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

From: Emil Tsalapatis

Date: Thu Nov 12 2026 - 02:06:18 EST


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@xxxxxxxxxxxxxxx>

(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@xxxxxxxxxx/
> v1: https://lore.kernel.org/bpf/20261028060046.549097-1-changwoo@xxxxxxxxxx/
>
> 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