Hi,
I'm trying to understanding the crash tool and help some review as I know the maintainers time resources are limited for the time being.
From: "启瑞" <qirui.001@bytedance.com>
Date: 2026-07-22 16:00:47
To: ltao@redhat.com
Cc: devel@lists.crash-utility.osci.io,Rui Qi <qirui.001@bytedance.com>
Subject: [Crash-utility] [PATCH] symbols: optimize symval_hash_init with O(1) tail insertion>From: Rui Qi <qirui.001@bytedance.com>
>
>Replace the O(n) tail traversal with O(1) tail insertion using the
>existing val_hash_last pointer. The original code traversed the entire
>linked list on every insert to find the tail, resulting in O(n^2)
>complexity for hash table initialization.
>
>The new implementation uses the val_hash_last pointer that was already
>maintained in the data structure:
It seems the val_has_last pointer is created for the "last visited entry" instead of the "tail" of the table. But you are using it as the tail pointer.
>- Insert at tail in O(1) time
>- Update val_hash_last after each insertion
>- Set val_hash_next to NULL for each new entry
>
>This reduces hash table initialization from O(n^2) to O(n).
>
>Benchmark on a RISC-V 64-core machine (kernel 6.12.95, ~200k symbols):
>
> $ echo q | ./crash /proc/kcore vmlinux
>
> Before: 44.67 s (mean, n=6, σ=5.61)
> After: 36.56 s (mean, n=6, σ=2.30)
> Speedup: 1.22x (-18.1%), with improved consistency.
>
>Signed-off-by: Rui Qi <qirui.001@bytedance.com>
>---
> symbols.c | 15 +++++++--------
> 1 file changed, 7 insertions(+), 8 deletions(-)
>
>diff --git a/symbols.c b/symbols.c
>index 03511c8..0b564d2 100644
>--- a/symbols.c
>+++ b/symbols.c
>@@ -1085,12 +1085,13 @@ symbol_value_from_proc_kallsyms(char *symname)
>
> /*
> * Install all static kernel symbol values into the symval_hash.
>+ * Uses val_hash_last for O(1) tail insertion.
> */
> static void
> symval_hash_init(void)
> {
> int index;
>- struct syment *sp, *sph;
>+ struct syment *sp;
>
> for (sp = st->symtable; sp < st->symend; sp++) {
> index = SYMVAL_HASH_INDEX(sp->value);
>@@ -1098,14 +1099,12 @@ symval_hash_init(void)
> if (st->symval_hash[index].val_hash_head == NULL) {
> st->symval_hash[index].val_hash_head = sp;
> st->symval_hash[index].val_hash_last = sp;
>- continue;
>+ } else {
>+ /* O(1) tail insertion using val_hash_last */
>+ st->symval_hash[index].val_hash_last->val_hash_next = sp;
if the head pointer is NULL, could the last value be NULL as well?
>+ st->symval_hash[index].val_hash_last = sp;
> }
>-
>- sph = st->symval_hash[index].val_hash_head;
>- while (sph->val_hash_next)
>- sph = sph->val_hash_next;
>-
>- sph->val_hash_next = sp;
>+ sp->val_hash_next = NULL;
> }
> }
>
>--
>2.47.3
>--
>Crash-utility mailing list -- devel@lists.crash-utility.osci.io
>To unsubscribe send an email to devel-leave@lists.crash-utility.osci.io
>https://${domain_name}/admin/lists/devel.lists.crash-utility.osci.io/
Thanks
Dave