85 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/*3 * Generic Timer-queue4 *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 serialized9 * 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 20static 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 timerqueue29 * @node: timer node to be added30 *31 * Adds the timer node to the timerqueue, sorted by the node's expires32 * value. Returns true if the newly added timer is the first expiring timer in33 * the queue.34 */35bool 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}42EXPORT_SYMBOL_GPL(timerqueue_add);43 44/**45 * timerqueue_del - Removes a timer from the timerqueue.46 *47 * @head: head of timerqueue48 * @node: timer node to be removed49 *50 * Removes the timer node from the timerqueue. Returns true if the queue is51 * not empty after the remove.52 */53bool 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}62EXPORT_SYMBOL_GPL(timerqueue_del);63 64/**65 * timerqueue_iterate_next - Returns the timer after the provided timer66 *67 * @node: Pointer to a timer.68 *69 * Provides the timer that is after the given node. This is used, when70 * necessary, to iterate through the list of timers in a timer list71 * without modifying the list.72 */73struct 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}84EXPORT_SYMBOL_GPL(timerqueue_iterate_next);85