From: Arunpravin Paneer Selvam <[email protected]>
A range + contiguous allocation (e.g. a scanout FB confined to the
CPU-visible VRAM aperture) rounds its size up to a power of two and
requires a naturally aligned free block of that size; on a fragmented
aperture no such aligned block may exist even though enough contiguous
space is free, so the allocation fails with -ENOSPC.
The non-range contiguous path already recovers from this via
__alloc_contig_try_harder(), which stitches an exact-size span from
smaller adjacent blocks, but that fallback was unreachable once
GPU_BUDDY_RANGE_ALLOCATION was set. Extend __alloc_contig_try_harder()
with a [range_start, range_end) window and route the range + contiguous
case through it: each candidate placement is confined to the window and
aligned to min_block_size. Non-range callers pass [0, mm->size), where
the guards are no-ops, so the existing behaviour is unchanged. A KUnit
test covers the fragmentation pattern.
v5: make the windowed try-harder search complete so it no longer returns
a spurious -ENOSPC while a valid placement exists:
- Descend through the lower orders instead of bailing out at the
requested order, so smaller free blocks are still considered.
- Clamp an out-of-range full fill back to range_end so the leftward
shift re-seats the span inside the window (reported by Sashiko).
- Add a final sweep of every min_block_size-aligned offset in the
window, catching a placement inside a larger coalesced block
(reported by Sashiko).
v4:
- As Matthew pointed out, the Fixes: tag did not fit this patch: it adds
try-harder range support, a new safety-net feature rather than the fix.
The root cause is __alloc_range_bias() losing its clear/dirty guard.
v3:
- Confine the try_harder scan to [range_start, range_end) to avoid
speculative out-of-window alloc/free.
v2:
- Drop the split-undo patch; the range-bias search always descends to
an exact-order block or fails the split (already handled), so the
extra undo was redundant. (Matthew)
Assisted-by: LLM
Cc: Matthew Auld <[email protected]>
Cc: Christian König <[email protected]>
Signed-off-by: Arunpravin Paneer Selvam <[email protected]>
---
drivers/gpu/buddy.c | 131 ++++++++++++-------
drivers/gpu/tests/gpu_buddy_test.c | 201 ++++++++++++++++++++++++++++-
2 files changed, 283 insertions(+), 49 deletions(-)
diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index 91935c71c525..ffa63ecaf235 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -1682,43 +1682,32 @@ static int __gpu_buddy_alloc_range(struct gpu_buddy *mm,
blocks, total_allocated_on_err);
}
-static int __alloc_contig_aligned_retry(struct gpu_buddy *mm,
- u64 unaligned_offset,
- u64 size,
- u64 min_block_size,
- unsigned long flags,
- struct list_head *blocks)
-{
- u64 aligned_offset = round_down(unaligned_offset, min_block_size);
-
- return __gpu_buddy_alloc_range(mm, aligned_offset, size, flags,
- NULL, blocks);
-}
-
static int __alloc_contig_try_harder(struct gpu_buddy *mm,
+ u64 range_start, u64 range_end,
u64 size,
u64 min_block_size,
unsigned long flags,
struct list_head *blocks)
{
- u64 rhs_offset, lhs_offset, filled;
+ u64 rhs_offset, lhs_offset, filled, aligned;
struct gpu_buddy_block *block;
+ unsigned int min_order, order;
struct rb_root *root;
struct rb_node *iter;
unsigned long pages;
- unsigned int order;
u64 modify_size;
int err;
+ min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
+
modify_size = rounddown_pow_of_two(size);
pages = modify_size >> ilog2(mm->chunk_size);
order = fls(pages) - 1;
- if (order == 0)
- return -ENOSPC;
+retry_order:
root = &mm->free_tree[order];
if (RB_EMPTY_ROOT(root))
- return -ENOSPC;
+ goto next_order;
iter = rb_last(root);
while (iter) {
@@ -1726,25 +1715,42 @@ static int __alloc_contig_try_harder(struct gpu_buddy
*mm,
rhs_offset = gpu_buddy_block_offset(block);
+ if (rhs_offset >= range_end) {
+ iter = rb_prev(iter);
+ continue;
+ }
+ if (rhs_offset < range_start)
+ break;
+
/* Allocate blocks traversing RHS */
err = __gpu_buddy_alloc_range(mm, rhs_offset, size,
flags, &filled, blocks);
if (err && err != -ENOSPC)
return err;
- if (!err && IS_ALIGNED(rhs_offset, min_block_size))
+ if (!err && rhs_offset + size > range_end) {
+ gpu_buddy_free_list_internal(mm, blocks);
+ filled = range_end - rhs_offset;
+ err = -ENOSPC;
+ }
+ if (!err && IS_ALIGNED(rhs_offset, min_block_size) &&
+ rhs_offset >= range_start && rhs_offset + size <= range_end)
return 0;
+
if (!err) {
/* Allocate the unaligned RHS offset using round_down */
gpu_buddy_free_list_internal(mm, blocks);
- err = __alloc_contig_aligned_retry(mm, rhs_offset,
- size,
- min_block_size,
- flags, blocks);
- if (!err)
- return 0;
- if (err != -ENOSPC) {
- gpu_buddy_free_list_internal(mm, blocks);
- return err;
+
+ aligned = round_down(rhs_offset, min_block_size);
+ if (aligned >= range_start &&
+ aligned + size <= range_end) {
+ err = __gpu_buddy_alloc_range(mm, aligned, size,
+ flags, NULL,
blocks);
+ if (!err)
+ return 0;
+ if (err != -ENOSPC) {
+ gpu_buddy_free_list_internal(mm,
blocks);
+ return err;
+ }
}
goto next;
}
@@ -1756,21 +1762,44 @@ static int __alloc_contig_try_harder(struct gpu_buddy
*mm,
/* Allocate the unaligned LHS offset using round_down */
gpu_buddy_free_list_internal(mm, blocks);
- err = __alloc_contig_aligned_retry(mm, lhs_offset,
- size,
- min_block_size,
- flags, blocks);
- if (!err)
- return 0;
- if (err != -ENOSPC) {
- gpu_buddy_free_list_internal(mm, blocks);
- return err;
+
+ aligned = round_down(lhs_offset, min_block_size);
+ if (aligned >= range_start && aligned + size <= range_end) {
+ err = __gpu_buddy_alloc_range(mm, aligned, size,
+ flags, NULL, blocks);
+ if (!err)
+ return 0;
+ if (err != -ENOSPC) {
+ gpu_buddy_free_list_internal(mm, blocks);
+ return err;
+ }
}
next:
gpu_buddy_free_list_internal(mm, blocks);
iter = rb_prev(iter);
}
+next_order:
+ if (order > min_order) {
+ order--;
+ goto retry_order;
+ }
+
+ /*
+ * Last resort: sweep every aligned offset in the window and let
+ * __gpu_buddy_alloc_range() carve the span from a larger covering
block.
+ */
+ for (aligned = round_up(range_start, min_block_size);
+ aligned + size <= range_end;
+ aligned += min_block_size) {
+ err = __gpu_buddy_alloc_range(mm, aligned, size, flags, NULL,
blocks);
+ if (!err)
+ return 0;
+ gpu_buddy_free_list_internal(mm, blocks);
+ if (err != -ENOSPC)
+ return err;
+ }
+
return -ENOSPC;
}
@@ -2018,11 +2047,18 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
if (order > mm->max_order || size > mm->size) {
- if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) &&
- !(flags & GPU_BUDDY_RANGE_ALLOCATION))
- return __alloc_contig_try_harder(mm, original_size,
+ if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) {
+ u64 range_start, range_end;
+
+ range_start = (flags & GPU_BUDDY_RANGE_ALLOCATION) ?
start : 0;
+ range_end = (flags & GPU_BUDDY_RANGE_ALLOCATION) ? end
: mm->size;
+
+ return __alloc_contig_try_harder(mm, range_start,
+ range_end,
+ original_size,
original_min_size,
flags, blocks);
+ }
return -EINVAL;
}
@@ -2055,9 +2091,14 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
* Try contiguous block allocation through
* try harder method.
*/
- if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION &&
- !(flags & GPU_BUDDY_RANGE_ALLOCATION)) {
- err = __alloc_contig_try_harder(mm,
+ if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) {
+ u64 range_start, range_end;
+
+ range_start = (flags &
GPU_BUDDY_RANGE_ALLOCATION) ? start : 0;
+ range_end = (flags &
GPU_BUDDY_RANGE_ALLOCATION) ? end : mm->size;
+
+ err = __alloc_contig_try_harder(mm, range_start,
+ range_end,
original_size,
original_min_size,
flags,
@@ -2065,9 +2106,9 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
if (!err)
return 0;
if (err != -ENOSPC)
- return err;
- goto err_free;
+ goto err_free;
}
+
err = -ENOSPC;
goto err_free;
} while (1);
diff --git a/drivers/gpu/tests/gpu_buddy_test.c
b/drivers/gpu/tests/gpu_buddy_test.c
index 3eaa261571bf..504910559e6c 100644
--- a/drivers/gpu/tests/gpu_buddy_test.c
+++ b/drivers/gpu/tests/gpu_buddy_test.c
@@ -1251,6 +1251,130 @@ static void gpu_test_buddy_alloc_contiguous(struct
kunit *test)
gpu_buddy_fini(&mm);
}
+/*
+ * Issue a range-restricted contiguous request and assert that it returns an
+ * exact-size, contiguous span confined to [range_start, range_end). Frees the
+ * allocation before returning; the caller owns mm init/fini and any pins.
+ */
+static void check_contig_range_alloc(struct kunit *test, struct gpu_buddy *mm,
+ u64 range_start, u64 range_end,
+ u64 size, u64 min, const char *shape)
+{
+ struct gpu_buddy_block *block, *prev;
+ LIST_HEAD(allocated);
+ u64 total;
+
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(mm, range_start,
range_end,
+ size, min, &allocated,
+
GPU_BUDDY_CONTIGUOUS_ALLOCATION |
+
GPU_BUDDY_RANGE_ALLOCATION),
+ "%s: range-restricted contiguous alloc failed\n",
+ shape);
+
+ total = 0;
+ prev = NULL;
+ list_for_each_entry(block, &allocated, link) {
+ u64 offset = gpu_buddy_block_offset(block);
+ u64 bsize = gpu_buddy_block_size(mm, block);
+
+ KUNIT_EXPECT_TRUE_MSG(test, offset >= range_start &&
+ offset + bsize <= range_end,
+ "%s: block [%llx, %llx) outside range\n",
+ shape, offset, offset + bsize);
+ if (prev)
+ KUNIT_EXPECT_EQ_MSG(test,
+ gpu_buddy_block_offset(prev) +
+ gpu_buddy_block_size(mm, prev),
+ offset,
+ "%s: block at %llx not
contiguous\n",
+ shape, offset);
+ prev = block;
+ total += bsize;
+ }
+ KUNIT_EXPECT_EQ_MSG(test, total, size, "%s: wrong total size\n", shape);
+
+ gpu_buddy_free_list(mm, &allocated, 0);
+}
+
+static void gpu_test_buddy_alloc_range_contiguous(struct kunit *test)
+{
+ const unsigned long ps = SZ_4K;
+ struct gpu_buddy mm;
+ LIST_HEAD(pin_lo);
+ LIST_HEAD(pin_hi);
+ LIST_HEAD(barrier);
+
+ /*
+ * Feature: confine a 12K contiguous request (rounded up to 16K) to
+ * [0, 32K), which splits into two naturally aligned 16K slots. Pin the
+ * first page of each ([0, 4K) and [16K, 20K)) so neither slot can
+ * satisfy the rounded-up 16K alloc, yet a contiguous but 16K-unaligned
+ * 12K hole remains at offset 4K. The fallback must stitch that hole
+ * instead of returning -ENOSPC.
+ */
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, 16 * ps, ps),
+ "buddy_init failed\n");
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(&mm, 0, ps, ps, ps,
+ &pin_lo, 0),
+ "failed to pin low page\n");
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(&mm, 4 * ps, 5 * ps, ps,
+ ps, &pin_hi, 0),
+ "failed to pin high page\n");
+ check_contig_range_alloc(test, &mm, 0, 8 * ps, 3 * ps, ps, "feature");
+ gpu_buddy_free_list(&mm, &pin_lo, 0);
+ gpu_buddy_free_list(&mm, &pin_hi, 0);
+ gpu_buddy_fini(&mm);
+
+ /*
+ * Higher-order: an empty arena coalesces all free
+ * space into one high-order block, so the anchored search finds no
+ * block at or below the derived order inside [4K, 20K). The allocator
+ * must still carve the 12K span out of the larger block.
+ */
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, 8 * ps, ps),
+ "buddy_init failed\n");
+ check_contig_range_alloc(test, &mm, ps, 5 * ps, 3 * ps, ps,
+ "higher_order");
+ gpu_buddy_fini(&mm);
+
+ /*
+ * Beyond range_end: pin [8K, 16K) and leave
+ * [16K, 32K) free, so the only fit inside [12K, 28K) is [16K, 28K) with
+ * a free page spilling past range_end. The tail coalesces above the
+ * derived order, so the request must still land on [16K, 28K).
+ */
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, 8 * ps, ps),
+ "buddy_init failed\n");
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(&mm, 2 * ps, 4 * ps,
+ 2 * ps, ps, &barrier, 0),
+ "failed to pin barrier\n");
+ check_contig_range_alloc(test, &mm, 3 * ps, 7 * ps, 3 * ps, ps,
+ "beyond_end");
+ gpu_buddy_free_list(&mm, &barrier, 0);
+ gpu_buddy_fini(&mm);
+
+ /*
+ * Left shift: pin [28K, 32K) and leave [0, 28K) free. For a 12K request
+ * in [4K, 20K) the anchored search fills rightward to [16K, 28K), a
full
+ * fill ending past range_end. The overshoot must be clamped so the
+ * leftward shift finds the valid placement [8K, 20K).
+ */
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, 8 * ps, ps),
+ "buddy_init failed\n");
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(&mm, 7 * ps, 8 * ps,
+ ps, ps, &barrier, 0),
+ "failed to pin barrier\n");
+ check_contig_range_alloc(test, &mm, ps, 5 * ps, 3 * ps, ps,
+ "left_shift");
+ gpu_buddy_free_list(&mm, &barrier, 0);
+ gpu_buddy_fini(&mm);
+}
+
static void gpu_test_buddy_alloc_pathological(struct kunit *test)
{
u64 mm_size, size, start = 0;
@@ -1534,10 +1658,13 @@ static void
gpu_test_buddy_alloc_exceeds_max_order(struct kunit *test)
GPU_BUDDY_RANGE_ALLOCATION);
KUNIT_EXPECT_EQ(test, err, -EINVAL);
- /* CONTIGUOUS + RANGE should return -EINVAL (no try_harder for RANGE) */
- err = gpu_buddy_alloc_blocks(&mm, 0, mm_size, size, SZ_4K, &blocks,
- GPU_BUDDY_CONTIGUOUS_ALLOCATION |
GPU_BUDDY_RANGE_ALLOCATION);
- KUNIT_EXPECT_EQ(test, err, -EINVAL);
+ /* CONTIGUOUS + RANGE should succeed via the range-aware try_harder */
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size,
size,
+ SZ_4K, &blocks,
+
GPU_BUDDY_CONTIGUOUS_ALLOCATION |
+
GPU_BUDDY_RANGE_ALLOCATION),
+ "range contiguous alloc hit an error
size=%llu\n", size);
+ gpu_buddy_free_list(&mm, &blocks, 0);
gpu_buddy_fini(&mm);
}
@@ -1586,6 +1713,70 @@ static void gpu_test_buddy_addr_to_block(struct kunit
*test)
gpu_buddy_fini(&mm);
}
+static void gpu_test_buddy_alloc_contiguous_descent(struct kunit *test)
+{
+ const unsigned long ps = SZ_4K, mm_size = 16 * ps;
+ struct gpu_buddy_block *block, *prev;
+ LIST_HEAD(allocated);
+ struct gpu_buddy mm;
+ LIST_HEAD(pin_lo);
+ LIST_HEAD(pin_hi);
+ u64 total;
+
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, ps),
+ "buddy_init failed\n");
+
+ /*
+ * Pin [0, 16K) and [48K, 64K). The remaining [16K, 48K) is free as two
+ * adjacent 16K halves under different parents; being un-mergeable
+ * buddies they never coalesce, so free_tree[3] (32K) stays empty. A
+ * contiguous 32K request with min_block_size 4K therefore has no 32K
+ * anchor and must descend to order 2 and stitch [16K, 48K).
+ */
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(&mm, 0, 4 * ps, 4 * ps,
+ ps, &pin_lo, 0),
+ "failed to pin low block\n");
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(&mm, 12 * ps, 16 * ps,
+ 4 * ps, ps, &pin_hi, 0),
+ "failed to pin high block\n");
+
+ KUNIT_ASSERT_FALSE_MSG(test,
+ gpu_buddy_alloc_blocks(&mm, 0, mm_size, 8 * ps,
+ ps, &allocated,
+
GPU_BUDDY_CONTIGUOUS_ALLOCATION),
+ "contiguous alloc failed to descend\n");
+
+ /* The result must be exactly 8*ps, contiguous, within [16K, 48K). */
+ total = 0;
+ prev = NULL;
+ list_for_each_entry(block, &allocated, link) {
+ u64 offset = gpu_buddy_block_offset(block);
+ u64 bsize = gpu_buddy_block_size(&mm, block);
+
+ KUNIT_EXPECT_TRUE_MSG(test, offset >= 4 * ps &&
+ offset + bsize <= 12 * ps,
+ "block [%llx, %llx) outside stitched
span\n",
+ offset, offset + bsize);
+ if (prev)
+ KUNIT_EXPECT_EQ_MSG(test,
+ gpu_buddy_block_offset(prev) +
+ gpu_buddy_block_size(&mm, prev),
+ offset,
+ "block at %llx not contiguous\n",
+ offset);
+ prev = block;
+ total += bsize;
+ }
+ KUNIT_EXPECT_EQ(test, total, 8 * ps);
+
+ gpu_buddy_free_list(&mm, &allocated, 0);
+ gpu_buddy_free_list(&mm, &pin_lo, 0);
+ gpu_buddy_free_list(&mm, &pin_hi, 0);
+ gpu_buddy_fini(&mm);
+}
+
static int gpu_buddy_suite_init(struct kunit_suite *suite)
{
while (!random_seed)
@@ -1667,6 +1858,8 @@ static struct kunit_case gpu_buddy_tests[] = {
KUNIT_CASE(gpu_test_buddy_alloc_pessimistic),
KUNIT_CASE(gpu_test_buddy_alloc_pathological),
KUNIT_CASE(gpu_test_buddy_alloc_contiguous),
+ KUNIT_CASE(gpu_test_buddy_alloc_range_contiguous),
+ KUNIT_CASE(gpu_test_buddy_alloc_contiguous_descent),
KUNIT_CASE(gpu_test_buddy_alloc_clear),
KUNIT_CASE(gpu_test_buddy_alloc_range),
KUNIT_CASE(gpu_test_buddy_alloc_range_bias),
--
2.43.0
