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 <map>
44#include <string>
45#include <utility>
46
47#include "common/scoped_ptr.h"
48#include "common/using_std_string.h"
49#include "processor/module_factory.h"
50#include "processor/simple_serializer-inl.h"
51
52using std::map;
53using std::make_pair;
54
55namespace google_breakpad {
56
57FastSourceLineResolver::FastSourceLineResolver()
58  : SourceLineResolverBase(new FastModuleFactory) { }
59
60bool FastSourceLineResolver::ShouldDeleteMemoryBufferAfterLoadModule() {
61  return false;
62}
63
64void FastSourceLineResolver::Module::LookupAddress(StackFrame *frame) const {
65  MemAddr address = frame->instruction - frame->module->base_address();
66
67  // First, look for a FUNC record that covers address. Use
68  // RetrieveNearestRange instead of RetrieveRange so that, if there
69  // is no such function, we can use the next function to bound the
70  // extent of the PUBLIC symbol we find, below. This does mean we
71  // need to check that address indeed falls within the function we
72  // find; do the range comparison in an overflow-friendly way.
73  scoped_ptr<Function> func(new Function);
74  const Function* func_ptr = 0;
75  scoped_ptr<PublicSymbol> public_symbol(new PublicSymbol);
76  const PublicSymbol* public_symbol_ptr = 0;
77  MemAddr function_base;
78  MemAddr function_size;
79  MemAddr public_address;
80
81  if (functions_.RetrieveNearestRange(address, func_ptr,
82                                      &function_base, &function_size) &&
83      address >= function_base && address - function_base < function_size) {
84    func.get()->CopyFrom(func_ptr);
85    frame->function_name = func->name;
86    frame->function_base = frame->module->base_address() + function_base;
87
88    scoped_ptr<Line> line(new Line);
89    const Line* line_ptr = 0;
90    MemAddr line_base;
91    if (func->lines.RetrieveRange(address, line_ptr, &line_base, NULL)) {
92      line.get()->CopyFrom(line_ptr);
93      FileMap::iterator it = files_.find(line->source_file_id);
94      if (it != files_.end()) {
95        frame->source_file_name =
96            files_.find(line->source_file_id).GetValuePtr();
97      }
98      frame->source_line = line->line;
99      frame->source_line_base = frame->module->base_address() + line_base;
100    }
101  } else if (public_symbols_.Retrieve(address,
102                                      public_symbol_ptr, &public_address) &&
103             (!func_ptr || public_address > function_base)) {
104    public_symbol.get()->CopyFrom(public_symbol_ptr);
105    frame->function_name = public_symbol->name;
106    frame->function_base = frame->module->base_address() + public_address;
107  }
108}
109
110// WFI: WindowsFrameInfo.
111// Returns a WFI object reading from a raw memory chunk of data
112WindowsFrameInfo FastSourceLineResolver::CopyWFI(const char *raw) {
113  const WindowsFrameInfo::StackInfoTypes type =
114     static_cast<const WindowsFrameInfo::StackInfoTypes>(
115         *reinterpret_cast<const int32_t*>(raw));
116
117  // The first 8 bytes of int data are unused.
118  // They correspond to "StackInfoTypes type_;" and "int valid;"
119  // data member of WFI.
120  const uint32_t *para_uint32 = reinterpret_cast<const uint32_t*>(
121      raw + 2 * sizeof(int32_t));
122
123  uint32_t prolog_size = para_uint32[0];;
124  uint32_t epilog_size = para_uint32[1];
125  uint32_t parameter_size = para_uint32[2];
126  uint32_t saved_register_size = para_uint32[3];
127  uint32_t local_size = para_uint32[4];
128  uint32_t max_stack_size = para_uint32[5];
129  const char *boolean = reinterpret_cast<const char*>(para_uint32 + 6);
130  bool allocates_base_pointer = (*boolean != 0);
131  string program_string = boolean + 1;
132
133  return WindowsFrameInfo(type,
134                          prolog_size,
135                          epilog_size,
136                          parameter_size,
137                          saved_register_size,
138                          local_size,
139                          max_stack_size,
140                          allocates_base_pointer,
141                          program_string);
142}
143
144// Loads a map from the given buffer in char* type.
145// Does NOT take ownership of mem_buffer.
146// In addition, treat mem_buffer as const char*.
147bool FastSourceLineResolver::Module::LoadMapFromMemory(
148    char *memory_buffer,
149    size_t memory_buffer_size) {
150  if (!memory_buffer) return false;
151
152  // Read the "is_corrupt" flag.
153  const char *mem_buffer = memory_buffer;
154  mem_buffer = SimpleSerializer<bool>::Read(mem_buffer, &is_corrupt_);
155
156  const uint32_t *map_sizes = reinterpret_cast<const uint32_t*>(mem_buffer);
157
158  unsigned int header_size = kNumberMaps_ * sizeof(unsigned int);
159
160  // offsets[]: an array of offset addresses (with respect to mem_buffer),
161  // for each "Static***Map" component of Module.
162  // "Static***Map": static version of std::map or map wrapper, i.e., StaticMap,
163  // StaticAddressMap, StaticContainedRangeMap, and StaticRangeMap.
164  unsigned int offsets[kNumberMaps_];
165  offsets[0] = header_size;
166  for (int i = 1; i < kNumberMaps_; ++i) {
167    offsets[i] = offsets[i - 1] + map_sizes[i - 1];
168  }
169
170  // Use pointers to construct Static*Map data members in Module:
171  int map_id = 0;
172  files_ = StaticMap<int, char>(mem_buffer + offsets[map_id++]);
173  functions_ =
174      StaticRangeMap<MemAddr, Function>(mem_buffer + offsets[map_id++]);
175  public_symbols_ =
176      StaticAddressMap<MemAddr, PublicSymbol>(mem_buffer + offsets[map_id++]);
177  for (int i = 0; i < WindowsFrameInfo::STACK_INFO_LAST; ++i)
178    windows_frame_info_[i] =
179        StaticContainedRangeMap<MemAddr, char>(mem_buffer + offsets[map_id++]);
180
181  cfi_initial_rules_ =
182      StaticRangeMap<MemAddr, char>(mem_buffer + offsets[map_id++]);
183  cfi_delta_rules_ = StaticMap<MemAddr, char>(mem_buffer + offsets[map_id++]);
184
185  return true;
186}
187
188WindowsFrameInfo *FastSourceLineResolver::Module::FindWindowsFrameInfo(
189    const StackFrame *frame) const {
190  MemAddr address = frame->instruction - frame->module->base_address();
191  scoped_ptr<WindowsFrameInfo> result(new WindowsFrameInfo());
192
193  // We only know about WindowsFrameInfo::STACK_INFO_FRAME_DATA and
194  // WindowsFrameInfo::STACK_INFO_FPO. Prefer them in this order.
195  // WindowsFrameInfo::STACK_INFO_FRAME_DATA is the newer type that
196  // includes its own program string.
197  // WindowsFrameInfo::STACK_INFO_FPO is the older type
198  // corresponding to the FPO_DATA struct. See stackwalker_x86.cc.
199  const char* frame_info_ptr;
200  if ((windows_frame_info_[WindowsFrameInfo::STACK_INFO_FRAME_DATA]
201       .RetrieveRange(address, frame_info_ptr))
202      || (windows_frame_info_[WindowsFrameInfo::STACK_INFO_FPO]
203          .RetrieveRange(address, frame_info_ptr))) {
204    result->CopyFrom(CopyWFI(frame_info_ptr));
205    return result.release();
206  }
207
208  // Even without a relevant STACK line, many functions contain
209  // information about how much space their parameters consume on the
210  // stack. Use RetrieveNearestRange instead of RetrieveRange, so that
211  // we can use the function to bound the extent of the PUBLIC symbol,
212  // below. However, this does mean we need to check that ADDRESS
213  // falls within the retrieved function's range; do the range
214  // comparison in an overflow-friendly way.
215  scoped_ptr<Function> function(new Function);
216  const Function* function_ptr = 0;
217  MemAddr function_base, function_size;
218  if (functions_.RetrieveNearestRange(address, function_ptr,
219                                      &function_base, &function_size) &&
220      address >= function_base && address - function_base < function_size) {
221    function.get()->CopyFrom(function_ptr);
222    result->parameter_size = function->parameter_size;
223    result->valid |= WindowsFrameInfo::VALID_PARAMETER_SIZE;
224    return result.release();
225  }
226
227  // PUBLIC symbols might have a parameter size. Use the function we
228  // found above to limit the range the public symbol covers.
229  scoped_ptr<PublicSymbol> public_symbol(new PublicSymbol);
230  const PublicSymbol* public_symbol_ptr = 0;
231  MemAddr public_address;
232  if (public_symbols_.Retrieve(address, public_symbol_ptr, &public_address) &&
233      (!function_ptr || public_address > function_base)) {
234    public_symbol.get()->CopyFrom(public_symbol_ptr);
235    result->parameter_size = public_symbol->parameter_size;
236  }
237
238  return NULL;
239}
240
241CFIFrameInfo *FastSourceLineResolver::Module::FindCFIFrameInfo(
242    const StackFrame *frame) const {
243  MemAddr address = frame->instruction - frame->module->base_address();
244  MemAddr initial_base, initial_size;
245  const char* initial_rules = NULL;
246
247  // Find the initial rule whose range covers this address. That
248  // provides an initial set of register recovery rules. Then, walk
249  // forward from the initial rule's starting address to frame's
250  // instruction address, applying delta rules.
251  if (!cfi_initial_rules_.RetrieveRange(address, initial_rules,
252                                        &initial_base, &initial_size)) {
253    return NULL;
254  }
255
256  // Create a frame info structure, and populate it with the rules from
257  // the STACK CFI INIT record.
258  scoped_ptr<CFIFrameInfo> rules(new CFIFrameInfo());
259  if (!ParseCFIRuleSet(initial_rules, rules.get()))
260    return NULL;
261
262  // Find the first delta rule that falls within the initial rule's range.
263  StaticMap<MemAddr, char>::iterator delta =
264    cfi_delta_rules_.lower_bound(initial_base);
265
266  // Apply delta rules up to and including the frame's address.
267  while (delta != cfi_delta_rules_.end() && delta.GetKey() <= address) {
268    ParseCFIRuleSet(delta.GetValuePtr(), rules.get());
269    delta++;
270  }
271
272  return rules.release();
273}
274
275}  // namespace google_breakpad
276