src/ld/debugline.c

   1 /*
   2  * Copyright (c) 2005-2006 Apple Computer, 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 bool
 349 next_state (struct line_reader_data *lnd)
 350 {
 351   if (lnd->cur.end_of_sequence)
 352     init_state (&lnd->cur);
 353
 354   for (;;)
 355     {
 356       uint8_t op;
 357       uint64_t tmp;
 358
 359       if (lnd->cpos == lnd->end)
 360         return false;
 361       op = *lnd->cpos++;
 362       if (op >= lnd->opcode_base)
 363         {
 364           op -= lnd->opcode_base;
 365
 366           lnd->cur.line += op % lnd->line_range + lnd->line_base;
 367           lnd->cur.pc += (op / lnd->line_range
 368                           * lnd->minimum_instruction_length);
 369           return true;
 370         }
 371       else switch (op)
 372         {
 373         case DW_LNS_extended_op:
 374           {
 375             uint64_t sz = read_uleb128 (lnd);
 376             const uint8_t * op = lnd->cpos;
 377
 378             if ((uint64_t)(lnd->end - op) < sz || sz == 0)
 379               return false;
 380             lnd->cpos += sz;
 381             switch (*op++)
 382               {
 383               case DW_LNE_end_sequence:
 384                 lnd->cur.end_of_sequence = true;
 385                 return true;
 386
 387               case DW_LNE_set_address:
 388                 if (sz == 9)
 389                   lnd->cur.pc = read_64 (op);
 390                 else if (sz == 5)
 391                   lnd->cur.pc = read_32 (op);
 392                 else
 393                   return false;
 394                 break;
 395
 396               case DW_LNE_define_file:
 397                 {
 398                   const uint8_t * * filenames;
 399                   filenames = realloc
 400                     (lnd->filenames,
 401                      (lnd->numfile + 1) * sizeof (const uint8_t *));
 402                   if (! filenames)
 403                     return false;
 404                   /* Check for zero-termination.  */
 405                   if (! memchr (op, 0, lnd->cpos - op))
 406                     return false;
 407                   filenames[lnd->numfile++] = op;
 408                   lnd->filenames = filenames;
 409
 410                   /* There's other data here, like file sizes and modification
 411                      times, but we don't need to read it so skip it.  */
 412                 }
 413                 break;
 414
 415               default:
 416                 /* Don't understand it, so skip it.  */
 417                 break;
 418               }
 419             break;
 420           }
 421
 422         case DW_LNS_copy:
 423         //fprintf(stderr, "DW_LNS_copy\n");
 424           return true;
 425         case DW_LNS_advance_pc:
 426         //fprintf(stderr, "DW_LNS_advance_pc\n");
 427           tmp = read_uleb128 (lnd);
 428           if (tmp == (uint64_t) -1)
 429             return false;
 430           lnd->cur.pc += tmp * lnd->minimum_instruction_length;
 431           break;
 432         case DW_LNS_advance_line:
 433         //fprintf(stderr, "DW_LNS_advance_line\n");
 434           lnd->cur.line += read_sleb128 (lnd);
 435           break;
 436         case DW_LNS_set_file:
 437         //fprintf(stderr, "DW_LNS_set_file\n");
 438           lnd->cur.file = read_uleb128 (lnd);
 439           break;
 440         case DW_LNS_set_column:
 441         //fprintf(stderr, "DW_LNS_set_column\n");
 442           lnd->cur.col = read_uleb128 (lnd);
 443           break;
 444         case DW_LNS_const_add_pc:
 445         //fprintf(stderr, "DW_LNS_const_add_pc\n");
 446           lnd->cur.pc += ((255 - lnd->opcode_base) / lnd->line_range
 447                           * lnd->minimum_instruction_length);
 448           break;
 449         case DW_LNS_fixed_advance_pc:
 450         //fprintf(stderr, "DW_LNS_fixed_advance_pc\n");
 451           if (lnd->end - lnd->cpos < 2)
 452             return false;
 453           lnd->cur.pc += read_16 (lnd->cpos);
 454           lnd->cpos += 2;
 455           break;
 456         default:
 457           {
 458             /* Don't know what it is, so skip it.  */
 459             int i;
 460             for (i = 0; i < lnd->standard_opcode_lengths[op - 1]; i++)
 461               skip_leb128 (lnd);
 462             break;
 463           }
 464         }
 465     }
 466 }
 467
 468
 469 /* Set RESULT to the next 'interesting' line state, as indicated
 470    by STOP, or return FALSE on error.  The final (end-of-sequence)
 471    line state is always considered interesting.  */
 472 int
 473 line_next (struct line_reader_data * lnd,
 474            struct line_info * result,
 475            enum line_stop_constants stop)
 476 {
 477   for (;;)
 478     {
 479       struct line_info prev = lnd->cur;
 480
 481       if (! next_state (lnd))
 482         return false;
 483
 484       if (lnd->cur.end_of_sequence)
 485         break;
 486       if (stop == line_stop_always)
 487         break;
 488       if ((stop & line_stop_pc) && lnd->cur.pc != prev.pc)
 489         break;
 490       if ((stop & line_stop_pos_mask) && lnd->cur.file != prev.file)
 491         break;
 492       if ((stop & line_stop_pos_mask) >= line_stop_line
 493           && lnd->cur.line != prev.line)
 494         break;
 495       if ((stop & line_stop_pos_mask) >= line_stop_col
 496           && lnd->cur.col != prev.col)
 497         break;
 498     }
 499   *result = lnd->cur;
 500   return true;
 501 }
 502
 503 /* Find the region (START->pc through END->pc) in the debug_line
 504    information which contains PC.  This routine starts searching at
 505    the current position (which is returned as END), and will go all
 506    the way around the debug_line information.  It will return false if
 507    an error occurs or if there is no matching region; these may be
 508    distinguished by looking at START->end_of_sequence, which will be
 509    false on error and true if there was no matching region.
 510    You could write this routine using line_next, but this version
 511    will be slightly more efficient, and of course more convenient.  */
 512
 513 int
 514 line_find_addr (struct line_reader_data * lnd,
 515                 struct line_info * start,
 516                 struct line_info * end,
 517                 uint64_t pc)
 518 {
 519   const uint8_t * startpos;
 520   struct line_info prev;
 521
 522   if (lnd->cur.end_of_sequence && lnd->cpos == lnd->end)
 523     line_reset (lnd);
 524
 525   startpos = lnd->cpos;
 526
 527   do {
 528     prev = lnd->cur;
 529     if (! next_state (lnd))
 530       {
 531         start->end_of_sequence = false;
 532         return false;
 533       }
 534     if (lnd->cur.end_of_sequence && lnd->cpos == lnd->end)
 535       line_reset (lnd);
 536     if (lnd->cpos == startpos)
 537       {
 538         start->end_of_sequence = true;
 539         return false;
 540       }
 541   } while (lnd->cur.pc <= pc || prev.pc > pc || prev.end_of_sequence);
 542   *start = prev;
 543   *end = lnd->cur;
 544   return true;
 545 }
 546 #endif /* ! KLD */
 547