[lkml]   [2017]   [Jun]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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
> 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


 \ /
  Last update: 2017-06-28 15:51    [W:0.212 / U:0.208 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site