From: Cong Wang <cong.wang@xxxxxxxxxxxxx>
This *incomplete* patchset introduces a programmable Qdisc with eBPF.
There are a few use cases:
1. Allow customizing Qdisc's in an easier way. So that people don't
have to write a complete Qdisc kernel module just to experiment
some new queuing theory.
2. Solve EDT's problem. EDT calcuates the "tokens" in clsact which
is before enqueue, it is impossible to adjust those "tokens" after
packets get dropped in enqueue. With eBPF Qdisc, it is easy to
be solved with a shared map between clsact and sch_bpf.
3. Replace qevents, as now the user gains much more control over the
skb and queues.
4. Provide a new way to reuse TC filters. Currently TC relies on filter
chain and block to reuse the TC filters, but they are too complicated
to understand. With eBPF helper bpf_skb_tc_classify(), we can invoke
TC filters on _any_ Qdisc (even on a different netdev) to do the
classification.
5. Potentially pave a way for ingress to queue packets, although
current implementation is still only for egress.
6. Possibly pave a way for handling TCP protocol in TC, as rbtree itself
is already used by TCP to handle TCP retransmission.
The goal here 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. This is why I give up on PIFO which has
serious limitations on the programmablity.
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. Introduce skb map, which will allow other eBPF programs to store skb's
too.
a) As eBPF maps are not directly visible to the kernel, we have to
dump the stats via eBPF map API's instead of netlink.
b) The user-space is not allowed to read the entire packets, only __sk_buff
itself is readable, because we don't have such a use case yet and it would
require a different API to read the data, as map values have fixed length.
c) Two eBPF helpers are introduced for skb map operations:
bpf_skb_map_push() and bpf_skb_map_pop(). Normal map update is
not allowed.
d) Multi-queue support is implemented via map-in-map, in a similar
push/pop fasion.
e) Use the netdevice notifier to reset the packets inside skb map upon
NETDEV_DOWN event.
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. Another helper bpf_skb_tc_classify() is
introduced for this purpose.
Any high-level feedback is welcome. Please kindly 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
Cc: Toke Høiland-Jørgensen <toke@xxxxxxxxxx>
Cc: Jamal Hadi Salim <jhs@xxxxxxxxxxxx>
Cc: Jiri Pirko <jiri@xxxxxxxxxxx>
Signed-off-by: Cong Wang <cong.wang@xxxxxxxxxxxxx>
---
v5: mv kernel/bpf/skb_map.c net/core/skb_map.c
implement flow map as map-in-map
rename bpf_skb_tc_classify() and move it to net/sched/cls_api.c
clean up eBPF qdisc program context
v4: get rid of PIFO, use rbtree directly
v3: move priority queue from sch_bpf to skb map
introduce skb map and its helpers
introduce bpf_skb_classify()
use netdevice notifier to reset skb's
Rebase on latest bpf-next
v2: Rebase on latest net-next
Make the code more complete (but still incomplete)
Cong Wang (5):
net: introduce skb_rbtree_walk_safe()
bpf: move map in map declarations to bpf.h
bpf: introduce skb map and flow map
net_sched: introduce eBPF based Qdisc
net_sched: introduce helper bpf_skb_tc_classify()
include/linux/bpf.h | 6 +
include/linux/bpf_types.h | 4 +
include/linux/skbuff.h | 9 +-
include/uapi/linux/bpf.h | 23 ++
include/uapi/linux/pkt_sched.h | 17 ++
kernel/bpf/arraymap.c | 2 -
kernel/bpf/hashtab.c | 1 -
kernel/bpf/map_in_map.c | 2 -
kernel/bpf/map_in_map.h | 19 --
kernel/bpf/verifier.c | 10 +
net/core/Makefile | 1 +
net/core/filter.c | 39 +++
net/core/skb_map.c | 520 +++++++++++++++++++++++++++++++++
net/sched/Kconfig | 15 +
net/sched/Makefile | 1 +
net/sched/cls_api.c | 69 +++++
net/sched/sch_bpf.c | 485 ++++++++++++++++++++++++++++++
17 files changed, 1198 insertions(+), 25 deletions(-)
delete mode 100644 kernel/bpf/map_in_map.h
create mode 100644 net/core/skb_map.c
create mode 100644 net/sched/sch_bpf.c
--
2.34.1
