• Edward Cree's avatar
    bpf/verifier: track liveness for pruning · dc503a8a
    Edward Cree authored
    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: default avatarEdward Cree <ecree@solarflare.com>
    Acked-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    dc503a8a
verifier.c 127 KB