RE: [RFC]-Approaches to user space probes

RE: [RFC]-Approaches to user space probes

[Stone, Joshua I]

Keshavamurthy Anil S wrote:
> On Fri, Jan 27, 2006 at 10:45:02AM -0800, Stone, Joshua I wrote:
>> An advantage I see in 4 is the ability to have scripts with a mix of
>> kernel & user probes.  This could let you do some interesting
>> correlations, perhaps something like:
> Sure, their is some advantange in 4, but the thing we need to see
> is whether this apporach suits probing different kinds of
> application(mainly java apps).

It may be possible to just have a user-mode daemon manage the
communication with the JVM (through JVMTI or the like).  So I don't
method 4 excludes other application types, though it may make some
things harder than they would be in methods 1-3.


> [...]
> If in the user program, strlen() is called only once and
> assuming that the return probe failed to initialize due to
> no kretprobe instance, your return probe handler will
> never gets fired and your hence in_strlen[tid()] will
> never gets reset and  the pagefault count will have
> wrong value.

Well, in a world where kretprobes can miss, the best you can do is a
"statistical" sampling.  If an event only heppens once, it may not be of
much interest anyway.  (It would be nice to see this limitation of
kretprobes go away, but I haven't reviewed the code enough to know why
that limitation is necessary...)

There is a real issue of stale 'flags' using up all of the map space,
but this can be alleviated if we enable wrapping on maps.

Do we have any hooks back to the stap module if a kretprobe instance
fails?  It would be nice if the runtime could keep track of that and
include it in the MAXSKIPPED count...


Josh

Re: [RFC]-Approaches to user space probes

[Frank Ch. Eigler]

Hi -

anil.s.keshavamurthy wrote:

> [...]  I am not an expert in Java or Java probes, but before we lock
> down this approach I am suggesting that if possible we get feedback
> from JVM gurus too.

OK, but to involve them at this stage, we have to first formulate the
issue in a form they can understand.  Beyond asking them to add a few
hooks into their various interpreters (similarly to dtrace), how do
you think they might be impacted?


> [...] having a counter to count the missed probe does not solve the
> problem here.

Which problem?  That this can occur (with some low probability?)?
That it may be difficult to detect after occurrence?  That it may
be hard for a user to work around (rerunning may not work)?

> [...] In other words we should not see rp->nmissed > 0, however it
> is okay to for rp->kp.nmissed > 0.

While we may *prefer* not to see any nmissed > 0, how bad do you think
the consequences are if we do miss a few?  What are the odds?


- FChE

RE: [RFC]-Approaches to user space probes

[Keshavamurthy, Anil S]

>anil.s.keshavamurthy wrote:
>
>> [...]
>> Sure, their is some advantange in 4, but the thing we need to see
>> is whether this apporach suits probing different kinds of 
>> application(mainly java apps).
>
>Could you explain why you think Java would be harder to instrument
>with kernel-space probes?  We may opt to compose user-kprobes along
>the lines of #4, and static instrumentation (a libmudflap.so
>containing hooks for language interpreters to hook up to and pass
>event parameters).

I am not an expert in Java or Java probes, but before we lock down this
approach
I am suggesting that if possible we get feedback from JVM gurus too.


>That is not such a big problem.  Should such an unfortunate timing
>glitch occur, the system would report a missed probe.  The user could
>then try again.

Frank, having a counter to count the missed probe does not solve the
problem here.
The issue here is that your function entry probe handler gets fired and
there are chances that
the corresponding function return probe hander might not be called and
rp->nmissed++ will
do no good. 
In other words we should not see rp->nmissed > 0, 
however it is okay to for rp->kp.nmissed > 0.

-Anil

RE: [RFC]-Approaches to user space probes

[Stone, Joshua I]

Stone, Joshua I wrote:
> Keshavamurthy Anil S wrote:
>> [...]
>> If in the user program, strlen() is called only once and
>> assuming that the return probe failed to initialize due to
>> no kretprobe instance, your return probe handler will
>> never gets fired and your hence in_strlen[tid()] will
>> never gets reset and  the pagefault count will have
>> wrong value.
> 
> Well, in a world where kretprobes can miss, the best you can do is a
> "statistical" sampling.  If an event only heppens once, it may not be
> of much interest anyway.  (It would be nice to see this limitation of
> kretprobes go away, but I haven't reviewed the code enough to know why
> that limitation is necessary...)

Sorry, I didn't quite understand your point.  If only one strlen is
called and then missed on return, then *every* pagefault in that thread
from then on will be attributed to strlen.  I agree this is a problem
with my example - and also a problem that may crop up in SystemTap
scripts in general.  All the more reason why I wish kretprobes were more
"robust"...

Josh

Re: [RFC]-Approaches to user space probes

[Frank Ch. Eigler]

anil.s.keshavamurthy wrote:

> [...]
> Sure, their is some advantange in 4, but the thing we need to see
> is whether this apporach suits probing different kinds of 
> application(mainly java apps).

Could you explain why you think Java would be harder to instrument
with kernel-space probes?  We may opt to compose user-kprobes along
the lines of #4, and static instrumentation (a libmudflap.so
containing hooks for language interpreters to hook up to and pass
event parameters).


> >   probe user.module("/lib/libc.so.6").function("strlen") {
> >       in_strlen[tid()] = 1
> Setting a variable in function entry probe and 
> later trying to reset in the function return probe
> is very problematic.	

> [...]
> >   probe user.module("/lib/libc.so.6").function("strlen").return {
> >       delete in_strlen[tid()]
> [...]  in_strlen[tid()] will never gets reset and the pagefault
> count will have wrong value.

That is not such a big problem.  Should such an unfortunate timing
glitch occur, the system would report a missed probe.  The user could
then try again.


- FChE

Re: [RFC]-Approaches to user space probes

[Keshavamurthy Anil S]

On Fri, Jan 27, 2006 at 10:45:02AM -0800, Stone, Joshua I wrote:
> Prasanna S Panchamukhi wrote:
> > 	1. Attaching or loading the application into the tool.
> > 	2. Using a jump instruction to a trampoline and trampoline
> > 	   executing the instrumented code.
> > 	3. Using a breakpoint instruction and changing the instruction
> > 	   point to the instrumentaiton code which is part of user
> > 	   address space.
> > 	4. Using a breakpoint instruction and executing the
> > 	   instrumentation code within the breakpoint handler.
> 
> An advantage I see in 4 is the ability to have scripts with a mix of
> kernel & user probes.  This could let you do some interesting
> correlations, perhaps something like:
Sure, their is some advantange in 4, but the thing we need to see
is whether this apporach suits probing different kinds of 
application(mainly java apps).


> 
>   # Figure out if calls to strlen are causing page faults, and by whom
>   global in_strlen, strlen_pagefaults
Very nice example, but I see a problem in your script,
let me know how this problem can be addressed.

>   probe user.module("/lib/libc.so.6").function("strlen") {
>       in_strlen[tid()] = 1
Setting a variable in function entry probe and 
later trying to reset in the function return probe
is very problematic.	
>   }

>   probe kernel.function("do_page_fault") {
>       if (in_strlen[tid()])
>           strlen_pagefaults[execname()] <<< 1
>   }
>   probe user.module("/lib/libc.so.6").function("strlen").return {
>       delete in_strlen[tid()]
If in the user program, strlen() is called only once and 
assuming that the return probe failed to initialize due to
no kretprobe instance, your return probe handler will
never gets fired and your hence in_strlen[tid()] will
never gets reset and  the pagefault count will have 
wrong value.
>   }
>   probe end {
>       foreach (name in strlen_pagefaults)
>           printf("%s: %d\n", name, strlen_pagefaults[name])
>   }
> 
> I don't think this sort of thing would be easy to implement with 1-3.
> You might be able to record timestamps and try to correlate the data
> later, but that's not as reliable.
> 
> Josh

Re: [RFC]-Approaches to user space probes

[Satoshi Oshima]

Hi,

We should think that we need to support 4G/4G split.

In the 4G/4G split environment, kernel space portion
cannot touch user space portion. So instrumentation
code should be placed in user space. Or we need to
add the way to aquire the memory that is place in
kernel/user common space.

On the other hand, aquiring instrumentation code area
from user space is difficult sometimes.  Applications
may use up user space.



By the way, I want to introduce Pannus project.

http://sourceforge.net/projects/pannus/

This is similar to or exactly the same as #2.

This is a live-patching to application. Pannus try to
remove target application out of schedule temporarily.
And it try to find an available user space using patched
do_mmap_pgoff(). It loads instrumentation code into
user space, if finding space. And change original code
to swich to patching code. it pins down the changed page.

I haven't tested this patch. So this way might have some
problem. But this approach is worth to discuss, I think.

Regards,
Satoshi


Prasanna S Panchamukhi wrote:
> Hi,
> 
> As per yesturday's Conf call dicussion, I have listed few approaches
> for dynamic instrumentation of applications/libraries. Please provide
> your suggestions about the listed approaches and other approaches you
> know.
> 
> Thanks
> Prasanna
> 
> 	1. Attaching or loading the application into the tool.
> 	2. Using a jump instruction to a trampoline and trampoline
> 	   executing the instrumented code.
> 	3. Using a breakpoint instruction and changing the instruction
> 	   point to the instrumentaiton code which is part of user
> 	   address space.
> 	4. Using a breakpoint instruction and executing the
> 	   instrumentation code within the breakpoint handler.
> 
> 1. Attaching or loading the application into the tool.
> 
> 	In this method the user application must be loaded into the
> tool or attached to already running application. Before the user can
> instrument an application he must decide what that instrumentation
> will consist of. Dynaprof uses such a mechanism. There are currently
> two probes shipped with Dynaprof, the PAPI Probe and the Wallclock
> Probe.  PAPI uses the processor's hardware performance counters to
> measure specific hardware events like cache misses, branch
> mispredictions and floating point instructions. The Wallclock probe
> measures elapsed real-time which is sometimes referred to as wallclock
> time.
> Dynaprof inserts instrumentation directly into the applications
> address space. This is accomplished through a run-time code generation
> and patching mechanism based upon either Dyninst or DPCL, IBM's
> derivative effort. Whenever a function is instrumented, all it's
> children are instrumented as well. This is to enable the probe to
> generate both inclusive and exclusive metrics.
> 
> 2. Using a jump instruction to a trampoline and trampoline executing
> the instrumented code.
> 
> 	In this method the instrumenation code must be loded into user
> address space dynamically. The major challenges are to generate
> instrumentation code at the run time and to allocate space for
> dynamically generated code. To insert this code, the application
> process is stopped, the code and data are installed into the
> application address space using operating system facilities such as
> ptrace and /proc file system. Each small code fragments are called
> trampolines. Associated with each active probe is a base-trampoline
> and block of instrumentation code is placed in its own mini-trampoline.
> The base trampoline contains the relocated original instructions from
> the probe point in the application program, instructions to save and
> restore registers, slots where jumps to mini-trampolines are be inserted
> and a jump to return to the application code. When the probe is fired,
> the base-trampoline gets executed that saves the registers state and
> then execute individual mini-trampolines After returning, base
> trampoline restores the registers state and normal execution continues.
> Eg: Paradyn tool.
> 
> Issues with method 1 and 2 are:
> 
> 	* Induces intel erratum E49 where the other processors see
> 	  stale data while one processor replaces the jump instruction.
> 
> 	* Instruction can only be replaced atomically if the size of
> 	  the jump instruction is greater than or equal to the original
> 	  instruction.
> 
> 	* Other processors need to be stopped if the jump instruction size
> 	  is less than the original instruction.
> 
> 3. Using breakpoint instruction and changing the instruction pointer
> 
> In this method a breakpoint instruction is inserted at the probe point
> and the original instruction is copied into the user address space.
> When the probe is fired, the breakpoint handler changes the instruction
> pointer to jump to a trampoline part of user address space. After the
> trampoline executes the instrumenation code, trampoline jumps back to
> the original routine after restoring the registers and process stack.
> 
> Issue associated with this approach is to allocate a saperate space in
> user address space to copy the instrumenation code and original
> instruction.
> 
> 4. Using breakpoint instruction
> 	Using a breakpoint instruction and executing the instrumentation
> code from within the breakpoint handler in the interrupt context.
> 
> Issue associated with this approach is to single step the original
> instruction out-of-line.
> 
> In kernel space probes, single stepping out-of-line is achieved by
> copying the instruction on to some location within kernel address space
> and then single step from that location. But for userspace probes,
> instruction copied into kernel address space cannot be single stepped,
> hence the instruction should be copied to user address space. The
> solution is to find free space in the current process address space
> and then copy the original instruction and single step that instruction.
> 
> User processes use stack space to store local variables, agruments and
> return values. Normally the stack space either below or above the stack
> pointer indicates the free stack space. If the stack grows downwards,
> the stack space below the stack pointer indicates the unused stack free
> space and if the stack grows upwards, the stack space above the stack
> pointer indicates the unused stack free space.
> 
> The instruction to be single stepped can modify the stack space,
> hence before using the unused stack free space, sufficient stack space
> should be left. The instruction is copied to the bottom of the page
> and check is made such that the copied instruction does not cross the
> page boundry. The copied instruction is then single stepped.
> 
> Several architectures does not allow the instruction to be executed
> from the stack location, since no-exec bit is set for the stack pages.
> In those architectures, the page table entry corresponding to the
> stack page is identified and the no-exec bit is unset making the
> instruction on that stack page to be executed.
> 
> There are situations where even the unused free stack space is not
> enough for the user instruction to be copied and single stepped. In
> such situations, the virtual memory area(vma) can be expanded beyond
> the current stack vma. This expaneded stack can be used to copy the
> original instruction and single step out-of-line.
> 
> Even if the vma cannot be extended then the instruction much be
> executed inline, by replacing the breakpoint instruction with original
> instruction.
> 
> Eg: Dprobes implemented this approach, but did not provide single
> stepping out-of-line.
> 
> Method 3 and 4 require similar breakpoint insertion/removal mechanism
> for the pages that are present in the memory and also for the pages
> that are not present in the memory during insertion of probes. URL of
> the initial patches are:
> 
> http://sourceware.org/ml/systemtap/2006-q1/msg00212.html
> http://sourceware.org/ml/systemtap/2006-q1/msg00210.html
> 
> Method 4 requires a mechaism for single stepping the original
> instruction out-of-line , URL of the prototype implentation is:
> 
> http://sourceware.org/ml/systemtap/2006-q1/msg00211.html

Re: [RFC]-Approaches to user space probes

[Frank Ch. Eigler]

prasanna wrote:

> 	1. Attaching or loading the application into the tool.
> 	2. Using a jump instruction to a trampoline and trampoline
> 	   executing the instrumented code.
> 	3. Using a breakpoint instruction and changing the instruction
> 	   point to the instrumentaiton code which is part of user
> 	   address space.
> 	4. Using a breakpoint instruction and executing the
> 	   instrumentation code within the breakpoint handler.
> [...]

Very early on in the project, I had imagined something like #1-3, but
since have come to a conclusion that #4 makes the most sense.  Josh's
reason (correlating user & kernel side events) is one; invisibility to
the user-space program is another, and related to that, less
likelihood of interference with complex programs (signals, threading);
simplicity of concurrency rules (atomic probe handlers).

- FChE

RE: [RFC]-Approaches to user space probes

[Stone, Joshua I]

Prasanna S Panchamukhi wrote:
> 	1. Attaching or loading the application into the tool.
> 	2. Using a jump instruction to a trampoline and trampoline
> 	   executing the instrumented code.
> 	3. Using a breakpoint instruction and changing the instruction
> 	   point to the instrumentaiton code which is part of user
> 	   address space.
> 	4. Using a breakpoint instruction and executing the
> 	   instrumentation code within the breakpoint handler.

An advantage I see in 4 is the ability to have scripts with a mix of
kernel & user probes.  This could let you do some interesting
correlations, perhaps something like:

  # Figure out if calls to strlen are causing page faults, and by whom
  global in_strlen, strlen_pagefaults
  probe user.module("/lib/libc.so.6").function("strlen") {
      in_strlen[tid()] = 1
  }
  probe kernel.function("do_page_fault") {
      if (in_strlen[tid()])
          strlen_pagefaults[execname()] <<< 1
  }
  probe user.module("/lib/libc.so.6").function("strlen").return {
      delete in_strlen[tid()]
  }
  probe end {
      foreach (name in strlen_pagefaults)
          printf("%s: %d\n", name, strlen_pagefaults[name])
  }

I don't think this sort of thing would be easy to implement with 1-3.
You might be able to record timestamps and try to correlate the data
later, but that's not as reliable.

Josh

[RFC]-Approaches to user space probes

[Prasanna S Panchamukhi]

Hi,

As per yesturday's Conf call dicussion, I have listed few approaches
for dynamic instrumentation of applications/libraries. Please provide
your suggestions about the listed approaches and other approaches you
know.

Thanks
Prasanna

	1. Attaching or loading the application into the tool.
	2. Using a jump instruction to a trampoline and trampoline
	   executing the instrumented code.
	3. Using a breakpoint instruction and changing the instruction
	   point to the instrumentaiton code which is part of user
	   address space.
	4. Using a breakpoint instruction and executing the
	   instrumentation code within the breakpoint handler.

1. Attaching or loading the application into the tool.

	In this method the user application must be loaded into the
tool or attached to already running application. Before the user can
instrument an application he must decide what that instrumentation
will consist of. Dynaprof uses such a mechanism. There are currently
two probes shipped with Dynaprof, the PAPI Probe and the Wallclock
Probe.  PAPI uses the processor's hardware performance counters to
measure specific hardware events like cache misses, branch
mispredictions and floating point instructions. The Wallclock probe
measures elapsed real-time which is sometimes referred to as wallclock
time.
Dynaprof inserts instrumentation directly into the applications
address space. This is accomplished through a run-time code generation
and patching mechanism based upon either Dyninst or DPCL, IBM's
derivative effort. Whenever a function is instrumented, all it's
children are instrumented as well. This is to enable the probe to
generate both inclusive and exclusive metrics.

2. Using a jump instruction to a trampoline and trampoline executing
the instrumented code.

	In this method the instrumenation code must be loded into user
address space dynamically. The major challenges are to generate
instrumentation code at the run time and to allocate space for
dynamically generated code. To insert this code, the application
process is stopped, the code and data are installed into the
application address space using operating system facilities such as
ptrace and /proc file system. Each small code fragments are called
trampolines. Associated with each active probe is a base-trampoline
and block of instrumentation code is placed in its own mini-trampoline.
The base trampoline contains the relocated original instructions from
the probe point in the application program, instructions to save and
restore registers, slots where jumps to mini-trampolines are be inserted
and a jump to return to the application code. When the probe is fired,
the base-trampoline gets executed that saves the registers state and
then execute individual mini-trampolines After returning, base
trampoline restores the registers state and normal execution continues.
Eg: Paradyn tool.

Issues with method 1 and 2 are:

	* Induces intel erratum E49 where the other processors see
	  stale data while one processor replaces the jump instruction.

	* Instruction can only be replaced atomically if the size of
	  the jump instruction is greater than or equal to the original
	  instruction.

	* Other processors need to be stopped if the jump instruction size
	  is less than the original instruction.

3. Using breakpoint instruction and changing the instruction pointer

In this method a breakpoint instruction is inserted at the probe point
and the original instruction is copied into the user address space.
When the probe is fired, the breakpoint handler changes the instruction
pointer to jump to a trampoline part of user address space. After the
trampoline executes the instrumenation code, trampoline jumps back to
the original routine after restoring the registers and process stack.

Issue associated with this approach is to allocate a saperate space in
user address space to copy the instrumenation code and original
instruction.

4. Using breakpoint instruction
	Using a breakpoint instruction and executing the instrumentation
code from within the breakpoint handler in the interrupt context.

Issue associated with this approach is to single step the original
instruction out-of-line.

In kernel space probes, single stepping out-of-line is achieved by
copying the instruction on to some location within kernel address space
and then single step from that location. But for userspace probes,
instruction copied into kernel address space cannot be single stepped,
hence the instruction should be copied to user address space. The
solution is to find free space in the current process address space
and then copy the original instruction and single step that instruction.

User processes use stack space to store local variables, agruments and
return values. Normally the stack space either below or above the stack
pointer indicates the free stack space. If the stack grows downwards,
the stack space below the stack pointer indicates the unused stack free
space and if the stack grows upwards, the stack space above the stack
pointer indicates the unused stack free space.

The instruction to be single stepped can modify the stack space,
hence before using the unused stack free space, sufficient stack space
should be left. The instruction is copied to the bottom of the page
and check is made such that the copied instruction does not cross the
page boundry. The copied instruction is then single stepped.

Several architectures does not allow the instruction to be executed
from the stack location, since no-exec bit is set for the stack pages.
In those architectures, the page table entry corresponding to the
stack page is identified and the no-exec bit is unset making the
instruction on that stack page to be executed.

There are situations where even the unused free stack space is not
enough for the user instruction to be copied and single stepped. In
such situations, the virtual memory area(vma) can be expanded beyond
the current stack vma. This expaneded stack can be used to copy the
original instruction and single step out-of-line.

Even if the vma cannot be extended then the instruction much be
executed inline, by replacing the breakpoint instruction with original
instruction.

Eg: Dprobes implemented this approach, but did not provide single
stepping out-of-line.

Method 3 and 4 require similar breakpoint insertion/removal mechanism
for the pages that are present in the memory and also for the pages
that are not present in the memory during insertion of probes. URL of
the initial patches are:

http://sourceware.org/ml/systemtap/2006-q1/msg00212.html
http://sourceware.org/ml/systemtap/2006-q1/msg00210.html

Method 4 requires a mechaism for single stepping the original
instruction out-of-line , URL of the prototype implentation is:

http://sourceware.org/ml/systemtap/2006-q1/msg00211.html
-- 
Prasanna S Panchamukhi
Linux Technology Center
India Software Labs, IBM Bangalore
Email: prasanna@in.ibm.com
Ph: 91-80-51776329