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

[Changwoo Min]

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*'

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.

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