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// fast_source_line_resolver.cc: FastSourceLineResolver is a concrete class that
31// implements SourceLineResolverInterface. Both FastSourceLineResolver and
32// BasicSourceLineResolver inherit from SourceLineResolverBase class to reduce
33// code redundancy.
34//
35// See fast_source_line_resolver.h and fast_source_line_resolver_types.h
36// for more documentation.
37//
38// Author: Siyang Xie (lambxsy@google.com)
39
40#include "google_breakpad/processor/fast_source_line_resolver.h"
41#include "processor/fast_source_line_resolver_types.h"
42
43#include <cassert>
44#include <map>
45#include <string>
46#include <utility>
47
48#include "common/scoped_ptr.h"
49#include "common/using_std_string.h"
50#include "processor/logging.h"
51#include "processor/module_factory.h"
52#include "processor/simple_serializer-inl.h"
53
54using std::deque;
55using std::unique_ptr;
56
57namespace google_breakpad {
58
59FastSourceLineResolver::FastSourceLineResolver()
60 : SourceLineResolverBase(new FastModuleFactory) { }
61
62bool FastSourceLineResolver::ShouldDeleteMemoryBufferAfterLoadModule() {
63 return false;
64}
65
66void FastSourceLineResolver::Module::LookupAddress(
67 StackFrame* frame,
68 std::deque<std::unique_ptr<StackFrame>>* inlined_frames) const {
69 MemAddr address = frame->instruction - frame->module->base_address();
70
71 // First, look for a FUNC record that covers address. Use
72 // RetrieveNearestRange instead of RetrieveRange so that, if there
73 // is no such function, we can use the next function to bound the
74 // extent of the PUBLIC symbol we find, below. This does mean we
75 // need to check that address indeed falls within the function we
76 // find; do the range comparison in an overflow-friendly way.
77 scoped_ptr<Function> func(new Function);
78 const Function* func_ptr = 0;
79 scoped_ptr<PublicSymbol> public_symbol(new PublicSymbol);
80 const PublicSymbol* public_symbol_ptr = 0;
81 MemAddr function_base;
82 MemAddr function_size;
83 MemAddr public_address;
84
85 if (functions_.RetrieveNearestRange(address, func_ptr,
86 &function_base, &function_size) &&
87 address >= function_base && address - function_base < function_size) {
88 func->CopyFrom(func_ptr);
89 frame->function_name = func->name;
90 frame->function_base = frame->module->base_address() + function_base;
91 frame->is_multiple = func->is_multiple;
92
93 scoped_ptr<Line> line(new Line);
94 const Line* line_ptr = 0;
95 MemAddr line_base;
96 if (func->lines.RetrieveRange(address, line_ptr, &line_base, NULL)) {
97 line->CopyFrom(line_ptr);
98 FileMap::iterator it = files_.find(line->source_file_id);
99 if (it != files_.end()) {
100 frame->source_file_name =
101 files_.find(line->source_file_id).GetValuePtr();
102 }
103 frame->source_line = line->line;
104 frame->source_line_base = frame->module->base_address() + line_base;
105 }
106 // Check if this is inlined function call.
107 if (inlined_frames) {
108 ConstructInlineFrames(frame, address, func->inlines, inlined_frames);
109 }
110 } else if (public_symbols_.Retrieve(address,
111 public_symbol_ptr, &public_address) &&
112 (!func_ptr || public_address > function_base)) {
113 public_symbol->CopyFrom(public_symbol_ptr);
114 frame->function_name = public_symbol->name;
115 frame->function_base = frame->module->base_address() + public_address;
116 frame->is_multiple = public_symbol->is_multiple;
117 }
118}
119
120void FastSourceLineResolver::Module::ConstructInlineFrames(
121 StackFrame* frame,
122 MemAddr address,
123 const StaticContainedRangeMap<MemAddr, char>& inline_map,
124 std::deque<std::unique_ptr<StackFrame>>* inlined_frames) const {
125 std::vector<const char*> inline_ptrs;
126 if (!inline_map.RetrieveRanges(address, inline_ptrs)) {
127 return;
128 }
129
130 for (const char* inline_ptr : inline_ptrs) {
131 scoped_ptr<Inline> in(new Inline);
132 in->CopyFrom(inline_ptr);
133 unique_ptr<StackFrame> new_frame =
134 unique_ptr<StackFrame>(new StackFrame(*frame));
135 auto origin_iter = inline_origins_.find(in->origin_id);
136 if (origin_iter != inline_origins_.end()) {
137 scoped_ptr<InlineOrigin> origin(new InlineOrigin);
138 origin->CopyFrom(origin_iter.GetValuePtr());
139 new_frame->function_name = origin->name;
140 } else {
141 new_frame->function_name = "<name omitted>";
142 }
143
144 // Store call site file and line in current frame, which will be updated
145 // later.
146 new_frame->source_line = in->call_site_line;
147 if (in->has_call_site_file_id) {
148 auto file_iter = files_.find(in->call_site_file_id);
149 if (file_iter != files_.end()) {
150 new_frame->source_file_name = file_iter.GetValuePtr();
151 }
152 }
153
154 // Use the starting adress of the inlined range as inlined function base.
155 new_frame->function_base = new_frame->module->base_address();
156 for (const auto& range : in->inline_ranges) {
157 if (address >= range.first && address < range.first + range.second) {
158 new_frame->function_base += range.first;
159 break;
160 }
161 }
162 new_frame->trust = StackFrame::FRAME_TRUST_INLINE;
163
164 // The inlines vector has an order from innermost entry to outermost entry.
165 // By push_back, we will have inlined_frames with the same order.
166 inlined_frames->push_back(std::move(new_frame));
167 }
168
169 // Update the source file and source line for each inlined frame.
170 if (!inlined_frames->empty()) {
171 string parent_frame_source_file_name = frame->source_file_name;
172 int parent_frame_source_line = frame->source_line;
173 frame->source_file_name = inlined_frames->back()->source_file_name;
174 frame->source_line = inlined_frames->back()->source_line;
175 for (unique_ptr<StackFrame>& inlined_frame : *inlined_frames) {
176 std::swap(inlined_frame->source_file_name, parent_frame_source_file_name);
177 std::swap(inlined_frame->source_line, parent_frame_source_line);
178 }
179 }
180}
181
182// WFI: WindowsFrameInfo.
183// Returns a WFI object reading from a raw memory chunk of data
184WindowsFrameInfo FastSourceLineResolver::CopyWFI(const char* raw) {
185 const WindowsFrameInfo::StackInfoTypes type =
186 static_cast<const WindowsFrameInfo::StackInfoTypes>(
187 *reinterpret_cast<const int32_t*>(raw));
188
189 // The first 8 bytes of int data are unused.
190 // They correspond to "StackInfoTypes type_;" and "int valid;"
191 // data member of WFI.
192 const uint32_t* para_uint32 = reinterpret_cast<const uint32_t*>(
193 raw + 2 * sizeof(int32_t));
194
195 uint32_t prolog_size = para_uint32[0];;
196 uint32_t epilog_size = para_uint32[1];
197 uint32_t parameter_size = para_uint32[2];
198 uint32_t saved_register_size = para_uint32[3];
199 uint32_t local_size = para_uint32[4];
200 uint32_t max_stack_size = para_uint32[5];
201 const char* boolean = reinterpret_cast<const char*>(para_uint32 + 6);
202 bool allocates_base_pointer = (*boolean != 0);
203 string program_string = boolean + 1;
204
205 return WindowsFrameInfo(type,
206 prolog_size,
207 epilog_size,
208 parameter_size,
209 saved_register_size,
210 local_size,
211 max_stack_size,
212 allocates_base_pointer,
213 program_string);
214}
215
216// Loads a map from the given buffer in char* type.
217// Does NOT take ownership of mem_buffer.
218// In addition, treat mem_buffer as const char*.
219bool FastSourceLineResolver::Module::LoadMapFromMemory(
220 char* memory_buffer,
221 size_t memory_buffer_size) {
222 if (!memory_buffer) return false;
223
224 // Read the "is_corrupt" flag.
225 const char* mem_buffer = memory_buffer;
226 mem_buffer = SimpleSerializer<bool>::Read(mem_buffer, &is_corrupt_);
227
228 const uint32_t* map_sizes = reinterpret_cast<const uint32_t*>(mem_buffer);
229
230 unsigned int header_size = kNumberMaps_ * sizeof(unsigned int);
231
232 // offsets[]: an array of offset addresses (with respect to mem_buffer),
233 // for each "Static***Map" component of Module.
234 // "Static***Map": static version of std::map or map wrapper, i.e., StaticMap,
235 // StaticAddressMap, StaticContainedRangeMap, and StaticRangeMap.
236 unsigned int offsets[kNumberMaps_];
237 offsets[0] = header_size;
238 for (int i = 1; i < kNumberMaps_; ++i) {
239 offsets[i] = offsets[i - 1] + map_sizes[i - 1];
240 }
241 unsigned int expected_size = sizeof(bool) + offsets[kNumberMaps_ - 1] +
242 map_sizes[kNumberMaps_ - 1] + 1;
243 if (expected_size != memory_buffer_size &&
244 // Allow for having an extra null terminator.
245 expected_size != memory_buffer_size - 1) {
246 // This could either be a random corruption or the serialization format was
247 // changed without updating the version in kSerializedBreakpadFileExtension.
248 BPLOG(ERROR) << "Memory buffer is either corrupt or an unsupported version"
249 << ", expected size: " << expected_size
250 << ", actual size: " << memory_buffer_size;
251 return false;
252 }
253 BPLOG(INFO) << "Memory buffer size looks good, size: " << memory_buffer_size;
254
255 // Use pointers to construct Static*Map data members in Module:
256 int map_id = 0;
257 files_ = StaticMap<int, char>(mem_buffer + offsets[map_id++]);
258 functions_ =
259 StaticRangeMap<MemAddr, Function>(mem_buffer + offsets[map_id++]);
260 public_symbols_ =
261 StaticAddressMap<MemAddr, PublicSymbol>(mem_buffer + offsets[map_id++]);
262 for (int i = 0; i < WindowsFrameInfo::STACK_INFO_LAST; ++i) {
263 windows_frame_info_[i] =
264 StaticContainedRangeMap<MemAddr, char>(mem_buffer + offsets[map_id++]);
265 }
266
267 cfi_initial_rules_ =
268 StaticRangeMap<MemAddr, char>(mem_buffer + offsets[map_id++]);
269 cfi_delta_rules_ = StaticMap<MemAddr, char>(mem_buffer + offsets[map_id++]);
270 inline_origins_ = StaticMap<int, char>(mem_buffer + offsets[map_id++]);
271 return true;
272}
273
274WindowsFrameInfo* FastSourceLineResolver::Module::FindWindowsFrameInfo(
275 const StackFrame* frame) const {
276 MemAddr address = frame->instruction - frame->module->base_address();
277 scoped_ptr<WindowsFrameInfo> result(new WindowsFrameInfo());
278
279 // We only know about WindowsFrameInfo::STACK_INFO_FRAME_DATA and
280 // WindowsFrameInfo::STACK_INFO_FPO. Prefer them in this order.
281 // WindowsFrameInfo::STACK_INFO_FRAME_DATA is the newer type that
282 // includes its own program string.
283 // WindowsFrameInfo::STACK_INFO_FPO is the older type
284 // corresponding to the FPO_DATA struct. See stackwalker_x86.cc.
285 const char* frame_info_ptr;
286 if ((windows_frame_info_[WindowsFrameInfo::STACK_INFO_FRAME_DATA]
287 .RetrieveRange(address, frame_info_ptr))
288 || (windows_frame_info_[WindowsFrameInfo::STACK_INFO_FPO]
289 .RetrieveRange(address, frame_info_ptr))) {
290 result->CopyFrom(CopyWFI(frame_info_ptr));
291 return result.release();
292 }
293
294 // Even without a relevant STACK line, many functions contain
295 // information about how much space their parameters consume on the
296 // stack. Use RetrieveNearestRange instead of RetrieveRange, so that
297 // we can use the function to bound the extent of the PUBLIC symbol,
298 // below. However, this does mean we need to check that ADDRESS
299 // falls within the retrieved function's range; do the range
300 // comparison in an overflow-friendly way.
301 scoped_ptr<Function> function(new Function);
302 const Function* function_ptr = 0;
303 MemAddr function_base, function_size;
304 if (functions_.RetrieveNearestRange(address, function_ptr,
305 &function_base, &function_size) &&
306 address >= function_base && address - function_base < function_size) {
307 function->CopyFrom(function_ptr);
308 result->parameter_size = function->parameter_size;
309 result->valid |= WindowsFrameInfo::VALID_PARAMETER_SIZE;
310 return result.release();
311 }
312
313 // PUBLIC symbols might have a parameter size. Use the function we
314 // found above to limit the range the public symbol covers.
315 scoped_ptr<PublicSymbol> public_symbol(new PublicSymbol);
316 const PublicSymbol* public_symbol_ptr = 0;
317 MemAddr public_address;
318 if (public_symbols_.Retrieve(address, public_symbol_ptr, &public_address) &&
319 (!function_ptr || public_address > function_base)) {
320 public_symbol->CopyFrom(public_symbol_ptr);
321 result->parameter_size = public_symbol->parameter_size;
322 }
323
324 return NULL;
325}
326
327CFIFrameInfo* FastSourceLineResolver::Module::FindCFIFrameInfo(
328 const StackFrame* frame) const {
329 MemAddr address = frame->instruction - frame->module->base_address();
330 MemAddr initial_base, initial_size;
331 const char* initial_rules = NULL;
332
333 // Find the initial rule whose range covers this address. That
334 // provides an initial set of register recovery rules. Then, walk
335 // forward from the initial rule's starting address to frame's
336 // instruction address, applying delta rules.
337 if (!cfi_initial_rules_.RetrieveRange(address, initial_rules,
338 &initial_base, &initial_size)) {
339 return NULL;
340 }
341
342 // Create a frame info structure, and populate it with the rules from
343 // the STACK CFI INIT record.
344 scoped_ptr<CFIFrameInfo> rules(new CFIFrameInfo());
345 if (!ParseCFIRuleSet(initial_rules, rules.get()))
346 return NULL;
347
348 // Find the first delta rule that falls within the initial rule's range.
349 StaticMap<MemAddr, char>::iterator delta =
350 cfi_delta_rules_.lower_bound(initial_base);
351
352 // Apply delta rules up to and including the frame's address.
353 while (delta != cfi_delta_rules_.end() && delta.GetKey() <= address) {
354 ParseCFIRuleSet(delta.GetValuePtr(), rules.get());
355 delta++;
356 }
357
358 return rules.release();
359}
360
361} // namespace google_breakpad
362