* [PATCH bpf-next v4 1/5] selftests/bpf: specify expected instructions in test_verifier tests
2022-06-08 19:26 [PATCH bpf-next v4 0/5] bpf_loop inlining Eduard Zingerman
@ 2022-06-08 19:26 ` Eduard Zingerman
2022-06-10 17:56 ` Song Liu
2022-06-08 19:26 ` [PATCH bpf-next v4 2/5] selftests/bpf: allow BTF specs and func infos " Eduard Zingerman
` (3 subsequent siblings)
4 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-08 19:26 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, song, joannelkoong; +Cc: eddyz87
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: Eduard Zingerman <eddyz87@gmail.com>
---
tools/testing/selftests/bpf/test_verifier.c | 234 ++++++++++++++++++++
1 file changed, 234 insertions(+)
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 372579c9f45e..1f24eae9e16e 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -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
@@ -58,6 +60,10 @@
#define POINTER_VALUE 0xcafe4all
#define TEST_DATA_LEN 64
+#define INSN_OFF_MASK ((__s16)0xFFFF)
+#define INSN_IMM_MASK ((__s32)0xFFFFFFFF)
+#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,23 @@ 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];
+ /* If specified, test engine applies same pattern matching
+ * logic as for `expected_insns`. If the specified pattern is
+ * matched test case is marked as failed.
+ */
+ 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];
@@ -1126,6 +1149,214 @@ static bool cmp_str_seq(const char *log, const char *exp)
return true;
}
+static int get_xlated_program(int fd_prog, struct bpf_insn **buf, int *cnt)
+{
+ struct bpf_prog_info info = {};
+ __u32 info_len = sizeof(info);
+ __u32 xlated_prog_len;
+ __u32 buf_element_size = sizeof(struct bpf_insn);
+
+ if (bpf_obj_get_info_by_fd(fd_prog, &info, &info_len)) {
+ perror("bpf_obj_get_info_by_fd failed");
+ return -1;
+ }
+
+ xlated_prog_len = info.xlated_prog_len;
+ if (xlated_prog_len % buf_element_size) {
+ printf("Program length %d is not multiple of %d\n",
+ xlated_prog_len, buf_element_size);
+ return -1;
+ }
+
+ *cnt = xlated_prog_len / buf_element_size;
+ *buf = calloc(*cnt, buf_element_size);
+ if (!buf) {
+ perror("can't allocate xlated program buffer");
+ return -ENOMEM;
+ }
+
+ bzero(&info, sizeof(info));
+ info.xlated_prog_len = xlated_prog_len;
+ info.xlated_prog_insns = (__u64)*buf;
+ if (bpf_obj_get_info_by_fd(fd_prog, &info, &info_len)) {
+ perror("second bpf_obj_get_info_by_fd failed");
+ goto out_free_buf;
+ }
+
+ return 0;
+
+out_free_buf:
+ free(*buf);
+ return -1;
+}
+
+static bool is_null_insn(struct bpf_insn *insn)
+{
+ struct bpf_insn null_insn = {};
+
+ return memcmp(insn, &null_insn, sizeof(null_insn)) == 0;
+}
+
+static bool is_skip_insn(struct bpf_insn *insn)
+{
+ struct bpf_insn skip_insn = SKIP_INSNS();
+
+ return memcmp(insn, &skip_insn, sizeof(skip_insn)) == 0;
+}
+
+static int null_terminated_insn_len(struct bpf_insn *seq, int max_len)
+{
+ int i;
+
+ for (i = 0; i < max_len; ++i) {
+ if (is_null_insn(&seq[i]))
+ return i;
+ }
+ return max_len;
+}
+
+static bool compare_masked_insn(struct bpf_insn *orig, struct bpf_insn *masked)
+{
+ struct bpf_insn orig_masked;
+
+ memcpy(&orig_masked, orig, sizeof(orig_masked));
+ if (masked->imm == INSN_IMM_MASK)
+ orig_masked.imm = INSN_IMM_MASK;
+ if (masked->off == INSN_OFF_MASK)
+ orig_masked.off = INSN_OFF_MASK;
+
+ return memcmp(&orig_masked, masked, sizeof(orig_masked)) == 0;
+}
+
+static int find_insn_subseq(struct bpf_insn *seq, struct bpf_insn *subseq,
+ int seq_len, int subseq_len)
+{
+ int i, j;
+
+ if (subseq_len > seq_len)
+ return -1;
+
+ for (i = 0; i < seq_len - subseq_len + 1; ++i) {
+ bool found = true;
+
+ for (j = 0; j < subseq_len; ++j) {
+ if (!compare_masked_insn(&seq[i + j], &subseq[j])) {
+ found = false;
+ break;
+ }
+ }
+ if (found)
+ return i;
+ }
+
+ return -1;
+}
+
+static int find_skip_insn_marker(struct bpf_insn *seq, int len)
+{
+ int i;
+
+ for (i = 0; i < len; ++i)
+ if (is_skip_insn(&seq[i]))
+ return i;
+
+ return -1;
+}
+
+/* Return true if all sub-sequences in `subseqs` could be found in
+ * `seq` one after another. Sub-sequences are separated by a single
+ * nil instruction.
+ */
+static bool find_all_insn_subseqs(struct bpf_insn *seq, struct bpf_insn *subseqs,
+ int seq_len, int max_subseqs_len)
+{
+ int subseqs_len = null_terminated_insn_len(subseqs, max_subseqs_len);
+
+ while (subseqs_len > 0) {
+ int skip_idx = find_skip_insn_marker(subseqs, subseqs_len);
+ int cur_subseq_len = skip_idx < 0 ? subseqs_len : skip_idx;
+ int subseq_idx = find_insn_subseq(seq, subseqs,
+ seq_len, cur_subseq_len);
+
+ if (subseq_idx < 0)
+ return false;
+ seq += subseq_idx + cur_subseq_len;
+ seq_len -= subseq_idx + cur_subseq_len;
+ subseqs += cur_subseq_len + 1;
+ subseqs_len -= cur_subseq_len + 1;
+ }
+
+ return true;
+}
+
+static void print_insn(struct bpf_insn *buf, int cnt)
+{
+ int i;
+
+ printf(" addr op d s off imm\n");
+ for (i = 0; i < cnt; ++i) {
+ struct bpf_insn *insn = &buf[i];
+
+ if (is_null_insn(insn))
+ break;
+
+ if (is_skip_insn(insn))
+ printf(" ...\n");
+ else
+ printf(" %04x: %02x %1x %x %04hx %08x\n",
+ i, insn->code, insn->dst_reg,
+ insn->src_reg, insn->off, insn->imm);
+ }
+}
+
+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) {
+ printf("Program:\n");
+ print_insn(buf, cnt);
+ printf("Expected subsequence:\n");
+ print_insn(test->expected_insns, MAX_EXPECTED_INSNS);
+ }
+ }
+
+ if (check_unexpected &&
+ find_all_insn_subseqs(buf, test->unexpected_insns,
+ cnt, MAX_UNEXPECTED_INSNS)) {
+ 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 +1493,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
^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 1/5] selftests/bpf: specify expected instructions in test_verifier tests
2022-06-08 19:26 ` [PATCH bpf-next v4 1/5] selftests/bpf: specify expected instructions in test_verifier tests Eduard Zingerman
@ 2022-06-10 17:56 ` Song Liu
0 siblings, 0 replies; 22+ messages in thread
From: Song Liu @ 2022-06-10 17:56 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Wed, Jun 8, 2022 at 12:27 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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:
>
[...]
>
> 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 <eddyz87@gmail.com>
Acked-by: Song Liu <songliubraving@fb.com>
^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH bpf-next v4 2/5] selftests/bpf: allow BTF specs and func infos in test_verifier tests
2022-06-08 19:26 [PATCH bpf-next v4 0/5] bpf_loop inlining Eduard Zingerman
2022-06-08 19:26 ` [PATCH bpf-next v4 1/5] selftests/bpf: specify expected instructions in test_verifier tests Eduard Zingerman
@ 2022-06-08 19:26 ` Eduard Zingerman
2022-06-10 18:09 ` Song Liu
2022-06-08 19:26 ` [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known Eduard Zingerman
` (2 subsequent siblings)
4 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-08 19:26 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, song, joannelkoong; +Cc: eddyz87
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 <eddyz87@gmail.com>
---
tools/testing/selftests/bpf/prog_tests/btf.c | 1 -
tools/testing/selftests/bpf/test_btf.h | 2 +
tools/testing/selftests/bpf/test_verifier.c | 94 ++++++++++++++++----
3 files changed, 79 insertions(+), 18 deletions(-)
diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/selftests/bpf/prog_tests/btf.c
index edb387163baa..1fd792a92a1c 100644
--- a/tools/testing/selftests/bpf/prog_tests/btf.c
+++ b/tools/testing/selftests/bpf/prog_tests/btf.c
@@ -34,7 +34,6 @@ static bool always_log;
#undef CHECK
#define CHECK(condition, format...) _CHECK(condition, "check", duration, format)
-#define BTF_END_RAW 0xdeadbeef
#define NAME_TBD 0xdeadb33f
#define NAME_NTH(N) (0xfffe0000 | N)
diff --git a/tools/testing/selftests/bpf/test_btf.h b/tools/testing/selftests/bpf/test_btf.h
index 38782bd47fdc..fb4f4714eeb4 100644
--- a/tools/testing/selftests/bpf/test_btf.h
+++ b/tools/testing/selftests/bpf/test_btf.h
@@ -4,6 +4,8 @@
#ifndef _TEST_BTF_H
#define _TEST_BTF_H
+#define BTF_END_RAW 0xdeadbeef
+
#define BTF_INFO_ENC(kind, kind_flag, vlen) \
((!!(kind_flag) << 31) | ((kind) << 24) | ((vlen) & BTF_MAX_VLEN))
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 1f24eae9e16e..7fe897c66d81 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -59,11 +59,17 @@
#define MAX_TEST_RUNS 8
#define POINTER_VALUE 0xcafe4all
#define TEST_DATA_LEN 64
+#define MAX_FUNC_INFOS 8
+#define MAX_BTF_STRINGS 256
+#define MAX_BTF_TYPES 256
#define INSN_OFF_MASK ((__s16)0xFFFF)
#define INSN_IMM_MASK ((__s32)0xFFFFFFFF)
#define SKIP_INSNS() BPF_RAW_INSN(0xde, 0xa, 0xd, 0xbeef, 0xdeadbeef)
+#define DEFAULT_LIBBPF_LOG_LEVEL 4
+#define VERBOSE_LIBBPF_LOG_LEVEL 1
+
#define F_NEEDS_EFFICIENT_UNALIGNED_ACCESS (1 << 0)
#define F_LOAD_WITH_STRICT_ALIGNMENT (1 << 1)
@@ -158,6 +164,14 @@ struct bpf_test {
};
enum bpf_attach_type expected_attach_type;
const char *kfunc;
+ struct bpf_func_info func_info[MAX_FUNC_INFOS];
+ int func_info_cnt;
+ char btf_strings[MAX_BTF_STRINGS];
+ /* A set of BTF types to load when specified,
+ * use macro definitions from test_btf.h,
+ * must end with BTF_END_RAW
+ */
+ __u32 btf_types[MAX_BTF_TYPES];
};
/* Note we want this to be 64 bit aligned so that the end of our array is
@@ -687,34 +701,66 @@ static __u32 btf_raw_types[] = {
BTF_MEMBER_ENC(71, 13, 128), /* struct prog_test_member __kptr_ref *ptr; */
};
-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;
+ LIBBPF_OPTS(bpf_btf_load_opts, opts,
+ .log_buf = bpf_vlog,
+ .log_size = sizeof(bpf_vlog),
+ .log_level = (verbose
+ ? VERBOSE_LIBBPF_LOG_LEVEL
+ : DEFAULT_LIBBPF_LOG_LEVEL),
+ );
- 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;
- btf_fd = bpf_btf_load(raw_btf, ptr - raw_btf, NULL);
- free(raw_btf);
+ 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;
+}
+
+static int load_btf(void)
+{
+ return load_btf_spec(btf_raw_types, sizeof(btf_raw_types),
+ btf_str_sec, sizeof(btf_str_sec));
+}
+
+static int load_btf_for_test(struct bpf_test *test)
+{
+ int types_num = 0;
+
+ while (types_num < MAX_BTF_TYPES &&
+ test->btf_types[types_num] != BTF_END_RAW)
+ ++types_num;
+
+ int types_len = types_num * sizeof(test->btf_types[0]);
+
+ return load_btf_spec(test->btf_types, types_len,
+ test->btf_strings, sizeof(test->btf_strings));
}
static int create_map_spin_lock(void)
@@ -793,8 +839,6 @@ static int create_map_kptr(void)
return fd;
}
-static char bpf_vlog[UINT_MAX >> 8];
-
static void do_test_fixup(struct bpf_test *test, enum bpf_prog_type prog_type,
struct bpf_insn *prog, int *map_fds)
{
@@ -1360,7 +1404,7 @@ static bool check_xlated_program(struct bpf_test *test, int fd_prog)
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);
@@ -1372,8 +1416,10 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
__u32 pflags;
int i, err;
+ fd_prog = -1;
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;
@@ -1406,11 +1452,11 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
opts.expected_attach_type = test->expected_attach_type;
if (verbose)
- opts.log_level = 1;
+ opts.log_level = VERBOSE_LIBBPF_LOG_LEVEL;
else if (expected_ret == VERBOSE_ACCEPT)
opts.log_level = 2;
else
- opts.log_level = 4;
+ opts.log_level = DEFAULT_LIBBPF_LOG_LEVEL;
opts.prog_flags = pflags;
if (prog_type == BPF_PROG_TYPE_TRACING && test->kfunc) {
@@ -1428,6 +1474,19 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
opts.attach_btf_id = attach_btf_id;
}
+ if (test->btf_types[0] != 0) {
+ btf_fd = load_btf_for_test(test);
+ if (btf_fd < 0)
+ goto fail_log;
+ opts.prog_btf_fd = btf_fd;
+ }
+
+ if (test->func_info_cnt != 0) {
+ opts.func_info = test->func_info;
+ opts.func_info_cnt = test->func_info_cnt;
+ opts.func_info_rec_size = sizeof(test->func_info[0]);
+ }
+
opts.log_buf = bpf_vlog;
opts.log_size = sizeof(bpf_vlog);
fd_prog = bpf_prog_load(prog_type, NULL, "GPL", prog, prog_len, &opts);
@@ -1539,6 +1598,7 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
if (test->fill_insns)
free(test->fill_insns);
close(fd_prog);
+ close(btf_fd);
for (i = 0; i < MAX_NR_MAPS; i++)
close(map_fds[i]);
sched_yield();
--
2.25.1
^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 2/5] selftests/bpf: allow BTF specs and func infos in test_verifier tests
2022-06-08 19:26 ` [PATCH bpf-next v4 2/5] selftests/bpf: allow BTF specs and func infos " Eduard Zingerman
@ 2022-06-10 18:09 ` Song Liu
2022-06-10 19:16 ` Eduard Zingerman
0 siblings, 1 reply; 22+ messages in thread
From: Song Liu @ 2022-06-10 18:09 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Wed, Jun 8, 2022 at 12:27 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <eddyz87@gmail.com>
[...]
> +
> +static int load_btf_for_test(struct bpf_test *test)
> +{
> + int types_num = 0;
> +
> + while (types_num < MAX_BTF_TYPES &&
> + test->btf_types[types_num] != BTF_END_RAW)
> + ++types_num;
> +
> + int types_len = types_num * sizeof(test->btf_types[0]);
> +
> + return load_btf_spec(test->btf_types, types_len,
> + test->btf_strings, sizeof(test->btf_strings));
IIUC, strings_len is always 256. Is this expected?
Thanks,
Song
> }
>
> static int create_map_spin_lock(void)
> @@ -793,8 +839,6 @@ static int create_map_kptr(void)
> return fd;
> }
[...]
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 2/5] selftests/bpf: allow BTF specs and func infos in test_verifier tests
2022-06-10 18:09 ` Song Liu
@ 2022-06-10 19:16 ` Eduard Zingerman
2022-06-10 20:56 ` Song Liu
0 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-10 19:16 UTC (permalink / raw)
To: Song Liu
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
> On Fri, 2022-06-10 at 11:09 -0700, Song Liu wrote:
> > +static int load_btf_for_test(struct bpf_test *test)
> > +{
> > + int types_num = 0;
> > +
> > + while (types_num < MAX_BTF_TYPES &&
> > + test->btf_types[types_num] != BTF_END_RAW)
> > + ++types_num;
> > +
> > + int types_len = types_num * sizeof(test->btf_types[0]);
> > +
> > + return load_btf_spec(test->btf_types, types_len,
> > + test->btf_strings, sizeof(test->btf_strings));
>
> IIUC, strings_len is always 256. Is this expected?
Yes, as long as strings are zero terminated the actual buffer size
shouldn't matter. So I decided that it would be better to avoid
strings length specification in the test definition to keep things
simpler.
Thanks,
Eduard
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 2/5] selftests/bpf: allow BTF specs and func infos in test_verifier tests
2022-06-10 19:16 ` Eduard Zingerman
@ 2022-06-10 20:56 ` Song Liu
0 siblings, 0 replies; 22+ messages in thread
From: Song Liu @ 2022-06-10 20:56 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Fri, Jun 10, 2022 at 12:16 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> > On Fri, 2022-06-10 at 11:09 -0700, Song Liu wrote:
>
> > > +static int load_btf_for_test(struct bpf_test *test)
> > > +{
> > > + int types_num = 0;
> > > +
> > > + while (types_num < MAX_BTF_TYPES &&
> > > + test->btf_types[types_num] != BTF_END_RAW)
> > > + ++types_num;
> > > +
> > > + int types_len = types_num * sizeof(test->btf_types[0]);
> > > +
> > > + return load_btf_spec(test->btf_types, types_len,
> > > + test->btf_strings, sizeof(test->btf_strings));
> >
> > IIUC, strings_len is always 256. Is this expected?
>
> Yes, as long as strings are zero terminated the actual buffer size
> shouldn't matter. So I decided that it would be better to avoid
> strings length specification in the test definition to keep things
> simpler.
Hmm.. OK, I guess this is acceptable for the test.
Acked-by: Song Liu <songliubraving@fb.com>
^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-08 19:26 [PATCH bpf-next v4 0/5] bpf_loop inlining Eduard Zingerman
2022-06-08 19:26 ` [PATCH bpf-next v4 1/5] selftests/bpf: specify expected instructions in test_verifier tests Eduard Zingerman
2022-06-08 19:26 ` [PATCH bpf-next v4 2/5] selftests/bpf: allow BTF specs and func infos " Eduard Zingerman
@ 2022-06-08 19:26 ` Eduard Zingerman
2022-06-09 14:56 ` kernel test robot
2022-06-10 20:54 ` Song Liu
2022-06-08 19:26 ` [PATCH bpf-next v4 4/5] selftests/bpf: BPF test_verifier selftests for bpf_loop inlining Eduard Zingerman
2022-06-08 19:26 ` [PATCH bpf-next v4 5/5] selftests/bpf: BPF test_prog " Eduard Zingerman
4 siblings, 2 replies; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-08 19:26 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, song, joannelkoong; +Cc: eddyz87
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: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf.h | 3 +
include/linux/bpf_verifier.h | 12 +++
kernel/bpf/bpf_iter.c | 9 +-
kernel/bpf/verifier.c | 168 +++++++++++++++++++++++++++++++++--
4 files changed, 183 insertions(+), 9 deletions(-)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 8e6092d0ea95..3c75ede138b5 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1236,6 +1236,9 @@ struct bpf_array {
#define BPF_COMPLEXITY_LIMIT_INSNS 1000000 /* yes. 1M insns */
#define MAX_TAIL_CALL_CNT 33
+/* Maximum number of loops for bpf_loop */
+#define BPF_MAX_LOOPS BIT(23)
+
#define BPF_F_ACCESS_MASK (BPF_F_RDONLY | \
BPF_F_RDONLY_PROG | \
BPF_F_WRONLY | \
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index e8439f6cbe57..5df09fc46043 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -344,6 +344,14 @@ struct bpf_verifier_state_list {
int miss_cnt, hit_cnt;
};
+struct bpf_loop_inline_state {
+ bool initialized; /* set to true upon first entry */
+ bool fit_for_inline; /* true if callback function is the same
+ * at each call and flags are always zero
+ */
+ u32 callback_subprogno; /* valid when fit_for_inline is true */
+};
+
/* Possible states for alu_state member. */
#define BPF_ALU_SANITIZE_SRC (1U << 0)
#define BPF_ALU_SANITIZE_DST (1U << 1)
@@ -373,6 +381,10 @@ struct bpf_insn_aux_data {
u32 mem_size; /* mem_size for non-struct typed var */
};
} btf_var;
+ /* if instruction is a call to bpf_loop this field tracks
+ * the state of the relevant registers to make decision about inlining
+ */
+ struct bpf_loop_inline_state loop_inline_state;
};
u64 map_key_state; /* constant (32 bit) key tracking for maps */
int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
diff --git a/kernel/bpf/bpf_iter.c b/kernel/bpf/bpf_iter.c
index d5d96ceca105..7e8fd49406f6 100644
--- a/kernel/bpf/bpf_iter.c
+++ b/kernel/bpf/bpf_iter.c
@@ -723,9 +723,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 +730,13 @@ 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. See
+ * function verifier.c:inline_bpf_loop.
+ */
if (flags)
return -EINVAL;
- if (nr_loops > MAX_LOOPS)
+ if (nr_loops > BPF_MAX_LOOPS)
return -E2BIG;
for (i = 0; i < nr_loops; i++) {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2d2872682278..81291dfa63cf 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7103,6 +7103,31 @@ 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];
+}
+
+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 = ®s[BPF_REG_4];
+
+ int flags_is_zero =
+ register_is_const(flags_reg) && flags_reg->var_off.value == 0;
+
+ if (state->initialized) {
+ state->fit_for_inline &=
+ flags_is_zero &&
+ state->callback_subprogno == subprogno;
+ } else {
+ state->initialized = 1;
+ state->fit_for_inline = 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 +7280,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 +7687,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,
@@ -14294,6 +14315,140 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
return 0;
}
+struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
+ int position,
+ s32 stack_base,
+ u32 callback_subprogno,
+ u32 *cnt)
+{
+ 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_start;
+ u32 call_insn_offset;
+ s32 callback_offset;
+
+ /* This represents an inlined version of bpf_iter.c:bpf_loop,
+ * be careful to modify this code in sync.
+ */
+ struct bpf_insn insn_buf[] = {
+ /* Return error and jump to the end of the patch if
+ * expected number of iterations is too big.
+ */
+ 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),
+ };
+
+ *cnt = ARRAY_SIZE(insn_buf);
+ 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;
+ /* Note: insn_buf[12] is an offset of BPF_CALL_REL instruction */
+ call_insn_offset = position + 12;
+ callback_offset = callback_start - call_insn_offset - 1;
+ env->prog->insnsi[call_insn_offset].imm = callback_offset;
+
+ return new_prog;
+}
+
+static bool is_bpf_loop_call(struct bpf_insn *insn)
+{
+ return insn->code == (BPF_JMP | BPF_CALL) &&
+ insn->src_reg == 0 &&
+ insn->imm == BPF_FUNC_loop;
+}
+
+/* For all sub-programs in the program (including main) check
+ * insn_aux_data to see if there are bpf_loop calls that require
+ * inlining. If such calls are found the calls are replaced with a
+ * sequence of instructions produced by `inline_bpf_loop` function and
+ * subprog stack_depth is increased by the size of 3 registers.
+ * This stack space is used to spill values of the R6, R7, R8. These
+ * registers are used to store the loop bound, counter and context
+ * variables.
+ */
+static int optimize_bpf_loop(struct bpf_verifier_env *env)
+{
+ struct bpf_subprog_info *subprogs = env->subprog_info;
+ int i, cur_subprog = 0, cnt, delta = 0;
+ struct bpf_insn *insn = env->prog->insnsi;
+ int insn_cnt = env->prog->len;
+ u16 stack_depth = subprogs[cur_subprog].stack_depth;
+ u16 stack_depth_extra = 0;
+
+ for (i = 0; i < insn_cnt; i++, insn++) {
+ struct bpf_loop_inline_state *inline_state =
+ &env->insn_aux_data[i + delta].loop_inline_state;
+
+ if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) {
+ struct bpf_prog *new_prog;
+
+ stack_depth_extra = BPF_REG_SIZE * 3;
+ new_prog = inline_bpf_loop(env,
+ i + delta,
+ -(stack_depth + stack_depth_extra),
+ inline_state->callback_subprogno,
+ &cnt);
+ if (!new_prog)
+ return -ENOMEM;
+
+ delta += cnt - 1;
+ env->prog = new_prog;
+ insn = new_prog->insnsi + i + delta;
+ }
+
+ if (subprogs[cur_subprog + 1].start == i + delta + 1) {
+ subprogs[cur_subprog].stack_depth += stack_depth_extra;
+ cur_subprog++;
+ stack_depth = subprogs[cur_subprog].stack_depth;
+ stack_depth_extra = 0;
+ }
+ }
+
+ env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
+
+ return 0;
+}
+
static void free_states(struct bpf_verifier_env *env)
{
struct bpf_verifier_state_list *sl, *sln;
@@ -15030,6 +15185,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)
+ optimize_bpf_loop(env);
+
/* instruction rewrites happen after this point */
if (is_priv) {
if (ret == 0)
--
2.25.1
^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-08 19:26 ` [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known Eduard Zingerman
@ 2022-06-09 14:56 ` kernel test robot
2022-06-10 20:54 ` Song Liu
1 sibling, 0 replies; 22+ messages in thread
From: kernel test robot @ 2022-06-09 14:56 UTC (permalink / raw)
To: Eduard Zingerman, bpf, ast, andrii, daniel, kernel-team, song,
joannelkoong
Cc: llvm, kbuild-all, eddyz87
Hi Eduard,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on bpf-next/master]
url: https://github.com/intel-lab-lkp/linux/commits/Eduard-Zingerman/bpf_loop-inlining/20220609-033007
base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
config: arm-randconfig-r014-20220608 (https://download.01.org/0day-ci/archive/20220609/202206092228.SWNGbTFO-lkp@intel.com/config)
compiler: clang version 15.0.0 (https://github.com/llvm/llvm-project 971e13d69e3e7b687213fef22952be6a328c426c)
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# install arm cross compiling tool for clang build
# apt-get install binutils-arm-linux-gnueabi
# https://github.com/intel-lab-lkp/linux/commit/10671a6a0479bb7ee4d437c4ce7307f198cb96fd
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Eduard-Zingerman/bpf_loop-inlining/20220609-033007
git checkout 10671a6a0479bb7ee4d437c4ce7307f198cb96fd
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=arm SHELL=/bin/bash kernel/bpf/
If you fix the issue, kindly add following tag where applicable
Reported-by: kernel test robot <lkp@intel.com>
All warnings (new ones prefixed by >>):
>> kernel/bpf/verifier.c:7111:6: warning: no previous prototype for function 'update_loop_inline_state' [-Wmissing-prototypes]
void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
^
kernel/bpf/verifier.c:7111:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
^
static
>> kernel/bpf/verifier.c:14318:18: warning: no previous prototype for function 'inline_bpf_loop' [-Wmissing-prototypes]
struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
^
kernel/bpf/verifier.c:14318:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
^
static
2 warnings generated.
vim +/update_loop_inline_state +7111 kernel/bpf/verifier.c
7110
> 7111 void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
7112 {
7113 struct bpf_loop_inline_state *state = &cur_aux(env)->loop_inline_state;
7114 struct bpf_reg_state *regs = cur_regs(env);
7115 struct bpf_reg_state *flags_reg = ®s[BPF_REG_4];
7116
7117 int flags_is_zero =
7118 register_is_const(flags_reg) && flags_reg->var_off.value == 0;
7119
7120 if (state->initialized) {
7121 state->fit_for_inline &=
7122 flags_is_zero &&
7123 state->callback_subprogno == subprogno;
7124 } else {
7125 state->initialized = 1;
7126 state->fit_for_inline = flags_is_zero;
7127 state->callback_subprogno = subprogno;
7128 }
7129 }
7130
--
0-DAY CI Kernel Test Service
https://01.org/lkp
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-08 19:26 ` [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known Eduard Zingerman
2022-06-09 14:56 ` kernel test robot
@ 2022-06-10 20:54 ` Song Liu
2022-06-10 21:54 ` Eduard Zingerman
1 sibling, 1 reply; 22+ messages in thread
From: Song Liu @ 2022-06-10 20:54 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Wed, Jun 8, 2022 at 12:27 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
[...]
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> include/linux/bpf.h | 3 +
> include/linux/bpf_verifier.h | 12 +++
> kernel/bpf/bpf_iter.c | 9 +-
> kernel/bpf/verifier.c | 168 +++++++++++++++++++++++++++++++++--
> 4 files changed, 183 insertions(+), 9 deletions(-)
[...]
> +struct bpf_loop_inline_state {
> + bool initialized; /* set to true upon first entry */
> + bool fit_for_inline; /* true if callback function is the same
> + * at each call and flags are always zero
> + */
> + u32 callback_subprogno; /* valid when fit_for_inline is true */
> +};
nit: We only need one bit for initialized and fit_for_inline.
> +
> /* Possible states for alu_state member. */
> #define BPF_ALU_SANITIZE_SRC (1U << 0)
> #define BPF_ALU_SANITIZE_DST (1U << 1)
> @@ -373,6 +381,10 @@ struct bpf_insn_aux_data {
> u32 mem_size; /* mem_size for non-struct typed var */
> };
[...]
> +
> +void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
static void ...
> +{
> + 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 = ®s[BPF_REG_4];
> +
nit: we usually don't have empty lines here.
> + int flags_is_zero =
> + register_is_const(flags_reg) && flags_reg->var_off.value == 0;
If we replace "fit_for_inline" with "not_fit_for_inline", we can make the cannot
inline case faster with:
if (state->not_fit_for_inline)
return;
> +
> + if (state->initialized) {
> + state->fit_for_inline &=
> + flags_is_zero &&
> + state->callback_subprogno == subprogno;
> + } else {
> + state->initialized = 1;
> + state->fit_for_inline = flags_is_zero;
> + state->callback_subprogno = subprogno;
> + }
> +}
> +
[...]
>
> +struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
> + int position,
> + s32 stack_base,
> + u32 callback_subprogno,
> + u32 *cnt)
missing static
> +{
> + 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;
> +
[...]
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-10 20:54 ` Song Liu
@ 2022-06-10 21:54 ` Eduard Zingerman
2022-06-10 22:40 ` Song Liu
0 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-10 21:54 UTC (permalink / raw)
To: Song Liu
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
> On Fri, 2022-06-10 at 13:54 -0700, Song Liu wrote:
> > +
> > +void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
>
> static void ...
>
> > +{
> > + 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 = ®s[BPF_REG_4];
> > +
>
> nit: we usually don't have empty lines here.
>
> > + int flags_is_zero =
> > + register_is_const(flags_reg) && flags_reg->var_off.value == 0;
>
> If we replace "fit_for_inline" with "not_fit_for_inline", we can make the cannot
> inline case faster with:
>
> if (state->not_fit_for_inline)
> return;
>
> > +
> > + if (state->initialized) {
> > + state->fit_for_inline &=
> > + flags_is_zero &&
> > + state->callback_subprogno == subprogno;
> > + } else {
> > + state->initialized = 1;
> > + state->fit_for_inline = flags_is_zero;
> > + state->callback_subprogno = subprogno;
> > + }
> > +}
> > +
Sorry, I'm not sure that I understand you correctly. Do you want me to
rewrite the code as follows:
struct bpf_loop_inline_state {
int initialized:1; /* set to true upon first entry */
int not_fit_for_inline:1; /* false if callback function is thesame
* at each call and flags are always zero
*/
u32 callback_subprogno; /* valid when fit_for_inline is true */
};
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 = ®s[BPF_REG_4];
int flags_is_zero =
register_is_const(flags_reg) && flags_reg->var_off.value == 0;
if (state->not_fit_for_inline)
return;
if (state->initialized) {
state->not_fit_for_inline |=
!flags_is_zero ||
state->callback_subprogno != subprogno;
} else {
state->initialized = 1;
state->not_fit_for_inline = !flags_is_zero;
state->callback_subprogno = subprogno;
}
}
// ...
static int optimize_bpf_loop(struct bpf_verifier_env *env)
{
// ...
if (is_bpf_loop_call(insn) && !inline_state->not_fit_for_inline) {
// ...
}
IMO, the code is less clear after such rewrite, also
`update_loop_inline_state` is not on a hot path (it is called from
`check_helper_call` only when helper is `bpf_loop`). Are you sure this
rewrite is necessary?
Thanks,
Eduard
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-10 21:54 ` Eduard Zingerman
@ 2022-06-10 22:40 ` Song Liu
2022-06-10 22:49 ` Eduard Zingerman
0 siblings, 1 reply; 22+ messages in thread
From: Song Liu @ 2022-06-10 22:40 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Fri, Jun 10, 2022 at 2:55 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> > On Fri, 2022-06-10 at 13:54 -0700, Song Liu wrote:
>
> > > +
> > > +void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno)
> >
> > static void ...
> >
> > > +{
> > > + 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 = ®s[BPF_REG_4];
> > > +
> >
> > nit: we usually don't have empty lines here.
> >
> > > + int flags_is_zero =
> > > + register_is_const(flags_reg) && flags_reg->var_off.value == 0;
> >
> > If we replace "fit_for_inline" with "not_fit_for_inline", we can make the cannot
> > inline case faster with:
> >
> > if (state->not_fit_for_inline)
> > return;
> >
> > > +
> > > + if (state->initialized) {
> > > + state->fit_for_inline &=
> > > + flags_is_zero &&
> > > + state->callback_subprogno == subprogno;
> > > + } else {
> > > + state->initialized = 1;
> > > + state->fit_for_inline = flags_is_zero;
> > > + state->callback_subprogno = subprogno;
> > > + }
> > > +}
> > > +
>
> Sorry, I'm not sure that I understand you correctly. Do you want me to
> rewrite the code as follows:
Yes, I was thinking about this change. I guess it can also be clear:
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 = ®s[BPF_REG_4];
int flags_is_zero;
if (state->cannot_inline)
return;
flags_is_zero = register_is_const(flags_reg) &&
flags_reg->var_off.value == 0;
if (!state->initialized) {
state->initialized = 1;
state->cannot_inline = !flags_is_zero;
state->callback_subprogno = subprogno;
return;
}
state->cannot_inline = !flags_is_zero ||
state->callback_subprogno != subprogno;
}
What do you think about this version?
Thanks,
Song
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-10 22:40 ` Song Liu
@ 2022-06-10 22:49 ` Eduard Zingerman
2022-06-10 23:01 ` Song Liu
0 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-10 22:49 UTC (permalink / raw)
To: Song Liu
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
> On Fri, 2022-06-10 at 15:40 -0700, Song Liu wrote:
> Yes, I was thinking about this change. I guess it can also be clear:
>
> 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 = ®s[BPF_REG_4];
> int flags_is_zero;
>
> if (state->cannot_inline)
> return;
>
> flags_is_zero = register_is_const(flags_reg) &&
> flags_reg->var_off.value == 0;
>
> if (!state->initialized) {
> state->initialized = 1;
> state->cannot_inline = !flags_is_zero;
> state->callback_subprogno = subprogno;
> return;
> }
>
> state->cannot_inline = !flags_is_zero ||
> state->callback_subprogno != subprogno;
> }
>
> What do you think about this version?
Maybe keep `fit_for_inline` to minimize amount of negations?
As below:
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 = ®s[BPF_REG_4];
int flags_is_zero;
/* this should be compiled as a single instruction anyway */
if (!state->fit_for_inline)
return;
flags_is_zero = register_is_const(flags_reg) && flags_reg->var_off.value == 0;
if (!state->initialized) {
state->initialized = 1;
state->fit_for_inline = flags_is_zero;
state->callback_subprogno = subprogno;
return;
}
state->fit_for_inline = flags_is_zero &&
state->callback_subprogno == subprogno;
}
// ...
static int optimize_bpf_loop(struct bpf_verifier_env *env)
{
if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) { ... }
// vs
if (is_bpf_loop_call(insn) && !inline_state->cannot_inline) { ... }
}
Thanks,
Eduard
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-10 22:49 ` Eduard Zingerman
@ 2022-06-10 23:01 ` Song Liu
2022-06-10 23:21 ` Eduard Zingerman
0 siblings, 1 reply; 22+ messages in thread
From: Song Liu @ 2022-06-10 23:01 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Fri, Jun 10, 2022 at 3:49 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
[...]
> >
> > state->cannot_inline = !flags_is_zero ||
> > state->callback_subprogno != subprogno;
> > }
> >
> > What do you think about this version?
>
> Maybe keep `fit_for_inline` to minimize amount of negations?
> As below:
>
> 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 = ®s[BPF_REG_4];
> int flags_is_zero;
>
> /* this should be compiled as a single instruction anyway */
> if (!state->fit_for_inline)
> return;
In this case, we need to initialize fit_for_inline to true, no?
Thanks,
Song
>
> flags_is_zero = register_is_const(flags_reg) && flags_reg->var_off.value == 0;
>
> if (!state->initialized) {
> state->initialized = 1;
> state->fit_for_inline = flags_is_zero;
> state->callback_subprogno = subprogno;
> return;
> }
>
> state->fit_for_inline = flags_is_zero &&
> state->callback_subprogno == subprogno;
> }
>
> // ...
>
> static int optimize_bpf_loop(struct bpf_verifier_env *env)
> {
> if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) { ... }
> // vs
> if (is_bpf_loop_call(insn) && !inline_state->cannot_inline) { ... }
> }
>
> Thanks,
> Eduard
>
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-10 23:01 ` Song Liu
@ 2022-06-10 23:21 ` Eduard Zingerman
2022-06-11 1:46 ` Song Liu
0 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-10 23:21 UTC (permalink / raw)
To: Song Liu
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
> On Fri, 2022-06-10 at 16:01 -0700, Song Liu wrote:
>
> In this case, we need to initialize fit_for_inline to true, no?
You are right...
My Last try is below, if you don't like it I'll proceed with your
version. I just really don't like the "not-cannot" part in the
expression "!inline_state->cannot_inline" :)
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 = ®s[BPF_REG_4];
int flags_is_zero =
register_is_const(flags_reg) && flags_reg->var_off.value == 0;
if (!state->initialized) {
state->initialized = 1;
state->fit_for_inline = flags_is_zero;
state->callback_subprogno = subprogno;
return;
}
if (!state->fit_for_inline)
return;
state->fit_for_inline =
flags_is_zero &&
state->callback_subprogno == subprogno;
}
static int optimize_bpf_loop(struct bpf_verifier_env *env)
{
// ...
if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) { ... }
// ...
}
Thanks,
Eduard
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known
2022-06-10 23:21 ` Eduard Zingerman
@ 2022-06-11 1:46 ` Song Liu
0 siblings, 0 replies; 22+ messages in thread
From: Song Liu @ 2022-06-11 1:46 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Fri, Jun 10, 2022 at 4:21 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> > On Fri, 2022-06-10 at 16:01 -0700, Song Liu wrote:
> >
> > In this case, we need to initialize fit_for_inline to true, no?
>
> You are right...
>
> My Last try is below, if you don't like it I'll proceed with your
> version. I just really don't like the "not-cannot" part in the
> expression "!inline_state->cannot_inline" :)
Yeah, this version looks good to me.
Thanks,
Song
>
> 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 = ®s[BPF_REG_4];
> int flags_is_zero =
> register_is_const(flags_reg) && flags_reg->var_off.value == 0;
>
> if (!state->initialized) {
> state->initialized = 1;
> state->fit_for_inline = flags_is_zero;
> state->callback_subprogno = subprogno;
> return;
> }
>
> if (!state->fit_for_inline)
> return;
>
> state->fit_for_inline =
> flags_is_zero &&
> state->callback_subprogno == subprogno;
> }
>
> static int optimize_bpf_loop(struct bpf_verifier_env *env)
> {
> // ...
> if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) { ... }
> // ...
> }
>
> Thanks,
> Eduard
>
^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH bpf-next v4 4/5] selftests/bpf: BPF test_verifier selftests for bpf_loop inlining
2022-06-08 19:26 [PATCH bpf-next v4 0/5] bpf_loop inlining Eduard Zingerman
` (2 preceding siblings ...)
2022-06-08 19:26 ` [PATCH bpf-next v4 3/5] bpf: Inline calls to bpf_loop when callback is known Eduard Zingerman
@ 2022-06-08 19:26 ` Eduard Zingerman
2022-06-10 18:14 ` Song Liu
2022-06-08 19:26 ` [PATCH bpf-next v4 5/5] selftests/bpf: BPF test_prog " Eduard Zingerman
4 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-08 19:26 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, song, joannelkoong; +Cc: eddyz87
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 <eddyz87@gmail.com>
---
.../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
diff --git a/tools/testing/selftests/bpf/verifier/bpf_loop_inline.c b/tools/testing/selftests/bpf/verifier/bpf_loop_inline.c
new file mode 100644
index 000000000000..d1fbcfef69f2
--- /dev/null
+++ b/tools/testing/selftests/bpf/verifier/bpf_loop_inline.c
@@ -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
^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 4/5] selftests/bpf: BPF test_verifier selftests for bpf_loop inlining
2022-06-08 19:26 ` [PATCH bpf-next v4 4/5] selftests/bpf: BPF test_verifier selftests for bpf_loop inlining Eduard Zingerman
@ 2022-06-10 18:14 ` Song Liu
2022-06-10 19:20 ` Eduard Zingerman
0 siblings, 1 reply; 22+ messages in thread
From: Song Liu @ 2022-06-10 18:14 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Wed, Jun 8, 2022 at 12:27 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <eddyz87@gmail.com>
Acked-by: Song Liu <songliubraving@fb.com>
PS: I already acked v3, so you can include it in v4.
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 4/5] selftests/bpf: BPF test_verifier selftests for bpf_loop inlining
2022-06-10 18:14 ` Song Liu
@ 2022-06-10 19:20 ` Eduard Zingerman
2022-06-10 20:57 ` Song Liu
0 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-10 19:20 UTC (permalink / raw)
To: Song Liu
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
> On Fri, 2022-06-10 at 11:14 -0700, Song Liu wrote:
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
>
> Acked-by: Song Liu <songliubraving@fb.com>
>
> PS: I already acked v3, so you can include it in v4.
Sorry, my first patch, wasn't sure what to do with the ack. Should I
put it in the changelog or in the commit message?
Thanks,
Eduard
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 4/5] selftests/bpf: BPF test_verifier selftests for bpf_loop inlining
2022-06-10 19:20 ` Eduard Zingerman
@ 2022-06-10 20:57 ` Song Liu
0 siblings, 0 replies; 22+ messages in thread
From: Song Liu @ 2022-06-10 20:57 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Fri, Jun 10, 2022 at 12:20 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> > On Fri, 2022-06-10 at 11:14 -0700, Song Liu wrote:
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> >
> > Acked-by: Song Liu <songliubraving@fb.com>
> >
> > PS: I already acked v3, so you can include it in v4.
>
> Sorry, my first patch, wasn't sure what to do with the ack. Should I
> put it in the changelog or in the commit message?
You can just add it to the commit message, right next to your
Signed-of-by tag.
Thanks,
Song
^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH bpf-next v4 5/5] selftests/bpf: BPF test_prog selftests for bpf_loop inlining
2022-06-08 19:26 [PATCH bpf-next v4 0/5] bpf_loop inlining Eduard Zingerman
` (3 preceding siblings ...)
2022-06-08 19:26 ` [PATCH bpf-next v4 4/5] selftests/bpf: BPF test_verifier selftests for bpf_loop inlining Eduard Zingerman
@ 2022-06-08 19:26 ` Eduard Zingerman
2022-06-10 18:15 ` Song Liu
4 siblings, 1 reply; 22+ messages in thread
From: Eduard Zingerman @ 2022-06-08 19:26 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, song, joannelkoong; +Cc: eddyz87
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 <eddyz87@gmail.com>
---
.../selftests/bpf/prog_tests/bpf_loop.c | 62 ++++++++++
tools/testing/selftests/bpf/progs/bpf_loop.c | 114 ++++++++++++++++++
2 files changed, 176 insertions(+)
diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_loop.c b/tools/testing/selftests/bpf/prog_tests/bpf_loop.c
index 380d7a2072e3..4cd8a25afe68 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_loop.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_loop.c
@@ -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");
+
+ bpf_link__destroy(link);
+}
+
+static void check_stack(struct bpf_loop *skel)
+{
+ struct bpf_link *link = bpf_program__attach(skel->progs.stack_check);
+ const int max_key = 12;
+ int key;
+ int map_fd;
+
+ if (!ASSERT_OK_PTR(link, "link"))
+ return;
+
+ map_fd = bpf_map__fd(skel->maps.map1);
+
+ if (!ASSERT_GE(map_fd, 0, "bpf_map__fd"))
+ goto out;
+
+ for (key = 1; key <= max_key; ++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 (key = 1; key <= max_key; ++key) {
+ 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);
+}
+
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);
}
diff --git a/tools/testing/selftests/bpf/progs/bpf_loop.c b/tools/testing/selftests/bpf/progs/bpf_loop.c
index e08565282759..de1fc82d2710 100644
--- a/tools/testing/selftests/bpf/progs/bpf_loop.c
+++ b/tools/testing/selftests/bpf/progs/bpf_loop.c
@@ -11,11 +11,19 @@ struct callback_ctx {
int output;
};
+struct {
+ __uint(type, BPF_MAP_TYPE_HASH);
+ __uint(max_entries, 32);
+ __type(key, int);
+ __type(value, int);
+} map1 SEC(".maps");
+
/* These should be set by the user program */
u32 nested_callback_nr_loops;
u32 stop_index = -1;
u32 nr_loops;
int pid;
+int callback_selector;
/* Making these global variables so that the userspace program
* can verify the output through the skeleton
@@ -111,3 +119,109 @@ int prog_nested_calls(void *ctx)
return 0;
}
+
+static int callback_set_f0(int i, void *ctx)
+{
+ g_output = 0xF0;
+ return 0;
+}
+
+static int callback_set_0f(int i, void *ctx)
+{
+ g_output = 0x0F;
+ return 0;
+}
+
+/*
+ * non-constant callback is a corner case for bpf_loop inline logic
+ */
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int prog_non_constant_callback(void *ctx)
+{
+ struct callback_ctx data = {};
+
+ if (bpf_get_current_pid_tgid() >> 32 != pid)
+ return 0;
+
+ int (*callback)(int i, void *ctx);
+
+ g_output = 0;
+
+ if (callback_selector == 0x0F)
+ callback = callback_set_0f;
+ else
+ callback = callback_set_f0;
+
+ bpf_loop(1, callback, NULL, 0);
+
+ return 0;
+}
+
+static int stack_check_inner_callback(void *ctx)
+{
+ return 0;
+}
+
+static int map1_lookup_elem(int key)
+{
+ int *val = bpf_map_lookup_elem(&map1, &key);
+
+ return val ? *val : -1;
+}
+
+static void map1_update_elem(int key, int val)
+{
+ bpf_map_update_elem(&map1, &key, &val, BPF_ANY);
+}
+
+static int stack_check_outer_callback(void *ctx)
+{
+ int a = map1_lookup_elem(1);
+ int b = map1_lookup_elem(2);
+ int c = map1_lookup_elem(3);
+ int d = map1_lookup_elem(4);
+ int e = map1_lookup_elem(5);
+ int f = map1_lookup_elem(6);
+
+ bpf_loop(1, stack_check_inner_callback, NULL, 0);
+
+ map1_update_elem(1, a + 1);
+ map1_update_elem(2, b + 1);
+ map1_update_elem(3, c + 1);
+ map1_update_elem(4, d + 1);
+ map1_update_elem(5, e + 1);
+ map1_update_elem(6, f + 1);
+
+ return 0;
+}
+
+/* Some of the local variables in stack_check and
+ * stack_check_outer_callback would be allocated on stack by
+ * compiler. This test should verify that stack content for these
+ * variables is preserved between calls to bpf_loop (might be an issue
+ * if loop inlining allocates stack slots incorrectly).
+ */
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int stack_check(void *ctx)
+{
+ if (bpf_get_current_pid_tgid() >> 32 != pid)
+ return 0;
+
+ int a = map1_lookup_elem(7);
+ int b = map1_lookup_elem(8);
+ int c = map1_lookup_elem(9);
+ int d = map1_lookup_elem(10);
+ int e = map1_lookup_elem(11);
+ int f = map1_lookup_elem(12);
+
+ bpf_loop(1, stack_check_outer_callback, NULL, 0);
+
+ map1_update_elem(7, a + 1);
+ map1_update_elem(8, b + 1);
+ map1_update_elem(9, c + 1);
+ map1_update_elem(10, d + 1);
+ map1_update_elem(11, e + 1);
+ map1_update_elem(12, f + 1);
+
+ return 0;
+}
--
2.25.1
^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH bpf-next v4 5/5] selftests/bpf: BPF test_prog selftests for bpf_loop inlining
2022-06-08 19:26 ` [PATCH bpf-next v4 5/5] selftests/bpf: BPF test_prog " Eduard Zingerman
@ 2022-06-10 18:15 ` Song Liu
0 siblings, 0 replies; 22+ messages in thread
From: Song Liu @ 2022-06-10 18:15 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, joannelkoong
On Wed, Jun 8, 2022 at 12:27 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <eddyz87@gmail.com>
Acked-by: Song Liu <songliubraving@fb.com>
^ permalink raw reply [flat|nested] 22+ messages in thread