From nobody Sun Feb 8 15:58:44 2026 Received: from mail-dl1-f49.google.com (mail-dl1-f49.google.com [74.125.82.49]) (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 D99FB3115A2 for ; Fri, 16 Jan 2026 09:08:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768554520; cv=none; b=dl9oTYscReO+NJV9nRnkt/6DrXrBCHCqKRyDSkalaLkuNvKOR/uDhRdsgBxmqZWe+rkAiTeSUg7yUCXeEDAYYXc5gOBjgL1ubFg1XBriGk0UZQkDyliT1lgYwah3vxPvqd8MWGER/h5KhA2/VGN48NFBbcXEldquu3y/YshD7T4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768554520; c=relaxed/simple; bh=o4lWNk+ZMPcaU9h9ZlO7K6J7v7mhjkHGlTUcDvdru94=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=O1x+5+bHCnyWRP47ewE/veeU+vqT6HfCGpW7GDPJJ2apIhlz1OoKT/IXleQJv4STXCuSENjCYtGWs746S69bluDbUXwas2p0IHmXz+RRRhUU2QqYtqpuB4+5F+hp6UaKWP8us1x6s2teZBQgmTIT5OflcePdcUk0yTsXUdO1eWw= 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=DZ8UnA+l; arc=none smtp.client-ip=74.125.82.49 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="DZ8UnA+l" Received: by mail-dl1-f49.google.com with SMTP id a92af1059eb24-12332910300so4455219c88.0 for ; Fri, 16 Jan 2026 01:08:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1768554516; x=1769159316; 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=fifXQLQN4gWGPVQytfiaXlhkJ+uL7Zz/OfkNW/kNrss=; b=DZ8UnA+lhBjg9k0HMGlxzDw4FGZmqJIeGC6SBkbVe9gL6prCzXkH4auAN8S3b5u7gg 5tQPfdNdScrgczkrJbngT4cqK/Kjijh2I8lQXTrS2SURz7H77dIKEeoUDlNYaQHHUW9S Djoq2s2qoza23aUT8e9cw2AHjbEX2MrndHWPvlyI7/tlOLCtxG/jk11GUq2EY7q6sCJ2 HkENi68WYLJojm/DOTBgPn6r1nSUeVZ/LoEKtwK6BgLr/lJ2kuy7DGZXIAkzIqza1dEj jINXRLUvnKY3PcB9vGlv/lvgSqmmFRM0K4SZ82AKGhqoiVlSicDL0qBXtooFCDLU2xiu p8EQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768554516; x=1769159316; 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=fifXQLQN4gWGPVQytfiaXlhkJ+uL7Zz/OfkNW/kNrss=; b=ub2IIn5iusv/+uKhvEJ2x7RVlAf462sKzDkqXB1XGViai4tMSUBRXYhFQmNqhimGkW RXJuBEhcGAytyRHnEBz4MhEihfV4lLGAA+8mh2Qewv593g//LmjyU/+MjZdpje6tjzot daPi3Znj8qe7BZNAExxVthSIk6ayxf6O0vtGAuGoxSUPnjjVMXJ524eYRXvltZ08sRuD FXj9LBua8YyNXfsDw00ZDlZ7pYIT2xTEspEAxcLt7EpWokAahz33WEZ/PylRq8hhBYv+ WMRLwMcSb6Xq+r7Fn1O06WfN3T3FYLDCr44Cs32CF23wrd28UDoPB8dRxI4nBYAJ7Oqt ibvw== X-Forwarded-Encrypted: i=1; AJvYcCVMFbs3nyzkHbdymfK7q1MR19Lw9nxcSAfLqzwMMVrrmCgfRcIhkcS9qwxSWcPVZ37bJUbuE1KGbSjGpqI=@vger.kernel.org X-Gm-Message-State: AOJu0YxVeS/gwvbHHSoX7Vuz/3zWTkPwEv1Ub7jtbLAnq0spLPyh/Usq vxS7rbPauD8gxzwPcVd+ybQ+mWe+CD4NMCibVucwDKWsfh6dyc3pwCih X-Gm-Gg: AY/fxX7kyNwKiEesS6HlVQ3UDl8AZEAjLyXAInnfA8r0BQ6qSp0F2Xo/G6JcrmBLz8Q bVCfrp0T94kAwsPwdPRlfBUPjTXoXw90Hru5kZrUnHWaUvtAEPRCYl9RXaj+USTNIjKyxZUbV94 WA3/PnulwknpTz2v3BwcPXefJ3etcQ6yJyhXdvrWcPgIDUs32QH9Vbb8DjypEMyW51B6dN5Pyw0 pK0WUZExPaUmv2DC3l2FclyIVTIccSErb4k8dtaoH07NYyvMBLJmeuBpg9NnD44TUKlzrtZ/3n8 x5vo6NidQG3t6rbYjjTk6K3JvPP53yyeETmK2efXIONobytjmsHb3nOsqjjcR5mQE2NLfYZgOFG weMQgN6RuJmHfjIpTL6IjgxlC12KeUcXOJJju06udc7s5ZPHXYHAbJFe9Moz7lgQKf9XCHo1tK9 x07JU1nUPF6j3CEMMnfyV9c6M= X-Received: by 2002:a05:7022:222:b0:11b:ade6:45bd with SMTP id a92af1059eb24-1244a6fa90amr2245378c88.8.1768554516053; Fri, 16 Jan 2026 01:08:36 -0800 (PST) Received: from localhost.localdomain ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id a92af1059eb24-1244aefab3fsm1479733c88.12.2026.01.16.01.08.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 16 Jan 2026 01:08:35 -0800 (PST) From: Qiliang Yuan To: andrii.nakryiko@gmail.com, eddyz87@gmail.com Cc: 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 v2] bpf/verifier: optimize ID mapping reset in states_equal Date: Fri, 16 Jan 2026 17:08:09 +0800 Message-Id: <20260116090809.25290-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. Following suggestions from Eduard Zingerman and Andrii Nakryiko, this patch optimizes the reset logic to avoid unnecessary memory operations: 1. Rename 'map_cnt' to 'cnt' for brevity. 2. Replace the O(N) memset() in reset_idmap_scratch() with a simple O(1) counter reset (idmap->cnt =3D 0). 3. Update check_ids() to search only up to 'idmap->cnt' entries. If no mapping is found, append the new mapping and increment 'cnt'. 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 Suggested-by: Andrii Nakryiko Suggested-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 Suggested-by: Eduard Zingerman Suggested-by: Andrii Nakryiko Signed-off-by: Qiliang Yuan --- Hi Eduard and Andrii, Thank you for the feedback on v1. I've optimized the ID mapping reset logic to O(1) and updated the benchmark results as suggested. v1 -> v2: - Rename map_cnt to cnt (Andrii Nakryiko) - Eliminate memset() by using cnt to bound search loop (Andrii Nakryiko) - Remove unnecessary if() check in reset_idmap_scratch() (Eduard Zingerman) - Use full name in Signed-off-by (Eduard Zingerman) include/linux/bpf_verifier.h | 2 +- kernel/bpf/verifier.c | 23 +++++++++++------------ 2 files changed, 12 insertions(+), 13 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 562f7e63be29..8355b585cd18 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -692,7 +692,7 @@ struct bpf_id_pair { =20 struct bpf_idmap { u32 tmp_id_gen; - u32 map_cnt; + 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 6220dde41107..c0e8604618de 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -18949,19 +18949,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; - idmap->map_cnt =3D i + 1; - 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; @@ -19475,10 +19477,7 @@ static void reset_idmap_scratch(struct bpf_verifie= r_env *env) struct bpf_idmap *idmap =3D &env->idmap_scratch; =20 idmap->tmp_id_gen =3D env->id_gen; - if (idmap->map_cnt) { - memset(idmap->map, 0, idmap->map_cnt * sizeof(struct bpf_id_pair)); - idmap->map_cnt =3D 0; - } + idmap->cnt =3D 0; } =20 static bool states_equal(struct bpf_verifier_env *env, --=20 2.39.5