* [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification
@ 2018-08-22 19:00 Edward Cree
2018-08-22 19:02 ` [RFC PATCH v2 bpf-next 1/2] bpf/verifier: per-register parent pointers Edward Cree
` (3 more replies)
0 siblings, 4 replies; 12+ messages in thread
From: Edward Cree @ 2018-08-22 19:00 UTC (permalink / raw)
To: ast, daniel; +Cc: netdev
The first patch is a simplification of register liveness tracking by using
a separate parentage chain for each register and stack slot, thus avoiding
the need for logic to handle callee-saved registers when applying read
marks. In the future this idea may be extended to form use-def chains.
The second patch adds information about misc/zero data on the stack to the
state dumps emitted to the log at various points; this information was
found essential in debugging the first patch, and may be useful elsewhere.
Edward Cree (2):
bpf/verifier: per-register parent pointers
bpf/verifier: display non-spill stack slot types in
print_verifier_state
include/linux/bpf_verifier.h | 8 +-
kernel/bpf/verifier.c | 216 ++++++++++++++-----------------------------
2 files changed, 72 insertions(+), 152 deletions(-)
^ permalink raw reply [flat|nested] 12+ messages in thread* [RFC PATCH v2 bpf-next 1/2] bpf/verifier: per-register parent pointers 2018-08-22 19:00 [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Edward Cree @ 2018-08-22 19:02 ` Edward Cree 2018-08-22 19:02 ` [RFC PATCH v2 bpf-next 2/2] bpf/verifier: display non-spill stack slot types in print_verifier_state Edward Cree ` (2 subsequent siblings) 3 siblings, 0 replies; 12+ messages in thread From: Edward Cree @ 2018-08-22 19:02 UTC (permalink / raw) To: ast, daniel; +Cc: netdev By giving each register its own liveness chain, we elide the skip_callee() logic. Instead, each register's parent is the state it inherits from; both check_func_call() and prepare_func_exit() automatically connect reg states to the correct chain since when they copy the reg state across (r1-r5 into the callee as args, and r0 out as the return value) they also copy the parent pointer. Signed-off-by: Edward Cree <ecree@solarflare.com> --- include/linux/bpf_verifier.h | 8 +- kernel/bpf/verifier.c | 184 +++++++++++-------------------------------- 2 files changed, 47 insertions(+), 145 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 38b04f559ad3..b42b60a83e19 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -41,6 +41,7 @@ enum bpf_reg_liveness { }; struct bpf_reg_state { + /* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type; union { /* valid when type == PTR_TO_PACKET */ @@ -59,7 +60,6 @@ struct bpf_reg_state { * came from, when one is tested for != NULL. */ u32 id; - /* Ordering of fields matters. See states_equal() */ /* For scalar types (SCALAR_VALUE), this represents our knowledge of * the actual value. * For pointer types, this represents the variable part of the offset @@ -76,15 +76,15 @@ struct bpf_reg_state { s64 smax_value; /* maximum possible (s64)value */ u64 umin_value; /* minimum possible (u64)value */ u64 umax_value; /* maximum possible (u64)value */ + /* parentage chain for liveness checking */ + struct bpf_reg_state *parent; /* Inside the callee two registers can be both PTR_TO_STACK like * R1=fp-8 and R2=fp-8, but one of them points to this function stack * while another to the caller's stack. To differentiate them 'frameno' * is used which is an index in bpf_verifier_state->frame[] array * pointing to bpf_func_state. - * This field must be second to last, for states_equal() reasons. */ u32 frameno; - /* This field must be last, for states_equal() reasons. */ enum bpf_reg_liveness live; }; @@ -107,7 +107,6 @@ struct bpf_stack_state { */ struct bpf_func_state { struct bpf_reg_state regs[MAX_BPF_REG]; - struct bpf_verifier_state *parent; /* index of call instruction that called into this func */ int callsite; /* stack frame number of this function state from pov of @@ -129,7 +128,6 @@ struct bpf_func_state { struct bpf_verifier_state { /* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES]; - struct bpf_verifier_state *parent; u32 curframe; }; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index ca90679a7fe5..b11d45916fff 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -380,9 +380,9 @@ static int copy_stack_state(struct bpf_func_state *dst, /* do_check() starts with zero-sized stack in struct bpf_verifier_state to * make it consume minimal amount of memory. check_stack_write() access from * the program calls into realloc_func_state() to grow the stack size. - * Note there is a non-zero 'parent' pointer inside bpf_verifier_state - * which this function copies over. It points to previous bpf_verifier_state - * which is never reallocated + * Note there is a non-zero parent pointer inside each reg of bpf_verifier_state + * which this function copies over. It points to corresponding reg in previous + * bpf_verifier_state which is never reallocated */ static int realloc_func_state(struct bpf_func_state *state, int size, bool copy_old) @@ -466,7 +466,6 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state, dst_state->frame[i] = NULL; } dst_state->curframe = src->curframe; - dst_state->parent = src->parent; for (i = 0; i <= src->curframe; i++) { dst = dst_state->frame[i]; if (!dst) { @@ -732,6 +731,7 @@ static void init_reg_state(struct bpf_verifier_env *env, for (i = 0; i < MAX_BPF_REG; i++) { mark_reg_not_init(env, regs, i); regs[i].live = REG_LIVE_NONE; + regs[i].parent = NULL; } /* frame pointer */ @@ -876,74 +876,21 @@ static int check_subprogs(struct bpf_verifier_env *env) return 0; } -static -struct bpf_verifier_state *skip_callee(struct bpf_verifier_env *env, - const struct bpf_verifier_state *state, - struct bpf_verifier_state *parent, - u32 regno) -{ - struct bpf_verifier_state *tmp = NULL; - - /* 'parent' could be a state of caller and - * 'state' could be a state of callee. In such case - * parent->curframe < state->curframe - * and it's ok for r1 - r5 registers - * - * 'parent' could be a callee's state after it bpf_exit-ed. - * In such case parent->curframe > state->curframe - * and it's ok for r0 only - */ - if (parent->curframe == state->curframe || - (parent->curframe < state->curframe && - regno >= BPF_REG_1 && regno <= BPF_REG_5) || - (parent->curframe > state->curframe && - regno == BPF_REG_0)) - return parent; - - if (parent->curframe > state->curframe && - regno >= BPF_REG_6) { - /* for callee saved regs we have to skip the whole chain - * of states that belong to callee and mark as LIVE_READ - * the registers before the call - */ - tmp = parent; - while (tmp && tmp->curframe != state->curframe) { - tmp = tmp->parent; - } - if (!tmp) - goto bug; - parent = tmp; - } else { - goto bug; - } - return parent; -bug: - verbose(env, "verifier bug regno %d tmp %p\n", regno, tmp); - verbose(env, "regno %d parent frame %d current frame %d\n", - regno, parent->curframe, state->curframe); - return NULL; -} - +/* Parentage chain of this register (or stack slot) should take care of all + * issues like callee-saved registers, stack slot allocation time, etc. + */ static int mark_reg_read(struct bpf_verifier_env *env, - const struct bpf_verifier_state *state, - struct bpf_verifier_state *parent, - u32 regno) + const struct bpf_reg_state *state, + struct bpf_reg_state *parent) { bool writes = parent == state->parent; /* Observe write marks */ - if (regno == BPF_REG_FP) - /* We don't need to worry about FP liveness because it's read-only */ - return 0; - while (parent) { /* if read wasn't screened by an earlier write ... */ - if (writes && state->frame[state->curframe]->regs[regno].live & REG_LIVE_WRITTEN) + if (writes && state->live & REG_LIVE_WRITTEN) break; - parent = skip_callee(env, state, parent, regno); - if (!parent) - return -EFAULT; /* ... then we depend on parent's value */ - parent->frame[parent->curframe]->regs[regno].live |= REG_LIVE_READ; + parent->live |= REG_LIVE_READ; state = parent; parent = state->parent; writes = true; @@ -969,7 +916,10 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno, verbose(env, "R%d !read_ok\n", regno); return -EACCES; } - return mark_reg_read(env, vstate, vstate->parent, regno); + /* We don't need to worry about FP liveness because it's read-only */ + if (regno != BPF_REG_FP) + return mark_reg_read(env, ®s[regno], + regs[regno].parent); } else { /* check whether register used as dest operand can be written to */ if (regno == BPF_REG_FP) { @@ -1080,8 +1030,8 @@ static int check_stack_write(struct bpf_verifier_env *env, } else { u8 type = STACK_MISC; - /* regular write of data into stack */ - state->stack[spi].spilled_ptr = (struct bpf_reg_state) {}; + /* regular write of data into stack destroys any spilled ptr */ + state->stack[spi].spilled_ptr.type = NOT_INIT; /* only mark the slot as written if all 8 bytes were written * otherwise read propagation may incorrectly stop too soon @@ -1106,61 +1056,6 @@ static int check_stack_write(struct bpf_verifier_env *env, return 0; } -/* registers of every function are unique and mark_reg_read() propagates - * the liveness in the following cases: - * - from callee into caller for R1 - R5 that were used as arguments - * - from caller into callee for R0 that used as result of the call - * - from caller to the same caller skipping states of the callee for R6 - R9, - * since R6 - R9 are callee saved by implicit function prologue and - * caller's R6 != callee's R6, so when we propagate liveness up to - * parent states we need to skip callee states for R6 - R9. - * - * stack slot marking is different, since stacks of caller and callee are - * accessible in both (since caller can pass a pointer to caller's stack to - * callee which can pass it to another function), hence mark_stack_slot_read() - * has to propagate the stack liveness to all parent states at given frame number. - * Consider code: - * f1() { - * ptr = fp - 8; - * *ptr = ctx; - * call f2 { - * .. = *ptr; - * } - * .. = *ptr; - * } - * First *ptr is reading from f1's stack and mark_stack_slot_read() has - * to mark liveness at the f1's frame and not f2's frame. - * Second *ptr is also reading from f1's stack and mark_stack_slot_read() has - * to propagate liveness to f2 states at f1's frame level and further into - * f1 states at f1's frame level until write into that stack slot - */ -static void mark_stack_slot_read(struct bpf_verifier_env *env, - const struct bpf_verifier_state *state, - struct bpf_verifier_state *parent, - int slot, int frameno) -{ - bool writes = parent == state->parent; /* Observe write marks */ - - while (parent) { - if (parent->frame[frameno]->allocated_stack <= slot * BPF_REG_SIZE) - /* since LIVE_WRITTEN mark is only done for full 8-byte - * write the read marks are conservative and parent - * state may not even have the stack allocated. In such case - * end the propagation, since the loop reached beginning - * of the function - */ - break; - /* if read wasn't screened by an earlier write ... */ - if (writes && state->frame[frameno]->stack[slot].spilled_ptr.live & REG_LIVE_WRITTEN) - break; - /* ... then we depend on parent's value */ - parent->frame[frameno]->stack[slot].spilled_ptr.live |= REG_LIVE_READ; - state = parent; - parent = state->parent; - writes = true; - } -} - static int check_stack_read(struct bpf_verifier_env *env, struct bpf_func_state *reg_state /* func where register points to */, int off, int size, int value_regno) @@ -1198,8 +1093,8 @@ static int check_stack_read(struct bpf_verifier_env *env, */ state->regs[value_regno].live |= REG_LIVE_WRITTEN; } - mark_stack_slot_read(env, vstate, vstate->parent, spi, - reg_state->frameno); + mark_reg_read(env, ®_state->stack[spi].spilled_ptr, + reg_state->stack[spi].spilled_ptr.parent); return 0; } else { int zeros = 0; @@ -1215,8 +1110,8 @@ static int check_stack_read(struct bpf_verifier_env *env, off, i, size); return -EACCES; } - mark_stack_slot_read(env, vstate, vstate->parent, spi, - reg_state->frameno); + mark_reg_read(env, ®_state->stack[spi].spilled_ptr, + reg_state->stack[spi].spilled_ptr.parent); if (value_regno >= 0) { if (zeros == size) { /* any size read into register is zero extended, @@ -1908,8 +1803,8 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno, /* reading any byte out of 8-byte 'spill_slot' will cause * the whole slot to be marked as 'read' */ - mark_stack_slot_read(env, env->cur_state, env->cur_state->parent, - spi, state->frameno); + mark_reg_read(env, &state->stack[spi].spilled_ptr, + state->stack[spi].spilled_ptr.parent); } return update_stack_depth(env, state, off); } @@ -2366,11 +2261,13 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn, state->curframe + 1 /* frameno within this callchain */, subprog /* subprog number within this prog */); - /* copy r1 - r5 args that callee can access */ + /* copy r1 - r5 args that callee can access. The copy includes parent + * pointers, which connects us up to the liveness chain + */ for (i = BPF_REG_1; i <= BPF_REG_5; i++) callee->regs[i] = caller->regs[i]; - /* after the call regsiters r0 - r5 were scratched */ + /* after the call registers r0 - r5 were scratched */ for (i = 0; i < CALLER_SAVED_REGS; i++) { mark_reg_not_init(env, caller->regs, caller_saved[i]); check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); @@ -4370,7 +4267,7 @@ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, /* explored state didn't use this */ return true; - equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, frameno)) == 0; + equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0; if (rold->type == PTR_TO_STACK) /* two stack pointers are equal only if they're pointing to @@ -4603,7 +4500,7 @@ static bool states_equal(struct bpf_verifier_env *env, * equivalent state (jump target or such) we didn't arrive by the straight-line * code, so read marks in the state must propagate to the parent regardless * of the state's write marks. That's what 'parent == state->parent' comparison - * in mark_reg_read() and mark_stack_slot_read() is for. + * in mark_reg_read() is for. */ static int propagate_liveness(struct bpf_verifier_env *env, const struct bpf_verifier_state *vstate, @@ -4624,7 +4521,8 @@ static int propagate_liveness(struct bpf_verifier_env *env, if (vparent->frame[vparent->curframe]->regs[i].live & REG_LIVE_READ) continue; if (vstate->frame[vstate->curframe]->regs[i].live & REG_LIVE_READ) { - err = mark_reg_read(env, vstate, vparent, i); + err = mark_reg_read(env, &vstate->frame[vstate->curframe]->regs[i], + &vparent->frame[vstate->curframe]->regs[i]); if (err) return err; } @@ -4639,7 +4537,8 @@ static int propagate_liveness(struct bpf_verifier_env *env, if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ) continue; if (state->stack[i].spilled_ptr.live & REG_LIVE_READ) - mark_stack_slot_read(env, vstate, vparent, i, frame); + mark_reg_read(env, &state->stack[i].spilled_ptr, + &parent->stack[i].spilled_ptr); } } return err; @@ -4649,7 +4548,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) { struct bpf_verifier_state_list *new_sl; struct bpf_verifier_state_list *sl; - struct bpf_verifier_state *cur = env->cur_state; + struct bpf_verifier_state *cur = env->cur_state, *new; int i, j, err; sl = env->explored_states[insn_idx]; @@ -4691,16 +4590,18 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) return -ENOMEM; /* add new state to the head of linked list */ - err = copy_verifier_state(&new_sl->state, cur); + new = &new_sl->state; + err = copy_verifier_state(new, cur); if (err) { - free_verifier_state(&new_sl->state, false); + free_verifier_state(new, false); kfree(new_sl); return err; } new_sl->next = env->explored_states[insn_idx]; env->explored_states[insn_idx] = new_sl; /* connect new state to parentage chain */ - cur->parent = &new_sl->state; + for (i = 0; i < BPF_REG_FP; i++) + cur_regs(env)[i].parent = &new->frame[new->curframe]->regs[i]; /* clear write marks in current state: the writes we did are not writes * our child did, so they don't screen off its reads from us. * (There are no read marks in current state, because reads always mark @@ -4713,9 +4614,13 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) /* all stack frames are accessible from callee, clear them all */ for (j = 0; j <= cur->curframe; j++) { struct bpf_func_state *frame = cur->frame[j]; + struct bpf_func_state *newframe = new->frame[j]; - for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) + for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) { frame->stack[i].spilled_ptr.live = REG_LIVE_NONE; + frame->stack[i].spilled_ptr.parent = + &newframe->stack[i].spilled_ptr; + } } return 0; } @@ -4734,7 +4639,6 @@ static int do_check(struct bpf_verifier_env *env) if (!state) return -ENOMEM; state->curframe = 0; - state->parent = NULL; state->frame[0] = kzalloc(sizeof(struct bpf_func_state), GFP_KERNEL); if (!state->frame[0]) { kfree(state); ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [RFC PATCH v2 bpf-next 2/2] bpf/verifier: display non-spill stack slot types in print_verifier_state 2018-08-22 19:00 [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Edward Cree 2018-08-22 19:02 ` [RFC PATCH v2 bpf-next 1/2] bpf/verifier: per-register parent pointers Edward Cree @ 2018-08-22 19:02 ` Edward Cree 2018-08-30 2:18 ` [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Alexei Starovoitov 2018-09-26 22:16 ` Jiong Wang 3 siblings, 0 replies; 12+ messages in thread From: Edward Cree @ 2018-08-22 19:02 UTC (permalink / raw) To: ast, daniel; +Cc: netdev If a stack slot does not hold a spilled register (STACK_SPILL), then each of its eight bytes could potentially have a different slot_type. This information can be important for debugging, and previously we either did not print anything for the stack slot, or just printed fp-X=0 in the case where its first byte was STACK_ZERO. Instead, print eight characters with either 0 (STACK_ZERO), m (STACK_MISC) or ? (STACK_INVALID) for any stack slot which is neither STACK_SPILL nor entirely STACK_INVALID. Signed-off-by: Edward Cree <ecree@solarflare.com> --- kernel/bpf/verifier.c | 32 +++++++++++++++++++++++++------- 1 file changed, 25 insertions(+), 7 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index b11d45916fff..2f4b52cf864c 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -263,6 +263,13 @@ static const char * const reg_type_str[] = { [PTR_TO_PACKET_END] = "pkt_end", }; +static char slot_type_char[] = { + [STACK_INVALID] = '?', + [STACK_SPILL] = 'r', + [STACK_MISC] = 'm', + [STACK_ZERO] = '0', +}; + static void print_liveness(struct bpf_verifier_env *env, enum bpf_reg_liveness live) { @@ -349,15 +356,26 @@ static void print_verifier_state(struct bpf_verifier_env *env, } } for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { - if (state->stack[i].slot_type[0] == STACK_SPILL) { - verbose(env, " fp%d", - (-i - 1) * BPF_REG_SIZE); - print_liveness(env, state->stack[i].spilled_ptr.live); + char types_buf[BPF_REG_SIZE + 1]; + bool valid = false; + int j; + + for (j = 0; j < BPF_REG_SIZE; j++) { + if (state->stack[i].slot_type[j] != STACK_INVALID) + valid = true; + types_buf[j] = slot_type_char[ + state->stack[i].slot_type[j]]; + } + types_buf[BPF_REG_SIZE] = 0; + if (!valid) + continue; + verbose(env, " fp%d", (-i - 1) * BPF_REG_SIZE); + print_liveness(env, state->stack[i].spilled_ptr.live); + if (state->stack[i].slot_type[0] == STACK_SPILL) verbose(env, "=%s", reg_type_str[state->stack[i].spilled_ptr.type]); - } - if (state->stack[i].slot_type[0] == STACK_ZERO) - verbose(env, " fp%d=0", (-i - 1) * BPF_REG_SIZE); + else + verbose(env, "=%s", types_buf); } verbose(env, "\n"); } ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-08-22 19:00 [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Edward Cree 2018-08-22 19:02 ` [RFC PATCH v2 bpf-next 1/2] bpf/verifier: per-register parent pointers Edward Cree 2018-08-22 19:02 ` [RFC PATCH v2 bpf-next 2/2] bpf/verifier: display non-spill stack slot types in print_verifier_state Edward Cree @ 2018-08-30 2:18 ` Alexei Starovoitov 2018-08-31 15:50 ` Edward Cree 2018-09-26 22:16 ` Jiong Wang 3 siblings, 1 reply; 12+ messages in thread From: Alexei Starovoitov @ 2018-08-30 2:18 UTC (permalink / raw) To: Edward Cree; +Cc: ast, daniel, netdev On Wed, Aug 22, 2018 at 08:00:46PM +0100, Edward Cree wrote: > The first patch is a simplification of register liveness tracking by using > a separate parentage chain for each register and stack slot, thus avoiding > the need for logic to handle callee-saved registers when applying read > marks. In the future this idea may be extended to form use-def chains. > The second patch adds information about misc/zero data on the stack to the > state dumps emitted to the log at various points; this information was > found essential in debugging the first patch, and may be useful elsewhere. I think this set is a great improvement in liveness tracking, so depsite seeing the issues I applied it to bpf-next. I think it's a better base to continue debugging. In particular: 1. we have instability issue in the verifier. from time to time the verifier goes to process extra 7 instructions on one of the cilium tests. This was happening before and after this set. 2. there is a nice improvement in number of processed insns with this set, but the difference I cannot explain, hence it has to debugged. In theory the liveness rewrite shouldn't cause the difference in processed insns. If not for the issue 1 I would argue that the issue 2 means that the set has to be debugged before going in, but since the verifier is unstable it's better to debug from this base with this patch set applied (because it greatly simplifies liveness and adds additional debug in patch2) and once we figure out the issue 1, I hope, the issue 2 will be resolved automatically. The numbers on cilium bpf programs: before1 before2 after1 after2 bpf_lb-DLB_L3.o 2003 2003 2003 2003 bpf_lb-DLB_L4.o 3173 3173 3173 3173 bpf_lb-DUNKNOWN.o 1080 1080 1080 1080 bpf_lxc-DDROP_ALL.o 29587 29587 29587 29587 bpf_lxc-DUNKNOWN.o 37204 37211 36926 36933 bpf_netdev.o 11283 11283 11188 11188 bpf_overlay.o 6679 6679 6679 6679 bpf_lcx_jit.o 39657 39657 39561 39561 notice how bpf_lxc-DUNKNOWN.o fluctuates with +7 before and after. That is issue 1. bpf_lxc-DUNKNOWN.o, bpf_netdev.o, and bpf_lcx_jit.o have small improvements. That is issue 2. To reproduce above numbers clone this repo: https://github.com/4ast/bpf_cilium_test and run .sh. The .o files in there are pretty old cilium bpf programs. I kept them frozen and didn't recompile for more than a year to keep stable base line and track the progress of the verifier in 'processed insns'. Thanks ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-08-30 2:18 ` [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Alexei Starovoitov @ 2018-08-31 15:50 ` Edward Cree 0 siblings, 0 replies; 12+ messages in thread From: Edward Cree @ 2018-08-31 15:50 UTC (permalink / raw) To: Alexei Starovoitov; +Cc: ast, daniel, netdev On 30/08/18 03:18, Alexei Starovoitov wrote: > I think it's a better base to continue debugging. > In particular: > 1. we have instability issue in the verifier. > from time to time the verifier goes to process extra 7 instructions on one > of the cilium tests. This was happening before and after this set. I can't reproduce this; I always get 36926. Can you try recording the verifier log and diff the output between the two cases? > 2. there is a nice improvement in number of processed insns with this set, > but the difference I cannot explain, hence it has to debugged. > In theory the liveness rewrite shouldn't cause the difference in processed insns. I shall attack this with the same methods I used for the other delta. Since that one turned out to be a real bug in the patch, I'm not so sanguine as to dismiss this one as probably connected to issue 1. -Ed ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-08-22 19:00 [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Edward Cree ` (2 preceding siblings ...) 2018-08-30 2:18 ` [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Alexei Starovoitov @ 2018-09-26 22:16 ` Jiong Wang 2018-09-28 13:36 ` Edward Cree 3 siblings, 1 reply; 12+ messages in thread From: Jiong Wang @ 2018-09-26 22:16 UTC (permalink / raw) To: Edward Cree, ast, daniel; +Cc: netdev On 22/08/2018 20:00, Edward Cree wrote: > The first patch is a simplification of register liveness tracking by using > a separate parentage chain for each register and stack slot, thus avoiding > the need for logic to handle callee-saved registers when applying read > marks. In the future this idea may be extended to form use-def chains. Interesting. This could potentially help efficient code-gen for 32-bit architectures and I had been thinking some implementations along this line and would like to have a discussion. Program description === It will be good if we could know one instruction is safe to operate on low 32-bit sub-register only. If this is true: - 32-bit arches could save some code-gen. - 64-bit arches could utilize 32-bit sub-register instructions. Algorithm === Based on the current verifier code-path-walker, it looks to me we could get 32-bit safety information using the following algorithm: 1. assume all instructions operate on 32-bit sub-register initially. 2. link each insn to insns which define its use. 3. for a register use, if it is a 64-bit write back to memory, or if it is a comparison-then-jump based on 64-bit value, or if it is a right shift, then consider the use is a 64-bit use, then all its define insns and their parents define insns should be marked as need full 64-bit operation. 4. currently, register read (REG_LIVE_READ) will be propagated to parent state when path prune happened, and REG_LIVE_WRITTEN would screen off such propagation. We need to propagate 64-bit mark in similar way, but REG_LIVE_WRITTEN shouldn't screen off backward 64-bit mark propagation if the written reg also used as source reg (this has raised REG_LIVE_READ propagation but it is not necessarily indicating 64-bit read) in the same instruction. Implementation === And it seems there could be an implementation based on current liveness tracking infrastructure without dramatic change. 1. instruction level use->def chain - new active_defs array for each call frame to record which insn the active define of one register comes from. callee copies active_defs from caller for argument registers only, and copies active_def of R0 to caller when exit. struct bpf_func_state { ... s16 active_defs[__MAX_BPF_REG]; - new use->def chains for each instruction. one eBPF insn could have two uses at maximum. also one new boolean "full_ref_def" added to keep the final 32-bit safety information. it will be true if this instruction needs to operate on full 64-bit. bpf_insn_aux_data { ... struct { s16 def[2]; bool full_ref_def; }; 2. Inside mark_reg_read, split SRC_OP to SRC0_OP/SRC1_OP/SRC_OP_64/SRC1_OP_64 to indicate one register read if from the first or second use slot of this instruction, and to indicate whether the read is on full 64-bit which will only be true if the read is for 64-bit write back to memory, or 64-bit comparison-then-jump, or bit right shift means 64-bit. Build use->def chain for any read, but do 64-bit backward propagation for 64-bit read only. The propagation is to set full_ref_def to true for def and parent defs of the 64-bit read. 3. Need new bpf_reg_liveness enum, REG_LIVE_READ64 to indicate there is 64-bit access to one register in the pruned path, and need REG_LIVE_WRITTEN64 to indicate a write that is REG_LIVE_WRITTEN but should not screen backward propagate 64-bit read info. #define REG_LIVE_NONE 0 #define REG_LIVE_READ BIT(0) #define REG_LIVE_READ64 BIT(1) #define REG_LIVE_WRITTEN BIT(2) #define REG_LIVE_WRITTEN64 BIT(3) I might have missed something in above thoughts, would appreciate reviews and suggestions. I will also send out some concrete patches later. Regards, Jiong ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-09-26 22:16 ` Jiong Wang @ 2018-09-28 13:36 ` Edward Cree 2018-10-03 15:36 ` Jiong Wang 0 siblings, 1 reply; 12+ messages in thread From: Edward Cree @ 2018-09-28 13:36 UTC (permalink / raw) To: Jiong Wang, ast, daniel; +Cc: netdev On 26/09/18 23:16, Jiong Wang wrote: > On 22/08/2018 20:00, Edward Cree wrote: >> In the future this idea may be extended to form use-def chains. > > 1. instruction level use->def chain > > - new use->def chains for each instruction. one eBPF insn could have two > uses at maximum. I was thinking of something a lot weaker/simpler, just making ld rX, rY copy rY.parent into rX.parent and not read-mark rY (whereas actual arithmetic, pointer deref etc. would still create read marks). But what you've described sounds interesting; perhaps it would also help later with loop-variable handling? -Ed ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-09-28 13:36 ` Edward Cree @ 2018-10-03 15:36 ` Jiong Wang 2018-10-03 15:59 ` Alexei Starovoitov 2018-10-04 17:35 ` Edward Cree 0 siblings, 2 replies; 12+ messages in thread From: Jiong Wang @ 2018-10-03 15:36 UTC (permalink / raw) To: Edward Cree, ast, daniel; +Cc: netdev On 28/09/2018 14:36, Edward Cree wrote: > On 26/09/18 23:16, Jiong Wang wrote: >> On 22/08/2018 20:00, Edward Cree wrote: >>> In the future this idea may be extended to form use-def chains. >> >> 1. instruction level use->def chain >> >> - new use->def chains for each instruction. one eBPF insn could have two >> uses at maximum. > I was thinking of something a lot weaker/simpler, just making > ld rX, rY > copy rY.parent into rX.parent and not read-mark rY (whereas actual > arithmetic, pointer deref etc. would still create read marks). Thanks for the feedback Edward. > But what you've described sounds interesting; perhaps it would also > help later with loop-variable handling? Haven't considered how to use this for loop-variable handling, guess you mean applying what I have described to your previous loop detection RFC? I will look into your RFC later. At the moment the design of the use->def chain is mainly to optimize 32-bit code-gen. I was about to satisfied with a local implementation and to share it to ML for further discussion. However, when manually check the optimization result on testcase with medium size (~1000 eBPF insns) and proper complexity (make sure path prunes etc are triggered inside verifier), I found the code-gen doesn't meet my expectation. For example, for the following sequence, insn at 25 should operate on full-64 bit but I found it is marked as 32-bit safe. 25: r7 = 1 26: if r4 > r8 goto +1200 <L> 27: r1 = *(u8 *)(r1 + 0) 28: r1 &= 15 29: r7 = 1 ... L: 1227: r0 = r7 1228: exit As described at previous email, the algorithm assume all insns are 32-bit safe first, then start to insns back to "64-bit" if there is any 64-bit use found for a insn. Insn 25 is defining r7 which is used at the 1227 where its value propagated to r0 and then r0 is implicitly used at insn 1228 as it is a exit from main function to external. For above example, as we don't know the external use of r0 at 1228 (exit from main to external), so r0 is treated as 64-bit implicit use. The define is at 1227, so insn 1227 is marked as "64-bit". The "64-bit" attribute should propagate to source register operand through register move and arithmetic, so r7 at insn 1227 is a "64-bit" use and should make its definition instruction, insn 25, marked as "64-bit". This is my thinking of how insn 25 should be marked. Now this hasn't happened. I am still debugging the root cause, but kind of feel "64-bit" attribute propagation is the issue, it seems to me it can't be nicely integrated into the existing register read/write propagation infrastructure. For example, for a slightly more complex sequence which is composed of three states: State A ... 10: r6 = *(u32 *)(r10 - 4) 11: r7 = *(u32 *)(r10 - 8) 12: *(u64 *)(r10 - 16) = r6 13: *(u64 *)(r10 - 24) = r7 State B 14: r6 += 1 15: r7 += r6 16: *(u32 *)(r10 - 28) = r7 State C ... 17: r3 += r7 18: r4 = 1 19: *(u64 *)(r10 - 32) = r3 20: *(u64 *)(r10 - 40) = r4 State A is parent of state B which is parent of state C. Inside state C, at insn 20, r4 is a 64-bit read/use, so its define at 18 is marked as "64-bit". There is no register source at 18, so "64-bit" attribute propagation is stopped. Then at insn 19, r3 is a 64-bit read/use, so its define at 17 is marked as "64-bit" read/use. Insn 17 has two register sources, r3 and r7, they become "64-bit" now, and their definition should be marked as "64-bit". Now if the definition of r3 or r7 comes from parent state, then the parent state should receive a "REG_LIVE_READ64", this is necessary if later another path reaches state C and triggers prune path, for which case that path should know there is "64-bit" use inside state C on some registers, and should use this information to mark "64-bit" insn. If the definition of r3 or r7 is still inside state C, we need to keep walking up the instruction sequences, and propagate "64-bit" attribute upward until it goes beyond the state C. The above propagation logic is quite different from existing register read/write propagation. For the latter, a write just screen up all following read, and a read would propagate directly to its parent is there is not previous write, no instruction analysis is required. I am just describing what I have run into and trying to resolve, any thoughts and suggestions are appreciated. Regards, Jiong ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-10-03 15:36 ` Jiong Wang @ 2018-10-03 15:59 ` Alexei Starovoitov 2018-10-03 16:53 ` Jiong Wang 2018-10-04 17:35 ` Edward Cree 1 sibling, 1 reply; 12+ messages in thread From: Alexei Starovoitov @ 2018-10-03 15:59 UTC (permalink / raw) To: Jiong Wang; +Cc: Edward Cree, ast, daniel, netdev On Wed, Oct 03, 2018 at 04:36:31PM +0100, Jiong Wang wrote: > On 28/09/2018 14:36, Edward Cree wrote: > > On 26/09/18 23:16, Jiong Wang wrote: > >> On 22/08/2018 20:00, Edward Cree wrote: > >>> In the future this idea may be extended to form use-def chains. > >> > >> 1. instruction level use->def chain > >> > >> - new use->def chains for each instruction. one eBPF insn could have > two > >> uses at maximum. > > I was thinking of something a lot weaker/simpler, just making > > ld rX, rY > > copy rY.parent into rX.parent and not read-mark rY (whereas actual > > arithmetic, pointer deref etc. would still create read marks). > > Thanks for the feedback Edward. > > > But what you've described sounds interesting; perhaps it would also > > help later with loop-variable handling? > > Haven't considered how to use this for loop-variable handling, guess you > mean > applying what I have described to your previous loop detection RFC? I will > look > into your RFC later. > > At the moment the design of the use->def chain is mainly to optimize 32-bit > code-gen. I was about to satisfied with a local implementation and to share > it > to ML for further discussion. However, when manually check the optimization > result on testcase with medium size (~1000 eBPF insns) and proper complexity > (make sure path prunes etc are triggered inside verifier), I found the > code-gen > doesn't meet my expectation. > > For example, for the following sequence, insn at 25 should operate on > full-64 > bit but I found it is marked as 32-bit safe. > > 25: r7 = 1 > 26: if r4 > r8 goto +1200 <L> > 27: r1 = *(u8 *)(r1 + 0) > 28: r1 &= 15 > 29: r7 = 1 > ... > > L: > 1227: r0 = r7 > 1228: exit > > As described at previous email, the algorithm assume all insns are 32-bit > safe > first, then start to insns back to "64-bit" if there is any 64-bit use found > for a insn. > > Insn 25 is defining r7 which is used at the 1227 where its value propagated > to > r0 and then r0 is implicitly used at insn 1228 as it is a exit from main > function to external. > > For above example, as we don't know the external use of r0 at 1228 (exit > from > main to external), so r0 is treated as 64-bit implicit use. The define is at > 1227, so insn 1227 is marked as "64-bit". The "64-bit" attribute should > propagate to source register operand through register move and arithmetic, > so > r7 at insn 1227 is a "64-bit" use and should make its definition > instruction, > insn 25, marked as "64-bit". This is my thinking of how insn 25 should be > marked. all makes sense to me. > Now this hasn't happened. I am still debugging the root cause, but kind of > feel > "64-bit" attribute propagation is the issue, it seems to me it can't be > nicely > integrated into the existing register read/write propagation infrastructure. may be share your patches that modify the liveness propagation? > For > example, for a slightly more complex sequence which is composed of three > states: > > State A > ... > 10: r6 = *(u32 *)(r10 - 4) > 11: r7 = *(u32 *)(r10 - 8) > 12: *(u64 *)(r10 - 16) = r6 > 13: *(u64 *)(r10 - 24) = r7 > > State B > 14: r6 += 1 > 15: r7 += r6 > 16: *(u32 *)(r10 - 28) = r7 > > State C > ... > 17: r3 += r7 > 18: r4 = 1 > 19: *(u64 *)(r10 - 32) = r3 > 20: *(u64 *)(r10 - 40) = r4 > > State A is parent of state B which is parent of state C. > > Inside state C, at insn 20, r4 is a 64-bit read/use, so its define at 18 is > marked as "64-bit". There is no register source at 18, so "64-bit" attribute > propagation is stopped. > > Then at insn 19, r3 is a 64-bit read/use, so its define at 17 is marked as > "64-bit" read/use. Insn 17 has two register sources, r3 and r7, they become > "64-bit" now, and their definition should be marked as "64-bit". > > Now if the definition of r3 or r7 comes from parent state, then the parent ... the definition of r3 _and_ r7 ... both need to propagate up with your algo, right? > state > should receive a "REG_LIVE_READ64", this is necessary if later another path > reaches state C and triggers prune path, for which case that path should > know > there is "64-bit" use inside state C on some registers, and should use this > information to mark "64-bit" insn. > > If the definition of r3 or r7 is still inside state C, we need to keep > walking > up the instruction sequences, and propagate "64-bit" attribute upward until > it > goes beyond the state C. > > The above propagation logic is quite different from existing register > read/write > propagation. > For the latter, a write just screen up all following read, and > a > read would propagate directly to its parent is there is not previous write, > no > instruction analysis is required. correct. with such algo REG_LIVE_WRITTEN shouldn't be screening the propagation. I think the patches will discuss the algo. Also I think the initial state of 'everything is 32-bit safe' and make marks to enforce 64-bit-ness is a dangerous algorithmic choice. Why not to start at a safer state where everything is 64-bit and work backward to find out which ones can be 32-bit? That will be safer algo in case there are issues with bit like you described in above. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-10-03 15:59 ` Alexei Starovoitov @ 2018-10-03 16:53 ` Jiong Wang 2018-10-08 20:18 ` Jiong Wang 0 siblings, 1 reply; 12+ messages in thread From: Jiong Wang @ 2018-10-03 16:53 UTC (permalink / raw) To: Alexei Starovoitov; +Cc: Edward Cree, ast, daniel, netdev On 03/10/2018 16:59, Alexei Starovoitov wrote: > On Wed, Oct 03, 2018 at 04:36:31PM +0100, Jiong Wang wrote: <snip...> >> Now this hasn't happened. I am still debugging the root cause, but kind of >> feel >> "64-bit" attribute propagation is the issue, it seems to me it can't be >> nicely >> integrated into the existing register read/write propagation infrastructure. > > may be share your patches that modify the liveness propagation? OK, I will share it after some clean up. >> For >> example, for a slightly more complex sequence which is composed of three >> states: >> >> State A >> ... >> 10: r6 = *(u32 *)(r10 - 4) >> 11: r7 = *(u32 *)(r10 - 8) >> 12: *(u64 *)(r10 - 16) = r6 >> 13: *(u64 *)(r10 - 24) = r7 >> >> State B >> 14: r6 += 1 >> 15: r7 += r6 >> 16: *(u32 *)(r10 - 28) = r7 >> >> State C >> ... >> 17: r3 += r7 >> 18: r4 = 1 >> 19: *(u64 *)(r10 - 32) = r3 >> 20: *(u64 *)(r10 - 40) = r4 >> >> State A is parent of state B which is parent of state C. >> >> Inside state C, at insn 20, r4 is a 64-bit read/use, so its define at 18 is >> marked as "64-bit". There is no register source at 18, so "64-bit" attribute >> propagation is stopped. >> >> Then at insn 19, r3 is a 64-bit read/use, so its define at 17 is marked as >> "64-bit" read/use. Insn 17 has two register sources, r3 and r7, they become >> "64-bit" now, and their definition should be marked as "64-bit". >> >> Now if the definition of r3 or r7 comes from parent state, then the parent > > ... the definition of r3 _and_ r7 ... > both need to propagate up with your algo, right? Yes, all sources of insn 17, both r3 and r7. >> state >> should receive a "REG_LIVE_READ64", this is necessary if later another path >> reaches state C and triggers prune path, for which case that path should >> know >> there is "64-bit" use inside state C on some registers, and should use this >> information to mark "64-bit" insn. >> >> If the definition of r3 or r7 is still inside state C, we need to keep >> walking >> up the instruction sequences, and propagate "64-bit" attribute upward until >> it >> goes beyond the state C. >> >> The above propagation logic is quite different from existing register >> read/write propagation. >> For the latter, a write just screen up all following read, and a >> read would propagate directly to its parent is there is not previous write, >> no instruction analysis is required. > > correct. > with such algo REG_LIVE_WRITTEN shouldn't be screening the propagation. > > I think the patches will discuss the algo. > Also I think the initial state of 'everything is 32-bit safe' > and make marks to enforce 64-bit-ness is a dangerous algorithmic choice. Indeed, and I am actually thinking the same thing ... > Why not to start at a safer state where everything is 64-bit > and work backward to find out which ones can be 32-bit? > That will be safer algo in case there are issues with bit like > you described in above. ... but I failed to find a algo works on making initial state of "everything is 64-bit". I haven't figured out a way to check that all use of one definition are 32-bit on all possible code paths, which looks to me is a must for one insn marked as 32-bit safe. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-10-03 16:53 ` Jiong Wang @ 2018-10-08 20:18 ` Jiong Wang 0 siblings, 0 replies; 12+ messages in thread From: Jiong Wang @ 2018-10-08 20:18 UTC (permalink / raw) To: Alexei Starovoitov; +Cc: Edward Cree, ast, daniel, netdev On 03/10/2018 17:53, Jiong Wang wrote: > On 03/10/2018 16:59, Alexei Starovoitov wrote: >> On Wed, Oct 03, 2018 at 04:36:31PM +0100, Jiong Wang wrote: > <snip...> >>> Now this hasn't happened. I am still debugging the root cause, but kind of >>> feel >>> "64-bit" attribute propagation is the issue, it seems to me it can't be >>> nicely >>> integrated into the existing register read/write propagation infrastructure. >> >> may be share your patches that modify the liveness propagation? > > OK, I will share it after some clean up. Have done more experiments on the algo, and finally got something passed my local tests. bpf selftest passed as well except several test_verifier failures due to some corner cases I guess, will have a look later. In these test, x86-64 is using the 32-bit information. In the insn loop inside sanitize_dead_code, once an insn is not marked as 64-bit and if it is ALU64, it will then be changed to ALU32. When enable tracking using printk, I could see quite a few ALU64 instructions really are rewritten into ALU32, so tests like test_l4lb runs OK looks like a positive signal of the correctness. The algo separates the problem into two steps. - First, assume there is no code path prune and all code paths will be walked through. In this case, if we could propagate 64-bit info backward along the use-def chains for all paths walked, one insn must will be marked as 64-bit correctly. Finish this step requires building use-def chain, and it is done in the following way: 1. each insn could have two explicit uses, so add two chain fields in bpf_insn_aux_data. 2. we need finer enum to describe register use, so split SRC_OP into SRC_OP_0, SRC_OP64_0, SRC_OP_1, SRC_OP64_1 to indicate the source is the first/second source and whether it is a 64-bit source. 3. create the chain at check_reg_arg which is exactly covering all register use sites. The function to create the chain is link_reg_to_def. 4. when creating the chain, if a source is a 64-bit source, also propagating the information backward along use-def chain straight away. This is done in mark_reg_read which further calls the new function "mark_insn_64bit" which is doing the real job. "mark_insn_64bit" fetches the def insn for the 64-bit source, and further marks the def insns of its sources as 64-bit. This will be repeated until the whole use-def chain consumed. 5. by use-def chain described above, if there is no code path prune, one insn must have been marked as 64-bit when it's result has 64-bit use. 6. helper call causing implicit reg use and must be conservative treated as 64-bit use, bpf-to-bpf function call has insn connected by use-def so doesn't need to make that conservative assumption. - Second, to handle code path prune, define new liveness enum REG_LIVE_READ64 and REG_LIVE_UNIQUE_WRITTEN. The latter will only be set if reg_arg_type is the new U_DST_OP or U_DST_OP_NO_MARK, and REG_LIVE_READ64 will be set if one 64-bit read is not screened off by REG_LIVE_UNIQUE_WRITTEN. The thought is 64-bit use info will only be screened off if the dst register is unique in all register operands, meaning not the same as any source. For example, insn 18 below will screen off r4 64-bit propagation. 17: r3 += r7 18: r4 = 1 19: *(u64 *)(r10 - 32) = r3 20: *(u64 *)(r10 - 40) = r4 So, U_DST_OP/U_DST_OP_NO_MARK have been introduced to differentiate with DST_OP/DST_OP_NO_MARK. Inside check_reg_arg, checks are done on dst_reg, and would pass U_DST_* as reg_arg_type when it is unique. U_DST_* then will set liveness to REG_LIVE_UNIQUE_WRITTEN. In side mark_reg_read, if one 64-bit read is not screened off by REG_LIVE_UNIQUE_WRITTEN, then REG_LIVE_READ64 will be set in the reg_state. REG_LIVE_READ64 further triggers propagating downstream 64-bit uses from the pruned paths into the current path inside propagate_liveness when path prune happened. Compared with propagating REG_LIVE_READ, propagating REG_LIVE_READ64 needs more work. Because one 64-bit read could indicating more than one registers are 64-bit. For example, insn 19 above shows r3 is 64-bit source, so its define at insn 17 are 64-bit, then all sources of insn 17 must be 64-bit, meaning both r3 and r7 are 64-bit. Therefore, REG_LIVE_READ64 needs to be propagated on both r3 and r7 upward along the register parentage chain. During walking def-use chain, we record all such affected reg_state, and propagate REG_LIVE_READ64 for all of them. This logic is done inside mark_insn_64bit as well. - For short, the implementation treating the new 64-bit info (REG_LIVE_READ64) propagation the same as REG_LIVE_READ propagation. REG_LIVE_READ triggers more path prune during state equal comparison, while REG_LIVE_READ64 triggers 64-bit insn marking during def-use chain walking. Use-def chain is separate from reg state parentage chain chain, the prior is helping the later, reg states that needs REG_LIVE_READ64 propagation are collected during use-def chain walking. Please review the following implementation. Thanks. Regards, Jiong diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index b42b60a..ea22f43 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -34,11 +34,15 @@ * but of the link between it and its parent. See mark_reg_read() and * mark_stack_slot_read() in kernel/bpf/verifier.c. */ -enum bpf_reg_liveness { - REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */ - REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */ - REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */ -}; +/* Reg hasn't been read or written this branch. */ +#define REG_LIVE_NONE 0 +/* Reg was read, so we're sensitive to initial value. */ +#define REG_LIVE_READ 0x1 +/* The read is also 64-bit. */ +#define REG_LIVE_READ64 0x2 +#define REG_LIVE_WRITTEN 0x4 +/* The write also should screen off 64-bit backward propagation. */ +#define REG_LIVE_UNIQUE_WRITTEN 0x8 struct bpf_reg_state { /* Ordering of fields matters. See states_equal() */ @@ -85,7 +89,11 @@ struct bpf_reg_state { * pointing to bpf_func_state. */ u32 frameno; - enum bpf_reg_liveness live; + u32 live; + struct { + s16 active_def; + bool full_ref; + }; }; enum bpf_stack_slot_type { @@ -145,6 +153,11 @@ struct bpf_insn_aux_data { }; int ctx_field_size; /* the ctx field size for load insn, maybe 0 */ int sanitize_stack_off; /* stack slot to be cleared */ + struct { + s16 def[2]; /* The insns defining the uses of this insn. */ + bool full_ref; /* This insn should operate on full 64-bit. */ + }; + struct bpf_reg_state *reg_state; bool seen; /* this insn was processed by the verifier */ }; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 8ccbff4..061345d 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -271,8 +271,7 @@ static char slot_type_char[] = { [STACK_ZERO] = '0', }; -static void print_liveness(struct bpf_verifier_env *env, - enum bpf_reg_liveness live) +static void print_liveness(struct bpf_verifier_env *env, u32 live) { if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN)) verbose(env, "_"); @@ -755,6 +754,7 @@ static void init_reg_state(struct bpf_verifier_env *env, mark_reg_not_init(env, regs, i); regs[i].live = REG_LIVE_NONE; regs[i].parent = NULL; + regs[i].active_def = -1; } /* frame pointer */ @@ -779,9 +779,16 @@ static void init_func_state(struct bpf_verifier_env *env, } enum reg_arg_type { - SRC_OP, /* register is used as source operand */ + SRC_OP_0, /* register is used as source operand */ + SRC_OP64_0, /* likewise, and all 64 bits of the source matter */ + SRC_OP_1, /* the second source */ + SRC_OP64_1, /* likewise */ + SRC_OP64_IMP, /* implicit source, always 64-bit */ + SRC_OP_SPILL, /* stack spill */ DST_OP, /* register is used as destination operand */ - DST_OP_NO_MARK /* same as above, check only, don't mark */ + U_DST_OP, /* likewise, and no overlap with any source */ + DST_OP_NO_MARK, /* same as above, check only, don't mark */ + U_DST_OP_NO_MARK/* likewise */ }; static int cmp_subprogs(const void *a, const void *b) @@ -899,14 +906,101 @@ static int check_subprogs(struct bpf_verifier_env *env) return 0; } +static void +link_reg_to_def(struct bpf_verifier_env *env, const struct bpf_reg_state *rstate, + enum reg_arg_type read_t, s16 insn_idx) +{ + s16 slot_idx, def_idx; + + if (insn_idx == -1) + return; + + slot_idx = (read_t - SRC_OP_0) % 2; + def_idx = rstate->active_def; + env->insn_aux_data[insn_idx].def[slot_idx] = def_idx + 1; +} + +/* Stack of insns to process, this is also used by check_cfg. */ +static int *insn_stack; + +struct prop_pair { + struct bpf_reg_state *reg_state; + u8 regno; +}; + +/* Mark insn upward along the chain, also propagate READ64 liveness. */ +static int mark_insn_64bit(struct bpf_verifier_env *env, int insn_idx) +{ + struct bpf_insn_aux_data *aux = env->insn_aux_data; + u16 u2d0, u2d1, stack_idx = 0, prop_idx = 0; + struct prop_pair *prop_stack; + + prop_stack = kcalloc(1024, sizeof(struct prop_pair), GFP_KERNEL); + if (!prop_stack) + return -ENOMEM; + + insn_stack[stack_idx++] = insn_idx; + + while (stack_idx) { + u16 def_idx = insn_stack[--stack_idx]; + + if (!def_idx) + continue; + + def_idx--; + + aux[def_idx].full_ref = true; + u2d0 = aux[def_idx].def[0]; + if (u2d0) { + insn_stack[stack_idx++] = u2d0; + prop_stack[prop_idx].reg_state = aux[def_idx].reg_state; + prop_stack[prop_idx++].regno = + env->prog->insnsi[u2d0 - 1].dst_reg; + } + u2d1 = aux[def_idx].def[1]; + if (u2d1) { + insn_stack[stack_idx++] = u2d1; + prop_stack[prop_idx].reg_state = aux[def_idx].reg_state; + prop_stack[prop_idx++].regno = + env->prog->insnsi[u2d1 - 1].dst_reg; + } + } + + while (prop_idx) { + struct prop_pair pair = prop_stack[--prop_idx]; + struct bpf_reg_state *state, *parent; + u8 regno = pair.regno; + + state = pair.reg_state + regno; + parent = state->parent; + + while (parent) { + if (state->live & REG_LIVE_UNIQUE_WRITTEN) + break; + + parent->live |= REG_LIVE_READ64; + state = parent; + parent = state->parent; + } + } + + kfree(prop_stack); + + return 0; +} + /* Parentage chain of this register (or stack slot) should take care of all * issues like callee-saved registers, stack slot allocation time, etc. */ static int mark_reg_read(struct bpf_verifier_env *env, const struct bpf_reg_state *state, - struct bpf_reg_state *parent) + struct bpf_reg_state *parent, bool full_reg_read) { bool writes = parent == state->parent; /* Observe write marks */ + const struct bpf_reg_state *orig_state = state; + struct bpf_reg_state *orig_parent = parent; + bool orig_writes = writes; + int def_idx; while (parent) { /* if read wasn't screened by an earlier write ... */ @@ -918,11 +1012,20 @@ static int mark_reg_read(struct bpf_verifier_env *env, parent = state->parent; writes = true; } - return 0; + + writes = orig_writes; + parent = orig_parent; + state = orig_state; + + def_idx = writes ? state->active_def : parent->active_def; + if (!full_reg_read || def_idx == -1) + return 0; + + return mark_insn_64bit(env, def_idx + 1); } static int check_reg_arg(struct bpf_verifier_env *env, u32 regno, - enum reg_arg_type t) + enum reg_arg_type t, s16 insn_idx) { struct bpf_verifier_state *vstate = env->cur_state; struct bpf_func_state *state = vstate->frame[vstate->curframe]; @@ -933,16 +1036,24 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno, return -EINVAL; } - if (t == SRC_OP) { + if (t == SRC_OP_0 || t == SRC_OP_1 || + t == SRC_OP64_0 || t == SRC_OP64_1 || t == SRC_OP64_IMP) { + struct bpf_reg_state *rstate = regs + regno; + /* check whether register used as source operand can be read */ - if (regs[regno].type == NOT_INIT) { + if (rstate->type == NOT_INIT) { verbose(env, "R%d !read_ok\n", regno); return -EACCES; } + + link_reg_to_def(env, rstate, t, insn_idx); + /* We don't need to worry about FP liveness because it's read-only */ if (regno != BPF_REG_FP) - return mark_reg_read(env, ®s[regno], - regs[regno].parent); + return mark_reg_read(env, rstate, rstate->parent, + t == SRC_OP64_0 || + t == SRC_OP64_1 || + t == SRC_OP64_IMP); } else { /* check whether register used as dest operand can be written to */ if (regno == BPF_REG_FP) { @@ -950,8 +1061,14 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno, return -EACCES; } regs[regno].live |= REG_LIVE_WRITTEN; - if (t == DST_OP) + if (t == U_DST_OP || t == U_DST_OP_NO_MARK) + regs[regno].live |= REG_LIVE_UNIQUE_WRITTEN; + if (t == DST_OP || t == U_DST_OP) mark_reg_unknown(env, regs, regno); + regs[regno].active_def = insn_idx; + if (insn_idx != -1) { + env->insn_aux_data[insn_idx].reg_state = regs; + } } return 0; } @@ -1118,7 +1235,8 @@ static int check_stack_read(struct bpf_verifier_env *env, state->regs[value_regno].live |= REG_LIVE_WRITTEN; } mark_reg_read(env, ®_state->stack[spi].spilled_ptr, - reg_state->stack[spi].spilled_ptr.parent); + reg_state->stack[spi].spilled_ptr.parent, + SRC_OP_SPILL); return 0; } else { int zeros = 0; @@ -1135,7 +1253,8 @@ static int check_stack_read(struct bpf_verifier_env *env, return -EACCES; } mark_reg_read(env, ®_state->stack[spi].spilled_ptr, - reg_state->stack[spi].spilled_ptr.parent); + reg_state->stack[spi].spilled_ptr.parent, + SRC_OP_SPILL); if (value_regno >= 0) { if (zeros == size) { /* any size read into register is zero extended, @@ -1735,23 +1854,26 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn return err; } -static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn) +static int +check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn) { + bool is_xadd_64 = BPF_SIZE(insn->code) == BPF_DW; + bool is_xadd_32 = BPF_SIZE(insn->code) == BPF_W; int err; - if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) || - insn->imm != 0) { + if (!(is_xadd_32 || is_xadd_64) || insn->imm != 0) { verbose(env, "BPF_XADD uses reserved fields\n"); return -EINVAL; } /* check src1 operand */ - err = check_reg_arg(env, insn->src_reg, SRC_OP); + err = check_reg_arg(env, insn->src_reg, + is_xadd_32 ? SRC_OP_0 : SRC_OP64_0, insn_idx); if (err) return err; /* check src2 operand */ - err = check_reg_arg(env, insn->dst_reg, SRC_OP); + err = check_reg_arg(env, insn->dst_reg, SRC_OP64_1, insn_idx); if (err) return err; @@ -1852,7 +1974,8 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno, * the whole slot to be marked as 'read' */ mark_reg_read(env, &state->stack[spi].spilled_ptr, - state->stack[spi].spilled_ptr.parent); + state->stack[spi].spilled_ptr.parent, + SRC_OP_SPILL); } return update_stack_depth(env, state, off); } @@ -1903,7 +2026,7 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno, if (arg_type == ARG_DONTCARE) return 0; - err = check_reg_arg(env, regno, SRC_OP); + err = check_reg_arg(env, regno, SRC_OP64_IMP, -1); if (err) return err; @@ -2320,7 +2443,7 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn, /* after the call registers r0 - r5 were scratched */ for (i = 0; i < CALLER_SAVED_REGS; i++) { mark_reg_not_init(env, caller->regs, caller_saved[i]); - check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); + check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK, -1); } /* only increment it after check_reg_arg() finished */ @@ -2510,7 +2633,7 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn /* reset caller saved regs */ for (i = 0; i < CALLER_SAVED_REGS; i++) { mark_reg_not_init(env, regs, caller_saved[i]); - check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); + check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK, -1); } /* update return register (already marked as written above) */ @@ -3161,7 +3284,10 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) { struct bpf_reg_state *regs = cur_regs(env); u8 opcode = BPF_OP(insn->code); - int err; + enum reg_arg_type dst_type; + int err, insn_idx; + + insn_idx = insn - env->prog->insnsi; if (opcode == BPF_END || opcode == BPF_NEG) { if (opcode == BPF_NEG) { @@ -3181,7 +3307,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) } /* check src operand */ - err = check_reg_arg(env, insn->dst_reg, SRC_OP); + err = check_reg_arg(env, insn->dst_reg, SRC_OP_0, insn_idx); if (err) return err; @@ -3191,8 +3317,9 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) return -EACCES; } + dst_type = insn->dst_reg != insn->src_reg ? U_DST_OP : DST_OP; /* check dest operand */ - err = check_reg_arg(env, insn->dst_reg, DST_OP); + err = check_reg_arg(env, insn->dst_reg, dst_type, insn_idx); if (err) return err; @@ -3205,18 +3332,24 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) } /* check src operand */ - err = check_reg_arg(env, insn->src_reg, SRC_OP); + err = check_reg_arg(env, insn->src_reg, SRC_OP_0, + insn_idx); if (err) return err; + + dst_type = insn->dst_reg != insn->src_reg ? + U_DST_OP_NO_MARK : DST_OP_NO_MARK; } else { if (insn->src_reg != BPF_REG_0 || insn->off != 0) { verbose(env, "BPF_MOV uses reserved fields\n"); return -EINVAL; } + + dst_type = U_DST_OP_NO_MARK; } /* check dest operand, mark as required later */ - err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); + err = check_reg_arg(env, insn->dst_reg, dst_type, insn_idx); if (err) return err; @@ -3225,8 +3358,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) /* case: R1 = R2 * copy register state to dest reg */ + u32 live_old = regs[insn->dst_reg].live; + s16 def_old = regs[insn->dst_reg].active_def; + regs[insn->dst_reg] = regs[insn->src_reg]; - regs[insn->dst_reg].live |= REG_LIVE_WRITTEN; + regs[insn->dst_reg].live |= live_old; + regs[insn->dst_reg].active_def = def_old; } else { /* R1 = (u32) R2 */ if (is_pointer_value(env, insn->src_reg)) { @@ -3266,18 +3403,23 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) return -EINVAL; } /* check src1 operand */ - err = check_reg_arg(env, insn->src_reg, SRC_OP); + err = check_reg_arg(env, insn->src_reg, SRC_OP_0, + insn_idx); if (err) return err; + dst_type = insn->dst_reg != insn->src_reg ? + U_DST_OP_NO_MARK : DST_OP_NO_MARK; } else { if (insn->src_reg != BPF_REG_0 || insn->off != 0) { verbose(env, "BPF_ALU uses reserved fields\n"); return -EINVAL; } + + dst_type = DST_OP_NO_MARK; } /* check src2 operand */ - err = check_reg_arg(env, insn->dst_reg, SRC_OP); + err = check_reg_arg(env, insn->dst_reg, SRC_OP_1, insn_idx); if (err) return err; @@ -3303,7 +3445,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) } /* check dest operand */ - err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); + err = check_reg_arg(env, insn->dst_reg, dst_type, insn_idx); if (err) return err; @@ -3759,6 +3901,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs; struct bpf_reg_state *dst_reg, *other_branch_regs; u8 opcode = BPF_OP(insn->code); + int old_insn_idx = *insn_idx; int err; if (opcode > BPF_JSLE) { @@ -3773,7 +3916,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, } /* check src1 operand */ - err = check_reg_arg(env, insn->src_reg, SRC_OP); + err = check_reg_arg(env, insn->src_reg, SRC_OP64_0, + old_insn_idx); if (err) return err; @@ -3790,7 +3934,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, } /* check src2 operand */ - err = check_reg_arg(env, insn->dst_reg, SRC_OP); + err = check_reg_arg(env, insn->dst_reg, SRC_OP64_1, old_insn_idx); if (err) return err; @@ -3896,7 +4040,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn) return -EINVAL; } - err = check_reg_arg(env, insn->dst_reg, DST_OP); + err = check_reg_arg(env, insn->dst_reg, U_DST_OP, + insn - env->prog->insnsi); if (err) return err; @@ -3945,9 +4090,9 @@ static bool may_access_skb(enum bpf_prog_type type) */ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) { + int i, err, insn_idx = insn - env->prog->insnsi; struct bpf_reg_state *regs = cur_regs(env); u8 mode = BPF_MODE(insn->code); - int i, err; if (!may_access_skb(env->prog->type)) { verbose(env, "BPF_LD_[ABS|IND] instructions not allowed for this program type\n"); @@ -3979,7 +4124,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) } /* check whether implicit source operand (register R6) is readable */ - err = check_reg_arg(env, BPF_REG_6, SRC_OP); + err = check_reg_arg(env, BPF_REG_6, SRC_OP64_1, insn_idx); if (err) return err; @@ -3991,7 +4136,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) if (mode == BPF_IND) { /* check explicit source operand */ - err = check_reg_arg(env, insn->src_reg, SRC_OP); + err = check_reg_arg(env, insn->src_reg, SRC_OP_0, insn_idx); if (err) return err; } @@ -3999,7 +4144,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) /* reset caller saved regs to unreadable */ for (i = 0; i < CALLER_SAVED_REGS; i++) { mark_reg_not_init(env, regs, caller_saved[i]); - check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); + check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK, -1); } /* mark destination R0 register as readable, since it contains @@ -4091,7 +4236,6 @@ enum { #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L) -static int *insn_stack; /* stack of insns to process */ static int cur_stack; /* current stack index */ static int *insn_state; @@ -4554,10 +4698,11 @@ static bool states_equal(struct bpf_verifier_env *env, */ static int propagate_liveness(struct bpf_verifier_env *env, const struct bpf_verifier_state *vstate, - struct bpf_verifier_state *vparent) + struct bpf_verifier_state *vparent, int insn_idx) { - int i, frame, err = 0; + struct bpf_reg_state *regs, *parent_regs; struct bpf_func_state *state, *parent; + int i, frame, err = 0; if (vparent->curframe != vstate->curframe) { WARN(1, "propagate_live: parent frame %d current frame %d\n", @@ -4566,13 +4711,24 @@ static int propagate_liveness(struct bpf_verifier_env *env, } /* Propagate read liveness of registers... */ BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG); + parent_regs = vparent->frame[vparent->curframe]->regs; + regs = vstate->frame[vparent->curframe]->regs; /* We don't need to worry about FP liveness because it's read-only */ for (i = 0; i < BPF_REG_FP; i++) { - if (vparent->frame[vparent->curframe]->regs[i].live & REG_LIVE_READ) + if (!(parent_regs[i].live & REG_LIVE_READ64) && + regs[i].live & REG_LIVE_READ64) { + err = mark_reg_read(env, ®s[i], &parent_regs[i], + true); + if (err) + return err; continue; - if (vstate->frame[vstate->curframe]->regs[i].live & REG_LIVE_READ) { - err = mark_reg_read(env, &vstate->frame[vstate->curframe]->regs[i], - &vparent->frame[vstate->curframe]->regs[i]); + } + + if (parent_regs[i].live & REG_LIVE_READ) + continue; + if (regs[i].live & REG_LIVE_READ) { + err = mark_reg_read(env, ®s[i], &parent_regs[i], + false); if (err) return err; } @@ -4588,7 +4744,8 @@ static int propagate_liveness(struct bpf_verifier_env *env, continue; if (state->stack[i].spilled_ptr.live & REG_LIVE_READ) mark_reg_read(env, &state->stack[i].spilled_ptr, - &parent->stack[i].spilled_ptr); + &parent->stack[i].spilled_ptr, + false); } } return err; @@ -4620,7 +4777,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) * they'll be immediately forgotten as we're pruning * this state and will pop a new one. */ - err = propagate_liveness(env, &sl->state, cur); + err = propagate_liveness(env, &sl->state, cur, insn_idx); if (err) return err; return 1; @@ -4699,6 +4856,12 @@ static int do_check(struct bpf_verifier_env *env) BPF_MAIN_FUNC /* callsite */, 0 /* frameno */, 0 /* subprogno, zero == main subprog */); + + /* insn_stack will be used by propagate_64bit_usage. */ + insn_stack = kcalloc(insn_cnt * 2, sizeof(int), GFP_KERNEL); + if (!insn_stack) + return -ENOMEM; + insn_idx = 0; for (;;) { struct bpf_insn *insn; @@ -4779,11 +4942,13 @@ static int do_check(struct bpf_verifier_env *env) /* check for reserved fields is already done */ /* check src operand */ - err = check_reg_arg(env, insn->src_reg, SRC_OP); + err = check_reg_arg(env, insn->src_reg, SRC_OP64_0, + insn_idx); if (err) return err; - err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); + err = check_reg_arg(env, insn->dst_reg, + U_DST_OP_NO_MARK, insn_idx); if (err) return err; @@ -4823,6 +4988,12 @@ static int do_check(struct bpf_verifier_env *env) } else if (class == BPF_STX) { enum bpf_reg_type *prev_dst_type, dst_reg_type; + enum reg_arg_type source_type; + + /* Let the back-end decide which insn to use according + * to store width. + */ + env->insn_aux_data[insn_idx].full_ref = true; if (BPF_MODE(insn->code) == BPF_XADD) { err = check_xadd(env, insn_idx, insn); @@ -4832,12 +5003,17 @@ static int do_check(struct bpf_verifier_env *env) continue; } + source_type = BPF_SIZE(insn->code) == BPF_DW ? + SRC_OP64_0 : SRC_OP_0; + /* check src1 operand */ - err = check_reg_arg(env, insn->src_reg, SRC_OP); + err = check_reg_arg(env, insn->src_reg, source_type, + insn_idx); if (err) return err; /* check src2 operand */ - err = check_reg_arg(env, insn->dst_reg, SRC_OP); + err = check_reg_arg(env, insn->dst_reg, SRC_OP64_1, + insn_idx); if (err) return err; @@ -4867,8 +5043,12 @@ static int do_check(struct bpf_verifier_env *env) verbose(env, "BPF_ST uses reserved fields\n"); return -EINVAL; } + + env->insn_aux_data[insn_idx].full_ref = true; + /* check src operand */ - err = check_reg_arg(env, insn->dst_reg, SRC_OP); + err = check_reg_arg(env, insn->dst_reg, SRC_OP64_0, + insn_idx); if (err) return err; @@ -4888,6 +5068,12 @@ static int do_check(struct bpf_verifier_env *env) } else if (class == BPF_JMP) { u8 opcode = BPF_OP(insn->code); + /* TODO: could potentially use range info to check if + * the comparison setting condition could be done on + * 32-bit sub-register. + */ + env->insn_aux_data[insn_idx].full_ref = true; + if (opcode == BPF_CALL) { if (BPF_SRC(insn->code) != BPF_K || insn->off != 0 || @@ -4918,6 +5104,9 @@ static int do_check(struct bpf_verifier_env *env) continue; } else if (opcode == BPF_EXIT) { + bool is_main_exit; + u32 frame_idx; + if (BPF_SRC(insn->code) != BPF_K || insn->imm != 0 || insn->src_reg != BPF_REG_0 || @@ -4926,7 +5115,8 @@ static int do_check(struct bpf_verifier_env *env) return -EINVAL; } - if (state->curframe) { + frame_idx = state->curframe; + if (frame_idx) { /* exit from nested function */ prev_insn_idx = insn_idx; err = prepare_func_exit(env, &insn_idx); @@ -4942,7 +5132,12 @@ static int do_check(struct bpf_verifier_env *env) * of bpf_exit, which means that program wrote * something into it earlier */ - err = check_reg_arg(env, BPF_REG_0, SRC_OP); + is_main_exit = + !state->frame[frame_idx]->subprogno; + err = check_reg_arg(env, BPF_REG_0, + is_main_exit ? + SRC_OP64_0 :SRC_OP_0, + insn_idx); if (err) return err; @@ -5267,6 +5462,13 @@ static void sanitize_dead_code(struct bpf_verifier_env *env) int i; for (i = 0; i < insn_cnt; i++) { + /* Demonstration the usage of "full_ref" info. We could rewrite + * BPF_ALU64 into BPF_ALU. 64-bit architecture could + * then automatically get more 32-bit sub-register. + */ + if (!aux_data[i].full_ref && + BPF_CLASS(insn[i].code) == BPF_ALU64) + insn[i].code = (insn[i].code & ~0x7) | BPF_ALU; if (aux_data[i].seen) continue; memcpy(insn + i, &trap, sizeof(trap)); @@ -5910,11 +6112,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr) if (ret < 0) goto skip_full_check; + insn_stack = NULL; ret = do_check(env); if (env->cur_state) { free_verifier_state(env->cur_state, true); env->cur_state = NULL; } + kfree(insn_stack); skip_full_check: while (!pop_stack(env, NULL, NULL)); ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification 2018-10-03 15:36 ` Jiong Wang 2018-10-03 15:59 ` Alexei Starovoitov @ 2018-10-04 17:35 ` Edward Cree 1 sibling, 0 replies; 12+ messages in thread From: Edward Cree @ 2018-10-04 17:35 UTC (permalink / raw) To: Jiong Wang, ast, daniel; +Cc: netdev On 03/10/18 16:36, Jiong Wang wrote: > On 28/09/2018 14:36, Edward Cree wrote: > > But what you've described sounds interesting; perhaps it would also > > help later with loop-variable handling? > > Haven't considered how to use this for loop-variable handling, guess you mean > applying what I have described to your previous loop detection RFC? I will look > into your RFC later. Tbh I was thinking more of John Fastabend's version (I'm not sure if he ever got round to posting patches, but he discussed the design towards the end of https://www.mail-archive.com/netdev@vger.kernel.org/msg216285.html ) which is building 'proper compiler data structures' and thus might be interested in proper use-def chains. (Or it might not; I'm not really a compiler-guru so it's not immediately obvious to me.) My approach was much less interested in the 'provenance' of the induction variable, just that it was increasing appropriately, so use-def chains are not really relevant to it. -Ed ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2018-10-09 3:32 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-08-22 19:00 [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Edward Cree 2018-08-22 19:02 ` [RFC PATCH v2 bpf-next 1/2] bpf/verifier: per-register parent pointers Edward Cree 2018-08-22 19:02 ` [RFC PATCH v2 bpf-next 2/2] bpf/verifier: display non-spill stack slot types in print_verifier_state Edward Cree 2018-08-30 2:18 ` [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Alexei Starovoitov 2018-08-31 15:50 ` Edward Cree 2018-09-26 22:16 ` Jiong Wang 2018-09-28 13:36 ` Edward Cree 2018-10-03 15:36 ` Jiong Wang 2018-10-03 15:59 ` Alexei Starovoitov 2018-10-03 16:53 ` Jiong Wang 2018-10-08 20:18 ` Jiong Wang 2018-10-04 17:35 ` Edward Cree
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).