1/* dwarf.c -- Get file/line information from DWARF for backtraces.
2 Copyright (C) 2012-2017 Free Software Foundation, Inc.
3 Written by Ian Lance Taylor, Google.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are
7met:
8
9 (1) Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
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.
16
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.
20
21THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
25INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
29STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
30IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31POSSIBILITY OF SUCH DAMAGE. */
32
33#include "config.h"
34
35#include <errno.h>
36#include <stdlib.h>
37#include <string.h>
38#include <sys/types.h>
39
40#include "dwarf2.h"
41#include "filenames.h"
42
43#include "backtrace.h"
44#include "internal.h"
45
46#if !defined(HAVE_DECL_STRNLEN) || !HAVE_DECL_STRNLEN
47
48/* If strnlen is not declared, provide our own version. */
49
50static size_t
51xstrnlen (const char *s, size_t maxlen)
52{
53 size_t i;
54
55 for (i = 0; i < maxlen; ++i)
56 if (s[i] == '\0')
57 break;
58 return i;
59}
60
61#define strnlen xstrnlen
62
63#endif
64
65/* A buffer to read DWARF info. */
66
67struct dwarf_buf
68{
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;
85};
86
87/* A single attribute in a DWARF abbreviation. */
88
89struct attr
90{
91 /* The attribute name. */
92 enum dwarf_attribute name;
93 /* The attribute form. */
94 enum dwarf_form form;
95};
96
97/* A single DWARF abbreviation. */
98
99struct abbrev
100{
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;
111};
112
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. */
119
120struct abbrevs
121{
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;
126};
127
128/* The different kinds of attribute values. */
129
130enum attr_val_encoding
131{
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,
152};
153
154/* An attribute value. */
155
156struct attr_val
157{
158 /* How the value is stored in the field u. */
159 enum attr_val_encoding encoding;
160 union
161 {
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;
170};
171
172/* The line number program header. */
173
174struct line_header
175{
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;
198};
199
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. */
204
205struct line
206{
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;
214 /* Index of the object in the original array read from the DWARF
215 section, before it has been sorted. The index makes it possible
216 to use Quicksort and maintain stability. */
217 int idx;
218};
219
220/* A growable vector of line number information. This is used while
221 reading the line numbers. */
222
223struct line_vector
224{
225 /* Memory. This is an array of struct line. */
226 struct backtrace_vector vec;
227 /* Number of valid mappings. */
228 size_t count;
229};
230
231/* A function described in the debug info. */
232
233struct function
234{
235 /* The name of the function. */
236 const char *name;
237 /* If this is an inlined function, the filename of the call
238 site. */
239 const char *caller_filename;
240 /* If this is an inlined function, the line number of the call
241 site. */
242 int caller_lineno;
243 /* Map PC ranges to inlined functions. */
244 struct function_addrs *function_addrs;
245 size_t function_addrs_count;
246};
247
248/* An address range for a function. This maps a PC value to a
249 specific function. */
250
251struct function_addrs
252{
253 /* Range is LOW <= PC < HIGH. */
254 uint64_t low;
255 uint64_t high;
256 /* Function for this address range. */
257 struct function *function;
258};
259
260/* A growable vector of function address ranges. */
261
262struct function_vector
263{
264 /* Memory. This is an array of struct function_addrs. */
265 struct backtrace_vector vec;
266 /* Number of address ranges present. */
267 size_t count;
268};
269
270/* A DWARF compilation unit. This only holds the information we need
271 to map a PC to a file and line. */
272
273struct unit
274{
275 /* The first entry for this compilation unit. */
276 const unsigned char *unit_data;
277 /* The length of the data for this compilation unit. */
278 size_t unit_data_len;
279 /* The offset of UNIT_DATA from the start of the information for
280 this compilation unit. */
281 size_t unit_data_offset;
282 /* DWARF version. */
283 int version;
284 /* Whether unit is DWARF64. */
285 int is_dwarf64;
286 /* Address size. */
287 int addrsize;
288 /* Offset into line number information. */
289 off_t lineoff;
290 /* Primary source file. */
291 const char *filename;
292 /* Compilation command working directory. */
293 const char *comp_dir;
294 /* Absolute file name, only set if needed. */
295 const char *abs_filename;
296 /* The abbreviations for this unit. */
297 struct abbrevs abbrevs;
298
299 /* The fields above this point are read in during initialization and
300 may be accessed freely. The fields below this point are read in
301 as needed, and therefore require care, as different threads may
302 try to initialize them simultaneously. */
303
304 /* PC to line number mapping. This is NULL if the values have not
305 been read. This is (struct line *) -1 if there was an error
306 reading the values. */
307 struct line *lines;
308 /* Number of entries in lines. */
309 size_t lines_count;
310 /* PC ranges to function. */
311 struct function_addrs *function_addrs;
312 size_t function_addrs_count;
313};
314
315/* An address range for a compilation unit. This maps a PC value to a
316 specific compilation unit. Note that we invert the representation
317 in DWARF: instead of listing the units and attaching a list of
318 ranges, we list the ranges and have each one point to the unit.
319 This lets us do a binary search to find the unit. */
320
321struct unit_addrs
322{
323 /* Range is LOW <= PC < HIGH. */
324 uint64_t low;
325 uint64_t high;
326 /* Compilation unit for this address range. */
327 struct unit *u;
328};
329
330/* A growable vector of compilation unit address ranges. */
331
332struct unit_addrs_vector
333{
334 /* Memory. This is an array of struct unit_addrs. */
335 struct backtrace_vector vec;
336 /* Number of address ranges present. */
337 size_t count;
338};
339
340/* The information we need to map a PC to a file and line. */
341
342struct dwarf_data
343{
344 /* The data for the next file we know about. */
345 struct dwarf_data *next;
346 /* The base address for this file. */
347 uintptr_t base_address;
348 /* A sorted list of address ranges. */
349 struct unit_addrs *addrs;
350 /* Number of address ranges in list. */
351 size_t addrs_count;
352 /* The unparsed .debug_info section. */
353 const unsigned char *dwarf_info;
354 size_t dwarf_info_size;
355 /* The unparsed .debug_line section. */
356 const unsigned char *dwarf_line;
357 size_t dwarf_line_size;
358 /* The unparsed .debug_ranges section. */
359 const unsigned char *dwarf_ranges;
360 size_t dwarf_ranges_size;
361 /* The unparsed .debug_str section. */
362 const unsigned char *dwarf_str;
363 size_t dwarf_str_size;
364 /* Whether the data is big-endian or not. */
365 int is_bigendian;
366 /* A vector used for function addresses. We keep this here so that
367 we can grow the vector as we read more functions. */
368 struct function_vector fvec;
369};
370
371/* Report an error for a DWARF buffer. */
372
373static void
374dwarf_buf_error (struct dwarf_buf *buf, const char *msg)
375{
376 char b[200];
377
378 snprintf (b, sizeof b, "%s in %s at %d",
379 msg, buf->name, (int) (buf->buf - buf->start));
380 buf->error_callback (buf->data, b, 0);
381}
382
383/* Require at least COUNT bytes in BUF. Return 1 if all is well, 0 on
384 error. */
385
386static int
387require (struct dwarf_buf *buf, size_t count)
388{
389 if (buf->left >= count)
390 return 1;
391
392 if (!buf->reported_underflow)
393 {
394 dwarf_buf_error (buf, "DWARF underflow");
395 buf->reported_underflow = 1;
396 }
397
398 return 0;
399}
400
401/* Advance COUNT bytes in BUF. Return 1 if all is well, 0 on
402 error. */
403
404static int
405advance (struct dwarf_buf *buf, size_t count)
406{
407 if (!require (buf, count))
408 return 0;
409 buf->buf += count;
410 buf->left -= count;
411 return 1;
412}
413
414/* Read one byte from BUF and advance 1 byte. */
415
416static unsigned char
417read_byte (struct dwarf_buf *buf)
418{
419 const unsigned char *p = buf->buf;
420
421 if (!advance (buf, 1))
422 return 0;
423 return p[0];
424}
425
426/* Read a signed char from BUF and advance 1 byte. */
427
428static signed char
429read_sbyte (struct dwarf_buf *buf)
430{
431 const unsigned char *p = buf->buf;
432
433 if (!advance (buf, 1))
434 return 0;
435 return (*p ^ 0x80) - 0x80;
436}
437
438/* Read a uint16 from BUF and advance 2 bytes. */
439
440static uint16_t
441read_uint16 (struct dwarf_buf *buf)
442{
443 const unsigned char *p = buf->buf;
444
445 if (!advance (buf, 2))
446 return 0;
447 if (buf->is_bigendian)
448 return ((uint16_t) p[0] << 8) | (uint16_t) p[1];
449 else
450 return ((uint16_t) p[1] << 8) | (uint16_t) p[0];
451}
452
453/* Read a uint32 from BUF and advance 4 bytes. */
454
455static uint32_t
456read_uint32 (struct dwarf_buf *buf)
457{
458 const unsigned char *p = buf->buf;
459
460 if (!advance (buf, 4))
461 return 0;
462 if (buf->is_bigendian)
463 return (((uint32_t) p[0] << 24) | ((uint32_t) p[1] << 16)
464 | ((uint32_t) p[2] << 8) | (uint32_t) p[3]);
465 else
466 return (((uint32_t) p[3] << 24) | ((uint32_t) p[2] << 16)
467 | ((uint32_t) p[1] << 8) | (uint32_t) p[0]);
468}
469
470/* Read a uint64 from BUF and advance 8 bytes. */
471
472static uint64_t
473read_uint64 (struct dwarf_buf *buf)
474{
475 const unsigned char *p = buf->buf;
476
477 if (!advance (buf, 8))
478 return 0;
479 if (buf->is_bigendian)
480 return (((uint64_t) p[0] << 56) | ((uint64_t) p[1] << 48)
481 | ((uint64_t) p[2] << 40) | ((uint64_t) p[3] << 32)
482 | ((uint64_t) p[4] << 24) | ((uint64_t) p[5] << 16)
483 | ((uint64_t) p[6] << 8) | (uint64_t) p[7]);
484 else
485 return (((uint64_t) p[7] << 56) | ((uint64_t) p[6] << 48)
486 | ((uint64_t) p[5] << 40) | ((uint64_t) p[4] << 32)
487 | ((uint64_t) p[3] << 24) | ((uint64_t) p[2] << 16)
488 | ((uint64_t) p[1] << 8) | (uint64_t) p[0]);
489}
490
491/* Read an offset from BUF and advance the appropriate number of
492 bytes. */
493
494static uint64_t
495read_offset (struct dwarf_buf *buf, int is_dwarf64)
496{
497 if (is_dwarf64)
498 return read_uint64 (buf);
499 else
500 return read_uint32 (buf);
501}
502
503/* Read an address from BUF and advance the appropriate number of
504 bytes. */
505
506static uint64_t
507read_address (struct dwarf_buf *buf, int addrsize)
508{
509 switch (addrsize)
510 {
511 case 1:
512 return read_byte (buf);
513 case 2:
514 return read_uint16 (buf);
515 case 4:
516 return read_uint32 (buf);
517 case 8:
518 return read_uint64 (buf);
519 default:
520 dwarf_buf_error (buf, "unrecognized address size");
521 return 0;
522 }
523}
524
525/* Return whether a value is the highest possible address, given the
526 address size. */
527
528static int
529is_highest_address (uint64_t address, int addrsize)
530{
531 switch (addrsize)
532 {
533 case 1:
534 return address == (unsigned char) -1;
535 case 2:
536 return address == (uint16_t) -1;
537 case 4:
538 return address == (uint32_t) -1;
539 case 8:
540 return address == (uint64_t) -1;
541 default:
542 return 0;
543 }
544}
545
546/* Read an unsigned LEB128 number. */
547
548static uint64_t
549read_uleb128 (struct dwarf_buf *buf)
550{
551 uint64_t ret;
552 unsigned int shift;
553 int overflow;
554 unsigned char b;
555
556 ret = 0;
557 shift = 0;
558 overflow = 0;
559 do
560 {
561 const unsigned char *p;
562
563 p = buf->buf;
564 if (!advance (buf, 1))
565 return 0;
566 b = *p;
567 if (shift < 64)
568 ret |= ((uint64_t) (b & 0x7f)) << shift;
569 else if (!overflow)
570 {
571 dwarf_buf_error (buf, "LEB128 overflows uint64_t");
572 overflow = 1;
573 }
574 shift += 7;
575 }
576 while ((b & 0x80) != 0);
577
578 return ret;
579}
580
581/* Read a signed LEB128 number. */
582
583static int64_t
584read_sleb128 (struct dwarf_buf *buf)
585{
586 uint64_t val;
587 unsigned int shift;
588 int overflow;
589 unsigned char b;
590
591 val = 0;
592 shift = 0;
593 overflow = 0;
594 do
595 {
596 const unsigned char *p;
597
598 p = buf->buf;
599 if (!advance (buf, 1))
600 return 0;
601 b = *p;
602 if (shift < 64)
603 val |= ((uint64_t) (b & 0x7f)) << shift;
604 else if (!overflow)
605 {
606 dwarf_buf_error (buf, "signed LEB128 overflows uint64_t");
607 overflow = 1;
608 }
609 shift += 7;
610 }
611 while ((b & 0x80) != 0);
612
613 if ((b & 0x40) != 0 && shift < 64)
614 val |= ((uint64_t) -1) << shift;
615
616 return (int64_t) val;
617}
618
619/* Return the length of an LEB128 number. */
620
621static size_t
622leb128_len (const unsigned char *p)
623{
624 size_t ret;
625
626 ret = 1;
627 while ((*p & 0x80) != 0)
628 {
629 ++p;
630 ++ret;
631 }
632 return ret;
633}
634
635/* Free an abbreviations structure. */
636
637static void
638free_abbrevs (struct backtrace_state *state, struct abbrevs *abbrevs,
639 backtrace_error_callback error_callback, void *data)
640{
641 size_t i;
642
643 for (i = 0; i < abbrevs->num_abbrevs; ++i)
644 backtrace_free (state, abbrevs->abbrevs[i].attrs,
645 abbrevs->abbrevs[i].num_attrs * sizeof (struct attr),
646 error_callback, data);
647 backtrace_free (state, abbrevs->abbrevs,
648 abbrevs->num_abbrevs * sizeof (struct abbrev),
649 error_callback, data);
650 abbrevs->num_abbrevs = 0;
651 abbrevs->abbrevs = NULL;
652}
653
654/* Read an attribute value. Returns 1 on success, 0 on failure. If
655 the value can be represented as a uint64_t, sets *VAL and sets
656 *IS_VALID to 1. We don't try to store the value of other attribute
657 forms, because we don't care about them. */
658
659static int
660read_attribute (enum dwarf_form form, struct dwarf_buf *buf,
661 int is_dwarf64, int version, int addrsize,
662 const unsigned char *dwarf_str, size_t dwarf_str_size,
663 struct attr_val *val)
664{
665 /* Avoid warnings about val.u.FIELD may be used uninitialized if
666 this function is inlined. The warnings aren't valid but can
667 occur because the different fields are set and used
668 conditionally. */
669 memset (val, 0, sizeof *val);
670
671 switch (form)
672 {
673 case DW_FORM_addr:
674 val->encoding = ATTR_VAL_ADDRESS;
675 val->u.uint = read_address (buf, addrsize);
676 return 1;
677 case DW_FORM_block2:
678 val->encoding = ATTR_VAL_BLOCK;
679 return advance (buf, read_uint16 (buf));
680 case DW_FORM_block4:
681 val->encoding = ATTR_VAL_BLOCK;
682 return advance (buf, read_uint32 (buf));
683 case DW_FORM_data2:
684 val->encoding = ATTR_VAL_UINT;
685 val->u.uint = read_uint16 (buf);
686 return 1;
687 case DW_FORM_data4:
688 val->encoding = ATTR_VAL_UINT;
689 val->u.uint = read_uint32 (buf);
690 return 1;
691 case DW_FORM_data8:
692 val->encoding = ATTR_VAL_UINT;
693 val->u.uint = read_uint64 (buf);
694 return 1;
695 case DW_FORM_string:
696 val->encoding = ATTR_VAL_STRING;
697 val->u.string = (const char *) buf->buf;
698 return advance (buf, strnlen ((const char *) buf->buf, buf->left) + 1);
699 case DW_FORM_block:
700 val->encoding = ATTR_VAL_BLOCK;
701 return advance (buf, read_uleb128 (buf));
702 case DW_FORM_block1:
703 val->encoding = ATTR_VAL_BLOCK;
704 return advance (buf, read_byte (buf));
705 case DW_FORM_data1:
706 val->encoding = ATTR_VAL_UINT;
707 val->u.uint = read_byte (buf);
708 return 1;
709 case DW_FORM_flag:
710 val->encoding = ATTR_VAL_UINT;
711 val->u.uint = read_byte (buf);
712 return 1;
713 case DW_FORM_sdata:
714 val->encoding = ATTR_VAL_SINT;
715 val->u.sint = read_sleb128 (buf);
716 return 1;
717 case DW_FORM_strp:
718 {
719 uint64_t offset;
720
721 offset = read_offset (buf, is_dwarf64);
722 if (offset >= dwarf_str_size)
723 {
724 dwarf_buf_error (buf, "DW_FORM_strp out of range");
725 return 0;
726 }
727 val->encoding = ATTR_VAL_STRING;
728 val->u.string = (const char *) dwarf_str + offset;
729 return 1;
730 }
731 case DW_FORM_udata:
732 val->encoding = ATTR_VAL_UINT;
733 val->u.uint = read_uleb128 (buf);
734 return 1;
735 case DW_FORM_ref_addr:
736 val->encoding = ATTR_VAL_REF_INFO;
737 if (version == 2)
738 val->u.uint = read_address (buf, addrsize);
739 else
740 val->u.uint = read_offset (buf, is_dwarf64);
741 return 1;
742 case DW_FORM_ref1:
743 val->encoding = ATTR_VAL_REF_UNIT;
744 val->u.uint = read_byte (buf);
745 return 1;
746 case DW_FORM_ref2:
747 val->encoding = ATTR_VAL_REF_UNIT;
748 val->u.uint = read_uint16 (buf);
749 return 1;
750 case DW_FORM_ref4:
751 val->encoding = ATTR_VAL_REF_UNIT;
752 val->u.uint = read_uint32 (buf);
753 return 1;
754 case DW_FORM_ref8:
755 val->encoding = ATTR_VAL_REF_UNIT;
756 val->u.uint = read_uint64 (buf);
757 return 1;
758 case DW_FORM_ref_udata:
759 val->encoding = ATTR_VAL_REF_UNIT;
760 val->u.uint = read_uleb128 (buf);
761 return 1;
762 case DW_FORM_indirect:
763 {
764 uint64_t form;
765
766 form = read_uleb128 (buf);
767 return read_attribute ((enum dwarf_form) form, buf, is_dwarf64,
768 version, addrsize, dwarf_str, dwarf_str_size,
769 val);
770 }
771 case DW_FORM_sec_offset:
772 val->encoding = ATTR_VAL_REF_SECTION;
773 val->u.uint = read_offset (buf, is_dwarf64);
774 return 1;
775 case DW_FORM_exprloc:
776 val->encoding = ATTR_VAL_EXPR;
777 return advance (buf, read_uleb128 (buf));
778 case DW_FORM_flag_present:
779 val->encoding = ATTR_VAL_UINT;
780 val->u.uint = 1;
781 return 1;
782 case DW_FORM_ref_sig8:
783 val->encoding = ATTR_VAL_REF_TYPE;
784 val->u.uint = read_uint64 (buf);
785 return 1;
786 case DW_FORM_GNU_addr_index:
787 val->encoding = ATTR_VAL_REF_SECTION;
788 val->u.uint = read_uleb128 (buf);
789 return 1;
790 case DW_FORM_GNU_str_index:
791 val->encoding = ATTR_VAL_REF_SECTION;
792 val->u.uint = read_uleb128 (buf);
793 return 1;
794 case DW_FORM_GNU_ref_alt:
795 val->encoding = ATTR_VAL_REF_SECTION;
796 val->u.uint = read_offset (buf, is_dwarf64);
797 return 1;
798 case DW_FORM_GNU_strp_alt:
799 val->encoding = ATTR_VAL_REF_SECTION;
800 val->u.uint = read_offset (buf, is_dwarf64);
801 return 1;
802 default:
803 dwarf_buf_error (buf, "unrecognized DWARF form");
804 return 0;
805 }
806}
807
808/* Compare function_addrs for qsort. When ranges are nested, make the
809 smallest one sort last. */
810
811static int
812function_addrs_compare (const void *v1, const void *v2)
813{
814 const struct function_addrs *a1 = (const struct function_addrs *) v1;
815 const struct function_addrs *a2 = (const struct function_addrs *) v2;
816
817 if (a1->low < a2->low)
818 return -1;
819 if (a1->low > a2->low)
820 return 1;
821 if (a1->high < a2->high)
822 return 1;
823 if (a1->high > a2->high)
824 return -1;
825 return strcmp (a1->function->name, a2->function->name);
826}
827
828/* Compare a PC against a function_addrs for bsearch. Note that if
829 there are multiple ranges containing PC, which one will be returned
830 is unpredictable. We compensate for that in dwarf_fileline. */
831
832static int
833function_addrs_search (const void *vkey, const void *ventry)
834{
835 const uintptr_t *key = (const uintptr_t *) vkey;
836 const struct function_addrs *entry = (const struct function_addrs *) ventry;
837 uintptr_t pc;
838
839 pc = *key;
840 if (pc < entry->low)
841 return -1;
842 else if (pc >= entry->high)
843 return 1;
844 else
845 return 0;
846}
847
848/* Add a new compilation unit address range to a vector. Returns 1 on
849 success, 0 on failure. */
850
851static int
852add_unit_addr (struct backtrace_state *state, uintptr_t base_address,
853 struct unit_addrs addrs,
854 backtrace_error_callback error_callback, void *data,
855 struct unit_addrs_vector *vec)
856{
857 struct unit_addrs *p;
858
859 /* Add in the base address of the module here, so that we can look
860 up the PC directly. */
861 addrs.low += base_address;
862 addrs.high += base_address;
863
864 /* Try to merge with the last entry. */
865 if (vec->count > 0)
866 {
867 p = (struct unit_addrs *) vec->vec.base + (vec->count - 1);
868 if ((addrs.low == p->high || addrs.low == p->high + 1)
869 && addrs.u == p->u)
870 {
871 if (addrs.high > p->high)
872 p->high = addrs.high;
873 return 1;
874 }
875 }
876
877 p = ((struct unit_addrs *)
878 backtrace_vector_grow (state, sizeof (struct unit_addrs),
879 error_callback, data, &vec->vec));
880 if (p == NULL)
881 return 0;
882
883 *p = addrs;
884 ++vec->count;
885 return 1;
886}
887
888/* Free a unit address vector. */
889
890static void
891free_unit_addrs_vector (struct backtrace_state *state,
892 struct unit_addrs_vector *vec,
893 backtrace_error_callback error_callback, void *data)
894{
895 struct unit_addrs *addrs;
896 size_t i;
897
898 addrs = (struct unit_addrs *) vec->vec.base;
899 for (i = 0; i < vec->count; ++i)
900 free_abbrevs (state, &addrs[i].u->abbrevs, error_callback, data);
901}
902
903/* Compare unit_addrs for qsort. When ranges are nested, make the
904 smallest one sort last. */
905
906static int
907unit_addrs_compare (const void *v1, const void *v2)
908{
909 const struct unit_addrs *a1 = (const struct unit_addrs *) v1;
910 const struct unit_addrs *a2 = (const struct unit_addrs *) v2;
911
912 if (a1->low < a2->low)
913 return -1;
914 if (a1->low > a2->low)
915 return 1;
916 if (a1->high < a2->high)
917 return 1;
918 if (a1->high > a2->high)
919 return -1;
920 if (a1->u->lineoff < a2->u->lineoff)
921 return -1;
922 if (a1->u->lineoff > a2->u->lineoff)
923 return 1;
924 return 0;
925}
926
927/* Compare a PC against a unit_addrs for bsearch. Note that if there
928 are multiple ranges containing PC, which one will be returned is
929 unpredictable. We compensate for that in dwarf_fileline. */
930
931static int
932unit_addrs_search (const void *vkey, const void *ventry)
933{
934 const uintptr_t *key = (const uintptr_t *) vkey;
935 const struct unit_addrs *entry = (const struct unit_addrs *) ventry;
936 uintptr_t pc;
937
938 pc = *key;
939 if (pc < entry->low)
940 return -1;
941 else if (pc >= entry->high)
942 return 1;
943 else
944 return 0;
945}
946
947/* Sort the line vector by PC. We want a stable sort here to maintain
948 the order of lines for the same PC values. Since the sequence is
949 being sorted in place, their addresses cannot be relied on to
950 maintain stability. That is the purpose of the index member. */
951
952static int
953line_compare (const void *v1, const void *v2)
954{
955 const struct line *ln1 = (const struct line *) v1;
956 const struct line *ln2 = (const struct line *) v2;
957
958 if (ln1->pc < ln2->pc)
959 return -1;
960 else if (ln1->pc > ln2->pc)
961 return 1;
962 else if (ln1->idx < ln2->idx)
963 return -1;
964 else if (ln1->idx > ln2->idx)
965 return 1;
966 else
967 return 0;
968}
969
970/* Find a PC in a line vector. We always allocate an extra entry at
971 the end of the lines vector, so that this routine can safely look
972 at the next entry. Note that when there are multiple mappings for
973 the same PC value, this will return the last one. */
974
975static int
976line_search (const void *vkey, const void *ventry)
977{
978 const uintptr_t *key = (const uintptr_t *) vkey;
979 const struct line *entry = (const struct line *) ventry;
980 uintptr_t pc;
981
982 pc = *key;
983 if (pc < entry->pc)
984 return -1;
985 else if (pc >= (entry + 1)->pc)
986 return 1;
987 else
988 return 0;
989}
990
991/* Sort the abbrevs by the abbrev code. This function is passed to
992 both qsort and bsearch. */
993
994static int
995abbrev_compare (const void *v1, const void *v2)
996{
997 const struct abbrev *a1 = (const struct abbrev *) v1;
998 const struct abbrev *a2 = (const struct abbrev *) v2;
999
1000 if (a1->code < a2->code)
1001 return -1;
1002 else if (a1->code > a2->code)
1003 return 1;
1004 else
1005 {
1006 /* This really shouldn't happen. It means there are two
1007 different abbrevs with the same code, and that means we don't
1008 know which one lookup_abbrev should return. */
1009 return 0;
1010 }
1011}
1012
1013/* Read the abbreviation table for a compilation unit. Returns 1 on
1014 success, 0 on failure. */
1015
1016static int
1017read_abbrevs (struct backtrace_state *state, uint64_t abbrev_offset,
1018 const unsigned char *dwarf_abbrev, size_t dwarf_abbrev_size,
1019 int is_bigendian, backtrace_error_callback error_callback,
1020 void *data, struct abbrevs *abbrevs)
1021{
1022 struct dwarf_buf abbrev_buf;
1023 struct dwarf_buf count_buf;
1024 size_t num_abbrevs;
1025
1026 abbrevs->num_abbrevs = 0;
1027 abbrevs->abbrevs = NULL;
1028
1029 if (abbrev_offset >= dwarf_abbrev_size)
1030 {
1031 error_callback (data, "abbrev offset out of range", 0);
1032 return 0;
1033 }
1034
1035 abbrev_buf.name = ".debug_abbrev";
1036 abbrev_buf.start = dwarf_abbrev;
1037 abbrev_buf.buf = dwarf_abbrev + abbrev_offset;
1038 abbrev_buf.left = dwarf_abbrev_size - abbrev_offset;
1039 abbrev_buf.is_bigendian = is_bigendian;
1040 abbrev_buf.error_callback = error_callback;
1041 abbrev_buf.data = data;
1042 abbrev_buf.reported_underflow = 0;
1043
1044 /* Count the number of abbrevs in this list. */
1045
1046 count_buf = abbrev_buf;
1047 num_abbrevs = 0;
1048 while (read_uleb128 (&count_buf) != 0)
1049 {
1050 if (count_buf.reported_underflow)
1051 return 0;
1052 ++num_abbrevs;
1053 // Skip tag.
1054 read_uleb128 (&count_buf);
1055 // Skip has_children.
1056 read_byte (&count_buf);
1057 // Skip attributes.
1058 while (read_uleb128 (&count_buf) != 0)
1059 read_uleb128 (&count_buf);
1060 // Skip form of last attribute.
1061 read_uleb128 (&count_buf);
1062 }
1063
1064 if (count_buf.reported_underflow)
1065 return 0;
1066
1067 if (num_abbrevs == 0)
1068 return 1;
1069
1070 abbrevs->num_abbrevs = num_abbrevs;
1071 abbrevs->abbrevs = ((struct abbrev *)
1072 backtrace_alloc (state,
1073 num_abbrevs * sizeof (struct abbrev),
1074 error_callback, data));
1075 if (abbrevs->abbrevs == NULL)
1076 return 0;
1077 memset (abbrevs->abbrevs, 0, num_abbrevs * sizeof (struct abbrev));
1078
1079 num_abbrevs = 0;
1080 while (1)
1081 {
1082 uint64_t code;
1083 struct abbrev a;
1084 size_t num_attrs;
1085 struct attr *attrs;
1086
1087 if (abbrev_buf.reported_underflow)
1088 goto fail;
1089
1090 code = read_uleb128 (&abbrev_buf);
1091 if (code == 0)
1092 break;
1093
1094 a.code = code;
1095 a.tag = (enum dwarf_tag) read_uleb128 (&abbrev_buf);
1096 a.has_children = read_byte (&abbrev_buf);
1097
1098 count_buf = abbrev_buf;
1099 num_attrs = 0;
1100 while (read_uleb128 (&count_buf) != 0)
1101 {
1102 ++num_attrs;
1103 read_uleb128 (&count_buf);
1104 }
1105
1106 if (num_attrs == 0)
1107 {
1108 attrs = NULL;
1109 read_uleb128 (&abbrev_buf);
1110 read_uleb128 (&abbrev_buf);
1111 }
1112 else
1113 {
1114 attrs = ((struct attr *)
1115 backtrace_alloc (state, num_attrs * sizeof *attrs,
1116 error_callback, data));
1117 if (attrs == NULL)
1118 goto fail;
1119 num_attrs = 0;
1120 while (1)
1121 {
1122 uint64_t name;
1123 uint64_t form;
1124
1125 name = read_uleb128 (&abbrev_buf);
1126 form = read_uleb128 (&abbrev_buf);
1127 if (name == 0)
1128 break;
1129 attrs[num_attrs].name = (enum dwarf_attribute) name;
1130 attrs[num_attrs].form = (enum dwarf_form) form;
1131 ++num_attrs;
1132 }
1133 }
1134
1135 a.num_attrs = num_attrs;
1136 a.attrs = attrs;
1137
1138 abbrevs->abbrevs[num_abbrevs] = a;
1139 ++num_abbrevs;
1140 }
1141
1142 backtrace_qsort (abbrevs->abbrevs, abbrevs->num_abbrevs,
1143 sizeof (struct abbrev), abbrev_compare);
1144
1145 return 1;
1146
1147 fail:
1148 free_abbrevs (state, abbrevs, error_callback, data);
1149 return 0;
1150}
1151
1152/* Return the abbrev information for an abbrev code. */
1153
1154static const struct abbrev *
1155lookup_abbrev (struct abbrevs *abbrevs, uint64_t code,
1156 backtrace_error_callback error_callback, void *data)
1157{
1158 struct abbrev key;
1159 void *p;
1160
1161 /* With GCC, where abbrevs are simply numbered in order, we should
1162 be able to just look up the entry. */
1163 if (code - 1 < abbrevs->num_abbrevs
1164 && abbrevs->abbrevs[code - 1].code == code)
1165 return &abbrevs->abbrevs[code - 1];
1166
1167 /* Otherwise we have to search. */
1168 memset (&key, 0, sizeof key);
1169 key.code = code;
1170 p = bsearch (&key, abbrevs->abbrevs, abbrevs->num_abbrevs,
1171 sizeof (struct abbrev), abbrev_compare);
1172 if (p == NULL)
1173 {
1174 error_callback (data, "invalid abbreviation code", 0);
1175 return NULL;
1176 }
1177 return (const struct abbrev *) p;
1178}
1179
1180/* Add non-contiguous address ranges for a compilation unit. Returns
1181 1 on success, 0 on failure. */
1182
1183static int
1184add_unit_ranges (struct backtrace_state *state, uintptr_t base_address,
1185 struct unit *u, uint64_t ranges, uint64_t base,
1186 int is_bigendian, const unsigned char *dwarf_ranges,
1187 size_t dwarf_ranges_size,
1188 backtrace_error_callback error_callback, void *data,
1189 struct unit_addrs_vector *addrs)
1190{
1191 struct dwarf_buf ranges_buf;
1192
1193 if (ranges >= dwarf_ranges_size)
1194 {
1195 error_callback (data, "ranges offset out of range", 0);
1196 return 0;
1197 }
1198
1199 ranges_buf.name = ".debug_ranges";
1200 ranges_buf.start = dwarf_ranges;
1201 ranges_buf.buf = dwarf_ranges + ranges;
1202 ranges_buf.left = dwarf_ranges_size - ranges;
1203 ranges_buf.is_bigendian = is_bigendian;
1204 ranges_buf.error_callback = error_callback;
1205 ranges_buf.data = data;
1206 ranges_buf.reported_underflow = 0;
1207
1208 while (1)
1209 {
1210 uint64_t low;
1211 uint64_t high;
1212
1213 if (ranges_buf.reported_underflow)
1214 return 0;
1215
1216 low = read_address (&ranges_buf, u->addrsize);
1217 high = read_address (&ranges_buf, u->addrsize);
1218
1219 if (low == 0 && high == 0)
1220 break;
1221
1222 if (is_highest_address (low, u->addrsize))
1223 base = high;
1224 else
1225 {
1226 struct unit_addrs a;
1227
1228 a.low = low + base;
1229 a.high = high + base;
1230 a.u = u;
1231 if (!add_unit_addr (state, base_address, a, error_callback, data,
1232 addrs))
1233 return 0;
1234 }
1235 }
1236
1237 if (ranges_buf.reported_underflow)
1238 return 0;
1239
1240 return 1;
1241}
1242
1243/* Find the address range covered by a compilation unit, reading from
1244 UNIT_BUF and adding values to U. Returns 1 if all data could be
1245 read, 0 if there is some error. */
1246
1247static int
1248find_address_ranges (struct backtrace_state *state, uintptr_t base_address,
1249 struct dwarf_buf *unit_buf,
1250 const unsigned char *dwarf_str, size_t dwarf_str_size,
1251 const unsigned char *dwarf_ranges,
1252 size_t dwarf_ranges_size,
1253 int is_bigendian, backtrace_error_callback error_callback,
1254 void *data, struct unit *u,
1255 struct unit_addrs_vector *addrs)
1256{
1257 while (unit_buf->left > 0)
1258 {
1259 uint64_t code;
1260 const struct abbrev *abbrev;
1261 uint64_t lowpc;
1262 int have_lowpc;
1263 uint64_t highpc;
1264 int have_highpc;
1265 int highpc_is_relative;
1266 uint64_t ranges;
1267 int have_ranges;
1268 size_t i;
1269
1270 code = read_uleb128 (unit_buf);
1271 if (code == 0)
1272 return 1;
1273
1274 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
1275 if (abbrev == NULL)
1276 return 0;
1277
1278 lowpc = 0;
1279 have_lowpc = 0;
1280 highpc = 0;
1281 have_highpc = 0;
1282 highpc_is_relative = 0;
1283 ranges = 0;
1284 have_ranges = 0;
1285 for (i = 0; i < abbrev->num_attrs; ++i)
1286 {
1287 struct attr_val val;
1288
1289 if (!read_attribute (abbrev->attrs[i].form, unit_buf,
1290 u->is_dwarf64, u->version, u->addrsize,
1291 dwarf_str, dwarf_str_size, &val))
1292 return 0;
1293
1294 switch (abbrev->attrs[i].name)
1295 {
1296 case DW_AT_low_pc:
1297 if (val.encoding == ATTR_VAL_ADDRESS)
1298 {
1299 lowpc = val.u.uint;
1300 have_lowpc = 1;
1301 }
1302 break;
1303
1304 case DW_AT_high_pc:
1305 if (val.encoding == ATTR_VAL_ADDRESS)
1306 {
1307 highpc = val.u.uint;
1308 have_highpc = 1;
1309 }
1310 else if (val.encoding == ATTR_VAL_UINT)
1311 {
1312 highpc = val.u.uint;
1313 have_highpc = 1;
1314 highpc_is_relative = 1;
1315 }
1316 break;
1317
1318 case DW_AT_ranges:
1319 if (val.encoding == ATTR_VAL_UINT
1320 || val.encoding == ATTR_VAL_REF_SECTION)
1321 {
1322 ranges = val.u.uint;
1323 have_ranges = 1;
1324 }
1325 break;
1326
1327 case DW_AT_stmt_list:
1328 if (abbrev->tag == DW_TAG_compile_unit
1329 && (val.encoding == ATTR_VAL_UINT
1330 || val.encoding == ATTR_VAL_REF_SECTION))
1331 u->lineoff = val.u.uint;
1332 break;
1333
1334 case DW_AT_name:
1335 if (abbrev->tag == DW_TAG_compile_unit
1336 && val.encoding == ATTR_VAL_STRING)
1337 u->filename = val.u.string;
1338 break;
1339
1340 case DW_AT_comp_dir:
1341 if (abbrev->tag == DW_TAG_compile_unit
1342 && val.encoding == ATTR_VAL_STRING)
1343 u->comp_dir = val.u.string;
1344 break;
1345
1346 default:
1347 break;
1348 }
1349 }
1350
1351 if (abbrev->tag == DW_TAG_compile_unit
1352 || abbrev->tag == DW_TAG_subprogram)
1353 {
1354 if (have_ranges)
1355 {
1356 if (!add_unit_ranges (state, base_address, u, ranges, lowpc,
1357 is_bigendian, dwarf_ranges,
1358 dwarf_ranges_size, error_callback,
1359 data, addrs))
1360 return 0;
1361 }
1362 else if (have_lowpc && have_highpc)
1363 {
1364 struct unit_addrs a;
1365
1366 if (highpc_is_relative)
1367 highpc += lowpc;
1368 a.low = lowpc;
1369 a.high = highpc;
1370 a.u = u;
1371
1372 if (!add_unit_addr (state, base_address, a, error_callback, data,
1373 addrs))
1374 return 0;
1375 }
1376
1377 /* If we found the PC range in the DW_TAG_compile_unit, we
1378 can stop now. */
1379 if (abbrev->tag == DW_TAG_compile_unit
1380 && (have_ranges || (have_lowpc && have_highpc)))
1381 return 1;
1382 }
1383
1384 if (abbrev->has_children)
1385 {
1386 if (!find_address_ranges (state, base_address, unit_buf,
1387 dwarf_str, dwarf_str_size,
1388 dwarf_ranges, dwarf_ranges_size,
1389 is_bigendian, error_callback, data,
1390 u, addrs))
1391 return 0;
1392 }
1393 }
1394
1395 return 1;
1396}
1397
1398/* Build a mapping from address ranges to the compilation units where
1399 the line number information for that range can be found. Returns 1
1400 on success, 0 on failure. */
1401
1402static int
1403build_address_map (struct backtrace_state *state, uintptr_t base_address,
1404 const unsigned char *dwarf_info, size_t dwarf_info_size,
1405 const unsigned char *dwarf_abbrev, size_t dwarf_abbrev_size,
1406 const unsigned char *dwarf_ranges, size_t dwarf_ranges_size,
1407 const unsigned char *dwarf_str, size_t dwarf_str_size,
1408 int is_bigendian, backtrace_error_callback error_callback,
1409 void *data, struct unit_addrs_vector *addrs)
1410{
1411 struct dwarf_buf info;
1412 struct abbrevs abbrevs;
1413
1414 memset (&addrs->vec, 0, sizeof addrs->vec);
1415 addrs->count = 0;
1416
1417 /* Read through the .debug_info section. FIXME: Should we use the
1418 .debug_aranges section? gdb and addr2line don't use it, but I'm
1419 not sure why. */
1420
1421 info.name = ".debug_info";
1422 info.start = dwarf_info;
1423 info.buf = dwarf_info;
1424 info.left = dwarf_info_size;
1425 info.is_bigendian = is_bigendian;
1426 info.error_callback = error_callback;
1427 info.data = data;
1428 info.reported_underflow = 0;
1429
1430 memset (&abbrevs, 0, sizeof abbrevs);
1431 while (info.left > 0)
1432 {
1433 const unsigned char *unit_data_start;
1434 uint64_t len;
1435 int is_dwarf64;
1436 struct dwarf_buf unit_buf;
1437 int version;
1438 uint64_t abbrev_offset;
1439 int addrsize;
1440 struct unit *u;
1441
1442 if (info.reported_underflow)
1443 goto fail;
1444
1445 unit_data_start = info.buf;
1446
1447 is_dwarf64 = 0;
1448 len = read_uint32 (&info);
1449 if (len == 0xffffffff)
1450 {
1451 len = read_uint64 (&info);
1452 is_dwarf64 = 1;
1453 }
1454
1455 unit_buf = info;
1456 unit_buf.left = len;
1457
1458 if (!advance (&info, len))
1459 goto fail;
1460
1461 version = read_uint16 (&unit_buf);
1462 if (version < 2 || version > 4)
1463 {
1464 dwarf_buf_error (&unit_buf, "unrecognized DWARF version");
1465 goto fail;
1466 }
1467
1468 abbrev_offset = read_offset (&unit_buf, is_dwarf64);
1469 if (!read_abbrevs (state, abbrev_offset, dwarf_abbrev, dwarf_abbrev_size,
1470 is_bigendian, error_callback, data, &abbrevs))
1471 goto fail;
1472
1473 addrsize = read_byte (&unit_buf);
1474
1475 u = ((struct unit *)
1476 backtrace_alloc (state, sizeof *u, error_callback, data));
1477 if (u == NULL)
1478 goto fail;
1479 u->unit_data = unit_buf.buf;
1480 u->unit_data_len = unit_buf.left;
1481 u->unit_data_offset = unit_buf.buf - unit_data_start;
1482 u->version = version;
1483 u->is_dwarf64 = is_dwarf64;
1484 u->addrsize = addrsize;
1485 u->filename = NULL;
1486 u->comp_dir = NULL;
1487 u->abs_filename = NULL;
1488 u->lineoff = 0;
1489 u->abbrevs = abbrevs;
1490 memset (&abbrevs, 0, sizeof abbrevs);
1491
1492 /* The actual line number mappings will be read as needed. */
1493 u->lines = NULL;
1494 u->lines_count = 0;
1495 u->function_addrs = NULL;
1496 u->function_addrs_count = 0;
1497
1498 if (!find_address_ranges (state, base_address, &unit_buf,
1499 dwarf_str, dwarf_str_size,
1500 dwarf_ranges, dwarf_ranges_size,
1501 is_bigendian, error_callback, data,
1502 u, addrs))
1503 {
1504 free_abbrevs (state, &u->abbrevs, error_callback, data);
1505 backtrace_free (state, u, sizeof *u, error_callback, data);
1506 goto fail;
1507 }
1508
1509 if (unit_buf.reported_underflow)
1510 {
1511 free_abbrevs (state, &u->abbrevs, error_callback, data);
1512 backtrace_free (state, u, sizeof *u, error_callback, data);
1513 goto fail;
1514 }
1515 }
1516 if (info.reported_underflow)
1517 goto fail;
1518
1519 return 1;
1520
1521 fail:
1522 free_abbrevs (state, &abbrevs, error_callback, data);
1523 free_unit_addrs_vector (state, addrs, error_callback, data);
1524 return 0;
1525}
1526
1527/* Add a new mapping to the vector of line mappings that we are
1528 building. Returns 1 on success, 0 on failure. */
1529
1530static int
1531add_line (struct backtrace_state *state, struct dwarf_data *ddata,
1532 uintptr_t pc, const char *filename, int lineno,
1533 backtrace_error_callback error_callback, void *data,
1534 struct line_vector *vec)
1535{
1536 struct line *ln;
1537
1538 /* If we are adding the same mapping, ignore it. This can happen
1539 when using discriminators. */
1540 if (vec->count > 0)
1541 {
1542 ln = (struct line *) vec->vec.base + (vec->count - 1);
1543 if (pc == ln->pc && filename == ln->filename && lineno == ln->lineno)
1544 return 1;
1545 }
1546
1547 ln = ((struct line *)
1548 backtrace_vector_grow (state, sizeof (struct line), error_callback,
1549 data, &vec->vec));
1550 if (ln == NULL)
1551 return 0;
1552
1553 /* Add in the base address here, so that we can look up the PC
1554 directly. */
1555 ln->pc = pc + ddata->base_address;
1556
1557 ln->filename = filename;
1558 ln->lineno = lineno;
1559 ln->idx = vec->count;
1560
1561 ++vec->count;
1562
1563 return 1;
1564}
1565
1566/* Free the line header information. */
1567
1568static void
1569free_line_header (struct backtrace_state *state, struct line_header *hdr,
1570 backtrace_error_callback error_callback, void *data)
1571{
1572 if (hdr->dirs_count != 0)
1573 backtrace_free (state, hdr->dirs, hdr->dirs_count * sizeof (const char *),
1574 error_callback, data);
1575 backtrace_free (state, hdr->filenames,
1576 hdr->filenames_count * sizeof (char *),
1577 error_callback, data);
1578}
1579
1580/* Read the line header. Return 1 on success, 0 on failure. */
1581
1582static int
1583read_line_header (struct backtrace_state *state, struct unit *u,
1584 int is_dwarf64, struct dwarf_buf *line_buf,
1585 struct line_header *hdr)
1586{
1587 uint64_t hdrlen;
1588 struct dwarf_buf hdr_buf;
1589 const unsigned char *p;
1590 const unsigned char *pend;
1591 size_t i;
1592
1593 hdr->version = read_uint16 (line_buf);
1594 if (hdr->version < 2 || hdr->version > 4)
1595 {
1596 dwarf_buf_error (line_buf, "unsupported line number version");
1597 return 0;
1598 }
1599
1600 hdrlen = read_offset (line_buf, is_dwarf64);
1601
1602 hdr_buf = *line_buf;
1603 hdr_buf.left = hdrlen;
1604
1605 if (!advance (line_buf, hdrlen))
1606 return 0;
1607
1608 hdr->min_insn_len = read_byte (&hdr_buf);
1609 if (hdr->version < 4)
1610 hdr->max_ops_per_insn = 1;
1611 else
1612 hdr->max_ops_per_insn = read_byte (&hdr_buf);
1613
1614 /* We don't care about default_is_stmt. */
1615 read_byte (&hdr_buf);
1616
1617 hdr->line_base = read_sbyte (&hdr_buf);
1618 hdr->line_range = read_byte (&hdr_buf);
1619
1620 hdr->opcode_base = read_byte (&hdr_buf);
1621 hdr->opcode_lengths = hdr_buf.buf;
1622 if (!advance (&hdr_buf, hdr->opcode_base - 1))
1623 return 0;
1624
1625 /* Count the number of directory entries. */
1626 hdr->dirs_count = 0;
1627 p = hdr_buf.buf;
1628 pend = p + hdr_buf.left;
1629 while (p < pend && *p != '\0')
1630 {
1631 p += strnlen((const char *) p, pend - p) + 1;
1632 ++hdr->dirs_count;
1633 }
1634
1635 hdr->dirs = NULL;
1636 if (hdr->dirs_count != 0)
1637 {
1638 hdr->dirs = ((const char **)
1639 backtrace_alloc (state,
1640 hdr->dirs_count * sizeof (const char *),
1641 line_buf->error_callback, line_buf->data));
1642 if (hdr->dirs == NULL)
1643 return 0;
1644 }
1645
1646 i = 0;
1647 while (*hdr_buf.buf != '\0')
1648 {
1649 if (hdr_buf.reported_underflow)
1650 return 0;
1651
1652 hdr->dirs[i] = (const char *) hdr_buf.buf;
1653 ++i;
1654 if (!advance (&hdr_buf,
1655 strnlen ((const char *) hdr_buf.buf, hdr_buf.left) + 1))
1656 return 0;
1657 }
1658 if (!advance (&hdr_buf, 1))
1659 return 0;
1660
1661 /* Count the number of file entries. */
1662 hdr->filenames_count = 0;
1663 p = hdr_buf.buf;
1664 pend = p + hdr_buf.left;
1665 while (p < pend && *p != '\0')
1666 {
1667 p += strnlen ((const char *) p, pend - p) + 1;
1668 p += leb128_len (p);
1669 p += leb128_len (p);
1670 p += leb128_len (p);
1671 ++hdr->filenames_count;
1672 }
1673
1674 hdr->filenames = ((const char **)
1675 backtrace_alloc (state,
1676 hdr->filenames_count * sizeof (char *),
1677 line_buf->error_callback,
1678 line_buf->data));
1679 if (hdr->filenames == NULL)
1680 return 0;
1681 i = 0;
1682 while (*hdr_buf.buf != '\0')
1683 {
1684 const char *filename;
1685 uint64_t dir_index;
1686
1687 if (hdr_buf.reported_underflow)
1688 return 0;
1689
1690 filename = (const char *) hdr_buf.buf;
1691 if (!advance (&hdr_buf,
1692 strnlen ((const char *) hdr_buf.buf, hdr_buf.left) + 1))
1693 return 0;
1694 dir_index = read_uleb128 (&hdr_buf);
1695 if (IS_ABSOLUTE_PATH (filename)
1696 || (dir_index == 0 && u->comp_dir == NULL))
1697 hdr->filenames[i] = filename;
1698 else
1699 {
1700 const char *dir;
1701 size_t dir_len;
1702 size_t filename_len;
1703 char *s;
1704
1705 if (dir_index == 0)
1706 dir = u->comp_dir;
1707 else if (dir_index - 1 < hdr->dirs_count)
1708 dir = hdr->dirs[dir_index - 1];
1709 else
1710 {
1711 dwarf_buf_error (line_buf,
1712 ("invalid directory index in "
1713 "line number program header"));
1714 return 0;
1715 }
1716 dir_len = strlen (dir);
1717 filename_len = strlen (filename);
1718 s = ((char *)
1719 backtrace_alloc (state, dir_len + filename_len + 2,
1720 line_buf->error_callback, line_buf->data));
1721 if (s == NULL)
1722 return 0;
1723 memcpy (s, dir, dir_len);
1724 /* FIXME: If we are on a DOS-based file system, and the
1725 directory or the file name use backslashes, then we
1726 should use a backslash here. */
1727 s[dir_len] = '/';
1728 memcpy (s + dir_len + 1, filename, filename_len + 1);
1729 hdr->filenames[i] = s;
1730 }
1731
1732 /* Ignore the modification time and size. */
1733 read_uleb128 (&hdr_buf);
1734 read_uleb128 (&hdr_buf);
1735
1736 ++i;
1737 }
1738
1739 if (hdr_buf.reported_underflow)
1740 return 0;
1741
1742 return 1;
1743}
1744
1745/* Read the line program, adding line mappings to VEC. Return 1 on
1746 success, 0 on failure. */
1747
1748static int
1749read_line_program (struct backtrace_state *state, struct dwarf_data *ddata,
1750 struct unit *u, const struct line_header *hdr,
1751 struct dwarf_buf *line_buf, struct line_vector *vec)
1752{
1753 uint64_t address;
1754 unsigned int op_index;
1755 const char *reset_filename;
1756 const char *filename;
1757 int lineno;
1758
1759 address = 0;
1760 op_index = 0;
1761 if (hdr->filenames_count > 0)
1762 reset_filename = hdr->filenames[0];
1763 else
1764 reset_filename = "";
1765 filename = reset_filename;
1766 lineno = 1;
1767 while (line_buf->left > 0)
1768 {
1769 unsigned int op;
1770
1771 op = read_byte (line_buf);
1772 if (op >= hdr->opcode_base)
1773 {
1774 unsigned int advance;
1775
1776 /* Special opcode. */
1777 op -= hdr->opcode_base;
1778 advance = op / hdr->line_range;
1779 address += (hdr->min_insn_len * (op_index + advance)
1780 / hdr->max_ops_per_insn);
1781 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1782 lineno += hdr->line_base + (int) (op % hdr->line_range);
1783 add_line (state, ddata, address, filename, lineno,
1784 line_buf->error_callback, line_buf->data, vec);
1785 }
1786 else if (op == DW_LNS_extended_op)
1787 {
1788 uint64_t len;
1789
1790 len = read_uleb128 (line_buf);
1791 op = read_byte (line_buf);
1792 switch (op)
1793 {
1794 case DW_LNE_end_sequence:
1795 /* FIXME: Should we mark the high PC here? It seems
1796 that we already have that information from the
1797 compilation unit. */
1798 address = 0;
1799 op_index = 0;
1800 filename = reset_filename;
1801 lineno = 1;
1802 break;
1803 case DW_LNE_set_address:
1804 address = read_address (line_buf, u->addrsize);
1805 break;
1806 case DW_LNE_define_file:
1807 {
1808 const char *f;
1809 unsigned int dir_index;
1810
1811 f = (const char *) line_buf->buf;
1812 if (!advance (line_buf, strnlen (f, line_buf->left) + 1))
1813 return 0;
1814 dir_index = read_uleb128 (line_buf);
1815 /* Ignore that time and length. */
1816 read_uleb128 (line_buf);
1817 read_uleb128 (line_buf);
1818 if (IS_ABSOLUTE_PATH (f))
1819 filename = f;
1820 else
1821 {
1822 const char *dir;
1823 size_t dir_len;
1824 size_t f_len;
1825 char *p;
1826
1827 if (dir_index == 0)
1828 dir = u->comp_dir;
1829 else if (dir_index - 1 < hdr->dirs_count)
1830 dir = hdr->dirs[dir_index - 1];
1831 else
1832 {
1833 dwarf_buf_error (line_buf,
1834 ("invalid directory index "
1835 "in line number program"));
1836 return 0;
1837 }
1838 dir_len = strlen (dir);
1839 f_len = strlen (f);
1840 p = ((char *)
1841 backtrace_alloc (state, dir_len + f_len + 2,
1842 line_buf->error_callback,
1843 line_buf->data));
1844 if (p == NULL)
1845 return 0;
1846 memcpy (p, dir, dir_len);
1847 /* FIXME: If we are on a DOS-based file system,
1848 and the directory or the file name use
1849 backslashes, then we should use a backslash
1850 here. */
1851 p[dir_len] = '/';
1852 memcpy (p + dir_len + 1, f, f_len + 1);
1853 filename = p;
1854 }
1855 }
1856 break;
1857 case DW_LNE_set_discriminator:
1858 /* We don't care about discriminators. */
1859 read_uleb128 (line_buf);
1860 break;
1861 default:
1862 if (!advance (line_buf, len - 1))
1863 return 0;
1864 break;
1865 }
1866 }
1867 else
1868 {
1869 switch (op)
1870 {
1871 case DW_LNS_copy:
1872 add_line (state, ddata, address, filename, lineno,
1873 line_buf->error_callback, line_buf->data, vec);
1874 break;
1875 case DW_LNS_advance_pc:
1876 {
1877 uint64_t advance;
1878
1879 advance = read_uleb128 (line_buf);
1880 address += (hdr->min_insn_len * (op_index + advance)
1881 / hdr->max_ops_per_insn);
1882 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1883 }
1884 break;
1885 case DW_LNS_advance_line:
1886 lineno += (int) read_sleb128 (line_buf);
1887 break;
1888 case DW_LNS_set_file:
1889 {
1890 uint64_t fileno;
1891
1892 fileno = read_uleb128 (line_buf);
1893 if (fileno == 0)
1894 filename = "";
1895 else
1896 {
1897 if (fileno - 1 >= hdr->filenames_count)
1898 {
1899 dwarf_buf_error (line_buf,
1900 ("invalid file number in "
1901 "line number program"));
1902 return 0;
1903 }
1904 filename = hdr->filenames[fileno - 1];
1905 }
1906 }
1907 break;
1908 case DW_LNS_set_column:
1909 read_uleb128 (line_buf);
1910 break;
1911 case DW_LNS_negate_stmt:
1912 break;
1913 case DW_LNS_set_basic_block:
1914 break;
1915 case DW_LNS_const_add_pc:
1916 {
1917 unsigned int advance;
1918
1919 op = 255 - hdr->opcode_base;
1920 advance = op / hdr->line_range;
1921 address += (hdr->min_insn_len * (op_index + advance)
1922 / hdr->max_ops_per_insn);
1923 op_index = (op_index + advance) % hdr->max_ops_per_insn;
1924 }
1925 break;
1926 case DW_LNS_fixed_advance_pc:
1927 address += read_uint16 (line_buf);
1928 op_index = 0;
1929 break;
1930 case DW_LNS_set_prologue_end:
1931 break;
1932 case DW_LNS_set_epilogue_begin:
1933 break;
1934 case DW_LNS_set_isa:
1935 read_uleb128 (line_buf);
1936 break;
1937 default:
1938 {
1939 unsigned int i;
1940
1941 for (i = hdr->opcode_lengths[op - 1]; i > 0; --i)
1942 read_uleb128 (line_buf);
1943 }
1944 break;
1945 }
1946 }
1947 }
1948
1949 return 1;
1950}
1951
1952/* Read the line number information for a compilation unit. Returns 1
1953 on success, 0 on failure. */
1954
1955static int
1956read_line_info (struct backtrace_state *state, struct dwarf_data *ddata,
1957 backtrace_error_callback error_callback, void *data,
1958 struct unit *u, struct line_header *hdr, struct line **lines,
1959 size_t *lines_count)
1960{
1961 struct line_vector vec;
1962 struct dwarf_buf line_buf;
1963 uint64_t len;
1964 int is_dwarf64;
1965 struct line *ln;
1966
1967 memset (&vec.vec, 0, sizeof vec.vec);
1968 vec.count = 0;
1969
1970 memset (hdr, 0, sizeof *hdr);
1971
1972 if (u->lineoff != (off_t) (size_t) u->lineoff
1973 || (size_t) u->lineoff >= ddata->dwarf_line_size)
1974 {
1975 error_callback (data, "unit line offset out of range", 0);
1976 goto fail;
1977 }
1978
1979 line_buf.name = ".debug_line";
1980 line_buf.start = ddata->dwarf_line;
1981 line_buf.buf = ddata->dwarf_line + u->lineoff;
1982 line_buf.left = ddata->dwarf_line_size - u->lineoff;
1983 line_buf.is_bigendian = ddata->is_bigendian;
1984 line_buf.error_callback = error_callback;
1985 line_buf.data = data;
1986 line_buf.reported_underflow = 0;
1987
1988 is_dwarf64 = 0;
1989 len = read_uint32 (&line_buf);
1990 if (len == 0xffffffff)
1991 {
1992 len = read_uint64 (&line_buf);
1993 is_dwarf64 = 1;
1994 }
1995 line_buf.left = len;
1996
1997 if (!read_line_header (state, u, is_dwarf64, &line_buf, hdr))
1998 goto fail;
1999
2000 if (!read_line_program (state, ddata, u, hdr, &line_buf, &vec))
2001 goto fail;
2002
2003 if (line_buf.reported_underflow)
2004 goto fail;
2005
2006 if (vec.count == 0)
2007 {
2008 /* This is not a failure in the sense of a generating an error,
2009 but it is a failure in that sense that we have no useful
2010 information. */
2011 goto fail;
2012 }
2013
2014 /* Allocate one extra entry at the end. */
2015 ln = ((struct line *)
2016 backtrace_vector_grow (state, sizeof (struct line), error_callback,
2017 data, &vec.vec));
2018 if (ln == NULL)
2019 goto fail;
2020 ln->pc = (uintptr_t) -1;
2021 ln->filename = NULL;
2022 ln->lineno = 0;
2023 ln->idx = 0;
2024
2025 if (!backtrace_vector_release (state, &vec.vec, error_callback, data))
2026 goto fail;
2027
2028 ln = (struct line *) vec.vec.base;
2029 backtrace_qsort (ln, vec.count, sizeof (struct line), line_compare);
2030
2031 *lines = ln;
2032 *lines_count = vec.count;
2033
2034 return 1;
2035
2036 fail:
2037 vec.vec.alc += vec.vec.size;
2038 vec.vec.size = 0;
2039 backtrace_vector_release (state, &vec.vec, error_callback, data);
2040 free_line_header (state, hdr, error_callback, data);
2041 *lines = (struct line *) (uintptr_t) -1;
2042 *lines_count = 0;
2043 return 0;
2044}
2045
2046/* Read the name of a function from a DIE referenced by a
2047 DW_AT_abstract_origin or DW_AT_specification tag. OFFSET is within
2048 the same compilation unit. */
2049
2050static const char *
2051read_referenced_name (struct dwarf_data *ddata, struct unit *u,
2052 uint64_t offset, backtrace_error_callback error_callback,
2053 void *data)
2054{
2055 struct dwarf_buf unit_buf;
2056 uint64_t code;
2057 const struct abbrev *abbrev;
2058 const char *ret;
2059 size_t i;
2060
2061 /* OFFSET is from the start of the data for this compilation unit.
2062 U->unit_data is the data, but it starts U->unit_data_offset bytes
2063 from the beginning. */
2064
2065 if (offset < u->unit_data_offset
2066 || offset - u->unit_data_offset >= u->unit_data_len)
2067 {
2068 error_callback (data,
2069 "abstract origin or specification out of range",
2070 0);
2071 return NULL;
2072 }
2073
2074 offset -= u->unit_data_offset;
2075
2076 unit_buf.name = ".debug_info";
2077 unit_buf.start = ddata->dwarf_info;
2078 unit_buf.buf = u->unit_data + offset;
2079 unit_buf.left = u->unit_data_len - offset;
2080 unit_buf.is_bigendian = ddata->is_bigendian;
2081 unit_buf.error_callback = error_callback;
2082 unit_buf.data = data;
2083 unit_buf.reported_underflow = 0;
2084
2085 code = read_uleb128 (&unit_buf);
2086 if (code == 0)
2087 {
2088 dwarf_buf_error (&unit_buf, "invalid abstract origin or specification");
2089 return NULL;
2090 }
2091
2092 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
2093 if (abbrev == NULL)
2094 return NULL;
2095
2096 ret = NULL;
2097 for (i = 0; i < abbrev->num_attrs; ++i)
2098 {
2099 struct attr_val val;
2100
2101 if (!read_attribute (abbrev->attrs[i].form, &unit_buf,
2102 u->is_dwarf64, u->version, u->addrsize,
2103 ddata->dwarf_str, ddata->dwarf_str_size,
2104 &val))
2105 return NULL;
2106
2107 switch (abbrev->attrs[i].name)
2108 {
2109 case DW_AT_name:
2110 /* We prefer the linkage name if get one. */
2111 if (val.encoding == ATTR_VAL_STRING)
2112 ret = val.u.string;
2113 break;
2114
2115 case DW_AT_linkage_name:
2116 case DW_AT_MIPS_linkage_name:
2117 if (val.encoding == ATTR_VAL_STRING)
2118 return val.u.string;
2119 break;
2120
2121 case DW_AT_specification:
2122 if (abbrev->attrs[i].form == DW_FORM_ref_addr
2123 || abbrev->attrs[i].form == DW_FORM_ref_sig8)
2124 {
2125 /* This refers to a specification defined in some other
2126 compilation unit. We can handle this case if we
2127 must, but it's harder. */
2128 break;
2129 }
2130 if (val.encoding == ATTR_VAL_UINT
2131 || val.encoding == ATTR_VAL_REF_UNIT)
2132 {
2133 const char *name;
2134
2135 name = read_referenced_name (ddata, u, val.u.uint,
2136 error_callback, data);
2137 if (name != NULL)
2138 ret = name;
2139 }
2140 break;
2141
2142 default:
2143 break;
2144 }
2145 }
2146
2147 return ret;
2148}
2149
2150/* Add a single range to U that maps to function. Returns 1 on
2151 success, 0 on error. */
2152
2153static int
2154add_function_range (struct backtrace_state *state, struct dwarf_data *ddata,
2155 struct function *function, uint64_t lowpc, uint64_t highpc,
2156 backtrace_error_callback error_callback,
2157 void *data, struct function_vector *vec)
2158{
2159 struct function_addrs *p;
2160
2161 /* Add in the base address here, so that we can look up the PC
2162 directly. */
2163 lowpc += ddata->base_address;
2164 highpc += ddata->base_address;
2165
2166 if (vec->count > 0)
2167 {
2168 p = (struct function_addrs *) vec->vec.base + vec->count - 1;
2169 if ((lowpc == p->high || lowpc == p->high + 1)
2170 && function == p->function)
2171 {
2172 if (highpc > p->high)
2173 p->high = highpc;
2174 return 1;
2175 }
2176 }
2177
2178 p = ((struct function_addrs *)
2179 backtrace_vector_grow (state, sizeof (struct function_addrs),
2180 error_callback, data, &vec->vec));
2181 if (p == NULL)
2182 return 0;
2183
2184 p->low = lowpc;
2185 p->high = highpc;
2186 p->function = function;
2187 ++vec->count;
2188 return 1;
2189}
2190
2191/* Add PC ranges to U that map to FUNCTION. Returns 1 on success, 0
2192 on error. */
2193
2194static int
2195add_function_ranges (struct backtrace_state *state, struct dwarf_data *ddata,
2196 struct unit *u, struct function *function,
2197 uint64_t ranges, uint64_t base,
2198 backtrace_error_callback error_callback, void *data,
2199 struct function_vector *vec)
2200{
2201 struct dwarf_buf ranges_buf;
2202
2203 if (ranges >= ddata->dwarf_ranges_size)
2204 {
2205 error_callback (data, "function ranges offset out of range", 0);
2206 return 0;
2207 }
2208
2209 ranges_buf.name = ".debug_ranges";
2210 ranges_buf.start = ddata->dwarf_ranges;
2211 ranges_buf.buf = ddata->dwarf_ranges + ranges;
2212 ranges_buf.left = ddata->dwarf_ranges_size - ranges;
2213 ranges_buf.is_bigendian = ddata->is_bigendian;
2214 ranges_buf.error_callback = error_callback;
2215 ranges_buf.data = data;
2216 ranges_buf.reported_underflow = 0;
2217
2218 while (1)
2219 {
2220 uint64_t low;
2221 uint64_t high;
2222
2223 if (ranges_buf.reported_underflow)
2224 return 0;
2225
2226 low = read_address (&ranges_buf, u->addrsize);
2227 high = read_address (&ranges_buf, u->addrsize);
2228
2229 if (low == 0 && high == 0)
2230 break;
2231
2232 if (is_highest_address (low, u->addrsize))
2233 base = high;
2234 else
2235 {
2236 if (!add_function_range (state, ddata, function, low + base,
2237 high + base, error_callback, data, vec))
2238 return 0;
2239 }
2240 }
2241
2242 if (ranges_buf.reported_underflow)
2243 return 0;
2244
2245 return 1;
2246}
2247
2248/* Read one entry plus all its children. Add function addresses to
2249 VEC. Returns 1 on success, 0 on error. */
2250
2251static int
2252read_function_entry (struct backtrace_state *state, struct dwarf_data *ddata,
2253 struct unit *u, uint64_t base, struct dwarf_buf *unit_buf,
2254 const struct line_header *lhdr,
2255 backtrace_error_callback error_callback, void *data,
2256 struct function_vector *vec_function,
2257 struct function_vector *vec_inlined)
2258{
2259 while (unit_buf->left > 0)
2260 {
2261 uint64_t code;
2262 const struct abbrev *abbrev;
2263 int is_function;
2264 struct function *function;
2265 struct function_vector *vec;
2266 size_t i;
2267 uint64_t lowpc;
2268 int have_lowpc;
2269 uint64_t highpc;
2270 int have_highpc;
2271 int highpc_is_relative;
2272 uint64_t ranges;
2273 int have_ranges;
2274
2275 code = read_uleb128 (unit_buf);
2276 if (code == 0)
2277 return 1;
2278
2279 abbrev = lookup_abbrev (&u->abbrevs, code, error_callback, data);
2280 if (abbrev == NULL)
2281 return 0;
2282
2283 is_function = (abbrev->tag == DW_TAG_subprogram
2284 || abbrev->tag == DW_TAG_entry_point
2285 || abbrev->tag == DW_TAG_inlined_subroutine);
2286
2287 if (abbrev->tag == DW_TAG_inlined_subroutine)
2288 vec = vec_inlined;
2289 else
2290 vec = vec_function;
2291
2292 function = NULL;
2293 if (is_function)
2294 {
2295 function = ((struct function *)
2296 backtrace_alloc (state, sizeof *function,
2297 error_callback, data));
2298 if (function == NULL)
2299 return 0;
2300 memset (function, 0, sizeof *function);
2301 }
2302
2303 lowpc = 0;
2304 have_lowpc = 0;
2305 highpc = 0;
2306 have_highpc = 0;
2307 highpc_is_relative = 0;
2308 ranges = 0;
2309 have_ranges = 0;
2310 for (i = 0; i < abbrev->num_attrs; ++i)
2311 {
2312 struct attr_val val;
2313
2314 if (!read_attribute (abbrev->attrs[i].form, unit_buf,
2315 u->is_dwarf64, u->version, u->addrsize,
2316 ddata->dwarf_str, ddata->dwarf_str_size,
2317 &val))
2318 return 0;
2319
2320 /* The compile unit sets the base address for any address
2321 ranges in the function entries. */
2322 if (abbrev->tag == DW_TAG_compile_unit
2323 && abbrev->attrs[i].name == DW_AT_low_pc
2324 && val.encoding == ATTR_VAL_ADDRESS)
2325 base = val.u.uint;
2326
2327 if (is_function)
2328 {
2329 switch (abbrev->attrs[i].name)
2330 {
2331 case DW_AT_call_file:
2332 if (val.encoding == ATTR_VAL_UINT)
2333 {
2334 if (val.u.uint == 0)
2335 function->caller_filename = "";
2336 else
2337 {
2338 if (val.u.uint - 1 >= lhdr->filenames_count)
2339 {
2340 dwarf_buf_error (unit_buf,
2341 ("invalid file number in "
2342 "DW_AT_call_file attribute"));
2343 return 0;
2344 }
2345 function->caller_filename =
2346 lhdr->filenames[val.u.uint - 1];
2347 }
2348 }
2349 break;
2350
2351 case DW_AT_call_line:
2352 if (val.encoding == ATTR_VAL_UINT)
2353 function->caller_lineno = val.u.uint;
2354 break;
2355
2356 case DW_AT_abstract_origin:
2357 case DW_AT_specification:
2358 if (abbrev->attrs[i].form == DW_FORM_ref_addr
2359 || abbrev->attrs[i].form == DW_FORM_ref_sig8)
2360 {
2361 /* This refers to an abstract origin defined in
2362 some other compilation unit. We can handle
2363 this case if we must, but it's harder. */
2364 break;
2365 }
2366 if (val.encoding == ATTR_VAL_UINT
2367 || val.encoding == ATTR_VAL_REF_UNIT)
2368 {
2369 const char *name;
2370
2371 name = read_referenced_name (ddata, u, val.u.uint,
2372 error_callback, data);
2373 if (name != NULL)
2374 function->name = name;
2375 }
2376 break;
2377
2378 case DW_AT_name:
2379 if (val.encoding == ATTR_VAL_STRING)
2380 {
2381 /* Don't override a name we found in some other
2382 way, as it will normally be more
2383 useful--e.g., this name is normally not
2384 mangled. */
2385 if (function->name == NULL)
2386 function->name = val.u.string;
2387 }
2388 break;
2389
2390 case DW_AT_linkage_name:
2391 case DW_AT_MIPS_linkage_name:
2392 if (val.encoding == ATTR_VAL_STRING)
2393 function->name = val.u.string;
2394 break;
2395
2396 case DW_AT_low_pc:
2397 if (val.encoding == ATTR_VAL_ADDRESS)
2398 {
2399 lowpc = val.u.uint;
2400 have_lowpc = 1;
2401 }
2402 break;
2403
2404 case DW_AT_high_pc:
2405 if (val.encoding == ATTR_VAL_ADDRESS)
2406 {
2407 highpc = val.u.uint;
2408 have_highpc = 1;
2409 }
2410 else if (val.encoding == ATTR_VAL_UINT)
2411 {
2412 highpc = val.u.uint;
2413 have_highpc = 1;
2414 highpc_is_relative = 1;
2415 }
2416 break;
2417
2418 case DW_AT_ranges:
2419 if (val.encoding == ATTR_VAL_UINT
2420 || val.encoding == ATTR_VAL_REF_SECTION)
2421 {
2422 ranges = val.u.uint;
2423 have_ranges = 1;
2424 }
2425 break;
2426
2427 default:
2428 break;
2429 }
2430 }
2431 }
2432
2433 /* If we couldn't find a name for the function, we have no use
2434 for it. */
2435 if (is_function && function->name == NULL)
2436 {
2437 backtrace_free (state, function, sizeof *function,
2438 error_callback, data);
2439 is_function = 0;
2440 }
2441
2442 if (is_function)
2443 {
2444 if (have_ranges)
2445 {
2446 if (!add_function_ranges (state, ddata, u, function, ranges,
2447 base, error_callback, data, vec))
2448 return 0;
2449 }
2450 else if (have_lowpc && have_highpc)
2451 {
2452 if (highpc_is_relative)
2453 highpc += lowpc;
2454 if (!add_function_range (state, ddata, function, lowpc, highpc,
2455 error_callback, data, vec))
2456 return 0;
2457 }
2458 else
2459 {
2460 backtrace_free (state, function, sizeof *function,
2461 error_callback, data);
2462 is_function = 0;
2463 }
2464 }
2465
2466 if (abbrev->has_children)
2467 {
2468 if (!is_function)
2469 {
2470 if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
2471 error_callback, data, vec_function,
2472 vec_inlined))
2473 return 0;
2474 }
2475 else
2476 {
2477 struct function_vector fvec;
2478
2479 /* Gather any information for inlined functions in
2480 FVEC. */
2481
2482 memset (&fvec, 0, sizeof fvec);
2483
2484 if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
2485 error_callback, data, vec_function,
2486 &fvec))
2487 return 0;
2488
2489 if (fvec.count > 0)
2490 {
2491 struct function_addrs *faddrs;
2492
2493 if (!backtrace_vector_release (state, &fvec.vec,
2494 error_callback, data))
2495 return 0;
2496
2497 faddrs = (struct function_addrs *) fvec.vec.base;
2498 backtrace_qsort (faddrs, fvec.count,
2499 sizeof (struct function_addrs),
2500 function_addrs_compare);
2501
2502 function->function_addrs = faddrs;
2503 function->function_addrs_count = fvec.count;
2504 }
2505 }
2506 }
2507 }
2508
2509 return 1;
2510}
2511
2512/* Read function name information for a compilation unit. We look
2513 through the whole unit looking for function tags. */
2514
2515static void
2516read_function_info (struct backtrace_state *state, struct dwarf_data *ddata,
2517 const struct line_header *lhdr,
2518 backtrace_error_callback error_callback, void *data,
2519 struct unit *u, struct function_vector *fvec,
2520 struct function_addrs **ret_addrs,
2521 size_t *ret_addrs_count)
2522{
2523 struct function_vector lvec;
2524 struct function_vector *pfvec;
2525 struct dwarf_buf unit_buf;
2526 struct function_addrs *addrs;
2527 size_t addrs_count;
2528
2529 /* Use FVEC if it is not NULL. Otherwise use our own vector. */
2530 if (fvec != NULL)
2531 pfvec = fvec;
2532 else
2533 {
2534 memset (&lvec, 0, sizeof lvec);
2535 pfvec = &lvec;
2536 }
2537
2538 unit_buf.name = ".debug_info";
2539 unit_buf.start = ddata->dwarf_info;
2540 unit_buf.buf = u->unit_data;
2541 unit_buf.left = u->unit_data_len;
2542 unit_buf.is_bigendian = ddata->is_bigendian;
2543 unit_buf.error_callback = error_callback;
2544 unit_buf.data = data;
2545 unit_buf.reported_underflow = 0;
2546
2547 while (unit_buf.left > 0)
2548 {
2549 if (!read_function_entry (state, ddata, u, 0, &unit_buf, lhdr,
2550 error_callback, data, pfvec, pfvec))
2551 return;
2552 }
2553
2554 if (pfvec->count == 0)
2555 return;
2556
2557 addrs_count = pfvec->count;
2558
2559 if (fvec == NULL)
2560 {
2561 if (!backtrace_vector_release (state, &lvec.vec, error_callback, data))
2562 return;
2563 addrs = (struct function_addrs *) pfvec->vec.base;
2564 }
2565 else
2566 {
2567 /* Finish this list of addresses, but leave the remaining space in
2568 the vector available for the next function unit. */
2569 addrs = ((struct function_addrs *)
2570 backtrace_vector_finish (state, &fvec->vec,
2571 error_callback, data));
2572 if (addrs == NULL)
2573 return;
2574 fvec->count = 0;
2575 }
2576
2577 backtrace_qsort (addrs, addrs_count, sizeof (struct function_addrs),
2578 function_addrs_compare);
2579
2580 *ret_addrs = addrs;
2581 *ret_addrs_count = addrs_count;
2582}
2583
2584/* See if PC is inlined in FUNCTION. If it is, print out the inlined
2585 information, and update FILENAME and LINENO for the caller.
2586 Returns whatever CALLBACK returns, or 0 to keep going. */
2587
2588static int
2589report_inlined_functions (uintptr_t pc, struct function *function,
2590 backtrace_full_callback callback, void *data,
2591 const char **filename, int *lineno)
2592{
2593 struct function_addrs *function_addrs;
2594 struct function *inlined;
2595 int ret;
2596
2597 if (function->function_addrs_count == 0)
2598 return 0;
2599
2600 function_addrs = ((struct function_addrs *)
2601 bsearch (&pc, function->function_addrs,
2602 function->function_addrs_count,
2603 sizeof (struct function_addrs),
2604 function_addrs_search));
2605 if (function_addrs == NULL)
2606 return 0;
2607
2608 while (((size_t) (function_addrs - function->function_addrs) + 1
2609 < function->function_addrs_count)
2610 && pc >= (function_addrs + 1)->low
2611 && pc < (function_addrs + 1)->high)
2612 ++function_addrs;
2613
2614 /* We found an inlined call. */
2615
2616 inlined = function_addrs->function;
2617
2618 /* Report any calls inlined into this one. */
2619 ret = report_inlined_functions (pc, inlined, callback, data,
2620 filename, lineno);
2621 if (ret != 0)
2622 return ret;
2623
2624 /* Report this inlined call. */
2625 ret = callback (data, pc, *filename, *lineno, inlined->name);
2626 if (ret != 0)
2627 return ret;
2628
2629 /* Our caller will report the caller of the inlined function; tell
2630 it the appropriate filename and line number. */
2631 *filename = inlined->caller_filename;
2632 *lineno = inlined->caller_lineno;
2633
2634 return 0;
2635}
2636
2637/* Look for a PC in the DWARF mapping for one module. On success,
2638 call CALLBACK and return whatever it returns. On error, call
2639 ERROR_CALLBACK and return 0. Sets *FOUND to 1 if the PC is found,
2640 0 if not. */
2641
2642static int
2643dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata,
2644 uintptr_t pc, backtrace_full_callback callback,
2645 backtrace_error_callback error_callback, void *data,
2646 int *found)
2647{
2648 struct unit_addrs *entry;
2649 struct unit *u;
2650 int new_data;
2651 struct line *lines;
2652 struct line *ln;
2653 struct function_addrs *function_addrs;
2654 struct function *function;
2655 const char *filename;
2656 int lineno;
2657 int ret;
2658
2659 *found = 1;
2660
2661 /* Find an address range that includes PC. */
2662 entry = bsearch (&pc, ddata->addrs, ddata->addrs_count,
2663 sizeof (struct unit_addrs), unit_addrs_search);
2664
2665 if (entry == NULL)
2666 {
2667 *found = 0;
2668 return 0;
2669 }
2670
2671 /* If there are multiple ranges that contain PC, use the last one,
2672 in order to produce predictable results. If we assume that all
2673 ranges are properly nested, then the last range will be the
2674 smallest one. */
2675 while ((size_t) (entry - ddata->addrs) + 1 < ddata->addrs_count
2676 && pc >= (entry + 1)->low
2677 && pc < (entry + 1)->high)
2678 ++entry;
2679
2680 /* We need the lines, lines_count, function_addrs,
2681 function_addrs_count fields of u. If they are not set, we need
2682 to set them. When running in threaded mode, we need to allow for
2683 the possibility that some other thread is setting them
2684 simultaneously. */
2685
2686 u = entry->u;
2687 lines = u->lines;
2688
2689 /* Skip units with no useful line number information by walking
2690 backward. Useless line number information is marked by setting
2691 lines == -1. */
2692 while (entry > ddata->addrs
2693 && pc >= (entry - 1)->low
2694 && pc < (entry - 1)->high)
2695 {
2696 if (state->threaded)
2697 lines = (struct line *) backtrace_atomic_load_pointer (&u->lines);
2698
2699 if (lines != (struct line *) (uintptr_t) -1)
2700 break;
2701
2702 --entry;
2703
2704 u = entry->u;
2705 lines = u->lines;
2706 }
2707
2708 if (state->threaded)
2709 lines = backtrace_atomic_load_pointer (&u->lines);
2710
2711 new_data = 0;
2712 if (lines == NULL)
2713 {
2714 size_t function_addrs_count;
2715 struct line_header lhdr;
2716 size_t count;
2717
2718 /* We have never read the line information for this unit. Read
2719 it now. */
2720
2721 function_addrs = NULL;
2722 function_addrs_count = 0;
2723 if (read_line_info (state, ddata, error_callback, data, entry->u, &lhdr,
2724 &lines, &count))
2725 {
2726 struct function_vector *pfvec;
2727
2728 /* If not threaded, reuse DDATA->FVEC for better memory
2729 consumption. */
2730 if (state->threaded)
2731 pfvec = NULL;
2732 else
2733 pfvec = &ddata->fvec;
2734 read_function_info (state, ddata, &lhdr, error_callback, data,
2735 entry->u, pfvec, &function_addrs,
2736 &function_addrs_count);
2737 free_line_header (state, &lhdr, error_callback, data);
2738 new_data = 1;
2739 }
2740
2741 /* Atomically store the information we just read into the unit.
2742 If another thread is simultaneously writing, it presumably
2743 read the same information, and we don't care which one we
2744 wind up with; we just leak the other one. We do have to
2745 write the lines field last, so that the acquire-loads above
2746 ensure that the other fields are set. */
2747
2748 if (!state->threaded)
2749 {
2750 u->lines_count = count;
2751 u->function_addrs = function_addrs;
2752 u->function_addrs_count = function_addrs_count;
2753 u->lines = lines;
2754 }
2755 else
2756 {
2757 backtrace_atomic_store_size_t (&u->lines_count, count);
2758 backtrace_atomic_store_pointer (&u->function_addrs, function_addrs);
2759 backtrace_atomic_store_size_t (&u->function_addrs_count,
2760 function_addrs_count);
2761 backtrace_atomic_store_pointer (&u->lines, lines);
2762 }
2763 }
2764
2765 /* Now all fields of U have been initialized. */
2766
2767 if (lines == (struct line *) (uintptr_t) -1)
2768 {
2769 /* If reading the line number information failed in some way,
2770 try again to see if there is a better compilation unit for
2771 this PC. */
2772 if (new_data)
2773 return dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2774 data, found);
2775 return callback (data, pc, NULL, 0, NULL);
2776 }
2777
2778 /* Search for PC within this unit. */
2779
2780 ln = (struct line *) bsearch (&pc, lines, entry->u->lines_count,
2781 sizeof (struct line), line_search);
2782 if (ln == NULL)
2783 {
2784 /* The PC is between the low_pc and high_pc attributes of the
2785 compilation unit, but no entry in the line table covers it.
2786 This implies that the start of the compilation unit has no
2787 line number information. */
2788
2789 if (entry->u->abs_filename == NULL)
2790 {
2791 const char *filename;
2792
2793 filename = entry->u->filename;
2794 if (filename != NULL
2795 && !IS_ABSOLUTE_PATH (filename)
2796 && entry->u->comp_dir != NULL)
2797 {
2798 size_t filename_len;
2799 const char *dir;
2800 size_t dir_len;
2801 char *s;
2802
2803 filename_len = strlen (filename);
2804 dir = entry->u->comp_dir;
2805 dir_len = strlen (dir);
2806 s = (char *) backtrace_alloc (state, dir_len + filename_len + 2,
2807 error_callback, data);
2808 if (s == NULL)
2809 {
2810 *found = 0;
2811 return 0;
2812 }
2813 memcpy (s, dir, dir_len);
2814 /* FIXME: Should use backslash if DOS file system. */
2815 s[dir_len] = '/';
2816 memcpy (s + dir_len + 1, filename, filename_len + 1);
2817 filename = s;
2818 }
2819 entry->u->abs_filename = filename;
2820 }
2821
2822 return callback (data, pc, entry->u->abs_filename, 0, NULL);
2823 }
2824
2825 /* Search for function name within this unit. */
2826
2827 if (entry->u->function_addrs_count == 0)
2828 return callback (data, pc, ln->filename, ln->lineno, NULL);
2829
2830 function_addrs = ((struct function_addrs *)
2831 bsearch (&pc, entry->u->function_addrs,
2832 entry->u->function_addrs_count,
2833 sizeof (struct function_addrs),
2834 function_addrs_search));
2835 if (function_addrs == NULL)
2836 return callback (data, pc, ln->filename, ln->lineno, NULL);
2837
2838 /* If there are multiple function ranges that contain PC, use the
2839 last one, in order to produce predictable results. */
2840
2841 while (((size_t) (function_addrs - entry->u->function_addrs + 1)
2842 < entry->u->function_addrs_count)
2843 && pc >= (function_addrs + 1)->low
2844 && pc < (function_addrs + 1)->high)
2845 ++function_addrs;
2846
2847 function = function_addrs->function;
2848
2849 filename = ln->filename;
2850 lineno = ln->lineno;
2851
2852 ret = report_inlined_functions (pc, function, callback, data,
2853 &filename, &lineno);
2854 if (ret != 0)
2855 return ret;
2856
2857 return callback (data, pc, filename, lineno, function->name);
2858}
2859
2860
2861/* Return the file/line information for a PC using the DWARF mapping
2862 we built earlier. */
2863
2864static int
2865dwarf_fileline (struct backtrace_state *state, uintptr_t pc,
2866 backtrace_full_callback callback,
2867 backtrace_error_callback error_callback, void *data)
2868{
2869 struct dwarf_data *ddata;
2870 int found;
2871 int ret;
2872
2873 if (!state->threaded)
2874 {
2875 for (ddata = (struct dwarf_data *) state->fileline_data;
2876 ddata != NULL;
2877 ddata = ddata->next)
2878 {
2879 ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2880 data, &found);
2881 if (ret != 0 || found)
2882 return ret;
2883 }
2884 }
2885 else
2886 {
2887 struct dwarf_data **pp;
2888
2889 pp = (struct dwarf_data **) (void *) &state->fileline_data;
2890 while (1)
2891 {
2892 ddata = backtrace_atomic_load_pointer (pp);
2893 if (ddata == NULL)
2894 break;
2895
2896 ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
2897 data, &found);
2898 if (ret != 0 || found)
2899 return ret;
2900
2901 pp = &ddata->next;
2902 }
2903 }
2904
2905 /* FIXME: See if any libraries have been dlopen'ed. */
2906
2907 return callback (data, pc, NULL, 0, NULL);
2908}
2909
2910/* Initialize our data structures from the DWARF debug info for a
2911 file. Return NULL on failure. */
2912
2913static struct dwarf_data *
2914build_dwarf_data (struct backtrace_state *state,
2915 uintptr_t base_address,
2916 const unsigned char *dwarf_info,
2917 size_t dwarf_info_size,
2918 const unsigned char *dwarf_line,
2919 size_t dwarf_line_size,
2920 const unsigned char *dwarf_abbrev,
2921 size_t dwarf_abbrev_size,
2922 const unsigned char *dwarf_ranges,
2923 size_t dwarf_ranges_size,
2924 const unsigned char *dwarf_str,
2925 size_t dwarf_str_size,
2926 int is_bigendian,
2927 backtrace_error_callback error_callback,
2928 void *data)
2929{
2930 struct unit_addrs_vector addrs_vec;
2931 struct unit_addrs *addrs;
2932 size_t addrs_count;
2933 struct dwarf_data *fdata;
2934
2935 if (!build_address_map (state, base_address, dwarf_info, dwarf_info_size,
2936 dwarf_abbrev, dwarf_abbrev_size, dwarf_ranges,
2937 dwarf_ranges_size, dwarf_str, dwarf_str_size,
2938 is_bigendian, error_callback, data, &addrs_vec))
2939 return NULL;
2940
2941 if (!backtrace_vector_release (state, &addrs_vec.vec, error_callback, data))
2942 return NULL;
2943 addrs = (struct unit_addrs *) addrs_vec.vec.base;
2944 addrs_count = addrs_vec.count;
2945 backtrace_qsort (addrs, addrs_count, sizeof (struct unit_addrs),
2946 unit_addrs_compare);
2947
2948 fdata = ((struct dwarf_data *)
2949 backtrace_alloc (state, sizeof (struct dwarf_data),
2950 error_callback, data));
2951 if (fdata == NULL)
2952 return NULL;
2953
2954 fdata->next = NULL;
2955 fdata->base_address = base_address;
2956 fdata->addrs = addrs;
2957 fdata->addrs_count = addrs_count;
2958 fdata->dwarf_info = dwarf_info;
2959 fdata->dwarf_info_size = dwarf_info_size;
2960 fdata->dwarf_line = dwarf_line;
2961 fdata->dwarf_line_size = dwarf_line_size;
2962 fdata->dwarf_ranges = dwarf_ranges;
2963 fdata->dwarf_ranges_size = dwarf_ranges_size;
2964 fdata->dwarf_str = dwarf_str;
2965 fdata->dwarf_str_size = dwarf_str_size;
2966 fdata->is_bigendian = is_bigendian;
2967 memset (&fdata->fvec, 0, sizeof fdata->fvec);
2968
2969 return fdata;
2970}
2971
2972/* Build our data structures from the DWARF sections for a module.
2973 Set FILELINE_FN and STATE->FILELINE_DATA. Return 1 on success, 0
2974 on failure. */
2975
2976int
2977backtrace_dwarf_add (struct backtrace_state *state,
2978 uintptr_t base_address,
2979 const unsigned char *dwarf_info,
2980 size_t dwarf_info_size,
2981 const unsigned char *dwarf_line,
2982 size_t dwarf_line_size,
2983 const unsigned char *dwarf_abbrev,
2984 size_t dwarf_abbrev_size,
2985 const unsigned char *dwarf_ranges,
2986 size_t dwarf_ranges_size,
2987 const unsigned char *dwarf_str,
2988 size_t dwarf_str_size,
2989 int is_bigendian,
2990 backtrace_error_callback error_callback,
2991 void *data, fileline *fileline_fn)
2992{
2993 struct dwarf_data *fdata;
2994
2995 fdata = build_dwarf_data (state, base_address, dwarf_info, dwarf_info_size,
2996 dwarf_line, dwarf_line_size, dwarf_abbrev,
2997 dwarf_abbrev_size, dwarf_ranges, dwarf_ranges_size,
2998 dwarf_str, dwarf_str_size, is_bigendian,
2999 error_callback, data);
3000 if (fdata == NULL)
3001 return 0;
3002
3003 if (!state->threaded)
3004 {
3005 struct dwarf_data **pp;
3006
3007 for (pp = (struct dwarf_data **) (void *) &state->fileline_data;
3008 *pp != NULL;
3009 pp = &(*pp)->next)
3010 ;
3011 *pp = fdata;
3012 }
3013 else
3014 {
3015 while (1)
3016 {
3017 struct dwarf_data **pp;
3018
3019 pp = (struct dwarf_data **) (void *) &state->fileline_data;
3020
3021 while (1)
3022 {
3023 struct dwarf_data *p;
3024
3025 p = backtrace_atomic_load_pointer (pp);
3026
3027 if (p == NULL)
3028 break;
3029
3030 pp = &p->next;
3031 }
3032
3033 if (__sync_bool_compare_and_swap (pp, NULL, fdata))
3034 break;
3035 }
3036 }
3037
3038 *fileline_fn = dwarf_fileline;
3039
3040 return 1;
3041}
3042