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

[Arunpravin Paneer Selvam <arunpravin.paneerselvam@amd.com>]

Hi Matthew,

Both Sashiko findings on v4 are intentional - no code change:

1. Strict pass skips straddling free blocks: This is intended. If the 
strict pass split a free block that crosses the range edge, part of it 
would fall outside the range and get rejected, leaving the split behind 
- and the strict pass has no way to merge it back. That was the v3 leak, 
so we now skip such blocks instead of splitting them.

The clear/dirty check ( block_incompatible() ) only looks at blocks that 
fit entirely inside the range, so it keeps clear and dirty apart 
correctly whenever such blocks exist. It is skipped in just one case: 
when the only option is a single big free block crossing the range edge. 
That happens when the area is still unused - nothing is allocated in it 
yet - so there are no existing clear or dirty allocations there that 
could get interleaved or broken up. The guard has nothing to protect in 
that case, so skipping it does no harm. At worst the fallback pass picks 
a block of the other class and it has to be cleared again - a re-clear 
cost, not fragmentation.

2. Dropped clear-child preference for mixed blocks: On purpose. Carrying 
that preference down through mixed blocks splits them to carve out a 
same-class leaf, which interleaves allocated clear and dirty blocks and 
regresses range allocations to  -ENOSPC . Taking the mixed child whole 
strands nothing, and the wholly-clear sibling stays free and usable, so 
the only cost is a possible re-clear.



Why we don't steer  has_clear  splits in mixed blocks:
Old dual-tree kept clear and dirty in separate pools (same-class-only 
merge), so every split came from a pure pool and never stranded the 
opposite class. The new design merges across classes into large MIXED 
blocks, so class-aware steering had to keep splitting those big blocks 
to carve out a same-class leaf - breaking contiguous space and leaving 
allocations of the two classes mixed together, so freed blocks can't 
reform a large run →  -ENOSPC . v4 drops steering: it still splits a 
mixed block that's larger than the request (for size only, spatially, no 
class bias) but takes the block whole once it reaches the requested 
order instead of splitting further to isolate a same-class leaf. Using 
only the block_incompatible  guard - which accepts or rejects a whole 
block by class and never traverses inside a mixed block to pick a 
clear/dirty child - it keeps large blocks intact and avoids the 
interleaving.

Could you please check and review the v4.

Thanks,
Arun.

On 11/4/2026 12:58 PM, Arunpravin Paneer Selvam wrote:
> 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.
>
> v4: a higher-order free mixed block straddling the range edge was split in
>      the strict pass then abandoned, leaving both children free under a split
>      parent that never coalesces, tripping gpu_buddy_fini()'s free-root assert
>      and leaking the children (reported by Sashiko). Fix: in the strict pass
>      don't split a free block that only partially overlaps the range; the
>      fallback pass consumes it (either class accepted).
>
> 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                | 83 ++++++++++++++++-------------
>   drivers/gpu/tests/gpu_buddy_test.c | 84 ++++++++++++++++++++++++++++++
>   2 files changed, 130 insertions(+), 37 deletions(-)
>
> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> index 28cff97d57dc..d9749cbaf05d 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);
> @@ -1296,8 +1306,19 @@ __alloc_range_bias(struct gpu_buddy *mm,
>   			if (round_down(adjusted_end + 1, req_size) <=
>   			    round_up(adjusted_start, req_size))
>   				continue;
> +
> +			/*
> +			 * Strict pass: don't split a partially-overlapping free
> +			 * block; rejecting its child would strand the split. Let
> +			 * the fallback pass consume it (either class accepted).
> +			 */
> +			if (!fallback && gpu_buddy_block_is_free(block))
> +				continue;
>   		}
>   
> +		if (!fallback && block_incompatible(block, flags))
> +			continue;
> +
>   		if (contains(start, end, block_start, block_end) &&
>   		    order == gpu_buddy_block_order(block)) {
>   			/*
> @@ -1315,38 +1336,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 +1352,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 +1933,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: 49f40f15d20f5b4073d517da7efbcea079f1b9e3