On Fri, Mar 29, 2019 at 08:18:28PM -0700, Jakub Kicinski wrote: > On Fri, 29 Mar 2019 17:16:05 -0700, Alexei Starovoitov wrote: > > Realize two key ideas to speed up verification speed by ~20 times > > 1. every 'branching' instructions records all verifier states. > > not all of them are useful for search pruning. > > add a simple heuristic to keep states that were successful in search pruning > > and remove those that were not > > 2. mark_reg_read walks parentage chain of registers to mark parents as LIVE_READ. > > Once the register is marked there is no need to remark it again in the future. > > Hence stop walking the chain once first LIVE_READ is seen. > > > > 1st optimization gives 10x speed up on large programs > > and 2nd optimization reduces the cost of mark_reg_read from ~40% of cpu to <1%. > > Combined the deliver ~20x speedup on large programs. > > > > Faster and bounded verification time allows to increase insn_processed > > limit to 1 million from 130k. > > > > Worst case it takes 1/10 of a second to process that many instructions > > and peak memory consumption is peak_states * sizeof(struct bpf_verifier_state) > > which is around ~5Mbyte. > > > > Increase insn_per_program limit for root to insn_processed limit. > > > > Add verification stats and stress tests for verifier scalability. > > > > This patch set is the first step to be able to accept large programs. > > The verifier still suffers from its brute force algorithm and > > large programs can easily hit 1M insn_processed limit. > > A lot more work is necessary to be able to verify large programs. > > Very nice! > > Hopefully this doesn't discourage people from working on loops ;) Definitely not :) we desperately need loops. llvm performs 'pragma unroll' only for relatively small loop counts. Walking stack traces still not possible. In the test from patch 7 doing jhash() over 64-bytes will not work, because llvm will generate a loop ignoring pragma unroll.
