From nobody Sun Jun 14 11:28:41 2026 Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BB34F223336 for ; Thu, 2 Apr 2026 12:21:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=216.40.44.13 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1775132499; cv=none; b=UeiFlGnWVNO3BSA3XVvxoqixJ6z5NM1gZZOADXWsEyYWl611Tq/uTrNu09Cad7Dxp7VO69ZvKxr8a0ZikU7yIea9RtWqcyaEG+naHg7TlYn/Z3Bj0OrL7dIUvs8HAsk2nEB2QU3upJljd0C9i8VoS6DxflnKPeq1fKc24EqKwRo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1775132499; c=relaxed/simple; bh=7yjwVqjdZ5KwYKjmJBysXznoTJ45iN5fneeTbGEHPnw=; h=Date:From:To:Cc:Subject:Message-ID:MIME-Version:Content-Type; b=CPWX7mxrW5PIoXBTLLwhlSd9SajSCP7Iq0KexB0NJKPsWXcx+pWqMe8oOiS3z1lbD3xzcoHLy1RxHiimiRbmxBi+1ZkCTsoP79GP2cBnlL0hcFsax+53ll0GH9knkd46jY6evuje1VuPmT3tPoGlhhJ5ri1W8n49Clnj++zHIis= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=goodmis.org; spf=pass smtp.mailfrom=goodmis.org; arc=none smtp.client-ip=216.40.44.13 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=goodmis.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=goodmis.org Received: from omf01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 1FB0A8C26A; Thu, 2 Apr 2026 12:21:30 +0000 (UTC) Received: from [HIDDEN] (Authenticated sender: rostedt@goodmis.org) by omf01.hostedemail.com (Postfix) with ESMTPA id 8FC7F60016; Thu, 2 Apr 2026 12:21:28 +0000 (UTC) Date: Thu, 2 Apr 2026 08:22:30 -0400 From: Steven Rostedt To: LKML Cc: Masami Hiramatsu , Mathieu Desnoyers , Mark Rutland , Andrey Grodzovsky Subject: [for-next][PATCH] ftrace: Use kallsyms binary search for single-symbol lookup Message-ID: <20260402082230.3c88b00c@gandalf.local.home> X-Mailer: Claws Mail 3.20.0git84 (GTK+ 2.24.33; x86_64-pc-linux-gnu) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-Stat-Signature: 5w7yyqsg3shw8jzkcbef7fma9wwpmiph X-Rspamd-Server: rspamout02 X-Rspamd-Queue-Id: 8FC7F60016 X-Session-Marker: 726F737465647440676F6F646D69732E6F7267 X-Session-ID: U2FsdGVkX182O56zwS0VWl1yudZiOH/Ikhn8EHz1CaI= X-HE-Tag: 1775132488-271079 X-HE-Meta: U2FsdGVkX1/mlkHgyLcL9VqQklUOYiGGEsTWOmgMYebbpNlwW+9Xeq6lLgRnv1a2HFG2gMTPaB8eAEGumI6sQvt4KKcsWFgeSSWwV/dc9LeTLQX+GWu5G3+n/nDh+hl5epAXekJGSy+VoyB2enXYq+bYQ0eebKlet8dQkVOZUOvFaxU84VgpLC26/auzRg+m/DIkeCerUALWgnk9sT/GLnxqSoQwnyJ589CCoHZ/TJAxGtLTBJ8m5HpNRq9obLXHcqIhV8087LbRwktvA2yQVhXm7/nL7Bh1PWaBS8q9+pH2KnVoO3ynG+mqARwT8CvCRrKBymJE3cIcQfm+k1B15GCfdClNHRWZWrJ0O+CHOGAHbiGbn+sElYbyrdzodky7bXHOA8uWCJA2wuJjiaekSnDusHH2GKSDp0YfEEenb737gDM3qqFGJf8vii7fU3tbrgrlgRQfsvTY+J4KzJcCdbOrVBPP2E0gZFhJuf1F60PzsL9vWVtl6v5lcQmvuc4D Content-Type: text/plain; charset="utf-8" git://git.kernel.org/pub/scm/linux/kernel/git/trace/linux-trace.git ftrace/for-next Head SHA1: 93e8fd1a565eb5d0c0bbcb18d00095ad255b6ecb Andrey Grodzovsky (1): ftrace: Use kallsyms binary search for single-symbol lookup ---- kernel/trace/ftrace.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) --------------------------- commit 93e8fd1a565eb5d0c0bbcb18d00095ad255b6ecb Author: Andrey Grodzovsky Date: Mon Mar 2 15:08:36 2026 -0500 ftrace: Use kallsyms binary search for single-symbol lookup =20 When ftrace_lookup_symbols() is called with a single symbol (cnt =3D=3D= 1), use kallsyms_lookup_name() for O(log N) binary search instead of the full linear scan via kallsyms_on_each_symbol(). =20 ftrace_lookup_symbols() was designed for batch resolution of many symbols in a single pass. For large cnt this is efficient: a single O(N) walk over all symbols with O(log cnt) binary search into the sorted input array. But for cnt =3D=3D 1 it still decompresses all ~20= 0K kernel symbols only to match one. =20 kallsyms_lookup_name() uses the sorted kallsyms index and needs only ~17 decompressions for a single lookup. =20 This is the common path for kprobe.session with exact function names, where libbpf sends one symbol per BPF_LINK_CREATE syscall. =20 If binary lookup fails (duplicate symbol names where the first match is not ftrace-instrumented), the function falls through to the existing linear scan path. =20 Before (cnt=3D1, 50 kprobe.session programs): Attach: 858 ms (kallsyms_expand_symbol 25% of CPU) =20 After: Attach: 52 ms (16x faster) =20 Cc: Link: https://patch.msgid.link/20260302200837.317907-3-andrey.grodzovsk= y@crowdstrike.com Signed-off-by: Andrey Grodzovsky Signed-off-by: Steven Rostedt (Google) diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c index 413310912609..7eac1472cc57 100644 --- a/kernel/trace/ftrace.c +++ b/kernel/trace/ftrace.c @@ -9267,6 +9267,15 @@ static int kallsyms_callback(void *data, const char = *name, unsigned long addr) * @addrs array, which needs to be big enough to store at least @cnt * addresses. * + * For a single symbol (cnt =3D=3D 1), uses kallsyms_lookup_name() which + * performs an O(log N) binary search via the sorted kallsyms index. + * This avoids the full O(N) linear scan over all kernel symbols that + * the multi-symbol path requires. + * + * For multiple symbols, uses a single-pass linear scan via + * kallsyms_on_each_symbol() with binary search into the sorted input + * array. + * * Returns: 0 if all provided symbols are found, -ESRCH otherwise. */ int ftrace_lookup_symbols(const char **sorted_syms, size_t cnt, unsigned l= ong *addrs) @@ -9274,6 +9283,19 @@ int ftrace_lookup_symbols(const char **sorted_syms, = size_t cnt, unsigned long *a struct kallsyms_data args; int found_all; =20 + /* Fast path: single symbol uses O(log N) binary search */ + if (cnt =3D=3D 1) { + addrs[0] =3D kallsyms_lookup_name(sorted_syms[0]); + if (addrs[0] && ftrace_location(addrs[0])) + return 0; + /* + * Binary lookup can fail for duplicate symbol names + * where the first match is not ftrace-instrumented. + * Retry with linear scan. + */ + } + + /* Batch path: single-pass O(N) linear scan */ memset(addrs, 0, sizeof(*addrs) * cnt); args.addrs =3D addrs; args.syms =3D sorted_syms;