src/ld/debugline.c

   1 /*
   2  * Copyright (c) 2005-2009 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 #ifndef KLD
  24 #include <string.h>
  25 #include <stdlib.h>
  26 #include <stdbool.h>
  27 #include <stdio.h>
  28 #include "dwarf2.h"
  29 #include "debugline.h"
  30
  31 struct line_reader_data
  32 {
  33   bool little_endian;
  34
  35   /* From the line number information header.  */
  36   uint8_t minimum_instruction_length;
  37   int8_t line_base;
  38   uint8_t line_range;
  39   uint8_t opcode_base;
  40   const uint8_t * standard_opcode_lengths;
  41   size_t numdir;
  42   const uint8_t * * dirnames;
  43   size_t numfile_orig;
  44   size_t numfile;  /* As updated during execution of the table.  */
  45   const uint8_t * * filenames;
  46
  47   /* Current position in the line table.  */
  48   const uint8_t * cpos;
  49   /* End of this part of the line table.  */
  50   const uint8_t * end;
  51   /* Start of the line table.  */
  52   const uint8_t * init;
  53
  54   struct line_info cur;
  55 };
  56
  57 /* Read in a word of fixed size, which may be unaligned, in the
  58    appropriate endianness.  */
  59 #define read_16(p) (lnd->little_endian          \
  60                     ? ((p)[1] << 8 | (p)[0])    \
  61                     : ((p)[0] << 8 | (p)[1]))
  62 #define read_32(p) (lnd->little_endian                                      \
  63                     ? ((p)[3] << 24 | (p)[2] << 16 | (p)[1] << 8 | (p)[0])  \
  64                     : ((p)[0] << 24 | (p)[1] << 16 | (p)[2] << 8 | (p)[3]))
  65 #define read_64(p) (lnd->little_endian                                      \
  66                     ? ((uint64_t) (p)[7] << 56 | (uint64_t) (p)[6] << 48    \
  67                        | (uint64_t) (p)[5] << 40 | (uint64_t) (p)[4] << 32  \
  68                        | (uint64_t) (p)[3] << 24 | (uint64_t) (p)[2] << 16u \
  69                        | (uint64_t) (p)[1] << 8 | (uint64_t) (p)[0])        \
  70                     : ((uint64_t) (p)[0] << 56 | (uint64_t) (p)[1] << 48    \
  71                        | (uint64_t) (p)[2] << 40 | (uint64_t) (p)[3] << 32  \
  72                        | (uint64_t) (p)[4] << 24 | (uint64_t) (p)[5] << 16u \
  73                        | (uint64_t) (p)[6] << 8 | (uint64_t) (p)[7]))
  74
  75 /* Skip over a LEB128 value (signed or unsigned).  */
  76 static void
  77 skip_leb128 (struct line_reader_data * leb)
  78 {
  79   while (leb->cpos != leb->end && *leb->cpos >= 0x80)
  80     leb->cpos++;
  81   if (leb->cpos != leb->end)
  82     leb->cpos++;
  83 }
  84
  85 /* Read a ULEB128 into a 64-bit word.  Return (uint64_t)-1 on overflow
  86    or error.  On overflow, skip past the rest of the uleb128.  */
  87 static uint64_t
  88 read_uleb128 (struct line_reader_data * leb)
  89 {
  90   uint64_t result = 0;
  91   int bit = 0;
  92
  93   do  {
  94     uint64_t b;
  95
  96     if (leb->cpos == leb->end)
  97       return (uint64_t) -1;
  98
  99     b = *leb->cpos & 0x7f;
 100
 101     if (bit >= 64 || b << bit >> bit != b)
 102       result = (uint64_t) -1;
 103     else
 104       result |= b << bit, bit += 7;
 105   } while (*leb->cpos++ >= 0x80);
 106   return result;
 107 }
 108
 109
 110 /* Read a SLEB128 into a 64-bit word.  Return 0 on overflow or error
 111    (which is not very helpful).  On overflow, skip past the rest of
 112    the SLEB128.  For negative numbers, this actually overflows when
 113    under -2^62, but since this is used for line numbers that ought to
 114    be OK...  */
 115 static int64_t
 116 read_sleb128 (struct line_reader_data * leb)
 117 {
 118   const uint8_t * start_pos = leb->cpos;
 119   uint64_t v = read_uleb128 (leb);
 120   uint64_t signbit;
 121
 122   if (v >= 1ull << 63)
 123     return 0;
 124   if (leb->cpos - start_pos > 9)
 125     return v;
 126
 127   signbit = 1ull << ((leb->cpos - start_pos) * 7 - 1);
 128
 129   return v | -(v & signbit);
 130 }
 131
 132 /* Free a line_reader_data structure.  */
 133 void
 134 line_free (struct line_reader_data * lnd)
 135 {
 136   if (! lnd)
 137     return;
 138   if (lnd->dirnames)
 139     free (lnd->dirnames);
 140   if (lnd->filenames)
 141     free (lnd->filenames);
 142   free (lnd);
 143 }
 144
 145 /* Return the pathname of the file in S, or NULL on error.
 146    The result will have been allocated with malloc.  */
 147
 148 char *
 149 line_file (struct line_reader_data *lnd, uint64_t n)
 150 {
 151   const uint8_t * prev_pos = lnd->cpos;
 152   size_t filelen, dirlen;
 153   uint64_t dir;
 154   char * result;
 155
 156   /* I'm not sure if this is actually an error.  */
 157   if (n == 0
 158       || n > lnd->numfile)
 159     return NULL;
 160
 161   filelen = strlen ((const char *)lnd->filenames[n - 1]);
 162   lnd->cpos = lnd->filenames[n - 1] + filelen + 1;
 163   dir = read_uleb128 (lnd);
 164   lnd->cpos = prev_pos;
 165   if (dir == 0
 166       || lnd->filenames[n - 1][0] == '/')
 167     return strdup ((const char *)lnd->filenames[n - 1]);
 168   else if (dir > lnd->numdir)
 169     return NULL;
 170
 171   dirlen = strlen ((const char *) lnd->dirnames[dir - 1]);
 172   result = malloc (dirlen + filelen + 2);
 173   memcpy (result, lnd->dirnames[dir - 1], dirlen);
 174   result[dirlen] = '/';
 175   memcpy (result + dirlen + 1, lnd->filenames[n - 1], filelen);
 176   result[dirlen + 1 + filelen] = '\0';
 177   return result;
 178 }
 179
 180 /* Initialize a state S.  Return FALSE on error.  */
 181
 182 static void
 183 init_state (struct line_info *s)
 184 {
 185   s->file = 1;
 186   s->line = 1;
 187   s->col = 0;
 188   s->pc = 0;
 189   s->end_of_sequence = false;
 190 }
 191
 192 /* Read a debug_line section.  */
 193
 194 struct line_reader_data *
 195 line_open (const uint8_t * debug_line, size_t debug_line_size,
 196            int little_endian)
 197 {
 198   struct line_reader_data * lnd = NULL;
 199   bool dwarf_size_64;
 200
 201   uint64_t lnd_length, header_length;
 202   const uint8_t * table_start;
 203
 204   if (debug_line_size < 12)
 205     return NULL;
 206
 207   lnd = malloc (sizeof (struct line_reader_data));
 208   if (! lnd)
 209     return NULL;
 210   bzero(lnd, sizeof(struct line_reader_data));
 211
 212   lnd->little_endian = little_endian;
 213   lnd->cpos = debug_line;
 214
 215   lnd_length = read_32 (lnd->cpos);
 216   lnd->cpos += 4;
 217   if (lnd_length == 0xffffffff)
 218     {
 219       lnd_length = read_64 (lnd->cpos);
 220       lnd->cpos += 8;
 221       dwarf_size_64 = true;
 222     }
 223   else if (lnd_length > 0xfffffff0)
 224     /* Not a format we understand.  */
 225     goto error;
 226   else
 227     dwarf_size_64 = false;
 228
 229   if (debug_line_size < lnd_length + (dwarf_size_64 ? 12 : 4)
 230       || lnd_length < (dwarf_size_64 ? 15 : 11))
 231     /* Too small.  */
 232     goto error;
 233
 234   if (read_16 (lnd->cpos) != 2)
 235     /* Unknown line number format.  */
 236     goto error;
 237   lnd->cpos += 2;
 238
 239   header_length = dwarf_size_64 ? (uint64_t)read_64(lnd->cpos) : (uint64_t)read_32(lnd->cpos);
 240   lnd->cpos += dwarf_size_64 ? 8 : 4;
 241   if (lnd_length < header_length + (lnd->cpos - debug_line)
 242       || header_length < 7)
 243     goto error;
 244
 245   lnd->minimum_instruction_length = lnd->cpos[0];
 246   /* Ignore default_is_stmt.  */
 247   lnd->line_base = lnd->cpos[2];
 248   lnd->line_range = lnd->cpos[3];
 249   lnd->opcode_base = lnd->cpos[4];
 250
 251   if (lnd->opcode_base == 0)
 252     /* Every valid line number program must use at least opcode 0
 253        for DW_LNE_end_sequence.  */
 254     goto error;
 255
 256   lnd->standard_opcode_lengths = lnd->cpos + 5;
 257   if (header_length < (uint64_t)(5 + (lnd->opcode_base - 1)))
 258     /* Header not long enough.  */
 259     goto error;
 260   lnd->cpos += 5 + lnd->opcode_base - 1;
 261   lnd->end = debug_line + header_length + (dwarf_size_64 ? 22 : 10);
 262
 263   /* Make table of offsets to directory names.  */
 264   table_start = lnd->cpos;
 265   lnd->numdir = 0;
 266   while (lnd->cpos != lnd->end && *lnd->cpos)
 267     {
 268       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos);
 269       if (! lnd->cpos)
 270         goto error;
 271       lnd->cpos++;
 272       lnd->numdir++;
 273     }
 274   if (lnd->cpos == lnd->end)
 275     goto error;
 276   lnd->dirnames = malloc (lnd->numdir * sizeof (const uint8_t *));
 277   if (! lnd->dirnames)
 278     goto error;
 279   lnd->numdir = 0;
 280   lnd->cpos = table_start;
 281   while (*lnd->cpos)
 282     {
 283       lnd->dirnames[lnd->numdir++] = lnd->cpos;
 284       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos) + 1;
 285     }
 286   lnd->cpos++;
 287
 288   /* Make table of offsets to file entries.  */
 289   table_start = lnd->cpos;
 290   lnd->numfile = 0;
 291   while (lnd->cpos != lnd->end && *lnd->cpos)
 292     {
 293       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos);
 294       if (! lnd->cpos)
 295         goto error;
 296       lnd->cpos++;
 297       skip_leb128 (lnd);
 298       skip_leb128 (lnd);
 299       skip_leb128 (lnd);
 300       lnd->numfile++;
 301     }
 302   if (lnd->cpos == lnd->end)
 303     goto error;
 304   lnd->filenames = malloc (lnd->numfile * sizeof (const uint8_t *));
 305   if (! lnd->filenames)
 306     goto error;
 307   lnd->numfile = 0;
 308   lnd->cpos = table_start;
 309   while (*lnd->cpos)
 310     {
 311       lnd->filenames[lnd->numfile++] = lnd->cpos;
 312       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos) + 1;
 313       skip_leb128 (lnd);
 314       skip_leb128 (lnd);
 315       skip_leb128 (lnd);
 316     }
 317   lnd->cpos++;
 318
 319   lnd->numfile_orig = lnd->numfile;
 320   lnd->cpos = lnd->init = lnd->end;
 321   lnd->end = debug_line + lnd_length + (dwarf_size_64 ? 12 : 4);
 322
 323   init_state (&lnd->cur);
 324
 325   return lnd;
 326
 327  error:
 328   line_free (lnd);
 329   return NULL;
 330 }
 331
 332 /* Reset back to the beginning.  */
 333 void
 334 line_reset (struct line_reader_data * lnd)
 335 {
 336   lnd->cpos = lnd->init;
 337   lnd->numfile = lnd->numfile_orig;
 338   init_state (&lnd->cur);
 339 }
 340
 341 /* Is there no more line data available?  */
 342 int
 343 line_at_eof (struct line_reader_data * lnd)
 344 {
 345   return lnd->cpos == lnd->end;
 346 }
 347
 348 static const bool verbose = false;
 349
 350 static bool
 351 next_state (struct line_reader_data *lnd)
 352 {
 353   if (lnd->cur.end_of_sequence)
 354     init_state (&lnd->cur);
 355
 356   for (;;)
 357     {
 358       uint8_t op;
 359       uint64_t tmp;
 360
 361       if (lnd->cpos == lnd->end)
 362         return false;
 363       op = *lnd->cpos++;
 364       if (op >= lnd->opcode_base)
 365         {
 366           op -= lnd->opcode_base;
 367
 368           lnd->cur.line += op % lnd->line_range + lnd->line_base;
 369           lnd->cur.pc += (op / lnd->line_range
 370                           * lnd->minimum_instruction_length);
 371           return true;
 372         }
 373       else switch (op)
 374         {
 375         case DW_LNS_extended_op:
 376           {
 377             uint64_t sz = read_uleb128 (lnd);
 378             const uint8_t * eop = lnd->cpos;
 379
 380             if ((uint64_t)(lnd->end - eop) < sz || sz == 0)
 381               return false;
 382             lnd->cpos += sz;
 383             switch (*eop++)
 384               {
 385               case DW_LNE_end_sequence:
 386               if (verbose) fprintf(stderr, "DW_LNE_end_sequence\n");
 387                 lnd->cur.end_of_sequence = true;
 388                 return true;
 389
 390               case DW_LNE_set_address:
 391                 if (sz == 9) {
 392                   lnd->cur.pc = read_64 (eop);
 393                   if (verbose) fprintf(stderr, "DW_LNE_set_address(0x%08llX)\n", lnd->cur.pc);
 394                 }
 395                 else if (sz == 5) {
 396                   lnd->cur.pc = read_32 (eop);
 397                   if (verbose) fprintf(stderr, "DW_LNE_set_address(0x%08llX)\n", lnd->cur.pc);
 398                 }
 399                 else
 400                   return false;
 401                 break;
 402
 403               case DW_LNE_define_file:
 404                 {
 405                   if (verbose) fprintf(stderr, "DW_LNE_define_file\n");
 406                   const uint8_t * * filenames;
 407                   filenames = realloc
 408                     (lnd->filenames,
 409                      (lnd->numfile + 1) * sizeof (const uint8_t *));
 410                   if (! filenames)
 411                     return false;
 412                   /* Check for zero-termination.  */
 413                   if (! memchr (eop, 0, lnd->cpos - eop))
 414                     return false;
 415                   filenames[lnd->numfile++] = eop;
 416                   lnd->filenames = filenames;
 417
 418                   /* There's other data here, like file sizes and modification
 419                      times, but we don't need to read it so skip it.  */
 420                 }
 421                 break;
 422
 423               default:
 424                 /* Don't understand it, so skip it.  */
 425                 if (verbose) fprintf(stderr, "DW_LNS_extended_op unknown\n");
 426                 break;
 427               }
 428             break;
 429           }
 430
 431         case DW_LNS_copy:
 432           if (verbose) fprintf(stderr, "DW_LNS_copy\n");
 433           return true;
 434         case DW_LNS_advance_pc:
 435           tmp = read_uleb128 (lnd);
 436           if (tmp == (uint64_t) -1)
 437             return false;
 438           lnd->cur.pc += tmp * lnd->minimum_instruction_length;
 439           if (verbose) fprintf(stderr, "DW_LNS_advance_pc(0x%08llX)\n", lnd->cur.pc);
 440           break;
 441         case DW_LNS_advance_line:
 442           lnd->cur.line += read_sleb128 (lnd);
 443           if (verbose) fprintf(stderr, "DW_LNS_advance_line(%lld)\n", lnd->cur.line);
 444           break;
 445         case DW_LNS_set_file:
 446           if (verbose) fprintf(stderr, "DW_LNS_set_file\n");
 447           lnd->cur.file = read_uleb128 (lnd);
 448           break;
 449         case DW_LNS_set_column:
 450           if (verbose) fprintf(stderr, "DW_LNS_set_column\n");
 451           lnd->cur.col = read_uleb128 (lnd);
 452           break;
 453         case DW_LNS_const_add_pc:
 454           if (verbose) fprintf(stderr, "DW_LNS_const_add_pc\n");
 455           lnd->cur.pc += ((255 - lnd->opcode_base) / lnd->line_range
 456                           * lnd->minimum_instruction_length);
 457           break;
 458         case DW_LNS_fixed_advance_pc:
 459           if (verbose) fprintf(stderr, "DW_LNS_fixed_advance_pc\n");
 460           if (lnd->end - lnd->cpos < 2)
 461             return false;
 462           lnd->cur.pc += read_16 (lnd->cpos);
 463           lnd->cpos += 2;
 464           break;
 465         default:
 466           {
 467             /* Don't know what it is, so skip it.  */
 468             if (verbose) fprintf(stderr, "unknown opcode\n");
 469             int i;
 470             for (i = 0; i < lnd->standard_opcode_lengths[op - 1]; i++)
 471               skip_leb128 (lnd);
 472             break;
 473           }
 474         }
 475     }
 476 }
 477
 478
 479 /* Set RESULT to the next 'interesting' line state, as indicated
 480    by STOP, or return FALSE on error.  The final (end-of-sequence)
 481    line state is always considered interesting.  */
 482 int
 483 line_next (struct line_reader_data * lnd,
 484            struct line_info * result,
 485            enum line_stop_constants stop)
 486 {
 487   for (;;)
 488     {
 489       struct line_info prev = lnd->cur;
 490
 491       if (! next_state (lnd))
 492         return false;
 493
 494       if (lnd->cur.end_of_sequence)
 495         break;
 496       if (stop == line_stop_always)
 497         break;
 498       if ((stop & line_stop_pc) && lnd->cur.pc != prev.pc)
 499         break;
 500       if ((stop & line_stop_pos_mask) && lnd->cur.file != prev.file)
 501         break;
 502       if ((stop & line_stop_pos_mask) >= line_stop_line
 503           && lnd->cur.line != prev.line)
 504         break;
 505       if ((stop & line_stop_pos_mask) >= line_stop_col
 506           && lnd->cur.col != prev.col)
 507         break;
 508     }
 509   *result = lnd->cur;
 510   return true;
 511 }
 512
 513 /* Find the region (START->pc through END->pc) in the debug_line
 514    information which contains PC.  This routine starts searching at
 515    the current position (which is returned as END), and will go all
 516    the way around the debug_line information.  It will return false if
 517    an error occurs or if there is no matching region; these may be
 518    distinguished by looking at START->end_of_sequence, which will be
 519    false on error and true if there was no matching region.
 520    You could write this routine using line_next, but this version
 521    will be slightly more efficient, and of course more convenient.  */
 522
 523 int
 524 line_find_addr (struct line_reader_data * lnd,
 525                 struct line_info * start,
 526                 struct line_info * end,
 527                 uint64_t pc)
 528 {
 529   const uint8_t * startpos;
 530   struct line_info prev;
 531
 532   if (lnd->cur.end_of_sequence && lnd->cpos == lnd->end)
 533     line_reset (lnd);
 534
 535   startpos = lnd->cpos;
 536
 537   do {
 538     prev = lnd->cur;
 539     if (! next_state (lnd))
 540       {
 541         start->end_of_sequence = false;
 542         return false;
 543       }
 544     if (lnd->cur.end_of_sequence && lnd->cpos == lnd->end)
 545       line_reset (lnd);
 546     if (lnd->cpos == startpos)
 547       {
 548         start->end_of_sequence = true;
 549         return false;
 550       }
 551   } while (lnd->cur.pc <= pc || prev.pc > pc || prev.end_of_sequence);
 552   *start = prev;
 553   *end = lnd->cur;
 554   return true;
 555 }
 556 #endif /* ! KLD */
 557