Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S934567AbZFLWsr (ORCPT ); Fri, 12 Jun 2009 18:48:47 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1761173AbZFLWsc (ORCPT ); Fri, 12 Jun 2009 18:48:32 -0400 Received: from mx2.redhat.com ([66.187.237.31]:57400 "EHLO mx2.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1762649AbZFLWsa (ORCPT ); Fri, 12 Jun 2009 18:48:30 -0400 From: Masami Hiramatsu Subject: [RFC][ PATCH -tip 0/6] kprobes: Kprobes jump optimization support To: Ingo Molnar , Ananth N Mavinakayanahalli , lkml Cc: "H. Peter Anvin" , Frederic Weisbecker , Ananth N Mavinakayanahalli , Jim Keniston , Srikar Dronamraju , Christoph Hellwig , Steven Rostedt , Anders Kaseorg , Tim Abbott , systemtap , DLE Date: Fri, 12 Jun 2009 18:49:25 -0400 Message-ID: <20090612224925.17825.49637.stgit@localhost.localdomain> User-Agent: StGIT/0.14.2 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6339 Lines: 154 Hi, 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 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. - 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 e-mail: mhiramat@redhat.com -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/