bpf: increase jmp sequence limit
Subsystems (6)
Alexei Starovoitov
maintainerv2 cover bpf: increase jmp sequence limit
Patch 1 - jmp sequence limit
Patch 2 - improve existing tests
Patch 3 - add pyperf-based realistic bpf program that takes advantage of higher limit and use it as a stress test
v1->v2: fixed nit in patch 3. added Andrii's acks
Alexei Starovoitov (3):
bpf: bump jmp sequence limit
selftests/bpf: adjust verifier scale test
selftests/bpf: add pyperf scale test
kernel/bpf/verifier.c | 7 +- .../bpf/prog_tests/bpf_verif_scale.c | 31 +- tools/testing/selftests/bpf/progs/pyperf.h | 268 ++++++++++++++++++ tools/testing/selftests/bpf/progs/pyperf100.c | 4 + tools/testing/selftests/bpf/progs/pyperf180.c | 4 + tools/testing/selftests/bpf/progs/pyperf50.c | 4 + tools/testing/selftests/bpf/test_verifier.c | 31 +- 7 files changed, 319 insertions(+), 30 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf.h create mode 100644 tools/testing/selftests/bpf/progs/pyperf100.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf180.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf50.c
Signature · 1 line
2.20.0
Alexei Starovoitov
maintainerPATCH v2 1/3 bpf: bump jmp sequence limit
The limit of 1024 subsequent jumps was causing otherwise valid programs to be rejected. Bump it to 8192 and make the error more verbose.
--- kernel/bpf/verifier.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +4 -3
@@ -176,7 +176,7 @@ struct bpf_verifier_stack_elem {struct bpf_verifier_stack_elem *next; }; -#define BPF_COMPLEXITY_LIMIT_STACK 1024 +#define BPF_COMPLEXITY_LIMIT_JMP_SEQ 8192#define BPF_COMPLEXITY_LIMIT_STATES 64#define BPF_MAP_PTR_UNPRIV 1UL
@@ -782,8 +782,9 @@ static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env,if (err) goto err; elem->st.speculative |= speculative; -if (env->stack_size >BPF_COMPLEXITY_LIMIT_STACK ) { -verbose (env,"BPF program is too complex\n" ); +if (env->stack_size >BPF_COMPLEXITY_LIMIT_JMP_SEQ ) { +verbose (env,"The sequence of %d jumps is too complex.\n" , + env->stack_size); goto err; }return &elem->st;
Signature · 1 line
2.20.0
Alexei Starovoitov
maintainerPATCH v2 2/3 selftests/bpf: adjust verifier scale test
In reply to Alexei StarovoitovAdjust scale tests to check for new jmp sequence limit.
BPF_JGT had to be changed to BPF_JEQ because the verifier was too smart. It tracked the known safe range of R0 values and pruned the search earlier before hitting exact 8192 limit. bpf_semi_rand_get() was too (un)?lucky.
k = 0; was missing in bpf_fill_scale2.
It was testing a bit shorter sequence of jumps than intended.
--- tools/testing/selftests/bpf/test_verifier.c | 31 +++++++++++---------- 1 file changed, 17 insertions(+), 14 deletions(-)
tools/testing/selftests/bpf/test_verifier.c +17 -14
@@ -210,33 +210,35 @@ static void bpf_fill_rand_ld_dw(struct bpf_test *self) self->retval = (uint32_t )res; } -/* test the sequence of 1k jumps */ +#define MAX_JMP_SEQ 8192 + +/* test the sequence of 8k jumps */ static void bpf_fill_scale1 (struct bpf_test *self) {struct bpf_insn *insn = self->fill_insns;int i =0 , k =0 ; insn[i++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); -/* test to check that the sequence of 1024 jumps is acceptable */ -while (k++ <1024 ) { +/* test to check that the long sequence of jumps is acceptable */ +while (k++ <MAX_JMP_SEQ ) { insn[i++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_get_prandom_u32); - insn[i++] =BPF_JMP_IMM (BPF_JGT ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); + insn[i++] =BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); insn[i++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ); insn[i++] =BPF_STX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_6 ,-8 * (k %64 +1 )); } -/* every jump adds 1024 steps to insn_processed, so to stay exactly -* within 1m limit add MAX_TEST_INSNS - 1025 MOVs and 1 EXIT +/* every jump adds 1 step to insn_processed, so to stay exactly +* within 1m limit add MAX_TEST_INSNS - MAX_JMP_SEQ - 1 MOVs and 1 EXIT */ -while (i <MAX_TEST_INSNS -1025 ) +while (i <MAX_TEST_INSNS -MAX_JMP_SEQ -1 ) insn[i++] =BPF_ALU32_IMM (BPF_MOV ,BPF_REG_0 ,42 ); insn[i] =BPF_EXIT_INSN (); self->prog_len = i +1 ; self->retval =42 ; } -/* test the sequence of 1k jumps in inner most function (function depth 8)*/ +/* test the sequence of 8k jumps in inner most function (function depth 8)*/ static void bpf_fill_scale2 (struct bpf_test *self) {struct bpf_insn *insn = self->fill_insns;
@@ -248,19 +250,20 @@ static void bpf_fill_scale2(struct bpf_test *self) insn[i++] =BPF_EXIT_INSN (); } insn[i++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); -/* test to check that the sequence of 1024 jumps is acceptable */ -while (k++ <1024 ) { +/* test to check that the long sequence of jumps is acceptable */ + k =0 ; +while (k++ <MAX_JMP_SEQ ) { insn[i++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_get_prandom_u32); - insn[i++] =BPF_JMP_IMM (BPF_JGT ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); + insn[i++] =BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); insn[i++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ); insn[i++] =BPF_STX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_6 ,-8 * (k % (64 -4 *FUNC_NEST ) +1 )); } -/* every jump adds 1024 steps to insn_processed, so to stay exactly -* within 1m limit add MAX_TEST_INSNS - 1025 MOVs and 1 EXIT +/* every jump adds 1 step to insn_processed, so to stay exactly +* within 1m limit add MAX_TEST_INSNS - MAX_JMP_SEQ - 1 MOVs and 1 EXIT */ -while (i <MAX_TEST_INSNS -1025 ) +while (i <MAX_TEST_INSNS -MAX_JMP_SEQ -1 ) insn[i++] =BPF_ALU32_IMM (BPF_MOV ,BPF_REG_0 ,42 ); insn[i] =BPF_EXIT_INSN (); self->prog_len = i +1 ;
Signature · 1 line
2.20.0
Alexei Starovoitov
maintainerPATCH v2 3/3 selftests/bpf: add pyperf scale test
In reply to Alexei StarovoitovAdd a snippet of pyperf bpf program used to collect python stack traces as a scale test for the verifier.
At 189 loop iterations llvm 9.0 starts ignoring '#pragma unroll' and generates partially unrolled loop instead.
Hence use 50, 100, and 180 loop iterations to stress test.
--- .../bpf/prog_tests/bpf_verif_scale.c | 31 +- tools/testing/selftests/bpf/progs/pyperf.h | 268 ++++++++++++++++++ tools/testing/selftests/bpf/progs/pyperf100.c | 4 + tools/testing/selftests/bpf/progs/pyperf180.c | 4 + tools/testing/selftests/bpf/progs/pyperf50.c | 4 + 5 files changed, 298 insertions(+), 13 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf.h create mode 100644 tools/testing/selftests/bpf/progs/pyperf100.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf180.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf50.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +18 -13
@@ -12,7 +12,7 @@ static int libbpf_debug_print(enum libbpf_print_level level,return vfprintf (stderr,"%s" , args); } -static int check_load (const char *file) +static int check_load (const char *file,enum bpf_prog_type type) {struct bpf_prog_load_attr attr;struct bpf_object *obj =NULL ;
@@ -20,7 +20,7 @@ static int check_load(const char *file)memset (&attr,0 ,sizeof (struct bpf_prog_load_attr )); attr.file = file; - attr.prog_type =BPF_PROG_TYPE_SCHED_CLS ; + attr.prog_type = type; attr.log_level =4 ; err =bpf_prog_load_xattr (&attr, &obj, &prog_fd);bpf_object__close (obj);
@@ -31,19 +31,24 @@ static int check_load(const char *file)void test_bpf_verif_scale (void ) { -const char *file1 ="./test_verif_scale1.o" ; -const char *file2 ="./test_verif_scale2.o" ; -const char *file3 ="./test_verif_scale3.o" ; -int err; +const char *scale[] = { +"./test_verif_scale1.o" ,"./test_verif_scale2.o" ,"./test_verif_scale3.o" + }; +const char *pyperf[] = { +"./pyperf50.o" ,"./pyperf100.o" ,"./pyperf180.o" + }; +int err, i;if (verifier_stats)libbpf_set_print (libbpf_debug_print); - err =check_load (file1); - err |=check_load (file2); - err |=check_load (file3); -if (!err) -printf ("test_verif_scale:OK\n" ); -else -printf ("test_verif_scale:FAIL\n" ); +for (i =0 ; i <ARRAY_SIZE (scale); i++) { + err =check_load (scale[i],BPF_PROG_TYPE_SCHED_CLS ); +printf ("test_scale:%s:%s\n" , scale[i], err ?"FAIL" :"OK" ); + } + +for (i =0 ; i <ARRAY_SIZE (pyperf); i++) { + err =check_load (pyperf[i],BPF_PROG_TYPE_RAW_TRACEPOINT ); +printf ("test_scale:%s:%s\n" , pyperf[i], err ?"FAIL" :"OK" ); + } }
tools/testing/selftests/bpf/progs/pyperf.h new file +268 -0
268 lines not on this page · raw message
tools/testing/selftests/bpf/progs/pyperf100.c new file +4 -0
@@ -0,0 +1,4 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2019 Facebook +#define STACK_MAX_LEN 100 +#include "pyperf.h"
tools/testing/selftests/bpf/progs/pyperf180.c new file +4 -0
@@ -0,0 +1,4 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2019 Facebook +#define STACK_MAX_LEN 180 +#include "pyperf.h"
tools/testing/selftests/bpf/progs/pyperf50.c new file +4 -0
@@ -0,0 +1,4 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2019 Facebook +#define STACK_MAX_LEN 50 +#include "pyperf.h"
Signature · 1 line
2.20.0
Daniel Borkmann
maintainerQuoted 12 lines · Alexei Starovoitov
Patch 1 - jmp sequence limit
Patch 2 - improve existing tests
Patch 3 - add pyperf-based realistic bpf program that takes advantage of higher limit and use it as a stress test
v1->v2: fixed nit in patch 3. added Andrii's acksAlexei Starovoitov (3):
bpf: bump jmp sequence limit
selftests/bpf: adjust verifier scale test
selftests/bpf: add pyperf scale test
Quoted 13 lines
kernel/bpf/verifier.c | 7 +- .../bpf/prog_tests/bpf_verif_scale.c | 31 +- tools/testing/selftests/bpf/progs/pyperf.h | 268 ++++++++++++++++++ tools/testing/selftests/bpf/progs/pyperf100.c | 4 + tools/testing/selftests/bpf/progs/pyperf180.c | 4 + tools/testing/selftests/bpf/progs/pyperf50.c | 4 + tools/testing/selftests/bpf/test_verifier.c | 31 +- 7 files changed, 319 insertions(+), 30 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf.h create mode 100644 tools/testing/selftests/bpf/progs/pyperf100.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf180.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf50.c
Looks good, applied, thanks!