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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 7 potential issue(s) to consider:
- [High] Missing acquire memory barrier in `lvq_steal` allows speculative execution to read stale or uninitialized queue elements.
- [High] `lvq_destroy` unconditionally calls `free()` on NULL pointers, which corrupts the selftest memory allocator state.
- [High] The use of the test-specific `can_loop` macro in library data structure logic risks silent data loss and incomplete initialization.
- [Medium] Implicit signed-to-unsigned type promotion in deque resize logic could trigger erroneous array expansions.
- [Medium] The commit message incorrectly documents the data structure's push/pop semantics.
- [Low] Pointer arithmetic is performed on a potentially NULL pointer in `lvq_order_init`.
- [Low] Memory leaks in selftest error paths upon assertion failures.
--

commit c550e5013d289b25ae7b41bfdffc6d59d1302758
Author: Emil Tsalapatis <emil@etsalapatis.com>

selftests/bpf: libarena: Add Lev-Chase queue data structure
    
Expand libarena with a Lev-Chase deque data structure. This is a single
producer, multiple consumer lockless queue that permits efficient
work stealing.

> 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.

The code appears to implement standard Chase-Lev deque semantics where the
owner operates at the bottom and stealers operate at the top.

Is the push and pop direction described in the commit message accurate?

> diff --git a/tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c
> new file mode 100644
> index 0000000000000..d53416d22f0a5
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c
[ ... ]
> @@ -0,0 +1,194 @@
> +SEC("syscall")
> +int test_lvqueue_steal_one(void)
> +{
> +	u64 val, newval;
> +	int ret, i;
> +
> +	lv_queue_t *lvq = lvq_create();
> +
> +	if (!lvq)
> +		return 1;
> +
> +	for (i = 0; i < 10 && can_loop; i++) {
> +		val = i;
> +
> +		ret = lvq_owner_push(lvq, val);
> +		if (ret)
> +			return 1;

Does this error path leak the queue's arena memory by returning without
calling lvq_destroy(lvq)?

[ ... ]
> diff --git a/tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c b/tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c
> new file mode 100644
> index 0000000000000..b93c4f9d1c929
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c
[ ... ]
> @@ -0,0 +1,241 @@
> +static inline
> +void lv_arr_copy(lv_arr_t *dst, lv_arr_t *src, u64 b, u64 t)
> +{
> +	u64 i;
> +
> +	for (i = t; i < b && can_loop; i++)
> +		lv_arr_put(dst, i, lv_arr_get(src, i));
> +}

If the instruction budget is exhausted during a queue resize, the loop will
terminate prematurely.

The caller lvq_owner_push() will then accept the partially copied array and
replace the active queue, permanently dropping the uncopied elements without
returning an error.

Can the use of the test-specific can_loop macro here cause silent data loss?

> +static inline
> +int lvq_order_init(lv_queue_t *lvq __arg_arena, int order)
> +{
> +	lv_arr_t *arr = &lvq->arr[order];
> +
> +	if (unlikely(!lvq))
> +		return -EINVAL;

Compilers might deduce that lvq cannot be NULL after pointer arithmetic and
optimize away the subsequent if (!lvq) check entirely.

Does performing pointer arithmetic (&lvq->arr[order]) before checking if
lvq is NULL result in undefined behavior?

[ ... ]
> +__weak
> +int lvq_owner_push(lv_queue_t *lvq __arg_arena, u64 val)
> +{
[ ... ]
> +	sz = b - t;
> +	if (sz >= lv_arr_size(arr) - 1) {

Here sz is ssize_t (signed), but lv_arr_size() returns a u64 (unsigned).
C type promotion rules will implicitly convert sz to an unsigned 64-bit
integer.

If sz is ever negative, the unsigned promotion transforms it into a massive
positive value, erroneously evaluating as greater than the array size.

Can this logic trigger an erroneous array expansion?

[ ... ]
> +__weak
> +int lvq_steal(lv_queue_t *lvq __arg_arena, u64 *val)
> +{
[ ... ]
> +	b = READ_ONCE(lvq->bottom);
> +	arr = READ_ONCE(lvq->cur);
> +
> +	sz = b - t;
> +	if (sz <= 0)
> +		return -ENOENT;
> +
> +	value = lv_arr_get(arr, t);

READ_ONCE() does not provide an acquire barrier, and control dependencies
(like if (sz <= 0)) do not order read-to-read operations.

If a concurrent push occurs, the stealer could speculatively load the array
element before loading the updated bottom index.

Does reading lvq->bottom with READ_ONCE() allow speculative execution to
read stale or uninitialized queue elements on weakly-ordered architectures?
Should lvq->bottom be read using smp_load_acquire() instead?

[ ... ]
> +__weak
> +u64 lvq_create_internal(void)
> +{
[ ... ]
> +	for (i = 0; i < LV_ARR_ORDERS && can_loop; i++) {
> +		lvq->arr[i].data = NULL;
> +		lvq->arr[i].order = i;
> +	}

Can an early termination of this loop due to can_loop leave array pointers
uninitialized, leading to undefined behavior later?

[ ... ]
> +__weak
> +int lvq_destroy(lv_queue_t *lvq __arg_arena)
> +{
> +	int i;
> +
> +	if (unlikely(!lvq))
> +		return -EINVAL;
> +
> +	for (i = 0; i < LV_ARR_ORDERS && can_loop; i++)
> +		free(lvq->arr[i].data);

The selftest free() implementation in mm.h does not check for NULL pointers
and unconditionally decrements malloc_count:

MALLOC_VISIBLE void free(void *where)
{
    malloc_count--;
    if (!malloc_count)
        malloc_ptr = free_mem_ptr;
}

Since arrays are allocated lazily, higher-order array pointers will be NULL.
Calling free() on these unallocated slots will drive malloc_count negative
and permanently prevent the allocator from resetting the memory arena.

Can calling free() unconditionally on potentially NULL pointers corrupt the
selftest memory allocator state?

> +
> +	free(lvq);
> +
> +	return 0;
> +}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260511210740.5395-1-emil@etsalapatis.com?part=2