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
timer_queue_empty(struct timer_queue * tq)21 static inline int timer_queue_empty(struct timer_queue *tq)
22 {
23 return tq->num_entries == 0;
24 }
25
timer_queue_full(struct timer_queue * tq)26 static inline int timer_queue_full(struct timer_queue *tq)
27 {
28 return tq->num_entries == tq->max_entries;
29 }
30
timer_queue_head(struct timer_queue * tq)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
timer_queue_insert(struct timer_queue * tq,struct timeout_callback * tocb)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. */
timer_queue_min_child_index(struct timer_queue * tq,int index)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
timer_queue_remove_head(struct timer_queue * tq)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 *
timer_queue_expired(struct timer_queue * tq,struct mono_time * current_time)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
timer_sched_callback(struct timeout_callback * tocb,uint64_t us)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(¤t_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(¤t_time, &tocb->expiration))
164 return -1;
165
166 return timer_queue_insert(&global_timer_queue, tocb);
167 }
168
timers_run(void)169 int timers_run(void)
170 {
171 struct timeout_callback *tocb;
172 struct mono_time current_time;
173
174 timer_monotonic_get(¤t_time);
175 tocb = timer_queue_expired(&global_timer_queue, ¤t_time);
176
177 if (tocb != NULL)
178 tocb->callback(tocb);
179
180 return !timer_queue_empty(&global_timer_queue);
181 }
182