* [PATCH v4 0/3] gpu/buddy: find range-biased blocks in the free trees
@ 2026-11-18 20:16 William Palacek
2026-11-18 20:16 ` [PATCH v4 1/3] " William Palacek
` (2 more replies)
0 siblings, 3 replies; 4+ messages in thread
From: William Palacek @ 2026-11-18 20:16 UTC (permalink / raw)
To: dri-devel
Cc: intel-xe, Matthew Auld, Arunpravin Paneer Selvam, Sanjay Yadav,
Joel Fernandes, Christian König, linux-kernel,
William Palacek
In a range-restricted allocation, the strict pass of
__alloc_range_bias() still visits every free block of the other class
in the range: a dirty request among many free cleared blocks steps
through each of them. amdgpu restricts every VRAM allocation to its
memory partition under NPS2/NPS4, so it takes this path for every KFD
VRAM allocation there.
Patch 1 replaces the walk with a lookup in the offset-sorted free trees,
on top of Arun's range guard code. Patch 2 drops subtree_max_free_order,
which nothing reads after patch 1. Patch 3 adds tests for an inverted
range and for the NPS4 fill pattern.
v3: https://patchwork.freedesktop.org/series/178108/#rev2
v2: https://patchwork.freedesktop.org/series/178108/#rev1
v1: https://patchwork.freedesktop.org/series/176957/
William Palacek (3):
gpu/buddy: find range-biased blocks in the free trees
gpu/buddy: drop subtree_max_free_order
gpu/tests/buddy: add range-biased allocation tests
drivers/gpu/buddy.c | 334 +++++++++++++++++++----------
drivers/gpu/tests/gpu_buddy_test.c | 67 ++++++
include/linux/gpu_buddy.h | 7 -
3 files changed, 291 insertions(+), 117 deletions(-)
--
2.43.0
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH v4 1/3] gpu/buddy: find range-biased blocks in the free trees
2026-11-18 20:16 [PATCH v4 0/3] gpu/buddy: find range-biased blocks in the free trees William Palacek
@ 2026-11-18 20:16 ` William Palacek
2026-11-18 20:17 ` [PATCH v4 2/3] gpu/buddy: drop subtree_max_free_order William Palacek
2026-11-18 20:17 ` [PATCH v4 3/3] gpu/tests/buddy: add range-biased allocation tests William Palacek
2 siblings, 0 replies; 4+ messages in thread
From: William Palacek @ 2026-11-18 20:16 UTC (permalink / raw)
To: dri-devel
Cc: intel-xe, Matthew Auld, Arunpravin Paneer Selvam, Sanjay Yadav,
Joel Fernandes, Christian König, linux-kernel,
William Palacek
__alloc_range_bias() walks the block tree from the roots. Subtrees
without a free block of the requested order or larger are skipped, but
the strict pass still descends to every free block of the other class
in the range: a dirty request in a range holding many free cleared
blocks visits each of them, and their split ancestors, before it finds
dirty space. amdgpu takes this path for every VRAM allocation when
memory is partitioned (NPS2/NPS4), as each BO is restricted to its
partition's range.
The free trees are sorted by offset, so find the block there instead.
For each order from the requested one up, look up the highest free
block below the range end, step down the tree to the highest one that
can hold the request, and split the highest of them down to the
requested order. The two passes keep the clear/dirty guard: the strict
pass only takes blocks wholly inside the range whose class suits the
request, the fallback pass takes either class and may split a block
straddling the range edge. A clear request without
GPU_BUDDY_TOPDOWN_ALLOCATION first takes the highest clear block in the
range, using subtree_block_state to skip subtrees without one; above the
requested order only wholly-clear blocks are split for it. The walk is
gone.
With 8192 free cleared 64 KiB blocks interleaved with allocated ones in
the range, 4096 dirty range allocations take 402 to 407 ms before and
97 to 145 ms after (KUnit, UML, two runs).
Cc: Matthew Auld <matthew.auld@intel.com>
Cc: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
Cc: Sanjay Yadav <sanjay.kumar.yadav@intel.com>
Signed-off-by: William Palacek <William.Palacek@amd.com>
---
Notes:
v4:
- rebased onto Sanjay's "gpu/buddy: Prune exhausted subtrees in
range-biased allocation" (5880b69a0b76); patch 2 drops
subtree_max_free_order, which nothing reads after this patch
- based on Arun's range guard code: a clear request without
GPU_BUDDY_TOPDOWN_ALLOCATION first takes the highest clear block in
the range (Arun)
- that search stops at the first match instead of scoring every clear
block, so rbtree_pick_best_class() goes away (Arun)
- drop the subtree_has_dirty augment; dirty requests step down past
free clear blocks instead (Arun)
- return -ENOSPC for start >= end instead of looking up outside the
range (sashiko)
- the strict pass always runs, as in Arun's guard code; the one-class
shortcut from cb0a63f0c96e is dropped (Arun)
v3:
- rebased onto the merged clear/dirty guard (cb0a63f0c96e) (Arun)
- take Arun's free-tree lookup and drop the walk instead of narrowing it
(Arun)
- strict pass O(log n) for both classes: subtree_block_state for clear
requests, new subtree_has_dirty augment for dirty ones
- placement now matches the walk exactly, including the guard
v2:
- rebased onto drm-misc-next (single free tree) (Arun)
- take the highest contained block, keeping top-down placement (Arun)
drivers/gpu/buddy.c | 295 +++++++++++++++++++++++++++++++++-----------
1 file changed, 220 insertions(+), 75 deletions(-)
diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index a1e9f5ebe05a..26af5428ff76 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -628,6 +628,26 @@ rbtree_last_free_block(struct rb_root *root)
return rbtree_get_free_block(rb_last(root));
}
+/* Return the highest free block with lo <= offset <= hi. */
+static struct gpu_buddy_block *
+rbtree_last_free_block_in(struct rb_root *root, u64 lo, u64 hi)
+{
+ struct gpu_buddy_block *block, *last = NULL;
+ struct rb_node *node = root->rb_node;
+
+ while (node) {
+ block = rbtree_get_free_block(node);
+ if (gpu_buddy_block_offset(block) > hi) {
+ node = node->rb_left;
+ } else {
+ last = block;
+ node = node->rb_right;
+ }
+ }
+
+ return last && gpu_buddy_block_offset(last) >= lo ? last : NULL;
+}
+
static struct gpu_buddy_block *
rbtree_last_clear_free_block(struct rb_root *root,
enum gpu_block_state min_block_state)
@@ -666,6 +686,51 @@ rbtree_last_clear_free_block(struct rb_root *root,
return block;
}
+static struct gpu_buddy_block *
+rbtree_range_best_block(struct rb_root *root, u64 lo, u64 hi,
+ enum gpu_block_state min_state)
+{
+ struct rb_node *node = root->rb_node;
+ struct gpu_buddy_block *best = NULL;
+ struct rb_node *prev = NULL;
+
+ while (node) {
+ struct gpu_buddy_block *block = rbtree_get_free_block(node);
+ bool pruned = block->subtree_block_state < min_state;
+ u64 off = gpu_buddy_block_offset(block);
+ bool desc_right = !pruned && off <= hi;
+ bool desc_left = !pruned && off >= lo;
+ struct rb_node *next;
+
+ if (prev == rb_parent(node) && desc_right && node->rb_right) {
+ /* First visit: higher offsets first. */
+ next = node->rb_right;
+ } else if (prev && prev == node->rb_left) {
+ next = rb_parent(node);
+ } else {
+ /* Right subtree done: score this node, then go left. */
+ if (!pruned && off >= lo && off <= hi &&
+ gpu_block_cached_state(block) >= min_state) {
+ if (gpu_block_cached_state(block) == GPU_BLOCK_CLEAR)
+ return block;
+ /* Highest mixed block; only a clear one beats it. */
+ best = block;
+ min_state = GPU_BLOCK_CLEAR;
+ }
+
+ if (desc_left && node->rb_left)
+ next = node->rb_left;
+ else
+ next = rb_parent(node);
+ }
+
+ prev = node;
+ node = next;
+ }
+
+ return best;
+}
+
static void rbtree_insert(struct gpu_buddy *mm,
struct gpu_buddy_block *block)
{
@@ -1274,94 +1339,185 @@ static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags
}
static struct gpu_buddy_block *
-__alloc_range_bias(struct gpu_buddy *mm,
- u64 start, u64 end,
- unsigned int order,
- unsigned long flags,
- bool fallback)
+__alloc_range_clear_block(struct gpu_buddy *mm,
+ u64 start, u64 end,
+ unsigned int order,
+ unsigned long flags)
{
- u64 req_size = mm->chunk_size << order;
struct gpu_buddy_block *block;
- LIST_HEAD(dfs);
+ unsigned int tmp;
int err;
- int i;
-
- end = end - 1;
- /*
- * 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.
- */
- for (i = mm->n_roots - 1; i >= 0; --i)
- list_add_tail(&mm->roots[i]->tmp_link, &dfs);
+ /* Only clear, non-top-down requests benefit from class navigation. */
+ if (!(flags & GPU_BUDDY_CLEAR_ALLOCATION) ||
+ (flags & GPU_BUDDY_TOPDOWN_ALLOCATION))
+ return NULL;
- do {
- u64 block_start;
- u64 block_end;
+ for (tmp = order; tmp <= mm->max_order; ++tmp) {
+ enum gpu_block_state min_state;
+ u64 size;
- block = list_first_entry_or_null(&dfs,
- struct gpu_buddy_block,
- tmp_link);
- if (!block)
+ size = mm->chunk_size << tmp;
+ if (size > end - start)
break;
- list_del(&block->tmp_link);
+ /*
+ * At the requested order a clear or mixed block is handed back
+ * whole (no split). At a higher order only a wholly-clear block
+ * is accepted, so splitting it down produces clear children and
+ * never strands a dirty sibling.
+ */
+ min_state = (tmp == order) ? GPU_BLOCK_MIXED : GPU_BLOCK_CLEAR;
+
+ block = rbtree_range_best_block(&mm->free_tree[tmp],
+ start, end - size, min_state);
+ if (block)
+ goto split_down;
+ }
+
+ return NULL;
+
+split_down:
+ while (gpu_buddy_block_order(block) != order) {
+ err = split_block(mm, block);
+ if (unlikely(err))
+ goto err_undo;
+
+ /*
+ * The parent is wholly clear above the requested order, so both
+ * children are clear and fully inside the window; descend the
+ * higher-address child to match the top-down default placement.
+ */
+ block = block->right;
+ }
+
+ return block;
+
+err_undo:
+ __gpu_buddy_undo_splits(mm, block);
+ return ERR_PTR(err);
+}
+
+static struct gpu_buddy_block *
+__alloc_range_block(struct gpu_buddy *mm, struct rb_root *root,
+ u64 start, u64 end, u64 req_size,
+ bool strict, unsigned long flags,
+ u64 *out_offset)
+{
+ struct gpu_buddy_block *last = rbtree_last_free_block_in(root, 0, end - 1);
+ struct rb_node *node;
+
+ /* Seek to the highest-offset block below @end, then walk down. */
+ for (node = last ? &last->rb : NULL; node; node = rb_prev(node)) {
+ u64 block_offset, block_end, low, high, offset;
+ struct gpu_buddy_block *block;
+
+ block = rbtree_get_free_block(node);
+ block_offset = gpu_buddy_block_offset(block);
+ block_end = block_offset + gpu_buddy_block_size(mm, block);
+
+ /* Offsets descend; once below the window nothing else fits. */
+ if (block_end <= start)
+ break;
- if (block->subtree_max_free_order < (int)order)
+ if (strict && (block_offset < start || block_end > end))
+ continue;
+ if (strict && block_incompatible(block, flags))
continue;
- block_start = gpu_buddy_block_offset(block);
- block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
+ low = max(block_offset, start);
+ high = min(block_end, end);
+ if (high < req_size)
+ continue;
- if (!overlaps(start, end, block_start, block_end))
+ offset = round_down(high - req_size, req_size);
+ if (offset < low)
continue;
- if (block_start < start || block_end > end) {
- u64 adjusted_start = max(block_start, start);
- u64 adjusted_end = min(block_end, end);
+ *out_offset = offset;
+ return block;
+ }
- if (round_down(adjusted_end + 1, req_size) <=
- round_up(adjusted_start, req_size))
- continue;
+ return NULL;
+}
- /*
- * 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;
- }
+static struct gpu_buddy_block *
+__alloc_range_freetree(struct gpu_buddy *mm,
+ u64 start, u64 end,
+ unsigned int order,
+ unsigned long flags)
+{
+ u64 req_size = mm->chunk_size << order;
+ struct gpu_buddy_block *preferred_block;
+ u64 max_offset = 0;
+ unsigned int pass;
+ int err;
- if (!fallback && block_incompatible(block, flags))
- continue;
+ if (start >= end)
+ return ERR_PTR(-ENOSPC);
- /* Not pruned at @order, so this block itself is FREE */
- if (contains(start, end, block_start, block_end) &&
- order == gpu_buddy_block_order(block))
- return block;
+ /* Clear, non-top-down: try clear space first, then placement. */
+ if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
+ !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) {
+ preferred_block = __alloc_range_clear_block(mm, start, end,
+ order, flags);
+ if (IS_ERR(preferred_block))
+ return preferred_block;
+ if (preferred_block)
+ return preferred_block;
+ }
- if (!gpu_buddy_block_is_split(block)) {
- err = split_block(mm, block);
- if (unlikely(err))
- goto err_undo;
+ /* Pass 0: strict (contained, class-match); pass 1: fallback (any). */
+ for (pass = 0; pass < 2; pass++) {
+ bool strict = (pass == 0);
+ unsigned int tmp;
+
+ preferred_block = NULL;
+ for (tmp = order; tmp <= mm->max_order; ++tmp) {
+ struct gpu_buddy_block *block;
+ u64 offset;
+
+ block = __alloc_range_block(mm, &mm->free_tree[tmp],
+ start, end,
+ req_size, strict,
+ flags, &offset);
+ if (block &&
+ (!preferred_block || offset > max_offset)) {
+ preferred_block = block;
+ max_offset = offset;
+ }
}
- list_add(&block->left->tmp_link, &dfs);
- list_add(&block->right->tmp_link, &dfs);
- } while (1);
+ if (preferred_block)
+ break;
+ }
- return ERR_PTR(-ENOSPC);
+ if (!preferred_block)
+ return ERR_PTR(-ENOSPC);
-err_undo:
/*
- * We really don't want to leave around a bunch of split blocks, since
- * bigger is better, so make sure we merge everything back before we
- * free the allocated blocks.
+ * Split @preferred_block down to the order-@order block covering
+ * @max_offset.
*/
- __gpu_buddy_undo_splits(mm, block);
+ while (gpu_buddy_block_order(preferred_block) != order) {
+ u64 mid_offset;
+
+ err = split_block(mm, preferred_block);
+ if (unlikely(err))
+ goto err_undo;
+
+ mid_offset = gpu_buddy_block_offset(preferred_block) +
+ (gpu_buddy_block_size(mm, preferred_block) >> 1);
+ if (max_offset >= mid_offset)
+ preferred_block = preferred_block->right;
+ else
+ preferred_block = preferred_block->left;
+ }
+
+ return preferred_block;
+
+err_undo:
+ __gpu_buddy_undo_splits(mm, preferred_block);
return ERR_PTR(err);
}
@@ -1371,18 +1527,7 @@ __gpu_buddy_alloc_range_bias(struct gpu_buddy *mm,
unsigned int order,
unsigned long flags)
{
- struct gpu_buddy_block *block;
- bool fallback;
-
- fallback = !(gpu_buddy_clear_avail(mm) && mm->dirty.total_dirty);
-
- block = __alloc_range_bias(mm, start, end, order,
- flags, fallback);
- if (IS_ERR(block) && !fallback)
- return __alloc_range_bias(mm, start, end, order,
- flags, true);
-
- return block;
+ return __alloc_range_freetree(mm, start, end, order, flags);
}
/* Return the highest-address free block of at least @order. */
--
2.43.0
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH v4 2/3] gpu/buddy: drop subtree_max_free_order
2026-11-18 20:16 [PATCH v4 0/3] gpu/buddy: find range-biased blocks in the free trees William Palacek
2026-11-18 20:16 ` [PATCH v4 1/3] " William Palacek
@ 2026-11-18 20:17 ` William Palacek
2026-11-18 20:17 ` [PATCH v4 3/3] gpu/tests/buddy: add range-biased allocation tests William Palacek
2 siblings, 0 replies; 4+ messages in thread
From: William Palacek @ 2026-11-18 20:17 UTC (permalink / raw)
To: dri-devel
Cc: intel-xe, Matthew Auld, Arunpravin Paneer Selvam, Sanjay Yadav,
Joel Fernandes, Christian König, linux-kernel,
William Palacek
__alloc_range_bias() no longer walks the buddy tree, so nothing reads
subtree_max_free_order. Stop maintaining it on every allocation and
free, and restore the original order in gpu_buddy_block_trim(), where
the block was detached early only to keep that field consistent.
Cc: Matthew Auld <matthew.auld@intel.com>
Cc: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
Cc: Sanjay Yadav <sanjay.kumar.yadav@intel.com>
Signed-off-by: William Palacek <William.Palacek@amd.com>
---
Notes:
v4:
- new patch
drivers/gpu/buddy.c | 39 ++++-----------------------------------
include/linux/gpu_buddy.h | 7 -------
2 files changed, 4 insertions(+), 42 deletions(-)
diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index 26af5428ff76..95f98830b787 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -602,7 +602,6 @@ 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);
@@ -783,27 +782,6 @@ 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)
{
@@ -816,7 +794,6 @@ 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,
@@ -838,7 +815,6 @@ 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,
@@ -958,8 +934,6 @@ 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;
@@ -2025,17 +1999,13 @@ int gpu_buddy_block_trim(struct gpu_buddy *mm,
gpu_buddy_block_offset(block),
gpu_buddy_block_size(mm, block));
- /*
- * Detach the block to prevent recursively freeing this node, and to
- * keep free-order updates from propagating above it until the trim
- * is done.
- */
- parent = block->parent;
- block->parent = NULL;
-
__mark_free(mm, block, was_clear ? GPU_BLOCK_CLEAR : GPU_BLOCK_DIRTY);
mm->avail += gpu_buddy_block_size(mm, block);
+ /* Prevent recursively freeing this node */
+ parent = block->parent;
+ block->parent = NULL;
+
list_add(&block->tmp_link, &dfs);
err = __alloc_range(mm, &dfs, new_start, new_size,
was_clear ? GPU_BUDDY_CLEAR_ALLOCATION : 0,
@@ -2054,7 +2024,6 @@ 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 8037f5a0feb1..ddc4eca84175 100644
--- a/include/linux/gpu_buddy.h
+++ b/include/linux/gpu_buddy.h
@@ -141,15 +141,8 @@ 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.43.0
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH v4 3/3] gpu/tests/buddy: add range-biased allocation tests
2026-11-18 20:16 [PATCH v4 0/3] gpu/buddy: find range-biased blocks in the free trees William Palacek
2026-11-18 20:16 ` [PATCH v4 1/3] " William Palacek
2026-11-18 20:17 ` [PATCH v4 2/3] gpu/buddy: drop subtree_max_free_order William Palacek
@ 2026-11-18 20:17 ` William Palacek
2 siblings, 0 replies; 4+ messages in thread
From: William Palacek @ 2026-11-18 20:17 UTC (permalink / raw)
To: dri-devel
Cc: intel-xe, Matthew Auld, Arunpravin Paneer Selvam, Sanjay Yadav,
Joel Fernandes, Christian König, linux-kernel,
William Palacek
Check that a range-biased allocation with start > end fails with
-ENOSPC.
Fill a 1 GiB range of a 4 GiB manager top-down with 64 KiB range-biased
allocations that request cleared memory, as amdgpu does for KFD VRAM on
NPS4 partitions, check that each one is placed directly below the
previous one, and report the time taken.
Cc: Matthew Auld <matthew.auld@intel.com>
Cc: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
Signed-off-by: William Palacek <William.Palacek@amd.com>
---
Notes:
v4:
- add the start > end test
- drop the before/after times; with Sanjay's pruning the old walk is
already fast on this test
v3:
- times for the new base and lookup (1103 ms, 2 ms)
v2:
- check top-down placement
drivers/gpu/tests/gpu_buddy_test.c | 67 ++++++++++++++++++++++++++++++
1 file changed, 67 insertions(+)
diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
index 9aaca2fc6a02..374f576c91f5 100644
--- a/drivers/gpu/tests/gpu_buddy_test.c
+++ b/drivers/gpu/tests/gpu_buddy_test.c
@@ -283,6 +283,32 @@ static void gpu_test_buddy_fragmentation_performance(struct kunit *test)
gpu_buddy_fini(&mm);
}
+static void gpu_test_buddy_range_bias_performance(struct kunit *test)
+{
+ struct gpu_buddy_block *block;
+ LIST_HEAD(allocated);
+ struct gpu_buddy mm;
+ ktime_t t0;
+ u64 i;
+
+ /* Fill one NPS4-like quarter top-down with cleared 64 KiB allocations. */
+ KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, SZ_4G, SZ_4K));
+ t0 = ktime_get();
+ for (i = 1; i <= SZ_1G / SZ_64K; i++) {
+ KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, SZ_1G, SZ_2G, SZ_64K,
+ SZ_64K, &allocated,
+ GPU_BUDDY_RANGE_ALLOCATION |
+ GPU_BUDDY_CLEAR_ALLOCATION |
+ GPU_BUDDY_TOPDOWN_ALLOCATION));
+ block = list_last_entry(&allocated, struct gpu_buddy_block, link);
+ KUNIT_ASSERT_EQ(test, gpu_buddy_block_offset(block), SZ_2G - i * SZ_64K);
+ }
+ kunit_info(test, "Range-biased fill took %lld ms\n",
+ ktime_ms_delta(ktime_get(), t0));
+ gpu_buddy_free_list(&mm, &allocated, 0);
+ gpu_buddy_fini(&mm);
+}
+
static void gpu_test_buddy_dirty_tracker_performance(struct kunit *test)
{
struct gpu_buddy_block *block, *tmp;
@@ -1606,6 +1632,45 @@ static int gpu_buddy_suite_init(struct kunit_suite *suite)
return 0;
}
+static void gpu_test_buddy_alloc_range_inverted(struct kunit *test)
+{
+ const unsigned long chunk = SZ_1M, mm_size = SZ_4M;
+ LIST_HEAD(low_dirty);
+ LIST_HEAD(barrier);
+ LIST_HEAD(high);
+ LIST_HEAD(res);
+ struct gpu_buddy mm;
+
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, chunk),
+ "buddy_init failed\n");
+
+ /*
+ * [0, 1M) dirty free
+ * [1M, 2M) allocated
+ * [2M, 4M) clear free, one order-1 block larger than @end below
+ */
+ KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 0, chunk, chunk, chunk,
+ &low_dirty, GPU_BUDDY_RANGE_ALLOCATION));
+ KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, chunk, 2 * chunk, chunk, chunk,
+ &barrier, GPU_BUDDY_RANGE_ALLOCATION));
+ KUNIT_ASSERT_FALSE(test, gpu_buddy_alloc_blocks(&mm, 2 * chunk, mm_size,
+ 2 * chunk, 2 * chunk, &high,
+ GPU_BUDDY_RANGE_ALLOCATION));
+ gpu_buddy_free_list(&mm, &low_dirty, 0);
+ gpu_buddy_free_list(&mm, &high, GPU_BUDDY_CLEARED);
+
+ /* start > end: nothing lies in the range, so expect -ENOSPC */
+ KUNIT_EXPECT_EQ(test, gpu_buddy_alloc_blocks(&mm, 2 * chunk, chunk, chunk, chunk, &res,
+ GPU_BUDDY_RANGE_ALLOCATION |
+ GPU_BUDDY_CLEAR_ALLOCATION),
+ -ENOSPC);
+ KUNIT_EXPECT_TRUE(test, list_empty(&res));
+
+ gpu_buddy_free_list(&mm, &res, 0);
+ gpu_buddy_free_list(&mm, &barrier, 0);
+ gpu_buddy_fini(&mm);
+}
+
static void gpu_test_buddy_alloc_range_clear_guard(struct kunit *test)
{
const unsigned long chunk = SZ_1M, mm_size = SZ_4M;
@@ -1699,8 +1764,10 @@ static struct kunit_case gpu_buddy_tests[] = {
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(gpu_test_buddy_alloc_range_inverted),
KUNIT_CASE_SLOW(gpu_test_buddy_fragmentation_performance),
KUNIT_CASE_SLOW(gpu_test_buddy_dirty_tracker_performance),
+ KUNIT_CASE_SLOW(gpu_test_buddy_range_bias_performance),
KUNIT_CASE(gpu_test_buddy_alloc_exceeds_max_order),
KUNIT_CASE(gpu_test_buddy_offset_aligned_allocation),
KUNIT_CASE(gpu_test_buddy_subtree_offset_alignment_stress),
--
2.43.0
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2026-11-18 20:17 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-18 20:16 [PATCH v4 0/3] gpu/buddy: find range-biased blocks in the free trees William Palacek
2026-11-18 20:16 ` [PATCH v4 1/3] " William Palacek
2026-11-18 20:17 ` [PATCH v4 2/3] gpu/buddy: drop subtree_max_free_order William Palacek
2026-11-18 20:17 ` [PATCH v4 3/3] gpu/tests/buddy: add range-biased allocation tests William Palacek
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®