[PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees
Arunpravin Paneer Selvam
arunpravin.paneerselvam at amd.com
Wed Aug 20 12:56:44 UTC 2025
Hi Matthew,
On 8/14/2025 4:41 PM, Matthew Auld wrote:
> On 24/07/2025 11:46, 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.
>>
>> Signed-off-by: Arunpravin Paneer Selvam
>> <Arunpravin.PaneerSelvam at amd.com>
>> Suggested-by: Matthew Auld <matthew.auld at intel.com>
>> ---
>> drivers/gpu/drm/drm_buddy.c | 316 ++++++++++++++++++++++--------------
>> include/drm/drm_buddy.h | 15 +-
>> 2 files changed, 204 insertions(+), 127 deletions(-)
>>
>> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
>> index 19e9773b41be..0ffb68474b83 100644
>> --- a/drivers/gpu/drm/drm_buddy.c
>> +++ b/drivers/gpu/drm/drm_buddy.c
>> @@ -43,27 +43,84 @@ 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->clear_tree[order];
>> + else
>> + return &mm->dirty_tree[order];
>> +}
>> +
>> +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)
>
> Do we need all these double underscores?
Not required, we can remove it.
>
>> +{
>> + return (flags & DRM_BUDDY_CLEAR_ALLOCATION) ? CLEAR_TREE :
>> DIRTY_TREE;
>> +}
>> +
>> +static inline struct drm_buddy_block *
>> +rbtree_get_entry(struct rb_node *node)
>> +{
>> + return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL;
>> +}
>> +
>> +static inline struct drm_buddy_block *
>> +rbtree_prev_entry(struct rb_node *node)
>> +{
>> + return rbtree_get_entry(rb_prev(node));
>> +}
>> +
>> +static inline struct drm_buddy_block *
>> +rbtree_first_entry(struct rb_root *root)
>> +{
>> + return rbtree_get_entry(rb_first(root));
>> +}
>> +
>> +static inline struct drm_buddy_block *
>> +rbtree_last_entry(struct rb_root *root)
>> +{
>> + return rbtree_get_entry(rb_last(root));
>> +}
>> +
>> +static inline bool rbtree_is_empty(struct rb_root *root)
>> +{
>> + return RB_EMPTY_ROOT(root);
>> +}
>
> Just wondering if these should have less generic names?
>
> rb_tree_first_free_block()
> rb_tree_last_free_block()
> ...
Yes, I will modify to have less generic names.
>
>> +
>> 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_entry(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;
>> }
>> + block->tree = tree;
>> +
>> rb_link_node(&block->rb, parent, link);
>> rb_insert_color(&block->rb, root);
>> }
>> @@ -71,27 +128,15 @@ 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;
>> - root = &mm->free_tree[drm_buddy_block_order(block)];
>> + root = __get_root(mm, order, block->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;
>> @@ -114,10 +159,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,
>> @@ -212,53 +261,52 @@ 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() {
>> + 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_entry_reverse_safe(block, prev_block,
>> &mm->free_tree[i], rb) {
>> - struct drm_buddy_block *buddy;
>> - u64 block_start, block_end;
>> + for_each_rb_entry_reverse_safe(block, prev_block, root,
>> rb) {
>> + struct drm_buddy_block *buddy;
>> + u64 block_start, block_end;
>> - if (RB_EMPTY_NODE(&block->rb))
>> - break;
>> + if (RB_EMPTY_NODE(&block->rb))
>> + break;
>> - 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_entry(root))
>> + prev_block =
>> rbtree_prev_entry(&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;
>> + }
>> }
>> }
>> @@ -301,14 +349,22 @@ 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)
>> + mm->clear_tree = kmalloc_array(mm->max_order + 1,
>> + sizeof(struct rb_root),
>> + GFP_KERNEL);
>> + if (!mm->clear_tree)
>> + return -ENOMEM;
>> +
>> + mm->dirty_tree = kmalloc_array(mm->max_order + 1,
>> + sizeof(struct rb_root),
>> + GFP_KERNEL);
>> + if (!mm->dirty_tree)
>
> goto out_free_tree
>
>> return -ENOMEM;
>> - for (i = 0; i <= mm->max_order; ++i)
>> - mm->free_tree[i] = RB_ROOT;
>> + for (i = 0; i <= mm->max_order; ++i) {
>> + mm->clear_tree[i] = RB_ROOT;
>> + mm->dirty_tree[i] = RB_ROOT;
>> + }
>> mm->n_roots = hweight64(size);
>> @@ -356,7 +412,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);
>> + kfree(mm->clear_tree);
>> + kfree(mm->dirty_tree);
>> return -ENOMEM;
>> }
>> EXPORT_SYMBOL(drm_buddy_init);
>> @@ -393,7 +450,8 @@ void drm_buddy_fini(struct drm_buddy *mm)
>> WARN_ON(mm->avail != mm->size);
>> kfree(mm->roots);
>> - kfree(mm->free_tree);
>> + kfree(mm->clear_tree);
>> + kfree(mm->dirty_tree);
>> }
>> EXPORT_SYMBOL(drm_buddy_fini);
>> @@ -417,15 +475,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;
>> @@ -632,26 +690,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_entry_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_entry(root);
>> + if (!block)
>> continue;
>> -
>> - block = tmp_block;
>> - break;
>> }
>> - if (!block)
>> - continue;
>> -
>> if (!max_block) {
>> max_block = block;
>> continue;
>> @@ -672,36 +726,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_entry_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)) {
>> + block = rbtree_last_entry(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)) {
>> + block = rbtree_last_entry(root);
>> if (block)
>> break;
>> }
>> @@ -859,34 +915,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_entry_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() {
>> + struct rb_root *root = __get_root(mm, order, tree);
>> +
>> + for_each_rb_entry_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;
>> @@ -1198,11 +1259,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_entry(block, &mm->free_tree[order], rb) {
>> - BUG_ON(!drm_buddy_block_is_free(block));
>> - count++;
>> + for_each_free_tree() {
>> + root = __get_root(mm, order, tree);
>> +
>> + for_each_rb_entry(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 a64d108a33b7..afaf62ee05e1 100644
>> --- a/include/drm/drm_buddy.h
>> +++ b/include/drm/drm_buddy.h
>> @@ -14,6 +14,11 @@
>> #include <drm/drm_print.h>
>> +enum free_tree {
>> + CLEAR_TREE = 0,
>> + DIRTY_TREE,
>> +};
>> +
>> #define range_overflows(start, size, max) ({ \
>> typeof(start) start__ = (start); \
>> typeof(size) size__ = (size); \
>> @@ -23,6 +28,9 @@
>> start__ >= max__ || size__ > max__ - start__; \
>> })
>> +#define for_each_free_tree() \
>
> I think rather give this an explicit 'tree' argument? Having it hidden
> is harder to read IMO.
Sure, will add 'tree' argument to the macro.
>
>> + for (enum free_tree tree = CLEAR_TREE; tree <= DIRTY_TREE; tree++)
>> +
>> /*
>> * for_each_rb_entry() - iterate over an RB tree in order
>> * @pos: the struct type * to use as a loop cursor
>> @@ -89,9 +97,11 @@ struct drm_buddy_block {
>> * a list, if so desired. As soon as the block is freed with
>> * drm_buddy_free* ownership is given back to the mm.
>> */
>> - struct rb_node rb;
>> struct list_head link;
>> struct list_head tmp_link;
>> +
>> + enum free_tree tree;
>
> We also have the existing dirty/free bit in the block itself. Would it
> make sense to re-use that instead, if possible?
Yes, we can re-use the existing dirty/free bit in the block. I will
remove this field.
>
>> + struct rb_node rb;
>> };
>> /* Order-zero must be at least SZ_4K */
>> @@ -105,7 +115,8 @@ struct drm_buddy_block {
>> */
>> struct drm_buddy {
>> /* Maintain a free list for each order. */
>> - struct rb_root *free_tree;
>> + struct rb_root *clear_tree;
>> + struct rb_root *dirty_tree;
>
> Could potentially make this something like:
>
> struct rb_root free_trees[DIRTY_TREE + 1]
>
> Or define DIRTY_TREE + 1 as the last value in the enum and give it a
> special name. We can then just use the enum as the index directly,
> which might be cleaner?
yeah, then we should access the rb_root of a specific order by
free_trees[tree][order].
Regards,
Arun.
>
>> /*
>> * Maintain explicit binary tree(s) to track the allocation of the
>
More information about the amd-gfx
mailing list