| Age | Commit message (Collapse) | Author |
|---|
|
bpf_arena_spin_lock.h defines its 64KB qnodes array in the header, so
every translation unit including it emits a copy. __weak makes them all
resolve to one instance, but bpftool gen object merges only the symbols
and concatenates each input's .addr_space.1 bytes, leaving the surplus
copies unreferenced in the linked object.
libarena links ten such units, so nine copies were dead weight (bytes):
object before after
-----------------------------------------------------
.addr_space.1 in libarena.bpf.o 676200 86376
libarena.skel.h 2100123 892371
libarena_asan.skel.h 2641124 1466477
Declare qnodes in the header and let each program define it once:
libarena in src/common.bpf.c, and the arena_spin_lock test beside the
lock it guards.
Tested with test_progs -t arena_spin_lock and -t libarena.
Signed-off-by: Changwoo Min <changwoo@igalia.com>
Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/bpf/20260817160249.655916-1-changwoo@igalia.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
Teach libarena's BPF atomic primitives to use compiler builtins for
load-acquire and store-release when Clang advertises
__BPF_FEATURE_LOAD_ACQ_STORE_REL. Older compilers continue to use the
existing barrier-based fallback.
Notably, as BPF programs begin running on arm64, it is better to use the
more appropriate variants since we can no longer rely on x86 TSO ordering.
Commit 880442305a39 ("bpf: Introduce load-acquire and store-release instructions")
introduced support, hence kernels from 6.15 onwards are needed when
compiling with compilers supporting these instructions. We have
relatively recent kernel version requirements in libarena anyway, and
have not cut first release, hence declare such a dependency.
Signed-off-by: Puranjay Mohan <puranjay@kernel.org>
Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/bpf/20260722141003.2841007-1-puranjay@kernel.org
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
When compiling BPF selftests with -O2, GCC reports a maybe-uninitialized
warning in libarena code:
In file included from /bpf-next/tools/testing/selftests/bpf/prog_tests/libarena_asan.c:11:
In function ‘libarena_asan_init’,
inlined from ‘run_test’ at /bpf-next/tools/testing/selftests/bpf/prog_tests/libarena_asan.c:59:8,
inlined from ‘test_libarena_asan’ at /bpf-next/tools/testing/selftests/bpf/prog_tests/libarena_asan.c:91:2:
/bpf-next/tools/testing/selftests/bpf/libarena/include/libarena/userspace.h:126:14: error: ‘globals_pages’ may be used uninitialized [-Werror=maybe-uninitialized]
126 | args = (struct asan_init_args){
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
127 | .arena_all_pages = arena_all_pages,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
128 | .arena_globals_pages = globals_pages,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
129 | };
| ~
/bpf-next/tools/testing/selftests/bpf/libarena/include/libarena/userspace.h: In function ‘test_libarena_asan’:
/bpf-next/tools/testing/selftests/bpf/libarena/include/libarena/userspace.h:118:13: note: ‘globals_pages’ was declared here
118 | u64 globals_pages;
| ^~~~~~~~~~~~~
Silence the warning by initializing globals_pages to 0.
Fixes: cfc00618b9df ("selftests/bpf: Add ASAN support for libarena selftests")
Signed-off-by: Viktor Malik <vmalik@redhat.com>
Link: https://lore.kernel.org/bpf/9f77a5c05c3c731ab2655fd66716ab9de4478b15.1784112948.git.vmalik@redhat.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
When building bpf selftest with latest bpf-next, I got the following failure:
In file included from /home/yhs/work/bpf-next/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c:8:
/home/yhs/work/bpf-next/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h:11:8: error: redefinition of
'bitmap'
11 | struct bitmap {
| ^
/home/yhs/work/bpf-next/tools/testing/selftests/bpf/tools/include/vmlinux.h:51320:8: note: previous definition is here
51320 | struct bitmap {
| ^
The vmlinux.h struct bitmap comes from drivers/md/md-bitmap.c:
struct bitmap {
struct bitmap_counts { ... }
...
}
To fix the issue, I renamed libarena struct bitmap to arena_bitmap to avoid the conflict.
Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/bpf/20260707220136.910374-1-yonghong.song@linux.dev
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
Add a selftest for testing the atomic bitmap set/clear/
test_and_set/test_and_clear operations. The selftest
checks atomicity by spawning two threads, each of which
either only works on even bits or with odd bits. The
test checks that threads do not affect each other's
bits.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/bpf/20260706181730.21731-7-emil@etsalapatis.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
Add testing for the new arena bitmap data structure.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Acked-by: Ihor Solodrai <ihor.solodrai@linux.dev>
Link: https://lore.kernel.org/bpf/20260706181730.21731-6-emil@etsalapatis.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
Add an arena-based word-aligned bitmap data struture. The
structure is useful as a building block, e.g., sched-ext
uses it to represent cpumask structures.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/bpf/20260706181730.21731-5-emil@etsalapatis.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
Summary: The buddy allocator requires the global BPF buddy allocator
to not be already initialized. However, the test currently merely resets
the allocator before the buddy tests instead of destroying it, and the
test worked because the buddy test happened to run first. Properly
destroy the allocator instead of resetting it.
Fixes: b1487dc1b181 ("selftests/bpf: Add selftests for libarena buddy allocator")
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Acked-by: Ihor Solodrai <ihor.solodrai@linux.dev>
Link: https://lore.kernel.org/bpf/20260706181730.21731-4-emil@etsalapatis.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
BPF can_loop based loops require the index variable to stay imprecise.
This means we must initialize them from a currently imprecise variable
instead of directly assigning 0 to them, like so:
static volatile u32 zero = 0;
for (i = zero; i < NUM_LOOPS; i++) {
/* loop body */
}
The libarena implementation of this technique is currently faulty. For
the technique to work, the variable must not be in a map. This includes
the .rodata DATASEC map used for const variables. However, libarena
still defines the zero variable as constant.
Modify the zero variable definition into a volatile variable. This
change adds a complication caused by the compiler optimizing array
derefences from
for (i = zero; i < NUM_LOOPS; i++) {
val = *(ptr + i);
}
into
for (i = zero; i < NUM_LOOPS; i++) {
val = *ptr++;
}
and causing verification failures. Use the barrier_var() clobber macro
to prevent this optimization from taking place. Using barrier_var() is
the only way to break the optimization, as annotating the index as
volatile does not suffice.
After that, remove the bpf_for() invocations introduced in libarena for
parallel spmc testing.
Reported-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/bpf/20260706181730.21731-3-emil@etsalapatis.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
The st_ (selftests_) prefix is confusing and has been replaced
with the more descriptive test_. However, last patch did not
properly move all files to the new prefix. Rename the existing
files to complete the move.
Acked-by: Ihor Solodrai <ihor.solodrai@linux.dev>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/bpf/20260706181730.21731-2-emil@etsalapatis.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
The libarena parallel spmc selftest is nondeterministic by design.
As a result it depends up to a point on the relative timing between the
producer and consumer threads. This introduces the possibility for two
kinds of spurious failures that this patch addresses.
1) Spurious timeouts. The test proceeds in phases, and threads use a
common counter as a barrier to avoid proceeding to the next phase
until all threads are ready to do so. If a thread takes too long to
reach the barrier, the already waiting threads may time out.
Increase the current timeout. The timeout's value is a balance
between the maximum amount of time spent on the test and the
possibility of spurious failures. Right now the timeout is too short.
Err on the side of caution and significantly increase it to avoid
spurious failures.
2) Spurious resize failures. Some selftests require the spmc queue to
resize itself. This in turn requires for the producer side to be
materially faster than the consumer side so that the queue gets full
enough for a resize. However, in the benchmark the spmc queue's producer
is outnumbered 3:1. To offset it we add busy waits for consume
queues. However, we still see occasional failures due to the queue
never resizing.
Minimize the possibility for this in two ways: First, remove one of
the consumers. The 2 consumers still exercise the "race between
consumers" scenario. Second, increase the busy wait duration to
decrease the rate by which the consumers act on the queue.
While at it, also replace a stray invalid error value "153" with EINVAL.
Fixes: 42998f819256 ("selftests/bpf: libarena: parallel test harness and spmc parallel selftest")
Reported-by: Jakub Kicinski <kuba@kernel.org>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260609063630.10245-1-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
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>
|
|
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 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>
|
|
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 code to directly test the output of libarena ASAN tests.
The code reuses testing infrastructure originally for BPF streams
to verify that ASAN emits call stacks when the selftests trigger
a memory error.
Since stderr() testing uses logic from test_progs, it is only
available on the test_progs-based selftest runner. The standalone
runner still uses internal ASAN state to verify access errors are
triaged as expected.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260426190338.4615-9-emil@etsalapatis.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
Introduce selftests for the buddy allocator with and without
ASAN. Add the libarena selftests both to the libarena test
runner and to test_progs, so that they are a) available when
libarena is pulled as a standalone library, and b) exercised
along with all other test programs in this directory.
ASAN for libarena requires LLVM 22. Add logic in the top-level
selftests Makefile to only compile the ASAN variant if the
compiler supports it, otherwise skip the test.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260426190338.4615-8-emil@etsalapatis.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>
|
|
The BPF selftest headers include functionality that is
specific to arenas and is required by libarena. Keep libarena
self-contained by moving all functionality into its include/
directory. Also add libarena/include to the standard include
paths for the selftests to make the moved headers easy to
access by existing selftests.
Some functionality is required by libarena but not strictly
arena-related. We still move it to the libarena/include path,
which is an upgrade from directly accessing them from the
selftests/bpf directory using relative paths.
A new bpf_may_goto.h file is split off of bpf_experimental.h.
bpf_arena_spin_lock.h and bpf_arena_common.h are moved to
libarena/include. bpf_atomic.h is also moved to libarena
because it is necessary for arena spinlocks.
For bpf_arena_spin_lock.h, mark the spinlock state array as __weak
to define the spinlock state array in the header while also
being compatible with multi-compilation unit programs. While
we're at it, we remove unnecessary definitions from existing
test programs.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://lore.kernel.org/r/20260426190338.4615-4-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>
|
