lkml.org 
[lkml]   [2010]   [Feb]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Subject[PATCH -tip v10 0/9] kprobes: Kprobes jump optimization support
    Date
    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(-)

    --
    Masami Hiramatsu
    e-mail: mhiramat@redhat.com


    \
     
     \ /
      Last update: 2010-02-18 23:09    [W:7.676 / U:0.032 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site