Messages in this thread | | | Date | Thu, 30 Apr 2020 10:46:17 +0200 | From | Peter Zijlstra <> | Subject | Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers |
| |
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.
| |