lkml.org 
[lkml]   [2009]   [Nov]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH -tip v5 00/10] kprobes: Kprobes jump optimization support
    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.



    \
     
     \ /
      Last update: 2009-11-24 03:11    [W:0.032 / U:1.396 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site