summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorDavidlohr Bueso <dave@stgolabs.net>2019-07-24 18:23:23 +0300
committerThomas Gleixner <tglx@linutronix.de>2019-07-24 18:38:01 +0300
commit511885d7061eda3eb1faf3f57dcc936ff75863f1 (patch)
treeaa17e0932d884a2088909c8523d8c3c17e34af06 /lib
parentad5e427e0f6b702e52c11d1f7b2b7be3bac7de82 (diff)
downloadlinux-511885d7061eda3eb1faf3f57dcc936ff75863f1.tar.xz
lib/timerqueue: Rely on rbtree semantics for next timer
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
Diffstat (limited to 'lib')
-rw-r--r--lib/timerqueue.c30
1 files changed, 12 insertions, 18 deletions
diff --git a/lib/timerqueue.c b/lib/timerqueue.c
index bc7e64df27df..c52710964593 100644
--- a/lib/timerqueue.c
+++ b/lib/timerqueue.c
@@ -26,9 +26,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));
@@ -36,19 +37,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);
@@ -65,15 +64,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);