Alexei Starovoitov 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
^^^^^^^^^^^^^^
Any idea what happened here? Going from 34439 -> 174607 on the new clang?
> 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 <[email protected]>
> Acked-by: Andrii Nakryiko <[email protected]>
> ---
> kernel/bpf/verifier.c | 90 +++++++++++++++++++++++++++++++------------
> 1 file changed, 65 insertions(+), 25 deletions(-)
I know these are already in bpf-next sorry it took me awhile to get
time to review, but looks good to me. Thanks! We had something similar
in the earlier loop test branch from last year.
