Skip to contentSkip to conversation

bpf_loop inlining

PATCH Superseded Eduard Zingerman 4 participants 14 messages Jun 13, 2022 – Jun 20, 2022

Subsystems (5)
Kselftest BPF BPF selftests BPF core +1 more subsystems

v7 of 8 Superseded Latest is v8 →

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

v7 cover bpf_loop inlining

Hi Everyone,

This is the next iteration of the patch. It includes changes suggested by Song, Joanne and Alexei. Please find updated intro message and change log below.

This patch implements inlining of calls to bpf_loop helper function when bpf_loop's callback is statically known. E.g. the rewrite does the following transformation during BPF program processing:

  bpf_loop(10, foo, NULL, 0);

->

  for (int i = 0; i < 10; ++i)
    foo(i, NULL);

The transformation leads to measurable latency change for simple loops. Measurements using benchs/run_bench_bpf_loop.sh inside QEMU / KVM on i7-4710HQ CPU show a drop in latency from 14 ns/op to 2 ns/op.

The change is split in five parts:

* Update to test_verifier.c to specify expected and unexpected instruction sequences. This allows to check BPF program rewrites applied by e.g. do_mix_fixups function.

* Update to test_verifier.c to specify BTF function infos and types per test case. This is necessary for tests that load sub-program addresses to a variable because of the checks applied by check_ld_imm function.

* The update to verifier.c that tracks state of the parameters for each bpf_loop call in a program and decides whether it could be replaced by a loop.

* A set of test cases for test_verifier that use capabilities added by the first two patches to verify instructions produced by inlining logic.

* Two test cases for test_prog to check that possible corner cases behave as expected.

Additional details are available in commit messages for each patch.

Changes since v6:
- Return value of the optimize_bpf_loop function is no longer ignored. This is necessary to properly propagate -ENOMEM error.

Changes since v5:
- Added function loop_flag_is_zero to skip a few checks in update_loop_inline_state when loop instruction is not fit for inline.

Changes since v4:
- Added missing static modifier for update_loop_inline_state and inline_bpf_loop functions.
- update_loop_inline_state updated for better readability.
- Fields initialized and fit_for_inline of struct bpf_loop_inline_state are changed back from bool to bitfields.
- Acks from Song Liu added to comments for patches 1/5, 2/5, 4/5, 5/5.

Changes since v3:
- Function adjust_stack_depth_for_loop_inlining is replaced by function optimize_bpf_loop. Function optimize_bpf_loop is responsible for both stack depth adjustment and call instruction replacement.
- Changes in do_misc_fixups are reverted.
- Changes in adjust_subprog_starts_after_remove are reverted and function adjust_loop_inline_subprogno is removed. This is possible because call to optimize_bpf_loop is placed before the dead code removal in opt_remove_dead_code (in contrast to the position of do_misc_fixups where inlining was done in v3).
- Field bpf_insn_aux_data.loop_inline_state is now a part of anonymous union at the start of the bpf_insn_aux_data.
- Data structure bpf_loop_inline_state is simplified to use single flag field fit_for_inline instead of separate fields flags_is_zero & callback_is_constant.
- Macro definition BPF_MAX_LOOPS is moved from include/linux/bpf_verifier.h to include/linux/bpf.h to avoid include of include/linux/bpf_verifier.h in bpf_iter.c.
- inline_bpf_loop changed back to use array initialization and hard coded offsets as in v2.
- Style / formatting updates.

Changes since v2:
- fix for stack_check test case in test_progs-no_alu32, all tests are passing now;
- v2 3/3 patch is split in three parts:
- kernel changes
- test_verifier changes
- test_prog changes
- updated inline_bpf_loop in verifier.c to calculate each offset used in instructions to avoid "magic" numbers;
- removed newline handling logic in fail_log branch of do_single_test in test_verifier.c to simplify the patch set;
- styling fixes suggested in review for v2 of this patch set.

Changes since v1:
- allow to use SKIP_INSNS in instruction pattern specification in test_verifier tests;
- fix for a bug in spill offset assignement for loop vars when bpf_loop is located in a non-main function.

Eduard Zingerman (5):
selftests/bpf: specify expected instructions in test_verifier tests selftests/bpf: allow BTF specs and func infos in test_verifier tests
bpf: Inline calls to bpf_loop when callback is known selftests/bpf: BPF test_verifier selftests for bpf_loop inlining selftests/bpf: BPF test_prog selftests for bpf_loop inlining

 include/linux/bpf.h                           |   3 +
 include/linux/bpf_verifier.h                  |  12 +
 kernel/bpf/bpf_iter.c                         |   9 +-
 kernel/bpf/verifier.c                         | 175 +++++++++-
 .../selftests/bpf/prog_tests/bpf_loop.c       |  62 ++++
 tools/testing/selftests/bpf/prog_tests/btf.c  |   1 -
 tools/testing/selftests/bpf/progs/bpf_loop.c  | 114 ++++++
 tools/testing/selftests/bpf/test_btf.h        |   2 +
 tools/testing/selftests/bpf/test_verifier.c   | 328 +++++++++++++++++-
 .../selftests/bpf/verifier/bpf_loop_inline.c  | 244 +++++++++++++
 10 files changed, 923 insertions(+), 27 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/bpf_loop_inline.c
Signature · 1 line
2.25.1
author maintainer
#1 lore raw

PATCH v7 1/5 selftests/bpf: specify expected instructions in test_verifier tests

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 <[email protected]>
Acked-by Song Liu <[email protected]>
---
 tools/testing/selftests/bpf/test_verifier.c | 234 ++++++++++++++++++++
 1 file changed, 234 insertions(+)
tools/testing/selftests/bpf/test_verifier.c +234 -0
index 372579c9f45e..1f24eae9e16e 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

@@ -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) {
Signature · 1 line
2.25.1
author maintainer
#2 lore raw

PATCH v7 2/5 selftests/bpf: allow BTF specs and func infos in test_verifier tests

In reply to Eduard Zingerman

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]>
Acked-by Song Liu <[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  | 94 ++++++++++++++++----
 3 files changed, 79 insertions(+), 18 deletions(-)
tools/testing/selftests/bpf/prog_tests/btf.c +0 -1
index edb387163baa..1fd792a92a1c 100644
@@ -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)
tools/testing/selftests/bpf/test_btf.h +2 -0
index 38782bd47fdc..fb4f4714eeb4 100644
@@ -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))
tools/testing/selftests/bpf/test_verifier.c +77 -17

174 lines not on this page · raw message

Signature · 1 line
2.25.1
author maintainer
#3 lore raw

PATCH v7 3/5 bpf: Inline calls to bpf_loop when callback is known

In reply to Eduard Zingerman

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 <[email protected]>
---
 include/linux/bpf.h          |   3 +
 include/linux/bpf_verifier.h |  12 +++
 kernel/bpf/bpf_iter.c        |   9 +-
 kernel/bpf/verifier.c        | 175 ++++++++++++++++++++++++++++++++++-
 4 files changed, 190 insertions(+), 9 deletions(-)
include/linux/bpf.h +3 -0
index 8e6092d0ea95..3c75ede138b5 100644
@@ -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 |		\
include/linux/bpf_verifier.h +12 -0
index e8439f6cbe57..5cf152b0a53e 100644
@@ -344,6 +344,14 @@ struct bpf_verifier_state_list {
 	int miss_cnt, hit_cnt;
 };
 
+struct bpf_loop_inline_state {
+	int initialized:1; /* set to true upon first entry */
+	int fit_for_inline:1; /* 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 */
kernel/bpf/bpf_iter.c +5 -4
index d5d96ceca105..7e8fd49406f6 100644
@@ -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++) {
kernel/bpf/verifier.c +170 -5

205 lines not on this page · raw message

Signature · 1 line
2.25.1
reviewer Acked-by on v7 3/5
#4 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

Quoted 28 lines · Eduard Zingerman

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;

Quoted 4 lines

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

LGTM.

Acked-by Song Liu <[email protected]>
maintainer
#5 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

In reply to Eduard Zingerman

On 6/13/22 10:50 PM, Eduard Zingerman wrote:
[...]

Quoted 38 lines
kernel/bpf/bpf_iter.c +5 -4
index d5d96ceca105..7e8fd49406f6 100644
@@ -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++) {
kernel/bpf/verifier.c +1 -0
index 2d2872682278..db854c09b603 100644
@@ -7103,6 +7103,38 @@ 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)

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

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+{
+	return &env->insn_aux_data[env->insn_idx];
+}
+
+static bool loop_flag_is_zero(struct bpf_verifier_env *env)
+{
+	struct bpf_reg_state *regs = cur_regs(env);
+	struct bpf_reg_state *reg = &regs[BPF_REG_4];
+
+	return register_is_const(reg) && reg->var_off.value == 0;

I think you might also need to add precision tracking for the flag check :

mark_chain_precision(env, BPF_REG_4)

See also cc52d9140aa92 ("bpf: Fix record_func_key to perform backtracking on r3").. not too much of an issue at the moment, but once we extend flags.

Quoted 32 lines
kernel/bpf/verifier.c +22 -0
+}
+
+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;
+
+	if (!state->initialized) {
+		state->initialized = 1;
+		state->fit_for_inline = loop_flag_is_zero(env);
+		state->callback_subprogno = subprogno;
+		return;
+	}
+
+	if (!state->fit_for_inline)
+		return;
+
+	state->fit_for_inline =
+		loop_flag_is_zero(env) &&
+		state->callback_subprogno == subprogno;
+}
+
  static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
  			     int *insn_idx_p)
  {

@@ -7255,6 +7287,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;
#6 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

In reply to Eduard Zingerman

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

Quoted 8 lines · Eduard Zingerman
kernel/bpf/verifier.c +8 -0
+
+static bool loop_flag_is_zero(struct bpf_verifier_env *env)
+{
+       struct bpf_reg_state *regs = cur_regs(env);
+       struct bpf_reg_state *reg = &regs[BPF_REG_4];
+
+       return register_is_const(reg) && reg->var_off.value == 0;
+}

Great catch here by Daniel.
It needs mark_chain_precision().

Quoted 8 lines
kernel/bpf/verifier.c +8 -0
+
+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;
+
+       if (!state->initialized) {
+               state->initialized = 1;
+               state->fit_for_inline = loop_flag_is_zero(env);

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

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+               state->callback_subprogno = subprogno;
+               return;
+       }
+
+       if (!state->fit_for_inline)
+               return;
+
+       state->fit_for_inline =
+               loop_flag_is_zero(env) &&
+               state->callback_subprogno == subprogno;

No need to heavy indent. Up to 100 char is fine.

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+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++) {

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

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+               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),

See the fix that just landed:
https://lore.kernel.org/bpf/[email protected]/

subprogs[cur_subprog].stack_depth may not be a multiple of 8. But spill slots for r[678] have to be.
We need to round_up(,8) here and
increase stack_depth_extra accordingly.

The rest looks great.
Thank you for working on it!

author maintainer
#7 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

Hi Daniel, Alexei,

Quoted 5 lines · Daniel Borkmann

On Thu, 2022-06-16 at 19:14 -0700, Alexei Starovoitov wrote:

Quoted 2 lines · Eduard Zingerman
kernel/bpf/verifier.c +2 -0
+
+static bool loop_flag_is_zero(struct bpf_verifier_env *env)

[...]

Quoted 3 lines

Great catch here by Daniel.
It needs mark_chain_precision().

Thanks for the catch regarding precision tracking. Unfortunately I struggle to create a test case that demonstrates the issue without the call to mark_chain_precision. As far as I understand this test case should look as follows:

	... do something in such a way that:
	  - there is a branch where
	    BPF_REG_4 is 0, SCALAR_VALUE, !precise
	    and this branch is explored first
	  - there is a branch where
	    BPF_REG_4 is 1, SCALAR_VALUE, !precise

	/* create branching point */
	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 0),
	/* load callback address to r2 */
	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 5),
	BPF_RAW_INSN(0, 0, 0, 0, 0),
	BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 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(),

The "do something" part would then rely on the state pruning logic to skip the verification for the second branch. Namely, the following part of the regsafe function should consider registers identical:

/* Returns true if (rold safe implies rcur safe) */
static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)

{
	...
	switch (base_type(rold->type)) {
	case SCALAR_VALUE:
		...
		if (rcur->type == SCALAR_VALUE) {
here ->			if (!rold->precise && !rcur->precise)
				return true;
			...
		} else {
			...
		}
		...	
	}
	...	
}

However, I don't understand what instructions could mark the register as a scalar with particular value, but w/o precise mark. I tried MOV, JEQ, JNE, MUL, sequence of BPF_ALU64_IMM(MOV, ...) - BPF_STX_MEM
- BPF_LDX_MEM to no avail.

The following observations might be relevant:
- __mark_reg_known does not change the state of the precise mark;
- __mark_reg_unknown always sets precise to true when there are multiple sub-programs (due to the following line:
reg->precise = env->subprog_cnt > 1 || !env->bpf_capable);
- there are always multiple sub-programs when bpf_loop is used.

Could you please suggest what to do with this test?

Best regards,
Eduard Zingerman

#8 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

Quoted 62 lines · Eduard Zingerman

Hi Daniel, Alexei,

Quoted 5 lines · Daniel Borkmann

On Thu, 2022-06-16 at 19:14 -0700, Alexei Starovoitov wrote:

Quoted 2 lines · Eduard Zingerman
kernel/bpf/verifier.c +2 -0
+
+static bool loop_flag_is_zero(struct bpf_verifier_env *env)

[...]

Quoted 3 lines

Great catch here by Daniel.
It needs mark_chain_precision().

Thanks for the catch regarding precision tracking. Unfortunately I struggle to create a test case that demonstrates the issue without the call to mark_chain_precision. As far as I understand this test case should look as follows:

	... do something in such a way that:
	  - there is a branch where
	    BPF_REG_4 is 0, SCALAR_VALUE, !precise
	    and this branch is explored first
	  - there is a branch where
	    BPF_REG_4 is 1, SCALAR_VALUE, !precise

	/* create branching point */
	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 0),
	/* load callback address to r2 */
	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 5),
	BPF_RAW_INSN(0, 0, 0, 0, 0),
	BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 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(),

The "do something" part would then rely on the state pruning logic to skip the verification for the second branch. Namely, the following part of the regsafe function should consider registers identical:

/* Returns true if (rold safe implies rcur safe) */
static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)

{
	...
	switch (base_type(rold->type)) {
	case SCALAR_VALUE:
		...
		if (rcur->type == SCALAR_VALUE) {
here ->			if (!rold->precise && !rcur->precise)
				return true;
			...
		} else {
			...
		}
		...	
	}
	...	
}
Quoted 7 lines

However, I don't understand what instructions could mark the register as a scalar with particular value, but w/o precise mark. I tried MOV, JEQ, JNE, MUL, sequence of BPF_ALU64_IMM(MOV, ...) - BPF_STX_MEM
- BPF_LDX_MEM to no avail.

The following observations might be relevant:
- __mark_reg_known does not change the state of the precise mark;

yes.
Just BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0) and ,1) in the other branch should do it.
The 'mov' won't make the register precise.

So something like below:

r0 = random_u32
r6 = random_u32
if (r0)
goto L;

r4 = 0

pruning_point:
if (r6) goto next;
next:
/* load callback address to r2 */
BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 5), BPF_RAW_INSN(0, 0, 0, 0, 0),
BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 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(),

L:
r4 = 1
goto pruning_point

The fallthrough path will proceed with r4=0 and pruning will trigger is_state_visited() with r4=1 which regsafe will incorrectly recognize as equivalent.

author maintainer
#9 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

Quoted 1 line · Alexei Starovoitov

[...]

Quoted 25 lines

yes.
Just BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0) and ,1) in the other branch should do it.
The 'mov' won't make the register precise.

So something like below:

r0 = random_u32
r6 = random_u32
if (r0)
goto L;

r4 = 0

pruning_point:
if (r6) goto next;
next:
/* load callback address to r2 */
BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, BPF_REG_2, BPF_PSEUDO_FUNC, 0, 5), BPF_RAW_INSN(0, 0, 0, 0, 0),
BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 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(),

Quoted 8 lines

L:
r4 = 1
goto pruning_point

The fallthrough path will proceed with r4=0 and pruning will trigger is_state_visited() with r4=1 which regsafe will incorrectly recognize as equivalent.

Actually this was the first thing I tried. Here is the pseudo code above translated to BPF instructions:

	/* main */
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
	BPF_ALU64_REG(BPF_MOV, BPF_REG_6, BPF_REG_0),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
	BPF_ALU64_REG(BPF_MOV, BPF_REG_7, BPF_REG_0),
	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 9),
	BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 0),
	BPF_JMP_IMM(BPF_JNE, BPF_REG_7, 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, 7),
	BPF_RAW_INSN(0, 0, 0, 0, 0),
	BPF_ALU64_IMM(BPF_MOV, BPF_REG_3, 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(),
	BPF_ALU64_IMM(BPF_MOV, BPF_REG_4, 1),
	BPF_JMP_IMM(BPF_JA, 0, 0, -10),
	/* callback */
	BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 1),
	BPF_EXIT_INSN(),

And here is the verification log for this program:

	#195/p don't inline bpf_loop call, flags non-zero 2 , verifier log:
	func#0 @0
	func#1 @16
	reg type unsupported for arg#0 function main#6
	
	from -1 to 0: R1=ctx(off=0,imm=0) R10=fp0
	0: (85) call bpf_jiffies64#118        ; R0_w=Pscalar()
	1: (bf) r6 = r0                       ; R0_w=Pscalar(id=1) R6_w=Pscalar(id=1)
	2: (85) call bpf_jiffies64#118        ; R0_w=Pscalar()
	3: (bf) r7 = r0                       ; R0_w=Pscalar(id=2) R7_w=Pscalar(id=2)
	4: (55) if r6 != 0x0 goto pc+9        ; R6_w=P0
-->	5: (b7) r4 = 0                        ; R4_w=P0
	6: (55) if r7 != 0x0 goto pc+0        ; R7_w=P0
	7: (b7) r1 = 1                        ; R1_w=P1
	8: (18) r2 = 0x7                      ; R2_w=func(off=0,imm=0)
	10: (b7) r3 = 0                       ; R3_w=P0
	11: (85) call bpf_loop#181
	reg type unsupported for arg#1 function callback#7
	caller:
	 R6=P0 R7=P0 R10=fp0
	callee:
	 frame1: R1=Pscalar() R2_w=P0 R10=fp0 cb
	16: frame1: R1_w=Pscalar() R2_w=P0 cb
	16: (b7) r0 = 1                       ; frame1: R0_w=P1 cb
	17: (95) exit
	returning from callee:
	 frame1: R0_w=P1 R1_w=Pscalar() R2_w=P0 R10=fp0 cb
	to caller at 12:
	 R0_w=Pscalar() R6=P0 R7=P0 R10=fp0
	
	from 17 to 12: R0_w=Pscalar() R6=P0 R7=P0 R10=fp0
	12: (b7) r0 = 0                       ; R0_w=P0
	13: (95) exit
	propagating r4
	
	from 6 to 7: safe
	
	from 4 to 14: R0=Pscalar(id=2) R6=Pscalar(id=1) R7=Pscalar(id=2) R10=fp0
-->	14: (b7) r4 = 1                       ; R4_w=P1
	15: (05) goto pc-10
	6: (55) if r7 != 0x0 goto pc+0        ; R7=P0
	7: (b7) r1 = 1                        ; R1_w=P1
	8: (18) r2 = 0x7                      ; R2_w=func(off=0,imm=0)
	10: (b7) r3 = 0                       ; R3_w=P0
	11: (85) call bpf_loop#181
	[...]

Note that for instructions [5] and [14] R4 is marked as precise. I actually verified in the debugger that this happens because of the following processing logic for MOV:

#0  check_alu_op (...) at kernel/bpf/verifier.c:9177
#1  ... in do_check (...) at kernel/bpf/verifier.c:12100
#2  do_check_common (...) at kernel/bpf/verifier.c:14552
#3  ... in do_check_main () at kernel/bpf/verifier.c:14615

The C code for relevant functions is below. Note that call to __mark_reg_unknown will mark the register as precise when env->subprog_cnt > 1, but for this test case it is 2.

static int do_check(struct bpf_verifier_env *env)

{
	...
		if (class == BPF_ALU || class == BPF_ALU64) {
12100:			err = check_alu_op(env, insn);
			if (err)
				return err;

		} else ...
	...
}

static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)

{
	...
	else if (opcode == BPF_MOV) {
		...
		if (BPF_SRC(insn->code) == BPF_X) {
			...
		} else {
			/* case: R = imm
			 * remember the value we stored into this reg
			 */
			/* clear any state __mark_reg_known doesn't set */
			mark_reg_unknown(env, regs, insn->dst_reg);
			regs[insn->dst_reg].type = SCALAR_VALUE;
			if (BPF_CLASS(insn->code) == BPF_ALU64) {
9177:				__mark_reg_known(regs + insn->dst_reg,
						 insn->imm);
			} else {
				__mark_reg_known(regs + insn->dst_reg,
						 (u32)insn->imm);
			}
		}
		...
	}
	...
}

/* Mark a register as having a completely unknown (scalar) value. */ static void __mark_reg_unknown(const struct bpf_verifier_env *env,
struct bpf_reg_state *reg)

{
	...
	reg->precise = env->subprog_cnt > 1 || !env->bpf_capable;
	...
}

static void mark_reg_unknown(struct bpf_verifier_env *env,
struct bpf_reg_state *regs, u32 regno)

{
	...
	__mark_reg_unknown(env, regs + regno);
}

Thanks,
Eduard

#10 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

Quoted 7 lines · Eduard Zingerman

/* Mark a register as having a completely unknown (scalar) value. */ static void __mark_reg_unknown(const struct bpf_verifier_env *env,
struct bpf_reg_state *reg)

{
        ...
        reg->precise = env->subprog_cnt > 1 || !env->bpf_capable;

Ahh. Thanks for explaining.
We probably need to fix this conservative logic. Can you repro the issue when you comment out above ?

Let's skip the test for now. Just add mark_chain_precision to loop logic, so we don't have to come back to it later when subprogs>1 is fixed.

author maintainer
#11 lore raw

Re: [PATCH bpf-next v7 3/5] bpf: Inline calls to bpf_loop when callback is known

Quoted 10 lines · Alexei Starovoitov
Quoted 7 lines · Eduard Zingerman

/* Mark a register as having a completely unknown (scalar) value. */ static void __mark_reg_unknown(const struct bpf_verifier_env *env,
struct bpf_reg_state *reg)

{
        ...
        reg->precise = env->subprog_cnt > 1 || !env->bpf_capable;
Quoted 3 lines

Ahh. Thanks for explaining.
We probably need to fix this conservative logic. Can you repro the issue when you comment out above ?

If I replace the assignment above with reg->precise = false the verifier does skip the second branch with BPF_REG_4 set to 1.

Quoted 3 lines

Let's skip the test for now. Just add mark_chain_precision to loop logic, so we don't have to come back to it later when subprogs>1 is fixed.

Will provide the updated version tonight, thank you for the suggestions.

Best regards,
Eduard.

author maintainer
#12 lore raw

PATCH v7 4/5 selftests/bpf: BPF test_verifier selftests for bpf_loop inlining

In reply to Eduard Zingerman

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]>
Acked-by Song Liu <[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 -0
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
Signature · 1 line
2.25.1
author maintainer
#13 lore raw

PATCH v7 5/5 selftests/bpf: BPF test_prog selftests for bpf_loop inlining

In reply to Eduard Zingerman

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]>
Acked-by Song Liu <[email protected]>
---
 .../selftests/bpf/prog_tests/bpf_loop.c       |  62 ++++++++++
 tools/testing/selftests/bpf/progs/bpf_loop.c  | 114 ++++++++++++++++++
 2 files changed, 176 insertions(+)
tools/testing/selftests/bpf/prog_tests/bpf_loop.c +62 -0
index 380d7a2072e3..4cd8a25afe68 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");
+
+	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);
 }
tools/testing/selftests/bpf/progs/bpf_loop.c +114 -0

128 lines not on this page · raw message

Signature · 1 line
2.25.1