From: Davidlohr Bueso dave@stgolabs.net
commit 511885d7061eda3eb1faf3f57dcc936ff75863f1 upstream.
Simplify the timerqueue code by using cached rbtrees and rely on the tree leftmost node semantics to get the timer with earliest expiration time. This is a drop in conversion, and therefore semantics remain untouched.
The runtime overhead of cached rbtrees is be pretty much the same as the current head->next method, noting that when removing the leftmost node, a common operation for the timerqueue, the rb_next(leftmost) is O(1) as well, so the next timer will either be the right node or its parent. Therefore no extra pointer chasing. Finally, the size of the struct timerqueue_head remains the same.
Passes several hours of rcutorture.
Signed-off-by: Davidlohr Bueso dbueso@suse.de Signed-off-by: Thomas Gleixner tglx@linutronix.de Link: https://lkml.kernel.org/r/20190724152323.bojciei3muvfxalm@linux-r8p5 [bwh: While this was supposed to be just refactoring, it also fixed a security flaw (CVE-2021-20317). Backported to 4.9: - Deleted code in timerqueue_del() is different before commit d852d39432f5 "timerqueue: Use rb_entry_safe() instead of open-coding it" - Adjust context] Signed-off-by: Ben Hutchings ben@decadent.org.uk --- include/linux/timerqueue.h | 13 ++++++------- lib/timerqueue.c | 31 ++++++++++++------------------- 2 files changed, 18 insertions(+), 26 deletions(-)
diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h index 7eec17ad7fa1..42868a9b4365 100644 --- a/include/linux/timerqueue.h +++ b/include/linux/timerqueue.h @@ -11,8 +11,7 @@ struct timerqueue_node { };
struct timerqueue_head { - struct rb_root head; - struct timerqueue_node *next; + struct rb_root_cached rb_root; };
@@ -28,13 +27,14 @@ extern struct timerqueue_node *timerqueue_iterate_next( * * @head: head of timerqueue * - * Returns a pointer to the timer node that has the - * earliest expiration time. + * Returns a pointer to the timer node that has the earliest expiration time. */ static inline struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) { - return head->next; + struct rb_node *leftmost = rb_first_cached(&head->rb_root); + + return rb_entry(leftmost, struct timerqueue_node, node); }
static inline void timerqueue_init(struct timerqueue_node *node) @@ -44,7 +44,6 @@ static inline void timerqueue_init(struct timerqueue_node *node)
static inline void timerqueue_init_head(struct timerqueue_head *head) { - head->head = RB_ROOT; - head->next = NULL; + head->rb_root = RB_ROOT_CACHED; } #endif /* _LINUX_TIMERQUEUE_H */ diff --git a/lib/timerqueue.c b/lib/timerqueue.c index 782ae8ca2c06..4f99b5c3ac0e 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -38,9 +38,10 @@ */ bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) { - struct rb_node **p = &head->head.rb_node; + struct rb_node **p = &head->rb_root.rb_root.rb_node; struct rb_node *parent = NULL; - struct timerqueue_node *ptr; + 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)); @@ -48,19 +49,17 @@ bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) while (*p) { parent = *p; ptr = rb_entry(parent, struct timerqueue_node, node); - if (node->expires.tv64 < ptr->expires.tv64) + if (node->expires.tv64 < ptr->expires.tv64) { p = &(*p)->rb_left; - else + } else { p = &(*p)->rb_right; + leftmost = false; + } } rb_link_node(&node->node, parent, p); - rb_insert_color(&node->node, &head->head); + rb_insert_color_cached(&node->node, &head->rb_root, leftmost);
- if (!head->next || node->expires.tv64 < head->next->expires.tv64) { - head->next = node; - return true; - } - return false; + return leftmost; } EXPORT_SYMBOL_GPL(timerqueue_add);
@@ -76,16 +75,10 @@ bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) { WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
- /* update next pointer */ - if (head->next == node) { - struct rb_node *rbn = rb_next(&node->node); - - head->next = rbn ? - rb_entry(rbn, struct timerqueue_node, node) : NULL; - } - rb_erase(&node->node, &head->head); + rb_erase_cached(&node->node, &head->rb_root); RB_CLEAR_NODE(&node->node); - return head->next != NULL; + + return !RB_EMPTY_ROOT(&head->rb_root.rb_root); } EXPORT_SYMBOL_GPL(timerqueue_del);