src/lib/timer_queue.c

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2
   3 #include <timer.h>
   4
   5 #define MAX_TIMER_QUEUE_ENTRIES 64
   6
   7 /* The timer queue is implemented using a min heap. Therefore the first
   8  * element is the one with smallest time to expiration. */
   9 struct timer_queue {
  10         int num_entries;
  11         int max_entries;
  12         struct timeout_callback *queue[MAX_TIMER_QUEUE_ENTRIES];
  13 };
  14
  15 static struct timer_queue global_timer_queue = {
  16         .num_entries = 0,
  17         .max_entries = MAX_TIMER_QUEUE_ENTRIES,
  18         .queue = { 0 },
  19 };
  20
  21 static inline int timer_queue_empty(struct timer_queue *tq)
  22 {
  23         return tq->num_entries == 0;
  24 }
  25
  26 static inline int timer_queue_full(struct timer_queue *tq)
  27 {
  28         return tq->num_entries == tq->max_entries;
  29 }
  30
  31 static inline struct timeout_callback *timer_queue_head(struct timer_queue *tq)
  32 {
  33         if (timer_queue_empty(tq))
  34                 return NULL;
  35         return tq->queue[0];
  36 }
  37
  38 static int timer_queue_insert(struct timer_queue *tq,
  39                               struct timeout_callback *tocb)
  40 {
  41         int index;
  42
  43         /* No more slots. */
  44         if (timer_queue_full(tq))
  45                 return -1;
  46
  47         index = tq->num_entries;
  48         tq->num_entries++;
  49         tq->queue[index] = tocb;
  50
  51         while (index != 0) {
  52                 struct timeout_callback *parent;
  53                 int parent_index;
  54
  55                 parent_index = (index - 1) / 2;
  56                 parent = tq->queue[parent_index];
  57
  58                 /* All other ancestors are less than or equal to the current. */
  59                 if (mono_time_cmp(&parent->expiration, &tocb->expiration) <= 0)
  60                         break;
  61
  62                 /* The parent is greater than current. Swap them. */
  63                 tq->queue[parent_index] = tocb;
  64                 tq->queue[index] = parent;
  65
  66                 index = parent_index;
  67         }
  68
  69         return 0;
  70 }
  71
  72 /* Get the index containing the entry with smallest value. */
  73 static int timer_queue_min_child_index(struct timer_queue *tq, int index)
  74 {
  75         int left_child_index;
  76         int right_child_index;
  77
  78         left_child_index = 2 * index + 1;
  79
  80         if (left_child_index >= tq->num_entries)
  81                 return -1;
  82
  83         right_child_index = left_child_index + 1;
  84
  85         if (right_child_index >= tq->num_entries)
  86                 return left_child_index;
  87
  88         if (mono_time_cmp(&tq->queue[left_child_index]->expiration,
  89                         &tq->queue[right_child_index]->expiration) < 0) {
  90                 return left_child_index;
  91         }
  92         return right_child_index;
  93 }
  94
  95 static void timer_queue_remove_head(struct timer_queue *tq)
  96 {
  97         int index;
  98         struct timeout_callback *tocb;
  99
 100         /* In order to remove the head the deepest child is replaced in the
 101          * head slot and bubbled down the tree. */
 102         tq->num_entries--;
 103         tocb = tq->queue[tq->num_entries];
 104         tq->queue[0] = tocb;
 105
 106         index = 0;
 107         while (1) {
 108                 int min_child_index;
 109                 struct timeout_callback *child;
 110
 111                 min_child_index = timer_queue_min_child_index(tq, index);
 112
 113                 /* No more entries to compare against. */
 114                 if (min_child_index < 0)
 115                         break;
 116
 117                 child = tq->queue[min_child_index];
 118
 119                 /* Current index is the correct place since it is smaller or
 120                  * equal to the smallest child. */
 121                 if (mono_time_cmp(&tocb->expiration, &child->expiration) <= 0)
 122                         break;
 123
 124                 /* Need to swap with smallest child. */
 125                 tq->queue[min_child_index] = tocb;
 126                 tq->queue[index] = child;
 127
 128                 index = min_child_index;
 129         }
 130 }
 131
 132 static struct timeout_callback *
 133 timer_queue_expired(struct timer_queue *tq, struct mono_time *current_time)
 134 {
 135         struct timeout_callback *tocb;
 136
 137         tocb = timer_queue_head(tq);
 138
 139         if (tocb == NULL)
 140                 return NULL;
 141
 142         /* The timeout callback hasn't expired yet. */
 143         if (mono_time_before(current_time, &tocb->expiration))
 144                 return NULL;
 145
 146         timer_queue_remove_head(tq);
 147
 148         return tocb;
 149 }
 150
 151 int timer_sched_callback(struct timeout_callback *tocb, uint64_t us)
 152 {
 153         struct mono_time current_time;
 154
 155         if ((long)us < 0)
 156                 return -1;
 157
 158         timer_monotonic_get(&current_time);
 159         tocb->expiration = current_time;
 160         mono_time_add_usecs(&tocb->expiration, us);
 161
 162         /* The expiration overflowed. */
 163         if (us != 0 && !mono_time_before(&current_time, &tocb->expiration))
 164                 return -1;
 165
 166         return timer_queue_insert(&global_timer_queue, tocb);
 167 }
 168
 169 int timers_run(void)
 170 {
 171         struct timeout_callback *tocb;
 172         struct mono_time current_time;
 173
 174         timer_monotonic_get(&current_time);
 175         tocb = timer_queue_expired(&global_timer_queue, &current_time);
 176
 177         if (tocb != NULL)
 178                 tocb->callback(tocb);
 179
 180         return !timer_queue_empty(&global_timer_queue);
 181 }