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
51namespace 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.
58static const uint32_t kMaxReasonableGapBetweenFrames = 128 * 1024;
59
60const StackwalkerX86::CFIWalker::RegisterSet
61StackwalkerX86::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
87StackwalkerX86::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
106StackFrameX86::~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
115uint64_t StackFrameX86::ReturnAddress() const {
116 assert(context_validity & StackFrameX86::CONTEXT_VALID_EIP);
117 return context.eip;
118}
119
120StackFrame* 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
138StackFrameX86* 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 // The last frame can never be inline. A sequence of inline frames always
145 // finishes with a conventional frame.
146 assert(frames.back()->trust != StackFrame::FRAME_TRUST_INLINE);
147 StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
148
149 // Save the stack walking info we found, in case we need it later to
150 // find the callee of the frame we're constructing now.
151 last_frame->windows_frame_info = last_frame_info;
152
153 // This function only covers the full STACK WIN case. If
154 // last_frame_info is VALID_PARAMETER_SIZE-only, then we should
155 // assume the traditional frame format or use some other strategy.
156 if (last_frame_info->valid != WindowsFrameInfo::VALID_ALL)
157 return NULL;
158
159 // This stackwalker sets each frame's %esp to its value immediately prior
160 // to the CALL into the callee. This means that %esp points to the last
161 // callee argument pushed onto the stack, which may not be where %esp points
162 // after the callee returns. Specifically, the value is correct for the
163 // cdecl calling convention, but not other conventions. The cdecl
164 // convention requires a caller to pop its callee's arguments from the
165 // stack after the callee returns. This is usually accomplished by adding
166 // the known size of the arguments to %esp. Other calling conventions,
167 // including stdcall, thiscall, and fastcall, require the callee to pop any
168 // parameters stored on the stack before returning. This is usually
169 // accomplished by using the RET n instruction, which pops n bytes off
170 // the stack after popping the return address.
171 //
172 // Because each frame's %esp will point to a location on the stack after
173 // callee arguments have been PUSHed, when locating things in a stack frame
174 // relative to %esp, the size of the arguments to the callee need to be
175 // taken into account. This seems a little bit unclean, but it's better
176 // than the alternative, which would need to take these same things into
177 // account, but only for cdecl functions. With this implementation, we get
178 // to be agnostic about each function's calling convention. Furthermore,
179 // this is how Windows debugging tools work, so it means that the %esp
180 // values produced by this stackwalker directly correspond to the %esp
181 // values you'll see there.
182 //
183 // If the last frame has no callee (because it's the context frame), just
184 // set the callee parameter size to 0: the stack pointer can't point to
185 // callee arguments because there's no callee. This is correct as long
186 // as the context wasn't captured while arguments were being pushed for
187 // a function call. Note that there may be functions whose parameter sizes
188 // are unknown, 0 is also used in that case. When that happens, it should
189 // be possible to walk to the next frame without reference to %esp.
190
191 uint32_t last_frame_callee_parameter_size = 0;
192 int frames_already_walked = frames.size();
193 for (int last_frame_callee_id = frames_already_walked - 2;
194 last_frame_callee_id >= 0; last_frame_callee_id--) {
195 // Searching for a real callee frame. Skipping inline frames since they
196 // cannot be downcasted to StackFrameX86.
197 if (frames[last_frame_callee_id]->trust == StackFrame::FRAME_TRUST_INLINE) {
198 continue;
199 }
200 const StackFrameX86* last_frame_callee
201 = static_cast<StackFrameX86*>(frames[last_frame_callee_id]);
202 WindowsFrameInfo* last_frame_callee_info
203 = last_frame_callee->windows_frame_info;
204 if (last_frame_callee_info &&
205 (last_frame_callee_info->valid
206 & WindowsFrameInfo::VALID_PARAMETER_SIZE)) {
207 last_frame_callee_parameter_size =
208 last_frame_callee_info->parameter_size;
209 }
210 }
211
212 // Set up the dictionary for the PostfixEvaluator. %ebp, %esp, and sometimes
213 // %ebx are used in program strings, and their previous values are known, so
214 // set them here.
215 PostfixEvaluator<uint32_t>::DictionaryType dictionary;
216 // Provide the current register values.
217 dictionary["$ebp"] = last_frame->context.ebp;
218 dictionary["$esp"] = last_frame->context.esp;
219 if (last_frame->context_validity & StackFrameX86::CONTEXT_VALID_EBX)
220 dictionary["$ebx"] = last_frame->context.ebx;
221 // Provide constants from the debug info for last_frame and its callee.
222 // .cbCalleeParams is a Breakpad extension that allows us to use the
223 // PostfixEvaluator engine when certain types of debugging information
224 // are present without having to write the constants into the program
225 // string as literals.
226 dictionary[".cbCalleeParams"] = last_frame_callee_parameter_size;
227 dictionary[".cbSavedRegs"] = last_frame_info->saved_register_size;
228 dictionary[".cbLocals"] = last_frame_info->local_size;
229
230 uint32_t raSearchStart = last_frame->context.esp +
231 last_frame_callee_parameter_size +
232 last_frame_info->local_size +
233 last_frame_info->saved_register_size;
234
235 uint32_t raSearchStartOld = raSearchStart;
236 uint32_t found = 0; // dummy value
237 // Scan up to three words above the calculated search value, in case
238 // the stack was aligned to a quadword boundary.
239 //
240 // TODO(ivan.penkov): Consider cleaning up the scan for return address that
241 // follows. The purpose of this scan is to adjust the .raSearchStart
242 // calculation (which is based on register %esp) in the cases where register
243 // %esp may have been aligned (up to a quadword). There are two problems
244 // with this approach:
245 // 1) In practice, 64 byte boundary alignment is seen which clearly can not
246 // be handled by a three word scan.
247 // 2) A search for a return address is "guesswork" by definition because
248 // the results will be different depending on what is left on the stack
249 // from previous executions.
250 // So, basically, the results from this scan should be ignored if other means
251 // for calculation of the value of .raSearchStart are available.
252 if (ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3) &&
253 last_frame->trust == StackFrame::FRAME_TRUST_CONTEXT &&
254 last_frame->windows_frame_info != NULL &&
255 last_frame_info->type_ == WindowsFrameInfo::STACK_INFO_FPO &&
256 raSearchStartOld == raSearchStart &&
257 found == last_frame->context.eip) {
258 // The context frame represents an FPO-optimized Windows system call.
259 // On the top of the stack we have a pointer to the current instruction.
260 // This means that the callee has returned but the return address is still
261 // on the top of the stack which is very atypical situaltion.
262 // Skip one slot from the stack and do another scan in order to get the
263 // actual return address.
264 raSearchStart += 4;
265 ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3);
266 }
267
268 dictionary[".cbParams"] = last_frame_info->parameter_size;
269
270 // Decide what type of program string to use. The program string is in
271 // postfix notation and will be passed to PostfixEvaluator::Evaluate.
272 // Given the dictionary and the program string, it is possible to compute
273 // the return address and the values of other registers in the calling
274 // function. Because of bugs described below, the stack may need to be
275 // scanned for these values. The results of program string evaluation
276 // will be used to determine whether to scan for better values.
277 string program_string;
278 bool recover_ebp = true;
279
280 trust = StackFrame::FRAME_TRUST_CFI;
281 if (!last_frame_info->program_string.empty()) {
282 // The FPO data has its own program string, which will tell us how to
283 // get to the caller frame, and may even fill in the values of
284 // nonvolatile registers and provide pointers to local variables and
285 // parameters. In some cases, particularly with program strings that use
286 // .raSearchStart, the stack may need to be scanned afterward.
287 program_string = last_frame_info->program_string;
288 } else if (last_frame_info->allocates_base_pointer) {
289 // The function corresponding to the last frame doesn't use the frame
290 // pointer for conventional purposes, but it does allocate a new
291 // frame pointer and use it for its own purposes. Its callee's
292 // information is still accessed relative to %esp, and the previous
293 // value of %ebp can be recovered from a location in its stack frame,
294 // within the saved-register area.
295 //
296 // Functions that fall into this category use the %ebp register for
297 // a purpose other than the frame pointer. They restore the caller's
298 // %ebp before returning. These functions create their stack frame
299 // after a CALL by decrementing the stack pointer in an amount
300 // sufficient to store local variables, and then PUSHing saved
301 // registers onto the stack. Arguments to a callee function, if any,
302 // are PUSHed after that. Walking up to the caller, therefore,
303 // can be done solely with calculations relative to the stack pointer
304 // (%esp). The return address is recovered from the memory location
305 // above the known sizes of the callee's parameters, saved registers,
306 // and locals. The caller's stack pointer (the value of %esp when
307 // the caller executed CALL) is the location immediately above the
308 // saved return address. The saved value of %ebp to be restored for
309 // the caller is at a known location in the saved-register area of
310 // the stack frame.
311 //
312 // For this type of frame, MSVC 14 (from Visual Studio 8/2005) in
313 // link-time code generation mode (/LTCG and /GL) can generate erroneous
314 // debugging data. The reported size of saved registers can be 0,
315 // which is clearly an error because these frames must, at the very
316 // least, save %ebp. For this reason, in addition to those given above
317 // about the use of .raSearchStart, the stack may need to be scanned
318 // for a better return address and a better frame pointer after the
319 // program string is evaluated.
320 //
321 // %eip_new = *(%esp_old + callee_params + saved_regs + locals)
322 // %ebp_new = *(%esp_old + callee_params + saved_regs - 8)
323 // %esp_new = %esp_old + callee_params + saved_regs + locals + 4
324 program_string = "$eip .raSearchStart ^ = "
325 "$ebp $esp .cbCalleeParams + .cbSavedRegs + 8 - ^ = "
326 "$esp .raSearchStart 4 + =";
327 } else {
328 // The function corresponding to the last frame doesn't use %ebp at
329 // all. The callee frame is located relative to %esp.
330 //
331 // The called procedure's instruction pointer and stack pointer are
332 // recovered in the same way as the case above, except that no
333 // frame pointer (%ebp) is used at all, so it is not saved anywhere
334 // in the callee's stack frame and does not need to be recovered.
335 // Because %ebp wasn't used in the callee, whatever value it has
336 // is the value that it had in the caller, so it can be carried
337 // straight through without bringing its validity into question.
338 //
339 // Because of the use of .raSearchStart, the stack will possibly be
340 // examined to locate a better return address after program string
341 // evaluation. The stack will not be examined to locate a saved
342 // %ebp value, because these frames do not save (or use) %ebp.
343 //
344 // We also propagate %ebx through, as it is commonly unmodifed after
345 // calling simple forwarding functions in ntdll (that are this non-EBP
346 // using type). It's not clear that this is always correct, but it is
347 // important for some functions to get a correct walk.
348 //
349 // %eip_new = *(%esp_old + callee_params + saved_regs + locals)
350 // %esp_new = %esp_old + callee_params + saved_regs + locals + 4
351 // %ebp_new = %ebp_old
352 // %ebx_new = %ebx_old // If available.
353 program_string = "$eip .raSearchStart ^ = "
354 "$esp .raSearchStart 4 + =";
355 if (last_frame->context_validity & StackFrameX86::CONTEXT_VALID_EBX)
356 program_string += " $ebx $ebx =";
357 recover_ebp = false;
358 }
359
360 // Check for alignment operators in the program string. If alignment
361 // operators are found, then current %ebp must be valid and it is the only
362 // reliable data point that can be used for getting to the previous frame.
363 // E.g. the .raSearchStart calculation (above) is based on %esp and since
364 // %esp was aligned in the current frame (which is a lossy operation) the
365 // calculated value of .raSearchStart cannot be correct and should not be
366 // used. Instead .raSearchStart must be calculated based on %ebp.
367 // The code that follows assumes that .raSearchStart is supposed to point
368 // at the saved return address (ebp + 4).
369 // For some more details on this topic, take a look at the following thread:
370 // https://groups.google.com/forum/#!topic/google-breakpad-dev/ZP1FA9B1JjM
371 if ((StackFrameX86::CONTEXT_VALID_EBP & last_frame->context_validity) != 0 &&
372 program_string.find('@') != string::npos) {
373 raSearchStart = last_frame->context.ebp + 4;
374 }
375
376 // The difference between raSearch and raSearchStart is unknown,
377 // but making them the same seems to work well in practice.
378 dictionary[".raSearchStart"] = raSearchStart;
379 dictionary[".raSearch"] = raSearchStart;
380
381 // Now crank it out, making sure that the program string set at least the
382 // two required variables.
383 PostfixEvaluator<uint32_t> evaluator =
384 PostfixEvaluator<uint32_t>(&dictionary, memory_);
385 PostfixEvaluator<uint32_t>::DictionaryValidityType dictionary_validity;
386 if (!evaluator.Evaluate(program_string, &dictionary_validity) ||
387 dictionary_validity.find("$eip") == dictionary_validity.end() ||
388 dictionary_validity.find("$esp") == dictionary_validity.end()) {
389 // Program string evaluation failed. It may be that %eip is not somewhere
390 // with stack frame info, and %ebp is pointing to non-stack memory, so
391 // our evaluation couldn't succeed. We'll scan the stack for a return
392 // address. This can happen if the stack is in a module for which
393 // we don't have symbols, and that module is compiled without a
394 // frame pointer.
395 uint32_t location_start = last_frame->context.esp;
396 uint32_t location, eip;
397 if (!stack_scan_allowed
398 || !ScanForReturnAddress(location_start, &location, &eip,
399 frames.size() == 1 /* is_context_frame */)) {
400 // if we can't find an instruction pointer even with stack scanning,
401 // give up.
402 return NULL;
403 }
404
405 // This seems like a reasonable return address. Since program string
406 // evaluation failed, use it and set %esp to the location above the
407 // one where the return address was found.
408 dictionary["$eip"] = eip;
409 dictionary["$esp"] = location + 4;
410 trust = StackFrame::FRAME_TRUST_SCAN;
411 }
412
413 // Since this stack frame did not use %ebp in a traditional way,
414 // locating the return address isn't entirely deterministic. In that
415 // case, the stack can be scanned to locate the return address.
416 //
417 // However, if program string evaluation resulted in both %eip and
418 // %ebp values of 0, trust that the end of the stack has been
419 // reached and don't scan for anything else.
420 if (dictionary["$eip"] != 0 || dictionary["$ebp"] != 0) {
421 int offset = 0;
422
423 // This scan can only be done if a CodeModules object is available, to
424 // check that candidate return addresses are in fact inside a module.
425 //
426 // TODO(mmentovai): This ignores dynamically-generated code. One possible
427 // solution is to check the minidump's memory map to see if the candidate
428 // %eip value comes from a mapped executable page, although this would
429 // require dumps that contain MINIDUMP_MEMORY_INFO, which the Breakpad
430 // client doesn't currently write (it would need to call MiniDumpWriteDump
431 // with the MiniDumpWithFullMemoryInfo type bit set). Even given this
432 // ability, older OSes (pre-XP SP2) and CPUs (pre-P4) don't enforce
433 // an independent execute privilege on memory pages.
434
435 uint32_t eip = dictionary["$eip"];
436 if (modules_ && !modules_->GetModuleForAddress(eip)) {
437 // The instruction pointer at .raSearchStart was invalid, so start
438 // looking one 32-bit word above that location.
439 uint32_t location_start = dictionary[".raSearchStart"] + 4;
440 uint32_t location;
441 if (stack_scan_allowed
442 && ScanForReturnAddress(location_start, &location, &eip,
443 frames.size() == 1 /* is_context_frame */)) {
444 // This is a better return address that what program string
445 // evaluation found. Use it, and set %esp to the location above the
446 // one where the return address was found.
447 dictionary["$eip"] = eip;
448 dictionary["$esp"] = location + 4;
449 offset = location - location_start;
450 trust = StackFrame::FRAME_TRUST_CFI_SCAN;
451 }
452 }
453
454 if (recover_ebp) {
455 // When trying to recover the previous value of the frame pointer (%ebp),
456 // start looking at the lowest possible address in the saved-register
457 // area, and look at the entire saved register area, increased by the
458 // size of |offset| to account for additional data that may be on the
459 // stack. The scan is performed from the highest possible address to
460 // the lowest, because the expectation is that the function's prolog
461 // would have saved %ebp early.
462 uint32_t ebp = dictionary["$ebp"];
463
464 // When a scan for return address is used, it is possible to skip one or
465 // more frames (when return address is not in a known module). One
466 // indication for skipped frames is when the value of %ebp is lower than
467 // the location of the return address on the stack
468 bool has_skipped_frames =
469 (trust != StackFrame::FRAME_TRUST_CFI && ebp <= raSearchStart + offset);
470
471 uint32_t value; // throwaway variable to check pointer validity
472 if (has_skipped_frames || !memory_->GetMemoryAtAddress(ebp, &value)) {
473 int fp_search_bytes = last_frame_info->saved_register_size + offset;
474 uint32_t location_end = last_frame->context.esp +
475 last_frame_callee_parameter_size;
476
477 for (uint32_t location = location_end + fp_search_bytes;
478 location >= location_end;
479 location -= 4) {
480 if (!memory_->GetMemoryAtAddress(location, &ebp))
481 break;
482
483 if (memory_->GetMemoryAtAddress(ebp, &value)) {
484 // The candidate value is a pointer to the same memory region
485 // (the stack). Prefer it as a recovered %ebp result.
486 dictionary["$ebp"] = ebp;
487 break;
488 }
489 }
490 }
491 }
492 }
493
494 // Create a new stack frame (ownership will be transferred to the caller)
495 // and fill it in.
496 StackFrameX86* frame = new StackFrameX86();
497
498 frame->trust = trust;
499 frame->context = last_frame->context;
500 frame->context.eip = dictionary["$eip"];
501 frame->context.esp = dictionary["$esp"];
502 frame->context.ebp = dictionary["$ebp"];
503 frame->context_validity = StackFrameX86::CONTEXT_VALID_EIP |
504 StackFrameX86::CONTEXT_VALID_ESP |
505 StackFrameX86::CONTEXT_VALID_EBP;
506
507 // These are nonvolatile (callee-save) registers, and the program string
508 // may have filled them in.
509 if (dictionary_validity.find("$ebx") != dictionary_validity.end()) {
510 frame->context.ebx = dictionary["$ebx"];
511 frame->context_validity |= StackFrameX86::CONTEXT_VALID_EBX;
512 }
513 if (dictionary_validity.find("$esi") != dictionary_validity.end()) {
514 frame->context.esi = dictionary["$esi"];
515 frame->context_validity |= StackFrameX86::CONTEXT_VALID_ESI;
516 }
517 if (dictionary_validity.find("$edi") != dictionary_validity.end()) {
518 frame->context.edi = dictionary["$edi"];
519 frame->context_validity |= StackFrameX86::CONTEXT_VALID_EDI;
520 }
521
522 return frame;
523}
524
525StackFrameX86* StackwalkerX86::GetCallerByCFIFrameInfo(
526 const vector<StackFrame*>& frames,
527 CFIFrameInfo* cfi_frame_info) {
528 // The last frame can never be inline. A sequence of inline frames always
529 // finishes with a conventional frame.
530 assert(frames.back()->trust != StackFrame::FRAME_TRUST_INLINE);
531 StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
532 last_frame->cfi_frame_info = cfi_frame_info;
533
534 scoped_ptr<StackFrameX86> frame(new StackFrameX86());
535 if (!cfi_walker_
536 .FindCallerRegisters(*memory_, *cfi_frame_info,
537 last_frame->context, last_frame->context_validity,
538 &frame->context, &frame->context_validity))
539 return NULL;
540
541 // Make sure we recovered all the essentials.
542 static const int essentials = (StackFrameX86::CONTEXT_VALID_EIP
543 | StackFrameX86::CONTEXT_VALID_ESP
544 | StackFrameX86::CONTEXT_VALID_EBP);
545 if ((frame->context_validity & essentials) != essentials)
546 return NULL;
547
548 frame->trust = StackFrame::FRAME_TRUST_CFI;
549
550 return frame.release();
551}
552
553StackFrameX86* StackwalkerX86::GetCallerByEBPAtBase(
554 const vector<StackFrame*>& frames,
555 bool stack_scan_allowed) {
556 StackFrame::FrameTrust trust;
557 // The last frame can never be inline. A sequence of inline frames always
558 // finishes with a conventional frame.
559 assert(frames.back()->trust != StackFrame::FRAME_TRUST_INLINE);
560 StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
561 uint32_t last_esp = last_frame->context.esp;
562 uint32_t last_ebp = last_frame->context.ebp;
563
564 // Assume that the standard %ebp-using x86 calling convention is in
565 // use.
566 //
567 // The typical x86 calling convention, when frame pointers are present,
568 // is for the calling procedure to use CALL, which pushes the return
569 // address onto the stack and sets the instruction pointer (%eip) to
570 // the entry point of the called routine. The called routine then
571 // PUSHes the calling routine's frame pointer (%ebp) onto the stack
572 // before copying the stack pointer (%esp) to the frame pointer (%ebp).
573 // Therefore, the calling procedure's frame pointer is always available
574 // by dereferencing the called procedure's frame pointer, and the return
575 // address is always available at the memory location immediately above
576 // the address pointed to by the called procedure's frame pointer. The
577 // calling procedure's stack pointer (%esp) is 8 higher than the value
578 // of the called procedure's frame pointer at the time the calling
579 // procedure made the CALL: 4 bytes for the return address pushed by the
580 // CALL itself, and 4 bytes for the callee's PUSH of the caller's frame
581 // pointer.
582 //
583 // %eip_new = *(%ebp_old + 4)
584 // %esp_new = %ebp_old + 8
585 // %ebp_new = *(%ebp_old)
586
587 uint32_t caller_eip, caller_esp, caller_ebp;
588
589 if (memory_->GetMemoryAtAddress(last_ebp + 4, &caller_eip) &&
590 memory_->GetMemoryAtAddress(last_ebp, &caller_ebp)) {
591 caller_esp = last_ebp + 8;
592 trust = StackFrame::FRAME_TRUST_FP;
593 } else {
594 // We couldn't read the memory %ebp refers to. It may be that %ebp
595 // is pointing to non-stack memory. We'll scan the stack for a
596 // return address. This can happen if last_frame is executing code
597 // for a module for which we don't have symbols, and that module
598 // is compiled without a frame pointer.
599 if (!stack_scan_allowed
600 || !ScanForReturnAddress(last_esp, &caller_esp, &caller_eip,
601 frames.size() == 1 /* is_context_frame */)) {
602 // if we can't find an instruction pointer even with stack scanning,
603 // give up.
604 return NULL;
605 }
606
607 // ScanForReturnAddress found a reasonable return address. Advance %esp to
608 // the location immediately above the one where the return address was
609 // found.
610 caller_esp += 4;
611 // Try to restore the %ebp chain. The caller %ebp should be stored at a
612 // location immediately below the one where the return address was found.
613 // A valid caller %ebp must be greater than the address where it is stored
614 // and the gap between the two adjacent frames should be reasonable.
615 uint32_t restored_ebp_chain = caller_esp - 8;
616 if (!memory_->GetMemoryAtAddress(restored_ebp_chain, &caller_ebp) ||
617 caller_ebp <= restored_ebp_chain ||
618 caller_ebp - restored_ebp_chain > kMaxReasonableGapBetweenFrames) {
619 // The restored %ebp chain doesn't appear to be valid.
620 // Assume that %ebp is unchanged.
621 caller_ebp = last_ebp;
622 }
623
624 trust = StackFrame::FRAME_TRUST_SCAN;
625 }
626
627 // Create a new stack frame (ownership will be transferred to the caller)
628 // and fill it in.
629 StackFrameX86* frame = new StackFrameX86();
630
631 frame->trust = trust;
632 frame->context = last_frame->context;
633 frame->context.eip = caller_eip;
634 frame->context.esp = caller_esp;
635 frame->context.ebp = caller_ebp;
636 frame->context_validity = StackFrameX86::CONTEXT_VALID_EIP |
637 StackFrameX86::CONTEXT_VALID_ESP |
638 StackFrameX86::CONTEXT_VALID_EBP;
639
640 return frame;
641}
642
643StackFrame* StackwalkerX86::GetCallerFrame(const CallStack* stack,
644 bool stack_scan_allowed) {
645 if (!memory_ || !stack) {
646 BPLOG(ERROR) << "Can't get caller frame without memory or stack";
647 return NULL;
648 }
649
650 const vector<StackFrame*>& frames = *stack->frames();
651 StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
652 // The last frame can never be inline. A sequence of inline frames always
653 // finishes with a conventional frame.
654 assert(last_frame->trust != StackFrame::FRAME_TRUST_INLINE);
655 scoped_ptr<StackFrameX86> new_frame;
656
657 // If the resolver has Windows stack walking information, use that.
658 WindowsFrameInfo* windows_frame_info
659 = frame_symbolizer_->FindWindowsFrameInfo(last_frame);
660 if (windows_frame_info)
661 new_frame.reset(GetCallerByWindowsFrameInfo(frames, windows_frame_info,
662 stack_scan_allowed));
663
664 // If the resolver has DWARF CFI information, use that.
665 if (!new_frame.get()) {
666 CFIFrameInfo* cfi_frame_info =
667 frame_symbolizer_->FindCFIFrameInfo(last_frame);
668 if (cfi_frame_info)
669 new_frame.reset(GetCallerByCFIFrameInfo(frames, cfi_frame_info));
670 }
671
672 // Otherwise, hope that the program was using a traditional frame structure.
673 if (!new_frame.get())
674 new_frame.reset(GetCallerByEBPAtBase(frames, stack_scan_allowed));
675
676 // If nothing worked, tell the caller.
677 if (!new_frame.get())
678 return NULL;
679
680 // Should we terminate the stack walk? (end-of-stack or broken invariant)
681 if (TerminateWalk(new_frame->context.eip,
682 new_frame->context.esp,
683 last_frame->context.esp,
684 frames.size() == 1)) {
685 return NULL;
686 }
687
688 // new_frame->context.eip is the return address, which is the instruction
689 // after the CALL that caused us to arrive at the callee. Set
690 // new_frame->instruction to one less than that, so it points within the
691 // CALL instruction. See StackFrame::instruction for details, and
692 // StackFrameAMD64::ReturnAddress.
693 new_frame->instruction = new_frame->context.eip - 1;
694
695 return new_frame.release();
696}
697
698} // namespace google_breakpad
699