bpf_loop inlining

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_INSN(),

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

---

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

+
+static int get_xlated_program(int fd_prog, struct bpf_insn **buf, int *cnt)
+{
+       struct bpf_prog_info info = {};
+       __u32 info_len = sizeof(info);
+       int err = 0;
+
+       if (bpf_obj_get_info_by_fd(fd_prog, &info, &info_len)) {
+               err = errno;
+               perror("bpf_obj_get_info_by_fd failed");
+               goto out;
+       }
+
+       __u32 xlated_prog_len = info.xlated_prog_len;
+       *cnt = roundup_u32(xlated_prog_len, sizeof(**buf));
+       *buf = calloc(*cnt, sizeof(**buf));
+       if (!buf) {
+               err = -ENOMEM;
+               perror("can't allocate xlated program buffer");
+               goto out;
+       }
+
+       bzero(&info, sizeof(info));

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]>

---
 tools/testing/selftests/bpf/prog_tests/btf.c |   1 -
 tools/testing/selftests/bpf/test_btf.h       |   2 +
 tools/testing/selftests/bpf/test_verifier.c  | 110 ++++++++++++++++---
 3 files changed, 95 insertions(+), 18 deletions(-)

tools/testing/selftests/bpf/test_verifier.c +11 -8

-static int load_btf(void)
+static char bpf_vlog[UINT_MAX >> 8];
+
+static int load_btf_spec(__u32 *types, int types_len,
+                        const char *strings, int strings_len)
 {
        struct btf_header hdr = {
                .magic = BTF_MAGIC,
                .version = BTF_VERSION,
                .hdr_len = sizeof(struct btf_header),
-               .type_len = sizeof(btf_raw_types),
-               .str_off = sizeof(btf_raw_types),
-               .str_len = sizeof(btf_str_sec),
+               .type_len = types_len,
+               .str_off = types_len,
+               .str_len = strings_len,
        };
        void *ptr, *raw_btf;
        int btf_fd;
 
-       ptr = raw_btf = malloc(sizeof(hdr) + sizeof(btf_raw_types) +
-                              sizeof(btf_str_sec));
+       raw_btf = malloc(sizeof(hdr) + types_len + strings_len);
 
+       ptr = raw_btf;
        memcpy(ptr, &hdr, sizeof(hdr));
        ptr += sizeof(hdr);
-       memcpy(ptr, btf_raw_types, hdr.type_len);
+       memcpy(ptr, types, hdr.type_len);
        ptr += hdr.type_len;
-       memcpy(ptr, btf_str_sec, hdr.str_len);
+       memcpy(ptr, strings, hdr.str_len);
        ptr += hdr.str_len;

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

+
+       btf_fd = bpf_btf_load(raw_btf, ptr - raw_btf, &opts);
        if (btf_fd < 0)
-               return -1;
-       return btf_fd;
+               printf("Failed to load BTF spec: '%s'\n", strerror(errno));
+
+       free(raw_btf);
+
+       return btf_fd < 0 ? -1 : btf_fd;
+}
+

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

+
 static void do_test_single(struct bpf_test *test, bool unpriv,
                           int *passes, int *errors)
 {
-       int fd_prog, expected_ret, alignment_prevented_execution;
+       int fd_prog, btf_fd, expected_ret, alignment_prevented_execution;
        int prog_len, prog_type = test->prog_type;
        struct bpf_insn *prog = test->insns;
        LIBBPF_OPTS(bpf_prog_load_opts, opts);

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

        for (i = 0; i < MAX_NR_MAPS; i++)
                map_fds[i] = -1;
+       btf_fd = -1;
 
        if (!prog_type)
                prog_type = BPF_PROG_TYPE_SOCKET_FILTER;

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

        goto close_fds;
 }
 
--

2.25.1

tools/testing/selftests/bpf/test_verifier.c static bool check_xlated_program(struct bpf_test *test, int fd_prog)

Quoted 9 lines

{

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

-       int fd_prog, expected_ret, alignment_prevented_execution;
+       int fd_prog, btf_fd, expected_ret, alignment_prevented_execution;
        int prog_len, prog_type = test->prog_type;
        struct bpf_insn *prog = test->insns;
        LIBBPF_OPTS(bpf_prog_load_opts, opts);        __u32 pflags;
        int i, err;
 
+       fd_prog = -1;

This is not really necessary.

Quoted 2 lines · Song Liu

Hi Song,

Thanks a lot for the review, I'll apply the suggested changes and provide the v3 in one or two days. My only objection is below.

Quoted 11 lines

tools/testing/selftests/bpf/test_verifier.c static bool check_xlated_program(struct bpf_test *test, int fd_prog)

Quoted 9 lines

{

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

-       int fd_prog, expected_ret, alignment_prevented_execution;
+       int fd_prog, btf_fd, expected_ret, alignment_prevented_execution;
        int prog_len, prog_type = test->prog_type;
        struct bpf_insn *prog = test->insns;
        LIBBPF_OPTS(bpf_prog_load_opts, opts);        __u32 pflags;
        int i, err;
 
+       fd_prog = -1;

This is not really necessary.

Actually this one is necessary to avoid compiler warning, note the following fragment of the do_test_single function below:

static void do_test_single(...)

{
        ...
        if (...) {
                btf_fd = load_btf_for_test(...);
                if (btf_fd < 0)
                        goto fail_log;
                opts.prog_btf_fd = btf_fd;
        }
        ...
        fd_prog = bpf_prog_load(..., &opts);
        ...
close_fds:
        ...
        close(fd_prog);
        close(btf_fd);
        ...
        return;
fail_log:
        ...
        goto close_fds;
}

If load_btf_for_test fails the goto fail_log would eventually jump to close_fds, where fd_prog would be in an uninitialised state.

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

---
 include/linux/bpf_verifier.h                  |  16 ++
 kernel/bpf/bpf_iter.c                         |   9 +-
 kernel/bpf/verifier.c                         | 184 ++++++++++++-
 .../selftests/bpf/prog_tests/bpf_loop.c       |  62 +++++
 tools/testing/selftests/bpf/progs/bpf_loop.c  | 122 +++++++++
 .../selftests/bpf/verifier/bpf_loop_inline.c  | 244 ++++++++++++++++++
 6 files changed, 628 insertions(+), 9 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/bpf_loop_inline.c

kernel/bpf/verifier.c +8 -0

+       s32 stack_base;
+
+       subprog_end = (env->subprog_cnt > 1
+                      ? subprogs[cur_subprog + 1].start
+                      : insn_cnt);
+       for (i = 0; i < insn_cnt; i++) {
+               struct bpf_insn_aux_data *aux = &env->insn_aux_data[i];
+

kernel/bpf/verifier.c +57 -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[] = {
+               /* 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.
+                */
+               BPF_JMP_IMM(BPF_JLE, BPF_REG_1, BPF_MAX_LOOPS, 2),
+               BPF_MOV32_IMM(BPF_REG_0, -E2BIG),
+               BPF_JMP_IMM(BPF_JA, 0, 0, 16),
+               /* spill R6, R7, R8 to use these as loop vars */
+               BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, r6_offset),
+               BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, r7_offset),
+               BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, r8_offset),
+               /* initialize loop vars */
+               BPF_MOV64_REG(reg_loop_max, BPF_REG_1),
+               BPF_MOV32_IMM(reg_loop_cnt, 0),
+               BPF_MOV64_REG(reg_loop_ctx, BPF_REG_3),
+               /* loop header,
+                * if reg_loop_cnt >= reg_loop_max skip the loop body
+                */
+               BPF_JMP_REG(BPF_JGE, reg_loop_cnt, reg_loop_max, 5),
+               /* callback call,
+                * correct callback offset would be set after patching
+                */
+               BPF_MOV64_REG(BPF_REG_1, reg_loop_cnt),
+               BPF_MOV64_REG(BPF_REG_2, reg_loop_ctx),
+               BPF_CALL_REL(0),
+               /* increment loop counter */
+               BPF_ALU64_IMM(BPF_ADD, reg_loop_cnt, 1),
+               /* jump to loop header if callback returned 0 */
+               BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, -6),
+               /* return value of bpf_loop,
+                * set R0 to the number of iterations
+                */
+               BPF_MOV64_REG(BPF_REG_0, reg_loop_cnt),
+               /* restore original values of R6, R7, R8 */
+               BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, r6_offset),
+               BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_10, r7_offset),
+               BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_10, r8_offset),

kernel/bpf/verifier.c +21 -0

+       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 +14417,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 +15201,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)

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

index 380d7a2072e3..1caa495be48c 100644
@@ -120,6 +120,64 @@ static void check_nested_calls(struct bpf_loop *skel)
        bpf_link__destroy(link);
 }
 
+static void check_non_constant_callback(struct bpf_loop *skel)
+{
+       struct bpf_link *link =
+               bpf_program__attach(skel->progs.prog_non_constant_callback);
+
+       if (!ASSERT_OK_PTR(link, "link"))
+               return;
+
+       skel->bss->callback_selector = 0x0F;
+       usleep(1);
+       ASSERT_EQ(skel->bss->g_output, 0x0F, "g_output #1");
+
+       skel->bss->callback_selector = 0xF0;
+       usleep(1);
+       ASSERT_EQ(skel->bss->g_output, 0xF0, "g_output #2");
+

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

+
+       if (!ASSERT_GE(map_fd, 0, "bpf_map__fd"))
+               goto out;
+
+       for (int key = 1; key <= 16; ++key) {
+               int val = key;
+               int err = bpf_map_update_elem(map_fd, &key, &val, BPF_NOEXIST);
+
+               if (!ASSERT_OK(err, "bpf_map_update_elem"))
+                       goto out;
+       }
+
+       usleep(1);
+
+       for (int key = 1; key <= 16; ++key) {
+               int val;

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

+}
+
 void test_bpf_loop(void)
 {
        struct bpf_loop *skel;

@@ -140,6 +198,10 @@ void test_bpf_loop(void)
                check_invalid_flags(skel);
        if (test__start_subtest("check_nested_calls"))
                check_nested_calls(skel);
+       if (test__start_subtest("check_non_constant_callback"))
+               check_non_constant_callback(skel);
+       if (test__start_subtest("check_stack"))
+               check_stack(skel);
 
        bpf_loop__destroy(skel);
 }