• Alexei Starovoitov's avatar
    bpf: Introduce function-by-function verification · 51c39bb1
    Alexei Starovoitov authored
    New llvm and old llvm with libbpf help produce BTF that distinguish global and
    static functions. Unlike arguments of static function the arguments of global
    functions cannot be removed or optimized away by llvm. The compiler has to use
    exactly the arguments specified in a function prototype. The argument type
    information allows the verifier validate each global function independently.
    For now only supported argument types are pointer to context and scalars. In
    the future pointers to structures, sizes, pointer to packet data can be
    supported as well. Consider the following example:
    
    static int f1(int ...)
    {
      ...
    }
    
    int f3(int b);
    
    int f2(int a)
    {
      f1(a) + f3(a);
    }
    
    int f3(int b)
    {
      ...
    }
    
    int main(...)
    {
      f1(...) + f2(...) + f3(...);
    }
    
    The verifier will start its safety checks from the first global function f2().
    It will recursively descend into f1() because it's static. Then it will check
    that arguments match for the f3() invocation inside f2(). It will not descend
    into f3(). It will finish f2() that has to be successfully verified for all
    possible values of 'a'. Then it will proceed with f3(). That function also has
    to be safe for all possible values of 'b'. Then it will start subprog 0 (which
    is main() function). It will recursively descend into f1() and will skip full
    check of f2() and f3(), since they are global. The order of processing global
    functions doesn't affect safety, since all global functions must be proven safe
    based on their arguments only.
    
    Such function by function verification can drastically improve speed of the
    verification and reduce complexity.
    
    Note that the stack limit of 512 still applies to the call chain regardless whether
    functions were static or global. The nested level of 8 also still applies. The
    same recursion prevention checks are in place as well.
    
    The type information and static/global kind is preserved after the verification
    hence in the above example global function f2() and f3() can be replaced later
    by equivalent functions with the same types that are loaded and verified later
    without affecting safety of this main() program. Such replacement (re-linking)
    of global functions is a subject of future patches.
    Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    Acked-by: default avatarSong Liu <songliubraving@fb.com>
    Link: https://lore.kernel.org/bpf/20200110064124.1760511-3-ast@kernel.org
    51c39bb1
verifier.c 287 KB