[lkml]   [2009]   [Jun]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    Subject[RFC][ PATCH -tip 0/6] kprobes: Kprobes jump optimization support

    Here are the RFC patchset of the kprobes jump optimization
    (a.k.a. Djprobe, which I had developed two years ago). This version
    supports all features of Kprobes (probe disabling, module .init probing,
    debugfs interface).

    These patches can be applied on -tip tree + x86 instruction decoder
    which I re-sent right now (see below). This is another example of
    x86 instruction decoder.

    This patch depends on:
    kprobes: cleanup fix_riprel() using insn decoder on x86
    kprobes: checks probe address is instruction boudary on x86
    x86: x86 instruction decoder build-time selftest
    x86: instruction decoder API

    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.

    o Usage
    Set CONFIG_OPTPROBES=y when building a kernel, then all *probes will be
    optimized if possible.

    Kprobes decodes probed function and checks whether the target instructions
    can be optimized(replaced with a jump) safely. If it can't be, Kprobes just
    doesn't optimize it.

    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, and 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.
    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

    - 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
    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.

    - 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.

    Thank you,


    Masami Hiramatsu (6):
    kprobes: add documents of jump optimization
    kprobes: x86: support kprobes jump optimization on x86
    kprobes: x86: cleanup save/restore registers
    kprobes: kprobes jump optimization core
    kprobes: introducing generic insn_slot framework
    kprobes: use list instead of hlist for insn_pages

    Documentation/kprobes.txt | 172 ++++++++++++-
    arch/Kconfig | 11 +
    arch/x86/Kconfig | 1
    arch/x86/include/asm/kprobes.h | 31 ++
    arch/x86/kernel/kprobes.c | 528 ++++++++++++++++++++++++++++++++++------
    include/linux/kprobes.h | 38 +++
    kernel/kprobes.c | 508 +++++++++++++++++++++++++++++++-------
    7 files changed, 1096 insertions(+), 193 deletions(-)

    Masami Hiramatsu

    Software Engineer
    Hitachi Computer Products (America), Inc.
    Software Solutions Division


     \ /
      Last update: 2009-06-13 00:51    [W:0.027 / U:4.880 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site