eBPF syscall, verifier, testsuite
Subsystems (10)
v11 cover eBPF syscall, verifier, testsuite
Hi David,
I've managed to reduce this set to 12:
Patches 1-4 establish BPF syscall shell for maps and programs. Patches 5-10 add verifier step by step
Patch 11 exposes existing instruction macros to user space Patch 12 adds test stubs and verifier testsuite from user space
I don't know how to reduce it further. Drop verifier and have programs loaded without verification? Sounds wrong. If anyone has other ideas, I'll gladly reduce it further.
Note that patches 1,3,4,7 add commands and attributes to the syscall while being backwards compatible from each other, which should demonstrate how other commands can be added in the future.
Daniel,bpf_common.h patch (that we discussed earlier) I didn't include here to reduce the number of patches. It can come next.
For those who have looked at the last set of 28 patches, the difference is:
- moved attaching to tracing and sockets to future patches
- moved hash table map type implementation to future
- split verifier further and moved LD_ABS checks and state prunning to future
- instead of running verifier testsuite on real tracing programs added test_stub.c with fake maps, context and helper functions to test verifier only
- rebased
Note, after this set the programs can be loaded for testing only. They cannot be attached to any events. This will come in the next set.
As requested by Andy and others, here is the man page:
BPF(2) Linux Programmer's Manual BPF(2)
NAME
bpf - perform a command on eBPF map or program
SYNOPSIS
#include <linux/bpf.h>
int bpf(int cmd, union bpf_attr *attr, unsigned int size);DESCRIPTION
bpf() syscall is a multiplexor for a range of different operations on eBPF which can be characterized as "universal in-kernel virtual machine". eBPF is similar to original Berkeley Packet Filter (or "clas- sic BPF") used to filter network packets. Both statically analyze the programs before loading them into the kernel to ensure that programs cannot harm the running system.
eBPF extends classic BPF in multiple ways including ability to call in- kernel helper functions and access shared data structures like eBPF maps. The programs can be written in a restricted C that is compiled into eBPF bytecode and executed on the eBPF virtual machine or JITed into native instruction set.
eBPF Design/Architecture
eBPF maps is a generic storage of different types. User process can
create multiple maps (with key/value being opaque bytes of data) and access them via file descriptor. In parallel eBPF programs can access maps from inside the kernel. It's up to user process and eBPF program to decide what they store inside maps.
eBPF programs are similar to kernel modules. They are loaded by the user process and automatically unloaded when process exits. Each eBPF program is a safe run-to-completion set of instructions. eBPF verifier statically determines that the program terminates and is safe to exe- cute. During verification the program takes a hold of maps that it intends to use, so selected maps cannot be removed until the program is unloaded. The program can be attached to different events. These events can be packets, tracepoint events and other types in the future. A new event triggers execution of the program which may store information about the event in the maps. Beyond storing data the programs may call into in-kernel helper functions which may, for example, dump stack, do trace_printk or other forms of live kernel debugging. The same program can be attached to multiple events. Different programs can access the same map:
tracepoint tracepoint tracepoint sk_buff sk_buff
event A event B event C on eth0 on eth1
| | | | |
| | | | |
--> tracing <-- tracing socket socket
prog_1 prog_2 prog_3 prog_4
| | | |
|--- -----| |-------| map_3
map_1 map_2
Syscall Arguments
bpf() syscall operation is determined by cmd which can be one of the following:
BPF_MAP_CREATE
Create a map with given type and attributes and return map FD
BPF_MAP_LOOKUP_ELEM
Lookup element by key in a given map and return its value
BPF_MAP_UPDATE_ELEM
Create or update element (key/value pair) in a given map
BPF_MAP_DELETE_ELEM
Lookup and delete element by key in a given map
BPF_MAP_GET_NEXT_KEY
Lookup element by key in a given map and return key of next ele- ment
BPF_PROG_LOAD
Verify and load eBPF program
attr is a pointer to a union of type bpf_attr as defined below.
size is the size of the union.
union bpf_attr {
struct { /* anonymous struct used by BPF_MAP_CREATE command */
enum bpf_map_type map_type;
__u32 key_size; /* size of key in bytes */
__u32 value_size; /* size of value in bytes */
__u32 max_entries; /* max number of entries in a map */
};
struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */
int map_fd;
void *key;
union {
void *value;
void *next_key;
};
};
struct { /* anonymous struct used by BPF_PROG_LOAD command */
enum bpf_prog_type prog_type;
__u32 insn_cnt;
const struct bpf_insn *insns;
const char *license;
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
void *log_buf; /* user supplied buffer */
};
};
eBPF maps
maps is a generic storage of different types for sharing data between kernel and userspace.
Any map type has the following attributes:
. type
. max number of elements
. key size in bytes
. value size in bytes
The following wrapper functions demonstrate how this syscall can be used to access the maps. The functions use the cmd argument to invoke different operations.
BPF_MAP_CREATE
int bpf_create_map(enum bpf_map_type map_type, int key_size,
int value_size, int max_entries)
{
union bpf_attr attr = {
.map_type = map_type,
.key_size = key_size,
.value_size = value_size,
.max_entries = max_entries
};
return bpf(BPF_MAP_CREATE, &attr, sizeof(attr));
}
bpf() syscall creates a map of map_type type and given
attributes key_size, value_size, max_entries. On success it
returns process-local file descriptor or negative error other- wise.
BPF_MAP_LOOKUP_ELEM
int bpf_lookup_elem(int fd, void *key, void *value) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
.value = value,
};
return bpf(BPF_MAP_LOOKUP_ELEM, &attr, sizeof(attr));
}
bpf() syscall looks up an element with given key in a map fd. If element is found it returns zero and stores element's value into value. Otherwise negative error is returned.
BPF_MAP_UPDATE_ELEM
int bpf_update_elem(int fd, void *key, void *value) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
.value = value,
};
return bpf(BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
}
The call creates or updates element with given key/value in a map fd. On success it returns zero or negative error otherwise.
BPF_MAP_DELETE_ELEM
int bpf_delete_elem(int fd, void *key) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
};
return bpf(BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
}
The call deletes an element in a map fd with given key.
BPF_MAP_GET_NEXT_KEY
int bpf_get_next_key(int fd, void *key, void *next_key) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
.next_key = next_key,
};
return bpf(BPF_MAP_GET_NEXT_KEY, &attr, sizeof(attr));
}
The call looks up an element by key in a given map fd and returns key of next element into next_key pointer. On success it returns zero or negative error otherwise. This method can be used to iterate over all elements of the map.
close(map_fd)
will delete the map map_fd. Exiting process will delete all maps automatically.
In the future maps can have different types: hash, array, bloom filter, radix-tree, but currently only hash type is supported:
enum bpf_map_type {
BPF_MAP_TYPE_UNSPEC,
BPF_MAP_TYPE_HASH,
};
eBPF programs
BPF_PROG_LOAD
This cmd is used to load eBPF program into the kernel.
char bpf_log_buf[LOG_BUF_SIZE];
int bpf_prog_load(enum bpf_prog_type prog_type,
const struct bpf_insn *insns, int insn_cnt, const char *license)
{
union bpf_attr attr = {
.prog_type = prog_type,
.insns = insns,
.insn_cnt = insn_cnt,
.license = license,
.log_buf = bpf_log_buf,
.log_size = LOG_BUF_SIZE,
.log_level = 1,
};
return bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
}
prog_type one of the available program types:
enum bpf_prog_type {
BPF_PROG_TYPE_UNSPEC, BPF_PROG_TYPE_SOCKET_FILTER, BPF_PROG_TYPE_TRACING_FILTER,
};
insns array of "struct bpf_insn" instructions
insn_cnt number of instructions in the program
license license string, which must be GPL compatible to call helper functions marked gpl_only
log_buf user supplied buffer that in-kernel verifier is using to store verification log
log_size size of user buffer
log_level verbosity level of eBPF verifier, where zero means no logs provided
close(prog_fd)
will unload eBPF program
The maps are accesible from programs and generally tie the two
together. Programs process various events (like tracepoint, kprobe,
packets) and store the data into maps. User space fetches data from
maps. Either the same or a different map may be used by user space as
configuration space to alter program behavior on the fly.
Events
Once an eBPF program is loaded, it can be attached to an event. Various kernel subsystems have different ways to do so. For example:
setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd, sizeof(prog_fd)); will attach the program prog_fd to socket sock which was received by prior call to socket().
ioctl(event_fd, PERF_EVENT_IOC_SET_BPF, prog_fd);
will attach the program prog_fd to perf event event_fd which was received by prior call to perf_event_open().
Another way to attach the program to a tracing event is:
event_fd = open("/sys/kernel/debug/tracing/events/skb/kfree_skb/filter"); write(event_fd, "bpf-123"); /* where 123 is eBPF program FD */ /* here program is attached and will be triggered by events */ close(event_fd); /* to detach from event */
EXAMPLES
/* eBPF+sockets example:
* 1. create map with maximum of 2 elements
* 2. set map[6] = 0 and map[17] = 0
* 3. load eBPF program that counts number of TCP and UDP packets received
* via map[skb->ip->proto]++
* 4. attach prog_fd to raw socket via setsockopt()
* 5. print number of received TCP/UDP packets every second
*/
int main(int ac, char **av)
{
static struct bpf_insn prog[] = {
BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
BPF_LD_ABS(BPF_B, 14 + 9 /* R0 = ip->proto */),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */
BPF_XADD(BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */
BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */
BPF_EXIT_INSN(),
};
int sock, map_fd, prog_fd, key;
long long value = 0, tcp_cnt, udp_cnt;
map_fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value), 2);
if (map_fd < 0) {
printf("failed to create map '%s'\n", strerror(errno));
/* likely not run as root */
return 1;
}
key = 6; /* tcp */
assert(bpf_update_elem(map_fd, &key, &value) == 0);
key = 17; /* udp */
assert(bpf_update_elem(map_fd, &key, &value) == 0);
prog[5].imm = map_fd;
prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, prog, sizeof(prog),
"GPL");
assert(prog_fd >= 0);
sock = open_raw_sock("lo");
assert(setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd,
sizeof(prog_fd)) == 0);
for (;;) {
key = 6;
assert(bpf_lookup_elem(map_fd, &key, &tcp_cnt) == 0);
key = 17;
assert(bpf_lookup_elem(map_fd, &key, &udp_cnt) == 0);
printf("TCP %lld UDP %lld packets0, tcp_cnt, udp_cnt);
sleep(1);
}
return 0;
}RETURN VALUE
For a successful call, the return value depends on the operation:
BPF_MAP_CREATE
The new file descriptor associated with eBPF map.
BPF_PROG_LOAD
The new file descriptor associated with eBPF program.
All other commands
Zero.
On error, -1 is returned, and errno is set appropriately.
ERRORS
EPERM bpf() syscall was made without sufficient privilege (without the
CAP_SYS_ADMIN capability).
ENOMEM Cannot allocate sufficient memory.
EBADF fd is not an open file descriptor
EFAULT One of the pointers ( key or value or log_buf or insns ) is out-
side accessible address space.
EINVAL The value specified in cmd is not recognized by this kernel.
EINVAL For BPF_MAP_CREATE, either map_type or attributes are invalid.
EINVAL For BPF_MAP_*_ELEM commands, some of the fields of "union
bpf_attr" unused by this command are not set to zero.
EINVAL For BPF_PROG_LOAD, attempt to load invalid program (unrecognized
instruction or uses reserved fields or jumps out of range or loop detected or calls unknown function).
EACCES For BPF_PROG_LOAD, though program has valid instructions, it was
rejected, since it was deemed unsafe (may access disallowed mem- ory region or uninitialized stack/register or function con- straints don't match actual types or misaligned access). In such case it is recommended to call bpf() again with log_level = 1 and examine log_buf for specific reason provided by verifier.
ENOENT For BPF_MAP_LOOKUP_ELEM or BPF_MAP_DELETE_ELEM, indicates that
element with given key was not found.
E2BIG program is too large.
NOTES
These commands may be used only by a privileged process (one having the CAP_SYS_ADMIN capability).
SEE ALSO
eBPF architecture and instruction set is explained in Documenta- tion/networking/filter.txt
Linux 2014-09-01 BPF(2)
PATCH v11 1/12 bpf: introduce BPF syscall and maps
BPF syscall is a multiplexor for a range of different operations on eBPF. This patch introduces syscall with single command to create a map. Next patch adds commands to access maps.
'maps' is a generic storage of different types for sharing data between kernel and userspace.
Userspace example:
/* this syscall wrapper creates a map with given type and attributes
* and returns map_fd on success.
* use close(map_fd) to delete the map
*/
int bpf_create_map(enum bpf_map_type map_type, int key_size,
int value_size, int max_entries)
{
union bpf_attr attr = {
.map_type = map_type,
.key_size = key_size,
.value_size = value_size,
.max_entries = max_entries
};
return bpf(BPF_MAP_CREATE, &attr, sizeof(attr));
}
syscall is using 'union bpf_attr' to be backwards compatible with future extensions. Different syscall commands will use different attributes.
More details in Documentation/networking/filter.txt and in manpage
--- Documentation/networking/filter.txt | 39 +++++++++ include/linux/bpf.h | 41 ++++++++++ include/uapi/linux/bpf.h | 24 ++++++ kernel/bpf/Makefile | 2 +- kernel/bpf/syscall.c | 149 +++++++++++++++++++++++++++++++++++ 5 files changed, 254 insertions(+), 1 deletion(-) create mode 100644 include/linux/bpf.h create mode 100644 kernel/bpf/syscall.c
Documentation/networking/filter.txt +39 -0
@@ -1001,6 +1001,45 @@ instruction that loads 64-bit immediate value into a dst_reg. Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads 32-bit immediate value into a register. +eBPF maps +--------- +'maps' is a generic storage of different types for sharing data between kernel +and userspace. + +The maps are accessed from user space via BPF syscall, which has commands: +- create a map with given type and attributes + map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) + using attr->map_type, attr->key_size, attr->value_size, attr->max_entries + returns process-local file descriptor or negative error + +- lookup key in a given map + err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) + using attr->map_fd, attr->key, attr->value + returns zero and stores found elem into value or negative error + +- create or update key/value pair in a given map + err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) + using attr->map_fd, attr->key, attr->value + returns zero or negative error + +- find and delete element by key in a given map + err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) + using attr->map_fd, attr->key + +- to delete map: close(fd) + Exiting process will delete maps automatically + +userspace programs use this syscall to create/access maps that eBPF programs +are concurrently updating. + +maps can have different types: hash, array, bloom filter, radix-tree, etc. + +The map is defined by: + . type + . max number of elements + . key size in bytes + . value size in bytes + Testing -------
include/linux/bpf.h new file +41 -0
41 lines not on this page · raw message
include/uapi/linux/bpf.h +24 -0
@@ -62,4 +62,28 @@ struct bpf_insn { __s32 imm; /* signed immediate constant */ }; +/* BPF syscall commands */ +enum bpf_cmd { +/* create a map with given type and attributes +* fd = bpf(BPF_MAP_CREATE, union bpf_attr *, u32 size) +* returns fd or negative error +* map is deleted when fd is closed +*/ +BPF_MAP_CREATE , +}; + +enum bpf_map_type { +BPF_MAP_TYPE_UNSPEC , +}; + +union bpf_attr { +struct {/* anonymous struct used by BPF_MAP_CREATE command */ +enum bpf_map_type map_type; +__u32 key_size;/* size of key in bytes */ +__u32 value_size;/* size of value in bytes */ +__u32 max_entries;/* max number of entries in a map */ +#define BPF_MAP_CREATE_LAST_FIELD max_entries + }; +}; +#endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/Makefile +1 -1
@@ -1 +1 @@ -obj-y := core.o +obj-y := core.o syscall.o
kernel/bpf/syscall.c new file +149 -0
149 lines not on this page · raw message
Signature · 1 line
1.7.9.5
PATCH v11 2/12 bpf: enable bpf syscall on x64 and i386
In reply to Alexei Starovoitovdone as separate commit to ease conflict resolution
--- arch/x86/syscalls/syscall_32.tbl | 1 + arch/x86/syscalls/syscall_64.tbl | 1 + include/linux/syscalls.h | 3 ++- include/uapi/asm-generic/unistd.h | 4 +++- kernel/sys_ni.c | 3 +++ 5 files changed, 10 insertions(+), 2 deletions(-)
arch/x86/syscalls/syscall_32.tbl +1 -0
@@ -363,3 +363,4 @@ 354 i386 seccomp sys_seccomp 355 i386 getrandom sys_getrandom 356 i386 memfd_create sys_memfd_create +357 i386 bpf sys_bpf
arch/x86/syscalls/syscall_64.tbl +1 -0
@@ -327,6 +327,7 @@ 318 common getrandom sys_getrandom 319 common memfd_create sys_memfd_create 320 common kexec_file_load sys_kexec_file_load +321 common bpf sys_bpf # # x32-specific system call numbers start at 512 to avoid cache impact
include/linux/syscalls.h +2 -1
@@ -65,6 +65,7 @@ struct old_linux_dirent;struct perf_event_attr ;struct file_handle ;struct sigaltstack ; +union bpf_attr ;#include <linux/types.h> #include <linux/aio_abi.h>
@@ -875,5 +876,5 @@ asmlinkage long sys_seccomp(unsigned int op, unsigned int flags, const char __user *uargs);asmlinkage long sys_getrandom (char __user *buf,size_t count,unsigned int flags); - +asmlinkage long sys_bpf (int cmd,union bpf_attr *attr,unsigned int size);#endif
include/uapi/asm-generic/unistd.h +3 -1
@@ -705,9 +705,11 @@ __SYSCALL(__NR_seccomp, sys_seccomp) __SYSCALL(__NR_getrandom, sys_getrandom)#define __NR_memfd_create 279 __SYSCALL(__NR_memfd_create, sys_memfd_create) +#define __NR_bpf 280 +__SYSCALL(__NR_bpf, sys_bpf)#undef __NR_syscalls -#define __NR_syscalls 280 +#define __NR_syscalls 281/* * All syscalls below here should go away really,
kernel/sys_ni.c +3 -0
@@ -218,3 +218,6 @@ cond_syscall(sys_kcmp);/* operate on Secure Computing state */ cond_syscall (sys_seccomp); + +/* access BPF programs and maps */ +cond_syscall (sys_bpf);
Signature · 1 line
1.7.9.5
PATCH v11 3/12 bpf: add lookup/update/delete/iterate methods to BPF maps
In reply to Alexei Starovoitov'maps' is a generic storage of different types for sharing data between kernel and userspace.
The maps are accessed from user space via BPF syscall, which has commands:
- create a map with given type and attributes
fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) returns fd or negative error
- lookup key in a given map referenced by fd
err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero and stores found elem into value or negative error
- create or update key/value pair in a given map
err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero or negative error
- find and delete element by key in a given map
err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key
- iterate map elements (based on input key return next_key) err = bpf(BPF_MAP_GET_NEXT_KEY, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->next_key
- close(fd) deletes the map
--- include/linux/bpf.h | 8 ++ include/uapi/linux/bpf.h | 42 +++++++++ kernel/bpf/syscall.c | 219 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 269 insertions(+)
include/linux/bpf.h +8 -0
@@ -9,6 +9,7 @@#include <uapi/linux/bpf.h> #include <linux/workqueue.h> +#include <linux/file.h> struct bpf_map ;
@@ -17,6 +18,12 @@ struct bpf_map_ops {/* funcs callable from userspace (via syscall) */ struct bpf_map *(*map_alloc)(union bpf_attr *attr);void (*map_free)(struct bpf_map *); +int (*map_get_next_key)(struct bpf_map *map,void *key,void *next_key); + +/* funcs callable from userspace and from eBPF programs */ +void *(*map_lookup_elem)(struct bpf_map *map,void *key); +int (*map_update_elem)(struct bpf_map *map,void *key,void *value); +int (*map_delete_elem)(struct bpf_map *map,void *key); };struct bpf_map {
@@ -37,5 +44,6 @@ struct bpf_map_type_list {void bpf_register_map_type (struct bpf_map_type_list *tl);void bpf_map_put (struct bpf_map *map); +struct bpf_map *bpf_map_get (struct fd f);#endif /* _LINUX_BPF_H */
include/uapi/linux/bpf.h +42 -0
54 lines not on this page · raw message
kernel/bpf/syscall.c +219 -0
237 lines not on this page · raw message
Signature · 1 line
1.7.9.5
PATCH v11 4/12 bpf: expand BPF syscall with program load/unload
In reply to Alexei StarovoitoveBPF programs are similar to kernel modules. They are loaded by the user process and automatically unloaded when process exits. Each eBPF program is a safe run-to-completion set of instructions. eBPF verifier statically determines that the program terminates and is safe to execute.
The following syscall wrapper can be used to load the program:
int bpf_prog_load(enum bpf_prog_type prog_type,
const struct bpf_insn *insns, int insn_cnt, const char *license)
{
union bpf_attr attr = {
.prog_type = prog_type,
.insns = insns,
.insn_cnt = insn_cnt,
.license = license,
};
return bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
}
where 'insns' is an array of eBPF instructions and 'license' is a string that must be GPL compatible to call helper functions marked gpl_only
Upon succesful load the syscall returns prog_fd.
Use close(prog_fd) to unload the program.
User space tests and examples follow in the later patches
--- include/linux/bpf.h | 36 ++++++++++ include/linux/filter.h | 7 +- include/uapi/linux/bpf.h | 27 ++++++++ kernel/bpf/syscall.c | 171 ++++++++++++++++++++++++++++++++++++++++++++++ net/core/filter.c | 2 + 5 files changed, 242 insertions(+), 1 deletion(-)
include/linux/bpf.h +36 -0
@@ -46,4 +46,40 @@ void bpf_register_map_type(struct bpf_map_type_list *tl);void bpf_map_put (struct bpf_map *map);struct bpf_map *bpf_map_get (struct fd f); +/* eBPF function prototype used by verifier to allow BPF_CALLs from eBPF programs +* to in-kernel helper functions and for adjusting imm32 field in BPF_CALL +* instructions after verifying +*/ +struct bpf_func_proto { +u64 (*func)(u64 r1,u64 r2,u64 r3,u64 r4,u64 r5); +bool gpl_only; +}; + +struct bpf_verifier_ops { +/* return eBPF function prototype for verification */ +const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id); +}; + +struct bpf_prog_type_list { +struct list_head list_node; +struct bpf_verifier_ops *ops; +enum bpf_prog_type type; +}; + +void bpf_register_prog_type (struct bpf_prog_type_list *tl); + +struct bpf_prog_info { +atomic_t refcnt; +bool is_gpl_compatible; +enum bpf_prog_type prog_type; +struct bpf_verifier_ops *ops; +struct bpf_map **used_maps; +u32 used_map_cnt; +}; + +struct bpf_prog ; + +void bpf_prog_put (struct bpf_prog *prog); +struct bpf_prog *bpf_prog_get (u32 ufd); +#endif /* _LINUX_BPF_H */
include/linux/filter.h +6 -1
@@ -15,6 +15,7 @@struct sk_buff ;struct sock ;struct seccomp_data ; +struct bpf_prog_info ;/* ArgX, context and stack frame pointer register positions. Note, * Arg1, Arg2, Arg3, etc are used as argument mappings of function
@@ -302,8 +303,12 @@ struct bpf_work_struct {struct bpf_prog {u16 pages;/* Number of allocated pages */ bool jited;/* Is our filter JIT'ed? */ +bool has_info;/* whether 'info' is valid */ u32 len;/* Number of filter blocks */ -struct sock_fprog_kern *orig_prog;/* Original BPF program */ +union { +struct sock_fprog_kern *orig_prog;/* Original BPF program */ +struct bpf_prog_info *info; + };struct bpf_work_struct *work;/* Deferred free work struct */ unsigned int (*bpf_func)(const struct sk_buff *skb,const struct bpf_insn *filter);
include/uapi/linux/bpf.h +27 -0
@@ -99,12 +99,23 @@ enum bpf_cmd {* returns zero and stores next key or negative error */ BPF_MAP_GET_NEXT_KEY, + +/* verify and load eBPF program +* prog_fd = bpf(BPF_PROG_LOAD, union bpf_attr *attr, u32 size) +* Using attr->prog_type, attr->insns, attr->license +* returns fd or negative error +*/ + BPF_PROG_LOAD, };enum bpf_map_type {BPF_MAP_TYPE_UNSPEC , }; +enum bpf_prog_type { +BPF_PROG_TYPE_UNSPEC , +}; +union bpf_attr {struct {/* anonymous struct used by BPF_MAP_CREATE command */ enum bpf_map_type map_type;
@@ -126,6 +137,22 @@ union bpf_attr {#define BPF_MAP_DELETE_ELEM_LAST_FIELD key#define BPF_MAP_GET_NEXT_KEY_LAST_FIELD next_key }; + +struct {/* anonymous struct used by BPF_PROG_LOAD command */ +enum bpf_prog_type prog_type; +__u32 insn_cnt; +const struct bpf_insn __user *insns; +const char __user *license; +#define BPF_PROG_LOAD_LAST_FIELD license + }; +}; + +/* integer value in 'imm' field of BPF_CALL instruction selects which helper +* function eBPF program intends to call +*/ +enum bpf_func_id { + BPF_FUNC_unspec, + __BPF_FUNC_MAX_ID, };#endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/syscall.c +171 -0
189 lines not on this page · raw message
net/core/filter.c +2 -0
@@ -835,6 +835,7 @@ static void bpf_release_orig_filter(struct bpf_prog *fp) {struct sock_fprog_kern *fprog = fp->orig_prog; +BUG_ON (fp->has_info);if (fprog) {kfree (fprog->filter);kfree (fprog);
@@ -973,6 +974,7 @@ static struct bpf_prog *bpf_prepare_filter(struct bpf_prog *fp) fp->bpf_func =NULL ; fp->jited = false; + fp->has_info = false; err =bpf_check_classic (fp->insns, fp->len);if (err) {
Signature · 1 line
1.7.9.5
Re: [PATCH v11 net-next 04/12] bpf: expand BPF syscall with program load/unload
Quoted 28 lines · Alexei Starovoitov
eBPF programs are similar to kernel modules. They are loaded by the user process and automatically unloaded when process exits. Each eBPF program is a safe run-to-completion set of instructions. eBPF verifier statically determines that the program terminates and is safe to execute.
The following syscall wrapper can be used to load the program:
int bpf_prog_load(enumbpf_prog_typeprog_type,
const structbpf_insn*insns, intinsn_cnt, const char *license)
{
unionbpf_attrattr = {
.prog_type =prog_type,
.insns = insns,
.insn_cnt =insn_cnt,
.license = license,
};return
bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
}
where 'insns' is an array of eBPF instructions and 'license' is a string that must be GPL compatible to call helper functions markedgpl_onlyUpon succesful load the syscall returns
prog_fd.
Useclose(prog_fd)to unload the program.User space tests and examples follow in the later patches
...
Quoted 13 lines
include/linux/filter.h +1
-0@@ -15,6 +15,7 @@struct sk_buff ;struct sock ;struct seccomp_data ; +struct bpf_prog_info ;/* ArgX, context and stack frame pointer register positions. Note, * Arg1, Arg2, Arg3, etc are used as argument mappings of function
include/linux/filter.h struct bpf_work_struct { · line 311
Quoted 10 lines
include/linux/filter.h +5
-1@@ -302,8 +303,12 @@ struct bpf_work_struct {struct bpf_prog {u16 pages;/* Number of allocated pages */ bool jited;/* Is our filter JIT'ed? */ +bool has_info;/* whether 'info' is valid */ u32 len;/* Number of filter blocks */ -struct sock_fprog_kern *orig_prog;/* Original BPF program */ +union { +struct sock_fprog_kern *orig_prog;/* Original BPF program */ +struct bpf_prog_info *info; + };
All members of this bpf_prog_info should go into bpf_work_struct, as I have intended this to be a ancillary structure here. Since we already allocate this anyway, you can reduce complexity by doing the additional allocation plus remove the has_info member.
Quoted 8 lines
include/linux/filter.h +0
-0struct bpf_work_struct *work;/* Deferred free work struct */ unsigned int (*bpf_func)(const struct sk_buff *skb,const struct bpf_insn *filter);include/uapi/linux/bpf.h +0
-0@@ -99,12 +99,23 @@ enum bpf_cmd {
...
Quoted 3 lines
+/* called by sockets/tracing/seccomp before attaching program to an event
+ * pairs withbpf_prog_put()
+ */
But seccomp already does refcounting on each BPF filter. Or, is the intention to remove this from seccomp?
Quoted 14 lines
include/uapi/linux/bpf.h +14
-0+struct bpf_prog *bpf_prog_get (u32 ufd) +{ +struct fd f =fdget (ufd); +struct bpf_prog *prog; + + prog =get_prog (f); + +if (IS_ERR (prog)) +return prog; + +atomic_inc (&prog->info->refcnt); +fdput (f); +return prog; +}
...
net/core/filter.c static void bpf_release_orig_filter(struct bpf_prog *fp) · line 838
Quoted 9 lines
net/core/filter.c +1
-0@@ -835,6 +835,7 @@ static void bpf_release_orig_filter(struct bpf_prog *fp) {struct sock_fprog_kern *fprog = fp->orig_prog; +BUG_ON (fp->has_info);
Why BUG_ON() (also in so many other places)?
Quoted 12 lines
net/core/filter.c +1
-0if (fprog) {kfree (fprog->filter);kfree (fprog);@@ -973,6 +974,7 @@ static struct bpf_prog *bpf_prepare_filter(struct bpf_prog *fp) fp->bpf_func =NULL ; fp->jited = false; + fp->has_info = false; err =bpf_check_classic (fp->insns, fp->len);if (err) {
Re: [PATCH v11 net-next 04/12] bpf: expand BPF syscall with program load/unload
Quoted 10 lines · Daniel Borkmann
include/linux/filter.h struct bpf_work_struct { · line 311
Quoted 8 lines
(quoted diff) +3
-1+ bool has_info; /* whether 'info' is valid u32 len; /* Number of filter blocks - struct sock_fprog_kern *orig_prog; /* Original BPF program */ + union { + struct sock_fprog_kern *orig_prog; /* Original BPFprogram */
include/linux/filter.h +2
-0+struct bpf_prog_info *info; + };
Quoted 4 lines
All members of this
bpf_prog_infoshould go intobpf_work_struct, as I have intended this to be a ancillary structure here. Since we already allocate this anyway, you can reduce complexity by doing the additional allocation plus remove thehas_infomember.
that's doable, but won't you be worried about extra 6 fields in there that only used by native eBPF programs?
I kept them separate not to introduce any overhead to classic programs.
Quoted 2 lines
Quoted 2 lines
struct
bpf_work_struct*work; /* Deferred free work
struct */
Also we'd need to rename it, adjust the comment above and move into linux/bpf.h, since it don't want to overload linux/filter.h with native eBPF stuff. In my mind filter.h is for classic and socket things, whereas bpf.h is net-less. So I'm 50/50 on this one.
Dropping has_info flag is definitely a plus.
Rename 'struct bpf_work_struct' to 'struct bpf_prog_info' ? bpf_prog_aux_data? bpf_prog_extra ?
Naming is hard.
Quoted 2 lines
But seccomp already does refcounting on each BPF filter. Or, is the intention to remove this from seccomp?
seccomp refcounts its own wrapper struct on top of classic bpf. It gets incremented when task is forked, so I suspect it will be needed even when seccomp moves to native.
Note that 'struct sk_filter' has its own refcnt as well which gets incremented when socket is cloned. It's independent from eBPF program refcnt which is part of 'struct bpf_prog_info', since the same eBPF program can be attached to multiple sockets. So both are needed. Seccomp may want to attach the same eBPF program to multiple tasks as well to save some memory.
In classic BPF we may open multiple sockets and attach the same classic BPF prog to all. prog is allocated multiple times. JIT is called multiple times, but overhead is not huge. For eBPF is not an option. In eBPF+tracing single program may be attached to hundreds of events.
Quoted 3 lines
Quoted 1 line
+
BUG_ON(fp->has_info);Why
BUG_ON()(also in so many other places)?
because struct bpf_prog can be created in many different ways and I had a painful bug here while developing. I think it can be dropped now.
PATCH v11 5/12 bpf: handle pseudo BPF_CALL insn
In reply to Alexei Starovoitovin native eBPF programs userspace is using pseudo BPF_CALL instructions which encode one of 'enum bpf_func_id' inside insn->imm field. Verifier checks that program using correct function arguments to given func_id. If all checks passed, kernel needs to fixup BPF_CALL->imm fields by replacing func_id with in-kernel function pointer.
eBPF interpreter just calls the function.
In-kernel eBPF users continue to use generic BPF_CALL.
--- kernel/bpf/syscall.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+)
kernel/bpf/syscall.c +37 -0
@@ -339,6 +339,40 @@ void bpf_register_prog_type(struct bpf_prog_type_list *tl)list_add (&tl->list_node, &bpf_prog_types); } +/* fixup insn->imm field of bpf_call instructions: +* if (insn->imm == BPF_FUNC_map_lookup_elem) +* insn->imm = bpf_map_lookup_elem - __bpf_call_base; +* else if (insn->imm == BPF_FUNC_map_update_elem) +* insn->imm = bpf_map_update_elem - __bpf_call_base; +* else ... +* +* this function is called after eBPF program passed verification +*/ +static void fixup_bpf_calls (struct bpf_prog *prog) +{ +const struct bpf_func_proto *fn; +int i; + +for (i =0 ; i < prog->len; i++) { +struct bpf_insn *insn = &prog->insnsi[i]; + +if (insn->code == (BPF_JMP |BPF_CALL )) { +/* we reach here when program has bpf_call instructions +* and it passed bpf_check(), means that +* ops->get_func_proto must have been supplied, check it +*/ +BUG_ON (!prog->info->ops->get_func_proto); + + fn = prog->info->ops->get_func_proto (insn->imm); +/* all functions that have prototype and verifier allowed +* programs to call them, must be real in-kernel functions +*/ +BUG_ON (!fn->func); + insn->imm = fn->func - __bpf_call_base; + } + } +} +/* drop refcnt on maps used by eBPF program and free auxilary data */ static void free_bpf_prog_info (struct bpf_prog_info *info) {
@@ -466,6 +500,9 @@ static int bpf_prog_load(union bpf_attr *attr)if (err <0 ) goto free_prog_info; +/* fixup BPF_CALL->imm field */ +fixup_bpf_calls (prog); +/* eBPF program is ready to be JITed */ bpf_prog_select_runtime (prog);
Signature · 1 line
1.7.9.5
PATCH v11 6/12 bpf: verifier (add docs)
In reply to Alexei Starovoitovthis patch adds all of eBPF verfier documentation and empty bpf_check()
The end goal for the verifier is to statically check safety of the program.
Verifier will catch:
- loops
- out of range jumps
- unreachable instructions
- invalid instructions
- uninitialized register access
- uninitialized stack access
- misaligned stack access
- out of range stack access
- invalid calling convention
More details in Documentation/networking/filter.txt
--- Documentation/networking/filter.txt | 224 +++++++++++++++++++++++++++++++++++ include/linux/bpf.h | 2 + kernel/bpf/Makefile | 2 +- kernel/bpf/syscall.c | 2 +- kernel/bpf/verifier.c | 133 +++++++++++++++++++++ 5 files changed, 361 insertions(+), 2 deletions(-) create mode 100644 kernel/bpf/verifier.c
Documentation/networking/filter.txt +224 -0
@@ -1001,6 +1001,99 @@ instruction that loads 64-bit immediate value into a dst_reg. Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads 32-bit immediate value into a register. +eBPF verifier +------------- +The safety of the eBPF program is determined in two steps. + +First step does DAG check to disallow loops and other CFG validation. +In particular it will detect programs that have unreachable instructions. +(though classic BPF checker allows them) + +Second step starts from the first insn and descends all possible paths. +It simulates execution of every insn and observes the state change of +registers and stack. + +At the start of the program the register R1 contains a pointer to context +and has type PTR_TO_CTX. +If verifier sees an insn that does R2=R1, then R2 has now type +PTR_TO_CTX as well and can be used on the right hand side of expression. +If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=UNKNOWN_VALUE, +since addition of two valid pointers makes invalid pointer. +(In 'secure' mode verifier will reject any type of pointer arithmetic to make +sure that kernel addresses don't leak to unprivileged users) + +If register was never written to, it's not readable: + bpf_mov R0 = R2 + bpf_exit +will be rejected, since R2 is unreadable at the start of the program. + +After kernel function call, R1-R5 are reset to unreadable and +R0 has a return type of the function. + +Since R6-R9 are callee saved, their state is preserved across the call. + bpf_mov R6 = 1 + bpf_call foo + bpf_mov R0 = R6 + bpf_exit +is a correct program. If there was R1 instead of R6, it would have +been rejected. + +load/store instructions are allowed only with registers of valid types, which +are PTR_TO_CTX, PTR_TO_MAP, FRAME_PTR. They are bounds and alignment checked. +For example: + bpf_mov R1 = 1 + bpf_mov R2 = 2 + bpf_xadd *(u32 *)(R1 + 3) += R2 + bpf_exit +will be rejected, since R1 doesn't have a valid pointer type at the time of +execution of instruction bpf_xadd. + +At the start R1 type is PTR_TO_CTX (a pointer to generic 'struct bpf_context') +A callback is used to customize verifier to restrict eBPF program access to only +certain fields within ctx structure with specified size and alignment. + +For example, the following insn: + bpf_ld R0 = *(u32 *)(R6 + 8) +intends to load a word from address R6 + 8 and store it into R0 +If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know +that offset 8 of size 4 bytes can be accessed for reading, otherwise +the verifier will reject the program. +If R6=FRAME_PTR, then access should be aligned and be within +stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8, +so it will fail verification, since it's out of bounds. + +The verifier will allow eBPF program to read data from stack only after +it wrote into it. +Classic BPF verifier does similar check with M[0-15] memory slots. +For example: + bpf_ld R0 = *(u32 *)(R10 - 4) + bpf_exit +is invalid program. +Though R10 is correct read-only register and has type FRAME_PTR +and R10 - 4 is within stack bounds, there were no stores into that location. + +Pointer register spill/fill is tracked as well, since four (R6-R9) +callee saved registers may not be enough for some programs. + +Allowed function calls are customized with bpf_verifier_ops->get_func_proto() +The eBPF verifier will check that registers match argument constraints. +After the call register R0 will be set to return type of the function. + +Function calls is a main mechanism to extend functionality of eBPF programs. +Socket filters may let programs to call one set of functions, whereas tracing +filters may allow completely different set. + +If a function made accessible to eBPF program, it needs to be thought through +from safety point of view. The verifier will guarantee that the function is +called with valid arguments. + +seccomp vs socket filters have different security restrictions for classic BPF. +Seccomp solves this by two stage verifier: classic BPF verifier is followed +by seccomp verifier. In case of eBPF one configurable verifier is shared for +all use cases. + +See details of eBPF verifier in kernel/bpf/verifier.c + eBPF maps --------- 'maps' is a generic storage of different types for sharing data between kernel
@@ -1040,6 +1133,137 @@ The map is defined by: . key size in bytes . value size in bytes +Understanding eBPF verifier messages +------------------------------------ + +The following are few examples of invalid eBPF programs and verifier error +messages as seen in the log: + +Program with unreachable instructions: +static struct bpf_insn prog[] = { + BPF_EXIT_INSN(), + BPF_EXIT_INSN(), +}; +Error: + unreachable insn 1 + +Program that reads uninitialized register: + BPF_MOV64_REG(BPF_REG_0, BPF_REG_2), + BPF_EXIT_INSN(), +Error: + 0: (bf) r0 = r2 + R2 !read_ok + +Program that doesn't initialize R0 before exiting: + BPF_MOV64_REG(BPF_REG_2, BPF_REG_1), + BPF_EXIT_INSN(), +Error: + 0: (bf) r2 = r1 + 1: (95) exit + R0 !read_ok + +Program that accesses stack out of bounds: + BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0), + BPF_EXIT_INSN(), +Error: + 0: (7a) *(u64 *)(r10 +8) = 0 + invalid stack off=8 size=8 + +Program that doesn't initialize stack before passing its address into function: + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_LD_MAP_FD(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), + BPF_EXIT_INSN(), +Error: + 0: (bf) r2 = r10 + 1: (07) r2 += -8 + 2: (b7) r1 = 0x0 + 3: (85) call 1 + invalid indirect read from stack off -8+0 size 8 + +Program that uses invalid map_fd=0 while calling to map_lookup_elem() function: + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_LD_MAP_FD(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), + BPF_EXIT_INSN(), +Error: + 0: (7a) *(u64 *)(r10 -8) = 0 + 1: (bf) r2 = r10 + 2: (07) r2 += -8 + 3: (b7) r1 = 0x0 + 4: (85) call 1 + fd 0 is not pointing to valid bpf_map + +Program that doesn't check return value of map_lookup_elem() before accessing +map element: + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_LD_MAP_FD(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), + BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0), + BPF_EXIT_INSN(), +Error: + 0: (7a) *(u64 *)(r10 -8) = 0 + 1: (bf) r2 = r10 + 2: (07) r2 += -8 + 3: (b7) r1 = 0x0 + 4: (85) call 1 + 5: (7a) *(u64 *)(r0 +0) = 0 + R0 invalid mem access 'map_value_or_null' + +Program that correctly checks map_lookup_elem() returned value for NULL, but +accesses the memory with incorrect alignment: + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_LD_MAP_FD(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1), + BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0), + BPF_EXIT_INSN(), +Error: + 0: (7a) *(u64 *)(r10 -8) = 0 + 1: (bf) r2 = r10 + 2: (07) r2 += -8 + 3: (b7) r1 = 1 + 4: (85) call 1 + 5: (15) if r0 == 0x0 goto pc+1 + R0=map_ptr R10=fp + 6: (7a) *(u64 *)(r0 +4) = 0 + misaligned access off 4 size 8 + +Program that correctly checks map_lookup_elem() returned value for NULL and +accesses memory with correct alignment in one side of 'if' branch, but fails +to do so in the other side of 'if' branch: + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_LD_MAP_FD(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), + BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0), + BPF_EXIT_INSN(), + BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), +Error: + 0: (7a) *(u64 *)(r10 -8) = 0 + 1: (bf) r2 = r10 + 2: (07) r2 += -8 + 3: (b7) r1 = 1 + 4: (85) call 1 + 5: (15) if r0 == 0x0 goto pc+2 + R0=map_ptr R10=fp + 6: (7a) *(u64 *)(r0 +0) = 0 + 7: (95) exit + + from 5 to 8: R0=imm0 R10=fp + 8: (7a) *(u64 *)(r0 +0) = 1 + R0 invalid mem access 'imm' + Testing -------
include/linux/bpf.h +2 -0
@@ -81,5 +81,7 @@ struct bpf_prog;void bpf_prog_put (struct bpf_prog *prog);struct bpf_prog *bpf_prog_get (u32 ufd); +/* verify correctness of eBPF program */ +int bpf_check (struct bpf_prog *fp,union bpf_attr *attr);#endif /* _LINUX_BPF_H */
kernel/bpf/Makefile +1 -1
@@ -1 +1 @@ -obj-y := core.o syscall.o +obj-y := core.o syscall.o verifier.o
kernel/bpf/syscall.c +1 -1
@@ -495,7 +495,7 @@ static int bpf_prog_load(union bpf_attr *attr) goto free_prog_info;/* run eBPF verifier */ -/* err = bpf_check(prog, tb); */ + err =bpf_check (prog, attr);if (err <0 ) goto free_prog_info;
kernel/bpf/verifier.c new file +133 -0
133 lines not on this page · raw message
Signature · 1 line
1.7.9.5
PATCH v11 7/12 bpf: verifier (add ability to receive verification log)
In reply to Alexei Starovoitovadd optional attributes for BPF_PROG_LOAD syscall:
struct {
...
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
void __user *log_buf; /* user supplied buffer */
};In such case the verifier will return its verification log in the user supplied buffer which can be used by humans to analyze why verifier rejected given program
--- include/uapi/linux/bpf.h | 5 +- kernel/bpf/verifier.c | 235 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 239 insertions(+), 1 deletion(-)
include/uapi/linux/bpf.h +4 -1
@@ -143,7 +143,10 @@ union bpf_attr {__u32 insn_cnt;const struct bpf_insn __user *insns;const char __user *license; -#define BPF_PROG_LOAD_LAST_FIELD license +__u32 log_level;/* verbosity level of eBPF verifier */ +__u32 log_size;/* size of user buffer */ +void __user *log_buf;/* user supplied buffer */ +#define BPF_PROG_LOAD_LAST_FIELD log_buf }; };
kernel/bpf/verifier.c +235 -0
244 lines not on this page · raw message
Signature · 1 line
1.7.9.5
PATCH v11 8/12 bpf: handle pseudo BPF_LD_IMM64 insn
In reply to Alexei StarovoitoveBPF programs passed from userspace are using pseudo BPF_LD_IMM64 instructions to refer to process-local map_fd. Scan the program for such instructions and if FDs are valid, convert them to 'struct bpf_map' pointers which will be used by verifier to check access to maps in bpf_map_lookup/update() calls. If program passes verifier, convert pseudo BPF_LD_IMM64 into generic by dropping BPF_PSEUDO_MAP_FD flag.
Note that eBPF interpreter is generic and knows nothing about pseudo insns.
--- include/linux/filter.h | 6 ++ kernel/bpf/verifier.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 153 insertions(+)
include/linux/filter.h +6 -0
@@ -139,6 +139,12 @@ struct bpf_prog_info; .off = 0, \ .imm = ((__u64) (IMM)) >> 32 }) +#define BPF_PSEUDO_MAP_FD 1 + +/* pseudo BPF_LD_IMM64 insn used to refer to process-local map_fd */ +#define BPF_LD_MAP_FD (DST ,MAP_FD ) \ + BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD) +/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */ #define BPF_MOV64_RAW (TYPE ,DST ,SRC ,IMM ) \
kernel/bpf/verifier.c +147 -0
188 lines not on this page · raw message
Signature · 1 line
1.7.9.5
PATCH v11 9/12 bpf: verifier (add branch/goto checks)
In reply to Alexei Starovoitovcheck that control flow graph of eBPF program is a directed acyclic graph
check_cfg() does:
- detect loops
- detect unreachable instructions
- check that program terminates with BPF_EXIT insn
- check that all branches are within program boundary
--- kernel/bpf/verifier.c | 183 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 183 insertions(+)
kernel/bpf/verifier.c +183 -0
@@ -313,6 +313,185 @@ static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)return (struct bpf_map *) (unsigned long ) imm64; } +/* non-recursive DFS pseudo code +* 1 procedure DFS-iterative(G,v): +* 2 label v as discovered +* 3 let S be a stack +* 4 S.push(v) +* 5 while S is not empty +* 6 t <- S.pop() +* 7 if t is what we're looking for: +* 8 return t +* 9 for all edges e in G.adjacentEdges(t) do +* 10 if edge e is already labelled +* 11 continue with the next edge +* 12 w <- G.adjacentVertex(t,e) +* 13 if vertex w is not discovered and not explored +* 14 label e as tree-edge +* 15 label w as discovered +* 16 S.push(w) +* 17 continue at 5 +* 18 else if vertex w is discovered +* 19 label e as back-edge +* 20 else +* 21 // vertex w is explored +* 22 label e as forward- or cross-edge +* 23 label t as explored +* 24 S.pop() +* +* convention: +* 0x10 - discovered +* 0x11 - discovered and fall-through edge labelled +* 0x12 - discovered and fall-through and branch edges labelled +* 0x20 - explored +*/ + +enum { +DISCOVERED =0x10 , +EXPLORED =0x20 , +FALLTHROUGH =1 , +BRANCH =2 , +}; + +#define PUSH_INT (I ) \ + do { \ + if (cur_stack >= insn_cnt) { \ + ret = -E2BIG; \ + goto free_st; \ + } \ + stack[cur_stack++] = I; \ + } while (0) + +#define PEEK_INT () \ + ({ \ + int _ret; \ + if (cur_stack == 0) \ + _ret = -1; \ + else \ + _ret = stack[cur_stack - 1]; \ + _ret; \ + }) + +#define POP_INT () \ + ({ \ + int _ret; \ + if (cur_stack == 0) \ + _ret = -1; \ + else \ + _ret = stack[--cur_stack]; \ + _ret; \ + }) + +#define PUSH_INSN (T ,W ,E ) \ + do { \ + int w = W; \ + if (E == FALLTHROUGH && st[T] >= (DISCOVERED | FALLTHROUGH)) \ + break; \ + if (E == BRANCH && st[T] >= (DISCOVERED | BRANCH)) \ + break; \ + if (w < 0 || w >= insn_cnt) { \ + verbose("jump out of range from insn %d to %d\n", T, w); \ + ret = -EINVAL; \ + goto free_st; \ + } \ + if (st[w] == 0) { \ +/* tree-edge */ \ + st[T ] =DISCOVERED |E ; \ + st[w] =DISCOVERED ; \ +PUSH_INT (w); \ + goto peek_stack; \ + } else if ((st[w] & 0xF0) == DISCOVERED) { \ +verbose ("back-edge from insn %d to %d\n" ,T , w); \ + ret = -EINVAL ; \ + goto free_st; \ + }else if (st[w] ==EXPLORED ) { \ +/* forward- or cross-edge */ \ + st[T ] =DISCOVERED |E ; \ + }else { \ +verbose ("insn state internal bug\n" ); \ + ret = -EFAULT ; \ + goto free_st; \ + } \ + } while (0) + +/* non-recursive depth-first-search to detect loops in BPF program +* loop == back-edge in directed graph +*/ +static int check_cfg(struct verifier_env *env) +{ +struct bpf_insn *insns = env->prog->insnsi; +int insn_cnt = env->prog->len; +int cur_stack =0 ; +int *stack; +int ret =0 ; +int *st; +int i, t; + + st =kzalloc (sizeof (int ) * insn_cnt,GFP_KERNEL ); +if (!st) +return -ENOMEM ; + + stack =kzalloc (sizeof (int ) * insn_cnt,GFP_KERNEL ); +if (!stack) { +kfree (st); +return -ENOMEM ; + } + + st[0 ] =DISCOVERED ;/* mark 1st insn as discovered */ +PUSH_INT (0 ); + +peek_stack: +while ((t =PEEK_INT ()) !=-1 ) { +if (BPF_CLASS (insns[t].code) ==BPF_JMP ) { +u8 opcode =BPF_OP (insns[t].code); + +if (opcode ==BPF_EXIT ) { + goto mark_explored; + }else if (opcode ==BPF_CALL ) { +PUSH_INSN (t, t +1 ,FALLTHROUGH ); + }else if (opcode ==BPF_JA ) { +if (BPF_SRC (insns[t].code) !=BPF_K ) { + ret = -EINVAL ; + goto free_st; + } +/* unconditional jump with single edge */ +PUSH_INSN (t, t + insns[t].off +1 ,FALLTHROUGH ); + }else { +/* conditional jump with two edges */ +PUSH_INSN (t, t +1 ,FALLTHROUGH ); +PUSH_INSN (t, t + insns[t].off +1 ,BRANCH ); + } + }else { +/* all other non-branch instructions with single +* fall-through edge +*/ +PUSH_INSN (t, t +1 ,FALLTHROUGH ); + } + +mark_explored: + st[t] =EXPLORED ; +if (POP_INT () ==-1 ) { +verbose ("pop_int internal bug\n" ); + ret = -EFAULT ; + goto free_st; + } + } + + +for (i =0 ; i < insn_cnt; i++) { +if (st[i] !=EXPLORED ) { +verbose ("unreachable insn %d\n" , i); + ret = -EINVAL ; + goto free_st; + } + } + +free_st: +kfree (st); +kfree (stack); +return ret; +} +/* look for pseudo eBPF instructions that access map FDs and * replace them with actual map pointers */
@@ -462,6 +641,10 @@ int bpf_check(struct bpf_prog *prog, union bpf_attr *attr)if (ret <0 ) goto skip_full_check; + ret =check_cfg (env); +if (ret <0 ) + goto skip_full_check; +/* ret = do_check(env); */ skip_full_check:
Signature · 1 line
1.7.9.5
PATCH v11 10/12 bpf: verifier (add verifier core)
In reply to Alexei StarovoitovThis patch adds verifier core which simulates execution of every insn and records the state of registers and program stack. Every branch instruction seen during simulation is pushed into state stack. When verifier reaches BPF_EXIT, it pops the state from the stack and continues until it reaches BPF_EXIT again. For program:
1: bpf_mov r1, xxx
2: if (r1 == 0) goto 5
3: bpf_mov r0, 1
4: goto 6
5: bpf_mov r0, 2
6: bpf_exit
The verifier will walk insns: 1, 2, 3, 4, 6
then it will pop the state recorded at insn#2 and will continue: 5, 6
This way it walks all possible paths through the program and checks all possible values of registers. While doing so, it checks for:
- invalid instructions
- uninitialized register access
- uninitialized stack access
- misaligned stack access
- out of range stack access
- invalid calling convention
- instruction encoding is not using reserved fields
Kernel subsystem configures the verifier with two callbacks:
- bool (*is_valid_access)(int off, int size, enum bpf_access_type type); that provides information to the verifer which fields of 'ctx' are accessible (remember 'ctx' is the first argument to eBPF program)
- const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id); returns argument constraints of kernel helper functions that eBPF program may call, so that verifier can checks that R1-R5 types match the prototype
More details in Documentation/networking/filter.txt and in kernel/bpf/verifier.c
--- include/linux/bpf.h | 47 +++ kernel/bpf/verifier.c | 1003 ++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 1049 insertions(+), 1 deletion(-)
include/linux/bpf.h +47 -0
@@ -46,6 +46,31 @@ void bpf_register_map_type(struct bpf_map_type_list *tl);void bpf_map_put (struct bpf_map *map);struct bpf_map *bpf_map_get (struct fd f); +/* function argument constraints */ +enum bpf_arg_type { +ARG_ANYTHING =0 ,/* any argument is ok */ + +/* the following constraints used to prototype +* bpf_map_lookup/update/delete_elem() functions +*/ +ARG_CONST_MAP_PTR ,/* const argument used as pointer to bpf_map */ +ARG_PTR_TO_MAP_KEY ,/* pointer to stack used as map key */ +ARG_PTR_TO_MAP_VALUE ,/* pointer to stack used as map value */ + +/* the following constraints used to prototype bpf_memcmp() and other +* functions that access data on eBPF program stack +*/ +ARG_PTR_TO_STACK ,/* any pointer to eBPF program stack */ +ARG_CONST_STACK_SIZE ,/* number of bytes accessed from stack */ +}; + +/* type of values returned from helper functions */ +enum bpf_return_type { +RET_INTEGER ,/* function returns integer */ +RET_VOID ,/* function doesn't return anything */ +RET_PTR_TO_MAP_VALUE_OR_NULL ,/* returns a pointer to map elem value or NULL */ +}; +/* eBPF function prototype used by verifier to allow BPF_CALLs from eBPF programs * to in-kernel helper functions and for adjusting imm32 field in BPF_CALL * instructions after verifying
@@ -53,11 +78,33 @@ struct bpf_map *bpf_map_get(struct fd f);struct bpf_func_proto {u64 (*func)(u64 r1,u64 r2,u64 r3,u64 r4,u64 r5);bool gpl_only; +enum bpf_return_type ret_type; +enum bpf_arg_type arg1_type; +enum bpf_arg_type arg2_type; +enum bpf_arg_type arg3_type; +enum bpf_arg_type arg4_type; +enum bpf_arg_type arg5_type; +}; + +/* bpf_context is intentionally undefined structure. Pointer to bpf_context is +* the first argument to eBPF programs. +* For socket filters: 'struct bpf_context *' == 'struct sk_buff *' +*/ +struct bpf_context ; + +enum bpf_access_type { +BPF_READ =1 , +BPF_WRITE =2 };struct bpf_verifier_ops {/* return eBPF function prototype for verification */ const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id); + +/* return true if 'size' wide access at offset 'off' within bpf_context +* with 'type' (read or write) is allowed +*/ +bool (*is_valid_access)(int off,int size,enum bpf_access_type type); };struct bpf_prog_type_list {
kernel/bpf/verifier.c +1002 -1
1,047 lines not on this page · raw message
Signature · 1 line
1.7.9.5
PATCH v11 11/12 net: filter: move eBPF instruction macros
In reply to Alexei Starovoitovmove instruction macros (like BPF_MOV64_REG or BPF_ALU32_IMM) from linux/filter.h into uapi/linux/bpf.h
so that userspace programs can use them.
verifier testsuite (in later patches) will be using them.
--- include/linux/filter.h | 226 ---------------------------------------------- include/uapi/linux/bpf.h | 226 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 226 insertions(+), 226 deletions(-)
include/linux/filter.h +0 -226
@@ -37,232 +37,6 @@ struct bpf_prog_info;/* BPF program can access up to 512 bytes of stack space. */ #define MAX_BPF_STACK 512 -/* Helper macros for filter block array initializers. */ - -/* ALU ops on registers, bpf_add|sub|...: dst_reg += src_reg */ - -#define BPF_ALU64_REG (OP ,DST ,SRC ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU64 | BPF_OP(OP) | BPF_X, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = 0 }) - -#define BPF_ALU32_REG (OP ,DST ,SRC ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU | BPF_OP(OP) | BPF_X, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = 0 }) - -/* ALU ops on immediates, bpf_add|sub|...: dst_reg += imm32 */ - -#define BPF_ALU64_IMM (OP ,DST ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU64 | BPF_OP(OP) | BPF_K, \ - .dst_reg = DST, \ - .src_reg = 0, \ - .off = 0, \ - .imm = IMM }) - -#define BPF_ALU32_IMM (OP ,DST ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU | BPF_OP(OP) | BPF_K, \ - .dst_reg = DST, \ - .src_reg = 0, \ - .off = 0, \ - .imm = IMM }) - -/* Endianess conversion, cpu_to_{l,b}e(), {l,b}e_to_cpu() */ - -#define BPF_ENDIAN (TYPE ,DST ,LEN ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU | BPF_END | BPF_SRC(TYPE), \ - .dst_reg = DST, \ - .src_reg = 0, \ - .off = 0, \ - .imm = LEN }) - -/* Short form of mov, dst_reg = src_reg */ - -#define BPF_MOV64_REG (DST ,SRC ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU64 | BPF_MOV | BPF_X, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = 0 }) - -#define BPF_MOV32_REG (DST ,SRC ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU | BPF_MOV | BPF_X, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = 0 }) - -/* Short form of mov, dst_reg = imm32 */ - -#define BPF_MOV64_IMM (DST ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU64 | BPF_MOV | BPF_K, \ - .dst_reg = DST, \ - .src_reg = 0, \ - .off = 0, \ - .imm = IMM }) - -#define BPF_MOV32_IMM (DST ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU | BPF_MOV | BPF_K, \ - .dst_reg = DST, \ - .src_reg = 0, \ - .off = 0, \ - .imm = IMM }) - -/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */ -#define BPF_LD_IMM64 (DST ,IMM ) \ - BPF_LD_IMM64_RAW(DST, 0, IMM) - -#define BPF_LD_IMM64_RAW(DST, SRC, IMM) \ - ((struct bpf_insn) { \ - .code = BPF_LD | BPF_DW | BPF_IMM, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = (__u32) (IMM) }), \ - ((struct bpf_insn) { \ - .code = 0, /* zero is reserved opcode */ \ - .dst_reg = 0, \ - .src_reg = 0, \ - .off = 0, \ - .imm = ((__u64) (IMM)) >> 32 }) - -#define BPF_PSEUDO_MAP_FD 1 - -/* pseudo BPF_LD_IMM64 insn used to refer to process-local map_fd */ -#define BPF_LD_MAP_FD (DST ,MAP_FD ) \ - BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD) - -/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */ - -#define BPF_MOV64_RAW (TYPE ,DST ,SRC ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU64 | BPF_MOV | BPF_SRC(TYPE), \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = IMM }) - -#define BPF_MOV32_RAW (TYPE ,DST ,SRC ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_ALU | BPF_MOV | BPF_SRC(TYPE), \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = IMM }) - -/* Direct packet access, R0 = *(uint *) (skb->data + imm32) */ - -#define BPF_LD_ABS (SIZE ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_LD | BPF_SIZE(SIZE) | BPF_ABS, \ - .dst_reg = 0, \ - .src_reg = 0, \ - .off = 0, \ - .imm = IMM }) - -/* Indirect packet access, R0 = *(uint *) (skb->data + src_reg + imm32) */ - -#define BPF_LD_IND (SIZE ,SRC ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_LD | BPF_SIZE(SIZE) | BPF_IND, \ - .dst_reg = 0, \ - .src_reg = SRC, \ - .off = 0, \ - .imm = IMM }) - -/* Memory load, dst_reg = *(uint *) (src_reg + off16) */ - -#define BPF_LDX_MEM (SIZE ,DST ,SRC ,OFF ) \ - ((struct bpf_insn) { \ - .code = BPF_LDX | BPF_SIZE(SIZE) | BPF_MEM, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = OFF, \ - .imm = 0 }) - -/* Memory store, *(uint *) (dst_reg + off16) = src_reg */ - -#define BPF_STX_MEM (SIZE ,DST ,SRC ,OFF ) \ - ((struct bpf_insn) { \ - .code = BPF_STX | BPF_SIZE(SIZE) | BPF_MEM, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = OFF, \ - .imm = 0 }) - -/* Memory store, *(uint *) (dst_reg + off16) = imm32 */ - -#define BPF_ST_MEM (SIZE ,DST ,OFF ,IMM ) \ - ((struct bpf_insn) { \ - .code = BPF_ST | BPF_SIZE(SIZE) | BPF_MEM, \ - .dst_reg = DST, \ - .src_reg = 0, \ - .off = OFF, \ - .imm = IMM }) - -/* Conditional jumps against registers, if (dst_reg 'op' src_reg) goto pc + off16 */ - -#define BPF_JMP_REG (OP ,DST ,SRC ,OFF ) \ - ((struct bpf_insn) { \ - .code = BPF_JMP | BPF_OP(OP) | BPF_X, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = OFF, \ - .imm = 0 }) - -/* Conditional jumps against immediates, if (dst_reg 'op' imm32) goto pc + off16 */ - -#define BPF_JMP_IMM (OP ,DST ,IMM ,OFF ) \ - ((struct bpf_insn) { \ - .code = BPF_JMP | BPF_OP(OP) | BPF_K, \ - .dst_reg = DST, \ - .src_reg = 0, \ - .off = OFF, \ - .imm = IMM }) - -/* Function call */ - -#define BPF_EMIT_CALL (FUNC ) \ - ((struct bpf_insn) { \ - .code = BPF_JMP | BPF_CALL, \ - .dst_reg = 0, \ - .src_reg = 0, \ - .off = 0, \ - .imm = ((FUNC) - __bpf_call_base) }) - -/* Raw code statement block */ - -#define BPF_RAW_INSN (CODE ,DST ,SRC ,OFF ,IMM ) \ - ((struct bpf_insn) { \ - .code = CODE, \ - .dst_reg = DST, \ - .src_reg = SRC, \ - .off = OFF, \ - .imm = IMM }) - -/* Program exit */ - -#define BPF_EXIT_INSN () \ - ((struct bpf_insn) { \ - .code = BPF_JMP | BPF_EXIT, \ - .dst_reg = 0, \ - .src_reg = 0, \ - .off = 0, \ - .imm = 0 }) -#define bytes_to_bpf_size (bytes) \ ({ \ int bpf_size = -EINVAL; \
include/uapi/linux/bpf.h +226 -0
232 lines not on this page · raw message
Signature · 1 line
1.7.9.5
Re: [PATCH v11 net-next 11/12] net: filter: move eBPF instruction macros
Quoted 7 lines · Alexei Starovoitov
move instruction macros (like
BPF_MOV64_REGorBPF_ALU32_IMM) fromlinux/filter.hintouapi/linux/bpf.h
so that userspace programs can use them.verifier testsuite (in later patches) will be using them.
I don't think we need this commit at all. These macros are not really part of the ABI and we should expose __as less as possible__, otherwise we won't be able to alter them anymore. Plus, based on your previous argumentation regarding the header file expose, we also won't be able to add any new macros anymore since you could run into name collisions.
Anyway, I don't see a reason why a e.g. central user space eBPF library cannot live with, for example, a private copy of these helper macros or whatever it wants to define by itself.
I know in classic BPF there's BPF_STMT() and BPF_JUMP() but it's much less complicated than eBPF and less likely to changes.
Re: [PATCH v11 net-next 11/12] net: filter: move eBPF instruction macros
Quoted 17 lines · Daniel Borkmann
Quoted 8 lines · Alexei Starovoitov
move instruction macros (like
BPF_MOV64_REGorBPF_ALU32_IMM) fromlinux/filter.hintouapi/linux/bpf.h
so that userspace programs can use them.verifier testsuite (in later patches) will be using them.
I don't think we need this commit at all. These macros are not really part of the ABI and we should expose
__asless aspossible__, otherwise we won't be able to alter them anymore. Plus, based on your previous argumentation regarding the header file expose, we also won't be able to add any new macros anymore since you could run into name collisions.
Quoted 6 lines
Anyway, I don't see a reason why a e.g. central user space eBPF library cannot live with, for example, a private copy of these helper macros or whatever it wants to define by itself.
I know in classic BPF there's
BPF_STMT()andBPF_JUMP()but it's much less complicated than eBPF and less likely to changes.
Interesting idea. Are you saying just copy paste these 226 lines into user libbpf.h for now to use them in testsuite and examples ? Hmm.
Indeed the less lines we add to uapi the better. I'll do that.
Re: [PATCH v11 net-next 11/12] net: filter: move eBPF instruction macros
Quoted 21 lines · Alexei Starovoitov
Quoted 20 lines · Daniel Borkmann
Quoted 8 lines · Alexei Starovoitov
move instruction macros (like
BPF_MOV64_REGorBPF_ALU32_IMM) fromlinux/filter.hintouapi/linux/bpf.h
so that userspace programs can use them.verifier testsuite (in later patches) will be using them.
Signed-off-by Alexei Starovoitov <[email protected]>I don't think we need this commit at all. These macros are not really part of the ABI and we should expose
__asless aspossible__, otherwise we won't be able to alter them anymore. Plus, based on your previous argumentation regarding the header file expose, we also won't be able to add any new macros anymore since you could run into name collisions.Anyway, I don't see a reason why a e.g. central user space eBPF library cannot live with, for example, a private copy of these helper macros or whatever it wants to define by itself.
Quoted 7 lines
Quoted 2 lines
I know in classic BPF there's
BPF_STMT()andBPF_JUMP()but it's much less complicated than eBPF and less likely to changes.Interesting idea. Are you saying just copy paste these 226 lines into user
libbpf.hfor now to use them in testsuite and examples ? Hmm.
Indeed the less lines we add to uapi the better. I'll do that.
Yes, that should be just fine, the existing ABI is not allowed to change anyway and we're running into less pain if we decide to change existing or add new macros internally.
Re: [PATCH v11 net-next 11/12] net: filter: move eBPF instruction macros
Quoted 10 lines · Daniel Borkmann
Quoted 5 lines
Interesting idea. Are you saying just copy paste these 226 lines into user
libbpf.hfor now to use them in testsuite and examples ? Hmm.
Indeed the less lines we add to uapi the better. I'll do that.Yes, that should be just fine, the existing ABI is not allowed to change anyway and we're running into less pain if we decide to change existing or add new macros internally.
ok. will do that in the next set.
btw, preliminary compat support in the attached patch. It works fine, but Andy's concern about enum is starting to get on me. May be we should replace
enum bpf_.._type with u32 just to be safe...
From 9c05cc1bd18e278f0cfd5a490644105aa7cbbf52 Mon Sep 17 00:00:00 2001
From: Alexei Starovoitov <[email protected]>
Date: Wed, 10 Sep 2014 19:41:31 -0700
Subject: [PATCH] bpf: add compat_sys_bpf wrapper
to support 32-bit user space with 64-bit kernel
--- arch/x86/syscalls/syscall_32.tbl | 2 +- include/uapi/asm-generic/unistd.h | 2 +- kernel/bpf/syscall.c | 95 +++++++++++++++++++++++++++++++++++++ 3 files changed, 97 insertions(+), 2 deletions(-)
arch/x86/syscalls/syscall_32.tbl +1 -1
@@ -363,4 +363,4 @@ 354 i386 seccomp sys_seccomp 355 i386 getrandom sys_getrandom 356 i386 memfd_create sys_memfd_create -357 i386 bpf sys_bpf +357 i386 bpf sys_bpf compat_sys_bpf
include/uapi/asm-generic/unistd.h +1 -1
@@ -706,7 +706,7 @@ __SYSCALL(__NR_getrandom, sys_getrandom)#define __NR_memfd_create 279 __SYSCALL(__NR_memfd_create, sys_memfd_create)#define __NR_bpf 280 -__SYSCALL(__NR_bpf, sys_bpf) +__SC_COMP(__NR_bpf, sys_bpf, compat_sys_bpf)#undef __NR_syscalls#define __NR_syscalls 281
kernel/bpf/syscall.c +95 -0
107 lines not on this page · raw message
Signature · 1 line
1.7.9.5
PATCH v11 12/12 bpf: mini eBPF library, test stubs and verifier testsuite
In reply to Alexei Starovoitov1.
the library includes a trivial set of BPF syscall wrappers:
int bpf_create_map(int key_size, int value_size, int max_entries); int bpf_update_elem(int fd, void *key, void *value); int bpf_lookup_elem(int fd, void *key, void *value); int bpf_delete_elem(int fd, void *key);
int bpf_get_next_key(int fd, void *key, void *next_key); int bpf_prog_load(enum bpf_prog_type prog_type,
const struct sock_filter_int *insns, int insn_len, const char *license);
bpf_prog_load() stores verifier log into global bpf_log_buf[] array
2.
test stubs configure eBPF infra with 'unspec' map and program types. These are fake types used by user space testsuite only.
3.
verifier tests valid and invalid programs and expects predefined error log messages from kernel.
40 tests so far.
$ sudo ./test_verifier #0 add+sub+mul OK #1 unreachable OK #2 unreachable2 OK #3 out of range jump OK #4 out of range jump2 OK #5 test1 ld_imm64 OK ...
--- kernel/bpf/Makefile | 4 + kernel/bpf/test_stub.c | 109 +++++++++ lib/Kconfig.debug | 3 +- samples/bpf/Makefile | 12 + samples/bpf/libbpf.c | 89 +++++++ samples/bpf/libbpf.h | 21 ++ samples/bpf/test_verifier.c | 548 +++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 785 insertions(+), 1 deletion(-) create mode 100644 kernel/bpf/test_stub.c create mode 100644 samples/bpf/Makefile create mode 100644 samples/bpf/libbpf.c create mode 100644 samples/bpf/libbpf.h create mode 100644 samples/bpf/test_verifier.c
kernel/bpf/Makefile +4 -0
@@ -1 +1,5 @@ obj-y := core.o syscall.o verifier.o + +ifdef CONFIG_TEST_BPF +obj-y += test_stub.o +endif
kernel/bpf/test_stub.c new file +109 -0
109 lines not on this page · raw message
lib/Kconfig.debug +2 -1
@@ -1672,7 +1672,8 @@ config TEST_BPF against the BPF interpreter or BPF JIT compiler depending on the current setting. This is in particular useful for BPF JIT compiler development, but also to run regression tests against changes in - the interpreter code. + the interpreter code. It also enables test stubs for eBPF maps and + verifier used by user space verifier testsuite. If unsure, say N.
samples/bpf/Makefile new file +12 -0
@@ -0,0 +1,12 @@ +# kbuild trick to avoid linker error. Can be omitted if a module is built. +obj- := dummy.o + +# List of programs to build +hostprogs-y := test_verifier + +test_verifier-objs := test_verifier.o libbpf.o + +# Tell kbuild to always build the programs +always := $(hostprogs-y) + +HOSTCFLAGS += -I$(objtree)/usr/include
samples/bpf/libbpf.c new file +89 -0
89 lines not on this page · raw message
samples/bpf/libbpf.h new file +21 -0
@@ -0,0 +1,21 @@ +/* eBPF mini library */ +#ifndef __LIBBPF_H +#define __LIBBPF_H + +struct bpf_insn ; + +int bpf_create_map (enum bpf_map_type map_type,int key_size,int value_size, +int max_entries); +int bpf_update_elem (int fd,void *key,void *value); +int bpf_lookup_elem (int fd,void *key,void *value); +int bpf_delete_elem (int fd,void *key); +int bpf_get_next_key (int fd,void *key,void *next_key); + +int bpf_prog_load (enum bpf_prog_type prog_type, +const struct bpf_insn *insns,int insn_len, +const char *license); + +#define LOG_BUF_SIZE 8192 +extern char bpf_log_buf[LOG_BUF_SIZE ]; + +#endif
samples/bpf/test_verifier.c new file +548 -0
548 lines not on this page · raw message
Signature · 1 line
1.7.9.5
Re: [PATCH v11 net-next 12/12] bpf: mini eBPF library, test stubs and verifier testsuite
Quoted 30 lines · Alexei Starovoitov
1.
the library includes a trivial set of BPF syscall wrappers:
intbpf_create_map(int key_size, int value_size, int max_entries); intbpf_update_elem(int fd, void *key, void *value); intbpf_lookup_elem(int fd, void *key, void *value); intbpf_delete_elem(int fd, void *key);
intbpf_get_next_key(int fd, void *key, void *next_key); int bpf_prog_load(enumbpf_prog_typeprog_type,const struct sock_filter_int *insns, int insn_len, const char *license);
bpf_prog_load()stores verifier log into global bpf_log_buf[] array2.
test stubs configure eBPF infra with 'unspec' map and program types. These are fake types used by user space testsuite only.3.
verifier tests valid and invalid programs and expects predefined error log messages from kernel.
40 tests so far.$ sudo ./test_verifier #0 add+sub+mul OK #1 unreachable OK #2 unreachable2 OK #3 out of range jump OK #4 out of range jump2 OK #5 test1 ld_imm64 OK ...
Quoted 1 line
Since we already have an extensive BPF test suite, that is, lib/test_bpf.c, which currently also does sanity checks for the classic BPF verifier, is there a reason these verifier test cases cannot be extended/integrated there as well but have to go to kernel/bpf/test_stub.c resp. samples/bpf/test_verifier.c ? I don't like that we put testing code into kernel/bpf/ whereas we already have a BPF test infrastructure in the kernel elsewhere.
Re: [PATCH v11 net-next 12/12] bpf: mini eBPF library, test stubs and verifier testsuite
Quoted 8 lines · Daniel Borkmann
Since we already have an extensive BPF test suite, that is,
lib/test_bpf.c, which currently also does sanity checks for the classic BPF verifier, is there a reason these verifier test cases cannot be extended/integrated there as well but have to go tokernel/bpf/test_stub.cresp.samples/bpf/test_verifier.c?
I don't like that we put testing code intokernel/bpf/whereas we already have a BPF test infrastructure in the kernel elsewhere.
yes. there is a reason. Verifier needs to be tested from user space, since it works on fds. Process local map_fd are part of the eBPF programs. Therefore one is testing things from kernel and another from userspace. We definitely need both. Currently there is no use case to call verifier from inside the kernel. I'm not sure there will be one. Verifier's main purpose is to check user supplied programs and provide humans an understandable error messages of what
is 'unsafe' in particular program.
Eventually we will integrate this verifier messages with program compilation. Like, the user would write a program in C then invoke a wrapper of compiler and verifier, which will point to lines in C code which are doing something wrong like loops or out of bounds access. Currently verifier complains about particular 'unsafe' instruction, but humans have hard time correlating asm to C.
Re: [PATCH v11 net-next 12/12] bpf: mini eBPF library, test stubs and verifier testsuite
Quoted 10 lines · Alexei Starovoitov
Quoted 8 lines · Daniel Borkmann
Since we already have an extensive BPF test suite, that is,
lib/test_bpf.c, which currently also does sanity checks for the classic BPF verifier, is there a reason these verifier test cases cannot be extended/integrated there as well but have to go tokernel/bpf/test_stub.cresp.samples/bpf/test_verifier.c?
I don't like that we put testing code intokernel/bpf/whereas we already have a BPF test infrastructure in the kernel elsewhere.
Quoted 16 lines
yes. there is a reason. Verifier needs to be tested from user space, since it works on fds. Process local
map_fdare part of the eBPF programs. Therefore one is testing things from kernel and another from userspace. We definitely need both. Currently there is no use case to call verifier from inside the kernel. I'm not sure there will be one. Verifier's main purpose is to check user supplied programs and provide humans an understandable error messages of what
is 'unsafe' in particular program.
Eventually we will integrate this verifier messages with program compilation. Like, the user would write a program in C then invoke a wrapper of compiler and verifier, which will point to lines in C code which are doing something wrong like loops or out of bounds access. Currently verifier complains about particular 'unsafe' instruction, but humans have hard time correlating asm to C.
That actually still doesn't answer my question why the test stub cannot live in lib/test_bpf where we have our actual testing framework for eBPF/BPF, also since you exactly only build test_stub.c when TEST_BPF is enabled which is the Kconfig for lib/test_bpf.
Re: [PATCH v11 net-next 12/12] bpf: mini eBPF library, test stubs and verifier testsuite
Quoted 6 lines · Daniel Borkmann
That actually still doesn't answer my question why the test stub cannot live in
lib/test_bpfwhere we have our actual testing framework for eBPF/BPF, also since you exactly only buildtest_stub.cwhenTEST_BPFis enabled which is theKconfigforlib/test_bpf.
multiple reasons:
1.lib/test_bpf.c is a module, whereas test_stub.c is kernel builtin.
2.
I wasn't sure that reusing CONFIG_TEST_BPF for this purpose was a good idea. May be it's better to introduce CONFIG_BPF_VERIFIER_TEST_STUBS or something.
3.kernel/bpf/test_stubs.c can be removed once real tracing or socket use case is in.
Re: [PATCH v11 net-next 12/12] bpf: mini eBPF library, test stubs and verifier testsuite
Quoted 11 lines · Alexei Starovoitov
Quoted 5 lines · Daniel Borkmann
That actually still doesn't answer my question why the test stub cannot live in
lib/test_bpfwhere we have our actual testing framework for eBPF/BPF, also since you exactly only buildtest_stub.cwhenTEST_BPFis enabled which is theKconfigforlib/test_bpf.multiple reasons:
1.lib/test_bpf.cis a module, whereastest_stub.cis kernel builtin.
Quoted 8 lines
2.
I wasn't sure that reusingCONFIG_TEST_BPFfor this purpose was a good idea. May be it's better to introduceCONFIG_BPF_VERIFIER_TEST_STUBSor something.3.
kernel/bpf/test_stubs.ccan be removed once real tracing or socket use case is in.
Yes, please, lets go for point 3 at the very least.
Re: [PATCH v11 net-next 12/12] bpf: mini eBPF library, test stubs and verifier testsuite
Quoted 7 lines · Daniel Borkmann
Quoted 4 lines
3.
kernel/bpf/test_stubs.ccan be removed once real tracing or socket use case is in.Yes, please, lets go for point 3 at the very least.
agree. test_stubs is a way to have verifier testsuite as the first ebpf user in this patch set.
There are multiple ways of connecting ebpf to tracing/sockets and these discussions cannot happen all at once.
So test_stubs to some degree is scaffolding to bring other pieces in place slowly with required due diligence. I don't think there will be a need for test_stubs when tracing+ebpf is in place. That's why I didn't introduce special prog_type and map_type for it and instead used 'unspec' type which is invalid type and used for testing temporarily.
verifier testsuite, of course, will stay. It will switch from 'unspec' type to real types when they're ready.
On 09/10/2014 07:09 AM, Alexei Starovoitov wrote:
...
Quoted 3 lines
As requested by Andy and others, here is the man page:
BPF(2) Linux Programmer's Manual BPF(2)
...
Quoted 6 lines
In the future maps can have different types: hash, array, bloom filter, radix-tree, but currently only hash type is supported:
enumbpf_map_type{
BPF_MAP_TYPE_UNSPEC,
BPF_MAP_TYPE_HASH,
};
If we mention them here in the man page, users are going to request them, naturally. ;) So I'd just mention what we have, not what we do not yet have. But I'm wondering how much library boiler plate only for BPF we want to add in future, hopefully not most of what's in Corman ... ? ;)
Quoted 10 lines · Daniel Borkmann
Quoted 8 lines
In the future maps can have different types: hash, array, bloom
filter,radix-tree, but currently only hash type is supported: enum bpf_map_type { BPF_MAP_TYPE_UNSPEC, BPF_MAP_TYPE_HASH, };
Quoted 5 lines
If we mention them here in the man page, users are going to request them, naturally. ;) So I'd just mention what we have, not what we do not yet have. But I'm wondering how much library boiler plate only for BPF we want to add in future, hopefully not most of what's in Corman ... ? ;)
:)
as cover letter says hash type was moved from this set to later series, so it's implemented.
array and radix-tree are implemented as well, but not ready for review yet. I have strong use cases for them.
Even two of the simplest examples for tracing (ex2 and ex3) will benefit from 'array' type.
For bloomfiler type Chema had a strong use case as well. I was assuming he will implement it sooner or later ;) But, surely, I can drop future features from the manpage.
On 09/10/2014 07:09 AM, Alexei Starovoitov wrote:
...
Quoted 9 lines
struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */
int map_fd;
void *key;
union {
void *value;
void *next_key;
};
};Quoted 8 lines
struct { /* anonymous struct used by BPF_PROG_LOAD command */
enum bpf_prog_type prog_type;
__u32 insn_cnt;
const struct bpf_insn *insns;
const char *license;
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
void *log_buf; /* user supplied buffer */What is log buffer? Would that mean the verifier will return an error string if the program will not pass it, or if not, what other data? I think the man page is missing how to examine the returned verifier log buffer data.
Quoted 12 lines · Daniel Borkmann
Quoted 10 lines
struct { /* anonymous struct used by BPF_PROG_LOAD command */ enum bpf_prog_type prog_type; __u32 insn_cnt; const struct bpf_insn *insns; const char *license; __u32 log_level; /* verbosity level of eBPF verifier */ __u32 log_size; /* size of user buffer */ void *log_buf; /* user supplied buffer*/
Quoted 4 lines
What is log buffer? Would that mean the verifier will return an error string if the program will not pass it, or if not, what other data? I think the man page is missing how to examine the returned verifier log buffer data.
yes. it's an error log (as text string for humans) from verifier. It is briefly explained in the man page:
EACCES For BPF_PROG_LOAD, though program has valid instructions, it was
rejected, since it was deemed unsafe (may access disallowed mem- ory region or uninitialized stack/register or function con- straints don't match actual types or misaligned access). In such case it is recommended to call bpf() again with log_level = 1 and examine log_buf for specific reason provided by verifier.
and there is a whole section about it in Documentation/networking/filter.txt
called "Understanding eBPF verifier messages".
Quoted 13 lines · Alexei Starovoitov
Quoted 12 lines · Daniel Borkmann
Quoted 10 lines
struct { /* anonymous struct used by BPF_PROG_LOAD command */ enum bpf_prog_type prog_type; __u32 insn_cnt; const struct bpf_insn *insns; const char *license; __u32 log_level; /* verbosity level of eBPF verifier */ __u32 log_size; /* size of user buffer */ void *log_buf; /* user supplied buffer*/
Quoted 6 lines
Quoted 4 lines
What is log buffer? Would that mean the verifier will return an error string if the program will not pass it, or if not, what other data? I think the man page is missing how to examine the returned verifier log buffer data.
yes. it's an error log (as text string for humans) from verifier.
I was confused due to the void pointer. But that also means that the text string becomes part of the ABI; aren't eBPF specific error codes (perhaps a tuple of [line + error code]), though ugly as well, but perhaps the better solution to this [which user space can then map to an actual string]?
Quoted 27 lines · Daniel Borkmann
Quoted 26 lines · Alexei Starovoitov
Quoted 21 lines · Daniel Borkmann
Quoted 8 lines
struct { /* anonymous struct used by
BPF_PROG_LOADcommand
*/enum bpf_prog_type prog_type; __u32 insn_cnt; const struct bpf_insn *insns; const char *license; __u32 log_level; /* verbosity level ofQuoted 6 lines
eBPF verifier */
__u32log_size; /* size of user buffer
*/
void*log_buf; /* user supplied
buffer
*/What is log buffer? Would that mean the verifier will return an error string if the program will not pass it, or if not, what other data? I think the man page is missing how to examine the returned verifier log buffer data.
Quoted 3 lines
Quoted 1 line
yes. it's an error log (as text string for humans) from verifier.
I was confused due to the void pointer. But that also means that the text
ahh. ok. will change it to 'char *' then.
Quoted 3 lines
string becomes part of the ABI; aren't eBPF specific error codes (perhaps a tuple of [line + error code]), though ugly as well, but perhaps the better solution to this [which user space can then map to an actual string]?
the verifier log contains full trace. Last unsafe instruction + error in many cases is useless. What we found empirically from using it over last 2 years is that developers have different learning curve to adjust to 'safe' style of C. Pretty much everyone couldn't figure out why program is rejected based on last error. Therefore verifier emits full log. From the 1st insn all the way till the last 'unsafe' instruction. So the log is multiline output. 'Understanding eBPF verifier messages' section of Documentation/networking/filter.txt provides few trivial examples of these multiline messages.
Like for the program:
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), BPF_LD_MAP_FD(BPF_REG_1, 0), BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1), BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),
the verifier log_buf is:
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+1
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8
It will surely change over time as verifier becomes smarter, supports new types, optimizations and so on.
So this log is not an ABI. It's for humans to read. The log explains _how_ verifier came to conclusion that the program is unsafe.
Quoted 68 lines · Alexei Starovoitov
Quoted 27 lines · Daniel Borkmann
Quoted 26 lines · Alexei Starovoitov
Quoted 21 lines · Daniel Borkmann
Quoted 8 lines
struct { /* anonymous struct used by
BPF_PROG_LOADcommand
*/enum bpf_prog_type prog_type; __u32 insn_cnt; const struct bpf_insn *insns; const char *license; __u32 log_level; /* verbosity level ofQuoted 6 lines
eBPF verifier */
__u32log_size; /* size of user buffer
*/
void*log_buf; /* user supplied
buffer
*/What is log buffer? Would that mean the verifier will return an error string if the program will not pass it, or if not, what other data? I think the man page is missing how to examine the returned verifier log buffer data.
Quoted 3 lines
Quoted 1 line
yes. it's an error log (as text string for humans) from verifier.
I was confused due to the void pointer. But that also means that the text
ahh. ok. will change it to 'char *' then.
Quoted 3 lines
string becomes part of the ABI; aren't eBPF specific error codes (perhaps a tuple of [line + error code]), though ugly as well, but perhaps the better solution to this [which user space can then map to an actual string]?
the verifier log contains full trace. Last unsafe instruction + error in many cases is useless. What we found empirically from using it over last 2 years is that developers have different learning curve to adjust to 'safe' style of C. Pretty much everyone couldn't figure out why program is rejected based on last error. Therefore verifier emits full log. From the 1st insn all the way till the last 'unsafe' instruction. So the log is multiline output. 'Understanding eBPF verifier messages' section of
Documentation/networking/filter.txtprovides few trivial examples of these multiline messages.
Like for the program:
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),BPF_LD_MAP_FD(BPF_REG_1, 0),BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem),BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),
the verifierlog_bufis:
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0
4: (85) call 1
5: (15) if r0 ==0x0goto pc+1
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8
Quoted 5 lines
It will surely change over time as verifier becomes smarter, supports new types, optimizations and so on.
So this log is not an ABI. It's for humans to read. The log explains _how_ verifier came to conclusion that the program is unsafe.
Given that you've already arranged (I think) for the verifier to be compilable in the kernel and in userspace, would it make more sense to have the kernel version just say yes or no and to make it easy for user code to retry verification in userspace if they want a full explanation?
--Andy
Quoted 37 lines · Andy Lutomirski
Quoted 31 lines
the verifier log contains full trace. Last unsafe instruction + error in many cases is useless. What we found empirically from using it over last 2 years is that developers have different learning curve to adjust to 'safe' style of C. Pretty much everyone couldn't figure out why program is rejected based on last error. Therefore verifier emits full log. From the 1st insn all the way till the last 'unsafe' instruction. So the log is multiline output. 'Understanding eBPF verifier messages' section of
Documentation/networking/filter.txtprovides few trivial examples of these multiline messages.
Like for the program:
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),BPF_LD_MAP_FD(BPF_REG_1, 0),BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem),BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),
the verifierlog_bufis:
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0
4: (85) call 1
5: (15) if r0 ==0x0goto pc+1
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8Quoted 5 lines
It will surely change over time as verifier becomes smarter, supports new types, optimizations and so on.
So this log is not an ABI. It's for humans to read. The log explains _how_ verifier came to conclusion that the program is unsafe.
Quoted 5 lines
Given that you've already arranged (I think) for the verifier to be compilable in the kernel and in userspace, would it make more sense to have the kernel version just say yes or no and to make it easy for user code to retry verification in userspace if they want a full explanation?
Good memory :) Long ago I had a hack where I compiled verifier.o for kernel and linked it with userspace wrappers to have the same verifier for userspace. It was very fragile. and maps were not separate objects and there were no fds. It's not feasible anymore, since different subsystems will configure different bpf_context and helper functions and verifier output is dynamic based on maps that were created. For example, if user's samples/bpf/sock_example.c does bpf_create_map(HASH, sizeof(key) * 2, ...);
instead ofbpf_create_map(HASH, sizeof(key), ...);
the same program will be rejected in first case and will be accepted in the second, because map sizes and ebpf program expectations are mismatching.
For the 1st case verifier will complain that program is trying to pass uninitialized stack into bpf_lookup(key,...) method or stack may be out of bounds.
Human insight is needed to understand what is going on.
I think more important is that source of truth needs to be in one place == kernel. If we have two verifiers they will diverge sooner or later and cause confusion for users. I think as long as we document that verifier log messages are not cast in stone and will change, we're fine. I consider them as continuation of compiler warnings/errors. They are meant for humans and do change from time to time.
Quoted 44 lines · Alexei Starovoitov
Quoted 37 lines · Andy Lutomirski
Quoted 31 lines
the verifier log contains full trace. Last unsafe instruction + error in many cases is useless. What we found empirically from using it over last 2 years is that developers have different learning curve to adjust to 'safe' style of C. Pretty much everyone couldn't figure out why program is rejected based on last error. Therefore verifier emits full log. From the 1st insn all the way till the last 'unsafe' instruction. So the log is multiline output. 'Understanding eBPF verifier messages' section of
Documentation/networking/filter.txtprovides few trivial examples of these multiline messages.
Like for the program:
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),BPF_LD_MAP_FD(BPF_REG_1, 0),BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem),BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),
the verifierlog_bufis:
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0
4: (85) call 1
5: (15) if r0 ==0x0goto pc+1
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8Quoted 5 lines
It will surely change over time as verifier becomes smarter, supports new types, optimizations and so on.
So this log is not an ABI. It's for humans to read. The log explains _how_ verifier came to conclusion that the program is unsafe.Quoted 5 lines
Given that you've already arranged (I think) for the verifier to be compilable in the kernel and in userspace, would it make more sense to have the kernel version just say yes or no and to make it easy for user code to retry verification in userspace if they want a full explanation?
Quoted 14 lines
Good memory :) Long ago I had a hack where I compiled verifier.o for kernel and linked it with userspace wrappers to have the same verifier for userspace. It was very fragile. and maps were not separate objects and there were no fds. It's not feasible anymore, since different subsystems will configure different
bpf_contextand helper functions and verifier output is dynamic based on maps that were created. For example, if user'ssamples/bpf/sock_example.cdoesbpf_create_map(HASH, sizeof(key) * 2, ...);
instead ofbpf_create_map(HASH, sizeof(key), ...);
the same program will be rejected in first case and will be accepted in the second, because map sizes and ebpf program expectations are mismatching.
Hmm.
This actually furthers my thought that the relocations should be a real relocation table. Then you could encode the types of the referenced objects in the table, and a program could be verified without looking up the fds. The only extra step would be to confirm that the actual types referenced match those in the table.
--Andy
Quoted 60 lines · Andy Lutomirski
Quoted 44 lines · Alexei Starovoitov
Quoted 37 lines · Andy Lutomirski
Quoted 31 lines
the verifier log contains full trace. Last unsafe instruction + error in many cases is useless. What we found empirically from using it over last 2 years is that developers have different learning curve to adjust to 'safe' style of C. Pretty much everyone couldn't figure out why program is rejected based on last error. Therefore verifier emits full log. From the 1st insn all the way till the last 'unsafe' instruction. So the log is multiline output. 'Understanding eBPF verifier messages' section of
Documentation/networking/filter.txtprovides few trivial examples of these multiline messages.
Like for the program:
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),BPF_LD_MAP_FD(BPF_REG_1, 0),BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem),BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),
the verifierlog_bufis:
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0
4: (85) call 1
5: (15) if r0 ==0x0goto pc+1
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8Quoted 5 lines
It will surely change over time as verifier becomes smarter, supports new types, optimizations and so on.
So this log is not an ABI. It's for humans to read. The log explains _how_ verifier came to conclusion that the program is unsafe.Quoted 5 lines
Given that you've already arranged (I think) for the verifier to be compilable in the kernel and in userspace, would it make more sense to have the kernel version just say yes or no and to make it easy for user code to retry verification in userspace if they want a full explanation?
Quoted 14 lines
Good memory :) Long ago I had a hack where I compiled verifier.o for kernel and linked it with userspace wrappers to have the same verifier for userspace. It was very fragile. and maps were not separate objects and there were no fds. It's not feasible anymore, since different subsystems will configure different
bpf_contextand helper functions and verifier output is dynamic based on maps that were created. For example, if user'ssamples/bpf/sock_example.cdoesbpf_create_map(HASH, sizeof(key) * 2, ...);
instead ofbpf_create_map(HASH, sizeof(key), ...);
the same program will be rejected in first case and will be accepted in the second, because map sizes and ebpf program expectations are mismatching.
Quoted 7 lines
Hmm.
This actually furthers my thought that the relocations should be a real relocation table. Then you could encode the types of the referenced objects in the table, and a program could be verified without looking up the fds. The only extra step would be to confirm that the actual types referenced match those in the table.
It's not the type is being checked, but one particular map instance with user specified key/value sizes. type is not helpful. type is not even used during verification. Only key_size and value_size of elements are meaningful and they're looked up dynamically by fd.
Hi All,
the list of things I fixed so far from V11:
- dropped patch 11 and copied few macros to libbpf.h (suggested by Daniel)
- replaced 'enum bpf_prog_type' with u32 to be safe in compat (.. Andy)
- implemented and tested compat support (.. Daniel)
- changed 'void *log_buf' to 'char *' (.. Daniel)
- combined struct bpf_work_struct and bpf_prog_info (.. Daniel)
- added better return value explanation to manpage (.. Andy)
- added log_buf/log_size explanation to manpage (.. Andy & Daniel)
- added a lot more info about prog_type and map_type and
they relation to verifier (.. Andy)
anything else I missed from the discussion we had?
Here is updated manpage. Please take a look.
BPF(2) Linux Programmer's Manual BPF(2)
NAME
bpf - perform a command on eBPF map or program
SYNOPSIS
#include <linux/bpf.h>
int bpf(int cmd, union bpf_attr *attr, unsigned int size);DESCRIPTION
bpf() syscall is a multiplexor for a range of different operations on eBPF which can be characterized as "universal in-kernel virtual machine". eBPF is similar to original Berkeley Packet Filter (or "classic BPF") used to filter network packets. Both statically analyze the programs before loading them into the kernel to ensure that programs cannot harm the running system.
eBPF extends classic BPF in multiple ways including ability to call in- kernel helper functions and access shared data structures like eBPF maps. The programs can be written in a restricted C that is compiled into eBPF bytecode and executed on the eBPF virtual machine or JITed into native instruction set.
eBPF Design/Architecture
eBPF maps is a generic storage of different types. User process can
create multiple maps (with key/value being opaque bytes of data) and access them via file descriptor. In parallel eBPF programs can access maps from inside the kernel. It's up to user process and eBPF program to decide what they store inside maps.
eBPF programs are similar to kernel modules. They are loaded by the user process and automatically unloaded when process exits. Each eBPF program is a safe run-to-completion set of instructions. eBPF verifier statically determines that the program terminates and is safe to execute. During verification the program takes a hold of maps that it intends to use, so selected maps cannot be removed until the program is unloaded. The program can be attached to different events. These events can be packets, tracepoint events and other types in the future. A new event triggers execution of the program which may store information about the event in the maps. Beyond storing data the programs may call into in-kernel helper functions which may, for example, dump stack, do trace_printk or other forms of live kernel debugging. The same program can be attached to multiple events. Different programs can access the same map:
tracepoint tracepoint tracepoint sk_buff sk_buff
event A event B event C on eth0 on eth1
| | | | |
| | | | |
--> tracing <-- tracing socket socket
prog_1 prog_2 prog_3 prog_4
| | | |
|--- -----| |-------| map_3
map_1 map_2
Syscall Arguments
bpf() syscall operation is determined by cmd which can be one of the following:
BPF_MAP_CREATE
Create a map with given type and attributes and return map FD
BPF_MAP_LOOKUP_ELEM
Lookup element by key in a given map and return its value
BPF_MAP_UPDATE_ELEM
Create or update element (key/value pair) in a given map
BPF_MAP_DELETE_ELEM
Lookup and delete element by key in a given map
BPF_MAP_GET_NEXT_KEY
Lookup element by key in a given map and return key of next element
BPF_PROG_LOAD
Verify and load eBPF program
attr is a pointer to a union of type bpf_attr as defined below.
size is the size of the union.
union bpf_attr {
struct { /* anonymous struct used by BPF_MAP_CREATE command */
__u32 map_type;
__u32 key_size; /* size of key in bytes */
__u32 value_size; /* size of value in bytes */
__u32 max_entries; /* max number of entries in a map */
};
struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */
int map_fd;
void *key;
union {
void *value;
void *next_key;
};
};
struct { /* anonymous struct used by BPF_PROG_LOAD command */
__u32 prog_type;
__u32 insn_cnt;
const struct bpf_insn *insns;
const char *license;
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
char *log_buf; /* user supplied buffer */
};
};
eBPF maps
maps is a generic storage of different types for sharing data between kernel and userspace.
Any map type has the following attributes:
. type
. max number of elements
. key size in bytes
. value size in bytes
The following wrapper functions demonstrate how this syscall can be used to access the maps. The functions use the cmd argument to invoke different operations.
BPF_MAP_CREATE
int bpf_create_map(enum bpf_map_type map_type, int key_size,
int value_size, int max_entries)
{
union bpf_attr attr = {
.map_type = map_type,
.key_size = key_size,
.value_size = value_size,
.max_entries = max_entries
};
return bpf(BPF_MAP_CREATE, &attr, sizeof(attr));
}
bpf() syscall creates a map of map_type type and given
attributes key_size, value_size, max_entries. On success it
returns process-local file descriptor. On error, -1 is returned and errno is set to EINVAL or EPERM or ENOMEM.
The attributes key_size and value_size will be used by verifier
during program loading to check that program is calling
bpf_map_*_elem() helper functions with correctly initialized key and that program doesn't access map element value beyond
specified value_size. For example, when map is created with
key_size = 8 and program does:
bpf_map_lookup_elem(map_fd, fp - 4)
such program will be rejected, since in-kernel helper function bpf_map_lookup_elem(map_fd, void *key) expects to read 8 bytes from 'key' pointer, but 'fp - 4' starting address will cause out of bounds stack access.
Similarly, when map is created with value_size = 1 and program does:
value = bpf_map_lookup_elem(...);
*(u32 *)value = 1;
such program will be rejected, since it accesses value pointer beyond specified 1 byte value_size limit.
Currently only hash table map_type is supported:
enum bpf_map_type {
BPF_MAP_TYPE_UNSPEC,
BPF_MAP_TYPE_HASH,
};
map_type selects one of the available map implementations in kernel. Regardless of type eBPF program accesses maps with the
same bpf_map_lookup_elem()/bpf_map_update_elem() helper
functions.
BPF_MAP_LOOKUP_ELEM
int bpf_lookup_elem(int fd, void *key, void *value) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
.value = value,
};
return bpf(BPF_MAP_LOOKUP_ELEM, &attr, sizeof(attr));
}
bpf() syscall looks up an element with given key in a map fd. If element is found it returns zero and stores element's value into value. If element is not found it returns -1 and sets errno to ENOENT.
BPF_MAP_UPDATE_ELEM
int bpf_update_elem(int fd, void *key, void *value) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
.value = value,
};
return bpf(BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
}
The call creates or updates element with given key/value in a map fd. On success it returns zero. On error, -1 is returned and errno is set to EINVAL or EPERM or ENOMEM or E2BIG. E2BIG indicates that number of elements in the map reached max_entries limit specified at map creation time.
BPF_MAP_DELETE_ELEM
int bpf_delete_elem(int fd, void *key) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
};
return bpf(BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
}
The call deletes an element in a map fd with given key. Returns zero on success. If element is not found it returns -1 and sets errno to ENOENT.
BPF_MAP_GET_NEXT_KEY
int bpf_get_next_key(int fd, void *key, void *next_key) {
union bpf_attr attr = {
.map_fd = fd,
.key = key,
.next_key = next_key,
};
return bpf(BPF_MAP_GET_NEXT_KEY, &attr, sizeof(attr));
}
The call looks up an element by key in a given map fd and returns key of the next element into next_key pointer. If key is not found, it return zero and returns key of the first element into next_key. If key is the last element, it returns -1 and sets errno to ENOENT. Other possible errno values are ENOMEM, EFAULT, EPERM, EINVAL. This method can be used to iterate over all elements of the map.
close(map_fd)
will delete the map map_fd. Exiting process will delete all maps automatically.
eBPF programs
BPF_PROG_LOAD
This cmd is used to load eBPF program into the kernel.
char bpf_log_buf[LOG_BUF_SIZE];
int bpf_prog_load(enum bpf_prog_type prog_type,
const struct bpf_insn *insns, int insn_cnt, const char *license)
{
union bpf_attr attr = {
.prog_type = prog_type,
.insns = insns,
.insn_cnt = insn_cnt,
.license = license,
.log_buf = bpf_log_buf,
.log_size = LOG_BUF_SIZE,
.log_level = 1,
};
return bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
}
prog_type is one of the available program types:
enum bpf_prog_type {
BPF_PROG_TYPE_UNSPEC,
BPF_PROG_TYPE_SOCKET, BPF_PROG_TYPE_TRACING,
};
By picking prog_type program author selects a set of helper functions callable from eBPF program and corresponding format of struct bpf_context (which is the data blob passed into the
program as the first argument). For example, the programs
loaded with prog_type = TYPE_TRACING may call bpf_printk()
helper, whereas TYPE_SOCKET programs may not. The set of
functions available to the programs under given type may increase in the future.
Currently the set of functions for TYPE_TRACING is:
bpf_map_lookup_elem(map_fd, void *key) // lookup key in a map_fd
bpf_map_update_elem(map_fd, void *key, void *value) // update key/value
bpf_map_delete_elem(map_fd, void *key) // delete key in a map_fd
bpf_ktime_get_ns(void) // returns current ktime
bpf_printk(char *fmt, int fmt_size, ...) // prints into trace buffer
bpf_get_current(void) // return current task pointer
bpf_memcmp(void *ptr1, void *ptr2, int size) // non-faulting memcmp
bpf_fetch_ptr(void *ptr) // non-faulting load pointer from any address
bpf_fetch_u8(void *ptr) // non-faulting 1 byte load
bpf_fetch_u16(void *ptr) // other non-faulting loads
bpf_fetch_u32(void *ptr)
bpf_fetch_u64(void *ptr)
and bpf_context is defined as:
struct bpf_context {
/* argN fields match one to one to arguments passed to trace events */ u64 arg1, arg2, arg3, arg4, arg5, arg6;
/* return value from kretprobe event or from syscall_exit event */ u64 ret;
};
The set of helper functions for TYPE_SOCKET is TBD.
More program types may be added in the future. Like
BPF_PROG_TYPE_USER_TRACING for unprivileged programs.
insns array of "struct bpf_insn" instructions
insn_cnt number of instructions in the program
license license string, which must be GPL compatible to call helper functions marked gpl_only
log_buf user supplied buffer that in-kernel verifier is using to store verification log. Log is a multi-line string that should be used by program author to understand how verifier came to conclusion that program is unsafe. The format of the output can change at any time as verifier evolves.
log_size size of user buffer. If size of the buffer is not large enough to store all verifier messages, -1 is returned and errno is set to ENOSPC.
log_level verbosity level of eBPF verifier, where zero means no logs provided
close(prog_fd)
will unload eBPF program
The maps are accesible from programs and generally tie the two
together. Programs process various events (like tracepoint, kprobe,
packets) and store the data into maps. User space fetches data from
maps. Either the same or a different map may be used by user space as
configuration space to alter program behavior on the fly.
Events
Once an eBPF program is loaded, it can be attached to an event. Various kernel subsystems have different ways to do so. For example:
setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd, sizeof(prog_fd)); will attach the program prog_fd to socket sock which was received by prior call to socket().
ioctl(event_fd, PERF_EVENT_IOC_SET_BPF, prog_fd);
will attach the program prog_fd to perf event event_fd which was received by prior call to perf_event_open().
Another way to attach the program to a tracing event is:
event_fd = open("/sys/kernel/debug/tracing/events/skb/kfree_skb/filter"); write(event_fd, "bpf-123"); /* where 123 is eBPF program FD */ /* here program is attached and will be triggered by events */ close(event_fd); /* to detach from event */
EXAMPLES
/* eBPF+sockets example:
* 1. create map with maximum of 2 elements
* 2. set map[6] = 0 and map[17] = 0
* 3. load eBPF program that counts number of TCP and UDP packets received
* via map[skb->ip->proto]++
* 4. attach prog_fd to raw socket via setsockopt()
* 5. print number of received TCP/UDP packets every second
*/
int main(int ac, char **av)
{
int sock, map_fd, prog_fd, key;
long long value = 0, tcp_cnt, udp_cnt;
map_fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value), 2);
if (map_fd < 0) {
printf("failed to create map '%s'\n", strerror(errno));
/* likely not run as root */
return 1;
}
key = 6; /* ip->proto == tcp */
assert(bpf_update_elem(map_fd, &key, &value) == 0);
key = 17; /* ip->proto == udp */
assert(bpf_update_elem(map_fd, &key, &value) == 0);
struct bpf_insn prog[] = {
BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), /* r6 = r1 */
BPF_LD_ABS(BPF_B, 14 + 9), /* r0 = ip->proto */
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4),/* *(u32 *)(fp - 4) = r0 */
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), /* r2 = fp */
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = r2 - 4 */
BPF_LD_MAP_FD(BPF_REG_1, map_fd), /* r1 = map_fd */
BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem), /* r0 = map_lookup(r1, r2) */
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), /* if (r0 == 0) goto pc+2 */
BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */
BPF_XADD(BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* lock *(u64 *)r0 += r1 */
BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */
BPF_EXIT_INSN(), /* return r0 */
};
prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET, prog, sizeof(prog), "GPL");
assert(prog_fd >= 0);
sock = open_raw_sock("lo");
assert(setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd,
sizeof(prog_fd)) == 0);
for (;;) {
key = 6;
assert(bpf_lookup_elem(map_fd, &key, &tcp_cnt) == 0);
key = 17;
assert(bpf_lookup_elem(map_fd, &key, &udp_cnt) == 0);
printf("TCP %lld UDP %lld packets0, tcp_cnt, udp_cnt);
sleep(1);
}
return 0;
}RETURN VALUE
For a successful call, the return value depends on the operation:
BPF_MAP_CREATE
The new file descriptor associated with eBPF map.
BPF_PROG_LOAD
The new file descriptor associated with eBPF program.
All other commands
Zero.
On error, -1 is returned, and errno is set appropriately.
ERRORS
EPERM bpf() syscall was made without sufficient privilege (without the
CAP_SYS_ADMIN capability).
ENOMEM Cannot allocate sufficient memory.
EBADF fd is not an open file descriptor
EFAULT One of the pointers ( key or value or log_buf or insns ) is
outside accessible address space.
EINVAL The value specified in cmd is not recognized by this kernel.
EINVAL For BPF_MAP_CREATE, either map_type or attributes are invalid.
EINVAL For BPF_MAP_*_ELEM commands, some of the fields of "union
bpf_attr" unused by this command are not set to zero.
EINVAL For BPF_PROG_LOAD, attempt to load invalid program (unrecognized
instruction or uses reserved fields or jumps out of range or loop detected or calls unknown function).
EACCES For BPF_PROG_LOAD, though program has valid instructions, it was
rejected, since it was deemed unsafe (may access disallowed
memory region or uninitialized stack/register or function
constraints don't match actual types or misaligned access). In such case it is recommended to call bpf() again with log_level = 1 and examine log_buf for specific reason provided by verifier.
ENOENT For BPF_MAP_LOOKUP_ELEM or BPF_MAP_DELETE_ELEM, indicates that
element with given key was not found.
E2BIG program is too large or a map reached max_entries limit (max
number of elements).
NOTES
These commands may be used only by a privileged process (one having the CAP_SYS_ADMIN capability).
SEE ALSO
eBPF architecture and instruction set is explained in
Documentation/networking/filter.txt
Linux 2014-09-12 BPF(2)
On 09/10/2014 07:09 AM, Alexei Starovoitov wrote:
....
Quoted 1 line
BPF(2) Linux Programmer's Manual BPF(2)
...
Quoted 8 lines
union bpf_attr {
struct { /* anonymous struct used by BPF_MAP_CREATE command */
enum bpf_map_type map_type;
__u32 key_size; /* size of key in bytes */
__u32 value_size; /* size of value in bytes */
__u32 max_entries; /* max number of entries in a map */
};Quoted 7 lines
struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */
int map_fd;
void *key;
union {
void *value;
void *next_key;
};When you pass in these structs with pointers in it to other user space buffers, how do you handle this with mixed 32/64 bit user/kernel space?
As an example, for the current way to load BPF although we export ...
struct sock_fprog {
unsigned short len;
struct sock_filter __user *filter;
};... through uapi, we still need to handle this via compat_sock_fprog to take care of different pointer sizes via compat_uptr_t :
#ifdef CONFIG_COMPAT
struct compat_sock_fprog {
u16 len;
compat_uptr_t filter;
};#endif
Perhaps I'm missing something, but I think, that would currently break in your syscall handler, no?
Quoted 12 lines
};
struct { /* anonymous struct used by BPF_PROG_LOAD command */
enum bpf_prog_type prog_type;
__u32 insn_cnt;
const struct bpf_insn *insns;
const char *license;
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
void *log_buf; /* user supplied buffer */
};
};Quoted 3 lines · Daniel Borkmann
When you pass in these structs with pointers in it to other user space buffers, how do you handle this with mixed 32/64 bit user/kernel space?
...
Quoted 2 lines
Perhaps I'm missing something, but I think, that would currently break in your syscall handler, no?
yes. compat stuff is not part of this diff.
I was thinking to handle it similar to the way signalfd deals with it:
add compat syscall, compat struct and convert it before going into main entry point.
Quoted 111 lines · Alexei Starovoitov
Hi David,
I've managed to reduce this set to 12:
Patches 1-4 establish BPF syscall shell for maps and programs. Patches 5-10 add verifier step by step
Patch 11 exposes existing instruction macros to user space Patch 12 adds test stubs and verifier testsuite from user spaceI don't know how to reduce it further. Drop verifier and have programs loaded without verification? Sounds wrong. If anyone has other ideas, I'll gladly reduce it further.
Note that patches 1,3,4,7 add commands and attributes to the syscall while being backwards compatible from each other, which should demonstrate how other commands can be added in the future.
Daniel,
bpf_common.hpatch (that we discussed earlier) I didn't include here to reduce the number of patches. It can come next.For those who have looked at the last set of 28 patches, the difference is:
- moved attaching to tracing and sockets to future patches
- moved hash table map type implementation to future
- split verifier further and movedLD_ABSchecks and state prunning to future
- instead of running verifier testsuite on real tracing programs addedtest_stub.cwith fake maps, context and helper functions to test verifier only
- rebasedNote, after this set the programs can be loaded for testing only. They cannot be attached to any events. This will come in the next set.
As requested by Andy and others, here is the man page:
BPF(2) Linux Programmer's Manual BPF(2)
NAME
bpf - perform a command on eBPF map or programSYNOPSIS
#include <linux/bpf.h> int bpf(int cmd, union bpf_attr *attr, unsigned int size);DESCRIPTION
bpf()syscall is a multiplexor for a range of different operations on eBPF which can be characterized as "universal in-kernel virtual machine". eBPF is similar to original Berkeley Packet Filter (or "clas- sic BPF") used to filter network packets. Both statically analyze the programs before loading them into the kernel to ensure that programs cannot harm the running system.eBPF extends classic BPF in multiple ways including ability to call in- kernel helper functions and access shared data structures like eBPF maps. The programs can be written in a restricted C that is compiled into eBPF bytecode and executed on the eBPF virtual machine or JITed into native instruction set.
eBPF Design/Architecture
eBPF maps is a generic storage of different types. User process can
create multiple maps (with key/value being opaque bytes of data) and access them via file descriptor. In parallel eBPF programs can access maps from inside the kernel. It's up to user process and eBPF program to decide what they store inside maps.eBPF programs are similar to kernel modules. They are loaded by the user process and automatically unloaded when process exits. Each eBPF program is a safe run-to-completion set of instructions. eBPF verifier statically determines that the program terminates and is safe to exe- cute. During verification the program takes a hold of maps that it intends to use, so selected maps cannot be removed until the program is unloaded. The program can be attached to different events. These events can be packets, tracepoint events and other types in the future. A new event triggers execution of the program which may store information about the event in the maps. Beyond storing data the programs may call into in-kernel helper functions which may, for example, dump stack, do
trace_printkor other forms of live kernel debugging. The same program can be attached to multiple events. Different programs can access the same map:
tracepoint tracepoint tracepointsk_buffsk_buff
event A event B event C on eth0 on eth1
| | | | |
| | | | |
--> tracing <-- tracing socket socket
prog_1prog_2prog_3prog_4
| | | |
|--- -----| |-------|map_3
map_1map_2Syscall Arguments
bpf()syscall operation is determined by cmd which can be one of the following:
BPF_MAP_CREATE
Create a map with given type and attributes and return map FD
BPF_MAP_LOOKUP_ELEM
Lookup element by key in a given map and return its value
BPF_MAP_UPDATE_ELEM
Create or update element (key/value pair) in a given map
BPF_MAP_DELETE_ELEM
Lookup and delete element by key in a given map
BPF_MAP_GET_NEXT_KEY
Lookup element by key in a given map and return key of next ele- ment
Quoted 6 lines
BPF_PROG_LOAD
Verify and load eBPF programattr is a pointer to a union of type
bpf_attras defined below.size is the size of the union.
I find this strange. Why not just make attr be a pointer to the relevant struct for the operation being invoked?
Quoted 4 lines
union bpf_attr {
struct { /* anonymous struct used by BPF_MAP_CREATE command */
enum bpf_map_type map_type;Does this reliably generate the same type on compat systems? C++11 has a fix for enum ABI compatibility, but this is plain C :(
Quoted 10 lines
struct { /* anonymous struct used by BPF_PROG_LOAD command */
enum bpf_prog_type prog_type;
__u32 insn_cnt;
const struct bpf_insn *insns;
const char *license;
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
void *log_buf; /* user supplied buffer */
};
};It might be a bit nicer to have separate in and out arguments.
Quoted 11 lines
BPF_MAP_CREATE
int bpf_create_map(enumbpf_map_typemap_type, intkey_size,
intvalue_size, intmax_entries)
{
unionbpf_attrattr = {
.map_type =map_type,
.key_size =key_size,
.value_size =value_size,
.max_entries =max_entries
};
I feel like this is asking for trouble, or at least bizarre namespace collisions in the anonymous struct members. At least please give the structs names. (Also, the first time I read this, I assumed that those were union members, which would have made the code be nonsense.)
Quoted 12 lines
BPF_MAP_DELETE_ELEM
int bpf_delete_elem(int fd, void *key)
{
union bpf_attr attr = {
.map_fd = fd,
.key = key,
};
return bpf(BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
}
The call deletes an element in a map fd with given key.What does it return? (The same question goes for a bunch of the map ops.)
Quoted 6 lines
eBPF programs
BPF_PROG_LOAD
This cmd is used to load eBPF program into the kernel.char bpf_log_buf[LOG_BUF_SIZE];
What happens if the size isn't LOG_BUF_SIZE?
Quoted 15 lines
int bpf_prog_load(enum
bpf_prog_typeprog_type,
const structbpf_insn*insns, intinsn_cnt, const char *license)
{
unionbpf_attrattr = {
.prog_type =prog_type,
.insns = insns,
.insn_cnt =insn_cnt,
.license = license,
.log_buf =bpf_log_buf,
.log_size =LOG_BUF_SIZE,
.log_level = 1,
};
Quoted 8 lines
return
bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
}
prog_typeone of the available program types:
enumbpf_prog_type{
BPF_PROG_TYPE_UNSPEC,BPF_PROG_TYPE_SOCKET_FILTER,BPF_PROG_TYPE_TRACING_FILTER,
};
Why does the type matter?
Quoted 25 lines
{
static struct bpf_insn prog[] = {
BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
BPF_LD_ABS(BPF_B, 14 + 9 /* R0 = ip->proto */),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_CALL_FUNC(BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */
BPF_XADD(BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */
BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */
BPF_EXIT_INSN(),
};
int sock, map_fd, prog_fd, key;
long long value = 0, tcp_cnt, udp_cnt;
map_fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value), 2);
if (map_fd < 0) {
printf("failed to create map '%s'\n", strerror(errno));
/* likely not run as root */
return 1;
}Quoted 7 lines
key = 6; /* tcp */
assert(bpf_update_elem(map_fd, &key, &value) == 0);
key = 17; /* udp */
assert(bpf_update_elem(map_fd, &key, &value) == 0);
prog[5].imm = map_fd;This (the .imm thing) is sufficiently weird that I think it needs to be mentioned in the main docs, not just in an example. It's especially odd since AFAIK essentially every other object format in the world uses a separate relocation table instead of inline magic opcodes like this.
Quoted 3 lines
All other commands
Zero.
Shouldn't delete return different values depending on whether anything was deleted?
Quoted 3 lines
ENOENT For
BPF_MAP_LOOKUP_ELEMorBPF_MAP_DELETE_ELEM, indicates that
element with given key was not found.
Ah, here it is. Please document this with the ops.
Quoted 6 lines
E2BIG program is too large.
NOTES
These commands may be used only by a privileged process (one having theCAP_SYS_ADMINcapability).
I hope this goes away :)
I can't shake the feeling that the whole syscall map API is wrong and that, instead, there should be a more general concept of objects provided by the eBPF runtime. Those objects could have methods that are callable by the syscall and callable from eBPF code.
--Andy
Quoted 7 lines · Andy Lutomirski
Quoted 4 lines
attr is a pointer to a union of type
bpf_attras defined below.size is the size of the union.
I find this strange. Why not just make attr be a pointer to the relevant struct for the operation being invoked?
you mean change attr to be 'void *' and type cast it to particular struct type based on cmd ? Possible, but I tried to avoid all typecasts as Dave doesn't like them.
Quoted 6 lines
Quoted 3 lines
union bpf_attr { struct { /* anonymous struct used by BPF_MAP_CREATE command */ enum bpf_map_type map_type;Does this reliably generate the same type on compat systems? C++11 has a fix for enum ABI compatibility, but this is plain C :(
enum is int on both 32 and 64-bit. What was the concern? anonymous struct ?
I've checked that with gcc 4.2 - 4.9 and clang. All was fine and it's part of C standard now.
Quoted 11 lines
Quoted 10 lines
struct { /* anonymous struct used by BPF_PROG_LOAD command */ enum bpf_prog_type prog_type; __u32 insn_cnt; const struct bpf_insn *insns; const char *license; __u32 log_level; /* verbosity level of eBPF verifier */ __u32 log_size; /* size of user buffer */ void *log_buf; /* user supplied buffer */ }; };
Quoted 1 line
It might be a bit nicer to have separate in and out arguments.
would do you mean specifically?
const pointer is obviously 'in' argument.
'void *' is 'out'.
Quoted 10 lines
Quoted 9 lines
int bpf_create_map(enum
bpf_map_typemap_type, intkey_size,
intvalue_size, intmax_entries)
{
unionbpf_attrattr = {
.map_type =map_type,
.key_size =key_size,
.value_size =value_size,
.max_entries =max_entries
};
Quoted 4 lines
I feel like this is asking for trouble, or at least bizarre namespace collisions in the anonymous struct members. At least please give the structs names. (Also, the first time I read this, I assumed that those were union members, which would have made the code be nonsense.)
if inner struct types had names they would need to have field names as well, so the syscall wrapper above would become much more verbose and uglier.
Also naming structs may give wrong ideas to some users, since they might think it's ok to init struct only and type cast it to pass into syscall. When inner structs don't have names, the user space is forced to always use 'union bpf_attr' and initialize relevant fields.
Quoted 3 lines
Quoted 1 line
char bpf_log_buf[LOG_BUF_SIZE];What happens if the size isn't
LOG_BUF_SIZE?
would do you mean?LOG_BUF_SIZE is just a user defined macro.
Can be anything.
it's passed along with pointer:
.log_buf = bpf_log_buf,
.log_size = LOG_BUF_SIZE,
.log_level = 1,Quoted 7 lines
Quoted 5 lines
enum bpf_prog_type { BPF_PROG_TYPE_UNSPEC, BPF_PROG_TYPE_SOCKET_FILTER, BPF_PROG_TYPE_TRACING_FILTER, };Why does the type matter?
type is way to tell eBPF infra what this type of programs is allowed to do. Different kernel subsystems configure different types.
Like patch 12 configures TYPE_UNSPEC for testing. This type allows one dummy function call and bpf_context of two u64 fields.
tracing subsystem will configure TYPE_TRACING
to do different set of helper functions and different body of 'bpf_context'.PROG_TYPE and MAP_TYPE are two main ways
to configure eBPF infra for different use cases.
Quoted 5 lines
This (the .imm thing) is sufficiently weird that I think it needs to be mentioned in the main docs, not just in an example. It's especially odd since AFAIK essentially every other object format in the world uses a separate relocation table instead of inline magic opcodes like this.
we discussed relocations before, right? ;)
I believe relocations are ugly. elf has no other way to deal with it, since .text has valid cpu instructions and generic loader has to adjust them without knowing hw encoding. Here we have pseudo instructions that are much easier to check/track in verifier than relocations.
As you remember in previous series I've tried relocation style and it was ugly. Both as user interface and as extra complexity for verifier.
Does commit log of patch 8 explain map_fd conversion well enough or not?
If not, I'll add more info, but please read it first.
Quoted 4 lines
Quoted 2 lines
ENOENT For
BPF_MAP_LOOKUP_ELEMorBPF_MAP_DELETE_ELEM, indicates that
element with given key was not found.What does it return? (The same question goes for a bunch of the map ops.)
...
Quoted 2 lines
Shouldn't delete return different values depending on whether anything was deleted?
...
Quoted 1 line
Ah, here it is. Please document this with the ops.
I believe it's a standard manpage style to document return values at the end in 'return value' section. I can duplicate it with ops, but is it really necessary?
Quoted 4 lines
Quoted 2 lines
These commands may be used only by a privileged process (one having the
CAP_SYS_ADMINcapability).I hope this goes away :)
hehe.
I think folks obsessed with security will say it should stay this way for looooong time :)
My immediate goal is tracing and there this restriction is necessary anyway.
Quoted 4 lines
I can't shake the feeling that the whole syscall map API is wrong and that, instead, there should be a more general concept of objects provided by the eBPF runtime. Those objects could have methods that are callable by the syscall and callable from eBPF code.
'concept of objects'... sounds abstractly good :) Something concrete you have in mind?
Theoretically I can see how we can add a 'stream' object which user space can read and programs feed stuff to. In other words an 'abstract' trace buffer, but imo it's overdesign. When we need a trace buffer, we'll just add a helper function that pushes stuff to it.
That will be the time when you see how handy pseudo instructions are. In this patch the only '.imm thing', as you say, is map_fd. I'm working on per-cpu local buffer via the same pseudo stuff. Seem to work quite nicely. Let's not get carried on with future cool stuff, basics first :)
Thanks for the feedback!
On 09/10/2014 10:21 PM, Alexei Starovoitov wrote:
...
Quoted 7 lines
Quoted 3 lines
Quoted 1 line
char bpf_log_buf[LOG_BUF_SIZE];What happens if the size isn't
LOG_BUF_SIZE?would do you mean?
LOG_BUF_SIZEis just a user defined macro.
Can be anything.
I believe, Andy means, what would happen if log_level > 0 but the log_size is not big enough so that the human-readable error text string from the verifier will fit into it? I presume that will be truncated then ... hm.
Quoted 4 lines
it's passed along with pointer:
.log_buf = bpf_log_buf, .log_size = LOG_BUF_SIZE, .log_level = 1,
Quoted 9 lines · Daniel Borkmann
On 09/10/2014 10:21 PM, Alexei Starovoitov wrote:
...Quoted 7 lines
Quoted 5 lines
Quoted 2 lines
char bpf_log_buf[LOG_BUF_SIZE];What happens if the size isn't
LOG_BUF_SIZE?
Quoted 8 lines
Quoted 3 lines
would do you mean?
LOG_BUF_SIZEis just a user defined macro.
Can be anything.I believe, Andy means, what would happen if
log_level> 0 but thelog_sizeis not big enough so that the human-readable error text string from the verifier will fit into it? I presume that will be truncated then ... hm.
Correct. It will be truncated and ENOSPC returned from syscall. Just noticed that I didn't mention that in the manpage... will do.