gpu/buddy: Track per-order free blocks with a scoreboard

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.

v3: Update after introducing __gpu_buddy_undo_splits() helper

v2: Update after fix for use-after-free in split_block() call sites

Assisted-by: GitHub Copilot:claude-sonnet-4.6
Reviewed-by: Matthew Auld <matthew.auld@intel.com>
Link: https://lore.kernel.org/r/20260522092600.32818-5-francois.dugast@intel.com
Signed-off-by: Francois Dugast <francois.dugast@intel.com>

1 files changed, 7 insertions, 0 deletions

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;