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

["Emil Tsalapatis" <emil@etsalapatis.com>]

On Mon May 11, 2026 at 6:12 PM EDT, bot+bpf-ci wrote:
>> 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:
>>
>> 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 API names in the commit message don't match the actual functions.
> Looking at tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h:
>
>     int lvq_owner_push(lv_queue_t *lvq, u64 val);
>     int lvq_owner_pop(lv_queue_t *lvq, u64 *val);
>     int lvq_steal(lv_queue_t *lvq, u64 *val);
>
> The functions use 'lvq_' prefix, not 'lvqueue_'.
>
> Also, the commit message describes push/pop as operating on the 'top' and
> steal as operating on the 'bottom', while the code follows the standard
> Chase-Lev convention where the owner operates at 'bottom' and stealers at
> 'top'. In lvq_owner_push():
>
>     b = smp_load_acquire(&lvq->bottom);
>     ...
>     lv_arr_put(lvq->cur, b, val);
>     smp_store_release(&lvq->bottom, b + 1);
>
> And in lvq_steal():
>
>     t = smp_load_acquire(&lvq->top);
>     ...
>     if (cmpxchg(&lvq->top, t, t + 1) != t)
>
> Could the commit message use the correct API names and clarify the
> terminology to match the variable names in the code?

Ack, will clean up.

>
> [ ... ]
>
>> 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 000000000000..b93c4f9d1c92
>> --- /dev/null
>> +++ b/tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c
>> @@ -0,0 +1,241 @@
>
> [ ... ]
>
>> +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;
>> +
>> +	if (order >= LV_ARR_ORDERS)
>> +		return -E2BIG;
>
> The pointer 'arr' is computed from '&lvq->arr[order]' before both the NULL
> check and the bounds check. Although this pointer is never dereferenced on
> the failure paths, forming a pointer more than one past the end of an array
> is undefined behavior per C17 6.5.6p8.
>
> This can occur when lvq_owner_push() calls lvq_order_init(lvq, arr->order + 1)
> with arr->order + 1 == LV_ARR_ORDERS.
>
> Since this function is marked '__arg_arena' and invoked by BPF programs, the
> verifier may reject the out-of-bounds pointer arithmetic. Should the 'arr'
> assignment be moved after both checks?
>

Will move the pointer calculation to its proper place, thought the bit
about verifier failures is completely extrapolated - this is an arena,
of course we can do any pointer arithmetic we like.

> [ ... ]
>
>
> ---
> AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
> See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
>
> CI run summary: https://github.com/kernel-patches/bpf/actions/runs/25699461713