function-exit probes += ppc64

[Jim Keniston]

Here's the function-exit probes design, updated after a talk with Haren
about ppc64.  See Appendix A.  I'm no PowerPC expert, so if you are, let
me know if you see any problems.

Jim Keniston

-------------- next part --------------
1	Function-Return Probes ("rprobes")

1.1	Overview

Here's a design for probing and tracing function returns.  The idea is
that upon entry to a probed function, you replace the return address (RA)
on the stack with the address of a "trampoline."  At the beginning of
time, we have set a probepoint at the trampoline, so when the function
returns, this probepoint gets hit.  The associated handler knows how to
decide which function is returning and thus which user-defined handler
to call.

Two other approaches are discussed briefly at the end of this paper.

1.2	Definitions

ISP: initial stack pointer: the value of the stack pointer upon
entry to a probed function

kprobe_handler: The function that is called by the int3 handler.
kprobe_handler determines whether the int3 is at a probepoint, and if so,
calls the associated probepoint pre-handler.

probepoint handler: A function, usually written by the user, to be
executed when a probepoint is hit.  A pre-handler is called after the
int3 instruction is hit.  A post-handler is called after the probed
instruction has been single-stepped.

RA: return address

return handler: A function, written by the user, that is executed by
the trampoline handler when the probed function returns.

rprobe registration function: register_erprobe() or register_jrprobe()

rprobes: An extension to jprobes/kprobes that allows the probing of
function returns as well as function entries.

SARA: stack address of RA: address on stack where return address is
stored.  For i386, x86_64, and similar architectures, SARA = ISP.
(For ppc64, the RA is stored in the LR register, so there is no SARA.
See Appendix A.)

trampoline: A tiny piece of code - i.e., a labeled nop instruction in an
assembly-language file - whose only purpose is to serve as the probepoint
for all function returns.

trampoline handler: The probepoint handler that is associated with the
probepoint at the trampoline.  This handler is part of the rprobes code.

1.3	API

struct rprobe {
	struct list_head list;
	rprobe_handler_t handler;
	kprobe_fault_handler_t fault_handler;
	int maxactive;
	int nmissed;
	struct kprobe *kp;			// kprobe at function entry
	struct rprobe_instance *instances;	// allocated memory
	struct list_head free_instances;
};

The members list, kp, instances, and free_instances are set and used
internally by kprobes.

handler is the user-supplied return handler to be run when the probed
function returns.  fault_handler is the user-supplied function to be
called if handler generates a fault.

maxactive is specified by the user.  It is the number of instances of the
probed function that can be active concurrently.  For example, if the
function is non-recusrive and is called with a spinlock or mutex held,
maxactive = 1 should be enough.  If the function never sleeps and is
not recursive, NR_CPUS should be enough. (Right?)  maxactive is used to
determine how many rprobe_instance objects to allocate for this particular
probed function.  maxactive <= 0 is the same as maxactive = NR_CPUS.

nmissed is set to zero when the rprobe is registered, and is incremented
every time the probed function is entered but there is no rprobe_instance
object available for establishing the function-return probe.

struct rprobe_instance {
	struct list_head list;
	struct rprobe *rp;
	void *ret_addr;
	void *stack_addr;	// ISP
};

int register_erprobe(struct kprobe *entryprobe, struct rprobe *returnprobe);
Registers a kprobe at the entry to the function whose address is
entryprobe->addr, and an rprobe for that function's return(s).

int register_jrprobe(struct jprobe *jprobe, struct rprobe *returnprobe);
Registers a jprobe at the entry to the function whose address is
jprobe->kp->addr, and an rprobe for that function's return(s).

We need to define rprobe_handler_t.  The handler should probably be
passed the pt_regs and the rprobe_instance object.

We need to provide a function that returns the address of the probed
function given the rprobe_instance pointer.  This needs to work whether
the rprobe is associated with a jprobe or a kprobe.  (For a regular
kprobe, it's just instance->rp->kp->addr.)

1.4	Implementation

1.4.1	Initial Setup

The first time one of the rprobe registration functions is called,
the following initial setup is run:
1.  Register a probepoint at the trampoline, so that the trampoline
handler is run every time a probed function returns.
2.  Initialize the hash table for looking up rprobe_instance objects
by ISP.

1.4.2	Registration

When an rprobe registration function is called, do the following:
1.  Run initial setup if it hasn't been run already.
2.  Allocate space for max_active rprobe_instance objects (rp->instances).
3.  Establish the function-entry probepoint.  If this fails, free
rp->instances.
4.  Put all of the rprobe_instance objects on the free list.
5.  Add the rprobe to some sort of list.
6.  Make the rprobe and kprobe/jprobe objects point to each other
(requires new kprobe field).

1.4.3	Function Entry

When a probepoint is hit, and the kprobe/jprobe object has a corresponding
rprobe object rp, do the following in addition to the usual stuff:
1.  Get an rprobe_instance object off rp's free list.  If there's no
free object, increment rp->nmissed and skip the remaining steps.
2.  Populate the rprobe_instance object with the RA, ISP, and rp.
3.  Add the rprobe_instance object to hash table (hash on ISP).
4.  Replace the RA on the stack with the trampoline's address.

Probably do this stuff before the probed instruction is single-stepped,
in case the probed instruction is the ret instruction.

1.4.4	Function Return

When the probe function returns, the ret instruction pops the trampoline's
address off the stack and jumps to the trampoline code.  The probepoint
is hit, and the trampoline handler is run.

The trampoline handler computes the ISP (pt_regs->esp - sizeof(ulong))
and looks up the rprobe_instance object in the hash table.  It calls
the user's return handler.

After the nop instruction at the trampoline has been single-stepped,
the saved eip is replaced with the original RA, and the rprobe_instance
object is placed back on the free list.  (Presumably this will be done
by resume_execution().)

1.4.5	Deregistration

This could be interesting.  Deregistering an rprobe involves at least
the following:
1.  Look through all the rprobe_instance objects in the hash table, and
for each one associated with this rprobe, plug the RA back into the stack.
2.  Free rp->instances.

We need to decide whether to allow deregistering an rprobe without
deregistering the corresponding kprobe/jprobe.  I vote no.

Need to handle requests to deregister an rprobe when one or more of its
instances are trampolining.

1.5	Assumptions and Limitations

1.  This requires a probepoint (but not necessarily a user-defined
handler) at the entry to every function whose returns are traced.

2.  The return handler is presented with the stack as it appears after
the ret instruction has been executed.  If the user wants to log the
return value or some such, he can refer to pt_regs (e.g., pt_regs->eax
for a function returning int).

3.  This doesn't work for user-mode probes, because there's no place
to put the trampoline.  I wonder if we could replace the RA with a
known "BAD" address, and somehow hook the page-fault handler...

4.  The design described above assumes that the RA is atop the stack when
a function starts, and that a function returns by popping the RA off the
stack and jumping to the RA.  (This would work even for architectures
where the callee pops the args upon return.)  However, it should work
with very little modification for ppc64 as well.  For thoughts on a
ppc64 implementation, see Appendix A.

5.  This assumes that the RA is always the same size.

6.  This doesn't work for inlined or tail-recursive functions where one
or more returns have been optimized out.

1.6	Issues

1.  Need to define rprobe_handler_t.
2.  Need to figure out locking.
3.  Under what circumstances should missed rprobes (i.e., because we're
out of rprobe_instance objects) be reported via printk?
4.  See deregistration issues.

1.7	Other Approaches

Two other possible approaches to function-return probes come to mind.
Unlike the approach described in this paper, these other approaches may
require the insertion of a probepoint or watchpoint every time a probed
function is entered, and the removal of the probepoint or watchpoint after
the function returns.  They also have other limitations, as noted below.

1.  Set a watchpoint at the SARA, so that when the RA is popped off
the stack, a handler will fire.  I haven't seen the details of this
implementation, but it sounds like there's a fair amount of fussing to
work around the limited number of debug registers.  Also, for ppc64,
there is no SARA.

2.  Set a probepoint at the RA.  The main (other) problem with this
approach is that the instruction at the RA may be executed even if the
probed function isn't called.

1.8	Revision History

Rev	Date	Author	Notes
0.1	1/29/05	Jim Keniston	Initial draft.  Sent to Hien 1/31/05
0.2	1/31/05	Jim Keniston	A few minor changes.  Added Revision History.
0.3	1/31/05	Jim Keniston	Solidified a few points after talking to Hien.
0.4	2/11/05	Jim Keniston	Reformatted using vi and fmt. :-}
0.5	2/18/05	Jim Keniston	Added thoughts re: ppc64 (Appendix A) and
				user-mode probes.

Appendix A - PPC64 Implementation

I don't know much about the ppc64 architecture, but I think this idea
should work, at least for a large class of "well behaved" functions (as
far as I can tell, all functions that aren't inlined).

Upon entry to a function, the return address is not atop the stack,
but rather in the LR register.  So upon entry to a function whose return
is probed, we would do the following for ppc64.  (Steps 1 and 3 are the
same as described for i386.)
1.  Get an rprobe_instance object off rp's free list.  If there's no
free object, increment rp->nmissed and skip the remaining steps.
2.  Populate the rprobe_instance object with the RA (from the LR register
-- pt_regs->link), ISP, and rp.
3.  Add the rprobe_instance object to hash table (hash on ISP).
4.  Replace the RA in pt_regs->link with the trampoline's address.

When the function returns via a blr or similar instruction, the probepoint
at the trampoline will be hit, as with the i386.  From there on, it's
pretty much the same as with the i386, except that the stack pointer
after the blr is executed (in pt_regs->gpr[1]) will equal the ISP.