• Masami Hiramatsu's avatar
    [PATCH] x86: kprobes-booster · 311ac88f
    Masami Hiramatsu authored
    Current kprobe copies the original instruction at the probe point and replaces
    it with a breakpoint instruction (int3).  When the kernel hits the probe
    point, kprobe handler is invoked.  And the copied instruction is single-step
    executed on the copied buffer (not on the original address) by kprobe.  After
    that, the kprobe checks registers and modify it (if need) as if the
    instructions was executed on the original address.
    
    My proposal is based on the fact there are many instructions which do NOT
    require the register modification after the single-step execution.  When the
    copied instruction is a kind of them, kprobe just jumps back to the next
    instruction after single-step execution.  If so, why don't we execute those
    instructions directly?
    
    With kprobe-booster patch, kprobes will execute a copied instruction directly
    and (if need) jump back to original code.  This direct execution is executed
    when the kprobe don't have both post_handler and break_handler, and the copied
    instruction can be executed directly.
    
    I sorted instructions which can be executed directly or not;
    
    - Call instructions are NG(can not be executed directly).
      We should correct the return address pushed into top of stack.
    - Indirect instructions except for absolute indirect-jumps
      are NG. Those instructions changes EIP randomly. We should
      check EIP and correct it.
    - Instructions that change EIP beyond the range of the
      instruction buffer are NG.
    - Instructions that change EIP to tail 5 bytes of the
      instruction buffer (it is the size of a jump instruction).
      We must write a jump instruction which backs to original
      kernel code in the instruction buffer.
    - Break point instruction is NG. We should not touch EIP and
      pass to other handlers.
    - Absolute direct/indirect jumps are OK.- Conditional Jumps are NG.
    - Halt and software-interruptions are NG. Because it will stay on
      the instruction buffer of kprobes.
    - Prefixes are NG.
    - Unknown/reserved opcode is NG.
    - Other 1 byte instructions are OK. But those instructions need a
      jump back code.
    - 2 bytes instructions are mapped sparsely. So, in this release,
      this patch don't boost those instructions.
    
    >From Intel's IA-32 opcode map described in IA-32 Intel Architecture Software
    Developer's Manual Vol.2 B, I determined that following opcodes are not
    boostable.
    
    - 0FH (2byte escape)
    - 70H - 7FH (Jump on condition)
    - 9AH (Call) and 9CH (Pushf)
    - C0H-C1H (Grp 2: includes reserved opcode)
    - C6H-C7H (Grp11: includes reserved opcode)
    - CCH-CEH (Software-interrupt)
    - D0H-D3H (Grp2: includes reserved opcode)
    - D6H (Reserved)
    - D8H-DFH (Coprocessor)
    - E0H-E3H (loop/conditional jump)
    - E8H (Call)
    - F0H-F3H (Prefixes and reserved)
    - F4H (Halt)
    - F6H-F7H (Grp3: includes reserved opcode)
    - FEH-FFH(Grp4,5: includes reserved opcode)
    
    Kprobe-booster checks whether target instruction can be boosted (can be
    executed directly) at arch_copy_kprobe() function.  If the target instruction
    can be boosted, it clears "boostable" flag.  If not, it sets "boostable" flag
    -1.  This is disabled status.  In resume_execution() function, If "boostable"
    flag is cleared, kprobe-booster measures the size of the target instruction
    and sets "boostable" flag 1.
    
    In kprobe_handler(), kprobe checks the "boostable" flag.  If the flag is 1, it
    resets current kprobe and executes instruction buffer directly instead of
    single stepping.
    
    When unregistering a boosted kprobe, it calls synchronize_sched()
    after "int3" is removed. So we can ensure followings after
    the synchronize_sched() called.
    - interrupt handlers are finished on all CPUs.
    - instruction buffer is not executed on all CPUs.
    And we can release the boosted kprobe safely.
    
    And also, on preemptible kernel, the booster is not enabled where the kernel
    preemption is enabled.  So, there are no preempted threads on the instruction
    buffer.
    
    The description of kretprobe-booster:
    ====================================
    
    In the normal operation, kretprobe make a target function return to trampoline
    code.  And a kprobe (called trampoline_probe) have been inserted at the
    trampoline code.  When the kernel hits this kprobe, it calls kretprobe's
    handler and it returns to original return address.
    
    Kretprobe-booster patch removes the trampoline_probe.  It allows the
    trampoline code to call kretprobe's handler directly instead of invoking
    kprobe.  And tranpoline code returns to original return address.
    
    This new trampoline code stores and restores registers, so the kretprobe
    handler is still able to access those registers.
    
    Current kprobe has about 1.3 usec/probe(*) overhead, and kprobe-booster patch
    reduces it to 0.6 usec/probe(*).  Also current kretprobe has about 2.0
    usec/probe(*) overhead.  Kprobe-booster patch reduces it to 1.3 usec/probe(*),
    and the combination of both kprobe-booster patch and kretprobe-booster patch
    reduces it to 0.9 usec/probe(*).
    
    I expect the combination of both patches can reduce half of a probing
    overhead.
    
    Performance numbers strongly depend on the processor model.
    
    Andrew Morton wrote:
    > These preempt tricks look rather nasty.  Can you please describe what the
    > problem is, precisely?  And how this code avoids it?  Perhaps we can find
    > something cleaner.
    
    The problem is how to remove the copied instructions of the
    kprobe *safely* on the preemptable kernel (CONFIG_PREEMPT=y).
    
    Kprobes basically executes the following actions;
    
    (1)int3
    (2)preempt_disable()
    (3)kprobe_prehandler()
    (4)copied instructioin(single step)
    (5)kprobe_posthandler()
    (6)preempt_enable()
    (7)return to the original code
    
    During the execution of copied instruction, preemption is
    disabled (from step (2) to (6)).
    When unregistering the probes, Kprobe waits for RCU
    quiescent state by using synchronize_sched() after removing
    int3 instruction.
    Thus we can ensure the copied instruction is not executed.
    
    On the other hand, kprobe-booster executes the following actions;
    
    (1)int3
    (2)preempt_disable()
    (3)kprobe_prehandler()
    (4)preempt_enable()             <-- this one is added by my patch
    (5)copied instruction(direct execution)
    (6)jmp back to the original code
    
    The problem is that we have no way to prevent preemption on
    step (5) or (6). We cannot call preempt_disable() after step (6),
    because there are no rooms to do that. Thus, some other
    processes may be preempted at step(5) or (6) on preemptable kernel.
    And I couldn't find the easy way to ensure that other processes'
    stack do *not* have the address of them. (I thought some way
    to do that, but those are very costly.)
    
    So currently, I simply boost the kprobe only when the probe
    point is already preemption disabled.
    
    > Also, the patch adds a preempt_enable() but I don't see a corresponding
    > preempt_disable().  Am I missing something?
    
    It is corresponding to the preempt_disable() in the top of
    kprobe_handler().
    I copied the code of kprobe_handler() here:
    
    static int __kprobes kprobe_handler(struct pt_regs *regs)
    {
            struct kprobe *p;
            int ret = 0;
            kprobe_opcode_t *addr = NULL;
            unsigned long *lp;
            struct kprobe_ctlblk *kcb;
    
            /*
             * We don't want to be preempted for the entire
             * duration of kprobe processing
             */
            preempt_disable();             <-- HERE
            kcb = get_kprobe_ctlblk();
    Signed-off-by: default avatarMasami Hiramatsu <hiramatu@sdl.hitachi.co.jp>
    Cc: Prasanna S Panchamukhi <prasanna@in.ibm.com>
    Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
    Cc: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>
    Cc: David S. Miller <davem@davemloft.net>
    Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
    311ac88f
kprobes.c 18.6 KB