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