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

[Arunpravin Paneer Selvam <arunpravin.paneerselvam@amd.com>]

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.

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