On Tue, Sep 02, 2025 at 12:26:04AM +0530, 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).
Did you consider the interval tree?
@@ -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;elselink = &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 inline bool __drm_bb_less(const struct drm_buddy_block *a, const struct drm_buddy_block *b) { return drm_buddy_block_offset(a) < drm_buddy_block_offset(b); }
#define __node_2_drm_bb(node) rb_entry((node), struct drm_buddy_block, rb)
static inline bool rb_drm_bb_less(struct rb_node *a, const struct rb_node *b) { return __drm_bb_less(__node_2_drm_bb(a), __node_2_drm_bb(b)); }
static void rbtree_insert(struct drm_buddy *mm, struct drm_buddy_block *block) { rb_add(block->rb, &mm->free_tree[drm_buddy_block_order(block)], rb_drm_bb_less); }
+static void rbtree_remove(struct drm_buddy *mm,
struct drm_buddy_block *block)+{
- struct rb_root *root;
- root = &mm->free_tree[drm_buddy_block_order(block)];
- rb_erase(&block->rb, root);
- __list_add(&block->link, node->link.prev, &node->link);
- 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;
+}
rb_add_cached() caches the leftmost entry, if you invert the key, the last is first.
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 8d2ba3749866..17190bb4837c 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -79,6 +79,62 @@ static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent ____ptr ? rb_entry(____ptr, type, member) : NULL; \ }) +/**
- rbtree_for_each_entry - iterate in-order over rb_root of given type
- @pos: the 'type *' to use as a loop cursor.
- @root: 'rb_root *' of the rbtree.
- @member: the name of the rb_node field within 'type'.
- */
+#define rbtree_for_each_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))+/**
- rbtree_reverse_for_each_entry - iterate in reverse in-order over rb_root
- of given type
- @pos: the 'type *' to use as a loop cursor.
- @root: 'rb_root *' of the rbtree.
- @member: the name of the rb_node field within 'type'.
- */
+#define rbtree_reverse_for_each_entry(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))+/**
- rbtree_for_each_entry_safe - iterate in-order over rb_root safe against removal
- @pos: the 'type *' to use as a loop cursor
- @n: another 'type *' to use as temporary storage
- @root: 'rb_root *' of the rbtree
- @member: the name of the rb_node field within 'type'
- */
+#define rbtree_for_each_entry_safe(pos, n, root, member) \
- for ((pos) = rb_entry_safe(rb_first(root), typeof(*(pos)), member), \
(n) = (pos) ? rb_entry_safe(rb_next(&(pos)->member), typeof(*(pos)), member) : NULL; \(pos); \(pos) = (n), \(n) = (pos) ? rb_entry_safe(rb_next(&(pos)->member), typeof(*(pos)), member) : NULL)+/**
- rbtree_reverse_for_each_entry_safe - iterate in reverse in-order over rb_root
- safe against removal
- @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 rbtree_reverse_for_each_entry_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)
Not really a fan of these. That's typically a sign you're doing it wrong. Full tree iteration is actually slower than linked list.