Re: [PATCH v5 1/3] drm/buddy: Optimize free block management with RB tree

[Peter Zijlstra <peterz@infradead.org>]

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.