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.