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