Skip to contentSkip to conversation

Add bpf_for_each helper

PATCH Superseded Joanne Koong 4 participants 20 messages Nov 18, 2021 – Nov 22, 2021 1 message not in the archive

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

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover Add bpf_for_each helper

This patchset add a new helper, bpf_for_each.

One of the complexities of using for loops in bpf programs is that the verifier needs to ensure that in every possibility of the loop logic, the loop will always terminate. As such, there is a limit on how many iterations the loop can do.

The bpf_for_each helper moves the loop logic into the kernel and can thereby guarantee that the loop will always terminate. The bpf_for_each helper simplifies a lot of the complexity the verifier needs to check, as well as removes the constraint on the number of loops able to be run.

From the test results, we see that using bpf_for_each in place of the traditional for loop led to a decrease in verification time and number of bpf instructions by 100%. The benchmark results show that as the number of iterations increases, the overhead per iteration decreases.

The high-level overview of the patches -
Patch 1 - kernel-side + API changes for adding bpf_for_each Patch 2 - tests
Patch 3 - benchmark for overhead of a bpf_for_each call

Joanne Koong (3):
bpf: Add bpf_for_each helper
selftests/bpf: Add tests for bpf_for_each
selftest/bpf/benchs: add bpf_for_each benchmark

 include/linux/bpf.h                           |   1 +
 include/uapi/linux/bpf.h                      |  23 ++++
 kernel/bpf/bpf_iter.c                         |  32 ++++++
 kernel/bpf/helpers.c                          |   2 +
 kernel/bpf/verifier.c                         |  28 +++++
 tools/include/uapi/linux/bpf.h                |  23 ++++
 tools/testing/selftests/bpf/Makefile          |   3 +-
 tools/testing/selftests/bpf/bench.c           |   4 +
 .../selftests/bpf/benchs/bench_for_each.c     | 105 ++++++++++++++++++
 .../bpf/benchs/run_bench_for_each.sh          |  16 +++
 .../bpf/prog_tests/bpf_verif_scale.c          |  12 ++
 .../selftests/bpf/prog_tests/for_each.c       |  61 ++++++++++
 .../selftests/bpf/progs/for_each_helper.c     |  82 ++++++++++++++
 tools/testing/selftests/bpf/progs/pyperf.h    |  70 +++++++++++-
 .../selftests/bpf/progs/pyperf600_foreach.c   |   5 +
 .../testing/selftests/bpf/progs/strobemeta.h  |  73 +++++++++++-
 .../selftests/bpf/progs/strobemeta_foreach.c  |   9 ++
 17 files changed, 544 insertions(+), 5 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_for_each.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_for_each.sh
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_helper.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_foreach.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_foreach.c
Signature · 1 line
2.30.2
#1 lore raw

PATCH 1/3 bpf: Add bpf_for_each helper

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

---
 include/linux/bpf.h            |  1 +
 include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++
 kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++
 kernel/bpf/helpers.c           |  2 ++
 kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++
 tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++
 6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
index 6deebf8bf78f..d9b69a896c91 100644
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;
 extern const struct bpf_func_proto bpf_task_storage_get_proto;
 extern const struct bpf_func_proto bpf_task_storage_delete_proto;
 extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
+extern const struct bpf_func_proto bpf_for_each_proto;
 extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
 extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
 extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
include/uapi/linux/bpf.h +23 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
  *		The number of traversed map elements for success, **-EINVAL** for
  *		invalid **flags**.
  *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_iterations**, call **callback_fn** function with
+ *		**callback_ctx** as the context parameter.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.
+ *		Currently, the **flags** must be 0.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *		where **index** is the current index in the iteration. The index
+ *		is zero-indexed.
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		iteration. If return value is 1, the helper will skip the rest of
+ *		the iterations and return. Other return values are not used now.
+ *
+ *	Return
+ *		The number of iterations performed, **-EINVAL** for invalid **flags**
+ *		or a null **callback_fn**.
+ *
  * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len)
  *	Description
  *		Outputs a string into the **str** buffer of size **str_size**
@@ -5105,6 +5127,7 @@ union bpf_attr {
 	FN(sock_from_file),		\
 	FN(check_mtu),			\
 	FN(for_each_map_elem),		\
+	FN(for_each),			\
 	FN(snprintf),			\
 	FN(sys_bpf),			\
 	FN(btf_find_by_name_kind),	\
kernel/bpf/bpf_iter.c +32 -0
index b2ee45064e06..cb742c50898a 100644
@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = {
 	.arg3_type	= ARG_PTR_TO_STACK_OR_NULL,
 	.arg4_type	= ARG_ANYTHING,
 };
+
+BPF_CALL_4(bpf_for_each, u32, nr_iterations, void *, callback_fn, void *, callback_ctx,
+	   u64, flags)
+{
+	bpf_callback_t callback = (bpf_callback_t)callback_fn;
+	u64 err;
+	u32 i;
+
+	if (flags)
+		return -EINVAL;
+
+	for (i = 0; i < nr_iterations; i++) {
+		err = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		/* return value: 0 - continue, 1 - stop and return */
+		if (err) {
+			i++;
+			break;
+		}
+	}
+
+	return i;
+}
+
+const struct bpf_func_proto bpf_for_each_proto = {
+	.func		= bpf_for_each,
+	.gpl_only	= false,
+	.ret_type	= RET_INTEGER,
+	.arg1_type	= ARG_ANYTHING,
+	.arg2_type	= ARG_PTR_TO_FUNC,
+	.arg3_type	= ARG_PTR_TO_STACK_OR_NULL,
+	.arg4_type	= ARG_ANYTHING,
+};
kernel/bpf/helpers.c +2 -0
index 1ffd469c217f..ac10e1b3859f 100644
@@ -1378,6 +1378,8 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 		return &bpf_ringbuf_query_proto;
 	case BPF_FUNC_for_each_map_elem:
 		return &bpf_for_each_map_elem_proto;
+	case BPF_FUNC_for_each:
+		return &bpf_for_each_proto;
 	default:
 		break;
 	}
kernel/bpf/verifier.c +28 -0
index 3c8aa7df1773..7c9cc4f01104 100644
@@ -6103,6 +6103,27 @@ static int set_map_elem_callback_state(struct bpf_verifier_env *env,
 	return 0;
 }
 
+static int set_for_each_callback_state(struct bpf_verifier_env *env,
+				       struct bpf_func_state *caller,
+				       struct bpf_func_state *callee,
+				       int insn_idx)
+{
+	/* bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx,
+	 *		u64 flags);
+	 * callback_fn(u32 index, void *callback_ctx);
+	 */
+	callee->regs[BPF_REG_1].type = SCALAR_VALUE;
+	callee->regs[BPF_REG_2] = caller->regs[BPF_REG_3];
+
+	/* unused */
+	__mark_reg_not_init(env, &callee->regs[BPF_REG_3]);
+	__mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
+	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
+
+	callee->in_callback_fn = true;
+	return 0;
+}
+
 static int set_timer_callback_state(struct bpf_verifier_env *env,
 				    struct bpf_func_state *caller,
 				    struct bpf_func_state *callee,
@@ -6482,6 +6503,13 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 			return -EINVAL;
 	}
 
+	if (func_id == BPF_FUNC_for_each) {
+		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
+					set_for_each_callback_state);
+		if (err < 0)
+			return -EINVAL;
+	}
+
 	if (func_id == BPF_FUNC_timer_set_callback) {
 		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
 					set_timer_callback_state);
tools/include/uapi/linux/bpf.h +23 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
  *		The number of traversed map elements for success, **-EINVAL** for
  *		invalid **flags**.
  *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_iterations**, call **callback_fn** function with
+ *		**callback_ctx** as the context parameter.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.
+ *		Currently, the **flags** must be 0.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *		where **index** is the current index in the iteration. The index
+ *		is zero-indexed.
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		iteration. If return value is 1, the helper will skip the rest of
+ *		the iterations and return. Other return values are not used now.
+ *
+ *	Return
+ *		The number of iterations performed, **-EINVAL** for invalid **flags**
+ *		or a null **callback_fn**.
+ *
  * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len)
  *	Description
  *		Outputs a string into the **str** buffer of size **str_size**
@@ -5105,6 +5127,7 @@ union bpf_attr {
 	FN(sock_from_file),		\
 	FN(check_mtu),			\
 	FN(for_each_map_elem),		\
+	FN(for_each),			\
 	FN(snprintf),			\
 	FN(sys_bpf),			\
 	FN(btf_find_by_name_kind),	\
Signature · 1 line
2.30.2
Acked-by on v1 1/3
#2 lore raw

Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper

Quoted 19 lines · Joanne Koong

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

Quoted 1 line

Great to see this! One small nit, below, but otherwise:

Quoted 36 lines
---
 include/linux/bpf.h            |  1 +
 include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++
 kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++
 kernel/bpf/helpers.c           |  2 ++
 kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++
 tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++
 6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
index 6deebf8bf78f..d9b69a896c91 100644
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;
 extern const struct bpf_func_proto bpf_task_storage_get_proto;
 extern const struct bpf_func_proto bpf_task_storage_delete_proto;
 extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
+extern const struct bpf_func_proto bpf_for_each_proto;
 extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
 extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
 extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
include/uapi/linux/bpf.h +7 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
  *		The number of traversed map elements for success, **-EINVAL** for
  *		invalid **flags**.
  *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_iterations**, call **callback_fn** function with
+ *		**callback_ctx** as the context parameter.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.

include/uapi/linux/bpf.h union bpf_attr { · line 4769

Quoted 10 lines
include/uapi/linux/bpf.h +10 -0
+ *		Currently, the **flags** must be 0.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *		where **index** is the current index in the iteration. The index
+ *		is zero-indexed.
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		iteration. If return value is 1, the helper will skip the rest of
+ *		the iterations and return. Other return values are not used now.

The code will actually return for any non-zero value, though? So shouldn't the documentation reflect this? Or, alternatively, should the verifier enforce that the function can only return 0 or 1?

#3 lore raw

Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper

Quoted 70 lines · Toke Høiland-Jørgensen
Quoted 19 lines · Joanne Koong

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

Quoted 1 line

Great to see this! One small nit, below, but otherwise:

Quoted 42 lines
---
  include/linux/bpf.h            |  1 +
  include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++
  kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++
  kernel/bpf/helpers.c           |  2 ++
  kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++
  tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++
  6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
index 6deebf8bf78f..d9b69a896c91 100644
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;
  extern const struct bpf_func_proto bpf_task_storage_get_proto;
  extern const struct bpf_func_proto bpf_task_storage_delete_proto;
  extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
+extern const struct bpf_func_proto bpf_for_each_proto;
  extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
  extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
  extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
include/uapi/linux/bpf.h +13 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
   *		The number of traversed map elements for success, **-EINVAL** for
   *		invalid **flags**.
   *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_iterations**, call **callback_fn** function with
+ *		**callback_ctx** as the context parameter.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.
+ *		Currently, the **flags** must be 0.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *		where **index** is the current index in the iteration. The index
+ *		is zero-indexed.
Quoted 8 lines

include/uapi/linux/bpf.h union bpf_attr { · line 4769

Quoted 4 lines
include/uapi/linux/bpf.h +4 -0
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		iteration. If return value is 1, the helper will skip the rest of
+ *		the iterations and return. Other return values are not used now.

The code will actually return for any non-zero value, though? So shouldn't the documentation reflect this? Or, alternatively, should the verifier enforce that the function can only return 0 or 1?

This is enforced in verifier.c prepare_func_exit().

        if (callee->in_callback_fn) {
                /* enforce R0 return value range [0, 1]. */
                struct tnum range = tnum_range(0, 1);

                if (r0->type != SCALAR_VALUE) {
                        verbose(env, "R0 not a scalar value\n");
                        return -EACCES;
                }
                if (!tnum_in(range, r0->var_off)) {
                        verbose_invalid_scalar(env, r0, &range, 
"callback return", "R0");
                        return -EINVAL;
                }
        }
Quoted 1 line
#4 lore raw

Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper

Quoted 82 lines · Yonghong Song
Quoted 70 lines · Toke Høiland-Jørgensen
Quoted 19 lines · Joanne Koong

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

Quoted 1 line

Great to see this! One small nit, below, but otherwise:

Quoted 42 lines
---
  include/linux/bpf.h            |  1 +
  include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++
  kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++
  kernel/bpf/helpers.c           |  2 ++
  kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++
  tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++
  6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
index 6deebf8bf78f..d9b69a896c91 100644
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;
  extern const struct bpf_func_proto bpf_task_storage_get_proto;
  extern const struct bpf_func_proto bpf_task_storage_delete_proto;
  extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
+extern const struct bpf_func_proto bpf_for_each_proto;
  extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
  extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
  extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
include/uapi/linux/bpf.h +13 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
   *		The number of traversed map elements for success, **-EINVAL** for
   *		invalid **flags**.
   *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_iterations**, call **callback_fn** function with
+ *		**callback_ctx** as the context parameter.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.
+ *		Currently, the **flags** must be 0.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *		where **index** is the current index in the iteration. The index
+ *		is zero-indexed.
Quoted 8 lines

include/uapi/linux/bpf.h union bpf_attr { · line 4769

Quoted 4 lines
include/uapi/linux/bpf.h +4 -0
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		iteration. If return value is 1, the helper will skip the rest of
+ *		the iterations and return. Other return values are not used now.

The code will actually return for any non-zero value, though? So shouldn't the documentation reflect this? Or, alternatively, should the verifier enforce that the function can only return 0 or 1?

This is enforced in verifier.c prepare_func_exit().

Quoted 14 lines
         if (callee->in_callback_fn) {
                 /* enforce R0 return value range [0, 1]. */
                 struct tnum range = tnum_range(0, 1);

                 if (r0->type != SCALAR_VALUE) {
                         verbose(env, "R0 not a scalar value\n");
                         return -EACCES;
                 }
                 if (!tnum_in(range, r0->var_off)) {
                         verbose_invalid_scalar(env, r0, &range, 
"callback return", "R0");
                         return -EINVAL;
                 }
         }

Ah, right! I went looking for this but couldn't find it - thanks for the pointer!

-Toke

#5 lore raw

Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper

In reply to Joanne Koong
Quoted 60 lines · Joanne Koong

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

---
  include/linux/bpf.h            |  1 +
  include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++
  kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++
  kernel/bpf/helpers.c           |  2 ++
  kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++
  tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++
  6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
index 6deebf8bf78f..d9b69a896c91 100644
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;
  extern const struct bpf_func_proto bpf_task_storage_get_proto;
  extern const struct bpf_func_proto bpf_task_storage_delete_proto;
  extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
+extern const struct bpf_func_proto bpf_for_each_proto;
  extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
  extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
  extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
include/uapi/linux/bpf.h +11 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
   *		The number of traversed map elements for success, **-EINVAL** for
   *		invalid **flags**.
   *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_iterations**, call **callback_fn** function with
+ *		**callback_ctx** as the context parameter.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.
+ *		Currently, the **flags** must be 0.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *

include/uapi/linux/bpf.h union bpf_attr { · line 4773

Quoted 10 lines
include/uapi/linux/bpf.h +10 -0
+ *		where **index** is the current index in the iteration. The index
+ *		is zero-indexed.
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		iteration. If return value is 1, the helper will skip the rest of
+ *		the iterations and return. Other return values are not used now.
+ *
+ *	Return
+ *		The number of iterations performed, **-EINVAL** for invalid **flags**
+ *		or a null **callback_fn**.

I think verifier enforced non-null callback_fn, right?

include/uapi/linux/bpf.h union bpf_attr { · line 5130

Quoted 9 lines
include/uapi/linux/bpf.h +2 -0
+ *
   * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len)
   *	Description
   *		Outputs a string into the **str** buffer of size **str_size**
@@ -5105,6 +5127,7 @@ union bpf_attr {
  	FN(sock_from_file),		\
  	FN(check_mtu),			\
  	FN(for_each_map_elem),		\
+	FN(for_each),			\

Please put for_each helper at the end of list. Otherwise, it will break uapi.

Quoted 12 lines
include/uapi/linux/bpf.h +0 -0
  	FN(snprintf),			\
  	FN(sys_bpf),			\
  	FN(btf_find_by_name_kind),	\
kernel/bpf/bpf_iter.c +1 -0
index b2ee45064e06..cb742c50898a 100644
@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = {
  	.arg3_type	= ARG_PTR_TO_STACK_OR_NULL,
  	.arg4_type	= ARG_ANYTHING,
  };
+

[...]

#6 lore raw

Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper

Quoted 75 lines · Yonghong Song
Quoted 72 lines · Joanne Koong

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

---
  include/linux/bpf.h            |  1 + include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++ kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++ kernel/bpf/helpers.c           |  2 ++ kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++ tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++

  6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
index 6deebf8bf78f..d9b69a896c91 100644
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto 
 bpf_get_socket_ptr_cookie_proto;
   extern const struct bpf_func_proto bpf_task_storage_get_proto;
   extern const struct bpf_func_proto bpf_task_storage_delete_proto;
   extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
+extern const struct bpf_func_proto bpf_for_each_proto;
   extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
   extern const struct bpf_func_proto bpf_sk_setsockopt_proto;

  extern const struct bpf_func_proto bpf_sk_getsockopt_proto;

include/uapi/linux/bpf.h +7 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
    *        The number of traversed map elements for success, **-EINVAL** for
    *        invalid **flags**.
    *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void 
 *callback_ctx, u64 flags)
+ *    Description
+ *        For **nr_iterations**, call **callback_fn** function with
+ *        **callback_ctx** as the context parameter.
+ *        The **callback_fn** should be a static function and
+ *        the **callback_ctx** should be a pointer to the stack.
+ *        The **flags** is used to control certain aspects of the 

helper.
+ *        Currently, the **flags** must be 0.
+ *
+ *        long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *        where **index** is the current index in the iteration. The index
+ *        is zero-indexed.
+ *
+ *        If **callback_fn** returns 0, the helper will continue to the next
+ *        iteration. If return value is 1, the helper will skip the rest of
+ *        the iterations and return. Other return values are not

Quoted 9 lines
Quoted 6 lines

used now.
+ *
+ *    Return
+ *        The number of iterations performed, **-EINVAL** for invalid **flags**
+ *        or a null **callback_fn**.

I think verifier enforced non-null callback_fn, right?

Yes, great point - I will remove the "or a null **callback_fn**" part.

Quoted 12 lines

include/uapi/linux/bpf.h union bpf_attr { · line 5130

Quoted 9 lines

+ *
   * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len) *    Description
   *        Outputs a string into the **str** buffer of size **str_size**

include/uapi/linux/bpf.h +1 -0
@@ -5105,6 +5127,7 @@ union bpf_attr {
       FN(sock_from_file),        \
       FN(check_mtu),            \
       FN(for_each_map_elem),        \
+    FN(for_each),            \

Please put for_each helper at the end of list. Otherwise, it will break uapi.

Gotcha. I will make this change for v2 and remember to do this in the future as well!

Quoted 14 lines
Quoted 13 lines
include/uapi/linux/bpf.h +0 -0
       FN(snprintf),            \
       FN(sys_bpf),            \
       FN(btf_find_by_name_kind),    \
kernel/bpf/bpf_iter.c +0 -0
index b2ee45064e06..cb742c50898a 100644
@@ -714,3 +714,35 @@ const struct bpf_func_proto 
 bpf_for_each_map_elem_proto = {
       .arg3_type    = ARG_PTR_TO_STACK_OR_NULL,
       .arg4_type    = ARG_ANYTHING,

  };
+

[...]

#7 lore raw

Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper

In reply to Joanne Koong
Quoted 6 lines · Joanne Koong

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

foreach in other languages are usually used when you are iterating elements of some data structure or stream of data, so the naming feels slightly off. bpf_loop() for bpf_for_range() seems to be more directly pointing to what's going on. My 2 cents, it's subjective, of course.

Quoted 3 lines

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

As Toke mentioned, we don't really check 1. Enforcing it on verifier side is just going to cause more troubles for users and doesn't seem important. I can see two ways to define the semantics, with error propagation and without.

For error propagation, we can define:
- >0, break and return number of iterations performed in total;
- 0, continue to next iteration, if no more iterations, return
number of iterations performed;
- <0, break and return that error value (but no way to know at which
iteration this happened, except through custom context);

Or we can make it simpler and just:
- 0, continue;
- != 0, break;
- always return number of iterations performed.

No strong preferences on my side, I see benefits to both ways.

Quoted 67 lines

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

---
 include/linux/bpf.h            |  1 +
 include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++
 kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++
 kernel/bpf/helpers.c           |  2 ++
 kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++
 tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++
 6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
index 6deebf8bf78f..d9b69a896c91 100644
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;
 extern const struct bpf_func_proto bpf_task_storage_get_proto;
 extern const struct bpf_func_proto bpf_task_storage_delete_proto;
 extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
+extern const struct bpf_func_proto bpf_for_each_proto;
 extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
 extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
 extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
include/uapi/linux/bpf.h +22 -0
index bd0c9f0487f6..ea5098920ed2 100644
@@ -4750,6 +4750,28 @@ union bpf_attr {
  *             The number of traversed map elements for success, **-EINVAL** for
  *             invalid **flags**.
  *
+ * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags)
+ *     Description
+ *             For **nr_iterations**, call **callback_fn** function with
+ *             **callback_ctx** as the context parameter.
+ *             The **callback_fn** should be a static function and
+ *             the **callback_ctx** should be a pointer to the stack.
+ *             The **flags** is used to control certain aspects of the helper.
+ *             Currently, the **flags** must be 0.
+ *
+ *             long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *             where **index** is the current index in the iteration. The index
+ *             is zero-indexed.
+ *
+ *             If **callback_fn** returns 0, the helper will continue to the next
+ *             iteration. If return value is 1, the helper will skip the rest of
+ *             the iterations and return. Other return values are not used now.
+ *
+ *     Return
+ *             The number of iterations performed, **-EINVAL** for invalid **flags**
+ *             or a null **callback_fn**.
+ *
  * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len)
  *     Description
  *             Outputs a string into the **str** buffer of size **str_size**

include/uapi/linux/bpf.h union bpf_attr { · line 5130

Quoted 4 lines
include/uapi/linux/bpf.h +1 -0
@@ -5105,6 +5127,7 @@ union bpf_attr {
        FN(sock_from_file),             \
        FN(check_mtu),                  \
        FN(for_each_map_elem),          \
+       FN(for_each),                   \

you can't change the order of the function definitions, this breaks ABI, please add it at the end

Quoted 9 lines
include/uapi/linux/bpf.h +0 -0
        FN(snprintf),                   \
        FN(sys_bpf),                    \
        FN(btf_find_by_name_kind),      \
kernel/bpf/bpf_iter.c +0 -0
index b2ee45064e06..cb742c50898a 100644
@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = {
        .arg3_type      = ARG_PTR_TO_STACK_OR_NULL,

kernel/bpf/bpf_iter.c const struct bpf_func_proto bpf_for_each_map_elem_proto = { · line 724

Quoted 10 lines
kernel/bpf/bpf_iter.c +8 -0
        .arg4_type      = ARG_ANYTHING,
 };
+
+BPF_CALL_4(bpf_for_each, u32, nr_iterations, void *, callback_fn, void *, callback_ctx,
+          u64, flags)
+{
+       bpf_callback_t callback = (bpf_callback_t)callback_fn;
+       u64 err;
+       u32 i;
+

I wonder if we should have some high but reasonable number of iteration limits. It would be too easy for users to cause some overflow and not notice it, and then pass 4bln iterations and freeze the kernel. I think limiting to something like 1mln or 8mln might be ok. Thoughts?

kernel/bpf/bpf_iter.c const struct bpf_func_proto bpf_for_each_map_elem_proto = { · line 731

Quoted 7 lines
kernel/bpf/bpf_iter.c +7 -0
+       if (flags)
+               return -EINVAL;
+
+       for (i = 0; i < nr_iterations; i++) {
+               err = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+               /* return value: 0 - continue, 1 - stop and return */
+               if (err) {

nit: not really error (at least in the current semantics), "ret" would be more appropriate

Quoted 8 lines
kernel/bpf/bpf_iter.c +8 -0
+                       i++;
+                       break;
+               }
+       }
+
+       return i;
+}
+

[...]

Quoted 4 lines

static int set_timer_callback_state(struct bpf_verifier_env *env,
struct bpf_func_state *caller, struct bpf_func_state *callee,

kernel/bpf/bpf_iter.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 6512

Quoted 10 lines
kernel/bpf/bpf_iter.c +7 -0
@@ -6482,6 +6503,13 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
                        return -EINVAL;
        }
 
+       if (func_id == BPF_FUNC_for_each) {
+               err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
+                                       set_for_each_callback_state);
+               if (err < 0)
+                       return -EINVAL;
+       }
+

we should convert these ifs (they are not even if elses!) into a switch. And move if (err < 0) return err; outside. It will only keep growing.

Quoted 3 lines
kernel/bpf/bpf_iter.c +0 -0
        if (func_id == BPF_FUNC_timer_set_callback) {
                err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
                                        set_timer_callback_state);

[...]

A message that is not in the archive (sent off-list or not yet received): [email protected]

#9 lore raw

Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper

Quoted 123 lines · Joanne Koong
Quoted 11 lines · Andrii Nakryiko
Quoted 5 lines · Joanne Koong

This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:

long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);

foreach in other languages are usually used when you are iterating elements of some data structure or stream of data, so the naming feels slightly off. bpf_loop() for bpf_for_range() seems to be more directly pointing to what's going on. My 2 cents, it's subjective, of course.

Ooh, I really like "bpf_loop()"! I will change it to this for v2.

Quoted 14 lines
Quoted 2 lines

bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.

As Toke mentioned, we don't really check 1. Enforcing it on verifier side is just going to cause more troubles for users and doesn't seem important. I can see two ways to define the semantics, with error propagation and without.

For error propagation, we can define:
- >0, break and return number of iterations performed in total;
- 0, continue to next iteration, if no more iterations, return
number of iterations performed;
- <0, break and return that error value (but no way to know at which
iteration this happened, except through custom context);

Quoted 7 lines

Or we can make it simpler and just:
- 0, continue;
- != 0, break;
- always return number of iterations performed.

No strong preferences on my side, I see benefits to both ways.

This is already enforced in the verifier (as Yonghong mentioned as well) in prepare_func_exit() -

          if (callee->in_callback_fn) {
                  /* enforce R0 return value range [0, 1]. */
                  struct tnum range = tnum_range(0, 1);

                  if (r0->type != SCALAR_VALUE) {
                          verbose(env, "R0 not a scalar value\n");
                          return -EACCES;
                  }
                  if (!tnum_in(range, r0->var_off)) {
                          verbose_invalid_scalar(env, r0, &range,
"callback return", "R0");
                          return -EINVAL;
                  }
          }

The verifier enforces that at callback return, the R0 register is always 0 or 1

Quoted 20 lines
Quoted 20 lines

A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and benchmark

---
  include/linux/bpf.h            |  1 +
  include/uapi/linux/bpf.h       | 23 +++++++++++++++++++++++
  kernel/bpf/bpf_iter.c          | 32 ++++++++++++++++++++++++++++++++
  kernel/bpf/helpers.c           |  2 ++
  kernel/bpf/verifier.c          | 28 ++++++++++++++++++++++++++++
  tools/include/uapi/linux/bpf.h | 23 +++++++++++++++++++++++
  6 files changed, 109 insertions(+)

[...]

Quoted 13 lines
Quoted 13 lines
kernel/bpf/bpf_iter.c +5 -0
index b2ee45064e06..cb742c50898a 100644
@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = {
         .arg3_type      = ARG_PTR_TO_STACK_OR_NULL,
         .arg4_type      = ARG_ANYTHING,
  };
+
+BPF_CALL_4(bpf_for_each, u32, nr_iterations, void *, callback_fn, void *, callback_ctx,
+          u64, flags)
+{
+       bpf_callback_t callback = (bpf_callback_t)callback_fn;
Quoted 9 lines

kernel/bpf/bpf_iter.c const struct bpf_func_proto bpf_for_each_map_elem_proto = { · line 724

Quoted 3 lines
kernel/bpf/bpf_iter.c +3 -0
+       u64 err;
+       u32 i;
+

I wonder if we should have some high but reasonable number of iteration limits. It would be too easy for users to cause some overflow and not notice it, and then pass 4bln iterations and freeze the kernel. I think limiting to something like 1mln or 8mln might be ok. Thoughts?

I see the pros and cons of both. It doesn't seem that likely to me that users would accidentally pass in a negative u32 value. At the same time, I don't think limiting it to something like 1 or 8 million is unreasonable (though it might require the user to read the documentation more closely :)) - if the user wants to do more than 8 million loops then they can call the loop helper multiple times

As a user, I think I'd prefer u32 where I'd automatically know the limit is 2^32 - 1, but either approach sounds good to me!

[...]

Quoted 7 lines
Quoted 7 lines
kernel/bpf/bpf_iter.c +0 -0
  static int set_timer_callback_state(struct bpf_verifier_env *env,
                                     struct bpf_func_state *caller,
                                     struct bpf_func_state *callee,
@@ -6482,6 +6503,13 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
                         return -EINVAL;
         }
 
Quoted 10 lines

kernel/bpf/bpf_iter.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 6512

Quoted 7 lines
kernel/bpf/bpf_iter.c +7 -0
+       if (func_id == BPF_FUNC_for_each) {
+               err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
+                                       set_for_each_callback_state);
+               if (err < 0)
+                       return -EINVAL;
+       }
+

we should convert these ifs (they are not even if elses!) into a switch. And move if (err < 0) return err; outside. It will only keep growing.

Quoted 2 lines

Sounds great, I will do this in v2!

Quoted 1 line

[...]

(resending this email to the vger mailing list because it didn't go through the first time)

#10 lore raw

PATCH 2/3 selftests/bpf: Add tests for bpf_for_each

In reply to Joanne Koong

In this patch -
1) Add a new prog "for_each_helper" which tests the basic functionality of the bpf_for_each helper.

2) Add pyperf600_foreach and strobemeta_foreach to test the performance of using bpf_for_each instead of a for loop

The results of pyperf600 and strobemeta are as follows:

~strobemeta~

Baseline
verification time 6808200 usec
stack depth 496
processed 592132 insns (limit 1000000) max_states_per_insn 14 total_states 16018 peak_states 13684 mark_read 3132 #188 verif_scale_strobemeta:OK (unrolled loop)

Using bpf_for_each
verification time 31589 usec
stack depth 96+408
processed 1630 insns (limit 1000000) max_states_per_insn 4 total_states 107 peak_states 107 mark_read 60 #189 verif_scale_strobemeta_foreach:OK

~pyperf600~

Baseline

    verification time 29702486 usec
    stack depth 368
    processed 626838 insns (limit 1000000) max_states_per_insn 7
    total_states 30368 peak_states 30279 mark_read 748
    #182 verif_scale_pyperf600:OK (unrolled loop)

Using bpf_for_each

    verification time 148488 usec
    stack depth 320+40
    processed 10518 insns (limit 1000000) max_states_per_insn 10
    total_states 705 peak_states 517 mark_read 38
    #183 verif_scale_pyperf600_foreach:OK

Using the bpf_for_each helper led to approximately a 100% decrease in the verification time and in the number of instructions.

---
 .../bpf/prog_tests/bpf_verif_scale.c          | 12 +++
 .../selftests/bpf/prog_tests/for_each.c       | 61 ++++++++++++++++
 .../selftests/bpf/progs/for_each_helper.c     | 69 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/pyperf.h    | 70 +++++++++++++++++-
 .../selftests/bpf/progs/pyperf600_foreach.c   |  5 ++
 .../testing/selftests/bpf/progs/strobemeta.h  | 73 ++++++++++++++++++-
 .../selftests/bpf/progs/strobemeta_foreach.c  |  9 +++
 7 files changed, 295 insertions(+), 4 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_helper.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_foreach.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_foreach.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +12 -0
index 867349e4ed9e..77396484fde7 100644
@@ -115,6 +115,12 @@ void test_verif_scale_pyperf600()
 	scale_test("pyperf600.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_pyperf600_foreach(void)
+{
+	/* use the bpf_for_each helper*/
+	scale_test("pyperf600_foreach.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_pyperf600_nounroll()
 {
 	/* no unroll at all.
@@ -165,6 +171,12 @@ void test_verif_scale_strobemeta()
 	scale_test("strobemeta.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_strobemeta_foreach(void)
+{
+	/* use the bpf_for_each helper*/
+	scale_test("strobemeta_foreach.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_strobemeta_nounroll1()
 {
 	/* no unroll, tiny loops */
tools/testing/selftests/bpf/prog_tests/for_each.c +61 -0

77 lines not on this page · raw message

tools/testing/selftests/bpf/progs/for_each_helper.c new file +69 -0

69 lines not on this page · raw message

tools/testing/selftests/bpf/progs/pyperf.h +69 -1

92 lines not on this page · raw message

tools/testing/selftests/bpf/progs/pyperf600_foreach.c new file +5 -0
new file mode 100644
index 000000000000..1b43f12a7d54
@@ -0,0 +1,5 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2021 Facebook
+#define STACK_MAX_LEN 600
+#define USE_FOREACH
+#include "pyperf.h"
tools/testing/selftests/bpf/progs/strobemeta.h +70 -3

104 lines not on this page · raw message

tools/testing/selftests/bpf/progs/strobemeta_foreach.c new file +9 -0
new file mode 100644
index 000000000000..a2d57d2d68ad
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+// Copyright (c) 2021 Facebook
+
+#define STROBE_MAX_INTS 2
+#define STROBE_MAX_STRS 25
+#define STROBE_MAX_MAPS 100
+#define STROBE_MAX_MAP_ENTRIES 20
+#define USE_FOREACH
+#include "strobemeta.h"
Signature · 1 line
2.30.2
#11 lore raw

Re: [PATCH bpf-next 2/3] selftests/bpf: Add tests for bpf_for_each

Quoted 29 lines · Joanne Koong

In this patch -
1) Add a new prog "for_each_helper" which tests the basic functionality of the bpf_for_each helper.

2) Add pyperf600_foreach and strobemeta_foreach to test the performance of using bpf_for_each instead of a for loop

The results of pyperf600 and strobemeta are as follows:

~strobemeta~

Baseline
verification time 6808200 usec
stack depth 496
processed 592132 insns (limit 1000000) max_states_per_insn 14 total_states 16018 peak_states 13684 mark_read 3132 #188 verif_scale_strobemeta:OK (unrolled loop)

Using bpf_for_each
verification time 31589 usec
stack depth 96+408
processed 1630 insns (limit 1000000) max_states_per_insn 4 total_states 107 peak_states 107 mark_read 60 #189 verif_scale_strobemeta_foreach:OK

~pyperf600~

Baseline

Quoted 8 lines
    verification time 29702486 usec
    stack depth 368
    processed 626838 insns (limit 1000000) max_states_per_insn 7
    total_states 30368 peak_states 30279 mark_read 748
    #182 verif_scale_pyperf600:OK (unrolled loop)

Using bpf_for_each
verification time 148488 usec

200x, this is awesome

Quoted 9 lines
    stack depth 320+40
    processed 10518 insns (limit 1000000) max_states_per_insn 10
    total_states 705 peak_states 517 mark_read 38
    #183 verif_scale_pyperf600_foreach:OK

Using the bpf_for_each helper led to approximately a 100% decrease in the verification time and in the number of instructions.

Quoted 8 lines
---
 .../bpf/prog_tests/bpf_verif_scale.c          | 12 +++
 .../selftests/bpf/prog_tests/for_each.c       | 61 ++++++++++++++++
 .../selftests/bpf/progs/for_each_helper.c     | 69 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/pyperf.h    | 70 +++++++++++++++++-
 .../selftests/bpf/progs/pyperf600_foreach.c   |  5 ++
 .../testing/selftests/bpf/progs/strobemeta.h  | 73 ++++++++++++++++++-
 .../selftests/bpf/progs/strobemeta_foreach.c  |  9 +++

let's split out strobemeta and pyperf refactorings into a separate patch from dedicated tests for bpf_for_each helper, they are logically quite different and independent

Quoted 56 lines
 7 files changed, 295 insertions(+), 4 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_helper.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_foreach.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_foreach.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +12 -0
index 867349e4ed9e..77396484fde7 100644
@@ -115,6 +115,12 @@ void test_verif_scale_pyperf600()
        scale_test("pyperf600.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_pyperf600_foreach(void)
+{
+       /* use the bpf_for_each helper*/
+       scale_test("pyperf600_foreach.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_pyperf600_nounroll()
 {
        /* no unroll at all.
@@ -165,6 +171,12 @@ void test_verif_scale_strobemeta()
        scale_test("strobemeta.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
+void test_verif_scale_strobemeta_foreach(void)
+{
+       /* use the bpf_for_each helper*/
+       scale_test("strobemeta_foreach.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_strobemeta_nounroll1()
 {
        /* no unroll, tiny loops */
tools/testing/selftests/bpf/prog_tests/for_each.c +6 -0
index 68eb12a287d4..529573a82334 100644
@@ -4,6 +4,7 @@
 #include <network_helpers.h>
 #include "for_each_hash_map_elem.skel.h"
 #include "for_each_array_map_elem.skel.h"
+#include "for_each_helper.skel.h"
 
 static unsigned int duration;
 
@@ -121,10 +122,70 @@ static void test_array_map(void)
        for_each_array_map_elem__destroy(skel);
 }
 
+static void test_for_each_helper(void)
+{
+       struct for_each_helper *skel;
+       __u32 retval;
+       int err;

tools/testing/selftests/bpf/prog_tests/for_each.c static void test_array_map(void) · line 139

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +10 -0
+
+       skel = for_each_helper__open_and_load();
+       if (!ASSERT_OK_PTR(skel, "for_each_helper__open_and_load"))
+               return;
+
+       skel->bss->nr_iterations = 100;
+       err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_prog),
+                               1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+                               &retval, &duration);
+       if (CHECK(err || retval, "bpf_for_each helper test_prog",

please don't use CHECK() in new test, stick to ASSERT_XXX()

Quoted 41 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +41 -0
+                 "err %d errno %d retval %d\n", err, errno, retval))
+               goto out;
+       ASSERT_EQ(skel->bss->nr_iterations_completed, skel->bss->nr_iterations,
+                 "nr_iterations mismatch");
+       ASSERT_EQ(skel->bss->g_output, (100 * 99) / 2, "wrong output");
+
+       /* test callback_fn returning 1 to stop iteration */
+       skel->bss->nr_iterations = 400;
+       skel->data->stop_index = 50;
+       err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_prog),
+                               1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+                               &retval, &duration);
+       if (CHECK(err || retval, "bpf_for_each helper test_prog",
+                 "err %d errno %d retval %d\n", err, errno, retval))
+               goto out;
+       ASSERT_EQ(skel->bss->nr_iterations_completed, skel->data->stop_index + 1,
+                 "stop_index not followed");
+       ASSERT_EQ(skel->bss->g_output, (50 * 49) / 2, "wrong output");
+
+       /* test passing in a null ctx */
+       skel->bss->nr_iterations = 10;
+       err = bpf_prog_test_run(bpf_program__fd(skel->progs.prog_null_ctx),
+                               1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+                               &retval, &duration);
+       if (CHECK(err || retval, "bpf_for_each helper prog_null_ctx",
+                 "err %d errno %d retval %d\n", err, errno, retval))
+               goto out;
+       ASSERT_EQ(skel->bss->nr_iterations_completed, skel->bss->nr_iterations,
+                 "nr_iterations mismatch");
+
+       /* test invalid flags */
+       err = bpf_prog_test_run(bpf_program__fd(skel->progs.prog_invalid_flags),
+                               1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+                               &retval, &duration);
+       if (CHECK(err || retval, "bpf_for_each helper prog_invalid_flags",
+                 "err %d errno %d retval %d\n", err, errno, retval))
+               goto out;
+       ASSERT_EQ(skel->bss->err, -EINVAL, "invalid_flags");
+
+out:
+       for_each_helper__destroy(skel);

tools/testing/selftests/bpf/prog_tests/for_each.c static void test_array_map(void) · line 190

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +4 -0
+}
+
 void test_for_each(void)
 {
        if (test__start_subtest("hash_map"))
                test_hash_map();
        if (test__start_subtest("array_map"))
                test_array_map();
+       if (test__start_subtest("for_each_helper"))
+               test_for_each_helper();

those hash_map and array_map are conceptually very different tests, it's probably best to have a separate file under prog_tests dedicated to this new helper.

Quoted 66 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +0 -0
 }
tools/testing/selftests/bpf/progs/for_each_helper.c new file +59 -0
new file mode 100644
index 000000000000..4404d0cb32a6
@@ -0,0 +1,69 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2021 Facebook */
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+
+char _license[] SEC("license") = "GPL";
+
+struct callback_ctx {
+       int output;
+};
+
+/* This should be set by the user program */
+u32 nr_iterations;
+u32 stop_index = -1;
+
+/* Making these global variables so that the userspace program
+ * can verify the output through the skeleton
+ */
+int nr_iterations_completed;
+int g_output;
+int err;
+
+static int callback_fn(__u32 index, void *data)
+{
+       struct callback_ctx *ctx = data;
+
+       if (index >= stop_index)
+               return 1;
+
+       ctx->output += index;
+
+       return 0;
+}
+
+static int empty_callback_fn(__u32 index, void *data)
+{
+       return 0;
+}
+
+SEC("tc")
+int test_prog(struct __sk_buff *skb)
+{
+       struct callback_ctx data = {};
+
+       nr_iterations_completed = bpf_for_each(nr_iterations, callback_fn, &data, 0);
+
+       g_output = data.output;
+
+       return 0;
+}
+
+SEC("tc")
+int prog_null_ctx(struct __sk_buff *skb)
+{
+       nr_iterations_completed = bpf_for_each(nr_iterations, empty_callback_fn, NULL, 0);
+
+       return 0;
+}

tools/testing/selftests/bpf/progs/for_each_helper.c line 69

Quoted 10 lines
tools/testing/selftests/bpf/progs/for_each_helper.c new file +10 -0
+
+SEC("tc")
+int prog_invalid_flags(struct __sk_buff *skb)
+{
+       struct callback_ctx data = {};
+
+       err = bpf_for_each(nr_iterations, callback_fn, &data, 1);
+
+       return 0;
+}

You mentioned that nested loops works, let's have a test for that.

[...]

#12 lore raw

PATCH 3/3 selftest/bpf/benchs: add bpf_for_each benchmark

In reply to Joanne Koong

Add benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.

Testing this on qemu on my dev machine on 1 thread, the data is as follows:

nr_iterations: 1
bpf_for_each helper - total callbacks called: 42.949 ± 1.404M/s

nr_iterations: 10
bpf_for_each helper - total callbacks called: 73.645 ± 2.077M/s

        nr_iterations: 100

bpf_for_each helper - total callbacks called: 73.058 ± 1.256M/s

        nr_iterations: 500

bpf_for_each helper - total callbacks called: 78.255 ± 2.845M/s

        nr_iterations: 1000

bpf_for_each helper - total callbacks called: 79.439 ± 1.805M/s

        nr_iterations: 5000

bpf_for_each helper - total callbacks called: 81.639 ± 2.053M/s

        nr_iterations: 10000

bpf_for_each helper - total callbacks called: 80.577 ± 1.824M/s

        nr_iterations: 50000

bpf_for_each helper - total callbacks called: 76.773 ± 1.578M/s

        nr_iterations: 100000

bpf_for_each helper - total callbacks called: 77.073 ± 2.200M/s

        nr_iterations: 500000

bpf_for_each helper - total callbacks called: 75.136 ± 0.552M/s

        nr_iterations: 1000000

bpf_for_each helper - total callbacks called: 76.364 ± 1.690M/s

From this data, we can see that we are able to run the loop at least 40 million times per second on an empty callback function.

From this data, we can also see that as the number of iterations increases, the overhead per iteration decreases and steadies towards a constant value.

---
 tools/testing/selftests/bpf/Makefile          |   3 +-
 tools/testing/selftests/bpf/bench.c           |   4 +
 .../selftests/bpf/benchs/bench_for_each.c     | 105 ++++++++++++++++++
 .../bpf/benchs/run_bench_for_each.sh          |  16 +++
 .../selftests/bpf/progs/for_each_helper.c     |  13 +++
 5 files changed, 140 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_for_each.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_for_each.sh
tools/testing/selftests/bpf/Makefile +2 -1
index f49cb5fc85af..b55fc72b8ef0 100644
@@ -537,7 +537,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o $(OUTPUT)/testing_helpers.o \
 		 $(OUTPUT)/bench_rename.o \
 		 $(OUTPUT)/bench_trigger.o \
 		 $(OUTPUT)/bench_ringbufs.o \
-		 $(OUTPUT)/bench_bloom_filter_map.o
+		 $(OUTPUT)/bench_bloom_filter_map.o \
+		 $(OUTPUT)/bench_for_each.o
 	$(call msg,BINARY,,$@)
 	$(Q)$(CC) $(LDFLAGS) -o $@ $(filter %.a %.o,$^) $(LDLIBS)
 
tools/testing/selftests/bpf/bench.c +4 -0
index cc4722f693e9..d8b3d537a700 100644
@@ -171,10 +171,12 @@ static const struct argp_option opts[] = {
 
 extern struct argp bench_ringbufs_argp;
 extern struct argp bench_bloom_map_argp;
+extern struct argp bench_for_each_argp;
 
 static const struct argp_child bench_parsers[] = {
 	{ &bench_ringbufs_argp, 0, "Ring buffers benchmark", 0 },
 	{ &bench_bloom_map_argp, 0, "Bloom filter map benchmark", 0 },
+	{ &bench_for_each_argp, 0, "bpf_for_each helper benchmark", 0 },
 	{},
 };
 
@@ -368,6 +370,7 @@ extern const struct bench bench_bloom_update;
 extern const struct bench bench_bloom_false_positive;
 extern const struct bench bench_hashmap_without_bloom;
 extern const struct bench bench_hashmap_with_bloom;
+extern const struct bench bench_for_each_helper;
 
 static const struct bench *benchs[] = {
 	&bench_count_global,
@@ -394,6 +397,7 @@ static const struct bench *benchs[] = {
 	&bench_bloom_false_positive,
 	&bench_hashmap_without_bloom,
 	&bench_hashmap_with_bloom,
+	&bench_for_each_helper,
 };
 
 static void setup_benchmark()
tools/testing/selftests/bpf/benchs/bench_for_each.c new file +105 -0

105 lines not on this page · raw message

tools/testing/selftests/bpf/benchs/run_bench_for_each.sh new file +16 -0
new file mode 100755
index 000000000000..5f11a1ad66d3
@@ -0,0 +1,16 @@
+#!/bin/bash
+# SPDX-License-Identifier: GPL-2.0
+
+source ./benchs/run_common.sh
+
+set -eufo pipefail
+
+for t in 1 4 8 12 16; do
+printf "\n"
+for i in 1 10 100 500 1000 5000 10000 50000 100000 500000 1000000; do
+subtitle "nr_iterations: $i, nr_threads: $t"
+	summarize "bpf_for_each helper - total callbacks called: " \
+	    "$($RUN_BENCH -p $t --nr_iters $i for-each-helper)"
+	printf "\n"
+done
+done
tools/testing/selftests/bpf/progs/for_each_helper.c +13 -0
index 4404d0cb32a6..b95551d99f75 100644
@@ -14,6 +14,8 @@ struct callback_ctx {
 u32 nr_iterations;
 u32 stop_index = -1;
 
+long hits;
+
 /* Making these global variables so that the userspace program
  * can verify the output through the skeleton
  */
@@ -67,3 +69,14 @@ int prog_invalid_flags(struct __sk_buff *skb)
 
 	return 0;
 }
+
+SEC("fentry/__x64_sys_getpgid")
+int benchmark(void *ctx)
+{
+	for (int i = 0; i < 1000; i++) {
+		bpf_for_each(nr_iterations, empty_callback_fn, NULL, 0);
+
+		__sync_add_and_fetch(&hits, nr_iterations);
+	}
+	return 0;
+}
Signature · 1 line
2.30.2
#13 lore raw

Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark

Quoted 5 lines · Joanne Koong

Add benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.

Testing this on qemu on my dev machine on 1 thread, the data is as follows:

Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?

-Toke

#14 lore raw

Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark

Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong

Add benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.

Quoted 8 lines
Quoted 2 lines

Testing this on qemu on my dev machine on 1 thread, the data is as follows:

Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?

Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of bpf_for_each() helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.

But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.

And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.

I read those numbers as "plenty fast" :)

Quoted 3 lines

-Toke

#15 lore raw

Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark

Quoted 28 lines · Andrii Nakryiko
Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong

Add benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.

Quoted 8 lines
Quoted 2 lines

Testing this on qemu on my dev machine on 1 thread, the data is as follows:

Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?

Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of bpf_for_each() helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.

But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.

Quoted 6 lines

And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.

I read those numbers as "plenty fast" :)

Hmm, okay, fair enough, but I think it would be good to have the "~12 ns per iteration" figure featured prominently in the commit message, then :)

-Toke

#16 lore raw

Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark

Quoted 36 lines · Toke Høiland-Jørgensen
Quoted 33 lines · Andrii Nakryiko
Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong

Add benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.

Quoted 8 lines
Quoted 2 lines

Testing this on qemu on my dev machine on 1 thread, the data is as follows:

Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?

Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of bpf_for_each() helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.

But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.

And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.

Quoted 5 lines
Quoted 1 line

I read those numbers as "plenty fast" :)

Hmm, okay, fair enough, but I think it would be good to have the "~12 ns per iteration" figure featured prominently in the commit message, then :)

We discussed with Joanne offline adding an ops_report_final() helper that will output both throughput (X ops/s) and latency/overhead ( (1000000000/X) ns/op), so that no one had to do any math.

Quoted 2 lines

-Toke

#17 lore raw

Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark

Quoted 39 lines · Andrii Nakryiko
Quoted 38 lines · Toke Høiland-Jørgensen
Quoted 34 lines · Andrii Nakryiko
Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong

Add benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.

Quoted 8 lines
Quoted 2 lines

Testing this on qemu on my dev machine on 1 thread, the data is as follows:

Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?

Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of bpf_for_each() helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.

But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.

And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.

I read those numbers as "plenty fast" :)

Quoted 7 lines
Quoted 3 lines

Hmm, okay, fair enough, but I think it would be good to have the "~12 ns per iteration" figure featured prominently in the commit message, then :)

We discussed with Joanne offline adding an ops_report_final() helper that will output both throughput (X ops/s) and latency/overhead ( (1000000000/X) ns/op), so that no one had to do any math.

Alright, sounds good, thanks!

-Toke

#18 lore raw

Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark

In reply to Joanne Koong
Quoted 31 lines · Joanne Koong

Add benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.

Testing this on qemu on my dev machine on 1 thread, the data is as follows:

nr_iterations: 1
bpf_for_each helper - total callbacks called: 42.949 ± 1.404M/s

nr_iterations: 10
bpf_for_each helper - total callbacks called: 73.645 ± 2.077M/s

        nr_iterations: 100

bpf_for_each helper - total callbacks called: 73.058 ± 1.256M/s

        nr_iterations: 500

bpf_for_each helper - total callbacks called: 78.255 ± 2.845M/s

        nr_iterations: 1000

bpf_for_each helper - total callbacks called: 79.439 ± 1.805M/s

        nr_iterations: 5000

bpf_for_each helper - total callbacks called: 81.639 ± 2.053M/s

        nr_iterations: 10000

bpf_for_each helper - total callbacks called: 80.577 ± 1.824M/s

        nr_iterations: 50000

bpf_for_each helper - total callbacks called: 76.773 ± 1.578M/s

Quoted 8 lines
        nr_iterations: 100000

bpf_for_each helper - total callbacks called: 77.073 ± 2.200M/s

        nr_iterations: 500000

bpf_for_each helper - total callbacks called: 75.136 ± 0.552M/s

        nr_iterations: 1000000

bpf_for_each helper - total callbacks called: 76.364 ± 1.690M/s

bit clear why numbers go down with increased nr_iterations, I'd expect them to stabilize. Try running bench with -a argument to set CPU affinity, that usually improves stability of test results

Quoted 8 lines

From this data, we can see that we are able to run the loop at least 40 million times per second on an empty callback function.

From this data, we can also see that as the number of iterations increases, the overhead per iteration decreases and steadies towards a constant value.

Quoted 7 lines
---
 tools/testing/selftests/bpf/Makefile          |   3 +-
 tools/testing/selftests/bpf/bench.c           |   4 +
 .../selftests/bpf/benchs/bench_for_each.c     | 105 ++++++++++++++++++
 .../bpf/benchs/run_bench_for_each.sh          |  16 +++
 .../selftests/bpf/progs/for_each_helper.c     |  13 +++
$ ls progs/*bench*
progs/bloom_filter_bench.c  progs/perfbuf_bench.c
progs/ringbuf_bench.c  progs/trigger_bench.c

let's keep the naming pattern

Quoted 4 lines
 5 files changed, 140 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_for_each.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_for_each.sh

[...]

#19 lore raw
In reply to Joanne Koong
Quoted 11 lines · Joanne Koong

This patchset add a new helper, bpf_for_each.

One of the complexities of using for loops in bpf programs is that the verifier needs to ensure that in every possibility of the loop logic, the loop will always terminate. As such, there is a limit on how many iterations the loop can do.

The bpf_for_each helper moves the loop logic into the kernel and can thereby guarantee that the loop will always terminate. The bpf_for_each helper simplifies a lot of the complexity the verifier needs to check, as well as removes the constraint on the number of loops able to be run.

Quoted 5 lines

From the test results, we see that using bpf_for_each in place of the traditional for loop led to a decrease in verification time and number of bpf instructions by 100%. The benchmark results show that as the number of iterations increases, the overhead per iteration decreases.

Small nit with the "by 100%" formulation: when giving such relative quantities 100% has a particular meaning, namely "eliminates entirely". Which this doesn't, obviously, it *almost* eliminates the verification overhead. So I'd change this to 99.5% instead (which is the actual value from your numbers in patch 2).

#20 lore raw
Quoted 18 lines · Toke Høiland-Jørgensen
Quoted 11 lines · Joanne Koong

This patchset add a new helper, bpf_for_each.

One of the complexities of using for loops in bpf programs is that the verifier needs to ensure that in every possibility of the loop logic, the loop will always terminate. As such, there is a limit on how many iterations the loop can do.

The bpf_for_each helper moves the loop logic into the kernel and can thereby guarantee that the loop will always terminate. The bpf_for_each helper simplifies a lot of the complexity the verifier needs to check, as well as removes the constraint on the number of loops able to be run.

Quoted 5 lines

From the test results, we see that using bpf_for_each in place
of the traditional for loop led to a decrease in verification time and number of bpf instructions by 100%. The benchmark results show that as the number of iterations increases, the overhead per iteration decreases.

Quoted 6 lines

Small nit with the "by 100%" formulation: when giving such relative quantities 100% has a particular meaning, namely "eliminates entirely". Which this doesn't, obviously, it *almost* eliminates the verification overhead. So I'd change this to 99.5% instead (which is the actual value from your numbers in patch 2).

Great point!! I will change this to "~99%" (and make this change in patch #2's commit message as well). Thanks for reviewing this patchset!