selftests/bpf: libarena: parallel test harness and spmc parallel selftest

Add a parallel test for the SPMC Lev-Chase workstealing queue. The queue
is built to be wait-free even when there are multip

selftests/bpf: libarena: parallel test harness and spmc parallel selftest

Add a parallel test for the SPMC Lev-Chase workstealing queue. The queue
is built to be wait-free even when there are multiple consumers, and
the parallel selftest provides a signal on whether the queue behaves
correctly when stress tested.

To support the test, this patch includes a test harness for parallel
selftests. The spmc selftest acts as an example of the naming and other
conventions expected by the harness.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260605222020.5231-4-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

show more ...

selftests/bpf: libarena: Add spmc queue data structure

Expand libarena with a single producer multiple consumer deque data
structure. This is a single producer, multiple consumer lockless structure

selftests/bpf: libarena: Add spmc queue data structure

Expand libarena with a single producer multiple consumer deque data
structure. This is a single producer, multiple consumer lockless structure
that permits efficient work stealing. The structure is a Lev-Chase queue,
so it is lock-free and wait-free.

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:

spmc_owner_push(): Push an item to the top of the queue.
spmc_owner_pop(): Pop an item from the top of the queue.
spmc_steal(): Steal a thread from the bottom of the queue from
any thread.

Note that the queue is not really FIFO for all consumers, since
non-owners of the queue can only work steal from the bottom.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260605222020.5231-3-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

show more ...

selftests/bpf: libarena: Add rbtree data structure

Add a native red-black tree data structure to libarena.
The data structure supports multiple APIs (key-value based,
node based) with which users ca

selftests/bpf: libarena: Add rbtree data structure

Add a native red-black tree data structure to libarena.
The data structure supports multiple APIs (key-value based,
node based) with which users can query and modify it. The
tree uses the libarena memory allocator to manage its data.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260605222020.5231-2-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

show more ...

selftests/bpf: libarena: Directly return arena pointers from functions

Now that the __arena annotation includes a BTF type tag, and the
verifier can identify arena pointers at BTF loading time, retu

selftests/bpf: libarena: Directly return arena pointers from functions

Now that the __arena annotation includes a BTF type tag, and the
verifier can identify arena pointers at BTF loading time, return
arena pointers as their true type instead of casting to u64. Remove the
preprocessor typecast wrappers used to hide this from the caller.

Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260602004120.17087-6-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

show more ...

selftests/bpf: Remove __arg_arena from the codebase

Now that BPF __arg_arena has been subsumed by __arena, remove
__arg_arena from the codebase. This way the user has one fewer
annotation to worry a

selftests/bpf: Remove __arg_arena from the codebase

Now that BPF __arg_arena has been subsumed by __arena, remove
__arg_arena from the codebase. This way the user has one fewer
annotation to worry about.

To remove __arg_arena we remove the typedefs we were previously
using to minimize __arena annotations. This is because __arena
now also includes a BTF type tag, which is ignored for non-pointer
types. As a result, we cannot capture the whole __arena annotation
inside a typedef and need to directly annotate the pointer type when
declaring the variable.

The extra verbosity is worth it because the use of the __arena tag
is intuitive to the programmer and removes the __arg_arena tag that
has been a consistent source of confusion for users. The typedefs
can be reintroduced later (without __arg_arena) once compilers start
supporting BTF type tags for non-pointer types.

Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260602004120.17087-5-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

show more ...

selftests/bpf: libarena: Add "arena" BTF type tag to __arena qualifier

The arena qualifier currently designates its associated type
as belonging to address space 1. This property affects code
genera

selftests/bpf: libarena: Add "arena" BTF type tag to __arena qualifier

The arena qualifier currently designates its associated type
as belonging to address space 1. This property affects code
generation, but is not reflected in the BTF information of
the function.

This lack of information at the BTF level prevents us from
returning arena pointers from global subprograms. Subprogs
cannot return any data structure more complex than a scalar,
so pointers to structs are rejected as a return type. We
have no way of marking the return type as a pointer to an
arena, which is safe provided the two subprogs have the same
arena.

Expand the __arena qualifier to also attach a BTF type tag
to the type. This lets us determine whether a variable belongs
to an arena from its type alone through BTF parsing.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260602004120.17087-2-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

show more ...