Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Youlin Li <liulin063@gmail.com>
To:     daniel@iogearbox.net, haoluo@google.com
Cc:     ast@kernel.org, john.fastabend@gmail.com, andrii@kernel.org,
        martin.lau@linux.dev, song@kernel.org, yhs@fb.com,
        kpsingh@kernel.org, sdf@google.com, jolsa@kernel.org,
        bpf@vger.kernel.org, linux-kernel@vger.kernel.org,
        Youlin Li <liulin063@gmail.com>
Subject: [PATCH bpf v2 1/2] bpf: Do more tight ALU bounds tracking
Date:   Sat, 27 Aug 2022 21:57:11 +0800
Message-Id: <20220827135711.21507-1-liulin063@gmail.com>
In-Reply-To: <5d2addca-10e5-f7a6-9efd-43322eec8347@iogearbox.net>
References: <5d2addca-10e5-f7a6-9efd-43322eec8347@iogearbox.net>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
to get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().

Note that we cannot simply add a call to __reg_combine_64_into_32(). In
previous versions of the code, when __reg_combine_64_into_32() was
called, the 32bit boundary was completely deduced from the 64bit
boundary, so there was a call to __mark_reg32_unbounded() in
__reg_combine_64_into_32(). But in adjust_scalar_min_max_vals(), the 32bit
bounds are already calculated to some extent, and __mark_reg32_unbounded()
will eliminate these information.

Simply copying a code without __mark_reg32_unbounded() should work.

Also, we can now fold reg_bounds_sync() into zext_32_to_64().

Before:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
    6: (95) exit

It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.

After:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
    6: (95) exit

Signed-off-by: Youlin Li <liulin063@gmail.com>
---
v1 -> v2:
    Replaced the call to __reg_combine_64_into_32() with the code in
    __reg_combine_64_into_32(), and removed the call to
    __mark_reg32_unbounded().

Sorry for the delay, I've been busy looking for a job recently :)

 kernel/bpf/verifier.c | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3eadb14e090b..b7403773e834 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4383,6 +4383,7 @@ static void zext_32_to_64(struct bpf_reg_state *reg)
 {
 	reg->var_off = tnum_subreg(reg->var_off);
 	__reg_assign_32_into_64(reg);
+	reg_bounds_sync(reg);
 }
 
 /* truncate register to smaller size (in bytes)
@@ -9010,10 +9011,22 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		break;
 	}
 
-	/* ALU32 ops are zero extended into 64bit register */
-	if (alu32)
+	if (alu32) {
+		/* ALU32 ops are zero extended into 64bit register */
 		zext_32_to_64(dst_reg);
-	reg_bounds_sync(dst_reg);
+	} else {
+		if (__reg64_bound_s32(dst_reg->smin_value) &&
+		    __reg64_bound_s32(dst_reg->smax_value)) {
+			dst_reg->s32_min_value = (s32)dst_reg->smin_value;
+			dst_reg->s32_max_value = (s32)dst_reg->smax_value;
+		}
+		if (__reg64_bound_u32(dst_reg->umin_value) &&
+		    __reg64_bound_u32(dst_reg->umax_value)) {
+			dst_reg->u32_min_value = (u32)dst_reg->umin_value;
+			dst_reg->u32_max_value = (u32)dst_reg->umax_value;
+		}
+		reg_bounds_sync(dst_reg);
+	}
 	return 0;
 }
 
@@ -9202,7 +9215,6 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 							 insn->dst_reg);
 				}
 				zext_32_to_64(dst_reg);
-				reg_bounds_sync(dst_reg);
 			}
 		} else {
 			/* case: R = imm
-- 
2.25.1