* [PATCH v3 0/2] gpu/buddy: find range-biased blocks in the free trees
@ 2026-11-16 16:11 William Palacek
2026-11-16 16:11 ` [PATCH v3 1/2] " William Palacek
2026-11-16 16:11 ` [PATCH v3 2/2] gpu/tests/buddy: add range-biased allocation performance test William Palacek
0 siblings, 2 replies; 3+ messages in thread
From: William Palacek @ 2026-11-16 16:11 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
A range-restricted allocation walks every split block in the range, so
its cost grows linearly with the number of live allocations there.
amdgpu restricts every VRAM allocation to its memory partition under
NPS2/NPS4, so on MI300X in CPX/NPS4 KFD allocation latency grows with
every live BO, under a VRAM manager lock shared by the compute
partitions.
Patch 1 replaces the walk with an O(log n) lookup in the offset-sorted
free trees, based on Arun's class-aware version of v1; placement is
unchanged. Patch 2 adds a KUnit test for the NPS4 pattern (range-biased,
cleared, top-down, 64 KiB) that also checks placement: 1103 ms before,
2 ms after.
v2: https://patchwork.freedesktop.org/series/178108/
v1: https://patchwork.freedesktop.org/series/176957/
William Palacek (2):
gpu/buddy: find range-biased blocks in the free trees
gpu/tests/buddy: add range-biased allocation performance test
drivers/gpu/buddy.c | 214 +++++++++++++++++++----------
drivers/gpu/tests/gpu_buddy_test.c | 27 ++++
include/linux/gpu_buddy.h | 1 +
3 files changed, 172 insertions(+), 70 deletions(-)
--
2.43.0
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH v3 1/2] gpu/buddy: find range-biased blocks in the free trees
2026-11-16 16:11 [PATCH v3 0/2] gpu/buddy: find range-biased blocks in the free trees William Palacek
@ 2026-11-16 16:11 ` William Palacek
2026-11-16 16:11 ` [PATCH v3 2/2] gpu/tests/buddy: add range-biased allocation performance test William Palacek
1 sibling, 0 replies; 3+ messages in thread
From: William Palacek @ 2026-11-16 16:11 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 and visits
every split block overlapping [start, end) until it finds a suitable
free block, so a range-restricted allocation costs time linear in the
number of live allocations in the range. When both clear and dirty
space exist, a request that the strict pass cannot serve walks the
range twice.
amdgpu pays this on every VRAM allocation when memory is partitioned
(NPS2/NPS4): each BO, including the page-table BOs created when memory
is mapped, is restricted to its partition's range, and KFD requests
cleared VRAM. On MI300X in CPX/NPS4 the compute partitions that share a
memory partition also share the VRAM manager lock, so the walk is
serialised across processes. hipMalloc latency grows linearly with the
number of live allocations, and vLLM piecewise graph capture slows down
with every captured graph.
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 that can hold the request, then split the highest of them down to
the requested order. The strict pass only takes blocks wholly inside
the range whose class suits the request: subtree_block_state lets a
clear request skip subtrees without a clear or mixed block, and a new
subtree_has_dirty augment lets a dirty request skip subtrees that hold
only clear blocks. The fallback pass takes the highest block of either
class and may split one that straddles the range edge. Each lookup is
O(log n) and the walk is gone.
Placement is unchanged. A seeded random workload of 42218 allocations
mixing range, clear and top-down requests and cleared and dirty frees
places every block at the same offset, order and clear state as the
walk.
Filling 1 GiB of a 4 GiB manager with 64 KiB range-biased allocations
that request cleared memory takes 1103 ms before, 2 ms after (KUnit,
UML). With 8192 free cleared 64 KiB blocks interleaved with allocated
ones in the range, 4096 dirty range allocations take 541 to 567 ms
before and 0 ms after, and 4096 cleared ones 106 to 110 ms before and
0 ms after.
On MI300X in CPX/NPS4, with 8000 live 2 MiB hipMalloc allocations on
one partition, the median latency of the last 800 over the first 800 is
1.56x and 7.97x before and 0.52x and 1.06x after (two runs each; the
first run after loading the driver starts slow). vLLM piecewise graph
capture with tensor parallelism over all 64 partitions stays at 4 to 6 s
per graph for all 51 graphs.
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:
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 | 214 +++++++++++++++++++++++++-------------
include/linux/gpu_buddy.h | 1 +
2 files changed, 145 insertions(+), 70 deletions(-)
diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index e7d2212bcec9..baf17700ffba 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -62,6 +62,8 @@ static struct kmem_cache *slab_extents;
* of any block in the subtree, maintained as a max augment. A value of
* >= MIXED means a clear-or-mixed block exists; == CLEAR means a
* fully-clear block exists.
+ * - subtree_has_dirty: some block in the subtree is not fully clear,
+ * so range allocations can skip all-clear subtrees for dirty requests.
*
* Block classes
* -------------
@@ -510,9 +512,11 @@ static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block)
struct gpu_buddy_block *right;
struct gpu_buddy_block *left;
unsigned int max_align;
+ bool has_dirty;
max_align = gpu_buddy_block_offset_alignment(block);
block_state = gpu_block_cached_state(block);
+ has_dirty = block_state != GPU_BLOCK_CLEAR;
left = rb_entry_safe(block->rb.rb_left, struct gpu_buddy_block, rb);
if (left) {
@@ -520,6 +524,7 @@ static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block)
max_align = left->subtree_max_alignment;
block_state = max(block_state, left->subtree_block_state);
+ has_dirty |= left->subtree_has_dirty;
}
right = rb_entry_safe(block->rb.rb_right, struct gpu_buddy_block, rb);
@@ -528,10 +533,12 @@ static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block)
max_align = right->subtree_max_alignment;
block_state = max(block_state, right->subtree_block_state);
+ has_dirty |= right->subtree_has_dirty;
}
block->subtree_max_alignment = max_align;
block->subtree_block_state = block_state;
+ block->subtree_has_dirty = has_dirty;
}
static void gpu_buddy_augment_propagate(struct rb_node *rb, struct rb_node *stop)
@@ -540,14 +547,17 @@ static void gpu_buddy_augment_propagate(struct rb_node *rb, struct rb_node *stop
struct gpu_buddy_block *block;
unsigned int old_align;
enum gpu_block_state old_block_state;
+ bool old_has_dirty;
block = rb_entry(rb, struct gpu_buddy_block, rb);
old_align = block->subtree_max_alignment;
old_block_state = block->subtree_block_state;
+ old_has_dirty = block->subtree_has_dirty;
gpu_buddy_augment_compute(block);
if (block->subtree_max_alignment == old_align &&
- block->subtree_block_state == old_block_state)
+ block->subtree_block_state == old_block_state &&
+ block->subtree_has_dirty == old_has_dirty)
break;
rb = rb_parent(&block->rb);
@@ -564,6 +574,7 @@ static void gpu_buddy_augment_copy(struct rb_node *rb_old, struct rb_node *rb_ne
new->subtree_max_alignment = old->subtree_max_alignment;
new->subtree_block_state = old->subtree_block_state;
+ new->subtree_has_dirty = old->subtree_has_dirty;
}
static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
@@ -576,6 +587,7 @@ static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct rb_node *rb_
new->subtree_max_alignment = old->subtree_max_alignment;
new->subtree_block_state = old->subtree_block_state;
+ new->subtree_has_dirty = old->subtree_has_dirty;
gpu_buddy_augment_compute(old);
}
@@ -695,6 +707,8 @@ static void rbtree_insert(struct gpu_buddy *mm,
node->subtree_max_alignment = block_alignment;
if (node->subtree_block_state < block_state)
node->subtree_block_state = block_state;
+ if (block_state != GPU_BLOCK_CLEAR)
+ node->subtree_has_dirty = true;
if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node))
link = &parent->rb_left;
@@ -704,6 +718,7 @@ static void rbtree_insert(struct gpu_buddy *mm,
block->subtree_max_alignment = block_alignment;
block->subtree_block_state = block_state;
+ block->subtree_has_dirty = block_state != GPU_BLOCK_CLEAR;
rb_link_node(&block->rb, parent, link);
rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);
}
@@ -1247,96 +1262,155 @@ static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags
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,
- bool fallback)
+/* Does the subtree at @node hold a block the strict pass may take? */
+static bool range_subtree_ok(struct rb_node *node, unsigned long flags)
{
- u64 req_size = mm->chunk_size << order;
- struct gpu_buddy_block *block;
- LIST_HEAD(dfs);
- int err;
- int i;
+ struct gpu_buddy_block *block = rbtree_get_free_block(node);
- end = end - 1;
+ if (!block)
+ return false;
+ if (flags & GPU_BUDDY_CLEAR_ALLOCATION)
+ return block->subtree_block_state >= GPU_BLOCK_MIXED;
+ return block->subtree_has_dirty;
+}
- /*
- * 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);
+/*
+ * Highest-offset free block in @root with offset < @limit that the strict
+ * pass may take (any block when @fallback). Subtrees without such a block
+ * are skipped through the augments, so this is O(log n) per call.
+ */
+static struct gpu_buddy_block *
+rbtree_last_range_block(struct rb_root *root, u64 limit,
+ unsigned long flags, bool fallback)
+{
+ struct rb_node *node = root->rb_node;
+ struct rb_node *prev = NULL;
- do {
- u64 block_start;
- u64 block_end;
+ while (node) {
+ if (gpu_buddy_block_offset(rbtree_get_free_block(node)) < limit) {
+ prev = node;
+ node = node->rb_right;
+ } else {
+ node = node->rb_left;
+ }
+ }
- block = list_first_entry_or_null(&dfs,
- struct gpu_buddy_block,
- tmp_link);
- if (!block)
- break;
+ for (node = prev; node; node = rb_parent(node)) {
+ if (fallback ||
+ !block_incompatible(rbtree_get_free_block(node), flags))
+ return rbtree_get_free_block(node);
- list_del(&block->tmp_link);
+ if (range_subtree_ok(node->rb_left, flags)) {
+ /* The left subtree holds one: take its highest. */
+ node = node->rb_left;
+ while (node) {
+ struct gpu_buddy_block *block = rbtree_get_free_block(node);
- if (gpu_buddy_block_order(block) < order)
- continue;
+ if (range_subtree_ok(node->rb_right, flags)) {
+ node = node->rb_right;
+ continue;
+ }
+ if (!block_incompatible(block, flags))
+ return block;
+ node = node->rb_left;
+ }
+ return NULL;
+ }
- block_start = gpu_buddy_block_offset(block);
- block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
+ /* Climb to the next lower ancestor. */
+ while (rb_parent(node) && node == rb_parent(node)->rb_left)
+ node = rb_parent(node);
+ }
- if (!overlaps(start, end, block_start, block_end))
- continue;
+ return NULL;
+}
- if (gpu_buddy_block_is_allocated(block))
- continue;
+/*
+ * Return the order-@order block at the highest @req_size-aligned offset in
+ * [@start, @end) that lies inside a free block, splitting as needed. The
+ * strict pass only takes free blocks wholly inside the range whose class
+ * suits @flags; splitting a block that straddles the range edge is left to
+ * the fallback pass, which takes either class.
+ */
+static struct gpu_buddy_block *
+__alloc_range_bias(struct gpu_buddy *mm,
+ u64 start, u64 end,
+ unsigned int order,
+ unsigned long flags,
+ bool fallback)
+{
+ u64 req_size = mm->chunk_size << order;
+ struct gpu_buddy_block *block = NULL;
+ u64 best = 0;
+ unsigned int i;
+ int err;
- if (block_start < start || block_end > end) {
- u64 adjusted_start = max(block_start, start);
- u64 adjusted_end = min(block_end, end);
+ for (i = order; i <= mm->max_order; i++) {
+ struct rb_root *root = &mm->free_tree[i];
+ u64 size = mm->chunk_size << i;
+ struct gpu_buddy_block *found;
+ u64 offset = 0;
- if (round_down(adjusted_end + 1, req_size) <=
- round_up(adjusted_start, req_size))
- continue;
+ if (!fallback) {
+ if (end - start < size)
+ break;
- /*
- * 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))
+ found = rbtree_last_range_block(root, end - size + 1,
+ flags, false);
+ if (!found || gpu_buddy_block_offset(found) < start)
continue;
- }
-
- if (!fallback && block_incompatible(block, flags))
- continue;
- if (contains(start, end, block_start, block_end) &&
- order == gpu_buddy_block_order(block)) {
- /*
- * Find the free block within the range.
- */
- if (gpu_buddy_block_is_free(block))
- return block;
+ offset = gpu_buddy_block_offset(found) + size - req_size;
+ } else {
+ /* At most the blocks straddling @end and @start miss. */
+ for (found = rbtree_last_range_block(root, end, flags, true);
+ found;
+ found = rbtree_get_free_block(rb_prev(&found->rb))) {
+ u64 lo = max(gpu_buddy_block_offset(found), start);
+ u64 hi = min(gpu_buddy_block_offset(found) + size, end);
+
+ if (hi <= start) {
+ found = NULL;
+ break;
+ }
- continue;
+ if (hi >= lo + req_size) {
+ offset = round_down(hi - req_size, req_size);
+ if (offset >= lo)
+ break;
+ }
+ }
+ if (!found)
+ continue;
}
- if (!gpu_buddy_block_is_split(block)) {
- err = split_block(mm, block);
- if (unlikely(err))
- goto err_undo;
+ if (!block || offset > best) {
+ block = found;
+ best = offset;
}
+ }
- list_add(&block->left->tmp_link, &dfs);
- list_add(&block->right->tmp_link, &dfs);
- } while (1);
+ if (!block)
+ return ERR_PTR(-ENOSPC);
+
+ while (gpu_buddy_block_order(block) > order) {
+ err = split_block(mm, block);
+ if (unlikely(err))
+ goto err_undo;
- return ERR_PTR(-ENOSPC);
+ /*
+ * Fallback: the child holding @best. Strict: the higher child
+ * unless its class does not suit, as the old walk did.
+ */
+ if (fallback)
+ block = best >= gpu_buddy_block_offset(block->right) ?
+ block->right : block->left;
+ else
+ block = block_incompatible(block->right, flags) ?
+ block->left : block->right;
+ }
+
+ return block;
err_undo:
/*
diff --git a/include/linux/gpu_buddy.h b/include/linux/gpu_buddy.h
index ddc4eca84175..6abc66125935 100644
--- a/include/linux/gpu_buddy.h
+++ b/include/linux/gpu_buddy.h
@@ -141,6 +141,7 @@ struct gpu_buddy_block {
unsigned int subtree_max_alignment;
struct list_head tmp_link;
bool has_clear;
+ bool subtree_has_dirty;
};
/* Order-zero must be at least SZ_4K */
--
2.43.0
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH v3 2/2] gpu/tests/buddy: add range-biased allocation performance test
2026-11-16 16:11 [PATCH v3 0/2] gpu/buddy: find range-biased blocks in the free trees William Palacek
2026-11-16 16:11 ` [PATCH v3 1/2] " William Palacek
@ 2026-11-16 16:11 ` William Palacek
1 sibling, 0 replies; 3+ messages in thread
From: William Palacek @ 2026-11-16 16:11 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
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: 1103 ms with the walk, 2 ms
with the free tree lookup.
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:
v3:
- times for the new base and lookup (1103 ms, 2 ms)
v2:
- check top-down placement
drivers/gpu/tests/gpu_buddy_test.c | 27 +++++++++++++++++++++++++++
1 file changed, 27 insertions(+)
diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
index 9aaca2fc6a02..e48a99136e68 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;
@@ -1701,6 +1727,7 @@ static struct kunit_case gpu_buddy_tests[] = {
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_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] 3+ messages in thread
end of thread, other threads:[~2026-11-16 16:12 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-16 16:11 [PATCH v3 0/2] gpu/buddy: find range-biased blocks in the free trees William Palacek
2026-11-16 16:11 ` [PATCH v3 1/2] " William Palacek
2026-11-16 16:11 ` [PATCH v3 2/2] gpu/tests/buddy: add range-biased allocation performance test 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®