gold/dwarf_reader.cc

   1 // dwarf_reader.cc -- parse dwarf2/3 debug information
   2
   3 // Copyright 2007, 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
   4 // Written by Ian Lance Taylor <iant@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 <algorithm>
  26 #include <vector>
  27
  28 #include "elfcpp_swap.h"
  29 #include "dwarf.h"
  30 #include "object.h"
  31 #include "reloc.h"
  32 #include "dwarf_reader.h"
  33 #include "int_encoding.h"
  34 #include "compressed_output.h"
  35
  36 namespace gold {
  37
  38 // Class Sized_elf_reloc_mapper
  39
  40 // Initialize the relocation tracker for section RELOC_SHNDX.
  41
  42 template<int size, bool big_endian>
  43 bool
  44 Sized_elf_reloc_mapper<size, big_endian>::do_initialize(
  45     unsigned int reloc_shndx, unsigned int reloc_type)
  46 {
  47   this->reloc_type_ = reloc_type;
  48   return this->track_relocs_.initialize(this->object_, reloc_shndx,
  49                                         reloc_type);
  50 }
  51
  52 // Looks in the symtab to see what section a symbol is in.
  53
  54 template<int size, bool big_endian>
  55 unsigned int
  56 Sized_elf_reloc_mapper<size, big_endian>::symbol_section(
  57     unsigned int symndx, Address* value, bool* is_ordinary)
  58 {
  59   const int symsize = elfcpp::Elf_sizes<size>::sym_size;
  60   gold_assert(static_cast<off_t>((symndx + 1) * symsize) <= this->symtab_size_);
  61   elfcpp::Sym<size, big_endian> elfsym(this->symtab_ + symndx * symsize);
  62   *value = elfsym.get_st_value();
  63   return this->object_->adjust_sym_shndx(symndx, elfsym.get_st_shndx(),
  64                                          is_ordinary);
  65 }
  66
  67 // Return the section index and offset within the section of
  68 // the target of the relocation for RELOC_OFFSET.
  69
  70 template<int size, bool big_endian>
  71 unsigned int
  72 Sized_elf_reloc_mapper<size, big_endian>::do_get_reloc_target(
  73     off_t reloc_offset, off_t* target_offset)
  74 {
  75   this->track_relocs_.advance(reloc_offset);
  76   if (reloc_offset != this->track_relocs_.next_offset())
  77     return 0;
  78   unsigned int symndx = this->track_relocs_.next_symndx();
  79   typename elfcpp::Elf_types<size>::Elf_Addr value;
  80   bool is_ordinary;
  81   unsigned int target_shndx = this->symbol_section(symndx, &value,
  82                                                    &is_ordinary);
  83   if (!is_ordinary)
  84     return 0;
  85   if (this->reloc_type_ == elfcpp::SHT_RELA)
  86     value += this->track_relocs_.next_addend();
  87   *target_offset = value;
  88   return target_shndx;
  89 }
  90
  91 static inline Elf_reloc_mapper*
  92 make_elf_reloc_mapper(Relobj* object, const unsigned char* symtab,
  93                       off_t symtab_size)
  94 {
  95   if (object->elfsize() == 32)
  96     {
  97       if (object->is_big_endian())
  98         {
  99 #ifdef HAVE_TARGET_32_BIG
 100           return new Sized_elf_reloc_mapper<32, true>(object, symtab,
 101                                                       symtab_size);
 102 #else
 103           gold_unreachable();
 104 #endif
 105         }
 106       else
 107         {
 108 #ifdef HAVE_TARGET_32_LITTLE
 109           return new Sized_elf_reloc_mapper<32, false>(object, symtab,
 110                                                        symtab_size);
 111 #else
 112           gold_unreachable();
 113 #endif
 114         }
 115     }
 116   else if (object->elfsize() == 64)
 117     {
 118       if (object->is_big_endian())
 119         {
 120 #ifdef HAVE_TARGET_64_BIG
 121           return new Sized_elf_reloc_mapper<64, true>(object, symtab,
 122                                                       symtab_size);
 123 #else
 124           gold_unreachable();
 125 #endif
 126         }
 127       else
 128         {
 129 #ifdef HAVE_TARGET_64_LITTLE
 130           return new Sized_elf_reloc_mapper<64, false>(object, symtab,
 131                                                        symtab_size);
 132 #else
 133           gold_unreachable();
 134 #endif
 135         }
 136     }
 137   else
 138     gold_unreachable();
 139 }
 140
 141 // class Dwarf_abbrev_table
 142
 143 void
 144 Dwarf_abbrev_table::clear_abbrev_codes()
 145 {
 146   for (unsigned int code = 0; code < this->low_abbrev_code_max_; ++code)
 147     {
 148       if (this->low_abbrev_codes_[code] != NULL)
 149         {
 150           delete this->low_abbrev_codes_[code];
 151           this->low_abbrev_codes_[code] = NULL;
 152         }
 153     }
 154   for (Abbrev_code_table::iterator it = this->high_abbrev_codes_.begin();
 155        it != this->high_abbrev_codes_.end();
 156        ++it)
 157     {
 158       if (it->second != NULL)
 159         delete it->second;
 160     }
 161   this->high_abbrev_codes_.clear();
 162 }
 163
 164 // Read the abbrev table from an object file.
 165
 166 bool
 167 Dwarf_abbrev_table::do_read_abbrevs(
 168     Relobj* object,
 169     unsigned int abbrev_shndx,
 170     off_t abbrev_offset)
 171 {
 172   this->clear_abbrev_codes();
 173
 174   // If we don't have relocations, abbrev_shndx will be 0, and
 175   // we'll have to hunt for the .debug_abbrev section.
 176   if (abbrev_shndx == 0 && this->abbrev_shndx_ > 0)
 177     abbrev_shndx = this->abbrev_shndx_;
 178   else if (abbrev_shndx == 0)
 179     {
 180       for (unsigned int i = 1; i < object->shnum(); ++i)
 181         {
 182           std::string name = object->section_name(i);
 183           if (name == ".debug_abbrev")
 184             {
 185               abbrev_shndx = i;
 186               // Correct the offset.  For incremental update links, we have a
 187               // relocated offset that is relative to the output section, but
 188               // here we need an offset relative to the input section.
 189               abbrev_offset -= object->output_section_offset(i);
 190               break;
 191             }
 192         }
 193       if (abbrev_shndx == 0)
 194         return false;
 195     }
 196
 197   // Get the section contents and decompress if necessary.
 198   if (abbrev_shndx != this->abbrev_shndx_)
 199     {
 200       if (this->owns_buffer_ && this->buffer_ != NULL)
 201         {
 202           delete[] this->buffer_;
 203           this->owns_buffer_ = false;
 204         }
 205
 206       section_size_type buffer_size;
 207       this->buffer_ =
 208           object->decompressed_section_contents(abbrev_shndx,
 209                                                 &buffer_size,
 210                                                 &this->owns_buffer_);
 211       this->buffer_end_ = this->buffer_ + buffer_size;
 212       this->abbrev_shndx_ = abbrev_shndx;
 213     }
 214
 215   this->buffer_pos_ = this->buffer_ + abbrev_offset;
 216   return true;
 217 }
 218
 219 // Lookup the abbrev code entry for CODE.  This function is called
 220 // only when the abbrev code is not in the direct lookup table.
 221 // It may be in the hash table, it may not have been read yet,
 222 // or it may not exist in the abbrev table.
 223
 224 const Dwarf_abbrev_table::Abbrev_code*
 225 Dwarf_abbrev_table::do_get_abbrev(unsigned int code)
 226 {
 227   // See if the abbrev code is already in the hash table.
 228   Abbrev_code_table::const_iterator it = this->high_abbrev_codes_.find(code);
 229   if (it != this->high_abbrev_codes_.end())
 230     return it->second;
 231
 232   // Read and store abbrev code definitions until we find the
 233   // one we're looking for.
 234   for (;;)
 235     {
 236       // Read the abbrev code.  A zero here indicates the end of the
 237       // abbrev table.
 238       size_t len;
 239       if (this->buffer_pos_ >= this->buffer_end_)
 240         return NULL;
 241       uint64_t nextcode = read_unsigned_LEB_128(this->buffer_pos_, &len);
 242       if (nextcode == 0)
 243         {
 244           this->buffer_pos_ = this->buffer_end_;
 245           return NULL;
 246         }
 247       this->buffer_pos_ += len;
 248
 249       // Read the tag.
 250       if (this->buffer_pos_ >= this->buffer_end_)
 251         return NULL;
 252       uint64_t tag = read_unsigned_LEB_128(this->buffer_pos_, &len);
 253       this->buffer_pos_ += len;
 254
 255       // Read the has_children flag.
 256       if (this->buffer_pos_ >= this->buffer_end_)
 257         return NULL;
 258       bool has_children = *this->buffer_pos_ == elfcpp::DW_CHILDREN_yes;
 259       this->buffer_pos_ += 1;
 260
 261       // Read the list of (attribute, form) pairs.
 262       Abbrev_code* entry = new Abbrev_code(tag, has_children);
 263       for (;;)
 264         {
 265           // Read the attribute.
 266           if (this->buffer_pos_ >= this->buffer_end_)
 267             return NULL;
 268           uint64_t attr = read_unsigned_LEB_128(this->buffer_pos_, &len);
 269           this->buffer_pos_ += len;
 270
 271           // Read the form.
 272           if (this->buffer_pos_ >= this->buffer_end_)
 273             return NULL;
 274           uint64_t form = read_unsigned_LEB_128(this->buffer_pos_, &len);
 275           this->buffer_pos_ += len;
 276
 277           // A (0,0) pair terminates the list.
 278           if (attr == 0 && form == 0)
 279             break;
 280
 281           if (attr == elfcpp::DW_AT_sibling)
 282             entry->has_sibling_attribute = true;
 283
 284           entry->add_attribute(attr, form);
 285         }
 286
 287       this->store_abbrev(nextcode, entry);
 288       if (nextcode == code)
 289         return entry;
 290     }
 291
 292   return NULL;
 293 }
 294
 295 // class Dwarf_ranges_table
 296
 297 // Read the ranges table from an object file.
 298
 299 bool
 300 Dwarf_ranges_table::read_ranges_table(
 301     Relobj* object,
 302     const unsigned char* symtab,
 303     off_t symtab_size,
 304     unsigned int ranges_shndx)
 305 {
 306   // If we've already read this abbrev table, return immediately.
 307   if (this->ranges_shndx_ > 0
 308       && this->ranges_shndx_ == ranges_shndx)
 309     return true;
 310
 311   // If we don't have relocations, ranges_shndx will be 0, and
 312   // we'll have to hunt for the .debug_ranges section.
 313   if (ranges_shndx == 0 && this->ranges_shndx_ > 0)
 314     ranges_shndx = this->ranges_shndx_;
 315   else if (ranges_shndx == 0)
 316     {
 317       for (unsigned int i = 1; i < object->shnum(); ++i)
 318         {
 319           std::string name = object->section_name(i);
 320           if (name == ".debug_ranges")
 321             {
 322               ranges_shndx = i;
 323               this->output_section_offset_ = object->output_section_offset(i);
 324               break;
 325             }
 326         }
 327       if (ranges_shndx == 0)
 328         return false;
 329     }
 330
 331   // Get the section contents and decompress if necessary.
 332   if (ranges_shndx != this->ranges_shndx_)
 333     {
 334       if (this->owns_ranges_buffer_ && this->ranges_buffer_ != NULL)
 335         {
 336           delete[] this->ranges_buffer_;
 337           this->owns_ranges_buffer_ = false;
 338         }
 339
 340       section_size_type buffer_size;
 341       this->ranges_buffer_ =
 342           object->decompressed_section_contents(ranges_shndx,
 343                                                 &buffer_size,
 344                                                 &this->owns_ranges_buffer_);
 345       this->ranges_buffer_end_ = this->ranges_buffer_ + buffer_size;
 346       this->ranges_shndx_ = ranges_shndx;
 347     }
 348
 349   if (this->ranges_reloc_mapper_ != NULL)
 350     {
 351       delete this->ranges_reloc_mapper_;
 352       this->ranges_reloc_mapper_ = NULL;
 353     }
 354
 355   // For incremental objects, we have no relocations.
 356   if (object->is_incremental())
 357     return true;
 358
 359   // Find the relocation section for ".debug_ranges".
 360   unsigned int reloc_shndx = 0;
 361   unsigned int reloc_type = 0;
 362   for (unsigned int i = 0; i < object->shnum(); ++i)
 363     {
 364       reloc_type = object->section_type(i);
 365       if ((reloc_type == elfcpp::SHT_REL
 366            || reloc_type == elfcpp::SHT_RELA)
 367           && object->section_info(i) == ranges_shndx)
 368         {
 369           reloc_shndx = i;
 370           break;
 371         }
 372     }
 373
 374   this->ranges_reloc_mapper_ = make_elf_reloc_mapper(object, symtab,
 375                                                      symtab_size);
 376   this->ranges_reloc_mapper_->initialize(reloc_shndx, reloc_type);
 377   this->reloc_type_ = reloc_type;
 378
 379   return true;
 380 }
 381
 382 // Read a range list from section RANGES_SHNDX at offset RANGES_OFFSET.
 383
 384 Dwarf_range_list*
 385 Dwarf_ranges_table::read_range_list(
 386     Relobj* object,
 387     const unsigned char* symtab,
 388     off_t symtab_size,
 389     unsigned int addr_size,
 390     unsigned int ranges_shndx,
 391     off_t offset)
 392 {
 393   Dwarf_range_list* ranges;
 394
 395   if (!this->read_ranges_table(object, symtab, symtab_size, ranges_shndx))
 396     return NULL;
 397
 398   // Correct the offset.  For incremental update links, we have a
 399   // relocated offset that is relative to the output section, but
 400   // here we need an offset relative to the input section.
 401   offset -= this->output_section_offset_;
 402
 403   // Read the range list at OFFSET.
 404   ranges = new Dwarf_range_list();
 405   off_t base = 0;
 406   for (;
 407        this->ranges_buffer_ + offset < this->ranges_buffer_end_;
 408        offset += 2 * addr_size)
 409     {
 410       off_t start;
 411       off_t end;
 412
 413       // Read the raw contents of the section.
 414       if (addr_size == 4)
 415         {
 416           start = this->dwinfo_->read_from_pointer<32>(this->ranges_buffer_
 417                                                        + offset);
 418           end = this->dwinfo_->read_from_pointer<32>(this->ranges_buffer_
 419                                                      + offset + 4);
 420         }
 421       else
 422         {
 423           start = this->dwinfo_->read_from_pointer<64>(this->ranges_buffer_
 424                                                        + offset);
 425           end = this->dwinfo_->read_from_pointer<64>(this->ranges_buffer_
 426                                                      + offset + 8);
 427         }
 428
 429       // Check for relocations and adjust the values.
 430       unsigned int shndx1 = 0;
 431       unsigned int shndx2 = 0;
 432       if (this->ranges_reloc_mapper_ != NULL)
 433         {
 434           shndx1 = this->lookup_reloc(offset, &start);
 435           shndx2 = this->lookup_reloc(offset + addr_size, &end);
 436         }
 437
 438       // End of list is marked by a pair of zeroes.
 439       if (shndx1 == 0 && start == 0 && end == 0)
 440         break;
 441
 442       // A "base address selection entry" is identified by
 443       // 0xffffffff for the first value of the pair.  The second
 444       // value is used as a base for subsequent range list entries.
 445       if (shndx1 == 0 && start == -1)
 446         base = end;
 447       else if (shndx1 == shndx2)
 448         {
 449           if (shndx1 == 0 || object->is_section_included(shndx1))
 450             ranges->add(shndx1, base + start, base + end);
 451         }
 452       else
 453         gold_warning(_("%s: DWARF info may be corrupt; offsets in a "
 454                        "range list entry are in different sections"),
 455                      object->name().c_str());
 456     }
 457
 458   return ranges;
 459 }
 460
 461 // Look for a relocation at offset OFF in the range table,
 462 // and return the section index and offset of the target.
 463
 464 unsigned int
 465 Dwarf_ranges_table::lookup_reloc(off_t off, off_t* target_off)
 466 {
 467   off_t value;
 468   unsigned int shndx =
 469       this->ranges_reloc_mapper_->get_reloc_target(off, &value);
 470   if (shndx == 0)
 471     return 0;
 472   if (this->reloc_type_ == elfcpp::SHT_REL)
 473     *target_off += value;
 474   else
 475     *target_off = value;
 476   return shndx;
 477 }
 478
 479 // class Dwarf_pubnames_table
 480
 481 // Read the pubnames section from the object file.
 482
 483 bool
 484 Dwarf_pubnames_table::read_section(Relobj* object, const unsigned char* symtab,
 485                                    off_t symtab_size)
 486 {
 487   section_size_type buffer_size;
 488   unsigned int shndx = 0;
 489
 490   // Find the .debug_pubnames/pubtypes section.
 491   const char* name = (this->is_pubtypes_
 492                       ? ".debug_pubtypes"
 493                       : ".debug_pubnames");
 494   for (unsigned int i = 1; i < object->shnum(); ++i)
 495     {
 496       if (object->section_name(i) == name)
 497         {
 498           shndx = i;
 499           this->output_section_offset_ = object->output_section_offset(i);
 500           break;
 501         }
 502     }
 503   if (shndx == 0)
 504     return false;
 505
 506
 507   this->buffer_ = object->decompressed_section_contents(shndx,
 508                                                         &buffer_size,
 509                                                         &this->owns_buffer_);
 510   if (this->buffer_ == NULL)
 511     return false;
 512   this->buffer_end_ = this->buffer_ + buffer_size;
 513
 514   // For incremental objects, we have no relocations.
 515   if (object->is_incremental())
 516     return true;
 517
 518   // Find the relocation section
 519   unsigned int reloc_shndx = 0;
 520   unsigned int reloc_type = 0;
 521   for (unsigned int i = 0; i < object->shnum(); ++i)
 522     {
 523       reloc_type = object->section_type(i);
 524       if ((reloc_type == elfcpp::SHT_REL
 525            || reloc_type == elfcpp::SHT_RELA)
 526           && object->section_info(i) == shndx)
 527         {
 528           reloc_shndx = i;
 529           break;
 530         }
 531     }
 532
 533   this->reloc_mapper_ = make_elf_reloc_mapper(object, symtab, symtab_size);
 534   this->reloc_mapper_->initialize(reloc_shndx, reloc_type);
 535   this->reloc_type_ = reloc_type;
 536
 537   return true;
 538 }
 539
 540 // Read the header for the set at OFFSET.
 541
 542 bool
 543 Dwarf_pubnames_table::read_header(off_t offset)
 544 {
 545   // Make sure we have actually read the section.
 546   gold_assert(this->buffer_ != NULL);
 547
 548   // Correct the offset.  For incremental update links, we have a
 549   // relocated offset that is relative to the output section, but
 550   // here we need an offset relative to the input section.
 551   offset -= this->output_section_offset_;
 552
 553   if (offset < 0 || offset + 14 >= this->buffer_end_ - this->buffer_)
 554     return false;
 555
 556   const unsigned char* pinfo = this->buffer_ + offset;
 557
 558   // Read the unit_length field.
 559   uint64_t unit_length = this->dwinfo_->read_from_pointer<32>(pinfo);
 560   pinfo += 4;
 561   if (unit_length == 0xffffffff)
 562     {
 563       unit_length = this->dwinfo_->read_from_pointer<64>(pinfo);
 564       this->unit_length_ = unit_length + 12;
 565       pinfo += 8;
 566       this->offset_size_ = 8;
 567     }
 568   else
 569     {
 570       this->unit_length_ = unit_length + 4;
 571       this->offset_size_ = 4;
 572     }
 573
 574   // Check the version.
 575   unsigned int version = this->dwinfo_->read_from_pointer<16>(pinfo);
 576   pinfo += 2;
 577   if (version != 2)
 578     return false;
 579
 580   this->reloc_mapper_->get_reloc_target(pinfo - this->buffer_,
 581                                         &this->cu_offset_);
 582
 583   // Skip the debug_info_offset and debug_info_size fields.
 584   pinfo += 2 * this->offset_size_;
 585
 586   if (pinfo >= this->buffer_end_)
 587     return false;
 588
 589   this->pinfo_ = pinfo;
 590   return true;
 591 }
 592
 593 // Read the next name from the set.
 594
 595 const char*
 596 Dwarf_pubnames_table::next_name()
 597 {
 598   const unsigned char* pinfo = this->pinfo_;
 599
 600   // Read the offset within the CU.  If this is zero, we have reached
 601   // the end of the list.
 602   uint32_t offset;
 603   if (this->offset_size_ == 4)
 604     offset = this->dwinfo_->read_from_pointer<32>(&pinfo);
 605   else
 606     offset = this->dwinfo_->read_from_pointer<64>(&pinfo);
 607   if (offset == 0)
 608     return NULL;
 609
 610   // Return a pointer to the string at the current location,
 611   // and advance the pointer to the next entry.
 612   const char* ret = reinterpret_cast<const char*>(pinfo);
 613   while (pinfo < this->buffer_end_ && *pinfo != '\0')
 614     ++pinfo;
 615   if (pinfo < this->buffer_end_)
 616     ++pinfo;
 617
 618   this->pinfo_ = pinfo;
 619   return ret;
 620 }
 621
 622 // class Dwarf_die
 623
 624 Dwarf_die::Dwarf_die(
 625     Dwarf_info_reader* dwinfo,
 626     off_t die_offset,
 627     Dwarf_die* parent)
 628   : dwinfo_(dwinfo), parent_(parent), die_offset_(die_offset),
 629     child_offset_(0), sibling_offset_(0), abbrev_code_(NULL), attributes_(),
 630     attributes_read_(false), name_(NULL), name_off_(-1), linkage_name_(NULL),
 631     linkage_name_off_(-1), string_shndx_(0), specification_(0),
 632     abstract_origin_(0)
 633 {
 634   size_t len;
 635   const unsigned char* pdie = dwinfo->buffer_at_offset(die_offset);
 636   if (pdie == NULL)
 637     return;
 638   unsigned int code = read_unsigned_LEB_128(pdie, &len);
 639   if (code == 0)
 640     {
 641       if (parent != NULL)
 642         parent->set_sibling_offset(die_offset + len);
 643       return;
 644     }
 645   this->attr_offset_ = len;
 646
 647   // Lookup the abbrev code in the abbrev table.
 648   this->abbrev_code_ = dwinfo->get_abbrev(code);
 649 }
 650
 651 // Read all the attributes of the DIE.
 652
 653 bool
 654 Dwarf_die::read_attributes()
 655 {
 656   if (this->attributes_read_)
 657     return true;
 658
 659   gold_assert(this->abbrev_code_ != NULL);
 660
 661   const unsigned char* pdie =
 662       this->dwinfo_->buffer_at_offset(this->die_offset_);
 663   if (pdie == NULL)
 664     return false;
 665   const unsigned char* pattr = pdie + this->attr_offset_;
 666
 667   unsigned int nattr = this->abbrev_code_->attributes.size();
 668   this->attributes_.reserve(nattr);
 669   for (unsigned int i = 0; i < nattr; ++i)
 670     {
 671       size_t len;
 672       unsigned int attr = this->abbrev_code_->attributes[i].attr;
 673       unsigned int form = this->abbrev_code_->attributes[i].form;
 674       if (form == elfcpp::DW_FORM_indirect)
 675         {
 676           form = read_unsigned_LEB_128(pattr, &len);
 677           pattr += len;
 678         }
 679       off_t attr_off = this->die_offset_ + (pattr - pdie);
 680       bool ref_form = false;
 681       Attribute_value attr_value;
 682       attr_value.attr = attr;
 683       attr_value.form = form;
 684       attr_value.aux.shndx = 0;
 685       switch(form)
 686         {
 687           case elfcpp::DW_FORM_flag_present:
 688             attr_value.val.intval = 1;
 689             break;
 690           case elfcpp::DW_FORM_strp:
 691             {
 692               off_t str_off;
 693               if (this->dwinfo_->offset_size() == 4)
 694                 str_off = this->dwinfo_->read_from_pointer<32>(&pattr);
 695               else
 696                 str_off = this->dwinfo_->read_from_pointer<64>(&pattr);
 697               unsigned int shndx =
 698                   this->dwinfo_->lookup_reloc(attr_off, &str_off);
 699               attr_value.aux.shndx = shndx;
 700               attr_value.val.refval = str_off;
 701               break;
 702             }
 703           case elfcpp::DW_FORM_sec_offset:
 704             {
 705               off_t sec_off;
 706               if (this->dwinfo_->offset_size() == 4)
 707                 sec_off = this->dwinfo_->read_from_pointer<32>(&pattr);
 708               else
 709                 sec_off = this->dwinfo_->read_from_pointer<64>(&pattr);
 710               unsigned int shndx =
 711                   this->dwinfo_->lookup_reloc(attr_off, &sec_off);
 712               attr_value.aux.shndx = shndx;
 713               attr_value.val.refval = sec_off;
 714               ref_form = true;
 715               break;
 716             }
 717           case elfcpp::DW_FORM_addr:
 718           case elfcpp::DW_FORM_ref_addr:
 719             {
 720               off_t sec_off;
 721               if (this->dwinfo_->address_size() == 4)
 722                 sec_off = this->dwinfo_->read_from_pointer<32>(&pattr);
 723               else
 724                 sec_off = this->dwinfo_->read_from_pointer<64>(&pattr);
 725               unsigned int shndx =
 726                   this->dwinfo_->lookup_reloc(attr_off, &sec_off);
 727               attr_value.aux.shndx = shndx;
 728               attr_value.val.refval = sec_off;
 729               ref_form = true;
 730               break;
 731             }
 732           case elfcpp::DW_FORM_block1:
 733             attr_value.aux.blocklen = *pattr++;
 734             attr_value.val.blockval = pattr;
 735             pattr += attr_value.aux.blocklen;
 736             break;
 737           case elfcpp::DW_FORM_block2:
 738             attr_value.aux.blocklen =
 739                 this->dwinfo_->read_from_pointer<16>(&pattr);
 740             attr_value.val.blockval = pattr;
 741             pattr += attr_value.aux.blocklen;
 742             break;
 743           case elfcpp::DW_FORM_block4:
 744             attr_value.aux.blocklen =
 745                 this->dwinfo_->read_from_pointer<32>(&pattr);
 746             attr_value.val.blockval = pattr;
 747             pattr += attr_value.aux.blocklen;
 748             break;
 749           case elfcpp::DW_FORM_block:
 750           case elfcpp::DW_FORM_exprloc:
 751             attr_value.aux.blocklen = read_unsigned_LEB_128(pattr, &len);
 752             attr_value.val.blockval = pattr + len;
 753             pattr += len + attr_value.aux.blocklen;
 754             break;
 755           case elfcpp::DW_FORM_data1:
 756           case elfcpp::DW_FORM_flag:
 757             attr_value.val.intval = *pattr++;
 758             break;
 759           case elfcpp::DW_FORM_ref1:
 760             attr_value.val.refval = *pattr++;
 761             ref_form = true;
 762             break;
 763           case elfcpp::DW_FORM_data2:
 764             attr_value.val.intval =
 765                 this->dwinfo_->read_from_pointer<16>(&pattr);
 766             break;
 767           case elfcpp::DW_FORM_ref2:
 768             attr_value.val.refval =
 769                 this->dwinfo_->read_from_pointer<16>(&pattr);
 770             ref_form = true;
 771             break;
 772           case elfcpp::DW_FORM_data4:
 773             {
 774               off_t sec_off;
 775               sec_off = this->dwinfo_->read_from_pointer<32>(&pattr);
 776               unsigned int shndx =
 777                   this->dwinfo_->lookup_reloc(attr_off, &sec_off);
 778               attr_value.aux.shndx = shndx;
 779               attr_value.val.intval = sec_off;
 780               break;
 781             }
 782           case elfcpp::DW_FORM_ref4:
 783             {
 784               off_t sec_off;
 785               sec_off = this->dwinfo_->read_from_pointer<32>(&pattr);
 786               unsigned int shndx =
 787                   this->dwinfo_->lookup_reloc(attr_off, &sec_off);
 788               attr_value.aux.shndx = shndx;
 789               attr_value.val.refval = sec_off;
 790               ref_form = true;
 791               break;
 792             }
 793           case elfcpp::DW_FORM_data8:
 794             {
 795               off_t sec_off;
 796               sec_off = this->dwinfo_->read_from_pointer<64>(&pattr);
 797               unsigned int shndx =
 798                   this->dwinfo_->lookup_reloc(attr_off, &sec_off);
 799               attr_value.aux.shndx = shndx;
 800               attr_value.val.intval = sec_off;
 801               break;
 802             }
 803           case elfcpp::DW_FORM_ref_sig8:
 804             attr_value.val.uintval =
 805                 this->dwinfo_->read_from_pointer<64>(&pattr);
 806             break;
 807           case elfcpp::DW_FORM_ref8:
 808             {
 809               off_t sec_off;
 810               sec_off = this->dwinfo_->read_from_pointer<64>(&pattr);
 811               unsigned int shndx =
 812                   this->dwinfo_->lookup_reloc(attr_off, &sec_off);
 813               attr_value.aux.shndx = shndx;
 814               attr_value.val.refval = sec_off;
 815               ref_form = true;
 816               break;
 817             }
 818           case elfcpp::DW_FORM_ref_udata:
 819             attr_value.val.refval = read_unsigned_LEB_128(pattr, &len);
 820             ref_form = true;
 821             pattr += len;
 822             break;
 823           case elfcpp::DW_FORM_udata:
 824           case elfcpp::DW_FORM_GNU_addr_index:
 825           case elfcpp::DW_FORM_GNU_str_index:
 826             attr_value.val.uintval = read_unsigned_LEB_128(pattr, &len);
 827             pattr += len;
 828             break;
 829           case elfcpp::DW_FORM_sdata:
 830             attr_value.val.intval = read_signed_LEB_128(pattr, &len);
 831             pattr += len;
 832             break;
 833           case elfcpp::DW_FORM_string:
 834             attr_value.val.stringval = reinterpret_cast<const char*>(pattr);
 835             len = strlen(attr_value.val.stringval);
 836             pattr += len + 1;
 837             break;
 838           default:
 839             return false;
 840         }
 841
 842       // Cache the most frequently-requested attributes.
 843       switch (attr)
 844         {
 845           case elfcpp::DW_AT_name:
 846             if (form == elfcpp::DW_FORM_string)
 847               this->name_ = attr_value.val.stringval;
 848             else if (form == elfcpp::DW_FORM_strp)
 849               {
 850                 // All indirect strings should refer to the same
 851                 // string section, so we just save the last one seen.
 852                 this->string_shndx_ = attr_value.aux.shndx;
 853                 this->name_off_ = attr_value.val.refval;
 854               }
 855             break;
 856           case elfcpp::DW_AT_linkage_name:
 857           case elfcpp::DW_AT_MIPS_linkage_name:
 858             if (form == elfcpp::DW_FORM_string)
 859               this->linkage_name_ = attr_value.val.stringval;
 860             else if (form == elfcpp::DW_FORM_strp)
 861               {
 862                 // All indirect strings should refer to the same
 863                 // string section, so we just save the last one seen.
 864                 this->string_shndx_ = attr_value.aux.shndx;
 865                 this->linkage_name_off_ = attr_value.val.refval;
 866               }
 867             break;
 868           case elfcpp::DW_AT_specification:
 869             if (ref_form)
 870               this->specification_ = attr_value.val.refval;
 871             break;
 872           case elfcpp::DW_AT_abstract_origin:
 873             if (ref_form)
 874               this->abstract_origin_ = attr_value.val.refval;
 875             break;
 876           case elfcpp::DW_AT_sibling:
 877             if (ref_form && attr_value.aux.shndx == 0)
 878               this->sibling_offset_ = attr_value.val.refval;
 879           default:
 880             break;
 881         }
 882
 883       this->attributes_.push_back(attr_value);
 884     }
 885
 886   // Now that we know where the next DIE begins, record the offset
 887   // to avoid later recalculation.
 888   if (this->has_children())
 889     this->child_offset_ = this->die_offset_ + (pattr - pdie);
 890   else
 891     this->sibling_offset_ = this->die_offset_ + (pattr - pdie);
 892
 893   this->attributes_read_ = true;
 894   return true;
 895 }
 896
 897 // Skip all the attributes of the DIE and return the offset of the next DIE.
 898
 899 off_t
 900 Dwarf_die::skip_attributes()
 901 {
 902   gold_assert(this->abbrev_code_ != NULL);
 903
 904   const unsigned char* pdie =
 905       this->dwinfo_->buffer_at_offset(this->die_offset_);
 906   if (pdie == NULL)
 907     return 0;
 908   const unsigned char* pattr = pdie + this->attr_offset_;
 909
 910   for (unsigned int i = 0; i < this->abbrev_code_->attributes.size(); ++i)
 911     {
 912       size_t len;
 913       unsigned int form = this->abbrev_code_->attributes[i].form;
 914       if (form == elfcpp::DW_FORM_indirect)
 915         {
 916           form = read_unsigned_LEB_128(pattr, &len);
 917           pattr += len;
 918         }
 919       switch(form)
 920         {
 921           case elfcpp::DW_FORM_flag_present:
 922             break;
 923           case elfcpp::DW_FORM_strp:
 924           case elfcpp::DW_FORM_sec_offset:
 925             pattr += this->dwinfo_->offset_size();
 926             break;
 927           case elfcpp::DW_FORM_addr:
 928           case elfcpp::DW_FORM_ref_addr:
 929             pattr += this->dwinfo_->address_size();
 930             break;
 931           case elfcpp::DW_FORM_block1:
 932             pattr += 1 + *pattr;
 933             break;
 934           case elfcpp::DW_FORM_block2:
 935             {
 936               uint16_t block_size;
 937               block_size = this->dwinfo_->read_from_pointer<16>(&pattr);
 938               pattr += block_size;
 939               break;
 940             }
 941           case elfcpp::DW_FORM_block4:
 942             {
 943               uint32_t block_size;
 944               block_size = this->dwinfo_->read_from_pointer<32>(&pattr);
 945               pattr += block_size;
 946               break;
 947             }
 948           case elfcpp::DW_FORM_block:
 949           case elfcpp::DW_FORM_exprloc:
 950             {
 951               uint64_t block_size;
 952               block_size = read_unsigned_LEB_128(pattr, &len);
 953               pattr += len + block_size;
 954               break;
 955             }
 956           case elfcpp::DW_FORM_data1:
 957           case elfcpp::DW_FORM_ref1:
 958           case elfcpp::DW_FORM_flag:
 959             pattr += 1;
 960             break;
 961           case elfcpp::DW_FORM_data2:
 962           case elfcpp::DW_FORM_ref2:
 963             pattr += 2;
 964             break;
 965           case elfcpp::DW_FORM_data4:
 966           case elfcpp::DW_FORM_ref4:
 967             pattr += 4;
 968             break;
 969           case elfcpp::DW_FORM_data8:
 970           case elfcpp::DW_FORM_ref8:
 971           case elfcpp::DW_FORM_ref_sig8:
 972             pattr += 8;
 973             break;
 974           case elfcpp::DW_FORM_ref_udata:
 975           case elfcpp::DW_FORM_udata:
 976           case elfcpp::DW_FORM_GNU_addr_index:
 977           case elfcpp::DW_FORM_GNU_str_index:
 978             read_unsigned_LEB_128(pattr, &len);
 979             pattr += len;
 980             break;
 981           case elfcpp::DW_FORM_sdata:
 982             read_signed_LEB_128(pattr, &len);
 983             pattr += len;
 984             break;
 985           case elfcpp::DW_FORM_string:
 986             len = strlen(reinterpret_cast<const char*>(pattr));
 987             pattr += len + 1;
 988             break;
 989           default:
 990             return 0;
 991         }
 992     }
 993
 994   return this->die_offset_ + (pattr - pdie);
 995 }
 996
 997 // Get the name of the DIE and cache it.
 998
 999 void
1000 Dwarf_die::set_name()
1001 {
1002   if (this->name_ != NULL || !this->read_attributes())
1003     return;
1004   if (this->name_off_ != -1)
1005     this->name_ = this->dwinfo_->get_string(this->name_off_,
1006                                             this->string_shndx_);
1007 }
1008
1009 // Get the linkage name of the DIE and cache it.
1010
1011 void
1012 Dwarf_die::set_linkage_name()
1013 {
1014   if (this->linkage_name_ != NULL || !this->read_attributes())
1015     return;
1016   if (this->linkage_name_off_ != -1)
1017     this->linkage_name_ = this->dwinfo_->get_string(this->linkage_name_off_,
1018                                                     this->string_shndx_);
1019 }
1020
1021 // Return the value of attribute ATTR.
1022
1023 const Dwarf_die::Attribute_value*
1024 Dwarf_die::attribute(unsigned int attr)
1025 {
1026   if (!this->read_attributes())
1027     return NULL;
1028   for (unsigned int i = 0; i < this->attributes_.size(); ++i)
1029     {
1030       if (this->attributes_[i].attr == attr)
1031         return &this->attributes_[i];
1032     }
1033   return NULL;
1034 }
1035
1036 const char*
1037 Dwarf_die::string_attribute(unsigned int attr)
1038 {
1039   const Attribute_value* attr_val = this->attribute(attr);
1040   if (attr_val == NULL)
1041     return NULL;
1042   switch (attr_val->form)
1043     {
1044       case elfcpp::DW_FORM_string:
1045         return attr_val->val.stringval;
1046       case elfcpp::DW_FORM_strp:
1047         return this->dwinfo_->get_string(attr_val->val.refval,
1048                                          attr_val->aux.shndx);
1049       default:
1050         return NULL;
1051     }
1052 }
1053
1054 int64_t
1055 Dwarf_die::int_attribute(unsigned int attr)
1056 {
1057   const Attribute_value* attr_val = this->attribute(attr);
1058   if (attr_val == NULL)
1059     return 0;
1060   switch (attr_val->form)
1061     {
1062       case elfcpp::DW_FORM_flag_present:
1063       case elfcpp::DW_FORM_data1:
1064       case elfcpp::DW_FORM_flag:
1065       case elfcpp::DW_FORM_data2:
1066       case elfcpp::DW_FORM_data4:
1067       case elfcpp::DW_FORM_data8:
1068       case elfcpp::DW_FORM_sdata:
1069         return attr_val->val.intval;
1070       default:
1071         return 0;
1072     }
1073 }
1074
1075 uint64_t
1076 Dwarf_die::uint_attribute(unsigned int attr)
1077 {
1078   const Attribute_value* attr_val = this->attribute(attr);
1079   if (attr_val == NULL)
1080     return 0;
1081   switch (attr_val->form)
1082     {
1083       case elfcpp::DW_FORM_flag_present:
1084       case elfcpp::DW_FORM_data1:
1085       case elfcpp::DW_FORM_flag:
1086       case elfcpp::DW_FORM_data4:
1087       case elfcpp::DW_FORM_data8:
1088       case elfcpp::DW_FORM_ref_sig8:
1089       case elfcpp::DW_FORM_udata:
1090         return attr_val->val.uintval;
1091       default:
1092         return 0;
1093     }
1094 }
1095
1096 off_t
1097 Dwarf_die::ref_attribute(unsigned int attr, unsigned int* shndx)
1098 {
1099   const Attribute_value* attr_val = this->attribute(attr);
1100   if (attr_val == NULL)
1101     return -1;
1102   switch (attr_val->form)
1103     {
1104       case elfcpp::DW_FORM_sec_offset:
1105       case elfcpp::DW_FORM_addr:
1106       case elfcpp::DW_FORM_ref_addr:
1107       case elfcpp::DW_FORM_ref1:
1108       case elfcpp::DW_FORM_ref2:
1109       case elfcpp::DW_FORM_ref4:
1110       case elfcpp::DW_FORM_ref8:
1111       case elfcpp::DW_FORM_ref_udata:
1112         *shndx = attr_val->aux.shndx;
1113         return attr_val->val.refval;
1114       case elfcpp::DW_FORM_ref_sig8:
1115         *shndx = attr_val->aux.shndx;
1116         return attr_val->val.uintval;
1117       case elfcpp::DW_FORM_data4:
1118       case elfcpp::DW_FORM_data8:
1119         *shndx = attr_val->aux.shndx;
1120         return attr_val->val.intval;
1121       default:
1122         return -1;
1123     }
1124 }
1125
1126 off_t
1127 Dwarf_die::address_attribute(unsigned int attr, unsigned int* shndx)
1128 {
1129   const Attribute_value* attr_val = this->attribute(attr);
1130   if (attr_val == NULL || attr_val->form != elfcpp::DW_FORM_addr)
1131     return -1;
1132
1133   *shndx = attr_val->aux.shndx;
1134   return attr_val->val.refval;
1135 }
1136
1137 // Return the offset of this DIE's first child.
1138
1139 off_t
1140 Dwarf_die::child_offset()
1141 {
1142   gold_assert(this->abbrev_code_ != NULL);
1143   if (!this->has_children())
1144     return 0;
1145   if (this->child_offset_ == 0)
1146     this->child_offset_ = this->skip_attributes();
1147   return this->child_offset_;
1148 }
1149
1150 // Return the offset of this DIE's next sibling.
1151
1152 off_t
1153 Dwarf_die::sibling_offset()
1154 {
1155   gold_assert(this->abbrev_code_ != NULL);
1156
1157   if (this->sibling_offset_ != 0)
1158     return this->sibling_offset_;
1159
1160   if (!this->has_children())
1161     {
1162       this->sibling_offset_ = this->skip_attributes();
1163       return this->sibling_offset_;
1164     }
1165
1166   if (this->has_sibling_attribute())
1167     {
1168       if (!this->read_attributes())
1169         return 0;
1170       if (this->sibling_offset_ != 0)
1171         return this->sibling_offset_;
1172     }
1173
1174   // Skip over the children.
1175   off_t child_offset = this->child_offset();
1176   while (child_offset > 0)
1177     {
1178       Dwarf_die die(this->dwinfo_, child_offset, this);
1179       // The Dwarf_die ctor will set this DIE's sibling offset
1180       // when it reads a zero abbrev code.
1181       if (die.tag() == 0)
1182         break;
1183       child_offset = die.sibling_offset();
1184     }
1185
1186   // This should be set by now.  If not, there was a problem reading
1187   // the DWARF info, and we return 0.
1188   return this->sibling_offset_;
1189 }
1190
1191 // class Dwarf_info_reader
1192
1193 // Begin parsing the debug info.  This calls visit_compilation_unit()
1194 // or visit_type_unit() for each compilation or type unit found in the
1195 // section, and visit_die() for each top-level DIE.
1196
1197 void
1198 Dwarf_info_reader::parse()
1199 {
1200   if (this->object_->is_big_endian())
1201     {
1202 #if defined(HAVE_TARGET_32_BIG) || defined(HAVE_TARGET_64_BIG)
1203       this->do_parse<true>();
1204 #else
1205       gold_unreachable();
1206 #endif
1207     }
1208   else
1209     {
1210 #if defined(HAVE_TARGET_32_LITTLE) || defined(HAVE_TARGET_64_LITTLE)
1211       this->do_parse<false>();
1212 #else
1213       gold_unreachable();
1214 #endif
1215     }
1216 }
1217
1218 template<bool big_endian>
1219 void
1220 Dwarf_info_reader::do_parse()
1221 {
1222   // Get the section contents and decompress if necessary.
1223   section_size_type buffer_size;
1224   bool buffer_is_new;
1225   this->buffer_ = this->object_->decompressed_section_contents(this->shndx_,
1226                                                                &buffer_size,
1227                                                                &buffer_is_new);
1228   if (this->buffer_ == NULL || buffer_size == 0)
1229     return;
1230   this->buffer_end_ = this->buffer_ + buffer_size;
1231
1232   // The offset of this input section in the output section.
1233   off_t section_offset = this->object_->output_section_offset(this->shndx_);
1234
1235   // Start tracking relocations for this section.
1236   this->reloc_mapper_ = make_elf_reloc_mapper(this->object_, this->symtab_,
1237                                               this->symtab_size_);
1238   this->reloc_mapper_->initialize(this->reloc_shndx_, this->reloc_type_);
1239
1240   // Loop over compilation units (or type units).
1241   unsigned int abbrev_shndx = this->abbrev_shndx_;
1242   off_t abbrev_offset = 0;
1243   const unsigned char* pinfo = this->buffer_;
1244   while (pinfo < this->buffer_end_)
1245     {
1246       // Read the compilation (or type) unit header.
1247       const unsigned char* cu_start = pinfo;
1248       this->cu_offset_ = cu_start - this->buffer_;
1249       this->cu_length_ = this->buffer_end_ - cu_start;
1250
1251       // Read unit_length (4 or 12 bytes).
1252       if (!this->check_buffer(pinfo + 4))
1253         break;
1254       uint32_t unit_length =
1255           elfcpp::Swap_unaligned<32, big_endian>::readval(pinfo);
1256       pinfo += 4;
1257       if (unit_length == 0xffffffff)
1258         {
1259           if (!this->check_buffer(pinfo + 8))
1260             break;
1261           unit_length = elfcpp::Swap_unaligned<64, big_endian>::readval(pinfo);
1262           pinfo += 8;
1263           this->offset_size_ = 8;
1264         }
1265       else
1266         this->offset_size_ = 4;
1267       if (!this->check_buffer(pinfo + unit_length))
1268         break;
1269       const unsigned char* cu_end = pinfo + unit_length;
1270       this->cu_length_ = cu_end - cu_start;
1271       if (!this->check_buffer(pinfo + 2 + this->offset_size_ + 1))
1272         break;
1273
1274       // Read version (2 bytes).
1275       this->cu_version_ =
1276           elfcpp::Swap_unaligned<16, big_endian>::readval(pinfo);
1277       pinfo += 2;
1278
1279       // Read debug_abbrev_offset (4 or 8 bytes).
1280       if (this->offset_size_ == 4)
1281         abbrev_offset = elfcpp::Swap_unaligned<32, big_endian>::readval(pinfo);
1282       else
1283         abbrev_offset = elfcpp::Swap_unaligned<64, big_endian>::readval(pinfo);
1284       if (this->reloc_shndx_ > 0)
1285         {
1286           off_t reloc_offset = pinfo - this->buffer_;
1287           off_t value;
1288           abbrev_shndx =
1289               this->reloc_mapper_->get_reloc_target(reloc_offset, &value);
1290           if (abbrev_shndx == 0)
1291             return;
1292           if (this->reloc_type_ == elfcpp::SHT_REL)
1293             abbrev_offset += value;
1294           else
1295             abbrev_offset = value;
1296         }
1297       pinfo += this->offset_size_;
1298
1299       // Read address_size (1 byte).
1300       this->address_size_ = *pinfo++;
1301
1302       // For type units, read the two extra fields.
1303       uint64_t signature = 0;
1304       off_t type_offset = 0;
1305       if (this->is_type_unit_)
1306         {
1307           if (!this->check_buffer(pinfo + 8 + this->offset_size_))
1308             break;
1309
1310           // Read type_signature (8 bytes).
1311           signature = elfcpp::Swap_unaligned<64, big_endian>::readval(pinfo);
1312           pinfo += 8;
1313
1314           // Read type_offset (4 or 8 bytes).
1315           if (this->offset_size_ == 4)
1316             type_offset =
1317                 elfcpp::Swap_unaligned<32, big_endian>::readval(pinfo);
1318           else
1319             type_offset =
1320                 elfcpp::Swap_unaligned<64, big_endian>::readval(pinfo);
1321           pinfo += this->offset_size_;
1322         }
1323
1324       // Read the .debug_abbrev table.
1325       this->abbrev_table_.read_abbrevs(this->object_, abbrev_shndx,
1326                                        abbrev_offset);
1327
1328       // Visit the root DIE.
1329       Dwarf_die root_die(this,
1330                          pinfo - (this->buffer_ + this->cu_offset_),
1331                          NULL);
1332       if (root_die.tag() != 0)
1333         {
1334           // Visit the CU or TU.
1335           if (this->is_type_unit_)
1336             this->visit_type_unit(section_offset + this->cu_offset_,
1337                                   cu_end - cu_start, type_offset, signature,
1338                                   &root_die);
1339           else
1340             this->visit_compilation_unit(section_offset + this->cu_offset_,
1341                                          cu_end - cu_start, &root_die);
1342         }
1343
1344       // Advance to the next CU.
1345       pinfo = cu_end;
1346     }
1347
1348   if (buffer_is_new)
1349     {
1350       delete[] this->buffer_;
1351       this->buffer_ = NULL;
1352     }
1353 }
1354
1355 // Read the DWARF string table.
1356
1357 bool
1358 Dwarf_info_reader::do_read_string_table(unsigned int string_shndx)
1359 {
1360   Relobj* object = this->object_;
1361
1362   // If we don't have relocations, string_shndx will be 0, and
1363   // we'll have to hunt for the .debug_str section.
1364   if (string_shndx == 0)
1365     {
1366       for (unsigned int i = 1; i < this->object_->shnum(); ++i)
1367         {
1368           std::string name = object->section_name(i);
1369           if (name == ".debug_str")
1370             {
1371               string_shndx = i;
1372               this->string_output_section_offset_ =
1373                   object->output_section_offset(i);
1374               break;
1375             }
1376         }
1377       if (string_shndx == 0)
1378         return false;
1379     }
1380
1381   if (this->owns_string_buffer_ && this->string_buffer_ != NULL)
1382     {
1383       delete[] this->string_buffer_;
1384       this->owns_string_buffer_ = false;
1385     }
1386
1387   // Get the secton contents and decompress if necessary.
1388   section_size_type buffer_size;
1389   const unsigned char* buffer =
1390       object->decompressed_section_contents(string_shndx,
1391                                             &buffer_size,
1392                                             &this->owns_string_buffer_);
1393   this->string_buffer_ = reinterpret_cast<const char*>(buffer);
1394   this->string_buffer_end_ = this->string_buffer_ + buffer_size;
1395   this->string_shndx_ = string_shndx;
1396   return true;
1397 }
1398
1399 // Read a possibly unaligned integer of SIZE.
1400 template <int valsize>
1401 inline typename elfcpp::Valtype_base<valsize>::Valtype
1402 Dwarf_info_reader::read_from_pointer(const unsigned char* source)
1403 {
1404   typename elfcpp::Valtype_base<valsize>::Valtype return_value;
1405   if (this->object_->is_big_endian())
1406     return_value = elfcpp::Swap_unaligned<valsize, true>::readval(source);
1407   else
1408     return_value = elfcpp::Swap_unaligned<valsize, false>::readval(source);
1409   return return_value;
1410 }
1411
1412 // Read a possibly unaligned integer of SIZE.  Update SOURCE after read.
1413 template <int valsize>
1414 inline typename elfcpp::Valtype_base<valsize>::Valtype
1415 Dwarf_info_reader::read_from_pointer(const unsigned char** source)
1416 {
1417   typename elfcpp::Valtype_base<valsize>::Valtype return_value;
1418   if (this->object_->is_big_endian())
1419     return_value = elfcpp::Swap_unaligned<valsize, true>::readval(*source);
1420   else
1421     return_value = elfcpp::Swap_unaligned<valsize, false>::readval(*source);
1422   *source += valsize / 8;
1423   return return_value;
1424 }
1425
1426 // Look for a relocation at offset ATTR_OFF in the dwarf info,
1427 // and return the section index and offset of the target.
1428
1429 unsigned int
1430 Dwarf_info_reader::lookup_reloc(off_t attr_off, off_t* target_off)
1431 {
1432   off_t value;
1433   attr_off += this->cu_offset_;
1434   unsigned int shndx = this->reloc_mapper_->get_reloc_target(attr_off, &value);
1435   if (shndx == 0)
1436     return 0;
1437   if (this->reloc_type_ == elfcpp::SHT_REL)
1438     *target_off += value;
1439   else
1440     *target_off = value;
1441   return shndx;
1442 }
1443
1444 // Return a string from the DWARF string table.
1445
1446 const char*
1447 Dwarf_info_reader::get_string(off_t str_off, unsigned int string_shndx)
1448 {
1449   if (!this->read_string_table(string_shndx))
1450     return NULL;
1451
1452   // Correct the offset.  For incremental update links, we have a
1453   // relocated offset that is relative to the output section, but
1454   // here we need an offset relative to the input section.
1455   str_off -= this->string_output_section_offset_;
1456
1457   const char* p = this->string_buffer_ + str_off;
1458
1459   if (p < this->string_buffer_ || p >= this->string_buffer_end_)
1460     return NULL;
1461
1462   return p;
1463 }
1464
1465 // The following are default, do-nothing, implementations of the
1466 // hook methods normally provided by a derived class.  We provide
1467 // default implementations rather than no implementation so that
1468 // a derived class needs to implement only the hooks that it needs
1469 // to use.
1470
1471 // Process a compilation unit and parse its child DIE.
1472
1473 void
1474 Dwarf_info_reader::visit_compilation_unit(off_t, off_t, Dwarf_die*)
1475 {
1476 }
1477
1478 // Process a type unit and parse its child DIE.
1479
1480 void
1481 Dwarf_info_reader::visit_type_unit(off_t, off_t, off_t, uint64_t, Dwarf_die*)
1482 {
1483 }
1484
1485 // Print a warning about a corrupt debug section.
1486
1487 void
1488 Dwarf_info_reader::warn_corrupt_debug_section() const
1489 {
1490   gold_warning(_("%s: corrupt debug info in %s"),
1491                this->object_->name().c_str(),
1492                this->object_->section_name(this->shndx_).c_str());
1493 }
1494
1495 // class Sized_dwarf_line_info
1496
1497 struct LineStateMachine
1498 {
1499   int file_num;
1500   uint64_t address;
1501   int line_num;
1502   int column_num;
1503   unsigned int shndx;    // the section address refers to
1504   bool is_stmt;          // stmt means statement.
1505   bool basic_block;
1506   bool end_sequence;
1507 };
1508
1509 static void
1510 ResetLineStateMachine(struct LineStateMachine* lsm, bool default_is_stmt)
1511 {
1512   lsm->file_num = 1;
1513   lsm->address = 0;
1514   lsm->line_num = 1;
1515   lsm->column_num = 0;
1516   lsm->shndx = -1U;
1517   lsm->is_stmt = default_is_stmt;
1518   lsm->basic_block = false;
1519   lsm->end_sequence = false;
1520 }
1521
1522 template<int size, bool big_endian>
1523 Sized_dwarf_line_info<size, big_endian>::Sized_dwarf_line_info(
1524     Object* object,
1525     unsigned int read_shndx)
1526   : data_valid_(false), buffer_(NULL), buffer_start_(NULL),
1527     reloc_mapper_(NULL), symtab_buffer_(NULL), directories_(), files_(),
1528     current_header_index_(-1)
1529 {
1530   unsigned int debug_shndx;
1531
1532   for (debug_shndx = 1; debug_shndx < object->shnum(); ++debug_shndx)
1533     {
1534       // FIXME: do this more efficiently: section_name() isn't super-fast
1535       std::string name = object->section_name(debug_shndx);
1536       if (name == ".debug_line" || name == ".zdebug_line")
1537         {
1538           section_size_type buffer_size;
1539           bool is_new = false;
1540           this->buffer_ = object->decompressed_section_contents(debug_shndx,
1541                                                                 &buffer_size,
1542                                                                 &is_new);
1543           if (is_new)
1544             this->buffer_start_ = this->buffer_;
1545           this->buffer_end_ = this->buffer_ + buffer_size;
1546           break;
1547         }
1548     }
1549   if (this->buffer_ == NULL)
1550     return;
1551
1552   // Find the relocation section for ".debug_line".
1553   // We expect these for relobjs (.o's) but not dynobjs (.so's).
1554   unsigned int reloc_shndx = 0;
1555   for (unsigned int i = 0; i < object->shnum(); ++i)
1556     {
1557       unsigned int reloc_sh_type = object->section_type(i);
1558       if ((reloc_sh_type == elfcpp::SHT_REL
1559            || reloc_sh_type == elfcpp::SHT_RELA)
1560           && object->section_info(i) == debug_shndx)
1561         {
1562           reloc_shndx = i;
1563           this->track_relocs_type_ = reloc_sh_type;
1564           break;
1565         }
1566     }
1567
1568   // Finally, we need the symtab section to interpret the relocs.
1569   if (reloc_shndx != 0)
1570     {
1571       unsigned int symtab_shndx;
1572       for (symtab_shndx = 0; symtab_shndx < object->shnum(); ++symtab_shndx)
1573         if (object->section_type(symtab_shndx) == elfcpp::SHT_SYMTAB)
1574           {
1575             this->symtab_buffer_ = object->section_contents(
1576                 symtab_shndx, &this->symtab_buffer_size_, false);
1577             break;
1578           }
1579       if (this->symtab_buffer_ == NULL)
1580         return;
1581     }
1582
1583   this->reloc_mapper_ =
1584       new Sized_elf_reloc_mapper<size, big_endian>(object,
1585                                                    this->symtab_buffer_,
1586                                                    this->symtab_buffer_size_);
1587   if (!this->reloc_mapper_->initialize(reloc_shndx, this->track_relocs_type_))
1588     return;
1589
1590   // Now that we have successfully read all the data, parse the debug
1591   // info.
1592   this->data_valid_ = true;
1593   this->read_line_mappings(read_shndx);
1594 }
1595
1596 // Read the DWARF header.
1597
1598 template<int size, bool big_endian>
1599 const unsigned char*
1600 Sized_dwarf_line_info<size, big_endian>::read_header_prolog(
1601     const unsigned char* lineptr)
1602 {
1603   uint32_t initial_length = elfcpp::Swap_unaligned<32, big_endian>::readval(lineptr);
1604   lineptr += 4;
1605
1606   // In DWARF2/3, if the initial length is all 1 bits, then the offset
1607   // size is 8 and we need to read the next 8 bytes for the real length.
1608   if (initial_length == 0xffffffff)
1609     {
1610       header_.offset_size = 8;
1611       initial_length = elfcpp::Swap_unaligned<64, big_endian>::readval(lineptr);
1612       lineptr += 8;
1613     }
1614   else
1615     header_.offset_size = 4;
1616
1617   header_.total_length = initial_length;
1618
1619   gold_assert(lineptr + header_.total_length <= buffer_end_);
1620
1621   header_.version = elfcpp::Swap_unaligned<16, big_endian>::readval(lineptr);
1622   lineptr += 2;
1623
1624   if (header_.offset_size == 4)
1625     header_.prologue_length = elfcpp::Swap_unaligned<32, big_endian>::readval(lineptr);
1626   else
1627     header_.prologue_length = elfcpp::Swap_unaligned<64, big_endian>::readval(lineptr);
1628   lineptr += header_.offset_size;
1629
1630   header_.min_insn_length = *lineptr;
1631   lineptr += 1;
1632
1633   header_.default_is_stmt = *lineptr;
1634   lineptr += 1;
1635
1636   header_.line_base = *reinterpret_cast<const signed char*>(lineptr);
1637   lineptr += 1;
1638
1639   header_.line_range = *lineptr;
1640   lineptr += 1;
1641
1642   header_.opcode_base = *lineptr;
1643   lineptr += 1;
1644
1645   header_.std_opcode_lengths.resize(header_.opcode_base + 1);
1646   header_.std_opcode_lengths[0] = 0;
1647   for (int i = 1; i < header_.opcode_base; i++)
1648     {
1649       header_.std_opcode_lengths[i] = *lineptr;
1650       lineptr += 1;
1651     }
1652
1653   return lineptr;
1654 }
1655
1656 // The header for a debug_line section is mildly complicated, because
1657 // the line info is very tightly encoded.
1658
1659 template<int size, bool big_endian>
1660 const unsigned char*
1661 Sized_dwarf_line_info<size, big_endian>::read_header_tables(
1662     const unsigned char* lineptr)
1663 {
1664   ++this->current_header_index_;
1665
1666   // Create a new directories_ entry and a new files_ entry for our new
1667   // header.  We initialize each with a single empty element, because
1668   // dwarf indexes directory and filenames starting at 1.
1669   gold_assert(static_cast<int>(this->directories_.size())
1670               == this->current_header_index_);
1671   gold_assert(static_cast<int>(this->files_.size())
1672               == this->current_header_index_);
1673   this->directories_.push_back(std::vector<std::string>(1));
1674   this->files_.push_back(std::vector<std::pair<int, std::string> >(1));
1675
1676   // It is legal for the directory entry table to be empty.
1677   if (*lineptr)
1678     {
1679       int dirindex = 1;
1680       while (*lineptr)
1681         {
1682           const char* dirname = reinterpret_cast<const char*>(lineptr);
1683           gold_assert(dirindex
1684                       == static_cast<int>(this->directories_.back().size()));
1685           this->directories_.back().push_back(dirname);
1686           lineptr += this->directories_.back().back().size() + 1;
1687           dirindex++;
1688         }
1689     }
1690   lineptr++;
1691
1692   // It is also legal for the file entry table to be empty.
1693   if (*lineptr)
1694     {
1695       int fileindex = 1;
1696       size_t len;
1697       while (*lineptr)
1698         {
1699           const char* filename = reinterpret_cast<const char*>(lineptr);
1700           lineptr += strlen(filename) + 1;
1701
1702           uint64_t dirindex = read_unsigned_LEB_128(lineptr, &len);
1703           lineptr += len;
1704
1705           if (dirindex >= this->directories_.back().size())
1706             dirindex = 0;
1707           int dirindexi = static_cast<int>(dirindex);
1708
1709           read_unsigned_LEB_128(lineptr, &len);   // mod_time
1710           lineptr += len;
1711
1712           read_unsigned_LEB_128(lineptr, &len);   // filelength
1713           lineptr += len;
1714
1715           gold_assert(fileindex
1716                       == static_cast<int>(this->files_.back().size()));
1717           this->files_.back().push_back(std::make_pair(dirindexi, filename));
1718           fileindex++;
1719         }
1720     }
1721   lineptr++;
1722
1723   return lineptr;
1724 }
1725
1726 // Process a single opcode in the .debug.line structure.
1727
1728 template<int size, bool big_endian>
1729 bool
1730 Sized_dwarf_line_info<size, big_endian>::process_one_opcode(
1731     const unsigned char* start, struct LineStateMachine* lsm, size_t* len)
1732 {
1733   size_t oplen = 0;
1734   size_t templen;
1735   unsigned char opcode = *start;
1736   oplen++;
1737   start++;
1738
1739   // If the opcode is great than the opcode_base, it is a special
1740   // opcode. Most line programs consist mainly of special opcodes.
1741   if (opcode >= header_.opcode_base)
1742     {
1743       opcode -= header_.opcode_base;
1744       const int advance_address = ((opcode / header_.line_range)
1745                                    * header_.min_insn_length);
1746       lsm->address += advance_address;
1747
1748       const int advance_line = ((opcode % header_.line_range)
1749                                 + header_.line_base);
1750       lsm->line_num += advance_line;
1751       lsm->basic_block = true;
1752       *len = oplen;
1753       return true;
1754     }
1755
1756   // Otherwise, we have the regular opcodes
1757   switch (opcode)
1758     {
1759     case elfcpp::DW_LNS_copy:
1760       lsm->basic_block = false;
1761       *len = oplen;
1762       return true;
1763
1764     case elfcpp::DW_LNS_advance_pc:
1765       {
1766         const uint64_t advance_address
1767             = read_unsigned_LEB_128(start, &templen);
1768         oplen += templen;
1769         lsm->address += header_.min_insn_length * advance_address;
1770       }
1771       break;
1772
1773     case elfcpp::DW_LNS_advance_line:
1774       {
1775         const uint64_t advance_line = read_signed_LEB_128(start, &templen);
1776         oplen += templen;
1777         lsm->line_num += advance_line;
1778       }
1779       break;
1780
1781     case elfcpp::DW_LNS_set_file:
1782       {
1783         const uint64_t fileno = read_unsigned_LEB_128(start, &templen);
1784         oplen += templen;
1785         lsm->file_num = fileno;
1786       }
1787       break;
1788
1789     case elfcpp::DW_LNS_set_column:
1790       {
1791         const uint64_t colno = read_unsigned_LEB_128(start, &templen);
1792         oplen += templen;
1793         lsm->column_num = colno;
1794       }
1795       break;
1796
1797     case elfcpp::DW_LNS_negate_stmt:
1798       lsm->is_stmt = !lsm->is_stmt;
1799       break;
1800
1801     case elfcpp::DW_LNS_set_basic_block:
1802       lsm->basic_block = true;
1803       break;
1804
1805     case elfcpp::DW_LNS_fixed_advance_pc:
1806       {
1807         int advance_address;
1808         advance_address = elfcpp::Swap_unaligned<16, big_endian>::readval(start);
1809         oplen += 2;
1810         lsm->address += advance_address;
1811       }
1812       break;
1813
1814     case elfcpp::DW_LNS_const_add_pc:
1815       {
1816         const int advance_address = (header_.min_insn_length
1817                                      * ((255 - header_.opcode_base)
1818                                         / header_.line_range));
1819         lsm->address += advance_address;
1820       }
1821       break;
1822
1823     case elfcpp::DW_LNS_extended_op:
1824       {
1825         const uint64_t extended_op_len
1826             = read_unsigned_LEB_128(start, &templen);
1827         start += templen;
1828         oplen += templen + extended_op_len;
1829
1830         const unsigned char extended_op = *start;
1831         start++;
1832
1833         switch (extended_op)
1834           {
1835           case elfcpp::DW_LNE_end_sequence:
1836             // This means that the current byte is the one immediately
1837             // after a set of instructions.  Record the current line
1838             // for up to one less than the current address.
1839             lsm->line_num = -1;
1840             lsm->end_sequence = true;
1841             *len = oplen;
1842             return true;
1843
1844           case elfcpp::DW_LNE_set_address:
1845             {
1846               lsm->address =
1847                 elfcpp::Swap_unaligned<size, big_endian>::readval(start);
1848               typename Reloc_map::const_iterator it
1849                   = this->reloc_map_.find(start - this->buffer_);
1850               if (it != reloc_map_.end())
1851                 {
1852                   // If this is a SHT_RELA section, then ignore the
1853                   // section contents.  This assumes that this is a
1854                   // straight reloc which just uses the reloc addend.
1855                   // The reloc addend has already been included in the
1856                   // symbol value.
1857                   if (this->track_relocs_type_ == elfcpp::SHT_RELA)
1858                     lsm->address = 0;
1859                   // Add in the symbol value.
1860                   lsm->address += it->second.second;
1861                   lsm->shndx = it->second.first;
1862                 }
1863               else
1864                 {
1865                   // If we're a normal .o file, with relocs, every
1866                   // set_address should have an associated relocation.
1867                   if (this->input_is_relobj())
1868                     this->data_valid_ = false;
1869                 }
1870               break;
1871             }
1872           case elfcpp::DW_LNE_define_file:
1873             {
1874               const char* filename  = reinterpret_cast<const char*>(start);
1875               templen = strlen(filename) + 1;
1876               start += templen;
1877
1878               uint64_t dirindex = read_unsigned_LEB_128(start, &templen);
1879
1880               if (dirindex >= this->directories_.back().size())
1881                 dirindex = 0;
1882               int dirindexi = static_cast<int>(dirindex);
1883
1884               // This opcode takes two additional ULEB128 parameters
1885               // (mod_time and filelength), but we don't use those
1886               // values.  Because OPLEN already tells us how far to
1887               // skip to the next opcode, we don't need to read
1888               // them at all.
1889
1890               this->files_.back().push_back(std::make_pair(dirindexi,
1891                                                            filename));
1892             }
1893             break;
1894           }
1895       }
1896       break;
1897
1898     default:
1899       {
1900         // Ignore unknown opcode  silently
1901         for (int i = 0; i < header_.std_opcode_lengths[opcode]; i++)
1902           {
1903             size_t templen;
1904             read_unsigned_LEB_128(start, &templen);
1905             start += templen;
1906             oplen += templen;
1907           }
1908       }
1909       break;
1910   }
1911   *len = oplen;
1912   return false;
1913 }
1914
1915 // Read the debug information at LINEPTR and store it in the line
1916 // number map.
1917
1918 template<int size, bool big_endian>
1919 unsigned const char*
1920 Sized_dwarf_line_info<size, big_endian>::read_lines(unsigned const char* lineptr,
1921                                                     unsigned int shndx)
1922 {
1923   struct LineStateMachine lsm;
1924
1925   // LENGTHSTART is the place the length field is based on.  It is the
1926   // point in the header after the initial length field.
1927   const unsigned char* lengthstart = buffer_;
1928
1929   // In 64 bit dwarf, the initial length is 12 bytes, because of the
1930   // 0xffffffff at the start.
1931   if (header_.offset_size == 8)
1932     lengthstart += 12;
1933   else
1934     lengthstart += 4;
1935
1936   while (lineptr < lengthstart + header_.total_length)
1937     {
1938       ResetLineStateMachine(&lsm, header_.default_is_stmt);
1939       while (!lsm.end_sequence)
1940         {
1941           size_t oplength;
1942           bool add_line = this->process_one_opcode(lineptr, &lsm, &oplength);
1943           if (add_line
1944               && (shndx == -1U || lsm.shndx == -1U || shndx == lsm.shndx))
1945             {
1946               Offset_to_lineno_entry entry
1947                   = { static_cast<off_t>(lsm.address),
1948                       this->current_header_index_,
1949                       static_cast<unsigned int>(lsm.file_num),
1950                       true, lsm.line_num };
1951               std::vector<Offset_to_lineno_entry>&
1952                 map(this->line_number_map_[lsm.shndx]);
1953               // If we see two consecutive entries with the same
1954               // offset and a real line number, then mark the first
1955               // one as non-canonical.
1956               if (!map.empty()
1957                   && (map.back().offset == static_cast<off_t>(lsm.address))
1958                   && lsm.line_num != -1
1959                   && map.back().line_num != -1)
1960                 map.back().last_line_for_offset = false;
1961               map.push_back(entry);
1962             }
1963           lineptr += oplength;
1964         }
1965     }
1966
1967   return lengthstart + header_.total_length;
1968 }
1969
1970 // Read the relocations into a Reloc_map.
1971
1972 template<int size, bool big_endian>
1973 void
1974 Sized_dwarf_line_info<size, big_endian>::read_relocs()
1975 {
1976   if (this->symtab_buffer_ == NULL)
1977     return;
1978
1979   off_t value;
1980   off_t reloc_offset;
1981   while ((reloc_offset = this->reloc_mapper_->next_offset()) != -1)
1982     {
1983       const unsigned int shndx =
1984           this->reloc_mapper_->get_reloc_target(reloc_offset, &value);
1985
1986       // There is no reason to record non-ordinary section indexes, or
1987       // SHN_UNDEF, because they will never match the real section.
1988       if (shndx != 0)
1989         this->reloc_map_[reloc_offset] = std::make_pair(shndx, value);
1990
1991       this->reloc_mapper_->advance(reloc_offset + 1);
1992     }
1993 }
1994
1995 // Read the line number info.
1996
1997 template<int size, bool big_endian>
1998 void
1999 Sized_dwarf_line_info<size, big_endian>::read_line_mappings(unsigned int shndx)
2000 {
2001   gold_assert(this->data_valid_ == true);
2002
2003   this->read_relocs();
2004   while (this->buffer_ < this->buffer_end_)
2005     {
2006       const unsigned char* lineptr = this->buffer_;
2007       lineptr = this->read_header_prolog(lineptr);
2008       lineptr = this->read_header_tables(lineptr);
2009       lineptr = this->read_lines(lineptr, shndx);
2010       this->buffer_ = lineptr;
2011     }
2012
2013   // Sort the lines numbers, so addr2line can use binary search.
2014   for (typename Lineno_map::iterator it = line_number_map_.begin();
2015        it != line_number_map_.end();
2016        ++it)
2017     // Each vector needs to be sorted by offset.
2018     std::sort(it->second.begin(), it->second.end());
2019 }
2020
2021 // Some processing depends on whether the input is a .o file or not.
2022 // For instance, .o files have relocs, and have .debug_lines
2023 // information on a per section basis.  .so files, on the other hand,
2024 // lack relocs, and offsets are unique, so we can ignore the section
2025 // information.
2026
2027 template<int size, bool big_endian>
2028 bool
2029 Sized_dwarf_line_info<size, big_endian>::input_is_relobj()
2030 {
2031   // Only .o files have relocs and the symtab buffer that goes with them.
2032   return this->symtab_buffer_ != NULL;
2033 }
2034
2035 // Given an Offset_to_lineno_entry vector, and an offset, figure out
2036 // if the offset points into a function according to the vector (see
2037 // comments below for the algorithm).  If it does, return an iterator
2038 // into the vector that points to the line-number that contains that
2039 // offset.  If not, it returns vector::end().
2040
2041 static std::vector<Offset_to_lineno_entry>::const_iterator
2042 offset_to_iterator(const std::vector<Offset_to_lineno_entry>* offsets,
2043                    off_t offset)
2044 {
2045   const Offset_to_lineno_entry lookup_key = { offset, 0, 0, true, 0 };
2046
2047   // lower_bound() returns the smallest offset which is >= lookup_key.
2048   // If no offset in offsets is >= lookup_key, returns end().
2049   std::vector<Offset_to_lineno_entry>::const_iterator it
2050       = std::lower_bound(offsets->begin(), offsets->end(), lookup_key);
2051
2052   // This code is easiest to understand with a concrete example.
2053   // Here's a possible offsets array:
2054   // {{offset = 3211, header_num = 0, file_num = 1, last, line_num = 16},  // 0
2055   //  {offset = 3224, header_num = 0, file_num = 1, last, line_num = 20},  // 1
2056   //  {offset = 3226, header_num = 0, file_num = 1, last, line_num = 22},  // 2
2057   //  {offset = 3231, header_num = 0, file_num = 1, last, line_num = 25},  // 3
2058   //  {offset = 3232, header_num = 0, file_num = 1, last, line_num = -1},  // 4
2059   //  {offset = 3232, header_num = 0, file_num = 1, last, line_num = 65},  // 5
2060   //  {offset = 3235, header_num = 0, file_num = 1, last, line_num = 66},  // 6
2061   //  {offset = 3236, header_num = 0, file_num = 1, last, line_num = -1},  // 7
2062   //  {offset = 5764, header_num = 0, file_num = 1, last, line_num = 48},  // 8
2063   //  {offset = 5764, header_num = 0, file_num = 1,!last, line_num = 47},  // 9
2064   //  {offset = 5765, header_num = 0, file_num = 1, last, line_num = 49},  // 10
2065   //  {offset = 5767, header_num = 0, file_num = 1, last, line_num = 50},  // 11
2066   //  {offset = 5768, header_num = 0, file_num = 1, last, line_num = 51},  // 12
2067   //  {offset = 5773, header_num = 0, file_num = 1, last, line_num = -1},  // 13
2068   //  {offset = 5787, header_num = 1, file_num = 1, last, line_num = 19},  // 14
2069   //  {offset = 5790, header_num = 1, file_num = 1, last, line_num = 20},  // 15
2070   //  {offset = 5793, header_num = 1, file_num = 1, last, line_num = 67},  // 16
2071   //  {offset = 5793, header_num = 1, file_num = 1, last, line_num = -1},  // 17
2072   //  {offset = 5793, header_num = 1, file_num = 1,!last, line_num = 66},  // 18
2073   //  {offset = 5795, header_num = 1, file_num = 1, last, line_num = 68},  // 19
2074   //  {offset = 5798, header_num = 1, file_num = 1, last, line_num = -1},  // 20
2075   // The entries with line_num == -1 mark the end of a function: the
2076   // associated offset is one past the last instruction in the
2077   // function.  This can correspond to the beginning of the next
2078   // function (as is true for offset 3232); alternately, there can be
2079   // a gap between the end of one function and the start of the next
2080   // (as is true for some others, most obviously from 3236->5764).
2081   //
2082   // Case 1: lookup_key has offset == 10.  lower_bound returns
2083   //         offsets[0].  Since it's not an exact match and we're
2084   //         at the beginning of offsets, we return end() (invalid).
2085   // Case 2: lookup_key has offset 10000.  lower_bound returns
2086   //         offset[21] (end()).  We return end() (invalid).
2087   // Case 3: lookup_key has offset == 3211.  lower_bound matches
2088   //         offsets[0] exactly, and that's the entry we return.
2089   // Case 4: lookup_key has offset == 3232.  lower_bound returns
2090   //         offsets[4].  That's an exact match, but indicates
2091   //         end-of-function.  We check if offsets[5] is also an
2092   //         exact match but not end-of-function.  It is, so we
2093   //         return offsets[5].
2094   // Case 5: lookup_key has offset == 3214.  lower_bound returns
2095   //         offsets[1].  Since it's not an exact match, we back
2096   //         up to the offset that's < lookup_key, offsets[0].
2097   //         We note offsets[0] is a valid entry (not end-of-function),
2098   //         so that's the entry we return.
2099   // Case 6: lookup_key has offset == 4000.  lower_bound returns
2100   //         offsets[8].  Since it's not an exact match, we back
2101   //         up to offsets[7].  Since offsets[7] indicates
2102   //         end-of-function, we know lookup_key is between
2103   //         functions, so we return end() (not a valid offset).
2104   // Case 7: lookup_key has offset == 5794.  lower_bound returns
2105   //         offsets[19].  Since it's not an exact match, we back
2106   //         up to offsets[16].  Note we back up to the *first*
2107   //         entry with offset 5793, not just offsets[19-1].
2108   //         We note offsets[16] is a valid entry, so we return it.
2109   //         If offsets[16] had had line_num == -1, we would have
2110   //         checked offsets[17].  The reason for this is that
2111   //         16 and 17 can be in an arbitrary order, since we sort
2112   //         only by offset and last_line_for_offset.  (Note it
2113   //         doesn't help to use line_number as a tertiary sort key,
2114   //         since sometimes we want the -1 to be first and sometimes
2115   //         we want it to be last.)
2116
2117   // This deals with cases (1) and (2).
2118   if ((it == offsets->begin() && offset < it->offset)
2119       || it == offsets->end())
2120     return offsets->end();
2121
2122   // This deals with cases (3) and (4).
2123   if (offset == it->offset)
2124     {
2125       while (it != offsets->end()
2126              && it->offset == offset
2127              && it->line_num == -1)
2128         ++it;
2129       if (it == offsets->end() || it->offset != offset)
2130         return offsets->end();
2131       else
2132         return it;
2133     }
2134
2135   // This handles the first part of case (7) -- we back up to the
2136   // *first* entry that has the offset that's behind us.
2137   gold_assert(it != offsets->begin());
2138   std::vector<Offset_to_lineno_entry>::const_iterator range_end = it;
2139   --it;
2140   const off_t range_value = it->offset;
2141   while (it != offsets->begin() && (it-1)->offset == range_value)
2142     --it;
2143
2144   // This handles cases (5), (6), and (7): if any entry in the
2145   // equal_range [it, range_end) has a line_num != -1, it's a valid
2146   // match.  If not, we're not in a function.  The line number we saw
2147   // last for an offset will be sorted first, so it'll get returned if
2148   // it's present.
2149   for (; it != range_end; ++it)
2150     if (it->line_num != -1)
2151       return it;
2152   return offsets->end();
2153 }
2154
2155 // Returns the canonical filename:lineno for the address passed in.
2156 // If other_lines is not NULL, appends the non-canonical lines
2157 // assigned to the same address.
2158
2159 template<int size, bool big_endian>
2160 std::string
2161 Sized_dwarf_line_info<size, big_endian>::do_addr2line(
2162     unsigned int shndx,
2163     off_t offset,
2164     std::vector<std::string>* other_lines)
2165 {
2166   if (this->data_valid_ == false)
2167     return "";
2168
2169   const std::vector<Offset_to_lineno_entry>* offsets;
2170   // If we do not have reloc information, then our input is a .so or
2171   // some similar data structure where all the information is held in
2172   // the offset.  In that case, we ignore the input shndx.
2173   if (this->input_is_relobj())
2174     offsets = &this->line_number_map_[shndx];
2175   else
2176     offsets = &this->line_number_map_[-1U];
2177   if (offsets->empty())
2178     return "";
2179
2180   typename std::vector<Offset_to_lineno_entry>::const_iterator it
2181       = offset_to_iterator(offsets, offset);
2182   if (it == offsets->end())
2183     return "";
2184
2185   std::string result = this->format_file_lineno(*it);
2186   if (other_lines != NULL)
2187     for (++it; it != offsets->end() && it->offset == offset; ++it)
2188       {
2189         if (it->line_num == -1)
2190           continue;  // The end of a previous function.
2191         other_lines->push_back(this->format_file_lineno(*it));
2192       }
2193   return result;
2194 }
2195
2196 // Convert the file_num + line_num into a string.
2197
2198 template<int size, bool big_endian>
2199 std::string
2200 Sized_dwarf_line_info<size, big_endian>::format_file_lineno(
2201     const Offset_to_lineno_entry& loc) const
2202 {
2203   std::string ret;
2204
2205   gold_assert(loc.header_num < static_cast<int>(this->files_.size()));
2206   gold_assert(loc.file_num
2207               < static_cast<unsigned int>(this->files_[loc.header_num].size()));
2208   const std::pair<int, std::string>& filename_pair
2209       = this->files_[loc.header_num][loc.file_num];
2210   const std::string& filename = filename_pair.second;
2211
2212   gold_assert(loc.header_num < static_cast<int>(this->directories_.size()));
2213   gold_assert(filename_pair.first
2214               < static_cast<int>(this->directories_[loc.header_num].size()));
2215   const std::string& dirname
2216       = this->directories_[loc.header_num][filename_pair.first];
2217
2218   if (!dirname.empty())
2219     {
2220       ret += dirname;
2221       ret += "/";
2222     }
2223   ret += filename;
2224   if (ret.empty())
2225     ret = "(unknown)";
2226
2227   char buffer[64];   // enough to hold a line number
2228   snprintf(buffer, sizeof(buffer), "%d", loc.line_num);
2229   ret += ":";
2230   ret += buffer;
2231
2232   return ret;
2233 }
2234
2235 // Dwarf_line_info routines.
2236
2237 static unsigned int next_generation_count = 0;
2238
2239 struct Addr2line_cache_entry
2240 {
2241   Object* object;
2242   unsigned int shndx;
2243   Dwarf_line_info* dwarf_line_info;
2244   unsigned int generation_count;
2245   unsigned int access_count;
2246
2247   Addr2line_cache_entry(Object* o, unsigned int s, Dwarf_line_info* d)
2248       : object(o), shndx(s), dwarf_line_info(d),
2249         generation_count(next_generation_count), access_count(0)
2250   {
2251     if (next_generation_count < (1U << 31))
2252       ++next_generation_count;
2253   }
2254 };
2255 // We expect this cache to be small, so don't bother with a hashtable
2256 // or priority queue or anything: just use a simple vector.
2257 static std::vector<Addr2line_cache_entry> addr2line_cache;
2258
2259 std::string
2260 Dwarf_line_info::one_addr2line(Object* object,
2261                                unsigned int shndx, off_t offset,
2262                                size_t cache_size,
2263                                std::vector<std::string>* other_lines)
2264 {
2265   Dwarf_line_info* lineinfo = NULL;
2266   std::vector<Addr2line_cache_entry>::iterator it;
2267
2268   // First, check the cache.  If we hit, update the counts.
2269   for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it)
2270     {
2271       if (it->object == object && it->shndx == shndx)
2272         {
2273           lineinfo = it->dwarf_line_info;
2274           it->generation_count = next_generation_count;
2275           // We cap generation_count at 2^31 -1 to avoid overflow.
2276           if (next_generation_count < (1U << 31))
2277             ++next_generation_count;
2278           // We cap access_count at 31 so 2^access_count doesn't overflow
2279           if (it->access_count < 31)
2280             ++it->access_count;
2281           break;
2282         }
2283     }
2284
2285   // If we don't hit the cache, create a new object and insert into the
2286   // cache.
2287   if (lineinfo == NULL)
2288   {
2289     switch (parameters->size_and_endianness())
2290       {
2291 #ifdef HAVE_TARGET_32_LITTLE
2292         case Parameters::TARGET_32_LITTLE:
2293           lineinfo = new Sized_dwarf_line_info<32, false>(object, shndx); break;
2294 #endif
2295 #ifdef HAVE_TARGET_32_BIG
2296         case Parameters::TARGET_32_BIG:
2297           lineinfo = new Sized_dwarf_line_info<32, true>(object, shndx); break;
2298 #endif
2299 #ifdef HAVE_TARGET_64_LITTLE
2300         case Parameters::TARGET_64_LITTLE:
2301           lineinfo = new Sized_dwarf_line_info<64, false>(object, shndx); break;
2302 #endif
2303 #ifdef HAVE_TARGET_64_BIG
2304         case Parameters::TARGET_64_BIG:
2305           lineinfo = new Sized_dwarf_line_info<64, true>(object, shndx); break;
2306 #endif
2307         default:
2308           gold_unreachable();
2309       }
2310     addr2line_cache.push_back(Addr2line_cache_entry(object, shndx, lineinfo));
2311   }
2312
2313   // Now that we have our object, figure out the answer
2314   std::string retval = lineinfo->addr2line(shndx, offset, other_lines);
2315
2316   // Finally, if our cache has grown too big, delete old objects.  We
2317   // assume the common (probably only) case is deleting only one object.
2318   // We use a pretty simple scheme to evict: function of LRU and MFU.
2319   while (addr2line_cache.size() > cache_size)
2320     {
2321       unsigned int lowest_score = ~0U;
2322       std::vector<Addr2line_cache_entry>::iterator lowest
2323           = addr2line_cache.end();
2324       for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it)
2325         {
2326           const unsigned int score = (it->generation_count
2327                                       + (1U << it->access_count));
2328           if (score < lowest_score)
2329             {
2330               lowest_score = score;
2331               lowest = it;
2332             }
2333         }
2334       if (lowest != addr2line_cache.end())
2335         {
2336           delete lowest->dwarf_line_info;
2337           addr2line_cache.erase(lowest);
2338         }
2339     }
2340
2341   return retval;
2342 }
2343
2344 void
2345 Dwarf_line_info::clear_addr2line_cache()
2346 {
2347   for (std::vector<Addr2line_cache_entry>::iterator it = addr2line_cache.begin();
2348        it != addr2line_cache.end();
2349        ++it)
2350     delete it->dwarf_line_info;
2351   addr2line_cache.clear();
2352 }
2353
2354 #ifdef HAVE_TARGET_32_LITTLE
2355 template
2356 class Sized_dwarf_line_info<32, false>;
2357 #endif
2358
2359 #ifdef HAVE_TARGET_32_BIG
2360 template
2361 class Sized_dwarf_line_info<32, true>;
2362 #endif
2363
2364 #ifdef HAVE_TARGET_64_LITTLE
2365 template
2366 class Sized_dwarf_line_info<64, false>;
2367 #endif
2368
2369 #ifdef HAVE_TARGET_64_BIG
2370 template
2371 class Sized_dwarf_line_info<64, true>;
2372 #endif
2373
2374 } // End namespace gold.