From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pj1-f44.google.com (mail-pj1-f44.google.com [209.85.216.44]) (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 9DB133BF2EE for ; Thu, 15 Jan 2026 18:52:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.44 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768503179; cv=none; b=L4GLyltahXOzOZET8occBtHSxDw8ijHYOcYW4hxZqbwZcIGKkgd9PmrSM4GhD3ZlYaEZAfVhwT0dfYMZCEm5NF9R8myknsMARXus+BXXE/togg0VV0vzcxYH/+o7I1MfD4IDQ586Z1PePGZ+bwlpBaDBuOJ6TnJgk3VKKmwz1OU= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768503179; c=relaxed/simple; bh=GK8dfjZb/iQYscKyU7AZCwNhZkFG/slojnCBvoIg1r0=; h=Message-ID:Subject:From:To:Cc:Date:In-Reply-To:References: Content-Type:MIME-Version; b=gh50lbYdO0GFuwqcoQZT9R0/ZZSmeBihbhsYitRwzHcuhmbe0EuyUxeyTFLw92O4nLcF6xKBoD1AWz0moJPXTX0ZB5Ftw3xjVgYKHWilexNcU8QpPuwgFrRMuZ8qmBEw7cCiNwcVFW+B8Vf0L3/GYPUd8vIKAKMeUqRJoDa9Dfw= 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=mw5u/Cb4; arc=none smtp.client-ip=209.85.216.44 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="mw5u/Cb4" Received: by mail-pj1-f44.google.com with SMTP id 98e67ed59e1d1-34ccdcbe520so797841a91.1 for ; Thu, 15 Jan 2026 10:52:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1768503178; x=1769107978; darn=vger.kernel.org; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:from:to:cc:subject :date:message-id:reply-to; bh=nuRnK6v+THA8EMuQwdCqiwUBSoTg/diTmevZF3L//tk=; b=mw5u/Cb4aYs9fr2BzmDmUy0W+KRTpSJo1DSfXa+n5A4fMQ5JWeXiSus4HxtlVvOmum 8G3K2KY0x7C1JxohQ+PUsy9uXhI62zcOIxk26Lrh3aJ+2CFdfPEmBIAZGsjCAMZsPp/A RVHutEATddqCpc2SPePme+T/tBm+130hfG2+YDkgdBpVSiX+ciWCMtenrBBO13QZix0F 649w6fuNJ1R2PgG6a7Cen7gNfAWOSGb4fKTChUknQ7UCsLvQbmDyY/9MeLZxC4sd5HJs bFA1wJAZeZdL64ku5GI1wZ5J0+YlmxpYBNXGyTVrr2L/N/+4+gLUWBiTT1d4T9xwgQ1v MNNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768503178; x=1769107978; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=nuRnK6v+THA8EMuQwdCqiwUBSoTg/diTmevZF3L//tk=; b=QiTpLLR/Z3WXm5VW8Fvdwd5GR1oyjR5X8cnOLv8wLbTZtiAOXQwTCa8djcYAV9QFf8 GgmLYRUmySlk4Aq+5exJQI4wtJynGAn4Le/5vEahckUDLKfQKaDHQq41phDQrEkNGj72 RQQRxNh2l/tDoEaNz/VRgr6xM+I7beYVQ5JyJJS3ik699VFQvMbfU2kUnZuId8KeqwQG b0UkuwZh1rxV+JJfwywZOrZlFcIrMOB52mwlUdUBhSjoeYtbwruT7/UagBnm4Voe+g1b 9K7hfIiT+yaWAkB3DOwwODLCg8+LTxUDIHGeRkB/wfaU+xGoWJ8mZDdtZl7XfcILpIVR rRSQ== X-Forwarded-Encrypted: i=1; AJvYcCU8pQ7dV6530e+HVFebaDc3/qVz9pA9dq6/Qwr/595FjJfh1QLs0c0fb60atPGbVV0HXOI9q4PJC0+d3H8=@vger.kernel.org X-Gm-Message-State: AOJu0Yx5g+IP85/jELAf7PquLIGMWd/3Pbw5sfB5N+n7Frq/+gDfLknb w5WPArEJbDFd3eL+IHLjfrb/7fM6rJYRc4zmxf6MOycfqB5miQDPSGP8 X-Gm-Gg: AY/fxX7vrrku3fTXXqCzr+k2Punks1WXGDUAbG8pw0JiXhnmVM8EToRUZ+ecOqx42AM GkSJ8auWj9+XzYnrSjoDo5udfnCUujVlS0UnxaRjFibIWFekb4dqqethaLZMuypkkRtCTET8NaE mNqeTguK4xQpwsXZPLvX7a3iUWV6yE4UkBqNHTXwd7NJMOd2h6iNzf/hHEHhlGZHFvmnCaZzq9g /epOsQKwqcKOLeTEqI3zqfY/DlqMey/emiDvwEdIpFfSvmkKd65mAl2iAl7RUd9y605OpQO+gj0 0ZHUS1peQ+Gxm8juiTyc+/yX9uYIz+UFbnap1JwYD56VCm3xtzTWHAdULTToTGom7LSE6m8k8cU nFzXoM0O3TvpbP2Kf4pJQ8Ke5A6G1O2H+4tYV4Pgs0AnK6zfwz91iYkpr1hkWCM+byBTA/04WIC O6lx0TZ/jwm3xHUdwMAO4e9j195wE7WDqed4eMYCte X-Received: by 2002:a17:90b:2b86:b0:34c:9cec:3898 with SMTP id 98e67ed59e1d1-352678d9b78mr3573117a91.13.1768503177800; Thu, 15 Jan 2026 10:52:57 -0800 (PST) Received: from [192.168.0.226] ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-c5edf3791e4sm148416a12.31.2026.01.15.10.52.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Jan 2026 10:52:57 -0800 (PST) Message-ID: Subject: Re: [PATCH] bpf/verifier: optimize precision backtracking by skipping precise bits From: Eduard Zingerman To: wujing , Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko Cc: Martin KaFai Lau , Song Liu , Yonghong Song , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , bpf@vger.kernel.org, linux-kernel@vger.kernel.org, Qiliang Yuan Date: Thu, 15 Jan 2026 10:52:54 -0800 In-Reply-To: <20260115150405.443581-1-realwujing@gmail.com> References: <20260115150405.443581-1-realwujing@gmail.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable User-Agent: Evolution 3.58.2 (3.58.2-1.fc43) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 On Thu, 2026-01-15 at 23:04 +0800, wujing wrote: > Backtracking is one of the most expensive parts of the verifier. When > marking precision, currently the verifier always triggers the full > __mark_chain_precision even if the target register or stack slot is > already marked as precise. > > Since a precise mark in a state implies that all necessary ancestors > have already been backtracked and marked accordingly, we can safely > skip the backtracking process if the bit is already set. > > This patch implements early exit logic in: > 1. mark_chain_precision: Check if the register is already precise. > 2. propagate_precision: Skip registers and stack slots that are already > precise in the current state when propagating from an old state. > > This significantly reduces redundant backtracking in complex BPF > programs with frequent state pruning and merges. > > Signed-off-by: wujing > Signed-off-by: Qiliang Yuan > --- __mark_chain_precision already stops propagation at states boundary. States are introduced often, so I don't think this patch solves a real world problem. In any case, the correct place to put such checks is the bt setup code in __mark_chain_precision: static int __mark_chain_precision(...) { ... func =3D st->frame[bt->frame]; if (regno >=3D 0) { reg =3D &func->regs[regno]; if (reg->type !=3D SCALAR_VALUE) { verifier_bug(env, "backtracking misuse"); return -EFAULT; } >>>>> add a condition here <<<<< bt_set_reg(bt, regno); } ... } But unless you see real measurable performance improvement, I don't think the code should be changed. [...]