On 9/9/2025 7:35 PM, 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.
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.
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.
Sorry for the delay. I have been discussing with Christian and testing a
few code
changes. Maintaining a sorted list_head alongside each rb_node is expensive,
which is the main reason we are moving from a list to an rbtree. In the
force_merge()
function, we only call this during normal allocation to iterate once or
twice and merge
the required blocks, not the entire tree. Therefore, rb_prev is
sufficient, and want to
avoid adding unnecessary complexity for this simple operation.
Therefore, I have removed
all the newly added macros in v7.
A full traversal of force_merge() is only needed during the buddy
allocator's fini() operation, and in that
case, any slowness or timing overhead is not critical.
Thanks,
Arun.
