bpf_loop inlining

Signed-off-by Eduard Zingerman <[email protected]>

---
 tools/testing/selftests/bpf/test_verifier.c | 222 ++++++++++++++++++++
 1 file changed, 222 insertions(+)

tools/testing/selftests/bpf/test_verifier.c +2 -0

index 372579c9f45e..373f7661f4d0 100644
@@ -51,6 +51,8 @@
 #endif
 
 #define MAX_INSNS      BPF_MAXINSNS
+#define MAX_EXPECTED_INSNS     32
+#define MAX_UNEXPECTED_INSNS   32
 #define MAX_TEST_INSNS 1000000
 #define MAX_FIXUPS     8
 #define MAX_NR_MAPS    23

tools/testing/selftests/bpf/test_verifier.c +15 -0

+#define SKIP_INSNS()   BPF_RAW_INSN(0xde, 0xa, 0xd, 0xbeef, 0xdeadbeef)
+
 #define F_NEEDS_EFFICIENT_UNALIGNED_ACCESS     (1 << 0)
 #define F_LOAD_WITH_STRICT_ALIGNMENT           (1 << 1)
 

@@ -79,6 +85,19 @@ struct bpf_test {
        const char *descr;
        struct bpf_insn insns[MAX_INSNS];
        struct bpf_insn *fill_insns;
+       /* If specified, test engine looks for this sequence of
+        * instructions in the BPF program after loading. Allows to
+        * test rewrites applied by verifier.  Use values
+        * INSN_OFF_MASK and INSN_IMM_MASK to mask `off` and `imm`
+        * fields if content does not matter.  The test case fails if
+        * specified instructions are not found.
+        *
+        * The sequence could be split into sub-sequences by adding
+        * SKIP_INSNS instruction at the end of each sub-sequence. In
+        * such case sub-sequences are searched for one after another.
+        */
+       struct bpf_insn expected_insns[MAX_EXPECTED_INSNS];
+       struct bpf_insn unexpected_insns[MAX_UNEXPECTED_INSNS];
        int fixup_map_hash_8b[MAX_FIXUPS];
        int fixup_map_hash_48b[MAX_FIXUPS];
        int fixup_map_hash_16b[MAX_FIXUPS];

tools/testing/selftests/bpf/test_verifier.c +6 -0

+               if (is_null_insn(&seq[i]))
+                       return i;
+       }
+       return max_len;
+}
+

tools/testing/selftests/bpf/test_verifier.c +23 -0

+
+static int find_insn_subseq(struct bpf_insn *seq, struct bpf_insn *subseq,
+                           int seq_len, int subseq_len)
+{
+       if (subseq_len > seq_len)
+               return -1;
+
+       for (int i = 0; i < seq_len - subseq_len + 1; ++i) {
+               bool found = true;
+
+               for (int j = 0; j < subseq_len; ++j) {
+                       if (!compare_masked_insn(&seq[i + j], &subseq[j])) {
+                               found = false;
+                               break;
+                       }
+               }
+               if (found)
+                       return i;
+       }
+
+       return -1;
+}
+

tools/testing/selftests/bpf/test_verifier.c +24 -0

+
+static bool check_xlated_program(struct bpf_test *test, int fd_prog)
+{
+       struct bpf_insn *buf;
+       int cnt;
+       bool result = true;
+       bool check_expected = !is_null_insn(test->expected_insns);
+       bool check_unexpected = !is_null_insn(test->unexpected_insns);
+
+       if (!check_expected && !check_unexpected)
+               goto out;
+
+       if (get_xlated_program(fd_prog, &buf, &cnt)) {
+               printf("FAIL: can't get xlated program\n");
+               result = false;
+               goto out;
+       }
+
+       if (check_expected &&
+           !find_all_insn_subseqs(buf, test->expected_insns,
+                                  cnt, MAX_EXPECTED_INSNS)) {
+               printf("FAIL: can't find expected subsequence of instructions\n");
+               result = false;
+               if (verbose) {

tools/testing/selftests/bpf/test_verifier.c +18 -1

+               printf("FAIL: found unexpected subsequence of instructions\n");
+               result = false;
+               if (verbose) {
+                       printf("Program:\n");
+                       print_insn(buf, cnt);
+                       printf("Un-expected subsequence:\n");
+                       print_insn(test->unexpected_insns, MAX_UNEXPECTED_INSNS);
+               }
+       }
+
+       free(buf);
+ out:
+       return result;
+}
+
 static void do_test_single(struct bpf_test *test, bool unpriv,
                           int *passes, int *errors)
 {

@@ -1262,6 +1481,9 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
        if (verbose)
                printf(", verifier log:\n%s", bpf_vlog);
 
+       if (!check_xlated_program(test, fd_prog))
+               goto fail_log;
+
        run_errs = 0;
        run_successes = 0;
        if (!alignment_prevented_execution && fd_prog >= 0 && test->runs >= 0) {
--

2.25.1

tools/testing/selftests/bpf/test_verifier.c line 64

Quoted 4 lines · Eduard Zingerman

tools/testing/selftests/bpf/test_verifier.c +2 -0

+#define INSN_OFF_MASK  ((s16)0xFFFF)
+#define INSN_IMM_MASK  ((s32)0xFFFFFFFF)

Shall we use __s16 and __s32 to match struct bpf_insn exactly.

Quoted 1 line

+ __u32 buf_elt_size = sizeof(**buf);

I guess elt means "element"? I would recommend use sizeof(struct bpf_insn) directly.

tools/testing/selftests/bpf/test_verifier.c static bool cmp_str_seq(const char *log, const char *exp) · line 1205

Quoted 3 lines

tools/testing/selftests/bpf/test_verifier.c +3 -0

+static int null_terminated_insn_len(struct bpf_insn *seq, int max_len)
+{
+       for (int i = 0; i < max_len; ++i) {

Sorry for missing this in v1. We should really pull variable declaration out, like

int i;

for (int i = 0; ...)

tools/testing/selftests/bpf/test_verifier.c static bool cmp_str_seq(const char *log, const char *exp) · line 1332

Quoted 4 lines

tools/testing/selftests/bpf/test_verifier.c +4 -0

+static int find_insn_subseq(struct bpf_insn *seq, struct bpf_insn *subseq,
+       if (check_unexpected &&
+           find_all_insn_subseqs(buf, test->unexpected_insns,
+                                 cnt, MAX_UNEXPECTED_INSNS)) {

I wonder whether we want different logic for unexpected_insns. With multiple sub sequences, say seq-A and seq-B, it is more natural to reject any results with either seq-A or seq-B. However, current logic will reject seq-A => seq-B, but will accept seq-B => seq-A. Does this make sense?

Quoted 2 lines

for (int i = 0; ...)

Sorry, just to clarify, you want me to pull all loop counter declarations to the top of the relevant functions, right? (Affecting 4 functions in this patch).

[...]

Quoted 9 lines

tools/testing/selftests/bpf/test_verifier.c static bool cmp_str_seq(const char *log, const char *exp) · line 1332

Quoted 4 lines

tools/testing/selftests/bpf/test_verifier.c +4 -0

+static int find_insn_subseq(struct bpf_insn *seq, struct bpf_insn *subseq,
+       if (check_unexpected &&
+           find_all_insn_subseqs(buf, test->unexpected_insns,
+                                 cnt, MAX_UNEXPECTED_INSNS)) {

I wonder whether we want different logic for unexpected_insns. With multiple sub sequences, say seq-A and seq-B, it is more natural to reject any results with either seq-A or seq-B. However, current logic will reject seq-A => seq-B, but will accept seq-B => seq-A. Does this make sense?

Have no strong opinion on this topic. In theory different variants might be useful in different cases.

In the test cases for bpf_loop inlining I only had to match a single unexpected instruction, so I opted to use same match function in both expected and unexpected cases to keep things simple.

Right. There are a few more in later patches.

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 Eduard Zingerman <[email protected]>

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 Eduard Zingerman <[email protected]>

---

kernel/bpf/verifier.c +64 -0

+static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
+                                       int position, u32 *cnt)
+{
+       struct bpf_insn_aux_data *aux = &env->insn_aux_data[position];
+       s32 stack_base = aux->loop_inline_state.stack_base;
+       s32 r6_offset = stack_base + 0 * BPF_REG_SIZE;
+       s32 r7_offset = stack_base + 1 * BPF_REG_SIZE;
+       s32 r8_offset = stack_base + 2 * BPF_REG_SIZE;
+       int reg_loop_max = BPF_REG_6;
+       int reg_loop_cnt = BPF_REG_7;
+       int reg_loop_ctx = BPF_REG_8;
+
+       struct bpf_prog *new_prog;
+       u32 callback_subprogno = aux->loop_inline_state.callback_subprogno;
+       u32 callback_start;
+       u32 call_insn_offset;
+       s32 callback_offset;
+       struct bpf_insn insn_buf[19];
+       struct bpf_insn *next = insn_buf;
+       struct bpf_insn *call, *jump_to_end, *loop_header;
+       struct bpf_insn *jump_to_header, *loop_exit;
+
+       /* Return error and jump to the end of the patch if
+        * expected number of iterations is too big.  This
+        * repeats the check done in bpf_loop helper function,
+        * be careful to modify this code in sync.
+        */
+       (*next++) = BPF_JMP_IMM(BPF_JLE, BPF_REG_1, BPF_MAX_LOOPS, 2);
+       (*next++) = BPF_MOV32_IMM(BPF_REG_0, -E2BIG);
+       jump_to_end = next;
+       (*next++) = BPF_JMP_IMM(BPF_JA, 0, 0, 0 /* set below */);
+       /* spill R6, R7, R8 to use these as loop vars */
+       (*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, r6_offset);
+       (*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, r7_offset);
+       (*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, r8_offset);
+       /* initialize loop vars */
+       (*next++) = BPF_MOV64_REG(reg_loop_max, BPF_REG_1);
+       (*next++) = BPF_MOV32_IMM(reg_loop_cnt, 0);
+       (*next++) = BPF_MOV64_REG(reg_loop_ctx, BPF_REG_3);
+       /* loop header;
+        * if reg_loop_cnt >= reg_loop_max skip the loop body
+        */
+       loop_header = next;
+       (*next++) = BPF_JMP_REG(BPF_JGE, reg_loop_cnt, reg_loop_max,
+                               0 /* set below */);
+       /* callback call */
+       (*next++) = BPF_MOV64_REG(BPF_REG_1, reg_loop_cnt);
+       (*next++) = BPF_MOV64_REG(BPF_REG_2, reg_loop_ctx);
+       call = next;
+       (*next++) = BPF_CALL_REL(0 /* set below after patching */);
+       /* increment loop counter */
+       (*next++) = BPF_ALU64_IMM(BPF_ADD, reg_loop_cnt, 1);
+       /* jump to loop header if callback returned 0 */
+       jump_to_header = next;
+       (*next++) = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 0 /* set below */);
+       /* return value of bpf_loop;
+        * set R0 to the number of iterations
+        */
+       loop_exit = next;
+       (*next++) = BPF_MOV64_REG(BPF_REG_0, reg_loop_cnt);
+       /* restore original values of R6, R7, R8 */
+       (*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, r6_offset);
+       (*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_10, r7_offset);
+       (*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_10, r8_offset);

kernel/bpf/verifier.c +29 -1

+
+       new_prog = bpf_patch_insn_data(env, position, insn_buf, *cnt);
+       if (!new_prog)
+               return new_prog;
+
+       /* callback start is known only after patching */
+       callback_start = env->subprog_info[callback_subprogno].start;
+       call_insn_offset = position + (call - insn_buf);
+       callback_offset = callback_start - call_insn_offset - 1;
+       env->prog->insnsi[call_insn_offset].imm = callback_offset;
+
+       return new_prog;
+}
+
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */

@@ -14258,6 +14432,18 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                        continue;
                }
 
+               if (insn->imm == BPF_FUNC_loop &&
+                   fit_for_bpf_loop_inline(&env->insn_aux_data[i + delta])) {
+                       new_prog = inline_bpf_loop(env, i + delta, &cnt);
+                       if (!new_prog)
+                               return -ENOMEM;
+
+                       delta    += cnt - 1;
+                       env->prog = prog = new_prog;
+                       insn      = new_prog->insnsi + i + delta;
+                       continue;
+               }
+
 patch_call_imm:
                fn = env->ops->get_func_proto(insn->imm, env->prog);
                /* all functions that have prototype and verifier allowed

@@ -15030,6 +15216,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr)
        if (ret == 0)
                ret = check_max_stack_depth(env);
 
+       if (ret == 0)
+               adjust_stack_depth_for_loop_inlining(env);
+
        /* instruction rewrites happen after this point */
        if (is_priv) {
                if (ret == 0)
--

2.25.1

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 adjust_stack_depth_for_loop_inlining increases stack depth for functions where bpf_loop calls could be inlined. This is needed to spill registers R6, R7 and R8. These registers are used as loop counter, loop maximal bound and callback context parameter;
- Function inline_bpf_loop called from do_misc_fixups replaces bpf_loop calls fit for inlining with corresponding loop instructions.

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 Eduard Zingerman <[email protected]>

---
 include/linux/bpf_verifier.h |  16 +++
 kernel/bpf/bpf_iter.c        |   9 +-
 kernel/bpf/verifier.c        | 199 ++++++++++++++++++++++++++++++++++-
 3 files changed, 215 insertions(+), 9 deletions(-)

include/linux/bpf_verifier.h +0 -0

index e8439f6cbe57..80279616a76b 100644

include/linux/bpf_verifier.h +4 -0

+       u32 callback_subprogno; /* valid when callback_is_constant == 1 */
+       s32 stack_base; /* stack offset for loop vars */
+};
+
 /* Possible states for alu_state member. */
 #define BPF_ALU_SANITIZE_SRC           (1U << 0)
 #define BPF_ALU_SANITIZE_DST           (1U << 1)

include/linux/bpf_verifier.h +0 -0

        /* below fields are initialized once */
        unsigned int orig_idx; /* original instruction index */

kernel/bpf/bpf_iter.c +5 -4

index d5d96ceca105..cdb898fce118 100644
@@ -6,6 +6,7 @@
 #include <linux/filter.h>
 #include <linux/bpf.h>
 #include <linux/rcupdate_trace.h>
+#include <linux/bpf_verifier.h>
 
 struct bpf_iter_target_info {
        struct list_head list;

@@ -723,9 +724,6 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = {
        .arg4_type      = ARG_ANYTHING,
 };
 
-/* maximum number of loops */
-#define MAX_LOOPS      BIT(23)
-
 BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
           u64, flags)
 {

@@ -733,9 +731,12 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
        u64 ret;
        u32 i;
 
+       /* note: these safety checks are also verified when bpf_loop is inlined,
+        * be careful to modify this code in sync
+        */
        if (flags)
                return -EINVAL;
-       if (nr_loops > MAX_LOOPS)
+       if (nr_loops > BPF_MAX_LOOPS)
                return -E2BIG;
 
        for (i = 0; i < nr_loops; i++) {

kernel/bpf/verifier.c +3 -0

index aedac2ac02b9..27d78fe6c3f9 100644
@@ -7103,6 +7103,78 @@ static int check_get_func_ip(struct bpf_verifier_env *env)
        return -ENOTSUPP;
 }
 
+static struct bpf_insn_aux_data *cur_aux(struct bpf_verifier_env *env)
+{
+       return &env->insn_aux_data[env->insn_idx];

kernel/bpf/verifier.c +8 -0

+
+               if (fit_for_bpf_loop_inline(aux)) {
+                       if (!subprog_updated) {
+                               subprog_updated = true;
+                               subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;
+                               stack_base = -subprogs[cur_subprog].stack_depth;
+                       }
+                       aux->loop_inline_state.stack_base = stack_base;

kernel/bpf/verifier.c +141 -5

+}
+
+static void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
+{
+       struct bpf_loop_inline_state *state = &cur_aux(env)->loop_inline_state;
+       struct bpf_reg_state *regs = cur_regs(env);
+       struct bpf_reg_state *flags_reg = &regs[BPF_REG_4];
+
+       int flags_is_zero =
+               register_is_const(flags_reg) && flags_reg->var_off.value == 0;
+
+       if (state->initialized) {
+               state->flags_is_zero &= flags_is_zero;
+               state->callback_is_constant &= state->callback_subprogno == subprogno;
+       } else {
+               state->initialized = 1;
+               state->callback_is_constant = 1;
+               state->flags_is_zero = flags_is_zero;
+               state->callback_subprogno = subprogno;
+       }
+}
+
 static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
                             int *insn_idx_p)
 {

@@ -7255,6 +7327,7 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
                err = check_bpf_snprintf_call(env, regs);
                break;
        case BPF_FUNC_loop:
+               update_loop_inline_state(env, meta.subprogno);
                err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
                                        set_loop_callback_state);
                break;

@@ -7661,11 +7734,6 @@ static bool check_reg_sane_offset(struct bpf_verifier_env *env,
        return true;
 }
 
-static struct bpf_insn_aux_data *cur_aux(struct bpf_verifier_env *env)
-{
-       return &env->insn_aux_data[env->insn_idx];
-}
-
 enum {
        REASON_BOUNDS   = -1,
        REASON_TYPE     = -2,

@@ -12920,6 +12988,22 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
        return new_prog;
 }
 
+static void adjust_loop_inline_subprogno(struct bpf_verifier_env *env,
+                                        u32 first_removed,
+                                        u32 first_remaining)
+{
+       int delta = first_remaining - first_removed;
+
+       for (int i = 0; i < env->prog->len; ++i) {
+               struct bpf_loop_inline_state *state =
+                       &env->insn_aux_data[i].loop_inline_state;
+
+               if (state->initialized &&
+                   state->callback_subprogno >= first_remaining)
+                       state->callback_subprogno -= delta;
+       }
+}
+
 static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
                                              u32 off, u32 cnt)
 {

@@ -12963,6 +13047,8 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
                         * in adjust_btf_func() - no need to adjust
                         */
                }
+
+               adjust_loop_inline_subprogno(env, i, j);
        } else {
                /* convert i from "first prog to remove" to "first to adjust" */
                if (env->subprog_info[i].start == off)

@@ -13773,6 +13859,94 @@ static int fixup_kfunc_call(struct bpf_verifier_env *env,
        return 0;
 }
 
+static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
+                                       int position, u32 *cnt)
+{
+       struct bpf_insn_aux_data *aux = &env->insn_aux_data[position];
+       s32 stack_base = aux->loop_inline_state.stack_base;
+       s32 r6_offset = stack_base + 0 * BPF_REG_SIZE;
+       s32 r7_offset = stack_base + 1 * BPF_REG_SIZE;
+       s32 r8_offset = stack_base + 2 * BPF_REG_SIZE;
+       int reg_loop_max = BPF_REG_6;
+       int reg_loop_cnt = BPF_REG_7;
+       int reg_loop_ctx = BPF_REG_8;
+
+       struct bpf_prog *new_prog;
+       u32 callback_subprogno = aux->loop_inline_state.callback_subprogno;
+       u32 callback_start;
+       u32 call_insn_offset;
+       s32 callback_offset;
+       struct bpf_insn insn_buf[19];
+       struct bpf_insn *next = insn_buf;
+       struct bpf_insn *call, *jump_to_end, *loop_header;
+       struct bpf_insn *jump_to_header, *loop_exit;
+
+       /* Return error and jump to the end of the patch if
+        * expected number of iterations is too big.  This
+        * repeats the check done in bpf_loop helper function,
+        * be careful to modify this code in sync.
+        */
+       (*next++) = BPF_JMP_IMM(BPF_JLE, BPF_REG_1, BPF_MAX_LOOPS, 2);
+       (*next++) = BPF_MOV32_IMM(BPF_REG_0, -E2BIG);
+       jump_to_end = next;
+       (*next++) = BPF_JMP_IMM(BPF_JA, 0, 0, 0 /* set below */);
+       /* spill R6, R7, R8 to use these as loop vars */
+       (*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, r6_offset);
+       (*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, r7_offset);
+       (*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, r8_offset);
+       /* initialize loop vars */
+       (*next++) = BPF_MOV64_REG(reg_loop_max, BPF_REG_1);
+       (*next++) = BPF_MOV32_IMM(reg_loop_cnt, 0);
+       (*next++) = BPF_MOV64_REG(reg_loop_ctx, BPF_REG_3);
+       /* loop header;
+        * if reg_loop_cnt >= reg_loop_max skip the loop body
+        */
+       loop_header = next;
+       (*next++) = BPF_JMP_REG(BPF_JGE, reg_loop_cnt, reg_loop_max,
+                               0 /* set below */);
+       /* callback call */
+       (*next++) = BPF_MOV64_REG(BPF_REG_1, reg_loop_cnt);
+       (*next++) = BPF_MOV64_REG(BPF_REG_2, reg_loop_ctx);
+       call = next;
+       (*next++) = BPF_CALL_REL(0 /* set below after patching */);
+       /* increment loop counter */
+       (*next++) = BPF_ALU64_IMM(BPF_ADD, reg_loop_cnt, 1);
+       /* jump to loop header if callback returned 0 */
+       jump_to_header = next;
+       (*next++) = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 0 /* set below */);
+       /* return value of bpf_loop;
+        * set R0 to the number of iterations
+        */
+       loop_exit = next;
+       (*next++) = BPF_MOV64_REG(BPF_REG_0, reg_loop_cnt);
+       /* restore original values of R6, R7, R8 */
+       (*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, r6_offset);
+       (*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_10, r7_offset);
+       (*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_10, r8_offset);
+
+       *cnt = next - insn_buf;
+       if (*cnt > ARRAY_SIZE(insn_buf)) {
+               WARN_ONCE(1, "BUG %s: 'next' exceeds bounds for 'insn_buf'\n",
+                         __func__);
+               return NULL;
+       }
+       jump_to_end->off = next - jump_to_end - 1;
+       loop_header->off = loop_exit - loop_header - 1;
+       jump_to_header->off = loop_header - jump_to_header - 1;
+
+       new_prog = bpf_patch_insn_data(env, position, insn_buf, *cnt);
+       if (!new_prog)
+               return new_prog;
+
+       /* callback start is known only after patching */
+       callback_start = env->subprog_info[callback_subprogno].start;
+       call_insn_offset = position + (call - insn_buf);
+       callback_offset = callback_start - call_insn_offset - 1;
+       env->prog->insnsi[call_insn_offset].imm = callback_offset;
+
+       return new_prog;
+}
+
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */

@@ -14258,6 +14432,18 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                        continue;
                }
 
+               if (insn->imm == BPF_FUNC_loop &&
+                   fit_for_bpf_loop_inline(&env->insn_aux_data[i + delta])) {
+                       new_prog = inline_bpf_loop(env, i + delta, &cnt);
+                       if (!new_prog)
+                               return -ENOMEM;
+
+                       delta    += cnt - 1;
+                       env->prog = prog = new_prog;
+                       insn      = new_prog->insnsi + i + delta;
+                       continue;
+               }
+
 patch_call_imm:
                fn = env->ops->get_func_proto(insn->imm, env->prog);
                /* all functions that have prototype and verifier allowed

kernel/bpf/verifier.c +1 -1

+
        /* instruction rewrites happen after this point */
        if (is_priv) {
                if (ret == 0)
--

2.25.1

Should this be moved to include/linux/bpf.h since kernel/bpf/bpf_iter.c also uses this? Then we don't need the "#include <linux/bpf_verifier.h>" in bpf_iter.c

Also, as a side-note, I think if we have an "is_valid" field, then we don't need both the "callback_is_constant" and "flags_is_zero" fields. If the flags is not zero or the callback subprogno is not the same on each invocation of the instruction, then we could represent that by just setting is_valid to false.

Is placing this inside the union in "struct bpf_insn_aux_data" an option?

Quoted 14 lines

kernel/bpf/verifier.c +14 -0

+
+               if (fit_for_bpf_loop_inline(aux)) {
+                       if (!subprog_updated) {
+                               subprog_updated = true;
+                               subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;
+                               stack_base = -subprogs[cur_subprog].stack_depth;
+                       }
+                       aux->loop_inline_state.stack_base = stack_base;
+               }
+               if (i == subprog_end - 1) {
+                       subprog_updated = false;
+                       cur_subprog++;
+                       if (cur_subprog < env->subprog_cnt)
+                               subprog_end = subprogs[cur_subprog + 1].start;

kernel/bpf/verifier.c static int check_get_func_ip(struct bpf_verifier_env *env) · line 7155

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+               }
+       }
+
+       env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;

In the case where a subprogram that is not subprogram 0 is a fit for the bpf loop inline and thus increases its stack depth, won't env->prog->aux->stack_depth need to also be updated?

kernel/bpf/verifier.c int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr) · line 15220

Quoted 6 lines

kernel/bpf/verifier.c +2 -0

@@ -15030,6 +15216,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr)
        if (ret == 0)
                ret = check_max_stack_depth(env);
 
+       if (ret == 0)
+               adjust_stack_depth_for_loop_inlining(env);

Do we need to do this before the check_max_stack_depth() call above since adjust_stack_depth_for_loop_inlining() adjusts the stack depth?

Hi Joanne, thanks for the review!

Quoted 1 line · Joanne Koong

Quoted 15 lines

Quoted 15 lines

kernel/bpf/verifier.c +14 -0

+
+               if (fit_for_bpf_loop_inline(aux)) {
+                       if (!subprog_updated) {
+                               subprog_updated = true;
+                               subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;
+                               stack_base = -subprogs[cur_subprog].stack_depth;
+                       }
+                       aux->loop_inline_state.stack_base = stack_base;
+               }
+               if (i == subprog_end - 1) {
+                       subprog_updated = false;
+                       cur_subprog++;
+                       if (cur_subprog < env->subprog_cnt)
+                               subprog_end = subprogs[cur_subprog + 1].start;

Quoted 8 lines

kernel/bpf/verifier.c static int check_get_func_ip(struct bpf_verifier_env *env) · line 7155

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+               }
+       }
+
+       env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;

In the case where a subprogram that is not subprogram 0 is a fit for the bpf loop inline and thus increases its stack depth, won't env->prog->aux->stack_depth need to also be updated?

As far as I understand the logic in do_check_main and jit_subprogs env->prog->aux->stack_depth always reflects the stack depth of the first sub-program (aka env->subprog_info[0].stack_depth). So the last line of adjust_stack_depth_for_loop_inlining merely ensures this invariant. The stack depth for each relevant subprogram is updated earlier in the function:

static void adjust_stack_depth_for_loop_inlining(struct bpf_verifier_env *env)

{
        ...
        for (i = 0; i < insn_cnt; i++) {
                ...
                if (fit_for_bpf_loop_inline(aux)) {
                        if (!subprog_updated) {
                                subprog_updated = true;
here  ---->                     subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;
                                ...
                        }
                        ...
                }
                if (i == subprog_end - 1) {
                        subprog_updated = false;
                        cur_subprog++;
                        ...
                }
        }
        ...
}

Also, the patch v3 4/5 in a series has a test case "bpf_loop_inline stack locations for loop vars" which checks that stack offsets for spilled registers are assigned correctly for subprogram that is not a first subprogram.

Quoted 9 lines

kernel/bpf/verifier.c int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr) · line 15220

Quoted 6 lines

kernel/bpf/verifier.c +2 -0

@@ -15030,6 +15216,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr)
        if (ret == 0)
                ret = check_max_stack_depth(env);
 
+       if (ret == 0)
+               adjust_stack_depth_for_loop_inlining(env);

Do we need to do this before the check_max_stack_depth() call above since adjust_stack_depth_for_loop_inlining() adjusts the stack depth?

This is an interesting question. I used the following reasoning placing adjust_stack_depth_for_loop_inlining after the check_max_stack_depth:

1. If adjust_stack_depth_for_loop_inlining is placed before check_max_stack_depth some of the existing BPF programs might stop loading, because of increased stack usage.
2. To avoid (1) it is possible to do check_max_stack_depth first, remember actual max depth and apply adjust_stack_depth_for_loop_inlining only when there is enough stack space. However there are two downsides:
- the optimization becomes flaky, similarly simple changes to the code of the BPF program might cause loop inlining to stop working;
- the precise verification itself is non-trivial as each possible stack trace has to be analyzed in terms of stack size with loop inlining / stack size without loop inlining. If necessary, I will probably use a simpler heuristic where stack budget for register spilling would be computed as
MAX_BPF_STACK - actual_max_stack_depth
3. Things are simpler if MAX_BPF_STACK is a soft limit that ensures that BPF programs consume limited amount of stack. In such case current implementation is sufficient.

So this boils down to the question what is MAX_BPF_STACK:
- a hard limit for the BPF program stack size?
- a soft limit used to verify that programs consume a limited amount of stack while executing?

If the answer is "hard limit" I'll proceed with implementation for option (2).

Thanks,
Eduard

Looking at arch/arm64/net/bpf_jit_comp.c, I see this diagram

/*
* BPF prog stack layout
*
* high
* original A64_SP => 0:+-----+ BPF prologue
* |FP/LR|
* current A64_FP => -16:+-----+
* | ... | callee saved registers
* BPF fp register => -64:+-----+ <= (BPF_FP)
* | |
* | ... | BPF prog stack
* | |
* +-----+ <= (BPF_FP - prog->aux->stack_depth)
* |RSVD | padding
* current A64_SP => +-----+ <= (BPF_FP - ctx->stack_size)
* | |

* | ... | Function call stack
* | |
* +-----+
* low
*
*/
It looks like prog->aux->stack_depth is used for the "BPF prog stack", which is the stack for the main bpf program (subprog 0)

I'm not sure either whether MAX_BPF_STACK is a hard limit or a soft limit. I'm curious to know as well.

kernel/bpf/verifier.c +52 -5

+				stack_base = -subprogs[cur_subprog].stack_depth;
+			}
+			aux->loop_inline_state.stack_base = stack_base;
+		}
+		if (i == subprog_end - 1) {
+			subprog_updated = false;
+			cur_subprog++;
+			if (cur_subprog < env->subprog_cnt)
+				subprog_end = subprogs[cur_subprog + 1].start;
+		}
+	}
+
+	env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
+}
+
+static void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
+{
+	struct bpf_loop_inline_state *state = &cur_aux(env)->loop_inline_state;
+	struct bpf_reg_state *regs = cur_regs(env);
+	struct bpf_reg_state *flags_reg = &regs[BPF_REG_4];
+
+	int flags_is_zero =
+		register_is_const(flags_reg) && flags_reg->var_off.value == 0;
+
+	if (state->initialized) {
+		state->flags_is_zero &= flags_is_zero;
+		state->callback_is_constant &= state->callback_subprogno == subprogno;
+	} else {
+		state->initialized = 1;
+		state->callback_is_constant = 1;
+		state->flags_is_zero = flags_is_zero;
+		state->callback_subprogno = subprogno;
+	}
+}
+
 static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			     int *insn_idx_p)
 {

@@ -7255,6 +7327,7 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		err = check_bpf_snprintf_call(env, regs);
 		break;
 	case BPF_FUNC_loop:
+		update_loop_inline_state(env, meta.subprogno);
 		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
 					set_loop_callback_state);
 		break;

@@ -7661,11 +7734,6 @@ static bool check_reg_sane_offset(struct bpf_verifier_env *env,
 	return true;
 }
 
-static struct bpf_insn_aux_data *cur_aux(struct bpf_verifier_env *env)
-{
-	return &env->insn_aux_data[env->insn_idx];
-}
-
 enum {
 	REASON_BOUNDS	= -1,
 	REASON_TYPE	= -2,

@@ -12920,6 +12988,22 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 	return new_prog;
 }
 
+static void adjust_loop_inline_subprogno(struct bpf_verifier_env *env,
+					 u32 first_removed,
+					 u32 first_remaining)
+{
+	int delta = first_remaining - first_removed;
+
+	for (int i = 0; i < env->prog->len; ++i) {
+		struct bpf_loop_inline_state *state =
+			&env->insn_aux_data[i].loop_inline_state;
+
+		if (state->initialized &&
+		    state->callback_subprogno >= first_remaining)
+			state->callback_subprogno -= delta;
+	}
+}
+
 static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 					      u32 off, u32 cnt)
 {

kernel/bpf/verifier.c +100 -0

 	} else {
 		/* convert i from "first prog to remove" to "first to adjust" */
 		if (env->subprog_info[i].start == off)

@@ -13773,6 +13859,94 @@ static int fixup_kfunc_call(struct bpf_verifier_env *env,
 	return 0;
 }
 
+static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
+					int position, u32 *cnt)
+{
+	struct bpf_insn_aux_data *aux = &env->insn_aux_data[position];
+	s32 stack_base = aux->loop_inline_state.stack_base;
+	s32 r6_offset = stack_base + 0 * BPF_REG_SIZE;
+	s32 r7_offset = stack_base + 1 * BPF_REG_SIZE;
+	s32 r8_offset = stack_base + 2 * BPF_REG_SIZE;
+	int reg_loop_max = BPF_REG_6;
+	int reg_loop_cnt = BPF_REG_7;
+	int reg_loop_ctx = BPF_REG_8;
+
+	struct bpf_prog *new_prog;
+	u32 callback_subprogno = aux->loop_inline_state.callback_subprogno;
+	u32 callback_start;
+	u32 call_insn_offset;
+	s32 callback_offset;
+	struct bpf_insn insn_buf[19];
+	struct bpf_insn *next = insn_buf;
+	struct bpf_insn *call, *jump_to_end, *loop_header;
+	struct bpf_insn *jump_to_header, *loop_exit;
+
+	/* Return error and jump to the end of the patch if
+	 * expected number of iterations is too big.  This
+	 * repeats the check done in bpf_loop helper function,
+	 * be careful to modify this code in sync.
+	 */
+	(*next++) = BPF_JMP_IMM(BPF_JLE, BPF_REG_1, BPF_MAX_LOOPS, 2);
+	(*next++) = BPF_MOV32_IMM(BPF_REG_0, -E2BIG);
+	jump_to_end = next;
+	(*next++) = BPF_JMP_IMM(BPF_JA, 0, 0, 0 /* set below */);
+	/* spill R6, R7, R8 to use these as loop vars */
+	(*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, r6_offset);
+	(*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, r7_offset);
+	(*next++) = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, r8_offset);
+	/* initialize loop vars */
+	(*next++) = BPF_MOV64_REG(reg_loop_max, BPF_REG_1);
+	(*next++) = BPF_MOV32_IMM(reg_loop_cnt, 0);
+	(*next++) = BPF_MOV64_REG(reg_loop_ctx, BPF_REG_3);
+	/* loop header;
+	 * if reg_loop_cnt >= reg_loop_max skip the loop body
+	 */
+	loop_header = next;
+	(*next++) = BPF_JMP_REG(BPF_JGE, reg_loop_cnt, reg_loop_max,
+				0 /* set below */);
+	/* callback call */
+	(*next++) = BPF_MOV64_REG(BPF_REG_1, reg_loop_cnt);
+	(*next++) = BPF_MOV64_REG(BPF_REG_2, reg_loop_ctx);
+	call = next;
+	(*next++) = BPF_CALL_REL(0 /* set below after patching */);
+	/* increment loop counter */
+	(*next++) = BPF_ALU64_IMM(BPF_ADD, reg_loop_cnt, 1);
+	/* jump to loop header if callback returned 0 */
+	jump_to_header = next;
+	(*next++) = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 0 /* set below */);
+	/* return value of bpf_loop;
+	 * set R0 to the number of iterations
+	 */
+	loop_exit = next;
+	(*next++) = BPF_MOV64_REG(BPF_REG_0, reg_loop_cnt);
+	/* restore original values of R6, R7, R8 */
+	(*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, r6_offset);
+	(*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_10, r7_offset);
+	(*next++) = BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_10, r8_offset);
+
+	*cnt = next - insn_buf;
+	if (*cnt > ARRAY_SIZE(insn_buf)) {
+		WARN_ONCE(1, "BUG %s: 'next' exceeds bounds for 'insn_buf'\n",
+			  __func__);
+		return NULL;
+	}
+	jump_to_end->off = next - jump_to_end - 1;
+	loop_header->off = loop_exit - loop_header - 1;
+	jump_to_header->off = loop_header - jump_to_header - 1;
+
+	new_prog = bpf_patch_insn_data(env, position, insn_buf, *cnt);
+	if (!new_prog)
+		return new_prog;
+
+	/* callback start is known only after patching */
+	callback_start = env->subprog_info[callback_subprogno].start;
+	call_insn_offset = position + (call - insn_buf);
+	callback_offset = callback_start - call_insn_offset - 1;
+	env->prog->insnsi[call_insn_offset].imm = callback_offset;
+
+	return new_prog;
+}
+
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */

@@ -14258,6 +14432,18 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
 			continue;
 		}
 
+		if (insn->imm == BPF_FUNC_loop &&
+		    fit_for_bpf_loop_inline(&env->insn_aux_data[i + delta])) {
+			new_prog = inline_bpf_loop(env, i + delta, &cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			continue;
+		}
+
 patch_call_imm:
 		fn = env->ops->get_func_proto(insn->imm, env->prog);
 		/* all functions that have prototype and verifier allowed

Quoted 1 line · Eduard Zingerman

kernel/bpf/verifier.c static int check_get_func_ip(struct bpf_verifier_env *env) · line 7142

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+		if (fit_for_bpf_loop_inline(aux)) {
+			if (!subprog_updated) {
+				subprog_updated = true;
+				subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;

Instead of doing += and keeping track that the stack was increased (if multiple bpf_loop happened to be in a function)
may be add subprogs[..].stack_depth_extra variable ?
And unconditionally do subprogs[cur_subprog].stack_depth_extra = BPF_REG_SIZE * 3; every time bpf_loop is seen?
Then we can do that during inline_bpf_loop().

kernel/bpf/verifier.c static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env, · line 13051

Quoted 6 lines

kernel/bpf/verifier.c +2 -0

@@ -12963,6 +13047,8 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 			 * in adjust_btf_func() - no need to adjust
 			 */
 		}
+
+		adjust_loop_inline_subprogno(env, i, j);

This special case isn't great.
May be let's do inline_bpf_loop() earlier?
Instead of doing it from do_misc_fixups() how about doing it as a separate pass right after check_max_stack_depth() ?
Then opt_remove_dead_code() will adjust BPF_CALL_REL automatically as a part of bpf_adj_branches().

kernel/bpf/verifier.c int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr) · line 15220

Quoted 5 lines

kernel/bpf/verifier.c +2 -0

 	if (ret == 0)
 		ret = check_max_stack_depth(env);
 
+	if (ret == 0)
+		adjust_stack_depth_for_loop_inlining(env);

With above two suggestions this will become
if (ret == 0)

    optimize_bpf_loop(env);

where it will call inline_bpf_loop() and will assign max_depth_extra. And then one extra loop for_each_subporg() max_depth += max_depth_extra.

wdyt?

Also is there a test for multiple bpf_loop in a func?

kernel/bpf/verifier.c int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr) · line 15220

Quoted 2 lines

kernel/bpf/verifier.c +2 -0

+       if (ret == 0)
+               adjust_stack_depth_for_loop_inlining(env);

Do we need to do this before the check_max_stack_depth() call above since adjust_stack_depth_for_loop_inlining() adjusts the stack depth?

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 Eduard Zingerman <[email protected]>

---
 .../selftests/bpf/verifier/bpf_loop_inline.c  | 244 ++++++++++++++++++
 1 file changed, 244 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/bpf_loop_inline.c

tools/testing/selftests/bpf/verifier/bpf_loop_inline.c new file +244 -1

new file mode 100644
index 000000000000..d1fbcfef69f2
@@ -0,0 +1,244 @@
+#define BTF_TYPES \
+       .btf_strings = "\0int\0i\0ctx\0callback\0main\0", \
+       .btf_types = { \
+       /* 1: int   */ BTF_TYPE_INT_ENC(1, BTF_INT_SIGNED, 0, 32, 4), \
+       /* 2: int*  */ BTF_PTR_ENC(1), \
+       /* 3: void* */ BTF_PTR_ENC(0), \
+       /* 4: int __(void*) */ BTF_FUNC_PROTO_ENC(1, 1), \
+               BTF_FUNC_PROTO_ARG_ENC(7, 3), \
+       /* 5: int __(int, int*) */ BTF_FUNC_PROTO_ENC(1, 2), \
+               BTF_FUNC_PROTO_ARG_ENC(5, 1), \
+               BTF_FUNC_PROTO_ARG_ENC(7, 2), \
+       /* 6: main      */ BTF_FUNC_ENC(20, 4), \
+       /* 7: callback  */ BTF_FUNC_ENC(11, 5), \
+       BTF_END_RAW \
+       }
+
+#define MAIN_TYPE      6
+#define CALLBACK_TYPE  7
+
+/* can't use BPF_CALL_REL, jit_subprogs adjusts IMM & OFF
+ * fields for pseudo calls
+ */
+#define PSEUDO_CALL_INSN() \
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, \
+                    INSN_OFF_MASK, INSN_IMM_MASK)
+
+/* can't use BPF_FUNC_loop constant,
+ * do_mix_fixups adjusts the IMM field
+ */
+#define HELPER_CALL_INSN() \
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, INSN_OFF_MASK, INSN_IMM_MASK)
+
+{
+       "inline simple bpf_loop call",
+       .insns = {
+       /* main */
+       /* force verifier state branching to verify logic on first and
+        * subsequent bpf_loop insn processing steps
+        */
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+       BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 777, 2),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 1),
+       BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 2),
+
+       BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 6),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_loop),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* callback */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
+       BPF_EXIT_INSN(),
+       },
+       .expected_insns = { PSEUDO_CALL_INSN() },
+       .unexpected_insns = { HELPER_CALL_INSN() },
+       .prog_type = BPF_PROG_TYPE_TRACEPOINT,
+       .result = ACCEPT,
+       .runs = 0,
+       .func_info = { { 0, MAIN_TYPE }, { 12, CALLBACK_TYPE } },
+       .func_info_cnt = 2,
+       BTF_TYPES
+},
+{
+       "don't inline bpf_loop call, flags non-zero",
+       .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_RAW_INSN(0, 0, 0, 0, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 1),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_loop),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* callback */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
+       BPF_EXIT_INSN(),
+       },
+       .expected_insns = { HELPER_CALL_INSN() },
+       .unexpected_insns = { PSEUDO_CALL_INSN() },
+       .prog_type = BPF_PROG_TYPE_TRACEPOINT,
+       .result = ACCEPT,
+       .runs = 0,
+       .func_info = { { 0, MAIN_TYPE }, { 8, CALLBACK_TYPE } },
+       .func_info_cnt = 2,
+       BTF_TYPES
+},
+{
+       "don't inline bpf_loop call, callback non-constant",
+       .insns = {
+       /* main */
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+       BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 777, 4), /* pick a random callback */
+
+       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, 10),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+       BPF_JMP_IMM(BPF_JA, 0, 0, 3),
+
+       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, 8),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_loop),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* callback */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
+       BPF_EXIT_INSN(),
+       /* callback #2 */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
+       BPF_EXIT_INSN(),
+       },
+       .expected_insns = { HELPER_CALL_INSN() },
+       .unexpected_insns = { PSEUDO_CALL_INSN() },
+       .prog_type = BPF_PROG_TYPE_TRACEPOINT,
+       .result = ACCEPT,
+       .runs = 0,
+       .func_info = {
+               { 0, MAIN_TYPE },
+               { 14, CALLBACK_TYPE },
+               { 16, CALLBACK_TYPE }
+       },
+       .func_info_cnt = 3,
+       BTF_TYPES
+},
+{
+       "bpf_loop_inline and a dead func",
+       .insns = {
+       /* main */
+
+       /* A reference to callback #1 to make verifier count it as a func.
+        * This reference is overwritten below and callback #1 is dead.
+        */
+       BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 9),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+       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, 8),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_loop),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* callback */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
+       BPF_EXIT_INSN(),
+       /* callback #2 */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
+       BPF_EXIT_INSN(),
+       },
+       .expected_insns = { PSEUDO_CALL_INSN() },
+       .unexpected_insns = { HELPER_CALL_INSN() },
+       .prog_type = BPF_PROG_TYPE_TRACEPOINT,
+       .result = ACCEPT,
+       .runs = 0,
+       .func_info = {
+               { 0, MAIN_TYPE },
+               { 10, CALLBACK_TYPE },
+               { 12, CALLBACK_TYPE }
+       },
+       .func_info_cnt = 3,
+       BTF_TYPES
+},
+{
+       "bpf_loop_inline stack locations for loop vars",
+       .insns = {
+       /* main */
+       BPF_ST_MEM(BPF_DW, BPF_REG_10, -16, 0x77),
+       /* bpf_loop call #1 */
+       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, 22),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_loop),
+       /* bpf_loop call #2 */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 2),
+       BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 16),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_loop),
+       /* call func and exit */
+       BPF_CALL_REL(2),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* func */
+       BPF_ST_MEM(BPF_DW, BPF_REG_10, -32, 0x55),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 2),
+       BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 6),
+       BPF_RAW_INSN(0, 0, 0, 0, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 0),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_loop),
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* callback */
+       BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
+       BPF_EXIT_INSN(),
+       },
+       .expected_insns = {
+       BPF_ST_MEM(BPF_DW, BPF_REG_10, -16, 0x77),
+       SKIP_INSNS(),
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, -40),
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, -32),
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, -24),
+       SKIP_INSNS(),
+       /* offsets are the same as in the first call */
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, -40),
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, -32),
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, -24),
+       SKIP_INSNS(),
+       BPF_ST_MEM(BPF_DW, BPF_REG_10, -32, 0x55),
+       SKIP_INSNS(),
+       /* offsets differ from main because of different offset
+        * in BPF_ST_MEM instruction
+        */
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, -56),
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, -48),
+       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, -40),
+       },
+       .unexpected_insns = { HELPER_CALL_INSN() },
+       .prog_type = BPF_PROG_TYPE_TRACEPOINT,
+       .result = ACCEPT,
+       .func_info = {
+               { 0, MAIN_TYPE },
+               { 16, MAIN_TYPE },
+               { 25, CALLBACK_TYPE },
+       },
+       .func_info_cnt = 3,
+       BTF_TYPES
+},
+
+#undef HELPER_CALL_INSN
+#undef PSEUDO_CALL_INSN
+#undef CALLBACK_TYPE
+#undef MAIN_TYPE
+#undef BTF_TYPES
--

2.25.1

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 Eduard Zingerman <[email protected]>

tools/testing/selftests/bpf/prog_tests/bpf_loop.c +5 -0

+static void check_stack(struct bpf_loop *skel)
+{
+       const int max_key = 12;
+       struct bpf_link *link = bpf_program__attach(skel->progs.stack_check);
+       int map_fd;

tools/testing/selftests/bpf/prog_tests/bpf_loop.c +13 -0

+               int val;
+               int err = bpf_map_lookup_elem(map_fd, &key, &val);
+
+               if (!ASSERT_OK(err, "bpf_map_lookup_elem"))
+                       goto out;
+               if (!ASSERT_EQ(val, key + 1, "bad value in the map"))
+                       goto out;
+       }
+
+out:
+       bpf_link__destroy(link);
+}
+