From patchwork Sun Dec 10 13:00:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Menglong Dong X-Patchwork-Id: 176333 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:bcd1:0:b0:403:3b70:6f57 with SMTP id r17csp6501976vqy; Sun, 10 Dec 2023 05:00:56 -0800 (PST) X-Google-Smtp-Source: AGHT+IE4veaLl3ADVeWYXVHEzHzLdz/3k1G0JFlJ8iMCtFs0d0E0r17WK/Ec58Ba+8uPPRqqQdh2 X-Received: by 2002:a05:6870:418c:b0:1fb:75b:12fd with SMTP id y12-20020a056870418c00b001fb075b12fdmr3741829oac.79.1702213256384; Sun, 10 Dec 2023 05:00:56 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1702213256; cv=none; d=google.com; s=arc-20160816; b=dQm+MOcYa6BEC2MuS2E5fneK6P5DkghActZpXFhhkXiPwfvNL7qGQx8dz2GCrc1kaG jBplGc/WNiCmuFt1dNp0p4gEV9kCRirFjfGnzCH9JWmm9A1btCfeYJqU5cOBHXNC/dXV 9L6u6a6eGfdrN8cVhmz1luPRO2E83rxFFm/Fxsli/c8ZOWYZwbtM+ZfaoaJiZkmuVw8t sBQTy3394as2HwgbRHm5UCPsyxvtSh57byAgahNG0mDPkL37C6w9DAJ2gr6RO3pBRy5V U30olNmpk/xkFn96Q/n9u1mWvZ9GKL5yDDGHQ++vG9/aOeKLdTS2HRMcSF5kkU1XB5SZ JgeQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :message-id:date:subject:cc:to:from:dkim-signature; bh=HKccvv63j0QYkaerqhaF/v4uQMT1J4GxnBO3+iS7dFM=; fh=5o6H2CaPff4H4axjvh3jFgrQvO/fkdmKNgmYSy+jBl0=; b=XDvSX2T7422B606vJ8X3hPJf95XFaKvwJrkUqzJh4+3MvMcbqo3TIjOMGTmt8Scxqd /T9EnhvVrNjr5NC0KagIrOr1N0bpnauGMvMJEHGBExjVk/tq8+StrU99H13c5qqDCT9B 0nZ0D32cmjl4ZldgbwoQr/ltywdhmSSXmrrdTNn1HE0RfTYkEzJxYIv0inwVJbkdOvBh 8wCcrl8CLAJ5ELEurBMI5BeHqGcng9v+dvmbbTVAuB2Jl0h5Ym2WHUi2lz5st9H2kaFn ZpobQY8+RbIdvJoPT7pvleVNNHaKxDmIZj7AJUUMbta8YBm9Hki/XfxAb+b/31YFZLhE /s3A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b="J/ZM2PDZ"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from snail.vger.email (snail.vger.email. [23.128.96.37]) by mx.google.com with ESMTPS id b13-20020a630c0d000000b005bda77217eesi4525298pgl.209.2023.12.10.05.00.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Dec 2023 05:00:56 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 as permitted sender) client-ip=23.128.96.37; Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b="J/ZM2PDZ"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by snail.vger.email (Postfix) with ESMTP id 3151280793D8; Sun, 10 Dec 2023 05:00:39 -0800 (PST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.11 at snail.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229518AbjLJNA3 (ORCPT + 99 others); Sun, 10 Dec 2023 08:00:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58620 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229584AbjLJNA1 (ORCPT ); Sun, 10 Dec 2023 08:00:27 -0500 Received: from mail-oi1-x242.google.com (mail-oi1-x242.google.com [IPv6:2607:f8b0:4864:20::242]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 20A7CFE; Sun, 10 Dec 2023 05:00:34 -0800 (PST) Received: by mail-oi1-x242.google.com with SMTP id 5614622812f47-3b9d2b8c3c6so2698890b6e.1; Sun, 10 Dec 2023 05:00:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1702213233; x=1702818033; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=HKccvv63j0QYkaerqhaF/v4uQMT1J4GxnBO3+iS7dFM=; b=J/ZM2PDZx+8iD22133s9ewn8MBDANi8atyy2N/c29aetbwKoI8ViUdP42q8s4fczEH p9fqRp732GoaOvp/CbFeWAJfYO3ThXgDZOrvU7U+aBJrPpPQgtXXDy88S8WHHJJt8iL8 /LpbuzfBIJ+Xc0SHPPsChO/XvFZLqk+0nXYIyyxqpqUGNa2xTsERs+i8Hk9N9DCIq4C4 fKWpu1+0RmJE56w9Hj6Ld2Mgn3KqeXMkPAnWNuBEIJtsJoOi+Ta8WAJaNHwgxCvY9mO1 ou2ZI4AWoEnZ+RzULd+D+2jIQu/+ILzWaTqD+ZIjbHh6+gFv8ELmD7ZcWN5dI25+TifV 514g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1702213233; x=1702818033; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=HKccvv63j0QYkaerqhaF/v4uQMT1J4GxnBO3+iS7dFM=; b=lODqYAMmnHvB4qei7dxbe5heUoe2jUT5TRnmWwa3D0wgMyYzjL8MjGZCAt12WyuKm+ FFd8aptY0WD13gk+UD3ViU2d/TH2tPyjlmChEbUYb+lm+3Ryv4E7LXsC1AhJ4AENw0Pr 4WUhbQi7cd+nXNpOu4uiEnvw7kaIv1IBLc8g/OckDnhp+9aK6k2V4XMrZasjjxjn8cf/ WFGF8sioPG1TXBc4TSlfy8AQ7H79BuzUxMOQfA4wx0N8gbztpjBnfWz6jj38UF3fnZaD bGrs20WII+jN5dAKewR56ztp0TMLbGjHpuHkEpt87WgeQmy4I1h7iz2r+r9Sr9gzf2db BKJQ== X-Gm-Message-State: AOJu0YwM3V+8DMcLAP0t08KCa6tajC0ziAtLXBhmKl0wJ3lF4N8kC/Lh iIPL+b1S4q4Bsum/wSAtVwM= X-Received: by 2002:a54:411a:0:b0:3b9:e853:a423 with SMTP id l26-20020a54411a000000b003b9e853a423mr3313755oic.109.1702213233284; Sun, 10 Dec 2023 05:00:33 -0800 (PST) Received: from localhost.localdomain ([43.129.244.20]) by smtp.gmail.com with ESMTPSA id d8-20020a056a00198800b006cee656cb35sm3420067pfl.156.2023.12.10.05.00.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Dec 2023 05:00:32 -0800 (PST) From: Menglong Dong To: andrii@kernel.org Cc: ast@kernel.org, daniel@iogearbox.net, john.fastabend@gmail.com, martin.lau@linux.dev, song@kernel.org, yonghong.song@linux.dev, kpsingh@kernel.org, sdf@google.com, haoluo@google.com, jolsa@kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org, Menglong Dong Subject: [PATCH bpf-next] bpf: make the verifier trace the "not qeual" for regs Date: Sun, 10 Dec 2023 21:00:01 +0800 Message-Id: <20231210130001.2050847-1-menglong8.dong@gmail.com> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM, RCVD_IN_DNSWL_BLOCKED,SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Sun, 10 Dec 2023 05:00:39 -0800 (PST) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1784899967696347095 X-GMAIL-MSGID: 1784899967696347095 We can derive some new information for BPF_JNE in regs_refine_cond_op(). Take following code for example: /* The type of "a" is u16 */ if (a > 0 && a < 100) { /* the range of the register for a is [0, 99], not [1, 99], * and will cause the following error: * * invalid zero-sized read * * as a can be 0. */ bpf_skb_store_bytes(skb, xx, xx, a, 0); } In the code above, "a > 0" will be compiled to "jmp xxx if a == 0". In the TRUE branch, the dst_reg will be marked as known to 0. However, in the fallthrough(FALSE) branch, the dst_reg will not be handled, which makes the [min, max] for a is [0, 99], not [1, 99]. For BPF_JNE, we can reduce the range of the dst reg if the src reg is a const and is exactly the edge of the dst reg. Signed-off-by: Menglong Dong --- kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 44 insertions(+), 1 deletion(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 727a59e4a647..7b074ac93190 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg) reg->type = SCALAR_VALUE; } +#define CHECK_REG_MIN(value) \ +do { \ + if ((value) == (typeof(value))imm) \ + value++; \ +} while (0) + +#define CHECK_REG_MAX(value) \ +do { \ + if ((value) == (typeof(value))imm) \ + value--; \ +} while (0) + +static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm) +{ + CHECK_REG_MIN(reg->s32_min_value); + CHECK_REG_MAX(reg->s32_max_value); + CHECK_REG_MIN(reg->u32_min_value); + CHECK_REG_MAX(reg->u32_max_value); +} + +static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm) +{ + CHECK_REG_MIN(reg->smin_value); + CHECK_REG_MAX(reg->smax_value); + + CHECK_REG_MIN(reg->umin_value); + CHECK_REG_MAX(reg->umax_value); + + CHECK_REG_MIN(reg->s32_min_value); + CHECK_REG_MAX(reg->s32_max_value); + CHECK_REG_MIN(reg->u32_min_value); + CHECK_REG_MAX(reg->u32_max_value); +} + static void mark_reg_known_zero(struct bpf_verifier_env *env, struct bpf_reg_state *regs, u32 regno) { @@ -14332,7 +14366,16 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state } break; case BPF_JNE: - /* we don't derive any new information for inequality yet */ + /* try to recompute the bound of reg1 if reg2 is a const and + * is exactly the edge of reg1. + */ + if (is_reg_const(reg2, is_jmp32)) { + val = reg_const_value(reg2, is_jmp32); + if (is_jmp32) + mark_reg32_not_equal(reg1, val); + else + mark_reg_not_equal(reg1, val); + } break; case BPF_JSET: if (!is_reg_const(reg2, is_jmp32))