From nobody Fri Dec 19 20:32:49 2025 Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com [209.85.221.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 792A2338F26 for ; Thu, 6 Nov 2025 12:53:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762433627; cv=none; b=BxTcUe9CUKXxmKt2uzp4K+Hb4IOPnmboZ5YSAW67qmJRH1276XEGnT8MdWJj9HxC0bgOI9xy+itA/yDWSZfxgWiHVDvu6tRfg3jFyuSA9n9SNsrBemcdjZwYx1mY+L32uddDNEkihnFxLKA8+oFAzQvwG/JlYsVZf77PY7LI25I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762433627; c=relaxed/simple; bh=ic+gOBYrHkh39eOmG4GQwcvbU3ifr1hE78B2se07zwc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=OtcaFT+ZoQxX09eb8Q9qsEhQ+AC/rBzN45d1GPh7WS8yTjPhN1FkUVG+IQTet/0T5hm8rYPvwoxvcqvJToWxTmtnLa4Ju/JjAmS+dg5qtaL255OVf6TndQyTKD6x+eF+luBy7MdvfFA+Xcb1wWSl7M0i8kX1yV1lEfTOqwmGtY0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=nfbcxNqy; arc=none smtp.client-ip=209.85.221.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nfbcxNqy" Received: by mail-wr1-f53.google.com with SMTP id ffacd0b85a97d-421851bca51so768837f8f.1 for ; Thu, 06 Nov 2025 04:53:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762433623; x=1763038423; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=8BVecavUPRiHXmHkxwJOxXNf9imfUNAzPBNe3t0kkm0=; b=nfbcxNqyWvXuIrAjO8EePloZWZV6MsKkuS/ZeMGAkF1/D06PnkqKC3LNwC8zZI4Ccc PvvWlPieXlBArGq5dVl2OjRNraIZHb+z6JbslivOJb95VJOAtRxyCepZ4GGZC2hYkdtC Rhlbva5ZjJ1T290lpl4mFaIQbYI9HhgQQM71c6j5S2ab/aFyL/uVFCxZYakXgIg36QL0 yNvMX1lMpcSbWG3+zsw1ISFlXsGcMDD/mq96ih/nkQrP00AN+lyzxBKJfnXr30aQ+ukW cjx5vbD64IAvjC2dxuSLv5B5o/266trnOrvRiKGYMy9+9hPOJQLS/49i7zGfqNpggcDS vIbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762433623; x=1763038423; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8BVecavUPRiHXmHkxwJOxXNf9imfUNAzPBNe3t0kkm0=; b=LO0luoHPJWYeqM/EQCG96KcZk2VWvAj+HqmFtRtXse/kZe3Yl2E/Micyuem3YCsdI7 K+2llgkQF4pIMzZOE6M0s6Z3h1+0cSB7K+Nu/30JOgrCiNr1DvE34VbigtaygNMTvoc8 mMmg9tBIo7Kod2jzKv4g9RBlHdLobKF1mR0EMMQYGf/BF54ItpXZrrHmtxAaHisVgj+V 4hc4eAhO2Yc9MKfNpZj1/3Kk9ugUt7VIGrM9sDguqTPxYr7cu+puaeI3f4ZE7NlJQcRT xbgDnjHM0PKjkOCwMhIO2g4eAVgEYTBRi1Mx3x/E7nKmPK31eW9ePyTGAaU6wr1uAEMY m+GA== X-Forwarded-Encrypted: i=1; AJvYcCVRG94ZTwN5UYU/cKA4GqnPotV+J2nRgskUftrUGEO2drRl6FwPMdk5uoA9joYbO8QeeDPXVTKP9iuToJE=@vger.kernel.org X-Gm-Message-State: AOJu0YzKLyNO7Ij6tBUx1kSST2/S3O0Ot85z0Zs0lT9hOixxZPUlUKaB 5P7wuvZmPiksiRvgElwpiEN4GA/4Ng3JAvnTUuwONtvXGvC5j6uitBM= X-Gm-Gg: ASbGncuCjFe1vl76RqKH1OmGGiY2ocHPOKqf3eLVnfVNAB26lrWBN7Qy2DA8r4zfmZM NUr1HOb4iJIXXTVehqdV0VySibRnJ3U19ttkenHibyKje4NY4jy0s3yLPaKZ9xs2odhoekvESXG WKjSlbBgWN1C/ToRcO7BC7Zis4TAJvQvSFNH7ZDWMQUE2EonTxFtXwyRXBq5LheZYPqJ9WFIxVR 22lDtjwoRo62Q5LDK8Ehj9IFTgg6KgaDMYL30K557r038paafxScghDhLQ4ZlSysRkTRvPdgT3k ZVljn0NnmqEe5DAUNEqH6zH/DqnC6pbG55WxFXCWS7lHkDM6cDHXo88F+DLxBfycaDj3mpEA7H3 KruZeW3axpPJ2F6vilGICC7E3GVoqg5ZFysKw9JATzAWuvicc4pxytjhNHxRUde3n1J1LV/eC1B IbN2BJX10kvrlzM0BKGugg+bMaBguoTrKBShmRtMSYvHOhJGeqzwBjJl/QuaP2sURA9w== X-Google-Smtp-Source: AGHT+IHyCbG6Ib5B/hxvhvU1M9zTmkq15fseYuID4g2BHydDK2L/8J6Y6qTfp+dgmtEKmD6926vZsg== X-Received: by 2002:a05:6000:2502:b0:427:454:43b4 with SMTP id ffacd0b85a97d-429e330ab16mr6604348f8f.48.1762433623418; Thu, 06 Nov 2025 04:53:43 -0800 (PST) Received: from ast-epyc5.inf.ethz.ch (ast-epyc5.inf.ethz.ch. [129.132.161.180]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-429eb40379esm4788856f8f.9.2025.11.06.04.53.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 04:53:43 -0800 (PST) From: Hao Sun X-Google-Original-From: Hao Sun To: bpf@vger.kernel.org Cc: ast@kernel.org, daniel@iogearbox.net, andrii@kernel.org, eddyz87@gmail.com, john.fastabend@gmail.com, martin.lau@linux.dev, song@kernel.org, yonghong.song@linux.dev, linux-kernel@vger.kernel.org, sunhao.th@gmail.com, Hao Sun Subject: [PATCH RFC 13/17] bpf: Skip state pruning for the parent states Date: Thu, 6 Nov 2025 13:52:51 +0100 Message-Id: <20251106125255.1969938-14-hao.sun@inf.ethz.ch> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106125255.1969938-1-hao.sun@inf.ethz.ch> References: <20251106125255.1969938-1-hao.sun@inf.ethz.ch> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Different incoming paths to the same instruction may yield different path conditions; pruning by containment would drop paths with different constrai= nts. - Add `children_unsafe` flag to `struct bpf_verifier_state`. - In `is_state_visited()`, if a visited candidate has `children_unsafe`, tr= eat it as a miss. - Propagate `children_unsafe` to the next state on split and clear it in the current state when pushing a new parent. - After a refinement request, clear all `bcf_expr` in registers and mark all collected parents (except the base) as `children_unsafe` to avoid pruning alternative suffixes that may build different path conditions. Signed-off-by: Hao Sun --- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 18 ++++++++++++++++++ 2 files changed, 19 insertions(+) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index b430702784e2..9b91353a86d7 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -422,6 +422,7 @@ struct bpf_verifier_state { bool speculative; bool in_sleepable; bool cleaned; + bool children_unsafe; =20 /* first and last insn idx of this verifier state */ u32 first_insn_idx; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index f1e8e70f9f61..ec0e736f39c5 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -19904,6 +19904,8 @@ static int is_state_visited(struct bpf_verifier_env= *env, int insn_idx) states_cnt++; if (sl->state.insn_idx !=3D insn_idx) continue; + if (sl->state.children_unsafe) + goto miss; =20 if (sl->state.branches) { struct bpf_func_state *frame =3D sl->state.frame[sl->state.curframe]; @@ -20216,6 +20218,8 @@ static int is_state_visited(struct bpf_verifier_env= *env, int insn_idx) return err; } =20 + new->children_unsafe =3D cur->children_unsafe; + cur->children_unsafe =3D false; cur->parent =3D new; cur->first_insn_idx =3D insn_idx; cur->dfs_depth =3D new->dfs_depth + 1; @@ -24272,6 +24276,20 @@ static int __used bcf_refine(struct bpf_verifier_e= nv *env, if (!err && (env->bcf.refine_cond >=3D 0 || env->bcf.path_cond >=3D 0)) mark_bcf_requested(env); =20 + for (i =3D 0; i < MAX_BPF_REG; i++) + regs[i].bcf_expr =3D -1; + + /* + * Mark the parents as children_unsafe, i.e., they are not safe for + * state pruning anymore. Say s0 is contained in s1 (marked), then + * exploring s0 will reach the same error state that triggers the + * refinement. However, since the path they reach the pruning point + * can be different, the path condition collected for s0 can be + * different from s1's. Hence, pruning is not safe. + */ + for (i =3D 0; i < bcf->vstate_cnt - 1; i++) + bcf->parents[i]->children_unsafe =3D true; + kfree(env->bcf.parents); return err ?: 1; } --=20 2.34.1