bpf: introduce bounded loops
authorAlexei Starovoitov <ast@kernel.org>
Sat, 15 Jun 2019 19:12:20 +0000 (12:12 -0700)
committerDaniel Borkmann <daniel@iogearbox.net>
Wed, 19 Jun 2019 00:22:51 +0000 (02:22 +0200)
commit2589726d12a1b12eaaa93c7f1ea64287e383c7a5
tree3116405339b609ed1ed6cdd24db9291d4dafdc67
parentfb8d251ee2a6bf4d7f4af5548e9c8f4fb5f90402
bpf: introduce bounded loops

Allow the verifier to validate the loops by simulating their execution.
Exisiting programs have used '#pragma unroll' to unroll the loops
by the compiler. Instead let the verifier simulate all iterations
of the loop.
In order to do that introduce parentage chain of bpf_verifier_state and
'branches' counter for the number of branches left to explore.
See more detailed algorithm description in bpf_verifier.h

This algorithm borrows the key idea from Edward Cree approach:
https://patchwork.ozlabs.org/patch/877222/
Additional state pruning heuristics make such brute force loop walk
practical even for large loops.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Andrii Nakryiko <andriin@fb.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
include/linux/bpf_verifier.h
kernel/bpf/verifier.c