[PATCH 0/2] gpu/buddy: Fix quadratic cost of range-biased allocation

[PATCH 0/2] gpu/buddy: Fix quadratic cost of range-biased allocation

[Sanjay Yadav]

Range-restricted allocations (GPU_BUDDY_RANGE_ALLOCATION) go through
__alloc_range_bias(), a depth-first walk over the buddy tree that visits
the higher-address child first. It skips blocks that are too small,
outside the range or ALLOCATED, but always descends SPLIT blocks, even
when nothing below them is free. Range allocations are placed top-down,
so they pack below the range end and each new allocation walks over all
blocks already allocated there: O(N) per allocation, O(N^2) in total,
under the driver's allocator lock.

On small-BAR systems only the start of VRAM is CPU accessible through
the PCI BAR. Drivers restrict every CPU-visible allocation to that
window with a range placement (fpfn = 0, lpfn = BAR size). In xe this
covers every pinned and mapped kernel BO (xe_bo_create_pin_map()),
including all page-table BOs, and user BOs created with
DRM_XE_GEM_CREATE_FLAG_NEEDS_VISIBLE_VRAM.

It is worst when VRAM is large but the BAR covers only part of it. On
the affected platform, VRAM is 160 GiB and the BAR is 32 GiB:

xe_pat@pt-caching-random-offsets creates 2 x 16384 4K BOs with
NEEDS_VISIBLE_VRAM and binds each at a random address in a 57-bit VA
space, which needs about three new page tables per bind. That is about
130k 4K range allocations in the visible window. In CI on a debug kernel
the test hit the 180s inactivity timeout inside gpu_buddy_alloc_blocks(),
called from xe_pt_create().

<6> [59.426526] [IGT] xe_pat: executing
<6> [59.436001] [IGT] xe_pat: starting subtest pt-caching-random-offsets
<6> [239.585293] task:xe_pat          state:R  running task     stack:0
pid:3700  tgid:3700  ppid:1957   task_flags:0x400100 flags:0x00000020
<6> [239.585304] Call Trace:
<6> [239.585307]  <TASK>
<6> [239.585309]  ? irqentry_exit+0x2a2/0x8d0
<6> [239.585314]  ? trace_hardirqs_off_finish+0xc7/0xe0
<6> [239.585320]  ? sysvec_apic_timer_interrupt+0x57/0xc0
<6> [239.585326]  ? asm_sysvec_apic_timer_interrupt+0x1b/0x20
<6> [239.585334]  ? gpu_buddy_alloc_blocks+0x442/0xec0
<6> [239.585341]  ? gpu_buddy_alloc_blocks+0xa37/0xec0
<6> [239.585353]  ? xe_ttm_vram_mgr_new+0x1c7/0x340 [xe]
<6> [239.585506]  ? ttm_resource_alloc+0x50/0xd0 [ttm]
<6> [239.585518]  ? ttm_bo_alloc_at_place+0x84/0x180 [ttm]
<6> [239.585527]  ? ttm_bo_alloc_resource+0x115/0x5e0 [ttm]
<6> [239.585538]  ? ttm_bo_validate+0x94/0x1c0 [ttm]
<6> [239.585546]  ? lock_is_held_type+0xa3/0x130
<6> [239.585552]  ? ttm_bo_init_reserved+0xa5/0x1f0 [ttm]
<6> [239.585560]  ? xe_bo_init_locked+0x20a/0x650 [xe]
<6> [239.585616]  ? __pfx_xe_ttm_bo_destroy+0x10/0x10 [xe]
<6> [239.585672]  ? stack_depot_save_flags+0x28/0x960
<6> [239.585679]  ? __xe_bo_create_locked+0xb1/0xa20 [xe]
<6> [239.585733]  ? _raw_spin_unlock_irqrestore+0x52/0x80
<6> [239.585743]  ? __create_object+0x67/0xe0
<6> [239.585747]  ? trace_hardirqs_on+0x22/0xe0
<6> [239.585753]  ? _raw_spin_unlock_irqrestore+0x52/0x80
<6> [239.585760]  ? xe_bo_create_pin_map_at_aligned+0x51/0x1f0 [xe]
<6> [239.585813]  ? __kmalloc_cache_noprof+0x494/0x670
<6> [239.585819]  ? xe_bo_create_pin_map+0x1f/0x40 [xe]
<6> [239.585870]  ? xe_pt_create+0xb5/0x430 [xe]

Patch 1 tracks, per block, the largest order of any FREE block in its
subtree and lets __alloc_range_bias() skip subtrees that cannot satisfy
the request. Skipped subtrees contain nothing the old walk could split
or return, and the remaining blocks are visited in the same order, so
the selected block and placement are unchanged. The new s8 field uses
existing tail padding.

Patch 2 adds KUnit tests. One fills a range prefix the way small-BAR
drivers do and checks pruning deterministically by hiding a free block
behind an ancestor that reports no free space. The other checks the
metadata of every block after each state change, including coalescing,
rollback of a partial allocation, and trim.

Results
  n_alloc     avg_blocks_visited        avg_allocation_time
              without fix  with fix     without fix  with fix
     4096          4141        46          10.7 us    0.293 us
    65536        127041        48           536 us    0.259 us
   126976        249911        47          1.46 ms    0.283 us

Sanjay Yadav (2):
  gpu/buddy: Prune exhausted subtrees in range-biased allocation
  gpu/tests/buddy: Add range-bias pruning and free-order tracking tests

 drivers/gpu/buddy.c                |  31 +++
 drivers/gpu/tests/gpu_buddy_test.c | 307 +++++++++++++++++++++++++++++
 include/linux/gpu_buddy.h          |   7 +
 3 files changed, 345 insertions(+)

-- 
2.52.0

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

[Sanjay Yadav]

__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 whenever a block changes
state, and skip subtrees that cannot satisfy the requested order.
gpu_buddy_block_trim() detaches the block while re-allocating inside
it, so 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.

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       | 31 +++++++++++++++++++++++++++++++
 include/linux/gpu_buddy.h |  7 +++++++
 2 files changed, 38 insertions(+)

diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index 2f2aaadafe35..7a975873238f 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,
@@ -772,6 +796,7 @@ static void mark_split(struct gpu_buddy *mm,
 	mm->free_scoreboard[gpu_buddy_block_order(block)]--;
 
 	rbtree_remove(mm, block);
+	update_subtree_max_free_order(block);
 }
 
 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
@@ -869,6 +894,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;
@@ -1280,6 +1307,9 @@ __alloc_range_bias(struct gpu_buddy *mm,
 		if (gpu_buddy_block_order(block) < order)
 			continue;
 
+		if (block->subtree_max_free_order < (int)order)
+			continue;
+
 		block_start = gpu_buddy_block_offset(block);
 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
 
@@ -1881,6 +1911,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)
 
-- 
2.52.0

[PATCH 2/2] gpu/tests/buddy: Add range-bias pruning and free-order tracking tests

[Sanjay Yadav]

gpu_test_buddy_range_bias_pruning fills a 128 MiB range of a 512 MiB
manager with 4K range allocations. It checks top-down placement, that
the exhausted range advertises GPU_BUDDY_NO_FREE_ORDER, -ENOSPC inside
the range while space outside stays usable, and that freed holes are
found again. To check pruning itself, it hides the only free block
behind an ancestor that advertises no free space and expects -ENOSPC;
without pruning the search would return that block. Allocation time is
reported but not asserted.

gpu_test_buddy_free_order_tracking covers root creation, split,
allocation, partial and full coalescing (4K vs 64K), rollback of a
partially satisfied request, gpu_buddy_block_trim() with and without an
explicit start, exact-range, clear and top-down allocations, and
teardown.

Both use a helper that checks every block's subtree_max_free_order
against its state and its children.

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/tests/gpu_buddy_test.c | 307 +++++++++++++++++++++++++++++
 1 file changed, 307 insertions(+)

diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
index b75d32ca6ca0..4c7e823d5789 100644
--- a/drivers/gpu/tests/gpu_buddy_test.c
+++ b/drivers/gpu/tests/gpu_buddy_test.c
@@ -1586,6 +1586,311 @@ static void gpu_test_buddy_addr_to_block(struct kunit *test)
 	gpu_buddy_fini(&mm);
 }
 
+static bool gpu_test_block_is_split(struct gpu_buddy_block *block)
+{
+	return (block->header & GPU_BUDDY_HEADER_STATE) == GPU_BUDDY_SPLIT;
+}
+
+static void gpu_test_check_free_order(struct kunit *test, struct gpu_buddy *mm)
+{
+	struct gpu_buddy_block *block, *bad = NULL;
+	unsigned int nr_bad = 0;
+	s8 expected, bad_expected = 0;
+	LIST_HEAD(dfs);
+	unsigned int i;
+
+	for (i = 0; i < mm->n_roots; i++)
+		list_add_tail(&mm->roots[i]->tmp_link, &dfs);
+
+	while ((block = list_first_entry_or_null(&dfs, struct gpu_buddy_block,
+						 tmp_link))) {
+		list_del(&block->tmp_link);
+
+		if (gpu_buddy_block_is_free(block)) {
+			expected = gpu_buddy_block_order(block);
+		} else if (gpu_test_block_is_split(block)) {
+			expected = max(block->left->subtree_max_free_order,
+				       block->right->subtree_max_free_order);
+			list_add(&block->right->tmp_link, &dfs);
+			list_add(&block->left->tmp_link, &dfs);
+		} else {
+			expected = GPU_BUDDY_NO_FREE_ORDER;
+		}
+
+		if (block->subtree_max_free_order != expected && !nr_bad++) {
+			bad = block;
+			bad_expected = expected;
+		}
+	}
+
+	KUNIT_EXPECT_EQ_MSG(test, nr_bad, 0U,
+			    "first stale block: offset=%#llx order=%u stored=%d expected=%d",
+			    bad ? gpu_buddy_block_offset(bad) : 0,
+			    bad ? gpu_buddy_block_order(bad) : 0,
+			    bad ? bad->subtree_max_free_order : 0, bad_expected);
+}
+
+static struct gpu_buddy_block *
+gpu_test_find_block(struct gpu_buddy *mm, u64 offset, unsigned int order)
+{
+	struct gpu_buddy_block *block;
+	unsigned int i;
+
+	for (i = 0; i < mm->n_roots; i++) {
+		u64 start;
+
+		block = mm->roots[i];
+		start = gpu_buddy_block_offset(block);
+		if (offset < start || offset >= start + gpu_buddy_block_size(mm, block))
+			continue;
+
+		while (gpu_buddy_block_order(block) > order) {
+			if (!gpu_test_block_is_split(block))
+				return NULL;
+			block = offset < gpu_buddy_block_offset(block->right) ?
+				block->left : block->right;
+		}
+		return block;
+	}
+
+	return NULL;
+}
+
+static struct gpu_buddy_block *
+gpu_test_take_block(struct list_head *blocks, u64 offset)
+{
+	struct gpu_buddy_block *block;
+
+	list_for_each_entry(block, blocks, link) {
+		if (gpu_buddy_block_offset(block) == offset) {
+			list_del(&block->link);
+			return block;
+		}
+	}
+
+	return NULL;
+}
+
+static void gpu_test_buddy_range_bias_pruning(struct kunit *test)
+{
+	const u64 mm_size = SZ_512M, range_end = SZ_128M, chunk = SZ_4K;
+	const unsigned int nr = range_end / chunk, window = 1024;
+	const u64 holes[] = { 0, range_end / 2 + 3 * chunk };
+	struct gpu_buddy_block *block, *hidden;
+	u64 first_ns = 0, last_ns = 0;
+	unsigned int i, misplaced = 0;
+	LIST_HEAD(allocated);
+	struct gpu_buddy mm;
+	LIST_HEAD(tmp);
+	int err;
+
+	KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, chunk),
+			       "buddy_init failed\n");
+	KUNIT_ASSERT_EQ(test, mm.n_roots, 1U);
+
+	/*
+	 * Small-BAR pattern: order-0 allocations confined to a low prefix of a
+	 * larger manager. Top-down placement packs them right below range_end,
+	 * so without pruning every allocation walks all previously allocated
+	 * blocks and the total cost is quadratic.
+	 */
+	for (i = 0; i < nr; i++) {
+		ktime_t start = ktime_get();
+		u64 elapsed;
+
+		err = gpu_buddy_alloc_blocks(&mm, 0, range_end, chunk, chunk,
+					     &allocated, GPU_BUDDY_RANGE_ALLOCATION);
+		elapsed = ktime_to_ns(ktime_sub(ktime_get(), start));
+		KUNIT_ASSERT_EQ_MSG(test, err, 0, "range alloc %u failed\n", i);
+
+		if (i < window)
+			first_ns += elapsed;
+		else if (i >= nr - window)
+			last_ns += elapsed;
+
+		block = list_last_entry(&allocated, struct gpu_buddy_block, link);
+		if (gpu_buddy_block_offset(block) != range_end - (u64)(i + 1) * chunk)
+			misplaced++;
+	}
+
+	kunit_info(test, "first %u range allocs: %llu us, last %u: %llu us\n",
+		   window, first_ns / NSEC_PER_USEC, window, last_ns / NSEC_PER_USEC);
+
+	/* Top-down placement inside the range is unchanged */
+	KUNIT_EXPECT_EQ(test, misplaced, 0U);
+
+	/* The exhausted range advertises no free space, so it is pruned */
+	block = gpu_test_find_block(&mm, 0, ilog2(range_end / chunk));
+	KUNIT_ASSERT_NOT_NULL(test, block);
+	KUNIT_EXPECT_EQ(test, block->subtree_max_free_order, GPU_BUDDY_NO_FREE_ORDER);
+	gpu_test_check_free_order(test, &mm);
+
+	KUNIT_EXPECT_EQ(test, gpu_buddy_alloc_blocks(&mm, 0, range_end, chunk, chunk,
+						     &tmp, GPU_BUDDY_RANGE_ALLOCATION),
+			-ENOSPC);
+
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, chunk, chunk,
+							&tmp, 0));
+	block = list_first_entry(&tmp, struct gpu_buddy_block, link);
+	KUNIT_EXPECT_GE(test, gpu_buddy_block_offset(block), range_end);
+	gpu_buddy_free_list(&mm, &tmp, 0);
+
+	/* A single hole, including the very last one in walk order, is found */
+	for (i = 0; i < ARRAY_SIZE(holes); i++) {
+		block = gpu_test_take_block(&allocated, holes[i]);
+		KUNIT_ASSERT_NOT_NULL(test, block);
+		gpu_buddy_free_block(&mm, block);
+		gpu_test_check_free_order(test, &mm);
+
+		KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 0, range_end,
+								chunk, chunk, &allocated,
+								GPU_BUDDY_RANGE_ALLOCATION));
+		block = list_last_entry(&allocated, struct gpu_buddy_block, link);
+		KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block), holes[i]);
+	}
+
+	/*
+	 * Deterministic pruning check: hide the only free block in the range
+	 * behind an ancestor that advertises no free space. Without pruning the
+	 * search would walk into that subtree and return the block.
+	 */
+	block = gpu_test_take_block(&allocated, holes[1]);
+	KUNIT_ASSERT_NOT_NULL(test, block);
+	gpu_buddy_free_block(&mm, block);
+	hidden = gpu_test_find_block(&mm, holes[1], 4);
+	KUNIT_ASSERT_NOT_NULL(test, hidden);
+	KUNIT_ASSERT_EQ(test, hidden->subtree_max_free_order, (s8)0);
+
+	hidden->subtree_max_free_order = GPU_BUDDY_NO_FREE_ORDER;
+	err = gpu_buddy_alloc_blocks(&mm, 0, range_end, chunk, chunk, &tmp,
+				     GPU_BUDDY_RANGE_ALLOCATION);
+	hidden->subtree_max_free_order = 0;
+	KUNIT_EXPECT_EQ(test, err, -ENOSPC);
+	gpu_buddy_free_list(&mm, &tmp, 0);
+	gpu_test_check_free_order(test, &mm);
+
+	gpu_buddy_free_list(&mm, &allocated, 0);
+	gpu_test_check_free_order(test, &mm);
+	KUNIT_EXPECT_EQ(test, mm.roots[0]->subtree_max_free_order, (s8)mm.max_order);
+
+	gpu_buddy_fini(&mm);
+}
+
+static void gpu_test_buddy_free_order_tracking(struct kunit *test)
+{
+	const u64 chunk = SZ_4K;
+	struct gpu_buddy_block *block;
+	LIST_HEAD(allocated);
+	struct gpu_buddy mm;
+	u64 start, avail;
+	LIST_HEAD(big);
+	unsigned int i;
+
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, SZ_8M + SZ_2M + SZ_64K, chunk));
+	KUNIT_EXPECT_EQ(test, mm.n_roots, 3U);
+	for (i = 0; i < mm.n_roots; i++)
+		KUNIT_EXPECT_EQ(test, mm.roots[i]->subtree_max_free_order,
+				(s8)gpu_buddy_block_order(mm.roots[i]));
+	gpu_test_check_free_order(test, &mm);
+	gpu_buddy_fini(&mm);
+
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, SZ_16M, chunk));
+	KUNIT_ASSERT_EQ(test, mm.n_roots, 1U);
+	for (i = 0; i < SZ_4M / chunk; i++)
+		KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_4M, chunk, chunk,
+								&allocated,
+								GPU_BUDDY_RANGE_ALLOCATION));
+	gpu_test_check_free_order(test, &mm);
+
+	/* Partial coalescing up to order 3 must not satisfy a 64K request */
+	for (i = 0; i < SZ_64K / chunk - 1; i++) {
+		block = gpu_test_take_block(&allocated, SZ_1M + i * chunk);
+		KUNIT_ASSERT_NOT_NULL(test, block);
+		gpu_buddy_free_block(&mm, block);
+	}
+	gpu_test_check_free_order(test, &mm);
+
+	/* A partially satisfied request is rolled back on -ENOSPC */
+	avail = mm.avail;
+	KUNIT_EXPECT_EQ(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_4M, SZ_128K, chunk, &big,
+						     GPU_BUDDY_RANGE_ALLOCATION),
+			-ENOSPC);
+	KUNIT_EXPECT_EQ(test, mm.avail, avail);
+	KUNIT_EXPECT_TRUE(test, list_empty(&big));
+	gpu_test_check_free_order(test, &mm);
+
+	KUNIT_EXPECT_EQ(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_4M, SZ_64K, SZ_64K, &big,
+						     GPU_BUDDY_RANGE_ALLOCATION),
+			-ENOSPC);
+	gpu_test_check_free_order(test, &mm);
+
+	/* SPLIT -> FREE: the last buddy coalesces the window into a 64K block */
+	block = gpu_test_take_block(&allocated, SZ_1M + SZ_64K - chunk);
+	KUNIT_ASSERT_NOT_NULL(test, block);
+	gpu_buddy_free_block(&mm, block);
+	gpu_test_check_free_order(test, &mm);
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_4M, SZ_64K, SZ_64K, &big,
+							GPU_BUDDY_RANGE_ALLOCATION));
+	block = list_last_entry(&big, struct gpu_buddy_block, link);
+	KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block), (u64)SZ_1M);
+	KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), (u64)SZ_64K);
+	gpu_test_check_free_order(test, &mm);
+
+	/* Trim with an explicit start re-allocates inside the detached block */
+	start = SZ_1M + SZ_16K;
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_block_trim(&mm, &start, SZ_16K, &big));
+	KUNIT_ASSERT_TRUE(test, list_is_singular(&big));
+	block = list_first_entry(&big, struct gpu_buddy_block, link);
+	KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block), start);
+	KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), (u64)SZ_16K);
+	gpu_test_check_free_order(test, &mm);
+
+	/* Exact-range allocation */
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, SZ_8M, SZ_8M + SZ_256K,
+							SZ_256K, chunk, &big, 0));
+	gpu_test_check_free_order(test, &mm);
+
+	/* Cleared frees, clear range allocation and top-down allocation */
+	gpu_buddy_free_list(&mm, &big, GPU_BUDDY_CLEARED);
+	gpu_test_check_free_order(test, &mm);
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, SZ_4M, SZ_16M, SZ_128K, chunk,
+							&big,
+							GPU_BUDDY_RANGE_ALLOCATION |
+							GPU_BUDDY_CLEAR_ALLOCATION));
+	gpu_test_check_free_order(test, &mm);
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_16M, SZ_1M, chunk, &big,
+							GPU_BUDDY_TOPDOWN_ALLOCATION));
+	gpu_test_check_free_order(test, &mm);
+
+	gpu_buddy_free_list(&mm, &big, 0);
+	gpu_buddy_free_list(&mm, &allocated, 0);
+	gpu_test_check_free_order(test, &mm);
+	KUNIT_EXPECT_EQ(test, mm.roots[0]->subtree_max_free_order, (s8)mm.max_order);
+	gpu_buddy_fini(&mm);
+
+	/*
+	 * Contiguous non-power-of-two allocations are trimmed, which re-allocates
+	 * inside a temporarily detached block. Ancestors must still be updated.
+	 */
+	KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, SZ_32K, chunk));
+	KUNIT_ASSERT_EQ(test, mm.n_roots, 1U);
+	for (i = 0; i < 2; i++) {
+		KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_32K,
+								SZ_8K + SZ_4K, chunk,
+								&allocated,
+								GPU_BUDDY_CONTIGUOUS_ALLOCATION));
+		gpu_test_check_free_order(test, &mm);
+	}
+	KUNIT_EXPECT_EQ(test, mm.roots[0]->subtree_max_free_order, (s8)0);
+	KUNIT_EXPECT_EQ(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_32K, SZ_8K, SZ_8K, &big,
+						     GPU_BUDDY_RANGE_ALLOCATION),
+			-ENOSPC);
+
+	gpu_buddy_free_list(&mm, &allocated, 0);
+	gpu_test_check_free_order(test, &mm);
+	gpu_buddy_fini(&mm);
+}
+
 static int gpu_buddy_suite_init(struct kunit_suite *suite)
 {
 	while (!random_seed)
@@ -1612,6 +1917,8 @@ static struct kunit_case gpu_buddy_tests[] = {
 	KUNIT_CASE(gpu_test_buddy_offset_aligned_allocation),
 	KUNIT_CASE(gpu_test_buddy_subtree_offset_alignment_stress),
 	KUNIT_CASE(gpu_test_buddy_addr_to_block),
+	KUNIT_CASE(gpu_test_buddy_range_bias_pruning),
+	KUNIT_CASE(gpu_test_buddy_free_order_tracking),
 	{}
 };
 
-- 
2.52.0

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

[Arunpravin Paneer Selvam]

On 10/12/2026 4:40 PM, 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 whenever a block changes
> state, and skip subtrees that cannot satisfy the requested order.
> gpu_buddy_block_trim() detaches the block while re-allocating inside
> it, so 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.
>
> 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       | 31 +++++++++++++++++++++++++++++++
>   include/linux/gpu_buddy.h |  7 +++++++
>   2 files changed, 38 insertions(+)
>
> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> index 2f2aaadafe35..7a975873238f 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,
> @@ -772,6 +796,7 @@ static void mark_split(struct gpu_buddy *mm,
>   	mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>   
>   	rbtree_remove(mm, block);
> +	update_subtree_max_free_order(block);
>   }
Just wondering if touching mark_free(), mark_allocated(), mark_split() 
which are hot-path functions, could have any performance implications.?

Regards,
Arun.
>   
>   static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
> @@ -869,6 +894,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;
> @@ -1280,6 +1307,9 @@ __alloc_range_bias(struct gpu_buddy *mm,
>   		if (gpu_buddy_block_order(block) < order)
>   			continue;
>   
> +		if (block->subtree_max_free_order < (int)order)
> +			continue;
> +
>   		block_start = gpu_buddy_block_offset(block);
>   		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
>   
> @@ -1881,6 +1911,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)
>