BPF and OVS extensions
Subsystems (7)
v2 cover BPF and OVS extensions
while net-next is closed, collecting feedback...
V2:
No changes to BPF engine
No changes to uapi
Add static branch prediction markings, remove unnecessary safety checks, fix crash where packets were enqueued to a BPF program while program was being unloaded
V1:
Today OVS is a cache engine. Userspace controller simulates traversal of network topology and establishes a flow (cached result of the traversal). Suffering upcall penalty, flow explosion, flow invalidation on topology changes, difficulties in keeping inner topology stats, etc. This patch enhances OVS by moving simple cases of topology traversal next to the packet. On a flow miss the chain of BPF programs executes the network topology. If packet requires userspace processing it can be pushed up by BPF program. BPF program that represent a bridge just needs to forward packets. MAC learning can be done either by BPF program or via userpsace upcall. Such bridge/router/nat can be programmed in BPF.
To achieve that BPF was extended to allow easier programability in restricted C or in dataplane language.
Patch 1/2: generic BPF extension
Original A and X 32-bit BPF registers are replaced with ten 64-bit registers. bpf opcode encoding kept the same. load/store were generalized to access stack, bpf_tables and bpf_context.
BPF program interfaces to outside world via tables that it can read and write, and via bpf_context which is in/out blob of data.
Other kernel components can provide callbacks to tailor BPF to specific needs.
Patch 2/2: extends OVS with network functions that use BPF as execution engine
BPF backend for GCC is available at:
https://github.com/iovisor/bpf_gcc
Distributed bridge demo written in BPF:
https://github.com/iovisor/iovisor
Alexei Starovoitov (2):
extended BPF
extend OVS to use BPF programs on flow miss
arch/x86/net/Makefile | 2 +- arch/x86/net/bpf2_jit_comp.c | 610 +++++++++++++++++++ arch/x86/net/bpf_jit_comp.c | 41 +- arch/x86/net/bpf_jit_comp.h | 36 ++ include/linux/filter.h | 79 +++ include/uapi/linux/filter.h | 125 +++- include/uapi/linux/openvswitch.h | 140 +++++ net/core/Makefile | 2 +- net/core/bpf_check.c | 1043 ++++++++++++++++++++++++++++++++ net/core/bpf_run.c | 412 +++++++++++++ net/openvswitch/Makefile | 7 +- net/openvswitch/bpf_callbacks.c | 295 +++++++++ net/openvswitch/bpf_plum.c | 931 +++++++++++++++++++++++++++++ net/openvswitch/bpf_replicator.c | 155 +++++ net/openvswitch/bpf_table.c | 500 ++++++++++++++++ net/openvswitch/datapath.c | 102 +++- net/openvswitch/datapath.h | 5 + net/openvswitch/dp_bpf.c | 1228 ++++++++++++++++++++++++++++++++++++++ net/openvswitch/dp_bpf.h | 160 +++++ net/openvswitch/dp_notify.c | 7 + net/openvswitch/vport-gre.c | 10 - net/openvswitch/vport-netdev.c | 15 +- net/openvswitch/vport-netdev.h | 1 + net/openvswitch/vport.h | 10 + 24 files changed, 5854 insertions(+), 62 deletions(-) create mode 100644 arch/x86/net/bpf2_jit_comp.c create mode 100644 arch/x86/net/bpf_jit_comp.h create mode 100644 net/core/bpf_check.c create mode 100644 net/core/bpf_run.c create mode 100644 net/openvswitch/bpf_callbacks.c create mode 100644 net/openvswitch/bpf_plum.c create mode 100644 net/openvswitch/bpf_replicator.c create mode 100644 net/openvswitch/bpf_table.c create mode 100644 net/openvswitch/dp_bpf.c create mode 100644 net/openvswitch/dp_bpf.h
Signature · 1 line
1.7.9.5
A message that is not in the archive (sent off-list or not yet received): 1379386119-4157-1-git-send-email-ast-uqk4Ao+rVK5Wk0Htik3J/[email protected]
RFC PATCH v2 1/2 extended BPF
extended BPF program = BPF insns + BPF tables
flexible instruction set:
- from two 32-bit registers (A and X) to ten 64-bit regs
- add conditional jump back, signed compare, bswap
- in addition to old load[1,2,4,8] bytes, add store[1,2,4,8] bytes
- fixed set of function calls via simple ABI:
R0 - return register
R1-R5 - argument passing
R6-R9 - callee saved
R10 - frame pointer
- bpf_table_lookup/bpf_table_update functions to access BPF tables
- generic 'struct bpf_context' = input/output argument to BPF program
BPF table is defined by
- type, id, number of elements, key size, element size
To use generic BPF engine other kernel components will define:
- the body of 'bpf_context' and access permission
- available function calls: their prototypes for BPF checker, body for BPF interpreter and JIT
BPF programs can be written in restricted C
GCC backend for BPF is available
BPF checker does full program validation before it is JITed or run in interpreter
--- arch/x86/net/Makefile | 2 +- arch/x86/net/bpf2_jit_comp.c | 610 ++++++++++++++++++++++++ arch/x86/net/bpf_jit_comp.c | 41 +- arch/x86/net/bpf_jit_comp.h | 36 ++ include/linux/filter.h | 79 ++++ include/uapi/linux/filter.h | 125 ++++- net/core/Makefile | 2 +- net/core/bpf_check.c | 1043 ++++++++++++++++++++++++++++++++++++++++++ net/core/bpf_run.c | 412 +++++++++++++++++ 9 files changed, 2315 insertions(+), 35 deletions(-) create mode 100644 arch/x86/net/bpf2_jit_comp.c create mode 100644 arch/x86/net/bpf_jit_comp.h create mode 100644 net/core/bpf_check.c create mode 100644 net/core/bpf_run.c
arch/x86/net/Makefile +1 -1
@@ -1,4 +1,4 @@ # # Arch-specific network modules # -obj-$(CONFIG_BPF_JIT) += bpf_jit.o bpf_jit_comp.o +obj-$(CONFIG_BPF_JIT) += bpf_jit.o bpf_jit_comp.o bpf2_jit_comp.o
arch/x86/net/bpf2_jit_comp.c new file +610 -0
610 lines not on this page · raw message
arch/x86/net/bpf_jit_comp.c +14 -27
65 lines not on this page · raw message
arch/x86/net/bpf_jit_comp.h new file +36 -0
@@ -0,0 +1,36 @@ +/* bpf_jit_comp.h : BPF filter alloc/free routines +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* as published by the Free Software Foundation; version 2 +* of the License. +*/ +#ifndef __BPF_JIT_COMP_H +#define __BPF_JIT_COMP_H + +#include <linux/uaccess.h> +#include <asm/cacheflush.h> + +struct bpf_binary_header { +unsigned int pages; +/* Note : for security reasons, bpf code will follow a randomly +* sized amount of int3 instructions +*/ +u8 image[]; +}; + +static inline void bpf_flush_icache (void *start,void *end) +{ +mm_segment_t old_fs =get_fs (); + +set_fs (KERNEL_DS ); +smp_wmb (); +flush_icache_range ((unsigned long )start, (unsigned long )end); +set_fs (old_fs); +} + +extern struct bpf_binary_header *bpf_alloc_binary (unsigned int proglen, +u8 **image_ptr); +extern void bpf_free_binary (void *image_ptr); + +#endif
include/linux/filter.h +79 -0
97 lines not on this page · raw message
include/uapi/linux/filter.h +119 -6
171 lines not on this page · raw message
net/core/Makefile +1 -1
@@ -9,7 +9,7 @@ obj-$(CONFIG_SYSCTL) += sysctl_net_core.o obj-y += dev.o ethtool.o dev_addr_lists.o dst.o netevent.o \ neighbour.o rtnetlink.o utils.o link_watch.o filter.o \ - sock_diag.o dev_ioctl.o + sock_diag.o dev_ioctl.o bpf_run.o bpf_check.o obj-$(CONFIG_XFRM) += flow.o obj-y += net-sysfs.o
net/core/bpf_check.c new file +1043 -0
1,043 lines not on this page · raw message
net/core/bpf_run.c new file +412 -0
412 lines not on this page · raw message
Signature · 1 line
1.7.9.5
RFC PATCH v2 2/2 extend OVS to use BPF programs on flow miss
In reply to a message not in the archiveOriginal OVS packet flow:flow_table_lookup -> flow_miss -> upcall
Original OVS is a cache engine: controller simulates traversal of network topology and establishes a flow == cached result of the traversal.
Extended OVS:flow_table_lookup -> flow_miss -> BPF workflow -> upcall (optional)
BPF programs traverse a topology of BPF-bridges/routers/nats/firewalls (plums). If they cannot do it completely, they can upcall into controller. Controller can either adjust execution of BPF programs via corresponding BPF tables or program flows in the main cache engine.
plum is a specific use case of BPF engine
plum stands for Parse Lookup Update Modify 'bpf_load_xxx' functions are used to read data from the packet. 'bpf_table_lookup' to access tables
'bpf_forward' to forward the packet
plums are connected to each other and to ovs-vport's via OVS_BPF_CMD_CONNECT_PORTS netlink command.
plums can push data to userspace via 'bpf_channel_push_xxx' functions that utilize ovs upcall mechanism
'bpf_csum_xxx' are helper functions when plum wants to modify the packet
--- include/uapi/linux/openvswitch.h | 140 +++++ net/openvswitch/Makefile | 7 +- net/openvswitch/bpf_callbacks.c | 295 +++++++++ net/openvswitch/bpf_plum.c | 931 +++++++++++++++++++++++++++++ net/openvswitch/bpf_replicator.c | 155 +++++ net/openvswitch/bpf_table.c | 500 ++++++++++++++++ net/openvswitch/datapath.c | 102 +++- net/openvswitch/datapath.h | 5 + net/openvswitch/dp_bpf.c | 1228 ++++++++++++++++++++++++++++++++++++++ net/openvswitch/dp_bpf.h | 160 +++++ net/openvswitch/dp_notify.c | 7 + net/openvswitch/vport-gre.c | 10 - net/openvswitch/vport-netdev.c | 15 +- net/openvswitch/vport-netdev.h | 1 + net/openvswitch/vport.h | 10 + 15 files changed, 3539 insertions(+), 27 deletions(-) create mode 100644 net/openvswitch/bpf_callbacks.c create mode 100644 net/openvswitch/bpf_plum.c create mode 100644 net/openvswitch/bpf_replicator.c create mode 100644 net/openvswitch/bpf_table.c create mode 100644 net/openvswitch/dp_bpf.c create mode 100644 net/openvswitch/dp_bpf.h
include/uapi/linux/openvswitch.h +140 -0
@@ -495,4 +495,144 @@ enum ovs_action_attr {#define OVS_ACTION_ATTR_MAX (__OVS_ACTION_ATTR_MAX - 1) +/* BPFs. */ + +#define OVS_BPF_FAMILY "ovs_bpf" +#define OVS_BPF_VERSION 0x1 + +enum ovs_bpf_cmd { +OVS_BPF_CMD_UNSPEC , +OVS_BPF_CMD_REGISTER_PLUM , +OVS_BPF_CMD_UNREGISTER_PLUM , +OVS_BPF_CMD_CONNECT_PORTS , +OVS_BPF_CMD_DISCONNECT_PORTS , +OVS_BPF_CMD_CLEAR_TABLE_ELEMENTS , +OVS_BPF_CMD_DELETE_TABLE_ELEMENT , +OVS_BPF_CMD_READ_TABLE_ELEMENT , +OVS_BPF_CMD_UPDATE_TABLE_ELEMENT , +OVS_BPF_CMD_DEL_REPLICATOR , +OVS_BPF_CMD_ADD_PORT_TO_REPLICATOR , +OVS_BPF_CMD_DEL_PORT_FROM_REPLICATOR , +OVS_BPF_CMD_CHANNEL_PUSH , +OVS_BPF_CMD_READ_PORT_STATS , + __OVS_BPF_CMD_MAX +}; + +#define OVS_BPF_CMD_MAX (__OVS_BPF_CMD_MAX - 1) + +enum ovs_bpf_attr { +OVS_BPF_ATTR_UNSPEC , +OVS_BPF_ATTR_PLUM ,/* struct bpf_image */ +OVS_BPF_ATTR_UPCALL_PID ,/* u32 Netlink PID to receive upcalls */ +OVS_BPF_ATTR_PLUM_ID ,/* u32 plum_id */ +OVS_BPF_ATTR_PORT_ID ,/* u32 port_id */ +OVS_BPF_ATTR_DEST_PLUM_ID ,/* u32 dest plum_id */ +OVS_BPF_ATTR_DEST_PORT_ID ,/* u32 dest port_id */ +OVS_BPF_ATTR_TABLE_ID ,/* u32 table_id */ +OVS_BPF_ATTR_KEY_OBJ ,/* table key (opaque data) */ +OVS_BPF_ATTR_LEAF_OBJ ,/* table leaf/element/value (opaque data) */ +OVS_BPF_ATTR_REPLICATOR_ID ,/* u32 replicator_id */ +OVS_BPF_ATTR_PACKET ,/* packet (opaque data) */ +OVS_BPF_ATTR_DIRECTION ,/* u32 direction */ + __OVS_BPF_ATTR_MAX +}; + +#define OVS_BPF_ATTR_MAX (__OVS_BPF_ATTR_MAX - 1) + +enum ovs_bpf_channel_push_direction { +OVS_BPF_OUT_DIR , +OVS_BPF_IN_DIR +}; + +struct ovs_bpf_port_stats { +__u64 rx_packets;/* total packets received */ +__u64 rx_bytes;/* total bytes received */ +__u64 rx_mcast_packets;/* total multicast pkts received */ +__u64 rx_mcast_bytes;/* total multicast bytes received */ +__u64 tx_packets;/* total packets transmitted */ +__u64 tx_bytes;/* total bytes transmitted */ +__u64 tx_mcast_packets;/* total multicast pkts transmitted */ +__u64 tx_mcast_bytes;/* total multicast bytes transmitted */ +}; + +struct bpf_ipv4_tun_key { +__u32 tun_id; +__u32 src_ip; +__u32 dst_ip; +__u8 tos; +__u8 ttl; +}; + +struct bpf_context { +__u32 port_id; +__u32 plum_id; +__u32 length; +__u32 arg1; +__u32 arg2; +__u32 arg3; +__u32 arg4; +__u16 vlan_tag; +__u8 hw_csum; +__u8 rsvd; +struct bpf_ipv4_tun_key tun_key; +}; + +enum { + FUNC_bpf_load_byte =3 , + FUNC_bpf_load_half, + FUNC_bpf_load_word, + FUNC_bpf_load_dword, + FUNC_bpf_load_bits, + FUNC_bpf_store_byte, + FUNC_bpf_store_half, + FUNC_bpf_store_word, + FUNC_bpf_store_dword, + FUNC_bpf_store_bits, + FUNC_bpf_channel_push_packet, + FUNC_bpf_channel_push_struct, + FUNC_bpf_forward, + FUNC_bpf_forward_self, + FUNC_bpf_forward_to_plum, + FUNC_bpf_clone_forward, + FUNC_bpf_replicate, + FUNC_bpf_checksum, + FUNC_bpf_checksum_pkt, + FUNC_bpf_csum_replace2, + FUNC_bpf_csum_replace4, + FUNC_bpf_pseudo_csum_replace2, + FUNC_bpf_pseudo_csum_replace4, + FUNC_bpf_get_usec_time, + FUNC_bpf_push_vlan, + FUNC_bpf_pop_vlan, +}; + +__u8 bpf_load_byte (struct bpf_context *ctx,__u32 off); +__u16 bpf_load_half (struct bpf_context *ctx,__u32 off); +__u32 bpf_load_word (struct bpf_context *ctx,__u32 off); +__u64 bpf_load_dword (struct bpf_context *ctx,__u32 off); +int bpf_load_bits (struct bpf_context *ctx,__u32 off,void *to,__u32 len); +void bpf_store_byte (struct bpf_context *pkt,__u32 off,__u8 val); +void bpf_store_half (struct bpf_context *pkt,__u32 off,__u16 val); +void bpf_store_word (struct bpf_context *pkt,__u32 off,__u32 val); +void bpf_store_dword (struct bpf_context *pkt,__u32 off,__u64 val); +void bpf_store_bits (struct bpf_context *pkt,__u32 off,const void *from, +__u32 len); +void bpf_channel_push_struct (struct bpf_context *pkt,__u32 struct_id, +const void *entry,__u32 len); +void bpf_channel_push_packet (struct bpf_context *pkt); +void bpf_forward (struct bpf_context *ctx,__u32 port_id); +void bpf_forward_self (struct bpf_context *pkt,__u32 port_id); +void bpf_forward_to_plum (struct bpf_context *ctx,__u32 plumid); +void bpf_clone_forward (struct bpf_context *pkt,__u32 port_id); +void bpf_replicate (struct bpf_context *ctx,__u32 replicator,__u32 src_port); +__u16 bpf_checksum (const __u8 *buf,__u32 len); +__u16 bpf_checksum_pkt (struct bpf_context *ctx,__u32 off,__u32 len); +__u16 bpf_csum_replace2 (__u16 csum,__u16 from,__u16 to); +__u16 bpf_csum_replace4 (__u16 csum,__u32 from,__u32 to); +__u16 bpf_pseudo_csum_replace2 (__u16 csum,__u16 from,__u16 to); +__u16 bpf_pseudo_csum_replace4 (__u16 csum,__u32 from,__u32 to); +__u64 bpf_get_usec_time (void ); +int bpf_push_vlan (struct bpf_context *ctx,__u16 proto,__u16 vlan); +int bpf_pop_vlan (struct bpf_context *ctx); +#endif /* _LINUX_OPENVSWITCH_H */
net/openvswitch/Makefile +6 -1
@@ -11,7 +11,12 @@ openvswitch-y := \ flow.o \ vport.o \ vport-internal_dev.o \ - vport-netdev.o + vport-netdev.o \ + dp_bpf.o \ + bpf_plum.o \ + bpf_table.o \ + bpf_replicator.o \ + bpf_callbacks.o ifneq ($(CONFIG_OPENVSWITCH_VXLAN),) openvswitch-y += vport-vxlan.o
net/openvswitch/bpf_callbacks.c new file +295 -0
295 lines not on this page · raw message
net/openvswitch/bpf_plum.c new file +931 -0
931 lines not on this page · raw message
net/openvswitch/bpf_replicator.c new file +155 -0
155 lines not on this page · raw message
net/openvswitch/bpf_table.c new file +500 -0
500 lines not on this page · raw message
net/openvswitch/datapath.c +89 -13
208 lines not on this page · raw message
net/openvswitch/datapath.h +5 -0
@@ -28,6 +28,7 @@#include "flow.h" #include "vport.h" +#include "dp_bpf.h" #define DP_MAX_PORTS USHRT_MAX#define DP_VPORT_HASH_BUCKETS 1024
@@ -83,6 +84,9 @@ struct datapath {/* Network namespace ref. */ struct net *net;#endif + +/* BPF extension */ +struct plum **plums; };/**
@@ -130,6 +134,7 @@ struct ovs_net {extern int ovs_net_id;void ovs_lock (void );void ovs_unlock (void ); +struct datapath *get_dp (struct net *net,int dp_ifindex);#ifdef CONFIG_LOCKDEP int lockdep_ovsl_is_held (void );
net/openvswitch/dp_bpf.c new file +1228 -0
731 lines not on this page · raw message
net/openvswitch/dp_bpf.h new file +160 -0
160 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
1.7.9.5
Part of the diff is not shown here. View the raw message.
Quoted 7 lines
Patch 1/2: generic BPF extension
Original A and X 32-bit BPF registers are replaced with ten 64-bit registers. bpf opcode encoding kept the same. load/store were generalized to access stack,bpf_tablesandbpf_context.
BPF program interfaces to outside world via tables that it can read and write, and viabpf_contextwhich is in/out blob of data.
Other kernel components can provide callbacks to tailor BPF to specific needs.
As has been recently pointed out on some of the NetBSD lists one of the points about BPF is that the filters are deterministic and easily proven to both terminate and have no unwanted side effects.
The functionality you are proposing breaks both of these assumptions.
It is understood that parsing IPv6 headers is currently impossible (needs loops of some form) but a specific helper instruction is probably a better solution.
What you seem to be proposing is a completely different beast, so you should call it something else - it isn't BPF.
Whether the Linux kernel needs a (another?) byte code interpreter is a separate issue.
David
Quoted 9 lines · David Laight
Quoted 8 lines
Patch 1/2: generic BPF extension
Original A and X 32-bit BPF registers are replaced with ten 64-bit registers. bpf opcode encoding kept the same. load/store were generalized to access stack,bpf_tablesandbpf_context.
BPF program interfaces to outside world via tables that it can read and write, and viabpf_contextwhich is in/out blob of data.
Other kernel components can provide callbacks to tailor BPF to specific needs.
Quoted 5 lines
As has been recently pointed out on some of the NetBSD lists one of the points about BPF is that the filters are deterministic and easily proven to both terminate and have no unwanted side effects.
The functionality you are proposing breaks both of these assumptions.
Proposed BPF extensions keep both of these assumptions. See bpf_check.c It guarantees that BPF program terminates, all memory/register accesses are valid,
function arguments are verified, no unknown insns, register/stack is initialized before read, aligned, etc
BPF checker algorithm is not as trivial as it was before, but still straightforward and simple.
It helped us catch some interesting bugs in BPF GCC backend. In one case we miscalculated
branch target by one insn and since register read came before it was written, BPF checker caught it.
In another case we improperly coded branch conditions in cbranchdi4 (see gcc/config/bpf/bpf.md on github). Again it caught it.
Using compiler is not mandatory. One can code BPF in assembler in the same way it was done before,
but doing it in C is easier to understand.
Thanks
Alexei