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  }