From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pl1-f181.google.com (mail-pl1-f181.google.com [209.85.214.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 47A4335BDAF for ; Fri, 9 Jan 2026 13:00:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.181 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767963612; cv=none; b=Uu+0ZmCnoLjfIMTXFOKV7JoT+XHeJFbdfOHXqP6x1kIctssVNRY/RTi/yyp1vu/UCW0/L06cXXp+6JOL3v5LKA6+gws1UaE6cvsIh/Z5kL4YdB/PSevWSuyceoyrhkh0A37YBdYFnw4vNvHqxC6tfGIAPCg3XCLZUBcqZ+Kr99w= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767963612; c=relaxed/simple; bh=ONYPdO0oI4IQBNojYDHFrlpYRDHKceOUA21unSYU4sc=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=Vnd5b22a1w/87TzH7JTVSo7o820805+UuZfl2CmSHsBlRU56ei90xyFwSKKWcAL2lZHPa52K4F4XqA32dZ/k3brGIjYumDdDdEce5EXa202OB/df+iAy6s8f3hog5oGM8gcmDlWOwHdmmF04H9zd5Czgf6wO3drVVPzRbQ+faVw= 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=cIeOLeMd; arc=none smtp.client-ip=209.85.214.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="cIeOLeMd" Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-2a0d52768ccso30598355ad.1 for ; Fri, 09 Jan 2026 05:00:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1767963609; x=1768568409; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=DqTEFv3iEfrbQjWUf/LvglJZxV3WM/6ZgOIEMLmAOkc=; b=cIeOLeMdBMHhjyWBt3swhzL4cFwrHHFAf/mJK+8FJMd/pYsgylrb75Md0iKGmtjGT7 bRAmZauRKAszYYjmJmlqPICxN5THrcGGJ6JdGwMVmAW32AEMGmFtbTw2mcZ6a8JhKyoA GGrdxRmi1uFAbfcotjlt2wjRnHDUP2BgDc17zNnwixRKS/dePi0duY4zOGz1MPlIqEU6 dUhtXWo975MMlvqPlVVmLmMOVsTIFXMEGp6kOWSvz8L7i5+ktc6H8z4LhQn4rue+8pHG mUjshl0olSM71bD+okegb83CqWc/M4RQ400SAgDIlv029BQWrO+xpKhQMfKEf27kzMCM QvGg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1767963609; x=1768568409; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=DqTEFv3iEfrbQjWUf/LvglJZxV3WM/6ZgOIEMLmAOkc=; b=v3G6UwSSHjcRUqxMTfus4F8tWjXFmfkKBYdqqQVovgwy7LEBbUnQqOm/+pmfcX3iYz ZxU7qDol1Saun58QywOCgWv0H0lGaB9hTYI6/ABiFUzCZYI8jLsXYRp/j3r6VA+lCxNb u9HzUH5CIsrhu9MR4mwY5b/s5/ydPzPukOoc+1L5p4tN9rFGe3uxx0FBqYmlR2UgwnQZ gFotklDD0vFWUvoEOYVFfxHn4bA/mIIfckBfYkbBe29vzYu99nEC/v3q4vUg9c54ELDU D/Dal3ZFzIOsG3JDE3dEEijwG9Hov3mH2gPqWWBAWIMM61ZXOrdEH+XMIk5qdb44YMgx cZAg== X-Forwarded-Encrypted: i=1; AJvYcCU7Snc/bvgDYfukfKbEgNIyi6fvBQp5aZs69I68W3Kd6HKcA7mVa3Why+Jr+OglDaquJyhXOdpsEbCn85k=@vger.kernel.org X-Gm-Message-State: AOJu0Yw6cR/T75Akwjre8lspQbS04L1fTsR0lYNM1BtjMU39b8sdg8nM j2b9kf087p3khaC+0NQPYcfrHOaJyouPRULCcZqJ+QfmFVlcYKwvrqL1GJuNNGZmDx4= X-Gm-Gg: AY/fxX4N8QvdIypQOAPA/AWu6ntBeJcCIn/i3MINMUAA1fcQPnm5RaAUgi+ifJ7DjG0 n08PKd8BqrcUMVzHO9BvDKS1S2082jZxMXRXpLCNo3LO+zAkwoKzVab3ztuYdcz1cWBO5v4zAR3 wD5uGpuMNm+eICxXM+D2Fy4oVcwsrVvO4PrlIVmMhjbRkJkyAyqaTddUGhE0q9ZtLob8suNsw6I HNo9hg5UZvkXWD5aQZZMbzFbHJ9B0viz+rMZtSEe+sRciGMrSY95sJez6rloncbkU7vS327qTGU /DCBVHHc7ufPhAOuBZ1BnGKM6pN/8cMRylgOsRgLMsRDnzycgC7eFqFN02EisN0Mdk4unKvMTJn cfwYiqOtv5dtDOJLSSPNqF6Q9xR9R/Xym5E3/XaN6L11s8798+Qj27MNbq3AJ2S+MRCjFei57+Y khrqKXYQAY/ZMAc4G1jjK+ORoqTZ0= X-Google-Smtp-Source: AGHT+IGvVgzurJmJBd4MSK31YuP+2+7S5NrO2pJ8y77RFx440Mv8avf69aS9nv5oE0Lheg8IDfRRPg== X-Received: by 2002:a17:903:240d:b0:2a0:f469:1f5f with SMTP id d9443c01a7336-2a3ee47d198mr93051645ad.13.1767963609308; Fri, 09 Jan 2026 05:00:09 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2a3e3c3a328sm104927325ad.4.2026.01.09.05.00.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 09 Jan 2026 05:00:08 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com, eddyz87@gmail.com Cc: zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng Subject: [PATCH bpf-next v12 00/11] Improve the performance of BTF type lookups with binary search Date: Fri, 9 Jan 2026 20:59:52 +0800 Message-Id: <20260109130003.3313716-1-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit From: Donglin Peng The series addresses the performance limitations of linear search in large BTFs by: 1. Adding BTF permutation support 2. Using resolve_btfids to sort BTF during the build phase 3. Checking BTF sorting 4. Using binary search when looking up types Patch #1 introduces an interface for btf__permute in libbpf to relay out BTF. Patch #2 adds test cases to validate the functionality of btf__permute in base and split BTF scenarios. Patch #3 introduces a new phase in the resolve_btfids tool to sort BTF by name in ascending order. Patches #4-#7 implement the sorting check and binary search. Patches #8-#10 optimize type lookup performance of some functions by skipping anonymous types or invoking btf_find_by_name_kind. Patch #11 refactors the code by calling str_is_empty. Here is a simple performance test result [1] for lookups to find 87,584 named types in vmlinux BTF: ./vmtest.sh -- ./test_progs -t btf_permute/perf -v Results: | Condition | Lookup Time | Improvement | |--------------------|-------------|--------------| | Unsorted (Linear) | 36,534 ms | Baseline | | Sorted (Binary) | 15 ms | 2437x faster | The binary search implementation reduces lookup time from 36.5 seconds to 15 milliseconds, achieving a **2437x** speedup for large-scale type queries. Changelog: v12: - Set the start_id to 1 instead of btf->start_id in the btf__find_by_name (AI) v11: - Link: https://lore.kernel.org/bpf/20260108031645.1350069-1-dolinux.peng@gmail.com/ - PATCH #1: Modify implementation of btf__permute: id_map[0] must be 0 for base BTF (Andrii) - PATCH #3: Refactor the code (Andrii) - PATCH #4~8: - Revert to using the binary search in v7 to simplify the code (Andrii) - Refactor the code of btf_check_sorted (Andrii, Eduard) - Rename sorted_start_id to named_start_id - Rename btf_sorted_start_id to btf_named_start_id, and add comments (Andrii, Eduard) v10: - Link: https://lore.kernel.org/all/20251218113051.455293-1-dolinux.peng@gmail.com/ - Improve btf__permute() documentation (Eduard) - Fall back to linear search when locating anonymous types (Eduard) - Remove redundant NULL name check in libbpf's linear search path (Eduard) - Simplify btf_check_sorted() implementation (Eduard) - Treat kernel modules as unsorted by default - Introduce btf_is_sorted and btf_sorted_start_id for clarity (Eduard) - Fix optimizations in btf_find_decl_tag_value() and btf_prepare_func_args() to support split BTF - Remove linear search branch in determine_ptr_size() - Rebase onto Ihor's v4 patch series [4] v9: - Link: https://lore.kernel.org/bpf/20251208062353.1702672-1-dolinux.peng@gmail.com/ - Optimize the performance of the function determine_ptr_size by invoking btf__find_by_name_kind - Optimize the performance of btf_find_decl_tag_value/btf_prepare_func_args/ bpf_core_add_cands by skipping anonymous types - Rebase the patch series onto Ihor's v3 patch series [3] v8 - Link: https://lore.kernel.org/bpf/20251126085025.784288-1-dolinux.peng@gmail.com/ - Remove the type dropping feature of btf__permute (Andrii) - Refactor the code of btf__permute (Andrii, Eduard) - Make the self-test code cleaner (Eduard) - Reconstruct the BTF sorting patch based on Ihor's patch series [2] - Simplify the sorting logic and place anonymous types before named types (Andrii, Eduard) - Optimize type lookup performance of two kernel functions - Refactoring the binary search and type lookup logic achieves a 4.2% performance gain, reducing the average lookup time (via the perf test code in [1] for 60,995 named types in vmlinux BTF) from 10,217 us (v7) to 9,783 us (v8). v7: - Link: https://lore.kernel.org/all/20251119031531.1817099-1-dolinux.peng@gmail.com/ - btf__permute API refinement: Adjusted id_map and id_map_cnt parameter usage so that for base BTF, id_map[0] now contains the new id of original type id 1 (instead of VOID type id 0), improving logical consistency - Selftest updates: Modified test cases to align with the API usage changes - Refactor the code of resolve_btfids v6: - Link: https://lore.kernel.org/all/20251117132623.3807094-1-dolinux.peng@gmail.com/ - ID Map-based reimplementation of btf__permute (Andrii) - Build-time BTF sorting using resolve_btfids (Alexei, Eduard) - Binary search method refactoring (Andrii) - Enhanced selftest coverage v5: - Link: https://lore.kernel.org/all/20251106131956.1222864-1-dolinux.peng@gmail.com/ - Refactor binary search implementation for improved efficiency (Thanks to Andrii and Eduard) - Extend btf__permute interface with 'ids_sz' parameter to support type dropping feature (suggested by Andrii). Plan subsequent reimplementation of id_map version for comparative analysis with current sequence interface - Add comprehensive test coverage for type dropping functionality - Enhance function comment clarity and accuracy v4: - Link: https://lore.kernel.org/all/20251104134033.344807-1-dolinux.peng@gmail.com/ - Abstracted btf_dedup_remap_types logic into a helper function (suggested by Eduard). - Removed btf_sort.c and implemented sorting separately for libbpf and kernel (suggested by Andrii). - Added test cases for both base BTF and split BTF scenarios (suggested by Eduard). - Added validation for name-only sorting of types (suggested by Andrii) - Refactored btf__permute implementation to reduce complexity (suggested by Andrii) - Add doc comments for btf__permute (suggested by Andrii) v3: - Link: https://lore.kernel.org/all/20251027135423.3098490-1-dolinux.peng@gmail.com/ - Remove sorting logic from libbpf and provide a generic btf__permute() interface (suggested by Andrii) - Omitted the search direction patch to avoid conflicts with base BTF (suggested by Eduard). - Include btf_sort.c directly in btf.c to reduce function call overhead v2: - Link: https://lore.kernel.org/all/20251020093941.548058-1-dolinux.peng@gmail.com/ - Moved sorting to the build phase to reduce overhead (suggested by Alexei). - Integrated sorting into btf_dedup_compact_and_sort_types (suggested by Eduard). - Added sorting checks during BTF parsing. - Consolidated common logic into btf_sort.c for sharing (suggested by Alan). v1: - Link: https://lore.kernel.org/all/20251013131537.1927035-1-dolinux.peng@gmail.com/ [1] https://github.com/pengdonglin137/btf_sort_test [2] https://lore.kernel.org/bpf/20251126012656.3546071-1-ihor.solodrai@linux.dev/ [3] https://lore.kernel.org/bpf/20251205223046.4155870-1-ihor.solodrai@linux.dev/ [4] https://lore.kernel.org/bpf/20251218003314.260269-1-ihor.solodrai@linux.dev/ Donglin Peng (11): libbpf: Add BTF permutation support for type reordering selftests/bpf: Add test cases for btf__permute functionality tools/resolve_btfids: Support BTF sorting feature libbpf: Optimize type lookup with binary search for sorted BTF libbpf: Verify BTF sorting btf: Optimize type lookup with binary search btf: Verify BTF sorting bpf: Skip anonymous types in type lookup for performance bpf: Optimize the performance of find_bpffs_btf_enums libbpf: Optimize the performance of determine_ptr_size btf: Refactor the code by calling str_is_empty include/linux/btf.h | 1 + kernel/bpf/btf.c | 143 ++++++++- kernel/bpf/inode.c | 42 +-- kernel/bpf/verifier.c | 7 +- tools/bpf/resolve_btfids/main.c | 64 ++++ tools/lib/bpf/btf.c | 296 +++++++++++++++--- tools/lib/bpf/btf.h | 42 +++ tools/lib/bpf/libbpf.c | 4 +- tools/lib/bpf/libbpf.map | 1 + .../selftests/bpf/prog_tests/btf_permute.c | 244 +++++++++++++++ 10 files changed, 746 insertions(+), 98 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c -- 2.34.1