Skip to content

bpf: improve verifier scalability

Alexei Starovoitov bpf netdev 2 versions – Applied

Status from this message: Applied, thanks! As discussed offline a bit with Alexei wrt to prior

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v2 Latest10 patches 1 replyApplied
  2. v17 patches 12 repliesSuperseded

Changes in v2 from the cover letter

- 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

Patches in v2 Applied

#Subject and filesSizeRepliesApplied
1/10bpf: add verifier stats and log_level bit 2include/linux/bpf_verifier.h kernel/bpf/verifier.c+73 -240 replies
2/10bpf: improve verification speed by droping statesinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+43 -30 replies
3/10bpf: improve verification speed by not remarking live_readkernel/bpf/verifier.c+9 -00 replies
4/10bpf: convert temp arrays to kvcallockernel/bpf/verifier.c+7 -70 replies
5/10bpf: verbose jump offset overflow checkkernel/bpf/core.c kernel/bpf/verifier.c+12 -60 replies
6/10bpf: increase complexity limit and maximum program sizeinclude/linux/bpf.h kernel/bpf/syscall.c kernel/bpf/verifier.c+3 -20 replies
7/10bpf: increase verifier log limitkernel/bpf/verifier.c+1 -10 replies
8/10libbpf: teach libbpf about log_level bit 2tools/lib/bpf/bpf.c tools/lib/bpf/bpf.h tools/lib/bpf/libbpf.c +1 more+17 -40 replies
9/10selftests/bpf: add few verifier scale teststools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c tools/testing/selftests/bpf/progs/test_jhash.h tools/testing/selftests/bpf/progs/test_verif_scale1.c +4 more+215 -10 replies
10/10selftests/bpf: synthetic tests to push verifier limitstools/testing/selftests/bpf/test_verifier.c tools/testing/selftests/bpf/verifier/ld_dw.c+35 -90 replies

Reviews trailers per patch

3 of 10 patches have a Reviewed-by or Acked-by.

PatchJakub KicinskiEdward Cree
1/10
2/10R-b
3/10R-b R-b
4/10
5/10
6/10
7/10R-b
8/10
9/10
10/10

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v2 thread

Cover letter [PATCH v2 bpf-next 00/10] bpf: improve verifier scalability

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.

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
Signature · 1 line
2.20.0