BPF and OVS extensions
Subsystems (7)
cover BPF and OVS extensions
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 | 923 ++++++++++++++++++++++++++++ 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 | 1221 ++++++++++++++++++++++++++++++++++++++ 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, 5839 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
RFC PATCH 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 2/2 extend OVS to use BPF programs on flow miss
In reply to Alexei StarovoitovOriginal 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 | 923 ++++++++++++++++++++++++++++ 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 | 1221 ++++++++++++++++++++++++++++++++++++++ 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, 3524 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 +923 -0
923 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 +1221 -0
739 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.