net_sched: introduce eBPF based Qdisc
Subsystems (6)
v5 cover net_sched: introduce eBPF based Qdisc
From: Cong Wang <[email protected]>
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
---
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
Signature · 1 line
2.34.1
RFC PATCH v5 1/5 net: introduce skb_rbtree_walk_safe()
From: Cong Wang <[email protected]>
--- include/linux/skbuff.h | 5 +++++ 1 file changed, 5 insertions(+)
include/linux/skbuff.h +5 -0
@@ -3929,6 +3929,11 @@ static inline int __skb_grow_rcsum(struct sk_buff *skb, unsigned int len)for (skb =skb_rb_first (root); skb !=NULL ; \ skb = skb_rb_next(skb)) +#define skb_rbtree_walk_safe (skb, tmp, root) \ + for (skb = skb_rb_first(root); \ + tmp = skb ? skb_rb_next(skb) : NULL, (skb != NULL); \ + skb = tmp) +#define skb_rbtree_walk_from (skb) \ for (; skb != NULL; \ skb = skb_rb_next(skb))
Signature · 1 line
2.34.1
RFC PATCH v5 2/5 bpf: move map in map declarations to bpf.h
In reply to Cong WangFrom: Cong Wang <[email protected]>
--- include/linux/bpf.h | 6 ++++++ kernel/bpf/arraymap.c | 2 -- kernel/bpf/hashtab.c | 1 - kernel/bpf/map_in_map.c | 2 -- kernel/bpf/map_in_map.h | 19 ------------------- 5 files changed, 6 insertions(+), 24 deletions(-) delete mode 100644 kernel/bpf/map_in_map.h
include/linux/bpf.h +6 -0
@@ -341,6 +341,12 @@ int map_check_no_btf(const struct bpf_map *map,bool bpf_map_meta_equal (const struct bpf_map *meta0,const struct bpf_map *meta1); +struct bpf_map *bpf_map_meta_alloc (int inner_map_ufd); +void bpf_map_meta_free (struct bpf_map *map_meta); +void *bpf_map_fd_get_ptr (struct bpf_map *map,struct file *map_file, +int ufd); +void bpf_map_fd_put_ptr (void *ptr); +u32 bpf_map_fd_sys_lookup_elem (void *ptr);extern const struct bpf_map_ops bpf_map_offload_ops;
kernel/bpf/arraymap.c +0 -2
@@ -13,8 +13,6 @@#include <linux/rcupdate_trace.h> #include <linux/btf_ids.h> -#include "map_in_map.h" -#define ARRAY_CREATE_FLAG_MASK \ (BPF_F_NUMA_NODE | BPF_F_MMAPABLE | BPF_F_ACCESS_MASK | \ BPF_F_PRESERVE_ELEMS | BPF_F_INNER_MAP)
kernel/bpf/hashtab.c +0 -1
@@ -13,7 +13,6 @@#include <linux/btf_ids.h> #include "percpu_freelist.h" #include "bpf_lru_list.h" -#include "map_in_map.h" #define HTAB_CREATE_FLAG_MASK \ (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE | \
kernel/bpf/map_in_map.c +0 -2
@@ -5,8 +5,6 @@#include <linux/bpf.h> #include <linux/btf.h> -#include "map_in_map.h" -struct bpf_map *bpf_map_meta_alloc (int inner_map_ufd) {struct bpf_map *inner_map, *inner_map_meta;
kernel/bpf/map_in_map.h deleted +0 -19
@@ -1,19 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-only */ -/* Copyright (c) 2017 Facebook -*/ -#ifndef __MAP_IN_MAP_H__ -#define __MAP_IN_MAP_H__ - -#include <linux/types.h> - -struct file ; -struct bpf_map ; - -struct bpf_map *bpf_map_meta_alloc (int inner_map_ufd); -void bpf_map_meta_free (struct bpf_map *map_meta); -void *bpf_map_fd_get_ptr (struct bpf_map *map,struct file *map_file, -int ufd); -void bpf_map_fd_put_ptr (void *ptr); -u32 bpf_map_fd_sys_lookup_elem (void *ptr); - -#endif
Signature · 1 line
2.34.1
RFC PATCH v5 3/5 bpf: introduce skb map and flow map
In reply to Cong WangIntroduce two maps: one for storing skb and one for storing skb flows, the latter one is implemented as a map in map. The API's for two maps are similiar, except one takes skb pointer and the other takes skb map pointer.
Here are the API's for skb map:
1. Insert skb into skb map at position @key:bpf_skb_push(&map, skb, key);
2. Remove the skb at position @key from skb map:
skb = bpf_skb_pop(&map, key);
3. Peek an skb by @key:
skb = bpf_map_lookup_elem(&map, &key);
4. Drop the skb at position @key:bpf_map_delete_elem(&map, &key);
5. Iterate all the skbs in the map in order:bpf_for_each_map_elem(&skb_map, skb_callback, key, skb);
--- include/linux/bpf.h | 4 + include/linux/bpf_types.h | 2 + include/linux/skbuff.h | 4 +- include/uapi/linux/bpf.h | 6 + kernel/bpf/verifier.c | 10 + net/core/Makefile | 1 + net/core/skb_map.c | 520 ++++++++++++++++++++++++++++++++++++++ 7 files changed, 546 insertions(+), 1 deletion(-) create mode 100644 net/core/skb_map.c
include/linux/bpf.h +4 -0
@@ -2274,6 +2274,10 @@ extern const struct bpf_func_proto bpf_loop_proto;extern const struct bpf_func_proto bpf_strncmp_proto;extern const struct bpf_func_proto bpf_copy_from_user_task_proto;extern const struct bpf_func_proto bpf_kptr_xchg_proto; +extern const struct bpf_func_proto bpf_skb_map_push_proto; +extern const struct bpf_func_proto bpf_skb_map_pop_proto; +extern const struct bpf_func_proto bpf_flow_map_push_proto; +extern const struct bpf_func_proto bpf_flow_map_pop_proto;const struct bpf_func_proto *tracing_prog_func_proto (enum bpf_func_id func_id,const struct bpf_prog *prog);
include/linux/bpf_types.h +2 -0
@@ -110,6 +110,8 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP, dev_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP_HASH, dev_map_hash_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_SK_STORAGE, sk_storage_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_CPUMAP, cpu_map_ops) +BPF_MAP_TYPE(BPF_MAP_TYPE_SKBMAP, skb_map_ops) +BPF_MAP_TYPE(BPF_MAP_TYPE_FLOWMAP, flow_map_ops)#if defined(CONFIG_XDP_SOCKETS ) BPF_MAP_TYPE(BPF_MAP_TYPE_XSKMAP, xsk_map_ops)#endif
include/linux/skbuff.h +3 -1
@@ -1017,7 +1017,9 @@ struct sk_buff {unsigned long dev_scratch; }; }; -struct rb_node rbnode;/* used in netem, ip4 defrag, and tcp stack */ +struct rb_node rbnode;/* used in eBPF skb map, netem, ip4 defrag, and tcp +* stack +*/ struct list_head list;struct llist_node ll_node; };
include/uapi/linux/bpf.h +6 -0
@@ -909,6 +909,8 @@ enum bpf_map_type {BPF_MAP_TYPE_INODE_STORAGE ,BPF_MAP_TYPE_TASK_STORAGE ,BPF_MAP_TYPE_BLOOM_FILTER , +BPF_MAP_TYPE_SKBMAP , + BPF_MAP_TYPE_FLOWMAP, };/* Note that tracing related programs such as
@@ -5455,6 +5457,10 @@ union bpf_attr {FN (dynptr_read), \FN (dynptr_write), \FN (dynptr_data), \ +FN (skb_map_push), \ +FN (skb_map_pop), \ +FN (flow_map_push), \ +FN (flow_map_pop), \/* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper
kernel/bpf/verifier.c +10 -0
@@ -6264,6 +6264,16 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env, func_id != BPF_FUNC_map_push_elem) goto error;break ; +case BPF_MAP_TYPE_SKBMAP : +if (func_id != BPF_FUNC_skb_map_push && + func_id != BPF_FUNC_skb_map_pop) + goto error; +break ; +case BPF_MAP_TYPE_FLOWMAP : +if (func_id != BPF_FUNC_flow_map_push && + func_id != BPF_FUNC_flow_map_pop) + goto error; +break ;default :break ; }
net/core/Makefile +1 -0
@@ -38,4 +38,5 @@ obj-$(CONFIG_FAILOVER) += failover.o obj-$(CONFIG_NET_SOCK_MSG) += skmsg.o obj-$(CONFIG_BPF_SYSCALL) += sock_map.o obj-$(CONFIG_BPF_SYSCALL) += bpf_sk_storage.o +obj-$(CONFIG_BPF_SYSCALL) += skb_map.o obj-$(CONFIG_OF) += of_net.o
net/core/skb_map.c new file +520 -0
520 lines not on this page · raw message
Signature · 1 line
2.34.1
RFC PATCH v5 4/5 net_sched: introduce eBPF based Qdisc
In reply to Cong WangIntroduce a new Qdisc which is completely managed by eBPF program of type BPF_PROG_TYPE_SCHED_QDISC. It accepts two eBPF programs of the same type, but one for enqueue and the other for dequeue.
And it interacts with Qdisc layer in two ways:
1) It relies on Qdisc watchdog to handle throttling;
2) It could pass the skb enqueue/dequeue down to child classes
The context of this eBPF program is different, as shown below:
┌─────────────────┬───────────────┬────────────────────────────────────┐ │ │ │ │ │ prog │ input │ output │ │ │ │ │ ├─────────────────┼───────────────┼────────────────────────────────────┤ │ │ │ │ │ │ ctx->skb │ SCH_BPF_THROTTLE: ctx->delay │ │ │ │ │ │ enqueue │ ctx->classid │ SCH_BPF_QUEUED: None │ │ │ │ │ │ │ │ SCH_BPF_DROP: None │ │ │ │ │ │ │ │ SCH_BPF_CN: None │ │ │ │ │ │ │ │ SCH_BPF_PASS: ctx->classid │ ├─────────────────┼───────────────┼────────────────────────────────────┤ │ │ │ │ │ │ │ SCH_BPF_THROTTLE: ctx->delay │ │ │ │ │ │ dequeue │ ctx->classid │ SCH_BPF_DEQUEUED: ctx->skb │ │ │ │ │ │ │ │ SCH_BPF_DROP: None │ │ │ │ │ │ │ │ SCH_BPF_PASS: ctx->classid │ │ │ │ │ └─────────────────┴───────────────┴────────────────────────────────────┘
Because eBPF maps are not directly visible to this Qdisc, so we have to rely on user-space dumping to retrieve the stats, which is not implemented yet as I don't find a right API to do this.
--- include/linux/bpf.h | 4 - include/linux/bpf_types.h | 2 + include/uapi/linux/bpf.h | 16 ++ include/uapi/linux/pkt_sched.h | 17 ++ net/core/filter.c | 34 +++ net/sched/Kconfig | 15 + net/sched/Makefile | 1 + net/sched/sch_bpf.c | 485 +++++++++++++++++++++++++++++++++ 8 files changed, 570 insertions(+), 4 deletions(-) create mode 100644 net/sched/sch_bpf.c
include/linux/bpf.h +0 -4
@@ -2274,10 +2274,6 @@ extern const struct bpf_func_proto bpf_loop_proto;extern const struct bpf_func_proto bpf_strncmp_proto;extern const struct bpf_func_proto bpf_copy_from_user_task_proto;extern const struct bpf_func_proto bpf_kptr_xchg_proto; -extern const struct bpf_func_proto bpf_skb_map_push_proto; -extern const struct bpf_func_proto bpf_skb_map_pop_proto; -extern const struct bpf_func_proto bpf_flow_map_push_proto; -extern const struct bpf_func_proto bpf_flow_map_pop_proto;const struct bpf_func_proto *tracing_prog_func_proto (enum bpf_func_id func_id,const struct bpf_prog *prog);
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_qdisc, + 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/uapi/linux/bpf.h +16 -0
@@ -954,6 +954,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 {
@@ -6765,4 +6766,19 @@ struct bpf_core_relo { enum bpf_core_relo_kind kind; }; +struct sch_bpf_ctx { +struct __sk_buff *skb; +__u32 classid; +__u64 delay; +}; + +enum { +SCH_BPF_QUEUED , +SCH_BPF_DEQUEUED =SCH_BPF_QUEUED , +SCH_BPF_DROP , +SCH_BPF_CN , +SCH_BPF_THROTTLE , +SCH_BPF_PASS , +}; +#endif /* _UAPI__LINUX_BPF_H__ */
include/uapi/linux/pkt_sched.h +17 -0
@@ -1267,4 +1267,21 @@ enum {#define TCA_ETS_MAX (__TCA_ETS_MAX - 1) +#define TCA_SCH_BPF_FLAG_DIRECT _BITUL(0) +enum { +TCA_SCH_BPF_UNSPEC , +TCA_SCH_BPF_FLAGS ,/* u32 */ +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/core/filter.c +34 -0
@@ -7813,6 +7813,28 @@ tc_cls_act_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog) } } +const struct bpf_func_proto bpf_skb_map_push_proto__weak ; +const struct bpf_func_proto bpf_skb_map_pop_proto__weak ; +const struct bpf_func_proto bpf_flow_map_push_proto__weak ; +const struct bpf_func_proto bpf_flow_map_pop_proto__weak ; + +static const struct bpf_func_proto * +tc_qdisc_func_proto (enum bpf_func_id func_id,const struct bpf_prog *prog) +{ +switch (func_id) { +case BPF_FUNC_skb_map_push: +return &bpf_skb_map_push_proto; +case BPF_FUNC_skb_map_pop: +return &bpf_skb_map_pop_proto; +case BPF_FUNC_flow_map_push: +return &bpf_flow_map_push_proto; +case BPF_FUNC_flow_map_pop: +return &bpf_flow_map_pop_proto; +default : +return tc_cls_act_func_proto (func_id, prog); + } +} +static const struct bpf_func_proto *xdp_func_proto (enum bpf_func_id func_id,const struct bpf_prog *prog) {
@@ -10476,6 +10498,18 @@ const struct bpf_prog_ops tc_cls_act_prog_ops = { .test_run = bpf_prog_test_run_skb, }; +const struct bpf_verifier_ops tc_qdisc_verifier_ops = { + .get_func_proto = tc_qdisc_func_proto, + .is_valid_access = tc_cls_act_is_valid_access, + .convert_ctx_access = tc_cls_act_convert_ctx_access, + .gen_prologue = tc_cls_act_prologue, + .gen_ld_abs = bpf_gen_ld_abs, +}; + +const struct bpf_prog_ops tc_qdisc_prog_ops = { + .test_run = bpf_prog_test_run_skb, +}; +const struct bpf_verifier_ops xdp_verifier_ops = { .get_func_proto = xdp_func_proto, .is_valid_access = xdp_is_valid_access,
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 +485 -0
485 lines not on this page · raw message
Signature · 1 line
2.34.1
Quoted 4 lines · Cong Wang
Because eBPF maps are not directly visible to this Qdisc, so we have to rely on user-space dumping to retrieve the stats, which is not implemented yet as I don't find a right API to do this.
I think an iterator for skb map could do this job, so I just implemented it here:
https://github.com/congwang/linux/commit/aed8536a94836bf6df69a379c43b03e50bf4f813
which will be in the next update.
Thanks.
RFC PATCH v5 5/5 net_sched: introduce helper bpf_skb_tc_classify()
In reply to Cong WangFrom: Cong Wang <[email protected]>
Introduce an eBPF helper function bpf_skb_tc_classify() to reuse exising TC filters on *any* Qdisc to classify the skb.
--- include/uapi/linux/bpf.h | 1 + net/core/filter.c | 5 +++ net/sched/cls_api.c | 69 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 75 insertions(+)
include/uapi/linux/bpf.h +1 -0
@@ -5462,6 +5462,7 @@ union bpf_attr {FN (skb_map_pop), \FN (flow_map_push), \FN (flow_map_pop), \ +FN (skb_tc_classify), \/* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper
net/core/filter.c +5 -0
@@ -7817,6 +7817,7 @@ const struct bpf_func_proto bpf_skb_map_push_proto __weak;const struct bpf_func_proto bpf_skb_map_pop_proto__weak ;const struct bpf_func_proto bpf_flow_map_push_proto__weak ;const struct bpf_func_proto bpf_flow_map_pop_proto__weak ; +const struct bpf_func_proto bpf_skb_tc_classify_proto__weak ;static const struct bpf_func_proto *tc_qdisc_func_proto (enum bpf_func_id func_id,const struct bpf_prog *prog)
@@ -7830,6 +7831,10 @@ tc_qdisc_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog)return &bpf_flow_map_push_proto;case BPF_FUNC_flow_map_pop:return &bpf_flow_map_pop_proto; +#ifdef CONFIG_NET_CLS_ACT +case BPF_FUNC_skb_tc_classify: +return &bpf_skb_tc_classify_proto; +#endif default :return tc_cls_act_func_proto (func_id, prog); }
net/sched/cls_api.c +69 -0
81 lines not on this page · raw message
Signature · 1 line
2.34.1
Quoted 3 lines · Cong Wang
From: Cong Wang <[email protected]>
This *incomplete* patchset introduces a programmable Qdisc with eBPF.
Sorry for the delay in looking at this; a few comments below:
[...]
Quoted 4 lines
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.
Could you elaborate on the limitations of the PIFO? It looks to me like the SKB map you're proposing is very close to a PIFO (it's a priority queue that SKBs can be inserted into at an arbitrary position)?
Quoted 6 lines
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 structQdisc_opsand structQdisc_class_opsare needed to implement. This is almost as hard as programming a Qdisc kernel module.
I agree that implementing the full Qdisc_class_ops as BPF functions is going to be prohibitive; let's use this opportunity to define a simpler API!
Quoted 5 lines
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.
Why not do a hybrid thing where the kernel side of the qdisc keeps some basic stats (packet counter for number of packets queued/dropped for instance) and define a separate BPF callback that can return more stats to the kernel for translation into netlink (e.g., "how many packets are currently in the queue")? And then if a particular implementation wants to do more custom stats, they can use BPF APIs for that?
Quoted 4 lines
b) The user-space is not allowed to read the entire packets, only
__sk_buffitself 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.
I agree there's not any need to make the packet contents directly accessible to userspace via reading the map.
Quoted 3 lines
c) Two eBPF helpers are introduced for skb map operations:
bpf_skb_map_push()andbpf_skb_map_pop(). Normal map update is not allowed.
So with kptr support in the map this could conceivably be done via the existing map_push() etc helpers?
Quoted 2 lines
d) Multi-queue support is implemented via map-in-map, in a similar push/pop fasion.
Not sure I understand what you mean by this? Will the qdisc automatically attach itself to all HWQs of an interface (like sch_mq does)? Surely it will be up to the BPF program whether it'll use map-in-map or something else?
Quoted 2 lines
e) Use the netdevice notifier to reset the packets inside skb map upon
NETDEV_DOWNevent.
Is it really necessary to pull out SKBs from under the BPF program? If the qdisc is removed and the BPF program goes away, so will the map and all SKBs stored in it?
Quoted 4 lines
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.
This seems a bit convoluted? If a BPF program wants to reuse an existing BPF TC filter it can just do that at the code level. As for the in-kernel filters are there really any of them it would be worth reusing from a BPF qdisc other than the flow dissector? In which case, why not just expose that instead of taking all the TC filter infrastructure with you?
Bringing in some text from patch 4 as well to comment on it all in one go:
Quoted 6 lines
Introduce a new Qdisc which is completely managed by eBPF program of type
BPF_PROG_TYPE_SCHED_QDISC. It accepts two eBPF programs of the same type, but one for enqueue and the other for dequeue.And it interacts with Qdisc layer in two ways:
1) It relies on Qdisc watchdog to handle throttling;
Having a way for BPF to schedule the qdisc watchdog wakeup is probably needed. For the XDP queueing side I'm planning to use BPF timers for (the equivalent of) this, but since we already have a watchdog mechanism on the qdisc side maybe just exposing that is fine...
Quoted 1 line
2) It could pass the skb enqueue/dequeue down to child classes
I'm not sure I think it's a good idea to keep the qdisc hierarchy. If someone wants to build a classification hierarchy they could just do this directly in BPF by whichever mechanism they want? I.e., it can just instantiate multiple skb maps in a single program to do classful queueing and select the right one however it wants?
Keeping the qdisc itself simple as, basically:
enqueue: pass skb to BPF program to do with as it will (enqueue into a map, drop, etc)
dequeue: execute BPF program, transmit pkt if it returns one
-Toke
In my world, it's inbound shaping that's the biggest problem, and my dream has long been to somehow have a way to do:
tc qdisc add dev eth0 ingress cake bandwidth 800mbit
and that be able to work across multiple cores, without act_mirred, without any filter magic. Getting there via ebpf as in
https://github.com/rchac/LibreQoS is working for ISPs (plea, anyone got time to make ipv6 work there?), but it's
running out of cpu for inbound shaping on the current act_mirred path we use that's killing us.
Quoted 72 lines · Cong Wang
From: Cong Wang <[email protected]>
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 structQdisc_opsand structQdisc_class_opsare 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()andbpf_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_DOWNevent.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 helperbpf_skb_tc_classify()is
introduced for this purpose.
Quoted 5 lines
Any high-level feedback is welcome. Please kindly do not review any coding details until RFC tag is removed.
TODO:
1. actually test it
Can you try to implement some existing qdisc using your new mechanism? For BPF-CC, Martin showcased how dctcp/cubic can be reimplemented; I feel like this patch series (even rfc), should also have a good example to show that bpf qdisc is on par and can be used to at least implement existing policies. fq/fq_codel/cake are good candidates.