• Daniel Borkmann's avatar
    bpf: add BPF_J{LT,LE,SLT,SLE} instructions · 92b31a9a
    Daniel Borkmann authored
    Currently, eBPF only understands BPF_JGT (>), BPF_JGE (>=),
    BPF_JSGT (s>), BPF_JSGE (s>=) instructions, this means that
    particularly *JLT/*JLE counterparts involving immediates need
    to be rewritten from e.g. X < [IMM] by swapping arguments into
    [IMM] > X, meaning the immediate first is required to be loaded
    into a register Y := [IMM], such that then we can compare with
    Y > X. Note that the destination operand is always required to
    be a register.
    
    This has the downside of having unnecessarily increased register
    pressure, meaning complex program would need to spill other
    registers temporarily to stack in order to obtain an unused
    register for the [IMM]. Loading to registers will thus also
    affect state pruning since we need to account for that register
    use and potentially those registers that had to be spilled/filled
    again. As a consequence slightly more stack space might have
    been used due to spilling, and BPF programs are a bit longer
    due to extra code involving the register load and potentially
    required spill/fills.
    
    Thus, add BPF_JLT (<), BPF_JLE (<=), BPF_JSLT (s<), BPF_JSLE (s<=)
    counterparts to the eBPF instruction set. Modifying LLVM to
    remove the NegateCC() workaround in a PoC patch at [1] and
    allowing it to also emit the new instructions resulted in
    cilium's BPF programs that are injected into the fast-path to
    have a reduced program length in the range of 2-3% (e.g.
    accumulated main and tail call sections from one of the object
    file reduced from 4864 to 4729 insns), reduced complexity in
    the range of 10-30% (e.g. accumulated sections reduced in one
    of the cases from 116432 to 88428 insns), and reduced stack
    usage in the range of 1-5% (e.g. accumulated sections from one
    of the object files reduced from 824 to 784b).
    
    The modification for LLVM will be incorporated in a backwards
    compatible way. Plan is for LLVM to have i) a target specific
    option to offer a possibility to explicitly enable the extension
    by the user (as we have with -m target specific extensions today
    for various CPU insns), and ii) have the kernel checked for
    presence of the extensions and enable them transparently when
    the user is selecting more aggressive options such as -march=native
    in a bpf target context. (Other frontends generating BPF byte
    code, e.g. ply can probe the kernel directly for its code
    generation.)
    
      [1] https://github.com/borkmann/llvm/tree/bpf-insnsSigned-off-by: 's avatarDaniel Borkmann <daniel@iogearbox.net>
    Acked-by: 's avatarAlexei Starovoitov <ast@kernel.org>
    Signed-off-by: 's avatarDavid S. Miller <davem@davemloft.net>
    92b31a9a