From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) (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 5533127732 for ; Thu, 15 Jan 2026 20:36:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.181 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768509367; cv=none; b=iGUup+KEcsmoM9D3l+f73itTJv5LpFWEN4RTMJWbYkFEmwSyrnuDx85mdDZ/oDpqvR1wl0LNmt9SVLzCGXv9PLn40BDCX7fWNoGT5VjUabGjV47oDaK0oGatL8vaFGg5QH+OzxuU5BpNp116Te6RbKnLXiQwryw/4EC/YFOa+dM= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768509367; c=relaxed/simple; bh=/zHe1NiH+CB6jspvR3U0E3fH4F1iosvN974W6nhFcvo=; h=Message-ID:Subject:From:To:Cc:Date:In-Reply-To:References: Content-Type:MIME-Version; b=ugrvog5tOWMKozL8Ydh7MMfoHaUFSRZdFYcks3iPEJa9x/G2mTLjJ07YLkyMWMK4FBZx06qmWus8bIQP7nWDCqKjBMXHECIq2VUGNBuD8pEzTjTP9GD5ldSUg/zM4dV+NC6p0NOzH0H7NJla+pI8A6W6e4ER1LltMVBeypkslpw= 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=fIWnB0F+; arc=none smtp.client-ip=209.85.210.181 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="fIWnB0F+" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-81f5381d168so1221702b3a.2 for ; Thu, 15 Jan 2026 12:36:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1768509366; x=1769114166; 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=aJcRRhOt4b0PRJq+/EF853UWo45Ejl2CeOM5aKFXoE4=; b=fIWnB0F+g3kgJ8JSUyGw1qArAmFafvoomNMM+ypyJcpBEH1Bjy8en1vyjbcfxgG7hI /F1R1n4U+q8WBkvcnQx2sJiwcW8mfVSNPuJ5IpoRDnHBwo1FGRvcBCwHmsF/mFo1wawx a8AST93kZBrWBSKj+NrRoU78515v0Nu6iMSRi38xCGcwcykD6bQCSl6/mKtx7HkDgftT 6se4gafehGwP2FDecod7baCc8H/8zsW5tL9xo0bvq+8gb1glQpjX5+kRKjJ6wJ/nDu/y yq2pcODrYrWYFR4trQ9zeVGDdYC50fAHwl4qSgA5Jwv3W92OXAVjK7MF1sik44rxRNIG /XFg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768509366; x=1769114166; 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=aJcRRhOt4b0PRJq+/EF853UWo45Ejl2CeOM5aKFXoE4=; b=wIMmoH0JlNyltRaULqeE3N16/p70tl3NPCeGBVU7hsVDIvCpoHd/tu1jvRgnfMG2hv 6tCve3AolihlkJt5sOztDIxpEsdwTuuL43v7X63CLvRWLcm/uZpFlQK7Xig0x9qTwdfT K04y5mCMyNLfea8cH5p1LGrJged0ymiVTBVP9xNxdUxN5Eyk/vPyBfoUBGiB3E3pdLxq 0TAPn1xhbu+QYgU6N21JWtRyLhVZSunhoWZcHBPeC3QVQSivp1K3peBPbhoTYhX3Pkdd 5kj7q/8ZtxgTLfbRMiMbq68VdVUF1Eeddccm99R4b3iySdqKv5bgvwWq4jlIt/ZAuH58 ahPA== X-Forwarded-Encrypted: i=1; AJvYcCWdFL6IvTWlauU8FdX5mRzakOGAwy1WdputXK4mFhKRzhQA3LurWtJ1owt/GQDKcHWOV8ICShDNax5kmHI=@vger.kernel.org X-Gm-Message-State: AOJu0YxVLjaFJu420SjW9RWBILNPf+WhByxbR8wdqjPmJ61NxnD1z+Al 3e6VV+lWV6PueQGdj8iqS/Ur4vz6DWCs2qi9DaMmQrn64uP1xWIR3k7h X-Gm-Gg: AY/fxX7jcf5bElFD6n4c8KO79RUDxKI/jX7CZXqLO9lADh0W7y1g9IwWkptGIjjgYqg vBUUkM3zV6RANc/Rkx8G8ZB0J9dxf0KZFMLxDpNlXDWyXuyZFKB1l/9LKvCS6ET2KaEfeIr6lEZ yHChqbf+GZLKkYku5Wvzuwb6JHytNXyD8oDQ6RIz3c5SZhs9bWjNLj7u/UqMsYnomxQ9OzStjNl eZNhQNg5iL6fp+WIqsXnd+aKtL+S0vlniXVmL/EcQaPZugQwIPGp9YYv74Bq8wEKBX+UR5Dt4i3 cTxwD0t/HxAy8pBUt9uIybN90RrlJH3RzuQO8kYAvuLzdUifPqKWwcomY9rhO6RExtHJV8vprsM UOjCmo/lb6oElTurV6vJp2OkqQGFNT8XwI+BDSisZxHDfDfDnuyxBob4ZBlluJ40cqwDhVfVfN2 2h3W+Yn/aDBUXPps4qx1/jz/iOXzwYuC0TXpyJql32 X-Received: by 2002:a05:6a21:6da6:b0:361:1cef:c39b with SMTP id adf61e73a8af0-38dfe76e2ffmr893133637.45.1768509365581; Thu, 15 Jan 2026 12:36:05 -0800 (PST) Received: from [192.168.0.226] ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-c5edf24dd20sm272655a12.14.2026.01.15.12.36.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Jan 2026 12:36:05 -0800 (PST) Message-ID: Subject: Re: [PATCH] bpf/verifier: optimize ID mapping reset in states_equal 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 12:36:02 -0800 In-Reply-To: <20260115144946.439069-1-realwujing@gmail.com> References: <20260115144946.439069-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 22:49 +0800, wujing wrote: > 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 in every call. >=20 > The table size is exactly 4800 bytes (approx. 4.7KB), calculated as: > - MAX_BPF_REG =3D 11 > - MAX_BPF_STACK =3D 512 > - BPF_REG_SIZE =3D 8 > - MAX_CALL_FRAMES =3D 8 > - BPF_ID_MAP_SIZE =3D (11 + 512 / 8) * 8 =3D 600 entries > - Each entry (struct bpf_id_pair) is 8 bytes (two u32 fields) > - Total size =3D 600 * 8 =3D 4800 bytes >=20 > For complex programs with many pruning points, this constant large memset > introduces significant CPU overhead and cache pressure, especially when > only a few IDs are actually used. >=20 > This patch optimizes the reset logic by: > 1. Adding 'map_cnt' to bpf_idmap to track used slots. > 2. Updating 'map_cnt' in check_ids to record the high-water mark. > 3. Making reset_idmap_scratch perform a partial memset based on 'map_cnt'= . >=20 > This improves pruning performance and reduces redundant memory writes. >=20 > Signed-off-by: wujing ^^^^^^ Please use your full name. > Signed-off-by: Qiliang Yuan > --- I think this is an ok change. Could you please collect some stats using 'perf stat' for some big selftest= ? > include/linux/bpf_verifier.h | 1 + > kernel/bpf/verifier.c | 10 ++++++++-- > 2 files changed, 9 insertions(+), 2 deletions(-) >=20 > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h > index 130bcbd66f60..562f7e63be29 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 map_cnt; > struct bpf_id_pair map[BPF_ID_MAP_SIZE]; > }; > =20 > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 37ce3990c9ad..6220dde41107 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -18954,6 +18954,7 @@ static bool check_ids(u32 old_id, u32 cur_id, str= uct bpf_idmap *idmap) > /* 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; > } > if (map[i].old =3D=3D old_id) > @@ -19471,8 +19472,13 @@ static bool func_states_equal(struct bpf_verifie= r_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; > + if (idmap->map_cnt) { Nit: this condition is not really necessary. > + memset(idmap->map, 0, idmap->map_cnt * sizeof(struct bpf_id_pair)); > + idmap->map_cnt =3D 0; > + } > } > =20 > static bool states_equal(struct bpf_verifier_env *env,