AMD General Hi Arun,
Thanks for putting this together. I applied it on drm-misc-next (6f7098738fff) and ran the gpu_buddy KUnit suite: all 16 pass, including the range_bias_performance test from my v2 (2 ms). Your clear_guard test fails without the patch and passes with it, so the regression coverage looks good. I tried one more pattern: 4 GiB manager, range [1G, 2G) filled with 64K blocks, then every other block freed as cleared (8192 free cleared blocks interleaved with allocated ones). - 4096 cleared, non-top-down allocations (amdgpu does this for CPU-visible VRAM): stock 117 ms, your patch 142 ms, v2 0 ms. rbtree_range_best_block() scores every matching free block in the window before picking one, so it is linear in the number of free cleared blocks. - 4096 dirty, top-down allocations into the same range: stock 120 ms, your patch 91 ms, v2 0 ms. The strict pass walks past every incompatible free block with rb_prev() before falling back. v2 doesn't have this problem, but it also doesn't keep cleared and dirty apart the way your guard does. Would it make sense to split this into two patches, the clear/dirty guard first (with the Fixes tag) and then the lookup on top? Then I could rebase v2 onto the guard, or you could fold the lookup into yours, whichever you prefer. Thanks, William -----Original Message----- From: Paneer Selvam, Arunpravin <[email protected]> Sent: Monday, November 9, 2026 1:41 AM To: Sanjay Yadav <[email protected]>; [email protected]; Palacek, William <[email protected]> Cc: [email protected]; Matthew Auld <[email protected]>; Joel Fernandes <[email protected]> Subject: Re: [PATCH v4 1/1] gpu/buddy: Prune exhausted subtrees in range-biased allocation 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 <[email protected]> > Cc: Arun Pravin <[email protected]> > Cc: Joel Fernandes <[email protected]> > Assisted-by: LLM > Signed-off-by: Sanjay Yadav <[email protected]> > --- > 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) >
