* [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree
@ 2025-07-24 10:46 Arunpravin Paneer Selvam
2025-07-24 10:46 ` [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees Arunpravin Paneer Selvam
2025-08-14 10:45 ` [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree Matthew Auld
0 siblings, 2 replies; 9+ messages in thread
From: Arunpravin Paneer Selvam @ 2025-07-24 10:46 UTC (permalink / raw)
To: christian.koenig, matthew.auld, dri-devel, amd-gfx
Cc: alexander.deucher, Arunpravin Paneer Selvam
Replace the freelist (O(n)) used for free block management with a
red-black tree, providing more efficient O(log n) search, insert,
and delete operations. This improves scalability and performance
when managing large numbers of free blocks per order (e.g., hundreds
or thousands).
In the VK-CTS memory stress subtest, the buddy manager merges
fragmented memory and inserts freed blocks into the freelist. Since
freelist insertion is O(n), this becomes a bottleneck as fragmentation
increases. Benchmarking shows list_insert_sorted() consumes ~52.69% CPU
with the freelist, compared to just 0.03% with the RB tree
(rbtree_insert.isra.0), despite performing the same sorted insert.
This also improves performance in heavily fragmented workloads,
such as games or graphics tests that stress memory.
Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
---
drivers/gpu/drm/drm_buddy.c | 141 +++++++++++++++++++++++-------------
include/drm/drm_buddy.h | 39 +++++++++-
2 files changed, 128 insertions(+), 52 deletions(-)
diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
index a1e652b7631d..19e9773b41be 100644
--- a/drivers/gpu/drm/drm_buddy.c
+++ b/drivers/gpu/drm/drm_buddy.c
@@ -31,6 +31,8 @@ static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm,
block->header |= order;
block->parent = parent;
+ RB_CLEAR_NODE(&block->rb);
+
BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
return block;
}
@@ -41,23 +43,53 @@ static void drm_block_free(struct drm_buddy *mm,
kmem_cache_free(slab_blocks, block);
}
-static void list_insert_sorted(struct drm_buddy *mm,
- struct drm_buddy_block *block)
+static void rbtree_insert(struct drm_buddy *mm,
+ struct drm_buddy_block *block)
{
+ 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 drm_buddy_block *node;
- struct list_head *head;
+ u64 offset;
+
+ offset = drm_buddy_block_offset(block);
- head = &mm->free_list[drm_buddy_block_order(block)];
- if (list_empty(head)) {
- list_add(&block->link, head);
- return;
+ while (*link) {
+ parent = *link;
+ node = rb_entry(parent, struct drm_buddy_block, rb);
+
+ if (offset < drm_buddy_block_offset(node))
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
}
- list_for_each_entry(node, head, link)
- if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node))
- break;
+ rb_link_node(&block->rb, parent, link);
+ rb_insert_color(&block->rb, root);
+}
+
+static void rbtree_remove(struct drm_buddy *mm,
+ struct drm_buddy_block *block)
+{
+ struct rb_root *root;
- __list_add(&block->link, node->link.prev, &node->link);
+ root = &mm->free_tree[drm_buddy_block_order(block)];
+ 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)
@@ -70,12 +102,13 @@ static void mark_cleared(struct drm_buddy_block *block)
block->header |= DRM_BUDDY_HEADER_CLEAR;
}
-static void mark_allocated(struct drm_buddy_block *block)
+static void mark_allocated(struct drm_buddy *mm,
+ struct drm_buddy_block *block)
{
block->header &= ~DRM_BUDDY_HEADER_STATE;
block->header |= DRM_BUDDY_ALLOCATED;
- list_del(&block->link);
+ rbtree_remove(mm, block);
}
static void mark_free(struct drm_buddy *mm,
@@ -84,15 +117,16 @@ static void mark_free(struct drm_buddy *mm,
block->header &= ~DRM_BUDDY_HEADER_STATE;
block->header |= DRM_BUDDY_FREE;
- list_insert_sorted(mm, block);
+ rbtree_insert(mm, block);
}
-static void mark_split(struct drm_buddy_block *block)
+static void mark_split(struct drm_buddy *mm,
+ struct drm_buddy_block *block)
{
block->header &= ~DRM_BUDDY_HEADER_STATE;
block->header |= DRM_BUDDY_SPLIT;
- list_del(&block->link);
+ rbtree_remove(mm, block);
}
static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
@@ -148,7 +182,7 @@ static unsigned int __drm_buddy_free(struct drm_buddy *mm,
mark_cleared(parent);
}
- list_del(&buddy->link);
+ rbtree_remove(mm, buddy);
if (force_merge && drm_buddy_block_is_clear(buddy))
mm->clear_avail -= drm_buddy_block_size(mm, buddy);
@@ -179,12 +213,17 @@ static int __force_merge(struct drm_buddy *mm,
return -EINVAL;
for (i = min_order - 1; i >= 0; i--) {
- struct drm_buddy_block *block, *prev;
+ struct drm_buddy_block *block, *prev_block, *first_block;
+
+ first_block = rb_entry(rb_first(&mm->free_tree[i]), struct drm_buddy_block, rb);
- list_for_each_entry_safe_reverse(block, prev, &mm->free_list[i], link) {
+ for_each_rb_entry_reverse_safe(block, prev_block, &mm->free_tree[i], rb) {
struct drm_buddy_block *buddy;
u64 block_start, block_end;
+ if (RB_EMPTY_NODE(&block->rb))
+ break;
+
if (!block->parent)
continue;
@@ -206,10 +245,14 @@ static int __force_merge(struct drm_buddy *mm,
* block in the next iteration as we would free the
* buddy block as part of the free function.
*/
- if (prev == buddy)
- prev = list_prev_entry(prev, link);
+ 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);
+ }
- list_del(&block->link);
+ rbtree_remove(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail -= drm_buddy_block_size(mm, block);
@@ -258,14 +301,14 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
- mm->free_list = kmalloc_array(mm->max_order + 1,
- sizeof(struct list_head),
+ mm->free_tree = kmalloc_array(mm->max_order + 1,
+ sizeof(struct rb_root),
GFP_KERNEL);
- if (!mm->free_list)
+ if (!mm->free_tree)
return -ENOMEM;
for (i = 0; i <= mm->max_order; ++i)
- INIT_LIST_HEAD(&mm->free_list[i]);
+ mm->free_tree[i] = RB_ROOT;
mm->n_roots = hweight64(size);
@@ -273,7 +316,7 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
sizeof(struct drm_buddy_block *),
GFP_KERNEL);
if (!mm->roots)
- goto out_free_list;
+ goto out_free_tree;
offset = 0;
i = 0;
@@ -312,8 +355,8 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
while (i--)
drm_block_free(mm, mm->roots[i]);
kfree(mm->roots);
-out_free_list:
- kfree(mm->free_list);
+out_free_tree:
+ kfree(mm->free_tree);
return -ENOMEM;
}
EXPORT_SYMBOL(drm_buddy_init);
@@ -323,7 +366,7 @@ EXPORT_SYMBOL(drm_buddy_init);
*
* @mm: DRM buddy manager to free
*
- * Cleanup memory manager resources and the freelist
+ * Cleanup memory manager resources and the freetree
*/
void drm_buddy_fini(struct drm_buddy *mm)
{
@@ -350,7 +393,7 @@ void drm_buddy_fini(struct drm_buddy *mm)
WARN_ON(mm->avail != mm->size);
kfree(mm->roots);
- kfree(mm->free_list);
+ kfree(mm->free_tree);
}
EXPORT_SYMBOL(drm_buddy_fini);
@@ -383,7 +426,7 @@ static int split_block(struct drm_buddy *mm,
clear_reset(block);
}
- mark_split(block);
+ mark_split(mm, block);
return 0;
}
@@ -598,7 +641,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int order,
for (i = order; i <= mm->max_order; ++i) {
struct drm_buddy_block *tmp_block;
- list_for_each_entry_reverse(tmp_block, &mm->free_list[i], link) {
+ for_each_rb_entry_reverse(tmp_block, &mm->free_tree[i], rb) {
if (block_incompatible(tmp_block, flags))
continue;
@@ -624,7 +667,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int order,
}
static struct drm_buddy_block *
-alloc_from_freelist(struct drm_buddy *mm,
+alloc_from_freetree(struct drm_buddy *mm,
unsigned int order,
unsigned long flags)
{
@@ -641,7 +684,7 @@ alloc_from_freelist(struct drm_buddy *mm,
for (tmp = order; tmp <= mm->max_order; ++tmp) {
struct drm_buddy_block *tmp_block;
- list_for_each_entry_reverse(tmp_block, &mm->free_list[tmp], link) {
+ for_each_rb_entry_reverse(tmp_block, &mm->free_tree[tmp], rb) {
if (block_incompatible(tmp_block, flags))
continue;
@@ -657,10 +700,8 @@ alloc_from_freelist(struct drm_buddy *mm,
if (!block) {
/* Fallback method */
for (tmp = order; tmp <= mm->max_order; ++tmp) {
- if (!list_empty(&mm->free_list[tmp])) {
- block = list_last_entry(&mm->free_list[tmp],
- struct drm_buddy_block,
- link);
+ if (!rbtree_is_empty(mm, tmp)) {
+ block = rbtree_last_entry(mm, tmp);
if (block)
break;
}
@@ -728,7 +769,7 @@ static int __alloc_range(struct drm_buddy *mm,
if (contains(start, end, block_start, block_end)) {
if (drm_buddy_block_is_free(block)) {
- mark_allocated(block);
+ mark_allocated(mm, block);
total_allocated += drm_buddy_block_size(mm, block);
mm->avail -= drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
@@ -806,7 +847,6 @@ static int __alloc_contig_try_harder(struct drm_buddy *mm,
{
u64 rhs_offset, lhs_offset, lhs_size, filled;
struct drm_buddy_block *block;
- struct list_head *list;
LIST_HEAD(blocks_lhs);
unsigned long pages;
unsigned int order;
@@ -819,11 +859,10 @@ static int __alloc_contig_try_harder(struct drm_buddy *mm,
if (order == 0)
return -ENOSPC;
- list = &mm->free_list[order];
- if (list_empty(list))
+ if (rbtree_is_empty(mm, order))
return -ENOSPC;
- list_for_each_entry_reverse(block, list, link) {
+ 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,
@@ -933,7 +972,7 @@ int drm_buddy_block_trim(struct drm_buddy *mm,
list_add(&block->tmp_link, &dfs);
err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
if (err) {
- mark_allocated(block);
+ mark_allocated(mm, block);
mm->avail -= drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail -= drm_buddy_block_size(mm, block);
@@ -956,8 +995,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
return __drm_buddy_alloc_range_bias(mm, start, end,
order, flags);
else
- /* Allocate from freelist */
- return alloc_from_freelist(mm, order, flags);
+ /* Allocate from freetree */
+ return alloc_from_freetree(mm, order, flags);
}
/**
@@ -974,8 +1013,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
* alloc_range_bias() called on range limitations, which traverses
* the tree and returns the desired block.
*
- * alloc_from_freelist() called when *no* range restrictions
- * are enforced, which picks the block from the freelist.
+ * alloc_from_freetree() called when *no* range restrictions
+ * are enforced, which picks the block from the freetree.
*
* Returns:
* 0 on success, error code on failure.
@@ -1077,7 +1116,7 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
}
} while (1);
- mark_allocated(block);
+ mark_allocated(mm, block);
mm->avail -= drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail -= drm_buddy_block_size(mm, block);
@@ -1161,7 +1200,7 @@ void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)
struct drm_buddy_block *block;
u64 count = 0, free;
- list_for_each_entry(block, &mm->free_list[order], link) {
+ for_each_rb_entry(block, &mm->free_tree[order], rb) {
BUG_ON(!drm_buddy_block_is_free(block));
count++;
}
diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
index 9689a7c5dd36..a64d108a33b7 100644
--- a/include/drm/drm_buddy.h
+++ b/include/drm/drm_buddy.h
@@ -10,6 +10,7 @@
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/sched.h>
+#include <linux/rbtree.h>
#include <drm/drm_print.h>
@@ -22,6 +23,41 @@
start__ >= max__ || size__ > max__ - start__; \
})
+/*
+ * for_each_rb_entry() - iterate over an RB tree in order
+ * @pos: the struct type * to use as a loop cursor
+ * @root: pointer to struct rb_root to iterate
+ * @member: name of the rb_node field within the struct
+ */
+#define for_each_rb_entry(pos, root, member) \
+ for (pos = rb_entry_safe(rb_first(root), typeof(*pos), member); \
+ pos; \
+ pos = rb_entry_safe(rb_next(&(pos)->member), typeof(*pos), member))
+
+/*
+ * for_each_rb_entry_reverse() - iterate over an RB tree in reverse order
+ * @pos: the struct type * to use as a loop cursor
+ * @root: pointer to struct rb_root to iterate
+ * @member: name of the rb_node field within the struct
+ */
+#define for_each_rb_entry_reverse(pos, root, member) \
+ for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member); \
+ pos; \
+ pos = rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos), member))
+
+/**
+ * for_each_rb_entry_reverse_safe() - safely iterate over an RB tree in reverse order
+ * @pos: the struct type * to use as a loop cursor.
+ * @n: another struct type * to use as temporary storage.
+ * @root: pointer to struct rb_root to iterate.
+ * @member: name of the rb_node field within the struct.
+ */
+#define for_each_rb_entry_reverse_safe(pos, n, root, member) \
+ for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member), \
+ n = pos ? rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos), member) : NULL; \
+ pos; \
+ pos = n, n = pos ? rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos), member) : NULL)
+
#define DRM_BUDDY_RANGE_ALLOCATION BIT(0)
#define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)
#define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)
@@ -53,6 +89,7 @@ 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;
};
@@ -68,7 +105,7 @@ struct drm_buddy_block {
*/
struct drm_buddy {
/* Maintain a free list for each order. */
- struct list_head *free_list;
+ struct rb_root *free_tree;
/*
* Maintain explicit binary tree(s) to track the allocation of the
--
2.34.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees
2025-07-24 10:46 [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree Arunpravin Paneer Selvam
@ 2025-07-24 10:46 ` Arunpravin Paneer Selvam
2025-08-13 13:56 ` Christian König
2025-08-14 11:11 ` Matthew Auld
2025-08-14 10:45 ` [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree Matthew Auld
1 sibling, 2 replies; 9+ messages in thread
From: Arunpravin Paneer Selvam @ 2025-07-24 10:46 UTC (permalink / raw)
To: christian.koenig, matthew.auld, dri-devel, amd-gfx
Cc: alexander.deucher, Arunpravin Paneer Selvam
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@amd.com>
Suggested-by: Matthew Auld <matthew.auld@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)
+{
+ 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);
+}
+
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)
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() \
+ 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;
+ 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;
/*
* Maintain explicit binary tree(s) to track the allocation of the
--
2.34.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees
2025-07-24 10:46 ` [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees Arunpravin Paneer Selvam
@ 2025-08-13 13:56 ` Christian König
2025-08-14 11:11 ` Matthew Auld
1 sibling, 0 replies; 9+ messages in thread
From: Christian König @ 2025-08-13 13:56 UTC (permalink / raw)
To: matthew.auld, dri-devel, amd-gfx
Cc: alexander.deucher, Arunpravin Paneer Selvam, Samuel Pitoiset
Gentle ping from my side since Arun is on sick leave today.
Matthew are you on vacation or could you take a look? It's kind of urgent to have this fixed.
Thanks,
Christian.
On 24.07.25 12: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@amd.com>
> Suggested-by: Matthew Auld <matthew.auld@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)
> +{
> + 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);
> +}
> +
> 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)
> 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() \
> + 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;
> + 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;
>
> /*
> * Maintain explicit binary tree(s) to track the allocation of the
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree
2025-07-24 10:46 [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree Arunpravin Paneer Selvam
2025-07-24 10:46 ` [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees Arunpravin Paneer Selvam
@ 2025-08-14 10:45 ` Matthew Auld
2025-08-20 7:56 ` Arunpravin Paneer Selvam
1 sibling, 1 reply; 9+ messages in thread
From: Matthew Auld @ 2025-08-14 10:45 UTC (permalink / raw)
To: Arunpravin Paneer Selvam, christian.koenig, dri-devel, amd-gfx
Cc: alexander.deucher
On 24/07/2025 11:46, Arunpravin Paneer Selvam wrote:
> Replace the freelist (O(n)) used for free block management with a
> red-black tree, providing more efficient O(log n) search, insert,
> and delete operations. This improves scalability and performance
> when managing large numbers of free blocks per order (e.g., hundreds
> or thousands).
>
> In the VK-CTS memory stress subtest, the buddy manager merges
> fragmented memory and inserts freed blocks into the freelist. Since
> freelist insertion is O(n), this becomes a bottleneck as fragmentation
> increases. Benchmarking shows list_insert_sorted() consumes ~52.69% CPU
> with the freelist, compared to just 0.03% with the RB tree
> (rbtree_insert.isra.0), despite performing the same sorted insert.
>
> This also improves performance in heavily fragmented workloads,
> such as games or graphics tests that stress memory.
Neat. Also please Cc intel-gfx@lists.freedesktop.org and
intel-xe@lists.freedesktop.org on the next revision so our CI can pick
this up.
>
> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
> ---
> drivers/gpu/drm/drm_buddy.c | 141 +++++++++++++++++++++++-------------
> include/drm/drm_buddy.h | 39 +++++++++-
> 2 files changed, 128 insertions(+), 52 deletions(-)
>
> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
> index a1e652b7631d..19e9773b41be 100644
> --- a/drivers/gpu/drm/drm_buddy.c
> +++ b/drivers/gpu/drm/drm_buddy.c
> @@ -31,6 +31,8 @@ static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm,
> block->header |= order;
> block->parent = parent;
>
> + RB_CLEAR_NODE(&block->rb);
> +
> BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
> return block;
> }
> @@ -41,23 +43,53 @@ static void drm_block_free(struct drm_buddy *mm,
> kmem_cache_free(slab_blocks, block);
> }
>
> -static void list_insert_sorted(struct drm_buddy *mm,
> - struct drm_buddy_block *block)
> +static void rbtree_insert(struct drm_buddy *mm,
> + struct drm_buddy_block *block)
> {
> + 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 drm_buddy_block *node;
> - struct list_head *head;
> + u64 offset;
> +
> + offset = drm_buddy_block_offset(block);
>
> - head = &mm->free_list[drm_buddy_block_order(block)];
> - if (list_empty(head)) {
> - list_add(&block->link, head);
> - return;
> + while (*link) {
> + parent = *link;
> + node = rb_entry(parent, struct drm_buddy_block, rb);
> +
> + if (offset < drm_buddy_block_offset(node))
> + link = &parent->rb_left;
> + else
> + link = &parent->rb_right;
> }
>
> - list_for_each_entry(node, head, link)
> - if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node))
> - break;
> + rb_link_node(&block->rb, parent, link);
> + rb_insert_color(&block->rb, root);
> +}
> +
> +static void rbtree_remove(struct drm_buddy *mm,
> + struct drm_buddy_block *block)
> +{
> + struct rb_root *root;
>
> - __list_add(&block->link, node->link.prev, &node->link);
> + root = &mm->free_tree[drm_buddy_block_order(block)];
> + 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)
> @@ -70,12 +102,13 @@ static void mark_cleared(struct drm_buddy_block *block)
> block->header |= DRM_BUDDY_HEADER_CLEAR;
> }
>
> -static void mark_allocated(struct drm_buddy_block *block)
> +static void mark_allocated(struct drm_buddy *mm,
> + struct drm_buddy_block *block)
> {
> block->header &= ~DRM_BUDDY_HEADER_STATE;
> block->header |= DRM_BUDDY_ALLOCATED;
>
> - list_del(&block->link);
> + rbtree_remove(mm, block);
> }
>
> static void mark_free(struct drm_buddy *mm,
> @@ -84,15 +117,16 @@ static void mark_free(struct drm_buddy *mm,
> block->header &= ~DRM_BUDDY_HEADER_STATE;
> block->header |= DRM_BUDDY_FREE;
>
> - list_insert_sorted(mm, block);
> + rbtree_insert(mm, block);
> }
>
> -static void mark_split(struct drm_buddy_block *block)
> +static void mark_split(struct drm_buddy *mm,
> + struct drm_buddy_block *block)
> {
> block->header &= ~DRM_BUDDY_HEADER_STATE;
> block->header |= DRM_BUDDY_SPLIT;
>
> - list_del(&block->link);
> + rbtree_remove(mm, block);
> }
>
> static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
> @@ -148,7 +182,7 @@ static unsigned int __drm_buddy_free(struct drm_buddy *mm,
> mark_cleared(parent);
> }
>
> - list_del(&buddy->link);
> + rbtree_remove(mm, buddy);
> if (force_merge && drm_buddy_block_is_clear(buddy))
> mm->clear_avail -= drm_buddy_block_size(mm, buddy);
>
> @@ -179,12 +213,17 @@ static int __force_merge(struct drm_buddy *mm,
> return -EINVAL;
>
> for (i = min_order - 1; i >= 0; i--) {
> - struct drm_buddy_block *block, *prev;
> + struct drm_buddy_block *block, *prev_block, *first_block;
> +
> + first_block = rb_entry(rb_first(&mm->free_tree[i]), struct drm_buddy_block, rb);
>
> - list_for_each_entry_safe_reverse(block, prev, &mm->free_list[i], link) {
> + for_each_rb_entry_reverse_safe(block, prev_block, &mm->free_tree[i], rb) {
> struct drm_buddy_block *buddy;
> u64 block_start, block_end;
>
> + if (RB_EMPTY_NODE(&block->rb))
> + break;
If we got the block from the rb tree, can it be empty here?
> +
> if (!block->parent)
> continue;
>
> @@ -206,10 +245,14 @@ static int __force_merge(struct drm_buddy *mm,
> * block in the next iteration as we would free the
> * buddy block as part of the free function.
> */
> - if (prev == buddy)
> - prev = list_prev_entry(prev, link);
> + 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);
> + }
>
> - list_del(&block->link);
> + rbtree_remove(mm, block);
> if (drm_buddy_block_is_clear(block))
> mm->clear_avail -= drm_buddy_block_size(mm, block);
>
> @@ -258,14 +301,14 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
>
> BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
>
> - mm->free_list = kmalloc_array(mm->max_order + 1,
> - sizeof(struct list_head),
> + mm->free_tree = kmalloc_array(mm->max_order + 1,
> + sizeof(struct rb_root),
> GFP_KERNEL);
> - if (!mm->free_list)
> + if (!mm->free_tree)
> return -ENOMEM;
>
> for (i = 0; i <= mm->max_order; ++i)
> - INIT_LIST_HEAD(&mm->free_list[i]);
> + mm->free_tree[i] = RB_ROOT;
>
> mm->n_roots = hweight64(size);
>
> @@ -273,7 +316,7 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
> sizeof(struct drm_buddy_block *),
> GFP_KERNEL);
> if (!mm->roots)
> - goto out_free_list;
> + goto out_free_tree;
>
> offset = 0;
> i = 0;
> @@ -312,8 +355,8 @@ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
> while (i--)
> drm_block_free(mm, mm->roots[i]);
> kfree(mm->roots);
> -out_free_list:
> - kfree(mm->free_list);
> +out_free_tree:
> + kfree(mm->free_tree);
> return -ENOMEM;
> }
> EXPORT_SYMBOL(drm_buddy_init);
> @@ -323,7 +366,7 @@ EXPORT_SYMBOL(drm_buddy_init);
> *
> * @mm: DRM buddy manager to free
> *
> - * Cleanup memory manager resources and the freelist
> + * Cleanup memory manager resources and the freetree
> */
> void drm_buddy_fini(struct drm_buddy *mm)
> {
> @@ -350,7 +393,7 @@ void drm_buddy_fini(struct drm_buddy *mm)
> WARN_ON(mm->avail != mm->size);
>
> kfree(mm->roots);
> - kfree(mm->free_list);
> + kfree(mm->free_tree);
> }
> EXPORT_SYMBOL(drm_buddy_fini);
>
> @@ -383,7 +426,7 @@ static int split_block(struct drm_buddy *mm,
> clear_reset(block);
> }
>
> - mark_split(block);
> + mark_split(mm, block);
>
> return 0;
> }
> @@ -598,7 +641,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int order,
> for (i = order; i <= mm->max_order; ++i) {
> struct drm_buddy_block *tmp_block;
>
> - list_for_each_entry_reverse(tmp_block, &mm->free_list[i], link) {
> + for_each_rb_entry_reverse(tmp_block, &mm->free_tree[i], rb) {
> if (block_incompatible(tmp_block, flags))
> continue;
>
> @@ -624,7 +667,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int order,
> }
>
> static struct drm_buddy_block *
> -alloc_from_freelist(struct drm_buddy *mm,
> +alloc_from_freetree(struct drm_buddy *mm,
> unsigned int order,
> unsigned long flags)
> {
> @@ -641,7 +684,7 @@ alloc_from_freelist(struct drm_buddy *mm,
> for (tmp = order; tmp <= mm->max_order; ++tmp) {
> struct drm_buddy_block *tmp_block;
>
> - list_for_each_entry_reverse(tmp_block, &mm->free_list[tmp], link) {
> + for_each_rb_entry_reverse(tmp_block, &mm->free_tree[tmp], rb) {
> if (block_incompatible(tmp_block, flags))
> continue;
>
> @@ -657,10 +700,8 @@ alloc_from_freelist(struct drm_buddy *mm,
> if (!block) {
> /* Fallback method */
> for (tmp = order; tmp <= mm->max_order; ++tmp) {
> - if (!list_empty(&mm->free_list[tmp])) {
> - block = list_last_entry(&mm->free_list[tmp],
> - struct drm_buddy_block,
> - link);
> + if (!rbtree_is_empty(mm, tmp)) {
> + block = rbtree_last_entry(mm, tmp);
> if (block)
> break;
> }
> @@ -728,7 +769,7 @@ static int __alloc_range(struct drm_buddy *mm,
>
> if (contains(start, end, block_start, block_end)) {
> if (drm_buddy_block_is_free(block)) {
> - mark_allocated(block);
> + mark_allocated(mm, block);
> total_allocated += drm_buddy_block_size(mm, block);
> mm->avail -= drm_buddy_block_size(mm, block);
> if (drm_buddy_block_is_clear(block))
> @@ -806,7 +847,6 @@ static int __alloc_contig_try_harder(struct drm_buddy *mm,
> {
> u64 rhs_offset, lhs_offset, lhs_size, filled;
> struct drm_buddy_block *block;
> - struct list_head *list;
> LIST_HEAD(blocks_lhs);
> unsigned long pages;
> unsigned int order;
> @@ -819,11 +859,10 @@ static int __alloc_contig_try_harder(struct drm_buddy *mm,
> if (order == 0)
> return -ENOSPC;
>
> - list = &mm->free_list[order];
> - if (list_empty(list))
> + if (rbtree_is_empty(mm, order))
> return -ENOSPC;
>
> - list_for_each_entry_reverse(block, list, link) {
> + 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,
> @@ -933,7 +972,7 @@ int drm_buddy_block_trim(struct drm_buddy *mm,
> list_add(&block->tmp_link, &dfs);
> err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
> if (err) {
> - mark_allocated(block);
> + mark_allocated(mm, block);
> mm->avail -= drm_buddy_block_size(mm, block);
> if (drm_buddy_block_is_clear(block))
> mm->clear_avail -= drm_buddy_block_size(mm, block);
> @@ -956,8 +995,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
> return __drm_buddy_alloc_range_bias(mm, start, end,
> order, flags);
> else
> - /* Allocate from freelist */
> - return alloc_from_freelist(mm, order, flags);
> + /* Allocate from freetree */
> + return alloc_from_freetree(mm, order, flags);
> }
>
> /**
> @@ -974,8 +1013,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
> * alloc_range_bias() called on range limitations, which traverses
> * the tree and returns the desired block.
> *
> - * alloc_from_freelist() called when *no* range restrictions
> - * are enforced, which picks the block from the freelist.
> + * alloc_from_freetree() called when *no* range restrictions
> + * are enforced, which picks the block from the freetree.
> *
> * Returns:
> * 0 on success, error code on failure.
> @@ -1077,7 +1116,7 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
> }
> } while (1);
>
> - mark_allocated(block);
> + mark_allocated(mm, block);
> mm->avail -= drm_buddy_block_size(mm, block);
> if (drm_buddy_block_is_clear(block))
> mm->clear_avail -= drm_buddy_block_size(mm, block);
> @@ -1161,7 +1200,7 @@ void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)
> struct drm_buddy_block *block;
> u64 count = 0, free;
>
> - list_for_each_entry(block, &mm->free_list[order], link) {
> + for_each_rb_entry(block, &mm->free_tree[order], rb) {
> BUG_ON(!drm_buddy_block_is_free(block));
> count++;
> }
> diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
> index 9689a7c5dd36..a64d108a33b7 100644
> --- a/include/drm/drm_buddy.h
> +++ b/include/drm/drm_buddy.h
> @@ -10,6 +10,7 @@
> #include <linux/list.h>
> #include <linux/slab.h>
> #include <linux/sched.h>
> +#include <linux/rbtree.h>
>
> #include <drm/drm_print.h>
>
> @@ -22,6 +23,41 @@
> start__ >= max__ || size__ > max__ - start__; \
> })
>
> +/*
> + * for_each_rb_entry() - iterate over an RB tree in order
> + * @pos: the struct type * to use as a loop cursor
> + * @root: pointer to struct rb_root to iterate
> + * @member: name of the rb_node field within the struct
> + */
> +#define for_each_rb_entry(pos, root, member) \
> + for (pos = rb_entry_safe(rb_first(root), typeof(*pos), member); \
> + pos; \
> + pos = rb_entry_safe(rb_next(&(pos)->member), typeof(*pos), member))
> +
> +/*
> + * for_each_rb_entry_reverse() - iterate over an RB tree in reverse order
> + * @pos: the struct type * to use as a loop cursor
> + * @root: pointer to struct rb_root to iterate
> + * @member: name of the rb_node field within the struct
> + */
> +#define for_each_rb_entry_reverse(pos, root, member) \
> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member); \
> + pos; \
> + pos = rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos), member))
> +
> +/**
> + * for_each_rb_entry_reverse_safe() - safely iterate over an RB tree in reverse order
> + * @pos: the struct type * to use as a loop cursor.
> + * @n: another struct type * to use as temporary storage.
> + * @root: pointer to struct rb_root to iterate.
> + * @member: name of the rb_node field within the struct.
> + */
> +#define for_each_rb_entry_reverse_safe(pos, n, root, member) \
Would it make sense to give these a less generic name? Something like
for_each_rb_free_block_* ?
Also should this be exported or rather kept within .c?
> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member), \
> + n = pos ? rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos), member) : NULL; \
> + pos; \
> + pos = n, n = pos ? rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos), member) : NULL)
> +
> #define DRM_BUDDY_RANGE_ALLOCATION BIT(0)
> #define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)
> #define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)
> @@ -53,6 +89,7 @@ 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;
I think we can be slippery here and make this a union? They should be
mutually exclusive AFAICT?
> struct list_head tmp_link;
Otherwise it should be possible to get rid of this instead, and just
re-use link? Could be done as separate patch, if this makes sense.
> };
> @@ -68,7 +105,7 @@ struct drm_buddy_block {
> */
> struct drm_buddy {
> /* Maintain a free list for each order. */
> - struct list_head *free_list;
> + struct rb_root *free_tree;
>
> /*
> * Maintain explicit binary tree(s) to track the allocation of the
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees
2025-07-24 10:46 ` [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees Arunpravin Paneer Selvam
2025-08-13 13:56 ` Christian König
@ 2025-08-14 11:11 ` Matthew Auld
2025-08-20 12:56 ` Arunpravin Paneer Selvam
1 sibling, 1 reply; 9+ messages in thread
From: Matthew Auld @ 2025-08-14 11:11 UTC (permalink / raw)
To: Arunpravin Paneer Selvam, christian.koenig, dri-devel, amd-gfx
Cc: alexander.deucher
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@amd.com>
> Suggested-by: Matthew Auld <matthew.auld@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?
> +{
> + 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()
...
> +
> 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.
> + 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?
> + 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?
>
> /*
> * Maintain explicit binary tree(s) to track the allocation of the
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree
2025-08-14 10:45 ` [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree Matthew Auld
@ 2025-08-20 7:56 ` Arunpravin Paneer Selvam
2025-08-20 10:14 ` Matthew Auld
0 siblings, 1 reply; 9+ messages in thread
From: Arunpravin Paneer Selvam @ 2025-08-20 7:56 UTC (permalink / raw)
To: Matthew Auld, christian.koenig, dri-devel, amd-gfx; +Cc: alexander.deucher
Hi Matthew,
On 8/14/2025 4:15 PM, Matthew Auld wrote:
> On 24/07/2025 11:46, Arunpravin Paneer Selvam wrote:
>> Replace the freelist (O(n)) used for free block management with a
>> red-black tree, providing more efficient O(log n) search, insert,
>> and delete operations. This improves scalability and performance
>> when managing large numbers of free blocks per order (e.g., hundreds
>> or thousands).
>>
>> In the VK-CTS memory stress subtest, the buddy manager merges
>> fragmented memory and inserts freed blocks into the freelist. Since
>> freelist insertion is O(n), this becomes a bottleneck as fragmentation
>> increases. Benchmarking shows list_insert_sorted() consumes ~52.69% CPU
>> with the freelist, compared to just 0.03% with the RB tree
>> (rbtree_insert.isra.0), despite performing the same sorted insert.
>>
>> This also improves performance in heavily fragmented workloads,
>> such as games or graphics tests that stress memory.
>
> Neat. Also please Cc intel-gfx@lists.freedesktop.org and
> intel-xe@lists.freedesktop.org on the next revision so our CI can pick
> this up.
Sure, I will add on v3.
>
>>
>> Signed-off-by: Arunpravin Paneer Selvam
>> <Arunpravin.PaneerSelvam@amd.com>
>> ---
>> drivers/gpu/drm/drm_buddy.c | 141 +++++++++++++++++++++++-------------
>> include/drm/drm_buddy.h | 39 +++++++++-
>> 2 files changed, 128 insertions(+), 52 deletions(-)
>>
>> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
>> index a1e652b7631d..19e9773b41be 100644
>> --- a/drivers/gpu/drm/drm_buddy.c
>> +++ b/drivers/gpu/drm/drm_buddy.c
>> @@ -31,6 +31,8 @@ static struct drm_buddy_block
>> *drm_block_alloc(struct drm_buddy *mm,
>> block->header |= order;
>> block->parent = parent;
>> + RB_CLEAR_NODE(&block->rb);
>> +
>> BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
>> return block;
>> }
>> @@ -41,23 +43,53 @@ static void drm_block_free(struct drm_buddy *mm,
>> kmem_cache_free(slab_blocks, block);
>> }
>> -static void list_insert_sorted(struct drm_buddy *mm,
>> - struct drm_buddy_block *block)
>> +static void rbtree_insert(struct drm_buddy *mm,
>> + struct drm_buddy_block *block)
>> {
>> + 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 drm_buddy_block *node;
>> - struct list_head *head;
>> + u64 offset;
>> +
>> + offset = drm_buddy_block_offset(block);
>> - head = &mm->free_list[drm_buddy_block_order(block)];
>> - if (list_empty(head)) {
>> - list_add(&block->link, head);
>> - return;
>> + while (*link) {
>> + parent = *link;
>> + node = rb_entry(parent, struct drm_buddy_block, rb);
>> +
>> + if (offset < drm_buddy_block_offset(node))
>> + link = &parent->rb_left;
>> + else
>> + link = &parent->rb_right;
>> }
>> - list_for_each_entry(node, head, link)
>> - if (drm_buddy_block_offset(block) <
>> drm_buddy_block_offset(node))
>> - break;
>> + rb_link_node(&block->rb, parent, link);
>> + rb_insert_color(&block->rb, root);
>> +}
>> +
>> +static void rbtree_remove(struct drm_buddy *mm,
>> + struct drm_buddy_block *block)
>> +{
>> + struct rb_root *root;
>> - __list_add(&block->link, node->link.prev, &node->link);
>> + root = &mm->free_tree[drm_buddy_block_order(block)];
>> + 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)
>> @@ -70,12 +102,13 @@ static void mark_cleared(struct drm_buddy_block
>> *block)
>> block->header |= DRM_BUDDY_HEADER_CLEAR;
>> }
>> -static void mark_allocated(struct drm_buddy_block *block)
>> +static void mark_allocated(struct drm_buddy *mm,
>> + struct drm_buddy_block *block)
>> {
>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>> block->header |= DRM_BUDDY_ALLOCATED;
>> - list_del(&block->link);
>> + rbtree_remove(mm, block);
>> }
>> static void mark_free(struct drm_buddy *mm,
>> @@ -84,15 +117,16 @@ static void mark_free(struct drm_buddy *mm,
>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>> block->header |= DRM_BUDDY_FREE;
>> - list_insert_sorted(mm, block);
>> + rbtree_insert(mm, block);
>> }
>> -static void mark_split(struct drm_buddy_block *block)
>> +static void mark_split(struct drm_buddy *mm,
>> + struct drm_buddy_block *block)
>> {
>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>> block->header |= DRM_BUDDY_SPLIT;
>> - list_del(&block->link);
>> + rbtree_remove(mm, block);
>> }
>> static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
>> @@ -148,7 +182,7 @@ static unsigned int __drm_buddy_free(struct
>> drm_buddy *mm,
>> mark_cleared(parent);
>> }
>> - list_del(&buddy->link);
>> + rbtree_remove(mm, buddy);
>> if (force_merge && drm_buddy_block_is_clear(buddy))
>> mm->clear_avail -= drm_buddy_block_size(mm, buddy);
>> @@ -179,12 +213,17 @@ static int __force_merge(struct drm_buddy *mm,
>> return -EINVAL;
>> for (i = min_order - 1; i >= 0; i--) {
>> - struct drm_buddy_block *block, *prev;
>> + struct drm_buddy_block *block, *prev_block, *first_block;
>> +
>> + first_block = rb_entry(rb_first(&mm->free_tree[i]), struct
>> drm_buddy_block, rb);
>> - list_for_each_entry_safe_reverse(block, prev,
>> &mm->free_list[i], link) {
>> + for_each_rb_entry_reverse_safe(block, prev_block,
>> &mm->free_tree[i], rb) {
>> struct drm_buddy_block *buddy;
>> u64 block_start, block_end;
>> + if (RB_EMPTY_NODE(&block->rb))
>> + break;
>
> If we got the block from the rb tree, can it be empty here?
I saw a crash earlier without this check while running graphics
workloads, but it is not happening now. I will
test with more workloads and remove it if everything looks fine.
>
>> +
>> if (!block->parent)
>> continue;
>> @@ -206,10 +245,14 @@ static int __force_merge(struct drm_buddy *mm,
>> * block in the next iteration as we would free the
>> * buddy block as part of the free function.
>> */
>> - if (prev == buddy)
>> - prev = list_prev_entry(prev, link);
>> + 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);
>> + }
>> - list_del(&block->link);
>> + rbtree_remove(mm, block);
>> if (drm_buddy_block_is_clear(block))
>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>> @@ -258,14 +301,14 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>> size, u64 chunk_size)
>> BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
>> - mm->free_list = kmalloc_array(mm->max_order + 1,
>> - sizeof(struct list_head),
>> + mm->free_tree = kmalloc_array(mm->max_order + 1,
>> + sizeof(struct rb_root),
>> GFP_KERNEL);
>> - if (!mm->free_list)
>> + if (!mm->free_tree)
>> return -ENOMEM;
>> for (i = 0; i <= mm->max_order; ++i)
>> - INIT_LIST_HEAD(&mm->free_list[i]);
>> + mm->free_tree[i] = RB_ROOT;
>> mm->n_roots = hweight64(size);
>> @@ -273,7 +316,7 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>> size, u64 chunk_size)
>> sizeof(struct drm_buddy_block *),
>> GFP_KERNEL);
>> if (!mm->roots)
>> - goto out_free_list;
>> + goto out_free_tree;
>> offset = 0;
>> i = 0;
>> @@ -312,8 +355,8 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>> size, u64 chunk_size)
>> while (i--)
>> drm_block_free(mm, mm->roots[i]);
>> kfree(mm->roots);
>> -out_free_list:
>> - kfree(mm->free_list);
>> +out_free_tree:
>> + kfree(mm->free_tree);
>> return -ENOMEM;
>> }
>> EXPORT_SYMBOL(drm_buddy_init);
>> @@ -323,7 +366,7 @@ EXPORT_SYMBOL(drm_buddy_init);
>> *
>> * @mm: DRM buddy manager to free
>> *
>> - * Cleanup memory manager resources and the freelist
>> + * Cleanup memory manager resources and the freetree
>> */
>> void drm_buddy_fini(struct drm_buddy *mm)
>> {
>> @@ -350,7 +393,7 @@ void drm_buddy_fini(struct drm_buddy *mm)
>> WARN_ON(mm->avail != mm->size);
>> kfree(mm->roots);
>> - kfree(mm->free_list);
>> + kfree(mm->free_tree);
>> }
>> EXPORT_SYMBOL(drm_buddy_fini);
>> @@ -383,7 +426,7 @@ static int split_block(struct drm_buddy *mm,
>> clear_reset(block);
>> }
>> - mark_split(block);
>> + mark_split(mm, block);
>> return 0;
>> }
>> @@ -598,7 +641,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int
>> order,
>> for (i = order; i <= mm->max_order; ++i) {
>> struct drm_buddy_block *tmp_block;
>> - list_for_each_entry_reverse(tmp_block, &mm->free_list[i],
>> link) {
>> + for_each_rb_entry_reverse(tmp_block, &mm->free_tree[i], rb) {
>> if (block_incompatible(tmp_block, flags))
>> continue;
>> @@ -624,7 +667,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int
>> order,
>> }
>> static struct drm_buddy_block *
>> -alloc_from_freelist(struct drm_buddy *mm,
>> +alloc_from_freetree(struct drm_buddy *mm,
>> unsigned int order,
>> unsigned long flags)
>> {
>> @@ -641,7 +684,7 @@ alloc_from_freelist(struct drm_buddy *mm,
>> for (tmp = order; tmp <= mm->max_order; ++tmp) {
>> struct drm_buddy_block *tmp_block;
>> - list_for_each_entry_reverse(tmp_block,
>> &mm->free_list[tmp], link) {
>> + for_each_rb_entry_reverse(tmp_block,
>> &mm->free_tree[tmp], rb) {
>> if (block_incompatible(tmp_block, flags))
>> continue;
>> @@ -657,10 +700,8 @@ alloc_from_freelist(struct drm_buddy *mm,
>> if (!block) {
>> /* Fallback method */
>> for (tmp = order; tmp <= mm->max_order; ++tmp) {
>> - if (!list_empty(&mm->free_list[tmp])) {
>> - block = list_last_entry(&mm->free_list[tmp],
>> - struct drm_buddy_block,
>> - link);
>> + if (!rbtree_is_empty(mm, tmp)) {
>> + block = rbtree_last_entry(mm, tmp);
>> if (block)
>> break;
>> }
>> @@ -728,7 +769,7 @@ static int __alloc_range(struct drm_buddy *mm,
>> if (contains(start, end, block_start, block_end)) {
>> if (drm_buddy_block_is_free(block)) {
>> - mark_allocated(block);
>> + mark_allocated(mm, block);
>> total_allocated += drm_buddy_block_size(mm, block);
>> mm->avail -= drm_buddy_block_size(mm, block);
>> if (drm_buddy_block_is_clear(block))
>> @@ -806,7 +847,6 @@ static int __alloc_contig_try_harder(struct
>> drm_buddy *mm,
>> {
>> u64 rhs_offset, lhs_offset, lhs_size, filled;
>> struct drm_buddy_block *block;
>> - struct list_head *list;
>> LIST_HEAD(blocks_lhs);
>> unsigned long pages;
>> unsigned int order;
>> @@ -819,11 +859,10 @@ static int __alloc_contig_try_harder(struct
>> drm_buddy *mm,
>> if (order == 0)
>> return -ENOSPC;
>> - list = &mm->free_list[order];
>> - if (list_empty(list))
>> + if (rbtree_is_empty(mm, order))
>> return -ENOSPC;
>> - list_for_each_entry_reverse(block, list, link) {
>> + 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,
>> @@ -933,7 +972,7 @@ int drm_buddy_block_trim(struct drm_buddy *mm,
>> list_add(&block->tmp_link, &dfs);
>> err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
>> if (err) {
>> - mark_allocated(block);
>> + mark_allocated(mm, block);
>> mm->avail -= drm_buddy_block_size(mm, block);
>> if (drm_buddy_block_is_clear(block))
>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>> @@ -956,8 +995,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
>> return __drm_buddy_alloc_range_bias(mm, start, end,
>> order, flags);
>> else
>> - /* Allocate from freelist */
>> - return alloc_from_freelist(mm, order, flags);
>> + /* Allocate from freetree */
>> + return alloc_from_freetree(mm, order, flags);
>> }
>> /**
>> @@ -974,8 +1013,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
>> * alloc_range_bias() called on range limitations, which traverses
>> * the tree and returns the desired block.
>> *
>> - * alloc_from_freelist() called when *no* range restrictions
>> - * are enforced, which picks the block from the freelist.
>> + * alloc_from_freetree() called when *no* range restrictions
>> + * are enforced, which picks the block from the freetree.
>> *
>> * Returns:
>> * 0 on success, error code on failure.
>> @@ -1077,7 +1116,7 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
>> }
>> } while (1);
>> - mark_allocated(block);
>> + mark_allocated(mm, block);
>> mm->avail -= drm_buddy_block_size(mm, block);
>> if (drm_buddy_block_is_clear(block))
>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>> @@ -1161,7 +1200,7 @@ void drm_buddy_print(struct drm_buddy *mm,
>> struct drm_printer *p)
>> struct drm_buddy_block *block;
>> u64 count = 0, free;
>> - list_for_each_entry(block, &mm->free_list[order], link) {
>> + for_each_rb_entry(block, &mm->free_tree[order], rb) {
>> BUG_ON(!drm_buddy_block_is_free(block));
>> count++;
>> }
>> diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
>> index 9689a7c5dd36..a64d108a33b7 100644
>> --- a/include/drm/drm_buddy.h
>> +++ b/include/drm/drm_buddy.h
>> @@ -10,6 +10,7 @@
>> #include <linux/list.h>
>> #include <linux/slab.h>
>> #include <linux/sched.h>
>> +#include <linux/rbtree.h>
>> #include <drm/drm_print.h>
>> @@ -22,6 +23,41 @@
>> start__ >= max__ || size__ > max__ - start__; \
>> })
>> +/*
>> + * for_each_rb_entry() - iterate over an RB tree in order
>> + * @pos: the struct type * to use as a loop cursor
>> + * @root: pointer to struct rb_root to iterate
>> + * @member: name of the rb_node field within the struct
>> + */
>> +#define for_each_rb_entry(pos, root, member) \
>> + for (pos = rb_entry_safe(rb_first(root), typeof(*pos), member); \
>> + pos; \
>> + pos = rb_entry_safe(rb_next(&(pos)->member), typeof(*pos),
>> member))
>> +
>> +/*
>> + * for_each_rb_entry_reverse() - iterate over an RB tree in reverse
>> order
>> + * @pos: the struct type * to use as a loop cursor
>> + * @root: pointer to struct rb_root to iterate
>> + * @member: name of the rb_node field within the struct
>> + */
>> +#define for_each_rb_entry_reverse(pos, root, member) \
>> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member); \
>> + pos; \
>> + pos = rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos),
>> member))
>> +
>> +/**
>> + * for_each_rb_entry_reverse_safe() - safely iterate over an RB tree
>> in reverse order
>> + * @pos: the struct type * to use as a loop cursor.
>> + * @n: another struct type * to use as temporary storage.
>> + * @root: pointer to struct rb_root to iterate.
>> + * @member: name of the rb_node field within the struct.
>> + */
>> +#define for_each_rb_entry_reverse_safe(pos, n, root, member) \
>
> Would it make sense to give these a less generic name? Something like
> for_each_rb_free_block_* ?
>
> Also should this be exported or rather kept within .c?
yes, I will change it.
>
>> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member), \
>> + n = pos ? rb_entry_safe(rb_prev(&(pos)->member),
>> typeof(*pos), member) : NULL; \
>> + pos; \
>> + pos = n, n = pos ? rb_entry_safe(rb_prev(&(pos)->member),
>> typeof(*pos), member) : NULL)
>
>
>> +
>> #define DRM_BUDDY_RANGE_ALLOCATION BIT(0)
>> #define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)
>> #define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)
>> @@ -53,6 +89,7 @@ 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;
>
> I think we can be slippery here and make this a union? They should be
> mutually exclusive AFAICT?
AFAIK, we need both, rb_node rb is for handling free blocks and the
list_head link for adding the allocated blocks into
the driver's list.
>
>> struct list_head tmp_link;
>
> Otherwise it should be possible to get rid of this instead, and just
> re-use link? Could be done as separate patch, if this makes sense.
I think we cannot use link here since it is needed to add the allocated
blocks to the driver's list and tmp_link is already used in
alloc_range() and alloc_range_bias().
Regards,
Arun.
>
>> };
>> @@ -68,7 +105,7 @@ struct drm_buddy_block {
>> */
>> struct drm_buddy {
>> /* Maintain a free list for each order. */
>> - struct list_head *free_list;
>> + struct rb_root *free_tree;
>> /*
>> * Maintain explicit binary tree(s) to track the allocation of the
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree
2025-08-20 7:56 ` Arunpravin Paneer Selvam
@ 2025-08-20 10:14 ` Matthew Auld
2025-08-20 10:37 ` Arunpravin Paneer Selvam
0 siblings, 1 reply; 9+ messages in thread
From: Matthew Auld @ 2025-08-20 10:14 UTC (permalink / raw)
To: Arunpravin Paneer Selvam, christian.koenig, dri-devel, amd-gfx
Cc: alexander.deucher
On 20/08/2025 08:56, Arunpravin Paneer Selvam wrote:
> Hi Matthew,
>
> On 8/14/2025 4:15 PM, Matthew Auld wrote:
>> On 24/07/2025 11:46, Arunpravin Paneer Selvam wrote:
>>> Replace the freelist (O(n)) used for free block management with a
>>> red-black tree, providing more efficient O(log n) search, insert,
>>> and delete operations. This improves scalability and performance
>>> when managing large numbers of free blocks per order (e.g., hundreds
>>> or thousands).
>>>
>>> In the VK-CTS memory stress subtest, the buddy manager merges
>>> fragmented memory and inserts freed blocks into the freelist. Since
>>> freelist insertion is O(n), this becomes a bottleneck as fragmentation
>>> increases. Benchmarking shows list_insert_sorted() consumes ~52.69% CPU
>>> with the freelist, compared to just 0.03% with the RB tree
>>> (rbtree_insert.isra.0), despite performing the same sorted insert.
>>>
>>> This also improves performance in heavily fragmented workloads,
>>> such as games or graphics tests that stress memory.
>>
>> Neat. Also please Cc intel-gfx@lists.freedesktop.org and intel-
>> xe@lists.freedesktop.org on the next revision so our CI can pick this up.
> Sure, I will add on v3.
>>
>>>
>>> Signed-off-by: Arunpravin Paneer Selvam
>>> <Arunpravin.PaneerSelvam@amd.com>
>>> ---
>>> drivers/gpu/drm/drm_buddy.c | 141 +++++++++++++++++++++++-------------
>>> include/drm/drm_buddy.h | 39 +++++++++-
>>> 2 files changed, 128 insertions(+), 52 deletions(-)
>>>
>>> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
>>> index a1e652b7631d..19e9773b41be 100644
>>> --- a/drivers/gpu/drm/drm_buddy.c
>>> +++ b/drivers/gpu/drm/drm_buddy.c
>>> @@ -31,6 +31,8 @@ static struct drm_buddy_block
>>> *drm_block_alloc(struct drm_buddy *mm,
>>> block->header |= order;
>>> block->parent = parent;
>>> + RB_CLEAR_NODE(&block->rb);
>>> +
>>> BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
>>> return block;
>>> }
>>> @@ -41,23 +43,53 @@ static void drm_block_free(struct drm_buddy *mm,
>>> kmem_cache_free(slab_blocks, block);
>>> }
>>> -static void list_insert_sorted(struct drm_buddy *mm,
>>> - struct drm_buddy_block *block)
>>> +static void rbtree_insert(struct drm_buddy *mm,
>>> + struct drm_buddy_block *block)
>>> {
>>> + 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 drm_buddy_block *node;
>>> - struct list_head *head;
>>> + u64 offset;
>>> +
>>> + offset = drm_buddy_block_offset(block);
>>> - head = &mm->free_list[drm_buddy_block_order(block)];
>>> - if (list_empty(head)) {
>>> - list_add(&block->link, head);
>>> - return;
>>> + while (*link) {
>>> + parent = *link;
>>> + node = rb_entry(parent, struct drm_buddy_block, rb);
>>> +
>>> + if (offset < drm_buddy_block_offset(node))
>>> + link = &parent->rb_left;
>>> + else
>>> + link = &parent->rb_right;
>>> }
>>> - list_for_each_entry(node, head, link)
>>> - if (drm_buddy_block_offset(block) <
>>> drm_buddy_block_offset(node))
>>> - break;
>>> + rb_link_node(&block->rb, parent, link);
>>> + rb_insert_color(&block->rb, root);
>>> +}
>>> +
>>> +static void rbtree_remove(struct drm_buddy *mm,
>>> + struct drm_buddy_block *block)
>>> +{
>>> + struct rb_root *root;
>>> - __list_add(&block->link, node->link.prev, &node->link);
>>> + root = &mm->free_tree[drm_buddy_block_order(block)];
>>> + 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)
>>> @@ -70,12 +102,13 @@ static void mark_cleared(struct drm_buddy_block
>>> *block)
>>> block->header |= DRM_BUDDY_HEADER_CLEAR;
>>> }
>>> -static void mark_allocated(struct drm_buddy_block *block)
>>> +static void mark_allocated(struct drm_buddy *mm,
>>> + struct drm_buddy_block *block)
>>> {
>>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>>> block->header |= DRM_BUDDY_ALLOCATED;
>>> - list_del(&block->link);
>>> + rbtree_remove(mm, block);
>>> }
>>> static void mark_free(struct drm_buddy *mm,
>>> @@ -84,15 +117,16 @@ static void mark_free(struct drm_buddy *mm,
>>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>>> block->header |= DRM_BUDDY_FREE;
>>> - list_insert_sorted(mm, block);
>>> + rbtree_insert(mm, block);
>>> }
>>> -static void mark_split(struct drm_buddy_block *block)
>>> +static void mark_split(struct drm_buddy *mm,
>>> + struct drm_buddy_block *block)
>>> {
>>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>>> block->header |= DRM_BUDDY_SPLIT;
>>> - list_del(&block->link);
>>> + rbtree_remove(mm, block);
>>> }
>>> static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
>>> @@ -148,7 +182,7 @@ static unsigned int __drm_buddy_free(struct
>>> drm_buddy *mm,
>>> mark_cleared(parent);
>>> }
>>> - list_del(&buddy->link);
>>> + rbtree_remove(mm, buddy);
>>> if (force_merge && drm_buddy_block_is_clear(buddy))
>>> mm->clear_avail -= drm_buddy_block_size(mm, buddy);
>>> @@ -179,12 +213,17 @@ static int __force_merge(struct drm_buddy *mm,
>>> return -EINVAL;
>>> for (i = min_order - 1; i >= 0; i--) {
>>> - struct drm_buddy_block *block, *prev;
>>> + struct drm_buddy_block *block, *prev_block, *first_block;
>>> +
>>> + first_block = rb_entry(rb_first(&mm->free_tree[i]), struct
>>> drm_buddy_block, rb);
>>> - list_for_each_entry_safe_reverse(block, prev, &mm-
>>> >free_list[i], link) {
>>> + for_each_rb_entry_reverse_safe(block, prev_block, &mm-
>>> >free_tree[i], rb) {
>>> struct drm_buddy_block *buddy;
>>> u64 block_start, block_end;
>>> + if (RB_EMPTY_NODE(&block->rb))
>>> + break;
>>
>> If we got the block from the rb tree, can it be empty here?
>
> I saw a crash earlier without this check while running graphics
> workloads, but it is not happening now. I will
>
> test with more workloads and remove it if everything looks fine.
>
>>
>>> +
>>> if (!block->parent)
>>> continue;
>>> @@ -206,10 +245,14 @@ static int __force_merge(struct drm_buddy *mm,
>>> * block in the next iteration as we would free the
>>> * buddy block as part of the free function.
>>> */
>>> - if (prev == buddy)
>>> - prev = list_prev_entry(prev, link);
>>> + 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);
>>> + }
>>> - list_del(&block->link);
>>> + rbtree_remove(mm, block);
>>> if (drm_buddy_block_is_clear(block))
>>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>>> @@ -258,14 +301,14 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>>> size, u64 chunk_size)
>>> BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
>>> - mm->free_list = kmalloc_array(mm->max_order + 1,
>>> - sizeof(struct list_head),
>>> + mm->free_tree = kmalloc_array(mm->max_order + 1,
>>> + sizeof(struct rb_root),
>>> GFP_KERNEL);
>>> - if (!mm->free_list)
>>> + if (!mm->free_tree)
>>> return -ENOMEM;
>>> for (i = 0; i <= mm->max_order; ++i)
>>> - INIT_LIST_HEAD(&mm->free_list[i]);
>>> + mm->free_tree[i] = RB_ROOT;
>>> mm->n_roots = hweight64(size);
>>> @@ -273,7 +316,7 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>>> size, u64 chunk_size)
>>> sizeof(struct drm_buddy_block *),
>>> GFP_KERNEL);
>>> if (!mm->roots)
>>> - goto out_free_list;
>>> + goto out_free_tree;
>>> offset = 0;
>>> i = 0;
>>> @@ -312,8 +355,8 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>>> size, u64 chunk_size)
>>> while (i--)
>>> drm_block_free(mm, mm->roots[i]);
>>> kfree(mm->roots);
>>> -out_free_list:
>>> - kfree(mm->free_list);
>>> +out_free_tree:
>>> + kfree(mm->free_tree);
>>> return -ENOMEM;
>>> }
>>> EXPORT_SYMBOL(drm_buddy_init);
>>> @@ -323,7 +366,7 @@ EXPORT_SYMBOL(drm_buddy_init);
>>> *
>>> * @mm: DRM buddy manager to free
>>> *
>>> - * Cleanup memory manager resources and the freelist
>>> + * Cleanup memory manager resources and the freetree
>>> */
>>> void drm_buddy_fini(struct drm_buddy *mm)
>>> {
>>> @@ -350,7 +393,7 @@ void drm_buddy_fini(struct drm_buddy *mm)
>>> WARN_ON(mm->avail != mm->size);
>>> kfree(mm->roots);
>>> - kfree(mm->free_list);
>>> + kfree(mm->free_tree);
>>> }
>>> EXPORT_SYMBOL(drm_buddy_fini);
>>> @@ -383,7 +426,7 @@ static int split_block(struct drm_buddy *mm,
>>> clear_reset(block);
>>> }
>>> - mark_split(block);
>>> + mark_split(mm, block);
>>> return 0;
>>> }
>>> @@ -598,7 +641,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int
>>> order,
>>> for (i = order; i <= mm->max_order; ++i) {
>>> struct drm_buddy_block *tmp_block;
>>> - list_for_each_entry_reverse(tmp_block, &mm->free_list[i],
>>> link) {
>>> + for_each_rb_entry_reverse(tmp_block, &mm->free_tree[i], rb) {
>>> if (block_incompatible(tmp_block, flags))
>>> continue;
>>> @@ -624,7 +667,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int
>>> order,
>>> }
>>> static struct drm_buddy_block *
>>> -alloc_from_freelist(struct drm_buddy *mm,
>>> +alloc_from_freetree(struct drm_buddy *mm,
>>> unsigned int order,
>>> unsigned long flags)
>>> {
>>> @@ -641,7 +684,7 @@ alloc_from_freelist(struct drm_buddy *mm,
>>> for (tmp = order; tmp <= mm->max_order; ++tmp) {
>>> struct drm_buddy_block *tmp_block;
>>> - list_for_each_entry_reverse(tmp_block, &mm-
>>> >free_list[tmp], link) {
>>> + for_each_rb_entry_reverse(tmp_block, &mm-
>>> >free_tree[tmp], rb) {
>>> if (block_incompatible(tmp_block, flags))
>>> continue;
>>> @@ -657,10 +700,8 @@ alloc_from_freelist(struct drm_buddy *mm,
>>> if (!block) {
>>> /* Fallback method */
>>> for (tmp = order; tmp <= mm->max_order; ++tmp) {
>>> - if (!list_empty(&mm->free_list[tmp])) {
>>> - block = list_last_entry(&mm->free_list[tmp],
>>> - struct drm_buddy_block,
>>> - link);
>>> + if (!rbtree_is_empty(mm, tmp)) {
>>> + block = rbtree_last_entry(mm, tmp);
>>> if (block)
>>> break;
>>> }
>>> @@ -728,7 +769,7 @@ static int __alloc_range(struct drm_buddy *mm,
>>> if (contains(start, end, block_start, block_end)) {
>>> if (drm_buddy_block_is_free(block)) {
>>> - mark_allocated(block);
>>> + mark_allocated(mm, block);
>>> total_allocated += drm_buddy_block_size(mm, block);
>>> mm->avail -= drm_buddy_block_size(mm, block);
>>> if (drm_buddy_block_is_clear(block))
>>> @@ -806,7 +847,6 @@ static int __alloc_contig_try_harder(struct
>>> drm_buddy *mm,
>>> {
>>> u64 rhs_offset, lhs_offset, lhs_size, filled;
>>> struct drm_buddy_block *block;
>>> - struct list_head *list;
>>> LIST_HEAD(blocks_lhs);
>>> unsigned long pages;
>>> unsigned int order;
>>> @@ -819,11 +859,10 @@ static int __alloc_contig_try_harder(struct
>>> drm_buddy *mm,
>>> if (order == 0)
>>> return -ENOSPC;
>>> - list = &mm->free_list[order];
>>> - if (list_empty(list))
>>> + if (rbtree_is_empty(mm, order))
>>> return -ENOSPC;
>>> - list_for_each_entry_reverse(block, list, link) {
>>> + 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,
>>> @@ -933,7 +972,7 @@ int drm_buddy_block_trim(struct drm_buddy *mm,
>>> list_add(&block->tmp_link, &dfs);
>>> err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
>>> if (err) {
>>> - mark_allocated(block);
>>> + mark_allocated(mm, block);
>>> mm->avail -= drm_buddy_block_size(mm, block);
>>> if (drm_buddy_block_is_clear(block))
>>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>>> @@ -956,8 +995,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
>>> return __drm_buddy_alloc_range_bias(mm, start, end,
>>> order, flags);
>>> else
>>> - /* Allocate from freelist */
>>> - return alloc_from_freelist(mm, order, flags);
>>> + /* Allocate from freetree */
>>> + return alloc_from_freetree(mm, order, flags);
>>> }
>>> /**
>>> @@ -974,8 +1013,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
>>> * alloc_range_bias() called on range limitations, which traverses
>>> * the tree and returns the desired block.
>>> *
>>> - * alloc_from_freelist() called when *no* range restrictions
>>> - * are enforced, which picks the block from the freelist.
>>> + * alloc_from_freetree() called when *no* range restrictions
>>> + * are enforced, which picks the block from the freetree.
>>> *
>>> * Returns:
>>> * 0 on success, error code on failure.
>>> @@ -1077,7 +1116,7 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
>>> }
>>> } while (1);
>>> - mark_allocated(block);
>>> + mark_allocated(mm, block);
>>> mm->avail -= drm_buddy_block_size(mm, block);
>>> if (drm_buddy_block_is_clear(block))
>>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>>> @@ -1161,7 +1200,7 @@ void drm_buddy_print(struct drm_buddy *mm,
>>> struct drm_printer *p)
>>> struct drm_buddy_block *block;
>>> u64 count = 0, free;
>>> - list_for_each_entry(block, &mm->free_list[order], link) {
>>> + for_each_rb_entry(block, &mm->free_tree[order], rb) {
>>> BUG_ON(!drm_buddy_block_is_free(block));
>>> count++;
>>> }
>>> diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
>>> index 9689a7c5dd36..a64d108a33b7 100644
>>> --- a/include/drm/drm_buddy.h
>>> +++ b/include/drm/drm_buddy.h
>>> @@ -10,6 +10,7 @@
>>> #include <linux/list.h>
>>> #include <linux/slab.h>
>>> #include <linux/sched.h>
>>> +#include <linux/rbtree.h>
>>> #include <drm/drm_print.h>
>>> @@ -22,6 +23,41 @@
>>> start__ >= max__ || size__ > max__ - start__; \
>>> })
>>> +/*
>>> + * for_each_rb_entry() - iterate over an RB tree in order
>>> + * @pos: the struct type * to use as a loop cursor
>>> + * @root: pointer to struct rb_root to iterate
>>> + * @member: name of the rb_node field within the struct
>>> + */
>>> +#define for_each_rb_entry(pos, root, member) \
>>> + for (pos = rb_entry_safe(rb_first(root), typeof(*pos), member); \
>>> + pos; \
>>> + pos = rb_entry_safe(rb_next(&(pos)->member), typeof(*pos),
>>> member))
>>> +
>>> +/*
>>> + * for_each_rb_entry_reverse() - iterate over an RB tree in reverse
>>> order
>>> + * @pos: the struct type * to use as a loop cursor
>>> + * @root: pointer to struct rb_root to iterate
>>> + * @member: name of the rb_node field within the struct
>>> + */
>>> +#define for_each_rb_entry_reverse(pos, root, member) \
>>> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member); \
>>> + pos; \
>>> + pos = rb_entry_safe(rb_prev(&(pos)->member), typeof(*pos),
>>> member))
>>> +
>>> +/**
>>> + * for_each_rb_entry_reverse_safe() - safely iterate over an RB tree
>>> in reverse order
>>> + * @pos: the struct type * to use as a loop cursor.
>>> + * @n: another struct type * to use as temporary storage.
>>> + * @root: pointer to struct rb_root to iterate.
>>> + * @member: name of the rb_node field within the struct.
>>> + */
>>> +#define for_each_rb_entry_reverse_safe(pos, n, root, member) \
>>
>> Would it make sense to give these a less generic name? Something like
>> for_each_rb_free_block_* ?
>>
>> Also should this be exported or rather kept within .c?
> yes, I will change it.
>>
>>> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member), \
>>> + n = pos ? rb_entry_safe(rb_prev(&(pos)->member),
>>> typeof(*pos), member) : NULL; \
>>> + pos; \
>>> + pos = n, n = pos ? rb_entry_safe(rb_prev(&(pos)->member),
>>> typeof(*pos), member) : NULL)
>>
>>
>>> +
>>> #define DRM_BUDDY_RANGE_ALLOCATION BIT(0)
>>> #define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)
>>> #define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)
>>> @@ -53,6 +89,7 @@ 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;
>>
>> I think we can be slippery here and make this a union? They should be
>> mutually exclusive AFAICT?
>
> AFAIK, we need both, rb_node rb is for handling free blocks and the
> list_head link for adding the allocated blocks into
>
> the driver's list.
At a given time I think it is either on the free rb or user block list,
not both at the same time, given that a block can't be free and
allocated? Just thinking if there is an easy way to trim the size a bit,
given that we are adding an entire rb_node, and there can be many of
these of these blocks around.
>
>>
>>> struct list_head tmp_link;
>>
>> Otherwise it should be possible to get rid of this instead, and just
>> re-use link? Could be done as separate patch, if this makes sense.
>
> I think we cannot use link here since it is needed to add the allocated
> blocks to the driver's list and tmp_link is already used in
>
> alloc_range() and alloc_range_bias().
Yeah, I don't this will work, but union might still be an option instead.
>
> Regards,
>
> Arun.
>
>>
>>> };
>>> @@ -68,7 +105,7 @@ struct drm_buddy_block {
>>> */
>>> struct drm_buddy {
>>> /* Maintain a free list for each order. */
>>> - struct list_head *free_list;
>>> + struct rb_root *free_tree;
>>> /*
>>> * Maintain explicit binary tree(s) to track the allocation of the
>>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree
2025-08-20 10:14 ` Matthew Auld
@ 2025-08-20 10:37 ` Arunpravin Paneer Selvam
0 siblings, 0 replies; 9+ messages in thread
From: Arunpravin Paneer Selvam @ 2025-08-20 10:37 UTC (permalink / raw)
To: Matthew Auld, christian.koenig, dri-devel, amd-gfx; +Cc: alexander.deucher
On 8/20/2025 3:44 PM, Matthew Auld wrote:
> On 20/08/2025 08:56, Arunpravin Paneer Selvam wrote:
>> Hi Matthew,
>>
>> On 8/14/2025 4:15 PM, Matthew Auld wrote:
>>> On 24/07/2025 11:46, Arunpravin Paneer Selvam wrote:
>>>> Replace the freelist (O(n)) used for free block management with a
>>>> red-black tree, providing more efficient O(log n) search, insert,
>>>> and delete operations. This improves scalability and performance
>>>> when managing large numbers of free blocks per order (e.g., hundreds
>>>> or thousands).
>>>>
>>>> In the VK-CTS memory stress subtest, the buddy manager merges
>>>> fragmented memory and inserts freed blocks into the freelist. Since
>>>> freelist insertion is O(n), this becomes a bottleneck as fragmentation
>>>> increases. Benchmarking shows list_insert_sorted() consumes ~52.69%
>>>> CPU
>>>> with the freelist, compared to just 0.03% with the RB tree
>>>> (rbtree_insert.isra.0), despite performing the same sorted insert.
>>>>
>>>> This also improves performance in heavily fragmented workloads,
>>>> such as games or graphics tests that stress memory.
>>>
>>> Neat. Also please Cc intel-gfx@lists.freedesktop.org and intel-
>>> xe@lists.freedesktop.org on the next revision so our CI can pick
>>> this up.
>> Sure, I will add on v3.
>>>
>>>>
>>>> Signed-off-by: Arunpravin Paneer Selvam
>>>> <Arunpravin.PaneerSelvam@amd.com>
>>>> ---
>>>> drivers/gpu/drm/drm_buddy.c | 141
>>>> +++++++++++++++++++++++-------------
>>>> include/drm/drm_buddy.h | 39 +++++++++-
>>>> 2 files changed, 128 insertions(+), 52 deletions(-)
>>>>
>>>> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
>>>> index a1e652b7631d..19e9773b41be 100644
>>>> --- a/drivers/gpu/drm/drm_buddy.c
>>>> +++ b/drivers/gpu/drm/drm_buddy.c
>>>> @@ -31,6 +31,8 @@ static struct drm_buddy_block
>>>> *drm_block_alloc(struct drm_buddy *mm,
>>>> block->header |= order;
>>>> block->parent = parent;
>>>> + RB_CLEAR_NODE(&block->rb);
>>>> +
>>>> BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
>>>> return block;
>>>> }
>>>> @@ -41,23 +43,53 @@ static void drm_block_free(struct drm_buddy *mm,
>>>> kmem_cache_free(slab_blocks, block);
>>>> }
>>>> -static void list_insert_sorted(struct drm_buddy *mm,
>>>> - struct drm_buddy_block *block)
>>>> +static void rbtree_insert(struct drm_buddy *mm,
>>>> + struct drm_buddy_block *block)
>>>> {
>>>> + 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 drm_buddy_block *node;
>>>> - struct list_head *head;
>>>> + u64 offset;
>>>> +
>>>> + offset = drm_buddy_block_offset(block);
>>>> - head = &mm->free_list[drm_buddy_block_order(block)];
>>>> - if (list_empty(head)) {
>>>> - list_add(&block->link, head);
>>>> - return;
>>>> + while (*link) {
>>>> + parent = *link;
>>>> + node = rb_entry(parent, struct drm_buddy_block, rb);
>>>> +
>>>> + if (offset < drm_buddy_block_offset(node))
>>>> + link = &parent->rb_left;
>>>> + else
>>>> + link = &parent->rb_right;
>>>> }
>>>> - list_for_each_entry(node, head, link)
>>>> - if (drm_buddy_block_offset(block) <
>>>> drm_buddy_block_offset(node))
>>>> - break;
>>>> + rb_link_node(&block->rb, parent, link);
>>>> + rb_insert_color(&block->rb, root);
>>>> +}
>>>> +
>>>> +static void rbtree_remove(struct drm_buddy *mm,
>>>> + struct drm_buddy_block *block)
>>>> +{
>>>> + struct rb_root *root;
>>>> - __list_add(&block->link, node->link.prev, &node->link);
>>>> + root = &mm->free_tree[drm_buddy_block_order(block)];
>>>> + 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)
>>>> @@ -70,12 +102,13 @@ static void mark_cleared(struct
>>>> drm_buddy_block *block)
>>>> block->header |= DRM_BUDDY_HEADER_CLEAR;
>>>> }
>>>> -static void mark_allocated(struct drm_buddy_block *block)
>>>> +static void mark_allocated(struct drm_buddy *mm,
>>>> + struct drm_buddy_block *block)
>>>> {
>>>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>>>> block->header |= DRM_BUDDY_ALLOCATED;
>>>> - list_del(&block->link);
>>>> + rbtree_remove(mm, block);
>>>> }
>>>> static void mark_free(struct drm_buddy *mm,
>>>> @@ -84,15 +117,16 @@ static void mark_free(struct drm_buddy *mm,
>>>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>>>> block->header |= DRM_BUDDY_FREE;
>>>> - list_insert_sorted(mm, block);
>>>> + rbtree_insert(mm, block);
>>>> }
>>>> -static void mark_split(struct drm_buddy_block *block)
>>>> +static void mark_split(struct drm_buddy *mm,
>>>> + struct drm_buddy_block *block)
>>>> {
>>>> block->header &= ~DRM_BUDDY_HEADER_STATE;
>>>> block->header |= DRM_BUDDY_SPLIT;
>>>> - list_del(&block->link);
>>>> + rbtree_remove(mm, block);
>>>> }
>>>> static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
>>>> @@ -148,7 +182,7 @@ static unsigned int __drm_buddy_free(struct
>>>> drm_buddy *mm,
>>>> mark_cleared(parent);
>>>> }
>>>> - list_del(&buddy->link);
>>>> + rbtree_remove(mm, buddy);
>>>> if (force_merge && drm_buddy_block_is_clear(buddy))
>>>> mm->clear_avail -= drm_buddy_block_size(mm, buddy);
>>>> @@ -179,12 +213,17 @@ static int __force_merge(struct drm_buddy *mm,
>>>> return -EINVAL;
>>>> for (i = min_order - 1; i >= 0; i--) {
>>>> - struct drm_buddy_block *block, *prev;
>>>> + struct drm_buddy_block *block, *prev_block, *first_block;
>>>> +
>>>> + first_block = rb_entry(rb_first(&mm->free_tree[i]), struct
>>>> drm_buddy_block, rb);
>>>> - list_for_each_entry_safe_reverse(block, prev, &mm-
>>>> >free_list[i], link) {
>>>> + for_each_rb_entry_reverse_safe(block, prev_block, &mm-
>>>> >free_tree[i], rb) {
>>>> struct drm_buddy_block *buddy;
>>>> u64 block_start, block_end;
>>>> + if (RB_EMPTY_NODE(&block->rb))
>>>> + break;
>>>
>>> If we got the block from the rb tree, can it be empty here?
>>
>> I saw a crash earlier without this check while running graphics
>> workloads, but it is not happening now. I will
>>
>> test with more workloads and remove it if everything looks fine.
>>
>>>
>>>> +
>>>> if (!block->parent)
>>>> continue;
>>>> @@ -206,10 +245,14 @@ static int __force_merge(struct drm_buddy *mm,
>>>> * block in the next iteration as we would free the
>>>> * buddy block as part of the free function.
>>>> */
>>>> - if (prev == buddy)
>>>> - prev = list_prev_entry(prev, link);
>>>> + 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);
>>>> + }
>>>> - list_del(&block->link);
>>>> + rbtree_remove(mm, block);
>>>> if (drm_buddy_block_is_clear(block))
>>>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>>>> @@ -258,14 +301,14 @@ int drm_buddy_init(struct drm_buddy *mm,
>>>> u64 size, u64 chunk_size)
>>>> BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
>>>> - mm->free_list = kmalloc_array(mm->max_order + 1,
>>>> - sizeof(struct list_head),
>>>> + mm->free_tree = kmalloc_array(mm->max_order + 1,
>>>> + sizeof(struct rb_root),
>>>> GFP_KERNEL);
>>>> - if (!mm->free_list)
>>>> + if (!mm->free_tree)
>>>> return -ENOMEM;
>>>> for (i = 0; i <= mm->max_order; ++i)
>>>> - INIT_LIST_HEAD(&mm->free_list[i]);
>>>> + mm->free_tree[i] = RB_ROOT;
>>>> mm->n_roots = hweight64(size);
>>>> @@ -273,7 +316,7 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>>>> size, u64 chunk_size)
>>>> sizeof(struct drm_buddy_block *),
>>>> GFP_KERNEL);
>>>> if (!mm->roots)
>>>> - goto out_free_list;
>>>> + goto out_free_tree;
>>>> offset = 0;
>>>> i = 0;
>>>> @@ -312,8 +355,8 @@ int drm_buddy_init(struct drm_buddy *mm, u64
>>>> size, u64 chunk_size)
>>>> while (i--)
>>>> drm_block_free(mm, mm->roots[i]);
>>>> kfree(mm->roots);
>>>> -out_free_list:
>>>> - kfree(mm->free_list);
>>>> +out_free_tree:
>>>> + kfree(mm->free_tree);
>>>> return -ENOMEM;
>>>> }
>>>> EXPORT_SYMBOL(drm_buddy_init);
>>>> @@ -323,7 +366,7 @@ EXPORT_SYMBOL(drm_buddy_init);
>>>> *
>>>> * @mm: DRM buddy manager to free
>>>> *
>>>> - * Cleanup memory manager resources and the freelist
>>>> + * Cleanup memory manager resources and the freetree
>>>> */
>>>> void drm_buddy_fini(struct drm_buddy *mm)
>>>> {
>>>> @@ -350,7 +393,7 @@ void drm_buddy_fini(struct drm_buddy *mm)
>>>> WARN_ON(mm->avail != mm->size);
>>>> kfree(mm->roots);
>>>> - kfree(mm->free_list);
>>>> + kfree(mm->free_tree);
>>>> }
>>>> EXPORT_SYMBOL(drm_buddy_fini);
>>>> @@ -383,7 +426,7 @@ static int split_block(struct drm_buddy *mm,
>>>> clear_reset(block);
>>>> }
>>>> - mark_split(block);
>>>> + mark_split(mm, block);
>>>> return 0;
>>>> }
>>>> @@ -598,7 +641,7 @@ get_maxblock(struct drm_buddy *mm, unsigned int
>>>> order,
>>>> for (i = order; i <= mm->max_order; ++i) {
>>>> struct drm_buddy_block *tmp_block;
>>>> - list_for_each_entry_reverse(tmp_block,
>>>> &mm->free_list[i], link) {
>>>> + for_each_rb_entry_reverse(tmp_block, &mm->free_tree[i], rb) {
>>>> if (block_incompatible(tmp_block, flags))
>>>> continue;
>>>> @@ -624,7 +667,7 @@ get_maxblock(struct drm_buddy *mm, unsigned
>>>> int order,
>>>> }
>>>> static struct drm_buddy_block *
>>>> -alloc_from_freelist(struct drm_buddy *mm,
>>>> +alloc_from_freetree(struct drm_buddy *mm,
>>>> unsigned int order,
>>>> unsigned long flags)
>>>> {
>>>> @@ -641,7 +684,7 @@ alloc_from_freelist(struct drm_buddy *mm,
>>>> for (tmp = order; tmp <= mm->max_order; ++tmp) {
>>>> struct drm_buddy_block *tmp_block;
>>>> - list_for_each_entry_reverse(tmp_block, &mm-
>>>> >free_list[tmp], link) {
>>>> + for_each_rb_entry_reverse(tmp_block, &mm-
>>>> >free_tree[tmp], rb) {
>>>> if (block_incompatible(tmp_block, flags))
>>>> continue;
>>>> @@ -657,10 +700,8 @@ alloc_from_freelist(struct drm_buddy *mm,
>>>> if (!block) {
>>>> /* Fallback method */
>>>> for (tmp = order; tmp <= mm->max_order; ++tmp) {
>>>> - if (!list_empty(&mm->free_list[tmp])) {
>>>> - block = list_last_entry(&mm->free_list[tmp],
>>>> - struct drm_buddy_block,
>>>> - link);
>>>> + if (!rbtree_is_empty(mm, tmp)) {
>>>> + block = rbtree_last_entry(mm, tmp);
>>>> if (block)
>>>> break;
>>>> }
>>>> @@ -728,7 +769,7 @@ static int __alloc_range(struct drm_buddy *mm,
>>>> if (contains(start, end, block_start, block_end)) {
>>>> if (drm_buddy_block_is_free(block)) {
>>>> - mark_allocated(block);
>>>> + mark_allocated(mm, block);
>>>> total_allocated += drm_buddy_block_size(mm, block);
>>>> mm->avail -= drm_buddy_block_size(mm, block);
>>>> if (drm_buddy_block_is_clear(block))
>>>> @@ -806,7 +847,6 @@ static int __alloc_contig_try_harder(struct
>>>> drm_buddy *mm,
>>>> {
>>>> u64 rhs_offset, lhs_offset, lhs_size, filled;
>>>> struct drm_buddy_block *block;
>>>> - struct list_head *list;
>>>> LIST_HEAD(blocks_lhs);
>>>> unsigned long pages;
>>>> unsigned int order;
>>>> @@ -819,11 +859,10 @@ static int __alloc_contig_try_harder(struct
>>>> drm_buddy *mm,
>>>> if (order == 0)
>>>> return -ENOSPC;
>>>> - list = &mm->free_list[order];
>>>> - if (list_empty(list))
>>>> + if (rbtree_is_empty(mm, order))
>>>> return -ENOSPC;
>>>> - list_for_each_entry_reverse(block, list, link) {
>>>> + 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,
>>>> @@ -933,7 +972,7 @@ int drm_buddy_block_trim(struct drm_buddy *mm,
>>>> list_add(&block->tmp_link, &dfs);
>>>> err = __alloc_range(mm, &dfs, new_start, new_size, blocks,
>>>> NULL);
>>>> if (err) {
>>>> - mark_allocated(block);
>>>> + mark_allocated(mm, block);
>>>> mm->avail -= drm_buddy_block_size(mm, block);
>>>> if (drm_buddy_block_is_clear(block))
>>>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>>>> @@ -956,8 +995,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
>>>> return __drm_buddy_alloc_range_bias(mm, start, end,
>>>> order, flags);
>>>> else
>>>> - /* Allocate from freelist */
>>>> - return alloc_from_freelist(mm, order, flags);
>>>> + /* Allocate from freetree */
>>>> + return alloc_from_freetree(mm, order, flags);
>>>> }
>>>> /**
>>>> @@ -974,8 +1013,8 @@ __drm_buddy_alloc_blocks(struct drm_buddy *mm,
>>>> * alloc_range_bias() called on range limitations, which traverses
>>>> * the tree and returns the desired block.
>>>> *
>>>> - * alloc_from_freelist() called when *no* range restrictions
>>>> - * are enforced, which picks the block from the freelist.
>>>> + * alloc_from_freetree() called when *no* range restrictions
>>>> + * are enforced, which picks the block from the freetree.
>>>> *
>>>> * Returns:
>>>> * 0 on success, error code on failure.
>>>> @@ -1077,7 +1116,7 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
>>>> }
>>>> } while (1);
>>>> - mark_allocated(block);
>>>> + mark_allocated(mm, block);
>>>> mm->avail -= drm_buddy_block_size(mm, block);
>>>> if (drm_buddy_block_is_clear(block))
>>>> mm->clear_avail -= drm_buddy_block_size(mm, block);
>>>> @@ -1161,7 +1200,7 @@ void drm_buddy_print(struct drm_buddy *mm,
>>>> struct drm_printer *p)
>>>> struct drm_buddy_block *block;
>>>> u64 count = 0, free;
>>>> - list_for_each_entry(block, &mm->free_list[order], link) {
>>>> + for_each_rb_entry(block, &mm->free_tree[order], rb) {
>>>> BUG_ON(!drm_buddy_block_is_free(block));
>>>> count++;
>>>> }
>>>> diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
>>>> index 9689a7c5dd36..a64d108a33b7 100644
>>>> --- a/include/drm/drm_buddy.h
>>>> +++ b/include/drm/drm_buddy.h
>>>> @@ -10,6 +10,7 @@
>>>> #include <linux/list.h>
>>>> #include <linux/slab.h>
>>>> #include <linux/sched.h>
>>>> +#include <linux/rbtree.h>
>>>> #include <drm/drm_print.h>
>>>> @@ -22,6 +23,41 @@
>>>> start__ >= max__ || size__ > max__ - start__; \
>>>> })
>>>> +/*
>>>> + * for_each_rb_entry() - iterate over an RB tree in order
>>>> + * @pos: the struct type * to use as a loop cursor
>>>> + * @root: pointer to struct rb_root to iterate
>>>> + * @member: name of the rb_node field within the struct
>>>> + */
>>>> +#define for_each_rb_entry(pos, root, member) \
>>>> + for (pos = rb_entry_safe(rb_first(root), typeof(*pos), member); \
>>>> + pos; \
>>>> + pos = rb_entry_safe(rb_next(&(pos)->member),
>>>> typeof(*pos), member))
>>>> +
>>>> +/*
>>>> + * for_each_rb_entry_reverse() - iterate over an RB tree in
>>>> reverse order
>>>> + * @pos: the struct type * to use as a loop cursor
>>>> + * @root: pointer to struct rb_root to iterate
>>>> + * @member: name of the rb_node field within the struct
>>>> + */
>>>> +#define for_each_rb_entry_reverse(pos, root, member) \
>>>> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member); \
>>>> + pos; \
>>>> + pos = rb_entry_safe(rb_prev(&(pos)->member),
>>>> typeof(*pos), member))
>>>> +
>>>> +/**
>>>> + * for_each_rb_entry_reverse_safe() - safely iterate over an RB
>>>> tree in reverse order
>>>> + * @pos: the struct type * to use as a loop cursor.
>>>> + * @n: another struct type * to use as temporary storage.
>>>> + * @root: pointer to struct rb_root to iterate.
>>>> + * @member: name of the rb_node field within the struct.
>>>> + */
>>>> +#define for_each_rb_entry_reverse_safe(pos, n, root, member) \
>>>
>>> Would it make sense to give these a less generic name? Something
>>> like for_each_rb_free_block_* ?
>>>
>>> Also should this be exported or rather kept within .c?
>> yes, I will change it.
>>>
>>>> + for (pos = rb_entry_safe(rb_last(root), typeof(*pos), member), \
>>>> + n = pos ? rb_entry_safe(rb_prev(&(pos)->member),
>>>> typeof(*pos), member) : NULL; \
>>>> + pos; \
>>>> + pos = n, n = pos ? rb_entry_safe(rb_prev(&(pos)->member),
>>>> typeof(*pos), member) : NULL)
>>>
>>>
>>>> +
>>>> #define DRM_BUDDY_RANGE_ALLOCATION BIT(0)
>>>> #define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)
>>>> #define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)
>>>> @@ -53,6 +89,7 @@ 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;
>>>
>>> I think we can be slippery here and make this a union? They should
>>> be mutually exclusive AFAICT?
>>
>> AFAIK, we need both, rb_node rb is for handling free blocks and the
>> list_head link for adding the allocated blocks into
>>
>> the driver's list.
>
> At a given time I think it is either on the free rb or user block
> list, not both at the same time, given that a block can't be free and
> allocated? Just thinking if there is an easy way to trim the size a
> bit, given that we are adding an entire rb_node, and there can be many
> of these of these blocks around.
yes, you are right. I will add union for free rb and user block list.
>
>>
>>>
>>>> struct list_head tmp_link;
>>>
>>> Otherwise it should be possible to get rid of this instead, and just
>>> re-use link? Could be done as separate patch, if this makes sense.
>>
>> I think we cannot use link here since it is needed to add the
>> allocated blocks to the driver's list and tmp_link is already used in
>>
>> alloc_range() and alloc_range_bias().
>
> Yeah, I don't this will work, but union might still be an option instead.
sure, we can make union for rb and list.
Regards,
Arun.
>
>
>>
>> Regards,
>>
>> Arun.
>>
>>>
>>>> };
>>>> @@ -68,7 +105,7 @@ struct drm_buddy_block {
>>>> */
>>>> struct drm_buddy {
>>>> /* Maintain a free list for each order. */
>>>> - struct list_head *free_list;
>>>> + struct rb_root *free_tree;
>>>> /*
>>>> * Maintain explicit binary tree(s) to track the allocation
>>>> of the
>>>
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees
2025-08-14 11:11 ` Matthew Auld
@ 2025-08-20 12:56 ` Arunpravin Paneer Selvam
0 siblings, 0 replies; 9+ messages in thread
From: Arunpravin Paneer Selvam @ 2025-08-20 12:56 UTC (permalink / raw)
To: Matthew Auld, christian.koenig, dri-devel, amd-gfx; +Cc: alexander.deucher
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@amd.com>
>> Suggested-by: Matthew Auld <matthew.auld@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
>
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2025-08-20 12:57 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-07-24 10:46 [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree Arunpravin Paneer Selvam
2025-07-24 10:46 ` [PATCH v2 2/2] drm/buddy: Separate clear and dirty free block trees Arunpravin Paneer Selvam
2025-08-13 13:56 ` Christian König
2025-08-14 11:11 ` Matthew Auld
2025-08-20 12:56 ` Arunpravin Paneer Selvam
2025-08-14 10:45 ` [PATCH v2 1/2] drm/buddy: Optimize free block management with RB tree Matthew Auld
2025-08-20 7:56 ` Arunpravin Paneer Selvam
2025-08-20 10:14 ` Matthew Auld
2025-08-20 10:37 ` Arunpravin Paneer Selvam
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).