On 13-10-2026 10:18, Arunpravin Paneer Selvam wrote:
On 10/12/2026 4:40 PM, Sanjay Yadav wrote:
__alloc_range_bias() walks the buddy tree depth-first, higher address
first, and descends every SPLIT block even when nothing below it is
free. Range allocations are placed top-down, so they pack below the
range end and each new one walks every block already allocated there:
O(N) per allocation and O(N^2) for N allocations, under the allocator
lock.
Track in each block the largest order of any FREE block in its subtree
(GPU_BUDDY_NO_FREE_ORDER if none), update it whenever a block changes
state, and skip subtrees that cannot satisfy the requested order.
gpu_buddy_block_trim() detaches the block while re-allocating inside
it, so recompute from the parent once it is reattached.
Skipped subtrees contain no FREE block of the requested order or
larger, so the old walk could neither split nor return anything there.
The remaining blocks are visited in the same order, so the selected
block and placement are unchanged.
Cc: Matthew Auld <[email protected]>
Cc: Arun Pravin <[email protected]>
Cc: Joel Fernandes <[email protected]>
Assisted-by: LLM
Signed-off-by: Sanjay Yadav <[email protected]>
---
drivers/gpu/buddy.c | 31 +++++++++++++++++++++++++++++++
include/linux/gpu_buddy.h | 7 +++++++
2 files changed, 38 insertions(+)
diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index 2f2aaadafe35..7a975873238f 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -602,6 +602,7 @@ 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);
@@ -717,6 +718,27 @@ 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)
{
@@ -729,6 +751,7 @@ 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,
@@ -750,6 +773,7 @@ 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,
@@ -772,6 +796,7 @@ static void mark_split(struct gpu_buddy *mm,
mm->free_scoreboard[gpu_buddy_block_order(block)]--;
rbtree_remove(mm, block);
+ update_subtree_max_free_order(block);
}
Just wondering if touching mark_free(), mark_allocated(), mark_split()
which are hot-path functions, could have any performance implications.?
Regards,
Arun.
Hi Arun,
Yes, I measured the impact because these are hot-path functions.
update_subtree_max_free_order() stops at the first ancestor whose value
remains unchanged. Across the tested workloads,
it walked approximately three levels on average, and around 88% of calls
stopped within four levels. Reaching the root was rare.
Cost on the normal (non-range) path. Existing gpu_buddy KUnit
performance tests, drm-tip vs drm-tip + patch:
Test drm-tip + patch
Fragmented allocation 139ms 154ms
Reverse-ordered free 91ms 96ms
Contiguous alloc after fragmentation 8ms 8ms
Repeated 256 KiB allocs from fragmented pool 14ms 14ms
For platform approximately 12 GiB VRAM and a 4 GiB BAR: xe_pat
pt-caching-random-offsets, per window of 16k allocations.
Metric Without Patch With Patch
Average range-allocation time 78-793µs 340-494ns
Blocks visited per allocation 16K-147K 38-39
xe_pat pt-caching-random-offsets runtime ~48s ~0.7s
Yes normal-path cost is increased very small and bounded, while the
patch removes the quadratic slowdown from range-restricted allocations.
static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
@@ -869,6 +894,8 @@ 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;
@@ -1280,6 +1307,9 @@ __alloc_range_bias(struct gpu_buddy *mm,
if (gpu_buddy_block_order(block) < order)
continue;
+ if (block->subtree_max_free_order < (int)order)
+ continue;
+
block_start = gpu_buddy_block_offset(block);
block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
@@ -1881,6 +1911,7 @@ 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 ddc4eca84175..8037f5a0feb1 100644
--- a/include/linux/gpu_buddy.h
+++ b/include/linux/gpu_buddy.h
@@ -141,8 +141,15 @@ 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)
