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