Re: [PATCH 04/13] kprobes: Maintain an rbtree of registered probes

[Jiri Olsa <olsajiri@gmail.com>]

On Tue, Nov 10, 2026 at 08:12:19AM +0000, Masami Hiramatsu (Google) wrote:
> On Mon,  9 Nov 2026 20:55:17 +0100, Jiri Olsa <jolsa@kernel.org> wrote:
> > 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.
> 
> Could you tell me why don't you use hlist (get_kprobe) instead?
> I would NOT like 2 different lists which is basically doing the
> same thing.

The speedup comes from finding the first relevant kprobe, then iterating
over the remaining probes in address order. The hash table supports
exact-address lookups, but it doesn’t provide that ordering.

I agree that maintaining both indexes is less convenient. What do you think
about centralizing their updates as in the change below? untested

jirka


---
diff --git a/kernel/kprobes.c b/kernel/kprobes.c
index 371ecc7d5b54..7868d8610b5f 100644
--- a/kernel/kprobes.c
+++ b/kernel/kprobes.c
@@ -435,6 +435,30 @@ static void kprobe_tree_replace(struct kprobe *old, struct kprobe *new)
 	RB_CLEAR_NODE(&old->rb_node);
 }
 
+static void add_kprobe(struct kprobe *p)
+{
+	lockdep_assert_held(&kprobe_mutex);
+	INIT_HLIST_NODE(&p->hlist);
+	hlist_add_head_rcu(&p->hlist,
+			   &kprobe_table[hash_ptr(p->addr, KPROBE_HASH_BITS)]);
+	kprobe_tree_insert(p);
+}
+
+static void remove_kprobe(struct kprobe *p)
+{
+	lockdep_assert_held(&kprobe_mutex);
+	hlist_del_init_rcu(&p->hlist);
+	kprobe_tree_erase(p);
+}
+
+static void replace_kprobe(struct kprobe *old, struct kprobe *new)
+{
+	lockdep_assert_held(&kprobe_mutex);
+	INIT_HLIST_NODE(&new->hlist);
+	hlist_replace_rcu(&old->hlist, &new->hlist);
+	kprobe_tree_replace(old, new);
+}
+
 struct kprobe *kprobe_iter_start(struct kprobe_iter *iter, unsigned long start,
 				 unsigned long end)
 {
@@ -751,8 +775,7 @@ static void do_unoptimize_kprobes(struct list_head *unopt_list,
 			 * for synchronization, these probes are reclaimed.
 			 * (reclaiming is done by do_free_cleaned_kprobes().)
 			 */
-			hlist_del_init_rcu(&op->kp.hlist);
-			kprobe_tree_erase(&op->kp);
+			remove_kprobe(&op->kp);
 		} else {
 			/*
 			 * Keep on cooling_list until the quiescence period
@@ -831,8 +854,7 @@ static void optprobe_finalize_generation(struct optprobe_generation *gen)
 			 * Unhash it now and move to cur_gen's freeing list so
 			 * it will be reclaimed after the next quiescence period.
 			 */
-			hlist_del_init_rcu(&op->kp.hlist);
-			kprobe_tree_erase(&op->kp);
+			remove_kprobe(&op->kp);
 			list_move(&op->list, &optprobe_gens[optprobe_cur_gen].freeing_list);
 			kick_kprobe_optimizer();
 		} else {
@@ -1116,8 +1138,7 @@ static void unoptimize_kprobe(struct kprobe *p, bool force)
 				if (kprobe_unused(&op->kp)) {
 					if (!kprobe_gone(&op->kp))
 						arch_disarm_kprobe(&op->kp);
-					hlist_del_init_rcu(&op->kp.hlist);
-					kprobe_tree_erase(&op->kp);
+					remove_kprobe(&op->kp);
 					list_move(&op->list, &cur->freeing_list);
 				} else {
 					list_move(&op->list, &cur->cooling_list);
@@ -1132,8 +1153,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);
+				remove_kprobe(&op->kp);
 				list_move(&op->list, &cur->freeing_list);
 				kick_kprobe_optimizer();
 			}
@@ -1188,8 +1208,7 @@ static void kill_optimized_kprobe(struct kprobe *p)
 	if (!list_empty(&op->list)) {
 		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);
+				remove_kprobe(&op->kp);
 				list_move(&op->list,
 					  &optprobe_gens[optprobe_cur_gen].freeing_list);
 				kick_kprobe_optimizer();
@@ -1709,11 +1728,9 @@ static void init_aggr_kprobe(struct kprobe *ap, struct kprobe *p)
 		ap->post_handler = aggr_post_handler;
 
 	INIT_LIST_HEAD(&ap->list);
-	INIT_HLIST_NODE(&ap->hlist);
 
 	list_add_rcu(&p->list, &ap->list);
-	hlist_replace_rcu(&p->hlist, &ap->hlist);
-	kprobe_tree_replace(p, ap);
+	replace_kprobe(p, ap);
 }
 
 /*
@@ -2052,16 +2069,12 @@ static int __register_kprobe(struct kprobe *p)
 			return ret;
 	}
 
-	INIT_HLIST_NODE(&p->hlist);
-	hlist_add_head_rcu(&p->hlist,
-		       &kprobe_table[hash_ptr(p->addr, KPROBE_HASH_BITS)]);
-	kprobe_tree_insert(p);
+	add_kprobe(p);
 
 	if (!kprobes_all_disarmed && !kprobe_disabled(p)) {
 		ret = arm_kprobe(p);
 		if (ret) {
-			hlist_del_rcu(&p->hlist);
-			kprobe_tree_erase(p);
+			remove_kprobe(p);
 			synchronize_rcu();
 		}
 	}
@@ -2191,8 +2204,7 @@ static int __unregister_kprobe_top(struct kprobe *p)
 		 * !disarmed could be happen if the probe is under delayed
 		 * unoptimizing.
 		 */
-		hlist_del_rcu(&ap->hlist);
-		kprobe_tree_erase(ap);
+		remove_kprobe(ap);
 		return 0;
 	}