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

  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