Skip to contentSkip to conversation

eBPF syscall, verifier, testsuite

PATCH Superseded Alexei Starovoitov 2 participants 23 messages Sep 17, 2014 – Sep 18, 2014

Subsystems (9)

v13 of 15 Superseded Latest is v15 →

lore
Share & tools
lore
#0 lore raw

v13 cover eBPF syscall, verifier, testsuite

Hi All,

v12 -> v13:
- replaced 'foo __user *' pointers with __aligned_u64 (suggested by David)
- added __attribute__((aligned(8)) to 'union bpf_attr' to keep constant alignment between patches
- updated manpage and syscall wrappers due to __aligned_u64
- rebased, retested on x64 with 32-bit and 64-bit userspace and on i386, build tested on arm32,sparc64

v11 -> v12:
- 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 (not part of this set) (.. 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 to manpage (.. Andy)
- rebased, tweaked test_stubs

Patches 1-4 establish BPF syscall shell for maps and programs. Patches 5-10 add verifier step by step
Patch 11 adds test stubs for 'unspec' program type and verifier testsuite
from user space

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.

After this set the programs can be loaded for testing only. They cannot be attached to any events. Though manpage talks about tracing and sockets, it will be a subject of future patches.

Please take a look at manpage:

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 */
__u32 map_fd;
__aligned_u64 key;
union {
__aligned_u64 value;
__aligned_u64 next_key;
};
};

struct { /* anonymous struct used by BPF_PROG_LOAD command */
__u32 prog_type;
__u32 insn_cnt;
__aligned_u64 insns; /* 'const struct bpf_insn *' */
__aligned_u64 license; /* 'const char *' */
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
__aligned_u64 log_buf; /* user supplied 'char *' buffer */
};
} __attribute__((aligned(8)));

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. For all map_types eBPF programs access 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 = ptr_to_u64(key),
.value = ptr_to_u64(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 = ptr_to_u64(key),
.value = ptr_to_u64(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 = ptr_to_u64(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 = ptr_to_u64(key),
.next_key = ptr_to_u64(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 = ptr_to_u64(insns),
.insn_cnt = insn_cnt,
.license = ptr_to_u64(license),
.log_buf = ptr_to_u64(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_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.

BPF_PROG_TYPE_UNSPEC is used for testing only. Such programs cannot be attached to events.

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-16 BPF(2)

#1 lore raw

PATCH v13 1/11 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            |   23 ++++++
 kernel/bpf/Makefile                 |    2 +-
 kernel/bpf/syscall.c                |  144 +++++++++++++++++++++++++++++++++++
 5 files changed, 248 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/bpf.h
 create mode 100644 kernel/bpf/syscall.c
Documentation/networking/filter.txt +39 -0
index 81916ab5d96f..1900d29518f1 100644
@@ -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 +23 -0
index 479ed0b6be16..f58a10f9670c 100644
@@ -62,4 +62,27 @@ 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 */
+		__u32	map_type;	/* one of enum bpf_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 */
+	};
+} __attribute__((aligned(8)));
+
 #endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/Makefile +1 -1
index 6a71145e2769..e9f7334ed07a 100644
@@ -1 +1 @@
-obj-y := core.o
+obj-y := core.o syscall.o
kernel/bpf/syscall.c new file +144 -0

144 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#2 lore raw

PATCH v13 2/11 bpf: enable bpf syscall on x64 and i386

In reply to Alexei Starovoitov

done 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
index 028b78168d85..9fe1b5d002f0 100644
@@ -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
index 35dd922727b9..281150b539a2 100644
@@ -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
index 0f86d85a9ce4..bda9b81357cc 100644
@@ -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
index 11d11bc5c78f..22749c134117 100644
@@ -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
index 391d4ddb6f4b..b4b5083f5f5e 100644
@@ -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
#3 lore raw

PATCH v13 3/11 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 |   38 ++++++++
 kernel/bpf/syscall.c     |  235 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 281 insertions(+)
include/linux/bpf.h +8 -0
index 48014a71f0fe..2887f3f9da59 100644
@@ -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 +38 -0
index f58a10f9670c..395cabd2ca0a 100644
@@ -70,6 +70,35 @@ enum bpf_cmd {
 	 * map is deleted when fd is closed
 	 */
 	BPF_MAP_CREATE,
+
+	/* 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
+	 */
+	BPF_MAP_LOOKUP_ELEM,
+
+	/* 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
+	 */
+	BPF_MAP_UPDATE_ELEM,
+
+	/* find and delete elem by key in a given map
+	 * err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size)
+	 * Using attr->map_fd, attr->key
+	 * returns zero or negative error
+	 */
+	BPF_MAP_DELETE_ELEM,
+
+	/* lookup key in a given map and 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
+	 * returns zero and stores next key or negative error
+	 */
+	BPF_MAP_GET_NEXT_KEY,
 };
 
 enum bpf_map_type {
@@ -83,6 +112,15 @@ union bpf_attr {
 		__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 */
+		__u32		map_fd;
+		__aligned_u64	key;
+		union {
+			__aligned_u64 value;
+			__aligned_u64 next_key;
+		};
+	};
 } __attribute__((aligned(8)));
 
 #endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/syscall.c +235 -0

253 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#4 lore raw

PATCH v13 4/11 bpf: expand BPF syscall with program load/unload

In reply to 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(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 = ptr_to_u64(insns),
        .insn_cnt = insn_cnt,
        .license = ptr_to_u64(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      |   38 +++++++++++
 include/linux/filter.h   |    8 +--
 include/uapi/linux/bpf.h |   26 ++++++++
 kernel/bpf/core.c        |   29 ++++----
 kernel/bpf/syscall.c     |  165 ++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 246 insertions(+), 20 deletions(-)
include/linux/bpf.h +38 -0
index 2887f3f9da59..92979182be81 100644
@@ -46,4 +46,42 @@ 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;
+
+struct bpf_prog_aux {
+	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 *prog;
+	struct work_struct work;
+};
+
+void bpf_prog_put(struct bpf_prog *prog);
+struct bpf_prog *bpf_prog_get(u32 ufd);
+
 #endif /* _LINUX_BPF_H */
include/linux/filter.h +2 -6
index 1a0bc6d134d7..4ffc0958d85e 100644
@@ -21,6 +21,7 @@
 struct sk_buff;
 struct sock;
 struct seccomp_data;
+struct bpf_prog_aux;
 
 /* ArgX, context and stack frame pointer register positions. Note,
  * Arg1, Arg2, Arg3, etc are used as argument mappings of function
@@ -300,17 +301,12 @@ struct bpf_binary_header {
 	u8 image[];
 };
 
-struct bpf_work_struct {
-	struct bpf_prog *prog;
-	struct work_struct work;
-};
-
 struct bpf_prog {
 	u16			pages;		/* Number of allocated pages */
 	bool			jited;		/* Is our filter JIT'ed? */
 	u32			len;		/* Number of filter blocks */
 	struct sock_fprog_kern	*orig_prog;	/* Original BPF program */
-	struct bpf_work_struct	*work;		/* Deferred free work struct */
+	struct bpf_prog_aux	*aux;		/* Auxiliary fields */
 	unsigned int		(*bpf_func)(const struct sk_buff *skb,
 					    const struct bpf_insn *filter);
 	/* Instructions for interpreter */
include/uapi/linux/bpf.h +26 -0
index 395cabd2ca0a..424f442016e7 100644
@@ -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 */
 		__u32	map_type;	/* one of enum bpf_map_type */
@@ -121,6 +132,21 @@ union bpf_attr {
 			__aligned_u64 next_key;
 		};
 	};
+
+	struct { /* anonymous struct used by BPF_PROG_LOAD command */
+		__u32		prog_type;	/* one of enum bpf_prog_type */
+		__u32		insn_cnt;
+		__aligned_u64	insns;
+		__aligned_u64	license;
+	};
 } __attribute__((aligned(8)));
 
+/* 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/core.c +15 -14
index 8b7002488251..f0c30c59b317 100644
@@ -27,6 +27,7 @@
 #include <linux/random.h>
 #include <linux/moduleloader.h>
 #include <asm/unaligned.h>
+#include <linux/bpf.h>
 
 /* Registers */
 #define BPF_R0	regs[BPF_REG_0]
@@ -71,7 +72,7 @@ struct bpf_prog *bpf_prog_alloc(unsigned int size, gfp_t gfp_extra_flags)
 {
 	gfp_t gfp_flags = GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO |
 			  gfp_extra_flags;
-	struct bpf_work_struct *ws;
+	struct bpf_prog_aux *aux;
 	struct bpf_prog *fp;
 
 	size = round_up(size, PAGE_SIZE);
@@ -79,14 +80,14 @@ struct bpf_prog *bpf_prog_alloc(unsigned int size, gfp_t gfp_extra_flags)
 	if (fp == NULL)
 		return NULL;
 
-	ws = kmalloc(sizeof(*ws), GFP_KERNEL | gfp_extra_flags);
-	if (ws == NULL) {
+	aux = kzalloc(sizeof(*aux), GFP_KERNEL | gfp_extra_flags);
+	if (aux == NULL) {
 		vfree(fp);
 		return NULL;
 	}
 
 	fp->pages = size / PAGE_SIZE;
-	fp->work = ws;
+	fp->aux = aux;
 
 	return fp;
 }
@@ -110,10 +111,10 @@ struct bpf_prog *bpf_prog_realloc(struct bpf_prog *fp_old, unsigned int size,
 		memcpy(fp, fp_old, fp_old->pages * PAGE_SIZE);
 		fp->pages = size / PAGE_SIZE;
 
-		/* We keep fp->work from fp_old around in the new
+		/* We keep fp->aux from fp_old around in the new
 		 * reallocated structure.
 		 */
-		fp_old->work = NULL;
+		fp_old->aux = NULL;
 		__bpf_prog_free(fp_old);
 	}
 
@@ -123,7 +124,7 @@ EXPORT_SYMBOL_GPL(bpf_prog_realloc);
 
 void __bpf_prog_free(struct bpf_prog *fp)
 {
-	kfree(fp->work);
+	kfree(fp->aux);
 	vfree(fp);
 }
 EXPORT_SYMBOL_GPL(__bpf_prog_free);
@@ -638,19 +639,19 @@ EXPORT_SYMBOL_GPL(bpf_prog_select_runtime);
 
 static void bpf_prog_free_deferred(struct work_struct *work)
 {
-	struct bpf_work_struct *ws;
+	struct bpf_prog_aux *aux;
 
-	ws = container_of(work, struct bpf_work_struct, work);
-	bpf_jit_free(ws->prog);
+	aux = container_of(work, struct bpf_prog_aux, work);
+	bpf_jit_free(aux->prog);
 }
 
 /* Free internal BPF program */
 void bpf_prog_free(struct bpf_prog *fp)
 {
-	struct bpf_work_struct *ws = fp->work;
+	struct bpf_prog_aux *aux = fp->aux;
 
-	INIT_WORK(&ws->work, bpf_prog_free_deferred);
-	ws->prog = fp;
-	schedule_work(&ws->work);
+	INIT_WORK(&aux->work, bpf_prog_free_deferred);
+	aux->prog = fp;
+	schedule_work(&aux->work);
 }
 EXPORT_SYMBOL_GPL(bpf_prog_free);
kernel/bpf/syscall.c +165 -0

183 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#5 lore raw

PATCH v13 5/11 bpf: handle pseudo BPF_CALL insn

In reply to Alexei Starovoitov

in 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
index a5b5c7ca0264..5a45cdc511e1 100644
@@ -357,6 +357,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->aux->ops->get_func_proto);
+
+			fn = prog->aux->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_used_maps(struct bpf_prog_aux *aux)
 {
@@ -478,6 +512,9 @@ static int bpf_prog_load(union bpf_attr *attr)
 	if (err < 0)
 		goto free_used_maps;
 
+	/* 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
#6 lore raw

PATCH v13 6/11 bpf: verifier (add docs)

In reply to Alexei Starovoitov

this 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
index 1900d29518f1..f1c90967f748 100644
@@ -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
index 92979182be81..9dfeb36f8971 100644
@@ -83,5 +83,7 @@ struct bpf_prog_aux {
 
 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
index e9f7334ed07a..3c726b0995b7 100644
@@ -1 +1 @@
-obj-y := core.o syscall.o
+obj-y := core.o syscall.o verifier.o
kernel/bpf/syscall.c +1 -1
index 5a45cdc511e1..67b5e29f183e 100644
@@ -507,7 +507,7 @@ static int bpf_prog_load(union bpf_attr *attr)
 		goto free_prog;
 
 	/* run eBPF verifier */
-	/* err = bpf_check(prog, tb); */
+	err = bpf_check(prog, attr);
 
 	if (err < 0)
 		goto free_used_maps;
kernel/bpf/verifier.c new file +133 -0

133 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#7 lore raw

PATCH v13 7/11 bpf: verifier (add ability to receive verification log)

In reply to Alexei Starovoitov

add optional attributes for BPF_PROG_LOAD syscall:
union bpf_attr {
struct {
...
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
__aligned_u64 log_buf; /* user supplied 'char *buffer' */
};
};

when log_level > 0 the verifier will return its verification log in the user supplied buffer 'log_buf' which can be used by program author to analyze why verifier rejected given program.

'Understanding eBPF verifier messages' section of Documentation/networking/filter.txt provides several examples of these messages, like 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(),

will be rejected with the following multi-line message in log_buf:

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

The format of the output can change at any time as verifier evolves.

---
 include/uapi/linux/bpf.h |    3 +
 kernel/bpf/syscall.c     |    2 +-
 kernel/bpf/verifier.c    |  235 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 239 insertions(+), 1 deletion(-)
include/uapi/linux/bpf.h +3 -0
index 424f442016e7..31b0ac208a52 100644
@@ -138,6 +138,9 @@ union bpf_attr {
 		__u32		insn_cnt;
 		__aligned_u64	insns;
 		__aligned_u64	license;
+		__u32		log_level;	/* verbosity level of verifier */
+		__u32		log_size;	/* size of user buffer */
+		__aligned_u64	log_buf;	/* user supplied buffer */
 	};
 } __attribute__((aligned(8)));
 
kernel/bpf/syscall.c +1 -1
index 67b5e29f183e..c7be7163bd11 100644
@@ -458,7 +458,7 @@ struct bpf_prog *bpf_prog_get(u32 ufd)
 }
 
 /* last field in 'union bpf_attr' used by this command */
-#define	BPF_PROG_LOAD_LAST_FIELD license
+#define	BPF_PROG_LOAD_LAST_FIELD log_buf
 
 static int bpf_prog_load(union bpf_attr *attr)
 {
kernel/bpf/verifier.c +235 -0

244 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#8 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 66 lines · Alexei Starovoitov

add optional attributes for BPF_PROG_LOAD syscall:
union bpf_attr {
struct {
...
__u32 log_level; /* verbosity level of eBPF verifier */
__u32 log_size; /* size of user buffer */
__aligned_u64 log_buf; /* user supplied 'char *buffer' */
};
};

when log_level > 0 the verifier will return its verification log in the user supplied buffer 'log_buf' which can be used by program author to analyze why verifier rejected given program.

'Understanding eBPF verifier messages' section of Documentation/networking/filter.txt provides several examples of these messages, like 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(),

will be rejected with the following multi-line message in log_buf:

   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

The format of the output can change at any time as verifier evolves.

---
  include/uapi/linux/bpf.h |    3 +
  kernel/bpf/syscall.c     |    2 +-
  kernel/bpf/verifier.c    |  235 ++++++++++++++++++++++++++++++++++++++++++++++
  3 files changed, 239 insertions(+), 1 deletion(-)
include/uapi/linux/bpf.h +3 -0
index 424f442016e7..31b0ac208a52 100644
@@ -138,6 +138,9 @@ union bpf_attr {
  		__u32		insn_cnt;
  		__aligned_u64	insns;
  		__aligned_u64	license;
+		__u32		log_level;	/* verbosity level of verifier */
+		__u32		log_size;	/* size of user buffer */
+		__aligned_u64	log_buf;	/* user supplied buffer */
  	};
  } __attribute__((aligned(8)));
 
kernel/bpf/syscall.c +0 -0
index 67b5e29f183e..c7be7163bd11 100644

kernel/bpf/syscall.c struct bpf_prog *bpf_prog_get(u32 ufd) · line 461

Quoted 5 lines
kernel/bpf/syscall.c +1 -1
@@ -458,7 +458,7 @@ struct bpf_prog *bpf_prog_get(u32 ufd)
  }
 
  /* last field in 'union bpf_attr' used by this command */
-#define	BPF_PROG_LOAD_LAST_FIELD license
+#define	BPF_PROG_LOAD_LAST_FIELD log_buf

I was looking to find a use case for this item, but couldn't find anything, so this seems to be dead code?

Was it, so that each time you extend an uapi structure like above that you would only access the structure up to BPF_PROG_LOAD_LAST_FIELD? That might not work for old binaries using this ABI running on newer kernels where there are different expectations of what BPF_PROG_LOAD_LAST_FIELD has been at the time of compilation.

Quoted 193 lines
kernel/bpf/syscall.c +0 -0
  static int bpf_prog_load(union bpf_attr *attr)
  {
kernel/bpf/verifier.c +179 -0
index d6f9c3d6b4d7..871edc1f2e1f 100644
@@ -125,9 +125,244 @@
   * are set to NOT_INIT to indicate that they are no longer readable.
   */
 
+/* single container for all structs
+ * one verifier_env per bpf_check() call
+ */
+struct verifier_env {
+};
+
+/* verbose verifier prints what it's seeing
+ * bpf_check() is called under lock, so no race to access these global vars
+ */
+static u32 log_level, log_size, log_len;
+static char *log_buf;
+
+static DEFINE_MUTEX(bpf_verifier_lock);
+
+/* log_level controls verbosity level of eBPF verifier.
+ * verbose() is used to dump the verification trace to the log, so the user
+ * can figure out what's wrong with the program
+ */
+static void verbose(const char *fmt, ...)
+{
+	va_list args;
+
+	if (log_level == 0 || log_len >= log_size - 1)
+		return;
+
+	va_start(args, fmt);
+	log_len += vscnprintf(log_buf + log_len, log_size - log_len, fmt, args);
+	va_end(args);
+}
+
+static const char *const bpf_class_string[] = {
+	[BPF_LD]    = "ld",
+	[BPF_LDX]   = "ldx",
+	[BPF_ST]    = "st",
+	[BPF_STX]   = "stx",
+	[BPF_ALU]   = "alu",
+	[BPF_JMP]   = "jmp",
+	[BPF_RET]   = "BUG",
+	[BPF_ALU64] = "alu64",
+};
+
+static const char *const bpf_alu_string[] = {
+	[BPF_ADD >> 4]  = "+=",
+	[BPF_SUB >> 4]  = "-=",
+	[BPF_MUL >> 4]  = "*=",
+	[BPF_DIV >> 4]  = "/=",
+	[BPF_OR  >> 4]  = "|=",
+	[BPF_AND >> 4]  = "&=",
+	[BPF_LSH >> 4]  = "<<=",
+	[BPF_RSH >> 4]  = ">>=",
+	[BPF_NEG >> 4]  = "neg",
+	[BPF_MOD >> 4]  = "%=",
+	[BPF_XOR >> 4]  = "^=",
+	[BPF_MOV >> 4]  = "=",
+	[BPF_ARSH >> 4] = "s>>=",
+	[BPF_END >> 4]  = "endian",
+};
+
+static const char *const bpf_ldst_string[] = {
+	[BPF_W >> 3]  = "u32",
+	[BPF_H >> 3]  = "u16",
+	[BPF_B >> 3]  = "u8",
+	[BPF_DW >> 3] = "u64",
+};
+
+static const char *const bpf_jmp_string[] = {
+	[BPF_JA >> 4]   = "jmp",
+	[BPF_JEQ >> 4]  = "==",
+	[BPF_JGT >> 4]  = ">",
+	[BPF_JGE >> 4]  = ">=",
+	[BPF_JSET >> 4] = "&",
+	[BPF_JNE >> 4]  = "!=",
+	[BPF_JSGT >> 4] = "s>",
+	[BPF_JSGE >> 4] = "s>=",
+	[BPF_CALL >> 4] = "call",
+	[BPF_EXIT >> 4] = "exit",
+};
+
+static void print_bpf_insn(struct bpf_insn *insn)
+{
+	u8 class = BPF_CLASS(insn->code);
+
+	if (class == BPF_ALU || class == BPF_ALU64) {
+		if (BPF_SRC(insn->code) == BPF_X)
+			verbose("(%02x) %sr%d %s %sr%d\n",
+				insn->code, class == BPF_ALU ? "(u32) " : "",
+				insn->dst_reg,
+				bpf_alu_string[BPF_OP(insn->code) >> 4],
+				class == BPF_ALU ? "(u32) " : "",
+				insn->src_reg);
+		else
+			verbose("(%02x) %sr%d %s %s%d\n",
+				insn->code, class == BPF_ALU ? "(u32) " : "",
+				insn->dst_reg,
+				bpf_alu_string[BPF_OP(insn->code) >> 4],
+				class == BPF_ALU ? "(u32) " : "",
+				insn->imm);
+	} else if (class == BPF_STX) {
+		if (BPF_MODE(insn->code) == BPF_MEM)
+			verbose("(%02x) *(%s *)(r%d %+d) = r%d\n",
+				insn->code,
+				bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+				insn->dst_reg,
+				insn->off, insn->src_reg);
+		else if (BPF_MODE(insn->code) == BPF_XADD)
+			verbose("(%02x) lock *(%s *)(r%d %+d) += r%d\n",
+				insn->code,
+				bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+				insn->dst_reg, insn->off,
+				insn->src_reg);
+		else
+			verbose("BUG_%02x\n", insn->code);
+	} else if (class == BPF_ST) {
+		if (BPF_MODE(insn->code) != BPF_MEM) {
+			verbose("BUG_st_%02x\n", insn->code);
+			return;
+		}
+		verbose("(%02x) *(%s *)(r%d %+d) = %d\n",
+			insn->code,
+			bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+			insn->dst_reg,
+			insn->off, insn->imm);
+	} else if (class == BPF_LDX) {
+		if (BPF_MODE(insn->code) != BPF_MEM) {
+			verbose("BUG_ldx_%02x\n", insn->code);
+			return;
+		}
+		verbose("(%02x) r%d = *(%s *)(r%d %+d)\n",
+			insn->code, insn->dst_reg,
+			bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+			insn->src_reg, insn->off);
+	} else if (class == BPF_LD) {
+		if (BPF_MODE(insn->code) == BPF_ABS) {
+			verbose("(%02x) r0 = *(%s *)skb[%d]\n",
+				insn->code,
+				bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+				insn->imm);
+		} else if (BPF_MODE(insn->code) == BPF_IND) {
+			verbose("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
+				insn->code,
+				bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+				insn->src_reg, insn->imm);
+		} else if (BPF_MODE(insn->code) == BPF_IMM) {
+			verbose("(%02x) r%d = 0x%x\n",
+				insn->code, insn->dst_reg, insn->imm);
+		} else {
+			verbose("BUG_ld_%02x\n", insn->code);
+			return;
+		}
+	} else if (class == BPF_JMP) {
+		u8 opcode = BPF_OP(insn->code);
+
+		if (opcode == BPF_CALL) {
+			verbose("(%02x) call %d\n", insn->code, insn->imm);
+		} else if (insn->code == (BPF_JMP | BPF_JA)) {
+			verbose("(%02x) goto pc%+d\n",
+				insn->code, insn->off);
+		} else if (insn->code == (BPF_JMP | BPF_EXIT)) {
+			verbose("(%02x) exit\n", insn->code);
+		} else if (BPF_SRC(insn->code) == BPF_X) {
+			verbose("(%02x) if r%d %s r%d goto pc%+d\n",
+				insn->code, insn->dst_reg,
+				bpf_jmp_string[BPF_OP(insn->code) >> 4],
+				insn->src_reg, insn->off);
+		} else {
+			verbose("(%02x) if r%d %s 0x%x goto pc%+d\n",
+				insn->code, insn->dst_reg,
+				bpf_jmp_string[BPF_OP(insn->code) >> 4],
+				insn->imm, insn->off);
+		}
+	} else {
+		verbose("(%02x) %s\n", insn->code, bpf_class_string[class]);
+	}
+}
+
  int bpf_check(struct bpf_prog *prog, union bpf_attr *attr)
  {
+	char __user *log_ubuf = NULL;
+	struct verifier_env *env;
  	int ret = -EINVAL;
 
+	if (prog->len <= 0 || prog->len > BPF_MAXINSNS)
+		return -E2BIG;

kernel/bpf/verifier.c line 320

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+
+	/* 'struct verifier_env' can be global, but since it's not small,
+	 * allocate/free it every time bpf_check() is called
+	 */
+	env = kzalloc(sizeof(struct verifier_env), GFP_KERNEL);
+	if (!env)
+		return -ENOMEM;
+
+	/* grab the mutex to protect few globals used by verifier */
+	mutex_lock(&bpf_verifier_lock);

So only because of the verifier error log (which are global vars here) we now have to hold a eBPF-related mutex lock each time when attaching a program?

Also, if you really have to do the verifier error log, can't we spare ourself most part of the textifying parts if you would encode the verifier log into a normal structure array with eBPF specific error codes and then do all this pretty printing in user space? Why is that impossible? I really think it's odd.

Quoted 48 lines
kernel/bpf/verifier.c +45 -0
+	if (attr->log_level || attr->log_buf || attr->log_size) {
+		/* user requested verbose verifier output
+		 * and supplied buffer to store the verification trace
+		 */
+		log_level = attr->log_level;
+		log_ubuf = (char __user *) (unsigned long) attr->log_buf;
+		log_size = attr->log_size;
+		log_len = 0;
+
+		ret = -EINVAL;
+		/* log_* values have to be sane */
+		if (log_size < 128 || log_size > UINT_MAX >> 8 ||
+		    log_level == 0 || log_ubuf == NULL)
+			goto free_env;
+
+		ret = -ENOMEM;
+		log_buf = vmalloc(log_size);
+		if (!log_buf)
+			goto free_env;
+	} else {
+		log_level = 0;
+	}
+
+	/* ret = do_check(env); */
+
+	if (log_level && log_len >= log_size - 1) {
+		BUG_ON(log_len >= log_size);
+		/* verifier log exceeded user supplied buffer */
+		ret = -ENOSPC;
+		/* fall through to return what was recorded */
+	}
+
+	/* copy verifier log back to user space including trailing zero */
+	if (log_level && copy_to_user(log_ubuf, log_buf, log_len + 1) != 0) {
+		ret = -EFAULT;
+		goto free_log_buf;
+	}
+
+
+free_log_buf:
+	if (log_level)
+		vfree(log_buf);
+free_env:
+	kfree(env);
+	mutex_unlock(&bpf_verifier_lock);
  	return ret;
  }
#9 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 9 lines · Daniel Borkmann

kernel/bpf/syscall.c struct bpf_prog *bpf_prog_get(u32 ufd) · line 461

Quoted 4 lines

/* last field in 'union bpf_attr' used by this command */

kernel/bpf/syscall.c +1 -1
-#define        BPF_PROG_LOAD_LAST_FIELD license
+#define        BPF_PROG_LOAD_LAST_FIELD log_buf

I was looking to find a use case for this item, but couldn't find anything, so
this seems to be dead code?

See CHECK_ATTR() macro and comment next to it in patch #1

Quoted 8 lines

Was it, so that each time you extend an uapi structure like above that you would
only access the structure up to BPF_PROG_LOAD_LAST_FIELD? That might not work for
old binaries using this ABI running on newer kernels where there are different
expectations of what BPF_PROG_LOAD_LAST_FIELD has been at the time of compilation.

exactly the opposite.
CHECK_ATTR() is checking that all fields beyond last for given command are zero, so we can extend bpf_attr with new fields added after last.
Transition from patch 4 to patch 7 and the hunk you quoted are demonstrating exactly that. Say, userspace was compiled
with bpf_attr as defined in patch 4 and it populated fields all the way till 'license', and kernel is compiled with patch 7. Kernel does:
union bpf_attr attr = {};
/* copy attributes from user space, may be less than sizeof(bpf_attr) */ copy_from_user(&attr, uattr, size)
so newer fields (all the way till log_buf) stay zero and kernel behavior is the same as it was in patch 4.
So older user space works as-is with newer kernel.
Another example:
say, we want to add another flag to lookup() method added in patch 3, we just add another 'flags' field after 'value' field and adjust:
-#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD value
+#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD flags
Older user apps stay binary compatible with newer kernel. Does this explain things?

Quoted 8 lines

kernel/bpf/verifier.c line 320

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+
+       /* grab the mutex to protect few globals used by verifier */
+       mutex_lock(&bpf_verifier_lock);

So only because of the verifier error log (which are global vars here) we now have to hold a eBPF-related mutex lock each time when attaching a program?

correct.
it's done on purpose to simplify verifier code.
User app is blocked in bpf syscall until verifier checks the program. Not a big deal. I don't expect a lot of concurrent program loading. If it somehow becomes an issue, when can fix it, but for now I think less lines of verifier code is definitely a better trade off.

Quoted 7 lines

Also, if you really have to do the verifier error log, can't we spare ourself
most part of the textifying parts if you would encode the verifier log into a
normal structure array with eBPF specific error codes and then do all this pretty printing in user space? Why is that impossible? I really think it's odd.

I thought I explained this already...
verifier log is not at all "an array of specific error codes". verifier is printing the trace and state of what it's seeing while analyzing the program. Very branchy program may generate a trace log several times larger than program size. pretty text is the most convenient way to pass it to user. Theoretically we can come with some obscure log format for this internal verifier state, but what do we get ? only additional complexity. This obscure format will change just as text will change, because verifier will evolve. If you're looking for a way to fix this output into ABI, it's not possible. Verifier will become more advanced in the future and it's trace whether in text or in obscure encoded structs will change. Therefore text is much simpler option.
Also consider the learning curve for somebody planning to add new features to verifier. This trace log is a perfect way to understand how verifier is working. Try simple program with multiple branches and see what kind of log is dumped.

Another example:
To make verifier easier to review, in this patch set I didn't include 'state pruning optimization' patch. That patch will change the trace log, because it changes the way verifier is working. If we had to introduce struct encoding of trace log, it would need to be changed already. So pretty text is the simplest and most convenient way.

#10 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 21 lines · Alexei Starovoitov
Quoted 8 lines · Daniel Borkmann

kernel/bpf/syscall.c struct bpf_prog *bpf_prog_get(u32 ufd) · line 461

Quoted 4 lines
   /* last field in 'union bpf_attr' used by this command */
kernel/bpf/syscall.c +1 -1
-#define        BPF_PROG_LOAD_LAST_FIELD license
+#define        BPF_PROG_LOAD_LAST_FIELD log_buf

I was looking to find a use case for this item, but couldn't find anything, so
this seems to be dead code?

See CHECK_ATTR() macro and comment next to it in patch #1

Quoted 8 lines

Was it, so that each time you extend an uapi structure like above that you would
only access the structure up to BPF_PROG_LOAD_LAST_FIELD? That might not work for
old binaries using this ABI running on newer kernels where there are different
expectations of what BPF_PROG_LOAD_LAST_FIELD has been at the time of compilation.

Quoted 14 lines

exactly the opposite.
CHECK_ATTR() is checking that all fields beyond last for given command are zero, so we can extend bpf_attr with new fields added after last.
Transition from patch 4 to patch 7 and the hunk you quoted are demonstrating exactly that. Say, userspace was compiled
with bpf_attr as defined in patch 4 and it populated fields all the way till 'license', and kernel is compiled with patch 7. Kernel does:
union bpf_attr attr = {};
/* copy attributes from user space, may be less than sizeof(bpf_attr) */ copy_from_user(&attr, uattr, size)
so newer fields (all the way till log_buf) stay zero and kernel behavior is the same as it was in patch 4.
So older user space works as-is with newer kernel.

Ok, I see. Lets say, since the introduction of this syscall you have added a couple of features and thus extended union bpf_attr where it grew in size over time.

You built your shiny new binary on that uapi setting, and later on decide to run it on an older kernel. What will happen is that in your bpf syscall handler you will return with -EINVAL on that kernel right away since the size of union bpf_attr is greater.

That would mean over time when new features will get added, applications that want to make sure to run on _all_ kernels where the bpf syscall is available have to make sure to either use the _initial_ version of union bpf_attr in order to not get an -EINVAL, or worse they have to probe though a syscall different versions of union bpf_attr if they wish to make use of a particular feature until they do not get an -EINVAL anymore.

I guess that might be problematic for an application developer that wants to ship its application across different distributions usually running different kernels. At least those people might then consider holding a private copy of the _initial_ version of union bpf_attr in their own source code, but it's not pleasant I guess.

I know you seem to have the constraint to run on NET-less systems, but netlink could partially resolve that in the sense that it would allow to at least load an eBPF program with initial feature set. Couldn't there be some mechanism to make this interaction more pleasant? E.g. in BPF extensions we can ask the kernel up to what extension it supports and accordingly adapt to it up front. I know it's just a /trivial/ example but have you thought about something on that kind for the syscall?

#11 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 60 lines · Daniel Borkmann
Quoted 21 lines · Alexei Starovoitov
Quoted 8 lines · Daniel Borkmann

kernel/bpf/syscall.c struct bpf_prog *bpf_prog_get(u32 ufd) · line 461

Quoted 4 lines
   /* last field in 'union bpf_attr' used by this command */
kernel/bpf/syscall.c +1 -1
-#define        BPF_PROG_LOAD_LAST_FIELD license
+#define        BPF_PROG_LOAD_LAST_FIELD log_buf

I was looking to find a use case for this item, but couldn't find anything, so
this seems to be dead code?

See CHECK_ATTR() macro and comment next to it in patch #1

Quoted 8 lines

Was it, so that each time you extend an uapi structure like above that you would
only access the structure up to BPF_PROG_LOAD_LAST_FIELD? That might not work for
old binaries using this ABI running on newer kernels where there are different
expectations of what BPF_PROG_LOAD_LAST_FIELD has been at the time of compilation.

Quoted 14 lines

exactly the opposite.
CHECK_ATTR() is checking that all fields beyond last for given command are zero, so we can extend bpf_attr with new fields added after last.
Transition from patch 4 to patch 7 and the hunk you quoted are demonstrating exactly that. Say, userspace was compiled
with bpf_attr as defined in patch 4 and it populated fields all the way till 'license', and kernel is compiled with patch 7. Kernel does:
union bpf_attr attr = {};
/* copy attributes from user space, may be less than sizeof(bpf_attr) */ copy_from_user(&attr, uattr, size)
so newer fields (all the way till log_buf) stay zero and kernel behavior is the same as it was in patch 4.
So older user space works as-is with newer kernel.

Ok, I see. Lets say, since the introduction of this syscall you have added a couple of features and thus extended union bpf_attr where it grew in size over time.

You built your shiny new binary on that uapi setting, and later on decide to run it on an older kernel. What will happen is that in your bpf syscall handler you will return with -EINVAL on that kernel right away since the size of union bpf_attr is greater.

That would mean over time when new features will get added, applications that want to make sure to run on _all_ kernels where the bpf syscall is available have to make sure to either use the _initial_ version of union bpf_attr in order to not get an -EINVAL, or worse they have to probe though a syscall different versions of union bpf_attr if they wish to make use of a particular feature until they do not get an -EINVAL anymore.

I guess that might be problematic for an application developer that wants to ship its application across different distributions usually running different kernels. At least those people might then consider holding a private copy of the _initial_ version of union bpf_attr in their own source code, but it's not pleasant I guess.

Quoted 8 lines

I know you seem to have the constraint to run on NET-less systems, but netlink could partially resolve that in the sense that it would allow to at least load an eBPF program with initial feature set. Couldn't there be some mechanism to make this interaction more pleasant? E.g. in BPF extensions we can ask the kernel up to what extension it supports and accordingly adapt to it up front. I know it's just a /trivial/ example but have you thought about something on that kind for the syscall?

Hm, thinking out loudly ... perhaps this could be made a library problem. Such that the library which wraps the syscall needs to be aware of a marker where the initial version ends, and if the application doesn't make use of any of the new features, it would just pass in the length up to the marker as size attribute into the syscall. Similarly, if new features are always added to the end of a structure and the library truncates the overall-length after the last used member we might have a chance to load something on older kernels, haven't tried that though.

#12 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 6 lines · Daniel Borkmann
Quoted 5 lines · Daniel Borkmann

You built your shiny new binary on that uapi setting, and later on decide to run it on an older kernel. What will happen is that in your bpf syscall handler you will return with -EINVAL on that kernel right away since the size of union bpf_attr is greater.

that's a correct description of the code in this set. What I mentioned in cover letter during v7 was:
"I've decided not to bother with forward compatiblity for now. We can address it later the way perf_event_open did." I was trying not open this can of worms :)

Quoted 7 lines
Quoted 7 lines

That would mean over time when new features will get added, applications that want to make sure to run on _all_ kernels where the bpf syscall is available have to make sure to either use the _initial_ version of union bpf_attr in order to not get an -EINVAL, or worse they have to probe though a syscall different versions of union bpf_attr if they wish to make use of a particular feature until they do not get an -EINVAL anymore.

Correct as well.
I say that would be the least of user space concerns. If user app is built with newer bpf_attr and relies on it for some functionality, it would need a lot more than probing. Depending how big the new bpf_attr feature is, the app might not have a workaround for older kernels at all.
So seeing EINVAL on older kernel might be a preferred way.

Quoted 4 lines
Quoted 4 lines

in BPF extensions we can ask the kernel up to what extension it supports and accordingly adapt to it up front. I know it's just a /trivial/ example but have you thought about something on that kind for the syscall?

A 2nd option would be to do what perf_copy_attr() does:
when newer struct is coming from user space, kernel checks that space beyond known last field is all zeros.
We can do the same, but I'm not convinced that it will help userspace much. Newer user space can only be _compiled_ with newer bpf_attr. It is still cannot use any new features and it needs to make sure that all new fields are zero. I'm not sure how it helps.
perf_event_open() also returns size. In that case it's helpful, since it's one structure. In ebpf case we have multiple structures under one union, so returning size of the whole bpf_attr doesn't help one particular command.

Quoted 8 lines

Hm, thinking out loudly ... perhaps this could be made a library problem. Such that the library which wraps the syscall needs to be aware of a marker where the initial version ends, and if the application doesn't make use of any of the new features, it would just pass in the length up to the marker as size attribute into the syscall. Similarly, if new features are always added to the end of a structure and the library truncates the overall-length after the last used member we might have a chance to load something on older kernels, haven't tried that though.

that's a 3rd option. I think it's cleaner than 2nd, since it solves it completely from user space.
It can even be smarter than that. If this syscall wrapper library sees that newer features are used and it can workaround them:
it can chop size and pass older fields into the older kernel and when it returns, do a workaround based on newer fields.

#13 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 10 lines · Alexei Starovoitov
Quoted 9 lines

Hm, thinking out loudly ... perhaps this could be made a library problem. Such that the library which wraps the syscall needs to be aware of a marker where the initial version ends, and if the application doesn't make use of any of the new features, it would just pass in the length up to the marker as size attribute into the syscall. Similarly, if new features are always added to the end of a structure and the library truncates the overall-length after the last used member we might have a chance to load something on older kernels, haven't tried that though.

Quoted 6 lines

that's a 3rd option. I think it's cleaner than 2nd, since it solves it completely from user space.
It can even be smarter than that. If this syscall wrapper library sees that newer features are used and it can workaround them:
it can chop size and pass older fields into the older kernel and when it returns, do a workaround based on newer fields.

the more I think about 'new user space + old kernel' problem, the more certain I am that kernel should not try to help user space, since most of the time it's not going to be enough, but additional code in kernel would need to be maintained.

syscall commands and size of bpf_attr is the least of problems. New map_type and prog_type will be added, new helper functions will be available to programs.
One would think that md5 of uapi/linux/bpf.h would be enough to say that user app is compatible... In reality, it's not. The 'state pruning' verifier optimization I've talked about will not change a single bit in bpf.h, but it will be able to recognize more programs as safe.
A program developed on a new kernel with more advanced verifier will load just fine on new kernel, but this valid program will not load on old kernel, only because verifier is not smart enough. Now we would need a version of verifier exposed all the way to user space?!
imo that's too much. I think for eBPF infra kernel should only guarantee backwards compatibility
(old user space must work with new kernel) and that's it. That's what this patch is trying to do.
Thoughts?

#14 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 33 lines · Alexei Starovoitov
Quoted 10 lines · Alexei Starovoitov
Quoted 9 lines

Hm, thinking out loudly ... perhaps this could be made a library problem. Such that the library which wraps the syscall needs to be aware of a marker where the initial version ends, and if the application doesn't make use of any of the new features, it would just pass in the length up to the marker as size attribute into the syscall. Similarly, if new features are always added to the end of a structure and the library truncates the overall-length after the last used member we might have a chance to load something on older kernels, haven't tried that though.

Quoted 6 lines

that's a 3rd option. I think it's cleaner than 2nd, since it solves it completely from user space.
It can even be smarter than that. If this syscall wrapper library sees that newer features are used and it can workaround them:
it can chop size and pass older fields into the older kernel and when it returns, do a workaround based on newer fields.

the more I think about 'new user space + old kernel' problem, the more certain I am that kernel should not try to help user space, since most of the time it's not going to be enough, but additional code in kernel would need to be maintained.

syscall commands and size of bpf_attr is the least of problems. New map_type and prog_type will be added, new helper functions will be available to programs.
One would think that md5 of uapi/linux/bpf.h would be enough to say that user app is compatible... In reality, it's not. The 'state pruning' verifier optimization I've talked about will not change a single bit in bpf.h, but it will be able to recognize more programs as safe.
A program developed on a new kernel with more advanced verifier will load just fine on new kernel, but

Quoted 8 lines

this valid program will not load on old kernel, only because verifier is not smart enough. Now we would need a version of verifier exposed all the way to user space?! imo that's too much. I think for eBPF infra kernel should only guarantee backwards compatibility
(old user space must work with new kernel) and that's it. That's what this patch is trying to do.
Thoughts?

Sure, you will never get a full compatibility on that regard while backwards compatibility needs to be guaranteed on the other hand. I looked at perf_copy_attr() implementation and I think that we should mimic it in a very similar way as it exactly solves what we need.

For example, it will return with -EINVAL for (size > PAGE_SIZE) and (size < PERF_ATTR_SIZE_VER0) where PAGE_SIZE has been chosen as an arbitrary hard upper limit where it is believed that it will never grow beyond that large limit in future.

So this is a more loose constraint than what we currently do, that is, -EINVAL on (size > sizeof(attr)) where attr is the currently known size of a specific kernel. That would at least be a start, you won't be able to cover everything though, but it would allow to address the issue raised when running with a basic feature set.

#15 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 61 lines · Daniel Borkmann
Quoted 39 lines · Alexei Starovoitov
Quoted 13 lines · Alexei Starovoitov
Quoted 11 lines

Hm, thinking out loudly ... perhaps this could be made a library problem.
Such that the library which wraps the syscall needs to be aware of a marker where the initial version ends, and if the application doesn't make use of any of the new features, it would just pass in the length up to the marker as size attribute into the syscall. Similarly, if new features are always added to the end of a structure and the library truncates the overall-length after the last used member we might have a chance to load something on older kernels, haven't tried that though.

Quoted 6 lines

that's a 3rd option. I think it's cleaner than 2nd, since it solves it completely from user space.
It can even be smarter than that. If this syscall wrapper library sees that newer features are used and it can workaround them:
it can chop size and pass older fields into the older kernel and when it returns, do a workaround based on newer fields.

the more I think about 'new user space + old kernel' problem, the more certain I am that kernel should not try to help user space, since most of the time it's not going to be enough, but additional code in kernel would need to be maintained.

syscall commands and size of bpf_attr is the least of problems. New map_type and prog_type will be added, new helper functions will be available to programs.
One would think that md5 of uapi/linux/bpf.h would be enough to say that user app is compatible... In reality, it's not. The 'state pruning' verifier optimization I've talked about will not change a single bit in bpf.h, but it will be able to recognize more programs as safe.
A program developed on a new kernel with more advanced verifier will load just fine on new kernel, but

Quoted 8 lines

this valid program will not load on old kernel, only because verifier is not smart enough. Now we would need a version of verifier exposed all the way to user space?! imo that's too much. I think for eBPF infra kernel should only guarantee backwards compatibility
(old user space must work with new kernel) and that's it. That's what this patch is trying to do.
Thoughts?

Sure, you will never get a full compatibility on that regard while backwards compatibility needs to be guaranteed on the other hand. I looked at perf_copy_attr() implementation and I think that we should mimic it in a very similar way as it exactly solves what we need.

For example, it will return with -EINVAL for (size > PAGE_SIZE) and (size < PERF_ATTR_SIZE_VER0) where PAGE_SIZE has been chosen as an arbitrary hard upper limit where it is believed that it will never grow beyond that large limit in future.

Quoted 6 lines

So this is a more loose constraint than what we currently do, that is, -EINVAL on (size > sizeof(attr)) where attr is the currently known size of a specific kernel. That would at least be a start, you won't be able to cover everything though, but it would allow to address the issue raised when running with a basic feature set.

you missed my point. We should not 'do a start', since it doesn't help user space in the long run and only makes kernel more complex.

#16 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 1 line · Alexei Starovoitov

On Wed, Sep 17, 2014 at 11:44 PM, Daniel Borkmann <[email protected]> wrote:

...

Quoted 18 lines
Quoted 11 lines

Sure, you will never get a full compatibility on that regard while backwards compatibility needs to be guaranteed on the other hand. I looked at perf_copy_attr() implementation and I think that we should mimic it in a very similar way as it exactly solves what we need.

For example, it will return with -EINVAL for (size > PAGE_SIZE) and (size < PERF_ATTR_SIZE_VER0) where PAGE_SIZE has been chosen as an arbitrary hard upper limit where it is believed that it will never grow beyond that large limit in future.

Quoted 6 lines

So this is a more loose constraint than what we currently do, that is, -EINVAL on (size > sizeof(attr)) where attr is the currently known size of a specific kernel. That would at least be a start, you won't be able to cover everything though, but it would allow to address the issue raised when running with a basic feature set.

Quoted 3 lines

you missed my point. We should not 'do a start', since it doesn't help user space in the long run and only makes kernel more complex.

Sorry, I don't think I missed your point. But if you see things differently, fair enough, it was just a suggestion.

#17 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

Quoted 26 lines · Daniel Borkmann
Quoted 3 lines · Alexei Starovoitov

On Wed, Sep 17, 2014 at 11:44 PM, Daniel Borkmann <[email protected]> wrote:

...

Quoted 20 lines
Quoted 18 lines

Sure, you will never get a full compatibility on that regard while backwards compatibility needs to be guaranteed on the other hand. I looked at perf_copy_attr() implementation and I think that we should mimic it in a very similar way as it exactly solves what we need.

For example, it will return with -EINVAL for (size > PAGE_SIZE) and (size < PERF_ATTR_SIZE_VER0) where PAGE_SIZE has been chosen as an arbitrary hard upper limit where it is believed that it will never grow beyond that large limit in future.

So this is a more loose constraint than what we currently do, that is, -EINVAL on (size > sizeof(attr)) where attr is the currently known size of a specific kernel. That would at least be a start, you won't be able to cover everything though, but it would allow to address the issue raised when running with a basic feature set.

Quoted 7 lines
Quoted 3 lines

you missed my point. We should not 'do a start', since it doesn't help user space in the long run and only makes kernel more complex.

Sorry, I don't think I missed your point. But if you see things differently, fair enough, it was just a suggestion.

now you probably think I'm shutting you up. Sorry. Was not my intention. Let me rephrase what I meant:
I think we should decide right now whether
'new user + old kernel' is really a problem we're going to solve or not. If we decide to solve it, we need to have a plan to solve it all the way. Partial fix for size of bpf_attr is not a plan. It's something that is not addressing the problem completely. Little bit of help is not useful for userspace. It would need to deal with new types, verifier differences and other things that I mentioned earlier. So we either decide that we're going to spend time to solve all of them (not necessarily today, but over long haul) or we're not doing any of it.

#18 lore raw

Re: [PATCH v13 net-next 07/11] bpf: verifier (add ability to receive verification log)

On 09/18/2014 05:24 PM, Alexei Starovoitov wrote:
...

Quoted 6 lines

solve or not. If we decide to solve it, we need to have a plan to solve it all the way. Partial fix for size of bpf_attr is not a plan. It's something that is not addressing the problem completely. Little bit of help is not useful for userspace. It would need to deal with new types, verifier differences and other things that I mentioned earlier.

Hm, I don't think it would be a strict requirement to solve it all the way, and I think that perf_event_open() with perf_copy_attr() is not trying to do so either. It, however, is trying on a ``best effort basis'' to still load something if new features are unused by the binary (I guess you saw the comment in perf_copy_attr()).

Iff, e.g. due to new types we fail at the verifier stage, sure, that's life since we only have backwards-compatible guarantee, but in case we tried to use features we support, we're still able to load the eBPF program while right now, we're rejecting it right up-front. That's just my $0.02 ...

#19 lore raw

PATCH v13 8/11 bpf: handle pseudo BPF_LD_IMM64 insn

In reply to Alexei Starovoitov

eBPF 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
index 4ffc0958d85e..ca95abd2bed1 100644
@@ -145,6 +145,12 @@ struct bpf_prog_aux;
 		.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
#20 lore raw

PATCH v13 9/11 bpf: verifier (add branch/goto checks)

In reply to Alexei Starovoitov

check 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
index 7227543e474b..effab7d1c7e8 100644
@@ -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
#21 lore raw

PATCH v13 10/11 bpf: verifier (add verifier core)

In reply to Alexei Starovoitov

This 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
index 9dfeb36f8971..3cf91754a957 100644
@@ -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
#22 lore raw

PATCH v13 11/11 bpf: mini eBPF library, test stubs and verifier testsuite

In reply to Alexei Starovoitov

1.
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

and BPF_*() macros to build instructions

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      |  116 +++++++++
 lib/Kconfig.debug           |    3 +-
 samples/bpf/Makefile        |   12 +
 samples/bpf/libbpf.c        |   94 ++++++++
 samples/bpf/libbpf.h        |  172 ++++++++++++++
 samples/bpf/test_verifier.c |  548 +++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 948 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
index 3c726b0995b7..45427239f375 100644
@@ -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 +116 -0

116 lines not on this page · raw message

lib/Kconfig.debug +2 -1
index a28590083622..3ac43f34437b 100644
@@ -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
new file mode 100644
index 000000000000..634391797856
@@ -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 +94 -0

94 lines not on this page · raw message

samples/bpf/libbpf.h new file +172 -0

172 lines not on this page · raw message

samples/bpf/test_verifier.c new file +548 -0

548 lines not on this page · raw message

Signature · 1 line
1.7.9.5