gpu: buddy: avoid repeated builds of root dfs when alloc range
Subsystems (2)
PATCH v2 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.
---
v2:
- Change __get_candidate_block to inline
- Link to v1: https://lore.kernel.org/all/ak+ECwsuSljmvyKd@hostpc/
--- 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 inline 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
[email protected]
AI reviewThank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Pre-existing issues:
- [High] Spurious -ENOSPC failure in __alloc_range() for fully free memory ranges due to unmerged SPLIT blocks. --
--- Patch [1]: [PATCH v2] gpu: buddy: avoid repeated builds of root dfs when alloc range --- commit 87b87afa0112d6b6bc23de2294a961d8ef1fb83e
Author: Zhaoyu Liu <[email protected]>
gpu: buddy: avoid repeated builds of root dfs when alloc range
This commit optimizes the buddy allocator by avoiding wasteful repeated builds of the DFS list during range allocations. It introduces __get_candidate_block() to unify block acquisition, falling back to lazily fetching the next root block only when the DFS list is exhausted.
Quoted 4 lines
drivers/gpu/buddy.c +0
-0
[ ... ]
Quoted 6 lines
drivers/gpu/buddy.c +0
-2@@ -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,
drivers/gpu/buddy.c static int __alloc_range(struct gpu_buddy *mm, · line 1067
Quoted 10 lines
drivers/gpu/buddy.c +2
-4- 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 ;
[Severity: High]
This is a pre-existing issue, but could allocations fail spuriously in __alloc_range() due to unmerged SPLIT blocks?
Looking further down in this same loop in __alloc_range():
if (contains(start, end, block_start, block_end)) {
if (gpu_buddy_block_is_free(block)) {
...
} else if (!mm->clear_avail) {
err = -ENOSPC;
goto err_free;
}
}If a previous allocation attempt splits a large free block but fails and does not undo the splits, the parent block is left marked as SPLIT with fully FREE children.
If the system globally has no available clear memory (mm->clear_avail == 0), a subsequent call to __alloc_range() requesting a range that completely encompasses this SPLIT block will satisfy the contains() check. However, because the parent block is SPLIT rather than FREE, it hits the !mm->clear_avail condition and immediately aborts the entire allocation with -ENOSPC.
Should this logic instead traverse down to allocate the perfectly free children instead of aborting?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/alTlW8TmTXLocWKP@hostpc?part=1
Quoted 5 lines · On Mon, Jul 13, 2026 at 01:31:31PM +0000, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Pre-existing issues:
- [High] Spurious-ENOSPCfailure in__alloc_range()for fully free memory ranges due to unmerged SPLIT blocks. --
As mentioned by AI, this is a pre-existing issue.
The reported problem is unrelated to the optimization patch we’re submitting currently. If this problem can be reproduced and confirmed as valid,
we will send a separate follow-up patch to fix it later.
Thanks,
zackary
Quoted 67 lines
--- Patch [1]: [PATCH v2] gpu: buddy: avoid repeated builds of root dfs when alloc range --- commit
87b87afa0112d6b6bc23de2294a961d8ef1fb83e
Author: Zhaoyu Liu <[email protected]>gpu: buddy: avoid repeated builds of root dfs when alloc range
This commit optimizes the buddy allocator by avoiding wasteful repeated builds of the DFS list during range allocations. It introduces
__get_candidate_block()to unify block acquisition, falling back to lazily fetching the next root block only when the DFS list is exhausted.Quoted 4 lines
drivers/gpu/buddy.c +0
-0[ ... ]
Quoted 6 lines
drivers/gpu/buddy.c +0
-2@@ -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,drivers/gpu/buddy.c static int __alloc_range(struct gpu_buddy *mm, · line 1067
Quoted 10 lines
drivers/gpu/buddy.c +2
-4- 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 ;[Severity: High]
This is a pre-existing issue, but could allocations fail spuriously in__alloc_range()due to unmerged SPLIT blocks?Looking further down in this same loop in
__alloc_range():if (contains(start, end, block_start, block_end)) { if (gpu_buddy_block_is_free(block)) { ... } else if (!mm->clear_avail) { err = -ENOSPC; goto err_free; } }If a previous allocation attempt splits a large free block but fails and does not undo the splits, the parent block is left marked as SPLIT with fully FREE children.
If the system globally has no available clear memory (
mm->clear_avail== 0), a subsequent call to__alloc_range()requesting a range that completely encompasses this SPLIT block will satisfy thecontains()check. However, because the parent block is SPLIT rather than FREE, it hits the !mm->clear_avail condition and immediately aborts the entire allocation with-ENOSPC.Should this logic instead traverse down to allocate the perfectly free children instead of aborting?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/alTlW8TmTXLocWKP@hostpc?part=1
On Mon, Jul 13, 2026 at 09:17:15PM +0800, Zhaoyu Liu wrote:
Hi,
Could you please help review and merge this patch?
And I'll submit additional new patches for follow-up work later.
Thanks,
zackary
Quoted 141 lines
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]>Suggested-by Arun Pravin <[email protected]>---
v2:
- Change__get_candidate_blockto inline
- Link to v1: https://lore.kernel.org/all/ak+ECwsuSljmvyKd@hostpc/--- 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 inline 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