[PATCH v3 2/2] drm/buddy: Separate clear and dirty free block trees
Arunpravin Paneer Selvam
arunpravin.paneerselvam at amd.com
Mon Aug 25 11:31:49 UTC 2025
On 8/22/2025 5:32 PM, Matthew Auld wrote:
> On 21/08/2025 16:06, Arunpravin Paneer Selvam 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.
>>
>> Signed-off-by: Arunpravin Paneer Selvam
>> <Arunpravin.PaneerSelvam at amd.com>
>> Suggested-by: Matthew Auld <matthew.auld at intel.com>
>> Closes: https://gitlab.freedesktop.org/drm/amd/-/issues/4260
>> ---
>> drivers/gpu/drm/drm_buddy.c | 342 ++++++++++++++++++++++--------------
>> include/drm/drm_buddy.h | 8 +-
>> 2 files changed, 215 insertions(+), 135 deletions(-)
>>
>> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
>> index 92226a46cc2c..f57c384889a9 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)++)
>> +
>> /*
>> * 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,77 @@ static void drm_block_free(struct drm_buddy *mm,
>> kmem_cache_free(slab_blocks, block);
>> }
>> +static inline struct rb_root *
>> +get_root(struct drm_buddy *mm,
>> + unsigned int order,
>> + enum free_tree tree)
>> +{
>> + if (tree == CLEAR_TREE)
>> + return &mm->free_trees[CLEAR_TREE][order];
>> + else
>> + return &mm->free_trees[DIRTY_TREE][order];
>
> I think we can replace this with something like:
>
> return &mm->free_trees[tree][order];
yes. we can replace with the above.
>
>> +}
>> +
>> +static inline enum free_tree
>> +get_tree_for_block(struct drm_buddy_block *block)
>> +{
>> + return drm_buddy_block_is_clear(block) ? CLEAR_TREE : DIRTY_TREE;
>> +}
>> +
>> +static inline enum free_tree
>> +get_tree_for_flags(unsigned long flags)
>> +{
>> + return (flags & DRM_BUDDY_CLEAR_ALLOCATION) ? 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 = get_root(mm, order, tree);
>> + 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 +164,19 @@ 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);
>> + enum free_tree tree;
>> struct rb_root *root;
>> - root = &mm->free_tree[drm_buddy_block_order(block)];
>> + tree = drm_buddy_block_is_clear(block) ?
>> + CLEAR_TREE : DIRTY_TREE;
>> +
>> + root = get_root(mm, order, tree);
>> 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 +199,14 @@ 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_tree_for_block(block);
>> +
>> + rbtree_insert(mm, block, tree);
>> }
>> static void mark_split(struct drm_buddy *mm,
>> @@ -238,6 +292,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 +302,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;
>> -
>> - first_block = rb_entry(rb_first(&mm->free_tree[i]), struct
>> drm_buddy_block, rb);
>> + for_each_free_tree(tree) {
>> + for (i = min_order - 1; i >= 0; i--) {
>> + struct rb_root *root = get_root(mm, i, tree);
>> + struct drm_buddy_block *block, *prev_block;
>> - 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;
>> + for_each_rb_free_block_reverse_safe(block, prev_block,
>> root, 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 +365,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 +387,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 +444,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 +481,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,15 +507,15 @@ static int split_block(struct drm_buddy *mm,
>> return -ENOMEM;
>> }
>> - mark_free(mm, block->left);
>> - mark_free(mm, block->right);
>> -
>> if (drm_buddy_block_is_clear(block)) {
>> mark_cleared(block->left);
>> mark_cleared(block->right);
>> clear_reset(block);
>> }
>> + mark_free(mm, block->left);
>> + mark_free(mm, block->right);
>> +
>> mark_split(mm, block);
>> return 0;
>> @@ -491,6 +549,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 +564,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 = get_root(mm, order, src_tree);
>> 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,26 +771,22 @@ __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))
>> + root = get_root(mm, i, tree);
>> + if (!rbtree_is_empty(root)) {
>> + block = rbtree_last_free_block(root);
>> + if (!block)
>> continue;
>> -
>> - block = tmp_block;
>> - break;
>> }
>> - if (!block)
>> - continue;
>> -
>> if (!max_block) {
>> max_block = block;
>> continue;
>> @@ -747,36 +807,38 @@ 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 = get_tree_for_flags(flags);
>> +
>> 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 = get_root(mm, tmp, tree);
>> + if (!rbtree_is_empty(root)) {
>
> Do we need this check? last_free_block should just return NULL? Or if
> this is somehow a cheaper check, maybe we should move it into the
> helper instead?
Not required. last_free_block will return NULL. I will remove this check.
>
>> + block = rbtree_last_free_block(root);
>> + if (block)
>> + break;
>> }
>> -
>> - 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);
>> + root = get_root(mm, tmp, tree);
>> + if (!rbtree_is_empty(root)) {
>
> Here also.
>
>> + block = rbtree_last_free_block(root);
>> if (block)
>> break;
>> }
>> @@ -923,6 +985,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 +997,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(get_root(mm, order, CLEAR_TREE)) &&
>> + rbtree_is_empty(get_root(mm, order, DIRTY_TREE)))
>> 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 = get_root(mm, order, tree);
>> +
>> + 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 +1334,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 +1342,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 = get_root(mm, order, tree);
>
> Hmm, actually maybe this helper should just give the root (or both)?
> Seems to be what all users want anyway?
Most of the time, we just need to root and the functionality determines
the tree (for example : rbtree_insert() or rbtree_remove()).
May be we can remove the get_root() and use &mm->free_trees[tree][order]
directly in all the places ?
Regards,
Arun.
>
>> +
>> + 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,
>> +};
>> +
>> #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
>
More information about the Intel-gfx
mailing list