Merge branch 'bpf-next'
authorDavid S. Miller <davem@davemloft.net>
Thu, 2 Oct 2014 01:30:46 +0000 (21:30 -0400)
committerDavid S. Miller <davem@davemloft.net>
Thu, 2 Oct 2014 01:30:46 +0000 (21:30 -0400)
commitf44d61cdd3ab4259289ccf314093eb45d83a69e6
treef76249eeb9f167a7e4dd4f609447cbeb7a2b9e91
parent1b7bde6d659d30f171259cc2dfba8e5dab34e735
parentfd10c2ef3e0ad82a4003d8005f3e7716d19a9376
Merge branch 'bpf-next'

Alexei Starovoitov says:

====================
bpf: add search pruning optimization and tests

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.
====================

Signed-off-by: David S. Miller <davem@davemloft.net>