Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

[Peter Zijlstra <peterz@infradead.org>]

On Wed, Apr 29, 2020 at 06:04:05PM -0700, Michel Lespinasse wrote:
> Hi Peter,
> 
> On Wed, Apr 29, 2020 at 05:32:59PM +0200, Peter Zijlstra wrote:
> > I've always been bothered by the endless (fragile) boilerplate for
> > rbtree, and I recently wrote some rbtree helpers for objtool and
> > figured I should lift them into the kernel and use them more widely.
> > 
> > Provide:
> > 
> > partial-order; less() based:
> >  - rb_add(): add a new entry to the rbtree
> >  - rb_add_cached(): like rb_add(), but for a rb_root_cached
> > 
> > total-order; cmp() based:
> >  - rb_find(): find an entry in an rbtree
> >  - rb_find_first(): find the first (leftmost) matching entry
> >  - rb_next_match(): continue from rb_find_first()
> >  - rb_for_each(): for loop with rb_find_first() / rb_next_match()

I appear to have failed to mention rb_find_add(), which is a bit of a
specialty, but I could imagine there being more like it the many rbtree
users out there (I count 300+ rb_link_node occurences).

> > 
> > Also make rb_add_cached() / rb_erase_cached() return true when
> > leftmost.
> > 
> > Inlining and constant propagation should see the compiler inline the
> > whole thing, including the various compare functions.
> 
> I really like the idea of this change. Also,I think it opens avenues
> for converting some users which had previously been avoiding raw rbtrees
> seemingly only because they didn't want to write this boilerplate.

Yeah; our current interface mandates you _understand_ binary trees, I
can imagine that's a step too far for some (sadly).

> Few questions:
> 
> - Adding the rb_add_cached() / rb_erase_cached() return value looks
>   like it almost belongs to a separate patch. Is this only used in
>   patch 3/7 (sched/deadline) or did I miss other uses ? Not objecting
>   to it, but it wasn't obvious to me when reading the patch what the
>   return value was for.

I can certainly add it in a separate patch; as might be evident from the
(lack) of changelogs on the whole, I basically split and posted the
thing the moment it booted. I figured I shouldn't sink more time into it
if people were going to hate it ;-)

> - Have you considered passing a cmp() function to rb_add() and
>   rb_add_cached(), and having these test cmp() < 0 rather than less() ?
>   I figure every user will need to have a cmp() function, so it'd be
>   nicer if they didn't also need a less() function, if the generated
>   code is similar (if you checked and rejected it because of bad code,
>   please just say so).

I did consider it; in fact I my original helpers had that.

The reaosn I went with less() over cmp() is that the add() vs find()
function signatures:

  bool (*less)(struct rb_node *, const struct rb_node *);
  int (*cmp)(const void *, const struct rb_node *);

differ anyway in the left-hand argument; this is 'fixable' when you
use an (on-stack) dummy object for find (as uprobes does), but that
doesn't always work, esp. when the object is big. And given you need two
functions anyway, I figured it was useful to name them differently.

If you've looked at the other patches a bit, you'll see I've implemented
both functions as 'trivial' wrappers around a single compare function in
many cases.

> Reviewed-by: Michel Lespinasse <walken@google.com>

Thanks, I suppose I'll go brush this up a bit more then.