From: Jiri Olsa <jolsa@kernel.org>
To: Masami Hiramatsu <mhiramat@kernel.org>,
Naveen N Rao <naveen@kernel.org>,
"David S. Miller" <davem@davemloft.net>
Cc: Peter Zijlstra <peterz@infradead.org>,
Josh Poimboeuf <jpoimboe@kernel.org>,
Jason Baron <jbaron@akamai.com>,
Alice Ryhl <aliceryhl@google.com>,
Steven Rostedt <rostedt@goodmis.org>,
Ard Biesheuvel <ardb@kernel.org>,
Thomas Gleixner <tglx@kernel.org>, Ingo Molnar <mingo@redhat.com>,
Alan Maguire <almagui@kernel.org>,
x86@kernel.org, linux-trace-kernel@vger.kernel.org,
linux-kernel@vger.kernel.org, bpf@vger.kernel.org
Subject: [PATCH 04/13] kprobes: Maintain an rbtree of registered probes
Date: Mon, 9 Nov 2026 20:55:17 +0100 [thread overview]
Message-ID: <20261109195517.1090787-1-jolsa@kernel.org> (raw)
In-Reply-To: <20261109194916.1089703-1-jolsa@kernel.org>
Add an address-ordered rbtree for registered probes. Keep it synchronized
with the hash table when probes are added, removed, or replaced by
aggregator probes.
Signed-off-by: Jiri Olsa <jolsa@kernel.org>
---
include/linux/kprobes.h | 2 ++
kernel/kprobes.c | 49 +++++++++++++++++++++++++++++++++++++++++
2 files changed, 51 insertions(+)
diff --git a/include/linux/kprobes.h b/include/linux/kprobes.h
index e6de7ae55bda..6f16cc01a16c 100644
--- a/include/linux/kprobes.h
+++ b/include/linux/kprobes.h
@@ -28,6 +28,7 @@
#include <linux/ftrace.h>
#include <linux/objpool.h>
#include <linux/rethook.h>
+#include <linux/rbtree.h>
#include <asm/kprobes.h>
#ifdef CONFIG_KPROBES
@@ -58,6 +59,7 @@ typedef int (*kretprobe_handler_t) (struct kretprobe_instance *,
struct kprobe {
struct hlist_node hlist;
+ struct rb_node rb_node;
/* list of kprobes for multi-handler support */
struct list_head list;
diff --git a/kernel/kprobes.c b/kernel/kprobes.c
index 2441b9e39343..6be1430a4ebe 100644
--- a/kernel/kprobes.c
+++ b/kernel/kprobes.c
@@ -64,6 +64,7 @@ static int kprobes_initialized;
* - RCU hlist traversal under disabling preempt (breakpoint handlers)
*/
static struct hlist_head kprobe_table[KPROBE_TABLE_SIZE];
+static struct rb_root kprobe_tree = RB_ROOT;
/* NOTE: change this value only with 'kprobe_mutex' held */
static bool kprobes_all_disarmed;
@@ -395,6 +396,45 @@ struct kprobe *get_kprobe(void *addr)
}
NOKPROBE_SYMBOL(get_kprobe);
+static void kprobe_tree_insert(struct kprobe *p)
+{
+ struct rb_node **link = &kprobe_tree.rb_node, *parent = NULL;
+ unsigned long addr = (unsigned long)p->addr;
+
+ lockdep_assert_held(&kprobe_mutex);
+ while (*link) {
+ struct kprobe *kp = rb_entry(*link, struct kprobe, rb_node);
+ unsigned long kp_addr = (unsigned long)kp->addr;
+
+ parent = *link;
+ if (addr < kp_addr)
+ link = &(*link)->rb_left;
+ else if (addr > kp_addr)
+ link = &(*link)->rb_right;
+ else {
+ WARN_ON_ONCE(1);
+ return;
+ }
+ }
+
+ rb_link_node(&p->rb_node, parent, link);
+ rb_insert_color(&p->rb_node, &kprobe_tree);
+}
+
+static void kprobe_tree_erase(struct kprobe *p)
+{
+ lockdep_assert_held(&kprobe_mutex);
+ rb_erase(&p->rb_node, &kprobe_tree);
+ RB_CLEAR_NODE(&p->rb_node);
+}
+
+static void kprobe_tree_replace(struct kprobe *old, struct kprobe *new)
+{
+ lockdep_assert_held(&kprobe_mutex);
+ rb_replace_node(&old->rb_node, &new->rb_node, &kprobe_tree);
+ RB_CLEAR_NODE(&old->rb_node);
+}
+
static int aggr_pre_handler(struct kprobe *p, struct pt_regs *regs);
/* Return true if 'p' is an aggregator */
@@ -643,6 +683,7 @@ static void do_unoptimize_kprobes(struct list_head *unopt_list,
* (reclaiming is done by do_free_cleaned_kprobes().)
*/
hlist_del_init_rcu(&op->kp.hlist);
+ kprobe_tree_erase(&op->kp);
} else {
/*
* Keep on cooling_list until the quiescence period
@@ -722,6 +763,7 @@ static void optprobe_finalize_generation(struct optprobe_generation *gen)
* it will be reclaimed after the next quiescence period.
*/
hlist_del_init_rcu(&op->kp.hlist);
+ kprobe_tree_erase(&op->kp);
list_move(&op->list, &optprobe_gens[optprobe_cur_gen].freeing_list);
kick_kprobe_optimizer();
} else {
@@ -1006,6 +1048,7 @@ static void unoptimize_kprobe(struct kprobe *p, bool force)
if (!kprobe_gone(&op->kp))
arch_disarm_kprobe(&op->kp);
hlist_del_init_rcu(&op->kp.hlist);
+ kprobe_tree_erase(&op->kp);
list_move(&op->list, &cur->freeing_list);
} else {
list_move(&op->list, &cur->cooling_list);
@@ -1021,6 +1064,7 @@ static void unoptimize_kprobe(struct kprobe *p, bool force)
if (!kprobe_gone(&op->kp))
arch_disarm_kprobe(&op->kp);
hlist_del_init_rcu(&op->kp.hlist);
+ kprobe_tree_erase(&op->kp);
list_move(&op->list, &cur->freeing_list);
kick_kprobe_optimizer();
}
@@ -1076,6 +1120,7 @@ static void kill_optimized_kprobe(struct kprobe *p)
if (kprobe_unused(p)) {
if (optprobe_queued_unopt(op) || optprobe_queued_cooling(op)) {
hlist_del_init_rcu(&op->kp.hlist);
+ kprobe_tree_erase(&op->kp);
list_move(&op->list,
&optprobe_gens[optprobe_cur_gen].freeing_list);
kick_kprobe_optimizer();
@@ -1599,6 +1644,7 @@ static void init_aggr_kprobe(struct kprobe *ap, struct kprobe *p)
list_add_rcu(&p->list, &ap->list);
hlist_replace_rcu(&p->hlist, &ap->hlist);
+ kprobe_tree_replace(p, ap);
}
/*
@@ -1940,11 +1986,13 @@ static int __register_kprobe(struct kprobe *p)
INIT_HLIST_NODE(&p->hlist);
hlist_add_head_rcu(&p->hlist,
&kprobe_table[hash_ptr(p->addr, KPROBE_HASH_BITS)]);
+ kprobe_tree_insert(p);
if (!kprobes_all_disarmed && !kprobe_disabled(p)) {
ret = arm_kprobe(p);
if (ret) {
hlist_del_rcu(&p->hlist);
+ kprobe_tree_erase(p);
synchronize_rcu();
}
}
@@ -2075,6 +2123,7 @@ static int __unregister_kprobe_top(struct kprobe *p)
* unoptimizing.
*/
hlist_del_rcu(&ap->hlist);
+ kprobe_tree_erase(ap);
return 0;
}
--
2.43.0
next prev parent reply other threads:[~2026-11-09 19:55 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-09 19:49 [PATCH 00/13] kprobes: Reduce registration and optimization lookup costs Jiri Olsa
2026-11-09 19:49 ` [PATCH 01/13] static_call: Index code text reservation lookups Jiri Olsa
2026-11-09 19:49 ` [PATCH 02/13] jump_label: Index " Jiri Olsa
2026-11-09 19:49 ` [PATCH 03/13] jump_label/x86: Avoid decoding instructions for jump entry size Jiri Olsa
2026-11-09 19:55 ` Jiri Olsa [this message]
2026-11-09 19:56 ` [PATCH 05/13] kprobes: Add an iterator for address ranges Jiri Olsa
2026-11-09 19:56 ` [PATCH 06/13] kprobes: Add an address iterator for probe lookup Jiri Olsa
2026-11-09 19:56 ` [PATCH 07/13] kprobes: Use kprobe iterator in get_optimized_kprobe Jiri Olsa
2026-11-09 19:57 ` [PATCH 08/13] x86/kprobes: Use kprobe iterator in __recover_optprobed_insn Jiri Olsa
2026-11-09 19:57 ` [PATCH 09/13] x86/kprobes: Use kprobe iterator in arch_check_optimized_kprobe Jiri Olsa
2026-11-09 19:57 ` [PATCH 10/13] x86/kprobes: Use kprobe address iterator in can_optimize Jiri Olsa
2026-11-09 19:57 ` [PATCH 11/13] x86/kprobes: Use kprobe address iterator in can_probe Jiri Olsa
2026-11-09 19:58 ` [PATCH 12/13] x86/kprobes: Use kprobe address iterator in in copy_optimized_instructions Jiri Olsa
2026-11-09 19:58 ` [PATCH 13/13] samples/kprobes: Add batch probe example Jiri Olsa
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261109195517.1090787-1-jolsa@kernel.org \
--to=jolsa@kernel.org \
--cc=aliceryhl@google.com \
--cc=almagui@kernel.org \
--cc=ardb@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=davem@davemloft.net \
--cc=jbaron@akamai.com \
--cc=jpoimboe@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-trace-kernel@vger.kernel.org \
--cc=mhiramat@kernel.org \
--cc=mingo@redhat.com \
--cc=naveen@kernel.org \
--cc=peterz@infradead.org \
--cc=rostedt@goodmis.org \
--cc=tglx@kernel.org \
--cc=x86@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®