From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com [209.85.221.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 BCB17426EC0 for ; Tue, 5 May 2026 12:24:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.41 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1777983888; cv=none; b=KEt6B0ZeRpAgYwPehM8a+lpz/iuQ1+D1QElWfLGOXKBMNU7+cV1bJtlInMFy9scVOPv5faUaQSZNAlFCIs2wBJ+fpgHnt7/Ktb9SRuzwqkIkrrDW+Y4jYzCMWfzVV3699olVDdHRKUTARNcuJWse90FiXxvKRssBmmLDqfmsAVM= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1777983888; c=relaxed/simple; bh=T60HQbL8qDyAg5IiNgQTk8uqdsTOZsHn/TzRE3z1AbM=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Mra/jiP1jvRBWTLxJmjuVMKJuwNvPYEOnzn2aGGhf19vjWkZLMaVTGeBZL7Pm/jgvu/Unp10M79tXguuAQM3qawS5iBkZDgil9BfNn4wUR6ryWErLjzkD6qFUAVT8alM9DROVfx/PBcp7iMUfH/hEMAguDifd4WAuec33FcrpgE= 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=cnj/gdL+; arc=none smtp.client-ip=209.85.221.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="cnj/gdL+" Received: by mail-wr1-f41.google.com with SMTP id ffacd0b85a97d-44a044cb827so3628650f8f.0 for ; Tue, 05 May 2026 05:24:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=google; t=1777983885; x=1778588685; 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=7yiH2TZpywbFVEglbVYA5/bUDfLfXjzVUSCKuxkRreU=; b=cnj/gdL+YLBQrX4yDlj3bwHxc/BaimJFIo/LT+2ZeTyz9TR58jX2qTFdWtuSSJAF6M 3QO13kQmzU/zQRVbpSQE42Xx+QpQnmFvy0u6v1fsXCOEO22UJTRkms9ohm01t/FaOW3G jaX8kF3sbydz1tge4OXh4RbMtBf/oj9UWUbesg0rYY9M4bcgxpYEqueaLR4YQ/SlVtb2 vjOXnAFZg4un5ydx78MWCwcWGiqtc5+sWF0W93aDgh9pb7o+Vicczk7DC7Cz05GkzGIo iociAN9JrOKFcfRrG5owf3NGebyoiYxQK+gB9T4fa4d2j9EpbvmSpMmpl0eG28mDDJer taMg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1777983885; x=1778588685; 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=7yiH2TZpywbFVEglbVYA5/bUDfLfXjzVUSCKuxkRreU=; b=mrth6xZJCltJPhJXhxuOB000240IshPNjzv/qh55wqUeMxzDnLjXw9aYgtkkUbed/N jFPTPjSJvsIBHx5rNYmQ5enzlDfUZsNFFrxlbtNYJcitcnJop3eQl/FPgZpY1QDaFA16 N0Kd+1VTyUtXL8YpulJU/bObPOuj8KBiSof4zbGYuLnUC4BgudxtTLgByz9mbQY00cIO gC3vjt+HyB9ewutbCocYMXL8CtQ0Mi9fbb+sNhP8Gq/10X6A84LkkoULHAAYzewYG9Kx 60r9Ap5O3XqYz/IVeyEUigbkaODfFZdINOUbfTSUOc70Lg5U6BlxpKgxBo1lHAUnwfl9 PCFA== X-Forwarded-Encrypted: i=1; AFNElJ9n2xKLxZ89vnc2yvMUT70T3vs6gd7cNf2dPiN0z6iHYgIZp19EVJhBDn3eUjJaS+7clft+tiGGQTERfb8=@vger.kernel.org X-Gm-Message-State: AOJu0YyNUErwEkmrKUEhSUVkq7mQMTZupDOm3GKVpl0sz1Iwv+W4jfyP 9iJQef5aQA/A+Q9jqmyqSqRbOiARVKxsfS7i7GR68f5qryPouGtBPy5qkP43+Yjsm/k= X-Gm-Gg: AeBDiesyrvkFuankv0xz1oSuTipHmcHPShDTKlsahCQEw476vxWli1TEqYuN03v+U8D nZNfZ7gL3zBO2CgvMze5EA1SjMmtEdC3MnnpnJSZpAWUTysNefd1b51SMWlUXovNqdx/opJ8tVh kojqpoJ32GUHTlpGTs/cefP3BE/7szhdMn68pH3zsDG3JLBYyUX0ay8/vwD28L+bpIzYyLvrv5v OLSuXQIL+ZkxJoC6Thu8/2Y/NOCsGJ8TetImRzYTmlsB3Mxg5RGrKtPQI0adep/ZpJDJ7q5s+We jG8n/2RqahXo+uE5hXS8yjKsWXBLogl1OmBVSoo1P3CPZTp2eI7P0BgCGE+ZJ9YF85ED0VhBFrJ 787qTSS2f2N9zwtUcO992z2w+6GkRmY2YA/anoIYtN33vp2iBT1ONi4GIIbApsWphH2rdLL/4Qg F0J1o3aBkaCtjBrcFPjO2vVuIyGmGIvWvzDypNhRGwUKgqvk0= X-Received: by 2002:a5d:64c9:0:b0:43d:7d24:b4ff with SMTP id ffacd0b85a97d-44bb772f856mr22057200f8f.40.1777983884553; Tue, 05 May 2026 05:24:44 -0700 (PDT) Received: from pathway.suse.cz ([176.114.240.130]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-4505285e765sm4159009f8f.10.2026.05.05.05.24.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 05 May 2026 05:24:43 -0700 (PDT) Date: Tue, 5 May 2026 14:24:41 +0200 From: Petr Mladek To: Stanislaw Gruszka Cc: linux-modules@vger.kernel.org, Sami Tolvanen , Luis Chamberlain , Petr Pavlu , 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> Precedence: bulk X-Mailing-List: linux-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: <20260327110005.16499-2-stf_xl@wp.pl> 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. 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. Idea: Is the shufling really important for the performance, please? I would expect that binary search would have a good performance even without the shuffling. It puts aside half of the symbols in one cycle. Note that the binary search in find_kallsyms_symbol() is perfectly fine. The livepatch code explicitly iterates over all symbols using module_kallsyms_on_each_symbol(), see klp_find_object_symbol(). Best Regards, Petr