Intel-XE Archive on lore.kernel.org
 help / color / mirror / Atom feed
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)
>>>>>
>>>
>>


  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