• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright (c) 2010 Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 //     * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 //     * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 //     * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
30 // stackwalker_x86.cc: x86-specific stackwalker.
31 //
32 // See stackwalker_x86.h for documentation.
33 //
34 // Author: Mark Mentovai
35 
36 #include <assert.h>
37 #include <string>
38 
39 #include "common/scoped_ptr.h"
40 #include "google_breakpad/processor/call_stack.h"
41 #include "google_breakpad/processor/code_modules.h"
42 #include "google_breakpad/processor/memory_region.h"
43 #include "google_breakpad/processor/source_line_resolver_interface.h"
44 #include "google_breakpad/processor/stack_frame_cpu.h"
45 #include "processor/logging.h"
46 #include "processor/postfix_evaluator-inl.h"
47 #include "processor/stackwalker_x86.h"
48 #include "processor/windows_frame_info.h"
49 #include "processor/cfi_frame_info.h"
50 
51 namespace google_breakpad {
52 
53 // Max reasonable size for a single x86 frame is 128 KB.  This value is used in
54 // a heuristic for recovering of the EBP chain after a scan for return address.
55 // This value is based on a stack frame size histogram built for a set of
56 // popular third party libraries which suggests that 99.5% of all frames are
57 // smaller than 128 KB.
58 static const uint32_t kMaxReasonableGapBetweenFrames = 128 * 1024;
59 
60 const StackwalkerX86::CFIWalker::RegisterSet
61 StackwalkerX86::cfi_register_map_[] = {
62   // It may seem like $eip and $esp are callee-saves, because (with Unix or
63   // cdecl calling conventions) the callee is responsible for having them
64   // restored upon return. But the callee_saves flags here really means
65   // that the walker should assume they're unchanged if the CFI doesn't
66   // mention them, which is clearly wrong for $eip and $esp.
67   { "$eip", ".ra",  false,
68     StackFrameX86::CONTEXT_VALID_EIP, &MDRawContextX86::eip },
69   { "$esp", ".cfa", false,
70     StackFrameX86::CONTEXT_VALID_ESP, &MDRawContextX86::esp },
71   { "$ebp", NULL,   true,
72     StackFrameX86::CONTEXT_VALID_EBP, &MDRawContextX86::ebp },
73   { "$eax", NULL,   false,
74     StackFrameX86::CONTEXT_VALID_EAX, &MDRawContextX86::eax },
75   { "$ebx", NULL,   true,
76     StackFrameX86::CONTEXT_VALID_EBX, &MDRawContextX86::ebx },
77   { "$ecx", NULL,   false,
78     StackFrameX86::CONTEXT_VALID_ECX, &MDRawContextX86::ecx },
79   { "$edx", NULL,   false,
80     StackFrameX86::CONTEXT_VALID_EDX, &MDRawContextX86::edx },
81   { "$esi", NULL,   true,
82     StackFrameX86::CONTEXT_VALID_ESI, &MDRawContextX86::esi },
83   { "$edi", NULL,   true,
84     StackFrameX86::CONTEXT_VALID_EDI, &MDRawContextX86::edi },
85 };
86 
StackwalkerX86(const SystemInfo * system_info,const MDRawContextX86 * context,MemoryRegion * memory,const CodeModules * modules,StackFrameSymbolizer * resolver_helper)87 StackwalkerX86::StackwalkerX86(const SystemInfo* system_info,
88                                const MDRawContextX86* context,
89                                MemoryRegion* memory,
90                                const CodeModules* modules,
91                                StackFrameSymbolizer* resolver_helper)
92     : Stackwalker(system_info, memory, modules, resolver_helper),
93       context_(context),
94       cfi_walker_(cfi_register_map_,
95                   (sizeof(cfi_register_map_) / sizeof(cfi_register_map_[0]))) {
96   if (memory_ && memory_->GetBase() + memory_->GetSize() - 1 > 0xffffffff) {
97     // The x86 is a 32-bit CPU, the limits of the supplied stack are invalid.
98     // Mark memory_ = NULL, which will cause stackwalking to fail.
99     BPLOG(ERROR) << "Memory out of range for stackwalking: " <<
100                     HexString(memory_->GetBase()) << "+" <<
101                     HexString(memory_->GetSize());
102     memory_ = NULL;
103   }
104 }
105 
~StackFrameX86()106 StackFrameX86::~StackFrameX86() {
107   if (windows_frame_info)
108     delete windows_frame_info;
109   windows_frame_info = NULL;
110   if (cfi_frame_info)
111     delete cfi_frame_info;
112   cfi_frame_info = NULL;
113 }
114 
ReturnAddress() const115 uint64_t StackFrameX86::ReturnAddress() const {
116   assert(context_validity & StackFrameX86::CONTEXT_VALID_EIP);
117   return context.eip;
118 }
119 
GetContextFrame()120 StackFrame* StackwalkerX86::GetContextFrame() {
121   if (!context_) {
122     BPLOG(ERROR) << "Can't get context frame without context";
123     return NULL;
124   }
125 
126   StackFrameX86* frame = new StackFrameX86();
127 
128   // The instruction pointer is stored directly in a register, so pull it
129   // straight out of the CPU context structure.
130   frame->context = *context_;
131   frame->context_validity = StackFrameX86::CONTEXT_VALID_ALL;
132   frame->trust = StackFrame::FRAME_TRUST_CONTEXT;
133   frame->instruction = frame->context.eip;
134 
135   return frame;
136 }
137 
GetCallerByWindowsFrameInfo(const vector<StackFrame * > & frames,WindowsFrameInfo * last_frame_info,bool stack_scan_allowed)138 StackFrameX86* StackwalkerX86::GetCallerByWindowsFrameInfo(
139     const vector<StackFrame*> &frames,
140     WindowsFrameInfo* last_frame_info,
141     bool stack_scan_allowed) {
142   StackFrame::FrameTrust trust = StackFrame::FRAME_TRUST_NONE;
143 
144   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
145 
146   // Save the stack walking info we found, in case we need it later to
147   // find the callee of the frame we're constructing now.
148   last_frame->windows_frame_info = last_frame_info;
149 
150   // This function only covers the full STACK WIN case. If
151   // last_frame_info is VALID_PARAMETER_SIZE-only, then we should
152   // assume the traditional frame format or use some other strategy.
153   if (last_frame_info->valid != WindowsFrameInfo::VALID_ALL)
154     return NULL;
155 
156   // This stackwalker sets each frame's %esp to its value immediately prior
157   // to the CALL into the callee.  This means that %esp points to the last
158   // callee argument pushed onto the stack, which may not be where %esp points
159   // after the callee returns.  Specifically, the value is correct for the
160   // cdecl calling convention, but not other conventions.  The cdecl
161   // convention requires a caller to pop its callee's arguments from the
162   // stack after the callee returns.  This is usually accomplished by adding
163   // the known size of the arguments to %esp.  Other calling conventions,
164   // including stdcall, thiscall, and fastcall, require the callee to pop any
165   // parameters stored on the stack before returning.  This is usually
166   // accomplished by using the RET n instruction, which pops n bytes off
167   // the stack after popping the return address.
168   //
169   // Because each frame's %esp will point to a location on the stack after
170   // callee arguments have been PUSHed, when locating things in a stack frame
171   // relative to %esp, the size of the arguments to the callee need to be
172   // taken into account.  This seems a little bit unclean, but it's better
173   // than the alternative, which would need to take these same things into
174   // account, but only for cdecl functions.  With this implementation, we get
175   // to be agnostic about each function's calling convention.  Furthermore,
176   // this is how Windows debugging tools work, so it means that the %esp
177   // values produced by this stackwalker directly correspond to the %esp
178   // values you'll see there.
179   //
180   // If the last frame has no callee (because it's the context frame), just
181   // set the callee parameter size to 0: the stack pointer can't point to
182   // callee arguments because there's no callee.  This is correct as long
183   // as the context wasn't captured while arguments were being pushed for
184   // a function call.  Note that there may be functions whose parameter sizes
185   // are unknown, 0 is also used in that case.  When that happens, it should
186   // be possible to walk to the next frame without reference to %esp.
187 
188   uint32_t last_frame_callee_parameter_size = 0;
189   int frames_already_walked = frames.size();
190   if (frames_already_walked >= 2) {
191     const StackFrameX86* last_frame_callee
192         = static_cast<StackFrameX86*>(frames[frames_already_walked - 2]);
193     WindowsFrameInfo* last_frame_callee_info
194         = last_frame_callee->windows_frame_info;
195     if (last_frame_callee_info &&
196         (last_frame_callee_info->valid
197          & WindowsFrameInfo::VALID_PARAMETER_SIZE)) {
198       last_frame_callee_parameter_size =
199           last_frame_callee_info->parameter_size;
200     }
201   }
202 
203   // Set up the dictionary for the PostfixEvaluator.  %ebp and %esp are used
204   // in each program string, and their previous values are known, so set them
205   // here.
206   PostfixEvaluator<uint32_t>::DictionaryType dictionary;
207   // Provide the current register values.
208   dictionary["$ebp"] = last_frame->context.ebp;
209   dictionary["$esp"] = last_frame->context.esp;
210   // Provide constants from the debug info for last_frame and its callee.
211   // .cbCalleeParams is a Breakpad extension that allows us to use the
212   // PostfixEvaluator engine when certain types of debugging information
213   // are present without having to write the constants into the program
214   // string as literals.
215   dictionary[".cbCalleeParams"] = last_frame_callee_parameter_size;
216   dictionary[".cbSavedRegs"] = last_frame_info->saved_register_size;
217   dictionary[".cbLocals"] = last_frame_info->local_size;
218 
219   uint32_t raSearchStart = last_frame->context.esp +
220                            last_frame_callee_parameter_size +
221                            last_frame_info->local_size +
222                            last_frame_info->saved_register_size;
223 
224   uint32_t raSearchStartOld = raSearchStart;
225   uint32_t found = 0;  // dummy value
226   // Scan up to three words above the calculated search value, in case
227   // the stack was aligned to a quadword boundary.
228   //
229   // TODO(ivan.penkov): Consider cleaning up the scan for return address that
230   // follows.  The purpose of this scan is to adjust the .raSearchStart
231   // calculation (which is based on register %esp) in the cases where register
232   // %esp may have been aligned (up to a quadword).  There are two problems
233   // with this approach:
234   //  1) In practice, 64 byte boundary alignment is seen which clearly can not
235   //     be handled by a three word scan.
236   //  2) A search for a return address is "guesswork" by definition because
237   //     the results will be different depending on what is left on the stack
238   //     from previous executions.
239   // So, basically, the results from this scan should be ignored if other means
240   // for calculation of the value of .raSearchStart are available.
241   if (ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3) &&
242       last_frame->trust == StackFrame::FRAME_TRUST_CONTEXT &&
243       last_frame->windows_frame_info != NULL &&
244       last_frame_info->type_ == WindowsFrameInfo::STACK_INFO_FPO &&
245       raSearchStartOld == raSearchStart &&
246       found == last_frame->context.eip) {
247     // The context frame represents an FPO-optimized Windows system call.
248     // On the top of the stack we have a pointer to the current instruction.
249     // This means that the callee has returned but the return address is still
250     // on the top of the stack which is very atypical situaltion.
251     // Skip one slot from the stack and do another scan in order to get the
252     // actual return address.
253     raSearchStart += 4;
254     ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3);
255   }
256 
257   dictionary[".cbParams"] = last_frame_info->parameter_size;
258 
259   // Decide what type of program string to use. The program string is in
260   // postfix notation and will be passed to PostfixEvaluator::Evaluate.
261   // Given the dictionary and the program string, it is possible to compute
262   // the return address and the values of other registers in the calling
263   // function. Because of bugs described below, the stack may need to be
264   // scanned for these values. The results of program string evaluation
265   // will be used to determine whether to scan for better values.
266   string program_string;
267   bool recover_ebp = true;
268 
269   trust = StackFrame::FRAME_TRUST_CFI;
270   if (!last_frame_info->program_string.empty()) {
271     // The FPO data has its own program string, which will tell us how to
272     // get to the caller frame, and may even fill in the values of
273     // nonvolatile registers and provide pointers to local variables and
274     // parameters.  In some cases, particularly with program strings that use
275     // .raSearchStart, the stack may need to be scanned afterward.
276     program_string = last_frame_info->program_string;
277   } else if (last_frame_info->allocates_base_pointer) {
278     // The function corresponding to the last frame doesn't use the frame
279     // pointer for conventional purposes, but it does allocate a new
280     // frame pointer and use it for its own purposes.  Its callee's
281     // information is still accessed relative to %esp, and the previous
282     // value of %ebp can be recovered from a location in its stack frame,
283     // within the saved-register area.
284     //
285     // Functions that fall into this category use the %ebp register for
286     // a purpose other than the frame pointer.  They restore the caller's
287     // %ebp before returning.  These functions create their stack frame
288     // after a CALL by decrementing the stack pointer in an amount
289     // sufficient to store local variables, and then PUSHing saved
290     // registers onto the stack.  Arguments to a callee function, if any,
291     // are PUSHed after that.  Walking up to the caller, therefore,
292     // can be done solely with calculations relative to the stack pointer
293     // (%esp).  The return address is recovered from the memory location
294     // above the known sizes of the callee's parameters, saved registers,
295     // and locals.  The caller's stack pointer (the value of %esp when
296     // the caller executed CALL) is the location immediately above the
297     // saved return address.  The saved value of %ebp to be restored for
298     // the caller is at a known location in the saved-register area of
299     // the stack frame.
300     //
301     // For this type of frame, MSVC 14 (from Visual Studio 8/2005) in
302     // link-time code generation mode (/LTCG and /GL) can generate erroneous
303     // debugging data.  The reported size of saved registers can be 0,
304     // which is clearly an error because these frames must, at the very
305     // least, save %ebp.  For this reason, in addition to those given above
306     // about the use of .raSearchStart, the stack may need to be scanned
307     // for a better return address and a better frame pointer after the
308     // program string is evaluated.
309     //
310     // %eip_new = *(%esp_old + callee_params + saved_regs + locals)
311     // %ebp_new = *(%esp_old + callee_params + saved_regs - 8)
312     // %esp_new = %esp_old + callee_params + saved_regs + locals + 4
313     program_string = "$eip .raSearchStart ^ = "
314         "$ebp $esp .cbCalleeParams + .cbSavedRegs + 8 - ^ = "
315         "$esp .raSearchStart 4 + =";
316   } else {
317     // The function corresponding to the last frame doesn't use %ebp at
318     // all.  The callee frame is located relative to %esp.
319     //
320     // The called procedure's instruction pointer and stack pointer are
321     // recovered in the same way as the case above, except that no
322     // frame pointer (%ebp) is used at all, so it is not saved anywhere
323     // in the callee's stack frame and does not need to be recovered.
324     // Because %ebp wasn't used in the callee, whatever value it has
325     // is the value that it had in the caller, so it can be carried
326     // straight through without bringing its validity into question.
327     //
328     // Because of the use of .raSearchStart, the stack will possibly be
329     // examined to locate a better return address after program string
330     // evaluation.  The stack will not be examined to locate a saved
331     // %ebp value, because these frames do not save (or use) %ebp.
332     //
333     // %eip_new = *(%esp_old + callee_params + saved_regs + locals)
334     // %esp_new = %esp_old + callee_params + saved_regs + locals + 4
335     // %ebp_new = %ebp_old
336     program_string = "$eip .raSearchStart ^ = "
337         "$esp .raSearchStart 4 + =";
338     recover_ebp = false;
339   }
340 
341   // Check for alignment operators in the program string.  If alignment
342   // operators are found, then current %ebp must be valid and it is the only
343   // reliable data point that can be used for getting to the previous frame.
344   // E.g. the .raSearchStart calculation (above) is based on %esp and since
345   // %esp was aligned in the current frame (which is a lossy operation) the
346   // calculated value of .raSearchStart cannot be correct and should not be
347   // used.  Instead .raSearchStart must be calculated based on %ebp.
348   // The code that follows assumes that .raSearchStart is supposed to point
349   // at the saved return address (ebp + 4).
350   // For some more details on this topic, take a look at the following thread:
351   // https://groups.google.com/forum/#!topic/google-breakpad-dev/ZP1FA9B1JjM
352   if ((StackFrameX86::CONTEXT_VALID_EBP & last_frame->context_validity) != 0 &&
353       program_string.find('@') != string::npos) {
354     raSearchStart = last_frame->context.ebp + 4;
355   }
356 
357   // The difference between raSearch and raSearchStart is unknown,
358   // but making them the same seems to work well in practice.
359   dictionary[".raSearchStart"] = raSearchStart;
360   dictionary[".raSearch"] = raSearchStart;
361 
362   // Now crank it out, making sure that the program string set at least the
363   // two required variables.
364   PostfixEvaluator<uint32_t> evaluator =
365       PostfixEvaluator<uint32_t>(&dictionary, memory_);
366   PostfixEvaluator<uint32_t>::DictionaryValidityType dictionary_validity;
367   if (!evaluator.Evaluate(program_string, &dictionary_validity) ||
368       dictionary_validity.find("$eip") == dictionary_validity.end() ||
369       dictionary_validity.find("$esp") == dictionary_validity.end()) {
370     // Program string evaluation failed. It may be that %eip is not somewhere
371     // with stack frame info, and %ebp is pointing to non-stack memory, so
372     // our evaluation couldn't succeed. We'll scan the stack for a return
373     // address. This can happen if the stack is in a module for which
374     // we don't have symbols, and that module is compiled without a
375     // frame pointer.
376     uint32_t location_start = last_frame->context.esp;
377     uint32_t location, eip;
378     if (!stack_scan_allowed
379         || !ScanForReturnAddress(location_start, &location, &eip,
380                                  frames.size() == 1 /* is_context_frame */)) {
381       // if we can't find an instruction pointer even with stack scanning,
382       // give up.
383       return NULL;
384     }
385 
386     // This seems like a reasonable return address. Since program string
387     // evaluation failed, use it and set %esp to the location above the
388     // one where the return address was found.
389     dictionary["$eip"] = eip;
390     dictionary["$esp"] = location + 4;
391     trust = StackFrame::FRAME_TRUST_SCAN;
392   }
393 
394   // Since this stack frame did not use %ebp in a traditional way,
395   // locating the return address isn't entirely deterministic. In that
396   // case, the stack can be scanned to locate the return address.
397   //
398   // However, if program string evaluation resulted in both %eip and
399   // %ebp values of 0, trust that the end of the stack has been
400   // reached and don't scan for anything else.
401   if (dictionary["$eip"] != 0 || dictionary["$ebp"] != 0) {
402     int offset = 0;
403 
404     // This scan can only be done if a CodeModules object is available, to
405     // check that candidate return addresses are in fact inside a module.
406     //
407     // TODO(mmentovai): This ignores dynamically-generated code.  One possible
408     // solution is to check the minidump's memory map to see if the candidate
409     // %eip value comes from a mapped executable page, although this would
410     // require dumps that contain MINIDUMP_MEMORY_INFO, which the Breakpad
411     // client doesn't currently write (it would need to call MiniDumpWriteDump
412     // with the MiniDumpWithFullMemoryInfo type bit set).  Even given this
413     // ability, older OSes (pre-XP SP2) and CPUs (pre-P4) don't enforce
414     // an independent execute privilege on memory pages.
415 
416     uint32_t eip = dictionary["$eip"];
417     if (modules_ && !modules_->GetModuleForAddress(eip)) {
418       // The instruction pointer at .raSearchStart was invalid, so start
419       // looking one 32-bit word above that location.
420       uint32_t location_start = dictionary[".raSearchStart"] + 4;
421       uint32_t location;
422       if (stack_scan_allowed
423           && ScanForReturnAddress(location_start, &location, &eip,
424                                   frames.size() == 1 /* is_context_frame */)) {
425         // This is a better return address that what program string
426         // evaluation found.  Use it, and set %esp to the location above the
427         // one where the return address was found.
428         dictionary["$eip"] = eip;
429         dictionary["$esp"] = location + 4;
430         offset = location - location_start;
431         trust = StackFrame::FRAME_TRUST_CFI_SCAN;
432       }
433     }
434 
435     if (recover_ebp) {
436       // When trying to recover the previous value of the frame pointer (%ebp),
437       // start looking at the lowest possible address in the saved-register
438       // area, and look at the entire saved register area, increased by the
439       // size of |offset| to account for additional data that may be on the
440       // stack.  The scan is performed from the highest possible address to
441       // the lowest, because the expectation is that the function's prolog
442       // would have saved %ebp early.
443       uint32_t ebp = dictionary["$ebp"];
444 
445       // When a scan for return address is used, it is possible to skip one or
446       // more frames (when return address is not in a known module).  One
447       // indication for skipped frames is when the value of %ebp is lower than
448       // the location of the return address on the stack
449       bool has_skipped_frames =
450         (trust != StackFrame::FRAME_TRUST_CFI && ebp <= raSearchStart + offset);
451 
452       uint32_t value;  // throwaway variable to check pointer validity
453       if (has_skipped_frames || !memory_->GetMemoryAtAddress(ebp, &value)) {
454         int fp_search_bytes = last_frame_info->saved_register_size + offset;
455         uint32_t location_end = last_frame->context.esp +
456                                  last_frame_callee_parameter_size;
457 
458         for (uint32_t location = location_end + fp_search_bytes;
459              location >= location_end;
460              location -= 4) {
461           if (!memory_->GetMemoryAtAddress(location, &ebp))
462             break;
463 
464           if (memory_->GetMemoryAtAddress(ebp, &value)) {
465             // The candidate value is a pointer to the same memory region
466             // (the stack).  Prefer it as a recovered %ebp result.
467             dictionary["$ebp"] = ebp;
468             break;
469           }
470         }
471       }
472     }
473   }
474 
475   // Create a new stack frame (ownership will be transferred to the caller)
476   // and fill it in.
477   StackFrameX86* frame = new StackFrameX86();
478 
479   frame->trust = trust;
480   frame->context = last_frame->context;
481   frame->context.eip = dictionary["$eip"];
482   frame->context.esp = dictionary["$esp"];
483   frame->context.ebp = dictionary["$ebp"];
484   frame->context_validity = StackFrameX86::CONTEXT_VALID_EIP |
485                                 StackFrameX86::CONTEXT_VALID_ESP |
486                                 StackFrameX86::CONTEXT_VALID_EBP;
487 
488   // These are nonvolatile (callee-save) registers, and the program string
489   // may have filled them in.
490   if (dictionary_validity.find("$ebx") != dictionary_validity.end()) {
491     frame->context.ebx = dictionary["$ebx"];
492     frame->context_validity |= StackFrameX86::CONTEXT_VALID_EBX;
493   }
494   if (dictionary_validity.find("$esi") != dictionary_validity.end()) {
495     frame->context.esi = dictionary["$esi"];
496     frame->context_validity |= StackFrameX86::CONTEXT_VALID_ESI;
497   }
498   if (dictionary_validity.find("$edi") != dictionary_validity.end()) {
499     frame->context.edi = dictionary["$edi"];
500     frame->context_validity |= StackFrameX86::CONTEXT_VALID_EDI;
501   }
502 
503   return frame;
504 }
505 
GetCallerByCFIFrameInfo(const vector<StackFrame * > & frames,CFIFrameInfo * cfi_frame_info)506 StackFrameX86* StackwalkerX86::GetCallerByCFIFrameInfo(
507     const vector<StackFrame*> &frames,
508     CFIFrameInfo* cfi_frame_info) {
509   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
510   last_frame->cfi_frame_info = cfi_frame_info;
511 
512   scoped_ptr<StackFrameX86> frame(new StackFrameX86());
513   if (!cfi_walker_
514       .FindCallerRegisters(*memory_, *cfi_frame_info,
515                            last_frame->context, last_frame->context_validity,
516                            &frame->context, &frame->context_validity))
517     return NULL;
518 
519   // Make sure we recovered all the essentials.
520   static const int essentials = (StackFrameX86::CONTEXT_VALID_EIP
521                                  | StackFrameX86::CONTEXT_VALID_ESP
522                                  | StackFrameX86::CONTEXT_VALID_EBP);
523   if ((frame->context_validity & essentials) != essentials)
524     return NULL;
525 
526   frame->trust = StackFrame::FRAME_TRUST_CFI;
527 
528   return frame.release();
529 }
530 
GetCallerByEBPAtBase(const vector<StackFrame * > & frames,bool stack_scan_allowed)531 StackFrameX86* StackwalkerX86::GetCallerByEBPAtBase(
532     const vector<StackFrame*> &frames,
533     bool stack_scan_allowed) {
534   StackFrame::FrameTrust trust;
535   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
536   uint32_t last_esp = last_frame->context.esp;
537   uint32_t last_ebp = last_frame->context.ebp;
538 
539   // Assume that the standard %ebp-using x86 calling convention is in
540   // use.
541   //
542   // The typical x86 calling convention, when frame pointers are present,
543   // is for the calling procedure to use CALL, which pushes the return
544   // address onto the stack and sets the instruction pointer (%eip) to
545   // the entry point of the called routine.  The called routine then
546   // PUSHes the calling routine's frame pointer (%ebp) onto the stack
547   // before copying the stack pointer (%esp) to the frame pointer (%ebp).
548   // Therefore, the calling procedure's frame pointer is always available
549   // by dereferencing the called procedure's frame pointer, and the return
550   // address is always available at the memory location immediately above
551   // the address pointed to by the called procedure's frame pointer.  The
552   // calling procedure's stack pointer (%esp) is 8 higher than the value
553   // of the called procedure's frame pointer at the time the calling
554   // procedure made the CALL: 4 bytes for the return address pushed by the
555   // CALL itself, and 4 bytes for the callee's PUSH of the caller's frame
556   // pointer.
557   //
558   // %eip_new = *(%ebp_old + 4)
559   // %esp_new = %ebp_old + 8
560   // %ebp_new = *(%ebp_old)
561 
562   uint32_t caller_eip, caller_esp, caller_ebp;
563 
564   if (memory_->GetMemoryAtAddress(last_ebp + 4, &caller_eip) &&
565       memory_->GetMemoryAtAddress(last_ebp, &caller_ebp)) {
566     caller_esp = last_ebp + 8;
567     trust = StackFrame::FRAME_TRUST_FP;
568   } else {
569     // We couldn't read the memory %ebp refers to. It may be that %ebp
570     // is pointing to non-stack memory. We'll scan the stack for a
571     // return address. This can happen if last_frame is executing code
572     // for a module for which we don't have symbols, and that module
573     // is compiled without a frame pointer.
574     if (!stack_scan_allowed
575         || !ScanForReturnAddress(last_esp, &caller_esp, &caller_eip,
576                                  frames.size() == 1 /* is_context_frame */)) {
577       // if we can't find an instruction pointer even with stack scanning,
578       // give up.
579       return NULL;
580     }
581 
582     // ScanForReturnAddress found a reasonable return address. Advance %esp to
583     // the location immediately above the one where the return address was
584     // found.
585     caller_esp += 4;
586     // Try to restore the %ebp chain.  The caller %ebp should be stored at a
587     // location immediately below the one where the return address was found.
588     // A valid caller %ebp must be greater than the address where it is stored
589     // and the gap between the two adjacent frames should be reasonable.
590     uint32_t restored_ebp_chain = caller_esp - 8;
591     if (!memory_->GetMemoryAtAddress(restored_ebp_chain, &caller_ebp) ||
592         caller_ebp <= restored_ebp_chain ||
593         caller_ebp - restored_ebp_chain > kMaxReasonableGapBetweenFrames) {
594       // The restored %ebp chain doesn't appear to be valid.
595       // Assume that %ebp is unchanged.
596       caller_ebp = last_ebp;
597     }
598 
599     trust = StackFrame::FRAME_TRUST_SCAN;
600   }
601 
602   // Create a new stack frame (ownership will be transferred to the caller)
603   // and fill it in.
604   StackFrameX86* frame = new StackFrameX86();
605 
606   frame->trust = trust;
607   frame->context = last_frame->context;
608   frame->context.eip = caller_eip;
609   frame->context.esp = caller_esp;
610   frame->context.ebp = caller_ebp;
611   frame->context_validity = StackFrameX86::CONTEXT_VALID_EIP |
612                             StackFrameX86::CONTEXT_VALID_ESP |
613                             StackFrameX86::CONTEXT_VALID_EBP;
614 
615   return frame;
616 }
617 
GetCallerFrame(const CallStack * stack,bool stack_scan_allowed)618 StackFrame* StackwalkerX86::GetCallerFrame(const CallStack* stack,
619                                            bool stack_scan_allowed) {
620   if (!memory_ || !stack) {
621     BPLOG(ERROR) << "Can't get caller frame without memory or stack";
622     return NULL;
623   }
624 
625   const vector<StackFrame*> &frames = *stack->frames();
626   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
627   scoped_ptr<StackFrameX86> new_frame;
628 
629   // If the resolver has Windows stack walking information, use that.
630   WindowsFrameInfo* windows_frame_info
631       = frame_symbolizer_->FindWindowsFrameInfo(last_frame);
632   if (windows_frame_info)
633     new_frame.reset(GetCallerByWindowsFrameInfo(frames, windows_frame_info,
634                                                 stack_scan_allowed));
635 
636   // If the resolver has DWARF CFI information, use that.
637   if (!new_frame.get()) {
638     CFIFrameInfo* cfi_frame_info =
639         frame_symbolizer_->FindCFIFrameInfo(last_frame);
640     if (cfi_frame_info)
641       new_frame.reset(GetCallerByCFIFrameInfo(frames, cfi_frame_info));
642   }
643 
644   // Otherwise, hope that the program was using a traditional frame structure.
645   if (!new_frame.get())
646     new_frame.reset(GetCallerByEBPAtBase(frames, stack_scan_allowed));
647 
648   // If nothing worked, tell the caller.
649   if (!new_frame.get())
650     return NULL;
651 
652   // Treat an instruction address of 0 as end-of-stack.
653   if (new_frame->context.eip == 0)
654     return NULL;
655 
656   // If the new stack pointer is at a lower address than the old, then
657   // that's clearly incorrect. Treat this as end-of-stack to enforce
658   // progress and avoid infinite loops.
659   if (new_frame->context.esp <= last_frame->context.esp)
660     return NULL;
661 
662   // new_frame->context.eip is the return address, which is the instruction
663   // after the CALL that caused us to arrive at the callee. Set
664   // new_frame->instruction to one less than that, so it points within the
665   // CALL instruction. See StackFrame::instruction for details, and
666   // StackFrameAMD64::ReturnAddress.
667   new_frame->instruction = new_frame->context.eip - 1;
668 
669   return new_frame.release();
670 }
671 
672 }  // namespace google_breakpad
673