Skip to contentSkip to conversation

net_sched: introduce eBPF based Qdisc

RFC PATCH Superseded Cong Wang 2 participants 4 messages May 20, 2022 – May 21, 2022

Subsystems (5)

v4 of 6 Superseded Latest is v6 →

lore
Share & tools
lore

Cong Wang

author
#0 lore raw

v4 cover net_sched: introduce eBPF based Qdisc

From: Cong Wang <[email protected]>

This *incomplete* patch 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. Potentially pave a way for ingress to queue packets, although current implementation is still only for egress.

4. Potentially pave a way for handling TCP protocol in TC, as rbtree itself is already used by TCP to handle TCP retransmission.

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. 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 should be done via map-in-map. This is TBD.

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_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 <[email protected]>
Cc Jamal Hadi Salim <[email protected]>
Cc Jiri Pirko <[email protected]>

---
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 (2):
bpf: introduce skb map
net_sched: introduce eBPF based Qdisc

 include/linux/bpf_types.h      |   2 +
 include/linux/skbuff.h         |   4 +-
 include/uapi/linux/bpf.h       |  15 +
 include/uapi/linux/pkt_sched.h |  17 ++
 kernel/bpf/Makefile            |   2 +-
 kernel/bpf/skb_map.c           | 337 +++++++++++++++++++++
 net/sched/Kconfig              |  15 +
 net/sched/Makefile             |   1 +
 net/sched/sch_bpf.c            | 520 +++++++++++++++++++++++++++++++++
 9 files changed, 911 insertions(+), 2 deletions(-)
 create mode 100644 kernel/bpf/skb_map.c
 create mode 100644 net/sched/sch_bpf.c
Signature · 1 line
2.34.1
author
#1 lore raw

RFC PATCH v4 1/2 bpf: introduce skb map

---
 include/linux/skbuff.h |   4 +-
 kernel/bpf/Makefile    |   2 +-
 kernel/bpf/skb_map.c   | 337 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 341 insertions(+), 2 deletions(-)
 create mode 100644 kernel/bpf/skb_map.c
include/linux/skbuff.h +3 -1
index dc4b3e1cf21b..7fa893008a64 100644
@@ -931,7 +931,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;
 	};
kernel/bpf/Makefile +1 -1
index 057ba8e01e70..37183df5b3ba 100644
@@ -8,7 +8,7 @@ CFLAGS_core.o += $(call cc-disable-warning, override-init) $(cflags-nogcse-yy)
 
 obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o
 obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o
-obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o
+obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o skb_map.o
 obj-$(CONFIG_BPF_SYSCALL) += bpf_local_storage.o bpf_task_storage.o
 obj-${CONFIG_BPF_LSM}	  += bpf_inode_storage.o
 obj-$(CONFIG_BPF_SYSCALL) += disasm.o
kernel/bpf/skb_map.c new file +337 -0

337 lines not on this page · raw message

Signature · 1 line
2.34.1
#2 lore raw

Re: [RFC Patch v4 1/2] bpf: introduce skb map

[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in https://git-scm.com/docs/git-format-patch]

Hi Cong,

[FYI, it's a private test report for your RFC patch.]
[auto build test WARNING on bpf-next/master]
[also build test WARNING on bpf/master horms-ipvs/master net/master net-next/master linus/master v5.18-rc7 next-20220520] [If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/intel-lab-lkp/linux/commits/Cong-Wang/net_sched-introduce-eBPF-based-Qdisc/20220521-014934
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
config: riscv-randconfig-r016-20220519 (https://download.01.org/0day-ci/archive/20220521/[email protected]/config)
compiler: clang version 15.0.0 (https://github.com/llvm/llvm-project e00cbbec06c08dc616a0d52a20f678b8fbd4e304)

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/intel-lab-lkp/linux/commit/771d03ba8e035ead53334c0dea1d181eb6e9e27d
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Cong-Wang/net_sched-introduce-eBPF-based-Qdisc/20220521-014934 git checkout 771d03ba8e035ead53334c0dea1d181eb6e9e27d
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=riscv SHELL=/bin/bash kernel/bpf/

If you fix the issue, kindly add following tag where applicable

All warnings (new ones prefixed by >>):

>> kernel/bpf/skb_map.c:264:36: warning: unused variable 'bpf_skb_map_pop_proto' [-Wunused-const-variable]
   static const struct bpf_func_proto bpf_skb_map_pop_proto = {
                                      ^
>> kernel/bpf/skb_map.c:287:36: warning: unused variable 'bpf_skb_map_push_proto' [-Wunused-const-variable]
   static const struct bpf_func_proto bpf_skb_map_push_proto = {
                                      ^

2 warnings generated.

vim +/bpf_skb_map_pop_proto +264 kernel/bpf/skb_map.c

263

 > 264	static const struct bpf_func_proto bpf_skb_map_pop_proto = {
   265		.func		= bpf_skb_map_pop,
   266		.gpl_only	= false,
   267		.ret_type	= RET_INTEGER,
   268		.arg1_type	= ARG_CONST_MAP_PTR,
   269		.arg2_type	= ARG_ANYTHING,
   270	};
   271	
   272	BPF_CALL_3(bpf_skb_map_push, struct bpf_map *, map, struct sk_buff *, skb, u64, key)
   273	{
   274		struct bpf_skb_map *rb = bpf_skb_map(map);
   275		unsigned long flags;
   276	
   277		if (atomic_inc_return(&rb->count) > rb->map.max_entries)
   278			return -ENOBUFS;
   279		skb = skb_get(skb);
   280		skb_map_cb(skb)->rank = key;
   281		raw_spin_lock_irqsave(&rb->lock, flags);
   282		skb_rb_push(&rb->root, skb);
   283		raw_spin_unlock_irqrestore(&rb->lock, flags);
   284		return 0;
   285	}
   286	
 > 287	static const struct bpf_func_proto bpf_skb_map_push_proto = {

288 .func = bpf_skb_map_push,
289 .gpl_only = false,
290 .ret_type = RET_INTEGER,
291 .arg1_type = ARG_CONST_MAP_PTR,
292 .arg2_type = ARG_PTR_TO_CTX,
293 .arg3_type = ARG_ANYTHING,
294 };
295

Signature · 2 lines
0-DAY CI Kernel Test Service
https://01.org/lkp
author
#3 lore raw

RFC PATCH v4 2/2 net_sched: introduce eBPF based Qdisc

In reply to Cong Wang
---
 include/linux/bpf_types.h      |   2 +
 include/uapi/linux/bpf.h       |  15 +
 include/uapi/linux/pkt_sched.h |  17 ++
 net/sched/Kconfig              |  15 +
 net/sched/Makefile             |   1 +
 net/sched/sch_bpf.c            | 520 +++++++++++++++++++++++++++++++++
 6 files changed, 570 insertions(+)
 create mode 100644 net/sched/sch_bpf.c
include/linux/bpf_types.h +2 -0
index 2b9112b80171..c3dac1c6b00e 100644
@@ -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/uapi/linux/bpf.h +15 -0
index 0210f85131b3..130933bf5034 100644
@@ -952,6 +952,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 {
@@ -6669,4 +6670,18 @@ 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_OK,
+	SCH_BPF_QUEUED,
+	SCH_BPF_DROP,
+	SCH_BPF_THROTTLE,
+	SCH_BPF_CONTINUE,
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
include/uapi/linux/pkt_sched.h +17 -0
index f292b467b27f..b51eb712517a 100644
@@ -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/sched/Kconfig +15 -0
index 1e8ab4749c6c..19f68aac79b1 100644
@@ -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
index dd14ef413fda..9ef0d579f5ff 100644
@@ -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 +520 -0

520 lines not on this page · raw message

Signature · 1 line
2.34.1