1#include <asm.h>
2#include <math/range.h>
3#include <mem/alloc.h>
4#include <nightmare/nightmare.h>
5#include <sch/sched.h>
6#include <sync/lock_chk.h>
7#include <sync/mutex.h>
8#include <sync/mutex_simple.h>
9#include <sync/qspinlock.h>
10#include <sync/rwlock.h>
11#include <sync/seqlock.h>
12#include <sync/spinlock.h>
13#include <thread/thread.h>
14#include <time/time.h>
15
16#define LOCKS_STORM_DEFAULT_WORKER_STALL_MS 10000
17#define LOCKS_STORM_RW_WRITER_BIT (UINT32_C(1) << 31)
18
19struct locks_storm_options {
20 time_ns_t worker_stall_ms;
21 time_ns_t park_delay_ms;
22 uint64_t corrupt_after_ops;
23 bool starve_one;
24};
25
26static struct locks_storm_options locks_storm_options;
27
28NIGHTMARE_OPTIONS_DECLARE(
29 locks_storm, struct locks_storm_options, locks_storm_options,
30 CMDLINE_SCHEMA_PROP(struct locks_storm_options, worker_stall_ms,
31 .types = CMDLINE_TYPES(CMDLINE_TYPE_DURATION),
32 .range = RANGE(MS_TO_NS(100), TIME_NS_MAX)),
33 CMDLINE_SCHEMA_PROP(struct locks_storm_options, park_delay_ms,
34 .types = CMDLINE_TYPES(CMDLINE_TYPE_DURATION),
35 .range = RANGE(MS_TO_NS(1), TIME_NS_MAX)),
36 CMDLINE_SCHEMA_PROP(struct locks_storm_options, corrupt_after_ops),
37 CMDLINE_SCHEMA_PROP(struct locks_storm_options, starve_one));
38
39#ifdef TEST_NIGHTMARE_LOCKS
40
41enum locks_storm_op : uint8_t {
42 LOCKS_OP_IDLE = 0,
43 LOCKS_OP_MUTEX,
44 LOCKS_OP_MUTEX_SIMPLE,
45 LOCKS_OP_RW_READ,
46 LOCKS_OP_RW_WRITE,
47 LOCKS_OP_SPIN,
48 LOCKS_OP_QSPIN,
49 LOCKS_OP_SEQ_READ,
50 LOCKS_OP_SEQ_WRITE,
51 LOCKS_OP_NESTED,
52 LOCKS_OP_COUNT,
53};
54
55enum locks_storm_check : uint8_t {
56 LOCKS_CHECK_PAIR = 1,
57 LOCKS_CHECK_EXCLUSIVE,
58 LOCKS_CHECK_RW_READ,
59 LOCKS_CHECK_RW_WRITE,
60 LOCKS_CHECK_QUIESCENT,
61};
62
63enum locks_storm_lane : uint8_t {
64 LOCKS_LANE_WORKER = 1,
65 LOCKS_LANE_MUTEX,
66 LOCKS_LANE_MUTEX_SIMPLE,
67 LOCKS_LANE_RW,
68 LOCKS_LANE_SPIN,
69 LOCKS_LANE_QSPIN,
70 LOCKS_LANE_SEQ,
71};
72
73enum locks_storm_failure_phase : uint8_t {
74 LOCKS_FAILURE_EMPTY = 0,
75 LOCKS_FAILURE_WRITING,
76 LOCKS_FAILURE_READY,
77 LOCKS_FAILURE_REPORTED,
78};
79
80enum locks_storm_op_result : uint8_t {
81 LOCKS_OP_COMPLETED = 0,
82 LOCKS_OP_RETRY,
83 LOCKS_OP_FAILED,
84 LOCKS_OP_INJECTED,
85};
86
87struct locks_storm_worker_state {
88 _Atomic uint64_t completed;
89 _Atomic enum locks_storm_op current_op;
90 uint64_t sampled_completed;
91 time_ms_t last_change_ms;
92};
93
94struct locks_storm_pair {
95 _Atomic uint64_t value;
96 _Atomic uint64_t complement;
97};
98
99struct locks_storm_failure {
100 _Atomic enum locks_storm_failure_phase phase;
101 enum locks_storm_lane lane;
102 enum locks_storm_check check;
103 enum locks_storm_op op;
104 size_t worker;
105 uint64_t observed_a;
106 uint64_t observed_b;
107};
108
109struct locks_storm_state {
110 struct mutex mutex;
111 struct mutex_simple mutex_simple;
112 struct rwlock rwlock;
113 struct spinlock spin;
114 struct qspinlock qspin;
115 struct seqlock seqlock;
116
117 struct locks_storm_pair mutex_pair;
118 struct locks_storm_pair mutex_simple_pair;
119 struct locks_storm_pair rw_pair;
120 struct locks_storm_pair spin_pair;
121 struct locks_storm_pair qspin_pair;
122 struct locks_storm_pair seq_pair;
123
124 _Atomic uint32_t mutex_holders;
125 _Atomic uint32_t mutex_simple_holders;
126 _Atomic uint32_t rw_occupancy;
127 _Atomic uint32_t spin_holders;
128 _Atomic uint32_t qspin_holders;
129
130 _Atomic uint64_t total_completed;
131 struct locks_storm_failure failure;
132 atomic_bool starvation_claimed;
133 atomic_bool corruption_injected;
134 bool probe_was_quiesced;
135
136 uint64_t corrupt_after_ops;
137 time_ms_t worker_stall_ms;
138
139 struct locks_storm_worker_state workers[];
140};
141
142LOCK_CHK_CLASS_DECLARE_LOCAL(locks_storm_mutex);
143LOCK_CHK_CLASS_DECLARE_LOCAL(locks_storm_mutex_simple);
144LOCK_CHK_CLASS_DECLARE_LOCAL(locks_storm_rw);
145LOCK_CHK_CLASS_DECLARE_LOCAL(locks_storm_spin);
146LOCK_CHK_CLASS_DECLARE_LOCAL(locks_storm_qspin);
147LOCK_CHK_CLASS_DECLARE_LOCAL(locks_storm_seq);
148
149static struct locks_storm_state *locks_state(struct nightmare_ctx *ctx) {
150 return ctx->private;
151}
152
153static const char *locks_op_name(enum locks_storm_op op) {
154 switch (op) {
155 case LOCKS_OP_IDLE: return "idle";
156 case LOCKS_OP_MUTEX: return "mutex";
157 case LOCKS_OP_MUTEX_SIMPLE: return "mutex_simple";
158 case LOCKS_OP_RW_READ: return "rw_read";
159 case LOCKS_OP_RW_WRITE: return "rw_write";
160 case LOCKS_OP_SPIN: return "spin";
161 case LOCKS_OP_QSPIN: return "qspin";
162 case LOCKS_OP_SEQ_READ: return "seq_read";
163 case LOCKS_OP_SEQ_WRITE: return "seq_write";
164 case LOCKS_OP_NESTED: return "nested";
165 case LOCKS_OP_COUNT: return "invalid";
166 }
167 return "unknown";
168}
169
170static const char *locks_lane_name(enum locks_storm_lane lane) {
171 switch (lane) {
172 case LOCKS_LANE_WORKER: return "worker";
173 case LOCKS_LANE_MUTEX: return "mutex";
174 case LOCKS_LANE_MUTEX_SIMPLE: return "mutex_simple";
175 case LOCKS_LANE_RW: return "rw";
176 case LOCKS_LANE_SPIN: return "spin";
177 case LOCKS_LANE_QSPIN: return "qspin";
178 case LOCKS_LANE_SEQ: return "seq";
179 }
180 return "unknown";
181}
182
183static void locks_pair_init(struct locks_storm_pair *pair) {
184 atomic_store_explicit(&pair->value, 0, memory_order_relaxed);
185 atomic_store_explicit(&pair->complement, UINT64_MAX, memory_order_relaxed);
186}
187
188static bool locks_pair_load(const struct locks_storm_pair *pair,
189 uint64_t *value, uint64_t *complement) {
190 *value = atomic_load_explicit(&pair->value, memory_order_relaxed);
191 *complement = atomic_load_explicit(&pair->complement, memory_order_relaxed);
192 return *complement == ~*value;
193}
194
195static void locks_pair_advance(struct locks_storm_pair *pair, uint64_t value) {
196 value++;
197 atomic_store_explicit(&pair->value, value, memory_order_relaxed);
198 atomic_store_explicit(&pair->complement, ~value, memory_order_relaxed);
199}
200
201static bool locks_record_failure(struct locks_storm_state *state,
202 enum locks_storm_lane lane,
203 enum locks_storm_check check,
204 enum locks_storm_op op, size_t worker,
205 uint64_t observed_a, uint64_t observed_b) {
206 enum locks_storm_failure_phase expected = LOCKS_FAILURE_EMPTY;
207 if (!atomic_compare_exchange_strong_explicit(
208 &state->failure.phase, &expected, LOCKS_FAILURE_WRITING,
209 memory_order_acq_rel, memory_order_acquire))
210 return false;
211
212 state->failure.lane = lane;
213 state->failure.check = check;
214 state->failure.op = op;
215 state->failure.worker = worker;
216 state->failure.observed_a = observed_a;
217 state->failure.observed_b = observed_b;
218 atomic_store_explicit(&state->failure.phase, LOCKS_FAILURE_READY,
219 memory_order_release);
220 return true;
221}
222
223static void locks_report_failure(struct locks_storm_state *state) {
224 enum locks_storm_failure_phase expected = LOCKS_FAILURE_READY;
225 if (!atomic_compare_exchange_strong_explicit(
226 &state->failure.phase, &expected, LOCKS_FAILURE_REPORTED,
227 memory_order_acq_rel, memory_order_acquire))
228 return;
229
230 uint64_t discriminator =
231 ((uint64_t) state->failure.lane << 8) | (uint64_t) state->failure.check;
232 NIGHTMARE_FINDING_TIER(
233 "lock_invariant", NIGHTMARE_TIER_CONFIDENT, discriminator,
234 "lane=%s op=%s check=%u worker=%lu observed_a=%lu observed_b=%lu",
235 locks_lane_name(state->failure.lane), locks_op_name(state->failure.op),
236 (unsigned int) state->failure.check,
237 (unsigned long) state->failure.worker,
238 (unsigned long) state->failure.observed_a,
239 (unsigned long) state->failure.observed_b);
240 nightmare_stop_after_finding();
241}
242
243static bool locks_enter_exclusive(struct locks_storm_state *state,
244 _Atomic uint32_t *holders,
245 enum locks_storm_lane lane,
246 enum locks_storm_op op, size_t worker) {
247 uint32_t prior =
248 atomic_fetch_add_explicit(holders, 1, memory_order_acq_rel);
249 if (prior == 0)
250 return true;
251 locks_record_failure(state, lane, check: LOCKS_CHECK_EXCLUSIVE, op, worker, observed_a: prior,
252 observed_b: prior + 1);
253 return false;
254}
255
256static void locks_leave_exclusive(_Atomic uint32_t *holders) {
257 atomic_fetch_sub_explicit(holders, 1, memory_order_acq_rel);
258}
259
260static bool locks_check_and_advance(struct locks_storm_state *state,
261 struct locks_storm_pair *pair,
262 enum locks_storm_lane lane,
263 enum locks_storm_op op, size_t worker) {
264 uint64_t value;
265 uint64_t complement;
266 if (!locks_pair_load(pair, value: &value, complement: &complement)) {
267 locks_record_failure(state, lane, check: LOCKS_CHECK_PAIR, op, worker, observed_a: value,
268 observed_b: complement);
269 return false;
270 }
271 locks_pair_advance(pair, value);
272 return true;
273}
274
275static bool locks_check_pair(struct locks_storm_state *state,
276 struct locks_storm_pair *pair,
277 enum locks_storm_lane lane, enum locks_storm_op op,
278 size_t worker) {
279 uint64_t value;
280 uint64_t complement;
281 if (locks_pair_load(pair, value: &value, complement: &complement))
282 return true;
283 locks_record_failure(state, lane, check: LOCKS_CHECK_PAIR, op, worker, observed_a: value,
284 observed_b: complement);
285 return false;
286}
287
288static bool locks_should_inject(struct locks_storm_state *state) {
289 if (state->corrupt_after_ops == 0 ||
290 atomic_load_explicit(&state->corruption_injected, memory_order_acquire))
291 return false;
292 return atomic_load_explicit(&state->total_completed,
293 memory_order_acquire) >=
294 state->corrupt_after_ops;
295}
296
297static enum locks_storm_op_result
298locks_run_mutex(struct locks_storm_state *state, size_t worker) {
299 enum locks_storm_op_result result = LOCKS_OP_COMPLETED;
300 mutex_lock(&state->mutex);
301
302 bool valid = locks_enter_exclusive(
303 state, holders: &state->mutex_holders, lane: LOCKS_LANE_MUTEX, op: LOCKS_OP_MUTEX, worker);
304 uint64_t value;
305 uint64_t complement;
306 if (!locks_pair_load(pair: &state->mutex_pair, value: &value, complement: &complement)) {
307 locks_record_failure(state, lane: LOCKS_LANE_MUTEX, check: LOCKS_CHECK_PAIR,
308 op: LOCKS_OP_MUTEX, worker, observed_a: value, observed_b: complement);
309 valid = false;
310 }
311
312 if (valid && locks_should_inject(state)) {
313 bool expected = false;
314 if (atomic_compare_exchange_strong_explicit(
315 &state->corruption_injected, &expected, true,
316 memory_order_acq_rel, memory_order_acquire)) {
317 atomic_store_explicit(&state->mutex_pair.complement,
318 complement ^ UINT64_C(1),
319 memory_order_relaxed);
320 result = LOCKS_OP_INJECTED;
321 }
322 }
323
324 if (valid && result == LOCKS_OP_COMPLETED)
325 locks_pair_advance(pair: &state->mutex_pair, value);
326 else if (!valid)
327 result = LOCKS_OP_FAILED;
328
329 locks_leave_exclusive(holders: &state->mutex_holders);
330 mutex_unlock(&state->mutex);
331 return result;
332}
333
334static enum locks_storm_op_result
335locks_run_mutex_simple(struct locks_storm_state *state, size_t worker) {
336 mutex_simple_lock(&state->mutex_simple);
337 bool valid = locks_enter_exclusive(state, holders: &state->mutex_simple_holders,
338 lane: LOCKS_LANE_MUTEX_SIMPLE,
339 op: LOCKS_OP_MUTEX_SIMPLE, worker);
340 if (!locks_check_and_advance(state, pair: &state->mutex_simple_pair,
341 lane: LOCKS_LANE_MUTEX_SIMPLE, op: LOCKS_OP_MUTEX_SIMPLE,
342 worker))
343 valid = false;
344 locks_leave_exclusive(holders: &state->mutex_simple_holders);
345 mutex_simple_unlock(&state->mutex_simple);
346 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
347}
348
349static enum locks_storm_op_result
350locks_run_rw_read(struct locks_storm_state *state, size_t worker) {
351 rw_lock(&state->rwlock, RWLOCK_ACQUIRE_READ);
352 uint32_t prior = atomic_fetch_add_explicit(&state->rw_occupancy, 1,
353 memory_order_acq_rel);
354 bool valid = (prior & LOCKS_STORM_RW_WRITER_BIT) == 0;
355 if (!valid)
356 locks_record_failure(state, lane: LOCKS_LANE_RW, check: LOCKS_CHECK_RW_READ,
357 op: LOCKS_OP_RW_READ, worker, observed_a: prior, observed_b: prior + 1);
358 if (!locks_check_pair(state, pair: &state->rw_pair, lane: LOCKS_LANE_RW,
359 op: LOCKS_OP_RW_READ, worker))
360 valid = false;
361 atomic_fetch_sub_explicit(&state->rw_occupancy, 1, memory_order_acq_rel);
362 rw_unlock(&state->rwlock);
363 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
364}
365
366static enum locks_storm_op_result
367locks_run_rw_write(struct locks_storm_state *state, size_t worker) {
368 rw_lock(&state->rwlock, RWLOCK_ACQUIRE_WRITE);
369 uint32_t prior = atomic_fetch_or_explicit(
370 &state->rw_occupancy, LOCKS_STORM_RW_WRITER_BIT, memory_order_acq_rel);
371 bool valid = prior == 0;
372 if (!valid)
373 locks_record_failure(state, lane: LOCKS_LANE_RW, check: LOCKS_CHECK_RW_WRITE,
374 op: LOCKS_OP_RW_WRITE, worker, observed_a: prior,
375 LOCKS_STORM_RW_WRITER_BIT);
376 if (!locks_check_and_advance(state, pair: &state->rw_pair, lane: LOCKS_LANE_RW,
377 op: LOCKS_OP_RW_WRITE, worker))
378 valid = false;
379 atomic_fetch_and_explicit(&state->rw_occupancy, ~LOCKS_STORM_RW_WRITER_BIT,
380 memory_order_acq_rel);
381 rw_unlock(&state->rwlock);
382 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
383}
384
385static enum locks_storm_op_result
386locks_run_spin(struct locks_storm_state *state,
387 struct nightmare_worker *worker) {
388 enum irql old;
389 if ((nightmare_rand(rng: &worker->rng) & 3) == 0) {
390 if (!spin_trylock(&state->spin, &old))
391 return LOCKS_OP_RETRY;
392 } else {
393 old = spin_lock(&state->spin);
394 }
395
396 bool valid =
397 locks_enter_exclusive(state, holders: &state->spin_holders, lane: LOCKS_LANE_SPIN,
398 op: LOCKS_OP_SPIN, worker: worker->index);
399 if (!locks_check_and_advance(state, pair: &state->spin_pair, lane: LOCKS_LANE_SPIN,
400 op: LOCKS_OP_SPIN, worker: worker->index))
401 valid = false;
402 locks_leave_exclusive(holders: &state->spin_holders);
403 spin_unlock(&state->spin, old);
404 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
405}
406
407static enum locks_storm_op_result
408locks_run_qspin(struct locks_storm_state *state,
409 struct nightmare_worker *worker) {
410 enum irql old;
411 if ((nightmare_rand(rng: &worker->rng) & 3) == 0) {
412 if (!qspin_trylock(&state->qspin, &old))
413 return LOCKS_OP_RETRY;
414 } else {
415 old = qspin_lock(&state->qspin);
416 }
417
418 bool valid =
419 locks_enter_exclusive(state, holders: &state->qspin_holders, lane: LOCKS_LANE_QSPIN,
420 op: LOCKS_OP_QSPIN, worker: worker->index);
421 if (!locks_check_and_advance(state, pair: &state->qspin_pair, lane: LOCKS_LANE_QSPIN,
422 op: LOCKS_OP_QSPIN, worker: worker->index))
423 valid = false;
424 locks_leave_exclusive(holders: &state->qspin_holders);
425 qspin_unlock(&state->qspin, old);
426 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
427}
428
429static enum locks_storm_op_result
430locks_run_seq_read(struct locks_storm_state *state, size_t worker) {
431 uint64_t value;
432 uint64_t complement;
433 uint32_t sequence;
434 do {
435 sequence = seq_begin_read(sl: &state->seqlock);
436 value =
437 atomic_load_explicit(&state->seq_pair.value, memory_order_relaxed);
438 complement = atomic_load_explicit(&state->seq_pair.complement,
439 memory_order_relaxed);
440 } while (seq_read_retry(sl: &state->seqlock, start: sequence));
441
442 if (complement == ~value)
443 return LOCKS_OP_COMPLETED;
444 locks_record_failure(state, lane: LOCKS_LANE_SEQ, check: LOCKS_CHECK_PAIR,
445 op: LOCKS_OP_SEQ_READ, worker, observed_a: value, observed_b: complement);
446 return LOCKS_OP_FAILED;
447}
448
449static enum locks_storm_op_result
450locks_run_seq_write(struct locks_storm_state *state, size_t worker) {
451 enum irql old = seq_write_lock(sl: &state->seqlock);
452 bool valid = locks_check_and_advance(
453 state, pair: &state->seq_pair, lane: LOCKS_LANE_SEQ, op: LOCKS_OP_SEQ_WRITE, worker);
454 seq_write_unlock(sl: &state->seqlock, old);
455 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
456}
457
458static enum locks_storm_op_result
459locks_run_nested(struct locks_storm_state *state, size_t worker) {
460 bool valid = true;
461 mutex_lock(&state->mutex);
462 if (!locks_enter_exclusive(state, holders: &state->mutex_holders, lane: LOCKS_LANE_MUTEX,
463 op: LOCKS_OP_NESTED, worker))
464 valid = false;
465
466 rw_lock(&state->rwlock, RWLOCK_ACQUIRE_WRITE);
467 uint32_t rw_prior = atomic_fetch_or_explicit(
468 &state->rw_occupancy, LOCKS_STORM_RW_WRITER_BIT, memory_order_acq_rel);
469 if (rw_prior != 0) {
470 locks_record_failure(state, lane: LOCKS_LANE_RW, check: LOCKS_CHECK_RW_WRITE,
471 op: LOCKS_OP_NESTED, worker, observed_a: rw_prior,
472 LOCKS_STORM_RW_WRITER_BIT);
473 valid = false;
474 }
475
476 enum irql old = spin_lock(&state->spin);
477 if (!locks_enter_exclusive(state, holders: &state->spin_holders, lane: LOCKS_LANE_SPIN,
478 op: LOCKS_OP_NESTED, worker))
479 valid = false;
480
481 if (!locks_check_and_advance(state, pair: &state->mutex_pair, lane: LOCKS_LANE_MUTEX,
482 op: LOCKS_OP_NESTED, worker) ||
483 !locks_check_and_advance(state, pair: &state->rw_pair, lane: LOCKS_LANE_RW,
484 op: LOCKS_OP_NESTED, worker) ||
485 !locks_check_and_advance(state, pair: &state->spin_pair, lane: LOCKS_LANE_SPIN,
486 op: LOCKS_OP_NESTED, worker))
487 valid = false;
488
489 locks_leave_exclusive(holders: &state->spin_holders);
490 spin_unlock(&state->spin, old);
491 atomic_fetch_and_explicit(&state->rw_occupancy, ~LOCKS_STORM_RW_WRITER_BIT,
492 memory_order_acq_rel);
493 rw_unlock(&state->rwlock);
494 locks_leave_exclusive(holders: &state->mutex_holders);
495 mutex_unlock(&state->mutex);
496 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
497}
498
499static enum locks_storm_op_result
500locks_run_operation(struct locks_storm_state *state,
501 struct nightmare_worker *worker, enum locks_storm_op op) {
502 switch (op) {
503 case LOCKS_OP_MUTEX: return locks_run_mutex(state, worker: worker->index);
504 case LOCKS_OP_MUTEX_SIMPLE:
505 return locks_run_mutex_simple(state, worker: worker->index);
506 case LOCKS_OP_RW_READ: return locks_run_rw_read(state, worker: worker->index);
507 case LOCKS_OP_RW_WRITE: return locks_run_rw_write(state, worker: worker->index);
508 case LOCKS_OP_SPIN: return locks_run_spin(state, worker);
509 case LOCKS_OP_QSPIN: return locks_run_qspin(state, worker);
510 case LOCKS_OP_SEQ_READ: return locks_run_seq_read(state, worker: worker->index);
511 case LOCKS_OP_SEQ_WRITE: return locks_run_seq_write(state, worker: worker->index);
512 case LOCKS_OP_NESTED: return locks_run_nested(state, worker: worker->index);
513 case LOCKS_OP_IDLE:
514 case LOCKS_OP_COUNT: break;
515 }
516 return LOCKS_OP_RETRY;
517}
518
519static enum locks_storm_op
520locks_choose_operation(struct locks_storm_state *state,
521 struct nightmare_worker *worker) {
522 if (locks_should_inject(state) ||
523 (atomic_load_explicit(&state->corruption_injected,
524 memory_order_acquire) &&
525 atomic_load_explicit(&state->failure.phase, memory_order_acquire) ==
526 LOCKS_FAILURE_EMPTY))
527 return LOCKS_OP_MUTEX;
528 return (enum locks_storm_op)(1 + nightmare_rand(rng: &worker->rng) %
529 (LOCKS_OP_COUNT - 1));
530}
531
532static void locks_storm_starve(struct locks_storm_state *state,
533 struct nightmare_worker *worker) {
534 struct locks_storm_worker_state *worker_state =
535 &state->workers[worker->index];
536 atomic_store_explicit(&worker_state->current_op, LOCKS_OP_MUTEX,
537 memory_order_release);
538 while (!nightmare_must_stop())
539 scheduler_yield();
540 atomic_store_explicit(&worker_state->current_op, LOCKS_OP_IDLE,
541 memory_order_release);
542}
543
544NIGHTMARE_WORKER(locks_storm_worker) {
545 struct locks_storm_state *state = locks_state(ctx: NM_CTX);
546 struct locks_storm_worker_state *worker_state =
547 &state->workers[NM_SELF->index];
548
549 if (locks_storm_options.starve_one && NM_SELF->index == 0) {
550 locks_storm_starve(state, worker: NM_SELF);
551 return;
552 }
553
554 while (!nightmare_must_stop()) {
555 if (nightmare_must_park()) {
556 if (locks_storm_options.park_delay_ms)
557 thread_sleep_for_ms(
558 NS_TO_MS(locks_storm_options.park_delay_ms));
559 nightmare_park(worker: NM_SELF);
560 if (nightmare_must_stop())
561 break;
562 }
563
564 enum locks_storm_op op = locks_choose_operation(state, worker: NM_SELF);
565 atomic_store_explicit(&worker_state->current_op, op,
566 memory_order_release);
567 enum locks_storm_op_result result =
568 locks_run_operation(state, worker: NM_SELF, op);
569 atomic_store_explicit(&worker_state->current_op, LOCKS_OP_IDLE,
570 memory_order_release);
571
572 if (result == LOCKS_OP_FAILED) {
573 locks_report_failure(state);
574 return;
575 }
576 if (result == LOCKS_OP_INJECTED)
577 continue;
578 if (result == LOCKS_OP_RETRY) {
579 scheduler_yield();
580 continue;
581 }
582
583 atomic_fetch_add_explicit(&worker_state->completed, 1,
584 memory_order_release);
585 atomic_fetch_add_explicit(&state->total_completed, 1,
586 memory_order_relaxed);
587 NIGHTMARE_PROGRESS();
588
589 if (nightmare_rand(rng: &NM_SELF->rng) & 1)
590 scheduler_yield();
591 }
592}
593
594static void locks_probe_rebaseline(struct nightmare_ctx *ctx,
595 struct locks_storm_state *state,
596 time_ms_t now) {
597 for (size_t i = 0; i < ctx->worker_count; i++) {
598 struct locks_storm_worker_state *worker = &state->workers[i];
599 worker->sampled_completed =
600 atomic_load_explicit(&worker->completed, memory_order_acquire);
601 worker->last_change_ms = now;
602 }
603}
604
605static void locks_storm_probe(struct nightmare_ctx *ctx) {
606 if (nightmare_must_stop())
607 return;
608
609 struct locks_storm_state *state = locks_state(ctx);
610 time_ms_t now = time_get_ms();
611 if (nightmare_must_park()) {
612 locks_probe_rebaseline(ctx, state, now);
613 state->probe_was_quiesced = true;
614 return;
615 }
616 if (state->probe_was_quiesced) {
617 locks_probe_rebaseline(ctx, state, now);
618 state->probe_was_quiesced = false;
619 return;
620 }
621
622 for (size_t i = 0; i < ctx->worker_count; i++) {
623 struct locks_storm_worker_state *worker = &state->workers[i];
624 uint64_t completed =
625 atomic_load_explicit(&worker->completed, memory_order_acquire);
626 if (completed != worker->sampled_completed) {
627 worker->sampled_completed = completed;
628 worker->last_change_ms = now;
629 continue;
630 }
631 if (now - worker->last_change_ms < state->worker_stall_ms)
632 continue;
633
634 bool expected = false;
635 if (!atomic_compare_exchange_strong_explicit(
636 &state->starvation_claimed, &expected, true,
637 memory_order_acq_rel, memory_order_acquire))
638 return;
639
640 enum locks_storm_op op =
641 atomic_load_explicit(&worker->current_op, memory_order_acquire);
642 NIGHTMARE_FINDING_TIER(
643 "worker_starvation", NIGHTMARE_TIER_AMBIGUOUS, (uint64_t) op,
644 "worker=%lu op=%s completed=%lu silent_ms=%lu", (unsigned long) i,
645 locks_op_name(op), (unsigned long) completed,
646 (unsigned long) (now - worker->last_change_ms));
647 nightmare_stop_after_finding();
648 return;
649 }
650}
651
652static void locks_quiescent_failure(struct locks_storm_state *state,
653 enum locks_storm_lane lane,
654 uint64_t observed_a, uint64_t observed_b) {
655 locks_record_failure(state, lane, check: LOCKS_CHECK_QUIESCENT, op: LOCKS_OP_IDLE,
656 SIZE_MAX, observed_a, observed_b);
657}
658
659static struct nightmare_verdict
660locks_storm_quiesce_check(struct nightmare_ctx *ctx) {
661 struct locks_storm_state *state = locks_state(ctx);
662
663 for (size_t i = 0; i < ctx->worker_count; i++) {
664 enum locks_storm_op op = atomic_load_explicit(
665 &state->workers[i].current_op, memory_order_acquire);
666 if (op != LOCKS_OP_IDLE) {
667 locks_quiescent_failure(state, lane: LOCKS_LANE_WORKER, observed_a: i, observed_b: op);
668 break;
669 }
670 }
671
672 uint32_t occupancy =
673 atomic_load_explicit(&state->rw_occupancy, memory_order_acquire);
674 if (occupancy != 0)
675 locks_quiescent_failure(state, lane: LOCKS_LANE_RW, observed_a: occupancy, observed_b: 0);
676
677 struct {
678 enum locks_storm_lane lane;
679 _Atomic uint32_t *holders;
680 } holder_lanes[] = {
681 {LOCKS_LANE_MUTEX, &state->mutex_holders},
682 {LOCKS_LANE_MUTEX_SIMPLE, &state->mutex_simple_holders},
683 {LOCKS_LANE_SPIN, &state->spin_holders},
684 {LOCKS_LANE_QSPIN, &state->qspin_holders},
685 };
686 for (size_t i = 0; i < sizeof(holder_lanes) / sizeof(holder_lanes[0]);
687 i++) {
688 uint32_t holders =
689 atomic_load_explicit(holder_lanes[i].holders, memory_order_acquire);
690 if (holders != 0) {
691 locks_quiescent_failure(state, lane: holder_lanes[i].lane, observed_a: holders, observed_b: 0);
692 break;
693 }
694 }
695
696 struct {
697 enum locks_storm_lane lane;
698 struct locks_storm_pair *pair;
699 } pair_lanes[] = {
700 {LOCKS_LANE_MUTEX, &state->mutex_pair},
701 {LOCKS_LANE_MUTEX_SIMPLE, &state->mutex_simple_pair},
702 {LOCKS_LANE_RW, &state->rw_pair},
703 {LOCKS_LANE_SPIN, &state->spin_pair},
704 {LOCKS_LANE_QSPIN, &state->qspin_pair},
705 {LOCKS_LANE_SEQ, &state->seq_pair},
706 };
707 for (size_t i = 0; i < sizeof(pair_lanes) / sizeof(pair_lanes[0]); i++) {
708 uint64_t value;
709 uint64_t complement;
710 if (!locks_pair_load(pair: pair_lanes[i].pair, value: &value, complement: &complement)) {
711 locks_quiescent_failure(state, lane: pair_lanes[i].lane, observed_a: value,
712 observed_b: complement);
713 break;
714 }
715 }
716
717 locks_report_failure(state);
718 return NIGHTMARE_OK;
719}
720
721static struct nightmare_verdict locks_storm_finish(struct nightmare_ctx *ctx) {
722 (void) ctx;
723 return NIGHTMARE_OK;
724}
725
726static struct nightmare_verdict locks_storm_prepare(struct nightmare_ctx *ctx) {
727 if (ctx->worker_count > (SIZE_MAX - sizeof(struct locks_storm_state)) /
728 sizeof(struct locks_storm_worker_state))
729 return NIGHTMARE_FAIL("state_size", "worker state size overflow");
730
731 size_t bytes = sizeof(struct locks_storm_state) +
732 ctx->worker_count * sizeof(struct locks_storm_worker_state);
733 struct locks_storm_state *state = kmalloc(bytes, ALLOC_FLAGS_ZERO);
734 if (!state)
735 return NIGHTMARE_FAIL("state_alloc", "could not allocate lock state");
736
737 mutex_init_chk(&state->mutex, LOCK_CHK_CLASS(locks_storm_mutex),
738 LOCK_CHKD_FULL);
739 mutex_simple_init_chk(&state->mutex_simple,
740 LOCK_CHK_CLASS(locks_storm_mutex_simple),
741 LOCK_CHKD_FULL);
742 rwlock_init_chk(&state->rwlock, THREAD_PRIO_CLASS_TIMESHARE,
743 LOCK_CHK_CLASS(locks_storm_rw), LOCK_CHKD_FULL);
744 spinlock_init_chk(&state->spin, LOCK_CHK_CLASS(locks_storm_spin),
745 LOCK_CHKD_FULL);
746 qspinlock_init_chk(&state->qspin, LOCK_CHK_CLASS(locks_storm_qspin),
747 LOCK_CHKD_FULL);
748 seqlock_init_chk(&state->seqlock, LOCK_CHK_CLASS(locks_storm_seq),
749 LOCK_CHKD_FULL);
750
751 locks_pair_init(pair: &state->mutex_pair);
752 locks_pair_init(pair: &state->mutex_simple_pair);
753 locks_pair_init(pair: &state->rw_pair);
754 locks_pair_init(pair: &state->spin_pair);
755 locks_pair_init(pair: &state->qspin_pair);
756 locks_pair_init(pair: &state->seq_pair);
757
758 state->corrupt_after_ops = locks_storm_options.corrupt_after_ops;
759 state->worker_stall_ms = locks_storm_options.worker_stall_ms
760 ? NS_TO_MS(locks_storm_options.worker_stall_ms)
761 : LOCKS_STORM_DEFAULT_WORKER_STALL_MS;
762 time_ms_t now = time_get_ms();
763 for (size_t i = 0; i < ctx->worker_count; i++)
764 state->workers[i].last_change_ms = now;
765
766 ctx->private = state;
767 return NIGHTMARE_OK;
768}
769
770static const struct nightmare_ops locks_storm_ops = {
771 .prepare = locks_storm_prepare,
772 .worker = locks_storm_worker,
773 .quiesce_check = locks_storm_quiesce_check,
774 .probe = locks_storm_probe,
775 .finish = locks_storm_finish,
776};
777
778NIGHTMARE_DECLARE(
779 locks_storm,
780 .desc = "Mixed lock contention with independent invariant checking",
781 .ops = &locks_storm_ops, .seed_policy = NIGHTMARE_SEED_IGNORED,
782 .requires = NIGHTMARE_REQ_SMP,
783 NIGHTMARE_INTENSITY_CORES(1, 4, 8, "workers"),
784 .default_duration_ms = 60000);
785
786#endif /* TEST_NIGHTMARE_LOCKS */
787