[RFC PATCH bpf-next 00/12] bpf: A fq example similar to the kernel sch_fq.c implementation

[Martin KaFai Lau <martin.lau@linux.dev>]

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

This patch is to show a fq implementation closer to the
sch_fq.c and how it can be done in bpf.

The first part of the set adds a few rbtree and list
traverse kfuncs.

The second part adds a bpf qdisc specific kfunc and then
a new bpf_sch_fq.c implementation in the selftest.

The second part of the set depends on the bpf qdisc changes in
the bpf-next/net. If bpf change is viable, it will be easier to
merge the first part of the set with the bpf specific changes
to the bpf-next/master first. The second part depending on the
bpf qdisc piece can wait for the next cycle.

A few more bpf tests are still needed and a few things
may still need to clean up in the bpf_sch_fq.c, so in RFC.

Martin KaFai Lau (12):
  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
  selftests/bpf: Adjust failure message in the rbtree_fail test
  bpf: Allow refcounted bpf_rb_node used in
    bpf_rbtree_{remove,left,right}
  selftests/bpf: Adjust test that does not allow refcounted node in
    rbtree_remove
  selftests/bpf: Add rbtree_search test
  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}
  bpf: net: Add a qdisc kfunc to set sk_pacing_status.
  selftests/bpf: A bpf fq implementation similar to the kernel sch_fq

 kernel/bpf/helpers.c                          |   52 +
 kernel/bpf/verifier.c                         |   65 +-
 net/sched/bpf_qdisc.c                         |   14 +
 .../selftests/bpf/prog_tests/bpf_qdisc.c      |   21 +
 .../selftests/bpf/prog_tests/linked_list.c    |    2 +
 .../testing/selftests/bpf/prog_tests/rbtree.c |    6 +
 .../selftests/bpf/progs/bpf_qdisc_common.h    |   97 +-
 .../selftests/bpf/progs/bpf_qdisc_fq.c        |    2 -
 .../testing/selftests/bpf/progs/bpf_sch_fq.c  | 1171 +++++++++++++++++
 .../selftests/bpf/progs/bpf_tracing_net.h     |    1 +
 .../selftests/bpf/progs/linked_list_peek.c    |  104 ++
 .../testing/selftests/bpf/progs/rbtree_fail.c |   26 +-
 .../selftests/bpf/progs/rbtree_search.c       |  137 ++
 13 files changed, 1665 insertions(+), 33 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_sch_fq.c
 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