Re: [PATCH net-next] bpf/verifier: track liveness for pruning

From: Daniel Borkmann
Date: Tue Aug 15 2017 - 07:53:05 EST


On 08/14/2017 07:55 PM, Edward Cree wrote:
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 79048
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 152
bpf_lxc_opt_-DUNKNOWN.o 1768 257
bpf_netdev.o 62 31
bpf_overlay.o 15 13

Signed-off-by: Edward Cree <ecree@xxxxxxxxxxxxxx>

Awesome work!

[...]
if (arg_type == ARG_ANYTHING) {
if (is_pointer_value(env, regno)) {
@@ -1639,10 +1675,13 @@ static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
}

/* reset caller saved regs */
- for (i = 0; i < CALLER_SAVED_REGS; i++)
+ for (i = 0; i < CALLER_SAVED_REGS; i++) {
mark_reg_not_init(regs, caller_saved[i]);
+ check_reg_arg(env, i, DST_OP_NO_MARK);

Don't we need the same in check_ld_abs() since we treat it similar
to a function call?

+ }

/* update return register */
+ check_reg_arg(env, BPF_REG_0, DST_OP_NO_MARK);
[...]