From nobody Sat Feb 7 17:55:53 2026 Received: from mail-dy1-f173.google.com (mail-dy1-f173.google.com [74.125.82.173]) (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 3F9A531D371 for ; Fri, 16 Jan 2026 04:58:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768539534; cv=none; b=cL2BG9onJ8XR4+wkVZvW0dj6Zyx+gBnPmlQc706vIQLkmtuejhEe8WWV+XrsIvzqRZo6cy37SmNgDvy8cCce6ww+NvjywF3ueVdx0i1GmpmZRzRNzEWKVobQc3ttu+nKZDuwZrhRxLlNCNUXq9Iq+0Ii9bgmH6iLBwSXlInM5Qo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768539534; c=relaxed/simple; bh=+JtErU4IsTTu5VsF09kHgDaqBgZ+Eh9d+qw9x/9WOBQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=agYEJt7WdIqj54ky/sd5NDemiEjtPab2lYqlJqFxTJeisMN9NA+bUJwZBVhuFkPrW9FAPv6NNU+wvvNg4gZpJanR6WRsP/RIbBeHU3yCZLAgCYCOByOzN6IqEIwLADoYJP8ith6lvIUOhNcPi+9wqa1fx5Aojo5P+HS+VZfNvKM= 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=OTwp+OJq; arc=none smtp.client-ip=74.125.82.173 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="OTwp+OJq" Received: by mail-dy1-f173.google.com with SMTP id 5a478bee46e88-2ae38f81be1so2232490eec.0 for ; Thu, 15 Jan 2026 20:58:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1768539530; x=1769144330; 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=PakQjvDWLKrfOt/1Dta85wOj3KGWWuK3r87J5UJgoug=; b=OTwp+OJqej38UGImID3CABgBUBLS3b4ii1W1YJGKTD6j4g6ajQu1YlxJvqLrR7NjR2 CISYAm3//ul/zXccP0jEscMnM7YOKhRvEpTekv7IkURBJwZISy/k86HJqp1z0FtmmlM5 jx/FIALZWgydK9+lpORzlhJ3FQO7IldN8ac2MraweIO7J6r5TH+29ZdG0mIiFuaPldiK 4msbvF99S1rQj5cHNfzkWdsP7QdRNosKF8zzDnfOFlIG4KC2/C5oCl4jnypkI3lLzJ43 pc8MnFLl1sH2+WMetT2RhGjb8aRI6xB4HEIKTJP0UhRBmmGCF1pOdUlGhQSdQfxpvfcx l/ZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768539530; x=1769144330; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=PakQjvDWLKrfOt/1Dta85wOj3KGWWuK3r87J5UJgoug=; b=Nsbr3/bWoV+peE9QCu2Mz7z09ajaHCA757p5izYrRRV19LbHMq8amycU2YDlVVc+JL Kf0epAu2FEM/uKLvuNgMgt39Hjn9Kc33DbLhwFzNIo8bMAP9BOiMvSOMoWU+QX1Sn0uI H6ghRFb6/AzxeKnDa8BikvHknd2nw0KDJofEW34EF5fdHdgLXCDaASbVclPs4fTNvvBV xjt9QK1v2WRYHIKFI2YTh3CUiIQDquZhkYsLBXBEvHjofdgwbLXWHp9GGoGXNSocWiDM Y7KSeTjTjx7AGpItKCP9u6IYe2m14V0rc+iD3e/GhEy/Kuc+Dp6OJZy+xj8EK/0/ge0M 3oqQ== X-Forwarded-Encrypted: i=1; AJvYcCVP5rtLVGIvdoWW0KIeprnOBZhQfemLHzSitVC/WgU52fS1e99DOXTPW2dGr2WBd2GSZTXvh8k5ebYcU1M=@vger.kernel.org X-Gm-Message-State: AOJu0Yz3Vj8k7ZZnc8fiS70tCZmdMrKmZbkAaRCH1zN04Jbcrg+nUlxI vSL7NTjQ0TFM6IBQLsFd6kiypFONlOyI0lCQciggc1EhX/qJHiua7rnD X-Gm-Gg: AY/fxX73uNqftMwJp2EfBZi4V/lTezeeYOB37qGqtzTkUQbHmaEMysQ0+OMns0gemSr +/MTSjrRpJEpRTTKmqaH9t4BQbj7Cra+zcl6OwR03AHu9w9SU5jMoz59XUW0EKSJPafjpv+c19m 9wBbwwoXhZzOlOy/hHEjeDqFaWiL/DvQkC4J1wo3C0CSkNW2hti0sylQ1qXbqZGOQMwCqTL4ju0 uMyaaZJ1j0CihbGtF3KMD30hFRXp7OgE5iRCuTSXTzmJyfyS73VsklLLYzLhJZ5YE1UVNd218K5 DmAaJgE3Uf73WmkrPrVx1ZuzNbDpdF/IuqEn39C2P2KhTnFSOeOEWVYTn828CA/+wsz8PsPN+lj krYF8UZLaGv6REvplKzchGtoaokSerFevU+wGF808KX7sLD5c4S7M+NW9LVpX/y4VbNaUqLtuk6 rY1+ApMftsrItApxRCye22uUY= X-Received: by 2002:a05:693c:2c94:b0:2ae:50d5:bc0b with SMTP id 5a478bee46e88-2b6b4714677mr1764866eec.18.1768539530350; Thu, 15 Jan 2026 20:58:50 -0800 (PST) Received: from localhost.localdomain ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-2b6b361a7acsm1200479eec.21.2026.01.15.20.58.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Jan 2026 20:58:49 -0800 (PST) From: Qiliang Yuan To: Eduard Zingerman , Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko Cc: bpf@vger.kernel.org, linux-kernel@vger.kernel.org, john.fastabend@gmail.com, martin.lau@linux.dev, song@kernel.org, yonghong.song@linux.dev, kpsingh@kernel.org, sdf@fomichev.me, haoluo@google.com, jolsa@kernel.org, Qiliang Yuan Subject: [PATCH v2] bpf/verifier: optimize precision backtracking by skipping precise bits Date: Fri, 16 Jan 2026 12:58:39 +0800 Message-Id: <20260116045839.23743-1-realwujing@gmail.com> X-Mailer: git-send-email 2.39.5 In-Reply-To: References: 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" Currently, precision backtracking logic in __mark_chain_precision does not check if the target register or stack slot is already marked as precise. This can lead to redundant work when multiple paths require the same register to be precise. This patch moves the "skip if already precise" logic into the core backtracking loop setup in __mark_chain_precision(). This ensures that all entry points (mark_chain_precision, propagate_precision) benefit from the optimization and allows for cleaner code at the call sites. Specifically: - In __mark_chain_precision(), before starting the backtracking loop, check if the initial register/stack slot is already precise. - For batch propagation (used by propagate_precision), iterate through the requested masks and clear bits that are already precise in the starting state. - Remove redundant checks in mark_chain_precision() and propagate_precision(). Performance results: The optimization significantly reduces verification time by skipping redundant backtracking for registers already marked as precise. Key improvements (Duration): - prog_nested_calls: 671us -> 292us (-56.48%) - prog_non_constant_callback: 254us -> 111us (-56.30%) - stack_check: 807us -> 411us (-49.07%) - arena_strsearch: 120us -> 65us (-45.83%) - prog_null_ctx: 216us -> 164us (-24.07%) Verified that total instruction and state counts remain identical across all tests (0.00% change), confirming logic equivalence. Test steps and detailed performance raw data are as follows: The data was collected using the following command: $ sudo ./veristat -e duration,total_insns,total_states -o csv \ bpf_flow.bpf.o bpf_loop.bpf.o arena_strsearch.bpf.o Baseline (at b54345928fa1): file_name,prog_name,verdict,duration,total_insns,total_states arena_strsearch.bpf.o,arena_strsearch,failure,120,20,2 bpf_flow.bpf.o,_dissect,success,465,211,13 bpf_flow.bpf.o,flow_dissector_0,success,2408,1461,68 bpf_flow.bpf.o,flow_dissector_1,success,2698,1567,59 bpf_flow.bpf.o,flow_dissector_2,success,2010,1244,56 bpf_flow.bpf.o,flow_dissector_3,success,2250,1498,57 bpf_flow.bpf.o,flow_dissector_4,success,343,259,4 bpf_flow.bpf.o,flow_dissector_5,success,674,416,21 bpf_loop.bpf.o,prog_invalid_flags,success,292,50,5 bpf_loop.bpf.o,prog_nested_calls,success,671,145,19 bpf_loop.bpf.o,prog_non_constant_callback,success,254,41,5 bpf_loop.bpf.o,prog_null_ctx,success,216,22,3 bpf_loop.bpf.o,stack_check,success,807,325,25 bpf_loop.bpf.o,test_prog,success,493,64,7 Patched: file_name,prog_name,verdict,duration,total_insns,total_states arena_strsearch.bpf.o,arena_strsearch,failure,65,20,2 bpf_flow.bpf.o,_dissect,success,467,211,13 bpf_flow.bpf.o,flow_dissector_0,success,2392,1461,68 bpf_flow.bpf.o,flow_dissector_1,success,2722,1567,59 bpf_flow.bpf.o,flow_dissector_2,success,2050,1244,56 bpf_flow.bpf.o,flow_dissector_3,success,2258,1498,57 bpf_flow.bpf.o,flow_dissector_4,success,342,259,4 bpf_flow.bpf.o,flow_dissector_5,success,702,416,21 bpf_loop.bpf.o,prog_invalid_flags,success,239,50,5 bpf_loop.bpf.o,prog_nested_calls,success,292,145,19 bpf_loop.bpf.o,prog_non_constant_callback,success,111,41,5 bpf_loop.bpf.o,prog_null_ctx,success,164,22,3 bpf_loop.bpf.o,stack_check,success,411,325,25 bpf_loop.bpf.o,test_prog,success,484,64,7 Comparison (veristat -C): $ ./veristat -C prec_skip_baseline.csv prec_skip_patched.csv File Program Verdict (A) Verdict (B)= Verdict (DIFF) Duration (us) (A) Duration (us) (B) Duration (us) (DIFF= ) Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) Suggested-by: Eduard Zingerman --------------------- -------------------------- ----------- -----------= -------------- ----------------- ----------------- -------------------= - --------- --------- ------------ ---------- ---------- ------------- arena_strsearch.bpf.o arena_strsearch failure failure = MATCH 120 65 -55 (-45.83%= ) 20 20 +0 (+0.00%) 2 2 +0 (+0.00%) bpf_flow.bpf.o _dissect success success = MATCH 465 467 +2 (+0.43%= ) 211 211 +0 (+0.00%) 13 13 +0 (+0.00%) bpf_flow.bpf.o flow_dissector_0 success success = MATCH 2408 2392 -16 (-0.66%= ) 1461 1461 +0 (+0.00%) 68 68 +0 (+0.00%) bpf_flow.bpf.o flow_dissector_1 success success = MATCH 2698 2722 +24 (+0.89%= ) 1567 1567 +0 (+0.00%) 59 59 +0 (+0.00%) bpf_flow.bpf.o flow_dissector_2 success success = MATCH 2010 2050 +40 (+1.99%= ) 1244 1244 +0 (+0.00%) 56 56 +0 (+0.00%) bpf_flow.bpf.o flow_dissector_3 success success = MATCH 2250 2258 +8 (+0.36%= ) 1498 1498 +0 (+0.00%) 57 57 +0 (+0.00%) bpf_flow.bpf.o flow_dissector_4 success success = MATCH 343 342 -1 (-0.29%= ) 259 259 +0 (+0.00%) 4 4 +0 (+0.00%) bpf_flow.bpf.o flow_dissector_5 success success = MATCH 674 702 +28 (+4.15%= ) 416 416 +0 (+0.00%) 21 21 +0 (+0.00%) bpf_loop.bpf.o prog_invalid_flags success success = MATCH 292 239 -53 (-18.15%= ) 50 50 +0 (+0.00%) 5 5 +0 (+0.00%) bpf_loop.bpf.o prog_nested_calls success success = MATCH 671 292 -379 (-56.48%= ) 145 145 +0 (+0.00%) 19 19 +0 (+0.00%) bpf_loop.bpf.o prog_non_constant_callback success success = MATCH 254 111 -143 (-56.30%= ) 41 41 +0 (+0.00%) 5 5 +0 (+0.00%) bpf_loop.bpf.o prog_null_ctx success success = MATCH 216 164 -52 (-24.07%= ) 22 22 +0 (+0.00%) 3 3 +0 (+0.00%) bpf_loop.bpf.o stack_check success success = MATCH 807 411 -396 (-49.07%= ) 325 325 +0 (+0.00%) 25 25 +0 (+0.00%) bpf_loop.bpf.o test_prog success success = MATCH 493 484 -9 (-1.83%= ) 64 64 +0 (+0.00%) 7 7 +0 (+0.00%) Suggested-by: Eduard Zingerman Signed-off-by: Qiliang Yuan --- v1 -> v2: - Move "skip if already precise" logic into the core backtracking engine __mark_chain_precision() as suggested by Eduard Zingerman. - Add detailed performance benchmark results and veristat comparison. - Clean up call sites in mark_chain_precision() and propagate_precision(). kernel/bpf/verifier.c | 27 +++++++++++++++++++++++++-- 1 file changed, 25 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index f0ca69f888fa..340d972bd833 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -4765,14 +4765,37 @@ static int __mark_chain_precision(struct bpf_verifi= er_env *env, * slot, but don't set precise flag in current state, as precision * tracking in the current state is unnecessary. */ - func =3D st->frame[bt->frame]; if (regno >=3D 0) { - reg =3D &func->regs[regno]; + reg =3D &st->frame[bt->frame]->regs[regno]; if (reg->type !=3D SCALAR_VALUE) { verifier_bug(env, "backtracking misuse"); return -EFAULT; } + if (reg->precise) + return 0; bt_set_reg(bt, regno); + } else { + for (fr =3D bt->frame; fr >=3D 0; fr--) { + u32 reg_mask =3D bt_frame_reg_mask(bt, fr); + u64 stack_mask =3D bt_frame_stack_mask(bt, fr); + DECLARE_BITMAP(mask, 64); + + func =3D st->frame[fr]; + if (reg_mask) { + bitmap_from_u64(mask, reg_mask); + for_each_set_bit(i, mask, 32) { + if (func->regs[i].precise) + bt_clear_frame_reg(bt, fr, i); + } + } + if (stack_mask) { + bitmap_from_u64(mask, stack_mask); + for_each_set_bit(i, mask, 64) { + if (func->stack[i].spilled_ptr.precise) + bt_clear_frame_slot(bt, fr, i); + } + } + } } =20 if (bt_empty(bt)) --=20 2.39.5