bpf: fix precision tracking
authorAlexei Starovoitov <ast@kernel.org>
Fri, 28 Jun 2019 16:24:09 +0000 (09:24 -0700)
committerDaniel Borkmann <daniel@iogearbox.net>
Wed, 3 Jul 2019 09:12:14 +0000 (11:12 +0200)
commita3ce685dd01a786fa5bc388e47d0066a4f842591
tree38e3aaffd4b9f7aeb593edc28321fb5bb68f9688
parent8daed7677a1da676332e0294db8a09cad030e693
bpf: fix precision tracking

When equivalent state is found the current state needs to propagate precision marks.
Otherwise the verifier will prune the search incorrectly.

There is a price for correctness:
                      before      before    broken    fixed
                      cnst spill  precise   precise
bpf_lb-DLB_L3.o       1923        8128      1863      1898
bpf_lb-DLB_L4.o       3077        6707      2468      2666
bpf_lb-DUNKNOWN.o     1062        1062      544       544
bpf_lxc-DDROP_ALL.o   166729      380712    22629     36823
bpf_lxc-DUNKNOWN.o    174607      440652    28805     45325
bpf_netdev.o          8407        31904     6801      7002
bpf_overlay.o         5420        23569     4754      4858
bpf_lxc_jit.o         39389       359445    50925     69631
Overall precision tracking is still very effective.

Fixes: b5dc0163d8fd ("bpf: precise scalar_value tracking")
Reported-by: Lawrence Brakmo <brakmo@fb.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Andrii Nakryiko <andriin@fb.com>
Tested-by: Lawrence Brakmo <brakmo@fb.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
kernel/bpf/verifier.c