[PATCH v8 bpf-next 6/7] bpf: allow for tailcalls in BPF subprograms for x64 JIT

[PATCH v8 bpf-next 6/7] bpf: allow for tailcalls in BPF subprograms for x64 JIT

[Maciej Fijalkowski]

Relax verifier's restriction that was meant to forbid tailcall usage
when subprog count was higher than 1.

Also, do not max out the stack depth of program that utilizes tailcalls.

Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
---
 kernel/bpf/verifier.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 644ee9286ecf..05034cff89ca 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4384,10 +4384,12 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
 	case BPF_FUNC_tail_call:
 		if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
 			goto error;
+#if !defined(CONFIG_X86_64) || !defined(CONFIG_BPF_JIT_ALWAYS_ON)
 		if (env->subprog_cnt > 1) {
 			verbose(env, "tail_calls are not allowed in programs with bpf-to-bpf calls\n");
 			return -EINVAL;
 		}
+#endif
 		break;
 	case BPF_FUNC_perf_event_read:
 	case BPF_FUNC_perf_event_output:
@@ -10633,7 +10635,9 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)
 			 * the program array.
 			 */
 			prog->cb_access = 1;
+#if !defined(CONFIG_X86_64) || !defined(CONFIG_BPF_JIT_ALWAYS_ON)
 			env->prog->aux->stack_depth = MAX_BPF_STACK;
+#endif
 			env->prog->aux->max_pkt_offset = MAX_PACKET_OFF;
 
 			/* mark bpf_tail_call as different opcode to avoid
-- 
2.20.1

Re: [PATCH v8 bpf-next 6/7] bpf: allow for tailcalls in BPF subprograms for x64 JIT

[Andrii Nakryiko]

On Wed, Sep 16, 2020 at 3:54 PM Maciej Fijalkowski
<maciej.fijalkowski@intel.com> wrote:
>
> Relax verifier's restriction that was meant to forbid tailcall usage
> when subprog count was higher than 1.
>
> Also, do not max out the stack depth of program that utilizes tailcalls.
>
> Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> ---

Maciej,

Only patches 6 and 7 arrived (a while ago) and seems like the other
patches are lost and not going to come. Do you mind resending entire
patch set?

[...]

Re: [PATCH v8 bpf-next 6/7] bpf: allow for tailcalls in BPF subprograms for x64 JIT

[Maciej Fijalkowski]

On Thu, Sep 17, 2020 at 02:03:32PM -0700, Andrii Nakryiko wrote:
> On Wed, Sep 16, 2020 at 3:54 PM Maciej Fijalkowski
> <maciej.fijalkowski@intel.com> wrote:
> >
> > Relax verifier's restriction that was meant to forbid tailcall usage
> > when subprog count was higher than 1.
> >
> > Also, do not max out the stack depth of program that utilizes tailcalls.
> >
> > Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> > ---
> 
> Maciej,
> 
> Only patches 6 and 7 arrived (a while ago) and seems like the other
> patches are lost and not going to come. Do you mind resending entire
> patch set?

Sure. Vger lately has been giving me a hard time, thought that maybe rest
of set would eventually arrive, similarly to what Toke experienced I
guess.

> 
> [...]

Re: [PATCH v8 bpf-next 6/7] bpf: allow for tailcalls in BPF subprograms for x64 JIT

[Alexei Starovoitov]

On Thu, Sep 17, 2020 at 3:51 PM Maciej Fijalkowski
<maciej.fijalkowski@intel.com> wrote:
>
> On Thu, Sep 17, 2020 at 02:03:32PM -0700, Andrii Nakryiko wrote:
> > On Wed, Sep 16, 2020 at 3:54 PM Maciej Fijalkowski
> > <maciej.fijalkowski@intel.com> wrote:
> > >
> > > Relax verifier's restriction that was meant to forbid tailcall usage
> > > when subprog count was higher than 1.
> > >
> > > Also, do not max out the stack depth of program that utilizes tailcalls.
> > >
> > > Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> > > ---
> >
> > Maciej,
> >
> > Only patches 6 and 7 arrived (a while ago) and seems like the other
> > patches are lost and not going to come. Do you mind resending entire
> > patch set?
>
> Sure. Vger lately has been giving me a hard time, thought that maybe rest
> of set would eventually arrive, similarly to what Toke experienced I
> guess.

I've got the patches. No need to resend.

[PATCH v8 bpf-next 7/7] selftests: bpf: introduce tailcall_bpf2bpf test suite

[Maciej Fijalkowski]

Add four tests to tailcalls selftest explicitly named
"tailcall_bpf2bpf2_X" as their purpose is to validate that combination
of tailcalls with bpf2bpf calls are working properly.

Include also test_verifier's test cases, one negative that will exercise
check_max_stack_depth check against caller's stack being larger than 256
bytes. Second one should be accepted by verifier as caller's stack depth
is smaller than 256 and from subprogram that has the tailcall new stack
frame is intentionally created, so the total stack depth is > 256 but
this last stack frame will be unwinded before the actual tailcall.

Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
---
 .../selftests/bpf/prog_tests/tailcalls.c      | 332 ++++++++++++++++++
 .../selftests/bpf/progs/tailcall_bpf2bpf1.c   |  38 ++
 .../selftests/bpf/progs/tailcall_bpf2bpf2.c   |  37 ++
 .../selftests/bpf/progs/tailcall_bpf2bpf3.c   |  57 +++
 .../selftests/bpf/progs/tailcall_bpf2bpf4.c   |  61 ++++
 tools/testing/selftests/bpf/verifier/calls.c  |  53 +++
 6 files changed, 578 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_bpf2bpf1.c
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_bpf2bpf2.c
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_bpf2bpf3.c
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c

diff --git a/tools/testing/selftests/bpf/prog_tests/tailcalls.c b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
index bb8fe646dd9f..ee27d68d2a1c 100644
--- a/tools/testing/selftests/bpf/prog_tests/tailcalls.c
+++ b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
@@ -1,5 +1,6 @@
 // SPDX-License-Identifier: GPL-2.0
 #include <test_progs.h>
+#include <network_helpers.h>
 
 /* test_tailcall_1 checks basic functionality by patching multiple locations
  * in a single program for a single tail call slot with nop->jmp, jmp->nop
@@ -472,6 +473,329 @@ static void test_tailcall_5(void)
 	bpf_object__close(obj);
 }
 
+/* test_tailcall_bpf2bpf_1 purpose is to make sure that tailcalls are working
+ * correctly in correlation with BPF subprograms
+ */
+static void test_tailcall_bpf2bpf_1(void)
+{
+	int err, map_fd, prog_fd, main_fd, i;
+	struct bpf_map *prog_array;
+	struct bpf_program *prog;
+	struct bpf_object *obj;
+	__u32 retval, duration;
+	char prog_name[32];
+
+	err = bpf_prog_load("tailcall_bpf2bpf1.o", BPF_PROG_TYPE_SCHED_CLS,
+			    &obj, &prog_fd);
+	if (CHECK_FAIL(err))
+		return;
+
+	prog = bpf_object__find_program_by_title(obj, "classifier");
+	if (CHECK_FAIL(!prog))
+		goto out;
+
+	main_fd = bpf_program__fd(prog);
+	if (CHECK_FAIL(main_fd < 0))
+		goto out;
+
+	prog_array = bpf_object__find_map_by_name(obj, "jmp_table");
+	if (CHECK_FAIL(!prog_array))
+		goto out;
+
+	map_fd = bpf_map__fd(prog_array);
+	if (CHECK_FAIL(map_fd < 0))
+		goto out;
+
+	/* nop -> jmp */
+	for (i = 0; i < bpf_map__def(prog_array)->max_entries; i++) {
+		snprintf(prog_name, sizeof(prog_name), "classifier/%i", i);
+
+		prog = bpf_object__find_program_by_title(obj, prog_name);
+		if (CHECK_FAIL(!prog))
+			goto out;
+
+		prog_fd = bpf_program__fd(prog);
+		if (CHECK_FAIL(prog_fd < 0))
+			goto out;
+
+		err = bpf_map_update_elem(map_fd, &i, &prog_fd, BPF_ANY);
+		if (CHECK_FAIL(err))
+			goto out;
+	}
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				0, &retval, &duration);
+	CHECK(err || retval != 1, "tailcall",
+	      "err %d errno %d retval %d\n", err, errno, retval);
+
+	/* jmp -> nop, call subprog that will do tailcall */
+	i = 1;
+	err = bpf_map_delete_elem(map_fd, &i);
+	if (CHECK_FAIL(err))
+		goto out;
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				0, &retval, &duration);
+	CHECK(err || retval != 0, "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+
+	/* make sure that subprog can access ctx and entry prog that
+	 * called this subprog can properly return
+	 */
+	i = 0;
+	err = bpf_map_delete_elem(map_fd, &i);
+	if (CHECK_FAIL(err))
+		goto out;
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				0, &retval, &duration);
+	CHECK(err || retval != sizeof(pkt_v4) * 2,
+	      "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+out:
+	bpf_object__close(obj);
+}
+
+/* test_tailcall_bpf2bpf_2 checks that the count value of the tail call limit
+ * enforcement matches with expectations when tailcall is preceded with
+ * bpf2bpf call.
+ */
+static void test_tailcall_bpf2bpf_2(void)
+{
+	int err, map_fd, prog_fd, main_fd, data_fd, i, val;
+	struct bpf_map *prog_array, *data_map;
+	struct bpf_program *prog;
+	struct bpf_object *obj;
+	__u32 retval, duration;
+	char buff[128] = {};
+
+	err = bpf_prog_load("tailcall_bpf2bpf2.o", BPF_PROG_TYPE_SCHED_CLS,
+			    &obj, &prog_fd);
+	if (CHECK_FAIL(err))
+		return;
+
+	prog = bpf_object__find_program_by_title(obj, "classifier");
+	if (CHECK_FAIL(!prog))
+		goto out;
+
+	main_fd = bpf_program__fd(prog);
+	if (CHECK_FAIL(main_fd < 0))
+		goto out;
+
+	prog_array = bpf_object__find_map_by_name(obj, "jmp_table");
+	if (CHECK_FAIL(!prog_array))
+		goto out;
+
+	map_fd = bpf_map__fd(prog_array);
+	if (CHECK_FAIL(map_fd < 0))
+		goto out;
+
+	prog = bpf_object__find_program_by_title(obj, "classifier/0");
+	if (CHECK_FAIL(!prog))
+		goto out;
+
+	prog_fd = bpf_program__fd(prog);
+	if (CHECK_FAIL(prog_fd < 0))
+		goto out;
+
+	i = 0;
+	err = bpf_map_update_elem(map_fd, &i, &prog_fd, BPF_ANY);
+	if (CHECK_FAIL(err))
+		goto out;
+
+	err = bpf_prog_test_run(main_fd, 1, buff, sizeof(buff), 0,
+				&duration, &retval, NULL);
+	CHECK(err || retval != 1, "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+
+	data_map = bpf_object__find_map_by_name(obj, "tailcall.bss");
+	if (CHECK_FAIL(!data_map || !bpf_map__is_internal(data_map)))
+		return;
+
+	data_fd = bpf_map__fd(data_map);
+	if (CHECK_FAIL(map_fd < 0))
+		return;
+
+	i = 0;
+	err = bpf_map_lookup_elem(data_fd, &i, &val);
+	CHECK(err || val != 33, "tailcall count", "err %d errno %d count %d\n",
+	      err, errno, val);
+
+	i = 0;
+	err = bpf_map_delete_elem(map_fd, &i);
+	if (CHECK_FAIL(err))
+		goto out;
+
+	err = bpf_prog_test_run(main_fd, 1, buff, sizeof(buff), 0,
+				&duration, &retval, NULL);
+	CHECK(err || retval != 0, "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+out:
+	bpf_object__close(obj);
+}
+
+/* test_tailcall_bpf2bpf_3 checks that non-trivial amount of stack (up to
+ * 256 bytes) can be used within bpf subprograms that have the tailcalls
+ * in them
+ */
+static void test_tailcall_bpf2bpf_3(void)
+{
+	int err, map_fd, prog_fd, main_fd, i;
+	struct bpf_map *prog_array;
+	struct bpf_program *prog;
+	struct bpf_object *obj;
+	__u32 retval, duration;
+	char prog_name[32];
+
+	err = bpf_prog_load("tailcall_bpf2bpf3.o", BPF_PROG_TYPE_SCHED_CLS,
+			    &obj, &prog_fd);
+	if (CHECK_FAIL(err))
+		return;
+
+	prog = bpf_object__find_program_by_title(obj, "classifier");
+	if (CHECK_FAIL(!prog))
+		goto out;
+
+	main_fd = bpf_program__fd(prog);
+	if (CHECK_FAIL(main_fd < 0))
+		goto out;
+
+	prog_array = bpf_object__find_map_by_name(obj, "jmp_table");
+	if (CHECK_FAIL(!prog_array))
+		goto out;
+
+	map_fd = bpf_map__fd(prog_array);
+	if (CHECK_FAIL(map_fd < 0))
+		goto out;
+
+	for (i = 0; i < bpf_map__def(prog_array)->max_entries; i++) {
+		snprintf(prog_name, sizeof(prog_name), "classifier/%i", i);
+
+		prog = bpf_object__find_program_by_title(obj, prog_name);
+		if (CHECK_FAIL(!prog))
+			goto out;
+
+		prog_fd = bpf_program__fd(prog);
+		if (CHECK_FAIL(prog_fd < 0))
+			goto out;
+
+		err = bpf_map_update_elem(map_fd, &i, &prog_fd, BPF_ANY);
+		if (CHECK_FAIL(err))
+			goto out;
+	}
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				&duration, &retval, NULL);
+	CHECK(err || retval != sizeof(pkt_v4) * 3,
+	      "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+
+	i = 1;
+	err = bpf_map_delete_elem(map_fd, &i);
+	if (CHECK_FAIL(err))
+		goto out;
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				&duration, &retval, NULL);
+	CHECK(err || retval != sizeof(pkt_v4),
+	      "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+
+	i = 0;
+	err = bpf_map_delete_elem(map_fd, &i);
+	if (CHECK_FAIL(err))
+		goto out;
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				&duration, &retval, NULL);
+	CHECK(err || retval != sizeof(pkt_v4) * 2,
+	      "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+out:
+	bpf_object__close(obj);
+}
+
+/* test_tailcall_bpf2bpf_4 checks that tailcall counter is correctly preserved
+ * across tailcalls combined with bpf2bpf calls. for making sure that tailcall
+ * counter behaves correctly, bpf program will go through following flow:
+ *
+ * entry -> entry_subprog -> tailcall0 -> bpf_func0 -> subprog0 ->
+ * -> tailcall1 -> bpf_func1 -> subprog1 -> tailcall2 -> bpf_func2 ->
+ * subprog2 [here bump global counter] --------^
+ *
+ * We go through first two tailcalls and start counting from the subprog2 where
+ * the loop begins. At the end of the test make sure that the global counter is
+ * equal to 31, because tailcall counter includes the first two tailcalls
+ * whereas global counter is incremented only on loop presented on flow above.
+ */
+static void test_tailcall_bpf2bpf_4(void)
+{
+	int err, map_fd, prog_fd, main_fd, data_fd, i, val;
+	struct bpf_map *prog_array, *data_map;
+	struct bpf_program *prog;
+	struct bpf_object *obj;
+	__u32 retval, duration;
+	char prog_name[32];
+
+	err = bpf_prog_load("tailcall_bpf2bpf4.o", BPF_PROG_TYPE_SCHED_CLS,
+			    &obj, &prog_fd);
+	if (CHECK_FAIL(err))
+		return;
+
+	prog = bpf_object__find_program_by_title(obj, "classifier");
+	if (CHECK_FAIL(!prog))
+		goto out;
+
+	main_fd = bpf_program__fd(prog);
+	if (CHECK_FAIL(main_fd < 0))
+		goto out;
+
+	prog_array = bpf_object__find_map_by_name(obj, "jmp_table");
+	if (CHECK_FAIL(!prog_array))
+		goto out;
+
+	map_fd = bpf_map__fd(prog_array);
+	if (CHECK_FAIL(map_fd < 0))
+		goto out;
+
+	for (i = 0; i < bpf_map__def(prog_array)->max_entries; i++) {
+		snprintf(prog_name, sizeof(prog_name), "classifier/%i", i);
+
+		prog = bpf_object__find_program_by_title(obj, prog_name);
+		if (CHECK_FAIL(!prog))
+			goto out;
+
+		prog_fd = bpf_program__fd(prog);
+		if (CHECK_FAIL(prog_fd < 0))
+			goto out;
+
+		err = bpf_map_update_elem(map_fd, &i, &prog_fd, BPF_ANY);
+		if (CHECK_FAIL(err))
+			goto out;
+	}
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				&duration, &retval, NULL);
+	CHECK(err || retval != sizeof(pkt_v4) * 3, "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+
+	data_map = bpf_object__find_map_by_name(obj, "tailcall.bss");
+	if (CHECK_FAIL(!data_map || !bpf_map__is_internal(data_map)))
+		return;
+
+	data_fd = bpf_map__fd(data_map);
+	if (CHECK_FAIL(map_fd < 0))
+		return;
+
+	i = 0;
+	err = bpf_map_lookup_elem(data_fd, &i, &val);
+	CHECK(err || val != 31, "tailcall count", "err %d errno %d count %d\n",
+	      err, errno, val);
+
+out:
+	bpf_object__close(obj);
+}
+
 void test_tailcalls(void)
 {
 	if (test__start_subtest("tailcall_1"))
@@ -484,4 +808,12 @@ void test_tailcalls(void)
 		test_tailcall_4();
 	if (test__start_subtest("tailcall_5"))
 		test_tailcall_5();
+	if (test__start_subtest("tailcall_bpf2bpf_1"))
+		test_tailcall_bpf2bpf_1();
+	if (test__start_subtest("tailcall_bpf2bpf_2"))
+		test_tailcall_bpf2bpf_2();
+	if (test__start_subtest("tailcall_bpf2bpf_3"))
+		test_tailcall_bpf2bpf_3();
+	if (test__start_subtest("tailcall_bpf2bpf_4"))
+		test_tailcall_bpf2bpf_4();
 }
diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf1.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf1.c
new file mode 100644
index 000000000000..e72ca5869b58
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf1.c
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 2);
+	__uint(key_size, sizeof(__u32));
+	__uint(value_size, sizeof(__u32));
+} jmp_table SEC(".maps");
+
+#define TAIL_FUNC(x) 				\
+	SEC("classifier/" #x)			\
+	int bpf_func_##x(struct __sk_buff *skb)	\
+	{					\
+		return x;			\
+	}
+TAIL_FUNC(0)
+TAIL_FUNC(1)
+
+static __attribute__ ((noinline))
+int subprog_tail(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 0);
+
+	return skb->len * 2;
+}
+
+SEC("classifier")
+int entry(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 1);
+
+	return subprog_tail(skb);
+}
+
+char __license[] SEC("license") = "GPL";
+int _version SEC("version") = 1;
diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf2.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf2.c
new file mode 100644
index 000000000000..1f7fc46628e4
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf2.c
@@ -0,0 +1,37 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 1);
+	__uint(key_size, sizeof(__u32));
+	__uint(value_size, sizeof(__u32));
+} jmp_table SEC(".maps");
+
+static __attribute__ ((noinline))
+int subprog_tail(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 0);
+	return 1;
+}
+
+static volatile int count;
+
+SEC("classifier/0")
+int bpf_func_0(struct __sk_buff *skb)
+{
+	count++;
+	return subprog_tail(skb);
+}
+
+SEC("classifier")
+int entry(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 0);
+
+	return 0;
+}
+
+char __license[] SEC("license") = "GPL";
+int _version SEC("version") = 1;
diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf3.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf3.c
new file mode 100644
index 000000000000..2f61abce83ca
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf3.c
@@ -0,0 +1,57 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 2);
+	__uint(key_size, sizeof(__u32));
+	__uint(value_size, sizeof(__u32));
+} jmp_table SEC(".maps");
+
+static __attribute__ ((noinline))
+int subprog_tail2(struct __sk_buff *skb)
+{
+	volatile char arr[64] = {};
+
+	bpf_tail_call(skb, &jmp_table, 1);
+
+	return skb->len;
+}
+
+static __attribute__ ((noinline))
+int subprog_tail(struct __sk_buff *skb)
+{
+	volatile char arr[64] = {};
+
+	bpf_tail_call(skb, &jmp_table, 0);
+
+	return skb->len * 2;
+}
+
+SEC("classifier/0")
+int bpf_func_0(struct __sk_buff *skb)
+{
+	volatile char arr[128] = {};
+
+	return subprog_tail2(skb);
+}
+
+SEC("classifier/1")
+int bpf_func_1(struct __sk_buff *skb)
+{
+	volatile char arr[128] = {};
+
+	return skb->len * 3;
+}
+
+SEC("classifier")
+int entry(struct __sk_buff *skb)
+{
+	volatile char arr[128] = {};
+
+	return subprog_tail(skb);
+}
+
+char __license[] SEC("license") = "GPL";
+int _version SEC("version") = 1;
diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
new file mode 100644
index 000000000000..686511535f83
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 3);
+	__uint(key_size, sizeof(__u32));
+	__uint(value_size, sizeof(__u32));
+} jmp_table SEC(".maps");
+
+static volatile int count;
+
+static __attribute__ ((noinline))
+int subprog_tail_2(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 2);
+	return skb->len * 3;
+}
+
+static __attribute__ ((noinline))
+int subprog_tail_1(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 1);
+	return skb->len * 2;
+}
+
+static __attribute__ ((noinline))
+int subprog_tail(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 0);
+	return skb->len;
+}
+
+SEC("classifier/1")
+int bpf_func_1(struct __sk_buff *skb)
+{
+	return subprog_tail_2(skb);
+}
+
+SEC("classifier/2")
+int bpf_func_2(struct __sk_buff *skb)
+{
+	count++;
+	return subprog_tail_2(skb);
+}
+
+SEC("classifier/0")
+int bpf_func_0(struct __sk_buff *skb)
+{
+	return subprog_tail_1(skb);
+}
+
+SEC("classifier")
+int entry(struct __sk_buff *skb)
+{
+	return subprog_tail(skb);
+}
+
+char __license[] SEC("license") = "GPL";
+int _version SEC("version") = 1;
diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
index 94258c6b5235..dc4603adb9eb 100644
--- a/tools/testing/selftests/bpf/verifier/calls.c
+++ b/tools/testing/selftests/bpf/verifier/calls.c
@@ -780,6 +780,59 @@
 	.errstr = "combined stack size",
 	.result = REJECT,
 },
+{
+	"calls: stack overflow for bpf2bpf calls combined with tailcall",
+	.insns = {
+	/* prog 1 */
+	BPF_ST_MEM(BPF_B, BPF_REG_10, -128, 0),
+	BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1),
+	BPF_EXIT_INSN(),
+
+	/* prog 2 */
+	BPF_ST_MEM(BPF_B, BPF_REG_10, -192, 0),
+	BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1),
+	BPF_EXIT_INSN(),
+
+	/*prog 3, caller's stack depth > 256 */
+	BPF_MOV64_IMM(BPF_REG_3, 0),
+	BPF_LD_MAP_FD(BPF_REG_2, 0),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call),
+	BPF_MOV64_IMM(BPF_REG_0, 1),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.errstr = "Cannot do bpf_tail_call in subprog",
+	.fixup_prog1 = { 7 },
+	.result = REJECT,
+},
+{
+	"calls: bpf2bpf calls combined with tailcall",
+	.insns = {
+	/* prog 1 */
+	BPF_ST_MEM(BPF_B, BPF_REG_10, -128, 0),
+	BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1),
+	BPF_EXIT_INSN(),
+
+	/* prog 2 */
+	BPF_ST_MEM(BPF_B, BPF_REG_10, -64, 0),
+	BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1),
+	BPF_EXIT_INSN(),
+
+	/* prog 3, caller's stack depth < 256; we are free to introduce here new
+	 * stack frame which will be unwinded before the tailcall
+	 */
+	BPF_ST_MEM(BPF_B, BPF_REG_10, -192, 0),
+	BPF_MOV64_IMM(BPF_REG_3, 0),
+	BPF_LD_MAP_FD(BPF_REG_2, 0),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call),
+	BPF_MOV64_IMM(BPF_REG_0, 1),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.fixup_prog1 = { 8 },
+	.result = ACCEPT,
+	.retval = 42,
+},
 {
 	"calls: stack depth check using three frames. test1",
 	.insns = {
-- 
2.20.1

Re: [PATCH v8 bpf-next 0/7] bpf: tailcalls in BPF subprograms

[Alexei Starovoitov]

On Wed, Sep 16, 2020 at 2:16 PM Maciej Fijalkowski
<maciej.fijalkowski@intel.com> wrote:
>
> Changelog:
>
> v7->v8:
> - teach bpf_patch_insn_data to adjust insn_idx of tailcall insn
> - address case of clearing tail call counter when bpf2bpf with tailcalls
>   are mixed
> - drop unnecessary checks against cbpf in JIT
> - introduce more tailcall_bpf2bpf[X] selftests that are making sure the
>   combination of tailcalls with bpf2bpf calls works correctly
> - add test cases to test_verifier to make sure logic from
>   check_max_stack_depth that limits caller's stack depth down to 256 is
>   correct
> - move the main patch to appear after the one that limits the caller's
>   stack depth so that 'has_tail_call' can be used by 'tail_call_reachable'
>   logic

Thanks a lot for your hard work on this set. 5 month effort!
I think it's a huge milestone that will enable cilium, cloudflare, katran to
use bpf functions. Removing always_inline will improve performance.
Switching to global functions with function-by-function verification
will drastically improve program load times.
libbpf has full support for subprogram composition and call relocations.
Until now these verifier and libbpf features were impossible to use in XDP
programs, since most of them use tail_calls.
It's great to see all these building blocks finally coming together.

I've applied the set with few changes.
In patch 4 I've removed ifdefs and redundant ().
In patch 5 removed redundant !tail_call_reachable check.
In patch 6 replaced CONFIG_JIT_ALWAYS_ON dependency with
jit_requested && IS_ENABLED(CONFIG_X86_64).
It's more user friendly.
I also added patch 7 that checks that ld_abs and tail_call are only
allowed in subprograms that return 'int'.
I felt that the fix is simple enough, so I just pushed it, since
without it the set is not safe. Please review it here:
https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=09b28d76eac48e922dc293da1aa2b2b85c32aeee
I'll address any issues in the followups.
Because of the above changes I tweaked patch 8 to increase test coverage
with ld_abs and combination of global/static subprogs.
Also did s/__attribute__((noinline))/__noinline/.

John and Daniel,
I wasn't able to test it on cilium programs.
When you have a chance please give it a thorough run.
tail_call poke logic is delicate.

Lorenz,
if you can test it on cloudflare progs would be awesome.

Thanks a lot everyone!

Re: [PATCH v8 bpf-next 0/7] bpf: tailcalls in BPF subprograms

[Maciej Fijalkowski]

On Thu, Sep 17, 2020 at 08:26:34PM -0700, Alexei Starovoitov wrote:
> On Wed, Sep 16, 2020 at 2:16 PM Maciej Fijalkowski
> <maciej.fijalkowski@intel.com> wrote:
> >
> > Changelog:
> >
> > v7->v8:
> > - teach bpf_patch_insn_data to adjust insn_idx of tailcall insn
> > - address case of clearing tail call counter when bpf2bpf with tailcalls
> >   are mixed
> > - drop unnecessary checks against cbpf in JIT
> > - introduce more tailcall_bpf2bpf[X] selftests that are making sure the
> >   combination of tailcalls with bpf2bpf calls works correctly
> > - add test cases to test_verifier to make sure logic from
> >   check_max_stack_depth that limits caller's stack depth down to 256 is
> >   correct
> > - move the main patch to appear after the one that limits the caller's
> >   stack depth so that 'has_tail_call' can be used by 'tail_call_reachable'
> >   logic
> 
> Thanks a lot for your hard work on this set. 5 month effort!

Thanks for the whole collaboration! It was quite a ride :)

> I think it's a huge milestone that will enable cilium, cloudflare, katran to
> use bpf functions. Removing always_inline will improve performance.
> Switching to global functions with function-by-function verification
> will drastically improve program load times.
> libbpf has full support for subprogram composition and call relocations.
> Until now these verifier and libbpf features were impossible to use in XDP
> programs, since most of them use tail_calls.
> It's great to see all these building blocks finally coming together.
> 
> I've applied the set with few changes.
> In patch 4 I've removed ifdefs and redundant ().
> In patch 5 removed redundant !tail_call_reachable check.
> In patch 6 replaced CONFIG_JIT_ALWAYS_ON dependency with
> jit_requested && IS_ENABLED(CONFIG_X86_64).
> It's more user friendly.
> I also added patch 7 that checks that ld_abs and tail_call are only
> allowed in subprograms that return 'int'.

Thank you for this last touch! I went through patches and I agree with the
changes.

> I felt that the fix is simple enough, so I just pushed it, since
> without it the set is not safe. Please review it here:
> https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=09b28d76eac48e922dc293da1aa2b2b85c32aeee

LGTM.

> I'll address any issues in the followups.
> Because of the above changes I tweaked patch 8 to increase test coverage
> with ld_abs and combination of global/static subprogs.
> Also did s/__attribute__((noinline))/__noinline/.
> 
> John and Daniel,
> I wasn't able to test it on cilium programs.
> When you have a chance please give it a thorough run.
> tail_call poke logic is delicate.
> 
> Lorenz,
> if you can test it on cloudflare progs would be awesome.
> 
> Thanks a lot everyone!

Re: [PATCH v8 bpf-next 0/7] bpf: tailcalls in BPF subprograms

[Lorenz Bauer]

On Fri, 18 Sep 2020 at 04:26, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
[...]
>
> Lorenz,
> if you can test it on cloudflare progs would be awesome.

Our programs all bpf_tail_call from the topmost function, so no calls
from subprogs. I stripped out our FORCE_INLINE flag, recompiled and
ran our testsuite. cls_redirect.c (also in the kernel selftests) has a
test failure that I currently can't explain, but I don't have the time
to look at it in detail right now.

Hopefully I can get back to this next week.

Best
Lorenz

--
Lorenz Bauer  |  Systems Engineer
6th Floor, County Hall/The Riverside Building, SE1 7PB, UK

www.cloudflare.com

Re: [PATCH v8 bpf-next 0/7] bpf: tailcalls in BPF subprograms

[Andrii Nakryiko]

On Wed, Sep 23, 2020 at 9:12 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> On Fri, 18 Sep 2020 at 04:26, Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> [...]
> >
> > Lorenz,
> > if you can test it on cloudflare progs would be awesome.
>
> Our programs all bpf_tail_call from the topmost function, so no calls
> from subprogs. I stripped out our FORCE_INLINE flag, recompiled and
> ran our testsuite. cls_redirect.c (also in the kernel selftests) has a
> test failure that I currently can't explain, but I don't have the time
> to look at it in detail right now.
>

I've already converted test_cls_redirect.c in selftest to have
__noinline variant. And it works fine. There are only 4 helper
functions that can't be converted to a sub-program (pkt_parse_ipv4,
pkt_parse_ipv6, and three buffer manipulation helpers) because they
are accepting a pointer to a stack from a calling function, which
won't work with subprograms. But all the other functions were
trivially converted to __noinline and keep working.

> Hopefully I can get back to this next week.
>
> Best
> Lorenz
>
> --
> Lorenz Bauer  |  Systems Engineer
> 6th Floor, County Hall/The Riverside Building, SE1 7PB, UK
>
> www.cloudflare.com

Re: [PATCH v8 bpf-next 0/7] bpf: tailcalls in BPF subprograms

[Lorenz Bauer]

On Wed, 23 Sep 2020 at 17:24, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
>
> On Wed, Sep 23, 2020 at 9:12 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
> >
> > On Fri, 18 Sep 2020 at 04:26, Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > [...]
> > >
> > > Lorenz,
> > > if you can test it on cloudflare progs would be awesome.
> >
> > Our programs all bpf_tail_call from the topmost function, so no calls
> > from subprogs. I stripped out our FORCE_INLINE flag, recompiled and
> > ran our testsuite. cls_redirect.c (also in the kernel selftests) has a
> > test failure that I currently can't explain, but I don't have the time
> > to look at it in detail right now.
> >
>
> I've already converted test_cls_redirect.c in selftest to have
> __noinline variant. And it works fine. There are only 4 helper
> functions that can't be converted to a sub-program (pkt_parse_ipv4,
> pkt_parse_ipv6, and three buffer manipulation helpers) because they
> are accepting a pointer to a stack from a calling function, which
> won't work with subprograms. But all the other functions were
> trivially converted to __noinline and keep working.

Yeah, that is very possible. Keep in mind though that our internal
version has since become more complex, and also has a more
comprehensive test suite. I wasn't sounding the alarms, it's just an
FYI that I appreciate the work that went into this and have taken a
look, but that I need to do some more digging :)

-- 
Lorenz Bauer  |  Systems Engineer
6th Floor, County Hall/The Riverside Building, SE1 7PB, UK

www.cloudflare.com

Re: [PATCH v8 bpf-next 0/7] bpf: tailcalls in BPF subprograms

[Andrii Nakryiko]

On Wed, Sep 23, 2020 at 9:43 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> On Wed, 23 Sep 2020 at 17:24, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
> >
> > On Wed, Sep 23, 2020 at 9:12 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
> > >
> > > On Fri, 18 Sep 2020 at 04:26, Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > [...]
> > > >
> > > > Lorenz,
> > > > if you can test it on cloudflare progs would be awesome.
> > >
> > > Our programs all bpf_tail_call from the topmost function, so no calls
> > > from subprogs. I stripped out our FORCE_INLINE flag, recompiled and
> > > ran our testsuite. cls_redirect.c (also in the kernel selftests) has a
> > > test failure that I currently can't explain, but I don't have the time
> > > to look at it in detail right now.
> > >
> >
> > I've already converted test_cls_redirect.c in selftest to have
> > __noinline variant. And it works fine. There are only 4 helper
> > functions that can't be converted to a sub-program (pkt_parse_ipv4,
> > pkt_parse_ipv6, and three buffer manipulation helpers) because they
> > are accepting a pointer to a stack from a calling function, which
> > won't work with subprograms. But all the other functions were
> > trivially converted to __noinline and keep working.
>
> Yeah, that is very possible. Keep in mind though that our internal
> version has since become more complex, and also has a more
> comprehensive test suite. I wasn't sounding the alarms, it's just an
> FYI that I appreciate the work that went into this and have taken a
> look, but that I need to do some more digging :)
>


> cls_redirect.c (also in the kernel selftests) has a test failure that

This sounded like there is a kernel selftest failure in cls_redirect.c
after you removed FORCE_INLINE flag. So I was curious where the new
failure is and whether it's in those 5 functions that just can't be
not-always_inlined.


> --
> Lorenz Bauer  |  Systems Engineer
> 6th Floor, County Hall/The Riverside Building, SE1 7PB, UK
>
> www.cloudflare.com

Re: [PATCH v8 bpf-next 0/7] bpf: tailcalls in BPF subprograms

[Alexei Starovoitov]

On Wed, Sep 23, 2020 at 9:11 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> On Fri, 18 Sep 2020 at 04:26, Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> [...]
> >
> > Lorenz,
> > if you can test it on cloudflare progs would be awesome.
>
> Our programs all bpf_tail_call from the topmost function, so no calls
> from subprogs. I stripped out our FORCE_INLINE flag, recompiled and
> ran our testsuite. cls_redirect.c (also in the kernel selftests) has a
> test failure that I currently can't explain, but I don't have the time
> to look at it in detail right now.

selftests's test_cls_redirect.c does not have any tail calls,
so it's not an interesting target.
But your internal code relying on tail_call and until today
you could not use subprograms at all.
It doesn't matter that you do tail_call out of topmost function.
The verifier would disallow subprogs, so you were missing
on lots of new functionality.
What I'm suggesting to try is to keep your code as-is
(with tail_call in topmost) and simply remove always_inline.
Let the compiler decide on better code layout.
That will improve performance and most likely improve verification time too.
If you convert some of the subprograms into global functions then
you will be able to use function-by-function verification which will
drastically improve verification time.

Same thing for cilium. Their progs use tail_calls and because of that
couldn't use subprogs at all.
I think John was saying that prog load time is important for cilium.
The answer is to use global functions.
Now with tail_calls being compatible with subprogs all that is available.