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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <20250506015857.817950-1-martin.lau@linux.dev>
Date: Mon,  5 May 2025 18:58:47 -0700
From: Martin KaFai Lau <martin.lau@...ux.dev>
To: bpf@...r.kernel.org
Cc: 'Alexei Starovoitov ' <ast@...nel.org>,
	'Andrii Nakryiko ' <andrii@...nel.org>,
	'Daniel Borkmann ' <daniel@...earbox.net>,
	'Kumar Kartikeya Dwivedi ' <memxor@...il.com>,
	'Amery Hung ' <ameryhung@...il.com>,
	netdev@...r.kernel.org,
	kernel-team@...a.com
Subject: [PATCH v2 bpf-next 0/8] bpf: Support bpf rbtree traversal and list peeking

From: Martin KaFai Lau <martin.lau@...nel.org>

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/20250418224652.105998-1-martin.lau@linux.dev/

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

-- 
2.47.1