Skip to content

kprobes: Kprobes jump optimization support

Masami Hiramatsu lkml 10 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v10 Latest9 patches 5 repliesIn review
  2. v99 patches 0 repliesSuperseded
  3. v89 patches 2 repliesSuperseded
Earlier versions · 7
VersionPostedPatchesRepliesStatus
v711 patches0 repliesSuperseded
v611 patches2 repliesSuperseded
v510 patches26 repliesSuperseded
v4 RFC9 patches0 repliesSuperseded
v3 RFC7 patches0 repliesSuperseded
v2 RFC7 patches21 repliesSuperseded
v1 RFC6 patches4 repliesSuperseded

Changes in v10 from the cover letter

- Editorial update by Jim Keniston.

Patches in v10 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/9kprobes/x86: Cleanup RELATIVEJUMP_INSTRUCTION to RELATIVEJUMP_OPCODEarch/x86/include/asm/kprobes.h arch/x86/kernel/kprobes.c+2 -20 replies
2/9kprobes: Introduce generic insn_slot frameworkkernel/kprobes.c+65 -390 replies
3/9kprobes: Introduce kprobes jump optimizationarch/Kconfig include/linux/kprobes.h kernel/kprobes.c+459 -510 replies
4/9kprobes: Jump optimization sysctl interfaceinclude/linux/kprobes.h kernel/kprobes.c kernel/sysctl.c+105 -30 replies
5/9kprobes/x86: Boost probes when reenteringarch/x86/kernel/kprobes.c+26 -220 replies
6/9kprobes/x86: Cleanup save/restore registersarch/x86/kernel/kprobes.c+67 -610 replies
7/9x86: Add text_poke_smp for SMP cross modifying codearch/x86/include/asm/alternative.h arch/x86/kernel/alternative.c+63 -10 replies
8/9kprobes/x86: Support kprobes jump optimization on x86arch/x86/Kconfig arch/x86/include/asm/kprobes.h arch/x86/kernel/kprobes.c+441 -220 replies
9/9kprobes: Add documents of jump optimizationDocumentation/kprobes.txt+195 -120 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v10 yet.

Read the v10 thread

Cover letter [PATCH -tip v10 0/9] kprobes: Kprobes jump optimization support

Hi Ingo,

Here are the patchset of the kprobes jump optimization v10 (a.k.a. Djprobe). This version just updated a document, and applicable for 2.6.33-rc8-tip.

This version of patch series uses text_poke_smp() which update kernel text by stop_machine(). That is 'officially' supported on Intel's processors. text_poke_smp() can't be used for modifying NMI code, but, fortunately:), kprobes also can't probe NMI code. Thus, kprobes jump-optimization can use it.
(Int3-bypassing method (text_poke_fixup()) is still unofficial
and we need to get more official answers from x86 vendors.)

Changes in v10:
- Editorial update by Jim Keniston.

And kprobe stress test didn't found any regressions - from kprobes, under kvm/x86.

TODO:
- Support NMI-safe int3-bypassing text_poke.
- Support preemptive kernel (by stack unwinding and checking address).

How to use it
=============

The jump replacement optimization is transparently done in kprobes. So, if you enables CONFIG_KPROBE_EVENT(a.k.a. kprobe-tracer) in kernel config, you can use it via kprobe_events interface.

e.g.

 # echo p:probe1 schedule > /sys/kernel/debug/tracing/kprobe_evnets
 # cat /sys/kernel/debug/kprobes/list
 c069ce4c  k  schedule+0x0    [DISABLED]
 # echo 1 > /sys/kernel/debug/tracing/events/kprobes/probe1/enable
 # cat /sys/kernel/debug/kprobes/list
 c069ce4c  k  schedule+0x0    [OPTIMIZED]

Note:
Which probe can be optimized is depends on the actual kernel binary. So, in some cases, it might not be optimized. Please try to probe another place in that case.

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 is about 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, with text_poke_smp patch, 2.6.33-rc4-tip+)

			x86-32  x86-64

kprobe: 0.80us 0.99us
kprobe+booster: 0.33us 0.43us
kprobe+optimized: 0.05us 0.06us
kprobe(post-handler): 0.81us 1.00us

kretprobe : 1.10us 1.24us
kretprobe+booster: 0.61us 0.68us
kretprobe+optimized: 0.33us 0.30us

jprobe: 1.37us 1.67us
jprobe+booster: 0.80us 1.10us

(booster skips single-stepping, kprobe with post handler
isn't boosted/optimized, and jprobe isn't optimized.)

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.

o Usage
If you configured your kernel with CONFIG_OPTPROBES=y (currently
this option is supported on x86/x86-64, non-preemptive kernel) and the "debug.kprobes_optimization" kernel parameter is set to 1 (see sysctl(8)), Kprobes tries to reduce probe-hit overhead by using a jump instruction instead of a breakpoint instruction at each probepoint.

o Optimization
When a probe is registered, before attempting this optimization,
Kprobes inserts an ordinary, breakpoint-based kprobe at the specified address. So, even if it's not possible to optimize this particular probepoint, there'll be a probe there.

- Safety check
Before optimizing a probe, Kprobes performs the following safety checks:

- Kprobes verifies that the region that will be replaced by the jump instruction (the "optimized region") lies entirely within one function. (A jump instruction is multiple bytes, and so may overlay multiple instructions.)

- Kprobes analyzes the entire function and verifies that there is no jump into the optimized region. Specifically:
- the function contains no indirect jump;
- the function contains no instruction that causes an exception (since the fixup code triggered by the exception could jump back into the optimized region -- Kprobes checks the exception tables to verify this); and
- there is no near jump to the optimized region (other than to the first byte).

- For each instruction in the optimized region, Kprobes verifies that the instruction can be executed out of line.

- Preparing detour code
Next, Kprobes prepares a "detour" buffer, which contains the following instruction sequence:
- code to push the CPU's registers (emulating a breakpoint trap)
- a call to the trampoline code which calls user's probe handlers.
- code to restore registers
- the instructions from the optimized region
- a jump back to the original execution path.

- Pre-optimization
After preparing the detour buffer, Kprobes verifies that none of the following situations exist:
- The probe has either a break_handler (i.e., it's a jprobe) or a post_handler.
- Other instructions in the optimized region are probed.
- The probe is disabled.
In any of the above cases, Kprobes won't start optimizing the probe. Since these are temporary situations, Kprobes tries to start optimizing it again if the situation is changed.

If the kprobe can be optimized, Kprobes enqueues the kprobe to an optimizing list, and kicks the kprobe-optimizer workqueue to optimize it. If the to-be-optimized probepoint is hit before being optimized, Kprobes returns control to the original instruction path by setting the CPU's instruction pointer to the copied code in the detour buffer -- thus at least avoiding the single-step.

- Optimization
The Kprobe-optimizer doesn't insert the jump instruction immediately; rather, it calls synchronize_sched() for safety first, because it's possible for a CPU to be interrupted in the middle of executing the optimized region(*). As you know, synchronize_sched() can ensure that all interruptions that were active when synchronize_sched() was called are done, but only if CONFIG_PREEMPT=n. So, this version of kprobe optimization supports only kernels with CONFIG_PREEMPT=n.(**)

After that, the Kprobe-optimizer calls stop_machine() to replace the optimized region with a jump instruction to the detour buffer, using text_poke_smp().

- Unoptimization
When an optimized kprobe is unregistered, disabled, or blocked by another kprobe, it will be unoptimized. If this happens before the optimization is complete, the kprobe is just dequeued from the optimized list. If the optimization has been done, the jump is replaced with the original code (except for an int3 breakpoint in the first byte) by using text_poke_smp().

(*)Please imagine that the 2nd instruction is interrupted and then the optimizer replaces the 2nd instruction with the jump *address* while the interrupt handler is running. When the interrupt returns to original address, there is no valid instruction, and it causes an unexpected result.

(**)This optimization-safety checking may be replaced with the stop-machine method that ksplice uses for supporting a CONFIG_PREEMPT=y kernel.

Thank you,

---

Masami Hiramatsu (9):
kprobes: Add documents of jump optimization
kprobes/x86: Support kprobes jump optimization on x86
x86: Add text_poke_smp for SMP cross modifying code kprobes/x86: Cleanup save/restore registers
kprobes/x86: Boost probes when reentering
kprobes: Jump optimization sysctl interface
kprobes: Introduce kprobes jump optimization
kprobes: Introduce generic insn_slot framework kprobes/x86: Cleanup RELATIVEJUMP_INSTRUCTION to RELATIVEJUMP_OPCODE

 Documentation/kprobes.txt          |  207 +++++++++++-
 arch/Kconfig                       |   13 +
 arch/x86/Kconfig                   |    1 
 arch/x86/include/asm/alternative.h |    4 
 arch/x86/include/asm/kprobes.h     |   31 ++
 arch/x86/kernel/alternative.c      |   60 +++
 arch/x86/kernel/kprobes.c          |  609 ++++++++++++++++++++++++++++------
 include/linux/kprobes.h            |   44 ++
 kernel/kprobes.c                   |  647 +++++++++++++++++++++++++++++++-----
 kernel/sysctl.c                    |   12 +
 10 files changed, 1419 insertions(+), 209 deletions(-)
Signature · 2 lines
Masami Hiramatsu
e-mail: [email protected]