Re: [PATCH v2 net-next] bpf/verifier: track liveness for pruning
flat view
From: Daniel Borkmann via iovisor-dev <hidden>
Date: 2017-08-15 16:34:05
Also in:
lkml
On 08/15/2017 03:53 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 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-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
[...]
quoted hunk ↗ jump to hunk
@@ -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);
Ah, I oversaw that earlier, this needs to be: s/i/caller_saved[i]/
quoted hunk ↗ jump to hunk
+ } /* update return register */ + check_reg_arg(env, BPF_REG_0, DST_OP_NO_MARK);
We could leave this for clarity, but ...
if (fn->ret_type == RET_INTEGER) {
/* sets type to SCALAR_VALUE */
mark_reg_unknown(regs, BPF_REG_0);[...]
quoted hunk ↗ jump to hunk
/* reset caller saved regs to unreadable */ - 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);
caller_saved[i]
quoted hunk ↗ jump to hunk
+ } /* mark destination R0 register as readable, since it contains - * the value fetched from the packet + * the value fetched from the packet. + * Already marked as written above.
... then it should be here as well. Other option is to leave out both BPF_REG_0 since covered by caller_saved[] already.
quoted hunk ↗ jump to hunk
*/ mark_reg_unknown(regs, BPF_REG_0); return 0;@@ -3194,7 +3236,11 @@ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, bool varlen_map_access, struct idpair *idmap) { - if (memcmp(rold, rcur, sizeof(*rold)) == 0) + if (!(rold->live & REG_LIVE_READ)) + /* explored state didn't use this */ + return true;