// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
#include <bpf_atomic.h>
#include <libarena/common.h>
#include <libarena/asan.h>
#include <libarena/spmc.h>
#define TEST_SPMC_THREADS 3
#define TEST_SPMC_STEALERS (TEST_SPMC_THREADS - 1)
/*
* The test requires the stealers/owners to sometimes quiesce
* before continuing the benchmark. Normally we'd use something
* like a condition variable, but since the benchmark is short-lived
* and operations are wait-free we just spin around the quiescence
* point instead. If we time out, we just fail the benchmark.
*/
#define TEST_SPMC_SYNC_SPINS BPF_MAX_LOOPS
/*
* We track all the values we retrieve from the queue
* to get some guarantee we're, not corrupting data,
* e.g., accidentally reusing a past value from a slot.
*/
#define TEST_SPMC_MAX_VALUES (1024)
static u64 __arena seen[TEST_SPMC_MAX_VALUES];
/* The single spmc queue for the benchmark. */
static struct spmc __arena *spmc;
/* Owner and stealer epochs. We define the , */
static volatile u64 owner_epoch;
static volatile u64 stealer_epoch;
/* Map owner epochs to stealer epochs (simply scale by # of stealers). */
#define STEALER_EPOCH(owner_epoch) ((owner_epoch) * TEST_SPMC_STEALERS)
/* Global abort switch. If any thread fails, all others exit ASAP. */
static volatile bool test_abort;
/*
* Counters useful for ensuring conservation of pushes/pops of unique values
* (we're not stealing/popping more/fewer items than were pushed).
*/
static volatile u64 expected_total;
static volatile u64 total_seen;
/* Measure how many pops and steals we've made (irrespective of retrieved value). */
static volatile u64 pops;
static volatile u64 steals;
/* Used for the resize selftest, see below. */
static volatile u64 stealers_started;
/* Used for the mixed selftest, see below. */
static volatile u64 round_steals;
/*
* We have multiple stealers and a single owner. We sometimes want the owner
* to successfully outproduce the stealers, we add a busy loop in them.
*/
#define TEST_SPMC_WASTE_ROUNDS (1UL << 12)
/*
* The spmc data structure depends on the runtime fully
* supporting acquire/release semantics, which is not
* the case for all architectures.
*/
#if defined(ENABLE_ATOMICS_TESTS) && \
(defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \
(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64))
static bool spmc_tests_enabled(void)
{
return true;
}
#else
static bool spmc_tests_enabled(void)
{
return false;
}
#endif
/*
* Scaffolding for each parallel test. Each test has setup/teardown,
* a single owner thread that owns the queue, and TEST_SPMC_STEALER
* threads that try to steal.
*/
#define DEFINE_PARALLEL_SPMC_TEST(prefix, expected_total) \
SEC("syscall") int parallel_test_spmc_##prefix##__enabled(void) \
{ \
return spmc_tests_enabled() ? 0 : -EOPNOTSUPP; \
} \
SEC("syscall") int parallel_test_spmc_##prefix##__init(void) \
{ \
return spmc_common_init(expected_total); \
} \
SEC("syscall") int parallel_test_spmc_##prefix##__fini(void) \
{ \
return spmc_common_fini(); \
} \
SEC("syscall") int parallel_test_spmc_##prefix##__0(void) \
{ \
return spmc_##prefix##_owner(); \
} \
SEC("syscall") int parallel_test_spmc_##prefix##__1(void) \
{ \
return spmc_##prefix##_stealer(); \
} \
SEC("syscall") int parallel_test_spmc_##prefix##__2(void) \
{ \
return spmc_##prefix##_stealer(); \
} \
static int spmc_common_init(u64 total)
{
u64 i;
if (total > TEST_SPMC_MAX_VALUES)
return -E2BIG;
owner_epoch = 0;
stealer_epoch = 0;
test_abort = false;
expected_total = total;
total_seen = 0;
pops = 0;
steals = 0;
stealers_started = 0;
round_steals = 0;
for (i = zero; i < TEST_SPMC_MAX_VALUES && can_loop; i++)
seen[i] = 0;
spmc = spmc_create();
if (!spmc)
return -ENOMEM;
return 0;
}
static int spmc_common_fini(void)
{
int ret;
ret = spmc_destroy(spmc);
spmc = NULL;
return ret;
}
__weak
int spmc_quiesce_on_owner(u64 epoch)
{
u64 i;
for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
if (test_abort)
return -EINTR;
if (smp_load_acquire(&owner_epoch) >= epoch)
return 0;
}
test_abort = true;
return -ETIMEDOUT;
}
__weak
int spmc_quiesce_on_stealer(u64 epoch)
{
u64 target, cur;
unsigned int i;
int err = -ETIMEDOUT;
target = STEALER_EPOCH(epoch);
for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
if (test_abort) {
err = -EINTR;
break;
}
cur = smp_load_acquire(&stealer_epoch);
if (cur > target) {
err = -EINVAL;
test_abort = true;
break;
}
if (cur == target)
return 0;
}
test_abort = true;
return err;
}
static int spmc_update_stats(u64 val, bool owner)
{
u64 total;
total = expected_total;
if (val >= total || val >= TEST_SPMC_MAX_VALUES) {
test_abort = true;
return -EINVAL;
}
if (__sync_fetch_and_add(&seen[val], 1) != 0) {
test_abort = true;
return -EINVAL;
}
__sync_fetch_and_add(&total_seen, 1);
if (owner)
__sync_fetch_and_add(&pops, 1);
else
__sync_fetch_and_add(&steals, 1);
return 0;
}
static int spmc_validate_owner_empty(void)
{
u64 val;
int ret;
ret = spmc_owned_remove(spmc, &val);
if (ret != -ENOENT) {
test_abort = true;
/* Change a 0 return value into -EINVAL. */
return ret ?: -EINVAL;
}
return 0;
}
__weak
int spmc_validate_all_seen(void)
{
u64 i, total;
total = expected_total;
if (total_seen != total)
goto err;
if (pops + steals != total)
goto err;
for (i = zero; i < total && can_loop; i++) {
if (seen[i % TEST_SPMC_MAX_VALUES] != 1)
goto err;
}
return 0;
err:
test_abort = true;
return -EINVAL;
}
/*
* Single value benchmark. The owner adds an item then races with
* the stealers for it. This way directly race between owner and
* stealers on the same slot.
*/
#define TEST_SPMC_SINGLEVAL_ITERS (64)
__weak
int spmc_singleval_tryconsume(u64 expected, bool steal)
{
u64 val;
int ret;
while (can_loop) {
if (steal)
ret = spmc_steal(spmc, &val);
else
ret = spmc_owned_remove(spmc, &val);
/* Success. Update and validate. */
if (!ret) {
if (val != expected)
return -EINVAL;
ret = spmc_update_stats(val, !steal);
if (ret)
return ret;
return 0;
}
/*
* If we got -ENOENT, the queue is empty
* and we're good to go.
*/
if (ret != -EAGAIN)
return (ret == -ENOENT) ? 0 : ret;
}
/* Impossible. */
return -EINVAL;
}
static int spmc_singleval_owner(void)
{
int ret;
u64 i;
for (i = zero; i < TEST_SPMC_SINGLEVAL_ITERS && can_loop; i++) {
ret = spmc_quiesce_on_stealer(i);
if (ret)
goto err;
ret = spmc_owned_add(spmc, i);
if (ret)
goto err;
__sync_fetch_and_add(&owner_epoch, 1);
ret = spmc_singleval_tryconsume(i, false);
if (ret)
goto err;
ret = spmc_quiesce_on_stealer(i + 1);
if (ret)
goto err;
}
ret = spmc_validate_owner_empty();
if (ret)
return ret;
return spmc_validate_all_seen();
err:
test_abort = true;
return -EINVAL;
}
static int spmc_singleval_stealer(void)
{
int ret;
u64 i;
for (i = zero; i < TEST_SPMC_SINGLEVAL_ITERS && can_loop; i++) {
ret = spmc_quiesce_on_owner(i + 1);
if (ret)
goto err;
ret = spmc_singleval_tryconsume(i, true);
if (ret)
goto err;
__sync_fetch_and_add(&stealer_epoch, 1);
}
return 0;
err:
test_abort = true;
return -EINVAL;
}
DEFINE_PARALLEL_SPMC_TEST(singleval, TEST_SPMC_SINGLEVAL_ITERS)
/*
* The resize test. Force a resize from the owner even while the stealers
* are trying to consume. Then make sure the queue is still consistent
* after the resize.
*
* The owner _doesn't_ consume from the queue. The test makes sure that
* switching the array from underneath the stealers works.
*/
/* Force 2 resizes (since the rate of resize is logarithmic). */
#define TEST_SPMC_RESIZE_ORDER (2)
#define TEST_SPMC_RESIZE_PREFILL ((SPMC_ARR_BASESZ << TEST_SPMC_RESIZE_ORDER) - 1)
/* */
#define TEST_SPMC_RESIZE_TAIL (SPMC_ARR_BASESZ << TEST_SPMC_RESIZE_ORDER)
#define TEST_SPMC_RESIZE_TOTAL (TEST_SPMC_RESIZE_PREFILL + TEST_SPMC_RESIZE_TAIL)
__weak
int spmc_wait_for_stealers_to_start(u64 target)
{
u64 i;
for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
if (test_abort)
return -EINTR;
if (READ_ONCE(stealers_started) >= target)
return 0;
}
test_abort = true;
return -ETIMEDOUT;
}
__weak
void spmc_waste_time(void)
{
int i;
int j;
for (i = zero; i < TEST_SPMC_WASTE_ROUNDS && can_loop; i++) {
/* Random computation. */
WRITE_ONCE(j, i * 17 + 23);
}
}
static int spmc_resize_owner(void)
{
bool resized = false;
u64 i;
int ret;
/* Get a head start vs the consumers. */
for (i = zero; i < TEST_SPMC_RESIZE_PREFILL && can_loop; i++) {
ret = spmc_owned_add(spmc, i);
if (ret) {
test_abort = true;
return ret;
}
}
__sync_fetch_and_add(&owner_epoch, 1);
/* Wait for stealers to start then start racing. */
ret = spmc_wait_for_stealers_to_start(TEST_SPMC_STEALERS);
if (ret)
return ret;
for (i = TEST_SPMC_RESIZE_PREFILL; i < TEST_SPMC_RESIZE_TOTAL && can_loop; i++) {
ret = spmc_owned_add(spmc, i);
if (ret) {
test_abort = true;
return ret;
}
if (spmc->cur->order > TEST_SPMC_RESIZE_ORDER)
resized = true;
}
/* Did we get to resize while racing? */
if (!resized) {
test_abort = true;
return -EINVAL;
}
/*
* Wait for the stealers to drain and make sure
* we didn't lose any items along the way.
*/
__sync_fetch_and_add(&owner_epoch, 1);
ret = spmc_quiesce_on_stealer(1);
if (ret)
return ret;
ret = spmc_validate_owner_empty();
if (ret)
return ret;
return spmc_validate_all_seen();
}
static int spmc_resize_stealer(void)
{
bool owner_done = false;
u64 val;
int ret;
arena_subprog_init();
ret = spmc_quiesce_on_owner(1);
if (ret)
return ret;
__sync_fetch_and_add(&stealers_started, 1);
while (can_loop) {
spmc_waste_time();
if (test_abort)
return -EINTR;
ret = spmc_steal(spmc, &val);
if (!ret) {
ret = spmc_update_stats(val, false);
if (ret)
return ret;
continue;
}
if (ret == -EAGAIN)
continue;
if (ret == -ENOENT) {
if (owner_done)
break;
owner_done = owner_epoch >= 2;
continue;
}
test_abort = true;
return ret;
}
__sync_fetch_and_add(&stealer_epoch, 1);
return 0;
}
DEFINE_PARALLEL_SPMC_TEST(resize, TEST_SPMC_RESIZE_TOTAL)
/*
* The burst benchmark. The owner generates data all at once,
* then waits for the stealers to steal half then starts removing
* items until the queue empties. The owner also makes sure the
* item order is not jumbled.
*/
#define TEST_SPMC_BURST_ROUNDS (4)
#define TEST_SPMC_BURST_BURST (64)
#define TEST_SPMC_BURST_TOTAL (TEST_SPMC_BURST_ROUNDS * TEST_SPMC_BURST_BURST)
#define TEST_SPMC_BURST_STEAL_TARGET (TEST_SPMC_BURST_BURST / 2)
static int spmc_wait_for_round_steals(u64 target)
{
u64 i;
arena_subprog_init();
for (i = zero; i < TEST_SPMC_SYNC_SPINS && can_loop; i++) {
if (test_abort)
return -EINTR;
if (round_steals >= target)
return 0;
}
test_abort = true;
return -ETIMEDOUT;
}
__weak int
spmc_burst_owner_round(u64 round)
{
u64 i, base, stolen, expected, val;
int ret;
base = round * TEST_SPMC_BURST_BURST;
round_steals = 0;
for (i = zero; i < TEST_SPMC_BURST_BURST && can_loop; i++) {
ret = spmc_owned_add(spmc, base + i);
if (ret)
return ret;
}
__sync_fetch_and_add(&owner_epoch, 1);
ret = spmc_wait_for_round_steals(TEST_SPMC_BURST_STEAL_TARGET);
if (ret == -EINTR || ret == -ETIMEDOUT)
return ret;
__sync_fetch_and_add(&owner_epoch, 1);
ret = spmc_quiesce_on_stealer(round + 1);
if (ret)
return ret;
stolen = round_steals;
if (stolen > TEST_SPMC_BURST_BURST)
return -EINVAL;
for (i = zero; i < TEST_SPMC_BURST_BURST - stolen && can_loop; i++) {
ret = spmc_owned_remove(spmc, &val);
if (ret)
return ret;
expected = base + TEST_SPMC_BURST_BURST - 1 - i;
if (val != expected)
return -EINVAL;
ret = spmc_update_stats(val, true);
if (ret) {
test_abort = true;
return -EINVAL;
}
}
ret = spmc_validate_owner_empty();
if (ret)
return ret;
return 0;
}
static int spmc_burst_owner(void)
{
u64 round;
int ret;
arena_subprog_init();
for (round = zero; round < TEST_SPMC_BURST_ROUNDS && can_loop; round++) {
ret = spmc_burst_owner_round(round);
if (ret)
goto err;
}
return spmc_validate_all_seen();
err:
test_abort = true;
return -EINVAL;
}
static int spmc_burst_stealer(void)
{
u64 round, val, active_epoch;
int ret;
arena_subprog_init();
for (round = zero; round < TEST_SPMC_BURST_ROUNDS && can_loop; round++) {
active_epoch = round * 2 + 1;
/*
* Wait till the owner prefills the queue then
* start stealing.
*/
ret = spmc_quiesce_on_owner(active_epoch);
if (ret)
return ret;
while (owner_epoch == active_epoch && can_loop) {
if (test_abort)
return -EINTR;
ret = spmc_steal(spmc, &val);
if (!ret) {
ret = spmc_update_stats(val, false);
if (ret)
return ret;
__sync_fetch_and_add(&round_steals, 1);
continue;
}
if (ret == -EAGAIN || ret == -ENOENT)
continue;
test_abort = true;
return ret;
}
__sync_fetch_and_add(&stealer_epoch, 1);
}
return 0;
}
DEFINE_PARALLEL_SPMC_TEST(burst, TEST_SPMC_BURST_TOTAL)