| Message ID | 20181212052854.4105971-5-ast@kernel.org |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | bpf: improve verifier state analysis | expand |
On 12/12/18 05:28, Alexei Starovoitov wrote: > introduce REG_LIVE_DONE to check the liveness propagation > and prepare the states for merging > See algorithm description in clean_live_states(). > No difference in tests. > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> This feels a bit magic to me, relying as it does on seeing the state again in is_state_visited() after the last continuation is explored (rather than the marking happening as soon as the last exit is reached). Also, why do you clean_live_states() in or after the states_equal() loop, rather than doing it (in just one place) before it? AIUI, being in is_state_visited() already implies that all explored states are DONE, whether any of them match cur_state or not. A different way I previously thought of was to have a refcount in verifier states (at the time we had a single parent rather than per- register parents) counting live children, that falls to 0 when all continuations have been walked. That was something I did in my bounded loops RFC. With something like that, we could check refcount != 0 in mark_reg_read and check refcount == 0 in explored states in is_state_visited. Seems to me like that gets you the same thing and also adds the guarantee that our explored_states really are fully explored. Rest of series looks good, have my Ack for patches 1-3. (Though, maybe use a few more capital letters in your commit messages?) -Ed
On Wed, Dec 12, 2018 at 08:58:33PM +0000, Edward Cree wrote: > On 12/12/18 05:28, Alexei Starovoitov wrote: > > introduce REG_LIVE_DONE to check the liveness propagation > > and prepare the states for merging > > See algorithm description in clean_live_states(). > > No difference in tests. > > > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > This feels a bit magic to me, relying as it does on seeing the state > again in is_state_visited() after the last continuation is explored > (rather than the marking happening as soon as the last exit is > reached). what is "last exit" ? Around 'process_bpf_exit' bit of code the verifier doesn't know which state lists are not going to be changed. > Also, why do you clean_live_states() in or after the states_equal() > loop, rather than doing it (in just one place) before it? true. can move the call to the beginning of is_state_visited(). > AIUI, being > in is_state_visited() already implies that all explored states are > DONE, whether any of them match cur_state or not. Unfortunately not. That's exactly the issue with liveness that I want to address with this additional safety check. For subprograms states_equal() checks callsite equivalence. That's what is saving the existing liveness from producing incorrect results. The states in state lists of subprogs are still going to be changed. > A different way I previously thought of was to have a refcount in > verifier states (at the time we had a single parent rather than per- > register parents) counting live children, that falls to 0 when all > continuations have been walked. That was something I did in my > bounded loops RFC. > With something like that, we could check refcount != 0 in mark_reg_read > and check refcount == 0 in explored states in is_state_visited. Seems > to me like that gets you the same thing and also adds the guarantee > that our explored_states really are fully explored. refcnt was my initial approach, but it needs to walk parentage chain. Also push/pop_stack needs full walk of all chains too. That is too expensive. What kind of refcnt you had in mind? > Rest of series looks good, have my Ack for patches 1-3. > (Though, maybe use a few more capital letters in your commit messages?) Meaning capitalize first letter of the sentences?
On 12/12/18 22:00, Alexei Starovoitov wrote: > On Wed, Dec 12, 2018 at 08:58:33PM +0000, Edward Cree wrote: >> A different way I previously thought of was to have a refcount in >> verifier states (at the time we had a single parent rather than per- >> register parents) counting live children, that falls to 0 when all >> continuations have been walked. That was something I did in my >> bounded loops RFC. >> With something like that, we could check refcount != 0 in mark_reg_read >> and check refcount == 0 in explored states in is_state_visited. Seems >> to me like that gets you the same thing and also adds the guarantee >> that our explored_states really are fully explored. > refcnt was my initial approach, but it needs to walk parentage chain. > Also push/pop_stack needs full walk of all chains too. > That is too expensive. > What kind of refcnt you had in mind? Shallow, rather than deep, refcnt means that you only have to walk to the parent when your refcnt falls to zero. push_stack never has to walk at all. The refcnt only counts immediate children, not all descendants. IIRC that's how I implemented it in my bounded loops RFC; see patch #9 "bpf/verifier: count still-live children of explored_states" of that series. Maybe it would still be too expensive, but I wonder if we should obtain numbers for that rather than guessing that it would or wouldn't. Note that if a process_bpf_exit would walk N states dropping refs, then there are N states that would need to be marked DONE by your approach; and you re-do clean_live_states() for each one every time is_state_visited() comes back to the same insn, rather than just walking them once on exit. >> Rest of series looks good, have my Ack for patches 1-3. >> (Though, maybe use a few more capital letters in your commit messages?) > Meaning capitalize first letter of the sentences? Yes, that was what I meant. (Also I think patch #2 is missing a full stop at the end of the sentence, but now I'm just being picky ;-) -Ed
On Wed, Dec 12, 2018 at 10:26:17PM +0000, Edward Cree wrote: > On 12/12/18 22:00, Alexei Starovoitov wrote: > > On Wed, Dec 12, 2018 at 08:58:33PM +0000, Edward Cree wrote: > >> A different way I previously thought of was to have a refcount in > >> verifier states (at the time we had a single parent rather than per- > >> register parents) counting live children, that falls to 0 when all > >> continuations have been walked. That was something I did in my > >> bounded loops RFC. > >> With something like that, we could check refcount != 0 in mark_reg_read > >> and check refcount == 0 in explored states in is_state_visited. Seems > >> to me like that gets you the same thing and also adds the guarantee > >> that our explored_states really are fully explored. > > refcnt was my initial approach, but it needs to walk parentage chain. > > Also push/pop_stack needs full walk of all chains too. > > That is too expensive. > > What kind of refcnt you had in mind? > Shallow, rather than deep, refcnt means that you only have to walk to the > parent when your refcnt falls to zero. push_stack never has to walk at > all. The refcnt only counts immediate children, not all descendants. > IIRC that's how I implemented it in my bounded loops RFC; see patch #9 > "bpf/verifier: count still-live children of explored_states" of that > series. luckily found it in my email archives. next time could you send a link to make sure we're talking about the same patch? back then there was no per-register chains and push_stack() has to do only one live_children++. With per-register it would need to walk all frames and all regs and all stack slots. Old kill_thread() instead of: + while (cur && !--cur->live_children) + cur = cur->parent; becomes such inner loop for all frames, all regs and all slots, right? I have to agree that it is easier to understand to do such kill_thread() in process_bpf_exit, but the cost seems excessive for safety feature. > Maybe it would still be too expensive, but I wonder if we should obtain > numbers for that rather than guessing that it would or wouldn't. Note > that if a process_bpf_exit would walk N states dropping refs, then there > are N states that would need to be marked DONE by your approach; and you > re-do clean_live_states() for each one every time is_state_visited() > comes back to the same insn, rather than just walking them once on exit. I can change clean_live_states() to be called only when equivalent state is not found. Since that's the place where I want to do state merging. Since is_state_visited() just walked state lists and all data is hot, it's the best place to walk them again either for safety check or for state merging. As far as state merging I see a pattern when a bunch of states are overlapping in the register ranges, but not fully contained. Essentially range_within() is too conservative. The idea is to merge [1,5] with [3,10] if this is the only difference between states. Merge, but don't declare it safe yet and proceed further. To do any merging the verifier needs to be sure that reg_state is DONE. Essentially the check of callsites with current state and whole idea of this patch is a precursor of state merging. I was thinking to enforce this safety first and keep it enforced, but use clean_live_states() entry point and checks as a gate for actual merging in the future patches.
On Tue, 11 Dec 2018 21:28:54 -0800, Alexei Starovoitov wrote: > introduce REG_LIVE_DONE to check the liveness propagation > and prepare the states for merging > See algorithm description in clean_live_states(). > No difference in tests. > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > @@ -5021,6 +5029,102 @@ static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap) > return false; > } > > +static void clean_func_state(struct bpf_verifier_env *env, > + struct bpf_func_state *st) > +{ > + enum bpf_reg_liveness live; > + int i, j; > + > + for (i = 0; i < BPF_REG_FP; i++) { > + live = st->regs[i].live; > + if (live & REG_LIVE_DONE) > + continue; Perhaps return; here? Seeing any "done" flag in the state entry implies all regs and stack slots are "done", no? Or even check if there are any DONE flags in clean_verifier_state() before the loop? > + /* liveness must not touch this register anymore */ > + st->regs[i].live |= REG_LIVE_DONE; > + if (!(live & REG_LIVE_READ)) > + /* since the register is unused, clear its state > + * to make further comparison simpler > + */ > + __mark_reg_not_init(&st->regs[i]); > + } > + > + for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) { > + live = st->stack[i].spilled_ptr.live; > + if (live & REG_LIVE_DONE) > + continue; > + /* liveness must not touch this stack slot anymore */ > + st->stack[i].spilled_ptr.live |= REG_LIVE_DONE; > + if (!(live & REG_LIVE_READ)) { > + __mark_reg_not_init(&st->stack[i].spilled_ptr); > + for (j = 0; j < BPF_REG_SIZE; j++) > + st->stack[i].slot_type[j] = STACK_INVALID; > + } > + } > +} > + > +static void clean_verifier_state(struct bpf_verifier_env *env, > + struct bpf_verifier_state *st) > +{ > + int i; > + > + for (i = 0; i <= st->curframe; i++) > + clean_func_state(env, st->frame[i]); > +} > + > +/* the parentage chains form a tree. > + * the verifier states are added to state lists at given insn and > + * pushed into state stack for future exploration. > + * when the verifier reaches bpf_exit insn some of the verifer states > + * stored in the state lists have their final liveness state already, > + * but a lot of states will get revised from liveness point of view when > + * the verifier explores other branches. > + * Example: > + * 1: r0 = 1 > + * 2: if r1 == 100 goto pc+1 > + * 3: r0 = 2 > + * 4: exit > + * when the verifier reaches exit insn the register r0 in the state list of > + * insn 2 will be seen as !REG_LIVE_READ. Then the verifier pops the other_branch > + * of insn 2 and goes exploring further. At the insn 4 it will walk the > + * parentage chain from insn 4 into insn 2 and will mark r0 as REG_LIVE_READ. > + * > + * Since the verifier pushes the branch states as it sees them while exploring > + * the program the condition of walking the branch instruction for the second > + * time means that all states below this branch were already explored and > + * their final liveness markes are already propagated. > + * Hence when the verifier completes the search of state list in is_state_visited() > + * we can call this clean_live_states() function to mark all liveness states > + * as REG_LIVE_DONE to indicate that 'parent' pointers of 'struct bpf_reg_state' > + * will not be used. > + * This function also clears the registers and stack for states that !READ > + * to simplify state merging. > + * > + * Important note here that walking the same branch instruction in the callee > + * doesn't meant that the states are DONE. The verifier has to compare > + * the callsites > + */ Little bike shedding - if I understand Ed's comment I feel the same way about "any state we see must be fully done". Different call sites are logically different state lists in my mind, we effectively "inline" the functions in the verifier walk... > +static void clean_live_states(struct bpf_verifier_env *env, int insn, > + struct bpf_verifier_state *cur) > +{ > + struct bpf_verifier_state_list *sl; > + int i; > + > + sl = env->explored_states[insn]; > + if (!sl) > + return; > + > + while (sl != STATE_LIST_MARK) { > + if (sl->state.curframe != cur->curframe) > + goto next; > + for (i = 0; i <= cur->curframe; i++) > + if (sl->state.frame[i]->callsite != cur->frame[i]->callsite) > + goto next; > + clean_verifier_state(env, &sl->state); > +next: > + sl = sl->next; > + } > +} > + > /* Returns true if (rold safe implies rcur safe) */ > static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, > struct idpair *idmap) > @@ -5354,11 +5458,13 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) > err = propagate_liveness(env, &sl->state, cur); > if (err) > return err; > + clean_live_states(env, insn_idx, cur); > return 1; > } > sl = sl->next; > states_cnt++; > } > + clean_live_states(env, insn_idx, cur); > > if (!env->allow_ptr_leaks && states_cnt > BPF_COMPLEXITY_LIMIT_STATES) > return 0;
On Wed, Dec 12, 2018 at 05:21:35PM -0800, Jakub Kicinski wrote: > On Tue, 11 Dec 2018 21:28:54 -0800, Alexei Starovoitov wrote: > > introduce REG_LIVE_DONE to check the liveness propagation > > and prepare the states for merging > > See algorithm description in clean_live_states(). > > No difference in tests. > > > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > > > @@ -5021,6 +5029,102 @@ static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap) > > return false; > > } > > > > +static void clean_func_state(struct bpf_verifier_env *env, > > + struct bpf_func_state *st) > > +{ > > + enum bpf_reg_liveness live; > > + int i, j; > > + > > + for (i = 0; i < BPF_REG_FP; i++) { > > + live = st->regs[i].live; > > + if (live & REG_LIVE_DONE) > > + continue; > > Perhaps return; here? Seeing any "done" flag in the state entry > implies all regs and stack slots are "done", no? Or even check if > there are any DONE flags in clean_verifier_state() before the loop? good idea. will do. > > + /* liveness must not touch this register anymore */ > > + st->regs[i].live |= REG_LIVE_DONE; > > + if (!(live & REG_LIVE_READ)) > > + /* since the register is unused, clear its state > > + * to make further comparison simpler > > + */ > > + __mark_reg_not_init(&st->regs[i]); > > + } > > + > > + for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) { > > + live = st->stack[i].spilled_ptr.live; > > + if (live & REG_LIVE_DONE) > > + continue; > > + /* liveness must not touch this stack slot anymore */ > > + st->stack[i].spilled_ptr.live |= REG_LIVE_DONE; > > + if (!(live & REG_LIVE_READ)) { > > + __mark_reg_not_init(&st->stack[i].spilled_ptr); > > + for (j = 0; j < BPF_REG_SIZE; j++) > > + st->stack[i].slot_type[j] = STACK_INVALID; > > + } > > + } > > +} > > + > > +static void clean_verifier_state(struct bpf_verifier_env *env, > > + struct bpf_verifier_state *st) > > +{ > > + int i; > > + > > + for (i = 0; i <= st->curframe; i++) > > + clean_func_state(env, st->frame[i]); > > +} > > + > > +/* the parentage chains form a tree. > > + * the verifier states are added to state lists at given insn and > > + * pushed into state stack for future exploration. > > + * when the verifier reaches bpf_exit insn some of the verifer states > > + * stored in the state lists have their final liveness state already, > > + * but a lot of states will get revised from liveness point of view when > > + * the verifier explores other branches. > > + * Example: > > + * 1: r0 = 1 > > + * 2: if r1 == 100 goto pc+1 > > + * 3: r0 = 2 > > + * 4: exit > > + * when the verifier reaches exit insn the register r0 in the state list of > > + * insn 2 will be seen as !REG_LIVE_READ. Then the verifier pops the other_branch > > + * of insn 2 and goes exploring further. At the insn 4 it will walk the > > + * parentage chain from insn 4 into insn 2 and will mark r0 as REG_LIVE_READ. > > + * > > + * Since the verifier pushes the branch states as it sees them while exploring > > + * the program the condition of walking the branch instruction for the second > > + * time means that all states below this branch were already explored and > > + * their final liveness markes are already propagated. > > + * Hence when the verifier completes the search of state list in is_state_visited() > > + * we can call this clean_live_states() function to mark all liveness states > > + * as REG_LIVE_DONE to indicate that 'parent' pointers of 'struct bpf_reg_state' > > + * will not be used. > > + * This function also clears the registers and stack for states that !READ > > + * to simplify state merging. > > + * > > + * Important note here that walking the same branch instruction in the callee > > + * doesn't meant that the states are DONE. The verifier has to compare > > + * the callsites > > + */ > > Little bike shedding - if I understand Ed's comment I feel the same way > about "any state we see must be fully done". Different call sites are > logically different state lists in my mind, we effectively "inline" the > functions in the verifier walk... yes, they are logically different, but implementation is only one state list per insn. So comparing callsites is the "filter" of logical lists.
On 13/12/18 00:00, Alexei Starovoitov wrote: > luckily found it in my email archives. next time could you send a link to > make sure we're talking about the same patch? Sorry, will do. > back then there was no per-register chains and push_stack() > has to do only one live_children++. > With per-register it would need to walk all frames and all regs and > all stack slots. Thinking about it, since this is about control flow rather than data flow, maybe it makes sense to add in a separate parent pointer on the verifier state, and use that for this, rather than shoehorning it into the liveness machinery. > Old kill_thread() instead of: > + while (cur && !--cur->live_children) > + cur = cur->parent; > becomes such inner loop for all frames, all regs and all slots, right? If it's done with the per-reg parent pointers, then yes that's right and that does start to look a bit painful, agreed. > As far as state merging I see a pattern when a bunch of states are > overlapping in the register ranges, but not fully contained. > Essentially range_within() is too conservative. > The idea is to merge [1,5] with [3,10] if this is the only difference > between states. Merge, but don't declare it safe yet and proceed further. Yep, makes sense. -Ed
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index c736945be7c5..07a55073c809 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -38,6 +38,7 @@ 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_LIVE_DONE = 4, /* liveness won't be updating this register anymore */ }; struct bpf_reg_state { diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 6e5ea4c4d8e7..9da0b3f8342a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -339,12 +339,14 @@ static char slot_type_char[] = { static void print_liveness(struct bpf_verifier_env *env, enum bpf_reg_liveness live) { - if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN)) + if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN | REG_LIVE_DONE)) verbose(env, "_"); if (live & REG_LIVE_READ) verbose(env, "r"); if (live & REG_LIVE_WRITTEN) verbose(env, "w"); + if (live & REG_LIVE_DONE) + verbose(env, "D"); } static struct bpf_func_state *func(struct bpf_verifier_env *env, @@ -1074,6 +1076,12 @@ static int mark_reg_read(struct bpf_verifier_env *env, /* if read wasn't screened by an earlier write ... */ if (writes && state->live & REG_LIVE_WRITTEN) break; + if (parent->live & REG_LIVE_DONE) { + verbose(env, "verifier BUG type %s var_off %lld off %d\n", + reg_type_str[parent->type], + parent->var_off.value, parent->off); + return -EFAULT; + } /* ... then we depend on parent's value */ parent->live |= REG_LIVE_READ; state = parent; @@ -5021,6 +5029,102 @@ static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap) return false; } +static void clean_func_state(struct bpf_verifier_env *env, + struct bpf_func_state *st) +{ + enum bpf_reg_liveness live; + int i, j; + + for (i = 0; i < BPF_REG_FP; i++) { + live = st->regs[i].live; + if (live & REG_LIVE_DONE) + continue; + /* liveness must not touch this register anymore */ + st->regs[i].live |= REG_LIVE_DONE; + if (!(live & REG_LIVE_READ)) + /* since the register is unused, clear its state + * to make further comparison simpler + */ + __mark_reg_not_init(&st->regs[i]); + } + + for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) { + live = st->stack[i].spilled_ptr.live; + if (live & REG_LIVE_DONE) + continue; + /* liveness must not touch this stack slot anymore */ + st->stack[i].spilled_ptr.live |= REG_LIVE_DONE; + if (!(live & REG_LIVE_READ)) { + __mark_reg_not_init(&st->stack[i].spilled_ptr); + for (j = 0; j < BPF_REG_SIZE; j++) + st->stack[i].slot_type[j] = STACK_INVALID; + } + } +} + +static void clean_verifier_state(struct bpf_verifier_env *env, + struct bpf_verifier_state *st) +{ + int i; + + for (i = 0; i <= st->curframe; i++) + clean_func_state(env, st->frame[i]); +} + +/* the parentage chains form a tree. + * the verifier states are added to state lists at given insn and + * pushed into state stack for future exploration. + * when the verifier reaches bpf_exit insn some of the verifer states + * stored in the state lists have their final liveness state already, + * but a lot of states will get revised from liveness point of view when + * the verifier explores other branches. + * Example: + * 1: r0 = 1 + * 2: if r1 == 100 goto pc+1 + * 3: r0 = 2 + * 4: exit + * when the verifier reaches exit insn the register r0 in the state list of + * insn 2 will be seen as !REG_LIVE_READ. Then the verifier pops the other_branch + * of insn 2 and goes exploring further. At the insn 4 it will walk the + * parentage chain from insn 4 into insn 2 and will mark r0 as REG_LIVE_READ. + * + * Since the verifier pushes the branch states as it sees them while exploring + * the program the condition of walking the branch instruction for the second + * time means that all states below this branch were already explored and + * their final liveness markes are already propagated. + * Hence when the verifier completes the search of state list in is_state_visited() + * we can call this clean_live_states() function to mark all liveness states + * as REG_LIVE_DONE to indicate that 'parent' pointers of 'struct bpf_reg_state' + * will not be used. + * This function also clears the registers and stack for states that !READ + * to simplify state merging. + * + * Important note here that walking the same branch instruction in the callee + * doesn't meant that the states are DONE. The verifier has to compare + * the callsites + */ +static void clean_live_states(struct bpf_verifier_env *env, int insn, + struct bpf_verifier_state *cur) +{ + struct bpf_verifier_state_list *sl; + int i; + + sl = env->explored_states[insn]; + if (!sl) + return; + + while (sl != STATE_LIST_MARK) { + if (sl->state.curframe != cur->curframe) + goto next; + for (i = 0; i <= cur->curframe; i++) + if (sl->state.frame[i]->callsite != cur->frame[i]->callsite) + goto next; + clean_verifier_state(env, &sl->state); +next: + sl = sl->next; + } +} + /* Returns true if (rold safe implies rcur safe) */ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, struct idpair *idmap) @@ -5354,11 +5458,13 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) err = propagate_liveness(env, &sl->state, cur); if (err) return err; + clean_live_states(env, insn_idx, cur); return 1; } sl = sl->next; states_cnt++; } + clean_live_states(env, insn_idx, cur); if (!env->allow_ptr_leaks && states_cnt > BPF_COMPLEXITY_LIMIT_STATES) return 0;
introduce REG_LIVE_DONE to check the liveness propagation and prepare the states for merging See algorithm description in clean_live_states(). No difference in tests. Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++++++++- 2 files changed, 108 insertions(+), 1 deletion(-)