CodeObject::findBlocks forces a full parse. Just look in the current function.
[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
64 AnalysisStepperImpl::AnalysisStepperImpl(Walker *w, AnalysisStepper *p) :
65    FrameStepper(w),
66    parent(p)
67 {
68     callchecker = new CallChecker(getProcessState());
69 }
70
71 AnalysisStepperImpl::~AnalysisStepperImpl()
72 {
73     delete callchecker;
74 }
75
76
77 #if defined(WITH_SYMLITE)
78 CodeSource *AnalysisStepperImpl::getCodeSource(std::string name)
79 {
80   map<string, CodeSource*>::iterator found = srcs.find(name);
81   if(found != srcs.end()) return found->second;
82   
83   static SymElfFactory factory;
84   
85   SymReader* r = factory.openSymbolReader(name);
86   if(!r) return NULL;
87   
88   
89   SymReaderCodeSource *cs = new SymReaderCodeSource(r);
90   srcs[name] = cs;
91   readers[name] = r;
92   
93   return static_cast<CodeSource *>(cs);
94 }
95 #elif defined(WITH_SYMTAB_API)
96 CodeSource* AnalysisStepperImpl::getCodeSource(std::string name)
97 {
98   map<string, CodeSource*>::iterator found = srcs.find(name);
99   if(found != srcs.end()) return found->second;
100   Symtab* st;
101   if(!Symtab::openFile(st, name)) return NULL;
102   
103   SymtabCodeSource *cs = new SymtabCodeSource(st);
104   srcs[name] = cs;
105   readers[name] = new SymtabReader(st);
106   
107   return static_cast<CodeSource *>(cs);  
108 }
109 #else
110 #error "Do symbol reader implementation"
111
112 #endif
113
114 CodeObject *AnalysisStepperImpl::getCodeObject(string name)
115 {
116    map<string, CodeObject *>::iterator i = objs.find(name);
117    if (i != objs.end()) {
118       return i->second;
119    }
120    
121    CodeSource *code_source = getCodeSource(name);
122    if (!code_source)
123       return NULL;
124    CodeObject *code_object = new CodeObject(code_source);
125    objs[name] = code_object;
126
127    return code_object;
128 }
129
130 gcframe_ret_t AnalysisStepperImpl::getCallerFrameArch(set<height_pair_t> heights,
131         const Frame &in, Frame &out)
132 {
133     ProcessState *proc = getProcessState();
134     
135     bool result = false;
136
137     set<height_pair_t>::iterator heightIter;
138     for (heightIter = heights.begin(); heightIter != heights.end(); ++heightIter) {
139
140         height_pair_t height = *heightIter;
141
142         Address in_sp = in.getSP(),
143                 in_fp = in.getFP(),
144                 out_sp = 0,
145                 out_ra = 0,
146                 out_fp = 0,
147                 out_fp_addr = 0;
148         StackAnalysis::Height sp_height = height.first;
149         StackAnalysis::Height fp_height = height.second;
150         location_t out_ra_loc, out_fp_loc;
151
152         if (sp_height == StackAnalysis::Height::bottom) {
153             sw_printf("[%s:%u] - Analysis didn't find a stack height\n", 
154                     FILE__, __LINE__);
155             continue;
156         } else {
157             
158             // SP height is the distance from the last SP of the previous frame
159             // to the SP in this frame at the current offset.
160             // Since we are walking to the previous frame,
161             // we subtract this height to get the outgoing SP
162             out_sp = in_sp - sp_height.height();
163         }
164
165         // Since we know the outgoing SP,
166         // the outgoing RA must be located just below it
167         if(!getOutRA(out_sp, out_ra, out_ra_loc, proc)) continue;
168
169
170         // If we have multiple potential heights (due to overlapping functions), 
171         // check if potential stack height is valid (verify that calculated RA follows a call instr)
172         if (heights.size() > 1) {
173           if(!validateRA(out_ra)) continue;
174         }
175         if (fp_height == StackAnalysis::Height::bottom)
176         {
177           if(sp_height.height() == -1 * (long)(proc->getAddressWidth()))
178           {
179             //out.setFP(out_sp);
180           }
181         }
182         else
183         {
184             // FP height is the distance from the last SP of the previous frame
185             // to the FP in this frame at the current offset.
186             // If analysis finds this height,
187             // then out SP + FP height should equal in FP.
188             // We then assume that in FP points to out FP.
189             out_fp_addr = out_sp + fp_height.height();
190
191         }
192         
193         if(out_fp_addr)
194         {
195           if (out_fp_addr != in_fp) {
196             sw_printf(
197                       "[%s:%u] - Warning - current FP %lx does not point to next FP located at %lx\n",
198                       FILE__, __LINE__, in_fp, out_fp_addr);
199           }
200           bool resultMem = proc->readMem(&out_fp, out_fp_addr, proc->getAddressWidth());
201           if (resultMem) {
202             out_fp_loc.location = loc_address;
203             out_fp_loc.val.addr = out_fp_addr;
204             
205             out.setFPLocation(out_fp_loc);
206             out.setFP(out_fp);
207           }
208           else {
209             sw_printf("[%s:%u] - Failed to read FP value\n", FILE__, __LINE__);
210           }
211         }
212         else
213         {
214           sw_printf("[%s:%u] - Failed to find FP\n", FILE__, __LINE__);
215         }
216         
217         
218         out.setSP(out_sp);
219         out.setRALocation(out_ra_loc);
220         out.setRA(out_ra);
221
222         if (result) {
223             sw_printf("[%s:%u] - Warning - found multiple valid frames.\n", 
224                     FILE__, __LINE__);
225         } else {
226             sw_printf("[%s:%u] - Found a valid frame\n", 
227                     FILE__, __LINE__);
228             result = true;
229         }
230     }
231     return checkResult(result);
232 }
233
234 CodeRegion* AnalysisStepperImpl::getCodeRegion(std::string name, Offset off)
235 {
236    CodeObject *obj = getCodeObject(name);
237    if (!obj) {
238       return NULL;
239    }
240    set<CodeRegion *> regions;
241    obj->cs()->findRegions(off, regions);
242    
243    if (regions.empty()) {
244       return NULL;
245    }
246    //We shouldn't be dealing with overlapping regions in a live process
247    assert(regions.size() == 1);
248    CodeRegion *region = *(regions.begin());
249    return region;
250 }
251
252
253
254
255 std::set<AnalysisStepperImpl::height_pair_t> AnalysisStepperImpl::analyzeFunction(string name,
256                                                                                   Offset callSite)
257 {
258     set<height_pair_t> err_heights_pair;
259     err_heights_pair.insert(err_height_pair);
260     CodeRegion* region = getCodeRegion(name, callSite);
261     CodeObject* obj = getCodeObject(name);
262     
263     if(!obj || !region) return err_heights_pair;
264     
265     Symbol_t sym = readers[name]->getContainingSymbol(callSite);
266     if (!readers[name]->isValidSymbol(sym)) {
267        sw_printf("[%s:%u] - Could not find symbol at offset %lx\n", FILE__,
268                  __LINE__, callSite);
269        return err_heights_pair;
270     }
271     Address entry_addr = readers[name]->getSymbolOffset(sym);
272     
273     
274     obj->parse(entry_addr, false);
275     ParseAPI::Function* func = obj->findFuncByEntry(region, entry_addr);
276
277     if(!func)
278     {
279       sw_printf("[%s:%u] - Could not find function at offset %lx\n", FILE__,
280                 __LINE__, callSite);
281       return err_heights_pair;
282     }
283
284    //Since there is only one region, there is only one block with the offset
285     // Not actually true; overlapping code is always possible.
286    set<ParseAPI::Block*> blocks;
287    for(auto i = func->blocks().begin();
288        i != func->blocks().end();
289        ++i)
290    {
291      if((*i)->start() <= callSite && (*i)->end() > callSite)
292      {
293        blocks.insert(*i);
294      }
295    }
296    //obj->findBlocks(region, callSite, blocks);
297    if(blocks.size() == 0) {
298       sw_printf("[%s:%u] - Function at entry point %lx did not contain call site %lx\n", FILE__,
299                 __LINE__, entry_addr, callSite);
300      return err_heights_pair;
301    }
302    
303    ParseAPI::Block *block = *(blocks.begin());
304
305    set<height_pair_t> heights;
306    StackAnalysis analysis(func);
307    heights.insert(height_pair_t(analysis.findSP(block, callSite), analysis.findFP(block, callSite)));
308  
309    sw_printf("[%s:%u] - Have %lu possible stack heights in %s at %lx:\n", FILE__, __LINE__, heights.size(), name.c_str(), callSite);
310    for (set<height_pair_t>::iterator i = heights.begin(); 
311         i != heights.end(); i++)
312    {
313       sw_printf("\tsp = %s, fp = %s\n", i->first.format().c_str(), i->second.format().c_str());
314    }
315
316    // Return set of possible heights
317    return heights;
318 }
319
320 gcframe_ret_t AnalysisStepperImpl::getCallerFrame(const Frame &in, Frame &out)
321 {
322    // For now, do not walk frames created by the Dyninst stepper
323    // as the stack pointer may not be correct
324    if (dynamic_cast<DyninstDynamicStepper*>(in.getStepper()))
325    {
326      return gcf_not_me;
327    }
328
329    LibAddrPair libaddr;
330    LibraryState *ls = getProcessState()->getLibraryTracker();
331    if (!ls) {
332       sw_printf("[%s:%u] - Failed to get library tracker\n", FILE__, __LINE__);
333       return gcf_not_me;
334    }
335
336    bool result = ls->getLibraryAtAddr(in.getRA(), libaddr);
337    if (!result) {
338       sw_printf("[%s:%u] - Failed to get library at %lx\n", FILE__, __LINE__, in.getRA());
339       return gcf_not_me;
340    }
341    
342    string name = libaddr.first;
343    Offset offset = in.getRA() - libaddr.second;
344    Offset function_offset = offset;
345    if (in.getRALocation().location != loc_register && !in.nonCall()) {
346       /* Look up by callsite, rather than return address */
347       function_offset = function_offset - 1;
348    }
349
350    set<height_pair_t> heights = analyzeFunction(name, function_offset);
351    gcframe_ret_t ret = gcf_not_me;
352    if (*(heights.begin()) == err_height_pair) {
353      sw_printf("[%s:%u] - Analysis failed on %s at %lx\n", FILE__, __LINE__, name.c_str(), offset);
354      return ret;
355    }
356
357    ret = getCallerFrameArch(heights, in, out);
358    
359    if((ret == gcf_not_me) && in.isTopFrame())
360    {
361      vector<registerState_t> all_defined_heights = fullAnalyzeFunction(name, function_offset);
362      if(!all_defined_heights.empty())
363      {
364          ret = getFirstCallerFrameArch(all_defined_heights, in, out);
365      }
366    }
367    // PGCC can confuse our analysis by popping the RA into a GPR and then storing it somewhere completely
368    // different. This shows up as a stack height of zero in our analysis.
369    // Fixing the infinite loop here.
370    if(in.getRA() == out.getRA()) return gcf_not_me;
371    
372    return ret;
373    
374 }
375
376 unsigned AnalysisStepperImpl::getPriority() const
377 {
378    return analysis_priority;
379 }
380
381 bool AnalysisStepperImpl::isPrevInstrACall(Address addr, Address & target)
382 {
383     return callchecker->isPrevInstrACall(addr, target);
384
385
386 std::vector<AnalysisStepperImpl::registerState_t> AnalysisStepperImpl::fullAnalyzeFunction(std::string name, Offset callSite)
387 {
388   std::vector<registerState_t> heights;
389   
390    CodeObject *obj = getCodeObject(name);
391    if (!obj) {
392      return heights;
393    }
394
395    set<CodeRegion *> regions;
396    obj->cs()->findRegions(callSite, regions);
397    
398    if (regions.empty()) {
399       sw_printf("[%s:%u] - Could not find region at %lx\n", FILE__, __LINE__, callSite);
400       return heights;
401    }
402    //We shouldn't be dealing with overlapping regions in a live process
403    assert(regions.size() == 1);
404    CodeRegion *region = *(regions.begin());
405    
406    set<ParseAPI::Function*> funcs;
407    obj->findFuncs(region, callSite, funcs);
408    if (funcs.empty()) {
409       sw_printf("[%s:%u] - Could not find function at offset %lx\n", FILE__,
410                 __LINE__, callSite);
411       return heights;
412    }
413
414    //Since there is only one region, there is only one block with the offset
415    set<ParseAPI::Block*> blocks;
416    obj->findBlocks(region, callSite, blocks);
417    if(blocks.empty()) return heights;
418    
419    ParseAPI::Block *block = *(blocks.begin());
420
421    for (set<ParseAPI::Function *>::iterator i = funcs.begin(); i != funcs.end(); i++)
422    {
423       StackAnalysis analysis(*i);
424       analysis.findDefinedHeights(block, callSite, heights);
425       
426    }
427
428    sw_printf("[%s:%u] - Have %lu possible stack heights in %s at %lx:\n", FILE__, __LINE__, heights.size(), name.c_str(), callSite);
429
430    // Return set of possible heights
431    return heights;  
432   
433 }
434
435
436 gcframe_ret_t AnalysisStepperImpl::getFirstCallerFrameArch(const std::vector<registerState_t>& heights,
437                                                            const Frame& in,
438                                                            Frame& out)
439 {
440   ProcessState *proc = getProcessState();
441     
442   bool result = false;
443
444   vector<registerState_t>::const_iterator heightIter;
445   for (heightIter = heights.begin(); heightIter != heights.end(); ++heightIter) {
446
447     Address
448     out_sp = 0,
449     out_ra = 0;
450     location_t out_ra_loc;
451         
452     StackAnalysis::Height sp_height = heightIter->second;
453         
454         
455     // SP height is the distance from the last SP of the previous frame
456     // to the SP in this frame at the current offset.
457     // Since we are walking to the previous frame,
458     // we subtract this height to get the outgoing SP
459     MachRegisterVal sp_base;
460         
461     proc->getRegValue(heightIter->first, in.getThread(), sp_base);
462     out_sp = sp_base - sp_height.height();
463
464     if(heightIter->second.height() == -1 * (long)proc->getAddressWidth())
465     {
466       // FP candidate: register pointing to entry SP
467        sw_printf("[%s:%u] - Found candidate FP %s, height 0x%lx\n", __FILE__, __LINE__,
468                  heightIter->first.name().c_str(), (unsigned long) heightIter->second.height());
469     }
470
471     // Since we know the outgoing SP,
472     // the outgoing RA must be located just below it
473     if(!getOutRA(out_sp, out_ra, out_ra_loc, proc)) continue;
474
475     // If we have multiple potential heights (due to overlapping functions), 
476     // check if potential stack height is valid (verify that calculated RA follows a call instr)
477     if (heights.size() > 1) {
478       if(!validateRA(out_ra)) continue;
479     }
480       
481     out.setSP(out_sp);
482     out.setRALocation(out_ra_loc);
483     out.setRA(out_ra);
484     
485     if (result) {
486       sw_printf("[%s:%u] - Warning - found multiple valid frames.\n", 
487                 FILE__, __LINE__);
488     } else {
489       sw_printf("[%s:%u] - Found a valid frame\n", 
490                 FILE__, __LINE__);
491       result = true;
492     }
493   }
494   return checkResult(result);
495
496 }
497
498 bool AnalysisStepperImpl::validateRA(Address candidateRA)
499 {
500   sw_printf("[%s:%u] - Calling isPrevInstrACall\n", FILE__, __LINE__);
501   Address target;
502   if (!isPrevInstrACall(candidateRA, target)) {
503     sw_printf("[%s:%u] - Return location %lx does not follow a call instruction\n",
504               FILE__, __LINE__, candidateRA);
505     return false;
506   }
507   return true;
508 }
509
510 gcframe_ret_t AnalysisStepperImpl::checkResult(bool result)
511 {
512   if (result) {
513     sw_printf("[%s:%u] - success\n", FILE__, __LINE__); 
514     return gcf_success;
515   } else {
516     sw_printf("[%s:%u] - failed\n", FILE__, __LINE__); 
517     return gcf_not_me;
518   }
519 }
520
521 bool AnalysisStepperImpl::getOutRA(Address out_sp, Address& out_ra, location_t& out_ra_loc, ProcessState* proc)
522 {
523   // Since we know the outgoing SP,
524   // the outgoing RA must be located just below it
525   size_t addr_width = proc->getAddressWidth();
526   Address out_ra_addr = out_sp - addr_width;
527   out_ra_loc.location = loc_address;
528   out_ra_loc.val.addr = out_ra_addr;
529   
530   bool resultMem = proc->readMem(&out_ra, out_ra_addr, addr_width);
531   if (!resultMem) {
532     sw_printf("[%s:%u] - Error reading from return location %lx on stack\n",
533               FILE__, __LINE__, out_ra_addr);
534     return false;
535   }
536   return true;
537 }