Generic RB-tree helpers
Subsystems (7)
Peter Zijlstra
maintainerv2 cover Generic RB-tree helpers
Hai all,
I found myself needing to write yet another rbtree and remembered I had these patches gathering dust. I've had them in a git tree pretty much ever since I posted them last and the robot is telling me they build/work/dance/sing fine.
I'm proposing to stick them in tip and get on with life. What say you?
Peter Zijlstra
maintainerPATCH v2 1/7 rbtree: Add generic add and find helpers
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_add(): find an entry, and add if not found
- rb_find_first(): find the first (leftmost) matching entry
- rb_next_match(): continue from rb_find_first()
- rb_for_each(): iterate a sub-tree using the previous two
Inlining and constant propagation should see the compiler inline the whole thing, including the various compare functions.
--- include/linux/rbtree.h | 190 ++++++++++++++++++++++++++++++++++++++++++ tools/include/linux/rbtree.h | 192 ++++++++++++++++++++++++++++++++++++++++++- tools/objtool/elf.c | 73 ++-------------- 3 files changed, 392 insertions(+), 63 deletions(-)
include/linux/rbtree.h +190 -0
@@ -158,4 +158,194 @@ static inline void rb_replace_node_cache rb_replace_node(victim, new, &root->rb_root); } +/* +* The below helper functions use 2 operators with 3 different +* calling conventions. The operators are related like: +* +* comp(a->key,b) < 0 := less(a,b) +* comp(a->key,b) > 0 := less(b,a) +* comp(a->key,b) == 0 := !less(a,b) && !less(b,a) +* +* If these operators define a partial order on the elements we make no +* guarantee on which of the elements matching the key is found. See +* rb_find(). +* +* The reason for this is to allow the find() interface without requiring an +* on-stack dummy object, which might not be feasible due to object size. +*/ + +/** +* rb_add_cached() - insert @node into the leftmost cached tree @tree +* @node: node to insert +* @tree: leftmost cached tree to insert @node into +* @less: operator defining the (partial) node order +*/ +static __always_inline void +rb_add_cached (struct rb_node *node,struct rb_root_cached *tree, +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); +} + +/** +* rb_add() - insert @node into @tree +* @node: node to insert +* @tree: tree to insert @node into +* @less: operator defining the (partial) node order +*/ +static __always_inline void +rb_add (struct rb_node *node,struct rb_root *tree, +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); +} + +/** +* rb_find_add() - 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 (struct rb_node *node,struct rb_root *tree, +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 ; +} + +/** +* rb_find() - find @key in tree @tree +* @key: key to match +* @tree: tree to search +* @cmp: operator defining the node order +* +* Returns the rb_node matching @key or NULL. +*/ +static __always_inline struct rb_node * +rb_find (const void *key,const struct rb_root *tree, +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 ; +} + +/** +* rb_find_first() - find the first @key in @tree +* @key: key to match +* @tree: tree to search +* @cmp: operator defining node order +* +* Returns the leftmost node matching @key, or NULL. +*/ +static __always_inline struct rb_node * +rb_find_first (const void *key,const struct rb_root *tree, +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; +} + +/** +* rb_next_match() - find the next @key in @tree +* @key: key to match +* @tree: tree to search +* @cmp: operator defining node order +* +* Returns the next node matching @key, or NULL. +*/ +static __always_inline struct rb_node * +rb_next_match (const void *key,struct rb_node *node, +int (*cmp)(const void *key,const struct rb_node *)) +{ + node =rb_next (node); +if (node &&cmp (key, node)) + node =NULL ; +return node; +} + +/** +* rb_for_each() - iterates a subtree matching @key +* @node: iterator +* @key: key to match +* @tree: tree to search +* @cmp: operator defining node order +*/ +#define rb_for_each (node, key, tree, cmp) \ + for ((node) = rb_find_first((key), (tree), (cmp)); \ + (node); (node) = rb_next_match((key), (node), (cmp))) +#endif /* _LINUX_RBTREE_H */
tools/include/linux/rbtree.h +191 -1
195 lines not on this page · raw message
tools/objtool/elf.c +11 -62
121 lines not on this page · raw message
Peter Zijlstra
maintainerPATCH v2 2/7 rbtree, sched/fair: Use rb_add_cached()
In reply to Peter ZijlstraReduce rbtree boiler plate by using the new helper function.
--- kernel/sched/fair.c | 46 ++++++++++++++-------------------------------- 1 file changed, 14 insertions(+), 32 deletions(-)
kernel/sched/fair.c +14 -32
@@ -533,12 +533,15 @@ static inline u64 min_vruntime(u64 min_vreturn min_vruntime; } -static inline int entity_before (struct sched_entity *a, +static inline bool entity_before (struct sched_entity *a,struct sched_entity *b) {return (s64)(a->vruntime - b->vruntime) <0 ; } +#define __node_2_se (node) \ + rb_entry((node), struct sched_entity, run_node) +static void update_min_vruntime (struct cfs_rq *cfs_rq) {struct sched_entity *curr = cfs_rq->curr;
@@ -554,8 +557,7 @@ static void update_min_vruntime(struct c }if (leftmost) {/* non-empty tree */ -struct sched_entity *se; - se = rb_entry(leftmost, struct sched_entity, run_node); +struct sched_entity *se =__node_2_se (leftmost);if (!curr) vruntime = se->vruntime;
@@ -571,37 +573,17 @@ static void update_min_vruntime(struct c#endif } +static inline bool __entity_less (struct rb_node *a,const struct rb_node *b) +{ +return entity_before (__node_2_se (a),__node_2_se (b)); +} +/* * Enqueue an entity into the rb-tree: */ static void __enqueue_entity (struct cfs_rq *cfs_rq,struct sched_entity *se) { -struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node; -struct rb_node *parent =NULL ; -struct sched_entity *entry; -bool leftmost = true; - -/* -* Find the right place in the rbtree: -*/ -while (*link) { - parent = *link; - entry = rb_entry(parent, struct sched_entity, run_node); -/* -* We dont care about collisions. Nodes with -* the same key stay together. -*/ -if (entity_before (se, entry)) { - link = &parent->rb_left; - }else { - link = &parent->rb_right; - leftmost = false; - } - } - -rb_link_node (&se->run_node, parent, link); -rb_insert_color_cached (&se->run_node, - &cfs_rq->tasks_timeline, leftmost); +rb_add_cached (&se->run_node, &cfs_rq->tasks_timeline, __entity_less); }static void __dequeue_entity (struct cfs_rq *cfs_rq,struct sched_entity *se)
@@ -616,7 +598,7 @@ struct sched_entity *__pick_first_entityif (!left)return NULL ; - return rb_entry(left, struct sched_entity, run_node); +return __node_2_se (left); }static struct sched_entity *__pick_next_entity (struct sched_entity *se)
@@ -626,7 +608,7 @@ static struct sched_entity *__pick_next_if (!next)return NULL ; - return rb_entry(next, struct sched_entity, run_node); +return __node_2_se (next); }#ifdef CONFIG_SCHED_DEBUG
@@ -637,7 +619,7 @@ struct sched_entity *__pick_last_entity(if (!last)return NULL ; - return rb_entry(last, struct sched_entity, run_node); +return __node_2_se (last); }/**************************************************************
Peter Zijlstra
maintainerPATCH v2 3/7 rbtree, sched/deadline: Use rb_add_cached()
In reply to Peter ZijlstraReduce rbtree boiler plate by using the new helpers.
Make rb_add_cached() / rb_erase_cached() return a pointer to the leftmost node to aid in updating additional state.
--- include/linux/rbtree.h | 18 ++++++++--- kernel/sched/deadline.c | 77 +++++++++++++++++------------------------------- 2 files changed, 42 insertions(+), 53 deletions(-)
include/linux/rbtree.h +14 -4
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cacherb_insert_color (node, &root->rb_root); } -static inline void 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) { +struct rb_node *leftmost =NULL ; +if (root->rb_leftmost == node) - root->rb_leftmost =rb_next (node); + leftmost = root->rb_leftmost =rb_next (node); +rb_erase (node, &root->rb_root); + +return leftmost; } static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -179,8 +185,10 @@ static inline void rb_replace_node_cache* @node: node to insert * @tree: leftmost cached tree to insert @node into * @less: operator defining the (partial) node order +* +* Returns @node when it is the new leftmost, or NULL. */ -static __always_inline void +static __always_inline struct rb_node *rb_add_cached (struct rb_node *node,struct rb_root_cached *tree,bool (*less)(struct rb_node *,const struct rb_node *)) {
@@ -200,6 +208,8 @@ rb_add_cached(struct rb_node *node, strurb_link_node (node, parent, link);rb_insert_color_cached (node, tree, leftmost); + +return leftmost ? node :NULL ; }/**
kernel/sched/deadline.c +28 -49
121 lines not on this page · raw message
Peter Zijlstra
maintainerPATCH v2 4/7 rbtree, perf: Use new rbtree helpers
In reply to Peter ZijlstraReduce rbtree boiler plate by using the new helpers.
One noteworthy change is unification of the various (partial) compare functions. We construct a subtree match by forcing the sub-order to always match, see __group_cmp().
Due to 'const' we had to touch cgroup_id().
--- include/linux/cgroup.h | 4 kernel/events/core.c | 201 ++++++++++++++++++++++--------------------------- 2 files changed, 95 insertions(+), 110 deletions(-)
include/linux/cgroup.h +2 -2
@@ -307,7 +307,7 @@ void css_task_iter_end(struct css_task_i* Inline functions. */ -static inline u64 cgroup_id (struct cgroup *cgrp) +static inline u64 cgroup_id (const struct cgroup *cgrp) {return cgrp->kn->id; }
@@ -701,7 +701,7 @@ void cgroup_path_from_kernfs_id(u64 id,struct cgroup_subsys_state ;struct cgroup ; -static inline u64 cgroup_id (struct cgroup *cgrp) {return 1 ; } +static inline u64 cgroup_id (const struct cgroup *cgrp) {return 1 ; }static inline void css_get (struct cgroup_subsys_state *css) {}static inline void css_put (struct cgroup_subsys_state *css) {} static inline int cgroup_attach_task_all(struct task_struct *from,
kernel/events/core.c +93 -108
242 lines not on this page · raw message
Re: [PATCH v2 4/7] rbtree, perf: Use new rbtree helpers
Quoted 10 lines · Peter Zijlstra
Reduce rbtree boiler plate by using the new helpers.
One noteworthy change is unification of the various (partial) compare functions. We construct a subtree match by forcing the sub-order to always match, see
__group_cmp().Due to 'const' we had to touch
cgroup_id().Cc Tejun Heo <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Thanks.
Signature · 1 line
tejun
Peter Zijlstra
maintainerPATCH v2 5/7 rbtree, uprobes: Use rbtree helpers
In reply to Peter ZijlstraReduce rbtree boilerplate by using the new helpers.
--- kernel/events/uprobes.c | 82 +++++++++++++++++++++++------------------------- 1 file changed, 40 insertions(+), 42 deletions(-)
kernel/events/uprobes.c +40 -42
@@ -619,41 +619,56 @@ static void put_uprobe(struct uprobe *up } } -static int match_uprobe (struct uprobe *l,struct uprobe *r) +static __always_inline +int uprobe_cmp(const struct inode *l_inode, const loff_t l_offset, +const struct uprobe *r) { -if (l->inode < r->inode) +if (l_inode < r->inode)return -1 ; -if (l->inode > r->inode) +if (l_inode > r->inode)return 1 ; -if (l->offset < r->offset) +if (l_offset < r->offset)return -1 ; -if (l->offset > r->offset) +if (l_offset > r->offset)return 1 ;return 0 ; } +#define __node_2_uprobe (node) \ + rb_entry((node), struct uprobe, rb_node) + +struct __uprobe_key { +struct inode *inode; +loff_t offset; +}; + +static inline int __uprobe_cmp_key (const void *key,const struct rb_node *b) +{ +const struct __uprobe_key *a = key; +return uprobe_cmp (a->inode, a->offset,__node_2_uprobe (b)); +} + +static inline int __uprobe_cmp (struct rb_node *a,const struct rb_node *b) +{ +struct uprobe *u =__node_2_uprobe (a); +return uprobe_cmp (u->inode, u->offset,__node_2_uprobe (b)); +} +static struct uprobe *__find_uprobe (struct inode *inode,loff_t offset) { -struct uprobe u = { .inode = inode, .offset = offset }; -struct rb_node *n = uprobes_tree.rb_node; -struct uprobe *uprobe; -int match; +struct __uprobe_key key = { + .inode = inode, + .offset = offset, + }; +struct rb_node *node =rb_find (&key, &uprobes_tree, __uprobe_cmp_key); + +if (node) +return __node_2_uprobe (node); -while (n) { - uprobe = rb_entry(n, struct uprobe, rb_node); - match =match_uprobe (&u, uprobe); -if (!match) -return get_uprobe (uprobe); - -if (match <0 ) - n = n->rb_left; -else - n = n->rb_right; - }return NULL ; }
@@ -674,32 +689,15 @@ static struct uprobe *find_uprobe(structstatic struct uprobe *__insert_uprobe (struct uprobe *uprobe) { -struct rb_node **p = &uprobes_tree.rb_node; -struct rb_node *parent =NULL ; -struct uprobe *u; -int match; - -while (*p) { - parent = *p; - u = rb_entry(parent, struct uprobe, rb_node); - match =match_uprobe (uprobe, u); -if (!match) -return get_uprobe (u); - -if (match <0 ) - p = &parent->rb_left; -else - p = &parent->rb_right; +struct rb_node *node; - } + node =rb_find_add (&uprobe->rb_node, &uprobes_tree, __uprobe_cmp); +if (node) +return get_uprobe (__node_2_uprobe (node)); - u =NULL ; -rb_link_node (&uprobe->rb_node, parent, p); -rb_insert_color (&uprobe->rb_node, &uprobes_tree);/* get access + creation ref */ refcount_set (&uprobe->ref,2 ); - -return u; +return NULL ; }/*
Re: [PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers
Quoted 1 line · Peter Zijlstra
Reduce rbtree boilerplate by using the new helpers.
This reminds me of:
https://lore.kernel.org/lkml/[email protected]/
Would a walk optimization (list+rbtree) serve here? Not sure how big the uprobes_trees gets.
Thanks,
Davidlohr
Peter Zijlstra
maintainerRe: [PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers
Quoted 10 lines · Davidlohr Bueso
Quoted 1 line · Peter Zijlstra
Reduce rbtree boilerplate by using the new helpers.
This reminds me of:
https://lore.kernel.org/lkml/[email protected]/
Would a walk optimization (list+rbtree) serve here? Not sure how big the
uprobes_treesgets.
Oh, that's patch set is horrible.. You can do a linked list with the unused node pointers directly.
https://en.wikipedia.org/wiki/Threaded_binary_tree
So instead of using NULL for the empty rb_{left,right} pointers, use pointers with the LSB set to differentiate them from regular leaf pointers.
Other than that, threaded rb-trees would be awesome. I've meant to implement them a number of times but never had the time to do the tree-wide clean up of the rb_tree API to enable them.
Peter Zijlstra
maintainerPATCH v2 6/7 rbtree, rtmutex: Use rb_add_cached()
In reply to Peter ZijlstraReduce rbtree boiler plate by using the new helpers.
--- kernel/locking/rtmutex.c | 54 +++++++++++++++-------------------------------- 1 file changed, 18 insertions(+), 36 deletions(-)
kernel/locking/rtmutex.c +18 -36
@@ -267,27 +267,18 @@ rt_mutex_waiter_equal(struct rt_mutex_wareturn 1 ; } +#define __node_2_waiter (node) \ + rb_entry((node), struct rt_mutex_waiter, tree_entry) + +static inline bool __waiter_less (struct rb_node *a,const struct rb_node *b) +{ +return rt_mutex_waiter_less (__node_2_waiter (a),__node_2_waiter (b)); +} +static void rt_mutex_enqueue (struct rt_mutex *lock,struct rt_mutex_waiter *waiter) { -struct rb_node **link = &lock->waiters.rb_root.rb_node; -struct rb_node *parent =NULL ; -struct rt_mutex_waiter *entry; -bool leftmost = true; - -while (*link) { - parent = *link; - entry = rb_entry(parent, struct rt_mutex_waiter, tree_entry); -if (rt_mutex_waiter_less (waiter, entry)) { - link = &parent->rb_left; - }else { - link = &parent->rb_right; - leftmost = false; - } - } - -rb_link_node (&waiter->tree_entry, parent, link); -rb_insert_color_cached (&waiter->tree_entry, &lock->waiters, leftmost); +rb_add_cached (&waiter->tree_entry, &lock->waiters, __waiter_less); } static void
@@ -300,27 +291,18 @@ rt_mutex_dequeue(struct rt_mutex *lock,RB_CLEAR_NODE (&waiter->tree_entry); } +#define __node_2_pi_waiter (node) \ + rb_entry((node), struct rt_mutex_waiter, pi_tree_entry) + +static inline bool __pi_waiter_less (struct rb_node *a,const struct rb_node *b) +{ +return rt_mutex_waiter_less (__node_2_pi_waiter (a),__node_2_pi_waiter (b)); +} +static void rt_mutex_enqueue_pi (struct task_struct *task,struct rt_mutex_waiter *waiter) { -struct rb_node **link = &task->pi_waiters.rb_root.rb_node; -struct rb_node *parent =NULL ; -struct rt_mutex_waiter *entry; -bool leftmost = true; - -while (*link) { - parent = *link; - entry = rb_entry(parent, struct rt_mutex_waiter, pi_tree_entry); -if (rt_mutex_waiter_less (waiter, entry)) { - link = &parent->rb_left; - }else { - link = &parent->rb_right; - leftmost = false; - } - } - -rb_link_node (&waiter->pi_tree_entry, parent, link); -rb_insert_color_cached (&waiter->pi_tree_entry, &task->pi_waiters, leftmost); +rb_add_cached (&waiter->pi_tree_entry, &task->pi_waiters, __pi_waiter_less); } static void
Quoted 8 lines · Peter Zijlstra
Hai all,
I found myself needing to write yet another rbtree and remembered I had these patches gathering dust. I've had them in a git tree pretty much ever since I posted them last and the robot is telling me they build/work/dance/sing fine.
I'm proposing to stick them in tip and get on with life. What say you?
I like consolidating this code with helpers, reduces LoC and improves readability imo. Feel free to add my:
Peter Zijlstra
maintainerPATCH v2 7/7 rbtree, timerqueue: Use rb_add_cached()
In reply to Peter ZijlstraReduce rbtree boiler plate by using the new helpers.
--- lib/timerqueue.c | 28 +++++++++------------------- 1 file changed, 9 insertions(+), 19 deletions(-)
lib/timerqueue.c +9 -19
@@ -14,6 +14,14 @@#include <linux/rbtree.h> #include <linux/export.h> +#define __node_2_tq (_n) \ + rb_entry((_n), struct timerqueue_node, node) + +static inline bool __timerqueue_less (struct rb_node *a,const struct rb_node *b) +{ +return __node_2_tq (a)->expires <__node_2_tq (b)->expires; +} +/** * timerqueue_add - Adds timer to timerqueue. *
@@ -26,28 +34,10 @@*/ bool timerqueue_add (struct timerqueue_head *head,struct timerqueue_node *node) { -struct rb_node **p = &head->rb_root.rb_root.rb_node; -struct rb_node *parent =NULL ; -struct timerqueue_node *ptr; -bool leftmost = true; -/* Make sure we don't add nodes that are already added */ WARN_ON_ONCE (!RB_EMPTY_NODE (&node->node)); -while (*p) { - parent = *p; - ptr = rb_entry(parent, struct timerqueue_node, node); -if (node->expires < ptr->expires) { - p = &(*p)->rb_left; - }else { - p = &(*p)->rb_right; - leftmost = false; - } - } -rb_link_node (&node->node, parent, p); -rb_insert_color_cached (&node->node, &head->rb_root, leftmost); - -return leftmost; +return rb_add_cached (&node->node, &head->rb_root, __timerqueue_less); }EXPORT_SYMBOL_GPL (timerqueue_add);