1#include <cmdline.h>
2#include <irq/irq.h>
3#include <math/clamp.h>
4#include <math/min_max.h>
5#include <mem/alloc.h>
6#include <smp/percpu.h>
7#include <time/names.h>
8#include <time/timer.h>
9
10#include "internal.h"
11
12static CMDLINE_DECLARE(timer, .flags = CMDLINE_ENTRY_SYMBOLIC,
13 .desc = "Timer subsystem cmdline entries");
14
15CMDLINE_CHILDREN_DECLARE(
16 timer,
17 CMDLINE_INNER_STRING(clock_evdev, clock_global.timer_clock_evdev,
18 .desc = "Timer subsystem clock event device",
19 .arg = "<device>", .default_val = CLOCK_NAME_LAPIC,
20 .choices = CMDLINE_CHOICES(CLOCK_NAME_LAPIC,
21 CLOCK_NAME_HPET,
22 CLOCK_NAME_TSC)));
23
24static void timer_dpc(void *ctx);
25void timer_base_reprogram_hardware(cpu_id_t cpu);
26static void timer_percpu_ctor(struct timer_percpu *p, cpu_id_t cpu) {
27 for (int i = 0; i < TIMER_BASE_MAX; i++) {
28 struct timer_base *pcpu = &p->bases[i];
29 pcpu->percpu = p;
30 pcpu->cpu = cpu;
31 pcpu->type = i;
32 pcpu->next_expiration_us = TIME_US_MAX;
33 spinlock_init(&pcpu->lock);
34 }
35
36 spinlock_init(&p->lock);
37 INIT_HLIST_HEAD(&p->dpc_timers);
38 dpc_init(d: &p->timer_dpc, fn: timer_dpc, ctx: p);
39}
40
41PERCPU_DECLARE(timer_percpu, struct timer_percpu, timer_percpu_ctor);
42
43static uint32_t wheel_index_for_level(time_us_t expiration, uint32_t level,
44 time_us_t *bucket_expiration) {
45 expiration = (expiration >> TIMER_LEVEL_SHIFT(level)) + 1;
46 *bucket_expiration = expiration << TIMER_LEVEL_SHIFT(level);
47 return TIMER_LEVEL_OFFSET(level) + (expiration & TIMER_LEVEL_MASK);
48}
49
50static uint32_t wheel_index_for(time_us_t expiration, time_us_t now,
51 time_us_t *bucket_expiration) {
52 time_us_t delta = expiration - now;
53
54 /* Passed */
55 if (expiration < now) {
56 *bucket_expiration = now;
57 return now & TIMER_LEVEL_MASK;
58 }
59
60 if (delta < TIMER_LEVEL_START(1)) {
61 return wheel_index_for_level(expiration, level: 0, bucket_expiration);
62 } else if (delta < TIMER_LEVEL_START(2)) {
63 return wheel_index_for_level(expiration, level: 1, bucket_expiration);
64 } else if (delta < TIMER_LEVEL_START(3)) {
65 return wheel_index_for_level(expiration, level: 2, bucket_expiration);
66 } else if (delta < TIMER_LEVEL_START(4)) {
67 return wheel_index_for_level(expiration, level: 3, bucket_expiration);
68 } else if (delta < TIMER_LEVEL_START(5)) {
69 return wheel_index_for_level(expiration, level: 4, bucket_expiration);
70 } else if (delta < TIMER_LEVEL_START(6)) {
71 return wheel_index_for_level(expiration, level: 5, bucket_expiration);
72 } else if (delta < TIMER_LEVEL_START(7)) {
73 return wheel_index_for_level(expiration, level: 6, bucket_expiration);
74 } else if (delta < TIMER_LEVEL_START(8)) {
75 return wheel_index_for_level(expiration, level: 7, bucket_expiration);
76 } else if (delta < TIMER_LEVEL_START(9)) {
77 return wheel_index_for_level(expiration, level: 8, bucket_expiration);
78 } else if (delta < TIMER_LEVEL_START(10)) {
79 return wheel_index_for_level(expiration, level: 9, bucket_expiration);
80 } else {
81 if (delta >= TIMER_WHEEL_TIMEOUT_CUTOFF)
82 expiration = now + TIMER_WHEEL_TIMEOUT_MAX;
83
84 return wheel_index_for_level(expiration, TIMER_LEVELS - 1,
85 bucket_expiration);
86 }
87}
88
89static void timer_enqueue_internal(struct timer_base *base, struct timer *timer,
90 uint32_t idx, time_us_t bucket_expiration) {
91 hlist_add_head(n: &timer->hlist_node, h: base->buckets + idx);
92 bitmap_set(map: base->pending_map, bit: idx);
93 timer_bucket_set(timer, bucket: idx);
94
95 if (!base->pending || bucket_expiration < base->next_expiration_us) {
96 base->next_expiration_us = bucket_expiration;
97 base->pending = true;
98 base->next_expiration_recalc = false;
99
100 timer_base_reprogram_hardware(cpu: base->cpu);
101 }
102}
103
104static void timer_add_internal(struct timer_base *base, struct timer *timer) {
105 time_us_t now = time_get_us();
106 if (!base->pending || base->next_expiration_us > now)
107 base->clock = now;
108
109 time_us_t bucket_expiration;
110 uint32_t idx =
111 wheel_index_for(expiration: timer->expiration_us, now: base->clock, bucket_expiration: &bucket_expiration);
112 timer_enqueue_internal(base, timer, idx, bucket_expiration);
113}
114
115static inline struct timer_base *timer_base_for_cpu(enum timer_flags flags,
116 cpu_id_t cpu) {
117 enum timer_base_type type =
118 flags & TIMER_FLAG_PINNED ? TIMER_BASE_LOCAL : TIMER_BASE_GLOBAL;
119
120 if (flags & TIMER_FLAG_DEFERRABLE)
121 type = TIMER_BASE_DEFERRED;
122
123 return &(PERCPU_PTR_FOR_CPU(timer_percpu, cpu)->bases[type]);
124}
125
126static inline struct timer_base *timer_base_for_flags(enum timer_flags flags) {
127 return timer_base_for_cpu(flags, cpu: flags & TIMER_FLAG_CPU_MASK);
128}
129
130static inline void timer_list_del(struct timer *timer) {
131 struct hlist_node *node = &timer->hlist_node;
132 hlist_del(n: node);
133}
134
135static inline void timer_fn_call(struct timer *timer) {
136 timer->func(timer);
137}
138
139static inline void timer_sync_wait_spin() {
140 for (int i = 0; i < TIMER_SYNC_SPIN_TIMES; i++)
141 cpu_relax();
142}
143
144static void timer_dpc(void *ctx) {
145 struct timer_percpu *pcpu = ctx;
146
147 while (true) {
148 enum irql irql = spin_lock_irq_disable(&pcpu->lock);
149 if (hlist_empty(h: &pcpu->dpc_timers)) {
150 spin_unlock(&pcpu->lock, irql);
151 break;
152 }
153
154 struct timer *timer =
155 hlist_entry(pcpu->dpc_timers.first, struct timer, hlist_node);
156 timer_list_del(timer);
157 spin_unlock(&pcpu->lock, irql);
158
159 struct timer_base *base = timer_base_for_flags(flags: timer->flags);
160
161 enum irql birql = spin_lock_irq_disable(&base->lock);
162 base->running = timer;
163 spin_unlock(&base->lock, birql);
164
165 kassert(!(timer->flags & TIMER_FLAG_IRQ));
166 timer_fn_call(timer);
167
168 birql = spin_lock_irq_disable(&base->lock);
169 base->running = NULL;
170 spin_unlock(&base->lock, birql);
171 }
172}
173
174/* Since we have two types of timers, DPC and IRQ ones, we have to construct
175 * the DPC list in here, and make sure we don't invert anything */
176static void timer_expire_bucket(struct timer_base *base,
177 struct hlist_head *head, enum irql *lirql) {
178 while (!hlist_empty(h: head)) {
179 struct timer *timer =
180 hlist_entry(head->first, struct timer, hlist_node);
181 timer_list_del(timer);
182
183 kassert(timer->func);
184
185 if (timer->flags & TIMER_FLAG_IRQ) {
186 base->running = timer;
187 spin_unlock(&base->lock, *lirql);
188 timer_fn_call(timer);
189 *lirql = spin_lock_irq_disable(&base->lock);
190 base->running = NULL;
191 } else {
192 enum irql pirql = spin_lock_irq_disable(&base->percpu->lock);
193
194 hlist_add_head(n: &timer->hlist_node, h: &base->percpu->dpc_timers);
195 dpc_enqueue_local(d: &base->percpu->timer_dpc);
196
197 spin_unlock(&base->percpu->lock, pirql);
198 }
199 }
200}
201
202static size_t timer_collect_expired(struct timer_base *base,
203 struct hlist_head *heads) {
204 time_us_t clock = base->clock = base->next_expiration_us;
205 size_t levels = 0;
206
207 for (int i = 0; i < TIMER_LEVELS; i++) {
208 uint32_t idx = (clock & TIMER_LEVEL_MASK) + i * TIMER_LEVEL_SIZE;
209
210 if (bitmap_test_and_clear(map: base->pending_map, bit: idx)) {
211 struct hlist_head *tmp = base->buckets + idx;
212 hlist_move_list(old: tmp, new: heads++);
213 levels++;
214 }
215
216 if (clock & TIMER_CLOCK_MASK)
217 break;
218
219 clock >>= TIMER_CLOCK_SHIFT;
220 }
221
222 return levels;
223}
224
225static int32_t timer_next_pending(struct timer_base *base, uint32_t offset,
226 time_us_t clock) {
227 uint32_t end = offset + TIMER_LEVEL_SIZE;
228 uint32_t start = offset + clock;
229
230 uint32_t pos = bitmap_find_next_bit(map: base->pending_map, nbits: end, start);
231 if (pos < end)
232 return pos - start;
233
234 pos = bitmap_find_next_bit(map: base->pending_map, nbits: start, start: offset);
235 return pos < start ? (int32_t) (pos + TIMER_LEVEL_SIZE - start) : -1;
236}
237
238static void timer_recalc_next_expiration(struct timer_base *base) {
239 SPINLOCK_ASSERT_HELD(&base->lock);
240 time_us_t next = TIME_US_MAX;
241 time_us_t clock = base->clock;
242
243 for (int lvl = 0; lvl < TIMER_LEVELS; lvl++) {
244 uint32_t offset = lvl * TIMER_LEVEL_SIZE;
245
246 /* Find the next set bit in pending_map for level */
247 int32_t pos =
248 timer_next_pending(base, offset, clock: clock & TIMER_LEVEL_MASK);
249
250 if (pos >= 0) {
251 /* Absolute minimum this bucket represents */
252 time_us_t sum = clock + (time_us_t) pos;
253 sum <<= TIMER_LEVEL_SHIFT(lvl);
254
255 if (sum < next)
256 next = sum;
257
258 /* If the bucket is within the current level's wraparound cycle,
259 * it's guaranteed to expire before any timer in higher levels */
260 time_us_t clock_lvl = clock & TIMER_CLOCK_MASK;
261 if ((time_us_t) pos <=
262 ((TIMER_CLOCK_FACTOR - clock_lvl) & TIMER_CLOCK_MASK))
263 break;
264 }
265
266 /* Check next level, shift down to its granularity */
267 clock >>= TIMER_CLOCK_SHIFT;
268 }
269
270 base->next_expiration_us = next;
271 base->pending = (next != TIME_US_MAX);
272 base->next_expiration_recalc = false;
273}
274
275static struct timer_base *timer_lock_base(struct timer *timer,
276 enum irql *irql) {
277 while (true) {
278 cpu_id_t cpu = timer_cpu_get(timer);
279 struct timer_base *base = timer_base_for_cpu(flags: timer->flags, cpu);
280
281 *irql = spin_lock_irq_disable(&base->lock);
282 if (timer_cpu_get(timer) == cpu)
283 return base;
284
285 spin_unlock(&base->lock, *irql);
286 }
287}
288
289static void timer_base_run(struct timer_base *base, enum irql *irql) {
290 struct hlist_head heads[TIMER_LEVELS];
291 SPINLOCK_ASSERT_HELD(&base->lock);
292
293 time_us_t time = time_get_us();
294
295 while (time >= base->clock && base->pending &&
296 time >= base->next_expiration_us) {
297 size_t levels = timer_collect_expired(base, heads);
298
299 for (size_t i = 0; i < levels; i++)
300 timer_expire_bucket(base, head: &heads[i], lirql: irql);
301
302 timer_recalc_next_expiration(base);
303 }
304}
305
306void timer_add_on(struct timer *timer, cpu_id_t cpu) {
307 enum irql irql;
308
309 /* Not pinned: set it to what's provided */
310 if (!(timer->flags & TIMER_FLAG_PINNED))
311 timer_cpu_set(timer, cpu);
312
313 cpu = timer_cpu_get(timer);
314 struct timer_base *base = timer_base_for_cpu(flags: timer->flags, cpu);
315 irql = spin_lock_irq_disable(&base->lock);
316
317 timer_add_internal(base, timer);
318
319 spin_unlock(&base->lock, irql);
320}
321
322void timer_add(struct timer *timer) {
323 /* Safe to call the _raw function here: we simply perform
324 * a read of the CPU ID and the caller enforces
325 * its own contracts wrt. this */
326 timer_add_on(timer, cpu: smp_id_raw());
327}
328
329void timer_add_local(struct timer *timer) {
330 timer->flags |= TIMER_FLAG_PINNED;
331 timer_add(timer);
332}
333
334void timer_add_global(struct timer *timer) {
335 timer->flags &= ~TIMER_FLAG_PINNED;
336 timer_add(timer);
337}
338
339static bool timer_delete_internal(struct timer *timer, bool shutdown) {
340 enum irql irql;
341 struct timer_base *base = timer_lock_base(timer, irql: &irql);
342
343 bool pending = hlist_unhashed(h: &timer->hlist_node) == 0;
344 if (pending) {
345 timer_list_del(timer);
346
347 uint32_t idx = timer_bucket_get(timer);
348 if (hlist_empty(h: &base->buckets[idx]))
349 bitmap_clear(map: base->pending_map, bit: idx);
350
351 timer_recalc_next_expiration(base);
352 }
353
354 if (shutdown)
355 timer->func = NULL;
356
357 cpu_id_t cpu = base->cpu;
358 spin_unlock(&base->lock, irql);
359
360 if (pending)
361 timer_base_reprogram_hardware(cpu);
362
363 return pending;
364}
365
366bool timer_delete(struct timer *timer) {
367 return timer_delete_internal(timer, false);
368}
369
370bool timer_shutdown(struct timer *timer) {
371 return timer_delete_internal(timer, true);
372}
373
374static bool timer_sync_wait(struct timer *timer) {
375 enum irql irql;
376 struct timer_base *base = timer_lock_base(timer, irql: &irql);
377
378 while (base->running == timer) {
379 spin_unlock(&base->lock, irql);
380 timer_sync_wait_spin();
381 base = timer_lock_base(timer, irql: &irql);
382 }
383
384 spin_unlock(&base->lock, irql);
385 return true;
386}
387
388bool timer_delete_sync(struct timer *timer) {
389 bool pending = timer_delete(timer);
390 timer_sync_wait(timer);
391 return pending;
392}
393
394bool timer_shutdown_sync(struct timer *timer) {
395 bool pending = timer_shutdown(timer);
396 timer_sync_wait(timer);
397 return pending;
398}
399
400bool timer_modify(struct timer *timer, time_us_t new_exp) {
401 enum irql outer = irql_raise(new_level: IRQL_HIGH_LEVEL);
402 enum irql irql;
403 struct timer_base *base = timer_lock_base(timer, irql: &irql);
404
405 bool pending = hlist_unhashed(h: &timer->hlist_node) == 0;
406 if (pending) {
407 timer_list_del(timer);
408 uint32_t idx = timer_bucket_get(timer);
409 if (hlist_empty(h: &base->buckets[idx])) {
410 bitmap_clear(map: base->pending_map, bit: idx);
411 }
412 } else if (!(timer->flags & TIMER_FLAG_PINNED) &&
413
414 /* The lock being held verifies the IRQL */
415 timer_cpu_get(timer) != smp_id(cond: TOPC_IRQL)) {
416 spin_unlock(&base->lock, irql);
417 timer_cpu_set(timer, cpu: smp_id(cond: TOPC_IRQL)); /* outer verifies this */
418 base = timer_lock_base(timer, irql: &irql);
419 }
420
421 timer->expiration_us = new_exp;
422 timer_add_internal(base, timer);
423
424 cpu_id_t cpu = base->cpu;
425 spin_unlock(&base->lock, irql);
426
427 timer_base_reprogram_hardware(cpu);
428 irql_lower(old_level: outer);
429 return pending;
430}
431
432bool timer_modify_pending(struct timer *timer, time_us_t new_exp) {
433 enum irql irql;
434 struct timer_base *base = timer_lock_base(timer, irql: &irql);
435
436 bool pending = hlist_unhashed(h: &timer->hlist_node) == 0;
437 if (pending) {
438 timer_list_del(timer);
439 uint32_t idx = timer_bucket_get(timer);
440 if (hlist_empty(h: &base->buckets[idx])) {
441 bitmap_clear(map: base->pending_map, bit: idx);
442 }
443
444 timer->expiration_us = new_exp;
445 timer_add_internal(base, timer);
446 }
447
448 cpu_id_t cpu = base->cpu;
449 spin_unlock(&base->lock, irql);
450
451 if (pending)
452 timer_base_reprogram_hardware(cpu);
453 return pending;
454}
455
456bool timer_modify_reduce(struct timer *timer, time_us_t new_exp) {
457 enum irql outer = irql_raise(new_level: IRQL_HIGH_LEVEL);
458 enum irql irql;
459 struct timer_base *base = timer_lock_base(timer, irql: &irql);
460
461 bool pending = hlist_unhashed(h: &timer->hlist_node) == 0;
462 if (pending) {
463 if (new_exp >= timer->expiration_us) {
464 spin_unlock(&base->lock, irql);
465 return true;
466 }
467
468 timer_list_del(timer);
469 uint32_t idx = timer_bucket_get(timer);
470 if (hlist_empty(h: &base->buckets[idx])) {
471 bitmap_clear(map: base->pending_map, bit: idx);
472 }
473 } else if (!(timer->flags & TIMER_FLAG_PINNED) &&
474 timer_cpu_get(timer) != smp_id(cond: TOPC_IRQL)) {
475 spin_unlock(&base->lock, irql);
476 timer_cpu_set(timer, cpu: smp_id(cond: TOPC_IRQL)); /* outer */
477 base = timer_lock_base(timer, irql: &irql);
478 }
479
480 timer->expiration_us = new_exp;
481 timer_add_internal(base, timer);
482
483 cpu_id_t cpu = base->cpu;
484 spin_unlock(&base->lock, irql);
485
486 timer_base_reprogram_hardware(cpu);
487 irql_lower(old_level: outer);
488 return pending;
489}
490
491void timer_base_reprogram_hardware(cpu_id_t cpu) {
492 enum irql outer = irql_raise(new_level: IRQL_HIGH_LEVEL);
493 if (cpu != smp_id(cond: TOPC_IRQL)) {
494 ipi_send(apic_id: cpu, IRQ_TIMER);
495 irql_lower(old_level: outer);
496 return;
497 }
498
499 struct timer_percpu *pcpu = PERCPU_PTR_FOR_CPU(timer_percpu, cpu);
500 struct clock_evdev *ced = pcpu->active_evdev;
501
502 if (!ced || ced->state != CLOCK_EVDEV_STATE_ONESHOT) {
503 irql_lower(old_level: outer);
504 return;
505 }
506
507 time_us_t next_us = TIME_US_MAX;
508
509 if (pcpu->bases[TIMER_BASE_LOCAL].pending)
510 next_us =
511 MIN(next_us, pcpu->bases[TIMER_BASE_LOCAL].next_expiration_us);
512 if (pcpu->bases[TIMER_BASE_GLOBAL].pending)
513 next_us =
514 MIN(next_us, pcpu->bases[TIMER_BASE_GLOBAL].next_expiration_us);
515
516 /* TODO: _DEFERRED handling */
517 if (next_us == TIME_US_MAX || next_us == (time_us_t) -1) {
518 irql_lower(old_level: outer);
519 return;
520 }
521
522 time_us_t now_us = time_get_us();
523 time_ns_t delta_ns =
524 (next_us > now_us) ? US_TO_NS(next_us - now_us) : ced->min_delta_ns;
525
526 CLAMP(delta_ns, ced->min_delta_ns, ced->max_delta_ns);
527 ced->set_next_event(ced, delta_ns);
528 irql_lower(old_level: outer);
529}
530
531enum irq_result timer_isr(void *ctx, uint8_t vec, struct irq_context *rsp) {
532 (void) ctx, (void) vec, (void) rsp;
533 cpu_id_t cpu = smp_id(cond: TOPC_IRQ);
534 if (!PERCPU_READY(timer_percpu))
535 return IRQ_HANDLED;
536
537 struct timer_percpu *pcpu = PERCPU_PTR(TOPC_IRQ, timer_percpu);
538
539 for (int i = 0; i < TIMER_BASE_MAX; i++) {
540 enum irql irql = spin_lock_irq_disable(&pcpu->bases[i].lock);
541 timer_base_run(base: &pcpu->bases[i], irql: &irql);
542 spin_unlock(&pcpu->bases[i].lock, irql);
543 }
544
545 timer_base_reprogram_hardware(cpu);
546 return IRQ_HANDLED;
547}
548
549void timers_init() {
550 struct clock_evdev_group *cedg =
551 kassert(clock_evdev_group_search_for(clock_global.timer_clock_evdev));
552 struct timer_percpu *iter;
553
554 percpu_for_each(timer_percpu, iter, cpu) {
555 struct clock_evdev *ced = clock_evdev_for_cpu(cedg, cpu);
556 iter->active_evdev = ced;
557 if (ced->change_state)
558 ced->change_state(ced, CLOCK_EVDEV_STATE_ONESHOT);
559 }
560}
561