Re: [PATCH -tip v5 00/10] kprobes: Kprobes jump optimization support

Frederic Weisbecker
2009-11-24T02:09:27Z

On Mon, Nov 23, 2009 at 06:21:16PM -0500, Masami Hiramatsu wrote:
> Hi,
>
> Here are the patchset of the kprobes jump optimization v5
> (a.k.a. Djprobe). Since it is not ensured that the int3 bypassing
> cross modifying code is safe on any processors yet, I introduced
> stop_machine() version of XMC. Using stop_machine() will disable
> us to probe NMI codes, but anyway, kprobes itself can't probe
> those codes. So, it's not a problem. This version also includes
> get/put_online_cpus() around optimization for avoiding deadlock
> of text_mutex.
>
> These patches can be applied on the latest -tip.
>
> Changes in v5:
> - Use stop_machine() to replace a breakpoint with a jump.
> - get/put_online_cpus() around optimization.
> - Make generic jump patching interface RFC.
>
> And kprobe stress test didn't found any regressions - from kprobes,
> under kvm/x86.
>
> Jump Optimized Kprobes
> ======================
> o Concept
> Kprobes uses the int3 breakpoint instruction on x86 for instrumenting
> probes into running kernel. Jump optimization allows kprobes to replace
> breakpoint with a jump instruction for reducing probing overhead drastically.
>
> o Performance
> An optimized kprobe 5 times faster than a kprobe.
>
> Optimizing probes gains its performance. Usually, a kprobe hit takes
> 0.5 to 1.0 microseconds to process. On the other hand, a jump optimized
> probe hit takes less than 0.1 microseconds (actual number depends on the
> processor). Here is a sample overheads.
>
> Intel(R) Xeon(R) CPU E5410 @ 2.33GHz (without debugging options)
>
> x86-32 x86-64
> kprobe: 0.68us 0.91us
> kprobe+booster: 0.27us 0.40us
> kprobe+optimized: 0.06us 0.06us
>
> kretprobe : 0.95us 1.21us
> kretprobe+booster: 0.53us 0.71us
> kretprobe+optimized: 0.30us 0.35us
>
> (booster skips single-stepping)
>
> Note that jump optimization also consumes more memory, but not so much.
> It just uses ~200 bytes, so, even if you use ~10,000 probes, it just
> consumes a few MB.

Nice results.

But I have troubles to figure out the difference between booster version and
optimized version.

> o Optimization
> Before preparing optimization, Kprobes inserts original(user-defined)
> kprobe on the specified address. So, even if the kprobe is not
> possible to be optimized, it just uses a normal kprobe.
>
> - Safety check
> First, Kprobes gets the address of probed function and checks whether the
> optimized region, which will be replaced by a jump instruction, does NOT
> straddle the function boundary, because if the optimized region reaches the
> next function, its caller causes unexpected results.
> Next, Kprobes decodes whole body of probed function and checks there is
> NO indirect jump, NO instruction which will cause exception by checking
> exception_tables (this will jump to fixup code and fixup code jumps into
> same function body) and NO near jump which jumps into the optimized region
> (except the 1st byte of jump), because if some jump instruction jumps
> into the middle of another instruction, it causes unexpected results too.
> Kprobes also measures the length of instructions which will be replaced
> by a jump instruction, because a jump instruction is longer than 1 byte,
> it may replaces multiple instructions, and it checks whether those
> instructions can be executed out-of-line.
>
> - Preparing detour code
> Then, Kprobes prepares "detour" buffer, which contains exception emulating
> code (push/pop registers, call handler), copied instructions(Kprobes copies
> instructions which will be replaced by a jump, to the detour buffer), and
> a jump which jumps back to the original execution path.
>
> - Pre-optimization
> After preparing detour code, Kprobes enqueues the kprobe to optimizing list
> and kicks kprobe-optimizer workqueue to optimize it. To wait other optimized
> probes, kprobe-optimizer will delay to work.

Hmm, so it waits for, actually, non-optimized probes to finish, right?
The site for which you have built up a detour buffer has an int3 in place
that could have kprobes in processing and your are waiting for them
to complete before patching with the jump?

> When the optimized-kprobe is hit before optimization, its handler
> changes IP(instruction pointer) to copied code and exits. So, the
> instructions which were copied to detour buffer are executed on the detour
> buffer.

Hm, why is it playing such hybrid game there?
If I understand well, we have executed int 3, executed the
handler and we jump back to the detour buffer?

> - Optimization
> Kprobe-optimizer doesn't start instruction-replacing soon, it waits
> synchronize_sched for safety, because some processors are possible to be
> interrupted on the instructions which will be replaced by a jump instruction.
> As you know, synchronize_sched() can ensure that all interruptions which were
> executed when synchronize_sched() was called are done, only if
> CONFIG_PREEMPT=n. So, this version supports only the kernel with
> CONFIG_PREEMPT=n.(*)
> After that, kprobe-optimizer replaces the 4 bytes right after int3 breakpoint
> with relative-jump destination, and synchronize caches on all processors. Next,
> it replaces int3 with relative-jump opcode, and synchronize caches again.

You said you now use stop_machine() to patch the jumps, which looks the only
safe way to do that. May be the above explanation is out of date?

> - Unoptimization
> When unregistering, disabling kprobe or being blocked by other kprobe,
> an optimized-kprobe will be unoptimized. Before kprobe-optimizer runs,
> the kprobe just be dequeued from the optimized list. When the optimization
> has been done, it replaces a jump with int3 breakpoint and original code.
> First it puts int3 at the first byte of the jump, synchronize caches
> on all processors, and replaces the 4 bytes right after int3 with the
> original code.
>
> (*)This optimization-safety checking may be replaced with stop-machine method
> which ksplice is done for supporting CONFIG_PREEMPT=y kernel.

And now that you use get_cpu()/put_cpu(), I guess this config
option is not required anymore.

I don't understand why the int 3 is still required in the sequence.

- Registration: You first patch the site with int 3, then try the jump
and use the int 3 as a gate to protect your patching.

- Unregistration: Same in reverse

You are doing a live patching while the code might be running concurrently
which requires a very tricky surgery, based on a int 3 gate and rcu as you
describe above.
But do we need to play such dangerous (and complicated) game.
I mean, it's like training to be a tightrope walker while we have a
bridge just beside :)
Why not running stop_machine(), first trying the jump directly, patching
it if it's considered safe, otherwise patching with int 3?

But you said you are using stop_machine() in the v5 changelog,
I should probably first look at the patches :)

Thanks.