1. 21 Jun, 2022 9 commits
    • Jakub Sitnicki's avatar
      bpf, arm64: Keep tail call count across bpf2bpf calls · d4609a5d
      Jakub Sitnicki authored
      Today doing a BPF tail call after a BPF to BPF call, that is from a
      subprogram, is allowed only by the x86-64 BPF JIT. Mixing these features
      requires support from JIT. Tail call count has to be tracked through BPF to
      BPF calls, as well as through BPF tail calls to prevent unbounded chains of
      tail calls.
      
      arm64 BPF JIT stores the tail call count (TCC) in a dedicated
      register (X26). This makes it easier to support bpf2bpf calls mixed with
      tail calls than on x86 platform.
      
      In order to keep the tail call count in tact throughout bpf2bpf calls, all
      we need to do is tweak the program prologue generator. When emitting
      prologue for a subprogram, we skip the block that initializes the tail call
      count and emits a jump pad for the tail call.
      
      With this change, a sample execution flow where a bpf2bpf call is followed
      by a tail call would look like so:
      
      int entry(struct __sk_buff *skb):
         0xffffffc0090151d4:  paciasp
         0xffffffc0090151d8:  stp     x29, x30, [sp, #-16]!
         0xffffffc0090151dc:  mov     x29, sp
         0xffffffc0090151e0:  stp     x19, x20, [sp, #-16]!
         0xffffffc0090151e4:  stp     x21, x22, [sp, #-16]!
         0xffffffc0090151e8:  stp     x25, x26, [sp, #-16]!
         0xffffffc0090151ec:  stp     x27, x28, [sp, #-16]!
         0xffffffc0090151f0:  mov     x25, sp
         0xffffffc0090151f4:  mov     x26, #0x0                       // <- init TCC only
         0xffffffc0090151f8:  bti     j                               //    in main prog
         0xffffffc0090151fc:  sub     x27, x25, #0x0
         0xffffffc009015200:  sub     sp, sp, #0x10
         0xffffffc009015204:  mov     w1, #0x0
         0xffffffc009015208:  mov     x10, #0xffffffffffffffff
         0xffffffc00901520c:  strb    w1, [x25, x10]
         0xffffffc009015210:  mov     x10, #0xffffffffffffd25c
         0xffffffc009015214:  movk    x10, #0x902, lsl #16
         0xffffffc009015218:  movk    x10, #0xffc0, lsl #32
         0xffffffc00901521c:  blr     x10 -------------------.        // bpf2bpf call
         0xffffffc009015220:  add     x7, x0, #0x0 <-------------.
         0xffffffc009015224:  add     sp, sp, #0x10          |   |
         0xffffffc009015228:  ldp     x27, x28, [sp], #16    |   |
         0xffffffc00901522c:  ldp     x25, x26, [sp], #16    |   |
         0xffffffc009015230:  ldp     x21, x22, [sp], #16    |   |
         0xffffffc009015234:  ldp     x19, x20, [sp], #16    |   |
         0xffffffc009015238:  ldp     x29, x30, [sp], #16    |   |
         0xffffffc00901523c:  add     x0, x7, #0x0           |   |
         0xffffffc009015240:  autiasp                        |   |
         0xffffffc009015244:  ret                            |   |
                                                             |   |
      int subprog_tail(struct __sk_buff *skb):               |   |
         0xffffffc00902d25c:  paciasp <----------------------'   |
         0xffffffc00902d260:  stp     x29, x30, [sp, #-16]!      |
         0xffffffc00902d264:  mov     x29, sp                    |
         0xffffffc00902d268:  stp     x19, x20, [sp, #-16]!      |
         0xffffffc00902d26c:  stp     x21, x22, [sp, #-16]!      |
         0xffffffc00902d270:  stp     x25, x26, [sp, #-16]!      |
         0xffffffc00902d274:  stp     x27, x28, [sp, #-16]!      |
         0xffffffc00902d278:  mov     x25, sp                    |
         0xffffffc00902d27c:  sub     x27, x25, #0x0             |
         0xffffffc00902d280:  sub     sp, sp, #0x10              |    // <- end of prologue, notice:
         0xffffffc00902d284:  add     x19, x0, #0x0              |    //    1) TCC not touched, and
         0xffffffc00902d288:  mov     w0, #0x1                   |    //    2) no tail call jump pad
         0xffffffc00902d28c:  mov     x10, #0xfffffffffffffffc   |
         0xffffffc00902d290:  str     w0, [x25, x10]             |
         0xffffffc00902d294:  mov     x20, #0xffffff80ffffffff   |
         0xffffffc00902d298:  movk    x20, #0xc033, lsl #16      |
         0xffffffc00902d29c:  movk    x20, #0x4e00               |
         0xffffffc00902d2a0:  add     x0, x19, #0x0              |
         0xffffffc00902d2a4:  add     x1, x20, #0x0              |
         0xffffffc00902d2a8:  mov     x2, #0x0                   |
         0xffffffc00902d2ac:  mov     w10, #0x24                 |
         0xffffffc00902d2b0:  ldr     w10, [x1, x10]             |
         0xffffffc00902d2b4:  add     w2, w2, #0x0               |
         0xffffffc00902d2b8:  cmp     w2, w10                    |
         0xffffffc00902d2bc:  b.cs    0xffffffc00902d2f8         |
         0xffffffc00902d2c0:  mov     w10, #0x21                 |
         0xffffffc00902d2c4:  cmp     x26, x10                   |    // TCC >= MAX_TAIL_CALL_CNT?
         0xffffffc00902d2c8:  b.cs    0xffffffc00902d2f8         |
         0xffffffc00902d2cc:  add     x26, x26, #0x1             |    // TCC++
         0xffffffc00902d2d0:  mov     w10, #0x110                |
         0xffffffc00902d2d4:  add     x10, x1, x10               |
         0xffffffc00902d2d8:  lsl     x11, x2, #3                |
         0xffffffc00902d2dc:  ldr     x11, [x10, x11]            |
         0xffffffc00902d2e0:  cbz     x11, 0xffffffc00902d2f8    |
         0xffffffc00902d2e4:  mov     w10, #0x30                 |
         0xffffffc00902d2e8:  ldr     x10, [x11, x10]            |
         0xffffffc00902d2ec:  add     x10, x10, #0x24            |
         0xffffffc00902d2f0:  add     sp, sp, #0x10              |    // <- destroy just current
         0xffffffc00902d2f4:  br      x10 ---------------------. |    //    BPF stack frame
         0xffffffc00902d2f8:  mov     x10, #0xfffffffffffffffc | |    //    before the tail call
         0xffffffc00902d2fc:  ldr     w7, [x25, x10]           | |
         0xffffffc00902d300:  add     sp, sp, #0x10            | |
         0xffffffc00902d304:  ldp     x27, x28, [sp], #16      | |
         0xffffffc00902d308:  ldp     x25, x26, [sp], #16      | |
         0xffffffc00902d30c:  ldp     x21, x22, [sp], #16      | |
         0xffffffc00902d310:  ldp     x19, x20, [sp], #16      | |
         0xffffffc00902d314:  ldp     x29, x30, [sp], #16      | |
         0xffffffc00902d318:  add     x0, x7, #0x0             | |
         0xffffffc00902d31c:  autiasp                          | |
         0xffffffc00902d320:  ret                              | |
                                                               | |
      int classifier_0(struct __sk_buff *skb):                 | |
         0xffffffc008ff5874:  paciasp                          | |
         0xffffffc008ff5878:  stp     x29, x30, [sp, #-16]!    | |
         0xffffffc008ff587c:  mov     x29, sp                  | |
         0xffffffc008ff5880:  stp     x19, x20, [sp, #-16]!    | |
         0xffffffc008ff5884:  stp     x21, x22, [sp, #-16]!    | |
         0xffffffc008ff5888:  stp     x25, x26, [sp, #-16]!    | |
         0xffffffc008ff588c:  stp     x27, x28, [sp, #-16]!    | |
         0xffffffc008ff5890:  mov     x25, sp                  | |
         0xffffffc008ff5894:  mov     x26, #0x0                | |
         0xffffffc008ff5898:  bti     j <----------------------' |
         0xffffffc008ff589c:  sub     x27, x25, #0x0             |
         0xffffffc008ff58a0:  sub     sp, sp, #0x0               |
         0xffffffc008ff58a4:  mov     x0, #0xffffffc0ffffffff    |
         0xffffffc008ff58a8:  movk    x0, #0x8fc, lsl #16        |
         0xffffffc008ff58ac:  movk    x0, #0x6000                |
         0xffffffc008ff58b0:  mov     w1, #0x1                   |
         0xffffffc008ff58b4:  str     w1, [x0]                   |
         0xffffffc008ff58b8:  mov     w7, #0x0                   |
         0xffffffc008ff58bc:  mov     sp, sp                     |
         0xffffffc008ff58c0:  ldp     x27, x28, [sp], #16        |
         0xffffffc008ff58c4:  ldp     x25, x26, [sp], #16        |
         0xffffffc008ff58c8:  ldp     x21, x22, [sp], #16        |
         0xffffffc008ff58cc:  ldp     x19, x20, [sp], #16        |
         0xffffffc008ff58d0:  ldp     x29, x30, [sp], #16        |
         0xffffffc008ff58d4:  add     x0, x7, #0x0               |
         0xffffffc008ff58d8:  autiasp                            |
         0xffffffc008ff58dc:  ret -------------------------------'
      Signed-off-by: default avatarJakub Sitnicki <jakub@cloudflare.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Link: https://lore.kernel.org/bpf/20220617105735.733938-3-jakub@cloudflare.com
      d4609a5d
    • Tony Ambardar's avatar
      bpf, x64: Add predicate for bpf2bpf with tailcalls support in JIT · 95acd881
      Tony Ambardar authored
      The BPF core/verifier is hard-coded to permit mixing bpf2bpf and tail
      calls for only x86-64. Change the logic to instead rely on a new weak
      function 'bool bpf_jit_supports_subprog_tailcalls(void)', which a capable
      JIT backend can override.
      
      Update the x86-64 eBPF JIT to reflect this.
      Signed-off-by: default avatarTony Ambardar <Tony.Ambardar@gmail.com>
      [jakub: drop MIPS bits and tweak patch subject]
      Signed-off-by: default avatarJakub Sitnicki <jakub@cloudflare.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Link: https://lore.kernel.org/bpf/20220617105735.733938-2-jakub@cloudflare.com
      95acd881
    • Alexei Starovoitov's avatar
      Merge branch 'bpf_loop inlining' · b40b414e
      Alexei Starovoitov authored
      Eduard Zingerman says:
      
      ====================
      
      Hi Everyone,
      
      This is the next iteration of the patch. It includes changes suggested
      by Song, Joanne and Alexei. Please find updated intro message and
      change log below.
      
      This patch implements inlining of calls to bpf_loop helper function
      when bpf_loop's callback is statically known. E.g. the rewrite does
      the following transformation during BPF program processing:
      
        bpf_loop(10, foo, NULL, 0);
      
       ->
      
        for (int i = 0; i < 10; ++i)
          foo(i, NULL);
      
      The transformation leads to measurable latency change for simple
      loops. Measurements using `benchs/run_bench_bpf_loop.sh` inside QEMU /
      KVM on i7-4710HQ CPU show a drop in latency from 14 ns/op to 2 ns/op.
      
      The change is split in five parts:
      
      * Update to test_verifier.c to specify expected and unexpected
        instruction sequences. This allows to check BPF program rewrites
        applied by e.g. do_mix_fixups function.
      
      * Update to test_verifier.c to specify BTF function infos and types
        per test case. This is necessary for tests that load sub-program
        addresses to a variable because of the checks applied by
        check_ld_imm function.
      
      * The update to verifier.c that tracks state of the parameters for
        each bpf_loop call in a program and decides whether it could be
        replaced by a loop.
      
      * A set of test cases for `test_verifier` that use capabilities added
        by the first two patches to verify instructions produced by inlining
        logic.
      
      * Two test cases for `test_prog` to check that possible corner cases
        behave as expected.
      
      Additional details are available in commit messages for each patch.
      
      Changes since v7:
       - Call to `mark_chain_precision` is added in `loop_flag_is_zero` to
         avoid potential issues with state pruning and precision tracking.
       - `flags non-zero` test_verifier test case is updated to have two
         execution paths reaching `bpf_loop` call, one with flags = 0,
         another with flags = 1. Potentially this test case should be able
         to show that call to `mark_chain_precision` is necessary in
         `loop_flag_is_zero` but not at the moment. Please refer to
         discussion for [PATCH bpf-next v7 3/5] for additional details.
       - `stack_depth_extra` computation is updated to guarantee that R6, R7
         and R8 offsets are always aligned on 8 byte boundary.
       - `stack locations for loop vars` test_verifier test case updated to
         show that R6, R7, R8 offsets are indeed aligned when function stack
         depth is not a multiple of 8.
       - I removed Song Liu's ACK from commit message for [PATCH bpf-next v8
         4/5] because I updated the patch. (Please let me know if I had to
         keep the ACK tag).
      
      Changes since v6:
       - Return value of the `optimize_bpf_loop` function is no longer
         ignored. This is necessary to properly propagate -ENOMEM error.
      
      Changes since v5:
       - Added function `loop_flag_is_zero` to skip a few checks in
         `update_loop_inline_state` when loop instruction is not fit for
         inline.
      
      Changes since v4:
       - Added missing `static` modifier for `update_loop_inline_state` and
         `inline_bpf_loop` functions.
       - `update_loop_inline_state` updated for better readability.
       - Fields `initialized` and `fit_for_inline` of `struct
         bpf_loop_inline_state` are changed back from `bool` to bitfields.
       - Acks from Song Liu added to comments for patches 1/5, 2/5, 4/5,
         5/5.
      
      Changes since v3:
       - Function `adjust_stack_depth_for_loop_inlining` is replaced by
         function `optimize_bpf_loop`. Function `optimize_bpf_loop` is
         responsible for both stack depth adjustment and call instruction
         replacement.
       - Changes in `do_misc_fixups` are reverted.
       - Changes in `adjust_subprog_starts_after_remove` are reverted and
         function `adjust_loop_inline_subprogno` is removed. This is
         possible because call to `optimize_bpf_loop` is placed before the
         dead code removal in `opt_remove_dead_code` (in contrast to the
         position of `do_misc_fixups` where inlining was done in v3).
       - Field `bpf_insn_aux_data.loop_inline_state` is now a part of
         anonymous union at the start of the `bpf_insn_aux_data`.
       - Data structure `bpf_loop_inline_state` is simplified to use single
         flag field `fit_for_inline` instead of separate fields
         `flags_is_zero` & `callback_is_constant`.
       - Macro definition `BPF_MAX_LOOPS` is moved from
         `include/linux/bpf_verifier.h` to `include/linux/bpf.h` to avoid
         include of `include/linux/bpf_verifier.h` in `bpf_iter.c`.
       - `inline_bpf_loop` changed back to use array initialization and hard
         coded offsets as in v2.
       - Style / formatting updates.
      
      Changes since v2:
       - fix for `stack_check` test case in `test_progs-no_alu32`, all tests
         are passing now;
       - v2 3/3 patch is split in three parts:
         - kernel changes
         - test_verifier changes
         - test_prog changes
       - updated `inline_bpf_loop` in `verifier.c` to calculate each offset
         used in instructions to avoid "magic" numbers;
       - removed newline handling logic in `fail_log` branch of
         `do_single_test` in `test_verifier.c` to simplify the patch set;
       - styling fixes suggested in review for v2 of this patch set.
      
      Changes since v1:
       - allow to use SKIP_INSNS in instruction pattern specification in
         test_verifier tests;
       - fix for a bug in spill offset assignement for loop vars when
         bpf_loop is located in a non-main function.
      ====================
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      b40b414e
    • Eduard Zingerman's avatar
      selftests/bpf: BPF test_prog selftests for bpf_loop inlining · 0e1bf9ed
      Eduard Zingerman authored
      Two new test BPF programs for test_prog selftests checking bpf_loop
      behavior. Both are corner cases for bpf_loop inlinig transformation:
       - check that bpf_loop behaves correctly when callback function is not
         a compile time constant
       - check that local function variables are not affected by allocating
         additional stack storage for registers spilled by loop inlining
      Signed-off-by: default avatarEduard Zingerman <eddyz87@gmail.com>
      Acked-by: default avatarSong Liu <songliubraving@fb.com>
      Link: https://lore.kernel.org/r/20220620235344.569325-6-eddyz87@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      0e1bf9ed
    • Eduard Zingerman's avatar
      selftests/bpf: BPF test_verifier selftests for bpf_loop inlining · f8acfdd0
      Eduard Zingerman authored
      A number of test cases for BPF selftests test_verifier to check how
      bpf_loop inline transformation rewrites the BPF program. The following
      cases are covered:
       - happy path
       - no-rewrite when flags is non-zero
       - no-rewrite when callback is non-constant
       - subprogno in insn_aux is updated correctly when dead sub-programs
         are removed
       - check that correct stack offsets are assigned for spilling of R6-R8
         registers
      Signed-off-by: default avatarEduard Zingerman <eddyz87@gmail.com>
      Acked-by: default avatarSong Liu <songliubraving@fb.com>
      Link: https://lore.kernel.org/r/20220620235344.569325-5-eddyz87@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      f8acfdd0
    • Eduard Zingerman's avatar
      bpf: Inline calls to bpf_loop when callback is known · 1ade2371
      Eduard Zingerman authored
      Calls to `bpf_loop` are replaced with direct loops to avoid
      indirection. E.g. the following:
      
        bpf_loop(10, foo, NULL, 0);
      
      Is replaced by equivalent of the following:
      
        for (int i = 0; i < 10; ++i)
          foo(i, NULL);
      
      This transformation could be applied when:
      - callback is known and does not change during program execution;
      - flags passed to `bpf_loop` are always zero.
      
      Inlining logic works as follows:
      
      - During execution simulation function `update_loop_inline_state`
        tracks the following information for each `bpf_loop` call
        instruction:
        - is callback known and constant?
        - are flags constant and zero?
      - Function `optimize_bpf_loop` increases stack depth for functions
        where `bpf_loop` calls can be inlined and invokes `inline_bpf_loop`
        to apply the inlining. The additional stack space is used to spill
        registers R6, R7 and R8. These registers are used as loop counter,
        loop maximal bound and callback context parameter;
      
      Measurements using `benchs/run_bench_bpf_loop.sh` inside QEMU / KVM on
      i7-4710HQ CPU show a drop in latency from 14 ns/op to 2 ns/op.
      Signed-off-by: default avatarEduard Zingerman <eddyz87@gmail.com>
      Acked-by: default avatarSong Liu <songliubraving@fb.com>
      Link: https://lore.kernel.org/r/20220620235344.569325-4-eddyz87@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      1ade2371
    • Eduard Zingerman's avatar
      selftests/bpf: allow BTF specs and func infos in test_verifier tests · 7a42008c
      Eduard Zingerman authored
      The BTF and func_info specification for test_verifier tests follows
      the same notation as in prog_tests/btf.c tests. E.g.:
      
        ...
        .func_info = { { 0, 6 }, { 8, 7 } },
        .func_info_cnt = 2,
        .btf_strings = "\0int\0",
        .btf_types = {
          BTF_TYPE_INT_ENC(1, BTF_INT_SIGNED, 0, 32, 4),
          BTF_PTR_ENC(1),
        },
        ...
      
      The BTF specification is loaded only when specified.
      Signed-off-by: default avatarEduard Zingerman <eddyz87@gmail.com>
      Acked-by: default avatarSong Liu <songliubraving@fb.com>
      Link: https://lore.kernel.org/r/20220620235344.569325-3-eddyz87@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      7a42008c
    • Eduard Zingerman's avatar
      selftests/bpf: specify expected instructions in test_verifier tests · 933ff531
      Eduard Zingerman authored
      Allows to specify expected and unexpected instruction sequences in
      test_verifier test cases. The instructions are requested from kernel
      after BPF program loading, thus allowing to check some of the
      transformations applied by BPF verifier.
      
      - `expected_insn` field specifies a sequence of instructions expected
        to be found in the program;
      - `unexpected_insn` field specifies a sequence of instructions that
        are not expected to be found in the program;
      - `INSN_OFF_MASK` and `INSN_IMM_MASK` values could be used to mask
        `off` and `imm` fields.
      - `SKIP_INSNS` could be used to specify that some instructions in the
        (un)expected pattern are not important (behavior similar to usage of
        `\t` in `errstr` field).
      
      The intended usage is as follows:
      
        {
      	"inline simple bpf_loop call",
      	.insns = {
      	/* main */
      	BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 1),
      	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2,
      			BPF_PSEUDO_FUNC, 0, 6),
          ...
      	BPF_EXIT_INSN(),
      	/* callback */
      	BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
      	BPF_EXIT_INSN(),
      	},
      	.expected_insns = {
      	BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 1),
      	SKIP_INSNS(),
      	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 8, 1)
      	},
      	.unexpected_insns = {
      	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0,
      			INSN_OFF_MASK, INSN_IMM_MASK),
      	},
      	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
      	.result = ACCEPT,
      	.runs = 0,
        },
      
      Here it is expected that move of 1 to register 1 would remain in place
      and helper function call instruction would be replaced by a relative
      call instruction.
      Signed-off-by: default avatarEduard Zingerman <eddyz87@gmail.com>
      Acked-by: default avatarSong Liu <songliubraving@fb.com>
      Link: https://lore.kernel.org/r/20220620235344.569325-2-eddyz87@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      933ff531
    • Delyan Kratunov's avatar
      uprobe: gate bpf call behind BPF_EVENTS · aca80dd9
      Delyan Kratunov authored
      The call into bpf from uprobes needs to be gated now that it doesn't use
      the trace_events.h helpers.
      
      Randy found this as a randconfig build failure on linux-next [1].
      
        [1]: https://lore.kernel.org/linux-next/2de99180-7d55-2fdf-134d-33198c27cc58@infradead.org/Reported-by: default avatarRandy Dunlap <rdunlap@infradead.org>
      Signed-off-by: default avatarDelyan Kratunov <delyank@fb.com>
      Tested-by: default avatarRandy Dunlap <rdunlap@infradead.org>
      Acked-by: default avatarRandy Dunlap <rdunlap@infradead.org>
      Link: https://lore.kernel.org/r/cb8bfbbcde87ed5d811227a393ef4925f2aadb7b.camel@fb.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      aca80dd9
  2. 20 Jun, 2022 23 commits
  3. 19 Jun, 2022 8 commits