Check that a comparison against a pointer whose offset is not bounded
from above does not make the verifier infer that a nullable pointer is
not NULL, and that a bounded offset still does. W/o the previous patch
the first test is accepted.

Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../bpf/progs/verifier_jeq_infer_not_null.c   | 80 +++++++++++++++++++
 1 file changed, 80 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_jeq_infer_not_null.c b/tools/testing/selftests/bpf/progs/verifier_jeq_infer_not_null.c
index b412a542ef76..8657e4a0d601 100644
--- a/tools/testing/selftests/bpf/progs/verifier_jeq_infer_not_null.c
+++ b/tools/testing/selftests/bpf/progs/verifier_jeq_infer_not_null.c
@@ -311,6 +311,86 @@ __naked void untrusted_mem_does_not_infer_map_value_non_null(void)
 	: __clobber_all);
 }
 
+/*
+ * A pointer with an offset that is not bounded from above may be null at
+ * runtime, hence it is not a witness for the pointer it is compared with.
+ */
+SEC("socket")
+__failure
+__msg("error: invalid dereference of R7 (a nullable map value pointer)")
+__naked void unbounded_offset_does_not_infer_map_value_non_null(void)
+{
+	asm volatile ("					\
+	/* r6 = bpf_map_lookup_elem(map_hash, &0); */	\
+	*(u64 *)(r10 - 8) = 0;				\
+	r1 = %[map_hash] ll;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	call %[bpf_map_lookup_elem];			\
+	if r0 == 0 goto 1f;				\
+	r6 = r0;					\
+	/* r7 = bpf_map_lookup_elem(map_hash, &1); */	\
+	*(u64 *)(r10 - 8) = 1;				\
+	r1 = %[map_hash] ll;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	call %[bpf_map_lookup_elem];			\
+	r7 = r0;					\
+	/* pointer - pointer is an unknown scalar */	\
+	r8 = r7;					\
+	r8 -= r6;					\
+	/* r8 is in [0, S64_MAX] */			\
+	r8 <<= 1;					\
+	r8 >>= 1;					\
+	/* r6 may wrap to zero at runtime */		\
+	r6 += r8;					\
+	if r7 != r6 goto 1f;				\
+	r0 = *(u8 *)(r7 + 0);				\
+1:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash)
+	: __clobber_all);
+}
+
+/* Same, but the offset is bounded, so the inference is still done. */
+SEC("socket")
+__success
+__naked void bounded_offset_infers_map_value_non_null(void)
+{
+	asm volatile ("					\
+	/* r6 = bpf_map_lookup_elem(map_hash, &0); */	\
+	*(u64 *)(r10 - 8) = 0;				\
+	r1 = %[map_hash] ll;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	call %[bpf_map_lookup_elem];			\
+	if r0 == 0 goto 1f;				\
+	r6 = r0;					\
+	/* r7 = bpf_map_lookup_elem(map_hash, &1); */	\
+	*(u64 *)(r10 - 8) = 1;				\
+	r1 = %[map_hash] ll;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	call %[bpf_map_lookup_elem];			\
+	r7 = r0;					\
+	/* pointer - pointer is an unknown scalar */	\
+	r8 = r7;					\
+	r8 -= r6;					\
+	/* r8 is in [0, 3] */				\
+	r8 &= 3;					\
+	r6 += r8;					\
+	if r7 != r6 goto 1f;				\
+	r0 = *(u8 *)(r7 + 0);				\
+1:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash)
+	: __clobber_all);
+}
+
 void kfunc_root(void)
 {
 	bpf_rdonly_cast(0, 0);
-- 
2.55.0