[PATCH v8 0/9] kallsyms: Optimizes the performance of lookup symbols

[PATCH v8 0/9] kallsyms: Optimizes the performance of lookup symbols

[Zhen Lei]

v7 --> v8:
Sort the symbols by name and implement kallsyms_lookup_name() using a binary
search. The performance is more than 20 times higher than that of v7. Of course,
the memory overhead is also extended to (3 * kallsyms_num_syms) bytes. Discard
all implementations of compression and then comparison in v7.

In addition, all sparse warnings about kallsyms_selftest.c are cleared.


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 (9):
  scripts/kallsyms: rename build_initial_tok_table()
  kallsyms: Improve the performance of kallsyms_lookup_name()
  kallsyms: Correctly sequence symbols when CONFIG_LTO_CLANG=y
  kallsyms: Reduce the memory occupied by kallsyms_seqs_of_names[]
  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          | 121 +++++++--
 kernel/kallsyms_internal.h |   1 +
 kernel/kallsyms_selftest.c | 485 +++++++++++++++++++++++++++++++++++++
 kernel/kallsyms_selftest.h |  13 +
 kernel/livepatch/core.c    |  31 ++-
 kernel/module/kallsyms.c   |  15 +-
 kernel/trace/ftrace.c      |   3 +-
 scripts/kallsyms.c         |  78 +++++-
 scripts/link-vmlinux.sh    |   4 +
 13 files changed, 743 insertions(+), 38 deletions(-)
 create mode 100644 kernel/kallsyms_selftest.c
 create mode 100644 kernel/kallsyms_selftest.h

-- 
2.25.1

[PATCH v8 1/9] scripts/kallsyms: rename build_initial_tok_table()

[Zhen Lei]

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 <thunder.leizhen@huawei.com>
Reviewed-by: Petr Mladek <pmladek@suse.com>
---
 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

[PATCH v8 2/9] kallsyms: Improve the performance of kallsyms_lookup_name()

[Zhen Lei]

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. It's O(n).

If we sort names in ascending order like addresses, we can also use
binary search. It's O(log(n)).

In order not to change the implementation of "/proc/kallsyms", the table
kallsyms_names[] is still stored in a one-to-one correspondence with the
address in ascending order.

Add array kallsyms_seqs_of_names[], it's indexed by the sequence number
of the sorted names, and the corresponding content is the sequence number
of the sorted addresses. For example:
Assume that the index of NameX in array kallsyms_seqs_of_names[] is 'i',
the content of kallsyms_seqs_of_names[i] is 'k', then the corresponding
address of NameX is kallsyms_addresses[k]. The offset in kallsyms_names[]
is get_symbol_offset(k).

Note that the memory usage will increase by (4 * kallsyms_num_syms)
bytes, the next two patches will reduce (1 * kallsyms_num_syms) bytes
and properly handle the case CONFIG_LTO_CLANG=y.

Performance test results: (x86)
Before:
min=234, max=10364402, avg=5206926
min=267, max=11168517, avg=5207587
After:
min=1016, max=90894, avg=7272
min=1014, max=93470, avg=7293

The average lookup performance of kallsyms_lookup_name() improved 715x.

Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 kernel/kallsyms.c          | 86 +++++++++++++++++++++++++++++++++-----
 kernel/kallsyms_internal.h |  1 +
 scripts/kallsyms.c         | 37 ++++++++++++++++
 3 files changed, 113 insertions(+), 11 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 60c20f301a6ba2c..ba351dfa109b6ac 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -187,26 +187,90 @@ static bool cleanup_symbol_name(char *s)
 	return false;
 }
 
+static int compare_symbol_name(const char *name, char *namebuf)
+{
+	int ret;
+
+	ret = strcmp(name, namebuf);
+	if (!ret)
+		return ret;
+
+	if (cleanup_symbol_name(namebuf) && !strcmp(name, namebuf))
+		return 0;
+
+	return ret;
+}
+
+static int kallsyms_lookup_names(const char *name,
+				 unsigned int *start,
+				 unsigned int *end)
+{
+	int ret;
+	int low, mid, high;
+	unsigned int seq, off;
+	char namebuf[KSYM_NAME_LEN];
+
+	low = 0;
+	high = kallsyms_num_syms - 1;
+
+	while (low <= high) {
+		mid = low + (high - low) / 2;
+		seq = kallsyms_seqs_of_names[mid];
+		off = get_symbol_offset(seq);
+		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
+		ret = compare_symbol_name(name, namebuf);
+		if (ret > 0)
+			low = mid + 1;
+		else if (ret < 0)
+			high = mid - 1;
+		else
+			break;
+	}
+
+	if (low > high)
+		return -ESRCH;
+
+	low = mid;
+	while (low) {
+		seq = kallsyms_seqs_of_names[low - 1];
+		off = get_symbol_offset(seq);
+		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
+		if (compare_symbol_name(name, namebuf))
+			break;
+		low--;
+	}
+	*start = low;
+
+	if (end) {
+		high = mid;
+		while (high < kallsyms_num_syms - 1) {
+			seq = kallsyms_seqs_of_names[high + 1];
+			off = get_symbol_offset(seq);
+			kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
+			if (compare_symbol_name(name, namebuf))
+				break;
+			high++;
+		}
+		*end = high;
+	}
+
+	return 0;
+}
+
 /* 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;
+	int ret;
+	unsigned int i;
 
 	/* Skip the search for empty string. */
 	if (!*name)
 		return 0;
 
-	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);
+	ret = kallsyms_lookup_names(name, &i, NULL);
+	if (!ret)
+		return kallsyms_sym_address(kallsyms_seqs_of_names[i]);
 
-		if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0)
-			return kallsyms_sym_address(i);
-	}
 	return module_kallsyms_lookup_name(name);
 }
 
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 2d0c6f2f0243a28..a04b7a5cb1e3eaf 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 int kallsyms_seqs_of_names[] __weak;
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index ab105bdde4efe4f..df2d93fb0e8d095 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -49,6 +49,7 @@ _Static_assert(
 struct sym_entry {
 	unsigned long long addr;
 	unsigned int len;
+	unsigned int seq;
 	unsigned int start_pos;
 	unsigned int percpu_absolute;
 	unsigned char sym[];
@@ -410,6 +411,35 @@ static int symbol_absolute(const struct sym_entry *s)
 	return s->percpu_absolute;
 }
 
+static int compare_names(const void *a, const void *b)
+{
+	int ret;
+	char sa_namebuf[KSYM_NAME_LEN];
+	char sb_namebuf[KSYM_NAME_LEN];
+	const struct sym_entry *sa = *(const struct sym_entry **)a;
+	const struct sym_entry *sb = *(const struct sym_entry **)b;
+
+	expand_symbol(sa->sym, sa->len, sa_namebuf);
+	expand_symbol(sb->sym, sb->len, sb_namebuf);
+	ret = strcmp(&sa_namebuf[1], &sb_namebuf[1]);
+	if (!ret) {
+		if (sa->addr > sb->addr)
+			return 1;
+		else if (sa->addr < sb->addr)
+			return -1;
+
+		/* keep old order */
+		return (int)(sa->seq - sb->seq);
+	}
+
+	return ret;
+}
+
+static void sort_symbols_by_name(void)
+{
+	qsort(table, table_cnt, sizeof(table[0]), compare_names);
+}
+
 static void write_src(void)
 {
 	unsigned int i, k, off;
@@ -495,6 +525,7 @@ static void write_src(void)
 	for (i = 0; i < table_cnt; i++) {
 		if ((i & 0xFF) == 0)
 			markers[i >> 8] = off;
+		table[i]->seq = i;
 
 		/* There cannot be any symbol of length zero. */
 		if (table[i]->len == 0) {
@@ -535,6 +566,12 @@ static void write_src(void)
 
 	free(markers);
 
+	sort_symbols_by_name();
+	output_label("kallsyms_seqs_of_names");
+	for (i = 0; i < table_cnt; i++)
+		printf("\t.long\t%u\n", table[i]->seq);
+	printf("\n");
+
 	output_label("kallsyms_token_table");
 	off = 0;
 	for (i = 0; i < 256; i++) {
-- 
2.25.1

[PATCH v8 3/9] kallsyms: Correctly sequence symbols when CONFIG_LTO_CLANG=y

[Zhen Lei]

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.

Old implementation code:
-	if (strcmp(namebuf, name) == 0)
-		return kallsyms_sym_address(i);
-	if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0)
-		return kallsyms_sym_address(i);

The preceding process is traversed by address from low to high. That is,
for those with the same name after the suffix is removed, the one with
the smallest address is returned first. Therefore, when sorting in the
tool, if the raw names are the same, they should be sorted by address in
ascending order.

ASCII[.]   = 2e
ASCII[0-9] = 30,39
ASCII[A-Z] = 41,5a
ASCII[_]   = 5f
ASCII[a-z] = 61,7a

According to the preceding ASCII code values, the following sorting result
is strictly followed.
 ---------------------------------
|    main-key     |    sub-key    |
|---------------------------------|
|                 |  addr_lowest  |
| <name>          |      ...      |
| <name>.<suffix> |      ...      |
|                 |  addr_highest |
|---------------------------------|
| <name>?<others> |               |   //? is [_A-Za-z0-9]
 ---------------------------------

Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 scripts/kallsyms.c      | 36 ++++++++++++++++++++++++++++++++++--
 scripts/link-vmlinux.sh |  4 ++++
 2 files changed, 38 insertions(+), 2 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index df2d93fb0e8d095..07ecf7e5c49f616 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -78,6 +78,7 @@ static unsigned int table_size, table_cnt;
 static int all_symbols;
 static int absolute_percpu;
 static int base_relative;
+static int lto_clang;
 
 static int token_profit[0x10000];
 
@@ -89,7 +90,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);
 }
 
@@ -411,6 +412,34 @@ static int symbol_absolute(const struct sym_entry *s)
 	return s->percpu_absolute;
 }
 
+static char * s_name(char *buf)
+{
+	/* Skip the symbol type */
+	return buf + 1;
+}
+
+static void cleanup_symbol_name(char *s)
+{
+	char *p;
+
+	if (!lto_clang)
+		return;
+
+	/*
+	 * ASCII[.]   = 2e
+	 * ASCII[0-9] = 30,39
+	 * ASCII[A-Z] = 41,5a
+	 * ASCII[_]   = 5f
+	 * ASCII[a-z] = 61,7a
+	 *
+	 * As above, replacing '.' with '\0' does not affect the main sorting,
+	 * but it helps us with subsorting.
+	 */
+	p = strchr(s, '.');
+	if (p)
+		*p = '\0';
+}
+
 static int compare_names(const void *a, const void *b)
 {
 	int ret;
@@ -421,7 +450,9 @@ static int compare_names(const void *a, const void *b)
 
 	expand_symbol(sa->sym, sa->len, sa_namebuf);
 	expand_symbol(sb->sym, sb->len, sb_namebuf);
-	ret = strcmp(&sa_namebuf[1], &sb_namebuf[1]);
+	cleanup_symbol_name(s_name(sa_namebuf));
+	cleanup_symbol_name(s_name(sb_namebuf));
+	ret = strcmp(s_name(sa_namebuf), s_name(sb_namebuf));
 	if (!ret) {
 		if (sa->addr > sb->addr)
 			return 1;
@@ -855,6 +886,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, &lto_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

[PATCH v8 4/9] kallsyms: Reduce the memory occupied by kallsyms_seqs_of_names[]

[Zhen Lei]

kallsyms_seqs_of_names[] records the symbol index sorted by address, the
maximum value in kallsyms_seqs_of_names[] is the number of symbols. And
2^24 = 16777216, which means that three bytes are enough to store the
index. This can help us save (1 * kallsyms_num_syms) bytes of memory.

Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 kernel/kallsyms.c          | 18 ++++++++++++++----
 kernel/kallsyms_internal.h |  2 +-
 scripts/kallsyms.c         |  5 ++++-
 3 files changed, 19 insertions(+), 6 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index ba351dfa109b6ac..48f36fd7e10b95e 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -201,6 +201,16 @@ static int compare_symbol_name(const char *name, char *namebuf)
 	return ret;
 }
 
+static unsigned int get_symbol_seq(int index)
+{
+	unsigned int i, seq = 0;
+
+	for (i = 0; i < 3; i++)
+		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
+
+	return seq;
+}
+
 static int kallsyms_lookup_names(const char *name,
 				 unsigned int *start,
 				 unsigned int *end)
@@ -215,7 +225,7 @@ static int kallsyms_lookup_names(const char *name,
 
 	while (low <= high) {
 		mid = low + (high - low) / 2;
-		seq = kallsyms_seqs_of_names[mid];
+		seq = get_symbol_seq(mid);
 		off = get_symbol_offset(seq);
 		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
 		ret = compare_symbol_name(name, namebuf);
@@ -232,7 +242,7 @@ static int kallsyms_lookup_names(const char *name,
 
 	low = mid;
 	while (low) {
-		seq = kallsyms_seqs_of_names[low - 1];
+		seq = get_symbol_seq(low - 1);
 		off = get_symbol_offset(seq);
 		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
 		if (compare_symbol_name(name, namebuf))
@@ -244,7 +254,7 @@ static int kallsyms_lookup_names(const char *name,
 	if (end) {
 		high = mid;
 		while (high < kallsyms_num_syms - 1) {
-			seq = kallsyms_seqs_of_names[high + 1];
+			seq = get_symbol_seq(high + 1);
 			off = get_symbol_offset(seq);
 			kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
 			if (compare_symbol_name(name, namebuf))
@@ -269,7 +279,7 @@ unsigned long kallsyms_lookup_name(const char *name)
 
 	ret = kallsyms_lookup_names(name, &i, NULL);
 	if (!ret)
-		return kallsyms_sym_address(kallsyms_seqs_of_names[i]);
+		return kallsyms_sym_address(get_symbol_seq(i));
 
 	return module_kallsyms_lookup_name(name);
 }
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index a04b7a5cb1e3eaf..27fabdcc40f5793 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -26,6 +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 int kallsyms_seqs_of_names[] __weak;
+extern const u8 kallsyms_seqs_of_names[] __weak;
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 07ecf7e5c49f616..04e04fbd9625caf 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -600,7 +600,10 @@ static void write_src(void)
 	sort_symbols_by_name();
 	output_label("kallsyms_seqs_of_names");
 	for (i = 0; i < table_cnt; i++)
-		printf("\t.long\t%u\n", table[i]->seq);
+		printf("\t.byte 0x%02x, 0x%02x, 0x%02x\n",
+			(unsigned char)(table[i]->seq >> 16),
+			(unsigned char)(table[i]->seq >> 8),
+			(unsigned char)(table[i]->seq >> 0));
 	printf("\n");
 
 	output_label("kallsyms_token_table");
-- 
2.25.1

RE: [PATCH v8 4/9] kallsyms: Reduce the memory occupied by kallsyms_seqs_of_names[]

[David Laight]

From: Zhen Lei
> Sent: 02 November 2022 08:49
> 
> kallsyms_seqs_of_names[] records the symbol index sorted by address, the
> maximum value in kallsyms_seqs_of_names[] is the number of symbols. And
> 2^24 = 16777216, which means that three bytes are enough to store the
> index. This can help us save (1 * kallsyms_num_syms) bytes of memory.

You can get the compiler to do the 'heavy lifting' for you.

struct uint24 {
    unsigned int val24:24;
} __attribute__((packed));

struct uint24 table[1024];

works fine.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: [PATCH v8 4/9] kallsyms: Reduce the memory occupied by kallsyms_seqs_of_names[]

[Leizhen (ThunderTown)]

On 2022/11/2 20:00, David Laight wrote:
> From: Zhen Lei
>> Sent: 02 November 2022 08:49
>>
>> kallsyms_seqs_of_names[] records the symbol index sorted by address, the
>> maximum value in kallsyms_seqs_of_names[] is the number of symbols. And
>> 2^24 = 16777216, which means that three bytes are enough to store the
>> index. This can help us save (1 * kallsyms_num_syms) bytes of memory.
> 
> You can get the compiler to do the 'heavy lifting' for you.
> 
> struct uint24 {
>     unsigned int val24:24;
> } __attribute__((packed));

This method depends on byte order. If the byte order of the tool is
different from that of the kernel, it's a problem. For example,
cross-compile PowerPC kernel on x86.

> 
> struct uint24 table[1024];
> 
> works fine.
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
> 
> 
> .
> 

-- 
Regards,
  Zhen Lei

[PATCH v8 5/9] kallsyms: Add helper kallsyms_on_each_match_symbol()

[Zhen Lei]

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.

Because all symbols are currently sorted by name, all the symbols with the
same name are clustered together. Function kallsyms_lookup_names() gets
the start and end positions of the set corresponding to the specified
name. So we can easily and quickly traverse all the matches.

The test results are as follows (twice): (x86)
kallsyms_on_each_match_symbol:     7454,     7984
kallsyms_on_each_symbol      : 11733809, 11785803

kallsyms_on_each_match_symbol() consumes only 0.066% of
kallsyms_on_each_symbol()'s time. In other words, 1523x better
performance.

Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 include/linux/kallsyms.h |  8 ++++++++
 kernel/kallsyms.c        | 18 ++++++++++++++++++
 2 files changed, 26 insertions(+)

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 48f36fd7e10b95e..0008ada2b135bef 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -307,6 +307,24 @@ 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;
+	unsigned int i, start, end;
+
+	ret = kallsyms_lookup_names(name, &start, &end);
+	if (ret)
+		return 0;
+
+	for (i = start; !ret && i <= end; i++) {
+		ret = fn(data, kallsyms_sym_address(get_symbol_seq(i)));
+		cond_resched();
+	}
+
+	return ret;
+}
+
 static unsigned long get_symbol_pos(unsigned long addr,
 				    unsigned long *symbolsize,
 				    unsigned long *offset)
-- 
2.25.1

[PATCH v8 6/9] livepatch: Use kallsyms_on_each_match_symbol() to improve performance

[Zhen Lei]

Based on the test results of kallsyms_on_each_match_symbol() and
kallsyms_on_each_symbol(), the average performance can be improved by
more than 1500 times.

Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 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

Re: [PATCH v8 6/9] livepatch: Use kallsyms_on_each_match_symbol() to improve performance

[Petr Mladek]

Hi,

I am sorry for the late review. I have been snowed under another
tasks.

On Wed 2022-11-02 16:49:18, Zhen Lei wrote:
> Based on the test results of kallsyms_on_each_match_symbol() and
> kallsyms_on_each_symbol(), the average performance can be improved by
> more than 1500 times.

Sounds great.

> --- 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;

This duplicates most of the klp_find_callback(). Please, call this
new function in klp_find_callback() instead of the duplicated code.
I mean to do:

static int klp_find_callback(void *data, const char *name, unsigned long addr)
{
	struct klp_find_arg *args = data;

	if (strcmp(args->name, name))
		return 0;

	return klp_match_callback(data, addr);
}

Otherwise, it looks good.

Best Regards,
Petr

Re: [PATCH v8 6/9] livepatch: Use kallsyms_on_each_match_symbol() to improve performance

[Leizhen (ThunderTown)]

On 2022/11/23 21:28, Petr Mladek wrote:
> Hi,
> 
> I am sorry for the late review. I have been snowed under another
> tasks.
> 
> On Wed 2022-11-02 16:49:18, Zhen Lei wrote:
>> Based on the test results of kallsyms_on_each_match_symbol() and
>> kallsyms_on_each_symbol(), the average performance can be improved by
>> more than 1500 times.
> 
> Sounds great.
> 
>> --- 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;
> 
> This duplicates most of the klp_find_callback(). Please, call this
> new function in klp_find_callback() instead of the duplicated code.
> I mean to do:
> 
> static int klp_find_callback(void *data, const char *name, unsigned long addr)
> {
> 	struct klp_find_arg *args = data;
> 
> 	if (strcmp(args->name, name))
> 		return 0;
> 
> 	return klp_match_callback(data, addr);
> }

Good idea. But these patches have been merged into linux-next, how about I post
a new cleanup patch after v6.2-rc1?

> 
> Otherwise, it looks good.
> 
> Best Regards,
> Petr
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH v8 6/9] livepatch: Use kallsyms_on_each_match_symbol() to improve performance

[Petr Mladek]

On Thu 2022-11-24 10:36:23, Leizhen (ThunderTown) wrote:
> On 2022/11/23 21:28, Petr Mladek wrote:
> > Hi,
> > 
> > I am sorry for the late review. I have been snowed under another
> > tasks.
> > 
> > On Wed 2022-11-02 16:49:18, Zhen Lei wrote:
> >> Based on the test results of kallsyms_on_each_match_symbol() and
> >> kallsyms_on_each_symbol(), the average performance can be improved by
> >> more than 1500 times.
> > 
> > Sounds great.
> > 
> >> --- 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;
> > 
> > This duplicates most of the klp_find_callback(). Please, call this
> > new function in klp_find_callback() instead of the duplicated code.
> > I mean to do:
> > 
> > static int klp_find_callback(void *data, const char *name, unsigned long addr)
> > {
> > 	struct klp_find_arg *args = data;
> > 
> > 	if (strcmp(args->name, name))
> > 		return 0;
> > 
> > 	return klp_match_callback(data, addr);
> > }
> 
> Good idea. But these patches have been merged into linux-next, how about I post
> a new cleanup patch after v6.2-rc1?

I am fine with it.

Best Regards,
Petr

Re: [PATCH v8 6/9] livepatch: Use kallsyms_on_each_match_symbol() to improve performance

[Luis Chamberlain]

On Thu, Nov 24, 2022 at 10:36:23AM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2022/11/23 21:28, Petr Mladek wrote:
> > Hi,
> > 
> > I am sorry for the late review. I have been snowed under another
> > tasks.
> > 
> > On Wed 2022-11-02 16:49:18, Zhen Lei wrote:
> >> Based on the test results of kallsyms_on_each_match_symbol() and
> >> kallsyms_on_each_symbol(), the average performance can be improved by
> >> more than 1500 times.
> > 
> > Sounds great.
> > 
> >> --- 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;
> > 
> > This duplicates most of the klp_find_callback(). Please, call this
> > new function in klp_find_callback() instead of the duplicated code.
> > I mean to do:
> > 
> > static int klp_find_callback(void *data, const char *name, unsigned long addr)
> > {
> > 	struct klp_find_arg *args = data;
> > 
> > 	if (strcmp(args->name, name))
> > 		return 0;
> > 
> > 	return klp_match_callback(data, addr);
> > }
> 
> Good idea. But these patches have been merged into linux-next, how about I post
> a new cleanup patch after v6.2-rc1?

You can send the cleanup now. The code doesn't change drastically, just
base it on modules-next.

  Luis

Re: [PATCH v8 6/9] livepatch: Use kallsyms_on_each_match_symbol() to improve performance

[Leizhen (ThunderTown)]

On 2022/12/7 6:08, Luis Chamberlain wrote:
> On Thu, Nov 24, 2022 at 10:36:23AM +0800, Leizhen (ThunderTown) wrote:
>>
>>
>> On 2022/11/23 21:28, Petr Mladek wrote:
>>> Hi,
>>>
>>> I am sorry for the late review. I have been snowed under another
>>> tasks.
>>>
>>> On Wed 2022-11-02 16:49:18, Zhen Lei wrote:
>>>> Based on the test results of kallsyms_on_each_match_symbol() and
>>>> kallsyms_on_each_symbol(), the average performance can be improved by
>>>> more than 1500 times.
>>>
>>> Sounds great.
>>>
>>>> --- 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;
>>>
>>> This duplicates most of the klp_find_callback(). Please, call this
>>> new function in klp_find_callback() instead of the duplicated code.
>>> I mean to do:
>>>
>>> static int klp_find_callback(void *data, const char *name, unsigned long addr)
>>> {
>>> 	struct klp_find_arg *args = data;
>>>
>>> 	if (strcmp(args->name, name))
>>> 		return 0;
>>>
>>> 	return klp_match_callback(data, addr);
>>> }
>>
>> Good idea. But these patches have been merged into linux-next, how about I post
>> a new cleanup patch after v6.2-rc1?
> 
> You can send the cleanup now. The code doesn't change drastically, just
> base it on modules-next.

OK

> 
>   Luis
> .
> 

-- 
Regards,
  Zhen Lei

[PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Zhen Lei]

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 <thunder.leizhen@huawei.com>
---
 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

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Jiri Olsa]

On Wed, Nov 02, 2022 at 04:49:19PM +0800, Zhen Lei wrote:
> 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.

hi,
sorry for delayed answer, I did not notice this until Stephen's email
about merge issue with recent bpf change [1]

> 
> Let's add a new parameter 'const char *modname' to function
> module_kallsyms_on_each_symbol(), then we can compare the module names

we have use case for iterating all modules and their symbols when we
want to resolve passed addresses for tracing

we don't have 'modname' that we could pass, we need to iterate all modules

so perhaps this could be made optional like with passing NULL for modname?

> directly in this function and call hook 'fn' after matching. And the
> parameter 'struct module *' in the hook 'fn' can also be deleted.

we need 'struct module *' argument in the callback as well because we are
taking the module reference if we trace function in it, so it wont get
unloaded

please let me know if I should do the change or can help in any way

thanks,
jirka

[1] https://lore.kernel.org/lkml/20221114111350.38e44eec@canb.auug.org.au/

> 
> Phase1: mod1-->mod2..(subsequent modules do not need to be compared)
>                 |
> Phase2:          -->f1-->f2-->f3
> 
> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> ---
>  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
> 

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Leizhen (ThunderTown)]

On 2022/11/14 15:47, Jiri Olsa wrote:
> On Wed, Nov 02, 2022 at 04:49:19PM +0800, Zhen Lei wrote:
>> 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.
> 
> hi,
> sorry for delayed answer, I did not notice this until Stephen's email
> about merge issue with recent bpf change [1]
> 
>>
>> Let's add a new parameter 'const char *modname' to function
>> module_kallsyms_on_each_symbol(), then we can compare the module names
> 
> we have use case for iterating all modules and their symbols when we
> want to resolve passed addresses for tracing
> 
> we don't have 'modname' that we could pass, we need to iterate all modules
> 
> so perhaps this could be made optional like with passing NULL for modname?

The deletion of modname was suggested by Petr Mladek. The reason is that
everyone passes modname as NULL, there was no actual demand at the time.
https://lkml.org/lkml/2022/9/20/682

> 
>> directly in this function and call hook 'fn' after matching. And the
>> parameter 'struct module *' in the hook 'fn' can also be deleted.
> 
> we need 'struct module *' argument in the callback as well because we are
> taking the module reference if we trace function in it, so it wont get
> unloaded
> 
> please let me know if I should do the change or can help in any way

It seems that we should take the module reference before invoking callback
and put it after it is called, without passing modname.

> 
> thanks,
> jirka
> 
> [1] https://lore.kernel.org/lkml/20221114111350.38e44eec@canb.auug.org.au/
> 
>>
>> Phase1: mod1-->mod2..(subsequent modules do not need to be compared)
>>                 |
>> Phase2:          -->f1-->f2-->f3
>>
>> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
>> ---
>>  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
>>
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Jiri Olsa]

On Mon, Nov 14, 2022 at 04:50:25PM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2022/11/14 15:47, Jiri Olsa wrote:
> > On Wed, Nov 02, 2022 at 04:49:19PM +0800, Zhen Lei wrote:
> >> 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.
> > 
> > hi,
> > sorry for delayed answer, I did not notice this until Stephen's email
> > about merge issue with recent bpf change [1]
> > 
> >>
> >> Let's add a new parameter 'const char *modname' to function
> >> module_kallsyms_on_each_symbol(), then we can compare the module names
> > 
> > we have use case for iterating all modules and their symbols when we
> > want to resolve passed addresses for tracing
> > 
> > we don't have 'modname' that we could pass, we need to iterate all modules
> > 
> > so perhaps this could be made optional like with passing NULL for modname?
> 
> The deletion of modname was suggested by Petr Mladek. The reason is that
> everyone passes modname as NULL, there was no actual demand at the time.
> https://lkml.org/lkml/2022/9/20/682
> 
> > 
> >> directly in this function and call hook 'fn' after matching. And the
> >> parameter 'struct module *' in the hook 'fn' can also be deleted.
> > 
> > we need 'struct module *' argument in the callback as well because we are
> > taking the module reference if we trace function in it, so it wont get
> > unloaded
> > 
> > please let me know if I should do the change or can help in any way
> 
> It seems that we should take the module reference before invoking callback
> and put it after it is called, without passing modname.

we take the module ref only if we (callback) find the traced address in
the module, we don't have the module object before

jirka

> 
> > 
> > thanks,
> > jirka
> > 
> > [1] https://lore.kernel.org/lkml/20221114111350.38e44eec@canb.auug.org.au/
> > 
> >>
> >> Phase1: mod1-->mod2..(subsequent modules do not need to be compared)
> >>                 |
> >> Phase2:          -->f1-->f2-->f3
> >>
> >> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> >> ---
> >>  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
> >>
> > .
> > 
> 
> -- 
> Regards,
>   Zhen Lei

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Leizhen (ThunderTown)]

On 2022/11/14 17:27, Jiri Olsa wrote:
> On Mon, Nov 14, 2022 at 04:50:25PM +0800, Leizhen (ThunderTown) wrote:
>>
>> On 2022/11/14 15:47, Jiri Olsa wrote:
>>> On Wed, Nov 02, 2022 at 04:49:19PM +0800, Zhen Lei wrote:
>>>> 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.
>>> hi,
>>> sorry for delayed answer, I did not notice this until Stephen's email
>>> about merge issue with recent bpf change [1]
>>>
>>>> Let's add a new parameter 'const char *modname' to function
>>>> module_kallsyms_on_each_symbol(), then we can compare the module names
>>> we have use case for iterating all modules and their symbols when we
>>> want to resolve passed addresses for tracing
>>>
>>> we don't have 'modname' that we could pass, we need to iterate all modules
>>>
>>> so perhaps this could be made optional like with passing NULL for modname?
>> The deletion of modname was suggested by Petr Mladek. The reason is that
>> everyone passes modname as NULL, there was no actual demand at the time.
>> https://lkml.org/lkml/2022/9/20/682
>>
>>>> directly in this function and call hook 'fn' after matching. And the
>>>> parameter 'struct module *' in the hook 'fn' can also be deleted.
>>> we need 'struct module *' argument in the callback as well because we are
>>> taking the module reference if we trace function in it, so it wont get
>>> unloaded
>>>
>>> please let me know if I should do the change or can help in any way
>> It seems that we should take the module reference before invoking callback
>> and put it after it is called, without passing modname.
> we take the module ref only if we (callback) find the traced address in
> the module, we don't have the module object before
> 
> jirka
> 

Do it in function module_kallsyms_on_each_symbol()?

But I just saw that mutex_lock(&module_mutex) protection is already
provided in this function. So reference counting protection may not
be required.


-- 
Regards,
  Zhen Lei

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Jiri Olsa]

On Mon, Nov 14, 2022 at 06:00:38PM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2022/11/14 17:27, Jiri Olsa wrote:
> > On Mon, Nov 14, 2022 at 04:50:25PM +0800, Leizhen (ThunderTown) wrote:
> >>
> >> On 2022/11/14 15:47, Jiri Olsa wrote:
> >>> On Wed, Nov 02, 2022 at 04:49:19PM +0800, Zhen Lei wrote:
> >>>> 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.
> >>> hi,
> >>> sorry for delayed answer, I did not notice this until Stephen's email
> >>> about merge issue with recent bpf change [1]
> >>>
> >>>> Let's add a new parameter 'const char *modname' to function
> >>>> module_kallsyms_on_each_symbol(), then we can compare the module names
> >>> we have use case for iterating all modules and their symbols when we
> >>> want to resolve passed addresses for tracing
> >>>
> >>> we don't have 'modname' that we could pass, we need to iterate all modules
> >>>
> >>> so perhaps this could be made optional like with passing NULL for modname?
> >> The deletion of modname was suggested by Petr Mladek. The reason is that
> >> everyone passes modname as NULL, there was no actual demand at the time.
> >> https://lkml.org/lkml/2022/9/20/682
> >>
> >>>> directly in this function and call hook 'fn' after matching. And the
> >>>> parameter 'struct module *' in the hook 'fn' can also be deleted.
> >>> we need 'struct module *' argument in the callback as well because we are
> >>> taking the module reference if we trace function in it, so it wont get
> >>> unloaded
> >>>
> >>> please let me know if I should do the change or can help in any way
> >> It seems that we should take the module reference before invoking callback
> >> and put it after it is called, without passing modname.
> > we take the module ref only if we (callback) find the traced address in
> > the module, we don't have the module object before
> > 
> > jirka
> > 
> 
> Do it in function module_kallsyms_on_each_symbol()?
> 
> But I just saw that mutex_lock(&module_mutex) protection is already
> provided in this function. So reference counting protection may not
> be required.

we take the module ref so it won't unload even outside of the
module_kallsyms_on_each_symbol function

jirka

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Leizhen (ThunderTown)]

On 2022/11/14 18:31, Jiri Olsa wrote:
> On Mon, Nov 14, 2022 at 06:00:38PM +0800, Leizhen (ThunderTown) wrote:
>>
>>
>> On 2022/11/14 17:27, Jiri Olsa wrote:
>>> On Mon, Nov 14, 2022 at 04:50:25PM +0800, Leizhen (ThunderTown) wrote:
>>>>
>>>> On 2022/11/14 15:47, Jiri Olsa wrote:
>>>>> On Wed, Nov 02, 2022 at 04:49:19PM +0800, Zhen Lei wrote:
>>>>>> 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.
>>>>> hi,
>>>>> sorry for delayed answer, I did not notice this until Stephen's email
>>>>> about merge issue with recent bpf change [1]
>>>>>
>>>>>> Let's add a new parameter 'const char *modname' to function
>>>>>> module_kallsyms_on_each_symbol(), then we can compare the module names
>>>>> we have use case for iterating all modules and their symbols when we
>>>>> want to resolve passed addresses for tracing
>>>>>
>>>>> we don't have 'modname' that we could pass, we need to iterate all modules
>>>>>
>>>>> so perhaps this could be made optional like with passing NULL for modname?
>>>> The deletion of modname was suggested by Petr Mladek. The reason is that
>>>> everyone passes modname as NULL, there was no actual demand at the time.
>>>> https://lkml.org/lkml/2022/9/20/682
>>>>
>>>>>> directly in this function and call hook 'fn' after matching. And the
>>>>>> parameter 'struct module *' in the hook 'fn' can also be deleted.
>>>>> we need 'struct module *' argument in the callback as well because we are
>>>>> taking the module reference if we trace function in it, so it wont get
>>>>> unloaded
>>>>>
>>>>> please let me know if I should do the change or can help in any way
>>>> It seems that we should take the module reference before invoking callback
>>>> and put it after it is called, without passing modname.
>>> we take the module ref only if we (callback) find the traced address in
>>> the module, we don't have the module object before
>>>
>>> jirka
>>>
>>
>> Do it in function module_kallsyms_on_each_symbol()?
>>
>> But I just saw that mutex_lock(&module_mutex) protection is already
>> provided in this function. So reference counting protection may not
>> be required.
> 
> we take the module ref so it won't unload even outside of the
> module_kallsyms_on_each_symbol function

There's another way to do it, but it's more time consuming.

struct module *__module_text_address(unsigned long addr);
struct module *__module_address(unsigned long addr);

Which way do you think is more appropriate?


> 
> jirka
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Jiri Olsa]

On Mon, Nov 14, 2022 at 07:30:16PM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2022/11/14 18:31, Jiri Olsa wrote:
> > On Mon, Nov 14, 2022 at 06:00:38PM +0800, Leizhen (ThunderTown) wrote:
> >>
> >>
> >> On 2022/11/14 17:27, Jiri Olsa wrote:
> >>> On Mon, Nov 14, 2022 at 04:50:25PM +0800, Leizhen (ThunderTown) wrote:
> >>>>
> >>>> On 2022/11/14 15:47, Jiri Olsa wrote:
> >>>>> On Wed, Nov 02, 2022 at 04:49:19PM +0800, Zhen Lei wrote:
> >>>>>> 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.
> >>>>> hi,
> >>>>> sorry for delayed answer, I did not notice this until Stephen's email
> >>>>> about merge issue with recent bpf change [1]
> >>>>>
> >>>>>> Let's add a new parameter 'const char *modname' to function
> >>>>>> module_kallsyms_on_each_symbol(), then we can compare the module names
> >>>>> we have use case for iterating all modules and their symbols when we
> >>>>> want to resolve passed addresses for tracing
> >>>>>
> >>>>> we don't have 'modname' that we could pass, we need to iterate all modules
> >>>>>
> >>>>> so perhaps this could be made optional like with passing NULL for modname?
> >>>> The deletion of modname was suggested by Petr Mladek. The reason is that
> >>>> everyone passes modname as NULL, there was no actual demand at the time.
> >>>> https://lkml.org/lkml/2022/9/20/682
> >>>>
> >>>>>> directly in this function and call hook 'fn' after matching. And the
> >>>>>> parameter 'struct module *' in the hook 'fn' can also be deleted.
> >>>>> we need 'struct module *' argument in the callback as well because we are
> >>>>> taking the module reference if we trace function in it, so it wont get
> >>>>> unloaded
> >>>>>
> >>>>> please let me know if I should do the change or can help in any way
> >>>> It seems that we should take the module reference before invoking callback
> >>>> and put it after it is called, without passing modname.
> >>> we take the module ref only if we (callback) find the traced address in
> >>> the module, we don't have the module object before
> >>>
> >>> jirka
> >>>
> >>
> >> Do it in function module_kallsyms_on_each_symbol()?
> >>
> >> But I just saw that mutex_lock(&module_mutex) protection is already
> >> provided in this function. So reference counting protection may not
> >> be required.
> > 
> > we take the module ref so it won't unload even outside of the
> > module_kallsyms_on_each_symbol function
> 
> There's another way to do it, but it's more time consuming.
> 
> struct module *__module_text_address(unsigned long addr);
> struct module *__module_address(unsigned long addr);
> 
> Which way do you think is more appropriate?

I think it'd be best to keep the module argument in the callback,
I don't see the harm.. AFAICS it was removed because you thought
nobody was using it, but that's not the case

using __module_text_address/__module_address might be doable and
it might be fast enough, because it's using rbtree

I'll check on that, meanwhile if we could keep the module argument,
that'd be great

thanks,
jirka

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Luis Chamberlain]

On Mon, Nov 14, 2022 at 02:26:19PM +0100, Jiri Olsa wrote:
> I'll check on that, meanwhile if we could keep the module argument,
> that'd be great

As Leizhen suggested I could just drop patches:

7/9 livepatch: Improve the search performance of module_kallsyms_on_each_symbol()
8/9 kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol()

Then after the next kernel is released this can be relooked at.
If this is agreeable let me know.

  Luis

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Leizhen (ThunderTown)]

On 2022/11/14 23:46, Luis Chamberlain wrote:
> On Mon, Nov 14, 2022 at 02:26:19PM +0100, Jiri Olsa wrote:
>> I'll check on that, meanwhile if we could keep the module argument,
>> that'd be great
> 
> As Leizhen suggested I could just drop patches:
> 
> 7/9 livepatch: Improve the search performance of module_kallsyms_on_each_symbol()
> 8/9 kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol()
> 
> Then after the next kernel is released this can be relooked at.
> If this is agreeable let me know.

I'm OK.

> 
>   Luis
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Jiri Olsa]

On Tue, Nov 15, 2022 at 10:10:16AM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2022/11/14 23:46, Luis Chamberlain wrote:
> > On Mon, Nov 14, 2022 at 02:26:19PM +0100, Jiri Olsa wrote:
> >> I'll check on that, meanwhile if we could keep the module argument,
> >> that'd be great
> > 
> > As Leizhen suggested I could just drop patches:
> > 
> > 7/9 livepatch: Improve the search performance of module_kallsyms_on_each_symbol()
> > 8/9 kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol()
> > 
> > Then after the next kernel is released this can be relooked at.
> > If this is agreeable let me know.
> 
> I'm OK.

sounds good, thanks

jirka

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Luis Chamberlain]

On Tue, Nov 15, 2022 at 08:30:23AM +0100, Jiri Olsa wrote:
> On Tue, Nov 15, 2022 at 10:10:16AM +0800, Leizhen (ThunderTown) wrote:
> > 
> > 
> > On 2022/11/14 23:46, Luis Chamberlain wrote:
> > > On Mon, Nov 14, 2022 at 02:26:19PM +0100, Jiri Olsa wrote:
> > >> I'll check on that, meanwhile if we could keep the module argument,
> > >> that'd be great
> > > 
> > > As Leizhen suggested I could just drop patches:
> > > 
> > > 7/9 livepatch: Improve the search performance of module_kallsyms_on_each_symbol()
> > > 8/9 kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol()
> > > 
> > > Then after the next kernel is released this can be relooked at.
> > > If this is agreeable let me know.
> > 
> > I'm OK.
> 
> sounds good, thanks

OK thanks, I dropped the last selftest patch as well, and pushed to
modules-next.  Leizhen, can you enhance the selftest for the new module
requirement and repost?

Stephen, you can drop your fix from linux-next, hopefully there should
no longer be any merge conflicts. The module requirement will stick for
now.

Thanks,

  Luis

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Leizhen (ThunderTown)]

On 2022/11/15 15:54, Luis Chamberlain wrote:
> On Tue, Nov 15, 2022 at 08:30:23AM +0100, Jiri Olsa wrote:
>> On Tue, Nov 15, 2022 at 10:10:16AM +0800, Leizhen (ThunderTown) wrote:
>>>
>>>
>>> On 2022/11/14 23:46, Luis Chamberlain wrote:
>>>> On Mon, Nov 14, 2022 at 02:26:19PM +0100, Jiri Olsa wrote:
>>>>> I'll check on that, meanwhile if we could keep the module argument,
>>>>> that'd be great
>>>>
>>>> As Leizhen suggested I could just drop patches:
>>>>
>>>> 7/9 livepatch: Improve the search performance of module_kallsyms_on_each_symbol()
>>>> 8/9 kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol()
>>>>
>>>> Then after the next kernel is released this can be relooked at.
>>>> If this is agreeable let me know.
>>>
>>> I'm OK.
>>
>> sounds good, thanks
> 
> OK thanks, I dropped the last selftest patch as well, and pushed to
> modules-next.  Leizhen, can you enhance the selftest for the new module
> requirement and repost?

Okay, right away.

> 
> Stephen, you can drop your fix from linux-next, hopefully there should
> no longer be any merge conflicts. The module requirement will stick for
> now.
> 
> Thanks,
> 
>   Luis
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Stephen Rothwell]

[-- Attachment #1: Type: text/plain, Size: 302 bytes --]

Hi Luis,

On Mon, 14 Nov 2022 23:54:08 -0800 Luis Chamberlain <mcgrof@kernel.org> wrote:
>
> Stephen, you can drop your fix from linux-next, hopefully there should
> no longer be any merge conflicts. The module requirement will stick for
> now.

OK, will do.

-- 
Cheers,
Stephen Rothwell

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Petr Mladek]

On Wed 2022-11-02 16:49:19, Zhen Lei wrote:
> 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

Just for record. The patch looks good from the livepatching code POV.

But I guess that it will need to get updated to support the new
callers in the ftrace and bpf code.

Best Regards,
Petr

Re: [PATCH v8 7/9] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Leizhen (ThunderTown)]

On 2022/11/23 21:57, Petr Mladek wrote:
> On Wed 2022-11-02 16:49:19, Zhen Lei wrote:
>> 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
> 
> Just for record. The patch looks good from the livepatching code POV.
> 
> But I guess that it will need to get updated to support the new
> callers in the ftrace and bpf code.

Yes, this patch and 8/9 conflicts with the patch series of Jiri Olsa,
So they didn't merge into linux-next. I will update and repost after
v6.2-rc1.

> 
> Best Regards,
> Petr
> .
> 

-- 
Regards,
  Zhen Lei

[PATCH v8 8/9] kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol()

[Zhen Lei]

The parameter 'struct module *' in the hook function associated with
kallsyms_on_each_symbol() is no longer used. Delete it.

Suggested-by: Petr Mladek <pmladek@suse.com>
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 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 0008ada2b135bef..5110d5501edeeb3 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -288,8 +288,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];
@@ -299,7 +298,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

[PATCH v8 9/9] kallsyms: Add self-test facility

[Zhen Lei]

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 <thunder.leizhen@huawei.com>
---
 include/linux/kallsyms.h   |   1 +
 init/Kconfig               |  13 +
 kernel/Makefile            |   1 +
 kernel/kallsyms.c          |   2 +-
 kernel/kallsyms_selftest.c | 485 +++++++++++++++++++++++++++++++++++++
 kernel/kallsyms_selftest.h |  13 +
 6 files changed, 514 insertions(+), 1 deletion(-)
 create mode 100644 kernel/kallsyms_selftest.c
 create mode 100644 kernel/kallsyms_selftest.h

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 abf65098f1b6bf1..c45935cd2f1f471 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 5110d5501edeeb3..77747391f49b66c 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -146,7 +146,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..e8cc0b41c7230a2
--- /dev/null
+++ b/kernel/kallsyms_selftest.c
@@ -0,0 +1,485 @@
+// 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 <thunder.leizhen@huawei.com> 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"
+#include "kallsyms_selftest.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 kallsyms_test_var_bss_static;
+static int kallsyms_test_var_data_static = 1;
+int kallsyms_test_var_bss;
+int kallsyms_test_var_data = 1;
+
+static int kallsyms_test_func_static(void)
+{
+	kallsyms_test_var_bss_static++;
+	kallsyms_test_var_data_static++;
+
+	return 0;
+}
+
+int kallsyms_test_func(void)
+{
+	return kallsyms_test_func_static();
+}
+
+__weak int kallsyms_test_func_weak(void)
+{
+	kallsyms_test_var_bss++;
+	kallsyms_test_var_data++;
+	return 0;
+}
+
+static struct test_item test_items[] = {
+	ITEM_FUNC(kallsyms_test_func_static),
+	ITEM_FUNC(kallsyms_test_func),
+	ITEM_FUNC(kallsyms_test_func_weak),
+	ITEM_FUNC(vmalloc),
+	ITEM_FUNC(vfree),
+#ifdef CONFIG_KALLSYMS_ALL
+	ITEM_DATA(kallsyms_test_var_bss_static),
+	ITEM_DATA(kallsyms_test_var_data_static),
+	ITEM_DATA(kallsyms_test_var_bss),
+	ITEM_DATA(kallsyms_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)
+{
+	u32 pos, off, len, num;
+	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 = 0;
+	num = 0;
+	off = 0;
+	while (pos < kallsyms_num_syms) {
+		len = kallsyms_names[off];
+		num++;
+		off++;
+		pos++;
+		if ((len & 0x80) != 0) {
+			len = (len & 0x7f) | (kallsyms_names[off] << 7);
+			num++;
+			off++;
+		}
+		off += len;
+	};
+
+	/*
+	 * 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 = off - num;
+	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, div_u64(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;
+
+	stat = kmalloc(sizeof(*stat) * 2, GFP_KERNEL);
+	if (!stat)
+		return -ENOMEM;
+	stat2 = stat + 1;
+
+	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) {
+		kfree(stat);
+		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;
+		}
+	}
+
+	kfree(stat);
+
+	return 0;
+
+failed:
+	pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr);
+	kfree(stat);
+	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);
diff --git a/kernel/kallsyms_selftest.h b/kernel/kallsyms_selftest.h
new file mode 100644
index 000000000000000..c0ca548e2a22599
--- /dev/null
+++ b/kernel/kallsyms_selftest.h
@@ -0,0 +1,13 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#ifndef LINUX_KALLSYMS_SELFTEST_H_
+#define LINUX_KALLSYMS_SELFTEST_H_
+
+#include <linux/types.h>
+
+extern int kallsyms_test_var_bss;
+extern int kallsyms_test_var_data;
+
+extern int kallsyms_test_func(void);
+extern int kallsyms_test_func_weak(void);
+
+#endif // LINUX_KALLSYMS_SELFTEST_H_
-- 
2.25.1

Re: [PATCH v8 0/9] kallsyms: Optimizes the performance of lookup symbols

[Luis Chamberlain]

On Wed, Nov 02, 2022 at 04:49:12PM +0800, Zhen Lei wrote:
> v7 --> v8:
> Sort the symbols by name and implement kallsyms_lookup_name() using a binary
> search. The performance is more than 20 times higher than that of v7. Of course,
> the memory overhead is also extended to (3 * kallsyms_num_syms) bytes. Discard
> all implementations of compression and then comparison in v7.
> 
> In addition, all sparse warnings about kallsyms_selftest.c are cleared.

Awesome work, I can't find a single thing I hate about this, but my
biggest conern is the lack of testing so I'm going to merge this to

Re: [PATCH v8 0/9] kallsyms: Optimizes the performance of lookup symbols

[Luis Chamberlain]

On Sat, Nov 12, 2022 at 06:44:26PM -0800, Luis Chamberlain wrote:
> On Wed, Nov 02, 2022 at 04:49:12PM +0800, Zhen Lei wrote:
> > v7 --> v8:
> > Sort the symbols by name and implement kallsyms_lookup_name() using a binary
> > search. The performance is more than 20 times higher than that of v7. Of course,
> > the memory overhead is also extended to (3 * kallsyms_num_syms) bytes. Discard
> > all implementations of compression and then comparison in v7.
> > 
> > In addition, all sparse warnings about kallsyms_selftest.c are cleared.
> 
> Awesome work, I can't find a single thing I hate about this, but my
> biggest conern is the lack of testing so I'm going to merge this to

Sorry finished the email too fast, I just wanted to add Nick to the
thread as his work does tons of changes on scripts/kallsyms.c.

I was saying -- I'm just concern with the lack of testing so I have merged
this to modules-next and see what explodes over the next few weeks.
I'm also happy to drop this from modules-next and have it go through
the livepatching tree instead, but given Nick's work is dedicated
towards modules and it also touches on scripts/kallsyms.c a lot, to
avoid conflicts it felt best to merge that to modules for now in case
his changes get merged during the next merge window.

Let me know what folks prefer.

Obviously, if testing blows up we can drop the series.

Zhen, wouldn't ftrace benefit from the same
s/kallsyms_on_each_symbol/kallsyms_on_each_match_symbol ?

  Luis

Re: [PATCH v8 0/9] kallsyms: Optimizes the performance of lookup symbols

[Leizhen (ThunderTown)]

On 2022/11/13 10:55, Luis Chamberlain wrote:
> On Sat, Nov 12, 2022 at 06:44:26PM -0800, Luis Chamberlain wrote:
>> On Wed, Nov 02, 2022 at 04:49:12PM +0800, Zhen Lei wrote:
>>> v7 --> v8:
>>> Sort the symbols by name and implement kallsyms_lookup_name() using a binary
>>> search. The performance is more than 20 times higher than that of v7. Of course,
>>> the memory overhead is also extended to (3 * kallsyms_num_syms) bytes. Discard
>>> all implementations of compression and then comparison in v7.
>>>
>>> In addition, all sparse warnings about kallsyms_selftest.c are cleared.
>>
>> Awesome work, I can't find a single thing I hate about this, but my
>> biggest conern is the lack of testing so I'm going to merge this to
> 
> Sorry finished the email too fast, I just wanted to add Nick to the
> thread as his work does tons of changes on scripts/kallsyms.c.
> 
> I was saying -- I'm just concern with the lack of testing so I have merged
> this to modules-next and see what explodes over the next few weeks.
> I'm also happy to drop this from modules-next and have it go through
> the livepatching tree instead, but given Nick's work is dedicated
> towards modules and it also touches on scripts/kallsyms.c a lot, to
> avoid conflicts it felt best to merge that to modules for now in case
> his changes get merged during the next merge window.
> 
> Let me know what folks prefer.
> 
> Obviously, if testing blows up we can drop the series.
> 
> Zhen, wouldn't ftrace benefit from the same
> s/kallsyms_on_each_symbol/kallsyms_on_each_match_symbol ?

ftrace uses regular matching, so it cannot be replaced.

> 
>   Luis
> .
> 

-- 
Regards,
  Zhen Lei