From: Zhen Lei <thunder.leizhen@huawei.com>
To: 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>,
"Luis Chamberlain" <mcgrof@kernel.org>,
<linux-modules@vger.kernel.org>,
"Steven Rostedt" <rostedt@goodmis.org>,
Ingo Molnar <mingo@redhat.com>
Cc: Zhen Lei <thunder.leizhen@huawei.com>
Subject: [PATCH v7 04/11] kallsyms: Add helper kallsyms_compress_symbol_name()
Date: Mon, 17 Oct 2022 14:49:43 +0800 [thread overview]
Message-ID: <20221017064950.2038-5-thunder.leizhen@huawei.com> (raw)
In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com>
To speed up the lookup of a symbol in the kernel, we'd better compress
the searched symbol first and then make a quick comparison based on the
compressed length and content. But the tokens in kallsyms_token_table[]
have been expanded, a more complex process is required to complete the
compression of a symbol. So generate kallsyms_best_token_table[] helps
us to compress a symbol in the kernel using a process similar to
compress_symbol(). The implementation of kallsyms_compress_symbol_name()
is almost the same as that of compress_symbols() in scripts/kallsyms.c.
Some minor changes have been made to reduce memory usage and improve
compression performance.
1. Some entries in best_table[] are single characters, and most of them
are clustered together. such as a-z, A-Z, 0-9. These individual
characters are not used in the process of compressing a symbol. Let
kallsyms_best_token_table[i][0] = 0x00, [i][0] = number of consecutive
single characters (for exampe, a-z is 26). When [i][0] = 0x00 is
encountered, we can skip to the next token with two elements.
2. Now ARRAY_SIZE(kallsyms_best_token_table) is not fixed, we store
the content of best_table[] to kallsyms_best_token_table[] in reverse
order. That is, the higher the frequency, the lower the index.
The modifier '__maybe_unused' of kallsyms_compress_symbol_name() is
temporary and will be removed in the next patch.
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
kernel/kallsyms.c | 80 ++++++++++++++++++++++++++++++++++++++
kernel/kallsyms_internal.h | 1 +
scripts/kallsyms.c | 18 +++++++++
3 files changed, 99 insertions(+)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 60c20f301a6ba2c..f1fe404af184047 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -95,6 +95,86 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,
return off;
}
+static unsigned char *find_token(unsigned char *str, int len,
+ const unsigned char *token)
+{
+ int i;
+
+ for (i = 0; i < len - 1; i++) {
+ if (str[i] == token[0] && str[i+1] == token[1])
+ return &str[i];
+ }
+ return NULL;
+}
+
+static int __maybe_unused kallsyms_compress_symbol_name(const char *name, char *buf, size_t size)
+{
+ int i, j, n, len;
+ unsigned char *p1, *p2;
+ const unsigned char *token;
+
+ len = strscpy(buf, name, size);
+ if (WARN_ON_ONCE(len <= 0))
+ return 0;
+
+ /*
+ * For each entry in kallsyms_best_token_table[], the storage
+ * format is:
+ * 1. For tokens that cannot be used to compress characters, the value
+ * at [j] is 0, and the value at [j+1] is the number of consecutive
+ * tokens with this feature.
+ * 2. For each token: the larger the token value, the higher the
+ * frequency, and the lower the index.
+ *
+ * -------------------------------
+ * | j | [j] [j+1] | token |
+ * -----|---------------|---------|
+ * | 0 | ?? ?? | 255 |
+ * | 2 | ?? ?? | 254 |
+ * | ... | ?? ?? | ... |
+ * | n-2 | ?? ?? | x |
+ * | n | 00 len | x-1 |
+ * | n+2 | ?? ?? | x-1-len |
+ * above '??' is non-zero
+ */
+ for (i = 255, j = 0; i >= 0; i--, j += 2) {
+ if (!kallsyms_best_token_table[j]) {
+ i -= kallsyms_best_token_table[j + 1];
+ if (i < 0)
+ break;
+ j += 2;
+ }
+ token = &kallsyms_best_token_table[j];
+
+ p1 = buf;
+
+ /* find the token on the symbol */
+ p2 = find_token(p1, len, token);
+ if (!p2)
+ continue;
+
+ n = len;
+
+ do {
+ *p2 = i;
+ p2++;
+ n -= (p2 - p1);
+ memmove(p2, p2 + 1, n);
+ p1 = p2;
+ len--;
+
+ if (n < 2)
+ break;
+
+ /* find the token on the symbol */
+ p2 = find_token(p1, n, token);
+
+ } while (p2);
+ }
+
+ return len;
+}
+
/*
* Get symbol type information. This is encoded as a single char at the
* beginning of the symbol name.
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 2d0c6f2f0243a28..d9672ede8cfc215 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -26,5 +26,6 @@ extern const char kallsyms_token_table[] __weak;
extern const u16 kallsyms_token_index[] __weak;
extern const unsigned int kallsyms_markers[] __weak;
+extern const unsigned char kallsyms_best_token_table[] __weak;
#endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 60686094f665164..9864ce5e6c5bfc1 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -548,6 +548,24 @@ static void write_src(void)
for (i = 0; i < 256; i++)
printf("\t.short\t%d\n", best_idx[i]);
printf("\n");
+
+ output_label("kallsyms_best_token_table");
+ for (i = 255, k = 0; (int)i >= 0; i--) {
+ if (best_table_len[i] <= 1) {
+ k++;
+ continue;
+ }
+
+ if (k) {
+ printf("\t.byte 0x00, 0x%02x\n", k);
+ k = 0;
+ }
+
+ printf("\t.byte 0x%02x, 0x%02x\n", best_table[i][0], best_table[i][1]);
+ }
+ if (k)
+ printf("\t.byte 0x00, 0x%02x\n", k);
+ printf("\n");
}
--
2.25.1
next prev parent reply other threads:[~2022-10-17 6:53 UTC|newest]
Thread overview: 30+ 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 ` Zhen Lei [this message]
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:32 ` kernel test robot
2022-10-19 8:39 ` Leizhen (ThunderTown)
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
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=20221017064950.2038-5-thunder.leizhen@huawei.com \
--to=thunder.leizhen@huawei.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=mingo@redhat.com \
--cc=pmladek@suse.com \
--cc=rostedt@goodmis.org \
/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).