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()
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.
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
---
include/linux/rbtree.h | 127 +++++++++++++++++++++++++++++++++++++++++-
tools/include/linux/rbtree.h | 129 ++++++++++++++++++++++++++++++++++++++++++-
tools/objtool/elf.c | 63 ++-------------------
3 files changed, 257 insertions(+), 62 deletions(-)
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
rb_insert_color(node, &root->rb_root);
}
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
struct rb_root_cached *root)
{
- if (root->rb_leftmost == node)
+ bool leftmost = false;
+
+ if (root->rb_leftmost == node) {
root->rb_leftmost = rb_next(node);
+ leftmost = true;
+ }
rb_erase(node, &root->rb_root);
+
+ return leftmost;
}
static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -158,4 +164,121 @@ static inline void rb_replace_node_cache
rb_replace_node(victim, new, &root->rb_root);
}
+static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
+ bool (*less)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->rb_root.rb_node;
+ struct rb_node *parent = NULL;
+ bool leftmost = true;
+
+ while (*link) {
+ parent = *link;
+ if (less(node, parent)) {
+ link = &parent->rb_left;
+ } else {
+ link = &parent->rb_right;
+ leftmost = false;
+ }
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color_cached(node, tree, leftmost);
+
+ return leftmost;
+}
+
+static inline void rb_add(struct rb_root *tree, struct rb_node *node,
+ bool (*less)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->rb_node;
+ struct rb_node *parent = NULL;
+
+ while (*link) {
+ parent = *link;
+ if (less(node, parent))
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color(node, tree);
+}
+
+static inline struct rb_node *rb_find_add(struct rb_root *tree, struct rb_node *node,
+ int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->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;
+ else
+ return parent;
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color(node, tree);
+ return NULL;
+}
+
+static inline struct rb_node *rb_find(struct rb_root *tree, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ struct rb_node *node = tree->rb_node;
+
+ while (node) {
+ int c = cmp(key, node);
+ if (c < 0) {
+ node = node->rb_left;
+ } else if (c > 0) {
+ node = node->rb_right;
+ } else
+ return node;
+ }
+
+ return NULL;
+}
+
+static inline struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ struct rb_node *node = tree->rb_node;
+ struct rb_node *match = NULL;
+
+ while (node) {
+ int c = cmp(key, node);
+ if (c <= 0) {
+ if (!c)
+ match = node;
+ node = node->rb_left;
+ } else if (c > 0) {
+ node = node->rb_right;
+ }
+ }
+
+ return match;
+}
+
+static inline struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ node = rb_next(node);
+ if (node && cmp(key, node))
+ node = NULL;
+ return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+ for ((node) = rb_find_first((tree), (key), (cmp)); \
+ (node); (node) = rb_next_match((node), (key), (cmp)))
+
+
#endif /* _LINUX_RBTREE_H */
--- a/tools/include/linux/rbtree.h
+++ b/tools/include/linux/rbtree.h
@@ -135,12 +135,18 @@ static inline void rb_insert_color_cache
rb_insert_color(node, &root->rb_root);
}
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
struct rb_root_cached *root)
{
- if (root->rb_leftmost == node)
+ bool leftmost = false;
+
+ if (root->rb_leftmost == node) {
root->rb_leftmost = rb_next(node);
+ leftmost = true;
+ }
rb_erase(node, &root->rb_root);
+
+ return leftmost;
}
static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -152,4 +158,121 @@ static inline void rb_replace_node_cache
rb_replace_node(victim, new, &root->rb_root);
}
-#endif /* __TOOLS_LINUX_PERF_RBTREE_H */
+static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
+ bool (*less)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->rb_root.rb_node;
+ struct rb_node *parent = NULL;
+ bool leftmost = true;
+
+ while (*link) {
+ parent = *link;
+ if (less(node, parent)) {
+ link = &parent->rb_left;
+ } else {
+ link = &parent->rb_right;
+ leftmost = false;
+ }
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color_cached(node, tree, leftmost);
+
+ return leftmost;
+}
+
+static inline void rb_add(struct rb_root *tree, struct rb_node *node,
+ bool (*less)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->rb_node;
+ struct rb_node *parent = NULL;
+
+ while (*link) {
+ parent = *link;
+ if (less(node, parent))
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color(node, tree);
+}
+
+static inline struct rb_node *rb_find_add(struct rb_root *tree, struct rb_node *node,
+ int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->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;
+ else
+ return parent;
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color(node, tree);
+ return NULL;
+}
+
+static inline struct rb_node *rb_find(struct rb_root *tree, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ struct rb_node *node = tree->rb_node;
+
+ while (node) {
+ int c = cmp(key, node);
+ if (c < 0) {
+ node = node->rb_left;
+ } else if (c > 0) {
+ node = node->rb_right;
+ } else
+ return node;
+ }
+
+ return NULL;
+}
+
+static inline struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ struct rb_node *node = tree->rb_node;
+ struct rb_node *match = NULL;
+
+ while (node) {
+ int c = cmp(key, node);
+ if (c <= 0) {
+ if (!c)
+ match = node;
+ node = node->rb_left;
+ } else if (c > 0) {
+ node = node->rb_right;
+ }
+ }
+
+ return match;
+}
+
+static inline struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ node = rb_next(node);
+ if (node && cmp(key, node))
+ node = NULL;
+ return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+ for ((node) = rb_find_first((tree), (key), (cmp)); \
+ (node); (node) = rb_next_match((node), (key), (cmp)))
+
+
+#endif /* _LINUX_RBTREE_H */
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -43,75 +43,24 @@ static void elf_hash_init(struct hlist_h
#define elf_hash_for_each_possible(name, obj, member, key) \
hlist_for_each_entry(obj, &name[hash_min(key, elf_hash_bits())], member)
-static void rb_add(struct rb_root *tree, struct rb_node *node,
- int (*cmp)(struct rb_node *, const struct rb_node *))
-{
- struct rb_node **link = &tree->rb_node;
- struct rb_node *parent = NULL;
-
- while (*link) {
- parent = *link;
- if (cmp(node, parent) < 0)
- link = &parent->rb_left;
- else
- link = &parent->rb_right;
- }
-
- rb_link_node(node, parent, link);
- rb_insert_color(node, tree);
-}
-
-static struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
- int (*cmp)(const void *key, const struct rb_node *))
-{
- struct rb_node *node = tree->rb_node;
- struct rb_node *match = NULL;
-
- while (node) {
- int c = cmp(key, node);
- if (c <= 0) {
- if (!c)
- match = node;
- node = node->rb_left;
- } else if (c > 0) {
- node = node->rb_right;
- }
- }
-
- return match;
-}
-
-static struct rb_node *rb_next_match(struct rb_node *node, const void *key,
- int (*cmp)(const void *key, const struct rb_node *))
-{
- node = rb_next(node);
- if (node && cmp(key, node))
- node = NULL;
- return node;
-}
-
-#define rb_for_each(tree, node, key, cmp) \
- for ((node) = rb_find_first((tree), (key), (cmp)); \
- (node); (node) = rb_next_match((node), (key), (cmp)))
-
-static int symbol_to_offset(struct rb_node *a, const struct rb_node *b)
+static bool symbol_to_offset(struct rb_node *a, const struct rb_node *b)
{
struct symbol *sa = rb_entry(a, struct symbol, node);
struct symbol *sb = rb_entry(b, struct symbol, node);
if (sa->offset < sb->offset)
- return -1;
+ return true;
if (sa->offset > sb->offset)
- return 1;
+ return false;
if (sa->len < sb->len)
- return -1;
+ return true;
if (sa->len > sb->len)
- return 1;
+ return false;
sa->alias = sb;
- return 0;
+ return false;
}
static int symbol_by_offset(const void *key, const struct rb_node *node)
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()
>
> 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.
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.
- 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).
Reviewed-by: Michel Lespinasse <[email protected]>
I also looked at the other commits in the series, making use of the
helpers, and they seem very reasonable but I did not give them as
thorough a look at this one.
>
> Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
> ---
> include/linux/rbtree.h | 127 +++++++++++++++++++++++++++++++++++++++++-
> tools/include/linux/rbtree.h | 129 ++++++++++++++++++++++++++++++++++++++++++-
> tools/objtool/elf.c | 63 ++-------------------
> 3 files changed, 257 insertions(+), 62 deletions(-)
>
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
> rb_insert_color(node, &root->rb_root);
> }
>
> -static inline void rb_erase_cached(struct rb_node *node,
> +static inline bool rb_erase_cached(struct rb_node *node,
> struct rb_root_cached *root)
> {
> - if (root->rb_leftmost == node)
> + bool leftmost = false;
> +
> + if (root->rb_leftmost == node) {
> root->rb_leftmost = rb_next(node);
> + leftmost = true;
> + }
> rb_erase(node, &root->rb_root);
> +
> + return leftmost;
> }
>
> static inline void rb_replace_node_cached(struct rb_node *victim,
> @@ -158,4 +164,121 @@ static inline void rb_replace_node_cache
> rb_replace_node(victim, new, &root->rb_root);
> }
>
> +static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
> + bool (*less)(struct rb_node *, const struct rb_node *))
> +{
> + struct rb_node **link = &tree->rb_root.rb_node;
> + struct rb_node *parent = NULL;
> + bool leftmost = true;
> +
> + while (*link) {
> + parent = *link;
> + if (less(node, parent)) {
> + link = &parent->rb_left;
> + } else {
> + link = &parent->rb_right;
> + leftmost = false;
> + }
> + }
> +
> + rb_link_node(node, parent, link);
> + rb_insert_color_cached(node, tree, leftmost);
> +
> + return leftmost;
> +}
> +
> +static inline void rb_add(struct rb_root *tree, struct rb_node *node,
> + bool (*less)(struct rb_node *, const struct rb_node *))
> +{
> + struct rb_node **link = &tree->rb_node;
> + struct rb_node *parent = NULL;
> +
> + while (*link) {
> + parent = *link;
> + if (less(node, parent))
> + link = &parent->rb_left;
> + else
> + link = &parent->rb_right;
> + }
> +
> + rb_link_node(node, parent, link);
> + rb_insert_color(node, tree);
> +}
> +
> +static inline struct rb_node *rb_find_add(struct rb_root *tree, struct rb_node *node,
> + int (*cmp)(struct rb_node *, const struct rb_node *))
> +{
> + struct rb_node **link = &tree->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;
> + else
> + return parent;
> + }
> +
> + rb_link_node(node, parent, link);
> + rb_insert_color(node, tree);
> + return NULL;
> +}
> +
> +static inline struct rb_node *rb_find(struct rb_root *tree, const void *key,
> + int (*cmp)(const void *key, const struct rb_node *))
> +{
> + struct rb_node *node = tree->rb_node;
> +
> + while (node) {
> + int c = cmp(key, node);
> + if (c < 0) {
> + node = node->rb_left;
> + } else if (c > 0) {
> + node = node->rb_right;
> + } else
> + return node;
> + }
> +
> + return NULL;
> +}
> +
> +static inline struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
> + int (*cmp)(const void *key, const struct rb_node *))
> +{
> + struct rb_node *node = tree->rb_node;
> + struct rb_node *match = NULL;
> +
> + while (node) {
> + int c = cmp(key, node);
> + if (c <= 0) {
> + if (!c)
> + match = node;
> + node = node->rb_left;
> + } else if (c > 0) {
> + node = node->rb_right;
> + }
> + }
> +
> + return match;
> +}
> +
> +static inline struct rb_node *rb_next_match(struct rb_node *node, const void *key,
> + int (*cmp)(const void *key, const struct rb_node *))
> +{
> + node = rb_next(node);
> + if (node && cmp(key, node))
> + node = NULL;
> + return node;
> +}
> +
> +#define rb_for_each(tree, node, key, cmp) \
> + for ((node) = rb_find_first((tree), (key), (cmp)); \
> + (node); (node) = rb_next_match((node), (key), (cmp)))
> +
> +
> #endif /* _LINUX_RBTREE_H */
> --- a/tools/include/linux/rbtree.h
> +++ b/tools/include/linux/rbtree.h
> @@ -135,12 +135,18 @@ static inline void rb_insert_color_cache
> rb_insert_color(node, &root->rb_root);
> }
>
> -static inline void rb_erase_cached(struct rb_node *node,
> +static inline bool rb_erase_cached(struct rb_node *node,
> struct rb_root_cached *root)
> {
> - if (root->rb_leftmost == node)
> + bool leftmost = false;
> +
> + if (root->rb_leftmost == node) {
> root->rb_leftmost = rb_next(node);
> + leftmost = true;
> + }
> rb_erase(node, &root->rb_root);
> +
> + return leftmost;
> }
>
> static inline void rb_replace_node_cached(struct rb_node *victim,
> @@ -152,4 +158,121 @@ static inline void rb_replace_node_cache
> rb_replace_node(victim, new, &root->rb_root);
> }
>
> -#endif /* __TOOLS_LINUX_PERF_RBTREE_H */
> +static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
> + bool (*less)(struct rb_node *, const struct rb_node *))
> +{
> + struct rb_node **link = &tree->rb_root.rb_node;
> + struct rb_node *parent = NULL;
> + bool leftmost = true;
> +
> + while (*link) {
> + parent = *link;
> + if (less(node, parent)) {
> + link = &parent->rb_left;
> + } else {
> + link = &parent->rb_right;
> + leftmost = false;
> + }
> + }
> +
> + rb_link_node(node, parent, link);
> + rb_insert_color_cached(node, tree, leftmost);
> +
> + return leftmost;
> +}
> +
> +static inline void rb_add(struct rb_root *tree, struct rb_node *node,
> + bool (*less)(struct rb_node *, const struct rb_node *))
> +{
> + struct rb_node **link = &tree->rb_node;
> + struct rb_node *parent = NULL;
> +
> + while (*link) {
> + parent = *link;
> + if (less(node, parent))
> + link = &parent->rb_left;
> + else
> + link = &parent->rb_right;
> + }
> +
> + rb_link_node(node, parent, link);
> + rb_insert_color(node, tree);
> +}
> +
> +static inline struct rb_node *rb_find_add(struct rb_root *tree, struct rb_node *node,
> + int (*cmp)(struct rb_node *, const struct rb_node *))
> +{
> + struct rb_node **link = &tree->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;
> + else
> + return parent;
> + }
> +
> + rb_link_node(node, parent, link);
> + rb_insert_color(node, tree);
> + return NULL;
> +}
> +
> +static inline struct rb_node *rb_find(struct rb_root *tree, const void *key,
> + int (*cmp)(const void *key, const struct rb_node *))
> +{
> + struct rb_node *node = tree->rb_node;
> +
> + while (node) {
> + int c = cmp(key, node);
> + if (c < 0) {
> + node = node->rb_left;
> + } else if (c > 0) {
> + node = node->rb_right;
> + } else
> + return node;
> + }
> +
> + return NULL;
> +}
> +
> +static inline struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
> + int (*cmp)(const void *key, const struct rb_node *))
> +{
> + struct rb_node *node = tree->rb_node;
> + struct rb_node *match = NULL;
> +
> + while (node) {
> + int c = cmp(key, node);
> + if (c <= 0) {
> + if (!c)
> + match = node;
> + node = node->rb_left;
> + } else if (c > 0) {
> + node = node->rb_right;
> + }
> + }
> +
> + return match;
> +}
> +
> +static inline struct rb_node *rb_next_match(struct rb_node *node, const void *key,
> + int (*cmp)(const void *key, const struct rb_node *))
> +{
> + node = rb_next(node);
> + if (node && cmp(key, node))
> + node = NULL;
> + return node;
> +}
> +
> +#define rb_for_each(tree, node, key, cmp) \
> + for ((node) = rb_find_first((tree), (key), (cmp)); \
> + (node); (node) = rb_next_match((node), (key), (cmp)))
> +
> +
> +#endif /* _LINUX_RBTREE_H */
> --- a/tools/objtool/elf.c
> +++ b/tools/objtool/elf.c
> @@ -43,75 +43,24 @@ static void elf_hash_init(struct hlist_h
> #define elf_hash_for_each_possible(name, obj, member, key) \
> hlist_for_each_entry(obj, &name[hash_min(key, elf_hash_bits())], member)
>
> -static void rb_add(struct rb_root *tree, struct rb_node *node,
> - int (*cmp)(struct rb_node *, const struct rb_node *))
> -{
> - struct rb_node **link = &tree->rb_node;
> - struct rb_node *parent = NULL;
> -
> - while (*link) {
> - parent = *link;
> - if (cmp(node, parent) < 0)
> - link = &parent->rb_left;
> - else
> - link = &parent->rb_right;
> - }
> -
> - rb_link_node(node, parent, link);
> - rb_insert_color(node, tree);
> -}
> -
> -static struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
> - int (*cmp)(const void *key, const struct rb_node *))
> -{
> - struct rb_node *node = tree->rb_node;
> - struct rb_node *match = NULL;
> -
> - while (node) {
> - int c = cmp(key, node);
> - if (c <= 0) {
> - if (!c)
> - match = node;
> - node = node->rb_left;
> - } else if (c > 0) {
> - node = node->rb_right;
> - }
> - }
> -
> - return match;
> -}
> -
> -static struct rb_node *rb_next_match(struct rb_node *node, const void *key,
> - int (*cmp)(const void *key, const struct rb_node *))
> -{
> - node = rb_next(node);
> - if (node && cmp(key, node))
> - node = NULL;
> - return node;
> -}
> -
> -#define rb_for_each(tree, node, key, cmp) \
> - for ((node) = rb_find_first((tree), (key), (cmp)); \
> - (node); (node) = rb_next_match((node), (key), (cmp)))
> -
> -static int symbol_to_offset(struct rb_node *a, const struct rb_node *b)
> +static bool symbol_to_offset(struct rb_node *a, const struct rb_node *b)
> {
> struct symbol *sa = rb_entry(a, struct symbol, node);
> struct symbol *sb = rb_entry(b, struct symbol, node);
>
> if (sa->offset < sb->offset)
> - return -1;
> + return true;
> if (sa->offset > sb->offset)
> - return 1;
> + return false;
>
> if (sa->len < sb->len)
> - return -1;
> + return true;
> if (sa->len > sb->len)
> - return 1;
> + return false;
>
> sa->alias = sb;
>
> - return 0;
> + return false;
> }
>
> static int symbol_by_offset(const void *key, const struct rb_node *node)
>
>
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
Hi,
On 29/04/20 17:32, 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()
>
> 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.
>
> Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
> ---
> include/linux/rbtree.h | 127 +++++++++++++++++++++++++++++++++++++++++-
> tools/include/linux/rbtree.h | 129 ++++++++++++++++++++++++++++++++++++++++++-
> tools/objtool/elf.c | 63 ++-------------------
> 3 files changed, 257 insertions(+), 62 deletions(-)
>
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
> rb_insert_color(node, &root->rb_root);
> }
>
> -static inline void rb_erase_cached(struct rb_node *node,
> +static inline bool rb_erase_cached(struct rb_node *node,
> struct rb_root_cached *root)
> {
> - if (root->rb_leftmost == node)
> + bool leftmost = false;
> +
> + if (root->rb_leftmost == node) {
> root->rb_leftmost = rb_next(node);
Think we need
if (root->rb_leftmost)
> + leftmost = true;
DEADLINE crashes w/o that.
> + }
> rb_erase(node, &root->rb_root);
> +
> + return leftmost;
> }
The rest looks good to me.
Thanks,
Juri
On Thu, Apr 30, 2020 at 12:28 AM Juri Lelli <[email protected]> wrote:
> > --- a/include/linux/rbtree.h
> > +++ b/include/linux/rbtree.h
> > @@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
> > rb_insert_color(node, &root->rb_root);
> > }
> >
> > -static inline void rb_erase_cached(struct rb_node *node,
> > +static inline bool rb_erase_cached(struct rb_node *node,
> > struct rb_root_cached *root)
> > {
> > - if (root->rb_leftmost == node)
> > + bool leftmost = false;
> > +
> > + if (root->rb_leftmost == node) {
> > root->rb_leftmost = rb_next(node);
>
> Think we need
>
> if (root->rb_leftmost)
>
> > + leftmost = true;
>
> DEADLINE crashes w/o that.
I think Peter's code is correct; after removing the only node in an
rbtree rb_leftmost should be NULL.
The issue appears to be in dequeue_pushable_dl_task unconditionally
dereferencing the pointer returned by rb_first_cached(), which may be
NULL. I'm not sure what the correct behavior is though, i.e. what
dl_rq->earliest_dl.next should be set to if the rbtree ends up empty.
Current code (before Peter's changes) preserves the existing
dl_rq->earliest_dl.next value in that case, which seems very weird to
me (and worthy of a comment if it's correct).
On 30/04/20 00:51, Michel Lespinasse wrote:
> On Thu, Apr 30, 2020 at 12:28 AM Juri Lelli <[email protected]> wrote:
> > > --- a/include/linux/rbtree.h
> > > +++ b/include/linux/rbtree.h
> > > @@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
> > > rb_insert_color(node, &root->rb_root);
> > > }
> > >
> > > -static inline void rb_erase_cached(struct rb_node *node,
> > > +static inline bool rb_erase_cached(struct rb_node *node,
> > > struct rb_root_cached *root)
> > > {
> > > - if (root->rb_leftmost == node)
> > > + bool leftmost = false;
> > > +
> > > + if (root->rb_leftmost == node) {
> > > root->rb_leftmost = rb_next(node);
> >
> > Think we need
> >
> > if (root->rb_leftmost)
> >
> > > + leftmost = true;
> >
> > DEADLINE crashes w/o that.
>
> I think Peter's code is correct; after removing the only node in an
> rbtree rb_leftmost should be NULL.
Indeed, I've only got the idea that Peter was thinking of using
rb_erase_cached return value as an indication that new rb_leftmost is
not NULL (and for example perform an update in DEADLINE earliest_dl).
I also had the impression that DEADLINE is actually the only consumer of
that return value and so we were able to define its semantic.
> The issue appears to be in dequeue_pushable_dl_task unconditionally
> dereferencing the pointer returned by rb_first_cached(), which may be
> NULL. I'm not sure what the correct behavior is though, i.e. what
> dl_rq->earliest_dl.next should be set to if the rbtree ends up empty.
> Current code (before Peter's changes) preserves the existing
> dl_rq->earliest_dl.next value in that case, which seems very weird to
> me (and worthy of a comment if it's correct).
But, yeah. Fixing things in DEADLINE code works for me as well. We could
reset it to 0 (initial value), but I now actually wonder if places where
that is consumed are actually OK. Different discussion, though. :-)
Thanks,
Juri
On Thu, Apr 30, 2020 at 12:51:02AM -0700, Michel Lespinasse wrote:
> On Thu, Apr 30, 2020 at 12:28 AM Juri Lelli <[email protected]> wrote:
> > > --- a/include/linux/rbtree.h
> > > +++ b/include/linux/rbtree.h
> > > @@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
> > > rb_insert_color(node, &root->rb_root);
> > > }
> > >
> > > -static inline void rb_erase_cached(struct rb_node *node,
> > > +static inline bool rb_erase_cached(struct rb_node *node,
> > > struct rb_root_cached *root)
> > > {
> > > - if (root->rb_leftmost == node)
> > > + bool leftmost = false;
> > > +
> > > + if (root->rb_leftmost == node) {
> > > root->rb_leftmost = rb_next(node);
> >
> > Think we need
> >
> > if (root->rb_leftmost)
> >
> > > + leftmost = true;
> >
> > DEADLINE crashes w/o that.
Clearly boot testing doesn't cover that..
> I think Peter's code is correct; after removing the only node in an
> rbtree rb_leftmost should be NULL.
>
> The issue appears to be in dequeue_pushable_dl_task unconditionally
> dereferencing the pointer returned by rb_first_cached(), which may be
> NULL.
Oh right.. silly me.
So yes, those rb_add_cached() / rb_erase_cached() return values are
(currently) only used by deadline. Deadline keeps a leftmost based value
cache and 'needs' this signal to update it; I can imagine there being
others, I didn't look at the many (~70) other users of
rb_erase_cached().
I briefly considered having rb_erase_cached() return the 'struct rb_node
*' of the new leftmost; that would naturally return NULL for the empty
tree. Maybe I should still do that -- see below.
Another thing I noticed is that I'm inconsistend with argument order;
rb_erase_cached(node, tree) vs rb_add_cached(tree, node). I'll go make
the new stuff use the 'wrong' order stuff too.
---
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -141,8 +141,8 @@ static inline void rb_insert_color_cache
rb_insert_color(node, &root->rb_root);
}
-static inline bool rb_erase_cached(struct rb_node *node,
- struct rb_root_cached *root)
+static inline struct rb_node *
+rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
{
bool leftmost = false;
@@ -152,7 +152,7 @@ static inline bool rb_erase_cached(struc
}
rb_erase(node, &root->rb_root);
- return leftmost;
+ return leftmost ? root->rb_leftmost : NULL;
}
static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -164,8 +164,9 @@ static inline void rb_replace_node_cache
rb_replace_node(victim, new, &root->rb_root);
}
-static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
- bool (*less)(struct rb_node *, const struct rb_node *))
+static inline struct rb_node *
+rb_add_cached(struct rb_root_cached *tree, struct rb_node *node, bool
+ (*less)(struct rb_node *, const struct rb_node *))
{
struct rb_node **link = &tree->rb_root.rb_node;
struct rb_node *parent = NULL;
@@ -184,7 +185,7 @@ static inline bool rb_add_cached(struct
rb_link_node(node, parent, link);
rb_insert_color_cached(node, tree, leftmost);
- return leftmost;
+ return leftmost ? node : NULL;
}
static inline void rb_add(struct rb_root *tree, struct rb_node *node,
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -454,10 +454,14 @@ static inline bool __pushable_less(struc
*/
static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
{
+ struct rb_node *leftmost;
+
BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
- if (rb_add_cached(&rq->dl.pushable_dl_tasks_root, &p->pushable_dl_tasks,
- __pushable_less))
+ leftmost = rb_add_cached(&rq->dl.pushable_dl_tasks_root,
+ &p->pushable_dl_tasks,
+ __pushable_less);
+ if (leftmost)
rq->dl.earliest_dl.next = p->dl.deadline;
}
@@ -465,12 +469,14 @@ static void dequeue_pushable_dl_task(str
{
struct dl_rq *dl_rq = &rq->dl;
struct rb_root_cached *root = &dl_rq->pushable_dl_tasks_root;
+ struct rb_node *leftmost;
if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
return;
- if (rb_erase_cached(&p->pushable_dl_tasks, root))
- dl_rq->earliest_dl.next = __node_2_pdl(rb_first_cached(root))->dl.deadline;
+ leftmost = rb_erase_cached(&p->pushable_dl_tasks, root);
+ if (leftmost)
+ dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline;
RB_CLEAR_NODE(&p->pushable_dl_tasks);
}
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 <[email protected]>
Thanks, I suppose I'll go brush this up a bit more then.
On Thu, Apr 30, 2020 at 10:46:17AM +0200, Peter Zijlstra wrote:
> On Wed, Apr 29, 2020 at 06:04:05PM -0700, Michel Lespinasse wrote:
> > - 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.
I just realized I'd already done all this at some point ;-) See
rbtree_latch.h. Clearly I failed to realize the full potential back when
I did that.