• Alexei Starovoitov's avatar
    bpf: introduce function calls (verification) · f4d7e40a
    Alexei Starovoitov authored
    Allow arbitrary function calls from bpf function to another bpf function.
    
    To recognize such set of bpf functions the verifier does:
    1. runs control flow analysis to detect function boundaries
    2. proceeds with verification of all functions starting from main(root) function
    It recognizes that the stack of the caller can be accessed by the callee
    (if the caller passed a pointer to its stack to the callee) and the callee
    can store map_value and other pointers into the stack of the caller.
    3. keeps track of the stack_depth of each function to make sure that total
    stack depth is still less than 512 bytes
    4. disallows pointers to the callee stack to be stored into the caller stack,
    since they will be invalid as soon as the callee returns
    5. to reuse all of the existing state_pruning logic each function call
    is considered to be independent call from the verifier point of view.
    The verifier pretends to inline all function calls it sees are being called.
    It stores the callsite instruction index as part of the state to make sure
    that two calls to the same callee from two different places in the caller
    will be different from state pruning point of view
    6. more safety checks are added to liveness analysis
    
    Implementation details:
    . struct bpf_verifier_state is now consists of all stack frames that
      led to this function
    . struct bpf_func_state represent one stack frame. It consists of
      registers in the given frame and its stack
    . propagate_liveness() logic had a premature optimization where
      mark_reg_read() and mark_stack_slot_read() were manually inlined
      with loop iterating over parents for each register or stack slot.
      Undo this optimization to reuse more complex mark_*_read() logic
    . skip_callee() logic is not necessary from safety point of view,
      but without it mark_*_read() markings become too conservative,
      since after returning from the funciton call a read of r6-r9
      will incorrectly propagate the read marks into callee causing
      inefficient pruning later
    . mark_*_read() logic is now aware of control flow which makes it
      more complex. In the future the plan is to rewrite liveness
      to be hierarchical. So that liveness can be done within
      basic block only and control flow will be responsible for
      propagation of liveness information along cfg and between calls.
    . tail_calls and ld_abs insns are not allowed in the programs with
      bpf-to-bpf calls
    . returning stack pointers to the caller or storing them into stack
      frame of the caller is not allowed
    
    Testing:
    . no difference in cilium processed_insn numbers
    . large number of tests follows in next patches
    Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    Acked-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
    Acked-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    f4d7e40a
verifier.c 151 KB