1#include <math/range.h>
2#include <mem/alloc.h>
3#include <nightmare/nightmare.h>
4#include <sch/sched.h>
5#include <sync/lock_chk.h>
6#include <sync/mutex.h>
7#include <sync/qspinlock.h>
8#include <sync/rwlock.h>
9#include <thread/thread.h>
10#include <time/time.h>
11
12#define WAKE_STORM_DEFAULT_SLEEPER_STALL_MS 10000
13
14struct wake_storm_options {
15 time_ns_t sleeper_stall_ms;
16
17 /* Defaults to off, so we can see invariants fail */
18 uint64_t drop_wake_after_ops;
19 uint64_t uncounted_wake_after_ops;
20};
21
22static struct wake_storm_options wake_storm_options;
23
24NIGHTMARE_OPTIONS_DECLARE(
25 wake_storm, struct wake_storm_options, wake_storm_options,
26 CMDLINE_SCHEMA_PROP(struct wake_storm_options, sleeper_stall_ms,
27 .types = CMDLINE_TYPES(CMDLINE_TYPE_DURATION),
28 .range = RANGE(MS_TO_NS(100), TIME_NS_MAX)),
29 CMDLINE_SCHEMA_PROP(struct wake_storm_options, drop_wake_after_ops),
30 CMDLINE_SCHEMA_PROP(struct wake_storm_options, uncounted_wake_after_ops));
31
32#ifdef TEST_NIGHTMARE_WAKE
33
34enum wake_storm_lane : uint8_t {
35 WAKE_LANE_ACCOUNTING = 1,
36 WAKE_LANE_NESTING,
37 WAKE_LANE_STARVATION,
38 WAKE_LANE_HARNESS,
39};
40
41enum wake_storm_failure_phase : uint8_t {
42 WAKE_FAILURE_EMPTY = 0,
43 WAKE_FAILURE_WRITING,
44 WAKE_FAILURE_READY,
45 WAKE_FAILURE_REPORTED,
46};
47
48struct wake_storm_sleeper {
49 _Atomic(struct thread *) th;
50
51 /* These don't have to be equal because thread_wake() sets WAKE_MATCHED
52 * regardless of if the target has reached thread_prepare_to_sleep() */
53 _Atomic uint64_t issued;
54 _Atomic uint64_t observed;
55
56 /* For noticing sleepers that got stuck from the probe */
57 uint64_t sampled_observed;
58 time_ms_t last_change_ms;
59
60 uint32_t sampled_nesting_max;
61};
62
63struct wake_storm_failure {
64 _Atomic enum wake_storm_failure_phase phase;
65 enum wake_storm_lane lane;
66 size_t sleeper;
67 uint64_t observed_a;
68 uint64_t observed_b;
69
70 const char *file;
71 uint32_t line;
72};
73
74struct wake_storm_state {
75 struct mutex mtx;
76 struct rwlock rw;
77 struct qspinlock qspin;
78
79 _Atomic uint64_t wakes_issued;
80 _Atomic size_t registered;
81 atomic_bool starvation_claimed;
82 bool probe_was_quiesced;
83
84 struct wake_storm_failure failure;
85
86 time_ms_t sleeper_stall_ms;
87 size_t sleeper_count;
88
89 uint32_t deepest_nesting;
90 uint64_t total_observed;
91
92 struct wake_storm_sleeper sleepers[];
93};
94
95LOCK_CHK_CLASS_DECLARE_LOCAL(wake_storm_mtx);
96LOCK_CHK_CLASS_DECLARE_LOCAL(wake_storm_rw);
97LOCK_CHK_CLASS_DECLARE_LOCAL(wake_storm_qspin);
98
99static struct wake_storm_state *wake_state(struct nightmare_ctx *ctx) {
100 return ctx->private;
101}
102
103static const char *wake_lane_name(enum wake_storm_lane lane) {
104 switch (lane) {
105 case WAKE_LANE_ACCOUNTING: return "accounting";
106 case WAKE_LANE_NESTING: return "nesting";
107 case WAKE_LANE_STARVATION: return "starvation";
108 case WAKE_LANE_HARNESS: return "harness";
109 }
110 return "unknown";
111}
112
113#define wake_record_failure(state_, lane_, sleeper_, a_, b_) \
114 wake_record_failure_at((state_), (lane_), (sleeper_), (a_), (b_), \
115 __RELFILE__, __LINE__)
116
117static bool wake_record_failure_at(struct wake_storm_state *state,
118 enum wake_storm_lane lane, size_t sleeper,
119 uint64_t observed_a, uint64_t observed_b,
120 const char *file, uint32_t line) {
121 enum wake_storm_failure_phase expected = WAKE_FAILURE_EMPTY;
122 if (!atomic_compare_exchange_strong_explicit(
123 &state->failure.phase, &expected, WAKE_FAILURE_WRITING,
124 memory_order_acq_rel, memory_order_acquire))
125 return false;
126
127 state->failure.lane = lane;
128 state->failure.sleeper = sleeper;
129 state->failure.observed_a = observed_a;
130 state->failure.observed_b = observed_b;
131 state->failure.file = file;
132 state->failure.line = line;
133 atomic_store_explicit(&state->failure.phase, WAKE_FAILURE_READY,
134 memory_order_release);
135 return true;
136}
137
138static void wake_report_failure(struct wake_storm_state *state) {
139 enum wake_storm_failure_phase expected = WAKE_FAILURE_READY;
140 if (!atomic_compare_exchange_strong_explicit(
141 &state->failure.phase, &expected, WAKE_FAILURE_REPORTED,
142 memory_order_acq_rel, memory_order_acquire))
143 return;
144
145 nightmare_finding_at(
146 site: &(const struct nightmare_finding_site){.kind = "wake_invariant",
147 .tier = NIGHTMARE_TIER_CONFIDENT,
148 .file = state->failure.file,
149 .line = state->failure.line},
150 discriminator: (uint64_t) state->failure.lane,
151 fmt: "lane=%s sleeper=%lu observed_a=%lu observed_b=%lu",
152 wake_lane_name(lane: state->failure.lane),
153 (unsigned long) state->failure.sleeper,
154 (unsigned long) state->failure.observed_a,
155 (unsigned long) state->failure.observed_b);
156 nightmare_stop_after_finding();
157}
158
159static void wake_storm_contend(struct wake_storm_state *state,
160 struct nightmare_worker *self) {
161 mutex_lock(&state->mtx);
162 for (volatile int i = 0; i < (int) (nightmare_rand(rng: &self->rng) & 0xF); i++)
163 cpu_relax();
164 mutex_unlock(&state->mtx);
165
166 if (nightmare_rand(rng: &self->rng) & 1) {
167 rw_lock(&state->rw, RWLOCK_ACQUIRE_READ);
168 for (volatile int i = 0; i < 4; i++)
169 cpu_relax();
170 rw_unlock(&state->rw);
171 } else {
172 rw_lock(&state->rw, RWLOCK_ACQUIRE_WRITE);
173 for (volatile int i = 0; i < 4; i++)
174 cpu_relax();
175 rw_unlock(&state->rw);
176 }
177
178 enum irql irql = qspin_lock(&state->qspin);
179 for (volatile int i = 0; i < 4; i++)
180 cpu_relax();
181 qspin_unlock(&state->qspin, irql);
182}
183
184static void wake_storm_sleeper_main(struct nightmare_ctx *ctx,
185 struct nightmare_worker *self,
186 size_t slot) {
187 struct wake_storm_state *state = wake_state(ctx);
188 struct wake_storm_sleeper *me = &state->sleepers[slot];
189 struct thread *t = thread_get_current();
190
191 atomic_store_explicit(&me->th, t, memory_order_release);
192 atomic_fetch_add_explicit(&state->registered, 1, memory_order_release);
193
194 while (!nightmare_must_stop()) {
195 if (nightmare_must_park()) {
196 nightmare_park(worker: self);
197 continue;
198 }
199
200 wake_storm_contend(state, self);
201
202 /* expected_wake_src is the thread pointer
203 *
204 * this means that it decides who can wake us:
205 *
206 * - our waker
207 * - nightmare_publish_stop
208 * - built-in waker perturber */
209 thread_prepare_to_sleep(t, r: THREAD_SLEEP_REASON_MANUAL,
210 wait_type: THREAD_WAIT_INTERRUPTIBLE, expect_wake_src: t);
211
212 /* Re check after we arm */
213 if (nightmare_must_stop() || nightmare_must_park()) {
214 atomic_fetch_add_explicit(&me->issued, 1, memory_order_release);
215 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_MANUAL,
216 prio: THREAD_PRIO_CLASS_TIMESHARE, wake_src: t);
217 }
218
219 thread_yield_until_wake_match();
220
221 if (nightmare_must_stop())
222 break;
223
224 atomic_fetch_add_explicit(&me->observed, 1, memory_order_release);
225 NIGHTMARE_PROGRESS();
226 }
227}
228
229/* Wake up EVERYONE, which is used because otherwise the stutter perturber
230 * would time out waiting for subjects that cannot park because they're
231 * busy waiting for the wake match. TODO: Generalize this and revise
232 * the sleeping functions */
233static void wake_storm_release_all(struct wake_storm_state *state,
234 bool count_issued) {
235 for (size_t i = 0; i < state->sleeper_count; i++) {
236 struct thread *t =
237 atomic_load_explicit(&state->sleepers[i].th, memory_order_acquire);
238 if (!t || !thread_get(obj: t))
239 continue;
240 if (count_issued)
241 atomic_fetch_add_explicit(&state->sleepers[i].issued, 1,
242 memory_order_release);
243 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_MANUAL,
244 prio: THREAD_PRIO_CLASS_TIMESHARE, wake_src: t);
245 thread_put(t);
246 }
247}
248
249static void wake_storm_waker_main(struct nightmare_ctx *ctx,
250 struct nightmare_worker *self) {
251 struct wake_storm_state *state = wake_state(ctx);
252
253 while (!nightmare_must_stop()) {
254 if (nightmare_must_park()) {
255 wake_storm_release_all(state, /* count_issued = */ true);
256 nightmare_park(worker: self);
257 continue;
258 }
259
260 if (atomic_load_explicit(&state->registered, memory_order_acquire) ==
261 0) {
262 scheduler_yield();
263 continue;
264 }
265
266 size_t slot = nightmare_rand(rng: &self->rng) % state->sleeper_count;
267 struct wake_storm_sleeper *target = &state->sleepers[slot];
268 struct thread *t =
269 atomic_load_explicit(&target->th, memory_order_acquire);
270 if (!t || !thread_get(obj: t)) {
271 scheduler_yield();
272 continue;
273 }
274
275 uint64_t ops = atomic_fetch_add_explicit(&state->wakes_issued, 1,
276 memory_order_relaxed);
277
278 /* Count a wake as issued but never actually issue it */
279 bool drop = wake_storm_options.drop_wake_after_ops &&
280 ops >= wake_storm_options.drop_wake_after_ops;
281
282 /* Deliver the wake without counting it */
283 bool uncounted = wake_storm_options.uncounted_wake_after_ops &&
284 ops >= wake_storm_options.uncounted_wake_after_ops;
285
286 if (drop) {
287 atomic_fetch_add_explicit(&target->issued, 1, memory_order_release);
288 } else if (uncounted) {
289 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_MANUAL,
290 prio: THREAD_PRIO_CLASS_TIMESHARE, wake_src: t);
291 } else {
292 atomic_fetch_add_explicit(&target->issued, 1, memory_order_release);
293 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_MANUAL,
294 prio: THREAD_PRIO_CLASS_TIMESHARE, wake_src: t);
295 }
296
297 thread_put(t);
298 scheduler_yield();
299 }
300
301 wake_storm_release_all(state, /* count_issued = */ false);
302}
303
304NIGHTMARE_WORKER(wake_storm_worker) {
305 if (NM_SELF->index == 0)
306 wake_storm_waker_main(ctx: NM_CTX, self: NM_SELF);
307 else
308 wake_storm_sleeper_main(ctx: NM_CTX, self: NM_SELF, slot: NM_SELF->index - 1);
309}
310
311static void wake_probe_rebaseline(struct wake_storm_state *state,
312 time_ms_t now) {
313 for (size_t i = 0; i < state->sleeper_count; i++) {
314 state->sleepers[i].sampled_observed = atomic_load_explicit(
315 &state->sleepers[i].observed, memory_order_acquire);
316 state->sleepers[i].last_change_ms = now;
317 }
318}
319
320/* A sleeper that stops advancing while wakers keep issuing to it
321 * are often lost wakes but scheduler starvation can cause that too */
322static void wake_storm_probe(struct nightmare_ctx *ctx) {
323 if (nightmare_must_stop())
324 return;
325
326 struct wake_storm_state *state = wake_state(ctx);
327 time_ms_t now = time_get_ms();
328
329 if (nightmare_must_park()) {
330 wake_probe_rebaseline(state, now);
331 state->probe_was_quiesced = true;
332 return;
333 }
334 if (state->probe_was_quiesced) {
335 wake_probe_rebaseline(state, now);
336 state->probe_was_quiesced = false;
337 return;
338 }
339
340 for (size_t i = 0; i < state->sleeper_count; i++) {
341 struct wake_storm_sleeper *sleeper = &state->sleepers[i];
342 if (!atomic_load_explicit(&sleeper->th, memory_order_acquire))
343 continue;
344
345 uint64_t observed =
346 atomic_load_explicit(&sleeper->observed, memory_order_acquire);
347 if (observed != sleeper->sampled_observed) {
348 sleeper->sampled_observed = observed;
349 sleeper->last_change_ms = now;
350 continue;
351 }
352 if (now - sleeper->last_change_ms < state->sleeper_stall_ms)
353 continue;
354
355 bool expected = false;
356 if (!atomic_compare_exchange_strong_explicit(
357 &state->starvation_claimed, &expected, true,
358 memory_order_acq_rel, memory_order_acquire))
359 return;
360
361 NIGHTMARE_FINDING_TIER(
362 "wake_starvation", NIGHTMARE_TIER_AMBIGUOUS, (uint64_t) i,
363 "sleeper=%lu issued=%lu observed=%lu silent_ms=%lu",
364 (unsigned long) i,
365 (unsigned long) atomic_load_explicit(&sleeper->issued,
366 memory_order_acquire),
367 (unsigned long) observed,
368 (unsigned long) (now - sleeper->last_change_ms));
369 nightmare_stop_after_finding();
370 return;
371 }
372}
373
374static struct nightmare_verdict
375wake_storm_quiesce_check(struct nightmare_ctx *ctx) {
376 struct wake_storm_state *state = wake_state(ctx);
377
378 uint64_t total_observed = 0;
379 uint32_t deepest = 0;
380
381 for (size_t i = 0; i < state->sleeper_count; i++) {
382 struct wake_storm_sleeper *sleeper = &state->sleepers[i];
383 struct thread *t =
384 atomic_load_explicit(&sleeper->th, memory_order_acquire);
385 if (!t)
386 continue;
387
388 /* `observed` can lag `issued`, never inverted
389 *
390 * Reading `observed` first prevents an inversion
391 */
392 uint64_t observed =
393 atomic_load_explicit(&sleeper->observed, memory_order_acquire);
394 uint64_t issued =
395 atomic_load_explicit(&sleeper->issued, memory_order_acquire);
396 total_observed += observed;
397 if (observed > issued) {
398 wake_record_failure(state, WAKE_LANE_ACCOUNTING, i, issued,
399 observed);
400 break;
401 }
402
403 uint32_t nesting = scheduler_yield_nesting_max(t);
404 if (nesting > deepest)
405 deepest = nesting;
406
407 if (nesting < sleeper->sampled_nesting_max)
408 sleeper->sampled_nesting_max = nesting;
409
410 if (nesting > SCHED_MAX_YIELD_NESTING &&
411 nesting > sleeper->sampled_nesting_max) {
412 sleeper->sampled_nesting_max = nesting;
413 wake_record_failure(state, WAKE_LANE_NESTING, i, nesting,
414 SCHED_MAX_YIELD_NESTING);
415 break;
416 }
417 }
418
419 state->deepest_nesting = deepest;
420 state->total_observed = total_observed;
421
422 wake_report_failure(state);
423 return NIGHTMARE_OK;
424}
425
426/* Min completed waits per sleeper before nesting guard is exercised */
427#define WAKE_STORM_VACUITY_MIN_PER_SLEEPER 8
428
429static struct nightmare_verdict wake_storm_finish(struct nightmare_ctx *ctx) {
430 struct wake_storm_state *state = wake_state(ctx);
431
432 /* Invariants that never had a chance to fail have not passed...
433 * thread_prepare_to_sleep() will exit if a wake already matched,
434 * and thread_yield_until_wake_match() returns without yielding at all
435 * afterwards, so we never measure a yield, thus, we use aggregates here
436 */
437 bool cut_short =
438 atomic_load_explicit(&state->starvation_claimed, memory_order_acquire);
439 uint64_t floor =
440 (uint64_t) state->sleeper_count * WAKE_STORM_VACUITY_MIN_PER_SLEEPER;
441
442 if (!cut_short && state->deepest_nesting == 0 &&
443 state->total_observed >= floor)
444 wake_record_failure(state, WAKE_LANE_HARNESS, SIZE_MAX,
445 state->total_observed, 0);
446
447 wake_report_failure(state);
448 return NIGHTMARE_OK;
449}
450
451static struct nightmare_verdict wake_storm_prepare(struct nightmare_ctx *ctx) {
452 /* Worker 0 is the waker, and a lone worker has no one to wake,
453 * so we just guard against this */
454 if (ctx->worker_count < 2)
455 return NIGHTMARE_FAIL("worker_count",
456 "wake_storm needs a waker and a sleeper");
457
458 size_t sleeper_count = ctx->worker_count - 1;
459 if (sleeper_count > (SIZE_MAX - sizeof(struct wake_storm_state)) /
460 sizeof(struct wake_storm_sleeper))
461 return NIGHTMARE_FAIL("state_size", "sleeper state size overflow");
462
463 size_t bytes = sizeof(struct wake_storm_state) +
464 sleeper_count * sizeof(struct wake_storm_sleeper);
465 struct wake_storm_state *state = kmalloc(bytes, ALLOC_FLAGS_ZERO);
466 if (!state)
467 return NIGHTMARE_FAIL("state_alloc", "could not allocate wake state");
468
469 mutex_init_chk(&state->mtx, LOCK_CHK_CLASS(wake_storm_mtx), LOCK_CHKD_FULL);
470 rwlock_init_chk(&state->rw, THREAD_PRIO_CLASS_TIMESHARE,
471 LOCK_CHK_CLASS(wake_storm_rw), LOCK_CHKD_FULL);
472 qspinlock_init_chk(&state->qspin, LOCK_CHK_CLASS(wake_storm_qspin),
473 LOCK_CHKD_FULL);
474
475 state->sleeper_count = sleeper_count;
476 state->sleeper_stall_ms =
477 wake_storm_options.sleeper_stall_ms
478 ? NS_TO_MS(wake_storm_options.sleeper_stall_ms)
479 : WAKE_STORM_DEFAULT_SLEEPER_STALL_MS;
480
481 time_ms_t now = time_get_ms();
482 for (size_t i = 0; i < sleeper_count; i++)
483 state->sleepers[i].last_change_ms = now;
484
485 ctx->private = state;
486 return NIGHTMARE_OK;
487}
488
489static const struct nightmare_ops wake_storm_ops = {
490 .prepare = wake_storm_prepare,
491 .worker = wake_storm_worker,
492 .quiesce_check = wake_storm_quiesce_check,
493 .probe = wake_storm_probe,
494 .finish = wake_storm_finish,
495};
496
497NIGHTMARE_DECLARE(
498 wake_storm,
499 .desc = "Wake/sleep handoff under lock, APC and migration pressure",
500 .ops = &wake_storm_ops, .seed_policy = NIGHTMARE_SEED_IGNORED,
501 .requires = NIGHTMARE_REQ_SMP,
502 /* Workers per core */
503 NIGHTMARE_INTENSITY_CORES(1, 2, 4, "workers/core"),
504 .default_duration_ms = 60000);
505
506#endif /* TEST_NIGHTMARE_WAKE */
507