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