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