2013-05-31 Janus Weil <janus@gcc.gnu.org>
[official-gcc.git] / libbacktrace / dwarf.c
blob501afe553d203486735a4645dc80689f03e86b8d
1 /* dwarf.c -- Get file/line information from DWARF for backtraces.
2 Copyright (C) 2012-2013 Free Software Foundation, Inc.
3 Written by Ian Lance Taylor, Google.
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are
7 met:
9 (1) Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
12 (2) Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in
14 the documentation and/or other materials provided with the
15 distribution.
17 (3) The name of the author may not be used to
18 endorse or promote products derived from this software without
19 specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
25 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
29 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
30 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 POSSIBILITY OF SUCH DAMAGE. */
33 #include "config.h"
35 #include <errno.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <sys/types.h>
40 #include "dwarf2.h"
41 #include "filenames.h"
43 #include "backtrace.h"
44 #include "internal.h"
46 #if !defined(HAVE_DECL_STRNLEN) || !HAVE_DECL_STRNLEN
48 /* If strnlen is not declared, provide our own version. */
50 static size_t
51 xstrnlen (const char *s, size_t maxlen)
53 size_t i;
55 for (i = 0; i < maxlen; ++i)
56 if (s[i] == '\0')
57 break;
58 return i;
61 #define strnlen xstrnlen
63 #endif
65 /* A buffer to read DWARF info. */
67 struct dwarf_buf
69 /* Buffer name for error messages. */
70 const char *name;
71 /* Start of the buffer. */
72 const unsigned char *start;
73 /* Next byte to read. */
74 const unsigned char *buf;
75 /* The number of bytes remaining. */
76 size_t left;
77 /* Whether the data is big-endian. */
78 int is_bigendian;
79 /* Error callback routine. */
80 backtrace_error_callback error_callback;
81 /* Data for error_callback. */
82 void *data;
83 /* Non-zero if we've reported an underflow error. */
84 int reported_underflow;
87 /* A single attribute in a DWARF abbreviation. */
89 struct attr
91 /* The attribute name. */
92 enum dwarf_attribute name;
93 /* The attribute form. */
94 enum dwarf_form form;
97 /* A single DWARF abbreviation. */
99 struct abbrev
101 /* The abbrev code--the number used to refer to the abbrev. */
102 uint64_t code;
103 /* The entry tag. */
104 enum dwarf_tag tag;
105 /* Non-zero if this abbrev has child entries. */
106 int has_children;
107 /* The number of attributes. */
108 size_t num_attrs;
109 /* The attributes. */
110 struct attr *attrs;
113 /* The DWARF abbreviations for a compilation unit. This structure
114 only exists while reading the compilation unit. Most DWARF readers
115 seem to a hash table to map abbrev ID's to abbrev entries.
116 However, we primarily care about GCC, and GCC simply issues ID's in
117 numerical order starting at 1. So we simply keep a sorted vector,
118 and try to just look up the code. */
120 struct abbrevs
122 /* The number of abbrevs in the vector. */
123 size_t num_abbrevs;
124 /* The abbrevs, sorted by the code field. */
125 struct abbrev *abbrevs;
128 /* The different kinds of attribute values. */
130 enum attr_val_encoding
132 /* An address. */
133 ATTR_VAL_ADDRESS,
134 /* A unsigned integer. */
135 ATTR_VAL_UINT,
136 /* A sigd integer. */
137 ATTR_VAL_SINT,
138 /* A string. */
139 ATTR_VAL_STRING,
140 /* An offset to other data in the containing unit. */
141 ATTR_VAL_REF_UNIT,
142 /* An offset to other data within the .dwarf_info section. */
143 ATTR_VAL_REF_INFO,
144 /* An offset to data in some other section. */
145 ATTR_VAL_REF_SECTION,
146 /* A type signature. */
147 ATTR_VAL_REF_TYPE,
148 /* A block of data (not represented). */
149 ATTR_VAL_BLOCK,
150 /* An expression (not represented). */
151 ATTR_VAL_EXPR,
154 /* An attribute value. */
156 struct attr_val
158 /* How the value is stored in the field u. */
159 enum attr_val_encoding encoding;
160 union
162 /* ATTR_VAL_ADDRESS, ATTR_VAL_UINT, ATTR_VAL_REF*. */
163 uint64_t uint;
164 /* ATTR_VAL_SINT. */
165 int64_t sint;
166 /* ATTR_VAL_STRING. */
167 const char *string;
168 /* ATTR_VAL_BLOCK not stored. */
169 } u;
172 /* The line number program header. */
174 struct line_header
176 /* The version of the line number information. */
177 int version;
178 /* The minimum instruction length. */
179 unsigned int min_insn_len;
180 /* The maximum number of ops per instruction. */
181 unsigned int max_ops_per_insn;
182 /* The line base for special opcodes. */
183 int line_base;
184 /* The line range for special opcodes. */
185 unsigned int line_range;
186 /* The opcode base--the first special opcode. */
187 unsigned int opcode_base;
188 /* Opcode lengths, indexed by opcode - 1. */
189 const unsigned char *opcode_lengths;
190 /* The number of directory entries. */
191 size_t dirs_count;
192 /* The directory entries. */
193 const char **dirs;
194 /* The number of filenames. */
195 size_t filenames_count;
196 /* The filenames. */
197 const char **filenames;
200 /* Map a single PC value to a file/line. We will keep a vector of
201 these sorted by PC value. Each file/line will be correct from the
202 PC up to the PC of the next entry if there is one. We allocate one
203 extra entry at the end so that we can use bsearch. */
205 struct line
207 /* PC. */
208 uintptr_t pc;
209 /* File name. Many entries in the array are expected to point to
210 the same file name. */
211 const char *filename;
212 /* Line number. */
213 int lineno;
216 /* A growable vector of line number information. This is used while
217 reading the line numbers. */
219 struct line_vector
221 /* Memory. This is an array of struct line. */
222 struct backtrace_vector vec;
223 /* Number of valid mappings. */
224 size_t count;
227 /* A function described in the debug info. */
229 struct function
231 /* The name of the function. */
232 const char *name;
233 /* If this is an inlined function, the filename of the call
234 site. */
235 const char *caller_filename;
236 /* If this is an inlined function, the line number of the call
237 site. */
238 int caller_lineno;
239 /* Map PC ranges to inlined functions. */
240 struct function_addrs *function_addrs;
241 size_t function_addrs_count;
244 /* An address range for a function. This maps a PC value to a
245 specific function. */
247 struct function_addrs
249 /* Range is LOW <= PC < HIGH. */
250 uint64_t low;
251 uint64_t high;
252 /* Function for this address range. */
253 struct function *function;
256 /* A growable vector of function address ranges. */
258 struct function_vector
260 /* Memory. This is an array of struct function_addrs. */
261 struct backtrace_vector vec;
262 /* Number of address ranges present. */
263 size_t count;
266 /* A DWARF compilation unit. This only holds the information we need
267 to map a PC to a file and line. */
269 struct unit
271 /* The first entry for this compilation unit. */
272 const unsigned char *unit_data;
273 /* The length of the data for this compilation unit. */
274 size_t unit_data_len;
275 /* The offset of UNIT_DATA from the start of the information for
276 this compilation unit. */
277 size_t unit_data_offset;
278 /* DWARF version. */
279 int version;
280 /* Whether unit is DWARF64. */
281 int is_dwarf64;
282 /* Address size. */
283 int addrsize;
284 /* Offset into line number information. */
285 off_t lineoff;
286 /* Primary source file. */
287 const char *filename;
288 /* Compilation command working directory. */
289 const char *comp_dir;
290 /* Absolute file name, only set if needed. */
291 const char *abs_filename;
292 /* The abbreviations for this unit. */
293 struct abbrevs abbrevs;
295 /* The fields above this point are read in during initialization and
296 may be accessed freely. The fields below this point are read in
297 as needed, and therefore require care, as different threads may
298 try to initialize them simultaneously. */
300 /* PC to line number mapping. This is NULL if the values have not
301 been read. This is (struct line *) -1 if there was an error
302 reading the values. */
303 struct line *lines;
304 /* Number of entries in lines. */
305 size_t lines_count;
306 /* PC ranges to function. */
307 struct function_addrs *function_addrs;
308 size_t function_addrs_count;
311 /* An address range for a compilation unit. This maps a PC value to a
312 specific compilation unit. Note that we invert the representation
313 in DWARF: instead of listing the units and attaching a list of
314 ranges, we list the ranges and have each one point to the unit.
315 This lets us do a binary search to find the unit. */
317 struct unit_addrs
319 /* Range is LOW <= PC < HIGH. */
320 uint64_t low;
321 uint64_t high;
322 /* Compilation unit for this address range. */
323 struct unit *u;
326 /* A growable vector of compilation unit address ranges. */
328 struct unit_addrs_vector
330 /* Memory. This is an array of struct unit_addrs. */
331 struct backtrace_vector vec;
332 /* Number of address ranges present. */
333 size_t count;
336 /* The information we need to map a PC to a file and line. */
338 struct dwarf_data
340 /* The data for the next file we know about. */
341 struct dwarf_data *next;
342 /* The base address for this file. */
343 uintptr_t base_address;
344 /* A sorted list of address ranges. */
345 struct unit_addrs *addrs;
346 /* Number of address ranges in list. */
347 size_t addrs_count;
348 /* The unparsed .debug_info section. */
349 const unsigned char *dwarf_info;
350 size_t dwarf_info_size;
351 /* The unparsed .debug_line section. */
352 const unsigned char *dwarf_line;
353 size_t dwarf_line_size;
354 /* The unparsed .debug_ranges section. */
355 const unsigned char *dwarf_ranges;
356 size_t dwarf_ranges_size;
357 /* The unparsed .debug_str section. */
358 const unsigned char *dwarf_str;
359 size_t dwarf_str_size;
360 /* Whether the data is big-endian or not. */
361 int is_bigendian;
362 /* A vector used for function addresses. We keep this here so that
363 we can grow the vector as we read more functions. */
364 struct function_vector fvec;
367 /* Report an error for a DWARF buffer. */
369 static void
370 dwarf_buf_error (struct dwarf_buf *buf, const char *msg)
372 char b[200];
374 snprintf (b, sizeof b, "%s in %s at %d",
375 msg, buf->name, (int) (buf->buf - buf->start));
376 buf->error_callback (buf->data, b, 0);
379 /* Require at least COUNT bytes in BUF. Return 1 if all is well, 0 on
380 error. */
382 static int
383 require (struct dwarf_buf *buf, size_t count)
385 if (buf->left >= count)
386 return 1;
388 if (!buf->reported_underflow)
390 dwarf_buf_error (buf, "DWARF underflow");
391 buf->reported_underflow = 1;
394 return 0;
397 /* Advance COUNT bytes in BUF. Return 1 if all is well, 0 on
398 error. */
400 static int
401 advance (struct dwarf_buf *buf, size_t count)
403 if (!require (buf, count))
404 return 0;
405 buf->buf += count;
406 buf->left -= count;
407 return 1;
410 /* Read one byte from BUF and advance 1 byte. */
412 static unsigned char
413 read_byte (struct dwarf_buf *buf)
415 const unsigned char *p = buf->buf;
417 if (!advance (buf, 1))
418 return 0;
419 return p[0];
422 /* Read a signed char from BUF and advance 1 byte. */
424 static signed char
425 read_sbyte (struct dwarf_buf *buf)
427 const unsigned char *p = buf->buf;
429 if (!advance (buf, 1))
430 return 0;
431 return (*p ^ 0x80) - 0x80;
434 /* Read a uint16 from BUF and advance 2 bytes. */
436 static uint16_t
437 read_uint16 (struct dwarf_buf *buf)
439 const unsigned char *p = buf->buf;
441 if (!advance (buf, 2))
442 return 0;
443 if (buf->is_bigendian)
444 return ((uint16_t) p[0] << 8) | (uint16_t) p[1];
445 else
446 return ((uint16_t) p[1] << 8) | (uint16_t) p[0];
449 /* Read a uint32 from BUF and advance 4 bytes. */
451 static uint32_t
452 read_uint32 (struct dwarf_buf *buf)
454 const unsigned char *p = buf->buf;
456 if (!advance (buf, 4))
457 return 0;
458 if (buf->is_bigendian)
459 return (((uint32_t) p[0] << 24) | ((uint32_t) p[1] << 16)
460 | ((uint32_t) p[2] << 8) | (uint32_t) p[3]);
461 else
462 return (((uint32_t) p[3] << 24) | ((uint32_t) p[2] << 16)
463 | ((uint32_t) p[1] << 8) | (uint32_t) p[0]);
466 /* Read a uint64 from BUF and advance 8 bytes. */
468 static uint64_t
469 read_uint64 (struct dwarf_buf *buf)
471 const unsigned char *p = buf->buf;
473 if (!advance (buf, 8))
474 return 0;
475 if (buf->is_bigendian)
476 return (((uint64_t) p[0] << 56) | ((uint64_t) p[1] << 48)
477 | ((uint64_t) p[2] << 40) | ((uint64_t) p[3] << 32)
478 | ((uint64_t) p[4] << 24) | ((uint64_t) p[5] << 16)
479 | ((uint64_t) p[6] << 8) | (uint64_t) p[7]);
480 else
481 return (((uint64_t) p[7] << 56) | ((uint64_t) p[6] << 48)
482 | ((uint64_t) p[5] << 40) | ((uint64_t) p[4] << 32)
483 | ((uint64_t) p[3] << 24) | ((uint64_t) p[2] << 16)
484 | ((uint64_t) p[1] << 8) | (uint64_t) p[0]);
487 /* Read an offset from BUF and advance the appropriate number of
488 bytes. */
490 static uint64_t
491 read_offset (struct dwarf_buf *buf, int is_dwarf64)
493 if (is_dwarf64)
494 return read_uint64 (buf);
495 else
496 return read_uint32 (buf);
499 /* Read an address from BUF and advance the appropriate number of
500 bytes. */
502 static uint64_t
503 read_address (struct dwarf_buf *buf, int addrsize)
505 switch (addrsize)
507 case 1:
508 return read_byte (buf);
509 case 2:
510 return read_uint16 (buf);
511 case 4:
512 return read_uint32 (buf);
513 case 8:
514 return read_uint64 (buf);
515 default:
516 dwarf_buf_error (buf, "unrecognized address size");
517 return 0;
521 /* Return whether a value is the highest possible address, given the
522 address size. */
524 static int
525 is_highest_address (uint64_t address, int addrsize)
527 switch (addrsize)
529 case 1:
530 return address == (unsigned char) -1;
531 case 2:
532 return address == (uint16_t) -1;
533 case 4:
534 return address == (uint32_t) -1;
535 case 8:
536 return address == (uint64_t) -1;
537 default:
538 return 0;
542 /* Read an unsigned LEB128 number. */
544 static uint64_t
545 read_uleb128 (struct dwarf_buf *buf)
547 uint64_t ret;
548 unsigned int shift;
549 int overflow;
550 unsigned char b;
552 ret = 0;
553 shift = 0;
554 overflow = 0;
557 const unsigned char *p;
559 p = buf->buf;
560 if (!advance (buf, 1))
561 return 0;
562 b = *p;
563 if (shift < 64)
564 ret |= ((uint64_t) (b & 0x7f)) << shift;
565 else if (!overflow)
567 dwarf_buf_error (buf, "LEB128 overflows uint64_t");
568 overflow = 1;
570 shift += 7;
572 while ((b & 0x80) != 0);
574 return ret;
577 /* Read a signed LEB128 number. */
579 static int64_t
580 read_sleb128 (struct dwarf_buf *buf)
582 uint64_t val;
583 unsigned int shift;
584 int overflow;
585 unsigned char b;
587 val = 0;
588 shift = 0;
589 overflow = 0;
592 const unsigned char *p;
594 p = buf->buf;
595 if (!advance (buf, 1))
596 return 0;
597 b = *p;
598 if (shift < 64)
599 val |= ((uint64_t) (b & 0x7f)) << shift;
600 else if (!overflow)
602 dwarf_buf_error (buf, "signed LEB128 overflows uint64_t");
603 overflow = 1;
605 shift += 7;
607 while ((b & 0x80) != 0);
609 if ((b & 0x40) != 0 && shift < 64)
610 val |= ((uint64_t) -1) << shift;
612 return (int64_t) val;
615 /* Return the length of an LEB128 number. */
617 static size_t
618 leb128_len (const unsigned char *p)
620 size_t ret;
622 ret = 1;
623 while ((*p & 0x80) != 0)
625 ++p;
626 ++ret;
628 return ret;
631 /* Free an abbreviations structure. */
633 static void
634 free_abbrevs (struct backtrace_state *state, struct abbrevs *abbrevs,
635 backtrace_error_callback error_callback, void *data)
637 size_t i;
639 for (i = 0; i < abbrevs->num_abbrevs; ++i)
640 backtrace_free (state, abbrevs->abbrevs[i].attrs,
641 abbrevs->abbrevs[i].num_attrs * sizeof (struct attr),
642 error_callback, data);
643 backtrace_free (state, abbrevs->abbrevs,
644 abbrevs->num_abbrevs * sizeof (struct abbrev),
645 error_callback, data);
646 abbrevs->num_abbrevs = 0;
647 abbrevs->abbrevs = NULL;
650 /* Read an attribute value. Returns 1 on success, 0 on failure. If
651 the value can be represented as a uint64_t, sets *VAL and sets
652 *IS_VALID to 1. We don't try to store the value of other attribute
653 forms, because we don't care about them. */
655 static int
656 read_attribute (enum dwarf_form form, struct dwarf_buf *buf,
657 int is_dwarf64, int version, int addrsize,
658 const unsigned char *dwarf_str, size_t dwarf_str_size,
659 struct attr_val *val)
661 /* Avoid warnings about val.u.FIELD may be used uninitialized if
662 this function is inlined. The warnings aren't valid but can
663 occur because the different fields are set and used
664 conditionally. */
665 memset (val, 0, sizeof *val);
667 switch (form)
669 case DW_FORM_addr:
670 val->encoding = ATTR_VAL_ADDRESS;
671 val->u.uint = read_address (buf, addrsize);
672 return 1;
673 case DW_FORM_block2:
674 val->encoding = ATTR_VAL_BLOCK;
675 return advance (buf, read_uint16 (buf));
676 case DW_FORM_block4:
677 val->encoding = ATTR_VAL_BLOCK;
678 return advance (buf, read_uint32 (buf));
679 case DW_FORM_data2:
680 val->encoding = ATTR_VAL_UINT;
681 val->u.uint = read_uint16 (buf);
682 return 1;
683 case DW_FORM_data4:
684 val->encoding = ATTR_VAL_UINT;
685 val->u.uint = read_uint32 (buf);
686 return 1;
687 case DW_FORM_data8:
688 val->encoding = ATTR_VAL_UINT;
689 val->u.uint = read_uint64 (buf);
690 return 1;
691 case DW_FORM_string:
692 val->encoding = ATTR_VAL_STRING;
693 val->u.string = (const char *) buf->buf;
694 return advance (buf, strnlen ((const char *) buf->buf, buf->left) + 1);
695 case DW_FORM_block:
696 val->encoding = ATTR_VAL_BLOCK;
697 return advance (buf, read_uleb128 (buf));
698 case DW_FORM_block1:
699 val->encoding = ATTR_VAL_BLOCK;
700 return advance (buf, read_byte (buf));
701 case DW_FORM_data1:
702 val->encoding = ATTR_VAL_UINT;
703 val->u.uint = read_byte (buf);
704 return 1;
705 case DW_FORM_flag:
706 val->encoding = ATTR_VAL_UINT;
707 val->u.uint = read_byte (buf);
708 return 1;
709 case DW_FORM_sdata:
710 val->encoding = ATTR_VAL_SINT;
711 val->u.sint = read_sleb128 (buf);
712 return 1;
713 case DW_FORM_strp:
715 uint64_t offset;
717 offset = read_offset (buf, is_dwarf64);
718 if (offset >= dwarf_str_size)
720 dwarf_buf_error (buf, "DW_FORM_strp out of range");
721 return 0;
723 val->encoding = ATTR_VAL_STRING;
724 val->u.string = (const char *) dwarf_str + offset;
725 return 1;
727 case DW_FORM_udata:
728 val->encoding = ATTR_VAL_UINT;
729 val->u.uint = read_uleb128 (buf);
730 return 1;
731 case DW_FORM_ref_addr:
732 val->encoding = ATTR_VAL_REF_INFO;
733 if (version == 2)
734 val->u.uint = read_address (buf, addrsize);
735 else
736 val->u.uint = read_offset (buf, is_dwarf64);
737 return 1;
738 case DW_FORM_ref1:
739 val->encoding = ATTR_VAL_REF_UNIT;
740 val->u.uint = read_byte (buf);
741 return 1;
742 case DW_FORM_ref2:
743 val->encoding = ATTR_VAL_REF_UNIT;
744 val->u.uint = read_uint16 (buf);
745 return 1;
746 case DW_FORM_ref4:
747 val->encoding = ATTR_VAL_REF_UNIT;
748 val->u.uint = read_uint32 (buf);
749 return 1;
750 case DW_FORM_ref8:
751 val->encoding = ATTR_VAL_REF_UNIT;
752 val->u.uint = read_uint64 (buf);
753 return 1;
754 case DW_FORM_ref_udata:
755 val->encoding = ATTR_VAL_REF_UNIT;
756 val->u.uint = read_uleb128 (buf);
757 return 1;
758 case DW_FORM_indirect:
760 uint64_t form;
762 form = read_uleb128 (buf);
763 return read_attribute ((enum dwarf_form) form, buf, is_dwarf64,
764 version, addrsize, dwarf_str, dwarf_str_size,
765 val);
767 case DW_FORM_sec_offset:
768 val->encoding = ATTR_VAL_REF_SECTION;
769 val->u.uint = read_offset (buf, is_dwarf64);
770 return 1;
771 case DW_FORM_exprloc:
772 val->encoding = ATTR_VAL_EXPR;
773 return advance (buf, read_uleb128 (buf));
774 case DW_FORM_flag_present:
775 val->encoding = ATTR_VAL_UINT;
776 val->u.uint = 1;
777 return 1;
778 case DW_FORM_ref_sig8:
779 val->encoding = ATTR_VAL_REF_TYPE;
780 val->u.uint = read_uint64 (buf);
781 return 1;
782 case DW_FORM_GNU_addr_index:
783 val->encoding = ATTR_VAL_REF_SECTION;
784 val->u.uint = read_uleb128 (buf);
785 return 1;
786 case DW_FORM_GNU_str_index:
787 val->encoding = ATTR_VAL_REF_SECTION;
788 val->u.uint = read_uleb128 (buf);
789 return 1;
790 case DW_FORM_GNU_ref_alt:
791 val->encoding = ATTR_VAL_REF_SECTION;
792 val->u.uint = read_offset (buf, is_dwarf64);
793 return 1;
794 case DW_FORM_GNU_strp_alt:
795 val->encoding = ATTR_VAL_REF_SECTION;
796 val->u.uint = read_offset (buf, is_dwarf64);
797 return 1;
798 default:
799 dwarf_buf_error (buf, "unrecognized DWARF form");
800 return 0;
804 /* Compare function_addrs for qsort. When ranges are nested, make the
805 smallest one sort last. */
807 static int
808 function_addrs_compare (const void *v1, const void *v2)
810 const struct function_addrs *a1 = (const struct function_addrs *) v1;
811 const struct function_addrs *a2 = (const struct function_addrs *) v2;
813 if (a1->low < a2->low)
814 return -1;
815 if (a1->low > a2->low)
816 return 1;
817 if (a1->high < a2->high)
818 return 1;
819 if (a1->high > a2->high)
820 return -1;
821 return strcmp (a1->function->name, a2->function->name);
824 /* Compare a PC against a function_addrs for bsearch. Note that if
825 there are multiple ranges containing PC, which one will be returned
826 is unpredictable. We compensate for that in dwarf_fileline. */
828 static int
829 function_addrs_search (const void *vkey, const void *ventry)
831 const uintptr_t *key = (const uintptr_t *) vkey;
832 const struct function_addrs *entry = (const struct function_addrs *) ventry;
833 uintptr_t pc;
835 pc = *key;
836 if (pc < entry->low)
837 return -1;
838 else if (pc >= entry->high)
839 return 1;
840 else
841 return 0;
844 /* Add a new compilation unit address range to a vector. Returns 1 on
845 success, 0 on failure. */
847 static int
848 add_unit_addr (struct backtrace_state *state, uintptr_t base_address,
849 struct unit_addrs addrs,
850 backtrace_error_callback error_callback, void *data,
851 struct unit_addrs_vector *vec)
853 struct unit_addrs *p;
855 /* Add in the base address of the module here, so that we can look
856 up the PC directly. */
857 addrs.low += base_address;
858 addrs.high += base_address;
860 /* Try to merge with the last entry. */
861 if (vec->count > 0)
863 p = (struct unit_addrs *) vec->vec.base + (vec->count - 1);
864 if ((addrs.low == p->high || addrs.low == p->high + 1)
865 && addrs.u == p->u)
867 if (addrs.high > p->high)
868 p->high = addrs.high;
869 return 1;
873 p = ((struct unit_addrs *)
874 backtrace_vector_grow (state, sizeof (struct unit_addrs),
875 error_callback, data, &vec->vec));
876 if (p == NULL)
877 return 0;
879 *p = addrs;
880 ++vec->count;
881 return 1;
884 /* Free a unit address vector. */
886 static void
887 free_unit_addrs_vector (struct backtrace_state *state,
888 struct unit_addrs_vector *vec,
889 backtrace_error_callback error_callback, void *data)
891 struct unit_addrs *addrs;
892 size_t i;
894 addrs = (struct unit_addrs *) vec->vec.base;
895 for (i = 0; i < vec->count; ++i)
896 free_abbrevs (state, &addrs[i].u->abbrevs, error_callback, data);
899 /* Compare unit_addrs for qsort. When ranges are nested, make the
900 smallest one sort last. */
902 static int
903 unit_addrs_compare (const void *v1, const void *v2)
905 const struct unit_addrs *a1 = (const struct unit_addrs *) v1;
906 const struct unit_addrs *a2 = (const struct unit_addrs *) v2;
908 if (a1->low < a2->low)
909 return -1;
910 if (a1->low > a2->low)
911 return 1;
912 if (a1->high < a2->high)
913 return 1;
914 if (a1->high > a2->high)
915 return -1;
916 if (a1->u->lineoff < a2->u->lineoff)
917 return -1;
918 if (a1->u->lineoff > a2->u->lineoff)
919 return 1;
920 return 0;
923 /* Compare a PC against a unit_addrs for bsearch. Note that if there
924 are multiple ranges containing PC, which one will be returned is
925 unpredictable. We compensate for that in dwarf_fileline. */
927 static int
928 unit_addrs_search (const void *vkey, const void *ventry)
930 const uintptr_t *key = (const uintptr_t *) vkey;
931 const struct unit_addrs *entry = (const struct unit_addrs *) ventry;
932 uintptr_t pc;
934 pc = *key;
935 if (pc < entry->low)
936 return -1;
937 else if (pc >= entry->high)
938 return 1;
939 else
940 return 0;
943 /* Sort the line vector by PC. We want a stable sort here. We know
944 that the pointers are into the same array, so it is safe to compare
945 them directly. */
947 static int
948 line_compare (const void *v1, const void *v2)
950 const struct line *ln1 = (const struct line *) v1;
951 const struct line *ln2 = (const struct line *) v2;
953 if (ln1->pc < ln2->pc)
954 return -1;
955 else if (ln1->pc > ln2->pc)
956 return 1;
957 else if (ln1 < ln2)
958 return -1;
959 else if (ln1 > ln2)
960 return 1;
961 else
962 return 0;
965 /* Find a PC in a line vector. We always allocate an extra entry at
966 the end of the lines vector, so that this routine can safely look
967 at the next entry. Note that when there are multiple mappings for
968 the same PC value, this will return the last one. */
970 static int
971 line_search (const void *vkey, const void *ventry)
973 const uintptr_t *key = (const uintptr_t *) vkey;
974 const struct line *entry = (const struct line *) ventry;
975 uintptr_t pc;
977 pc = *key;
978 if (pc < entry->pc)
979 return -1;
980 else if (pc >= (entry + 1)->pc)
981 return 1;
982 else
983 return 0;
986 /* Sort the abbrevs by the abbrev code. This function is passed to
987 both qsort and bsearch. */
989 static int
990 abbrev_compare (const void *v1, const void *v2)
992 const struct abbrev *a1 = (const struct abbrev *) v1;
993 const struct abbrev *a2 = (const struct abbrev *) v2;
995 if (a1->code < a2->code)
996 return -1;
997 else if (a1->code > a2->code)
998 return 1;
999 else
1001 /* This really shouldn't happen. It means there are two
1002 different abbrevs with the same code, and that means we don't
1003 know which one lookup_abbrev should return. */
1004 return 0;
1008 /* Read the abbreviation table for a compilation unit. Returns 1 on
1009 success, 0 on failure. */
1011 static int
1012 read_abbrevs (struct backtrace_state *state, uint64_t abbrev_offset,
1013 const unsigned char *dwarf_abbrev, size_t dwarf_abbrev_size,
1014 int is_bigendian, backtrace_error_callback error_callback,
1015 void *data, struct abbrevs *abbrevs)
1017 struct dwarf_buf abbrev_buf;
1018 struct dwarf_buf count_buf;
1019 size_t num_abbrevs;
1021 abbrevs->num_abbrevs = 0;
1022 abbrevs->abbrevs = NULL;
1024 if (abbrev_offset >= dwarf_abbrev_size)
1026 error_callback (data, "abbrev offset out of range", 0);
1027 return 0;
1030 abbrev_buf.name = ".debug_abbrev";
1031 abbrev_buf.start = dwarf_abbrev;
1032 abbrev_buf.buf = dwarf_abbrev + abbrev_offset;
1033 abbrev_buf.left = dwarf_abbrev_size - abbrev_offset;
1034 abbrev_buf.is_bigendian = is_bigendian;
1035 abbrev_buf.error_callback = error_callback;
1036 abbrev_buf.data = data;
1037 abbrev_buf.reported_underflow = 0;
1039 /* Count the number of abbrevs in this list. */
1041 count_buf = abbrev_buf;
1042 num_abbrevs = 0;
1043 while (read_uleb128 (&count_buf) != 0)
1045 if (count_buf.reported_underflow)
1046 return 0;
1047 ++num_abbrevs;
1048 // Skip tag.
1049 read_uleb128 (&count_buf);
1050 // Skip has_children.
1051 read_byte (&count_buf);
1052 // Skip attributes.
1053 while (read_uleb128 (&count_buf) != 0)
1054 read_uleb128 (&count_buf);
1055 // Skip form of last attribute.
1056 read_uleb128 (&count_buf);
1059 if (count_buf.reported_underflow)
1060 return 0;
1062 if (num_abbrevs == 0)
1063 return 1;
1065 abbrevs->num_abbrevs = num_abbrevs;
1066 abbrevs->abbrevs = ((struct abbrev *)
1067 backtrace_alloc (state,
1068 num_abbrevs * sizeof (struct abbrev),
1069 error_callback, data));
1070 if (abbrevs->abbrevs == NULL)
1071 return 0;
1072 memset (abbrevs->abbrevs, 0, num_abbrevs * sizeof (struct abbrev));
1074 num_abbrevs = 0;
1075 while (1)
1077 uint64_t code;
1078 struct abbrev a;
1079 size_t num_attrs;
1080 struct attr *attrs;
1082 if (abbrev_buf.reported_underflow)
1083 goto fail;
1085 code = read_uleb128 (&abbrev_buf);
1086 if (code == 0)
1087 break;
1089 a.code = code;
1090 a.tag = (enum dwarf_tag) read_uleb128 (&abbrev_buf);
1091 a.has_children = read_byte (&abbrev_buf);
1093 count_buf = abbrev_buf;
1094 num_attrs = 0;
1095 while (read_uleb128 (&count_buf) != 0)
1097 ++num_attrs;
1098 read_uleb128 (&count_buf);
1101 if (num_attrs == 0)
1103 attrs = NULL;
1104 read_uleb128 (&abbrev_buf);
1105 read_uleb128 (&abbrev_buf);
1107 else
1109 attrs = ((struct attr *)
1110 backtrace_alloc (state, num_attrs * sizeof *attrs,
1111 error_callback, data));
1112 if (attrs == NULL)
1113 goto fail;
1114 num_attrs = 0;
1115 while (1)
1117 uint64_t name;
1118 uint64_t form;
1120 name = read_uleb128 (&abbrev_buf);
1121 form = read_uleb128 (&abbrev_buf);
1122 if (name == 0)
1123 break;
1124 attrs[num_attrs].name = (enum dwarf_attribute) name;
1125 attrs[num_attrs].form = (enum dwarf_form) form;
1126 ++num_attrs;
1130 a.num_attrs = num_attrs;
1131 a.attrs = attrs;
1133 abbrevs->abbrevs[num_abbrevs] = a;
1134 ++num_abbrevs;
1137 qsort (abbrevs->abbrevs, abbrevs->num_abbrevs, sizeof (struct abbrev),
1138 abbrev_compare);
1140 return 1;
1142 fail:
1143 free_abbrevs (state, abbrevs, error_callback, data);
1144 return 0;
1147 /* Return the abbrev information for an abbrev code. */
1149 static const struct abbrev *
1150 lookup_abbrev (struct abbrevs *abbrevs, uint64_t code,
1151 backtrace_error_callback error_callback, void *data)
1153 struct abbrev key;
1154 void *p;
1156 /* With GCC, where abbrevs are simply numbered in order, we should
1157 be able to just look up the entry. */
1158 if (code - 1 < abbrevs->num_abbrevs
1159 && abbrevs->abbrevs[code - 1].code == code)
1160 return &abbrevs->abbrevs[code - 1];
1162 /* Otherwise we have to search. */
1163 memset (&key, 0, sizeof key);
1164 key.code = code;
1165 p = bsearch (&key, abbrevs->abbrevs, abbrevs->num_abbrevs,
1166 sizeof (struct abbrev), abbrev_compare);
1167 if (p == NULL)
1169 error_callback (data, "invalid abbreviation code", 0);
1170 return NULL;
1172 return (const struct abbrev *) p;
1175 /* Add non-contiguous address ranges for a compilation unit. Returns
1176 1 on success, 0 on failure. */
1178 static int
1179 add_unit_ranges (struct backtrace_state *state, uintptr_t base_address,
1180 struct unit *u, uint64_t ranges, uint64_t base,
1181 int is_bigendian, const unsigned char *dwarf_ranges,
1182 size_t dwarf_ranges_size,
1183 backtrace_error_callback error_callback, void *data,
1184 struct unit_addrs_vector *addrs)
1186 struct dwarf_buf ranges_buf;
1188 if (ranges >= dwarf_ranges_size)
1190 error_callback (data, "ranges offset out of range", 0);
1191 return 0;
1194 ranges_buf.name = ".debug_ranges";
1195 ranges_buf.start = dwarf_ranges;
1196 ranges_buf.buf = dwarf_ranges + ranges;
1197 ranges_buf.left = dwarf_ranges_size - ranges;
1198 ranges_buf.is_bigendian = is_bigendian;
1199 ranges_buf.error_callback = error_callback;
1200 ranges_buf.data = data;
1201 ranges_buf.reported_underflow = 0;
1203 while (1)
1205 uint64_t low;
1206 uint64_t high;
1208 if (ranges_buf.reported_underflow)
1209 return 0;
1211 low = read_address (&ranges_buf, u->addrsize);
1212 high = read_address (&ranges_buf, u->addrsize);
1214 if (low == 0 && high == 0)
1215 break;
1217 if (is_highest_address (low, u->addrsize))
1218 base = high;
1219 else
1221 struct unit_addrs a;
1223 a.low = low + base;
1224 a.high = high + base;
1225 a.u = u;
1226 if (!add_unit_addr (state, base_address, a, error_callback, data,
1227 addrs))
1228 return 0;
1232 if (ranges_buf.reported_underflow)
1233 return 0;
1235 return 1;
1238 /* Build a mapping from address ranges to the compilation units where
1239 the line number information for that range can be found. Returns 1
1240 on success, 0 on failure. */
1242 static int
1243 build_address_map (struct backtrace_state *state, uintptr_t base_address,
1244 const unsigned char *dwarf_info, size_t dwarf_info_size,
1245 const unsigned char *dwarf_abbrev, size_t dwarf_abbrev_size,
1246 const unsigned char *dwarf_ranges, size_t dwarf_ranges_size,
1247 const unsigned char *dwarf_str, size_t dwarf_str_size,
1248 int is_bigendian, backtrace_error_callback error_callback,
1249 void *data, struct unit_addrs_vector *addrs)
1251 struct dwarf_buf info;
1252 struct abbrevs abbrevs;
1254 memset (&addrs->vec, 0, sizeof addrs->vec);
1255 addrs->count = 0;
1257 /* Read through the .debug_info section. FIXME: Should we use the
1258 .debug_aranges section? gdb and addr2line don't use it, but I'm
1259 not sure why. */
1261 info.name = ".debug_info";
1262 info.start = dwarf_info;
1263 info.buf = dwarf_info;
1264 info.left = dwarf_info_size;
1265 info.is_bigendian = is_bigendian;
1266 info.error_callback = error_callback;
1267 info.data = data;
1268 info.reported_underflow = 0;
1270 memset (&abbrevs, 0, sizeof abbrevs);
1271 while (info.left > 0)
1273 const unsigned char *unit_data_start;
1274 uint64_t len;
1275 int is_dwarf64;
1276 struct dwarf_buf unit_buf;
1277 int version;
1278 uint64_t abbrev_offset;
1279 const struct abbrev *abbrev;
1280 int addrsize;
1281 const unsigned char *unit_data;
1282 size_t unit_data_len;
1283 size_t unit_data_offset;
1284 uint64_t code;
1285 size_t i;
1286 uint64_t lowpc;
1287 int have_lowpc;
1288 uint64_t highpc;
1289 int have_highpc;
1290 int highpc_is_relative;
1291 uint64_t ranges;
1292 int have_ranges;
1293 uint64_t lineoff;
1294 int have_lineoff;
1295 const char *filename;
1296 const char *comp_dir;
1298 if (info.reported_underflow)
1299 goto fail;
1301 unit_data_start = info.buf;
1303 is_dwarf64 = 0;
1304 len = read_uint32 (&info);
1305 if (len == 0xffffffff)
1307 len = read_uint64 (&info);
1308 is_dwarf64 = 1;
1311 unit_buf = info;
1312 unit_buf.left = len;
1314 if (!advance (&info, len))
1315 goto fail;
1317 version = read_uint16 (&unit_buf);
1318 if (version < 2 || version > 4)
1320 dwarf_buf_error (&unit_buf, "unrecognized DWARF version");
1321 goto fail;
1324 abbrev_offset = read_offset (&unit_buf, is_dwarf64);
1325 if (!read_abbrevs (state, abbrev_offset, dwarf_abbrev, dwarf_abbrev_size,
1326 is_bigendian, error_callback, data, &abbrevs))
1327 goto fail;
1329 addrsize = read_byte (&unit_buf);
1331 unit_data = unit_buf.buf;
1332 unit_data_len = unit_buf.left;
1333 unit_data_offset = unit_buf.buf - unit_data_start;
1335 /* We only look at the first attribute in the compilation unit.
1336 In practice this will be a DW_TAG_compile_unit which will
1337 tell us the PC range and where to find the line number
1338 information. */
1340 code = read_uleb128 (&unit_buf);
1341 abbrev = lookup_abbrev (&abbrevs, code, error_callback, data);
1342 if (abbrev == NULL)
1343 goto fail;
1345 lowpc = 0;
1346 have_lowpc = 0;
1347 highpc = 0;
1348 have_highpc = 0;
1349 highpc_is_relative = 0;
1350 ranges = 0;
1351 have_ranges = 0;
1352 lineoff = 0;
1353 have_lineoff = 0;
1354 filename = NULL;
1355 comp_dir = NULL;
1356 for (i = 0; i < abbrev->num_attrs; ++i)
1358 struct attr_val val;
1360 if (!read_attribute (abbrev->attrs[i].form, &unit_buf, is_dwarf64,
1361 version, addrsize, dwarf_str, dwarf_str_size,
1362 &val))
1363 goto fail;
1365 switch (abbrev->attrs[i].name)
1367 case DW_AT_low_pc:
1368 if (val.encoding == ATTR_VAL_ADDRESS)
1370 lowpc = val.u.uint;
1371 have_lowpc = 1;
1373 break;
1374 case DW_AT_high_pc:
1375 if (val.encoding == ATTR_VAL_ADDRESS)
1377 highpc = val.u.uint;
1378 have_highpc = 1;
1380 else if (val.encoding == ATTR_VAL_UINT)
1382 highpc = val.u.uint;
1383 have_highpc = 1;
1384 highpc_is_relative = 1;
1386 break;
1387 case DW_AT_ranges:
1388 if (val.encoding == ATTR_VAL_UINT
1389 || val.encoding == ATTR_VAL_REF_SECTION)
1391 ranges = val.u.uint;
1392 have_ranges = 1;
1394 break;
1395 case DW_AT_stmt_list:
1396 if (val.encoding == ATTR_VAL_UINT
1397 || val.encoding == ATTR_VAL_REF_SECTION)
1399 lineoff = val.u.uint;
1400 have_lineoff = 1;
1402 break;
1403 case DW_AT_name:
1404 if (val.encoding == ATTR_VAL_STRING)
1405 filename = val.u.string;
1406 break;
1407 case DW_AT_comp_dir:
1408 if (val.encoding == ATTR_VAL_STRING)
1409 comp_dir = val.u.string;
1410 break;
1411 default:
1412 break;
1416 if (unit_buf.reported_underflow)
1417 goto fail;
1419 if (((have_lowpc && have_highpc) || have_ranges) && have_lineoff)
1421 struct unit *u;
1422 struct unit_addrs a;
1424 u = ((struct unit *)
1425 backtrace_alloc (state, sizeof *u, error_callback, data));
1426 if (u == NULL)
1427 goto fail;
1428 u->unit_data = unit_data;
1429 u->unit_data_len = unit_data_len;
1430 u->unit_data_offset = unit_data_offset;
1431 u->version = version;
1432 u->is_dwarf64 = is_dwarf64;
1433 u->addrsize = addrsize;
1434 u->filename = filename;
1435 u->comp_dir = comp_dir;
1436 u->abs_filename = NULL;
1437 u->lineoff = lineoff;
1438 u->abbrevs = abbrevs;
1439 memset (&abbrevs, 0, sizeof abbrevs);
1441 /* The actual line number mappings will be read as
1442 needed. */
1443 u->lines = NULL;
1444 u->lines_count = 0;
1445 u->function_addrs = NULL;
1446 u->function_addrs_count = 0;
1448 if (have_ranges)
1450 if (!add_unit_ranges (state, base_address, u, ranges, lowpc,
1451 is_bigendian, dwarf_ranges,
1452 dwarf_ranges_size, error_callback, data,
1453 addrs))
1455 free_abbrevs (state, &u->abbrevs, error_callback, data);
1456 backtrace_free (state, u, sizeof *u, error_callback, data);
1457 goto fail;
1460 else
1462 if (highpc_is_relative)
1463 highpc += lowpc;
1464 a.low = lowpc;
1465 a.high = highpc;
1466 a.u = u;
1468 if (!add_unit_addr (state, base_address, a, error_callback, data,
1469 addrs))
1471 free_abbrevs (state, &u->abbrevs, error_callback, data);
1472 backtrace_free (state, u, sizeof *u, error_callback, data);
1473 goto fail;
1477 else
1479 free_abbrevs (state, &abbrevs, error_callback, data);
1480 memset (&abbrevs, 0, sizeof abbrevs);
1483 if (info.reported_underflow)
1484 goto fail;
1486 return 1;
1488 fail:
1489 free_abbrevs (state, &abbrevs, error_callback, data);
1490 free_unit_addrs_vector (state, addrs, error_callback, data);
1491 return 0;
1494 /* Add a new mapping to the vector of line mappings that we are
1495 building. Returns 1 on success, 0 on failure. */
1497 static int
1498 add_line (struct backtrace_state *state, struct dwarf_data *ddata,
1499 uintptr_t pc, const char *filename, int lineno,
1500 backtrace_error_callback error_callback, void *data,
1501 struct line_vector *vec)
1503 struct line *ln;
1505 /* If we are adding the same mapping, ignore it. This can happen
1506 when using discriminators. */
1507 if (vec->count > 0)
1509 ln = (struct line *) vec->vec.base + (vec->count - 1);
1510 if (pc == ln->pc && filename == ln->filename && lineno == ln->lineno)
1511 return 1;
1514 ln = ((struct line *)
1515 backtrace_vector_grow (state, sizeof (struct line), error_callback,
1516 data, &vec->vec));
1517 if (ln == NULL)
1518 return 0;
1520 /* Add in the base address here, so that we can look up the PC
1521 directly. */
1522 ln->pc = pc + ddata->base_address;
1524 ln->filename = filename;
1525 ln->lineno = lineno;
1527 ++vec->count;
1529 return 1;
1532 /* Free the line header information. If FREE_FILENAMES is true we
1533 free the file names themselves, otherwise we leave them, as there
1534 may be line structures pointing to them. */
1536 static void
1537 free_line_header (struct backtrace_state *state, struct line_header *hdr,
1538 backtrace_error_callback error_callback, void *data)
1540 backtrace_free (state, hdr->dirs, hdr->dirs_count * sizeof (const char *),
1541 error_callback, data);
1542 backtrace_free (state, hdr->filenames,
1543 hdr->filenames_count * sizeof (char *),
1544 error_callback, data);
1547 /* Read the line header. Return 1 on success, 0 on failure. */
1549 static int
1550 read_line_header (struct backtrace_state *state, struct unit *u,
1551 int is_dwarf64, struct dwarf_buf *line_buf,
1552 struct line_header *hdr)
1554 uint64_t hdrlen;
1555 struct dwarf_buf hdr_buf;
1556 const unsigned char *p;
1557 const unsigned char *pend;
1558 size_t i;
1560 hdr->version = read_uint16 (line_buf);
1561 if (hdr->version < 2 || hdr->version > 4)
1563 dwarf_buf_error (line_buf, "unsupported line number version");
1564 return 0;
1567 hdrlen = read_offset (line_buf, is_dwarf64);
1569 hdr_buf = *line_buf;
1570 hdr_buf.left = hdrlen;
1572 if (!advance (line_buf, hdrlen))
1573 return 0;
1575 hdr->min_insn_len = read_byte (&hdr_buf);
1576 if (hdr->version < 4)
1577 hdr->max_ops_per_insn = 1;
1578 else
1579 hdr->max_ops_per_insn = read_byte (&hdr_buf);
1581 /* We don't care about default_is_stmt. */
1582 read_byte (&hdr_buf);
1584 hdr->line_base = read_sbyte (&hdr_buf);
1585 hdr->line_range = read_byte (&hdr_buf);
1587 hdr->opcode_base = read_byte (&hdr_buf);
1588 hdr->opcode_lengths = hdr_buf.buf;
1589 if (!advance (&hdr_buf, hdr->opcode_base - 1))
1590 return 0;
1592 /* Count the number of directory entries. */
1593 hdr->dirs_count = 0;
1594 p = hdr_buf.buf;
1595 pend = p + hdr_buf.left;
1596 while (p < pend && *p != '\0')
1598 p += strnlen((const char *) p, pend - p) + 1;
1599 ++hdr->dirs_count;
1602 hdr->dirs = ((const char **)
1603 backtrace_alloc (state,
1604 hdr->dirs_count * sizeof (const char *),
1605 line_buf->error_callback, line_buf->data));
1606 if (hdr->dirs == NULL)
1607 return 0;
1609 i = 0;
1610 while (*hdr_buf.buf != '\0')
1612 if (hdr_buf.reported_underflow)
1613 return 0;
1615 hdr->dirs[i] = (const char *) hdr_buf.buf;
1616 ++i;
1617 if (!advance (&hdr_buf,
1618 strnlen ((const char *) hdr_buf.buf, hdr_buf.left) + 1))
1619 return 0;
1621 if (!advance (&hdr_buf, 1))
1622 return 0;
1624 /* Count the number of file entries. */
1625 hdr->filenames_count = 0;
1626 p = hdr_buf.buf;
1627 pend = p + hdr_buf.left;
1628 while (p < pend && *p != '\0')
1630 p += strnlen ((const char *) p, pend - p) + 1;
1631 p += leb128_len (p);
1632 p += leb128_len (p);
1633 p += leb128_len (p);
1634 ++hdr->filenames_count;
1637 hdr->filenames = ((const char **)
1638 backtrace_alloc (state,
1639 hdr->filenames_count * sizeof (char *),
1640 line_buf->error_callback,
1641 line_buf->data));
1642 if (hdr->filenames == NULL)
1643 return 0;
1644 i = 0;
1645 while (*hdr_buf.buf != '\0')
1647 const char *filename;
1648 uint64_t dir_index;
1650 if (hdr_buf.reported_underflow)
1651 return 0;
1653 filename = (const char *) hdr_buf.buf;
1654 if (!advance (&hdr_buf,
1655 strnlen ((const char *) hdr_buf.buf, hdr_buf.left) + 1))
1656 return 0;
1657 dir_index = read_uleb128 (&hdr_buf);
1658 if (IS_ABSOLUTE_PATH (filename)
1659 || (dir_index == 0 && u->comp_dir == NULL))
1660 hdr->filenames[i] = filename;
1661 else
1663 const char *dir;
1664 size_t dir_len;
1665 size_t filename_len;
1666 char *s;
1668 if (dir_index == 0)
1669 dir = u->comp_dir;
1670 else if (dir_index - 1 < hdr->dirs_count)
1671 dir = hdr->dirs[dir_index - 1];
1672 else
1674 dwarf_buf_error (line_buf,
1675 ("invalid directory index in "
1676 "line number program header"));
1677 return 0;
1679 dir_len = strlen (dir);
1680 filename_len = strlen (filename);
1681 s = ((char *)
1682 backtrace_alloc (state, dir_len + filename_len + 2,
1683 line_buf->error_callback, line_buf->data));
1684 if (s == NULL)
1685 return 0;
1686 memcpy (s, dir, dir_len);
1687 /* FIXME: If we are on a DOS-based file system, and the
1688 directory or the file name use backslashes, then we
1689 should use a backslash here. */
1690 s[dir_len] = '/';
1691 memcpy (s + dir_len + 1, filename, filename_len + 1);
1692 hdr->filenames[i] = s;
1695 /* Ignore the modification time and size. */
1696 read_uleb128 (&hdr_buf);
1697 read_uleb128 (&hdr_buf);
1699 ++i;
1702 if (hdr_buf.reported_underflow)
1703 return 0;
1705 return 1;
1708 /* Read the line program, adding line mappings to VEC. Return 1 on
1709 success, 0 on failure. */
1711 static int
1712 read_line_program (struct backtrace_state *state, struct dwarf_data *ddata,
1713 struct unit *u, const struct line_header *hdr,
1714 struct dwarf_buf *line_buf, struct line_vector *vec)
1716 uint64_t address;
1717 unsigned int op_index;
1718 const char *reset_filename;
1719 const char *filename;
1720 int lineno;
1722 address = 0;
1723 op_index = 0;
1724 if (hdr->filenames_count > 0)
1725 reset_filename = hdr->filenames[0];
1726 else
1727 reset_filename = "";
1728 filename = reset_filename;
1729 lineno = 1;
1730 while (line_buf->left > 0)
1732 unsigned int op;
1734 op = read_byte (line_buf);
1735 if (op >= hdr->opcode_base)
1737 unsigned int advance;
1739 /* Special opcode. */
1740 op -= hdr->opcode_base;
1741 advance = op / hdr->line_range;
1742 address += (hdr->min_insn_len * (op_index + advance)
1743 / hdr->max_ops_per_insn);
1744 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1745 lineno += hdr->line_base + (int) (op % hdr->line_range);
1746 add_line (state, ddata, address, filename, lineno,
1747 line_buf->error_callback, line_buf->data, vec);
1749 else if (op == DW_LNS_extended_op)
1751 uint64_t len;
1753 len = read_uleb128 (line_buf);
1754 op = read_byte (line_buf);
1755 switch (op)
1757 case DW_LNE_end_sequence:
1758 /* FIXME: Should we mark the high PC here? It seems
1759 that we already have that information from the
1760 compilation unit. */
1761 address = 0;
1762 op_index = 0;
1763 filename = reset_filename;
1764 lineno = 1;
1765 break;
1766 case DW_LNE_set_address:
1767 address = read_address (line_buf, u->addrsize);
1768 break;
1769 case DW_LNE_define_file:
1771 const char *f;
1772 unsigned int dir_index;
1774 f = (const char *) line_buf->buf;
1775 if (!advance (line_buf, strnlen (f, line_buf->left) + 1))
1776 return 0;
1777 dir_index = read_uleb128 (line_buf);
1778 /* Ignore that time and length. */
1779 read_uleb128 (line_buf);
1780 read_uleb128 (line_buf);
1781 if (IS_ABSOLUTE_PATH (f))
1782 filename = f;
1783 else
1785 const char *dir;
1786 size_t dir_len;
1787 size_t f_len;
1788 char *p;
1790 if (dir_index == 0)
1791 dir = u->comp_dir;
1792 else if (dir_index - 1 < hdr->dirs_count)
1793 dir = hdr->dirs[dir_index - 1];
1794 else
1796 dwarf_buf_error (line_buf,
1797 ("invalid directory index "
1798 "in line number program"));
1799 return 0;
1801 dir_len = strlen (dir);
1802 f_len = strlen (f);
1803 p = ((char *)
1804 backtrace_alloc (state, dir_len + f_len + 2,
1805 line_buf->error_callback,
1806 line_buf->data));
1807 if (p == NULL)
1808 return 0;
1809 memcpy (p, dir, dir_len);
1810 /* FIXME: If we are on a DOS-based file system,
1811 and the directory or the file name use
1812 backslashes, then we should use a backslash
1813 here. */
1814 p[dir_len] = '/';
1815 memcpy (p + dir_len + 1, f, f_len + 1);
1816 filename = p;
1819 break;
1820 case DW_LNE_set_discriminator:
1821 /* We don't care about discriminators. */
1822 read_uleb128 (line_buf);
1823 break;
1824 default:
1825 if (!advance (line_buf, len - 1))
1826 return 0;
1827 break;
1830 else
1832 switch (op)
1834 case DW_LNS_copy:
1835 add_line (state, ddata, address, filename, lineno,
1836 line_buf->error_callback, line_buf->data, vec);
1837 break;
1838 case DW_LNS_advance_pc:
1840 uint64_t advance;
1842 advance = read_uleb128 (line_buf);
1843 address += (hdr->min_insn_len * (op_index + advance)
1844 / hdr->max_ops_per_insn);
1845 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1847 break;
1848 case DW_LNS_advance_line:
1849 lineno += (int) read_sleb128 (line_buf);
1850 break;
1851 case DW_LNS_set_file:
1853 uint64_t fileno;
1855 fileno = read_uleb128 (line_buf);
1856 if (fileno == 0)
1857 filename = "";
1858 else
1860 if (fileno - 1 >= hdr->filenames_count)
1862 dwarf_buf_error (line_buf,
1863 ("invalid file number in "
1864 "line number program"));
1865 return 0;
1867 filename = hdr->filenames[fileno - 1];
1870 break;
1871 case DW_LNS_set_column:
1872 read_uleb128 (line_buf);
1873 break;
1874 case DW_LNS_negate_stmt:
1875 break;
1876 case DW_LNS_set_basic_block:
1877 break;
1878 case DW_LNS_const_add_pc:
1880 unsigned int advance;
1882 op = 255 - hdr->opcode_base;
1883 advance = op / hdr->line_range;
1884 address += (hdr->min_insn_len * (op_index + advance)
1885 / hdr->max_ops_per_insn);
1886 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1888 break;
1889 case DW_LNS_fixed_advance_pc:
1890 address += read_uint16 (line_buf);
1891 op_index = 0;
1892 break;
1893 case DW_LNS_set_prologue_end:
1894 break;
1895 case DW_LNS_set_epilogue_begin:
1896 break;
1897 case DW_LNS_set_isa:
1898 read_uleb128 (line_buf);
1899 break;
1900 default:
1902 unsigned int i;
1904 for (i = hdr->opcode_lengths[op - 1]; i > 0; --i)
1905 read_uleb128 (line_buf);
1907 break;
1912 return 1;
1915 /* Read the line number information for a compilation unit. Returns 1
1916 on success, 0 on failure. */
1918 static int
1919 read_line_info (struct backtrace_state *state, struct dwarf_data *ddata,
1920 backtrace_error_callback error_callback, void *data,
1921 struct unit *u, struct line_header *hdr, struct line **lines,
1922 size_t *lines_count)
1924 struct line_vector vec;
1925 struct dwarf_buf line_buf;
1926 uint64_t len;
1927 int is_dwarf64;
1928 struct line *ln;
1930 memset (&vec.vec, 0, sizeof vec.vec);
1931 vec.count = 0;
1933 memset (hdr, 0, sizeof *hdr);
1935 if (u->lineoff != (off_t) (size_t) u->lineoff
1936 || (size_t) u->lineoff >= ddata->dwarf_line_size)
1938 error_callback (data, "unit line offset out of range", 0);
1939 goto fail;
1942 line_buf.name = ".debug_line";
1943 line_buf.start = ddata->dwarf_line;
1944 line_buf.buf = ddata->dwarf_line + u->lineoff;
1945 line_buf.left = ddata->dwarf_line_size - u->lineoff;
1946 line_buf.is_bigendian = ddata->is_bigendian;
1947 line_buf.error_callback = error_callback;
1948 line_buf.data = data;
1949 line_buf.reported_underflow = 0;
1951 is_dwarf64 = 0;
1952 len = read_uint32 (&line_buf);
1953 if (len == 0xffffffff)
1955 len = read_uint64 (&line_buf);
1956 is_dwarf64 = 1;
1958 line_buf.left = len;
1960 if (!read_line_header (state, u, is_dwarf64, &line_buf, hdr))
1961 goto fail;
1963 if (!read_line_program (state, ddata, u, hdr, &line_buf, &vec))
1964 goto fail;
1966 if (line_buf.reported_underflow)
1967 goto fail;
1969 if (vec.count == 0)
1971 /* This is not a failure in the sense of a generating an error,
1972 but it is a failure in that sense that we have no useful
1973 information. */
1974 goto fail;
1977 /* Allocate one extra entry at the end. */
1978 ln = ((struct line *)
1979 backtrace_vector_grow (state, sizeof (struct line), error_callback,
1980 data, &vec.vec));
1981 if (ln == NULL)
1982 goto fail;
1983 ln->pc = (uintptr_t) -1;
1984 ln->filename = NULL;
1985 ln->lineno = 0;
1987 if (!backtrace_vector_release (state, &vec.vec, error_callback, data))
1988 goto fail;
1990 ln = (struct line *) vec.vec.base;
1991 qsort (ln, vec.count, sizeof (struct line), line_compare);
1993 *lines = ln;
1994 *lines_count = vec.count;
1996 return 1;
1998 fail:
1999 vec.vec.alc += vec.vec.size;
2000 vec.vec.size = 0;
2001 backtrace_vector_release (state, &vec.vec, error_callback, data);
2002 free_line_header (state, hdr, error_callback, data);
2003 *lines = (struct line *) (uintptr_t) -1;
2004 *lines_count = 0;
2005 return 0;
2008 /* Read the name of a function from a DIE referenced by a
2009 DW_AT_abstract_origin or DW_AT_specification tag. OFFSET is within
2010 the same compilation unit. */
2012 static const char *
2013 read_referenced_name (struct dwarf_data *ddata, struct unit *u,
2014 uint64_t offset, backtrace_error_callback error_callback,
2015 void *data)
2017 struct dwarf_buf unit_buf;
2018 uint64_t code;
2019 const struct abbrev *abbrev;
2020 const char *ret;
2021 size_t i;
2023 /* OFFSET is from the start of the data for this compilation unit.
2024 U->unit_data is the data, but it starts U->unit_data_offset bytes
2025 from the beginning. */
2027 if (offset < u->unit_data_offset
2028 || offset - u->unit_data_offset >= u->unit_data_len)
2030 error_callback (data,
2031 "abstract origin or specification out of range",
2033 return NULL;
2036 offset -= u->unit_data_offset;
2038 unit_buf.name = ".debug_info";
2039 unit_buf.start = ddata->dwarf_info;
2040 unit_buf.buf = u->unit_data + offset;
2041 unit_buf.left = u->unit_data_len - offset;
2042 unit_buf.is_bigendian = ddata->is_bigendian;
2043 unit_buf.error_callback = error_callback;
2044 unit_buf.data = data;
2045 unit_buf.reported_underflow = 0;
2047 code = read_uleb128 (&unit_buf);
2048 if (code == 0)
2050 dwarf_buf_error (&unit_buf, "invalid abstract origin or specification");
2051 return NULL;
2054 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
2055 if (abbrev == NULL)
2056 return NULL;
2058 ret = NULL;
2059 for (i = 0; i < abbrev->num_attrs; ++i)
2061 struct attr_val val;
2063 if (!read_attribute (abbrev->attrs[i].form, &unit_buf,
2064 u->is_dwarf64, u->version, u->addrsize,
2065 ddata->dwarf_str, ddata->dwarf_str_size,
2066 &val))
2067 return NULL;
2069 switch (abbrev->attrs[i].name)
2071 case DW_AT_name:
2072 /* We prefer the linkage name if get one. */
2073 if (val.encoding == ATTR_VAL_STRING)
2074 ret = val.u.string;
2075 break;
2077 case DW_AT_linkage_name:
2078 case DW_AT_MIPS_linkage_name:
2079 if (val.encoding == ATTR_VAL_STRING)
2080 return val.u.string;
2081 break;
2083 case DW_AT_specification:
2084 if (abbrev->attrs[i].form == DW_FORM_ref_addr
2085 || abbrev->attrs[i].form == DW_FORM_ref_sig8)
2087 /* This refers to a specification defined in some other
2088 compilation unit. We can handle this case if we
2089 must, but it's harder. */
2090 break;
2092 if (val.encoding == ATTR_VAL_UINT
2093 || val.encoding == ATTR_VAL_REF_UNIT)
2095 const char *name;
2097 name = read_referenced_name (ddata, u, val.u.uint,
2098 error_callback, data);
2099 if (name != NULL)
2100 ret = name;
2102 break;
2104 default:
2105 break;
2109 return ret;
2112 /* Add a single range to U that maps to function. Returns 1 on
2113 success, 0 on error. */
2115 static int
2116 add_function_range (struct backtrace_state *state, struct dwarf_data *ddata,
2117 struct function *function, uint64_t lowpc, uint64_t highpc,
2118 backtrace_error_callback error_callback,
2119 void *data, struct function_vector *vec)
2121 struct function_addrs *p;
2123 /* Add in the base address here, so that we can look up the PC
2124 directly. */
2125 lowpc += ddata->base_address;
2126 highpc += ddata->base_address;
2128 if (vec->count > 0)
2130 p = (struct function_addrs *) vec->vec.base + vec->count - 1;
2131 if ((lowpc == p->high || lowpc == p->high + 1)
2132 && function == p->function)
2134 if (highpc > p->high)
2135 p->high = highpc;
2136 return 1;
2140 p = ((struct function_addrs *)
2141 backtrace_vector_grow (state, sizeof (struct function_addrs),
2142 error_callback, data, &vec->vec));
2143 if (p == NULL)
2144 return 0;
2146 p->low = lowpc;
2147 p->high = highpc;
2148 p->function = function;
2149 ++vec->count;
2150 return 1;
2153 /* Add PC ranges to U that map to FUNCTION. Returns 1 on success, 0
2154 on error. */
2156 static int
2157 add_function_ranges (struct backtrace_state *state, struct dwarf_data *ddata,
2158 struct unit *u, struct function *function,
2159 uint64_t ranges, uint64_t base,
2160 backtrace_error_callback error_callback, void *data,
2161 struct function_vector *vec)
2163 struct dwarf_buf ranges_buf;
2165 if (ranges >= ddata->dwarf_ranges_size)
2167 error_callback (data, "function ranges offset out of range", 0);
2168 return 0;
2171 ranges_buf.name = ".debug_ranges";
2172 ranges_buf.start = ddata->dwarf_ranges;
2173 ranges_buf.buf = ddata->dwarf_ranges + ranges;
2174 ranges_buf.left = ddata->dwarf_ranges_size - ranges;
2175 ranges_buf.is_bigendian = ddata->is_bigendian;
2176 ranges_buf.error_callback = error_callback;
2177 ranges_buf.data = data;
2178 ranges_buf.reported_underflow = 0;
2180 while (1)
2182 uint64_t low;
2183 uint64_t high;
2185 if (ranges_buf.reported_underflow)
2186 return 0;
2188 low = read_address (&ranges_buf, u->addrsize);
2189 high = read_address (&ranges_buf, u->addrsize);
2191 if (low == 0 && high == 0)
2192 break;
2194 if (is_highest_address (low, u->addrsize))
2195 base = high;
2196 else
2198 if (!add_function_range (state, ddata, function, low + base,
2199 high + base, error_callback, data, vec))
2200 return 0;
2204 if (ranges_buf.reported_underflow)
2205 return 0;
2207 return 1;
2210 /* Read one entry plus all its children. Add function addresses to
2211 VEC. Returns 1 on success, 0 on error. */
2213 static int
2214 read_function_entry (struct backtrace_state *state, struct dwarf_data *ddata,
2215 struct unit *u, uint64_t base, struct dwarf_buf *unit_buf,
2216 const struct line_header *lhdr,
2217 backtrace_error_callback error_callback, void *data,
2218 struct function_vector *vec)
2220 while (unit_buf->left > 0)
2222 uint64_t code;
2223 const struct abbrev *abbrev;
2224 int is_function;
2225 struct function *function;
2226 size_t i;
2227 uint64_t lowpc;
2228 int have_lowpc;
2229 uint64_t highpc;
2230 int have_highpc;
2231 int highpc_is_relative;
2232 uint64_t ranges;
2233 int have_ranges;
2235 code = read_uleb128 (unit_buf);
2236 if (code == 0)
2237 return 1;
2239 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
2240 if (abbrev == NULL)
2241 return 0;
2243 is_function = (abbrev->tag == DW_TAG_subprogram
2244 || abbrev->tag == DW_TAG_entry_point
2245 || abbrev->tag == DW_TAG_inlined_subroutine);
2247 function = NULL;
2248 if (is_function)
2250 function = ((struct function *)
2251 backtrace_alloc (state, sizeof *function,
2252 error_callback, data));
2253 if (function == NULL)
2254 return 0;
2255 memset (function, 0, sizeof *function);
2258 lowpc = 0;
2259 have_lowpc = 0;
2260 highpc = 0;
2261 have_highpc = 0;
2262 highpc_is_relative = 0;
2263 ranges = 0;
2264 have_ranges = 0;
2265 for (i = 0; i < abbrev->num_attrs; ++i)
2267 struct attr_val val;
2269 if (!read_attribute (abbrev->attrs[i].form, unit_buf,
2270 u->is_dwarf64, u->version, u->addrsize,
2271 ddata->dwarf_str, ddata->dwarf_str_size,
2272 &val))
2273 return 0;
2275 /* The compile unit sets the base address for any address
2276 ranges in the function entries. */
2277 if (abbrev->tag == DW_TAG_compile_unit
2278 && abbrev->attrs[i].name == DW_AT_low_pc
2279 && val.encoding == ATTR_VAL_ADDRESS)
2280 base = val.u.uint;
2282 if (is_function)
2284 switch (abbrev->attrs[i].name)
2286 case DW_AT_call_file:
2287 if (val.encoding == ATTR_VAL_UINT)
2289 if (val.u.uint == 0)
2290 function->caller_filename = "";
2291 else
2293 if (val.u.uint - 1 >= lhdr->filenames_count)
2295 dwarf_buf_error (unit_buf,
2296 ("invalid file number in "
2297 "DW_AT_call_file attribute"));
2298 return 0;
2300 function->caller_filename =
2301 lhdr->filenames[val.u.uint - 1];
2304 break;
2306 case DW_AT_call_line:
2307 if (val.encoding == ATTR_VAL_UINT)
2308 function->caller_lineno = val.u.uint;
2309 break;
2311 case DW_AT_abstract_origin:
2312 case DW_AT_specification:
2313 if (abbrev->attrs[i].form == DW_FORM_ref_addr
2314 || abbrev->attrs[i].form == DW_FORM_ref_sig8)
2316 /* This refers to an abstract origin defined in
2317 some other compilation unit. We can handle
2318 this case if we must, but it's harder. */
2319 break;
2321 if (val.encoding == ATTR_VAL_UINT
2322 || val.encoding == ATTR_VAL_REF_UNIT)
2324 const char *name;
2326 name = read_referenced_name (ddata, u, val.u.uint,
2327 error_callback, data);
2328 if (name != NULL)
2329 function->name = name;
2331 break;
2333 case DW_AT_name:
2334 if (val.encoding == ATTR_VAL_STRING)
2336 /* Don't override a name we found in some other
2337 way, as it will normally be more
2338 useful--e.g., this name is normally not
2339 mangled. */
2340 if (function->name == NULL)
2341 function->name = val.u.string;
2343 break;
2345 case DW_AT_linkage_name:
2346 case DW_AT_MIPS_linkage_name:
2347 if (val.encoding == ATTR_VAL_STRING)
2348 function->name = val.u.string;
2349 break;
2351 case DW_AT_low_pc:
2352 if (val.encoding == ATTR_VAL_ADDRESS)
2354 lowpc = val.u.uint;
2355 have_lowpc = 1;
2357 break;
2359 case DW_AT_high_pc:
2360 if (val.encoding == ATTR_VAL_ADDRESS)
2362 highpc = val.u.uint;
2363 have_highpc = 1;
2365 else if (val.encoding == ATTR_VAL_UINT)
2367 highpc = val.u.uint;
2368 have_highpc = 1;
2369 highpc_is_relative = 1;
2371 break;
2373 case DW_AT_ranges:
2374 if (val.encoding == ATTR_VAL_UINT
2375 || val.encoding == ATTR_VAL_REF_SECTION)
2377 ranges = val.u.uint;
2378 have_ranges = 1;
2380 break;
2382 default:
2383 break;
2388 /* If we couldn't find a name for the function, we have no use
2389 for it. */
2390 if (is_function && function->name == NULL)
2392 backtrace_free (state, function, sizeof *function,
2393 error_callback, data);
2394 is_function = 0;
2397 if (is_function)
2399 if (have_ranges)
2401 if (!add_function_ranges (state, ddata, u, function, ranges,
2402 base, error_callback, data, vec))
2403 return 0;
2405 else if (have_lowpc && have_highpc)
2407 if (highpc_is_relative)
2408 highpc += lowpc;
2409 if (!add_function_range (state, ddata, function, lowpc, highpc,
2410 error_callback, data, vec))
2411 return 0;
2413 else
2415 backtrace_free (state, function, sizeof *function,
2416 error_callback, data);
2417 is_function = 0;
2421 if (abbrev->has_children)
2423 if (!is_function)
2425 if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
2426 error_callback, data, vec))
2427 return 0;
2429 else
2431 struct function_vector fvec;
2433 /* Gather any information for inlined functions in
2434 FVEC. */
2436 memset (&fvec, 0, sizeof fvec);
2438 if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
2439 error_callback, data, &fvec))
2440 return 0;
2442 if (fvec.count > 0)
2444 struct function_addrs *faddrs;
2446 if (!backtrace_vector_release (state, &fvec.vec,
2447 error_callback, data))
2448 return 0;
2450 faddrs = (struct function_addrs *) fvec.vec.base;
2451 qsort (faddrs, fvec.count,
2452 sizeof (struct function_addrs),
2453 function_addrs_compare);
2455 function->function_addrs = faddrs;
2456 function->function_addrs_count = fvec.count;
2462 return 1;
2465 /* Read function name information for a compilation unit. We look
2466 through the whole unit looking for function tags. */
2468 static void
2469 read_function_info (struct backtrace_state *state, struct dwarf_data *ddata,
2470 const struct line_header *lhdr,
2471 backtrace_error_callback error_callback, void *data,
2472 struct unit *u, struct function_vector *fvec,
2473 struct function_addrs **ret_addrs,
2474 size_t *ret_addrs_count)
2476 struct function_vector lvec;
2477 struct function_vector *pfvec;
2478 struct dwarf_buf unit_buf;
2479 struct function_addrs *addrs;
2480 size_t addrs_count;
2482 /* Use FVEC if it is not NULL. Otherwise use our own vector. */
2483 if (fvec != NULL)
2484 pfvec = fvec;
2485 else
2487 memset (&lvec, 0, sizeof lvec);
2488 pfvec = &lvec;
2491 unit_buf.name = ".debug_info";
2492 unit_buf.start = ddata->dwarf_info;
2493 unit_buf.buf = u->unit_data;
2494 unit_buf.left = u->unit_data_len;
2495 unit_buf.is_bigendian = ddata->is_bigendian;
2496 unit_buf.error_callback = error_callback;
2497 unit_buf.data = data;
2498 unit_buf.reported_underflow = 0;
2500 while (unit_buf.left > 0)
2502 if (!read_function_entry (state, ddata, u, 0, &unit_buf, lhdr,
2503 error_callback, data, pfvec))
2504 return;
2507 if (pfvec->count == 0)
2508 return;
2510 addrs = (struct function_addrs *) pfvec->vec.base;
2511 addrs_count = pfvec->count;
2513 if (fvec == NULL)
2515 if (!backtrace_vector_release (state, &lvec.vec, error_callback, data))
2516 return;
2518 else
2520 /* Finish this list of addresses, but leave the remaining space in
2521 the vector available for the next function unit. */
2522 backtrace_vector_finish (state, &fvec->vec);
2523 fvec->count = 0;
2526 qsort (addrs, addrs_count, sizeof (struct function_addrs),
2527 function_addrs_compare);
2529 *ret_addrs = addrs;
2530 *ret_addrs_count = addrs_count;
2533 /* See if PC is inlined in FUNCTION. If it is, print out the inlined
2534 information, and update FILENAME and LINENO for the caller.
2535 Returns whatever CALLBACK returns, or 0 to keep going. */
2537 static int
2538 report_inlined_functions (uintptr_t pc, struct function *function,
2539 backtrace_full_callback callback, void *data,
2540 const char **filename, int *lineno)
2542 struct function_addrs *function_addrs;
2543 struct function *inlined;
2544 int ret;
2546 if (function->function_addrs_count == 0)
2547 return 0;
2549 function_addrs = ((struct function_addrs *)
2550 bsearch (&pc, function->function_addrs,
2551 function->function_addrs_count,
2552 sizeof (struct function_addrs),
2553 function_addrs_search));
2554 if (function_addrs == NULL)
2555 return 0;
2557 while (((size_t) (function_addrs - function->function_addrs) + 1
2558 < function->function_addrs_count)
2559 && pc >= (function_addrs + 1)->low
2560 && pc < (function_addrs + 1)->high)
2561 ++function_addrs;
2563 /* We found an inlined call. */
2565 inlined = function_addrs->function;
2567 /* Report any calls inlined into this one. */
2568 ret = report_inlined_functions (pc, inlined, callback, data,
2569 filename, lineno);
2570 if (ret != 0)
2571 return ret;
2573 /* Report this inlined call. */
2574 ret = callback (data, pc, *filename, *lineno, inlined->name);
2575 if (ret != 0)
2576 return ret;
2578 /* Our caller will report the caller of the inlined function; tell
2579 it the appropriate filename and line number. */
2580 *filename = inlined->caller_filename;
2581 *lineno = inlined->caller_lineno;
2583 return 0;
2586 /* Look for a PC in the DWARF mapping for one module. On success,
2587 call CALLBACK and return whatever it returns. On error, call
2588 ERROR_CALLBACK and return 0. Sets *FOUND to 1 if the PC is found,
2589 0 if not. */
2591 static int
2592 dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata,
2593 uintptr_t pc, backtrace_full_callback callback,
2594 backtrace_error_callback error_callback, void *data,
2595 int *found)
2597 struct unit_addrs *entry;
2598 struct unit *u;
2599 int new_data;
2600 struct line *lines;
2601 struct line *ln;
2602 struct function_addrs *function_addrs;
2603 struct function *function;
2604 const char *filename;
2605 int lineno;
2606 int ret;
2608 *found = 1;
2610 /* Find an address range that includes PC. */
2611 entry = bsearch (&pc, ddata->addrs, ddata->addrs_count,
2612 sizeof (struct unit_addrs), unit_addrs_search);
2614 if (entry == NULL)
2616 *found = 0;
2617 return 0;
2620 /* If there are multiple ranges that contain PC, use the last one,
2621 in order to produce predictable results. If we assume that all
2622 ranges are properly nested, then the last range will be the
2623 smallest one. */
2624 while ((size_t) (entry - ddata->addrs) + 1 < ddata->addrs_count
2625 && pc >= (entry + 1)->low
2626 && pc < (entry + 1)->high)
2627 ++entry;
2629 /* We need the lines, lines_count, function_addrs,
2630 function_addrs_count fields of u. If they are not set, we need
2631 to set them. When running in threaded mode, we need to allow for
2632 the possibility that some other thread is setting them
2633 simultaneously. */
2635 u = entry->u;
2636 lines = u->lines;
2638 /* Skip units with no useful line number information by walking
2639 backward. Useless line number information is marked by setting
2640 lines == -1. */
2641 while (entry > ddata->addrs
2642 && pc >= (entry - 1)->low
2643 && pc < (entry - 1)->high)
2645 if (state->threaded)
2647 /* Use __sync_bool_compare_and_swap to do a
2648 load-acquire. */
2649 while (!__sync_bool_compare_and_swap (&u->lines, lines, lines))
2650 lines = u->lines;
2653 if (lines != (struct line *) (uintptr_t) -1)
2654 break;
2656 --entry;
2658 u = entry->u;
2659 lines = u->lines;
2662 /* Do a load-acquire of u->lines. */
2663 if (state->threaded)
2665 /* Use __sync_bool_compare_and_swap to do an atomic load. */
2666 while (!__sync_bool_compare_and_swap (&u->lines, lines, lines))
2667 lines = u->lines;
2670 new_data = 0;
2671 if (lines == NULL)
2673 size_t function_addrs_count;
2674 struct line_header lhdr;
2675 size_t count;
2677 /* We have never read the line information for this unit. Read
2678 it now. */
2680 function_addrs = NULL;
2681 function_addrs_count = 0;
2682 if (read_line_info (state, ddata, error_callback, data, entry->u, &lhdr,
2683 &lines, &count))
2685 struct function_vector *pfvec;
2687 /* If not threaded, reuse DDATA->FVEC for better memory
2688 consumption. */
2689 if (state->threaded)
2690 pfvec = NULL;
2691 else
2692 pfvec = &ddata->fvec;
2693 read_function_info (state, ddata, &lhdr, error_callback, data,
2694 entry->u, pfvec, &function_addrs,
2695 &function_addrs_count);
2696 free_line_header (state, &lhdr, error_callback, data);
2697 new_data = 1;
2700 /* Atomically store the information we just read into the unit.
2701 If another thread is simultaneously writing, it presumably
2702 read the same information, and we don't care which one we
2703 wind up with; we just leak the other one. We do have to
2704 write the lines field last, so that the acquire-loads above
2705 ensure that the other fields are set. */
2707 if (!state->threaded)
2709 u->lines_count = count;
2710 u->function_addrs = function_addrs;
2711 u->function_addrs_count = function_addrs_count;
2712 u->lines = lines;
2714 else
2716 __sync_bool_compare_and_swap (&u->lines_count, 0, count);
2717 __sync_bool_compare_and_swap (&u->function_addrs, NULL,
2718 function_addrs);
2719 __sync_bool_compare_and_swap (&u->function_addrs_count, 0,
2720 function_addrs_count);
2721 __sync_bool_compare_and_swap (&u->lines, NULL, lines);
2725 /* Now all fields of U have been initialized. */
2727 if (lines == (struct line *) (uintptr_t) -1)
2729 /* If reading the line number information failed in some way,
2730 try again to see if there is a better compilation unit for
2731 this PC. */
2732 if (new_data)
2733 return dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2734 data, found);
2735 return callback (data, pc, NULL, 0, NULL);
2738 /* Search for PC within this unit. */
2740 ln = (struct line *) bsearch (&pc, lines, entry->u->lines_count,
2741 sizeof (struct line), line_search);
2742 if (ln == NULL)
2744 /* The PC is between the low_pc and high_pc attributes of the
2745 compilation unit, but no entry in the line table covers it.
2746 This implies that the start of the compilation unit has no
2747 line number information. */
2749 if (entry->u->abs_filename == NULL)
2751 const char *filename;
2753 filename = entry->u->filename;
2754 if (filename != NULL
2755 && !IS_ABSOLUTE_PATH (filename)
2756 && entry->u->comp_dir != NULL)
2758 size_t filename_len;
2759 const char *dir;
2760 size_t dir_len;
2761 char *s;
2763 filename_len = strlen (filename);
2764 dir = entry->u->comp_dir;
2765 dir_len = strlen (dir);
2766 s = (char *) backtrace_alloc (state, dir_len + filename_len + 2,
2767 error_callback, data);
2768 if (s == NULL)
2770 *found = 0;
2771 return 0;
2773 memcpy (s, dir, dir_len);
2774 /* FIXME: Should use backslash if DOS file system. */
2775 s[dir_len] = '/';
2776 memcpy (s + dir_len + 1, filename, filename_len + 1);
2777 filename = s;
2779 entry->u->abs_filename = filename;
2782 return callback (data, pc, entry->u->abs_filename, 0, NULL);
2785 /* Search for function name within this unit. */
2787 if (entry->u->function_addrs_count == 0)
2788 return callback (data, pc, ln->filename, ln->lineno, NULL);
2790 function_addrs = ((struct function_addrs *)
2791 bsearch (&pc, entry->u->function_addrs,
2792 entry->u->function_addrs_count,
2793 sizeof (struct function_addrs),
2794 function_addrs_search));
2795 if (function_addrs == NULL)
2796 return callback (data, pc, ln->filename, ln->lineno, NULL);
2798 /* If there are multiple function ranges that contain PC, use the
2799 last one, in order to produce predictable results. */
2801 while (((size_t) (function_addrs - entry->u->function_addrs + 1)
2802 < entry->u->function_addrs_count)
2803 && pc >= (function_addrs + 1)->low
2804 && pc < (function_addrs + 1)->high)
2805 ++function_addrs;
2807 function = function_addrs->function;
2809 filename = ln->filename;
2810 lineno = ln->lineno;
2812 ret = report_inlined_functions (pc, function, callback, data,
2813 &filename, &lineno);
2814 if (ret != 0)
2815 return ret;
2817 return callback (data, pc, filename, lineno, function->name);
2821 /* Return the file/line information for a PC using the DWARF mapping
2822 we built earlier. */
2824 static int
2825 dwarf_fileline (struct backtrace_state *state, uintptr_t pc,
2826 backtrace_full_callback callback,
2827 backtrace_error_callback error_callback, void *data)
2829 struct dwarf_data *ddata;
2830 int found;
2831 int ret;
2833 if (!state->threaded)
2835 for (ddata = (struct dwarf_data *) state->fileline_data;
2836 ddata != NULL;
2837 ddata = ddata->next)
2839 ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2840 data, &found);
2841 if (ret != 0 || found)
2842 return ret;
2845 else
2847 struct dwarf_data **pp;
2849 pp = (struct dwarf_data **) (void *) &state->fileline_data;
2850 while (1)
2852 ddata = *pp;
2853 /* Atomic load. */
2854 while (!__sync_bool_compare_and_swap (pp, ddata, ddata))
2855 ddata = *pp;
2857 if (ddata == NULL)
2858 break;
2860 ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2861 data, &found);
2862 if (ret != 0 || found)
2863 return ret;
2865 pp = &ddata->next;
2869 /* FIXME: See if any libraries have been dlopen'ed. */
2871 return callback (data, pc, NULL, 0, NULL);
2874 /* Initialize our data structures from the DWARF debug info for a
2875 file. Return NULL on failure. */
2877 static struct dwarf_data *
2878 build_dwarf_data (struct backtrace_state *state,
2879 uintptr_t base_address,
2880 const unsigned char *dwarf_info,
2881 size_t dwarf_info_size,
2882 const unsigned char *dwarf_line,
2883 size_t dwarf_line_size,
2884 const unsigned char *dwarf_abbrev,
2885 size_t dwarf_abbrev_size,
2886 const unsigned char *dwarf_ranges,
2887 size_t dwarf_ranges_size,
2888 const unsigned char *dwarf_str,
2889 size_t dwarf_str_size,
2890 int is_bigendian,
2891 backtrace_error_callback error_callback,
2892 void *data)
2894 struct unit_addrs_vector addrs_vec;
2895 struct unit_addrs *addrs;
2896 size_t addrs_count;
2897 struct dwarf_data *fdata;
2899 if (!build_address_map (state, base_address, dwarf_info, dwarf_info_size,
2900 dwarf_abbrev, dwarf_abbrev_size, dwarf_ranges,
2901 dwarf_ranges_size, dwarf_str, dwarf_str_size,
2902 is_bigendian, error_callback, data, &addrs_vec))
2903 return NULL;
2905 if (!backtrace_vector_release (state, &addrs_vec.vec, error_callback, data))
2906 return NULL;
2907 addrs = (struct unit_addrs *) addrs_vec.vec.base;
2908 addrs_count = addrs_vec.count;
2909 qsort (addrs, addrs_count, sizeof (struct unit_addrs), unit_addrs_compare);
2911 fdata = ((struct dwarf_data *)
2912 backtrace_alloc (state, sizeof (struct dwarf_data),
2913 error_callback, data));
2914 if (fdata == NULL)
2915 return NULL;
2917 fdata->next = NULL;
2918 fdata->base_address = base_address;
2919 fdata->addrs = addrs;
2920 fdata->addrs_count = addrs_count;
2921 fdata->dwarf_info = dwarf_info;
2922 fdata->dwarf_info_size = dwarf_info_size;
2923 fdata->dwarf_line = dwarf_line;
2924 fdata->dwarf_line_size = dwarf_line_size;
2925 fdata->dwarf_ranges = dwarf_ranges;
2926 fdata->dwarf_ranges_size = dwarf_ranges_size;
2927 fdata->dwarf_str = dwarf_str;
2928 fdata->dwarf_str_size = dwarf_str_size;
2929 fdata->is_bigendian = is_bigendian;
2930 memset (&fdata->fvec, 0, sizeof fdata->fvec);
2932 return fdata;
2935 /* Build our data structures from the DWARF sections for a module.
2936 Set FILELINE_FN and STATE->FILELINE_DATA. Return 1 on success, 0
2937 on failure. */
2940 backtrace_dwarf_add (struct backtrace_state *state,
2941 uintptr_t base_address,
2942 const unsigned char *dwarf_info,
2943 size_t dwarf_info_size,
2944 const unsigned char *dwarf_line,
2945 size_t dwarf_line_size,
2946 const unsigned char *dwarf_abbrev,
2947 size_t dwarf_abbrev_size,
2948 const unsigned char *dwarf_ranges,
2949 size_t dwarf_ranges_size,
2950 const unsigned char *dwarf_str,
2951 size_t dwarf_str_size,
2952 int is_bigendian,
2953 backtrace_error_callback error_callback,
2954 void *data, fileline *fileline_fn)
2956 struct dwarf_data *fdata;
2958 fdata = build_dwarf_data (state, base_address, dwarf_info, dwarf_info_size,
2959 dwarf_line, dwarf_line_size, dwarf_abbrev,
2960 dwarf_abbrev_size, dwarf_ranges, dwarf_ranges_size,
2961 dwarf_str, dwarf_str_size, is_bigendian,
2962 error_callback, data);
2963 if (fdata == NULL)
2964 return 0;
2966 if (!state->threaded)
2968 struct dwarf_data **pp;
2970 for (pp = (struct dwarf_data **) (void *) &state->fileline_data;
2971 *pp != NULL;
2972 pp = &(*pp)->next)
2974 *pp = fdata;
2976 else
2978 while (1)
2980 struct dwarf_data **pp;
2982 pp = (struct dwarf_data **) (void *) &state->fileline_data;
2984 while (1)
2986 struct dwarf_data *p;
2988 /* Atomic load. */
2989 p = *pp;
2990 while (!__sync_bool_compare_and_swap (pp, p, p))
2991 p = *pp;
2993 if (p == NULL)
2994 break;
2996 pp = &p->next;
2999 if (__sync_bool_compare_and_swap (pp, NULL, fdata))
3000 break;
3004 *fileline_fn = dwarf_fileline;
3006 return 1;