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