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

[Yadav, Sanjay Kumar]

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.a...@intel.com>
Cc: Arun Pravin <arunpravin.paneersel...@amd.com>
Cc: Joel Fernandes <joelagn...@nvidia.com>
Assisted-by: LLM
Signed-off-by: Sanjay Yadav <sanjay.kumar.ya...@intel.com>

Gentle ping

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