On 04/02/2019 06:27 AM, Alexei Starovoitov wrote: > v1->v2: > - fixed typo in patch 1 > - added a patch to convert kcalloc to kvcalloc > - added a patch to verbose 16-bit jump offset check > - added a test with 1m insns > > 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. > > v1: > 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. Applied, thanks! As discussed offline a bit with Alexei wrt to prior thread on uapi, this will be documented in design FAQ. > Alexei Starovoitov (10): > bpf: add verifier stats and log_level bit 2 > bpf: improve verification speed by droping states > bpf: improve verification speed by not remarking live_read > bpf: convert temp arrays to kvcalloc > bpf: verbose jump offset overflow check > bpf: increase complexity limit and maximum program size > bpf: increase verifier log limit > libbpf: teach libbpf about log_level bit 2 > selftests/bpf: add few verifier scale tests > selftests/bpf: synthetic tests to push verifier limits > > include/linux/bpf.h | 1 + > include/linux/bpf_verifier.h | 23 +++ > kernel/bpf/core.c | 11 +- > kernel/bpf/syscall.c | 3 +- > kernel/bpf/verifier.c | 153 +++++++++++++----- > tools/lib/bpf/bpf.c | 2 +- > tools/lib/bpf/bpf.h | 2 +- > tools/lib/bpf/libbpf.c | 16 +- > tools/lib/bpf/libbpf.h | 1 + > .../bpf/prog_tests/bpf_verif_scale.c | 49 ++++++ > .../testing/selftests/bpf/progs/test_jhash.h | 70 ++++++++ > .../selftests/bpf/progs/test_verif_scale1.c | 30 ++++ > .../selftests/bpf/progs/test_verif_scale2.c | 30 ++++ > .../selftests/bpf/progs/test_verif_scale3.c | 30 ++++ > tools/testing/selftests/bpf/test_progs.c | 6 +- > tools/testing/selftests/bpf/test_progs.h | 1 + > tools/testing/selftests/bpf/test_verifier.c | 35 ++-- > tools/testing/selftests/bpf/verifier/ld_dw.c | 9 ++ > 18 files changed, 415 insertions(+), 57 deletions(-) > create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c > create mode 100644 tools/testing/selftests/bpf/progs/test_jhash.h > create mode 100644 tools/testing/selftests/bpf/progs/test_verif_scale1.c > create mode 100644 tools/testing/selftests/bpf/progs/test_verif_scale2.c > create mode 100644 tools/testing/selftests/bpf/progs/test_verif_scale3.c >
