[v5,bpf-next,3/3] selftests/bpf: Remove i = zero workaround and add new tests.

Commit Message

Alexei Starovoitov June 6, 2024, 12:54 a.m. UTC

From: Alexei Starovoitov <[e-mail]>

. remove i = zero workaround from various tests
. improve arena based tests
. add asm test for this_branch_reg->id == other_branch_reg->id condition
. add several loop inside open coded iter tests

Signed-off-by: Alexei Starovoitov <[e-mail]>
---
 .../testing/selftests/bpf/progs/arena_htab.c  |  16 ++-
 tools/testing/selftests/bpf/progs/iters.c     |  14 +-
 .../selftests/bpf/progs/iters_task_vma.c      | 130 ++++++++++++++++++
 .../bpf/progs/verifier_iterating_callbacks.c  |  23 ++--
 .../selftests/bpf/progs/verifier_reg_equal.c  |  29 ++++
 5 files changed, 185 insertions(+), 27 deletions(-)

Patch

diff --git a/tools/testing/selftests/bpf/progs/arena_htab.c b/tools/testing/selftests/bpf/progs/arena_htab.c
index 1e6ac187a6a0..1917f35b5963 100644
--- a/tools/testing/selftests/bpf/progs/arena_htab.c
+++ b/tools/testing/selftests/bpf/progs/arena_htab.c
@@ -18,25 +18,35 @@  void __arena *htab_for_user;
 bool skip = false;
 
 int zero = 0;
+char __arena arr1[100000];
+char arr2[1000];
 
 SEC("syscall")
 int arena_htab_llvm(void *ctx)
 {
 #if defined(__BPF_FEATURE_ADDR_SPACE_CAST) || defined(BPF_ARENA_FORCE_ASM)
 	struct htab __arena *htab;
+	char __arena *arr = arr1;
 	__u64 i;
 
 	htab = bpf_alloc(sizeof(*htab));
 	cast_kern(htab);
 	htab_init(htab);
 
+	cast_kern(arr);
+
 	/* first run. No old elems in the table */
-	for (i = zero; i < 1000; i++)
+	for (i = 0; i < 100000 && can_loop; i++) {
 		htab_update_elem(htab, i, i);
+		arr[i] = i;
+	}
 
-	/* should replace all elems with new ones */
-	for (i = zero; i < 1000; i++)
+	/* should replace some elems with new ones */
+	for (i = 0; i < 1000 && can_loop; i++) {
 		htab_update_elem(htab, i, i);
+		/* Access mem to make the verifier use bounded loop logic */
+		arr2[i] = i;
+	}
 	cast_user(htab);
 	htab_for_user = htab;
 #else
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index fe65e0952a1e..1a5adffae5d3 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -291,10 +291,7 @@  int iter_obfuscate_counter(const void *ctx)
 {
 	struct bpf_iter_num it;
 	int *v, sum = 0;
-	/* Make i's initial value unknowable for verifier to prevent it from
-	 * pruning if/else branch inside the loop body and marking i as precise.
-	 */
-	int i = zero;
+	int i = 0;
 
 	MY_PID_GUARD();
 
@@ -304,15 +301,6 @@  int iter_obfuscate_counter(const void *ctx)
 
 		i += 1;
 
-		/* If we initialized i as `int i = 0;` above, verifier would
-		 * track that i becomes 1 on first iteration after increment
-		 * above, and here verifier would eagerly prune else branch
-		 * and mark i as precise, ruining open-coded iterator logic
-		 * completely, as each next iteration would have a different
-		 * *precise* value of i, and thus there would be no
-		 * convergence of state. This would result in reaching maximum
-		 * instruction limit, no matter what the limit is.
-		 */
 		if (i == 1)
 			x = 123;
 		else
diff --git a/tools/testing/selftests/bpf/progs/iters_task_vma.c b/tools/testing/selftests/bpf/progs/iters_task_vma.c
index dc0c3691dcc2..31c4e7d9eaa3 100644
--- a/tools/testing/selftests/bpf/progs/iters_task_vma.c
+++ b/tools/testing/selftests/bpf/progs/iters_task_vma.c
@@ -28,6 +28,10 @@  int iter_task_vma_for_each(const void *ctx)
 		return 0;
 
 	bpf_for_each(task_vma, vma, task, 0) {
+		/*
+		 * Fast to verify, since 'seen' has the same range at every
+		 * loop iteration.
+		 */
 		if (bpf_cmp_unlikely(seen, >=, 1000))
 			break;
 
@@ -40,4 +44,130 @@  int iter_task_vma_for_each(const void *ctx)
 	return 0;
 }
 
+SEC("raw_tp/sys_enter")
+int iter_task_vma_for_each_eq(const void *ctx)
+{
+	struct task_struct *task = bpf_get_current_task_btf();
+	struct vm_area_struct *vma;
+	unsigned int seen = 0;
+
+	if (task->pid != target_pid)
+		return 0;
+
+	if (vmas_seen)
+		return 0;
+
+	bpf_for_each(task_vma, vma, task, 0) {
+		/*
+		 * Also fast, since the verifier recognizes
+		 * 0, 1, 2 != 1000 as [0, 999] range.
+		 */
+		if (bpf_cmp_unlikely(seen, ==, 1000))
+			break;
+
+		vm_ranges[seen].vm_start = vma->vm_start;
+		vm_ranges[seen].vm_end = vma->vm_end;
+		seen++;
+	}
+
+	vmas_seen = seen;
+	return 0;
+}
+
+#define ARR_SZ 100000
+char arr[ARR_SZ];
+
+SEC("socket")
+__success __flag(BPF_F_TEST_STATE_FREQ)
+int loop_inside_iter(const void *ctx)
+{
+	struct bpf_iter_num it;
+	int *v, sum = 0;
+	__u64 i = 0;
+
+	bpf_iter_num_new(&it, 0, ARR_SZ);
+	while ((v = bpf_iter_num_next(&it))) {
+		if (i < ARR_SZ)
+			sum += arr[i++];
+	}
+	bpf_iter_num_destroy(&it);
+	return sum;
+}
+
+SEC("socket")
+__success __flag(BPF_F_TEST_STATE_FREQ)
+int loop_inside_iter_signed(const void *ctx)
+{
+	struct bpf_iter_num it;
+	int *v, sum = 0;
+	long i = 0;
+
+	bpf_iter_num_new(&it, 0, ARR_SZ);
+	while ((v = bpf_iter_num_next(&it))) {
+		if (i < ARR_SZ && i >= 0)
+			sum += arr[i++];
+	}
+	bpf_iter_num_destroy(&it);
+	return sum;
+}
+
+volatile const int limit = ARR_SZ;
+
+SEC("socket")
+__success __flag(BPF_F_TEST_STATE_FREQ)
+int loop_inside_iter_volatile_limit(const void *ctx)
+{
+	struct bpf_iter_num it;
+	int *v, sum = 0;
+	__u64 i = 0;
+
+	bpf_iter_num_new(&it, 0, ARR_SZ);
+	while ((v = bpf_iter_num_next(&it))) {
+		if (i < limit)
+			sum += arr[i++];
+	}
+	bpf_iter_num_destroy(&it);
+	return sum;
+}
+
+__noinline
+static void touch_arr(int i)
+{
+	/*
+	 * Though 'i' is signed the verifier sees that 0
+	 * is the lowest number passed into static subprogram
+	 * and determines the range [0, ARR_SZ - 1].
+	 */
+	if (i >= ARR_SZ)
+		return;
+	arr[i] = i;
+}
+
+__noinline
+int touch_arr_global(__u32 i)
+{
+	/*
+	 * In global function the array index 'i' has to be unsigned,
+	 * otherwise the verifier will see unbounded min value.
+	 */
+	if (i >= ARR_SZ)
+		return 0;
+	arr[i] = i;
+	return 0;
+}
+
+SEC("socket")
+__success
+int loop_inside_iter_subprog(const void *ctx)
+{
+	long i;
+
+	for (i = 0; i <= 1000000 && can_loop; i++)
+		touch_arr(i);
+
+	for (i = 0; i <= 1000000 && can_loop; i++)
+		touch_arr_global(i);
+
+	return 0;
+}
 char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index bd676d7e615f..78016294df95 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -308,7 +308,6 @@  int iter_limit_bug(struct __sk_buff *skb)
 }
 
 #define ARR_SZ 1000000
-int zero;
 char arr[ARR_SZ];
 
 SEC("socket")
@@ -318,9 +317,10 @@  int cond_break1(const void *ctx)
 	unsigned long i;
 	unsigned int sum = 0;
 
-	for (i = zero; i < ARR_SZ && can_loop; i++)
+	for (i = 0; i < ARR_SZ && can_loop; i++)
 		sum += i;
-	for (i = zero; i < ARR_SZ; i++) {
+
+	for (i = 0; i < ARR_SZ; i++) {
 		barrier_var(i);
 		sum += i + arr[i];
 		cond_break;
@@ -333,11 +333,11 @@  SEC("socket")
 __success __retval(999000000)
 int cond_break2(const void *ctx)
 {
-	int i, j;
+	long i, j;
 	int sum = 0;
 
-	for (i = zero; i < 1000 && can_loop; i++)
-		for (j = zero; j < 1000; j++) {
+	for (i = 0; i < 1000 && can_loop; i++)
+		for (j = 0; j < 1000; j++) {
 			sum += i + j;
 			cond_break;
 	}
@@ -346,9 +346,10 @@  int cond_break2(const void *ctx)
 
 static __noinline int loop(void)
 {
-	int i, sum = 0;
+	int sum = 0;
+	long i;
 
-	for (i = zero; i <= 1000000 && can_loop; i++)
+	for (i = 0; i <= 1000000 && can_loop; i++)
 		sum += i;
 
 	return sum;
@@ -365,7 +366,7 @@  SEC("socket")
 __success __retval(1)
 int cond_break4(const void *ctx)
 {
-	int cnt = zero;
+	int cnt = 0;
 
 	for (;;) {
 		/* should eventually break out of the loop */
@@ -378,7 +379,7 @@  int cond_break4(const void *ctx)
 
 static __noinline int static_subprog(void)
 {
-	int cnt = zero;
+	int cnt = 0;
 
 	for (;;) {
 		cond_break;
@@ -392,7 +393,7 @@  SEC("socket")
 __success __retval(1)
 int cond_break5(const void *ctx)
 {
-	int cnt1 = zero, cnt2;
+	int cnt1 = 0, cnt2;
 
 	for (;;) {
 		cond_break;
diff --git a/tools/testing/selftests/bpf/progs/verifier_reg_equal.c b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
index dc1d8c30fb0e..cc1e7e372daf 100644
--- a/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
+++ b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
@@ -55,4 +55,33 @@  l1_%=:	exit;						\
 	: __clobber_all);
 }
 
+/*
+ * The tests checks that the verifier doesn't WARN_ON in:
+ * if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
+ *     !WARN_ON_ONCE(dst_reg->id != other_dst_reg->id)) {
+ */
+SEC("socket")
+__description("check this_branch_reg->id == other_branch_reg->id")
+__success
+__naked void reg_id(void)
+{
+	asm volatile ("					\
+	call %[bpf_ktime_get_ns];			\
+	.byte 0xe5; /* may_goto */			\
+	.byte 0; /* regs */				\
+	.short 5; /* off of l0_%=: */			\
+	.long 0; /* imm */				\
+	r0 &= 1;					\
+	r2 = r0;					\
+	/* is_branch_taken will predict fallthrough */	\
+	if r2 == 2 goto l0_%=;				\
+	r0 = 0;						\
+	exit;						\
+l0_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";