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