This is a note to let you know that I've just added the patch titled lib/timerqueue: Rely on rbtree semantics for next timer to the 4.9-stable tree which can be found at: http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary The filename of the patch is: lib-timerqueue-rely-on-rbtree-semantics-for-next-timer.patch and it can be found in the queue-4.9 subdirectory. If you, or anyone else, feels it should not be added to the stable tree, please let <stable@xxxxxxxxxxxxxxx> know about it. >From foo@baz Mon Jan 24 07:28:36 PM CET 2022 From: Ben Hutchings <ben@xxxxxxxxxxxxxxx> Date: Mon, 24 Jan 2022 17:33:46 +0100 Subject: lib/timerqueue: Rely on rbtree semantics for next timer To: stable@xxxxxxxxxxxxxxx Cc: Davidlohr Bueso <dave@xxxxxxxxxxxx>, Thomas Gleixner <tglx@xxxxxxxxxxxxx> Message-ID: <Ye7U6m6TkFmoM5iZ@xxxxxxxxxxxxxxx> Content-Disposition: inline From: Davidlohr Bueso <dave@xxxxxxxxxxxx> 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@xxxxxxx> Signed-off-by: Thomas Gleixner <tglx@xxxxxxxxxxxxx> 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@xxxxxxxxxxxxxxx> Signed-off-by: Greg Kroah-Hartman <gregkh@xxxxxxxxxxxxxxxxxxx> --- include/linux/timerqueue.h | 13 ++++++------- lib/timerqueue.c | 31 ++++++++++++------------------- 2 files changed, 18 insertions(+), 26 deletions(-) --- 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 *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) @@ -44,7 +44,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 @@ -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_he 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_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 = 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); Patches currently in stable-queue which might be from ben@xxxxxxxxxxxxxxx are queue-4.9/lib-timerqueue-rely-on-rbtree-semantics-for-next-timer.patch queue-4.9/gup-document-and-work-around-cow-can-break-either-way-issue.patch queue-4.9/fuse-fix-live-lock-in-fuse_iget.patch queue-4.9/kvm-do-not-assume-pte-is-writable-after-follow_pfn.patch queue-4.9/drm-ttm-nouveau-don-t-call-tt-destroy-callback-on-alloc-failure.patch queue-4.9/gianfar-simplify-fcs-handling-and-fix-memory-leak.patch queue-4.9/mm-add-follow_pte_pmd.patch queue-4.9/revert-gup-document-and-work-around-cow-can-break-either-way-issue.patch queue-4.9/gianfar-fix-jumbo-packets-napi-rx-overrun-crash.patch queue-4.9/cipso-calipso-resolve-a-number-of-problems-with-the-doi-refcounts.patch queue-4.9/rbtree-cache-leftmost-node-internally.patch queue-4.9/kvm-use-kvm_pfn_t-for-local-pfn-variable-in-hva_to_pfn_remapped.patch queue-4.9/kvm-do-not-allow-mapping-valid-but-non-reference-counted-pages.patch queue-4.9/fuse-fix-bad-inode.patch