Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1676686
| From | Daniel Borkmann <daniel@iogearbox.net> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier |
| Date | 2017-06-28 16:00 +0200 |
| Message-ID | <tXlFF-7uy-33@gated-at.bofh.it> (permalink) |
| References | <tWYg2-C4-5@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
Hi Edward, On 06/27/2017 02:53 PM, Edward Cree wrote: > This series simplifies alignment tracking, generalises bounds tracking and > fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on > packet pointers, stack pointers, map value pointers and context pointers has > been unified, and bounds on these pointers are only checked when the pointer > is dereferenced. > Operations on pointers which destroy all relation to the original pointer > (such as multiplies and shifts) are disallowed if !env->allow_ptr_leaks, > otherwise they convert the pointer to an unknown scalar and feed it to the > normal scalar arithmetic handling. > Pointer types have been unified with the corresponding adjusted-pointer types > where those existed (e.g. PTR_TO_MAP_VALUE[_ADJ] or FRAME_PTR vs > PTR_TO_STACK); similarly, CONST_IMM and UNKNOWN_VALUE have been unified into > SCALAR_VALUE. > Pointer types (except CONST_PTR_TO_MAP, PTR_TO_MAP_VALUE_OR_NULL and > PTR_TO_PACKET_END, which do not allow arithmetic) have a 'fixed offset' and > a 'variable offset'; the former is used when e.g. adding an immediate or a > known-constant register, as long as it does not overflow. Otherwise the > latter is used, and any operation creating a new variable offset creates a > new 'id' (and, for PTR_TO_PACKET, clears the 'range'). > SCALAR_VALUEs use the 'variable offset' fields to track the range of possible > values; the 'fixed offset' should never be set on a scalar. > > As of patch 12/12, all tests of tools/testing/selftests/bpf/test_verifier > and tools/testing/selftests/bpf/test_align pass. > > v3: added a few more tests; removed RFC tags. Did you also have a chance in the meantime to look at reducing complexity along with your unification? I did run the cilium test suite with your latest set from here and current # worst case processed insns that verifier has to go through for cilium progs increases from ~53k we have right now to ~76k. I'm a bit worried that this quickly gets us close to the upper ~98k max limit starting to reject programs again. Alternative is to bump the complexity limit again in near future once run into it, but preferably there's a way to optimize it along with the rewrite? Do you see any possibilities worth exploring? > v2: fixed nfp build, made test_align pass again and extended it with a few > new tests (though still need to add more). > > Edward Cree (12): > selftests/bpf: add test for mixed signed and unsigned bounds checks > bpf/verifier: rework value tracking > nfp: change bpf verifier hooks to match new verifier data structures > bpf/verifier: track signed and unsigned min/max values > bpf/verifier: more concise register state logs for constant var_off > selftests/bpf: change test_verifier expectations > selftests/bpf: rewrite test_align > selftests/bpf: add a test to test_align > selftests/bpf: add test for bogus operations on pointers > selftests/bpf: don't try to access past MAX_PACKET_OFF in > test_verifier > selftests/bpf: add tests for subtraction & negative numbers > selftests/bpf: variable offset negative tests > > drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +- > include/linux/bpf.h | 34 +- > include/linux/bpf_verifier.h | 56 +- > include/linux/tnum.h | 81 + > kernel/bpf/Makefile | 2 +- > kernel/bpf/tnum.c | 180 ++ > kernel/bpf/verifier.c | 1943 ++++++++++++--------- > tools/testing/selftests/bpf/test_align.c | 462 ++++- > tools/testing/selftests/bpf/test_verifier.c | 293 ++-- > 9 files changed, 2034 insertions(+), 1041 deletions(-) > create mode 100644 include/linux/tnum.h > create mode 100644 kernel/bpf/tnum.c > Thanks, Daniel
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
[PATCH v3 net-next 06/12] selftests/bpf: change test_verifier expectations Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
[PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
Re: [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 22:50 +0200
Re: [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures Jakub Kicinski <jakub.kicinski@netronome.com> - 2017-06-29 05:50 +0200
[PATCH v3 net-next 01/12] selftests/bpf: add test for mixed signed and unsigned bounds checks Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
Re: [PATCH v3 net-next 01/12] selftests/bpf: add test for mixed signed and unsigned bounds checks Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 16:00 +0200
[PATCH v3 net-next 07/12] selftests/bpf: rewrite test_align Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
[PATCH v3 net-next 09/12] selftests/bpf: add test for bogus operations on pointers Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 12/12] selftests/bpf: variable offset negative tests Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 08/12] selftests/bpf: add a test to test_align Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 10/12] selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 11/12] selftests/bpf: add tests for subtraction & negative numbers Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 16:00 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-06-28 16:20 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 22:50 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2017-06-28 23:40 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-06-30 18:50 +0200
[TEST PATCH] bpf/verifier: roll back ptr&const handling, and fix signed bounds Edward Cree <ecree@solarflare.com> - 2017-06-30 19:40 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 17:20 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Edward Cree <ecree@solarflare.com> - 2017-06-28 18:10 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 21:50 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 20:00 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Edward Cree <ecree@solarflare.com> - 2017-06-28 20:30 +0200
csiph-web