[PATCH v2] gpu: buddy: avoid repeated builds of root dfs when alloc range

[PATCH v2] gpu: buddy: avoid repeated builds of root dfs when alloc range

[Zhaoyu Liu]

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.

Signed-off-by: Zhaoyu Liu <liuzhaoyu.zackary@picoheart.com>
Suggested-by: Arun Pravin <arunpravin.paneerselvam@amd.com>
---

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(-)

diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index dc81fe0301ce..63b3959973fa 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -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);
-- 
2.34.1

Re: [PATCH v2] gpu: buddy: avoid repeated builds of root dfs when alloc range

[sashiko-bot]

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 <liuzhaoyu.zackary@picoheart.com>

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.

> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> index 3c73ae87f3c5b..72f521c51b3fa 100644
> --- a/drivers/gpu/buddy.c
> +++ b/drivers/gpu/buddy.c

[ ... ]

> @@ -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;

[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?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/alTlW8TmTXLocWKP@hostpc?part=1

Re: [PATCH v2] gpu: buddy: avoid repeated builds of root dfs when alloc range

[Zhaoyu Liu]

On Mon, Jul 13, 2026 at 01:31:31PM +0000, sashiko-bot@kernel.org wrote:
> 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.
> --

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

> 
> --- Patch [1]: [PATCH v2] gpu: buddy: avoid repeated builds of root dfs when alloc range ---
> commit 87b87afa0112d6b6bc23de2294a961d8ef1fb83e
> Author: Zhaoyu Liu <liuzhaoyu.zackary@picoheart.com>
> 
> 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.
> 
> > diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> > index 3c73ae87f3c5b..72f521c51b3fa 100644
> > --- a/drivers/gpu/buddy.c
> > +++ b/drivers/gpu/buddy.c
> 
> [ ... ]
> 
> > @@ -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;
> 
> [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?
> 
> -- 
> Sashiko AI review · https://sashiko.dev/#/patchset/alTlW8TmTXLocWKP@hostpc?part=1