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

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

On 04-11-2026 17:42, Yadav, Sanjay Kumar 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

Hi Arun

Could you please review?

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