On Thu, 28 Aug 2025, Arunpravin Paneer Selvam <arunpravin.paneersel...@amd.com>
wrote:
> Maintain two separate RB trees per order - one for clear (zeroed) blocks
> and another for dirty (uncleared) blocks. This separation improves
> code clarity and makes it more obvious which tree is being searched
> during allocation. It also improves scalability and efficiency when
> searching for a specific type of block, avoiding unnecessary checks
> and making the allocator more predictable under fragmentation.
>
> The changes have been validated using the existing drm_buddy_test
> KUnit test cases, along with selected graphics workloads,
> to ensure correctness and avoid regressions.
>
> v2: Missed adding the suggested-by tag. Added it in v2.
>
> v3(Matthew):
> - Remove the double underscores from the internal functions.
> - Rename the internal functions to have less generic names.
> - Fix the error handling code.
> - Pass tree argument for the tree macro.
> - Use the existing dirty/free bit instead of new tree field.
> - Make free_trees[] instead of clear_tree and dirty_tree for
> more cleaner approach.
>
> v4:
> - A bug was reported by Intel CI and it is fixed by
> Matthew Auld.
> - Replace the get_root function with
> &mm->free_trees[tree][order] (Matthew)
> - Remove the unnecessary rbtree_is_empty() check (Matthew)
> - Remove the unnecessary get_tree_for_flags() function.
> - Rename get_tree_for_block() name with get_block_tree() for more
> clarity.
>
> Signed-off-by: Arunpravin Paneer Selvam <arunpravin.paneersel...@amd.com>
> Suggested-by: Matthew Auld <matthew.a...@intel.com>
> Closes: https://gitlab.freedesktop.org/drm/amd/-/issues/4260
> ---
> drivers/gpu/drm/drm_buddy.c | 322 +++++++++++++++++++++---------------
> include/drm/drm_buddy.h | 8 +-
> 2 files changed, 192 insertions(+), 138 deletions(-)
>
> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
> index 01ae984340cc..06e90020177f 100644
> --- a/drivers/gpu/drm/drm_buddy.c
> +++ b/drivers/gpu/drm/drm_buddy.c
> @@ -14,6 +14,9 @@
>
> static struct kmem_cache *slab_blocks;
>
> +#define for_each_free_tree(tree) \
> + for ((tree) = CLEAR_TREE; (tree) < MAX_FREE_TREES; (tree)++)
IMO better to just use 0 and ARRAY_SIZE() for the limits, here and
everywhere. It's just that there's no connection between the enum and
how its used anyway.
> +
> /*
> * for_each_rb_free_block() - iterate over an RB tree in order
> * @pos: the struct type * to use as a loop cursor
> @@ -78,22 +81,60 @@ static void drm_block_free(struct drm_buddy *mm,
> kmem_cache_free(slab_blocks, block);
> }
>
> +static inline enum free_tree
Please don't use static inline in .c files. Just let the compiler do
what it deems best.
> +get_block_tree(struct drm_buddy_block *block)
> +{
> + return drm_buddy_block_is_clear(block) ? CLEAR_TREE : DIRTY_TREE;
> +}
> +
> +static inline struct drm_buddy_block *
> +rbtree_get_free_block(struct rb_node *node)
> +{
> + return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL;
> +}
> +
> +static inline struct drm_buddy_block *
> +rbtree_prev_free_block(struct rb_node *node)
> +{
> + return rbtree_get_free_block(rb_prev(node));
> +}
> +
> +static inline struct drm_buddy_block *
> +rbtree_first_free_block(struct rb_root *root)
> +{
> + return rbtree_get_free_block(rb_first(root));
> +}
> +
> +static inline struct drm_buddy_block *
> +rbtree_last_free_block(struct rb_root *root)
> +{
> + return rbtree_get_free_block(rb_last(root));
> +}
> +
> +static inline bool rbtree_is_empty(struct rb_root *root)
> +{
> + return RB_EMPTY_ROOT(root);
> +}
> +
> static void rbtree_insert(struct drm_buddy *mm,
> - struct drm_buddy_block *block)
> + struct drm_buddy_block *block,
> + enum free_tree tree)
> {
> - struct rb_root *root = &mm->free_tree[drm_buddy_block_order(block)];
> - struct rb_node **link = &root->rb_node;
> - struct rb_node *parent = NULL;
> + struct rb_node **link, *parent = NULL;
> struct drm_buddy_block *node;
> - u64 offset;
> + struct rb_root *root;
> + unsigned int order;
> +
> + order = drm_buddy_block_order(block);
>
> - offset = drm_buddy_block_offset(block);
> + root = &mm->free_trees[tree][order];
> + link = &root->rb_node;
>
> while (*link) {
> parent = *link;
> - node = rb_entry(parent, struct drm_buddy_block, rb);
> + node = rbtree_get_free_block(parent);
>
> - if (offset < drm_buddy_block_offset(node))
> + if (drm_buddy_block_offset(block) <
> drm_buddy_block_offset(node))
> link = &parent->rb_left;
> else
> link = &parent->rb_right;
> @@ -106,27 +147,17 @@ static void rbtree_insert(struct drm_buddy *mm,
> static void rbtree_remove(struct drm_buddy *mm,
> struct drm_buddy_block *block)
> {
> + unsigned int order = drm_buddy_block_order(block);
> struct rb_root *root;
> + enum free_tree tree;
>
> - root = &mm->free_tree[drm_buddy_block_order(block)];
> - rb_erase(&block->rb, root);
> + tree = get_block_tree(block);
> + root = &mm->free_trees[tree][order];
>
> + rb_erase(&block->rb, root);
> RB_CLEAR_NODE(&block->rb);
> }
>
> -static inline struct drm_buddy_block *
> -rbtree_last_entry(struct drm_buddy *mm, unsigned int order)
> -{
> - struct rb_node *node = rb_last(&mm->free_tree[order]);
> -
> - return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL;
> -}
> -
> -static bool rbtree_is_empty(struct drm_buddy *mm, unsigned int order)
> -{
> - return RB_EMPTY_ROOT(&mm->free_tree[order]);
> -}
> -
> static void clear_reset(struct drm_buddy_block *block)
> {
> block->header &= ~DRM_BUDDY_HEADER_CLEAR;
> @@ -149,10 +180,13 @@ static void mark_allocated(struct drm_buddy *mm,
> static void mark_free(struct drm_buddy *mm,
> struct drm_buddy_block *block)
> {
> + enum free_tree tree;
> +
> block->header &= ~DRM_BUDDY_HEADER_STATE;
> block->header |= DRM_BUDDY_FREE;
>
> - rbtree_insert(mm, block);
> + tree = get_block_tree(block);
> + rbtree_insert(mm, block, tree);
> }
>
> static void mark_split(struct drm_buddy *mm,
> @@ -238,6 +272,7 @@ static int __force_merge(struct drm_buddy *mm,
> u64 end,
> unsigned int min_order)
> {
> + enum free_tree tree;
> unsigned int order;
> int i;
>
> @@ -247,50 +282,49 @@ static int __force_merge(struct drm_buddy *mm,
> if (min_order > mm->max_order)
> return -EINVAL;
>
> - for (i = min_order - 1; i >= 0; i--) {
> - struct drm_buddy_block *block, *prev_block, *first_block;
> + for_each_free_tree(tree) {
> + for (i = min_order - 1; i >= 0; i--) {
> + struct rb_root *root = &mm->free_trees[tree][i];
> + struct drm_buddy_block *block, *prev_block;
>
> - first_block = rb_entry(rb_first(&mm->free_tree[i]), struct
> drm_buddy_block, rb);
> + for_each_rb_free_block_reverse_safe(block, prev_block,
> root, rb) {
> + struct drm_buddy_block *buddy;
> + u64 block_start, block_end;
>
> - for_each_rb_free_block_reverse_safe(block, prev_block,
> &mm->free_tree[i], rb) {
> - struct drm_buddy_block *buddy;
> - u64 block_start, block_end;
> -
> - if (!block->parent)
> - continue;
> + if (!block->parent)
> + continue;
>
> - block_start = drm_buddy_block_offset(block);
> - block_end = block_start + drm_buddy_block_size(mm,
> block) - 1;
> + block_start = drm_buddy_block_offset(block);
> + block_end = block_start +
> drm_buddy_block_size(mm, block) - 1;
>
> - if (!contains(start, end, block_start, block_end))
> - continue;
> + if (!contains(start, end, block_start,
> block_end))
> + continue;
>
> - buddy = __get_buddy(block);
> - if (!drm_buddy_block_is_free(buddy))
> - continue;
> + buddy = __get_buddy(block);
> + if (!drm_buddy_block_is_free(buddy))
> + continue;
>
> - WARN_ON(drm_buddy_block_is_clear(block) ==
> - drm_buddy_block_is_clear(buddy));
> + WARN_ON(drm_buddy_block_is_clear(block) ==
> + drm_buddy_block_is_clear(buddy));
>
> - /*
> - * If the prev block is same as buddy, don't access the
> - * block in the next iteration as we would free the
> - * buddy block as part of the free function.
> - */
> - if (prev_block && prev_block == buddy) {
> - if (prev_block != first_block)
> - prev_block =
> rb_entry(rb_prev(&prev_block->rb),
> - struct
> drm_buddy_block,
> - rb);
> - }
> + /*
> + * If the prev block is same as buddy, don't
> access the
> + * block in the next iteration as we would free
> the
> + * buddy block as part of the free function.
> + */
> + if (prev_block && prev_block == buddy) {
> + if (prev_block !=
> rbtree_first_free_block(root))
> + prev_block =
> rbtree_prev_free_block(&prev_block->rb);
> + }
>
> - rbtree_remove(mm, block);
> - if (drm_buddy_block_is_clear(block))
> - mm->clear_avail -= drm_buddy_block_size(mm,
> block);
> + rbtree_remove(mm, block);
> + if (drm_buddy_block_is_clear(block))
> + mm->clear_avail -=
> drm_buddy_block_size(mm, block);
>
> - order = __drm_buddy_free(mm, block, true);
> - if (order >= min_order)
> - return 0;
> + order = __drm_buddy_free(mm, block, true);
> + if (order >= min_order)
> + return 0;
> + }
> }
> }
>
> @@ -311,7 +345,7 @@ static int __force_merge(struct drm_buddy *mm,
> */
> int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
> {
> - unsigned int i;
> + unsigned int i, j;
> u64 offset;
>
> if (size < chunk_size)
> @@ -333,14 +367,16 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64
> chunk_size)
>
> BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
>
> - mm->free_tree = kmalloc_array(mm->max_order + 1,
> - sizeof(struct rb_root),
> - GFP_KERNEL);
> - if (!mm->free_tree)
> - return -ENOMEM;
> + for (i = 0; i < MAX_FREE_TREES; i++) {
> + mm->free_trees[i] = kmalloc_array(mm->max_order + 1,
> + sizeof(struct rb_root),
> + GFP_KERNEL);
> + if (!mm->free_trees[i])
> + goto out_free_tree;
>
> - for (i = 0; i <= mm->max_order; ++i)
> - mm->free_tree[i] = RB_ROOT;
> + for (j = 0; j <= mm->max_order; ++j)
> + mm->free_trees[i][j] = RB_ROOT;
> + }
>
> mm->n_roots = hweight64(size);
>
> @@ -388,7 +424,8 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64
> chunk_size)
> drm_block_free(mm, mm->roots[i]);
> kfree(mm->roots);
> out_free_tree:
> - kfree(mm->free_tree);
> + while (i--)
> + kfree(mm->free_trees[i]);
> return -ENOMEM;
> }
> EXPORT_SYMBOL(drm_buddy_init);
> @@ -424,8 +461,9 @@ void drm_buddy_fini(struct drm_buddy *mm)
>
> WARN_ON(mm->avail != mm->size);
>
> + for (i = 0; i < MAX_FREE_TREES; i++)
> + kfree(mm->free_trees[i]);
> kfree(mm->roots);
> - kfree(mm->free_tree);
> }
> EXPORT_SYMBOL(drm_buddy_fini);
>
> @@ -449,8 +487,7 @@ static int split_block(struct drm_buddy *mm,
> return -ENOMEM;
> }
>
> - mark_free(mm, block->left);
> - mark_free(mm, block->right);
> + mark_split(mm, block);
>
> if (drm_buddy_block_is_clear(block)) {
> mark_cleared(block->left);
> @@ -458,7 +495,8 @@ static int split_block(struct drm_buddy *mm,
> clear_reset(block);
> }
>
> - mark_split(mm, block);
> + mark_free(mm, block->left);
> + mark_free(mm, block->right);
>
> return 0;
> }
> @@ -491,6 +529,7 @@ EXPORT_SYMBOL(drm_get_buddy);
> */
> void drm_buddy_reset_clear(struct drm_buddy *mm, bool is_clear)
> {
> + enum free_tree src_tree, dst_tree;
> u64 root_size, size, start;
> unsigned int order;
> int i;
> @@ -505,19 +544,24 @@ void drm_buddy_reset_clear(struct drm_buddy *mm, bool
> is_clear)
> size -= root_size;
> }
>
> + src_tree = is_clear ? DIRTY_TREE : CLEAR_TREE;
> + dst_tree = is_clear ? CLEAR_TREE : DIRTY_TREE;
> +
> for (i = 0; i <= mm->max_order; ++i) {
> + struct rb_root *root = &mm->free_trees[src_tree][i];
> struct drm_buddy_block *block;
>
> - for_each_rb_free_block_reverse(block, &mm->free_tree[i], rb) {
> - if (is_clear != drm_buddy_block_is_clear(block)) {
> - if (is_clear) {
> - mark_cleared(block);
> - mm->clear_avail +=
> drm_buddy_block_size(mm, block);
> - } else {
> - clear_reset(block);
> - mm->clear_avail -=
> drm_buddy_block_size(mm, block);
> - }
> + for_each_rb_free_block_reverse(block, root, rb) {
> + rbtree_remove(mm, block);
> + if (is_clear) {
> + mark_cleared(block);
> + mm->clear_avail += drm_buddy_block_size(mm,
> block);
> + } else {
> + clear_reset(block);
> + mm->clear_avail -= drm_buddy_block_size(mm,
> block);
> }
> +
> + rbtree_insert(mm, block, dst_tree);
> }
> }
> }
> @@ -707,23 +751,17 @@ __drm_buddy_alloc_range_bias(struct drm_buddy *mm,
> }
>
> static struct drm_buddy_block *
> -get_maxblock(struct drm_buddy *mm, unsigned int order,
> - unsigned long flags)
> +get_maxblock(struct drm_buddy *mm,
> + unsigned int order,
> + enum free_tree tree)
> {
> struct drm_buddy_block *max_block = NULL, *block = NULL;
> + struct rb_root *root;
> unsigned int i;
>
> for (i = order; i <= mm->max_order; ++i) {
> - struct drm_buddy_block *tmp_block;
> -
> - for_each_rb_free_block_reverse(tmp_block, &mm->free_tree[i],
> rb) {
> - if (block_incompatible(tmp_block, flags))
> - continue;
> -
> - block = tmp_block;
> - break;
> - }
> -
> + root = &mm->free_trees[tree][i];
> + block = rbtree_last_free_block(root);
> if (!block)
> continue;
>
> @@ -747,39 +785,37 @@ alloc_from_freetree(struct drm_buddy *mm,
> unsigned long flags)
> {
> struct drm_buddy_block *block = NULL;
> + struct rb_root *root;
> + enum free_tree tree;
> unsigned int tmp;
> int err;
>
> + tree = (flags & DRM_BUDDY_CLEAR_ALLOCATION) ? CLEAR_TREE : DIRTY_TREE;
> +
> if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) {
> - block = get_maxblock(mm, order, flags);
> + block = get_maxblock(mm, order, tree);
> if (block)
> /* Store the obtained block order */
> tmp = drm_buddy_block_order(block);
> } else {
> for (tmp = order; tmp <= mm->max_order; ++tmp) {
> - struct drm_buddy_block *tmp_block;
> -
> - for_each_rb_free_block_reverse(tmp_block,
> &mm->free_tree[tmp], rb) {
> - if (block_incompatible(tmp_block, flags))
> - continue;
> -
> - block = tmp_block;
> - break;
> - }
> -
> + /* Get RB tree root for this order and tree */
> + root = &mm->free_trees[tree][tmp];
> + block = rbtree_last_free_block(root);
> if (block)
> break;
> }
> }
>
> if (!block) {
> - /* Fallback method */
> + /* Try allocating from the other tree */
> + tree = (tree == CLEAR_TREE) ? DIRTY_TREE : CLEAR_TREE;
> +
> for (tmp = order; tmp <= mm->max_order; ++tmp) {
> - if (!rbtree_is_empty(mm, tmp)) {
> - block = rbtree_last_entry(mm, tmp);
> - if (block)
> - break;
> - }
> + root = &mm->free_trees[tree][tmp];
> + block = rbtree_last_free_block(root);
> + if (block)
> + break;
> }
>
> if (!block)
> @@ -923,6 +959,7 @@ static int __alloc_contig_try_harder(struct drm_buddy *mm,
> u64 rhs_offset, lhs_offset, lhs_size, filled;
> struct drm_buddy_block *block;
> LIST_HEAD(blocks_lhs);
> + enum free_tree tree;
> unsigned long pages;
> unsigned int order;
> u64 modify_size;
> @@ -934,34 +971,39 @@ static int __alloc_contig_try_harder(struct drm_buddy
> *mm,
> if (order == 0)
> return -ENOSPC;
>
> - if (rbtree_is_empty(mm, order))
> + if (rbtree_is_empty(&mm->free_trees[CLEAR_TREE][order]) &&
> + rbtree_is_empty(&mm->free_trees[DIRTY_TREE][order]))
> return -ENOSPC;
>
> - for_each_rb_free_block_reverse(block, &mm->free_tree[order], rb) {
> - /* Allocate blocks traversing RHS */
> - rhs_offset = drm_buddy_block_offset(block);
> - err = __drm_buddy_alloc_range(mm, rhs_offset, size,
> - &filled, blocks);
> - if (!err || err != -ENOSPC)
> - return err;
> -
> - lhs_size = max((size - filled), min_block_size);
> - if (!IS_ALIGNED(lhs_size, min_block_size))
> - lhs_size = round_up(lhs_size, min_block_size);
> -
> - /* Allocate blocks traversing LHS */
> - lhs_offset = drm_buddy_block_offset(block) - lhs_size;
> - err = __drm_buddy_alloc_range(mm, lhs_offset, lhs_size,
> - NULL, &blocks_lhs);
> - if (!err) {
> - list_splice(&blocks_lhs, blocks);
> - return 0;
> - } else if (err != -ENOSPC) {
> + for_each_free_tree(tree) {
> + struct rb_root *root = &mm->free_trees[tree][order];
> +
> + for_each_rb_free_block_reverse(block, root, rb) {
> + /* Allocate blocks traversing RHS */
> + rhs_offset = drm_buddy_block_offset(block);
> + err = __drm_buddy_alloc_range(mm, rhs_offset, size,
> + &filled, blocks);
> + if (!err || err != -ENOSPC)
> + return err;
> +
> + lhs_size = max((size - filled), min_block_size);
> + if (!IS_ALIGNED(lhs_size, min_block_size))
> + lhs_size = round_up(lhs_size, min_block_size);
> +
> + /* Allocate blocks traversing LHS */
> + lhs_offset = drm_buddy_block_offset(block) - lhs_size;
> + err = __drm_buddy_alloc_range(mm, lhs_offset, lhs_size,
> + NULL, &blocks_lhs);
> + if (!err) {
> + list_splice(&blocks_lhs, blocks);
> + return 0;
> + } else if (err != -ENOSPC) {
> + drm_buddy_free_list_internal(mm, blocks);
> + return err;
> + }
> + /* Free blocks for the next iteration */
> drm_buddy_free_list_internal(mm, blocks);
> - return err;
> }
> - /* Free blocks for the next iteration */
> - drm_buddy_free_list_internal(mm, blocks);
> }
>
> return -ENOSPC;
> @@ -1266,6 +1308,7 @@ EXPORT_SYMBOL(drm_buddy_block_print);
> */
> void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)
> {
> + enum free_tree tree;
> int order;
>
> drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB,
> clear_free: %lluMiB\n",
> @@ -1273,11 +1316,16 @@ void drm_buddy_print(struct drm_buddy *mm, struct
> drm_printer *p)
>
> for (order = mm->max_order; order >= 0; order--) {
> struct drm_buddy_block *block;
> + struct rb_root *root;
> u64 count = 0, free;
>
> - for_each_rb_free_block(block, &mm->free_tree[order], rb) {
> - BUG_ON(!drm_buddy_block_is_free(block));
> - count++;
> + for_each_free_tree(tree) {
> + root = &mm->free_trees[tree][order];
> +
> + for_each_rb_free_block(block, root, rb) {
> + BUG_ON(!drm_buddy_block_is_free(block));
> + count++;
> + }
> }
>
> drm_printf(p, "order-%2d ", order);
> diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
> index 091823592034..2fc1cc7b78bf 100644
> --- a/include/drm/drm_buddy.h
> +++ b/include/drm/drm_buddy.h
> @@ -14,6 +14,12 @@
>
> #include <drm/drm_print.h>
>
> +enum free_tree {
> + CLEAR_TREE = 0,
> + DIRTY_TREE,
> + MAX_FREE_TREES,
Those are quite generic enum and enumerator names for a very specific
header and usage.
And really this whole enum should be an implementation detail.
> +};
> +
> #define range_overflows(start, size, max) ({ \
> typeof(start) start__ = (start); \
> typeof(size) size__ = (size); \
> @@ -73,7 +79,7 @@ struct drm_buddy_block {
> */
> struct drm_buddy {
> /* Maintain a free list for each order. */
> - struct rb_root *free_tree;
> + struct rb_root *free_trees[MAX_FREE_TREES];
>
> /*
> * Maintain explicit binary tree(s) to track the allocation of the
--
Jani Nikula, Intel
