1#include "tests/test_internal.h"
2
3static __noinline void sd_save_n(stack_handle_t *out, size_t n) {
4 for (size_t i = 0; i < n; i++)
5 out[i] = stack_depot_save_current();
6}
7
8#define SD_SEED 0xDEADBEEFULL
9#define SD_TRACE_LEN 8
10#define SD_MANY 4096 /* > STACK_DEPOT_HASH_SIZE, forces chain collisions */
11static_assert(SD_MANY > STACK_DEPOT_HASH_SIZE);
12
13static void sd_make_trace(uintptr_t *entries, size_t len, uint64_t id) {
14 for (size_t i = 0; i < len; i++)
15 entries[i] = (uintptr_t) (0xffffffff80000000ULL + (id << 20) + i * 16);
16}
17
18#define SD_MT_THREADS 8
19#define SD_MT_TIMEOUT_MS 30000
20
21struct sd_mt_state {
22 atomic_uint left;
23 atomic_bool stop;
24 atomic_bool fail;
25 atomic_bool oom;
26 const char *fail_msg;
27 uint64_t seed;
28
29 struct thread *threads[SD_MT_THREADS];
30 size_t nthreads;
31};
32
33static struct sd_mt_state sd_mt;
34
35static void sd_mt_reset(struct test_context *ctx, unsigned workers) {
36 atomic_store(&sd_mt.left, workers);
37 atomic_store(&sd_mt.stop, false);
38 atomic_store(&sd_mt.fail, false);
39 atomic_store(&sd_mt.oom, false);
40 sd_mt.fail_msg = NULL;
41 sd_mt.seed = ctx->seed;
42 memset(sd_mt.threads, 0, sizeof(sd_mt.threads));
43 sd_mt.nthreads = 0;
44}
45
46static void sd_mt_report(const char *msg) {
47 /* First failure wins; everyone else just stops. */
48 if (!atomic_exchange(&sd_mt.fail, true))
49 sd_mt.fail_msg = msg;
50 atomic_store(&sd_mt.stop, true);
51}
52
53static void sd_mt_report_oom(void) {
54 atomic_store(&sd_mt.oom, true);
55 atomic_store(&sd_mt.stop, true);
56}
57
58#define SD_WORKER_CHECK(x) \
59 do { \
60 if (!(x)) { \
61 sd_mt_report(#x " (worker, " __RELFILE__ ")"); \
62 return false; \
63 } \
64 } while (0)
65
66static inline uint64_t sd_rng(uint64_t *s) {
67 uint64_t x = *s;
68 x ^= x << 13;
69 x ^= x >> 7;
70 x ^= x << 17;
71 return (*s = x);
72}
73
74static inline uint64_t sd_rng_seed(size_t tid) {
75 return (sd_mt.seed ^ (0x9E3779B97F4A7C15ULL * (tid + 1))) | 1;
76}
77
78static size_t sd_chain_count(uintptr_t *trace, size_t len) {
79 struct stack_depot_record_chain *chain =
80 &stack_depot_global
81 .chains[stack_depot_hash(entries: trace, num_entries: len) % STACK_DEPOT_HASH_SIZE];
82 struct stack_depot_record *pos;
83 size_t n = 0;
84
85 enum irql irql = spin_lock(&chain->lock);
86 list_for_each_entry(pos, &chain->list,
87 hash_list) if (pos->num_entries == len &&
88 !memcmp(pos->entries, trace,
89 len * sizeof(uintptr_t))) n++;
90 spin_unlock(&chain->lock, irql);
91
92 return n;
93}
94
95static bool sd_mt_wait_for(atomic_uint *counter, unsigned target) {
96 time_ms_t deadline = time_get_ms() + SD_MT_TIMEOUT_MS;
97
98 while (atomic_load(counter) != target) {
99 if (time_get_ms() > deadline)
100 return false;
101 scheduler_yield();
102 }
103
104 return true;
105}
106
107static void sd_mt_abandon(void) {
108 atomic_store(&sd_mt.stop, true);
109
110 for (size_t i = 0; i < sd_mt.nthreads; i++) {
111 if (sd_mt.threads[i]) {
112 thread_detach(t: sd_mt.threads[i]);
113 sd_mt.threads[i] = NULL;
114 }
115 }
116}
117
118/* Join + fold verdict */
119static struct test_verdict sd_mt_join(void) {
120 time_ms_t deadline = time_get_ms() + SD_MT_TIMEOUT_MS;
121 bool timed_out = false;
122
123 for (size_t i = 0; i < sd_mt.nthreads; i++) {
124 struct thread *t = sd_mt.threads[i];
125 if (!t)
126 continue;
127
128 sd_mt.threads[i] = NULL;
129
130 time_ms_t now = time_get_ms();
131 time_ms_t left = now >= deadline ? 1 : deadline - now;
132
133 /* If it times out, we stop waiting on the rest too */
134 if (timed_out || !thread_join_timeout(t, timeout_ms: left, NULL)) {
135 atomic_store(&sd_mt.stop, true);
136 thread_detach(t);
137 timed_out = true;
138 }
139 }
140
141 if (timed_out)
142 return TEST_FAIL("workers did not finish in time");
143
144 if (atomic_load(&sd_mt.fail))
145 return TEST_FAIL(sd_mt.fail_msg);
146
147 if (atomic_load(&sd_mt.oom))
148 return TEST_SKIP(TEST_SKIP_RAM_LOW);
149
150 /* every worker ran to completion */
151 if (atomic_load(&sd_mt.left))
152 return TEST_FAIL("worker fleet did not spawn");
153
154 return TEST_SUCCESS;
155}
156
157#define SD_MT_JOIN() \
158 do { \
159 struct test_verdict _v = sd_mt_join(); \
160 if (_v.result != TEST_RESULT_OK) \
161 return _v; \
162 } while (0)
163
164static void sd_mt_spawn(char *name, void (*fn)(void *), size_t n) {
165 kassert(n <= SD_MT_THREADS);
166 sd_mt.nthreads = n;
167
168 /* Raise to spawn a bunch */
169 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
170 for (size_t i = 0; i < n; i++)
171 sd_mt.threads[i] =
172 thread_spawn_joinable(name, entry: fn, arg: (void *) (uintptr_t) i);
173 irql_lower(old_level: irql);
174}
175
176#define SD_MT_DEDUP_SAVES_MAX 256
177#define SD_MT_DEDUP_ID 0x3000
178
179static stack_handle_t sd_dedup_handles[SD_MT_THREADS];
180static atomic_uint sd_dedup_saved;
181static atomic_bool sd_dedup_release;
182static size_t sd_dedup_saves_count = 64;
183
184static bool sd_dedup_body(size_t tid, stack_handle_t *held, size_t *held_n) {
185 uintptr_t trace[SD_TRACE_LEN];
186 sd_make_trace(entries: trace, SD_TRACE_LEN, SD_MT_DEDUP_ID);
187
188 for (size_t i = 0; i < sd_dedup_saves_count; i++) {
189 stack_handle_t h =
190 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
191 if (!h) {
192 sd_mt_report_oom();
193 return false;
194 }
195
196 held[(*held_n)++] = h;
197 /* Every save of an identical trace must land on one record. */
198 SD_WORKER_CHECK(h == held[0]);
199 }
200
201 sd_dedup_handles[tid] = held[0];
202 return true;
203}
204
205static void sd_dedup_worker(void *arg) {
206 size_t tid = (size_t) (uintptr_t) arg;
207 stack_handle_t held[SD_MT_DEDUP_SAVES_MAX];
208 size_t held_n = 0;
209
210 sd_dedup_body(tid, held, held_n: &held_n);
211
212 /* Publish unconditionally since the main thread will be waiting */
213 atomic_fetch_add(&sd_dedup_saved, 1);
214
215 while (!atomic_load(&sd_dedup_release))
216 scheduler_yield();
217
218 for (size_t i = 0; i < held_n; i++)
219 stack_depot_put(key: held[i]);
220
221 atomic_fetch_sub(&sd_mt.left, 1);
222}
223
224TEST_DECLARE_INTEGRATION(stack_depot, mt_dedup, TEST_INTENSITY(16, 64, 256)) {
225 uintptr_t trace[SD_TRACE_LEN];
226 sd_make_trace(entries: trace, SD_TRACE_LEN, SD_MT_DEDUP_ID);
227 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
228
229 sd_dedup_saves_count = ctx->intensity_val ? ctx->intensity_val : 64;
230 if (sd_dedup_saves_count > SD_MT_DEDUP_SAVES_MAX)
231 sd_dedup_saves_count = SD_MT_DEDUP_SAVES_MAX;
232
233 sd_mt_reset(ctx, SD_MT_THREADS);
234 atomic_store(&sd_dedup_saved, 0);
235 atomic_store(&sd_dedup_release, false);
236 memset(sd_dedup_handles, 0, sizeof(sd_dedup_handles));
237
238 sd_mt_spawn(name: "sd_dedup", fn: sd_dedup_worker, SD_MT_THREADS);
239
240 /* All refs are taken and none are released yet, since the depot
241 * must hold precisely one record with every ref accounted */
242 bool barrier = sd_mt_wait_for(counter: &sd_dedup_saved, SD_MT_THREADS);
243 bool clean = !atomic_load(&sd_mt.fail) && !atomic_load(&sd_mt.oom);
244
245 if (barrier && clean) {
246 stack_handle_t h = sd_dedup_handles[0];
247 if (h) {
248 struct stack_depot_record *rec = stack_depot_get_record(key: h);
249 if (refcount_read(rc: &rec->refcount) !=
250 SD_MT_THREADS * sd_dedup_saves_count)
251 sd_mt_report(msg: "refcount != total concurrent saves");
252
253 for (size_t i = 1; i < SD_MT_THREADS; i++)
254 if (sd_dedup_handles[i] != h)
255 sd_mt_report(msg: "threads got distinct records for one trace");
256
257 if (sd_chain_count(trace, SD_TRACE_LEN) != 1)
258 sd_mt_report(msg: "duplicate records on chain");
259 }
260 }
261
262 atomic_store(&sd_dedup_release, true);
263
264 if (!barrier) {
265 sd_mt_abandon();
266 return TEST_FAIL("workers did not reach the barrier in time");
267 }
268
269 SD_MT_JOIN();
270
271 /* Last put drops the record off the chain */
272 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
273 return TEST_SUCCESS;
274}
275
276#define SD_MT_SET 16
277#define SD_MT_SET_ID 0x4000
278static size_t sd_mt_set_iters_count = 1500;
279
280static bool sd_shared_body(size_t tid) {
281 uint64_t rng = sd_rng_seed(tid);
282
283 for (size_t i = 0; i < sd_mt_set_iters_count; i++) {
284 if (atomic_load(&sd_mt.stop))
285 return false;
286
287 size_t id = sd_rng(s: &rng) % SD_MT_SET;
288 uintptr_t want[SD_TRACE_LEN];
289 sd_make_trace(entries: want, SD_TRACE_LEN, SD_MT_SET_ID + id);
290
291 stack_handle_t h =
292 stack_depot_save(entries: want, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
293 if (!h) {
294 sd_mt_report_oom();
295 return false;
296 }
297
298 struct stack_depot_record *rec = stack_depot_get_record(key: h);
299 /* While we hold a ref the record has to be ours, so
300 * we check the data to make sure */
301 SD_WORKER_CHECK(rec->num_entries == SD_TRACE_LEN);
302 SD_WORKER_CHECK(rec->hash == stack_depot_hash(want, SD_TRACE_LEN));
303 SD_WORKER_CHECK(refcount_read(&rec->refcount) > 0);
304
305 uintptr_t got[STACK_TRACE_MAX_DEPTH];
306 size_t n = stack_depot_read(key: h, entries: got);
307 SD_WORKER_CHECK(n == SD_TRACE_LEN);
308 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
309
310 if (sd_rng(s: &rng) & 1)
311 scheduler_yield();
312
313 /* Re read after potential preemption, so racing put does not
314 * recycle the record under our ref */
315 SD_WORKER_CHECK(stack_depot_read(h, got) == SD_TRACE_LEN);
316 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
317
318 stack_depot_put(key: h);
319 }
320
321 return true;
322}
323
324static void sd_shared_worker(void *arg) {
325 sd_shared_body(tid: (size_t) (uintptr_t) arg);
326 atomic_fetch_sub(&sd_mt.left, 1);
327}
328
329TEST_DECLARE_INTEGRATION(stack_depot, mt_shared_set,
330 TEST_INTENSITY(200, 1500, 8000)) {
331 sd_mt_set_iters_count = ctx->intensity_val ? ctx->intensity_val : 1500;
332 sd_mt_reset(ctx, SD_MT_THREADS);
333 sd_mt_spawn(name: "sd_shared", fn: sd_shared_worker, SD_MT_THREADS);
334 SD_MT_JOIN();
335
336 /* Everything was put back and nothing left behind */
337 for (size_t id = 0; id < SD_MT_SET; id++) {
338 uintptr_t trace[SD_TRACE_LEN];
339 sd_make_trace(entries: trace, SD_TRACE_LEN, SD_MT_SET_ID + id);
340 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
341 }
342
343 return TEST_SUCCESS;
344}
345
346#define SD_MT_DISJOINT_PER_THREAD_MAX 128
347#define SD_MT_DISJOINT_ID 0x5000
348static size_t sd_mt_disjoint_per_thread = 32;
349
350static stack_handle_t sd_disjoint_handles[SD_MT_THREADS]
351 [SD_MT_DISJOINT_PER_THREAD_MAX];
352
353static bool sd_disjoint_body(size_t tid) {
354 stack_handle_t *mine = sd_disjoint_handles[tid];
355
356 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
357 uintptr_t trace[SD_TRACE_LEN];
358 sd_make_trace(entries: trace, SD_TRACE_LEN,
359 SD_MT_DISJOINT_ID + tid * sd_mt_disjoint_per_thread + i);
360
361 mine[i] = stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
362 if (!mine[i]) {
363 sd_mt_report_oom();
364 return false;
365 }
366
367 /* No one else uses this id, and we are the only reference */
368 SD_WORKER_CHECK(
369 refcount_read(&stack_depot_get_record(mine[i])->refcount) == 1);
370
371 stack_handle_t again =
372 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
373 SD_WORKER_CHECK(again == mine[i]);
374 SD_WORKER_CHECK(
375 refcount_read(&stack_depot_get_record(mine[i])->refcount) == 2);
376 stack_depot_put(key: again);
377
378 if ((i & 3) == 0)
379 scheduler_yield();
380 }
381
382 /* Re-verify after every thread has been hammering the same chains. */
383 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
384 uintptr_t want[SD_TRACE_LEN], got[STACK_TRACE_MAX_DEPTH];
385 sd_make_trace(entries: want, SD_TRACE_LEN,
386 SD_MT_DISJOINT_ID + tid * sd_mt_disjoint_per_thread + i);
387
388 SD_WORKER_CHECK(stack_depot_read(mine[i], got) == SD_TRACE_LEN);
389 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
390 SD_WORKER_CHECK(
391 refcount_read(&stack_depot_get_record(mine[i])->refcount) == 1);
392 }
393
394 return true;
395}
396
397static void sd_disjoint_worker(void *arg) {
398 size_t tid = (size_t) (uintptr_t) arg;
399
400 sd_disjoint_body(tid);
401
402 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
403 if (sd_disjoint_handles[tid][i]) {
404 stack_depot_put(key: sd_disjoint_handles[tid][i]);
405 sd_disjoint_handles[tid][i] = NULL;
406 }
407 }
408
409 atomic_fetch_sub(&sd_mt.left, 1);
410}
411
412TEST_DECLARE_INTEGRATION(stack_depot, mt_disjoint, TEST_INTENSITY(8, 32, 128)) {
413 sd_mt_disjoint_per_thread = ctx->intensity_val ? ctx->intensity_val : 32;
414 if (sd_mt_disjoint_per_thread > SD_MT_DISJOINT_PER_THREAD_MAX)
415 sd_mt_disjoint_per_thread = SD_MT_DISJOINT_PER_THREAD_MAX;
416
417 sd_mt_reset(ctx, SD_MT_THREADS);
418 memset(sd_disjoint_handles, 0, sizeof(sd_disjoint_handles));
419
420 sd_mt_spawn(name: "sd_disjoint", fn: sd_disjoint_worker, SD_MT_THREADS);
421 SD_MT_JOIN();
422
423 for (size_t t = 0; t < SD_MT_THREADS; t++) {
424 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
425 uintptr_t trace[SD_TRACE_LEN];
426 sd_make_trace(entries: trace, SD_TRACE_LEN,
427 SD_MT_DISJOINT_ID + t * sd_mt_disjoint_per_thread +
428 i);
429 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
430 }
431 }
432
433 return TEST_SUCCESS;
434}
435
436#define SD_MT_CHURN_SET 4
437#define SD_MT_CHURN_ID 0x6000
438static size_t sd_mt_churn_iters_count = 4000;
439
440/* Tiny id set and save/put pair keeps refcounts around zero,
441 * so we use that to test for races and issues here */
442static bool sd_churn_body(size_t tid) {
443 uint64_t rng = sd_rng_seed(tid: tid + SD_MT_THREADS);
444
445 for (size_t i = 0; i < sd_mt_churn_iters_count; i++) {
446 if (atomic_load(&sd_mt.stop))
447 return false;
448
449 size_t id = sd_rng(s: &rng) % SD_MT_CHURN_SET;
450 uintptr_t want[SD_TRACE_LEN];
451 sd_make_trace(entries: want, SD_TRACE_LEN, SD_MT_CHURN_ID + id);
452
453 stack_handle_t h =
454 stack_depot_save(entries: want, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
455 if (!h) {
456 sd_mt_report_oom();
457 return false;
458 }
459
460 uintptr_t got[STACK_TRACE_MAX_DEPTH];
461 SD_WORKER_CHECK(stack_depot_read(h, got) == SD_TRACE_LEN);
462 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
463 SD_WORKER_CHECK(refcount_read(&stack_depot_get_record(h)->refcount) >
464 0);
465
466 stack_depot_put(key: h);
467 }
468
469 return true;
470}
471
472static void sd_churn_worker(void *arg) {
473 sd_churn_body(tid: (size_t) (uintptr_t) arg);
474 atomic_fetch_sub(&sd_mt.left, 1);
475}
476
477TEST_DECLARE_INTEGRATION(stack_depot, mt_churn_race,
478 TEST_INTENSITY(500, 4000, 20000)) {
479 sd_mt_churn_iters_count = ctx->intensity_val ? ctx->intensity_val : 4000;
480 sd_mt_reset(ctx, SD_MT_THREADS);
481 sd_mt_spawn(name: "sd_churn", fn: sd_churn_worker, SD_MT_THREADS);
482 SD_MT_JOIN();
483
484 for (size_t id = 0; id < SD_MT_CHURN_SET; id++) {
485 uintptr_t trace[SD_TRACE_LEN];
486 sd_make_trace(entries: trace, SD_TRACE_LEN, SD_MT_CHURN_ID + id);
487 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
488 }
489
490 return TEST_SUCCESS;
491}
492
493static stack_handle_t sd_cur_handles[SD_MT_THREADS];
494static uintptr_t sd_cur_traces[SD_MT_THREADS][STACK_TRACE_MAX_DEPTH];
495static size_t sd_cur_lens[SD_MT_THREADS];
496
497static __noinline bool sd_cur_body(size_t tid) {
498 /* Both saves have to come from a single calls site, that's why we
499 * need to loop in sd_save_n(), otherwise it would be two different */
500 stack_handle_t h[2] = {0};
501 volatile size_t n = 2;
502
503 sd_save_n(out: h, n);
504
505 stack_handle_t a = h[0], b = h[1];
506 if (!a || !b) {
507 if (a)
508 stack_depot_put(key: a);
509 if (b)
510 stack_depot_put(key: b);
511 sd_mt_report_oom();
512 return false;
513 }
514
515 bool ok = true;
516 if (b != a) {
517 sd_mt_report(msg: "save_current did not dedup within a thread");
518 ok = false;
519 } else if (refcount_read(rc: &stack_depot_get_record(key: a)->refcount) < 2) {
520 sd_mt_report(msg: "save_current dropped a reference");
521 ok = false;
522 }
523
524 stack_depot_put(key: b);
525
526 if (ok) {
527 sd_cur_lens[tid] = stack_depot_read(key: a, entries: sd_cur_traces[tid]);
528 sd_cur_handles[tid] = a;
529 return true;
530 }
531
532 stack_depot_put(key: a);
533 return false;
534}
535
536static void sd_cur_worker(void *arg) {
537 sd_cur_body(tid: (size_t) (uintptr_t) arg);
538 atomic_fetch_sub(&sd_mt.left, 1);
539}
540
541TEST_DECLARE_INTEGRATION(stack_depot, mt_save_current) {
542 sd_mt_reset(ctx, SD_MT_THREADS);
543 memset(sd_cur_handles, 0, sizeof(sd_cur_handles));
544 memset(sd_cur_lens, 0, sizeof(sd_cur_lens));
545
546 sd_mt_spawn(name: "sd_cur", fn: sd_cur_worker, SD_MT_THREADS);
547 SD_MT_JOIN();
548
549 for (size_t i = 0; i < SD_MT_THREADS; i++) {
550 TEST_ASSERT_NONNULL(sd_cur_handles[i]);
551 TEST_ASSERT_GT(sd_cur_lens[i], 0);
552 TEST_ASSERT_LE(sd_cur_lens[i], STACK_TRACE_MAX_DEPTH);
553
554 for (size_t j = i + 1; j < SD_MT_THREADS; j++) {
555 bool same_trace = sd_cur_lens[i] == sd_cur_lens[j] &&
556 !memcmp(sd_cur_traces[i], sd_cur_traces[j],
557 sd_cur_lens[i] * sizeof(uintptr_t));
558 TEST_ASSERT_EQ(same_trace,
559 (sd_cur_handles[i] == sd_cur_handles[j]));
560 }
561 }
562
563 for (size_t i = 0; i < SD_MT_THREADS; i++)
564 stack_depot_put(key: sd_cur_handles[i]);
565
566 return TEST_SUCCESS;
567}
568