Re: [PATCH v4 1/1] gpu/buddy: Prune exhausted subtrees in range-biased allocation

["Yadav, Sanjay Kumar" <sanjay.kumar.yadav@intel.com>]

On 06-11-2026 19:15, Joel Fernandes wrote:
>
>> On Nov 4, 2026, at 7:13 AM, Yadav, Sanjay Kumar <sanjay.kumar.yadav@intel.com> wrote:
>>
>> 
>>> On 02-11-2026 10:46, 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.
>>>
>>> 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>
>> Gentle ping
> Can you provide performance numbers with this change too?
>
> Thanks
>
Existing gpu_buddy KUnit performance tests, drm-tip vs drm-tip + patch:

Test                                            drm-tip        + patch
Fragmented allocation                            139ms       154ms
Reverse-ordered free                            91ms        96ms
Contiguous alloc after fragmentation            8ms            8ms
Repeated 256 KiB allocs from fragmented pool    14ms        14ms

Metric                                        Without Patch With Patch
Average range-allocation time                78-793µs  340-494ns
Blocks visited per allocation                16K-147K        38-39
xe_pat pt-caching-random-offsets runtime    ~48s            ~0.7s

Sharing the same data that was previously requested by Arun. Please let 
me know if you need any
additional or specific data.

Thanks

>>> ---
>>>   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)
>>>