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// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
31
32// Implement the DwarfCUToModule class; see dwarf_cu_to_module.h.
33
34// For <inttypes.h> PRI* macros, before anything else might #include it.
35#ifndef __STDC_FORMAT_MACROS
36#define __STDC_FORMAT_MACROS
37#endif /* __STDC_FORMAT_MACROS */
38
39#include "common/dwarf_cu_to_module.h"
40
41#include <assert.h>
42#include <inttypes.h>
43#include <stdint.h>
44#include <stdio.h>
45
46#include <algorithm>
47#include <memory>
48#include <numeric>
49#include <utility>
50
51#include "common/string_view.h"
52#include "common/dwarf_line_to_module.h"
53#include "google_breakpad/common/breakpad_types.h"
54
55namespace google_breakpad {
56
57using std::accumulate;
58using std::map;
59using std::pair;
60using std::sort;
61using std::vector;
62using std::unique_ptr;
63
64// Data provided by a DWARF specification DIE.
65//
66// In DWARF, the DIE for a definition may contain a DW_AT_specification
67// attribute giving the offset of the corresponding declaration DIE, and
68// the definition DIE may omit information given in the declaration. For
69// example, it's common for a function's address range to appear only in
70// its definition DIE, but its name to appear only in its declaration
71// DIE.
72//
73// The dumper needs to be able to follow DW_AT_specification links to
74// bring all this information together in a FUNC record. Conveniently,
75// DIEs that are the target of such links have a DW_AT_declaration flag
76// set, so we can identify them when we first see them, and record their
77// contents for later reference.
78//
79// A Specification holds information gathered from a declaration DIE that
80// we may need if we find a DW_AT_specification link pointing to it.
81struct DwarfCUToModule::Specification {
82 // The qualified name that can be found by demangling DW_AT_MIPS_linkage_name.
83 StringView qualified_name;
84
85 // The name of the enclosing scope, or the empty string if there is none.
86 StringView enclosing_name;
87
88 // The name for the specification DIE itself, without any enclosing
89 // name components.
90 StringView unqualified_name;
91};
92
93// An abstract origin -- base definition of an inline function.
94struct AbstractOrigin {
95 explicit AbstractOrigin(StringView name) : name(name) {}
96
97 StringView name;
98};
99
100typedef map<uint64_t, AbstractOrigin> AbstractOriginByOffset;
101
102// Data global to the DWARF-bearing file that is private to the
103// DWARF-to-Module process.
104struct DwarfCUToModule::FilePrivate {
105 // A map from offsets of DIEs within the .debug_info section to
106 // Specifications describing those DIEs. Specification references can
107 // cross compilation unit boundaries.
108 SpecificationByOffset specifications;
109
110 AbstractOriginByOffset origins;
111
112 // Keep a list of forward references from DW_AT_abstract_origin and
113 // DW_AT_specification attributes so names can be fixed up.
114 std::map<uint64_t, Module::Function*> forward_ref_die_to_func;
115};
116
117DwarfCUToModule::FileContext::FileContext(const string& filename,
118 Module* module,
119 bool handle_inter_cu_refs)
120 : filename_(filename),
121 module_(module),
122 handle_inter_cu_refs_(handle_inter_cu_refs),
123 file_private_(new FilePrivate()) {
124}
125
126DwarfCUToModule::FileContext::~FileContext() {
127}
128
129void DwarfCUToModule::FileContext::AddSectionToSectionMap(
130 const string& name, const uint8_t* contents, uint64_t length) {
131 section_map_[name] = std::make_pair(contents, length);
132}
133
134void DwarfCUToModule::FileContext::ClearSectionMapForTest() {
135 section_map_.clear();
136}
137
138const SectionMap&
139DwarfCUToModule::FileContext::section_map() const {
140 return section_map_;
141}
142
143void DwarfCUToModule::FileContext::ClearSpecifications() {
144 if (!handle_inter_cu_refs_)
145 file_private_->specifications.clear();
146}
147
148bool DwarfCUToModule::FileContext::IsUnhandledInterCUReference(
149 uint64_t offset, uint64_t compilation_unit_start) const {
150 if (handle_inter_cu_refs_)
151 return false;
152 return offset < compilation_unit_start;
153}
154
155// Information global to the particular compilation unit we're
156// parsing. This is for data shared across the CU's entire DIE tree,
157// and parameters from the code invoking the CU parser.
158struct DwarfCUToModule::CUContext {
159 CUContext(FileContext* file_context_arg, WarningReporter* reporter_arg,
160 RangesHandler* ranges_handler_arg)
161 : version(0),
162 file_context(file_context_arg),
163 reporter(reporter_arg),
164 ranges_handler(ranges_handler_arg),
165 language(Language::CPlusPlus),
166 low_pc(0),
167 high_pc(0),
168 ranges_form(DW_FORM_sec_offset),
169 ranges_data(0),
170 ranges_base(0),
171 str_offsets_base(0) { }
172
173 ~CUContext() {
174 for (vector<Module::Function*>::iterator it = functions.begin();
175 it != functions.end(); ++it) {
176 delete *it;
177 }
178 };
179
180 // Dwarf version of the source CU.
181 uint8_t version;
182
183 // The DWARF-bearing file into which this CU was incorporated.
184 FileContext* file_context;
185
186 // For printing error messages.
187 WarningReporter* reporter;
188
189 // For reading ranges from the .debug_ranges section
190 RangesHandler* ranges_handler;
191
192 // The source language of this compilation unit.
193 const Language* language;
194
195 // Addresses covered by this CU. If high_pc_ is non-zero then the CU covers
196 // low_pc to high_pc, otherwise ranges_data is non-zero and low_pc represents
197 // the base address of the ranges covered by the CU. ranges_data will define
198 // the CU's actual ranges.
199 uint64_t low_pc;
200 uint64_t high_pc;
201
202 // Ranges for this CU are read according to this form.
203 enum DwarfForm ranges_form;
204 uint64_t ranges_data;
205
206 // Offset into .debug_rngslists where this CU's ranges are stored.
207 // Data in DW_FORM_rnglistx is relative to this offset.
208 uint64_t ranges_base;
209
210 // Offset into .debug_addr where this CU's addresses are stored. Data in
211 // form DW_FORM_addrxX is relative to this offset.
212 uint64_t addr_base;
213
214 // Offset into this CU's contribution to .debug_str_offsets.
215 uint64_t str_offsets_base;
216
217 // Collect all the data from the CU that a RangeListReader needs to read a
218 // range.
219 bool AssembleRangeListInfo(
220 RangeListReader::CURangesInfo* info) {
221 const SectionMap& section_map
222 = file_context->section_map();
223 info->version_ = version;
224 info->base_address_ = low_pc;
225 info->ranges_base_ = ranges_base;
226 const char* section_name = (version <= 4 ?
227 ".debug_ranges" : ".debug_rnglists");
228 SectionMap::const_iterator map_entry
229 = GetSectionByName(section_map, section_name);
230 if (map_entry == section_map.end()) {
231 return false;
232 }
233 info->buffer_ = map_entry->second.first;
234 info->size_ = map_entry->second.second;
235 if (version > 4) {
236 SectionMap::const_iterator map_entry
237 = GetSectionByName(section_map, ".debug_addr");
238 if (map_entry == section_map.end()) {
239 return false;
240 }
241 info->addr_buffer_ = map_entry->second.first;
242 info->addr_buffer_size_ = map_entry->second.second;
243 info->addr_base_ = addr_base;
244 }
245 return true;
246 }
247
248 // The functions defined in this compilation unit. We accumulate
249 // them here during parsing. Then, in DwarfCUToModule::Finish, we
250 // assign them lines and add them to file_context->module.
251 //
252 // Destroying this destroys all the functions this vector points to.
253 vector<Module::Function*> functions;
254
255 // A map of function pointers to the its forward specification DIE's offset.
256 map<Module::Function*, uint64_t> spec_function_offsets;
257};
258
259// Information about the context of a particular DIE. This is for
260// information that changes as we descend the tree towards the leaves:
261// the containing classes/namespaces, etc.
262struct DwarfCUToModule::DIEContext {
263 // The fully-qualified name of the context. For example, for a
264 // tree like:
265 //
266 // DW_TAG_namespace Foo
267 // DW_TAG_class Bar
268 // DW_TAG_subprogram Baz
269 //
270 // in a C++ compilation unit, the DIEContext's name for the
271 // DW_TAG_subprogram DIE would be "Foo::Bar". The DIEContext's
272 // name for the DW_TAG_namespace DIE would be "".
273 StringView name;
274};
275
276// An abstract base class for all the dumper's DIE handlers.
277class DwarfCUToModule::GenericDIEHandler: public DIEHandler {
278 public:
279 // Create a handler for the DIE at OFFSET whose compilation unit is
280 // described by CU_CONTEXT, and whose immediate context is described
281 // by PARENT_CONTEXT.
282 GenericDIEHandler(CUContext* cu_context, DIEContext* parent_context,
283 uint64_t offset)
284 : cu_context_(cu_context),
285 parent_context_(parent_context),
286 offset_(offset),
287 declaration_(false),
288 specification_(NULL),
289 abstract_origin_(NULL),
290 forward_ref_die_offset_(0), specification_offset_(0) { }
291
292 // Derived classes' ProcessAttributeUnsigned can defer to this to
293 // handle DW_AT_declaration, or simply not override it.
294 void ProcessAttributeUnsigned(enum DwarfAttribute attr,
295 enum DwarfForm form,
296 uint64_t data);
297
298 // Derived classes' ProcessAttributeReference can defer to this to
299 // handle DW_AT_specification, or simply not override it.
300 void ProcessAttributeReference(enum DwarfAttribute attr,
301 enum DwarfForm form,
302 uint64_t data);
303
304 // Derived classes' ProcessAttributeReference can defer to this to
305 // handle DW_AT_specification, or simply not override it.
306 void ProcessAttributeString(enum DwarfAttribute attr,
307 enum DwarfForm form,
308 const string& data);
309
310 protected:
311 // Compute and return the fully-qualified name of the DIE. If this
312 // DIE is a declaration DIE, to be cited by other DIEs'
313 // DW_AT_specification attributes, record its enclosing name and
314 // unqualified name in the specification table.
315 //
316 // Use this from EndAttributes member functions, not ProcessAttribute*
317 // functions; only the former can be sure that all the DIE's attributes
318 // have been seen.
319 StringView ComputeQualifiedName();
320
321 CUContext* cu_context_;
322 DIEContext* parent_context_;
323 uint64_t offset_;
324
325 // If this DIE has a DW_AT_declaration attribute, this is its value.
326 // It is false on DIEs with no DW_AT_declaration attribute.
327 bool declaration_;
328
329 // If this DIE has a DW_AT_specification attribute, this is the
330 // Specification structure for the DIE the attribute refers to.
331 // Otherwise, this is NULL.
332 Specification* specification_;
333
334 // If this DIE has a DW_AT_abstract_origin attribute, this is the
335 // AbstractOrigin structure for the DIE the attribute refers to.
336 // Otherwise, this is NULL.
337 const AbstractOrigin* abstract_origin_;
338
339 // If this DIE has a DW_AT_specification or DW_AT_abstract_origin and it is a
340 // forward reference, no Specification will be available. Track the reference
341 // to be fixed up when the DIE is parsed.
342 uint64_t forward_ref_die_offset_;
343
344 // The root offset of Specification or abstract origin.
345 uint64_t specification_offset_;
346
347 // The value of the DW_AT_name attribute, or the empty string if the
348 // DIE has no such attribute.
349 StringView name_attribute_;
350
351 // The demangled value of the DW_AT_MIPS_linkage_name attribute, or the empty
352 // string if the DIE has no such attribute or its content could not be
353 // demangled.
354 StringView demangled_name_;
355
356 // The non-demangled value of the DW_AT_MIPS_linkage_name attribute,
357 // it its content count not be demangled.
358 StringView raw_name_;
359};
360
361void DwarfCUToModule::GenericDIEHandler::ProcessAttributeUnsigned(
362 enum DwarfAttribute attr,
363 enum DwarfForm form,
364 uint64_t data) {
365 switch (attr) {
366 case DW_AT_declaration: declaration_ = (data != 0); break;
367 default: break;
368 }
369}
370
371void DwarfCUToModule::GenericDIEHandler::ProcessAttributeReference(
372 enum DwarfAttribute attr,
373 enum DwarfForm form,
374 uint64_t data) {
375 switch (attr) {
376 case DW_AT_specification: {
377 FileContext* file_context = cu_context_->file_context;
378 if (file_context->IsUnhandledInterCUReference(
379 data, cu_context_->reporter->cu_offset())) {
380 cu_context_->reporter->UnhandledInterCUReference(offset_, data);
381 break;
382 }
383 // Find the Specification to which this attribute refers, and
384 // set specification_ appropriately. We could do more processing
385 // here, but it's better to leave the real work to our
386 // EndAttribute member function, at which point we know we have
387 // seen all the DIE's attributes.
388 SpecificationByOffset* specifications =
389 &file_context->file_private_->specifications;
390 SpecificationByOffset::iterator spec = specifications->find(data);
391 if (spec != specifications->end()) {
392 specification_ = &spec->second;
393 } else if (data > offset_) {
394 forward_ref_die_offset_ = data;
395 } else {
396 cu_context_->reporter->UnknownSpecification(offset_, data);
397 }
398 specification_offset_ = data;
399 break;
400 }
401 case DW_AT_abstract_origin: {
402 const AbstractOriginByOffset& origins =
403 cu_context_->file_context->file_private_->origins;
404 AbstractOriginByOffset::const_iterator origin = origins.find(data);
405 if (origin != origins.end()) {
406 abstract_origin_ = &(origin->second);
407 } else if (data > offset_) {
408 forward_ref_die_offset_ = data;
409 }
410 specification_offset_ = data;
411 break;
412 }
413 default: break;
414 }
415}
416
417void DwarfCUToModule::GenericDIEHandler::ProcessAttributeString(
418 enum DwarfAttribute attr,
419 enum DwarfForm form,
420 const string& data) {
421 switch (attr) {
422 case DW_AT_name:
423 name_attribute_ =
424 cu_context_->file_context->module_->AddStringToPool(data);
425 break;
426 case DW_AT_MIPS_linkage_name:
427 case DW_AT_linkage_name: {
428 string demangled;
429 Language::DemangleResult result =
430 cu_context_->language->DemangleName(data, &demangled);
431 switch (result) {
432 case Language::kDemangleSuccess:
433 demangled_name_ =
434 cu_context_->file_context->module_->AddStringToPool(demangled);
435 break;
436
437 case Language::kDemangleFailure:
438 cu_context_->reporter->DemangleError(data);
439 // fallthrough
440 case Language::kDontDemangle:
441 demangled_name_ = StringView();
442 raw_name_ = cu_context_->file_context->module_->AddStringToPool(data);
443 break;
444 }
445 break;
446 }
447 default: break;
448 }
449}
450
451StringView DwarfCUToModule::GenericDIEHandler::ComputeQualifiedName() {
452 // Use the demangled name, if one is available. Demangled names are
453 // preferable to those inferred from the DWARF structure because they
454 // include argument types.
455 StringView* qualified_name = nullptr;
456 if (!demangled_name_.empty()) {
457 // Found it is this DIE.
458 qualified_name = &demangled_name_;
459 } else if (specification_ && !specification_->qualified_name.empty()) {
460 // Found it on the specification.
461 qualified_name = &specification_->qualified_name;
462 }
463
464 StringView* unqualified_name = nullptr;
465 StringView* enclosing_name = nullptr;
466 if (!qualified_name) {
467 // Find the unqualified name. If the DIE has its own DW_AT_name
468 // attribute, then use that; otherwise, check the specification.
469 if (!name_attribute_.empty()) {
470 unqualified_name = &name_attribute_;
471 } else if (specification_) {
472 unqualified_name = &specification_->unqualified_name;
473 } else if (!raw_name_.empty()) {
474 unqualified_name = &raw_name_;
475 }
476
477 // Find the name of the enclosing context. If this DIE has a
478 // specification, it's the specification's enclosing context that
479 // counts; otherwise, use this DIE's context.
480 if (specification_) {
481 enclosing_name = &specification_->enclosing_name;
482 } else {
483 enclosing_name = &parent_context_->name;
484 }
485 }
486
487 // Prepare the return value before upcoming mutations possibly invalidate the
488 // existing pointers.
489 string return_value;
490 if (qualified_name) {
491 return_value = qualified_name->str();
492 } else if (unqualified_name && enclosing_name) {
493 // Combine the enclosing name and unqualified name to produce our
494 // own fully-qualified name.
495 return_value = cu_context_->language->MakeQualifiedName(
496 enclosing_name->str(), unqualified_name->str());
497 }
498
499 // If this DIE was marked as a declaration, record its names in the
500 // specification table.
501 if ((declaration_ && qualified_name) ||
502 (unqualified_name && enclosing_name)) {
503 Specification spec;
504 if (qualified_name) {
505 spec.qualified_name = *qualified_name;
506 } else {
507 spec.enclosing_name = *enclosing_name;
508 spec.unqualified_name = *unqualified_name;
509 }
510 cu_context_->file_context->file_private_->specifications[offset_] = spec;
511 }
512
513 return cu_context_->file_context->module_->AddStringToPool(return_value);
514}
515
516static bool IsEmptyRange(const vector<Module::Range>& ranges) {
517 uint64_t size = accumulate(ranges.cbegin(), ranges.cend(), 0,
518 [](uint64_t total, Module::Range entry) {
519 return total + entry.size;
520 }
521 );
522
523 return size == 0;
524}
525
526
527// A handler for DW_TAG_inlined_subroutine DIEs.
528class DwarfCUToModule::InlineHandler : public GenericDIEHandler {
529 public:
530 InlineHandler(CUContext* cu_context,
531 DIEContext* parent_context,
532 uint64_t offset,
533 int inline_nest_level,
534 vector<unique_ptr<Module::Inline>>& inlines)
535 : GenericDIEHandler(cu_context, parent_context, offset),
536 low_pc_(0),
537 high_pc_(0),
538 high_pc_form_(DW_FORM_addr),
539 ranges_form_(DW_FORM_sec_offset),
540 ranges_data_(0),
541 call_site_line_(0),
542 inline_nest_level_(inline_nest_level),
543 inlines_(inlines) {}
544
545 void ProcessAttributeUnsigned(enum DwarfAttribute attr,
546 enum DwarfForm form,
547 uint64_t data);
548 DIEHandler* FindChildHandler(uint64_t offset, enum DwarfTag tag);
549 bool EndAttributes();
550 void Finish();
551
552 private:
553 // The fully-qualified name, as derived from name_attribute_,
554 // specification_, parent_context_. Computed in EndAttributes.
555 StringView name_;
556 uint64_t low_pc_; // DW_AT_low_pc
557 uint64_t high_pc_; // DW_AT_high_pc
558 DwarfForm high_pc_form_; // DW_AT_high_pc can be length or address.
559 DwarfForm ranges_form_; // DW_FORM_sec_offset or DW_FORM_rnglistx
560 uint64_t ranges_data_; // DW_AT_ranges
561 int call_site_line_; // DW_AT_call_line
562 int call_site_file_id_; // DW_AT_call_file
563 int inline_nest_level_;
564 // A vector of inlines in the same nest level. It's owned by its parent
565 // function/inline. At Finish(), add this inline into the vector.
566 vector<unique_ptr<Module::Inline>>& inlines_;
567 // A vector of child inlines.
568 vector<unique_ptr<Module::Inline>> child_inlines_;
569};
570
571void DwarfCUToModule::InlineHandler::ProcessAttributeUnsigned(
572 enum DwarfAttribute attr,
573 enum DwarfForm form,
574 uint64_t data) {
575 switch (attr) {
576 case DW_AT_low_pc:
577 low_pc_ = data;
578 break;
579 case DW_AT_high_pc:
580 high_pc_form_ = form;
581 high_pc_ = data;
582 break;
583 case DW_AT_ranges:
584 ranges_data_ = data;
585 ranges_form_ = form;
586 break;
587 case DW_AT_call_line:
588 call_site_line_ = data;
589 break;
590 case DW_AT_call_file:
591 call_site_file_id_ = data;
592 break;
593 default:
594 GenericDIEHandler::ProcessAttributeUnsigned(attr, form, data);
595 break;
596 }
597}
598
599DIEHandler* DwarfCUToModule::InlineHandler::FindChildHandler(
600 uint64_t offset,
601 enum DwarfTag tag) {
602 switch (tag) {
603 case DW_TAG_inlined_subroutine:
604 return new InlineHandler(cu_context_, new DIEContext(), offset,
605 inline_nest_level_ + 1, child_inlines_);
606 default:
607 return NULL;
608 }
609}
610
611bool DwarfCUToModule::InlineHandler::EndAttributes() {
612 if (abstract_origin_)
613 name_ = abstract_origin_->name;
614 if (name_.empty()) {
615 // We haven't seen the abstract origin yet, which might appears later and we
616 // will fix the name after calling
617 // InlineOriginMap::GetOrCreateInlineOrigin with right name.
618 name_ =
619 cu_context_->file_context->module_->AddStringToPool("<name omitted>");
620 }
621 return true;
622}
623
624void DwarfCUToModule::InlineHandler::Finish() {
625 vector<Module::Range> ranges;
626
627 if (low_pc_ && high_pc_) {
628 if (high_pc_form_ != DW_FORM_addr &&
629 high_pc_form_ != DW_FORM_GNU_addr_index &&
630 high_pc_form_ != DW_FORM_addrx &&
631 high_pc_form_ != DW_FORM_addrx1 &&
632 high_pc_form_ != DW_FORM_addrx2 &&
633 high_pc_form_ != DW_FORM_addrx3 &&
634 high_pc_form_ != DW_FORM_addrx4) {
635 high_pc_ += low_pc_;
636 }
637
638 Module::Range range(low_pc_, high_pc_ - low_pc_);
639 ranges.push_back(range);
640 } else {
641 RangesHandler* ranges_handler = cu_context_->ranges_handler;
642 if (ranges_handler) {
643 RangeListReader::CURangesInfo cu_info;
644 if (cu_context_->AssembleRangeListInfo(&cu_info)) {
645 if (!ranges_handler->ReadRanges(ranges_form_, ranges_data_,
646 &cu_info, &ranges)) {
647 ranges.clear();
648 cu_context_->reporter->MalformedRangeList(ranges_data_);
649 }
650 } else {
651 cu_context_->reporter->MissingRanges();
652 }
653 }
654 }
655
656 // Ignore DW_TAG_inlined_subroutine with empty range.
657 if (ranges.empty()) {
658 return;
659 }
660
661 // Every DW_TAG_inlined_subroutine should have a DW_AT_abstract_origin.
662 assert(specification_offset_ != 0);
663
664 cu_context_->file_context->module_->inline_origin_map.SetReference(
665 specification_offset_, specification_offset_);
666 Module::InlineOrigin* origin =
667 cu_context_->file_context->module_->inline_origin_map
668 .GetOrCreateInlineOrigin(specification_offset_, name_);
669 unique_ptr<Module::Inline> in(
670 new Module::Inline(origin, ranges, call_site_line_, call_site_file_id_,
671 inline_nest_level_, std::move(child_inlines_)));
672 inlines_.push_back(std::move(in));
673}
674
675// A handler class for DW_TAG_subprogram DIEs.
676class DwarfCUToModule::FuncHandler: public GenericDIEHandler {
677 public:
678 FuncHandler(CUContext* cu_context,
679 DIEContext* parent_context,
680 uint64_t offset,
681 bool handle_inline)
682 : GenericDIEHandler(cu_context, parent_context, offset),
683 low_pc_(0),
684 high_pc_(0),
685 high_pc_form_(DW_FORM_addr),
686 ranges_form_(DW_FORM_sec_offset),
687 ranges_data_(0),
688 inline_(false),
689 handle_inline_(handle_inline) {}
690
691 void ProcessAttributeUnsigned(enum DwarfAttribute attr,
692 enum DwarfForm form,
693 uint64_t data);
694 void ProcessAttributeSigned(enum DwarfAttribute attr,
695 enum DwarfForm form,
696 int64_t data);
697 DIEHandler* FindChildHandler(uint64_t offset, enum DwarfTag tag);
698 bool EndAttributes();
699 void Finish();
700
701 private:
702 // The fully-qualified name, as derived from name_attribute_,
703 // specification_, parent_context_. Computed in EndAttributes.
704 StringView name_;
705 uint64_t low_pc_, high_pc_; // DW_AT_low_pc, DW_AT_high_pc
706 DwarfForm high_pc_form_; // DW_AT_high_pc can be length or address.
707 DwarfForm ranges_form_; // DW_FORM_sec_offset or DW_FORM_rnglistx
708 uint64_t ranges_data_; // DW_AT_ranges
709 bool inline_;
710 vector<unique_ptr<Module::Inline>> child_inlines_;
711 bool handle_inline_;
712};
713
714void DwarfCUToModule::FuncHandler::ProcessAttributeUnsigned(
715 enum DwarfAttribute attr,
716 enum DwarfForm form,
717 uint64_t data) {
718 switch (attr) {
719 // If this attribute is present at all --- even if its value is
720 // DW_INL_not_inlined --- then GCC may cite it as someone else's
721 // DW_AT_abstract_origin attribute.
722 case DW_AT_inline: inline_ = true; break;
723
724 case DW_AT_low_pc: low_pc_ = data; break;
725 case DW_AT_high_pc:
726 high_pc_form_ = form;
727 high_pc_ = data;
728 break;
729 case DW_AT_ranges:
730 ranges_data_ = data;
731 ranges_form_ = form;
732 break;
733 default:
734 GenericDIEHandler::ProcessAttributeUnsigned(attr, form, data);
735 break;
736 }
737}
738
739void DwarfCUToModule::FuncHandler::ProcessAttributeSigned(
740 enum DwarfAttribute attr,
741 enum DwarfForm form,
742 int64_t data) {
743 switch (attr) {
744 // If this attribute is present at all --- even if its value is
745 // DW_INL_not_inlined --- then GCC may cite it as someone else's
746 // DW_AT_abstract_origin attribute.
747 case DW_AT_inline: inline_ = true; break;
748
749 default:
750 break;
751 }
752}
753
754DIEHandler* DwarfCUToModule::FuncHandler::FindChildHandler(
755 uint64_t offset,
756 enum DwarfTag tag) {
757 switch (tag) {
758 case DW_TAG_inlined_subroutine:
759 if (handle_inline_)
760 return new InlineHandler(cu_context_, new DIEContext(), offset, 0,
761 child_inlines_);
762 default:
763 return NULL;
764 }
765}
766
767bool DwarfCUToModule::FuncHandler::EndAttributes() {
768 // Compute our name, and record a specification, if appropriate.
769 name_ = ComputeQualifiedName();
770 if (name_.empty() && abstract_origin_) {
771 name_ = abstract_origin_->name;
772 }
773 return true;
774}
775
776void DwarfCUToModule::FuncHandler::Finish() {
777 vector<Module::Range> ranges;
778
779 // Check if this DIE was one of the forward references that was not able
780 // to be processed, and fix up the name of the appropriate Module::Function.
781 // "name_" will have already been fixed up in EndAttributes().
782 if (!name_.empty()) {
783 auto iter =
784 cu_context_->file_context->file_private_->forward_ref_die_to_func.find(
785 offset_);
786 if (iter !=
787 cu_context_->file_context->file_private_->forward_ref_die_to_func.end())
788 iter->second->name = name_;
789 }
790
791 if (!ranges_data_) {
792 // Make high_pc_ an address, if it isn't already.
793 if (high_pc_form_ != DW_FORM_addr &&
794 high_pc_form_ != DW_FORM_GNU_addr_index &&
795 high_pc_form_ != DW_FORM_addrx &&
796 high_pc_form_ != DW_FORM_addrx1 &&
797 high_pc_form_ != DW_FORM_addrx2 &&
798 high_pc_form_ != DW_FORM_addrx3 &&
799 high_pc_form_ != DW_FORM_addrx4) {
800 high_pc_ += low_pc_;
801 }
802
803 Module::Range range(low_pc_, high_pc_ - low_pc_);
804 ranges.push_back(range);
805 } else {
806 RangesHandler* ranges_handler = cu_context_->ranges_handler;
807 if (ranges_handler) {
808 RangeListReader::CURangesInfo cu_info;
809 if (cu_context_->AssembleRangeListInfo(&cu_info)) {
810 if (!ranges_handler->ReadRanges(ranges_form_, ranges_data_,
811 &cu_info, &ranges)) {
812 ranges.clear();
813 cu_context_->reporter->MalformedRangeList(ranges_data_);
814 }
815 } else {
816 cu_context_->reporter->MissingRanges();
817 }
818 }
819 }
820
821 StringView name_omitted =
822 cu_context_->file_context->module_->AddStringToPool("<name omitted>");
823 bool empty_range = IsEmptyRange(ranges);
824 // Did we collect the information we need? Not all DWARF function
825 // entries are non-empty (for example, inlined functions that were never
826 // used), but all the ones we're interested in cover a non-empty range of
827 // bytes.
828 if (!empty_range) {
829 low_pc_ = ranges.front().address;
830 // Malformed DWARF may omit the name, but all Module::Functions must
831 // have names.
832 StringView name = name_.empty() ? name_omitted : name_;
833 // Create a Module::Function based on the data we've gathered, and
834 // add it to the functions_ list.
835 scoped_ptr<Module::Function> func(new Module::Function(name, low_pc_));
836 func->ranges = ranges;
837 func->parameter_size = 0;
838 if (func->address) {
839 // If the function address is zero this is a sign that this function
840 // description is just empty debug data and should just be discarded.
841 cu_context_->functions.push_back(func.release());
842 if (forward_ref_die_offset_ != 0) {
843 cu_context_->file_context->file_private_
844 ->forward_ref_die_to_func[forward_ref_die_offset_] =
845 cu_context_->functions.back();
846
847 cu_context_->spec_function_offsets[cu_context_->functions.back()] =
848 forward_ref_die_offset_;
849 }
850
851 cu_context_->functions.back()->inlines.swap(child_inlines_);
852 }
853 } else if (inline_) {
854 AbstractOrigin origin(name_);
855 cu_context_->file_context->file_private_->origins.insert({offset_, origin});
856 }
857
858 // Only keep track of DW_TAG_subprogram which have the attributes we are
859 // interested.
860 if (handle_inline_ && (!empty_range || inline_)) {
861 StringView name = name_.empty() ? name_omitted : name_;
862 uint64_t offset =
863 specification_offset_ != 0 ? specification_offset_ : offset_;
864 cu_context_->file_context->module_->inline_origin_map.SetReference(offset_,
865 offset);
866 cu_context_->file_context->module_->inline_origin_map
867 .GetOrCreateInlineOrigin(offset_, name);
868 }
869}
870
871// A handler for DIEs that contain functions and contribute a
872// component to their names: namespaces, classes, etc.
873class DwarfCUToModule::NamedScopeHandler: public GenericDIEHandler {
874 public:
875 NamedScopeHandler(CUContext* cu_context,
876 DIEContext* parent_context,
877 uint64_t offset,
878 bool handle_inline)
879 : GenericDIEHandler(cu_context, parent_context, offset),
880 handle_inline_(handle_inline) {}
881 bool EndAttributes();
882 DIEHandler* FindChildHandler(uint64_t offset, enum DwarfTag tag);
883
884 private:
885 DIEContext child_context_; // A context for our children.
886 bool handle_inline_;
887};
888
889bool DwarfCUToModule::NamedScopeHandler::EndAttributes() {
890 child_context_.name = ComputeQualifiedName();
891 return true;
892}
893
894DIEHandler* DwarfCUToModule::NamedScopeHandler::FindChildHandler(
895 uint64_t offset,
896 enum DwarfTag tag) {
897 switch (tag) {
898 case DW_TAG_subprogram:
899 return new FuncHandler(cu_context_, &child_context_, offset,
900 handle_inline_);
901 case DW_TAG_namespace:
902 case DW_TAG_class_type:
903 case DW_TAG_structure_type:
904 case DW_TAG_union_type:
905 return new NamedScopeHandler(cu_context_, &child_context_, offset,
906 handle_inline_);
907 default:
908 return NULL;
909 }
910}
911
912void DwarfCUToModule::WarningReporter::CUHeading() {
913 if (printed_cu_header_)
914 return;
915 fprintf(stderr, "%s: in compilation unit '%s' (offset 0x%" PRIx64 "):\n",
916 filename_.c_str(), cu_name_.c_str(), cu_offset_);
917 printed_cu_header_ = true;
918}
919
920void DwarfCUToModule::WarningReporter::UnknownSpecification(uint64_t offset,
921 uint64_t target) {
922 CUHeading();
923 fprintf(stderr, "%s: the DIE at offset 0x%" PRIx64 " has a "
924 "DW_AT_specification attribute referring to the DIE at offset 0x%"
925 PRIx64 ", which was not marked as a declaration\n",
926 filename_.c_str(), offset, target);
927}
928
929void DwarfCUToModule::WarningReporter::UnknownAbstractOrigin(uint64_t offset,
930 uint64_t target) {
931 CUHeading();
932 fprintf(stderr, "%s: the DIE at offset 0x%" PRIx64 " has a "
933 "DW_AT_abstract_origin attribute referring to the DIE at offset 0x%"
934 PRIx64 ", which was not marked as an inline\n",
935 filename_.c_str(), offset, target);
936}
937
938void DwarfCUToModule::WarningReporter::MissingSection(const string& name) {
939 CUHeading();
940 fprintf(stderr, "%s: warning: couldn't find DWARF '%s' section\n",
941 filename_.c_str(), name.c_str());
942}
943
944void DwarfCUToModule::WarningReporter::BadLineInfoOffset(uint64_t offset) {
945 CUHeading();
946 fprintf(stderr, "%s: warning: line number data offset beyond end"
947 " of '.debug_line' section\n",
948 filename_.c_str());
949}
950
951void DwarfCUToModule::WarningReporter::UncoveredHeading() {
952 if (printed_unpaired_header_)
953 return;
954 CUHeading();
955 fprintf(stderr, "%s: warning: skipping unpaired lines/functions:\n",
956 filename_.c_str());
957 printed_unpaired_header_ = true;
958}
959
960void DwarfCUToModule::WarningReporter::UncoveredFunction(
961 const Module::Function& function) {
962 if (!uncovered_warnings_enabled_)
963 return;
964 UncoveredHeading();
965 fprintf(stderr, " function%s: %s\n",
966 IsEmptyRange(function.ranges) ? " (zero-length)" : "",
967 function.name.str().c_str());
968}
969
970void DwarfCUToModule::WarningReporter::UncoveredLine(const Module::Line& line) {
971 if (!uncovered_warnings_enabled_)
972 return;
973 UncoveredHeading();
974 fprintf(stderr, " line%s: %s:%d at 0x%" PRIx64 "\n",
975 (line.size == 0 ? " (zero-length)" : ""),
976 line.file->name.c_str(), line.number, line.address);
977}
978
979void DwarfCUToModule::WarningReporter::UnnamedFunction(uint64_t offset) {
980 CUHeading();
981 fprintf(stderr, "%s: warning: function at offset 0x%" PRIx64 " has no name\n",
982 filename_.c_str(), offset);
983}
984
985void DwarfCUToModule::WarningReporter::DemangleError(const string& input) {
986 CUHeading();
987 fprintf(stderr, "%s: warning: failed to demangle %s\n",
988 filename_.c_str(), input.c_str());
989}
990
991void DwarfCUToModule::WarningReporter::UnhandledInterCUReference(
992 uint64_t offset, uint64_t target) {
993 CUHeading();
994 fprintf(stderr, "%s: warning: the DIE at offset 0x%" PRIx64 " has a "
995 "DW_FORM_ref_addr attribute with an inter-CU reference to "
996 "0x%" PRIx64 ", but inter-CU reference handling is turned "
997 " off.\n", filename_.c_str(), offset, target);
998}
999
1000void DwarfCUToModule::WarningReporter::MalformedRangeList(uint64_t offset) {
1001 CUHeading();
1002 fprintf(stderr, "%s: warning: the range list at offset 0x%" PRIx64 " falls "
1003 " out of the .debug_ranges section.\n",
1004 filename_.c_str(), offset);
1005}
1006
1007void DwarfCUToModule::WarningReporter::MissingRanges() {
1008 CUHeading();
1009 fprintf(stderr, "%s: warning: A DW_AT_ranges attribute was encountered but "
1010 "the .debug_ranges section is missing.\n", filename_.c_str());
1011}
1012
1013DwarfCUToModule::DwarfCUToModule(FileContext* file_context,
1014 LineToModuleHandler* line_reader,
1015 RangesHandler* ranges_handler,
1016 WarningReporter* reporter,
1017 bool handle_inline)
1018 : RootDIEHandler(handle_inline),
1019 line_reader_(line_reader),
1020 cu_context_(new CUContext(file_context, reporter, ranges_handler)),
1021 child_context_(new DIEContext()),
1022 has_source_line_info_(false) {}
1023
1024DwarfCUToModule::~DwarfCUToModule() {
1025}
1026
1027void DwarfCUToModule::ProcessAttributeSigned(enum DwarfAttribute attr,
1028 enum DwarfForm form,
1029 int64_t data) {
1030 switch (attr) {
1031 case DW_AT_language: // source language of this CU
1032 SetLanguage(static_cast<DwarfLanguage>(data));
1033 break;
1034 default:
1035 break;
1036 }
1037}
1038
1039void DwarfCUToModule::ProcessAttributeUnsigned(enum DwarfAttribute attr,
1040 enum DwarfForm form,
1041 uint64_t data) {
1042 switch (attr) {
1043 case DW_AT_stmt_list: // Line number information.
1044 has_source_line_info_ = true;
1045 source_line_offset_ = data;
1046 break;
1047 case DW_AT_language: // source language of this CU
1048 SetLanguage(static_cast<DwarfLanguage>(data));
1049 break;
1050 case DW_AT_low_pc:
1051 cu_context_->low_pc = data;
1052 break;
1053 case DW_AT_high_pc:
1054 cu_context_->high_pc = data;
1055 break;
1056 case DW_AT_ranges:
1057 cu_context_->ranges_data = data;
1058 cu_context_->ranges_form = form;
1059 break;
1060 case DW_AT_rnglists_base:
1061 cu_context_->ranges_base = data;
1062 break;
1063 case DW_AT_addr_base:
1064 case DW_AT_GNU_addr_base:
1065 cu_context_->addr_base = data;
1066 break;
1067 case DW_AT_str_offsets_base:
1068 cu_context_->str_offsets_base = data;
1069 break;
1070 default:
1071 break;
1072 }
1073}
1074
1075void DwarfCUToModule::ProcessAttributeString(enum DwarfAttribute attr,
1076 enum DwarfForm form,
1077 const string& data) {
1078 switch (attr) {
1079 case DW_AT_name:
1080 cu_context_->reporter->SetCUName(data);
1081 break;
1082 case DW_AT_comp_dir:
1083 line_reader_->StartCompilationUnit(data);
1084 break;
1085 default:
1086 break;
1087 }
1088}
1089
1090bool DwarfCUToModule::EndAttributes() {
1091 return true;
1092}
1093
1094DIEHandler* DwarfCUToModule::FindChildHandler(
1095 uint64_t offset,
1096 enum DwarfTag tag) {
1097 switch (tag) {
1098 case DW_TAG_subprogram:
1099 return new FuncHandler(cu_context_.get(), child_context_.get(), offset,
1100 handle_inline);
1101 case DW_TAG_namespace:
1102 case DW_TAG_class_type:
1103 case DW_TAG_structure_type:
1104 case DW_TAG_union_type:
1105 case DW_TAG_module:
1106 return new NamedScopeHandler(cu_context_.get(), child_context_.get(),
1107 offset, handle_inline);
1108 default:
1109 return NULL;
1110 }
1111}
1112
1113void DwarfCUToModule::SetLanguage(DwarfLanguage language) {
1114 switch (language) {
1115 case DW_LANG_Java:
1116 cu_context_->language = Language::Java;
1117 break;
1118
1119 case DW_LANG_Swift:
1120 cu_context_->language = Language::Swift;
1121 break;
1122
1123 case DW_LANG_Rust:
1124 cu_context_->language = Language::Rust;
1125 break;
1126
1127 // DWARF has no generic language code for assembly language; this is
1128 // what the GNU toolchain uses.
1129 case DW_LANG_Mips_Assembler:
1130 cu_context_->language = Language::Assembler;
1131 break;
1132
1133 // C++ covers so many cases that it probably has some way to cope
1134 // with whatever the other languages throw at us. So make it the
1135 // default.
1136 //
1137 // Objective C and Objective C++ seem to create entries for
1138 // methods whose DW_AT_name values are already fully-qualified:
1139 // "-[Classname method:]". These appear at the top level.
1140 //
1141 // DWARF data for C should never include namespaces or functions
1142 // nested in struct types, but if it ever does, then C++'s
1143 // notation is probably not a bad choice for that.
1144 default:
1145 case DW_LANG_ObjC:
1146 case DW_LANG_ObjC_plus_plus:
1147 case DW_LANG_C:
1148 case DW_LANG_C89:
1149 case DW_LANG_C99:
1150 case DW_LANG_C_plus_plus:
1151 cu_context_->language = Language::CPlusPlus;
1152 break;
1153 }
1154}
1155
1156void DwarfCUToModule::ReadSourceLines(uint64_t offset) {
1157 const SectionMap& section_map
1158 = cu_context_->file_context->section_map();
1159 SectionMap::const_iterator map_entry
1160 = GetSectionByName(section_map, ".debug_line");
1161 if (map_entry == section_map.end()) {
1162 cu_context_->reporter->MissingSection(".debug_line");
1163 return;
1164 }
1165 const uint8_t* line_section_start = map_entry->second.first + offset;
1166 uint64_t line_section_length = map_entry->second.second;
1167 if (offset >= line_section_length) {
1168 cu_context_->reporter->BadLineInfoOffset(offset);
1169 return;
1170 }
1171 line_section_length -= offset;
1172 // When reading line tables, string sections are never needed for dwarf4, and
1173 // may or may not be needed by dwarf5, so no error if they are missing.
1174 const uint8_t* string_section_start = nullptr;
1175 uint64_t string_section_length = 0;
1176 map_entry = GetSectionByName(section_map, ".debug_str");
1177 if (map_entry != section_map.end()) {
1178 string_section_start = map_entry->second.first;
1179 string_section_length = map_entry->second.second;
1180 }
1181 const uint8_t* line_string_section_start = nullptr;
1182 uint64_t line_string_section_length = 0;
1183 map_entry = GetSectionByName(section_map, ".debug_line_str");
1184 if (map_entry != section_map.end()) {
1185 line_string_section_start = map_entry->second.first;
1186 line_string_section_length = map_entry->second.second;
1187 }
1188 line_reader_->ReadProgram(
1189 line_section_start, line_section_length,
1190 string_section_start, string_section_length,
1191 line_string_section_start, line_string_section_length,
1192 cu_context_->file_context->module_, &lines_, &files_);
1193}
1194
1195namespace {
1196class FunctionRange {
1197 public:
1198 FunctionRange(const Module::Range& range, Module::Function* function) :
1199 address(range.address), size(range.size), function(function) { }
1200
1201 void AddLine(Module::Line& line) {
1202 function->lines.push_back(line);
1203 }
1204
1205 Module::Address address;
1206 Module::Address size;
1207 Module::Function* function;
1208};
1209
1210// Fills an array of ranges with pointers to the functions which owns
1211// them. The array is sorted in ascending order and the ranges are non
1212// empty and non-overlapping.
1213
1214static void FillSortedFunctionRanges(vector<FunctionRange>& dest_ranges,
1215 vector<Module::Function*>* functions) {
1216 for (vector<Module::Function*>::const_iterator func_it = functions->cbegin();
1217 func_it != functions->cend();
1218 func_it++)
1219 {
1220 Module::Function* func = *func_it;
1221 vector<Module::Range>& ranges = func->ranges;
1222 for (vector<Module::Range>::const_iterator ranges_it = ranges.cbegin();
1223 ranges_it != ranges.cend();
1224 ++ranges_it) {
1225 FunctionRange range(*ranges_it, func);
1226 if (range.size != 0) {
1227 dest_ranges.push_back(range);
1228 }
1229 }
1230 }
1231
1232 sort(dest_ranges.begin(), dest_ranges.end(),
1233 [](const FunctionRange& fr1, const FunctionRange& fr2) {
1234 return fr1.address < fr2.address;
1235 }
1236 );
1237}
1238
1239// Return true if ADDRESS falls within the range of ITEM.
1240template <class T>
1241inline bool within(const T& item, Module::Address address) {
1242 // Because Module::Address is unsigned, and unsigned arithmetic
1243 // wraps around, this will be false if ADDRESS falls before the
1244 // start of ITEM, or if it falls after ITEM's end.
1245 return address - item.address < item.size;
1246}
1247}
1248
1249void DwarfCUToModule::AssignLinesToFunctions() {
1250 vector<Module::Function*>* functions = &cu_context_->functions;
1251 WarningReporter* reporter = cu_context_->reporter;
1252
1253 // This would be simpler if we assumed that source line entries
1254 // don't cross function boundaries. However, there's no real reason
1255 // to assume that (say) a series of function definitions on the same
1256 // line wouldn't get coalesced into one line number entry. The
1257 // DWARF spec certainly makes no such promises.
1258 //
1259 // So treat the functions and lines as peers, and take the trouble
1260 // to compute their ranges' intersections precisely. In any case,
1261 // the hair here is a constant factor for performance; the
1262 // complexity from here on out is linear.
1263
1264 // Put both our functions and lines in order by address.
1265 std::sort(functions->begin(), functions->end(),
1266 Module::Function::CompareByAddress);
1267 std::sort(lines_.begin(), lines_.end(), Module::Line::CompareByAddress);
1268
1269 // The last line that we used any piece of. We use this only for
1270 // generating warnings.
1271 const Module::Line* last_line_used = NULL;
1272
1273 // The last function and line we warned about --- so we can avoid
1274 // doing so more than once.
1275 const Module::Function* last_function_cited = NULL;
1276 const Module::Line* last_line_cited = NULL;
1277
1278 // Prepare a sorted list of ranges with range-to-function mapping
1279 vector<FunctionRange> sorted_ranges;
1280 FillSortedFunctionRanges(sorted_ranges, functions);
1281
1282 // Make a single pass through both the range and line vectors from lower to
1283 // higher addresses, populating each range's function lines vector with lines
1284 // from our lines_ vector that fall within the range.
1285 vector<FunctionRange>::iterator range_it = sorted_ranges.begin();
1286 vector<Module::Line>::const_iterator line_it = lines_.begin();
1287
1288 Module::Address current;
1289
1290 // Pointers to the referents of func_it and line_it, or NULL if the
1291 // iterator is at the end of the sequence.
1292 FunctionRange* range;
1293 const Module::Line* line;
1294
1295 // Start current at the beginning of the first line or function,
1296 // whichever is earlier.
1297 if (range_it != sorted_ranges.end() && line_it != lines_.end()) {
1298 range = &*range_it;
1299 line = &*line_it;
1300 current = std::min(range->address, line->address);
1301 } else if (line_it != lines_.end()) {
1302 range = NULL;
1303 line = &*line_it;
1304 current = line->address;
1305 } else if (range_it != sorted_ranges.end()) {
1306 range = &*range_it;
1307 line = NULL;
1308 current = range->address;
1309 } else {
1310 return;
1311 }
1312
1313 // Some dwarf producers handle linker-removed functions by using -1 as a
1314 // tombstone in the line table. So the end marker can be -1.
1315 if (current == Module::kMaxAddress)
1316 return;
1317
1318 while (range || line) {
1319 // This loop has two invariants that hold at the top.
1320 //
1321 // First, at least one of the iterators is not at the end of its
1322 // sequence, and those that are not refer to the earliest
1323 // range or line that contains or starts after CURRENT.
1324 //
1325 // Note that every byte is in one of four states: it is covered
1326 // or not covered by a range, and, independently, it is
1327 // covered or not covered by a line.
1328 //
1329 // The second invariant is that CURRENT refers to a byte whose
1330 // state is different from its predecessor, or it refers to the
1331 // first byte in the address space. In other words, CURRENT is
1332 // always the address of a transition.
1333 //
1334 // Note that, although each iteration advances CURRENT from one
1335 // transition address to the next in each iteration, it might
1336 // not advance the iterators. Suppose we have a range that
1337 // starts with a line, has a gap, and then a second line, and
1338 // suppose that we enter an iteration with CURRENT at the end of
1339 // the first line. The next transition address is the start of
1340 // the second line, after the gap, so the iteration should
1341 // advance CURRENT to that point. At the head of that iteration,
1342 // the invariants require that the line iterator be pointing at
1343 // the second line. But this is also true at the head of the
1344 // next. And clearly, the iteration must not change the range
1345 // iterator. So neither iterator moves.
1346
1347 // Assert the first invariant (see above).
1348 assert(!range || current < range->address || within(*range, current));
1349 assert(!line || current < line->address || within(*line, current));
1350
1351 // The next transition after CURRENT.
1352 Module::Address next_transition;
1353
1354 // Figure out which state we're in, add lines or warn, and compute
1355 // the next transition address.
1356 if (range && current >= range->address) {
1357 if (line && current >= line->address) {
1358 // Covered by both a line and a range.
1359 Module::Address range_left = range->size - (current - range->address);
1360 Module::Address line_left = line->size - (current - line->address);
1361 // This may overflow, but things work out.
1362 next_transition = current + std::min(range_left, line_left);
1363 Module::Line l = *line;
1364 l.address = current;
1365 l.size = next_transition - current;
1366 range->AddLine(l);
1367 last_line_used = line;
1368 } else {
1369 // Covered by a range, but no line.
1370 if (range->function != last_function_cited) {
1371 reporter->UncoveredFunction(*(range->function));
1372 last_function_cited = range->function;
1373 }
1374 if (line && within(*range, line->address))
1375 next_transition = line->address;
1376 else
1377 // If this overflows, we'll catch it below.
1378 next_transition = range->address + range->size;
1379 }
1380 } else {
1381 if (line && current >= line->address) {
1382 // Covered by a line, but no range.
1383 //
1384 // If GCC emits padding after one function to align the start
1385 // of the next, then it will attribute the padding
1386 // instructions to the last source line of function (to reduce
1387 // the size of the line number info), but omit it from the
1388 // DW_AT_{low,high}_pc range given in .debug_info (since it
1389 // costs nothing to be precise there). If we did use at least
1390 // some of the line we're about to skip, and it ends at the
1391 // start of the next function, then assume this is what
1392 // happened, and don't warn.
1393 if (line != last_line_cited
1394 && !(range
1395 && line == last_line_used
1396 && range->address - line->address == line->size)) {
1397 reporter->UncoveredLine(*line);
1398 last_line_cited = line;
1399 }
1400 if (range && within(*line, range->address))
1401 next_transition = range->address;
1402 else
1403 // If this overflows, we'll catch it below.
1404 next_transition = line->address + line->size;
1405 } else {
1406 // Covered by neither a range nor a line. By the invariant,
1407 // both range and line begin after CURRENT. The next transition
1408 // is the start of the next range or next line, whichever
1409 // is earliest.
1410 assert(range || line);
1411 if (range && line)
1412 next_transition = std::min(range->address, line->address);
1413 else if (range)
1414 next_transition = range->address;
1415 else
1416 next_transition = line->address;
1417 }
1418 }
1419
1420 // If a function or line abuts the end of the address space, then
1421 // next_transition may end up being zero, in which case we've completed
1422 // our pass. Handle that here, instead of trying to deal with it in
1423 // each place we compute next_transition.
1424
1425 // Some dwarf producers handle linker-removed functions by using -1 as a
1426 // tombstone in the line table. So the end marker can be -1.
1427 if (!next_transition || next_transition == Module::kMaxAddress)
1428 break;
1429
1430 // Advance iterators as needed. If lines overlap or functions overlap,
1431 // then we could go around more than once. We don't worry too much
1432 // about what result we produce in that case, just as long as we don't
1433 // hang or crash.
1434 while (range_it != sorted_ranges.end()
1435 && next_transition >= range_it->address
1436 && !within(*range_it, next_transition))
1437 range_it++;
1438 range = (range_it != sorted_ranges.end()) ? &(*range_it) : NULL;
1439 while (line_it != lines_.end()
1440 && next_transition >= line_it->address
1441 && !within(*line_it, next_transition))
1442 line_it++;
1443 line = (line_it != lines_.end()) ? &*line_it : NULL;
1444
1445 // We must make progress.
1446 assert(next_transition > current);
1447 current = next_transition;
1448 }
1449}
1450
1451void DwarfCUToModule::AssignFilesToInlines() {
1452 // Assign File* to Inlines inside this CU.
1453 auto assignFile = [this](unique_ptr<Module::Inline>& in) {
1454 in->call_site_file = files_[in->call_site_file_id];
1455 };
1456 for (auto func : cu_context_->functions) {
1457 Module::Inline::InlineDFS(func->inlines, assignFile);
1458 }
1459}
1460
1461void DwarfCUToModule::Finish() {
1462 // Assembly language files have no function data, and that gives us
1463 // no place to store our line numbers (even though the GNU toolchain
1464 // will happily produce source line info for assembly language
1465 // files). To avoid spurious warnings about lines we can't assign
1466 // to functions, skip CUs in languages that lack functions.
1467 if (!cu_context_->language->HasFunctions())
1468 return;
1469
1470 // Read source line info, if we have any.
1471 if (has_source_line_info_)
1472 ReadSourceLines(source_line_offset_);
1473
1474 vector<Module::Function*>* functions = &cu_context_->functions;
1475
1476 // Dole out lines to the appropriate functions.
1477 AssignLinesToFunctions();
1478
1479 AssignFilesToInlines();
1480
1481 // Add our functions, which now have source lines assigned to them,
1482 // to module_, and remove duplicate functions.
1483 for (Module::Function* func : *functions)
1484 if (!cu_context_->file_context->module_->AddFunction(func)) {
1485 auto iter = cu_context_->spec_function_offsets.find(func);
1486 if (iter != cu_context_->spec_function_offsets.end())
1487 cu_context_->file_context->file_private_->forward_ref_die_to_func.erase(
1488 iter->second);
1489 delete func;
1490 }
1491
1492 // Ownership of the function objects has shifted from cu_context to
1493 // the Module.
1494 functions->clear();
1495
1496 cu_context_->file_context->ClearSpecifications();
1497}
1498
1499bool DwarfCUToModule::StartCompilationUnit(uint64_t offset,
1500 uint8_t address_size,
1501 uint8_t offset_size,
1502 uint64_t cu_length,
1503 uint8_t dwarf_version) {
1504 cu_context_->version = dwarf_version;
1505 return dwarf_version >= 2;
1506}
1507
1508bool DwarfCUToModule::StartRootDIE(uint64_t offset, enum DwarfTag tag) {
1509 // We don't deal with partial compilation units (the only other tag
1510 // likely to be used for root DIE).
1511 return (tag == DW_TAG_compile_unit
1512 || tag == DW_TAG_skeleton_unit);
1513}
1514
1515} // namespace google_breakpad
1516