Received-SPF: pass (google.com: domain of linux-kernel+bounces-17043-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161;
Message-ID: <f3dd9d80-3fab-4676-b589-1d4667431287@linux.dev>
Date: Thu, 4 Jan 2024 09:31:52 -0800
Precedence: bulk
MIME-Version: 1.0
Subject: Re: [PATCH v2 bpf-next 2/2] selftests/bpf: add inline assembly
 helpers to access array elements
Content-Language: en-GB
To: Jiri Olsa <olsajiri@gmail.com>, Barret Rhoden <brho@google.com>,
 Eddy Z <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii@kernel.org>, Alexei Starovoitov <ast@kernel.org>,
 Daniel Borkmann <daniel@iogearbox.net>, Song Liu <song@kernel.org>,
 mattbobrowski@google.com, bpf@vger.kernel.org, linux-kernel@vger.kernel.org
References: <20240103185403.610641-1-brho@google.com>
 <20240103185403.610641-3-brho@google.com> <ZZa1668ft4Npd1DA@krava>
From: Yonghong Song <yonghong.song@linux.dev>
In-Reply-To: <ZZa1668ft4Npd1DA@krava>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

cc Eduard.

On 1/4/24 5:43 AM, Jiri Olsa wrote:
> On Wed, Jan 03, 2024 at 01:53:59PM -0500, Barret Rhoden wrote:
>
> SNIP
>
>> +
>> +
>> +/* Test that attempting to load a bad program fails. */
>> +#define test_bad(PROG) ({						\
>> +	struct array_elem_test *skel;					\
>> +	int err;							\
>> +	skel = array_elem_test__open();					\
>> +	if (!ASSERT_OK_PTR(skel, "array_elem_test open"))		\
>> +		return;							\
>> +	bpf_program__set_autoload(skel->progs.x_bad_ ## PROG, true); 	\
>> +	err = array_elem_test__load(skel);				\
>> +	ASSERT_ERR(err, "array_elem_test load " # PROG);		\
>> +	array_elem_test__destroy(skel);					\
>> +})
> I wonder we could use the existing RUN_TESTS macro and use tags
> in programs like we do for example in progs/test_global_func1.c:
>
>    SEC("tc")
>    __failure __msg("combined stack size of 4 calls is 544")
>    int global_func1(struct __sk_buff *skb)
>
> jirka
>
>
>> +
>> +void test_test_array_elem(void)
>> +{
>> +	if (test__start_subtest("array_elem_access_all"))
>> +		test_access_all();
>> +	if (test__start_subtest("array_elem_oob_access"))
>> +		test_oob_access();
>> +	if (test__start_subtest("array_elem_access_array_map_infer_sz"))
>> +		test_access_array_map_infer_sz();
>> +	if (test__start_subtest("array_elem_bad_map_array_access"))
>> +		test_bad(map_array_access);
>> +	if (test__start_subtest("array_elem_bad_bss_array_access"))
>> +		test_bad(bss_array_access);
>> +
[...]
>> 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.
>> + */
>> +#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:;				\
>> +			      %[__arr] = 0;			\
>> +			      2:				\
>> +			      "						\
>> +			     : [__arr]"+r"(___arr), [__idx]"+r"(___idx)	\
>> +			     : [__bound]"r"((arr_sz)),		        \
>> +			       [__size]"i"(sizeof(typeof((arr)[0])))	\
>> +			     : "cc");					\
>> +	}								\
>> +	___arr;								\
>> +})

The LLVM bpf backend has made some improvement to handle the case like
   r1 = ...
   r2 = r1 + 1
   if (r2 < num) ...
   using r1
by preventing generating the above code pattern.

The implementation is a pattern matching style so surely it won't be
able to cover all cases.

Do you have specific examples which has verification failure due to
false array out of bound access?

>> +
>> +/*
>> + * 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
>>
>>