Re: [Valgrind-developers] Re: Tracking function entry/exit (fwd)

[Josef W. <Jos...@gm...>]

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