4:54 a.m.
The numeric_forward() function serves as the comparator for qsort() when
sorting kernel symbols. For a modern Linux kernel containing hundreds of
thousands of symbols (N), qsort() performs O(N log N) comparisons,
meaning this function is invoked millions of times during the startup
phase of the crash utility.
During these millions of comparisons, it frequently checks for specific
symbol names (e.g., "_stext", "kaslr_get_random_long") using the
STREQ()
macro. STREQ() internally expands to string_exists() checks followed by a
full strcmp(), incurring significant function call overhead that cannot be
optimized out by the compiler at runtime.
By explicitly checking the first character of the symbol name
(e.g., x->name[0] == '_') before invoking STREQ(), we introduce a
lightweight "early reject" mechanism. Since the distribution of kernel
symbol starting characters is relatively sparse, this short-circuits the
evaluation for the vast majority of symbols, completely avoiding the
overhead of strcmp() macro expansion.
Additionally, since x->name could potentially be NULL, we must safely
guard the character access with an explicit non-null check (x->name &&)
to prevent segmentation faults.
This O(N log N) cumulative optimization yields a measurable performance
improvement in symbol sorting speed, which scales directly with the size
of the kernel symbol table.
Performance measurement (./crash /proc/kcore startup, n=6 alternating
runs on RISC-V 32-core, kernel 6.12.13.bsk.1-rc17-riscv64):
before after
mean (s) 60.367 48.688
median (s) 58.831 47.588
min (s) 54.980 45.951
max (s) 69.889 52.988
Speedup (mean): 1.24x (-11.68 s, -19.3%)
perf stat:
instructions: 3.104e11 -> 2.680e11 (-13.7%)
cycles: 1.612e11 -> 1.406e11 (-12.8%)
perf record (top hotspots):
strcmp: 12.59% -> 3.64%
string_exists: dropped out of top-10
Signed-off-by: Rui Qi <qirui.001(a)bytedance.com>
---
Changes in V2:
- Add performance measurement data (time, perf stat, perf record)
symbols.c | 40 ++++++++++++++++++++--------------------
1 file changed, 20 insertions(+), 20 deletions(-)
diff --git a/symbols.c b/symbols.c
index c0285058c5cb..c0353d626477 100644
--- a/symbols.c
+++ b/symbols.c
@@ -14412,16 +14412,16 @@ numeric_forward(const void *P_x, const void *P_y)
error(FATAL, "bfd_minisymbol_to_symbol failed\n");
if (st->_stext_vmlinux == UNINITIALIZED) {
- if (STREQ(x->name, "_stext"))
+ if (x->name && x->name[0] == '_' && STREQ(x->name,
"_stext"))
st->_stext_vmlinux = valueof(x);
- else if (STREQ(y->name, "_stext"))
+ else if (y->name && y->name[0] == '_' &&
STREQ(y->name, "_stext"))
st->_stext_vmlinux = valueof(y);
}
if (kt->flags2 & KASLR_CHECK) {
- if (STREQ(x->name, "kaslr_get_random_long") ||
- STREQ(y->name, "kaslr_get_random_long") ||
- STREQ(x->name, "module_load_offset") ||
- STREQ(y->name, "module_load_offset")) {
+ if ((x->name && x->name[0] == 'k' && STREQ(x->name,
"kaslr_get_random_long")) ||
+ (y->name && y->name[0] == 'k' && STREQ(y->name,
"kaslr_get_random_long")) ||
+ (x->name && x->name[0] == 'm' && STREQ(x->name,
"module_load_offset")) ||
+ (y->name && y->name[0] == 'm' && STREQ(y->name,
"module_load_offset"))) {
kt->flags2 &= ~KASLR_CHECK;
kt->flags2 |= (RELOC_AUTO|KASLR);
}
@@ -14429,36 +14429,36 @@ numeric_forward(const void *P_x, const void *P_y)
if (SADUMP_DUMPFILE() || QEMU_MEM_DUMP_NO_VMCOREINFO() || VMSS_DUMPFILE()) {
/* Need for kaslr_offset and phys_base */
- if (STREQ(x->name, "divide_error") ||
- STREQ(x->name, "asm_exc_divide_error"))
+ if ((x->name && x->name[0] == 'd' && STREQ(x->name,
"divide_error")) ||
+ (x->name && x->name[0] == 'a' && STREQ(x->name,
"asm_exc_divide_error")))
st->divide_error_vmlinux = valueof(x);
- else if (STREQ(y->name, "divide_error") ||
- STREQ(y->name, "asm_exc_divide_error"))
+ else if ((y->name && y->name[0] == 'd' &&
STREQ(y->name, "divide_error")) ||
+ (y->name && y->name[0] == 'a' && STREQ(y->name,
"asm_exc_divide_error")))
st->divide_error_vmlinux = valueof(y);
- if (STREQ(x->name, "idt_table"))
+ if (x->name && x->name[0] == 'i' && STREQ(x->name,
"idt_table"))
st->idt_table_vmlinux = valueof(x);
- else if (STREQ(y->name, "idt_table"))
+ else if (y->name && y->name[0] == 'i' &&
STREQ(y->name, "idt_table"))
st->idt_table_vmlinux = valueof(y);
- if (STREQ(x->name, "kaiser_init"))
+ if (x->name && x->name[0] == 'k' && STREQ(x->name,
"kaiser_init"))
st->kaiser_init_vmlinux = valueof(x);
- else if (STREQ(y->name, "kaiser_init"))
+ else if (y->name && y->name[0] == 'k' &&
STREQ(y->name, "kaiser_init"))
st->kaiser_init_vmlinux = valueof(y);
- if (STREQ(x->name, "linux_banner"))
+ if (x->name && x->name[0] == 'l' && STREQ(x->name,
"linux_banner"))
st->linux_banner_vmlinux = valueof(x);
- else if (STREQ(y->name, "linux_banner"))
+ else if (y->name && y->name[0] == 'l' &&
STREQ(y->name, "linux_banner"))
st->linux_banner_vmlinux = valueof(y);
- if (STREQ(x->name, "pti_init"))
+ if (x->name && x->name[0] == 'p' && STREQ(x->name,
"pti_init"))
st->pti_init_vmlinux = valueof(x);
- else if (STREQ(y->name, "pti_init"))
+ else if (y->name && y->name[0] == 'p' &&
STREQ(y->name, "pti_init"))
st->pti_init_vmlinux = valueof(y);
- if (STREQ(x->name, "saved_command_line"))
+ if (x->name && x->name[0] == 's' && STREQ(x->name,
"saved_command_line"))
st->saved_command_line_vmlinux = valueof(x);
- else if (STREQ(y->name, "saved_command_line"))
+ else if (y->name && y->name[0] == 's' &&
STREQ(y->name, "saved_command_line"))
st->saved_command_line_vmlinux = valueof(y);
}
--
2.47.3