Line data    Source code

       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        1197 : static inline bool __timerqueue_less(struct rb_node *a, const struct rb_node *b)
      21             : {
      22        1197 :         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         657 : 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         657 :         WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
      39             : 
      40         657 :         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         642 : bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
      54             : {
      55         642 :         WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
      56             : 
      57         642 :         rb_erase_cached(&node->node, &head->rb_root);
      58         642 :         RB_CLEAR_NODE(&node->node);
      59             : 
      60         642 :         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           0 : struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
      74             : {
      75           0 :         struct rb_node *next;
      76             : 
      77           0 :         if (!node)
      78             :                 return NULL;
      79           0 :         next = rb_next(&node->node);
      80           0 :         if (!next)
      81           0 :                 return NULL;
      82           0 :         return container_of(next, struct timerqueue_node, node);
      83             : }
      84             : EXPORT_SYMBOL_GPL(timerqueue_iterate_next);