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 #define __node_2_tq(_n) \ 18 rb_entry((_n), struct timerqueue_node, node) 19 20 static inline bool __timerqueue_less(struct rb_node *a, const struct rb_node *b) 21 { 22 return __node_2_tq(a)->expires < __node_2_tq(b)->expires; 23 } 24 25 /** 26 * timerqueue_add - Adds timer to timerqueue. 27 * 28 * @head: head of timerqueue 29 * @node: timer node to be added 30 * 31 * Adds the timer node to the timerqueue, sorted by the node's expires 32 * value. Returns true if the newly added timer is the first expiring timer in 33 * the queue. 34 */ 35 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) 36 { 37 /* Make sure we don't add nodes that are already added */ 38 WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); 39 40 return rb_add_cached(&node->node, &head->rb_root, __timerqueue_less); 41 } 42 EXPORT_SYMBOL_GPL(timerqueue_add); 43 44 /** 45 * timerqueue_del - Removes a timer from the timerqueue. 46 * 47 * @head: head of timerqueue 48 * @node: timer node to be removed 49 * 50 * Removes the timer node from the timerqueue. Returns true if the queue is 51 * not empty after the remove. 52 */ 53 bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) 54 { 55 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); 56 57 rb_erase_cached(&node->node, &head->rb_root); 58 RB_CLEAR_NODE(&node->node); 59 60 return !RB_EMPTY_ROOT(&head->rb_root.rb_root); 61 } 62 EXPORT_SYMBOL_GPL(timerqueue_del); 63 64 /** 65 * timerqueue_iterate_next - Returns the timer after the provided timer 66 * 67 * @node: Pointer to a timer. 68 * 69 * Provides the timer that is after the given node. This is used, when 70 * necessary, to iterate through the list of timers in a timer list 71 * without modifying the list. 72 */ 73 struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) 74 { 75 struct rb_node *next; 76 77 if (!node) 78 return NULL; 79 next = rb_next(&node->node); 80 if (!next) 81 return NULL; 82 return container_of(next, struct timerqueue_node, node); 83 } 84 EXPORT_SYMBOL_GPL(timerqueue_iterate_next); 85