|
From: Nicholas N. <nj...@ca...> - 2004-06-21 10:15:54
|
Josef, I've finally (it only took 6 months!) had a close look at your description of how Calltree accurately tracks function entry/exit. I've paraphrased your description to help me understand it better, but I'm still not quite clear on some points. I looked at the code, but found it hard to understand. Could you help me? I've written my questions in square brackets. Here's the description. -------- Data structures: - have a shadow call stack for every thread [not sure exactly what goes on this] Action at BB start -- depends on jmp_kind from previous BB: - If jmp_kind is neither JmpCall nor JmpRet (ie. is JmpNone, JmpBoring, JmpCond or JmpSyscall) and we transferred from one ELF object/section to another, it must be a function call to a shared library -- treat as a call. This catches jmps from PLT code. - If this is the first BB of a function, treat as a call. This catches tail calls (which gcc uses for "return f()" with -O2). [What if a function had a 'goto' back to its beginning? Would that be interpreted as a call?] - Unwind the shadow call stack if necessary. [when is "necessary"? If the real %esp > the shadow stack %esp?] - If this is a function return and there was no shadow stack unwinding, this must be a RET control transfer (typically used in the runtime linker). Pop the shadow call stack, setting the previous BB address to call site and override jmpkind with a CALL. By this, you get 2 function calls from a calling site. [I don't understand this... What is a "RET control transfer"? Why do you end up with 2 function calls -- is that a bad thing?] - If we're treating the control transfer as a call, push new function call from previous BB to current BB on shadow call stack. [when is this information used?] - Save current BB address to be available for call to handler in next BB. Other actions: When entering a signal handler, first push a separation marker on the thread's shadow stack, then use it as normal. The marker is used for unwinding when leaving the signal handler. This is fine as there is no scheduling among signal handlers of one thread. Special care is needed at thread switches and enter/leave of signal handlers, as we need separate shadow call stacks. [Do you mean "separate shadow call stacks for each thread"?] Known bugs: - should check if unwinding is necessary when ESP is explicitly written to. -------- What about stack switching -- does it cope with that? (Not that Valgrind in general does...) N |
|
From: Josef W. <Jos...@gm...> - 2004-06-25 10:17:54
|
On Monday 21 June 2004 12:15, Nicholas Nethercote wrote: > Josef, > > I've finally (it only took 6 months!) had a close look at your description > of how Calltree accurately tracks function entry/exit. > > I've paraphrased your description to help me understand it better, but I'm > still not quite clear on some points. I looked at the code, but found it > hard to understand. Could you help me? I've written my questions in > square brackets. Here's the description. > > -------- > > Data structures: > > - have a shadow call stack for every thread > [not sure exactly what goes on this] That's the resizable array of struct _call_entry's. Probably most important for call tracking is the %ESP value directly after a CALL, and a pointer to some struct storing information about the call arc or the called function. The esp value is needed to be able to robustly unwind correctly at %esp changes with %esp > stored esp on shadow stack. > Action at BB start -- depends on jmp_kind from previous BB: > > - If jmp_kind is neither JmpCall nor JmpRet (ie. is JmpNone, JmpBoring, > JmpCond or JmpSyscall) and we transferred from one ELF object/section to > another, it must be a function call to a shared library -- treat as a > call. This catches jmps from PLT code. > > - If this is the first BB of a function, treat as a call. This catches > tail calls (which gcc uses for "return f()" with -O2). > [What if a function had a 'goto' back to its beginning? Would that be > interpreted as a call?] Yes. IMHO, there is no way to distinguish between optimized tail recursion using a jump and regular jumping. But as most functions need parameters on the stack, a normal jump will rarely jump to the first BB of a function, wouldn't it? > - Unwind the shadow call stack if necessary. > [when is "necessary"? If the real %esp > the shadow stack %esp?] Yes. Currently I do this at every BB boundary, but perhaps it should be checked at every %esp change. Then, OTOH, it would look strange to attribute instructions of one BB to different functions? > - If this is a function return and there was no shadow stack unwinding, > this must be a RET control transfer (typically used in the runtime > linker). Pop the shadow call stack, setting the previous BB address to > call site and override jmpkind with a CALL. By this, you get 2 function > calls from a calling site. > [I don't understand this... What is a "RET control transfer"? Why do > you end up with 2 function calls -- is that a bad thing?] If there is a RET instruction, this usually should unwind (i.e. leave a function) at least one entry of the shadow call stack. But this doesn't need to be the case, i.e. even after a RET, %esp could be lower or equal to the one on the shadow stack. E.g. suppose PUSH addr RET This is only another way of saying "JMP addr", and doesn't add/remove any stack frame at all. Now, if addr is (according to debug information) inside of another function, this is a JMP between functions, let's say from B to C. Suppose B was called from A, I generate a RETURN event to A and a CALL event from A to C in this case. > - If we're treating the control transfer as a call, push new function call > from previous BB to current BB on shadow call stack. > [when is this information used?] I meant: Append a struct call_entry to the shadow stack (together with the current %esp value). As I said before, the shadow stack is used for robust unwinding. > - Save current BB address to be available for call to handler in next BB. > > > Other actions: > > When entering a signal handler, first push a separation marker on the > thread's shadow stack, then use it as normal. The marker is used for > unwinding when leaving the signal handler. This is fine as there is no > scheduling among signal handlers of one thread. > > Special care is needed at thread switches and enter/leave of signal > handlers, as we need separate shadow call stacks. > [Do you mean "separate shadow call stacks for each thread"?] Yes. > What about stack switching -- does it cope with that? (Not that Valgrind > in general does...) No. If you could give me a hint how to do it, I would be pleased. The problem here IMHO is: How to distinguish among a stack switch and allocating a huge array on the stack? Josef |