Skip to content

RFC bpf: inlinable kfuncs for BPF

Eduard Zingerman bpf oe-kbuild-all 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest11 patches 22 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/11bpf: use branch predictions in opt_hard_wire_dead_code_branches()include/linux/bpf_verifier.h kernel/bpf/verifier.c+15 -511 replies
2/11selftests/bpf: tests for opt_hard_wire_dead_code_branches()tools/testing/selftests/bpf/prog_tests/verifier.c tools/testing/selftests/bpf/progs/verifier_dead_code.c+65 -00 replies
3/11bpf: shared BPF/native kfuncsMakefile kernel/bpf/Makefile kernel/bpf/inlinable_kfuncs.c +1 more+680 -194 replies
4/11bpf: allow specifying inlinable kfuncs in modulesinclude/linux/bpf.h include/linux/btf.h kernel/bpf/btf.c +1 more+119 -220 replies
5/11bpf: dynamic allocation for bpf_verifier_env->subprog_infoinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+24 -80 replies
6/11bpf: KERNEL_VALUE register typeinclude/linux/bpf.h kernel/bpf/log.c kernel/bpf/verifier.c+25 -10 replies
7/11bpf: instantiate inlinable kfuncs before verificationinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+317 -340 replies
8/11bpf: special rules for kernel function calls inside inlinable kfuncskernel/bpf/verifier.c+66 -10 replies
9/11bpf: move selected dynptr kfuncs to inlinable_kfuncs.cinclude/linux/bpf.h kernel/bpf/Makefile kernel/bpf/helpers.c +1 more+148 -1310 replies
10/11selftests/bpf: tests to verify handling of inlined kfuncstools/testing/selftests/bpf/bpf_testmod/Makefile tools/testing/selftests/bpf/bpf_testmod/bpf_testmod_core.c tools/testing/selftests/bpf/bpf_testmod/test_inlinable_kfuncs.c +2 more+440 -14 replies
11/11selftests/bpf: dynptr_slice benchmarktools/testing/selftests/bpf/Makefile tools/testing/selftests/bpf/bench.c tools/testing/selftests/bpf/benchs/bench_dynptr_slice.c +1 more+109 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [RFC bpf-next 00/11] bpf: inlinable kfuncs for BPF

Some time ago, in an off-list discussion, Alexei Starovoitov suggested compiling certain kfuncs to BPF to allow inlining calls to such kfuncs during verification. This RFC explores the idea.

This RFC introduces a notion of inlinable BPF kfuncs. Inlinable kfuncs are compiled to BPF and are inlined by verifier after program verification. Inlined kfunc bodies are subject to dead code removal and removal of conditional jumps, if such jumps are proved to always follow a single branch.

Motivation
----------

The patch set uses bpf_dynptr_slice() as guinea pig, as this function is relatively complex and has a few conditionals that could be removed most of the times. The function has the following structure:

    void *bpf_dynptr_slice(const struct bpf_dynptr *p, u32 offset,
                           void *buffer__opt, u32 buffer__szk)
    {
        ...
        type = bpf_dynptr_get_type(ptr);

        switch (type) {
        ...
        case BPF_DYNPTR_TYPE_SKB:
                if (buffer__opt)
                        return skb_header_pointer(...);
                else
                        return skb_pointer_if_linear(...);
        ...
    }

Parameters 'type' and 'buffer__opt' are most likely to be known at callsite, and thus the function could be inlined w/o 'switch' and 'if' checks above.

This has a measurable speedup on microbenchmark, e.g. a simple test measuring number of bpf_dynptr_slice() executions per second shows ~1.5 speedup compared to master (see last patch in the series). Granted, real world programs do some other work beside slice calls.

Mechanism
---------

Implementation pursues three main goals:
- avoid differences in program verification whether or not certain kfunc is inlinable;
- predict branches in inlined kfuncs bodies;
- allow inlined kfunc bodies to do arbitrary computations.

The goals are achieved in the following steps:
- Inlinable kfuncs are defined in kernel/bpf/inlinable_kfuncs.c.
- In order to include kernel headers as-is the C file is compiled to llvm bitcode targeting native architecture and then to BPF elf object using llc utility.
- BPF elf object is embedded in kernel data section.
- At kernel initialization time the elf object is parsed and functions defined in the object are deemed to be inlinable kfuncs.
- Before main verification pass, for each inlinable kfunc callsite, inlinable kfunc is cloned as a hidden subprogram. Such subprograms are called kfunc instances.
- A new KERNEL_VALUE register type is added:
- ALU operations on any type and KERNEL_VALUE return KERNEL_VALUE;
- load / store operations with base register having type KERNEL_VALUE return KERNEL_VALUE.
- During main verification pass:
- inlinable kfunc calls are verified as regular kfunc calls;
- the bodies of the corresponding kfunc instances are visited in a "distilled" context:
- no caller stack frame;
- scalar or null pointer r1-r5 from caller stack frame are copied to instance call frame verbatim;
- pointer to dynptr r1-r5 from caller stack frame are represented in the instance call frame as pointers to a fake stack frame. For each dynptr this fake stack frame contains two register spills:
- one scalar for 'size' field, which also encodes type;
- one KERNEL_VALUE for 'data' field;
- r1-r5 of all other types are represented in the instance call frame as KERNEL_VALUEs;
- when 'exit' instruction within kfunc instance body is processed, verification for the current path is assumed complete.
- After main verification pass:
- rely on existing passes opt_hard_wire_dead_code_branches() and

    opt_remove_dead_code() to simplify kfunc instance bodies;

- calls to inlinable kfuncs are replaced with corresponding kfunc instance bodies, instance subprograms are removed.

Patch-set structure
-------------------

Implementation of the above mechanics is split in several patches to simplify the review. The following patches are most interesting:

- "bpf: shared BPF/native kfuncs":
Build system integration and kfuncs inlining after verification.

- "bpf: KERNEL_VALUE register type"
Adds an opaque type for registers that could be used for ALU and memory access.

- "bpf: allow specifying inlinable kfuncs in modules" This is mostly for tests: for testing purposes it is necessary to control exact assembly code for both test case calling kfunc and kfunc itself.

- "bpf: instantiate inlinable kfuncs before verification" Adds a pass that clones inlinable kfunc bodies as hidden subprograms, one subprogram per callsite.

- "bpf: special rules for kernel function calls inside inlinable kfuncs" Allows to call arbitrary kernel functions from kfunc instances.

Limitations
-----------

Some existing verifier restrictions are not lifted for inlinable kfuncs:
- stack is limited to 512 bytes;
- max 8 call frames (7 with the fake call frame);
- loops are still verified in a "brute force" way;
- instructions processed for kfunc instances are counted in 1M instructions budget.

The list is probably not exhaustive.

TODO items
----------

The following items are currently on the TODO list:
- consider getting rid of bpftool linking phase for BPF elf object;
- consider getting rid of clang->bitcode->llc->elf dance;
- make bpf_dynptr_from_skb() inlinable and allow passing objects state between kfunc instances, thus avoiding special case for dynptr;
- determine the set of kfuncs for which inlining makes sense.

Alternatives
------------

Imo, this RFC is worth following through only if number of kfuncs benefiting from inlining is big. If the set is limited to dynptr family of functions, it is simpler to add a number of hard-coded inlining templates for such functions (similarly to what is currently done for some helpers).

Eduard Zingerman (11):
bpf: use branch predictions in opt_hard_wire_dead_code_branches() selftests/bpf: tests for opt_hard_wire_dead_code_branches()
bpf: shared BPF/native kfuncs
bpf: allow specifying inlinable kfuncs in modules
bpf: dynamic allocation for bpf_verifier_env->subprog_info
bpf: KERNEL_VALUE register type
bpf: instantiate inlinable kfuncs before verification
bpf: special rules for kernel function calls inside inlinable kfuncs
bpf: move selected dynptr kfuncs to inlinable_kfuncs.c selftests/bpf: tests to verify handling of inlined kfuncs selftests/bpf: dynptr_slice benchmark

 Makefile                                      |   22 +-
 include/linux/bpf.h                           |   40 +-
 include/linux/bpf_verifier.h                  |   12 +-
 include/linux/btf.h                           |    7 +
 kernel/bpf/Makefile                           |   25 +-
 kernel/bpf/btf.c                              |    2 +-
 kernel/bpf/helpers.c                          |  130 +-
 kernel/bpf/inlinable_kfuncs.c                 |  113 ++
 kernel/bpf/log.c                              |    1 +
 kernel/bpf/verifier.c                         | 1187 ++++++++++++++++-
 tools/testing/selftests/bpf/Makefile          |    2 +
 tools/testing/selftests/bpf/bench.c           |    2 +
 .../selftests/bpf/benchs/bench_dynptr_slice.c |   76 ++
 .../selftests/bpf/bpf_testmod/Makefile        |   24 +-
 .../{bpf_testmod.c => bpf_testmod_core.c}     |   25 +
 .../bpf/bpf_testmod/test_inlinable_kfuncs.c   |  132 ++
 .../selftests/bpf/prog_tests/verifier.c       |    9 +
 .../selftests/bpf/progs/dynptr_slice_bench.c  |   29 +
 .../selftests/bpf/progs/verifier_dead_code.c  |   63 +
 .../bpf/progs/verifier_inlinable_kfuncs.c     |  253 ++++
 20 files changed, 1970 insertions(+), 184 deletions(-)
 create mode 100644 kernel/bpf/inlinable_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_dynptr_slice.c
 rename tools/testing/selftests/bpf/bpf_testmod/{bpf_testmod.c => bpf_testmod_core.c} (97%)
 create mode 100644 tools/testing/selftests/bpf/bpf_testmod/test_inlinable_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/dynptr_slice_bench.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_dead_code.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_inlinable_kfuncs.c
Signature · 1 line
2.47.0