[PATCH bpf-next 0/2] bpf: Fix to preserve reg parent/live fields when copying range info

[Eduard Zingerman <eddyz87@gmail.com>]

Struct bpf_reg_state is copied directly in several places including:
- check_stack_write_fixed_off() (via save_register_state());
- check_stack_read_fixed_off();
- find_equal_scalars().

However, a literal copy of this struct also copies the following fields:

struct bpf_reg_state {
	...
	struct bpf_reg_state *parent;
	...
	enum bpf_reg_liveness live;
	...
};

This breaks register parentage chain and liveness marking logic.
The commit message for the first patch has a detailed example.
This patch-set replaces direct copies with a call to a function
copy_register_state(dst,src), which preserves 'parent' and 'live'
fields of the 'dst'.

The fix comes with a significant verifier runtime penalty for some
selftest binaries listed in tools/testing/selftests/bpf/veristat.cfg
and cilium BPF binaries (see [1]):

$ ./veristat -e file,prog,states -C -f 'states_diff>10' master-baseline.log current.log 
File                        Program                         States (A)  States (B)  States   (DIFF)
--------------------------  ------------------------------  ----------  ----------  ---------------
bpf_host.o                  tail_handle_ipv4_from_host             225         297    +72 (+32.00%)
bpf_host.o                  tail_handle_nat_fwd_ipv4              1746        1900    +154 (+8.82%)
bpf_host.o                  tail_handle_nat_fwd_ipv6               709         722     +13 (+1.83%)
bpf_host.o                  tail_nodeport_nat_ingress_ipv4         276         316    +40 (+14.49%)
bpf_host.o                  tail_nodeport_nat_ingress_ipv6         243         254     +11 (+4.53%)
bpf_lxc.o                   tail_handle_nat_fwd_ipv4              1746        1900    +154 (+8.82%)
bpf_lxc.o                   tail_handle_nat_fwd_ipv6               709         722     +13 (+1.83%)
bpf_lxc.o                   tail_nodeport_nat_ingress_ipv4         276         316    +40 (+14.49%)
bpf_lxc.o                   tail_nodeport_nat_ingress_ipv6         243         254     +11 (+4.53%)
bpf_overlay.o               tail_handle_nat_fwd_ipv4              1082        1116     +34 (+3.14%)
bpf_overlay.o               tail_nodeport_nat_ingress_ipv4         276         316    +40 (+14.49%)
bpf_overlay.o               tail_nodeport_nat_ingress_ipv6         243         254     +11 (+4.53%)
bpf_sock.o                  cil_sock4_connect                       47          70    +23 (+48.94%)
bpf_sock.o                  cil_sock4_sendmsg                       45          68    +23 (+51.11%)
bpf_sock.o                  cil_sock6_post_bind                     31          42    +11 (+35.48%)
bpf_xdp.o                   tail_lb_ipv4                          4643        6996  +2353 (+50.68%)
bpf_xdp.o                   tail_lb_ipv6                          7303        8057   +754 (+10.32%)
test_cls_redirect.bpf.o     cls_redirect                          7918        8210    +292 (+3.69%)
test_tcp_hdr_options.bpf.o  estab                                  180         215    +35 (+19.44%)
xdp_synproxy_kern.bpf.o     syncookie_tc                         22513       22564     +51 (+0.23%)
xdp_synproxy_kern.bpf.o     syncookie_xdp                        22207       24206   +1999 (+9.00%)

This patch-set is a continuation of discussion from [2].

[1] git@github.com:anakryiko/cilium.git
[2] https://lore.kernel.org/bpf/517af2c57ee4b9ce2d96a8cf33f7295f2d2dfe13.camel@gmail.com/

Eduard Zingerman (2):
  bpf: Fix to preserve reg parent/live fields when copying range info
  selftests/bpf: Verify copy_register_state() preserves parent/live
    fields

 kernel/bpf/verifier.c                         | 25 +++++++++----
 .../selftests/bpf/verifier/search_pruning.c   | 36 +++++++++++++++++++
 2 files changed, 54 insertions(+), 7 deletions(-)

-- 
2.34.1