From: Petr Mladek <pmladek@suse.com>
To: Zhen Lei <thunder.leizhen@huawei.com>
Cc: Josh Poimboeuf <jpoimboe@kernel.org>,
Jiri Kosina <jikos@kernel.org>, Miroslav Benes <mbenes@suse.cz>,
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>,
Luis Chamberlain <mcgrof@kernel.org>,
linux-modules@vger.kernel.org
Subject: Re: [PATCH v4 3/8] scripts/kallsyms: don't compress symbol types
Date: Wed, 21 Sep 2022 11:00:50 +0200 [thread overview]
Message-ID: <YyrSwnvMn5N5lV6Q@alley> (raw)
In-Reply-To: <20220920071317.1787-4-thunder.leizhen@huawei.com>
On Tue 2022-09-20 15:13:12, 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. Because we do not know the symbol type, and the symbol type
> may be combined with the following characters to form a token.
>
> So if we don't compress the symbol type, we can first compress the
> searched symbol and then make a quick comparison based on the compressed
> length and content. In this way, for entries with mismatched lengths,
> there is no need to expand and compare strings. And for those matching
> lengths, there's no need to expand the symbol. This saves a lot of time.
> According to my test results, the average performance of
> kallsyms_lookup_name() can be improved by 20 to 30 times.
>
> Of course, because the symbol type is forcibly not compressed, the
> compression rate also decreases. Here are the test results with
> defconfig:
>
> arm64: <<<<<<
> ---------------------------------------------------------------
> | ALL | nr_symbols | compressed size | original size | ratio(%) |
> -----|---------------------------------------------------------|
> Before | Y | 174094 | 1884938 | 3750653 | 50.25 |
> After | Y | 174099 | 1960154 | 3750756 | 52.26 |
> Before | N | 61744 | 725507 | 1222737 | 59.33 |
> After | N | 61747 | 745733 | 1222801 | 60.98 |
> ---------------------------------------------------------------
> The memory overhead is increased by:
> 73.5KiB and 4.0% if CONFIG_KALLSYMS_ALL=y.
> 19.8KiB and 2.8% if CONFIG_KALLSYMS_ALL=n.
>
> x86: <<<<<<<<
> ---------------------------------------------------------------
> | ALL | nr_symbols | compressed size | original size | ratio(%) |
> -----|---------------------------------------------------------|
> Before | Y | 131415 | 1697542 | 3161216 | 53.69 |
> After | Y | 131540 | 1747769 | 3163933 | 55.24 |
> Before | N | 60695 | 737627 | 1283046 | 57.49 |
> After | N | 60699 | 754797 | 1283149 | 58.82 |
> ---------------------------------------------------------------
> The memory overhead is increased by:
> 49.0KiB and 3.0% if CONFIG_KALLSYMS_ALL=y.
> 16.8KiB and 2.3% if CONFIG_KALLSYMS_ALL=n.
>
> This additional memory overhead is worth it compared to the performance
> improvement, I think.
I agree. The speedup mentioned in the followup patches looks big.
I just suggest to do this change a cleaner way, see below.
> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> ---
> scripts/kallsyms.c | 15 ++++++++++++---
> 1 file changed, 12 insertions(+), 3 deletions(-)
>
> diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> index 3319d9f38d7a5f2..1ae9ce773d2a31d 100644
> --- a/scripts/kallsyms.c
> +++ b/scripts/kallsyms.c
> @@ -61,6 +61,15 @@ static int all_symbols;
> static int absolute_percpu;
> static int base_relative;
>
> +/*
> + * Each entry in the symbol table consists of the symbol type and the symbol
> + * itself. To optimize the performance of finding or traversing symbols in
> + * kernel, do not compress the symbol type. In this way, when looking for a
> + * symbol of unknown type, we can first compress the searched symbol and then
> + * make a quick comparison based on the compressed length and content.
> + */
> +static int sym_start_idx = 1;
> +
> static int token_profit[0x10000];
>
> /* the table that holds the result of the compression */
> @@ -511,7 +520,7 @@ static void learn_symbol(const unsigned char *symbol, int len)
> {
> int i;
>
> - for (i = 0; i < len - 1; i++)
> + for (i = sym_start_idx; i < len - 1; i++)
It creates yet another twists in scripts/kallsyms.c. read_symbol()
explicitely adds the type as the first character so that it can be
compressed. And this patch adds a hack to skip it.
Let's do it a clean way and store the type serarately:
struct sym_entry {
unsigned long long addr;
unsigned int len;
unsigned int start_pos;
unsigned int percpu_absolute;
unsigned char type;
unsigned char name[];
};
static struct sym_entry *read_symbol(FILE *in)
{
[...]
name_len = strlen(name);
sym = malloc(sizeof(*sym) + name_len);
if (!sym) {
fprintf(stderr, "kallsyms failure: "
"unable to allocate required amount of memory\n");
exit(EXIT_FAILURE);
}
sym->addr = addr;
sym->len = name_len;
sym->type = type;
strcpy(sys->name, name);
sym->percpu_absolute = 0;
}
It would allow to remove the tricky:
static char *sym_name(const struct sym_entry *s)
{
return (char *)s->sym + 1;
}
and access s->name directly.
OK, the problem is how to store the type. The clean way would be
to put it into a separate section, for example:
static void write_src(void)
{
[...]
output_label("kallsyms_types");
off = 0;
for (i = 0; i < table_cnt; i++) {
printf("\t.byte 0x%02x\n", table[i]->type);
}
printf("\n");
[...]
}
It would probably increase the size even more. Another problem
is that it would need changes in the crash dump tools, see:
static int __init crash_save_vmcoreinfo_init(void)
{
[...]
VMCOREINFO_SYMBOL(kallsyms_names);
[...]
}
A solution would be to store it the old way:
static void write_src(void)
{
[...]
output_label("kallsyms_names");
off = 0;
for (i = 0; i < table_cnt; i++) {
if ((i & 0xFF) == 0)
markers[i >> 8] = off;
/*
* Store the symbol type togerher with symbol name.
* It helps to reduce the size.
*/
printf("\t.byte 0x%02x", table[i]->len + 1);
printf(", 0x%02x", table[i]->type);
for (k = 0; k < table[i]->len; k++)
printf(", 0x%02x", table[i]->sym[k]);
printf("\n");
/* symbol name lenght + type + "\n" */
off += table[i]->len + 2;
}
printf("\n");
[...]
}
The result would be the same as with your patch. But the code would be
even cleaner than before.
Best Regards,
Petr
next prev parent reply other threads:[~2022-09-21 9:00 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-20 7:13 [PATCH v4 0/8] kallsyms: Optimizes the performance of lookup symbols Zhen Lei
2022-09-20 7:13 ` [PATCH v4 1/8] scripts/kallsyms: rename build_initial_tok_table() Zhen Lei
2022-09-21 7:47 ` Petr Mladek
2022-09-20 7:13 ` [PATCH v4 2/8] scripts/kallsyms: ensure that all possible combinations are compressed Zhen Lei
2022-09-21 8:00 ` Petr Mladek
2022-09-21 8:31 ` Leizhen (ThunderTown)
2022-09-21 12:46 ` Leizhen (ThunderTown)
2022-09-20 7:13 ` [PATCH v4 3/8] scripts/kallsyms: don't compress symbol types Zhen Lei
2022-09-21 9:00 ` Petr Mladek [this message]
2022-09-21 13:13 ` Leizhen (ThunderTown)
2022-09-20 7:13 ` [PATCH v4 4/8] kallsyms: Improve the performance of kallsyms_lookup_name() Zhen Lei
2022-09-21 15:25 ` Petr Mladek
2022-09-22 2:15 ` Leizhen (ThunderTown)
2022-09-22 7:02 ` Petr Mladek
2022-09-22 7:21 ` Leizhen (ThunderTown)
2022-09-22 13:17 ` Petr Mladek
2022-09-28 1:35 ` Leizhen (ThunderTown)
2022-09-30 11:37 ` Leizhen (ThunderTown)
2022-09-22 7:14 ` Leizhen (ThunderTown)
2022-09-20 7:13 ` [PATCH v4 5/8] kallsyms: Add helper kallsyms_on_each_match_symbol() Zhen Lei
2022-09-21 15:30 ` Petr Mladek
2022-09-22 2:16 ` Leizhen (ThunderTown)
2022-09-20 7:13 ` [PATCH v4 6/8] livepatch: Use kallsyms_on_each_match_symbol() to improve performance Zhen Lei
2022-09-20 7:13 ` [PATCH v4 7/8] livepatch: Improve the search performance of module_kallsyms_on_each_symbol() Zhen Lei
2022-09-20 7:13 ` [PATCH v4 8/8] kallsyms: Add self-test facility Zhen Lei
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=YyrSwnvMn5N5lV6Q@alley \
--to=pmladek@suse.com \
--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=mcgrof@kernel.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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).