Re: [RFC PATCH bpf-next 05/12] bpf/verifier: detect loops dynamically rather than statically
From: John Fastabend <john.fastabend@gmail.com>
Date: 2018-02-23 22:27:29
On 02/23/2018 09:40 AM, Edward Cree wrote:
Add in a new chain of parent states, which does not cross function-call boundaries, and check whether our current insn_idx appears anywhere in the chain. Since all jump targets have state-list marks (now placed by prepare_cfg_marks(), which replaces check_cfg()), it suffices to thread this chain through the existing explored_states and check it only in is_state_visited(). By using this parent-state chain to detect loops, we open up the possibility that in future we could determine a loop to be bounded and thus accept it. A few selftests had to be changed to ensure that all the insns walked before reaching the back-edge are valid.
I still believe this needs to be done in an initial pass where we can build a proper CFG and analyze the loops to ensure we have loops that can be properly verified. Otherwise we end up trying to handle all the special cases later like the comment in patch 7/12 'three-jump trick'. So rather than try to handle all loops only handle "normal" loops. In an early CFG stage with DOM tree the algorithm for this is already used by gcc/clang so there is good precedent for this type of work. Without this we are open to other "clever" goto programs that create loops that we have to special case. Better to just reject all these classes of loops because most users will never need them. See more notes in 7/12 patch, sorry I've been busy and not had a chance to push code to build cfg and dom tree yet. Also case analysis in patch description describing types of loops this handles (either here or in another patch) would help me understand at least.
quoted hunk ↗ jump to hunk
Signed-off-by: Edward Cree <redacted> --- include/linux/bpf_verifier.h | 2 + kernel/bpf/verifier.c | 280 +++++++++------------------- tools/testing/selftests/bpf/test_verifier.c | 12 +- 3 files changed, 97 insertions(+), 197 deletions(-)diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 0bc49c768585..24ddbc1ed3b2 100644