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