This patch improves the refinement of 64bit bounds from the u32 bounds.

u32:     xxx         xxx         xxx         xxx         xxx
     |-----------------------------|-----------------------------|
u64:                        xxxxxxx

The above diagram represents a u32 range mapped on the u64 line.
Because the umin64 doesn't match the u32 bounds, it's clear that it
could be tightened to match the next umin32 value:

u32:     xxx         xxx         xxx         xxx         xxx
     |-----------------------------|-----------------------------|
u64:                             xx

This patch implements the logic for this refinement, for the min and
max bounds of u64 and s64. This refinement only takes place if the 32
lower bits of umin64 are outside of the u32 range. In that case, we
update umin64 to the next matching umin32 value. For the max bounds, we
proceed in the same way, but update umax64 to the previous matching
umax32 value.

Note that when updating the min, we can run into an overflow. It
corresponds to the following case and doesn't require special handling.

u32:     xxx         xxx         xxx         xxx         xxx
     |-----------------------------|-----------------------------|
u64: xxxxxx                                                   xxxx

This patch also updates reg_bounds to implement the same refinement.
That change is small because commit 2fefa9c81a25 ("selftests/bpf: Fix
reg_bounds to match new tnum-based refinement") already implemented
similar logic to the above in reg_bounds.

Together, these changes to the verifier and reg_bounds fix the selftest
"(s64)[0xfffffffe000000ff; 0xffffffff00000000] (u32)<op> S64_MIN+255".

Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 kernel/bpf/verifier.c                         | 50 ++++++++++++++++---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 10 ++--
 2 files changed, 47 insertions(+), 13 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1d5d2b7e5140..bcf8a38a4d72 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2273,17 +2273,51 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
 	 */
 	__u64 new_umin, new_umax;
 	__s64 new_smin, new_smax;
+	__u32 umin_32lower, umax_32lower;
+	__u32 smin_32lower, smax_32lower;
 
 	/* u32 -> u64 tightening, it's always well-formed */
-	new_umin = (reg->umin_value & ~0xffffffffULL) | reg->u32_min_value;
-	new_umax = (reg->umax_value & ~0xffffffffULL) | reg->u32_max_value;
-	reg->umin_value = max_t(u64, reg->umin_value, new_umin);
-	reg->umax_value = min_t(u64, reg->umax_value, new_umax);
+	umin_32lower = reg->umin_value & 0xffffffffULL;
+	if (umin_32lower < reg->u32_min_value || umin_32lower > reg->u32_max_value) {
+		new_umin = (reg->umin_value & ~0xffffffffULL) | reg->u32_min_value;
+		if (new_umin < reg->umin_value)
+			/*
+			 * The potential overflow here corresponds to the
+			 * following case and doesn't require special handling.
+			 *
+			 * u32:     xxx        xxx        xxx        xxx
+			 *      |---------------------|---------------------|
+			 * u64: xxxxxx                                   xxxx
+			 */
+			new_umin += 0x100000000;
+		reg->umin_value = new_umin;
+	}
+	umax_32lower = reg->umax_value & 0xffffffffULL;
+	if (umax_32lower < reg->u32_min_value || umax_32lower > reg->u32_max_value) {
+		new_umax = (reg->umax_value & ~0xffffffffULL) | reg->u32_max_value;
+		if (new_umax > reg->umax_value)
+			/* Cf comment on new_umin for potential overflow. */
+			new_umax -= 0x100000000;
+		reg->umax_value = new_umax;
+	}
+
 	/* u32 -> s64 tightening, u32 range embedded into s64 preserves range validity */
-	new_smin = (reg->smin_value & ~0xffffffffULL) | reg->u32_min_value;
-	new_smax = (reg->smax_value & ~0xffffffffULL) | reg->u32_max_value;
-	reg->smin_value = max_t(s64, reg->smin_value, new_smin);
-	reg->smax_value = min_t(s64, reg->smax_value, new_smax);
+	smin_32lower = reg->smin_value & 0xffffffffULL;
+	if (smin_32lower < reg->u32_min_value || smin_32lower > reg->u32_max_value) {
+		new_smin = (reg->smin_value & ~0xffffffffULL) | reg->u32_min_value;
+		if (new_smin < reg->smin_value)
+			/* Cf comment on new_umin for potential overflow. */
+			new_smin += 0x100000000;
+		reg->smin_value = new_smin;
+	}
+	smax_32lower = reg->smax_value & 0xffffffffULL;
+	if (smax_32lower < reg->u32_min_value || smax_32lower > reg->u32_max_value) {
+		new_smax = (reg->smax_value & ~0xffffffffULL) | reg->u32_max_value;
+		if (new_smax > reg->smax_value)
+			/* Cf comment on new_umin for potential overflow. */
+			new_smax -= 0x100000000;
+		reg->smax_value = new_smax;
+	}
 
 	/* Here we would like to handle a special case after sign extending load,
 	 * when upper bits for a 64-bit range are all 1s or all 0s.
diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
index c0b3a357a0f4..d38550fc1624 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
@@ -500,7 +500,7 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 	    (s64)x.a >= S32_MIN && (s64)x.b <= S32_MAX)
 		return range_intersection(x_t, x, y_cast);
 
-	if (y_t == U32 && x_t == U64) {
+	if (y_t == U32 && !t_is_32(x_t)) {
 		u64 xmin_swap, xmax_swap, xmin_lower32, xmax_lower32;
 
 		xmin_lower32 = x.a & 0xffffffff;
@@ -518,8 +518,8 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 			 */
 			if (xmin_swap < x.a)
 				xmin_swap += 0x100000000;
-			if (xmin_swap == x.b)
-				return range(x_t, x.b, x.b);
+			if (xmin_swap != x.a)
+				return range(x_t, xmin_swap, x.b);
 		} else if (xmax_lower32 < y.a || xmax_lower32 > y.b) {
 			/* Same for the umax64, but we want to *decrease*
 			 * umax64 to the *maximum* value that matches the u32
@@ -528,8 +528,8 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 			xmax_swap = swap_low32(x.b, y.b);
 			if (xmax_swap > x.b)
 				xmax_swap -= 0x100000000;
-			if (xmax_swap == x.a)
-				return range(x_t, x.a, x.a);
+			if (xmax_swap != x.b)
+				return range(x_t, x.a, xmax_swap);
 		}
 	}
 
-- 
2.43.0