From: Arunpravin Paneer Selvam <arunpravin.paneerselvam@amd.com>
To: "Yadav, Sanjay Kumar" <sanjay.kumar.yadav@intel.com>,
Matthew Auld <matthew.auld@intel.com>,
dri-devel@lists.freedesktop.org,
William Palacek <William.Palacek@amd.com>
Cc: intel-xe@lists.freedesktop.org, Joel Fernandes <joelagnelf@nvidia.com>
Subject: Re: [PATCH v4 1/1] gpu/buddy: Prune exhausted subtrees in range-biased allocation
Date: Tue, 17 Nov 2026 18:43:20 +0530 [thread overview]
Message-ID: <fb5c1552-e47e-4530-bf7b-20763e338fdb@amd.com> (raw)
In-Reply-To: <da65f083-ab85-4f14-8be6-a720b9f6efc6@intel.com>
On 11/17/2026 6:36 PM, Yadav, Sanjay Kumar wrote:
>
> On 17-11-2026 15:27, Matthew Auld wrote:
>> On 17/11/2026 04:57, Arunpravin Paneer Selvam wrote:
>>>
>>>
>>> On 11/15/2026 9:23 PM, Yadav, Sanjay Kumar wrote:
>>>>
>>>> On 09-11-2026 12:10, Arunpravin Paneer Selvam wrote:
>>>>> Hi Sanjay,
>>>>>
>>>>> On 11/2/2026 10:46 AM, Sanjay Yadav wrote:
>>>>>> __alloc_range_bias() walks the buddy tree depth-first, higher
>>>>>> address
>>>>>> first, and descends every SPLIT block even when nothing below it is
>>>>>> free. Range allocations are placed top-down, so they pack below the
>>>>>> range end and each new one walks every block already allocated
>>>>>> there:
>>>>>> O(N) per allocation and O(N^2) for N allocations, under the
>>>>>> allocator
>>>>>> lock.
>>>>>>
>>>>>> Track in each block the largest order of any FREE block in its
>>>>>> subtree
>>>>>> (GPU_BUDDY_NO_FREE_ORDER if none), update it when a block is
>>>>>> allocated
>>>>>> or freed, and skip subtrees that cannot satisfy the requested order.
>>>>>> Splitting needs no update of its own, as both children are marked
>>>>>> free
>>>>>> right after and that propagates the new value up.
>>>>>> gpu_buddy_block_trim() detaches the block before freeing it, so
>>>>>> updates
>>>>>> stop there while re-allocating inside it; recompute from the parent
>>>>>> once it is reattached.
>>>>>>
>>>>>> Skipped subtrees contain no FREE block of the requested order or
>>>>>> larger, so the old walk could neither split nor return anything
>>>>>> there.
>>>>>> The remaining blocks are visited in the same order, so the selected
>>>>>> block and placement are unchanged.
>>>>> I am not receiving some of the emails you are. sending me. I think
>>>>> there may be an issue with my mailbox, so I need to check that on
>>>>> my side.
>>>>> William has also been working on improving the range-allocation
>>>>> performance in drm_buddy. His patch is here:
>>>>>
>>>>> https://patchwork.freedesktop.org/patch/763478/
>>>>>
>>>>> Since both patches are trying to improve the same range-allocation
>>>>> path, I would like to converge on a single upstream approach
>>>>> rather than carry separate optimizations.
>>>>> I have put together a version based on William’s offset-sorted
>>>>> free- tree approach, extending the search to be class-aware:
>>>>>
>>>>> https://gitlab.freedesktop.org/arunpravin24/drm-buddy-range-wip/-/
>>>>> commit/72414977d38f4bcf7a364c64f24aa7f25cf699d9
>>>>>
>>>>> With this approach, we can remove the buddy-tree DFS walk
>>>>> entirely. Cleared blocks are located using the existing
>>>>> subtree_block_state augmentation, and top-down placement comes
>>>>> directly from the offset- sorted free trees, reducing the lookup
>>>>> to an O(log n) free-tree search followed by a small bounded scan.
>>>>>
>>>>> @Sanjay, could you take a look at the version above? I think it
>>>>> would be better to follow this approach upstream and create a
>>>>> patch with the test cases around it.
>>>> I tested your WIP on our side (applied on current drm-tip, on top of
>>>> the merged two-pass guard).
>>>>
>>>> BMG, CPU-visible BAR resized to 4GB, xe_pat@pt-caching-random-offsets:
>>>>
>>>> drm-tip ~48-51s
>>>> drm-tip + my v4 ~0.7s
>>>> drm-tip + your WIP ~0.75s
>>>> (drm-tip, full BAR ~0.7s, range path not used)
>>>> So your version fixes the xe small-BAR case as well as v4 and looks
>>>> good to me.
>>>> v4(already R-b/T-b by Joel) could go in first as the small fix and
>>>> your
>>>> series replace the walk on top. Whichever you and Matt prefer.
>>> Okay, please confirm with Matthew. If this is the final version, I
>>> will merge it upstream.
>>
>> Yeah, ack from my side.
> Thanks Matt for Ack.
> FYI Arun: I need to send one more version just for CI because CI was
> not run on v4.
Also, rebase on drm-misc-next.
>>
>>>
>>> Regards,
>>> Arun.
>>>>>
>>>>> @William, could you also take a look at the version above?
>>>>> Hopefully we can follow the same approach when porting this
>>>>> optimization to the older dual-free-tree branch
>>>>> used by the ROCm versions you are targeting.
>>>>>
>>>>> Thanks,
>>>>> Arun
>>>>>>
>>>>>> v4: (Matt A)
>>>>>> - Drop the update in mark_split(), the children being marked free
>>>>>> updates the parent
>>>>>> - Detach the block before __mark_free() in
>>>>>> gpu_buddy_block_trim(), so
>>>>>> only the final update from the parent propagates up
>>>>>> - Drop the order, is_allocated() and is_free() checks in
>>>>>> __alloc_range_bias() that the pruning check now covers
>>>>>>
>>>>>> Cc: Matthew Auld <matthew.auld@intel.com>
>>>>>> Cc: Arun Pravin <arunpravin.paneerselvam@amd.com>
>>>>>> Cc: Joel Fernandes <joelagnelf@nvidia.com>
>>>>>> Assisted-by: LLM
>>>>>> Signed-off-by: Sanjay Yadav <sanjay.kumar.yadav@intel.com>
>>>>>> ---
>>>>>> drivers/gpu/buddy.c | 56 ++++++++++++++++++++++++++
>>>>>> +------------
>>>>>> include/linux/gpu_buddy.h | 7 +++++
>>>>>> 2 files changed, 46 insertions(+), 17 deletions(-)
>>>>>>
>>>>>> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
>>>>>> index 28cff97d57dc..93f70c98b235 100644
>>>>>> --- a/drivers/gpu/buddy.c
>>>>>> +++ b/drivers/gpu/buddy.c
>>>>>> @@ -602,6 +602,7 @@ static struct gpu_buddy_block
>>>>>> *gpu_block_alloc(struct gpu_buddy *mm,
>>>>>> block->header = offset;
>>>>>> block->header |= order;
>>>>>> block->parent = parent;
>>>>>> + block->subtree_max_free_order = GPU_BUDDY_NO_FREE_ORDER;
>>>>>> RB_CLEAR_NODE(&block->rb);
>>>>>> @@ -717,6 +718,27 @@ static void rbtree_remove(struct gpu_buddy
>>>>>> *mm,
>>>>>> RB_CLEAR_NODE(&block->rb);
>>>>>> }
>>>>>> +static void update_subtree_max_free_order(struct
>>>>>> gpu_buddy_block *block)
>>>>>> +{
>>>>>> + while (block) {
>>>>>> + s8 max_free;
>>>>>> +
>>>>>> + if (gpu_buddy_block_is_free(block))
>>>>>> + max_free = gpu_buddy_block_order(block);
>>>>>> + else if (gpu_buddy_block_is_split(block))
>>>>>> + max_free = max(block->left->subtree_max_free_order,
>>>>>> + block->right->subtree_max_free_order);
>>>>>> + else
>>>>>> + max_free = GPU_BUDDY_NO_FREE_ORDER;
>>>>>> +
>>>>>> + if (block->subtree_max_free_order == max_free)
>>>>>> + break;
>>>>>> +
>>>>>> + block->subtree_max_free_order = max_free;
>>>>>> + block = block->parent;
>>>>>> + }
>>>>>> +}
>>>>>> +
>>>>>> static void mark_allocated(struct gpu_buddy *mm,
>>>>>> struct gpu_buddy_block *block)
>>>>>> {
>>>>>> @@ -729,6 +751,7 @@ static void mark_allocated(struct gpu_buddy *mm,
>>>>>> mm->used_scoreboard[gpu_buddy_block_order(block)]++;
>>>>>> rbtree_remove(mm, block);
>>>>>> + update_subtree_max_free_order(block);
>>>>>> }
>>>>>> static void __mark_free(struct gpu_buddy *mm,
>>>>>> @@ -750,6 +773,7 @@ static void __mark_free(struct gpu_buddy *mm,
>>>>>> mm->free_scoreboard[gpu_buddy_block_order(block)]++;
>>>>>> rbtree_insert(mm, block);
>>>>>> + update_subtree_max_free_order(block);
>>>>>> }
>>>>>> static void mark_free(struct gpu_buddy *mm,
>>>>>> @@ -869,6 +893,8 @@ int gpu_buddy_init(struct gpu_buddy *mm, u64
>>>>>> size, u64 chunk_size)
>>>>>> size = round_down(size, chunk_size);
>>>>>> + BUILD_BUG_ON(GPU_BUDDY_MAX_ORDER > S8_MAX);
>>>>>> +
>>>>>> mm->size = size;
>>>>>> mm->avail = size;
>>>>>> mm->chunk_size = chunk_size;
>>>>>> @@ -1277,7 +1303,7 @@ __alloc_range_bias(struct gpu_buddy *mm,
>>>>>> list_del(&block->tmp_link);
>>>>>> - if (gpu_buddy_block_order(block) < order)
>>>>>> + if (block->subtree_max_free_order < (int)order)
>>>>>> continue;
>>>>>> block_start = gpu_buddy_block_offset(block);
>>>>>> @@ -1286,9 +1312,6 @@ __alloc_range_bias(struct gpu_buddy *mm,
>>>>>> if (!overlaps(start, end, block_start, block_end))
>>>>>> continue;
>>>>>> - if (gpu_buddy_block_is_allocated(block))
>>>>>> - continue;
>>>>>> -
>>>>>> if (block_start < start || block_end > end) {
>>>>>> u64 adjusted_start = max(block_start, start);
>>>>>> u64 adjusted_end = min(block_end, end);
>>>>>> @@ -1298,16 +1321,10 @@ __alloc_range_bias(struct gpu_buddy *mm,
>>>>>> continue;
>>>>>> }
>>>>>> + /* Not pruned at @order, so this block itself is FREE */
>>>>>> if (contains(start, end, block_start, block_end) &&
>>>>>> - order == gpu_buddy_block_order(block)) {
>>>>>> - /*
>>>>>> - * Find the free block within the range.
>>>>>> - */
>>>>>> - if (gpu_buddy_block_is_free(block))
>>>>>> - return block;
>>>>>> -
>>>>>> - continue;
>>>>>> - }
>>>>>> + order == gpu_buddy_block_order(block))
>>>>>> + return block;
>>>>>> if (!gpu_buddy_block_is_split(block)) {
>>>>>> err = split_block(mm, block);
>>>>>> @@ -1856,13 +1873,17 @@ int gpu_buddy_block_trim(struct gpu_buddy
>>>>>> *mm,
>>>>>> gpu_buddy_block_offset(block),
>>>>>> gpu_buddy_block_size(mm, block));
>>>>>> - __mark_free(mm, block, was_clear ? GPU_BLOCK_CLEAR :
>>>>>> GPU_BLOCK_DIRTY);
>>>>>> - mm->avail += gpu_buddy_block_size(mm, block);
>>>>>> -
>>>>>> - /* Prevent recursively freeing this node */
>>>>>> + /*
>>>>>> + * Detach the block to prevent recursively freeing this
>>>>>> node, and to
>>>>>> + * keep free-order updates from propagating above it until
>>>>>> the trim
>>>>>> + * is done.
>>>>>> + */
>>>>>> parent = block->parent;
>>>>>> block->parent = NULL;
>>>>>> + __mark_free(mm, block, was_clear ? GPU_BLOCK_CLEAR :
>>>>>> GPU_BLOCK_DIRTY);
>>>>>> + mm->avail += gpu_buddy_block_size(mm, block);
>>>>>> +
>>>>>> list_add(&block->tmp_link, &dfs);
>>>>>> err = __alloc_range(mm, &dfs, new_start, new_size,
>>>>>> was_clear ? GPU_BUDDY_CLEAR_ALLOCATION : 0,
>>>>>> @@ -1881,6 +1902,7 @@ int gpu_buddy_block_trim(struct gpu_buddy *mm,
>>>>>> }
>>>>>> block->parent = parent;
>>>>>> + update_subtree_max_free_order(parent);
>>>>>> return err;
>>>>>> }
>>>>>> EXPORT_SYMBOL(gpu_buddy_block_trim);
>>>>>> diff --git a/include/linux/gpu_buddy.h b/include/linux/gpu_buddy.h
>>>>>> index ddc4eca84175..8037f5a0feb1 100644
>>>>>> --- a/include/linux/gpu_buddy.h
>>>>>> +++ b/include/linux/gpu_buddy.h
>>>>>> @@ -141,8 +141,15 @@ struct gpu_buddy_block {
>>>>>> unsigned int subtree_max_alignment;
>>>>>> struct list_head tmp_link;
>>>>>> bool has_clear;
>>>>>> + /*
>>>>>> + * Largest order of any FREE block in this block's buddy
>>>>>> subtree, or
>>>>>> + * GPU_BUDDY_NO_FREE_ORDER if none. Protected by the driver
>>>>>> lock.
>>>>>> + */
>>>>>> + s8 subtree_max_free_order;
>>>>>> };
>>>>>> +#define GPU_BUDDY_NO_FREE_ORDER (-1)
>>>>>> +
>>>>>> /* Order-zero must be at least SZ_4K */
>>>>>> #define GPU_BUDDY_MAX_ORDER (63 - 12)
>>>>>
>>>
>>
next prev parent reply other threads:[~2026-11-17 13:14 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-02 5:16 [PATCH v4 0/1] gpu/buddy: Fix quadratic cost of range-biased allocation Sanjay Yadav
2026-11-02 5:16 ` [PATCH v4 1/1] gpu/buddy: Prune exhausted subtrees in " Sanjay Yadav
2026-11-04 12:12 ` Yadav, Sanjay Kumar
2026-11-06 12:20 ` Yadav, Sanjay Kumar
2026-11-06 13:45 ` Joel Fernandes
2026-11-06 15:58 ` Yadav, Sanjay Kumar
2026-11-07 14:56 ` Joel Fernandes
2026-11-09 6:40 ` Arunpravin Paneer Selvam
2026-11-09 14:07 ` Palacek, William
2026-11-12 14:45 ` Arunpravin Paneer Selvam
2026-11-15 15:53 ` Yadav, Sanjay Kumar
2026-11-17 4:57 ` Arunpravin Paneer Selvam
2026-11-17 9:57 ` Matthew Auld
2026-11-17 13:06 ` Yadav, Sanjay Kumar
2026-11-17 13:13 ` Arunpravin Paneer Selvam [this message]
2026-11-02 5:30 ` ✗ CI.checkpatch: warning for gpu/buddy: Fix quadratic cost of range-biased allocation (rev5) Patchwork
2026-11-02 5:33 ` ✓ CI.KUnit: success " Patchwork
2026-11-02 6:06 ` ✗ Xe.CI.BAT: failure " Patchwork
2026-11-02 6:34 ` ✗ Xe.CI.FULL: " Patchwork
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=fb5c1552-e47e-4530-bf7b-20763e338fdb@amd.com \
--to=arunpravin.paneerselvam@amd.com \
--cc=William.Palacek@amd.com \
--cc=dri-devel@lists.freedesktop.org \
--cc=intel-xe@lists.freedesktop.org \
--cc=joelagnelf@nvidia.com \
--cc=matthew.auld@intel.com \
--cc=sanjay.kumar.yadav@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox