[PATCH bpf-next 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).
- 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 (2/3).
- Add rb_next(), so that a consumer can walk past tasks it cannot run
  in key order (3/3).

Each patch adds selftests, which run with:

  $> ./test_progs -t 'libarena/test_rbtree*'

Changwoo Min (3):
  selftests/bpf: libarena: Order equal rbtree keys FIFO
  selftests/bpf: libarena: Cache the rbtree's leftmost node and count
  selftests/bpf: libarena: Add rb_next()

 .../bpf/libarena/include/libarena/rbtree.h    |  82 ++++-
 .../bpf/libarena/selftests/test_rbtree.bpf.c  | 300 ++++++++++++++++++
 .../selftests/bpf/libarena/src/rbtree.bpf.c   | 138 ++++++--
 3 files changed, 493 insertions(+), 27 deletions(-)


base-commit: 4169c9c90532df9585c0a2ae513337a58f5e59ab
-- 
2.56.0