1	/* dwarf.c -- Get file/line information from DWARF for backtraces.
2	Copyright (C) 2012-2024 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 for this file. */
392	uintptr_t 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	/* Sort the line vector by PC. We want a stable sort here to maintain
1280	the order of lines for the same PC values. Since the sequence is
1281	being sorted in place, their addresses cannot be relied on to
1282	maintain stability. That is the purpose of the index member. */
1283
1284	static int
1285	line_compare (const void *v1, const void *v2)
1286	{
1287	const struct line *ln1 = (const struct line *) v1;
1288	const struct line *ln2 = (const struct line *) v2;
1289
1290	if (ln1->pc < ln2->pc)
1291	return -1;
1292	else if (ln1->pc > ln2->pc)
1293	return 1;
1294	else if (ln1->idx < ln2->idx)
1295	return -1;
1296	else if (ln1->idx > ln2->idx)
1297	return 1;
1298	else
1299	return 0;
1300	}
1301
1302	/* Find a PC in a line vector. We always allocate an extra entry at
1303	the end of the lines vector, so that this routine can safely look
1304	at the next entry. Note that when there are multiple mappings for
1305	the same PC value, this will return the last one. */
1306
1307	static int
1308	line_search (const void *vkey, const void *ventry)
1309	{
1310	const uintptr_t *key = (const uintptr_t *) vkey;
1311	const struct line *entry = (const struct line *) ventry;
1312	uintptr_t pc;
1313
1314	pc = *key;
1315	if (pc < entry->pc)
1316	return -1;
1317	else if (pc >= (entry + 1)->pc)
1318	return 1;
1319	else
1320	return 0;
1321	}
1322
1323	/* Sort the abbrevs by the abbrev code. This function is passed to
1324	both qsort and bsearch. */
1325
1326	static int
1327	abbrev_compare (const void *v1, const void *v2)
1328	{
1329	const struct abbrev *a1 = (const struct abbrev *) v1;
1330	const struct abbrev *a2 = (const struct abbrev *) v2;
1331
1332	if (a1->code < a2->code)
1333	return -1;
1334	else if (a1->code > a2->code)
1335	return 1;
1336	else
1337	{
1338	/* This really shouldn't happen. It means there are two
1339	different abbrevs with the same code, and that means we don't
1340	know which one lookup_abbrev should return. */
1341	return 0;
1342	}
1343	}
1344
1345	/* Read the abbreviation table for a compilation unit. Returns 1 on
1346	success, 0 on failure. */
1347
1348	static int
1349	read_abbrevs (struct backtrace_state *state, uint64_t abbrev_offset,
1350	const unsigned char *dwarf_abbrev, size_t dwarf_abbrev_size,
1351	int is_bigendian, backtrace_error_callback error_callback,
1352	void *data, struct abbrevs *abbrevs)
1353	{
1354	struct dwarf_buf abbrev_buf;
1355	struct dwarf_buf count_buf;
1356	size_t num_abbrevs;
1357
1358	abbrevs->num_abbrevs = 0;
1359	abbrevs->abbrevs = NULL;
1360
1361	if (abbrev_offset >= dwarf_abbrev_size)
1362	{
1363	error_callback (data, "abbrev offset out of range", 0);
1364	return 0;
1365	}
1366
1367	abbrev_buf.name = ".debug_abbrev";
1368	abbrev_buf.start = dwarf_abbrev;
1369	abbrev_buf.buf = dwarf_abbrev + abbrev_offset;
1370	abbrev_buf.left = dwarf_abbrev_size - abbrev_offset;
1371	abbrev_buf.is_bigendian = is_bigendian;
1372	abbrev_buf.error_callback = error_callback;
1373	abbrev_buf.data = data;
1374	abbrev_buf.reported_underflow = 0;
1375
1376	/* Count the number of abbrevs in this list. */
1377
1378	count_buf = abbrev_buf;
1379	num_abbrevs = 0;
1380	while (read_uleb128 (buf: &count_buf) != 0)
1381	{
1382	if (count_buf.reported_underflow)
1383	return 0;
1384	++num_abbrevs;
1385	// Skip tag.
1386	read_uleb128 (buf: &count_buf);
1387	// Skip has_children.
1388	read_byte (buf: &count_buf);
1389	// Skip attributes.
1390	while (read_uleb128 (buf: &count_buf) != 0)
1391	{
1392	uint64_t form;
1393
1394	form = read_uleb128 (buf: &count_buf);
1395	if ((enum dwarf_form) form == DW_FORM_implicit_const)
1396	read_sleb128 (buf: &count_buf);
1397	}
1398	// Skip form of last attribute.
1399	read_uleb128 (buf: &count_buf);
1400	}
1401
1402	if (count_buf.reported_underflow)
1403	return 0;
1404
1405	if (num_abbrevs == 0)
1406	return 1;
1407
1408	abbrevs->abbrevs = ((struct abbrev *)
1409	backtrace_alloc (state,
1410	size: num_abbrevs * sizeof (struct abbrev),
1411	error_callback, data));
1412	if (abbrevs->abbrevs == NULL)
1413	return 0;
1414	abbrevs->num_abbrevs = num_abbrevs;
1415	memset (s: abbrevs->abbrevs, c: 0, n: num_abbrevs * sizeof (struct abbrev));
1416
1417	num_abbrevs = 0;
1418	while (1)
1419	{
1420	uint64_t code;
1421	struct abbrev a;
1422	size_t num_attrs;
1423	struct attr *attrs;
1424
1425	if (abbrev_buf.reported_underflow)
1426	goto fail;
1427
1428	code = read_uleb128 (buf: &abbrev_buf);
1429	if (code == 0)
1430	break;
1431
1432	a.code = code;
1433	a.tag = (enum dwarf_tag) read_uleb128 (buf: &abbrev_buf);
1434	a.has_children = read_byte (buf: &abbrev_buf);
1435
1436	count_buf = abbrev_buf;
1437	num_attrs = 0;
1438	while (read_uleb128 (buf: &count_buf) != 0)
1439	{
1440	uint64_t form;
1441
1442	++num_attrs;
1443	form = read_uleb128 (buf: &count_buf);
1444	if ((enum dwarf_form) form == DW_FORM_implicit_const)
1445	read_sleb128 (buf: &count_buf);
1446	}
1447
1448	if (num_attrs == 0)
1449	{
1450	attrs = NULL;
1451	read_uleb128 (buf: &abbrev_buf);
1452	read_uleb128 (buf: &abbrev_buf);
1453	}
1454	else
1455	{
1456	attrs = ((struct attr *)
1457	backtrace_alloc (state, size: num_attrs * sizeof *attrs,
1458	error_callback, data));
1459	if (attrs == NULL)
1460	goto fail;
1461	num_attrs = 0;
1462	while (1)
1463	{
1464	uint64_t name;
1465	uint64_t form;
1466
1467	name = read_uleb128 (buf: &abbrev_buf);
1468	form = read_uleb128 (buf: &abbrev_buf);
1469	if (name == 0)
1470	break;
1471	attrs[num_attrs].name = (enum dwarf_attribute) name;
1472	attrs[num_attrs].form = (enum dwarf_form) form;
1473	if ((enum dwarf_form) form == DW_FORM_implicit_const)
1474	attrs[num_attrs].val = read_sleb128 (buf: &abbrev_buf);
1475	else
1476	attrs[num_attrs].val = 0;
1477	++num_attrs;
1478	}
1479	}
1480
1481	a.num_attrs = num_attrs;
1482	a.attrs = attrs;
1483
1484	abbrevs->abbrevs[num_abbrevs] = a;
1485	++num_abbrevs;
1486	}
1487
1488	backtrace_qsort (base: abbrevs->abbrevs, count: abbrevs->num_abbrevs,
1489	size: sizeof (struct abbrev), compar: abbrev_compare);
1490
1491	return 1;
1492
1493	fail:
1494	free_abbrevs (state, abbrevs, error_callback, data);
1495	return 0;
1496	}
1497
1498	/* Return the abbrev information for an abbrev code. */
1499
1500	static const struct abbrev *
1501	lookup_abbrev (struct abbrevs *abbrevs, uint64_t code,
1502	backtrace_error_callback error_callback, void *data)
1503	{
1504	struct abbrev key;
1505	void *p;
1506
1507	/* With GCC, where abbrevs are simply numbered in order, we should
1508	be able to just look up the entry. */
1509	if (code - 1 < abbrevs->num_abbrevs
1510	&& abbrevs->abbrevs[code - 1].code == code)
1511	return &abbrevs->abbrevs[code - 1];
1512
1513	/* Otherwise we have to search. */
1514	memset (s: &key, c: 0, n: sizeof key);
1515	key.code = code;
1516	p = bsearch (key: &key, base: abbrevs->abbrevs, nmemb: abbrevs->num_abbrevs,
1517	size: sizeof (struct abbrev), compar: abbrev_compare);
1518	if (p == NULL)
1519	{
1520	error_callback (data, "invalid abbreviation code", 0);
1521	return NULL;
1522	}
1523	return (const struct abbrev *) p;
1524	}
1525
1526	/* This struct is used to gather address range information while
1527	reading attributes. We use this while building a mapping from
1528	address ranges to compilation units and then again while mapping
1529	from address ranges to function entries. Normally either
1530	lowpc/highpc is set or ranges is set. */
1531
1532	struct pcrange {
1533	uintptr_t lowpc; /* The low PC value. */
1534	int have_lowpc; /* Whether a low PC value was found. */
1535	int lowpc_is_addr_index; /* Whether lowpc is in .debug_addr. */
1536	uintptr_t highpc; /* The high PC value. */
1537	int have_highpc; /* Whether a high PC value was found. */
1538	int highpc_is_relative; /* Whether highpc is relative to lowpc. */
1539	int highpc_is_addr_index; /* Whether highpc is in .debug_addr. */
1540	uint64_t ranges; /* Offset in ranges section. */
1541	int have_ranges; /* Whether ranges is valid. */
1542	int ranges_is_index; /* Whether ranges is DW_FORM_rnglistx. */
1543	};
1544
1545	/* Update PCRANGE from an attribute value. */
1546
1547	static void
1548	update_pcrange (const struct attr* attr, const struct attr_val* val,
1549	struct pcrange *pcrange)
1550	{
1551	switch (attr->name)
1552	{
1553	case DW_AT_low_pc:
1554	if (val->encoding == ATTR_VAL_ADDRESS)
1555	{
1556	pcrange->lowpc = (uintptr_t) val->u.uint;
1557	pcrange->have_lowpc = 1;
1558	}
1559	else if (val->encoding == ATTR_VAL_ADDRESS_INDEX)
1560	{
1561	pcrange->lowpc = (uintptr_t) val->u.uint;
1562	pcrange->have_lowpc = 1;
1563	pcrange->lowpc_is_addr_index = 1;
1564	}
1565	break;
1566
1567	case DW_AT_high_pc:
1568	if (val->encoding == ATTR_VAL_ADDRESS)
1569	{
1570	pcrange->highpc = (uintptr_t) val->u.uint;
1571	pcrange->have_highpc = 1;
1572	}
1573	else if (val->encoding == ATTR_VAL_UINT)
1574	{
1575	pcrange->highpc = (uintptr_t) val->u.uint;
1576	pcrange->have_highpc = 1;
1577	pcrange->highpc_is_relative = 1;
1578	}
1579	else if (val->encoding == ATTR_VAL_ADDRESS_INDEX)
1580	{
1581	pcrange->highpc = (uintptr_t) val->u.uint;
1582	pcrange->have_highpc = 1;
1583	pcrange->highpc_is_addr_index = 1;
1584	}
1585	break;
1586
1587	case DW_AT_ranges:
1588	if (val->encoding == ATTR_VAL_UINT
1589	|| val->encoding == ATTR_VAL_REF_SECTION)
1590	{
1591	pcrange->ranges = val->u.uint;
1592	pcrange->have_ranges = 1;
1593	}
1594	else if (val->encoding == ATTR_VAL_RNGLISTS_INDEX)
1595	{
1596	pcrange->ranges = val->u.uint;
1597	pcrange->have_ranges = 1;
1598	pcrange->ranges_is_index = 1;
1599	}
1600	break;
1601
1602	default:
1603	break;
1604	}
1605	}
1606
1607	/* Call ADD_RANGE for a low/high PC pair. Returns 1 on success, 0 on
1608	error. */
1609
1610	static int
1611	add_low_high_range (struct backtrace_state *state,
1612	const struct dwarf_sections *dwarf_sections,
1613	uintptr_t base_address, int is_bigendian,
1614	struct unit *u, const struct pcrange *pcrange,
1615	int (*add_range) (struct backtrace_state *state,
1616	void *rdata, uintptr_t lowpc,
1617	uintptr_t highpc,
1618	backtrace_error_callback error_callback,
1619	void *data, void *vec),
1620	void *rdata,
1621	backtrace_error_callback error_callback, void *data,
1622	void *vec)
1623	{
1624	uintptr_t lowpc;
1625	uintptr_t highpc;
1626
1627	lowpc = pcrange->lowpc;
1628	if (pcrange->lowpc_is_addr_index)
1629	{
1630	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base, addrsize: u->addrsize,
1631	is_bigendian, addr_index: lowpc, error_callback, data,
1632	address: &lowpc))
1633	return 0;
1634	}
1635
1636	highpc = pcrange->highpc;
1637	if (pcrange->highpc_is_addr_index)
1638	{
1639	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base, addrsize: u->addrsize,
1640	is_bigendian, addr_index: highpc, error_callback, data,
1641	address: &highpc))
1642	return 0;
1643	}
1644	if (pcrange->highpc_is_relative)
1645	highpc += lowpc;
1646
1647	/* Add in the base address of the module when recording PC values,
1648	so that we can look up the PC directly. */
1649	lowpc += base_address;
1650	highpc += base_address;
1651
1652	return add_range (state, rdata, lowpc, highpc, error_callback, data, vec);
1653	}
1654
1655	/* Call ADD_RANGE for each range read from .debug_ranges, as used in
1656	DWARF versions 2 through 4. */
1657
1658	static int
1659	add_ranges_from_ranges (
1660	struct backtrace_state *state,
1661	const struct dwarf_sections *dwarf_sections,
1662	uintptr_t base_address, int is_bigendian,
1663	struct unit *u, uintptr_t base,
1664	const struct pcrange *pcrange,
1665	int (*add_range) (struct backtrace_state *state, void *rdata,
1666	uintptr_t lowpc, uintptr_t highpc,
1667	backtrace_error_callback error_callback, void *data,
1668	void *vec),
1669	void *rdata,
1670	backtrace_error_callback error_callback, void *data,
1671	void *vec)
1672	{
1673	struct dwarf_buf ranges_buf;
1674
1675	if (pcrange->ranges >= dwarf_sections->size[DEBUG_RANGES])
1676	{
1677	error_callback (data, "ranges offset out of range", 0);
1678	return 0;
1679	}
1680
1681	ranges_buf.name = ".debug_ranges";
1682	ranges_buf.start = dwarf_sections->data[DEBUG_RANGES];
1683	ranges_buf.buf = dwarf_sections->data[DEBUG_RANGES] + pcrange->ranges;
1684	ranges_buf.left = dwarf_sections->size[DEBUG_RANGES] - pcrange->ranges;
1685	ranges_buf.is_bigendian = is_bigendian;
1686	ranges_buf.error_callback = error_callback;
1687	ranges_buf.data = data;
1688	ranges_buf.reported_underflow = 0;
1689
1690	while (1)
1691	{
1692	uint64_t low;
1693	uint64_t high;
1694
1695	if (ranges_buf.reported_underflow)
1696	return 0;
1697
1698	low = read_address (buf: &ranges_buf, addrsize: u->addrsize);
1699	high = read_address (buf: &ranges_buf, addrsize: u->addrsize);
1700
1701	if (low == 0 && high == 0)
1702	break;
1703
1704	if (is_highest_address (address: low, addrsize: u->addrsize))
1705	base = (uintptr_t) high;
1706	else
1707	{
1708	if (!add_range (state, rdata,
1709	(uintptr_t) low + base + base_address,
1710	(uintptr_t) high + base + base_address,
1711	error_callback, data, vec))
1712	return 0;
1713	}
1714	}
1715
1716	if (ranges_buf.reported_underflow)
1717	return 0;
1718
1719	return 1;
1720	}
1721
1722	/* Call ADD_RANGE for each range read from .debug_rnglists, as used in
1723	DWARF version 5. */
1724
1725	static int
1726	add_ranges_from_rnglists (
1727	struct backtrace_state *state,
1728	const struct dwarf_sections *dwarf_sections,
1729	uintptr_t base_address, int is_bigendian,
1730	struct unit *u, uintptr_t base,
1731	const struct pcrange *pcrange,
1732	int (*add_range) (struct backtrace_state *state, void *rdata,
1733	uintptr_t lowpc, uintptr_t highpc,
1734	backtrace_error_callback error_callback, void *data,
1735	void *vec),
1736	void *rdata,
1737	backtrace_error_callback error_callback, void *data,
1738	void *vec)
1739	{
1740	uint64_t offset;
1741	struct dwarf_buf rnglists_buf;
1742
1743	if (!pcrange->ranges_is_index)
1744	offset = pcrange->ranges;
1745	else
1746	offset = u->rnglists_base + pcrange->ranges * (u->is_dwarf64 ? 8 : 4);
1747	if (offset >= dwarf_sections->size[DEBUG_RNGLISTS])
1748	{
1749	error_callback (data, "rnglists offset out of range", 0);
1750	return 0;
1751	}
1752
1753	rnglists_buf.name = ".debug_rnglists";
1754	rnglists_buf.start = dwarf_sections->data[DEBUG_RNGLISTS];
1755	rnglists_buf.buf = dwarf_sections->data[DEBUG_RNGLISTS] + offset;
1756	rnglists_buf.left = dwarf_sections->size[DEBUG_RNGLISTS] - offset;
1757	rnglists_buf.is_bigendian = is_bigendian;
1758	rnglists_buf.error_callback = error_callback;
1759	rnglists_buf.data = data;
1760	rnglists_buf.reported_underflow = 0;
1761
1762	if (pcrange->ranges_is_index)
1763	{
1764	offset = read_offset (buf: &rnglists_buf, is_dwarf64: u->is_dwarf64);
1765	offset += u->rnglists_base;
1766	if (offset >= dwarf_sections->size[DEBUG_RNGLISTS])
1767	{
1768	error_callback (data, "rnglists index offset out of range", 0);
1769	return 0;
1770	}
1771	rnglists_buf.buf = dwarf_sections->data[DEBUG_RNGLISTS] + offset;
1772	rnglists_buf.left = dwarf_sections->size[DEBUG_RNGLISTS] - offset;
1773	}
1774
1775	while (1)
1776	{
1777	unsigned char rle;
1778
1779	rle = read_byte (buf: &rnglists_buf);
1780	if (rle == DW_RLE_end_of_list)
1781	break;
1782	switch (rle)
1783	{
1784	case DW_RLE_base_addressx:
1785	{
1786	uint64_t index;
1787
1788	index = read_uleb128 (buf: &rnglists_buf);
1789	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
1790	addrsize: u->addrsize, is_bigendian, addr_index: index,
1791	error_callback, data, address: &base))
1792	return 0;
1793	}
1794	break;
1795
1796	case DW_RLE_startx_endx:
1797	{
1798	uint64_t index;
1799	uintptr_t low;
1800	uintptr_t high;
1801
1802	index = read_uleb128 (buf: &rnglists_buf);
1803	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
1804	addrsize: u->addrsize, is_bigendian, addr_index: index,
1805	error_callback, data, address: &low))
1806	return 0;
1807	index = read_uleb128 (buf: &rnglists_buf);
1808	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
1809	addrsize: u->addrsize, is_bigendian, addr_index: index,
1810	error_callback, data, address: &high))
1811	return 0;
1812	if (!add_range (state, rdata, low + base_address,
1813	high + base_address, error_callback, data,
1814	vec))
1815	return 0;
1816	}
1817	break;
1818
1819	case DW_RLE_startx_length:
1820	{
1821	uint64_t index;
1822	uintptr_t low;
1823	uintptr_t length;
1824
1825	index = read_uleb128 (buf: &rnglists_buf);
1826	if (!resolve_addr_index (dwarf_sections, addr_base: u->addr_base,
1827	addrsize: u->addrsize, is_bigendian, addr_index: index,
1828	error_callback, data, address: &low))
1829	return 0;
1830	length = read_uleb128 (buf: &rnglists_buf);
1831	low += base_address;
1832	if (!add_range (state, rdata, low, low + length,
1833	error_callback, data, vec))
1834	return 0;
1835	}
1836	break;
1837
1838	case DW_RLE_offset_pair:
1839	{
1840	uint64_t low;
1841	uint64_t high;
1842
1843	low = read_uleb128 (buf: &rnglists_buf);
1844	high = read_uleb128 (buf: &rnglists_buf);
1845	if (!add_range (state, rdata, low + base + base_address,
1846	high + base + base_address,
1847	error_callback, data, vec))
1848	return 0;
1849	}
1850	break;
1851
1852	case DW_RLE_base_address:
1853	base = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
1854	break;
1855
1856	case DW_RLE_start_end:
1857	{
1858	uintptr_t low;
1859	uintptr_t high;
1860
1861	low = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
1862	high = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
1863	if (!add_range (state, rdata, low + base_address,
1864	high + base_address, error_callback, data,
1865	vec))
1866	return 0;
1867	}
1868	break;
1869
1870	case DW_RLE_start_length:
1871	{
1872	uintptr_t low;
1873	uintptr_t length;
1874
1875	low = (uintptr_t) read_address (buf: &rnglists_buf, addrsize: u->addrsize);
1876	length = (uintptr_t) read_uleb128 (buf: &rnglists_buf);
1877	low += base_address;
1878	if (!add_range (state, rdata, low, low + length,
1879	error_callback, data, vec))
1880	return 0;
1881	}
1882	break;
1883
1884	default:
1885	dwarf_buf_error (buf: &rnglists_buf, msg: "unrecognized DW_RLE value", errnum: -1);
1886	return 0;
1887	}
1888	}
1889
1890	if (rnglists_buf.reported_underflow)
1891	return 0;
1892
1893	return 1;
1894	}
1895
1896	/* Call ADD_RANGE for each lowpc/highpc pair in PCRANGE. RDATA is
1897	passed to ADD_RANGE, and is either a struct unit * or a struct
1898	function *. VEC is the vector we are adding ranges to, and is
1899	either a struct unit_addrs_vector * or a struct function_vector *.
1900	Returns 1 on success, 0 on error. */
1901
1902	static int
1903	add_ranges (struct backtrace_state *state,
1904	const struct dwarf_sections *dwarf_sections,
1905	uintptr_t base_address, int is_bigendian,
1906	struct unit *u, uintptr_t base, const struct pcrange *pcrange,
1907	int (*add_range) (struct backtrace_state *state, void *rdata,
1908	uintptr_t lowpc, uintptr_t highpc,
1909	backtrace_error_callback error_callback,
1910	void *data, void *vec),
1911	void *rdata,
1912	backtrace_error_callback error_callback, void *data,
1913	void *vec)
1914	{
1915	if (pcrange->have_lowpc && pcrange->have_highpc)
1916	return add_low_high_range (state, dwarf_sections, base_address,
1917	is_bigendian, u, pcrange, add_range, rdata,
1918	error_callback, data, vec);
1919
1920	if (!pcrange->have_ranges)
1921	{
1922	/* Did not find any address ranges to add. */
1923	return 1;
1924	}
1925
1926	if (u->version < 5)
1927	return add_ranges_from_ranges (state, dwarf_sections, base_address,
1928	is_bigendian, u, base, pcrange, add_range,
1929	rdata, error_callback, data, vec);
1930	else
1931	return add_ranges_from_rnglists (state, dwarf_sections, base_address,
1932	is_bigendian, u, base, pcrange, add_range,
1933	rdata, error_callback, data, vec);
1934	}
1935
1936	/* Find the address range covered by a compilation unit, reading from
1937	UNIT_BUF and adding values to U. Returns 1 if all data could be
1938	read, 0 if there is some error. */
1939
1940	static int
1941	find_address_ranges (struct backtrace_state *state, uintptr_t base_address,
1942	struct dwarf_buf *unit_buf,
1943	const struct dwarf_sections *dwarf_sections,
1944	int is_bigendian, struct dwarf_data *altlink,
1945	backtrace_error_callback error_callback, void *data,
1946	struct unit *u, struct unit_addrs_vector *addrs,
1947	enum dwarf_tag *unit_tag)
1948	{
1949	while (unit_buf->left > 0)
1950	{
1951	uint64_t code;
1952	const struct abbrev *abbrev;
1953	struct pcrange pcrange;
1954	struct attr_val name_val;
1955	int have_name_val;
1956	struct attr_val comp_dir_val;
1957	int have_comp_dir_val;
1958	size_t i;
1959
1960	code = read_uleb128 (buf: unit_buf);
1961	if (code == 0)
1962	return 1;
1963
1964	abbrev = lookup_abbrev (abbrevs: &u->abbrevs, code, error_callback, data);
1965	if (abbrev == NULL)
1966	return 0;
1967
1968	if (unit_tag != NULL)
1969	*unit_tag = abbrev->tag;
1970
1971	memset (s: &pcrange, c: 0, n: sizeof pcrange);
1972	memset (s: &name_val, c: 0, n: sizeof name_val);
1973	have_name_val = 0;
1974	memset (s: &comp_dir_val, c: 0, n: sizeof comp_dir_val);
1975	have_comp_dir_val = 0;
1976	for (i = 0; i < abbrev->num_attrs; ++i)
1977	{
1978	struct attr_val val;
1979
1980	if (!read_attribute (form: abbrev->attrs[i].form, implicit_val: abbrev->attrs[i].val,
1981	buf: unit_buf, is_dwarf64: u->is_dwarf64, version: u->version,
1982	addrsize: u->addrsize, dwarf_sections, altlink, val: &val))
1983	return 0;
1984
1985	switch (abbrev->attrs[i].name)
1986	{
1987	case DW_AT_low_pc: case DW_AT_high_pc: case DW_AT_ranges:
1988	update_pcrange (attr: &abbrev->attrs[i], val: &val, pcrange: &pcrange);
1989	break;
1990
1991	case DW_AT_stmt_list:
1992	if ((abbrev->tag == DW_TAG_compile_unit
1993	|| abbrev->tag == DW_TAG_skeleton_unit)
1994	&& (val.encoding == ATTR_VAL_UINT
1995	|| val.encoding == ATTR_VAL_REF_SECTION))
1996	u->lineoff = val.u.uint;
1997	break;
1998
1999	case DW_AT_name:
2000	if (abbrev->tag == DW_TAG_compile_unit
2001	|| abbrev->tag == DW_TAG_skeleton_unit)
2002	{
2003	name_val = val;
2004	have_name_val = 1;
2005	}
2006	break;
2007
2008	case DW_AT_comp_dir:
2009	if (abbrev->tag == DW_TAG_compile_unit
2010	|| abbrev->tag == DW_TAG_skeleton_unit)
2011	{
2012	comp_dir_val = val;
2013	have_comp_dir_val = 1;
2014	}
2015	break;
2016
2017	case DW_AT_str_offsets_base:
2018	if ((abbrev->tag == DW_TAG_compile_unit
2019	|| abbrev->tag == DW_TAG_skeleton_unit)
2020	&& val.encoding == ATTR_VAL_REF_SECTION)
2021	u->str_offsets_base = val.u.uint;
2022	break;
2023
2024	case DW_AT_addr_base:
2025	if ((abbrev->tag == DW_TAG_compile_unit
2026	|| abbrev->tag == DW_TAG_skeleton_unit)
2027	&& val.encoding == ATTR_VAL_REF_SECTION)
2028	u->addr_base = val.u.uint;
2029	break;
2030
2031	case DW_AT_rnglists_base:
2032	if ((abbrev->tag == DW_TAG_compile_unit
2033	|| abbrev->tag == DW_TAG_skeleton_unit)
2034	&& val.encoding == ATTR_VAL_REF_SECTION)
2035	u->rnglists_base = val.u.uint;
2036	break;
2037
2038	default:
2039	break;
2040	}
2041	}
2042
2043	// Resolve strings after we're sure that we have seen
2044	// DW_AT_str_offsets_base.
2045	if (have_name_val)
2046	{
2047	if (!resolve_string (dwarf_sections, is_dwarf64: u->is_dwarf64, is_bigendian,
2048	str_offsets_base: u->str_offsets_base, val: &name_val,
2049	error_callback, data, string: &u->filename))
2050	return 0;
2051	}
2052	if (have_comp_dir_val)
2053	{
2054	if (!resolve_string (dwarf_sections, is_dwarf64: u->is_dwarf64, is_bigendian,
2055	str_offsets_base: u->str_offsets_base, val: &comp_dir_val,
2056	error_callback, data, string: &u->comp_dir))
2057	return 0;
2058	}
2059
2060	if (abbrev->tag == DW_TAG_compile_unit
2061	|| abbrev->tag == DW_TAG_subprogram
2062	|| abbrev->tag == DW_TAG_skeleton_unit)
2063	{
2064	if (!add_ranges (state, dwarf_sections, base_address,
2065	is_bigendian, u, base: pcrange.lowpc, pcrange: &pcrange,
2066	add_range: add_unit_addr, rdata: (void *) u, error_callback, data,
2067	vec: (void *) addrs))
2068	return 0;
2069
2070	/* If we found the PC range in the DW_TAG_compile_unit or
2071	DW_TAG_skeleton_unit, we can stop now. */
2072	if ((abbrev->tag == DW_TAG_compile_unit
2073	|| abbrev->tag == DW_TAG_skeleton_unit)
2074	&& (pcrange.have_ranges
2075	|| (pcrange.have_lowpc && pcrange.have_highpc)))
2076	return 1;
2077	}
2078
2079	if (abbrev->has_children)
2080	{
2081	if (!find_address_ranges (state, base_address, unit_buf,
2082	dwarf_sections, is_bigendian, altlink,
2083	error_callback, data, u, addrs, NULL))
2084	return 0;
2085	}
2086	}
2087
2088	return 1;
2089	}
2090
2091	/* Build a mapping from address ranges to the compilation units where
2092	the line number information for that range can be found. Returns 1
2093	on success, 0 on failure. */
2094
2095	static int
2096	build_address_map (struct backtrace_state *state, uintptr_t base_address,
2097	const struct dwarf_sections *dwarf_sections,
2098	int is_bigendian, struct dwarf_data *altlink,
2099	backtrace_error_callback error_callback, void *data,
2100	struct unit_addrs_vector *addrs,
2101	struct unit_vector *unit_vec)
2102	{
2103	struct dwarf_buf info;
2104	struct backtrace_vector units;
2105	size_t units_count;
2106	size_t i;
2107	struct unit **pu;
2108	size_t unit_offset = 0;
2109	struct unit_addrs *pa;
2110
2111	memset (s: &addrs->vec, c: 0, n: sizeof addrs->vec);
2112	memset (s: &unit_vec->vec, c: 0, n: sizeof unit_vec->vec);
2113	addrs->count = 0;
2114	unit_vec->count = 0;
2115
2116	/* Read through the .debug_info section. FIXME: Should we use the
2117	.debug_aranges section? gdb and addr2line don't use it, but I'm
2118	not sure why. */
2119
2120	info.name = ".debug_info";
2121	info.start = dwarf_sections->data[DEBUG_INFO];
2122	info.buf = info.start;
2123	info.left = dwarf_sections->size[DEBUG_INFO];
2124	info.is_bigendian = is_bigendian;
2125	info.error_callback = error_callback;
2126	info.data = data;
2127	info.reported_underflow = 0;
2128
2129	memset (s: &units, c: 0, n: sizeof units);
2130	units_count = 0;
2131
2132	while (info.left > 0)
2133	{
2134	const unsigned char *unit_data_start;
2135	uint64_t len;
2136	int is_dwarf64;
2137	struct dwarf_buf unit_buf;
2138	int version;
2139	int unit_type;
2140	uint64_t abbrev_offset;
2141	int addrsize;
2142	struct unit *u;
2143	enum dwarf_tag unit_tag;
2144
2145	if (info.reported_underflow)
2146	goto fail;
2147
2148	unit_data_start = info.buf;
2149
2150	len = read_initial_length (buf: &info, is_dwarf64: &is_dwarf64);
2151	unit_buf = info;
2152	unit_buf.left = len;
2153
2154	if (!advance (buf: &info, count: len))
2155	goto fail;
2156
2157	version = read_uint16 (buf: &unit_buf);
2158	if (version < 2 || version > 5)
2159	{
2160	dwarf_buf_error (buf: &unit_buf, msg: "unrecognized DWARF version", errnum: -1);
2161	goto fail;
2162	}
2163
2164	if (version < 5)
2165	unit_type = 0;
2166	else
2167	{
2168	unit_type = read_byte (buf: &unit_buf);
2169	if (unit_type == DW_UT_type || unit_type == DW_UT_split_type)
2170	{
2171	/* This unit doesn't have anything we need. */
2172	continue;
2173	}
2174	}
2175
2176	pu = ((struct unit **)
2177	backtrace_vector_grow (state, size: sizeof (struct unit *),
2178	error_callback, data, vec: &units));
2179	if (pu == NULL)
2180	goto fail;
2181
2182	u = ((struct unit *)
2183	backtrace_alloc (state, size: sizeof *u, error_callback, data));
2184	if (u == NULL)
2185	goto fail;
2186
2187	*pu = u;
2188	++units_count;
2189
2190	if (version < 5)
2191	addrsize = 0; /* Set below. */
2192	else
2193	addrsize = read_byte (buf: &unit_buf);
2194
2195	memset (s: &u->abbrevs, c: 0, n: sizeof u->abbrevs);
2196	abbrev_offset = read_offset (buf: &unit_buf, is_dwarf64);
2197	if (!read_abbrevs (state, abbrev_offset,
2198	dwarf_abbrev: dwarf_sections->data[DEBUG_ABBREV],
2199	dwarf_abbrev_size: dwarf_sections->size[DEBUG_ABBREV],
2200	is_bigendian, error_callback, data, abbrevs: &u->abbrevs))
2201	goto fail;
2202
2203	if (version < 5)
2204	addrsize = read_byte (buf: &unit_buf);
2205
2206	switch (unit_type)
2207	{
2208	case 0:
2209	break;
2210	case DW_UT_compile: case DW_UT_partial:
2211	break;
2212	case DW_UT_skeleton: case DW_UT_split_compile:
2213	read_uint64 (buf: &unit_buf); /* dwo_id */
2214	break;
2215	default:
2216	break;
2217	}
2218
2219	u->low_offset = unit_offset;
2220	unit_offset += len + (is_dwarf64 ? 12 : 4);
2221	u->high_offset = unit_offset;
2222	u->unit_data = unit_buf.buf;
2223	u->unit_data_len = unit_buf.left;
2224	u->unit_data_offset = unit_buf.buf - unit_data_start;
2225	u->version = version;
2226	u->is_dwarf64 = is_dwarf64;
2227	u->addrsize = addrsize;
2228	u->filename = NULL;
2229	u->comp_dir = NULL;
2230	u->abs_filename = NULL;
2231	u->lineoff = 0;
2232	u->str_offsets_base = 0;
2233	u->addr_base = 0;
2234	u->rnglists_base = 0;
2235
2236	/* The actual line number mappings will be read as needed. */
2237	u->lines = NULL;
2238	u->lines_count = 0;
2239	u->function_addrs = NULL;
2240	u->function_addrs_count = 0;
2241
2242	if (!find_address_ranges (state, base_address, unit_buf: &unit_buf, dwarf_sections,
2243	is_bigendian, altlink, error_callback, data,
2244	u, addrs, unit_tag: &unit_tag))
2245	goto fail;
2246
2247	if (unit_buf.reported_underflow)
2248	goto fail;
2249	}
2250	if (info.reported_underflow)
2251	goto fail;
2252
2253	/* Add a trailing addrs entry, but don't include it in addrs->count. */
2254	pa = ((struct unit_addrs *)
2255	backtrace_vector_grow (state, size: sizeof (struct unit_addrs),
2256	error_callback, data, vec: &addrs->vec));
2257	if (pa == NULL)
2258	goto fail;
2259	pa->low = 0;
2260	--pa->low;
2261	pa->high = pa->low;
2262	pa->u = NULL;
2263
2264	unit_vec->vec = units;
2265	unit_vec->count = units_count;
2266	return 1;
2267
2268	fail:
2269	if (units_count > 0)
2270	{
2271	pu = (struct unit **) units.base;
2272	for (i = 0; i < units_count; i++)
2273	{
2274	free_abbrevs (state, abbrevs: &pu[i]->abbrevs, error_callback, data);
2275	backtrace_free (state, mem: pu[i], size: sizeof **pu, error_callback, data);
2276	}
2277	backtrace_vector_free (state, vec: &units, error_callback, data);
2278	}
2279	if (addrs->count > 0)
2280	{
2281	backtrace_vector_free (state, vec: &addrs->vec, error_callback, data);
2282	addrs->count = 0;
2283	}
2284	return 0;
2285	}
2286
2287	/* Add a new mapping to the vector of line mappings that we are
2288	building. Returns 1 on success, 0 on failure. */
2289
2290	static int
2291	add_line (struct backtrace_state *state, struct dwarf_data *ddata,
2292	uintptr_t pc, const char *filename, int lineno,
2293	backtrace_error_callback error_callback, void *data,
2294	struct line_vector *vec)
2295	{
2296	struct line *ln;
2297
2298	/* If we are adding the same mapping, ignore it. This can happen
2299	when using discriminators. */
2300	if (vec->count > 0)
2301	{
2302	ln = (struct line *) vec->vec.base + (vec->count - 1);
2303	if (pc == ln->pc && filename == ln->filename && lineno == ln->lineno)
2304	return 1;
2305	}
2306
2307	ln = ((struct line *)
2308	backtrace_vector_grow (state, size: sizeof (struct line), error_callback,
2309	data, vec: &vec->vec));
2310	if (ln == NULL)
2311	return 0;
2312
2313	/* Add in the base address here, so that we can look up the PC
2314	directly. */
2315	ln->pc = pc + ddata->base_address;
2316
2317	ln->filename = filename;
2318	ln->lineno = lineno;
2319	ln->idx = vec->count;
2320
2321	++vec->count;
2322
2323	return 1;
2324	}
2325
2326	/* Free the line header information. */
2327
2328	static void
2329	free_line_header (struct backtrace_state *state, struct line_header *hdr,
2330	backtrace_error_callback error_callback, void *data)
2331	{
2332	if (hdr->dirs_count != 0)
2333	backtrace_free (state, mem: hdr->dirs, size: hdr->dirs_count * sizeof (const char *),
2334	error_callback, data);
2335	backtrace_free (state, mem: hdr->filenames,
2336	size: hdr->filenames_count * sizeof (char *),
2337	error_callback, data);
2338	}
2339
2340	/* Read the directories and file names for a line header for version
2341	2, setting fields in HDR. Return 1 on success, 0 on failure. */
2342
2343	static int
2344	read_v2_paths (struct backtrace_state *state, struct unit *u,
2345	struct dwarf_buf *hdr_buf, struct line_header *hdr)
2346	{
2347	const unsigned char *p;
2348	const unsigned char *pend;
2349	size_t i;
2350
2351	/* Count the number of directory entries. */
2352	hdr->dirs_count = 0;
2353	p = hdr_buf->buf;
2354	pend = p + hdr_buf->left;
2355	while (p < pend && *p != '\0')
2356	{
2357	p += strnlen(string: (const char *) p, maxlen: pend - p) + 1;
2358	++hdr->dirs_count;
2359	}
2360
2361	/* The index of the first entry in the list of directories is 1. Index 0 is
2362	used for the current directory of the compilation. To simplify index
2363	handling, we set entry 0 to the compilation unit directory. */
2364	++hdr->dirs_count;
2365	hdr->dirs = ((const char **)
2366	backtrace_alloc (state,
2367	size: hdr->dirs_count * sizeof (const char *),
2368	error_callback: hdr_buf->error_callback,
2369	data: hdr_buf->data));
2370	if (hdr->dirs == NULL)
2371	return 0;
2372
2373	hdr->dirs[0] = u->comp_dir;
2374	i = 1;
2375	while (*hdr_buf->buf != '\0')
2376	{
2377	if (hdr_buf->reported_underflow)
2378	return 0;
2379
2380	hdr->dirs[i] = read_string (buf: hdr_buf);
2381	if (hdr->dirs[i] == NULL)
2382	return 0;
2383	++i;
2384	}
2385	if (!advance (buf: hdr_buf, count: 1))
2386	return 0;
2387
2388	/* Count the number of file entries. */
2389	hdr->filenames_count = 0;
2390	p = hdr_buf->buf;
2391	pend = p + hdr_buf->left;
2392	while (p < pend && *p != '\0')
2393	{
2394	p += strnlen (string: (const char *) p, maxlen: pend - p) + 1;
2395	p += leb128_len (p);
2396	p += leb128_len (p);
2397	p += leb128_len (p);
2398	++hdr->filenames_count;
2399	}
2400
2401	/* The index of the first entry in the list of file names is 1. Index 0 is
2402	used for the DW_AT_name of the compilation unit. To simplify index
2403	handling, we set entry 0 to the compilation unit file name. */
2404	++hdr->filenames_count;
2405	hdr->filenames = ((const char **)
2406	backtrace_alloc (state,
2407	size: hdr->filenames_count * sizeof (char *),
2408	error_callback: hdr_buf->error_callback,
2409	data: hdr_buf->data));
2410	if (hdr->filenames == NULL)
2411	return 0;
2412	hdr->filenames[0] = u->filename;
2413	i = 1;
2414	while (*hdr_buf->buf != '\0')
2415	{
2416	const char *filename;
2417	uint64_t dir_index;
2418
2419	if (hdr_buf->reported_underflow)
2420	return 0;
2421
2422	filename = read_string (buf: hdr_buf);
2423	if (filename == NULL)
2424	return 0;
2425	dir_index = read_uleb128 (buf: hdr_buf);
2426	if (IS_ABSOLUTE_PATH (filename)
2427	|| (dir_index < hdr->dirs_count && hdr->dirs[dir_index] == NULL))
2428	hdr->filenames[i] = filename;
2429	else
2430	{
2431	const char *dir;
2432	size_t dir_len;
2433	size_t filename_len;
2434	char *s;
2435
2436	if (dir_index < hdr->dirs_count)
2437	dir = hdr->dirs[dir_index];
2438	else
2439	{
2440	dwarf_buf_error (buf: hdr_buf,
2441	msg: ("invalid directory index in "
2442	"line number program header"),
2443	errnum: 0);
2444	return 0;
2445	}
2446	dir_len = strlen (s: dir);
2447	filename_len = strlen (s: filename);
2448	s = ((char *) backtrace_alloc (state, size: dir_len + filename_len + 2,
2449	error_callback: hdr_buf->error_callback,
2450	data: hdr_buf->data));
2451	if (s == NULL)
2452	return 0;
2453	memcpy (dest: s, src: dir, n: dir_len);
2454	/* FIXME: If we are on a DOS-based file system, and the
2455	directory or the file name use backslashes, then we
2456	should use a backslash here. */
2457	s[dir_len] = '/';
2458	memcpy (dest: s + dir_len + 1, src: filename, n: filename_len + 1);
2459	hdr->filenames[i] = s;
2460	}
2461
2462	/* Ignore the modification time and size. */
2463	read_uleb128 (buf: hdr_buf);
2464	read_uleb128 (buf: hdr_buf);
2465
2466	++i;
2467	}
2468
2469	return 1;
2470	}
2471
2472	/* Read a single version 5 LNCT entry for a directory or file name in a
2473	line header. Sets *STRING to the resulting name, ignoring other
2474	data. Return 1 on success, 0 on failure. */
2475
2476	static int
2477	read_lnct (struct backtrace_state *state, struct dwarf_data *ddata,
2478	struct unit *u, struct dwarf_buf *hdr_buf,
2479	const struct line_header *hdr, size_t formats_count,
2480	const struct line_header_format *formats, const char **string)
2481	{
2482	size_t i;
2483	const char *dir;
2484	const char *path;
2485
2486	dir = NULL;
2487	path = NULL;
2488	for (i = 0; i < formats_count; i++)
2489	{
2490	struct attr_val val;
2491
2492	if (!read_attribute (form: formats[i].form, implicit_val: 0, buf: hdr_buf, is_dwarf64: u->is_dwarf64,
2493	version: u->version, addrsize: hdr->addrsize, dwarf_sections: &ddata->dwarf_sections,
2494	altlink: ddata->altlink, val: &val))
2495	return 0;
2496	switch (formats[i].lnct)
2497	{
2498	case DW_LNCT_path:
2499	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
2500	is_bigendian: ddata->is_bigendian, str_offsets_base: u->str_offsets_base,
2501	val: &val, error_callback: hdr_buf->error_callback, data: hdr_buf->data,
2502	string: &path))
2503	return 0;
2504	break;
2505	case DW_LNCT_directory_index:
2506	if (val.encoding == ATTR_VAL_UINT)
2507	{
2508	if (val.u.uint >= hdr->dirs_count)
2509	{
2510	dwarf_buf_error (buf: hdr_buf,
2511	msg: ("invalid directory index in "
2512	"line number program header"),
2513	errnum: 0);
2514	return 0;
2515	}
2516	dir = hdr->dirs[val.u.uint];
2517	}
2518	break;
2519	default:
2520	/* We don't care about timestamps or sizes or hashes. */
2521	break;
2522	}
2523	}
2524
2525	if (path == NULL)
2526	{
2527	dwarf_buf_error (buf: hdr_buf,
2528	msg: "missing file name in line number program header",
2529	errnum: 0);
2530	return 0;
2531	}
2532
2533	if (dir == NULL)
2534	*string = path;
2535	else
2536	{
2537	size_t dir_len;
2538	size_t path_len;
2539	char *s;
2540
2541	dir_len = strlen (s: dir);
2542	path_len = strlen (s: path);
2543	s = (char *) backtrace_alloc (state, size: dir_len + path_len + 2,
2544	error_callback: hdr_buf->error_callback, data: hdr_buf->data);
2545	if (s == NULL)
2546	return 0;
2547	memcpy (dest: s, src: dir, n: dir_len);
2548	/* FIXME: If we are on a DOS-based file system, and the
2549	directory or the path name use backslashes, then we should
2550	use a backslash here. */
2551	s[dir_len] = '/';
2552	memcpy (dest: s + dir_len + 1, src: path, n: path_len + 1);
2553	*string = s;
2554	}
2555
2556	return 1;
2557	}
2558
2559	/* Read a set of DWARF 5 line header format entries, setting *PCOUNT
2560	and *PPATHS. Return 1 on success, 0 on failure. */
2561
2562	static int
2563	read_line_header_format_entries (struct backtrace_state *state,
2564	struct dwarf_data *ddata,
2565	struct unit *u,
2566	struct dwarf_buf *hdr_buf,
2567	struct line_header *hdr,
2568	size_t *pcount,
2569	const char ***ppaths)
2570	{
2571	size_t formats_count;
2572	struct line_header_format *formats;
2573	size_t paths_count;
2574	const char **paths;
2575	size_t i;
2576	int ret;
2577
2578	formats_count = read_byte (buf: hdr_buf);
2579	if (formats_count == 0)
2580	formats = NULL;
2581	else
2582	{
2583	formats = ((struct line_header_format *)
2584	backtrace_alloc (state,
2585	size: (formats_count
2586	* sizeof (struct line_header_format)),
2587	error_callback: hdr_buf->error_callback,
2588	data: hdr_buf->data));
2589	if (formats == NULL)
2590	return 0;
2591
2592	for (i = 0; i < formats_count; i++)
2593	{
2594	formats[i].lnct = (int) read_uleb128(buf: hdr_buf);
2595	formats[i].form = (enum dwarf_form) read_uleb128 (buf: hdr_buf);
2596	}
2597	}
2598
2599	paths_count = read_uleb128 (buf: hdr_buf);
2600	if (paths_count == 0)
2601	{
2602	*pcount = 0;
2603	*ppaths = NULL;
2604	ret = 1;
2605	goto exit;
2606	}
2607
2608	paths = ((const char **)
2609	backtrace_alloc (state, size: paths_count * sizeof (const char *),
2610	error_callback: hdr_buf->error_callback, data: hdr_buf->data));
2611	if (paths == NULL)
2612	{
2613	ret = 0;
2614	goto exit;
2615	}
2616	for (i = 0; i < paths_count; i++)
2617	{
2618	if (!read_lnct (state, ddata, u, hdr_buf, hdr, formats_count,
2619	formats, string: &paths[i]))
2620	{
2621	backtrace_free (state, mem: paths,
2622	size: paths_count * sizeof (const char *),
2623	error_callback: hdr_buf->error_callback, data: hdr_buf->data);
2624	ret = 0;
2625	goto exit;
2626	}
2627	}
2628
2629	*pcount = paths_count;
2630	*ppaths = paths;
2631
2632	ret = 1;
2633
2634	exit:
2635	if (formats != NULL)
2636	backtrace_free (state, mem: formats,
2637	size: formats_count * sizeof (struct line_header_format),
2638	error_callback: hdr_buf->error_callback, data: hdr_buf->data);
2639
2640	return ret;
2641	}
2642
2643	/* Read the line header. Return 1 on success, 0 on failure. */
2644
2645	static int
2646	read_line_header (struct backtrace_state *state, struct dwarf_data *ddata,
2647	struct unit *u, int is_dwarf64, struct dwarf_buf *line_buf,
2648	struct line_header *hdr)
2649	{
2650	uint64_t hdrlen;
2651	struct dwarf_buf hdr_buf;
2652
2653	hdr->version = read_uint16 (buf: line_buf);
2654	if (hdr->version < 2 || hdr->version > 5)
2655	{
2656	dwarf_buf_error (buf: line_buf, msg: "unsupported line number version", errnum: -1);
2657	return 0;
2658	}
2659
2660	if (hdr->version < 5)
2661	hdr->addrsize = u->addrsize;
2662	else
2663	{
2664	hdr->addrsize = read_byte (buf: line_buf);
2665	/* We could support a non-zero segment_selector_size but I doubt
2666	we'll ever see it. */
2667	if (read_byte (buf: line_buf) != 0)
2668	{
2669	dwarf_buf_error (buf: line_buf,
2670	msg: "non-zero segment_selector_size not supported",
2671	errnum: -1);
2672	return 0;
2673	}
2674	}
2675
2676	hdrlen = read_offset (buf: line_buf, is_dwarf64);
2677
2678	hdr_buf = *line_buf;
2679	hdr_buf.left = hdrlen;
2680
2681	if (!advance (buf: line_buf, count: hdrlen))
2682	return 0;
2683
2684	hdr->min_insn_len = read_byte (buf: &hdr_buf);
2685	if (hdr->version < 4)
2686	hdr->max_ops_per_insn = 1;
2687	else
2688	hdr->max_ops_per_insn = read_byte (buf: &hdr_buf);
2689
2690	/* We don't care about default_is_stmt. */
2691	read_byte (buf: &hdr_buf);
2692
2693	hdr->line_base = read_sbyte (buf: &hdr_buf);
2694	hdr->line_range = read_byte (buf: &hdr_buf);
2695
2696	hdr->opcode_base = read_byte (buf: &hdr_buf);
2697	hdr->opcode_lengths = hdr_buf.buf;
2698	if (!advance (buf: &hdr_buf, count: hdr->opcode_base - 1))
2699	return 0;
2700
2701	if (hdr->version < 5)
2702	{
2703	if (!read_v2_paths (state, u, hdr_buf: &hdr_buf, hdr))
2704	return 0;
2705	}
2706	else
2707	{
2708	if (!read_line_header_format_entries (state, ddata, u, hdr_buf: &hdr_buf, hdr,
2709	pcount: &hdr->dirs_count,
2710	ppaths: &hdr->dirs))
2711	return 0;
2712	if (!read_line_header_format_entries (state, ddata, u, hdr_buf: &hdr_buf, hdr,
2713	pcount: &hdr->filenames_count,
2714	ppaths: &hdr->filenames))
2715	return 0;
2716	}
2717
2718	if (hdr_buf.reported_underflow)
2719	return 0;
2720
2721	return 1;
2722	}
2723
2724	/* Read the line program, adding line mappings to VEC. Return 1 on
2725	success, 0 on failure. */
2726
2727	static int
2728	read_line_program (struct backtrace_state *state, struct dwarf_data *ddata,
2729	const struct line_header *hdr, struct dwarf_buf *line_buf,
2730	struct line_vector *vec)
2731	{
2732	uint64_t address;
2733	unsigned int op_index;
2734	const char *reset_filename;
2735	const char *filename;
2736	int lineno;
2737
2738	address = 0;
2739	op_index = 0;
2740	if (hdr->filenames_count > 1)
2741	reset_filename = hdr->filenames[1];
2742	else
2743	reset_filename = "";
2744	filename = reset_filename;
2745	lineno = 1;
2746	while (line_buf->left > 0)
2747	{
2748	unsigned int op;
2749
2750	op = read_byte (buf: line_buf);
2751	if (op >= hdr->opcode_base)
2752	{
2753	unsigned int advance;
2754
2755	/* Special opcode. */
2756	op -= hdr->opcode_base;
2757	advance = op / hdr->line_range;
2758	address += (hdr->min_insn_len * (op_index + advance)
2759	/ hdr->max_ops_per_insn);
2760	op_index = (op_index + advance) % hdr->max_ops_per_insn;
2761	lineno += hdr->line_base + (int) (op % hdr->line_range);
2762	add_line (state, ddata, pc: address, filename, lineno,
2763	error_callback: line_buf->error_callback, data: line_buf->data, vec);
2764	}
2765	else if (op == DW_LNS_extended_op)
2766	{
2767	uint64_t len;
2768
2769	len = read_uleb128 (buf: line_buf);
2770	op = read_byte (buf: line_buf);
2771	switch (op)
2772	{
2773	case DW_LNE_end_sequence:
2774	/* FIXME: Should we mark the high PC here? It seems
2775	that we already have that information from the
2776	compilation unit. */
2777	address = 0;
2778	op_index = 0;
2779	filename = reset_filename;
2780	lineno = 1;
2781	break;
2782	case DW_LNE_set_address:
2783	address = read_address (buf: line_buf, addrsize: hdr->addrsize);
2784	break;
2785	case DW_LNE_define_file:
2786	{
2787	const char *f;
2788	unsigned int dir_index;
2789
2790	f = read_string (buf: line_buf);
2791	if (f == NULL)
2792	return 0;
2793	dir_index = read_uleb128 (buf: line_buf);
2794	/* Ignore that time and length. */
2795	read_uleb128 (buf: line_buf);
2796	read_uleb128 (buf: line_buf);
2797	if (IS_ABSOLUTE_PATH (f))
2798	filename = f;
2799	else
2800	{
2801	const char *dir;
2802	size_t dir_len;
2803	size_t f_len;
2804	char *p;
2805
2806	if (dir_index < hdr->dirs_count)
2807	dir = hdr->dirs[dir_index];
2808	else
2809	{
2810	dwarf_buf_error (buf: line_buf,
2811	msg: ("invalid directory index "
2812	"in line number program"),
2813	errnum: 0);
2814	return 0;
2815	}
2816	dir_len = strlen (s: dir);
2817	f_len = strlen (s: f);
2818	p = ((char *)
2819	backtrace_alloc (state, size: dir_len + f_len + 2,
2820	error_callback: line_buf->error_callback,
2821	data: line_buf->data));
2822	if (p == NULL)
2823	return 0;
2824	memcpy (dest: p, src: dir, n: dir_len);
2825	/* FIXME: If we are on a DOS-based file system,
2826	and the directory or the file name use
2827	backslashes, then we should use a backslash
2828	here. */
2829	p[dir_len] = '/';
2830	memcpy (dest: p + dir_len + 1, src: f, n: f_len + 1);
2831	filename = p;
2832	}
2833	}
2834	break;
2835	case DW_LNE_set_discriminator:
2836	/* We don't care about discriminators. */
2837	read_uleb128 (buf: line_buf);
2838	break;
2839	default:
2840	if (!advance (buf: line_buf, count: len - 1))
2841	return 0;
2842	break;
2843	}
2844	}
2845	else
2846	{
2847	switch (op)
2848	{
2849	case DW_LNS_copy:
2850	add_line (state, ddata, pc: address, filename, lineno,
2851	error_callback: line_buf->error_callback, data: line_buf->data, vec);
2852	break;
2853	case DW_LNS_advance_pc:
2854	{
2855	uint64_t advance;
2856
2857	advance = read_uleb128 (buf: line_buf);
2858	address += (hdr->min_insn_len * (op_index + advance)
2859	/ hdr->max_ops_per_insn);
2860	op_index = (op_index + advance) % hdr->max_ops_per_insn;
2861	}
2862	break;
2863	case DW_LNS_advance_line:
2864	lineno += (int) read_sleb128 (buf: line_buf);
2865	break;
2866	case DW_LNS_set_file:
2867	{
2868	uint64_t fileno;
2869
2870	fileno = read_uleb128 (buf: line_buf);
2871	if (fileno >= hdr->filenames_count)
2872	{
2873	dwarf_buf_error (buf: line_buf,
2874	msg: ("invalid file number in "
2875	"line number program"),
2876	errnum: 0);
2877	return 0;
2878	}
2879	filename = hdr->filenames[fileno];
2880	}
2881	break;
2882	case DW_LNS_set_column:
2883	read_uleb128 (buf: line_buf);
2884	break;
2885	case DW_LNS_negate_stmt:
2886	break;
2887	case DW_LNS_set_basic_block:
2888	break;
2889	case DW_LNS_const_add_pc:
2890	{
2891	unsigned int advance;
2892
2893	op = 255 - hdr->opcode_base;
2894	advance = op / hdr->line_range;
2895	address += (hdr->min_insn_len * (op_index + advance)
2896	/ hdr->max_ops_per_insn);
2897	op_index = (op_index + advance) % hdr->max_ops_per_insn;
2898	}
2899	break;
2900	case DW_LNS_fixed_advance_pc:
2901	address += read_uint16 (buf: line_buf);
2902	op_index = 0;
2903	break;
2904	case DW_LNS_set_prologue_end:
2905	break;
2906	case DW_LNS_set_epilogue_begin:
2907	break;
2908	case DW_LNS_set_isa:
2909	read_uleb128 (buf: line_buf);
2910	break;
2911	default:
2912	{
2913	unsigned int i;
2914
2915	for (i = hdr->opcode_lengths[op - 1]; i > 0; --i)
2916	read_uleb128 (buf: line_buf);
2917	}
2918	break;
2919	}
2920	}
2921	}
2922
2923	return 1;
2924	}
2925
2926	/* Read the line number information for a compilation unit. Returns 1
2927	on success, 0 on failure. */
2928
2929	static int
2930	read_line_info (struct backtrace_state *state, struct dwarf_data *ddata,
2931	backtrace_error_callback error_callback, void *data,
2932	struct unit *u, struct line_header *hdr, struct line **lines,
2933	size_t *lines_count)
2934	{
2935	struct line_vector vec;
2936	struct dwarf_buf line_buf;
2937	uint64_t len;
2938	int is_dwarf64;
2939	struct line *ln;
2940
2941	memset (s: &vec.vec, c: 0, n: sizeof vec.vec);
2942	vec.count = 0;
2943
2944	memset (s: hdr, c: 0, n: sizeof *hdr);
2945
2946	if (u->lineoff != (off_t) (size_t) u->lineoff
2947	|| (size_t) u->lineoff >= ddata->dwarf_sections.size[DEBUG_LINE])
2948	{
2949	error_callback (data, "unit line offset out of range", 0);
2950	goto fail;
2951	}
2952
2953	line_buf.name = ".debug_line";
2954	line_buf.start = ddata->dwarf_sections.data[DEBUG_LINE];
2955	line_buf.buf = ddata->dwarf_sections.data[DEBUG_LINE] + u->lineoff;
2956	line_buf.left = ddata->dwarf_sections.size[DEBUG_LINE] - u->lineoff;
2957	line_buf.is_bigendian = ddata->is_bigendian;
2958	line_buf.error_callback = error_callback;
2959	line_buf.data = data;
2960	line_buf.reported_underflow = 0;
2961
2962	len = read_initial_length (buf: &line_buf, is_dwarf64: &is_dwarf64);
2963	line_buf.left = len;
2964
2965	if (!read_line_header (state, ddata, u, is_dwarf64, line_buf: &line_buf, hdr))
2966	goto fail;
2967
2968	if (!read_line_program (state, ddata, hdr, line_buf: &line_buf, vec: &vec))
2969	goto fail;
2970
2971	if (line_buf.reported_underflow)
2972	goto fail;
2973
2974	if (vec.count == 0)
2975	{
2976	/* This is not a failure in the sense of a generating an error,
2977	but it is a failure in that sense that we have no useful
2978	information. */
2979	goto fail;
2980	}
2981
2982	/* Allocate one extra entry at the end. */
2983	ln = ((struct line *)
2984	backtrace_vector_grow (state, size: sizeof (struct line), error_callback,
2985	data, vec: &vec.vec));
2986	if (ln == NULL)
2987	goto fail;
2988	ln->pc = (uintptr_t) -1;
2989	ln->filename = NULL;
2990	ln->lineno = 0;
2991	ln->idx = 0;
2992
2993	if (!backtrace_vector_release (state, vec: &vec.vec, error_callback, data))
2994	goto fail;
2995
2996	ln = (struct line *) vec.vec.base;
2997	backtrace_qsort (base: ln, count: vec.count, size: sizeof (struct line), compar: line_compare);
2998
2999	*lines = ln;
3000	*lines_count = vec.count;
3001
3002	return 1;
3003
3004	fail:
3005	backtrace_vector_free (state, vec: &vec.vec, error_callback, data);
3006	free_line_header (state, hdr, error_callback, data);
3007	*lines = (struct line *) (uintptr_t) -1;
3008	*lines_count = 0;
3009	return 0;
3010	}
3011
3012	static const char *read_referenced_name (struct dwarf_data *, struct unit *,
3013	uint64_t, backtrace_error_callback,
3014	void *);
3015
3016	/* Read the name of a function from a DIE referenced by ATTR with VAL. */
3017
3018	static const char *
3019	read_referenced_name_from_attr (struct dwarf_data *ddata, struct unit *u,
3020	struct attr *attr, struct attr_val *val,
3021	backtrace_error_callback error_callback,
3022	void *data)
3023	{
3024	switch (attr->name)
3025	{
3026	case DW_AT_abstract_origin:
3027	case DW_AT_specification:
3028	break;
3029	default:
3030	return NULL;
3031	}
3032
3033	if (attr->form == DW_FORM_ref_sig8)
3034	return NULL;
3035
3036	if (val->encoding == ATTR_VAL_REF_INFO)
3037	{
3038	struct unit *unit
3039	= find_unit (pu: ddata->units, units_count: ddata->units_count,
3040	offset: val->u.uint);
3041	if (unit == NULL)
3042	return NULL;
3043
3044	uint64_t offset = val->u.uint - unit->low_offset;
3045	return read_referenced_name (ddata, unit, offset, error_callback, data);
3046	}
3047
3048	if (val->encoding == ATTR_VAL_UINT
3049	|| val->encoding == ATTR_VAL_REF_UNIT)
3050	return read_referenced_name (ddata, u, val->u.uint, error_callback, data);
3051
3052	if (val->encoding == ATTR_VAL_REF_ALT_INFO)
3053	{
3054	struct unit *alt_unit
3055	= find_unit (pu: ddata->altlink->units, units_count: ddata->altlink->units_count,
3056	offset: val->u.uint);
3057	if (alt_unit == NULL)
3058	return NULL;
3059
3060	uint64_t offset = val->u.uint - alt_unit->low_offset;
3061	return read_referenced_name (ddata->altlink, alt_unit, offset,
3062	error_callback, data);
3063	}
3064
3065	return NULL;
3066	}
3067
3068	/* Read the name of a function from a DIE referenced by a
3069	DW_AT_abstract_origin or DW_AT_specification tag. OFFSET is within
3070	the same compilation unit. */
3071
3072	static const char *
3073	read_referenced_name (struct dwarf_data *ddata, struct unit *u,
3074	uint64_t offset, backtrace_error_callback error_callback,
3075	void *data)
3076	{
3077	struct dwarf_buf unit_buf;
3078	uint64_t code;
3079	const struct abbrev *abbrev;
3080	const char *ret;
3081	size_t i;
3082
3083	/* OFFSET is from the start of the data for this compilation unit.
3084	U->unit_data is the data, but it starts U->unit_data_offset bytes
3085	from the beginning. */
3086
3087	if (offset < u->unit_data_offset
3088	|| offset - u->unit_data_offset >= u->unit_data_len)
3089	{
3090	error_callback (data,
3091	"abstract origin or specification out of range",
3092	0);
3093	return NULL;
3094	}
3095
3096	offset -= u->unit_data_offset;
3097
3098	unit_buf.name = ".debug_info";
3099	unit_buf.start = ddata->dwarf_sections.data[DEBUG_INFO];
3100	unit_buf.buf = u->unit_data + offset;
3101	unit_buf.left = u->unit_data_len - offset;
3102	unit_buf.is_bigendian = ddata->is_bigendian;
3103	unit_buf.error_callback = error_callback;
3104	unit_buf.data = data;
3105	unit_buf.reported_underflow = 0;
3106
3107	code = read_uleb128 (buf: &unit_buf);
3108	if (code == 0)
3109	{
3110	dwarf_buf_error (buf: &unit_buf,
3111	msg: "invalid abstract origin or specification",
3112	errnum: 0);
3113	return NULL;
3114	}
3115
3116	abbrev = lookup_abbrev (abbrevs: &u->abbrevs, code, error_callback, data);
3117	if (abbrev == NULL)
3118	return NULL;
3119
3120	ret = NULL;
3121	for (i = 0; i < abbrev->num_attrs; ++i)
3122	{
3123	struct attr_val val;
3124
3125	if (!read_attribute (form: abbrev->attrs[i].form, implicit_val: abbrev->attrs[i].val,
3126	buf: &unit_buf, is_dwarf64: u->is_dwarf64, version: u->version, addrsize: u->addrsize,
3127	dwarf_sections: &ddata->dwarf_sections, altlink: ddata->altlink, val: &val))
3128	return NULL;
3129
3130	switch (abbrev->attrs[i].name)
3131	{
3132	case DW_AT_name:
3133	/* Third name preference: don't override. A name we found in some
3134	other way, will normally be more useful -- e.g., this name is
3135	normally not mangled. */
3136	if (ret != NULL)
3137	break;
3138	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3139	is_bigendian: ddata->is_bigendian, str_offsets_base: u->str_offsets_base,
3140	val: &val, error_callback, data, string: &ret))
3141	return NULL;
3142	break;
3143
3144	case DW_AT_linkage_name:
3145	case DW_AT_MIPS_linkage_name:
3146	/* First name preference: override all. */
3147	{
3148	const char *s;
3149
3150	s = NULL;
3151	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3152	is_bigendian: ddata->is_bigendian, str_offsets_base: u->str_offsets_base,
3153	val: &val, error_callback, data, string: &s))
3154	return NULL;
3155	if (s != NULL)
3156	return s;
3157	}
3158	break;
3159
3160	case DW_AT_specification:
3161	/* Second name preference: override DW_AT_name, don't override
3162	DW_AT_linkage_name. */
3163	{
3164	const char *name;
3165
3166	name = read_referenced_name_from_attr (ddata, u, attr: &abbrev->attrs[i],
3167	val: &val, error_callback, data);
3168	if (name != NULL)
3169	ret = name;
3170	}
3171	break;
3172
3173	default:
3174	break;
3175	}
3176	}
3177
3178	return ret;
3179	}
3180
3181	/* Add a range to a unit that maps to a function. This is called via
3182	add_ranges. Returns 1 on success, 0 on error. */
3183
3184	static int
3185	add_function_range (struct backtrace_state *state, void *rdata,
3186	uintptr_t lowpc, uintptr_t highpc,
3187	backtrace_error_callback error_callback, void *data,
3188	void *pvec)
3189	{
3190	struct function *function = (struct function *) rdata;
3191	struct function_vector *vec = (struct function_vector *) pvec;
3192	struct function_addrs *p;
3193
3194	if (vec->count > 0)
3195	{
3196	p = (struct function_addrs *) vec->vec.base + (vec->count - 1);
3197	if ((lowpc == p->high || lowpc == p->high + 1)
3198	&& function == p->function)
3199	{
3200	if (highpc > p->high)
3201	p->high = highpc;
3202	return 1;
3203	}
3204	}
3205
3206	p = ((struct function_addrs *)
3207	backtrace_vector_grow (state, size: sizeof (struct function_addrs),
3208	error_callback, data, vec: &vec->vec));
3209	if (p == NULL)
3210	return 0;
3211
3212	p->low = lowpc;
3213	p->high = highpc;
3214	p->function = function;
3215
3216	++vec->count;
3217
3218	return 1;
3219	}
3220
3221	/* Read one entry plus all its children. Add function addresses to
3222	VEC. Returns 1 on success, 0 on error. */
3223
3224	static int
3225	read_function_entry (struct backtrace_state *state, struct dwarf_data *ddata,
3226	struct unit *u, uintptr_t base, struct dwarf_buf *unit_buf,
3227	const struct line_header *lhdr,
3228	backtrace_error_callback error_callback, void *data,
3229	struct function_vector *vec_function,
3230	struct function_vector *vec_inlined)
3231	{
3232	while (unit_buf->left > 0)
3233	{
3234	uint64_t code;
3235	const struct abbrev *abbrev;
3236	int is_function;
3237	struct function *function;
3238	struct function_vector *vec;
3239	size_t i;
3240	struct pcrange pcrange;
3241	int have_linkage_name;
3242
3243	code = read_uleb128 (buf: unit_buf);
3244	if (code == 0)
3245	return 1;
3246
3247	abbrev = lookup_abbrev (abbrevs: &u->abbrevs, code, error_callback, data);
3248	if (abbrev == NULL)
3249	return 0;
3250
3251	is_function = (abbrev->tag == DW_TAG_subprogram
3252	|| abbrev->tag == DW_TAG_entry_point
3253	|| abbrev->tag == DW_TAG_inlined_subroutine);
3254
3255	if (abbrev->tag == DW_TAG_inlined_subroutine)
3256	vec = vec_inlined;
3257	else
3258	vec = vec_function;
3259
3260	function = NULL;
3261	if (is_function)
3262	{
3263	function = ((struct function *)
3264	backtrace_alloc (state, size: sizeof *function,
3265	error_callback, data));
3266	if (function == NULL)
3267	return 0;
3268	memset (s: function, c: 0, n: sizeof *function);
3269	}
3270
3271	memset (s: &pcrange, c: 0, n: sizeof pcrange);
3272	have_linkage_name = 0;
3273	for (i = 0; i < abbrev->num_attrs; ++i)
3274	{
3275	struct attr_val val;
3276
3277	if (!read_attribute (form: abbrev->attrs[i].form, implicit_val: abbrev->attrs[i].val,
3278	buf: unit_buf, is_dwarf64: u->is_dwarf64, version: u->version,
3279	addrsize: u->addrsize, dwarf_sections: &ddata->dwarf_sections,
3280	altlink: ddata->altlink, val: &val))
3281	return 0;
3282
3283	/* The compile unit sets the base address for any address
3284	ranges in the function entries. */
3285	if ((abbrev->tag == DW_TAG_compile_unit
3286	|| abbrev->tag == DW_TAG_skeleton_unit)
3287	&& abbrev->attrs[i].name == DW_AT_low_pc)
3288	{
3289	if (val.encoding == ATTR_VAL_ADDRESS)
3290	base = (uintptr_t) val.u.uint;
3291	else if (val.encoding == ATTR_VAL_ADDRESS_INDEX)
3292	{
3293	if (!resolve_addr_index (dwarf_sections: &ddata->dwarf_sections,
3294	addr_base: u->addr_base, addrsize: u->addrsize,
3295	is_bigendian: ddata->is_bigendian, addr_index: val.u.uint,
3296	error_callback, data, address: &base))
3297	return 0;
3298	}
3299	}
3300
3301	if (is_function)
3302	{
3303	switch (abbrev->attrs[i].name)
3304	{
3305	case DW_AT_call_file:
3306	if (val.encoding == ATTR_VAL_UINT)
3307	{
3308	if (val.u.uint >= lhdr->filenames_count)
3309	{
3310	dwarf_buf_error (buf: unit_buf,
3311	msg: ("invalid file number in "
3312	"DW_AT_call_file attribute"),
3313	errnum: 0);
3314	return 0;
3315	}
3316	function->caller_filename = lhdr->filenames[val.u.uint];
3317	}
3318	break;
3319
3320	case DW_AT_call_line:
3321	if (val.encoding == ATTR_VAL_UINT)
3322	function->caller_lineno = val.u.uint;
3323	break;
3324
3325	case DW_AT_abstract_origin:
3326	case DW_AT_specification:
3327	/* Second name preference: override DW_AT_name, don't override
3328	DW_AT_linkage_name. */
3329	if (have_linkage_name)
3330	break;
3331	{
3332	const char *name;
3333
3334	name
3335	= read_referenced_name_from_attr (ddata, u,
3336	attr: &abbrev->attrs[i], val: &val,
3337	error_callback, data);
3338	if (name != NULL)
3339	function->name = name;
3340	}
3341	break;
3342
3343	case DW_AT_name:
3344	/* Third name preference: don't override. */
3345	if (function->name != NULL)
3346	break;
3347	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3348	is_bigendian: ddata->is_bigendian,
3349	str_offsets_base: u->str_offsets_base, val: &val,
3350	error_callback, data, string: &function->name))
3351	return 0;
3352	break;
3353
3354	case DW_AT_linkage_name:
3355	case DW_AT_MIPS_linkage_name:
3356	/* First name preference: override all. */
3357	{
3358	const char *s;
3359
3360	s = NULL;
3361	if (!resolve_string (dwarf_sections: &ddata->dwarf_sections, is_dwarf64: u->is_dwarf64,
3362	is_bigendian: ddata->is_bigendian,
3363	str_offsets_base: u->str_offsets_base, val: &val,
3364	error_callback, data, string: &s))
3365	return 0;
3366	if (s != NULL)
3367	{
3368	function->name = s;
3369	have_linkage_name = 1;
3370	}
3371	}
3372	break;
3373
3374	case DW_AT_low_pc: case DW_AT_high_pc: case DW_AT_ranges:
3375	update_pcrange (attr: &abbrev->attrs[i], val: &val, pcrange: &pcrange);
3376	break;
3377
3378	default:
3379	break;
3380	}
3381	}
3382	}
3383
3384	/* If we couldn't find a name for the function, we have no use
3385	for it. */
3386	if (is_function && function->name == NULL)
3387	{
3388	backtrace_free (state, mem: function, size: sizeof *function,
3389	error_callback, data);
3390	is_function = 0;
3391	}
3392
3393	if (is_function)
3394	{
3395	if (pcrange.have_ranges
3396	|| (pcrange.have_lowpc && pcrange.have_highpc))
3397	{
3398	if (!add_ranges (state, dwarf_sections: &ddata->dwarf_sections,
3399	base_address: ddata->base_address, is_bigendian: ddata->is_bigendian,
3400	u, base, pcrange: &pcrange, add_range: add_function_range,
3401	rdata: (void *) function, error_callback, data,
3402	vec: (void *) vec))
3403	return 0;
3404	}
3405	else
3406	{
3407	backtrace_free (state, mem: function, size: sizeof *function,
3408	error_callback, data);
3409	is_function = 0;
3410	}
3411	}
3412
3413	if (abbrev->has_children)
3414	{
3415	if (!is_function)
3416	{
3417	if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
3418	error_callback, data, vec_function,
3419	vec_inlined))
3420	return 0;
3421	}
3422	else
3423	{
3424	struct function_vector fvec;
3425
3426	/* Gather any information for inlined functions in
3427	FVEC. */
3428
3429	memset (s: &fvec, c: 0, n: sizeof fvec);
3430
3431	if (!read_function_entry (state, ddata, u, base, unit_buf, lhdr,
3432	error_callback, data, vec_function,
3433	vec_inlined: &fvec))
3434	return 0;
3435
3436	if (fvec.count > 0)
3437	{
3438	struct function_addrs *p;
3439	struct function_addrs *faddrs;
3440
3441	/* Allocate a trailing entry, but don't include it
3442	in fvec.count. */
3443	p = ((struct function_addrs *)
3444	backtrace_vector_grow (state,
3445	size: sizeof (struct function_addrs),
3446	error_callback, data,
3447	vec: &fvec.vec));
3448	if (p == NULL)
3449	return 0;
3450	p->low = 0;
3451	--p->low;
3452	p->high = p->low;
3453	p->function = NULL;
3454
3455	if (!backtrace_vector_release (state, vec: &fvec.vec,
3456	error_callback, data))
3457	return 0;
3458
3459	faddrs = (struct function_addrs *) fvec.vec.base;
3460	backtrace_qsort (base: faddrs, count: fvec.count,
3461	size: sizeof (struct function_addrs),
3462	compar: function_addrs_compare);
3463
3464	function->function_addrs = faddrs;
3465	function->function_addrs_count = fvec.count;
3466	}
3467	}
3468	}
3469	}
3470
3471	return 1;
3472	}
3473
3474	/* Read function name information for a compilation unit. We look
3475	through the whole unit looking for function tags. */
3476
3477	static void
3478	read_function_info (struct backtrace_state *state, struct dwarf_data *ddata,
3479	const struct line_header *lhdr,
3480	backtrace_error_callback error_callback, void *data,
3481	struct unit *u, struct function_vector *fvec,
3482	struct function_addrs **ret_addrs,
3483	size_t *ret_addrs_count)
3484	{
3485	struct function_vector lvec;
3486	struct function_vector *pfvec;
3487	struct dwarf_buf unit_buf;
3488	struct function_addrs *p;
3489	struct function_addrs *addrs;
3490	size_t addrs_count;
3491
3492	/* Use FVEC if it is not NULL. Otherwise use our own vector. */
3493	if (fvec != NULL)
3494	pfvec = fvec;
3495	else
3496	{
3497	memset (s: &lvec, c: 0, n: sizeof lvec);
3498	pfvec = &lvec;
3499	}
3500
3501	unit_buf.name = ".debug_info";
3502	unit_buf.start = ddata->dwarf_sections.data[DEBUG_INFO];
3503	unit_buf.buf = u->unit_data;
3504	unit_buf.left = u->unit_data_len;
3505	unit_buf.is_bigendian = ddata->is_bigendian;
3506	unit_buf.error_callback = error_callback;
3507	unit_buf.data = data;
3508	unit_buf.reported_underflow = 0;
3509
3510	while (unit_buf.left > 0)
3511	{
3512	if (!read_function_entry (state, ddata, u, base: 0, unit_buf: &unit_buf, lhdr,
3513	error_callback, data, vec_function: pfvec, vec_inlined: pfvec))
3514	return;
3515	}
3516
3517	if (pfvec->count == 0)
3518	return;
3519
3520	/* Allocate a trailing entry, but don't include it in
3521	pfvec->count. */
3522	p = ((struct function_addrs *)
3523	backtrace_vector_grow (state, size: sizeof (struct function_addrs),
3524	error_callback, data, vec: &pfvec->vec));
3525	if (p == NULL)
3526	return;
3527	p->low = 0;
3528	--p->low;
3529	p->high = p->low;
3530	p->function = NULL;
3531
3532	addrs_count = pfvec->count;
3533
3534	if (fvec == NULL)
3535	{
3536	if (!backtrace_vector_release (state, vec: &lvec.vec, error_callback, data))
3537	return;
3538	addrs = (struct function_addrs *) pfvec->vec.base;
3539	}
3540	else
3541	{
3542	/* Finish this list of addresses, but leave the remaining space in
3543	the vector available for the next function unit. */
3544	addrs = ((struct function_addrs *)
3545	backtrace_vector_finish (state, vec: &fvec->vec,
3546	error_callback, data));
3547	if (addrs == NULL)
3548	return;
3549	fvec->count = 0;
3550	}
3551
3552	backtrace_qsort (base: addrs, count: addrs_count, size: sizeof (struct function_addrs),
3553	compar: function_addrs_compare);
3554
3555	*ret_addrs = addrs;
3556	*ret_addrs_count = addrs_count;
3557	}
3558
3559	/* See if PC is inlined in FUNCTION. If it is, print out the inlined
3560	information, and update FILENAME and LINENO for the caller.
3561	Returns whatever CALLBACK returns, or 0 to keep going. */
3562
3563	static int
3564	report_inlined_functions (uintptr_t pc, struct function *function,
3565	backtrace_full_callback callback, void *data,
3566	const char **filename, int *lineno)
3567	{
3568	struct function_addrs *p;
3569	struct function_addrs *match;
3570	struct function *inlined;
3571	int ret;
3572
3573	if (function->function_addrs_count == 0)
3574	return 0;
3575
3576	/* Our search isn't safe if pc == -1, as that is the sentinel
3577	value. */
3578	if (pc + 1 == 0)
3579	return 0;
3580
3581	p = ((struct function_addrs *)
3582	bsearch (key: &pc, base: function->function_addrs,
3583	nmemb: function->function_addrs_count,
3584	size: sizeof (struct function_addrs),
3585	compar: function_addrs_search));
3586	if (p == NULL)
3587	return 0;
3588
3589	/* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are
3590	sorted by low, so if pc > p->low we are at the end of a range of
3591	function_addrs with the same low value. If pc == p->low walk
3592	forward to the end of the range with that low value. Then walk
3593	backward and use the first range that includes pc. */
3594	while (pc == (p + 1)->low)
3595	++p;
3596	match = NULL;
3597	while (1)
3598	{
3599	if (pc < p->high)
3600	{
3601	match = p;
3602	break;
3603	}
3604	if (p == function->function_addrs)
3605	break;
3606	if ((p - 1)->low < p->low)
3607	break;
3608	--p;
3609	}
3610	if (match == NULL)
3611	return 0;
3612
3613	/* We found an inlined call. */
3614
3615	inlined = match->function;
3616
3617	/* Report any calls inlined into this one. */
3618	ret = report_inlined_functions (pc, function: inlined, callback, data,
3619	filename, lineno);
3620	if (ret != 0)
3621	return ret;
3622
3623	/* Report this inlined call. */
3624	ret = callback (data, pc, *filename, *lineno, inlined->name);
3625	if (ret != 0)
3626	return ret;
3627
3628	/* Our caller will report the caller of the inlined function; tell
3629	it the appropriate filename and line number. */
3630	*filename = inlined->caller_filename;
3631	*lineno = inlined->caller_lineno;
3632
3633	return 0;
3634	}
3635
3636	/* Look for a PC in the DWARF mapping for one module. On success,
3637	call CALLBACK and return whatever it returns. On error, call
3638	ERROR_CALLBACK and return 0. Sets *FOUND to 1 if the PC is found,
3639	0 if not. */
3640
3641	static int
3642	dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata,
3643	uintptr_t pc, backtrace_full_callback callback,
3644	backtrace_error_callback error_callback, void *data,
3645	int *found)
3646	{
3647	struct unit_addrs *entry;
3648	int found_entry;
3649	struct unit *u;
3650	int new_data;
3651	struct line *lines;
3652	struct line *ln;
3653	struct function_addrs *p;
3654	struct function_addrs *fmatch;
3655	struct function *function;
3656	const char *filename;
3657	int lineno;
3658	int ret;
3659
3660	*found = 1;
3661
3662	/* Find an address range that includes PC. Our search isn't safe if
3663	PC == -1, as we use that as a sentinel value, so skip the search
3664	in that case. */
3665	entry = (ddata->addrs_count == 0 || pc + 1 == 0
3666	? NULL
3667	: bsearch (key: &pc, base: ddata->addrs, nmemb: ddata->addrs_count,
3668	size: sizeof (struct unit_addrs), compar: unit_addrs_search));
3669
3670	if (entry == NULL)
3671	{
3672	*found = 0;
3673	return 0;
3674	}
3675
3676	/* Here pc >= entry->low && pc < (entry + 1)->low. The unit_addrs
3677	are sorted by low, so if pc > p->low we are at the end of a range
3678	of unit_addrs with the same low value. If pc == p->low walk
3679	forward to the end of the range with that low value. Then walk
3680	backward and use the first range that includes pc. */
3681	while (pc == (entry + 1)->low)
3682	++entry;
3683	found_entry = 0;
3684	while (1)
3685	{
3686	if (pc < entry->high)
3687	{
3688	found_entry = 1;
3689	break;
3690	}
3691	if (entry == ddata->addrs)
3692	break;
3693	if ((entry - 1)->low < entry->low)
3694	break;
3695	--entry;
3696	}
3697	if (!found_entry)
3698	{
3699	*found = 0;
3700	return 0;
3701	}
3702
3703	/* We need the lines, lines_count, function_addrs,
3704	function_addrs_count fields of u. If they are not set, we need
3705	to set them. When running in threaded mode, we need to allow for
3706	the possibility that some other thread is setting them
3707	simultaneously. */
3708
3709	u = entry->u;
3710	lines = u->lines;
3711
3712	/* Skip units with no useful line number information by walking
3713	backward. Useless line number information is marked by setting
3714	lines == -1. */
3715	while (entry > ddata->addrs
3716	&& pc >= (entry - 1)->low
3717	&& pc < (entry - 1)->high)
3718	{
3719	if (state->threaded)
3720	lines = (struct line *) backtrace_atomic_load_pointer (&u->lines);
3721
3722	if (lines != (struct line *) (uintptr_t) -1)
3723	break;
3724
3725	--entry;
3726
3727	u = entry->u;
3728	lines = u->lines;
3729	}
3730
3731	if (state->threaded)
3732	lines = backtrace_atomic_load_pointer (&u->lines);
3733
3734	new_data = 0;
3735	if (lines == NULL)
3736	{
3737	struct function_addrs *function_addrs;
3738	size_t function_addrs_count;
3739	struct line_header lhdr;
3740	size_t count;
3741
3742	/* We have never read the line information for this unit. Read
3743	it now. */
3744
3745	function_addrs = NULL;
3746	function_addrs_count = 0;
3747	if (read_line_info (state, ddata, error_callback, data, u: entry->u, hdr: &lhdr,
3748	lines: &lines, lines_count: &count))
3749	{
3750	struct function_vector *pfvec;
3751
3752	/* If not threaded, reuse DDATA->FVEC for better memory
3753	consumption. */
3754	if (state->threaded)
3755	pfvec = NULL;
3756	else
3757	pfvec = &ddata->fvec;
3758	read_function_info (state, ddata, lhdr: &lhdr, error_callback, data,
3759	u: entry->u, fvec: pfvec, ret_addrs: &function_addrs,
3760	ret_addrs_count: &function_addrs_count);
3761	free_line_header (state, hdr: &lhdr, error_callback, data);
3762	new_data = 1;
3763	}
3764
3765	/* Atomically store the information we just read into the unit.
3766	If another thread is simultaneously writing, it presumably
3767	read the same information, and we don't care which one we
3768	wind up with; we just leak the other one. We do have to
3769	write the lines field last, so that the acquire-loads above
3770	ensure that the other fields are set. */
3771
3772	if (!state->threaded)
3773	{
3774	u->lines_count = count;
3775	u->function_addrs = function_addrs;
3776	u->function_addrs_count = function_addrs_count;
3777	u->lines = lines;
3778	}
3779	else
3780	{
3781	backtrace_atomic_store_size_t (&u->lines_count, count);
3782	backtrace_atomic_store_pointer (&u->function_addrs, function_addrs);
3783	backtrace_atomic_store_size_t (&u->function_addrs_count,
3784	function_addrs_count);
3785	backtrace_atomic_store_pointer (&u->lines, lines);
3786	}
3787	}
3788
3789	/* Now all fields of U have been initialized. */
3790
3791	if (lines == (struct line *) (uintptr_t) -1)
3792	{
3793	/* If reading the line number information failed in some way,
3794	try again to see if there is a better compilation unit for
3795	this PC. */
3796	if (new_data)
3797	return dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
3798	data, found);
3799	return callback (data, pc, NULL, 0, NULL);
3800	}
3801
3802	/* Search for PC within this unit. */
3803
3804	ln = (struct line *) bsearch (key: &pc, base: lines, nmemb: entry->u->lines_count,
3805	size: sizeof (struct line), compar: line_search);
3806	if (ln == NULL)
3807	{
3808	/* The PC is between the low_pc and high_pc attributes of the
3809	compilation unit, but no entry in the line table covers it.
3810	This implies that the start of the compilation unit has no
3811	line number information. */
3812
3813	if (entry->u->abs_filename == NULL)
3814	{
3815	const char *filename;
3816
3817	filename = entry->u->filename;
3818	if (filename != NULL
3819	&& !IS_ABSOLUTE_PATH (filename)
3820	&& entry->u->comp_dir != NULL)
3821	{
3822	size_t filename_len;
3823	const char *dir;
3824	size_t dir_len;
3825	char *s;
3826
3827	filename_len = strlen (s: filename);
3828	dir = entry->u->comp_dir;
3829	dir_len = strlen (s: dir);
3830	s = (char *) backtrace_alloc (state, size: dir_len + filename_len + 2,
3831	error_callback, data);
3832	if (s == NULL)
3833	{
3834	*found = 0;
3835	return 0;
3836	}
3837	memcpy (dest: s, src: dir, n: dir_len);
3838	/* FIXME: Should use backslash if DOS file system. */
3839	s[dir_len] = '/';
3840	memcpy (dest: s + dir_len + 1, src: filename, n: filename_len + 1);
3841	filename = s;
3842	}
3843	entry->u->abs_filename = filename;
3844	}
3845
3846	return callback (data, pc, entry->u->abs_filename, 0, NULL);
3847	}
3848
3849	/* Search for function name within this unit. */
3850
3851	if (entry->u->function_addrs_count == 0)
3852	return callback (data, pc, ln->filename, ln->lineno, NULL);
3853
3854	p = ((struct function_addrs *)
3855	bsearch (key: &pc, base: entry->u->function_addrs,
3856	nmemb: entry->u->function_addrs_count,
3857	size: sizeof (struct function_addrs),
3858	compar: function_addrs_search));
3859	if (p == NULL)
3860	return callback (data, pc, ln->filename, ln->lineno, NULL);
3861
3862	/* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are
3863	sorted by low, so if pc > p->low we are at the end of a range of
3864	function_addrs with the same low value. If pc == p->low walk
3865	forward to the end of the range with that low value. Then walk
3866	backward and use the first range that includes pc. */
3867	while (pc == (p + 1)->low)
3868	++p;
3869	fmatch = NULL;
3870	while (1)
3871	{
3872	if (pc < p->high)
3873	{
3874	fmatch = p;
3875	break;
3876	}
3877	if (p == entry->u->function_addrs)
3878	break;
3879	if ((p - 1)->low < p->low)
3880	break;
3881	--p;
3882	}
3883	if (fmatch == NULL)
3884	return callback (data, pc, ln->filename, ln->lineno, NULL);
3885
3886	function = fmatch->function;
3887
3888	filename = ln->filename;
3889	lineno = ln->lineno;
3890
3891	ret = report_inlined_functions (pc, function, callback, data,
3892	filename: &filename, lineno: &lineno);
3893	if (ret != 0)
3894	return ret;
3895
3896	return callback (data, pc, filename, lineno, function->name);
3897	}
3898
3899
3900	/* Return the file/line information for a PC using the DWARF mapping
3901	we built earlier. */
3902
3903	static int
3904	dwarf_fileline (struct backtrace_state *state, uintptr_t pc,
3905	backtrace_full_callback callback,
3906	backtrace_error_callback error_callback, void *data)
3907	{
3908	struct dwarf_data *ddata;
3909	int found;
3910	int ret;
3911
3912	if (!state->threaded)
3913	{
3914	for (ddata = (struct dwarf_data *) state->fileline_data;
3915	ddata != NULL;
3916	ddata = ddata->next)
3917	{
3918	ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
3919	data, found: &found);
3920	if (ret != 0 || found)
3921	return ret;
3922	}
3923	}
3924	else
3925	{
3926	struct dwarf_data **pp;
3927
3928	pp = (struct dwarf_data **) (void *) &state->fileline_data;
3929	while (1)
3930	{
3931	ddata = backtrace_atomic_load_pointer (pp);
3932	if (ddata == NULL)
3933	break;
3934
3935	ret = dwarf_lookup_pc (state, ddata, pc, callback, error_callback,
3936	data, found: &found);
3937	if (ret != 0 || found)
3938	return ret;
3939
3940	pp = &ddata->next;
3941	}
3942	}
3943
3944	/* FIXME: See if any libraries have been dlopen'ed. */
3945
3946	return callback (data, pc, NULL, 0, NULL);
3947	}
3948
3949	/* Initialize our data structures from the DWARF debug info for a
3950	file. Return NULL on failure. */
3951
3952	static struct dwarf_data *
3953	build_dwarf_data (struct backtrace_state *state,
3954	uintptr_t base_address,
3955	const struct dwarf_sections *dwarf_sections,
3956	int is_bigendian,
3957	struct dwarf_data *altlink,
3958	backtrace_error_callback error_callback,
3959	void *data)
3960	{
3961	struct unit_addrs_vector addrs_vec;
3962	struct unit_addrs *addrs;
3963	size_t addrs_count;
3964	struct unit_vector units_vec;
3965	struct unit **units;
3966	size_t units_count;
3967	struct dwarf_data *fdata;
3968
3969	if (!build_address_map (state, base_address, dwarf_sections, is_bigendian,
3970	altlink, error_callback, data, addrs: &addrs_vec,
3971	unit_vec: &units_vec))
3972	return NULL;
3973
3974	if (!backtrace_vector_release (state, vec: &addrs_vec.vec, error_callback, data))
3975	return NULL;
3976	if (!backtrace_vector_release (state, vec: &units_vec.vec, error_callback, data))
3977	return NULL;
3978	addrs = (struct unit_addrs *) addrs_vec.vec.base;
3979	units = (struct unit **) units_vec.vec.base;
3980	addrs_count = addrs_vec.count;
3981	units_count = units_vec.count;
3982	backtrace_qsort (base: addrs, count: addrs_count, size: sizeof (struct unit_addrs),
3983	compar: unit_addrs_compare);
3984	/* No qsort for units required, already sorted. */
3985
3986	fdata = ((struct dwarf_data *)
3987	backtrace_alloc (state, size: sizeof (struct dwarf_data),
3988	error_callback, data));
3989	if (fdata == NULL)
3990	return NULL;
3991
3992	fdata->next = NULL;
3993	fdata->altlink = altlink;
3994	fdata->base_address = base_address;
3995	fdata->addrs = addrs;
3996	fdata->addrs_count = addrs_count;
3997	fdata->units = units;
3998	fdata->units_count = units_count;
3999	fdata->dwarf_sections = *dwarf_sections;
4000	fdata->is_bigendian = is_bigendian;
4001	memset (s: &fdata->fvec, c: 0, n: sizeof fdata->fvec);
4002
4003	return fdata;
4004	}
4005
4006	/* Build our data structures from the DWARF sections for a module.
4007	Set FILELINE_FN and STATE->FILELINE_DATA. Return 1 on success, 0
4008	on failure. */
4009
4010	int
4011	backtrace_dwarf_add (struct backtrace_state *state,
4012	uintptr_t base_address,
4013	const struct dwarf_sections *dwarf_sections,
4014	int is_bigendian,
4015	struct dwarf_data *fileline_altlink,
4016	backtrace_error_callback error_callback,
4017	void *data, fileline *fileline_fn,
4018	struct dwarf_data **fileline_entry)
4019	{
4020	struct dwarf_data *fdata;
4021
4022	fdata = build_dwarf_data (state, base_address, dwarf_sections, is_bigendian,
4023	altlink: fileline_altlink, error_callback, data);
4024	if (fdata == NULL)
4025	return 0;
4026
4027	if (fileline_entry != NULL)
4028	*fileline_entry = fdata;
4029
4030	if (!state->threaded)
4031	{
4032	struct dwarf_data **pp;
4033
4034	for (pp = (struct dwarf_data **) (void *) &state->fileline_data;
4035	*pp != NULL;
4036	pp = &(*pp)->next)
4037	;
4038	*pp = fdata;
4039	}
4040	else
4041	{
4042	while (1)
4043	{
4044	struct dwarf_data **pp;
4045
4046	pp = (struct dwarf_data **) (void *) &state->fileline_data;
4047
4048	while (1)
4049	{
4050	struct dwarf_data *p;
4051
4052	p = backtrace_atomic_load_pointer (pp);
4053
4054	if (p == NULL)
4055	break;
4056
4057	pp = &p->next;
4058	}
4059
4060	if (__sync_bool_compare_and_swap (pp, NULL, fdata))
4061	break;
4062	}
4063	}
4064
4065	*fileline_fn = dwarf_fileline;
4066
4067	return 1;
4068	}
4069