lkml.org 
[lkml]   [2021]   [Oct]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH 4.19 12/12] lib/timerqueue: Rely on rbtree semantics for next timer
Date
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
Reference: CVE-2021-20317
Signed-off-by: Nobuhiro Iwamatsu (CIP) <nobuhiro1.iwamatsu@toshiba.co.jp>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
---
include/linux/timerqueue.h | 13 ++++++-------
lib/timerqueue.c | 30 ++++++++++++------------------
2 files changed, 18 insertions(+), 25 deletions(-)

--- 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 *timerqueu
*
* @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(struc

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 */
--- 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_he
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_he
{
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);


\
 
 \ /
  Last update: 2021-10-08 13:33    [W:1.590 / U:0.232 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site