1 // SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
2
3 #include <bpf_atomic.h>
4
5 #include <libarena/common.h>
6
7 #include <libarena/asan.h>
8 #include <libarena/spmc.h>
9
10 #define TEST_SPMC_THREADS 3
11 #define TEST_SPMC_STEALERS (TEST_SPMC_THREADS - 1)
12
13 /*
14 * The test requires the stealers/owners to sometimes quiesce
15 * before continuing the benchmark. Normally we'd use something
16 * like a condition variable, but since the benchmark is short-lived
17 * and operations are wait-free we just spin around the quiescence
18 * point instead. If we time out, we just fail the benchmark.
19 */
20 #define TEST_SPMC_SYNC_SPINS BPF_MAX_LOOPS
21
22 /*
23 * We track all the values we retrieve from the queue
24 * to get some guarantee we're, not corrupting data,
25 * e.g., accidentally reusing a past value from a slot.
26 */
27 #define TEST_SPMC_MAX_VALUES (1024)
28 static u64 __arena seen[TEST_SPMC_MAX_VALUES];
29
30 /* The single spmc queue for the benchmark. */
31 static struct spmc __arena *spmc;
32
33 /* Owner and stealer epochs. We define the , */
34 static volatile u64 owner_epoch;
35 static volatile u64 stealer_epoch;
36
37 /* Map owner epochs to stealer epochs (simply scale by # of stealers). */
38 #define STEALER_EPOCH(owner_epoch) ((owner_epoch) * TEST_SPMC_STEALERS)
39
40 /* Global abort switch. If any thread fails, all others exit ASAP. */
41 static volatile bool test_abort;
42
43 /*
44 * Counters useful for ensuring conservation of pushes/pops of unique values
45 * (we're not stealing/popping more/fewer items than were pushed).
46 */
47 static volatile u64 expected_total;
48 static volatile u64 total_seen;
49
50 /* Measure how many pops and steals we've made (irrespective of retrieved value). */
51 static volatile u64 pops;
52 static volatile u64 steals;
53
54 /* Used for the resize selftest, see below. */
55 static volatile u64 stealers_started;
56
57 /* Used for the mixed selftest, see below. */
58 static volatile u64 round_steals;
59
60 /*
61 * We have multiple stealers and a single owner. We sometimes want the owner
62 * to successfully outproduce the stealers, we add a busy loop in them.
63 */
64 #define TEST_SPMC_WASTE_ROUNDS (1UL << 12)
65
66 /*
67 * The spmc data structure depends on the runtime fully
68 * supporting acquire/release semantics, which is not
69 * the case for all architectures.
70 */
71 #if defined(ENABLE_ATOMICS_TESTS) && \
72 (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \
73 (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64))
spmc_tests_enabled(void)74 static bool spmc_tests_enabled(void)
75 {
76 return true;
77 }
78 #else
spmc_tests_enabled(void)79 static bool spmc_tests_enabled(void)
80 {
81 return false;
82 }
83 #endif
84
85 /*
86 * Scaffolding for each parallel test. Each test has setup/teardown,
87 * a single owner thread that owns the queue, and TEST_SPMC_STEALER
88 * threads that try to steal.
89 */
90 #define DEFINE_PARALLEL_SPMC_TEST(prefix, expected_total) \
91 SEC("syscall") int parallel_test_spmc_##prefix##__enabled(void) \
92 { \
93 return spmc_tests_enabled() ? 0 : -EOPNOTSUPP; \
94 } \
95 SEC("syscall") int parallel_test_spmc_##prefix##__init(void) \
96 { \
97 return spmc_common_init(expected_total); \
98 } \
99 SEC("syscall") int parallel_test_spmc_##prefix##__fini(void) \
100 { \
101 return spmc_common_fini(); \
102 } \
103 SEC("syscall") int parallel_test_spmc_##prefix##__0(void) \
104 { \
105 return spmc_##prefix##_owner(); \
106 } \
107 SEC("syscall") int parallel_test_spmc_##prefix##__1(void) \
108 { \
109 return spmc_##prefix##_stealer(); \
110 } \
111 SEC("syscall") int parallel_test_spmc_##prefix##__2(void) \
112 { \
113 return spmc_##prefix##_stealer(); \
114 } \
115
spmc_common_init(u64 total)116 static int spmc_common_init(u64 total)
117 {
118 u64 i;
119
120 if (total > TEST_SPMC_MAX_VALUES)
121 return -E2BIG;
122
123 owner_epoch = 0;
124 stealer_epoch = 0;
125 test_abort = false;
126 expected_total = total;
127 total_seen = 0;
128 pops = 0;
129 steals = 0;
130 stealers_started = 0;
131 round_steals = 0;
132
133 for (i = zero; i < TEST_SPMC_MAX_VALUES && can_loop; i++)
134 seen[i] = 0;
135
136 spmc = spmc_create();
137 if (!spmc)
138 return -ENOMEM;
139
140 return 0;
141 }
142
spmc_common_fini(void)143 static int spmc_common_fini(void)
144 {
145 int ret;
146
147 ret = spmc_destroy(spmc);
148 spmc = NULL;
149
150 return ret;
151 }
152
153 __weak
spmc_quiesce_on_owner(u64 epoch)154 int spmc_quiesce_on_owner(u64 epoch)
155 {
156 u64 i;
157
158 for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
159 if (test_abort)
160 return -EINTR;
161 if (smp_load_acquire(&owner_epoch) >= epoch)
162 return 0;
163 }
164
165 test_abort = true;
166
167 return -ETIMEDOUT;
168 }
169
170 __weak
spmc_quiesce_on_stealer(u64 epoch)171 int spmc_quiesce_on_stealer(u64 epoch)
172 {
173 u64 target, cur;
174 unsigned int i;
175 int err = -ETIMEDOUT;
176
177 target = STEALER_EPOCH(epoch);
178 for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
179 if (test_abort) {
180 err = -EINTR;
181 break;
182 }
183
184 cur = smp_load_acquire(&stealer_epoch);
185 if (cur > target) {
186 err = -EINVAL;
187 test_abort = true;
188 break;
189 }
190
191 if (cur == target)
192 return 0;
193 }
194
195 test_abort = true;
196
197 return err;
198 }
199
spmc_update_stats(u64 val,bool owner)200 static int spmc_update_stats(u64 val, bool owner)
201 {
202 u64 total;
203
204 total = expected_total;
205 if (val >= total || val >= TEST_SPMC_MAX_VALUES) {
206 test_abort = true;
207 return -EINVAL;
208 }
209
210 if (__sync_fetch_and_add(&seen[val], 1) != 0) {
211 test_abort = true;
212 return -EINVAL;
213 }
214
215 __sync_fetch_and_add(&total_seen, 1);
216 if (owner)
217 __sync_fetch_and_add(&pops, 1);
218 else
219 __sync_fetch_and_add(&steals, 1);
220
221 return 0;
222 }
223
spmc_validate_owner_empty(void)224 static int spmc_validate_owner_empty(void)
225 {
226 u64 val;
227 int ret;
228
229 ret = spmc_owned_remove(spmc, &val);
230 if (ret != -ENOENT) {
231 test_abort = true;
232 /* Change a 0 return value into -EINVAL. */
233 return ret ?: -EINVAL;
234 }
235
236 return 0;
237 }
238
239 __weak
spmc_validate_all_seen(void)240 int spmc_validate_all_seen(void)
241 {
242 u64 i, total;
243
244 total = expected_total;
245 if (total_seen != total)
246 goto err;
247
248 if (pops + steals != total)
249 goto err;
250
251 for (i = zero; i < total && can_loop; i++) {
252 if (seen[i % TEST_SPMC_MAX_VALUES] != 1)
253 goto err;
254 }
255
256 return 0;
257
258 err:
259 test_abort = true;
260
261 return -EINVAL;
262 }
263
264 /*
265 * Single value benchmark. The owner adds an item then races with
266 * the stealers for it. This way directly race between owner and
267 * stealers on the same slot.
268 */
269
270
271 #define TEST_SPMC_SINGLEVAL_ITERS (64)
272
273 __weak
spmc_singleval_tryconsume(u64 expected,bool steal)274 int spmc_singleval_tryconsume(u64 expected, bool steal)
275 {
276 u64 val;
277 int ret;
278
279 while (can_loop) {
280 if (steal)
281 ret = spmc_steal(spmc, &val);
282 else
283 ret = spmc_owned_remove(spmc, &val);
284
285 /* Success. Update and validate. */
286 if (!ret) {
287 if (val != expected)
288 return -EINVAL;
289
290 ret = spmc_update_stats(val, !steal);
291 if (ret)
292 return ret;
293
294 return 0;
295 }
296
297 /*
298 * If we got -ENOENT, the queue is empty
299 * and we're good to go.
300 */
301 if (ret != -EAGAIN)
302 return (ret == -ENOENT) ? 0 : ret;
303 }
304
305 /* Impossible. */
306 return -EINVAL;
307 }
308
spmc_singleval_owner(void)309 static int spmc_singleval_owner(void)
310 {
311 int ret;
312 u64 i;
313
314 for (i = zero; i < TEST_SPMC_SINGLEVAL_ITERS && can_loop; i++) {
315 ret = spmc_quiesce_on_stealer(i);
316 if (ret)
317 goto err;
318
319 ret = spmc_owned_add(spmc, i);
320 if (ret)
321 goto err;
322
323 __sync_fetch_and_add(&owner_epoch, 1);
324
325 ret = spmc_singleval_tryconsume(i, false);
326 if (ret)
327 goto err;
328
329 ret = spmc_quiesce_on_stealer(i + 1);
330 if (ret)
331 goto err;
332 }
333
334 ret = spmc_validate_owner_empty();
335 if (ret)
336 return ret;
337
338 return spmc_validate_all_seen();
339
340 err:
341 test_abort = true;
342 return -EINVAL;
343 }
344
spmc_singleval_stealer(void)345 static int spmc_singleval_stealer(void)
346 {
347 int ret;
348 u64 i;
349
350 for (i = zero; i < TEST_SPMC_SINGLEVAL_ITERS && can_loop; i++) {
351 ret = spmc_quiesce_on_owner(i + 1);
352 if (ret)
353 goto err;
354
355 ret = spmc_singleval_tryconsume(i, true);
356 if (ret)
357 goto err;
358
359 __sync_fetch_and_add(&stealer_epoch, 1);
360 }
361
362 return 0;
363
364 err:
365 test_abort = true;
366 return -EINVAL;
367 }
368
DEFINE_PARALLEL_SPMC_TEST(singleval,TEST_SPMC_SINGLEVAL_ITERS)369 DEFINE_PARALLEL_SPMC_TEST(singleval, TEST_SPMC_SINGLEVAL_ITERS)
370
371 /*
372 * The resize test. Force a resize from the owner even while the stealers
373 * are trying to consume. Then make sure the queue is still consistent
374 * after the resize.
375 *
376 * The owner _doesn't_ consume from the queue. The test makes sure that
377 * switching the array from underneath the stealers works.
378 */
379
380 /* Force 2 resizes (since the rate of resize is logarithmic). */
381 #define TEST_SPMC_RESIZE_ORDER (2)
382 #define TEST_SPMC_RESIZE_PREFILL ((SPMC_ARR_BASESZ << TEST_SPMC_RESIZE_ORDER) - 1)
383
384 /* */
385 #define TEST_SPMC_RESIZE_TAIL (SPMC_ARR_BASESZ << TEST_SPMC_RESIZE_ORDER)
386 #define TEST_SPMC_RESIZE_TOTAL (TEST_SPMC_RESIZE_PREFILL + TEST_SPMC_RESIZE_TAIL)
387
388 __weak
389 int spmc_wait_for_stealers_to_start(u64 target)
390 {
391 u64 i;
392
393 for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
394 if (test_abort)
395 return -EINTR;
396 if (READ_ONCE(stealers_started) >= target)
397 return 0;
398 }
399
400 test_abort = true;
401
402 return -ETIMEDOUT;
403 }
404
405 __weak
spmc_waste_time(void)406 void spmc_waste_time(void)
407 {
408 int i;
409 int j;
410
411 for (i = zero; i < TEST_SPMC_WASTE_ROUNDS && can_loop; i++) {
412 /* Random computation. */
413 WRITE_ONCE(j, i * 17 + 23);
414 }
415 }
416
spmc_resize_owner(void)417 static int spmc_resize_owner(void)
418 {
419 bool resized = false;
420 u64 i;
421 int ret;
422
423 /* Get a head start vs the consumers. */
424 for (i = zero; i < TEST_SPMC_RESIZE_PREFILL && can_loop; i++) {
425 ret = spmc_owned_add(spmc, i);
426 if (ret) {
427 test_abort = true;
428 return ret;
429 }
430 }
431
432 __sync_fetch_and_add(&owner_epoch, 1);
433
434 /* Wait for stealers to start then start racing. */
435 ret = spmc_wait_for_stealers_to_start(TEST_SPMC_STEALERS);
436 if (ret)
437 return ret;
438
439 for (i = TEST_SPMC_RESIZE_PREFILL; i < TEST_SPMC_RESIZE_TOTAL && can_loop; i++) {
440 ret = spmc_owned_add(spmc, i);
441 if (ret) {
442 test_abort = true;
443 return ret;
444 }
445
446 if (spmc->cur->order > TEST_SPMC_RESIZE_ORDER)
447 resized = true;
448 }
449
450 /* Did we get to resize while racing? */
451 if (!resized) {
452 test_abort = true;
453 return -EINVAL;
454 }
455
456 /*
457 * Wait for the stealers to drain and make sure
458 * we didn't lose any items along the way.
459 */
460 __sync_fetch_and_add(&owner_epoch, 1);
461
462 ret = spmc_quiesce_on_stealer(1);
463 if (ret)
464 return ret;
465
466 ret = spmc_validate_owner_empty();
467 if (ret)
468 return ret;
469
470 return spmc_validate_all_seen();
471 }
472
spmc_resize_stealer(void)473 static int spmc_resize_stealer(void)
474 {
475 bool owner_done = false;
476 u64 val;
477 int ret;
478
479 arena_subprog_init();
480
481 ret = spmc_quiesce_on_owner(1);
482 if (ret)
483 return ret;
484
485 __sync_fetch_and_add(&stealers_started, 1);
486
487 while (can_loop) {
488 spmc_waste_time();
489 if (test_abort)
490 return -EINTR;
491
492 ret = spmc_steal(spmc, &val);
493 if (!ret) {
494 ret = spmc_update_stats(val, false);
495 if (ret)
496 return ret;
497 continue;
498 }
499
500 if (ret == -EAGAIN)
501 continue;
502
503 if (ret == -ENOENT) {
504 if (owner_done)
505 break;
506 owner_done = owner_epoch >= 2;
507 continue;
508 }
509
510 test_abort = true;
511 return ret;
512 }
513
514 __sync_fetch_and_add(&stealer_epoch, 1);
515
516 return 0;
517 }
518
DEFINE_PARALLEL_SPMC_TEST(resize,TEST_SPMC_RESIZE_TOTAL)519 DEFINE_PARALLEL_SPMC_TEST(resize, TEST_SPMC_RESIZE_TOTAL)
520
521 /*
522 * The burst benchmark. The owner generates data all at once,
523 * then waits for the stealers to steal half then starts removing
524 * items until the queue empties. The owner also makes sure the
525 * item order is not jumbled.
526 */
527
528 #define TEST_SPMC_BURST_ROUNDS (4)
529 #define TEST_SPMC_BURST_BURST (64)
530 #define TEST_SPMC_BURST_TOTAL (TEST_SPMC_BURST_ROUNDS * TEST_SPMC_BURST_BURST)
531 #define TEST_SPMC_BURST_STEAL_TARGET (TEST_SPMC_BURST_BURST / 2)
532
533 static int spmc_wait_for_round_steals(u64 target)
534 {
535 u64 i;
536
537 arena_subprog_init();
538
539 for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
540 if (test_abort)
541 return -EINTR;
542 if (round_steals >= target)
543 return 0;
544 }
545
546 test_abort = true;
547
548 return -ETIMEDOUT;
549 }
550
551 __weak int
spmc_burst_owner_round(u64 round)552 spmc_burst_owner_round(u64 round)
553 {
554 u64 i, base, stolen, expected, val;
555 int ret;
556
557 base = round * TEST_SPMC_BURST_BURST;
558 round_steals = 0;
559
560 for (i = zero; i < TEST_SPMC_BURST_BURST && can_loop; i++) {
561 ret = spmc_owned_add(spmc, base + i);
562 if (ret)
563 return ret;
564 }
565
566 __sync_fetch_and_add(&owner_epoch, 1);
567
568 ret = spmc_wait_for_round_steals(TEST_SPMC_BURST_STEAL_TARGET);
569 if (ret == -EINTR || ret == -ETIMEDOUT)
570 return ret;
571
572 __sync_fetch_and_add(&owner_epoch, 1);
573
574 ret = spmc_quiesce_on_stealer(round + 1);
575 if (ret)
576 return ret;
577
578 stolen = round_steals;
579 if (stolen > TEST_SPMC_BURST_BURST)
580 return -EINVAL;
581
582 for (i = zero; i < TEST_SPMC_BURST_BURST - stolen && can_loop; i++) {
583 ret = spmc_owned_remove(spmc, &val);
584 if (ret)
585 return ret;
586
587 expected = base + TEST_SPMC_BURST_BURST - 1 - i;
588 if (val != expected)
589 return -EINVAL;
590
591 ret = spmc_update_stats(val, true);
592 if (ret) {
593 test_abort = true;
594 return -EINVAL;
595 }
596 }
597
598 ret = spmc_validate_owner_empty();
599 if (ret)
600 return ret;
601
602 return 0;
603 }
604
spmc_burst_owner(void)605 static int spmc_burst_owner(void)
606 {
607 u64 round;
608 int ret;
609
610 arena_subprog_init();
611
612 for (round = zero; round < TEST_SPMC_BURST_ROUNDS && can_loop; round++) {
613 ret = spmc_burst_owner_round(round);
614 if (ret)
615 goto err;
616 }
617
618 return spmc_validate_all_seen();
619
620 err:
621 test_abort = true;
622 return -EINVAL;
623 }
624
spmc_burst_stealer(void)625 static int spmc_burst_stealer(void)
626 {
627 u64 round, val, active_epoch;
628 int ret;
629
630 arena_subprog_init();
631
632 for (round = zero; round < TEST_SPMC_BURST_ROUNDS && can_loop; round++) {
633 active_epoch = round * 2 + 1;
634
635 /*
636 * Wait till the owner prefills the queue then
637 * start stealing.
638 */
639 ret = spmc_quiesce_on_owner(active_epoch);
640 if (ret)
641 return ret;
642
643 while (owner_epoch == active_epoch && can_loop) {
644 if (test_abort)
645 return -EINTR;
646
647 ret = spmc_steal(spmc, &val);
648 if (!ret) {
649 ret = spmc_update_stats(val, false);
650 if (ret)
651 return ret;
652 __sync_fetch_and_add(&round_steals, 1);
653 continue;
654 }
655 if (ret == -EAGAIN || ret == -ENOENT)
656 continue;
657
658 test_abort = true;
659 return ret;
660 }
661
662 __sync_fetch_and_add(&stealer_epoch, 1);
663 }
664
665 return 0;
666 }
667
668 DEFINE_PARALLEL_SPMC_TEST(burst, TEST_SPMC_BURST_TOTAL)
669