__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 28cff97d57dc..b77d7f621290 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);
