bpf: improve stacksafe state comparison
authorAlexei Starovoitov <ast@kernel.org>
Thu, 13 Dec 2018 19:42:33 +0000 (11:42 -0800)
committerDaniel Borkmann <daniel@iogearbox.net>
Sat, 15 Dec 2018 00:28:32 +0000 (01:28 +0100)
commit19e2dbb7dd978d24505e918ac54d6f7dfdc88b1d
tree874741560410dfa96412b382c02a65b3ddaf7fb9
parent730ff40f80c5b09b2402958321f2762a3f852e30
bpf: improve stacksafe state comparison

"if (old->allocated_stack > cur->allocated_stack)" check is too conservative.
In some cases explored stack could have allocated more space,
but that stack space was not live.
The test case improves from 19 to 15 processed insns
and improvement on real programs is significant as well:

                       before    after
bpf_lb-DLB_L3.o        1940      1831
bpf_lb-DLB_L4.o        3089      3029
bpf_lb-DUNKNOWN.o      1065      1064
bpf_lxc-DDROP_ALL.o    28052     26309
bpf_lxc-DUNKNOWN.o     35487     33517
bpf_netdev.o           10864     9713
bpf_overlay.o          6643      6184
bpf_lcx_jit.o          38437     37335

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Edward Cree <ecree@solarflare.com>
Acked-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
kernel/bpf/verifier.c
tools/testing/selftests/bpf/test_verifier.c