From nobody Fri Dec 19 16:01:01 2025 Received: from mail-pj1-f51.google.com (mail-pj1-f51.google.com [209.85.216.51]) (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 56E8132F76F for ; Thu, 6 Nov 2025 13:20:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435223; cv=none; b=qgkvD06gWUqC3IYoj+Af7/vcYjqKmcCDpUQ1ectEpI6qKHlGu+deuVRmMNUrVFa/os7cvEawUaEg9nFTujdfhlzvuxNJr9yjgc80+tjpHUTqrTYDWNqFVcmKu0spHpwR/YsNErQ4Ydea0M8VMQI6Z1528IZlbI9IU91cqmzfKBQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435223; c=relaxed/simple; bh=/C7lP1Yq/5ogUMjkgaXSCCkh4BcomIYuobmhyRXlXAA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GL1eud0afkqCAGxtn4qeAZ+7OQ9wadQWmeMvpitt6qm8wCXewGSjblQoaBpLADhdrHhgpwptKm/PwuSqGPeW4ae767BbLzGaiQ33vyfN3nusBnm5mtdP/V5UoCtr+zqwyVR1YPe6K1iEU+1n3S5nS46cVHJBOi8Z66sr7r7QCbA= 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=G+Yy114T; arc=none smtp.client-ip=209.85.216.51 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="G+Yy114T" Received: by mail-pj1-f51.google.com with SMTP id 98e67ed59e1d1-340c39ee02dso996397a91.1 for ; Thu, 06 Nov 2025 05:20:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762435220; x=1763040020; 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=XmRxjb3TYj5YoPOI2P5uBjXYSAdjGF3zYPhjRb8AdXU=; b=G+Yy114T7D/+7G3pukGkxBhrifshlWR8Jbj0HHBo7W6BjvxNmaS6N1eyRCa4gb/wJe uwNAvIKccqQcXdzi3FxzTYlSaH9dsirxL2Cl/XK/uNHPZMmX0NaP6day0PEpjG7gAzWo 2hOgO1tKSm10O+eFJ8eOWtHgk6XJf035h5Pl0+BgbLJ0aJa5sn49AVvS8KSjhbs4HfJQ n4xSzZVX4T3mTCaWOSMHq2NCr48H5Irc3WXc0GmyhvJHgybXwWHv2opJNegxIfj2Xt9t wuBDTTscvwIJ4DQiR8h6na+Y4FNVUgfdZgepbt2sRt84oZN78tv1RevQikUPKk4G1O/D 17QQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762435220; x=1763040020; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=XmRxjb3TYj5YoPOI2P5uBjXYSAdjGF3zYPhjRb8AdXU=; b=i1wOUxHql44rGj5QXGBnc28hFa29C1XUowtv4jN4Zx+ot7DsJbMBHMvWlOZVQzAA5o abzMsaIc96jm0Y/42TZ88MLVT9TZ2I8dsO76d+30+N/Wq99aXSTwyV9yLlYscn/ea0jd DNLg22NUkg66udDXKffHLHFnjg0ymrEGVwDRs4ZBCE1BCX3iu4uXPoxPHE+1AU+KJ9Jg yn/Giq8L9M7M9DX8KhQQ4Re7i9RA9Jh2nYlh8cUwrpPqiUSYA+LuL7kPo5kCxYkMrGJy 31QdP5VdTboT2UCgtBTZ5oI4HbIAnlHR2KkDoXYmtVTESh9fL+0HaU0qC59s0QXn3yVo CJwQ== X-Forwarded-Encrypted: i=1; AJvYcCV4FB38WrX7NXERka9naghdWYkJiyEPow4tplKFw2x/quOxCDMw1wfRukLIMYISNyz/9N6douaEE9Uxx3M=@vger.kernel.org X-Gm-Message-State: AOJu0YwFfbl4KR3Q+Tnpm96azRx/vIdWb8JBtHtWDaoOlcEm+qTfZsY7 wniDCIIDrAmVXSSCaJVLw/wAQDfq5E6o7BspgmXTm2so9d/qGOf7XJm9 X-Gm-Gg: ASbGnctqL/u83+DE5766A7VNRBUi57tgGpHVHMTFqFVtuCKCakNKqN6scdZ6lfqwxIs 98pEhXwqvbQNNf0OK4CoRJ2jSOQysBJFPsI2vFThccSTe/5wemYwYhdQUlUOqV/k9RaV9UJcWbX AL1NeZUEA1ZOX1amQU94L6bV34lN4gufO5IlDk8n6bBHkz1eLaWlmqVPogtW6+RGrt/tqEWxdJD 0kP1W6VklJREb/VmzbVXWYLEfrxipRKS9+Shzqvb8ytWlDoGr5nY2XGbIL3/hji/lI4v2I806pS 1nEUwgWPxIxQ+rinNNVYr2NtrOX0pUGI19J357/WCwMmBO98JsyzIUzRSuia80hDvf7Hk1saaG7 msBvc5MGS7B7zXpW0kmkHE+6U5BAitiVuZo547DoskT5TbqcQk5OEBdK2AHLTH1CDPNWu8lPHYf ppHPR818+LwajM93Sk X-Google-Smtp-Source: AGHT+IGVdYS7PgIVP1pHCtuED1Z22PNW48lpWxrAamOrC3ebNLKDkO1COF/nQxHRmrAxURN7NQuBSQ== X-Received: by 2002:a17:90b:5250:b0:32e:38b0:15f4 with SMTP id 98e67ed59e1d1-341a6c00d22mr10400975a91.7.1762435220286; Thu, 06 Nov 2025 05:20:20 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-341d3e0b0b2sm1914869a91.21.2025.11.06.05.20.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 05:20:19 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu , Donglin Peng Subject: [PATCH v5 1/7] libbpf: Extract BTF type remapping logic into helper function Date: Thu, 6 Nov 2025 21:19:50 +0800 Message-Id: <20251106131956.1222864-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106131956.1222864-1-dolinux.peng@gmail.com> References: <20251106131956.1222864-1-dolinux.peng@gmail.com> 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" From: Donglin Peng Refactor btf_dedup_remap_types() by extracting its core logic into a new btf_remap_types() helper function. This eliminates code duplication and improves modularity while maintaining the same functionality. The new function encapsulates iteration over BTF types and BTF ext sections, accepting a callback for flexible type ID remapping. This makes the type remapping logic more maintainable and reusable. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng Signed-off-by: Donglin Peng Reviewed-by: Eduard Zingerman --- tools/lib/bpf/btf.c | 63 +++++++++++++++++++++++---------------------- 1 file changed, 32 insertions(+), 31 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 18907f0fcf9f..0c1dab8a199a 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext,= enum btf_endianness endian) return 0; } =20 +static int btf_remap_types(struct btf *btf, struct btf_ext *btf_ext, + type_id_visit_fn visit, void *ctx) +{ + int i, r; + + for (i =3D 0; i < btf->nr_types; i++) { + struct btf_type *t =3D btf_type_by_id(btf, btf->start_id + i); + struct btf_field_iter it; + __u32 *type_id; + + r =3D btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS); + if (r) + return r; + + while ((type_id =3D btf_field_iter_next(&it))) { + r =3D visit(type_id, ctx); + if (r) + return r; + } + } + + if (!btf_ext) + return 0; + + r =3D btf_ext_visit_type_ids(btf_ext, visit, ctx); + if (r) + return r; + + return 0; +} + struct btf_dedup; =20 static struct btf_dedup *btf_dedup_new(struct btf *btf, const struct btf_d= edup_opts *opts); @@ -5320,37 +5351,7 @@ static int btf_dedup_remap_type_id(__u32 *type_id, v= oid *ctx) */ static int btf_dedup_remap_types(struct btf_dedup *d) { - int i, r; - - for (i =3D 0; i < d->btf->nr_types; i++) { - struct btf_type *t =3D btf_type_by_id(d->btf, d->btf->start_id + i); - struct btf_field_iter it; - __u32 *type_id; - - r =3D btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS); - if (r) - return r; - - while ((type_id =3D btf_field_iter_next(&it))) { - __u32 resolved_id, new_id; - - resolved_id =3D resolve_type_id(d, *type_id); - new_id =3D d->hypot_map[resolved_id]; - if (new_id > BTF_MAX_NR_TYPES) - return -EINVAL; - - *type_id =3D new_id; - } - } - - if (!d->btf_ext) - return 0; - - r =3D btf_ext_visit_type_ids(d->btf_ext, btf_dedup_remap_type_id, d); - if (r) - return r; - - return 0; + return btf_remap_types(d->btf, d->btf_ext, btf_dedup_remap_type_id, d); } =20 /* --=20 2.34.1 From nobody Fri Dec 19 16:01:01 2025 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (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 D7ADE3314BC for ; Thu, 6 Nov 2025 13:20:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435228; cv=none; b=OeU2NdyRDggWRVe7+AC6lQC6DHhY5IPflPvXIPBM9MD/RyyQhNxf8KMnJ3pZC34BEpAK2/i7R+uEvAyyWoQ5co7VAsRU9e2Hr3knOvj8IZT6m78/YW3VHmC2sU6OoJV/Dd2CLTgNLAKVwil+j4qeW2xO/QJ1Xv2CPokLoIbARhI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435228; c=relaxed/simple; bh=5WMlMP0Qa86xjepvackGCM9Kudf88xqqA/oP2jNoOCQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Nl4bbia+VlWUtOnGiQWVNopUMlRq8IA2rFSE2S8BiKKKWAEGXtCyOZVnZUagdut9hvU3L6hmPp9LwtYH1/h4T+U5fl6KCk9ZCYTGFLXD+AmRsT8iq9ytgpXOdxTsJ+sYnSJ+S8HBLwovrxdNA9c2Zq0DLNF1h+aWxP0UPh70TF4= 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=aQjYe9Xr; arc=none smtp.client-ip=209.85.216.48 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="aQjYe9Xr" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-340bb1cb9ddso883446a91.2 for ; Thu, 06 Nov 2025 05:20:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762435224; x=1763040024; 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=eE4f1ExBgKlia9rPOG35Lwiq1YmfGukK360i7Hwinqw=; b=aQjYe9XrE+e8eNCSH/ilBMoiaZvJph4A6bFp+4ZXXtG/XGfXd0amdwEJQ8GlXP1TUG SodsMDPHx5a8dEX0TTiURx+Y26FjkGpO6gXEqvH5G/KlyhfUXl7NcAjyQLSPqEPiz9Y4 0VFyhTbix9sildE0McG/lVIfEcWHQL2EjUHPa4ef2T0RWh1vn7u3+MsN4JssMPMJNJnG fbKrg9WAzBnr2q3zraxY7dmhz9J+Hw5Moh1FU2fIFTYHTOaZ63brZR+WlcZ+0x7gjNHc m+2a8iIcfDfqsVsFM1rXB5PetEfNe8S8XrTkxsfLjdtFwXbUKQpH+x0DSJYjv8AlGzek I0cA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762435224; x=1763040024; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=eE4f1ExBgKlia9rPOG35Lwiq1YmfGukK360i7Hwinqw=; b=DmUqStTdN8P6BqqrkvluOKMkQvW7NqjTH2d4iV9lt4QJ//nq/W1RytK4slw9A/KloY 3sTO8VHwIYZVP2iayQNZUwyBg+QYfYnsjTAwbcpT9EbJQodmcwaTu8nD9fLEsWp3hpsW l0NoIxZ5hFzgA1xIhqCgrLWLv/QfNSKNw/YJN4XVSbAFyTZlrvdaEDu1o6rq/u5++gWo Z6ZK3tNPXldKo+5bA06Ovr+mi0rlUfBc2AQO1TR2O9w8YXij2EObkicMdeYkweYTr8vm mYqa0v96MJe2o/oVn6MU+0pTW+7rBUHuck03spnsPiJ6rHMnxx+FJWncvA85mmF6paoA L+eg== X-Forwarded-Encrypted: i=1; AJvYcCUad1WDBs8NLCwAEiZixixK27eezRcaP5yc21h/Cod2hYkLqzaTeE3LHhHVAp/WepQ5+4kKjOPCoZG4WEw=@vger.kernel.org X-Gm-Message-State: AOJu0YyPZ1vkkik4DolBEmcpekDAEIshG6Dny6fYCbAW4AzlajUjvoe/ 8yF/mSsa3mVM1Bnd7B3ZHMXLWlXYLYH+XQyLupzwIpr/mRF+qsuE56Hx X-Gm-Gg: ASbGncshxxIoCZClOjYhC3ZMT2heBbc9dou4VS1vl382Qmk4RuIy5+wKpnuKVTS4R4J GlVQfedp1X1anW+H1OOlloHtHA1vvx6l2AVl+5VWvvVJCksSQtxbh0mwKqOCxuZPWarGG7tnod9 y8ghapj/YB90zmDuIFIBWxzu3ZvWzASS2ow0uZtao38b3jtPzgjV2QxLr6NrgZ+sJEHY/Kbv3e7 w1bTnEHf3gCtWNuWKW2jZTNTn+doY5R9Ig20OVbLnavKAQa2OGMgQnFwaWuA0tFAe4pv++wXeqz AIAC5UtMVJKu+oLmVmLvHuxQ5zOCy8xL/Gmf7s/RmVDildMfNY8LTPbTcFNuAV3ClZGEs+/r4tW 9+1uMi9ouA8gUd4VZJqxDZfZ4oDJCswit4O0oDtTrPIr2DpqtN1hbdYGLoMJx7MAG2DGcmJJmyX Sn2BjkG9qcU9T868eP X-Google-Smtp-Source: AGHT+IHl0IBfcX7XHHEZM/JveOzysrq0UeZjBlkdDeFpHD0i/NWXnablAyZP2GJ7vtmKTkU9OsY4CA== X-Received: by 2002:a17:90b:2fcd:b0:338:3d07:5174 with SMTP id 98e67ed59e1d1-341a6c4189bmr8351963a91.5.1762435223917; Thu, 06 Nov 2025 05:20:23 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-341d3e0b0b2sm1914869a91.21.2025.11.06.05.20.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 05:20:22 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu , Donglin Peng Subject: [PATCH v5 2/7] libbpf: Add BTF permutation support for type reordering Date: Thu, 6 Nov 2025 21:19:51 +0800 Message-Id: <20251106131956.1222864-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106131956.1222864-1-dolinux.peng@gmail.com> References: <20251106131956.1222864-1-dolinux.peng@gmail.com> 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" From: Donglin Peng Introduce btf__permute() API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency. The permutation process involves: 1. Shuffling types into new order based on the provided IDs array 2. Remapping all type ID references to point to new locations 3. Handling BTF extension data if provided via options This is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng Signed-off-by: Donglin Peng Acked-by: Eduard Zingerman --- tools/lib/bpf/btf.c | 176 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 31 +++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 208 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 0c1dab8a199a..aad630822584 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -5830,3 +5830,179 @@ int btf__relocate(struct btf *btf, const struct btf= *base_btf) btf->owns_base =3D false; return libbpf_err(err); } + +struct btf_permute { + /* .BTF section to be permuted in-place */ + struct btf *btf; + /* optional .BTF.ext info along the main BTF info */ + struct btf_ext *btf_ext; + /* Array containing original type IDs (exclude VOID type ID 0) + * in user-defined order + */ + __u32 *ids; + /* Array used to map from original type ID to a new permuted type + * ID + */ + __u32 *ids_map; + /* Number of elements in ids array */ + __u32 ids_sz; +}; + +static int btf_permute_shuffle_types(struct btf_permute *p); +static int btf_permute_remap_types(struct btf_permute *p); +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx); + +int btf__permute(struct btf *btf, __u32 *ids, __u32 ids_sz, const struct b= tf_permute_opts *opts) +{ + struct btf_permute p; + int err =3D 0; + __u32 *ids_map =3D NULL; + + if (!OPTS_VALID(opts, btf_permute_opts) || (ids_sz > btf->nr_types)) + return libbpf_err(-EINVAL); + + ids_map =3D calloc(ids_sz, sizeof(*ids_map)); + if (!ids_map) { + err =3D -ENOMEM; + goto done; + } + + p.btf =3D btf; + p.btf_ext =3D OPTS_GET(opts, btf_ext, NULL); + p.ids =3D ids; + p.ids_map =3D ids_map; + p.ids_sz =3D ids_sz; + + if (btf_ensure_modifiable(btf)) { + err =3D -ENOMEM; + goto done; + } + err =3D btf_permute_shuffle_types(&p); + if (err < 0) { + goto done; + } + err =3D btf_permute_remap_types(&p); + if (err < 0) { + goto done; + } + +done: + free(ids_map); + return libbpf_err(err); +} + +/* Shuffle BTF types. + * + * Rearranges types according to the order specified in p->ids array. + * The p->ids_map array stores the mapping from original type IDs to + * new shuffled IDs, which is used in the next phase to update type + * references. + */ +static int btf_permute_shuffle_types(struct btf_permute *p) +{ + struct btf *btf =3D p->btf; + const struct btf_type *t; + __u32 *new_offs =3D NULL, *ids_map; + void *nt, *new_types =3D NULL; + int i, id, len, err; + + new_offs =3D calloc(p->ids_sz, sizeof(*new_offs)); + new_types =3D calloc(btf->hdr->type_len, 1); + if (!new_offs || !new_types) { + err =3D -ENOMEM; + goto out_err; + } + + nt =3D new_types; + for (i =3D 0; i < p->ids_sz; i++) { + id =3D p->ids[i]; + /* type IDs from base_btf and the VOID type are not allowed */ + if (id < btf->start_id) { + err =3D -EINVAL; + goto out_err; + } + /* must be a valid type ID */ + t =3D btf__type_by_id(btf, id); + if (!t) { + err =3D -EINVAL; + goto out_err; + } + ids_map =3D &p->ids_map[id - btf->start_id]; + /* duplicate type IDs are not allowed */ + if (*ids_map) { + err =3D -EINVAL; + goto out_err; + } + len =3D btf_type_size(t); + memcpy(nt, t, len); + new_offs[i] =3D nt - new_types; + *ids_map =3D btf->start_id + i; + nt +=3D len; + } + + /* resize */ + if (p->ids_sz < btf->nr_types) { + __u32 type_len =3D nt - new_types; + void *tmp_types; + + tmp_types =3D realloc(new_types, type_len); + if (!tmp_types) { + err =3D -ENOMEM; + goto out_err; + } + new_types =3D tmp_types; + btf->nr_types =3D p->ids_sz; + btf->type_offs_cap =3D p->ids_sz; + btf->types_data_cap =3D type_len; + btf->hdr->type_len =3D type_len; + btf->hdr->str_off =3D type_len; + btf->raw_size =3D btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str= _len; + } + free(btf->types_data); + free(btf->type_offs); + btf->types_data =3D new_types; + btf->type_offs =3D new_offs; + return 0; + +out_err: + free(new_offs); + free(new_types); + return err; +} + +/* Callback function to remap individual type ID references + * + * This callback is invoked by btf_remap_types() for each type ID reference + * found in the BTF data. It updates the reference to point to the new + * permuted type ID using ids_map array. + */ +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx) +{ + struct btf_permute *p =3D ctx; + __u32 new_type_id =3D *type_id; + + /* skip references that point into the base BTF */ + if (new_type_id < p->btf->start_id) + return 0; + + new_type_id =3D p->ids_map[*type_id - p->btf->start_id]; + if (new_type_id > BTF_MAX_NR_TYPES) + return -EINVAL; + + *type_id =3D new_type_id; + return 0; +} + +/* Remap referenced type IDs into permuted type IDs. + * + * After BTF types are permuted, their final type IDs may differ from orig= inal + * ones. The map from original to a corresponding permuted type ID is stor= ed + * in p->ids_map array and is populated during shuffle phase. During remap= ping + * phase we are rewriting all type IDs referenced from any BTF type (e.g., + * struct fields, func proto args, etc) to their final permuted type IDs. + */ +static int btf_permute_remap_types(struct btf_permute *p) +{ + return btf_remap_types(p->btf, p->btf_ext, btf_permute_remap_type_id, p); +} + diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index ccfd905f03df..a0bf9b011c94 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -273,6 +273,37 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struc= t btf_dedup_opts *opts); */ LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf); =20 +struct btf_permute_opts { + size_t sz; + /* optional .BTF.ext info along the main BTF info */ + struct btf_ext *btf_ext; + size_t :0; +}; +#define btf_permute_opts__last_field btf_ext + +/** + * @brief **btf__permute()** rearranges BTF types in-place according to sp= ecified mapping + * @param btf BTF object to permute + * @param ids Array containing original type IDs (exclude VOID type ID 0) = in user-defined order. + * @param ids_sz Number of elements in @ids array + * @param opts Optional parameters for BTF extension data reference updates + * @return 0 on success, negative error code on failure + * + * **btf__permute()** performs an in-place permutation of BTF types, rearr= anging them according + * to the order specified in @ids array. If @ids_sz is smaller than the to= tal number of types + * in @btf, the BTF will be truncated to contain only the types specified = in @ids. After + * reordering, all type references within the BTF data and optional BTF ex= tension are updated + * to maintain consistency. Subsequent btf__dedup may be required if the B= TF is truncated during + * permutation. + * + * On error, negative error code is returned and errno is set appropriatel= y. + * Common error codes include: + * - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate = IDs, out-of-range IDs) + * - -ENOMEM: Memory allocation failure during permutation process + */ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, __u32 ids_sz, + const struct btf_permute_opts *opts); + struct btf_dump; =20 struct btf_dump_opts { diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map index 8ed8749907d4..b778e5a5d0a8 100644 --- a/tools/lib/bpf/libbpf.map +++ b/tools/lib/bpf/libbpf.map @@ -451,4 +451,5 @@ LIBBPF_1.7.0 { global: bpf_map__set_exclusive_program; bpf_map__exclusive_program; + btf__permute; } LIBBPF_1.6.0; --=20 2.34.1 From nobody Fri Dec 19 16:01:01 2025 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (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 AF617330B34 for ; Thu, 6 Nov 2025 13:20:28 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435230; cv=none; b=RDlarblwVDen2QKRg9ply3PWLD4T/77XvVKnKLWRRyW/c6wB656yxFKUfISHjEPG15F1c2ZB7mPRQ3EF+kc1gsuqagxesBPFoot68ai8DsM/Ng3hFWKEJ7TXIKWECRLpbI41poDzWaN+MBSk4AOpeXIwzKPtVYvpbDJRXBlTFuk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435230; c=relaxed/simple; bh=h0EAfcD+G3X7Szy66vuob8E02hE5zbvK7+ntjyNEADw=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=j5K3uDtsktQ6EuMN8bSET4rDKyzE3ZUiX7uSDG5m6WcfQlGuGZ5oiZZs4d+VuMahZ2DlMTRV7gqRI98i081dDEfXAy4RhheLs++8VU3Vq4rPAAWgXWzBZtPr97TX0AKItsLZXFCJQa/IW4ZC2lyA4yZ871ZZxD7SZjVKFj9d5hQ= 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=DLYqaOfd; arc=none smtp.client-ip=209.85.216.48 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="DLYqaOfd" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-3418ac74bffso755095a91.1 for ; Thu, 06 Nov 2025 05:20:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762435228; x=1763040028; 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=2uTTJAlVf03fWlQTjN51jZc/1vK3RKFQ55CcWNpRfq0=; b=DLYqaOfdZGIj6yp4A2m7PNvAtkV0tB0MN03vF74YnVRTM8jNXYhnkgCUlC+p2NCsF8 AnM4jdjf2gJazEQQzm77Twz2rkQTV3OfiML5tUU0MJ6LFmJOZU8pXu/Z+RyKP9RaRaTn lkcUVAuA59xoxcBhuq3miBxP8WK3nkl79wAJIjr82UoYjusTy0K+BmJf+xRNUDmsUp95 bgzr4KfXRQ4/N4axnWkbtB+LgO4ZIdn8VkGzZSKVKtwv1pDieigZavszudf5ZmUcD/g8 20FIoymd8lCAakOdK8pV0opXWklbhihNr+fpPZxSE/mJru44GQ4Nj3SvjAWWer8lb3d7 X9Jg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762435228; x=1763040028; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=2uTTJAlVf03fWlQTjN51jZc/1vK3RKFQ55CcWNpRfq0=; b=NQLxe/2ktrxX4VcqY2gU29qGWPkOB3+ETSooR7sxnrt0EGV3zo+y0/dJXWYaSnLoAI zdt9eIlHGFyVOUDeieksXQTdHCtVIe1tmzGWDKIlgoRb2JNW7DrZNfObDRK+KGWeAybX mGhKN4tNk1XOpGn8fTSXa+10UV7rjMwIerZhw4BzG+YffHG9JfIfv07S/UfreVnEUlCa drx7dtHDVTcVQdpR66iWcP5tknGf7yGQ5AFCYiN//rSoH4il+fRf1pTuTTi5JED7vCDu TmqJQ0HOVnBrG+Pm2CCOUfVTuR3dT+6nQqs4rgcbbDdZiqurxr/KK//cBVKF1PQZhRTQ 1gmw== X-Forwarded-Encrypted: i=1; AJvYcCXZvzYsMT1XAHNl8Am7/d+YTmQt722J4nq9EvPiqXnPnOLmP4q44EBekhI/0Ju/z32IeVLA3YWFDXSHTZQ=@vger.kernel.org X-Gm-Message-State: AOJu0Yyqodq6ZKUg8lolWq0K/HYWGbg3muebyk8Dwa/6euzi3hS8a/ji ICW3h/iX9ItyY0ZClqrRZYUpiAAZ/Eg05P4YO4qn0PPSHjk3g7/hvMp8 X-Gm-Gg: ASbGncv6dF3WmrmxmeAmp/h/2r5X3xg24reQDo4w8FTJFOZ3+lQJGB4SW3x8KqR1973 QWGyKiJmWjEkWtwI0IqYICGCk3q+Rshh3wJZqwHvtdba6FQ8n8tRay4ebsDHaXC5FjLR9s+9T/K MtjkrKG16Hb+O8HitgJqwZODb8Di6Kl6jAiW+Yki4XaK/ZxYSOt2+0z835+uaBLzFWil3TcYMLq abLohPKNz6mCS66CnrjMA/ZHMCoUtb4x73p+RbVfAYbFFHOqE1/4iGAgd6Y2kt5O27CAd3Ye2kV grXxvy/wGqBSRZDUf8fga1x1F73Tp+aqcb1uszwQbw5p7zIUvZOSkw+XxXv21OjvwKIwCQzoFYX sbnrncSxZEAaa+pMNVt9+YlyMjBs8rxg9lfOz2zl81GOH0HQpstdHzm/ujWbuomNUAQNo7xIypr Mwd3KfPbER1yqTb0gg X-Google-Smtp-Source: AGHT+IHo+v0TtA1LN3JuLTKCRweiuU1NOoFv6iTGjRKxpQ9ZmN93DDux9gXzM/pFEUH3U2AvrZ42mg== X-Received: by 2002:a17:90b:4acf:b0:32e:3552:8c79 with SMTP id 98e67ed59e1d1-341a6defc72mr8457709a91.29.1762435227616; Thu, 06 Nov 2025 05:20:27 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-341d3e0b0b2sm1914869a91.21.2025.11.06.05.20.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 05:20:26 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu , Donglin Peng Subject: [PATCH v5 3/7] libbpf: Optimize type lookup with binary search for sorted BTF Date: Thu, 6 Nov 2025 21:19:52 +0800 Message-Id: <20251106131956.1222864-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106131956.1222864-1-dolinux.peng@gmail.com> References: <20251106131956.1222864-1-dolinux.peng@gmail.com> 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" From: Donglin Peng This patch introduces binary search optimization for BTF type lookups when the BTF instance contains sorted types. The optimization significantly improves performance when searching for types in large BTF instances with sorted type names. For unsorted BTF or when nr_sorted_types is zero, the implementation falls back to the original linear search algorithm. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 145 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 122 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index aad630822584..be092892c4ae 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -26,6 +26,10 @@ =20 #define BTF_MAX_NR_TYPES 0x7fffffffU #define BTF_MAX_STR_OFFSET 0x7fffffffU +/* + * sort verification occurs lazily upon first btf_find_type_by_name_kind()= call + */ +#define BTF_NEED_SORT_CHECK ((__u32)-1) =20 static struct btf_type btf_void; =20 @@ -92,6 +96,16 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of sorted and named types in this BTF instance: + * - doesn't include special [0] void type; + * - for split BTF counts number of sorted and named types added on + * top of base BTF. + * - BTF_NEED_SORT_CHECK value indicates sort validation will be perfor= med + * on first call to btf_find_type_by_name_kind. + * - zero value indicates applied sorting check with unsorted BTF or no + * named types. + */ + __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,44 +911,126 @@ int btf__resolve_type(const struct btf *btf, __u32 t= ype_id) return type_id; } =20 -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* Performs binary search within specified type ID range to find the leftm= ost + * BTF type matching the given name. The search assumes types are sorted by + * name in lexicographical order within the specified range. + * + * Return: Type ID of leftmost matching type, or -ENOENT if not found + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, + __s32 start_id, __s32 end_id) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + __s32 l, r, m, lmost =3D -ENOENT; + int ret; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf__str_by_offset(btf, t->name_off); + ret =3D strcmp(tname, name); + if (ret < 0) { + l =3D m + 1; + } else { + if (ret =3D=3D 0) + lmost =3D m; + r =3D m - 1; + } + } =20 - if (!strcmp(type_name, "void")) - return 0; + return lmost; +} =20 - for (i =3D 1; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name =3D btf__name_by_offset(btf, t->name_off); +/* Searches for a BTF type by name and optionally by kind. The function fi= rst + * checks if the search should start from the base BTF (if @start_id is be= fore + * current BTF's start_id). If types are sorted, it uses binary search to = find + * the leftmost matching type and then verifies the kind. For unsorted typ= es, + * it falls back to linear search through all types. + * + * The function handles split BTF scenarios by recursively searching in ba= se + * BTFs when necessary. When @kind is -1, only the name matching is perfor= med. + * + * Return: Type ID of matching type on success, -ENOENT if not found + */ +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_i= d, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + int err =3D -ENOENT; + + if (start_id < btf->start_id) { + err =3D btf_find_type_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (err > 0) + goto out; + start_id =3D btf->start_id; + } + + if (btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK) { + /* binary search */ + __s32 end_id; + bool skip_first; + int ret; + + end_id =3D btf->start_id + btf->nr_sorted_types - 1; + ret =3D btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id); + if (ret < 0) + goto out; + if (kind =3D=3D -1) + return ret; + skip_first =3D true; + do { + t =3D btf_type_by_id(btf, ret); + if (BTF_INFO_KIND(t->info) !=3D kind) { + if (skip_first) { + skip_first =3D false; + continue; + } + } else if (skip_first) { + return ret; + } + tname =3D btf__str_by_offset(btf, t->name_off); + if (!strcmp(tname, type_name)) + return ret; + else + break; + } while (++ret <=3D end_id); + } else { + /* linear search */ + __u32 i, total; =20 - if (name && !strcmp(type_name, name)) - return i; + total =3D btf__type_cnt(btf); + for (i =3D start_id; i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (kind !=3D -1 && btf_kind(t) !=3D kind) + continue; + tname =3D btf__str_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } } =20 - return libbpf_err(-ENOENT); +out: + return err; } =20 static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind) { - __u32 i, nr_types =3D btf__type_cnt(btf); - if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) return 0; =20 - for (i =3D start_id; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name; - - if (btf_kind(t) !=3D kind) - continue; - name =3D btf__name_by_offset(btf, t->name_off); - if (name && !strcmp(type_name, name)) - return i; - } + return libbpf_err(btf_find_type_by_name_kind(btf, start_id, type_name, ki= nd)); +} =20 - return libbpf_err(-ENOENT); +/* the kind value of -1 indicates that kind matching should be skipped */ +__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +{ + return btf_find_by_name_kind(btf, btf->start_id, type_name, -1); } =20 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, @@ -1006,6 +1102,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) btf->fd =3D -1; btf->ptr_sz =3D sizeof(void *); btf->swapped_endian =3D false; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1057,6 +1154,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b btf->start_id =3D 1; btf->start_str_off =3D 0; btf->fd =3D -1; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1715,6 +1813,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped =3D NULL; } + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; } =20 /* Ensure BTF is ready to be modified (by splitting into a three memory --=20 2.34.1 From nobody Fri Dec 19 16:01:01 2025 Received: from mail-pg1-f173.google.com (mail-pg1-f173.google.com [209.85.215.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 4C6FF3321CE for ; Thu, 6 Nov 2025 13:20:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435234; cv=none; b=eETaub6zzEe/pGoRU1X0wYrXWJfJF7FwCUNKfv+cIIRt9vgr0WBYZTwynSua8g8J8yRrXqeyRrEuHS7vDiWT6A0QzDZU8nu4iT81x0sBg/hFyuOsJplSPoCXH/leUGLtWGd4pX+Xk1orRkEQXss/PHUMM2aMU44Zxm+r/3Mm+9Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435234; c=relaxed/simple; bh=9IIrVWj4EOAFacobzgV9OdSZQ7IU230SlMHy8PsLO8k=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=MCtkIZtu6U2ZajtHFHETPAmFMKziFbt7+gLAhmpw/uaCCwa+QmrjovzeJB1NZ7Bu3YLdGcx1SCCBcx3NwBFRu0pCaJbZ4J3znKCor0tTOgYIQor+b3kGs5u62fONnuYIuvDPIPyX3PL6QH4RdvVZky4fVB/s/QpQvAhme34kWCk= 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=RTjErpzD; arc=none smtp.client-ip=209.85.215.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="RTjErpzD" Received: by mail-pg1-f173.google.com with SMTP id 41be03b00d2f7-ba599137cf7so859132a12.0 for ; Thu, 06 Nov 2025 05:20:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762435231; x=1763040031; 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=YpLkwEVaZQ31ymQfuOb0WcKoTYd7LV9JMIguVBgQh3c=; b=RTjErpzDzneMzIhtVkTSCyy5q1v6TCxqD1w1JHSQZfDN55zUTjrsXOBGQ/XeRLSDNd yL3AU8Dc+xDs1Q83JJVwvuVwg4K0KvgyDt9rqAo2OrTffYeDx9L1P4ttYR8YwEiiO2K7 mH0icQSrgQqPp8KL+l35eZpGgTdMeccfMq3Ld/LTiWPljo4p43fz4lPLdnuKgHa20E3U 5sNSJHFOhwN6tyVKLZXo4bw0jS7Ho4AszmJQk27mzrvnynsATRzcS5Rb8h80ek2Xjh5w LF0P1RRIvjJIh9/9AniXHIPxT4DxI01ImSXkBN2SGD2Bi9omH/GRwISgXLBGyaqVrG02 CmeA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762435231; x=1763040031; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=YpLkwEVaZQ31ymQfuOb0WcKoTYd7LV9JMIguVBgQh3c=; b=RXBW/h8HIT+feo3e09G2Y+rQHi5KqdrmamW7ZXmTTf570h5liVCfZx7Gnqb5FqHezs lizTVGOoyJD+ETgcw9U5nuwRlXrGq12Ms1XD06PeceKR29KP5jqJXrR7HRMfpRmsvKvC bS7mgAg/kxbhTCK8T+hIovlPpzvsnVbrzzp/LHS36RFF+qAmllP2qY/ZKLYhDR+a9ZrE FVsvOHJ4UvmJ2PwCNzDQ6Xs6A+k1/L51Mz+n69dyM8JHnPM6M461CCmP2coCUgck7xZH e8nGr1ypvQkxOs5ihVYih511QhY9/O6YK0KR8afGgQ8LNy/v0Pv3hbgTIYhUrgIgx6rx oqYQ== X-Forwarded-Encrypted: i=1; AJvYcCV0llX0nIeh/sVsfXTeGEKxzmryuPCdD6Qq84wpaJlaB1SZMnGhIOKBOqf0DPvL3Au6NFddsud/72Ouo1U=@vger.kernel.org X-Gm-Message-State: AOJu0Yyv+1ZPu7qZBJNEbPTBG5bTi4hDC9uqFhdfRJJdlyh4vdFR4M4Q FPXlsLpDjlY8nxznFIShA1HTUe/qZaQH+2FT+mgJHwgqxKp2I7ywmp6y X-Gm-Gg: ASbGncvryZjcLC2EL6W1FnVl6jZeEuoHJtqU3bnAPU0khIt1IfwZFF6bT0+xv+5AU3/ qI4EuJ4GlKrRvbiP4YQRWFTNz2wDV5D5/fK3+34f6Fx8kBtPcVhWQJAv174ymXC330UWWl39E79 Ws4fHwaM6GopVtYKcxImt9t3uSpXeiBihor7NF+58k1DywqNi4y+z1+RYweUVxMd85k6iHFA/kP 0sQV9HmyK5z8onL21nI/lwyJHe3Ms6eGmMarA6oKe9Y7HOULRD1+GO/nMFoHgk318fMOlR8DkAp ju/zgYs2OEp5LwlSUNfAiBbHUfhC2c6abHPISFRbOWnKfqhXUGSoGJ8GuhKIrYDEvjXjcCCj4Xt pchjaJU+K5bmyE3KJlm5/et81tRxRc4C3w2MYC1ur/7JDlU0KWJOZN1L+BVXB1wLI3crDZqTe5I 4qni3NG+V8GXsS+kPu X-Google-Smtp-Source: AGHT+IH8xXHumIVLMZrCxwSH55ZPpWyKAGLDtEe4kXor9petOsUVlk2TDe4v5DrC1SE3U/hEmx1AMw== X-Received: by 2002:a17:90b:3812:b0:341:8ae5:fde5 with SMTP id 98e67ed59e1d1-341a6dc4bdemr8230717a91.18.1762435231258; Thu, 06 Nov 2025 05:20:31 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-341d3e0b0b2sm1914869a91.21.2025.11.06.05.20.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 05:20:30 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu , Donglin Peng Subject: [PATCH v5 4/7] libbpf: Implement lazy sorting validation for binary search optimization Date: Thu, 6 Nov 2025 21:19:53 +0800 Message-Id: <20251106131956.1222864-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106131956.1222864-1-dolinux.peng@gmail.com> References: <20251106131956.1222864-1-dolinux.peng@gmail.com> 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" From: Donglin Peng This patch adds lazy validation of BTF type ordering to determine if types are sorted by name. The check is performed on first access and cached, enabling efficient binary search for sorted BTF while maintaining linear search fallback for unsorted cases. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 69 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 68 insertions(+), 1 deletion(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index be092892c4ae..56e555c43712 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -911,6 +911,73 @@ int btf__resolve_type(const struct btf *btf, __u32 typ= e_id) return type_id; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + bool anon_a, anon_b; + + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + anon_a =3D str_is_empty(na); + anon_b =3D str_is_empty(nb); + + if (anon_a && !anon_b) + return 1; + if (!anon_a && anon_b) + return -1; + if (anon_a && anon_b) + return 0; + + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the orderi= ng + * is correct, counts the number of named types and updates the BTF object= 's + * nr_sorted_types field. + * + * Return: true if types are properly sorted, false otherwise + */ +static bool btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, k =3D 0, n, nr_sorted_types; + + if (likely(btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK)) + goto out; + btf->nr_sorted_types =3D 0; + + if (btf->nr_types < 2) + goto out; + + nr_sorted_types =3D 0; + n =3D btf__type_cnt(btf) - 1; + for (i =3D btf->start_id; i < n; i++) { + k =3D i + 1; + if (btf_compare_type_names(&i, &k, btf) > 0) + goto out; + t =3D btf_type_by_id(btf, i); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + } + + t =3D btf_type_by_id(btf, k); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; + +out: + return btf->nr_sorted_types > 0; +} + /* Performs binary search within specified type ID range to find the leftm= ost * BTF type matching the given name. The search assumes types are sorted by * name in lexicographical order within the specified range. @@ -970,7 +1037,7 @@ static __s32 btf_find_type_by_name_kind(const struct b= tf *btf, int start_id, start_id =3D btf->start_id; } =20 - if (btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK) { + if (btf_check_sorted((struct btf *)btf)) { /* binary search */ __s32 end_id; bool skip_first; --=20 2.34.1 From nobody Fri Dec 19 16:01:01 2025 Received: from mail-pj1-f42.google.com (mail-pj1-f42.google.com [209.85.216.42]) (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 770113328FB for ; Thu, 6 Nov 2025 13:20:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435237; cv=none; b=Z9S4SmHd8TC03ABaCmyOB31h/SKRP5+5sgGH4xMU3OslIbFRa9D2uWZZoa/uofJwYHMp33+btHidB4UDORh8NVxlg3W3CryUl61q/f7PBqiHimAQLHBwlFiynu80XoYK9Z3sIQc288BwZFnRAJEcuqlLO4MkZHxbQGEntJhRHOs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435237; c=relaxed/simple; bh=F5X5Y5A4ts8MLXZLKzfKP+tr0DZu+o/90/KYpaX5Qb0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=OAJNOQ0JDbaYqMtTKZkJ6+JwpBr10Lwkg+3YYrajOrphCJwcKej4Bl7mqqVXKkfyE4awyQ0lcGCM7P7WMpgFE/sYZeb/7UvK1yXKAQGyg/FT5yHDAAEeqPL2VMxEqbYe1vOeYadMuPoxw/xIb63FdflUf4hkIj6GOkI3FzDUkG8= 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=GyQscZaf; arc=none smtp.client-ip=209.85.216.42 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="GyQscZaf" Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-340c39ee02dso996835a91.1 for ; Thu, 06 Nov 2025 05:20:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762435235; x=1763040035; 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=3oe9IB7XRuftK/ORLSLXvtfYwT74Xn4ffToyKR5CyQA=; b=GyQscZaf8nREVM6RKPr779zcbhPzppTWxVAttqaAS1kdmiugEXA3yHDHadnl6n/SuU XLGLOjHGAMcUKSzHMVkScwc7CmAo+vPZDK4/DJYNekd4MMbH+pWGl/GKs9YxXzPSPpnS V1k16MxcePyUe5clRTArIJUiIbg0mow7Yo/6AI+PQl7tVYuWZLyka44KMLdQD02zyyNm p/+5Vx8B/spM98NSwALTreTLaUAdZCTfrvoxkUCWj7Hj8tsFcsUozHtVR5PRe635I6xy 7iX8oyalFwbb0+Wrv5k8O+yKtQHf9UVua3kem3IQ2Rf1VqajAyuSqTBrt2TRB+gfFpdC eg3g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762435235; x=1763040035; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=3oe9IB7XRuftK/ORLSLXvtfYwT74Xn4ffToyKR5CyQA=; b=jln+Ev+QFjYw82wc7aFNP6J3bb4nUtHf0fed4ela/fEZe9pHWbVzP473mdUBDOl44Y 7gUL7oa5GTn++0PaXIq0l81vK1cNW3xcFHJaQz9bt9ekMlpKgSyv0T7QJdVIvqREU9g4 1v+MG8FCvyPPmD2SnzFkxPKw8SseaLXV4fJrX+7+phvUj7sCl+1GZyug1EucJ4UjeZXP qnqpCUqzlozZk5KRgvMB+6Mbc07duz8TnODEuCiS3NPuTm12vGEeFIQUkHz5i1Q3JRoD NpVBs8LPIHFMlbxgEFjbd2zBZhAQefBLVYtPuZ90bEkJseHESkszOuMOT2Pj+5CjJf60 xeiQ== X-Forwarded-Encrypted: i=1; AJvYcCWZHbNSb8hd3ZBEt418dI8qTtNK1bZVBawp8VDLOA+yasMZnUYpWSHcRYaKxH8PwN5s5Km8Vek5fChr/VY=@vger.kernel.org X-Gm-Message-State: AOJu0YyFOLEHxbImTRQtdpNPDj6D9WwLI58tXXPQOvGuuDgJEI/pwPK5 Puo37tloYV3jihJcH22qph+nxtyn9kREcnaWrMQO4WVowxnEQaENuQaa X-Gm-Gg: ASbGncvertzPMXopdJI+ymIcZnx2bfRPIlnlkyvwLE2tKJeqN58ZHkEzd/PrylVr2Gx 0xgdQtAX1abQFYyWgnc7q9TeTTQiFC3q7shCZ7UegxE7mnwR8VaASKka79eO1Qx6evYuuqhklXB Ib19lYwvHZ1OfEeLiQqDZxvyqFDSPkti1gEh1jLcKWYw0qCy8yGoQsHCKGkMdAP2okhaa7vltmk gAniN7zkYCY4F3U1VE1hEy/BbW5IjE9HeahTCnL9yIJsBwXcXn+qoUPFv90N7CxFj4+CZnB4K/l PSTdHiF1oRKvtJgkyUPBDp5F8sJK+Gpyh5ipAYVUl7XuOlqGCCGcs1vF/GPgrisBojggvcml8Lm ouQTKbW7yq6LomavRM2YmXv9Dx/4v44YagO2YOWP3LW0vqLLjl//kE1yPGBaiWLfm9UBEsIKfKv PEX/FmL+0rZ+V+N0UZ X-Google-Smtp-Source: AGHT+IHdCvg4WM6MDWt7CjISOISNrqfsnmPepoxmBDS9wWIOhAC432xRASHA8HBRdlSBjrUGDiQajg== X-Received: by 2002:a17:90a:1508:b0:340:d578:f299 with SMTP id 98e67ed59e1d1-341a6c00d45mr5789547a91.3.1762435234764; Thu, 06 Nov 2025 05:20:34 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-341d3e0b0b2sm1914869a91.21.2025.11.06.05.20.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 05:20:33 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu , Donglin Peng Subject: [PATCH v5 5/7] btf: Optimize type lookup with binary search Date: Thu, 6 Nov 2025 21:19:54 +0800 Message-Id: <20251106131956.1222864-6-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106131956.1222864-1-dolinux.peng@gmail.com> References: <20251106131956.1222864-1-dolinux.peng@gmail.com> 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" From: Donglin Peng Improve btf_find_by_name_kind() performance by adding binary search support for sorted types. Falls back to linear search for compatibility. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 117 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 107 insertions(+), 10 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..66cb739a0598 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -192,6 +192,8 @@ */ #define BTF_MAX_SIZE (16 * 1024 * 1024) =20 +#define BTF_NEED_SORT_CHECK ((u32)-1) + #define for_each_member_from(i, from, struct_type, member) \ for (i =3D from, member =3D btf_type_member(struct_type) + from; \ i < btf_type_vlen(struct_type); \ @@ -259,6 +261,7 @@ struct btf { void *nohdr_data; struct btf_header hdr; u32 nr_types; /* includes VOID for base BTF */ + u32 nr_sorted_types; /* exclude VOID for base BTF */ u32 types_size; u32 data_size; refcount_t refcnt; @@ -494,6 +497,11 @@ static bool btf_type_is_modifier(const struct btf_type= *t) return false; } =20 +static int btf_start_id(const struct btf *btf) +{ + return btf->start_id + (btf->base_btf ? 0 : 1); +} + bool btf_type_is_void(const struct btf_type *t) { return t =3D=3D &btf_void; @@ -544,24 +552,110 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +/* Performs binary search within specified type ID range to find the leftm= ost + * BTF type matching the given name. The search assumes types are sorted by + * name in lexicographical order within the specified range. + * + * Return: Type ID of leftmost matching type, or -ENOENT if not found + */ +static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name, + s32 start_id, s32 end_id) +{ + const struct btf_type *t; + const char *tname; + s32 l, r, m, lmost =3D -ENOENT; + int ret; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf_name_by_offset(btf, t->name_off); + ret =3D strcmp(tname, name); + if (ret < 0) { + l =3D m + 1; + } else { + if (ret =3D=3D 0) + lmost =3D m; + r =3D m - 1; + } + } + + return lmost; +} + +/* Searches for a BTF type with the specified name and kind. The function + * first recursively searches in the base BTF (if present), then searches + * in the current BTF using either binary search (if types are sorted) + * or linear search. + * + * Binary search is used when types are name-sorted (nr_sorted_types > 0). + * After finding a name match, it scans forward to find the first type + * that also matches the specified kind. Linear search is used for unsorted + * types, checking each type sequentially. + * + * Return: Type ID of matching type on success, -ENOENT if not found + */ s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) { + const struct btf *base_btf =3D btf_base_btf(btf);; const struct btf_type *t; const char *tname; - u32 i, total; + int err =3D -ENOENT; =20 - total =3D btf_nr_types(btf); - for (i =3D 1; i < total; i++) { - t =3D btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) !=3D kind) - continue; + if (base_btf) { + err =3D btf_find_by_name_kind(base_btf, name, kind); + if (err > 0) + goto out; + } =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK) { + /* binary search */ + bool skip_first; + s32 start_id, end_id;; + int ret; + + start_id =3D btf_start_id(btf); + end_id =3D start_id + btf->nr_sorted_types - 1; + ret =3D btf_find_by_name_kind_bsearch(btf, name, start_id, end_id); + if (ret < 0) + goto out; + skip_first =3D true; + do { + t =3D btf_type_by_id(btf, ret); + if (BTF_INFO_KIND(t->info) !=3D kind) { + if (skip_first) { + skip_first =3D false; + continue; + } + } else if (skip_first) { + return ret; + } + tname =3D btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return ret; + else + break; + } while (++ret <=3D end_id); + } else { + /* linear search */ + u32 i, total; + + total =3D btf_nr_types(btf); + for (i =3D btf_start_id(btf); i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (BTF_INFO_KIND(t->info) !=3D kind) + continue; + + tname =3D btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return i; + } } =20 - return -ENOENT; +out: + return err; } =20 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) @@ -5791,6 +5885,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6210,6 +6305,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name btf->data =3D data; btf->data_size =3D data_size; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6327,6 +6423,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, btf->start_id =3D base_btf->nr_types; btf->start_str_off =3D base_btf->hdr.str_len; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; snprintf(btf->name, sizeof(btf->name), "%s", module_name); =20 btf->data =3D kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN); --=20 2.34.1 From nobody Fri Dec 19 16:01:01 2025 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) (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 3D574332916 for ; Thu, 6 Nov 2025 13:20:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435240; cv=none; b=bccryM1L48X4f4lvJH58/p6/h7gI9VMP+5usHnm5atXXKKlExuBzA6FYaCL/RH5e0TTQ18Exu6RMLzPep5mYcR4RUY1kriA7WkW9/EfoQeu5r24JDMYCOOSyDnITscDusIZoKuUcIXG99z1Y4aE7h39XNnpHlePsbw+YsVwi/Hs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435240; c=relaxed/simple; bh=/oZgc5EZQ0oqNKRJlEKYw6rWHvpsXgnnWABDSIU5hdg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=QP1G2J3fwEDq9H5QVTS7xc4wdWdvukk8kDvVMlB4q5aBl8RyoQk37iXwk5CV5O5xtvJlM2Owul9xTiKfHVLDL90aBrPgqD0zfaNbc681JsT9Guwdu9ObtKBr9EAFUMvjUzw3kdI9CRVsPxOftx8FSDBBjgvH0GD+WFYTlsO4mlA= 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=fP4Weuxz; arc=none smtp.client-ip=209.85.210.179 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="fP4Weuxz" Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-781ea2cee3fso965603b3a.0 for ; Thu, 06 Nov 2025 05:20:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762435238; x=1763040038; 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=CgFobqwTDCy/M0FzLCDbAJgfJuKUpynhUI9wDqv4IFk=; b=fP4Weuxzzc5ghHkGZgCdmZU3ZOa2/PFr5IruKjJPDxHS+QDBurApmMSWGsuf5su7oC Og1CSuyDR3UEvWRjVnQHkfCB7CfoHsuRiP3Ne4KMdNxWPfkTYlPEXzfNcxHn9+Ncm3PN da66Tl05YXaJi3cFLTjpJLrApBv2qP5aGTymCkMlVJ/krPIdQL7guK0GO55E3wB3lst8 np56ciNydDhTPkEhPQAqHqT9x8Z9Yy3aAa1iUpX4u3VYSumCk3aDOpJ8FuWdVVIQv75j HprxJDf6VYe59rajnaKPv7pObdKy5SZSjtgcZlgdD50ovPEapx9xorqfFRiCUtTHJso8 e+TQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762435238; x=1763040038; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=CgFobqwTDCy/M0FzLCDbAJgfJuKUpynhUI9wDqv4IFk=; b=DcYTT1fqUDDbmnoe+xvHj7F3yezZeTry1q4YdeCdaYJ3mqlnLA3Gn9+PUOjp3SV2+o MExOrc1eMnWNZixkPyMIaPweYaT1arA4PplyBd5vXk9jofODM8orlw7Oby3fZ6HhiRGE fEbOs+vYtTm3IJmMdm61i0BIYnn9hETCMVtHGFxbSPXNaXz/Byb5Kf/f4o0QzC0Xhyxo ilGQk/tHpLHtaUoEG0bSszAdwJ4Wv4FH/6R8z0kwSyum33OjpNFgengYMdw78+TkmRhh u2bXKETb+/2kQ/5Fl02cyEsuX1h07nL5IOzDj7XYQ3gx//eDSesKjCml37tCryq1hgXQ mpBQ== X-Forwarded-Encrypted: i=1; AJvYcCX2QqAbsJ9OdG6HjayVsakvL+nuXcvvU7JnG97ENVnbd0LAOIsjOuHbgpp26958Xj1dhSK6iQsMO+Yh1UQ=@vger.kernel.org X-Gm-Message-State: AOJu0YwLEawOkEGd9jMPLFmDAIJeT/n79bqozSADgTs2NlaDdgetjfWt fWNKNE7DaD66jhBprj5I/jT1pkkI+4Z9UE9KTOfvsGaU8IoKNupT1Fdl X-Gm-Gg: ASbGncv0POi0z6kofMCEj613EKfbzoXULwPaLCR5lxJDo7raqRB0q8mYKKZOWEuu0yO HCh0C4Z63YTcOqBXu4EYIKnd8lN9QnwRmF65uS1Qna6zEksn6l5O7zyB218zHNjEAoU/IhEuFbD 0L59qvULgwi0qOF+78H/2ZirPYRClKtSJI/9jzXQOV360SPD8SwTxCsFIdmEzNYwxiZRcYJNp67 tFrvS9lpNVj0F9UnZtQ7sHXgEH/WykhYF8NYeFXQGv3Xk5rks23epNtl2dkJ6DJK/u7ctuQFPm1 ElrVg1yx3GOMy/Hbp50gp5kCDqxPtumiGAHxx01/+9DZ7ZVjuKhfgOMHVn/tgTeb+SJWMAvX3Gl kcLNtxRGfi9jdK6hJ64Ik4Peoo3K+7N6Hvj5WfBlGwg26HN1k8k0KWP+VomQo3rKF8Niuq6aFWX qMLp+XttuPgZB7vk3V X-Google-Smtp-Source: AGHT+IGmChUlKr4zR+bh7ahXgtDaj2BWrn64VpiXcCg95goTFuCvcJ8ABcPCYkwKgODrux1uBreeEw== X-Received: by 2002:a05:6a20:6a0f:b0:34f:1c92:769 with SMTP id adf61e73a8af0-34f83b0e78cmr9394651637.16.1762435238328; Thu, 06 Nov 2025 05:20:38 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-341d3e0b0b2sm1914869a91.21.2025.11.06.05.20.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 05:20:37 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu , Donglin Peng Subject: [PATCH v5 6/7] btf: Add lazy sorting validation for binary search Date: Thu, 6 Nov 2025 21:19:55 +0800 Message-Id: <20251106131956.1222864-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106131956.1222864-1-dolinux.peng@gmail.com> References: <20251106131956.1222864-1-dolinux.peng@gmail.com> 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" From: Donglin Peng Implement lazy validation of BTF type ordering to enable efficient binary search for sorted BTF while maintaining linear search fallback for unsorted cases. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 65 insertions(+), 1 deletion(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 66cb739a0598..33c327d3cac3 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -552,6 +552,70 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + const struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + if (!ta->name_off && tb->name_off) + return 1; + if (ta->name_off && !tb->name_off) + return -1; + if (!ta->name_off && !tb->name_off) + return 0; + + na =3D btf_name_by_offset(btf, ta->name_off); + nb =3D btf_name_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the orderi= ng + * is correct, counts the number of named types and updates the BTF object= 's + * nr_sorted_types field. + * + * Return: true if types are properly sorted, false otherwise + */ +static bool btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, n, k =3D 0, nr_sorted_types; + + if (likely(btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK)) + goto out; + btf->nr_sorted_types =3D 0; + + if (btf->nr_types < 2) + goto out; + + nr_sorted_types =3D 0; + n =3D btf_nr_types(btf) - 1; + for (i =3D btf_start_id(btf); i < n; i++) { + k =3D i + 1; + if (btf_compare_type_names(&i, &k, btf) > 0) + goto out; + + t =3D btf_type_by_id(btf, i); + if (t->name_off) + nr_sorted_types++; + } + + t =3D btf_type_by_id(btf, k); + if (t->name_off) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; + +out: + return btf->nr_sorted_types > 0; +} + /* Performs binary search within specified type ID range to find the leftm= ost * BTF type matching the given name. The search assumes types are sorted by * name in lexicographical order within the specified range. @@ -610,7 +674,7 @@ s32 btf_find_by_name_kind(const struct btf *btf, const = char *name, u8 kind) goto out; } =20 - if (btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK) { + if (btf_check_sorted((struct btf *)btf)) { /* binary search */ bool skip_first; s32 start_id, end_id;; --=20 2.34.1 From nobody Fri Dec 19 16:01:01 2025 Received: from mail-pj1-f51.google.com (mail-pj1-f51.google.com [209.85.216.51]) (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 8EDAC33373D for ; Thu, 6 Nov 2025 13:20:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435244; cv=none; b=h3jqJSaUX8AvEL6Lpq+Lc8iPsWo+LFDkhaFxGNM3t0Z/PFU37lq+k8jDVRphzuh5h3RsMAFOoO0IUgBscIpiAj49WedYqKzzya+a+pj/jzPiZd+rKLT3d9cd4xOx6HMc/7vnDJtGUu1TwknOvlbVHOUW+BRs1dpeKU1vAEckf5s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762435244; c=relaxed/simple; bh=kXTsduKxLo9uHmoNu6IW7eKc1GQZJpGYrGZWrIBc2AU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=RbP0jETB2tyUjJ6ynVs2isTn44jA2F+KSsmMBfKadkj9O4+sXUTOvxv5jsvxgd9+X9G9qAjvatZO79fQeNF6JAZGarC9A7fZYujo4FXyVsXzGoyL0Jx0EsH93YPdzqy9QXFpZBrsM/rNdl/LtzkdkiqED9YvPV1aStrb49zorpQ= 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=V7tChW0o; arc=none smtp.client-ip=209.85.216.51 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="V7tChW0o" Received: by mail-pj1-f51.google.com with SMTP id 98e67ed59e1d1-340ba29d518so713291a91.3 for ; Thu, 06 Nov 2025 05:20:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762435242; x=1763040042; 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=Mbhqg+u2xhmrkRGLtmWVa4WGYDJR8aV9FcUmNybsdgM=; b=V7tChW0or7DHazekqe4Q4C541ArAOidzl94ATtmmzChhZHDMP9R1SwYjFXFE2Bq0cs qpSTRLwaVPObFR/cv5/UFjkfhVGgVhDYP2vk6F+Nqr/TO0KRUYOrr3HjX8XLXSd1k6sf jtQbzvW/SkefMCTXGGkg95cC5TGdGFR8BMeHMl83hu8/TtdQuusziYYrE5D3kYsxi6Qs M41tp+HZ1+higKmg51+71x352fDbBhhipTRhUGLbis+9AP06dL587xFlJkZHaXG+ZSH9 wDl1hms/wdUuwksYN8FzZ1S8thKzPjBlwmkBLV3RWE1InDExTST1LLrBcDrxXAQcaxsg nmHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762435242; x=1763040042; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Mbhqg+u2xhmrkRGLtmWVa4WGYDJR8aV9FcUmNybsdgM=; b=vaRS5l+O5BLj9+Rrg9Hv0U+n/o0osX1qsbpTGKyEmjGtPktD2ZamMv6dwNJLpZC26x glzBProxbWuAeBwyw5SjbvJdnazVqrxilEqFojtHIDGau2nGSVxju2eToyi4pxcr8epv L+8XYy6LmKO6SDBp3WQShc6AeBt0OKmhrkoW1911w4QhHicUYodperrosdGx9uYVMTj2 nW5GjgcM5l8wyhw09iBwVfBwW/kOJrRZkIU4t/XmTjWjYx5BQoxBwwCTLO2YEFCtWuh0 WPHRwpi4SLPnsQAy+csFfhuj4K1j9zHBn4/6Gbr1yonR1oouZMicMLtv/7scERjM/Y+c xbdQ== X-Forwarded-Encrypted: i=1; AJvYcCUL5jYBuTMJrsMZwW+/k4N1ZfX2X18U/d05XS39wiDagQErnK0RTuiomPUFRHkdm2vDefmiPYKwcmY30WQ=@vger.kernel.org X-Gm-Message-State: AOJu0YzJ5fbGugfXISCsTDeRG9PJaxfEClq9BFu7Ein9ej6HoPc57prA AC5nPCu4kYOQ0En0OkFsODQ4zBB3f27MhqdgWLUvgy1m+TU2dAmM6ME0 X-Gm-Gg: ASbGncss0xQ8RyYQyUvraqEOjEhORgB7X+wrtY+utBKFS8ujPdKkynaxcyCGbjkkYGD C9EIrX4CLuxbxC0esCncVMI+z4+B+RFRGIu3sgPWnjnvCv+8CyQ+i3AWS5eCT/85lQPLZm3mtVx 4TlKmEO5/MeFALdrEnDd+POAev7VxvTYFBTe0pg5vrIkdUZvKY/TFTlfYRuMtJdtwdg9X8N2EX6 zunMG7a9iri3NnXg4LhDqwJMbAWWvOc7uzItG/G7xQq3b734qel2O3Omuej0nNYa1FEfEcvffkb BlvjcIY8vKhkezbZhuznSOi3StxxJ8Rz6KU6YqOCFml/HiqigWGjXsyKpLpycMC0kNLv5zdTleM izIUQPdh+/gbPmg8oQBAYkKS0pbJjXKnqAdD3/6LKa3une1DuR3sYk0hA/u/UUHmP8FROdbLNQf mFCcuczakUSImwfAoVWC9I+8CYNk0= X-Google-Smtp-Source: AGHT+IFHVedB9NmBgtn6+nlw/N4zptK11GvUsLCXCmsB8fjmD3DGYnva+eMZrhOmWymj8Dw6tJk+tg== X-Received: by 2002:a17:90b:1c07:b0:340:bc27:97bd with SMTP id 98e67ed59e1d1-341a6c4516cmr8047408a91.9.1762435241884; Thu, 06 Nov 2025 05:20:41 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-341d3e0b0b2sm1914869a91.21.2025.11.06.05.20.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Nov 2025 05:20:40 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu , Donglin Peng Subject: [PATCH v5 7/7] selftests/bpf: Add test cases for btf__permute functionality Date: Thu, 6 Nov 2025 21:19:56 +0800 Message-Id: <20251106131956.1222864-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251106131956.1222864-1-dolinux.peng@gmail.com> References: <20251106131956.1222864-1-dolinux.peng@gmail.com> 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" From: Donglin Peng This patch introduces test cases for the btf__permute function to ensure it works correctly with both base BTF and split BTF scenarios. The test suite includes: - test_permute_base: Validates permutation on base BTF - test_permute_split: Tests permutation on split BTF - test_permute_drop_base: Validates type dropping on base BTF - test_permute_drop_split: Tests type dropping on split BTF Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng Signed-off-by: Donglin Peng Acked-by: Eduard Zingerman --- .../selftests/bpf/prog_tests/btf_permute.c | 279 ++++++++++++++++++ 1 file changed, 279 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c diff --git a/tools/testing/selftests/bpf/prog_tests/btf_permute.c b/tools/t= esting/selftests/bpf/prog_tests/btf_permute.c new file mode 100644 index 000000000000..edab03742598 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c @@ -0,0 +1,279 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Xiaomi */ + +#include +#include +#include "btf_helpers.h" + +/* Ensure btf__permute work as expected with base_btf */ +static void test_permute_base(void) +{ + struct btf *btf; + __u32 permute_ids[6]; + int err; + + btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(btf, "empty_main_btf")) + return; + + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(btf, 1); /* [2] ptr to int */ + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */ + btf__add_func_param(btf, "p", 2); + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */ + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 4; /* struct s2 */ + permute_ids[1] =3D 3; /* struct s1 */ + permute_ids[2] =3D 5; /* int (*)(int *p) */ + permute_ids[3] =3D 1; /* int */ + permute_ids[4] =3D 6; /* int f(int *p) */ + permute_ids[5] =3D 2; /* ptr to int */ + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_OK(err, "btf__permute_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D6", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[6] PTR '(anon)' type_id=3D4"); + +done: + btf__free(btf); +} + +/* Ensure btf__permute work as expected with split_btf */ +static void test_permute_split(void) +{ + struct btf *split_btf =3D NULL, *base_btf =3D NULL; + __u32 permute_ids[4]; + int err; + + base_btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(base_btf, "empty_main_btf")) + return; + + btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(base_btf, 1); /* [2] ptr to int */ + VALIDATE_RAW_BTF( + base_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + split_btf =3D btf__new_empty_split(base_btf); + if (!ASSERT_OK_PTR(split_btf, "empty_split_btf")) + goto cleanup; + btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */ + btf__add_func_param(split_btf, "p", 2); + btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); = */ + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 6; /* int f(int *p) */ + permute_ids[1] =3D 3; /* struct s1 */ + permute_ids[2] =3D 5; /* int (*)(int *p) */ + permute_ids[3] =3D 4; /* struct s2 */ + err =3D btf__permute(split_btf, permute_ids, ARRAY_SIZE(permute_ids), NUL= L); + if (!ASSERT_OK(err, "btf__permute_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[4] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + +cleanup: + btf__free(split_btf); + btf__free(base_btf); +} + +/* Verify btf__permute function drops types correctly with base_btf */ +static void test_permute_drop_base(void) +{ + struct btf *btf; + __u32 permute_ids[6]; + int err; + + btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(btf, "empty_main_btf")) + return; + + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(btf, 1); /* [2] ptr to int */ + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */ + btf__add_func_param(btf, "p", 2); + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */ + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 4; /* struct s2 */ + permute_ids[1] =3D 2; /* ptr to int */ + permute_ids[2] =3D 5; /* int (*)(int *p) */ + permute_ids[3] =3D 1; /* int */ + err =3D btf__permute(btf, permute_ids, 4, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] PTR '(anon)' type_id=3D4", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D2", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + permute_ids[0] =3D 4; /* struct s2 */ + permute_ids[1] =3D 5; /* int (*)(int *p) */ + permute_ids[2] =3D 1; /* int */ + err =3D btf__permute(btf, permute_ids, 3, NULL); + if (!ASSERT_ERR(err, "btf__permute_drop_base_fail")) + goto done; + +done: + btf__free(btf); +} + +/* Verify btf__permute function drops types correctly with split_btf */ +static void test_permute_drop_split(void) +{ + struct btf *split_btf =3D NULL, *base_btf =3D NULL; + __u32 permute_ids[4]; + int err; + + base_btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(base_btf, "empty_main_btf")) + return; + + btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(base_btf, 1); /* [2] ptr to int */ + VALIDATE_RAW_BTF( + base_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + split_btf =3D btf__new_empty_split(base_btf); + if (!ASSERT_OK_PTR(split_btf, "empty_split_btf")) + goto cleanup; + btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */ + btf__add_func_param(split_btf, "p", 2); + btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); = */ + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 6; /* int f(int *p) */ + permute_ids[1] =3D 3; /* struct s1 */ + permute_ids[2] =3D 5; /* int (*)(int *p) */ + err =3D btf__permute(split_btf, permute_ids, 3, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[4] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2"); + + permute_ids[0] =3D 6; /* int f(int *p) */ + permute_ids[1] =3D 3; /* struct s1 */ + err =3D btf__permute(split_btf, permute_ids, 2, NULL); + if (!ASSERT_ERR(err, "btf__permute_drop_split_fail")) + goto cleanup; + +cleanup: + btf__free(split_btf); + btf__free(base_btf); +} + +void test_btf_permute(void) +{ + if (test__start_subtest("permute_base")) + test_permute_base(); + if (test__start_subtest("permute_split")) + test_permute_split(); + if (test__start_subtest("permute_drop_base")) + test_permute_drop_base(); + if (test__start_subtest("permute_drop_split")) + test_permute_drop_split(); +} --=20 2.34.1