From nobody Sat Feb 7 15:40:24 2026 Received: from mail-dl1-f43.google.com (mail-dl1-f43.google.com [74.125.82.43]) (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 1E033450F2 for ; Tue, 20 Jan 2026 01:56:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768874189; cv=none; b=Z1VLzQEUAUdcDs4ZfwgtIEn72/PSM5be88OltWrK6YTj/KjYyYbw2ZTMkfVPJPMdougte+i6LZAmtzE3t45UFLbSoctxTcPv1QrVemjXdYj0a+JjqDvGIfLRiWBnk13atW89ClsSw2HI+Xu0DL5SF0xWkBthGqBlha8LChPjlUM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768874189; c=relaxed/simple; bh=GLQecKHexuR0LR9N3OvtSmstyAexwGd77tPt8q7U3UQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ZHFr6PtAc5rHmOHfVQfmmWLS+QCWrY+0IAuXcpVzkBOpFSnHDPyA0c3DH4+Fu6ltKv08KvleppUBayoAKz0p9Harf3jzV6d2VSBb2AEPOHg53QEoPZRI7H1IkMXlNJn2P6VPdXj2+wZHMAd8+QsxXslqsSgOWG5D1QkfK/MDXNg= 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=BrNj5upo; arc=none smtp.client-ip=74.125.82.43 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="BrNj5upo" Received: by mail-dl1-f43.google.com with SMTP id a92af1059eb24-11f36012fb2so6941844c88.1 for ; Mon, 19 Jan 2026 17:56:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1768874187; x=1769478987; 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=DCCqZQlRXuTOCucNloGfjcUe3if2CIntAVLWdDySPgw=; b=BrNj5upob5iDbPZslaYkle2t2GBPyQOg0n2zaJINuqdjyldK/fi5lPRiooMtE++Yvp 1No9qhamRIkdFvue0VkgJBpeZHwjp6DB1mpbtpCbAlsNXiv7nW17uJfoa7MzwFXrgYi6 f/6+G8w5TiLjAs8CzNCwzOrcowsS793P8BEmTOhBQ2bE0YcFdeKMrI0smuntRuuwFTfB muvzb5Og/1H8e/lAp5zV4e45Zf/ZT7z8t1lY1UmH4eo733MfqrG1KbGks5YUUa8cbuyI uZaUm38b+EveHGuGVyfXBELdBpsE4ZtfY7xyHNWbollPxUkcOQIyV2gma56bc5qZt2Ws BztQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768874187; x=1769478987; 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=DCCqZQlRXuTOCucNloGfjcUe3if2CIntAVLWdDySPgw=; b=h0N+xcGBld7HCb+VT7o/kBYoFHShFCCPeb1RMfiVL8ratPQ4kvx3oOZzPk72ZUgKnD l6HascNvzwTiMGLNvQE6XEI2m4V8/tIJrhOBB2qK6d2bkAGHpXa9qiE36SlyWplErDul Ju8rzJBVXiBj6AoKvDpvpyzDrBRgWkq/SwuxnSuHjPe7RyZUjPJ8qLSGZ65+7leN9lKZ 0gZ8qHW8cPN5u6NrK9xssmf3Rsfh69kOsMUuZI7ojWuITUH0LtpOrN/jP2KwHyIm+SXm 4rygunSOUGGVhSaCgpHUgoT2lgGBnp6ihFIhypcP/5KRDbbdU2GB3B9vUkbLNt9RFF4z 55bA== X-Forwarded-Encrypted: i=1; AJvYcCUINeTSIPeSNFswyFrMEBRKB2Fm3TRjtywnCTjXRkEsMOwGxiEpG3J346fZrud/uhxHAWLeo4v/gbRuXss=@vger.kernel.org X-Gm-Message-State: AOJu0YyHq1nsoCgEWpmhuF8msfUN6bboziQ6Zl/d3T0182vcNMhxt4KT xsWQoid10waDzmE3Uyk7KuH+a1Ec/Rjkdc29jji82WodTLCqkV12cCO3 X-Gm-Gg: AY/fxX4wBv6rA2yYjx8gUvy15HQjs6ksOtht5ikOdUsCWYmibRrlmGjPMTMdZLB82UL WqoY73xBemO61fPS9K9+IHk1kH74MZ56xiq7HbVQAoTpvorsS2UcXPqetA8v87BuMyXqGtrcpBM waw7GDi7yBJVTmJnRs8s+Uj6Ms9y2UX9g9Rjz+tqyPYlK0tqmTO9Ms4xI9Sww5VogovFlYV1hhh gPY1pQBC1uPZD4l/o3wgQlHYEDQQrpRGO1AlnclJOs9rhz/H1dYBPBSwIUyAiDdUHv/tGJVd3gQ d1vM1c6eCr5Shc8vn0Ub6DHhM6rDvLjcZDwQSqbp4I3mYar42bhZoEuN2IJwV7XwJ1WsiuxC6Fk ZW7T5xkyxNvvMplGj8bWouAI8QUeD7BxtaEGmuSj/bkM+EJrNafFSCLmSpchMGM68L8daawJdhF dOnJalC8t7hQwLdfJl2yW7ldM= X-Received: by 2002:a05:7022:928:b0:119:e56b:91e6 with SMTP id a92af1059eb24-1244b35f47amr8360625c88.23.1768874187084; Mon, 19 Jan 2026 17:56:27 -0800 (PST) Received: from localhost.localdomain ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id a92af1059eb24-1244ad7201fsm18395141c88.7.2026.01.19.17.56.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 19 Jan 2026 17:56:26 -0800 (PST) From: Qiliang Yuan To: eddyz87@gmail.com Cc: andrii.nakryiko@gmail.com, andrii@kernel.org, ast@kernel.org, bpf@vger.kernel.org, daniel@iogearbox.net, haoluo@google.com, jolsa@kernel.org, kpsingh@kernel.org, linux-kernel@vger.kernel.org, martin.lau@linux.dev, realwujing@gmail.com, sdf@fomichev.me, song@kernel.org, yonghong.song@linux.dev, yuanql9@chinatelecom.cn Subject: [PATCH v3] bpf/verifier: optimize ID mapping reset in states_equal Date: Tue, 20 Jan 2026 09:56:16 +0800 Message-Id: <20260120015616.69224-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" The verifier uses an ID mapping table (struct bpf_idmap) during state equivalence checks. Currently, reset_idmap_scratch performs a full memset on the entire map (~4.7KB) in every call to states_equal. This ensures that reset overhead is minimal and the search loop is bounded by the number of IDs actually encountered in the current equivalence check. Benchmark results (system-wide 'perf stat' during high-concurrency 'verista= t' stress test, 60s): The following results, captured using perf while running veristat in parall= el across all CPU cores, show a significant reduction in instruction overhead (~9.3%) and branch executions (~11%), confirming that the O(1) reset logic significantly reduces the verifier's workload during state equivalence checks. Metric | Baseline | Patched | Delta Acked-by: Eduard Zingerman ----------------|---------------|---------------|---------- Iterations | 5710 | 5731 | +0.37% Instructions | 1.714 T | 1.555 T | -9.28% Inst/Iter | 300.2 M | 271.3 M | -9.63% Cycles | 1.436 T | 1.335 T | -7.03% Branches | 350.4 B | 311.9 B | -10.99% Migrations | 25,977 | 23,524 | -9.44% Test Command: seq 1 2000000 | sudo perf stat -a -- \ timeout 60s xargs -P $(nproc) -I {} ./veristat access_map_in_map.bpf.o Detailed Performance Stats: Baseline: Performance counter stats for 'system wide': 6,735,538 context-switches # 3505.5 cs/sec = cs_per_second 1,921,431.27 msec cpu-clock # 32.0 CPUs C= PUs_utilized 25,977 cpu-migrations # 13.5 migrati= ons/sec migrations_per_second 7,268,841 page-faults # 3783.0 faults/= sec page_fault_per_second 18,662,357,052 branch-misses # 3.9 % bran= ch_miss_rate (50.14%) 350,411,558,023 branches # 182.4 M/sec = branch_frequency (66.85%) 1,435,774,261,319 cpu-cycles # 0.7 GHz cy= cles_frequency (66.95%) 1,714,154,229,503 instructions # 1.2 instruc= tions insn_per_cycle (66.86%) 429,445,480,497 stalled-cycles-frontend # 0.30 fronten= d_cycles_idle (66.36%) 60.035899231 seconds time elapsed Patched: Performance counter stats for 'system wide': 6,662,371 context-switches # 3467.3 cs/sec = cs_per_second 1,921,497.78 msec cpu-clock # 32.0 CPUs C= PUs_utilized 23,524 cpu-migrations # 12.2 migrati= ons/sec migrations_per_second 7,783,064 page-faults # 4050.5 faults/= sec page_faults_per_second 18,181,655,163 branch-misses # 4.3 % bran= ch_miss_rate (50.15%) 311,865,239,743 branches # 162.3 M/sec = branch_frequency (66.86%) 1,334,859,779,821 cpu-cycles # 0.7 GHz cy= cles_frequency (66.96%) 1,555,086,465,845 instructions # 1.2 instruc= tions insn_per_cycle (66.87%) 407,666,712,045 stalled-cycles-frontend # 0.31 fronten= d_cycles_idle (66.35%) 60.034702643 seconds time elapsed Acked-by: Eduard Zingerman Signed-off-by: Qiliang Yuan --- v3: - Remove Suggested-by tags per Eduard's feedback. - Add Eduard's Acked-by. - Credit Andrii Nakryiko for the further optimization suggestion. - Mention the limitation of system-wide profiling in commit message. v2: - Further optimize ID mapping reset (suggested by Andrii Nakryiko) by using a simple counter reset and bounding the search loop. v1: - Initial version using a watermark-based partial memset to optimize the ID mapping reset overhead. include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 23 ++++++++++++++--------- 2 files changed, 15 insertions(+), 9 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 130bcbd66f60..8355b585cd18 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -692,6 +692,7 @@ struct bpf_id_pair { =20 struct bpf_idmap { u32 tmp_id_gen; + u32 cnt; struct bpf_id_pair map[BPF_ID_MAP_SIZE]; }; =20 diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 3135643d5695..6ec6d70e5ce7 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -18948,18 +18948,21 @@ static bool check_ids(u32 old_id, u32 cur_id, str= uct bpf_idmap *idmap) if (old_id =3D=3D 0) /* cur_id =3D=3D 0 as well */ return true; =20 - for (i =3D 0; i < BPF_ID_MAP_SIZE; i++) { - if (!map[i].old) { - /* Reached an empty slot; haven't seen this id before */ - map[i].old =3D old_id; - map[i].cur =3D cur_id; - return true; - } + for (i =3D 0; i < idmap->cnt; i++) { if (map[i].old =3D=3D old_id) return map[i].cur =3D=3D cur_id; if (map[i].cur =3D=3D cur_id) return false; } + + /* Reached the end of known mappings; haven't seen this id before */ + if (idmap->cnt < BPF_ID_MAP_SIZE) { + map[idmap->cnt].old =3D old_id; + map[idmap->cnt].cur =3D cur_id; + idmap->cnt++; + return true; + } + /* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE(1); return false; @@ -19470,8 +19473,10 @@ static bool func_states_equal(struct bpf_verifier_= env *env, struct bpf_func_stat =20 static void reset_idmap_scratch(struct bpf_verifier_env *env) { - env->idmap_scratch.tmp_id_gen =3D env->id_gen; - memset(&env->idmap_scratch.map, 0, sizeof(env->idmap_scratch.map)); + struct bpf_idmap *idmap =3D &env->idmap_scratch; + + idmap->tmp_id_gen =3D env->id_gen; + idmap->cnt =3D 0; } =20 static bool states_equal(struct bpf_verifier_env *env, --=20 2.39.5