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.cc: Generic stackwalker.
31//
32// See stackwalker.h for documentation.
33//
34// Author: Mark Mentovai
35
36#include "google_breakpad/processor/stackwalker.h"
37
38#include <assert.h>
39
40#include "common/scoped_ptr.h"
41#include "google_breakpad/processor/call_stack.h"
42#include "google_breakpad/processor/code_module.h"
43#include "google_breakpad/processor/code_modules.h"
44#include "google_breakpad/processor/dump_context.h"
45#include "google_breakpad/processor/stack_frame.h"
46#include "google_breakpad/processor/stack_frame_symbolizer.h"
47#include "google_breakpad/processor/system_info.h"
48#include "processor/linked_ptr.h"
49#include "processor/logging.h"
50#include "processor/stackwalker_ppc.h"
51#include "processor/stackwalker_ppc64.h"
52#include "processor/stackwalker_sparc.h"
53#include "processor/stackwalker_x86.h"
54#include "processor/stackwalker_amd64.h"
55#include "processor/stackwalker_arm.h"
56#include "processor/stackwalker_arm64.h"
57#include "processor/stackwalker_mips.h"
58
59namespace google_breakpad {
60
61const int Stackwalker::kRASearchWords = 40;
62
63// This default is just a sanity check: a large enough value
64// that allow capturing unbounded recursion traces, yet provide a
65// guardrail against stack walking bugs. The stack walking invariants
66// guarantee that the unwinding process is strictly monotonic and
67// practically bounded by the size of the stack memory range.
68uint32_t Stackwalker::max_frames_ = 1 << 20; // 1M
69bool Stackwalker::max_frames_set_ = false;
70
71uint32_t Stackwalker::max_frames_scanned_ = 1 << 14; // 16k
72
73Stackwalker::Stackwalker(const SystemInfo* system_info,
74 MemoryRegion* memory,
75 const CodeModules* modules,
76 StackFrameSymbolizer* frame_symbolizer)
77 : system_info_(system_info),
78 memory_(memory),
79 modules_(modules),
80 unloaded_modules_(NULL),
81 frame_symbolizer_(frame_symbolizer) {
82 assert(frame_symbolizer_);
83}
84
85void InsertSpecialAttentionModule(
86 StackFrameSymbolizer::SymbolizerResult symbolizer_result,
87 const CodeModule* module,
88 vector<const CodeModule*>* modules) {
89 if (!module) {
90 return;
91 }
92 assert(symbolizer_result == StackFrameSymbolizer::kError ||
93 symbolizer_result == StackFrameSymbolizer::kWarningCorruptSymbols);
94 bool found = false;
95 vector<const CodeModule*>::iterator iter;
96 for (iter = modules->begin(); iter != modules->end(); ++iter) {
97 if (*iter == module) {
98 found = true;
99 break;
100 }
101 }
102 if (!found) {
103 BPLOG(INFO) << ((symbolizer_result == StackFrameSymbolizer::kError) ?
104 "Couldn't load symbols for: " :
105 "Detected corrupt symbols for: ")
106 << module->debug_file() << "|" << module->debug_identifier();
107 modules->push_back(module);
108 }
109}
110
111bool Stackwalker::Walk(
112 CallStack* stack,
113 vector<const CodeModule*>* modules_without_symbols,
114 vector<const CodeModule*>* modules_with_corrupt_symbols) {
115 BPLOG_IF(ERROR, !stack) << "Stackwalker::Walk requires |stack|";
116 assert(stack);
117 stack->Clear();
118
119 BPLOG_IF(ERROR, !modules_without_symbols) << "Stackwalker::Walk requires "
120 << "|modules_without_symbols|";
121 BPLOG_IF(ERROR, !modules_without_symbols) << "Stackwalker::Walk requires "
122 << "|modules_with_corrupt_symbols|";
123 assert(modules_without_symbols);
124 assert(modules_with_corrupt_symbols);
125
126 // Begin with the context frame, and keep getting callers until there are
127 // no more.
128
129 // Keep track of the number of scanned or otherwise dubious frames seen
130 // so far, as the caller may have set a limit.
131 uint32_t scanned_frames = 0;
132
133 // Take ownership of the pointer returned by GetContextFrame.
134 scoped_ptr<StackFrame> frame(GetContextFrame());
135
136 while (frame.get()) {
137 // frame already contains a good frame with properly set instruction and
138 // frame_pointer fields. The frame structure comes from either the
139 // context frame (above) or a caller frame (below).
140
141 std::deque<std::unique_ptr<StackFrame>> inlined_frames;
142 // Resolve the module information, if a module map was provided.
143 StackFrameSymbolizer::SymbolizerResult symbolizer_result =
144 frame_symbolizer_->FillSourceLineInfo(modules_, unloaded_modules_,
145 system_info_,
146 frame.get(), &inlined_frames);
147 switch (symbolizer_result) {
148 case StackFrameSymbolizer::kInterrupt:
149 BPLOG(INFO) << "Stack walk is interrupted.";
150 return false;
151 break;
152 case StackFrameSymbolizer::kError:
153 InsertSpecialAttentionModule(symbolizer_result, frame->module,
154 modules_without_symbols);
155 break;
156 case StackFrameSymbolizer::kWarningCorruptSymbols:
157 InsertSpecialAttentionModule(symbolizer_result, frame->module,
158 modules_with_corrupt_symbols);
159 break;
160 case StackFrameSymbolizer::kNoError:
161 break;
162 default:
163 assert(false);
164 break;
165 }
166
167 // Keep track of the number of dubious frames so far.
168 switch (frame.get()->trust) {
169 case StackFrame::FRAME_TRUST_NONE:
170 case StackFrame::FRAME_TRUST_SCAN:
171 case StackFrame::FRAME_TRUST_CFI_SCAN:
172 scanned_frames++;
173 break;
174 default:
175 break;
176 }
177 // Add all nested inlined frames belonging to this frame from the innermost
178 // frame to the outermost frame.
179 while (!inlined_frames.empty()) {
180 stack->frames_.push_back(inlined_frames.front().release());
181 inlined_frames.pop_front();
182 }
183 // Add the frame to the call stack. Relinquish the ownership claim
184 // over the frame, because the stack now owns it.
185 stack->frames_.push_back(frame.release());
186 if (stack->frames_.size() > max_frames_) {
187 // Only emit an error message in the case where the limit
188 // reached is the default limit, not set by the user.
189 if (!max_frames_set_)
190 BPLOG(ERROR) << "The stack is over " << max_frames_ << " frames.";
191 break;
192 }
193
194 // Get the next frame and take ownership.
195 bool stack_scan_allowed = scanned_frames < max_frames_scanned_;
196 frame.reset(GetCallerFrame(stack, stack_scan_allowed));
197 }
198
199 return true;
200}
201
202// static
203Stackwalker* Stackwalker::StackwalkerForCPU(
204 const SystemInfo* system_info,
205 DumpContext* context,
206 MemoryRegion* memory,
207 const CodeModules* modules,
208 const CodeModules* unloaded_modules,
209 StackFrameSymbolizer* frame_symbolizer) {
210 if (!context) {
211 BPLOG(ERROR) << "Can't choose a stackwalker implementation without context";
212 return NULL;
213 }
214
215 Stackwalker* cpu_stackwalker = NULL;
216
217 uint32_t cpu = context->GetContextCPU();
218 switch (cpu) {
219 case MD_CONTEXT_X86:
220 cpu_stackwalker = new StackwalkerX86(system_info,
221 context->GetContextX86(),
222 memory, modules, frame_symbolizer);
223 break;
224
225 case MD_CONTEXT_PPC:
226 cpu_stackwalker = new StackwalkerPPC(system_info,
227 context->GetContextPPC(),
228 memory, modules, frame_symbolizer);
229 break;
230
231 case MD_CONTEXT_PPC64:
232 cpu_stackwalker = new StackwalkerPPC64(system_info,
233 context->GetContextPPC64(),
234 memory, modules, frame_symbolizer);
235 break;
236
237 case MD_CONTEXT_AMD64:
238 cpu_stackwalker = new StackwalkerAMD64(system_info,
239 context->GetContextAMD64(),
240 memory, modules, frame_symbolizer);
241 break;
242
243 case MD_CONTEXT_SPARC:
244 cpu_stackwalker = new StackwalkerSPARC(system_info,
245 context->GetContextSPARC(),
246 memory, modules, frame_symbolizer);
247 break;
248
249 case MD_CONTEXT_MIPS:
250 case MD_CONTEXT_MIPS64:
251 cpu_stackwalker = new StackwalkerMIPS(system_info,
252 context->GetContextMIPS(),
253 memory, modules, frame_symbolizer);
254 break;
255
256 case MD_CONTEXT_ARM:
257 {
258 int fp_register = -1;
259 if (system_info->os_short == "ios")
260 fp_register = MD_CONTEXT_ARM_REG_IOS_FP;
261 cpu_stackwalker = new StackwalkerARM(system_info,
262 context->GetContextARM(),
263 fp_register, memory, modules,
264 frame_symbolizer);
265 break;
266 }
267
268 case MD_CONTEXT_ARM64:
269 cpu_stackwalker = new StackwalkerARM64(system_info,
270 context->GetContextARM64(),
271 memory, modules,
272 frame_symbolizer);
273 break;
274 }
275
276 BPLOG_IF(ERROR, !cpu_stackwalker) << "Unknown CPU type " << HexString(cpu) <<
277 ", can't choose a stackwalker "
278 "implementation";
279 if (cpu_stackwalker) {
280 cpu_stackwalker->unloaded_modules_ = unloaded_modules;
281 }
282 return cpu_stackwalker;
283}
284
285// CONSIDER: check stack alignment?
286bool Stackwalker::TerminateWalk(uint64_t caller_ip,
287 uint64_t caller_sp,
288 uint64_t callee_sp,
289 bool first_unwind) const {
290 // Treat an instruction address less than 4k as end-of-stack.
291 // (using InstructionAddressSeemsValid() here is very tempting,
292 // but we need to handle JITted code)
293 if (caller_ip < (1 << 12)) {
294 return true;
295 }
296
297 // NOTE: The stack address range is implicitly checked
298 // when the stack memory is accessed.
299
300 // The stack pointer should monotonically increase. For first unwind
301 // we allow caller_sp == callee_sp to account for architectures where
302 // the return address is stored in a register (so it's possible to have
303 // leaf functions which don't move the stack pointer)
304 if (first_unwind ? (caller_sp < callee_sp) : (caller_sp <= callee_sp)) {
305 return true;
306 }
307
308 return false;
309}
310
311bool Stackwalker::InstructionAddressSeemsValid(uint64_t address) const {
312 StackFrame frame;
313 frame.instruction = address;
314 StackFrameSymbolizer::SymbolizerResult symbolizer_result =
315 frame_symbolizer_->FillSourceLineInfo(modules_, unloaded_modules_,
316 system_info_, &frame, nullptr);
317
318 if (!frame.module) {
319 // not inside any loaded module
320 return false;
321 }
322
323 if (!frame_symbolizer_->HasImplementation()) {
324 // No valid implementation to symbolize stack frame, but the address is
325 // within a known module.
326 return true;
327 }
328
329 if (symbolizer_result != StackFrameSymbolizer::kNoError &&
330 symbolizer_result != StackFrameSymbolizer::kWarningCorruptSymbols) {
331 // Some error occurred during symbolization, but the address is within a
332 // known module
333 return true;
334 }
335
336 return !frame.function_name.empty();
337}
338
339} // namespace google_breakpad
340