v6 --> v7:
1. Improve the performance of kallsyms_lookup_name() when CONFIG_LTO_CLANG=y
To achieve this, restrict '.' to be at the beginning of a substring, not in
the middle or end.
2. kallsyms_selftest.c adds support for CONFIG_LTO_CLANG=y.
3. Patches 4-6 are rearranged, centralize implementations of the same
functionality in one patch, rather than split it based on whether it
belongs to the tool or kernel.
4. Due to the impact of the following patches, some adaptations are made.
aa221f2ea58655f kallsyms: take the input file instead of reading stdin
73bbb94466fd3f8 kallsyms: support "big" kernel symbols
dfb352ab1162f73 kallsyms: Drop CONFIG_CFI_CLANG workarounds
v5 --> v6:
1. Add patch 6/11, kallsyms: Add helper kallsyms_lookup_clang_name()
2. Update commit message of patch 9/11.
v4 --> v5:
1. In scripts/kallsyms.c, we use an extra field to hold type and eventually
put it together with name in write_src().
2. Generate a new table kallsyms_best_token_table[], so that we compress a
symbol in the kernel using a process similar to compress_symbol().
3. Remove helper sym_name(), and rename field 'sym[]' to 'name[]' in
scripts/kallsyms.c
4. Add helper __kallsyms_lookup_compressed_name() to avoid duplicate code in
functions kallsyms_lookup_name() and kallsyms_on_each_match_symbol().
5. Add a new parameter "const char *modname" to module_kallsyms_on_each_symbol(),
this makes the code logic clearer.
6. Delete the parameter 'struct module *' in the hook function associated with
kallsyms_on_each_symbol(), it's unused now.
v3 --> v4:
1. Move the declaration of function kallsyms_sym_address() to linux/kallsyms.h,
fix a build warning.
v2 --> v3:
1. Improve test cases, perform complete functional tests on functions
kallsyms_lookup_name(), kallsyms_on_each_symbol() and
kallsyms_on_each_match_symbol().
2. Add patch [PATCH v3 2/8] scripts/kallsyms: ensure that all possible
combinations are compressed.
3. The symbol type is not compressed regardless of whether
CONFIG_KALLSYMS_ALL is set or not. The memory overhead is increased
by less than 20KiB if CONFIG_KALLSYMS_ALL=n.
4. Discard [PATCH v2 3/8] kallsyms: Adjust the types of some local variables
v1 --> v2:
Add self-test facility
v1:
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.
To avoid increasing the kernel size in non-debug mode, the optimization is only
for the case CONFIG_KALLSYMS_ALL=y.
Zhen Lei (11):
scripts/kallsyms: rename build_initial_tok_table()
scripts/kallsyms: don't compress symbol types
scripts/kallsyms: remove helper sym_name() and cleanup
kallsyms: Add helper kallsyms_compress_symbol_name()
kallsyms: Improve the performance of kallsyms_lookup_name()
kallsyms: Improve the performance of kallsyms_lookup_name() when
CONFIG_LTO_CLANG=y
kallsyms: Add helper kallsyms_on_each_match_symbol()
livepatch: Use kallsyms_on_each_match_symbol() to improve performance
livepatch: Improve the search performance of
module_kallsyms_on_each_symbol()
kallsyms: Delete an unused parameter related to
kallsyms_on_each_symbol()
kallsyms: Add self-test facility
include/linux/kallsyms.h | 12 +-
include/linux/module.h | 4 +-
init/Kconfig | 13 ++
kernel/Makefile | 1 +
kernel/kallsyms.c | 197 ++++++++++++++--
kernel/kallsyms_internal.h | 1 +
kernel/kallsyms_selftest.c | 464 +++++++++++++++++++++++++++++++++++++
kernel/livepatch/core.c | 31 ++-
kernel/module/kallsyms.c | 15 +-
kernel/trace/ftrace.c | 3 +-
scripts/kallsyms.c | 161 ++++++++++---
scripts/link-vmlinux.sh | 4 +
12 files changed, 837 insertions(+), 69 deletions(-)
create mode 100644 kernel/kallsyms_selftest.c
--
2.25.1
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.
Let's use an extra field to hold type and eventually put it together with
name in write_src().
Signed-off-by: Zhen Lei <[email protected]>
---
scripts/kallsyms.c | 38 +++++++++++++++++++++++---------------
1 file changed, 23 insertions(+), 15 deletions(-)
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index ab105bdde4efe4f..d3aae0491b3e963 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -51,6 +51,7 @@ struct sym_entry {
unsigned int len;
unsigned int start_pos;
unsigned int percpu_absolute;
+ unsigned char type;
unsigned char sym[];
};
@@ -94,7 +95,7 @@ static void usage(void)
static char *sym_name(const struct sym_entry *s)
{
- return (char *)s->sym + 1;
+ return (char *)s->sym;
}
static bool is_ignored_symbol(const char *name, char type)
@@ -242,11 +243,7 @@ static struct sym_entry *read_symbol(FILE *in)
check_symbol_range(name, addr, text_ranges, ARRAY_SIZE(text_ranges));
check_symbol_range(name, addr, &percpu_range, 1);
- /* include the type field in the symbol name, so that it gets
- * compressed together */
-
- len = strlen(name) + 1;
-
+ len = strlen(name);
sym = malloc(sizeof(*sym) + len + 1);
if (!sym) {
fprintf(stderr, "kallsyms failure: "
@@ -255,7 +252,7 @@ static struct sym_entry *read_symbol(FILE *in)
}
sym->addr = addr;
sym->len = len;
- sym->sym[0] = type;
+ sym->type = type;
strcpy(sym_name(sym), name);
sym->percpu_absolute = 0;
@@ -503,6 +500,12 @@ static void write_src(void)
exit(EXIT_FAILURE);
}
+ /*
+ * Store the symbol type togerher with symbol name.
+ * It helps to reduce the size.
+ */
+ table[i]->len++;
+
/* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
if (table[i]->len > 0x3FFF) {
fprintf(stderr, "kallsyms failure: "
@@ -522,7 +525,8 @@ static void write_src(void)
(table[i]->len >> 7) & 0x7F);
off += table[i]->len + 2;
}
- for (k = 0; k < table[i]->len; k++)
+ printf(", 0x%02x", table[i]->type);
+ for (k = 0; k < table[i]->len - 1; k++)
printf(", 0x%02x", table[i]->sym[k]);
printf("\n");
}
@@ -685,14 +689,18 @@ static void optimize_result(void)
/* start by placing the symbols that are actually used on the table */
static void insert_real_symbols_in_table(void)
{
- unsigned int i, j, c;
+ unsigned int i, j;
+ unsigned char c;
for (i = 0; i < table_cnt; i++) {
for (j = 0; j < table[i]->len; j++) {
c = table[i]->sym[j];
- best_table[c][0]=c;
- best_table_len[c]=1;
+ best_table[c][0] = c;
+ best_table_len[c] = 1;
}
+ c = table[i]->type;
+ best_table[c][0] = c;
+ best_table_len[c] = 1;
}
}
@@ -709,7 +717,7 @@ static void optimize_token_table(void)
static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
{
const char *symbol = sym_name(se);
- int len = se->len - 1;
+ int len = se->len;
if (len < 8)
return 0;
@@ -753,8 +761,8 @@ static int compare_symbols(const void *a, const void *b)
return -1;
/* sort by "weakness" type */
- wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
- wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
+ wa = (sa->type == 'w') || (sa->type == 'W');
+ wb = (sb->type == 'w') || (sb->type == 'W');
if (wa != wb)
return wa - wb;
@@ -790,7 +798,7 @@ static void make_percpus_absolute(void)
* ensure consistent behavior compared to older
* versions of this tool.
*/
- table[i]->sym[0] = 'A';
+ table[i]->type = 'A';
table[i]->percpu_absolute = 1;
}
}
--
2.25.1
Currently we traverse all symbols of all modules to find the specified
function for the specified module. But in reality, we just need to find
the given module and then traverse all the symbols in it.
Let's add a new parameter 'const char *modname' to function
module_kallsyms_on_each_symbol(), then we can compare the module names
directly in this function and call hook 'fn' after matching. And the
parameter 'struct module *' in the hook 'fn' can also be deleted.
Phase1: mod1-->mod2..(subsequent modules do not need to be compared)
|
Phase2: -->f1-->f2-->f3
Signed-off-by: Zhen Lei <[email protected]>
---
include/linux/module.h | 4 ++--
kernel/livepatch/core.c | 13 ++-----------
kernel/module/kallsyms.c | 15 ++++++++++++---
3 files changed, 16 insertions(+), 16 deletions(-)
diff --git a/include/linux/module.h b/include/linux/module.h
index ec61fb53979a92a..0a3b44ff885a48c 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -879,8 +879,8 @@ static inline bool module_sig_ok(struct module *module)
}
#endif /* CONFIG_MODULE_SIG */
-int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
- struct module *, unsigned long),
+int module_kallsyms_on_each_symbol(const char *modname,
+ int (*fn)(void *, const char *, unsigned long),
void *data);
#endif /* _LINUX_MODULE_H */
diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c
index 50bfc3481a4ee38..d4fe2d1b0e562bc 100644
--- a/kernel/livepatch/core.c
+++ b/kernel/livepatch/core.c
@@ -118,27 +118,19 @@ static struct klp_object *klp_find_object(struct klp_patch *patch,
}
struct klp_find_arg {
- const char *objname;
const char *name;
unsigned long addr;
unsigned long count;
unsigned long pos;
};
-static int klp_find_callback(void *data, const char *name,
- struct module *mod, unsigned long addr)
+static int klp_find_callback(void *data, const char *name, unsigned long addr)
{
struct klp_find_arg *args = data;
- if ((mod && !args->objname) || (!mod && args->objname))
- return 0;
-
if (strcmp(args->name, name))
return 0;
- if (args->objname && strcmp(args->objname, mod->name))
- return 0;
-
args->addr = addr;
args->count++;
@@ -175,7 +167,6 @@ static int klp_find_object_symbol(const char *objname, const char *name,
unsigned long sympos, unsigned long *addr)
{
struct klp_find_arg args = {
- .objname = objname,
.name = name,
.addr = 0,
.count = 0,
@@ -183,7 +174,7 @@ static int klp_find_object_symbol(const char *objname, const char *name,
};
if (objname)
- module_kallsyms_on_each_symbol(klp_find_callback, &args);
+ module_kallsyms_on_each_symbol(objname, klp_find_callback, &args);
else
kallsyms_on_each_match_symbol(klp_match_callback, name, &args);
diff --git a/kernel/module/kallsyms.c b/kernel/module/kallsyms.c
index f5c5c9175333df7..329cef573675d49 100644
--- a/kernel/module/kallsyms.c
+++ b/kernel/module/kallsyms.c
@@ -495,8 +495,8 @@ unsigned long module_kallsyms_lookup_name(const char *name)
}
#ifdef CONFIG_LIVEPATCH
-int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
- struct module *, unsigned long),
+int module_kallsyms_on_each_symbol(const char *modname,
+ int (*fn)(void *, const char *, unsigned long),
void *data)
{
struct module *mod;
@@ -510,6 +510,9 @@ int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
if (mod->state == MODULE_STATE_UNFORMED)
continue;
+ if (strcmp(modname, mod->name))
+ continue;
+
/* Use rcu_dereference_sched() to remain compliant with the sparse tool */
preempt_disable();
kallsyms = rcu_dereference_sched(mod->kallsyms);
@@ -522,10 +525,16 @@ int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
continue;
ret = fn(data, kallsyms_symbol_name(kallsyms, i),
- mod, kallsyms_symbol_value(sym));
+ kallsyms_symbol_value(sym));
if (ret != 0)
goto out;
}
+
+ /*
+ * The given module is found, the subsequent modules do not
+ * need to be compared.
+ */
+ break;
}
out:
mutex_unlock(&module_mutex);
--
2.25.1
The parameter 'struct module *' in the hook function associated with
kallsyms_on_each_symbol() is no longer used. Delete it.
Suggested-by: Petr Mladek <[email protected]>
Signed-off-by: Zhen Lei <[email protected]>
---
include/linux/kallsyms.h | 3 +--
kernel/kallsyms.c | 5 ++---
kernel/trace/ftrace.c | 3 +--
3 files changed, 4 insertions(+), 7 deletions(-)
diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h
index 0cd33be7142ad0d..5002ebe9dff5a0e 100644
--- a/include/linux/kallsyms.h
+++ b/include/linux/kallsyms.h
@@ -66,8 +66,7 @@ static inline void *dereference_symbol_descriptor(void *ptr)
}
#ifdef CONFIG_KALLSYMS
-int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
- unsigned long),
+int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
void *data);
int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
const char *name, void *data);
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index a1d3aa2c44e8d6f..017fe0570d5f348 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -363,8 +363,7 @@ unsigned long kallsyms_lookup_name(const char *name)
* Iterate over all symbols in vmlinux. For symbols from modules use
* module_kallsyms_on_each_symbol instead.
*/
-int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
- unsigned long),
+int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
void *data)
{
char namebuf[KSYM_NAME_LEN];
@@ -374,7 +373,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
for (i = 0, off = 0; i < kallsyms_num_syms; i++) {
off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
- ret = fn(data, namebuf, NULL, kallsyms_sym_address(i));
+ ret = fn(data, namebuf, kallsyms_sym_address(i));
if (ret != 0)
return ret;
cond_resched();
diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index fbf2543111c05c2..e3ef4f0defb2e37 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -8267,8 +8267,7 @@ struct kallsyms_data {
size_t found;
};
-static int kallsyms_callback(void *data, const char *name,
- struct module *mod, unsigned long addr)
+static int kallsyms_callback(void *data, const char *name, unsigned long addr)
{
struct kallsyms_data *args = data;
const char **sym;
--
2.25.1
Except for the function build_initial_tok_table(), no token abbreviation
is used elsewhere.
$ cat scripts/kallsyms.c | grep tok | wc -l
33
$ cat scripts/kallsyms.c | grep token | wc -l
31
Here, it would be clearer to use the full name.
Signed-off-by: Zhen Lei <[email protected]>
Reviewed-by: Petr Mladek <[email protected]>
---
scripts/kallsyms.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 03fa07ad45d95b8..ab105bdde4efe4f 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -573,7 +573,7 @@ static void forget_symbol(const unsigned char *symbol, int len)
}
/* do the initial token count */
-static void build_initial_tok_table(void)
+static void build_initial_token_table(void)
{
unsigned int i;
@@ -698,7 +698,7 @@ static void insert_real_symbols_in_table(void)
static void optimize_token_table(void)
{
- build_initial_tok_table();
+ build_initial_token_table();
insert_real_symbols_in_table();
--
2.25.1
Based on the test results of kallsyms_on_each_match_symbol() and
kallsyms_on_each_symbol(), the average performance can be improved by 20
to 30 times.
Signed-off-by: Zhen Lei <[email protected]>
---
kernel/livepatch/core.c | 20 +++++++++++++++++++-
1 file changed, 19 insertions(+), 1 deletion(-)
diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c
index 9ada0bc5247be5d..50bfc3481a4ee38 100644
--- a/kernel/livepatch/core.c
+++ b/kernel/livepatch/core.c
@@ -153,6 +153,24 @@ static int klp_find_callback(void *data, const char *name,
return 0;
}
+static int klp_match_callback(void *data, unsigned long addr)
+{
+ struct klp_find_arg *args = data;
+
+ args->addr = addr;
+ args->count++;
+
+ /*
+ * Finish the search when the symbol is found for the desired position
+ * or the position is not defined for a non-unique symbol.
+ */
+ if ((args->pos && (args->count == args->pos)) ||
+ (!args->pos && (args->count > 1)))
+ return 1;
+
+ return 0;
+}
+
static int klp_find_object_symbol(const char *objname, const char *name,
unsigned long sympos, unsigned long *addr)
{
@@ -167,7 +185,7 @@ static int klp_find_object_symbol(const char *objname, const char *name,
if (objname)
module_kallsyms_on_each_symbol(klp_find_callback, &args);
else
- kallsyms_on_each_symbol(klp_find_callback, &args);
+ kallsyms_on_each_match_symbol(klp_match_callback, name, &args);
/*
* Ensure an address was found. If sympos is 0, ensure symbol is unique;
--
2.25.1
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 <[email protected]>
---
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
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 process can be optimized.
And now scripts/kallsyms no longer compresses the symbol types, each
symbol type always occupies one byte. So 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.
The pseudo code of the test case is as follows:
static int stat_find_name(...)
{
start = sched_clock();
(void)kallsyms_lookup_name(name);
end = sched_clock();
//Update min, max, cnt, sum
}
/*
* Traverse all symbols in sequence and collect statistics on the time
* taken by kallsyms_lookup_name() to lookup each symbol.
*/
kallsyms_on_each_symbol(stat_find_name, NULL);
The test results are as follows (twice):
After : min=5250, max= 726560, avg= 302132
After : min=5320, max= 726850, avg= 301978
Before: min=170, max=15949190, avg=7553906
Before: min=160, max=15877280, avg=7517784
The average time consumed is only 4.01% and the maximum time consumed is
only 4.57% of the time consumed before optimization.
Signed-off-by: Zhen Lei <[email protected]>
---
kernel/kallsyms.c | 50 +++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 46 insertions(+), 4 deletions(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index f1fe404af184047..7f3987cc975be3b 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -107,7 +107,7 @@ static unsigned char *find_token(unsigned char *str, int len,
return NULL;
}
-static int __maybe_unused kallsyms_compress_symbol_name(const char *name, char *buf, size_t size)
+static int kallsyms_compress_symbol_name(const char *name, char *buf, size_t size)
{
int i, j, n, len;
unsigned char *p1, *p2;
@@ -267,23 +267,65 @@ static bool cleanup_symbol_name(char *s)
return false;
}
+static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
+ unsigned long *addr)
+{
+ unsigned int i, off;
+ unsigned int len, x;
+ const unsigned char *name;
+
+ for (i = 0, off = 0; namelen && i < kallsyms_num_syms; i++) {
+ /*
+ * For each entry in kallsyms_names[], the storage format is:
+ * ----------------------------
+ * | len(1-2) | type(1) | name(x) |
+ * ----------------------------
+ *
+ * Number of bytes in parentheses, and: len = 1 + x
+ */
+ len = kallsyms_names[off];
+ off++;
+ if (len & 0x80) {
+ len = (len & 0x7f) | (kallsyms_names[off] << 7);
+ off++;
+ }
+ name = &kallsyms_names[off + 1];
+ off += len;
+
+ x = len - 1;
+ if (x != namelen)
+ continue;
+
+ if (!memcmp(name, namebuf, namelen)) {
+ *addr = kallsyms_sym_address(i);
+ return 0;
+ }
+ }
+
+ return -ENOENT;
+}
+
/* Lookup the address for this symbol. Returns 0 if not found. */
unsigned long kallsyms_lookup_name(const char *name)
{
char namebuf[KSYM_NAME_LEN];
unsigned long i;
unsigned int off;
+ unsigned long addr;
+ int ret, len;
/* Skip the search for empty string. */
if (!*name)
return 0;
+ len = kallsyms_compress_symbol_name(name, namebuf, ARRAY_SIZE(namebuf));
+ ret = kallsyms_lookup_compressed_name(namebuf, len, &addr);
+ if (!ret)
+ return addr;
+
for (i = 0, off = 0; i < kallsyms_num_syms; i++) {
off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
- if (strcmp(namebuf, name) == 0)
- return kallsyms_sym_address(i);
-
if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0)
return kallsyms_sym_address(i);
}
--
2.25.1
Now, the type and name of a symbol are no longer stored together. So the
helper sym_name() is no longer needed. Correspondingly, replacing the
field name 'sym[]' with 'name[]' is more accurate.
Suggested-by: Petr Mladek <[email protected]>
Signed-off-by: Zhen Lei <[email protected]>
---
scripts/kallsyms.c | 29 ++++++++++++-----------------
1 file changed, 12 insertions(+), 17 deletions(-)
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index d3aae0491b3e963..60686094f665164 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -52,7 +52,7 @@ struct sym_entry {
unsigned int start_pos;
unsigned int percpu_absolute;
unsigned char type;
- unsigned char sym[];
+ unsigned char name[];
};
struct addr_range {
@@ -93,11 +93,6 @@ static void usage(void)
exit(1);
}
-static char *sym_name(const struct sym_entry *s)
-{
- return (char *)s->sym;
-}
-
static bool is_ignored_symbol(const char *name, char type)
{
/* Symbol names that exactly match to the following are ignored.*/
@@ -253,7 +248,7 @@ static struct sym_entry *read_symbol(FILE *in)
sym->addr = addr;
sym->len = len;
sym->type = type;
- strcpy(sym_name(sym), name);
+ strcpy((char *)sym->name, name);
sym->percpu_absolute = 0;
return sym;
@@ -277,7 +272,7 @@ static int symbol_in_range(const struct sym_entry *s,
static int symbol_valid(const struct sym_entry *s)
{
- const char *name = sym_name(s);
+ const char *name = (char *)s->name;
/* if --all-symbols is not specified, then symbols outside the text
* and inittext sections are discarded */
@@ -527,7 +522,7 @@ static void write_src(void)
}
printf(", 0x%02x", table[i]->type);
for (k = 0; k < table[i]->len - 1; k++)
- printf(", 0x%02x", table[i]->sym[k]);
+ printf(", 0x%02x", table[i]->name[k]);
printf("\n");
}
printf("\n");
@@ -582,7 +577,7 @@ static void build_initial_token_table(void)
unsigned int i;
for (i = 0; i < table_cnt; i++)
- learn_symbol(table[i]->sym, table[i]->len);
+ learn_symbol(table[i]->name, table[i]->len);
}
static unsigned char *find_token(unsigned char *str, int len,
@@ -607,14 +602,14 @@ static void compress_symbols(const unsigned char *str, int idx)
for (i = 0; i < table_cnt; i++) {
len = table[i]->len;
- p1 = table[i]->sym;
+ p1 = table[i]->name;
/* find the token on the symbol */
p2 = find_token(p1, len, str);
if (!p2) continue;
/* decrease the counts for this symbol's tokens */
- forget_symbol(table[i]->sym, len);
+ forget_symbol(table[i]->name, len);
size = len;
@@ -636,7 +631,7 @@ static void compress_symbols(const unsigned char *str, int idx)
table[i]->len = len;
/* increase the counts for this symbol's new tokens */
- learn_symbol(table[i]->sym, len);
+ learn_symbol(table[i]->name, len);
}
}
@@ -694,7 +689,7 @@ static void insert_real_symbols_in_table(void)
for (i = 0; i < table_cnt; i++) {
for (j = 0; j < table[i]->len; j++) {
- c = table[i]->sym[j];
+ c = table[i]->name[j];
best_table[c][0] = c;
best_table_len[c] = 1;
}
@@ -716,7 +711,7 @@ static void optimize_token_table(void)
/* guess for "linker script provide" symbol */
static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
{
- const char *symbol = sym_name(se);
+ const char *symbol = (char *)se->name;
int len = se->len;
if (len < 8)
@@ -773,8 +768,8 @@ static int compare_symbols(const void *a, const void *b)
return wa - wb;
/* sort by the number of prefix underscores */
- wa = strspn(sym_name(sa), "_");
- wb = strspn(sym_name(sb), "_");
+ wa = strspn((char *)sa->name, "_");
+ wb = strspn((char *)sb->name, "_");
if (wa != wb)
return wa - wb;
--
2.25.1
Added test cases for basic functions and performance of functions
kallsyms_lookup_name(), kallsyms_on_each_symbol() and
kallsyms_on_each_match_symbol(). It also calculates the compression rate
of the kallsyms compression algorithm for the current symbol set.
The basic functions test begins by testing a set of symbols whose address
values are known. Then, traverse all symbol addresses and find the
corresponding symbol name based on the address. It's impossible to
determine whether these addresses are correct, but we can use the above
three functions along with the addresses to test each other. Due to the
traversal operation of kallsyms_on_each_symbol() is too slow, only 60
symbols can be tested in one second, so let it test on average once
every 128 symbols. The other two functions validate all symbols.
If the basic functions test is passed, print only performance test
results. If the test fails, print error information, but do not perform
subsequent performance tests.
Start self-test automatically after system startup if
CONFIG_KALLSYMS_SELFTEST=y.
Example of output content: (prefix 'kallsyms_selftest:' is omitted)
start
---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
| 174099 | 1960154 | 3750756 | 52.26 |
---------------------------------------------------------
kallsyms_lookup_name() looked up 174099 symbols
The time spent on each symbol is (ns): min=5250, max=726560, avg=302132
kallsyms_on_each_symbol() traverse all: 16659500 ns
kallsyms_on_each_match_symbol() traverse all: 557400 ns
finish
Signed-off-by: Zhen Lei <[email protected]>
---
include/linux/kallsyms.h | 1 +
init/Kconfig | 13 ++
kernel/Makefile | 1 +
kernel/kallsyms.c | 2 +-
kernel/kallsyms_selftest.c | 464 +++++++++++++++++++++++++++++++++++++
5 files changed, 480 insertions(+), 1 deletion(-)
create mode 100644 kernel/kallsyms_selftest.c
diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h
index 5002ebe9dff5a0e..d4079b3d951d1ef 100644
--- a/include/linux/kallsyms.h
+++ b/include/linux/kallsyms.h
@@ -66,6 +66,7 @@ static inline void *dereference_symbol_descriptor(void *ptr)
}
#ifdef CONFIG_KALLSYMS
+unsigned long kallsyms_sym_address(int idx);
int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
void *data);
int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
diff --git a/init/Kconfig b/init/Kconfig
index 694f7c160c9c107..90c8aa75a6495a6 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1723,6 +1723,19 @@ config KALLSYMS
symbolic stack backtraces. This increases the size of the kernel
somewhat, as all symbols have to be loaded into the kernel image.
+config KALLSYMS_SELFTEST
+ bool "Test the basic functions and performance of kallsyms"
+ depends on KALLSYMS
+ default n
+ help
+ Test the basic functions and performance of some interfaces, such as
+ kallsyms_lookup_name. It also calculates the compression rate of the
+ kallsyms compression algorithm for the current symbol set.
+
+ Start self-test automatically after system startup. Suggest executing
+ "dmesg | grep kallsyms_selftest" to collect test results. "finish" is
+ displayed in the last line, indicating that the test is complete.
+
config KALLSYMS_ALL
bool "Include all symbols in kallsyms"
depends on DEBUG_KERNEL && KALLSYMS
diff --git a/kernel/Makefile b/kernel/Makefile
index d754e0be1176df3..e7fc37a6806979f 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -69,6 +69,7 @@ endif
obj-$(CONFIG_UID16) += uid16.o
obj-$(CONFIG_MODULE_SIG_FORMAT) += module_signature.o
obj-$(CONFIG_KALLSYMS) += kallsyms.o
+obj-$(CONFIG_KALLSYMS_SELFTEST) += kallsyms_selftest.o
obj-$(CONFIG_BSD_PROCESS_ACCT) += acct.o
obj-$(CONFIG_CRASH_CORE) += crash_core.o
obj-$(CONFIG_KEXEC_CORE) += kexec_core.o
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 017fe0570d5f348..f886bc71630d486 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -226,7 +226,7 @@ static unsigned int get_symbol_offset(unsigned long pos)
return name - kallsyms_names;
}
-static unsigned long kallsyms_sym_address(int idx)
+unsigned long kallsyms_sym_address(int idx)
{
if (!IS_ENABLED(CONFIG_KALLSYMS_BASE_RELATIVE))
return kallsyms_addresses[idx];
diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c
new file mode 100644
index 000000000000000..d6736e7fb2b0bc5
--- /dev/null
+++ b/kernel/kallsyms_selftest.c
@@ -0,0 +1,464 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Test the function and performance of kallsyms
+ *
+ * Copyright (C) Huawei Technologies Co., Ltd., 2022
+ *
+ * Authors: Zhen Lei <[email protected]> Huawei
+ */
+
+#define pr_fmt(fmt) "kallsyms_selftest: " fmt
+
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/kallsyms.h>
+#include <linux/random.h>
+#include <linux/sched/clock.h>
+#include <linux/kthread.h>
+#include <linux/vmalloc.h>
+
+#include "kallsyms_internal.h"
+
+
+#define MAX_NUM_OF_RECORDS 64
+
+struct test_stat {
+ int min;
+ int max;
+ int save_cnt;
+ int real_cnt;
+ int perf;
+ u64 sum;
+ char *name;
+ unsigned long addr;
+ unsigned long addrs[MAX_NUM_OF_RECORDS];
+};
+
+struct test_item {
+ char *name;
+ unsigned long addr;
+};
+
+#define ITEM_FUNC(s) \
+ { \
+ .name = #s, \
+ .addr = (unsigned long)s, \
+ }
+
+#define ITEM_DATA(s) \
+ { \
+ .name = #s, \
+ .addr = (unsigned long)&s, \
+ }
+
+static int test_var_bss_static;
+static int test_var_data_static = 1;
+int test_var_bss;
+int test_var_data = 1;
+
+static int test_func_static(void)
+{
+ test_var_bss_static++;
+ test_var_data_static++;
+
+ return 0;
+}
+
+int test_func(void)
+{
+ return test_func_static();
+}
+
+__weak int test_func_weak(void)
+{
+ test_var_bss++;
+ test_var_data++;
+ return 0;
+}
+
+static struct test_item test_items[] = {
+ ITEM_FUNC(test_func_static),
+ ITEM_FUNC(test_func),
+ ITEM_FUNC(test_func_weak),
+ ITEM_FUNC(vmalloc),
+ ITEM_FUNC(vfree),
+#ifdef CONFIG_KALLSYMS_ALL
+ ITEM_DATA(test_var_bss_static),
+ ITEM_DATA(test_var_data_static),
+ ITEM_DATA(test_var_bss),
+ ITEM_DATA(test_var_data),
+ ITEM_DATA(vmap_area_list),
+#endif
+};
+
+static char stub_name[KSYM_NAME_LEN];
+
+static int stat_symbol_len(void *data, const char *name, unsigned long addr)
+{
+ *(u32 *)data += strlen(name);
+
+ return 0;
+}
+
+static void test_kallsyms_compression_ratio(void)
+{
+ int i;
+ const u8 *name;
+ u32 pos;
+ u32 ratio, total_size, total_len = 0;
+
+ kallsyms_on_each_symbol(stat_symbol_len, &total_len);
+
+ /*
+ * A symbol name cannot start with a number. This stub name helps us
+ * traverse the entire symbol table without finding a match. It's used
+ * for subsequent performance tests, and its length is the average
+ * length of all symbol names.
+ */
+ memset(stub_name, '4', sizeof(stub_name));
+ pos = total_len / kallsyms_num_syms;
+ stub_name[pos] = 0;
+
+ pos = kallsyms_num_syms - 1;
+ name = &kallsyms_names[kallsyms_markers[pos >> 8]];
+ for (i = 0; i <= (pos & 0xff); i++)
+ name = name + (*name) + 1;
+
+ /*
+ * 1. The length fields is not counted
+ * 2. The memory occupied by array kallsyms_token_table[] and
+ * kallsyms_token_index[] needs to be counted.
+ */
+ total_size = (name - kallsyms_names) - kallsyms_num_syms;
+ pos = kallsyms_token_index[0xff];
+ total_size += pos + strlen(&kallsyms_token_table[pos]) + 1;
+ total_size += 0x100 * sizeof(u16);
+
+ pr_info(" ---------------------------------------------------------\n");
+ pr_info("| nr_symbols | compressed size | original size | ratio(%%) |\n");
+ pr_info("|---------------------------------------------------------|\n");
+ ratio = (u32)div_u64(10000ULL * total_size, total_len);
+ pr_info("| %10d | %10d | %10d | %2d.%-2d |\n",
+ kallsyms_num_syms, total_size, total_len, ratio / 100, ratio % 100);
+ pr_info(" ---------------------------------------------------------\n");
+}
+
+static int lookup_name(void *data, const char *name, unsigned long addr)
+{
+ u64 t0, t1, t;
+ unsigned long flags;
+ struct test_stat *stat = (struct test_stat *)data;
+
+ local_irq_save(flags);
+ t0 = sched_clock();
+ (void)kallsyms_lookup_name(name);
+ t1 = sched_clock();
+ local_irq_restore(flags);
+
+ t = t1 - t0;
+ if (t < stat->min)
+ stat->min = t;
+
+ if (t > stat->max)
+ stat->max = t;
+
+ stat->real_cnt++;
+ stat->sum += t;
+
+ return 0;
+}
+
+static void test_perf_kallsyms_lookup_name(void)
+{
+ struct test_stat stat;
+
+ memset(&stat, 0, sizeof(stat));
+ stat.min = INT_MAX;
+ kallsyms_on_each_symbol(lookup_name, &stat);
+ pr_info("kallsyms_lookup_name() looked up %d symbols\n", stat.real_cnt);
+ pr_info("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n",
+ stat.min, stat.max, stat.sum / stat.real_cnt);
+}
+
+static bool match_cleanup_name(const char *s, const char *name)
+{
+ char *p;
+ int len;
+
+ if (!IS_ENABLED(CONFIG_LTO_CLANG))
+ return false;
+
+ p = strchr(s, '.');
+ if (!p)
+ return false;
+
+ len = strlen(name);
+ if (p - s != len)
+ return false;
+
+ return !strncmp(s, name, len);
+}
+
+static int find_symbol(void *data, const char *name, unsigned long addr)
+{
+ struct test_stat *stat = (struct test_stat *)data;
+
+ if (strcmp(name, stat->name) == 0 ||
+ (!stat->perf && match_cleanup_name(name, stat->name))) {
+ stat->real_cnt++;
+ stat->addr = addr;
+
+ if (stat->save_cnt < MAX_NUM_OF_RECORDS) {
+ stat->addrs[stat->save_cnt] = addr;
+ stat->save_cnt++;
+ }
+
+ if (stat->real_cnt == stat->max)
+ return 1;
+ }
+
+ return 0;
+}
+
+static void test_perf_kallsyms_on_each_symbol(void)
+{
+ u64 t0, t1;
+ unsigned long flags;
+ struct test_stat stat;
+
+ memset(&stat, 0, sizeof(stat));
+ stat.max = INT_MAX;
+ stat.name = stub_name;
+ stat.perf = 1;
+ local_irq_save(flags);
+ t0 = sched_clock();
+ kallsyms_on_each_symbol(find_symbol, &stat);
+ t1 = sched_clock();
+ local_irq_restore(flags);
+ pr_info("kallsyms_on_each_symbol() traverse all: %lld ns\n", t1 - t0);
+}
+
+static int match_symbol(void *data, unsigned long addr)
+{
+ struct test_stat *stat = (struct test_stat *)data;
+
+ stat->real_cnt++;
+ stat->addr = addr;
+
+ if (stat->save_cnt < MAX_NUM_OF_RECORDS) {
+ stat->addrs[stat->save_cnt] = addr;
+ stat->save_cnt++;
+ }
+
+ if (stat->real_cnt == stat->max)
+ return 1;
+
+ return 0;
+}
+
+static void test_perf_kallsyms_on_each_match_symbol(void)
+{
+ u64 t0, t1;
+ unsigned long flags;
+ struct test_stat stat;
+
+ memset(&stat, 0, sizeof(stat));
+ stat.max = INT_MAX;
+ stat.name = stub_name;
+ local_irq_save(flags);
+ t0 = sched_clock();
+ kallsyms_on_each_match_symbol(match_symbol, stat.name, &stat);
+ t1 = sched_clock();
+ local_irq_restore(flags);
+ pr_info("kallsyms_on_each_match_symbol() traverse all: %lld ns\n", t1 - t0);
+}
+
+static int test_kallsyms_basic_function(void)
+{
+ int i, j, ret;
+ int next = 0, nr_failed = 0;
+ char *prefix;
+ unsigned short rand;
+ unsigned long addr, lookup_addr;
+ char namebuf[KSYM_NAME_LEN];
+ struct test_stat stat, stat2;
+
+ prefix = "kallsyms_lookup_name() for";
+ for (i = 0; i < ARRAY_SIZE(test_items); i++) {
+ addr = kallsyms_lookup_name(test_items[i].name);
+ if (addr != test_items[i].addr) {
+ nr_failed++;
+ pr_info("%s %s failed: addr=%lx, expect %lx\n",
+ prefix, test_items[i].name, addr, test_items[i].addr);
+ }
+ }
+
+ prefix = "kallsyms_on_each_symbol() for";
+ for (i = 0; i < ARRAY_SIZE(test_items); i++) {
+ memset(&stat, 0, sizeof(stat));
+ stat.max = INT_MAX;
+ stat.name = test_items[i].name;
+ kallsyms_on_each_symbol(find_symbol, &stat);
+ if (stat.addr != test_items[i].addr || stat.real_cnt != 1) {
+ nr_failed++;
+ pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
+ prefix, test_items[i].name,
+ stat.real_cnt, stat.addr, test_items[i].addr);
+ }
+ }
+
+ prefix = "kallsyms_on_each_match_symbol() for";
+ for (i = 0; i < ARRAY_SIZE(test_items); i++) {
+ memset(&stat, 0, sizeof(stat));
+ stat.max = INT_MAX;
+ stat.name = test_items[i].name;
+ kallsyms_on_each_match_symbol(match_symbol, test_items[i].name, &stat);
+ if (stat.addr != test_items[i].addr || stat.real_cnt != 1) {
+ nr_failed++;
+ pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
+ prefix, test_items[i].name,
+ stat.real_cnt, stat.addr, test_items[i].addr);
+ }
+ }
+
+ if (nr_failed)
+ return -ESRCH;
+
+ for (i = 0; i < kallsyms_num_syms; i++) {
+ addr = kallsyms_sym_address(i);
+ if (!is_ksym_addr(addr))
+ continue;
+
+ ret = lookup_symbol_name(addr, namebuf);
+ if (unlikely(ret)) {
+ namebuf[0] = 0;
+ goto failed;
+ }
+
+ /*
+ * The first '.' may be the initial letter, in which case the
+ * entire symbol name will be truncated to an empty string in
+ * cleanup_symbol_name(). Do not test these symbols.
+ *
+ * For example:
+ * cat /proc/kallsyms | awk '{print $3}' | grep -E "^\." | head
+ * .E_read_words
+ * .E_leading_bytes
+ * .E_trailing_bytes
+ * .E_write_words
+ * .E_copy
+ * .str.292.llvm.12122243386960820698
+ * .str.24.llvm.12122243386960820698
+ * .str.29.llvm.12122243386960820698
+ * .str.75.llvm.12122243386960820698
+ * .str.99.llvm.12122243386960820698
+ */
+ if (IS_ENABLED(CONFIG_LTO_CLANG) && !namebuf[0])
+ continue;
+
+ lookup_addr = kallsyms_lookup_name(namebuf);
+
+ memset(&stat, 0, sizeof(stat));
+ stat.max = INT_MAX;
+ kallsyms_on_each_match_symbol(match_symbol, namebuf, &stat);
+
+ /*
+ * kallsyms_on_each_symbol() is too slow, randomly select some
+ * symbols for test.
+ */
+ if (i >= next) {
+ memset(&stat2, 0, sizeof(stat2));
+ stat2.max = INT_MAX;
+ stat2.name = namebuf;
+ kallsyms_on_each_symbol(find_symbol, &stat2);
+
+ /*
+ * kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol()
+ * need to get the same traversal result.
+ */
+ if (stat.addr != stat2.addr ||
+ stat.real_cnt != stat2.real_cnt ||
+ memcmp(stat.addrs, stat2.addrs,
+ stat.save_cnt * sizeof(stat.addrs[0])))
+ goto failed;
+
+ /*
+ * The average of random increments is 128, that is, one of
+ * them is tested every 128 symbols.
+ */
+ get_random_bytes(&rand, sizeof(rand));
+ next = i + (rand & 0xff) + 1;
+ }
+
+ /* Need to be found at least once */
+ if (!stat.real_cnt)
+ goto failed;
+
+ /*
+ * kallsyms_lookup_name() returns the address of the first
+ * symbol found and cannot be NULL.
+ */
+ if (!lookup_addr || lookup_addr != stat.addrs[0])
+ goto failed;
+
+ /*
+ * If the addresses of all matching symbols are recorded, the
+ * target address needs to be exist.
+ */
+ if (stat.real_cnt <= MAX_NUM_OF_RECORDS) {
+ for (j = 0; j < stat.save_cnt; j++) {
+ if (stat.addrs[j] == addr)
+ break;
+ }
+
+ if (j == stat.save_cnt)
+ goto failed;
+ }
+ }
+
+ return 0;
+
+failed:
+ pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr);
+ return -ESRCH;
+}
+
+static int test_entry(void *p)
+{
+ int ret;
+
+ do {
+ schedule_timeout(5 * HZ);
+ } while (system_state != SYSTEM_RUNNING);
+
+ pr_info("start\n");
+ ret = test_kallsyms_basic_function();
+ if (ret) {
+ pr_info("abort\n");
+ return 0;
+ }
+
+ test_kallsyms_compression_ratio();
+ test_perf_kallsyms_lookup_name();
+ test_perf_kallsyms_on_each_symbol();
+ test_perf_kallsyms_on_each_match_symbol();
+ pr_info("finish\n");
+
+ return 0;
+}
+
+static int __init kallsyms_test_init(void)
+{
+ struct task_struct *t;
+
+ t = kthread_create(test_entry, NULL, "kallsyms_test");
+ if (IS_ERR(t)) {
+ pr_info("Create kallsyms selftest task failed\n");
+ return PTR_ERR(t);
+ }
+ kthread_bind(t, 0);
+ wake_up_process(t);
+
+ return 0;
+}
+late_initcall(kallsyms_test_init);
--
2.25.1
LLVM appends various suffixes for local functions and variables, suffixes
observed:
- foo.llvm.[0-9a-f]+
- foo.[0-9a-f]+
Therefore, when CONFIG_LTO_CLANG=y, kallsyms_lookup_name() needs to
truncate the suffix of the symbol name before comparing the local function
or variable name.
Currently, to improve performance, we compare tokens generated by
compressing the function name or variable name without suffix. However,
the symbols recorded in kallsyms_names[] are compressed with suffixes.
During symbol compression, the suffix header may be combined with a
subsequent token to generate a new token, or may be combined with a
previous token to generate a new token. This combination process must
follow a strict sequence, otherwise we may not get the same result.
For example:
Assume that the following three combinations occur in descending order:
c. > b[c.] > ab
The compression result of "abc." is: "a" + "bc."
The compression result of "abc" is: "ab" + "c"
Therefore, when CONFIG_LTO_CLANG=y, the compression algorithm needs to be
adjusted. That is, the token with the suffix header cannot be combined
with the token before it. The two substrings before and after the suffix
header are compressed separately.
sub-string1 (function or variable name, without suffix)
sub-string2 (suffix, contains suffix header '.')
The implementation of the tool is as follows:
1. A new table polluted_table[] is added, it records all tokens with
suffix headers after expansion. These tokens are called polluted
tokens, which are polluted by suffix headers. When combined with other
tokens, these tokens cannot be placed behind them. This ensures that
the suffix header is at the beginning of all tokens after expansion.
2. Because the suffix needs to be processed only when CONFIG_LTO_CLANG=y,
option "--lto-clang" is added, to avoid affecting the compression ratio
when CONFIG_LTO_CLANG=n.
According to the test result, the memory increment is less than 1KB,
regardless of whether CONFIG_LTO_CLANG=y or CONFIG_LTO_CLANG=n.
The implementation on the kernel side is relatively simple:
1. Compare only when the length is equal or the next token after expansion
starts with suffix initial. Although there is no guarantee that this
suffix initial is the suffix header, for example, the suffix may
contain two '.', such as "show_cpuinfo.llvm.3123972329667954434".
Don't worry, one with '.' and one without '.', the comparison is bound
to fail.
Signed-off-by: Zhen Lei <[email protected]>
---
kernel/kallsyms.c | 30 ++++++++++++-----
scripts/kallsyms.c | 74 +++++++++++++++++++++++++++++++++++++++--
scripts/link-vmlinux.sh | 4 +++
3 files changed, 97 insertions(+), 11 deletions(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 7f3987cc975be3b..bd1f263b1c69b53 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -267,6 +267,25 @@ static bool cleanup_symbol_name(char *s)
return false;
}
+/*
+ * Please refer to the comments in cleanup_symbol_name() for more details.
+ * The former is used to handle expanded symbols, while this function is used
+ * to handle unexpanded symbols.
+ */
+static bool cleanup_compressed_symbol_name(int token)
+{
+ char first;
+
+ if (!IS_ENABLED(CONFIG_LTO_CLANG))
+ return false;
+
+ first = kallsyms_token_table[kallsyms_token_index[token]];
+ if (first == '.')
+ return true;
+
+ return false;
+}
+
static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
unsigned long *addr)
{
@@ -293,7 +312,8 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
off += len;
x = len - 1;
- if (x != namelen)
+ if ((x < namelen) ||
+ (x > namelen && !cleanup_compressed_symbol_name(name[namelen])))
continue;
if (!memcmp(name, namebuf, namelen)) {
@@ -309,8 +329,6 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
unsigned long kallsyms_lookup_name(const char *name)
{
char namebuf[KSYM_NAME_LEN];
- unsigned long i;
- unsigned int off;
unsigned long addr;
int ret, len;
@@ -323,12 +341,6 @@ unsigned long kallsyms_lookup_name(const char *name)
if (!ret)
return addr;
- for (i = 0, off = 0; i < kallsyms_num_syms; i++) {
- off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-
- if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0)
- return kallsyms_sym_address(i);
- }
return module_kallsyms_lookup_name(name);
}
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 9864ce5e6c5bfc1..7fbb976f3805b17 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -78,6 +78,10 @@ static unsigned int table_size, table_cnt;
static int all_symbols;
static int absolute_percpu;
static int base_relative;
+static int lto_clang;
+
+static unsigned char polluted_table[256];
+static unsigned char polluted_table_len;
static int token_profit[0x10000];
@@ -89,7 +93,7 @@ static unsigned char best_table_len[256];
static void usage(void)
{
fprintf(stderr, "Usage: kallsyms [--all-symbols] [--absolute-percpu] "
- "[--base-relative] in.map > out.S\n");
+ "[--base-relative] [--lto-clang] in.map > out.S\n");
exit(1);
}
@@ -653,6 +657,67 @@ static void compress_symbols(const unsigned char *str, int idx)
}
}
+static void init_polluted_table(void)
+{
+ int i;
+ unsigned char c;
+ unsigned char suffix_head[] = {'.'};
+
+ if (!lto_clang)
+ return;
+
+ for (i = 0; i < sizeof(suffix_head); i++) {
+ c = suffix_head[i];
+ if (best_table_len[c])
+ polluted_table[polluted_table_len++] = c;
+ }
+}
+
+static void update_polluted_table(unsigned char new_token)
+{
+ int i;
+ unsigned char first_token;
+
+ if (!lto_clang)
+ return;
+
+ /*
+ * Polluted tokens are prohibited from being at the end, so they can
+ * only be at the beginning, only the first sub-token needs to be
+ * checked.
+ */
+ first_token = best_table[new_token][0];
+ for (i = 0; i < polluted_table_len; i++) {
+ if (first_token == polluted_table[i]) {
+ polluted_table[polluted_table_len++] = new_token;
+ return;
+ }
+ }
+}
+
+/*
+ * To ensure that the first character of the suffix(such as '.') is at the
+ * beginning of the expanded substring. During compression, no token with
+ * suffix header(all of them are recorded in polluted_table[]) is allowed
+ * to be at the end.
+ */
+static bool is_forbidden(int index)
+{
+ int i;
+ unsigned char last_token;
+
+ if (!lto_clang)
+ return false;
+
+ last_token = (index >> 8) & 0xFF;
+ for (i = 0; i < polluted_table_len; i++) {
+ if (last_token == polluted_table[i])
+ return true;
+ }
+
+ return false;
+}
+
/* search the token with the maximum profit */
static int find_best_token(void)
{
@@ -662,7 +727,7 @@ static int find_best_token(void)
best = 0;
for (i = 0; i < 0x10000; i++) {
- if (token_profit[i] > bestprofit) {
+ if ((token_profit[i] > bestprofit) && !is_forbidden(i)) {
best = i;
bestprofit = token_profit[i];
}
@@ -693,6 +758,8 @@ static void optimize_result(void)
best_table[i][0] = best & 0xFF;
best_table[i][1] = (best >> 8) & 0xFF;
+ update_polluted_table((unsigned char)i);
+
/* replace this token in all the valid symbols */
compress_symbols(best_table[i], i);
}
@@ -715,6 +782,8 @@ static void insert_real_symbols_in_table(void)
best_table[c][0] = c;
best_table_len[c] = 1;
}
+
+ init_polluted_table();
}
static void optimize_token_table(void)
@@ -839,6 +908,7 @@ int main(int argc, char **argv)
{"all-symbols", no_argument, &all_symbols, 1},
{"absolute-percpu", no_argument, &absolute_percpu, 1},
{"base-relative", no_argument, &base_relative, 1},
+ {"lto-clang", no_argument, <o_clang, 1},
{},
};
diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index 918470d768e9c7d..32e573943cf036b 100755
--- a/scripts/link-vmlinux.sh
+++ b/scripts/link-vmlinux.sh
@@ -156,6 +156,10 @@ kallsyms()
kallsymopt="${kallsymopt} --base-relative"
fi
+ if is_enabled CONFIG_LTO_CLANG; then
+ kallsymopt="${kallsymopt} --lto-clang"
+ fi
+
info KSYMS ${2}
scripts/kallsyms ${kallsymopt} ${1} > ${2}
}
--
2.25.1
Function kallsyms_on_each_symbol() traverses all symbols and submits each
symbol to the hook 'fn' for judgment and processing. For some cases, the
hook actually only handles the matched symbol, such as livepatch.
So that, we can first compress the name being looked up and then use
it for comparison when traversing 'kallsyms_names', this greatly reduces
the time consumed by traversing.
The pseudo code of the test case is as follows:
static int tst_find(void *data, const char *name,
struct module *mod, unsigned long addr)
{
if (strcmp(name, "stub_name") == 0)
*(unsigned long *)data = addr;
return 0;
}
static int tst_match(void *data, unsigned long addr)
{
*(unsigned long *)data = addr;
return 0;
}
start = sched_clock();
kallsyms_on_each_match_symbol(tst_match, "stub_name", &addr);
end = sched_clock();
start = sched_clock();
kallsyms_on_each_symbol(tst_find, &addr);
end = sched_clock();
The test results are as follows (twice):
kallsyms_on_each_match_symbol: 557400, 583900
kallsyms_on_each_symbol : 16659500, 16113950
kallsyms_on_each_match_symbol() consumes only 3.48% of
kallsyms_on_each_symbol()'s time.
Signed-off-by: Zhen Lei <[email protected]>
---
include/linux/kallsyms.h | 8 ++++++++
kernel/kallsyms.c | 44 ++++++++++++++++++++++++++++++++++++----
2 files changed, 48 insertions(+), 4 deletions(-)
diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h
index 649faac31ddb162..0cd33be7142ad0d 100644
--- a/include/linux/kallsyms.h
+++ b/include/linux/kallsyms.h
@@ -69,6 +69,8 @@ static inline void *dereference_symbol_descriptor(void *ptr)
int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
unsigned long),
void *data);
+int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
+ const char *name, void *data);
/* Lookup the address for a symbol. Returns 0 if not found. */
unsigned long kallsyms_lookup_name(const char *name);
@@ -168,6 +170,12 @@ static inline int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct
{
return -EOPNOTSUPP;
}
+
+static inline int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
+ const char *name, void *data)
+{
+ return -EOPNOTSUPP;
+}
#endif /*CONFIG_KALLSYMS*/
static inline void print_ip_sym(const char *loglvl, unsigned long ip)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index bd1f263b1c69b53..a1d3aa2c44e8d6f 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -286,14 +286,17 @@ static bool cleanup_compressed_symbol_name(int token)
return false;
}
-static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
- unsigned long *addr)
+static int __kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
+ unsigned int *index,
+ unsigned int *offset,
+ unsigned long *addr)
{
- unsigned int i, off;
+ unsigned int i = *index;
+ unsigned int off = *offset;
unsigned int len, x;
const unsigned char *name;
- for (i = 0, off = 0; namelen && i < kallsyms_num_syms; i++) {
+ for (; namelen && i < kallsyms_num_syms; i++) {
/*
* For each entry in kallsyms_names[], the storage format is:
* ----------------------------
@@ -317,6 +320,10 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
continue;
if (!memcmp(name, namebuf, namelen)) {
+ /* Prepare for the next iteration */
+ *index = i + 1;
+ *offset = off;
+
*addr = kallsyms_sym_address(i);
return 0;
}
@@ -325,6 +332,14 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen,
return -ENOENT;
}
+static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len,
+ unsigned long *addr)
+{
+ unsigned int i = 0, off = 0;
+
+ return __kallsyms_lookup_compressed_name(namebuf, len, &i, &off, addr);
+}
+
/* Lookup the address for this symbol. Returns 0 if not found. */
unsigned long kallsyms_lookup_name(const char *name)
{
@@ -367,6 +382,27 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
return 0;
}
+int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
+ const char *name, void *data)
+{
+ int ret, len;
+ unsigned long addr;
+ unsigned int i = 0, off = 0;
+ char namebuf[KSYM_NAME_LEN];
+
+ len = kallsyms_compress_symbol_name(name, namebuf, ARRAY_SIZE(namebuf));
+ do {
+ ret = __kallsyms_lookup_compressed_name(namebuf, len, &i, &off, &addr);
+ if (ret)
+ return 0; /* end of lookup */
+
+ ret = fn(data, addr);
+ cond_resched();
+ } while (!ret);
+
+ return ret;
+}
+
static unsigned long get_symbol_pos(unsigned long addr,
unsigned long *symbolsize,
unsigned long *offset)
--
2.25.1
Hi Zhen,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on masahiroy-kbuild/for-next]
[also build test WARNING on linus/master v6.1-rc1 next-20221018]
[cannot apply to mcgrof/modules-next]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
base: https://git.kernel.org/pub/scm/linux/kernel/git/masahiroy/linux-kbuild.git for-next
patch link: https://lore.kernel.org/r/20221017064950.2038-12-thunder.leizhen%40huawei.com
patch subject: [PATCH v7 11/11] kallsyms: Add self-test facility
config: sh-allmodconfig
compiler: sh4-linux-gcc (GCC) 12.1.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
git checkout 3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=sh SHELL=/bin/bash
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <[email protected]>
All warnings (new ones prefixed by >>):
kernel/kallsyms_selftest.c:67:5: warning: no previous prototype for 'test_func' [-Wmissing-prototypes]
67 | int test_func(void)
| ^~~~~~~~~
kernel/kallsyms_selftest.c:72:12: warning: no previous prototype for 'test_func_weak' [-Wmissing-prototypes]
72 | __weak int test_func_weak(void)
| ^~~~~~~~~~~~~~
kernel/kallsyms_selftest.c: In function 'test_kallsyms_basic_function':
>> kernel/kallsyms_selftest.c:424:1: warning: the frame size of 1124 bytes is larger than 1024 bytes [-Wframe-larger-than=]
424 | }
| ^
vim +424 kernel/kallsyms_selftest.c
275
276 static int test_kallsyms_basic_function(void)
277 {
278 int i, j, ret;
279 int next = 0, nr_failed = 0;
280 char *prefix;
281 unsigned short rand;
282 unsigned long addr, lookup_addr;
283 char namebuf[KSYM_NAME_LEN];
284 struct test_stat stat, stat2;
285
286 prefix = "kallsyms_lookup_name() for";
287 for (i = 0; i < ARRAY_SIZE(test_items); i++) {
288 addr = kallsyms_lookup_name(test_items[i].name);
289 if (addr != test_items[i].addr) {
290 nr_failed++;
291 pr_info("%s %s failed: addr=%lx, expect %lx\n",
292 prefix, test_items[i].name, addr, test_items[i].addr);
293 }
294 }
295
296 prefix = "kallsyms_on_each_symbol() for";
297 for (i = 0; i < ARRAY_SIZE(test_items); i++) {
298 memset(&stat, 0, sizeof(stat));
299 stat.max = INT_MAX;
300 stat.name = test_items[i].name;
301 kallsyms_on_each_symbol(find_symbol, &stat);
302 if (stat.addr != test_items[i].addr || stat.real_cnt != 1) {
303 nr_failed++;
304 pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
305 prefix, test_items[i].name,
306 stat.real_cnt, stat.addr, test_items[i].addr);
307 }
308 }
309
310 prefix = "kallsyms_on_each_match_symbol() for";
311 for (i = 0; i < ARRAY_SIZE(test_items); i++) {
312 memset(&stat, 0, sizeof(stat));
313 stat.max = INT_MAX;
314 stat.name = test_items[i].name;
315 kallsyms_on_each_match_symbol(match_symbol, test_items[i].name, &stat);
316 if (stat.addr != test_items[i].addr || stat.real_cnt != 1) {
317 nr_failed++;
318 pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
319 prefix, test_items[i].name,
320 stat.real_cnt, stat.addr, test_items[i].addr);
321 }
322 }
323
324 if (nr_failed)
325 return -ESRCH;
326
327 for (i = 0; i < kallsyms_num_syms; i++) {
328 addr = kallsyms_sym_address(i);
329 if (!is_ksym_addr(addr))
330 continue;
331
332 ret = lookup_symbol_name(addr, namebuf);
333 if (unlikely(ret)) {
334 namebuf[0] = 0;
335 goto failed;
336 }
337
338 /*
339 * The first '.' may be the initial letter, in which case the
340 * entire symbol name will be truncated to an empty string in
341 * cleanup_symbol_name(). Do not test these symbols.
342 *
343 * For example:
344 * cat /proc/kallsyms | awk '{print $3}' | grep -E "^\." | head
345 * .E_read_words
346 * .E_leading_bytes
347 * .E_trailing_bytes
348 * .E_write_words
349 * .E_copy
350 * .str.292.llvm.12122243386960820698
351 * .str.24.llvm.12122243386960820698
352 * .str.29.llvm.12122243386960820698
353 * .str.75.llvm.12122243386960820698
354 * .str.99.llvm.12122243386960820698
355 */
356 if (IS_ENABLED(CONFIG_LTO_CLANG) && !namebuf[0])
357 continue;
358
359 lookup_addr = kallsyms_lookup_name(namebuf);
360
361 memset(&stat, 0, sizeof(stat));
362 stat.max = INT_MAX;
363 kallsyms_on_each_match_symbol(match_symbol, namebuf, &stat);
364
365 /*
366 * kallsyms_on_each_symbol() is too slow, randomly select some
367 * symbols for test.
368 */
369 if (i >= next) {
370 memset(&stat2, 0, sizeof(stat2));
371 stat2.max = INT_MAX;
372 stat2.name = namebuf;
373 kallsyms_on_each_symbol(find_symbol, &stat2);
374
375 /*
376 * kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol()
377 * need to get the same traversal result.
378 */
379 if (stat.addr != stat2.addr ||
380 stat.real_cnt != stat2.real_cnt ||
381 memcmp(stat.addrs, stat2.addrs,
382 stat.save_cnt * sizeof(stat.addrs[0])))
383 goto failed;
384
385 /*
386 * The average of random increments is 128, that is, one of
387 * them is tested every 128 symbols.
388 */
389 get_random_bytes(&rand, sizeof(rand));
390 next = i + (rand & 0xff) + 1;
391 }
392
393 /* Need to be found at least once */
394 if (!stat.real_cnt)
395 goto failed;
396
397 /*
398 * kallsyms_lookup_name() returns the address of the first
399 * symbol found and cannot be NULL.
400 */
401 if (!lookup_addr || lookup_addr != stat.addrs[0])
402 goto failed;
403
404 /*
405 * If the addresses of all matching symbols are recorded, the
406 * target address needs to be exist.
407 */
408 if (stat.real_cnt <= MAX_NUM_OF_RECORDS) {
409 for (j = 0; j < stat.save_cnt; j++) {
410 if (stat.addrs[j] == addr)
411 break;
412 }
413
414 if (j == stat.save_cnt)
415 goto failed;
416 }
417 }
418
419 return 0;
420
421 failed:
422 pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr);
423 return -ESRCH;
> 424 }
425
--
0-DAY CI Kernel Test Service
https://01.org/lkp
Hi Zhen,
Thank you for the patch! Yet something to improve:
[auto build test ERROR on masahiroy-kbuild/for-next]
[also build test ERROR on linus/master v6.1-rc1 next-20221018]
[cannot apply to mcgrof/modules-next]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
base: https://git.kernel.org/pub/scm/linux/kernel/git/masahiroy/linux-kbuild.git for-next
patch link: https://lore.kernel.org/r/20221017064950.2038-12-thunder.leizhen%40huawei.com
patch subject: [PATCH v7 11/11] kallsyms: Add self-test facility
config: mips-allyesconfig
compiler: mips-linux-gcc (GCC) 12.1.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
git checkout 3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=mips SHELL=/bin/bash
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <[email protected]>
All errors (new ones prefixed by >>):
arch/mips/kernel/head.o: in function `kernel_entry':
(.ref.text+0xac): relocation truncated to fit: R_MIPS_26 against `start_kernel'
init/main.o: in function `set_reset_devices':
main.c:(.init.text+0x20): relocation truncated to fit: R_MIPS_26 against `_mcount'
main.c:(.init.text+0x30): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
init/main.o: in function `debug_kernel':
main.c:(.init.text+0xa4): relocation truncated to fit: R_MIPS_26 against `_mcount'
main.c:(.init.text+0xb4): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
init/main.o: in function `quiet_kernel':
main.c:(.init.text+0x128): relocation truncated to fit: R_MIPS_26 against `_mcount'
main.c:(.init.text+0x138): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
init/main.o: in function `warn_bootconfig':
main.c:(.init.text+0x1ac): relocation truncated to fit: R_MIPS_26 against `_mcount'
main.c:(.init.text+0x1bc): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
init/main.o: in function `init_setup':
main.c:(.init.text+0x234): relocation truncated to fit: R_MIPS_26 against `_mcount'
main.c:(.init.text+0x254): additional relocation overflows omitted from the output
mips-linux-ld: kernel/kallsyms_selftest.o: in function `test_perf_kallsyms_lookup_name':
>> kallsyms_selftest.c:(.text.unlikely.test_perf_kallsyms_lookup_name+0x100): undefined reference to `__udivdi3'
--
0-DAY CI Kernel Test Service
https://01.org/lkp
On 2022/10/18 16:21, kernel test robot wrote:
> Hi Zhen,
>
> Thank you for the patch! Perhaps something to improve:
>
> [auto build test WARNING on masahiroy-kbuild/for-next]
> [also build test WARNING on linus/master v6.1-rc1 next-20221018]
> [cannot apply to mcgrof/modules-next]
> [If your patch is applied to the wrong git tree, kindly drop us a note.
> And when submitting patch, we suggest to use '--base' as documented in
> https://git-scm.com/docs/git-format-patch#_base_tree_information]
>
> url: https://github.com/intel-lab-lkp/linux/commits/Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
> base: https://git.kernel.org/pub/scm/linux/kernel/git/masahiroy/linux-kbuild.git for-next
> patch link: https://lore.kernel.org/r/20221017064950.2038-12-thunder.leizhen%40huawei.com
> patch subject: [PATCH v7 11/11] kallsyms: Add self-test facility
> config: sh-allmodconfig
> compiler: sh4-linux-gcc (GCC) 12.1.0
> reproduce (this is a W=1 build):
> wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
> chmod +x ~/bin/make.cross
> # https://github.com/intel-lab-lkp/linux/commit/3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
> git remote add linux-review https://github.com/intel-lab-lkp/linux
> git fetch --no-tags linux-review Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
> git checkout 3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
> # save the config file
> mkdir build_dir && cp config build_dir/.config
> COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=sh SHELL=/bin/bash
>
> If you fix the issue, kindly add following tag where applicable
> | Reported-by: kernel test robot <[email protected]>
>
> All warnings (new ones prefixed by >>):
>
> kernel/kallsyms_selftest.c:67:5: warning: no previous prototype for 'test_func' [-Wmissing-prototypes]
> 67 | int test_func(void)
> | ^~~~~~~~~
> kernel/kallsyms_selftest.c:72:12: warning: no previous prototype for 'test_func_weak' [-Wmissing-prototypes]
> 72 | __weak int test_func_weak(void)
> | ^~~~~~~~~~~~~~
> kernel/kallsyms_selftest.c: In function 'test_kallsyms_basic_function':
>>> kernel/kallsyms_selftest.c:424:1: warning: the frame size of 1124 bytes is larger than 1024 bytes [-Wframe-larger-than=]
> 424 | }
> | ^
OK, thanks. These warnings are minor. I will fix them in the next version after collecting review comments.
>
>
> vim +424 kernel/kallsyms_selftest.c
>
> 275
> 276 static int test_kallsyms_basic_function(void)
> 277 {
> 278 int i, j, ret;
> 279 int next = 0, nr_failed = 0;
> 280 char *prefix;
> 281 unsigned short rand;
> 282 unsigned long addr, lookup_addr;
> 283 char namebuf[KSYM_NAME_LEN];
> 284 struct test_stat stat, stat2;
> 285
> 286 prefix = "kallsyms_lookup_name() for";
> 287 for (i = 0; i < ARRAY_SIZE(test_items); i++) {
> 288 addr = kallsyms_lookup_name(test_items[i].name);
> 289 if (addr != test_items[i].addr) {
> 290 nr_failed++;
> 291 pr_info("%s %s failed: addr=%lx, expect %lx\n",
> 292 prefix, test_items[i].name, addr, test_items[i].addr);
> 293 }
> 294 }
> 295
> 296 prefix = "kallsyms_on_each_symbol() for";
> 297 for (i = 0; i < ARRAY_SIZE(test_items); i++) {
> 298 memset(&stat, 0, sizeof(stat));
> 299 stat.max = INT_MAX;
> 300 stat.name = test_items[i].name;
> 301 kallsyms_on_each_symbol(find_symbol, &stat);
> 302 if (stat.addr != test_items[i].addr || stat.real_cnt != 1) {
> 303 nr_failed++;
> 304 pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
> 305 prefix, test_items[i].name,
> 306 stat.real_cnt, stat.addr, test_items[i].addr);
> 307 }
> 308 }
> 309
> 310 prefix = "kallsyms_on_each_match_symbol() for";
> 311 for (i = 0; i < ARRAY_SIZE(test_items); i++) {
> 312 memset(&stat, 0, sizeof(stat));
> 313 stat.max = INT_MAX;
> 314 stat.name = test_items[i].name;
> 315 kallsyms_on_each_match_symbol(match_symbol, test_items[i].name, &stat);
> 316 if (stat.addr != test_items[i].addr || stat.real_cnt != 1) {
> 317 nr_failed++;
> 318 pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
> 319 prefix, test_items[i].name,
> 320 stat.real_cnt, stat.addr, test_items[i].addr);
> 321 }
> 322 }
> 323
> 324 if (nr_failed)
> 325 return -ESRCH;
> 326
> 327 for (i = 0; i < kallsyms_num_syms; i++) {
> 328 addr = kallsyms_sym_address(i);
> 329 if (!is_ksym_addr(addr))
> 330 continue;
> 331
> 332 ret = lookup_symbol_name(addr, namebuf);
> 333 if (unlikely(ret)) {
> 334 namebuf[0] = 0;
> 335 goto failed;
> 336 }
> 337
> 338 /*
> 339 * The first '.' may be the initial letter, in which case the
> 340 * entire symbol name will be truncated to an empty string in
> 341 * cleanup_symbol_name(). Do not test these symbols.
> 342 *
> 343 * For example:
> 344 * cat /proc/kallsyms | awk '{print $3}' | grep -E "^\." | head
> 345 * .E_read_words
> 346 * .E_leading_bytes
> 347 * .E_trailing_bytes
> 348 * .E_write_words
> 349 * .E_copy
> 350 * .str.292.llvm.12122243386960820698
> 351 * .str.24.llvm.12122243386960820698
> 352 * .str.29.llvm.12122243386960820698
> 353 * .str.75.llvm.12122243386960820698
> 354 * .str.99.llvm.12122243386960820698
> 355 */
> 356 if (IS_ENABLED(CONFIG_LTO_CLANG) && !namebuf[0])
> 357 continue;
> 358
> 359 lookup_addr = kallsyms_lookup_name(namebuf);
> 360
> 361 memset(&stat, 0, sizeof(stat));
> 362 stat.max = INT_MAX;
> 363 kallsyms_on_each_match_symbol(match_symbol, namebuf, &stat);
> 364
> 365 /*
> 366 * kallsyms_on_each_symbol() is too slow, randomly select some
> 367 * symbols for test.
> 368 */
> 369 if (i >= next) {
> 370 memset(&stat2, 0, sizeof(stat2));
> 371 stat2.max = INT_MAX;
> 372 stat2.name = namebuf;
> 373 kallsyms_on_each_symbol(find_symbol, &stat2);
> 374
> 375 /*
> 376 * kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol()
> 377 * need to get the same traversal result.
> 378 */
> 379 if (stat.addr != stat2.addr ||
> 380 stat.real_cnt != stat2.real_cnt ||
> 381 memcmp(stat.addrs, stat2.addrs,
> 382 stat.save_cnt * sizeof(stat.addrs[0])))
> 383 goto failed;
> 384
> 385 /*
> 386 * The average of random increments is 128, that is, one of
> 387 * them is tested every 128 symbols.
> 388 */
> 389 get_random_bytes(&rand, sizeof(rand));
> 390 next = i + (rand & 0xff) + 1;
> 391 }
> 392
> 393 /* Need to be found at least once */
> 394 if (!stat.real_cnt)
> 395 goto failed;
> 396
> 397 /*
> 398 * kallsyms_lookup_name() returns the address of the first
> 399 * symbol found and cannot be NULL.
> 400 */
> 401 if (!lookup_addr || lookup_addr != stat.addrs[0])
> 402 goto failed;
> 403
> 404 /*
> 405 * If the addresses of all matching symbols are recorded, the
> 406 * target address needs to be exist.
> 407 */
> 408 if (stat.real_cnt <= MAX_NUM_OF_RECORDS) {
> 409 for (j = 0; j < stat.save_cnt; j++) {
> 410 if (stat.addrs[j] == addr)
> 411 break;
> 412 }
> 413
> 414 if (j == stat.save_cnt)
> 415 goto failed;
> 416 }
> 417 }
> 418
> 419 return 0;
> 420
> 421 failed:
> 422 pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr);
> 423 return -ESRCH;
> > 424 }
> 425
>
--
Regards,
Zhen Lei
On 2022/10/18 17:32, kernel test robot wrote:
> Hi Zhen,
>
> Thank you for the patch! Yet something to improve:
>
> [auto build test ERROR on masahiroy-kbuild/for-next]
> [also build test ERROR on linus/master v6.1-rc1 next-20221018]
> [cannot apply to mcgrof/modules-next]
> [If your patch is applied to the wrong git tree, kindly drop us a note.
> And when submitting patch, we suggest to use '--base' as documented in
> https://git-scm.com/docs/git-format-patch#_base_tree_information]
>
> url: https://github.com/intel-lab-lkp/linux/commits/Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
> base: https://git.kernel.org/pub/scm/linux/kernel/git/masahiroy/linux-kbuild.git for-next
> patch link: https://lore.kernel.org/r/20221017064950.2038-12-thunder.leizhen%40huawei.com
> patch subject: [PATCH v7 11/11] kallsyms: Add self-test facility
> config: mips-allyesconfig
> compiler: mips-linux-gcc (GCC) 12.1.0
> reproduce (this is a W=1 build):
> wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
> chmod +x ~/bin/make.cross
> # https://github.com/intel-lab-lkp/linux/commit/3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
> git remote add linux-review https://github.com/intel-lab-lkp/linux
> git fetch --no-tags linux-review Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
> git checkout 3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
> # save the config file
> mkdir build_dir && cp config build_dir/.config
> COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=mips SHELL=/bin/bash
>
> If you fix the issue, kindly add following tag where applicable
> | Reported-by: kernel test robot <[email protected]>>
> All errors (new ones prefixed by >>):
>
> arch/mips/kernel/head.o: in function `kernel_entry':
> (.ref.text+0xac): relocation truncated to fit: R_MIPS_26 against `start_kernel'
> init/main.o: in function `set_reset_devices':
> main.c:(.init.text+0x20): relocation truncated to fit: R_MIPS_26 against `_mcount'
> main.c:(.init.text+0x30): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
> init/main.o: in function `debug_kernel':
> main.c:(.init.text+0xa4): relocation truncated to fit: R_MIPS_26 against `_mcount'
> main.c:(.init.text+0xb4): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
> init/main.o: in function `quiet_kernel':
> main.c:(.init.text+0x128): relocation truncated to fit: R_MIPS_26 against `_mcount'
> main.c:(.init.text+0x138): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
> init/main.o: in function `warn_bootconfig':
> main.c:(.init.text+0x1ac): relocation truncated to fit: R_MIPS_26 against `_mcount'
> main.c:(.init.text+0x1bc): relocation truncated to fit: R_MIPS_26 against `__sanitizer_cov_trace_pc'
> init/main.o: in function `init_setup':
> main.c:(.init.text+0x234): relocation truncated to fit: R_MIPS_26 against `_mcount'
> main.c:(.init.text+0x254): additional relocation overflows omitted from the output
> mips-linux-ld: kernel/kallsyms_selftest.o: in function `test_perf_kallsyms_lookup_name':
>>> kallsyms_selftest.c:(.text.unlikely.test_perf_kallsyms_lookup_name+0x100): undefined reference to `__udivdi3'
OK, thanks. I will fix it in the next version.
>
--
Regards,
Zhen Lei
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?
Luis
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.
>
> Luis
> .
>
--
Regards,
Zhen Lei
Hi Zhen,
Thank you for the patch! Yet something to improve:
[auto build test ERROR on masahiroy-kbuild/for-next]
[also build test ERROR on linus/master v6.1-rc1 next-20221020]
[cannot apply to mcgrof/modules-next]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
base: https://git.kernel.org/pub/scm/linux/kernel/git/masahiroy/linux-kbuild.git for-next
patch link: https://lore.kernel.org/r/20221017064950.2038-12-thunder.leizhen%40huawei.com
patch subject: [PATCH v7 11/11] kallsyms: Add self-test facility
config: i386-allyesconfig
compiler: gcc-11 (Debian 11.3.0-8) 11.3.0
reproduce (this is a W=1 build):
# https://github.com/intel-lab-lkp/linux/commit/3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Zhen-Lei/kallsyms-Optimizes-the-performance-of-lookup-symbols/20221017-145455
git checkout 3f5fc7fa1f657df865ef14b2d24f837a7cc079c9
# save the config file
mkdir build_dir && cp config build_dir/.config
make W=1 O=build_dir ARCH=i386 SHELL=/bin/bash
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <[email protected]>
All errors (new ones prefixed by >>):
ld: kernel/kallsyms_selftest.o: in function `test_perf_kallsyms_lookup_name':
>> kallsyms_selftest.c:(.text.unlikely+0x5db): undefined reference to `__udivdi3'
--
0-DAY CI Kernel Test Service
https://01.org/lkp
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
On 2022/10/26 1:53, Luis Chamberlain wrote:
> 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?
I'm not the original author, and I can only answer now based on my understanding. Maybe
the original author didn't think of the hash method, or he has weighed it out.
Hash is a good solution if only performance is required and memory overhead is not
considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
Because I don't know what hash algorithm will be used, the cost of generating the
hash value corresponding to the symbol name is unknown now. But I think it's gonna
be small. But it definitely needs a simpler algorithm, the tool needs to implement
the same hash algorithm.
If the hash is not very uniform or ARRAY_SIZE(hashtable) is small, then my current
approach still makes sense. So maybe hash can be deferred to the next phase of
improvement.
>
> Luis
> .
>
--
Regards,
Zhen Lei
On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
> On 2022/10/26 1:53, Luis Chamberlain wrote:
> > This answers how we don't use a hash table, the question was *should* we
> > use one?
>
> I'm not the original author, and I can only answer now based on my understanding. Maybe
> the original author didn't think of the hash method, or he has weighed it out.
>
> Hash is a good solution if only performance is required and memory overhead is not
> considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
> 4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
>
> Because I don't know what hash algorithm will be used, the cost of generating the
> hash value corresponding to the symbol name is unknown now. But I think it's gonna
> be small. But it definitely needs a simpler algorithm, the tool needs to implement
> the same hash algorithm.
For instance, you can look at evaluating if alloc_large_system_hash() would help.
Luis
On 2022/10/27 3:03, Luis Chamberlain wrote:
> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
>> On 2022/10/26 1:53, Luis Chamberlain wrote:
>>> This answers how we don't use a hash table, the question was *should* we
>>> use one?
>>
>> I'm not the original author, and I can only answer now based on my understanding. Maybe
>> the original author didn't think of the hash method, or he has weighed it out.
>>
>> Hash is a good solution if only performance is required and memory overhead is not
>> considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
>> 4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
>>
>> Because I don't know what hash algorithm will be used, the cost of generating the
>> hash value corresponding to the symbol name is unknown now. But I think it's gonna
>> be small. But it definitely needs a simpler algorithm, the tool needs to implement
>> the same hash algorithm.
>
> For instance, you can look at evaluating if alloc_large_system_hash() would help.
OK, I found the right hash function. In this way, the tool does not need to consider
the byte order.
include/linux/stringhash.h
/*
* Version 1: one byte at a time. Example of use:
*
* unsigned long hash = init_name_hash;
* while (*p)
* hash = partial_name_hash(tolower(*p++), hash);
* hash = end_name_hash(hash);
>
> Luis
> .
>
--
Regards,
Zhen Lei
On 2022/10/27 11:26, Leizhen (ThunderTown) wrote:
>
>
> On 2022/10/27 3:03, Luis Chamberlain wrote:
>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
>>>> This answers how we don't use a hash table, the question was *should* we
>>>> use one?
>>>
>>> I'm not the original author, and I can only answer now based on my understanding. Maybe
>>> the original author didn't think of the hash method, or he has weighed it out.
>>>
>>> Hash is a good solution if only performance is required and memory overhead is not
>>> considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
>>> 4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
Sorry, 1-2 million ==> 0.1~0.2 million
>>>
>>> Because I don't know what hash algorithm will be used, the cost of generating the
>>> hash value corresponding to the symbol name is unknown now. But I think it's gonna
>>> be small. But it definitely needs a simpler algorithm, the tool needs to implement
>>> the same hash algorithm.
>>
>> For instance, you can look at evaluating if alloc_large_system_hash() would help.
>
> OK, I found the right hash function. In this way, the tool does not need to consider
> the byte order.
https://en.wikipedia.org/wiki/Jenkins_hash_function
Let's go with jenkins_one_at_a_time_hash(), which looks simpler and doesn't even
have to think about sizeof(long). It seems to be closest to our current needs.
uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
size_t i = 0;
uint32_t hash = 0;
while (i != length) {
hash += key[i++];
hash += hash << 10;
hash ^= hash >> 6;
}
hash += hash << 3;
hash ^= hash >> 11;
hash += hash << 15;
return hash;
}
>
> include/linux/stringhash.h
>
> /*
> * Version 1: one byte at a time. Example of use:
> *
> * unsigned long hash = init_name_hash;
> * while (*p)
> * hash = partial_name_hash(tolower(*p++), hash);
> * hash = end_name_hash(hash);
>
>
>>
>> Luis
>> .
>>
>
--
Regards,
Zhen Lei
On 2022/10/27 14:27, Leizhen (ThunderTown) wrote:
>
>
> On 2022/10/27 11:26, Leizhen (ThunderTown) wrote:
>>
>>
>> On 2022/10/27 3:03, Luis Chamberlain wrote:
>>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
>>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
>>>>> This answers how we don't use a hash table, the question was *should* we
>>>>> use one?
>>>>
>>>> I'm not the original author, and I can only answer now based on my understanding. Maybe
>>>> the original author didn't think of the hash method, or he has weighed it out.
>>>>
>>>> Hash is a good solution if only performance is required and memory overhead is not
>>>> considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
>>>> 4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
>
> Sorry, 1-2 million ==> 0.1~0.2 million
>
>>>>
>>>> Because I don't know what hash algorithm will be used, the cost of generating the
>>>> hash value corresponding to the symbol name is unknown now. But I think it's gonna
>>>> be small. But it definitely needs a simpler algorithm, the tool needs to implement
>>>> the same hash algorithm.
>>>
>>> For instance, you can look at evaluating if alloc_large_system_hash() would help.
>>
The following three hash algorithms are compared. The kernel is compiled by defconfig
on arm64.
|---------------------------------------------------------------------------------------|
| | hash &= HASH_TABLE_SIZE - 1 |
| | number of conflicts >= 1000 |
|---------------------------------------------------------------------------------------|
| ARRAY_SIZE(hash_table) | crc16 | jhash_one_at_a_time | string hash_32 |
|---------------------------------------------------------------------------------------|
| | 345b: 3905 | 0d40: 1013 | 4a4c: 6548 |
| | 35bb: 1016 | 35ce: 6549 | 883a: 1015 |
| 0x10000 | 385b: 6548 | 4440: 19126 | d05f: 19129 |
| | f0ba: 19127 | 7ebe: 3916 | ecda: 3903 |
|---------------------------------------------------------------------------------------|
| | 0ba: 19168 | 440: 19165 | 05f: 19170 |
| | 45b: 3955 | 5ce: 6577 | 83a: 1066 |
| 0x1000 | 5bb: 1069 | d40: 1052 | a4c: 6609 |
| | 85b: 6582 | ebe: 3938 | cda: 3924 |
|---------------------------------------------------------------------------------------|
Based on the above test results, I conclude that:
1. For the worst-case scenario, the three algorithms are not much different. But the kernel
only implements crc16 and string hash_32. The latter is not processed byte-by-byte, so
it is coupled with byte order and sizeof(long). So crc16 is the best choice.
2. For the worst-case scenario, there are almost 19K strings are mapped to the same hash
value，just over 1/10 of the total. And with my current compression-then-comparison
approach, it's 25-30 times faster. So there's still a need for my current approach, and
they can be combined.
if (nr_conflicts(key) >= CONST_N) {
newname = compress(name);
for_each_name_in_slot(key): compare(new_name)
} else {
for_each_name_in_slot(key): compare(name)
}
Above CONST_N can be roughly calculated:
time_of_compress(name) + N * time_of_compare(new_name) <= N * time_of_compare(name)
3. For the worst-case scenario, there is no obvious difference between ARRAY_SIZE(hash_table)
0x10000 and 0x1000. So ARRAY_SIZE(hash_table)=0x1000 is enough.
Statistic information:
|------------------------------------------------------|
| nr_conflicts(key) | ARRAY_SIZE(hash_table) |
|------------------------------------------------------|
| <= ? | 0x1000 | 0x10000 |
|------------------------------------------------------|
| 0 | 0 | 7821 |
| 20 | 19 | 57375 |
| 40 | 2419 | 124 |
| 60 | 1343 | 70 |
| 80 | 149 | 73 |
| 100 | 38 | 49 |
| 200 | 108 | 16 |
| 400 | 14 | 2 |
| 600 | 2 | 2 |
| 800 | 0 | 0 |
| 1000 | 0 | 0 |
| 100000 | 4 | 4 |
|------------------------------------------------------|
Also, I re-calculated:
Using hash will increase the memory size by up to "6 * kallsyms_num_syms + 4 * ARRAY_SIZE(hashtable)"
|---- What I said earlier was 4
The increased size is close to 1 MB if CONFIG_KALLSYMS_ALL=y.
Hi, Luis:
For the reasons of the above-mentioned second conclusion. And except for patches 4-6,
even if only the hash method is used, other patches and option "--lto-clang" in patch 6/11
are also needed. If you don't mind, I'd like to use hash at the next stage. The current
patch set is already huge.
>> OK, I found the right hash function. In this way, the tool does not need to consider
>> the byte order.
>
> https://en.wikipedia.org/wiki/Jenkins_hash_function
>
> Let's go with jenkins_one_at_a_time_hash(), which looks simpler and doesn't even
> have to think about sizeof(long). It seems to be closest to our current needs.
>
> uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
> size_t i = 0;
> uint32_t hash = 0;
>
> while (i != length) {
> hash += key[i++];
> hash += hash << 10;
> hash ^= hash >> 6;
> }
> hash += hash << 3;
> hash ^= hash >> 11;
> hash += hash << 15;
>
> return hash;
> }
>
>>
>> include/linux/stringhash.h
>>
>> /*
>> * Version 1: one byte at a time. Example of use:
>> *
>> * unsigned long hash = init_name_hash;
>> * while (*p)
>> * hash = partial_name_hash(tolower(*p++), hash);
>> * hash = end_name_hash(hash);
>>
>>
>>>
>>> Luis
>>> .
>>>
>>
>
--
Regards,
Zhen Lei
> >> On 2022/10/27 3:03, Luis Chamberlain wrote:
> >>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
> >>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
> >>>>> This answers how we don't use a hash table, the question was *should* we
> >>>>> use one?
(Probably brainfart) thought...
Is the current table (effectively) a sorted list of strings?
So the lookup is a binary chop - so O(log(n)).
But your hashes are having 'trouble' stopping one chain
being very long?
So a linear search of that hash chain is slow.
In fact that sort of hashed lookup in O(n).
What if the symbols were sorted by hash then name?
(Without putting the hash into each entry.)
Then the code could do a binary chop search over
the symbols with the same hash value.
The additional data is then an array of symbol numbers
indexed by the hash - 32 bits for each bucket.
If the hash table has 0x1000 entries it saves 12 compares.
(All of which are likely to be data cache misses.)
If you add the hash to each table entry then you can do
a binary chop search for the hash itself.
While this is the same search as is done for the strings
the comparison (just a number) will be faster than a
string compare.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
On 2022/10/29 20:49, David Laight wrote:
>>>> On 2022/10/27 3:03, Luis Chamberlain wrote:
>>>>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
>>>>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
>>>>>>> This answers how we don't use a hash table, the question was *should* we
>>>>>>> use one?
>
> (Probably brainfart) thought...
>
> Is the current table (effectively) a sorted list of strings?
> So the lookup is a binary chop - so O(log(n)).
Currently not sorted.
>
> But your hashes are having 'trouble' stopping one chain
> being very long?
> So a linear search of that hash chain is slow.
> In fact that sort of hashed lookup in O(n).
You've analyzed it very well. The hash method is not good for sorting names
and then searching in binary mode. I figured it out when I was working on
the design these days.
Current Implementation:
---------------------------------------
| idx | addresses | markers | names |
---------------------------------------
| 0 | addr0 | | name0 |
| 1 | addr1 | | name1 |
| ... | addrx | [0] | namex |
| 255 | addrx | | name255|
---------------------------------------
| 256 | addr256 | | name256|
| ... | addrx | [1] | namex |
| 511 | addr511 | | name511|
---------------------------------------
markers[0] = offset_of(name0)
markers[1] = offset_of(name256)
1. Find name by address
binary search addresses[], get idx, traverse names[] from markers[idx>>8] to markers[(idx>>8) + 1], return name
2. Find address by name
traverse names[], get idx, return addresses[idx]
Hash Implementation:
Add two new arrays: hash_table[] and names_offsets[]
-----------------------------------------------------------------
| key | hash_table | names_offsets |
|---------------------------------------------------------------|
| 0 | names_offsets[key=0] | offsets of all names with key=0 |
| 1 | names_offsets[key=1] | offsets of all names with key=1 |
| ... | ... | offsets of all names with key=k |
|---------------------------------------------------------------|
hash_table[0] = 0
hash_table[1] = hash_table[0] + sizeof(names_offsets[0]) * number_of_names(key=0)
hash_table[2] = hash_table[1] + sizeof(names_offsets[0]) * number_of_names(key=1)
1. Find address by name
hash name, get key, traverse names_offsets[] from index=hash_table[key] to
index=hash_table[key+1], get the offset of name in names[]. binary search markers[],
get index, then traverse names[] from markers[index] to markers[index + 1], until
match the offset of name, return addresses[idx].
2. Find address by name
No change.
Sorted names Implementation:
Add two new arrays: offsets_of_addr_to_name[] and offsets_of_name[]
offsets_of_addr_to_name[i] = offset of name i in names[]
offsets_of_name[i] = offset of sorted name i in names[]
1. Find name by address
binary search addresses[], get idx, return names[offsets_of_addr_to_name[idx]]
2. Find address by name
binary search offsets_of_name[], get idx, return addresses[idx]
>
> What if the symbols were sorted by hash then name?
> (Without putting the hash into each entry.)
> Then the code could do a binary chop search over
> the symbols with the same hash value.
> The additional data is then an array of symbol numbers
> indexed by the hash - 32 bits for each bucket.
>
> If the hash table has 0x1000 entries it saves 12 compares.
> (All of which are likely to be data cache misses.)
>
> If you add the hash to each table entry then you can do
> a binary chop search for the hash itself.
> While this is the same search as is done for the strings
> the comparison (just a number) will be faster than a
> string compare.
>
> David
>
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
>
--
Regards,
Zhen Lei
On 2022/10/29 16:10, Leizhen (ThunderTown) wrote:
>
>
> On 2022/10/27 14:27, Leizhen (ThunderTown) wrote:
>>
>>
>> On 2022/10/27 11:26, Leizhen (ThunderTown) wrote:
>>>
>>>
>>> On 2022/10/27 3:03, Luis Chamberlain wrote:
>>>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
>>>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
>>>>>> This answers how we don't use a hash table, the question was *should* we
>>>>>> use one?
>>>>>
>>>>> I'm not the original author, and I can only answer now based on my understanding. Maybe
>>>>> the original author didn't think of the hash method, or he has weighed it out.
>>>>>
>>>>> Hash is a good solution if only performance is required and memory overhead is not
>>>>> considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
>>>>> 4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
>>
>> Sorry, 1-2 million ==> 0.1~0.2 million
>>
>>>>>
>>>>> Because I don't know what hash algorithm will be used, the cost of generating the
>>>>> hash value corresponding to the symbol name is unknown now. But I think it's gonna
>>>>> be small. But it definitely needs a simpler algorithm, the tool needs to implement
>>>>> the same hash algorithm.
>>>>
>>>> For instance, you can look at evaluating if alloc_large_system_hash() would help.
>>>
>
> The following three hash algorithms are compared. The kernel is compiled by defconfig
> on arm64.
>
> |---------------------------------------------------------------------------------------|
> | | hash &= HASH_TABLE_SIZE - 1 |
> | | number of conflicts >= 1000 |
> |---------------------------------------------------------------------------------------|
> | ARRAY_SIZE(hash_table) | crc16 | jhash_one_at_a_time | string hash_32 |
> |---------------------------------------------------------------------------------------|
> | | 345b: 3905 | 0d40: 1013 | 4a4c: 6548 |
> | | 35bb: 1016 | 35ce: 6549 | 883a: 1015 |
> | 0x10000 | 385b: 6548 | 4440: 19126 | d05f: 19129 |
> | | f0ba: 19127 | 7ebe: 3916 | ecda: 3903 |
> |---------------------------------------------------------------------------------------|
> | | 0ba: 19168 | 440: 19165 | 05f: 19170 |
> | | 45b: 3955 | 5ce: 6577 | 83a: 1066 |
> | 0x1000 | 5bb: 1069 | d40: 1052 | a4c: 6609 |
> | | 85b: 6582 | ebe: 3938 | cda: 3924 |
> |---------------------------------------------------------------------------------------|
>
> Based on the above test results, I conclude that:
> 1. For the worst-case scenario, the three algorithms are not much different. But the kernel
> only implements crc16 and string hash_32. The latter is not processed byte-by-byte, so
> it is coupled with byte order and sizeof(long). So crc16 is the best choice.
> 2. For the worst-case scenario, there are almost 19K strings are mapped to the same hash
> value，just over 1/10 of the total. And with my current compression-then-comparison
> approach, it's 25-30 times faster. So there's still a need for my current approach, and
> they can be combined.
> if (nr_conflicts(key) >= CONST_N) {
> newname = compress(name);
> for_each_name_in_slot(key): compare(new_name)
> } else {
> for_each_name_in_slot(key): compare(name)
> }
>
> Above CONST_N can be roughly calculated:
> time_of_compress(name) + N * time_of_compare(new_name) <= N * time_of_compare(name)
> 3. For the worst-case scenario, there is no obvious difference between ARRAY_SIZE(hash_table)
> 0x10000 and 0x1000. So ARRAY_SIZE(hash_table)=0x1000 is enough.
> Statistic information:
> |------------------------------------------------------|
> | nr_conflicts(key) | ARRAY_SIZE(hash_table) |
> |------------------------------------------------------|
> | <= ? | 0x1000 | 0x10000 |
> |------------------------------------------------------|
> | 0 | 0 | 7821 |
> | 20 | 19 | 57375 |
> | 40 | 2419 | 124 |
> | 60 | 1343 | 70 |
> | 80 | 149 | 73 |
> | 100 | 38 | 49 |
> | 200 | 108 | 16 |
> | 400 | 14 | 2 |
> | 600 | 2 | 2 |
> | 800 | 0 | 0 |
> | 1000 | 0 | 0 |
> | 100000 | 4 | 4 |
> |------------------------------------------------------|
>
>
> Also, I re-calculated:
> Using hash will increase the memory size by up to "6 * kallsyms_num_syms + 4 * ARRAY_SIZE(hashtable)"
> |---- What I said earlier was 4
> The increased size is close to 1 MB if CONFIG_KALLSYMS_ALL=y.
>
> Hi, Luis:
> For the reasons of the above-mentioned second conclusion. And except for patches 4-6,
> even if only the hash method is used, other patches and option "--lto-clang" in patch 6/11
> are also needed. If you don't mind, I'd like to use hash at the next stage. The current
> patch set is already huge.
I just had an update in response to David Laight's email. The hash solution is like
a centrist. It doesn't seem very feasible.
Now, we need to make a decision. Choose one of the two:
1. Continue with my current approach. Improve the average performance of
kallsyms_lookup_name() by 20 to 30 times. The memory overhead is increased by:
arm64 (defconfig):
73.5KiB and 4.0% if CONFIG_KALLSYMS_ALL=y.
19.8KiB and 2.8% if CONFIG_KALLSYMS_ALL=n.
x86 (defconfig):
49.0KiB and 3.0% if CONFIG_KALLSYMS_ALL=y.
16.8KiB and 2.3% if CONFIG_KALLSYMS_ALL=n.
2. Sort names, binary search (The static function causes duplicate names. Additional work is required）
2^18=262144, only up to 18 symbol expansions and comparisons are required.
The performance is definitely excellent, although I haven't tested it yet.
The memory overhead is increased by: 6 * kallsyms_num_syms
arm64 (defconfig):
1MiB if CONFIG_KALLSYMS_ALL=y.
362KiB if CONFIG_KALLSYMS_ALL=n.
x86 (defconfig):
770KiB if CONFIG_KALLSYMS_ALL=y.
356KiB if CONFIG_KALLSYMS_ALL=n.
>
>
>>> OK, I found the right hash function. In this way, the tool does not need to consider
>>> the byte order.
>>
>> https://en.wikipedia.org/wiki/Jenkins_hash_function
>>
>> Let's go with jenkins_one_at_a_time_hash(), which looks simpler and doesn't even
>> have to think about sizeof(long). It seems to be closest to our current needs.
>>
>> uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
>> size_t i = 0;
>> uint32_t hash = 0;
>>
>> while (i != length) {
>> hash += key[i++];
>> hash += hash << 10;
>> hash ^= hash >> 6;
>> }
>> hash += hash << 3;
>> hash ^= hash >> 11;
>> hash += hash << 15;
>>
>> return hash;
>> }
>>
>>>
>>> include/linux/stringhash.h
>>>
>>> /*
>>> * Version 1: one byte at a time. Example of use:
>>> *
>>> * unsigned long hash = init_name_hash;
>>> * while (*p)
>>> * hash = partial_name_hash(tolower(*p++), hash);
>>> * hash = end_name_hash(hash);
>>>
>>>
>>>>
>>>> Luis
>>>> .
>>>>
>>>
>>
>
--
Regards,
Zhen Lei
On 2022/10/31 12:55, Leizhen (ThunderTown) wrote:
>
>
> On 2022/10/29 16:10, Leizhen (ThunderTown) wrote:
>>
>>
>> On 2022/10/27 14:27, Leizhen (ThunderTown) wrote:
>>>
>>>
>>> On 2022/10/27 11:26, Leizhen (ThunderTown) wrote:
>>>>
>>>>
>>>> On 2022/10/27 3:03, Luis Chamberlain wrote:
>>>>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
>>>>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
>>>>>>> This answers how we don't use a hash table, the question was *should* we
>>>>>>> use one?
>>>>>>
>>>>>> I'm not the original author, and I can only answer now based on my understanding. Maybe
>>>>>> the original author didn't think of the hash method, or he has weighed it out.
>>>>>>
>>>>>> Hash is a good solution if only performance is required and memory overhead is not
>>>>>> considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
>>>>>> 4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
>>>
>>> Sorry, 1-2 million ==> 0.1~0.2 million
>>>
>>>>>>
>>>>>> Because I don't know what hash algorithm will be used, the cost of generating the
>>>>>> hash value corresponding to the symbol name is unknown now. But I think it's gonna
>>>>>> be small. But it definitely needs a simpler algorithm, the tool needs to implement
>>>>>> the same hash algorithm.
>>>>>
>>>>> For instance, you can look at evaluating if alloc_large_system_hash() would help.
>>>>
>>
>> The following three hash algorithms are compared. The kernel is compiled by defconfig
>> on arm64.
>>
>> |---------------------------------------------------------------------------------------|
>> | | hash &= HASH_TABLE_SIZE - 1 |
>> | | number of conflicts >= 1000 |
>> |---------------------------------------------------------------------------------------|
>> | ARRAY_SIZE(hash_table) | crc16 | jhash_one_at_a_time | string hash_32 |
>> |---------------------------------------------------------------------------------------|
>> | | 345b: 3905 | 0d40: 1013 | 4a4c: 6548 |
>> | | 35bb: 1016 | 35ce: 6549 | 883a: 1015 |
>> | 0x10000 | 385b: 6548 | 4440: 19126 | d05f: 19129 |
>> | | f0ba: 19127 | 7ebe: 3916 | ecda: 3903 |
>> |---------------------------------------------------------------------------------------|
>> | | 0ba: 19168 | 440: 19165 | 05f: 19170 |
>> | | 45b: 3955 | 5ce: 6577 | 83a: 1066 |
>> | 0x1000 | 5bb: 1069 | d40: 1052 | a4c: 6609 |
>> | | 85b: 6582 | ebe: 3938 | cda: 3924 |
>> |---------------------------------------------------------------------------------------|
>>
>> Based on the above test results, I conclude that:
>> 1. For the worst-case scenario, the three algorithms are not much different. But the kernel
>> only implements crc16 and string hash_32. The latter is not processed byte-by-byte, so
>> it is coupled with byte order and sizeof(long). So crc16 is the best choice.
>> 2. For the worst-case scenario, there are almost 19K strings are mapped to the same hash
>> value，just over 1/10 of the total. And with my current compression-then-comparison
>> approach, it's 25-30 times faster. So there's still a need for my current approach, and
>> they can be combined.
>> if (nr_conflicts(key) >= CONST_N) {
>> newname = compress(name);
>> for_each_name_in_slot(key): compare(new_name)
>> } else {
>> for_each_name_in_slot(key): compare(name)
>> }
>>
>> Above CONST_N can be roughly calculated:
>> time_of_compress(name) + N * time_of_compare(new_name) <= N * time_of_compare(name)
>> 3. For the worst-case scenario, there is no obvious difference between ARRAY_SIZE(hash_table)
>> 0x10000 and 0x1000. So ARRAY_SIZE(hash_table)=0x1000 is enough.
>> Statistic information:
>> |------------------------------------------------------|
>> | nr_conflicts(key) | ARRAY_SIZE(hash_table) |
>> |------------------------------------------------------|
>> | <= ? | 0x1000 | 0x10000 |
>> |------------------------------------------------------|
>> | 0 | 0 | 7821 |
>> | 20 | 19 | 57375 |
>> | 40 | 2419 | 124 |
>> | 60 | 1343 | 70 |
>> | 80 | 149 | 73 |
>> | 100 | 38 | 49 |
>> | 200 | 108 | 16 |
>> | 400 | 14 | 2 |
>> | 600 | 2 | 2 |
>> | 800 | 0 | 0 |
>> | 1000 | 0 | 0 |
>> | 100000 | 4 | 4 |
>> |------------------------------------------------------|
>>
>>
>> Also, I re-calculated:
>> Using hash will increase the memory size by up to "6 * kallsyms_num_syms + 4 * ARRAY_SIZE(hashtable)"
>> |---- What I said earlier was 4
>> The increased size is close to 1 MB if CONFIG_KALLSYMS_ALL=y.
>>
>> Hi, Luis:
>> For the reasons of the above-mentioned second conclusion. And except for patches 4-6,
>> even if only the hash method is used, other patches and option "--lto-clang" in patch 6/11
>> are also needed. If you don't mind, I'd like to use hash at the next stage. The current
>> patch set is already huge.
>
> I just had an update in response to David Laight's email. The hash solution is like
> a centrist. It doesn't seem very feasible.
>
> Now, we need to make a decision. Choose one of the two:
> 1. Continue with my current approach. Improve the average performance of
> kallsyms_lookup_name() by 20 to 30 times. The memory overhead is increased by:
> arm64 (defconfig):
> 73.5KiB and 4.0% if CONFIG_KALLSYMS_ALL=y.
> 19.8KiB and 2.8% if CONFIG_KALLSYMS_ALL=n.
> x86 (defconfig):
> 49.0KiB and 3.0% if CONFIG_KALLSYMS_ALL=y.
> 16.8KiB and 2.3% if CONFIG_KALLSYMS_ALL=n.
> 2. Sort names, binary search (The static function causes duplicate names. Additional work is required）
> 2^18=262144, only up to 18 symbol expansions and comparisons are required.
> The performance is definitely excellent, although I haven't tested it yet.
> The memory overhead is increased by: 6 * kallsyms_num_syms
> arm64 (defconfig):
> 1MiB if CONFIG_KALLSYMS_ALL=y.
> 362KiB if CONFIG_KALLSYMS_ALL=n.
> x86 (defconfig):
> 770KiB if CONFIG_KALLSYMS_ALL=y.
> 356KiB if CONFIG_KALLSYMS_ALL=n.
>
Preliminary Test Results: (On Qemu arm64)
[ 73.049249] kallsyms_selftest: kallsyms_lookup_name() looked up 151880 symbols
[ 73.049331] kallsyms_selftest: The time spent on each symbol is (ns): min=1088, max=46848, avg=6629
>
>
>
>>
>>
>>>> OK, I found the right hash function. In this way, the tool does not need to consider
>>>> the byte order.
>>>
>>> https://en.wikipedia.org/wiki/Jenkins_hash_function
>>>
>>> Let's go with jenkins_one_at_a_time_hash(), which looks simpler and doesn't even
>>> have to think about sizeof(long). It seems to be closest to our current needs.
>>>
>>> uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
>>> size_t i = 0;
>>> uint32_t hash = 0;
>>>
>>> while (i != length) {
>>> hash += key[i++];
>>> hash += hash << 10;
>>> hash ^= hash >> 6;
>>> }
>>> hash += hash << 3;
>>> hash ^= hash >> 11;
>>> hash += hash << 15;
>>>
>>> return hash;
>>> }
>>>
>>>>
>>>> include/linux/stringhash.h
>>>>
>>>> /*
>>>> * Version 1: one byte at a time. Example of use:
>>>> *
>>>> * unsigned long hash = init_name_hash;
>>>> * while (*p)
>>>> * hash = partial_name_hash(tolower(*p++), hash);
>>>> * hash = end_name_hash(hash);
>>>>
>>>>
>>>>>
>>>>> Luis
>>>>> .
>>>>>
>>>>
>>>
>>
>
--
Regards,
Zhen Lei
On 2022/10/31 23:04, Leizhen (ThunderTown) wrote:
> Now, we need to make a decision. Choose one of the two:
> 1. Continue with my current approach. Improve the average performance of
> kallsyms_lookup_name() by 20 to 30 times. The memory overhead is increased by:
> arm64 (defconfig):
> 73.5KiB and 4.0% if CONFIG_KALLSYMS_ALL=y.
> 19.8KiB and 2.8% if CONFIG_KALLSYMS_ALL=n.
> x86 (defconfig):
> 49.0KiB and 3.0% if CONFIG_KALLSYMS_ALL=y.
> 16.8KiB and 2.3% if CONFIG_KALLSYMS_ALL=n.
> 2. Sort names, binary search (The static function causes duplicate names. Additional work is required）
> 2^18=262144, only up to 18 symbol expansions and comparisons are required.
> The performance is definitely excellent, although I haven't tested it yet.
> The memory overhead is increased by: 6 * kallsyms_num_syms
> arm64 (defconfig):
> 1MiB if CONFIG_KALLSYMS_ALL=y.
> 362KiB if CONFIG_KALLSYMS_ALL=n.
> x86 (defconfig):
> 770KiB if CONFIG_KALLSYMS_ALL=y.
> 356KiB if CONFIG_KALLSYMS_ALL=n.
Hi, Luis:
I've implemented v8 based on method 2(Sort names, binary search).
The memory overhead is increased by: 3 * kallsyms_num_syms.
kallsyms_offsets_of_names[] is not added in v8 because it does not help
much in performance improvement, so save (3 * kallsyms_num_syms) bytes.
For details about the performance data, please see the commit message.
--
Regards,
Zhen Lei