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_DEFINE(
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 struct spinlock lock;
52 struct thread_wait_header wait;
53 bool permit;
54 atomic_uint64_t alerts;
55
56 atomic_uint64_t issued;
57 atomic_uint64_t observed;
58
59 /* For noticing sleepers that got stuck from the probe */
60 uint64_t sampled_observed;
61 time_ms_t last_change_ms;
62
63 uint32_t sampled_nesting_max;
64};
65
66struct wake_storm_failure {
67 atomic(enum wake_storm_failure_phase) phase;
68 enum wake_storm_lane lane;
69 size_t sleeper;
70 uint64_t observed_a;
71 uint64_t observed_b;
72
73 const char *file;
74 uint32_t line;
75};
76
77struct wake_storm_state {
78 struct mutex mtx;
79 struct rwlock rw;
80 struct qspinlock qspin;
81
82 atomic_uint64_t wakes_issued;
83 atomic_size_t registered;
84 atomic_bool starvation_claimed;
85 bool probe_was_quiesced;
86
87 struct wake_storm_failure failure;
88
89 time_ms_t sleeper_stall_ms;
90 size_t sleeper_count;
91
92 uint32_t deepest_nesting;
93 uint64_t total_observed;
94
95 struct wake_storm_sleeper sleepers[] cc_counted_by(sleeper_count);
96};
97
98LOCK_CHK_CLASS_DEFINE_LOCAL(wake_storm_mtx);
99LOCK_CHK_CLASS_DEFINE_LOCAL(wake_storm_rw);
100LOCK_CHK_CLASS_DEFINE_LOCAL(wake_storm_qspin);
101
102static struct wake_storm_state *wake_state(struct nightmare_ctx *ctx) {
103 return ctx->private;
104}
105
106static const char *wake_lane_name(enum wake_storm_lane lane) {
107 switch (lane) {
108 case WAKE_LANE_ACCOUNTING: return "accounting";
109 case WAKE_LANE_NESTING: return "nesting";
110 case WAKE_LANE_STARVATION: return "starvation";
111 case WAKE_LANE_HARNESS: return "harness";
112 }
113 return "unknown";
114}
115
116#define wake_record_failure(state_, lane_, sleeper_, a_, b_) \
117 wake_record_failure_at((state_), (lane_), (sleeper_), (a_), (b_), \
118 __RELFILE__, __LINE__)
119
120static bool wake_record_failure_at(struct wake_storm_state *state,
121 enum wake_storm_lane lane, size_t sleeper,
122 uint64_t observed_a, uint64_t observed_b,
123 const char *file, uint32_t line) {
124 enum wake_storm_failure_phase expected = WAKE_FAILURE_EMPTY;
125 if (!atomic_cas_strong(&state->failure.phase, &expected,
126 WAKE_FAILURE_WRITING, mo_acq_rel, mo_acquire))
127 return false;
128
129 state->failure.lane = lane;
130 state->failure.sleeper = sleeper;
131 state->failure.observed_a = observed_a;
132 state->failure.observed_b = observed_b;
133 state->failure.file = file;
134 state->failure.line = line;
135 atomic_store_release(&state->failure.phase, WAKE_FAILURE_READY);
136 return true;
137}
138
139static void wake_report_failure(struct wake_storm_state *state) {
140 enum wake_storm_failure_phase expected = WAKE_FAILURE_READY;
141 if (!atomic_cas_strong(&state->failure.phase, &expected,
142 WAKE_FAILURE_REPORTED, mo_acq_rel, mo_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 test_conc_worker *self) {
161 mutex_lock(&state->mtx);
162 for (volatile int i = 0; i < (int) (test_rng_next(rng: &self->rng) & 0xF); i++)
163 cpu_pause();
164 mutex_unlock(&state->mtx);
165
166 if (test_rng_next(rng: &self->rng) & 1) {
167 rw_lock(&state->rw, RWLOCK_READ);
168 for (volatile int i = 0; i < 4; i++)
169 cpu_pause();
170 rw_unlock(&state->rw);
171 } else {
172 rw_lock(&state->rw, RWLOCK_WRITE);
173 for (volatile int i = 0; i < 4; i++)
174 cpu_pause();
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_pause();
181 qspin_unlock(&state->qspin, irql);
182}
183
184static void wake_storm_sleeper_main(struct nightmare_ctx *ctx,
185 struct test_conc_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_release(&me->th, t);
192 atomic_inc_release(&state->registered);
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 enum irql irql = spin_lock_high(&me->lock);
203 bool object_completion = true;
204 if (!me->permit) {
205 thread_wait_prepare_to_sleep(header: &me->wait, object: me,
206 type: THREAD_WAIT_INTERRUPTIBLE);
207 spin_unlock(&me->lock, irql);
208
209 if (nightmare_must_stop() || nightmare_must_park())
210 thread_alert(thread: t);
211
212 struct thread_wait_result result = thread_wait_complete();
213 object_completion = result.status == THREAD_WAIT_SATISFIED;
214 irql = spin_lock_high(&me->lock);
215 }
216
217 if (object_completion)
218 me->permit = false;
219
220 spin_unlock(&me->lock, irql);
221
222 if (!object_completion)
223 atomic_inc_release(&me->alerts);
224
225 if (nightmare_must_stop())
226 break;
227
228 if (object_completion)
229 atomic_inc_release(&me->observed);
230 NIGHTMARE_PROGRESS();
231 }
232}
233
234static void wake_storm_signal(struct wake_storm_sleeper *sleeper,
235 bool counted) {
236 enum irql irql = spin_lock_high(&sleeper->lock);
237 if (counted)
238 atomic_inc_release(&sleeper->issued);
239
240 sleeper->permit = true;
241 thread_wait_header_satisfy(hdr: &sleeper->wait, reason: THREAD_WAKE_REASON_SLEEP_MANUAL,
242 NULL);
243
244 spin_unlock(&sleeper->lock, irql);
245}
246
247/* Wake up EVERYONE, which is used because otherwise the stutter perturber
248 * would time out waiting for subjects that cannot park because they're
249 * waiting for an object permit */
250static void wake_storm_release_all(struct wake_storm_state *state,
251 bool count_issued) {
252 for (size_t i = 0; i < state->sleeper_count; i++) {
253 struct thread *t = atomic_load_acq(&state->sleepers[i].th);
254 if (!t || !thread_getref(obj: t))
255 continue;
256 if (count_issued)
257 wake_storm_signal(sleeper: &state->sleepers[i], true);
258 else
259 thread_alert(thread: t);
260
261 thread_putref(t);
262 }
263}
264
265static void wake_storm_waker_main(struct nightmare_ctx *ctx,
266 struct test_conc_worker *self) {
267 struct wake_storm_state *state = wake_state(ctx);
268
269 while (!nightmare_must_stop()) {
270 if (nightmare_must_park()) {
271 wake_storm_release_all(state, /* count_issued = */ true);
272 nightmare_park(worker: self);
273 continue;
274 }
275
276 if (atomic_load_acq(&state->registered) == 0) {
277 scheduler_yield();
278 continue;
279 }
280
281 size_t slot = test_rng_next(rng: &self->rng) % state->sleeper_count;
282 struct wake_storm_sleeper *target = &state->sleepers[slot];
283 struct thread *t = atomic_load_acq(&target->th);
284 if (!t || !thread_getref(obj: t)) {
285 scheduler_yield();
286 continue;
287 }
288
289 uint64_t ops = atomic_fetch_add_rlx(&state->wakes_issued, 1);
290
291 /* Count a wake as issued but never actually issue it */
292 bool drop = wake_storm_options.drop_wake_after_ops &&
293 ops >= wake_storm_options.drop_wake_after_ops;
294
295 /* Deliver the wake without counting it */
296 bool uncounted = wake_storm_options.uncounted_wake_after_ops &&
297 ops >= wake_storm_options.uncounted_wake_after_ops;
298
299 if (drop) {
300 atomic_inc_release(&target->issued);
301 } else {
302 wake_storm_signal(sleeper: target, counted: !uncounted);
303 }
304
305 thread_putref(t);
306 scheduler_yield();
307 }
308
309 wake_storm_release_all(state, /* count_issued = */ false);
310}
311
312NIGHTMARE_WORKER(wake_storm_worker) {
313 if (NM_SELF->index == 0)
314 wake_storm_waker_main(ctx: NM_CTX, self: NM_SELF);
315 else
316 wake_storm_sleeper_main(ctx: NM_CTX, self: NM_SELF, slot: NM_SELF->index - 1);
317}
318
319static void wake_probe_rebaseline(struct wake_storm_state *state,
320 time_ms_t now) {
321 for (size_t i = 0; i < state->sleeper_count; i++) {
322 state->sleepers[i].sampled_observed =
323 atomic_load_acq(&state->sleepers[i].observed);
324 state->sleepers[i].last_change_ms = now;
325 }
326}
327
328/* A sleeper that stops advancing while wakers keep issuing to it
329 * are often lost wakes but scheduler starvation can cause that too */
330static void wake_storm_probe(struct nightmare_ctx *ctx) {
331 if (nightmare_must_stop())
332 return;
333
334 struct wake_storm_state *state = wake_state(ctx);
335 time_ms_t now = time_get_ms();
336
337 if (nightmare_must_park()) {
338 wake_probe_rebaseline(state, now);
339 state->probe_was_quiesced = true;
340 return;
341 }
342 if (state->probe_was_quiesced) {
343 wake_probe_rebaseline(state, now);
344 state->probe_was_quiesced = false;
345 return;
346 }
347
348 for (size_t i = 0; i < state->sleeper_count; i++) {
349 struct wake_storm_sleeper *sleeper = &state->sleepers[i];
350 if (!atomic_load_acq(&sleeper->th))
351 continue;
352
353 uint64_t observed = atomic_load_acq(&sleeper->observed);
354 if (observed != sleeper->sampled_observed) {
355 sleeper->sampled_observed = observed;
356 sleeper->last_change_ms = now;
357 continue;
358 }
359
360 if (now - sleeper->last_change_ms < state->sleeper_stall_ms)
361 continue;
362
363 bool expected = false;
364 if (!atomic_cas_strong(&state->starvation_claimed, &expected, true,
365 mo_acq_rel, mo_acquire))
366 return;
367
368 NIGHTMARE_FINDING_TIER(
369 "wake_starvation", NIGHTMARE_TIER_AMBIGUOUS, (uint64_t) i,
370 "sleeper=%lu issued=%lu observed=%lu silent_ms=%lu",
371 (unsigned long) i,
372 (unsigned long) atomic_load_acq(&sleeper->issued),
373 (unsigned long) observed,
374 (unsigned long) (now - sleeper->last_change_ms));
375 nightmare_stop_after_finding();
376 return;
377 }
378}
379
380static struct nightmare_verdict
381wake_storm_quiesce_check(struct nightmare_ctx *ctx) {
382 struct wake_storm_state *state = wake_state(ctx);
383
384 uint64_t total_observed = 0;
385 uint32_t deepest = 0;
386
387 for (size_t i = 0; i < state->sleeper_count; i++) {
388 struct wake_storm_sleeper *sleeper = &state->sleepers[i];
389 struct thread *t = atomic_load_acq(&sleeper->th);
390 if (!t)
391 continue;
392
393 /* `observed` can lag `issued`, never inverted
394 *
395 * Reading `observed` first prevents an inversion
396 */
397 uint64_t observed = atomic_load_acq(&sleeper->observed);
398 uint64_t issued = atomic_load_acq(&sleeper->issued);
399 total_observed += observed;
400 if (observed > issued) {
401 wake_record_failure(state, WAKE_LANE_ACCOUNTING, i, issued,
402 observed);
403 break;
404 }
405
406 uint32_t nesting = scheduler_yield_nesting_max(t);
407 if (nesting > deepest)
408 deepest = nesting;
409
410 if (nesting < sleeper->sampled_nesting_max)
411 sleeper->sampled_nesting_max = nesting;
412
413 if (nesting > SCHED_MAX_YIELD_NESTING &&
414 nesting > sleeper->sampled_nesting_max) {
415 sleeper->sampled_nesting_max = nesting;
416 wake_record_failure(state, WAKE_LANE_NESTING, i, nesting,
417 SCHED_MAX_YIELD_NESTING);
418 break;
419 }
420 }
421
422 state->deepest_nesting = deepest;
423 state->total_observed = total_observed;
424
425 wake_report_failure(state);
426 return NIGHTMARE_OK;
427}
428
429/* Min completed waits per sleeper before nesting guard is exercised */
430#define WAKE_STORM_VACUITY_MIN_PER_SLEEPER 8
431
432static struct nightmare_verdict wake_storm_finish(struct nightmare_ctx *ctx) {
433 struct wake_storm_state *state = wake_state(ctx);
434
435 /* Invariants that never had a chance to fail have not passed...
436 * Pending object permits or alerts can complete before yielding
437 */
438 bool cut_short = atomic_load_acq(&state->starvation_claimed);
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 = valloc(bytes, ALLOC_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 spinlock_init(&state->sleepers[i].lock);
485 thread_wait_header_init(header: &state->sleepers[i].wait);
486 }
487
488 ctx->private = state;
489 return NIGHTMARE_OK;
490}
491
492static const struct nightmare_ops wake_storm_ops = {
493 .prepare = wake_storm_prepare,
494 .worker = wake_storm_worker,
495 .quiesce_check = wake_storm_quiesce_check,
496 .probe = wake_storm_probe,
497 .finish = wake_storm_finish,
498};
499
500NIGHTMARE_DEFINE(
501 wake_storm,
502 .desc = "Wake/sleep handoff under lock, APC and migration pressure",
503 .ops = &wake_storm_ops, .seed_policy = NIGHTMARE_SEED_IGNORED,
504 .requires = NIGHTMARE_REQ_SMP,
505 /* Workers per core */
506 NIGHTMARE_INTENSITY_CORES(1, 2, 4, "workers/core"),
507 .default_duration_ms = 60000);
508
509#endif /* TEST_NIGHTMARE_WAKE */
510