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 ;)
