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

[PATCH v2 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.

This is a property of the range-biased allocation algorithm rather than
of any particular memory configuration. Any driver that repeatedly
restricts placement to a window can encounter this behavior once enough
small allocations accumulate in that window.

One configuration where the problem becomes particularly visible is a
small-BAR system. Drivers restrict every CPU-visible allocation to that
window with a range placement (fpfn = 0, lpfn = BAR size).

xe_pat@pt-caching-random-offsets does about 130k 4K range allocations
and hit the CI 180s inactivity timeout on a debug kernel inside
gpu_buddy_alloc_blocks(). With the full VRAM visible the same test does
not use the range path.

<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

v2:
- Reword cover letter and to describe this as a general fix for the
  algorithmic cost of range-biased allocation rather than a small-BAR
  specific issue (Matt A)
- No code changes

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 v2 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 28cff97d57dc..b77d7f621290 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 v2 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 2c6f1da1a6d1..dfe4ac9b5bad 100644
--- a/drivers/gpu/tests/gpu_buddy_test.c
+++ b/drivers/gpu/tests/gpu_buddy_test.c
@@ -1595,6 +1595,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)
@@ -1621,6 +1926,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 v2 2/2] gpu/tests/buddy: Add range-bias pruning and free-order tracking tests

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] gpu/tests/buddy: 64-bit division in gpu_test_buddy_range_bias_pruning()
--

commit c218b91af95d861d31913d5c9b3ba0681e319523
Author: Sanjay Yadav <sanjay.kumar.yadav@intel.com>

gpu/tests/buddy: Add range-bias pruning and free-order tracking tests

This commit adds KUnit tests in drivers/gpu/tests/gpu_buddy_test.c to verify
range-bias subtree pruning and subtree_max_free_order tracking across block
allocation, splitting, coalescing, and trimming operations.

> diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
> index b75d32ca6ca0a..4c7e823d57892 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 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;
[ ... ]
> +	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);

[Severity: Low]
In gpu_test_buddy_range_bias_pruning() in drivers/gpu/tests/gpu_buddy_test.c,
first_ns and last_ns are u64 variables that accumulate runtime nanosecond
durations. On 32-bit architectures with CONFIG_GPU_BUDDY_KUNIT_TEST enabled,
won't dividing them directly with the / operator by NSEC_PER_USEC emit calls
to __udivdi3 or __aeabi_uldivmod and cause a link failure?

Should this use div_u64() (or ktime_to_us()) instead?

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1792599420.git.sanjay.kumar.yadav@intel.com?part=2

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

[Yadav, Sanjay Kumar]

On 21-10-2026 22:54, sashiko-bot@kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [Low] gpu/tests/buddy: 64-bit division in gpu_test_buddy_range_bias_pruning()
> --
>
> commit c218b91af95d861d31913d5c9b3ba0681e319523
> Author: Sanjay Yadav <sanjay.kumar.yadav@intel.com>
>
> gpu/tests/buddy: Add range-bias pruning and free-order tracking tests
>
> This commit adds KUnit tests in drivers/gpu/tests/gpu_buddy_test.c to verify
> range-bias subtree pruning and subtree_max_free_order tracking across block
> allocation, splitting, coalescing, and trimming operations.
>
>> diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
>> index b75d32ca6ca0a..4c7e823d57892 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 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;
> [ ... ]
>> +	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);
> [Severity: Low]
> In gpu_test_buddy_range_bias_pruning() in drivers/gpu/tests/gpu_buddy_test.c,
> first_ns and last_ns are u64 variables that accumulate runtime nanosecond
> durations. On 32-bit architectures with CONFIG_GPU_BUDDY_KUNIT_TEST enabled,
> won't dividing them directly with the / operator by NSEC_PER_USEC emit calls
> to __udivdi3 or __aeabi_uldivmod and cause a link failure?
>
> Should this use div_u64() (or ktime_to_us()) instead?
Yes, this matches the kernel test robot’s __aeabi_uldivmod failure on 
32-bit ARM.
I reproduced it locally on 32bit compiler and confirmed that replacing 
the direct u64 divisions with div_u64() fixes the issue.
>
> [ ... ]
>