1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Generic Timer-queue 4 * 5 * Manages a simple queue of timers, ordered by expiration time. 6 * Uses rbtrees for quick list adds and expiration. 7 * 8 * NOTE: All of the following functions need to be serialized 9 * to avoid races. No locking is done by this library code. 10 */ 11 12 #include <linux/bug.h> 13 #include <linux/timerqueue.h> 14 #include <linux/rbtree.h> 15 #include <linux/export.h> 16 17 /** 18 * timerqueue_add - Adds timer to timerqueue. 19 * 20 * @head: head of timerqueue 21 * @node: timer node to be added 22 * 23 * Adds the timer node to the timerqueue, sorted by the node's expires 24 * value. Returns true if the newly added timer is the first expiring timer in 25 * the queue. 26 */ 27 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) 28 { 29 struct rb_node **p = &head->head.rb_node; 30 struct rb_node *parent = NULL; 31 struct timerqueue_node *ptr; 32 33 /* Make sure we don't add nodes that are already added */ 34 WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); 35 36 while (*p) { 37 parent = *p; 38 ptr = rb_entry(parent, struct timerqueue_node, node); 39 if (node->expires < ptr->expires) 40 p = &(*p)->rb_left; 41 else 42 p = &(*p)->rb_right; 43 } 44 rb_link_node(&node->node, parent, p); 45 rb_insert_color(&node->node, &head->head); 46 47 if (!head->next || node->expires < head->next->expires) { 48 head->next = node; 49 return true; 50 } 51 return false; 52 } 53 EXPORT_SYMBOL_GPL(timerqueue_add); 54 55 /** 56 * timerqueue_del - Removes a timer from the timerqueue. 57 * 58 * @head: head of timerqueue 59 * @node: timer node to be removed 60 * 61 * Removes the timer node from the timerqueue. Returns true if the queue is 62 * not empty after the remove. 63 */ 64 bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) 65 { 66 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); 67 68 /* update next pointer */ 69 if (head->next == node) { 70 struct rb_node *rbn = rb_next(&node->node); 71 72 head->next = rb_entry_safe(rbn, struct timerqueue_node, node); 73 } 74 rb_erase(&node->node, &head->head); 75 RB_CLEAR_NODE(&node->node); 76 return head->next != NULL; 77 } 78 EXPORT_SYMBOL_GPL(timerqueue_del); 79 80 /** 81 * timerqueue_iterate_next - Returns the timer after the provided timer 82 * 83 * @node: Pointer to a timer. 84 * 85 * Provides the timer that is after the given node. This is used, when 86 * necessary, to iterate through the list of timers in a timer list 87 * without modifying the list. 88 */ 89 struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) 90 { 91 struct rb_node *next; 92 93 if (!node) 94 return NULL; 95 next = rb_next(&node->node); 96 if (!next) 97 return NULL; 98 return container_of(next, struct timerqueue_node, node); 99 } 100 EXPORT_SYMBOL_GPL(timerqueue_iterate_next); 101