lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-Id: <20241029002208.1947947-1-dolinux.peng@gmail.com>
Date: Tue, 29 Oct 2024 08:22:05 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: andrii@...nel.org,
	eddyz87@...il.com
Cc: ast@...nel.org,
	rostedt@...dmis.org,
	mhiramat@...nel.org,
	bpf@...r.kernel.org,
	linux-trace-kernel@...r.kernel.org,
	linux-kselftest@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	Donglin Peng <dolinux.peng@...il.com>
Subject: [PATCH v4 0/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind

Currently, we are only using the linear search method to find the type
id by the name, which has a time complexity of O(n). This change involves
sorting the names of btf types in ascending order and using binary search,
which has a time complexity of O(log(n)). This idea was inspired by the
following patch:

60443c88f3a8 ("kallsyms: Improve the performance of kallsyms_lookup_name()").

At present, this improvement is only for searching in vmlinux's and module's BTFs.

Another change is the search direction, where we search the BTF first and
then its base, the type id of the first matched btf_type will be returned.

Here is a time-consuming result that finding 87590 type ids by their names in
vmlinux's BTF.

Before: 158426 ms
After:     114 ms

The average lookup performance has improved more than 1000x in the above scenario.

v4:
 - Divide the patch into two parts: kernel and libbpf
 - Use Eduard's code to sort btf_types in the btf__dedup function
 - Correct some btf testcases due to modifications of the order of btf_types.

v3:
 - Link: https://lore.kernel.org/all/20240608140835.965949-1-dolinux.peng@gmail.com/
 - Sort btf_types during build process other than during boot, to reduce the
   overhead of memory and boot time.

v2:
 - Link: https://lore.kernel.org/all/20230909091646.420163-1-pengdonglin@sangfor.com.cn

Donglin Peng (3):
  libbpf: Sort btf_types in ascending order by name
  bpf: Using binary search to improve the performance of
    btf_find_by_name_kind
  libbpf: Using binary search to improve the performance of
    btf__find_by_name_kind

 include/linux/btf.h                           |   1 +
 kernel/bpf/btf.c                              | 157 +++++++++-
 tools/lib/bpf/btf.c                           | 274 +++++++++++++---
 tools/testing/selftests/bpf/prog_tests/btf.c  | 296 +++++++++---------
 .../bpf/prog_tests/btf_dedup_split.c          |  64 ++--
 5 files changed, 555 insertions(+), 237 deletions(-)

-- 
2.34.1


Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ