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_DEFINE(
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 size_t worker_count;
140 struct locks_storm_worker_state workers[] cc_counted_by(worker_count);
141};
142
143LOCK_CHK_CLASS_DEFINE_LOCAL(locks_storm_mutex);
144LOCK_CHK_CLASS_DEFINE_LOCAL(locks_storm_mutex_simple);
145LOCK_CHK_CLASS_DEFINE_LOCAL(locks_storm_rw);
146LOCK_CHK_CLASS_DEFINE_LOCAL(locks_storm_spin);
147LOCK_CHK_CLASS_DEFINE_LOCAL(locks_storm_qspin);
148LOCK_CHK_CLASS_DEFINE_LOCAL(locks_storm_seq);
149
150static struct locks_storm_state *locks_state(struct nightmare_ctx *ctx) {
151 return ctx->private;
152}
153
154static const char *locks_op_name(enum locks_storm_op op) {
155 switch (op) {
156 case LOCKS_OP_IDLE: return "idle";
157 case LOCKS_OP_MUTEX: return "mutex";
158 case LOCKS_OP_MUTEX_SIMPLE: return "mutex_simple";
159 case LOCKS_OP_RW_READ: return "rw_read";
160 case LOCKS_OP_RW_WRITE: return "rw_write";
161 case LOCKS_OP_SPIN: return "spin";
162 case LOCKS_OP_QSPIN: return "qspin";
163 case LOCKS_OP_SEQ_READ: return "seq_read";
164 case LOCKS_OP_SEQ_WRITE: return "seq_write";
165 case LOCKS_OP_NESTED: return "nested";
166 case LOCKS_OP_COUNT: return "invalid";
167 }
168 return "unknown";
169}
170
171static const char *locks_lane_name(enum locks_storm_lane lane) {
172 switch (lane) {
173 case LOCKS_LANE_WORKER: return "worker";
174 case LOCKS_LANE_MUTEX: return "mutex";
175 case LOCKS_LANE_MUTEX_SIMPLE: return "mutex_simple";
176 case LOCKS_LANE_RW: return "rw";
177 case LOCKS_LANE_SPIN: return "spin";
178 case LOCKS_LANE_QSPIN: return "qspin";
179 case LOCKS_LANE_SEQ: return "seq";
180 }
181 return "unknown";
182}
183
184static void locks_pair_init(struct locks_storm_pair *pair) {
185 atomic_store_rlx(&pair->value, 0);
186 atomic_store_rlx(&pair->complement, UINT64_MAX);
187}
188
189static bool locks_pair_load(const struct locks_storm_pair *pair,
190 uint64_t *value, uint64_t *complement) {
191 *value = atomic_load_rlx(&pair->value);
192 *complement = atomic_load_rlx(&pair->complement);
193 return *complement == ~*value;
194}
195
196static void locks_pair_advance(struct locks_storm_pair *pair, uint64_t value) {
197 value++;
198 atomic_store_rlx(&pair->value, value);
199 atomic_store_rlx(&pair->complement, ~value);
200}
201
202static bool locks_record_failure(struct locks_storm_state *state,
203 enum locks_storm_lane lane,
204 enum locks_storm_check check,
205 enum locks_storm_op op, size_t worker,
206 uint64_t observed_a, uint64_t observed_b) {
207 enum locks_storm_failure_phase expected = LOCKS_FAILURE_EMPTY;
208 if (!atomic_cas_strong(&state->failure.phase, &expected,
209 LOCKS_FAILURE_WRITING, mo_acq_rel, mo_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_release(&state->failure.phase, LOCKS_FAILURE_READY);
219 return true;
220}
221
222static void locks_report_failure(struct locks_storm_state *state) {
223 enum locks_storm_failure_phase expected = LOCKS_FAILURE_READY;
224 if (!atomic_cas_strong(&state->failure.phase, &expected,
225 LOCKS_FAILURE_REPORTED, mo_acq_rel, mo_acquire))
226 return;
227
228 uint64_t discriminator =
229 ((uint64_t) state->failure.lane << 8) | (uint64_t) state->failure.check;
230 NIGHTMARE_FINDING_TIER(
231 "lock_invariant", NIGHTMARE_TIER_CONFIDENT, discriminator,
232 "lane=%s op=%s check=%u worker=%lu observed_a=%lu observed_b=%lu",
233 locks_lane_name(state->failure.lane), locks_op_name(state->failure.op),
234 (unsigned int) state->failure.check,
235 (unsigned long) state->failure.worker,
236 (unsigned long) state->failure.observed_a,
237 (unsigned long) state->failure.observed_b);
238 nightmare_stop_after_finding();
239}
240
241static bool locks_enter_exclusive(struct locks_storm_state *state,
242 atomic_uint32_t *holders,
243 enum locks_storm_lane lane,
244 enum locks_storm_op op, size_t worker) {
245 uint32_t prior = atomic_fetch_add_acq_rel(holders, 1);
246 if (prior == 0)
247 return true;
248 locks_record_failure(state, lane, check: LOCKS_CHECK_EXCLUSIVE, op, worker, observed_a: prior,
249 observed_b: prior + 1);
250 return false;
251}
252
253static void locks_leave_exclusive(atomic_uint32_t *holders) {
254 atomic_dec_acq_rel(holders);
255}
256
257static bool locks_check_and_advance(struct locks_storm_state *state,
258 struct locks_storm_pair *pair,
259 enum locks_storm_lane lane,
260 enum locks_storm_op op, size_t worker) {
261 uint64_t value;
262 uint64_t complement;
263 if (!locks_pair_load(pair, value: &value, complement: &complement)) {
264 locks_record_failure(state, lane, check: LOCKS_CHECK_PAIR, op, worker, observed_a: value,
265 observed_b: complement);
266 return false;
267 }
268 locks_pair_advance(pair, value);
269 return true;
270}
271
272static bool locks_check_pair(struct locks_storm_state *state,
273 struct locks_storm_pair *pair,
274 enum locks_storm_lane lane, enum locks_storm_op op,
275 size_t worker) {
276 uint64_t value;
277 uint64_t complement;
278 if (locks_pair_load(pair, value: &value, complement: &complement))
279 return true;
280 locks_record_failure(state, lane, check: LOCKS_CHECK_PAIR, op, worker, observed_a: value,
281 observed_b: complement);
282 return false;
283}
284
285static bool locks_should_inject(struct locks_storm_state *state) {
286 if (state->corrupt_after_ops == 0 ||
287 atomic_load_acq(&state->corruption_injected))
288 return false;
289 return atomic_load_acq(&state->total_completed) >= state->corrupt_after_ops;
290}
291
292static enum locks_storm_op_result
293locks_run_mutex(struct locks_storm_state *state, size_t worker) {
294 enum locks_storm_op_result result = LOCKS_OP_COMPLETED;
295 mutex_lock(&state->mutex);
296
297 bool valid = locks_enter_exclusive(
298 state, holders: &state->mutex_holders, lane: LOCKS_LANE_MUTEX, op: LOCKS_OP_MUTEX, worker);
299 uint64_t value;
300 uint64_t complement;
301 if (!locks_pair_load(pair: &state->mutex_pair, value: &value, complement: &complement)) {
302 locks_record_failure(state, lane: LOCKS_LANE_MUTEX, check: LOCKS_CHECK_PAIR,
303 op: LOCKS_OP_MUTEX, worker, observed_a: value, observed_b: complement);
304 valid = false;
305 }
306
307 if (valid && locks_should_inject(state)) {
308 bool expected = false;
309 if (atomic_cas_strong(&state->corruption_injected, &expected, true,
310 mo_acq_rel, mo_acquire)) {
311 atomic_store_rlx(&state->mutex_pair.complement,
312 complement ^ UINT64_C(1));
313 result = LOCKS_OP_INJECTED;
314 }
315 }
316
317 if (valid && result == LOCKS_OP_COMPLETED)
318 locks_pair_advance(pair: &state->mutex_pair, value);
319 else if (!valid)
320 result = LOCKS_OP_FAILED;
321
322 locks_leave_exclusive(holders: &state->mutex_holders);
323 mutex_unlock(&state->mutex);
324 return result;
325}
326
327static enum locks_storm_op_result
328locks_run_mutex_simple(struct locks_storm_state *state, size_t worker) {
329 mutex_simple_lock(&state->mutex_simple);
330 bool valid = locks_enter_exclusive(state, holders: &state->mutex_simple_holders,
331 lane: LOCKS_LANE_MUTEX_SIMPLE,
332 op: LOCKS_OP_MUTEX_SIMPLE, worker);
333 if (!locks_check_and_advance(state, pair: &state->mutex_simple_pair,
334 lane: LOCKS_LANE_MUTEX_SIMPLE, op: LOCKS_OP_MUTEX_SIMPLE,
335 worker))
336 valid = false;
337 locks_leave_exclusive(holders: &state->mutex_simple_holders);
338 mutex_simple_unlock(&state->mutex_simple);
339 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
340}
341
342static enum locks_storm_op_result
343locks_run_rw_read(struct locks_storm_state *state, size_t worker) {
344 rw_lock(&state->rwlock, RWLOCK_READ);
345 uint32_t prior = atomic_fetch_add_acq_rel(&state->rw_occupancy, 1);
346 bool valid = (prior & LOCKS_STORM_RW_WRITER_BIT) == 0;
347 if (!valid)
348 locks_record_failure(state, lane: LOCKS_LANE_RW, check: LOCKS_CHECK_RW_READ,
349 op: LOCKS_OP_RW_READ, worker, observed_a: prior, observed_b: prior + 1);
350 if (!locks_check_pair(state, pair: &state->rw_pair, lane: LOCKS_LANE_RW,
351 op: LOCKS_OP_RW_READ, worker))
352 valid = false;
353 atomic_dec_acq_rel(&state->rw_occupancy);
354 rw_unlock(&state->rwlock);
355 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
356}
357
358static enum locks_storm_op_result
359locks_run_rw_write(struct locks_storm_state *state, size_t worker) {
360 rw_lock(&state->rwlock, RWLOCK_WRITE);
361 uint32_t prior = atomic_fetch_or_acq_rel(&state->rw_occupancy,
362 LOCKS_STORM_RW_WRITER_BIT);
363 bool valid = prior == 0;
364 if (!valid)
365 locks_record_failure(state, lane: LOCKS_LANE_RW, check: LOCKS_CHECK_RW_WRITE,
366 op: LOCKS_OP_RW_WRITE, worker, observed_a: prior,
367 LOCKS_STORM_RW_WRITER_BIT);
368 if (!locks_check_and_advance(state, pair: &state->rw_pair, lane: LOCKS_LANE_RW,
369 op: LOCKS_OP_RW_WRITE, worker))
370 valid = false;
371 atomic_fetch_and_acq_rel(&state->rw_occupancy, ~LOCKS_STORM_RW_WRITER_BIT);
372 rw_unlock(&state->rwlock);
373 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
374}
375
376static enum locks_storm_op_result
377locks_run_spin(struct locks_storm_state *state,
378 struct test_conc_worker *worker) {
379 enum irql old;
380 if ((test_rng_next(rng: &worker->rng) & 3) == 0) {
381 if (!spin_trylock(&state->spin, &old))
382 return LOCKS_OP_RETRY;
383 } else {
384 old = spin_lock(&state->spin);
385 }
386
387 bool valid =
388 locks_enter_exclusive(state, holders: &state->spin_holders, lane: LOCKS_LANE_SPIN,
389 op: LOCKS_OP_SPIN, worker: worker->index);
390 if (!locks_check_and_advance(state, pair: &state->spin_pair, lane: LOCKS_LANE_SPIN,
391 op: LOCKS_OP_SPIN, worker: worker->index))
392 valid = false;
393 locks_leave_exclusive(holders: &state->spin_holders);
394 spin_unlock(&state->spin, old);
395 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
396}
397
398static enum locks_storm_op_result
399locks_run_qspin(struct locks_storm_state *state,
400 struct test_conc_worker *worker) {
401 enum irql old;
402 if ((test_rng_next(rng: &worker->rng) & 3) == 0) {
403 if (!qspin_trylock(&state->qspin, &old))
404 return LOCKS_OP_RETRY;
405 } else {
406 old = qspin_lock(&state->qspin);
407 }
408
409 bool valid =
410 locks_enter_exclusive(state, holders: &state->qspin_holders, lane: LOCKS_LANE_QSPIN,
411 op: LOCKS_OP_QSPIN, worker: worker->index);
412 if (!locks_check_and_advance(state, pair: &state->qspin_pair, lane: LOCKS_LANE_QSPIN,
413 op: LOCKS_OP_QSPIN, worker: worker->index))
414 valid = false;
415 locks_leave_exclusive(holders: &state->qspin_holders);
416 qspin_unlock(&state->qspin, old);
417 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
418}
419
420static enum locks_storm_op_result
421locks_run_seq_read(struct locks_storm_state *state, size_t worker) {
422 uint64_t value;
423 uint64_t complement;
424 uint32_t sequence;
425 do {
426 sequence = seq_begin_read(sl: &state->seqlock);
427 value = atomic_load_rlx(&state->seq_pair.value);
428 complement = atomic_load_rlx(&state->seq_pair.complement);
429 } while (seq_read_retry(sl: &state->seqlock, start: sequence));
430
431 if (complement == ~value)
432 return LOCKS_OP_COMPLETED;
433 locks_record_failure(state, lane: LOCKS_LANE_SEQ, check: LOCKS_CHECK_PAIR,
434 op: LOCKS_OP_SEQ_READ, worker, observed_a: value, observed_b: complement);
435 return LOCKS_OP_FAILED;
436}
437
438static enum locks_storm_op_result
439locks_run_seq_write(struct locks_storm_state *state, size_t worker) {
440 enum irql old = seq_write_lock(sl: &state->seqlock);
441 bool valid = locks_check_and_advance(
442 state, pair: &state->seq_pair, lane: LOCKS_LANE_SEQ, op: LOCKS_OP_SEQ_WRITE, worker);
443 seq_write_unlock(sl: &state->seqlock, old);
444 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
445}
446
447static enum locks_storm_op_result
448locks_run_nested(struct locks_storm_state *state, size_t worker) {
449 bool valid = true;
450 mutex_lock(&state->mutex);
451 if (!locks_enter_exclusive(state, holders: &state->mutex_holders, lane: LOCKS_LANE_MUTEX,
452 op: LOCKS_OP_NESTED, worker))
453 valid = false;
454
455 rw_lock(&state->rwlock, RWLOCK_WRITE);
456 uint32_t rw_prior = atomic_fetch_or_acq_rel(&state->rw_occupancy,
457 LOCKS_STORM_RW_WRITER_BIT);
458 if (rw_prior != 0) {
459 locks_record_failure(state, lane: LOCKS_LANE_RW, check: LOCKS_CHECK_RW_WRITE,
460 op: LOCKS_OP_NESTED, worker, observed_a: rw_prior,
461 LOCKS_STORM_RW_WRITER_BIT);
462 valid = false;
463 }
464
465 enum irql old = spin_lock(&state->spin);
466 if (!locks_enter_exclusive(state, holders: &state->spin_holders, lane: LOCKS_LANE_SPIN,
467 op: LOCKS_OP_NESTED, worker))
468 valid = false;
469
470 if (!locks_check_and_advance(state, pair: &state->mutex_pair, lane: LOCKS_LANE_MUTEX,
471 op: LOCKS_OP_NESTED, worker) ||
472 !locks_check_and_advance(state, pair: &state->rw_pair, lane: LOCKS_LANE_RW,
473 op: LOCKS_OP_NESTED, worker) ||
474 !locks_check_and_advance(state, pair: &state->spin_pair, lane: LOCKS_LANE_SPIN,
475 op: LOCKS_OP_NESTED, worker))
476 valid = false;
477
478 locks_leave_exclusive(holders: &state->spin_holders);
479 spin_unlock(&state->spin, old);
480 atomic_fetch_and_acq_rel(&state->rw_occupancy, ~LOCKS_STORM_RW_WRITER_BIT);
481 rw_unlock(&state->rwlock);
482 locks_leave_exclusive(holders: &state->mutex_holders);
483 mutex_unlock(&state->mutex);
484 return valid ? LOCKS_OP_COMPLETED : LOCKS_OP_FAILED;
485}
486
487static enum locks_storm_op_result
488locks_run_operation(struct locks_storm_state *state,
489 struct test_conc_worker *worker, enum locks_storm_op op) {
490 switch (op) {
491 case LOCKS_OP_MUTEX: return locks_run_mutex(state, worker: worker->index);
492 case LOCKS_OP_MUTEX_SIMPLE:
493 return locks_run_mutex_simple(state, worker: worker->index);
494 case LOCKS_OP_RW_READ: return locks_run_rw_read(state, worker: worker->index);
495 case LOCKS_OP_RW_WRITE: return locks_run_rw_write(state, worker: worker->index);
496 case LOCKS_OP_SPIN: return locks_run_spin(state, worker);
497 case LOCKS_OP_QSPIN: return locks_run_qspin(state, worker);
498 case LOCKS_OP_SEQ_READ: return locks_run_seq_read(state, worker: worker->index);
499 case LOCKS_OP_SEQ_WRITE: return locks_run_seq_write(state, worker: worker->index);
500 case LOCKS_OP_NESTED: return locks_run_nested(state, worker: worker->index);
501 case LOCKS_OP_IDLE:
502 case LOCKS_OP_COUNT: break;
503 }
504 return LOCKS_OP_RETRY;
505}
506
507static enum locks_storm_op
508locks_choose_operation(struct locks_storm_state *state,
509 struct test_conc_worker *worker) {
510 if (locks_should_inject(state) ||
511 (atomic_load_acq(&state->corruption_injected) &&
512 atomic_load_acq(&state->failure.phase) == LOCKS_FAILURE_EMPTY))
513 return LOCKS_OP_MUTEX;
514 return (enum locks_storm_op)(1 + test_rng_next(rng: &worker->rng) %
515 (LOCKS_OP_COUNT - 1));
516}
517
518static void locks_storm_starve(struct locks_storm_state *state,
519 struct test_conc_worker *worker) {
520 struct locks_storm_worker_state *worker_state =
521 &state->workers[worker->index];
522 atomic_store_release(&worker_state->current_op, LOCKS_OP_MUTEX);
523 while (!nightmare_must_stop())
524 scheduler_yield();
525 atomic_store_release(&worker_state->current_op, LOCKS_OP_IDLE);
526}
527
528NIGHTMARE_WORKER(locks_storm_worker) {
529 struct locks_storm_state *state = locks_state(ctx: NM_CTX);
530 struct locks_storm_worker_state *worker_state =
531 &state->workers[NM_SELF->index];
532
533 if (locks_storm_options.starve_one && NM_SELF->index == 0) {
534 locks_storm_starve(state, worker: NM_SELF);
535 return;
536 }
537
538 while (!nightmare_must_stop()) {
539 if (nightmare_must_park()) {
540 if (locks_storm_options.park_delay_ms)
541 thread_sleep_for_ms(
542 NS_TO_MS(locks_storm_options.park_delay_ms));
543 nightmare_park(worker: NM_SELF);
544 if (nightmare_must_stop())
545 break;
546 }
547
548 enum locks_storm_op op = locks_choose_operation(state, worker: NM_SELF);
549 atomic_store_release(&worker_state->current_op, op);
550 enum locks_storm_op_result result =
551 locks_run_operation(state, worker: NM_SELF, op);
552 atomic_store_release(&worker_state->current_op, LOCKS_OP_IDLE);
553
554 if (result == LOCKS_OP_FAILED) {
555 locks_report_failure(state);
556 return;
557 }
558 if (result == LOCKS_OP_INJECTED)
559 continue;
560 if (result == LOCKS_OP_RETRY) {
561 scheduler_yield();
562 continue;
563 }
564
565 atomic_inc_release(&worker_state->completed);
566 atomic_inc_rlx(&state->total_completed);
567 NIGHTMARE_PROGRESS();
568
569 if (test_rng_next(rng: &NM_SELF->rng) & 1)
570 scheduler_yield();
571 }
572}
573
574static void locks_probe_rebaseline(struct nightmare_ctx *ctx,
575 struct locks_storm_state *state,
576 time_ms_t now) {
577 for (size_t i = 0; i < ctx->worker_count; i++) {
578 struct locks_storm_worker_state *worker = &state->workers[i];
579 worker->sampled_completed = atomic_load_acq(&worker->completed);
580 worker->last_change_ms = now;
581 }
582}
583
584static void locks_storm_probe(struct nightmare_ctx *ctx) {
585 if (nightmare_must_stop())
586 return;
587
588 struct locks_storm_state *state = locks_state(ctx);
589 time_ms_t now = time_get_ms();
590 if (nightmare_must_park()) {
591 locks_probe_rebaseline(ctx, state, now);
592 state->probe_was_quiesced = true;
593 return;
594 }
595 if (state->probe_was_quiesced) {
596 locks_probe_rebaseline(ctx, state, now);
597 state->probe_was_quiesced = false;
598 return;
599 }
600
601 for (size_t i = 0; i < ctx->worker_count; i++) {
602 struct locks_storm_worker_state *worker = &state->workers[i];
603 uint64_t completed = atomic_load_acq(&worker->completed);
604 if (completed != worker->sampled_completed) {
605 worker->sampled_completed = completed;
606 worker->last_change_ms = now;
607 continue;
608 }
609 if (now - worker->last_change_ms < state->worker_stall_ms)
610 continue;
611
612 bool expected = false;
613 if (!atomic_cas_strong(&state->starvation_claimed, &expected, true,
614 mo_acq_rel, mo_acquire))
615 return;
616
617 enum locks_storm_op op = atomic_load_acq(&worker->current_op);
618 NIGHTMARE_FINDING_TIER(
619 "worker_starvation", NIGHTMARE_TIER_AMBIGUOUS, (uint64_t) op,
620 "worker=%lu op=%s completed=%lu silent_ms=%lu", (unsigned long) i,
621 locks_op_name(op), (unsigned long) completed,
622 (unsigned long) (now - worker->last_change_ms));
623 nightmare_stop_after_finding();
624 return;
625 }
626}
627
628static void locks_quiescent_failure(struct locks_storm_state *state,
629 enum locks_storm_lane lane,
630 uint64_t observed_a, uint64_t observed_b) {
631 locks_record_failure(state, lane, check: LOCKS_CHECK_QUIESCENT, op: LOCKS_OP_IDLE,
632 SIZE_MAX, observed_a, observed_b);
633}
634
635static struct nightmare_verdict
636locks_storm_quiesce_check(struct nightmare_ctx *ctx) {
637 struct locks_storm_state *state = locks_state(ctx);
638
639 for (size_t i = 0; i < ctx->worker_count; i++) {
640 enum locks_storm_op op = atomic_load_acq(&state->workers[i].current_op);
641 if (op != LOCKS_OP_IDLE) {
642 locks_quiescent_failure(state, lane: LOCKS_LANE_WORKER, observed_a: i, observed_b: op);
643 break;
644 }
645 }
646
647 uint32_t occupancy = atomic_load_acq(&state->rw_occupancy);
648 if (occupancy != 0)
649 locks_quiescent_failure(state, lane: LOCKS_LANE_RW, observed_a: occupancy, observed_b: 0);
650
651 struct {
652 enum locks_storm_lane lane;
653 atomic_uint32_t *holders;
654 } holder_lanes[] = {
655 {LOCKS_LANE_MUTEX, &state->mutex_holders},
656 {LOCKS_LANE_MUTEX_SIMPLE, &state->mutex_simple_holders},
657 {LOCKS_LANE_SPIN, &state->spin_holders},
658 {LOCKS_LANE_QSPIN, &state->qspin_holders},
659 };
660 for (size_t i = 0; i < sizeof(holder_lanes) / sizeof(holder_lanes[0]);
661 i++) {
662 uint32_t holders = atomic_load_acq(holder_lanes[i].holders);
663 if (holders != 0) {
664 locks_quiescent_failure(state, lane: holder_lanes[i].lane, observed_a: holders, observed_b: 0);
665 break;
666 }
667 }
668
669 struct {
670 enum locks_storm_lane lane;
671 struct locks_storm_pair *pair;
672 } pair_lanes[] = {
673 {LOCKS_LANE_MUTEX, &state->mutex_pair},
674 {LOCKS_LANE_MUTEX_SIMPLE, &state->mutex_simple_pair},
675 {LOCKS_LANE_RW, &state->rw_pair},
676 {LOCKS_LANE_SPIN, &state->spin_pair},
677 {LOCKS_LANE_QSPIN, &state->qspin_pair},
678 {LOCKS_LANE_SEQ, &state->seq_pair},
679 };
680 for (size_t i = 0; i < sizeof(pair_lanes) / sizeof(pair_lanes[0]); i++) {
681 uint64_t value;
682 uint64_t complement;
683 if (!locks_pair_load(pair: pair_lanes[i].pair, value: &value, complement: &complement)) {
684 locks_quiescent_failure(state, lane: pair_lanes[i].lane, observed_a: value,
685 observed_b: complement);
686 break;
687 }
688 }
689
690 locks_report_failure(state);
691 return NIGHTMARE_OK;
692}
693
694static struct nightmare_verdict locks_storm_finish(struct nightmare_ctx *ctx) {
695 cc_ignore(ctx);
696 return NIGHTMARE_OK;
697}
698
699static struct nightmare_verdict locks_storm_prepare(struct nightmare_ctx *ctx) {
700 if (ctx->worker_count > (SIZE_MAX - sizeof(struct locks_storm_state)) /
701 sizeof(struct locks_storm_worker_state))
702 return NIGHTMARE_FAIL("state_size", "worker state size overflow");
703
704 size_t bytes = sizeof(struct locks_storm_state) +
705 ctx->worker_count * sizeof(struct locks_storm_worker_state);
706 struct locks_storm_state *state = valloc(bytes, ALLOC_ZERO);
707 if (!state)
708 return NIGHTMARE_FAIL("state_alloc", "could not allocate lock state");
709 state->worker_count = ctx->worker_count; /* before any workers[] access */
710
711 mutex_init_chk(&state->mutex, LOCK_CHK_CLASS(locks_storm_mutex),
712 LOCK_CHKD_FULL);
713 mutex_simple_init_chk(&state->mutex_simple,
714 LOCK_CHK_CLASS(locks_storm_mutex_simple),
715 LOCK_CHKD_FULL);
716 rwlock_init_chk(&state->rwlock, THREAD_PRIO_CLASS_TIMESHARE,
717 LOCK_CHK_CLASS(locks_storm_rw), LOCK_CHKD_FULL);
718 spinlock_init_chk(&state->spin, LOCK_CHK_CLASS(locks_storm_spin),
719 LOCK_CHKD_FULL);
720 qspinlock_init_chk(&state->qspin, LOCK_CHK_CLASS(locks_storm_qspin),
721 LOCK_CHKD_FULL);
722 seqlock_init_chk(&state->seqlock, LOCK_CHK_CLASS(locks_storm_seq),
723 LOCK_CHKD_FULL);
724
725 locks_pair_init(pair: &state->mutex_pair);
726 locks_pair_init(pair: &state->mutex_simple_pair);
727 locks_pair_init(pair: &state->rw_pair);
728 locks_pair_init(pair: &state->spin_pair);
729 locks_pair_init(pair: &state->qspin_pair);
730 locks_pair_init(pair: &state->seq_pair);
731
732 state->corrupt_after_ops = locks_storm_options.corrupt_after_ops;
733 state->worker_stall_ms = locks_storm_options.worker_stall_ms
734 ? NS_TO_MS(locks_storm_options.worker_stall_ms)
735 : LOCKS_STORM_DEFAULT_WORKER_STALL_MS;
736 time_ms_t now = time_get_ms();
737 for (size_t i = 0; i < ctx->worker_count; i++)
738 state->workers[i].last_change_ms = now;
739
740 ctx->private = state;
741 return NIGHTMARE_OK;
742}
743
744static const struct nightmare_ops locks_storm_ops = {
745 .prepare = locks_storm_prepare,
746 .worker = locks_storm_worker,
747 .quiesce_check = locks_storm_quiesce_check,
748 .probe = locks_storm_probe,
749 .finish = locks_storm_finish,
750};
751
752NIGHTMARE_DEFINE(
753 locks_storm,
754 .desc = "Mixed lock contention with independent invariant checking",
755 .ops = &locks_storm_ops, .seed_policy = NIGHTMARE_SEED_IGNORED,
756 .requires = NIGHTMARE_REQ_SMP,
757 NIGHTMARE_INTENSITY_CORES(1, 4, 8, "workers"),
758 .default_duration_ms = 60000);
759
760#endif /* TEST_NIGHTMARE_LOCKS */
761