1// Copyright (c) 2011 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// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
31
32// module.cc: Implement google_breakpad::Module. See module.h.
33
34#include "common/module.h"
35#include "common/string_view.h"
36
37#include <assert.h>
38#include <errno.h>
39#include <stdio.h>
40#include <string.h>
41
42#include <functional>
43#include <iostream>
44#include <memory>
45#include <utility>
46
47namespace google_breakpad {
48
49using std::dec;
50using std::hex;
51using std::unique_ptr;
52
53Module::InlineOrigin* Module::InlineOriginMap::GetOrCreateInlineOrigin(
54 uint64_t offset,
55 StringView name) {
56 uint64_t specification_offset = references_[offset];
57 // Find the root offset.
58 auto iter = references_.find(specification_offset);
59 while (iter != references_.end() &&
60 specification_offset != references_[specification_offset]) {
61 specification_offset = references_[specification_offset];
62 iter = references_.find(specification_offset);
63 }
64 if (inline_origins_.find(specification_offset) != inline_origins_.end()) {
65 if (inline_origins_[specification_offset]->name == "<name omitted>") {
66 inline_origins_[specification_offset]->name = name;
67 }
68 return inline_origins_[specification_offset];
69 }
70 inline_origins_[specification_offset] = new Module::InlineOrigin(name);
71 return inline_origins_[specification_offset];
72}
73
74void Module::InlineOriginMap::SetReference(uint64_t offset,
75 uint64_t specification_offset) {
76 // If we haven't seen this doesn't exist in reference map, always add it.
77 if (references_.find(offset) == references_.end()) {
78 references_[offset] = specification_offset;
79 return;
80 }
81 // If offset equals specification_offset and offset exists in
82 // references_, there is no need to update the references_ map.
83 // This early return is necessary because the call to erase in following if
84 // will remove the entry of specification_offset in inline_origins_. If
85 // specification_offset equals to references_[offset], it might be
86 // duplicate debug info.
87 if (offset == specification_offset ||
88 specification_offset == references_[offset])
89 return;
90
91 // Fix up mapping in inline_origins_.
92 auto remove = inline_origins_.find(references_[offset]);
93 if (remove != inline_origins_.end()) {
94 inline_origins_[specification_offset] = std::move(remove->second);
95 inline_origins_.erase(remove);
96 }
97 references_[offset] = specification_offset;
98}
99
100Module::Module(const string& name, const string& os,
101 const string& architecture, const string& id,
102 const string& code_id /* = "" */) :
103 name_(name),
104 os_(os),
105 architecture_(architecture),
106 id_(id),
107 code_id_(code_id),
108 load_address_(0) { }
109
110Module::~Module() {
111 for (FileByNameMap::iterator it = files_.begin(); it != files_.end(); ++it)
112 delete it->second;
113 for (FunctionSet::iterator it = functions_.begin();
114 it != functions_.end(); ++it) {
115 delete *it;
116 }
117 for (vector<StackFrameEntry*>::iterator it = stack_frame_entries_.begin();
118 it != stack_frame_entries_.end(); ++it) {
119 delete *it;
120 }
121 for (ExternSet::iterator it = externs_.begin(); it != externs_.end(); ++it)
122 delete *it;
123}
124
125void Module::SetLoadAddress(Address address) {
126 load_address_ = address;
127}
128
129void Module::SetAddressRanges(const vector<Range>& ranges) {
130 address_ranges_ = ranges;
131}
132
133bool Module::AddFunction(Function* function) {
134 // FUNC lines must not hold an empty name, so catch the problem early if
135 // callers try to add one.
136 assert(!function->name.empty());
137
138 if (!AddressIsInModule(function->address)) {
139 return false;
140 }
141
142 // FUNCs are better than PUBLICs as they come with sizes, so remove an extern
143 // with the same address if present.
144 Extern ext(function->address);
145 ExternSet::iterator it_ext = externs_.find(&ext);
146 if (it_ext == externs_.end() &&
147 architecture_ == "arm" &&
148 (function->address & 0x1) == 0) {
149 // ARM THUMB functions have bit 0 set. ARM64 does not have THUMB.
150 Extern arm_thumb_ext(function->address | 0x1);
151 it_ext = externs_.find(&arm_thumb_ext);
152 }
153 if (it_ext != externs_.end()) {
154 delete *it_ext;
155 externs_.erase(it_ext);
156 }
157#if _DEBUG
158 {
159 // There should be no other PUBLIC symbols that overlap with the function.
160 for (const Range& range : function->ranges) {
161 Extern debug_ext(range.address);
162 ExternSet::iterator it_debug = externs_.lower_bound(&ext);
163 assert(it_debug == externs_.end() ||
164 (*it_debug)->address >= range.address + range.size);
165 }
166 }
167#endif
168
169 std::pair<FunctionSet::iterator,bool> ret = functions_.insert(function);
170 if (!ret.second && (*ret.first != function)) {
171 // Free the duplicate that was not inserted because this Module
172 // now owns it.
173 return false;
174 }
175 return true;
176}
177
178void Module::AddStackFrameEntry(StackFrameEntry* stack_frame_entry) {
179 if (!AddressIsInModule(stack_frame_entry->address)) {
180 return;
181 }
182
183 stack_frame_entries_.push_back(stack_frame_entry);
184}
185
186void Module::AddExtern(Extern* ext) {
187 if (!AddressIsInModule(ext->address)) {
188 return;
189 }
190
191 std::pair<ExternSet::iterator,bool> ret = externs_.insert(ext);
192 if (!ret.second) {
193 // Free the duplicate that was not inserted because this Module
194 // now owns it.
195 delete ext;
196 }
197}
198
199void Module::GetFunctions(vector<Function*>* vec,
200 vector<Function*>::iterator i) {
201 vec->insert(i, functions_.begin(), functions_.end());
202}
203
204void Module::GetExterns(vector<Extern*>* vec,
205 vector<Extern*>::iterator i) {
206 vec->insert(i, externs_.begin(), externs_.end());
207}
208
209Module::File* Module::FindFile(const string& name) {
210 // A tricky bit here. The key of each map entry needs to be a
211 // pointer to the entry's File's name string. This means that we
212 // can't do the initial lookup with any operation that would create
213 // an empty entry for us if the name isn't found (like, say,
214 // operator[] or insert do), because such a created entry's key will
215 // be a pointer the string passed as our argument. Since the key of
216 // a map's value type is const, we can't fix it up once we've
217 // created our file. lower_bound does the lookup without doing an
218 // insertion, and returns a good hint iterator to pass to insert.
219 // Our "destiny" is where we belong, whether we're there or not now.
220 FileByNameMap::iterator destiny = files_.lower_bound(&name);
221 if (destiny == files_.end()
222 || *destiny->first != name) { // Repeated string comparison, boo hoo.
223 File* file = new File(name);
224 file->source_id = -1;
225 destiny = files_.insert(destiny,
226 FileByNameMap::value_type(&file->name, file));
227 }
228 return destiny->second;
229}
230
231Module::File* Module::FindFile(const char* name) {
232 string name_string = name;
233 return FindFile(name_string);
234}
235
236Module::File* Module::FindExistingFile(const string& name) {
237 FileByNameMap::iterator it = files_.find(&name);
238 return (it == files_.end()) ? NULL : it->second;
239}
240
241void Module::GetFiles(vector<File*>* vec) {
242 vec->clear();
243 for (FileByNameMap::iterator it = files_.begin(); it != files_.end(); ++it)
244 vec->push_back(it->second);
245}
246
247void Module::GetStackFrameEntries(vector<StackFrameEntry*>* vec) const {
248 *vec = stack_frame_entries_;
249}
250
251void Module::AssignSourceIds(
252 set<InlineOrigin*, InlineOriginCompare>& inline_origins) {
253 // First, give every source file an id of -1.
254 for (FileByNameMap::iterator file_it = files_.begin();
255 file_it != files_.end(); ++file_it) {
256 file_it->second->source_id = -1;
257 }
258
259 // Next, mark all files actually cited by our functions' line number
260 // info, by setting each one's source id to zero.
261 for (FunctionSet::const_iterator func_it = functions_.begin();
262 func_it != functions_.end(); ++func_it) {
263 Function* func = *func_it;
264 for (vector<Line>::iterator line_it = func->lines.begin();
265 line_it != func->lines.end(); ++line_it)
266 line_it->file->source_id = 0;
267 }
268
269 // Also mark all files cited by inline callsite by setting each one's source
270 // id to zero.
271 auto markInlineFiles = [](unique_ptr<Inline>& in) {
272 // There are some artificial inline functions which don't belong to
273 // any file. Those will have file id -1.
274 if (in->call_site_file) {
275 in->call_site_file->source_id = 0;
276 }
277 };
278 for (auto func : functions_) {
279 Inline::InlineDFS(func->inlines, markInlineFiles);
280 }
281
282 // Finally, assign source ids to those files that have been marked.
283 // We could have just assigned source id numbers while traversing
284 // the line numbers, but doing it this way numbers the files in
285 // lexicographical order by name, which is neat.
286 int next_source_id = 0;
287 for (FileByNameMap::iterator file_it = files_.begin();
288 file_it != files_.end(); ++file_it) {
289 if (!file_it->second->source_id)
290 file_it->second->source_id = next_source_id++;
291 }
292}
293
294void Module::CreateInlineOrigins(
295 set<InlineOrigin*, InlineOriginCompare>& inline_origins) {
296 // Only add origins that have file and deduplicate origins with same name and
297 // file id by doing a DFS.
298 auto addInlineOrigins = [&](unique_ptr<Inline>& in) {
299 auto it = inline_origins.find(in->origin);
300 if (it == inline_origins.end())
301 inline_origins.insert(in->origin);
302 else
303 in->origin = *it;
304 };
305 for (Function* func : functions_)
306 Module::Inline::InlineDFS(func->inlines, addInlineOrigins);
307 int next_id = 0;
308 for (InlineOrigin* origin : inline_origins) {
309 origin->id = next_id++;
310 }
311}
312
313bool Module::ReportError() {
314 fprintf(stderr, "error writing symbol file: %s\n",
315 strerror(errno));
316 return false;
317}
318
319bool Module::WriteRuleMap(const RuleMap& rule_map, std::ostream& stream) {
320 for (RuleMap::const_iterator it = rule_map.begin();
321 it != rule_map.end(); ++it) {
322 if (it != rule_map.begin())
323 stream << ' ';
324 stream << it->first << ": " << it->second;
325 }
326 return stream.good();
327}
328
329bool Module::AddressIsInModule(Address address) const {
330 if (address_ranges_.empty()) {
331 return true;
332 }
333 for (const auto& segment : address_ranges_) {
334 if (address >= segment.address &&
335 address < segment.address + segment.size) {
336 return true;
337 }
338 }
339 return false;
340}
341
342bool Module::Write(std::ostream& stream, SymbolData symbol_data) {
343 stream << "MODULE " << os_ << " " << architecture_ << " "
344 << id_ << " " << name_ << "\n";
345 if (!stream.good())
346 return ReportError();
347
348 if (!code_id_.empty()) {
349 stream << "INFO CODE_ID " << code_id_ << "\n";
350 }
351
352 if (symbol_data & SYMBOLS_AND_FILES) {
353 // Get all referenced inline origins.
354 set<InlineOrigin*, InlineOriginCompare> inline_origins;
355 CreateInlineOrigins(inline_origins);
356 AssignSourceIds(inline_origins);
357
358 // Write out files.
359 for (FileByNameMap::iterator file_it = files_.begin();
360 file_it != files_.end(); ++file_it) {
361 File* file = file_it->second;
362 if (file->source_id >= 0) {
363 stream << "FILE " << file->source_id << " " << file->name << "\n";
364 if (!stream.good())
365 return ReportError();
366 }
367 }
368 // Write out inline origins.
369 for (InlineOrigin* origin : inline_origins) {
370 stream << "INLINE_ORIGIN " << origin->id << " " << origin->name << "\n";
371 if (!stream.good())
372 return ReportError();
373 }
374
375 // Write out functions and their inlines and lines.
376 for (FunctionSet::const_iterator func_it = functions_.begin();
377 func_it != functions_.end(); ++func_it) {
378 Function* func = *func_it;
379 vector<Line>::iterator line_it = func->lines.begin();
380 for (auto range_it = func->ranges.cbegin();
381 range_it != func->ranges.cend(); ++range_it) {
382 stream << "FUNC " << hex
383 << (range_it->address - load_address_) << " "
384 << range_it->size << " "
385 << func->parameter_size << " "
386 << func->name << dec << "\n";
387
388 if (!stream.good())
389 return ReportError();
390
391 // Write out inlines.
392 auto write_inline = [&](unique_ptr<Inline>& in) {
393 stream << "INLINE ";
394 stream << in->inline_nest_level << " " << in->call_site_line << " "
395 << in->getCallSiteFileID() << " " << in->origin->id << hex;
396 for (const Range& r : in->ranges)
397 stream << " " << (r.address - load_address_) << " " << r.size;
398 stream << dec << "\n";
399 };
400 Module::Inline::InlineDFS(func->inlines, write_inline);
401 if (!stream.good())
402 return ReportError();
403
404 while ((line_it != func->lines.end()) &&
405 (line_it->address >= range_it->address) &&
406 (line_it->address < (range_it->address + range_it->size))) {
407 stream << hex
408 << (line_it->address - load_address_) << " "
409 << line_it->size << " "
410 << dec
411 << line_it->number << " "
412 << line_it->file->source_id << "\n";
413
414 if (!stream.good())
415 return ReportError();
416
417 ++line_it;
418 }
419 }
420 }
421
422 // Write out 'PUBLIC' records.
423 for (ExternSet::const_iterator extern_it = externs_.begin();
424 extern_it != externs_.end(); ++extern_it) {
425 Extern* ext = *extern_it;
426 stream << "PUBLIC " << hex
427 << (ext->address - load_address_) << " 0 "
428 << ext->name << dec << "\n";
429 }
430 }
431
432 if (symbol_data & CFI) {
433 // Write out 'STACK CFI INIT' and 'STACK CFI' records.
434 vector<StackFrameEntry*>::const_iterator frame_it;
435 for (frame_it = stack_frame_entries_.begin();
436 frame_it != stack_frame_entries_.end(); ++frame_it) {
437 StackFrameEntry* entry = *frame_it;
438 stream << "STACK CFI INIT " << hex
439 << (entry->address - load_address_) << " "
440 << entry->size << " " << dec;
441 if (!stream.good()
442 || !WriteRuleMap(entry->initial_rules, stream))
443 return ReportError();
444
445 stream << "\n";
446
447 // Write out this entry's delta rules as 'STACK CFI' records.
448 for (RuleChangeMap::const_iterator delta_it = entry->rule_changes.begin();
449 delta_it != entry->rule_changes.end(); ++delta_it) {
450 stream << "STACK CFI " << hex
451 << (delta_it->first - load_address_) << " " << dec;
452 if (!stream.good()
453 || !WriteRuleMap(delta_it->second, stream))
454 return ReportError();
455
456 stream << "\n";
457 }
458 }
459 }
460
461 return true;
462}
463
464} // namespace google_breakpad
465