Infrastructure for SW CallTrees and group operations
[dyninst.git] / stackwalk / src / x86-swk.C
1 /*
2  * Copyright (c) 1996-2011 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include "stackwalk/h/basetypes.h"
33 #include "stackwalk/h/swk_errors.h"
34 #include "stackwalk/h/procstate.h"
35 #include "stackwalk/h/framestepper.h"
36 #include "stackwalk/h/frame.h"
37 #include "stackwalk/h/walker.h"
38
39 #include "stackwalk/src/symtab-swk.h"
40 #include "stackwalk/src/dbgstepper-impl.h"
41 #include "stackwalk/src/x86-swk.h"
42 #include "stackwalk/src/sw.h"
43 #include "stackwalk/src/libstate.h"
44
45 #include "common/h/lru_cache.h"
46
47 #include "dynutil/h/SymReader.h"
48
49 using namespace Dyninst;
50 using namespace Dyninst::Stackwalker;
51
52 bool ProcSelf::getRegValue(Dyninst::MachRegister reg, THR_ID, Dyninst::MachRegisterVal &val)
53 {
54   unsigned long *frame_pointer;
55
56 #if defined(arch_x86_64) && (defined(os_linux) || defined(os_freebsd))
57   __asm__("mov %%rbp, %0\n"
58           : "=r"(frame_pointer));
59 #elif defined(os_linux) || defined(os_freebsd)
60   __asm__("movl %%ebp, %0\n"
61           : "=r"(frame_pointer));
62 #elif defined(os_windows)
63    __asm
64    {
65       mov frame_pointer, ebp ;
66    }   
67 #endif
68
69   frame_pointer = (unsigned long *) *frame_pointer;
70   
71   switch(reg.val())
72   {
73      case Dyninst::x86_64::irip:
74      case Dyninst::x86::ieip:
75      case Dyninst::iReturnAddr:
76         val = (Dyninst::MachRegisterVal) frame_pointer[1];
77         break;
78      case Dyninst::iFrameBase:
79         val = (Dyninst::MachRegisterVal) frame_pointer[0];
80         break;
81      case Dyninst::x86_64::irsp:
82      case Dyninst::x86::iesp:
83      case Dyninst::iStackTop:
84         val = (Dyninst::MachRegisterVal) (frame_pointer + 2);
85         break;      
86      default:
87         sw_printf("[%s:%u] - Request for unsupported register %s\n",
88                   __FILE__, __LINE__, reg.name().c_str());
89         setLastError(err_badparam, "Unknown register passed in reg field");
90   }
91
92   return true;
93 }
94
95 Dyninst::Architecture ProcSelf::getArchitecture()
96 {
97    if (sizeof(void *) == 8)
98       return Arch_x86_64;
99    return Arch_x86;
100 }
101
102 static gcframe_ret_t HandleStandardFrame(const Frame &in, Frame &out, ProcessState *proc)
103 {
104   Address in_fp, out_sp;
105   const unsigned addr_width = proc->getAddressWidth();
106   bool result;
107
108   struct {
109     Address out_fp;
110     Address out_ra;
111   } ra_fp_pair;
112
113   in_fp = in.getFP();
114   out_sp = in_fp + (2 * addr_width);
115
116 #if defined(arch_x86_64)
117   /**
118    * On AMD64 we may be reading from a process with a different
119    * address width than the current one.  We'll do the read at
120    * the correct size, then convert the addresses into the 
121    * local size
122    **/
123   struct {
124      unsigned out_fp;
125      unsigned out_ra;
126   } ra_fp_pair32;
127   if (addr_width != sizeof(Address))
128   {
129      result = proc->readMem(&ra_fp_pair32, in_fp, 
130                             sizeof(ra_fp_pair32));
131      ra_fp_pair.out_fp = (Address) ra_fp_pair32.out_fp;
132      ra_fp_pair.out_ra = (Address) ra_fp_pair32.out_ra;
133   }
134   else
135 #endif
136   {
137     result = proc->readMem(&ra_fp_pair, in_fp, sizeof(ra_fp_pair));
138   }
139
140   if (!result) {
141     sw_printf("[%s:%u] - Couldn't read from %lx\n", __FILE__, __LINE__, in_fp);
142     return gcf_error;
143   }
144   
145   if (!ra_fp_pair.out_ra) {
146      return gcf_not_me;
147   }
148
149   out.setFP(ra_fp_pair.out_fp);
150   out.setRA(ra_fp_pair.out_ra);
151   out.setSP(out_sp);
152
153   return gcf_success;
154 }
155
156 bool Walker::checkValidFrame(const Frame &in, const Frame &out)
157 {
158    if (out.getSP() <= in.getSP()) {
159       sw_printf("[%s:%u] - Stackwalk went backwards, %lx to %lx\n",
160                 __FILE__, __LINE__, in.getSP(), out.getSP());
161       return false;
162    }
163    return true;
164 }
165
166 gcframe_ret_t FrameFuncStepperImpl::getCallerFrame(const Frame &in, Frame &out)
167 {
168   if (!in.getFP())
169      return gcf_not_me;
170
171   FrameFuncHelper::alloc_frame_t frame = helper->allocatesFrame(in.getRA());
172   if (frame.first != FrameFuncHelper::standard_frame) {
173      return gcf_not_me;
174   }
175
176   return HandleStandardFrame(in, out, getProcessState());
177 }
178  
179 std::map<Dyninst::PID, LookupFuncStart*> LookupFuncStart::all_func_starts;
180
181 static int hash_address(Address a)
182 {
183    return (int) a;
184 }
185
186 LookupFuncStart::LookupFuncStart(ProcessState *proc_) :
187    FrameFuncHelper(proc_),
188    cache(cache_size, hash_address)
189 {
190    all_func_starts[proc->getProcessId()] = this;
191    ref_count = 1;
192 }
193
194 LookupFuncStart::~LookupFuncStart()
195 {
196    Dyninst::PID pid = proc->getProcessId();
197    all_func_starts.erase(pid);
198 }
199
200 LookupFuncStart *LookupFuncStart::getLookupFuncStart(ProcessState *p)
201 {
202    Dyninst::PID pid = p->getProcessId();
203    std::map<Dyninst::PID, LookupFuncStart*>::iterator i = all_func_starts.find(pid);
204    if (i == all_func_starts.end()) {
205       return new LookupFuncStart(p);
206    }
207    (*i).second->ref_count++;
208    return (*i).second;
209 }
210
211 void LookupFuncStart::releaseMe()
212 {
213    ref_count--;
214    if (!ref_count)
215       delete this;
216 }
217
218 FrameFuncStepperImpl::FrameFuncStepperImpl(Walker *w, FrameStepper *parent_,
219                                            FrameFuncHelper *helper_) :
220    FrameStepper(w),
221    parent(parent_),
222    helper(helper_)
223 {
224    helper = helper_ ? helper_ : LookupFuncStart::getLookupFuncStart(getProcessState());
225 }
226
227 FrameFuncStepperImpl::~FrameFuncStepperImpl()
228 {
229    LookupFuncStart *lookup = dynamic_cast<LookupFuncStart*>(helper);
230    if (lookup)
231       lookup->releaseMe();
232    else if (helper)
233       delete helper;
234 }
235
236 unsigned FrameFuncStepperImpl::getPriority() const
237 {
238   return frame_priority;
239 }
240
241 /**
242  * Look at the first few bytes in the function and see if they contain
243  * the standard set to allocate a stack frame.
244  **/
245 #define FUNCTION_PROLOG_TOCHECK 12
246 static unsigned char push_ebp = 0x55;
247 static unsigned char mov_esp_ebp[2][2] = { { 0x89, 0xe5 },
248                                            { 0x8b, 0xec } };
249 static unsigned char rex_mov_esp_ebp = 0x48;
250
251 FrameFuncHelper::alloc_frame_t LookupFuncStart::allocatesFrame(Address addr)
252 {
253    LibAddrPair lib;
254    unsigned char mem[FUNCTION_PROLOG_TOCHECK];
255    Address func_addr;
256    unsigned cur;
257    int push_ebp_pos = -1, mov_esp_ebp_pos = -1;
258    alloc_frame_t res = alloc_frame_t(unknown_t, unknown_s);
259    bool result;
260    SymReader *reader;
261    Offset off;
262    Symbol_t sym;
263
264    result = checkCache(addr, res);
265    if (result) {
266       sw_printf("[%s:%u] - Cached value for %lx is %d/%d\n",
267                 __FILE__, __LINE__, addr, (int) res.first, (int) res.second);
268       return res;
269    }
270
271    result = proc->getLibraryTracker()->getLibraryAtAddr(addr, lib);
272    if (!result)
273    {
274       sw_printf("[%s:%u] - No library at %lx\n", __FILE__, __LINE__, addr);
275       goto done;
276    }
277
278    reader = LibraryWrapper::getLibrary(lib.first);
279    if (!reader) {
280       sw_printf("[%s:%u] - Failed to open symbol reader %s\n",
281                 __FILE__, __LINE__, lib.first.c_str() );
282       goto done;
283    }   
284    off = addr - lib.second;
285    sym = reader->getContainingSymbol(off);
286    if (!reader->isValidSymbol(sym)) {
287       sw_printf("[%s:%u] - Could not find symbol in binary\n", __FILE__, __LINE__);
288       goto done;
289    }
290    func_addr = reader->getSymbolOffset(sym) + lib.second;
291
292    result = proc->readMem(mem, func_addr, FUNCTION_PROLOG_TOCHECK);
293    if (!result) {
294       sw_printf("[%s:%u] - Error.  Couldn't read from memory at %lx\n",
295                 __FILE__, __LINE__, func_addr);
296       goto done;
297    }
298    
299    //Try to find a 'push (r|e)bp'
300    for (cur=0; cur<FUNCTION_PROLOG_TOCHECK; cur++)
301    {
302       if (mem[cur] == push_ebp)
303       {
304          push_ebp_pos = cur;
305          break;
306       }
307    }
308
309    //Try to find the mov esp->ebp
310    for (; cur<FUNCTION_PROLOG_TOCHECK; cur++)
311    {
312       if (proc->getAddressWidth() == 8) {
313          if (mem[cur] != rex_mov_esp_ebp)
314             continue;
315          cur++;
316       }
317       
318       if (cur+1 >= FUNCTION_PROLOG_TOCHECK) 
319          break;
320       if ((mem[cur] == mov_esp_ebp[0][0] && mem[cur+1] == mov_esp_ebp[0][1]) || 
321           (mem[cur] == mov_esp_ebp[1][0] && mem[cur+1] == mov_esp_ebp[1][1])) {
322          if (proc->getAddressWidth() == 8) 
323             mov_esp_ebp_pos = cur-1;
324          else
325             mov_esp_ebp_pos = cur;
326          break;
327       }
328    }
329
330    if (push_ebp_pos != -1 && mov_esp_ebp_pos != -1)
331       res.first = standard_frame;
332    else if (push_ebp_pos != -1 && mov_esp_ebp_pos == -1)
333       res.first = savefp_only_frame;
334    else 
335       res.first = no_frame;
336    
337    if (push_ebp_pos != -1 && addr <= func_addr + push_ebp_pos)
338       res.second = unset_frame;
339    else if (mov_esp_ebp_pos != -1 && addr <= func_addr + mov_esp_ebp_pos)
340       res.second = halfset_frame;
341    else
342       res.second = set_frame;
343
344  done:
345    sw_printf("[%s:%u] - Function containing %lx has frame type %d/%d\n",
346              __FILE__, __LINE__, addr, (int) res.first, (int) res.second);
347    updateCache(addr, res);
348    return res;
349 }
350
351 void LookupFuncStart::updateCache(Address addr, alloc_frame_t result)
352 {
353    cache.insert(addr, result);
354 }
355
356 bool LookupFuncStart::checkCache(Address addr, alloc_frame_t &result)
357 {
358    return cache.lookup(addr, result);
359 }
360
361 void LookupFuncStart::clear_func_mapping(Dyninst::PID pid)
362 {
363    std::map<Dyninst::PID, LookupFuncStart *>::iterator i;
364    i = all_func_starts.find(pid);
365    if (i == all_func_starts.end())
366       return;
367
368    LookupFuncStart *fs = (*i).second;
369    all_func_starts.erase(i);
370    
371    delete fs;
372 }
373
374 gcframe_ret_t DyninstInstrStepperImpl::getCallerFrameArch(const Frame &in, Frame &out, 
375                                                           Address /*base*/, Address lib_base,
376                                                           unsigned /*size*/, unsigned stack_height)
377 {
378   gcframe_ret_t ret = HandleStandardFrame(in, out, getProcessState());
379   if (ret != gcf_success)
380     return ret;
381   out.setRA(out.getRA() + lib_base);
382   out.setSP(out.getSP() + stack_height);
383   return gcf_success;
384 }
385
386 #include "analysis_stepper.h"
387 gcframe_ret_t AnalysisStepperImpl::getCallerFrameArch(height_pair_t height,
388                                                       const Frame &in, Frame &out)
389 {
390    Address in_sp = in.getSP(),
391            in_fp = in.getFP(),
392            out_sp = 0,
393            out_ra = 0,
394            out_ra_addr = 0,
395            out_fp = 0,
396            out_fp_addr = 0;
397    StackAnalysis::Height sp_height = height.first;
398    StackAnalysis::Height fp_height = height.second;
399    location_t out_ra_loc, out_fp_loc;
400
401    ProcessState *proc = getProcessState();
402
403    if (sp_height == StackAnalysis::Height::bottom) {
404       sw_printf("[%s:%u] - Analysis didn't find a stack height\n", 
405                 __FILE__, __LINE__);
406       return gcf_not_me;
407    }
408
409    // SP height is the distance from the last SP of the previous frame
410    // to the SP in this frame at the current offset.
411    // Since we are walking to the previous frame,
412    // we subtract this height to get the outgoing SP
413    out_sp = in_sp - sp_height.height();
414
415    // Since we know the outgoing SP,
416    // the outgoing RA must be located just below it
417    out_ra_addr = out_sp - proc->getAddressWidth();
418    out_ra_loc.location = loc_address;
419    out_ra_loc.val.addr = out_ra_addr;
420
421    bool result = proc->readMem(&out_ra, out_ra_addr, proc->getAddressWidth());
422    if (!result) {
423       sw_printf("[%s:%u] - Error reading from return location %lx on stack\n",
424                 __FILE__, __LINE__, out_ra_addr);
425       return gcf_not_me;
426    }
427
428    if (fp_height != StackAnalysis::Height::bottom) {
429       // FP height is the distance from the last SP of the previous frame
430       // to the FP in this frame at the current offset.
431       // If analysis finds this height,
432       // then out SP + FP height should equal in FP.
433       // We then assume that in FP points to out FP.
434       out_fp_addr = out_sp + fp_height.height();
435
436       if (out_fp_addr != in_fp) {
437          sw_printf(
438             "[%s:%u] - Warning - current FP %lx does not point to next FP located at %lx\n",
439             __FILE__, __LINE__, in_fp, out_fp_addr);
440       }
441
442       result = proc->readMem(&out_fp, out_fp_addr, proc->getAddressWidth());
443       if (result) {
444          out_fp_loc.location = loc_address;
445          out_fp_loc.val.addr = out_fp_addr;
446
447          out.setFPLocation(out_fp_loc);
448          out.setFP(out_fp);
449       }
450       else {
451          sw_printf("[%s:%u] - Failed to read FP value\n", __FILE__, __LINE__);
452       }
453    }
454    else {
455       sw_printf("[%s:%u] - Did not find frame pointer in analysis\n",
456                 __FILE__, __LINE__);
457    }
458
459    out.setSP(out_sp);
460    out.setRALocation(out_ra_loc);
461    out.setRA(out_ra);
462
463    return gcf_success;
464 }
465
466 gcframe_ret_t DyninstDynamicStepperImpl::getCallerFrameArch(const Frame &in, Frame &out, 
467                                                             Address /*base*/, Address lib_base,
468                                                             unsigned /*size*/, unsigned stack_height,
469                                                             Address orig_ra, bool pEntryExit)
470 {
471   bool result = false;
472   const unsigned addr_width = getProcessState()->getAddressWidth();
473   unsigned long sp_value = 0x0;
474   Address sp_addr = 0x0;
475
476   // Handle frameless instrumentation
477   if (0x0 != orig_ra)
478   {
479     location_t unknownLocation;
480     unknownLocation.location = loc_unknown;
481     out.setRA(orig_ra);
482     out.setFP(in.getFP());
483     out.setSP(in.getSP()); //Not really correct, but difficult to compute and unlikely to matter
484     out.setRALocation(unknownLocation);
485     sw_printf("[%s:%u] - DyninstDynamicStepper handled frameless instrumentation\n",
486               __FILE__, __LINE__);
487     return gcf_success;
488   }
489
490   // Handle case where *previous* frame was entry/exit instrumentation
491   if (pEntryExit)
492   {
493     Address ra_value = 0x0;
494
495     // RA is pointed to by input SP
496     // TODO may have an additional offset in some cases...
497     Address newRAAddr = in.getSP();
498
499     location_t raLocation;
500     raLocation.location = loc_address;
501     raLocation.val.addr = newRAAddr;
502     out.setRALocation(raLocation);
503
504     // TODO handle 64-bit mutator / 32-bit mutatee
505
506     // get value of RA
507     result = getProcessState()->readMem(&ra_value, newRAAddr, addr_width);
508
509     if (!result) {
510       sw_printf("[%s:%u] - Couldn't read from %lx\n", __FILE__, __LINE__, newRAAddr);
511       return gcf_error;
512     }
513
514     out.setRA(ra_value);
515     out.setFP(in.getFP()); // FP stays the same
516     out.setSP(newRAAddr + addr_width);
517     sw_printf("[%s:%u] - DyninstDynamicStepper handled post entry/exit instrumentation\n",
518               __FILE__, __LINE__);
519     return gcf_success;
520   }
521
522   gcframe_ret_t ret = HandleStandardFrame(in, out, getProcessState());
523   if (ret != gcf_success)
524     return ret;
525   out.setRA(out.getRA() + lib_base);
526
527   // For tramps with frames, read the saved stack pointer
528   // TODO does this apply to static instrumentation?
529   if (stack_height)
530   {
531     sp_addr = in.getFP() + stack_height;
532     result = getProcessState()->readMem(&sp_value, sp_addr, addr_width);
533
534     if (!result) {
535       sw_printf("[%s:%u] - Couldn't read from %lx\n", __FILE__, __LINE__, sp_addr);
536       return gcf_error;
537     }
538
539     sw_printf("[%s:%u] - Read SP %p from addr %p, using stack height of 0x%lx\n",
540               __FILE__, __LINE__, sp_value, sp_addr, stack_height);
541     out.setSP(sp_value);
542   }
543
544   sw_printf("[%s:%u] - DyninstDynamicStepper handled normal instrumentation\n",
545             __FILE__, __LINE__);
546   return gcf_success;
547 }
548
549 namespace Dyninst {
550 namespace Stackwalker {
551 void getTrapInstruction(char *buffer, unsigned buf_size, 
552                         unsigned &actual_len, bool include_return)
553 {
554    if (include_return)
555    {
556       assert(buf_size >= 2);
557       buffer[0] = 0xcc; //trap
558       buffer[1] = 0xc3; //ret
559       actual_len = 2;
560       return;
561    }
562    assert(buf_size >= 1);
563    buffer[0] = 0xcc; //trap
564    actual_len = 1;
565    return;
566 }
567 }
568 }
569