* [RFC/PATCH for 4.14 and 4.19] lib/timerqueue: Rely on rbtree semantics for next timer
@ 2021-10-07 12:32 Nobuhiro Iwamatsu
2021-10-08 9:10 ` Greg KH
0 siblings, 1 reply; 2+ messages in thread
From: Nobuhiro Iwamatsu @ 2021-10-07 12:32 UTC (permalink / raw)
To: stable
Cc: gregkh, sashal, Davidlohr Bueso, Davidlohr Bueso,
Thomas Gleixner, Nobuhiro Iwamatsu
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>
---
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 78b8cc73f12fc9..aff122f1062a83 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 0d54bcbc8170c7..7a8ae3d5fd4057 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);
--
2.33.0
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [RFC/PATCH for 4.14 and 4.19] lib/timerqueue: Rely on rbtree semantics for next timer
2021-10-07 12:32 [RFC/PATCH for 4.14 and 4.19] lib/timerqueue: Rely on rbtree semantics for next timer Nobuhiro Iwamatsu
@ 2021-10-08 9:10 ` Greg KH
0 siblings, 0 replies; 2+ messages in thread
From: Greg KH @ 2021-10-08 9:10 UTC (permalink / raw)
To: Nobuhiro Iwamatsu
Cc: stable, sashal, Davidlohr Bueso, Davidlohr Bueso, Thomas Gleixner
On Thu, Oct 07, 2021 at 09:32:43PM +0900, Nobuhiro Iwamatsu wrote:
> 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>
> ---
Now queued up, thanks.
greg k-h
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-10-08 9:10 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-10-07 12:32 [RFC/PATCH for 4.14 and 4.19] lib/timerqueue: Rely on rbtree semantics for next timer Nobuhiro Iwamatsu
2021-10-08 9:10 ` Greg KH
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.