Andrii Nakryiko
1952a4d5e4
bpf: aggressively forget precise markings during state checkpointing ...
[ Upstream commit 7a830b53c17bbadcf99f778f28aaaa4e6c41df5f ]
Exploit the property of about-to-be-checkpointed state to be able to
forget all precise markings up to that point even more aggressively. We
now clear all potentially inherited precise markings right before
checkpointing and branching off into child state. If any of children
states require precise knowledge of any SCALAR register, those will be
propagated backwards later on before this state is finalized, preserving
correctness.
There is a single selftests BPF program change, but tremendous one: 25x
reduction in number of verified instructions and states in
trace_virtqueue_add_sgs.
Cilium results are more modest, but happen across wider range of programs.
SELFTESTS RESULTS
=================
$ ./veristat -C -e file,prog,insns,states ~/imprecise-early-results.csv ~/imprecise-aggressive-results.csv | grep -v '+0'
File Program Total insns (A) Total insns (B) Total insns (DIFF) Total states (A) Total states (B) Total states (DIFF)
------------------- ----------------------- --------------- --------------- ------------------ ---------------- ---------------- -------------------
loop6.bpf.linked1.o trace_virtqueue_add_sgs 398057 15114 -382943 (-96.20%) 8717 336 -8381 (-96.15%)
------------------- ----------------------- --------------- --------------- ------------------ ---------------- ---------------- -------------------
CILIUM RESULTS
==============
$ ./veristat -C -e file,prog,insns,states ~/imprecise-early-results-cilium.csv ~/imprecise-aggressive-results-cilium.csv | grep -v '+0'
File Program Total insns (A) Total insns (B) Total insns (DIFF) Total states (A) Total states (B) Total states (DIFF)
------------- -------------------------------- --------------- --------------- ------------------ ---------------- ---------------- -------------------
bpf_host.o tail_handle_nat_fwd_ipv4 23426 23221 -205 (-0.88%) 1537 1515 -22 (-1.43%)
bpf_host.o tail_handle_nat_fwd_ipv6 13009 12904 -105 (-0.81%) 719 708 -11 (-1.53%)
bpf_host.o tail_nodeport_nat_ingress_ipv6 5261 5196 -65 (-1.24%) 247 243 -4 (-1.62%)
bpf_host.o tail_nodeport_nat_ipv6_egress 3446 3406 -40 (-1.16%) 203 198 -5 (-2.46%)
bpf_lxc.o tail_handle_nat_fwd_ipv4 23426 23221 -205 (-0.88%) 1537 1515 -22 (-1.43%)
bpf_lxc.o tail_handle_nat_fwd_ipv6 13009 12904 -105 (-0.81%) 719 708 -11 (-1.53%)
bpf_lxc.o tail_ipv4_ct_egress 5074 4897 -177 (-3.49%) 255 248 -7 (-2.75%)
bpf_lxc.o tail_ipv4_ct_ingress 5100 4923 -177 (-3.47%) 255 248 -7 (-2.75%)
bpf_lxc.o tail_ipv4_ct_ingress_policy_only 5100 4923 -177 (-3.47%) 255 248 -7 (-2.75%)
bpf_lxc.o tail_ipv6_ct_egress 4558 4536 -22 (-0.48%) 188 187 -1 (-0.53%)
bpf_lxc.o tail_ipv6_ct_ingress 4578 4556 -22 (-0.48%) 188 187 -1 (-0.53%)
bpf_lxc.o tail_ipv6_ct_ingress_policy_only 4578 4556 -22 (-0.48%) 188 187 -1 (-0.53%)
bpf_lxc.o tail_nodeport_nat_ingress_ipv6 5261 5196 -65 (-1.24%) 247 243 -4 (-1.62%)
bpf_overlay.o tail_nodeport_nat_ingress_ipv6 5261 5196 -65 (-1.24%) 247 243 -4 (-1.62%)
bpf_overlay.o tail_nodeport_nat_ipv6_egress 3482 3442 -40 (-1.15%) 204 201 -3 (-1.47%)
bpf_xdp.o tail_nodeport_nat_egress_ipv4 17200 15619 -1581 (-9.19%) 1111 1010 -101 (-9.09%)
------------- -------------------------------- --------------- --------------- ------------------ ---------------- ---------------- -------------------
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
Link: https://lore.kernel.org/r/20221104163649.121784-6-andrii@kernel.org
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Stable-dep-of: ecdf985d7615 ("bpf: track immediate values written to stack by BPF_ST instruction")
Signed-off-by: Pu Lehui <pulehui@huawei.com>
Tested-by: Luiz Capitulino <luizcap@amazon.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2023-08-16 18:20:59 +02:00
2021-03-30 14:32:03 +02:00
2022-08-25 11:37:55 +02:00
2021-03-30 14:31:56 +02:00
2021-03-04 11:37:33 +01:00
2023-05-30 12:57:48 +01:00
2023-07-27 08:44:38 +02:00
2023-07-27 08:44:38 +02:00
2020-11-06 13:15:21 -08:00
2020-01-09 08:46:18 -08:00
2021-10-06 15:55:50 +02:00
2023-06-28 10:28:16 +02:00
2023-07-27 08:43:37 +02:00
2023-04-05 11:23:35 +02:00
2020-09-28 23:30:42 +02:00
2021-12-17 10:14:41 +01:00
2021-08-04 12:46:44 +02:00
2020-03-13 12:49:52 -07:00
2022-08-25 11:37:55 +02:00
2021-09-03 10:09:31 +02:00
2021-04-14 08:42:00 +02:00
2021-09-03 10:09:21 +02:00
2020-08-28 15:41:30 +02:00
2020-10-29 20:01:46 -07:00
2020-08-28 15:41:30 +02:00
2020-08-28 15:41:30 +02:00
2020-08-21 14:01:39 -07:00
2020-08-01 20:38:28 -07:00
2020-02-17 16:53:49 +01:00
2022-11-25 17:45:45 +01:00
2020-10-06 00:04:11 +02:00
2020-07-25 20:16:32 -07:00
2020-08-28 15:41:30 +02:00
2020-09-30 11:50:35 -07:00
2022-02-08 18:30:39 +01:00
2022-06-22 14:13:12 +02:00
2022-10-26 13:25:21 +02:00
2020-09-21 21:50:24 +02:00
2021-01-19 18:27:28 +01:00
2020-03-30 14:59:53 -07:00
2022-06-06 08:42:45 +02:00
2023-08-16 18:20:59 +02:00
1952a4d5e4