[PATCH bpf v2 0/2] Don't trust r0 bounds after BPF to BPF calls with abnormal returns

[PATCH bpf v2 0/2] Don't trust r0 bounds after BPF to BPF calls with abnormal returns

[Arthur Fabre]

A BPF function can return before its exit instruction: LD_ABS, LD_IND,
and tail_call() can all cause it to return prematurely.

When such a function is called by another BPF function, the verifier
doesn't take this into account when calculating the bounds of r0 in the
caller after the callee returns.

---
Changes in v2:
- Handle LD_ABS and LD_IND, not just tail_call()
- Split tests out
- Use inline asm for tests

---
Arthur Fabre (2):
  bpf: Don't trust r0 bounds after BPF to BPF calls with abnormal
    returns
  selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal
    return

 kernel/bpf/verifier.c                         | 18 ++--
 .../selftests/bpf/prog_tests/verifier.c       |  2 +
 .../bpf/progs/verifier_abnormal_ret.c         | 88 +++++++++++++++++++
 3 files changed, 102 insertions(+), 6 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c

-- 
2.34.1

[PATCH bpf v2 1/2] bpf: Don't trust r0 bounds after BPF to BPF calls with abnormal returns

[Arthur Fabre]

When making BPF to BPF calls, the verifier propagates register bounds
info for r0 from the callee to the caller.

For example loading:

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

    static __attribute__((noinline)) int callee(struct xdp_md *ctx)
    {
            int ret;
            asm volatile("%0 = 23" : "=r"(ret));
            return ret;
    }

    static SEC("xdp") int caller(struct xdp_md *ctx)
    {
            int res = callee(ctx);
            if (res == 23) {
                    return XDP_PASS;
            }
            return XDP_DROP;
    }

The verifier logs:

    func#0 @0
    func#1 @6
    0: R1=ctx() R10=fp0
    ; int res = callee(ctx); @ test.c:15
    0: (85) call pc+5
    caller:
     R10=fp0
    callee:
     frame1: R1=ctx() R10=fp0
    6: frame1: R1=ctx() R10=fp0
    ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:9
    6: (b7) r0 = 23                       ; frame1: R0_w=23
    ; return ret; @ test.c:10
    7: (95) exit
    returning from callee:
     frame1: R0_w=23 R1=ctx() R10=fp0
    to caller at 1:
     R0_w=23 R10=fp0

    from 7 to 1: R0_w=23 R10=fp0
    ; int res = callee(ctx); @ test.c:15
    1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
    2: (b4) w0 = 2                        ; R0_w=2
    ;  @ test.c:0
    3: (16) if w1 == 0x17 goto pc+1
    3: R1_w=23
    ; } @ test.c:20
    5: (95) exit
    processed 7 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0

And correctly tracks R0_w=23 from the callee through to the caller.
This lets it completely prune the res != 23 branch, skipping over
instruction 4.

But this isn't sound if the callee can return "abnormally" before an
exit instruction:
- If LD_ABS or LD_IND try to access data beyond the end of the packet,
  the callee returns 0 directly.
- If a tail_call succeeds, the return value of the tail called program
  will be returned directly.
We can't know what the bounds of r0 will be.

The verifier still incorrectly tracks the bounds of r0 in these cases. Loading:

    #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));
    } tail_call_map SEC(".maps");

    static __attribute__((noinline)) int callee(struct xdp_md *ctx)
    {
            bpf_tail_call(ctx, &tail_call_map, 0);

            int ret;
            asm volatile("%0 = 23" : "=r"(ret));
            return ret;
    }

    static SEC("xdp") int caller(struct xdp_md *ctx)
    {
            int res = callee(ctx);
            if (res == 23) {
                    return XDP_PASS;
            }
            return XDP_DROP;
    }

The verifier logs:

    func#0 @0
    func#1 @6
    0: R1=ctx() R10=fp0
    ; int res = callee(ctx); @ test.c:24
    0: (85) call pc+5
    caller:
     R10=fp0
    callee:
     frame1: R1=ctx() R10=fp0
    6: frame1: R1=ctx() R10=fp0
    ; bpf_tail_call(ctx, &tail_call_map, 0); @ test.c:15
    6: (18) r2 = 0xffff8a9c82a75800       ; frame1: R2_w=map_ptr(map=tail_call_map,ks=4,vs=4)
    8: (b4) w3 = 0                        ; frame1: R3_w=0
    9: (85) call bpf_tail_call#12
    10: frame1:
    ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:18
    10: (b7) r0 = 23                      ; frame1: R0_w=23
    ; return ret; @ test.c:19
    11: (95) exit
    returning from callee:
     frame1: R0_w=23 R10=fp0
    to caller at 1:
     R0_w=23 R10=fp0

    from 11 to 1: R0_w=23 R10=fp0
    ; int res = callee(ctx); @ test.c:24
    1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
    2: (b4) w0 = 2                        ; R0=2
    ;  @ test.c:0
    3: (16) if w1 == 0x17 goto pc+1
    3: R1=23
    ; } @ test.c:29
    5: (95) exit
    processed 10 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

It still prunes the res != 23 branch, skipping over instruction 4.
But the tail called program can return any value.

Aside from pruning incorrect branches, this can also be used to read and
write arbitrary memory by using r0 as a index.

Fixes: e411901c0b77 ("bpf: allow for tailcalls in BPF subprograms for x64 JIT")
Signed-off-by: Arthur Fabre <afabre@cloudflare.com>
Cc: stable@vger.kernel.org
---
 kernel/bpf/verifier.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c2e5d0e6e3d0..76c0008f6914 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10314,6 +10314,11 @@ static bool retval_range_within(struct bpf_retval_range range, const struct bpf_
 		return range.minval <= reg->smin_value && reg->smax_value <= range.maxval;
 }
 
+static bool has_abnormal_return(struct bpf_subprog_info *subprog_info)
+{
+	return subprog_info->has_ld_abs || subprog_info->has_tail_call;
+}
+
 static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 {
 	struct bpf_verifier_state *state = env->cur_state, *prev_st;
@@ -10359,6 +10364,10 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 				*insn_idx, callee->callsite);
 			return -EFAULT;
 		}
+	} else if (has_abnormal_return(
+		    &env->subprog_info[state->frame[state->curframe]->subprogno])) {
+		/* callee can return before exit instruction, r0 could hold anything */
+		__mark_reg_unknown(env, &caller->regs[BPF_REG_0]);
 	} else {
 		/* return to the caller whatever r0 had in the callee */
 		caller->regs[BPF_REG_0] = *r0;
@@ -16881,17 +16890,14 @@ static int check_cfg(struct bpf_verifier_env *env)
 	return ret;
 }
 
+
 static int check_abnormal_return(struct bpf_verifier_env *env)
 {
 	int i;
 
 	for (i = 1; i < env->subprog_cnt; i++) {
-		if (env->subprog_info[i].has_ld_abs) {
-			verbose(env, "LD_ABS is not allowed in subprogs without BTF\n");
-			return -EINVAL;
-		}
-		if (env->subprog_info[i].has_tail_call) {
-			verbose(env, "tail_call is not allowed in subprogs without BTF\n");
+		if (has_abnormal_return(&env->subprog_info[i])) {
+			verbose(env, "LD_ABS/tail_call is not allowed in subprogs without BTF\n");
 			return -EINVAL;
 		}
 	}
-- 
2.34.1

[PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Arthur Fabre]

Test the bounds of r0 aren't known by the verifier in all three cases
where a callee can abnormally return.

Signed-off-by: Arthur Fabre <afabre@cloudflare.com>
---
 .../selftests/bpf/prog_tests/verifier.c       |  2 +
 .../bpf/progs/verifier_abnormal_ret.c         | 88 +++++++++++++++++++
 2 files changed, 90 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index 3ee40ee9413a..6bed606544e3 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -3,6 +3,7 @@
 #include <test_progs.h>
 
 #include "cap_helpers.h"
+#include "verifier_abnormal_ret.skel.h"
 #include "verifier_and.skel.h"
 #include "verifier_arena.skel.h"
 #include "verifier_arena_large.skel.h"
@@ -133,6 +134,7 @@ static void run_tests_aux(const char *skel_name,
 
 #define RUN(skel) run_tests_aux(#skel, skel##__elf_bytes, NULL)
 
+void test_verifier_abnormal_ret(void)         { RUN(verifier_abnormal_ret); }
 void test_verifier_and(void)                  { RUN(verifier_and); }
 void test_verifier_arena(void)                { RUN(verifier_arena); }
 void test_verifier_arena_large(void)          { RUN(verifier_arena_large); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c b/tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c
new file mode 100644
index 000000000000..5e246986945f
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c
@@ -0,0 +1,88 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "../../../include/linux/filter.h"
+#include "bpf_misc.h"
+
+#define TEST(NAME, CALLEE) \
+	SEC("socket")					\
+	__description("abnormal_ret: " #NAME)		\
+	__failure __msg("math between ctx pointer and register with unbounded min value") \
+	__naked void check_abnormal_ret_##NAME(void)	\
+	{						\
+		asm volatile("				\
+		r6 = r1;				\
+		call " #CALLEE ";			\
+		r6 += r0;				\
+		r0 = 0;					\
+		exit;					\
+	"	:					\
+		:					\
+		: __clobber_all);			\
+	}
+
+TEST(ld_abs, callee_ld_abs);
+TEST(ld_ind, callee_ld_ind);
+TEST(tail_call, callee_tail_call);
+
+static __naked __noinline __used
+int callee_ld_abs(void)
+{
+	asm volatile("					\
+	r6 = r1;					\
+	.8byte %[ld_abs];				\
+	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm_insn(ld_abs, BPF_LD_ABS(BPF_W, 0))
+	: __clobber_all);
+}
+
+static __naked __noinline __used
+int callee_ld_ind(void)
+{
+	asm volatile("					\
+	r6 = r1;					\
+	r7 = 1;						\
+	.8byte %[ld_ind];				\
+	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm_insn(ld_ind, BPF_LD_IND(BPF_W, BPF_REG_7, 0))
+	: __clobber_all);
+}
+
+SEC("socket")
+__auxiliary __naked
+void dummy_prog(void)
+{
+	asm volatile("r0 = 1; exit;");
+}
+
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 1);
+	__uint(key_size, sizeof(int));
+	__array(values, void(void));
+} map_prog SEC(".maps") = {
+	.values = {
+		[0] = (void *)&dummy_prog,
+	},
+};
+
+static __naked __noinline __used
+int callee_tail_call(void)
+{
+	asm volatile("					\
+	r2 = %[map_prog] ll;				\
+	r3 = 0;						\
+	call %[bpf_tail_call];				\
+	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_tail_call), __imm_addr(map_prog)
+	: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.34.1

Re: [PATCH bpf v2 1/2] bpf: Don't trust r0 bounds after BPF to BPF calls with abnormal returns

[Eduard Zingerman]

On Fri, 2024-12-13 at 22:27 +0100, Arthur Fabre wrote:
> When making BPF to BPF calls, the verifier propagates register bounds
> info for r0 from the callee to the caller.
> 
> For example loading:
> 
>     #include <linux/bpf.h>
>     #include <bpf/bpf_helpers.h>
> 
>     static __attribute__((noinline)) int callee(struct xdp_md *ctx)
>     {
>             int ret;
>             asm volatile("%0 = 23" : "=r"(ret));
>             return ret;
>     }
> 
>     static SEC("xdp") int caller(struct xdp_md *ctx)
>     {
>             int res = callee(ctx);
>             if (res == 23) {
>                     return XDP_PASS;
>             }
>             return XDP_DROP;
>     }
> 
> The verifier logs:
> 
>     func#0 @0
>     func#1 @6
>     0: R1=ctx() R10=fp0
>     ; int res = callee(ctx); @ test.c:15
>     0: (85) call pc+5
>     caller:
>      R10=fp0
>     callee:
>      frame1: R1=ctx() R10=fp0
>     6: frame1: R1=ctx() R10=fp0
>     ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:9
>     6: (b7) r0 = 23                       ; frame1: R0_w=23
>     ; return ret; @ test.c:10
>     7: (95) exit
>     returning from callee:
>      frame1: R0_w=23 R1=ctx() R10=fp0
>     to caller at 1:
>      R0_w=23 R10=fp0
> 
>     from 7 to 1: R0_w=23 R10=fp0
>     ; int res = callee(ctx); @ test.c:15
>     1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
>     2: (b4) w0 = 2                        ; R0_w=2
>     ;  @ test.c:0
>     3: (16) if w1 == 0x17 goto pc+1
>     3: R1_w=23
>     ; } @ test.c:20
>     5: (95) exit
>     processed 7 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
> 
> And correctly tracks R0_w=23 from the callee through to the caller.
> This lets it completely prune the res != 23 branch, skipping over
> instruction 4.
> 
> But this isn't sound if the callee can return "abnormally" before an
> exit instruction:
> - If LD_ABS or LD_IND try to access data beyond the end of the packet,
>   the callee returns 0 directly.
> - If a tail_call succeeds, the return value of the tail called program
>   will be returned directly.
> We can't know what the bounds of r0 will be.
> 
> The verifier still incorrectly tracks the bounds of r0 in these cases. Loading:
> 
>     #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));
>     } tail_call_map SEC(".maps");
> 
>     static __attribute__((noinline)) int callee(struct xdp_md *ctx)
>     {
>             bpf_tail_call(ctx, &tail_call_map, 0);
> 
>             int ret;
>             asm volatile("%0 = 23" : "=r"(ret));
>             return ret;
>     }
> 
>     static SEC("xdp") int caller(struct xdp_md *ctx)
>     {
>             int res = callee(ctx);
>             if (res == 23) {
>                     return XDP_PASS;
>             }
>             return XDP_DROP;
>     }
> 
> The verifier logs:
> 
>     func#0 @0
>     func#1 @6
>     0: R1=ctx() R10=fp0
>     ; int res = callee(ctx); @ test.c:24
>     0: (85) call pc+5
>     caller:
>      R10=fp0
>     callee:
>      frame1: R1=ctx() R10=fp0
>     6: frame1: R1=ctx() R10=fp0
>     ; bpf_tail_call(ctx, &tail_call_map, 0); @ test.c:15
>     6: (18) r2 = 0xffff8a9c82a75800       ; frame1: R2_w=map_ptr(map=tail_call_map,ks=4,vs=4)
>     8: (b4) w3 = 0                        ; frame1: R3_w=0
>     9: (85) call bpf_tail_call#12
>     10: frame1:
>     ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:18
>     10: (b7) r0 = 23                      ; frame1: R0_w=23
>     ; return ret; @ test.c:19
>     11: (95) exit
>     returning from callee:
>      frame1: R0_w=23 R10=fp0
>     to caller at 1:
>      R0_w=23 R10=fp0
> 
>     from 11 to 1: R0_w=23 R10=fp0
>     ; int res = callee(ctx); @ test.c:24
>     1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
>     2: (b4) w0 = 2                        ; R0=2
>     ;  @ test.c:0
>     3: (16) if w1 == 0x17 goto pc+1
>     3: R1=23
>     ; } @ test.c:29
>     5: (95) exit
>     processed 10 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
> 
> It still prunes the res != 23 branch, skipping over instruction 4.
> But the tail called program can return any value.
> 
> Aside from pruning incorrect branches, this can also be used to read and
> write arbitrary memory by using r0 as a index.
> 
> Fixes: e411901c0b77 ("bpf: allow for tailcalls in BPF subprograms for x64 JIT")
> Signed-off-by: Arthur Fabre <afabre@cloudflare.com>
> Cc: stable@vger.kernel.org
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[...]

> @@ -10359,6 +10364,10 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
>  				*insn_idx, callee->callsite);
>  			return -EFAULT;
>  		}
> +	} else if (has_abnormal_return(
> +		    &env->subprog_info[state->frame[state->curframe]->subprogno])) {
                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                       Nit: this is 'callee'

> +		/* callee can return before exit instruction, r0 could hold anything */
> +		__mark_reg_unknown(env, &caller->regs[BPF_REG_0]);
>  	} else {
>  		/* return to the caller whatever r0 had in the callee */
>  		caller->regs[BPF_REG_0] = *r0;
> @@ -16881,17 +16890,14 @@ static int check_cfg(struct bpf_verifier_env *env)
>  	return ret;
>  }
>  
> +

Nit: this empty line is not needed.

[...]

Re: [PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Eduard Zingerman]

On Fri, 2024-12-13 at 22:27 +0100, Arthur Fabre wrote:
> Test the bounds of r0 aren't known by the verifier in all three cases
> where a callee can abnormally return.
> 
> Signed-off-by: Arthur Fabre <afabre@cloudflare.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[...]

> +++ b/tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c
> @@ -0,0 +1,88 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <linux/bpf.h>
> +#include <bpf/bpf_helpers.h>
> +#include "../../../include/linux/filter.h"
> +#include "bpf_misc.h"
> +
> +#define TEST(NAME, CALLEE) \
> +	SEC("socket")					\
> +	__description("abnormal_ret: " #NAME)		\
> +	__failure __msg("math between ctx pointer and register with unbounded min value") \
> +	__naked void check_abnormal_ret_##NAME(void)	\
> +	{						\

Nit: this one and 'callee_tail_call' could be plain C.

> +		asm volatile("				\
> +		r6 = r1;				\
> +		call " #CALLEE ";			\
> +		r6 += r0;				\
> +		r0 = 0;					\
> +		exit;					\
> +	"	:					\
> +		:					\
> +		: __clobber_all);			\
> +	}

[...]

> +static __naked __noinline __used
> +int callee_tail_call(void)
> +{
> +	asm volatile("					\
> +	r2 = %[map_prog] ll;				\
> +	r3 = 0;						\
> +	call %[bpf_tail_call];				\
> +	r0 = 0;						\
> +	exit;						\
> +"	:
> +	: __imm(bpf_tail_call), __imm_addr(map_prog)
> +	: __clobber_all);
> +}
> +
> +char _license[] SEC("license") = "GPL";

Re: [PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Arthur Fabre]

On Sat Dec 14, 2024 at 12:55 AM CET, Eduard Zingerman wrote:
> On Fri, 2024-12-13 at 22:27 +0100, Arthur Fabre wrote:
[...]
> > +++ b/tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c
> > @@ -0,0 +1,88 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +#include <linux/bpf.h>
> > +#include <bpf/bpf_helpers.h>
> > +#include "../../../include/linux/filter.h"
> > +#include "bpf_misc.h"
> > +
> > +#define TEST(NAME, CALLEE) \
> > +	SEC("socket")					\
> > +	__description("abnormal_ret: " #NAME)		\
> > +	__failure __msg("math between ctx pointer and register with unbounded min value") \
> > +	__naked void check_abnormal_ret_##NAME(void)	\
> > +	{						\
>
> Nit: this one and 'callee_tail_call' could be plain C.
>
> > +		asm volatile("				\
> > +		r6 = r1;				\
> > +		call " #CALLEE ";			\
> > +		r6 += r0;				\
> > +		r0 = 0;					\
> > +		exit;					\
> > +	"	:					\
> > +		:					\
> > +		: __clobber_all);			\
> > +	}
>
> [...]
>
> > +static __naked __noinline __used
> > +int callee_tail_call(void)
> > +{
> > +	asm volatile("					\
> > +	r2 = %[map_prog] ll;				\
> > +	r3 = 0;						\
> > +	call %[bpf_tail_call];				\
> > +	r0 = 0;						\
> > +	exit;						\
> > +"	:
> > +	: __imm(bpf_tail_call), __imm_addr(map_prog)
> > +	: __clobber_all);
> > +}
> > +
> > +char _license[] SEC("license") = "GPL";

Thanks for the review! Good point, I'll try to write them in C.

It might not be possible to do them both entirely: clang also doesn't
know that bpf_tail_call() can return, so it assumes the callee() will
return a constant r0. It sometimes optimizes branches / loads out
because of this.

Re: [PATCH bpf v2 0/2] Don't trust r0 bounds after BPF to BPF calls with abnormal returns

[Arthur Fabre]

On Fri Dec 13, 2024 at 10:27 PM CET, Arthur Fabre wrote:
> A BPF function can return before its exit instruction: LD_ABS, LD_IND,
> and tail_call() can all cause it to return prematurely.
>
> When such a function is called by another BPF function, the verifier
> doesn't take this into account when calculating the bounds of r0 in the
> caller after the callee returns.

I've just realized r0 isn't he only problem: a caller can pass a
reference to its stack to a callee, and the verifier also tracks the
value of this.

If the callee writes to the caller's stack after the abnormal return
(tail_call, ld_abs), the verifier will also incorrectly assume the 
write always happens.

I think we need to treat these abnormal returns as a branch that can
exit. That way the verifier will explore both possibilities, and the
combined result will really reflect what can happen.
I'll try that out for a v3.

Re: [PATCH bpf v2 0/2] Don't trust r0 bounds after BPF to BPF calls with abnormal returns

[Alexei Starovoitov]

On Mon, Dec 16, 2024 at 9:45 AM Arthur Fabre <afabre@cloudflare.com> wrote:
>
> On Fri Dec 13, 2024 at 10:27 PM CET, Arthur Fabre wrote:
> > A BPF function can return before its exit instruction: LD_ABS, LD_IND,
> > and tail_call() can all cause it to return prematurely.
> >
> > When such a function is called by another BPF function, the verifier
> > doesn't take this into account when calculating the bounds of r0 in the
> > caller after the callee returns.
>
> I've just realized r0 isn't he only problem: a caller can pass a
> reference to its stack to a callee, and the verifier also tracks the
> value of this.
>
> If the callee writes to the caller's stack after the abnormal return
> (tail_call, ld_abs), the verifier will also incorrectly assume the
> write always happens.
>
> I think we need to treat these abnormal returns as a branch that can
> exit. That way the verifier will explore both possibilities, and the
> combined result will really reflect what can happen.
> I'll try that out for a v3.

Good idea. Makes sense to me.

Re: [PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Alexei Starovoitov]

On Mon, Dec 16, 2024 at 9:39 AM Arthur Fabre <afabre@cloudflare.com> wrote:
>
> On Sat Dec 14, 2024 at 12:55 AM CET, Eduard Zingerman wrote:
> > On Fri, 2024-12-13 at 22:27 +0100, Arthur Fabre wrote:
> [...]
> > > +++ b/tools/testing/selftests/bpf/progs/verifier_abnormal_ret.c
> > > @@ -0,0 +1,88 @@
> > > +// SPDX-License-Identifier: GPL-2.0
> > > +
> > > +#include <linux/bpf.h>
> > > +#include <bpf/bpf_helpers.h>
> > > +#include "../../../include/linux/filter.h"
> > > +#include "bpf_misc.h"
> > > +
> > > +#define TEST(NAME, CALLEE) \
> > > +   SEC("socket")                                   \
> > > +   __description("abnormal_ret: " #NAME)           \
> > > +   __failure __msg("math between ctx pointer and register with unbounded min value") \
> > > +   __naked void check_abnormal_ret_##NAME(void)    \
> > > +   {                                               \
> >
> > Nit: this one and 'callee_tail_call' could be plain C.
> >
> > > +           asm volatile("                          \
> > > +           r6 = r1;                                \
> > > +           call " #CALLEE ";                       \
> > > +           r6 += r0;                               \
> > > +           r0 = 0;                                 \
> > > +           exit;                                   \
> > > +   "       :                                       \
> > > +           :                                       \
> > > +           : __clobber_all);                       \
> > > +   }
> >
> > [...]
> >
> > > +static __naked __noinline __used
> > > +int callee_tail_call(void)
> > > +{
> > > +   asm volatile("                                  \
> > > +   r2 = %[map_prog] ll;                            \
> > > +   r3 = 0;                                         \
> > > +   call %[bpf_tail_call];                          \
> > > +   r0 = 0;                                         \
> > > +   exit;                                           \
> > > +"  :
> > > +   : __imm(bpf_tail_call), __imm_addr(map_prog)
> > > +   : __clobber_all);
> > > +}
> > > +
> > > +char _license[] SEC("license") = "GPL";
>
> Thanks for the review! Good point, I'll try to write them in C.
>
> It might not be possible to do them both entirely: clang also doesn't
> know that bpf_tail_call() can return, so it assumes the callee() will
> return a constant r0. It sometimes optimizes branches / loads out
> because of this.

I wonder whether we should tell llvm that it's similar to longjmp()
with __attribute__((noreturn)) or some other attribute.

Re: [PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Eduard Zingerman]

On Mon, 2024-12-16 at 10:05 -0800, Alexei Starovoitov wrote:

[...]

> > Thanks for the review! Good point, I'll try to write them in C.
> > 
> > It might not be possible to do them both entirely: clang also doesn't
> > know that bpf_tail_call() can return, so it assumes the callee() will
> > return a constant r0. It sometimes optimizes branches / loads out
> > because of this.
>
> I wonder whether we should tell llvm that it's similar to longjmp()
> with __attribute__((noreturn)) or some other attribute.

GCC documents it as follows [1]:

  > The noreturn keyword tells the compiler to assume that fatal
  > cannot reaturn. It can then optimize without regard to what would
  > happen if fatal ever did return. This makes slightly better code.
  > More importantly, it helps avoid spurious warnings of
  > uninitialized variables.

But the bpf_tail_call could return if MAX_TAIL_CALL_CNT limit is exceeded,
or programs map index is out of bounds.

[1] https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Function-Attributes.html#index-noreturn-function-attribute

Re: [PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Eduard Zingerman]

On Mon, 2024-12-16 at 18:39 +0100, Arthur Fabre wrote:

[...]

> It might not be possible to do them both entirely: clang also doesn't
> know that bpf_tail_call() can return, so it assumes the callee() will
> return a constant r0. It sometimes optimizes branches / loads out
> because of this.

Hm, haven't thought about this.
You would need assembly to hide the r0 indeed.

Re: [PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Alexei Starovoitov]

On Mon, Dec 16, 2024 at 10:50 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-12-16 at 10:05 -0800, Alexei Starovoitov wrote:
>
> [...]
>
> > > Thanks for the review! Good point, I'll try to write them in C.
> > >
> > > It might not be possible to do them both entirely: clang also doesn't
> > > know that bpf_tail_call() can return, so it assumes the callee() will
> > > return a constant r0. It sometimes optimizes branches / loads out
> > > because of this.
> >
> > I wonder whether we should tell llvm that it's similar to longjmp()
> > with __attribute__((noreturn)) or some other attribute.
>
> GCC documents it as follows [1]:
>
>   > The noreturn keyword tells the compiler to assume that fatal
>   > cannot reaturn. It can then optimize without regard to what would
>   > happen if fatal ever did return. This makes slightly better code.
>   > More importantly, it helps avoid spurious warnings of
>   > uninitialized variables.
>
> But the bpf_tail_call could return if MAX_TAIL_CALL_CNT limit is exceeded,
> or programs map index is out of bounds.
>
> [1] https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Function-Attributes.html#index-noreturn-function-attribute

Yeah. noreturn is too heavy.
attr(returns_twice) is another option, but it will probably
pessimize the code too much as well.

Re: [PATCH bpf v2 2/2] selftests/bpf: Test r0 bounds after BPF to BPF call with abnormal return

[Arthur Fabre]

On Mon Dec 16, 2024 at 8:47 PM CET, Alexei Starovoitov wrote:
> On Mon, Dec 16, 2024 at 10:50 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Mon, 2024-12-16 at 10:05 -0800, Alexei Starovoitov wrote:
> >
> > [...]
> >
> > > > Thanks for the review! Good point, I'll try to write them in C.
> > > >
> > > > It might not be possible to do them both entirely: clang also doesn't
> > > > know that bpf_tail_call() can return, so it assumes the callee() will
> > > > return a constant r0. It sometimes optimizes branches / loads out
> > > > because of this.
> > >
> > > I wonder whether we should tell llvm that it's similar to longjmp()
> > > with __attribute__((noreturn)) or some other attribute.
> >
> > GCC documents it as follows [1]:
> >
> >   > The noreturn keyword tells the compiler to assume that fatal
> >   > cannot reaturn. It can then optimize without regard to what would
> >   > happen if fatal ever did return. This makes slightly better code.
> >   > More importantly, it helps avoid spurious warnings of
> >   > uninitialized variables.
> >
> > But the bpf_tail_call could return if MAX_TAIL_CALL_CNT limit is exceeded,
> > or programs map index is out of bounds.
> >
> > [1] https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Function-Attributes.html#index-noreturn-function-attribute
>
> Yeah. noreturn is too heavy.
> attr(returns_twice) is another option, but it will probably
> pessimize the code too much as well.

We could provide a macro like:

#define BPF_TAIL_CALL(ctx, map, index) do { \
    bpf_tail_call(ctx, map, index); \
    int maybe_return; \
    asm volatile("%0 = 0" : "=r"(maybe_return)); \
    if (maybe_return) \
        return maybe_return; \
} while(0)

It correctly tricks clang into thinking it can return early, but the
verifier removes the dead branch so there's no runtime cost.

But users would have to switch to it, I don't think we can replace the
definition in bpf_helper_defs.h in a backwards compatible way.