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 = -1;
 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::read_header_prolog(const unsigned char* lineptr)
 122 {
 123   uint32_t initial_length = elfcpp::Swap<32, big_endian>::readval(lineptr);
 124   lineptr += 4;
 125
 126   // In DWARF2/3, if the initial length is all 1 bits, then the offset
 127   // size is 8 and we need to read the next 8 bytes for the real length.
 128   if (initial_length == 0xffffffff)
 129     {
 130       header_.offset_size = 8;
 131       initial_length = elfcpp::Swap<64, big_endian>::readval(lineptr);
 132       lineptr += 8;
 133     }
 134   else
 135     header_.offset_size = 4;
 136
 137   header_.total_length = initial_length;
 138
 139   gold_assert(lineptr + header_.total_length <= buffer_end_);
 140
 141   header_.version = elfcpp::Swap<16, big_endian>::readval(lineptr);
 142   lineptr += 2;
 143
 144   if (header_.offset_size == 4)
 145     header_.prologue_length = elfcpp::Swap<32, big_endian>::readval(lineptr);
 146   else
 147     header_.prologue_length = elfcpp::Swap<64, big_endian>::readval(lineptr);
 148   lineptr += header_.offset_size;
 149
 150   header_.min_insn_length = *lineptr;
 151   lineptr += 1;
 152
 153   header_.default_is_stmt = *lineptr;
 154   lineptr += 1;
 155
 156   header_.line_base = *reinterpret_cast<const signed char*>(lineptr);
 157   lineptr += 1;
 158
 159   header_.line_range = *lineptr;
 160   lineptr += 1;
 161
 162   header_.opcode_base = *lineptr;
 163   lineptr += 1;
 164
 165   header_.std_opcode_lengths.reserve(header_.opcode_base + 1);
 166   header_.std_opcode_lengths[0] = 0;
 167   for (int i = 1; i < header_.opcode_base; i++)
 168     {
 169       header_.std_opcode_lengths[i] = *lineptr;
 170       lineptr += 1;
 171     }
 172
 173   return lineptr;
 174 }
 175
 176 // The header for a debug_line section is mildly complicated, because
 177 // the line info is very tightly encoded.
 178
 179 const unsigned char*
 180 Dwarf_line_info::read_header_tables(const unsigned char* lineptr)
 181 {
 182   // It is legal for the directory entry table to be empty.
 183   if (*lineptr)
 184     {
 185       int dirindex = 1;
 186       while (*lineptr)
 187         {
 188           const unsigned char* dirname = lineptr;
 189           gold_assert(dirindex == static_cast<int>(directories_.size()));
 190           directories_.push_back(reinterpret_cast<const char*>(dirname));
 191           lineptr += directories_.back().size() + 1;
 192           dirindex++;
 193         }
 194     }
 195   lineptr++;
 196
 197   // It is also legal for the file entry table to be empty.
 198   if (*lineptr)
 199     {
 200       int fileindex = 1;
 201       size_t len;
 202       while (*lineptr)
 203         {
 204           const char* filename = reinterpret_cast<const char*>(lineptr);
 205           lineptr += strlen(filename) + 1;
 206
 207           uint64_t dirindex = read_unsigned_LEB_128(lineptr, &len);
 208           if (dirindex >= directories_.size())
 209             dirindex = 0;
 210           lineptr += len;
 211
 212           read_unsigned_LEB_128(lineptr, &len);   // mod_time
 213           lineptr += len;
 214
 215           read_unsigned_LEB_128(lineptr, &len);   // filelength
 216           lineptr += len;
 217
 218           gold_assert(fileindex == static_cast<int>(files_.size()));
 219           files_.push_back(std::pair<int, std::string>(dirindex, filename));
 220           fileindex++;
 221         }
 222     }
 223   lineptr++;
 224
 225   return lineptr;
 226 }
 227
 228 // Process a single opcode in the .debug.line structure.
 229
 230 // Templating on size and big_endian would yield more efficient (and
 231 // simpler) code, but would bloat the binary.  Speed isn't important
 232 // here.
 233
 234 bool
 235 Dwarf_line_info::process_one_opcode(int size, bool big_endian,
 236                                     const unsigned char* start,
 237                                     struct LineStateMachine* lsm,
 238                                     size_t* len)
 239 {
 240   size_t oplen = 0;
 241   size_t templen;
 242   unsigned char opcode = *start;
 243   oplen++;
 244   start++;
 245
 246   // If the opcode is great than the opcode_base, it is a special
 247   // opcode. Most line programs consist mainly of special opcodes.
 248   if (opcode >= header_.opcode_base)
 249     {
 250       opcode -= header_.opcode_base;
 251       const int advance_address = ((opcode / header_.line_range)
 252                                    * header_.min_insn_length);
 253       lsm->address += advance_address;
 254
 255       const int advance_line = ((opcode % header_.line_range)
 256                                 + header_.line_base);
 257       lsm->line_num += advance_line;
 258       lsm->basic_block = true;
 259       *len = oplen;
 260       return true;
 261     }
 262
 263   // Otherwise, we have the regular opcodes
 264   switch (opcode)
 265     {
 266     case elfcpp::DW_LNS_copy:
 267       lsm->basic_block = false;
 268       *len = oplen;
 269       return true;
 270
 271     case elfcpp::DW_LNS_advance_pc:
 272       {
 273         const uint64_t advance_address
 274             = read_unsigned_LEB_128(start, &templen);
 275         oplen += templen;
 276         lsm->address += header_.min_insn_length * advance_address;
 277       }
 278       break;
 279
 280     case elfcpp::DW_LNS_advance_line:
 281       {
 282         const uint64_t advance_line = read_signed_LEB_128(start, &templen);
 283         oplen += templen;
 284         lsm->line_num += advance_line;
 285       }
 286       break;
 287
 288     case elfcpp::DW_LNS_set_file:
 289       {
 290         const uint64_t fileno = read_unsigned_LEB_128(start, &templen);
 291         oplen += templen;
 292         lsm->file_num = fileno;
 293       }
 294       break;
 295
 296     case elfcpp::DW_LNS_set_column:
 297       {
 298         const uint64_t colno = read_unsigned_LEB_128(start, &templen);
 299         oplen += templen;
 300         lsm->column_num = colno;
 301       }
 302       break;
 303
 304     case elfcpp::DW_LNS_negate_stmt:
 305       lsm->is_stmt = !lsm->is_stmt;
 306       break;
 307
 308     case elfcpp::DW_LNS_set_basic_block:
 309       lsm->basic_block = true;
 310       break;
 311
 312     case elfcpp::DW_LNS_fixed_advance_pc:
 313       {
 314         int advance_address;
 315         if (big_endian)
 316           advance_address = elfcpp::Swap<16, true>::readval(start);
 317         else
 318           advance_address = elfcpp::Swap<16, false>::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             // FIXME: modify the address based on the reloc
 352             if (size == 32 && big_endian == false)
 353               lsm->address = elfcpp::Swap<32, false>::readval(start);
 354             else if (size == 32 && big_endian == true)
 355               lsm->address = elfcpp::Swap<32, true>::readval(start);
 356             else if (size == 64 && big_endian == false)
 357               lsm->address = elfcpp::Swap<64, false>::readval(start);
 358             else if (size == 64 && big_endian == true)
 359               lsm->address = elfcpp::Swap<64, true>::readval(start);
 360             else
 361               gold_assert(false);  // We need to implement more cases, then.
 362             // FIXME: set lsm->shndx from the reloc
 363             lsm->shndx = 1;
 364             break;
 365
 366           case elfcpp::DW_LNE_define_file:
 367             {
 368               const char* filename  = reinterpret_cast<const char*>(start);
 369               templen = strlen(filename) + 1;
 370               start += templen;
 371
 372               uint64_t dirindex = read_unsigned_LEB_128(start, &templen);
 373               if (dirindex >= directories_.size())
 374                 dirindex = 0;
 375               oplen += templen;
 376
 377               read_unsigned_LEB_128(start, &templen);   // mod_time
 378               oplen += templen;
 379
 380               read_unsigned_LEB_128(start, &templen);   // filelength
 381               oplen += templen;
 382
 383               files_.push_back(std::pair<int, std::string>(dirindex,
 384                                                            filename));
 385             }
 386             break;
 387           }
 388       }
 389       break;
 390
 391     default:
 392       {
 393         // Ignore unknown opcode  silently
 394         for (int i = 0; i < header_.std_opcode_lengths[opcode]; i++)
 395           {
 396             size_t templen;
 397             read_unsigned_LEB_128(start, &templen);
 398             start += templen;
 399             oplen += templen;
 400           }
 401       }
 402       break;
 403   }
 404   *len = oplen;
 405   return false;
 406 }
 407
 408 // Read the debug information at LINEPTR and store it in the line
 409 // number map.
 410
 411 unsigned const char*
 412 Dwarf_line_info::read_lines(int size, bool big_endian,
 413                             unsigned const char* lineptr)
 414 {
 415   struct LineStateMachine lsm;
 416
 417   // LENGTHSTART is the place the length field is based on.  It is the
 418   // point in the header after the initial length field.
 419   const unsigned char* lengthstart = buffer_;
 420
 421   // In 64 bit dwarf, the initial length is 12 bytes, because of the
 422   // 0xffffffff at the start.
 423   if (header_.offset_size == 8)
 424     lengthstart += 12;
 425   else
 426     lengthstart += 4;
 427
 428   while (lineptr < lengthstart + header_.total_length)
 429     {
 430       ResetLineStateMachine(&lsm, header_.default_is_stmt);
 431       while (!lsm.end_sequence)
 432         {
 433           size_t oplength;
 434           bool add_line = this->process_one_opcode(size, big_endian,
 435                                                    lineptr, &lsm, &oplength);
 436           if (add_line)
 437             {
 438               Offset_to_lineno_entry entry
 439                   = { lsm.address, lsm.file_num, lsm.line_num };
 440               line_number_map_[lsm.shndx].push_back(entry);
 441             }
 442           lineptr += oplength;
 443         }
 444     }
 445
 446   return lengthstart + header_.total_length;
 447 }
 448
 449 // Called after all line numbers have been read.
 450
 451 void
 452 Dwarf_line_info::finalize_line_number_map()
 453 {
 454   for (Lineno_map::iterator it = line_number_map_.begin();
 455        it != line_number_map_.end();
 456        ++it)
 457     // Each vector needs to be sorted by offset.
 458     sort(it->second.begin(), it->second.end());
 459 }
 460
 461 // Return a string for a file name and line number.
 462
 463 std::string
 464 Dwarf_line_info::addr2line(unsigned int shndx, off_t offset)
 465 {
 466   const Offset_to_lineno_entry lookup_key = { offset, 0, 0 };
 467   std::vector<Offset_to_lineno_entry>& offsets = line_number_map_[shndx];
 468   std::vector<Offset_to_lineno_entry>::const_iterator it
 469       = std::lower_bound(offsets.begin(), offsets.end(), lookup_key);
 470
 471   // If we found an exact match, great, otherwise find the last entry
 472   // before the passed-in offset.
 473   if (it->offset > offset)
 474     {
 475       if (it == offsets.begin())
 476         return "";
 477       --it;
 478       gold_assert(it->offset < offset);
 479     }
 480
 481   // Convert the file_num + line_num into a string.
 482   std::string ret;
 483   gold_assert(it->file_num < static_cast<int>(files_.size()));
 484   const std::pair<int, std::string>& filename_pair = files_[it->file_num];
 485   gold_assert(filename_pair.first < static_cast<int>(directories_.size()));
 486   const std::string& dirname = directories_[filename_pair.first];
 487   const std::string& filename = filename_pair.second;
 488   if (!dirname.empty())
 489     {
 490       ret += dirname;
 491       ret += "/";
 492     }
 493   ret += filename;
 494   if (ret.empty())
 495     ret = "(unknown)";
 496
 497   char buffer[64];   // enough to hold a line number
 498   snprintf(buffer, sizeof(buffer), "%d", it->line_num);
 499   ret += ":";
 500   ret += buffer;
 501
 502   return ret;
 503 }
 504
 505 #ifdef HAVE_TARGET_32_LITTLE
 506 template
 507 const unsigned char*
 508 Dwarf_line_info::read_header_prolog<32, false>(const unsigned char* lineptr);
 509 #endif
 510
 511 #ifdef HAVE_TARGET_32_BIG
 512 template
 513 const unsigned char*
 514 Dwarf_line_info::read_header_prolog<32, true>(const unsigned char* lineptr);
 515 #endif
 516
 517 #ifdef HAVE_TARGET_64_LITTLE
 518 template
 519 const unsigned char*
 520 Dwarf_line_info::read_header_prolog<64, false>(const unsigned char* lineptr);
 521 #endif
 522
 523 #ifdef HAVE_TARGET_64_BIG
 524 template
 525 const unsigned char*
 526 Dwarf_line_info::read_header_prolog<64, true>(const unsigned char* lineptr);
 527 #endif
 528
 529 } // End namespace gold.