From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wm1-f41.google.com (mail-wm1-f41.google.com [209.85.128.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 019023E92BB for ; Wed, 6 May 2026 08:58:19 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.41 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778057903; cv=none; b=MbxREK5G5rcepmxkCCNuwXO5G3OKKZu6EYIjgGjTe33vfN+28+thqznvUNbIVFTZagNi3z4rKWQVy+1CMLZRY4LEG9C60339zp/Yoqj1HFXE96hUFXEuuFeENVf1gJd5WoqrVRvisAE3pNbwfOt3oJ6c/Y4+P3m7oxB8BShzX+A= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778057903; c=relaxed/simple; bh=2ql1LwdlEFefyEoDGprmept9lrBe1j+xp7imDDXxwOQ=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Bv1G++O/37Dw/iudvy/25zjVtLoBrZIK3+CJBdZIy0AviMfljKCUQpdHfJBedE0wd9T10FJxX6SxCqcKU3lCvFjirAYg1oGYq7Se1HKXwGiJOEQzEdK8ectOQsQP1SllAEsFGrwDOnMhpdLudwz7U+eVLQlX78bR+/XKgX2FKfE= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=suse.com; spf=pass smtp.mailfrom=suse.com; dkim=pass (2048-bit key) header.d=suse.com header.i=@suse.com header.b=KL2L13gw; arc=none smtp.client-ip=209.85.128.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=suse.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=suse.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=suse.com header.i=@suse.com header.b="KL2L13gw" Received: by mail-wm1-f41.google.com with SMTP id 5b1f17b1804b1-48896199cbaso53955125e9.1 for ; Wed, 06 May 2026 01:58:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=google; t=1778057898; x=1778662698; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=yq1rhhp+Y2W2kfISuuZ/kFZ98isQ+AScoJuJplL5IG4=; b=KL2L13gwWqZLTtRoOPyd4Jroet2qjFDquj6vD3ieDegRK5tjXarPh+NSH36QLQfq9a Uqf34+tRGQmozY93bJ8esfvRYYFmUYFAu6+DhPUkIjOnM+zGdpCJEAG6vFtsK8PeB3Bs KBqH9SoJDYY0lciPlgqIbG8ziWDv4aZQuRng4VdI6i12ttn6LdpQAFlywM0mMvv/JWa5 /0rGiWoCsdLS6g9m6JqE/JLCGLPUytq8rvfgt95/My2tk0w32Sm+ku6ufkxsvGz0vyqB adL5rHernpe6ba1cZFuNPYpeXk5ceFQXuQARSkPlUrkekBz1BTY5Jy2UA4bK+DeHOcbg SNmA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1778057898; x=1778662698; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-gg:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=yq1rhhp+Y2W2kfISuuZ/kFZ98isQ+AScoJuJplL5IG4=; b=Ss7xtKLmPDXPoRBj+YGRCJxQtTZGDCbl9zaTojMUoFZDn7/HFT9GovW6l3IgAvROEo kvedBL9LZOTwngC64KqfrNRBvi197UDOPTWogCF3EY1hxMfHvV5Us2mnNCP9CB+sT9vM f4ojFWCSh5FfxHrZyOXkMwsZwuVtHLLKnduNe+svPO4Frtvh6mqUA/3QnByPVZhplD8n fXbLzKxaMW8UsaIawL0mr21CjeNZ05YA6nfrTWs593uNZlclgP+0NvoT9kRb8XjlLMdT c/aoYK1CkpKMeU/qDv/rvKpCryQRjBFgBWiH0XJb0Ql8X0GJv92SxnQ5JAFJK1m+gl1U IQvQ== X-Forwarded-Encrypted: i=1; AFNElJ/3LkmdQDXIXJblVzpbKccJSJN8uGAOHxSzkwh0xcR9DL2mzTk0bNKbFnLeOflRenKcPNHVUPc62UQttd5mrxQXo9A=@vger.kernel.org X-Gm-Message-State: AOJu0YzLLLR5YrnfG96J5fanA4VuzYy4iszSbgPCqAgMT+b5sKfdspDc tHeU9bj16Vf5D6O9macqLMgCJYILuvCh7znmysVyuyF61NzqBPieOa3+jNlr4FbXaNY= X-Gm-Gg: AeBDievCKozglciQLdig1MDMxdfH7nObHDuXofY7ZZJU+URrl1CeVBZzLJmwv6h2oRb Ptw8NL6ooqVIblVttQDY15RAnM/1ceq4xfeAZbc2EWDevgyDEEjBvxJBos2PvZqldjJ+fmBD8Sb CuAbZoxrgN7OYkRwYGIao8s6pST8IgIaeJUTideHHJwUzUR8XlAtfvAhRSGi33B/omQx50RsLJA QHPd3etFeFNVkS6KdUKdQyDaoCfS0d0NwJu/bO+ytSWrAVKitd+kaYAaShWAaAafLTjxlc1EjyA r7UximxwuQVfocCCtcBFDlSsosFbHQPsmFIWgnlwhpZm4dMCimUWW1R+vw+LKrLGj/XQVfdLew/ 7aqymuY1dVyfxCMewJW3FXBYYrplHnHfd8FWsPRtNHIHtvrgk+zof8mbHSO+RmMVsN6gUb/QxHv QR1RxHl4qHRyHSHOkR6xHiTLOkcVx+RgkwBkcr X-Received: by 2002:a05:600c:4449:b0:48a:89d9:a419 with SMTP id 5b1f17b1804b1-48e51f2e67fmr42687525e9.11.1778057897613; Wed, 06 May 2026 01:58:17 -0700 (PDT) Received: from pathway.suse.cz ([176.114.240.130]) by smtp.gmail.com with ESMTPSA id 5b1f17b1804b1-48e52f5d299sm17831355e9.0.2026.05.06.01.58.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 06 May 2026 01:58:17 -0700 (PDT) Date: Wed, 6 May 2026 10:58:14 +0200 From: Petr Mladek To: Petr Pavlu Cc: Stanislaw Gruszka , linux-modules@vger.kernel.org, Sami Tolvanen , Luis Chamberlain , linux-kernel@vger.kernel.org, linux-trace-kernel@vger.kernel.org, live-patching@vger.kernel.org, Daniel Gomez , Aaron Tomlin , Steven Rostedt , Masami Hiramatsu , Jordan Rome , Viktor Malik , Miroslav Benes , Josh Poimboeuf , Joe Lawrence Subject: Re: [PATCH v2 2/2] module/kallsyms: sort function symbols and use binary search Message-ID: References: <20260327110005.16499-1-stf_xl@wp.pl> <20260327110005.16499-2-stf_xl@wp.pl> <28bb0f74-8721-4e53-ad89-87b2a78623b2@suse.com> Precedence: bulk X-Mailing-List: linux-trace-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <28bb0f74-8721-4e53-ad89-87b2a78623b2@suse.com> On Tue 2026-05-05 16:37:56, Petr Pavlu wrote: > On 5/5/26 2:24 PM, Petr Mladek wrote: > > On Fri 2026-03-27 12:00:05, Stanislaw Gruszka wrote: > >> Module symbol lookup via find_kallsyms_symbol() performs a linear scan > >> over the entire symtab when resolving an address. The number of symbols > >> in module symtabs has grown over the years, largely due to additional > >> metadata in non-standard sections, making this lookup very slow. > >> > >> Improve this by separating function symbols during module load, placing > >> them at the beginning of the symtab, sorting them by address, and using > >> binary search when resolving addresses in module text. > >> > >> This also should improve times for linear symbol name lookups, as valid > >> function symbols are now located at the beginning of the symtab. > >> > >> The cost of sorting is small relative to module load time. In repeated > >> module load tests [1], depending on .config options, this change > >> increases load time between 2% and 4%. With cold caches, the difference > >> is not measurable, as memory access latency dominates. > >> > >> The sorting theoretically could be done in compile time, but much more > >> complicated as we would have to simulate kernel addresses resolution > >> for symbols, and then correct relocation entries. That would be risky > >> if get out of sync. > >> > >> The improvement can be observed when listing ftrace filter functions. > >> > >> Before: > >> > >> root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l > >> 74908 > >> > >> real 0m1.315s > >> user 0m0.000s > >> sys 0m1.312s > >> > >> After: > >> > >> root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l > >> 74911 > >> > >> real 0m0.167s > >> user 0m0.004s > >> sys 0m0.175s > >> > >> (there are three more symbols introduced by the patch) > >> > >> For livepatch modules, the symtab layout is preserved and the existing > >> linear search is used. For this case, it should be possible to keep > >> the original ELF symtab instead of copying it 1:1, but that is outside > >> the scope of this patch. > > > > What is the exact motivation for the special handling of livepatch modules, > > please? > > > > Honestly, I am always a bit lost in the various symbol tables. It is > > possile that I have got something wrong. > > > > Anyway, my understanding is that there are two aspects which are important > > for livepatches: > > > > 1. Livepatches need to preserve special symbols which are used to > > relocate symbols which were local in the original code, see > > Documentation/livepatch/module-elf-format.rst > > > > IMHO, this is why layout_symtab() computes space for all core > > symbols in livepatch modules and copies them in add_kallsyms(). > > > > The symtab is normally released when the module is loaded. > > But livepatch modules make its own copy of the important > > parts, see copy_module_elf(). > > > > IMHO, the sorting of function symbols vs other symbols does > > not matter here. I believe that the special relocation > > symbols are not affected by this. > > I'm not sure if I fully follow the conclusion in this point. My > understanding is that .klp.rela sections still refer to their special > symbols in the symbol table via Elf_Rela::r_info. If the symbol table is > filtered or reordered, these references will end up pointing to > incorrect symbols. My understanding is that the relocations point to symbols which are found via the name of the entry. Let's take an example from Documentation/livepatch/module-elf-format.rst: 73: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.snprintf,0 This symbol points to snprintf() function in vmlinux object. The address of this function is found via kallsyms, see klp_find_object_symbol(). IMHO, it does not matter if we shuffle this entry in the livepatch module because the real address is found via kallsyms(). Even the ordering of the entries in vmlinux is not important in _this particular case_ because the "sympos" is zero "0" in this case. It means that "snprintf" symbol name is unique in vmlinux. The ordering of the symbols in "vmlinux" becomes important if the livepatch needs to access a symbol and there are more symbols of the same name. This is what I tried to describe below. I hope that it makes some sense. As I said, I am not familiar with the elf format... > This is also described in Documentation/livepatch/module-elf-format.rst, > section "4.1 A livepatch module's symbol table". > > > > > > > 2. Livepatches _rely on the sorting_ of symbols in the module. > > The special relocation symbols might define a symbol position, > > see > > > > .klp.sym.objname.symbol_name,sympos > > > > in the documentation. It defines the position of the symbol > > when there are more symbols of the same name, see > > klp_match_callback() in kernel/livepatch/core.c. > > > > I am afraid that _this patch might break_ this when it moves > > function symbols before non-funciton ones. I guess that > > the symbols of the same name will not longer be groupped. > > I see. So if the module loader sorts the symbol table in a regular > module and a livepatch module exists for that module, the livepatch may > no longer function correctly. This means that the loader cannot even > reorder the symbol table in regular modules. Yeah, reordering symbols in regular module might break livepatching. Namely it might break finding the right symbol when there are more symbols of the same name. Best Regards, Petr