[PATCH][0/2] kprobe: kprobe-booster against 2.6.16-rc1 for i386

[PATCH][0/2] kprobe: kprobe-booster against 2.6.16-rc1 for i386

[Masami Hiramatsu]

Hi, Andrew

I would like to propose the kprobe-booster and kretprobe-booster
to reduce overhead of kprobes and kretprobes.
They have already been discussed on the SystemTap ML.

I send a couple of patches of kprobe-booster and a patch of
kretprobe-booster in next mails.
These patches are against 2.6.16-rc1 and can be applied against
2.6.16-rc1-mm4.

Here are the descriptions of kprobe-booster and kretprobe-booster.

The description of kprobe-booster:
==================================
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 tranpoline code to call kretprobe's handler directly instead of
invoking kprobe. And tranpoline code returns to original return
address.

This new tranpoline code stores and restores registers, so the kretprobe
handler is still able to access those registers.

Best Regards,

-- 
Masami HIRAMATSU
2nd Research Dept.
Hitachi, Ltd., Systems Development Laboratory
E-mail: hiramatu@sdl.hitachi.co.jp

Re: [PATCH][0/2] kprobe: kprobe-booster against 2.6.16-rc1 for i386

[Masami Hiramatsu]

[-- Attachment #1: Type: text/plain, Size: 3360 bytes --]

Hi, Andrew

Andrew Morton wrote:
> Masami Hiramatsu <hiramatu@sdl.hitachi.co.jp> wrote:
> 
>>I would like to propose the kprobe-booster and kretprobe-booster
>> to reduce overhead of kprobes and kretprobes.
>> They have already been discussed on the SystemTap ML.
> 
> 
> Do you have performance testing results for this change?
> 

Yes, I have. I measured the overhead of probes by measuring the
processing time of gettimeofday systemcall. Details are described
later.

 From the result, 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 number strongly depends on the processor model.


Description of measurement:
==========================
I measured the processing time of sys_gettimeofday()
systemcall on linux-2.6.16-rc1 in 3 cases below;

(A) Not-probed
(B) Probed by a kprobe at the top of do_gettimeofday()
(C) Probed by a kretprobe at the end of do_gettimeofday()

Here is machine spec;
Processor: Pentium4 3.06GHz
Memory: 1024MB
Kernel Configuration: defconfig + CONFIG_KPROBES

I used a non-operation probe functions described below:

---
static int probe_pre_handler (struct kprobe * kp,
                              struct pt_regs * regs)
{
        return 0;
}
---
static int probe_ret_handler (struct kretprobe_instance * ri,
                              struct pt_regs * regs)
{
        return 0;
}
---

I attach a micro benchmark (called gtodbench) to measure
the processing time of sys_gettimeofday() systemcall.
This micro benchmark repeats gettimeofday system call for 10
or specified seconds and counts the number of call.
After that, it calculates average processing time.

Results of measurement:
======================
The results of normal linux-2.6.16-rc1:
(A) 264 nsec/call
(B) 1534 nsec/call
(C) 2245 nsec/call
The overhead of kprobes is 1270 nsec/call(equal to (B) - (A))
The overhead of kretprobes is 1981 nsec/call(equal to (C) - (A))

The results of linux-2.6.16-rc1 with only kprobe-booster patch:
(A) 264 nsec/call
(B) 837 nsec/call
(C) 1585 nsec/call
The overhead of kprobes is 573 nsec/call(equal to (B) - (A))
The overhead of kretprobes is 1321 nsec/call(equal to (C) - (A))
kprobe-booster patch also improves the performance of kretprobe,
because kretprobe is implemented on kprobe.

The results of linux-2.6.16-rc1 with only kretprobe-booster patch:
(A) 264 nsec/call
(B) 1548 nsec/call
(C) 1832 nsec/call
The overhead of kprobes is 1284 nsec/call(equal to (B) - (A))
The overhead of kretprobes is 1568 nsec/call(equal to (C) - (A))
In the other hand, kretprobe-booster does not improbe the
performance of kprobe.

The results of linux-2.6.16-rc1 with the combination of both
kretprobe-booster and kprobe-booster:
(A) 264 nsec/call
(B) 836 nsec/call
(C) 1182 nsec/call
The overhead of kprobes is 572 nsec/call(equal to (B) - (A))
The overhead of kretprobes is 918 nsec/call(equal to (C) - (A))

Best regards,

-- 
Masami HIRAMATSU
2nd Research Dept.
Hitachi, Ltd., Systems Development Laboratory
E-mail: hiramatu@sdl.hitachi.co.jp




[-- Attachment #2: gtodbench.c --]
[-- Type: text/plain, Size: 1646 bytes --]

/*
 gettimeofday micro benchmark for measurement system call performance
 
 Copyright (C) HITACHI,LTD. 2005,2006
 WRITTEN BY HITACHI SYSTEMS DEVELOPMENT LABORATORY,
 Created by M.Hiramatsu <hiramatu@sdl.hitachi.co.jp>
  
 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>

int main (int argc, char *argv[])
{
	struct timeval tv, otv;
	int sec=10;
	unsigned long count;
	struct rusage usage;
	
	if(argc == 2) sec = atoi(argv[1]);
	gettimeofday(&otv,NULL);
	count = 0;
	do {
		gettimeofday(&tv,NULL);
		count ++;
	} while ( (sec - (tv.tv_sec - otv.tv_sec))*1000 >
		  (tv.tv_usec - otv.tv_usec)/1000 );
	getrusage(RUSAGE_SELF, &usage);
	tv = usage.ru_stime;
	tv.tv_sec += usage.ru_utime.tv_sec;
	tv.tv_usec += usage.ru_utime.tv_usec;
	fprintf(stderr, "gettimeofday was called %u times per %d sec: %d nsec per call\n",
	       count, sec, (tv.tv_sec*1000*1000 + tv.tv_usec)/(count/1000));
	return 0;
}