1/* @title: Watchdog */
2#pragma once
3#include <linker/symbol_table.h>
4#include <math/ewma.h>
5#include <math/fixed.h>
6#include <structures/cpu_mask.h>
7#include <structures/list.h>
8#include <structures/locked_list.h>
9#include <sync/seqlock.h>
10#include <sync/spinlock.h>
11#include <time/timer.h>
12#include <types/types.h>
13
14/* TODO: This watchdog implementation is the "minimal correct fallback",
15 * in the future we will abstract + scale this up, however, what we have
16 * right now is enough for a first iteration and avoid bikeshedding
17 * before we get any real consumers */
18
19/*
20 * Watchdog architecture diagram
21 *
22 * ┌──────────┐
23 * │ Master │ ┌─────┐
24 * │ Watchdog │◀────│ NMI │
25 * └──────────┘ └─────┘
26 * │
27 * ┌────────watches────────┐
28 * │ │ │
29 * ▼ ▼ ▼
30 * ┌──────────┐┌──────────┐┌──────────┐
31 * │ Worker ││ Worker ││ Worker │ ┌───────────────────┐
32 * │Watchdog 0││Watchdog 1││Watchdog 2│◀───│ struct timer IRQs │
33 * └──────────┘└──────────┘└──────────┘ └───────────────────┘
34 * │ │ │
35 * monitors code execution with dynamic
36 * │ callback registration │
37 * ▼ ▼ ▼
38 * ┌───────────────────────────┐
39 * │ │
40 * │ Tests, subsystems, │
41 * │ non-hangup livelock and │
42 * │ deadlock detection, etc. │
43 * │ │
44 * └───────────────────────────┘
45 *
46 * The premise of the watchdog is that certain code can lockup/hang.
47 * However, as with many supervision programs, we run into a
48 * "Who watches the watchers?" (Quis custodiet ipsos custodes?) problem.
49 *
50 * For instance, in userspace, the runtime/VM watches the program, the
51 * OS watches the runtime, and, depending on the OS architecture,
52 * the kernel watches the user-facing components.
53 *
54 * Here, the worker watchdog watches the kernel,
55 * and the master watchdog watches the workers.
56 *
57 * The reason for such an architecture is as follows:
58 * When enabled, the master watchdog uses a completely separate pipeline
59 * than worker watchdogs, which simultaneously restricts it, and also
60 * makes it more powerful. The master watchdog, for instance,
61 * does NOT use `struct timer`, which prevents it from failing
62 * due to a bug in the timer subsystem. Furthermore, it also
63 * operates on a completely separate clock. On x86, for instance,
64 * it uses the PIT, whereas the worker watchdogs typically use the LAPIC.
65 *
66 * And, as the architecture diagram outlines, the master is
67 * signaled through an NMI, as opposed to a standard IRQ, which allows
68 * it to detect when the *worker* watchdogs do not have heartbeats
69 * due to a hard lockup inside of an ISR.
70 *
71 * Vocabulary:
72 *
73 * "heartbeats" refer to the events where a watchdog worker receives
74 * an interrupt, and acknowledges them. Heartbeats only are
75 * incremented/occur at the *end* of the watchdog's execution
76 * of callbacks and work, NOT at the beginning
77 *
78 * "ticks" are watchdog master ticks (different from heartbeats)
79 *
80 * Lockups are specific cases of hangs where the system fails
81 * to respond to interrupts, whereas hangs are the general
82 * word for the system failing to respond. Here, we are able
83 * to separate the two, i.e. in almost all cases of a lockup,
84 * we can report it as a lockup, and not a general purpose hang
85 *
86 */
87
88/* Notes about the state machine:
89 *
90 * Every CPU is tracked by the master watchdog according to this state machine.
91 *
92 * At each state, the behavior regarding the watchdog's tracking of the various
93 * CPUs changes.
94 *
95 * NORMAL = passive observance of heartbeats aggregate in the domain
96 * SUSPECT = a few CPUs that were previously NORMAL, pulled for tracking.
97 * for these suspect CPUs, they'll have their lockup_score
98 *
99 * CRITICAL = CPUs continuously SUSPECT for a while, pulled into this tier
100 * for live examination and IPIs + petting
101 *
102 */
103enum watchdog_master_state {
104 WATCHDOG_STATE_NORMAL, /* All OK */
105 WATCHDOG_STATE_SUSPECT, /* This is a stage in between normal execution
106 * and issuing a warning. The premise:
107 *
108 * When we start to see suspicious
109 * behavior from some CPUs, we don't
110 * immediately send a warning, and we also
111 * don't want to ALWAYS be investigating,
112 * because that incurs a cost every tick.
113 *
114 * Thus, we have this SUSPECT stage
115 * where we check suspect_cpus and the percpu
116 * array, and send NMIs/report data
117 *
118 * i.e. "Passive Supervision"
119 */
120
121 /* CRITICAL is our name for what is exposed as "warn" */
122 WATCHDOG_STATE_CRITICAL, /* This is where the warning is issued, and the
123 * idea is that the warning is the "last chance"
124 * before the master will panic
125 *
126 * i.e. "Active Interrogation"
127 *
128 * Notably, only ONE CPU needs to exhibit the
129 * PANIC state for the system to panic */
130 WATCHDOG_STATE_PANIC,
131 WATCHDOG_STATE_MAX,
132};
133
134/* NOTE: By default, not tunable by cmdline */
135
136/* TODO: Tune these and test around */
137#define WATCHDOG_WINDOW_BUCKETS 8
138#define WATCHDOG_MASTER_SEQCOUNT_SPINS 3
139#define WATCHDOG_NUM_BUCKETS 64
140#define WATCHDOG_MSG_LEN_MAX 512
141#define WATCHDOG_EWMA_ALPHA FX(0.15)
142#define WATCHDOG_SUSPECT_LOG_TICK_THRESHOLD (40)
143#define WATCHDOG_CRITICAL_LOG_TICK_THRESHOLD (20)
144
145/* This is influenced by pets and anti-pets
146 *
147 * Essentially, pet status has 3 outcomes:
148 * neutral - pets > 0
149 * stuck - pets == 0 and anti_pets == 0
150 * penalty - pets == 0 and anti_pets > 0
151 *
152 * where a neutral score does WATCHDOG_CRITICAL_IPI_TESTS, stuck
153 * bumps it down 25%, and penalty by another 25% from the original
154 */
155#define WATCHDOG_CRITICAL_IPI_TESTS \
156 40 /* Test an IPI ping pong \
157 * times to get the avg, this is 4s */
158
159/* if latency <= threshold, we pass */
160#define WATCHDOG_CRITICAL_PASS_THRESHOLD_MS 250
161#define WATCHDOG_CRITICAL_PANIC_THRESHOLD_MS \
162 10000 /* If we delay this long, panic */
163
164#define WATCHDOG_CRITICAL_TESTS_FACTOR FX(0.4)
165#define WATCHDOG_CRITICAL_PETS_FACTOR FX(0.6)
166
167/* This is the hard stall detector, only checking if the heartbeat
168 * counter has moved, and not using the incremental checks
169 * and logging that other cases do. TODO: In the future watchdog redesign,
170 * we can consider throwing out the incrementality entirely in favor of this */
171#define WATCHDOG_STALL_TIMEOUT_DEFAULT_MS 15000
172
173#define WATCHDOG_STALL_GRACE_TICKS 20
174struct watchdog_bucket {
175 size_t epoch; /* Epoch counter to see which buckets are outdated */
176 size_t heartbeats; /* Heartbeats in this bucket */
177};
178
179struct watchdog_buckets {
180 struct seqcount seq;
181 struct watchdog_bucket buckets_internal[WATCHDOG_NUM_BUCKETS];
182 size_t idx;
183 size_t curr_epoch;
184 time_ms_t last_heartbeat_ms;
185};
186
187struct watchdog_bucket_snapshot {
188 size_t idx;
189 size_t curr_epoch;
190 time_ms_t last_heartbeat_ms;
191 struct watchdog_bucket buckets[WATCHDOG_NUM_BUCKETS];
192};
193
194struct watchdog_percpu_response {
195 /* This structure holds everything that a CPU responds with when IPI'd
196 * in CRITICAL state so we can examine what's going on, protected by
197 * the seqcount here */
198 /* TODO: */
199
200 time_ms_t finished_ms; /* Published before seqcount ack */
201 struct seqcount seqcount;
202};
203
204/* Rules for master callbacks:
205 *
206 * 1. No locks of any kind may be acquired
207 * 2. No waiting may happen, and no faults may be taken
208 * 3. No recursion is permitted in callbacks
209 *
210 * Rules for worker callbacks:
211 * 1. Only IRQ safe locks may be taken
212 * 2. No waiting, no faults
213 * 3. Recursion discouraged
214 */
215struct watchdog_callback {
216 struct list_head list;
217 void (*fn)(struct watchdog_callback *);
218 void *private;
219};
220
221/* Updated by `cpu`, read by the master */
222struct watchdog_percpu {
223 cpu_id_t id;
224
225 /* Pets, when enabled */
226 bool pets_enabled; /* This is a per-cpu LOCAL variable, never read
227 * or modified outside of it, no need for atomics */
228 struct seqcount pets_seq;
229
230 _Atomic size_t pets;
231 _Atomic size_t anti_pets;
232
233 /* Monotonic count of heartbeats the CPU has emitted */
234 _Atomic uint64_t heartbeat_seq;
235
236 struct watchdog_percpu_response response;
237 struct watchdog_buckets buckets;
238 struct timer timer;
239 struct locked_list callback_list;
240};
241
242/* NOTE: This is NOT just for CPU 0 (the host of the master), the master
243 * has one of these for *each* CPU to track its state, and this remains
244 * readable and writable by the master ONLY */
245struct watchdog_master_cpu {
246 cpu_id_t id;
247 struct watchdog_percpu *pcpu;
248 enum watchdog_master_state state;
249 /* The premise: if a CPU doesn't respond to interrupts for a short
250 * amount of time (100ms), it could just be because we're running
251 * in a VM and the host system is highly contended, and the vCPUs
252 * are not getting much CPU time, which is fine
253 *
254 *
255 *
256 ^
257 │
258 1 │ ┌──────────────>
259 │ │
260 │ │
261 │ ┌──────┘
262 │ │
263 │ │
264 0.7 │ ┌────┘
265 │ │
266 │ │
267Score │ ┌─────┘ < a progressively longer
268 │ │ interval with no IRQ response
269 │ │ will increase the lockup
270 │ < this is fine > │ score until it reaches 1 >
271 0.3 │ ┌───┐ │
272 │ │ │ │
273 │ │ │ │
274 │ │ └──┐ │
275 │ │ │ │
276 │ │ │ │
277 0 └────────────────────────────Time──────────────────────────────>
278
279 */
280 struct ewma lockup_ewma; /* Used in SUSPECT */
281 fx32_32_t lockup_score; /* [0, 1], the way that this works is that
282 * depending on state, it has four behaviors:
283 *
284 * NORMAL = 0
285 * SUSPECT = (0, warn_score), this
286 * score is an EWMA of
287 *
288 * expected heartbeats that didn't fire
289 * --------------------------------------
290 * total expected heartbeats
291 *
292 * updated per tick advancement
293 *
294 * Once this reaches master_warn_score, then...
295 *
296 * CRITICAL = [warn_score, panic_score), where
297 * the score range now is
298 *
299 * failed tests
300 * ---------------- * WATCHDOG_CRITICAL_TEST_WEIGHT
301 * total tests
302 *
303 * + pet_factor * WATCHDOG_CRITICAL_PET_WEIGHT
304 *
305 * mapped to [warn_score, panic_score), where
306 *
307 * pet_factor = 0 if pets > 0 else 1
308 *
309 * and WATCHDOG_CRITICAL_PET_WEIGHT
310 * + WATCHDOG_CRITICAL_ACK_WEIGHT = 1.0
311 *
312 * PANIC = [panic_score, 1], we just panic and
313 * echo out all relevant information
314 */
315
316 /* stack, each record is latency */
317 time_ms_t critical_tests[WATCHDOG_CRITICAL_IPI_TESTS];
318 time_ms_t critical_test_start; /* CRITICAL only - the timestamp for
319 * the current outgoing test's start time */
320 size_t critical_tests_done; /* CRITICAL only */
321 size_t critical_start_tick; /* Started tick */
322
323 size_t suspect_start_tick; /* SUSPECT only - stores the master's
324 * tick that it entered in on, so we can
325 * warn about lingerers. This notably is NOT
326 * present for CRITICAL, because that runs
327 * a finite amount of tests */
328
329 /* Stall detection state, used to immediately panic on
330 * completely stuck CPUs */
331 uint64_t last_seen_heartbeat; /* heartbeat_seq at last observed progress */
332 size_t last_progress_tick; /* master tick when it last progressed */
333};
334
335struct watchdog_master {
336 size_t tick; /* +1 per tick */
337
338 /* Bitmap so that watchdog_master_cpu does not have to be fully iterated
339 * over - we can just cpu_mask_for_each() over this
340 *
341 * we need panic_cpus so we can batch a panic */
342 struct cpu_mask cpu_masks[WATCHDOG_STATE_MAX];
343
344 /* Because the watchdog is NOT allowed to allocate, and struct cpu_mask
345 * allocates memory on systems with > 64 CPUs, we need to keep
346 * a scratch mask here so the watchdog can do CPU mask related operations
347 * without possibly going and allocating anything */
348 struct cpu_mask scratch_mask;
349 struct watchdog_master_cpu *cpus;
350
351 /* This is just for logging so it can log once at most for a tick */
352 char msg_buf[WATCHDOG_MSG_LEN_MAX];
353};
354
355/* Just as a means of aggregating cmdline options */
356struct watchdog_config {
357 /* ========== These are cmdline/config values ========== */
358
359 /* These are ns_t because that's what the cmdline parser gives us */
360
361 /* watchdog.master.tick_interval, some time duration */
362 time_ns_t master_tick_interval;
363
364 time_ns_t worker_heartbeat_interval;
365
366 /* watchdog.bucket_interval - applies for both master and worker */
367 time_ns_t bucket_interval;
368
369 fx32_32_t master_panic_score; /* score >= this, we panic */
370
371 fx32_32_t master_critical_score; /* score >= this, we warn in logs */
372
373 /* A CPU whose heartbeat counter hasn't
374 * moved for this long panic, bypassing scoring,
375 * with zero disabling the detector */
376 time_ns_t master_stall_timeout;
377
378 time_ns_t master_print_interval; /* prevents spam in some scenarios where
379 * there might be no hangup,
380 * just slowdowns */
381
382 fx32_32_t master_suspect_score; /* missed/expected heartbeats >= this,
383 * we move to SUSPECT */
384};
385
386struct watchdog_globals {
387 /* ========== These are computed ========== */
388 time_ms_t bucket_interval_ms;
389 size_t expected_heartbeats_per_bucket;
390
391 /* master_stall_timeout in master ticks, with
392 * 0 indicating it's disabled */
393 size_t stall_timeout_ticks;
394
395 irq_t critical_test_irq;
396};
397
398void watchdog_init(void);
399void watchdog_start(void);
400void watchdog_anti_pet(void);
401void watchdog_pet(void);
402void watchdog_callback_add(cpu_id_t cpu, struct watchdog_callback *cb);
403void watchdog_callback_remove(cpu_id_t cpu, struct watchdog_callback *cb);
404
405#define watchdog_cpu_for_each(__i, state) \
406 cpu_mask_for_each(__i, watchdog_master.cpu_masks[state])
407