Daily bump.
[official-gcc.git] / libbacktrace / dwarf.c
blob919b568c786ce264971d7aa4db807d12ab8d624c
1 /* dwarf.c -- Get file/line information from DWARF for backtraces.
2 Copyright (C) 2012-2015 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 backtrace_qsort (abbrevs->abbrevs, abbrevs->num_abbrevs,
1138 sizeof (struct abbrev), 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 /* Find the address range covered by a compilation unit, reading from
1239 UNIT_BUF and adding values to U. Returns 1 if all data could be
1240 read, 0 if there is some error. */
1242 static int
1243 find_address_ranges (struct backtrace_state *state, uintptr_t base_address,
1244 struct dwarf_buf *unit_buf,
1245 const unsigned char *dwarf_str, size_t dwarf_str_size,
1246 const unsigned char *dwarf_ranges,
1247 size_t dwarf_ranges_size,
1248 int is_bigendian, backtrace_error_callback error_callback,
1249 void *data, struct unit *u,
1250 struct unit_addrs_vector *addrs)
1252 while (unit_buf->left > 0)
1254 uint64_t code;
1255 const struct abbrev *abbrev;
1256 uint64_t lowpc;
1257 int have_lowpc;
1258 uint64_t highpc;
1259 int have_highpc;
1260 int highpc_is_relative;
1261 uint64_t ranges;
1262 int have_ranges;
1263 size_t i;
1265 code = read_uleb128 (unit_buf);
1266 if (code == 0)
1267 return 1;
1269 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
1270 if (abbrev == NULL)
1271 return 0;
1273 lowpc = 0;
1274 have_lowpc = 0;
1275 highpc = 0;
1276 have_highpc = 0;
1277 highpc_is_relative = 0;
1278 ranges = 0;
1279 have_ranges = 0;
1280 for (i = 0; i < abbrev->num_attrs; ++i)
1282 struct attr_val val;
1284 if (!read_attribute (abbrev->attrs[i].form, unit_buf,
1285 u->is_dwarf64, u->version, u->addrsize,
1286 dwarf_str, dwarf_str_size, &val))
1287 return 0;
1289 switch (abbrev->attrs[i].name)
1291 case DW_AT_low_pc:
1292 if (val.encoding == ATTR_VAL_ADDRESS)
1294 lowpc = val.u.uint;
1295 have_lowpc = 1;
1297 break;
1299 case DW_AT_high_pc:
1300 if (val.encoding == ATTR_VAL_ADDRESS)
1302 highpc = val.u.uint;
1303 have_highpc = 1;
1305 else if (val.encoding == ATTR_VAL_UINT)
1307 highpc = val.u.uint;
1308 have_highpc = 1;
1309 highpc_is_relative = 1;
1311 break;
1313 case DW_AT_ranges:
1314 if (val.encoding == ATTR_VAL_UINT
1315 || val.encoding == ATTR_VAL_REF_SECTION)
1317 ranges = val.u.uint;
1318 have_ranges = 1;
1320 break;
1322 case DW_AT_stmt_list:
1323 if (abbrev->tag == DW_TAG_compile_unit
1324 && (val.encoding == ATTR_VAL_UINT
1325 || val.encoding == ATTR_VAL_REF_SECTION))
1326 u->lineoff = val.u.uint;
1327 break;
1329 case DW_AT_name:
1330 if (abbrev->tag == DW_TAG_compile_unit
1331 && val.encoding == ATTR_VAL_STRING)
1332 u->filename = val.u.string;
1333 break;
1335 case DW_AT_comp_dir:
1336 if (abbrev->tag == DW_TAG_compile_unit
1337 && val.encoding == ATTR_VAL_STRING)
1338 u->comp_dir = val.u.string;
1339 break;
1341 default:
1342 break;
1346 if (abbrev->tag == DW_TAG_compile_unit
1347 || abbrev->tag == DW_TAG_subprogram)
1349 if (have_ranges)
1351 if (!add_unit_ranges (state, base_address, u, ranges, lowpc,
1352 is_bigendian, dwarf_ranges,
1353 dwarf_ranges_size, error_callback,
1354 data, addrs))
1355 return 0;
1357 else if (have_lowpc && have_highpc)
1359 struct unit_addrs a;
1361 if (highpc_is_relative)
1362 highpc += lowpc;
1363 a.low = lowpc;
1364 a.high = highpc;
1365 a.u = u;
1367 if (!add_unit_addr (state, base_address, a, error_callback, data,
1368 addrs))
1369 return 0;
1372 /* If we found the PC range in the DW_TAG_compile_unit, we
1373 can stop now. */
1374 if (abbrev->tag == DW_TAG_compile_unit
1375 && (have_ranges || (have_lowpc && have_highpc)))
1376 return 1;
1379 if (abbrev->has_children)
1381 if (!find_address_ranges (state, base_address, unit_buf,
1382 dwarf_str, dwarf_str_size,
1383 dwarf_ranges, dwarf_ranges_size,
1384 is_bigendian, error_callback, data,
1385 u, addrs))
1386 return 0;
1390 return 1;
1393 /* Build a mapping from address ranges to the compilation units where
1394 the line number information for that range can be found. Returns 1
1395 on success, 0 on failure. */
1397 static int
1398 build_address_map (struct backtrace_state *state, uintptr_t base_address,
1399 const unsigned char *dwarf_info, size_t dwarf_info_size,
1400 const unsigned char *dwarf_abbrev, size_t dwarf_abbrev_size,
1401 const unsigned char *dwarf_ranges, size_t dwarf_ranges_size,
1402 const unsigned char *dwarf_str, size_t dwarf_str_size,
1403 int is_bigendian, backtrace_error_callback error_callback,
1404 void *data, struct unit_addrs_vector *addrs)
1406 struct dwarf_buf info;
1407 struct abbrevs abbrevs;
1409 memset (&addrs->vec, 0, sizeof addrs->vec);
1410 addrs->count = 0;
1412 /* Read through the .debug_info section. FIXME: Should we use the
1413 .debug_aranges section? gdb and addr2line don't use it, but I'm
1414 not sure why. */
1416 info.name = ".debug_info";
1417 info.start = dwarf_info;
1418 info.buf = dwarf_info;
1419 info.left = dwarf_info_size;
1420 info.is_bigendian = is_bigendian;
1421 info.error_callback = error_callback;
1422 info.data = data;
1423 info.reported_underflow = 0;
1425 memset (&abbrevs, 0, sizeof abbrevs);
1426 while (info.left > 0)
1428 const unsigned char *unit_data_start;
1429 uint64_t len;
1430 int is_dwarf64;
1431 struct dwarf_buf unit_buf;
1432 int version;
1433 uint64_t abbrev_offset;
1434 int addrsize;
1435 struct unit *u;
1437 if (info.reported_underflow)
1438 goto fail;
1440 unit_data_start = info.buf;
1442 is_dwarf64 = 0;
1443 len = read_uint32 (&info);
1444 if (len == 0xffffffff)
1446 len = read_uint64 (&info);
1447 is_dwarf64 = 1;
1450 unit_buf = info;
1451 unit_buf.left = len;
1453 if (!advance (&info, len))
1454 goto fail;
1456 version = read_uint16 (&unit_buf);
1457 if (version < 2 || version > 4)
1459 dwarf_buf_error (&unit_buf, "unrecognized DWARF version");
1460 goto fail;
1463 abbrev_offset = read_offset (&unit_buf, is_dwarf64);
1464 if (!read_abbrevs (state, abbrev_offset, dwarf_abbrev, dwarf_abbrev_size,
1465 is_bigendian, error_callback, data, &abbrevs))
1466 goto fail;
1468 addrsize = read_byte (&unit_buf);
1470 u = ((struct unit *)
1471 backtrace_alloc (state, sizeof *u, error_callback, data));
1472 if (u == NULL)
1473 goto fail;
1474 u->unit_data = unit_buf.buf;
1475 u->unit_data_len = unit_buf.left;
1476 u->unit_data_offset = unit_buf.buf - unit_data_start;
1477 u->version = version;
1478 u->is_dwarf64 = is_dwarf64;
1479 u->addrsize = addrsize;
1480 u->filename = NULL;
1481 u->comp_dir = NULL;
1482 u->abs_filename = NULL;
1483 u->lineoff = 0;
1484 u->abbrevs = abbrevs;
1485 memset (&abbrevs, 0, sizeof abbrevs);
1487 /* The actual line number mappings will be read as needed. */
1488 u->lines = NULL;
1489 u->lines_count = 0;
1490 u->function_addrs = NULL;
1491 u->function_addrs_count = 0;
1493 if (!find_address_ranges (state, base_address, &unit_buf,
1494 dwarf_str, dwarf_str_size,
1495 dwarf_ranges, dwarf_ranges_size,
1496 is_bigendian, error_callback, data,
1497 u, addrs))
1499 free_abbrevs (state, &u->abbrevs, error_callback, data);
1500 backtrace_free (state, u, sizeof *u, error_callback, data);
1501 goto fail;
1504 if (unit_buf.reported_underflow)
1506 free_abbrevs (state, &u->abbrevs, error_callback, data);
1507 backtrace_free (state, u, sizeof *u, error_callback, data);
1508 goto fail;
1511 if (info.reported_underflow)
1512 goto fail;
1514 return 1;
1516 fail:
1517 free_abbrevs (state, &abbrevs, error_callback, data);
1518 free_unit_addrs_vector (state, addrs, error_callback, data);
1519 return 0;
1522 /* Add a new mapping to the vector of line mappings that we are
1523 building. Returns 1 on success, 0 on failure. */
1525 static int
1526 add_line (struct backtrace_state *state, struct dwarf_data *ddata,
1527 uintptr_t pc, const char *filename, int lineno,
1528 backtrace_error_callback error_callback, void *data,
1529 struct line_vector *vec)
1531 struct line *ln;
1533 /* If we are adding the same mapping, ignore it. This can happen
1534 when using discriminators. */
1535 if (vec->count > 0)
1537 ln = (struct line *) vec->vec.base + (vec->count - 1);
1538 if (pc == ln->pc && filename == ln->filename && lineno == ln->lineno)
1539 return 1;
1542 ln = ((struct line *)
1543 backtrace_vector_grow (state, sizeof (struct line), error_callback,
1544 data, &vec->vec));
1545 if (ln == NULL)
1546 return 0;
1548 /* Add in the base address here, so that we can look up the PC
1549 directly. */
1550 ln->pc = pc + ddata->base_address;
1552 ln->filename = filename;
1553 ln->lineno = lineno;
1555 ++vec->count;
1557 return 1;
1560 /* Free the line header information. If FREE_FILENAMES is true we
1561 free the file names themselves, otherwise we leave them, as there
1562 may be line structures pointing to them. */
1564 static void
1565 free_line_header (struct backtrace_state *state, struct line_header *hdr,
1566 backtrace_error_callback error_callback, void *data)
1568 backtrace_free (state, hdr->dirs, hdr->dirs_count * sizeof (const char *),
1569 error_callback, data);
1570 backtrace_free (state, hdr->filenames,
1571 hdr->filenames_count * sizeof (char *),
1572 error_callback, data);
1575 /* Read the line header. Return 1 on success, 0 on failure. */
1577 static int
1578 read_line_header (struct backtrace_state *state, struct unit *u,
1579 int is_dwarf64, struct dwarf_buf *line_buf,
1580 struct line_header *hdr)
1582 uint64_t hdrlen;
1583 struct dwarf_buf hdr_buf;
1584 const unsigned char *p;
1585 const unsigned char *pend;
1586 size_t i;
1588 hdr->version = read_uint16 (line_buf);
1589 if (hdr->version < 2 || hdr->version > 4)
1591 dwarf_buf_error (line_buf, "unsupported line number version");
1592 return 0;
1595 hdrlen = read_offset (line_buf, is_dwarf64);
1597 hdr_buf = *line_buf;
1598 hdr_buf.left = hdrlen;
1600 if (!advance (line_buf, hdrlen))
1601 return 0;
1603 hdr->min_insn_len = read_byte (&hdr_buf);
1604 if (hdr->version < 4)
1605 hdr->max_ops_per_insn = 1;
1606 else
1607 hdr->max_ops_per_insn = read_byte (&hdr_buf);
1609 /* We don't care about default_is_stmt. */
1610 read_byte (&hdr_buf);
1612 hdr->line_base = read_sbyte (&hdr_buf);
1613 hdr->line_range = read_byte (&hdr_buf);
1615 hdr->opcode_base = read_byte (&hdr_buf);
1616 hdr->opcode_lengths = hdr_buf.buf;
1617 if (!advance (&hdr_buf, hdr->opcode_base - 1))
1618 return 0;
1620 /* Count the number of directory entries. */
1621 hdr->dirs_count = 0;
1622 p = hdr_buf.buf;
1623 pend = p + hdr_buf.left;
1624 while (p < pend && *p != '\0')
1626 p += strnlen((const char *) p, pend - p) + 1;
1627 ++hdr->dirs_count;
1630 hdr->dirs = ((const char **)
1631 backtrace_alloc (state,
1632 hdr->dirs_count * sizeof (const char *),
1633 line_buf->error_callback, line_buf->data));
1634 if (hdr->dirs == NULL)
1635 return 0;
1637 i = 0;
1638 while (*hdr_buf.buf != '\0')
1640 if (hdr_buf.reported_underflow)
1641 return 0;
1643 hdr->dirs[i] = (const char *) hdr_buf.buf;
1644 ++i;
1645 if (!advance (&hdr_buf,
1646 strnlen ((const char *) hdr_buf.buf, hdr_buf.left) + 1))
1647 return 0;
1649 if (!advance (&hdr_buf, 1))
1650 return 0;
1652 /* Count the number of file entries. */
1653 hdr->filenames_count = 0;
1654 p = hdr_buf.buf;
1655 pend = p + hdr_buf.left;
1656 while (p < pend && *p != '\0')
1658 p += strnlen ((const char *) p, pend - p) + 1;
1659 p += leb128_len (p);
1660 p += leb128_len (p);
1661 p += leb128_len (p);
1662 ++hdr->filenames_count;
1665 hdr->filenames = ((const char **)
1666 backtrace_alloc (state,
1667 hdr->filenames_count * sizeof (char *),
1668 line_buf->error_callback,
1669 line_buf->data));
1670 if (hdr->filenames == NULL)
1671 return 0;
1672 i = 0;
1673 while (*hdr_buf.buf != '\0')
1675 const char *filename;
1676 uint64_t dir_index;
1678 if (hdr_buf.reported_underflow)
1679 return 0;
1681 filename = (const char *) hdr_buf.buf;
1682 if (!advance (&hdr_buf,
1683 strnlen ((const char *) hdr_buf.buf, hdr_buf.left) + 1))
1684 return 0;
1685 dir_index = read_uleb128 (&hdr_buf);
1686 if (IS_ABSOLUTE_PATH (filename)
1687 || (dir_index == 0 && u->comp_dir == NULL))
1688 hdr->filenames[i] = filename;
1689 else
1691 const char *dir;
1692 size_t dir_len;
1693 size_t filename_len;
1694 char *s;
1696 if (dir_index == 0)
1697 dir = u->comp_dir;
1698 else if (dir_index - 1 < hdr->dirs_count)
1699 dir = hdr->dirs[dir_index - 1];
1700 else
1702 dwarf_buf_error (line_buf,
1703 ("invalid directory index in "
1704 "line number program header"));
1705 return 0;
1707 dir_len = strlen (dir);
1708 filename_len = strlen (filename);
1709 s = ((char *)
1710 backtrace_alloc (state, dir_len + filename_len + 2,
1711 line_buf->error_callback, line_buf->data));
1712 if (s == NULL)
1713 return 0;
1714 memcpy (s, dir, dir_len);
1715 /* FIXME: If we are on a DOS-based file system, and the
1716 directory or the file name use backslashes, then we
1717 should use a backslash here. */
1718 s[dir_len] = '/';
1719 memcpy (s + dir_len + 1, filename, filename_len + 1);
1720 hdr->filenames[i] = s;
1723 /* Ignore the modification time and size. */
1724 read_uleb128 (&hdr_buf);
1725 read_uleb128 (&hdr_buf);
1727 ++i;
1730 if (hdr_buf.reported_underflow)
1731 return 0;
1733 return 1;
1736 /* Read the line program, adding line mappings to VEC. Return 1 on
1737 success, 0 on failure. */
1739 static int
1740 read_line_program (struct backtrace_state *state, struct dwarf_data *ddata,
1741 struct unit *u, const struct line_header *hdr,
1742 struct dwarf_buf *line_buf, struct line_vector *vec)
1744 uint64_t address;
1745 unsigned int op_index;
1746 const char *reset_filename;
1747 const char *filename;
1748 int lineno;
1750 address = 0;
1751 op_index = 0;
1752 if (hdr->filenames_count > 0)
1753 reset_filename = hdr->filenames[0];
1754 else
1755 reset_filename = "";
1756 filename = reset_filename;
1757 lineno = 1;
1758 while (line_buf->left > 0)
1760 unsigned int op;
1762 op = read_byte (line_buf);
1763 if (op >= hdr->opcode_base)
1765 unsigned int advance;
1767 /* Special opcode. */
1768 op -= hdr->opcode_base;
1769 advance = op / hdr->line_range;
1770 address += (hdr->min_insn_len * (op_index + advance)
1771 / hdr->max_ops_per_insn);
1772 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1773 lineno += hdr->line_base + (int) (op % hdr->line_range);
1774 add_line (state, ddata, address, filename, lineno,
1775 line_buf->error_callback, line_buf->data, vec);
1777 else if (op == DW_LNS_extended_op)
1779 uint64_t len;
1781 len = read_uleb128 (line_buf);
1782 op = read_byte (line_buf);
1783 switch (op)
1785 case DW_LNE_end_sequence:
1786 /* FIXME: Should we mark the high PC here? It seems
1787 that we already have that information from the
1788 compilation unit. */
1789 address = 0;
1790 op_index = 0;
1791 filename = reset_filename;
1792 lineno = 1;
1793 break;
1794 case DW_LNE_set_address:
1795 address = read_address (line_buf, u->addrsize);
1796 break;
1797 case DW_LNE_define_file:
1799 const char *f;
1800 unsigned int dir_index;
1802 f = (const char *) line_buf->buf;
1803 if (!advance (line_buf, strnlen (f, line_buf->left) + 1))
1804 return 0;
1805 dir_index = read_uleb128 (line_buf);
1806 /* Ignore that time and length. */
1807 read_uleb128 (line_buf);
1808 read_uleb128 (line_buf);
1809 if (IS_ABSOLUTE_PATH (f))
1810 filename = f;
1811 else
1813 const char *dir;
1814 size_t dir_len;
1815 size_t f_len;
1816 char *p;
1818 if (dir_index == 0)
1819 dir = u->comp_dir;
1820 else if (dir_index - 1 < hdr->dirs_count)
1821 dir = hdr->dirs[dir_index - 1];
1822 else
1824 dwarf_buf_error (line_buf,
1825 ("invalid directory index "
1826 "in line number program"));
1827 return 0;
1829 dir_len = strlen (dir);
1830 f_len = strlen (f);
1831 p = ((char *)
1832 backtrace_alloc (state, dir_len + f_len + 2,
1833 line_buf->error_callback,
1834 line_buf->data));
1835 if (p == NULL)
1836 return 0;
1837 memcpy (p, dir, dir_len);
1838 /* FIXME: If we are on a DOS-based file system,
1839 and the directory or the file name use
1840 backslashes, then we should use a backslash
1841 here. */
1842 p[dir_len] = '/';
1843 memcpy (p + dir_len + 1, f, f_len + 1);
1844 filename = p;
1847 break;
1848 case DW_LNE_set_discriminator:
1849 /* We don't care about discriminators. */
1850 read_uleb128 (line_buf);
1851 break;
1852 default:
1853 if (!advance (line_buf, len - 1))
1854 return 0;
1855 break;
1858 else
1860 switch (op)
1862 case DW_LNS_copy:
1863 add_line (state, ddata, address, filename, lineno,
1864 line_buf->error_callback, line_buf->data, vec);
1865 break;
1866 case DW_LNS_advance_pc:
1868 uint64_t advance;
1870 advance = read_uleb128 (line_buf);
1871 address += (hdr->min_insn_len * (op_index + advance)
1872 / hdr->max_ops_per_insn);
1873 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1875 break;
1876 case DW_LNS_advance_line:
1877 lineno += (int) read_sleb128 (line_buf);
1878 break;
1879 case DW_LNS_set_file:
1881 uint64_t fileno;
1883 fileno = read_uleb128 (line_buf);
1884 if (fileno == 0)
1885 filename = "";
1886 else
1888 if (fileno - 1 >= hdr->filenames_count)
1890 dwarf_buf_error (line_buf,
1891 ("invalid file number in "
1892 "line number program"));
1893 return 0;
1895 filename = hdr->filenames[fileno - 1];
1898 break;
1899 case DW_LNS_set_column:
1900 read_uleb128 (line_buf);
1901 break;
1902 case DW_LNS_negate_stmt:
1903 break;
1904 case DW_LNS_set_basic_block:
1905 break;
1906 case DW_LNS_const_add_pc:
1908 unsigned int advance;
1910 op = 255 - hdr->opcode_base;
1911 advance = op / hdr->line_range;
1912 address += (hdr->min_insn_len * (op_index + advance)
1913 / hdr->max_ops_per_insn);
1914 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1916 break;
1917 case DW_LNS_fixed_advance_pc:
1918 address += read_uint16 (line_buf);
1919 op_index = 0;
1920 break;
1921 case DW_LNS_set_prologue_end:
1922 break;
1923 case DW_LNS_set_epilogue_begin:
1924 break;
1925 case DW_LNS_set_isa:
1926 read_uleb128 (line_buf);
1927 break;
1928 default:
1930 unsigned int i;
1932 for (i = hdr->opcode_lengths[op - 1]; i > 0; --i)
1933 read_uleb128 (line_buf);
1935 break;
1940 return 1;
1943 /* Read the line number information for a compilation unit. Returns 1
1944 on success, 0 on failure. */
1946 static int
1947 read_line_info (struct backtrace_state *state, struct dwarf_data *ddata,
1948 backtrace_error_callback error_callback, void *data,
1949 struct unit *u, struct line_header *hdr, struct line **lines,
1950 size_t *lines_count)
1952 struct line_vector vec;
1953 struct dwarf_buf line_buf;
1954 uint64_t len;
1955 int is_dwarf64;
1956 struct line *ln;
1958 memset (&vec.vec, 0, sizeof vec.vec);
1959 vec.count = 0;
1961 memset (hdr, 0, sizeof *hdr);
1963 if (u->lineoff != (off_t) (size_t) u->lineoff
1964 || (size_t) u->lineoff >= ddata->dwarf_line_size)
1966 error_callback (data, "unit line offset out of range", 0);
1967 goto fail;
1970 line_buf.name = ".debug_line";
1971 line_buf.start = ddata->dwarf_line;
1972 line_buf.buf = ddata->dwarf_line + u->lineoff;
1973 line_buf.left = ddata->dwarf_line_size - u->lineoff;
1974 line_buf.is_bigendian = ddata->is_bigendian;
1975 line_buf.error_callback = error_callback;
1976 line_buf.data = data;
1977 line_buf.reported_underflow = 0;
1979 is_dwarf64 = 0;
1980 len = read_uint32 (&line_buf);
1981 if (len == 0xffffffff)
1983 len = read_uint64 (&line_buf);
1984 is_dwarf64 = 1;
1986 line_buf.left = len;
1988 if (!read_line_header (state, u, is_dwarf64, &line_buf, hdr))
1989 goto fail;
1991 if (!read_line_program (state, ddata, u, hdr, &line_buf, &vec))
1992 goto fail;
1994 if (line_buf.reported_underflow)
1995 goto fail;
1997 if (vec.count == 0)
1999 /* This is not a failure in the sense of a generating an error,
2000 but it is a failure in that sense that we have no useful
2001 information. */
2002 goto fail;
2005 /* Allocate one extra entry at the end. */
2006 ln = ((struct line *)
2007 backtrace_vector_grow (state, sizeof (struct line), error_callback,
2008 data, &vec.vec));
2009 if (ln == NULL)
2010 goto fail;
2011 ln->pc = (uintptr_t) -1;
2012 ln->filename = NULL;
2013 ln->lineno = 0;
2015 if (!backtrace_vector_release (state, &vec.vec, error_callback, data))
2016 goto fail;
2018 ln = (struct line *) vec.vec.base;
2019 backtrace_qsort (ln, vec.count, sizeof (struct line), line_compare);
2021 *lines = ln;
2022 *lines_count = vec.count;
2024 return 1;
2026 fail:
2027 vec.vec.alc += vec.vec.size;
2028 vec.vec.size = 0;
2029 backtrace_vector_release (state, &vec.vec, error_callback, data);
2030 free_line_header (state, hdr, error_callback, data);
2031 *lines = (struct line *) (uintptr_t) -1;
2032 *lines_count = 0;
2033 return 0;
2036 /* Read the name of a function from a DIE referenced by a
2037 DW_AT_abstract_origin or DW_AT_specification tag. OFFSET is within
2038 the same compilation unit. */
2040 static const char *
2041 read_referenced_name (struct dwarf_data *ddata, struct unit *u,
2042 uint64_t offset, backtrace_error_callback error_callback,
2043 void *data)
2045 struct dwarf_buf unit_buf;
2046 uint64_t code;
2047 const struct abbrev *abbrev;
2048 const char *ret;
2049 size_t i;
2051 /* OFFSET is from the start of the data for this compilation unit.
2052 U->unit_data is the data, but it starts U->unit_data_offset bytes
2053 from the beginning. */
2055 if (offset < u->unit_data_offset
2056 || offset - u->unit_data_offset >= u->unit_data_len)
2058 error_callback (data,
2059 "abstract origin or specification out of range",
2061 return NULL;
2064 offset -= u->unit_data_offset;
2066 unit_buf.name = ".debug_info";
2067 unit_buf.start = ddata->dwarf_info;
2068 unit_buf.buf = u->unit_data + offset;
2069 unit_buf.left = u->unit_data_len - offset;
2070 unit_buf.is_bigendian = ddata->is_bigendian;
2071 unit_buf.error_callback = error_callback;
2072 unit_buf.data = data;
2073 unit_buf.reported_underflow = 0;
2075 code = read_uleb128 (&unit_buf);
2076 if (code == 0)
2078 dwarf_buf_error (&unit_buf, "invalid abstract origin or specification");
2079 return NULL;
2082 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
2083 if (abbrev == NULL)
2084 return NULL;
2086 ret = NULL;
2087 for (i = 0; i < abbrev->num_attrs; ++i)
2089 struct attr_val val;
2091 if (!read_attribute (abbrev->attrs[i].form, &unit_buf,
2092 u->is_dwarf64, u->version, u->addrsize,
2093 ddata->dwarf_str, ddata->dwarf_str_size,
2094 &val))
2095 return NULL;
2097 switch (abbrev->attrs[i].name)
2099 case DW_AT_name:
2100 /* We prefer the linkage name if get one. */
2101 if (val.encoding == ATTR_VAL_STRING)
2102 ret = val.u.string;
2103 break;
2105 case DW_AT_linkage_name:
2106 case DW_AT_MIPS_linkage_name:
2107 if (val.encoding == ATTR_VAL_STRING)
2108 return val.u.string;
2109 break;
2111 case DW_AT_specification:
2112 if (abbrev->attrs[i].form == DW_FORM_ref_addr
2113 || abbrev->attrs[i].form == DW_FORM_ref_sig8)
2115 /* This refers to a specification defined in some other
2116 compilation unit. We can handle this case if we
2117 must, but it's harder. */
2118 break;
2120 if (val.encoding == ATTR_VAL_UINT
2121 || val.encoding == ATTR_VAL_REF_UNIT)
2123 const char *name;
2125 name = read_referenced_name (ddata, u, val.u.uint,
2126 error_callback, data);
2127 if (name != NULL)
2128 ret = name;
2130 break;
2132 default:
2133 break;
2137 return ret;
2140 /* Add a single range to U that maps to function. Returns 1 on
2141 success, 0 on error. */
2143 static int
2144 add_function_range (struct backtrace_state *state, struct dwarf_data *ddata,
2145 struct function *function, uint64_t lowpc, uint64_t highpc,
2146 backtrace_error_callback error_callback,
2147 void *data, struct function_vector *vec)
2149 struct function_addrs *p;
2151 /* Add in the base address here, so that we can look up the PC
2152 directly. */
2153 lowpc += ddata->base_address;
2154 highpc += ddata->base_address;
2156 if (vec->count > 0)
2158 p = (struct function_addrs *) vec->vec.base + vec->count - 1;
2159 if ((lowpc == p->high || lowpc == p->high + 1)
2160 && function == p->function)
2162 if (highpc > p->high)
2163 p->high = highpc;
2164 return 1;
2168 p = ((struct function_addrs *)
2169 backtrace_vector_grow (state, sizeof (struct function_addrs),
2170 error_callback, data, &vec->vec));
2171 if (p == NULL)
2172 return 0;
2174 p->low = lowpc;
2175 p->high = highpc;
2176 p->function = function;
2177 ++vec->count;
2178 return 1;
2181 /* Add PC ranges to U that map to FUNCTION. Returns 1 on success, 0
2182 on error. */
2184 static int
2185 add_function_ranges (struct backtrace_state *state, struct dwarf_data *ddata,
2186 struct unit *u, struct function *function,
2187 uint64_t ranges, uint64_t base,
2188 backtrace_error_callback error_callback, void *data,
2189 struct function_vector *vec)
2191 struct dwarf_buf ranges_buf;
2193 if (ranges >= ddata->dwarf_ranges_size)
2195 error_callback (data, "function ranges offset out of range", 0);
2196 return 0;
2199 ranges_buf.name = ".debug_ranges";
2200 ranges_buf.start = ddata->dwarf_ranges;
2201 ranges_buf.buf = ddata->dwarf_ranges + ranges;
2202 ranges_buf.left = ddata->dwarf_ranges_size - ranges;
2203 ranges_buf.is_bigendian = ddata->is_bigendian;
2204 ranges_buf.error_callback = error_callback;
2205 ranges_buf.data = data;
2206 ranges_buf.reported_underflow = 0;
2208 while (1)
2210 uint64_t low;
2211 uint64_t high;
2213 if (ranges_buf.reported_underflow)
2214 return 0;
2216 low = read_address (&ranges_buf, u->addrsize);
2217 high = read_address (&ranges_buf, u->addrsize);
2219 if (low == 0 && high == 0)
2220 break;
2222 if (is_highest_address (low, u->addrsize))
2223 base = high;
2224 else
2226 if (!add_function_range (state, ddata, function, low + base,
2227 high + base, error_callback, data, vec))
2228 return 0;
2232 if (ranges_buf.reported_underflow)
2233 return 0;
2235 return 1;
2238 /* Read one entry plus all its children. Add function addresses to
2239 VEC. Returns 1 on success, 0 on error. */
2241 static int
2242 read_function_entry (struct backtrace_state *state, struct dwarf_data *ddata,
2243 struct unit *u, uint64_t base, struct dwarf_buf *unit_buf,
2244 const struct line_header *lhdr,
2245 backtrace_error_callback error_callback, void *data,
2246 struct function_vector *vec)
2248 while (unit_buf->left > 0)
2250 uint64_t code;
2251 const struct abbrev *abbrev;
2252 int is_function;
2253 struct function *function;
2254 size_t i;
2255 uint64_t lowpc;
2256 int have_lowpc;
2257 uint64_t highpc;
2258 int have_highpc;
2259 int highpc_is_relative;
2260 uint64_t ranges;
2261 int have_ranges;
2263 code = read_uleb128 (unit_buf);
2264 if (code == 0)
2265 return 1;
2267 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
2268 if (abbrev == NULL)
2269 return 0;
2271 is_function = (abbrev->tag == DW_TAG_subprogram
2272 || abbrev->tag == DW_TAG_entry_point
2273 || abbrev->tag == DW_TAG_inlined_subroutine);
2275 function = NULL;
2276 if (is_function)
2278 function = ((struct function *)
2279 backtrace_alloc (state, sizeof *function,
2280 error_callback, data));
2281 if (function == NULL)
2282 return 0;
2283 memset (function, 0, sizeof *function);
2286 lowpc = 0;
2287 have_lowpc = 0;
2288 highpc = 0;
2289 have_highpc = 0;
2290 highpc_is_relative = 0;
2291 ranges = 0;
2292 have_ranges = 0;
2293 for (i = 0; i < abbrev->num_attrs; ++i)
2295 struct attr_val val;
2297 if (!read_attribute (abbrev->attrs[i].form, unit_buf,
2298 u->is_dwarf64, u->version, u->addrsize,
2299 ddata->dwarf_str, ddata->dwarf_str_size,
2300 &val))
2301 return 0;
2303 /* The compile unit sets the base address for any address
2304 ranges in the function entries. */
2305 if (abbrev->tag == DW_TAG_compile_unit
2306 && abbrev->attrs[i].name == DW_AT_low_pc
2307 && val.encoding == ATTR_VAL_ADDRESS)
2308 base = val.u.uint;
2310 if (is_function)
2312 switch (abbrev->attrs[i].name)
2314 case DW_AT_call_file:
2315 if (val.encoding == ATTR_VAL_UINT)
2317 if (val.u.uint == 0)
2318 function->caller_filename = "";
2319 else
2321 if (val.u.uint - 1 >= lhdr->filenames_count)
2323 dwarf_buf_error (unit_buf,
2324 ("invalid file number in "
2325 "DW_AT_call_file attribute"));
2326 return 0;
2328 function->caller_filename =
2329 lhdr->filenames[val.u.uint - 1];
2332 break;
2334 case DW_AT_call_line:
2335 if (val.encoding == ATTR_VAL_UINT)
2336 function->caller_lineno = val.u.uint;
2337 break;
2339 case DW_AT_abstract_origin:
2340 case DW_AT_specification:
2341 if (abbrev->attrs[i].form == DW_FORM_ref_addr
2342 || abbrev->attrs[i].form == DW_FORM_ref_sig8)
2344 /* This refers to an abstract origin defined in
2345 some other compilation unit. We can handle
2346 this case if we must, but it's harder. */
2347 break;
2349 if (val.encoding == ATTR_VAL_UINT
2350 || val.encoding == ATTR_VAL_REF_UNIT)
2352 const char *name;
2354 name = read_referenced_name (ddata, u, val.u.uint,
2355 error_callback, data);
2356 if (name != NULL)
2357 function->name = name;
2359 break;
2361 case DW_AT_name:
2362 if (val.encoding == ATTR_VAL_STRING)
2364 /* Don't override a name we found in some other
2365 way, as it will normally be more
2366 useful--e.g., this name is normally not
2367 mangled. */
2368 if (function->name == NULL)
2369 function->name = val.u.string;
2371 break;
2373 case DW_AT_linkage_name:
2374 case DW_AT_MIPS_linkage_name:
2375 if (val.encoding == ATTR_VAL_STRING)
2376 function->name = val.u.string;
2377 break;
2379 case DW_AT_low_pc:
2380 if (val.encoding == ATTR_VAL_ADDRESS)
2382 lowpc = val.u.uint;
2383 have_lowpc = 1;
2385 break;
2387 case DW_AT_high_pc:
2388 if (val.encoding == ATTR_VAL_ADDRESS)
2390 highpc = val.u.uint;
2391 have_highpc = 1;
2393 else if (val.encoding == ATTR_VAL_UINT)
2395 highpc = val.u.uint;
2396 have_highpc = 1;
2397 highpc_is_relative = 1;
2399 break;
2401 case DW_AT_ranges:
2402 if (val.encoding == ATTR_VAL_UINT
2403 || val.encoding == ATTR_VAL_REF_SECTION)
2405 ranges = val.u.uint;
2406 have_ranges = 1;
2408 break;
2410 default:
2411 break;
2416 /* If we couldn't find a name for the function, we have no use
2417 for it. */
2418 if (is_function && function->name == NULL)
2420 backtrace_free (state, function, sizeof *function,
2421 error_callback, data);
2422 is_function = 0;
2425 if (is_function)
2427 if (have_ranges)
2429 if (!add_function_ranges (state, ddata, u, function, ranges,
2430 base, error_callback, data, vec))
2431 return 0;
2433 else if (have_lowpc && have_highpc)
2435 if (highpc_is_relative)
2436 highpc += lowpc;
2437 if (!add_function_range (state, ddata, function, lowpc, highpc,
2438 error_callback, data, vec))
2439 return 0;
2441 else
2443 backtrace_free (state, function, sizeof *function,
2444 error_callback, data);
2445 is_function = 0;
2449 if (abbrev->has_children)
2451 if (!is_function)
2453 if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
2454 error_callback, data, vec))
2455 return 0;
2457 else
2459 struct function_vector fvec;
2461 /* Gather any information for inlined functions in
2462 FVEC. */
2464 memset (&fvec, 0, sizeof fvec);
2466 if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
2467 error_callback, data, &fvec))
2468 return 0;
2470 if (fvec.count > 0)
2472 struct function_addrs *faddrs;
2474 if (!backtrace_vector_release (state, &fvec.vec,
2475 error_callback, data))
2476 return 0;
2478 faddrs = (struct function_addrs *) fvec.vec.base;
2479 backtrace_qsort (faddrs, fvec.count,
2480 sizeof (struct function_addrs),
2481 function_addrs_compare);
2483 function->function_addrs = faddrs;
2484 function->function_addrs_count = fvec.count;
2490 return 1;
2493 /* Read function name information for a compilation unit. We look
2494 through the whole unit looking for function tags. */
2496 static void
2497 read_function_info (struct backtrace_state *state, struct dwarf_data *ddata,
2498 const struct line_header *lhdr,
2499 backtrace_error_callback error_callback, void *data,
2500 struct unit *u, struct function_vector *fvec,
2501 struct function_addrs **ret_addrs,
2502 size_t *ret_addrs_count)
2504 struct function_vector lvec;
2505 struct function_vector *pfvec;
2506 struct dwarf_buf unit_buf;
2507 struct function_addrs *addrs;
2508 size_t addrs_count;
2510 /* Use FVEC if it is not NULL. Otherwise use our own vector. */
2511 if (fvec != NULL)
2512 pfvec = fvec;
2513 else
2515 memset (&lvec, 0, sizeof lvec);
2516 pfvec = &lvec;
2519 unit_buf.name = ".debug_info";
2520 unit_buf.start = ddata->dwarf_info;
2521 unit_buf.buf = u->unit_data;
2522 unit_buf.left = u->unit_data_len;
2523 unit_buf.is_bigendian = ddata->is_bigendian;
2524 unit_buf.error_callback = error_callback;
2525 unit_buf.data = data;
2526 unit_buf.reported_underflow = 0;
2528 while (unit_buf.left > 0)
2530 if (!read_function_entry (state, ddata, u, 0, &unit_buf, lhdr,
2531 error_callback, data, pfvec))
2532 return;
2535 if (pfvec->count == 0)
2536 return;
2538 addrs_count = pfvec->count;
2540 if (fvec == NULL)
2542 if (!backtrace_vector_release (state, &lvec.vec, error_callback, data))
2543 return;
2544 addrs = (struct function_addrs *) pfvec->vec.base;
2546 else
2548 /* Finish this list of addresses, but leave the remaining space in
2549 the vector available for the next function unit. */
2550 addrs = ((struct function_addrs *)
2551 backtrace_vector_finish (state, &fvec->vec,
2552 error_callback, data));
2553 if (addrs == NULL)
2554 return;
2555 fvec->count = 0;
2558 backtrace_qsort (addrs, addrs_count, sizeof (struct function_addrs),
2559 function_addrs_compare);
2561 *ret_addrs = addrs;
2562 *ret_addrs_count = addrs_count;
2565 /* See if PC is inlined in FUNCTION. If it is, print out the inlined
2566 information, and update FILENAME and LINENO for the caller.
2567 Returns whatever CALLBACK returns, or 0 to keep going. */
2569 static int
2570 report_inlined_functions (uintptr_t pc, struct function *function,
2571 backtrace_full_callback callback, void *data,
2572 const char **filename, int *lineno)
2574 struct function_addrs *function_addrs;
2575 struct function *inlined;
2576 int ret;
2578 if (function->function_addrs_count == 0)
2579 return 0;
2581 function_addrs = ((struct function_addrs *)
2582 bsearch (&pc, function->function_addrs,
2583 function->function_addrs_count,
2584 sizeof (struct function_addrs),
2585 function_addrs_search));
2586 if (function_addrs == NULL)
2587 return 0;
2589 while (((size_t) (function_addrs - function->function_addrs) + 1
2590 < function->function_addrs_count)
2591 && pc >= (function_addrs + 1)->low
2592 && pc < (function_addrs + 1)->high)
2593 ++function_addrs;
2595 /* We found an inlined call. */
2597 inlined = function_addrs->function;
2599 /* Report any calls inlined into this one. */
2600 ret = report_inlined_functions (pc, inlined, callback, data,
2601 filename, lineno);
2602 if (ret != 0)
2603 return ret;
2605 /* Report this inlined call. */
2606 ret = callback (data, pc, *filename, *lineno, inlined->name);
2607 if (ret != 0)
2608 return ret;
2610 /* Our caller will report the caller of the inlined function; tell
2611 it the appropriate filename and line number. */
2612 *filename = inlined->caller_filename;
2613 *lineno = inlined->caller_lineno;
2615 return 0;
2618 /* Look for a PC in the DWARF mapping for one module. On success,
2619 call CALLBACK and return whatever it returns. On error, call
2620 ERROR_CALLBACK and return 0. Sets *FOUND to 1 if the PC is found,
2621 0 if not. */
2623 static int
2624 dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata,
2625 uintptr_t pc, backtrace_full_callback callback,
2626 backtrace_error_callback error_callback, void *data,
2627 int *found)
2629 struct unit_addrs *entry;
2630 struct unit *u;
2631 int new_data;
2632 struct line *lines;
2633 struct line *ln;
2634 struct function_addrs *function_addrs;
2635 struct function *function;
2636 const char *filename;
2637 int lineno;
2638 int ret;
2640 *found = 1;
2642 /* Find an address range that includes PC. */
2643 entry = bsearch (&pc, ddata->addrs, ddata->addrs_count,
2644 sizeof (struct unit_addrs), unit_addrs_search);
2646 if (entry == NULL)
2648 *found = 0;
2649 return 0;
2652 /* If there are multiple ranges that contain PC, use the last one,
2653 in order to produce predictable results. If we assume that all
2654 ranges are properly nested, then the last range will be the
2655 smallest one. */
2656 while ((size_t) (entry - ddata->addrs) + 1 < ddata->addrs_count
2657 && pc >= (entry + 1)->low
2658 && pc < (entry + 1)->high)
2659 ++entry;
2661 /* We need the lines, lines_count, function_addrs,
2662 function_addrs_count fields of u. If they are not set, we need
2663 to set them. When running in threaded mode, we need to allow for
2664 the possibility that some other thread is setting them
2665 simultaneously. */
2667 u = entry->u;
2668 lines = u->lines;
2670 /* Skip units with no useful line number information by walking
2671 backward. Useless line number information is marked by setting
2672 lines == -1. */
2673 while (entry > ddata->addrs
2674 && pc >= (entry - 1)->low
2675 && pc < (entry - 1)->high)
2677 if (state->threaded)
2678 lines = (struct line *) backtrace_atomic_load_pointer (&u->lines);
2680 if (lines != (struct line *) (uintptr_t) -1)
2681 break;
2683 --entry;
2685 u = entry->u;
2686 lines = u->lines;
2689 if (state->threaded)
2690 lines = backtrace_atomic_load_pointer (&u->lines);
2692 new_data = 0;
2693 if (lines == NULL)
2695 size_t function_addrs_count;
2696 struct line_header lhdr;
2697 size_t count;
2699 /* We have never read the line information for this unit. Read
2700 it now. */
2702 function_addrs = NULL;
2703 function_addrs_count = 0;
2704 if (read_line_info (state, ddata, error_callback, data, entry->u, &lhdr,
2705 &lines, &count))
2707 struct function_vector *pfvec;
2709 /* If not threaded, reuse DDATA->FVEC for better memory
2710 consumption. */
2711 if (state->threaded)
2712 pfvec = NULL;
2713 else
2714 pfvec = &ddata->fvec;
2715 read_function_info (state, ddata, &lhdr, error_callback, data,
2716 entry->u, pfvec, &function_addrs,
2717 &function_addrs_count);
2718 free_line_header (state, &lhdr, error_callback, data);
2719 new_data = 1;
2722 /* Atomically store the information we just read into the unit.
2723 If another thread is simultaneously writing, it presumably
2724 read the same information, and we don't care which one we
2725 wind up with; we just leak the other one. We do have to
2726 write the lines field last, so that the acquire-loads above
2727 ensure that the other fields are set. */
2729 if (!state->threaded)
2731 u->lines_count = count;
2732 u->function_addrs = function_addrs;
2733 u->function_addrs_count = function_addrs_count;
2734 u->lines = lines;
2736 else
2738 backtrace_atomic_store_size_t (&u->lines_count, count);
2739 backtrace_atomic_store_pointer (&u->function_addrs, function_addrs);
2740 backtrace_atomic_store_size_t (&u->function_addrs_count,
2741 function_addrs_count);
2742 backtrace_atomic_store_pointer (&u->lines, lines);
2746 /* Now all fields of U have been initialized. */
2748 if (lines == (struct line *) (uintptr_t) -1)
2750 /* If reading the line number information failed in some way,
2751 try again to see if there is a better compilation unit for
2752 this PC. */
2753 if (new_data)
2754 return dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2755 data, found);
2756 return callback (data, pc, NULL, 0, NULL);
2759 /* Search for PC within this unit. */
2761 ln = (struct line *) bsearch (&pc, lines, entry->u->lines_count,
2762 sizeof (struct line), line_search);
2763 if (ln == NULL)
2765 /* The PC is between the low_pc and high_pc attributes of the
2766 compilation unit, but no entry in the line table covers it.
2767 This implies that the start of the compilation unit has no
2768 line number information. */
2770 if (entry->u->abs_filename == NULL)
2772 const char *filename;
2774 filename = entry->u->filename;
2775 if (filename != NULL
2776 && !IS_ABSOLUTE_PATH (filename)
2777 && entry->u->comp_dir != NULL)
2779 size_t filename_len;
2780 const char *dir;
2781 size_t dir_len;
2782 char *s;
2784 filename_len = strlen (filename);
2785 dir = entry->u->comp_dir;
2786 dir_len = strlen (dir);
2787 s = (char *) backtrace_alloc (state, dir_len + filename_len + 2,
2788 error_callback, data);
2789 if (s == NULL)
2791 *found = 0;
2792 return 0;
2794 memcpy (s, dir, dir_len);
2795 /* FIXME: Should use backslash if DOS file system. */
2796 s[dir_len] = '/';
2797 memcpy (s + dir_len + 1, filename, filename_len + 1);
2798 filename = s;
2800 entry->u->abs_filename = filename;
2803 return callback (data, pc, entry->u->abs_filename, 0, NULL);
2806 /* Search for function name within this unit. */
2808 if (entry->u->function_addrs_count == 0)
2809 return callback (data, pc, ln->filename, ln->lineno, NULL);
2811 function_addrs = ((struct function_addrs *)
2812 bsearch (&pc, entry->u->function_addrs,
2813 entry->u->function_addrs_count,
2814 sizeof (struct function_addrs),
2815 function_addrs_search));
2816 if (function_addrs == NULL)
2817 return callback (data, pc, ln->filename, ln->lineno, NULL);
2819 /* If there are multiple function ranges that contain PC, use the
2820 last one, in order to produce predictable results. */
2822 while (((size_t) (function_addrs - entry->u->function_addrs + 1)
2823 < entry->u->function_addrs_count)
2824 && pc >= (function_addrs + 1)->low
2825 && pc < (function_addrs + 1)->high)
2826 ++function_addrs;
2828 function = function_addrs->function;
2830 filename = ln->filename;
2831 lineno = ln->lineno;
2833 ret = report_inlined_functions (pc, function, callback, data,
2834 &filename, &lineno);
2835 if (ret != 0)
2836 return ret;
2838 return callback (data, pc, filename, lineno, function->name);
2842 /* Return the file/line information for a PC using the DWARF mapping
2843 we built earlier. */
2845 static int
2846 dwarf_fileline (struct backtrace_state *state, uintptr_t pc,
2847 backtrace_full_callback callback,
2848 backtrace_error_callback error_callback, void *data)
2850 struct dwarf_data *ddata;
2851 int found;
2852 int ret;
2854 if (!state->threaded)
2856 for (ddata = (struct dwarf_data *) state->fileline_data;
2857 ddata != NULL;
2858 ddata = ddata->next)
2860 ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2861 data, &found);
2862 if (ret != 0 || found)
2863 return ret;
2866 else
2868 struct dwarf_data **pp;
2870 pp = (struct dwarf_data **) (void *) &state->fileline_data;
2871 while (1)
2873 ddata = backtrace_atomic_load_pointer (pp);
2874 if (ddata == NULL)
2875 break;
2877 ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2878 data, &found);
2879 if (ret != 0 || found)
2880 return ret;
2882 pp = &ddata->next;
2886 /* FIXME: See if any libraries have been dlopen'ed. */
2888 return callback (data, pc, NULL, 0, NULL);
2891 /* Initialize our data structures from the DWARF debug info for a
2892 file. Return NULL on failure. */
2894 static struct dwarf_data *
2895 build_dwarf_data (struct backtrace_state *state,
2896 uintptr_t base_address,
2897 const unsigned char *dwarf_info,
2898 size_t dwarf_info_size,
2899 const unsigned char *dwarf_line,
2900 size_t dwarf_line_size,
2901 const unsigned char *dwarf_abbrev,
2902 size_t dwarf_abbrev_size,
2903 const unsigned char *dwarf_ranges,
2904 size_t dwarf_ranges_size,
2905 const unsigned char *dwarf_str,
2906 size_t dwarf_str_size,
2907 int is_bigendian,
2908 backtrace_error_callback error_callback,
2909 void *data)
2911 struct unit_addrs_vector addrs_vec;
2912 struct unit_addrs *addrs;
2913 size_t addrs_count;
2914 struct dwarf_data *fdata;
2916 if (!build_address_map (state, base_address, dwarf_info, dwarf_info_size,
2917 dwarf_abbrev, dwarf_abbrev_size, dwarf_ranges,
2918 dwarf_ranges_size, dwarf_str, dwarf_str_size,
2919 is_bigendian, error_callback, data, &addrs_vec))
2920 return NULL;
2922 if (!backtrace_vector_release (state, &addrs_vec.vec, error_callback, data))
2923 return NULL;
2924 addrs = (struct unit_addrs *) addrs_vec.vec.base;
2925 addrs_count = addrs_vec.count;
2926 backtrace_qsort (addrs, addrs_count, sizeof (struct unit_addrs),
2927 unit_addrs_compare);
2929 fdata = ((struct dwarf_data *)
2930 backtrace_alloc (state, sizeof (struct dwarf_data),
2931 error_callback, data));
2932 if (fdata == NULL)
2933 return NULL;
2935 fdata->next = NULL;
2936 fdata->base_address = base_address;
2937 fdata->addrs = addrs;
2938 fdata->addrs_count = addrs_count;
2939 fdata->dwarf_info = dwarf_info;
2940 fdata->dwarf_info_size = dwarf_info_size;
2941 fdata->dwarf_line = dwarf_line;
2942 fdata->dwarf_line_size = dwarf_line_size;
2943 fdata->dwarf_ranges = dwarf_ranges;
2944 fdata->dwarf_ranges_size = dwarf_ranges_size;
2945 fdata->dwarf_str = dwarf_str;
2946 fdata->dwarf_str_size = dwarf_str_size;
2947 fdata->is_bigendian = is_bigendian;
2948 memset (&fdata->fvec, 0, sizeof fdata->fvec);
2950 return fdata;
2953 /* Build our data structures from the DWARF sections for a module.
2954 Set FILELINE_FN and STATE->FILELINE_DATA. Return 1 on success, 0
2955 on failure. */
2958 backtrace_dwarf_add (struct backtrace_state *state,
2959 uintptr_t base_address,
2960 const unsigned char *dwarf_info,
2961 size_t dwarf_info_size,
2962 const unsigned char *dwarf_line,
2963 size_t dwarf_line_size,
2964 const unsigned char *dwarf_abbrev,
2965 size_t dwarf_abbrev_size,
2966 const unsigned char *dwarf_ranges,
2967 size_t dwarf_ranges_size,
2968 const unsigned char *dwarf_str,
2969 size_t dwarf_str_size,
2970 int is_bigendian,
2971 backtrace_error_callback error_callback,
2972 void *data, fileline *fileline_fn)
2974 struct dwarf_data *fdata;
2976 fdata = build_dwarf_data (state, base_address, dwarf_info, dwarf_info_size,
2977 dwarf_line, dwarf_line_size, dwarf_abbrev,
2978 dwarf_abbrev_size, dwarf_ranges, dwarf_ranges_size,
2979 dwarf_str, dwarf_str_size, is_bigendian,
2980 error_callback, data);
2981 if (fdata == NULL)
2982 return 0;
2984 if (!state->threaded)
2986 struct dwarf_data **pp;
2988 for (pp = (struct dwarf_data **) (void *) &state->fileline_data;
2989 *pp != NULL;
2990 pp = &(*pp)->next)
2992 *pp = fdata;
2994 else
2996 while (1)
2998 struct dwarf_data **pp;
3000 pp = (struct dwarf_data **) (void *) &state->fileline_data;
3002 while (1)
3004 struct dwarf_data *p;
3006 p = backtrace_atomic_load_pointer (pp);
3008 if (p == NULL)
3009 break;
3011 pp = &p->next;
3014 if (__sync_bool_compare_and_swap (pp, NULL, fdata))
3015 break;
3019 *fileline_fn = dwarf_fileline;
3021 return 1;