1	/* dwarf.c -- Get file/line information from DWARF for backtraces.
2	Copyright (C) 2012-2025 Free Software Foundation, Inc.
3	Written by Ian Lance Taylor, Google.
4
5	Redistribution and use in source and binary forms, with or without
6	modification, are permitted provided that the following conditions are
7	met:
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
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. */
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
50	static size_t
51	xstrnlen (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
67	struct 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
89	struct attr
90	{
91	/* The attribute name. */
92	enum dwarf_attribute name;
93	/* The attribute form. */
94	enum dwarf_form form;
95	/* The attribute value, for DW_FORM_implicit_const. */
96	int64_t val;
97	};
98
99	/* A single DWARF abbreviation. */
100
101	struct abbrev
102	{
103	/* The abbrev code--the number used to refer to the abbrev. */
104	uint64_t code;
105	/* The entry tag. */
106	enum dwarf_tag tag;
107	/* Non-zero if this abbrev has child entries. */
108	int has_children;
109	/* The number of attributes. */
110	size_t num_attrs;
111	/* The attributes. */
112	struct attr *attrs;
113	};
114
115	/* The DWARF abbreviations for a compilation unit. This structure
116	only exists while reading the compilation unit. Most DWARF readers
117	seem to a hash table to map abbrev ID's to abbrev entries.
118	However, we primarily care about GCC, and GCC simply issues ID's in
119	numerical order starting at 1. So we simply keep a sorted vector,
120	and try to just look up the code. */
121
122	struct abbrevs
123	{
124	/* The number of abbrevs in the vector. */
125	size_t num_abbrevs;
126	/* The abbrevs, sorted by the code field. */
127	struct abbrev *abbrevs;
128	};
129
130	/* The different kinds of attribute values. */
131
132	enum attr_val_encoding
133	{
134	/* No attribute value. */
135	ATTR_VAL_NONE,
136	/* An address. */
137	ATTR_VAL_ADDRESS,
138	/* An index into the .debug_addr section, whose value is relative to
139	the DW_AT_addr_base attribute of the compilation unit. */
140	ATTR_VAL_ADDRESS_INDEX,
141	/* A unsigned integer. */
142	ATTR_VAL_UINT,
143	/* A sigd integer. */
144	ATTR_VAL_SINT,
145	/* A string. */
146	ATTR_VAL_STRING,
147	/* An index into the .debug_str_offsets section. */
148	ATTR_VAL_STRING_INDEX,
149	/* An offset to other data in the containing unit. */
150	ATTR_VAL_REF_UNIT,
151	/* An offset to other data within the .debug_info section. */
152	ATTR_VAL_REF_INFO,
153	/* An offset to other data within the alt .debug_info section. */
154	ATTR_VAL_REF_ALT_INFO,
155	/* An offset to data in some other section. */
156	ATTR_VAL_REF_SECTION,
157	/* A type signature. */
158	ATTR_VAL_REF_TYPE,
159	/* An index into the .debug_rnglists section. */
160	ATTR_VAL_RNGLISTS_INDEX,
161	/* A block of data (not represented). */
162	ATTR_VAL_BLOCK,
163	/* An expression (not represented). */
164	ATTR_VAL_EXPR,
165	};
166
167	/* An attribute value. */
168
169	struct attr_val
170	{
171	/* How the value is stored in the field u. */
172	enum attr_val_encoding encoding;
173	union
174	{
175	/* ATTR_VAL_ADDRESS*, ATTR_VAL_UINT, ATTR_VAL_REF*. */
176	uint64_t uint;
177	/* ATTR_VAL_SINT. */
178	int64_t sint;
179	/* ATTR_VAL_STRING. */
180	const char *string;
181	/* ATTR_VAL_BLOCK not stored. */
182	} u;
183	};
184
185	/* The line number program header. */
186
187	struct line_header
188	{
189	/* The version of the line number information. */
190	int version;
191	/* Address size. */
192	int addrsize;
193	/* The minimum instruction length. */
194	unsigned int min_insn_len;
195	/* The maximum number of ops per instruction. */
196	unsigned int max_ops_per_insn;
197	/* The line base for special opcodes. */
198	int line_base;
199	/* The line range for special opcodes. */
200	unsigned int line_range;
201	/* The opcode base--the first special opcode. */
202	unsigned int opcode_base;
203	/* Opcode lengths, indexed by opcode - 1. */
204	const unsigned char *opcode_lengths;
205	/* The number of directory entries. */
206	size_t dirs_count;
207	/* The directory entries. */
208	const char **dirs;
209	/* The number of filenames. */
210	size_t filenames_count;
211	/* The filenames. */
212	const char **filenames;
213	};
214
215	/* A format description from a line header. */
216
217	struct line_header_format
218	{
219	int lnct; /* LNCT code. */
220	enum dwarf_form form; /* Form of entry data. */
221	};
222
223	/* Map a single PC value to a file/line. We will keep a vector of
224	these sorted by PC value. Each file/line will be correct from the
225	PC up to the PC of the next entry if there is one. We allocate one
226	extra entry at the end so that we can use bsearch. */
227
228	struct line
229	{
230	/* PC. */
231	uintptr_t pc;
232	/* File name. Many entries in the array are expected to point to
233	the same file name. */
234	const char *filename;
235	/* Line number. */
236	int lineno;
237	/* Index of the object in the original array read from the DWARF
238	section, before it has been sorted. The index makes it possible
239	to use Quicksort and maintain stability. */
240	int idx;
241	};
242
243	/* A growable vector of line number information. This is used while
244	reading the line numbers. */
245
246	struct line_vector
247	{
248	/* Memory. This is an array of struct line. */
249	struct backtrace_vector vec;
250	/* Number of valid mappings. */
251	size_t count;
252	};
253
254	/* A function described in the debug info. */
255
256	struct function
257	{
258	/* The name of the function. */
259	const char *name;
260	/* If this is an inlined function, the filename of the call
261	site. */
262	const char *caller_filename;
263	/* If this is an inlined function, the line number of the call
264	site. */
265	int caller_lineno;
266	/* Map PC ranges to inlined functions. */
267	struct function_addrs *function_addrs;
268	size_t function_addrs_count;
269	};
270
271	/* An address range for a function. This maps a PC value to a
272	specific function. */
273
274	struct function_addrs
275	{
276	/* Range is LOW <= PC < HIGH. */
277	uintptr_t low;
278	uintptr_t high;
279	/* Function for this address range. */
280	struct function *function;
281	};
282
283	/* A growable vector of function address ranges. */
284
285	struct function_vector
286	{
287	/* Memory. This is an array of struct function_addrs. */
288	struct backtrace_vector vec;
289	/* Number of address ranges present. */
290	size_t count;
291	};
292
293	/* A DWARF compilation unit. This only holds the information we need
294	to map a PC to a file and line. */
295
296	struct unit
297	{
298	/* The first entry for this compilation unit. */
299	const unsigned char *unit_data;
300	/* The length of the data for this compilation unit. */
301	size_t unit_data_len;
302	/* The offset of UNIT_DATA from the start of the information for
303	this compilation unit. */
304	size_t unit_data_offset;
305	/* Offset of the start of the compilation unit from the start of the
306	.debug_info section. */
307	size_t low_offset;
308	/* Offset of the end of the compilation unit from the start of the
309	.debug_info section. */
310	size_t high_offset;
311	/* DWARF version. */
312	int version;
313	/* Whether unit is DWARF64. */
314	int is_dwarf64;
315	/* Address size. */
316	int addrsize;
317	/* Offset into line number information. */
318	off_t lineoff;
319	/* Offset of compilation unit in .debug_str_offsets. */
320	uint64_t str_offsets_base;
321	/* Offset of compilation unit in .debug_addr. */
322	uint64_t addr_base;
323	/* Offset of compilation unit in .debug_rnglists. */
324	uint64_t rnglists_base;
325	/* Primary source file. */
326	const char *filename;
327	/* Compilation command working directory. */
328	const char *comp_dir;
329	/* Absolute file name, only set if needed. */
330	const char *abs_filename;
331	/* The abbreviations for this unit. */
332	struct abbrevs abbrevs;
333
334	/* The fields above this point are read in during initialization and
335	may be accessed freely. The fields below this point are read in
336	as needed, and therefore require care, as different threads may
337	try to initialize them simultaneously. */
338
339	/* PC to line number mapping. This is NULL if the values have not
340	been read. This is (struct line *) -1 if there was an error
341	reading the values. */
342	struct line *lines;
343	/* Number of entries in lines. */
344	size_t lines_count;
345	/* PC ranges to function. */
346	struct function_addrs *function_addrs;
347	size_t function_addrs_count;
348	};
349
350	/* An address range for a compilation unit. This maps a PC value to a
351	specific compilation unit. Note that we invert the representation
352	in DWARF: instead of listing the units and attaching a list of
353	ranges, we list the ranges and have each one point to the unit.
354	This lets us do a binary search to find the unit. */
355
356	struct unit_addrs
357	{
358	/* Range is LOW <= PC < HIGH. */
359	uintptr_t low;
360	uintptr_t high;
361	/* Compilation unit for this address range. */
362	struct unit *u;
363	};
364
365	/* A growable vector of compilation unit address ranges. */
366
367	struct unit_addrs_vector
368	{
369	/* Memory. This is an array of struct unit_addrs. */
370	struct backtrace_vector vec;
371	/* Number of address ranges present. */
372	size_t count;
373	};
374
375	/* A growable vector of compilation unit pointer. */
376
377	struct unit_vector
378	{
379	struct backtrace_vector vec;
380	size_t count;
381	};
382
383	/* The information we need to map a PC to a file and line. */
384
385	struct dwarf_data
386	{
387	/* The data for the next file we know about. */
388	struct dwarf_data *next;
389	/* The data for .gnu_debugaltlink. */
390	struct dwarf_data *altlink;
391	/* The base address mapping for this file. */
392	struct libbacktrace_base_address base_address;
393	/* A sorted list of address ranges. */
394	struct unit_addrs *addrs;
395	/* Number of address ranges in list. */
396	size_t addrs_count;
397	/* A sorted list of units. */
398	struct unit **units;
399	/* Number of units in the list. */
400	size_t units_count;
401	/* The unparsed DWARF debug data. */
402	struct dwarf_sections dwarf_sections;
403	/* Whether the data is big-endian or not. */
404	int is_bigendian;
405	/* A vector used for function addresses. We keep this here so that
406	we can grow the vector as we read more functions. */
407	struct function_vector fvec;
408	};
409
410	/* Report an error for a DWARF buffer. */
411
412	static void
413	dwarf_buf_error (struct dwarf_buf *buf, const char *msg, int errnum)
414	{
415	char b[200];
416
417	snprintf (s: b, maxlen: sizeof b, format: "%s in %s at %d",
418	msg, buf->name, (int) (buf->buf - buf->start));
419	buf->error_callback (buf->data, b, errnum);
420	}
421
422	/* Require at least COUNT bytes in BUF. Return 1 if all is well, 0 on
423	error. */
424
425	static int
426	require (struct dwarf_buf *buf, size_t count)
427	{
428	if (buf->left >= count)
429	return 1;
430
431	if (!buf->reported_underflow)
432	{
433	dwarf_buf_error (buf, msg: "DWARF underflow", errnum: 0);
434	buf->reported_underflow = 1;
435	}
436
437	return 0;
438	}
439
440	/* Advance COUNT bytes in BUF. Return 1 if all is well, 0 on
441	error. */
442
443	static int
444	advance (struct dwarf_buf *buf, size_t count)
445	{
446	if (!require (buf, count))
447	return 0;
448	buf->buf += count;
449	buf->left -= count;
450	return 1;
451	}
452
453	/* Read one zero-terminated string from BUF and advance past the string. */
454
455	static const char *
456	read_string (struct dwarf_buf *buf)
457	{
458	const char *p = (const char *)buf->buf;
459	size_t len = strnlen (string: p, maxlen: buf->left);
460
461	/* - If len == left, we ran out of buffer before finding the zero terminator.
462	Generate an error by advancing len + 1.
463	- If len < left, advance by len + 1 to skip past the zero terminator. */
464	size_t count = len + 1;
465
466	if (!advance (buf, count))
467	return NULL;
468
469	return p;
470	}
471
472	/* Read one byte from BUF and advance 1 byte. */
473
474	static unsigned char
475	read_byte (struct dwarf_buf *buf)
476	{
477	const unsigned char *p = buf->buf;
478
479	if (!advance (buf, count: 1))
480	return 0;
481	return p[0];
482	}
483
484	/* Read a signed char from BUF and advance 1 byte. */
485
486	static signed char
487	read_sbyte (struct dwarf_buf *buf)
488	{
489	const unsigned char *p = buf->buf;
490
491	if (!advance (buf, count: 1))
492	return 0;
493	return (*p ^ 0x80) - 0x80;
494	}
495
496	/* Read a uint16 from BUF and advance 2 bytes. */
497
498	static uint16_t
499	read_uint16 (struct dwarf_buf *buf)
500	{
501	const unsigned char *p = buf->buf;
502
503	if (!advance (buf, count: 2))
504	return 0;
505	if (buf->is_bigendian)
506	return ((uint16_t) p[0] << 8) | (uint16_t) p[1];
507	else
508	return ((uint16_t) p[1] << 8) | (uint16_t) p[0];
509	}
510
511	/* Read a 24 bit value from BUF and advance 3 bytes. */
512
513	static uint32_t
514	read_uint24 (struct dwarf_buf *buf)
515	{
516	const unsigned char *p = buf->buf;
517
518	if (!advance (buf, count: 3))
519	return 0;
520	if (buf->is_bigendian)
521	return (((uint32_t) p[0] << 16) | ((uint32_t) p[1] << 8)
522	| (uint32_t) p[2]);
523	else
524	return (((uint32_t) p[2] << 16) | ((uint32_t) p[1] << 8)
525	| (uint32_t) p[0]);
526	}
527
528	/* Read a uint32 from BUF and advance 4 bytes. */
529
530	static uint32_t
531	read_uint32 (struct dwarf_buf *buf)
532	{
533	const unsigned char *p = buf->buf;
534
535	if (!advance (buf, count: 4))
536	return 0;
537	if (buf->is_bigendian)
538	return (((uint32_t) p[0] << 24) | ((uint32_t) p[1] << 16)
539	| ((uint32_t) p[2] << 8) | (uint32_t) p[3]);
540	else
541	return (((uint32_t) p[3] << 24) | ((uint32_t) p[2] << 16)
542	| ((uint32_t) p[1] << 8) | (uint32_t) p[0]);
543	}
544
545	/* Read a uint64 from BUF and advance 8 bytes. */
546
547	static uint64_t
548	read_uint64 (struct dwarf_buf *buf)
549	{
550	const unsigned char *p = buf->buf;
551
552	if (!advance (buf, count: 8))
553	return 0;
554	if (buf->is_bigendian)
555	return (((uint64_t) p[0] << 56) | ((uint64_t) p[1] << 48)
556	| ((uint64_t) p[2] << 40) | ((uint64_t) p[3] << 32)
557	| ((uint64_t) p[4] << 24) | ((uint64_t) p[5] << 16)
558	| ((uint64_t) p[6] << 8) | (uint64_t) p[7]);
559	else
560	return (((uint64_t) p[7] << 56) | ((uint64_t) p[6] << 48)
561	| ((uint64_t) p[5] << 40) | ((uint64_t) p[4] << 32)
562	| ((uint64_t) p[3] << 24) | ((uint64_t) p[2] << 16)
563	| ((uint64_t) p[1] << 8) | (uint64_t) p[0]);
564	}
565
566	/* Read an offset from BUF and advance the appropriate number of
567	bytes. */
568
569	static uint64_t
570	read_offset (struct dwarf_buf *buf, int is_dwarf64)
571	{
572	if (is_dwarf64)
573	return read_uint64 (buf);
574	else
575	return read_uint32 (buf);
576	}
577
578	/* Read an address from BUF and advance the appropriate number of
579	bytes. */
580
581	static uint64_t
582	read_address (struct dwarf_buf *buf, int addrsize)
583	{
584	switch (addrsize)
585	{
586	case 1:
587	return read_byte (buf);
588	case 2:
589	return read_uint16 (buf);
590	case 4:
591	return read_uint32 (buf);
592	case 8:
593	return read_uint64 (buf);
594	default:
595	dwarf_buf_error (buf, msg: "unrecognized address size", errnum: 0);
596	return 0;
597	}
598	}
599
600	/* Return whether a value is the highest possible address, given the
601	address size. */
602
603	static int
604	is_highest_address (uint64_t address, int addrsize)
605	{
606	switch (addrsize)
607	{
608	case 1:
609	return address == (unsigned char) -1;
610	case 2:
611	return address == (uint16_t) -1;
612	case 4:
613	return address == (uint32_t) -1;
614	case 8:
615	return address == (uint64_t) -1;
616	default:
617	return 0;
618	}
619	}
620
621	/* Read an unsigned LEB128 number. */
622
623	static uint64_t
624	read_uleb128 (struct dwarf_buf *buf)
625	{
626	uint64_t ret;
627	unsigned int shift;
628	int overflow;
629	unsigned char b;
630
631	ret = 0;
632	shift = 0;
633	overflow = 0;
634	do
635	{
636	const unsigned char *p;
637
638	p = buf->buf;
639	if (!advance (buf, count: 1))
640	return 0;
641	b = *p;
642	if (shift < 64)
643	ret |= ((uint64_t) (b & 0x7f)) << shift;
644	else if (!overflow)
645	{
646	dwarf_buf_error (buf, msg: "LEB128 overflows uint64_t", errnum: 0);
647	overflow = 1;
648	}
649	shift += 7;
650	}
651	while ((b & 0x80) != 0);
652
653	return ret;
654	}
655
656	/* Read a signed LEB128 number. */
657
658	static int64_t
659	read_sleb128 (struct dwarf_buf *buf)
660	{
661	uint64_t val;
662	unsigned int shift;
663	int overflow;
664	unsigned char b;
665
666	val = 0;
667	shift = 0;
668	overflow = 0;
669	do
670	{
671	const unsigned char *p;
672
673	p = buf->buf;
674	if (!advance (buf, count: 1))
675	return 0;
676	b = *p;
677	if (shift < 64)
678	val |= ((uint64_t) (b & 0x7f)) << shift;
679	else if (!overflow)
680	{
681	dwarf_buf_error (buf, msg: "signed LEB128 overflows uint64_t", errnum: 0);
682	overflow = 1;
683	}
684	shift += 7;
685	}
686	while ((b & 0x80) != 0);
687
688	if ((b & 0x40) != 0 && shift < 64)
689	val |= ((uint64_t) -1) << shift;
690
691	return (int64_t) val;
692	}
693
694	/* Return the length of an LEB128 number. */
695
696	static size_t
697	leb128_len (const unsigned char *p)
698	{
699	size_t ret;
700
701	ret = 1;
702	while ((*p & 0x80) != 0)
703	{
704	++p;
705	++ret;
706	}
707	return ret;
708	}
709
710	/* Read initial_length from BUF and advance the appropriate number of bytes. */
711
712	static uint64_t
713	read_initial_length (struct dwarf_buf *buf, int *is_dwarf64)
714	{
715	uint64_t len;
716
717	len = read_uint32 (buf);
718	if (len == 0xffffffff)
719	{
720	len = read_uint64 (buf);
721	*is_dwarf64 = 1;
722	}
723	else
724	*is_dwarf64 = 0;
725
726	return len;
727	}
728
729	/* Free an abbreviations structure. */
730
731	static void
732	free_abbrevs (struct backtrace_state *state, struct abbrevs *abbrevs,
733	backtrace_error_callback error_callback, void *data)
734	{
735	size_t i;
736
737	for (i = 0; i < abbrevs->num_abbrevs; ++i)
738	backtrace_free (state, mem: abbrevs->abbrevs[i].attrs,
739	size: abbrevs->abbrevs[i].num_attrs * sizeof (struct attr),
740	error_callback, data);
741	backtrace_free (state, mem: abbrevs->abbrevs,
742	size: abbrevs->num_abbrevs * sizeof (struct abbrev),
743	error_callback, data);
744	abbrevs->num_abbrevs = 0;
745	abbrevs->abbrevs = NULL;
746	}
747
748	/* Read an attribute value. Returns 1 on success, 0 on failure. If
749	the value can be represented as a uint64_t, sets *VAL and sets
750	*IS_VALID to 1. We don't try to store the value of other attribute
751	forms, because we don't care about them. */
752
753	static int
754	read_attribute (enum dwarf_form form, uint64_t implicit_val,
755	struct dwarf_buf *buf, int is_dwarf64, int version,
756	int addrsize, const struct dwarf_sections *dwarf_sections,
757	struct dwarf_data *altlink, struct attr_val *val)
758	{
759	/* Avoid warnings about val.u.FIELD may be used uninitialized if
760	this function is inlined. The warnings aren't valid but can
761	occur because the different fields are set and used
762	conditionally. */
763	memset (s: val, c: 0, n: sizeof *val);
764
765	switch (form)
766	{
767	case DW_FORM_addr:
768	val->encoding = ATTR_VAL_ADDRESS;
769	val->u.uint = read_address (buf, addrsize);
770	return 1;
771	case DW_FORM_block2:
772	val->encoding = ATTR_VAL_BLOCK;
773	return advance (buf, count: read_uint16 (buf));
774	case DW_FORM_block4:
775	val->encoding = ATTR_VAL_BLOCK;
776	return advance (buf, count: read_uint32 (buf));
777	case DW_FORM_data2:
778	val->encoding = ATTR_VAL_UINT;
779	val->u.uint = read_uint16 (buf);
780	return 1;
781	case DW_FORM_data4:
782	val->encoding = ATTR_VAL_UINT;
783	val->u.uint = read_uint32 (buf);
784	return 1;
785	case DW_FORM_data8:
786	val->encoding = ATTR_VAL_UINT;
787	val->u.uint = read_uint64 (buf);
788	return 1;
789	case DW_FORM_data16:
790	val->encoding = ATTR_VAL_BLOCK;
791	return advance (buf, count: 16);
792	case DW_FORM_string:
793	val->encoding = ATTR_VAL_STRING;
794	val->u.string = read_string (buf);
795	return val->u.string == NULL ? 0 : 1;
796	case DW_FORM_block:
797	val->encoding = ATTR_VAL_BLOCK;
798	return advance (buf, count: read_uleb128 (buf));
799	case DW_FORM_block1:
800	val->encoding = ATTR_VAL_BLOCK;
801	return advance (buf, count: read_byte (buf));
802	case DW_FORM_data1:
803	val->encoding = ATTR_VAL_UINT;
804	val->u.uint = read_byte (buf);
805	return 1;
806	case DW_FORM_flag:
807	val->encoding = ATTR_VAL_UINT;
808	val->u.uint = read_byte (buf);
809	return 1;
810	case DW_FORM_sdata:
811	val->encoding = ATTR_VAL_SINT;
812	val->u.sint = read_sleb128 (buf);
813	return 1;
814	case DW_FORM_strp:
815	{
816	uint64_t offset;
817
818	offset = read_offset (buf, is_dwarf64);
819	if (offset >= dwarf_sections->size[DEBUG_STR])
820	{
821	dwarf_buf_error (buf, msg: "DW_FORM_strp out of range", errnum: 0);
822	return 0;
823	}
824	val->encoding = ATTR_VAL_STRING;
825	val->u.string =
826	(const char *) dwarf_sections->data[DEBUG_STR] + offset;
827	return 1;
828	}
829	case DW_FORM_line_strp:
830	{
831	uint64_t offset;
832
833	offset = read_offset (buf, is_dwarf64);
834	if (offset >= dwarf_sections->size[DEBUG_LINE_STR])
835	{
836	dwarf_buf_error (buf, msg: "DW_FORM_line_strp out of range", errnum: 0);
837	return 0;
838	}
839	val->encoding = ATTR_VAL_STRING;
840	val->u.string =
841	(const char *) dwarf_sections->data[DEBUG_LINE_STR] + offset;
842	return 1;
843	}
844	case DW_FORM_udata:
845	val->encoding = ATTR_VAL_UINT;
846	val->u.uint = read_uleb128 (buf);
847	return 1;
848	case DW_FORM_ref_addr:
849	val->encoding = ATTR_VAL_REF_INFO;
850	if (version == 2)
851	val->u.uint = read_address (buf, addrsize);
852	else
853	val->u.uint = read_offset (buf, is_dwarf64);
854	return 1;
855	case DW_FORM_ref1:
856	val->encoding = ATTR_VAL_REF_UNIT;
857	val->u.uint = read_byte (buf);
858	return 1;
859	case DW_FORM_ref2:
860	val->encoding = ATTR_VAL_REF_UNIT;
861	val->u.uint = read_uint16 (buf);
862	return 1;
863	case DW_FORM_ref4:
864	val->encoding = ATTR_VAL_REF_UNIT;
865	val->u.uint = read_uint32 (buf);
866	return 1;
867	case DW_FORM_ref8:
868	val->encoding = ATTR_VAL_REF_UNIT;
869	val->u.uint = read_uint64 (buf);
870	return 1;
871	case DW_FORM_ref_udata:
872	val->encoding = ATTR_VAL_REF_UNIT;
873	val->u.uint = read_uleb128 (buf);
874	return 1;
875	case DW_FORM_indirect:
876	{
877	uint64_t form;
878
879	form = read_uleb128 (buf);
880	if (form == DW_FORM_implicit_const)
881	{
882	dwarf_buf_error (buf,
883	msg: "DW_FORM_indirect to DW_FORM_implicit_const",
884	errnum: 0);
885	return 0;
886	}
887	return read_attribute (form: (enum dwarf_form) form, implicit_val: 0, buf, is_dwarf64,
888	version, addrsize, dwarf_sections, altlink,
889	val);
890	}
891	case DW_FORM_sec_offset:
892	val->encoding = ATTR_VAL_REF_SECTION;
893	val->u.uint = read_offset (buf, is_dwarf64);
894	return 1;
895	case DW_FORM_exprloc:
896	val->encoding = ATTR_VAL_EXPR;
897	return advance (buf, count: read_uleb128 (buf));
898	case DW_FORM_flag_present:
899	val->encoding = ATTR_VAL_UINT;
900	val->u.uint = 1;
901	return 1;
902	case DW_FORM_ref_sig8:
903	val->encoding = ATTR_VAL_REF_TYPE;
904	val->u.uint = read_uint64 (buf);
905	return 1;
906	case DW_FORM_strx: case DW_FORM_strx1: case DW_FORM_strx2:
907	case DW_FORM_strx3: case DW_FORM_strx4:
908	{
909	uint64_t offset;
910
911	switch (form)
912	{
913	case DW_FORM_strx:
914	offset = read_uleb128 (buf);
915	break;
916	case DW_FORM_strx1:
917	offset = read_byte (buf);
918	break;
919	case DW_FORM_strx2:
920	offset = read_uint16 (buf);
921	break;
922	case DW_FORM_strx3:
923	offset = read_uint24 (buf);
924	break;
925	case DW_FORM_strx4:
926	offset = read_uint32 (buf);
927	break;
928	default:
929	/* This case can't happen. */
930	return 0;
931	}
932	val->encoding = ATTR_VAL_STRING_INDEX;
933	val->u.uint = offset;
934	return 1;
935	}
936	case DW_FORM_addrx: case DW_FORM_addrx1: case DW_FORM_addrx2:
937	case DW_FORM_addrx3: case DW_FORM_addrx4:
938	{
939	uint64_t offset;
940
941	switch (form)
942	{
943	case DW_FORM_addrx:
944	offset = read_uleb128 (buf);
945	break;
946	case DW_FORM_addrx1:
947	offset = read_byte (buf);
948	break;
949	case DW_FORM_addrx2:
950	offset = read_uint16 (buf);
951	break;
952	case DW_FORM_addrx3:
953	offset = read_uint24 (buf);
954	break;
955	case DW_FORM_addrx4:
956	offset = read_uint32 (buf);
957	break;
958	default:
959	/* This case can't happen. */
960	return 0;
961	}
962	val->encoding = ATTR_VAL_ADDRESS_INDEX;
963	val->u.uint = offset;
964	return 1;
965	}
966	case DW_FORM_ref_sup4:
967	val->encoding = ATTR_VAL_REF_SECTION;
968	val->u.uint = read_uint32 (buf);
969	return 1;
970	case DW_FORM_ref_sup8:
971	val->encoding = ATTR_VAL_REF_SECTION;
972	val->u.uint = read_uint64 (buf);
973	return 1;
974	case DW_FORM_implicit_const:
975	val->encoding = ATTR_VAL_UINT;
976	val->u.uint = implicit_val;
977	return 1;
978	case DW_FORM_loclistx:
979	/* We don't distinguish this from DW_FORM_sec_offset. It
980	* shouldn't matter since we don't care about loclists. */
981	val->encoding = ATTR_VAL_REF_SECTION;
982	val->u.uint = read_uleb128 (buf);
983	return 1;
984	case DW_FORM_rnglistx:
985	val->encoding = ATTR_VAL_RNGLISTS_INDEX;
986	val->u.uint = read_uleb128 (buf);
987	return 1;
988	case DW_FORM_GNU_addr_index:
989	val->encoding = ATTR_VAL_REF_SECTION;
990	val->u.uint = read_uleb128 (buf);
991	return 1;
992	case DW_FORM_GNU_str_index:
993	val->encoding = ATTR_VAL_REF_SECTION;
994	val->u.uint = read_uleb128 (buf);
995	return 1;
996	case DW_FORM_GNU_ref_alt:
997	val->u.uint = read_offset (buf, is_dwarf64);
998	if (altlink == NULL)
999	{
1000	val->encoding = ATTR_VAL_NONE;
1001	return 1;
1002	}
1003	val->encoding = ATTR_VAL_REF_ALT_INFO;
1004	return 1;
1005	case DW_FORM_strp_sup: case DW_FORM_GNU_strp_alt:
1006	{
1007	uint64_t offset;
1008
1009	offset = read_offset (buf, is_dwarf64);
1010	if (altlink == NULL)
1011	{
1012	val->encoding = ATTR_VAL_NONE;
1013	return 1;
1014	}
1015	if (offset >= altlink->dwarf_sections.size[DEBUG_STR])
1016	{
1017	dwarf_buf_error (buf, msg: "DW_FORM_strp_sup out of range", errnum: 0);
1018	return 0;
1019	}
1020	val->encoding = ATTR_VAL_STRING;
1021	val->u.string =
1022	(const char *) altlink->dwarf_sections.data[DEBUG_STR] + offset;
1023	return 1;
1024	}
1025	default:
1026	dwarf_buf_error (buf, msg: "unrecognized DWARF form", errnum: -1);
1027	return 0;
1028	}
1029	}
1030
1031	/* If we can determine the value of a string attribute, set *STRING to
1032	point to the string. Return 1 on success, 0 on error. If we don't
1033	know the value, we consider that a success, and we don't change
1034	*STRING. An error is only reported for some sort of out of range
1035	offset. */
1036
1037	static int
1038	resolve_string (const struct dwarf_sections *dwarf_sections, int is_dwarf64,
1039	int is_bigendian, uint64_t str_offsets_base,
1040	const struct attr_val *val,
1041	backtrace_error_callback error_callback, void *data,
1042	const char **string)
1043	{
1044	switch (val->encoding)
1045	{
1046	case ATTR_VAL_STRING:
1047	*string = val->u.string;
1048	return 1;
1049
1050	case ATTR_VAL_STRING_INDEX:
1051	{
1052	uint64_t offset;
1053	struct dwarf_buf offset_buf;
1054
1055	offset = val->u.uint * (is_dwarf64 ? 8 : 4) + str_offsets_base;
1056	if (offset + (is_dwarf64 ? 8 : 4)
1057	> dwarf_sections->size[DEBUG_STR_OFFSETS])
1058	{
1059	error_callback (data, "DW_FORM_strx value out of range", 0);
1060	return 0;
1061	}
1062
1063	offset_buf.name = ".debug_str_offsets";
1064	offset_buf.start = dwarf_sections->data[DEBUG_STR_OFFSETS];
1065	offset_buf.buf = dwarf_sections->data[DEBUG_STR_OFFSETS] + offset;
1066	offset_buf.left = dwarf_sections->size[DEBUG_STR_OFFSETS] - offset;
1067	offset_buf.is_bigendian = is_bigendian;
1068	offset_buf.error_callback = error_callback;
1069	offset_buf.data = data;
1070	offset_buf.reported_underflow = 0;
1071
1072	offset = read_offset (buf: &offset_buf, is_dwarf64);
1073	if (offset >= dwarf_sections->size[DEBUG_STR])
1074	{
1075	dwarf_buf_error (buf: &offset_buf,
1076	msg: "DW_FORM_strx offset out of range",
1077	errnum: 0);
1078	return 0;
1079	}
1080	*string = (const char *) dwarf_sections->data[DEBUG_STR] + offset;
1081	return 1;
1082	}
1083
1084	default:
1085	return 1;
1086	}
1087	}
1088
1089	/* Set *ADDRESS to the real address for a ATTR_VAL_ADDRESS_INDEX.
1090	Return 1 on success, 0 on error. */
1091
1092	static int
1093	resolve_addr_index (const struct dwarf_sections *dwarf_sections,
1094	uint64_t addr_base, int addrsize, int is_bigendian,
1095	uint64_t addr_index,
1096	backtrace_error_callback error_callback, void *data,
1097	uintptr_t *address)
1098	{
1099	uint64_t offset;
1100	struct dwarf_buf addr_buf;
1101
1102	offset = addr_index * addrsize + addr_base;
1103	if (offset + addrsize > dwarf_sections->size[DEBUG_ADDR])
1104	{
1105	error_callback (data, "DW_FORM_addrx value out of range", 0);
1106	return 0;
1107	}
1108
1109	addr_buf.name = ".debug_addr";
1110	addr_buf.start = dwarf_sections->data[DEBUG_ADDR];
1111	addr_buf.buf = dwarf_sections->data[DEBUG_ADDR] + offset;
1112	addr_buf.left = dwarf_sections->size[DEBUG_ADDR] - offset;
1113	addr_buf.is_bigendian = is_bigendian;
1114	addr_buf.error_callback = error_callback;
1115	addr_buf.data = data;
1116	addr_buf.reported_underflow = 0;
1117
1118	*address = (uintptr_t) read_address (buf: &addr_buf, addrsize);
1119	return 1;
1120	}
1121
1122	/* Compare a unit offset against a unit for bsearch. */
1123
1124	static int
1125	units_search (const void *vkey, const void *ventry)
1126	{
1127	const size_t *key = (const size_t *) vkey;
1128	const struct unit *entry = *((const struct unit *const *) ventry);
1129	size_t offset;
1130
1131	offset = *key;
1132	if (offset < entry->low_offset)
1133	return -1;
1134	else if (offset >= entry->high_offset)
1135	return 1;
1136	else
1137	return 0;
1138	}
1139
1140	/* Find a unit in PU containing OFFSET. */
1141
1142	static struct unit *
1143	find_unit (struct unit **pu, size_t units_count, size_t offset)
1144	{
1145	struct unit **u;
1146	u = bsearch (key: &offset, base: pu, nmemb: units_count, size: sizeof (struct unit *), compar: units_search);
1147	return u == NULL ? NULL : *u;
1148	}
1149
1150	/* Compare function_addrs for qsort. When ranges are nested, make the
1151	smallest one sort last. */
1152
1153	static int
1154	function_addrs_compare (const void *v1, const void *v2)
1155	{
1156	const struct function_addrs *a1 = (const struct function_addrs *) v1;
1157	const struct function_addrs *a2 = (const struct function_addrs *) v2;
1158
1159	if (a1->low < a2->low)
1160	return -1;
1161	if (a1->low > a2->low)
1162	return 1;
1163	if (a1->high < a2->high)
1164	return 1;
1165	if (a1->high > a2->high)
1166	return -1;
1167	return strcmp (s1: a1->function->name, s2: a2->function->name);
1168	}
1169
1170	/* Compare a PC against a function_addrs for bsearch. We always
1171	allocate an entra entry at the end of the vector, so that this
1172	routine can safely look at the next entry. Note that if there are
1173	multiple ranges containing PC, which one will be returned is
1174	unpredictable. We compensate for that in dwarf_fileline. */
1175
1176	static int
1177	function_addrs_search (const void *vkey, const void *ventry)
1178	{
1179	const uintptr_t *key = (const uintptr_t *) vkey;
1180	const struct function_addrs *entry = (const struct function_addrs *) ventry;
1181	uintptr_t pc;
1182
1183	pc = *key;
1184	if (pc < entry->low)
1185	return -1;
1186	else if (pc > (entry + 1)->low)
1187	return 1;
1188	else
1189	return 0;
1190	}
1191
1192	/* Add a new compilation unit address range to a vector. This is
1193	called via add_ranges. Returns 1 on success, 0 on failure. */
1194
1195	static int
1196	add_unit_addr (struct backtrace_state *state, void *rdata,
1197	uintptr_t lowpc, uintptr_t highpc,
1198	backtrace_error_callback error_callback, void *data,
1199	void *pvec)
1200	{
1201	struct unit *u = (struct unit *) rdata;
1202	struct unit_addrs_vector *vec = (struct unit_addrs_vector *) pvec;
1203	struct unit_addrs *p;
1204
1205	/* Try to merge with the last entry. */
1206	if (vec->count > 0)
1207	{
1208	p = (struct unit_addrs *) vec->vec.base + (vec->count - 1);
1209	if ((lowpc == p->high || lowpc == p->high + 1)
1210	&& u == p->u)
1211	{
1212	if (highpc > p->high)
1213	p->high = highpc;
1214	return 1;
1215	}
1216	}
1217
1218	p = ((struct unit_addrs *)
1219	backtrace_vector_grow (state, size: sizeof (struct unit_addrs),
1220	error_callback, data, vec: &vec->vec));
1221	if (p == NULL)
1222	return 0;
1223
1224	p->low = lowpc;
1225	p->high = highpc;
1226	p->u = u;
1227
1228	++vec->count;
1229
1230	return 1;
1231	}
1232
1233	/* Compare unit_addrs for qsort. When ranges are nested, make the
1234	smallest one sort last. */
1235
1236	static int
1237	unit_addrs_compare (const void *v1, const void *v2)
1238	{
1239	const struct unit_addrs *a1 = (const struct unit_addrs *) v1;
1240	const struct unit_addrs *a2 = (const struct unit_addrs *) v2;
1241
1242	if (a1->low < a2->low)
1243	return -1;
1244	if (a1->low > a2->low)
1245	return 1;
1246	if (a1->high < a2->high)
1247	return 1;
1248	if (a1->high > a2->high)
1249	return -1;
1250	if (a1->u->lineoff < a2->u->lineoff)
1251	return -1;
1252	if (a1->u->lineoff > a2->u->lineoff)
1253	return 1;
1254	return 0;
1255	}
1256
1257	/* Compare a PC against a unit_addrs for bsearch. We always allocate
1258	an entry entry at the end of the vector, so that this routine can
1259	safely look at the next entry. Note that if there are multiple
1260	ranges containing PC, which one will be returned is unpredictable.
1261	We compensate for that in dwarf_fileline. */
1262
1263	static int
1264	unit_addrs_search (const void *vkey, const void *ventry)
1265	{
1266	const uintptr_t *key = (const uintptr_t *) vkey;
1267	const struct unit_addrs *entry = (const struct unit_addrs *) ventry;
1268	uintptr_t pc;
1269
1270	pc = *key;
1271	if (pc < entry->low)
1272	return -1;
1273	else if (pc > (entry + 1)->low)
1274	return 1;
1275	else
1276	return 0;
1277	}
1278
1279	/* Fill in overlapping ranges as needed. This is a subroutine of
1280	resolve_unit_addrs_overlap. */
1281
1282	static int
1283	resolve_unit_addrs_overlap_walk (struct backtrace_state *state,
1284	size_t *pfrom, size_t *pto,
1285	struct unit_addrs *enclosing,
1286	struct unit_addrs_vector *old_vec,
1287	backtrace_error_callback error_callback,
1288	void *data,
1289	struct unit_addrs_vector *new_vec)
1290	{
1291	struct unit_addrs *old_addrs;
1292	size_t old_count;
1293	struct unit_addrs *new_addrs;
1294	size_t from;
1295	size_t to;
1296
1297	old_addrs = (struct unit_addrs *) old_vec->vec.base;
1298	old_count = old_vec->count;
1299	new_addrs = (struct unit_addrs *) new_vec->vec.base;
1300
1301	for (from = *pfrom, to = *pto; from < old_count; from++, to++)
1302	{
1303	/* If we are in the scope of a larger range that can no longer
1304	cover any further ranges, return back to the caller. */
1305
1306	if (enclosing != NULL
1307	&& enclosing->high <= old_addrs[from].low)
1308	{
1309	*pfrom = from;
1310	*pto = to;
1311	return 1;
1312	}
1313
1314	new_addrs[to] = old_addrs[from];
1315
1316	/* If we are in scope of a larger range, fill in any gaps
1317	between this entry and the next one.
1318
1319	There is an extra entry at the end of the vector, so it's
1320	always OK to refer to from + 1. */
1321
1322	if (enclosing != NULL
1323	&& enclosing->high > old_addrs[from].high
1324	&& old_addrs[from].high < old_addrs[from + 1].low)
1325	{
1326	void *grew;
1327	size_t new_high;
1328
1329	grew = backtrace_vector_grow (state, size: sizeof (struct unit_addrs),
1330	error_callback, data, vec: &new_vec->vec);
1331	if (grew == NULL)
1332	return 0;
1333	new_addrs = (struct unit_addrs *) new_vec->vec.base;
1334	to++;
1335	new_addrs[to].low = old_addrs[from].high;
1336	new_high = old_addrs[from + 1].low;
1337	if (enclosing->high < new_high)
1338	new_high = enclosing->high;
1339	new_addrs[to].high = new_high;
1340	new_addrs[to].u = enclosing->u;
1341	}
1342
1343	/* If this range has a larger scope than the next one, use it to
1344	fill in any gaps. */
1345
1346	if (old_addrs[from].high > old_addrs[from + 1].high)
1347	{
1348	*pfrom = from + 1;
1349	*pto = to + 1;
1350	if (!resolve_unit_addrs_overlap_walk (state, pfrom, pto,
1351	enclosing: &old_addrs[from], old_vec,
1352	error_callback, data, new_vec))
1353	return 0;
1354	from = *pfrom;
1355	to = *pto;
1356
1357	/* Undo the increment the loop is about to do. */
1358	from--;
1359	to--;
1360	}
1361	}
1362
1363	if (enclosing == NULL)
1364	{
1365	struct unit_addrs *pa;
1366
1367	/* Add trailing entry. */
1368
1369	pa = ((struct unit_addrs *)
1370	backtrace_vector_grow (state, size: sizeof (struct unit_addrs),
1371	error_callback, data, vec: &new_vec->vec));
1372	if (pa == NULL)
1373	return 0;
1374	pa->low = 0;
1375	--pa->low;
1376	pa->high = pa->low;
1377	pa->u = NULL;
1378
1379	new_vec->count = to;
1380	}
1381
1382	return 1;
1383	}
1384
1385	/* It is possible for the unit_addrs list to contain overlaps, as in
1386
1387	10: low == 10, high == 20, unit 1
1388	11: low == 12, high == 15, unit 2
1389	12: low == 20, high == 30, unit 1
1390
1391	In such a case, for pc == 17, a search using units_addr_search will
1392	return entry 11. However, pc == 17 doesn't fit in that range. We
1393	actually want range 10.
1394
1395	It seems that in general we might have an arbitrary number of
1396	ranges in between 10 and 12.
1397
1398	To handle this we look for cases where range R1 is followed by
1399	range R2 such that R2 is a strict subset of R1. In such cases we
1400	insert a new range R3 following R2 that fills in the remainder of
1401	the address space covered by R1. That lets a relatively simple
1402	search find the correct range.
1403
1404	These overlaps can occur because of the range merging we do in
1405	add_unit_addr. When the linker de-duplicates functions, it can
1406	leave behind an address range that refers to the address range of
1407	the retained duplicate. If the retained duplicate address range is
1408	merged with others, then after sorting we can see overlapping
1409	address ranges.
1410
1411	See https://github.com/ianlancetaylor/libbacktrace/issues/137. */
1412
1413	static int
1414	resolve_unit_addrs_overlap (struct backtrace_state *state,
1415	backtrace_error_callback error_callback,
1416	void *data, struct unit_addrs_vector *addrs_vec)
1417	{
1418	struct unit_addrs *addrs;
1419	size_t count;
1420	int found;
1421	struct unit_addrs *entry;
1422	size_t i;
1423	struct unit_addrs_vector new_vec;
1424	void *grew;
1425	size_t from;
1426	size_t to;
1427
1428	addrs = (struct unit_addrs *) addrs_vec->vec.base;
1429	count = addrs_vec->count;
1430
1431	if (count == 0)
1432	return 1;
1433
1434	/* Optimistically assume that overlaps are rare. */
1435	found = 0;
1436	entry = addrs;
1437	for (i = 0; i < count - 1; i++)
1438	{
1439	if (entry->low < (entry + 1)->low
1440	&& entry->high > (entry + 1)->high)
1441	{
1442	found = 1;
1443	break;
1444	}
1445	entry++;
1446	}
1447	if (!found)
1448	return 1;
1449
1450	memset (s: &new_vec, c: 0, n: sizeof new_vec);
1451	grew = backtrace_vector_grow (state,
1452	size: count * sizeof (struct unit_addrs),
1453	error_callback, data, vec: &new_vec.vec);
1454	if (grew == NULL)
1455	return 0;
1456
1457	from = 0;
1458	to = 0;
1459	resolve_unit_addrs_overlap_walk (state, pfrom: &from, pto: &to, NULL, old_vec: addrs_vec,
1460	error_callback, data, new_vec: &new_vec);
1461	backtrace_vector_free (state, vec: &addrs_vec->vec, error_callback, data);
1462	*addrs_vec = new_vec;
1463
1464	return 1;
1465	}
1466
1467	/* Sort the line vector by PC. We want a stable sort here to maintain
1468	the order of lines for the same PC values. Since the sequence is
1469	being sorted in place, their addresses cannot be relied on to
1470	maintain stability. That is the purpose of the index member. */
1471
1472	static int
1473	line_compare (const void *v1, const void *v2)
1474	{
1475	const struct line *ln1 = (const struct line *) v1;
1476	const struct line *ln2 = (const struct line *) v2;
1477
1478	if (ln1->pc < ln2->pc)
1479	return -1;
1480	else if (ln1->pc > ln2->pc)
1481	return 1;
1482	else if (ln1->idx < ln2->idx)
1483	return -1;
1484	else if (ln1->idx > ln2->idx)
1485	return 1;
1486	else
1487	return 0;
1488	}
1489
1490	/* Find a PC in a line vector. We always allocate an extra entry at
1491	the end of the lines vector, so that this routine can safely look
1492	at the next entry. Note that when there are multiple mappings for
1493	the same PC value, this will return the last one. */
1494
1495	static int
1496	line_search (const void *vkey, const void *ventry)
1497	{
1498	const uintptr_t *key = (const uintptr_t *) vkey;
1499	const struct line *entry = (const struct line *) ventry;
1500	uintptr_t pc;
1501
1502	pc = *key;
1503	if (pc < entry->pc)
1504	return -1;
1505	else if (pc >= (entry + 1)->pc)
1506	return 1;
1507	else
1508	return 0;
1509	}
1510
1511	/* Sort the abbrevs by the abbrev code. This function is passed to
1512	both qsort and bsearch. */
1513
1514	static int
1515	abbrev_compare (const void *v1, const void *v2)
1516	{
1517	const struct abbrev *a1 = (const struct abbrev *) v1;
1518	const struct abbrev *a2 = (const struct abbrev *) v2;
1519
1520	if (a1->code < a2->code)
1521	return -1;
1522	else if (a1->code > a2->code)
1523	return 1;
1524	else
1525	{
1526	/* This really shouldn't happen. It means there are two
1527	different abbrevs with the same code, and that means we don't
1528	know which one lookup_abbrev should return. */
1529	return 0;
1530	}
1531	}
1532
1533	/* Read the abbreviation table for a compilation unit. Returns 1 on
1534	success, 0 on failure. */
1535
1536	static int
1537	read_abbrevs (struct backtrace_state *state, uint64_t abbrev_offset,
1538	const unsigned char *dwarf_abbrev, size_t dwarf_abbrev_size,
1539	int is_bigendian, backtrace_error_callback error_callback,
1540	void *data, struct abbrevs *abbrevs)
1541	{
1542	struct dwarf_buf abbrev_buf;
1543	struct dwarf_buf count_buf;
1544	size_t num_abbrevs;
1545
1546	abbrevs->num_abbrevs = 0;
1547	abbrevs->abbrevs = NULL;
1548
1549	if (abbrev_offset >= dwarf_abbrev_size)
1550	{
1551	error_callback (data, "abbrev offset out of range", 0);
1552	return 0;
1553	}
1554
1555	abbrev_buf.name = ".debug_abbrev";
1556	abbrev_buf.start = dwarf_abbrev;
1557	abbrev_buf.buf = dwarf_abbrev + abbrev_offset;
1558	abbrev_buf.left = dwarf_abbrev_size - abbrev_offset;
1559	abbrev_buf.is_bigendian = is_bigendian;
1560	abbrev_buf.error_callback = error_callback;
1561	abbrev_buf.data = data;
1562	abbrev_buf.reported_underflow = 0;
1563
1564	/* Count the number of abbrevs in this list. */
1565
1566	count_buf = abbrev_buf;
1567	num_abbrevs = 0;
1568	while (read_uleb128 (buf: &count_buf) != 0)
1569	{
1570	if (count_buf.reported_underflow)
1571	return 0;
1572	++num_abbrevs;
1573	// Skip tag.
1574	read_uleb128 (buf: &count_buf);
1575	// Skip has_children.
1576	read_byte (buf: &count_buf);
1577	// Skip attributes.
1578	while (read_uleb128 (buf: &count_buf) != 0)
1579	{
1580	uint64_t form;
1581
1582	form = read_uleb128 (buf: &count_buf);
1583	if ((enum dwarf_form) form == DW_FORM_implicit_const)
1584	read_sleb128 (buf: &count_buf);
1585	}
1586	// Skip form of last attribute.
1587	read_uleb128 (buf: &count_buf);
1588	}
1589
1590	if (count_buf.reported_underflow)
1591	return 0;
1592
1593	if (num_abbrevs == 0)
1594	return 1;
1595
1596	abbrevs->abbrevs = ((struct abbrev *)
1597	backtrace_alloc (state,
1598	size: num_abbrevs * sizeof (struct abbrev),
1599	error_callback, data));
1600	if (abbrevs->abbrevs == NULL)
1601	return 0;
1602	abbrevs->num_abbrevs = num_abbrevs;
1603	memset (s: abbrevs->abbrevs, c: 0, n: num_abbrevs * sizeof (struct abbrev));
1604
1605	num_abbrevs = 0;
1606	while (1)
1607	{
1608	uint64_t code;
1609	struct abbrev a;
1610	size_t num_attrs;
1611	struct attr *attrs;
1612
1613	if (abbrev_buf.reported_underflow)
1614	goto fail;
1615
1616	code = read_uleb128 (buf: &abbrev_buf);
1617	if (code == 0)
1618	break;
1619
1620	a.code = code;
1621	a.tag = (enum dwarf_tag) read_uleb128 (buf: &abbrev_buf);
1622	a.has_children = read_byte (buf: &abbrev_buf);
1623
1624	count_buf = abbrev_buf;
1625	num_attrs = 0;
1626	while (read_uleb128 (buf: &count_buf) != 0)
1627	{
1628	uint64_t form;
1629
1630	++num_attrs;
1631	form = read_uleb128 (buf: &count_buf);
1632	if ((enum dwarf_form) form == DW_FORM_implicit_const)
1633	read_sleb128 (buf: &count_buf);
1634	}
1635
1636	if (num_attrs == 0)
1637	{
1638	attrs = NULL;
1639	read_uleb128 (buf: &abbrev_buf);
1640	read_uleb128 (buf: &abbrev_buf);
1641	}
1642	else
1643	{
1644	attrs = ((struct attr *)
1645	backtrace_alloc (state, size: num_attrs * sizeof *attrs,
1646	error_callback, data));
1647	if (attrs == NULL)
1648	goto fail;
1649	num_attrs = 0;
1650	while (1)
1651	{
1652	uint64_t name;
1653	uint64_t form;
1654
1655	name = read_uleb128 (buf: &abbrev_buf);
1656	form = read_uleb128 (buf: &abbrev_buf);
1657	if (name == 0)
1658	break;
1659	attrs[num_attrs].name = (enum dwarf_attribute) name;
1660	attrs[num_attrs].form = (enum dwarf_form) form;
1661	if ((enum dwarf_form) form == DW_FORM_implicit_const)
1662	attrs[num_attrs].val = read_sleb128 (buf: &abbrev_buf);
1663	else
1664	attrs[num_attrs].val = 0;
1665	++num_attrs;
1666	}
1667	}
1668
1669	a.num_attrs = num_attrs;
1670	a.attrs = attrs;
1671
1672	abbrevs->abbrevs[num_abbrevs] = a;
1673	++num_abbrevs;
1674	}
1675
1676	backtrace_qsort (base: abbrevs->abbrevs, count: abbrevs->num_abbrevs,
1677	size: sizeof (struct abbrev), compar: abbrev_compare);
1678
1679	return 1;
1680
1681	fail:
1682	free_abbrevs (state, abbrevs, error_callback, data);
1683	return 0;
1684	}
1685
1686	/* Return the abbrev information for an abbrev code. */
1687
1688	static const struct abbrev *
1689	lookup_abbrev (struct abbrevs *abbrevs, uint64_t code,
1690	backtrace_error_callback error_callback, void *data)
1691	{
1692	struct abbrev key;
1693	void *p;
1694
1695	/* With GCC, where abbrevs are simply numbered in order, we should
1696	be able to just look up the entry. */
1697	if (code - 1 < abbrevs->num_abbrevs
1698	&& abbrevs->abbrevs[code - 1].code == code)
1699	return &abbrevs->abbrevs[code - 1];
1700
1701	/* Otherwise we have to search. */
1702	memset (s: &key, c: 0, n: sizeof key);
1703	key.code = code;
1704	p = bsearch (key: &key, base: abbrevs->abbrevs, nmemb: abbrevs->num_abbrevs,
1705	size: sizeof (struct abbrev), compar: abbrev_compare);
1706	if (p == NULL)
1707	{
1708	error_callback (data, "invalid abbreviation code", 0);
1709	return NULL;
1710	}
1711	return (const struct abbrev *) p;
1712	}
1713
1714	/* This struct is used to gather address range information while
1715	reading attributes. We use this while building a mapping from
1716	address ranges to compilation units and then again while mapping
1717	from address ranges to function entries. Normally either
1718	lowpc/highpc is set or ranges is set. */
1719
1720	struct pcrange {
1721	uintptr_t lowpc; /* The low PC value. */
1722	int have_lowpc; /* Whether a low PC value was found. */
1723	int lowpc_is_addr_index; /* Whether lowpc is in .debug_addr. */
1724	uintptr_t highpc; /* The high PC value. */
1725	int have_highpc; /* Whether a high PC value was found. */
1726	int highpc_is_relative; /* Whether highpc is relative to lowpc. */
1727	int highpc_is_addr_index; /* Whether highpc is in .debug_addr. */
1728	uint64_t ranges; /* Offset in ranges section. */
1729	int have_ranges; /* Whether ranges is valid. */
1730	int ranges_is_index; /* Whether ranges is DW_FORM_rnglistx. */
1731	};
1732
1733	/* Update PCRANGE from an attribute value. */
1734
1735	static void
1736	update_pcrange (const struct attr* attr, const struct attr_val* val,
1737	struct pcrange *pcrange)
1738	{
1739	switch (attr->name)
1740	{
1741	case DW_AT_low_pc:
1742	if (val->encoding == ATTR_VAL_ADDRESS)
1743	{
1744	pcrange->lowpc = (uintptr_t) val->u.uint;
1745	pcrange->have_lowpc = 1;
1746	}
1747	else if (val->encoding == ATTR_VAL_ADDRESS_INDEX)
1748	{
1749	pcrange->lowpc = (uintptr_t) val->u.uint;
1750	pcrange->have_lowpc = 1;
1751	pcrange->lowpc_is_addr_index = 1;
1752	}
1753	break;
1754
1755	case DW_AT_high_pc:
1756	if (val->encoding == ATTR_VAL_ADDRESS)
1757	{
1758	pcrange->highpc = (uintptr_t) val->u.uint;
1759	pcrange->have_highpc = 1;
1760	}
1761	else if (val->encoding == ATTR_VAL_UINT)
1762	{
1763	pcrange->highpc = (uintptr_t) val->u.uint;
1764	pcrange->have_highpc = 1;
1765	pcrange->highpc_is_relative = 1;
1766	}
1767	else if (val->encoding == ATTR_VAL_ADDRESS_INDEX)
1768	{
1769	pcrange->highpc = (uintptr_t) val->u.uint;
1770	pcrange->have_highpc = 1;
1771	pcrange->highpc_is_addr_index = 1;
1772	}
1773	break;
1774
1775	case DW_AT_ranges:
1776	if (val->encoding == ATTR_VAL_UINT
1777	|| val->encoding == ATTR_VAL_REF_SECTION)
1778	{
1779	pcrange->ranges = val->u.uint;
1780	pcrange->have_ranges = 1;
1781	}
1782	else if (val->encoding == ATTR_VAL_RNGLISTS_INDEX)
1783	{
1784	pcrange->ranges = val->u.uint;
1785	pcrange->have_ranges = 1;
1786	pcrange->ranges_is_index = 1;
1787	}
1788	break;
1789
1790	default:
1791	break;
1792	}
1793	}
1794
1795	/* Call ADD_RANGE for a low/high PC pair. Returns 1 on success, 0 on
1796	error. */
1797
1798	static int
1799	add_low_high_range (struct backtrace_state *state,
1800	const struct dwarf_sections *dwarf_sections,
1801	struct libbacktrace_base_address base_address,
1802	int is_bigendian, struct unit *u,
1803	const struct pcrange *pcrange,
1804	int (*add_range) (struct backtrace_state *state,
1805	void *rdata, uintptr_t lowpc,
1806	uintptr_t highpc,
1807	backtrace_error_callback error_callback,
1808	void *data, void *vec),
1809	void *rdata,
1810	backtrace_error_callback error_callback, void *data,
1811	void *vec)
1812	{
1813	uintptr_t lowpc;
1814	uintptr_t highpc;
1815
1816	lowpc = pcrange->lowpc;
1817	if (pcrange->lowpc_is_addr_index)
1818	{
1819	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base, addrsize: u->addrsize,
1820	is_bigendian, addr_index: lowpc, error_callback, data,
1821	address: &lowpc))
1822	return 0;
1823	}
1824
1825	highpc = pcrange->highpc;
1826	if (pcrange->highpc_is_addr_index)
1827	{
1828	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base, addrsize: u->addrsize,
1829	is_bigendian, addr_index: highpc, error_callback, data,
1830	address: &highpc))
1831	return 0;
1832	}
1833	if (pcrange->highpc_is_relative)
1834	highpc += lowpc;
1835
1836	/* Add in the base address of the module when recording PC values,
1837	so that we can look up the PC directly. */
1838	lowpc = libbacktrace_add_base (lowpc, base_address);
1839	highpc = libbacktrace_add_base (highpc, base_address);
1840
1841	return add_range (state, rdata, lowpc, highpc, error_callback, data, vec);
1842	}
1843
1844	/* Call ADD_RANGE for each range read from .debug_ranges, as used in
1845	DWARF versions 2 through 4. */
1846
1847	static int
1848	add_ranges_from_ranges (
1849	struct backtrace_state *state,
1850	const struct dwarf_sections *dwarf_sections,
1851	struct libbacktrace_base_address base_address, int is_bigendian,
1852	struct unit *u, uintptr_t base,
1853	const struct pcrange *pcrange,
1854	int (*add_range) (struct backtrace_state *state, void *rdata,
1855	uintptr_t lowpc, uintptr_t highpc,
1856	backtrace_error_callback error_callback, void *data,
1857	void *vec),
1858	void *rdata,
1859	backtrace_error_callback error_callback, void *data,
1860	void *vec)
1861	{
1862	struct dwarf_buf ranges_buf;
1863
1864	if (pcrange->ranges >= dwarf_sections->size[DEBUG_RANGES])
1865	{
1866	error_callback (data, "ranges offset out of range", 0);
1867	return 0;
1868	}
1869
1870	ranges_buf.name = ".debug_ranges";
1871	ranges_buf.start = dwarf_sections->data[DEBUG_RANGES];
1872	ranges_buf.buf = dwarf_sections->data[DEBUG_RANGES] + pcrange->ranges;
1873	ranges_buf.left = dwarf_sections->size[DEBUG_RANGES] - pcrange->ranges;
1874	ranges_buf.is_bigendian = is_bigendian;
1875	ranges_buf.error_callback = error_callback;
1876	ranges_buf.data = data;
1877	ranges_buf.reported_underflow = 0;
1878
1879	while (1)
1880	{
1881	uint64_t low;
1882	uint64_t high;
1883
1884	if (ranges_buf.reported_underflow)
1885	return 0;
1886
1887	low = read_address (buf: &ranges_buf, addrsize: u->addrsize);
1888	high = read_address (buf: &ranges_buf, addrsize: u->addrsize);
1889
1890	if (low == 0 && high == 0)
1891	break;
1892
1893	if (is_highest_address (address: low, addrsize: u->addrsize))
1894	base = (uintptr_t) high;
1895	else
1896	{
1897	uintptr_t rl, rh;
1898
1899	rl = libbacktrace_add_base ((uintptr_t) low + base, base_address);
1900	rh = libbacktrace_add_base ((uintptr_t) high + base, base_address);
1901	if (!add_range (state, rdata, rl, rh, error_callback, data, vec))
1902	return 0;
1903	}
1904	}
1905
1906	if (ranges_buf.reported_underflow)
1907	return 0;
1908
1909	return 1;
1910	}
1911
1912	/* Call ADD_RANGE for each range read from .debug_rnglists, as used in
1913	DWARF version 5. */
1914
1915	static int
1916	add_ranges_from_rnglists (
1917	struct backtrace_state *state,
1918	const struct dwarf_sections *dwarf_sections,
1919	struct libbacktrace_base_address base_address, int is_bigendian,
1920	struct unit *u, uintptr_t base,
1921	const struct pcrange *pcrange,
1922	int (*add_range) (struct backtrace_state *state, void *rdata,
1923	uintptr_t lowpc, uintptr_t highpc,
1924	backtrace_error_callback error_callback, void *data,
1925	void *vec),
1926	void *rdata,
1927	backtrace_error_callback error_callback, void *data,
1928	void *vec)
1929	{
1930	uint64_t offset;
1931	struct dwarf_buf rnglists_buf;
1932
1933	if (!pcrange->ranges_is_index)
1934	offset = pcrange->ranges;
1935	else
1936	offset = u->rnglists_base + pcrange->ranges * (u->is_dwarf64 ? 8 : 4);
1937	if (offset >= dwarf_sections->size[DEBUG_RNGLISTS])
1938	{
1939	error_callback (data, "rnglists offset out of range", 0);
1940	return 0;
1941	}
1942
1943	rnglists_buf.name = ".debug_rnglists";
1944	rnglists_buf.start = dwarf_sections->data[DEBUG_RNGLISTS];
1945	rnglists_buf.buf = dwarf_sections->data[DEBUG_RNGLISTS] + offset;
1946	rnglists_buf.left = dwarf_sections->size[DEBUG_RNGLISTS] - offset;
1947	rnglists_buf.is_bigendian = is_bigendian;
1948	rnglists_buf.error_callback = error_callback;
1949	rnglists_buf.data = data;
1950	rnglists_buf.reported_underflow = 0;
1951
1952	if (pcrange->ranges_is_index)
1953	{
1954	offset = read_offset (buf: &rnglists_buf, is_dwarf64: u->is_dwarf64);
1955	offset += u->rnglists_base;
1956	if (offset >= dwarf_sections->size[DEBUG_RNGLISTS])
1957	{
1958	error_callback (data, "rnglists index offset out of range", 0);
1959	return 0;
1960	}
1961	rnglists_buf.buf = dwarf_sections->data[DEBUG_RNGLISTS] + offset;
1962	rnglists_buf.left = dwarf_sections->size[DEBUG_RNGLISTS] - offset;
1963	}
1964
1965	while (1)
1966	{
1967	unsigned char rle;
1968
1969	rle = read_byte (buf: &rnglists_buf);
1970	if (rle == DW_RLE_end_of_list)
1971	break;
1972	switch (rle)
1973	{
1974	case DW_RLE_base_addressx:
1975	{
1976	uint64_t index;
1977
1978	index = read_uleb128 (buf: &rnglists_buf);
1979	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
1980	addrsize: u->addrsize, is_bigendian, addr_index: index,
1981	error_callback, data, address: &base))
1982	return 0;
1983	}
1984	break;
1985
1986	case DW_RLE_startx_endx:
1987	{
1988	uint64_t index;
1989	uintptr_t low;
1990	uintptr_t high;
1991
1992	index = read_uleb128 (buf: &rnglists_buf);
1993	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
1994	addrsize: u->addrsize, is_bigendian, addr_index: index,
1995	error_callback, data, address: &low))
1996	return 0;
1997	index = read_uleb128 (buf: &rnglists_buf);
1998	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
1999	addrsize: u->addrsize, is_bigendian, addr_index: index,
2000	error_callback, data, address: &high))
2001	return 0;
2002	if (!add_range (state, rdata,
2003	libbacktrace_add_base (low, base_address),
2004	libbacktrace_add_base (high, base_address),
2005	error_callback, data, vec))
2006	return 0;
2007	}
2008	break;
2009
2010	case DW_RLE_startx_length:
2011	{
2012	uint64_t index;
2013	uintptr_t low;
2014	uintptr_t length;
2015
2016	index = read_uleb128 (buf: &rnglists_buf);
2017	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
2018	addrsize: u->addrsize, is_bigendian, addr_index: index,
2019	error_callback, data, address: &low))
2020	return 0;
2021	length = read_uleb128 (buf: &rnglists_buf);
2022	low = libbacktrace_add_base (low, base_address);
2023	if (!add_range (state, rdata, low, low + length,
2024	error_callback, data, vec))
2025	return 0;
2026	}
2027	break;
2028
2029	case DW_RLE_offset_pair:
2030	{
2031	uint64_t low;
2032	uint64_t high;
2033
2034	low = read_uleb128 (buf: &rnglists_buf);
2035	high = read_uleb128 (buf: &rnglists_buf);
2036	if (!add_range (state, rdata,
2037	libbacktrace_add_base (low + base, base_address),
2038	libbacktrace_add_base (high + base, base_address),
2039	error_callback, data, vec))
2040	return 0;
2041	}
2042	break;
2043
2044	case DW_RLE_base_address:
2045	base = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
2046	break;
2047
2048	case DW_RLE_start_end:
2049	{
2050	uintptr_t low;
2051	uintptr_t high;
2052
2053	low = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
2054	high = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
2055	if (!add_range (state, rdata,
2056	libbacktrace_add_base (low, base_address),
2057	libbacktrace_add_base (high, base_address),
2058	error_callback, data, vec))
2059	return 0;
2060	}
2061	break;
2062
2063	case DW_RLE_start_length:
2064	{
2065	uintptr_t low;
2066	uintptr_t length;
2067
2068	low = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
2069	length = (uintptr_t) read_uleb128 (buf: &rnglists_buf);
2070	low = libbacktrace_add_base (low, base_address);
2071	if (!add_range (state, rdata, low, low + length,
2072	error_callback, data, vec))
2073	return 0;
2074	}
2075	break;
2076
2077	default:
2078	dwarf_buf_error (buf: &rnglists_buf, msg: "unrecognized DW_RLE value", errnum: -1);
2079	return 0;
2080	}
2081	}
2082
2083	if (rnglists_buf.reported_underflow)
2084	return 0;
2085
2086	return 1;
2087	}
2088
2089	/* Call ADD_RANGE for each lowpc/highpc pair in PCRANGE. RDATA is
2090	passed to ADD_RANGE, and is either a struct unit * or a struct
2091	function *. VEC is the vector we are adding ranges to, and is
2092	either a struct unit_addrs_vector * or a struct function_vector *.
2093	Returns 1 on success, 0 on error. */
2094
2095	static int
2096	add_ranges (struct backtrace_state *state,
2097	const struct dwarf_sections *dwarf_sections,
2098	struct libbacktrace_base_address base_address, int is_bigendian,
2099	struct unit *u, uintptr_t base, const struct pcrange *pcrange,
2100	int (*add_range) (struct backtrace_state *state, void *rdata,
2101	uintptr_t lowpc, uintptr_t highpc,
2102	backtrace_error_callback error_callback,
2103	void *data, void *vec),
2104	void *rdata,
2105	backtrace_error_callback error_callback, void *data,
2106	void *vec)
2107	{
2108	if (pcrange->have_lowpc && pcrange->have_highpc)
2109	return add_low_high_range (state, dwarf_sections, base_address,
2110	is_bigendian, u, pcrange, add_range, rdata,
2111	error_callback, data, vec);
2112
2113	if (!pcrange->have_ranges)
2114	{
2115	/* Did not find any address ranges to add. */
2116	return 1;
2117	}
2118
2119	if (u->version < 5)
2120	return add_ranges_from_ranges (state, dwarf_sections, base_address,
2121	is_bigendian, u, base, pcrange, add_range,
2122	rdata, error_callback, data, vec);
2123	else
2124	return add_ranges_from_rnglists (state, dwarf_sections, base_address,
2125	is_bigendian, u, base, pcrange, add_range,
2126	rdata, error_callback, data, vec);
2127	}
2128
2129	/* Find the address range covered by a compilation unit, reading from
2130	UNIT_BUF and adding values to U. Returns 1 if all data could be
2131	read, 0 if there is some error. */
2132
2133	static int
2134	find_address_ranges (struct backtrace_state *state,
2135	struct libbacktrace_base_address base_address,
2136	struct dwarf_buf *unit_buf,
2137	const struct dwarf_sections *dwarf_sections,
2138	int is_bigendian, struct dwarf_data *altlink,
2139	backtrace_error_callback error_callback, void *data,
2140	struct unit *u, struct unit_addrs_vector *addrs,
2141	enum dwarf_tag *unit_tag)
2142	{
2143	while (unit_buf->left > 0)
2144	{
2145	uint64_t code;
2146	const struct abbrev *abbrev;
2147	struct pcrange pcrange;
2148	struct attr_val name_val;
2149	int have_name_val;
2150	struct attr_val comp_dir_val;
2151	int have_comp_dir_val;
2152	size_t i;
2153
2154	code = read_uleb128 (buf: unit_buf);
2155	if (code == 0)
2156	return 1;
2157
2158	abbrev = lookup_abbrev (abbrevs: &u->abbrevs, code, error_callback, data);
2159	if (abbrev == NULL)
2160	return 0;
2161
2162	if (unit_tag != NULL)
2163	*unit_tag = abbrev->tag;
2164
2165	memset (s: &pcrange, c: 0, n: sizeof pcrange);
2166	memset (s: &name_val, c: 0, n: sizeof name_val);
2167	have_name_val = 0;
2168	memset (s: &comp_dir_val, c: 0, n: sizeof comp_dir_val);
2169	have_comp_dir_val = 0;
2170	for (i = 0; i < abbrev->num_attrs; ++i)
2171	{
2172	struct attr_val val;
2173
2174	if (!read_attribute (form: abbrev->attrs[i].form, implicit_val: abbrev->attrs[i].val,
2175	buf: unit_buf, is_dwarf64: u->is_dwarf64, version: u->version,
2176	addrsize: u->addrsize, dwarf_sections, altlink, val: &val))
2177	return 0;
2178
2179	switch (abbrev->attrs[i].name)
2180	{
2181	case DW_AT_low_pc: case DW_AT_high_pc: case DW_AT_ranges:
2182	update_pcrange (attr: &abbrev->attrs[i], val: &val, pcrange: &pcrange);
2183	break;
2184
2185	case DW_AT_stmt_list:
2186	if ((abbrev->tag == DW_TAG_compile_unit
2187	|| abbrev->tag == DW_TAG_skeleton_unit)
2188	&& (val.encoding == ATTR_VAL_UINT
2189	|| val.encoding == ATTR_VAL_REF_SECTION))
2190	u->lineoff = val.u.uint;
2191	break;
2192
2193	case DW_AT_name:
2194	if (abbrev->tag == DW_TAG_compile_unit
2195	|| abbrev->tag == DW_TAG_skeleton_unit)
2196	{
2197	name_val = val;
2198	have_name_val = 1;
2199	}
2200	break;
2201
2202	case DW_AT_comp_dir:
2203	if (abbrev->tag == DW_TAG_compile_unit
2204	|| abbrev->tag == DW_TAG_skeleton_unit)
2205	{
2206	comp_dir_val = val;
2207	have_comp_dir_val = 1;
2208	}
2209	break;
2210
2211	case DW_AT_str_offsets_base:
2212	if ((abbrev->tag == DW_TAG_compile_unit
2213	|| abbrev->tag == DW_TAG_skeleton_unit)
2214	&& val.encoding == ATTR_VAL_REF_SECTION)
2215	u->str_offsets_base = val.u.uint;
2216	break;
2217
2218	case DW_AT_addr_base:
2219	if ((abbrev->tag == DW_TAG_compile_unit
2220	|| abbrev->tag == DW_TAG_skeleton_unit)
2221	&& val.encoding == ATTR_VAL_REF_SECTION)
2222	u->addr_base = val.u.uint;
2223	break;
2224
2225	case DW_AT_rnglists_base:
2226	if ((abbrev->tag == DW_TAG_compile_unit
2227	|| abbrev->tag == DW_TAG_skeleton_unit)
2228	&& val.encoding == ATTR_VAL_REF_SECTION)
2229	u->rnglists_base = val.u.uint;
2230	break;
2231
2232	default:
2233	break;
2234	}
2235	}
2236
2237	// Resolve strings after we're sure that we have seen
2238	// DW_AT_str_offsets_base.
2239	if (have_name_val)
2240	{
2241	if (!resolve_string (dwarf_sections, is_dwarf64: u->is_dwarf64, is_bigendian,
2242	str_offsets_base: u->str_offsets_base, val: &name_val,
2243	error_callback, data, string: &u->filename))
2244	return 0;
2245	}
2246	if (have_comp_dir_val)
2247	{
2248	if (!resolve_string (dwarf_sections, is_dwarf64: u->is_dwarf64, is_bigendian,
2249	str_offsets_base: u->str_offsets_base, val: &comp_dir_val,
2250	error_callback, data, string: &u->comp_dir))
2251	return 0;
2252	}
2253
2254	if (abbrev->tag == DW_TAG_compile_unit
2255	|| abbrev->tag == DW_TAG_subprogram
2256	|| abbrev->tag == DW_TAG_skeleton_unit)
2257	{
2258	if (!add_ranges (state, dwarf_sections, base_address,
2259	is_bigendian, u, base: pcrange.lowpc, pcrange: &pcrange,
2260	add_range: add_unit_addr, rdata: (void *) u, error_callback, data,
2261	vec: (void *) addrs))
2262	return 0;
2263
2264	/* If we found the PC range in the DW_TAG_compile_unit or
2265	DW_TAG_skeleton_unit, we can stop now. */
2266	if ((abbrev->tag == DW_TAG_compile_unit
2267	|| abbrev->tag == DW_TAG_skeleton_unit)
2268	&& (pcrange.have_ranges
2269	|| (pcrange.have_lowpc && pcrange.have_highpc)))
2270	return 1;
2271	}
2272
2273	if (abbrev->has_children)
2274	{
2275	if (!find_address_ranges (state, base_address, unit_buf,
2276	dwarf_sections, is_bigendian, altlink,
2277	error_callback, data, u, addrs, NULL))
2278	return 0;
2279	}
2280	}
2281
2282	return 1;
2283	}
2284
2285	/* Build a mapping from address ranges to the compilation units where
2286	the line number information for that range can be found. Returns 1
2287	on success, 0 on failure. */
2288
2289	static int
2290	build_address_map (struct backtrace_state *state,
2291	struct libbacktrace_base_address base_address,
2292	const struct dwarf_sections *dwarf_sections,
2293	int is_bigendian, struct dwarf_data *altlink,
2294	backtrace_error_callback error_callback, void *data,
2295	struct unit_addrs_vector *addrs,
2296	struct unit_vector *unit_vec)
2297	{
2298	struct dwarf_buf info;
2299	struct backtrace_vector units;
2300	size_t units_count;
2301	size_t i;
2302	struct unit **pu;
2303	size_t unit_offset = 0;
2304	struct unit_addrs *pa;
2305
2306	memset (s: &addrs->vec, c: 0, n: sizeof addrs->vec);
2307	memset (s: &unit_vec->vec, c: 0, n: sizeof unit_vec->vec);
2308	addrs->count = 0;
2309	unit_vec->count = 0;
2310
2311	/* Read through the .debug_info section. FIXME: Should we use the
2312	.debug_aranges section? gdb and addr2line don't use it, but I'm
2313	not sure why. */
2314
2315	info.name = ".debug_info";
2316	info.start = dwarf_sections->data[DEBUG_INFO];
2317	info.buf = info.start;
2318	info.left = dwarf_sections->size[DEBUG_INFO];
2319	info.is_bigendian = is_bigendian;
2320	info.error_callback = error_callback;
2321	info.data = data;
2322	info.reported_underflow = 0;
2323
2324	memset (s: &units, c: 0, n: sizeof units);
2325	units_count = 0;
2326
2327	while (info.left > 0)
2328	{
2329	const unsigned char *unit_data_start;
2330	uint64_t len;
2331	int is_dwarf64;
2332	struct dwarf_buf unit_buf;
2333	int version;
2334	int unit_type;
2335	uint64_t abbrev_offset;
2336	int addrsize;
2337	struct unit *u;
2338	enum dwarf_tag unit_tag;
2339
2340	if (info.reported_underflow)
2341	goto fail;
2342
2343	unit_data_start = info.buf;
2344
2345	len = read_initial_length (buf: &info, is_dwarf64: &is_dwarf64);
2346	unit_buf = info;
2347	unit_buf.left = len;
2348
2349	if (!advance (buf: &info, count: len))
2350	goto fail;
2351
2352	version = read_uint16 (buf: &unit_buf);
2353	if (version < 2 || version > 5)
2354	{
2355	dwarf_buf_error (buf: &unit_buf, msg: "unrecognized DWARF version", errnum: -1);
2356	goto fail;
2357	}
2358
2359	if (version < 5)
2360	unit_type = 0;
2361	else
2362	{
2363	unit_type = read_byte (buf: &unit_buf);
2364	if (unit_type == DW_UT_type || unit_type == DW_UT_split_type)
2365	{
2366	/* This unit doesn't have anything we need. */
2367	continue;
2368	}
2369	}
2370
2371	pu = ((struct unit **)
2372	backtrace_vector_grow (state, size: sizeof (struct unit *),
2373	error_callback, data, vec: &units));
2374	if (pu == NULL)
2375	goto fail;
2376
2377	u = ((struct unit *)
2378	backtrace_alloc (state, size: sizeof *u, error_callback, data));
2379	if (u == NULL)
2380	goto fail;
2381
2382	*pu = u;
2383	++units_count;
2384
2385	if (version < 5)
2386	addrsize = 0; /* Set below. */
2387	else
2388	addrsize = read_byte (buf: &unit_buf);
2389
2390	memset (s: &u->abbrevs, c: 0, n: sizeof u->abbrevs);
2391	abbrev_offset = read_offset (buf: &unit_buf, is_dwarf64);
2392	if (!read_abbrevs (state, abbrev_offset,
2393	dwarf_abbrev: dwarf_sections->data[DEBUG_ABBREV],
2394	dwarf_abbrev_size: dwarf_sections->size[DEBUG_ABBREV],
2395	is_bigendian, error_callback, data, abbrevs: &u->abbrevs))
2396	goto fail;
2397
2398	if (version < 5)
2399	addrsize = read_byte (buf: &unit_buf);
2400
2401	switch (unit_type)
2402	{
2403	case 0:
2404	break;
2405	case DW_UT_compile: case DW_UT_partial:
2406	break;
2407	case DW_UT_skeleton: case DW_UT_split_compile:
2408	read_uint64 (buf: &unit_buf); /* dwo_id */
2409	break;
2410	default:
2411	break;
2412	}
2413
2414	u->low_offset = unit_offset;
2415	unit_offset += len + (is_dwarf64 ? 12 : 4);
2416	u->high_offset = unit_offset;
2417	u->unit_data = unit_buf.buf;
2418	u->unit_data_len = unit_buf.left;
2419	u->unit_data_offset = unit_buf.buf - unit_data_start;
2420	u->version = version;
2421	u->is_dwarf64 = is_dwarf64;
2422	u->addrsize = addrsize;
2423	u->filename = NULL;
2424	u->comp_dir = NULL;
2425	u->abs_filename = NULL;
2426	u->lineoff = 0;
2427	u->str_offsets_base = 0;
2428	u->addr_base = 0;
2429	u->rnglists_base = 0;
2430
2431	/* The actual line number mappings will be read as needed. */
2432	u->lines = NULL;
2433	u->lines_count = 0;
2434	u->function_addrs = NULL;
2435	u->function_addrs_count = 0;
2436
2437	if (!find_address_ranges (state, base_address, unit_buf: &unit_buf, dwarf_sections,
2438	is_bigendian, altlink, error_callback, data,
2439	u, addrs, unit_tag: &unit_tag))
2440	goto fail;
2441
2442	if (unit_buf.reported_underflow)
2443	goto fail;
2444	}
2445	if (info.reported_underflow)
2446	goto fail;
2447
2448	/* Add a trailing addrs entry, but don't include it in addrs->count. */
2449	pa = ((struct unit_addrs *)
2450	backtrace_vector_grow (state, size: sizeof (struct unit_addrs),
2451	error_callback, data, vec: &addrs->vec));
2452	if (pa == NULL)
2453	goto fail;
2454	pa->low = 0;
2455	--pa->low;
2456	pa->high = pa->low;
2457	pa->u = NULL;
2458
2459	unit_vec->vec = units;
2460	unit_vec->count = units_count;
2461	return 1;
2462
2463	fail:
2464	if (units_count > 0)
2465	{
2466	pu = (struct unit **) units.base;
2467	for (i = 0; i < units_count; i++)
2468	{
2469	free_abbrevs (state, abbrevs: &pu[i]->abbrevs, error_callback, data);
2470	backtrace_free (state, mem: pu[i], size: sizeof **pu, error_callback, data);
2471	}
2472	backtrace_vector_free (state, vec: &units, error_callback, data);
2473	}
2474	if (addrs->count > 0)
2475	{
2476	backtrace_vector_free (state, vec: &addrs->vec, error_callback, data);
2477	addrs->count = 0;
2478	}
2479	return 0;
2480	}
2481
2482	/* Add a new mapping to the vector of line mappings that we are
2483	building. Returns 1 on success, 0 on failure. */
2484
2485	static int
2486	add_line (struct backtrace_state *state, struct dwarf_data *ddata,
2487	uintptr_t pc, const char *filename, int lineno,
2488	backtrace_error_callback error_callback, void *data,
2489	struct line_vector *vec)
2490	{
2491	struct line *ln;
2492
2493	/* If we are adding the same mapping, ignore it. This can happen
2494	when using discriminators. */
2495	if (vec->count > 0)
2496	{
2497	ln = (struct line *) vec->vec.base + (vec->count - 1);
2498	if (pc == ln->pc && filename == ln->filename && lineno == ln->lineno)
2499	return 1;
2500	}
2501
2502	ln = ((struct line *)
2503	backtrace_vector_grow (state, size: sizeof (struct line), error_callback,
2504	data, vec: &vec->vec));
2505	if (ln == NULL)
2506	return 0;
2507
2508	/* Add in the base address here, so that we can look up the PC
2509	directly. */
2510	ln->pc = libbacktrace_add_base (pc, ddata->base_address);
2511
2512	ln->filename = filename;
2513	ln->lineno = lineno;
2514	ln->idx = vec->count;
2515
2516	++vec->count;
2517
2518	return 1;
2519	}
2520
2521	/* Free the line header information. */
2522
2523	static void
2524	free_line_header (struct backtrace_state *state, struct line_header *hdr,
2525	backtrace_error_callback error_callback, void *data)
2526	{
2527	if (hdr->dirs_count != 0)
2528	backtrace_free (state, mem: hdr->dirs, size: hdr->dirs_count * sizeof (const char *),
2529	error_callback, data);
2530	backtrace_free (state, mem: hdr->filenames,
2531	size: hdr->filenames_count * sizeof (char *),
2532	error_callback, data);
2533	}
2534
2535	/* Read the directories and file names for a line header for version
2536	2, setting fields in HDR. Return 1 on success, 0 on failure. */
2537
2538	static int
2539	read_v2_paths (struct backtrace_state *state, struct unit *u,
2540	struct dwarf_buf *hdr_buf, struct line_header *hdr)
2541	{
2542	const unsigned char *p;
2543	const unsigned char *pend;
2544	size_t i;
2545
2546	/* Count the number of directory entries. */
2547	hdr->dirs_count = 0;
2548	p = hdr_buf->buf;
2549	pend = p + hdr_buf->left;
2550	while (p < pend && *p != '\0')
2551	{
2552	p += strnlen(string: (const char *) p, maxlen: pend - p) + 1;
2553	++hdr->dirs_count;
2554	}
2555
2556	/* The index of the first entry in the list of directories is 1. Index 0 is
2557	used for the current directory of the compilation. To simplify index
2558	handling, we set entry 0 to the compilation unit directory. */
2559	++hdr->dirs_count;
2560	hdr->dirs = ((const char **)
2561	backtrace_alloc (state,
2562	size: hdr->dirs_count * sizeof (const char *),
2563	error_callback: hdr_buf->error_callback,
2564	data: hdr_buf->data));
2565	if (hdr->dirs == NULL)
2566	return 0;
2567
2568	hdr->dirs[0] = u->comp_dir;
2569	i = 1;
2570	while (*hdr_buf->buf != '\0')
2571	{
2572	if (hdr_buf->reported_underflow)
2573	return 0;
2574
2575	hdr->dirs[i] = read_string (buf: hdr_buf);
2576	if (hdr->dirs[i] == NULL)
2577	return 0;
2578	++i;
2579	}
2580	if (!advance (buf: hdr_buf, count: 1))
2581	return 0;
2582
2583	/* Count the number of file entries. */
2584	hdr->filenames_count = 0;
2585	p = hdr_buf->buf;
2586	pend = p + hdr_buf->left;
2587	while (p < pend && *p != '\0')
2588	{
2589	p += strnlen (string: (const char *) p, maxlen: pend - p) + 1;
2590	p += leb128_len (p);
2591	p += leb128_len (p);
2592	p += leb128_len (p);
2593	++hdr->filenames_count;
2594	}
2595
2596	/* The index of the first entry in the list of file names is 1. Index 0 is
2597	used for the DW_AT_name of the compilation unit. To simplify index
2598	handling, we set entry 0 to the compilation unit file name. */
2599	++hdr->filenames_count;
2600	hdr->filenames = ((const char **)
2601	backtrace_alloc (state,
2602	size: hdr->filenames_count * sizeof (char *),
2603	error_callback: hdr_buf->error_callback,
2604	data: hdr_buf->data));
2605	if (hdr->filenames == NULL)
2606	return 0;
2607	hdr->filenames[0] = u->filename;
2608	i = 1;
2609	while (*hdr_buf->buf != '\0')
2610	{
2611	const char *filename;
2612	uint64_t dir_index;
2613
2614	if (hdr_buf->reported_underflow)
2615	return 0;
2616
2617	filename = read_string (buf: hdr_buf);
2618	if (filename == NULL)
2619	return 0;
2620	dir_index = read_uleb128 (buf: hdr_buf);
2621	if (IS_ABSOLUTE_PATH (filename)
2622	|| (dir_index < hdr->dirs_count && hdr->dirs[dir_index] == NULL))
2623	hdr->filenames[i] = filename;
2624	else
2625	{
2626	const char *dir;
2627	size_t dir_len;
2628	size_t filename_len;
2629	char *s;
2630
2631	if (dir_index < hdr->dirs_count)
2632	dir = hdr->dirs[dir_index];
2633	else
2634	{
2635	dwarf_buf_error (buf: hdr_buf,
2636	msg: ("invalid directory index in "
2637	"line number program header"),
2638	errnum: 0);
2639	return 0;
2640	}
2641	dir_len = strlen (s: dir);
2642	filename_len = strlen (s: filename);
2643	s = ((char *) backtrace_alloc (state, size: dir_len + filename_len + 2,
2644	error_callback: hdr_buf->error_callback,
2645	data: hdr_buf->data));
2646	if (s == NULL)
2647	return 0;
2648	memcpy (dest: s, src: dir, n: dir_len);
2649	/* FIXME: If we are on a DOS-based file system, and the
2650	directory or the file name use backslashes, then we
2651	should use a backslash here. */
2652	s[dir_len] = '/';
2653	memcpy (dest: s + dir_len + 1, src: filename, n: filename_len + 1);
2654	hdr->filenames[i] = s;
2655	}
2656
2657	/* Ignore the modification time and size. */
2658	read_uleb128 (buf: hdr_buf);
2659	read_uleb128 (buf: hdr_buf);
2660
2661	++i;
2662	}
2663
2664	return 1;
2665	}
2666
2667	/* Read a single version 5 LNCT entry for a directory or file name in a
2668	line header. Sets *STRING to the resulting name, ignoring other
2669	data. Return 1 on success, 0 on failure. */
2670
2671	static int
2672	read_lnct (struct backtrace_state *state, struct dwarf_data *ddata,
2673	struct unit *u, struct dwarf_buf *hdr_buf,
2674	const struct line_header *hdr, size_t formats_count,
2675	const struct line_header_format *formats, const char **string)
2676	{
2677	size_t i;
2678	const char *dir;
2679	const char *path;
2680
2681	dir = NULL;
2682	path = NULL;
2683	for (i = 0; i < formats_count; i++)
2684	{
2685	struct attr_val val;
2686
2687	if (!read_attribute (form: formats[i].form, implicit_val: 0, buf: hdr_buf, is_dwarf64: u->is_dwarf64,
2688	version: u->version, addrsize: hdr->addrsize, dwarf_sections: &ddata->dwarf_sections,
2689	altlink: ddata->altlink, val: &val))
2690	return 0;
2691	switch (formats[i].lnct)
2692	{
2693	case DW_LNCT_path:
2694	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
2695	is_bigendian: ddata->is_bigendian, str_offsets_base: u->str_offsets_base,
2696	val: &val, error_callback: hdr_buf->error_callback, data: hdr_buf->data,
2697	string: &path))
2698	return 0;
2699	break;
2700	case DW_LNCT_directory_index:
2701	if (val.encoding == ATTR_VAL_UINT)
2702	{
2703	if (val.u.uint >= hdr->dirs_count)
2704	{
2705	dwarf_buf_error (buf: hdr_buf,
2706	msg: ("invalid directory index in "
2707	"line number program header"),
2708	errnum: 0);
2709	return 0;
2710	}
2711	dir = hdr->dirs[val.u.uint];
2712	}
2713	break;
2714	default:
2715	/* We don't care about timestamps or sizes or hashes. */
2716	break;
2717	}
2718	}
2719
2720	if (path == NULL)
2721	{
2722	dwarf_buf_error (buf: hdr_buf,
2723	msg: "missing file name in line number program header",
2724	errnum: 0);
2725	return 0;
2726	}
2727
2728	if (dir == NULL)
2729	*string = path;
2730	else
2731	{
2732	size_t dir_len;
2733	size_t path_len;
2734	char *s;
2735
2736	dir_len = strlen (s: dir);
2737	path_len = strlen (s: path);
2738	s = (char *) backtrace_alloc (state, size: dir_len + path_len + 2,
2739	error_callback: hdr_buf->error_callback, data: hdr_buf->data);
2740	if (s == NULL)
2741	return 0;
2742	memcpy (dest: s, src: dir, n: dir_len);
2743	/* FIXME: If we are on a DOS-based file system, and the
2744	directory or the path name use backslashes, then we should
2745	use a backslash here. */
2746	s[dir_len] = '/';
2747	memcpy (dest: s + dir_len + 1, src: path, n: path_len + 1);
2748	*string = s;
2749	}
2750
2751	return 1;
2752	}
2753
2754	/* Read a set of DWARF 5 line header format entries, setting *PCOUNT
2755	and *PPATHS. Return 1 on success, 0 on failure. */
2756
2757	static int
2758	read_line_header_format_entries (struct backtrace_state *state,
2759	struct dwarf_data *ddata,
2760	struct unit *u,
2761	struct dwarf_buf *hdr_buf,
2762	struct line_header *hdr,
2763	size_t *pcount,
2764	const char ***ppaths)
2765	{
2766	size_t formats_count;
2767	struct line_header_format *formats;
2768	size_t paths_count;
2769	const char **paths;
2770	size_t i;
2771	int ret;
2772
2773	formats_count = read_byte (buf: hdr_buf);
2774	if (formats_count == 0)
2775	formats = NULL;
2776	else
2777	{
2778	formats = ((struct line_header_format *)
2779	backtrace_alloc (state,
2780	size: (formats_count
2781	* sizeof (struct line_header_format)),
2782	error_callback: hdr_buf->error_callback,
2783	data: hdr_buf->data));
2784	if (formats == NULL)
2785	return 0;
2786
2787	for (i = 0; i < formats_count; i++)
2788	{
2789	formats[i].lnct = (int) read_uleb128(buf: hdr_buf);
2790	formats[i].form = (enum dwarf_form) read_uleb128 (buf: hdr_buf);
2791	}
2792	}
2793
2794	paths_count = read_uleb128 (buf: hdr_buf);
2795	if (paths_count == 0)
2796	{
2797	*pcount = 0;
2798	*ppaths = NULL;
2799	ret = 1;
2800	goto exit;
2801	}
2802
2803	paths = ((const char **)
2804	backtrace_alloc (state, size: paths_count * sizeof (const char *),
2805	error_callback: hdr_buf->error_callback, data: hdr_buf->data));
2806	if (paths == NULL)
2807	{
2808	ret = 0;
2809	goto exit;
2810	}
2811	for (i = 0; i < paths_count; i++)
2812	{
2813	if (!read_lnct (state, ddata, u, hdr_buf, hdr, formats_count,
2814	formats, string: &paths[i]))
2815	{
2816	backtrace_free (state, mem: paths,
2817	size: paths_count * sizeof (const char *),
2818	error_callback: hdr_buf->error_callback, data: hdr_buf->data);
2819	ret = 0;
2820	goto exit;
2821	}
2822	}
2823
2824	*pcount = paths_count;
2825	*ppaths = paths;
2826
2827	ret = 1;
2828
2829	exit:
2830	if (formats != NULL)
2831	backtrace_free (state, mem: formats,
2832	size: formats_count * sizeof (struct line_header_format),
2833	error_callback: hdr_buf->error_callback, data: hdr_buf->data);
2834
2835	return ret;
2836	}
2837
2838	/* Read the line header. Return 1 on success, 0 on failure. */
2839
2840	static int
2841	read_line_header (struct backtrace_state *state, struct dwarf_data *ddata,
2842	struct unit *u, int is_dwarf64, struct dwarf_buf *line_buf,
2843	struct line_header *hdr)
2844	{
2845	uint64_t hdrlen;
2846	struct dwarf_buf hdr_buf;
2847
2848	hdr->version = read_uint16 (buf: line_buf);
2849	if (hdr->version < 2 || hdr->version > 5)
2850	{
2851	dwarf_buf_error (buf: line_buf, msg: "unsupported line number version", errnum: -1);
2852	return 0;
2853	}
2854
2855	if (hdr->version < 5)
2856	hdr->addrsize = u->addrsize;
2857	else
2858	{
2859	hdr->addrsize = read_byte (buf: line_buf);
2860	/* We could support a non-zero segment_selector_size but I doubt
2861	we'll ever see it. */
2862	if (read_byte (buf: line_buf) != 0)
2863	{
2864	dwarf_buf_error (buf: line_buf,
2865	msg: "non-zero segment_selector_size not supported",
2866	errnum: -1);
2867	return 0;
2868	}
2869	}
2870
2871	hdrlen = read_offset (buf: line_buf, is_dwarf64);
2872
2873	hdr_buf = *line_buf;
2874	hdr_buf.left = hdrlen;
2875
2876	if (!advance (buf: line_buf, count: hdrlen))
2877	return 0;
2878
2879	hdr->min_insn_len = read_byte (buf: &hdr_buf);
2880	if (hdr->version < 4)
2881	hdr->max_ops_per_insn = 1;
2882	else
2883	hdr->max_ops_per_insn = read_byte (buf: &hdr_buf);
2884
2885	/* We don't care about default_is_stmt. */
2886	read_byte (buf: &hdr_buf);
2887
2888	hdr->line_base = read_sbyte (buf: &hdr_buf);
2889	hdr->line_range = read_byte (buf: &hdr_buf);
2890
2891	hdr->opcode_base = read_byte (buf: &hdr_buf);
2892	hdr->opcode_lengths = hdr_buf.buf;
2893	if (!advance (buf: &hdr_buf, count: hdr->opcode_base - 1))
2894	return 0;
2895
2896	if (hdr->version < 5)
2897	{
2898	if (!read_v2_paths (state, u, hdr_buf: &hdr_buf, hdr))
2899	return 0;
2900	}
2901	else
2902	{
2903	if (!read_line_header_format_entries (state, ddata, u, hdr_buf: &hdr_buf, hdr,
2904	pcount: &hdr->dirs_count,
2905	ppaths: &hdr->dirs))
2906	return 0;
2907	if (!read_line_header_format_entries (state, ddata, u, hdr_buf: &hdr_buf, hdr,
2908	pcount: &hdr->filenames_count,
2909	ppaths: &hdr->filenames))
2910	return 0;
2911	}
2912
2913	if (hdr_buf.reported_underflow)
2914	return 0;
2915
2916	return 1;
2917	}
2918
2919	/* Read the line program, adding line mappings to VEC. Return 1 on
2920	success, 0 on failure. */
2921
2922	static int
2923	read_line_program (struct backtrace_state *state, struct dwarf_data *ddata,
2924	const struct line_header *hdr, struct dwarf_buf *line_buf,
2925	struct line_vector *vec)
2926	{
2927	uint64_t address;
2928	unsigned int op_index;
2929	const char *reset_filename;
2930	const char *filename;
2931	int lineno;
2932
2933	address = 0;
2934	op_index = 0;
2935	if (hdr->filenames_count > 1)
2936	reset_filename = hdr->filenames[1];
2937	else
2938	reset_filename = "";
2939	filename = reset_filename;
2940	lineno = 1;
2941	while (line_buf->left > 0)
2942	{
2943	unsigned int op;
2944
2945	op = read_byte (buf: line_buf);
2946	if (op >= hdr->opcode_base)
2947	{
2948	unsigned int advance;
2949
2950	/* Special opcode. */
2951	op -= hdr->opcode_base;
2952	advance = op / hdr->line_range;
2953	address += (hdr->min_insn_len * (op_index + advance)
2954	/ hdr->max_ops_per_insn);
2955	op_index = (op_index + advance) % hdr->max_ops_per_insn;
2956	lineno += hdr->line_base + (int) (op % hdr->line_range);
2957	add_line (state, ddata, pc: address, filename, lineno,
2958	error_callback: line_buf->error_callback, data: line_buf->data, vec);
2959	}
2960	else if (op == DW_LNS_extended_op)
2961	{
2962	uint64_t len;
2963
2964	len = read_uleb128 (buf: line_buf);
2965	op = read_byte (buf: line_buf);
2966	switch (op)
2967	{
2968	case DW_LNE_end_sequence:
2969	/* FIXME: Should we mark the high PC here? It seems
2970	that we already have that information from the
2971	compilation unit. */
2972	address = 0;
2973	op_index = 0;
2974	filename = reset_filename;
2975	lineno = 1;
2976	break;
2977	case DW_LNE_set_address:
2978	address = read_address (buf: line_buf, addrsize: hdr->addrsize);
2979	break;
2980	case DW_LNE_define_file:
2981	{
2982	const char *f;
2983	unsigned int dir_index;
2984
2985	f = read_string (buf: line_buf);
2986	if (f == NULL)
2987	return 0;
2988	dir_index = read_uleb128 (buf: line_buf);
2989	/* Ignore that time and length. */
2990	read_uleb128 (buf: line_buf);
2991	read_uleb128 (buf: line_buf);
2992	if (IS_ABSOLUTE_PATH (f))
2993	filename = f;
2994	else
2995	{
2996	const char *dir;
2997	size_t dir_len;
2998	size_t f_len;
2999	char *p;
3000
3001	if (dir_index < hdr->dirs_count)
3002	dir = hdr->dirs[dir_index];
3003	else
3004	{
3005	dwarf_buf_error (buf: line_buf,
3006	msg: ("invalid directory index "
3007	"in line number program"),
3008	errnum: 0);
3009	return 0;
3010	}
3011	dir_len = strlen (s: dir);
3012	f_len = strlen (s: f);
3013	p = ((char *)
3014	backtrace_alloc (state, size: dir_len + f_len + 2,
3015	error_callback: line_buf->error_callback,
3016	data: line_buf->data));
3017	if (p == NULL)
3018	return 0;
3019	memcpy (dest: p, src: dir, n: dir_len);
3020	/* FIXME: If we are on a DOS-based file system,
3021	and the directory or the file name use
3022	backslashes, then we should use a backslash
3023	here. */
3024	p[dir_len] = '/';
3025	memcpy (dest: p + dir_len + 1, src: f, n: f_len + 1);
3026	filename = p;
3027	}
3028	}
3029	break;
3030	case DW_LNE_set_discriminator:
3031	/* We don't care about discriminators. */
3032	read_uleb128 (buf: line_buf);
3033	break;
3034	default:
3035	if (!advance (buf: line_buf, count: len - 1))
3036	return 0;
3037	break;
3038	}
3039	}
3040	else
3041	{
3042	switch (op)
3043	{
3044	case DW_LNS_copy:
3045	add_line (state, ddata, pc: address, filename, lineno,
3046	error_callback: line_buf->error_callback, data: line_buf->data, vec);
3047	break;
3048	case DW_LNS_advance_pc:
3049	{
3050	uint64_t advance;
3051
3052	advance = read_uleb128 (buf: line_buf);
3053	address += (hdr->min_insn_len * (op_index + advance)
3054	/ hdr->max_ops_per_insn);
3055	op_index = (op_index + advance) % hdr->max_ops_per_insn;
3056	}
3057	break;
3058	case DW_LNS_advance_line:
3059	lineno += (int) read_sleb128 (buf: line_buf);
3060	break;
3061	case DW_LNS_set_file:
3062	{
3063	uint64_t fileno;
3064
3065	fileno = read_uleb128 (buf: line_buf);
3066	if (fileno >= hdr->filenames_count)
3067	{
3068	dwarf_buf_error (buf: line_buf,
3069	msg: ("invalid file number in "
3070	"line number program"),
3071	errnum: 0);
3072	return 0;
3073	}
3074	filename = hdr->filenames[fileno];
3075	}
3076	break;
3077	case DW_LNS_set_column:
3078	read_uleb128 (buf: line_buf);
3079	break;
3080	case DW_LNS_negate_stmt:
3081	break;
3082	case DW_LNS_set_basic_block:
3083	break;
3084	case DW_LNS_const_add_pc:
3085	{
3086	unsigned int advance;
3087
3088	op = 255 - hdr->opcode_base;
3089	advance = op / hdr->line_range;
3090	address += (hdr->min_insn_len * (op_index + advance)
3091	/ hdr->max_ops_per_insn);
3092	op_index = (op_index + advance) % hdr->max_ops_per_insn;
3093	}
3094	break;
3095	case DW_LNS_fixed_advance_pc:
3096	address += read_uint16 (buf: line_buf);
3097	op_index = 0;
3098	break;
3099	case DW_LNS_set_prologue_end:
3100	break;
3101	case DW_LNS_set_epilogue_begin:
3102	break;
3103	case DW_LNS_set_isa:
3104	read_uleb128 (buf: line_buf);
3105	break;
3106	default:
3107	{
3108	unsigned int i;
3109
3110	for (i = hdr->opcode_lengths[op - 1]; i > 0; --i)
3111	read_uleb128 (buf: line_buf);
3112	}
3113	break;
3114	}
3115	}
3116	}
3117
3118	return 1;
3119	}
3120
3121	/* Read the line number information for a compilation unit. Returns 1
3122	on success, 0 on failure. */
3123
3124	static int
3125	read_line_info (struct backtrace_state *state, struct dwarf_data *ddata,
3126	backtrace_error_callback error_callback, void *data,
3127	struct unit *u, struct line_header *hdr, struct line **lines,
3128	size_t *lines_count)
3129	{
3130	struct line_vector vec;
3131	struct dwarf_buf line_buf;
3132	uint64_t len;
3133	int is_dwarf64;
3134	struct line *ln;
3135
3136	memset (s: &vec.vec, c: 0, n: sizeof vec.vec);
3137	vec.count = 0;
3138
3139	memset (s: hdr, c: 0, n: sizeof *hdr);
3140
3141	if (u->lineoff != (off_t) (size_t) u->lineoff
3142	|| (size_t) u->lineoff >= ddata->dwarf_sections.size[DEBUG_LINE])
3143	{
3144	error_callback (data, "unit line offset out of range", 0);
3145	goto fail;
3146	}
3147
3148	line_buf.name = ".debug_line";
3149	line_buf.start = ddata->dwarf_sections.data[DEBUG_LINE];
3150	line_buf.buf = ddata->dwarf_sections.data[DEBUG_LINE] + u->lineoff;
3151	line_buf.left = ddata->dwarf_sections.size[DEBUG_LINE] - u->lineoff;
3152	line_buf.is_bigendian = ddata->is_bigendian;
3153	line_buf.error_callback = error_callback;
3154	line_buf.data = data;
3155	line_buf.reported_underflow = 0;
3156
3157	len = read_initial_length (buf: &line_buf, is_dwarf64: &is_dwarf64);
3158	line_buf.left = len;
3159
3160	if (!read_line_header (state, ddata, u, is_dwarf64, line_buf: &line_buf, hdr))
3161	goto fail;
3162
3163	if (!read_line_program (state, ddata, hdr, line_buf: &line_buf, vec: &vec))
3164	goto fail;
3165
3166	if (line_buf.reported_underflow)
3167	goto fail;
3168
3169	if (vec.count == 0)
3170	{
3171	/* This is not a failure in the sense of generating an error,
3172	but it is a failure in that sense that we have no useful
3173	information. */
3174	goto fail;
3175	}
3176
3177	/* Allocate one extra entry at the end. */
3178	ln = ((struct line *)
3179	backtrace_vector_grow (state, size: sizeof (struct line), error_callback,
3180	data, vec: &vec.vec));
3181	if (ln == NULL)
3182	goto fail;
3183	ln->pc = (uintptr_t) -1;
3184	ln->filename = NULL;
3185	ln->lineno = 0;
3186	ln->idx = 0;
3187
3188	if (!backtrace_vector_release (state, vec: &vec.vec, error_callback, data))
3189	goto fail;
3190
3191	ln = (struct line *) vec.vec.base;
3192	backtrace_qsort (base: ln, count: vec.count, size: sizeof (struct line), compar: line_compare);
3193
3194	*lines = ln;
3195	*lines_count = vec.count;
3196
3197	return 1;
3198
3199	fail:
3200	backtrace_vector_free (state, vec: &vec.vec, error_callback, data);
3201	free_line_header (state, hdr, error_callback, data);
3202	*lines = (struct line *) (uintptr_t) -1;
3203	*lines_count = 0;
3204	return 0;
3205	}
3206
3207	static const char *read_referenced_name (struct dwarf_data *, struct unit *,
3208	uint64_t, backtrace_error_callback,
3209	void *);
3210
3211	/* Read the name of a function from a DIE referenced by ATTR with VAL. */
3212
3213	static const char *
3214	read_referenced_name_from_attr (struct dwarf_data *ddata, struct unit *u,
3215	struct attr *attr, struct attr_val *val,
3216	backtrace_error_callback error_callback,
3217	void *data)
3218	{
3219	switch (attr->name)
3220	{
3221	case DW_AT_abstract_origin:
3222	case DW_AT_specification:
3223	break;
3224	default:
3225	return NULL;
3226	}
3227
3228	if (attr->form == DW_FORM_ref_sig8)
3229	return NULL;
3230
3231	if (val->encoding == ATTR_VAL_REF_INFO)
3232	{
3233	struct unit *unit
3234	= find_unit (pu: ddata->units, units_count: ddata->units_count,
3235	offset: val->u.uint);
3236	if (unit == NULL)
3237	return NULL;
3238
3239	uint64_t offset = val->u.uint - unit->low_offset;
3240	return read_referenced_name (ddata, unit, offset, error_callback, data);
3241	}
3242
3243	if (val->encoding == ATTR_VAL_UINT
3244	|| val->encoding == ATTR_VAL_REF_UNIT)
3245	return read_referenced_name (ddata, u, val->u.uint, error_callback, data);
3246
3247	if (val->encoding == ATTR_VAL_REF_ALT_INFO)
3248	{
3249	struct unit *alt_unit
3250	= find_unit (pu: ddata->altlink->units, units_count: ddata->altlink->units_count,
3251	offset: val->u.uint);
3252	if (alt_unit == NULL)
3253	return NULL;
3254
3255	uint64_t offset = val->u.uint - alt_unit->low_offset;
3256	return read_referenced_name (ddata->altlink, alt_unit, offset,
3257	error_callback, data);
3258	}
3259
3260	return NULL;
3261	}
3262
3263	/* Read the name of a function from a DIE referenced by a
3264	DW_AT_abstract_origin or DW_AT_specification tag. OFFSET is within
3265	the same compilation unit. */
3266
3267	static const char *
3268	read_referenced_name (struct dwarf_data *ddata, struct unit *u,
3269	uint64_t offset, backtrace_error_callback error_callback,
3270	void *data)
3271	{
3272	struct dwarf_buf unit_buf;
3273	uint64_t code;
3274	const struct abbrev *abbrev;
3275	const char *ret;
3276	size_t i;
3277
3278	/* OFFSET is from the start of the data for this compilation unit.
3279	U->unit_data is the data, but it starts U->unit_data_offset bytes
3280	from the beginning. */
3281
3282	if (offset < u->unit_data_offset
3283	|| offset - u->unit_data_offset >= u->unit_data_len)
3284	{
3285	error_callback (data,
3286	"abstract origin or specification out of range",
3287	0);
3288	return NULL;
3289	}
3290
3291	offset -= u->unit_data_offset;
3292
3293	unit_buf.name = ".debug_info";
3294	unit_buf.start = ddata->dwarf_sections.data[DEBUG_INFO];
3295	unit_buf.buf = u->unit_data + offset;
3296	unit_buf.left = u->unit_data_len - offset;
3297	unit_buf.is_bigendian = ddata->is_bigendian;
3298	unit_buf.error_callback = error_callback;
3299	unit_buf.data = data;
3300	unit_buf.reported_underflow = 0;
3301
3302	code = read_uleb128 (buf: &unit_buf);
3303	if (code == 0)
3304	{
3305	dwarf_buf_error (buf: &unit_buf,
3306	msg: "invalid abstract origin or specification",
3307	errnum: 0);
3308	return NULL;
3309	}
3310
3311	abbrev = lookup_abbrev (abbrevs: &u->abbrevs, code, error_callback, data);
3312	if (abbrev == NULL)
3313	return NULL;
3314
3315	ret = NULL;
3316	for (i = 0; i < abbrev->num_attrs; ++i)
3317	{
3318	struct attr_val val;
3319
3320	if (!read_attribute (form: abbrev->attrs[i].form, implicit_val: abbrev->attrs[i].val,
3321	buf: &unit_buf, is_dwarf64: u->is_dwarf64, version: u->version, addrsize: u->addrsize,
3322	dwarf_sections: &ddata->dwarf_sections, altlink: ddata->altlink, val: &val))
3323	return NULL;
3324
3325	switch (abbrev->attrs[i].name)
3326	{
3327	case DW_AT_name:
3328	/* Third name preference: don't override. A name we found in some
3329	other way, will normally be more useful -- e.g., this name is
3330	normally not mangled. */
3331	if (ret != NULL)
3332	break;
3333	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3334	is_bigendian: ddata->is_bigendian, str_offsets_base: u->str_offsets_base,
3335	val: &val, error_callback, data, string: &ret))
3336	return NULL;
3337	break;
3338
3339	case DW_AT_linkage_name:
3340	case DW_AT_MIPS_linkage_name:
3341	/* First name preference: override all. */
3342	{
3343	const char *s;
3344
3345	s = NULL;
3346	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3347	is_bigendian: ddata->is_bigendian, str_offsets_base: u->str_offsets_base,
3348	val: &val, error_callback, data, string: &s))
3349	return NULL;
3350	if (s != NULL)
3351	return s;
3352	}
3353	break;
3354
3355	case DW_AT_specification:
3356	/* Second name preference: override DW_AT_name, don't override
3357	DW_AT_linkage_name. */
3358	{
3359	const char *name;
3360
3361	name = read_referenced_name_from_attr (ddata, u, attr: &abbrev->attrs[i],
3362	val: &val, error_callback, data);
3363	if (name != NULL)
3364	ret = name;
3365	}
3366	break;
3367
3368	default:
3369	break;
3370	}
3371	}
3372
3373	return ret;
3374	}
3375
3376	/* Add a range to a unit that maps to a function. This is called via
3377	add_ranges. Returns 1 on success, 0 on error. */
3378
3379	static int
3380	add_function_range (struct backtrace_state *state, void *rdata,
3381	uintptr_t lowpc, uintptr_t highpc,
3382	backtrace_error_callback error_callback, void *data,
3383	void *pvec)
3384	{
3385	struct function *function = (struct function *) rdata;
3386	struct function_vector *vec = (struct function_vector *) pvec;
3387	struct function_addrs *p;
3388
3389	if (vec->count > 0)
3390	{
3391	p = (struct function_addrs *) vec->vec.base + (vec->count - 1);
3392	if ((lowpc == p->high || lowpc == p->high + 1)
3393	&& function == p->function)
3394	{
3395	if (highpc > p->high)
3396	p->high = highpc;
3397	return 1;
3398	}
3399	}
3400
3401	p = ((struct function_addrs *)
3402	backtrace_vector_grow (state, size: sizeof (struct function_addrs),
3403	error_callback, data, vec: &vec->vec));
3404	if (p == NULL)
3405	return 0;
3406
3407	p->low = lowpc;
3408	p->high = highpc;
3409	p->function = function;
3410
3411	++vec->count;
3412
3413	return 1;
3414	}
3415
3416	/* Read one entry plus all its children. Add function addresses to
3417	VEC. Returns 1 on success, 0 on error. */
3418
3419	static int
3420	read_function_entry (struct backtrace_state *state, struct dwarf_data *ddata,
3421	struct unit *u, uintptr_t base, struct dwarf_buf *unit_buf,
3422	const struct line_header *lhdr,
3423	backtrace_error_callback error_callback, void *data,
3424	struct function_vector *vec_function,
3425	struct function_vector *vec_inlined)
3426	{
3427	while (unit_buf->left > 0)
3428	{
3429	uint64_t code;
3430	const struct abbrev *abbrev;
3431	int is_function;
3432	struct function *function;
3433	struct function_vector *vec;
3434	size_t i;
3435	struct pcrange pcrange;
3436	int have_linkage_name;
3437
3438	code = read_uleb128 (buf: unit_buf);
3439	if (code == 0)
3440	return 1;
3441
3442	abbrev = lookup_abbrev (abbrevs: &u->abbrevs, code, error_callback, data);
3443	if (abbrev == NULL)
3444	return 0;
3445
3446	is_function = (abbrev->tag == DW_TAG_subprogram
3447	|| abbrev->tag == DW_TAG_entry_point
3448	|| abbrev->tag == DW_TAG_inlined_subroutine);
3449
3450	if (abbrev->tag == DW_TAG_inlined_subroutine)
3451	vec = vec_inlined;
3452	else
3453	vec = vec_function;
3454
3455	function = NULL;
3456	if (is_function)
3457	{
3458	function = ((struct function *)
3459	backtrace_alloc (state, size: sizeof *function,
3460	error_callback, data));
3461	if (function == NULL)
3462	return 0;
3463	memset (s: function, c: 0, n: sizeof *function);
3464	}
3465
3466	memset (s: &pcrange, c: 0, n: sizeof pcrange);
3467	have_linkage_name = 0;
3468	for (i = 0; i < abbrev->num_attrs; ++i)
3469	{
3470	struct attr_val val;
3471
3472	if (!read_attribute (form: abbrev->attrs[i].form, implicit_val: abbrev->attrs[i].val,
3473	buf: unit_buf, is_dwarf64: u->is_dwarf64, version: u->version,
3474	addrsize: u->addrsize, dwarf_sections: &ddata->dwarf_sections,
3475	altlink: ddata->altlink, val: &val))
3476	return 0;
3477
3478	/* The compile unit sets the base address for any address
3479	ranges in the function entries. */
3480	if ((abbrev->tag == DW_TAG_compile_unit
3481	|| abbrev->tag == DW_TAG_skeleton_unit)
3482	&& abbrev->attrs[i].name == DW_AT_low_pc)
3483	{
3484	if (val.encoding == ATTR_VAL_ADDRESS)
3485	base = (uintptr_t) val.u.uint;
3486	else if (val.encoding == ATTR_VAL_ADDRESS_INDEX)
3487	{
3488	if (!resolve_addr_index (dwarf_sections: &ddata->dwarf_sections,
3489	addr_base: u->addr_base, addrsize: u->addrsize,
3490	is_bigendian: ddata->is_bigendian, addr_index: val.u.uint,
3491	error_callback, data, address: &base))
3492	return 0;
3493	}
3494	}
3495
3496	if (is_function)
3497	{
3498	switch (abbrev->attrs[i].name)
3499	{
3500	case DW_AT_call_file:
3501	if (val.encoding == ATTR_VAL_UINT)
3502	{
3503	if (val.u.uint >= lhdr->filenames_count)
3504	{
3505	dwarf_buf_error (buf: unit_buf,
3506	msg: ("invalid file number in "
3507	"DW_AT_call_file attribute"),
3508	errnum: 0);
3509	return 0;
3510	}
3511	function->caller_filename = lhdr->filenames[val.u.uint];
3512	}
3513	break;
3514
3515	case DW_AT_call_line:
3516	if (val.encoding == ATTR_VAL_UINT)
3517	function->caller_lineno = val.u.uint;
3518	break;
3519
3520	case DW_AT_abstract_origin:
3521	case DW_AT_specification:
3522	/* Second name preference: override DW_AT_name, don't override
3523	DW_AT_linkage_name. */
3524	if (have_linkage_name)
3525	break;
3526	{
3527	const char *name;
3528
3529	name
3530	= read_referenced_name_from_attr (ddata, u,
3531	attr: &abbrev->attrs[i], val: &val,
3532	error_callback, data);
3533	if (name != NULL)
3534	function->name = name;
3535	}
3536	break;
3537
3538	case DW_AT_name:
3539	/* Third name preference: don't override. */
3540	if (function->name != NULL)
3541	break;
3542	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3543	is_bigendian: ddata->is_bigendian,
3544	str_offsets_base: u->str_offsets_base, val: &val,
3545	error_callback, data, string: &function->name))
3546	return 0;
3547	break;
3548
3549	case DW_AT_linkage_name:
3550	case DW_AT_MIPS_linkage_name:
3551	/* First name preference: override all. */
3552	{
3553	const char *s;
3554
3555	s = NULL;
3556	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3557	is_bigendian: ddata->is_bigendian,
3558	str_offsets_base: u->str_offsets_base, val: &val,
3559	error_callback, data, string: &s))
3560	return 0;
3561	if (s != NULL)
3562	{
3563	function->name = s;
3564	have_linkage_name = 1;
3565	}
3566	}
3567	break;
3568
3569	case DW_AT_low_pc: case DW_AT_high_pc: case DW_AT_ranges:
3570	update_pcrange (attr: &abbrev->attrs[i], val: &val, pcrange: &pcrange);
3571	break;
3572
3573	default:
3574	break;
3575	}
3576	}
3577	}
3578
3579	/* If we couldn't find a name for the function, we have no use
3580	for it. */
3581	if (is_function && function->name == NULL)
3582	{
3583	backtrace_free (state, mem: function, size: sizeof *function,
3584	error_callback, data);
3585	is_function = 0;
3586	}
3587
3588	if (is_function)
3589	{
3590	if (pcrange.have_ranges
3591	|| (pcrange.have_lowpc && pcrange.have_highpc))
3592	{
3593	if (!add_ranges (state, dwarf_sections: &ddata->dwarf_sections,
3594	base_address: ddata->base_address, is_bigendian: ddata->is_bigendian,
3595	u, base, pcrange: &pcrange, add_range: add_function_range,
3596	rdata: (void *) function, error_callback, data,
3597	vec: (void *) vec))
3598	return 0;
3599	}
3600	else
3601	{
3602	backtrace_free (state, mem: function, size: sizeof *function,
3603	error_callback, data);
3604	is_function = 0;
3605	}
3606	}
3607
3608	if (abbrev->has_children)
3609	{
3610	if (!is_function)
3611	{
3612	if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
3613	error_callback, data, vec_function,
3614	vec_inlined))
3615	return 0;
3616	}
3617	else
3618	{
3619	struct function_vector fvec;
3620
3621	/* Gather any information for inlined functions in
3622	FVEC. */
3623
3624	memset (s: &fvec, c: 0, n: sizeof fvec);
3625
3626	if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
3627	error_callback, data, vec_function,
3628	vec_inlined: &fvec))
3629	return 0;
3630
3631	if (fvec.count > 0)
3632	{
3633	struct function_addrs *p;
3634	struct function_addrs *faddrs;
3635
3636	/* Allocate a trailing entry, but don't include it
3637	in fvec.count. */
3638	p = ((struct function_addrs *)
3639	backtrace_vector_grow (state,
3640	size: sizeof (struct function_addrs),
3641	error_callback, data,
3642	vec: &fvec.vec));
3643	if (p == NULL)
3644	return 0;
3645	p->low = 0;
3646	--p->low;
3647	p->high = p->low;
3648	p->function = NULL;
3649
3650	if (!backtrace_vector_release (state, vec: &fvec.vec,
3651	error_callback, data))
3652	return 0;
3653
3654	faddrs = (struct function_addrs *) fvec.vec.base;
3655	backtrace_qsort (base: faddrs, count: fvec.count,
3656	size: sizeof (struct function_addrs),
3657	compar: function_addrs_compare);
3658
3659	function->function_addrs = faddrs;
3660	function->function_addrs_count = fvec.count;
3661	}
3662	}
3663	}
3664	}
3665
3666	return 1;
3667	}
3668
3669	/* Read function name information for a compilation unit. We look
3670	through the whole unit looking for function tags. */
3671
3672	static void
3673	read_function_info (struct backtrace_state *state, struct dwarf_data *ddata,
3674	const struct line_header *lhdr,
3675	backtrace_error_callback error_callback, void *data,
3676	struct unit *u, struct function_vector *fvec,
3677	struct function_addrs **ret_addrs,
3678	size_t *ret_addrs_count)
3679	{
3680	struct function_vector lvec;
3681	struct function_vector *pfvec;
3682	struct dwarf_buf unit_buf;
3683	struct function_addrs *p;
3684	struct function_addrs *addrs;
3685	size_t addrs_count;
3686
3687	/* Use FVEC if it is not NULL. Otherwise use our own vector. */
3688	if (fvec != NULL)
3689	pfvec = fvec;
3690	else
3691	{
3692	memset (s: &lvec, c: 0, n: sizeof lvec);
3693	pfvec = &lvec;
3694	}
3695
3696	unit_buf.name = ".debug_info";
3697	unit_buf.start = ddata->dwarf_sections.data[DEBUG_INFO];
3698	unit_buf.buf = u->unit_data;
3699	unit_buf.left = u->unit_data_len;
3700	unit_buf.is_bigendian = ddata->is_bigendian;
3701	unit_buf.error_callback = error_callback;
3702	unit_buf.data = data;
3703	unit_buf.reported_underflow = 0;
3704
3705	while (unit_buf.left > 0)
3706	{
3707	if (!read_function_entry (state, ddata, u, base: 0, unit_buf: &unit_buf, lhdr,
3708	error_callback, data, vec_function: pfvec, vec_inlined: pfvec))
3709	return;
3710	}
3711
3712	if (pfvec->count == 0)
3713	return;
3714
3715	/* Allocate a trailing entry, but don't include it in
3716	pfvec->count. */
3717	p = ((struct function_addrs *)
3718	backtrace_vector_grow (state, size: sizeof (struct function_addrs),
3719	error_callback, data, vec: &pfvec->vec));
3720	if (p == NULL)
3721	return;
3722	p->low = 0;
3723	--p->low;
3724	p->high = p->low;
3725	p->function = NULL;
3726
3727	addrs_count = pfvec->count;
3728
3729	if (fvec == NULL)
3730	{
3731	if (!backtrace_vector_release (state, vec: &lvec.vec, error_callback, data))
3732	return;
3733	addrs = (struct function_addrs *) pfvec->vec.base;
3734	}
3735	else
3736	{
3737	/* Finish this list of addresses, but leave the remaining space in
3738	the vector available for the next function unit. */
3739	addrs = ((struct function_addrs *)
3740	backtrace_vector_finish (state, vec: &fvec->vec,
3741	error_callback, data));
3742	if (addrs == NULL)
3743	return;
3744	fvec->count = 0;
3745	}
3746
3747	backtrace_qsort (base: addrs, count: addrs_count, size: sizeof (struct function_addrs),
3748	compar: function_addrs_compare);
3749
3750	*ret_addrs = addrs;
3751	*ret_addrs_count = addrs_count;
3752	}
3753
3754	/* See if PC is inlined in FUNCTION. If it is, print out the inlined
3755	information, and update FILENAME and LINENO for the caller.
3756	Returns whatever CALLBACK returns, or 0 to keep going. */
3757
3758	static int
3759	report_inlined_functions (uintptr_t pc, struct function *function,
3760	backtrace_full_callback callback, void *data,
3761	const char **filename, int *lineno)
3762	{
3763	struct function_addrs *p;
3764	struct function_addrs *match;
3765	struct function *inlined;
3766	int ret;
3767
3768	if (function->function_addrs_count == 0)
3769	return 0;
3770
3771	/* Our search isn't safe if pc == -1, as that is the sentinel
3772	value. */
3773	if (pc + 1 == 0)
3774	return 0;
3775
3776	p = ((struct function_addrs *)
3777	bsearch (key: &pc, base: function->function_addrs,
3778	nmemb: function->function_addrs_count,
3779	size: sizeof (struct function_addrs),
3780	compar: function_addrs_search));
3781	if (p == NULL)
3782	return 0;
3783
3784	/* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are
3785	sorted by low, so if pc > p->low we are at the end of a range of
3786	function_addrs with the same low value. If pc == p->low walk
3787	forward to the end of the range with that low value. Then walk
3788	backward and use the first range that includes pc. */
3789	while (pc == (p + 1)->low)
3790	++p;
3791	match = NULL;
3792	while (1)
3793	{
3794	if (pc < p->high)
3795	{
3796	match = p;
3797	break;
3798	}
3799	if (p == function->function_addrs)
3800	break;
3801	if ((p - 1)->low < p->low)
3802	break;
3803	--p;
3804	}
3805	if (match == NULL)
3806	return 0;
3807
3808	/* We found an inlined call. */
3809
3810	inlined = match->function;
3811
3812	/* Report any calls inlined into this one. */
3813	ret = report_inlined_functions (pc, function: inlined, callback, data,
3814	filename, lineno);
3815	if (ret != 0)
3816	return ret;
3817
3818	/* Report this inlined call. */
3819	ret = callback (data, pc, *filename, *lineno, inlined->name);
3820	if (ret != 0)
3821	return ret;
3822
3823	/* Our caller will report the caller of the inlined function; tell
3824	it the appropriate filename and line number. */
3825	*filename = inlined->caller_filename;
3826	*lineno = inlined->caller_lineno;
3827
3828	return 0;
3829	}
3830
3831	/* Look for a PC in the DWARF mapping for one module. On success,
3832	call CALLBACK and return whatever it returns. On error, call
3833	ERROR_CALLBACK and return 0. Sets *FOUND to 1 if the PC is found,
3834	0 if not. */
3835
3836	static int
3837	dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata,
3838	uintptr_t pc, backtrace_full_callback callback,
3839	backtrace_error_callback error_callback, void *data,
3840	int *found)
3841	{
3842	struct unit_addrs *entry;
3843	int found_entry;
3844	struct unit *u;
3845	int new_data;
3846	struct line *lines;
3847	struct line *ln;
3848	struct function_addrs *p;
3849	struct function_addrs *fmatch;
3850	struct function *function;
3851	const char *filename;
3852	int lineno;
3853	int ret;
3854
3855	*found = 1;
3856
3857	/* Find an address range that includes PC. Our search isn't safe if
3858	PC == -1, as we use that as a sentinel value, so skip the search
3859	in that case. */
3860	entry = (ddata->addrs_count == 0 || pc + 1 == 0
3861	? NULL
3862	: bsearch (key: &pc, base: ddata->addrs, nmemb: ddata->addrs_count,
3863	size: sizeof (struct unit_addrs), compar: unit_addrs_search));
3864
3865	if (entry == NULL)
3866	{
3867	*found = 0;
3868	return 0;
3869	}
3870
3871	/* Here pc >= entry->low && pc < (entry + 1)->low. The unit_addrs
3872	are sorted by low, so if pc > p->low we are at the end of a range
3873	of unit_addrs with the same low value. If pc == p->low walk
3874	forward to the end of the range with that low value. Then walk
3875	backward and use the first range that includes pc. */
3876	while (pc == (entry + 1)->low)
3877	++entry;
3878	found_entry = 0;
3879	while (1)
3880	{
3881	if (pc < entry->high)
3882	{
3883	found_entry = 1;
3884	break;
3885	}
3886	if (entry == ddata->addrs)
3887	break;
3888	if ((entry - 1)->low < entry->low)
3889	break;
3890	--entry;
3891	}
3892	if (!found_entry)
3893	{
3894	*found = 0;
3895	return 0;
3896	}
3897
3898	/* We need the lines, lines_count, function_addrs,
3899	function_addrs_count fields of u. If they are not set, we need
3900	to set them. When running in threaded mode, we need to allow for
3901	the possibility that some other thread is setting them
3902	simultaneously. */
3903
3904	u = entry->u;
3905	lines = u->lines;
3906
3907	/* Skip units with no useful line number information by walking
3908	backward. Useless line number information is marked by setting
3909	lines == -1. */
3910	while (entry > ddata->addrs
3911	&& pc >= (entry - 1)->low
3912	&& pc < (entry - 1)->high)
3913	{
3914	if (state->threaded)
3915	lines = (struct line *) backtrace_atomic_load_pointer (&u->lines);
3916
3917	if (lines != (struct line *) (uintptr_t) -1)
3918	break;
3919
3920	--entry;
3921
3922	u = entry->u;
3923	lines = u->lines;
3924	}
3925
3926	if (state->threaded)
3927	lines = backtrace_atomic_load_pointer (&u->lines);
3928
3929	new_data = 0;
3930	if (lines == NULL)
3931	{
3932	struct function_addrs *function_addrs;
3933	size_t function_addrs_count;
3934	struct line_header lhdr;
3935	size_t count;
3936
3937	/* We have never read the line information for this unit. Read
3938	it now. */
3939
3940	function_addrs = NULL;
3941	function_addrs_count = 0;
3942	if (read_line_info (state, ddata, error_callback, data, u: entry->u, hdr: &lhdr,
3943	lines: &lines, lines_count: &count))
3944	{
3945	struct function_vector *pfvec;
3946
3947	/* If not threaded, reuse DDATA->FVEC for better memory
3948	consumption. */
3949	if (state->threaded)
3950	pfvec = NULL;
3951	else
3952	pfvec = &ddata->fvec;
3953	read_function_info (state, ddata, lhdr: &lhdr, error_callback, data,
3954	u: entry->u, fvec: pfvec, ret_addrs: &function_addrs,
3955	ret_addrs_count: &function_addrs_count);
3956	free_line_header (state, hdr: &lhdr, error_callback, data);
3957	new_data = 1;
3958	}
3959
3960	/* Atomically store the information we just read into the unit.
3961	If another thread is simultaneously writing, it presumably
3962	read the same information, and we don't care which one we
3963	wind up with; we just leak the other one. We do have to
3964	write the lines field last, so that the acquire-loads above
3965	ensure that the other fields are set. */
3966
3967	if (!state->threaded)
3968	{
3969	u->lines_count = count;
3970	u->function_addrs = function_addrs;
3971	u->function_addrs_count = function_addrs_count;
3972	u->lines = lines;
3973	}
3974	else
3975	{
3976	backtrace_atomic_store_size_t (&u->lines_count, count);
3977	backtrace_atomic_store_pointer (&u->function_addrs, function_addrs);
3978	backtrace_atomic_store_size_t (&u->function_addrs_count,
3979	function_addrs_count);
3980	backtrace_atomic_store_pointer (&u->lines, lines);
3981	}
3982	}
3983
3984	/* Now all fields of U have been initialized. */
3985
3986	if (lines == (struct line *) (uintptr_t) -1)
3987	{
3988	/* If reading the line number information failed in some way,
3989	try again to see if there is a better compilation unit for
3990	this PC. */
3991	if (new_data)
3992	return dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
3993	data, found);
3994	return callback (data, pc, NULL, 0, NULL);
3995	}
3996
3997	/* Search for PC within this unit. */
3998
3999	ln = (struct line *) bsearch (key: &pc, base: lines, nmemb: entry->u->lines_count,
4000	size: sizeof (struct line), compar: line_search);
4001	if (ln == NULL)
4002	{
4003	/* The PC is between the low_pc and high_pc attributes of the
4004	compilation unit, but no entry in the line table covers it.
4005	This implies that the start of the compilation unit has no
4006	line number information. */
4007
4008	if (entry->u->abs_filename == NULL)
4009	{
4010	const char *filename;
4011
4012	filename = entry->u->filename;
4013	if (filename != NULL
4014	&& !IS_ABSOLUTE_PATH (filename)
4015	&& entry->u->comp_dir != NULL)
4016	{
4017	size_t filename_len;
4018	const char *dir;
4019	size_t dir_len;
4020	char *s;
4021
4022	filename_len = strlen (s: filename);
4023	dir = entry->u->comp_dir;
4024	dir_len = strlen (s: dir);
4025	s = (char *) backtrace_alloc (state, size: dir_len + filename_len + 2,
4026	error_callback, data);
4027	if (s == NULL)
4028	{
4029	*found = 0;
4030	return 0;
4031	}
4032	memcpy (dest: s, src: dir, n: dir_len);
4033	/* FIXME: Should use backslash if DOS file system. */
4034	s[dir_len] = '/';
4035	memcpy (dest: s + dir_len + 1, src: filename, n: filename_len + 1);
4036	filename = s;
4037	}
4038	entry->u->abs_filename = filename;
4039	}
4040
4041	return callback (data, pc, entry->u->abs_filename, 0, NULL);
4042	}
4043
4044	/* Search for function name within this unit. */
4045
4046	if (entry->u->function_addrs_count == 0)
4047	return callback (data, pc, ln->filename, ln->lineno, NULL);
4048
4049	p = ((struct function_addrs *)
4050	bsearch (key: &pc, base: entry->u->function_addrs,
4051	nmemb: entry->u->function_addrs_count,
4052	size: sizeof (struct function_addrs),
4053	compar: function_addrs_search));
4054	if (p == NULL)
4055	return callback (data, pc, ln->filename, ln->lineno, NULL);
4056
4057	/* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are
4058	sorted by low, so if pc > p->low we are at the end of a range of
4059	function_addrs with the same low value. If pc == p->low walk
4060	forward to the end of the range with that low value. Then walk
4061	backward and use the first range that includes pc. */
4062	while (pc == (p + 1)->low)
4063	++p;
4064	fmatch = NULL;
4065	while (1)
4066	{
4067	if (pc < p->high)
4068	{
4069	fmatch = p;
4070	break;
4071	}
4072	if (p == entry->u->function_addrs)
4073	break;
4074	if ((p - 1)->low < p->low)
4075	break;
4076	--p;
4077	}
4078	if (fmatch == NULL)
4079	return callback (data, pc, ln->filename, ln->lineno, NULL);
4080
4081	function = fmatch->function;
4082
4083	filename = ln->filename;
4084	lineno = ln->lineno;
4085
4086	ret = report_inlined_functions (pc, function, callback, data,
4087	filename: &filename, lineno: &lineno);
4088	if (ret != 0)
4089	return ret;
4090
4091	return callback (data, pc, filename, lineno, function->name);
4092	}
4093
4094
4095	/* Return the file/line information for a PC using the DWARF mapping
4096	we built earlier. */
4097
4098	static int
4099	dwarf_fileline (struct backtrace_state *state, uintptr_t pc,
4100	backtrace_full_callback callback,
4101	backtrace_error_callback error_callback, void *data)
4102	{
4103	struct dwarf_data *ddata;
4104	int found;
4105	int ret;
4106
4107	if (!state->threaded)
4108	{
4109	for (ddata = (struct dwarf_data *) state->fileline_data;
4110	ddata != NULL;
4111	ddata = ddata->next)
4112	{
4113	ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
4114	data, found: &found);
4115	if (ret != 0 || found)
4116	return ret;
4117	}
4118	}
4119	else
4120	{
4121	struct dwarf_data **pp;
4122
4123	pp = (struct dwarf_data **) (void *) &state->fileline_data;
4124	while (1)
4125	{
4126	ddata = backtrace_atomic_load_pointer (pp);
4127	if (ddata == NULL)
4128	break;
4129
4130	ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
4131	data, found: &found);
4132	if (ret != 0 || found)
4133	return ret;
4134
4135	pp = &ddata->next;
4136	}
4137	}
4138
4139	/* FIXME: See if any libraries have been dlopen'ed. */
4140
4141	return callback (data, pc, NULL, 0, NULL);
4142	}
4143
4144	/* Initialize our data structures from the DWARF debug info for a
4145	file. Return NULL on failure. */
4146
4147	static struct dwarf_data *
4148	build_dwarf_data (struct backtrace_state *state,
4149	struct libbacktrace_base_address base_address,
4150	const struct dwarf_sections *dwarf_sections,
4151	int is_bigendian,
4152	struct dwarf_data *altlink,
4153	backtrace_error_callback error_callback,
4154	void *data)
4155	{
4156	struct unit_addrs_vector addrs_vec;
4157	struct unit_vector units_vec;
4158	struct dwarf_data *fdata;
4159
4160	if (!build_address_map (state, base_address, dwarf_sections, is_bigendian,
4161	altlink, error_callback, data, addrs: &addrs_vec,
4162	unit_vec: &units_vec))
4163	return NULL;
4164
4165	if (!backtrace_vector_release (state, vec: &addrs_vec.vec, error_callback, data))
4166	return NULL;
4167	if (!backtrace_vector_release (state, vec: &units_vec.vec, error_callback, data))
4168	return NULL;
4169
4170	backtrace_qsort (base: (struct unit_addrs *) addrs_vec.vec.base, count: addrs_vec.count,
4171	size: sizeof (struct unit_addrs), compar: unit_addrs_compare);
4172	if (!resolve_unit_addrs_overlap (state, error_callback, data, addrs_vec: &addrs_vec))
4173	return NULL;
4174
4175	/* No qsort for units required, already sorted. */
4176
4177	fdata = ((struct dwarf_data *)
4178	backtrace_alloc (state, size: sizeof (struct dwarf_data),
4179	error_callback, data));
4180	if (fdata == NULL)
4181	return NULL;
4182
4183	fdata->next = NULL;
4184	fdata->altlink = altlink;
4185	fdata->base_address = base_address;
4186	fdata->addrs = (struct unit_addrs *) addrs_vec.vec.base;
4187	fdata->addrs_count = addrs_vec.count;
4188	fdata->units = (struct unit **) units_vec.vec.base;
4189	fdata->units_count = units_vec.count;
4190	fdata->dwarf_sections = *dwarf_sections;
4191	fdata->is_bigendian = is_bigendian;
4192	memset (s: &fdata->fvec, c: 0, n: sizeof fdata->fvec);
4193
4194	return fdata;
4195	}
4196
4197	/* Build our data structures from the DWARF sections for a module.
4198	Set FILELINE_FN and STATE->FILELINE_DATA. Return 1 on success, 0
4199	on failure. */
4200
4201	int
4202	backtrace_dwarf_add (struct backtrace_state *state,
4203	struct libbacktrace_base_address base_address,
4204	const struct dwarf_sections *dwarf_sections,
4205	int is_bigendian,
4206	struct dwarf_data *fileline_altlink,
4207	backtrace_error_callback error_callback,
4208	void *data, fileline *fileline_fn,
4209	struct dwarf_data **fileline_entry)
4210	{
4211	struct dwarf_data *fdata;
4212
4213	fdata = build_dwarf_data (state, base_address, dwarf_sections, is_bigendian,
4214	altlink: fileline_altlink, error_callback, data);
4215	if (fdata == NULL)
4216	return 0;
4217
4218	if (fileline_entry != NULL)
4219	*fileline_entry = fdata;
4220
4221	if (!state->threaded)
4222	{
4223	struct dwarf_data **pp;
4224
4225	for (pp = (struct dwarf_data **) (void *) &state->fileline_data;
4226	*pp != NULL;
4227	pp = &(*pp)->next)
4228	;
4229	*pp = fdata;
4230	}
4231	else
4232	{
4233	while (1)
4234	{
4235	struct dwarf_data **pp;
4236
4237	pp = (struct dwarf_data **) (void *) &state->fileline_data;
4238
4239	while (1)
4240	{
4241	struct dwarf_data *p;
4242
4243	p = backtrace_atomic_load_pointer (pp);
4244
4245	if (p == NULL)
4246	break;
4247
4248	pp = &p->next;
4249	}
4250
4251	if (__sync_bool_compare_and_swap (pp, NULL, fdata))
4252	break;
4253	}
4254	}
4255
4256	*fileline_fn = dwarf_fileline;
4257
4258	return 1;
4259	}
4260