Re: [PATCH bpf-next v3 0/3] selftests/bpf: libarena: Add ordered-walk and lockless-peek support to the rbtree

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

On Wed Nov 11, 2026 at 10:09 AM UTC, Changwoo Min wrote:
> A sched_ext scheduler can build a task queue on libarena's rbtree, keyed
> by vtime, in place of a vtime-ordered DSQ. Such a queue needs three things
> the tree lacks. This series adds them:
>
> - Serve equal keys in insertion order, as vtime-ordered DSQs do (1/3).
> - Add rb_next(), so that a consumer can walk past tasks it cannot run
>   in key order (2/3).
> - Cache the leftmost node and the node count, so that other CPUs can
>   peek at the head and the length without the writer's lock, like
>   scx_bpf_dsq_peek() and scx_bpf_dsq_nr_queued(). Add rb_init() and
>   rb_fini() for a tree embedded in another object (3/3).
>
> Each patch adds selftests, which run with:
>
>   $> ./test_progs -t 'libarena/test_rbtree*'

Hi Changwoo,

feel free to keep my:

Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>

(though I didn't add them myself to v1's patches 2 and 3,
I assume transcription error?)

>
> Changes in v3:
> - Make the lockless readers static inline. A plain static function in
>   a header fails -Wunused-function under -Werror in a file that does
>   not call it (bot+bpf-ci, 3/3).
>
> Changes in v2:
> - Drop the comment on the insert helper and keep the name
>   rbnode_least_upper_bound() (Emil, 1/3).
> - Move rb_next() before the caching patch and into rbtree.bpf.c with the
>   other traversal functions (Alexei, Emil, 2/3).
> - Hand the head to its successor at the top of rb_node_remove(), before
>   an RB_ALLOC tree frees the node, so that a lockless reader never sees a
>   freed head. This drops the wrapper, was_first and the rename to
>   rbnode_remove() (Alexei, 3/3).
> - Drop the cache line alignment of the lockless fields, which showed no
>   measurable benefit (Alexei, 3/3).
> - Rename the lockless readers to rb_first_lockless(),
>   rb_first_key_lockless() and rb_nr_nodes_lockless(), and document that
>   a caller that dereferences the head must keep the node valid itself
>   (Emil, 3/3).
> - Drop __always_inline from static functions (Emil, 3/3).
> - Add Reviewed-by tags from Alexei and Emil.
> - Rebase on bpf-next.
>
> v2: https://lore.kernel.org/bpf/20261111073416.203153-1-changwoo@igalia.com/
> v1: https://lore.kernel.org/bpf/20261028060046.549097-1-changwoo@igalia.com/
>
> Changwoo Min (3):
>   selftests/bpf: libarena: Order equal rbtree keys FIFO
>   selftests/bpf: libarena: Add rb_next()
>   selftests/bpf: libarena: Cache the rbtree's leftmost node and count
>
>  .../bpf/libarena/include/libarena/rbtree.h    |  57 +++-
>  .../bpf/libarena/selftests/test_rbtree.bpf.c  | 303 ++++++++++++++++++
>  .../selftests/bpf/libarena/src/rbtree.bpf.c   | 120 +++++--
>  3 files changed, 457 insertions(+), 23 deletions(-)
>
>
> base-commit: 0fb18ce8a2e9de830433923cf65838933d615359