Skip to contentSkip to conversation

Add bpf_loop helper

PATCH Superseded Joanne Koong 3 participants 11 messages Nov 29, 2021 – Nov 30, 2021

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

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover Add bpf_loop helper

This patchset add a new helper, bpf_loop.

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_loop helper moves the loop logic into the kernel and can thereby guarantee that the loop will always terminate. The bpf_loop 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_loop in place of the traditional for loop led to a decrease in verification time and number of bpf instructions by ~99%. 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_loop
Patch 2 - tests
Patch 3 - use bpf_loop in strobemeta + pyperf600 and measure verifier performance Patch 4 - benchmark for throughput + latency of bpf_loop call

v2 -> v3:
~ Rerun benchmarks on physical machine, update results ~ Propagate original error codes in the verifier

v1 -> v2:
~ Change helper name to bpf_loop (instead of bpf_for_each)
~ Set max nr_loops (~8 million loops) for bpf_loop call
~ Split tests + strobemeta/pyperf600 changes into two patches ~ Add new ops_report_final helper for outputting throughput and latency

Joanne Koong (4):
bpf: Add bpf_loop helper
selftests/bpf: Add bpf_loop test selftests/bpf: measure bpf_loop verifier performance selftest/bpf/benchs: add bpf_loop benchmark

 include/linux/bpf.h                           |   1 +
 include/uapi/linux/bpf.h                      |  25 ++++
 kernel/bpf/bpf_iter.c                         |  35 +++++
 kernel/bpf/helpers.c                          |   2 +
 kernel/bpf/verifier.c                         |  88 ++++++-----
 tools/include/uapi/linux/bpf.h                |  25 ++++
 tools/testing/selftests/bpf/Makefile          |   4 +-
 tools/testing/selftests/bpf/bench.c           |  37 +++++
 tools/testing/selftests/bpf/bench.h           |   2 +
 .../selftests/bpf/benchs/bench_bpf_loop.c     | 105 +++++++++++++
 .../bpf/benchs/run_bench_bpf_loop.sh          |  15 ++
 .../selftests/bpf/benchs/run_common.sh        |  15 ++
 .../selftests/bpf/prog_tests/bpf_loop.c       | 138 ++++++++++++++++++
 .../bpf/prog_tests/bpf_verif_scale.c          |  12 ++
 tools/testing/selftests/bpf/progs/bpf_loop.c  |  99 +++++++++++++
 .../selftests/bpf/progs/bpf_loop_bench.c      |  26 ++++
 tools/testing/selftests/bpf/progs/pyperf.h    |  71 ++++++++-
 .../selftests/bpf/progs/pyperf600_bpf_loop.c  |   6 +
 .../testing/selftests/bpf/progs/strobemeta.h  |  75 +++++++++-
 .../selftests/bpf/progs/strobemeta_bpf_loop.c |   9 ++
 20 files changed, 751 insertions(+), 39 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_loop.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop_bench.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c
Signature · 1 line
2.30.2
#1 lore raw

PATCH v3 1/4 bpf: Add bpf_loop helper

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

long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags);

where long (*callback_fn)(u32 index, void *ctx);

bpf_loop invokes the "callback_fn" **nr_loops** times or until the callback_fn returns 1. The callback_fn can only return 0 or 1, and this is enforced by the verifier. The callback_fn index is zero-indexed.

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_loop (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_loop calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ Recursive callback_fns do not pass the verifier, due to the call stack for these being too deep.
~ The next patch will include the tests and benchmark

---
 include/linux/bpf.h            |  1 +
 include/uapi/linux/bpf.h       | 25 ++++++++++
 kernel/bpf/bpf_iter.c          | 35 ++++++++++++++
 kernel/bpf/helpers.c           |  2 +
 kernel/bpf/verifier.c          | 88 +++++++++++++++++++++-------------
 tools/include/uapi/linux/bpf.h | 25 ++++++++++
 6 files changed, 142 insertions(+), 34 deletions(-)
include/linux/bpf.h +1 -0
index cc7a0c36e7df..cad0829710be 100644
@@ -2164,6 +2164,7 @@ extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
 extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
 extern const struct bpf_func_proto bpf_kallsyms_lookup_name_proto;
 extern const struct bpf_func_proto bpf_find_vma_proto;
+extern const struct bpf_func_proto bpf_loop_proto;
 
 const struct bpf_func_proto *tracing_prog_func_proto(
   enum bpf_func_id func_id, const struct bpf_prog *prog);
include/uapi/linux/bpf.h +25 -0
index a69e4b04ffeb..211b43afd0fb 100644
@@ -4957,6 +4957,30 @@ union bpf_attr {
  *		**-ENOENT** if *task->mm* is NULL, or no vma contains *addr*.
  *		**-EBUSY** if failed to try lock mmap_lock.
  *		**-EINVAL** for invalid **flags**.
+ *
+ * long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_loops**, 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. Currently, nr_loops is
+ *		limited to 1 << 23 (~8 million) loops.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *		where **index** is the current index in the loop. The index
+ *		is zero-indexed.
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		loop. If return value is 1, the helper will skip the rest of
+ *		the loops and return. Other return values are not used now,
+ *		and will be rejected by the verifier.
+ *
+ *	Return
+ *		The number of loops performed, **-EINVAL** for invalid **flags**,
+ *		**-E2BIG** if **nr_loops** exceeds the maximum number of loops.
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5140,6 +5164,7 @@ union bpf_attr {
 	FN(skc_to_unix_sock),		\
 	FN(kallsyms_lookup_name),	\
 	FN(find_vma),			\
+	FN(loop),			\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
kernel/bpf/bpf_iter.c +35 -0
index b2ee45064e06..b7aef5b3416d 100644
@@ -714,3 +714,38 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = {
 	.arg3_type	= ARG_PTR_TO_STACK_OR_NULL,
 	.arg4_type	= ARG_ANYTHING,
 };
+
+/* maximum number of loops */
+#define MAX_LOOPS	BIT(23)
+
+BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
+	   u64, flags)
+{
+	bpf_callback_t callback = (bpf_callback_t)callback_fn;
+	u64 ret;
+	u32 i;
+
+	if (flags)
+		return -EINVAL;
+	if (nr_loops > MAX_LOOPS)
+		return -E2BIG;
+
+	for (i = 0; i < nr_loops; i++) {
+		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		/* return value: 0 - continue, 1 - stop and return */
+		if (ret)
+			return i + 1;
+	}
+
+	return i;
+}
+
+const struct bpf_func_proto bpf_loop_proto = {
+	.func		= bpf_loop,
+	.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..52188004a9c3 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_loop:
+		return &bpf_loop_proto;
 	default:
 		break;
 	}
kernel/bpf/verifier.c +54 -34

115 lines not on this page · raw message

tools/include/uapi/linux/bpf.h +25 -0
index a69e4b04ffeb..211b43afd0fb 100644
@@ -4957,6 +4957,30 @@ union bpf_attr {
  *		**-ENOENT** if *task->mm* is NULL, or no vma contains *addr*.
  *		**-EBUSY** if failed to try lock mmap_lock.
  *		**-EINVAL** for invalid **flags**.
+ *
+ * long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For **nr_loops**, 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. Currently, nr_loops is
+ *		limited to 1 << 23 (~8 million) loops.
+ *
+ *		long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ *		where **index** is the current index in the loop. The index
+ *		is zero-indexed.
+ *
+ *		If **callback_fn** returns 0, the helper will continue to the next
+ *		loop. If return value is 1, the helper will skip the rest of
+ *		the loops and return. Other return values are not used now,
+ *		and will be rejected by the verifier.
+ *
+ *	Return
+ *		The number of loops performed, **-EINVAL** for invalid **flags**,
+ *		**-E2BIG** if **nr_loops** exceeds the maximum number of loops.
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5140,6 +5164,7 @@ union bpf_attr {
 	FN(skc_to_unix_sock),		\
 	FN(kallsyms_lookup_name),	\
 	FN(find_vma),			\
+	FN(loop),			\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
Signature · 1 line
2.30.2
Acked-by on v3 1/4
#2 lore raw

Re: [PATCH v3 bpf-next 1/4] bpf: Add bpf_loop helper

Quoted 25 lines · Joanne Koong

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

long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags);

where long (*callback_fn)(u32 index, void *ctx);

bpf_loop invokes the "callback_fn" **nr_loops** times or until the callback_fn returns 1. The callback_fn can only return 0 or 1, and this is enforced by the verifier. The callback_fn index is zero-indexed.

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_loop (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_loop calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ Recursive callback_fns do not pass the verifier, due to the call stack for these being too deep.
~ The next patch will include the tests and benchmark

Quoted 2 lines

---

LGTM.

Quoted 8 lines
 include/linux/bpf.h            |  1 +
 include/uapi/linux/bpf.h       | 25 ++++++++++
 kernel/bpf/bpf_iter.c          | 35 ++++++++++++++
 kernel/bpf/helpers.c           |  2 +
 kernel/bpf/verifier.c          | 88 +++++++++++++++++++++-------------
 tools/include/uapi/linux/bpf.h | 25 ++++++++++
 6 files changed, 142 insertions(+), 34 deletions(-)

[...]

Acked-by on v3 1/4
#3 lore raw

Re: [PATCH v3 bpf-next 1/4] bpf: Add bpf_loop helper

In reply to Joanne Koong
Quoted 24 lines · Joanne Koong

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

long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags);

where long (*callback_fn)(u32 index, void *ctx);

bpf_loop invokes the "callback_fn" **nr_loops** times or until the callback_fn returns 1. The callback_fn can only return 0 or 1, and this is enforced by the verifier. The callback_fn index is zero-indexed.

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_loop (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_loop calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ Recursive callback_fns do not pass the verifier, due to the call stack for these being too deep.
~ The next patch will include the tests and benchmark

Quoted 1 line
#4 lore raw

PATCH v3 2/4 selftests/bpf: Add bpf_loop test

In reply to Joanne Koong

Add test for bpf_loop testing a variety of cases:
various nr_loops, null callback ctx, invalid flags, nested callbacks.

---
 .../selftests/bpf/prog_tests/bpf_loop.c       | 138 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/bpf_loop.c  |  99 +++++++++++++
 2 files changed, 237 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.c
tools/testing/selftests/bpf/prog_tests/bpf_loop.c new file +138 -0
new file mode 100644
index 000000000000..31b8e7715f07
@@ -0,0 +1,138 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2021 Facebook */
+
+#include <test_progs.h>
+#include <network_helpers.h>
+#include "bpf_loop.skel.h"
+
+static void check_nr_loops(struct bpf_loop *skel)
+{
+	__u32 retval, duration;
+	int err;
+
+	/* test 0 loops */
+	skel->bss->nr_loops = 0;
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_prog),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+	if (!ASSERT_OK(err, "err") || !ASSERT_OK(retval, "retval"))
+		return;
+	ASSERT_EQ(skel->bss->nr_loops_returned, skel->bss->nr_loops,
+		  "0 loops");
+
+	/* test 500 loops */
+	skel->bss->nr_loops = 500;
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_prog),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+	if (!ASSERT_OK(err, "err") ||
+	    !ASSERT_OK(retval, "retval"))
+		return;
+	ASSERT_EQ(skel->bss->nr_loops_returned, skel->bss->nr_loops,
+		  "500 loops");
+	ASSERT_EQ(skel->bss->g_output, (500 * 499) / 2, "g_output");
+
+	/* test exceeding the max limit */
+	skel->bss->nr_loops = -1;
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_prog),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+	if (!ASSERT_OK(err, "err") || !ASSERT_OK(retval, "retval"))
+		return;
+	ASSERT_EQ(skel->bss->err, -E2BIG, "over max limit");
+}
+
+static void check_callback_fn_stop(struct bpf_loop *skel)
+{
+	__u32 retval, duration;
+	int err;
+
+	skel->bss->nr_loops = 400;
+	skel->data->stop_index = 50;
+
+	/* testing that loop is stopped when callback_fn returns 1 */
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_prog),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+
+	if (!ASSERT_OK(err, "err") || !ASSERT_OK(retval, "retval"))
+		return;
+
+	ASSERT_EQ(skel->bss->nr_loops_returned, skel->data->stop_index + 1,
+		  "nr_loops_returned");
+	ASSERT_EQ(skel->bss->g_output, (50 * 49) / 2,
+		  "g_output");
+}
+
+static void check_null_callback_ctx(struct bpf_loop *skel)
+{
+	__u32 retval, duration;
+	int err;
+
+	skel->bss->nr_loops = 10;
+
+	/* check that user is able to pass in a null callback_ctx */
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.prog_null_ctx),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+
+	if (!ASSERT_OK(err, "err") || !ASSERT_OK(retval, "retval"))
+		return;
+
+	ASSERT_EQ(skel->bss->nr_loops_returned, skel->bss->nr_loops,
+		  "nr_loops_returned");
+}
+
+static void check_invalid_flags(struct bpf_loop *skel)
+{
+	__u32 retval, duration;
+	int err;
+
+	/* check that passing in non-zero flags returns -EINVAL */
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.prog_invalid_flags),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+
+	if (!ASSERT_OK(err, "err") || !ASSERT_OK(retval, "retval"))
+		return;
+
+	ASSERT_EQ(skel->bss->err, -EINVAL, "err");
+}
+
+static void check_nested_calls(struct bpf_loop *skel)
+{
+	__u32 nr_loops = 100, nested_callback_nr_loops = 4;
+	__u32 retval, duration;
+	int err;
+
+	skel->bss->nr_loops = nr_loops;
+	skel->bss->nested_callback_nr_loops = nested_callback_nr_loops;
+
+	/* check that nested calls are supported */
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.prog_nested_calls),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+	if (!ASSERT_OK(err, "err") || !ASSERT_OK(retval, "retval"))
+		return;
+	ASSERT_EQ(skel->bss->nr_loops_returned, nr_loops * nested_callback_nr_loops
+		  * nested_callback_nr_loops, "nr_loops_returned");
+	ASSERT_EQ(skel->bss->g_output, (4 * 3) / 2 * nested_callback_nr_loops
+		* nr_loops, "g_output");
+}
+
+void test_bpf_loop(void)
+{
+	struct bpf_loop *skel;
+
+	skel = bpf_loop__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "bpf_loop__open_and_load"))
+		return;
+
+	check_nr_loops(skel);
+	check_callback_fn_stop(skel);
+	check_null_callback_ctx(skel);
+	check_invalid_flags(skel);
+	check_nested_calls(skel);
+
+	bpf_loop__destroy(skel);
+}
tools/testing/selftests/bpf/progs/bpf_loop.c new file +99 -0

99 lines not on this page · raw message

Signature · 1 line
2.30.2
Acked-by on v3 2/4
#5 lore raw

Re: [PATCH v3 bpf-next 2/4] selftests/bpf: Add bpf_loop test

Quoted 6 lines · Joanne Koong

Add test for bpf_loop testing a variety of cases:
various nr_loops, null callback ctx, invalid flags, nested callbacks.

---

LGTM, one small nit below.

tools/testing/selftests/bpf/prog_tests/bpf_loop.c line 19

Quoted 12 lines
 .../selftests/bpf/prog_tests/bpf_loop.c       | 138 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/bpf_loop.c  |  99 +++++++++++++
 2 files changed, 237 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.c
tools/testing/selftests/bpf/prog_tests/bpf_loop.c new file +5 -0
+       err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_prog),
+                               1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+                               &retval, &duration);
+       if (!ASSERT_OK(err, "err") || !ASSERT_OK(retval, "retval"))
+               return;

Still think that usleep(1) is better and cleaner... pkt_v4 has nothing to do with what you are testing.

Quoted 5 lines
tools/testing/selftests/bpf/prog_tests/bpf_loop.c new file +5 -0
+       ASSERT_EQ(skel->bss->nr_loops_returned, skel->bss->nr_loops,
+                 "0 loops");
+
+       /* test 500 loops */
+       skel->bss->nr_loops = 500;

[...]

#6 lore raw

PATCH v3 3/4 selftests/bpf: measure bpf_loop verifier performance

In reply to Joanne Koong

This patch tests bpf_loop in pyperf and strobemeta, and measures the verifier performance of replacing the traditional for loop with bpf_loop.

The results are as follows:

~strobemeta~

Baseline
verification time 6808200 usec
stack depth 496
processed 554252 insns (limit 1000000) max_states_per_insn 16 total_states 15878 peak_states 13489 mark_read 3110 #192 verif_scale_strobemeta:OK (unrolled loop)

Using bpf_loop
verification time 31589 usec
stack depth 96+400
processed 1513 insns (limit 1000000) max_states_per_insn 2 total_states 106 peak_states 106 mark_read 60 #193 verif_scale_strobemeta_bpf_loop: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_loop

    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_bpf_loop:OK

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

---
 .../bpf/prog_tests/bpf_verif_scale.c          | 12 +++
 tools/testing/selftests/bpf/progs/pyperf.h    | 71 +++++++++++++++++-
 .../selftests/bpf/progs/pyperf600_bpf_loop.c  |  6 ++
 .../testing/selftests/bpf/progs/strobemeta.h  | 75 ++++++++++++++++++-
 .../selftests/bpf/progs/strobemeta_bpf_loop.c |  9 +++
 5 files changed, 169 insertions(+), 4 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +12 -0
index 27f5d8ea7964..1fb16f8dad56 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_bpf_loop(void)
+{
+	/* use the bpf_loop helper*/
+	scale_test("pyperf600_bpf_loop.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_bpf_loop(void)
+{
+	/* use the bpf_loop helper*/
+	scale_test("strobemeta_bpf_loop.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
+}
+
 void test_verif_scale_strobemeta_nounroll1()
 {
 	/* no unroll, tiny loops */
tools/testing/selftests/bpf/progs/pyperf.h +70 -1

93 lines not on this page · raw message

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

106 lines not on this page · raw message

tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c new file +9 -0
new file mode 100644
index 000000000000..e6f9f920e68a
@@ -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_BPF_LOOP
+#include "strobemeta.h"
Signature · 1 line
2.30.2
Acked-by on v3 3/4
#7 lore raw

Re: [PATCH v3 bpf-next 3/4] selftests/bpf: measure bpf_loop verifier performance

Quoted 39 lines · Joanne Koong

This patch tests bpf_loop in pyperf and strobemeta, and measures the verifier performance of replacing the traditional for loop with bpf_loop.

The results are as follows:

~strobemeta~

Baseline
verification time 6808200 usec
stack depth 496
processed 554252 insns (limit 1000000) max_states_per_insn 16 total_states 15878 peak_states 13489 mark_read 3110 #192 verif_scale_strobemeta:OK (unrolled loop)

Using bpf_loop
verification time 31589 usec
stack depth 96+400
processed 1513 insns (limit 1000000) max_states_per_insn 2 total_states 106 peak_states 106 mark_read 60 #193 verif_scale_strobemeta_bpf_loop: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_loop

    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_bpf_loop:OK
Quoted 5 lines

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

---

Quoted 9 lines
 .../bpf/prog_tests/bpf_verif_scale.c          | 12 +++
 tools/testing/selftests/bpf/progs/pyperf.h    | 71 +++++++++++++++++-
 .../selftests/bpf/progs/pyperf600_bpf_loop.c  |  6 ++
 .../testing/selftests/bpf/progs/strobemeta.h  | 75 ++++++++++++++++++-
 .../selftests/bpf/progs/strobemeta_bpf_loop.c |  9 +++
 5 files changed, 169 insertions(+), 4 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c

[...]

Quoted 17 lines
                /* Unwind python stack */
                for (int i = 0; i < STACK_MAX_LEN; ++i) {
                        if (frame_ptr && get_frame_data(frame_ptr, pidData, &frame, &sym)) {
tools/testing/selftests/bpf/progs/pyperf.h +1 -0
@@ -251,6 +319,7 @@ int __on_event(struct bpf_raw_tracepoint_args *ctx)
                                frame_ptr = frame.f_back;
                        }
                }
+#endif /* USE_BPF_LOOP */
                event->stack_complete = frame_ptr == NULL;
        } else {
                event->stack_complete = 1;
tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c new file +0 -0
new file mode 100644
index 000000000000..bde8baed4ca6

tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c line 2

Quoted 2 lines
tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c new file +2 -0
@@ -0,0 +1,6 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2021 Facebook

nit: should be /* ... */

Quoted 4 lines
tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c new file +4 -0
+
+#define STACK_MAX_LEN 600
+#define USE_BPF_LOOP
+#include "pyperf.h"

[...]

tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c line 2

Quoted 8 lines
tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c new file +2 -0
new file mode 100644
index 000000000000..e6f9f920e68a
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+// Copyright (c) 2021 Facebook

same

Quoted 10 lines
tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c new file +7 -1
+
+#define STROBE_MAX_INTS 2
+#define STROBE_MAX_STRS 25
+#define STROBE_MAX_MAPS 100
+#define STROBE_MAX_MAP_ENTRIES 20
+#define USE_BPF_LOOP
+#include "strobemeta.h"
--

2.30.2

#8 lore raw

PATCH v3 4/4 selftest/bpf/benchs: add bpf_loop benchmark

In reply to Joanne Koong

Add benchmark to measure the throughput and latency of the bpf_loop call.

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

        nr_loops: 10

bpf_loop - throughput: 198.519 ± 0.155 M ops/s, latency: 5.037 ns/op

        nr_loops: 100

bpf_loop - throughput: 247.448 ± 0.305 M ops/s, latency: 4.041 ns/op

        nr_loops: 500

bpf_loop - throughput: 260.839 ± 0.380 M ops/s, latency: 3.834 ns/op

        nr_loops: 1000

bpf_loop - throughput: 262.806 ± 0.629 M ops/s, latency: 3.805 ns/op

        nr_loops: 5000

bpf_loop - throughput: 264.211 ± 1.508 M ops/s, latency: 3.785 ns/op

        nr_loops: 10000

bpf_loop - throughput: 265.366 ± 3.054 M ops/s, latency: 3.768 ns/op

        nr_loops: 50000

bpf_loop - throughput: 235.986 ± 20.205 M ops/s, latency: 4.238 ns/op

        nr_loops: 100000

bpf_loop - throughput: 264.482 ± 0.279 M ops/s, latency: 3.781 ns/op

        nr_loops: 500000

bpf_loop - throughput: 309.773 ± 87.713 M ops/s, latency: 3.228 ns/op

        nr_loops: 1000000

bpf_loop - throughput: 262.818 ± 4.143 M ops/s, latency: 3.805 ns/op

From this data, we can see that the latency per loop decreases as the number of loops increases. On this particular machine, each loop had an overhead of about ~4 ns, and we were able to run ~250 million loops per second.

---
 tools/testing/selftests/bpf/Makefile          |   4 +-
 tools/testing/selftests/bpf/bench.c           |  37 ++++++
 tools/testing/selftests/bpf/bench.h           |   2 +
 .../selftests/bpf/benchs/bench_bpf_loop.c     | 105 ++++++++++++++++++
 .../bpf/benchs/run_bench_bpf_loop.sh          |  15 +++
 .../selftests/bpf/benchs/run_common.sh        |  15 +++
 .../selftests/bpf/progs/bpf_loop_bench.c      |  26 +++++
 7 files changed, 203 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_loop.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop_bench.c
tools/testing/selftests/bpf/Makefile +3 -1
index 35684d61aaeb..a6c0e92c86a1 100644
@@ -531,6 +531,7 @@ $(OUTPUT)/bench_trigger.o: $(OUTPUT)/trigger_bench.skel.h
 $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \
 			    $(OUTPUT)/perfbuf_bench.skel.h
 $(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.skel.h
+$(OUTPUT)/bench_bpf_loop.o: $(OUTPUT)/bpf_loop_bench.skel.h
 $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ)
 $(OUTPUT)/bench: LDLIBS += -lm
 $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -540,7 +541,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.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_bpf_loop.o
 	$(call msg,BINARY,,$@)
 	$(Q)$(CC) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
 
tools/testing/selftests/bpf/bench.c +37 -0
index c75e7ee28746..3d6082b97a56 100644
@@ -134,6 +134,39 @@ void hits_drops_report_final(struct bench_res res[], int res_cnt)
 	       total_ops_mean, total_ops_stddev);
 }
 
+void ops_report_progress(int iter, struct bench_res *res, long delta_ns)
+{
+	double hits_per_sec, hits_per_prod;
+
+	hits_per_sec = res->hits / 1000000.0 / (delta_ns / 1000000000.0);
+	hits_per_prod = hits_per_sec / env.producer_cnt;
+
+	printf("Iter %3d (%7.3lfus): ", iter, (delta_ns - 1000000000) / 1000.0);
+
+	printf("hits %8.3lfM/s (%7.3lfM/prod)\n", hits_per_sec, hits_per_prod);
+}
+
+void ops_report_final(struct bench_res res[], int res_cnt)
+{
+	double hits_mean = 0.0, hits_stddev = 0.0;
+	int i;
+
+	for (i = 0; i < res_cnt; i++)
+		hits_mean += res[i].hits / 1000000.0 / (0.0 + res_cnt);
+
+	if (res_cnt > 1)  {
+		for (i = 0; i < res_cnt; i++)
+			hits_stddev += (hits_mean - res[i].hits / 1000000.0) *
+				       (hits_mean - res[i].hits / 1000000.0) /
+				       (res_cnt - 1.0);
+
+		hits_stddev = sqrt(hits_stddev);
+	}
+	printf("Summary: throughput %8.3lf \u00B1 %5.3lf M ops/s (%7.3lfM ops/prod), ",
+	       hits_mean, hits_stddev, hits_mean / env.producer_cnt);
+	printf("latency %8.3lf ns/op\n", 1000.0 / hits_mean * env.producer_cnt);
+}
+
 const char *argp_program_version = "benchmark";
 const char *argp_program_bug_address = "<[email protected]>";
 const char argp_program_doc[] =
@@ -171,10 +204,12 @@ static const struct argp_option opts[] = {
 
 extern struct argp bench_ringbufs_argp;
 extern struct argp bench_bloom_map_argp;
+extern struct argp bench_bpf_loop_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_bpf_loop_argp, 0, "bpf_loop helper benchmark", 0 },
 	{},
 };
 
@@ -373,6 +408,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_bpf_loop;
 
 static const struct bench *benchs[] = {
 	&bench_count_global,
@@ -404,6 +440,7 @@ static const struct bench *benchs[] = {
 	&bench_bloom_false_positive,
 	&bench_hashmap_without_bloom,
 	&bench_hashmap_with_bloom,
+	&bench_bpf_loop,
 };
 
 static void setup_benchmark()
tools/testing/selftests/bpf/bench.h +2 -0
index 624c6b11501f..50785503756b 100644
@@ -59,6 +59,8 @@ void hits_drops_report_progress(int iter, struct bench_res *res, long delta_ns);
 void hits_drops_report_final(struct bench_res res[], int res_cnt);
 void false_hits_report_progress(int iter, struct bench_res *res, long delta_ns);
 void false_hits_report_final(struct bench_res res[], int res_cnt);
+void ops_report_progress(int iter, struct bench_res *res, long delta_ns);
+void ops_report_final(struct bench_res res[], int res_cnt);
 
 static inline __u64 get_time_ns() {
 	struct timespec t;
tools/testing/selftests/bpf/benchs/bench_bpf_loop.c new file +105 -0

105 lines not on this page · raw message

tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh new file +15 -0
new file mode 100755
index 000000000000..ff740e80ba84
@@ -0,0 +1,15 @@
+#!/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
+for i in 1 10 100 500 1000 5000 10000 50000 100000 500000 1000000; do
+subtitle "nr_loops: $i, nr_threads: $t"
+	summarize_ops "bpf_loop: " \
+	    "$($RUN_BENCH -p $t --nr_loops $i bpf-loop)"
+	printf "\n"
+done
+done
tools/testing/selftests/bpf/benchs/run_common.sh +15 -0
index 9a16be78b180..6c5e6023a69f 100644
@@ -33,6 +33,14 @@ function percentage()
 	echo "$*" | sed -E "s/.*Percentage\s=\s+([0-9]+\.[0-9]+).*/\1/"
 }
 
+function ops()
+{
+	echo -n "throughput: "
+	echo -n "$*" | sed -E "s/.*throughput\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+\sM\sops\/s).*/\1/"
+	echo -n -e ", latency: "
+	echo "$*" | sed -E "s/.*latency\s+([0-9]+\.[0-9]+\sns\/op).*/\1/"
+}
+
 function total()
 {
 	echo "$*" | sed -E "s/.*total operations\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/"
@@ -52,6 +60,13 @@ function summarize_percentage()
 	printf "%-20s %s%%\n" "$bench" "$(percentage $summary)"
 }
 
+function summarize_ops()
+{
+	bench="$1"
+	summary=$(echo $2 | tail -n1)
+	printf "%-20s %s\n" "$bench" "$(ops $summary)"
+}
+
 function summarize_total()
 {
 	bench="$1"
tools/testing/selftests/bpf/progs/bpf_loop_bench.c new file +26 -0
new file mode 100644
index 000000000000..ff00621858c0
@@ -0,0 +1,26 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2021 Facebook
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+
+char _license[] SEC("license") = "GPL";
+
+u32 nr_loops;
+long hits;
+
+static int empty_callback(__u32 index, void *data)
+{
+	return 0;
+}
+
+SEC("fentry/__x64_sys_getpgid")
+int benchmark(void *ctx)
+{
+	for (int i = 0; i < 1000; i++) {
+		bpf_loop(nr_loops, empty_callback, NULL, 0);
+
+		__sync_add_and_fetch(&hits, nr_loops);
+	}
+	return 0;
+}
Signature · 1 line
2.30.2
Acked-by on v3 4/4
#9 lore raw

Re: [PATCH v3 bpf-next 4/4] selftest/bpf/benchs: add bpf_loop benchmark

Quoted 36 lines · Joanne Koong

Add benchmark to measure the throughput and latency of the bpf_loop call.

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

        nr_loops: 10

bpf_loop - throughput: 198.519 ± 0.155 M ops/s, latency: 5.037 ns/op

        nr_loops: 100

bpf_loop - throughput: 247.448 ± 0.305 M ops/s, latency: 4.041 ns/op

        nr_loops: 500

bpf_loop - throughput: 260.839 ± 0.380 M ops/s, latency: 3.834 ns/op

        nr_loops: 1000

bpf_loop - throughput: 262.806 ± 0.629 M ops/s, latency: 3.805 ns/op

        nr_loops: 5000

bpf_loop - throughput: 264.211 ± 1.508 M ops/s, latency: 3.785 ns/op

        nr_loops: 10000

bpf_loop - throughput: 265.366 ± 3.054 M ops/s, latency: 3.768 ns/op

        nr_loops: 50000

bpf_loop - throughput: 235.986 ± 20.205 M ops/s, latency: 4.238 ns/op

        nr_loops: 100000

bpf_loop - throughput: 264.482 ± 0.279 M ops/s, latency: 3.781 ns/op

        nr_loops: 500000

bpf_loop - throughput: 309.773 ± 87.713 M ops/s, latency: 3.228 ns/op

        nr_loops: 1000000

bpf_loop - throughput: 262.818 ± 4.143 M ops/s, latency: 3.805 ns/op

Quoted 7 lines

From this data, we can see that the latency per loop decreases as the number of loops increases. On this particular machine, each loop had an overhead of about ~4 ns, and we were able to run ~250 million loops per second.

---

LGTM.

Quoted 11 lines
 tools/testing/selftests/bpf/Makefile          |   4 +-
 tools/testing/selftests/bpf/bench.c           |  37 ++++++
 tools/testing/selftests/bpf/bench.h           |   2 +
 .../selftests/bpf/benchs/bench_bpf_loop.c     | 105 ++++++++++++++++++
 .../bpf/benchs/run_bench_bpf_loop.sh          |  15 +++
 .../selftests/bpf/benchs/run_common.sh        |  15 +++
 .../selftests/bpf/progs/bpf_loop_bench.c      |  26 +++++
 7 files changed, 203 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_loop.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop_bench.c

[...]

Acked-by on v3 4/4
#10 lore raw

Re: [PATCH v3 bpf-next 4/4] selftest/bpf/benchs: add bpf_loop benchmark

In reply to Joanne Koong
Quoted 33 lines · Joanne Koong

Add benchmark to measure the throughput and latency of the bpf_loop call.

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

        nr_loops: 10

bpf_loop - throughput: 198.519 ± 0.155 M ops/s, latency: 5.037 ns/op

        nr_loops: 100

bpf_loop - throughput: 247.448 ± 0.305 M ops/s, latency: 4.041 ns/op

        nr_loops: 500

bpf_loop - throughput: 260.839 ± 0.380 M ops/s, latency: 3.834 ns/op

        nr_loops: 1000

bpf_loop - throughput: 262.806 ± 0.629 M ops/s, latency: 3.805 ns/op

        nr_loops: 5000

bpf_loop - throughput: 264.211 ± 1.508 M ops/s, latency: 3.785 ns/op

        nr_loops: 10000

bpf_loop - throughput: 265.366 ± 3.054 M ops/s, latency: 3.768 ns/op

        nr_loops: 50000

bpf_loop - throughput: 235.986 ± 20.205 M ops/s, latency: 4.238 ns/op

        nr_loops: 100000

bpf_loop - throughput: 264.482 ± 0.279 M ops/s, latency: 3.781 ns/op

        nr_loops: 500000

bpf_loop - throughput: 309.773 ± 87.713 M ops/s, latency: 3.228 ns/op

        nr_loops: 1000000
Quoted 8 lines

bpf_loop - throughput: 262.818 ± 4.143 M ops/s, latency: 3.805 ns/op

From this data, we can see that the latency per loop decreases as the number of loops increases. On this particular machine, each loop had an overhead of about ~4 ns, and we were able to run ~250 million loops per second.