bpf: convert explored_states to hash table
authorAlexei Starovoitov <ast@kernel.org>
Wed, 22 May 2019 03:17:07 +0000 (20:17 -0700)
committerDaniel Borkmann <daniel@iogearbox.net>
Thu, 23 May 2019 23:46:22 +0000 (01:46 +0200)
commitdc2a4ebc0b44a212fcf72242210e56aa17e7317b
treee4715aaacbb75b910f1ff7c57f071fa5efec6aa4
parenta8f500af0ccffc3d2aaf9018537981cb173865a1
bpf: convert explored_states to hash table

All prune points inside a callee bpf function most likely will have
different callsites. For example, if function foo() is called from
two callsites the half of explored states in all prune points in foo()
will be useless for subsequent walking of one of those callsites.
Fortunately explored_states pruning heuristics keeps the number of states
per prune point small, but walking these states is still a waste of cpu
time when the callsite of the current state is different from the callsite
of the explored state.

To improve pruning logic convert explored_states into hash table and
use simple insn_idx ^ callsite hash to select hash bucket.
This optimization has no effect on programs without bpf2bpf calls
and drastically improves programs with calls.
In the later case it reduces total memory consumption in 1M scale tests
by almost 3 times (peak_states drops from 5752 to 2016).

Care should be taken when comparing the states for equivalency.
Since the same hash bucket can now contain states with different indices
the insn_idx has to be part of verifier_state and compared.

Different hash table sizes and different hash functions were explored,
but the results were not significantly better vs this patch.
They can be improved in the future.

Hit/miss heuristic is not counting index miscompare as a miss.
Otherwise verifier stats become unstable when experimenting
with different hash functions.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
include/linux/bpf_verifier.h
kernel/bpf/verifier.c