From: Luis Chamberlain <mcgrof@kernel.org>
To: "Leizhen (ThunderTown)" <thunder.leizhen@huawei.com>
Cc: Josh Poimboeuf <jpoimboe@kernel.org>,
Jiri Kosina <jikos@kernel.org>, Miroslav Benes <mbenes@suse.cz>,
Petr Mladek <pmladek@suse.com>,
Joe Lawrence <joe.lawrence@redhat.com>,
live-patching@vger.kernel.org, linux-kernel@vger.kernel.org,
Masahiro Yamada <masahiroy@kernel.org>,
Alexei Starovoitov <ast@kernel.org>, Jiri Olsa <jolsa@kernel.org>,
Kees Cook <keescook@chromium.org>,
Andrew Morton <akpm@linux-foundation.org>,
linux-modules@vger.kernel.org,
Steven Rostedt <rostedt@goodmis.org>,
Ingo Molnar <mingo@redhat.com>
Subject: Re: [PATCH v7 00/11] kallsyms: Optimizes the performance of lookup symbols
Date: Tue, 25 Oct 2022 10:53:53 -0700 [thread overview]
Message-ID: <Y1gisUFzgt1D1Jle@bombadil.infradead.org> (raw)
In-Reply-To: <ad9e51c6-f77d-d9e9-9c13-42fcbbde7147@huawei.com>
On Wed, Oct 19, 2022 at 10:11:58PM +0800, Leizhen (ThunderTown) wrote:
>
>
> On 2022/10/19 20:01, Luis Chamberlain wrote:
> > On Mon, Oct 17, 2022 at 02:49:39PM +0800, Zhen Lei wrote:
> >> Currently, to search for a symbol, we need to expand the symbols in
> >> 'kallsyms_names' one by one, and then use the expanded string for
> >> comparison. This is very slow.
> >>
> >> In fact, we can first compress the name being looked up and then use
> >> it for comparison when traversing 'kallsyms_names'.
> >>
> >> This patch series optimizes the performance of function kallsyms_lookup_name(),
> >> and function klp_find_object_symbol() in the livepatch module. Based on the
> >> test results, the performance overhead is reduced to 5%. That is, the
> >> performance of these functions is improved by 20 times.
> >
> > Stupid question, is a hash table in order?
>
> No hash table.
>
> All symbols are arranged in ascending order of address. For example: cat /proc/kallsyms
>
> The addresses of all symbols are stored in kallsyms_addresses[], and names of all symbols
> are stored in kallsyms_names[]. The elements in these two arrays are in a one-to-one
> relationship. For any symbol, it has the same index in both arrays.
>
> Therefore, when we look up a symbolic name based on an address, we use a binary lookup.
> However, when we look up an address based on a symbol name, we can only traverse array
> kallsyms_names[] in sequence. I think the reason why hash is not used is to save memory.
This answers how we don't use a hash table, the question was *should* we
use one?
Luis
next prev parent reply other threads:[~2022-10-25 17:54 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-17 6:49 [PATCH v7 00/11] kallsyms: Optimizes the performance of lookup symbols Zhen Lei
2022-10-17 6:49 ` [PATCH v7 01/11] scripts/kallsyms: rename build_initial_tok_table() Zhen Lei
2022-10-17 6:49 ` [PATCH v7 02/11] scripts/kallsyms: don't compress symbol types Zhen Lei
2022-10-17 6:49 ` [PATCH v7 03/11] scripts/kallsyms: remove helper sym_name() and cleanup Zhen Lei
2022-10-17 6:49 ` [PATCH v7 04/11] kallsyms: Add helper kallsyms_compress_symbol_name() Zhen Lei
2022-10-17 6:49 ` [PATCH v7 05/11] kallsyms: Improve the performance of kallsyms_lookup_name() Zhen Lei
2022-10-17 6:49 ` [PATCH v7 06/11] kallsyms: Improve the performance of kallsyms_lookup_name() when CONFIG_LTO_CLANG=y Zhen Lei
2022-10-17 6:49 ` [PATCH v7 07/11] kallsyms: Add helper kallsyms_on_each_match_symbol() Zhen Lei
2022-10-17 6:49 ` [PATCH v7 08/11] livepatch: Use kallsyms_on_each_match_symbol() to improve performance Zhen Lei
2022-10-17 6:49 ` [PATCH v7 09/11] livepatch: Improve the search performance of module_kallsyms_on_each_symbol() Zhen Lei
2022-10-17 6:49 ` [PATCH v7 10/11] kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol() Zhen Lei
2022-10-17 6:49 ` [PATCH v7 11/11] kallsyms: Add self-test facility Zhen Lei
2022-10-18 8:21 ` kernel test robot
2022-10-18 9:11 ` Leizhen (ThunderTown)
2022-10-18 9:11 ` Leizhen
2022-10-18 9:32 ` kernel test robot
2022-10-19 8:39 ` Leizhen (ThunderTown)
2022-10-19 8:39 ` Leizhen
2022-10-21 2:00 ` kernel test robot
2022-10-19 12:01 ` [PATCH v7 00/11] kallsyms: Optimizes the performance of lookup symbols Luis Chamberlain
2022-10-19 14:11 ` Leizhen (ThunderTown)
2022-10-25 17:53 ` Luis Chamberlain [this message]
2022-10-26 6:44 ` Leizhen (ThunderTown)
2022-10-26 19:03 ` Luis Chamberlain
2022-10-27 3:26 ` Leizhen (ThunderTown)
2022-10-27 6:27 ` Leizhen (ThunderTown)
2022-10-29 8:10 ` Leizhen (ThunderTown)
2022-10-29 12:49 ` David Laight
2022-10-31 2:55 ` Leizhen (ThunderTown)
2022-10-31 4:55 ` Leizhen (ThunderTown)
2022-10-31 15:04 ` Leizhen (ThunderTown)
2022-11-02 9:18 ` Leizhen (ThunderTown)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Y1gisUFzgt1D1Jle@bombadil.infradead.org \
--to=mcgrof@kernel.org \
--cc=akpm@linux-foundation.org \
--cc=ast@kernel.org \
--cc=jikos@kernel.org \
--cc=joe.lawrence@redhat.com \
--cc=jolsa@kernel.org \
--cc=jpoimboe@kernel.org \
--cc=keescook@chromium.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-modules@vger.kernel.org \
--cc=live-patching@vger.kernel.org \
--cc=masahiroy@kernel.org \
--cc=mbenes@suse.cz \
--cc=mingo@redhat.com \
--cc=pmladek@suse.com \
--cc=rostedt@goodmis.org \
--cc=thunder.leizhen@huawei.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.