diff --git a/drivers/gpu/tests/gpu_buddy_test.c
b/drivers/gpu/tests/gpu_buddy_test.c
index 2c6f1da1a6d1..76392329e9e2 100644
--- a/drivers/gpu/tests/gpu_buddy_test.c
+++ b/drivers/gpu/tests/gpu_buddy_test.c
@@ -1595,6 +1595,312 @@ 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, div_u64(first_ns, NSEC_PER_USEC),
+ window, div_u64(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 +1927,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),
{}
};
