Re: [RESEND PATCH bpf-next 2/2] selftests/bpf: libarena: Add Lev-Chase queue data structure

["Alexei Starovoitov" <alexei.starovoitov@gmail.com>]

On Mon May 11, 2026 at 2:41 PM PDT, Emil Tsalapatis wrote:
> Expand libarena with a Lev-Chase deque data structure. This is a single
> producer, multiple consumer lockless queue that permits efficient
> work stealing. The structure is lock-free and wait-free to minimize
> overhead.
>
> The data structure exposes three main calls. two of them are available to
> the thread owning the queue and one available to all threads in the program:
>
> lvqueue_owner_push(): Push an item to the top of the lvqueue.
> lvqueue_owner_pop(): Pop an item from the top of the lvqueue.
> lvqueue_steal(): Steal a thread from the bottom of the lvqueue from
> any thread.
>
> Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
> ---
>  .../bpf/libarena/include/libarena/lvqueue.h   |  33 +++
>  .../bpf/libarena/selftests/st_lvqueue.bpf.c   | 194 ++++++++++++++
>  .../selftests/bpf/libarena/src/lvqueue.bpf.c  | 241 ++++++++++++++++++
>  3 files changed, 468 insertions(+)
>  create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h
>  create mode 100644 tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c
>  create mode 100644 tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c
>
> diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h b/tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h
> new file mode 100644
> index 000000000000..c4091387c7a1
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h
> @@ -0,0 +1,33 @@
> +/* SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause */
> +
> +#pragma once
> +
> +struct lv_arr;
> +
> +#define LV_ARR_BASESZ 128
> +#define LV_ARR_ORDERS 10
> +
> +struct lv_arr {
> +	u64 __arena *data;
> +	u64 order;
> +};
> +
> +typedef volatile struct lv_arr __arena lv_arr_t;
> +
> +struct lv_queue {
> +	lv_arr_t *cur;
> +	volatile u64 top;
> +	volatile u64 bottom;
> +	struct lv_arr arr[LV_ARR_ORDERS];
> +};
> +
> +typedef struct lv_queue __arena lv_queue_t;
> +
> +int lvq_owner_push(lv_queue_t *lvq, u64 val);
> +int lvq_owner_pop(lv_queue_t *lvq, u64 *val);
> +int lvq_steal(lv_queue_t *lvq, u64 *val);

One more thing.
I feel the actual alogrithm name doesn't need to be in the name.
Maybe
spmc_queue_push()
spmc_queue_pop()
?