contrib/binutils-2.24/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                                   type_offset, signature, &root_die);
1338           else
1339             this->visit_compilation_unit(section_offset + this->cu_offset_,
1340                                          cu_end - cu_start, &root_die);
1341         }
1342
1343       // Advance to the next CU.
1344       pinfo = cu_end;
1345     }
1346
1347   if (buffer_is_new)
1348     {
1349       delete[] this->buffer_;
1350       this->buffer_ = NULL;
1351     }
1352 }
1353
1354 // Read the DWARF string table.
1355
1356 bool
1357 Dwarf_info_reader::do_read_string_table(unsigned int string_shndx)
1358 {
1359   Relobj* object = this->object_;
1360
1361   // If we don't have relocations, string_shndx will be 0, and
1362   // we'll have to hunt for the .debug_str section.
1363   if (string_shndx == 0)
1364     {
1365       for (unsigned int i = 1; i < this->object_->shnum(); ++i)
1366         {
1367           std::string name = object->section_name(i);
1368           if (name == ".debug_str")
1369             {
1370               string_shndx = i;
1371               this->string_output_section_offset_ =
1372                   object->output_section_offset(i);
1373               break;
1374             }
1375         }
1376       if (string_shndx == 0)
1377         return false;
1378     }
1379
1380   if (this->owns_string_buffer_ && this->string_buffer_ != NULL)
1381     {
1382       delete[] this->string_buffer_;
1383       this->owns_string_buffer_ = false;
1384     }
1385
1386   // Get the secton contents and decompress if necessary.
1387   section_size_type buffer_size;
1388   const unsigned char* buffer =
1389       object->decompressed_section_contents(string_shndx,
1390                                             &buffer_size,
1391                                             &this->owns_string_buffer_);
1392   this->string_buffer_ = reinterpret_cast<const char*>(buffer);
1393   this->string_buffer_end_ = this->string_buffer_ + buffer_size;
1394   this->string_shndx_ = string_shndx;
1395   return true;
1396 }
1397
1398 // Read a possibly unaligned integer of SIZE.
1399 template <int valsize>
1400 inline typename elfcpp::Valtype_base<valsize>::Valtype
1401 Dwarf_info_reader::read_from_pointer(const unsigned char* source)
1402 {
1403   typename elfcpp::Valtype_base<valsize>::Valtype return_value;
1404   if (this->object_->is_big_endian())
1405     return_value = elfcpp::Swap_unaligned<valsize, true>::readval(source);
1406   else
1407     return_value = elfcpp::Swap_unaligned<valsize, false>::readval(source);
1408   return return_value;
1409 }
1410
1411 // Read a possibly unaligned integer of SIZE.  Update SOURCE after read.
1412 template <int valsize>
1413 inline typename elfcpp::Valtype_base<valsize>::Valtype
1414 Dwarf_info_reader::read_from_pointer(const unsigned char** source)
1415 {
1416   typename elfcpp::Valtype_base<valsize>::Valtype return_value;
1417   if (this->object_->is_big_endian())
1418     return_value = elfcpp::Swap_unaligned<valsize, true>::readval(*source);
1419   else
1420     return_value = elfcpp::Swap_unaligned<valsize, false>::readval(*source);
1421   *source += valsize / 8;
1422   return return_value;
1423 }
1424
1425 // Look for a relocation at offset ATTR_OFF in the dwarf info,
1426 // and return the section index and offset of the target.
1427
1428 unsigned int
1429 Dwarf_info_reader::lookup_reloc(off_t attr_off, off_t* target_off)
1430 {
1431   off_t value;
1432   attr_off += this->cu_offset_;
1433   unsigned int shndx = this->reloc_mapper_->get_reloc_target(attr_off, &value);
1434   if (shndx == 0)
1435     return 0;
1436   if (this->reloc_type_ == elfcpp::SHT_REL)
1437     *target_off += value;
1438   else
1439     *target_off = value;
1440   return shndx;
1441 }
1442
1443 // Return a string from the DWARF string table.
1444
1445 const char*
1446 Dwarf_info_reader::get_string(off_t str_off, unsigned int string_shndx)
1447 {
1448   if (!this->read_string_table(string_shndx))
1449     return NULL;
1450
1451   // Correct the offset.  For incremental update links, we have a
1452   // relocated offset that is relative to the output section, but
1453   // here we need an offset relative to the input section.
1454   str_off -= this->string_output_section_offset_;
1455
1456   const char* p = this->string_buffer_ + str_off;
1457
1458   if (p < this->string_buffer_ || p >= this->string_buffer_end_)
1459     return NULL;
1460
1461   return p;
1462 }
1463
1464 // The following are default, do-nothing, implementations of the
1465 // hook methods normally provided by a derived class.  We provide
1466 // default implementations rather than no implementation so that
1467 // a derived class needs to implement only the hooks that it needs
1468 // to use.
1469
1470 // Process a compilation unit and parse its child DIE.
1471
1472 void
1473 Dwarf_info_reader::visit_compilation_unit(off_t, off_t, Dwarf_die*)
1474 {
1475 }
1476
1477 // Process a type unit and parse its child DIE.
1478
1479 void
1480 Dwarf_info_reader::visit_type_unit(off_t, off_t, uint64_t, Dwarf_die*)
1481 {
1482 }
1483
1484 // Print a warning about a corrupt debug section.
1485
1486 void
1487 Dwarf_info_reader::warn_corrupt_debug_section() const
1488 {
1489   gold_warning(_("%s: corrupt debug info in %s"),
1490                this->object_->name().c_str(),
1491                this->object_->section_name(this->shndx_).c_str());
1492 }
1493
1494 // class Sized_dwarf_line_info
1495
1496 struct LineStateMachine
1497 {
1498   int file_num;
1499   uint64_t address;
1500   int line_num;
1501   int column_num;
1502   unsigned int shndx;    // the section address refers to
1503   bool is_stmt;          // stmt means statement.
1504   bool basic_block;
1505   bool end_sequence;
1506 };
1507
1508 static void
1509 ResetLineStateMachine(struct LineStateMachine* lsm, bool default_is_stmt)
1510 {
1511   lsm->file_num = 1;
1512   lsm->address = 0;
1513   lsm->line_num = 1;
1514   lsm->column_num = 0;
1515   lsm->shndx = -1U;
1516   lsm->is_stmt = default_is_stmt;
1517   lsm->basic_block = false;
1518   lsm->end_sequence = false;
1519 }
1520
1521 template<int size, bool big_endian>
1522 Sized_dwarf_line_info<size, big_endian>::Sized_dwarf_line_info(
1523     Object* object,
1524     unsigned int read_shndx)
1525   : data_valid_(false), buffer_(NULL), buffer_start_(NULL),
1526     reloc_mapper_(NULL), symtab_buffer_(NULL), directories_(), files_(),
1527     current_header_index_(-1)
1528 {
1529   unsigned int debug_shndx;
1530
1531   for (debug_shndx = 1; debug_shndx < object->shnum(); ++debug_shndx)
1532     {
1533       // FIXME: do this more efficiently: section_name() isn't super-fast
1534       std::string name = object->section_name(debug_shndx);
1535       if (name == ".debug_line" || name == ".zdebug_line")
1536         {
1537           section_size_type buffer_size;
1538           bool is_new = false;
1539           this->buffer_ = object->decompressed_section_contents(debug_shndx,
1540                                                                 &buffer_size,
1541                                                                 &is_new);
1542           if (is_new)
1543             this->buffer_start_ = this->buffer_;
1544           this->buffer_end_ = this->buffer_ + buffer_size;
1545           break;
1546         }
1547     }
1548   if (this->buffer_ == NULL)
1549     return;
1550
1551   // Find the relocation section for ".debug_line".
1552   // We expect these for relobjs (.o's) but not dynobjs (.so's).
1553   unsigned int reloc_shndx = 0;
1554   for (unsigned int i = 0; i < object->shnum(); ++i)
1555     {
1556       unsigned int reloc_sh_type = object->section_type(i);
1557       if ((reloc_sh_type == elfcpp::SHT_REL
1558            || reloc_sh_type == elfcpp::SHT_RELA)
1559           && object->section_info(i) == debug_shndx)
1560         {
1561           reloc_shndx = i;
1562           this->track_relocs_type_ = reloc_sh_type;
1563           break;
1564         }
1565     }
1566
1567   // Finally, we need the symtab section to interpret the relocs.
1568   if (reloc_shndx != 0)
1569     {
1570       unsigned int symtab_shndx;
1571       for (symtab_shndx = 0; symtab_shndx < object->shnum(); ++symtab_shndx)
1572         if (object->section_type(symtab_shndx) == elfcpp::SHT_SYMTAB)
1573           {
1574             this->symtab_buffer_ = object->section_contents(
1575                 symtab_shndx, &this->symtab_buffer_size_, false);
1576             break;
1577           }
1578       if (this->symtab_buffer_ == NULL)
1579         return;
1580     }
1581
1582   this->reloc_mapper_ =
1583       new Sized_elf_reloc_mapper<size, big_endian>(object,
1584                                                    this->symtab_buffer_,
1585                                                    this->symtab_buffer_size_);
1586   if (!this->reloc_mapper_->initialize(reloc_shndx, this->track_relocs_type_))
1587     return;
1588
1589   // Now that we have successfully read all the data, parse the debug
1590   // info.
1591   this->data_valid_ = true;
1592   this->read_line_mappings(read_shndx);
1593 }
1594
1595 // Read the DWARF header.
1596
1597 template<int size, bool big_endian>
1598 const unsigned char*
1599 Sized_dwarf_line_info<size, big_endian>::read_header_prolog(
1600     const unsigned char* lineptr)
1601 {
1602   uint32_t initial_length = elfcpp::Swap_unaligned<32, big_endian>::readval(lineptr);
1603   lineptr += 4;
1604
1605   // In DWARF2/3, if the initial length is all 1 bits, then the offset
1606   // size is 8 and we need to read the next 8 bytes for the real length.
1607   if (initial_length == 0xffffffff)
1608     {
1609       header_.offset_size = 8;
1610       initial_length = elfcpp::Swap_unaligned<64, big_endian>::readval(lineptr);
1611       lineptr += 8;
1612     }
1613   else
1614     header_.offset_size = 4;
1615
1616   header_.total_length = initial_length;
1617
1618   gold_assert(lineptr + header_.total_length <= buffer_end_);
1619
1620   header_.version = elfcpp::Swap_unaligned<16, big_endian>::readval(lineptr);
1621   lineptr += 2;
1622
1623   if (header_.offset_size == 4)
1624     header_.prologue_length = elfcpp::Swap_unaligned<32, big_endian>::readval(lineptr);
1625   else
1626     header_.prologue_length = elfcpp::Swap_unaligned<64, big_endian>::readval(lineptr);
1627   lineptr += header_.offset_size;
1628
1629   header_.min_insn_length = *lineptr;
1630   lineptr += 1;
1631
1632   header_.default_is_stmt = *lineptr;
1633   lineptr += 1;
1634
1635   header_.line_base = *reinterpret_cast<const signed char*>(lineptr);
1636   lineptr += 1;
1637
1638   header_.line_range = *lineptr;
1639   lineptr += 1;
1640
1641   header_.opcode_base = *lineptr;
1642   lineptr += 1;
1643
1644   header_.std_opcode_lengths.resize(header_.opcode_base + 1);
1645   header_.std_opcode_lengths[0] = 0;
1646   for (int i = 1; i < header_.opcode_base; i++)
1647     {
1648       header_.std_opcode_lengths[i] = *lineptr;
1649       lineptr += 1;
1650     }
1651
1652   return lineptr;
1653 }
1654
1655 // The header for a debug_line section is mildly complicated, because
1656 // the line info is very tightly encoded.
1657
1658 template<int size, bool big_endian>
1659 const unsigned char*
1660 Sized_dwarf_line_info<size, big_endian>::read_header_tables(
1661     const unsigned char* lineptr)
1662 {
1663   ++this->current_header_index_;
1664
1665   // Create a new directories_ entry and a new files_ entry for our new
1666   // header.  We initialize each with a single empty element, because
1667   // dwarf indexes directory and filenames starting at 1.
1668   gold_assert(static_cast<int>(this->directories_.size())
1669               == this->current_header_index_);
1670   gold_assert(static_cast<int>(this->files_.size())
1671               == this->current_header_index_);
1672   this->directories_.push_back(std::vector<std::string>(1));
1673   this->files_.push_back(std::vector<std::pair<int, std::string> >(1));
1674
1675   // It is legal for the directory entry table to be empty.
1676   if (*lineptr)
1677     {
1678       int dirindex = 1;
1679       while (*lineptr)
1680         {
1681           const char* dirname = reinterpret_cast<const char*>(lineptr);
1682           gold_assert(dirindex
1683                       == static_cast<int>(this->directories_.back().size()));
1684           this->directories_.back().push_back(dirname);
1685           lineptr += this->directories_.back().back().size() + 1;
1686           dirindex++;
1687         }
1688     }
1689   lineptr++;
1690
1691   // It is also legal for the file entry table to be empty.
1692   if (*lineptr)
1693     {
1694       int fileindex = 1;
1695       size_t len;
1696       while (*lineptr)
1697         {
1698           const char* filename = reinterpret_cast<const char*>(lineptr);
1699           lineptr += strlen(filename) + 1;
1700
1701           uint64_t dirindex = read_unsigned_LEB_128(lineptr, &len);
1702           lineptr += len;
1703
1704           if (dirindex >= this->directories_.back().size())
1705             dirindex = 0;
1706           int dirindexi = static_cast<int>(dirindex);
1707
1708           read_unsigned_LEB_128(lineptr, &len);   // mod_time
1709           lineptr += len;
1710
1711           read_unsigned_LEB_128(lineptr, &len);   // filelength
1712           lineptr += len;
1713
1714           gold_assert(fileindex
1715                       == static_cast<int>(this->files_.back().size()));
1716           this->files_.back().push_back(std::make_pair(dirindexi, filename));
1717           fileindex++;
1718         }
1719     }
1720   lineptr++;
1721
1722   return lineptr;
1723 }
1724
1725 // Process a single opcode in the .debug.line structure.
1726
1727 template<int size, bool big_endian>
1728 bool
1729 Sized_dwarf_line_info<size, big_endian>::process_one_opcode(
1730     const unsigned char* start, struct LineStateMachine* lsm, size_t* len)
1731 {
1732   size_t oplen = 0;
1733   size_t templen;
1734   unsigned char opcode = *start;
1735   oplen++;
1736   start++;
1737
1738   // If the opcode is great than the opcode_base, it is a special
1739   // opcode. Most line programs consist mainly of special opcodes.
1740   if (opcode >= header_.opcode_base)
1741     {
1742       opcode -= header_.opcode_base;
1743       const int advance_address = ((opcode / header_.line_range)
1744                                    * header_.min_insn_length);
1745       lsm->address += advance_address;
1746
1747       const int advance_line = ((opcode % header_.line_range)
1748                                 + header_.line_base);
1749       lsm->line_num += advance_line;
1750       lsm->basic_block = true;
1751       *len = oplen;
1752       return true;
1753     }
1754
1755   // Otherwise, we have the regular opcodes
1756   switch (opcode)
1757     {
1758     case elfcpp::DW_LNS_copy:
1759       lsm->basic_block = false;
1760       *len = oplen;
1761       return true;
1762
1763     case elfcpp::DW_LNS_advance_pc:
1764       {
1765         const uint64_t advance_address
1766             = read_unsigned_LEB_128(start, &templen);
1767         oplen += templen;
1768         lsm->address += header_.min_insn_length * advance_address;
1769       }
1770       break;
1771
1772     case elfcpp::DW_LNS_advance_line:
1773       {
1774         const uint64_t advance_line = read_signed_LEB_128(start, &templen);
1775         oplen += templen;
1776         lsm->line_num += advance_line;
1777       }
1778       break;
1779
1780     case elfcpp::DW_LNS_set_file:
1781       {
1782         const uint64_t fileno = read_unsigned_LEB_128(start, &templen);
1783         oplen += templen;
1784         lsm->file_num = fileno;
1785       }
1786       break;
1787
1788     case elfcpp::DW_LNS_set_column:
1789       {
1790         const uint64_t colno = read_unsigned_LEB_128(start, &templen);
1791         oplen += templen;
1792         lsm->column_num = colno;
1793       }
1794       break;
1795
1796     case elfcpp::DW_LNS_negate_stmt:
1797       lsm->is_stmt = !lsm->is_stmt;
1798       break;
1799
1800     case elfcpp::DW_LNS_set_basic_block:
1801       lsm->basic_block = true;
1802       break;
1803
1804     case elfcpp::DW_LNS_fixed_advance_pc:
1805       {
1806         int advance_address;
1807         advance_address = elfcpp::Swap_unaligned<16, big_endian>::readval(start);
1808         oplen += 2;
1809         lsm->address += advance_address;
1810       }
1811       break;
1812
1813     case elfcpp::DW_LNS_const_add_pc:
1814       {
1815         const int advance_address = (header_.min_insn_length
1816                                      * ((255 - header_.opcode_base)
1817                                         / header_.line_range));
1818         lsm->address += advance_address;
1819       }
1820       break;
1821
1822     case elfcpp::DW_LNS_extended_op:
1823       {
1824         const uint64_t extended_op_len
1825             = read_unsigned_LEB_128(start, &templen);
1826         start += templen;
1827         oplen += templen + extended_op_len;
1828
1829         const unsigned char extended_op = *start;
1830         start++;
1831
1832         switch (extended_op)
1833           {
1834           case elfcpp::DW_LNE_end_sequence:
1835             // This means that the current byte is the one immediately
1836             // after a set of instructions.  Record the current line
1837             // for up to one less than the current address.
1838             lsm->line_num = -1;
1839             lsm->end_sequence = true;
1840             *len = oplen;
1841             return true;
1842
1843           case elfcpp::DW_LNE_set_address:
1844             {
1845               lsm->address =
1846                 elfcpp::Swap_unaligned<size, big_endian>::readval(start);
1847               typename Reloc_map::const_iterator it
1848                   = this->reloc_map_.find(start - this->buffer_);
1849               if (it != reloc_map_.end())
1850                 {
1851                   // If this is a SHT_RELA section, then ignore the
1852                   // section contents.  This assumes that this is a
1853                   // straight reloc which just uses the reloc addend.
1854                   // The reloc addend has already been included in the
1855                   // symbol value.
1856                   if (this->track_relocs_type_ == elfcpp::SHT_RELA)
1857                     lsm->address = 0;
1858                   // Add in the symbol value.
1859                   lsm->address += it->second.second;
1860                   lsm->shndx = it->second.first;
1861                 }
1862               else
1863                 {
1864                   // If we're a normal .o file, with relocs, every
1865                   // set_address should have an associated relocation.
1866                   if (this->input_is_relobj())
1867                     this->data_valid_ = false;
1868                 }
1869               break;
1870             }
1871           case elfcpp::DW_LNE_define_file:
1872             {
1873               const char* filename  = reinterpret_cast<const char*>(start);
1874               templen = strlen(filename) + 1;
1875               start += templen;
1876
1877               uint64_t dirindex = read_unsigned_LEB_128(start, &templen);
1878
1879               if (dirindex >= this->directories_.back().size())
1880                 dirindex = 0;
1881               int dirindexi = static_cast<int>(dirindex);
1882
1883               // This opcode takes two additional ULEB128 parameters
1884               // (mod_time and filelength), but we don't use those
1885               // values.  Because OPLEN already tells us how far to
1886               // skip to the next opcode, we don't need to read
1887               // them at all.
1888
1889               this->files_.back().push_back(std::make_pair(dirindexi,
1890                                                            filename));
1891             }
1892             break;
1893           }
1894       }
1895       break;
1896
1897     default:
1898       {
1899         // Ignore unknown opcode  silently
1900         for (int i = 0; i < header_.std_opcode_lengths[opcode]; i++)
1901           {
1902             size_t templen;
1903             read_unsigned_LEB_128(start, &templen);
1904             start += templen;
1905             oplen += templen;
1906           }
1907       }
1908       break;
1909   }
1910   *len = oplen;
1911   return false;
1912 }
1913
1914 // Read the debug information at LINEPTR and store it in the line
1915 // number map.
1916
1917 template<int size, bool big_endian>
1918 unsigned const char*
1919 Sized_dwarf_line_info<size, big_endian>::read_lines(unsigned const char* lineptr,
1920                                                     unsigned int shndx)
1921 {
1922   struct LineStateMachine lsm;
1923
1924   // LENGTHSTART is the place the length field is based on.  It is the
1925   // point in the header after the initial length field.
1926   const unsigned char* lengthstart = buffer_;
1927
1928   // In 64 bit dwarf, the initial length is 12 bytes, because of the
1929   // 0xffffffff at the start.
1930   if (header_.offset_size == 8)
1931     lengthstart += 12;
1932   else
1933     lengthstart += 4;
1934
1935   while (lineptr < lengthstart + header_.total_length)
1936     {
1937       ResetLineStateMachine(&lsm, header_.default_is_stmt);
1938       while (!lsm.end_sequence)
1939         {
1940           size_t oplength;
1941           bool add_line = this->process_one_opcode(lineptr, &lsm, &oplength);
1942           if (add_line
1943               && (shndx == -1U || lsm.shndx == -1U || shndx == lsm.shndx))
1944             {
1945               Offset_to_lineno_entry entry
1946                   = { static_cast<off_t>(lsm.address),
1947                       this->current_header_index_,
1948                       static_cast<unsigned int>(lsm.file_num),
1949                       true, lsm.line_num };
1950               std::vector<Offset_to_lineno_entry>&
1951                 map(this->line_number_map_[lsm.shndx]);
1952               // If we see two consecutive entries with the same
1953               // offset and a real line number, then mark the first
1954               // one as non-canonical.
1955               if (!map.empty()
1956                   && (map.back().offset == static_cast<off_t>(lsm.address))
1957                   && lsm.line_num != -1
1958                   && map.back().line_num != -1)
1959                 map.back().last_line_for_offset = false;
1960               map.push_back(entry);
1961             }
1962           lineptr += oplength;
1963         }
1964     }
1965
1966   return lengthstart + header_.total_length;
1967 }
1968
1969 // Read the relocations into a Reloc_map.
1970
1971 template<int size, bool big_endian>
1972 void
1973 Sized_dwarf_line_info<size, big_endian>::read_relocs()
1974 {
1975   if (this->symtab_buffer_ == NULL)
1976     return;
1977
1978   off_t value;
1979   off_t reloc_offset;
1980   while ((reloc_offset = this->reloc_mapper_->next_offset()) != -1)
1981     {
1982       const unsigned int shndx =
1983           this->reloc_mapper_->get_reloc_target(reloc_offset, &value);
1984
1985       // There is no reason to record non-ordinary section indexes, or
1986       // SHN_UNDEF, because they will never match the real section.
1987       if (shndx != 0)
1988         this->reloc_map_[reloc_offset] = std::make_pair(shndx, value);
1989
1990       this->reloc_mapper_->advance(reloc_offset + 1);
1991     }
1992 }
1993
1994 // Read the line number info.
1995
1996 template<int size, bool big_endian>
1997 void
1998 Sized_dwarf_line_info<size, big_endian>::read_line_mappings(unsigned int shndx)
1999 {
2000   gold_assert(this->data_valid_ == true);
2001
2002   this->read_relocs();
2003   while (this->buffer_ < this->buffer_end_)
2004     {
2005       const unsigned char* lineptr = this->buffer_;
2006       lineptr = this->read_header_prolog(lineptr);
2007       lineptr = this->read_header_tables(lineptr);
2008       lineptr = this->read_lines(lineptr, shndx);
2009       this->buffer_ = lineptr;
2010     }
2011
2012   // Sort the lines numbers, so addr2line can use binary search.
2013   for (typename Lineno_map::iterator it = line_number_map_.begin();
2014        it != line_number_map_.end();
2015        ++it)
2016     // Each vector needs to be sorted by offset.
2017     std::sort(it->second.begin(), it->second.end());
2018 }
2019
2020 // Some processing depends on whether the input is a .o file or not.
2021 // For instance, .o files have relocs, and have .debug_lines
2022 // information on a per section basis.  .so files, on the other hand,
2023 // lack relocs, and offsets are unique, so we can ignore the section
2024 // information.
2025
2026 template<int size, bool big_endian>
2027 bool
2028 Sized_dwarf_line_info<size, big_endian>::input_is_relobj()
2029 {
2030   // Only .o files have relocs and the symtab buffer that goes with them.
2031   return this->symtab_buffer_ != NULL;
2032 }
2033
2034 // Given an Offset_to_lineno_entry vector, and an offset, figure out
2035 // if the offset points into a function according to the vector (see
2036 // comments below for the algorithm).  If it does, return an iterator
2037 // into the vector that points to the line-number that contains that
2038 // offset.  If not, it returns vector::end().
2039
2040 static std::vector<Offset_to_lineno_entry>::const_iterator
2041 offset_to_iterator(const std::vector<Offset_to_lineno_entry>* offsets,
2042                    off_t offset)
2043 {
2044   const Offset_to_lineno_entry lookup_key = { offset, 0, 0, true, 0 };
2045
2046   // lower_bound() returns the smallest offset which is >= lookup_key.
2047   // If no offset in offsets is >= lookup_key, returns end().
2048   std::vector<Offset_to_lineno_entry>::const_iterator it
2049       = std::lower_bound(offsets->begin(), offsets->end(), lookup_key);
2050
2051   // This code is easiest to understand with a concrete example.
2052   // Here's a possible offsets array:
2053   // {{offset = 3211, header_num = 0, file_num = 1, last, line_num = 16},  // 0
2054   //  {offset = 3224, header_num = 0, file_num = 1, last, line_num = 20},  // 1
2055   //  {offset = 3226, header_num = 0, file_num = 1, last, line_num = 22},  // 2
2056   //  {offset = 3231, header_num = 0, file_num = 1, last, line_num = 25},  // 3
2057   //  {offset = 3232, header_num = 0, file_num = 1, last, line_num = -1},  // 4
2058   //  {offset = 3232, header_num = 0, file_num = 1, last, line_num = 65},  // 5
2059   //  {offset = 3235, header_num = 0, file_num = 1, last, line_num = 66},  // 6
2060   //  {offset = 3236, header_num = 0, file_num = 1, last, line_num = -1},  // 7
2061   //  {offset = 5764, header_num = 0, file_num = 1, last, line_num = 48},  // 8
2062   //  {offset = 5764, header_num = 0, file_num = 1,!last, line_num = 47},  // 9
2063   //  {offset = 5765, header_num = 0, file_num = 1, last, line_num = 49},  // 10
2064   //  {offset = 5767, header_num = 0, file_num = 1, last, line_num = 50},  // 11
2065   //  {offset = 5768, header_num = 0, file_num = 1, last, line_num = 51},  // 12
2066   //  {offset = 5773, header_num = 0, file_num = 1, last, line_num = -1},  // 13
2067   //  {offset = 5787, header_num = 1, file_num = 1, last, line_num = 19},  // 14
2068   //  {offset = 5790, header_num = 1, file_num = 1, last, line_num = 20},  // 15
2069   //  {offset = 5793, header_num = 1, file_num = 1, last, line_num = 67},  // 16
2070   //  {offset = 5793, header_num = 1, file_num = 1, last, line_num = -1},  // 17
2071   //  {offset = 5793, header_num = 1, file_num = 1,!last, line_num = 66},  // 18
2072   //  {offset = 5795, header_num = 1, file_num = 1, last, line_num = 68},  // 19
2073   //  {offset = 5798, header_num = 1, file_num = 1, last, line_num = -1},  // 20
2074   // The entries with line_num == -1 mark the end of a function: the
2075   // associated offset is one past the last instruction in the
2076   // function.  This can correspond to the beginning of the next
2077   // function (as is true for offset 3232); alternately, there can be
2078   // a gap between the end of one function and the start of the next
2079   // (as is true for some others, most obviously from 3236->5764).
2080   //
2081   // Case 1: lookup_key has offset == 10.  lower_bound returns
2082   //         offsets[0].  Since it's not an exact match and we're
2083   //         at the beginning of offsets, we return end() (invalid).
2084   // Case 2: lookup_key has offset 10000.  lower_bound returns
2085   //         offset[21] (end()).  We return end() (invalid).
2086   // Case 3: lookup_key has offset == 3211.  lower_bound matches
2087   //         offsets[0] exactly, and that's the entry we return.
2088   // Case 4: lookup_key has offset == 3232.  lower_bound returns
2089   //         offsets[4].  That's an exact match, but indicates
2090   //         end-of-function.  We check if offsets[5] is also an
2091   //         exact match but not end-of-function.  It is, so we
2092   //         return offsets[5].
2093   // Case 5: lookup_key has offset == 3214.  lower_bound returns
2094   //         offsets[1].  Since it's not an exact match, we back
2095   //         up to the offset that's < lookup_key, offsets[0].
2096   //         We note offsets[0] is a valid entry (not end-of-function),
2097   //         so that's the entry we return.
2098   // Case 6: lookup_key has offset == 4000.  lower_bound returns
2099   //         offsets[8].  Since it's not an exact match, we back
2100   //         up to offsets[7].  Since offsets[7] indicates
2101   //         end-of-function, we know lookup_key is between
2102   //         functions, so we return end() (not a valid offset).
2103   // Case 7: lookup_key has offset == 5794.  lower_bound returns
2104   //         offsets[19].  Since it's not an exact match, we back
2105   //         up to offsets[16].  Note we back up to the *first*
2106   //         entry with offset 5793, not just offsets[19-1].
2107   //         We note offsets[16] is a valid entry, so we return it.
2108   //         If offsets[16] had had line_num == -1, we would have
2109   //         checked offsets[17].  The reason for this is that
2110   //         16 and 17 can be in an arbitrary order, since we sort
2111   //         only by offset and last_line_for_offset.  (Note it
2112   //         doesn't help to use line_number as a tertiary sort key,
2113   //         since sometimes we want the -1 to be first and sometimes
2114   //         we want it to be last.)
2115
2116   // This deals with cases (1) and (2).
2117   if ((it == offsets->begin() && offset < it->offset)
2118       || it == offsets->end())
2119     return offsets->end();
2120
2121   // This deals with cases (3) and (4).
2122   if (offset == it->offset)
2123     {
2124       while (it != offsets->end()
2125              && it->offset == offset
2126              && it->line_num == -1)
2127         ++it;
2128       if (it == offsets->end() || it->offset != offset)
2129         return offsets->end();
2130       else
2131         return it;
2132     }
2133
2134   // This handles the first part of case (7) -- we back up to the
2135   // *first* entry that has the offset that's behind us.
2136   gold_assert(it != offsets->begin());
2137   std::vector<Offset_to_lineno_entry>::const_iterator range_end = it;
2138   --it;
2139   const off_t range_value = it->offset;
2140   while (it != offsets->begin() && (it-1)->offset == range_value)
2141     --it;
2142
2143   // This handles cases (5), (6), and (7): if any entry in the
2144   // equal_range [it, range_end) has a line_num != -1, it's a valid
2145   // match.  If not, we're not in a function.  The line number we saw
2146   // last for an offset will be sorted first, so it'll get returned if
2147   // it's present.
2148   for (; it != range_end; ++it)
2149     if (it->line_num != -1)
2150       return it;
2151   return offsets->end();
2152 }
2153
2154 // Returns the canonical filename:lineno for the address passed in.
2155 // If other_lines is not NULL, appends the non-canonical lines
2156 // assigned to the same address.
2157
2158 template<int size, bool big_endian>
2159 std::string
2160 Sized_dwarf_line_info<size, big_endian>::do_addr2line(
2161     unsigned int shndx,
2162     off_t offset,
2163     std::vector<std::string>* other_lines)
2164 {
2165   if (this->data_valid_ == false)
2166     return "";
2167
2168   const std::vector<Offset_to_lineno_entry>* offsets;
2169   // If we do not have reloc information, then our input is a .so or
2170   // some similar data structure where all the information is held in
2171   // the offset.  In that case, we ignore the input shndx.
2172   if (this->input_is_relobj())
2173     offsets = &this->line_number_map_[shndx];
2174   else
2175     offsets = &this->line_number_map_[-1U];
2176   if (offsets->empty())
2177     return "";
2178
2179   typename std::vector<Offset_to_lineno_entry>::const_iterator it
2180       = offset_to_iterator(offsets, offset);
2181   if (it == offsets->end())
2182     return "";
2183
2184   std::string result = this->format_file_lineno(*it);
2185   if (other_lines != NULL)
2186     for (++it; it != offsets->end() && it->offset == offset; ++it)
2187       {
2188         if (it->line_num == -1)
2189           continue;  // The end of a previous function.
2190         other_lines->push_back(this->format_file_lineno(*it));
2191       }
2192   return result;
2193 }
2194
2195 // Convert the file_num + line_num into a string.
2196
2197 template<int size, bool big_endian>
2198 std::string
2199 Sized_dwarf_line_info<size, big_endian>::format_file_lineno(
2200     const Offset_to_lineno_entry& loc) const
2201 {
2202   std::string ret;
2203
2204   gold_assert(loc.header_num < static_cast<int>(this->files_.size()));
2205   gold_assert(loc.file_num
2206               < static_cast<unsigned int>(this->files_[loc.header_num].size()));
2207   const std::pair<int, std::string>& filename_pair
2208       = this->files_[loc.header_num][loc.file_num];
2209   const std::string& filename = filename_pair.second;
2210
2211   gold_assert(loc.header_num < static_cast<int>(this->directories_.size()));
2212   gold_assert(filename_pair.first
2213               < static_cast<int>(this->directories_[loc.header_num].size()));
2214   const std::string& dirname
2215       = this->directories_[loc.header_num][filename_pair.first];
2216
2217   if (!dirname.empty())
2218     {
2219       ret += dirname;
2220       ret += "/";
2221     }
2222   ret += filename;
2223   if (ret.empty())
2224     ret = "(unknown)";
2225
2226   char buffer[64];   // enough to hold a line number
2227   snprintf(buffer, sizeof(buffer), "%d", loc.line_num);
2228   ret += ":";
2229   ret += buffer;
2230
2231   return ret;
2232 }
2233
2234 // Dwarf_line_info routines.
2235
2236 static unsigned int next_generation_count = 0;
2237
2238 struct Addr2line_cache_entry
2239 {
2240   Object* object;
2241   unsigned int shndx;
2242   Dwarf_line_info* dwarf_line_info;
2243   unsigned int generation_count;
2244   unsigned int access_count;
2245
2246   Addr2line_cache_entry(Object* o, unsigned int s, Dwarf_line_info* d)
2247       : object(o), shndx(s), dwarf_line_info(d),
2248         generation_count(next_generation_count), access_count(0)
2249   {
2250     if (next_generation_count < (1U << 31))
2251       ++next_generation_count;
2252   }
2253 };
2254 // We expect this cache to be small, so don't bother with a hashtable
2255 // or priority queue or anything: just use a simple vector.
2256 static std::vector<Addr2line_cache_entry> addr2line_cache;
2257
2258 std::string
2259 Dwarf_line_info::one_addr2line(Object* object,
2260                                unsigned int shndx, off_t offset,
2261                                size_t cache_size,
2262                                std::vector<std::string>* other_lines)
2263 {
2264   Dwarf_line_info* lineinfo = NULL;
2265   std::vector<Addr2line_cache_entry>::iterator it;
2266
2267   // First, check the cache.  If we hit, update the counts.
2268   for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it)
2269     {
2270       if (it->object == object && it->shndx == shndx)
2271         {
2272           lineinfo = it->dwarf_line_info;
2273           it->generation_count = next_generation_count;
2274           // We cap generation_count at 2^31 -1 to avoid overflow.
2275           if (next_generation_count < (1U << 31))
2276             ++next_generation_count;
2277           // We cap access_count at 31 so 2^access_count doesn't overflow
2278           if (it->access_count < 31)
2279             ++it->access_count;
2280           break;
2281         }
2282     }
2283
2284   // If we don't hit the cache, create a new object and insert into the
2285   // cache.
2286   if (lineinfo == NULL)
2287   {
2288     switch (parameters->size_and_endianness())
2289       {
2290 #ifdef HAVE_TARGET_32_LITTLE
2291         case Parameters::TARGET_32_LITTLE:
2292           lineinfo = new Sized_dwarf_line_info<32, false>(object, shndx); break;
2293 #endif
2294 #ifdef HAVE_TARGET_32_BIG
2295         case Parameters::TARGET_32_BIG:
2296           lineinfo = new Sized_dwarf_line_info<32, true>(object, shndx); break;
2297 #endif
2298 #ifdef HAVE_TARGET_64_LITTLE
2299         case Parameters::TARGET_64_LITTLE:
2300           lineinfo = new Sized_dwarf_line_info<64, false>(object, shndx); break;
2301 #endif
2302 #ifdef HAVE_TARGET_64_BIG
2303         case Parameters::TARGET_64_BIG:
2304           lineinfo = new Sized_dwarf_line_info<64, true>(object, shndx); break;
2305 #endif
2306         default:
2307           gold_unreachable();
2308       }
2309     addr2line_cache.push_back(Addr2line_cache_entry(object, shndx, lineinfo));
2310   }
2311
2312   // Now that we have our object, figure out the answer
2313   std::string retval = lineinfo->addr2line(shndx, offset, other_lines);
2314
2315   // Finally, if our cache has grown too big, delete old objects.  We
2316   // assume the common (probably only) case is deleting only one object.
2317   // We use a pretty simple scheme to evict: function of LRU and MFU.
2318   while (addr2line_cache.size() > cache_size)
2319     {
2320       unsigned int lowest_score = ~0U;
2321       std::vector<Addr2line_cache_entry>::iterator lowest
2322           = addr2line_cache.end();
2323       for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it)
2324         {
2325           const unsigned int score = (it->generation_count
2326                                       + (1U << it->access_count));
2327           if (score < lowest_score)
2328             {
2329               lowest_score = score;
2330               lowest = it;
2331             }
2332         }
2333       if (lowest != addr2line_cache.end())
2334         {
2335           delete lowest->dwarf_line_info;
2336           addr2line_cache.erase(lowest);
2337         }
2338     }
2339
2340   return retval;
2341 }
2342
2343 void
2344 Dwarf_line_info::clear_addr2line_cache()
2345 {
2346   for (std::vector<Addr2line_cache_entry>::iterator it = addr2line_cache.begin();
2347        it != addr2line_cache.end();
2348        ++it)
2349     delete it->dwarf_line_info;
2350   addr2line_cache.clear();
2351 }
2352
2353 #ifdef HAVE_TARGET_32_LITTLE
2354 template
2355 class Sized_dwarf_line_info<32, false>;
2356 #endif
2357
2358 #ifdef HAVE_TARGET_32_BIG
2359 template
2360 class Sized_dwarf_line_info<32, true>;
2361 #endif
2362
2363 #ifdef HAVE_TARGET_64_LITTLE
2364 template
2365 class Sized_dwarf_line_info<64, false>;
2366 #endif
2367
2368 #ifdef HAVE_TARGET_64_BIG
2369 template
2370 class Sized_dwarf_line_info<64, true>;
2371 #endif
2372
2373 } // End namespace gold.