> On Nov 4, 2026, at 7:13 AM, Yadav, Sanjay Kumar
> <[email protected]> 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 <[email protected]>
>> Cc: Arun Pravin <[email protected]>
>> Cc: Joel Fernandes <[email protected]>
>> Assisted-by: LLM
>> Signed-off-by: Sanjay Yadav <[email protected]>
> Gentle ping
Can you provide performance numbers with this change too?
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)
>>
