Skip to content

bpf: Support bpf rbtree traversal and list peeking

Martin KaFai Lau bpf netdev 2 versions – Applied

Status from this message: This series was applied to bpf/bpf-next.git (master)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v2 Latest8 patches 0 repliesApplied 8/8
  2. v1 RFC12 patches 14 repliesSuperseded

Changes in v2 from the cover letter

- Added tests to check that the return value of
the bpf_rbtree_{root,left,right} and bpf_list_{front,back} is marked as a non_own_ref node pointer. (Kumar)
- Added tests to ensure that the bpf_rbtree_{root,left,right} and bpf_list_{front,back} must be called after holding the spinlock.
- Squashed the selftests adjustment to the corresponding verifier changes to avoid bisect failure. (Kumar)
- Separated the bpf qdisc specific changes and fq selftest example from this set.

Patches in v2 All 8 applied

#Subject and filesSizeRepliesApplied
1/8bpf: Check KF_bpf_rbtree_add_impl for the "case KF_ARG_PTR_TO_RB_NODE"kernel/bpf/verifier.c+9 -90 repliesApplied
2/8bpf: Simplify reg0 marking for the rbtree kfuncs that return a bpf_rb_node pointerkernel/bpf/verifier.c+7 -30 repliesApplied
3/8bpf: Add bpf_rbtree_{root,left,right} kfunckernel/bpf/helpers.c kernel/bpf/verifier.c+48 -40 repliesApplied
4/8bpf: Allow refcounted bpf_rb_node used in bpf_rbtree_{remove,left,right}kernel/bpf/verifier.c tools/testing/selftests/bpf/progs/rbtree_fail.c+17 -160 repliesApplied
5/8selftests/bpf: Add tests for bpf_rbtree_{root,left,right}tools/testing/selftests/bpf/prog_tests/rbtree.c tools/testing/selftests/bpf/progs/rbtree_search.c+212 -00 repliesApplied
6/8bpf: Simplify reg0 marking for the list kfuncs that return a bpf_list_node pointerkernel/bpf/verifier.c+6 -20 repliesApplied
7/8bpf: Add bpf_list_{front,back} kfunckernel/bpf/helpers.c kernel/bpf/verifier.c+32 -20 repliesApplied
8/8selftests/bpf: Add test for bpf_list_{front,back}tools/testing/selftests/bpf/prog_tests/linked_list.c tools/testing/selftests/bpf/progs/linked_list_peek.c+119 -00 repliesApplied

Reviews trailers per patch

6 of 8 patches have a Reviewed-by or Acked-by.

PatchKumar Kartikeya Dwivedi
1/8A-b
2/8A-b
3/8A-b
4/8A-b
5/8
6/8A-b
7/8A-b
8/8

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v2 thread

Cover letter [PATCH v2 bpf-next 0/8] bpf: Support bpf rbtree traversal and list peeking

From: Martin KaFai Lau <[email protected]>

The RFC v1 [1] showed a fq qdisc implementation in bpf that is much closer to the kernel sch_fq.c.

The fq example and bpf qdisc changes are separated out from this set. This set is to focus on the kfunc and verifier changes that enable the bpf rbtree traversal and list peeking.

v2:
- Added tests to check that the return value of
the bpf_rbtree_{root,left,right} and bpf_list_{front,back} is marked as a non_own_ref node pointer. (Kumar)
- Added tests to ensure that the bpf_rbtree_{root,left,right} and bpf_list_{front,back} must be called after holding the spinlock.
- Squashed the selftests adjustment to the corresponding verifier changes to avoid bisect failure. (Kumar)
- Separated the bpf qdisc specific changes and fq selftest example from this set.

[1]: https://lore.kernel.org/bpf/[email protected]/

Martin KaFai Lau (8):
bpf: Check KF_bpf_rbtree_add_impl for the "case KF_ARG_PTR_TO_RB_NODE"
bpf: Simplify reg0 marking for the rbtree kfuncs that return a
bpf_rb_node pointer
bpf: Add bpf_rbtree_{root,left,right} kfunc
bpf: Allow refcounted bpf_rb_node used in

    bpf_rbtree_{remove,left,right}

selftests/bpf: Add tests for bpf_rbtree_{root,left,right}
bpf: Simplify reg0 marking for the list kfuncs that return a
bpf_list_node pointer
bpf: Add bpf_list_{front,back} kfunc selftests/bpf: Add test for bpf_list_{front,back}

 kernel/bpf/helpers.c                          |  52 +++++
 kernel/bpf/verifier.c                         |  64 ++++--
 .../selftests/bpf/prog_tests/linked_list.c    |   6 +
 .../testing/selftests/bpf/prog_tests/rbtree.c |   6 +
 .../selftests/bpf/progs/linked_list_peek.c    | 113 ++++++++++
 .../testing/selftests/bpf/progs/rbtree_fail.c |  29 +--
 .../selftests/bpf/progs/rbtree_search.c       | 206 ++++++++++++++++++
 7 files changed, 445 insertions(+), 31 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/linked_list_peek.c
 create mode 100644 tools/testing/selftests/bpf/progs/rbtree_search.c
Signature · 1 line
2.47.1