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