On 09.09.25 16:05, Peter Zijlstra wrote:
On Tue, Sep 09, 2025 at 02:04:30PM +0200, Christian König wrote:
Hi Arun,
On 09.09.25 11:56, Arunpravin Paneer Selvam wrote: [SNIP]
+/**
- 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)As far as I know exactly that operation does not work on an R/B tree.
See the _safe() variants of the for_each_ macros are usually used to iterate over a container while being able to remove entries.
But because of the potential re-balance storing just the next entry is not sufficient for an R/B tree to do that as far as I know.
Please explain how exactly you want to use this macro.
So I don't much like these iterators; I've said so before. Either we should introduce a properly threaded rb-tree (where the NULL child pointers encode a linked list), or simply keep a list_head next to the rb_node and use that.
I agree, something is clearly fishy here.
The rb_{next,prev}() things are O(ln n), in the worst case they do a full traversal up the tree and a full traversal down the other branch.
Yeah from the logic that is exactly what is supposed to happen in the __force_merge() function.
The question is rather why does that function exists in the first place? The operation doesn't look logical to me.
For drm_buddy_reset_clear() and drm_buddy_fini() we should use rbtree_postorder_for_each_entry_safe() instead.
And during normal allocation __force_merge() should never be used.
That said; given 'next' will remain an existing node, only the 'pos' node gets removed, rb_next() will still work correctly, even in the face of rebalance.
Good to know!
Regards, Christian.