gold/dwarf_reader.cc

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