net_sched: introduce eBPF based Qdisc
Subsystems (5)
RFC PATCH v2 1/1 net_sched: introduce eBPF based Qdisc
From: Cong Wang <[email protected]>
This *incomplete* patch introduces a programmable Qdisc with eBPF. The goal is to make this Qdisc as programmable as possible, that is, to replace as many existing Qdisc's as we can, no matter in tree or out of tree. And we want to make programmer's and researcher's life as easy as possible, so that they don't have to write a complete Qdisc kernel module just to experiment some queuing theory.
The design was discussed during last LPC:
https://linuxplumbersconf.org/event/7/contributions/679/attachments/520/1188/sch_bpf.pdf
Here is a summary of design decisions I made:
1. Avoid eBPF struct_ops, as it would be really hard to program a Qdisc with this approach, literally all the struct Qdisc_ops and struct Qdisc_class_ops are needed to implement. This is almost as hard as programming a Qdisc kernel module.
2. Avoid exposing skb's to user-space, which means we don't introduce a map to store skb's. Instead, store them in kernel without exposure to user-space. There are three different reasons behind this:
2a) User-space does not need to read skb, there is no use case to let user-space make decisions, so far.
2b) Kernel would lose the visibility of the "queues", as maps are only shared between eBPF programs and user-space. These queues still have to interact with the kernel, for example, kernel wants to reset all queues when we reset the network interface, kernel wants to adjust number of queues if they are mapped to hardware queues.
2c) It is harder to interact with existing TC infra. See below.
3. Integrate with existing TC infra. For example, if the user doesn't want to implement her own filters (e.g. a flow dissector), she should be able to re-use the existing TC filters. And each queue can be easily mapped to a TC class and dump its stats easily via netlink. Users can use this Qdisc together with any other Qdisc's too, pretty much like a regular Qdisc.
So I choose to use priority queues to store skb's inside a flow and to store flows inside a Qdisc, and let eBPF programs decide the *relative* position of the skb within the flow and the *relative* order of the flows too, upon each enqueue and dequeue. Each flow is also exposed to user as a TC class, like many other classful Qdisc's.
Although the biggest limitation is obviously that users can not traverse the packets or flows inside the Qdisc, I think at least they could store those global information of interest inside their own hashmap.
Any high-level feedbacks are welcome. Please do not review any coding details until RFC tag is removed.
TODO:
1. actually test it
2. write a document for this Qdisc
3. add test cases and sample code
---
v2: Rebase on latest net-next
Make the code more complete (but still incomplete)
include/linux/bpf_types.h | 2 + include/linux/priority_queue.h | 90 ++++++ include/linux/skbuff.h | 2 + include/uapi/linux/bpf.h | 20 ++ include/uapi/linux/pkt_sched.h | 15 + net/sched/Kconfig | 15 + net/sched/Makefile | 1 + net/sched/sch_bpf.c | 609 +++++++++++++++++++++++++++++++++++++++++ 8 files changed, 754 insertions(+)
include/linux/bpf_types.h +2 -0
@@ -8,6 +8,8 @@ BPF_PROG_TYPE(BPF_PROG_TYPE_SCHED_CLS, tc_cls_act, struct __sk_buff, struct sk_buff) BPF_PROG_TYPE(BPF_PROG_TYPE_SCHED_ACT, tc_cls_act, struct __sk_buff, struct sk_buff) +BPF_PROG_TYPE(BPF_PROG_TYPE_SCHED_QDISC, tc_cls_act, + struct __sk_buff, struct sk_buff) BPF_PROG_TYPE(BPF_PROG_TYPE_XDP, xdp, struct xdp_md, struct xdp_buff)#ifdef CONFIG_CGROUP_BPF
include/linux/priority_queue.h new file +90 -0
90 lines not on this page · raw message
include/linux/skbuff.h +2 -0
@@ -36,6 +36,7 @@#include <linux/splice.h> #include <linux/in6.h> #include <linux/if_packet.h> +#include <linux/priority_queue.h> #include <net/flow.h> #include <net/page_pool.h> #if IS_ENABLED (CONFIG_NF_CONNTRACK )
@@ -735,6 +736,7 @@ struct sk_buff { }; };struct rb_node rbnode;/* used in netem, ip4 defrag, and tcp stack */ +struct pq_node pqnode;/* used in ebpf qdisc */ struct list_head list; };
include/uapi/linux/bpf.h +20 -0
@@ -949,6 +949,7 @@ enum bpf_prog_type {BPF_PROG_TYPE_LSM ,BPF_PROG_TYPE_SK_LOOKUP ,BPF_PROG_TYPE_SYSCALL ,/* a program that can execute syscalls */ + BPF_PROG_TYPE_SCHED_QDISC, }; enum bpf_attach_type {
@@ -6260,4 +6261,23 @@ enum { BTF_F_ZERO = (1ULL << 3), }; +struct sch_bpf_ctx { +/* Input */ +struct __sk_buff *skb; +__u32 nr_flows; +__u32 handle; + +/* Output */ +__u64 rank; +__u64 delay; +__u32 classid; +}; + +enum { +SCH_BPF_OK , +SCH_BPF_REQUEUE , +SCH_BPF_DROP , +SCH_BPF_THROTTLE , +}; +#endif /* _UAPI__LINUX_BPF_H__ */
include/uapi/linux/pkt_sched.h +15 -0
@@ -1263,4 +1263,19 @@ enum {#define TCA_ETS_MAX (__TCA_ETS_MAX - 1) +enum { +TCA_SCH_BPF_UNSPEC , +TCA_SCH_BPF_ENQUEUE_PROG_NAME ,/* string */ +TCA_SCH_BPF_ENQUEUE_PROG_FD ,/* u32 */ +TCA_SCH_BPF_ENQUEUE_PROG_ID ,/* u32 */ +TCA_SCH_BPF_ENQUEUE_PROG_TAG ,/* data */ +TCA_SCH_BPF_DEQUEUE_PROG_NAME ,/* string */ +TCA_SCH_BPF_DEQUEUE_PROG_FD ,/* u32 */ +TCA_SCH_BPF_DEQUEUE_PROG_ID ,/* u32 */ +TCA_SCH_BPF_DEQUEUE_PROG_TAG ,/* data */ + __TCA_SCH_BPF_MAX, +}; + +#define TCA_SCH_BPF_MAX (__TCA_SCH_BPF_MAX - 1) +#endif
net/sched/Kconfig +15 -0
@@ -439,6 +439,21 @@ config NET_SCH_ETS If unsure, say N. +config NET_SCH_BPF + tristate "eBPF based programmable queue discipline" + help + This eBPF based queue discipline offers a way to program your + own packet scheduling algorithm. This is a classful qdisc which + also allows you to decide the hierarchy. + + Say Y here if you want to use the eBPF based programmable queue + discipline. + + To compile this driver as a module, choose M here: the module + will be called sch_bpf. + + If unsure, say N. + menuconfig NET_SCH_DEFAULT bool "Allow override default queue discipline" help
net/sched/Makefile +1 -0
@@ -65,6 +65,7 @@ obj-$(CONFIG_NET_SCH_FQ_PIE) += sch_fq_pie.o obj-$(CONFIG_NET_SCH_CBS) += sch_cbs.o obj-$(CONFIG_NET_SCH_ETF) += sch_etf.o obj-$(CONFIG_NET_SCH_TAPRIO) += sch_taprio.o +obj-$(CONFIG_NET_SCH_BPF) += sch_bpf.o obj-$(CONFIG_NET_CLS_U32) += cls_u32.o obj-$(CONFIG_NET_CLS_ROUTE4) += cls_route.o
net/sched/sch_bpf.c new file +609 -0
609 lines not on this page · raw message
kernel test robot
build botreproduce (this is a W=1 build): wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross # install riscv cross compiling tool for…
Hi Cong,
[FYI, it's a private test report for your RFC patch.] [auto build test ERROR on net-next/master]
url: https://github.com/0day-ci/linux/commits/Cong-Wang/net_sched-introduce-eBPF-based-Qdisc/20210914-072015 base: https://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git 13bb8429ca985497bfba3a4afa6cd470d15fed10 config: riscv-buildonly-randconfig-r003-20210913 (attached as .config) compiler: clang version 14.0.0 (https://github.com/llvm/llvm-project 261cbe98c38f8c1ee1a482fe76511110e790f58a)
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# install riscv cross compiling tool for clang build
# apt-get install binutils-riscv64-linux-gnu
# https://github.com/0day-ci/linux/commit/11b7d639a3edc1182a3027ae62cc35dcf0924178
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Cong-Wang/net_sched-introduce-eBPF-based-Qdisc/20210914-072015 git checkout 11b7d639a3edc1182a3027ae62cc35dcf0924178
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross ARCH=riscv
If you fix the issue, kindly add following tag as appropriate
All errors (new ones prefixed by >>):
>> kernel/bpf/btf.c:4422:2: error: initializer overrides prior initialization of this subobject [-Werror,-Winitializer-overrides]
0, /* avoid empty array */
^
include/linux/bpf_types.h:11:1: note: previous initialization is here
BPF_PROG_TYPE(BPF_PROG_TYPE_SCHED_QDISC, tc_cls_act,
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kernel/bpf/btf.c:4419:10: note: expanded from macro 'BPF_PROG_TYPE'
[_id] = __ctx_convert##_id,
^~~~~~~~~~~~~~~~~~ <scratch space>:151:1: note: expanded from here __ctx_convertBPF_PROG_TYPE_SCHED_QDISC ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1 error generated.
vim +4422 kernel/bpf/btf.c
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4396
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4397 #define BPF_MAP_TYPE(_id, _ops)
f2e10bff16a0fd Andrii Nakryiko 2020-04-28 4398 #define BPF_LINK_TYPE(_id, _name)
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4399 static union {
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4400 struct bpf_ctx_convert {
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4401 #define BPF_PROG_TYPE(_id, _name, prog_ctx_type, kern_ctx_type) \
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4402 prog_ctx_type _id##_prog; \
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4403 kern_ctx_type _id##_kern;
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4404 #include <linux/bpf_types.h>
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4405 #undef BPF_PROG_TYPE
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4406 } *__t;
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4407 /* 't' is written once under lock. Read many times. */
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4408 const struct btf_type *t;
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4409 } bpf_ctx_convert;
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4410 enum {
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4411 #define BPF_PROG_TYPE(_id, _name, prog_ctx_type, kern_ctx_type) \
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4412 __ctx_convert##_id,
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4413 #include <linux/bpf_types.h>
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4414 #undef BPF_PROG_TYPE
ce27709b8162e5 Alexei Starovoitov 2019-11-27 4415 __ctx_convert_unused, /* to avoid empty enum in extreme .config */
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4416 };
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4417 static u8 bpf_ctx_convert_map[] = {
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4418 #define BPF_PROG_TYPE(_id, _name, prog_ctx_type, kern_ctx_type) \
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4419 [_id] = __ctx_convert##_id,
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4420 #include <linux/bpf_types.h>
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4421 #undef BPF_PROG_TYPE
4c80c7bc583a87 Arnd Bergmann 2019-12-10 @4422 0, /* avoid empty array */
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4423 };
91cc1a99740e2e Alexei Starovoitov 2019-11-14 4424 #undef BPF_MAP_TYPE
f2e10bff16a0fd Andrii Nakryiko 2020-04-28 4425 #undef BPF_LINK_TYPE91cc1a99740e2e Alexei Starovoitov 2019-11-14 4426
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
Quoted 3 lines · Cong Wang
---
v2: Rebase on latest net-next
Make the code more complete (but still incomplete)
What is the point of v2 when feedback on the first RFC was ignored?
Quoted 7 lines · Alexei Starovoitov
Quoted 3 lines · Cong Wang
---
v2: Rebase on latest net-next
Make the code more complete (but still incomplete)What is the point of v2 when feedback on the first RFC was ignored?
They are not ignored for two reasons:
1) I responded to those reasonable ones in the original thread. Clearly you missed them.
2) I also responded in changelog, please check the difference, clearly V2 is much more lengthy than V1.
It becomes clear you ignored mine (either email or changelog), not vice versa.
Please lead by examples, you are not actually following anything you ask others to do. Remember the last time I asked you to expand your changelog for bpf timer? You kept ignoring it. ;)
Thanks.
Quoted 9 lines · Cong Wang
Quoted 6 lines · Alexei Starovoitov
Quoted 3 lines · Cong Wang
---
v2: Rebase on latest net-next
Make the code more complete (but still incomplete)
Quoted 6 lines
Quoted 1 line
What is the point of v2 when feedback on the first RFC was ignored?
They are not ignored for two reasons:
1) I responded to those reasonable ones in the original thread. Clearly you missed them.
Multiple people in the v1 thread made it clear that the approach presented in v1 is not generic enough. v2 made no attempt to address these concerns.
Quoted 13 lines · Alexei Starovoitov
Quoted 11 lines · Cong Wang
Quoted 7 lines · Alexei Starovoitov
Quoted 3 lines · Cong Wang
---
v2: Rebase on latest net-next
Make the code more complete (but still incomplete)What is the point of v2 when feedback on the first RFC was ignored?
Quoted 8 lines
Quoted 4 lines
They are not ignored for two reasons:
1) I responded to those reasonable ones in the original thread. Clearly you missed them.
Multiple people in the v1 thread made it clear that the approach presented in v1 is not generic enough. v2 made no attempt to address these concerns.
It looks like you just missed the first part:
"This *incomplete* patch introduces a programmable Qdisc with eBPF. The goal is to make this Qdisc as programmable as possible, that is, to replace as many existing Qdisc's as we can, no matter in tree or out of tree. And we want to make programmer's and researcher's life as easy as possible, so that they don't have to write a complete Qdisc kernel module just to experiment some queuing theory."
If you compare it with V1, V2 explains the use case in more details, which is to target Qdisc writers, not any other. Therefore, the argument of making it out of Qdisc is non-sense, anything outside of Qdisc is not even my target. Of course you can do anything in XDP, but it has absolutely nothing with my goal here: Qdisc.
I also addressed the skb map concern:
" 2b) Kernel would lose the visibility of the "queues", as maps are only
shared between eBPF programs and user-space. These queues still have to interact with the kernel, for example, kernel wants to reset all queues when we reset the network interface, kernel wants to adjust number of queues if they are mapped to hardware queues."
More than writing, I even tried to write a skb map by myself, I don't see it fits into my goal at all. Therefore, the only thing I can do is just to expand my changelog to explain why.
Thanks.
Quoted 7 lines · Cong Wang
"This *incomplete* patch introduces a programmable Qdisc with eBPF. The goal is to make this Qdisc as programmable as possible, that is, to replace as many existing Qdisc's as we can, no matter in tree or out of tree. And we want to make programmer's and researcher's life as easy as possible, so that they don't have to write a complete Qdisc kernel module just to experiment some queuing theory."
The inspiration was clear and obvious.
Folks in the thread had the same idea long before your patches came out. But it doesn't matter who came up with an idea to implement qdisc in bpf first. Everyone in the thread agreed that such a feature would be great to have. The point people explicitly highlighted is that qdisc is not only about skbs. The queuing concepts (fq, codel, etc) are useful in xdp and non networking contexts too.
That's why approaching the goal with more generic ambitions was requested.
Quoted 5 lines
If you compare it with V1, V2 explains the use case in more details, which is to target Qdisc writers, not any other. Therefore, the argument of making it out of Qdisc is non-sense, anything outside of Qdisc is not even my target. Of course you can do anything in XDP, but it has absolutely nothing with my goal here: Qdisc.
Applying queuing discipline to non-skb context may be not your target but it's a reasonable and practical request to have. The kernel is not about solving one person's itch. The kernel has to be optimized for all use cases.
Quoted 10 lines
I also addressed the skb map concern:
" 2b) Kernel would lose the visibility of the "queues", as maps are only
shared between eBPF programs and user-space. These queues still have to interact with the kernel, for example, kernel wants to reset all queues when we reset the network interface, kernel wants to adjust number of queues if they are mapped to hardware queues."More than writing, I even tried to write a skb map by myself,
Cool and it sounds that you've failed to do so?
At the same time Toke mentioned that he has a prototype of suck skb map. What addition data can open your mind that skb/packet map is more universal building block for queuing discipline in different layers?
Quoted 1 line · Alexei Starovoitov
At the same time Toke mentioned that he has a prototype of suck skb map.
This is such an embarrassing typo :) Sorry Toke. s/suck/such/ in above.
Quoted 5 lines · Alexei Starovoitov
Quoted 1 line · Alexei Starovoitov
At the same time Toke mentioned that he has a prototype of suck skb map.
This is such an embarrassing typo :) Sorry Toke. s/suck/such/ in above.
Haha, managed to completely miss this; no worries, though, gave me a good chuckle :)
-Toke
Quoted 10 lines · Alexei Starovoitov
Quoted 7 lines · Cong Wang
"This *incomplete* patch introduces a programmable Qdisc with eBPF. The goal is to make this Qdisc as programmable as possible, that is, to replace as many existing Qdisc's as we can, no matter in tree or out of tree. And we want to make programmer's and researcher's life as easy as possible, so that they don't have to write a complete Qdisc kernel module just to experiment some queuing theory."
Quoted 8 lines
The inspiration was clear and obvious.
Folks in the thread had the same idea long before your patches came out. But it doesn't matter who came up with an idea to implement qdisc in bpf first. Everyone in the thread agreed that such a feature would be great to have. The point people explicitly highlighted is that qdisc is not only about skbs. The queuing concepts (fq, codel, etc) are useful in xdp and non networking contexts too.
That's why approaching the goal with more generic ambitions was requested.
This goal has nothing to do with my goal, I am pretty sure we have a lot of queues in networking, here I am only interested in Qdisc for sure. If you need queues in any other place, it is your job, not mine.
More importantly, what's the conflict between these two goals here? I see none, from your response, it implies we could only have one.
Quoted 9 lines
Quoted 6 lines
If you compare it with V1, V2 explains the use case in more details, which is to target Qdisc writers, not any other. Therefore, the argument of making it out of Qdisc is non-sense, anything outside of Qdisc is not even my target. Of course you can do anything in XDP, but it has absolutely nothing with my goal here: Qdisc.
Applying queuing discipline to non-skb context may be not your target but it's a reasonable and practical request to have. The kernel is not
Your request has nothing to do with TC or Qdisc, nor it has any conflict at all.
Quoted 2 lines
about solving one person's itch. The kernel has to be optimized for all use cases.
What are you talking about? Are you saying we can't add any new Qdisc simply because you want to a queue in XDP and it is more generic??
Quoted 10 lines
Quoted 10 lines
I also addressed the skb map concern:
" 2b) Kernel would lose the visibility of the "queues", as maps are only
shared between eBPF programs and user-space. These queues still have to interact with the kernel, for example, kernel wants to reset all queues when we reset the network interface, kernel wants to adjust number of queues if they are mapped to hardware queues."
Quoted 3 lines
Quoted 1 line
More than writing, I even tried to write a skb map by myself,
Cool and it sounds that you've failed to do so?
Sure, the above precisely explains why it fails to fit in Qdisc context. Thanks for repeating it.
Quoted 3 lines
At the same time Toke mentioned that he has a prototype of suck skb map. What addition data can open your mind that skb/packet map is more universal building block for queuing discipline in different layers?
You can add queue at any place you want, what's your problem of repeating it? What can open your mind to just look at Qdisc?
Thanks
Quoted 5 lines · Cong Wang
Quoted 1 line
That's why approaching the goal with more generic ambitions was requested.
This goal has nothing to do with my goal, I am pretty sure we have a lot of queues in networking, here I am only interested in Qdisc for sure. If you need queues in any other place, it is your job, not mine.
Now it's yours.
Applying queuing discipline to non-skb context may be not your target but it's a reasonable and practical request to have.
Jamal Hadi Salim
maintainerQuoted 2 lines · Alexei Starovoitov
Applying queuing discipline to non-skb context may be not your target but it's a reasonable and practical request to have.
While i agree that it is useful to deal with queues and scheduling for other buffer contexts, it certainly not the same infrastructure wise to deal with sending a context to user space vs dealing with the qdisc environment. There are a lot of corner cases of dealing with the mix of hard and softirqs, non-work conserving modes, multiflow funneling and locking etc that have been refined over the years that are incorporated into the tc + netdev infra.
The approach that Cong took of just reusing that infra will take advantage of those learnings. The only thing that is variable between the different qdiscs is the enqueue/dequeue algos (which is where Cong is sticking the ebpf hooks). To me that looks like a very good starting point as i dont believe you can come up with one size fits all without excessive over-engineering (which seems to defeat the purpose of ebpf).
cheers,
jamal