Skip to contentSkip to conversation

BPF open-coded iterators

PATCH Superseded Andrii Nakryiko 3 participants 12 messages Mar 7, 2023

Subsystems (6)

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

v2 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 patches #4-#5). 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 (which we now enforce on the kernel side).

Patch #1 is preparatory refactoring for easier way to check for special kfunc calls. Patch #2 is adding iterator kfunc registration and validation logic, which is mostly independent from the rest of open-coded iterator logic, so is separated out for easier reviewing.

The meat of verifier-side logic is in patch #3. Patch #4 implements numbers iterator. I kept them separate to have clean reference for how to integrate new iterator types (now even simpler to do than in v1 of this patch set). Patch #5 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 #6 is verification tests, based on numbers iterator (as the only available right now). Patch #7 actually tests runtime behavior of numbers iterator.

Finally, with changes in v2, it's possible and trivial to implement custom iterators completely in kernel modules, which we showcase and test by adding a simple iterator returning same number a given number of times to bpf_testmod. Patch #8 is where all this happens and is tested.

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

v1->v2:
- rebased on latest, dropping previously landed preparatory patches;
- each iterator type now have its own struct bpf_iter_<type> which allows each iterator implementation to use exactly as much stack space as necessary, allowing to avoid runtime allocations (Alexei);
- reworked how iterator kfuncs are defined, no verifier changes are required

    when adding new iterator type;

- added bpf_testmod-based iterator implementation;
- address the rest of feedback, comments, commit message adjustment, etc.

Cc Tejun Heo <[email protected]>

Andrii Nakryiko (8):
bpf: factor out fetching basic kfunc metadata
bpf: add iterator kfuncs registration and validation logic
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
selftests/bpf: implement and test custom testmod_seq iterator

 include/linux/bpf.h                           |   8 +-
 include/linux/bpf_verifier.h                  |  27 +-
 include/linux/btf.h                           |   4 +
 include/uapi/linux/bpf.h                      |   8 +
 kernel/bpf/bpf_iter.c                         |  70 ++
 kernel/bpf/btf.c                              | 112 ++-
 kernel/bpf/helpers.c                          |   3 +
 kernel/bpf/verifier.c                         | 693 ++++++++++++++++-
 tools/include/uapi/linux/bpf.h                |   8 +
 .../selftests/bpf/bpf_testmod/bpf_testmod.c   |  42 +-
 .../selftests/bpf/bpf_testmod/bpf_testmod.h   |   6 +
 .../bpf/prog_tests/bpf_verif_scale.c          |   6 +
 .../testing/selftests/bpf/prog_tests/iters.c  | 106 +++
 .../bpf/prog_tests/uprobe_autoattach.c        |   1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  | 100 +++
 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  | 426 +++++++++++
 .../selftests/bpf/progs/iters_testmod_seq.c   |  79 ++
 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 -
 24 files changed, 2796 insertions(+), 56 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/iters_testmod_seq.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
Signature · 1 line
2.34.1
author maintainer
#1 lore raw

PATCH v2 1/8 bpf: factor out fetching basic kfunc metadata

Factor out logic to fetch basic kfunc metadata based on struct bpf_insn. This is not exactly short or trivial code to just copy/paste, and this information is sometimes necessary in other parts of verifier logic. Subsequent patches will rely on this to determine if an instruction is a kfunc call to iterator next method.

No functional changes intended, including that verbose() warning behavior when kfunc is not allowed for a particular program type.

---
 kernel/bpf/verifier.c | 92 +++++++++++++++++++++++++++----------------
 1 file changed, 59 insertions(+), 33 deletions(-)
kernel/bpf/verifier.c +59 -33
index b2116ca78d9a..8d40fba6a1c0 100644
@@ -10079,24 +10079,21 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 	return 0;
 }
 
-static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
-			    int *insn_idx_p)
+static int fetch_kfunc_meta(struct bpf_verifier_env *env,
+			    struct bpf_insn *insn,
+			    struct bpf_kfunc_call_arg_meta *meta,
+			    const char **kfunc_name)
 {
-	const struct btf_type *t, *func, *func_proto, *ptr_type;
-	u32 i, nargs, func_id, ptr_type_id, release_ref_obj_id;
-	struct bpf_reg_state *regs = cur_regs(env);
-	const char *func_name, *ptr_type_name;
-	bool sleepable, rcu_lock, rcu_unlock;
-	struct bpf_kfunc_call_arg_meta meta;
-	int err, insn_idx = *insn_idx_p;
-	const struct btf_param *args;
-	const struct btf_type *ret_t;
+	const struct btf_type *func, *func_proto;
+	u32 func_id, *kfunc_flags;
+	const char *func_name;
 	struct btf *desc_btf;
-	u32 *kfunc_flags;
 
-	/* skip for now, but return error when we find this in fixup_kfunc_call */
+	if (kfunc_name)
+		*kfunc_name = NULL;
+
 	if (!insn->imm)
-		return 0;
+		return -EINVAL;
 
 	desc_btf = find_kfunc_desc_btf(env, insn->off);
 	if (IS_ERR(desc_btf))
@@ -10105,22 +10102,51 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	func_id = insn->imm;
 	func = btf_type_by_id(desc_btf, func_id);
 	func_name = btf_name_by_offset(desc_btf, func->name_off);
+	if (kfunc_name)
+		*kfunc_name = func_name;
 	func_proto = btf_type_by_id(desc_btf, func->type);
 
 	kfunc_flags = btf_kfunc_id_set_contains(desc_btf, resolve_prog_type(env->prog), func_id);
 	if (!kfunc_flags) {
-		verbose(env, "calling kernel function %s is not allowed\n",
-			func_name);
 		return -EACCES;
 	}
 
-	/* Prepare kfunc call metadata */
-	memset(&meta, 0, sizeof(meta));
-	meta.btf = desc_btf;
-	meta.func_id = func_id;
-	meta.kfunc_flags = *kfunc_flags;
-	meta.func_proto = func_proto;
-	meta.func_name = func_name;
+	memset(meta, 0, sizeof(*meta));
+	meta->btf = desc_btf;
+	meta->func_id = func_id;
+	meta->kfunc_flags = *kfunc_flags;
+	meta->func_proto = func_proto;
+	meta->func_name = func_name;
+
+	return 0;
+}
+
+static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			    int *insn_idx_p)
+{
+	const struct btf_type *t, *ptr_type;
+	u32 i, nargs, ptr_type_id, release_ref_obj_id;
+	struct bpf_reg_state *regs = cur_regs(env);
+	const char *func_name, *ptr_type_name;
+	bool sleepable, rcu_lock, rcu_unlock;
+	struct bpf_kfunc_call_arg_meta meta;
+	struct bpf_insn_aux_data *insn_aux;
+	int err, insn_idx = *insn_idx_p;
+	const struct btf_param *args;
+	const struct btf_type *ret_t;
+	struct btf *desc_btf;
+
+	/* skip for now, but return error when we find this in fixup_kfunc_call */
+	if (!insn->imm)
+		return 0;
+
+	err = fetch_kfunc_meta(env, insn, &meta, &func_name);
+	if (err == -EACCES && func_name)
+		verbose(env, "calling kernel function %s is not allowed\n", func_name);
+	if (err)
+		return err;
+	desc_btf = meta.btf;
+	insn_aux = &env->insn_aux_data[insn_idx];
 
 	if (is_kfunc_destructive(&meta) && !capable(CAP_SYS_BOOT)) {
 		verbose(env, "destructive kfunc calls require CAP_SYS_BOOT capability\n");
@@ -10173,7 +10199,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		err = release_reference(env, regs[meta.release_regno].ref_obj_id);
 		if (err) {
 			verbose(env, "kfunc %s#%d reference has not been acquired before\n",
-				func_name, func_id);
+				func_name, meta.func_id);
 			return err;
 		}
 	}
@@ -10185,14 +10211,14 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		err = ref_convert_owning_non_owning(env, release_ref_obj_id);
 		if (err) {
 			verbose(env, "kfunc %s#%d conversion of owning ref to non-owning failed\n",
-				func_name, func_id);
+				func_name, meta.func_id);
 			return err;
 		}
 
 		err = release_reference(env, release_ref_obj_id);
 		if (err) {
 			verbose(env, "kfunc %s#%d reference has not been acquired before\n",
-				func_name, func_id);
+				func_name, meta.func_id);
 			return err;
 		}
 	}
@@ -10202,7 +10228,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 					set_rbtree_add_callback_state);
 		if (err) {
 			verbose(env, "kfunc %s#%d failed callback verification\n",
-				func_name, func_id);
+				func_name, meta.func_id);
 			return err;
 		}
 	}
@@ -10211,7 +10237,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		mark_reg_not_init(env, regs, caller_saved[i]);
 
 	/* Check return type */
-	t = btf_type_skip_modifiers(desc_btf, func_proto->type, NULL);
+	t = btf_type_skip_modifiers(desc_btf, meta.func_proto->type, NULL);
 
 	if (is_kfunc_acquire(&meta) && !btf_type_is_struct_ptr(meta.btf, t)) {
 		/* Only exception is bpf_obj_new_impl */
@@ -10260,11 +10286,11 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 				regs[BPF_REG_0].btf = ret_btf;
 				regs[BPF_REG_0].btf_id = ret_btf_id;
 
-				env->insn_aux_data[insn_idx].obj_new_size = ret_t->size;
-				env->insn_aux_data[insn_idx].kptr_struct_meta =
+				insn_aux->obj_new_size = ret_t->size;
+				insn_aux->kptr_struct_meta =
 					btf_find_struct_meta(ret_btf, ret_btf_id);
 			} else if (meta.func_id == special_kfunc_list[KF_bpf_obj_drop_impl]) {
-				env->insn_aux_data[insn_idx].kptr_struct_meta =
+				insn_aux->kptr_struct_meta =
 					btf_find_struct_meta(meta.arg_obj_drop.btf,
 							     meta.arg_obj_drop.btf_id);
 			} else if (meta.func_id == special_kfunc_list[KF_bpf_list_pop_front] ||
@@ -10397,8 +10423,8 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			regs[BPF_REG_0].id = ++env->id_gen;
 	} /* else { add_kfunc_call() ensures it is btf_type_is_void(t) } */
 
-	nargs = btf_type_vlen(func_proto);
-	args = (const struct btf_param *)(func_proto + 1);
+	nargs = btf_type_vlen(meta.func_proto);
+	args = (const struct btf_param *)(meta.func_proto + 1);
 	for (i = 0; i < nargs; i++) {
 		u32 regno = i + 1;
 
Signature · 1 line
2.34.1
author maintainer
#2 lore raw

PATCH v2 2/8 bpf: add iterator kfuncs registration and validation logic

In reply to Andrii Nakryiko

Add ability to register kfuncs that implement BPF open-coded iterator contract and enforce naming and function proto convention. Enforcement is happing at the time of kfunc registration and is significantly simplifies the rest of iterators logic in verifier.

More details follow in subsequent patches, but we recognize and enforce the following conditions.

All kfuncs (constructor, next, destructor) have to be named consistenly as bpf_iter_<type>_{new,next,destroy(), respectively. <type> represents iterator type, and iterator's state should be represented as matching struct bpf_iter_<type> state type. Also, all iter kfuncs should have a pointer to this struct bpf_iter_<type> as a very first argument.

Additionally:
- Constructor, i.e., bpf_iter_<type>_new(), can have arbitrary extra number of arguments. Return type not enforced either.
- Next method, i.e., bpf_iter_<type>_next(), has to return a pointer type and should have exactly one argument: struct bpf_iter_<type> * (const/volatile/restrict and typedefs are ignored).
- Destructor, i.e., bpf_iter_<type>_destroy(), should return void and should have exactly one argument, similar to next method.
- struct bpf_iter_<type> size is enforced to be positive and a multiple of 8 bytes (to fit stack slots correctly).

Such strictness and consistency allows to build generic helpers abstracting important, but boilerplate, details to be able to use open-coded iterators effectively and ergonomically. It also simplifies verifier logic in some places. At the same time, this doesn't hurt generality of possible iterator implementations. Win-win.

Constructor kfunc is marked with a new KF_ITER_NEW flags, next method is marked with KF_ITER_NEXT (and should also have KF_RET_NULL, of course), while destructor kfunc is marked as KF_ITER_DESTROY.

Additionally, we add a trivial kfunc name validation, it should be a valid non-NULL and non-empty string.

---
 include/linux/bpf_verifier.h |   2 +
 include/linux/btf.h          |   4 ++
 kernel/bpf/btf.c             | 112 ++++++++++++++++++++++++++++++++++-
 3 files changed, 117 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +2 -0
index 18538bad2b8c..e2dc7f064449 100644
@@ -59,6 +59,8 @@ struct bpf_active_lock {
 	u32 id;
 };
 
+#define ITER_PREFIX "bpf_iter_"
+
 struct bpf_reg_state {
 	/* Ordering of fields matters.  See states_equal() */
 	enum bpf_reg_type type;
include/linux/btf.h +4 -0
index 556b3e2e7471..1bba0827e8c4 100644
@@ -71,6 +71,10 @@
 #define KF_SLEEPABLE    (1 << 5) /* kfunc may sleep */
 #define KF_DESTRUCTIVE  (1 << 6) /* kfunc performs destructive actions */
 #define KF_RCU          (1 << 7) /* kfunc takes either rcu or trusted pointer arguments */
+/* only one of KF_ITER_{NEW,NEXT,DESTROY} could be specified per kfunc */
+#define KF_ITER_NEW     (1 << 8) /* kfunc implements BPF iter constructor */
+#define KF_ITER_NEXT    (1 << 9) /* kfunc implements BPF iter next method */
+#define KF_ITER_DESTROY (1 << 10) /* kfunc implements BPF iter destructor */
 
 /*
  * Tag marking a kernel function as a kfunc. This is meant to minimize the
kernel/bpf/btf.c +111 -1

131 lines not on this page · raw message

Signature · 1 line
2.34.1
author maintainer
#3 lore raw

PATCH v2 3/8 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.

Each kind of iterators has its own associated struct bpf_iter_<type>, where <type> specifies a specific type of iterator. struct bpf_iter_<type> state is supposed to be on BPF program's stack, so there will be no way to change its size later on without breaking backwards compatibility, so choose wisely! But given it's specific to a given <type> of iterator, this allows a lot of flexibility: simple iterators could be fine with just one stack slot (8 bytes), like numbers iterator in the next patch. While some other more complicated iterators would need way more to keep their iterator state. Either way, such design allows to avoid runtime memory allocations, which otherwise would be necessary if fixed on-the-stack size turns out too small.

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_<type> 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_num 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. This matches similar APIs (e.g., slices in Go or Rust) that implement a range of elements, where end index is non-inclusive.

In the above example, we see a trio of function:
- constructor, bpf_iter_num_new(), which initializes iterator state (struct bpf_iter_num 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_num 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 state 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. This is enforced at kfunc registration point by one of the previous patches in this series.

At the implementation level, iterator state tracking for verification purposes is very similar to dynptr. We add STACK_ITER stack slot type, reserve necessary number of slots, depending on sizeof(struct bpf_iter_<type>), and keep track of necessary extra state in the "main" slot, which is marked with non-zero ref_obj_id. Other slots are also marked as STACK_ITER, but have zero ref_obj_id. This is simpler than having a separate "is_first_slot" flag.

Another big distinction is that STACK_ITER is *always refcounted*, which simplifies implementation 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 here.

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 one. 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 account the contract stating that iterator next method *has to* return NULL eventually, we can conclude that loop body is safe and will eventually terminate. 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_verifier.h |  25 +-
 kernel/bpf/verifier.c        | 595 ++++++++++++++++++++++++++++++++++-
 2 files changed, 611 insertions(+), 9 deletions(-)
include/linux/bpf_verifier.h +24 -1
index e2dc7f064449..d0483aed2580 100644
@@ -61,6 +61,12 @@ struct bpf_active_lock {
 
 #define ITER_PREFIX "bpf_iter_"
 
+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;
@@ -105,6 +111,18 @@ struct bpf_reg_state {
 			bool first_slot;
 		} dynptr;
 
+		/* For bpf_iter stack slots */
+		struct {
+			/* BTF container and BTF type ID describing
+			 * struct bpf_iter_<type> of an iterator state
+			 */
+			struct btf *btf;
+			u32 btf_id;
+			/* packing following two fields to fit iter state into 16 bytes */
+			enum bpf_iter_state state:2;
+			int depth:30;
+		} iter;
+
 		/* Max size from any of the above. */
 		struct {
 			unsigned long raw1;
@@ -143,6 +161,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
@@ -213,11 +233,13 @@ 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)
 
 struct bpf_stack_state {
 	struct bpf_reg_state spilled_ptr;
@@ -450,6 +472,7 @@ struct bpf_insn_aux_data {
 	bool sanitize_stack_spill; /* subject to Spectre v4 sanitation */
 	bool zext_dst; /* this insn zero extends dst reg */
 	bool storage_get_func_atomic; /* bpf_*_storage_get() with atomic memory alloc */
+	bool is_iter_next; /* bpf_iter_<type>_next() kfunc call */
 	u8 alu_state; /* used in combination with alu_limit */
 
 	/* below fields are initialized once */
kernel/bpf/verifier.c +587 -8

733 lines not on this page · raw message

Signature · 1 line
2.34.1
#4 lore raw

Re: [PATCH v2 bpf-next 3/8] bpf: add support for open-coded iterator loops

I love your patch! Perhaps something to improve:

Hi Andrii,

I love your patch! Perhaps something to improve:

[auto build test WARNING on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Andrii-Nakryiko/bpf-factor-out-fetching-basic-kfunc-metadata/20230308-055530
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20230307215329.3895377-4-andrii%40kernel.org
patch subject: [PATCH v2 bpf-next 3/8] bpf: add support for open-coded iterator loops
config: m68k-allyesconfig (https://download.01.org/0day-ci/archive/20230308/[email protected]/config)
compiler: m68k-linux-gcc (GCC) 12.1.0

reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/9eada50b93c4fc3f41032699fda73bc125b37d0e
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Andrii-Nakryiko/bpf-factor-out-fetching-basic-kfunc-metadata/20230308-055530 git checkout 9eada50b93c4fc3f41032699fda73bc125b37d0e
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=m68k olddefconfig COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=m68k SHELL=/bin/bash kernel/bpf/

If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <[email protected]>
| Link: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All warnings (new ones prefixed by >>):

kernel/bpf/verifier.c: In function 'is_iter_reg_valid_init':

>> kernel/bpf/verifier.c:1255:32: warning: variable 't' set but not used [-Wunused-but-set-variable]
    1255 |         const struct btf_type *t;
         |                                ^

vim +/t +1255 kernel/bpf/verifier.c

1250
1251 static bool is_iter_reg_valid_init(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
1252 struct btf *btf, u32 btf_id, int nr_slots)
1253 {
1254 struct bpf_func_state *state = func(env, reg);

> 1255		const struct btf_type *t;

1256 int spi, i, j;
1257
1258 spi = iter_get_spi(env, reg, nr_slots);
1259 if (spi < 0)
1260 return false;
1261
1262 t = btf_type_by_id(btf, btf_id);
1263
1264 for (i = 0; i < nr_slots; i++) {
1265 struct bpf_stack_state *slot = &state->stack[spi - i];
1266 struct bpf_reg_state *st = &slot->spilled_ptr;
1267
1268 /* only main (first) slot has ref_obj_id set */
1269 if (i == 0 && !st->ref_obj_id)
1270 return false;
1271 if (i != 0 && st->ref_obj_id)
1272 return false;
1273 if (st->iter.btf != btf || st->iter.btf_id != btf_id)
1274 return false;
1275
1276 for (j = 0; j < BPF_REG_SIZE; j++)
1277 if (slot->slot_type[j] != STACK_ITER)
1278 return false;
1279 }
1280
1281 return true;
1282 }
1283

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests
#5 lore raw

Re: [PATCH v2 bpf-next 3/8] bpf: add support for open-coded iterator loops

Quoted 46 lines · kernel test robot

Hi Andrii,

I love your patch! Perhaps something to improve:

[auto build test WARNING on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Andrii-Nakryiko/bpf-factor-out-fetching-basic-kfunc-metadata/20230308-055530
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20230307215329.3895377-4-andrii%40kernel.org
patch subject: [PATCH v2 bpf-next 3/8] bpf: add support for open-coded iterator loops
config: m68k-allyesconfig (https://download.01.org/0day-ci/archive/20230308/[email protected]/config)
compiler: m68k-linux-gcc (GCC) 12.1.0

reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/9eada50b93c4fc3f41032699fda73bc125b37d0e
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Andrii-Nakryiko/bpf-factor-out-fetching-basic-kfunc-metadata/20230308-055530 git checkout 9eada50b93c4fc3f41032699fda73bc125b37d0e
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=m68k olddefconfig COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=m68k SHELL=/bin/bash kernel/bpf/

If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <[email protected]>
| Link: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All warnings (new ones prefixed by >>):

kernel/bpf/verifier.c: In function 'is_iter_reg_valid_init':

Quoted 1 line
Quoted 1 line

kernel/bpf/verifier.c:1255:32: warning: variable 't' set but not used [-Wunused-but-set-variable]

    1255 |         const struct btf_type *t;
         |                                ^

vim +/t +1255 kernel/bpf/verifier.c

1250
1251 static bool is_iter_reg_valid_init(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
1252 struct btf *btf, u32 btf_id, int nr_slots)
1253 {

  1254          struct bpf_func_state *state = func(env, reg);
> 1255          const struct btf_type *t;
  1256          int spi, i, j;
Quoted 6 lines

1257
1258 spi = iter_get_spi(env, reg, nr_slots);
1259 if (spi < 0)
1260 return false;
1261
1262 t = btf_type_by_id(btf, btf_id);

some leftover from early v2 attempts, doh

I'll wait an hour or two for some other feedback before spamming with v4

Quoted 25 lines
  1263
  1264          for (i = 0; i < nr_slots; i++) {
  1265                  struct bpf_stack_state *slot = &state->stack[spi - i];
  1266                  struct bpf_reg_state *st = &slot->spilled_ptr;
  1267
  1268                  /* only main (first) slot has ref_obj_id set */
  1269                  if (i == 0 && !st->ref_obj_id)
  1270                          return false;
  1271                  if (i != 0 && st->ref_obj_id)
  1272                          return false;
  1273                  if (st->iter.btf != btf || st->iter.btf_id != btf_id)
  1274                          return false;
  1275
  1276                  for (j = 0; j < BPF_REG_SIZE; j++)
  1277                          if (slot->slot_type[j] != STACK_ITER)
  1278                                  return false;
  1279          }
  1280
  1281          return true;
  1282  }
  1283

--
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests

author maintainer
#6 lore raw

PATCH v2 4/8 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, end is exclusive).
- bpf_iter_num_next() which will keep returning 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, which 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 or 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            |  8 +++-
 include/uapi/linux/bpf.h       |  8 ++++
 kernel/bpf/bpf_iter.c          | 70 ++++++++++++++++++++++++++++++++++
 kernel/bpf/helpers.c           |  3 ++
 kernel/bpf/verifier.c          |  6 +++
 tools/include/uapi/linux/bpf.h |  8 ++++
 6 files changed, 101 insertions(+), 2 deletions(-)
include/linux/bpf.h +6 -2
index 6792a7940e1e..e64ff1e89fb2 100644
@@ -1617,8 +1617,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 |	\
include/uapi/linux/bpf.h +8 -0
index 976b194eb775..bf8b77d9a17e 100644
@@ -7112,4 +7112,12 @@ enum {
 	BPF_F_TIMER_ABS = (1ULL << 0),
 };
 
+/* BPF numbers iterator state */
+struct bpf_iter_num {
+	/* opaque iterator state; having __u64 here allows to preserve correct
+	 * alignment requirements in vmlinux.h, generated from BTF
+	 */
+	__u64 __opaque[1];
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/bpf_iter.c +70 -0

73 lines not on this page · raw message

kernel/bpf/helpers.c +3 -0
index 637ac4e92e75..f9b7eeedce08 100644
@@ -2411,6 +2411,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, KF_ITER_NEW)
+BTF_ID_FLAGS(func, bpf_iter_num_next, KF_ITER_NEXT | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_num_destroy, KF_ITER_DESTROY)
 BTF_SET8_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
kernel/bpf/verifier.c +6 -0
index d1246d187fac..33c305b563f6 100644
@@ -9542,6 +9542,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)
@@ -9580,6 +9583,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)
 {
tools/include/uapi/linux/bpf.h +8 -0
index 976b194eb775..bf8b77d9a17e 100644
@@ -7112,4 +7112,12 @@ enum {
 	BPF_F_TIMER_ABS = (1ULL << 0),
 };
 
+/* BPF numbers iterator state */
+struct bpf_iter_num {
+	/* opaque iterator state; having __u64 here allows to preserve correct
+	 * alignment requirements in vmlinux.h, generated from BTF
+	 */
+	__u64 __opaque[1];
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
Signature · 1 line
2.34.1
#7 lore raw

Re: [PATCH v2 bpf-next 4/8] bpf: implement number iterator

Quoted 184 lines · 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, end is exclusive).
- bpf_iter_num_next() which will keep returning 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, which 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 or 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            |  8 +++-
 include/uapi/linux/bpf.h       |  8 ++++
 kernel/bpf/bpf_iter.c          | 70 ++++++++++++++++++++++++++++++++++
 kernel/bpf/helpers.c           |  3 ++
 kernel/bpf/verifier.c          |  6 +++
 tools/include/uapi/linux/bpf.h |  8 ++++
 6 files changed, 101 insertions(+), 2 deletions(-)
include/linux/bpf.h +6 -2
index 6792a7940e1e..e64ff1e89fb2 100644
@@ -1617,8 +1617,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 |    \
include/uapi/linux/bpf.h +8 -0
index 976b194eb775..bf8b77d9a17e 100644
@@ -7112,4 +7112,12 @@ enum {
        BPF_F_TIMER_ABS = (1ULL << 0),
 };
 
+/* BPF numbers iterator state */
+struct bpf_iter_num {
+       /* opaque iterator state; having __u64 here allows to preserve correct
+        * alignment requirements in vmlinux.h, generated from BTF
+        */
+       __u64 __opaque[1];
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/bpf_iter.c +70 -0
index 5dc307bdeaeb..96856f130cbf 100644
@@ -776,3 +776,73 @@ const struct bpf_func_proto bpf_loop_proto = {
        .arg3_type      = ARG_PTR_TO_STACK_OR_NULL,
        .arg4_type      = ARG_ANYTHING,
 };
+
+struct bpf_iter_num_kern {
+       int cur; /* current value, inclusive */
+       int end; /* final value, exclusive */
+} __aligned(8);
+
+__diag_push();
+__diag_ignore_all("-Wmissing-prototypes",
+                 "Global functions as their definitions will be in vmlinux BTF");
+
+__bpf_kfunc int bpf_iter_num_new(struct bpf_iter_num *it, int start, int end)
+{
+       struct bpf_iter_num_kern *s = (void *)it;
+
+       BUILD_BUG_ON(sizeof(struct bpf_iter_num_kern) != sizeof(struct bpf_iter_num));
+       BUILD_BUG_ON(__alignof__(struct bpf_iter_num_kern) != __alignof__(struct bpf_iter_num));
+
+       BTF_TYPE_EMIT(struct btf_iter_num);
+
+       /* start == end is legit, it's an empty range and we'll just get NULL
+        * on first (and any subsequent) bpf_iter_num_next() call
+        */
+       if (start > end) {
+               s->cur = s->end = 0;
+               return -EINVAL;
+       }
+
+       /* avoid overflows, e.g., if start == INT_MIN and end == INT_MAX */
+       if ((s64)end - (s64)start > BPF_MAX_LOOPS) {
+               s->cur = s->end = 0;
+               return -E2BIG;
+       }
+
+       /* user will call bpf_iter_num_next() first,
+        * which will set s->cur to exactly start value;
+        * underflow shouldn't matter
+        */
+       s->cur = start - 1;
+       s->end = end;
+
+       return 0;
+}
+
+__bpf_kfunc int *bpf_iter_num_next(struct bpf_iter_num* it)
+{
+       struct bpf_iter_num_kern *s = (void *)it;
+
+       /* check failed initialization or if we are done (same behavior);
+        * need to be careful about overflow, so convert to s64 for checks,
+        * e.g., if s->cur == s->end == INT_MAX, we can't just do
+        * s->cur + 1 >= s->end
+        */
+       if ((s64)(s->cur + 1) >= s->end) {
+               s->cur = s->end = 0;
+               return NULL;
+       }
+
+       s->cur++;
+
+       return &s->cur;
+}
+
+__bpf_kfunc void bpf_iter_num_destroy(struct bpf_iter_num *it)
+{
+       struct bpf_iter_num_kern *s = (void *)it;
+
+       s->cur = s->end = 0;
+}
+
+__diag_pop();
kernel/bpf/helpers.c +3 -0
index 637ac4e92e75..f9b7eeedce08 100644
@@ -2411,6 +2411,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, KF_ITER_NEW)
+BTF_ID_FLAGS(func, bpf_iter_num_next, KF_ITER_NEXT | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_num_destroy, KF_ITER_DESTROY)
 BTF_SET8_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
kernel/bpf/verifier.c +0 -0
index d1246d187fac..33c305b563f6 100644

kernel/bpf/verifier.c enum special_kfunc_type { · line 9547

Quoted 6 lines
kernel/bpf/verifier.c +3 -0
@@ -9542,6 +9542,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,

don't really need this, this is a leftover from v1, missed it. If this patch set is going to be applied as is, please strip these three rows.

Quoted 33 lines
kernel/bpf/verifier.c +3 -0
 };
 
 BTF_SET_START(special_kfunc_set)
@@ -9580,6 +9583,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)
 {
tools/include/uapi/linux/bpf.h +8 -1
index 976b194eb775..bf8b77d9a17e 100644
@@ -7112,4 +7112,12 @@ enum {
        BPF_F_TIMER_ABS = (1ULL << 0),
 };
 
+/* BPF numbers iterator state */
+struct bpf_iter_num {
+       /* opaque iterator state; having __u64 here allows to preserve correct
+        * alignment requirements in vmlinux.h, generated from BTF
+        */
+       __u64 __opaque[1];
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
--

2.34.1

author maintainer
#8 lore raw

PATCH v2 5/8 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 ergonomics very close to C language's 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 meant as a simple "repeat action N times" loop:

bpf_repeat(N) { /* whatever, N times */ }

Note that break and continue statements 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 a 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  | 99 +++++++++++++++++++
 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, 124 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 +99 -0

104 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.34.1
author maintainer
#9 lore raw

PATCH v2 6/8 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  | 426 +++++++++++
 5 files changed, 1325 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 597688a188ae..43b154a639e7 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 +426 -0

426 lines not on this page · raw message

Signature · 1 line
2.34.1
author maintainer
#10 lore raw

PATCH v2 7/8 selftests/bpf: add number iterator tests

In reply to Andrii Nakryiko

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

---
 .../testing/selftests/bpf/prog_tests/iters.c  |  49 ++++
 tools/testing/selftests/bpf/progs/iters_num.c | 242 ++++++++++++++++++
 2 files changed, 291 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/iters_num.c
tools/testing/selftests/bpf/prog_tests/iters.c +49 -0
index 414fb8d82145..2e7caff9523e 100644
@@ -6,10 +6,59 @@
 #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);
+
+#undef VALIDATE_CASE
+
+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.34.1
author maintainer
#11 lore raw

PATCH v2 8/8 selftests/bpf: implement and test custom testmod_seq iterator

In reply to Andrii Nakryiko

Implement a trivial iterator returning same specified integer value N times as part of bpf_testmod kernel module. Add selftests to validate everything works end to end.

We also reuse these tests as "verification-only" tests, to validate that kernel prints the state of custom module-only iterator correctly:

fp-16=iter_testmod_seq(ref_id=1,state=drained,depth=0)

"testmod_seq" part is iterator type, and is coming from module's BTF information dynamically at runtime.

---
 .../selftests/bpf/bpf_testmod/bpf_testmod.c   | 42 +++++++++-
 .../selftests/bpf/bpf_testmod/bpf_testmod.h   |  6 ++
 .../testing/selftests/bpf/prog_tests/iters.c  | 42 ++++++++++
 .../selftests/bpf/progs/iters_testmod_seq.c   | 79 +++++++++++++++++++
 4 files changed, 168 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/progs/iters_testmod_seq.c
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c +41 -1
index 46500636d8cd..5e6e85c8d77d 100644
@@ -65,6 +65,34 @@ bpf_testmod_test_mod_kfunc(int i)
 	*(int *)this_cpu_ptr(&bpf_testmod_ksym_percpu) = i;
 }
 
+__bpf_kfunc int bpf_iter_testmod_seq_new(struct bpf_iter_testmod_seq *it, s64 value, int cnt)
+{
+	if (cnt < 0) {
+		it->cnt = 0;
+		return -EINVAL;
+	}
+
+	it->value = value;
+	it->cnt = cnt;
+
+	return 0;
+}
+
+__bpf_kfunc s64 *bpf_iter_testmod_seq_next(struct bpf_iter_testmod_seq* it)
+{
+	if (it->cnt <= 0)
+		return NULL;
+
+	it->cnt--;
+
+	return &it->value;
+}
+
+__bpf_kfunc void bpf_iter_testmod_seq_destroy(struct bpf_iter_testmod_seq *it)
+{
+	it->cnt = 0;
+}
+
 struct bpf_testmod_btf_type_tag_1 {
 	int a;
 };
@@ -220,6 +248,17 @@ static struct bin_attribute bin_attr_bpf_testmod_file __ro_after_init = {
 	.write = bpf_testmod_test_write,
 };
 
+BTF_SET8_START(bpf_testmod_common_kfunc_ids)
+BTF_ID_FLAGS(func, bpf_iter_testmod_seq_new, KF_ITER_NEW)
+BTF_ID_FLAGS(func, bpf_iter_testmod_seq_next, KF_ITER_NEXT | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_testmod_seq_destroy, KF_ITER_DESTROY)
+BTF_SET8_END(bpf_testmod_common_kfunc_ids)
+
+static const struct btf_kfunc_id_set bpf_testmod_common_kfunc_set = {
+	.owner = THIS_MODULE,
+	.set   = &bpf_testmod_common_kfunc_ids,
+};
+
 BTF_SET8_START(bpf_testmod_check_kfunc_ids)
 BTF_ID_FLAGS(func, bpf_testmod_test_mod_kfunc)
 BTF_SET8_END(bpf_testmod_check_kfunc_ids)
@@ -235,7 +274,8 @@ static int bpf_testmod_init(void)
 {
 	int ret;
 
-	ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_SCHED_CLS, &bpf_testmod_kfunc_set);
+	ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_UNSPEC, &bpf_testmod_common_kfunc_set);
+	ret = ret ?: register_btf_kfunc_id_set(BPF_PROG_TYPE_SCHED_CLS, &bpf_testmod_kfunc_set);
 	if (ret < 0)
 		return ret;
 	if (bpf_fentry_test1(0) < 0)
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.h +6 -0
index 0d71e2607832..f32793efe095 100644
@@ -22,4 +22,10 @@ struct bpf_testmod_test_writable_ctx {
 	int val;
 };
 
+/* BPF iter that returns *value* *n* times in a row */
+struct bpf_iter_testmod_seq {
+	s64 value;
+	int cnt;
+};
+
 #endif /* _BPF_TESTMOD_H */
tools/testing/selftests/bpf/prog_tests/iters.c +42 -0

60 lines not on this page · raw message

tools/testing/selftests/bpf/progs/iters_testmod_seq.c new file +79 -0

79 lines not on this page · raw message

Signature · 1 line
2.34.1