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->node, tree: &head->rb_root, less: __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->node, root: &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 | |