From nobody Thu Nov 5 05:13:33 2026 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=124.126.103.232 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793848570; b=n7XhDH8T7PuL7gvYh0kTgOw4ls8j1gzdi+RG99/zNxwt7i3Allb/RGe/kwTy0K7idMz3 mcy8vP8VYZm94iiPdi7lBOHDgsQZbQin4X/whGxPaqQyaqiZkTDqpRv5ZjkefwHrFq+Rd 6GI1uMPa02PrrhiO47eO8G5c00XlJkrXfCczU5CSWNb2T2IqUz2bY6BHLhDPdh+Xj6Gyq alz+kcZk7XFLvNrNpqQ0LESgR/UW9D57LbM2cYM2yPDRGEf7pe2UKCfQg0xthgHD1u4yV VB0/NK39wJiPGtpOSVRowtEStWjFRrg4YuuSIKBfl1tyDied3pnpr7YnsNOk4dAwe+A== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793848570; h=DMARC-Filter:X-UUID:X-CTIC-Tags:X-CID-P-RULE:X-CID-O-INFO:X-CID-INFO: X-CID-META:X-CID-BVR:X-CID-BAS:X-CID-FACTOR:X-CID-RHF:X-UUID:X-User: Received:From:To:Cc:Subject:Date:Message-ID:X-Mailer:MIME-Version: Content-Transfer-Encoding; bh=ga6B7jCELkzHuVa0pEKdnU/De6nHNcAqX9HaxrGvbrA=; b=NXEU+xZeCkvIPA9WJBhmvN10K6R/Cof+gF1HX7Q6p2WHc1ZxIC8VO9jMrzH9Y804hQYG EYja0CoGWeaEhP+IOKVoXZY2FCfG1HuQK6QScwU1GbvbAPKCogsFyURwx9a1nY0dbXOV3 RXT0J0r3hBeDjnzzTlKzG9CweoFZFRPKsAllndOQ00DxlB0BrIrmnDc00HjglTAkR7F7Z XJSTqIsqaTA6t5WejaQW2wh0842FLl31RbrA9O/BaY+0Gl96DPDbGKE163imqxCHE493+ NEunmUum2QzuU9iAJkPyHYOsK8FgljsYfEhfFtSXdZ1bsOMcK2D1iy4+TELu1KN5lnQ== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none header.from=kylinos.cn; spf=pass smtp.mailfrom=kylinos.cn; arc=none smtp.remote-ip=124.126.103.232 Received: from mailgw.kylinos.cn (mailgw.kylinos.cn [124.126.103.232]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1665C606A32D; Thu, 5 Nov 2026 03:16:06 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 1665C606A32D Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=kylinos.cn Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=kylinos.cn X-UUID: 3650c5e8d8c711f19a56ed5b684f684d-20261105 X-CTIC-Tags: HR_CC_COUNT, HR_CC_DOMAIN_COUNT, HR_CC_NAME, HR_CC_NO_NAME, HR_CTE_8B HR_CTT_MISS, HR_DATE_H, HR_DATE_WKD, HR_DATE_ZONE, HR_FROM_NAME HR_SJ_DIGIT_LEN, HR_SJ_LANG, HR_SJ_LEN, HR_SJ_LETTER, HR_SJ_NOR_SYM HR_SJ_PHRASE, HR_SJ_PHRASE_LEN, HR_SJ_WS, HR_TO_COUNT, HR_TO_DOMAIN_COUNT HR_TO_NO_NAME, IP_TRUSTED, SRC_TRUSTED, SA_TRUSTED, SA_EXISTED SN_TRUSTED, SN_EXISTED, SPF_NOPASS, DKIM_NOPASS, DMARC_NOPASS UD_TRUSTED, CIE_BAD, CIE_GOOD, CIE_GOOD_SPF, GTI_FG_BS GTI_RG_INFO, GTI_C_BU, AMN_T1, AMN_GOOD, ABX_MISS_RDNS X-CID-P-RULE: Release_Ham X-CID-O-INFO: VERSION:1.3.19,REQID:7f62fdda-3fc7-4db5-bfa9-97d101fe9e3f,IP:15, URL:0,TC:0,Content:-25,EDM:25,RT:0,SF:0,FILE:0,BULK:0,RULE:Release_Ham,ACT ION:release,TS:15 X-CID-INFO: VERSION:1.3.19,REQID:7f62fdda-3fc7-4db5-bfa9-97d101fe9e3f,IP:15,UR L:0,TC:0,Content:-25,EDM:25,RT:0,SF:0,FILE:0,BULK:0,RULE:Release_Ham,ACTIO N:release,TS:15 X-CID-META: VersionHash:7db8b62,CLOUDID:28c6da9c87e703cbf0257455612a5dc8,BulkI D:261105111559WSM1TMSB,BulkQuantity:0,SF:17|19|38|66|78|102|127|153|865|89 8,TC:nil,Content:0|15|50|99,EDM:5,IP:-2,URL:99|1,File:nil,RT:nil,Bulk:nil, QS:nil,BEC:nil,COL:0,OSI:0,OSA:0,AV:0,LES:1,SPR:NO,DKR:0,DKP:0,BRR:0,BRE:0 ,ARC:0 X-CID-BVR: 2,SSN|SDN X-CID-BAS: 2,SSN|SDN,0,_ X-CID-FACTOR: TF_CID_SPAM_SNR,TF_CID_SPAM_FAS,TF_CID_SPAM_FSD,TF_CID_SPAM_ULS X-CID-RHF: D41D8CD98F00B204E9800998ECF8427E X-UUID: 3650c5e8d8c711f19a56ed5b684f684d-20261105 X-User: tianyaxiong@kylinos.cn Received: from kare.. [(116.128.244.171)] by mailgw.kylinos.cn (envelope-from ) (Generic MTA) with ESMTP id 1881586552; Thu, 05 Nov 2026 11:15:54 +0800 From: Yaxiong Tian To: rostedt@goodmis.org, mhiramat@kernel.org, mark.rutland@arm.com, mathieu.desnoyers@efficios.com Cc: linux-kernel@vger.kernel.org, linux-trace-kernel@vger.kernel.org, Yaxiong Tian Subject: [PATCH v2] ftrace: speed up module enable by binary searching module symbols Date: Thu, 5 Nov 2026 11:15:30 +0800 Message-ID: <20261105031530.280442-1-tianyaxiong@kylinos.cn> X-Mailer: git-send-email 2.43.0 X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Loading a module with many functions takes seconds, almost all of it in ftrace_module_enable(). amdgpu modules stall for about ten seconds, and disabling CONFIG_DYNAMIC_FTRACE makes the stall disappear. Every record is validated by test_for_valid_rec(), which resolves its ip through kallsyms_lookup(); for a module address that ends up in find_kallsyms_symbol(), which walks the whole module symbol table from index 1. The core kernel instead binary searches its sorted kallsyms table in get_symbol_pos(). So only modules pay, and the cost is quadratic: both the record count and the symbol count grow with the module. An amdgpu.ko from this tree has 17282 records and 55332 symbol table entries. Fix this by collecting the addresses of a module's symbols once, sorting them, and binary searching that array instead of walking the table once per record; a loaded module's symbol table cannot change, so the array stays valid for the whole pass. What comes back is what the linear scan returned: the same entries are skipped - SHN_UNDEF, unnamed and mapping symbols - and the closest address not below the base of the record's memory region is taken. Whenever the array cannot answer, because it could not be built or because no such symbol exists, the record is handed to test_for_valid_rec(), so the rest of kallsyms_lookup() still has its say and no verdict can change. On the machine that reported the stall, modprobe of that amdgpu.ko takes 12.242 s before and 2.870 s after, and the time spent inside ftrace_lock drops from 9.368 s to 1.585 ms - 15.195 ms if the price of building the array is included, that build being 13.6 ms, 0.15% of the 9.37 s saved. The array costs O(symbols * log symbols), it does not grow with the record count. Across the 74 modules loaded at boot, total lock time drops from 491 ms to 2.33 ms. Signed-off-by: Yaxiong Tian --- v2: - Use rcu_dereference_raw() instead of a transient rcu_read_lock() pair. - Manage the symbol array with __free(kvfree). - Adapt to the v7.4-rc1 rename of is_mapping_symbol() to is_ignored_kernel_symbol(). - v1 discussion: https://lore.kernel.org/all/20260916082715.320853-1-tianyaxiong@kylinos.c= n/ kernel/trace/ftrace.c | 124 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 123 insertions(+), 1 deletion(-) diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c index c7d74b33d36d..255e813fe70e 100644 --- a/kernel/trace/ftrace.c +++ b/kernel/trace/ftrace.c @@ -26,6 +26,7 @@ #include #include #include +#include #include #include #include @@ -8034,8 +8035,129 @@ void ftrace_release_mod(struct module *mod) } } =20 +#ifdef FTRACE_MCOUNT_MAX_OFFSET +/* + * ftrace_module_enable() validates every record with test_for_valid_rec(), + * which walks the whole symbol table of a module for each address in it, = so a + * large module loads in quadratic time. Search a sorted copy of the symb= ol + * addresses instead, the way get_symbol_pos() searches the kallsyms table. + * The array is an accelerator only; records it cannot resolve are tested = the + * old way, so the verdict does not change. + */ +struct ftrace_mod_syms { + unsigned int nr; + unsigned long addr[]; /* sorted, @nr entries */ +}; + +static int ftrace_mod_syms_cmp(const void *a, const void *b) +{ + unsigned long va =3D *(const unsigned long *)a; + unsigned long vb =3D *(const unsigned long *)b; + + return (va > vb) - (va < vb); +} + +static struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module *mod) +{ + struct mod_kallsyms *kallsyms; + struct ftrace_mod_syms *syms; + unsigned int i, nr =3D 0; + + /* + * mod->kallsyms stays valid until do_init_module() replaces it later + * in this thread, so no RCU read-side section is needed. + */ + kallsyms =3D rcu_dereference_raw(mod->kallsyms); + + if (!kallsyms || kallsyms->num_symtab < 2) + return NULL; + + syms =3D kvmalloc(struct_size(syms, addr, kallsyms->num_symtab), + GFP_KERNEL); + if (!syms) + return NULL; + + /* The symbols find_kallsyms_symbol() would consider. */ + for (i =3D 1; i < kallsyms->num_symtab; i++) { + const Elf_Sym *sym =3D &kallsyms->symtab[i]; + const char *name =3D kallsyms->strtab + sym->st_name; + + if (sym->st_shndx =3D=3D SHN_UNDEF || !*name || + is_ignored_kernel_symbol(name)) + continue; + + syms->addr[nr++] =3D kallsyms_symbol_value(sym); + } + syms->nr =3D nr; + + if (nr > 1) + sort(syms->addr, nr, sizeof(syms->addr[0]), ftrace_mod_syms_cmp, + NULL); + + return syms; +} + +/* The verdict test_for_valid_rec() would give, without walking the table.= */ +static bool ftrace_mod_rec_is_valid(struct module *mod, + const struct ftrace_mod_syms *syms, + struct dyn_ftrace *rec) +{ + unsigned long base, best; + unsigned int lo, hi; + + if (!syms) + return test_for_valid_rec(rec) !=3D 0; + + /* A record is in executable memory; anything else kallsyms answers. */ + if (within_module_mem_type(rec->ip, mod, MOD_TEXT)) + base =3D (unsigned long)mod->mem[MOD_TEXT].base; + else if (within_module_mem_type(rec->ip, mod, MOD_INIT_TEXT)) + base =3D (unsigned long)mod->mem[MOD_INIT_TEXT].base; + else + return test_for_valid_rec(rec) !=3D 0; + + /* The closest address at or below @rec->ip, if there is one. */ + best =3D 0; + for (lo =3D 0, hi =3D syms->nr; lo < hi; ) { + unsigned int mid =3D lo + (hi - lo) / 2; + + if (syms->addr[mid] <=3D rec->ip) + lo =3D mid + 1; + else + hi =3D mid; + } + if (lo) + best =3D syms->addr[lo - 1]; + + /* + * No symbol, or only ones below @base: let kallsyms_lookup() answer, + * as it also looks in the BPF and ftrace trampoline tables. + */ + if (best < base) + return test_for_valid_rec(rec) !=3D 0; + + return rec->ip - best <=3D FTRACE_MCOUNT_MAX_OFFSET; +} +#else +struct ftrace_mod_syms; + +static inline struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module = *mod) +{ + return NULL; +} + +static inline bool ftrace_mod_rec_is_valid(struct module *mod, + const struct ftrace_mod_syms *syms, + struct dyn_ftrace *rec) +{ + return test_for_valid_rec(rec) !=3D 0; +} +#endif /* FTRACE_MCOUNT_MAX_OFFSET */ + void ftrace_module_enable(struct module *mod) { + struct ftrace_mod_syms *syms __free(kvfree) =3D + ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod); struct dyn_ftrace *rec; struct ftrace_page *pg; =20 @@ -8074,7 +8196,7 @@ void ftrace_module_enable(struct module *mod) cond_resched(); =20 /* Weak functions should still be ignored */ - if (!test_for_valid_rec(rec)) { + if (!ftrace_mod_rec_is_valid(mod, syms, rec)) { /* Clear all other flags. Should not be enabled anyway */ rec->flags =3D FTRACE_FL_DISABLED; continue; --=20 2.43.0