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   const char * dirpath;
 156
 157   /* I'm not sure if this is actually an error.  */
 158   if (n == 0
 159       || n > lnd->numfile)
 160     return NULL;
 161
 162   filelen = strlen ((const char *)lnd->filenames[n - 1]);
 163   lnd->cpos = lnd->filenames[n - 1] + filelen + 1;
 164   dir = read_uleb128 (lnd);
 165   lnd->cpos = prev_pos;
 166   if (dir == 0
 167       || lnd->filenames[n - 1][0] == '/')
 168     return strdup ((const char *)lnd->filenames[n - 1]);
 169   else if (dir > lnd->numdir)
 170     return NULL;
 171
 172   dirpath = (const char *)lnd->dirnames[dir - 1];
 173   dirlen = strlen (dirpath);
 174   if ( dirpath[dirlen-1] == '/' )
 175     --dirlen;
 176   if ( (dirpath[dirlen-1] == '.') && (dirpath[dirlen-2] == '/') )
 177     dirlen -= 2;
 178   result = malloc (dirlen + filelen + 2);
 179   memcpy (result, dirpath, dirlen);
 180   result[dirlen] = '/';
 181   memcpy (result + dirlen + 1, lnd->filenames[n - 1], filelen);
 182   result[dirlen + 1 + filelen] = '\0';
 183   return result;
 184 }
 185
 186 /* Initialize a state S.  Return FALSE on error.  */
 187
 188 static void
 189 init_state (struct line_info *s)
 190 {
 191   s->file = 1;
 192   s->line = 1;
 193   s->col = 0;
 194   s->pc = 0;
 195   s->end_of_sequence = false;
 196 }
 197
 198 /* Read a debug_line section.  */
 199
 200 struct line_reader_data *
 201 line_open (const uint8_t * debug_line, size_t debug_line_size,
 202            int little_endian)
 203 {
 204   struct line_reader_data * lnd = NULL;
 205   bool dwarf_size_64;
 206
 207   uint64_t lnd_length, header_length;
 208   const uint8_t * table_start;
 209
 210   if (debug_line_size < 12)
 211     return NULL;
 212
 213   lnd = malloc (sizeof (struct line_reader_data));
 214   if (! lnd)
 215     return NULL;
 216   bzero(lnd, sizeof(struct line_reader_data));
 217
 218   lnd->little_endian = little_endian;
 219   lnd->cpos = debug_line;
 220
 221   lnd_length = read_32 (lnd->cpos);
 222   lnd->cpos += 4;
 223   if (lnd_length == 0xffffffff)
 224     {
 225       lnd_length = read_64 (lnd->cpos);
 226       lnd->cpos += 8;
 227       dwarf_size_64 = true;
 228     }
 229   else if (lnd_length > 0xfffffff0)
 230     /* Not a format we understand.  */
 231     goto error;
 232   else
 233     dwarf_size_64 = false;
 234
 235   if (debug_line_size < lnd_length + (dwarf_size_64 ? 12 : 4)
 236       || lnd_length < (dwarf_size_64 ? 15 : 11))
 237     /* Too small.  */
 238     goto error;
 239
 240   if (read_16 (lnd->cpos) != 2)
 241     /* Unknown line number format.  */
 242     goto error;
 243   lnd->cpos += 2;
 244
 245   header_length = dwarf_size_64 ? (uint64_t)read_64(lnd->cpos) : (uint64_t)read_32(lnd->cpos);
 246   lnd->cpos += dwarf_size_64 ? 8 : 4;
 247   if (lnd_length < header_length + (lnd->cpos - debug_line)
 248       || header_length < 7)
 249     goto error;
 250
 251   lnd->minimum_instruction_length = lnd->cpos[0];
 252   /* Ignore default_is_stmt.  */
 253   lnd->line_base = lnd->cpos[2];
 254   lnd->line_range = lnd->cpos[3];
 255   lnd->opcode_base = lnd->cpos[4];
 256
 257   if (lnd->opcode_base == 0)
 258     /* Every valid line number program must use at least opcode 0
 259        for DW_LNE_end_sequence.  */
 260     goto error;
 261
 262   lnd->standard_opcode_lengths = lnd->cpos + 5;
 263   if (header_length < (uint64_t)(5 + (lnd->opcode_base - 1)))
 264     /* Header not long enough.  */
 265     goto error;
 266   lnd->cpos += 5 + lnd->opcode_base - 1;
 267   lnd->end = debug_line + header_length + (dwarf_size_64 ? 22 : 10);
 268
 269   /* Make table of offsets to directory names.  */
 270   table_start = lnd->cpos;
 271   lnd->numdir = 0;
 272   while (lnd->cpos != lnd->end && *lnd->cpos)
 273     {
 274       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos);
 275       if (! lnd->cpos)
 276         goto error;
 277       lnd->cpos++;
 278       lnd->numdir++;
 279     }
 280   if (lnd->cpos == lnd->end)
 281     goto error;
 282   lnd->dirnames = malloc (lnd->numdir * sizeof (const uint8_t *));
 283   if (! lnd->dirnames)
 284     goto error;
 285   lnd->numdir = 0;
 286   lnd->cpos = table_start;
 287   while (*lnd->cpos)
 288     {
 289       lnd->dirnames[lnd->numdir++] = lnd->cpos;
 290       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos) + 1;
 291     }
 292   lnd->cpos++;
 293
 294   /* Make table of offsets to file entries.  */
 295   table_start = lnd->cpos;
 296   lnd->numfile = 0;
 297   while (lnd->cpos != lnd->end && *lnd->cpos)
 298     {
 299       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos);
 300       if (! lnd->cpos)
 301         goto error;
 302       lnd->cpos++;
 303       skip_leb128 (lnd);
 304       skip_leb128 (lnd);
 305       skip_leb128 (lnd);
 306       lnd->numfile++;
 307     }
 308   if (lnd->cpos == lnd->end)
 309     goto error;
 310   lnd->filenames = malloc (lnd->numfile * sizeof (const uint8_t *));
 311   if (! lnd->filenames)
 312     goto error;
 313   lnd->numfile = 0;
 314   lnd->cpos = table_start;
 315   while (*lnd->cpos)
 316     {
 317       lnd->filenames[lnd->numfile++] = lnd->cpos;
 318       lnd->cpos = memchr (lnd->cpos, 0, lnd->end - lnd->cpos) + 1;
 319       skip_leb128 (lnd);
 320       skip_leb128 (lnd);
 321       skip_leb128 (lnd);
 322     }
 323   lnd->cpos++;
 324
 325   lnd->numfile_orig = lnd->numfile;
 326   lnd->cpos = lnd->init = lnd->end;
 327   lnd->end = debug_line + lnd_length + (dwarf_size_64 ? 12 : 4);
 328
 329   init_state (&lnd->cur);
 330
 331   return lnd;
 332
 333  error:
 334   line_free (lnd);
 335   return NULL;
 336 }
 337
 338 /* Reset back to the beginning.  */
 339 void
 340 line_reset (struct line_reader_data * lnd)
 341 {
 342   lnd->cpos = lnd->init;
 343   lnd->numfile = lnd->numfile_orig;
 344   init_state (&lnd->cur);
 345 }
 346
 347 /* Is there no more line data available?  */
 348 int
 349 line_at_eof (struct line_reader_data * lnd)
 350 {
 351   return lnd->cpos == lnd->end;
 352 }
 353
 354 static const bool verbose = false;
 355
 356 static bool
 357 next_state (struct line_reader_data *lnd)
 358 {
 359   if (lnd->cur.end_of_sequence)
 360     init_state (&lnd->cur);
 361
 362   for (;;)
 363     {
 364       uint8_t op;
 365       uint64_t tmp;
 366
 367       if (lnd->cpos == lnd->end)
 368         return false;
 369       op = *lnd->cpos++;
 370       if (op >= lnd->opcode_base)
 371         {
 372           op -= lnd->opcode_base;
 373
 374           lnd->cur.line += op % lnd->line_range + lnd->line_base;
 375           lnd->cur.pc += (op / lnd->line_range
 376                           * lnd->minimum_instruction_length);
 377           return true;
 378         }
 379       else switch (op)
 380         {
 381         case DW_LNS_extended_op:
 382           {
 383             uint64_t sz = read_uleb128 (lnd);
 384             const uint8_t * eop = lnd->cpos;
 385
 386             if ((uint64_t)(lnd->end - eop) < sz || sz == 0)
 387               return false;
 388             lnd->cpos += sz;
 389             switch (*eop++)
 390               {
 391               case DW_LNE_end_sequence:
 392               if (verbose) fprintf(stderr, "DW_LNE_end_sequence\n");
 393                 lnd->cur.end_of_sequence = true;
 394                 return true;
 395
 396               case DW_LNE_set_address:
 397                 if (sz == 9) {
 398                   lnd->cur.pc = read_64 (eop);
 399                   if (verbose) fprintf(stderr, "DW_LNE_set_address(0x%08llX)\n", lnd->cur.pc);
 400                 }
 401                 else if (sz == 5) {
 402                   lnd->cur.pc = read_32 (eop);
 403                   if (verbose) fprintf(stderr, "DW_LNE_set_address(0x%08llX)\n", lnd->cur.pc);
 404                 }
 405                 else
 406                   return false;
 407                 break;
 408
 409               case DW_LNE_define_file:
 410                 {
 411                   if (verbose) fprintf(stderr, "DW_LNE_define_file\n");
 412                   const uint8_t * * filenames;
 413                   filenames = realloc
 414                     (lnd->filenames,
 415                      (lnd->numfile + 1) * sizeof (const uint8_t *));
 416                   if (! filenames)
 417                     return false;
 418                   /* Check for zero-termination.  */
 419                   if (! memchr (eop, 0, lnd->cpos - eop))
 420                     return false;
 421                   filenames[lnd->numfile++] = eop;
 422                   lnd->filenames = filenames;
 423
 424                   /* There's other data here, like file sizes and modification
 425                      times, but we don't need to read it so skip it.  */
 426                 }
 427                 break;
 428
 429               default:
 430                 /* Don't understand it, so skip it.  */
 431                 if (verbose) fprintf(stderr, "DW_LNS_extended_op unknown\n");
 432                 break;
 433               }
 434             break;
 435           }
 436
 437         case DW_LNS_copy:
 438           if (verbose) fprintf(stderr, "DW_LNS_copy\n");
 439           return true;
 440         case DW_LNS_advance_pc:
 441           tmp = read_uleb128 (lnd);
 442           if (tmp == (uint64_t) -1)
 443             return false;
 444           lnd->cur.pc += tmp * lnd->minimum_instruction_length;
 445           if (verbose) fprintf(stderr, "DW_LNS_advance_pc(0x%08llX)\n", lnd->cur.pc);
 446           break;
 447         case DW_LNS_advance_line:
 448           lnd->cur.line += read_sleb128 (lnd);
 449           if (verbose) fprintf(stderr, "DW_LNS_advance_line(%lld)\n", lnd->cur.line);
 450           break;
 451         case DW_LNS_set_file:
 452           if (verbose) fprintf(stderr, "DW_LNS_set_file\n");
 453           lnd->cur.file = read_uleb128 (lnd);
 454           break;
 455         case DW_LNS_set_column:
 456           if (verbose) fprintf(stderr, "DW_LNS_set_column\n");
 457           lnd->cur.col = read_uleb128 (lnd);
 458           break;
 459         case DW_LNS_const_add_pc:
 460           if (verbose) fprintf(stderr, "DW_LNS_const_add_pc\n");
 461           lnd->cur.pc += ((255 - lnd->opcode_base) / lnd->line_range
 462                           * lnd->minimum_instruction_length);
 463           break;
 464         case DW_LNS_fixed_advance_pc:
 465           if (verbose) fprintf(stderr, "DW_LNS_fixed_advance_pc\n");
 466           if (lnd->end - lnd->cpos < 2)
 467             return false;
 468           lnd->cur.pc += read_16 (lnd->cpos);
 469           lnd->cpos += 2;
 470           break;
 471         default:
 472           {
 473             /* Don't know what it is, so skip it.  */
 474             if (verbose) fprintf(stderr, "unknown opcode\n");
 475             int i;
 476             for (i = 0; i < lnd->standard_opcode_lengths[op - 1]; i++)
 477               skip_leb128 (lnd);
 478             break;
 479           }
 480         }
 481     }
 482 }
 483
 484
 485 /* Set RESULT to the next 'interesting' line state, as indicated
 486    by STOP, or return FALSE on error.  The final (end-of-sequence)
 487    line state is always considered interesting.  */
 488 int
 489 line_next (struct line_reader_data * lnd,
 490            struct line_info * result,
 491            enum line_stop_constants stop)
 492 {
 493   for (;;)
 494     {
 495       struct line_info prev = lnd->cur;
 496
 497       if (! next_state (lnd))
 498         return false;
 499
 500       if (lnd->cur.end_of_sequence)
 501         break;
 502       if (stop == line_stop_always)
 503         break;
 504       if ((stop & line_stop_pc) && lnd->cur.pc != prev.pc)
 505         break;
 506       if ((stop & line_stop_pos_mask) && lnd->cur.file != prev.file)
 507         break;
 508       if ((stop & line_stop_pos_mask) >= line_stop_line
 509           && lnd->cur.line != prev.line)
 510         break;
 511       if ((stop & line_stop_pos_mask) >= line_stop_col
 512           && lnd->cur.col != prev.col)
 513         break;
 514     }
 515   *result = lnd->cur;
 516   return true;
 517 }
 518
 519 /* Find the region (START->pc through END->pc) in the debug_line
 520    information which contains PC.  This routine starts searching at
 521    the current position (which is returned as END), and will go all
 522    the way around the debug_line information.  It will return false if
 523    an error occurs or if there is no matching region; these may be
 524    distinguished by looking at START->end_of_sequence, which will be
 525    false on error and true if there was no matching region.
 526    You could write this routine using line_next, but this version
 527    will be slightly more efficient, and of course more convenient.  */
 528
 529 int
 530 line_find_addr (struct line_reader_data * lnd,
 531                 struct line_info * start,
 532                 struct line_info * end,
 533                 uint64_t pc)
 534 {
 535   const uint8_t * startpos;
 536   struct line_info prev;
 537
 538   if (lnd->cur.end_of_sequence && lnd->cpos == lnd->end)
 539     line_reset (lnd);
 540
 541   startpos = lnd->cpos;
 542
 543   do {
 544     prev = lnd->cur;
 545     if (! next_state (lnd))
 546       {
 547         start->end_of_sequence = false;
 548         return false;
 549       }
 550     if (lnd->cur.end_of_sequence && lnd->cpos == lnd->end)
 551       line_reset (lnd);
 552     if (lnd->cpos == startpos)
 553       {
 554         start->end_of_sequence = true;
 555         return false;
 556       }
 557   } while (lnd->cur.pc <= pc || prev.pc > pc || prev.end_of_sequence);
 558   *start = prev;
 559   *end = lnd->cur;
 560   return true;
 561 }
 562 #endif /* ! KLD */
 563