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
