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.
