From: Davidlohr Bueso dave@stgolabs.net
mainline inclusion from mainline-v5.4-rc1 commit 511885d7061eda3eb1faf3f57dcc936ff75863f1 category: bugfix bugzilla: NA CVE: CVE-2021-20317
---------------------------
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 Signed-off-by: Xiongfeng Wang wangxiongfeng2@huawei.com Reviewed-by: Xie XiuQi xiexiuqi@huawei.com --- include/linux/timerqueue.h | 13 ++++++------- lib/timerqueue.c | 30 ++++++++++++------------------ 2 files changed, 18 insertions(+), 25 deletions(-)
diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h index 78b8cc73f12f..aff122f1062a 100644 --- a/include/linux/timerqueue.h +++ b/include/linux/timerqueue.h @@ -12,8 +12,7 @@ struct timerqueue_node { };
struct timerqueue_head { - struct rb_root head; - struct timerqueue_node *next; + struct rb_root_cached rb_root; };
@@ -29,13 +28,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) @@ -45,7 +45,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 0d54bcbc8170..7a8ae3d5fd40 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -39,9 +39,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)); @@ -49,19 +50,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 < ptr->expires) + if (node->expires < ptr->expires) { 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 < head->next->expires) { - head->next = node; - return true; - } - return false; + return leftmost; } EXPORT_SYMBOL_GPL(timerqueue_add);
@@ -78,15 +77,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 = rb_entry_safe(rbn, struct timerqueue_node, node); - } - 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);