Re: [PATCH bpf-next 7/7] bpf: track aligned STACK_ZERO cases as imprecise spilled registers

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Wed, Nov 1, 2023 at 12:56 AM Jiri Olsa <olsajiri@xxxxxxxxx> wrote:
>
> On Mon, Oct 30, 2023 at 10:22:48PM -0700, Andrii Nakryiko wrote:
> > On Mon, Oct 30, 2023 at 10:03 PM Andrii Nakryiko <andrii@xxxxxxxxxx> wrote:
> > >
> > > Now that precision backtracing is supporting register spill/fill to/from
> > > stack, there is another oportunity to be exploited here: minimizing
> > > precise STACK_ZERO cases. With a simple code change we can rely on
> > > initially imprecise register spill tracking for cases when register
> > > spilled to stack was a known zero.
> > >
> > > This is a very common case for initializing on the stack variables,
> > > including rather large structures. Often times zero has no special
> > > meaning for the subsequent BPF program logic and is often overwritten
> > > with non-zero values soon afterwards. But due to STACK_ZERO vs
> > > STACK_MISC tracking, such initial zero initialization actually causes
> > > duplication of verifier states as STACK_ZERO is clearly different than
> > > STACK_MISC or spilled SCALAR_VALUE register.
> > >
> > > The effect of this (now) trivial change is huge, as can be seen below.
> > > These are differences between BPF selftests, Cilium, and Meta-internal
> > > BPF object files relative to previous patch in this series. You can see
> > > improvements ranging from single-digit percentage improvement for
> > > instructions and states, all the way to 50-60% reduction for some of
> > > Meta-internal host agent programs, and even some Cilium programs.
> > >
> > > For Meta-internal ones I left only the differences for largest BPF
> > > object files by states/instructions, as there were too many differences
> > > in the overall output. All the differences were improvements, reducting
> > > number of states and thus instructions validated.
> > >
> > > Note, Meta-internal BPF object file names are not printed below.
> > > Many copies of balancer_ingress are actually many different
> > > configurations of Katran, so they are different BPF programs, which
> > > explains state reduction going from -16% all the way to 31%, depending
> > > on BPF program logic complexity.
> > >
> > > SELFTESTS
> > > =========
> > > File                                     Program                  Insns (A)  Insns (B)  Insns    (DIFF)  States (A)  States (B)  States (DIFF)
> > > ---------------------------------------  -----------------------  ---------  ---------  ---------------  ----------  ----------  -------------
> > > bpf_iter_netlink.bpf.linked3.o           dump_netlink                   148        104    -44 (-29.73%)           8           5   -3 (-37.50%)
> > > bpf_iter_unix.bpf.linked3.o              dump_unix                     8474       8404     -70 (-0.83%)         151         147    -4 (-2.65%)
> > > bpf_loop.bpf.linked3.o                   stack_check                    560        324   -236 (-42.14%)          42          24  -18 (-42.86%)
> > > local_storage_bench.bpf.linked3.o        get_local                      120         77    -43 (-35.83%)           9           6   -3 (-33.33%)
> > > loop6.bpf.linked3.o                      trace_virtqueue_add_sgs      10167       9868    -299 (-2.94%)         226         206   -20 (-8.85%)
> > > pyperf600_bpf_loop.bpf.linked3.o         on_event                      4872       3423  -1449 (-29.74%)         322         229  -93 (-28.88%)
> > > strobemeta.bpf.linked3.o                 on_event                    180697     176036   -4661 (-2.58%)        4780        4734   -46 (-0.96%)
> > > test_cls_redirect.bpf.linked3.o          cls_redirect                 65594      65401    -193 (-0.29%)        4230        4212   -18 (-0.43%)
> > > test_global_func_args.bpf.linked3.o      test_cls                       145        136      -9 (-6.21%)          10           9   -1 (-10.00%)
> > > test_l4lb.bpf.linked3.o                  balancer_ingress              4760       2612  -2148 (-45.13%)         113         102   -11 (-9.73%)
> > > test_l4lb_noinline.bpf.linked3.o         balancer_ingress              4845       4877     +32 (+0.66%)         219         221    +2 (+0.91%)
> > > test_l4lb_noinline_dynptr.bpf.linked3.o  balancer_ingress              2072       2087     +15 (+0.72%)          97          98    +1 (+1.03%)
> > > test_seg6_loop.bpf.linked3.o             __add_egr_x                  12440       9975  -2465 (-19.82%)         364         353   -11 (-3.02%)
> > > test_tcp_hdr_options.bpf.linked3.o       estab                         2558       2572     +14 (+0.55%)         179         180    +1 (+0.56%)
> > > test_xdp_dynptr.bpf.linked3.o            _xdp_tx_iptunnel               645        596     -49 (-7.60%)          26          24    -2 (-7.69%)
> > > test_xdp_noinline.bpf.linked3.o          balancer_ingress_v6           3520       3516      -4 (-0.11%)         216         216    +0 (+0.00%)
> > > xdp_synproxy_kern.bpf.linked3.o          syncookie_tc                 82661      81241   -1420 (-1.72%)        5073        5155   +82 (+1.62%)
> > > xdp_synproxy_kern.bpf.linked3.o          syncookie_xdp                84964      82297   -2667 (-3.14%)        5130        5157   +27 (+0.53%)
> > >
> > > META-INTERNAL
> > > =============
> > > Program                                 Insns (A)  Insns (B)  Insns      (DIFF)  States (A)  States (B)  States   (DIFF)
> > > --------------------------------------  ---------  ---------  -----------------  ----------  ----------  ---------------
> > > balancer_ingress                            27925      23608    -4317 (-15.46%)        1488        1482      -6 (-0.40%)
> > > balancer_ingress                            31824      27546    -4278 (-13.44%)        1658        1652      -6 (-0.36%)
> > > balancer_ingress                            32213      27935    -4278 (-13.28%)        1689        1683      -6 (-0.36%)
> > > balancer_ingress                            32213      27935    -4278 (-13.28%)        1689        1683      -6 (-0.36%)
> > > balancer_ingress                            31824      27546    -4278 (-13.44%)        1658        1652      -6 (-0.36%)
> > > balancer_ingress                            38647      29562    -9085 (-23.51%)        2069        1835   -234 (-11.31%)
> > > balancer_ingress                            38647      29562    -9085 (-23.51%)        2069        1835   -234 (-11.31%)
> > > balancer_ingress                            40339      30792    -9547 (-23.67%)        2193        1934   -259 (-11.81%)
> > > balancer_ingress                            37321      29055    -8266 (-22.15%)        1972        1795    -177 (-8.98%)
> > > balancer_ingress                            38176      29753    -8423 (-22.06%)        2008        1831    -177 (-8.81%)
> > > balancer_ingress                            29193      20910    -8283 (-28.37%)        1599        1422   -177 (-11.07%)
> > > balancer_ingress                            30013      21452    -8561 (-28.52%)        1645        1447   -198 (-12.04%)
> > > balancer_ingress                            28691      24290    -4401 (-15.34%)        1545        1531     -14 (-0.91%)
> > > balancer_ingress                            34223      28965    -5258 (-15.36%)        1984        1875    -109 (-5.49%)
> > > balancer_ingress                            35481      26158    -9323 (-26.28%)        2095        1806   -289 (-13.79%)
> > > balancer_ingress                            35481      26158    -9323 (-26.28%)        2095        1806   -289 (-13.79%)
> > > balancer_ingress                            35868      26455    -9413 (-26.24%)        2140        1827   -313 (-14.63%)
> > > balancer_ingress                            35868      26455    -9413 (-26.24%)        2140        1827   -313 (-14.63%)
> > > balancer_ingress                            35481      26158    -9323 (-26.28%)        2095        1806   -289 (-13.79%)
> > > balancer_ingress                            35481      26158    -9323 (-26.28%)        2095        1806   -289 (-13.79%)
> > > balancer_ingress                            34844      29485    -5359 (-15.38%)        2036        1918    -118 (-5.80%)
> > > fbflow_egress                                3256       2652     -604 (-18.55%)         218         192    -26 (-11.93%)
> > > fbflow_ingress                               1026        944       -82 (-7.99%)          70          63     -7 (-10.00%)
> > > sslwall_tc_egress                            8424       7360    -1064 (-12.63%)         498         458     -40 (-8.03%)
> > > syar_accept_protect                         15040       9539    -5501 (-36.58%)         364         220   -144 (-39.56%)
> > > syar_connect_tcp_v6                         15036       9535    -5501 (-36.59%)         360         216   -144 (-40.00%)
> > > syar_connect_udp_v4                         15039       9538    -5501 (-36.58%)         361         217   -144 (-39.89%)
> > > syar_connect_connect4_protect4              24805      15833    -8972 (-36.17%)         756         480   -276 (-36.51%)
> > > syar_lsm_file_open                         167772     151813    -15959 (-9.51%)        1836        1667    -169 (-9.20%)
> > > syar_namespace_create_new                   14805       9304    -5501 (-37.16%)         353         209   -144 (-40.79%)
> > > syar_python3_detect                         17531      12030    -5501 (-31.38%)         391         247   -144 (-36.83%)
> > > syar_ssh_post_fork                          16412      10911    -5501 (-33.52%)         405         261   -144 (-35.56%)
> > > syar_enter_execve                           14728       9227    -5501 (-37.35%)         345         201   -144 (-41.74%)
> > > syar_enter_execveat                         14728       9227    -5501 (-37.35%)         345         201   -144 (-41.74%)
> > > syar_exit_execve                            16622      11121    -5501 (-33.09%)         376         232   -144 (-38.30%)
> > > syar_exit_execveat                          16622      11121    -5501 (-33.09%)         376         232   -144 (-38.30%)
> > > syar_syscalls_kill                          15288       9787    -5501 (-35.98%)         398         254   -144 (-36.18%)
> > > syar_task_enter_pivot_root                  14898       9397    -5501 (-36.92%)         357         213   -144 (-40.34%)
> > > syar_syscalls_setreuid                      16678      11177    -5501 (-32.98%)         429         285   -144 (-33.57%)
> > > syar_syscalls_setuid                        16678      11177    -5501 (-32.98%)         429         285   -144 (-33.57%)
> > > syar_syscalls_process_vm_readv              14959       9458    -5501 (-36.77%)         364         220   -144 (-39.56%)
> > > syar_syscalls_process_vm_writev             15757      10256    -5501 (-34.91%)         390         246   -144 (-36.92%)
> > > do_uprobe                                   15519      10018    -5501 (-35.45%)         373         229   -144 (-38.61%)
> > > edgewall                                   179715      55783  -123932 (-68.96%)       12607        3999  -8608 (-68.28%)
> > > bictcp_state                                 7570       4131    -3439 (-45.43%)         496         269   -227 (-45.77%)
> > > cubictcp_state                               7570       4131    -3439 (-45.43%)         496         269   -227 (-45.77%)
> > > tcp_rate_skb_delivered                        447        272     -175 (-39.15%)          29          18    -11 (-37.93%)
> > > kprobe__bbr_set_state                        4566       2615    -1951 (-42.73%)         209         124    -85 (-40.67%)
> > > kprobe__bictcp_state                         4566       2615    -1951 (-42.73%)         209         124    -85 (-40.67%)
> > > inet_sock_set_state                          1501       1337     -164 (-10.93%)          93          85      -8 (-8.60%)
> > > tcp_retransmit_skb                           1145        981     -164 (-14.32%)          67          59     -8 (-11.94%)
> > > tcp_retransmit_synack                        1183        951     -232 (-19.61%)          67          55    -12 (-17.91%)
> > > bpf_tcptuner                                 1459       1187     -272 (-18.64%)          99          80    -19 (-19.19%)
> > > tw_egress                                     801        776       -25 (-3.12%)          69          66      -3 (-4.35%)
> > > tw_ingress                                    795        770       -25 (-3.14%)          69          66      -3 (-4.35%)
> > > ttls_tc_ingress                             19025      19383      +358 (+1.88%)         470         465      -5 (-1.06%)
> > > ttls_nat_egress                               490        299     -191 (-38.98%)          33          20    -13 (-39.39%)
> > > ttls_nat_ingress                              448        285     -163 (-36.38%)          32          21    -11 (-34.38%)
> > > tw_twfw_egress                             511127     212071  -299056 (-58.51%)       16733        8504  -8229 (-49.18%)
> > > tw_twfw_ingress                            500095     212069  -288026 (-57.59%)       16223        8504  -7719 (-47.58%)
> > > tw_twfw_tc_eg                              511113     212064  -299049 (-58.51%)       16732        8504  -8228 (-49.18%)
> > > tw_twfw_tc_in                              500095     212069  -288026 (-57.59%)       16223        8504  -7719 (-47.58%)
> > > tw_twfw_egress                              12632      12435      -197 (-1.56%)         276         260     -16 (-5.80%)
> > > tw_twfw_ingress                             12631      12454      -177 (-1.40%)         278         261     -17 (-6.12%)
> > > tw_twfw_tc_eg                               12595      12435      -160 (-1.27%)         274         259     -15 (-5.47%)
> > > tw_twfw_tc_in                               12631      12454      -177 (-1.40%)         278         261     -17 (-6.12%)
> > > tw_xdp_dump                                   266        209      -57 (-21.43%)           9           8     -1 (-11.11%)
> > >
> > > CILIUM
> > > =========
> > > File           Program                           Insns (A)  Insns (B)  Insns     (DIFF)  States (A)  States (B)  States  (DIFF)
> > > -------------  --------------------------------  ---------  ---------  ----------------  ----------  ----------  --------------
> > > bpf_host.o     cil_to_netdev                          6047       4578   -1469 (-24.29%)         362         249  -113 (-31.22%)
> > > bpf_host.o     handle_lxc_traffic                     2227       1585    -642 (-28.83%)         156         103   -53 (-33.97%)
> > > bpf_host.o     tail_handle_ipv4_from_netdev           2244       1458    -786 (-35.03%)         163         106   -57 (-34.97%)
> > > bpf_host.o     tail_handle_nat_fwd_ipv4              21022      10479  -10543 (-50.15%)        1289         670  -619 (-48.02%)
> > > bpf_host.o     tail_handle_nat_fwd_ipv6              15433      11375   -4058 (-26.29%)         905         643  -262 (-28.95%)
> > > bpf_host.o     tail_ipv4_host_policy_ingress          2219       1367    -852 (-38.40%)         161          96   -65 (-40.37%)
> > > bpf_host.o     tail_nodeport_nat_egress_ipv4         22460      19862   -2598 (-11.57%)        1469        1293  -176 (-11.98%)
> > > bpf_host.o     tail_nodeport_nat_ingress_ipv4         5526       3534   -1992 (-36.05%)         366         243  -123 (-33.61%)
> > > bpf_host.o     tail_nodeport_nat_ingress_ipv6         5132       4256    -876 (-17.07%)         241         219    -22 (-9.13%)
> > > bpf_host.o     tail_nodeport_nat_ipv6_egress          3702       3542     -160 (-4.32%)         215         205    -10 (-4.65%)
> > > bpf_lxc.o      tail_handle_nat_fwd_ipv4              21022      10479  -10543 (-50.15%)        1289         670  -619 (-48.02%)
> > > bpf_lxc.o      tail_handle_nat_fwd_ipv6              15433      11375   -4058 (-26.29%)         905         643  -262 (-28.95%)
> > > bpf_lxc.o      tail_ipv4_ct_egress                    5073       3374   -1699 (-33.49%)         262         172   -90 (-34.35%)
> > > bpf_lxc.o      tail_ipv4_ct_ingress                   5093       3385   -1708 (-33.54%)         262         172   -90 (-34.35%)
> > > bpf_lxc.o      tail_ipv4_ct_ingress_policy_only       5093       3385   -1708 (-33.54%)         262         172   -90 (-34.35%)
> > > bpf_lxc.o      tail_ipv6_ct_egress                    4593       3878    -715 (-15.57%)         194         151   -43 (-22.16%)
> > > bpf_lxc.o      tail_ipv6_ct_ingress                   4606       3891    -715 (-15.52%)         194         151   -43 (-22.16%)
> > > bpf_lxc.o      tail_ipv6_ct_ingress_policy_only       4606       3891    -715 (-15.52%)         194         151   -43 (-22.16%)
> > > bpf_lxc.o      tail_nodeport_nat_ingress_ipv4         5526       3534   -1992 (-36.05%)         366         243  -123 (-33.61%)
> > > bpf_lxc.o      tail_nodeport_nat_ingress_ipv6         5132       4256    -876 (-17.07%)         241         219    -22 (-9.13%)
> > > bpf_overlay.o  tail_handle_nat_fwd_ipv4              20524      10114  -10410 (-50.72%)        1271         638  -633 (-49.80%)
> > > bpf_overlay.o  tail_nodeport_nat_egress_ipv4         22718      19490   -3228 (-14.21%)        1475        1275  -200 (-13.56%)
> > > bpf_overlay.o  tail_nodeport_nat_ingress_ipv4         5526       3534   -1992 (-36.05%)         366         243  -123 (-33.61%)
> > > bpf_overlay.o  tail_nodeport_nat_ingress_ipv6         5132       4256    -876 (-17.07%)         241         219    -22 (-9.13%)
> > > bpf_overlay.o  tail_nodeport_nat_ipv6_egress          3638       3548      -90 (-2.47%)         209         203     -6 (-2.87%)
> > > bpf_overlay.o  tail_rev_nodeport_lb4                  4368       3820    -548 (-12.55%)         248         215   -33 (-13.31%)
> > > bpf_overlay.o  tail_rev_nodeport_lb6                  2867       2428    -439 (-15.31%)         167         140   -27 (-16.17%)
> > > bpf_sock.o     cil_sock6_connect                      1718       1703      -15 (-0.87%)         100          99     -1 (-1.00%)
> > > bpf_xdp.o      tail_handle_nat_fwd_ipv4              12917      12443     -474 (-3.67%)         875         849    -26 (-2.97%)
> > > bpf_xdp.o      tail_handle_nat_fwd_ipv6              13515      13264     -251 (-1.86%)         715         702    -13 (-1.82%)
> > > bpf_xdp.o      tail_lb_ipv4                          39492      36367    -3125 (-7.91%)        2430        2251   -179 (-7.37%)
> > > bpf_xdp.o      tail_lb_ipv6                          80441      78058    -2383 (-2.96%)        3647        3523   -124 (-3.40%)
> > > bpf_xdp.o      tail_nodeport_ipv6_dsr                 1038        901    -137 (-13.20%)          61          55     -6 (-9.84%)
> > > bpf_xdp.o      tail_nodeport_nat_egress_ipv4         13027      12096     -931 (-7.15%)         868         809    -59 (-6.80%)
> > > bpf_xdp.o      tail_nodeport_nat_ingress_ipv4         7617       5900   -1717 (-22.54%)         522         413  -109 (-20.88%)
> > > bpf_xdp.o      tail_nodeport_nat_ingress_ipv6         7575       7395     -180 (-2.38%)         383         374     -9 (-2.35%)
> > > bpf_xdp.o      tail_rev_nodeport_lb4                  6808       6739      -69 (-1.01%)         403         396     -7 (-1.74%)
> > > bpf_xdp.o      tail_rev_nodeport_lb6                 16173      15847     -326 (-2.02%)        1010         990    -20 (-1.98%)
> > >
> >
> > So I also want to mention that while I did spot check a few programs
> > (not the biggest ones) and they did seem to have correct verification
> > flow, I obviously can't easily validate verifier log_level=2 logs for
> > all of the changes above, especially those multi-thousand state
> > programs. I'd really appreciate someone from Isovalent/Cilium to do
> > some checking of the Cilium program or two for sanity, just in case.
> > Thanks!
>
> fyi, I was curious so tried that on top of tetragon programs,
> seems up and down, but verification time is mostly lower ;-)
>

Nice! Can you please regenerate results and sort by either insn_diff
(absolute difference, not percentage), or states_diff? It would be
easier to see top10 improvement and regression that way. Percentages
by themselves can be misleading.

Oh, and peak states are probably not that useful, so maybe just use
`-e file,prog,duration,insns,states -s insns_diff`?

> jirka
>
>
> ---
> $ veristat --compare veristat.old veristat.new
>
> File                            Program                        Duration (us) (A)  Duration (us) (B)  Duration (us) (DIFF)  Insns (A)  Insns (B)  Insns     (DIFF)  States (A)  States (B)  States   (DIFF)  Peak states (A)  Peak states (B)  Peak states (DIFF)
> ------------------------------  -----------------------------  -----------------  -----------------  --------------------  ---------  ---------  ----------------  ----------  ----------  ---------------  ---------------  ---------------  ------------------
> bpf_cgroup_mkdir.o              tg_tp_cgrp_mkdir                             206                190          -16 (-7.77%)        581        581       +0 (+0.00%)          24          24      +0 (+0.00%)               24               24         +0 (+0.00%)
> bpf_cgroup_release.o            tg_tp_cgrp_release                           114                104          -10 (-8.77%)        381        381       +0 (+0.00%)          13          13      +0 (+0.00%)               13               13         +0 (+0.00%)
> bpf_cgroup_rmdir.o              tg_tp_cgrp_rmdir                             126                121           -5 (-3.97%)        381        381       +0 (+0.00%)          13          13      +0 (+0.00%)               13               13         +0 (+0.00%)
> bpf_execve_bprm_commit_creds.o  tg_kp_bprm_committing_creds                  100                 95           -5 (-5.00%)        163        163       +0 (+0.00%)          14          14      +0 (+0.00%)               14               14         +0 (+0.00%)
> bpf_execve_event.o              event_execve                               12147              12843         +696 (+5.73%)      35096      34723     -373 (-1.06%)        2278        2251     -27 (-1.19%)             1110             1115         +5 (+0.45%)
> bpf_execve_event.o              execve_send                                   93                 57         -36 (-38.71%)         82         82       +0 (+0.00%)           6           6      +0 (+0.00%)                6                6         +0 (+0.00%)
> bpf_execve_event_v53.o          event_execve                               97457              98430         +973 (+1.00%)     245365     239363    -6002 (-2.45%)       15430       15334     -96 (-0.62%)             7994             7929        -65 (-0.81%)
> bpf_execve_event_v53.o          execve_send                                   52                 54           +2 (+3.85%)        105        105       +0 (+0.00%)           5           5      +0 (+0.00%)                5                5         +0 (+0.00%)
> bpf_execve_event_v61.o          event_execve                                6094               6059          -35 (-0.57%)      27456      26871     -585 (-2.13%)         671         636     -35 (-5.22%)              301              309         +8 (+2.66%)
> bpf_execve_event_v61.o          execve_send                                   66                 69           +3 (+4.55%)        105        105       +0 (+0.00%)           5           5      +0 (+0.00%)                5                5         +0 (+0.00%)
> bpf_exit.o                      event_exit                                    65                 53         -12 (-18.46%)         94         94       +0 (+0.00%)           8           8      +0 (+0.00%)                8                8         +0 (+0.00%)
> bpf_fork.o                      event_wake_up_new_task                       179                209         +30 (+16.76%)        514        514       +0 (+0.00%)          30          30      +0 (+0.00%)               30               30         +0 (+0.00%)

[...]





[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux