GCC 4.8 build fixes: ensure all extern template declarations are in fact extern'ed...
[dyninst.git] / stackwalk / src / analysis_stepper.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #include "stackwalk/src/analysis_stepper.h"
32 #include "dataflowAPI/h/stackanalysis.h"
33 #include "stackwalk/h/swk_errors.h"
34 #include "stackwalk/h/frame.h"
35 #include "stackwalk/src/sw.h"
36
37 #include "parseAPI/h/CodeSource.h"
38 #include "parseAPI/h/SymLiteCodeSource.h"
39 #include "parseAPI/h/CodeObject.h"
40
41 #include "instructionAPI/h/InstructionDecoder.h"
42
43 #if defined(WITH_SYMLITE)
44 #include "symlite/h/SymLite-elf.h"
45 #elif defined(WITH_SYMTAB_API)
46 #include "symtabAPI/h/Symtab.h"
47 #include "symtabAPI/h/SymtabReader.h"
48 using namespace SymtabAPI;
49 #else
50 #error "No defined symbol reader"
51 #endif
52
53 using namespace Dyninst;
54 using namespace Stackwalker;
55 using namespace ParseAPI;
56 using namespace std;
57
58 std::map<string, CodeObject *> AnalysisStepperImpl::objs;
59 const AnalysisStepperImpl::height_pair_t AnalysisStepperImpl::err_height_pair;
60 std::map<string, CodeSource*> AnalysisStepperImpl::srcs;
61 std::map<string, SymReader*> AnalysisStepperImpl::readers;
62
63 extern template class boost::shared_ptr<Dyninst::InstructionAPI::Instruction>;
64
65
66 AnalysisStepperImpl::AnalysisStepperImpl(Walker *w, AnalysisStepper *p) :
67    FrameStepper(w),
68    parent(p)
69 {
70     callchecker = new CallChecker(getProcessState());
71 }
72
73 AnalysisStepperImpl::~AnalysisStepperImpl()
74 {
75     delete callchecker;
76 }
77
78
79 #if defined(WITH_SYMLITE)
80 CodeSource *AnalysisStepperImpl::getCodeSource(std::string name)
81 {
82   map<string, CodeSource*>::iterator found = srcs.find(name);
83   if(found != srcs.end()) return found->second;
84   
85   static SymElfFactory factory;
86   
87   SymReader* r = factory.openSymbolReader(name);
88   if(!r) return NULL;
89   
90   
91   SymReaderCodeSource *cs = new SymReaderCodeSource(r);
92   srcs[name] = cs;
93   readers[name] = r;
94   
95   return static_cast<CodeSource *>(cs);
96 }
97 #elif defined(WITH_SYMTAB_API)
98 CodeSource* AnalysisStepperImpl::getCodeSource(std::string name)
99 {
100   map<string, CodeSource*>::iterator found = srcs.find(name);
101   if(found != srcs.end()) return found->second;
102   Symtab* st;
103   if(!Symtab::openFile(st, name)) return NULL;
104   
105   SymtabCodeSource *cs = new SymtabCodeSource(st);
106   srcs[name] = cs;
107   readers[name] = new SymtabReader(st);
108   
109   return static_cast<CodeSource *>(cs);  
110 }
111 #else
112 #error "Do symbol reader implementation"
113
114 #endif
115
116 CodeObject *AnalysisStepperImpl::getCodeObject(string name)
117 {
118    map<string, CodeObject *>::iterator i = objs.find(name);
119    if (i != objs.end()) {
120       return i->second;
121    }
122    
123    CodeSource *code_source = getCodeSource(name);
124    if (!code_source)
125       return NULL;
126    CodeObject *code_object = new CodeObject(code_source);
127    objs[name] = code_object;
128
129    return code_object;
130 }
131
132 gcframe_ret_t AnalysisStepperImpl::getCallerFrameArch(set<height_pair_t> heights,
133         const Frame &in, Frame &out)
134 {
135     ProcessState *proc = getProcessState();
136     
137     bool result = false;
138
139     set<height_pair_t>::iterator heightIter;
140     for (heightIter = heights.begin(); heightIter != heights.end(); ++heightIter) {
141
142         height_pair_t height = *heightIter;
143
144         Address in_sp = in.getSP(),
145                 in_fp = in.getFP(),
146                 out_sp = 0,
147                 out_ra = 0,
148                 out_fp = 0,
149                 out_fp_addr = 0;
150         StackAnalysis::Height sp_height = height.first;
151         StackAnalysis::Height fp_height = height.second;
152         location_t out_ra_loc, out_fp_loc;
153
154         if (sp_height == StackAnalysis::Height::bottom) {
155             sw_printf("[%s:%u] - Analysis didn't find a stack height\n", 
156                     FILE__, __LINE__);
157             continue;
158         } else {
159             
160             // SP height is the distance from the last SP of the previous frame
161             // to the SP in this frame at the current offset.
162             // Since we are walking to the previous frame,
163             // we subtract this height to get the outgoing SP
164             out_sp = in_sp - sp_height.height();
165         }
166
167         // Since we know the outgoing SP,
168         // the outgoing RA must be located just below it
169         if(!getOutRA(out_sp, out_ra, out_ra_loc, proc)) continue;
170
171
172         // If we have multiple potential heights (due to overlapping functions), 
173         // check if potential stack height is valid (verify that calculated RA follows a call instr)
174         if (heights.size() > 1) {
175           if(!validateRA(out_ra)) continue;
176         }
177         if (fp_height == StackAnalysis::Height::bottom)
178         {
179           if(sp_height.height() == -1 * (long)(proc->getAddressWidth()))
180           {
181             //out.setFP(out_sp);
182           }
183         }
184         else
185         {
186             // FP height is the distance from the last SP of the previous frame
187             // to the FP in this frame at the current offset.
188             // If analysis finds this height,
189             // then out SP + FP height should equal in FP.
190             // We then assume that in FP points to out FP.
191             out_fp_addr = out_sp + fp_height.height();
192
193         }
194         
195         if(out_fp_addr)
196         {
197           if (out_fp_addr != in_fp) {
198             sw_printf(
199                       "[%s:%u] - Warning - current FP %lx does not point to next FP located at %lx\n",
200                       FILE__, __LINE__, in_fp, out_fp_addr);
201           }
202           bool resultMem = proc->readMem(&out_fp, out_fp_addr, proc->getAddressWidth());
203           if (resultMem) {
204             out_fp_loc.location = loc_address;
205             out_fp_loc.val.addr = out_fp_addr;
206             
207             out.setFPLocation(out_fp_loc);
208             out.setFP(out_fp);
209           }
210           else {
211             sw_printf("[%s:%u] - Failed to read FP value\n", FILE__, __LINE__);
212           }
213         }
214         else
215         {
216           sw_printf("[%s:%u] - Failed to find FP\n", FILE__, __LINE__);
217         }
218         
219         
220         out.setSP(out_sp);
221         out.setRALocation(out_ra_loc);
222         out.setRA(out_ra);
223
224         if (result) {
225             sw_printf("[%s:%u] - Warning - found multiple valid frames.\n", 
226                     FILE__, __LINE__);
227         } else {
228             sw_printf("[%s:%u] - Found a valid frame\n", 
229                     FILE__, __LINE__);
230             result = true;
231         }
232     }
233     return checkResult(result);
234 }
235
236 CodeRegion* AnalysisStepperImpl::getCodeRegion(std::string name, Offset off)
237 {
238    CodeObject *obj = getCodeObject(name);
239    if (!obj) {
240       return NULL;
241    }
242    set<CodeRegion *> regions;
243    obj->cs()->findRegions(off, regions);
244    
245    if (regions.empty()) {
246       return NULL;
247    }
248    //We shouldn't be dealing with overlapping regions in a live process
249    assert(regions.size() == 1);
250    CodeRegion *region = *(regions.begin());
251    return region;
252 }
253
254
255
256
257 std::set<AnalysisStepperImpl::height_pair_t> AnalysisStepperImpl::analyzeFunction(string name,
258                                                                                   Offset callSite)
259 {
260     set<height_pair_t> err_heights_pair;
261     err_heights_pair.insert(err_height_pair);
262     CodeRegion* region = getCodeRegion(name, callSite);
263     CodeObject* obj = getCodeObject(name);
264     
265     if(!obj || !region) return err_heights_pair;
266     
267     Symbol_t sym = readers[name]->getContainingSymbol(callSite);
268     if (!readers[name]->isValidSymbol(sym)) {
269        sw_printf("[%s:%u] - Could not find symbol at offset %lx\n", FILE__,
270                  __LINE__, callSite);
271        return err_heights_pair;
272     }
273     Address entry_addr = readers[name]->getSymbolOffset(sym);
274     
275     
276     obj->parse(entry_addr, false);
277     ParseAPI::Function* func = obj->findFuncByEntry(region, entry_addr);
278
279     if(!func)
280     {
281       sw_printf("[%s:%u] - Could not find function at offset %lx\n", FILE__,
282                 __LINE__, callSite);
283       return err_heights_pair;
284     }
285
286    //Since there is only one region, there is only one block with the offset
287     // Not actually true; overlapping code is always possible.
288    set<ParseAPI::Block*> blocks;
289    for(auto i = func->blocks().begin();
290        i != func->blocks().end();
291        ++i)
292    {
293      if((*i)->start() <= callSite && (*i)->end() > callSite)
294      {
295        blocks.insert(*i);
296      }
297    }
298    //obj->findBlocks(region, callSite, blocks);
299    if(blocks.size() == 0) {
300       sw_printf("[%s:%u] - Function at entry point %lx did not contain call site %lx\n", FILE__,
301                 __LINE__, entry_addr, callSite);
302      return err_heights_pair;
303    }
304    
305    ParseAPI::Block *block = *(blocks.begin());
306
307    set<height_pair_t> heights;
308    StackAnalysis analysis(func);
309    heights.insert(height_pair_t(analysis.findSP(block, callSite), analysis.findFP(block, callSite)));
310  
311    sw_printf("[%s:%u] - Have %lu possible stack heights in %s at %lx:\n", FILE__, __LINE__, heights.size(), name.c_str(), callSite);
312    for (set<height_pair_t>::iterator i = heights.begin(); 
313         i != heights.end(); i++)
314    {
315       sw_printf("\tsp = %s, fp = %s\n", i->first.format().c_str(), i->second.format().c_str());
316    }
317
318    // Return set of possible heights
319    return heights;
320 }
321
322 gcframe_ret_t AnalysisStepperImpl::getCallerFrame(const Frame &in, Frame &out)
323 {
324    // For now, do not walk frames created by the Dyninst stepper
325    // as the stack pointer may not be correct
326    if (dynamic_cast<DyninstDynamicStepper*>(in.getStepper()))
327    {
328      return gcf_not_me;
329    }
330
331    LibAddrPair libaddr;
332    LibraryState *ls = getProcessState()->getLibraryTracker();
333    if (!ls) {
334       sw_printf("[%s:%u] - Failed to get library tracker\n", FILE__, __LINE__);
335       return gcf_not_me;
336    }
337
338    bool result = ls->getLibraryAtAddr(in.getRA(), libaddr);
339    if (!result) {
340       sw_printf("[%s:%u] - Failed to get library at %lx\n", FILE__, __LINE__, in.getRA());
341       return gcf_not_me;
342    }
343    
344    string name = libaddr.first;
345    Offset offset = in.getRA() - libaddr.second;
346    Offset function_offset = offset;
347    if (in.getRALocation().location != loc_register && !in.nonCall()) {
348       /* Look up by callsite, rather than return address */
349       function_offset = function_offset - 1;
350    }
351
352    set<height_pair_t> heights = analyzeFunction(name, function_offset);
353    gcframe_ret_t ret = gcf_not_me;
354    if (*(heights.begin()) == err_height_pair) {
355      sw_printf("[%s:%u] - Analysis failed on %s at %lx\n", FILE__, __LINE__, name.c_str(), offset);
356      return ret;
357    }
358
359    ret = getCallerFrameArch(heights, in, out);
360    
361    if((ret == gcf_not_me) && in.isTopFrame())
362    {
363      vector<registerState_t> all_defined_heights = fullAnalyzeFunction(name, function_offset);
364      if(!all_defined_heights.empty())
365      {
366          ret = getFirstCallerFrameArch(all_defined_heights, in, out);
367      }
368    }
369    // PGCC can confuse our analysis by popping the RA into a GPR and then storing it somewhere completely
370    // different. This shows up as a stack height of zero in our analysis.
371    // Fixing the infinite loop here.
372    if(in.getRA() == out.getRA()) return gcf_not_me;
373    
374    return ret;
375    
376 }
377
378 unsigned AnalysisStepperImpl::getPriority() const
379 {
380    return analysis_priority;
381 }
382
383 bool AnalysisStepperImpl::isPrevInstrACall(Address addr, Address & target)
384 {
385     return callchecker->isPrevInstrACall(addr, target);
386
387
388 std::vector<AnalysisStepperImpl::registerState_t> AnalysisStepperImpl::fullAnalyzeFunction(std::string name, Offset callSite)
389 {
390    std::vector<registerState_t> heights;
391   
392    CodeObject *obj = getCodeObject(name);
393    if (!obj) {
394      return heights;
395    }
396
397    set<CodeRegion *> regions;
398    obj->cs()->findRegions(callSite, regions);
399    
400    if (regions.empty()) {
401       sw_printf("[%s:%u] - Could not find region at %lx\n", FILE__, __LINE__, callSite);
402       return heights;
403    }
404    //We shouldn't be dealing with overlapping regions in a live process
405    assert(regions.size() == 1);
406    CodeRegion *region = *(regions.begin());
407    
408    set<ParseAPI::Function*> funcs;
409    obj->findFuncs(region, callSite, funcs);
410    if (funcs.empty()) {
411       sw_printf("[%s:%u] - Could not find function at offset %lx\n", FILE__,
412                 __LINE__, callSite);
413       return heights;
414    }
415
416    //Since there is only one region, there is only one block with the offset
417    set<ParseAPI::Block*> blocks;
418    obj->findBlocks(region, callSite, blocks);
419    if(blocks.empty()) return heights;
420    
421    ParseAPI::Block *block = *(blocks.begin());
422
423    for (set<ParseAPI::Function *>::iterator i = funcs.begin(); i != funcs.end(); i++)
424    {
425       StackAnalysis analysis(*i);
426       analysis.findDefinedHeights(block, callSite, heights);
427       
428    }
429
430    sw_printf("[%s:%u] - Have %lu possible stack heights in %s at %lx:\n", FILE__, __LINE__, heights.size(), name.c_str(), callSite);
431
432    // Return set of possible heights
433    return heights;  
434   
435 }
436
437
438 gcframe_ret_t AnalysisStepperImpl::getFirstCallerFrameArch(const std::vector<registerState_t>& heights,
439                                                            const Frame& in,
440                                                            Frame& out)
441 {
442   ProcessState *proc = getProcessState();
443
444   bool result = false;
445
446   vector<registerState_t>::const_iterator heightIter;
447   for (heightIter = heights.begin(); heightIter != heights.end(); ++heightIter) {
448
449     Address
450     out_sp = 0,
451     out_ra = 0;
452     location_t out_ra_loc;
453
454     StackAnalysis::Height sp_height = heightIter->second;
455
456
457     // SP height is the distance from the last SP of the previous frame
458     // to the SP in this frame at the current offset.
459     // Since we are walking to the previous frame,
460     // we subtract this height to get the outgoing SP
461     MachRegisterVal sp_base;
462
463     if (heightIter->first.type() != Absloc::Register) continue;
464     proc->getRegValue(heightIter->first.reg(), in.getThread(), sp_base);
465     out_sp = sp_base - sp_height.height();
466
467     if(heightIter->second.height() == -1 * (long)proc->getAddressWidth())
468     {
469       // FP candidate: register pointing to entry SP
470        sw_printf("[%s:%u] - Found candidate FP %s, height 0x%lx\n", __FILE__, __LINE__,
471                  heightIter->first.format().c_str(), (unsigned long) heightIter->second.height());
472     }
473
474     // Since we know the outgoing SP,
475     // the outgoing RA must be located just below it
476     if(!getOutRA(out_sp, out_ra, out_ra_loc, proc)) continue;
477
478     // If we have multiple potential heights (due to overlapping functions), 
479     // check if potential stack height is valid (verify that calculated RA follows a call instr)
480     if (heights.size() > 1) {
481       if(!validateRA(out_ra)) continue;
482     }
483       
484     out.setSP(out_sp);
485     out.setRALocation(out_ra_loc);
486     out.setRA(out_ra);
487     
488     if (result) {
489       sw_printf("[%s:%u] - Warning - found multiple valid frames.\n", 
490                 FILE__, __LINE__);
491     } else {
492       sw_printf("[%s:%u] - Found a valid frame\n", 
493                 FILE__, __LINE__);
494       result = true;
495     }
496   }
497   return checkResult(result);
498
499 }
500
501 bool AnalysisStepperImpl::validateRA(Address candidateRA)
502 {
503   sw_printf("[%s:%u] - Calling isPrevInstrACall\n", FILE__, __LINE__);
504   Address target;
505   if (!isPrevInstrACall(candidateRA, target)) {
506     sw_printf("[%s:%u] - Return location %lx does not follow a call instruction\n",
507               FILE__, __LINE__, candidateRA);
508     return false;
509   }
510   return true;
511 }
512
513 gcframe_ret_t AnalysisStepperImpl::checkResult(bool result)
514 {
515   if (result) {
516     sw_printf("[%s:%u] - success\n", FILE__, __LINE__); 
517     return gcf_success;
518   } else {
519     sw_printf("[%s:%u] - failed\n", FILE__, __LINE__); 
520     return gcf_not_me;
521   }
522 }
523
524 bool AnalysisStepperImpl::getOutRA(Address out_sp, Address& out_ra, location_t& out_ra_loc, ProcessState* proc)
525 {
526   // Since we know the outgoing SP,
527   // the outgoing RA must be located just below it
528   size_t addr_width = proc->getAddressWidth();
529   Address out_ra_addr = out_sp - addr_width;
530   out_ra_loc.location = loc_address;
531   out_ra_loc.val.addr = out_ra_addr;
532   
533   bool resultMem = proc->readMem(&out_ra, out_ra_addr, addr_width);
534   if (!resultMem) {
535     sw_printf("[%s:%u] - Error reading from return location %lx on stack\n",
536               FILE__, __LINE__, out_ra_addr);
537     return false;
538   }
539   return true;
540 }