gold/gdb-index.cc

   1 // gdb-index.cc -- generate .gdb_index section for fast debug lookup
   2
   3 // Copyright 2012 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 = 5;
  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   // Read the .debug_pubnames and .debug_pubtypes tables.
 277   bool
 278   read_pubnames_and_pubtypes(Dwarf_die* die);
 279
 280   // Clear the declarations map.
 281   void
 282   clear_declarations();
 283
 284   // The Gdb_index section.
 285   Gdb_index* gdb_index_;
 286   // The current CU index (negative for a TU).
 287   int cu_index_;
 288   // The language of the current CU or TU.
 289   unsigned int cu_language_;
 290   // Map from DIE offset to (parent offset, name) pair,
 291   // for DW_AT_specification.
 292   Declaration_map declarations_;
 293
 294   // Statistics.
 295   // Total number of DWARF compilation units processed.
 296   static unsigned int dwarf_cu_count;
 297   // Number of DWARF compilation units with pubnames/pubtypes.
 298   static unsigned int dwarf_cu_nopubnames_count;
 299   // Total number of DWARF type units processed.
 300   static unsigned int dwarf_tu_count;
 301   // Number of DWARF type units with pubnames/pubtypes.
 302   static unsigned int dwarf_tu_nopubnames_count;
 303 };
 304
 305 // Total number of DWARF compilation units processed.
 306 unsigned int Gdb_index_info_reader::dwarf_cu_count = 0;
 307 // Number of DWARF compilation units without pubnames/pubtypes.
 308 unsigned int Gdb_index_info_reader::dwarf_cu_nopubnames_count = 0;
 309 // Total number of DWARF type units processed.
 310 unsigned int Gdb_index_info_reader::dwarf_tu_count = 0;
 311 // Number of DWARF type units without pubnames/pubtypes.
 312 unsigned int Gdb_index_info_reader::dwarf_tu_nopubnames_count = 0;
 313
 314 // Process a compilation unit and parse its child DIE.
 315
 316 void
 317 Gdb_index_info_reader::visit_compilation_unit(off_t cu_offset, off_t cu_length,
 318                                               Dwarf_die* root_die)
 319 {
 320   ++Gdb_index_info_reader::dwarf_cu_count;
 321   this->cu_index_ = this->gdb_index_->add_comp_unit(cu_offset, cu_length);
 322   this->visit_top_die(root_die);
 323 }
 324
 325 // Process a type unit and parse its child DIE.
 326
 327 void
 328 Gdb_index_info_reader::visit_type_unit(off_t tu_offset, off_t,
 329                                        off_t type_offset, uint64_t signature,
 330                                        Dwarf_die* root_die)
 331 {
 332   ++Gdb_index_info_reader::dwarf_tu_count;
 333   // Use a negative index to flag this as a TU instead of a CU.
 334   this->cu_index_ = -1 - this->gdb_index_->add_type_unit(tu_offset, type_offset,
 335                                                          signature);
 336   this->visit_top_die(root_die);
 337 }
 338
 339 // Process a top-level DIE.
 340 // For compile_unit DIEs, record the address ranges.  For all
 341 // interesting tags, add qualified names to the symbol table
 342 // and process interesting children.  We may need to process
 343 // certain children just for saving declarations that might be
 344 // referenced by later DIEs with a DW_AT_specification attribute.
 345
 346 void
 347 Gdb_index_info_reader::visit_top_die(Dwarf_die* die)
 348 {
 349   this->clear_declarations();
 350
 351   switch (die->tag())
 352     {
 353       case elfcpp::DW_TAG_compile_unit:
 354       case elfcpp::DW_TAG_type_unit:
 355         this->cu_language_ = die->int_attribute(elfcpp::DW_AT_language);
 356         // Check for languages that require specialized knowledge to
 357         // construct fully-qualified names, that we don't yet support.
 358         if (this->cu_language_ == elfcpp::DW_LANG_Ada83
 359             || this->cu_language_ == elfcpp::DW_LANG_Fortran77
 360             || this->cu_language_ == elfcpp::DW_LANG_Fortran90
 361             || this->cu_language_ == elfcpp::DW_LANG_Java
 362             || this->cu_language_ == elfcpp::DW_LANG_Ada95
 363             || this->cu_language_ == elfcpp::DW_LANG_Fortran95)
 364           {
 365             gold_warning(_("%s: --gdb-index currently supports "
 366                            "only C and C++ languages"),
 367                          this->object()->name().c_str());
 368             return;
 369           }
 370         if (die->tag() == elfcpp::DW_TAG_compile_unit)
 371           this->record_cu_ranges(die);
 372         // If there is a pubnames and/or pubtypes section for this
 373         // compilation unit, use those; otherwise, parse the DWARF
 374         // info to extract the names.
 375         if (!this->read_pubnames_and_pubtypes(die))
 376           {
 377             if (die->tag() == elfcpp::DW_TAG_compile_unit)
 378               ++Gdb_index_info_reader::dwarf_cu_nopubnames_count;
 379             else
 380               ++Gdb_index_info_reader::dwarf_tu_nopubnames_count;
 381             this->visit_children(die, NULL);
 382           }
 383         break;
 384       default:
 385         // The top level DIE should be one of the above.
 386         gold_warning(_("%s: top level DIE is not DW_TAG_compile_unit "
 387                        "or DW_TAG_type_unit"),
 388                      this->object()->name().c_str());
 389         return;
 390     }
 391
 392 }
 393
 394 // Visit the children of PARENT, looking for symbols to add to the index.
 395 // CONTEXT points to the DIE to use for constructing the qualified name --
 396 // NULL if PARENT is the top-level DIE; otherwise it is the same as PARENT.
 397
 398 void
 399 Gdb_index_info_reader::visit_children(Dwarf_die* parent, Dwarf_die* context)
 400 {
 401   off_t next_offset = 0;
 402   for (off_t die_offset = parent->child_offset();
 403        die_offset != 0;
 404        die_offset = next_offset)
 405     {
 406       Dwarf_die die(this, die_offset, parent);
 407       if (die.tag() == 0)
 408         break;
 409       this->visit_die(&die, context);
 410       next_offset = die.sibling_offset();
 411     }
 412 }
 413
 414 // Visit a child DIE, looking for symbols to add to the index.
 415 // CONTEXT is the parent DIE, used for constructing the qualified name;
 416 // it is NULL if the parent DIE is the top-level DIE.
 417
 418 void
 419 Gdb_index_info_reader::visit_die(Dwarf_die* die, Dwarf_die* context)
 420 {
 421   switch (die->tag())
 422     {
 423       case elfcpp::DW_TAG_subprogram:
 424       case elfcpp::DW_TAG_constant:
 425       case elfcpp::DW_TAG_variable:
 426       case elfcpp::DW_TAG_enumerator:
 427       case elfcpp::DW_TAG_base_type:
 428         if (die->is_declaration())
 429           this->add_declaration(die, context);
 430         else
 431           {
 432             // If the DIE is not a declaration, add it to the index.
 433             std::string full_name = this->get_qualified_name(die, context);
 434             if (!full_name.empty())
 435               this->gdb_index_->add_symbol(this->cu_index_, full_name.c_str());
 436           }
 437         break;
 438       case elfcpp::DW_TAG_typedef:
 439       case elfcpp::DW_TAG_union_type:
 440       case elfcpp::DW_TAG_class_type:
 441       case elfcpp::DW_TAG_interface_type:
 442       case elfcpp::DW_TAG_structure_type:
 443       case elfcpp::DW_TAG_enumeration_type:
 444       case elfcpp::DW_TAG_subrange_type:
 445       case elfcpp::DW_TAG_namespace:
 446         {
 447           std::string full_name;
 448
 449           // For classes at the top level, we need to look for a
 450           // member function with a linkage name in order to get
 451           // the properly-canonicalized name.
 452           if (context == NULL
 453               && (die->tag() == elfcpp::DW_TAG_class_type
 454                   || die->tag() == elfcpp::DW_TAG_structure_type
 455                   || die->tag() == elfcpp::DW_TAG_union_type))
 456             full_name.assign(this->guess_full_class_name(die));
 457
 458           // Because we will visit the children, we need to add this DIE
 459           // to the declarations table.
 460           if (full_name.empty())
 461             this->add_declaration(die, context);
 462           else
 463             this->add_declaration_with_full_name(die, full_name.c_str());
 464
 465           // If the DIE is not a declaration, add it to the index.
 466           // Gdb stores a namespace in the index even when it is
 467           // a declaration.
 468           if (die->tag() == elfcpp::DW_TAG_namespace
 469               || !die->is_declaration())
 470             {
 471               if (full_name.empty())
 472                 full_name = this->get_qualified_name(die, context);
 473               if (!full_name.empty())
 474                 this->gdb_index_->add_symbol(this->cu_index_,
 475                                              full_name.c_str());
 476             }
 477
 478           // We're interested in the children only for namespaces and
 479           // enumeration types.  For enumeration types, we do not include
 480           // the enumeration tag as part of the full name.  For other tags,
 481           // visit the children only to collect declarations.
 482           if (die->tag() == elfcpp::DW_TAG_namespace
 483               || die->tag() == elfcpp::DW_TAG_enumeration_type)
 484             this->visit_children(die, die);
 485           else
 486             this->visit_children_for_decls(die);
 487         }
 488         break;
 489       default:
 490         break;
 491     }
 492 }
 493
 494 // Visit the children of PARENT, looking only for declarations that
 495 // may be referenced by later specification DIEs.
 496
 497 void
 498 Gdb_index_info_reader::visit_children_for_decls(Dwarf_die* parent)
 499 {
 500   off_t next_offset = 0;
 501   for (off_t die_offset = parent->child_offset();
 502        die_offset != 0;
 503        die_offset = next_offset)
 504     {
 505       Dwarf_die die(this, die_offset, parent);
 506       if (die.tag() == 0)
 507         break;
 508       this->visit_die_for_decls(&die, parent);
 509       next_offset = die.sibling_offset();
 510     }
 511 }
 512
 513 // Visit a child DIE, looking only for declarations that
 514 // may be referenced by later specification DIEs.
 515
 516 void
 517 Gdb_index_info_reader::visit_die_for_decls(Dwarf_die* die, Dwarf_die* context)
 518 {
 519   switch (die->tag())
 520     {
 521       case elfcpp::DW_TAG_subprogram:
 522       case elfcpp::DW_TAG_constant:
 523       case elfcpp::DW_TAG_variable:
 524       case elfcpp::DW_TAG_enumerator:
 525       case elfcpp::DW_TAG_base_type:
 526         {
 527           if (die->is_declaration())
 528             this->add_declaration(die, context);
 529         }
 530         break;
 531       case elfcpp::DW_TAG_typedef:
 532       case elfcpp::DW_TAG_union_type:
 533       case elfcpp::DW_TAG_class_type:
 534       case elfcpp::DW_TAG_interface_type:
 535       case elfcpp::DW_TAG_structure_type:
 536       case elfcpp::DW_TAG_enumeration_type:
 537       case elfcpp::DW_TAG_subrange_type:
 538       case elfcpp::DW_TAG_namespace:
 539         {
 540           if (die->is_declaration())
 541             this->add_declaration(die, context);
 542           this->visit_children_for_decls(die);
 543         }
 544         break;
 545       default:
 546         break;
 547     }
 548 }
 549
 550 // Extract the class name from the linkage name of a member function.
 551 // This code is adapted from ../gdb/cp-support.c.
 552
 553 #define d_left(dc) (dc)->u.s_binary.left
 554 #define d_right(dc) (dc)->u.s_binary.right
 555
 556 static char*
 557 class_name_from_linkage_name(const char* linkage_name)
 558 {
 559   void* storage;
 560   struct demangle_component* tree =
 561       cplus_demangle_v3_components(linkage_name, DMGL_NO_OPTS, &storage);
 562   if (tree == NULL)
 563     return NULL;
 564
 565   int done = 0;
 566
 567   // First strip off any qualifiers, if we have a function or
 568   // method.
 569   while (!done)
 570     switch (tree->type)
 571       {
 572         case DEMANGLE_COMPONENT_CONST:
 573         case DEMANGLE_COMPONENT_RESTRICT:
 574         case DEMANGLE_COMPONENT_VOLATILE:
 575         case DEMANGLE_COMPONENT_CONST_THIS:
 576         case DEMANGLE_COMPONENT_RESTRICT_THIS:
 577         case DEMANGLE_COMPONENT_VOLATILE_THIS:
 578         case DEMANGLE_COMPONENT_VENDOR_TYPE_QUAL:
 579           tree = d_left(tree);
 580           break;
 581         default:
 582           done = 1;
 583           break;
 584       }
 585
 586   // If what we have now is a function, discard the argument list.
 587   if (tree->type == DEMANGLE_COMPONENT_TYPED_NAME)
 588     tree = d_left(tree);
 589
 590   // If what we have now is a template, strip off the template
 591   // arguments.  The left subtree may be a qualified name.
 592   if (tree->type == DEMANGLE_COMPONENT_TEMPLATE)
 593     tree = d_left(tree);
 594
 595   // What we have now should be a name, possibly qualified.
 596   // Additional qualifiers could live in the left subtree or the right
 597   // subtree.  Find the last piece.
 598   done = 0;
 599   struct demangle_component* prev_comp = NULL;
 600   struct demangle_component* cur_comp = tree;
 601   while (!done)
 602     switch (cur_comp->type)
 603       {
 604         case DEMANGLE_COMPONENT_QUAL_NAME:
 605         case DEMANGLE_COMPONENT_LOCAL_NAME:
 606           prev_comp = cur_comp;
 607           cur_comp = d_right(cur_comp);
 608           break;
 609         case DEMANGLE_COMPONENT_TEMPLATE:
 610         case DEMANGLE_COMPONENT_NAME:
 611         case DEMANGLE_COMPONENT_CTOR:
 612         case DEMANGLE_COMPONENT_DTOR:
 613         case DEMANGLE_COMPONENT_OPERATOR:
 614         case DEMANGLE_COMPONENT_EXTENDED_OPERATOR:
 615           done = 1;
 616           break;
 617         default:
 618           done = 1;
 619           cur_comp = NULL;
 620           break;
 621       }
 622
 623   char* ret = NULL;
 624   if (cur_comp != NULL && prev_comp != NULL)
 625     {
 626       // We want to discard the rightmost child of PREV_COMP.
 627       *prev_comp = *d_left(prev_comp);
 628       size_t allocated_size;
 629       ret = cplus_demangle_print(DMGL_NO_OPTS, tree, 30, &allocated_size);
 630     }
 631
 632   free(storage);
 633   return ret;
 634 }
 635
 636 // Guess a fully-qualified name for a class type, based on member function
 637 // linkage names.  This is needed for class/struct/union types at the
 638 // top level, because GCC does not always properly embed them within
 639 // the namespace.  As in gdb, we look for a member function with a linkage
 640 // name and extract the qualified name from the demangled name.
 641
 642 std::string
 643 Gdb_index_info_reader::guess_full_class_name(Dwarf_die* die)
 644 {
 645   std::string full_name;
 646   off_t next_offset = 0;
 647
 648   // This routine scans ahead in the DIE structure, possibly advancing
 649   // the relocation tracker beyond the current DIE.  We need to checkpoint
 650   // the tracker and reset it when we're done.
 651   uint64_t checkpoint = this->get_reloc_checkpoint();
 652
 653   for (off_t child_offset = die->child_offset();
 654        child_offset != 0;
 655        child_offset = next_offset)
 656     {
 657       Dwarf_die child(this, child_offset, die);
 658       if (child.tag() == 0)
 659         break;
 660       if (child.tag() == elfcpp::DW_TAG_subprogram)
 661         {
 662           const char* linkage_name = child.linkage_name();
 663           if (linkage_name != NULL)
 664             {
 665               char* guess = class_name_from_linkage_name(linkage_name);
 666               if (guess != NULL)
 667                 {
 668                   full_name.assign(guess);
 669                   free(guess);
 670                   break;
 671                 }
 672             }
 673         }
 674       next_offset = child.sibling_offset();
 675     }
 676
 677   this->reset_relocs(checkpoint);
 678   return full_name;
 679 }
 680
 681 // Add a declaration DIE to the table of declarations.
 682
 683 void
 684 Gdb_index_info_reader::add_declaration(Dwarf_die* die, Dwarf_die* context)
 685 {
 686   const char* name = die->name();
 687
 688   off_t parent_offset = context != NULL ? context->offset() : 0;
 689
 690   // If this DIE has a DW_AT_specification or DW_AT_abstract_origin
 691   // attribute, use the parent and name from the earlier declaration.
 692   off_t spec = die->specification();
 693   if (spec == 0)
 694     spec = die->abstract_origin();
 695   if (spec > 0)
 696     {
 697       Declaration_map::iterator it = this->declarations_.find(spec);
 698       if (it != this->declarations_.end())
 699         {
 700           parent_offset = it->second.parent_offset_;
 701           name = it->second.name_;
 702         }
 703     }
 704
 705   if (name == NULL)
 706     {
 707       if (die->tag() == elfcpp::DW_TAG_namespace)
 708         name = "(anonymous namespace)";
 709       else if (die->tag() == elfcpp::DW_TAG_union_type)
 710         name = "(anonymous union)";
 711       else
 712         name = "(unknown)";
 713     }
 714
 715   Declaration_pair decl(parent_offset, name);
 716   this->declarations_.insert(std::make_pair(die->offset(), decl));
 717 }
 718
 719 // Add a declaration whose fully-qualified name is already known.
 720 // In the case where we had to get the canonical name by demangling
 721 // a linkage name, this ensures we use that name instead of the one
 722 // provided in DW_AT_name.
 723
 724 void
 725 Gdb_index_info_reader::add_declaration_with_full_name(
 726     Dwarf_die* die,
 727     const char* full_name)
 728 {
 729   // We need to copy the name.
 730   int len = strlen(full_name);
 731   char* copy = new char[len + 1];
 732   memcpy(copy, full_name, len + 1);
 733
 734   // Flag that we now manage the memory this points to.
 735   Declaration_pair decl(-1, copy);
 736   this->declarations_.insert(std::make_pair(die->offset(), decl));
 737 }
 738
 739 // Return the context for a DIE whose parent is at DIE_OFFSET.
 740
 741 std::string
 742 Gdb_index_info_reader::get_context(off_t die_offset)
 743 {
 744   std::string context;
 745   Declaration_map::iterator it = this->declarations_.find(die_offset);
 746   if (it != this->declarations_.end())
 747     {
 748       off_t parent_offset = it->second.parent_offset_;
 749       if (parent_offset > 0)
 750         {
 751           context = get_context(parent_offset);
 752           context.append("::");
 753         }
 754       if (it->second.name_ != NULL)
 755         context.append(it->second.name_);
 756     }
 757   return context;
 758 }
 759
 760 // Construct the fully-qualified name for DIE.
 761
 762 std::string
 763 Gdb_index_info_reader::get_qualified_name(Dwarf_die* die, Dwarf_die* context)
 764 {
 765   std::string full_name;
 766   const char* name = die->name();
 767
 768   off_t parent_offset = context != NULL ? context->offset() : 0;
 769
 770   // If this DIE has a DW_AT_specification or DW_AT_abstract_origin
 771   // attribute, use the parent and name from the earlier declaration.
 772   off_t spec = die->specification();
 773   if (spec == 0)
 774     spec = die->abstract_origin();
 775   if (spec > 0)
 776     {
 777       Declaration_map::iterator it = this->declarations_.find(spec);
 778       if (it != this->declarations_.end())
 779         {
 780           parent_offset = it->second.parent_offset_;
 781           name = it->second.name_;
 782         }
 783     }
 784
 785   if (name == NULL && die->tag() == elfcpp::DW_TAG_namespace)
 786     name = "(anonymous namespace)";
 787   else if (name == NULL)
 788     return full_name;
 789
 790   // If this is an enumerator constant, skip the immediate parent,
 791   // which is the enumeration tag.
 792   if (die->tag() == elfcpp::DW_TAG_enumerator)
 793     {
 794       Declaration_map::iterator it = this->declarations_.find(parent_offset);
 795       if (it != this->declarations_.end())
 796         parent_offset = it->second.parent_offset_;
 797     }
 798
 799   if (parent_offset > 0)
 800     {
 801       full_name.assign(this->get_context(parent_offset));
 802       full_name.append("::");
 803     }
 804   full_name.append(name);
 805
 806   return full_name;
 807 }
 808
 809 // Record the address ranges for a compilation unit.
 810
 811 void
 812 Gdb_index_info_reader::record_cu_ranges(Dwarf_die* die)
 813 {
 814   unsigned int shndx;
 815   unsigned int shndx2;
 816
 817   off_t ranges_offset = die->ref_attribute(elfcpp::DW_AT_ranges, &shndx);
 818   if (ranges_offset != -1)
 819     {
 820       Dwarf_range_list* ranges = this->read_range_list(shndx, ranges_offset);
 821       if (ranges != NULL)
 822         this->gdb_index_->add_address_range_list(this->object(),
 823                                                  this->cu_index_, ranges);
 824       return;
 825     }
 826
 827   off_t low_pc = die->address_attribute(elfcpp::DW_AT_low_pc, &shndx);
 828   off_t high_pc = die->address_attribute(elfcpp::DW_AT_high_pc, &shndx2);
 829   if (high_pc == -1)
 830     {
 831       high_pc = die->uint_attribute(elfcpp::DW_AT_high_pc);
 832       high_pc += low_pc;
 833       shndx2 = shndx;
 834     }
 835   if ((low_pc != 0 || high_pc != 0) && low_pc != -1)
 836     {
 837       if (shndx != shndx2)
 838         {
 839           gold_warning(_("%s: DWARF info may be corrupt; low_pc and high_pc "
 840                          "are in different sections"),
 841                        this->object()->name().c_str());
 842           return;
 843         }
 844       if (shndx == 0 || this->object()->is_section_included(shndx))
 845         {
 846           Dwarf_range_list* ranges = new Dwarf_range_list();
 847           ranges->add(shndx, low_pc, high_pc);
 848           this->gdb_index_->add_address_range_list(this->object(),
 849                                                    this->cu_index_, ranges);
 850         }
 851     }
 852 }
 853
 854 // Read the .debug_pubnames and .debug_pubtypes tables for the CU or TU.
 855 // Returns TRUE if either a pubnames or pubtypes section was found.
 856
 857 bool
 858 Gdb_index_info_reader::read_pubnames_and_pubtypes(Dwarf_die* die)
 859 {
 860   bool ret = false;
 861
 862   // If we find a DW_AT_GNU_pubnames attribute, read the pubnames table.
 863   unsigned int pubnames_shndx;
 864   off_t pubnames_offset = die->ref_attribute(elfcpp::DW_AT_GNU_pubnames,
 865                                              &pubnames_shndx);
 866   if (pubnames_offset != -1)
 867     {
 868       if (this->gdb_index_->pubnames_read(this->object(), pubnames_shndx,
 869                                           pubnames_offset))
 870         ret = true;
 871       else
 872         {
 873           Dwarf_pubnames_table pubnames(this, false);
 874           if (!pubnames.read_section(this->object(), pubnames_shndx))
 875             return false;
 876           if (!pubnames.read_header(pubnames_offset))
 877             return false;
 878           while (true)
 879             {
 880               const char* name = pubnames.next_name();
 881               if (name == NULL)
 882                 break;
 883               this->gdb_index_->add_symbol(this->cu_index_, name);
 884             }
 885           ret = true;
 886         }
 887     }
 888
 889   // If we find a DW_AT_GNU_pubtypes attribute, read the pubtypes table.
 890   unsigned int pubtypes_shndx;
 891   off_t pubtypes_offset = die->ref_attribute(elfcpp::DW_AT_GNU_pubtypes,
 892                                              &pubtypes_shndx);
 893   if (pubtypes_offset != -1)
 894     {
 895       if (this->gdb_index_->pubtypes_read(this->object(),
 896                                           pubtypes_shndx, pubtypes_offset))
 897         ret = true;
 898       else
 899         {
 900           Dwarf_pubnames_table pubtypes(this, true);
 901           if (!pubtypes.read_section(this->object(), pubtypes_shndx))
 902             return false;
 903           if (!pubtypes.read_header(pubtypes_offset))
 904             return false;
 905           while (true)
 906             {
 907               const char* name = pubtypes.next_name();
 908               if (name == NULL)
 909                 break;
 910               this->gdb_index_->add_symbol(this->cu_index_, name);
 911             }
 912           ret = true;
 913         }
 914     }
 915
 916   return ret;
 917 }
 918
 919 // Clear the declarations map.
 920 void
 921 Gdb_index_info_reader::clear_declarations()
 922 {
 923   // Free strings in memory we manage.
 924   for (Declaration_map::iterator it = this->declarations_.begin();
 925        it != this->declarations_.end();
 926        ++it)
 927     {
 928       if (it->second.parent_offset_ == -1)
 929         delete[] it->second.name_;
 930     }
 931
 932   this->declarations_.clear();
 933 }
 934
 935 // Print usage statistics.
 936 void
 937 Gdb_index_info_reader::print_stats()
 938 {
 939   fprintf(stderr, _("%s: DWARF CUs: %u\n"),
 940           program_name, Gdb_index_info_reader::dwarf_cu_count);
 941   fprintf(stderr, _("%s: DWARF CUs without pubnames/pubtypes: %u\n"),
 942           program_name, Gdb_index_info_reader::dwarf_cu_nopubnames_count);
 943   fprintf(stderr, _("%s: DWARF TUs: %u\n"),
 944           program_name, Gdb_index_info_reader::dwarf_tu_count);
 945   fprintf(stderr, _("%s: DWARF TUs without pubnames/pubtypes: %u\n"),
 946           program_name, Gdb_index_info_reader::dwarf_tu_nopubnames_count);
 947 }
 948
 949 // Class Gdb_index.
 950
 951 // Construct the .gdb_index section.
 952
 953 Gdb_index::Gdb_index(Output_section* gdb_index_section)
 954   : Output_section_data(4),
 955     gdb_index_section_(gdb_index_section),
 956     comp_units_(),
 957     type_units_(),
 958     ranges_(),
 959     cu_vector_list_(),
 960     cu_vector_offsets_(NULL),
 961     stringpool_(),
 962     tu_offset_(0),
 963     addr_offset_(0),
 964     symtab_offset_(0),
 965     cu_pool_offset_(0),
 966     stringpool_offset_(0),
 967     pubnames_object_(NULL),
 968     pubnames_shndx_(0),
 969     pubnames_offset_(0),
 970     pubtypes_object_(NULL),
 971     pubtypes_shndx_(0),
 972     pubtypes_offset_(0)
 973 {
 974   this->gdb_symtab_ = new Gdb_hashtab<Gdb_symbol>();
 975 }
 976
 977 Gdb_index::~Gdb_index()
 978 {
 979   // Free the memory used by the symbol table.
 980   delete this->gdb_symtab_;
 981   // Free the memory used by the CU vectors.
 982   for (unsigned int i = 0; i < this->cu_vector_list_.size(); ++i)
 983     delete this->cu_vector_list_[i];
 984 }
 985
 986 // Scan a .debug_info or .debug_types input section.
 987
 988 void
 989 Gdb_index::scan_debug_info(bool is_type_unit,
 990                            Relobj* object,
 991                            const unsigned char* symbols,
 992                            off_t symbols_size,
 993                            unsigned int shndx,
 994                            unsigned int reloc_shndx,
 995                            unsigned int reloc_type)
 996 {
 997   Gdb_index_info_reader dwinfo(is_type_unit, object,
 998                                symbols, symbols_size,
 999                                shndx, reloc_shndx,
1000                                reloc_type, this);
1001   dwinfo.parse();
1002 }
1003
1004 // Add a symbol.
1005
1006 void
1007 Gdb_index::add_symbol(int cu_index, const char* sym_name)
1008 {
1009   unsigned int hash = mapped_index_string_hash(
1010       reinterpret_cast<const unsigned char*>(sym_name));
1011   Gdb_symbol* sym = new Gdb_symbol();
1012   this->stringpool_.add(sym_name, true, &sym->name_key);
1013   sym->hashval = hash;
1014   sym->cu_vector_index = 0;
1015
1016   Gdb_symbol* found = this->gdb_symtab_->add(sym);
1017   if (found == sym)
1018     {
1019       // New symbol -- allocate a new CU index vector.
1020       found->cu_vector_index = this->cu_vector_list_.size();
1021       this->cu_vector_list_.push_back(new Cu_vector());
1022     }
1023   else
1024     {
1025       // Found an existing symbol -- append to the existing
1026       // CU index vector.
1027       delete sym;
1028     }
1029
1030   // Add the CU index to the vector list for this symbol,
1031   // if it's not already on the list.  We only need to
1032   // check the last added entry.
1033   Cu_vector* cu_vec = this->cu_vector_list_[found->cu_vector_index];
1034   if (cu_vec->size() == 0 || cu_vec->back() != cu_index)
1035     cu_vec->push_back(cu_index);
1036 }
1037
1038 // Return TRUE if we have already processed the pubnames set at
1039 // OFFSET in section SHNDX
1040
1041 bool
1042 Gdb_index::pubnames_read(const Relobj* object, unsigned int shndx, off_t offset)
1043 {
1044   bool ret = (this->pubnames_object_ == object
1045               && this->pubnames_shndx_ == shndx
1046               && this->pubnames_offset_ == offset);
1047   this->pubnames_object_ = object;
1048   this->pubnames_shndx_ = shndx;
1049   this->pubnames_offset_ = offset;
1050   return ret;
1051 }
1052
1053 // Return TRUE if we have already processed the pubtypes set at
1054 // OFFSET in section SHNDX
1055
1056 bool
1057 Gdb_index::pubtypes_read(const Relobj* object, unsigned int shndx, off_t offset)
1058 {
1059   bool ret = (this->pubtypes_object_ == object
1060               && this->pubtypes_shndx_ == shndx
1061               && this->pubtypes_offset_ == offset);
1062   this->pubtypes_object_ = object;
1063   this->pubtypes_shndx_ = shndx;
1064   this->pubtypes_offset_ = offset;
1065   return ret;
1066 }
1067
1068 // Set the size of the .gdb_index section.
1069
1070 void
1071 Gdb_index::set_final_data_size()
1072 {
1073   // Finalize the string pool.
1074   this->stringpool_.set_string_offsets();
1075
1076   // Compute the total size of the CU vectors.
1077   // For each CU vector, include one entry for the count at the
1078   // beginning of the vector.
1079   unsigned int cu_vector_count = this->cu_vector_list_.size();
1080   unsigned int cu_vector_size = 0;
1081   this->cu_vector_offsets_ = new off_t[cu_vector_count];
1082   for (unsigned int i = 0; i < cu_vector_count; ++i)
1083     {
1084       Cu_vector* cu_vec = this->cu_vector_list_[i];
1085       cu_vector_offsets_[i] = cu_vector_size;
1086       cu_vector_size += gdb_index_offset_size * (cu_vec->size() + 1);
1087     }
1088
1089   // Assign relative offsets to each portion of the index,
1090   // and find the total size of the section.
1091   section_size_type data_size = gdb_index_hdr_size;
1092   data_size += this->comp_units_.size() * gdb_index_cu_size;
1093   this->tu_offset_ = data_size;
1094   data_size += this->type_units_.size() * gdb_index_tu_size;
1095   this->addr_offset_ = data_size;
1096   for (unsigned int i = 0; i < this->ranges_.size(); ++i)
1097     data_size += this->ranges_[i].ranges->size() * gdb_index_addr_size;
1098   this->symtab_offset_ = data_size;
1099   data_size += this->gdb_symtab_->capacity() * gdb_index_sym_size;
1100   this->cu_pool_offset_ = data_size;
1101   data_size += cu_vector_size;
1102   this->stringpool_offset_ = data_size;
1103   data_size += this->stringpool_.get_strtab_size();
1104
1105   this->set_data_size(data_size);
1106 }
1107
1108 // Write the data to the file.
1109
1110 void
1111 Gdb_index::do_write(Output_file* of)
1112 {
1113   const off_t off = this->offset();
1114   const off_t oview_size = this->data_size();
1115   unsigned char* const oview = of->get_output_view(off, oview_size);
1116   unsigned char* pov = oview;
1117
1118   // Write the file header.
1119   // (1) Version number.
1120   elfcpp::Swap<32, false>::writeval(pov, gdb_index_version);
1121   pov += 4;
1122   // (2) Offset of the CU list.
1123   elfcpp::Swap<32, false>::writeval(pov, gdb_index_hdr_size);
1124   pov += 4;
1125   // (3) Offset of the types CU list.
1126   elfcpp::Swap<32, false>::writeval(pov, this->tu_offset_);
1127   pov += 4;
1128   // (4) Offset of the address area.
1129   elfcpp::Swap<32, false>::writeval(pov, this->addr_offset_);
1130   pov += 4;
1131   // (5) Offset of the symbol table.
1132   elfcpp::Swap<32, false>::writeval(pov, this->symtab_offset_);
1133   pov += 4;
1134   // (6) Offset of the constant pool.
1135   elfcpp::Swap<32, false>::writeval(pov, this->cu_pool_offset_);
1136   pov += 4;
1137
1138   gold_assert(pov - oview == gdb_index_hdr_size);
1139
1140   // Write the CU list.
1141   unsigned int comp_units_count = this->comp_units_.size();
1142   for (unsigned int i = 0; i < comp_units_count; ++i)
1143     {
1144       const Comp_unit& cu = this->comp_units_[i];
1145       elfcpp::Swap<64, false>::writeval(pov, cu.cu_offset);
1146       elfcpp::Swap<64, false>::writeval(pov + 8, cu.cu_length);
1147       pov += 16;
1148     }
1149
1150   gold_assert(pov - oview == this->tu_offset_);
1151
1152   // Write the types CU list.
1153   for (unsigned int i = 0; i < this->type_units_.size(); ++i)
1154     {
1155       const Type_unit& tu = this->type_units_[i];
1156       elfcpp::Swap<64, false>::writeval(pov, tu.tu_offset);
1157       elfcpp::Swap<64, false>::writeval(pov + 8, tu.type_offset);
1158       elfcpp::Swap<64, false>::writeval(pov + 16, tu.type_signature);
1159       pov += 24;
1160     }
1161
1162   gold_assert(pov - oview == this->addr_offset_);
1163
1164   // Write the address area.
1165   for (unsigned int i = 0; i < this->ranges_.size(); ++i)
1166     {
1167       int cu_index = this->ranges_[i].cu_index;
1168       // Translate negative indexes, which refer to a TU, to a
1169       // logical index into a concatenated CU/TU list.
1170       if (cu_index < 0)
1171         cu_index = comp_units_count + (-1 - cu_index);
1172       Relobj* object = this->ranges_[i].object;
1173       const Dwarf_range_list& ranges = *this->ranges_[i].ranges;
1174       for (unsigned int j = 0; j < ranges.size(); ++j)
1175         {
1176           const Dwarf_range_list::Range& range = ranges[j];
1177           uint64_t base = 0;
1178           if (range.shndx > 0)
1179             {
1180               const Output_section* os = object->output_section(range.shndx);
1181               base = (os->address()
1182                       + object->output_section_offset(range.shndx));
1183             }
1184           elfcpp::Swap_aligned32<64, false>::writeval(pov, base + range.start);
1185           elfcpp::Swap_aligned32<64, false>::writeval(pov + 8,
1186                                                       base + range.end);
1187           elfcpp::Swap<32, false>::writeval(pov + 16, cu_index);
1188           pov += 20;
1189         }
1190     }
1191
1192   gold_assert(pov - oview == this->symtab_offset_);
1193
1194   // Write the symbol table.
1195   for (unsigned int i = 0; i < this->gdb_symtab_->capacity(); ++i)
1196     {
1197       const Gdb_symbol* sym = (*this->gdb_symtab_)[i];
1198       section_offset_type name_offset = 0;
1199       unsigned int cu_vector_offset = 0;
1200       if (sym != NULL)
1201         {
1202           name_offset = (this->stringpool_.get_offset_from_key(sym->name_key)
1203                          + this->stringpool_offset_ - this->cu_pool_offset_);
1204           cu_vector_offset = this->cu_vector_offsets_[sym->cu_vector_index];
1205         }
1206       elfcpp::Swap<32, false>::writeval(pov, name_offset);
1207       elfcpp::Swap<32, false>::writeval(pov + 4, cu_vector_offset);
1208       pov += 8;
1209     }
1210
1211   gold_assert(pov - oview == this->cu_pool_offset_);
1212
1213   // Write the CU vectors into the constant pool.
1214   for (unsigned int i = 0; i < this->cu_vector_list_.size(); ++i)
1215     {
1216       Cu_vector* cu_vec = this->cu_vector_list_[i];
1217       elfcpp::Swap<32, false>::writeval(pov, cu_vec->size());
1218       pov += 4;
1219       for (unsigned int j = 0; j < cu_vec->size(); ++j)
1220         {
1221           int cu_index = (*cu_vec)[j];
1222           if (cu_index < 0)
1223             cu_index = comp_units_count + (-1 - cu_index);
1224           elfcpp::Swap<32, false>::writeval(pov, cu_index);
1225           pov += 4;
1226         }
1227     }
1228
1229   gold_assert(pov - oview == this->stringpool_offset_);
1230
1231   // Write the strings into the constant pool.
1232   this->stringpool_.write_to_buffer(pov, oview_size - this->stringpool_offset_);
1233
1234   of->write_output_view(off, oview_size, oview);
1235 }
1236
1237 // Print usage statistics.
1238 void
1239 Gdb_index::print_stats()
1240 {
1241   if (parameters->options().gdb_index())
1242     Gdb_index_info_reader::print_stats();
1243 }
1244
1245 } // End namespace gold.