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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [High] kprobes: double rb_erase() in kprobe_tree_erase() via
  freeing_list
It also noticed 2 related pre-existing issues this patch does not
introduce:
- [Critical] kprobes: missing cooling delay on forced unoptimization in
  unoptimize_kprobe() [1]
- [Critical] kprobes: premature optinsn slot free in
  kill_optimized_kprobe() [2]
--

commit 8d3f55a56b4caad208426449cba53c9ca99b1316
Author: Jiri Olsa <jolsa@kernel.org>

kprobes: Maintain an rbtree of registered probes

This commit adds an address-ordered rbtree for registered kprobes and
keeps it synchronized with kprobe_table across probe insertion, removal,
and aggregator replacement.

> diff --git a/kernel/kprobes.c b/kernel/kprobes.c
> index 2441b9e393438..6be1430a4ebe9 100644
> --- a/kernel/kprobes.c
> +++ b/kernel/kprobes.c
[ ... ]
> @@ -395,6 +396,45 @@ struct kprobe *get_kprobe(void *addr)
>  }
>  NOKPROBE_SYMBOL(get_kprobe);
>  
[ ... ]
> +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);
> +}
[ ... ]
> @@ -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 {

[Severity: High]
Can this regression call rb_erase() twice on &op->kp.rb_node and corrupt
kprobe_tree?

When an unused optimized_kprobe is queued onto freeing_list (for example in
optprobe_finalize_generation(), unoptimize_kprobe(), or
kill_optimized_kprobe()), it calls hlist_del_init_rcu(&op->kp.hlist) and
kprobe_tree_erase(&op->kp).  When optprobe_dispatch_generation() later
dispatches that generation, do_unoptimize_kprobes() walks freeing_list and
calls both functions again on the same probe.

Unlike hlist_del_init_rcu(), which checks !hlist_unhashed(),
kprobe_tree_erase() does not check !RB_EMPTY_NODE(&p->rb_node) before
calling rb_erase().  Because the first erase leaves stale child pointers in
rb_node and sets its parent to itself, the second rb_erase() links live
kprobe_tree nodes to the about-to-be-freed op->kp.rb_node.

> @@ -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();
>  			}

[Severity: Critical]
This problem wasn't introduced by this patch, but in unoptimize_kprobe()
[1], can forced unoptimization of an already-optimized probe free
the probe and its detour trampoline before preempted tasks exit it?

kernel/kprobes.c:unoptimize_kprobe() {
	...
	if (!kprobe_optimized(p))
		return;

	/* Optimized kprobe case */
	if (force) {
		/* Forcibly update the code: this is a special case */
		force_unoptimize_kprobe(op);
	} else {
		list_add(&op->list, &cur->unoptimizing_list);
		kick_kprobe_optimizer();
	}
}

Once a probe finishes optimizing, KPROBE_FLAG_OPTIMIZED is set and op->list
is empty.  When unoptimize_kprobe(p, true) runs (such as from
add_new_kprobe() or disarm_all_kprobes()), force_unoptimize_kprobe(op)
patches the jump back to a breakpoint and clears KPROBE_FLAG_OPTIMIZED,
leaving op->list empty instead of queueing op onto cur->cooling_list.

A subsequent unregister_kprobe() sees kprobe_disarmed(ap) evaluate to true
in __unregister_kprobe_top(), unhashes and erases ap immediately, and waits
only for synchronize_rcu() before freeing struct optimized_kprobe and its
trampoline slot without waiting for a Tasks RCU grace period.  If a task was
preempted inside the detour trampoline before the jump was patched, it
triggers a use-after-free when it resumes.

> @@ -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();

[Severity: Critical]
This problem wasn't introduced by this patch, but in
kill_optimized_kprobe() [2], can killing an aggregator probe that
still has child probes free its optinsn slot while tasks are still
preempted inside the trampoline?

kernel/kprobes.c:kill_optimized_kprobe() {
	...
	if (!list_empty(&op->list)) {
		if (kprobe_unused(p)) {
			...
		} else {
			list_del_init(&op->list);
		}
	}
	op->kp.flags &= ~KPROBE_FLAG_OPTIMIZED;

	if (!optprobe_queued_freeing(op) && !optprobe_queued_unopt(op) &&
	    !optprobe_queued_cooling(op))
		arch_remove_optimized_kprobe(op);
}

When kill_kprobe() is called on an aggregator probe that is queued on
unoptimizing_list or cooling_list and still has child probes
(!kprobe_unused(p)), the else branch runs list_del_init(&op->list).  Because
optprobe_queued_unopt() and optprobe_queued_cooling() check queue membership
by walking those lists, detaching op->list first makes both checks return
false.  arch_remove_optimized_kprobe() then frees the detour buffer
immediately without waiting for the pending Tasks RCU grace period.

[1] https://sashiko.dev/#/bug/linux-f9b316b8-64c0-4c88-8de2-81f70a772f7b
[2] https://sashiko.dev/#/bug/linux-cc62e94b-a020-483a-84cb-52080d1d23a0

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261109194916.1089703-1-jolsa@kernel.org?part=4