From 4cd3675ebf74d7f559038ded6aa8088e4099a83d Mon Sep 17 00:00:00 2001 From: Chema Gonzalez Date: Mon, 21 Apr 2014 09:21:24 -0700 Subject: filter: added BPF random opcode Added a new ancillary load (bpf call in eBPF parlance) that produces a 32-bit random number. We are implementing it as an ancillary load (instead of an ISA opcode) because (a) it is simpler, (b) allows easy JITing, and (c) seems more in line with generic ISAs that do not have "get a random number" as a instruction, but as an OS call. The main use for this ancillary load is to perform random packet sampling. Signed-off-by: Chema Gonzalez Acked-by: Alexei Starovoitov Acked-by: Daniel Borkmann Signed-off-by: David S. Miller --- tools/net/bpf_exp.l | 1 + tools/net/bpf_exp.y | 11 ++++++++++- 2 files changed, 11 insertions(+), 1 deletion(-) (limited to 'tools') diff --git a/tools/net/bpf_exp.l b/tools/net/bpf_exp.l index bf7be77ddd62..833a96611da6 100644 --- a/tools/net/bpf_exp.l +++ b/tools/net/bpf_exp.l @@ -92,6 +92,7 @@ extern void yyerror(const char *str); "#"?("cpu") { return K_CPU; } "#"?("vlan_tci") { return K_VLANT; } "#"?("vlan_pr") { return K_VLANP; } +"#"?("rand") { return K_RAND; } ":" { return ':'; } "," { return ','; } diff --git a/tools/net/bpf_exp.y b/tools/net/bpf_exp.y index d15efc989ef5..e6306c51c26f 100644 --- a/tools/net/bpf_exp.y +++ b/tools/net/bpf_exp.y @@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type); %token OP_LDXI %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE -%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF +%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%' @@ -164,6 +164,9 @@ ldb | OP_LDB K_POFF { bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0, SKF_AD_OFF + SKF_AD_PAY_OFFSET); } + | OP_LDB K_RAND { + bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0, + SKF_AD_OFF + SKF_AD_RANDOM); } ; ldh @@ -212,6 +215,9 @@ ldh | OP_LDH K_POFF { bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0, SKF_AD_OFF + SKF_AD_PAY_OFFSET); } + | OP_LDH K_RAND { + bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0, + SKF_AD_OFF + SKF_AD_RANDOM); } ; ldi @@ -265,6 +271,9 @@ ld | OP_LD K_POFF { bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0, SKF_AD_OFF + SKF_AD_PAY_OFFSET); } + | OP_LD K_RAND { + bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0, + SKF_AD_OFF + SKF_AD_RANDOM); } | OP_LD 'M' '[' number ']' { bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); } | OP_LD '[' 'x' '+' number ']' { -- cgit v1.2.3 From 64a8946b447e418b4283c3573ef397980cca0cd8 Mon Sep 17 00:00:00 2001 From: Alexei Starovoitov Date: Thu, 8 May 2014 14:10:52 -0700 Subject: net: filter: BPF testsuite The testsuite covers classic and internal BPF instructions. It is particularly useful for JIT compiler developers. Adds to "net" selftest target. The testsuite can be used as a set of micro-benchmarks. It measures execution time of each BPF program in nsec. This patch adds core framework. Signed-off-by: Alexei Starovoitov Signed-off-by: David S. Miller --- lib/Kconfig.debug | 13 ++ lib/Makefile | 1 + lib/test_bpf.c | 322 +++++++++++++++++++++++++++++++++++ tools/testing/selftests/net/Makefile | 8 +- 4 files changed, 343 insertions(+), 1 deletion(-) create mode 100644 lib/test_bpf.c (limited to 'tools') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 819ac51202c0..423ca319a5f8 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1620,6 +1620,19 @@ config TEST_USER_COPY If unsure, say N. +config TEST_BPF + tristate "Test BPF filter functionality" + default n + depends on m + help + This builds the "test_bpf" module that runs various test vectors + 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. + + If unsure, say N. + source "samples/Kconfig" source "lib/Kconfig.kgdb" diff --git a/lib/Makefile b/lib/Makefile index 0cd7b68e1382..b2be1ef1e8ec 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -33,6 +33,7 @@ obj-y += kstrtox.o obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o obj-$(CONFIG_TEST_MODULE) += test_module.o obj-$(CONFIG_TEST_USER_COPY) += test_user_copy.o +obj-$(CONFIG_TEST_BPF) += test_bpf.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG diff --git a/lib/test_bpf.c b/lib/test_bpf.c new file mode 100644 index 000000000000..9f25dc127330 --- /dev/null +++ b/lib/test_bpf.c @@ -0,0 +1,322 @@ +/* + * Testsuite for BPF interpreter and BPF JIT compiler + * + * Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt + +#include +#include +#include +#include +#include +#include + +#define MAX_SUBTESTS 3 +#define MAX_DATA 128 +#define MAX_INSNS 512 +#define MAX_K 0xffffFFFF + +/* define few constants used to init test 'skb' */ +#define SKB_TYPE 3 +#define SKB_MARK 0x1234aaaa +#define SKB_HASH 0x1234aaab +#define SKB_QUEUE_MAP 123 +#define SKB_VLAN_TCI 0xffff +#define SKB_DEV_IFINDEX 577 +#define SKB_DEV_TYPE 588 + +/* redefine REGs to make tests less verbose */ +#define R0 BPF_REG_0 +#define R1 BPF_REG_1 +#define R2 BPF_REG_2 +#define R3 BPF_REG_3 +#define R4 BPF_REG_4 +#define R5 BPF_REG_5 +#define R6 BPF_REG_6 +#define R7 BPF_REG_7 +#define R8 BPF_REG_8 +#define R9 BPF_REG_9 +#define R10 BPF_REG_10 + +struct bpf_test { + const char *descr; + union { + struct sock_filter insns[MAX_INSNS]; + struct sock_filter_int insns_int[MAX_INSNS]; + }; + enum { + NO_DATA, + EXPECTED_FAIL, + SKB, + SKB_INT + } data_type; + __u8 data[MAX_DATA]; + struct { + int data_size; + __u32 result; + } test[MAX_SUBTESTS]; +}; + +static struct bpf_test tests[] = { + { + "TAX", + .insns = { + BPF_STMT(BPF_LD | BPF_IMM, 1), + BPF_STMT(BPF_MISC | BPF_TAX, 0), + BPF_STMT(BPF_LD | BPF_IMM, 2), + BPF_STMT(BPF_ALU | BPF_ADD | BPF_X, 0), + BPF_STMT(BPF_ALU | BPF_NEG, 0), /* A == -3 */ + BPF_STMT(BPF_MISC | BPF_TAX, 0), + BPF_STMT(BPF_LD | BPF_LEN, 0), + BPF_STMT(BPF_ALU | BPF_ADD | BPF_X, 0), + BPF_STMT(BPF_MISC | BPF_TAX, 0), /* X == len - 3 */ + BPF_STMT(BPF_LD | BPF_B | BPF_IND, 1), + BPF_STMT(BPF_RET | BPF_A, 0) + }, + SKB, + { 10, 20, 30, 40, 50 }, + { { 2, 10 }, { 3, 20 }, { 4, 30 } }, + }, + { + "tcpdump port 22", + .insns = { + { 0x28, 0, 0, 0x0000000c }, + { 0x15, 0, 8, 0x000086dd }, + { 0x30, 0, 0, 0x00000014 }, + { 0x15, 2, 0, 0x00000084 }, + { 0x15, 1, 0, 0x00000006 }, + { 0x15, 0, 17, 0x00000011 }, + { 0x28, 0, 0, 0x00000036 }, + { 0x15, 14, 0, 0x00000016 }, + { 0x28, 0, 0, 0x00000038 }, + { 0x15, 12, 13, 0x00000016 }, + { 0x15, 0, 12, 0x00000800 }, + { 0x30, 0, 0, 0x00000017 }, + { 0x15, 2, 0, 0x00000084 }, + { 0x15, 1, 0, 0x00000006 }, + { 0x15, 0, 8, 0x00000011 }, + { 0x28, 0, 0, 0x00000014 }, + { 0x45, 6, 0, 0x00001fff }, + { 0xb1, 0, 0, 0x0000000e }, + { 0x48, 0, 0, 0x0000000e }, + { 0x15, 2, 0, 0x00000016 }, + { 0x48, 0, 0, 0x00000010 }, + { 0x15, 0, 1, 0x00000016 }, + { 0x06, 0, 0, 0x0000ffff }, + { 0x06, 0, 0, 0x00000000 }, + }, + SKB, + /* 3c:07:54:43:e5:76 > 10:bf:48:d6:43:d6, ethertype IPv4(0x0800) + * length 114: 10.1.1.149.49700 > 10.1.2.10.22: Flags [P.], + * seq 1305692979:1305693027, ack 3650467037, win 65535, + * options [nop,nop,TS val 2502645400 ecr 3971138], length 48 + */ + { 0x10, 0xbf, 0x48, 0xd6, 0x43, 0xd6, + 0x3c, 0x07, 0x54, 0x43, 0xe5, 0x76, + 0x08, 0x00, + 0x45, 0x10, 0x00, 0x64, 0x75, 0xb5, + 0x40, 0x00, 0x40, 0x06, 0xad, 0x2e, /* IP header */ + 0x0a, 0x01, 0x01, 0x95, /* ip src */ + 0x0a, 0x01, 0x02, 0x0a, /* ip dst */ + 0xc2, 0x24, + 0x00, 0x16 /* dst port */ }, + { { 10, 0 }, { 30, 0 }, { 100, 65535 } }, + }, + { + "INT: DIV + ABS", + .insns_int = { + BPF_ALU64_REG(BPF_MOV, R6, R1), + BPF_LD_ABS(BPF_B, 3), + BPF_ALU64_IMM(BPF_MOV, R2, 2), + BPF_ALU32_REG(BPF_DIV, R0, R2), + BPF_ALU64_REG(BPF_MOV, R8, R0), + BPF_LD_ABS(BPF_B, 4), + BPF_ALU64_REG(BPF_ADD, R8, R0), + BPF_LD_IND(BPF_B, R8, -70), + BPF_EXIT_INSN(), + }, + SKB_INT, + { 10, 20, 30, 40, 50 }, + { { 4, 0 }, { 5, 10 } } + }, + { + "check: missing ret", + .insns = { + BPF_STMT(BPF_LD | BPF_IMM, 1), + }, + EXPECTED_FAIL, + { }, + { } + }, +}; + +static int get_length(struct sock_filter *fp) +{ + int len = 0; + + while (fp->code != 0 || fp->k != 0) { + fp++; + len++; + } + + return len; +} + +struct net_device dev; +struct sk_buff *populate_skb(char *buf, int size) +{ + struct sk_buff *skb; + + if (size >= MAX_DATA) + return NULL; + + skb = alloc_skb(MAX_DATA, GFP_KERNEL); + if (!skb) + return NULL; + + memcpy(__skb_put(skb, size), buf, size); + skb_reset_mac_header(skb); + skb->protocol = htons(ETH_P_IP); + skb->pkt_type = SKB_TYPE; + skb->mark = SKB_MARK; + skb->hash = SKB_HASH; + skb->queue_mapping = SKB_QUEUE_MAP; + skb->vlan_tci = SKB_VLAN_TCI; + skb->dev = &dev; + skb->dev->ifindex = SKB_DEV_IFINDEX; + skb->dev->type = SKB_DEV_TYPE; + skb_set_network_header(skb, min(size, ETH_HLEN)); + + return skb; +} + +static int run_one(struct sk_filter *fp, struct bpf_test *t) +{ + u64 start, finish, res, cnt = 100000; + int err_cnt = 0, err, i, j; + u32 ret = 0; + void *data; + + for (i = 0; i < MAX_SUBTESTS; i++) { + if (t->test[i].data_size == 0 && + t->test[i].result == 0) + break; + if (t->data_type == SKB || + t->data_type == SKB_INT) { + data = populate_skb(t->data, t->test[i].data_size); + if (!data) + return -ENOMEM; + } else { + data = NULL; + } + + start = ktime_to_us(ktime_get()); + for (j = 0; j < cnt; j++) + ret = SK_RUN_FILTER(fp, data); + finish = ktime_to_us(ktime_get()); + + res = (finish - start) * 1000; + do_div(res, cnt); + + err = ret != t->test[i].result; + if (!err) + pr_cont("%lld ", res); + + if (t->data_type == SKB || t->data_type == SKB_INT) + kfree_skb(data); + + if (err) { + pr_cont("ret %d != %d ", ret, t->test[i].result); + err_cnt++; + } + } + + return err_cnt; +} + +static __init int test_bpf(void) +{ + struct sk_filter *fp, *fp_ext = NULL; + struct sock_fprog fprog; + int err, i, err_cnt = 0; + + for (i = 0; i < ARRAY_SIZE(tests); i++) { + pr_info("#%d %s ", i, tests[i].descr); + + fprog.filter = tests[i].insns; + fprog.len = get_length(fprog.filter); + + if (tests[i].data_type == SKB_INT) { + fp_ext = kzalloc(4096, GFP_KERNEL); + if (!fp_ext) + return -ENOMEM; + fp = fp_ext; + memcpy(fp_ext->insns, tests[i].insns_int, + fprog.len * 8); + fp->len = fprog.len; + fp->bpf_func = sk_run_filter_int_skb; + } else { + err = sk_unattached_filter_create(&fp, &fprog); + if (tests[i].data_type == EXPECTED_FAIL) { + if (err == -EINVAL) { + pr_cont("PASS\n"); + continue; + } else { + pr_cont("UNEXPECTED_PASS\n"); + /* verifier didn't reject the test + * that's bad enough, just return + */ + return -EINVAL; + } + } + if (err) { + pr_cont("FAIL to attach err=%d len=%d\n", + err, fprog.len); + return err; + } + } + + err = run_one(fp, &tests[i]); + + if (tests[i].data_type != SKB_INT) + sk_unattached_filter_destroy(fp); + else + kfree(fp); + + if (err) { + pr_cont("FAIL %d\n", err); + err_cnt++; + } else { + pr_cont("PASS\n"); + } + } + + if (err_cnt) + return -EINVAL; + else + return 0; +} + +static int __init test_bpf_init(void) +{ + return test_bpf(); +} + +static void __exit test_bpf_exit(void) +{ +} + +module_init(test_bpf_init); +module_exit(test_bpf_exit); +MODULE_LICENSE("GPL"); diff --git a/tools/testing/selftests/net/Makefile b/tools/testing/selftests/net/Makefile index 750512ba2c88..c7493b8f9b0e 100644 --- a/tools/testing/selftests/net/Makefile +++ b/tools/testing/selftests/net/Makefile @@ -14,6 +14,12 @@ all: $(NET_PROGS) run_tests: all @/bin/sh ./run_netsocktests || echo "sockettests: [FAIL]" @/bin/sh ./run_afpackettests || echo "afpackettests: [FAIL]" - + @if /sbin/modprobe test_bpf ; then \ + /sbin/rmmod test_bpf; \ + echo "test_bpf: ok"; \ + else \ + echo "test_bpf: [FAIL]"; \ + exit 1; \ + fi clean: $(RM) $(NET_PROGS) -- cgit v1.2.3 From ed4afd451f12ea57f9aaaf6f8442eee7e415fa1a Mon Sep 17 00:00:00 2001 From: Alexei Starovoitov Date: Thu, 15 May 2014 15:56:38 -0700 Subject: tools: bpf_jit_disasm: ignore image address for disasm seccomp filters use kernel JIT image addresses, so bpf_jit_enable=2 prints [ 20.146438] flen=3 proglen=82 pass=0 image=0000000000000000 [ 20.146442] JIT code: 00000000: 55 48 89 e5 48 81 ec 28 02 00 00 ... ignore image address, so that seccomp filters can be disassembled Signed-off-by: Alexei Starovoitov Acked-by: Daniel Borkmann Signed-off-by: David S. Miller --- tools/net/bpf_jit_disasm.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) (limited to 'tools') diff --git a/tools/net/bpf_jit_disasm.c b/tools/net/bpf_jit_disasm.c index cfe0cdcda3de..d9730c3319b9 100644 --- a/tools/net/bpf_jit_disasm.c +++ b/tools/net/bpf_jit_disasm.c @@ -43,8 +43,7 @@ static void get_exec_path(char *tpath, size_t size) free(path); } -static void get_asm_insns(uint8_t *image, size_t len, unsigned long base, - int opcodes) +static void get_asm_insns(uint8_t *image, size_t len, int opcodes) { int count, i, pc = 0; char tpath[256]; @@ -107,13 +106,13 @@ static void put_klog_buff(char *buff) } static int get_last_jit_image(char *haystack, size_t hlen, - uint8_t *image, size_t ilen, - unsigned long *base) + uint8_t *image, size_t ilen) { char *ptr, *pptr, *tmp; off_t off = 0; int ret, flen, proglen, pass, ulen = 0; regmatch_t pmatch[1]; + unsigned long base; regex_t regex; if (hlen == 0) @@ -136,7 +135,7 @@ static int get_last_jit_image(char *haystack, size_t hlen, ptr = haystack + off - (pmatch[0].rm_eo - pmatch[0].rm_so); ret = sscanf(ptr, "flen=%d proglen=%d pass=%d image=%lx", - &flen, &proglen, &pass, base); + &flen, &proglen, &pass, &base); if (ret != 4) return 0; @@ -162,7 +161,7 @@ static int get_last_jit_image(char *haystack, size_t hlen, assert(ulen == proglen); printf("%d bytes emitted from JIT compiler (pass:%d, flen:%d)\n", proglen, pass, flen); - printf("%lx + :\n", *base); + printf("%lx + :\n", base); regfree(®ex); return ulen; @@ -172,7 +171,6 @@ int main(int argc, char **argv) { int len, klen, opcodes = 0; char *kbuff; - unsigned long base; uint8_t image[4096]; if (argc > 1) { @@ -189,9 +187,9 @@ int main(int argc, char **argv) kbuff = get_klog_buff(&klen); - len = get_last_jit_image(kbuff, klen, image, sizeof(image), &base); - if (len > 0 && base > 0) - get_asm_insns(image, len, base, opcodes); + len = get_last_jit_image(kbuff, klen, image, sizeof(image)); + if (len > 0) + get_asm_insns(image, len, opcodes); put_klog_buff(kbuff); -- cgit v1.2.3 From 9bb1a208fddda94ea3c6df1fc9a225f92761cf1c Mon Sep 17 00:00:00 2001 From: Alexei Starovoitov Date: Thu, 15 May 2014 15:56:39 -0700 Subject: tools: bpf_jit_disasm: increase image buffer size JITed seccomp filters can be quite large if they check a lot of syscalls Simply increase buffer size Signed-off-by: Alexei Starovoitov Acked-by: Daniel Borkmann Signed-off-by: David S. Miller --- tools/net/bpf_jit_disasm.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'tools') diff --git a/tools/net/bpf_jit_disasm.c b/tools/net/bpf_jit_disasm.c index d9730c3319b9..c5baf9c591b7 100644 --- a/tools/net/bpf_jit_disasm.c +++ b/tools/net/bpf_jit_disasm.c @@ -171,7 +171,7 @@ int main(int argc, char **argv) { int len, klen, opcodes = 0; char *kbuff; - uint8_t image[4096]; + static uint8_t image[32768]; if (argc > 1) { if (!strncmp("-o", argv[argc - 1], 2)) { -- cgit v1.2.3