1#include <structures/bitmap.h>
2#include <structures/hlist.h>
3#include <structures/locked_list.h>
4#include <time/clock.h>
5#include <time/clock_evdev.h>
6#include <time/time.h>
7
8enum timer_base_type {
9 TIMER_BASE_LOCAL,
10 TIMER_BASE_GLOBAL,
11 TIMER_BASE_DEFERRED,
12 TIMER_BASE_MAX
13};
14
15#define TIMER_LEVELS 10
16#define TIMER_LEVEL_BITS 6
17#define TIMER_LEVEL_SIZE (1ULL << TIMER_LEVEL_BITS)
18#define TIMER_LEVEL_MASK (TIMER_LEVEL_SIZE - 1)
19#define TIMER_LEVEL_OFFSET(n) ((n) * TIMER_LEVEL_SIZE)
20
21#define TIMER_CLOCK_SHIFT 4
22#define TIMER_CLOCK_FACTOR (1ULL << TIMER_CLOCK_SHIFT)
23#define TIMER_CLOCK_MASK (TIMER_CLOCK_FACTOR - 1)
24
25#define TIMER_LEVEL_SHIFT(n) ((n) * TIMER_CLOCK_SHIFT)
26#define TIMER_LEVEL_GRANULARITY(n) (1ULL << TIMER_LEVEL_SHIFT(n))
27#define TIMER_LEVEL_START(n) \
28 ((TIMER_LEVEL_SIZE - 1) << (((n) - 1) * TIMER_CLOCK_SHIFT))
29#define TIMER_LEVEL_END(n) (TIMER_LEVEL_START(n + 1) - 1)
30
31#define TIMER_WHEEL_SIZE (TIMER_LEVELS * TIMER_LEVEL_SIZE)
32#define TIMER_WHEEL_TIMEOUT_CUTOFF (TIMER_LEVEL_START(TIMER_LEVELS))
33#define TIMER_WHEEL_TIMEOUT_MAX \
34 (TIMER_WHEEL_TIMEOUT_CUTOFF - TIMER_LEVEL_GRANULARITY(TIMER_LEVELS - 1))
35
36#define TIMER_SYNC_SPIN_TIMES 500
37
38/*
39 * Since we don't have jiffies, the finest granularity we work with is
40 * a single microsecond, and this is a non-cascading implementation,
41 * resulting in this hierarchy (wide table, so we turn clang-format off):
42 */
43
44// clang-format off
45
46/*
47 * Level Offset Granularity Range
48 * 0 0 1 us 0 us - 63 us
49 * 1 64 16 us 64 us - 1,023 us (~64us - ~1ms)
50 * 2 128 256 us 1,024 us - 16,383 us (~1ms - ~16ms)
51 * 3 192 4,096 us (~4ms) 16,384 us - 262,143 us (~16ms - ~262ms)
52 * 4 256 65,536 us (~65ms) 262,144 us - 4,194,303 us (~262ms - ~4s)
53 * 5 320 1,048,576 us (~1s) 4,194,304 us - 67,108,863 us (~4s - ~1m)
54 * 6 384 16,777,216 us (~16s) 67,108,864 us - 1,073,741,823 us (~1m - ~17m)
55 * 7 448 268,435,456 us (~4m) 1,073,741,824 us - 17,179,869,183 us (~17m - ~5h)
56 * 8 512 4,294,967,296 us (~1h) 17,179,869,184 us - 274,877,906,943 us (~5h - ~3d)
57 * 9 576 68,719,476,736 us (~19h) 274,877,906,944 us - 4,398,046,511,103 us (~3d - ~50d)
58 */
59
60// clang-format on
61
62/* Otherwise there won't be enough room in `timer_flags` */
63static_assert(TIMER_WHEEL_SIZE <= 1024);
64
65struct timer_base {
66 enum timer_base_type type;
67 cpu_id_t cpu;
68 struct spinlock lock;
69 struct timer *running;
70 struct timer_percpu *percpu;
71 time_us_t clock; /* Updated before enqueue */
72 time_us_t next_expiration_us; /* Expiration ts of the next timer */
73 bool idle;
74 bool pending; /* Any timers pending? */
75 bool next_expiration_recalc;
76
77 BITMAP_DECLARE(pending_map, TIMER_WHEEL_SIZE);
78 struct hlist_head buckets[TIMER_WHEEL_SIZE];
79};
80
81struct timer_percpu {
82 struct timer_base bases[TIMER_BASE_MAX];
83 struct dpc timer_dpc;
84
85 struct spinlock lock; /* THIS one is for the dpc_timers */
86 struct hlist_head dpc_timers;
87 struct clock_evdev *active_evdev;
88};
89
90struct clock_globals {
91 struct locked_list clocks;
92 struct locked_list clock_evdevs;
93 struct locked_list clock_evdev_groups;
94 char *timer_clock_evdev;
95};
96
97extern struct clock_globals clock_global;
98void timer_base_reprogram_hardware(cpu_id_t cpu);
99
100struct clock *hpet_clock_init(void);
101
102void timekeeper_init(void);
103void timekeeper_update(void);
104time_ns_t timekeeper_get_ns(void);
105
106#define TIMEKEEPER_TRY_READ_SPINS 4
107bool timekeeper_try_get_ns(time_ns_t *out);
108time_us_t timekeeper_get_us(void);
109
110struct clock *clock_get_best(void);
111struct clock *clock_get_by_name(const char *name);
112