• Alexei Starovoitov's avatar
    bpf: convert explored_states to hash table · dc2a4ebc
    Alexei Starovoitov authored
    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: default avatarAlexei Starovoitov <ast@kernel.org>
    Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    dc2a4ebc
bpf_verifier.h 12.3 KB