Re: [PATCH v7 2/3] drm/buddy: Separate clear and dirty free block trees

On 23/09/2025 10:02, 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.

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.

v5(Jani Nikula):

• Don't use static inline in .c files.
• enum free_tree and enumerator names are quite generic for a header and usage and the whole enum should be an implementation detail.

v6:

• Rewrite the __force_merge() function using the rb_last() and rb_prev().

Cc: stable@vger.kernel.org Fixes: a68c7eaa7a8f ("drm/amdgpu: Enable clear page functionality") Signed-off-by: Arunpravin Paneer Selvam Arunpravin.PaneerSelvam@amd.com Suggested-by: Matthew Auld matthew.auld@intel.com Closes: https://gitlab.freedesktop.org/drm/amd/-/issues/4260

---

drivers/gpu/drm/drm_buddy.c | 321 ++++++++++++++++++++---------------- include/drm/drm_buddy.h | 2 +- 2 files changed, 182 insertions(+), 141 deletions(-)

diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c index 67aa67229cc3..6e12a0b5d5e3 100644 --- a/drivers/gpu/drm/drm_buddy.c +++ b/drivers/gpu/drm/drm_buddy.c @@ -12,9 +12,16 @@ #include <drm/drm_buddy.h> +enum drm_buddy_free_tree {

• DRM_BUDDY_CLEAR_TREE = 0,
• DRM_BUDDY_DIRTY_TREE,
• DRM_BUDDY_MAX_FREE_TREES,

+};

• static struct kmem_cache *slab_blocks;

-#define rbtree_get_free_block(node) rb_entry((node), struct drm_buddy_block, rb) +#define for_each_free_tree(tree) \

• for ((tree) = 0; (tree) < DRM_BUDDY_MAX_FREE_TREES; (tree)++)

Some places seem to open code this? Maybe just drop this or use it everywhere?

static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm, struct drm_buddy_block *parent, @@ -45,6 +52,30 @@ static void drm_block_free(struct drm_buddy *mm, kmem_cache_free(slab_blocks, block); } +static enum drm_buddy_free_tree +get_block_tree(struct drm_buddy_block *block) +{

• return drm_buddy_block_is_clear(block) ?

•       DRM_BUDDY_CLEAR_TREE : DRM_BUDDY_DIRTY_TREE;
  

+}

+static struct drm_buddy_block * +rbtree_get_free_block(const struct rb_node *node) +{

• return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL;

+}

+static struct drm_buddy_block * +rbtree_last_free_block(struct rb_root *root) +{

• return rbtree_get_free_block(rb_last(root));

+}

+static bool rbtree_is_empty(struct rb_root *root) +{

• return RB_EMPTY_ROOT(root);

+}

• static bool drm_buddy_block_offset_less(const struct drm_buddy_block *block, const struct drm_buddy_block *node) {

@@ -59,37 +90,28 @@ static bool rbtree_block_offset_less(struct rb_node *block, } static void rbtree_insert(struct drm_buddy *mm,

• 	  struct drm_buddy_block *block)
  

• 	  struct drm_buddy_block *block,
  

• 	  enum drm_buddy_free_tree tree)
  

  { rb_add(&block->rb,

•       &mm->free_tree[drm_buddy_block_order(block)],
  

•       &mm->free_trees[tree][drm_buddy_block_order(block)],
      rbtree_block_offset_less);
  

  }

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 drm_buddy_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 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;

@@ -112,10 +134,13 @@ static void mark_allocated(struct drm_buddy *mm, static void mark_free(struct drm_buddy *mm, struct drm_buddy_block *block) {

• enum drm_buddy_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, @@ -201,6 +226,7 @@ static int __force_merge(struct drm_buddy *mm, u64 end, unsigned int min_order) {

• enum drm_buddy_free_tree tree; unsigned int order; int i;

@@ -210,45 +236,48 @@ 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 rb_root *root = &mm->free_tree[i];
  

• struct rb_node *iter;
  

• for_each_free_tree(tree) {

• for (i = min_order - 1; i >= 0; i--) {
  

• 	struct rb_node *iter = rb_last(&mm->free_trees[tree][i]);
  

• iter = rb_last(root);
  

• while (iter) {
  

• 	struct drm_buddy_block *block, *buddy;
  

• 	u64 block_start, block_end;
  

• 	while (iter) {
  

• 		struct drm_buddy_block *block, *buddy;
  

• 		u64 block_start, block_end;
  

• 	block = rbtree_get_free_block(iter);
  

• 	iter = rb_prev(iter);
  

• 		block = rbtree_get_free_block(iter);
  

• 		iter = rb_prev(iter);
  

• 	if (!block || !block->parent)
  

• 		continue;
  

• 		if (!block || !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 (iter == &buddy->rb)
  

• 		iter = rb_prev(iter);
  

• 		/*
  

• 		 * Advance to the next node when the current node is the buddy,
  

• 		 * as freeing the block will also remove its buddy from the tree.
  

• 		 */
  

• 		if (iter == &buddy->rb)
  

• 			iter = rb_prev(iter);
  

• 	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;
  

• 	}
  

Do we need all these changes in __force_merge? Can't we just always pick the dirty tree and keep everything else the same? If something is non-merged there must be a dirty block preventing that, and when force merging everything unmerged will be re-labled as dirty anyway, so the second loop through the clean tree should always yield nothing?

}

} @@ -269,7 +298,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) @@ -291,14 +320,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->free_trees = kmalloc_array(DRM_BUDDY_MAX_FREE_TREES,

• 		       sizeof(*mm->free_trees),
  

• 		       GFP_KERNEL);
  

• if (!mm->free_trees) return -ENOMEM;

• for (i = 0; i <= mm->max_order; ++i)

• mm->free_tree[i] = RB_ROOT;
  

• for (i = 0; i < DRM_BUDDY_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 (j = 0; j <= mm->max_order; ++j)
  

• 	mm->free_trees[i][j] = RB_ROOT;
  

• }

mm->n_roots = hweight64(size); @@ -346,7 +383,9 @@ 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]);
  

out_free_roots is also decrementing 'i' here it seems, so looks like this might blow up?

• kfree(mm->free_trees); return -ENOMEM; } EXPORT_SYMBOL(drm_buddy_init);

@@ -382,8 +421,9 @@ void drm_buddy_fini(struct drm_buddy *mm) WARN_ON(mm->avail != mm->size);

• for (i = 0; i < DRM_BUDDY_MAX_FREE_TREES; i++)

• kfree(mm->free_trees[i]);
  

  kfree(mm->roots);

• kfree(mm->free_tree); } EXPORT_SYMBOL(drm_buddy_fini);

@@ -407,8 +447,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); @@ -416,7 +455,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; } @@ -449,6 +489,7 @@ EXPORT_SYMBOL(drm_get_buddy); */ void drm_buddy_reset_clear(struct drm_buddy *mm, bool is_clear) {

• enum drm_buddy_free_tree src_tree, dst_tree; u64 root_size, size, start; unsigned int order; int i;

@@ -463,19 +504,24 @@ void drm_buddy_reset_clear(struct drm_buddy *mm, bool is_clear) size -= root_size; }

• src_tree = is_clear ? DRM_BUDDY_DIRTY_TREE : DRM_BUDDY_CLEAR_TREE;
• dst_tree = is_clear ? DRM_BUDDY_CLEAR_TREE : DRM_BUDDY_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, *tmp;

• rbtree_postorder_for_each_entry_safe(block, tmp, &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);
  

• 		}
  

• rbtree_postorder_for_each_entry_safe(block, tmp, 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);
  

  } } }

@@ -665,27 +711,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 drm_buddy_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 rb_node *iter = rb_last(&mm->free_tree[i]);
  

• struct drm_buddy_block *tmp_block;
  

• while (iter) {
  

• 	tmp_block = rbtree_get_free_block(iter);
  

• 	if (!block_incompatible(tmp_block, flags)) {
  

• 		block = tmp_block;
  

• 		break;
  

• 	}
  

• 	iter = rb_prev(iter);
  

• }
  

• root = &mm->free_trees[tree][i];
  

• block = rbtree_last_free_block(root);
  

  if (!block) continue;

@@ -709,43 +745,39 @@ alloc_from_freetree(struct drm_buddy *mm, unsigned long flags) { struct drm_buddy_block *block = NULL;

• struct rb_root *root;
• enum drm_buddy_free_tree tree; unsigned int tmp; int err;

• tree = (flags & DRM_BUDDY_CLEAR_ALLOCATION) ?

• DRM_BUDDY_CLEAR_TREE : DRM_BUDDY_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 rb_node *iter = rb_last(&mm->free_tree[tmp]);
  

• 	struct drm_buddy_block *tmp_block;
  

• 	while (iter) {
  

• 		tmp_block = rbtree_get_free_block(iter);
  

• 		if (!block_incompatible(tmp_block, flags)) {
  

• 			block = tmp_block;
  

• 			break;
  

• 		}
  

• 		iter = rb_prev(iter);
  

• 	}
  

• 	/* 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 == DRM_BUDDY_CLEAR_TREE) ?
  

• 	DRM_BUDDY_DIRTY_TREE : DRM_BUDDY_CLEAR_TREE;
  

• for (tmp = order; tmp <= mm->max_order; ++tmp) {

• 	if (!rbtree_is_empty(mm, tmp)) {
  

Did you mean to drop the is_empty() check here? If it's overkill I think better just not add it in the previous patch?

• 		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) @@ -887,9 +919,9 @@ static int __alloc_contig_try_harder(struct drm_buddy *mm, struct list_head *blocks) { u64 rhs_offset, lhs_offset, lhs_size, filled;

• enum drm_buddy_free_tree tree; struct drm_buddy_block *block; LIST_HEAD(blocks_lhs);

• struct rb_node *iter; unsigned long pages; unsigned int order; u64 modify_size;

@@ -901,40 +933,43 @@ 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[DRM_BUDDY_CLEAR_TREE][order]) &&

•    rbtree_is_empty(&mm->free_trees[DRM_BUDDY_DIRTY_TREE][order]))
  

Could potentially merge this with the for_each_tree loop below?

Otherwise, Reviewed-by: Matthew Auld matthew.auld@intel.com

return -ENOSPC;

• iter = rb_last(&mm->free_tree[order]);
• while (iter) {

• block = rbtree_get_free_block(iter);
  

• /* 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_node *iter = rb_last(&mm->free_trees[tree][order]);
  

• while (iter) {
  

• 	block = rbtree_get_free_block(iter);
  

• 	/* 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);
  

• iter = rb_prev(iter);
  

• 	iter = rb_prev(iter);
  

• }
  

  }

return -ENOSPC; @@ -1239,6 +1274,7 @@ EXPORT_SYMBOL(drm_buddy_block_print); */ void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p) {

• enum drm_buddy_free_tree tree; int order;

drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n", @@ -1246,11 +1282,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, *tmp;

• struct rb_root *root;
  

  u64 count = 0, free;

• rbtree_postorder_for_each_entry_safe(block, tmp, &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];
  

• 	rbtree_postorder_for_each_entry_safe(block, tmp, 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 9ee105d4309f..d7891d08f67a 100644 --- a/include/drm/drm_buddy.h +++ b/include/drm/drm_buddy.h @@ -73,7 +73,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;

/* * Maintain explicit binary tree(s) to track the allocation of the