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>

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>

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>

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>

The s390 architecture uses the token "free" for an enum, conflicting
with the malloc/free definitions. Rename the calls to arena_malloc and
arena_free instead to prevent collisions.

Reported-by: Ihor Solodrai <ihor.solodrai@linux.dev>
Signed-off-by: Emil Tsalapatis <etsal@meta.com>
Fixes: 86426a28c52d ("selftests/bpf: Add buddy allocator for libarena")
Acked-by: Ihor Solodrai <ihor.solodrai@linux.dev>
Link: https://lore.kernel.org/r/20260428134252.2783519-1-etsal@meta.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Add a byte-oriented buddy allocator for libarena. The buddy
allocator provides an alloc/free interface for small arena allocations
ranging from 16 bytes to 512 KiB. Lower allocations values are rounded
up to 16 bytes. The buddy allocator does not handle larger allocations
that can instead use the existing bpf_arena_{alloc, free}_pages() kfunc.

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

Expand the arena library selftest infrastructure to support
address sanitization. Add the compiler flags necessary to
compile the library under ASAN when supported.

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

Add an address sanitizer (ASAN) runtime to the arena library. The
ASAN runtime implements the functions injected into BPF binaries
by LLVM sanitization when ASAN is enabled during compilation.

The runtime also includes functions called explicitly by memory
allocation code to mark memory as poisoned/unpoisoned to ASAN.
This code is a no-op when sanitization is turned off.

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

Add initial code and a Makefile for an arena-based BPF library. Modules
can be added just by including the source file in the library's src/
subdirectory. Future commits will introduce the library code itself.

The code includes workarounds that are removed in subsequent patches
that ensure bisectability.

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