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@xxxxxxxxxx>
> ---
> 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
>
>
