Automatic date update in version.in
[external/binutils.git] / gold / gdb-index.cc
1 // gdb-index.cc -- generate .gdb_index section for fast debug lookup
2
3 // Copyright (C) 2012-2019 Free Software Foundation, Inc.
4 // Written by Cary Coutant <ccoutant@google.com>.
5
6 // This file is part of gold.
7
8 // This program is free software; you can redistribute it and/or modify
9 // it under the terms of the GNU General Public License as published by
10 // the Free Software Foundation; either version 3 of the License, or
11 // (at your option) any later version.
12
13 // This program is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 // GNU General Public License for more details.
17
18 // You should have received a copy of the GNU General Public License
19 // along with this program; if not, write to the Free Software
20 // Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21 // MA 02110-1301, USA.
22
23 #include "gold.h"
24
25 #include "gdb-index.h"
26 #include "dwarf_reader.h"
27 #include "dwarf.h"
28 #include "object.h"
29 #include "output.h"
30 #include "demangle.h"
31
32 namespace gold
33 {
34
35 const int gdb_index_version = 7;
36
37 // Sizes of various records in the .gdb_index section.
38 const int gdb_index_offset_size = 4;
39 const int gdb_index_hdr_size = 6 * gdb_index_offset_size;
40 const int gdb_index_cu_size = 16;
41 const int gdb_index_tu_size = 24;
42 const int gdb_index_addr_size = 16 + gdb_index_offset_size;
43 const int gdb_index_sym_size = 2 * gdb_index_offset_size;
44
45 // This class manages the hashed symbol table for the .gdb_index section.
46 // It is essentially equivalent to the hashtab implementation in libiberty,
47 // but is copied into gdb sources and here for compatibility because its
48 // data structure is exposed on disk.
49
50 template <typename T>
51 class Gdb_hashtab
52 {
53  public:
54   Gdb_hashtab()
55     : size_(0), capacity_(0), hashtab_(NULL)
56   { }
57
58   ~Gdb_hashtab()
59   {
60     for (size_t i = 0; i < this->capacity_; ++i)
61       if (this->hashtab_[i] != NULL)
62         delete this->hashtab_[i];
63     delete[] this->hashtab_;
64   }
65
66   // Add a symbol.
67   T*
68   add(T* symbol)
69   {
70     // Resize the hash table if necessary.
71     if (4 * this->size_ / 3 >= this->capacity_)
72       this->expand();
73
74     T** slot = this->find_slot(symbol);
75     if (*slot == NULL)
76       {
77         ++this->size_;
78         *slot = symbol;
79       }
80
81     return *slot;
82   }
83
84   // Return the current size.
85   size_t
86   size() const
87   { return this->size_; }
88
89   // Return the current capacity.
90   size_t
91   capacity() const
92   { return this->capacity_; }
93
94   // Return the contents of slot N.
95   T*
96   operator[](size_t n)
97   { return this->hashtab_[n]; }
98
99  private:
100   // Find a symbol in the hash table, or return an empty slot if
101   // the symbol is not in the table.
102   T**
103   find_slot(T* symbol)
104   {
105     unsigned int index = symbol->hash() & (this->capacity_ - 1);
106     unsigned int step = ((symbol->hash() * 17) & (this->capacity_ - 1)) | 1;
107
108     for (;;)
109       {
110         if (this->hashtab_[index] == NULL
111             || this->hashtab_[index]->equal(symbol))
112           return &this->hashtab_[index];
113         index = (index + step) & (this->capacity_ - 1);
114       }
115   }
116
117   // Expand the hash table.
118   void
119   expand()
120   {
121     if (this->capacity_ == 0)
122       {
123         // Allocate the hash table for the first time.
124         this->capacity_ = Gdb_hashtab::initial_size;
125         this->hashtab_ = new T*[this->capacity_];
126         memset(this->hashtab_, 0, this->capacity_ * sizeof(T*));
127       }
128     else
129       {
130         // Expand and rehash.
131         unsigned int old_cap = this->capacity_;
132         T** old_hashtab = this->hashtab_;
133         this->capacity_ *= 2;
134         this->hashtab_ = new T*[this->capacity_];
135         memset(this->hashtab_, 0, this->capacity_ * sizeof(T*));
136         for (size_t i = 0; i < old_cap; ++i)
137           {
138             if (old_hashtab[i] != NULL)
139               {
140                 T** slot = this->find_slot(old_hashtab[i]);
141                 *slot = old_hashtab[i];
142               }
143           }
144         delete[] old_hashtab;
145       }
146   }
147
148   // Initial size of the hash table; must be a power of 2.
149   static const int initial_size = 1024;
150   size_t size_;
151   size_t capacity_;
152   T** hashtab_;
153 };
154
155 // The hash function for strings in the mapped index.  This is copied
156 // directly from gdb/dwarf2read.c.
157
158 static unsigned int
159 mapped_index_string_hash(const unsigned char* str)
160 {
161   unsigned int r = 0;
162   unsigned char c;
163
164   while ((c = *str++) != 0)
165     {
166       if (gdb_index_version >= 5)
167         c = tolower (c);
168       r = r * 67 + c - 113;
169     }
170
171   return r;
172 }
173
174 // A specialization of Dwarf_info_reader, for building the .gdb_index.
175
176 class Gdb_index_info_reader : public Dwarf_info_reader
177 {
178  public:
179   Gdb_index_info_reader(bool is_type_unit,
180                         Relobj* object,
181                         const unsigned char* symbols,
182                         off_t symbols_size,
183                         unsigned int shndx,
184                         unsigned int reloc_shndx,
185                         unsigned int reloc_type,
186                         Gdb_index* gdb_index)
187     : Dwarf_info_reader(is_type_unit, object, symbols, symbols_size, shndx,
188                         reloc_shndx, reloc_type),
189       gdb_index_(gdb_index), cu_index_(0), cu_language_(0)
190   { }
191
192   ~Gdb_index_info_reader()
193   { this->clear_declarations(); }
194
195   // Print usage statistics.
196   static void
197   print_stats();
198
199  protected:
200   // Visit a compilation unit.
201   virtual void
202   visit_compilation_unit(off_t cu_offset, off_t cu_length, Dwarf_die*);
203
204   // Visit a type unit.
205   virtual void
206   visit_type_unit(off_t tu_offset, off_t tu_length, off_t type_offset,
207                   uint64_t signature, Dwarf_die*);
208
209  private:
210   // A map for recording DIEs we've seen that may be referred to be
211   // later DIEs (via DW_AT_specification or DW_AT_abstract_origin).
212   // The map is indexed by a DIE offset within the compile unit.
213   // PARENT_OFFSET_ is the offset of the DIE that represents the
214   // outer context, and NAME_ is a pointer to a component of the
215   // fully-qualified name.
216   // Normally, the names we point to are in a string table, so we don't
217   // have to manage them, but when we have a fully-qualified name
218   // computed, we put it in the table, and set PARENT_OFFSET_ to -1
219   // indicate a string that we are managing.
220   struct Declaration_pair
221   {
222     Declaration_pair(off_t parent_offset, const char* name)
223       : parent_offset_(parent_offset), name_(name)
224     { }
225
226     off_t parent_offset_;
227     const char* name_; 
228   };
229   typedef Unordered_map<off_t, Declaration_pair> Declaration_map;
230
231   // Visit a top-level DIE.
232   void
233   visit_top_die(Dwarf_die* die);
234
235   // Visit the children of a DIE.
236   void
237   visit_children(Dwarf_die* die, Dwarf_die* context);
238
239   // Visit a DIE.
240   void
241   visit_die(Dwarf_die* die, Dwarf_die* context);
242
243   // Visit the children of a DIE.
244   void
245   visit_children_for_decls(Dwarf_die* die);
246
247   // Visit a DIE.
248   void
249   visit_die_for_decls(Dwarf_die* die, Dwarf_die* context);
250
251   // Guess a fully-qualified name for a class type, based on member function
252   // linkage names.
253   std::string
254   guess_full_class_name(Dwarf_die* die);
255
256   // Add a declaration DIE to the table of declarations.
257   void
258   add_declaration(Dwarf_die* die, Dwarf_die* context);
259
260   // Add a declaration whose fully-qualified name is already known.
261   void
262   add_declaration_with_full_name(Dwarf_die* die, const char* full_name);
263
264   // Return the context for a DIE whose parent is at DIE_OFFSET.
265   std::string
266   get_context(off_t die_offset);
267
268   // Construct a fully-qualified name for DIE.
269   std::string
270   get_qualified_name(Dwarf_die* die, Dwarf_die* context);
271
272   // Record the address ranges for a compilation unit.
273   void
274   record_cu_ranges(Dwarf_die* die);
275
276   // Wrapper for read_pubtable.
277   bool
278   read_pubnames_and_pubtypes(Dwarf_die* die);
279
280   // Read the .debug_pubnames and .debug_pubtypes tables.
281   bool
282   read_pubtable(Dwarf_pubnames_table* table, off_t offset);
283
284   // Clear the declarations map.
285   void
286   clear_declarations();
287
288   // The Gdb_index section.
289   Gdb_index* gdb_index_;
290   // The current CU index (negative for a TU).
291   int cu_index_;
292   // The language of the current CU or TU.
293   unsigned int cu_language_;
294   // Map from DIE offset to (parent offset, name) pair,
295   // for DW_AT_specification.
296   Declaration_map declarations_;
297
298   // Statistics.
299   // Total number of DWARF compilation units processed.
300   static unsigned int dwarf_cu_count;
301   // Number of DWARF compilation units with pubnames/pubtypes.
302   static unsigned int dwarf_cu_nopubnames_count;
303   // Total number of DWARF type units processed.
304   static unsigned int dwarf_tu_count;
305   // Number of DWARF type units with pubnames/pubtypes.
306   static unsigned int dwarf_tu_nopubnames_count;
307 };
308
309 // Total number of DWARF compilation units processed.
310 unsigned int Gdb_index_info_reader::dwarf_cu_count = 0;
311 // Number of DWARF compilation units without pubnames/pubtypes.
312 unsigned int Gdb_index_info_reader::dwarf_cu_nopubnames_count = 0;
313 // Total number of DWARF type units processed.
314 unsigned int Gdb_index_info_reader::dwarf_tu_count = 0;
315 // Number of DWARF type units without pubnames/pubtypes.
316 unsigned int Gdb_index_info_reader::dwarf_tu_nopubnames_count = 0;
317
318 // Process a compilation unit and parse its child DIE.
319
320 void
321 Gdb_index_info_reader::visit_compilation_unit(off_t cu_offset, off_t cu_length,
322                                               Dwarf_die* root_die)
323 {
324   ++Gdb_index_info_reader::dwarf_cu_count;
325   this->cu_index_ = this->gdb_index_->add_comp_unit(cu_offset, cu_length);
326   this->visit_top_die(root_die);
327 }
328
329 // Process a type unit and parse its child DIE.
330
331 void
332 Gdb_index_info_reader::visit_type_unit(off_t tu_offset, off_t,
333                                        off_t type_offset, uint64_t signature,
334                                        Dwarf_die* root_die)
335 {
336   ++Gdb_index_info_reader::dwarf_tu_count;
337   // Use a negative index to flag this as a TU instead of a CU.
338   this->cu_index_ = -1 - this->gdb_index_->add_type_unit(tu_offset, type_offset,
339                                                          signature);
340   this->visit_top_die(root_die);
341 }
342
343 // Process a top-level DIE.
344 // For compile_unit DIEs, record the address ranges.  For all
345 // interesting tags, add qualified names to the symbol table
346 // and process interesting children.  We may need to process
347 // certain children just for saving declarations that might be
348 // referenced by later DIEs with a DW_AT_specification attribute.
349
350 void
351 Gdb_index_info_reader::visit_top_die(Dwarf_die* die)
352 {
353   this->clear_declarations();
354
355   switch (die->tag())
356     {
357       case elfcpp::DW_TAG_compile_unit:
358       case elfcpp::DW_TAG_type_unit:
359         this->cu_language_ = die->int_attribute(elfcpp::DW_AT_language);
360         if (die->tag() == elfcpp::DW_TAG_compile_unit)
361           this->record_cu_ranges(die);
362         // If there is a pubnames and/or pubtypes section for this
363         // compilation unit, use those; otherwise, parse the DWARF
364         // info to extract the names.
365         if (!this->read_pubnames_and_pubtypes(die))
366           {
367             // Check for languages that require specialized knowledge to
368             // construct fully-qualified names, that we don't yet support.
369             if (this->cu_language_ == elfcpp::DW_LANG_Ada83
370                 || this->cu_language_ == elfcpp::DW_LANG_Fortran77
371                 || this->cu_language_ == elfcpp::DW_LANG_Fortran90
372                 || this->cu_language_ == elfcpp::DW_LANG_Java
373                 || this->cu_language_ == elfcpp::DW_LANG_Ada95
374                 || this->cu_language_ == elfcpp::DW_LANG_Fortran95
375                 || this->cu_language_ == elfcpp::DW_LANG_Fortran03
376                 || this->cu_language_ == elfcpp::DW_LANG_Fortran08)
377               {
378                 gold_warning(_("%s: --gdb-index currently supports "
379                                "only C and C++ languages"),
380                              this->object()->name().c_str());
381                 return;
382               }
383             if (die->tag() == elfcpp::DW_TAG_compile_unit)
384               ++Gdb_index_info_reader::dwarf_cu_nopubnames_count;
385             else
386               ++Gdb_index_info_reader::dwarf_tu_nopubnames_count;
387             this->visit_children(die, NULL);
388           }
389         break;
390       default:
391         // The top level DIE should be one of the above.
392         gold_warning(_("%s: top level DIE is not DW_TAG_compile_unit "
393                        "or DW_TAG_type_unit"),
394                      this->object()->name().c_str());
395         return;
396     }
397 }
398
399 // Visit the children of PARENT, looking for symbols to add to the index.
400 // CONTEXT points to the DIE to use for constructing the qualified name --
401 // NULL if PARENT is the top-level DIE; otherwise it is the same as PARENT.
402
403 void
404 Gdb_index_info_reader::visit_children(Dwarf_die* parent, Dwarf_die* context)
405 {
406   off_t next_offset = 0;
407   for (off_t die_offset = parent->child_offset();
408        die_offset != 0;
409        die_offset = next_offset)
410     {
411       Dwarf_die die(this, die_offset, parent);
412       if (die.tag() == 0)
413         break;
414       this->visit_die(&die, context);
415       next_offset = die.sibling_offset();
416     }
417 }
418
419 // Visit a child DIE, looking for symbols to add to the index.
420 // CONTEXT is the parent DIE, used for constructing the qualified name;
421 // it is NULL if the parent DIE is the top-level DIE.
422
423 void
424 Gdb_index_info_reader::visit_die(Dwarf_die* die, Dwarf_die* context)
425 {
426   switch (die->tag())
427     {
428       case elfcpp::DW_TAG_subprogram:
429       case elfcpp::DW_TAG_constant:
430       case elfcpp::DW_TAG_variable:
431       case elfcpp::DW_TAG_enumerator:
432       case elfcpp::DW_TAG_base_type:
433         if (die->is_declaration())
434           this->add_declaration(die, context);
435         else
436           {
437             // If the DIE is not a declaration, add it to the index.
438             std::string full_name = this->get_qualified_name(die, context);
439             if (!full_name.empty())
440               this->gdb_index_->add_symbol(this->cu_index_,
441                                            full_name.c_str(), 0);
442           }
443         break;
444       case elfcpp::DW_TAG_typedef:
445       case elfcpp::DW_TAG_union_type:
446       case elfcpp::DW_TAG_class_type:
447       case elfcpp::DW_TAG_interface_type:
448       case elfcpp::DW_TAG_structure_type:
449       case elfcpp::DW_TAG_enumeration_type:
450       case elfcpp::DW_TAG_subrange_type:
451       case elfcpp::DW_TAG_namespace:
452         {
453           std::string full_name;
454           
455           // For classes at the top level, we need to look for a
456           // member function with a linkage name in order to get
457           // the properly-canonicalized name.
458           if (context == NULL
459               && (die->tag() == elfcpp::DW_TAG_class_type
460                   || die->tag() == elfcpp::DW_TAG_structure_type
461                   || die->tag() == elfcpp::DW_TAG_union_type))
462             full_name.assign(this->guess_full_class_name(die));
463
464           // Because we will visit the children, we need to add this DIE
465           // to the declarations table.
466           if (full_name.empty())
467             this->add_declaration(die, context);
468           else
469             this->add_declaration_with_full_name(die, full_name.c_str());
470
471           // If the DIE is not a declaration, add it to the index.
472           // Gdb stores a namespace in the index even when it is
473           // a declaration.
474           if (die->tag() == elfcpp::DW_TAG_namespace
475               || !die->is_declaration())
476             {
477               if (full_name.empty())
478                 full_name = this->get_qualified_name(die, context);
479               if (!full_name.empty())
480                 this->gdb_index_->add_symbol(this->cu_index_,
481                                              full_name.c_str(), 0);
482             }
483
484           // We're interested in the children only for namespaces and
485           // enumeration types.  For enumeration types, we do not include
486           // the enumeration tag as part of the full name.  For other tags,
487           // visit the children only to collect declarations.
488           if (die->tag() == elfcpp::DW_TAG_namespace
489               || die->tag() == elfcpp::DW_TAG_enumeration_type)
490             this->visit_children(die, die);
491           else
492             this->visit_children_for_decls(die);
493         }
494         break;
495       default:
496         break;
497     }
498 }
499
500 // Visit the children of PARENT, looking only for declarations that
501 // may be referenced by later specification DIEs.
502
503 void
504 Gdb_index_info_reader::visit_children_for_decls(Dwarf_die* parent)
505 {
506   off_t next_offset = 0;
507   for (off_t die_offset = parent->child_offset();
508        die_offset != 0;
509        die_offset = next_offset)
510     {
511       Dwarf_die die(this, die_offset, parent);
512       if (die.tag() == 0)
513         break;
514       this->visit_die_for_decls(&die, parent);
515       next_offset = die.sibling_offset();
516     }
517 }
518
519 // Visit a child DIE, looking only for declarations that
520 // may be referenced by later specification DIEs.
521
522 void
523 Gdb_index_info_reader::visit_die_for_decls(Dwarf_die* die, Dwarf_die* context)
524 {
525   switch (die->tag())
526     {
527       case elfcpp::DW_TAG_subprogram:
528       case elfcpp::DW_TAG_constant:
529       case elfcpp::DW_TAG_variable:
530       case elfcpp::DW_TAG_enumerator:
531       case elfcpp::DW_TAG_base_type:
532         {
533           if (die->is_declaration())
534             this->add_declaration(die, context);
535         }
536         break;
537       case elfcpp::DW_TAG_typedef:
538       case elfcpp::DW_TAG_union_type:
539       case elfcpp::DW_TAG_class_type:
540       case elfcpp::DW_TAG_interface_type:
541       case elfcpp::DW_TAG_structure_type:
542       case elfcpp::DW_TAG_enumeration_type:
543       case elfcpp::DW_TAG_subrange_type:
544       case elfcpp::DW_TAG_namespace:
545         {
546           if (die->is_declaration())
547             this->add_declaration(die, context);
548           this->visit_children_for_decls(die);
549         }
550         break;
551       default:
552         break;
553     }
554 }
555
556 // Extract the class name from the linkage name of a member function.
557 // This code is adapted from ../gdb/cp-support.c.
558
559 #define d_left(dc) (dc)->u.s_binary.left
560 #define d_right(dc) (dc)->u.s_binary.right
561
562 static char*
563 class_name_from_linkage_name(const char* linkage_name)
564 {
565   void* storage;
566   struct demangle_component* tree =
567       cplus_demangle_v3_components(linkage_name, DMGL_NO_OPTS, &storage);
568   if (tree == NULL)
569     return NULL;
570
571   int done = 0;
572
573   // First strip off any qualifiers, if we have a function or
574   // method.
575   while (!done)
576     switch (tree->type)
577       {
578         case DEMANGLE_COMPONENT_CONST:
579         case DEMANGLE_COMPONENT_RESTRICT:
580         case DEMANGLE_COMPONENT_VOLATILE:
581         case DEMANGLE_COMPONENT_CONST_THIS:
582         case DEMANGLE_COMPONENT_RESTRICT_THIS:
583         case DEMANGLE_COMPONENT_VOLATILE_THIS:
584         case DEMANGLE_COMPONENT_VENDOR_TYPE_QUAL:
585           tree = d_left(tree);
586           break;
587         default:
588           done = 1;
589           break;
590       }
591
592   // If what we have now is a function, discard the argument list.
593   if (tree->type == DEMANGLE_COMPONENT_TYPED_NAME)
594     tree = d_left(tree);
595
596   // If what we have now is a template, strip off the template
597   // arguments.  The left subtree may be a qualified name.
598   if (tree->type == DEMANGLE_COMPONENT_TEMPLATE)
599     tree = d_left(tree);
600
601   // What we have now should be a name, possibly qualified.
602   // Additional qualifiers could live in the left subtree or the right
603   // subtree.  Find the last piece.
604   done = 0;
605   struct demangle_component* prev_comp = NULL;
606   struct demangle_component* cur_comp = tree;
607   while (!done)
608     switch (cur_comp->type)
609       {
610         case DEMANGLE_COMPONENT_QUAL_NAME:
611         case DEMANGLE_COMPONENT_LOCAL_NAME:
612           prev_comp = cur_comp;
613           cur_comp = d_right(cur_comp);
614           break;
615         case DEMANGLE_COMPONENT_TEMPLATE:
616         case DEMANGLE_COMPONENT_NAME:
617         case DEMANGLE_COMPONENT_CTOR:
618         case DEMANGLE_COMPONENT_DTOR:
619         case DEMANGLE_COMPONENT_OPERATOR:
620         case DEMANGLE_COMPONENT_EXTENDED_OPERATOR:
621           done = 1;
622           break;
623         default:
624           done = 1;
625           cur_comp = NULL;
626           break;
627       }
628
629   char* ret = NULL;
630   if (cur_comp != NULL && prev_comp != NULL)
631     {
632       // We want to discard the rightmost child of PREV_COMP.
633       *prev_comp = *d_left(prev_comp);
634       size_t allocated_size;
635       ret = cplus_demangle_print(DMGL_NO_OPTS, tree, 30, &allocated_size);
636     }
637
638   free(storage);
639   return ret;
640 }
641
642 // Guess a fully-qualified name for a class type, based on member function
643 // linkage names.  This is needed for class/struct/union types at the
644 // top level, because GCC does not always properly embed them within
645 // the namespace.  As in gdb, we look for a member function with a linkage
646 // name and extract the qualified name from the demangled name.
647
648 std::string
649 Gdb_index_info_reader::guess_full_class_name(Dwarf_die* die)
650 {
651   std::string full_name;
652   off_t next_offset = 0;
653   
654   // This routine scans ahead in the DIE structure, possibly advancing
655   // the relocation tracker beyond the current DIE.  We need to checkpoint
656   // the tracker and reset it when we're done.
657   uint64_t checkpoint = this->get_reloc_checkpoint();
658
659   for (off_t child_offset = die->child_offset();
660        child_offset != 0;
661        child_offset = next_offset)
662     {
663       Dwarf_die child(this, child_offset, die);
664       if (child.tag() == 0)
665         break;
666       if (child.tag() == elfcpp::DW_TAG_subprogram)
667         {
668           const char* linkage_name = child.linkage_name();
669           if (linkage_name != NULL)
670             {
671               char* guess = class_name_from_linkage_name(linkage_name);
672               if (guess != NULL)
673                 {
674                   full_name.assign(guess);
675                   free(guess);
676                   break;
677                 }
678             }
679         }
680       next_offset = child.sibling_offset();
681     }
682
683   this->reset_relocs(checkpoint);
684   return full_name;
685 }
686
687 // Add a declaration DIE to the table of declarations.
688
689 void
690 Gdb_index_info_reader::add_declaration(Dwarf_die* die, Dwarf_die* context)
691 {
692   const char* name = die->name();
693
694   off_t parent_offset = context != NULL ? context->offset() : 0;
695
696   // If this DIE has a DW_AT_specification or DW_AT_abstract_origin
697   // attribute, use the parent and name from the earlier declaration.
698   off_t spec = die->specification();
699   if (spec == 0)
700     spec = die->abstract_origin();
701   if (spec > 0)
702     {
703       Declaration_map::iterator it = this->declarations_.find(spec);
704       if (it != this->declarations_.end())
705         {
706           parent_offset = it->second.parent_offset_;
707           name = it->second.name_;
708         }
709     }
710
711   if (name == NULL)
712     {
713       if (die->tag() == elfcpp::DW_TAG_namespace)
714         name = "(anonymous namespace)";
715       else if (die->tag() == elfcpp::DW_TAG_union_type)
716         name = "(anonymous union)";
717       else
718         name = "(unknown)";
719     }
720
721   Declaration_pair decl(parent_offset, name);
722   this->declarations_.insert(std::make_pair(die->offset(), decl));
723 }
724
725 // Add a declaration whose fully-qualified name is already known.
726 // In the case where we had to get the canonical name by demangling
727 // a linkage name, this ensures we use that name instead of the one
728 // provided in DW_AT_name.
729
730 void
731 Gdb_index_info_reader::add_declaration_with_full_name(
732     Dwarf_die* die,
733     const char* full_name)
734 {
735   // We need to copy the name.
736   int len = strlen(full_name);
737   char* copy = new char[len + 1];
738   memcpy(copy, full_name, len + 1);
739
740   // Flag that we now manage the memory this points to.
741   Declaration_pair decl(-1, copy);
742   this->declarations_.insert(std::make_pair(die->offset(), decl));
743 }
744
745 // Return the context for a DIE whose parent is at DIE_OFFSET.
746
747 std::string
748 Gdb_index_info_reader::get_context(off_t die_offset)
749 {
750   std::string context;
751   Declaration_map::iterator it = this->declarations_.find(die_offset);
752   if (it != this->declarations_.end())
753     {
754       off_t parent_offset = it->second.parent_offset_;
755       if (parent_offset > 0)
756         {
757           context = get_context(parent_offset);
758           context.append("::");
759         }
760       if (it->second.name_ != NULL)
761         context.append(it->second.name_);
762     }
763   return context;
764 }
765
766 // Construct the fully-qualified name for DIE.
767
768 std::string
769 Gdb_index_info_reader::get_qualified_name(Dwarf_die* die, Dwarf_die* context)
770 {
771   std::string full_name;
772   const char* name = die->name();
773
774   off_t parent_offset = context != NULL ? context->offset() : 0;
775
776   // If this DIE has a DW_AT_specification or DW_AT_abstract_origin
777   // attribute, use the parent and name from the earlier declaration.
778   off_t spec = die->specification();
779   if (spec == 0)
780     spec = die->abstract_origin();
781   if (spec > 0)
782     {
783       Declaration_map::iterator it = this->declarations_.find(spec);
784       if (it != this->declarations_.end())
785         {
786           parent_offset = it->second.parent_offset_;
787           name = it->second.name_;
788         }
789     }
790
791   if (name == NULL && die->tag() == elfcpp::DW_TAG_namespace)
792     name = "(anonymous namespace)";
793   else if (name == NULL)
794     return full_name;
795
796   // If this is an enumerator constant, skip the immediate parent,
797   // which is the enumeration tag.
798   if (die->tag() == elfcpp::DW_TAG_enumerator)
799     {
800       Declaration_map::iterator it = this->declarations_.find(parent_offset);
801       if (it != this->declarations_.end())
802         parent_offset = it->second.parent_offset_;
803     }
804
805   if (parent_offset > 0)
806     {
807       full_name.assign(this->get_context(parent_offset));
808       full_name.append("::");
809     }
810   full_name.append(name);
811
812   return full_name;
813 }
814
815 // Record the address ranges for a compilation unit.
816
817 void
818 Gdb_index_info_reader::record_cu_ranges(Dwarf_die* die)
819 {
820   unsigned int shndx;
821   unsigned int shndx2;
822
823   off_t ranges_offset = die->ref_attribute(elfcpp::DW_AT_ranges, &shndx);
824   if (ranges_offset != -1)
825     {
826       Dwarf_range_list* ranges = this->read_range_list(shndx, ranges_offset);
827       if (ranges != NULL)
828         this->gdb_index_->add_address_range_list(this->object(),
829                                                  this->cu_index_, ranges);
830       return;
831     }
832
833   off_t low_pc = die->address_attribute(elfcpp::DW_AT_low_pc, &shndx);
834   off_t high_pc = die->address_attribute(elfcpp::DW_AT_high_pc, &shndx2);
835   if (high_pc == -1)
836     {
837       high_pc = die->uint_attribute(elfcpp::DW_AT_high_pc);
838       high_pc += low_pc;
839       shndx2 = shndx;
840     }
841   if ((low_pc != 0 || high_pc != 0) && low_pc != -1)
842     {
843       if (shndx != shndx2)
844         {
845           gold_warning(_("%s: DWARF info may be corrupt; low_pc and high_pc "
846                          "are in different sections"),
847                        this->object()->name().c_str());
848           return;
849         }
850       if (shndx == 0 || this->object()->is_section_included(shndx))
851         {
852           Dwarf_range_list* ranges = new Dwarf_range_list();
853           ranges->add(shndx, low_pc, high_pc);
854           this->gdb_index_->add_address_range_list(this->object(),
855                                                    this->cu_index_, ranges);
856         }
857     }
858 }
859
860 // Read table and add the relevant names to the index.  Returns true
861 // if any names were added.
862
863 bool
864 Gdb_index_info_reader::read_pubtable(Dwarf_pubnames_table* table, off_t offset)
865 {
866   // If we couldn't read the section when building the cu_pubname_map,
867   // then we won't find any pubnames now.
868   if (table == NULL)
869     return false;
870
871   if (!table->read_header(offset))
872     return false;
873   while (true)
874     {
875       uint8_t flag_byte;
876       const char* name = table->next_name(&flag_byte);
877       if (name == NULL)
878         break;
879
880       this->gdb_index_->add_symbol(this->cu_index_, name, flag_byte);
881     }
882   return true;
883 }
884
885 // Read the .debug_pubnames and .debug_pubtypes tables for the CU or TU.
886 // Returns TRUE if either a pubnames or pubtypes section was found.
887
888 bool
889 Gdb_index_info_reader::read_pubnames_and_pubtypes(Dwarf_die* die)
890 {
891   // If this is a skeleton debug-type die (generated via
892   // -gsplit-dwarf), then the associated pubnames should have been
893   // read along with the corresponding CU.  In any case, there isn't
894   // enough info inside to build a gdb index entry.
895   if (die->tag() == elfcpp::DW_TAG_type_unit
896       && die->string_attribute(elfcpp::DW_AT_GNU_dwo_name))
897     return true;
898
899   // We use stmt_list_off as a unique identifier for the
900   // compilation unit and its associated type units.
901   unsigned int shndx;
902   off_t stmt_list_off = die->ref_attribute (elfcpp::DW_AT_stmt_list,
903                                             &shndx);
904   // Look for the attr as either a flag or a ref.
905   off_t offset = die->ref_attribute(elfcpp::DW_AT_GNU_pubnames, &shndx);
906
907   // Newer versions of GCC generate CUs, but not TUs, with
908   // DW_AT_FORM_flag_present.
909   unsigned int flag = die->uint_attribute(elfcpp::DW_AT_GNU_pubnames);
910   if (offset == -1 && flag == 0)
911     {
912       // Didn't find the attribute.
913       if (die->tag() == elfcpp::DW_TAG_type_unit)
914         {
915           // If die is a TU, then it might correspond to a CU which we
916           // have read. If it does, then no need to read the pubnames.
917           // If it doesn't, then the caller will have to parse the
918           // dies manually to find the names.
919           return this->gdb_index_->pubnames_read(this->object(),
920                                                  stmt_list_off);
921         }
922       else
923         {
924           // No attribute on the CU means that no pubnames were read.
925           return false;
926         }
927     }
928
929   // We found the attribute, so we can check if the corresponding
930   // pubnames have been read.
931   if (this->gdb_index_->pubnames_read(this->object(), stmt_list_off))
932     return true;
933
934   this->gdb_index_->set_pubnames_read(this->object(), stmt_list_off);
935
936   // We have an attribute, and the pubnames haven't been read, so read
937   // them.
938   bool names = false;
939   // In some of the cases, we could rely on the previous value of
940   // offset here, but sorting out which cases complicates the logic
941   // enough that it isn't worth it. So just look up the offset again.
942   offset = this->gdb_index_->find_pubname_offset(this->cu_offset());
943   names = this->read_pubtable(this->gdb_index_->pubnames_table(), offset);
944
945   bool types = false;
946   offset = this->gdb_index_->find_pubtype_offset(this->cu_offset());
947   types = this->read_pubtable(this->gdb_index_->pubtypes_table(), offset);
948   return names || types;
949 }
950
951 // Clear the declarations map.
952 void
953 Gdb_index_info_reader::clear_declarations()
954 {
955   // Free strings in memory we manage.
956   for (Declaration_map::iterator it = this->declarations_.begin();
957        it != this->declarations_.end();
958        ++it)
959     {
960       if (it->second.parent_offset_ == -1)
961         delete[] it->second.name_;
962     }
963
964   this->declarations_.clear();
965 }
966
967 // Print usage statistics.
968 void
969 Gdb_index_info_reader::print_stats()
970 {
971   fprintf(stderr, _("%s: DWARF CUs: %u\n"),
972           program_name, Gdb_index_info_reader::dwarf_cu_count);
973   fprintf(stderr, _("%s: DWARF CUs without pubnames/pubtypes: %u\n"),
974           program_name, Gdb_index_info_reader::dwarf_cu_nopubnames_count);
975   fprintf(stderr, _("%s: DWARF TUs: %u\n"),
976           program_name, Gdb_index_info_reader::dwarf_tu_count);
977   fprintf(stderr, _("%s: DWARF TUs without pubnames/pubtypes: %u\n"),
978           program_name, Gdb_index_info_reader::dwarf_tu_nopubnames_count);
979 }
980
981 // Class Gdb_index.
982
983 // Construct the .gdb_index section.
984
985 Gdb_index::Gdb_index(Output_section* gdb_index_section)
986   : Output_section_data(4),
987     pubnames_table_(NULL),
988     pubtypes_table_(NULL),
989     gdb_index_section_(gdb_index_section),
990     comp_units_(),
991     type_units_(),
992     ranges_(),
993     cu_vector_list_(),
994     cu_vector_offsets_(NULL),
995     stringpool_(),
996     tu_offset_(0),
997     addr_offset_(0),
998     symtab_offset_(0),
999     cu_pool_offset_(0),
1000     stringpool_offset_(0),
1001     pubnames_object_(NULL),
1002     stmt_list_offset_(-1)
1003 {
1004   this->gdb_symtab_ = new Gdb_hashtab<Gdb_symbol>();
1005 }
1006
1007 Gdb_index::~Gdb_index()
1008 {
1009   // Free the memory used by the symbol table.
1010   delete this->gdb_symtab_;
1011   // Free the memory used by the CU vectors.
1012   for (unsigned int i = 0; i < this->cu_vector_list_.size(); ++i)
1013     delete this->cu_vector_list_[i];
1014 }
1015
1016
1017 // Scan the pubnames and pubtypes sections and build a map of the
1018 // various cus and tus they refer to, so we can process the entries
1019 // when we encounter the die for that cu or tu.
1020 // Return the just-read table so it can be cached.
1021
1022 Dwarf_pubnames_table*
1023 Gdb_index::map_pubtable_to_dies(unsigned int attr,
1024                                 Gdb_index_info_reader* dwinfo,
1025                                 Relobj* object,
1026                                 const unsigned char* symbols,
1027                                 off_t symbols_size)
1028 {
1029   uint64_t section_offset = 0;
1030   Dwarf_pubnames_table* table;
1031   Pubname_offset_map* map;
1032
1033   if (attr == elfcpp::DW_AT_GNU_pubnames)
1034     {
1035       table = new Dwarf_pubnames_table(dwinfo, false);
1036       map = &this->cu_pubname_map_;
1037     }
1038   else
1039     {
1040       table = new Dwarf_pubnames_table(dwinfo, true);
1041       map = &this->cu_pubtype_map_;
1042     }
1043
1044   map->clear();
1045   if (!table->read_section(object, symbols, symbols_size))
1046     return NULL;
1047
1048   while (table->read_header(section_offset))
1049     {
1050       map->insert(std::make_pair(table->cu_offset(), section_offset));
1051       section_offset += table->subsection_size();
1052     }
1053
1054   return table;
1055 }
1056
1057 // Wrapper for map_pubtable_to_dies
1058
1059 void
1060 Gdb_index::map_pubnames_and_types_to_dies(Gdb_index_info_reader* dwinfo,
1061                                           Relobj* object,
1062                                           const unsigned char* symbols,
1063                                           off_t symbols_size)
1064 {
1065   // This is a new object, so reset the relevant variables.
1066   this->pubnames_object_ = object;
1067   this->stmt_list_offset_ = -1;
1068
1069   delete this->pubnames_table_;
1070   this->pubnames_table_
1071       = this->map_pubtable_to_dies(elfcpp::DW_AT_GNU_pubnames, dwinfo,
1072                                    object, symbols, symbols_size);
1073   delete this->pubtypes_table_;
1074   this->pubtypes_table_
1075       = this->map_pubtable_to_dies(elfcpp::DW_AT_GNU_pubtypes, dwinfo,
1076                                    object, symbols, symbols_size);
1077 }
1078
1079 // Given a cu_offset, find the associated section of the pubnames
1080 // table.
1081
1082 off_t
1083 Gdb_index::find_pubname_offset(off_t cu_offset)
1084 {
1085   Pubname_offset_map::iterator it = this->cu_pubname_map_.find(cu_offset);
1086   if (it != this->cu_pubname_map_.end())
1087     return it->second;
1088   return -1;
1089 }
1090
1091 // Given a cu_offset, find the associated section of the pubnames
1092 // table.
1093
1094 off_t
1095 Gdb_index::find_pubtype_offset(off_t cu_offset)
1096 {
1097   Pubname_offset_map::iterator it = this->cu_pubtype_map_.find(cu_offset);
1098   if (it != this->cu_pubtype_map_.end())
1099     return it->second;
1100   return -1;
1101 }
1102
1103 // Scan a .debug_info or .debug_types input section.
1104
1105 void
1106 Gdb_index::scan_debug_info(bool is_type_unit,
1107                            Relobj* object,
1108                            const unsigned char* symbols,
1109                            off_t symbols_size,
1110                            unsigned int shndx,
1111                            unsigned int reloc_shndx,
1112                            unsigned int reloc_type)
1113 {
1114   Gdb_index_info_reader dwinfo(is_type_unit, object,
1115                                symbols, symbols_size,
1116                                shndx, reloc_shndx,
1117                                reloc_type, this);
1118   if (object != this->pubnames_object_)
1119     map_pubnames_and_types_to_dies(&dwinfo, object, symbols, symbols_size);
1120   dwinfo.parse();
1121 }
1122
1123 // Add a symbol.
1124
1125 void
1126 Gdb_index::add_symbol(int cu_index, const char* sym_name, uint8_t flags)
1127 {
1128   unsigned int hash = mapped_index_string_hash(
1129       reinterpret_cast<const unsigned char*>(sym_name));
1130   Gdb_symbol* sym = new Gdb_symbol();
1131   this->stringpool_.add(sym_name, true, &sym->name_key);
1132   sym->hashval = hash;
1133   sym->cu_vector_index = 0;
1134
1135   Gdb_symbol* found = this->gdb_symtab_->add(sym);
1136   if (found == sym)
1137     {
1138       // New symbol -- allocate a new CU index vector.
1139       found->cu_vector_index = this->cu_vector_list_.size();
1140       this->cu_vector_list_.push_back(new Cu_vector());
1141     }
1142   else
1143     {
1144       // Found an existing symbol -- append to the existing
1145       // CU index vector.
1146       delete sym;
1147     }
1148
1149   // Add the CU index to the vector list for this symbol,
1150   // if it's not already on the list.  We only need to
1151   // check the last added entry.
1152   Cu_vector* cu_vec = this->cu_vector_list_[found->cu_vector_index];
1153   if (cu_vec->size() == 0
1154       || cu_vec->back().first != cu_index
1155       || cu_vec->back().second != flags)
1156     cu_vec->push_back(std::make_pair(cu_index, flags));
1157 }
1158
1159 // Return TRUE if we have already processed the pubnames associated
1160 // with the statement list at the given OFFSET.
1161
1162 bool
1163 Gdb_index::pubnames_read(const Relobj* object, off_t offset)
1164 {
1165   bool ret = (this->pubnames_object_ == object
1166               && this->stmt_list_offset_ == offset);
1167   return ret;
1168 }
1169
1170 // Record that we have processed the pubnames associated with the
1171 // statement list for OBJECT at the given OFFSET.
1172
1173 void
1174 Gdb_index::set_pubnames_read(const Relobj* object, off_t offset)
1175 {
1176   this->pubnames_object_ = object;
1177   this->stmt_list_offset_ = offset;
1178 }
1179
1180 // Set the size of the .gdb_index section.
1181
1182 void
1183 Gdb_index::set_final_data_size()
1184 {
1185   // Finalize the string pool.
1186   this->stringpool_.set_string_offsets();
1187
1188   // Compute the total size of the CU vectors.
1189   // For each CU vector, include one entry for the count at the
1190   // beginning of the vector.
1191   unsigned int cu_vector_count = this->cu_vector_list_.size();
1192   unsigned int cu_vector_size = 0;
1193   this->cu_vector_offsets_ = new off_t[cu_vector_count];
1194   for (unsigned int i = 0; i < cu_vector_count; ++i)
1195     {
1196       Cu_vector* cu_vec = this->cu_vector_list_[i];
1197       cu_vector_offsets_[i] = cu_vector_size;
1198       cu_vector_size += gdb_index_offset_size * (cu_vec->size() + 1);
1199     }
1200
1201   // Assign relative offsets to each portion of the index,
1202   // and find the total size of the section.
1203   section_size_type data_size = gdb_index_hdr_size;
1204   data_size += this->comp_units_.size() * gdb_index_cu_size;
1205   this->tu_offset_ = data_size;
1206   data_size += this->type_units_.size() * gdb_index_tu_size;
1207   this->addr_offset_ = data_size;
1208   for (unsigned int i = 0; i < this->ranges_.size(); ++i)
1209     data_size += this->ranges_[i].ranges->size() * gdb_index_addr_size;
1210   this->symtab_offset_ = data_size;
1211   data_size += this->gdb_symtab_->capacity() * gdb_index_sym_size;
1212   this->cu_pool_offset_ = data_size;
1213   data_size += cu_vector_size;
1214   this->stringpool_offset_ = data_size;
1215   data_size += this->stringpool_.get_strtab_size();
1216
1217   this->set_data_size(data_size);
1218 }
1219
1220 // Write the data to the file.
1221
1222 void
1223 Gdb_index::do_write(Output_file* of)
1224 {
1225   const off_t off = this->offset();
1226   const off_t oview_size = this->data_size();
1227   unsigned char* const oview = of->get_output_view(off, oview_size);
1228   unsigned char* pov = oview;
1229
1230   // Write the file header.
1231   // (1) Version number.
1232   elfcpp::Swap<32, false>::writeval(pov, gdb_index_version);
1233   pov += 4;
1234   // (2) Offset of the CU list.
1235   elfcpp::Swap<32, false>::writeval(pov, gdb_index_hdr_size);
1236   pov += 4;
1237   // (3) Offset of the types CU list.
1238   elfcpp::Swap<32, false>::writeval(pov, this->tu_offset_);
1239   pov += 4;
1240   // (4) Offset of the address area.
1241   elfcpp::Swap<32, false>::writeval(pov, this->addr_offset_);
1242   pov += 4;
1243   // (5) Offset of the symbol table.
1244   elfcpp::Swap<32, false>::writeval(pov, this->symtab_offset_);
1245   pov += 4;
1246   // (6) Offset of the constant pool.
1247   elfcpp::Swap<32, false>::writeval(pov, this->cu_pool_offset_);
1248   pov += 4;
1249
1250   gold_assert(pov - oview == gdb_index_hdr_size);
1251
1252   // Write the CU list.
1253   unsigned int comp_units_count = this->comp_units_.size();
1254   for (unsigned int i = 0; i < comp_units_count; ++i)
1255     {
1256       const Comp_unit& cu = this->comp_units_[i];
1257       elfcpp::Swap<64, false>::writeval(pov, cu.cu_offset);
1258       elfcpp::Swap<64, false>::writeval(pov + 8, cu.cu_length);
1259       pov += 16;
1260     }
1261
1262   gold_assert(pov - oview == this->tu_offset_);
1263
1264   // Write the types CU list.
1265   for (unsigned int i = 0; i < this->type_units_.size(); ++i)
1266     {
1267       const Type_unit& tu = this->type_units_[i];
1268       elfcpp::Swap<64, false>::writeval(pov, tu.tu_offset);
1269       elfcpp::Swap<64, false>::writeval(pov + 8, tu.type_offset);
1270       elfcpp::Swap<64, false>::writeval(pov + 16, tu.type_signature);
1271       pov += 24;
1272     }
1273
1274   gold_assert(pov - oview == this->addr_offset_);
1275
1276   // Write the address area.
1277   for (unsigned int i = 0; i < this->ranges_.size(); ++i)
1278     {
1279       int cu_index = this->ranges_[i].cu_index;
1280       // Translate negative indexes, which refer to a TU, to a
1281       // logical index into a concatenated CU/TU list.
1282       if (cu_index < 0)
1283         cu_index = comp_units_count + (-1 - cu_index);
1284       Relobj* object = this->ranges_[i].object;
1285       const Dwarf_range_list& ranges = *this->ranges_[i].ranges;
1286       for (unsigned int j = 0; j < ranges.size(); ++j)
1287         {
1288           const Dwarf_range_list::Range& range = ranges[j];
1289           uint64_t base = 0;
1290           if (range.shndx > 0)
1291             {
1292               const Output_section* os = object->output_section(range.shndx);
1293               base = (os->address()
1294                       + object->output_section_offset(range.shndx));
1295             }
1296           elfcpp::Swap_aligned32<64, false>::writeval(pov, base + range.start);
1297           elfcpp::Swap_aligned32<64, false>::writeval(pov + 8,
1298                                                       base + range.end);
1299           elfcpp::Swap<32, false>::writeval(pov + 16, cu_index);
1300           pov += 20;
1301         }
1302     }
1303
1304   gold_assert(pov - oview == this->symtab_offset_);
1305
1306   // Write the symbol table.
1307   for (unsigned int i = 0; i < this->gdb_symtab_->capacity(); ++i)
1308     {
1309       const Gdb_symbol* sym = (*this->gdb_symtab_)[i];
1310       section_offset_type name_offset = 0;
1311       unsigned int cu_vector_offset = 0;
1312       if (sym != NULL)
1313         {
1314           name_offset = (this->stringpool_.get_offset_from_key(sym->name_key)
1315                          + this->stringpool_offset_ - this->cu_pool_offset_);
1316           cu_vector_offset = this->cu_vector_offsets_[sym->cu_vector_index];
1317         }
1318       elfcpp::Swap<32, false>::writeval(pov, name_offset);
1319       elfcpp::Swap<32, false>::writeval(pov + 4, cu_vector_offset);
1320       pov += 8;
1321     }
1322
1323   gold_assert(pov - oview == this->cu_pool_offset_);
1324
1325   // Write the CU vectors into the constant pool.
1326   for (unsigned int i = 0; i < this->cu_vector_list_.size(); ++i)
1327     {
1328       Cu_vector* cu_vec = this->cu_vector_list_[i];
1329       elfcpp::Swap<32, false>::writeval(pov, cu_vec->size());
1330       pov += 4;
1331       for (unsigned int j = 0; j < cu_vec->size(); ++j)
1332         {
1333           int cu_index = (*cu_vec)[j].first;
1334           uint8_t flags = (*cu_vec)[j].second;
1335           if (cu_index < 0)
1336             cu_index = comp_units_count + (-1 - cu_index);
1337           cu_index |= flags << 24;
1338           elfcpp::Swap<32, false>::writeval(pov, cu_index);
1339           pov += 4;
1340         }
1341     }
1342
1343   gold_assert(pov - oview == this->stringpool_offset_);
1344
1345   // Write the strings into the constant pool.
1346   this->stringpool_.write_to_buffer(pov, oview_size - this->stringpool_offset_);
1347
1348   of->write_output_view(off, oview_size, oview);
1349 }
1350
1351 // Print usage statistics.
1352 void
1353 Gdb_index::print_stats()
1354 {
1355   if (parameters->options().gdb_index())
1356     Gdb_index_info_reader::print_stats();
1357 }
1358
1359 } // End namespace gold.