Skip to contentSkip to conversation

BPF open-coded iterators

PATCH Superseded Andrii Nakryiko 5 participants 35 messages Mar 2, 2023 – Mar 7, 2023

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

v1 of 5 Superseded 12 of 17 applied Latest is v5 →

lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

cover BPF open-coded iterators

Add support for open-coded (aka inline) iterators in BPF world. This is a next evolution of gradually allowing more powerful and less restrictive looping and iteration capabilities to BPF programs.

We set up a framework for implementing all kinds of iterators (e.g., cgroup, task, file, etc, iterators), but this patch set only implements numbers iterator, which is used to implement ergonomic bpf_for() for-like construct (see patch #15). We also add bpf_for_each(), which is a generic foreach-like construct that will work with any kind of open-coded iterator implementation, as long as we stick with bpf_iter_<type>_{new,next,destroy}() naming pattern.

Patches #1 through #12 are various preparatory patches, first eitht of them are from preliminaries patch set ([0]) which haven't landed yet, so I just merged them together to let CI do end-to-end testing of everything properly. Few new patches further adds some necessary functionality in verifier (like fixed-size read-only memory access for int *-returning kfuncs).

The meat of verifier-side logic is in lucky patch #13. Patch #14 implements numbers iterator. I kept them separate to have clean reference for how to integrate new iterator types. And it makes verifier core logic changes abstracted from any particularities of numbers iterator. Patch #15 adds bpf_for(), bpf_for_each(), and bpf_repeat() macros to bpf_misc.h, and also adds yet another pyperf test variant, now with bpf_for() loop. Patch #16 is verification tests, based on numbers iterator (as the only available right now). Patch #17 actually tests runtime behavior of numbers iterator.

Most of the relevant details are in corresponding commit messages or code comments.

[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=725996&state=*

Cc Tejun Heo <[email protected]>

Andrii Nakryiko (17):
bpf: improve stack slot state printing
bpf: improve regsafe() checks for PTR_TO_{MEM,BUF,TP_BUFFER} selftests/bpf: enhance align selftest's expected log matching
bpf: honor env->test_state_freq flag in is_state_visited() selftests/bpf: adjust log_fixup's buffer size for proper truncation
bpf: clean up visit_insn()'s instruction processing
bpf: fix visit_insn()'s detection of BPF_FUNC_timer_set_callback
helper
bpf: ensure that r0 is marked scratched after any function call
bpf: move kfunc_call_arg_meta higher in the file
bpf: mark PTR_TO_MEM as non-null register type
bpf: generalize dynptr_get_spi to be usable for iters
bpf: add support for fixed-size memory pointer returns for kfuncs
bpf: add support for open-coded iterator loops
bpf: implement number iterator
selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros selftests/bpf: add iterators tests
selftests/bpf: add number iterator tests

 include/linux/bpf.h                           |  19 +-
 include/linux/bpf_verifier.h                  |  22 +-
 include/uapi/linux/bpf.h                      |   6 +
 kernel/bpf/bpf_iter.c                         |  71 ++
 kernel/bpf/helpers.c                          |   3 +
 kernel/bpf/verifier.c                         | 851 ++++++++++++++++--
 tools/include/uapi/linux/bpf.h                |   6 +
 .../testing/selftests/bpf/prog_tests/align.c  |  18 +-
 .../bpf/prog_tests/bpf_verif_scale.c          |   6 +
 .../testing/selftests/bpf/prog_tests/iters.c  |  62 ++
 .../selftests/bpf/prog_tests/log_fixup.c      |   2 +-
 .../bpf/prog_tests/uprobe_autoattach.c        |   1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  |  77 ++
 tools/testing/selftests/bpf/progs/iters.c     | 720 +++++++++++++++
 .../selftests/bpf/progs/iters_looping.c       | 163 ++++
 tools/testing/selftests/bpf/progs/iters_num.c | 242 +++++
 .../selftests/bpf/progs/iters_state_safety.c  | 455 ++++++++++
 tools/testing/selftests/bpf/progs/lsm.c       |   4 +-
 tools/testing/selftests/bpf/progs/pyperf.h    |  14 +-
 .../selftests/bpf/progs/pyperf600_iter.c      |   7 +
 .../selftests/bpf/progs/pyperf600_nounroll.c  |   3 -
 21 files changed, 2641 insertions(+), 111 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/iters.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_looping.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_num.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_state_safety.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

PATCH 1/17 bpf: improve stack slot state printing

Improve stack slot state printing to provide more useful and relevant information, especially for dynptrs. While previously we'd see something like:

8: (85) call bpf_ringbuf_reserve_dynptr#198 ; R0_w=scalar() fp-8_w=dddddddd fp-16_w=dddddddd refs=2

Now we'll see way more useful:

8: (85) call bpf_ringbuf_reserve_dynptr#198 ; R0_w=scalar() fp-16_w=dynptr_ringbuf(ref_id=2) refs=2

I experimented with printing the range of slots taken by dynptr, something like:

fp-16..8_w=dynptr_ringbuf(ref_id=2)

But it felt very awkward and pretty useless. So we print the lowest address (most negative offset) only.

The general structure of this code is now also set up for easier extension and will accommodate ITER slots naturally.

---
 kernel/bpf/verifier.c | 75 ++++++++++++++++++++++++++++---------------
 1 file changed, 49 insertions(+), 26 deletions(-)
kernel/bpf/verifier.c +49 -26
index bf580f246a01..60cc8473faa8 100644
@@ -705,6 +705,25 @@ static const char *kernel_type_name(const struct btf* btf, u32 id)
 	return btf_name_by_offset(btf, btf_type_by_id(btf, id)->name_off);
 }
 
+static const char *dynptr_type_str(enum bpf_dynptr_type type)
+{
+	switch (type) {
+	case BPF_DYNPTR_TYPE_LOCAL:
+		return "local";
+	case BPF_DYNPTR_TYPE_RINGBUF:
+		return "ringbuf";
+	case BPF_DYNPTR_TYPE_SKB:
+		return "skb";
+	case BPF_DYNPTR_TYPE_XDP:
+		return "xdp";
+	case BPF_DYNPTR_TYPE_INVALID:
+		return "<invalid>";
+	default:
+		WARN_ONCE(1, "unknown dynptr type %d\n", type);
+		return "<unknown>";
+	}
+}
+
 static void mark_reg_scratched(struct bpf_verifier_env *env, u32 regno)
 {
 	env->scratched_regs |= 1U << regno;
@@ -1176,26 +1195,49 @@ static void print_verifier_state(struct bpf_verifier_env *env,
 		for (j = 0; j < BPF_REG_SIZE; j++) {
 			if (state->stack[i].slot_type[j] != STACK_INVALID)
 				valid = true;
-			types_buf[j] = slot_type_char[
-					state->stack[i].slot_type[j]];
+			types_buf[j] = slot_type_char[state->stack[i].slot_type[j]];
 		}
 		types_buf[BPF_REG_SIZE] = 0;
 		if (!valid)
 			continue;
 		if (!print_all && !stack_slot_scratched(env, i))
 			continue;
-		verbose(env, " fp%d", (-i - 1) * BPF_REG_SIZE);
-		print_liveness(env, state->stack[i].spilled_ptr.live);
-		if (is_spilled_reg(&state->stack[i])) {
+		switch (state->stack[i].slot_type[BPF_REG_SIZE - 1]) {
+		case STACK_SPILL:
 			reg = &state->stack[i].spilled_ptr;
 			t = reg->type;
+
+			verbose(env, " fp%d", (-i - 1) * BPF_REG_SIZE);
+			print_liveness(env, reg->live);
 			verbose(env, "=%s", t == SCALAR_VALUE ? "" : reg_type_str(env, t));
 			if (t == SCALAR_VALUE && reg->precise)
 				verbose(env, "P");
 			if (t == SCALAR_VALUE && tnum_is_const(reg->var_off))
 				verbose(env, "%lld", reg->var_off.value + reg->off);
-		} else {
+			break;
+		case STACK_DYNPTR:
+			i += BPF_DYNPTR_NR_SLOTS - 1;
+			reg = &state->stack[i].spilled_ptr;
+
+			verbose(env, " fp%d", (-i - 1) * BPF_REG_SIZE);
+			print_liveness(env, reg->live);
+			verbose(env, "=dynptr_%s", dynptr_type_str(reg->dynptr.type));
+			if (reg->ref_obj_id)
+				verbose(env, "(ref_id=%d)", reg->ref_obj_id);
+			break;
+		case STACK_MISC:
+		case STACK_ZERO:
+		default:
+			reg = &state->stack[i].spilled_ptr;
+
+			for (j = 0; j < BPF_REG_SIZE; j++)
+				types_buf[j] = slot_type_char[state->stack[i].slot_type[j]];
+			types_buf[BPF_REG_SIZE] = 0;
+
+			verbose(env, " fp%d", (-i - 1) * BPF_REG_SIZE);
+			print_liveness(env, reg->live);
 			verbose(env, "=%s", types_buf);
+			break;
 		}
 	}
 	if (state->acquired_refs && state->refs[0].id) {
@@ -6312,28 +6354,9 @@ static int process_dynptr_func(struct bpf_verifier_env *env, int regno, int insn
 
 		/* Fold modifiers (in this case, MEM_RDONLY) when checking expected type */
 		if (!is_dynptr_type_expected(env, reg, arg_type & ~MEM_RDONLY)) {
-			const char *err_extra = "";
-
-			switch (arg_type & DYNPTR_TYPE_FLAG_MASK) {
-			case DYNPTR_TYPE_LOCAL:
-				err_extra = "local";
-				break;
-			case DYNPTR_TYPE_RINGBUF:
-				err_extra = "ringbuf";
-				break;
-			case DYNPTR_TYPE_SKB:
-				err_extra = "skb ";
-				break;
-			case DYNPTR_TYPE_XDP:
-				err_extra = "xdp ";
-				break;
-			default:
-				err_extra = "<unknown>";
-				break;
-			}
 			verbose(env,
 				"Expected a dynptr of type %s as arg #%d\n",
-				err_extra, regno);
+				dynptr_type_str(arg_to_dynptr_type(arg_type)), regno);
 			return -EINVAL;
 		}
 
Signature · 1 line
2.30.2
author maintainer
#2 lore raw

PATCH 2/17 bpf: improve regsafe() checks for PTR_TO_{MEM,BUF,TP_BUFFER}

In reply to Andrii Nakryiko

Teach regsafe() logic to handle PTR_TO_MEM, PTR_TO_BUF, and PTR_TO_TP_BUFFER similarly to PTR_TO_MAP_{KEY,VALUE}. That is, instead of exact match for var_off and range, use tnum_in() and range_within() checks, allowing more general verified state to subsume more specific current state. This allows to match wider range of valid and safe states, speeding up verification and detecting wider range of equivalent states for upcoming open-coded iteration looping logic.

---
 kernel/bpf/verifier.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +5 -1
index 60cc8473faa8..97f03f9fc711 100644
@@ -14114,13 +14114,17 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		       tnum_in(rold->var_off, rcur->var_off);
 	case PTR_TO_MAP_KEY:
 	case PTR_TO_MAP_VALUE:
+	case PTR_TO_MEM:
+	case PTR_TO_BUF:
+	case PTR_TO_TP_BUFFER:
 		/* If the new min/max/var_off satisfy the old ones and
 		 * everything else matches, we are OK.
 		 */
 		return memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)) == 0 &&
 		       range_within(rold, rcur) &&
 		       tnum_in(rold->var_off, rcur->var_off) &&
-		       check_ids(rold->id, rcur->id, idmap);
+		       check_ids(rold->id, rcur->id, idmap) &&
+		       check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
 	case PTR_TO_PACKET_META:
 	case PTR_TO_PACKET:
 		/* We must have at least as much range as the old ptr
Signature · 1 line
2.30.2
author maintainer
#3 lore raw

PATCH 3/17 selftests/bpf: enhance align selftest's expected log matching

In reply to Andrii Nakryiko

Allow to search for expected register state in all the verifier log output that's related to specified instruction number.

See added comment for an example of possible situation that is happening due to a simple enhancement done in the next patch, which fixes handling of env->test_state_freq flag in state checkpointing logic.

---
 tools/testing/selftests/bpf/prog_tests/align.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/align.c +12 -6
index 4666f88f2bb4..c94fa8d6c4f6 100644
@@ -660,16 +660,22 @@ static int do_test_single(struct bpf_align_test *test)
 			 * func#0 @0
 			 * 0: R1=ctx(off=0,imm=0) R10=fp0
 			 * 0: (b7) r3 = 2                 ; R3_w=2
+			 *
+			 * Sometimes it's actually two lines below, e.g. when
+			 * searching for "6: R3_w=scalar(umax=255,var_off=(0x0; 0xff))":
+			 *   from 4 to 6: R0_w=pkt(off=8,r=8,imm=0) R1=ctx(off=0,imm=0) R2_w=pkt(off=0,r=8,imm=0) R3_w=pkt_end(off=0,imm=0) R10=fp0
+			 *   6: R0_w=pkt(off=8,r=8,imm=0) R1=ctx(off=0,imm=0) R2_w=pkt(off=0,r=8,imm=0) R3_w=pkt_end(off=0,imm=0) R10=fp0
+			 *   6: (71) r3 = *(u8 *)(r2 +0)           ; R2_w=pkt(off=0,r=8,imm=0) R3_w=scalar(umax=255,var_off=(0x0; 0xff))
 			 */
-			if (!strstr(line_ptr, m.match)) {
+			while (!strstr(line_ptr, m.match)) {
 				cur_line = -1;
 				line_ptr = strtok(NULL, "\n");
-				sscanf(line_ptr, "%u: ", &cur_line);
+				sscanf(line_ptr ?: "", "%u: ", &cur_line);
+				if (!line_ptr || cur_line != m.line)
+					break;
 			}
-			if (cur_line != m.line || !line_ptr ||
-			    !strstr(line_ptr, m.match)) {
-				printf("Failed to find match %u: %s\n",
-				       m.line, m.match);
+			if (cur_line != m.line || !line_ptr || !strstr(line_ptr, m.match)) {
+				printf("Failed to find match %u: %s\n", m.line, m.match);
 				ret = 1;
 				printf("%s", bpf_vlog);
 				break;
Signature · 1 line
2.30.2
author maintainer
#4 lore raw

PATCH 4/17 bpf: honor env->test_state_freq flag in is_state_visited()

In reply to Andrii Nakryiko

env->test_state_freq flag can be set by user by passing BPF_F_TEST_STATE_FREQ program flag. This is used in a bunch of selftests to have predictable state checkpoints at every jump and so on.

Currently, bounded loop handling heuristic ignores this flag if number of processed jumps and/or number of processed instructions is below some thresholds, which throws off that reliable state checkpointing.

Honor this flag in all circumstances by disabling heuristic if env->test_state_freq is set.

---
 kernel/bpf/verifier.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +2 -1
index 97f03f9fc711..154f5d251ecb 100644
@@ -14556,7 +14556,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			 * This threshold shouldn't be too high either, since states
 			 * at the end of the loop are likely to be useful in pruning.
 			 */
-			if (env->jmps_processed - env->prev_jmps_processed < 20 &&
+			if (!env->test_state_freq &&
+			    env->jmps_processed - env->prev_jmps_processed < 20 &&
 			    env->insn_processed - env->prev_insn_processed < 100)
 				add_new_state = false;
 			goto miss;
Signature · 1 line
2.30.2
author maintainer
#5 lore raw

PATCH 5/17 selftests/bpf: adjust log_fixup's buffer size for proper truncation

In reply to Andrii Nakryiko

Adjust log_fixup's expected buffer length to fix the test. It's pretty finicky in its length expectation, but it doesn't break often. So just adjust the length to work on current kernel and with follow up iterator changes as well.

---
 tools/testing/selftests/bpf/prog_tests/log_fixup.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
tools/testing/selftests/bpf/prog_tests/log_fixup.c +1 -1
index f4ffdcabf4e4..239e1c5753b0 100644
@@ -141,7 +141,7 @@ void test_log_fixup(void)
 	if (test__start_subtest("bad_core_relo_trunc_partial"))
 		bad_core_relo(300, TRUNC_PARTIAL /* truncate original log a bit */);
 	if (test__start_subtest("bad_core_relo_trunc_full"))
-		bad_core_relo(250, TRUNC_FULL  /* truncate also libbpf's message patch */);
+		bad_core_relo(210, TRUNC_FULL  /* truncate also libbpf's message patch */);
 	if (test__start_subtest("bad_core_relo_subprog"))
 		bad_core_relo_subprog();
 	if (test__start_subtest("missing_map"))
Signature · 1 line
2.30.2
author maintainer
#6 lore raw

PATCH 6/17 bpf: clean up visit_insn()'s instruction processing

In reply to Andrii Nakryiko

Instead of referencing processed instruction repeatedly as insns[t] throughout entire visit_insn() function, take a local insn pointer and work with it in a cleaner way.

It makes enhancing this function further a bit easier as well.

---
 kernel/bpf/verifier.c | 25 ++++++++++++-------------
 1 file changed, 12 insertions(+), 13 deletions(-)
kernel/bpf/verifier.c +12 -13
index 154f5d251ecb..f8055f3d9b47 100644
@@ -13389,44 +13389,43 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,
  */
 static int visit_insn(int t, struct bpf_verifier_env *env)
 {
-	struct bpf_insn *insns = env->prog->insnsi;
+	struct bpf_insn *insns = env->prog->insnsi, *insn = &insns[t];
 	int ret;
 
-	if (bpf_pseudo_func(insns + t))
+	if (bpf_pseudo_func(insn))
 		return visit_func_call_insn(t, insns, env, true);
 
 	/* All non-branch instructions have a single fall-through edge. */
-	if (BPF_CLASS(insns[t].code) != BPF_JMP &&
-	    BPF_CLASS(insns[t].code) != BPF_JMP32)
+	if (BPF_CLASS(insn->code) != BPF_JMP &&
+	    BPF_CLASS(insn->code) != BPF_JMP32)
 		return push_insn(t, t + 1, FALLTHROUGH, env, false);
 
-	switch (BPF_OP(insns[t].code)) {
+	switch (BPF_OP(insn->code)) {
 	case BPF_EXIT:
 		return DONE_EXPLORING;
 
 	case BPF_CALL:
-		if (insns[t].imm == BPF_FUNC_timer_set_callback)
+		if (insn->imm == BPF_FUNC_timer_set_callback)
 			/* Mark this call insn as a prune point to trigger
 			 * is_state_visited() check before call itself is
 			 * processed by __check_func_call(). Otherwise new
 			 * async state will be pushed for further exploration.
 			 */
 			mark_prune_point(env, t);
-		return visit_func_call_insn(t, insns, env,
-					    insns[t].src_reg == BPF_PSEUDO_CALL);
+		return visit_func_call_insn(t, insns, env, insn->src_reg == BPF_PSEUDO_CALL);
 
 	case BPF_JA:
-		if (BPF_SRC(insns[t].code) != BPF_K)
+		if (BPF_SRC(insn->code) != BPF_K)
 			return -EINVAL;
 
 		/* unconditional jump with single edge */
-		ret = push_insn(t, t + insns[t].off + 1, FALLTHROUGH, env,
+		ret = push_insn(t, t + insn->off + 1, FALLTHROUGH, env,
 				true);
 		if (ret)
 			return ret;
 
-		mark_prune_point(env, t + insns[t].off + 1);
-		mark_jmp_point(env, t + insns[t].off + 1);
+		mark_prune_point(env, t + insn->off + 1);
+		mark_jmp_point(env, t + insn->off + 1);
 
 		return ret;
 
@@ -13438,7 +13437,7 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 		if (ret)
 			return ret;
 
-		return push_insn(t, t + insns[t].off + 1, BRANCH, env, true);
+		return push_insn(t, t + insn->off + 1, BRANCH, env, true);
 	}
 }
 
Signature · 1 line
2.30.2
author maintainer
#7 lore raw

PATCH 7/17 bpf: fix visit_insn()'s detection of BPF_FUNC_timer_set_callback helper

In reply to Andrii Nakryiko

It's not correct to assume that any BPF_CALL instruction is a helper call. Fix visit_insn()'s detection of bpf_timer_set_callback() helper by also checking insn->code == 0. For kfuncs insn->code would be set to BPF_PSEUDO_KFUNC_CALL, and for subprog calls it will be BPF_PSEUDO_CALL.

---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
index f8055f3d9b47..666e416dc8a2 100644
@@ -13405,7 +13405,7 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 		return DONE_EXPLORING;
 
 	case BPF_CALL:
-		if (insn->imm == BPF_FUNC_timer_set_callback)
+		if (insn->src_reg == 0 && insn->imm == BPF_FUNC_timer_set_callback)
 			/* Mark this call insn as a prune point to trigger
 			 * is_state_visited() check before call itself is
 			 * processed by __check_func_call(). Otherwise new
Signature · 1 line
2.30.2
author maintainer
#8 lore raw

PATCH 8/17 bpf: ensure that r0 is marked scratched after any function call

In reply to Andrii Nakryiko

r0 is important (unless called function is void-returning, but that's taken care of by print_verifier_state() anyways) in verifier logs. Currently for helpers we seem to print it in verifier log, but for kfuncs we don't.

Instead of figuring out where in the maze of code we accidentally set r0 as scratched for helpers and why we don't do that for kfuncs, just enforce that after any function call r0 is marked as scratched.

Also, perhaps, we should reconsider "scratched" terminology, as it's mightily confusing. "Touched" would seem more appropriate. But I left that for follow ups for now.

---
 kernel/bpf/verifier.c | 2 ++
 1 file changed, 2 insertions(+)
kernel/bpf/verifier.c +2 -0
index 666e416dc8a2..0004c9f3737f 100644
@@ -15001,6 +15001,8 @@ static int do_check(struct bpf_verifier_env *env)
 					err = check_helper_call(env, insn, &env->insn_idx);
 				if (err)
 					return err;
+
+				mark_reg_scratched(env, BPF_REG_0);
 			} else if (opcode == BPF_JA) {
 				if (BPF_SRC(insn->code) != BPF_K ||
 				    insn->imm != 0 ||
Signature · 1 line
2.30.2
author maintainer
#9 lore raw

PATCH 9/17 bpf: move kfunc_call_arg_meta higher in the file

In reply to Andrii Nakryiko

Move struct bpf_kfunc_call_arg_meta higher in the file and put it next to struct bpf_call_arg_meta, so it can be used from more functions.

---
 kernel/bpf/verifier.c | 70 +++++++++++++++++++++----------------------
 1 file changed, 35 insertions(+), 35 deletions(-)
kernel/bpf/verifier.c +35 -35
index 0004c9f3737f..a75d909f4a59 100644
@@ -270,6 +270,41 @@ struct bpf_call_arg_meta {
 	struct btf_field *kptr_field;
 };
 
+struct bpf_kfunc_call_arg_meta {
+	/* In parameters */
+	struct btf *btf;
+	u32 func_id;
+	u32 kfunc_flags;
+	const struct btf_type *func_proto;
+	const char *func_name;
+	/* Out parameters */
+	u32 ref_obj_id;
+	u8 release_regno;
+	bool r0_rdonly;
+	u32 ret_btf_id;
+	u64 r0_size;
+	u32 subprogno;
+	struct {
+		u64 value;
+		bool found;
+	} arg_constant;
+	struct {
+		struct btf *btf;
+		u32 btf_id;
+	} arg_obj_drop;
+	struct {
+		struct btf_field *field;
+	} arg_list_head;
+	struct {
+		struct btf_field *field;
+	} arg_rbtree_root;
+	struct {
+		enum bpf_dynptr_type type;
+		u32 id;
+	} initialized_dynptr;
+	u64 mem_size;
+};
+
 struct btf *btf_vmlinux;
 
 static DEFINE_MUTEX(bpf_verifier_lock);
@@ -8712,41 +8747,6 @@ static void mark_btf_func_reg_size(struct bpf_verifier_env *env, u32 regno,
 	}
 }
 
-struct bpf_kfunc_call_arg_meta {
-	/* In parameters */
-	struct btf *btf;
-	u32 func_id;
-	u32 kfunc_flags;
-	const struct btf_type *func_proto;
-	const char *func_name;
-	/* Out parameters */
-	u32 ref_obj_id;
-	u8 release_regno;
-	bool r0_rdonly;
-	u32 ret_btf_id;
-	u64 r0_size;
-	u32 subprogno;
-	struct {
-		u64 value;
-		bool found;
-	} arg_constant;
-	struct {
-		struct btf *btf;
-		u32 btf_id;
-	} arg_obj_drop;
-	struct {
-		struct btf_field *field;
-	} arg_list_head;
-	struct {
-		struct btf_field *field;
-	} arg_rbtree_root;
-	struct {
-		enum bpf_dynptr_type type;
-		u32 id;
-	} initialized_dynptr;
-	u64 mem_size;
-};
-
 static bool is_kfunc_acquire(struct bpf_kfunc_call_arg_meta *meta)
 {
 	return meta->kfunc_flags & KF_ACQUIRE;
Signature · 1 line
2.30.2
author maintainer
#10 lore raw

PATCH 10/17 bpf: mark PTR_TO_MEM as non-null register type

In reply to Andrii Nakryiko

PTR_TO_MEM register without PTR_MAYBE_NULL is indeed non-null. This is important for BPF verifier to be able to prune guaranteed not to be taken branches. This is always the case with open-coded iterators.

---
 kernel/bpf/verifier.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +2 -1
index a75d909f4a59..4ed53280ce95 100644
@@ -487,7 +487,8 @@ static bool reg_type_not_null(enum bpf_reg_type type)
 		type == PTR_TO_TCP_SOCK ||
 		type == PTR_TO_MAP_VALUE ||
 		type == PTR_TO_MAP_KEY ||
-		type == PTR_TO_SOCK_COMMON;
+		type == PTR_TO_SOCK_COMMON ||
+		type == PTR_TO_MEM;
 }
 
 static bool type_is_ptr_alloc_obj(u32 type)
Signature · 1 line
2.30.2
author maintainer
#11 lore raw

PATCH 11/17 bpf: generalize dynptr_get_spi to be usable for iters

In reply to Andrii Nakryiko

Generalize the logic of fetching special stack slot object state using spi (stack slot index). This will be used by STACK_ITER logic next.

---
 kernel/bpf/verifier.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +12 -6
index 4ed53280ce95..641a36204493 100644
@@ -710,32 +710,38 @@ static bool is_spi_bounds_valid(struct bpf_func_state *state, int spi, int nr_sl
        return spi - nr_slots + 1 >= 0 && spi < allocated_slots;
 }
 
-static int dynptr_get_spi(struct bpf_verifier_env *env, struct bpf_reg_state *reg)
+static int stack_slot_obj_get_spi(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
+			          const char *obj_kind, int nr_slots)
 {
 	int off, spi;
 
 	if (!tnum_is_const(reg->var_off)) {
-		verbose(env, "dynptr has to be at a constant offset\n");
+		verbose(env, "%s has to be at a constant offset\n", obj_kind);
 		return -EINVAL;
 	}
 
 	off = reg->off + reg->var_off.value;
 	if (off % BPF_REG_SIZE) {
-		verbose(env, "cannot pass in dynptr at an offset=%d\n", off);
+		verbose(env, "cannot pass in %s at an offset=%d\n", obj_kind, off);
 		return -EINVAL;
 	}
 
 	spi = __get_spi(off);
-	if (spi < 1) {
-		verbose(env, "cannot pass in dynptr at an offset=%d\n", off);
+	if (spi + 1 < nr_slots) {
+		verbose(env, "cannot pass in %s at an offset=%d\n", obj_kind, off);
 		return -EINVAL;
 	}
 
-	if (!is_spi_bounds_valid(func(env, reg), spi, BPF_DYNPTR_NR_SLOTS))
+	if (!is_spi_bounds_valid(func(env, reg), spi, nr_slots))
 		return -ERANGE;
 	return spi;
 }
 
+static int dynptr_get_spi(struct bpf_verifier_env *env, struct bpf_reg_state *reg)
+{
+	return stack_slot_obj_get_spi(env, reg, "dynptr", BPF_DYNPTR_NR_SLOTS);
+}
+
 static const char *kernel_type_name(const struct btf* btf, u32 id)
 {
 	return btf_name_by_offset(btf, btf_type_by_id(btf, id)->name_off);
Signature · 1 line
2.30.2
author maintainer
#12 lore raw

PATCH 12/17 bpf: add support for fixed-size memory pointer returns for kfuncs

In reply to Andrii Nakryiko

Support direct fixed-size (and for now, read-only) memory access when kfunc's return type is a pointer to non-struct type. Calculate type size and let BPF program access that many bytes directly. This is crucial for numbers iterator.

---
 kernel/bpf/verifier.c | 8 ++++++++
 1 file changed, 8 insertions(+)
kernel/bpf/verifier.c +8 -0
index 641a36204493..0ff9dd9170ef 100644
@@ -10241,6 +10241,14 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 				return -EFAULT;
 			}
 		} else if (!__btf_type_is_struct(ptr_type)) {
+			if (!meta.r0_size) {
+				__u32 sz;
+
+				if (!IS_ERR(btf_resolve_size(desc_btf, ptr_type, &sz))) {
+					meta.r0_size = sz;
+					meta.r0_rdonly = true;
+				}
+			}
 			if (!meta.r0_size) {
 				ptr_type_name = btf_name_by_offset(desc_btf,
 								   ptr_type->name_off);
Signature · 1 line
2.30.2
author maintainer
#13 lore raw

PATCH 13/17 bpf: add support for open-coded iterator loops

In reply to Andrii Nakryiko

Teach verifier about the concept of open-coded (or inline) iterators.

This patch adds generic iterator loop verification logic, new STACK_ITER stack slot type to contain iterator state, and necessary kfunc plumbing for iterator's constructor, destructor and next "methods". Next patch implements first specific version of iterator (number iterator for implementing for loop). Such split allows to have more focused commits for verifier logic and separate commit that we could point later to what it takes to add new kind of iterator.

First, we add new fixed-size opaque struct bpf_iter (24-byte long) to contain runtime state of any possible iterator. struct bpf_iter state is supposed to be on BPF program's stack, so there will be no way to change its size later on. 24 bytes are chosen as a compromise between using too much stack and providing too little pre-allocated space for future iterator types. Numbers iterator in the next patch needs only 8, and thus fits perfectly and won't require any runtime memory allocation. But if some other iterator implementation would require more than 24 bytes to represent iterator runtime state, we'd have to perform runtime allocation for extra state, which leads to performance hit and general unreliability (especially in restricted environments of NMI or IRQ). 3 words were chosen to at least accommodate 1 pointer to "collection" (e.g., bpf_map), 1 pointer to "current/next element", and still leaving 1 word for extra parameters and flags. As such it should hopefully make a lot of other iterator implementations much simpler and reliable.

The way BPF verifier logic is implemented, there are no artificial restrictions on a number of active iterators, it should work correctly using multiple at the same time. This also means you can have multiple nested iteration loops. struct bpf_iter reference can be safely passed to subprograms as well.

General flow is easiest to demonstrate with a simple example using number iterator implemented in next patch. Here's the simplest possible loop:

struct bpf_iter it;
int *v;

  bpf_iter_num_new(&it, 2, 5);
  while ((v = bpf_iter_num_next(&it))) {
      bpf_printk("X = %d", *v);
  }
  bpf_iter_num_destroy(&it);

Above snippet should output "X = 2", "X = 3", "X = 4". Note that 5 is exclusive and is not returned.

In the above example, we see a trio of function:
- constructor, bpf_iter_num_new(), which initializes iterator state (struct bpf_iter it) on the stack. If any on the input arguments are invalid, constructor should make sure to still initialize it such that subsequent bpf_iter_num_next() calls will return NULL. I.e., on error, return error and construct empty iterator.
- next method, bpf_iter_num_next(), which accepts pointer to iterator state and produces an element. Next method should always return a pointer. The contract between BPF verifier is that next method will always eventually return NULL when elements are exhausted. One NULL is returned, subsequent next calls should keep returning NULL. In the case of numbers iterator, bpf_iter_num_next() returns a pointer to int (where current integer value itself is stored inside iterator state), which can be dereferenced after according NULL check.
- once done with the iterator, it's mandated that user cleans up its state with destructor, bpf_iter_num_destroy() in this case. Destructor frees up any resources and marks stack space used by struct bpf_iter as usable for something else.

Any other iterator implementation will have to implement at least these three methods. It is enforced that for any given type of iterator only applicable constructor/destructor/next are callable. I.e., verifier ensures you can't pass number iterator into, say, cgroup iterator's next method.

It is important to keep naming consistent to be able to create generic helpers/macros to help with bpf_iter usability. E.g., one of the follow up patches adds generic bpf_for_each() macro to bpf_misc.h in selftests, which allows to utilize iterator "trio" nicely without having to code the above somewhat tedious loop explicitly every time.

**So it is expected that new iterator implementations will follow bpf_iter_<kind>_{new,next,destroy}() naming.**

At the implementation level, iterator state tracking for verification purposes is very similar to dynptr. We add STACK_ITER stack slot type, reserve 3 slots, keep track of necessary extra state in the "main" slot. Other slots are marked as STACK_ITER, but having invalid iterator type. This seems simpler than having a separate "is_first_slot" flag. We should consider reworking STACK_DYNPTR to follow similar approach.

Another big distinction is that STACK_ITER is *always refcounted*, which simplifies implementation a bit without sacrificing usability. So no need for extra "iter_id", no need to anticipate reuse of STACK_ITER slots for new constructors, etc. Keeping it simpler.

As far as verification logic, there are two extensive comments, in process_iter_next_call() and iter_active_depths_differ(), please refer to them for details.

But from 10,000-foot point of view, next methods are the points of forking, which are conceptually similar to what verifier is doing when validating conditional jump. We branch out at call bpf_iter_<type>_next instruction and simulate two situations: NULL (iteration is done) and non-NULL (new element returned). NULL is simulated first and is supposed to reach exit without looping. After that non-NULL case is validated and it either reaches exit (for trivial examples with no real loop), or reaches another call bpf_iter_<type>_next instruction with the state equivalent to already (partially) validated. State equivalency at that point means we technically are going to be looping forever without "breaking out" out of established "state envelope" (i.e., subsequent iterations don't add any new knowledge or constraints to verifier state, so running 1, 2, 10, or a million doesn't matter). But taking into the account the contract that iterator next method *has to* return NULL eventually, we can conclude that loop body is safe. Given we validated logic outside of the loop (NULL case), and concluded that loop body is safe, though potentially looping many times, verifier can claim safety of the overall program logic.

The rest of the patch is necessary plumbing for state tracking, marking, validation, and necessary kfunc infrastructure to allow implementing iterator constructor, destructor, and next methods.

---
 include/linux/bpf.h            |   7 +
 include/linux/bpf_verifier.h   |  22 +-
 include/uapi/linux/bpf.h       |   6 +
 kernel/bpf/verifier.c          | 621 ++++++++++++++++++++++++++++++++-
 tools/include/uapi/linux/bpf.h |   6 +
 5 files changed, 653 insertions(+), 9 deletions(-)
include/linux/bpf.h +7 -0
index 23ec684e660d..a968282ba324 100644
@@ -620,6 +620,8 @@ enum bpf_type_flag {
 #define DYNPTR_TYPE_FLAG_MASK	(DYNPTR_TYPE_LOCAL | DYNPTR_TYPE_RINGBUF | DYNPTR_TYPE_SKB \
 				 | DYNPTR_TYPE_XDP)
 
+#define ITER_TYPE_FLAG_MASK	(0)
+
 /* Max number of base types. */
 #define BPF_BASE_TYPE_LIMIT	(1UL << BPF_BASE_TYPE_BITS)
 
@@ -663,6 +665,7 @@ enum bpf_arg_type {
 	ARG_PTR_TO_TIMER,	/* pointer to bpf_timer */
 	ARG_PTR_TO_KPTR,	/* pointer to referenced kptr */
 	ARG_PTR_TO_DYNPTR,      /* pointer to bpf_dynptr. See bpf_type_flag for dynptr type */
+	ARG_PTR_TO_ITER,	/* pointer to bpf_iter. See bpf_type_flag for iter type */
 	__BPF_ARG_TYPE_MAX,
 
 	/* Extended arg_types. */
@@ -1162,6 +1165,10 @@ enum bpf_dynptr_type {
 int bpf_dynptr_check_size(u32 size);
 u32 bpf_dynptr_get_size(const struct bpf_dynptr_kern *ptr);
 
+enum bpf_iter_type {
+	BPF_ITER_TYPE_INVALID,
+};
+
 #ifdef CONFIG_BPF_JIT
 int bpf_trampoline_link_prog(struct bpf_tramp_link *link, struct bpf_trampoline *tr);
 int bpf_trampoline_unlink_prog(struct bpf_tramp_link *link, struct bpf_trampoline *tr);
include/linux/bpf_verifier.h +21 -1
index b26ff2a8f63b..493a4bb239fe 100644
@@ -59,6 +59,12 @@ struct bpf_active_lock {
 	u32 id;
 };
 
+enum bpf_iter_state {
+	BPF_ITER_STATE_INVALID, /* for non-first slot */
+	BPF_ITER_STATE_ACTIVE,
+	BPF_ITER_STATE_DRAINED,
+};
+
 struct bpf_reg_state {
 	/* Ordering of fields matters.  See states_equal() */
 	enum bpf_reg_type type;
@@ -103,6 +109,13 @@ struct bpf_reg_state {
 			bool first_slot;
 		} dynptr;
 
+		/* For bpf_iter stack slots */
+		struct {
+			enum bpf_iter_type type;
+			enum bpf_iter_state state;
+			int depth;
+		} iter;
+
 		/* Max size from any of the above. */
 		struct {
 			unsigned long raw1;
@@ -141,6 +154,8 @@ struct bpf_reg_state {
 	 * same reference to the socket, to determine proper reference freeing.
 	 * For stack slots that are dynptrs, this is used to track references to
 	 * the dynptr to determine proper reference freeing.
+	 * Similarly to dynptrs, we use ID to track "belonging" of a reference
+	 * to a specific instance of bpf_iter.
 	 */
 	u32 id;
 	/* PTR_TO_SOCKET and PTR_TO_TCP_SOCK could be a ptr returned
@@ -211,11 +226,16 @@ enum bpf_stack_slot_type {
 	 * is stored in bpf_stack_state->spilled_ptr.dynptr.type
 	 */
 	STACK_DYNPTR,
+	STACK_ITER,
 };
 
 #define BPF_REG_SIZE 8	/* size of eBPF register in bytes */
+
 #define BPF_DYNPTR_SIZE		sizeof(struct bpf_dynptr_kern)
-#define BPF_DYNPTR_NR_SLOTS		(BPF_DYNPTR_SIZE / BPF_REG_SIZE)
+#define BPF_DYNPTR_NR_SLOTS	(BPF_DYNPTR_SIZE / BPF_REG_SIZE)
+
+#define BPF_ITER_SIZE		sizeof(struct bpf_iter)
+#define BPF_ITER_NR_SLOTS	(BPF_ITER_SIZE / BPF_REG_SIZE)
 
 struct bpf_stack_state {
 	struct bpf_reg_state spilled_ptr;
include/uapi/linux/bpf.h +6 -0
index c9699304aed2..c4b506193365 100644
@@ -6927,6 +6927,12 @@ struct bpf_dynptr {
 	__u64 :64;
 } __attribute__((aligned(8)));
 
+struct bpf_iter {
+	__u64 :64;
+	__u64 :64;
+	__u64 :64;
+} __attribute__((aligned(8)));
+
 struct bpf_list_head {
 	__u64 :64;
 	__u64 :64;
kernel/bpf/verifier.c +613 -8

807 lines not on this page · raw message

tools/include/uapi/linux/bpf.h +6 -0
index c9699304aed2..c4b506193365 100644
@@ -6927,6 +6927,12 @@ struct bpf_dynptr {
 	__u64 :64;
 } __attribute__((aligned(8)));
 
+struct bpf_iter {
+	__u64 :64;
+	__u64 :64;
+	__u64 :64;
+} __attribute__((aligned(8)));
+
 struct bpf_list_head {
 	__u64 :64;
 	__u64 :64;
Signature · 1 line
2.30.2
#14 lore raw

Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops

Quoted 10 lines · Andrii Nakryiko

Teach verifier about the concept of open-coded (or inline) iterators.

This patch adds generic iterator loop verification logic, new STACK_ITER stack slot type to contain iterator state, and necessary kfunc plumbing for iterator's constructor, destructor and next "methods". Next patch implements first specific version of iterator (number iterator for implementing for loop). Such split allows to have more focused commits for verifier logic and separate commit that we could point later to what it takes to add new kind of iterator.

Quoted 2 lines

First, we add new fixed-size opaque struct bpf_iter (24-byte long) to contain runtime state of any possible iterator. struct bpf_iter state is

Looking at the verifier changes it seems that it should be possible to support any sized iterator and we don't have to fit all of them in 24-bytes. The same bpf_iter_<kind>_{new,next,destroy}() naming convention can apply to types and we can have 8-byte struct bpf_iter_num
The bpf_for() macros would work with bpf_iter_<kind> too.
iirc that was your plan earlier (to have different structs).
What prompted you to change that plan?

Quoted 5 lines

Any other iterator implementation will have to implement at least these three methods. It is enforced that for any given type of iterator only applicable constructor/destructor/next are callable. I.e., verifier ensures you can't pass number iterator into, say, cgroup iterator's next method.

is_iter_type_compatible() does that, right?

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+
+static int mark_stack_slots_iter(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
+				 enum bpf_arg_type arg_type, int insn_idx)
+{
+	struct bpf_func_state *state = func(env, reg);

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1180

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+	enum bpf_iter_type type;
+	int spi, i, j, id;
+
+	spi = iter_get_spi(env, reg);
+	if (spi < 0)
+		return spi;
+
+	type = arg_to_iter_type(arg_type);
+	if (type == BPF_ITER_TYPE_INVALID)
+		return -EINVAL;

Do we need destroy_if_dynptr_stack_slot() equivalent here?

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+	id = acquire_reference_state(env, insn_idx);
+	if (id < 0)
+		return id;
+
+	for (i = 0; i < BPF_ITER_NR_SLOTS; i++) {
+		struct bpf_stack_state *slot = &state->stack[spi - i];
+		struct bpf_reg_state *st = &slot->spilled_ptr;
+
+		__mark_reg_known_zero(st);
+		st->type = PTR_TO_STACK; /* we don't have dedicated reg type */

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1201

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+		st->live |= REG_LIVE_WRITTEN;
+		st->ref_obj_id = i == 0 ? id : 0;
+		st->iter.type = i == 0 ? type : BPF_ITER_TYPE_INVALID;
+		st->iter.state = BPF_ITER_STATE_ACTIVE;
+		st->iter.depth = 0;
+
+		for (j = 0; j < BPF_REG_SIZE; j++)
+			slot->slot_type[j] = STACK_ITER;
+
+		mark_stack_slot_scratched(env, spi - i);

dynptr needs similar mark_stack_slot_scratched() fix, right?

Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+	}
+
+	return 0;
+}

...

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

Quoted 10 lines
kernel/bpf/verifier.c +2 -2
@@ -3691,8 +3928,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
 
 		/* regular write of data into stack destroys any spilled ptr */
 		state->stack[spi].spilled_ptr.type = NOT_INIT;
-		/* Mark slots as STACK_MISC if they belonged to spilled ptr. */
-		if (is_spilled_reg(&state->stack[spi]))
+		/* Mark slots as STACK_MISC if they belonged to spilled ptr/dynptr/iter. */
+		if (is_stack_slot_special(&state->stack[spi]))
 			for (i = 0; i < BPF_REG_SIZE; i++)
 				scrub_spilled_slot(&state->stack[spi].slot_type[i]);

It fixes something for dynptr, right?

Quoted 29 lines
kernel/bpf/verifier.c +29 -0
+static int process_iter_next_call(struct bpf_verifier_env *env, int insn_idx,
+				  struct bpf_kfunc_call_arg_meta *meta)
+{
+	struct bpf_verifier_state *cur_st = env->cur_state, *queued_st;
+	struct bpf_func_state *cur_fr = cur_st->frame[cur_st->curframe], *queued_fr;
+	struct bpf_reg_state *cur_iter, *queued_iter;
+	int iter_frameno = meta->iter.frameno;
+	int iter_spi = meta->iter.spi;
+
+	BTF_TYPE_EMIT(struct bpf_iter);
+
+	cur_iter = &env->cur_state->frame[iter_frameno]->stack[iter_spi].spilled_ptr;
+
+	if (cur_iter->iter.state != BPF_ITER_STATE_ACTIVE &&
+	    cur_iter->iter.state != BPF_ITER_STATE_DRAINED) {
+		verbose(env, "verifier internal error: unexpected iterator state %d (%s)\n",
+			cur_iter->iter.state, iter_state_str(cur_iter->iter.state));
+		return -EFAULT;
+	}
+
+	if (cur_iter->iter.state == BPF_ITER_STATE_ACTIVE) {
+		/* branch out active iter state */
+		queued_st = push_stack(env, insn_idx + 1, insn_idx, false);
+		if (!queued_st)
+			return -ENOMEM;
+
+		queued_iter = &queued_st->frame[iter_frameno]->stack[iter_spi].spilled_ptr;
+		queued_iter->iter.state = BPF_ITER_STATE_ACTIVE;
+		queued_iter->iter.depth++;

kernel/bpf/verifier.c static int process_dynptr_func(struct bpf_verifier_env *env, int regno, int insn · line 6804

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+
+		queued_fr = queued_st->frame[queued_st->curframe];
+		mark_ptr_not_null_reg(&queued_fr->regs[BPF_REG_0]);
+	}
+
+	/* switch to DRAINED state, but keep the depth unchanged */
+	/* mark current iter state as drained and assume returned NULL */
+	cur_iter->iter.state = BPF_ITER_STATE_DRAINED;
+	__mark_reg_known_zero(&cur_fr->regs[BPF_REG_0]);
+	cur_fr->regs[BPF_REG_0].type = SCALAR_VALUE;

__mark_reg_const_zero() instead?

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+
+	return 0;
+}

...

Quoted 18 lines
kernel/bpf/verifier.c +18 -0
+static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx, int *reg_idx)
+{
+	struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
+	const struct btf_param *args;
+	const struct btf_type *t;
+	const struct btf *btf;
+	int nargs, i;
+
+	if (!bpf_pseudo_kfunc_call(insn))
+		return false;
+	if (!is_iter_next_kfunc(insn->imm))
+		return false;
+
+	btf = find_kfunc_desc_btf(env, insn->off);
+	if (IS_ERR(btf))
+		return false;
+
+	t = btf_type_by_id(btf, insn->imm);	/* FUNC */

kernel/bpf/verifier.c static bool states_maybe_looping(struct bpf_verifier_state *old, · line 14987

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+	t = btf_type_by_id(btf, t->type);	/* FUNC_PROTO */
+
+	args = btf_params(t);
+	nargs = btf_vlen(t);
+	for (i = 0; i < nargs; i++) {
+		if (is_kfunc_arg_iter(btf, &args[i])) {
+			*reg_idx = BPF_REG_1 + i;
+			return true;
+		}
+	}

This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?

Quoted 32 lines
kernel/bpf/verifier.c +32 -0
+
+	return false;
+}
+
+/* is_state_visited() handles iter_next() (see process_iter_next_call() for
+ * terminology) calls specially: as opposed to bounded BPF loops, it *expects*
+ * state matching, which otherwise looks like an infinite loop. So while
+ * iter_next() calls are taken care of, we still need to be careful and
+ * prevent erroneous and too eager declaration of "ininite loop", when
+ * iterators are involved.
+ *
+ * Here's a situation in pseudo-BPF assembly form:
+ *
+ *   0: again:                          ; set up iter_next() call args
+ *   1:   r1 = &it                      ; <CHECKPOINT HERE>
+ *   2:   call bpf_iter_num_next        ; this is iter_next() call
+ *   3:   if r0 == 0 goto done
+ *   4:   ... something useful here ...
+ *   5:   goto again                    ; another iteration
+ *   6: done:
+ *   7:   r1 = &it
+ *   8:   call bpf_iter_num_destroy     ; clean up iter state
+ *   9:   exit
+ *
+ * This is a typical loop. Let's assume that we have a prune point at 1:,
+ * before we get to `call bpf_iter_num_next` (e.g., because of that `goto
+ * again`, assuming other heuristics don't get in a way).
+ *
+ * When we first time come to 1:, let's say we have some state X. We proceed
+ * to 2:, fork states, enqueue ACTIVE, validate NULL case successfully, exit.
+ * Now we come back to validate that forked ACTIVE state. We proceed through
+ * 3-5, come to goto, jump to 1:. Let's assume our state didn't change, so we

kernel/bpf/verifier.c static bool states_maybe_looping(struct bpf_verifier_state *old, · line 15029

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+ * are converging. But the problem is that we don't know that yet, as this
+ * convergence has to happen at iter_next() call site only. So if nothing is
+ * done, at 1: verifier will use bounded loop logic and declare infinite
+ * looping (and would be *technically* correct, if not for iterator "eventual
+ * sticky NULL" contract, see process_iter_next_call()). But we don't want
+ * that. So what we do in process_iter_next_call() when we go on another
+ * ACTIVE iteration, we bump slot->iter.depth, to mark that it's a different
+ * iteration. So when we detect soon-to-be-declared infinite loop, we also
+ * check if any of *ACTIVE* iterator state's depth differs. If yes, we pretend
+ * we are not looping and wait for next iter_next() call.

'depth' part of bpf_reg_state will be checked for equality in regsafe(), right? Everytime we branch out in process_iter_next_call() there is depth++
So how come we're able to converge with:
+ if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+ if (states_equal(env, &sl->state, cur)) {
That's because states_equal() is done right before doing process_iter_next_call(), right?

So depth counts the number of times bpf_iter*_next() was processed. In other words it's a number of ways the body of the loop can be walked?

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+			if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+				if (states_equal(env, &sl->state, cur)) {
+					struct bpf_func_state *cur_frame;
+					struct bpf_reg_state *iter_state, *iter_reg;
+					int spi;
+
+					/* current state is valid due to states_equal(),
+					 * so we can assume valid iter state, no need for extra
+					 * (re-)validations
+					 */

kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15154

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+					cur_frame = cur->frame[cur->curframe];
+					iter_reg = &cur_frame->regs[iter_arg_reg_idx];
+					spi = iter_get_spi(env, iter_reg);
+					if (spi < 0)
+						return spi;
+					iter_state = &func(env, iter_reg)->stack[spi].spilled_ptr;
+					if (iter_state->iter.state == BPF_ITER_STATE_ACTIVE)
+						goto hit;
+				}
+				goto skip_inf_loop_check;

This goto is "optional", right?
Meaning that if we remove it the states_maybe_looping() + states_equal() won't match anyway. The goto avoids wasting cycles.

kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15157

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+			}
+			/* attempt to detect infinite loop to avoid unnecessary doomed work */
+			if (states_maybe_looping(&sl->state, cur) &&

Maybe cleaner is to remove above 'goto' and do '} else if (states_maybe_looping' here ?

Quoted 5 lines
kernel/bpf/verifier.c +2 -0
+			    states_equal(env, &sl->state, cur) &&
+			    !iter_active_depths_differ(&sl->state, cur)) {
 				verbose_linfo(env, insn_idx, "; ");
 				verbose(env, "infinite loop detected at insn %d\n", insn_idx);
 				return -EINVAL;
#15 lore raw

Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops

Quoted 15 lines · Alexei Starovoitov
Quoted 10 lines · Andrii Nakryiko

Teach verifier about the concept of open-coded (or inline) iterators.

This patch adds generic iterator loop verification logic, new STACK_ITER stack slot type to contain iterator state, and necessary kfunc plumbing for iterator's constructor, destructor and next "methods". Next patch implements first specific version of iterator (number iterator for implementing for loop). Such split allows to have more focused commits for verifier logic and separate commit that we could point later to what it takes to add new kind of iterator.

Quoted 2 lines

First, we add new fixed-size opaque struct bpf_iter (24-byte long) to contain runtime state of any possible iterator. struct bpf_iter state is

Quoted 7 lines

Looking at the verifier changes it seems that it should be possible to support any sized iterator and we don't have to fit all of them in 24-bytes. The same bpf_iter_<kind>_{new,next,destroy}() naming convention can apply to types and we can have 8-byte struct bpf_iter_num
The bpf_for() macros would work with bpf_iter_<kind> too.
iirc that was your plan earlier (to have different structs).
What prompted you to change that plan?

Not really, single user-facing struct bpf_iter was what I was going for from the very beginning, similar to single struct bpf_dynptr. But I guess they are a bit different in that there are many generic operations applicable across different types of dynptr (bpf_dynptr_read, write, data, slice, etc), so it makes sense to abstract it behind single type.

Here, with iterators, besides something like "is iterator exhausted" (not that I'm planning to add something like that), there isn't much generic to be shared, so yeah, we can switch to one public UAPI struct per each type of iterator and then those can be tailored to each particular type. This will automatically work better for kfuncs as new/next/destroy trios will have the same struct bpf_iter_<type> * and it won't be possible to accidentally pass wrong bpf_iter_<type> to wrong new/next/destroy method.

Quoted 8 lines
Quoted 6 lines

Any other iterator implementation will have to implement at least these three methods. It is enforced that for any given type of iterator only applicable constructor/destructor/next are callable. I.e., verifier ensures you can't pass number iterator into, say, cgroup iterator's next method.

is_iter_type_compatible() does that, right?

yep. Currently it also anticipates generic iterator functions, but as I mentioned above, I don't think we'll have any common methods anyways.

Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +9 -0
+
+static int mark_stack_slots_iter(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
+                              enum bpf_arg_type arg_type, int insn_idx)
+{
+     struct bpf_func_state *state = func(env, reg);
+     enum bpf_iter_type type;
+     int spi, i, j, id;
+
+     spi = iter_get_spi(env, reg);
Quoted 8 lines

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1180

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+     if (spi < 0)
+             return spi;
+
+     type = arg_to_iter_type(arg_type);
+     if (type == BPF_ITER_TYPE_INVALID)
+             return -EINVAL;

Do we need destroy_if_dynptr_stack_slot() equivalent here?

no, because bpf_iter is always ref-counted, so we'll always have explicit unmark_stack_slots_iter() call, which will reset slot types

destroy_if_dynptr_stack_slot() was added because LOCAL dynptr doesn't require explicit destruction. I mentioned this difference (simplification for bpf_iter case) somewhere in the commit message.

Quoted 15 lines
Quoted 15 lines
kernel/bpf/verifier.c +14 -0
+     id = acquire_reference_state(env, insn_idx);
+     if (id < 0)
+             return id;
+
+     for (i = 0; i < BPF_ITER_NR_SLOTS; i++) {
+             struct bpf_stack_state *slot = &state->stack[spi - i];
+             struct bpf_reg_state *st = &slot->spilled_ptr;
+
+             __mark_reg_known_zero(st);
+             st->type = PTR_TO_STACK; /* we don't have dedicated reg type */
+             st->live |= REG_LIVE_WRITTEN;
+             st->ref_obj_id = i == 0 ? id : 0;
+             st->iter.type = i == 0 ? type : BPF_ITER_TYPE_INVALID;
+             st->iter.state = BPF_ITER_STATE_ACTIVE;
Quoted 8 lines

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1201

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+             st->iter.depth = 0;
+
+             for (j = 0; j < BPF_REG_SIZE; j++)
+                     slot->slot_type[j] = STACK_ITER;
+
+             mark_stack_slot_scratched(env, spi - i);

dynptr needs similar mark_stack_slot_scratched() fix, right?

probably yes. destroy_if_dynptr_stack_slot() is scratching slots, but we don't call that on OBJ_RELEASE (in unmark_stack_slots_dynptr), so yeah, we should add this for dynptrs as well

Quoted 10 lines
Quoted 5 lines
kernel/bpf/verifier.c +4 -0
+     }
+
+     return 0;
+}

...

Quoted 2 lines
(quoted diff) +0 -0
@@ -3691,8 +3928,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
 
Quoted 10 lines

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

Quoted 8 lines
kernel/bpf/verifier.c +2 -2
              /* regular write of data into stack destroys any spilled ptr */
              state->stack[spi].spilled_ptr.type = NOT_INIT;
-             /* Mark slots as STACK_MISC if they belonged to spilled ptr. */
-             if (is_spilled_reg(&state->stack[spi]))
+             /* Mark slots as STACK_MISC if they belonged to spilled ptr/dynptr/iter. */
+             if (is_stack_slot_special(&state->stack[spi]))
                      for (i = 0; i < BPF_REG_SIZE; i++)
                              scrub_spilled_slot(&state->stack[spi].slot_type[i]);

It fixes something for dynptr, right?

It's convoluted, I think it might not have a visible effect. This is the situation of partial (e.g., single byte) overwrite of STACK_DYNPTR/STACK_ITER, and without this change we'll leave some slot_types as STACK_MISC, while others as STACK_DYNPTP/STACK_ITER. This is unexpected state, but I think existing code always checks that for STACK_DYNPTR's all 8 slots are STACK_DYNPTR.

So I think it's a good clean up, but no consequences for dynptr correctness. And for STACK_ITER I don't have to worry about such mix, if any of the slot_type[i] is STACK_ITER, then it's a correct iterator.

Quoted 34 lines
Quoted 34 lines
kernel/bpf/verifier.c +33 -0
+static int process_iter_next_call(struct bpf_verifier_env *env, int insn_idx,
+                               struct bpf_kfunc_call_arg_meta *meta)
+{
+     struct bpf_verifier_state *cur_st = env->cur_state, *queued_st;
+     struct bpf_func_state *cur_fr = cur_st->frame[cur_st->curframe], *queued_fr;
+     struct bpf_reg_state *cur_iter, *queued_iter;
+     int iter_frameno = meta->iter.frameno;
+     int iter_spi = meta->iter.spi;
+
+     BTF_TYPE_EMIT(struct bpf_iter);
+
+     cur_iter = &env->cur_state->frame[iter_frameno]->stack[iter_spi].spilled_ptr;
+
+     if (cur_iter->iter.state != BPF_ITER_STATE_ACTIVE &&
+         cur_iter->iter.state != BPF_ITER_STATE_DRAINED) {
+             verbose(env, "verifier internal error: unexpected iterator state %d (%s)\n",
+                     cur_iter->iter.state, iter_state_str(cur_iter->iter.state));
+             return -EFAULT;
+     }
+
+     if (cur_iter->iter.state == BPF_ITER_STATE_ACTIVE) {
+             /* branch out active iter state */
+             queued_st = push_stack(env, insn_idx + 1, insn_idx, false);
+             if (!queued_st)
+                     return -ENOMEM;
+
+             queued_iter = &queued_st->frame[iter_frameno]->stack[iter_spi].spilled_ptr;
+             queued_iter->iter.state = BPF_ITER_STATE_ACTIVE;
+             queued_iter->iter.depth++;
+
+             queued_fr = queued_st->frame[queued_st->curframe];
+             mark_ptr_not_null_reg(&queued_fr->regs[BPF_REG_0]);
+     }
Quoted 8 lines

kernel/bpf/verifier.c static int process_dynptr_func(struct bpf_verifier_env *env, int regno, int insn · line 6804

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+
+     /* switch to DRAINED state, but keep the depth unchanged */
+     /* mark current iter state as drained and assume returned NULL */
+     cur_iter->iter.state = BPF_ITER_STATE_DRAINED;
+     __mark_reg_known_zero(&cur_fr->regs[BPF_REG_0]);
+     cur_fr->regs[BPF_REG_0].type = SCALAR_VALUE;

__mark_reg_const_zero() instead?

sure, didn't know about it

Quoted 30 lines
Quoted 4 lines
kernel/bpf/verifier.c +3 -0
+
+     return 0;
+}

...

Quoted 25 lines
kernel/bpf/verifier.c +25 -0
+static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx, int *reg_idx)
+{
+     struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
+     const struct btf_param *args;
+     const struct btf_type *t;
+     const struct btf *btf;
+     int nargs, i;
+
+     if (!bpf_pseudo_kfunc_call(insn))
+             return false;
+     if (!is_iter_next_kfunc(insn->imm))
+             return false;
+
+     btf = find_kfunc_desc_btf(env, insn->off);
+     if (IS_ERR(btf))
+             return false;
+
+     t = btf_type_by_id(btf, insn->imm);     /* FUNC */
+     t = btf_type_by_id(btf, t->type);       /* FUNC_PROTO */
+
+     args = btf_params(t);
+     nargs = btf_vlen(t);
+     for (i = 0; i < nargs; i++) {
+             if (is_kfunc_arg_iter(btf, &args[i])) {
+                     *reg_idx = BPF_REG_1 + i;
Quoted 8 lines

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1260

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+                     return true;
+             }
+     }

This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?

Yeah, a bit of generality. For a long time I had an assumption hardcoded about first argument being struct bpf_iter *, but that felt unclean, so I generalized that before submission.

But I can't think why we wouldn't just dictate (and enforce) that struct bpf_iter * is first. It makes sense, it's clean, and we lose nothing. This is another thing that differs between dynptr and iter, for dynptr such restriction wouldn't make sense.

Where would be a good place to enforce this for iter kfuncs?

Quoted 37 lines
Quoted 37 lines
kernel/bpf/verifier.c +36 -0
+
+     return false;
+}
+
+/* is_state_visited() handles iter_next() (see process_iter_next_call() for
+ * terminology) calls specially: as opposed to bounded BPF loops, it *expects*
+ * state matching, which otherwise looks like an infinite loop. So while
+ * iter_next() calls are taken care of, we still need to be careful and
+ * prevent erroneous and too eager declaration of "ininite loop", when
+ * iterators are involved.
+ *
+ * Here's a situation in pseudo-BPF assembly form:
+ *
+ *   0: again:                          ; set up iter_next() call args
+ *   1:   r1 = &it                      ; <CHECKPOINT HERE>
+ *   2:   call bpf_iter_num_next        ; this is iter_next() call
+ *   3:   if r0 == 0 goto done
+ *   4:   ... something useful here ...
+ *   5:   goto again                    ; another iteration
+ *   6: done:
+ *   7:   r1 = &it
+ *   8:   call bpf_iter_num_destroy     ; clean up iter state
+ *   9:   exit
+ *
+ * This is a typical loop. Let's assume that we have a prune point at 1:,
+ * before we get to `call bpf_iter_num_next` (e.g., because of that `goto
+ * again`, assuming other heuristics don't get in a way).
+ *
+ * When we first time come to 1:, let's say we have some state X. We proceed
+ * to 2:, fork states, enqueue ACTIVE, validate NULL case successfully, exit.
+ * Now we come back to validate that forked ACTIVE state. We proceed through
+ * 3-5, come to goto, jump to 1:. Let's assume our state didn't change, so we
+ * are converging. But the problem is that we don't know that yet, as this
+ * convergence has to happen at iter_next() call site only. So if nothing is
+ * done, at 1: verifier will use bounded loop logic and declare infinite
+ * looping (and would be *technically* correct, if not for iterator "eventual
Quoted 8 lines
Quoted 6 lines

+ * sticky NULL" contract, see process_iter_next_call()). But we don't want
+ * that. So what we do in process_iter_next_call() when we go on another
+ * ACTIVE iteration, we bump slot->iter.depth, to mark that it's a different
+ * iteration. So when we detect soon-to-be-declared infinite loop, we also
+ * check if any of *ACTIVE* iterator state's depth differs. If yes, we pretend
+ * we are not looping and wait for next iter_next() call.

'depth' part of bpf_reg_state will be checked for equality in regsafe(), right?

no, it is explicitly skipped (and it's actually stacksafe(), not regsafe()). I can add explicit comment that we *ignore* depth

I was considering adding a flag to states_equal() whether to check depth or not (that would make iter_active_depths_differ unnecessary), but it doesn't feel right. Any preferences one way or the other?

Quoted 5 lines

Everytime we branch out in process_iter_next_call() there is depth++
So how come we're able to converge with:
+ if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+ if (states_equal(env, &sl->state, cur)) {
That's because states_equal() is done right before doing process_iter_next_call(), right?

Yes, we check convergence before we process_iter_next_call. We do converge because we ignore depth, as I mentioned above.

Quoted 3 lines

So depth counts the number of times bpf_iter*_next() was processed. In other words it's a number of ways the body of the loop can be walked?

More or less, yes. It's a number of sequential unrolls of loop body, each time with a different starting state. But all that only in the current code path. So it's not like "how many different loop states we could have" in total. It's number of loop unrols with the condition "assuming current code path that led to start of iterator loop". Some other code path could lead to the state (before iterator loop starts) that converges faster or slower, which is why I'm pointing out the distinction.

But I think "yes" would be the answer to the question you had in mind.

Quoted 22 lines
Quoted 11 lines
kernel/bpf/verifier.c +10 -0
+                     if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+                             if (states_equal(env, &sl->state, cur)) {
+                                     struct bpf_func_state *cur_frame;
+                                     struct bpf_reg_state *iter_state, *iter_reg;
+                                     int spi;
+
+                                     /* current state is valid due to states_equal(),
+                                      * so we can assume valid iter state, no need for extra
+                                      * (re-)validations
+                                      */

kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15154

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+                                     cur_frame = cur->frame[cur->curframe];
+                                     iter_reg = &cur_frame->regs[iter_arg_reg_idx];
+                                     spi = iter_get_spi(env, iter_reg);
+                                     if (spi < 0)
+                                             return spi;
+                                     iter_state = &func(env, iter_reg)->stack[spi].spilled_ptr;
+                                     if (iter_state->iter.state == BPF_ITER_STATE_ACTIVE)
+                                             goto hit;
+                             }
+                             goto skip_inf_loop_check;
Quoted 3 lines

This goto is "optional", right?
Meaning that if we remove it the states_maybe_looping() + states_equal() won't match anyway. The goto avoids wasting cycles.

yes, avoids doing this check again, but also felt cleaner to be explicit about skipping infinite loop check

Quoted 6 lines

kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15157

Quoted 4 lines
kernel/bpf/verifier.c +3 -0
+                     }
+                     /* attempt to detect infinite loop to avoid unnecessary doomed work */
+                     if (states_maybe_looping(&sl->state, cur) &&

Maybe cleaner is to remove above 'goto' and do '} else if (states_maybe_looping' here ?

I can undo this, it felt cleaner with explicit "skip infinite loop check" both for new code and for that async_entry_cnt check above. But I can revert to if/else if/else if pattern, though I find it harder to follow, given all this code (plus comments) is pretty long, so it's easy to lose track when reading

Quoted 6 lines
Quoted 6 lines
kernel/bpf/verifier.c +2 -0
+                         states_equal(env, &sl->state, cur) &&
+                         !iter_active_depths_differ(&sl->state, cur)) {
                              verbose_linfo(env, insn_idx, "; ");
                              verbose(env, "infinite loop detected at insn %d\n", insn_idx);
                              return -EINVAL;
#16 lore raw

Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops

Quoted 4 lines · Andrii Nakryiko

particular type. This will automatically work better for kfuncs as new/next/destroy trios will have the same struct bpf_iter_<type> * and it won't be possible to accidentally pass wrong bpf_iter_<type> to wrong new/next/destroy method.

Exactly.

Quoted 19 lines
Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +9 -0
+
+static int mark_stack_slots_iter(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
+                              enum bpf_arg_type arg_type, int insn_idx)
+{
+     struct bpf_func_state *state = func(env, reg);
+     enum bpf_iter_type type;
+     int spi, i, j, id;
+
+     spi = iter_get_spi(env, reg);
Quoted 8 lines

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1180

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+     if (spi < 0)
+             return spi;
+
+     type = arg_to_iter_type(arg_type);
+     if (type == BPF_ITER_TYPE_INVALID)
+             return -EINVAL;

Do we need destroy_if_dynptr_stack_slot() equivalent here?

Quoted 6 lines

no, because bpf_iter is always ref-counted, so we'll always have explicit unmark_stack_slots_iter() call, which will reset slot types

destroy_if_dynptr_stack_slot() was added because LOCAL dynptr doesn't require explicit destruction. I mentioned this difference (simplification for bpf_iter case) somewhere in the commit message.

I see. Makes sense.

Quoted 19 lines
Quoted 11 lines

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

Quoted 9 lines
              /* regular write of data into stack destroys any spilled ptr */
              state->stack[spi].spilled_ptr.type = NOT_INIT;
kernel/bpf/verifier.c +2 -2
-             /* Mark slots as STACK_MISC if they belonged to spilled ptr. */
-             if (is_spilled_reg(&state->stack[spi]))
+             /* Mark slots as STACK_MISC if they belonged to spilled ptr/dynptr/iter. */
+             if (is_stack_slot_special(&state->stack[spi]))
                      for (i = 0; i < BPF_REG_SIZE; i++)
                              scrub_spilled_slot(&state->stack[spi].slot_type[i]);

It fixes something for dynptr, right?

It's convoluted, I think it might not have a visible effect. This is the situation of partial (e.g., single byte) overwrite of STACK_DYNPTR/STACK_ITER, and without this change we'll leave some slot_types as STACK_MISC, while others as STACK_DYNPTP/STACK_ITER. This is unexpected state, but I think existing code always checks that for STACK_DYNPTR's all 8 slots are STACK_DYNPTR.

Quoted 4 lines

So I think it's a good clean up, but no consequences for dynptr correctness. And for STACK_ITER I don't have to worry about such mix, if any of the slot_type[i] is STACK_ITER, then it's a correct iterator.

agree. I was just curious.

Quoted 38 lines
Quoted 25 lines
Quoted 25 lines
kernel/bpf/verifier.c +25 -0
+static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx, int *reg_idx)
+{
+     struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
+     const struct btf_param *args;
+     const struct btf_type *t;
+     const struct btf *btf;
+     int nargs, i;
+
+     if (!bpf_pseudo_kfunc_call(insn))
+             return false;
+     if (!is_iter_next_kfunc(insn->imm))
+             return false;
+
+     btf = find_kfunc_desc_btf(env, insn->off);
+     if (IS_ERR(btf))
+             return false;
+
+     t = btf_type_by_id(btf, insn->imm);     /* FUNC */
+     t = btf_type_by_id(btf, t->type);       /* FUNC_PROTO */
+
+     args = btf_params(t);
+     nargs = btf_vlen(t);
+     for (i = 0; i < nargs; i++) {
+             if (is_kfunc_arg_iter(btf, &args[i])) {
+                     *reg_idx = BPF_REG_1 + i;
Quoted 8 lines

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1260

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+                     return true;
+             }
+     }

This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?

Yeah, a bit of generality. For a long time I had an assumption hardcoded about first argument being struct bpf_iter *, but that felt unclean, so I generalized that before submission.

Quoted 6 lines

But I can't think why we wouldn't just dictate (and enforce) that struct bpf_iter * is first. It makes sense, it's clean, and we lose nothing. This is another thing that differs between dynptr and iter, for dynptr such restriction wouldn't make sense.

Where would be a good place to enforce this for iter kfuncs?

I would probably just remove is_iter_next_insn() completely, hard code BPF_REG_1 and add a big comment for now.

In the follow up we can figure out how to:
BUILD_BUG_ON(!__same_type(bpf_iter_num_next, some canonical proto for iter_next));

Like we do:
BUILD_BUG_ON(!__same_type(ops->map_lookup_elem,

               (void *(*)(struct bpf_map *map, void *key))NULL));
Quoted 5 lines
Quoted 2 lines

'depth' part of bpf_reg_state will be checked for equality in regsafe(), right?

no, it is explicitly skipped (and it's actually stacksafe(), not regsafe()). I can add explicit comment that we *ignore* depth

Ahh. That's stacksafe() indeed.
Would be great to add a comment to:
+ if (old_reg->iter.type != cur_reg->iter.type ||
+ old_reg->iter.state != cur_reg->iter.state ||
+ !check_ids(old_reg->ref_obj_id, cur_reg->ref_obj_id, idmap))
+ return false;

that depth is explicitly not compared.

Quoted 3 lines

I was considering adding a flag to states_equal() whether to check depth or not (that would make iter_active_depths_differ unnecessary), but it doesn't feel right. Any preferences one way or the other?

probably overkill. just comment should be enough.

Quoted 13 lines
Quoted 5 lines

Everytime we branch out in process_iter_next_call() there is depth++
So how come we're able to converge with:
+ if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+ if (states_equal(env, &sl->state, cur)) {
That's because states_equal() is done right before doing process_iter_next_call(), right?

Yes, we check convergence before we process_iter_next_call. We do converge because we ignore depth, as I mentioned above.

Quoted 3 lines

So depth counts the number of times bpf_iter*_next() was processed. In other words it's a number of ways the body of the loop can be walked?

Quoted 8 lines

More or less, yes. It's a number of sequential unrolls of loop body, each time with a different starting state. But all that only in the current code path. So it's not like "how many different loop states we could have" in total. It's number of loop unrols with the condition "assuming current code path that led to start of iterator loop". Some other code path could lead to the state (before iterator loop starts) that converges faster or slower, which is why I'm pointing out the distinction.

got it. I know the comments are big and extensive already, but little bit more won't hurt.

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
kernel/bpf/verifier.c +3 -0
+                     }
+                     /* attempt to detect infinite loop to avoid unnecessary doomed work */
+                     if (states_maybe_looping(&sl->state, cur) &&
Quoted 7 lines
Quoted 1 line

Maybe cleaner is to remove above 'goto' and do '} else if (states_maybe_looping' here ?

I can undo this, it felt cleaner with explicit "skip infinite loop check" both for new code and for that async_entry_cnt check above. But I can revert to if/else if/else if pattern, though I find it harder to follow, given all this code (plus comments) is pretty long, so it's easy to lose track when reading

I'm fine whichever way. I just remembered that you typically try to avoid goto-s and seeing goto here that could have easily been 'else' raised my internal alarm that I could be missing something subtle in the code here.

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
kernel/bpf/verifier.c +2 -0
+                         states_equal(env, &sl->state, cur) &&
+                         !iter_active_depths_differ(&sl->state, cur)) {
                              verbose_linfo(env, insn_idx, "; ");
                              verbose(env, "infinite loop detected at insn %d\n", insn_idx);
                              return -EINVAL;
#17 lore raw

Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops

Quoted 9 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko

particular type. This will automatically work better for kfuncs as new/next/destroy trios will have the same struct bpf_iter_<type> * and it won't be possible to accidentally pass wrong bpf_iter_<type> to wrong new/next/destroy method.

Exactly.

cool, I'll change this to struct bpf_iter_<type>

[...]

Quoted 49 lines
Quoted 39 lines
Quoted 26 lines
Quoted 26 lines
kernel/bpf/verifier.c +25 -0
+static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx, int *reg_idx)
+{
+     struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
+     const struct btf_param *args;
+     const struct btf_type *t;
+     const struct btf *btf;
+     int nargs, i;
+
+     if (!bpf_pseudo_kfunc_call(insn))
+             return false;
+     if (!is_iter_next_kfunc(insn->imm))
+             return false;
+
+     btf = find_kfunc_desc_btf(env, insn->off);
+     if (IS_ERR(btf))
+             return false;
+
+     t = btf_type_by_id(btf, insn->imm);     /* FUNC */
+     t = btf_type_by_id(btf, t->type);       /* FUNC_PROTO */
+
+     args = btf_params(t);
+     nargs = btf_vlen(t);
+     for (i = 0; i < nargs; i++) {
+             if (is_kfunc_arg_iter(btf, &args[i])) {
+                     *reg_idx = BPF_REG_1 + i;
Quoted 8 lines

kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1260

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+                     return true;
+             }
+     }

This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?

Yeah, a bit of generality. For a long time I had an assumption hardcoded about first argument being struct bpf_iter *, but that felt unclean, so I generalized that before submission.

Quoted 6 lines

But I can't think why we wouldn't just dictate (and enforce) that struct bpf_iter * is first. It makes sense, it's clean, and we lose nothing. This is another thing that differs between dynptr and iter, for dynptr such restriction wouldn't make sense.

Where would be a good place to enforce this for iter kfuncs?

I would probably just remove is_iter_next_insn() completely, hard code BPF_REG_1 and add a big comment for now.

Quoted 7 lines

In the follow up we can figure out how to:
BUILD_BUG_ON(!__same_type(bpf_iter_num_next, some canonical proto for iter_next));

Like we do:
BUILD_BUG_ON(!__same_type(ops->map_lookup_elem,

               (void *(*)(struct bpf_map *map, void *key))NULL));

I ended up adding proper enforcement of iter kfunc prototypes and generalizing everything with new KF_ITER_xxx flags. It's a pretty major change that allows implementing new iterators even easier, please see v2. It's now possible to define iterators in kernel modules as well, thanks to not having to update core verifier logic for each new set of iter functions.

Quoted 13 lines
Quoted 5 lines
Quoted 2 lines

'depth' part of bpf_reg_state will be checked for equality in regsafe(), right?

no, it is explicitly skipped (and it's actually stacksafe(), not regsafe()). I can add explicit comment that we *ignore* depth

Ahh. That's stacksafe() indeed.
Would be great to add a comment to:

kernel/bpf/verifier.c +4 -0
+                       if (old_reg->iter.type != cur_reg->iter.type ||
+                           old_reg->iter.state != cur_reg->iter.state ||
+                           !check_ids(old_reg->ref_obj_id, cur_reg->ref_obj_id, idmap))
+                               return false;
Quoted 1 line

that depth is explicitly not compared.

ok, added

Quoted 7 lines
Quoted 4 lines

I was considering adding a flag to states_equal() whether to check depth or not (that would make iter_active_depths_differ unnecessary), but it doesn't feel right. Any preferences one way or the other?

probably overkill. just comment should be enough.

[...]

Quoted 14 lines
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
kernel/bpf/verifier.c +3 -0
+                     }
+                     /* attempt to detect infinite loop to avoid unnecessary doomed work */
+                     if (states_maybe_looping(&sl->state, cur) &&
Quoted 7 lines
Quoted 1 line

Maybe cleaner is to remove above 'goto' and do '} else if (states_maybe_looping' here ?

I can undo this, it felt cleaner with explicit "skip infinite loop check" both for new code and for that async_entry_cnt check above. But I can revert to if/else if/else if pattern, though I find it harder to follow, given all this code (plus comments) is pretty long, so it's easy to lose track when reading

Quoted 3 lines

I'm fine whichever way. I just remembered that you typically try to avoid goto-s and seeing goto here that could have easily been 'else' raised my internal alarm that I could be missing something subtle in the code here.

Well, it depends, as usual. I certainly don't like something like "goto process_bpf_exit" in do_check(), which jumps into the middle of a completely unrelated if/else branch, so there's that. But these "skip a bunch of checks" gotos are cleaner, IMO, if we are talking about a bunch of complicated if/else if/else checks. Let's go with explicit goto for now, we can always revert.

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
kernel/bpf/verifier.c +2 -0
+                         states_equal(env, &sl->state, cur) &&
+                         !iter_active_depths_differ(&sl->state, cur)) {
                              verbose_linfo(env, insn_idx, "; ");
                              verbose(env, "infinite loop detected at insn %d\n", insn_idx);
                              return -EINVAL;
author maintainer
#18 lore raw

PATCH 14/17 bpf: implement number iterator

In reply to Andrii Nakryiko

Implement first open-coded iterator type over a range of integers.

It's public API consists of:
- bpf_iter_num_new() constructor, which accepts [start, end) range (that is, start is inclusive, while end is exclusive).
- bpf_iter_num_next() which will keep returning 4-byte read-only pointer to int until the range is exhausted, at which point NULL will be returned. If bpf_iter_num_next() is kept calling after this, NULL will be persistently returned.
- bpf_iter_num_destroy() destructor, that needs to be called at some point to clean up iterator state. BPF verifier enforces that iterator destructor is called at some point before BPF program exits.

Note that start = end = X is a valid combination to setup empty iterator. bpf_iter_num_new() will return 0 (success) for any such combination.

If bpf_iter_num_new() detects invalid combination of input arguments, it returns error, resets iterator state to, effectively, empty iterator, so any subsequent call to bpf_iter_num_next() will keep returning NULL.

BPF verifier has no knowledge that returned integers are in the [start, end) value range, as both start and end are not statically known/enforced, they are runtime values only.

While implementation is pretty trivial, some care needs to be taken to avoid overflows and underflows. Subsequent selftests will validate correctness of [start, end) semantics, especially around extremes (INT_MIN and INT_MAX).

Similarly to bpf_loop(), we enforce that no more than BPF_MAX_LOOPS can be specified.

bpf_iter_num_{new,next,destroy}() is a logical evolution from bounded BPF loops and bpf_loop() helper and is the basis for implementing ergonomic BPF loops with no statically known and verified bounds. Subsequent patches implement bpf_for() macro, demonstrating how this can be wrapped into something that works and feels like a normal for() loop in C language.

---
 include/linux/bpf.h   | 14 +++++++--
 kernel/bpf/bpf_iter.c | 71 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/helpers.c  |  3 ++
 kernel/bpf/verifier.c | 24 +++++++++++++--
 4 files changed, 107 insertions(+), 5 deletions(-)
include/linux/bpf.h +11 -3
index a968282ba324..2a730759a471 100644
@@ -613,6 +613,9 @@ enum bpf_type_flag {
 	/* DYNPTR points to xdp_buff */
 	DYNPTR_TYPE_XDP		= BIT(16 + BPF_BASE_TYPE_BITS),
 
+	/* ITER of integers */
+	ITER_TYPE_NUM		= BIT(17 + BPF_BASE_TYPE_BITS),
+
 	__BPF_TYPE_FLAG_MAX,
 	__BPF_TYPE_LAST_FLAG	= __BPF_TYPE_FLAG_MAX - 1,
 };
@@ -620,7 +623,7 @@ enum bpf_type_flag {
 #define DYNPTR_TYPE_FLAG_MASK	(DYNPTR_TYPE_LOCAL | DYNPTR_TYPE_RINGBUF | DYNPTR_TYPE_SKB \
 				 | DYNPTR_TYPE_XDP)
 
-#define ITER_TYPE_FLAG_MASK	(0)
+#define ITER_TYPE_FLAG_MASK	(ITER_TYPE_NUM)
 
 /* Max number of base types. */
 #define BPF_BASE_TYPE_LIMIT	(1UL << BPF_BASE_TYPE_BITS)
@@ -1167,6 +1170,7 @@ u32 bpf_dynptr_get_size(const struct bpf_dynptr_kern *ptr);
 
 enum bpf_iter_type {
 	BPF_ITER_TYPE_INVALID,
+	BPF_ITER_TYPE_NUM,
 };
 
 #ifdef CONFIG_BPF_JIT
@@ -1622,8 +1626,12 @@ 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)
+/* Maximum number of loops for bpf_loop and bpf_iter_num.
+ * It's enum to expose it (and thus make it discoverable) through BTF.
+ */
+enum {
+	BPF_MAX_LOOPS = 8 * 1024 * 1024,
+};
 
 #define BPF_F_ACCESS_MASK	(BPF_F_RDONLY |		\
 				 BPF_F_RDONLY_PROG |	\
kernel/bpf/bpf_iter.c +71 -0

80 lines not on this page · raw message

kernel/bpf/helpers.c +3 -0
index de9ef8476e29..23c8f2313d5a 100644
@@ -2398,6 +2398,9 @@ BTF_ID_FLAGS(func, bpf_rcu_read_lock)
 BTF_ID_FLAGS(func, bpf_rcu_read_unlock)
 BTF_ID_FLAGS(func, bpf_dynptr_slice, KF_RET_NULL)
 BTF_ID_FLAGS(func, bpf_dynptr_slice_rdwr, KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_num_new)
+BTF_ID_FLAGS(func, bpf_iter_num_next, KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_num_destroy)
 BTF_SET8_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
kernel/bpf/verifier.c +22 -2
index 58754929ee33..9671b4f354e9 100644
@@ -779,6 +779,8 @@ static const char *dynptr_type_str(enum bpf_dynptr_type type)
 static const char *iter_type_str(enum bpf_iter_type type)
 {
 	switch (type) {
+	case BPF_ITER_TYPE_NUM:
+		return "num";
 	case BPF_ITER_TYPE_INVALID:
 		return "<invalid>";
 	default:
@@ -1157,6 +1159,8 @@ static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg
 static enum bpf_dynptr_type arg_to_iter_type(enum bpf_arg_type arg_type)
 {
 	switch (arg_type & ITER_TYPE_FLAG_MASK) {
+	case ITER_TYPE_NUM:
+		return BPF_ITER_TYPE_NUM;
 	default:
 		return BPF_ITER_TYPE_INVALID;
 	}
@@ -9445,6 +9449,9 @@ enum special_kfunc_type {
 	KF_bpf_dynptr_from_xdp,
 	KF_bpf_dynptr_slice,
 	KF_bpf_dynptr_slice_rdwr,
+	KF_bpf_iter_num_new,
+	KF_bpf_iter_num_next,
+	KF_bpf_iter_num_destroy,
 };
 
 BTF_SET_START(special_kfunc_set)
@@ -9483,6 +9490,9 @@ BTF_ID(func, bpf_dynptr_from_skb)
 BTF_ID(func, bpf_dynptr_from_xdp)
 BTF_ID(func, bpf_dynptr_slice)
 BTF_ID(func, bpf_dynptr_slice_rdwr)
+BTF_ID(func, bpf_iter_num_new)
+BTF_ID(func, bpf_iter_num_next)
+BTF_ID(func, bpf_iter_num_destroy)
 
 static bool is_kfunc_bpf_rcu_read_lock(struct bpf_kfunc_call_arg_meta *meta)
 {
@@ -9496,7 +9506,7 @@ static bool is_kfunc_bpf_rcu_read_unlock(struct bpf_kfunc_call_arg_meta *meta)
 
 static bool is_iter_next_kfunc(int btf_id)
 {
-	return false;
+	return btf_id == special_kfunc_list[KF_bpf_iter_num_next];
 }
 
 static enum kfunc_ptr_arg_type
@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 			if (is_kfunc_arg_uninit(btf, &args[i]))
 				iter_arg_type |= MEM_UNINIT;
 
-			ret = process_iter_arg(env, regno, insn_idx, iter_arg_type,  meta);
+			if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] ||
+			    meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) {
+				iter_arg_type |= ITER_TYPE_NUM;
+			} else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) {
+				iter_arg_type |= ITER_TYPE_NUM | OBJ_RELEASE;
+			} else {
+				verbose(env, "verifier internal error: unrecognized iterator kfunc\n");
+				return -EFAULT;
+			}
+
+			ret = process_iter_arg(env, regno, insn_idx, iter_arg_type, meta);
 			if (ret < 0)
 				return ret;
 			break;
Signature · 1 line
2.30.2
#19 lore raw

Re: [PATCH bpf-next 14/17] bpf: implement number iterator

kernel/bpf/verifier.c static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ · line 10295

Quoted 12 lines · Andrii Nakryiko

static enum kfunc_ptr_arg_type

kernel/bpf/verifier.c +5 -1
@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 			if (is_kfunc_arg_uninit(btf, &args[i]))
 				iter_arg_type |= MEM_UNINIT;
 
-			ret = process_iter_arg(env, regno, insn_idx, iter_arg_type,  meta);
+			if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] ||
+			    meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) {
+				iter_arg_type |= ITER_TYPE_NUM;
+			} else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) {
+				iter_arg_type |= ITER_TYPE_NUM | OBJ_RELEASE;

Since OBJ_RELEASE is set pretty late here and kfuncs are not marked with KF_RELEASE, the arg_type_is_release() in check_func_arg_reg_off() won't trigger. So I'm confused why there is:
+ if (arg_type_is_iter(arg_type))
+ return 0;
in the previous patch.
Will it ever trigger?

Separate question: What happens when the user does:
bpf_iter_destroy(&it); bpf_iter_destroy(&it);

+ if (!is_iter_reg_valid_init(env, reg)) {
+ verbose(env, "expected an initialized iter as arg #%d\n", regno);
will trigger, right?
I didn't find such selftest.

#20 lore raw

Re: [PATCH bpf-next 14/17] bpf: implement number iterator

Quoted 8 lines · Alexei Starovoitov
Quoted 6 lines · Andrii Nakryiko

static enum kfunc_ptr_arg_type

kernel/bpf/verifier.c +0 -0
@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
                      if (is_kfunc_arg_uninit(btf, &args[i]))
                              iter_arg_type |= MEM_UNINIT;
 
Quoted 9 lines

kernel/bpf/verifier.c static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ · line 10295

Quoted 6 lines
kernel/bpf/verifier.c +5 -1
-                     ret = process_iter_arg(env, regno, insn_idx, iter_arg_type,  meta);
+                     if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] ||
+                         meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) {
+                             iter_arg_type |= ITER_TYPE_NUM;
+                     } else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) {
+                             iter_arg_type |= ITER_TYPE_NUM | OBJ_RELEASE;

Since OBJ_RELEASE is set pretty late here and kfuncs are not marked with KF_RELEASE, the arg_type_is_release() in check_func_arg_reg_off() won't trigger.

yeah, I had troubles with doing this release using existing scheme. KF_RELEASE doesn't work, as it makes some extra assumptions about what was acquired, it didn't fit iters. And I didn't have a precedent in dynptr to learn from, as RINGBUF dynptr is "acquired" and "released" using helper. Basically, we don't have dynptr release kfunc yet.

So I set the OBJ_RELEASE flag for process_iter_arg to do an explicit release.

I'd appreciate guidance on how to do this cleaner. Naive attempt to set KF_ACQUIRE for bpf_iter_num_new() and KF_RELEASE for bpf_iter_num_destroy() didn't work.

Quoted 5 lines

So I'm confused why there is:

(quoted diff) +2 -0
+               if (arg_type_is_iter(arg_type))
+                       return 0;

in the previous patch.
Will it ever trigger?

maybe not, just followed what dynptr is doing

Quoted 4 lines

Separate question: What happens when the user does:
bpf_iter_destroy(&it); bpf_iter_destroy(&it);

After the first destroy stack slots are marked STACK_INVALID, so next bpf_iter_destroy(&it) will complain about not seeing the initialized iterator.

Quoted 5 lines
(quoted diff) +2 -0
+               if (!is_iter_reg_valid_init(env, reg)) {
+                       verbose(env, "expected an initialized iter as arg #%d\n", regno);

will trigger, right?
I didn't find such selftest.

yep, that's the idea, I just checked, I do have such test, it's in iters_state_safety.c:

__failure __msg("expected an initialized iter as arg #1") int double_destroy_fail(void *ctx)

There is also next_after_destroy_fail, next_without_new_fail, and other obvious error conditions. But it would be good for few people to check that with a fresh eye. I added them a long time ago, and might have missed something.

#21 lore raw

Re: [PATCH bpf-next 14/17] bpf: implement number iterator

Quoted 26 lines · Andrii Nakryiko
Quoted 8 lines · Alexei Starovoitov
Quoted 6 lines · Andrii Nakryiko

static enum kfunc_ptr_arg_type

kernel/bpf/verifier.c +0 -0
@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
                      if (is_kfunc_arg_uninit(btf, &args[i]))
                              iter_arg_type |= MEM_UNINIT;
 
Quoted 9 lines

kernel/bpf/verifier.c static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ · line 10295

Quoted 6 lines
kernel/bpf/verifier.c +5 -1
-                     ret = process_iter_arg(env, regno, insn_idx, iter_arg_type,  meta);
+                     if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] ||
+                         meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) {
+                             iter_arg_type |= ITER_TYPE_NUM;
+                     } else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) {
+                             iter_arg_type |= ITER_TYPE_NUM | OBJ_RELEASE;

Since OBJ_RELEASE is set pretty late here and kfuncs are not marked with KF_RELEASE, the arg_type_is_release() in check_func_arg_reg_off() won't trigger.

yeah, I had troubles with doing this release using existing scheme. KF_RELEASE doesn't work, as it makes some extra assumptions about what was acquired, it didn't fit iters. And I didn't have a precedent in dynptr to learn from, as RINGBUF dynptr is "acquired" and "released" using helper. Basically, we don't have dynptr release kfunc yet.

Quoted 5 lines

So I set the OBJ_RELEASE flag for process_iter_arg to do an explicit release.

I'd appreciate guidance on how to do this cleaner. Naive attempt to set KF_ACQUIRE for bpf_iter_num_new() and KF_RELEASE for bpf_iter_num_destroy() didn't work.

yep. KF_ACQUIRE and KF_RELEASE don't fit here, since they need the register to be ref_obj_id-ed while here it's in the stack.

The current patch is fine. We can generalize iter and dynptr later in the follow up.

Quoted 24 lines
Quoted 6 lines

So I'm confused why there is:

(quoted diff) +2 -0
+               if (arg_type_is_iter(arg_type))
+                       return 0;

in the previous patch.
Will it ever trigger?

maybe not, just followed what dynptr is doing

Quoted 4 lines

Separate question: What happens when the user does:
bpf_iter_destroy(&it); bpf_iter_destroy(&it);

After the first destroy stack slots are marked STACK_INVALID, so next bpf_iter_destroy(&it) will complain about not seeing the initialized iterator.

Quoted 5 lines
(quoted diff) +2 -0
+               if (!is_iter_reg_valid_init(env, reg)) {
+                       verbose(env, "expected an initialized iter as arg #%d\n", regno);

will trigger, right?
I didn't find such selftest.

Quoted 5 lines

yep, that's the idea, I just checked, I do have such test, it's in iters_state_safety.c:

__failure __msg("expected an initialized iter as arg #1") int double_destroy_fail(void *ctx)

See it now. Thanks for checking.

Quoted 4 lines

There is also next_after_destroy_fail, next_without_new_fail, and other obvious error conditions. But it would be good for few people to check that with a fresh eye. I added them a long time ago, and might have missed something.

author maintainer
#22 lore raw

PATCH 15/17 selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros

In reply to Andrii Nakryiko

Add bpf_for_each(), bpf_for() and bpf_repeat() macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer loop would look like:

  int i;
  int arr[N];

  bpf_for(i, 0, N) {
  /* verifier will know that i >= 0 && i < N, so could be used to
   * directly access array elements with no extra checks
   */
   arr[i] = i;
  }

bpf_repeat() is very similar, but it doesn't expose iteration number and is mean as a simple "repeat action N times":

bpf_repeat(N) { /* whatever */ }

Note that break and continue inside the {} block work as expected.

bpf_for_each() is a generalization over any kind of BPF open-coded iterator allowing to use for-each-like approach instead of calling low-level bpf_iter_<type>_{new,next,destroy}() APIs explicitly. E.g.:

struct cgroup *cg;

  bpf_for_each(cgroup, cg, some, input, args) {
      /* do something with each cg */
  }

Would call (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where some, input, args are passed verbatim into constructor as
bpf_iter_cgroup_new(&it, some, input, args).

As a demonstration, add pyperf variant based on bpf_for() loop.

Also clean up few tests that either included bpf_misc.h header unnecessarily from user-space or included it before any common types are defined.

---
 .../bpf/prog_tests/bpf_verif_scale.c          |  6 ++
 .../bpf/prog_tests/uprobe_autoattach.c        |  1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  | 76 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/lsm.c       |  4 +-
 tools/testing/selftests/bpf/progs/pyperf.h    | 14 +++-
 .../selftests/bpf/progs/pyperf600_iter.c      |  7 ++
 .../selftests/bpf/progs/pyperf600_nounroll.c  |  3 -
 7 files changed, 101 insertions(+), 10 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +6 -0
index 5ca252823294..731c343897d8 100644
@@ -144,6 +144,12 @@ void test_verif_scale_pyperf600_nounroll()
 	scale_test("pyperf600_nounroll.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_pyperf600_iter()
+{
+	/* open-coded BPF iterator version */
+	scale_test("pyperf600_iter.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_loop1()
 {
 	scale_test("loop1.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
tools/testing/selftests/bpf/prog_tests/uprobe_autoattach.c +0 -1
index 6558c857e620..d5b3377aa33c 100644
@@ -3,7 +3,6 @@
 
 #include <test_progs.h>
 #include "test_uprobe_autoattach.skel.h"
-#include "progs/bpf_misc.h"
 
 /* uprobe attach point */
 static noinline int autoattach_trigger_func(int arg1, int arg2, int arg3,
tools/testing/selftests/bpf/progs/bpf_misc.h +76 -0

81 lines not on this page · raw message

tools/testing/selftests/bpf/progs/lsm.c +2 -2
index dc93887ed34c..fadfdd98707c 100644
@@ -4,12 +4,12 @@
  * Copyright 2020 Google LLC.
  */
 
-#include "bpf_misc.h"
 #include "vmlinux.h"
+#include <errno.h>
 #include <bpf/bpf_core_read.h>
 #include <bpf/bpf_helpers.h>
 #include <bpf/bpf_tracing.h>
-#include <errno.h>
+#include "bpf_misc.h"
 
 struct {
 	__uint(type, BPF_MAP_TYPE_ARRAY);
tools/testing/selftests/bpf/progs/pyperf.h +10 -4
index 6c7b1fb268d6..f2e7a31c8d75 100644
@@ -7,6 +7,7 @@
 #include <stdbool.h>
 #include <linux/bpf.h>
 #include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
 
 #define FUNCTION_NAME_LEN 64
 #define FILE_NAME_LEN 128
@@ -294,17 +295,22 @@ int __on_event(struct bpf_raw_tracepoint_args *ctx)
 	if (ctx.done)
 		return 0;
 #else
-#ifdef NO_UNROLL
+#if defined(USE_ITER)
+/* no for loop, no unrolling */
+#elif defined(NO_UNROLL)
 #pragma clang loop unroll(disable)
-#else
-#ifdef UNROLL_COUNT
+#elif defined(UNROLL_COUNT)
 #pragma clang loop unroll_count(UNROLL_COUNT)
 #else
 #pragma clang loop unroll(full)
-#endif
 #endif /* NO_UNROLL */
 		/* Unwind python stack */
+#ifdef USE_ITER
+		int i;
+		bpf_for(i, 0, STACK_MAX_LEN) {
+#else /* !USE_ITER */
 		for (int i = 0; i < STACK_MAX_LEN; ++i) {
+#endif
 			if (frame_ptr && get_frame_data(frame_ptr, pidData, &frame, &sym)) {
 				int32_t new_symbol_id = *symbol_counter * 64 + cur_cpu;
 				int32_t *symbol_id = bpf_map_lookup_elem(&symbolmap, &sym);
tools/testing/selftests/bpf/progs/pyperf600_iter.c new file +7 -0
new file mode 100644
index 000000000000..d62e1b200c30
@@ -0,0 +1,7 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2023 Meta Platforms, Inc. and affiliates.
+#define STACK_MAX_LEN 600
+#define SUBPROGS
+#define NO_UNROLL
+#define USE_ITER
+#include "pyperf.h"
tools/testing/selftests/bpf/progs/pyperf600_nounroll.c +0 -3
index 6beff7502f4d..520b58c4f8db 100644
@@ -2,7 +2,4 @@
 // Copyright (c) 2019 Facebook
 #define STACK_MAX_LEN 600
 #define NO_UNROLL
-/* clang will not unroll at all.
- * Total program size is around 2k insns
- */
 #include "pyperf.h"
Signature · 1 line
2.30.2
#23 lore raw

Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros

Quoted 114 lines · Andrii Nakryiko

Add bpf_for_each(), bpf_for() and bpf_repeat() macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer loop would look like:

  int i;
  int arr[N];

  bpf_for(i, 0, N) {
  /* verifier will know that i >= 0 && i < N, so could be used to
   * directly access array elements with no extra checks
   */
   arr[i] = i;
  }

bpf_repeat() is very similar, but it doesn't expose iteration number and is mean as a simple "repeat action N times":

bpf_repeat(N) { /* whatever */ }

Note that break and continue inside the {} block work as expected.

bpf_for_each() is a generalization over any kind of BPF open-coded iterator allowing to use for-each-like approach instead of calling low-level bpf_iter_<type>_{new,next,destroy}() APIs explicitly. E.g.:

struct cgroup *cg;

  bpf_for_each(cgroup, cg, some, input, args) {
      /* do something with each cg */
  }

Would call (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where some, input, args are passed verbatim into constructor as
bpf_iter_cgroup_new(&it, some, input, args).

As a demonstration, add pyperf variant based on bpf_for() loop.

Also clean up few tests that either included bpf_misc.h header unnecessarily from user-space or included it before any common types are defined.

---
 .../bpf/prog_tests/bpf_verif_scale.c          |  6 ++
 .../bpf/prog_tests/uprobe_autoattach.c        |  1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  | 76 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/lsm.c       |  4 +-
 tools/testing/selftests/bpf/progs/pyperf.h    | 14 +++-
 .../selftests/bpf/progs/pyperf600_iter.c      |  7 ++
 .../selftests/bpf/progs/pyperf600_nounroll.c  |  3 -
 7 files changed, 101 insertions(+), 10 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +6 -0
index 5ca252823294..731c343897d8 100644
@@ -144,6 +144,12 @@ void test_verif_scale_pyperf600_nounroll()
 	scale_test("pyperf600_nounroll.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_pyperf600_iter()
+{
+	/* open-coded BPF iterator version */
+	scale_test("pyperf600_iter.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_loop1()
 {
 	scale_test("loop1.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
tools/testing/selftests/bpf/prog_tests/uprobe_autoattach.c +0 -1
index 6558c857e620..d5b3377aa33c 100644
@@ -3,7 +3,6 @@
 
 #include <test_progs.h>
 #include "test_uprobe_autoattach.skel.h"
-#include "progs/bpf_misc.h"
 
 /* uprobe attach point */
 static noinline int autoattach_trigger_func(int arg1, int arg2, int arg3,
tools/testing/selftests/bpf/progs/bpf_misc.h +21 -0
index f704885aa534..08a791f307a6 100644
@@ -75,5 +75,81 @@
 #define FUNC_REG_ARG_CNT 5
 #endif
 
+struct bpf_iter;
+
+extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym;
+extern int *bpf_iter_num_next(struct bpf_iter *it) __ksym;
+extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym;
+
+#ifndef bpf_for_each
+/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF
+ * open-coded iterators without having to write mundane explicit low-level
+ * loop. Instead, it provides for()-like generic construct that can be used
+ * pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write:
+ *
+ * struct cgroup *cg, *parent_cg = <...>;
+ *
+ * bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) {
+ *     bpf_printk("Child cgroup id = %d", cg->cgroup_id);
+ *     if (cg->cgroup_id == 123)
+ *         break;
+ * }
+ *
+ * I.e., it looks almost like high-level for each loop in other languages,

tools/testing/selftests/bpf/progs/bpf_misc.h line 108

Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +10 -0
+ * supports continue/break, and is verifiable by BPF verifier.
+ *
+ * For iterating integers, the difference betwen bpf_for_each(num, i, N, M)
+ * and bpf_for(i, N, M) is in that bpf_for() provides additional proof to
+ * verifier that i is in [N, M) range, and in bpf_for_each() case i is `int
+ * *`, not just `int`. So for integers bpf_for() is more convenient.
+ */
+#define bpf_for_each(type, cur, args...) for (						  \
+	/* initialize and define destructor */						  \
+	struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))),	  \

We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.

Also what are the rules for attr(cleanup()).
When does it get called?
My understanding that the visibility of ___it is only within for() body. So when the prog does:
bpf_for(i, 0, 10) sum += i;
bpf_for(i, 0, 10) sum += i;

the compiler should generate bpf_iter_num_destroy right after each bpf_for() ? Or will it group them at the end of function body and destroy all iterators ? Will compiler reuse the stack space used by ___it in case there are multiple bpf_for-s ?

Quoted 16 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +16 -0
+	/* ___p pointer is just to call bpf_iter_##type##_new() *once* to init ___it */	  \
+			*___p = (bpf_iter_##type##_new(&___it, ##args),		  \
+	/* this is a workaround for Clang bug: it currently doesn't emit BTF */		  \
+	/* for bpf_iter_##type##_destroy when used from cleanup() attribute */		  \
+				(void)bpf_iter_##type##_destroy, (void *)0);		  \
+	/* iteration and termination check */						  \
+	((cur = bpf_iter_##type##_next(&___it)));					  \
+	/* nothing here  */								  \
+)
+#endif /* bpf_for_each */
+
+#ifndef bpf_for
+/* bpf_for(i, start, end) proves to verifier that i is in [start, end) */
+#define bpf_for(i, start, end) for (							  \
+	/* initialize and define destructor */						  \
+	struct bpf_iter ___it __attribute__((cleanup(bpf_iter_num_destroy))),		  \

tools/testing/selftests/bpf/progs/bpf_misc.h line 134

Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +10 -0
+	/* ___p pointer is necessary to call bpf_iter_num_new() *once* to init ___it */	  \
+			*___p = (bpf_iter_num_new(&___it, (start), (end)),		  \
+	/* this is a workaround for Clang bug: it currently doesn't emit BTF */		  \
+	/* for bpf_iter_num_destroy when used from cleanup() attribute */		  \
+				(void)bpf_iter_num_destroy, (void *)0);			  \
+	({										  \
+		/* iteration step */							  \
+		int *___t = bpf_iter_num_next(&___it);					  \
+		/* termination and bounds check */					  \
+		(___t && ((i) = *___t, i >= (start) && i < (end)));			  \

The i >= (start) && i < (end) is necessary to make sure that the verifier tightens the range of 'i' inside the body of the loop and
when the program does arr[i] access the verifier will know that 'i' is within bounds, right?

In such case should we add __builtin_constant_p() check for 'start' and 'end' ? int arr[100];
if (var < 100)
bpf_for(i, 0, global_var) sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.

Also if start and end are variables they potentially can change between bpf_iter_num_new() and in each iteration of the loop.
__builtin_constant_p() might be too restrictive.
May be read start/end once, at least?

Quoted 5 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5 -0
+	});										  \
+	/* nothing here  */								  \
+)
+#endif /* bpf_for */
+
#24 lore raw

Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros

Quoted 121 lines · Alexei Starovoitov
Quoted 119 lines · Andrii Nakryiko

Add bpf_for_each(), bpf_for() and bpf_repeat() macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer loop would look like:

  int i;
  int arr[N];

  bpf_for(i, 0, N) {
  /* verifier will know that i >= 0 && i < N, so could be used to
   * directly access array elements with no extra checks
   */
   arr[i] = i;
  }

bpf_repeat() is very similar, but it doesn't expose iteration number and is mean as a simple "repeat action N times":

bpf_repeat(N) { /* whatever */ }

Note that break and continue inside the {} block work as expected.

bpf_for_each() is a generalization over any kind of BPF open-coded iterator allowing to use for-each-like approach instead of calling low-level bpf_iter_<type>_{new,next,destroy}() APIs explicitly. E.g.:

struct cgroup *cg;

  bpf_for_each(cgroup, cg, some, input, args) {
      /* do something with each cg */
  }

Would call (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where some, input, args are passed verbatim into constructor as
bpf_iter_cgroup_new(&it, some, input, args).

As a demonstration, add pyperf variant based on bpf_for() loop.

Also clean up few tests that either included bpf_misc.h header unnecessarily from user-space or included it before any common types are defined.

---
 .../bpf/prog_tests/bpf_verif_scale.c          |  6 ++
 .../bpf/prog_tests/uprobe_autoattach.c        |  1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  | 76 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/lsm.c       |  4 +-
 tools/testing/selftests/bpf/progs/pyperf.h    | 14 +++-
 .../selftests/bpf/progs/pyperf600_iter.c      |  7 ++
 .../selftests/bpf/progs/pyperf600_nounroll.c  |  3 -
 7 files changed, 101 insertions(+), 10 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +6 -0
index 5ca252823294..731c343897d8 100644
@@ -144,6 +144,12 @@ void test_verif_scale_pyperf600_nounroll()
      scale_test("pyperf600_nounroll.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_pyperf600_iter()
+{
+     /* open-coded BPF iterator version */
+     scale_test("pyperf600_iter.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_loop1()
 {
      scale_test("loop1.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
tools/testing/selftests/bpf/prog_tests/uprobe_autoattach.c +0 -1
index 6558c857e620..d5b3377aa33c 100644
@@ -3,7 +3,6 @@
 
 #include <test_progs.h>
 #include "test_uprobe_autoattach.skel.h"
-#include "progs/bpf_misc.h"
 
 /* uprobe attach point */
 static noinline int autoattach_trigger_func(int arg1, int arg2, int arg3,
tools/testing/selftests/bpf/progs/bpf_misc.h +26 -0
index f704885aa534..08a791f307a6 100644
@@ -75,5 +75,81 @@
 #define FUNC_REG_ARG_CNT 5
 #endif
 
+struct bpf_iter;
+
+extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym;
+extern int *bpf_iter_num_next(struct bpf_iter *it) __ksym;
+extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym;
+
+#ifndef bpf_for_each
+/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF
+ * open-coded iterators without having to write mundane explicit low-level
+ * loop. Instead, it provides for()-like generic construct that can be used
+ * pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write:
+ *
+ * struct cgroup *cg, *parent_cg = <...>;
+ *
+ * bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) {
+ *     bpf_printk("Child cgroup id = %d", cg->cgroup_id);
+ *     if (cg->cgroup_id == 123)
+ *         break;
+ * }
+ *
+ * I.e., it looks almost like high-level for each loop in other languages,
+ * supports continue/break, and is verifiable by BPF verifier.
+ *
+ * For iterating integers, the difference betwen bpf_for_each(num, i, N, M)
+ * and bpf_for(i, N, M) is in that bpf_for() provides additional proof to
+ * verifier that i is in [N, M) range, and in bpf_for_each() case i is `int
Quoted 8 lines

tools/testing/selftests/bpf/progs/bpf_misc.h line 108

Quoted 5 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5 -0
+ * *`, not just `int`. So for integers bpf_for() is more convenient.
+ */
+#define bpf_for_each(type, cur, args...) for (                                                 \
+     /* initialize and define destructor */                                            \
+     struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))),        \

We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.

yes, I'll add a comment. I think cleanup attribute isn't standard as well, I'll mention it. This shouldn't be restrictive, though, as we expect very modern Clang (or eventually GCC), which definitely will support all of that. And I feel like most people don't restrict their BPF-side code to strict C89 anyways.

Quoted 3 lines

Also what are the rules for attr(cleanup()).
When does it get called?

From GCC documentation:

Quoted 1 line

The cleanup attribute runs a function when the variable goes out of scope.

So given ___it is bound to for loop, any code path that leads to loop exit (so, when condition turns false or *breaking* out of the loop, which is why I use cleanup, this was a saving grace for this approach to work at all).

Quoted 1 line

My understanding that the visibility of ___it is only within for() body.

right

Quoted 5 lines

So when the prog does:
bpf_for(i, 0, 10) sum += i;
bpf_for(i, 0, 10) sum += i;

the compiler should generate bpf_iter_num_destroy right after each bpf_for() ?

Conceptually, yes, but see the note about breaking out of the loop above. How actual assembly code is generated is beyond our control. If the compiler generates multiple separate code paths, each with its own destroy, that's fine as well. No assumptions are made in the verifier, we just need to see one bpf_iter_<type>_destroy() for each instance of iterator.

Quoted 1 line

Or will it group them at the end of function body and destroy all iterators ?

That would be a bug, as documentation states that clean up happens as soon as a variable goes out of scope. Delaying clean up could result in program logic bugs. I.e., we rely on destructors to be called as soon as possible.

Quoted 1 line

Will compiler reuse the stack space used by ___it in case there are multiple bpf_for-s ?

That's the question to compiler developers, but I'd assume that, yes, it should. Why not?

And looking at, for example, iter_pass_iter_ptr_to_subprog which has 4 sequential bpf_for() loops:

0000000000002328 <iter_pass_iter_ptr_to_subprog>:

    1125:       bf a6 00 00 00 00 00 00 r6 = r10
    1126:       07 06 00 00 28 ff ff ff r6 += -216    <-- THIS IS ITER
    1127:       bf 61 00 00 00 00 00 00 r1 = r6
    1128:       b4 02 00 00 00 00 00 00 w2 = 0
    1129:       b4 03 00 00 10 00 00 00 w3 = 16
    1130:       85 10 00 00 ff ff ff ff call -1
                0000000000002350:  R_BPF_64_32  bpf_iter_num_new
    1131:       bf a7 00 00 00 00 00 00 r7 = r10
    1132:       07 07 00 00 c0 ff ff ff r7 += -64
    1133:       bf 61 00 00 00 00 00 00 r1 = r6
    1134:       bf 72 00 00 00 00 00 00 r2 = r7
    1135:       b4 03 00 00 10 00 00 00 w3 = 16
    1136:       b4 04 00 00 02 00 00 00 w4 = 2
    1137:       85 10 00 00 53 00 00 00 call 83
                0000000000002388:  R_BPF_64_32  .text
    1138:       bf 61 00 00 00 00 00 00 r1 = r6
    1139:       85 10 00 00 ff ff ff ff call -1
                0000000000002398:  R_BPF_64_32  bpf_iter_num_destroy
    1140:       bf 61 00 00 00 00 00 00 r1 = r6     <<--- HERE WE REUSE
    1141:       b4 02 00 00 00 00 00 00 w2 = 0
    1142:       b4 03 00 00 20 00 00 00 w3 = 32
    1143:       85 10 00 00 ff ff ff ff call -1
                00000000000023b8:  R_BPF_64_32  bpf_iter_num_new

Note that r6 is set to fp-216 and is just reused as is for second bpf_for loop (second bpf_iter_num_new) call.

Quoted 23 lines
Quoted 23 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +22 -0
+     /* ___p pointer is just to call bpf_iter_##type##_new() *once* to init ___it */   \
+                     *___p = (bpf_iter_##type##_new(&___it, ##args),           \
+     /* this is a workaround for Clang bug: it currently doesn't emit BTF */           \
+     /* for bpf_iter_##type##_destroy when used from cleanup() attribute */            \
+                             (void)bpf_iter_##type##_destroy, (void *)0);              \
+     /* iteration and termination check */                                             \
+     ((cur = bpf_iter_##type##_next(&___it)));                                         \
+     /* nothing here  */                                                               \
+)
+#endif /* bpf_for_each */
+
+#ifndef bpf_for
+/* bpf_for(i, start, end) proves to verifier that i is in [start, end) */
+#define bpf_for(i, start, end) for (                                                   \
+     /* initialize and define destructor */                                            \
+     struct bpf_iter ___it __attribute__((cleanup(bpf_iter_num_destroy))),             \
+     /* ___p pointer is necessary to call bpf_iter_num_new() *once* to init ___it */   \
+                     *___p = (bpf_iter_num_new(&___it, (start), (end)),                \
+     /* this is a workaround for Clang bug: it currently doesn't emit BTF */           \
+     /* for bpf_iter_num_destroy when used from cleanup() attribute */                 \
+                             (void)bpf_iter_num_destroy, (void *)0);                   \
+     ({                                                                                \
Quoted 8 lines

tools/testing/selftests/bpf/progs/bpf_misc.h line 134

Quoted 4 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +4 -0
+             /* iteration step */                                                      \
+             int *___t = bpf_iter_num_next(&___it);                                    \
+             /* termination and bounds check */                                        \
+             (___t && ((i) = *___t, i >= (start) && i < (end)));                       \

The i >= (start) && i < (end) is necessary to make sure that the verifier tightens the range of 'i' inside the body of the loop and
when the program does arr[i] access the verifier will know that 'i' is within bounds, right?

yes, it feels like a common pattern, but I was contemplating to add bpf_for_uncheck() where we "expose" i value, but don't do check. I decided to keep it simple, as most examples actually required bounds checks anyways. And for cases where we don't, often bpf_repeat() suffices. One other way would be to expose i from bpf_repeat(), just no checks.

One restriction with this approach is that I can't define both struct bpf_iter __it and int i inside for loop, so cur/i has to be declared and passed into bpf_for/bpf_for_each by user explicitly. So for bpf_repeat() to expose i would require always doing:

int i;

bpf_repeat(i, 100) { /* i is set to 0, 1, ..., 99 */ }

which, if you don't care about iteration number, is a bit of waste. So don't know, I'm undecided on bpf_repeat with i.

Quoted 2 lines

In such case should we add __builtin_constant_p() check for 'start' and 'end' ?

that seems to defy the purpose, as if you know start/end statically, you might as well just write either unrolled loop or bounded for() loop

Quoted 4 lines

int arr[100];
if (var < 100)
bpf_for(i, 0, global_var) sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.

but I'm not following this example, so maybe the answer to above would be different if I would. What's var and global_var? Are they supposed to be the same thing? If yes, why would that bpf_for() loop fail?

I suspect you are conflating the other pattern I pointed out with:

int cnt = 0;

bpf_for_each(...) {
if (cnt++ > 100)

      break;
}

It's different, as cnt comes from outside the loop and is updated on each iteration. While for

bpf_for(i, 0, var) {
if (i > 100)

        break;
}

it should work fine, as i is originally unknowable, then narrowed to *a range* [0, 99]. But that [0, 99] knowledge is part of "inner loop body" state, so it will still converge as it's going to be basically ignored during the equivalence check on next bpf_iter_num_next() (old state didn't know about i yet).

Quoted 4 lines

Also if start and end are variables they potentially can change between bpf_iter_num_new() and in each iteration of the loop.
__builtin_constant_p() might be too restrictive.

yep, I think so

Quoted 1 line

May be read start/end once, at least?

I can't do that, as for() allows only one type of variables to be defined (note *___p hack as well), so there is no place to remember start/end, unfortunately...

So it's a tradeoff. I can drop range validation, but then every example and lots of production code would be re-checking these conditions.

Quoted 6 lines
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5 -0
+     });                                                                               \
+     /* nothing here  */                                                               \
+)
+#endif /* bpf_for */
+
#25 lore raw

Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros

Quoted 132 lines · Andrii Nakryiko
Quoted 121 lines · Alexei Starovoitov
Quoted 119 lines · Andrii Nakryiko

Add bpf_for_each(), bpf_for() and bpf_repeat() macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer loop would look like:

  int i;
  int arr[N];

  bpf_for(i, 0, N) {
  /* verifier will know that i >= 0 && i < N, so could be used to
   * directly access array elements with no extra checks
   */
   arr[i] = i;
  }

bpf_repeat() is very similar, but it doesn't expose iteration number and is mean as a simple "repeat action N times":

bpf_repeat(N) { /* whatever */ }

Note that break and continue inside the {} block work as expected.

bpf_for_each() is a generalization over any kind of BPF open-coded iterator allowing to use for-each-like approach instead of calling low-level bpf_iter_<type>_{new,next,destroy}() APIs explicitly. E.g.:

struct cgroup *cg;

  bpf_for_each(cgroup, cg, some, input, args) {
      /* do something with each cg */
  }

Would call (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where some, input, args are passed verbatim into constructor as
bpf_iter_cgroup_new(&it, some, input, args).

As a demonstration, add pyperf variant based on bpf_for() loop.

Also clean up few tests that either included bpf_misc.h header unnecessarily from user-space or included it before any common types are defined.

---
 .../bpf/prog_tests/bpf_verif_scale.c          |  6 ++
 .../bpf/prog_tests/uprobe_autoattach.c        |  1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  | 76 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/lsm.c       |  4 +-
 tools/testing/selftests/bpf/progs/pyperf.h    | 14 +++-
 .../selftests/bpf/progs/pyperf600_iter.c      |  7 ++
 .../selftests/bpf/progs/pyperf600_nounroll.c  |  3 -
 7 files changed, 101 insertions(+), 10 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +6 -0
index 5ca252823294..731c343897d8 100644
@@ -144,6 +144,12 @@ void test_verif_scale_pyperf600_nounroll()
      scale_test("pyperf600_nounroll.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_pyperf600_iter()
+{
+     /* open-coded BPF iterator version */
+     scale_test("pyperf600_iter.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_loop1()
 {
      scale_test("loop1.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
tools/testing/selftests/bpf/prog_tests/uprobe_autoattach.c +0 -1
index 6558c857e620..d5b3377aa33c 100644
@@ -3,7 +3,6 @@
 
 #include <test_progs.h>
 #include "test_uprobe_autoattach.skel.h"
-#include "progs/bpf_misc.h"
 
 /* uprobe attach point */
 static noinline int autoattach_trigger_func(int arg1, int arg2, int arg3,
tools/testing/selftests/bpf/progs/bpf_misc.h +26 -0
index f704885aa534..08a791f307a6 100644
@@ -75,5 +75,81 @@
 #define FUNC_REG_ARG_CNT 5
 #endif
 
+struct bpf_iter;
+
+extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym;
+extern int *bpf_iter_num_next(struct bpf_iter *it) __ksym;
+extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym;
+
+#ifndef bpf_for_each
+/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF
+ * open-coded iterators without having to write mundane explicit low-level
+ * loop. Instead, it provides for()-like generic construct that can be used
+ * pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write:
+ *
+ * struct cgroup *cg, *parent_cg = <...>;
+ *
+ * bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) {
+ *     bpf_printk("Child cgroup id = %d", cg->cgroup_id);
+ *     if (cg->cgroup_id == 123)
+ *         break;
+ * }
+ *
+ * I.e., it looks almost like high-level for each loop in other languages,
+ * supports continue/break, and is verifiable by BPF verifier.
+ *
+ * For iterating integers, the difference betwen bpf_for_each(num, i, N, M)
+ * and bpf_for(i, N, M) is in that bpf_for() provides additional proof to
+ * verifier that i is in [N, M) range, and in bpf_for_each() case i is `int
Quoted 8 lines

tools/testing/selftests/bpf/progs/bpf_misc.h line 108

Quoted 5 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5 -0
+ * *`, not just `int`. So for integers bpf_for() is more convenient.
+ */
+#define bpf_for_each(type, cur, args...) for (                                                 \
+     /* initialize and define destructor */                                            \
+     struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))),        \

We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.

Quoted 5 lines

yes, I'll add a comment. I think cleanup attribute isn't standard as well, I'll mention it. This shouldn't be restrictive, though, as we expect very modern Clang (or eventually GCC), which definitely will support all of that. And I feel like most people don't restrict their BPF-side code to strict C89 anyways.

yep. No UX concerns. A comment to manage expectations should be enough.

Quoted 4 lines
Quoted 3 lines

Also what are the rules for attr(cleanup()).
When does it get called?

Quoted 8 lines

From GCC documentation:

Quoted 1 line

The cleanup attribute runs a function when the variable goes out of scope.

So given ___it is bound to for loop, any code path that leads to loop exit (so, when condition turns false or *breaking* out of the loop, which is why I use cleanup, this was a saving grace for this approach to work at all).

+1

Quoted 58 lines
Quoted 2 lines

My understanding that the visibility of ___it is only within for() body.

right

Quoted 5 lines

So when the prog does:
bpf_for(i, 0, 10) sum += i;
bpf_for(i, 0, 10) sum += i;

the compiler should generate bpf_iter_num_destroy right after each bpf_for() ?

Conceptually, yes, but see the note about breaking out of the loop above. How actual assembly code is generated is beyond our control. If the compiler generates multiple separate code paths, each with its own destroy, that's fine as well. No assumptions are made in the verifier, we just need to see one bpf_iter_<type>_destroy() for each instance of iterator.

Quoted 1 line

Or will it group them at the end of function body and destroy all iterators ?

That would be a bug, as documentation states that clean up happens as soon as a variable goes out of scope. Delaying clean up could result in program logic bugs. I.e., we rely on destructors to be called as soon as possible.

Quoted 1 line

Will compiler reuse the stack space used by ___it in case there are multiple bpf_for-s ?

That's the question to compiler developers, but I'd assume that, yes, it should. Why not?

And looking at, for example, iter_pass_iter_ptr_to_subprog which has 4 sequential bpf_for() loops:

0000000000002328 <iter_pass_iter_ptr_to_subprog>:

    1125:       bf a6 00 00 00 00 00 00 r6 = r10
    1126:       07 06 00 00 28 ff ff ff r6 += -216    <-- THIS IS ITER
    1127:       bf 61 00 00 00 00 00 00 r1 = r6
    1128:       b4 02 00 00 00 00 00 00 w2 = 0
    1129:       b4 03 00 00 10 00 00 00 w3 = 16
    1130:       85 10 00 00 ff ff ff ff call -1
                0000000000002350:  R_BPF_64_32  bpf_iter_num_new
    1131:       bf a7 00 00 00 00 00 00 r7 = r10
    1132:       07 07 00 00 c0 ff ff ff r7 += -64
    1133:       bf 61 00 00 00 00 00 00 r1 = r6
    1134:       bf 72 00 00 00 00 00 00 r2 = r7
    1135:       b4 03 00 00 10 00 00 00 w3 = 16
    1136:       b4 04 00 00 02 00 00 00 w4 = 2
    1137:       85 10 00 00 53 00 00 00 call 83
                0000000000002388:  R_BPF_64_32  .text
    1138:       bf 61 00 00 00 00 00 00 r1 = r6
    1139:       85 10 00 00 ff ff ff ff call -1
                0000000000002398:  R_BPF_64_32  bpf_iter_num_destroy
    1140:       bf 61 00 00 00 00 00 00 r1 = r6     <<--- HERE WE REUSE
    1141:       b4 02 00 00 00 00 00 00 w2 = 0
    1142:       b4 03 00 00 20 00 00 00 w3 = 32
    1143:       85 10 00 00 ff ff ff ff call -1
                00000000000023b8:  R_BPF_64_32  bpf_iter_num_new
Quoted 2 lines

Note that r6 is set to fp-216 and is just reused as is for second bpf_for loop (second bpf_iter_num_new) call.

Great. Thanks for checking. I was worried that attr(cleanup) will force compiler to think that different objects cannot reuse the stack slots which will lead to stack exhaustion. Especially with 24-bytes bpf_iter-s and our tiny 512 limit.

Quoted 44 lines
Quoted 23 lines
Quoted 23 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +22 -0
+     /* ___p pointer is just to call bpf_iter_##type##_new() *once* to init ___it */   \
+                     *___p = (bpf_iter_##type##_new(&___it, ##args),           \
+     /* this is a workaround for Clang bug: it currently doesn't emit BTF */           \
+     /* for bpf_iter_##type##_destroy when used from cleanup() attribute */            \
+                             (void)bpf_iter_##type##_destroy, (void *)0);              \
+     /* iteration and termination check */                                             \
+     ((cur = bpf_iter_##type##_next(&___it)));                                         \
+     /* nothing here  */                                                               \
+)
+#endif /* bpf_for_each */
+
+#ifndef bpf_for
+/* bpf_for(i, start, end) proves to verifier that i is in [start, end) */
+#define bpf_for(i, start, end) for (                                                   \
+     /* initialize and define destructor */                                            \
+     struct bpf_iter ___it __attribute__((cleanup(bpf_iter_num_destroy))),             \
+     /* ___p pointer is necessary to call bpf_iter_num_new() *once* to init ___it */   \
+                     *___p = (bpf_iter_num_new(&___it, (start), (end)),                \
+     /* this is a workaround for Clang bug: it currently doesn't emit BTF */           \
+     /* for bpf_iter_num_destroy when used from cleanup() attribute */                 \
+                             (void)bpf_iter_num_destroy, (void *)0);                   \
+     ({                                                                                \
Quoted 8 lines

tools/testing/selftests/bpf/progs/bpf_misc.h line 134

Quoted 4 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +4 -0
+             /* iteration step */                                                      \
+             int *___t = bpf_iter_num_next(&___it);                                    \
+             /* termination and bounds check */                                        \
+             (___t && ((i) = *___t, i >= (start) && i < (end)));                       \

The i >= (start) && i < (end) is necessary to make sure that the verifier tightens the range of 'i' inside the body of the loop and
when the program does arr[i] access the verifier will know that 'i' is within bounds, right?

yes, it feels like a common pattern, but I was contemplating to add bpf_for_uncheck() where we "expose" i value, but don't do check. I decided to keep it simple, as most examples actually required bounds checks anyways. And for cases where we don't, often bpf_repeat() suffices. One other way would be to expose i from bpf_repeat(), just no checks.

One restriction with this approach is that I can't define both struct bpf_iter __it and int i inside for loop, so cur/i has to be declared and passed into bpf_for/bpf_for_each by user explicitly. So for bpf_repeat() to expose i would require always doing:

Quoted 6 lines

int i;

bpf_repeat(i, 100) { /* i is set to 0, 1, ..., 99 */ }

which, if you don't care about iteration number, is a bit of waste. So don't know, I'm undecided on bpf_repeat with i.

It feels that the proposed bpf_repeat() without 'i' is cleaner.

Quoted 7 lines
Quoted 2 lines

In such case should we add __builtin_constant_p() check for 'start' and 'end' ?

that seems to defy the purpose, as if you know start/end statically, you might as well just write either unrolled loop or bounded for() loop

Quoted 8 lines
Quoted 4 lines

int arr[100];
if (var < 100)
bpf_for(i, 0, global_var) sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.

but I'm not following this example, so maybe the answer to above would be different if I would. What's var and global_var?

typo. I meant the same var in both places.

Quoted 31 lines

Are they supposed
to be the same thing? If yes, why would that bpf_for() loop fail?

I suspect you are conflating the other pattern I pointed out with:

int cnt = 0;

bpf_for_each(...) {
   if (cnt++ > 100)
      break;
}

It's different, as cnt comes from outside the loop and is updated on each iteration. While for

bpf_for(i, 0, var) {
   if (i > 100)
        break;
}

it should work fine, as i is originally unknowable, then narrowed to *a range* [0, 99]. But that [0, 99] knowledge is part of "inner loop body" state, so it will still converge as it's going to be basically ignored during the equivalence check on next bpf_iter_num_next() (old state didn't know about i yet).

Quoted 4 lines

Also if start and end are variables they potentially can change between bpf_iter_num_new() and in each iteration of the loop.
__builtin_constant_p() might be too restrictive.

Quoted 7 lines

yep, I think so

Quoted 1 line

May be read start/end once, at least?

I can't do that, as for() allows only one type of variables to be defined (note *___p hack as well), so there is no place to remember start/end, unfortunately...

I see. Abusing bpf_iter like:
for (struct bpf_iter_num __it, *___p, start_end = (struct bpf_iter_num) {start, end}; is probably too ugly just to READ_ONCE(start).
Especially since bpf_iter_num is opaque.

Please add a comment to warn users that if start/end are variables they better not change during bpf_for().
I guess plain C loop: for (int i = 0; i < j; i++) will go crazy too if 'j' changes. I'm not sure what standard says here.
Whether compiler has to reload 'j' every iteration or not.

Quoted 3 lines

So it's a tradeoff. I can drop range validation, but then every example and lots of production code would be re-checking these conditions.

Understood. Keep it as-is.

Quoted 3 lines
Quoted 3 lines

tools/testing/selftests/bpf/progs/bpf_misc.h line 136

Quoted 3 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +2 -0
+     });                                                                               \
+     /* nothing here  */                                                               \

btw that 'nothing here' comment is distracting when reading this macro.

#26 lore raw

Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros

Quoted 134 lines · Alexei Starovoitov
Quoted 132 lines · Andrii Nakryiko
Quoted 129 lines · Alexei Starovoitov
Quoted 114 lines · Andrii Nakryiko

Add bpf_for_each(), bpf_for() and bpf_repeat() macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer loop would look like:

  int i;
  int arr[N];

  bpf_for(i, 0, N) {
  /* verifier will know that i >= 0 && i < N, so could be used to
   * directly access array elements with no extra checks
   */
   arr[i] = i;
  }

bpf_repeat() is very similar, but it doesn't expose iteration number and is mean as a simple "repeat action N times":

bpf_repeat(N) { /* whatever */ }

Note that break and continue inside the {} block work as expected.

bpf_for_each() is a generalization over any kind of BPF open-coded iterator allowing to use for-each-like approach instead of calling low-level bpf_iter_<type>_{new,next,destroy}() APIs explicitly. E.g.:

struct cgroup *cg;

  bpf_for_each(cgroup, cg, some, input, args) {
      /* do something with each cg */
  }

Would call (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where some, input, args are passed verbatim into constructor as
bpf_iter_cgroup_new(&it, some, input, args).

As a demonstration, add pyperf variant based on bpf_for() loop.

Also clean up few tests that either included bpf_misc.h header unnecessarily from user-space or included it before any common types are defined.

---
 .../bpf/prog_tests/bpf_verif_scale.c          |  6 ++
 .../bpf/prog_tests/uprobe_autoattach.c        |  1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  | 76 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/lsm.c       |  4 +-
 tools/testing/selftests/bpf/progs/pyperf.h    | 14 +++-
 .../selftests/bpf/progs/pyperf600_iter.c      |  7 ++
 .../selftests/bpf/progs/pyperf600_nounroll.c  |  3 -
 7 files changed, 101 insertions(+), 10 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +6 -0
index 5ca252823294..731c343897d8 100644
@@ -144,6 +144,12 @@ void test_verif_scale_pyperf600_nounroll()
      scale_test("pyperf600_nounroll.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_pyperf600_iter()
+{
+     /* open-coded BPF iterator version */
+     scale_test("pyperf600_iter.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_loop1()
 {
      scale_test("loop1.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
tools/testing/selftests/bpf/prog_tests/uprobe_autoattach.c +0 -1
index 6558c857e620..d5b3377aa33c 100644
@@ -3,7 +3,6 @@
 
 #include <test_progs.h>
 #include "test_uprobe_autoattach.skel.h"
-#include "progs/bpf_misc.h"
 
 /* uprobe attach point */
 static noinline int autoattach_trigger_func(int arg1, int arg2, int arg3,
tools/testing/selftests/bpf/progs/bpf_misc.h +21 -0
index f704885aa534..08a791f307a6 100644
@@ -75,5 +75,81 @@
 #define FUNC_REG_ARG_CNT 5
 #endif
 
+struct bpf_iter;
+
+extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym;
+extern int *bpf_iter_num_next(struct bpf_iter *it) __ksym;
+extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym;
+
+#ifndef bpf_for_each
+/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF
+ * open-coded iterators without having to write mundane explicit low-level
+ * loop. Instead, it provides for()-like generic construct that can be used
+ * pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write:
+ *
+ * struct cgroup *cg, *parent_cg = <...>;
+ *
+ * bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) {
+ *     bpf_printk("Child cgroup id = %d", cg->cgroup_id);
+ *     if (cg->cgroup_id == 123)
+ *         break;
+ * }
+ *
+ * I.e., it looks almost like high-level for each loop in other languages,

tools/testing/selftests/bpf/progs/bpf_misc.h line 108

Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +10 -0
+ * supports continue/break, and is verifiable by BPF verifier.
+ *
+ * For iterating integers, the difference betwen bpf_for_each(num, i, N, M)
+ * and bpf_for(i, N, M) is in that bpf_for() provides additional proof to
+ * verifier that i is in [N, M) range, and in bpf_for_each() case i is `int
+ * *`, not just `int`. So for integers bpf_for() is more convenient.
+ */
+#define bpf_for_each(type, cur, args...) for (                                                 \
+     /* initialize and define destructor */                                            \
+     struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))),        \

We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.

Quoted 8 lines
Quoted 5 lines

yes, I'll add a comment. I think cleanup attribute isn't standard as well, I'll mention it. This shouldn't be restrictive, though, as we expect very modern Clang (or eventually GCC), which definitely will support all of that. And I feel like most people don't restrict their BPF-side code to strict C89 anyways.

yep. No UX concerns. A comment to manage expectations should be enough.

added

Quoted 33 lines
Quoted 4 lines
Quoted 3 lines

Also what are the rules for attr(cleanup()).
When does it get called?

Quoted 8 lines

From GCC documentation:

Quoted 1 line

The cleanup attribute runs a function when the variable goes out of scope.

So given ___it is bound to for loop, any code path that leads to loop exit (so, when condition turns false or *breaking* out of the loop, which is why I use cleanup, this was a saving grace for this approach to work at all).

+1

Quoted 18 lines
Quoted 2 lines

My understanding that the visibility of ___it is only within for() body.

right

Quoted 5 lines

So when the prog does:
bpf_for(i, 0, 10) sum += i;
bpf_for(i, 0, 10) sum += i;

the compiler should generate bpf_iter_num_destroy right after each bpf_for() ?

Conceptually, yes, but see the note about breaking out of the loop above. How actual assembly code is generated is beyond our control. If the compiler generates multiple separate code paths, each with its own destroy, that's fine as well. No assumptions are made in the verifier, we just need to see one bpf_iter_<type>_destroy() for each instance of iterator.

[...]

Quoted 5 lines
Quoted 5 lines

One restriction with this approach is that I can't define both struct bpf_iter __it and int i inside for loop, so cur/i has to be declared and passed into bpf_for/bpf_for_each by user explicitly. So for bpf_repeat() to expose i would require always doing:

Quoted 9 lines
Quoted 6 lines

int i;

bpf_repeat(i, 100) { /* i is set to 0, 1, ..., 99 */ }

which, if you don't care about iteration number, is a bit of waste. So don't know, I'm undecided on bpf_repeat with i.

It feels that the proposed bpf_repeat() without 'i' is cleaner.

agreed, I'm keeping it as is

Quoted 13 lines
Quoted 13 lines
Quoted 2 lines

In such case should we add __builtin_constant_p() check for 'start' and 'end' ?

that seems to defy the purpose, as if you know start/end statically, you might as well just write either unrolled loop or bounded for() loop

Quoted 4 lines

int arr[100];
if (var < 100)
bpf_for(i, 0, global_var) sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.

[...]

Quoted 9 lines
Quoted 4 lines

I can't do that, as for() allows only one type of variables to be defined (note *___p hack as well), so there is no place to remember start/end, unfortunately...

I see. Abusing bpf_iter like:
for (struct bpf_iter_num __it, *___p, start_end = (struct bpf_iter_num) {start, end}; is probably too ugly just to READ_ONCE(start).
Especially since bpf_iter_num is opaque.

yeah, that seems like too much

Quoted 6 lines

Please add a comment to warn users that if start/end are variables they better not change during bpf_for().
I guess plain C loop: for (int i = 0; i < j; i++) will go crazy too if 'j' changes. I'm not sure what standard says here.
Whether compiler has to reload 'j' every iteration or not.

no idea, but yep, will add a comment

Quoted 5 lines
Quoted 4 lines

So it's a tradeoff. I can drop range validation, but then every example and lots of production code would be re-checking these conditions.

Quoted 7 lines

Understood. Keep it as-is.

Quoted 3 lines
Quoted 3 lines

tools/testing/selftests/bpf/progs/bpf_misc.h

Quoted 3 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +2 -0
+     });                                                                               \
+     /* nothing here  */                                                               \

btw that 'nothing here' comment is distracting when reading this macro.

ok, dropped this

author maintainer
#27 lore raw

PATCH 16/17 selftests/bpf: add iterators tests

In reply to Andrii Nakryiko

Add various tests for open-coded iterators. Some of them excercise various possible coding patterns in C, some go down to low-level assembly for more control over various conditions.

We also make use of bpf_for(), bpf_for_each(), bpf_repeat() macros.

---
 .../testing/selftests/bpf/prog_tests/iters.c  |  15 +
 tools/testing/selftests/bpf/progs/bpf_misc.h  |   1 +
 tools/testing/selftests/bpf/progs/iters.c     | 720 ++++++++++++++++++
 .../selftests/bpf/progs/iters_looping.c       | 163 ++++
 .../selftests/bpf/progs/iters_state_safety.c  | 455 +++++++++++
 5 files changed, 1354 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/iters.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_looping.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_state_safety.c
tools/testing/selftests/bpf/prog_tests/iters.c new file +15 -0
new file mode 100644
index 000000000000..414fb8d82145
@@ -0,0 +1,15 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */
+
+#include <test_progs.h>
+
+#include "iters.skel.h"
+#include "iters_state_safety.skel.h"
+#include "iters_looping.skel.h"
+
+void test_iters(void)
+{
+	RUN_TESTS(iters_state_safety);
+	RUN_TESTS(iters_looping);
+	RUN_TESTS(iters);
+}
tools/testing/selftests/bpf/progs/bpf_misc.h +1 -0
index 08a791f307a6..955c09e67abb 100644
@@ -36,6 +36,7 @@
 #define __clobber_common "r0", "r1", "r2", "r3", "r4", "r5", "memory"
 #define __imm(name) [name]"i"(name)
 #define __imm_addr(name) [name]"i"(&name)
+#define __imm_ptr(name) [name]"p"(&name)
 
 #if defined(__TARGET_ARCH_x86)
 #define SYSCALL_WRAPPER 1
tools/testing/selftests/bpf/progs/iters.c new file +720 -0

720 lines not on this page · raw message

tools/testing/selftests/bpf/progs/iters_looping.c new file +163 -0

163 lines not on this page · raw message

tools/testing/selftests/bpf/progs/iters_state_safety.c new file +455 -0

455 lines not on this page · raw message

Signature · 1 line
2.30.2
#28 lore raw

Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests

Review

Quoted 2 lines · Andrii Nakryiko
(quoted diff) +2 -0
+
+#ifdef REAL_TEST

Looks like REAL_TEST is never set.

and all bpf_printk-s in tests are never executed, because the test are 'load-only' to check the verifier?

It looks like all of them can be run (once printks are removed and converted to if-s). That would nicely complement patch 17 runners.

It can be a follow up, of course.

Great stuff overall!

#29 lore raw

Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests

Quoted 7 lines · Alexei Starovoitov

Review

Quoted 2 lines · Andrii Nakryiko
(quoted diff) +2 -0
+
+#ifdef REAL_TEST

Looks like REAL_TEST is never set.

Quoted 6 lines

and all bpf_printk-s in tests are never executed, because the test are 'load-only' to check the verifier?

It looks like all of them can be run (once printks are removed and converted to if-s). That would nicely complement patch 17 runners.

Yes, it's a bit sloppy. I used these also as manual tests during development. I did have an ad-hoc test that attaches and triggers these programs. And I just manually looked at printk output in trace_pipe to confirm it does actually work as expected.

And I felt sorry to drop all that, so just added that REAL_TEST hack to make program code simpler (no extra states for those pid conditions), it was simpler to debug verification failures, less states to consider.

I did try to quickly extend RUN_TESTS with the ability to specify a callback that will be called on success, but it's not trivial if we want to preserve skeletons, so I abandoned that effort, trying to save a bit of time. I still want to have RUN_TESTS with ability to specify callback in the form of:

static void on_success(struct <my_skeleton_type> *skel, struct

bpf_program *prog) {
    ...
}

but it needs more thought and macro magic (or something else), so I postponed it and wrote simple number iterator tests in patch #17.

Quoted 1 line

It can be a follow up, of course.

yep, let's keep bpf_printks, as they currently serve as consumers of variables, preventing the compiler from optimizing loops too much. This shouldn't be a problem for verification-only kind of tests. And then with RUN_TESTS() additions, we can actually start executing this.

Quoted 2 lines

Great stuff overall!

Thanks!

#30 lore raw

Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests

Quoted 32 lines · Andrii Nakryiko
Quoted 7 lines · Alexei Starovoitov

Review

Quoted 2 lines · Andrii Nakryiko
(quoted diff) +2 -0
+
+#ifdef REAL_TEST

Looks like REAL_TEST is never set.

Quoted 6 lines

and all bpf_printk-s in tests are never executed, because the test are 'load-only' to check the verifier?

It looks like all of them can be run (once printks are removed and converted to if-s). That would nicely complement patch 17 runners.

Yes, it's a bit sloppy. I used these also as manual tests during development. I did have an ad-hoc test that attaches and triggers these programs. And I just manually looked at printk output in trace_pipe to confirm it does actually work as expected.

And I felt sorry to drop all that, so just added that REAL_TEST hack to make program code simpler (no extra states for those pid conditions), it was simpler to debug verification failures, less states to consider.

I did try to quickly extend RUN_TESTS with the ability to specify a callback that will be called on success, but it's not trivial if we want to preserve skeletons, so I abandoned that effort, trying to save a bit of time. I still want to have RUN_TESTS with ability to specify callback in the form of:

Quoted 7 lines

static void on_success(struct <my_skeleton_type> *skel, struct

bpf_program *prog) {
    ...
}

but it needs more thought and macro magic (or something else), so I postponed it and wrote simple number iterator tests in patch #17.

Sounds good to me. Follow up is fine.

Quoted 6 lines
Quoted 1 line

It can be a follow up, of course.

yep, let's keep bpf_printks, as they currently serve as consumers of variables, preventing the compiler from optimizing loops too much. This shouldn't be a problem for verification-only kind of tests. And then with RUN_TESTS() additions, we can actually start executing this.

+1

#31 lore raw

Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests

In reply to Andrii Nakryiko

On Thu, Mar 02, 2023 at 03:50:14PM -0800, Andrii Nakryiko wrote:

SNIP

Quoted 26 lines
tools/testing/selftests/bpf/progs/iters.c new file +26 -0
+
+SEC("raw_tp")
+__success
+int iter_pass_iter_ptr_to_subprog(const void *ctx)
+{
+	int arr1[16], arr2[32];
+	struct bpf_iter it;
+	int n, sum1, sum2;
+
+	MY_PID_GUARD();
+
+	/* fill arr1 */
+	n = ARRAY_SIZE(arr1);
+	bpf_iter_num_new(&it, 0, n);
+	fill(&it, arr1, n, 2);
+	bpf_iter_num_destroy(&it);
+
+	/* fill arr2 */
+	n = ARRAY_SIZE(arr2);
+	bpf_iter_num_new(&it, 0, n);
+	fill(&it, arr2, n, 10);
+	bpf_iter_num_destroy(&it);
+
+	/* sum arr1 */
+	n = ARRAY_SIZE(arr1);
+	bpf_iter_num_new(&it, 0, n);

tools/testing/selftests/bpf/progs/iters.c line 715

Quoted 10 lines
tools/testing/selftests/bpf/progs/iters.c new file +10 -0
+	sum1 = sum(&it, arr1, n);
+	bpf_iter_num_destroy(&it);
+
+	/* sum arr2 */
+	n = ARRAY_SIZE(arr2);
+	bpf_iter_num_new(&it, 0, n);
+	sum1 = sum(&it, arr2, n);
+	bpf_iter_num_destroy(&it);
+
+	bpf_printk("sum1=%d, sum2=%d", sum1, sum2);

got to remove this to compile it, debug leftover?

jirka

Quoted 5 lines
tools/testing/selftests/bpf/progs/iters.c new file +5 -0
+
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";

SNIP

#32 lore raw

Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests

Quoted 30 lines · Jiri Olsa

On Thu, Mar 02, 2023 at 03:50:14PM -0800, Andrii Nakryiko wrote:

SNIP

Quoted 25 lines
tools/testing/selftests/bpf/progs/iters.c new file +25 -0
+
+SEC("raw_tp")
+__success
+int iter_pass_iter_ptr_to_subprog(const void *ctx)
+{
+     int arr1[16], arr2[32];
+     struct bpf_iter it;
+     int n, sum1, sum2;
+
+     MY_PID_GUARD();
+
+     /* fill arr1 */
+     n = ARRAY_SIZE(arr1);
+     bpf_iter_num_new(&it, 0, n);
+     fill(&it, arr1, n, 2);
+     bpf_iter_num_destroy(&it);
+
+     /* fill arr2 */
+     n = ARRAY_SIZE(arr2);
+     bpf_iter_num_new(&it, 0, n);
+     fill(&it, arr2, n, 10);
+     bpf_iter_num_destroy(&it);
+
+     /* sum arr1 */
+     n = ARRAY_SIZE(arr1);
Quoted 8 lines

tools/testing/selftests/bpf/progs/iters.c line 712

Quoted 8 lines
tools/testing/selftests/bpf/progs/iters.c new file +8 -0
+     bpf_iter_num_new(&it, 0, n);
+     sum1 = sum(&it, arr1, n);
+     bpf_iter_num_destroy(&it);
+
+     /* sum arr2 */
+     n = ARRAY_SIZE(arr2);
+     bpf_iter_num_new(&it, 0, n);
+     sum1 = sum(&it, arr2, n);

this should have been sum2, not sum1, mechanical mistake

Quoted 5 lines

tools/testing/selftests/bpf/progs/iters.c line 715

Quoted 3 lines
tools/testing/selftests/bpf/progs/iters.c new file +3 -0
+     bpf_iter_num_destroy(&it);
+
+     bpf_printk("sum1=%d, sum2=%d", sum1, sum2);

got to remove this to compile it, debug leftover?

nope, sum1->sum2 typo, which wasn't caught because Dave's patch to error out on uninitialized variable reads landed a bit later

I'll fix this in v2, of course.

Quoted 10 lines

jirka

Quoted 5 lines
tools/testing/selftests/bpf/progs/iters.c new file +5 -0
+
+     return 0;
+}
+
+char _license[] SEC("license") = "GPL";

SNIP

author maintainer
#33 lore raw

PATCH 17/17 selftests/bpf: add number iterator tests

In reply to Andrii Nakryiko

Add number iterator (bpf_iter_num_{new,next,destroy}()) specific tests, validating its correct handling of various corner cases *at runtime*.

---
 .../testing/selftests/bpf/prog_tests/iters.c  |  47 ++++
 tools/testing/selftests/bpf/progs/iters_num.c | 242 ++++++++++++++++++
 2 files changed, 289 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/iters_num.c
tools/testing/selftests/bpf/prog_tests/iters.c +47 -0
index 414fb8d82145..d467f49dcf9b 100644
@@ -6,10 +6,57 @@
 #include "iters.skel.h"
 #include "iters_state_safety.skel.h"
 #include "iters_looping.skel.h"
+#include "iters_num.skel.h"
+
+static void subtest_num_iters(void)
+{
+	struct iters_num *skel;
+	int err;
+
+	skel = iters_num__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel_open_and_load"))
+		return;
+
+	err = iters_num__attach(skel);
+	if (!ASSERT_OK(err, "skel_attach"))
+		goto cleanup;
+
+	usleep(1);
+	iters_num__detach(skel);
+
+#define VALIDATE_CASE(case_name)					\
+	ASSERT_EQ(skel->bss->res_##case_name,				\
+		  skel->rodata->exp_##case_name,			\
+		  #case_name)
+
+	VALIDATE_CASE(empty_zero);
+	VALIDATE_CASE(empty_int_min);
+	VALIDATE_CASE(empty_int_max);
+	VALIDATE_CASE(empty_minus_one);
+
+	VALIDATE_CASE(simple_sum);
+	VALIDATE_CASE(neg_sum);
+	VALIDATE_CASE(very_neg_sum);
+	VALIDATE_CASE(neg_pos_sum);
+
+	VALIDATE_CASE(invalid_range);
+	VALIDATE_CASE(max_range);
+	VALIDATE_CASE(e2big_range);
+
+	VALIDATE_CASE(succ_elem_cnt);
+	VALIDATE_CASE(overfetched_elem_cnt);
+	VALIDATE_CASE(fail_elem_cnt);
+
+cleanup:
+	iters_num__destroy(skel);
+}
 
 void test_iters(void)
 {
 	RUN_TESTS(iters_state_safety);
 	RUN_TESTS(iters_looping);
 	RUN_TESTS(iters);
+
+	if (test__start_subtest("num"))
+		subtest_num_iters();
 }
tools/testing/selftests/bpf/progs/iters_num.c new file +242 -0

242 lines not on this page · raw message

Signature · 1 line
2.30.2
#34 lore raw
In reply to Andrii Nakryiko
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 4 lines · On Thu, 2 Mar 2023 15:49:58 -0800 you wrote:

Add support for open-coded (aka inline) iterators in BPF world. This is a next evolution of gradually allowing more powerful and less restrictive looping and iteration capabilities to BPF programs.

Quoted 8 lines

We set up a framework for implementing all kinds of iterators (e.g., cgroup, task, file, etc, iterators), but this patch set only implements numbers iterator, which is used to implement ergonomic bpf_for() for-like construct (see patch #15). We also add bpf_for_each(), which is a generic foreach-like construct that will work with any kind of open-coded iterator implementation, as long as we stick with bpf_iter_<type>_{new,next,destroy}() naming pattern.

[...]

Here is the summary with links:
- [bpf-next,01/17] bpf: improve stack slot state printing

    https://git.kernel.org/bpf/bpf-next/c/d54e0f6c1adf
  - [bpf-next,02/17] bpf: improve regsafe() checks for PTR_TO_{MEM,BUF,TP_BUFFER}
    https://git.kernel.org/bpf/bpf-next/c/567da5d253cd
  - [bpf-next,03/17] selftests/bpf: enhance align selftest's expected log matching
    https://git.kernel.org/bpf/bpf-next/c/6f876e75d316
  - [bpf-next,04/17] bpf: honor env->test_state_freq flag in is_state_visited()
    https://git.kernel.org/bpf/bpf-next/c/98ddcf389d1b
  - [bpf-next,05/17] selftests/bpf: adjust log_fixup's buffer size for proper truncation
    https://git.kernel.org/bpf/bpf-next/c/fffc893b6bf2
  - [bpf-next,06/17] bpf: clean up visit_insn()'s instruction processing
    https://git.kernel.org/bpf/bpf-next/c/653ae3a874ac
  - [bpf-next,07/17] bpf: fix visit_insn()'s detection of BPF_FUNC_timer_set_callback helper
    https://git.kernel.org/bpf/bpf-next/c/c1ee85a9806a
  - [bpf-next,08/17] bpf: ensure that r0 is marked scratched after any function call
    https://git.kernel.org/bpf/bpf-next/c/553a64a85c5d
  - [bpf-next,09/17] bpf: move kfunc_call_arg_meta higher in the file
    https://git.kernel.org/bpf/bpf-next/c/d0e1ac227945
  - [bpf-next,10/17] bpf: mark PTR_TO_MEM as non-null register type
    https://git.kernel.org/bpf/bpf-next/c/d5271c5b1950
  - [bpf-next,11/17] bpf: generalize dynptr_get_spi to be usable for iters
    https://git.kernel.org/bpf/bpf-next/c/a461f5adf177
  - [bpf-next,12/17] bpf: add support for fixed-size memory pointer returns for kfuncs
    https://git.kernel.org/bpf/bpf-next/c/f4b4eee6169b

- [bpf-next,13/17] bpf: add support for open-coded iterator loops
(no matching commit)
- [bpf-next,14/17] bpf: implement number iterator
(no matching commit)
- [bpf-next,15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros (no matching commit)
- [bpf-next,16/17] selftests/bpf: add iterators tests
(no matching commit)
- [bpf-next,17/17] selftests/bpf: add number iterator tests
(no matching commit)

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html