michael@0: // Copyright (c) 2010 Google Inc.
michael@0: // All rights reserved.
michael@0: //
michael@0: // Redistribution and use in source and binary forms, with or without
michael@0: // modification, are permitted provided that the following conditions are
michael@0: // met:
michael@0: //
michael@0: //     * Redistributions of source code must retain the above copyright
michael@0: // notice, this list of conditions and the following disclaimer.
michael@0: //     * Redistributions in binary form must reproduce the above
michael@0: // copyright notice, this list of conditions and the following disclaimer
michael@0: // in the documentation and/or other materials provided with the
michael@0: // distribution.
michael@0: //     * Neither the name of Google Inc. nor the names of its
michael@0: // contributors may be used to endorse or promote products derived from
michael@0: // this software without specific prior written permission.
michael@0: //
michael@0: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
michael@0: // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
michael@0: // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
michael@0: // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
michael@0: // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
michael@0: // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
michael@0: // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
michael@0: // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
michael@0: // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
michael@0: // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
michael@0: // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0: 
michael@0: // stackwalker_x86.cc: x86-specific stackwalker.
michael@0: //
michael@0: // See stackwalker_x86.h for documentation.
michael@0: //
michael@0: // Author: Mark Mentovai
michael@0: 
michael@0: #include <assert.h>
michael@0: #include <string>
michael@0: 
michael@0: #include "common/scoped_ptr.h"
michael@0: #include "google_breakpad/processor/call_stack.h"
michael@0: #include "google_breakpad/processor/code_modules.h"
michael@0: #include "google_breakpad/processor/memory_region.h"
michael@0: #include "google_breakpad/processor/source_line_resolver_interface.h"
michael@0: #include "google_breakpad/processor/stack_frame_cpu.h"
michael@0: #include "common/logging.h"
michael@0: #include "processor/postfix_evaluator-inl.h"
michael@0: #include "processor/stackwalker_x86.h"
michael@0: #include "processor/windows_frame_info.h"
michael@0: #include "processor/cfi_frame_info.h"
michael@0: 
michael@0: namespace google_breakpad {
michael@0: 
michael@0: 
michael@0: const StackwalkerX86::CFIWalker::RegisterSet
michael@0: StackwalkerX86::cfi_register_map_[] = {
michael@0:   // It may seem like $eip and $esp are callee-saves, because (with Unix or
michael@0:   // cdecl calling conventions) the callee is responsible for having them
michael@0:   // restored upon return. But the callee_saves flags here really means
michael@0:   // that the walker should assume they're unchanged if the CFI doesn't
michael@0:   // mention them, which is clearly wrong for $eip and $esp.
michael@0:   { ToUniqueString("$eip"), ToUniqueString(".ra"),  false,
michael@0:     StackFrameX86::CONTEXT_VALID_EIP, &MDRawContextX86::eip },
michael@0:   { ToUniqueString("$esp"), ToUniqueString(".cfa"), false,
michael@0:     StackFrameX86::CONTEXT_VALID_ESP, &MDRawContextX86::esp },
michael@0:   { ToUniqueString("$ebp"), NULL,   true,
michael@0:     StackFrameX86::CONTEXT_VALID_EBP, &MDRawContextX86::ebp },
michael@0:   { ToUniqueString("$eax"), NULL,   false,
michael@0:     StackFrameX86::CONTEXT_VALID_EAX, &MDRawContextX86::eax },
michael@0:   { ToUniqueString("$ebx"), NULL,   true,
michael@0:     StackFrameX86::CONTEXT_VALID_EBX, &MDRawContextX86::ebx },
michael@0:   { ToUniqueString("$ecx"), NULL,   false,
michael@0:     StackFrameX86::CONTEXT_VALID_ECX, &MDRawContextX86::ecx },
michael@0:   { ToUniqueString("$edx"), NULL,   false,
michael@0:     StackFrameX86::CONTEXT_VALID_EDX, &MDRawContextX86::edx },
michael@0:   { ToUniqueString("$esi"), NULL,   true,
michael@0:     StackFrameX86::CONTEXT_VALID_ESI, &MDRawContextX86::esi },
michael@0:   { ToUniqueString("$edi"), NULL,   true,
michael@0:     StackFrameX86::CONTEXT_VALID_EDI, &MDRawContextX86::edi },
michael@0: };
michael@0: 
michael@0: StackwalkerX86::StackwalkerX86(const SystemInfo* system_info,
michael@0:                                const MDRawContextX86* context,
michael@0:                                MemoryRegion* memory,
michael@0:                                const CodeModules* modules,
michael@0:                                StackFrameSymbolizer* resolver_helper)
michael@0:     : Stackwalker(system_info, memory, modules, resolver_helper),
michael@0:       context_(context),
michael@0:       cfi_walker_(cfi_register_map_,
michael@0:                   (sizeof(cfi_register_map_) / sizeof(cfi_register_map_[0]))) {
michael@0:   if (memory_ && memory_->GetBase() + memory_->GetSize() - 1 > 0xffffffff) {
michael@0:     // The x86 is a 32-bit CPU, the limits of the supplied stack are invalid.
michael@0:     // Mark memory_ = NULL, which will cause stackwalking to fail.
michael@0:     BPLOG(ERROR) << "Memory out of range for stackwalking: " <<
michael@0:                     HexString(memory_->GetBase()) << "+" <<
michael@0:                     HexString(memory_->GetSize());
michael@0:     memory_ = NULL;
michael@0:   }
michael@0: }
michael@0: 
michael@0: StackFrameX86::~StackFrameX86() {
michael@0:   if (windows_frame_info)
michael@0:     delete windows_frame_info;
michael@0:   windows_frame_info = NULL;
michael@0:   if (cfi_frame_info)
michael@0:     delete cfi_frame_info;
michael@0:   cfi_frame_info = NULL;
michael@0: }
michael@0: 
michael@0: uint64_t StackFrameX86::ReturnAddress() const
michael@0: {
michael@0:   assert(context_validity & StackFrameX86::CONTEXT_VALID_EIP);
michael@0:   return context.eip;   
michael@0: }
michael@0: 
michael@0: StackFrame* StackwalkerX86::GetContextFrame() {
michael@0:   if (!context_) {
michael@0:     BPLOG(ERROR) << "Can't get context frame without context";
michael@0:     return NULL;
michael@0:   }
michael@0: 
michael@0:   StackFrameX86* frame = new StackFrameX86();
michael@0: 
michael@0:   // The instruction pointer is stored directly in a register, so pull it
michael@0:   // straight out of the CPU context structure.
michael@0:   frame->context = *context_;
michael@0:   frame->context_validity = StackFrameX86::CONTEXT_VALID_ALL;
michael@0:   frame->trust = StackFrame::FRAME_TRUST_CONTEXT;
michael@0:   frame->instruction = frame->context.eip;
michael@0: 
michael@0:   return frame;
michael@0: }
michael@0: 
michael@0: StackFrameX86* StackwalkerX86::GetCallerByWindowsFrameInfo(
michael@0:     const vector<StackFrame*> &frames,
michael@0:     WindowsFrameInfo* last_frame_info,
michael@0:     bool stack_scan_allowed) {
michael@0:   StackFrame::FrameTrust trust = StackFrame::FRAME_TRUST_NONE;
michael@0: 
michael@0:   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
michael@0: 
michael@0:   // Save the stack walking info we found, in case we need it later to
michael@0:   // find the callee of the frame we're constructing now.
michael@0:   last_frame->windows_frame_info = last_frame_info;
michael@0: 
michael@0:   // This function only covers the full STACK WIN case. If
michael@0:   // last_frame_info is VALID_PARAMETER_SIZE-only, then we should
michael@0:   // assume the traditional frame format or use some other strategy.
michael@0:   if (last_frame_info->valid != WindowsFrameInfo::VALID_ALL)
michael@0:     return NULL;
michael@0: 
michael@0:   // This stackwalker sets each frame's %esp to its value immediately prior
michael@0:   // to the CALL into the callee.  This means that %esp points to the last
michael@0:   // callee argument pushed onto the stack, which may not be where %esp points
michael@0:   // after the callee returns.  Specifically, the value is correct for the
michael@0:   // cdecl calling convention, but not other conventions.  The cdecl
michael@0:   // convention requires a caller to pop its callee's arguments from the
michael@0:   // stack after the callee returns.  This is usually accomplished by adding
michael@0:   // the known size of the arguments to %esp.  Other calling conventions,
michael@0:   // including stdcall, thiscall, and fastcall, require the callee to pop any
michael@0:   // parameters stored on the stack before returning.  This is usually
michael@0:   // accomplished by using the RET n instruction, which pops n bytes off
michael@0:   // the stack after popping the return address.
michael@0:   //
michael@0:   // Because each frame's %esp will point to a location on the stack after
michael@0:   // callee arguments have been PUSHed, when locating things in a stack frame
michael@0:   // relative to %esp, the size of the arguments to the callee need to be
michael@0:   // taken into account.  This seems a little bit unclean, but it's better
michael@0:   // than the alternative, which would need to take these same things into
michael@0:   // account, but only for cdecl functions.  With this implementation, we get
michael@0:   // to be agnostic about each function's calling convention.  Furthermore,
michael@0:   // this is how Windows debugging tools work, so it means that the %esp
michael@0:   // values produced by this stackwalker directly correspond to the %esp
michael@0:   // values you'll see there.
michael@0:   //
michael@0:   // If the last frame has no callee (because it's the context frame), just
michael@0:   // set the callee parameter size to 0: the stack pointer can't point to
michael@0:   // callee arguments because there's no callee.  This is correct as long
michael@0:   // as the context wasn't captured while arguments were being pushed for
michael@0:   // a function call.  Note that there may be functions whose parameter sizes
michael@0:   // are unknown, 0 is also used in that case.  When that happens, it should
michael@0:   // be possible to walk to the next frame without reference to %esp.
michael@0: 
michael@0:   uint32_t last_frame_callee_parameter_size = 0;
michael@0:   int frames_already_walked = frames.size();
michael@0:   if (frames_already_walked >= 2) {
michael@0:     const StackFrameX86* last_frame_callee
michael@0:         = static_cast<StackFrameX86*>(frames[frames_already_walked - 2]);
michael@0:     WindowsFrameInfo* last_frame_callee_info
michael@0:         = last_frame_callee->windows_frame_info;
michael@0:     if (last_frame_callee_info &&
michael@0:         (last_frame_callee_info->valid
michael@0:          & WindowsFrameInfo::VALID_PARAMETER_SIZE)) {
michael@0:       last_frame_callee_parameter_size =
michael@0:           last_frame_callee_info->parameter_size;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Set up the dictionary for the PostfixEvaluator.  %ebp and %esp are used
michael@0:   // in each program string, and their previous values are known, so set them
michael@0:   // here.
michael@0:   PostfixEvaluator<uint32_t>::DictionaryType dictionary;
michael@0:   // Provide the current register values.
michael@0:   dictionary.set(ustr__ZSebp(), last_frame->context.ebp);
michael@0:   dictionary.set(ustr__ZSesp(), last_frame->context.esp);
michael@0:   // Provide constants from the debug info for last_frame and its callee.
michael@0:   // .cbCalleeParams is a Breakpad extension that allows us to use the
michael@0:   // PostfixEvaluator engine when certain types of debugging information
michael@0:   // are present without having to write the constants into the program
michael@0:   // string as literals.
michael@0:   dictionary.set(ustr__ZDcbCalleeParams(), last_frame_callee_parameter_size);
michael@0:   dictionary.set(ustr__ZDcbSavedRegs(), last_frame_info->saved_register_size);
michael@0:   dictionary.set(ustr__ZDcbLocals(), last_frame_info->local_size);
michael@0: 
michael@0:   uint32_t raSearchStart = last_frame->context.esp +
michael@0:                             last_frame_callee_parameter_size +
michael@0:                             last_frame_info->local_size +
michael@0:                             last_frame_info->saved_register_size;
michael@0: 
michael@0:   uint32_t raSearchStartOld = raSearchStart;
michael@0:   uint32_t found = 0;  // dummy value
michael@0:   // Scan up to three words above the calculated search value, in case
michael@0:   // the stack was aligned to a quadword boundary.
michael@0:   if (ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3) &&
michael@0:       last_frame->trust == StackFrame::FRAME_TRUST_CONTEXT &&
michael@0:       last_frame->windows_frame_info != NULL &&
michael@0:       last_frame_info->type_ == WindowsFrameInfo::STACK_INFO_FPO &&
michael@0:       raSearchStartOld == raSearchStart &&
michael@0:       found == last_frame->context.eip) {
michael@0:     // The context frame represents an FPO-optimized Windows system call.
michael@0:     // On the top of the stack we have a pointer to the current instruction.
michael@0:     // This means that the callee has returned but the return address is still
michael@0:     // on the top of the stack which is very atypical situaltion.
michael@0:     // Skip one slot from the stack and do another scan in order to get the
michael@0:     // actual return address.
michael@0:     raSearchStart += 4;
michael@0:     ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3);
michael@0:   }
michael@0: 
michael@0:   // The difference between raSearch and raSearchStart is unknown,
michael@0:   // but making them the same seems to work well in practice.
michael@0:   dictionary.set(ustr__ZDraSearchStart(), raSearchStart);
michael@0:   dictionary.set(ustr__ZDraSearch(), raSearchStart);
michael@0: 
michael@0:   dictionary.set(ustr__ZDcbParams(), last_frame_info->parameter_size);
michael@0: 
michael@0:   // Decide what type of program string to use. The program string is in
michael@0:   // postfix notation and will be passed to PostfixEvaluator::Evaluate.
michael@0:   // Given the dictionary and the program string, it is possible to compute
michael@0:   // the return address and the values of other registers in the calling
michael@0:   // function. Because of bugs described below, the stack may need to be
michael@0:   // scanned for these values. The results of program string evaluation
michael@0:   // will be used to determine whether to scan for better values.
michael@0:   string program_string;
michael@0:   bool recover_ebp = true;
michael@0: 
michael@0:   trust = StackFrame::FRAME_TRUST_CFI;
michael@0:   if (!last_frame_info->program_string.empty()) {
michael@0:     // The FPO data has its own program string, which will tell us how to
michael@0:     // get to the caller frame, and may even fill in the values of
michael@0:     // nonvolatile registers and provide pointers to local variables and
michael@0:     // parameters.  In some cases, particularly with program strings that use
michael@0:     // .raSearchStart, the stack may need to be scanned afterward.
michael@0:     program_string = last_frame_info->program_string;
michael@0:   } else if (last_frame_info->allocates_base_pointer) {
michael@0:     // The function corresponding to the last frame doesn't use the frame
michael@0:     // pointer for conventional purposes, but it does allocate a new
michael@0:     // frame pointer and use it for its own purposes.  Its callee's
michael@0:     // information is still accessed relative to %esp, and the previous
michael@0:     // value of %ebp can be recovered from a location in its stack frame,
michael@0:     // within the saved-register area.
michael@0:     //
michael@0:     // Functions that fall into this category use the %ebp register for
michael@0:     // a purpose other than the frame pointer.  They restore the caller's
michael@0:     // %ebp before returning.  These functions create their stack frame
michael@0:     // after a CALL by decrementing the stack pointer in an amount
michael@0:     // sufficient to store local variables, and then PUSHing saved
michael@0:     // registers onto the stack.  Arguments to a callee function, if any,
michael@0:     // are PUSHed after that.  Walking up to the caller, therefore,
michael@0:     // can be done solely with calculations relative to the stack pointer
michael@0:     // (%esp).  The return address is recovered from the memory location
michael@0:     // above the known sizes of the callee's parameters, saved registers,
michael@0:     // and locals.  The caller's stack pointer (the value of %esp when
michael@0:     // the caller executed CALL) is the location immediately above the
michael@0:     // saved return address.  The saved value of %ebp to be restored for
michael@0:     // the caller is at a known location in the saved-register area of
michael@0:     // the stack frame.
michael@0:     //
michael@0:     // For this type of frame, MSVC 14 (from Visual Studio 8/2005) in
michael@0:     // link-time code generation mode (/LTCG and /GL) can generate erroneous
michael@0:     // debugging data.  The reported size of saved registers can be 0,
michael@0:     // which is clearly an error because these frames must, at the very
michael@0:     // least, save %ebp.  For this reason, in addition to those given above
michael@0:     // about the use of .raSearchStart, the stack may need to be scanned
michael@0:     // for a better return address and a better frame pointer after the
michael@0:     // program string is evaluated.
michael@0:     //
michael@0:     // %eip_new = *(%esp_old + callee_params + saved_regs + locals)
michael@0:     // %ebp_new = *(%esp_old + callee_params + saved_regs - 8)
michael@0:     // %esp_new = %esp_old + callee_params + saved_regs + locals + 4
michael@0:     program_string = "$eip .raSearchStart ^ = "
michael@0:         "$ebp $esp .cbCalleeParams + .cbSavedRegs + 8 - ^ = "
michael@0:         "$esp .raSearchStart 4 + =";
michael@0:   } else {
michael@0:     // The function corresponding to the last frame doesn't use %ebp at
michael@0:     // all.  The callee frame is located relative to %esp.
michael@0:     //
michael@0:     // The called procedure's instruction pointer and stack pointer are
michael@0:     // recovered in the same way as the case above, except that no
michael@0:     // frame pointer (%ebp) is used at all, so it is not saved anywhere
michael@0:     // in the callee's stack frame and does not need to be recovered.
michael@0:     // Because %ebp wasn't used in the callee, whatever value it has
michael@0:     // is the value that it had in the caller, so it can be carried
michael@0:     // straight through without bringing its validity into question.
michael@0:     //
michael@0:     // Because of the use of .raSearchStart, the stack will possibly be
michael@0:     // examined to locate a better return address after program string
michael@0:     // evaluation.  The stack will not be examined to locate a saved
michael@0:     // %ebp value, because these frames do not save (or use) %ebp.
michael@0:     //
michael@0:     // %eip_new = *(%esp_old + callee_params + saved_regs + locals)
michael@0:     // %esp_new = %esp_old + callee_params + saved_regs + locals + 4
michael@0:     // %ebp_new = %ebp_old
michael@0:     program_string = "$eip .raSearchStart ^ = "
michael@0:         "$esp .raSearchStart 4 + =";
michael@0:     recover_ebp = false;
michael@0:   }
michael@0: 
michael@0:   // Now crank it out, making sure that the program string set at least the
michael@0:   // two required variables.
michael@0:   PostfixEvaluator<uint32_t> evaluator =
michael@0:       PostfixEvaluator<uint32_t>(&dictionary, memory_);
michael@0:   PostfixEvaluator<uint32_t>::DictionaryValidityType dictionary_validity;
michael@0:   if (!evaluator.Evaluate(program_string, &dictionary_validity) ||
michael@0:       !dictionary_validity.have(ustr__ZSeip()) ||
michael@0:       !dictionary_validity.have(ustr__ZSesp())) {
michael@0:     // Program string evaluation failed. It may be that %eip is not somewhere
michael@0:     // with stack frame info, and %ebp is pointing to non-stack memory, so
michael@0:     // our evaluation couldn't succeed. We'll scan the stack for a return
michael@0:     // address. This can happen if the stack is in a module for which
michael@0:     // we don't have symbols, and that module is compiled without a
michael@0:     // frame pointer.
michael@0:     uint32_t location_start = last_frame->context.esp;
michael@0:     uint32_t location, eip;
michael@0:     if (!stack_scan_allowed
michael@0:         || !ScanForReturnAddress(location_start, &location, &eip)) {
michael@0:       // if we can't find an instruction pointer even with stack scanning,
michael@0:       // give up.
michael@0:       return NULL;
michael@0:     }
michael@0: 
michael@0:     // This seems like a reasonable return address. Since program string
michael@0:     // evaluation failed, use it and set %esp to the location above the
michael@0:     // one where the return address was found.
michael@0:     dictionary.set(ustr__ZSeip(), eip);
michael@0:     dictionary.set(ustr__ZSesp(), location + 4);
michael@0:     trust = StackFrame::FRAME_TRUST_SCAN;
michael@0:   }
michael@0: 
michael@0:   // Since this stack frame did not use %ebp in a traditional way,
michael@0:   // locating the return address isn't entirely deterministic. In that
michael@0:   // case, the stack can be scanned to locate the return address.
michael@0:   //
michael@0:   // However, if program string evaluation resulted in both %eip and
michael@0:   // %ebp values of 0, trust that the end of the stack has been
michael@0:   // reached and don't scan for anything else.
michael@0:   if (dictionary.get(ustr__ZSeip()) != 0 ||
michael@0:       dictionary.get(ustr__ZSebp()) != 0) {
michael@0:     int offset = 0;
michael@0: 
michael@0:     // This scan can only be done if a CodeModules object is available, to
michael@0:     // check that candidate return addresses are in fact inside a module.
michael@0:     //
michael@0:     // TODO(mmentovai): This ignores dynamically-generated code.  One possible
michael@0:     // solution is to check the minidump's memory map to see if the candidate
michael@0:     // %eip value comes from a mapped executable page, although this would
michael@0:     // require dumps that contain MINIDUMP_MEMORY_INFO, which the Breakpad
michael@0:     // client doesn't currently write (it would need to call MiniDumpWriteDump
michael@0:     // with the MiniDumpWithFullMemoryInfo type bit set).  Even given this
michael@0:     // ability, older OSes (pre-XP SP2) and CPUs (pre-P4) don't enforce
michael@0:     // an independent execute privilege on memory pages.
michael@0: 
michael@0:     uint32_t eip = dictionary.get(ustr__ZSeip());
michael@0:     if (modules_ && !modules_->GetModuleForAddress(eip)) {
michael@0:       // The instruction pointer at .raSearchStart was invalid, so start
michael@0:       // looking one 32-bit word above that location.
michael@0:       uint32_t location_start = dictionary.get(ustr__ZDraSearchStart()) + 4;
michael@0:       uint32_t location;
michael@0:       if (stack_scan_allowed
michael@0:           && ScanForReturnAddress(location_start, &location, &eip)) {
michael@0:         // This is a better return address that what program string
michael@0:         // evaluation found.  Use it, and set %esp to the location above the
michael@0:         // one where the return address was found.
michael@0:         dictionary.set(ustr__ZSeip(), eip);
michael@0:         dictionary.set(ustr__ZSesp(), location + 4);
michael@0:         offset = location - location_start;
michael@0:         trust = StackFrame::FRAME_TRUST_CFI_SCAN;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     if (recover_ebp) {
michael@0:       // When trying to recover the previous value of the frame pointer (%ebp),
michael@0:       // start looking at the lowest possible address in the saved-register
michael@0:       // area, and look at the entire saved register area, increased by the
michael@0:       // size of |offset| to account for additional data that may be on the
michael@0:       // stack.  The scan is performed from the highest possible address to
michael@0:       // the lowest, because the expectation is that the function's prolog
michael@0:       // would have saved %ebp early.
michael@0:       uint32_t ebp = dictionary.get(ustr__ZSebp());
michael@0: 
michael@0:       // When a scan for return address is used, it is possible to skip one or
michael@0:       // more frames (when return address is not in a known module).  One
michael@0:       // indication for skipped frames is when the value of %ebp is lower than
michael@0:       // the location of the return address on the stack
michael@0:       bool has_skipped_frames =
michael@0:         (trust != StackFrame::FRAME_TRUST_CFI && ebp <= raSearchStart + offset);
michael@0: 
michael@0:       uint32_t value;  // throwaway variable to check pointer validity
michael@0:       if (has_skipped_frames || !memory_->GetMemoryAtAddress(ebp, &value)) {
michael@0:         int fp_search_bytes = last_frame_info->saved_register_size + offset;
michael@0:         uint32_t location_end = last_frame->context.esp +
michael@0:                                  last_frame_callee_parameter_size;
michael@0: 
michael@0:         for (uint32_t location = location_end + fp_search_bytes;
michael@0:              location >= location_end;
michael@0:              location -= 4) {
michael@0:           if (!memory_->GetMemoryAtAddress(location, &ebp))
michael@0:             break;
michael@0: 
michael@0:           if (memory_->GetMemoryAtAddress(ebp, &value)) {
michael@0:             // The candidate value is a pointer to the same memory region
michael@0:             // (the stack).  Prefer it as a recovered %ebp result.
michael@0:             dictionary.set(ustr__ZSebp(), ebp);
michael@0:             break;
michael@0:           }
michael@0:         }
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Create a new stack frame (ownership will be transferred to the caller)
michael@0:   // and fill it in.
michael@0:   StackFrameX86* frame = new StackFrameX86();
michael@0: 
michael@0:   frame->trust = trust;
michael@0:   frame->context = last_frame->context;
michael@0:   frame->context.eip = dictionary.get(ustr__ZSeip());
michael@0:   frame->context.esp = dictionary.get(ustr__ZSesp());
michael@0:   frame->context.ebp = dictionary.get(ustr__ZSebp());
michael@0:   frame->context_validity = StackFrameX86::CONTEXT_VALID_EIP |
michael@0:                                 StackFrameX86::CONTEXT_VALID_ESP |
michael@0:                                 StackFrameX86::CONTEXT_VALID_EBP;
michael@0: 
michael@0:   // These are nonvolatile (callee-save) registers, and the program string
michael@0:   // may have filled them in.
michael@0:   if (dictionary_validity.have(ustr__ZSebx())) {
michael@0:     frame->context.ebx = dictionary.get(ustr__ZSebx());
michael@0:     frame->context_validity |= StackFrameX86::CONTEXT_VALID_EBX;
michael@0:   }
michael@0:   if (dictionary_validity.have(ustr__ZSesi())) {
michael@0:     frame->context.esi = dictionary.get(ustr__ZSesi());
michael@0:     frame->context_validity |= StackFrameX86::CONTEXT_VALID_ESI;
michael@0:   }
michael@0:   if (dictionary_validity.have(ustr__ZSedi())) {
michael@0:     frame->context.edi = dictionary.get(ustr__ZSedi());
michael@0:     frame->context_validity |= StackFrameX86::CONTEXT_VALID_EDI;
michael@0:   }
michael@0: 
michael@0:   return frame;
michael@0: }
michael@0: 
michael@0: StackFrameX86* StackwalkerX86::GetCallerByCFIFrameInfo(
michael@0:     const vector<StackFrame*> &frames,
michael@0:     CFIFrameInfo* cfi_frame_info) {
michael@0:   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
michael@0:   last_frame->cfi_frame_info = cfi_frame_info;
michael@0: 
michael@0:   scoped_ptr<StackFrameX86> frame(new StackFrameX86());
michael@0:   if (!cfi_walker_
michael@0:       .FindCallerRegisters(*memory_, *cfi_frame_info,
michael@0:                            last_frame->context, last_frame->context_validity,
michael@0:                            &frame->context, &frame->context_validity))
michael@0:     return NULL;
michael@0: 
michael@0:   // Make sure we recovered all the essentials.
michael@0:   static const int essentials = (StackFrameX86::CONTEXT_VALID_EIP
michael@0:                                  | StackFrameX86::CONTEXT_VALID_ESP
michael@0:                                  | StackFrameX86::CONTEXT_VALID_EBP);
michael@0:   if ((frame->context_validity & essentials) != essentials)
michael@0:     return NULL;
michael@0: 
michael@0:   frame->trust = StackFrame::FRAME_TRUST_CFI;
michael@0: 
michael@0:   return frame.release();
michael@0: }
michael@0: 
michael@0: StackFrameX86* StackwalkerX86::GetCallerByEBPAtBase(
michael@0:     const vector<StackFrame*> &frames,
michael@0:     bool stack_scan_allowed) {
michael@0:   StackFrame::FrameTrust trust;
michael@0:   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
michael@0:   uint32_t last_esp = last_frame->context.esp;
michael@0:   uint32_t last_ebp = last_frame->context.ebp;
michael@0: 
michael@0:   // Assume that the standard %ebp-using x86 calling convention is in
michael@0:   // use.
michael@0:   //
michael@0:   // The typical x86 calling convention, when frame pointers are present,
michael@0:   // is for the calling procedure to use CALL, which pushes the return
michael@0:   // address onto the stack and sets the instruction pointer (%eip) to
michael@0:   // the entry point of the called routine.  The called routine then
michael@0:   // PUSHes the calling routine's frame pointer (%ebp) onto the stack
michael@0:   // before copying the stack pointer (%esp) to the frame pointer (%ebp).
michael@0:   // Therefore, the calling procedure's frame pointer is always available
michael@0:   // by dereferencing the called procedure's frame pointer, and the return
michael@0:   // address is always available at the memory location immediately above
michael@0:   // the address pointed to by the called procedure's frame pointer.  The
michael@0:   // calling procedure's stack pointer (%esp) is 8 higher than the value
michael@0:   // of the called procedure's frame pointer at the time the calling
michael@0:   // procedure made the CALL: 4 bytes for the return address pushed by the
michael@0:   // CALL itself, and 4 bytes for the callee's PUSH of the caller's frame
michael@0:   // pointer.
michael@0:   //
michael@0:   // %eip_new = *(%ebp_old + 4)
michael@0:   // %esp_new = %ebp_old + 8
michael@0:   // %ebp_new = *(%ebp_old)
michael@0: 
michael@0:   uint32_t caller_eip, caller_esp, caller_ebp;
michael@0: 
michael@0:   if (memory_->GetMemoryAtAddress(last_ebp + 4, &caller_eip) &&
michael@0:       memory_->GetMemoryAtAddress(last_ebp, &caller_ebp)) {
michael@0:     caller_esp = last_ebp + 8;
michael@0:     trust = StackFrame::FRAME_TRUST_FP;
michael@0:   } else {
michael@0:     // We couldn't read the memory %ebp refers to. It may be that %ebp
michael@0:     // is pointing to non-stack memory. We'll scan the stack for a
michael@0:     // return address. This can happen if last_frame is executing code
michael@0:     // for a module for which we don't have symbols, and that module
michael@0:     // is compiled without a frame pointer.
michael@0:     if (!stack_scan_allowed
michael@0:         || !ScanForReturnAddress(last_esp, &caller_esp, &caller_eip)) {
michael@0:       // if we can't find an instruction pointer even with stack scanning,
michael@0:       // give up.
michael@0:       return NULL;
michael@0:     }
michael@0: 
michael@0:     // ScanForReturnAddress found a reasonable return address. Advance
michael@0:     // %esp to the location above the one where the return address was
michael@0:     // found. Assume that %ebp is unchanged.
michael@0:     caller_esp += 4;
michael@0:     caller_ebp = last_ebp;
michael@0: 
michael@0:     trust = StackFrame::FRAME_TRUST_SCAN;
michael@0:   }
michael@0: 
michael@0:   // Create a new stack frame (ownership will be transferred to the caller)
michael@0:   // and fill it in.
michael@0:   StackFrameX86* frame = new StackFrameX86();
michael@0: 
michael@0:   frame->trust = trust;
michael@0:   frame->context = last_frame->context;
michael@0:   frame->context.eip = caller_eip;
michael@0:   frame->context.esp = caller_esp;
michael@0:   frame->context.ebp = caller_ebp;
michael@0:   frame->context_validity = StackFrameX86::CONTEXT_VALID_EIP |
michael@0:                             StackFrameX86::CONTEXT_VALID_ESP |
michael@0:                             StackFrameX86::CONTEXT_VALID_EBP;
michael@0: 
michael@0:   return frame;
michael@0: }
michael@0: 
michael@0: StackFrame* StackwalkerX86::GetCallerFrame(const CallStack* stack,
michael@0:                                            bool stack_scan_allowed) {
michael@0:   if (!memory_ || !stack) {
michael@0:     BPLOG(ERROR) << "Can't get caller frame without memory or stack";
michael@0:     return NULL;
michael@0:   }
michael@0: 
michael@0:   const vector<StackFrame*> &frames = *stack->frames();
michael@0:   StackFrameX86* last_frame = static_cast<StackFrameX86*>(frames.back());
michael@0:   scoped_ptr<StackFrameX86> new_frame;
michael@0: 
michael@0:   // If the resolver has Windows stack walking information, use that.
michael@0:   WindowsFrameInfo* windows_frame_info
michael@0:       = frame_symbolizer_->FindWindowsFrameInfo(last_frame);
michael@0:   if (windows_frame_info)
michael@0:     new_frame.reset(GetCallerByWindowsFrameInfo(frames, windows_frame_info,
michael@0:                                                 stack_scan_allowed));
michael@0: 
michael@0:   // If the resolver has DWARF CFI information, use that.
michael@0:   if (!new_frame.get()) {
michael@0:     CFIFrameInfo* cfi_frame_info =
michael@0:         frame_symbolizer_->FindCFIFrameInfo(last_frame);
michael@0:     if (cfi_frame_info)
michael@0:       new_frame.reset(GetCallerByCFIFrameInfo(frames, cfi_frame_info));
michael@0:   }
michael@0: 
michael@0:   // Otherwise, hope that the program was using a traditional frame structure.
michael@0:   if (!new_frame.get())
michael@0:     new_frame.reset(GetCallerByEBPAtBase(frames, stack_scan_allowed));
michael@0: 
michael@0:   // If nothing worked, tell the caller.
michael@0:   if (!new_frame.get())
michael@0:     return NULL;
michael@0: 
michael@0:   // Treat an instruction address of 0 as end-of-stack.
michael@0:   if (new_frame->context.eip == 0)
michael@0:     return NULL;
michael@0: 
michael@0:   // If the new stack pointer is at a lower address than the old, then
michael@0:   // that's clearly incorrect. Treat this as end-of-stack to enforce
michael@0:   // progress and avoid infinite loops.
michael@0:   if (new_frame->context.esp <= last_frame->context.esp)
michael@0:     return NULL;
michael@0: 
michael@0:   // new_frame->context.eip is the return address, which is the instruction
michael@0:   // after the CALL that caused us to arrive at the callee. Set
michael@0:   // new_frame->instruction to one less than that, so it points within the
michael@0:   // CALL instruction. See StackFrame::instruction for details, and
michael@0:   // StackFrameAMD64::ReturnAddress.
michael@0:   new_frame->instruction = new_frame->context.eip - 1;
michael@0: 
michael@0:   return new_frame.release();
michael@0: }
michael@0: 
michael@0: }  // namespace google_breakpad