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