gpu: buddy: avoid repeated builds of root dfs when alloc range
Subsystems (2)
PATCH 1/1 gpu: buddy: avoid repeated builds of root dfs when alloc range
The buddy allocator previously pre-built a DFS list by inserting all root blocks via list_add_tail() before every allocation call in __alloc_range_bias() and __gpu_buddy_alloc_range(). This is wasteful when the allocation can be satisfied by the first root or by sub-blocks produced from splits, as the remaining roots are never consumed.
Introduce __get_candidate_block() which unifies the block acquisition logic for both __alloc_range_bias() and __alloc_range(): it first checks the DFS list (populated by splits during allocation or pre-filled by the caller for trim), and only when the list is exhausted does it lazily fetch the next root block through a cursor.
When the caller pre-fills the DFS list (trim scenario), the cursor is initialized to mm->n_roots to disable root iteration entirely, preserving the original behavior.
--- drivers/gpu/buddy.c | 61 ++++++++++++++++++++++++++++++--------------- 1 file changed, 41 insertions(+), 20 deletions(-)
drivers/gpu/buddy.c +41 -20
@@ -700,6 +700,41 @@ static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, } } +/** +* __get_candidate_block - Get a candidate block for allocation. +* @mm: GPU buddy manager +* @dfs: List of candidate blocks. Populated in two ways: (1) pre-filled by +* the caller before allocation with blocks available for allocation, +* and (2) extended during allocation by block splits, which add the +* resulting sub-blocks for subsequent finer-grained allocation. +* @cursor: Pointer to current root index, advanced when iterating roots. +* Pass in a value >= mm->n_roots to disable root iteration entirely, +* restricting block acquisition to @dfs only; this is used in the +* trim scenario where only pre-split sub-blocks should be considered. +* +* Return: Pointer to the acquired block on success, ERR_PTR(-ENOSPC) when no +* more blocks are available. +*/ +static struct gpu_buddy_block * +__get_candidate_block (struct gpu_buddy *mm,struct list_head *dfs, +uint32_t *cursor) +{ +struct gpu_buddy_block *block; + + block =list_first_entry_or_null (dfs, + struct gpu_buddy_block, + tmp_link); +if (block) { +list_del (&block->tmp_link); +return block; + } + +if (*cursor >= mm->n_roots) +return ERR_PTR (-ENOSPC ); + +return mm->roots[(*cursor)++]; +} +static struct gpu_buddy_block * __alloc_range_bias(struct gpu_buddy *mm, u64 start, u64 end,
@@ -711,25 +746,18 @@ __alloc_range_bias(struct gpu_buddy *mm,struct gpu_buddy_block *block;LIST_HEAD (dfs);int err; -int i; +uint32_t cursor =0 ; end = end -1 ; -for (i =0 ; i < mm->n_roots; ++i) -list_add_tail (&mm->roots[i]->tmp_link, &dfs); - do { u64 block_start; u64 block_end; - block = list_first_entry_or_null(&dfs, - struct gpu_buddy_block, - tmp_link); - if (!block) + block = __get_candidate_block(mm, &dfs, &cursor); + if (IS_ERR(block)) break; - list_del(&block->tmp_link); - if (gpu_buddy_block_order(block) < order) continue;
@@ -1023,6 +1051,7 @@ static int __alloc_range(struct gpu_buddy *mm,LIST_HEAD (allocated);u64 end;int err; +uint32_t cursor =list_empty (dfs) ?0 : mm->n_roots; end = start + size -1 ;
@@ -1030,14 +1059,10 @@ static int __alloc_range(struct gpu_buddy *mm,u64 block_start;u64 block_end; - block =list_first_entry_or_null (dfs, - struct gpu_buddy_block, - tmp_link); -if (!block) + block =__get_candidate_block (mm, dfs, &cursor); +if (IS_ERR (block))break ; -list_del (&block->tmp_link); - block_start =gpu_buddy_block_offset (block); block_end = block_start +gpu_buddy_block_size (mm, block) -1 ;
@@ -1109,10 +1134,6 @@ static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, struct list_head *blocks) {LIST_HEAD (dfs); -int i; - -for (i =0 ; i < mm->n_roots; ++i) -list_add_tail (&mm->roots[i]->tmp_link, &dfs);return __alloc_range (mm, &dfs, start, size, blocks, total_allocated_on_err);
Signature · 1 line
2.34.1
Please help review this patch.
Thanks!
Quoted 140 lines
From: "Zhaoyu Liu"<[email protected]>
Date: Thu, Jul 9, 2026, 19:20
Subject: [PATCH] gpu: buddy: avoid repeated builds of root dfs when alloc range
To: <[email protected]>, <[email protected]>, <[email protected]>, <[email protected]>, <[email protected]>
Cc: <[email protected]>, <[email protected]>
The buddy allocator previously pre-built a DFS list by inserting all
root blocks vialist_add_tail()before every allocation call in__alloc_range_bias()and__gpu_buddy_alloc_range(). This is wasteful
when the allocation can be satisfied by the first root or by sub-blocks
produced from splits, as the remaining roots are never consumed.
Introduce__get_candidate_block()which unifies the block acquisition
logic for both__alloc_range_bias()and__alloc_range(): it first
checks the DFS list (populated by splits during allocation or
pre-filled by the caller for trim), and only when the list is exhausted
does it lazily fetch the next root block through a cursor.
When the caller pre-fills the DFS list (trim scenario), the cursor is
initialized tomm->n_rootsto disable root iteration entirely,
preserving the original behavior.Signed-off-by Zhaoyu Liu <[email protected]>---
drivers/gpu/buddy.c | 61 ++++++++++++++++++++++++++++++---------------1 file changed, 41 insertions(+), 20 deletions(-)drivers/gpu/buddy.c +0
-0@@ -700,6 +700,41 @@ static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, } }drivers/gpu/buddy.c +35
-0+/** +* __get_candidate_block - Get a candidate block for allocation. +* @mm: GPU buddy manager +* @dfs: List of candidate blocks. Populated in two ways: (1) pre-filled by +* the caller before allocation with blocks available for allocation, +* and (2) extended during allocation by block splits, which add the +* resulting sub-blocks for subsequent finer-grained allocation. +* @cursor: Pointer to current root index, advanced when iterating roots. +* Pass in a value >= mm->n_roots to disable root iteration entirely, +* restricting block acquisition to @dfs only; this is used in the +* trim scenario where only pre-split sub-blocks should be considered. +* +* Return: Pointer to the acquired block on success, ERR_PTR(-ENOSPC) when no +* more blocks are available. +*/ +static struct gpu_buddy_block * +__get_candidate_block (struct gpu_buddy *mm,struct list_head *dfs, + uint32_t *cursor) +{ + struct gpu_buddy_block *block; + + block = list_first_entry_or_null(dfs, + struct gpu_buddy_block, + tmp_link); + if (block) { + list_del(&block->tmp_link); + return block; + } + + if (*cursor >= mm->n_roots) + return ERR_PTR(-ENOSPC); + + return mm->roots[(*cursor)++]; +} +static struct
gpu_buddy_block*
__alloc_range_bias(structgpu_buddy*mm,
u64 start, u64 end,drivers/gpu/buddy.c +1
-1@@ -711,25 +746,18 @@ __alloc_range_bias(struct gpu_buddy *mm, struct gpu_buddy_block *block; LIST_HEAD(dfs); int err; - int i; + uint32_t cursor = 0;
end = end - 1;
- for (i = 0; i <mm->n_roots; ++i)
- list_add_tail(&mm->roots[i]->tmp_link, &dfs); -
do {
u64block_start;
u64block_end;
- block = list_first_entry_or_null(&dfs,
- structgpu_buddy_block,
-tmp_link);
- if (!block)
+ block =__get_candidate_block(mm, &dfs, &cursor);
+ if (IS_ERR(block))
break;
- list_del(&block->tmp_link);
-
if (gpu_buddy_block_order(block)< order) continue;drivers/gpu/buddy.c +1
-0@@ -1023,6 +1051,7 @@ static int __alloc_range(struct gpu_buddy *mm, LIST_HEAD(allocated); u64 end; int err; + uint32_t cursor = list_empty(dfs) ? 0 : mm->n_roots;
end = start + size - 1;drivers/gpu/buddy.c +0
-0@@ -1030,14 +1059,10 @@ static int __alloc_range(struct gpu_buddy *mm, u64 block_start; u64 block_end;
- block = list_first_entry_or_null(dfs,
- structgpu_buddy_block,
-tmp_link);
- if (!block)
+ block =__get_candidate_block(mm, dfs, &cursor);
+ if (IS_ERR(block))
break;
- list_del(&block->tmp_link);
-
block_start =gpu_buddy_block_offset(block);block_end=block_start+gpu_buddy_block_size(mm, block)- 1;drivers/gpu/buddy.c +0
-4@@ -1109,10 +1134,6 @@ static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, struct list_head *blocks) { LIST_HEAD(dfs); - int i; - - for (i = 0; i < mm->n_roots; ++i) - list_add_tail(&mm->roots[i]->tmp_link, &dfs);
return__alloc_range(mm, &dfs, start, size, blocks, total_allocated_on_err); --
2.34.1
Arunpravin Paneer Selvam
maintainerQuoted 4 lines · 刘照玉
[You don't often get email from [email protected]. Learn why this is important at https://aka.ms/LearnAboutSenderIdentification ]
Please help review this patch.
Thanks!
I was wondering whether this optimization provides a measurable benefit in practice. Since mm->n_roots is typically quite small, the previous DFS list construction only adds a few list_add_tail() operations per allocation. On the other hand, the new approach introduces an additional helper call and branching during candidate selection. Have you done any profiling or benchmarking to quantify the improvement?
Thanks,
Arun.
Quoted 141 lines
Quoted 141 lines
From: "Zhaoyu Liu"<[email protected]> Date: Thu, Jul 9, 2026, 19:20 Subject: [PATCH] gpu: buddy: avoid repeated builds of root dfs when alloc range To: <[email protected]>, <[email protected]>, <[email protected]>, <[email protected]>, <[email protected]>Cc: <[email protected]>, <[email protected]> The buddy allocator previously pre-built a DFS list by inserting all root blocks via
list_add_tail()before every allocation call in__alloc_range_bias()and__gpu_buddy_alloc_range(). This is wasteful when the allocation can be satisfied by the first root or by sub-blocks produced from splits, as the remaining roots are never consumed.Introduce
__get_candidate_block()which unifies the block acquisition logic for both__alloc_range_bias()and__alloc_range(): it first checks the DFS list (populated by splits during allocation or pre-filled by the caller for trim), and only when the list is exhausted does it lazily fetch the next root block through a cursor.When the caller pre-fills the DFS list (trim scenario), the cursor is initialized to
mm->n_rootsto disable root iteration entirely, preserving the original behavior.Signed-off-by Zhaoyu Liu <[email protected]>--- drivers/gpu/buddy.c | 61 ++++++++++++++++++++++++++++++--------------- 1 file changed, 41 insertions(+), 20 deletions(-)drivers/gpu/buddy.c +41
-21@@ -700,6 +700,41 @@ static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, } } +/** +* __get_candidate_block - Get a candidate block for allocation. +* @mm: GPU buddy manager +* @dfs: List of candidate blocks. Populated in two ways: (1) pre-filled by +* the caller before allocation with blocks available for allocation, +* and (2) extended during allocation by block splits, which add the +* resulting sub-blocks for subsequent finer-grained allocation. +* @cursor: Pointer to current root index, advanced when iterating roots. +* Pass in a value >= mm->n_roots to disable root iteration entirely, +* restricting block acquisition to @dfs only; this is used in the +* trim scenario where only pre-split sub-blocks should be considered. +* +* Return: Pointer to the acquired block on success, ERR_PTR(-ENOSPC) when no +* more blocks are available. +*/ +static struct gpu_buddy_block * +__get_candidate_block (struct gpu_buddy *mm,struct list_head *dfs, +uint32_t *cursor) +{ +struct gpu_buddy_block *block; + + block =list_first_entry_or_null (dfs, + struct gpu_buddy_block, + tmp_link); +if (block) { +list_del (&block->tmp_link); +return block; + } + +if (*cursor >= mm->n_roots) +return ERR_PTR (-ENOSPC ); + +return mm->roots[(*cursor)++]; +} +static struct gpu_buddy_block * __alloc_range_bias(struct gpu_buddy *mm, u64 start, u64 end,@@ -711,25 +746,18 @@ __alloc_range_bias(struct gpu_buddy *mm,struct gpu_buddy_block *block;LIST_HEAD (dfs);int err; -int i; +uint32_t cursor =0 ; end = end -1 ; -for (i =0 ; i < mm->n_roots; ++i) -list_add_tail (&mm->roots[i]->tmp_link, &dfs); - do { u64 block_start; u64 block_end; - block = list_first_entry_or_null(&dfs, - struct gpu_buddy_block, - tmp_link); - if (!block) + block = __get_candidate_block(mm, &dfs, &cursor); + if (IS_ERR(block)) break; - list_del(&block->tmp_link); - if (gpu_buddy_block_order(block) < order) continue;@@ -1023,6 +1051,7 @@ static int __alloc_range(struct gpu_buddy *mm,LIST_HEAD (allocated);u64 end;int err; +uint32_t cursor =list_empty (dfs) ?0 : mm->n_roots; end = start + size -1 ;@@ -1030,14 +1059,10 @@ static int __alloc_range(struct gpu_buddy *mm,u64 block_start;u64 block_end; - block =list_first_entry_or_null (dfs, - struct gpu_buddy_block, - tmp_link); -if (!block) + block =__get_candidate_block (mm, dfs, &cursor); +if (IS_ERR (block))break ; -list_del (&block->tmp_link); - block_start =gpu_buddy_block_offset (block); block_end = block_start +gpu_buddy_block_size (mm, block) -1 ;@@ -1109,10 +1134,6 @@ static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, struct list_head *blocks) {LIST_HEAD (dfs); -int i; - -for (i =0 ; i < mm->n_roots; ++i) -list_add_tail (&mm->roots[i]->tmp_link, &dfs);return __alloc_range (mm, &dfs, start, size, blocks, total_allocated_on_err); --2.34.1
Quoted 14 lines · Arunpravin Paneer Selvam
Quoted 4 lines · 刘照玉
[You don't often get email from [email protected]. Learn why this is important at https://aka.ms/LearnAboutSenderIdentification ]
Please help review this patch.
Thanks!I was wondering whether this optimization provides a measurable benefit in practice. Since
mm->n_rootsis typically quite small, the previous DFS list construction only adds a fewlist_add_tail()operations per allocation. On the other hand, the new approach introduces an additional helper call and branching during candidate selection. Have you done any profiling or benchmarking to quantify the improvement?
Quoted 2 lines
Thanks,
Arun.
Thank you for your review, Arun.
To verify the gain, a KUnit perf case (gpu_test_buddy_range_alloc_perf) was added locally. It sweeps fixed 1MB bias ranges across the whole address space, allocating and freeing each range exactly, repeated 10000 iterations.
Two scenarios cover the two extremes of n_roots:
- 16MB mm -> n_roots = 1 (16 bias ranges)
- 1GB-1 mm -> n_roots = 18 (1023 bias ranges)
Each configuration was measured 3 times and averaged. Three builds were compared:
- baseline : unmodified tree
- no-inline : patched, __get_candidate_block is static
- inline : patched, __get_candidate_block is static inline
+----------+-----------------+------------------+------------------+ | mm_size | baseline (ns) | no-inline (ns) | inline (ns) | | | | (change vs base) | (change vs base) | +----------+-----------------+------------------+------------------+ | 16MB | 66877 | 66598 | 64663 | | | | -0.42% | -3.31% | +----------+-----------------+------------------+------------------+ | 1GB-1 | 9333559 | 9193052 | 9251951 | | | | -1.51% | -0.87% | +----------+-----------------+------------------+------------------+
And, I've sent new v2 patch with inline function,
Please help review it again.
Thanks,
zackary
Quoted 137 lines
Quoted 136 lines
Quoted 136 lines
From: "Zhaoyu Liu"<[email protected]> Date: Thu, Jul 9, 2026, 19:20 Subject: [PATCH] gpu: buddy: avoid repeated builds of root dfs when alloc range To: <[email protected]>, <[email protected]>, <[email protected]>, <[email protected]>, <[email protected]>Cc: <[email protected]>, <[email protected]> The buddy allocator previously pre-built a DFS list by inserting all root blocks via
list_add_tail()before every allocation call in__alloc_range_bias()and__gpu_buddy_alloc_range(). This is wasteful when the allocation can be satisfied by the first root or by sub-blocks produced from splits, as the remaining roots are never consumed. Introduce__get_candidate_block()which unifies the block acquisition logic for both__alloc_range_bias()and__alloc_range(): it first checks the DFS list (populated by splits during allocation or pre-filled by the caller for trim), and only when the list is exhausted does it lazily fetch the next root block through a cursor. When the caller pre-fills the DFS list (trim scenario), the cursor is initialized tomm->n_rootsto disable root iteration entirely, preserving the original behavior.Signed-off-by Zhaoyu Liu <[email protected]>--- drivers/gpu/buddy.c | 61 ++++++++++++++++++++++++++++++--------------- 1 file changed, 41 insertions(+), 20 deletions(-)drivers/gpu/buddy.c +41
-21@@ -700,6 +700,41 @@ static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, } } +/** +* __get_candidate_block - Get a candidate block for allocation. +* @mm: GPU buddy manager +* @dfs: List of candidate blocks. Populated in two ways: (1) pre-filled by +* the caller before allocation with blocks available for allocation, +* and (2) extended during allocation by block splits, which add the +* resulting sub-blocks for subsequent finer-grained allocation. +* @cursor: Pointer to current root index, advanced when iterating roots. +* Pass in a value >= mm->n_roots to disable root iteration entirely, +* restricting block acquisition to @dfs only; this is used in the +* trim scenario where only pre-split sub-blocks should be considered. +* +* Return: Pointer to the acquired block on success, ERR_PTR(-ENOSPC) when no +* more blocks are available. +*/ +static struct gpu_buddy_block * +__get_candidate_block (struct gpu_buddy *mm,struct list_head *dfs, +uint32_t *cursor) +{ +struct gpu_buddy_block *block; + + block =list_first_entry_or_null (dfs, + struct gpu_buddy_block, + tmp_link); +if (block) { +list_del (&block->tmp_link); +return block; + } + +if (*cursor >= mm->n_roots) +return ERR_PTR (-ENOSPC ); + +return mm->roots[(*cursor)++]; +} +static struct gpu_buddy_block * __alloc_range_bias(struct gpu_buddy *mm, u64 start, u64 end,@@ -711,25 +746,18 @@ __alloc_range_bias(struct gpu_buddy *mm,struct gpu_buddy_block *block;LIST_HEAD (dfs);int err; -int i; +uint32_t cursor =0 ; end = end -1 ; -for (i =0 ; i < mm->n_roots; ++i) -list_add_tail (&mm->roots[i]->tmp_link, &dfs); - do { u64 block_start; u64 block_end; - block = list_first_entry_or_null(&dfs, - struct gpu_buddy_block, - tmp_link); - if (!block) + block = __get_candidate_block(mm, &dfs, &cursor); + if (IS_ERR(block)) break; - list_del(&block->tmp_link); - if (gpu_buddy_block_order(block) < order) continue;@@ -1023,6 +1051,7 @@ static int __alloc_range(struct gpu_buddy *mm,LIST_HEAD (allocated);u64 end;int err; +uint32_t cursor =list_empty (dfs) ?0 : mm->n_roots; end = start + size -1 ;@@ -1030,14 +1059,10 @@ static int __alloc_range(struct gpu_buddy *mm,u64 block_start;u64 block_end; - block =list_first_entry_or_null (dfs, - struct gpu_buddy_block, - tmp_link); -if (!block) + block =__get_candidate_block (mm, dfs, &cursor); +if (IS_ERR (block))break ; -list_del (&block->tmp_link); - block_start =gpu_buddy_block_offset (block); block_end = block_start +gpu_buddy_block_size (mm, block) -1 ;@@ -1109,10 +1134,6 @@ static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, struct list_head *blocks) {LIST_HEAD (dfs); -int i; - -for (i =0 ; i < mm->n_roots; ++i) -list_add_tail (&mm->roots[i]->tmp_link, &dfs);return __alloc_range (mm, &dfs, start, size, blocks, total_allocated_on_err); --2.34.1