| Message ID | 4768e17a808c754748ac9264b5de9e8f00f22380.1733850317.git.beckerlee3@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | reduce boilerplate code within btrfs | expand |
On 10.12.24 20:07, Roger L. Beckermeyer III wrote: > Adds rb_find_add_cached() as a helper function for use with > red-black trees. Used in btrfs to reduce boilerplate code. > > Reported-by: kernel test robot <lkp@intel.com> > Closes: https://lore.kernel.org/oe-kbuild-all/202412092033.josUXvY4-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412091004.4vQ7P5Kl-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090944.g3jpT1Cz-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090919.RdI1OMQg-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.LHCgRc17-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412091036.JGaCqbvL-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090921.E0n0Ioce-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090958.CtUdYRwP-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.Cg7LuOhS-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090910.F5gin2Tv-lkp@intel.com/ Don't add the Closes: tag here. It's a change between v1 and v2 which does not need to go to the git history. > Suggested-by: Josef Bacik <josef@toxicpanda.com> > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
On Tue, Dec 10, 2024 at 01:06:07PM -0600, Roger L. Beckermeyer III wrote: > Adds rb_find_add_cached() as a helper function for use with > red-black trees. Used in btrfs to reduce boilerplate code. > > Reported-by: kernel test robot <lkp@intel.com> > Closes: https://lore.kernel.org/oe-kbuild-all/202412092033.josUXvY4-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412091004.4vQ7P5Kl-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090944.g3jpT1Cz-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090919.RdI1OMQg-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.LHCgRc17-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412091036.JGaCqbvL-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090921.E0n0Ioce-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090958.CtUdYRwP-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.Cg7LuOhS-lkp@intel.com/ > Closes: https://lore.kernel.org/oe-kbuild-all/202412090910.F5gin2Tv-lkp@intel.com/ > Suggested-by: Josef Bacik <josef@toxicpanda.com> > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> > --- > include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ This is generic code and you need to CC the right people to get their ack and reviewed-by. Alternatively we can have our own copy in fs/btrfs/misc.h and then move it to the generic code.
在 2024/12/13 03:16, Roger L. Beckermeyer III 写道: > Adds rb_find_add_cached() as a helper function for use with > red-black trees. Used in btrfs to reduce boilerplate code. I won't call it boilerplate code though, it's just to utilize the cached rb tree feature as an optimization. And since rbtree is a tree-wide infrastructure, you need to be more persuasive to add a new interface. Yes, btrfs is utilizing this cached rb tree, but since you're adding a new tree-wide interface, it will be much better to find another driver/subsystem that can benefit from the new interface. > > Suggested-by: Josef Bacik <josef@toxicpanda.com> > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> > --- > include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ > 1 file changed, 37 insertions(+) > > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h > index 7c173aa64e1e..0d4444c0cfb3 100644 > --- a/include/linux/rbtree.h > +++ b/include/linux/rbtree.h > @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree, > rb_insert_color(node, tree); > } > > +/** > + * rb_find_add_cached() - find equivalent @node in @tree, or add @node > + * @node: node to look-for / insert > + * @tree: tree to search / modify > + * @cmp: operator defining the node order > + * > + * Returns the rb_node matching @node, or NULL when no match is found and @node > + * is inserted. > + */ > +static __always_inline struct rb_node * > +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree, > + int (*cmp)(struct rb_node *, const struct rb_node *)) This function is almost the same as rb_add_cached(), the only difference is the extra handling for the cmp function returning 0. So I'm wondering if it's possible to enhance rb_add_cached(), or even refactor it so there can be a shared core function and rb_add_cached() and rb_find_add_cached() can reuse the same function. Thanks, Qu > +{ > + bool leftmost = true; > + struct rb_node **link = &tree->rb_root.rb_node; > + struct rb_node *parent = NULL; > + int c; > + > + while (*link) { > + parent = *link; > + c = cmp(node, parent); > + > + if (c < 0) { > + link = &parent->rb_left; > + } else if (c > 0) { > + link = &parent->rb_right; > + leftmost = false; > + } else { > + return parent; > + } > + } > + > + rb_link_node(node, parent, link); > + rb_insert_color_cached(node, tree, leftmost); > + return NULL; > +} > + > /** > * rb_find_add() - find equivalent @node in @tree, or add @node > * @node: node to look-for / insert
On Fri, Dec 13, 2024 at 05:51:44PM +1030, Qu Wenruo wrote: > > > 在 2024/12/13 03:16, Roger L. Beckermeyer III 写道: > > Adds rb_find_add_cached() as a helper function for use with > > red-black trees. Used in btrfs to reduce boilerplate code. > > I won't call it boilerplate code though, it's just to utilize the cached > rb tree feature as an optimization. Nah, all this is boilerplate :-) > > > > Suggested-by: Josef Bacik <josef@toxicpanda.com> > > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> > > --- > > include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ > > 1 file changed, 37 insertions(+) > > > > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h > > index 7c173aa64e1e..0d4444c0cfb3 100644 > > --- a/include/linux/rbtree.h > > +++ b/include/linux/rbtree.h > > @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree, > > rb_insert_color(node, tree); > > } > > > > +/** > > + * rb_find_add_cached() - find equivalent @node in @tree, or add @node > > + * @node: node to look-for / insert > > + * @tree: tree to search / modify > > + * @cmp: operator defining the node order > > + * > > + * Returns the rb_node matching @node, or NULL when no match is found and @node > > + * is inserted. > > + */ > > +static __always_inline struct rb_node * > > +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree, > > + int (*cmp)(struct rb_node *, const struct rb_node *)) > > This function is almost the same as rb_add_cached(), the only difference > is the extra handling for the cmp function returning 0. > > So I'm wondering if it's possible to enhance rb_add_cached(), or even > refactor it so there can be a shared core function and rb_add_cached() > and rb_find_add_cached() can reuse the same function. Nope, rb_add_cached() can add multiple entries with the same key, rb_find_add() cannot. Also, note that all these things are effectively 'templates', they generate code at the call site. The cmp() function as required for find_add() is a tri-state return and generates more logic than the binary less() required for add().
On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote: > Adds rb_find_add_cached() as a helper function for use with > red-black trees. Used in btrfs to reduce boilerplate code. > > Suggested-by: Josef Bacik <josef@toxicpanda.com> > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> > --- > include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ > 1 file changed, 37 insertions(+) > > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h > index 7c173aa64e1e..0d4444c0cfb3 100644 > --- a/include/linux/rbtree.h > +++ b/include/linux/rbtree.h > @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree, > rb_insert_color(node, tree); > } > > +/** > + * rb_find_add_cached() - find equivalent @node in @tree, or add @node > + * @node: node to look-for / insert > + * @tree: tree to search / modify > + * @cmp: operator defining the node order > + * > + * Returns the rb_node matching @node, or NULL when no match is found and @node > + * is inserted. > + */ > +static __always_inline struct rb_node * > +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree, > + int (*cmp)(struct rb_node *, const struct rb_node *)) > +{ > + bool leftmost = true; > + struct rb_node **link = &tree->rb_root.rb_node; > + struct rb_node *parent = NULL; > + int c; > + > + while (*link) { > + parent = *link; > + c = cmp(node, parent); > + > + if (c < 0) { > + link = &parent->rb_left; > + } else if (c > 0) { > + link = &parent->rb_right; > + leftmost = false; > + } else { > + return parent; > + } > + } > + > + rb_link_node(node, parent, link); > + rb_insert_color_cached(node, tree, leftmost); > + return NULL; > +} > + > /** > * rb_find_add() - find equivalent @node in @tree, or add @node > * @node: node to look-for / insert > -- > 2.45.2 >
在 2024/12/13 19:36, Peter Zijlstra 写道: > On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote: >> Adds rb_find_add_cached() as a helper function for use with >> red-black trees. Used in btrfs to reduce boilerplate code. >> >> Suggested-by: Josef Bacik <josef@toxicpanda.com> >> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> > > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> I guess it's fine to merge this change through btrfs tree? Just curious about the existing cmp() and less() functions, as they only accept the exist node as const. I'm wondering if this is intentional to allow the less/cmp() functions to modify the new node if needed. As I normally assume such cmp()/less() should never touch any node nor its entries. Thanks, Qu > >> --- >> include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ >> 1 file changed, 37 insertions(+) >> >> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h >> index 7c173aa64e1e..0d4444c0cfb3 100644 >> --- a/include/linux/rbtree.h >> +++ b/include/linux/rbtree.h >> @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree, >> rb_insert_color(node, tree); >> } >> >> +/** >> + * rb_find_add_cached() - find equivalent @node in @tree, or add @node >> + * @node: node to look-for / insert >> + * @tree: tree to search / modify >> + * @cmp: operator defining the node order >> + * >> + * Returns the rb_node matching @node, or NULL when no match is found and @node >> + * is inserted. >> + */ >> +static __always_inline struct rb_node * >> +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree, >> + int (*cmp)(struct rb_node *, const struct rb_node *)) >> +{ >> + bool leftmost = true; >> + struct rb_node **link = &tree->rb_root.rb_node; >> + struct rb_node *parent = NULL; >> + int c; >> + >> + while (*link) { >> + parent = *link; >> + c = cmp(node, parent); >> + >> + if (c < 0) { >> + link = &parent->rb_left; >> + } else if (c > 0) { >> + link = &parent->rb_right; >> + leftmost = false; >> + } else { >> + return parent; >> + } >> + } >> + >> + rb_link_node(node, parent, link); >> + rb_insert_color_cached(node, tree, leftmost); >> + return NULL; >> +} >> + >> /** >> * rb_find_add() - find equivalent @node in @tree, or add @node >> * @node: node to look-for / insert >> -- >> 2.45.2 >> >
On Tue, Dec 17, 2024 at 08:43:26AM +1030, Qu Wenruo wrote: > > > 在 2024/12/13 19:36, Peter Zijlstra 写道: > > On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote: > > > Adds rb_find_add_cached() as a helper function for use with > > > red-black trees. Used in btrfs to reduce boilerplate code. > > > > > > Suggested-by: Josef Bacik <josef@toxicpanda.com> > > > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> > > > > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> > > I guess it's fine to merge this change through btrfs tree? Yeah, I think so. I don't think there's anything else pending for this file -- its not touched much. > > Just curious about the existing cmp() and less() functions, as they only > accept the exist node as const. > > I'm wondering if this is intentional to allow the less/cmp() functions > to modify the new node if needed. > As I normally assume such cmp()/less() should never touch any node nor > its entries. Oh yeah, they probably should not. I think it's just because the callchain as a whole does not have const on the new node (for obvious raisins), and I failed to put it on for the comparators. You could add it (and fix up the whole tree) and see if anything comes apart.
在 2024/12/17 08:52, Peter Zijlstra 写道: > On Tue, Dec 17, 2024 at 08:43:26AM +1030, Qu Wenruo wrote: >> >> >> 在 2024/12/13 19:36, Peter Zijlstra 写道: >>> On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote: >>>> Adds rb_find_add_cached() as a helper function for use with >>>> red-black trees. Used in btrfs to reduce boilerplate code. >>>> >>>> Suggested-by: Josef Bacik <josef@toxicpanda.com> >>>> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> >>> >>> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> >> >> I guess it's fine to merge this change through btrfs tree? > > Yeah, I think so. I don't think there's anything else pending for this > file -- its not touched much. > >> >> Just curious about the existing cmp() and less() functions, as they only >> accept the exist node as const. >> >> I'm wondering if this is intentional to allow the less/cmp() functions >> to modify the new node if needed. >> As I normally assume such cmp()/less() should never touch any node nor >> its entries. > > Oh yeah, they probably should not. I think it's just because the > callchain as a whole does not have const on the new node (for obvious > raisins), and I failed to put it on for the comparators. > > You could add it (and fix up the whole tree) and see if anything comes > apart. > Thanks for confirming this. I'll make the cmp() for the new helper to accept all const parameter, and give a try to do a tree-wide cleanup to make existing cmp/less() to accept all const parameters. (pretty sure a lot of things will fall apart though). Thanks, Qu
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 7c173aa64e1e..0d4444c0cfb3 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree, rb_insert_color(node, tree); } +/** + * rb_find_add_cached() - find equivalent @node in @tree, or add @node + * @node: node to look-for / insert + * @tree: tree to search / modify + * @cmp: operator defining the node order + * + * Returns the rb_node matching @node, or NULL when no match is found and @node + * is inserted. + */ +static __always_inline struct rb_node * +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree, + int (*cmp)(struct rb_node *, const struct rb_node *)) +{ + bool leftmost = true; + struct rb_node **link = &tree->rb_root.rb_node; + struct rb_node *parent = NULL; + int c; + + while (*link) { + parent = *link; + c = cmp(node, parent); + + if (c < 0) { + link = &parent->rb_left; + } else if (c > 0) { + link = &parent->rb_right; + leftmost = false; + } else { + return parent; + } + } + + rb_link_node(node, parent, link); + rb_insert_color_cached(node, tree, leftmost); + return NULL; +} + /** * rb_find_add() - find equivalent @node in @tree, or add @node * @node: node to look-for / insert
Adds rb_find_add_cached() as a helper function for use with red-black trees. Used in btrfs to reduce boilerplate code. Reported-by: kernel test robot <lkp@intel.com> Closes: https://lore.kernel.org/oe-kbuild-all/202412092033.josUXvY4-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412091004.4vQ7P5Kl-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412090944.g3jpT1Cz-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412090919.RdI1OMQg-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.LHCgRc17-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412091036.JGaCqbvL-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412090921.E0n0Ioce-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412090958.CtUdYRwP-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.Cg7LuOhS-lkp@intel.com/ Closes: https://lore.kernel.org/oe-kbuild-all/202412090910.F5gin2Tv-lkp@intel.com/ Suggested-by: Josef Bacik <josef@toxicpanda.com> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com> --- include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+)