On 10/02/18 03:18, Alexei Starovoitov wrote: > On Thu, Feb 08, 2018 at 07:31:55PM +0000, Edward Cree wrote: >> By storing subprog boundaries as a subprogno mark on each insn, rather than >> a start (and implicit end) for each subprog, we collect a number of gains: >> * More efficient determination of which subprog contains a given insn, and >> thus of find_subprog (which subprog begins at a given insn). >> * Number of verifier passes is reduced, since most of the work is done in >> the main insn walk (do_check()). > unfortunately this is the opposite of where the verifier should be heading. > For bpf libraries and indirect call support the verifier has to be further > split into more distinct passes. Not less. Since it needs to determine > function boundaries and general validity of the instructions without > performing do_check()-style walk. > The function in the given prog may be called by other bpf functions that will > be > loaded later and just like indirect calls the final 'check all pointers > and load/stores' pass (currently done by do_check) will done last. Strictly speaking, any kind of sanity check done before the program can be do_check() walked can only be a kind of early-fail optimisation, because the final 'check pointers and load/stores' (and register types in general, and any data value tracking we may use for bounded loops) can depend on values returned from callees. So I am tempted to suggest that any such 'early sanity passes' should be in addition to, rather than instead of, checks at walk time. > (In case of indirect calls this pass will done at the time of > bpf_map_update() call) Btw I hope you're planning to only have these maps writable by the control plane, and not from within BPF programs themselves; allowing BPF execution to trigger a verifier run would be... interesting.
> while all preparatory passes like function boundaries, basic block > detection, control flow check and general instruction sanity will > be done before that final run-time linking phase. > Hence we cannot merge subprog detection pass with anything else. > It has to be done first. Why does it *have* to be done first? Why would a verifier that postponed all checks until the complete prog was available be actually wrong? >> * Subprogs no longer have to be contiguous; so long as they don't overlap >> and there are no unreachable insns, verifier is happy. (This does require >> a small amount of care at jit_subprogs() time to fix up jump offsets, so >> we could instead disallow this if people prefer.) > do you have patches to make llvm blend multiple C functions into > non-contiguous piece of .text code ? I have an assembler that produces eBPF object files. I can make whatever crazy .text I want ;-) > What would be the purpose of such bizarre code generation? > If not, there is no reason to support such code layout in the verifier. But the real reason is that disallowing it would have required writing an extra check, and I wanted to get a first prototype out for discussion ASAP. >> Some other changes were also included to support this: >> * Per-subprog info is stored in env->subprog_info, an array of structs, >> rather than several arrays with a common index. >> * Call graph is now stored in the new bpf_subprog_info struct; used here for >> check_max_stack_depth() but may have other uses too. > The new maximum stack depth algorithm is interesting, but it looks > unrelated to the rest and much harder to understand It's basically Kahn's algorithm from https://en.wikipedia.org/wiki/Topological_sorting if that helps? I could perhaps explain that more fully in comments. > comparing to existing check_max_stack_depth() algorithm. > The patches must explain the benefits clearly. Currently it's not the case. The benefit here, which indeed I didn't clearly explain, is that we replace a full recursive-walk pass with an algorithm that's O(n) in the number of subprogs. >> * LD_ABS and LD_IND were previously disallowed in programs that also contain >> subprog calls. Now they are only disallowed in callees, i.e. main() can >> always use them even if it also uses subprog calls. AFAICT this is safe >> (main()'s r1 arg is still known to be ctx, so prologue can do its stuff). >> But again it can be disallowed if necessary. > What is the purpose of allowing ld_abs in calls ? > The work over the last years have been to avoid ld_abs as much as possible, > since these instructions are slow, carry a lot of legacy baggage and corner > cases > that cause JITs and verifier to do additional work and make every piece more > complex. > Allowing ld_abs with calls is going into the opposite direction. > Personally I very much dislike patches that "lets do this just because". > Nothing in the patch 1 or in this cover letter explain the reason. Again, it was because it was more effort to forbid than allow (if we walk a ld_abs before the first call, we don't know yet that calls are coming, so I'd need to do something like recording in check_cfg that a call was seen) and I wanted to get the prototype out there. There are more patches coming, btw; I am not just doing a random collection of changes but rather working towards a prototype implementation of bounded loops. (I also have a 'parent-pointer-per-reg' patch, passing tests, in the series. That cuts out 100 lines!) While it's probably different to the way you're planning/expecting them to be handled, I think it's worth having both approaches to compare. There's a reason this series is marked RFC ;-) > Overall I think the set is more harmful than useful. > > If you like to help developing bpf infrastructure please focus > on replacing signed/unsigned min/max tracking logic with simpler and safer > logic. If you like to keep bringing up [su]minmax tracking, please focus on answering the points I've repeatedly raised about the alternatives being confusing and complicated (due to asymmetry) which leads (and historically led) to them being buggy. > 1. [su]minmax burning memory and making verifier process slower Memory is cheap. Do you have numbers that show it's a problem in the real world for someone, or are you committing premature optimisation? (Even with (say) 4k explored_states * 11 regs, it's only 1.4MB. All this fuss over just those 32 bytes per reg... it probably takes more memory just to store all our arguments about [su]minmax.) > 2. it's internally inconsistent, since it can determine that smin > smax. > We had to remove that WARN_ON, but underlying issue remains. IIRC the old tracking could do the same; if you did two JSGTs you could get a branch where min_value > max_value. This is a natural result of following such 'impossible' branches, in no sense specific to [su]minmax. > 3. it had been source of security bugs So had the alternative, whose bugs stayed hidden for longer because of the inelegant, asymmetric complexity of the code. > 4. The reason it was introduced was to verify validity of variable length > array access, but it can be done much simpler instead. > We're dealing with C compiled code here and C arrays have zero till N range. > There is no reason to track that a variable can be between -100 to -10. But there is reason to track whether a bound came from a signed or an unsigned compare, and I don't see why it should be a point against the _clean_ implementation that it happens to also support unusual things. > This tracking is a waste of verifier resources for realistic C programs. And what if someone subtracts a variable with a min_value from another, and the min_value is necessary to prove the access safe? I suppose that's 'unrealistic', up until the day that someone wants to do it. Also, my design for bounded loops really does need a min_value in order to handle an increasing loop counter. > All of [su]minmax can be replaced with {u32_max_value, can_be_zero, > can_be_negative} > tracking which is 4 bytes and 2 bits of info per bpf_reg_state instead of 32 > bytes. > Such tracking will be more accurate as well. > llvm can optimize 'var >= 1' compare into 'var != 0' and we've seen > cases that this optimization breaks minmax tracking, since !=0 simply > doesn't fit into minmax logic. One can argue reg_set_min_max() needs to track > this extra boolean state as well, Well, if real-world programs are hitting this and need it, then yes, handling for jeq/jne 0 should be changed to give umin >= 1. > but then it would mean more inconsistency > in the bpf_reg_state and information contradicting each other. > Any verifier pass looking at bpf_reg_state at any given time should > see bpf_reg_state being valid and not guessing why smin is suddenly more > than smax. Again, nothing to do with [su]minmax, your approach could have a state in which max_value=0 and can_be_zero is false, for the exact same reason. -Ed