Update copyright to LGPL on all files
[dyninst.git] / stackwalk / src / x86-wanderer.C
1 /*
2  * Copyright (c) 1996-2009 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/walker.h"
33 #include "stackwalk/h/frame.h"
34 #include "stackwalk/h/swk_errors.h"
35 #include "stackwalk/h/procstate.h"
36 #include "stackwalk/src/x86-swk.h"
37 #include "stackwalk/src/symtab-swk.h"
38
39 #include "common/h/Types.h"
40
41 #include "symtabAPI/h/Function.h"
42
43 using namespace Dyninst;
44 using namespace Stackwalker;
45
46
47 StepperWandererImpl::StepperWandererImpl(Walker *walker_,
48                                          StepperWanderer *parent_,
49                                          WandererHelper *whelper_,
50                                          FrameFuncHelper *fhelper_) :
51   FrameStepper(walker_),
52   whelper(whelper_),
53   fhelper(fhelper_),
54   parent(parent_)
55 {
56 }
57
58 StepperWandererImpl::~StepperWandererImpl()
59 {
60 }
61
62 unsigned StepperWandererImpl::getPriority() const
63 {
64    return 0x10030;
65 }
66
67 void StepperWandererImpl::registerStepperGroup(StepperGroup *group) {
68   FrameStepper::registerStepperGroup(group);
69 }
70
71 gcframe_ret_t StepperWandererImpl::getCallerFrame(const Frame &in, Frame &out)
72 {
73    sw_printf("[%s:%u] - Wanderer attempting to walk from 0x%lx\n",
74              __FILE__, __LINE__, in.getRA());
75
76    const unsigned addr_width = getProcessState()->getAddressWidth();
77    std::vector<std::pair<Address, Address> > candidate;
78
79    Address current_stack = in.getSP();
80    unsigned num_words_tried = 0;
81    Address word;
82    bool result;
83    bool found_exact_match = false;
84    Address found_base = 0x0;
85    Address found_ra = 0x0;
86
87    do {
88       result = getWord(word, current_stack);
89       if (!result) {
90          sw_printf("[%s:%u] - getWord returned false\n", __FILE__, __LINE__);
91          return gcf_not_me;
92       }
93       
94       Address target;
95       if (whelper->isPrevInstrACall(word, target))
96       {
97          if (whelper->isPCInFunc(target, in.getRA()))
98          {
99             sw_printf("[%s:%u] - Wanderer thinks word 0x%lx at 0x%lx  is return "
100                       " address\n", __FILE__, __LINE__, word, current_stack);
101             found_base = current_stack;
102             found_ra = word;
103             found_exact_match = true;
104             break;
105          }
106          else
107          {
108             //candidate.push_back(std::pair<Address, Address>(word, current_stack));
109          }
110       }
111       current_stack += addr_width;
112       num_words_tried++;
113    } while (num_words_tried < MAX_WANDERER_DEPTH);
114
115    if (!found_exact_match && !candidate.size()) {
116       sw_printf("[%s:%u] - Wanderer couldn't find anything in %u words\n",
117                 __FILE__, __LINE__, MAX_WANDERER_DEPTH);
118       return gcf_not_me;
119    }
120
121    if (!found_exact_match && candidate.size()) {
122       /**
123        * If we ever want to rely on candidates, then uncomment the above
124        * push_back and the below code.  This trades false negatives for
125        * potential false positives, but I'm not sure it's worth it.
126        **/
127       return gcf_not_me;
128       //found_ra = candidate[0].first;
129       //found_base = candidate[0].second;
130    }
131
132    out.setRA(found_ra);
133    out.setSP(found_base);
134    
135    if (fhelper->allocatesFrame(in.getRA()).first == FrameFuncHelper::savefp_only_frame) {
136       Address new_fp;
137       result = getProcessState()->readMem(&new_fp, out.getSP(), 
138                                           getProcessState()->getAddressWidth());
139       if (!result) {
140          sw_printf("[%s:%u] - Error, couln't read from stack at %lx\n",
141                    __FILE__, __LINE__, out.getSP());
142          return gcf_error;
143       }
144       out.setFP(new_fp);
145    }
146    else {
147       out.setFP(in.getFP());
148    }
149
150    return gcf_success;
151    
152 }
153
154 bool StepperWandererImpl::getWord(Address &word_out, Address start)
155 {
156    const unsigned addr_width = getProcessState()->getAddressWidth();
157    if (start < 1024) {
158       sw_printf("[%s:%u] - %lx too low to be valid memory\n",
159                 __FILE__, __LINE__, start);
160       return false;
161    }
162    word_out = 0x0;
163    bool result = getProcessState()->readMem(&word_out, start, addr_width);
164    if (!result) {
165       sw_printf("[%s:%u] - Wanderer couldn't read from stack at 0x%lx\n",
166                 __FILE__, __LINE__, start);
167       return false;
168    }
169
170    return true;
171 }
172
173 bool WandererHelper::isPrevInstrACall(Address addr, Address &target)
174 {
175    const unsigned max_call_length = 5;
176    bool result;
177    unsigned char buffer[max_call_length];
178
179    sw_printf("[%s:%u] - isPrevInstrACall on %lx\n", __FILE__, __LINE__, addr);
180    Address start = addr - max_call_length;
181    result = proc->readMem(buffer, start, max_call_length);
182    if (!result)
183    {
184       sw_printf("[%s:%u] - Address 0x%lx is not a call--unreadable\n",
185                 __FILE__, __LINE__, addr);
186       return false;
187    }
188
189    if (buffer[max_call_length - 5] == 0xe8) {
190       int32_t disp = *((int32_t *) (buffer+1));
191       target = addr + disp;
192       sw_printf("[%s:%u] - Found call encoded by %x to %lx (addr = %lx, disp = %lx)\n",
193                 __FILE__, __LINE__, (int) buffer[0], target, addr, disp);
194                 
195       return true;
196    }
197
198    target = 0x0;
199    for (unsigned i=0; i<max_call_length-1; i++)
200    {
201       if (buffer[i] != 0xff) 
202          continue;
203       int modrm_reg = buffer[i+1] >> 3 & 7;
204       if (modrm_reg != 2)
205          continue;
206
207       /**
208        * Compute the size of the x86 instruction.
209        **/
210       int modrm_mod = buffer[i+1] >> 6;
211       int modrm_rm = buffer[i+1] & 7;
212       unsigned size = 2; //Opcode + MOD/RM
213       switch (modrm_mod)
214       {
215          case 0:
216             if (modrm_rm == 5)
217                size += 4; //disp32
218             if (modrm_rm == 4)
219                size += 1; //SIB
220             break;
221          case 1:
222             size += 1; //disp8
223             if (modrm_rm == 4)
224                size += 1; //SIB
225             break;
226          case 2:
227             size += 4; //disp32
228             if (modrm_rm == 4)
229                size += 1; //SIB
230             break;
231          case 3:
232             break;
233       }
234
235       if (i + size == max_call_length)
236       {
237          sw_printf("[%s:%u] - Found call of size %d encoded by: ",
238                    __FILE__, __LINE__, size);
239          for (unsigned j=i; j<i+size; j++) {
240             sw_printf("%x ", buffer[j]);
241          }
242          sw_printf("\n");
243
244          return true;
245       }
246    }
247
248    return false;
249 }
250
251 bool WandererHelper::isPCInFunc(Address func_entry, Address pc)
252 {
253    if (!func_entry || !pc)
254       return false;
255    if (func_entry == pc)
256       return true;
257 #if defined(cap_stackwalker_use_symtab)
258    Symtab *symtab = NULL;
259    LibAddrPair func_lib, pc_lib;
260    LibraryState *tracker = proc->getLibraryTracker();
261    std::vector<Symbol *> funcs;
262    Region *func_region;
263    Offset pc_offset, func_entry_offset;
264    bool result;
265    SymtabAPI::Function *func_symbol = NULL;
266    SymtabAPI::Function *pc_symbol = NULL;
267
268
269    result = tracker->getLibraryAtAddr(func_entry, func_lib);
270    if (!result) {
271       sw_printf("[%s:%u] - Failed to find library at %lx\n",
272                 __FILE__, __LINE__, func_entry);
273       return false;
274    }
275    func_entry_offset = func_entry - func_lib.second;
276
277    symtab = SymtabWrapper::getSymtab(func_lib.first);
278    if (!symtab) {
279       sw_printf("[%s:%u] - Failed to open symtab for %s\n", 
280                 __FILE__, __LINE__, func_lib.first.c_str());
281       goto symtab_fail;
282    }
283
284    func_region = symtab->findEnclosingRegion(func_entry_offset);
285    if (func_region->getRegionName() == std::string(".plt")) {
286       sw_printf("[%s:%u] - %lx is a PLT entry, trying to map to real target\n",
287                 __FILE__, __LINE__, func_entry);
288       int got_offset = -1;
289       Address got_abs = 0x0;
290       if (proc->getAddressWidth() == 4) {
291          //32-bit mode.  Recognize common PLT idioms
292          #define MAX_PLT32_IDIOM_SIZE 6
293          unsigned char buffer[MAX_PLT32_IDIOM_SIZE];
294          result = proc->readMem(buffer, func_entry, MAX_PLT32_IDIOM_SIZE);
295          if (buffer[0] == 0xff && buffer[1] == 0xa3) {
296             //Indirect jump off of ebx
297             got_offset = *((int32_t*) (buffer+2));
298          }
299          else if (buffer[0] == 0xff && buffer[1] == 0x25) {
300             //Indirect jump through absolute
301             got_abs = *((uint32_t*) (buffer+2));
302          }
303          else {
304             sw_printf("[%s:%u] - Unrecognized PLT idiom at %lx: ",
305                       __FILE__, __LINE__, func_entry);
306             for (unsigned i=0; i<MAX_PLT32_IDIOM_SIZE; i++) {
307                sw_printf("%x ", buffer[i]);
308             }
309             sw_printf("\n");
310          }
311       }
312       if (proc->getAddressWidth() == 8) {
313          //32-bit mode.  Recognize common PLT idioms
314          #define MAX_PLT64_IDIOM_SIZE 6
315          unsigned char buffer[MAX_PLT64_IDIOM_SIZE];
316          result = proc->readMem(buffer, func_entry, MAX_PLT64_IDIOM_SIZE);
317          if (buffer[0] == 0xff && buffer[1] == 0x25) {
318             //PC Relative jump indirect
319             got_abs = *((int32_t *) (buffer+2)) + func_entry + 6;
320          }
321          else {
322             sw_printf("[%s:%u] - Unrecognized PLT idiom at %lx: ",
323                       __FILE__, __LINE__, func_entry);
324             for (unsigned i=0; i<MAX_PLT32_IDIOM_SIZE; i++) {
325                sw_printf("%x ", buffer[i]);
326             }
327             sw_printf("\n");
328          }
329       }
330       
331       if (got_offset != -1) {
332          sw_printf("[%s:%u] - Computed PLT to be going through GOT offset %d\n",
333                    __FILE__, __LINE__, got_offset);
334          Region *got_region = NULL;
335          result = symtab->findRegion(got_region, ".got");
336          got_abs = got_offset + got_region->getMemOffset() + func_lib.second;
337       }
338
339       if (got_abs) {
340          Address real_target;
341          result = proc->readMem(&real_target, got_abs, proc->getAddressWidth());
342          sw_printf("[%s:%u] - Computed PLT to be going through GOT abs %lx to "
343                    "real target %lx\n", __FILE__, __LINE__, got_abs, real_target);
344          return isPCInFunc(real_target, pc);
345       }
346
347    }
348
349    result = tracker->getLibraryAtAddr(pc, pc_lib);
350    if (!result) {
351       sw_printf("[%s:%u] - Failed to find library at %lx\n",
352                 __FILE__, __LINE__, pc);
353       return false;
354    }
355    pc_offset = pc - pc_lib.second;
356
357
358    if (func_entry > pc) {
359       sw_printf("[%s:%u] - func_entry %lx is greater than pc %lx\n",
360                 __FILE__, __LINE__, func_entry, pc);
361       return false;
362    }
363    
364    if (pc_lib != func_lib)
365    {
366       sw_printf("[%s:%u] - %lx and %lx are from different libraries\n",
367                 __FILE__, __LINE__, func_entry, pc);
368       return false;
369    }
370
371    result = symtab->getContainingFunction(func_entry_offset, func_symbol);
372    if (!result || !func_symbol) {
373       sw_printf("[%s:%u] - No functions begin at %lx\n", 
374                 __FILE__, __LINE__, func_entry_offset);
375       goto symtab_fail;
376    }
377
378    result = symtab->getContainingFunction(pc_offset, pc_symbol);
379    if (!result || !pc_symbol) {
380       sw_printf("[%s:%u] - No functions begin at %lx\n", 
381                 __FILE__, __LINE__, func_entry_offset);
382       goto symtab_fail;
383    }
384
385    sw_printf("[%s:%u] - Decided func at offset %lx and pc-func at offset %lx\n",
386              __FILE__, __LINE__, func_symbol->getOffset(), pc_symbol->getOffset());
387    return (func_symbol->getOffset() == pc_symbol->getOffset());
388  symtab_fail:   
389 #endif
390    //We don't have much to work with.  This is all heuristics anyway, so assume
391    // that if pc is within 8k of func_entry that it's a part of the function.
392    return (pc >= func_entry && pc < func_entry + 8192);
393 }
394
395 WandererHelper::WandererHelper(ProcessState *proc_) :
396    proc(proc_)
397 {
398 }
399
400 WandererHelper::~WandererHelper()
401 {
402 }