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

Commit Message

Arthur Fabre Dec. 13, 2024, 9:27 p.m. UTC

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 <[e-mail]>
---
 .../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

Comments

Eduard Zingerman Dec. 13, 2024, 11:55 p.m. UTC | #1

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 <[e-mail]>
> ---

Acked-by: Eduard Zingerman <[e-mail]>

[...]

> +++ 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";

Arthur Fabre Dec. 16, 2024, 5:39 p.m. UTC | #2

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.

Alexei Starovoitov Dec. 16, 2024, 6:05 p.m. UTC | #3

On Mon, Dec 16, 2024 at 9:39 AM Arthur Fabre <[e-mail]> 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.

Eduard Zingerman Dec. 16, 2024, 6:50 p.m. UTC | #4

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

Eduard Zingerman Dec. 16, 2024, 6:50 p.m. UTC | #5

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.

Alexei Starovoitov Dec. 16, 2024, 7:47 p.m. UTC | #6

On Mon, Dec 16, 2024 at 10:50 AM Eduard Zingerman <[e-mail]> 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.

Arthur Fabre Dec. 16, 2024, 8:45 p.m. UTC | #7

On Mon Dec 16, 2024 at 8:47 PM CET, Alexei Starovoitov wrote:
> On Mon, Dec 16, 2024 at 10:50 AM Eduard Zingerman <[e-mail]> 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.

Patch

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