Re: [PATCH v2 2/3] gpu/buddy: Track per-order free blocks with a scoreboard

[Matthew Auld <matthew.auld@intel.com>]

On 11/05/2026 17:41, Francois Dugast wrote:
> Reporting per-order free block counts in drm_buddy_print() currently
> requires walking all rbtrees, which is O(n) over the total number of
> free blocks and holds the allocator lock for the duration. This becomes
> expensive on large VRAM heaps with many small free fragments.
> 
> Maintain a free_scoreboard[] array indexed by order instead, so that
> the count for any order is always available in O(1). The scoreboard is
> kept accurate by hooking into the four places where a block's free state
> changes: mark_free(), mark_allocated(), mark_split(), and the sites in
> __gpu_buddy_free(), __force_merge(), and the four err_undo paths that
> call rbtree_remove() directly on free blocks without going through
> mark_*().
> 
> The print functions are simplified as a result: the rbtree traversal
> is replaced by a direct array lookup.
> 
> v2: Update after fix for use-after-free in split_block() call sites
> 
> Signed-off-by: Francois Dugast <francois.dugast@intel.com>
> Assisted-by: GitHub Copilot:claude-sonnet-4.6
> ---
>   drivers/gpu/buddy.c         | 39 +++++++++++++++++++++++--------------
>   drivers/gpu/drm/drm_buddy.c | 16 ++-------------
>   include/linux/gpu_buddy.h   |  7 +++++++
>   3 files changed, 33 insertions(+), 29 deletions(-)
> 
> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> index dac2027bb64a..01247e3201fb 100644
> --- a/drivers/gpu/buddy.c
> +++ b/drivers/gpu/buddy.c
> @@ -193,6 +193,8 @@ static void mark_allocated(struct gpu_buddy *mm,
>   	block->header &= ~GPU_BUDDY_HEADER_STATE;
>   	block->header |= GPU_BUDDY_ALLOCATED;
>   
> +	mm->free_scoreboard[gpu_buddy_block_order(block)]--;
> +
>   	rbtree_remove(mm, block);
>   }
>   
> @@ -204,6 +206,8 @@ static void mark_free(struct gpu_buddy *mm,
>   	block->header &= ~GPU_BUDDY_HEADER_STATE;
>   	block->header |= GPU_BUDDY_FREE;
>   
> +	mm->free_scoreboard[gpu_buddy_block_order(block)]++;
> +
>   	tree = get_block_tree(block);
>   	rbtree_insert(mm, block, tree);
>   }
> @@ -214,6 +218,8 @@ static void mark_split(struct gpu_buddy *mm,
>   	block->header &= ~GPU_BUDDY_HEADER_STATE;
>   	block->header |= GPU_BUDDY_SPLIT;
>   
> +	mm->free_scoreboard[gpu_buddy_block_order(block)]--;
> +
>   	rbtree_remove(mm, block);
>   }
>   
> @@ -271,6 +277,7 @@ static unsigned int __gpu_buddy_free(struct gpu_buddy *mm,
>   		}
>   
>   		rbtree_remove(mm, buddy);
> +		mm->free_scoreboard[gpu_buddy_block_order(buddy)]--;
>   		if (force_merge && gpu_buddy_block_is_clear(buddy))
>   			mm->clear_avail -= gpu_buddy_block_size(mm, buddy);
>   
> @@ -335,6 +342,7 @@ static int __force_merge(struct gpu_buddy *mm,
>   					iter = rb_prev(iter);
>   
>   				rbtree_remove(mm, block);
> +				mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>   				if (gpu_buddy_block_is_clear(block))
>   					mm->clear_avail -= gpu_buddy_block_size(mm, block);
>   
> @@ -384,11 +392,17 @@ int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size)
>   
>   	BUG_ON(mm->max_order > GPU_BUDDY_MAX_ORDER);
>   
> +	mm->free_scoreboard = kcalloc(mm->max_order + 1,
> +				      sizeof(*mm->free_scoreboard),
> +				      GFP_KERNEL);
> +	if (!mm->free_scoreboard)
> +		return -ENOMEM;
> +
>   	mm->free_trees = kmalloc_array(GPU_BUDDY_MAX_FREE_TREES,
>   				       sizeof(*mm->free_trees),
>   				       GFP_KERNEL);
>   	if (!mm->free_trees)
> -		return -ENOMEM;
> +		goto out_free_scoreboard;
>   
>   	for_each_free_tree(i) {
>   		mm->free_trees[i] = kmalloc_array(mm->max_order + 1,
> @@ -450,6 +464,8 @@ int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size)
>   	while (i--)
>   		kfree(mm->free_trees[i]);
>   	kfree(mm->free_trees);
> +out_free_scoreboard:
> +	kfree(mm->free_scoreboard);
>   	return -ENOMEM;
>   }
>   EXPORT_SYMBOL(gpu_buddy_init);
> @@ -488,6 +504,7 @@ void gpu_buddy_fini(struct gpu_buddy *mm)
>   		kfree(mm->free_trees[i]);
>   	kfree(mm->free_trees);
>   	kfree(mm->roots);
> +	kfree(mm->free_scoreboard);
>   }
>   EXPORT_SYMBOL(gpu_buddy_fini);
>   
> @@ -739,6 +756,7 @@ __alloc_range_bias(struct gpu_buddy *mm,
>   	    (gpu_buddy_block_is_free(block) &&
>   	     gpu_buddy_block_is_free(buddy))) {
>   		rbtree_remove(mm, block);
> +		mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>   		__gpu_buddy_free(mm, block, false);

Wondering if it now makes sense to refactor this and consolidate in one 
place? Maybe something like:

__gpu_buddy_undo_splits()
{
	if (is_free(block) && is_free(buddy) {
             rbtree_remove(mm, block);
             mm->free_scoreboard[gpu_buddy_block_order(block)]--;
             __gpu_buddy_free(mm, block, false);
         }
}

>   	}
>   	return ERR_PTR(err);
> @@ -851,6 +869,7 @@ alloc_from_freetree(struct gpu_buddy *mm,
>   err_undo:
>   	if (tmp != order) {
>   		rbtree_remove(mm, block);
> +		mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>   		__gpu_buddy_free(mm, block, false);
>   	}
>   	return ERR_PTR(err);
> @@ -974,6 +993,7 @@ gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm,
>   	    (gpu_buddy_block_is_free(block) &&
>   	     gpu_buddy_block_is_free(buddy))) {
>   		rbtree_remove(mm, block);
> +		mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>   		__gpu_buddy_free(mm, block, false);
>   	}
>   	return ERR_PTR(err);
> @@ -1062,6 +1082,7 @@ static int __alloc_range(struct gpu_buddy *mm,
>   	    (gpu_buddy_block_is_free(block) &&
>   	     gpu_buddy_block_is_free(buddy))) {
>   		rbtree_remove(mm, block);
> +		mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>   		__gpu_buddy_free(mm, block, false);
>   	}
>   
> @@ -1498,21 +1519,9 @@ void gpu_buddy_print(struct gpu_buddy *mm)
>   		mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20);
>   
>   	for (order = mm->max_order; order >= 0; order--) {
> -		struct gpu_buddy_block *block, *tmp;
> -		struct rb_root *root;
> -		u64 count = 0, free;
> -		unsigned int tree;
> -
> -		for_each_free_tree(tree) {
> -			root = &mm->free_trees[tree][order];
> -
> -			rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) {
> -				BUG_ON(!gpu_buddy_block_is_free(block));
> -				count++;
> -			}
> -		}
> +		u64 count = mm->free_scoreboard[order];
> +		u64 free = count * (mm->chunk_size << order);
>   
> -		free = count * (mm->chunk_size << order);
>   		if (free < SZ_1M)
>   			pr_info("order-%2d free: %8llu KiB, blocks: %llu\n",
>   				order, free >> 10, count);
> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
> index faa025498de4..eef995e08a37 100644
> --- a/drivers/gpu/drm/drm_buddy.c
> +++ b/drivers/gpu/drm/drm_buddy.c
> @@ -47,23 +47,11 @@ void drm_buddy_print(struct gpu_buddy *mm, struct drm_printer *p)
>   		   mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20);
>   
>   	for (order = mm->max_order; order >= 0; order--) {
> -		struct gpu_buddy_block *block, *tmp;
> -		struct rb_root *root;
> -		u64 count = 0, free;
> -		unsigned int tree;
> -
> -		for_each_free_tree(tree) {
> -			root = &mm->free_trees[tree][order];
> -
> -			rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) {
> -				BUG_ON(!gpu_buddy_block_is_free(block));
> -				count++;
> -			}
> -		}
> +		u64 count = mm->free_scoreboard[order];
> +		u64 free = count * (mm->chunk_size << order);
>   
>   		drm_printf(p, "order-%2d ", order);
>   
> -		free = count * (mm->chunk_size << order);
>   		if (free < SZ_1M)
>   			drm_printf(p, "free: %8llu KiB", free >> 10);
>   		else
> diff --git a/include/linux/gpu_buddy.h b/include/linux/gpu_buddy.h
> index 71941a039648..a28f7d7637ca 100644
> --- a/include/linux/gpu_buddy.h
> +++ b/include/linux/gpu_buddy.h
> @@ -173,6 +173,13 @@ struct gpu_buddy {
>   	 * that fits in the remaining space.
>   	 */
>   	struct gpu_buddy_block **roots;
> +	/*
> +	 * Per-order free block scoreboard: free_scoreboard[order] holds the
> +	 * number of blocks of that order currently in the free state.
> +	 * Incremented in mark_free(), decremented wherever rbtree_remove() is
> +	 * called on a free block.
> +	 */
> +	u64 *free_scoreboard;
>   /* public: */
>   	unsigned int n_roots;
>   	unsigned int max_order;