1 2This file describes in detail how Calltree accurately tracks function 3entry/exit, one of those harder-than-you'd-think things. 4 5----------------------------------------------------------------------------- 6Josef's description 7----------------------------------------------------------------------------- 8From: Josef Weidendorfer <Josef.Weidendorfer@gmx.de> 9To: Nicholas Nethercote <njn25@cam.ac.uk> 10Cc: valgrind-developers@lists.sourceforge.net 11Subject: [Valgrind-developers] Re: Tracking function entry/exit 12 13On Sunday 25 January 2004 16:53, Nicholas Nethercote wrote: 14> Josef, 15> 16> The topic of tracking function entry/exit has come up a few times on the 17> mailing lists recently. My usual answer is that it's difficult to do 18> correctly. However, you seem to do it with Calltree. I looked at the 19> source code a bit, and it looks like you are doing some reasonably 20> complicated things to get it right, eg. unwinding the stack. How robust 21> is your approach? Can you briefly explain how it works? 22 23A note before describing the mechanism: I need to have a helper call at start 24of every BB anyway, so I use this helper to do the tracking. This of course 25has some overhead, and perhaps can be avoided, but it seems to add to the 26robustness. I have a bug fix here for reentrent entering of a signal handler 27(2 bug reports). Otherwise I have no bug reports, so I assume that the 28mechanism to be quite robust. 29 30I have a shadow call stack for every thread. For signal handlers of a thread, 31I first PUSH a separation marker on the shadow stack, and use the stack as 32normal. The marker is used for unwinding when leaving the signal handler. 33This is fine as there is no scheduling among signal handlers of one thread. 34 35Instrumentation of calltree: 36* Store at the end of each basic block the jmpkind into a tool-global, static 37variable. 38* At the start of every BB, jump to a helper function. 39 40The helper function does the following regarding function call tracking: 41- for a control transfer to another ELF object/ELF section, override jmpkind 42 with a CALL (*1) 43- for a control transfer to the 1st basic block of a function, override 44 jmpkind with a CALL (*2) 45- do unwinding if needed (i.e, POPs of the shadow call stack) 46- if jmpkind is RET and there was no unwinding/POP: 47 - if our call stack is empty, simulate a CALL lasting from beginning 48 (with Valgrind 2.1.x, this is not needed any more, as we run on 49 simulated CPU from first client instruction) 50 - otherwise this is a JMP using a RET instruction (typically used in 51 the runtime linker). Do a POP, setting previous BB address to call 52 site and override jmpkind with a CALL. By this, you get 2 function 53 calls from a calling site. 54- when jmpkind is a CALL, push new function call from previous BB to current 55 BB on shadow call stack. 56- Save current BB address to be available for call to handler in next BB. 57 58Special care is needed at thread switches and enter/leave of signal handlers, 59as we need separate shadow call stacks. 60 61Known bug: We should check for the need of unwinding when ESP is explicitly 62written to. I hope this doesn't create too much overhead. 63 64Remarks: 65(*1) Jumps between ELF objects are function calls to a shared library. This is 66 mainly done to catch the JMP from PLT code. 67(*2) This is what your function tracking skin/tool does. It is needed here 68 mainly to catch tail recursion. In general, for functions doing a 69 "return otherfunction()", GCC produces JMPs with -O2. 70 71Additional points: 72- If I need a name for a function, but there is no debug info, I use the 73 instruction address minus the load offset of the corresponding ELF object 74 (if there is one) to get a relative address for that ELF object. This 75 offset can be used with objdump later in postprocessing tools (e.g. 76 objdump). I would suggest this change even for cachegrind instead of a 77 "???". 78- I introduced the ability to specify functions to be "skipped". This means 79 that execution of these functions is attributed to the calling function. 80 The default is to skip all functions located in PLT sections. Thus, in 81 effect, costs of PLT functions are attributed to callers, and the call to 82 a shared library function starts directly with code in the other ELF 83 object. 84- As Vg 2.1.x does pointerchecking, the instrumentation can't write to 85 memory space of Valgrind any longer. Currently, my tool needs 86 "--pointercheck=no" to be able to run. Jeremy and me already agreed on 87 replacing current LD/ST with a CLD/CST (Client Load/Store) with pointer 88 check and keep original LD/ST for tool usage without pointerchecking. 89 90Looking at these things, it seems possible to do function tracking at end of a 91basic block instead of the beginning of the next BB. This way, we can perhaps 92avoid calls to helpers at every BB. 93 94From my point of view, it would be great to integrate optional function 95tracking into Valgrind core with some hooks. 96 97Josef 98 99 100----------------------------------------------------------------------------- 101Josef's clarification of Nick's summary of Josef's description 102----------------------------------------------------------------------------- 103On Monday 21 June 2004 12:15, Nicholas Nethercote wrote: 104 105> I've paraphrased your description to help me understand it better, but I'm 106> still not quite clear on some points. I looked at the code, but found it 107> hard to understand. Could you help me? I've written my questions in 108> square brackets. Here's the description. 109> 110> -------- 111> 112> Data structures: 113> 114> - have a shadow call stack for every thread 115> [not sure exactly what goes on this] 116 117That's the resizable array of struct _call_entry's. 118Probably most important for call tracking is the %ESP value 119directly after a CALL, and a pointer to some struct storing information 120about the call arc or the called function. 121 122The esp value is needed to be able to robustly unwind correctly at %esp 123changes with %esp > stored esp on shadow stack. 124 125> Action at BB start -- depends on jmp_kind from previous BB: 126> 127> - If jmp_kind is neither JmpCall nor JmpRet (ie. is JmpNone, JmpBoring, 128> JmpCond or JmpSyscall) and we transferred from one ELF object/section to 129> another, it must be a function call to a shared library -- treat as a 130> call. This catches jmps from PLT code. 131> 132> - If this is the first BB of a function, treat as a call. This catches 133> tail calls (which gcc uses for "return f()" with -O2). 134> [What if a function had a 'goto' back to its beginning? Would that be 135> interpreted as a call?] 136 137Yes. IMHO, there is no way to distinguish between optimized tail recursion 138using a jump and regular jumping. But as most functions need parameters on 139the stack, a normal jump will rarely jump to the first BB of a function, 140wouldn't it? 141 142> - Unwind the shadow call stack if necessary. 143> [when is "necessary"? If the real %esp > the shadow stack %esp?] 144 145Yes. Currently I do this at every BB boundary, but perhaps it should be 146checked at every %esp change. Then, OTOH, it would look strange to attribute 147instructions of one BB to different functions? 148 149> - If this is a function return and there was no shadow stack unwinding, 150> this must be a RET control transfer (typically used in the runtime 151> linker). Pop the shadow call stack, setting the previous BB address to 152> call site and override jmpkind with a CALL. By this, you get 2 function 153> calls from a calling site. 154> [I don't understand this... What is a "RET control transfer"? Why do 155> you end up with 2 function calls -- is that a bad thing?] 156 157If there is a RET instruction, this usually should unwind (i.e. leave a 158function) at least one entry of the shadow call stack. But this doesn't need 159to be the case, i.e. even after a RET, %esp could be lower or equal to the 160one on the shadow stack. E.g. suppose 161 162 PUSH addr 163 RET 164 165This is only another way of saying "JMP addr", and doesn't add/remove any 166stack frame at all. 167Now, if addr is (according to debug information) inside of another function, 168this is a JMP between functions, let's say from B to C. Suppose B was called 169from A, I generate a RETURN event to A and a CALL event from A to C in this 170case. 171 172> - If we're treating the control transfer as a call, push new function call 173> from previous BB to current BB on shadow call stack. 174> [when is this information used?] 175 176I meant: Append a struct call_entry to the shadow stack (together with the 177current %esp value). As I said before, the shadow stack is used for robust 178unwinding. 179 180> - Save current BB address to be available for call to handler in next BB. 181> 182> 183> Other actions: 184> 185> When entering a signal handler, first push a separation marker on the 186> thread's shadow stack, then use it as normal. The marker is used for 187> unwinding when leaving the signal handler. This is fine as there is no 188> scheduling among signal handlers of one thread. 189> 190> Special care is needed at thread switches and enter/leave of signal 191> handlers, as we need separate shadow call stacks. 192> [Do you mean "separate shadow call stacks for each thread"?] 193 194Yes. 195 196> What about stack switching -- does it cope with that? (Not that Valgrind 197> in general does...) 198 199No. 200If you could give me a hint how to do it, I would be pleased. The problem here 201IMHO is: How to distinguish among a stack switch and allocating a huge array 202on the stack? 203 204Josef 205 206