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