gold/dwarf_reader.cc

   1 // dwarf_reader.cc -- parse dwarf2/3 debug information
   2
   3 // Copyright 2007 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 "elfcpp_swap.h"
  26 #include "dwarf.h"
  27 #include "reloc.h"
  28 #include "dwarf_reader.h"
  29
  30 namespace {
  31
  32 // Read an unsigned LEB128 number.  Each byte contains 7 bits of
  33 // information, plus one bit saying whether the number continues or
  34 // not.
  35
  36 uint64_t
  37 read_unsigned_LEB_128(const unsigned char* buffer, size_t* len)
  38 {
  39   uint64_t result = 0;
  40   size_t num_read = 0;
  41   unsigned int shift = 0;
  42   unsigned char byte;
  43
  44   do
  45     {
  46       byte = *buffer++;
  47       num_read++;
  48       result |= (static_cast<uint64_t>(byte & 0x7f)) << shift;
  49       shift += 7;
  50     }
  51   while (byte & 0x80);
  52
  53   *len = num_read;
  54
  55   return result;
  56 }
  57
  58 // Read a signed LEB128 number.  These are like regular LEB128
  59 // numbers, except the last byte may have a sign bit set.
  60
  61 int64_t
  62 read_signed_LEB_128(const unsigned char* buffer, size_t* len)
  63 {
  64   int64_t result = 0;
  65   int shift = 0;
  66   size_t num_read = 0;
  67   unsigned char byte;
  68
  69   do
  70     {
  71       byte = *buffer++;
  72       num_read++;
  73       result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
  74       shift += 7;
  75     }
  76   while (byte & 0x80);
  77
  78   if ((shift < 8 * static_cast<int>(sizeof(result))) && (byte & 0x40))
  79     result |= -((static_cast<int64_t>(1)) << shift);
  80   *len = num_read;
  81   return result;
  82 }
  83
  84 } // End anonymous namespace.
  85
  86
  87 namespace gold {
  88
  89 // This is the format of a DWARF2/3 line state machine that we process
  90 // opcodes using.  There is no need for anything outside the lineinfo
  91 // processor to know how this works.
  92
  93 struct LineStateMachine
  94 {
  95   int file_num;
  96   uint64_t address;
  97   int line_num;
  98   int column_num;
  99   unsigned int shndx;    // the section address refers to
 100   bool is_stmt;          // stmt means statement.
 101   bool basic_block;
 102   bool end_sequence;
 103 };
 104
 105 static void
 106 ResetLineStateMachine(struct LineStateMachine* lsm, bool default_is_stmt)
 107 {
 108   lsm->file_num = 1;
 109   lsm->address = 0;
 110   lsm->line_num = 1;
 111   lsm->column_num = 0;
 112   lsm->shndx = -1U;
 113   lsm->is_stmt = default_is_stmt;
 114   lsm->basic_block = false;
 115   lsm->end_sequence = false;
 116 }
 117
 118 // Read the DWARF header.
 119
 120 template<int size, bool big_endian>
 121 const unsigned char*
 122 Dwarf_line_info<size, big_endian>::read_header_prolog(
 123     const unsigned char* lineptr)
 124 {
 125   uint32_t initial_length = elfcpp::Swap<32, big_endian>::readval(lineptr);
 126   lineptr += 4;
 127
 128   // In DWARF2/3, if the initial length is all 1 bits, then the offset
 129   // size is 8 and we need to read the next 8 bytes for the real length.
 130   if (initial_length == 0xffffffff)
 131     {
 132       header_.offset_size = 8;
 133       initial_length = elfcpp::Swap<64, big_endian>::readval(lineptr);
 134       lineptr += 8;
 135     }
 136   else
 137     header_.offset_size = 4;
 138
 139   header_.total_length = initial_length;
 140
 141   gold_assert(lineptr + header_.total_length <= buffer_end_);
 142
 143   header_.version = elfcpp::Swap<16, big_endian>::readval(lineptr);
 144   lineptr += 2;
 145
 146   if (header_.offset_size == 4)
 147     header_.prologue_length = elfcpp::Swap<32, big_endian>::readval(lineptr);
 148   else
 149     header_.prologue_length = elfcpp::Swap<64, big_endian>::readval(lineptr);
 150   lineptr += header_.offset_size;
 151
 152   header_.min_insn_length = *lineptr;
 153   lineptr += 1;
 154
 155   header_.default_is_stmt = *lineptr;
 156   lineptr += 1;
 157
 158   header_.line_base = *reinterpret_cast<const signed char*>(lineptr);
 159   lineptr += 1;
 160
 161   header_.line_range = *lineptr;
 162   lineptr += 1;
 163
 164   header_.opcode_base = *lineptr;
 165   lineptr += 1;
 166
 167   header_.std_opcode_lengths.reserve(header_.opcode_base + 1);
 168   header_.std_opcode_lengths[0] = 0;
 169   for (int i = 1; i < header_.opcode_base; i++)
 170     {
 171       header_.std_opcode_lengths[i] = *lineptr;
 172       lineptr += 1;
 173     }
 174
 175   return lineptr;
 176 }
 177
 178 // The header for a debug_line section is mildly complicated, because
 179 // the line info is very tightly encoded.
 180
 181 template<int size, bool big_endian>
 182 const unsigned char*
 183 Dwarf_line_info<size, big_endian>::read_header_tables(
 184     const unsigned char* lineptr)
 185 {
 186   // It is legal for the directory entry table to be empty.
 187   if (*lineptr)
 188     {
 189       int dirindex = 1;
 190       while (*lineptr)
 191         {
 192           const unsigned char* dirname = lineptr;
 193           gold_assert(dirindex == static_cast<int>(directories_.size()));
 194           directories_.push_back(reinterpret_cast<const char*>(dirname));
 195           lineptr += directories_.back().size() + 1;
 196           dirindex++;
 197         }
 198     }
 199   lineptr++;
 200
 201   // It is also legal for the file entry table to be empty.
 202   if (*lineptr)
 203     {
 204       int fileindex = 1;
 205       size_t len;
 206       while (*lineptr)
 207         {
 208           const char* filename = reinterpret_cast<const char*>(lineptr);
 209           lineptr += strlen(filename) + 1;
 210
 211           uint64_t dirindex = read_unsigned_LEB_128(lineptr, &len);
 212           if (dirindex >= directories_.size())
 213             dirindex = 0;
 214           lineptr += len;
 215
 216           read_unsigned_LEB_128(lineptr, &len);   // mod_time
 217           lineptr += len;
 218
 219           read_unsigned_LEB_128(lineptr, &len);   // filelength
 220           lineptr += len;
 221
 222           gold_assert(fileindex == static_cast<int>(files_.size()));
 223           files_.push_back(std::pair<int, std::string>(dirindex, filename));
 224           fileindex++;
 225         }
 226     }
 227   lineptr++;
 228
 229   return lineptr;
 230 }
 231
 232 // Process a single opcode in the .debug.line structure.
 233
 234 // Templating on size and big_endian would yield more efficient (and
 235 // simpler) code, but would bloat the binary.  Speed isn't important
 236 // here.
 237
 238 template<int size, bool big_endian>
 239 bool
 240 Dwarf_line_info<size, big_endian>::process_one_opcode(
 241     const unsigned char* start, struct LineStateMachine* lsm, size_t* len)
 242 {
 243   size_t oplen = 0;
 244   size_t templen;
 245   unsigned char opcode = *start;
 246   oplen++;
 247   start++;
 248
 249   // If the opcode is great than the opcode_base, it is a special
 250   // opcode. Most line programs consist mainly of special opcodes.
 251   if (opcode >= header_.opcode_base)
 252     {
 253       opcode -= header_.opcode_base;
 254       const int advance_address = ((opcode / header_.line_range)
 255                                    * header_.min_insn_length);
 256       lsm->address += advance_address;
 257
 258       const int advance_line = ((opcode % header_.line_range)
 259                                 + header_.line_base);
 260       lsm->line_num += advance_line;
 261       lsm->basic_block = true;
 262       *len = oplen;
 263       return true;
 264     }
 265
 266   // Otherwise, we have the regular opcodes
 267   switch (opcode)
 268     {
 269     case elfcpp::DW_LNS_copy:
 270       lsm->basic_block = false;
 271       *len = oplen;
 272       return true;
 273
 274     case elfcpp::DW_LNS_advance_pc:
 275       {
 276         const uint64_t advance_address
 277             = read_unsigned_LEB_128(start, &templen);
 278         oplen += templen;
 279         lsm->address += header_.min_insn_length * advance_address;
 280       }
 281       break;
 282
 283     case elfcpp::DW_LNS_advance_line:
 284       {
 285         const uint64_t advance_line = read_signed_LEB_128(start, &templen);
 286         oplen += templen;
 287         lsm->line_num += advance_line;
 288       }
 289       break;
 290
 291     case elfcpp::DW_LNS_set_file:
 292       {
 293         const uint64_t fileno = read_unsigned_LEB_128(start, &templen);
 294         oplen += templen;
 295         lsm->file_num = fileno;
 296       }
 297       break;
 298
 299     case elfcpp::DW_LNS_set_column:
 300       {
 301         const uint64_t colno = read_unsigned_LEB_128(start, &templen);
 302         oplen += templen;
 303         lsm->column_num = colno;
 304       }
 305       break;
 306
 307     case elfcpp::DW_LNS_negate_stmt:
 308       lsm->is_stmt = !lsm->is_stmt;
 309       break;
 310
 311     case elfcpp::DW_LNS_set_basic_block:
 312       lsm->basic_block = true;
 313       break;
 314
 315     case elfcpp::DW_LNS_fixed_advance_pc:
 316       {
 317         int advance_address;
 318         advance_address = elfcpp::Swap<16, big_endian>::readval(start);
 319         oplen += 2;
 320         lsm->address += advance_address;
 321       }
 322       break;
 323
 324     case elfcpp::DW_LNS_const_add_pc:
 325       {
 326         const int advance_address = (header_.min_insn_length
 327                                      * ((255 - header_.opcode_base)
 328                                         / header_.line_range));
 329         lsm->address += advance_address;
 330       }
 331       break;
 332
 333     case elfcpp::DW_LNS_extended_op:
 334       {
 335         const uint64_t extended_op_len
 336             = read_unsigned_LEB_128(start, &templen);
 337         start += templen;
 338         oplen += templen + extended_op_len;
 339
 340         const unsigned char extended_op = *start;
 341         start++;
 342
 343         switch (extended_op)
 344           {
 345           case elfcpp::DW_LNE_end_sequence:
 346             lsm->end_sequence = true;
 347             *len = oplen;
 348             return true;
 349
 350           case elfcpp::DW_LNE_set_address:
 351             {
 352               typename Reloc_map::const_iterator it
 353                   = reloc_map_.find(start - this->buffer_);
 354               if (it != reloc_map_.end())
 355                 {
 356                   // value + addend.
 357                   lsm->address =
 358                     (elfcpp::Swap<size, big_endian>::readval(start)
 359                      + it->second.second);
 360                   lsm->shndx = it->second.first;
 361                 }
 362               else
 363                 {
 364                   // Every set_address should have an associated
 365                   // relocation.
 366                   this->data_valid_ = false;
 367                 }
 368               break;
 369             }
 370           case elfcpp::DW_LNE_define_file:
 371             {
 372               const char* filename  = reinterpret_cast<const char*>(start);
 373               templen = strlen(filename) + 1;
 374               start += templen;
 375
 376               uint64_t dirindex = read_unsigned_LEB_128(start, &templen);
 377               if (dirindex >= directories_.size())
 378                 dirindex = 0;
 379               oplen += templen;
 380
 381               read_unsigned_LEB_128(start, &templen);   // mod_time
 382               oplen += templen;
 383
 384               read_unsigned_LEB_128(start, &templen);   // filelength
 385               oplen += templen;
 386
 387               files_.push_back(std::pair<int, std::string>(dirindex,
 388                                                            filename));
 389             }
 390             break;
 391           }
 392       }
 393       break;
 394
 395     default:
 396       {
 397         // Ignore unknown opcode  silently
 398         for (int i = 0; i < header_.std_opcode_lengths[opcode]; i++)
 399           {
 400             size_t templen;
 401             read_unsigned_LEB_128(start, &templen);
 402             start += templen;
 403             oplen += templen;
 404           }
 405       }
 406       break;
 407   }
 408   *len = oplen;
 409   return false;
 410 }
 411
 412 // Read the debug information at LINEPTR and store it in the line
 413 // number map.
 414
 415 template<int size, bool big_endian>
 416 unsigned const char*
 417 Dwarf_line_info<size, big_endian>::read_lines(unsigned const char* lineptr)
 418 {
 419   struct LineStateMachine lsm;
 420
 421   // LENGTHSTART is the place the length field is based on.  It is the
 422   // point in the header after the initial length field.
 423   const unsigned char* lengthstart = buffer_;
 424
 425   // In 64 bit dwarf, the initial length is 12 bytes, because of the
 426   // 0xffffffff at the start.
 427   if (header_.offset_size == 8)
 428     lengthstart += 12;
 429   else
 430     lengthstart += 4;
 431
 432   while (lineptr < lengthstart + header_.total_length)
 433     {
 434       ResetLineStateMachine(&lsm, header_.default_is_stmt);
 435       while (!lsm.end_sequence)
 436         {
 437           size_t oplength;
 438           bool add_line = this->process_one_opcode(lineptr, &lsm, &oplength);
 439           if (add_line)
 440             {
 441               Offset_to_lineno_entry entry
 442                   = { lsm.address, lsm.file_num, lsm.line_num };
 443               line_number_map_[lsm.shndx].push_back(entry);
 444             }
 445           lineptr += oplength;
 446         }
 447     }
 448
 449   return lengthstart + header_.total_length;
 450 }
 451
 452 // Looks in the symtab to see what section a symbol is in.
 453
 454 template<int size, bool big_endian>
 455 unsigned int
 456 Dwarf_line_info<size, big_endian>::symbol_section(
 457     unsigned int sym,
 458     typename elfcpp::Elf_types<size>::Elf_Addr* value)
 459 {
 460   const int symsize = elfcpp::Elf_sizes<size>::sym_size;
 461   gold_assert(this->symtab_buffer_ + sym * symsize < this->symtab_buffer_end_);
 462   elfcpp::Sym<size, big_endian> elfsym(this->symtab_buffer_ + sym * symsize);
 463   *value = elfsym.get_st_value();
 464   return elfsym.get_st_shndx();
 465 }
 466
 467 // Read the relocations into a Reloc_map.
 468
 469 template<int size, bool big_endian>
 470 void
 471 Dwarf_line_info<size, big_endian>::read_relocs()
 472 {
 473   if (this->symtab_buffer_ == NULL)
 474     return;
 475
 476   typename elfcpp::Elf_types<size>::Elf_Addr value;
 477   off_t reloc_offset;
 478   while ((reloc_offset = this->track_relocs_->next_offset()) != -1)
 479     {
 480       const unsigned int sym = this->track_relocs_->next_symndx();
 481       const unsigned int shndx = this->symbol_section(sym, &value);
 482       this->reloc_map_[reloc_offset] = std::make_pair(shndx, value);
 483       this->track_relocs_->advance(reloc_offset + 1);
 484     }
 485 }
 486
 487 // Read the line number info.
 488
 489 template<int size, bool big_endian>
 490 void
 491 Dwarf_line_info<size, big_endian>::read_line_mappings()
 492 {
 493   read_relocs();
 494   while (this->buffer_ < this->buffer_end_)
 495     {
 496       const unsigned char* lineptr = this->buffer_;
 497       lineptr = this->read_header_prolog(lineptr);
 498       lineptr = this->read_header_tables(lineptr);
 499       lineptr = this->read_lines(lineptr);
 500       this->buffer_ = lineptr;
 501     }
 502
 503   // Sort the lines numbers, so addr2line can use binary search.
 504   for (typename Lineno_map::iterator it = line_number_map_.begin();
 505        it != line_number_map_.end();
 506        ++it)
 507     // Each vector needs to be sorted by offset.
 508     std::sort(it->second.begin(), it->second.end());
 509 }
 510
 511 // Return a string for a file name and line number.
 512
 513 template<int size, bool big_endian>
 514 std::string
 515 Dwarf_line_info<size, big_endian>::addr2line(unsigned int shndx, off_t offset)
 516 {
 517   if (this->data_valid_ == false)
 518     return "";
 519
 520   const Offset_to_lineno_entry lookup_key = { offset, 0, 0 };
 521   std::vector<Offset_to_lineno_entry>& offsets = this->line_number_map_[shndx];
 522   if (offsets.empty())
 523     return "";
 524
 525   typename std::vector<Offset_to_lineno_entry>::const_iterator it
 526       = std::lower_bound(offsets.begin(), offsets.end(), lookup_key);
 527
 528   // If we found an exact match, great, otherwise find the last entry
 529   // before the passed-in offset.
 530   if (it->offset > offset)
 531     {
 532       if (it == offsets.begin())
 533         return "";
 534       --it;
 535       gold_assert(it->offset < offset);
 536     }
 537
 538   // Convert the file_num + line_num into a string.
 539   std::string ret;
 540   gold_assert(it->file_num < static_cast<int>(files_.size()));
 541   const std::pair<int, std::string>& filename_pair = files_[it->file_num];
 542   gold_assert(filename_pair.first < static_cast<int>(directories_.size()));
 543   const std::string& dirname = directories_[filename_pair.first];
 544   const std::string& filename = filename_pair.second;
 545   if (!dirname.empty())
 546     {
 547       ret += dirname;
 548       ret += "/";
 549     }
 550   ret += filename;
 551   if (ret.empty())
 552     ret = "(unknown)";
 553
 554   char buffer[64];   // enough to hold a line number
 555   snprintf(buffer, sizeof(buffer), "%d", it->line_num);
 556   ret += ":";
 557   ret += buffer;
 558
 559   return ret;
 560 }
 561
 562 #ifdef HAVE_TARGET_32_LITTLE
 563 template
 564 class Dwarf_line_info<32, false>;
 565 #endif
 566
 567 #ifdef HAVE_TARGET_32_BIG
 568 template
 569 class Dwarf_line_info<32, true>;
 570 #endif
 571
 572 #ifdef HAVE_TARGET_64_LITTLE
 573 template
 574 class Dwarf_line_info<64, false>;
 575 #endif
 576
 577 #ifdef HAVE_TARGET_64_BIG
 578 template
 579 class Dwarf_line_info<64, true>;
 580 #endif
 581
 582 } // End namespace gold.