[PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for narrowing stack spills

[Vineet Gupta]

Six programs:

 - zext_narrowing_spill_reaches_fill: narrowing while the value is still
   on the stack narrows the slot, and the fill copies an already narrowed
   value. This is the order the link is for
 - zext_narrowing_spill_drops_link: the other order does not pay, since
   the fill is a mov and a mov drops a zero-extending link
 - zext_narrowing_spill_truncates_slot: the slot must be truncated before
   the kind goes on it, or the first sync empties it. Asserted on the
   dump, since nothing downstream rejects an empty slot --
   BPF_F_TEST_REG_INVARIANTS does not walk them
 - zext_narrowing_spill_byte_no_link: a sub-word spill is below the model
 - sext_delta_survives_narrowing_spill: a source carrying a delta hands
   it to the slot
 - sext_fill_of_narrowing_spill_drops_zext: a sign-extending fill of such
   a slot must not come away with its zero-extending link

Posted with the patch above, which is not proposed for merge; these go or
stay with it.

Signed-off-by: Vineet Gupta <vineet.gupta@xxxxxxxxx>
---
v3: was v2 13/13, now tagged [do not merge] with the patch above.
 - zext_narrowing_spill_keeps_link becomes
   zext_narrowing_spill_drops_link: a fill is a mov, and a mov drops
   the link (patch 4)
 - new: zext_narrowing_spill_reaches_fill, the first positive test for
   the spill link, narrowing before the fill
 - new: zext_narrowing_spill_truncates_slot,
   sext_delta_survives_narrowing_spill and
   sext_fill_of_narrowing_spill_drops_zext

 .../bpf/progs/verifier_linked_scalars.c       | 181 ++++++++++++++++++
 1 file changed, 181 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index ab78285153fb..8ade4836e1b2 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -1217,6 +1217,128 @@ __naked void zext_fill_byte_forms_no_link(void)
 	: __clobber_all);
 }
 
+/*
+ * The link does reach a fill, provided the narrowing happens while the value
+ * is still on the stack: sync_linked_regs() walks spilled slots, so narrowing
+ * r6 narrows the slot and the fill copies an already narrowed value. This is
+ * the order the narrowing-spill link is for; the other order is below.
+ */
+SEC("socket")
+__success
+__naked void zext_narrowing_spill_reaches_fill(void)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r6 = r0;						\
+	call %[bpf_get_prandom_u32];				\
+	r0 <<= 32;						\
+	r6 |= r0;		/* r6 = full 64-bit unknown */	\
+	*(u32 *)(r10 - 8) = r6;	/* narrowing spill, forms the link */ \
+	if w6 != 0 goto 1f;	/* narrow r6 while it is on the stack */ \
+	r2 = *(u32 *)(r10 - 8);	/* fill gets the narrowed value */ \
+	if r2 == 0 goto 1f;					\
+	r0 /= 0;						\
+1:								\
+	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * A narrowing spill stores only the source's low 32 bits, so the slot is their
+ * zero-extension. Filling it back is a mov, though, and that drops the link
+ * for the same reason zext_chain_drops_link does, so a later narrowing of the
+ * source does not reach the filled register.
+ */
+SEC("socket")
+__failure
+__msg("div by zero")
+__naked void zext_narrowing_spill_drops_link(void)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r6 = r0;						\
+	call %[bpf_get_prandom_u32];				\
+	r0 <<= 32;						\
+	r6 |= r0;		/* r6 = full 64-bit unknown */	\
+	*(u32 *)(r10 - 8) = r6;	/* narrowing spill, forms the link */ \
+	r2 = *(u32 *)(r10 - 8);	/* fill it back */		\
+	if w6 != 0 goto 1f;	/* narrows r6, propagates to r2 */ \
+	if r2 == 0 goto 1f;					\
+	r0 /= 0;						\
+1:								\
+	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * save_register_state() copies the source register whole, so the slot of a
+ * narrowing spill arrives holding bounds for bits the store never wrote.
+ * Recording BPF_REG_LINK_ZEXT on top of those is a contradiction, and the first
+ * sync_linked_regs() runs straight into it: it rebuilds the slot's low half
+ * correctly and then intersects it against the stale wide bounds, which are
+ * disjoint from it, leaving the slot with an empty range. Nothing downstream
+ * notices -- not even BPF_F_TEST_REG_INVARIANTS, which does not walk stack
+ * slots -- so assert on the dump.
+ */
+SEC("socket")
+__success __log_level(2)
+/* untruncated, the slot kept r6's umin=0x100000000 and went empty on sync */
+__msg("*(u32 *)(r10 -8) = r6 {{.*}} fp-8={{.*}}smin=0,smax=umax=0xffffffff")
+__naked void zext_narrowing_spill_truncates_slot(void)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r6 = r0;						\
+	r7 = 1;							\
+	r7 <<= 32;						\
+	r6 |= r7;		/* r6 >= 2^32, so the spill narrows */ \
+	*(u32 *)(r10 - 8) = r6;	/* slot is (u32)r6 */		\
+	r8 = 1;							\
+	r8 <<= 32;						\
+	r8 += 5;						\
+	if r6 > r8 goto 1f;	/* narrows r6, syncs the slot */ \
+1:								\
+	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * A sub-word spill is below the low-32 model, so no link is formed there.
+ * The fill is a byte load too, so this pins the spill-side and fill-side
+ * size gates together rather than either on its own.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void zext_narrowing_spill_byte_no_link(void)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r6 = r0;						\
+	call %[bpf_get_prandom_u32];				\
+	r0 <<= 32;						\
+	r6 |= r0;						\
+	*(u8 *)(r10 - 8) = r6;	/* 1-byte spill: no link */	\
+	r2 = *(u8 *)(r10 - 8);					\
+	if w6 != 0 goto 1f;					\
+	if r2 == 0 goto 1f;	/* not deduced */		\
+	r0 /= 0;						\
+1:								\
+	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 #ifdef CAN_USE_MOVSX
 
 /*
@@ -1628,6 +1750,36 @@ __naked void sext_delta_survives_narrowing_fill(void)
 	: __clobber_all);
 }
 
+/*
+ * And for a narrowing spill: the slot holds (u32)(r6 + 5). Recording delta 0
+ * there put the slot, and anything filled from it, 5 away from the truth.
+ */
+SEC("socket")
+__success
+__naked void sext_delta_survives_narrowing_spill(void)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r6 = r0;						\
+	r6 <<= 32;						\
+	call %[bpf_get_prandom_u32];				\
+	r6 |= r0;		/* r6 = full 64-bit unknown */	\
+	w7 = w6;		/* BPF_REG_LINK_ZEXT, delta 0 */	\
+	w7 += 5;		/* BPF_REG_LINK_ZEXT, delta 5 */	\
+	r8 = (s32)r7;		/* BPF_REG_LINK_SEXT, delta 5 */	\
+	*(u32 *)(r10 - 8) = r8;	/* narrowing spill keeps delta */ \
+	if r6 != 0 goto 1f;	/* narrow before the fill */	\
+	r2 = *(u32 *)(r10 - 8);	/* r2 == 5, not 0 */		\
+	if r2 == 5 goto 1f;	/* always taken: r2 is 5 */					\
+	r0 /= 0;						\
+1:								\
+	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 #endif /* CAN_USE_MOVSX */
 
 #ifdef CAN_USE_LDSX
@@ -1800,6 +1952,35 @@ __naked void sext_byte_fill_drops_sext_link(void)
 }
 #endif /* CAN_USE_MOVSX */
 
+/*
+ * The same, with the zero-extending link coming from a narrowing spill rather
+ * than a mov. The spill truncated the slot to 32 bits, so the fill is not
+ * narrowing and assigns no link kind of its own; the slot's zero-extending
+ * one must not survive the sign-extending load.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void sext_fill_of_narrowing_spill_drops_zext(void)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r6 = r0;						\
+	call %[bpf_get_prandom_u32];				\
+	r0 <<= 32;						\
+	r6 |= r0;		/* r6 = full 64-bit unknown */	\
+	*(u32 *)(r10 - 8) = r6;	/* narrowing spill: slot is ZEXT */ \
+	r2 = *(s32 *)(r10 - 8);	/* sign-extending, not narrowing */ \
+	if w6 != -1 goto 1f;	/* slot low 32 bits are all ones */ \
+	if r2 s>= 0 goto 1f;	/* taken only if r2 was rebuilt zext */ \
+	r0 /= 0;						\
+1:								\
+	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 #endif /* CAN_USE_LDSX */
 
 char _license[] SEC("license") = "GPL";
-- 
2.53.0-Meta