Skip to content

bpf: add search pruning optimization and tests

Alexei Starovoitov lkml netdev 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest2 patches 1 replyIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2bpf: add search pruning optimization to verifierkernel/bpf/verifier.c+146 -00 replies
2/2bpf: add tests to verifier testsuitesamples/bpf/test_verifier.c+130 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH net-next 0/2] bpf: add search pruning optimization and tests

Hi All,

patch #1 commit log explains why eBPF verifier has to examine some instructions multiple times and describes the search pruning optimization that improves verification speed for branchy programs and allows more complex programs to be verified successfully.
This patch completes the core verifier logic.

patch #2 adds more verifier tests related to branches and search pruning

I'm still working on Andy's 'bitmask for stack slots' suggestion. It will be done on top of this patch.

The current verifier algorithm is brute force depth first search with state pruning. If anyone can come up with another algorithm that demonstrates better results, we'll replace the algorithm without affecting user space.

Note verifier doesn't guarantee that all possible valid programs are accepted. Overly complex programs may still be rejected.
Verifier improvements/optimizations will guarantee that if a program was passing verification in the past, it will still be passing.

Alexei Starovoitov (2):
bpf: add search pruning optimization to verifier
bpf: add tests to verifier testsuite

 kernel/bpf/verifier.c       |  146 +++++++++++++++++++++++++++++++++++++++++++
 samples/bpf/test_verifier.c |  130 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 276 insertions(+)
Signature · 1 line
1.7.9.5