[PATCH bpf-next v4 0/4] bpf: Fix tailcall infinite loop caused by freplace

[PATCH bpf-next v4 0/4] bpf: Fix tailcall infinite loop caused by freplace

[Leon Hwang]

Previously, I fixed a tailcall infinite loop issue caused by trampoline[0].

At this time, I fix a tailcall infinite loop issue caused by tailcall and
freplace combination by preventing updating extended prog to prog_array map
and preventing extending tail callee prog with freplace:

1. If a prog or its subprog has been extended by freplace prog, the prog
   can not be updated to prog_array map.
2. If a prog has been updated to prog_array map, it or its subprog can not
   be extended by freplace prog.

v3 -> v4:
  * Address comments from Eduard:
    * Rename 'tail_callee_cnt' to 'prog_array_member_cnt'.
    * Add comment to 'prog_array_member_cnt'.
    * Use a mutex to protect 'is_extended' and 'prog_array_member_cnt'.

v2 -> v3:
  * Address comments from Alexei:
    * Stop hacking JIT.
    * Prevent the specific use case at attach/update time.

v1 -> v2:
  * Address comment from Eduard:
    * Explain why nop5 and xor/nop3 are swapped at prologue.
  * Address comment from Alexei:
    * Disallow attaching tail_call_reachable freplace prog to
      not-tail_call_reachable target in verifier.
  * Update "bpf, arm64: Fix tailcall infinite loop caused by freplace" with
    latest arm64 JIT code.

Links:
[0] https://lore.kernel.org/bpf/20230912150442.2009-1-hffilwlqm@gmail.com/

Leon Hwang (4):
  bpf: Prevent updating extended prog to prog_array map
  bpf: Prevent extending tail callee prog with freplace prog
  selftests/bpf: Add a test case to confirm a tailcall infinite loop
    issue has been prevented
  selftests/bpf: Add cases to test tailcall in freplace

 include/linux/bpf.h                           |   3 +
 kernel/bpf/arraymap.c                         |  30 ++-
 kernel/bpf/core.c                             |   1 +
 kernel/bpf/syscall.c                          |  53 ++++-
 .../selftests/bpf/prog_tests/tailcalls.c      | 196 +++++++++++++++++-
 .../tailcall_bpf2bpf_hierarchy_freplace.c     |  30 +++
 .../testing/selftests/bpf/progs/tc_bpf2bpf.c  |  37 +++-
 7 files changed, 335 insertions(+), 15 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_bpf2bpf_hierarchy_freplace.c

-- 
2.44.0

[PATCH bpf-next v4 1/4] bpf: Prevent updating extended prog to prog_array map

[Leon Hwang]

This patch partially prevents a potential infinite loop issue caused by
combination of tailcal and freplace.

For example:

tc_bpf2bpf.c:

// SPDX-License-Identifier: GPL-2.0

\#include <linux/bpf.h>
\#include <bpf/bpf_helpers.h>

__noinline
int subprog_tc(struct __sk_buff *skb)
{
	return skb->len * 2;
}

SEC("tc")
int entry_tc(struct __sk_buff *skb)
{
	return subprog_tc(skb);
}

char __license[] SEC("license") = "GPL";

tailcall_freplace.c:

// 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");

int count = 0;

SEC("freplace")
int entry_freplace(struct __sk_buff *skb)
{
	count++;
	bpf_tail_call_static(skb, &jmp_table, 0);
	return count;
}

char __license[] SEC("license") = "GPL";

The attach target of entry_freplace is subprog_tc, and the tail callee
in entry_freplace is entry_tc.

Then, the infinite loop will be entry_tc -> subprog_tc -> entry_freplace
--tailcall-> entry_tc, because tail_call_cnt in entry_freplace will count
from zero for every time of entry_freplace execution. Kernel will panic,
like:

[   15.310490] BUG: TASK stack guard page was hit at (____ptrval____)
(stack is (____ptrval____)..(____ptrval____))
[   15.310490] Oops: stack guard page: 0000 [#1] PREEMPT SMP NOPTI
[   15.310490] CPU: 1 PID: 89 Comm: test_progs Tainted: G           OE
   6.10.0-rc6-g026dcdae8d3e-dirty #72
[   15.310490] Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX,
1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
[   15.310490] RIP: 0010:bpf_prog_3a140cef239a4b4f_subprog_tail+0x14/0x53
[   15.310490] Code: cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc
cc cc cc cc cc f3 0f 1e fa 0f 1f 44 00 00 0f 1f 00 55 48 89 e5 f3 0f 1e
fa <50> 50 53 41 55 48 89 fb 49 bd 00 2a 46 82 98 9c ff ff 48 89 df 4c
[   15.310490] RSP: 0018:ffffb500c0aa0000 EFLAGS: 00000202
[   15.310490] RAX: ffffb500c0aa0028 RBX: ffff9c98808b7e00 RCX:
0000000000008cb5
[   15.310490] RDX: 0000000000000000 RSI: ffff9c9882462a00 RDI:
ffff9c98808b7e00
[   15.310490] RBP: ffffb500c0aa0000 R08: 0000000000000000 R09:
0000000000000000
[   15.310490] R10: 0000000000000001 R11: 0000000000000000 R12:
ffffb500c01af000
[   15.310490] R13: ffffb500c01cd000 R14: 0000000000000000 R15:
0000000000000000
[   15.310490] FS:  00007f133b665140(0000) GS:ffff9c98bbd00000(0000)
knlGS:0000000000000000
[   15.310490] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[   15.310490] CR2: ffffb500c0a9fff8 CR3: 0000000102478000 CR4:
00000000000006f0
[   15.310490] Call Trace:
[   15.310490]  <#DF>
[   15.310490]  ? die+0x36/0x90
[   15.310490]  ? handle_stack_overflow+0x4d/0x60
[   15.310490]  ? exc_double_fault+0x117/0x1a0
[   15.310490]  ? asm_exc_double_fault+0x23/0x30
[   15.310490]  ? bpf_prog_3a140cef239a4b4f_subprog_tail+0x14/0x53
[   15.310490]  </#DF>
[   15.310490]  <TASK>
[   15.310490]  bpf_prog_85781a698094722f_entry+0x4c/0x64
[   15.310490]  bpf_prog_1c515f389a9059b4_entry2+0x19/0x1b
[   15.310490]  ...
[   15.310490]  bpf_prog_85781a698094722f_entry+0x4c/0x64
[   15.310490]  bpf_prog_1c515f389a9059b4_entry2+0x19/0x1b
[   15.310490]  bpf_test_run+0x210/0x370
[   15.310490]  ? bpf_test_run+0x128/0x370
[   15.310490]  bpf_prog_test_run_skb+0x388/0x7a0
[   15.310490]  __sys_bpf+0xdbf/0x2c40
[   15.310490]  ? clockevents_program_event+0x52/0xf0
[   15.310490]  ? lock_release+0xbf/0x290
[   15.310490]  __x64_sys_bpf+0x1e/0x30
[   15.310490]  do_syscall_64+0x68/0x140
[   15.310490]  entry_SYSCALL_64_after_hwframe+0x76/0x7e
[   15.310490] RIP: 0033:0x7f133b52725d
[   15.310490] Code: ff c3 66 2e 0f 1f 84 00 00 00 00 00 90 f3 0f 1e fa
48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f
05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d 8b bb 0d 00 f7 d8 64 89 01 48
[   15.310490] RSP: 002b:00007ffddbc10258 EFLAGS: 00000206 ORIG_RAX:
0000000000000141
[   15.310490] RAX: ffffffffffffffda RBX: 00007ffddbc10828 RCX:
00007f133b52725d
[   15.310490] RDX: 0000000000000050 RSI: 00007ffddbc102a0 RDI:
000000000000000a
[   15.310490] RBP: 00007ffddbc10270 R08: 0000000000000000 R09:
00007ffddbc102a0
[   15.310490] R10: 0000000000000064 R11: 0000000000000206 R12:
0000000000000004
[   15.310490] R13: 0000000000000000 R14: 0000558ec4c24890 R15:
00007f133b6ed000
[   15.310490]  </TASK>
[   15.310490] Modules linked in: bpf_testmod(OE)
[   15.310490] ---[ end trace 0000000000000000 ]---
[   15.310490] RIP: 0010:bpf_prog_3a140cef239a4b4f_subprog_tail+0x14/0x53
[   15.310490] Code: cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc
cc cc cc cc cc f3 0f 1e fa 0f 1f 44 00 00 0f 1f 00 55 48 89 e5 f3 0f 1e
fa <50> 50 53 41 55 48 89 fb 49 bd 00 2a 46 82 98 9c ff ff 48 89 df 4c
[   15.310490] RSP: 0018:ffffb500c0aa0000 EFLAGS: 00000202
[   15.310490] RAX: ffffb500c0aa0028 RBX: ffff9c98808b7e00 RCX:
0000000000008cb5
[   15.310490] RDX: 0000000000000000 RSI: ffff9c9882462a00 RDI:
ffff9c98808b7e00
[   15.310490] RBP: ffffb500c0aa0000 R08: 0000000000000000 R09:
0000000000000000
[   15.310490] R10: 0000000000000001 R11: 0000000000000000 R12:
ffffb500c01af000
[   15.310490] R13: ffffb500c01cd000 R14: 0000000000000000 R15:
0000000000000000
[   15.310490] FS:  00007f133b665140(0000) GS:ffff9c98bbd00000(0000)
knlGS:0000000000000000
[   15.310490] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[   15.310490] CR2: ffffb500c0a9fff8 CR3: 0000000102478000 CR4:
00000000000006f0
[   15.310490] Kernel panic - not syncing: Fatal exception in interrupt
[   15.310490] Kernel Offset: 0x30000000 from 0xffffffff81000000
(relocation range: 0xffffffff80000000-0xffffffffbfffffff)

This patch partially prevents this panic by preventing updating extended
prog to prog_array map.

If a prog or its subprog has been extended by freplace prog, the prog
can not be updated to prog_array map.

Alongside next patch, the panic will be prevented completely.

BTW, fix a minor style issue by replacing 8-spaces with a tab.

Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 include/linux/bpf.h   |  2 ++
 kernel/bpf/arraymap.c | 21 +++++++++++++++++----
 kernel/bpf/core.c     |  1 +
 kernel/bpf/syscall.c  | 42 ++++++++++++++++++++++++++++++++++++------
 4 files changed, 56 insertions(+), 10 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 19d8ca8ac960f..aac6d2f42830c 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1483,6 +1483,8 @@ struct bpf_prog_aux {
 	bool xdp_has_frags;
 	bool exception_cb;
 	bool exception_boundary;
+	bool is_extended; /* true if extended by freplace program */
+	struct mutex ext_mutex; /* mutex for is_extended */
 	struct bpf_arena *arena;
 	/* BTF_KIND_FUNC_PROTO for valid attach_btf_id */
 	const struct btf_type *attach_func_proto;
diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index 79660e3fca4c1..4a4de4f014be9 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -947,16 +947,29 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
 				   struct file *map_file, int fd)
 {
 	struct bpf_prog *prog = bpf_prog_get(fd);
+	bool is_extended;
 
 	if (IS_ERR(prog))
 		return prog;
 
-	if (!bpf_prog_map_compatible(map, prog)) {
-		bpf_prog_put(prog);
-		return ERR_PTR(-EINVAL);
-	}
+	if (!bpf_prog_map_compatible(map, prog))
+		goto out_put_prog;
+
+	mutex_lock(&prog->aux->ext_mutex);
+	is_extended = prog->aux->is_extended;
+	mutex_unlock(&prog->aux->ext_mutex);
+	if (is_extended)
+		/* Extended prog can not be tail callee. It's to prevent a
+		 * potential infinite loop like:
+		 * tail callee prog entry -> tail callee prog subprog ->
+		 * freplace prog entry --tailcall-> tail callee prog entry.
+		 */
+		goto out_put_prog;
 
 	return prog;
+out_put_prog:
+	bpf_prog_put(prog);
+	return ERR_PTR(-EINVAL);
 }
 
 static void prog_fd_array_put_ptr(struct bpf_map *map, void *ptr, bool need_defer)
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 4e07cc057d6f2..ea7f59374b378 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -131,6 +131,7 @@ struct bpf_prog *bpf_prog_alloc_no_stats(unsigned int size, gfp_t gfp_extra_flag
 	INIT_LIST_HEAD_RCU(&fp->aux->ksym_prefix.lnode);
 #endif
 	mutex_init(&fp->aux->used_maps_mutex);
+	mutex_init(&fp->aux->ext_mutex);
 	mutex_init(&fp->aux->dst_mutex);
 
 	return fp;
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index a8f1808a1ca54..db17c52fa35db 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -3212,14 +3212,23 @@ static void bpf_tracing_link_release(struct bpf_link *link)
 {
 	struct bpf_tracing_link *tr_link =
 		container_of(link, struct bpf_tracing_link, link.link);
-
-	WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
-						tr_link->trampoline));
+	struct bpf_prog *tgt_prog = tr_link->tgt_prog;
+
+	if (link->prog->type == BPF_PROG_TYPE_EXT) {
+		mutex_lock(&tgt_prog->aux->ext_mutex);
+		WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
+							tr_link->trampoline));
+		tgt_prog->aux->is_extended = false;
+		mutex_unlock(&tgt_prog->aux->ext_mutex);
+	} else {
+		WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
+							tr_link->trampoline));
+	}
 
 	bpf_trampoline_put(tr_link->trampoline);
 
 	/* tgt_prog is NULL if target is a kernel function */
-	if (tr_link->tgt_prog)
+	if (tgt_prog)
 		bpf_prog_put(tr_link->tgt_prog);
 }
 
@@ -3270,6 +3279,24 @@ static const struct bpf_link_ops bpf_tracing_link_lops = {
 	.fill_link_info = bpf_tracing_link_fill_link_info,
 };
 
+static int bpf_extend_prog(struct bpf_tracing_link *link,
+			   struct bpf_trampoline *tr,
+			   struct bpf_prog *tgt_prog)
+{
+	struct bpf_prog_aux *aux = tgt_prog->aux;
+	int err = 0;
+
+	mutex_lock(&aux->ext_mutex);
+	err = bpf_trampoline_link_prog(&link->link, tr);
+	if (err)
+		goto out_unlock;
+
+	aux->is_extended = true;
+out_unlock:
+	mutex_unlock(&aux->ext_mutex);
+	return err;
+}
+
 static int bpf_tracing_prog_attach(struct bpf_prog *prog,
 				   int tgt_prog_fd,
 				   u32 btf_id,
@@ -3354,7 +3381,7 @@ static int bpf_tracing_prog_attach(struct bpf_prog *prog,
 	 *   in prog->aux
 	 *
 	 * - if prog->aux->dst_trampoline is NULL, the program has already been
-         *   attached to a target and its initial target was cleared (below)
+	 *   attached to a target and its initial target was cleared (below)
 	 *
 	 * - if tgt_prog != NULL, the caller specified tgt_prog_fd +
 	 *   target_btf_id using the link_create API.
@@ -3429,7 +3456,10 @@ static int bpf_tracing_prog_attach(struct bpf_prog *prog,
 	if (err)
 		goto out_unlock;
 
-	err = bpf_trampoline_link_prog(&link->link, tr);
+	if (prog->type == BPF_PROG_TYPE_EXT)
+		err = bpf_extend_prog(link, tr, tgt_prog);
+	else
+		err = bpf_trampoline_link_prog(&link->link, tr);
 	if (err) {
 		bpf_link_cleanup(&link_primer);
 		link = NULL;
-- 
2.44.0

Re: [PATCH bpf-next v4 1/4] bpf: Prevent updating extended prog to prog_array map

[Eduard Zingerman]

On Sun, 2024-09-29 at 21:27 +0800, Leon Hwang wrote:

[...]

> diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
> index 79660e3fca4c1..4a4de4f014be9 100644
> --- a/kernel/bpf/arraymap.c
> +++ b/kernel/bpf/arraymap.c
> @@ -947,16 +947,29 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
>  				   struct file *map_file, int fd)
>  {
>  	struct bpf_prog *prog = bpf_prog_get(fd);
> +	bool is_extended;
>  
>  	if (IS_ERR(prog))
>  		return prog;
>  
> -	if (!bpf_prog_map_compatible(map, prog)) {
> -		bpf_prog_put(prog);
> -		return ERR_PTR(-EINVAL);
> -	}
> +	if (!bpf_prog_map_compatible(map, prog))
> +		goto out_put_prog;
> +
> +	mutex_lock(&prog->aux->ext_mutex);
> +	is_extended = prog->aux->is_extended;
> +	mutex_unlock(&prog->aux->ext_mutex);
> +	if (is_extended)
> +		/* Extended prog can not be tail callee. It's to prevent a
> +		 * potential infinite loop like:
> +		 * tail callee prog entry -> tail callee prog subprog ->
> +		 * freplace prog entry --tailcall-> tail callee prog entry.
> +		 */
> +		goto out_put_prog;

Nit: I think return value should be -EBUSY in this case.

>  
>  	return prog;
> +out_put_prog:
> +	bpf_prog_put(prog);
> +	return ERR_PTR(-EINVAL);
>  }
>

[...]

> diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
> index a8f1808a1ca54..db17c52fa35db 100644
> --- a/kernel/bpf/syscall.c
> +++ b/kernel/bpf/syscall.c
> @@ -3212,14 +3212,23 @@ static void bpf_tracing_link_release(struct bpf_link *link)
>  {
>  	struct bpf_tracing_link *tr_link =
>  		container_of(link, struct bpf_tracing_link, link.link);
> -
> -	WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
> -						tr_link->trampoline));
> +	struct bpf_prog *tgt_prog = tr_link->tgt_prog;
> +
> +	if (link->prog->type == BPF_PROG_TYPE_EXT) {
> +		mutex_lock(&tgt_prog->aux->ext_mutex);
> +		WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
> +							tr_link->trampoline));
> +		tgt_prog->aux->is_extended = false;

In case if unlink fails is_extended should not be reset.

> +		mutex_unlock(&tgt_prog->aux->ext_mutex);
> +	} else {
> +		WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
> +							tr_link->trampoline));
> +	}
>  
>  	bpf_trampoline_put(tr_link->trampoline);
>  
>  	/* tgt_prog is NULL if target is a kernel function */
> -	if (tr_link->tgt_prog)
> +	if (tgt_prog)
>  		bpf_prog_put(tr_link->tgt_prog);
>  }

[...]

Re: [PATCH bpf-next v4 1/4] bpf: Prevent updating extended prog to prog_array map

[Leon Hwang]

On 2024/10/1 19:13, Eduard Zingerman wrote:
> On Sun, 2024-09-29 at 21:27 +0800, Leon Hwang wrote:
> 
> [...]
> 
>> diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
>> index 79660e3fca4c1..4a4de4f014be9 100644
>> --- a/kernel/bpf/arraymap.c
>> +++ b/kernel/bpf/arraymap.c
>> @@ -947,16 +947,29 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
>>  				   struct file *map_file, int fd)
>>  {
>>  	struct bpf_prog *prog = bpf_prog_get(fd);
>> +	bool is_extended;
>>  
>>  	if (IS_ERR(prog))
>>  		return prog;
>>  
>> -	if (!bpf_prog_map_compatible(map, prog)) {
>> -		bpf_prog_put(prog);
>> -		return ERR_PTR(-EINVAL);
>> -	}
>> +	if (!bpf_prog_map_compatible(map, prog))
>> +		goto out_put_prog;
>> +
>> +	mutex_lock(&prog->aux->ext_mutex);
>> +	is_extended = prog->aux->is_extended;
>> +	mutex_unlock(&prog->aux->ext_mutex);
>> +	if (is_extended)
>> +		/* Extended prog can not be tail callee. It's to prevent a
>> +		 * potential infinite loop like:
>> +		 * tail callee prog entry -> tail callee prog subprog ->
>> +		 * freplace prog entry --tailcall-> tail callee prog entry.
>> +		 */
>> +		goto out_put_prog;
> 
> Nit: I think return value should be -EBUSY in this case.

Ack.

> 
>>  
>>  	return prog;
>> +out_put_prog:
>> +	bpf_prog_put(prog);
>> +	return ERR_PTR(-EINVAL);
>>  }
>>
> 
> [...]
> 
>> diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
>> index a8f1808a1ca54..db17c52fa35db 100644
>> --- a/kernel/bpf/syscall.c
>> +++ b/kernel/bpf/syscall.c
>> @@ -3212,14 +3212,23 @@ static void bpf_tracing_link_release(struct bpf_link *link)
>>  {
>>  	struct bpf_tracing_link *tr_link =
>>  		container_of(link, struct bpf_tracing_link, link.link);
>> -
>> -	WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
>> -						tr_link->trampoline));
>> +	struct bpf_prog *tgt_prog = tr_link->tgt_prog;
>> +
>> +	if (link->prog->type == BPF_PROG_TYPE_EXT) {
>> +		mutex_lock(&tgt_prog->aux->ext_mutex);
>> +		WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
>> +							tr_link->trampoline));
>> +		tgt_prog->aux->is_extended = false;
> 
> In case if unlink fails is_extended should not be reset.
>

Nope.

In bpf_trampoline_unlink_prog(), 'tr->extension_prog = NULL;' always no
matter whether fail to unlink.

So, it should reset is_extended always too.

Thanks,
Leon

>> +		mutex_unlock(&tgt_prog->aux->ext_mutex);
>> +	} else {
>> +		WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
>> +							tr_link->trampoline));
>> +	}
>>  
>>  	bpf_trampoline_put(tr_link->trampoline);
>>  
>>  	/* tgt_prog is NULL if target is a kernel function */
>> -	if (tr_link->tgt_prog)
>> +	if (tgt_prog)
>>  		bpf_prog_put(tr_link->tgt_prog);
>>  }
> 
> [...]
> 

Re: [PATCH bpf-next v4 1/4] bpf: Prevent updating extended prog to prog_array map

[Eduard Zingerman]

On Tue, 2024-10-01 at 21:20 +0800, Leon Hwang wrote:

[...]

> > > diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
> > > index a8f1808a1ca54..db17c52fa35db 100644
> > > --- a/kernel/bpf/syscall.c
> > > +++ b/kernel/bpf/syscall.c
> > > @@ -3212,14 +3212,23 @@ static void bpf_tracing_link_release(struct bpf_link *link)
> > >  {
> > >  	struct bpf_tracing_link *tr_link =
> > >  		container_of(link, struct bpf_tracing_link, link.link);
> > > -
> > > -	WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
> > > -						tr_link->trampoline));
> > > +	struct bpf_prog *tgt_prog = tr_link->tgt_prog;
> > > +
> > > +	if (link->prog->type == BPF_PROG_TYPE_EXT) {
> > > +		mutex_lock(&tgt_prog->aux->ext_mutex);
> > > +		WARN_ON_ONCE(bpf_trampoline_unlink_prog(&tr_link->link,
> > > +							tr_link->trampoline));
> > > +		tgt_prog->aux->is_extended = false;
> > 
> > In case if unlink fails is_extended should not be reset.
> > 
> 
> Nope.
> 
> In bpf_trampoline_unlink_prog(), 'tr->extension_prog = NULL;' always no
> matter whether fail to unlink.
> 
> So, it should reset is_extended always too.

Hm, you are correct, sorry for the noise.
It is unfortunate that these updates are separated in the code, tbh.

[...]

[PATCH bpf-next v4 2/4] bpf: Prevent extending tail callee prog with freplace prog

[Leon Hwang]

Alongside previous patch, the infinite loop issue caused by combination of
tailcal and freplace can be prevented completely.

The previous patch can not prevent the use case that updates a prog to
prog_array map and then extends subprog of the prog with freplace prog.

This patch fixes the case by preventing extending a prog, which has been
updated to prog_array map, with freplace prog.

If a prog has been updated to prog_array map, it or its subprog can not
be extended by freplace prog.

Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 include/linux/bpf.h   |  3 ++-
 kernel/bpf/arraymap.c |  9 ++++++++-
 kernel/bpf/syscall.c  | 11 +++++++++++
 3 files changed, 21 insertions(+), 2 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index aac6d2f42830c..dc19ad99e2857 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1484,7 +1484,8 @@ struct bpf_prog_aux {
 	bool exception_cb;
 	bool exception_boundary;
 	bool is_extended; /* true if extended by freplace program */
-	struct mutex ext_mutex; /* mutex for is_extended */
+	u32 prog_array_member_cnt; /* counts how many times as member of prog_array */
+	struct mutex ext_mutex; /* mutex for is_extended and prog_array_member_cnt */
 	struct bpf_arena *arena;
 	/* BTF_KIND_FUNC_PROTO for valid attach_btf_id */
 	const struct btf_type *attach_func_proto;
diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index 4a4de4f014be9..91b5bdf4dc72d 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -957,6 +957,8 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
 
 	mutex_lock(&prog->aux->ext_mutex);
 	is_extended = prog->aux->is_extended;
+	if (!is_extended)
+		prog->aux->prog_array_member_cnt++;
 	mutex_unlock(&prog->aux->ext_mutex);
 	if (is_extended)
 		/* Extended prog can not be tail callee. It's to prevent a
@@ -974,8 +976,13 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
 
 static void prog_fd_array_put_ptr(struct bpf_map *map, void *ptr, bool need_defer)
 {
+	struct bpf_prog *prog = ptr;
+
+	mutex_lock(&prog->aux->ext_mutex);
+	prog->aux->prog_array_member_cnt--;
+	mutex_unlock(&prog->aux->ext_mutex);
 	/* bpf_prog is freed after one RCU or tasks trace grace period */
-	bpf_prog_put(ptr);
+	bpf_prog_put(prog);
 }
 
 static u32 prog_fd_array_sys_lookup_elem(void *ptr)
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index db17c52fa35db..4beec9729f742 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -3287,6 +3287,17 @@ static int bpf_extend_prog(struct bpf_tracing_link *link,
 	int err = 0;
 
 	mutex_lock(&aux->ext_mutex);
+	if (aux->prog_array_member_cnt) {
+		/* Program extensions can not extend target prog when the target
+		 * prog has been updated to any prog_array map as tail callee.
+		 * It's to prevent a potential infinite loop like:
+		 * tgt prog entry -> tgt prog subprog -> freplace prog entry
+		 * --tailcall-> tgt prog entry.
+		 */
+		err = -EINVAL;
+		goto out_unlock;
+	}
+
 	err = bpf_trampoline_link_prog(&link->link, tr);
 	if (err)
 		goto out_unlock;
-- 
2.44.0

Re: [PATCH bpf-next v4 2/4] bpf: Prevent extending tail callee prog with freplace prog

[Leon Hwang]

On 29/9/24 21:27, Leon Hwang wrote:
> Alongside previous patch, the infinite loop issue caused by combination of
> tailcal and freplace can be prevented completely.
> 
> The previous patch can not prevent the use case that updates a prog to
> prog_array map and then extends subprog of the prog with freplace prog.
> 
> This patch fixes the case by preventing extending a prog, which has been
> updated to prog_array map, with freplace prog.
> 
> If a prog has been updated to prog_array map, it or its subprog can not
> be extended by freplace prog.
> 
> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
> ---
>  include/linux/bpf.h   |  3 ++-
>  kernel/bpf/arraymap.c |  9 ++++++++-
>  kernel/bpf/syscall.c  | 11 +++++++++++
>  3 files changed, 21 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index aac6d2f42830c..dc19ad99e2857 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -1484,7 +1484,8 @@ struct bpf_prog_aux {
>  	bool exception_cb;
>  	bool exception_boundary;
>  	bool is_extended; /* true if extended by freplace program */
> -	struct mutex ext_mutex; /* mutex for is_extended */
> +	u32 prog_array_member_cnt; /* counts how many times as member of prog_array */
> +	struct mutex ext_mutex; /* mutex for is_extended and prog_array_member_cnt */
>  	struct bpf_arena *arena;
>  	/* BTF_KIND_FUNC_PROTO for valid attach_btf_id */
>  	const struct btf_type *attach_func_proto;
> diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
> index 4a4de4f014be9..91b5bdf4dc72d 100644
> --- a/kernel/bpf/arraymap.c
> +++ b/kernel/bpf/arraymap.c
> @@ -957,6 +957,8 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
>  
>  	mutex_lock(&prog->aux->ext_mutex);
>  	is_extended = prog->aux->is_extended;
> +	if (!is_extended)
> +		prog->aux->prog_array_member_cnt++;

prog_array_member_cnt must check U32_MAX before incrementing. Or it will
overflow u32. So it will be better like:

	mutex_lock(&prog->aux->ext_mutex);
	is_invalid = prog->aux->is_extended || prog->aux->prog_array_member_cnt
== U32_MAX;
	if (!is_invalid)
		prog->aux->prog_array_member_cnt++;
	mutex_unlock(&prog->aux->ext_mutex);
	if (is_invalid)
		goto out_put_prog;

Thanks,
Leon

Re: [PATCH bpf-next v4 2/4] bpf: Prevent extending tail callee prog with freplace prog

[Alexei Starovoitov]

On Sun, Sep 29, 2024 at 6:54 PM Leon Hwang <hffilwlqm@gmail.com> wrote:
>
>
>
> On 29/9/24 21:27, Leon Hwang wrote:
> > Alongside previous patch, the infinite loop issue caused by combination of
> > tailcal and freplace can be prevented completely.
> >
> > The previous patch can not prevent the use case that updates a prog to
> > prog_array map and then extends subprog of the prog with freplace prog.
> >
> > This patch fixes the case by preventing extending a prog, which has been
> > updated to prog_array map, with freplace prog.
> >
> > If a prog has been updated to prog_array map, it or its subprog can not
> > be extended by freplace prog.
> >
> > Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
> > ---
> >  include/linux/bpf.h   |  3 ++-
> >  kernel/bpf/arraymap.c |  9 ++++++++-
> >  kernel/bpf/syscall.c  | 11 +++++++++++
> >  3 files changed, 21 insertions(+), 2 deletions(-)
> >
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index aac6d2f42830c..dc19ad99e2857 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -1484,7 +1484,8 @@ struct bpf_prog_aux {
> >       bool exception_cb;
> >       bool exception_boundary;
> >       bool is_extended; /* true if extended by freplace program */
> > -     struct mutex ext_mutex; /* mutex for is_extended */
> > +     u32 prog_array_member_cnt; /* counts how many times as member of prog_array */
> > +     struct mutex ext_mutex; /* mutex for is_extended and prog_array_member_cnt */
> >       struct bpf_arena *arena;
> >       /* BTF_KIND_FUNC_PROTO for valid attach_btf_id */
> >       const struct btf_type *attach_func_proto;
> > diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
> > index 4a4de4f014be9..91b5bdf4dc72d 100644
> > --- a/kernel/bpf/arraymap.c
> > +++ b/kernel/bpf/arraymap.c
> > @@ -957,6 +957,8 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
> >
> >       mutex_lock(&prog->aux->ext_mutex);
> >       is_extended = prog->aux->is_extended;
> > +     if (!is_extended)
> > +             prog->aux->prog_array_member_cnt++;
>
> prog_array_member_cnt must check U32_MAX before incrementing. Or it will
> overflow u32. So it will be better like:
>
>         mutex_lock(&prog->aux->ext_mutex);
>         is_invalid = prog->aux->is_extended || prog->aux->prog_array_member_cnt
> == U32_MAX;

No. Just make it u64 instead.

btw the whole thing can be done with a single atomic64_t:
- set it to 1 at the start then

- prog_fd_array_get_ptr() will do
atomic64_inc_not_zero

- prog_fd_array_put_ptr() will do
atomic64_add_unless(,-1, 1)

- freplace attach will do
cmpxchg(,1,0)

so 1 - initial state
2,3,.. - prog in prog_array
0 - prog was extended.

If == 0 -> cannot add to prog_array
if > 1 -> cannot freplace.

but it's too clever.
It's better to use mutex and keep bool + count,
but extra mutex is unnecessary.
Reuse prog->aux->dst_mutex.
Grab it prog_fd_array_get_ptr() and do the check and cnt++

Also pls combine patch 1 and 2.
They do one logical step.

Re: [PATCH bpf-next v4 2/4] bpf: Prevent extending tail callee prog with freplace prog

[Eduard Zingerman]

On Fri, 2024-10-04 at 12:33 -0700, Alexei Starovoitov wrote:

[...]

> so 1 - initial state
> 2,3,.. - prog in prog_array
> 0 - prog was extended.

This sounds interesting, but need to think a bit.

> If == 0 -> cannot add to prog_array
> if > 1 -> cannot freplace.
> 
> but it's too clever.
> It's better to use mutex and keep bool + count,
> but extra mutex is unnecessary.
> Reuse prog->aux->dst_mutex.
> Grab it prog_fd_array_get_ptr() and do the check and cnt++

I think it is not possible to grab the correct mutex in
prog_fd_array_get_ptr().

bpf_tracing_prog_attach() operates on two programs:
- one named 'prog' is the freplace program;
- another named 'tgt_prog' is the program to attach 'prog' to.

bpf_tracing_prog_attach() grabs prog->aux->dst_mutex.
Inside prog_fd_array_get_ptr() there is only a pointer to program
being put into array, potential target of the freplace.
From bpf_tracing_prog_attach() it is referred as 'tgt_prog'.
As far as I understand, there is no way to get a pointer to an active
freplace program from prog_fd_array_get_ptr().

[...]

Re: [PATCH bpf-next v4 2/4] bpf: Prevent extending tail callee prog with freplace prog

[Eduard Zingerman]

On Fri, 2024-10-04 at 12:33 -0700, Alexei Starovoitov wrote:

[...]

> btw the whole thing can be done with a single atomic64_t:
> - set it to 1 at the start then
> 
> - prog_fd_array_get_ptr() will do
> atomic64_inc_not_zero
> 
> - prog_fd_array_put_ptr() will do
> atomic64_add_unless(,-1, 1)
> 
> - freplace attach will do
> cmpxchg(,1,0)
> 
> so 1 - initial state
> 2,3,.. - prog in prog_array
> 0 - prog was extended.
> 
> If == 0 -> cannot add to prog_array
> if > 1 -> cannot freplace.

I think this should work, because we no longer need to jungle two values.
I kinda like it.

[...]

Re: [PATCH bpf-next v4 2/4] bpf: Prevent extending tail callee prog with freplace prog

[Alexei Starovoitov]

On Fri, Oct 4, 2024 at 1:52 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2024-10-04 at 12:33 -0700, Alexei Starovoitov wrote:
>
> [...]
>
> > btw the whole thing can be done with a single atomic64_t:
> > - set it to 1 at the start then
> >
> > - prog_fd_array_get_ptr() will do
> > atomic64_inc_not_zero
> >
> > - prog_fd_array_put_ptr() will do
> > atomic64_add_unless(,-1, 1)
> >
> > - freplace attach will do
> > cmpxchg(,1,0)
> >
> > so 1 - initial state
> > 2,3,.. - prog in prog_array
> > 0 - prog was extended.
> >
> > If == 0 -> cannot add to prog_array
> > if > 1 -> cannot freplace.
>
> I think this should work, because we no longer need to jungle two values.
> I kinda like it.

It's a bit too clever.

With mutex it's much easier to reason about:

struct bpf_prog_aux {
   mutex ext_mutex;
   bool is_extended;
   u64 prog_array_member_cnt;
};

freplace link on tgt_prog:
guard(mutex)(&aux->ext_mutex);
if (aux->prog_array_member_cnt) {
  // reject freplace
} else {
  aux->is_extended = true;
}

freplace unlink:
guard(mutex)(&aux->ext_mutex);
aux->is_extended = false;

and similar in prog_fd_array_get_ptr():
guard(mutex)(&aux->ext_mutex);
if (aux->is_extended) {
   // reject adding to prog_array
} else {
  aux->prog_array_member_cnt++;
}

in prog_fd_array_put_ptr():
guard(mutex)(&aux->ext_mutex);
aux->prog_array_member_cnt--;

[PATCH bpf-next v4 3/4] selftests/bpf: Add a test case to confirm a tailcall infinite loop issue has been prevented

[Leon Hwang]

cd tools/testing/selftests/bpf; ./test_progs -t tailcalls
335/26  tailcalls/tailcall_bpf2bpf_freplace:OK
335     tailcalls:OK
Summary: 1/26 PASSED, 0 SKIPPED, 0 FAILED

Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 .../selftests/bpf/prog_tests/tailcalls.c      | 99 ++++++++++++++++++-
 .../testing/selftests/bpf/progs/tc_bpf2bpf.c  | 24 ++++-
 2 files changed, 119 insertions(+), 4 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/tailcalls.c b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
index 21c5a37846ade..fa3f3bb11b098 100644
--- a/tools/testing/selftests/bpf/prog_tests/tailcalls.c
+++ b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
@@ -1525,7 +1525,8 @@ static void test_tailcall_freplace(void)
 
 	prog_fd = bpf_program__fd(tc_skel->progs.entry_tc);
 	freplace_prog = freplace_skel->progs.entry_freplace;
-	err = bpf_program__set_attach_target(freplace_prog, prog_fd, "subprog");
+	err = bpf_program__set_attach_target(freplace_prog, prog_fd,
+					     "subprog_tailcall_tc");
 	if (!ASSERT_OK(err, "set_attach_target"))
 		goto out;
 
@@ -1534,7 +1535,7 @@ static void test_tailcall_freplace(void)
 		goto out;
 
 	freplace_link = bpf_program__attach_freplace(freplace_prog, prog_fd,
-						     "subprog");
+						     "subprog_tailcall_tc");
 	if (!ASSERT_OK_PTR(freplace_link, "attach_freplace"))
 		goto out;
 
@@ -1556,6 +1557,98 @@ static void test_tailcall_freplace(void)
 	tailcall_freplace__destroy(freplace_skel);
 }
 
+/* test_tailcall_bpf2bpf_freplace checks the failure that fails to attach a tail
+ * callee prog with freplace prog or fails to update an extended prog to
+ * prog_array map.
+ */
+static void test_tailcall_bpf2bpf_freplace(void)
+{
+	struct tailcall_freplace *freplace_skel = NULL;
+	struct bpf_link *freplace_link = NULL;
+	struct tc_bpf2bpf *tc_skel = NULL;
+	char buff[128] = {};
+	int prog_fd, map_fd;
+	int err, key;
+
+	LIBBPF_OPTS(bpf_test_run_opts, topts,
+		    .data_in = buff,
+		    .data_size_in = sizeof(buff),
+		    .repeat = 1,
+	);
+
+	tc_skel = tc_bpf2bpf__open_and_load();
+	if (!ASSERT_OK_PTR(tc_skel, "tc_bpf2bpf__open_and_load"))
+		goto out;
+
+	prog_fd = bpf_program__fd(tc_skel->progs.entry_tc);
+	freplace_skel = tailcall_freplace__open();
+	if (!ASSERT_OK_PTR(freplace_skel, "tailcall_freplace__open"))
+		goto out;
+
+	err = bpf_program__set_attach_target(freplace_skel->progs.entry_freplace,
+					     prog_fd, "subprog_tc");
+	if (!ASSERT_OK(err, "set_attach_target"))
+		goto out;
+
+	err = tailcall_freplace__load(freplace_skel);
+	if (!ASSERT_OK(err, "tailcall_freplace__load"))
+		goto out;
+
+	/* OK to attach then detach freplace prog. */
+
+	freplace_link = bpf_program__attach_freplace(freplace_skel->progs.entry_freplace,
+						     prog_fd, "subprog_tc");
+	if (!ASSERT_OK_PTR(freplace_link, "attach_freplace"))
+		goto out;
+
+	err = bpf_link__destroy(freplace_link);
+	if (!ASSERT_OK(err, "destroy link"))
+		goto out;
+
+	/* OK to update prog_array map then delete element from the map. */
+
+	key = 0;
+	map_fd = bpf_map__fd(freplace_skel->maps.jmp_table);
+	err = bpf_map_update_elem(map_fd, &key, &prog_fd, BPF_ANY);
+	if (!ASSERT_OK(err, "update jmp_table"))
+		goto out;
+
+	err = bpf_map_delete_elem(map_fd, &key);
+	if (!ASSERT_OK(err, "delete_elem from jmp_table"))
+		goto out;
+
+	/* Fail to attach a tail callee prog with freplace prog. */
+
+	err = bpf_map_update_elem(map_fd, &key, &prog_fd, BPF_ANY);
+	if (!ASSERT_OK(err, "update jmp_table"))
+		goto out;
+
+	freplace_link = bpf_program__attach_freplace(freplace_skel->progs.entry_freplace,
+						     prog_fd, "subprog_tc");
+	if (!ASSERT_ERR_PTR(freplace_link, "attach_freplace failure"))
+		goto out;
+
+	err = bpf_map_delete_elem(map_fd, &key);
+	if (!ASSERT_OK(err, "delete_elem from jmp_table"))
+		goto out;
+
+	/* Fail to update an extended prog to prog_array map. */
+
+	freplace_link = bpf_program__attach_freplace(freplace_skel->progs.entry_freplace,
+						     prog_fd, "subprog_tc");
+	if (!ASSERT_OK_PTR(freplace_link, "attach_freplace"))
+		goto out;
+
+	err = bpf_map_update_elem(map_fd, &key, &prog_fd, BPF_ANY);
+	if (!ASSERT_ERR(err, "update jmp_table failure"))
+		goto out;
+
+out:
+	bpf_link__destroy(freplace_link);
+	tailcall_freplace__destroy(freplace_skel);
+	tc_bpf2bpf__destroy(tc_skel);
+}
+
 void test_tailcalls(void)
 {
 	if (test__start_subtest("tailcall_1"))
@@ -1606,4 +1699,6 @@ void test_tailcalls(void)
 	test_tailcall_bpf2bpf_hierarchy_3();
 	if (test__start_subtest("tailcall_freplace"))
 		test_tailcall_freplace();
+	if (test__start_subtest("tailcall_bpf2bpf_freplace"))
+		test_tailcall_bpf2bpf_freplace();
 }
diff --git a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
index 8a0632c37839a..34f3c780194e4 100644
--- a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
+++ b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
@@ -4,11 +4,30 @@
 #include <bpf/bpf_helpers.h>
 #include "bpf_misc.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");
+
+__noinline
+int subprog_tailcall_tc(struct __sk_buff *skb)
+{
+	int ret = 1;
+
+	bpf_tail_call_static(skb, &jmp_table, 0);
+	__sink(skb);
+	__sink(ret);
+	return ret;
+}
+
 __noinline
-int subprog(struct __sk_buff *skb)
+int subprog_tc(struct __sk_buff *skb)
 {
 	int ret = 1;
 
+	__sink(skb);
 	__sink(ret);
 	return ret;
 }
@@ -16,7 +35,8 @@ int subprog(struct __sk_buff *skb)
 SEC("tc")
 int entry_tc(struct __sk_buff *skb)
 {
-	return subprog(skb);
+	subprog_tc(skb);
+	return subprog_tailcall_tc(skb);
 }
 
 char __license[] SEC("license") = "GPL";
-- 
2.44.0

[PATCH bpf-next v4 4/4] selftests/bpf: Add cases to test tailcall in freplace

[Leon Hwang]

cd tools/testing/selftests/bpf; ./test_progs -t tailcalls
335/27  tailcalls/tailcall_bpf2bpf_hierarchy_freplace_1:OK
335/28  tailcalls/tailcall_bpf2bpf_hierarchy_freplace_2:OK
335     tailcalls:OK
Summary: 1/28 PASSED, 0 SKIPPED, 0 FAILED

Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 .../selftests/bpf/prog_tests/tailcalls.c      | 97 +++++++++++++++++++
 .../tailcall_bpf2bpf_hierarchy_freplace.c     | 30 ++++++
 .../testing/selftests/bpf/progs/tc_bpf2bpf.c  | 13 +++
 3 files changed, 140 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_bpf2bpf_hierarchy_freplace.c

diff --git a/tools/testing/selftests/bpf/prog_tests/tailcalls.c b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
index fa3f3bb11b098..0564ad6c9b288 100644
--- a/tools/testing/selftests/bpf/prog_tests/tailcalls.c
+++ b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
@@ -5,6 +5,7 @@
 #include "tailcall_poke.skel.h"
 #include "tailcall_bpf2bpf_hierarchy2.skel.h"
 #include "tailcall_bpf2bpf_hierarchy3.skel.h"
+#include "tailcall_bpf2bpf_hierarchy_freplace.skel.h"
 #include "tailcall_freplace.skel.h"
 #include "tc_bpf2bpf.skel.h"
 
@@ -1649,6 +1650,98 @@ static void test_tailcall_bpf2bpf_freplace(void)
 	tc_bpf2bpf__destroy(tc_skel);
 }
 
+static void test_tailcall_bpf2bpf_hierarchy_freplace(bool freplace_subprog,
+						     bool target_entry2,
+						     int count1, int count2)
+{
+	struct tailcall_bpf2bpf_hierarchy_freplace *freplace_skel = NULL;
+	struct bpf_link *freplace_link = NULL;
+	struct tc_bpf2bpf *tc_skel = NULL;
+	int prog_fd, map_fd;
+	char buff[128] = {};
+	int err, key, val;
+
+	LIBBPF_OPTS(bpf_test_run_opts, topts,
+		    .data_in = buff,
+		    .data_size_in = sizeof(buff),
+		    .repeat = 1,
+	);
+
+	tc_skel = tc_bpf2bpf__open_and_load();
+	if (!ASSERT_OK_PTR(tc_skel, "tc_bpf2bpf__open_and_load"))
+		goto out;
+
+	prog_fd = bpf_program__fd(target_entry2 ? tc_skel->progs.entry_tc_2 :
+				  tc_skel->progs.entry_tc);
+	freplace_skel = tailcall_bpf2bpf_hierarchy_freplace__open();
+	if (!ASSERT_OK_PTR(freplace_skel, "tailcall_bpf2bpf_hierarchy_freplace__open"))
+		goto out;
+
+	err = bpf_program__set_attach_target(freplace_skel->progs.entry_freplace,
+					     prog_fd, freplace_subprog ?
+					     "subprog_tailcall_tc" : "entry_tc");
+	if (!ASSERT_OK(err, "set_attach_target"))
+		goto out;
+
+	err = tailcall_bpf2bpf_hierarchy_freplace__load(freplace_skel);
+	if (!ASSERT_OK(err, "tailcall_bpf2bpf_hierarchy_freplace__load"))
+		goto out;
+
+	val = bpf_program__fd(freplace_skel->progs.entry_freplace);
+	map_fd = bpf_map__fd(freplace_skel->maps.jmp_table);
+	key = 0;
+	err = bpf_map_update_elem(map_fd, &key, &val, BPF_ANY);
+	if (!ASSERT_OK(err, "update jmp_table"))
+		goto out;
+
+	freplace_link = bpf_program__attach_freplace(freplace_skel->progs.entry_freplace,
+						     prog_fd, freplace_subprog ?
+						     "subprog_tailcall_tc" : "entry_tc");
+	if (!ASSERT_OK_PTR(freplace_link, "attach_freplace"))
+		goto out;
+
+	err = bpf_prog_test_run_opts(prog_fd, &topts);
+	ASSERT_OK(err, "test_run_opts");
+	ASSERT_EQ(topts.retval, count1, "test_run_opts retval");
+
+	err = bpf_map_delete_elem(map_fd, &key);
+	if (!ASSERT_OK(err, "delete_elem from jmp_table"))
+		goto out;
+
+	err = bpf_prog_test_run_opts(prog_fd, &topts);
+	ASSERT_OK(err, "test_run_opts again");
+	ASSERT_EQ(topts.retval, count2, "test_run_opts retval again");
+
+out:
+	bpf_link__destroy(freplace_link);
+	tailcall_bpf2bpf_hierarchy_freplace__destroy(freplace_skel);
+	tc_bpf2bpf__destroy(tc_skel);
+}
+
+/* test_tailcall_bpf2bpf_hierarchy_freplace_1 checks the count value of tail
+ * call limit enforcement matches with expectation for the case:
+ *
+ *                                    subprog_tail --tailcall-> entry_freplace
+ * entry_tc --jump-> entry_freplace <
+ *                                    subprog_tail --tailcall-> entry_freplace
+ */
+static void test_tailcall_bpf2bpf_hierarchy_freplace_1(void)
+{
+	test_tailcall_bpf2bpf_hierarchy_freplace(false, false, 34, 35);
+}
+
+/* test_tailcall_bpf2bpf_hierarchy_freplace_2 checks the count value of tail
+ * call limit enforcement matches with expectation for the case:
+ *
+ *                                                                              subprog_tail --tailcall-> entry_freplace
+ * entry_tc_2 --> subprog_tailcall_tc (call 10 times) --jump-> entry_freplace <
+ *                                                                              subprog_tail --tailcall-> entry_freplace
+ */
+static void test_tailcall_bpf2bpf_hierarchy_freplace_2(void)
+{
+	test_tailcall_bpf2bpf_hierarchy_freplace(true, true, 340, 350);
+}
+
 void test_tailcalls(void)
 {
 	if (test__start_subtest("tailcall_1"))
@@ -1701,4 +1794,8 @@ void test_tailcalls(void)
 		test_tailcall_freplace();
 	if (test__start_subtest("tailcall_bpf2bpf_freplace"))
 		test_tailcall_bpf2bpf_freplace();
+	if (test__start_subtest("tailcall_bpf2bpf_hierarchy_freplace_1"))
+		test_tailcall_bpf2bpf_hierarchy_freplace_1();
+	if (test__start_subtest("tailcall_bpf2bpf_hierarchy_freplace_2"))
+		test_tailcall_bpf2bpf_hierarchy_freplace_2();
 }
diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf_hierarchy_freplace.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf_hierarchy_freplace.c
new file mode 100644
index 0000000000000..6f7c1fac9ddb7
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf_hierarchy_freplace.c
@@ -0,0 +1,30 @@
+// 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");
+
+int count = 0;
+
+static __noinline
+int subprog_tail(struct __sk_buff *skb)
+{
+	bpf_tail_call_static(skb, &jmp_table, 0);
+	return 0;
+}
+
+SEC("freplace")
+int entry_freplace(struct __sk_buff *skb)
+{
+	count++;
+	subprog_tail(skb);
+	subprog_tail(skb);
+	return count;
+}
+
+char __license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
index 34f3c780194e4..beacf60a52677 100644
--- a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
+++ b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
@@ -39,4 +39,17 @@ int entry_tc(struct __sk_buff *skb)
 	return subprog_tailcall_tc(skb);
 }
 
+SEC("tc")
+int entry_tc_2(struct __sk_buff *skb)
+{
+	int ret, i;
+
+	for (i = 0; i < 10; i++) {
+		ret = subprog_tailcall_tc(skb);
+		__sink(ret);
+	}
+
+	return ret;
+}
+
 char __license[] SEC("license") = "GPL";
-- 
2.44.0

Re: [PATCH bpf-next v4 0/4] bpf: Fix tailcall infinite loop caused by freplace

[Eduard Zingerman]

On Sun, 2024-09-29 at 21:27 +0800, Leon Hwang wrote:
> Previously, I fixed a tailcall infinite loop issue caused by trampoline[0].
> 
> At this time, I fix a tailcall infinite loop issue caused by tailcall and
> freplace combination by preventing updating extended prog to prog_array map
> and preventing extending tail callee prog with freplace:
> 
> 1. If a prog or its subprog has been extended by freplace prog, the prog
>    can not be updated to prog_array map.
> 2. If a prog has been updated to prog_array map, it or its subprog can not
>    be extended by freplace prog.

So, once this series is applied we essentially have:
- three variables:
  - tgt_prog->aux->is_extended
  - tgt_prog->aux->prog_array_member_cnt
  - trampoline->extension_prog
- four operations:
  - link/attach extension program 'prog' using trampoline 'tr'
  - unlink/detach extension program 'prog' using trampoline 'tr'
  - put program 'tgt_prog' into prog array
  - remove program 'tgt_prog' from prog array

And above four operations have the following pseudo-code with regards
to update of the variables:

- link/attach extension program 'prog' using trampoline 'tr':

    with lock(tgt_prog->ext_mutex):
      if tgt_prog->aux->prog_array_member_cnt:
         return error
      if tr->extension_prog:
         return error
      tr->extension_prog = prog
      tgt_prog->is_extended = true

- unlink/detach extension program 'prog' using trampoline 'tr':

    with lock(tgt_prog->ext_mutex):
      tr->extension_prog = NULL
      tgt_prog->is_extended = false

- put program 'tgt_prog' into prog array:

    with lock(tgt_prog->ext_mutex):
      if tgt_prog->aux->is_extended:
         return error
      tgt_prog->aux->prog_array_member_cnt++

- remove program 'tgt_prog' from prog array:

    with lock(tgt_prog->ext_mutex):
      tgt_prog->aux->prog_array_member_cnt--

I think this is correct, would be great if someone with more
concurrency related experience would take a look.

[...]