From: "Yadav, Sanjay Kumar" <sanjay.kumar.yadav@intel.com>
To: Matthew Auld <matthew.auld@intel.com>,
Arunpravin Paneer Selvam <arunpravin.paneerselvam@amd.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:36:27 +0530 [thread overview]
Message-ID: <da65f083-ab85-4f14-8be6-a720b9f6efc6@intel.com> (raw)
In-Reply-To: <8b622510-5dff-4adc-abe9-db7b782692e2@intel.com>
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.
>
>>
>> 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:07 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 [this message]
2026-11-17 13:13 ` Arunpravin Paneer Selvam
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=da65f083-ab85-4f14-8be6-a720b9f6efc6@intel.com \
--to=sanjay.kumar.yadav@intel.com \
--cc=William.Palacek@amd.com \
--cc=arunpravin.paneerselvam@amd.com \
--cc=dri-devel@lists.freedesktop.org \
--cc=intel-xe@lists.freedesktop.org \
--cc=joelagnelf@nvidia.com \
--cc=matthew.auld@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