[PATCH] bpf: Prevent invalid u32 bounds in __reg32_deduce_bounds()

[Andrea Righi]

When refining register bounds, __reg32_deduce_bounds can derive u32
min/max from 64-bit or s32 bounds and assign them with max_t/min_t.

If the existing u32 range and the derived range do not overlap (e.g.,
u64 says [0, 1] while u32 was [2, 2] from an earlier path), the
intersection is empty and the new u32_min_value can end up greater than
u32_max_value, triggering the following warning:

  verifier bug: REG INVARIANTS VIOLATION (false_reg1): range bounds violation
    u64=[0x0, 0x1] s64=[0x0, 0x1] u32=[0x3, 0x1] s32=[0x0, 0x1] var_off=(0x0, 0x1)
  WARNING: kernel/bpf/verifier.c:2742 at reg_bounds_sanity_check
  Call Trace:
    reg_bounds_sanity_check+0xbc/0x1e0
    reg_set_min_max+0x1a2/0x1f0
    check_cond_jmp_op+0x5d2/0x1980
    do_check_common+0x2b0f/0x3410
    do_check_subprogs+0xcd/0x180
    bpf_check+0x33fe/0x3850
    bpf_prog_load+0x7d7/0xee0
    __sys_bpf+0xea2/0x2e30

This was triggered by the scx CI while loading the scx_layered sched_ext
scheduler [1].

Fix by only applying the derived u32 bounds when the resulting range is
valid (u32_min <= u32_max).

[1] https://github.com/sched-ext/scx/pull/3349

Fixes: c1efab6468fd5 ("bpf: derive subreg bounds from full bounds when upper 32 bits are constant")
Signed-off-by: Andrea Righi <arighi@xxxxxxxxxx>
---
 kernel/bpf/verifier.c | 27 +++++++++++++++++++++------
 1 file changed, 21 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index edf5342b982f6..78964c7e9ac99 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2424,8 +2424,13 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
 		/* u64 to u32 casting preserves validity of low 32 bits as
 		 * a range, if upper 32 bits are the same
 		 */
-		reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->umin_value);
-		reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->umax_value);
+		u32 u32_min = max_t(u32, reg->u32_min_value, (u32)reg->umin_value);
+		u32 u32_max = min_t(u32, reg->u32_max_value, (u32)reg->umax_value);
+
+		if (u32_min <= u32_max) {
+			reg->u32_min_value = u32_min;
+			reg->u32_max_value = u32_max;
+		}
 
 		if ((s32)reg->umin_value <= (s32)reg->umax_value) {
 			reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->umin_value);
@@ -2435,8 +2440,13 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
 	if ((reg->smin_value >> 32) == (reg->smax_value >> 32)) {
 		/* low 32 bits should form a proper u32 range */
 		if ((u32)reg->smin_value <= (u32)reg->smax_value) {
-			reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->smin_value);
-			reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->smax_value);
+			u32 u32_min = max_t(u32, reg->u32_min_value, (u32)reg->smin_value);
+			u32 u32_max = min_t(u32, reg->u32_max_value, (u32)reg->smax_value);
+
+			if (u32_min <= u32_max) {
+				reg->u32_min_value = u32_min;
+				reg->u32_max_value = u32_max;
+			}
 		}
 		/* low 32 bits should form a proper s32 range */
 		if ((s32)reg->smin_value <= (s32)reg->smax_value) {
@@ -2479,8 +2489,13 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
 	 * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff.
 	 */
 	if ((u32)reg->s32_min_value <= (u32)reg->s32_max_value) {
-		reg->u32_min_value = max_t(u32, reg->s32_min_value, reg->u32_min_value);
-		reg->u32_max_value = min_t(u32, reg->s32_max_value, reg->u32_max_value);
+		u32 u32_min = max_t(u32, reg->s32_min_value, reg->u32_min_value);
+		u32 u32_max = min_t(u32, reg->s32_max_value, reg->u32_max_value);
+
+		if (u32_min <= u32_max) {
+			reg->u32_min_value = u32_min;
+			reg->u32_max_value = u32_max;
+		}
 	}
 }
 
-- 
2.53.0