1  // Copyright 2010 Google LLC
  2  //
  3  // Redistribution and use in source and binary forms, with or without
  4  // modification, are permitted provided that the following conditions are
  5  // met:
  6  //
  7  //     * Redistributions of source code must retain the above copyright
  8  // notice, this list of conditions and the following disclaimer.
  9  //     * Redistributions in binary form must reproduce the above
 10  // copyright notice, this list of conditions and the following disclaimer
 11  // in the documentation and/or other materials provided with the
 12  // distribution.
 13  //     * Neither the name of Google LLC nor the names of its
 14  // contributors may be used to endorse or promote products derived from
 15  // this software without specific prior written permission.
 16  //
 17  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 18  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 19  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 20  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 21  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 22  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 23  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 24  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 25  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 26  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 27  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 28  
 29  // stackwalker.cc: Generic stackwalker.
 30  //
 31  // See stackwalker.h for documentation.
 32  //
 33  // Author: Mark Mentovai
 34  
 35  #ifdef HAVE_CONFIG_H
 36  #include <config.h>  // Must come first
 37  #endif
 38  
 39  #include "google_breakpad/processor/stackwalker.h"
 40  
 41  #include <assert.h>
 42  
 43  #include "common/scoped_ptr.h"
 44  #include "google_breakpad/processor/call_stack.h"
 45  #include "google_breakpad/processor/code_module.h"
 46  #include "google_breakpad/processor/code_modules.h"
 47  #include "google_breakpad/processor/dump_context.h"
 48  #include "google_breakpad/processor/stack_frame.h"
 49  #include "google_breakpad/processor/stack_frame_symbolizer.h"
 50  #include "google_breakpad/processor/system_info.h"
 51  #include "processor/linked_ptr.h"
 52  #include "processor/logging.h"
 53  #include "processor/stackwalker_ppc.h"
 54  #include "processor/stackwalker_ppc64.h"
 55  #include "processor/stackwalker_sparc.h"
 56  #include "processor/stackwalker_x86.h"
 57  #include "processor/stackwalker_amd64.h"
 58  #include "processor/stackwalker_arm.h"
 59  #include "processor/stackwalker_arm64.h"
 60  #include "processor/stackwalker_mips.h"
 61  #include "processor/stackwalker_riscv.h"
 62  #include "processor/stackwalker_riscv64.h"
 63  
 64  namespace google_breakpad {
 65  
 66  const int Stackwalker::kRASearchWords = 40;
 67  
 68  // This default is just a sanity check: a large enough value
 69  // that allow capturing unbounded recursion traces, yet provide a
 70  // guardrail against stack walking bugs. The stack walking invariants
 71  // guarantee that the unwinding process is strictly monotonic and
 72  // practically bounded by the size of the stack memory range.
 73  uint32_t Stackwalker::max_frames_ = 1 << 20;  // 1M
 74  bool Stackwalker::max_frames_set_ = false;
 75  
 76  uint32_t Stackwalker::max_frames_scanned_ = 1 << 14;  // 16k
 77  
 78  Stackwalker::Stackwalker(const SystemInfo* system_info,
 79                           MemoryRegion* memory,
 80                           const CodeModules* modules,
 81                           StackFrameSymbolizer* frame_symbolizer)
 82      : system_info_(system_info),
 83        memory_(memory),
 84        modules_(modules),
 85        unloaded_modules_(NULL),
 86        frame_symbolizer_(frame_symbolizer) {
 87    assert(frame_symbolizer_);
 88  }
 89  
 90  void InsertSpecialAttentionModule(
 91      StackFrameSymbolizer::SymbolizerResult symbolizer_result,
 92      const CodeModule* module,
 93      vector<const CodeModule*>* modules) {
 94    if (!module) {
 95      return;
 96    }
 97    assert(symbolizer_result == StackFrameSymbolizer::kError ||
 98           symbolizer_result == StackFrameSymbolizer::kWarningCorruptSymbols);
 99    bool found = false;
100    vector<const CodeModule*>::iterator iter;
101    for (iter = modules->begin(); iter != modules->end(); ++iter) {
102      if (*iter == module) {
103        found = true;
104        break;
105      }
106    }
107    if (!found) {
108      BPLOG(INFO) << ((symbolizer_result == StackFrameSymbolizer::kError) ?
109                         "Couldn't load symbols for: " :
110                         "Detected corrupt symbols for: ")
111                  << module->debug_file() << "|" << module->debug_identifier();
112      modules->push_back(module);
113    }
114  }
115  
116  bool Stackwalker::Walk(
117      CallStack* stack,
118      vector<const CodeModule*>* modules_without_symbols,
119      vector<const CodeModule*>* modules_with_corrupt_symbols) {
120    BPLOG_IF(ERROR, !stack) << "Stackwalker::Walk requires |stack|";
121    assert(stack);
122    stack->Clear();
123  
124    BPLOG_IF(ERROR, !modules_without_symbols) << "Stackwalker::Walk requires "
125                                              << "|modules_without_symbols|";
126    BPLOG_IF(ERROR, !modules_without_symbols) << "Stackwalker::Walk requires "
127                                              << "|modules_with_corrupt_symbols|";
128    assert(modules_without_symbols);
129    assert(modules_with_corrupt_symbols);
130  
131    // Begin with the context frame, and keep getting callers until there are
132    // no more.
133  
134    // Keep track of the number of scanned or otherwise dubious frames seen
135    // so far, as the caller may have set a limit.
136    uint32_t scanned_frames = 0;
137  
138    // Take ownership of the pointer returned by GetContextFrame.
139    scoped_ptr<StackFrame> frame(GetContextFrame());
140  
141    while (frame.get()) {
142      // frame already contains a good frame with properly set instruction and
143      // frame_pointer fields.  The frame structure comes from either the
144      // context frame (above) or a caller frame (below).
145  
146      std::deque<std::unique_ptr<StackFrame>> inlined_frames;
147      // Resolve the module information, if a module map was provided.
148      StackFrameSymbolizer::SymbolizerResult symbolizer_result =
149          frame_symbolizer_->FillSourceLineInfo(modules_, unloaded_modules_,
150                                                system_info_,
151                                                frame.get(), &inlined_frames);
152      switch (symbolizer_result) {
153        case StackFrameSymbolizer::kInterrupt:
154          BPLOG(INFO) << "Stack walk is interrupted.";
155          return false;
156          break;
157        case StackFrameSymbolizer::kError:
158          InsertSpecialAttentionModule(symbolizer_result, frame->module,
159                                       modules_without_symbols);
160          break;
161        case StackFrameSymbolizer::kWarningCorruptSymbols:
162          InsertSpecialAttentionModule(symbolizer_result, frame->module,
163                                       modules_with_corrupt_symbols);
164          break;
165        case StackFrameSymbolizer::kNoError:
166          break;
167        default:
168          assert(false);
169          break;
170      }
171  
172      // Keep track of the number of dubious frames so far.
173      switch (frame.get()->trust) {
174         case StackFrame::FRAME_TRUST_NONE:
175         case StackFrame::FRAME_TRUST_SCAN:
176         case StackFrame::FRAME_TRUST_CFI_SCAN:
177           scanned_frames++;
178           break;
179        default:
180          break;
181      }
182      // Add all nested inlined frames belonging to this frame from the innermost
183      // frame to the outermost frame.
184      while (!inlined_frames.empty()) {
185        stack->frames_.push_back(inlined_frames.front().release());
186        inlined_frames.pop_front();
187      }
188      // Add the frame to the call stack.  Relinquish the ownership claim
189      // over the frame, because the stack now owns it.
190      stack->frames_.push_back(frame.release());
191      if (stack->frames_.size() > max_frames_) {
192        // Only emit an error message in the case where the limit
193        // reached is the default limit, not set by the user.
194        if (!max_frames_set_)
195          BPLOG(ERROR) << "The stack is over " << max_frames_ << " frames.";
196        break;
197      }
198  
199      // Get the next frame and take ownership.
200      bool stack_scan_allowed = scanned_frames < max_frames_scanned_;
201      frame.reset(GetCallerFrame(stack, stack_scan_allowed));
202    }
203  
204    return true;
205  }
206  
207  // static
208  Stackwalker* Stackwalker::StackwalkerForCPU(
209      const SystemInfo* system_info,
210      DumpContext* context,
211      MemoryRegion* memory,
212      const CodeModules* modules,
213      const CodeModules* unloaded_modules,
214      StackFrameSymbolizer* frame_symbolizer) {
215    if (!context) {
216      BPLOG(ERROR) << "Can't choose a stackwalker implementation without context";
217      return NULL;
218    }
219  
220    Stackwalker* cpu_stackwalker = NULL;
221  
222    uint32_t cpu = context->GetContextCPU();
223    switch (cpu) {
224      case MD_CONTEXT_X86:
225        cpu_stackwalker = new StackwalkerX86(system_info,
226                                             context->GetContextX86(),
227                                             memory, modules, frame_symbolizer);
228        break;
229  
230      case MD_CONTEXT_PPC:
231        cpu_stackwalker = new StackwalkerPPC(system_info,
232                                             context->GetContextPPC(),
233                                             memory, modules, frame_symbolizer);
234        break;
235  
236      case MD_CONTEXT_PPC64:
237        cpu_stackwalker = new StackwalkerPPC64(system_info,
238                                               context->GetContextPPC64(),
239                                               memory, modules, frame_symbolizer);
240        break;
241  
242      case MD_CONTEXT_AMD64:
243        cpu_stackwalker = new StackwalkerAMD64(system_info,
244                                               context->GetContextAMD64(),
245                                               memory, modules, frame_symbolizer);
246        break;
247  
248      case MD_CONTEXT_SPARC:
249        cpu_stackwalker = new StackwalkerSPARC(system_info,
250                                               context->GetContextSPARC(),
251                                               memory, modules, frame_symbolizer);
252        break;
253  
254      case MD_CONTEXT_MIPS:
255      case MD_CONTEXT_MIPS64:
256        cpu_stackwalker = new StackwalkerMIPS(system_info,
257                                              context->GetContextMIPS(),
258                                              memory, modules, frame_symbolizer);
259        break;
260  
261      case MD_CONTEXT_ARM:
262      {
263        int fp_register = -1;
264        if (system_info->os_short == "ios")
265          fp_register = MD_CONTEXT_ARM_REG_IOS_FP;
266        cpu_stackwalker = new StackwalkerARM(system_info,
267                                             context->GetContextARM(),
268                                             fp_register, memory, modules,
269                                             frame_symbolizer);
270        break;
271      }
272  
273      case MD_CONTEXT_ARM64:
274        cpu_stackwalker = new StackwalkerARM64(system_info,
275                                               context->GetContextARM64(),
276                                               memory, modules,
277                                               frame_symbolizer);
278        break;
279  
280      case MD_CONTEXT_RISCV:
281        cpu_stackwalker = new StackwalkerRISCV(system_info,
282                                               context->GetContextRISCV(),
283                                               memory, modules,
284                                               frame_symbolizer);
285        break;
286  
287      case MD_CONTEXT_RISCV64:
288        cpu_stackwalker = new StackwalkerRISCV64(system_info,
289                                                 context->GetContextRISCV64(),
290                                                 memory, modules,
291                                                 frame_symbolizer);
292        break;
293    }
294  
295    BPLOG_IF(ERROR, !cpu_stackwalker) << "Unknown CPU type " << HexString(cpu) <<
296                                         ", can't choose a stackwalker "
297                                         "implementation";
298    if (cpu_stackwalker) {
299      cpu_stackwalker->unloaded_modules_ = unloaded_modules;
300    }
301    return cpu_stackwalker;
302  }
303  
304  // CONSIDER: check stack alignment?
305  bool Stackwalker::TerminateWalk(uint64_t caller_ip,
306                                  uint64_t caller_sp,
307                                  uint64_t callee_sp,
308                                  bool first_unwind) const {
309    // Treat an instruction address less than 4k as end-of-stack.
310    // (using InstructionAddressSeemsValid() here is very tempting,
311    // but we need to handle JITted code)
312    if (caller_ip < (1 << 12)) {
313      return true;
314    }
315  
316    // NOTE: The stack address range is implicitly checked
317    //   when the stack memory is accessed.
318  
319    // The stack pointer should monotonically increase. For first unwind
320    // we allow caller_sp == callee_sp to account for architectures where
321    // the return address is stored in a register (so it's possible to have
322    // leaf functions which don't move the stack pointer)
323    if (first_unwind ? (caller_sp < callee_sp) : (caller_sp <= callee_sp)) {
324      return true;
325    }
326  
327    return false;
328  }
329  
330  bool Stackwalker::InstructionAddressSeemsValid(uint64_t address) const {
331    StackFrame frame;
332    frame.instruction = address;
333    StackFrameSymbolizer::SymbolizerResult symbolizer_result =
334        frame_symbolizer_->FillSourceLineInfo(modules_, unloaded_modules_,
335                                              system_info_, &frame, nullptr);
336  
337    if (!frame.module) {
338      // not inside any loaded module
339      return false;
340    }
341  
342    if (!frame_symbolizer_->HasImplementation()) {
343      // No valid implementation to symbolize stack frame, but the address is
344      // within a known module.
345      return true;
346    }
347  
348    if (symbolizer_result != StackFrameSymbolizer::kNoError &&
349        symbolizer_result != StackFrameSymbolizer::kWarningCorruptSymbols) {
350      // Some error occurred during symbolization, but the address is within a
351      // known module
352      return true;
353    }
354  
355    return !frame.function_name.empty();
356  }
357  
358  }  // namespace google_breakpad