1#include "tests/test_internal.h"
2
3static cc_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, hash_list)
87 if (pos->num_entries == len &&
88 !memcmp(pos->entries, trace, len * sizeof(uintptr_t)))
89 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 enforce(n <= SD_MT_THREADS, CAPACITY_EXCEEDED);
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] = thread_spawn(
172 ("%s", name), fn, .arg = (void *) (uintptr_t) i, .joinable = true);
173 irql_lower(old_level: irql);
174}
175
176#define SD_MT_DEDUP_SAVES_MAX ((size_t) 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 if (*held_n == 0)
202 return false;
203
204 sd_dedup_handles[tid] = held[0];
205 return true;
206}
207
208static void sd_dedup_worker(void *arg) {
209 size_t tid = (size_t) (uintptr_t) arg;
210 stack_handle_t held[SD_MT_DEDUP_SAVES_MAX];
211 size_t held_n = 0;
212
213 sd_dedup_body(tid, held, held_n: &held_n);
214
215 /* Publish unconditionally since the main thread will be waiting */
216 atomic_inc(&sd_dedup_saved);
217
218 while (!atomic_load(&sd_dedup_release))
219 scheduler_yield();
220
221 for (size_t i = 0; i < held_n; i++)
222 stack_depot_putref(key: held[i]);
223
224 atomic_dec(&sd_mt.left);
225}
226
227TEST_DEFINE_INTEGRATION(stack_depot, mt_dedup, TEST_INTENSITY(16, 64, 256)) {
228 uintptr_t trace[SD_TRACE_LEN];
229 sd_make_trace(entries: trace, SD_TRACE_LEN, SD_MT_DEDUP_ID);
230 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
231
232 sd_dedup_saves_count = MIN(ctx->intensity_val ? ctx->intensity_val : 64,
233 SD_MT_DEDUP_SAVES_MAX);
234
235 sd_mt_reset(ctx, SD_MT_THREADS);
236 atomic_store(&sd_dedup_saved, 0);
237 atomic_store(&sd_dedup_release, false);
238 memset(sd_dedup_handles, 0, sizeof(sd_dedup_handles));
239
240 sd_mt_spawn(name: "sd_dedup", fn: sd_dedup_worker, SD_MT_THREADS);
241
242 /* All refs are taken and none are released yet, since the depot
243 * must hold precisely one record with every ref accounted */
244 bool barrier = sd_mt_wait_for(counter: &sd_dedup_saved, SD_MT_THREADS);
245 bool clean = !atomic_load(&sd_mt.fail) && !atomic_load(&sd_mt.oom);
246
247 if (barrier && clean) {
248 stack_handle_t h = sd_dedup_handles[0];
249 if (h) {
250 struct stack_depot_record *rec = stack_depot_get_record(key: h);
251 if (refcount_read(rc: &rec->refcount) !=
252 SD_MT_THREADS * sd_dedup_saves_count)
253 sd_mt_report(msg: "refcount != total concurrent saves");
254
255 for (size_t i = 1; i < SD_MT_THREADS; i++)
256 if (sd_dedup_handles[i] != h)
257 sd_mt_report(msg: "threads got distinct records for one trace");
258
259 if (sd_chain_count(trace, SD_TRACE_LEN) != 1)
260 sd_mt_report(msg: "duplicate records on chain");
261 }
262 }
263
264 atomic_store(&sd_dedup_release, true);
265
266 if (!barrier) {
267 sd_mt_abandon();
268 return TEST_FAIL("workers did not reach the barrier in time");
269 }
270
271 SD_MT_JOIN();
272
273 /* Last putref drops the record off the chain */
274 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
275 return TEST_SUCCESS;
276}
277
278#define SD_MT_SET 16
279#define SD_MT_SET_ID 0x4000
280static size_t sd_mt_set_iters_count = 1500;
281
282static bool sd_shared_body(size_t tid) {
283 uint64_t rng = sd_rng_seed(tid);
284
285 for (size_t i = 0; i < sd_mt_set_iters_count; i++) {
286 if (atomic_load(&sd_mt.stop))
287 return false;
288
289 size_t id = sd_rng(s: &rng) % SD_MT_SET;
290 uintptr_t want[SD_TRACE_LEN];
291 sd_make_trace(entries: want, SD_TRACE_LEN, SD_MT_SET_ID + id);
292
293 stack_handle_t h =
294 stack_depot_save(entries: want, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
295 if (!h) {
296 sd_mt_report_oom();
297 return false;
298 }
299
300 struct stack_depot_record *rec = stack_depot_get_record(key: h);
301 /* While we hold a ref the record has to be ours, so
302 * we check the data to make sure */
303 SD_WORKER_CHECK(rec->num_entries == SD_TRACE_LEN);
304 SD_WORKER_CHECK(rec->hash == stack_depot_hash(want, SD_TRACE_LEN));
305 SD_WORKER_CHECK(refcount_read(&rec->refcount) > 0);
306
307 uintptr_t got[STACK_TRACE_MAX_DEPTH];
308 size_t n = stack_depot_read(key: h, entries: got);
309 SD_WORKER_CHECK(n == SD_TRACE_LEN);
310 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
311
312 if (sd_rng(s: &rng) & 1)
313 scheduler_yield();
314
315 /* Re read after potential preemption, so racing putref does not
316 * recycle the record under our ref */
317 SD_WORKER_CHECK(stack_depot_read(h, got) == SD_TRACE_LEN);
318 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
319
320 stack_depot_putref(key: h);
321 }
322
323 return true;
324}
325
326static void sd_shared_worker(void *arg) {
327 sd_shared_body(tid: (size_t) (uintptr_t) arg);
328 atomic_dec(&sd_mt.left);
329}
330
331TEST_DEFINE_INTEGRATION(stack_depot, mt_shared_set,
332 TEST_INTENSITY(200, 1500, 8000)) {
333 sd_mt_set_iters_count = ctx->intensity_val ? ctx->intensity_val : 1500;
334 sd_mt_reset(ctx, SD_MT_THREADS);
335 sd_mt_spawn(name: "sd_shared", fn: sd_shared_worker, SD_MT_THREADS);
336 SD_MT_JOIN();
337
338 /* Everything was putref-ed back and nothing left behind */
339 for (size_t id = 0; id < SD_MT_SET; id++) {
340 uintptr_t trace[SD_TRACE_LEN];
341 sd_make_trace(entries: trace, SD_TRACE_LEN, SD_MT_SET_ID + id);
342 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
343 }
344
345 return TEST_SUCCESS;
346}
347
348#define SD_MT_DISJOINT_PER_THREAD_MAX ((size_t) 128)
349#define SD_MT_DISJOINT_ID 0x5000
350static size_t sd_mt_disjoint_per_thread = 32;
351
352static stack_handle_t sd_disjoint_handles[SD_MT_THREADS]
353 [SD_MT_DISJOINT_PER_THREAD_MAX];
354
355static bool sd_disjoint_body(size_t tid) {
356 stack_handle_t *mine = sd_disjoint_handles[tid];
357
358 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
359 uintptr_t trace[SD_TRACE_LEN];
360 sd_make_trace(entries: trace, SD_TRACE_LEN,
361 SD_MT_DISJOINT_ID + tid * sd_mt_disjoint_per_thread + i);
362
363 mine[i] = stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
364 if (!mine[i]) {
365 sd_mt_report_oom();
366 return false;
367 }
368
369 /* No one else uses this id, and we are the only reference */
370 SD_WORKER_CHECK(
371 refcount_read(&stack_depot_get_record(mine[i])->refcount) == 1);
372
373 stack_handle_t again =
374 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
375 SD_WORKER_CHECK(again == mine[i]);
376 SD_WORKER_CHECK(
377 refcount_read(&stack_depot_get_record(mine[i])->refcount) == 2);
378 stack_depot_putref(key: again);
379
380 if ((i & 3) == 0)
381 scheduler_yield();
382 }
383
384 /* Re-verify after every thread has been hammering the same chains. */
385 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
386 uintptr_t want[SD_TRACE_LEN], got[STACK_TRACE_MAX_DEPTH];
387 sd_make_trace(entries: want, SD_TRACE_LEN,
388 SD_MT_DISJOINT_ID + tid * sd_mt_disjoint_per_thread + i);
389
390 SD_WORKER_CHECK(stack_depot_read(mine[i], got) == SD_TRACE_LEN);
391 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
392 SD_WORKER_CHECK(
393 refcount_read(&stack_depot_get_record(mine[i])->refcount) == 1);
394 }
395
396 return true;
397}
398
399static void sd_disjoint_worker(void *arg) {
400 size_t tid = (size_t) (uintptr_t) arg;
401
402 sd_disjoint_body(tid);
403
404 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
405 if (sd_disjoint_handles[tid][i]) {
406 stack_depot_putref(key: sd_disjoint_handles[tid][i]);
407 sd_disjoint_handles[tid][i] = NULL;
408 }
409 }
410
411 atomic_dec(&sd_mt.left);
412}
413
414TEST_DEFINE_INTEGRATION(stack_depot, mt_disjoint, TEST_INTENSITY(8, 32, 128)) {
415 sd_mt_disjoint_per_thread =
416 MIN(ctx->intensity_val ? ctx->intensity_val : 32,
417 SD_MT_DISJOINT_PER_THREAD_MAX);
418
419 sd_mt_reset(ctx, SD_MT_THREADS);
420 memset(sd_disjoint_handles, 0, sizeof(sd_disjoint_handles));
421
422 sd_mt_spawn(name: "sd_disjoint", fn: sd_disjoint_worker, SD_MT_THREADS);
423 SD_MT_JOIN();
424
425 for (size_t t = 0; t < SD_MT_THREADS; t++) {
426 for (size_t i = 0; i < sd_mt_disjoint_per_thread; i++) {
427 uintptr_t trace[SD_TRACE_LEN];
428 sd_make_trace(entries: trace, SD_TRACE_LEN,
429 SD_MT_DISJOINT_ID + t * sd_mt_disjoint_per_thread +
430 i);
431 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
432 }
433 }
434
435 return TEST_SUCCESS;
436}
437
438#define SD_MT_CHURN_SET 4
439#define SD_MT_CHURN_ID 0x6000
440static size_t sd_mt_churn_iters_count = 4000;
441
442/* Tiny id set and save/putref pair keeps refcounts around zero,
443 * so we use that to test for races and issues here */
444static bool sd_churn_body(size_t tid) {
445 uint64_t rng = sd_rng_seed(tid: tid + SD_MT_THREADS);
446
447 for (size_t i = 0; i < sd_mt_churn_iters_count; i++) {
448 if (atomic_load(&sd_mt.stop))
449 return false;
450
451 size_t id = sd_rng(s: &rng) % SD_MT_CHURN_SET;
452 uintptr_t want[SD_TRACE_LEN];
453 sd_make_trace(entries: want, SD_TRACE_LEN, SD_MT_CHURN_ID + id);
454
455 stack_handle_t h =
456 stack_depot_save(entries: want, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
457 if (!h) {
458 sd_mt_report_oom();
459 return false;
460 }
461
462 uintptr_t got[STACK_TRACE_MAX_DEPTH];
463 SD_WORKER_CHECK(stack_depot_read(h, got) == SD_TRACE_LEN);
464 SD_WORKER_CHECK(!memcmp(got, want, sizeof(want)));
465 SD_WORKER_CHECK(refcount_read(&stack_depot_get_record(h)->refcount) >
466 0);
467
468 stack_depot_putref(key: h);
469 }
470
471 return true;
472}
473
474static void sd_churn_worker(void *arg) {
475 sd_churn_body(tid: (size_t) (uintptr_t) arg);
476 atomic_dec(&sd_mt.left);
477}
478
479TEST_DEFINE_INTEGRATION(stack_depot, mt_churn_race,
480 TEST_INTENSITY(500, 4000, 20000)) {
481 sd_mt_churn_iters_count = ctx->intensity_val ? ctx->intensity_val : 4000;
482 sd_mt_reset(ctx, SD_MT_THREADS);
483 sd_mt_spawn(name: "sd_churn", fn: sd_churn_worker, SD_MT_THREADS);
484 SD_MT_JOIN();
485
486 for (size_t id = 0; id < SD_MT_CHURN_SET; id++) {
487 uintptr_t trace[SD_TRACE_LEN];
488 sd_make_trace(entries: trace, SD_TRACE_LEN, SD_MT_CHURN_ID + id);
489 TEST_ASSERT_EQ(sd_chain_count(trace, SD_TRACE_LEN), 0);
490 }
491
492 return TEST_SUCCESS;
493}
494
495static stack_handle_t sd_cur_handles[SD_MT_THREADS];
496static uintptr_t sd_cur_traces[SD_MT_THREADS][STACK_TRACE_MAX_DEPTH];
497static size_t sd_cur_lens[SD_MT_THREADS];
498
499static cc_noinline bool sd_cur_body(size_t tid) {
500 /* Both saves have to come from a single calls site, that's why we
501 * need to loop in sd_save_n(), otherwise it would be two different */
502 stack_handle_t h[2] = {0};
503 volatile size_t n = 2;
504
505 sd_save_n(out: h, n);
506
507 stack_handle_t a = h[0], b = h[1];
508 if (!a || !b) {
509 if (a)
510 stack_depot_putref(key: a);
511 if (b)
512 stack_depot_putref(key: b);
513 sd_mt_report_oom();
514 return false;
515 }
516
517 bool ok = true;
518 if (b != a) {
519 sd_mt_report(msg: "save_current did not dedup within a thread");
520 ok = false;
521 } else if (refcount_read(rc: &stack_depot_get_record(key: a)->refcount) < 2) {
522 sd_mt_report(msg: "save_current dropped a reference");
523 ok = false;
524 }
525
526 stack_depot_putref(key: b);
527
528 if (ok) {
529 sd_cur_lens[tid] = stack_depot_read(key: a, entries: sd_cur_traces[tid]);
530 sd_cur_handles[tid] = a;
531 return true;
532 }
533
534 stack_depot_putref(key: a);
535 return false;
536}
537
538static void sd_cur_worker(void *arg) {
539 sd_cur_body(tid: (size_t) (uintptr_t) arg);
540 atomic_dec(&sd_mt.left);
541}
542
543TEST_DEFINE_INTEGRATION(stack_depot, mt_save_current) {
544 sd_mt_reset(ctx, SD_MT_THREADS);
545 memset(sd_cur_handles, 0, sizeof(sd_cur_handles));
546 memset(sd_cur_lens, 0, sizeof(sd_cur_lens));
547
548 sd_mt_spawn(name: "sd_cur", fn: sd_cur_worker, SD_MT_THREADS);
549 SD_MT_JOIN();
550
551 for (size_t i = 0; i < SD_MT_THREADS; i++) {
552 TEST_ASSERT_NONNULL(sd_cur_handles[i]);
553 TEST_ASSERT_GT(sd_cur_lens[i], 0);
554 TEST_ASSERT_LE(sd_cur_lens[i], STACK_TRACE_MAX_DEPTH);
555
556 for (size_t j = i + 1; j < SD_MT_THREADS; j++) {
557 bool same_trace = sd_cur_lens[i] == sd_cur_lens[j] &&
558 !memcmp(sd_cur_traces[i], sd_cur_traces[j],
559 sd_cur_lens[i] * sizeof(uintptr_t));
560 TEST_ASSERT_EQ(same_trace,
561 (sd_cur_handles[i] == sd_cur_handles[j]));
562 }
563 }
564
565 for (size_t i = 0; i < SD_MT_THREADS; i++)
566 stack_depot_putref(key: sd_cur_handles[i]);
567
568 return TEST_SUCCESS;
569}
570