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