bpf/verifier: track liveness for pruning
authorEdward Cree <ecree@solarflare.com>
Tue, 15 Aug 2017 19:34:35 +0000 (20:34 +0100)
committerDavid S. Miller <davem@davemloft.net>
Tue, 15 Aug 2017 23:32:33 +0000 (16:32 -0700)
commitdc503a8ad98474ea0073a1c5c4d9f18cb8dd0dbf
tree042702a45fc624febef25ce9173298fe7d396280
parent0461b76661d0689bdcaf953a8c42addc517febf1
bpf/verifier: track liveness for pruning

State of a register doesn't matter if it wasn't read in reaching an exit;
 a write screens off all reads downstream of it from all explored_states
 upstream of it.
This allows us to prune many more branches; here are some processed insn
 counts for some Cilium programs:
Program                  before  after
bpf_lb_opt_-DLB_L3.o       6515   3361
bpf_lb_opt_-DLB_L4.o       8976   5176
bpf_lb_opt_-DUNKNOWN.o     2960   1137
bpf_lxc_opt_-DDROP_ALL.o  95412  48537
bpf_lxc_opt_-DUNKNOWN.o  141706  78718
bpf_netdev.o              24251  17995
bpf_overlay.o             10999   9385

The runtime is also improved; here are 'time' results in ms:
Program                  before  after
bpf_lb_opt_-DLB_L3.o         24      6
bpf_lb_opt_-DLB_L4.o         26     11
bpf_lb_opt_-DUNKNOWN.o       11      2
bpf_lxc_opt_-DDROP_ALL.o   1288    139
bpf_lxc_opt_-DUNKNOWN.o    1768    234
bpf_netdev.o                 62     31
bpf_overlay.o                15     13

Signed-off-by: Edward Cree <ecree@solarflare.com>
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/linux/bpf_verifier.h
kernel/bpf/verifier.c