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 | |
47 | namespace google_breakpad { |
48 | |
49 | using std::dec; |
50 | using std::hex; |
51 | using std::unique_ptr; |
52 | |
53 | Module::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 | |
74 | void 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 | |
100 | Module::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 | |
110 | Module::~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 | |
125 | void Module::SetLoadAddress(Address address) { |
126 | load_address_ = address; |
127 | } |
128 | |
129 | void Module::SetAddressRanges(const vector<Range>& ranges) { |
130 | address_ranges_ = ranges; |
131 | } |
132 | |
133 | bool 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 | |
178 | void 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 | |
186 | void 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 | |
199 | void Module::GetFunctions(vector<Function*>* vec, |
200 | vector<Function*>::iterator i) { |
201 | vec->insert(i, functions_.begin(), functions_.end()); |
202 | } |
203 | |
204 | void Module::GetExterns(vector<Extern*>* vec, |
205 | vector<Extern*>::iterator i) { |
206 | vec->insert(i, externs_.begin(), externs_.end()); |
207 | } |
208 | |
209 | Module::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 | |
231 | Module::File* Module::FindFile(const char* name) { |
232 | string name_string = name; |
233 | return FindFile(name_string); |
234 | } |
235 | |
236 | Module::File* Module::FindExistingFile(const string& name) { |
237 | FileByNameMap::iterator it = files_.find(&name); |
238 | return (it == files_.end()) ? NULL : it->second; |
239 | } |
240 | |
241 | void 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 | |
247 | void Module::GetStackFrameEntries(vector<StackFrameEntry*>* vec) const { |
248 | *vec = stack_frame_entries_; |
249 | } |
250 | |
251 | void 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 | |
294 | void 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 | |
313 | bool Module::ReportError() { |
314 | fprintf(stderr, "error writing symbol file: %s\n" , |
315 | strerror(errno)); |
316 | return false; |
317 | } |
318 | |
319 | bool 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 | |
329 | bool 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 | |
342 | bool 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 | |