[PATCH bpf-next v2 1/2] bpf: reject pointer operands for 32-bit recurrences/latches

[Eduard Zingerman <eddyz87@gmail.com>]

Avoid inferring loop bounds for the following program shapes:

     32-bit latch (A)      |    32-bit recurrence (B)
  -------------------------+--------------------------
     r1 = ... pointer ...  |    r1 = ... pointer ...
     r2 = ... pointer ...  |    r2 = ... pointer ...
  l: r1 += 8               | l: w1 += 8
     ...                   |    ...
     if w1 < w2 goto l     |    if r1 < r2 goto l

(A) Scalar bounds for pointers represent only offsets from their
    common origin values. The 32-bit operations also depend on the
    runtime base address: the addresses can wrap at 32 bits without
    the tracked offsets wrapping. Thus, offsets alone do not determine
    the iteration count.

(B) 32-bit operations on pointers either prohibited (wX += 1)
    or convert them to scalars (wX = wX). No need to deal with
    this at SCEV level.

Fixes: df4761bd441c ("bpf: Support 32-bit linear scalar evolution")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/scev.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index fea77772ca96..f9e2ca6a5a12 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -2024,7 +2024,8 @@ static void log_incompatible_scev_values(struct bpf_verifier_env *env, const cha
 }
 
 static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_state *st,
-				  const struct scev_value *a, const struct scev_value *b)
+				  const struct scev_value *a, const struct scev_value *b,
+				  const struct linear_latch *latch)
 {
 	const struct bpf_reg_state *ra, *rb;
 
@@ -2035,7 +2036,7 @@ static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_
 	}
 	ra = scev_reg_for_read(env, st, a->ptr_reg);
 	rb = scev_reg_for_read(env, st, b->ptr_reg);
-	if (ra && rb && bpf_same_memory_origin(ra, rb))
+	if (ra && rb && bpf_same_memory_origin(ra, rb) && !latch->zext32 && !latch->jmp32)
 		return true;
 
 incompatible:
@@ -2267,7 +2268,7 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		}
 		return false;
 	}
-	if (!scev_value_compatible(env, st, &initial_val, &bound_val))
+	if (!scev_value_compatible(env, st, &initial_val, &bound_val, latch))
 		return false;
 
 	initial = initial_val.value;
@@ -2700,6 +2701,9 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
 		reg = scev_reg_for_linear(cur_func, r);
 		/* If SCEV for r is (linear <reg> <slope>) */
 		if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) {
+			/* 32-bit ALU operations on pointers convert them to scalars */
+			if (coefs.zext32 && reg->type != SCALAR_VALUE)
+				goto cant_widen;
 			/* Spills at varying offsets lose precision */
 			if (test_bit(r, loop->store_base_regs)) {
 				spill_base = true;
-- 
2.56.0