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