kprobes: Kprobes jump optimization support
Subsystems (4)
v3 cover kprobes: Kprobes jump optimization support
Hi,
Here are the patchset of the kprobes jump optimization v3 (a.k.a. Djprobe). This version includes some bugfixes and sysctl interface for disabling optimization runtime.
I fixed an important bug about reentering probes which will cause unexpected kernel panic if a probe is hit when another probe handler is running.
As far as I can see, the gcc's crossjumping unifies equivalent code inside function and doesn't generate jumps which jump into the middle of other functions. So I decided to drop disabling crossjumping patch from this series.
These patches can be applied on -tip tree + x86 instruction decoder which I sent before. This is another example of x86 instruction decoder.
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, 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.
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 (7):
kprobes: Add documents of jump optimization
kprobes: x86: Support kprobes jump optimization on x86
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
Documentation/kprobes.txt | 192 ++++++++++++- arch/Kconfig | 13 + arch/x86/Kconfig | 1 arch/x86/include/asm/kprobes.h | 31 ++ arch/x86/kernel/kprobes.c | 589 +++++++++++++++++++++++++++++++++------- include/linux/kprobes.h | 45 +++ kernel/kprobes.c | 571 +++++++++++++++++++++++++++++++++------ kernel/sysctl.c | 13 + 8 files changed, 1252 insertions(+), 203 deletions(-)
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]
RFC PATCH v3 1/7 kprobes: Introduce generic insn_slot framework
Make insn_slot framework support various size slots.
Current insn_slot just supports one-size instruction buffer slot. However, kprobes jump optimization needs larger size buffers.
Changes from v2:
- Use an empty array for a variable array.
- Use WARN_ON(1) when finding a trivial bug, instead of BUG().
---
kernel/kprobes.c | 102 +++++++++++++++++++++++++++++++++--------------------- 1 files changed, 63 insertions(+), 39 deletions(-)
kernel/kprobes.c +63 -39
@@ -100,26 +100,42 @@ static struct kprobe_blackpoint kprobe_blacklist[] = {* stepping on the instruction on a vmalloced/kmalloced/data page * is a recipe for disaster */ -#define INSNS_PER_PAGE (PAGE_SIZE/(MAX_INSN_SIZE * sizeof(kprobe_opcode_t))) -struct kprobe_insn_page {struct list_head list;kprobe_opcode_t *insns;/* Page of instruction slots */ -char slot_used[INSNS_PER_PAGE ];int nused;int ngarbage; +char slot_used[]; }; +#define KPROBE_INSN_PAGE_SIZE (slots) \ + (offsetof(struct kprobe_insn_page, slot_used) + \ + (sizeof(char) * (slots))) + +struct kprobe_insn_cache { +struct list_head pages;/* list of kprobe_insn_page */ +size_t insn_size;/* size of instruction slot */ +int nr_garbage; +}; + +static int slots_per_page (struct kprobe_insn_cache *c) +{ +return PAGE_SIZE /(c->insn_size *sizeof (kprobe_opcode_t)); +} +enum kprobe_slot_state {SLOT_CLEAN =0 ,SLOT_DIRTY =1 ,SLOT_USED =2 , }; -static DEFINE_MUTEX (kprobe_insn_mutex);/* Protects kprobe_insn_pages */ -static LIST_HEAD (kprobe_insn_pages); -static int kprobe_garbage_slots; -static int collect_garbage_slots (void ); +static DEFINE_MUTEX (kprobe_insn_mutex);/* Protects kprobe_insn_slots */ +static struct kprobe_insn_cache kprobe_insn_slots = { + .pages =LIST_HEAD_INIT (kprobe_insn_slots.pages), + .insn_size =MAX_INSN_SIZE , + .nr_garbage =0 , +}; +static int __kprobes collect_garbage_slots (struct kprobe_insn_cache *c);static int __kprobes check_safety (void ) {
@@ -149,32 +165,33 @@ loop_end:* __get_insn_slot() - Find a slot on an executable page for an instruction. * We allocate an executable page if there's no room on existing ones. */ -static kprobe_opcode_t __kprobes *__get_insn_slot (void ) +static kprobe_opcode_t __kprobes *__get_insn_slot (struct kprobe_insn_cache *c) {struct kprobe_insn_page *kip; retry: -list_for_each_entry (kip, &kprobe_insn_pages, list) { -if (kip->nused <INSNS_PER_PAGE ) { +list_for_each_entry (kip, &c->pages, list) { +if (kip->nused <slots_per_page (c)) {int i; -for (i =0 ; i <INSNS_PER_PAGE ; i++) { +for (i =0 ; i <slots_per_page (c); i++) {if (kip->slot_used[i] ==SLOT_CLEAN ) { kip->slot_used[i] =SLOT_USED ; kip->nused++; -return kip->insns + (i *MAX_INSN_SIZE ); +return kip->insns + (i * c->insn_size); } } -/* Surprise! No unused slots. Fix kip->nused. */ - kip->nused =INSNS_PER_PAGE ; +/* kip->nused is broken. Fix it. */ + kip->nused =slots_per_page (c); +WARN_ON (1 ); } }/* If there are any garbage slots, collect it and try again. */ -if (kprobe_garbage_slots &&collect_garbage_slots () ==0 ) { +if (c->nr_garbage &&collect_garbage_slots (c) ==0 ) goto retry; - } -/* All out of space. Need to allocate a new page. Use slot 0. */ - kip =kmalloc (sizeof (struct kprobe_insn_page ),GFP_KERNEL ); + +/* All out of space. Need to allocate a new page. */ + kip =kmalloc (KPROBE_INSN_PAGE_SIZE (slots_per_page (c)),GFP_KERNEL );if (!kip)return NULL ;
@@ -189,19 +206,20 @@ static kprobe_opcode_t __kprobes *__get_insn_slot(void)return NULL ; }INIT_LIST_HEAD (&kip->list); -list_add (&kip->list, &kprobe_insn_pages); -memset (kip->slot_used,SLOT_CLEAN ,INSNS_PER_PAGE ); +memset (kip->slot_used,SLOT_CLEAN ,slots_per_page (c)); kip->slot_used[0 ] =SLOT_USED ; kip->nused =1 ; kip->ngarbage =0 ; +list_add (&kip->list, &c->pages);return kip->insns; } +kprobe_opcode_t __kprobes *get_insn_slot (void ) { -kprobe_opcode_t *ret; +kprobe_opcode_t *ret =NULL ;mutex_lock (&kprobe_insn_mutex); - ret =__get_insn_slot (); + ret =__get_insn_slot (&kprobe_insn_slots);mutex_unlock (&kprobe_insn_mutex);return ret; }
@@ -218,7 +236,7 @@ static int __kprobes collect_one_slot(struct kprobe_insn_page *kip, int idx)* so as not to have to set it up again the * next time somebody inserts a probe. */ -if (!list_is_singular (&kprobe_insn_pages)) { +if (!list_is_singular (&kip->list)) {list_del (&kip->list);module_free (NULL , kip->insns);kfree (kip);
@@ -228,7 +246,7 @@ static int __kprobes collect_one_slot(struct kprobe_insn_page *kip, int idx)return 0 ; } -static int __kprobes collect_garbage_slots (void ) +static int __kprobes collect_garbage_slots (struct kprobe_insn_cache *c) {struct kprobe_insn_page *kip, *next;
@@ -236,42 +254,48 @@ static int __kprobes collect_garbage_slots(void)if (check_safety ())return -EAGAIN ; -list_for_each_entry_safe (kip, next, &kprobe_insn_pages, list) { +list_for_each_entry_safe (kip, next, &c->pages, list) {int i;if (kip->ngarbage ==0 )continue ; kip->ngarbage =0 ;/* we will collect all garbages */ -for (i =0 ; i <INSNS_PER_PAGE ; i++) { +for (i =0 ; i <slots_per_page (c); i++) {if (kip->slot_used[i] ==SLOT_DIRTY &&collect_one_slot (kip, i))break ; } } - kprobe_garbage_slots =0 ; + c->nr_garbage =0 ;return 0 ; } -void __kprobes free_insn_slot (kprobe_opcode_t * slot,int dirty) +static void __kprobes __free_insn_slot (struct kprobe_insn_cache *c, +kprobe_opcode_t *slot,int dirty) {struct kprobe_insn_page *kip; -mutex_lock (&kprobe_insn_mutex); -list_for_each_entry (kip, &kprobe_insn_pages, list) { -if (kip->insns <= slot && - slot < kip->insns + (INSNS_PER_PAGE *MAX_INSN_SIZE )) { -int i = (slot - kip->insns) /MAX_INSN_SIZE ; +list_for_each_entry (kip, &c->pages, list) { +long idx = ((long )slot - (long )kip->insns) / c->insn_size; +if (idx >=0 && idx <slots_per_page (c)) { +WARN_ON (kip->slot_used[idx] !=SLOT_USED );if (dirty) { - kip->slot_used[i] =SLOT_DIRTY ; + kip->slot_used[idx] =SLOT_DIRTY ; kip->ngarbage++; +if (++c->nr_garbage >slots_per_page (c)) +collect_garbage_slots (c); }else -collect_one_slot (kip, i); -break ; +collect_one_slot (kip, idx); +return ; } } +/* Could not free this slot. */ +WARN_ON (1 ); +} -if (dirty && ++kprobe_garbage_slots >INSNS_PER_PAGE ) -collect_garbage_slots (); - +void __kprobes free_insn_slot (kprobe_opcode_t * slot,int dirty) +{ +mutex_lock (&kprobe_insn_mutex); +__free_insn_slot (&kprobe_insn_slots, slot, dirty);mutex_unlock (&kprobe_insn_mutex); }#endif
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]
RFC PATCH v3 2/7 kprobes: Introduce kprobes jump optimization
In reply to Masami HiramatsuIntroduce kprobes jump optimization arch-independent parts. Kprobes uses breakpoint instruction for interrupting execution flow, on some architectures, it can be replaced by a jump instruction and interruption emulation code. This gains kprobs' performance drastically.
Changes from v2:
- Set CONFIG_OPTPROBES=y by default.
- Remove CONFIG_DISABLE_CROSSJUMP
- Change detour logic for supporting reentered probes (remove detour_optimized_kprobe())
---
arch/Kconfig | 13 ++ include/linux/kprobes.h | 36 ++++ kernel/kprobes.c | 390 +++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 393 insertions(+), 46 deletions(-)
arch/Kconfig +13 -0
@@ -44,6 +44,17 @@ config KPROBES for kernel debugging, non-intrusive instrumentation and testing. If in doubt, say "N". +config OPTPROBES + bool "Kprobes jump optimization support (EXPERIMENTAL)" + default y + depends on KPROBES + depends on !PREEMPT + depends on HAVE_OPTPROBES + select KALLSYMS_ALL + help + This option will allow kprobes to optimize breakpoint to + a jump for reducing its overhead. + config HAVE_EFFICIENT_UNALIGNED_ACCESS bool help
@@ -79,6 +90,8 @@ config HAVE_KPROBES config HAVE_KRETPROBES bool +config HAVE_OPTPROBES + bool # # An arch should select this if it provides all these things: #
include/linux/kprobes.h +36 -0
@@ -122,6 +122,11 @@ struct kprobe {/* Kprobe status flags */ #define KPROBE_FLAG_GONE 1/* breakpoint has already gone */ #define KPROBE_FLAG_DISABLED 2/* probe is temporarily disabled */ +#define KPROBE_FLAG_OPTIMIZED 4/* +* probe is really optimized. +* NOTE: +* this flag is only for optimized_kprobe. +*/ /* Has this kprobe gone ? */ static inline int kprobe_gone (struct kprobe *p)
@@ -134,6 +139,12 @@ static inline int kprobe_disabled(struct kprobe *p) {return p->flags & (KPROBE_FLAG_DISABLED |KPROBE_FLAG_GONE ); } + +/* Is this kprobe really running optimized path ? */ +static inline int kprobe_optimized (struct kprobe *p) +{ +return p->flags &KPROBE_FLAG_OPTIMIZED ; +}/* * Special probe type that uses setjmp-longjmp type tricks to resume * execution at a specified entry with a matching prototype corresponding
@@ -249,6 +260,31 @@ extern kprobe_opcode_t *get_insn_slot(void);extern void free_insn_slot (kprobe_opcode_t *slot,int dirty);extern void kprobes_inc_nmissed_count (struct kprobe *p); +#ifdef CONFIG_OPTPROBES +/* +* Internal structure for direct jump optimized probe +*/ +struct optimized_kprobe { +struct kprobe kp; +struct list_head list;/* list for optimizing queue */ +struct arch_optimized_insn optinsn; +}; + +/* Architecture dependent functions for direct jump optimization */ +extern int arch_prepared_optinsn (struct arch_optimized_insn *optinsn); +extern int arch_check_optimized_kprobe (struct optimized_kprobe *op); +extern int arch_prepare_optimized_kprobe (struct optimized_kprobe *op); +extern void arch_remove_optimized_kprobe (struct optimized_kprobe *op); +extern int arch_optimize_kprobe (struct optimized_kprobe *op); +extern void arch_unoptimize_kprobe (struct optimized_kprobe *op); +extern kprobe_opcode_t *get_optinsn_slot (void ); +extern void free_optinsn_slot (kprobe_opcode_t *slot,int dirty); +extern int arch_within_optimized_kprobe (struct optimized_kprobe *op, +unsigned long addr); + +extern void opt_pre_handler (struct kprobe *p,struct pt_regs *regs); +#endif /* CONFIG_OPTPROBES */ +/* Get the kprobe at this addr (if any) - called with preemption disabled */ struct kprobe *get_kprobe (void *addr); void kretprobe_hash_lock(struct task_struct *tsk,
kernel/kprobes.c +344 -46
572 lines not on this page · raw message
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]
RFC PATCH v3 3/7 kprobes: Jump optimization sysctl interface
In reply to Masami HiramatsuAdd /proc/sys/debug/kprobes-optimization sysctl which enables and disables kprobes jump optimization on the fly for debugging.
---
include/linux/kprobes.h | 9 +++++ kernel/kprobes.c | 85 +++++++++++++++++++++++++++++++++++++++++++++-- kernel/sysctl.c | 13 +++++++ 3 files changed, 104 insertions(+), 3 deletions(-)
include/linux/kprobes.h +9 -0
@@ -283,6 +283,15 @@ extern int arch_within_optimized_kprobe(struct optimized_kprobe *op, unsigned long addr);extern void opt_pre_handler (struct kprobe *p,struct pt_regs *regs); + +#ifdef CONFIG_SYSCTL +extern int sysctl_kprobes_optimization; +extern int proc_kprobes_optimization_handler (struct ctl_table *table, +int write,struct file *file, +void __user *buffer, +size_t *length,loff_t *ppos); +#endif +#endif /* CONFIG_OPTPROBES */ /* Get the kprobe at this addr (if any) - called with preemption disabled */
kernel/kprobes.c +82 -3
124 lines not on this page · raw message
kernel/sysctl.c +13 -0
@@ -51,6 +51,7 @@#include <linux/ftrace.h> #include <linux/slow-work.h> #include <linux/perf_counter.h> +#include <linux/kprobes.h> #include <asm/uaccess.h> #include <asm/processor.h>
@@ -1551,6 +1552,18 @@ static struct ctl_table debug_table[] = { .proc_handler = proc_dointvec },#endif +#if defined(CONFIG_OPTPROBES) + { + .ctl_name = CTL_UNNUMBERED, + .procname = "kprobes-optimization", + .data = &sysctl_kprobes_optimization, + .maxlen = sizeof(int), + .mode = 0644, + .proc_handler = proc_kprobes_optimization_handler, + .extra1 = &zero, + .extra2 = &one, + }, +#endif { .ctl_name = 0 } };
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]
RFC PATCH v3 4/7 kprobes: x86: Boost probes when reentering
In reply to Masami HiramatsuCleanup prepare_singlestep() and setup_singlestep() to boost up reenter probes.
---
arch/x86/kernel/kprobes.c | 40 +++++++++++++++++++--------------------- 1 files changed, 19 insertions(+), 21 deletions(-)
arch/x86/kernel/kprobes.c +19 -21
@@ -411,18 +411,6 @@ static void __kprobes restore_btf(void)update_debugctlmsr (current->thread.debugctlmsr); } -static void __kprobes prepare_singlestep (struct kprobe *p,struct pt_regs *regs) -{ -clear_btf (); - regs->flags |=X86_EFLAGS_TF ; - regs->flags &= ~X86_EFLAGS_IF ; -/* single step inline if the instruction is an int3 */ -if (p->opcode ==BREAKPOINT_INSTRUCTION ) - regs->ip = (unsigned long )p->addr; -else - regs->ip = (unsigned long )p->ainsn.insn; -} -void __kprobes arch_prepare_kretprobe (struct kretprobe_instance *ri,struct pt_regs *regs) {
@@ -435,7 +423,7 @@ void __kprobes arch_prepare_kretprobe(struct kretprobe_instance *ri, }static void __kprobes setup_singlestep (struct kprobe *p,struct pt_regs *regs, -struct kprobe_ctlblk *kcb) +struct kprobe_ctlblk *kcb,int reenter) {#if !defined(CONFIG_PREEMPT ) || defined(CONFIG_FREEZER )if (p->ainsn.boostable ==1 && !p->post_handler) {
@@ -446,8 +434,21 @@ static void __kprobes setup_singlestep(struct kprobe *p, struct pt_regs *regs, return; }#endif -prepare_singlestep (p, regs); - kcb->kprobe_status =KPROBE_HIT_SS ; +if (reenter) { +save_previous_kprobe (kcb); +set_current_kprobe (p, regs, kcb); + kcb->kprobe_status =KPROBE_REENTER ; + }else + kcb->kprobe_status =KPROBE_HIT_SS ; +/* Prepare real single stepping */ +clear_btf (); + regs->flags |=X86_EFLAGS_TF ; + regs->flags &= ~X86_EFLAGS_IF ; +/* single step inline if the instruction is an int3 */ +if (p->opcode ==BREAKPOINT_INSTRUCTION ) + regs->ip = (unsigned long )p->addr; +else + regs->ip = (unsigned long )p->ainsn.insn; }/*
@@ -472,11 +473,8 @@ static int __kprobes reenter_kprobe(struct kprobe *p, struct pt_regs *regs,break ;#endif case KPROBE_HIT_ACTIVE : -save_previous_kprobe (kcb); -set_current_kprobe (p, regs, kcb);kprobes_inc_nmissed_count (p); -prepare_singlestep (p, regs); - kcb->kprobe_status =KPROBE_REENTER ; +setup_singlestep (p, regs, kcb,1 );break ;case KPROBE_HIT_SS :if (p ==kprobe_running ()) {
@@ -553,13 +551,13 @@ static int __kprobes kprobe_handler(struct pt_regs *regs)* more here. */ if (!p->pre_handler || !p->pre_handler (p, regs)) -setup_singlestep (p, regs, kcb); +setup_singlestep (p, regs, kcb,0 );return 1 ; } }else if (kprobe_running ()) { p =__get_cpu_var (current_kprobe);if (p->break_handler && p->break_handler (p, regs)) { -setup_singlestep (p, regs, kcb); +setup_singlestep (p, regs, kcb,0 );return 1 ; } }/* else: not a kprobe fault; let the kernel handle it */
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]
RFC PATCH v3 5/7 kprobes: x86: Cleanup save/restore registers
In reply to Masami HiramatsuIntroduce SAVE/RESOTRE_REGS_STRING for cleanup kretprobe-trampoline asm code. These macros will be used for emulating interruption.
---
arch/x86/kernel/kprobes.c | 128 ++++++++++++++++++++++++--------------------- 1 files changed, 67 insertions(+), 61 deletions(-)
arch/x86/kernel/kprobes.c +67 -61
@@ -566,6 +566,69 @@ static int __kprobes kprobe_handler(struct pt_regs *regs)return 0 ; } +#ifdef CONFIG_X86_64 +#define SAVE_REGS_STRING \ +/* Skip cs, ip, orig_ax. */ \ + " subq $24, %rsp\n" \ + " pushq %rdi\n" \ + " pushq %rsi\n" \ + " pushq %rdx\n" \ + " pushq %rcx\n" \ + " pushq %rax\n" \ + " pushq %r8\n" \ + " pushq %r9\n" \ + " pushq %r10\n" \ + " pushq %r11\n" \ + " pushq %rbx\n" \ + " pushq %rbp\n" \ + " pushq %r12\n" \ + " pushq %r13\n" \ + " pushq %r14\n" \ + " pushq %r15\n" +#define RESTORE_REGS_STRING \ + " popq %r15\n" \ + " popq %r14\n" \ + " popq %r13\n" \ + " popq %r12\n" \ + " popq %rbp\n" \ + " popq %rbx\n" \ + " popq %r11\n" \ + " popq %r10\n" \ + " popq %r9\n" \ + " popq %r8\n" \ + " popq %rax\n" \ + " popq %rcx\n" \ + " popq %rdx\n" \ + " popq %rsi\n" \ + " popq %rdi\n" \ +/* Skip orig_ax, ip, cs */ \ + " addq $24, %rsp\n" +#else +#define SAVE_REGS_STRING \ +/* Skip cs, ip, orig_ax and gs. */ \ + " subl $16, %esp\n" \ + " pushl %fs\n" \ + " pushl %ds\n" \ + " pushl %es\n" \ + " pushl %eax\n" \ + " pushl %ebp\n" \ + " pushl %edi\n" \ + " pushl %esi\n" \ + " pushl %edx\n" \ + " pushl %ecx\n" \ + " pushl %ebx\n" +#define RESTORE_REGS_STRING \ + " popl %ebx\n" \ + " popl %ecx\n" \ + " popl %edx\n" \ + " popl %esi\n" \ + " popl %edi\n" \ + " popl %ebp\n" \ + " popl %eax\n" \ +/* Skip ds, es, fs, gs, orig_ax, and ip. Note: don't pop cs here*/ \ + " addl $24, %esp\n" +#endif +/* * When a retprobed function returns, this code saves registers and * calls trampoline_handler() runs, which calls the kretprobe's handler.
@@ -579,65 +642,16 @@ static void __used __kprobes kretprobe_trampoline_holder(void)/* We don't bother saving the ss register */ " pushq %rsp\n" " pushfq\n" -/* -* Skip cs, ip, orig_ax. -* trampoline_handler() will plug in these values -*/ -" subq $24, %rsp\n" -" pushq %rdi\n" -" pushq %rsi\n" -" pushq %rdx\n" -" pushq %rcx\n" -" pushq %rax\n" -" pushq %r8\n" -" pushq %r9\n" -" pushq %r10\n" -" pushq %r11\n" -" pushq %rbx\n" -" pushq %rbp\n" -" pushq %r12\n" -" pushq %r13\n" -" pushq %r14\n" -" pushq %r15\n" +SAVE_REGS_STRING " movq %rsp, %rdi\n" " call trampoline_handler\n" /* Replace saved sp with true return address. */ " movq %rax, 152(%rsp)\n" -" popq %r15\n" -" popq %r14\n" -" popq %r13\n" -" popq %r12\n" -" popq %rbp\n" -" popq %rbx\n" -" popq %r11\n" -" popq %r10\n" -" popq %r9\n" -" popq %r8\n" -" popq %rax\n" -" popq %rcx\n" -" popq %rdx\n" -" popq %rsi\n" -" popq %rdi\n" -/* Skip orig_ax, ip, cs */ -" addq $24, %rsp\n" +RESTORE_REGS_STRING " popfq\n"#else " pushf\n" -/* -* Skip cs, ip, orig_ax and gs. -* trampoline_handler() will plug in these values -*/ -" subl $16, %esp\n" -" pushl %fs\n" -" pushl %es\n" -" pushl %ds\n" -" pushl %eax\n" -" pushl %ebp\n" -" pushl %edi\n" -" pushl %esi\n" -" pushl %edx\n" -" pushl %ecx\n" -" pushl %ebx\n" +SAVE_REGS_STRING " movl %esp, %eax\n" " call trampoline_handler\n" /* Move flags to cs */
@@ -645,15 +659,7 @@ static void __used __kprobes kretprobe_trampoline_holder(void)" movl %edx, 52(%esp)\n" /* Replace saved flags with true return address. */ " movl %eax, 56(%esp)\n" -" popl %ebx\n" -" popl %ecx\n" -" popl %edx\n" -" popl %esi\n" -" popl %edi\n" -" popl %ebp\n" -" popl %eax\n" -/* Skip ds, es, fs, gs, orig_ax and ip */ -" addl $24, %esp\n" +RESTORE_REGS_STRING " popf\n"#endif " ret\n");
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]
RFC PATCH v3 6/7 kprobes: x86: Support kprobes jump optimization on x86
In reply to Masami HiramatsuIntroduce x86 arch-specific optimization code, which supports both of x86-32 and x86-64.
This code also supports safety checking, which decodes whole of a function in which probe is inserted, and checks following conditions before optimization:
- The optimized instructions which will be replaced by a jump instruction don't straddle the function boundary.
- There is no indirect jump instruction, because it will jumps into the address range which is replaced by jump operand.
- There is no jump/loop instruction which jumps into the address range which is replaced by jump operand.
- Don't optimize kprobes if it is in functions into which fixup code will jumps.
Changes from v2:
- Fix a bug to support reentered probes (add setup_detour_execution(), and modify setup_singlestep().)
---
arch/x86/Kconfig | 1 arch/x86/include/asm/kprobes.h | 31 +++ arch/x86/kernel/kprobes.c | 421 ++++++++++++++++++++++++++++++++++++++-- 3 files changed, 430 insertions(+), 23 deletions(-)
arch/x86/Kconfig +1 -0
@@ -30,6 +30,7 @@ config X86 select ARCH_WANT_FRAME_POINTERS select HAVE_DMA_ATTRS select HAVE_KRETPROBES + select HAVE_OPTPROBES select HAVE_FTRACE_MCOUNT_RECORD select HAVE_DYNAMIC_FTRACE select HAVE_FUNCTION_TRACER
arch/x86/include/asm/kprobes.h +30 -1
@@ -32,7 +32,10 @@ struct kprobe;typedef u8 kprobe_opcode_t ;#define BREAKPOINT_INSTRUCTION 0xcc -#define RELATIVEJUMP_INSTRUCTION 0xe9 +#define RELATIVEJUMP_OPCODE 0xe9 +#define RELATIVECALL_OPCODE 0xe8 +#define RELATIVE_ADDR_SIZE 4 +#define RELATIVE_JUMP_SIZE (sizeof(kprobe_opcode_t) + RELATIVE_ADDR_SIZE)#define MAX_INSN_SIZE 16#define MAX_STACK_SIZE 64#define MIN_STACK_SIZE (ADDR ) \
@@ -44,6 +47,17 @@ typedef u8 kprobe_opcode_t;#define flush_insn_slot (p) do { } while (0) +/* optinsn template addresses */ +extern kprobe_opcode_t optprobe_template_entry; +extern kprobe_opcode_t optprobe_template_val; +extern kprobe_opcode_t optprobe_template_call; +extern kprobe_opcode_t optprobe_template_end; +#define MAX_OPTIMIZED_LENGTH (MAX_INSN_SIZE + RELATIVE_ADDR_SIZE) +#define MAX_OPTINSN_SIZE \ + (((unsigned long)&optprobe_template_end - \ + (unsigned long)&optprobe_template_entry) + \ + MAX_OPTIMIZED_LENGTH + RELATIVE_JUMP_SIZE) +extern const int kretprobe_blacklist_size;void arch_remove_kprobe (struct kprobe *p);
@@ -64,6 +78,21 @@ struct arch_specific_insn {int boostable; }; +struct arch_optimized_insn { +/* copy of the original instructions */ +kprobe_opcode_t copied_insn[RELATIVE_ADDR_SIZE ]; +/* detour code buffer */ +kprobe_opcode_t *insn; +/* the size of instructions copied to detour code buffer */ +size_t size; +}; + +/* Return true (!0) if optinsn is prepared for optimization. */ +static inline int arch_prepared_optinsn (struct arch_optimized_insn *optinsn) +{ +return optinsn->size; +} +struct prev_kprobe {struct kprobe *kp;unsigned long status;
arch/x86/kernel/kprobes.c +399 -22
486 lines not on this page · raw message
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]
RFC PATCH v3 7/7 kprobes: Add documents of jump optimization
In reply to Masami HiramatsuAdd documentations about kprobe jump optimization to Documentation/kprobes.txt.
Changes from v2:
- Add a description about sysctl (Appendix B).
---
Documentation/kprobes.txt | 192 ++++++++++++++++++++++++++++++++++++++++++--- 1 files changed, 179 insertions(+), 13 deletions(-)
Documentation/kprobes.txt +179 -13
@@ -1,6 +1,7 @@ Title : Kernel Probes (Kprobes) Authors : Jim Keniston <[email protected]> : Prasanna S Panchamukhi <[email protected]> + : Masami Hiramatsu <[email protected]> CONTENTS
@@ -14,6 +15,7 @@ CONTENTS 8. Kprobes Example 9. Jprobes Example 10. Kretprobes Example +11. Optimization Example Appendix A: The kprobes debugfs interface 1. Concepts: Kprobes, Jprobes, Return Probes
@@ -42,13 +44,13 @@ registration/unregistration of a group of *probes. These functions can speed up unregistration process when you have to unregister a lot of probes at once. -The next three subsections explain how the different types of -probes work. They explain certain things that you'll need to -know in order to make the best use of Kprobes -- e.g., the -difference between a pre_handler and a post_handler, and how -to use the maxactive and nmissed fields of a kretprobe. But -if you're in a hurry to start using Kprobes, you can skip ahead -to section 2. +The next four subsections explain how the different types of +probes work and how the optimization works. They explain certain +things that you'll need to know in order to make the best use of +Kprobes -- e.g., the difference between a pre_handler and +a post_handler, and how to use the maxactive and nmissed fields of +a kretprobe. But if you're in a hurry to start using Kprobes, you +can skip ahead to section 2. 1.1 How Does a Kprobe Work?
@@ -161,13 +163,110 @@ In case probed function is entered but there is no kretprobe_instance object available, then in addition to incrementing the nmissed count, the user entry_handler invocation is also skipped. +1.4 How Does the Optimization Work? + + If you configured kernel with CONFIG_OPTPROBES=y (currently this option is +supported on x86/x86-64, non-preemptive kernel) and +"debug.kprobes_optimization" sysctl sets 1, kprobes tries to use a +jump instruction instead of breakpoint instruction automatically. + +1.4.1 Init a Kprobe + + 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. + +1.4.2 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. + +1.4.3 Preparing detour buffer + + 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. + +1.4.4 Pre-optimization + + After preparing detour buffer, Kprobes checks that the probe is *NOT* in +the below cases; + - The probe has either break_handler or post_handler. + - Other probes are probing the instructions which will be replaced by + a jump instruction. + - The probe is disabled. +In above cases, Kprobes just doesn't start optimizating the probe. + + If the kprobe can be optimized, 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. + +1.4.5 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. And then, it replaces int3 with relative-jump opcode, and +synchronize caches again. + + After optimizing the probe, a CPU hits the jump instruction and jumps to +the out-of-line buffer directly. Thus the breakpoint exception is skipped. + +1.4.6 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, replaces the 4 bytes right after int3 with the original +code and synchronize caches again. + +(*)This optimization-safety checking may be replaced with stop-machine method + which ksplice is done for supporting CONFIG_PREEMPT=y kernel. + +NOTE for geeks: +The jump optimization changes the kprobe's pre_handler behavior. +Without optimization, pre_handler can change kernel execution path by +changing regs->ip and return 1. However, after optimizing the probe, +that modification is ignored. Thus, if you'd like to tweak kernel +execution path, you need to avoid optimization. In that case, you can +choose either, + - Set empty function to post_handler or break_handler. + or + - Config CONFIG_OPTPROBES=n. + or + - Execute 'sysctl -w debug.kprobes_optimization=n' + 2. Architectures Supported Kprobes, jprobes, and return probes are implemented on the following architectures: -- i386 -- x86_64 (AMD-64, EM64T) +- i386 (Supports jump optimization) +- x86_64 (AMD-64, EM64T) (Supports jump optimization) - ppc64 - ia64 (Does not support probes on instruction slot1.) - sparc64 (Return probes not yet implemented.)
@@ -193,6 +292,10 @@ it useful to "Compile the kernel with debug info" (CONFIG_DEBUG_INFO), so you can use "objdump -d -l vmlinux" to see the source-to-object code mapping. +If you want to reduce probing overhead, set "Kprobes jump optimization +support" (CONFIG_OPTPROBES) to "y". You can find this option under +"Kprobes" line. + 4. API Reference The Kprobes API includes a "register" function and an "unregister"
@@ -387,9 +490,12 @@ the probe which has been registered. 5. Kprobes Features and Limitations -Kprobes allows multiple probes at the same address. Currently, -however, there cannot be multiple jprobes on the same function at -the same time. +Kprobes allows multiple probes at the same address even if it is optimized. +Currently, however, there cannot be multiple jprobes on the same function +at the same time. And also, optimized kprobes can not invoke the +post_handler and the break_handler. So if you attempt to install the probe +which has the the post_handler or the break_handler at the same address of +an optimized kprobe, the probe will be unoptimized automatically. In general, you can install a probe anywhere in the kernel. In particular, you can probe interrupt handlers. Known exceptions
@@ -453,6 +559,37 @@ reason, Kprobes doesn't support return probes (or kprobes or jprobes) on the x86_64 version of __switch_to(); the registration functions return -EINVAL. +On x86/x86-64, since the Jump Optimization of Kprobes modifies instructions +widely, there are some limitations for optimization. To explain it, +we introduce some terminology. Image certain binary line which is +constructed by 2 byte instruction, 2byte instruction and 3byte instruction. + + IA + | +[-2][-1][0][1][2][3][4][5][6][7] + [ins1][ins2][ ins3 ] + [<- DCR ->] + [<- JTPR ->] + +ins1: 1st Instruction +ins2: 2nd Instruction +ins3: 3rd Instruction +IA: Insertion Address +JTPR: Jump Target Prohibition Region +DCR: Detoured Code Region + +The instructions in DCR are copied to the out-of-line buffer +of the djprobe instance, because the bytes in JTPR are replaced by +a jump instruction. So, there are several limitations. + +a) The instructions in DCR must be relocatable. +b) The instructions in DCR must not include call instruction. +c) JTPR must not be targeted by any jump or call instruction. +d) DCR must not straddle the border betweeen functions. + +Anyway, these limitations are checked by in-kernel instruction decoder, +so you don't need to care about that. + 6. Probe Overhead On a typical CPU in use in 2005, a kprobe hit takes 0.5 to 1.0
@@ -476,6 +613,19 @@ k = 0.49 usec; j = 0.76; r = 0.80; kr = 0.82; jr = 1.07 ppc64: POWER5 (gr), 1656 MHz (SMT disabled, 1 virtual CPU per physical CPU) k = 0.77 usec; j = 1.31; r = 1.26; kr = 1.45; jr = 1.99 +6.1 Optimized Probe Overhead + +Typically, an optimized kprobe hit takes 0.07 to 0.1 microseconds to +process. Here are sample overhead figures (in usec) for x86-64 architectures. +k = unoptimized kprobe, b = boosted(single-step skipped), o = optimized kprobe, +r = unoptimized kretprobe, rb = boosted kretprobe, ro = optimized kretprobe. + +i386: Intel(R) Xeon(R) E5410, 2.33GHz, 4656.90 bogomips +k = 0.68 usec; b = 0.27; o = 0.06; r = 0.95; rb = 0.53; ro = 0.30 + +x86-64: Intel(R) Xeon(R) E5410, 2.33GHz, 4656.90 bogomips +k = 0.91 usec; b = 0.40; o = 0.06; r = 1.21; rb = 0.71; ro = 0.35 + 7. TODO a. SystemTap (http://sourceware.org/systemtap): Provides a simplified
@@ -523,7 +673,8 @@ is also specified. Following columns show probe status. If the probe is on a virtual address that is no longer valid (module init sections, module virtual addresses that correspond to modules that've been unloaded), such probes are marked with [GONE]. If the probe is temporarily disabled, -such probes are marked with [DISABLED]. +such probes are marked with [DISABLED]. If the probe is optimized, it is +marked with [OPTIMIZED]. /sys/kernel/debug/kprobes/enabled: Turn kprobes ON/OFF forcibly.
@@ -533,3 +684,18 @@ registered probes will be disarmed, till such time a "1" is echoed to this file. Note that this knob just disarms and arms all kprobes and doesn't change each probe's disabling state. This means that disabled kprobes (marked [DISABLED]) will be not enabled if you turn ON all kprobes by this knob. + + +Appendix B: The kprobes sysctl interface + +/proc/sys/debug/kprobes-optimization: Turn kprobes optimization ON/OFF. + +When CONFIG_OPTPROBES=y, this sysctl interface appears and it provides a knob +to globally and forcibly turn the jump optimization ON or OFF. By default, +jump optimization is allowed(ON). By echoing "0" to this file or By setting +0 to "debug.kprobes_optimization" via sysctl, all optimized probes will be +unoptimized. And new probes registered after that will not be optimized. +Note that this knob *Changes* the optimized state. This means that optimized +probes (marked [OPTIMIZED]) will be unoptimized ([OPTIMIZED] tag will be +removed). And after the knob is turned on, it will be optimized again. +
Signature · 7 lines
Masami Hiramatsu Software Engineer Hitachi Computer Products (America), Inc. Software Solutions Division e-mail: [email protected]