bpf: mini eBPF library, test stubs and verifier testsuite

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

Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
Signed-off-by: David S. Miller <davem@davemloft.net>

4 files changed, 826 insertions, 0 deletions

diff --git a/samples/bpf/Makefile b/samples/bpf/Makefile
new file mode 100644
index 000000000000..634391797856
--- /dev/null
+++ b/samples/bpf/Makefile
@@ -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
diff --git a/samples/bpf/libbpf.c b/samples/bpf/libbpf.c
new file mode 100644
index 000000000000..ff6504420738
--- /dev/null
+++ b/samples/bpf/libbpf.c
@@ -0,0 +1,94 @@
+/* eBPF mini library */
+#include <stdlib.h>
+#include <stdio.h>
+#include <linux/unistd.h>
+#include <unistd.h>
+#include <string.h>
+#include <linux/netlink.h>
+#include <linux/bpf.h>
+#include <errno.h>
+#include "libbpf.h"
+
+static __u64 ptr_to_u64(void *ptr)
+{
+        return (__u64) (unsigned long) ptr;
+}
+
+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 syscall(__NR_bpf, BPF_MAP_CREATE, &attr, sizeof(attr));
+}
+
+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 syscall(__NR_bpf, BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
+}
+
+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 syscall(__NR_bpf, BPF_MAP_LOOKUP_ELEM, &attr, sizeof(attr));
+}
+
+int bpf_delete_elem(int fd, void *key)
+{
+        union bpf_attr attr = {
+                .map_fd = fd,
+                .key = ptr_to_u64(key),
+        };
+
+        return syscall(__NR_bpf, BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
+}
+
+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 syscall(__NR_bpf, BPF_MAP_GET_NEXT_KEY, &attr, sizeof(attr));
+}
+
+#define ROUND_UP(x, n) (((x) + (n) - 1u) & ~((n) - 1u))
+
+char bpf_log_buf[LOG_BUF_SIZE];
+
+int bpf_prog_load(enum bpf_prog_type prog_type,
+                  const struct bpf_insn *insns, int prog_len,
+                  const char *license)
+{
+        union bpf_attr attr = {
+                .prog_type = prog_type,
+                .insns = ptr_to_u64((void *) insns),
+                .insn_cnt = prog_len / sizeof(struct bpf_insn),
+                .license = ptr_to_u64((void *) license),
+                .log_buf = ptr_to_u64(bpf_log_buf),
+                .log_size = LOG_BUF_SIZE,
+                .log_level = 1,
+        };
+
+        bpf_log_buf[0] = 0;
+
+        return syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+}
diff --git a/samples/bpf/libbpf.h b/samples/bpf/libbpf.h
new file mode 100644
index 000000000000..8a31babeca5d
--- /dev/null
+++ b/samples/bpf/libbpf.h
@@ -0,0 +1,172 @@
+/* eBPF mini library */
+#ifndef __LIBBPF_H
+#define __LIBBPF_H
+
+struct bpf_insn;
+
+int bpf_create_map(enum bpf_map_type map_type, int key_size, int value_size,
+                   int max_entries);
+int bpf_update_elem(int fd, void *key, void *value);
+int bpf_lookup_elem(int fd, void *key, void *value);
+int bpf_delete_elem(int fd, void *key);
+int bpf_get_next_key(int fd, void *key, void *next_key);
+
+int bpf_prog_load(enum bpf_prog_type prog_type,
+                  const struct bpf_insn *insns, int insn_len,
+                  const char *license);
+
+#define LOG_BUF_SIZE 8192
+extern char bpf_log_buf[LOG_BUF_SIZE];
+
+/* ALU ops on registers, bpf_add|sub|...: dst_reg += src_reg */
+
+#define BPF_ALU64_REG(OP, DST, SRC)                             \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_ALU64 | BPF_OP(OP) | BPF_X,        \
+                .dst_reg = DST,                                 \
+                .src_reg = SRC,                                 \
+                .off   = 0,                                     \
+                .imm   = 0 })
+
+#define BPF_ALU32_REG(OP, DST, SRC)                             \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_ALU | BPF_OP(OP) | BPF_X,          \
+                .dst_reg = DST,                                 \
+                .src_reg = SRC,                                 \
+                .off   = 0,                                     \
+                .imm   = 0 })
+
+/* ALU ops on immediates, bpf_add|sub|...: dst_reg += imm32 */
+
+#define BPF_ALU64_IMM(OP, DST, IMM)                             \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_ALU64 | BPF_OP(OP) | BPF_K,        \
+                .dst_reg = DST,                                 \
+                .src_reg = 0,                                   \
+                .off   = 0,                                     \
+                .imm   = IMM })
+
+#define BPF_ALU32_IMM(OP, DST, IMM)                             \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_ALU | BPF_OP(OP) | BPF_K,          \
+                .dst_reg = DST,                                 \
+                .src_reg = 0,                                   \
+                .off   = 0,                                     \
+                .imm   = IMM })
+
+/* Short form of mov, dst_reg = src_reg */
+
+#define BPF_MOV64_REG(DST, SRC)                                 \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_ALU64 | BPF_MOV | BPF_X,           \
+                .dst_reg = DST,                                 \
+                .src_reg = SRC,                                 \
+                .off   = 0,                                     \
+                .imm   = 0 })
+
+/* Short form of mov, dst_reg = imm32 */
+
+#define BPF_MOV64_IMM(DST, IMM)                                 \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_ALU64 | BPF_MOV | BPF_K,           \
+                .dst_reg = DST,                                 \
+                .src_reg = 0,                                   \
+                .off   = 0,                                     \
+                .imm   = IMM })
+
+/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */
+#define BPF_LD_IMM64(DST, IMM)                                  \
+        BPF_LD_IMM64_RAW(DST, 0, IMM)
+
+#define BPF_LD_IMM64_RAW(DST, SRC, IMM)                         \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_LD | BPF_DW | BPF_IMM,             \
+                .dst_reg = DST,                                 \
+                .src_reg = SRC,                                 \
+                .off   = 0,                                     \
+                .imm   = (__u32) (IMM) }),                      \
+        ((struct bpf_insn) {                                    \
+                .code  = 0, /* zero is reserved opcode */       \
+                .dst_reg = 0,                                   \
+                .src_reg = 0,                                   \
+                .off   = 0,                                     \
+                .imm   = ((__u64) (IMM)) >> 32 })
+
+#define BPF_PSEUDO_MAP_FD       1
+
+/* pseudo BPF_LD_IMM6