On Fri, Jun 14, 2019 at 12:26 AM Alexei Starovoitov <ast@xxxxxxxxxx> wrote: > > Compilers often spill induction variables into the stack, > hence it is necessary for the verifier to track scalar values > of the registers through stack slots. > > Also few bpf programs were incorrectly rejected in the past, > since the verifier was not able to track such constants while > they were used to compute offsets into packet headers. > > Tracking constants through the stack significantly decreases > the chances of state pruning, since two different constants > are considered to be different by state equivalency. > End result that cilium tests suffer serious degradation in the number > of states processed and corresponding verification time increase. > > before after > bpf_lb-DLB_L3.o 1838 6441 > bpf_lb-DLB_L4.o 3218 5908 > bpf_lb-DUNKNOWN.o 1064 1064 > bpf_lxc-DDROP_ALL.o 26935 93790 > bpf_lxc-DUNKNOWN.o 34439 123886 > bpf_netdev.o 9721 31413 > bpf_overlay.o 6184 18561 > bpf_lxc_jit.o 39389 359445 > > After further debugging turned out that cillium progs are > getting hurt by clang due to the same constant tracking issue. > Newer clang generates better code by spilling less to the stack. > Instead it keeps more constants in the registers which > hurts state pruning since the verifier already tracks constants > in the registers: > old clang new clang > (no spill/fill tracking introduced by this patch) > bpf_lb-DLB_L3.o 1838 1923 > bpf_lb-DLB_L4.o 3218 3077 > bpf_lb-DUNKNOWN.o 1064 1062 > bpf_lxc-DDROP_ALL.o 26935 166729 > bpf_lxc-DUNKNOWN.o 34439 174607 > bpf_netdev.o 9721 8407 > bpf_overlay.o 6184 5420 > bpf_lcx_jit.o 39389 39389 > > The final table is depressing: > old clang old clang new clang new clang > const spill/fill const spill/fill > bpf_lb-DLB_L3.o 1838 6441 1923 8128 > bpf_lb-DLB_L4.o 3218 5908 3077 6707 > bpf_lb-DUNKNOWN.o 1064 1064 1062 1062 > bpf_lxc-DDROP_ALL.o 26935 93790 166729 380712 > bpf_lxc-DUNKNOWN.o 34439 123886 174607 440652 > bpf_netdev.o 9721 31413 8407 31904 > bpf_overlay.o 6184 18561 5420 23569 > bpf_lxc_jit.o 39389 359445 39389 359445 > > Tracking constants in the registers hurts state pruning already. > Adding tracking of constants through stack hurts pruning even more. > The later patch address this general constant tracking issue > with coarse/precise logic. > > Signed-off-by: Alexei Starovoitov <ast@xxxxxxxxxx> > --- This looks good as well, thanks! Acked-by: Andrii Nakryiko <andriin@xxxxxx> > kernel/bpf/verifier.c | 90 +++++++++++++++++++++++++++++++------------ > 1 file changed, 65 insertions(+), 25 deletions(-) >
