linux-kernel - RE: [PATCH bpf-next 2/2] selftests/bpf: add inline assembly helpers to access array elements

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <65959ed1b9e86_2384720818@john.notmuch>
Date: Wed, 03 Jan 2024 09:52:17 -0800
From: John Fastabend <john.fastabend@...il.com>
To: Barret Rhoden <brho@...gle.com>, 
 Andrii Nakryiko <andrii@...nel.org>, 
 Alexei Starovoitov <ast@...nel.org>, 
 Daniel Borkmann <daniel@...earbox.net>, 
 Song Liu <song@...nel.org>, 
 Yonghong Song <yonghong.song@...ux.dev>
Cc: mattbobrowski@...gle.com, 
 bpf@...r.kernel.org, 
 linux-kernel@...r.kernel.org
Subject: RE: [PATCH bpf-next 2/2] selftests/bpf: add inline assembly helpers
 to access array elements

Barret Rhoden wrote:
> When accessing an array, even if you insert your own bounds check,
> sometimes the compiler will remove the check, or modify it such that the
> verifier no longer knows your access is within bounds.
> 
> The compiler is even free to make a copy of a register, check the copy,
> and use the original to access the array.  The verifier knows the *copy*
> is within bounds, but not the original register!
> 
> Signed-off-by: Barret Rhoden <brho@...gle.com>
> ---
>  tools/testing/selftests/bpf/Makefile          |   2 +-
>  .../bpf/prog_tests/test_array_elem.c          | 112 ++++++++++
>  .../selftests/bpf/progs/array_elem_test.c     | 195 ++++++++++++++++++
>  tools/testing/selftests/bpf/progs/bpf_misc.h  |  43 ++++
>  4 files changed, 351 insertions(+), 1 deletion(-)
>  create mode 100644 tools/testing/selftests/bpf/prog_tests/test_array_elem.c
>  create mode 100644 tools/testing/selftests/bpf/progs/array_elem_test.c
> 
> diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile
> index 617ae55c3bb5..651d4663cc78 100644
> --- a/tools/testing/selftests/bpf/Makefile
> +++ b/tools/testing/selftests/bpf/Makefile
> @@ -34,7 +34,7 @@ LIBELF_CFLAGS	:= $(shell $(PKG_CONFIG) libelf --cflags 2>/dev/null)
>  LIBELF_LIBS	:= $(shell $(PKG_CONFIG) libelf --libs 2>/dev/null || echo -lelf)
>  
>  CFLAGS += -g $(OPT_FLAGS) -rdynamic					\
> -	  -Wall -Werror 						\
> +	  -dicks -Wall -Werror 						\
>  	  $(GENFLAGS) $(SAN_CFLAGS) $(LIBELF_CFLAGS)			\
>  	  -I$(CURDIR) -I$(INCLUDE_DIR) -I$(GENDIR) -I$(LIBDIR)		\
>  	  -I$(TOOLSINCDIR) -I$(APIDIR) -I$(OUTPUT)
> diff --git a/tools/testing/selftests/bpf/prog_tests/test_array_elem.c b/tools/testing/selftests/bpf/prog_tests/test_array_elem.c
> new file mode 100644
> index 000000000000..c953636f07c9
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/test_array_elem.c
> @@ -0,0 +1,112 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/* Copyright (c) 2024 Google LLC. */
> +#include <test_progs.h>
> +#include "array_elem_test.skel.h"
> +
> +#define NR_MAP_ELEMS 100

[...]

> diff --git a/tools/testing/selftests/bpf/progs/bpf_misc.h b/tools/testing/selftests/bpf/progs/bpf_misc.h
> index 2fd59970c43a..002bab44cde2 100644
> --- a/tools/testing/selftests/bpf/progs/bpf_misc.h
> +++ b/tools/testing/selftests/bpf/progs/bpf_misc.h
> @@ -135,4 +135,47 @@
>  /* make it look to compiler like value is read and written */
>  #define __sink(expr) asm volatile("" : "+g"(expr))
>  
> +/*
> + * Access an array element within a bound, such that the verifier knows the
> + * access is safe.
> + *
> + * This macro asm is the equivalent of:
> + *
> + *	if (!arr)
> + *		return NULL;
> + *	if (idx >= arr_sz)
> + *		return NULL;
> + *	return &arr[idx];
> + *
> + * The index (___idx below) needs to be a u64, at least for certain versions of
> + * the BPF ISA, since there aren't u32 conditional jumps.
> + */

This is nice, but in practice what we've been doing is making
our maps power of 2 and then just masking them as needed. I think
this is more efficient if you care about performance.

FWIW I'm not opposed to having this though.

> +#define bpf_array_elem(arr, arr_sz, idx) ({				\
> +	typeof(&(arr)[0]) ___arr = arr;					\
> +	__u64 ___idx = idx;						\
> +	if (___arr) {							\
> +		asm volatile("if %[__idx] >= %[__bound] goto 1f;	\
> +			      %[__idx] *= %[__size];		\
> +			      %[__arr] += %[__idx];		\
> +			      goto 2f;				\

+1 for using asm goto :)

> +			      1:;				\
> +			      %[__arr] = 0;			\
> +			      2:				\
> +			      "						\
> +			     : [__arr]"+r"(___arr), [__idx]"+r"(___idx)	\
> +			     : [__bound]"r"((arr_sz)),		        \
> +			       [__size]"i"(sizeof(typeof((arr)[0])))	\
> +			     : "cc");					\
> +	}								\
> +	___arr;								\
> +})
> +
> +/*
> + * Convenience wrapper for bpf_array_elem(), where we compute the size of the
> + * array.  Be sure to use an actual array, and not a pointer, just like with the
> + * ARRAY_SIZE macro.
> + */
> +#define bpf_array_sz_elem(arr, idx) \
> +	bpf_array_elem(arr, sizeof(arr) / sizeof((arr)[0]), idx)
> +
>  #endif
> -- 
> 2.43.0.472.g3155946c3a-goog
> 
>