Re: [RESEND 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 3 potential issue(s) to consider:
- [High] Use of undefined `malloc()` and `free()` instead of `arena_malloc()` and `arena_free()`
- [High] Missing acquire memory barrier when reading `lvq->bottom` in `lvq_steal()` leads to stealing uninitialized data
- [High] Early loop termination via `can_loop` causes silent data corruption and wild pointer frees
--

commit f362e0549cb75d0f854b07e362d4f47abea9daf9
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. The structure is lock-free and wait-free to minimize
overhead.

> 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
[ ... ]
> +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++)

If can_loop breaks early, won't this array expansion silently abort without
copying all queue items?

lvq_owner_push() doesn't seem to have error handling for this, which might
lead to published, partially empty arrays and permanent queue data loss.

> +		lv_arr_put(dst, i, lv_arr_get(src, i));
> +}
> +
> +static inline
> +int lvq_order_init(lv_queue_t *lvq __arg_arena, int order)
> +{
[ ... ]
> +	arr->data = (u64 __arena *)malloc((LV_ARR_BASESZ << order) * sizeof(*arr->data));

Should this be arena_malloc() instead?

Standard C library functions are typically not available during BPF target
compilation, which could cause build or linker errors due to undefined
symbols.

> +	if (!arr->data)
> +		return -ENOMEM;
> +
> +	return 0;
> +}
[ ... ]
> +__weak
> +int lvq_steal(lv_queue_t *lvq __arg_arena, u64 *val)
> +{
> +	volatile u64 b, t;
> +	lv_arr_t *arr;
> +	ssize_t sz;
> +	u64 value;
> +
> +	if (unlikely(!lvq || !val))
> +		return -EINVAL;
> +
> +	t = smp_load_acquire(&lvq->top);
> +
> +	/*
> +	 * It is important that t is read before b for
> +	 * stealers to avoid racing with the owner.
> +	 * Races between stealers are dealt with using
> +	 * CAS to increment the top value below.
> +	 */
> +	smp_rmb();
> +
> +	b = READ_ONCE(lvq->bottom);

Could reading lvq->bottom without smp_load_acquire() (or a following
smp_rmb()) cause the stealer to read uninitialized data?

In lvq_owner_push(), the array is updated before lvq->bottom is updated
via smp_store_release(). On weakly ordered CPUs like ARM64, the control
dependency (sz <= 0) below does not guarantee read-to-read ordering.

Could the CPU speculatively execute lv_arr_get(arr, t) before fetching the
updated lvq->bottom, resulting in a successful steal of garbage data?

> +	arr = READ_ONCE(lvq->cur);
> +
> +	sz = b - t;
> +	if (sz <= 0)
> +		return -ENOENT;
> +
> +	value = lv_arr_get(arr, t);
[ ... ]
> +__weak
> +u64 lvq_create_internal(void)
> +{
> +	/*
> +	 * Marked as volatile because otherwise the array
> +	 * reference in the internal loop gets demoted to
> +	 * scalar and the program fails verification.
> +	 */
> +	volatile lv_queue_t *lvq;
> +	int ret, i;
> +
> +	lvq = malloc(sizeof(*lvq));

Is it possible this should be arena_malloc() as well?

> +	if (!lvq)
> +		return (u64)NULL;
> +
> +	WRITE_ONCE(lvq->bottom, 0);
> +	WRITE_ONCE(lvq->top, 0);
> +
> +	for (i = 0; i < LV_ARR_ORDERS && can_loop; i++) {

If this initialization loop terminates early due to can_loop, will the
remaining lvq->arr[i].data pointers retain uninitialized memory from the
allocation?

If so, could the subsequent iteration in lvq_destroy() call free() on those
wild pointers, causing memory corruption?

> +		lvq->arr[i].data = NULL;
> +		lvq->arr[i].order = i;
> +	}
[ ... ]
> +__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);

Should these be arena_free() calls?

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

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