[PATCH v3] gpu/buddy: restore two-pass clear/dirty guard for range-biased allocation

[PATCH v3] gpu/buddy: restore two-pass clear/dirty guard for range-biased allocation

[Arunpravin Paneer Selvam]

From: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>

Range-restricted allocations (the visible-VRAM aperture) skip
dirty_steer_window() and reach __alloc_range_bias() with no clear/dirty
eligibility guard, so a dirty allocation freely splits clear extents (and
vice versa), interleaving the two classes until no large same-class run
survives and a 4K scanout pin fails with -ENOSPC. Use a two-pass range
search instead: block_incompatible() rejects opposite-class blocks in the
strict pass and relaxes only when the strict pass returns -ENOSPC, so a
request still succeeds when only opposite-class space remains. A KUnit
regression test covers the interleaving pattern and fails without the
guard.

v2: the strict pass can split a block and then reject both children, so
    a split no longer implies a compatible block exists. Sashiko reported
    the resulting leaked splits; fix as suggested by Matthew:
 - Push the parent back on the DFS stack after each split and merge it
   back with unsplit_block() if both children are still free.
 - Make block_incompatible() judge free blocks only (split nodes keep a
   stale clear bit) and take the requested order, so mixed blocks that
   can hold a compatible block are descended instead of skipped.
 - Extend the KUnit test with a coalesced mixed block and a check that
   a rejected split is merged back.

v3: igt@kms_plane@plane-panning-bottom-right failed on Radeon RX 9070 XT
    with -ENOSPC: the range allocator's strict pass split mixed blocks to
    look for a wholly-clear (or wholly-dirty) leaf, discarded the mixed
    leaves it found, and ran unsplit_block to merge the splits back, whose
    per-allocation cost and residual fragmentation starved the large
    pipe-A scanout. Fix: accept a mixed block at the requested order as-is
    (caller re-clears), so the first pass no longer splits and discards
    mixed blocks. This clear/dirty compatibility relaxation applies only
    to range-biased allocation, where keeping blocks intact reduces
    fragmentation and preserves large contiguous spaces. The now-unneeded
    unsplit_block helper is dropped.

Fixes: 1ad5e807f716 ("gpu/buddy: replace dual-tree/force_merge with decoupled dirty tracker")
Assisted-by: LLM
Cc: Matthew Auld <matthew.auld@intel.com>
Cc: Christian König <christian.koenig@amd.com>
Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
---
 drivers/gpu/buddy.c                | 75 +++++++++++++-------------
 drivers/gpu/tests/gpu_buddy_test.c | 84 ++++++++++++++++++++++++++++++
 2 files changed, 122 insertions(+), 37 deletions(-)

diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index 28cff97d57dc..f2914f919b04 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -1240,11 +1240,23 @@ static void __gpu_buddy_undo_splits(struct gpu_buddy *mm,
 	}
 }
 
+static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags)
+{
+	bool needs_clear = flags & GPU_BUDDY_CLEAR_ALLOCATION;
+
+	if (!gpu_buddy_block_is_free(block))
+		return false;
+
+	return needs_clear ? !block->has_clear :
+			     gpu_buddy_block_is_clear(block);
+}
+
 static struct gpu_buddy_block *
 __alloc_range_bias(struct gpu_buddy *mm,
 		   u64 start, u64 end,
 		   unsigned int order,
-		   unsigned long flags)
+		   unsigned long flags,
+		   bool fallback)
 {
 	u64 req_size = mm->chunk_size << order;
 	struct gpu_buddy_block *block;
@@ -1258,9 +1270,7 @@ __alloc_range_bias(struct gpu_buddy *mm,
 	 * This range-constrained search hands back the highest/right-most
 	 * address that satisfies the request: the roots are seeded high-to-low
 	 * and the right (higher-address) child is descended first, making
-	 * top-down the default placement here. A non-top-down clear request is
-	 * the only exception, where the descent is biased towards clear or
-	 * clear-containing subtrees to satisfy the clear preference.
+	 * top-down the default placement here.
 	 */
 	for (i = mm->n_roots - 1; i >= 0; --i)
 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);
@@ -1298,6 +1308,9 @@ __alloc_range_bias(struct gpu_buddy *mm,
 				continue;
 		}
 
+		if (!fallback && block_incompatible(block, flags))
+			continue;
+
 		if (contains(start, end, block_start, block_end) &&
 		    order == gpu_buddy_block_order(block)) {
 			/*
@@ -1315,38 +1328,8 @@ __alloc_range_bias(struct gpu_buddy *mm,
 				goto err_undo;
 		}
 
-		/*
-		 * Top-down is a strict address-placement policy, so when it is
-		 * requested we ignore clear steering and simply descend the
-		 * right (higher-address) child first. Only a non-top-down clear
-		 * request biases the descent towards clear/has_clear subtrees.
-		 */
-		if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
-		    !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) {
-			struct gpu_buddy_block *prefer;
-
-			if (gpu_buddy_block_is_clear(block->right))
-				prefer = block->right;
-			else if (gpu_buddy_block_is_clear(block->left))
-				prefer = block->left;
-			else if (block->right->has_clear)
-				prefer = block->right;
-			else if (block->left->has_clear)
-				prefer = block->left;
-			else
-				prefer = block->right;
-
-			if (prefer == block->right) {
-				list_add(&block->left->tmp_link, &dfs);
-				list_add(&block->right->tmp_link, &dfs);
-			} else {
-				list_add(&block->right->tmp_link, &dfs);
-				list_add(&block->left->tmp_link, &dfs);
-			}
-		} else {
-			list_add(&block->left->tmp_link, &dfs);
-			list_add(&block->right->tmp_link, &dfs);
-		}
+		list_add(&block->left->tmp_link, &dfs);
+		list_add(&block->right->tmp_link, &dfs);
 	} while (1);
 
 	return ERR_PTR(-ENOSPC);
@@ -1361,6 +1344,24 @@ __alloc_range_bias(struct gpu_buddy *mm,
 	return ERR_PTR(err);
 }
 
+static struct gpu_buddy_block *
+__gpu_buddy_alloc_range_bias(struct gpu_buddy *mm,
+			     u64 start, u64 end,
+			     unsigned int order,
+			     unsigned long flags)
+{
+	struct gpu_buddy_block *block;
+	bool fallback = false;
+
+	block = __alloc_range_bias(mm, start, end, order,
+				   flags, fallback);
+	if (IS_ERR(block))
+		return __alloc_range_bias(mm, start, end, order,
+					  flags, !fallback);
+
+	return block;
+}
+
 /* Return the highest-address free block of at least @order. */
 static struct gpu_buddy_block *
 get_maxblock(struct gpu_buddy *mm,
@@ -1924,7 +1925,7 @@ __gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
 
 	if (flags & GPU_BUDDY_RANGE_ALLOCATION) {
 		/* Allocate traversing within the range */
-		block = __alloc_range_bias(mm, start, end, order, flags);
+		block = __gpu_buddy_alloc_range_bias(mm, start, end, order, flags);
 		if (!IS_ERR(block) || !steered)
 			return block;
 
diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
index 2c6f1da1a6d1..9aaca2fc6a02 100644
--- a/drivers/gpu/tests/gpu_buddy_test.c
+++ b/drivers/gpu/tests/gpu_buddy_test.c
@@ -1606,6 +1606,89 @@ static int gpu_buddy_suite_init(struct kunit_suite *suite)
 	return 0;
 }
 
+static void gpu_test_buddy_alloc_range_clear_guard(struct kunit *test)
+{
+	const unsigned long chunk = SZ_1M, mm_size = SZ_4M;
+	struct gpu_buddy_block *block;
+	LIST_HEAD(low_dirty);
+	LIST_HEAD(high_a);
+	LIST_HEAD(high_b);
+	LIST_HEAD(barrier);
+	LIST_HEAD(dirty_res);
+	LIST_HEAD(clear_res);
+	struct gpu_buddy mm;
+
+	KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, chunk),
+			       "buddy_init failed\n");
+
+	/*
+	 * Idea is to lay out a range allocation as a low dirty block, an
+	 * allocated barrier, and a high naturally-aligned clear extent, then
+	 * issue a dirty range allocation. It must take the low dirty block and
+	 * leave the clear extent intact; if it instead cuts the clear extent,
+	 * a following same-class clear allocation can no longer find a
+	 * contiguous clear run and fails with -ENOSPC.
+	 *
+	 *   [0,  1M)   dirty free
+	 *   [1M, 2M)   allocated  (barrier, keeps the halves un-mergeable)
+	 *   [2M, 4M)   clear free (one naturally aligned 2 MiB extent)
+	 */
+	KUNIT_ASSERT_FALSE_MSG(test,
+			       gpu_buddy_alloc_blocks(&mm, 0, chunk, chunk, chunk,
+						      &low_dirty, GPU_BUDDY_RANGE_ALLOCATION),
+			       "alloc [0, 1M) failed\n");
+	KUNIT_ASSERT_FALSE_MSG(test,
+			       gpu_buddy_alloc_blocks(&mm, chunk, 2 * chunk, chunk, chunk,
+						      &barrier, GPU_BUDDY_RANGE_ALLOCATION),
+			       "alloc [1M, 2M) failed\n");
+	KUNIT_ASSERT_FALSE_MSG(test,
+			       gpu_buddy_alloc_blocks(&mm, 2 * chunk, 3 * chunk, chunk, chunk,
+						      &high_a, GPU_BUDDY_RANGE_ALLOCATION),
+			       "alloc [2M, 3M) failed\n");
+	KUNIT_ASSERT_FALSE_MSG(test,
+			       gpu_buddy_alloc_blocks(&mm, 3 * chunk, 4 * chunk, chunk, chunk,
+						      &high_b, GPU_BUDDY_RANGE_ALLOCATION),
+			       "alloc [3M, 4M) failed\n");
+
+	/* [2M, 4M) coalesces into one aligned clear extent; [0, 1M) stays dirty. */
+	gpu_buddy_free_list(&mm, &low_dirty, 0);
+	gpu_buddy_free_list(&mm, &high_a, GPU_BUDDY_CLEARED);
+	gpu_buddy_free_list(&mm, &high_b, GPU_BUDDY_CLEARED);
+
+	/* Dirty 1 MiB range alloc: must land at [0, 1M), not cut the clear extent. */
+	KUNIT_ASSERT_FALSE_MSG(test,
+			       gpu_buddy_alloc_blocks(&mm, 0, mm_size, chunk, chunk,
+						      &dirty_res, GPU_BUDDY_RANGE_ALLOCATION),
+			       "dirty range alloc failed\n");
+	block = list_first_entry(&dirty_res, struct gpu_buddy_block, link);
+	KUNIT_EXPECT_FALSE_MSG(test, gpu_buddy_block_is_clear(block),
+			       "dirty range alloc cut the clear extent (offset=%llx)\n",
+			       gpu_buddy_block_offset(block));
+	KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block), 0ULL);
+
+	/*
+	 * The 2 MiB clear extent must still be intact: a clear order-1 range
+	 * allocation has to succeed. Without the guard the extent was cut
+	 * above and this returns -ENOSPC.
+	 */
+	KUNIT_EXPECT_FALSE_MSG(test,
+			       gpu_buddy_alloc_blocks(&mm, 0, mm_size, 2 * chunk, 2 * chunk,
+						      &clear_res,
+						      GPU_BUDDY_RANGE_ALLOCATION |
+						      GPU_BUDDY_CLEAR_ALLOCATION),
+			       "clear 2M range alloc failed: clear extent was fragmented (-ENOSPC)\n");
+	if (!list_empty(&clear_res)) {
+		block = list_first_entry(&clear_res, struct gpu_buddy_block, link);
+		KUNIT_EXPECT_TRUE(test, gpu_buddy_block_is_clear(block));
+		KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block), (u64)(2 * chunk));
+	}
+
+	gpu_buddy_free_list(&mm, &clear_res, GPU_BUDDY_CLEARED);
+	gpu_buddy_free_list(&mm, &dirty_res, 0);
+	gpu_buddy_free_list(&mm, &barrier, 0);
+	gpu_buddy_fini(&mm);
+}
+
 static struct kunit_case gpu_buddy_tests[] = {
 	KUNIT_CASE(gpu_test_buddy_alloc_limit),
 	KUNIT_CASE(gpu_test_buddy_alloc_optimistic),
@@ -1615,6 +1698,7 @@ static struct kunit_case gpu_buddy_tests[] = {
 	KUNIT_CASE(gpu_test_buddy_alloc_clear),
 	KUNIT_CASE(gpu_test_buddy_alloc_range),
 	KUNIT_CASE(gpu_test_buddy_alloc_range_bias),
+	KUNIT_CASE(gpu_test_buddy_alloc_range_clear_guard),
 	KUNIT_CASE_SLOW(gpu_test_buddy_fragmentation_performance),
 	KUNIT_CASE_SLOW(gpu_test_buddy_dirty_tracker_performance),
 	KUNIT_CASE(gpu_test_buddy_alloc_exceeds_max_order),

base-commit: 6f7098738fff3ec7393f924343188cb8e6ebc5d2
-- 
2.43.0

Re: [PATCH v3] gpu/buddy: restore two-pass clear/dirty guard for range-biased allocation

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] gpu/buddy: leaked split on range-straddling mixed block in __alloc_range_bias()
--

commit caf65a7be15ef66d98faecfc731749477d23b658
Author: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>

gpu/buddy: restore two-pass clear/dirty guard for range-biased allocation

This commit introduces a two-pass clear/dirty eligibility check in
__alloc_range_bias() via block_incompatible() so that range-biased
allocations avoid splitting opposite-class extents during the initial strict
pass before falling back when -ENOSPC is returned. It also accepts mixed
blocks at the requested order as-is and adds a KUnit regression test for
range-biased clear/dirty separation.

> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> index 28cff97d57dc8..f2914f919b04a 100644
> --- a/drivers/gpu/buddy.c
> +++ b/drivers/gpu/buddy.c
> @@ -1240,11 +1240,23 @@ static void __gpu_buddy_undo_splits(struct gpu_buddy *mm,
>  	}
>  }
>  
> +static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags)
> +{
> +	bool needs_clear = flags & GPU_BUDDY_CLEAR_ALLOCATION;
> +
> +	if (!gpu_buddy_block_is_free(block))
> +		return false;
> +
> +	return needs_clear ? !block->has_clear :
> +			     gpu_buddy_block_is_clear(block);
> +}
> +
>  static struct gpu_buddy_block *
>  __alloc_range_bias(struct gpu_buddy *mm,
>  		   u64 start, u64 end,
>  		   unsigned int order,
> -		   unsigned long flags)
> +		   unsigned long flags,
> +		   bool fallback)
>  {

[ ... ]

> @@ -1298,6 +1308,9 @@ __alloc_range_bias(struct gpu_buddy *mm,
>  				continue;
>  		}
>  
> +		if (!fallback && block_incompatible(block, flags))
> +			continue;
> +
>  		if (contains(start, end, block_start, block_end) &&
>  		    order == gpu_buddy_block_order(block)) {
>  			/*
> @@ -1315,38 +1328,8 @@ __alloc_range_bias(struct gpu_buddy *mm,
>  				goto err_undo;
>  		}
>  
> -		/*
> -		 * Top-down is a strict address-placement policy, so when it is
> -		 * requested we ignore clear steering and simply descend the
> -		 * right (higher-address) child first. Only a non-top-down clear
> -		 * request biases the descent towards clear/has_clear subtrees.
> -		 */
> -		if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
> -		    !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) {
> -			struct gpu_buddy_block *prefer;
> -
> -			if (gpu_buddy_block_is_clear(block->right))
> -				prefer = block->right;
> -			else if (gpu_buddy_block_is_clear(block->left))
> -				prefer = block->left;
> -			else if (block->right->has_clear)
> -				prefer = block->right;
> -			else if (block->left->has_clear)
> -				prefer = block->left;
> -			else
> -				prefer = block->right;
> -
> -			if (prefer == block->right) {
> -				list_add(&block->left->tmp_link, &dfs);
> -				list_add(&block->right->tmp_link, &dfs);
> -			} else {
> -				list_add(&block->right->tmp_link, &dfs);
> -				list_add(&block->left->tmp_link, &dfs);
> -			}
> -		} else {
> -			list_add(&block->left->tmp_link, &dfs);
> -			list_add(&block->right->tmp_link, &dfs);
> -		}
> +		list_add(&block->left->tmp_link, &dfs);
> +		list_add(&block->right->tmp_link, &dfs);
>  	} while (1);

[Severity: High]
Can __alloc_range_bias() still leave an unmerged split block (and leak the
child gpu_buddy_block allocations on teardown) when a free mixed block of
order greater than the target order straddles the start or end boundary of
the requested [start, end) range?

In __alloc_range_bias(), block_incompatible() returns false for any free
mixed block because block->has_clear is true and gpu_buddy_block_is_clear()
is false across the whole block span. Dropping unsplit_block() relies on the
assumption that splitting a mixed block during the strict pass
(fallback == false) will always find at least one compatible descendant at
the target order.

However, when a free mixed block with order > target order only partially
overlaps [start, end), it passes the adjusted range check in
__alloc_range_bias():

	if (block_start < start || block_end > end) {
		u64 adjusted_start = max(block_start, start);
		u64 adjusted_end = min(block_end, end);

		if (round_down(adjusted_end + 1, req_size) <=
		    round_up(adjusted_start, req_size))
			continue;
	}

	if (!fallback && block_incompatible(block, flags))
		continue;

	...

	if (!gpu_buddy_block_is_split(block)) {
		err = split_block(mm, block);
		if (unlikely(err))
			goto err_undo;
	}

If the compatible portion that made the parent mixed lies in the child
outside [start, end) while the child inside [start, end) is purely
opposite-class (for example, clear when a dirty allocation is requested),
split_block() splits the parent into two free children, the out-of-range
child is skipped by the range check, and the in-range child is rejected by
block_incompatible().

When the allocation is then satisfied elsewhere in the tree, the split parent
is left in GPU_BUDDY_SPLIT state with both children simultaneously in
GPU_BUDDY_FREE state:

1. If the mixed block straddles end (e.g. a 4 MiB allocator with 1 MiB
   chunks where [0, 1M) is dirty free, [1M, 2M) is allocated, and [2M, 4M)
   is a coalesced free mixed block with [2M, 3M) clear and [3M, 4M) dirty),
   a 1 MiB dirty range allocation over [0, 3M) visits [2M, 4M) first, splits
   it, rejects [3M, 4M) as out of range and [2M, 3M) via
   block_incompatible(), and then succeeds at [0, 1M) during the strict pass
   without running the fallback pass.

2. If the mixed block straddles start (e.g. [0, 2M) is a free mixed block
   with [0, 1M) dirty and [1M, 2M) clear, and [2M, 4M) is clear free), a
   1 MiB dirty range allocation over [1M, 4M) skips [2M, 4M) in the strict
   pass, splits [0, 2M) and rejects both halves, fails the strict pass with
   -ENOSPC, and then satisfies the request from [3M, 4M) in the fallback
   pass before visiting [0, 2M).

Because neither child of the abandoned split node is allocated, freeing
other blocks never coalesces across the GPU_BUDDY_SPLIT parent in
__gpu_buddy_free(), leaving the buddy tree permanently fragmented and
triggering gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i])) in
gpu_buddy_fini() while leaking the descendant gpu_buddy_block structures in
slab_blocks.

Should __alloc_range_bias() still undo rejected splits when descending
blocks that are not fully contained within [start, end), or check compatibility
against the in-range portion?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261103125617.2480786-1-arunpravin.paneerselvam@amd.com?part=1