1 /* elf.c -- Get debug data from an ELF file for backtraces.
2    Copyright (C) 2012-2020 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 #include <sys/stat.h>
40 #include <unistd.h>
41 
42 #ifdef HAVE_DL_ITERATE_PHDR
43 #include <link.h>
44 #endif
45 
46 #include "backtrace.h"
47 #include "internal.h"
48 
49 #ifndef S_ISLNK
50  #ifndef S_IFLNK
51   #define S_IFLNK 0120000
52  #endif
53  #ifndef S_IFMT
54   #define S_IFMT 0170000
55  #endif
56  #define S_ISLNK(m) (((m) & S_IFMT) == S_IFLNK)
57 #endif
58 
59 #ifndef __GNUC__
av_bswap16(uint16_t x)60 #define __builtin_prefetch(p, r, l)
61 #define unlikely(x) (x)
62 #else
63 #define unlikely(x) __builtin_expect(!!(x), 0)
64 #endif
65 
66 #if !defined(HAVE_DECL_STRNLEN) || !HAVE_DECL_STRNLEN
67 
68 /* If strnlen is not declared, provide our own version.  */
69 
70 static size_t
71 xstrnlen (const char *s, size_t maxlen)
72 {
73   size_t i;
74 
75   for (i = 0; i < maxlen; ++i)
76     if (s[i] == '\0')
77       break;
78   return i;
79 }
80 
81 #define strnlen xstrnlen
82 
83 #endif
84 
85 #ifndef HAVE_LSTAT
86 
87 /* Dummy version of lstat for systems that don't have it.  */
88 
89 static int
90 xlstat (const char *path ATTRIBUTE_UNUSED, struct stat *st ATTRIBUTE_UNUSED)
91 {
92   return -1;
93 }
94 
95 #define lstat xlstat
96 
97 #endif
98 
99 #ifndef HAVE_READLINK
100 
101 /* Dummy version of readlink for systems that don't have it.  */
102 
103 static ssize_t
104 xreadlink (const char *path ATTRIBUTE_UNUSED, char *buf ATTRIBUTE_UNUSED,
105 	   size_t bufsz ATTRIBUTE_UNUSED)
106 {
107   return -1;
108 }
109 
110 #define readlink xreadlink
111 
112 #endif
113 
114 #ifndef HAVE_DL_ITERATE_PHDR
115 
116 /* Dummy version of dl_iterate_phdr for systems that don't have it.  */
117 
118 #define dl_phdr_info x_dl_phdr_info
119 #define dl_iterate_phdr x_dl_iterate_phdr
120 
121 struct dl_phdr_info
122 {
123   uintptr_t dlpi_addr;
124   const char *dlpi_name;
125 };
126 
127 static int
128 dl_iterate_phdr (int (*callback) (struct dl_phdr_info *,
129 				  size_t, void *) ATTRIBUTE_UNUSED,
130 		 void *data ATTRIBUTE_UNUSED)
131 {
132   return 0;
133 }
134 
135 #endif /* ! defined (HAVE_DL_ITERATE_PHDR) */
136 
137 /* The configure script must tell us whether we are 32-bit or 64-bit
138    ELF.  We could make this code test and support either possibility,
139    but there is no point.  This code only works for the currently
140    running executable, which means that we know the ELF mode at
141    configure time.  */
142 
143 #if BACKTRACE_ELF_SIZE != 32 && BACKTRACE_ELF_SIZE != 64
144 #error "Unknown BACKTRACE_ELF_SIZE"
145 #endif
146 
147 /* <link.h> might #include <elf.h> which might define our constants
148    with slightly different values.  Undefine them to be safe.  */
149 
150 #undef EI_NIDENT
151 #undef EI_MAG0
152 #undef EI_MAG1
153 #undef EI_MAG2
154 #undef EI_MAG3
155 #undef EI_CLASS
156 #undef EI_DATA
157 #undef EI_VERSION
158 #undef ELF_MAG0
159 #undef ELF_MAG1
160 #undef ELF_MAG2
161 #undef ELF_MAG3
162 #undef ELFCLASS32
163 #undef ELFCLASS64
164 #undef ELFDATA2LSB
165 #undef ELFDATA2MSB
166 #undef EV_CURRENT
167 #undef ET_DYN
168 #undef EM_PPC64
169 #undef EF_PPC64_ABI
170 #undef SHN_LORESERVE
171 #undef SHN_XINDEX
172 #undef SHN_UNDEF
173 #undef SHT_PROGBITS
174 #undef SHT_SYMTAB
175 #undef SHT_STRTAB
176 #undef SHT_DYNSYM
177 #undef SHF_COMPRESSED
178 #undef STT_OBJECT
179 #undef STT_FUNC
180 #undef NT_GNU_BUILD_ID
181 #undef ELFCOMPRESS_ZLIB
182 
183 /* Basic types.  */
184 
185 typedef uint16_t b_elf_half;    /* Elf_Half.  */
186 typedef uint32_t b_elf_word;    /* Elf_Word.  */
187 typedef int32_t  b_elf_sword;   /* Elf_Sword.  */
188 
189 #if BACKTRACE_ELF_SIZE == 32
190 
191 typedef uint32_t b_elf_addr;    /* Elf_Addr.  */
192 typedef uint32_t b_elf_off;     /* Elf_Off.  */
193 
194 typedef uint32_t b_elf_wxword;  /* 32-bit Elf_Word, 64-bit ELF_Xword.  */
195 
196 #else
197 
198 typedef uint64_t b_elf_addr;    /* Elf_Addr.  */
199 typedef uint64_t b_elf_off;     /* Elf_Off.  */
200 typedef uint64_t b_elf_xword;   /* Elf_Xword.  */
201 typedef int64_t  b_elf_sxword;  /* Elf_Sxword.  */
202 
203 typedef uint64_t b_elf_wxword;  /* 32-bit Elf_Word, 64-bit ELF_Xword.  */
204 
205 #endif
206 
207 /* Data structures and associated constants.  */
208 
209 #define EI_NIDENT 16
210 
211 typedef struct {
212   unsigned char	e_ident[EI_NIDENT];	/* ELF "magic number" */
213   b_elf_half	e_type;			/* Identifies object file type */
214   b_elf_half	e_machine;		/* Specifies required architecture */
215   b_elf_word	e_version;		/* Identifies object file version */
216   b_elf_addr	e_entry;		/* Entry point virtual address */
217   b_elf_off	e_phoff;		/* Program header table file offset */
218   b_elf_off	e_shoff;		/* Section header table file offset */
219   b_elf_word	e_flags;		/* Processor-specific flags */
220   b_elf_half	e_ehsize;		/* ELF header size in bytes */
221   b_elf_half	e_phentsize;		/* Program header table entry size */
222   b_elf_half	e_phnum;		/* Program header table entry count */
223   b_elf_half	e_shentsize;		/* Section header table entry size */
224   b_elf_half	e_shnum;		/* Section header table entry count */
225   b_elf_half	e_shstrndx;		/* Section header string table index */
226 } b_elf_ehdr;  /* Elf_Ehdr.  */
227 
228 #define EI_MAG0 0
229 #define EI_MAG1 1
230 #define EI_MAG2 2
231 #define EI_MAG3 3
232 #define EI_CLASS 4
233 #define EI_DATA 5
234 #define EI_VERSION 6
235 
236 #define ELFMAG0 0x7f
237 #define ELFMAG1 'E'
238 #define ELFMAG2 'L'
239 #define ELFMAG3 'F'
240 
241 #define ELFCLASS32 1
242 #define ELFCLASS64 2
243 
244 #define ELFDATA2LSB 1
245 #define ELFDATA2MSB 2
246 
247 #define EV_CURRENT 1
248 
249 #define ET_DYN 3
250 
251 #define EM_PPC64 21
252 #define EF_PPC64_ABI 3
253 
254 typedef struct {
255   b_elf_word	sh_name;		/* Section name, index in string tbl */
256   b_elf_word	sh_type;		/* Type of section */
257   b_elf_wxword	sh_flags;		/* Miscellaneous section attributes */
258   b_elf_addr	sh_addr;		/* Section virtual addr at execution */
259   b_elf_off	sh_offset;		/* Section file offset */
260   b_elf_wxword	sh_size;		/* Size of section in bytes */
261   b_elf_word	sh_link;		/* Index of another section */
262   b_elf_word	sh_info;		/* Additional section information */
263   b_elf_wxword	sh_addralign;		/* Section alignment */
264   b_elf_wxword	sh_entsize;		/* Entry size if section holds table */
265 } b_elf_shdr;  /* Elf_Shdr.  */
266 
267 #define SHN_UNDEF	0x0000		/* Undefined section */
268 #define SHN_LORESERVE	0xFF00		/* Begin range of reserved indices */
269 #define SHN_XINDEX	0xFFFF		/* Section index is held elsewhere */
270 
271 #define SHT_PROGBITS 1
272 #define SHT_SYMTAB 2
273 #define SHT_STRTAB 3
274 #define SHT_DYNSYM 11
275 
276 #define SHF_COMPRESSED 0x800
277 
278 #if BACKTRACE_ELF_SIZE == 32
279 
280 typedef struct
281 {
282   b_elf_word	st_name;		/* Symbol name, index in string tbl */
283   b_elf_addr	st_value;		/* Symbol value */
284   b_elf_word	st_size;		/* Symbol size */
285   unsigned char	st_info;		/* Symbol binding and type */
286   unsigned char	st_other;		/* Visibility and other data */
287   b_elf_half	st_shndx;		/* Symbol section index */
288 } b_elf_sym;  /* Elf_Sym.  */
289 
290 #else /* BACKTRACE_ELF_SIZE != 32 */
291 
292 typedef struct
293 {
294   b_elf_word	st_name;		/* Symbol name, index in string tbl */
295   unsigned char	st_info;		/* Symbol binding and type */
296   unsigned char	st_other;		/* Visibility and other data */
297   b_elf_half	st_shndx;		/* Symbol section index */
298   b_elf_addr	st_value;		/* Symbol value */
299   b_elf_xword	st_size;		/* Symbol size */
300 } b_elf_sym;  /* Elf_Sym.  */
301 
302 #endif /* BACKTRACE_ELF_SIZE != 32 */
303 
304 #define STT_OBJECT 1
305 #define STT_FUNC 2
306 
307 typedef struct
308 {
309   uint32_t namesz;
310   uint32_t descsz;
311   uint32_t type;
312   char name[1];
313 } b_elf_note;
314 
315 #define NT_GNU_BUILD_ID 3
316 
317 #if BACKTRACE_ELF_SIZE == 32
318 
319 typedef struct
320 {
321   b_elf_word	ch_type;		/* Compresstion algorithm */
322   b_elf_word	ch_size;		/* Uncompressed size */
323   b_elf_word	ch_addralign;		/* Alignment for uncompressed data */
324 } b_elf_chdr;  /* Elf_Chdr */
325 
326 #else /* BACKTRACE_ELF_SIZE != 32 */
327 
328 typedef struct
329 {
330   b_elf_word	ch_type;		/* Compression algorithm */
331   b_elf_word	ch_reserved;		/* Reserved */
332   b_elf_xword	ch_size;		/* Uncompressed size */
333   b_elf_xword	ch_addralign;		/* Alignment for uncompressed data */
334 } b_elf_chdr;  /* Elf_Chdr */
335 
336 #endif /* BACKTRACE_ELF_SIZE != 32 */
337 
338 #define ELFCOMPRESS_ZLIB 1
339 
340 /* Names of sections, indexed by enum dwarf_section in internal.h.  */
341 
342 static const char * const dwarf_section_names[DEBUG_MAX] =
343 {
344   ".debug_info",
345   ".debug_line",
346   ".debug_abbrev",
347   ".debug_ranges",
348   ".debug_str",
349   ".debug_addr",
350   ".debug_str_offsets",
351   ".debug_line_str",
352   ".debug_rnglists"
353 };
354 
355 /* Information we gather for the sections we care about.  */
356 
357 struct debug_section_info
358 {
359   /* Section file offset.  */
360   off_t offset;
361   /* Section size.  */
362   size_t size;
363   /* Section contents, after read from file.  */
364   const unsigned char *data;
365   /* Whether the SHF_COMPRESSED flag is set for the section.  */
366   int compressed;
367 };
368 
369 /* Information we keep for an ELF symbol.  */
370 
371 struct elf_symbol
372 {
373   /* The name of the symbol.  */
374   const char *name;
375   /* The address of the symbol.  */
376   uintptr_t address;
377   /* The size of the symbol.  */
378   size_t size;
379 };
380 
381 /* Information to pass to elf_syminfo.  */
382 
383 struct elf_syminfo_data
384 {
385   /* Symbols for the next module.  */
386   struct elf_syminfo_data *next;
387   /* The ELF symbols, sorted by address.  */
388   struct elf_symbol *symbols;
389   /* The number of symbols.  */
390   size_t count;
391 };
392 
393 /* Information about PowerPC64 ELFv1 .opd section.  */
394 
395 struct elf_ppc64_opd_data
396 {
397   /* Address of the .opd section.  */
398   b_elf_addr addr;
399   /* Section data.  */
400   const char *data;
401   /* Size of the .opd section.  */
402   size_t size;
403   /* Corresponding section view.  */
404   struct backtrace_view view;
405 };
406 
407 /* Compute the CRC-32 of BUF/LEN.  This uses the CRC used for
408    .gnu_debuglink files.  */
409 
410 static uint32_t
411 elf_crc32 (uint32_t crc, const unsigned char *buf, size_t len)
412 {
413   static const uint32_t crc32_table[256] =
414     {
415       0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
416       0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
417       0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
418       0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
419       0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
420       0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
421       0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
422       0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
423       0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
424       0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
425       0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
426       0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
427       0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
428       0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
429       0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
430       0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
431       0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
432       0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
433       0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
434       0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
435       0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
436       0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
437       0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
438       0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
439       0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
440       0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
441       0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
442       0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
443       0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
444       0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
445       0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
446       0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
447       0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
448       0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
449       0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
450       0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
451       0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
452       0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
453       0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
454       0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
455       0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
456       0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
457       0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
458       0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
459       0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
460       0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
461       0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
462       0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
463       0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
464       0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
465       0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
466       0x2d02ef8d
467     };
468   const unsigned char *end;
469 
470   crc = ~crc;
471   for (end = buf + len; buf < end; ++ buf)
472     crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8);
473   return ~crc;
474 }
475 
476 /* Return the CRC-32 of the entire file open at DESCRIPTOR.  */
477 
478 static uint32_t
479 elf_crc32_file (struct backtrace_state *state, int descriptor,
480 		backtrace_error_callback error_callback, void *data)
481 {
482   struct stat st;
483   struct backtrace_view file_view;
484   uint32_t ret;
485 
486   if (fstat (descriptor, &st) < 0)
487     {
488       error_callback (data, "fstat", errno);
489       return 0;
490     }
491 
492   if (!backtrace_get_view (state, descriptor, 0, st.st_size, error_callback,
493 			   data, &file_view))
494     return 0;
495 
496   ret = elf_crc32 (0, (const unsigned char *) file_view.data, st.st_size);
497 
498   backtrace_release_view (state, &file_view, error_callback, data);
499 
500   return ret;
501 }
502 
503 /* A dummy callback function used when we can't find any debug info.  */
504 
505 static int
506 elf_nodebug (struct backtrace_state *state ATTRIBUTE_UNUSED,
507 	     uintptr_t pc ATTRIBUTE_UNUSED,
508 	     backtrace_full_callback callback ATTRIBUTE_UNUSED,
509 	     backtrace_error_callback error_callback, void *data)
510 {
511   error_callback (data, "no debug info in ELF executable", -1);
512   return 0;
513 }
514 
515 /* A dummy callback function used when we can't find a symbol
516    table.  */
517 
518 static void
519 elf_nosyms (struct backtrace_state *state ATTRIBUTE_UNUSED,
520 	    uintptr_t addr ATTRIBUTE_UNUSED,
521 	    backtrace_syminfo_callback callback ATTRIBUTE_UNUSED,
522 	    backtrace_error_callback error_callback, void *data)
523 {
524   error_callback (data, "no symbol table in ELF executable", -1);
525 }
526 
527 /* Compare struct elf_symbol for qsort.  */
528 
529 static int
530 elf_symbol_compare (const void *v1, const void *v2)
531 {
532   const struct elf_symbol *e1 = (const struct elf_symbol *) v1;
533   const struct elf_symbol *e2 = (const struct elf_symbol *) v2;
534 
535   if (e1->address < e2->address)
536     return -1;
537   else if (e1->address > e2->address)
538     return 1;
539   else
540     return 0;
541 }
542 
543 /* Compare an ADDR against an elf_symbol for bsearch.  We allocate one
544    extra entry in the array so that this can look safely at the next
545    entry.  */
546 
547 static int
548 elf_symbol_search (const void *vkey, const void *ventry)
549 {
550   const uintptr_t *key = (const uintptr_t *) vkey;
551   const struct elf_symbol *entry = (const struct elf_symbol *) ventry;
552   uintptr_t addr;
553 
554   addr = *key;
555   if (addr < entry->address)
556     return -1;
557   else if (addr >= entry->address + entry->size)
558     return 1;
559   else
560     return 0;
561 }
562 
563 /* Initialize the symbol table info for elf_syminfo.  */
564 
565 static int
566 elf_initialize_syminfo (struct backtrace_state *state,
567 			uintptr_t base_address,
568 			const unsigned char *symtab_data, size_t symtab_size,
569 			const unsigned char *strtab, size_t strtab_size,
570 			backtrace_error_callback error_callback,
571 			void *data, struct elf_syminfo_data *sdata,
572 			struct elf_ppc64_opd_data *opd)
573 {
574   size_t sym_count;
575   const b_elf_sym *sym;
576   size_t elf_symbol_count;
577   size_t elf_symbol_size;
578   struct elf_symbol *elf_symbols;
579   size_t i;
580   unsigned int j;
581 
582   sym_count = symtab_size / sizeof (b_elf_sym);
583 
584   /* We only care about function symbols.  Count them.  */
585   sym = (const b_elf_sym *) symtab_data;
586   elf_symbol_count = 0;
587   for (i = 0; i < sym_count; ++i, ++sym)
588     {
589       int info;
590 
591       info = sym->st_info & 0xf;
592       if ((info == STT_FUNC || info == STT_OBJECT)
593 	  && sym->st_shndx != SHN_UNDEF)
594 	++elf_symbol_count;
595     }
596 
597   elf_symbol_size = elf_symbol_count * sizeof (struct elf_symbol);
598   elf_symbols = ((struct elf_symbol *)
599 		 backtrace_alloc (state, elf_symbol_size, error_callback,
600 				  data));
601   if (elf_symbols == NULL)
602     return 0;
603 
604   sym = (const b_elf_sym *) symtab_data;
605   j = 0;
606   for (i = 0; i < sym_count; ++i, ++sym)
607     {
608       int info;
609 
610       info = sym->st_info & 0xf;
611       if (info != STT_FUNC && info != STT_OBJECT)
612 	continue;
613       if (sym->st_shndx == SHN_UNDEF)
614 	continue;
615       if (sym->st_name >= strtab_size)
616 	{
617 	  error_callback (data, "symbol string index out of range", 0);
618 	  backtrace_free (state, elf_symbols, elf_symbol_size, error_callback,
619 			  data);
620 	  return 0;
621 	}
622       elf_symbols[j].name = (const char *) strtab + sym->st_name;
623       /* Special case PowerPC64 ELFv1 symbols in .opd section, if the symbol
624 	 is a function descriptor, read the actual code address from the
625 	 descriptor.  */
626       if (opd
627 	  && sym->st_value >= opd->addr
628 	  && sym->st_value < opd->addr + opd->size)
629 	elf_symbols[j].address
630 	  = *(const b_elf_addr *) (opd->data + (sym->st_value - opd->addr));
631       else
632 	elf_symbols[j].address = sym->st_value;
633       elf_symbols[j].address += base_address;
634       elf_symbols[j].size = sym->st_size;
635       ++j;
636     }
637 
638   backtrace_qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
639 		   elf_symbol_compare);
640 
641   sdata->next = NULL;
642   sdata->symbols = elf_symbols;
643   sdata->count = elf_symbol_count;
644 
645   return 1;
646 }
647 
648 /* Add EDATA to the list in STATE.  */
649 
650 static void
651 elf_add_syminfo_data (struct backtrace_state *state,
652 		      struct elf_syminfo_data *edata)
653 {
654   if (!state->threaded)
655     {
656       struct elf_syminfo_data **pp;
657 
658       for (pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
659 	   *pp != NULL;
660 	   pp = &(*pp)->next)
661 	;
662       *pp = edata;
663     }
664   else
665     {
666       while (1)
667 	{
668 	  struct elf_syminfo_data **pp;
669 
670 	  pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
671 
672 	  while (1)
673 	    {
674 	      struct elf_syminfo_data *p;
675 
676 	      p = backtrace_atomic_load_pointer (pp);
677 
678 	      if (p == NULL)
679 		break;
680 
681 	      pp = &p->next;
682 	    }
683 
684 	  if (__sync_bool_compare_and_swap (pp, NULL, edata))
685 	    break;
686 	}
687     }
688 }
689 
690 /* Return the symbol name and value for an ADDR.  */
691 
692 static void
693 elf_syminfo (struct backtrace_state *state, uintptr_t addr,
694 	     backtrace_syminfo_callback callback,
695 	     backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
696 	     void *data)
697 {
698   struct elf_syminfo_data *edata;
699   struct elf_symbol *sym = NULL;
700 
701   if (!state->threaded)
702     {
703       for (edata = (struct elf_syminfo_data *) state->syminfo_data;
704 	   edata != NULL;
705 	   edata = edata->next)
706 	{
707 	  sym = ((struct elf_symbol *)
708 		 bsearch (&addr, edata->symbols, edata->count,
709 			  sizeof (struct elf_symbol), elf_symbol_search));
710 	  if (sym != NULL)
711 	    break;
712 	}
713     }
714   else
715     {
716       struct elf_syminfo_data **pp;
717 
718       pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
719       while (1)
720 	{
721 	  edata = backtrace_atomic_load_pointer (pp);
722 	  if (edata == NULL)
723 	    break;
724 
725 	  sym = ((struct elf_symbol *)
726 		 bsearch (&addr, edata->symbols, edata->count,
727 			  sizeof (struct elf_symbol), elf_symbol_search));
728 	  if (sym != NULL)
729 	    break;
730 
731 	  pp = &edata->next;
732 	}
733     }
734 
735   if (sym == NULL)
736     callback (data, addr, NULL, 0, 0);
737   else
738     callback (data, addr, sym->name, sym->address, sym->size);
739 }
740 
741 /* Return whether FILENAME is a symlink.  */
742 
743 static int
744 elf_is_symlink (const char *filename)
745 {
746   struct stat st;
747 
748   if (lstat (filename, &st) < 0)
749     return 0;
750   return S_ISLNK (st.st_mode);
751 }
752 
753 /* Return the results of reading the symlink FILENAME in a buffer
754    allocated by backtrace_alloc.  Return the length of the buffer in
755    *LEN.  */
756 
757 static char *
758 elf_readlink (struct backtrace_state *state, const char *filename,
759 	      backtrace_error_callback error_callback, void *data,
760 	      size_t *plen)
761 {
762   size_t len;
763   char *buf;
764 
765   len = 128;
766   while (1)
767     {
768       ssize_t rl;
769 
770       buf = backtrace_alloc (state, len, error_callback, data);
771       if (buf == NULL)
772 	return NULL;
773       rl = readlink (filename, buf, len);
774       if (rl < 0)
775 	{
776 	  backtrace_free (state, buf, len, error_callback, data);
777 	  return NULL;
778 	}
779       if ((size_t) rl < len - 1)
780 	{
781 	  buf[rl] = '\0';
782 	  *plen = len;
783 	  return buf;
784 	}
785       backtrace_free (state, buf, len, error_callback, data);
786       len *= 2;
787     }
788 }
789 
790 #define SYSTEM_BUILD_ID_DIR "/usr/lib/debug/.build-id/"
791 
792 /* Open a separate debug info file, using the build ID to find it.
793    Returns an open file descriptor, or -1.
794 
795    The GDB manual says that the only place gdb looks for a debug file
796    when the build ID is known is in /usr/lib/debug/.build-id.  */
797 
798 static int
799 elf_open_debugfile_by_buildid (struct backtrace_state *state,
800 			       const char *buildid_data, size_t buildid_size,
801 			       backtrace_error_callback error_callback,
802 			       void *data)
803 {
804   const char * const prefix = SYSTEM_BUILD_ID_DIR;
805   const size_t prefix_len = strlen (prefix);
806   const char * const suffix = ".debug";
807   const size_t suffix_len = strlen (suffix);
808   size_t len;
809   char *bd_filename;
810   char *t;
811   size_t i;
812   int ret;
813   int does_not_exist;
814 
815   len = prefix_len + buildid_size * 2 + suffix_len + 2;
816   bd_filename = backtrace_alloc (state, len, error_callback, data);
817   if (bd_filename == NULL)
818     return -1;
819 
820   t = bd_filename;
821   memcpy (t, prefix, prefix_len);
822   t += prefix_len;
823   for (i = 0; i < buildid_size; i++)
824     {
825       unsigned char b;
826       unsigned char nib;
827 
828       b = (unsigned char) buildid_data[i];
829       nib = (b & 0xf0) >> 4;
830       *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
831       nib = b & 0x0f;
832       *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
833       if (i == 0)
834 	*t++ = '/';
835     }
836   memcpy (t, suffix, suffix_len);
837   t[suffix_len] = '\0';
838 
839   ret = backtrace_open (bd_filename, error_callback, data, &does_not_exist);
840 
841   backtrace_free (state, bd_filename, len, error_callback, data);
842 
843   /* gdb checks that the debuginfo file has the same build ID note.
844      That seems kind of pointless to me--why would it have the right
845      name but not the right build ID?--so skipping the check.  */
846 
847   return ret;
848 }
849 
850 /* Try to open a file whose name is PREFIX (length PREFIX_LEN)
851    concatenated with PREFIX2 (length PREFIX2_LEN) concatenated with
852    DEBUGLINK_NAME.  Returns an open file descriptor, or -1.  */
853 
854 static int
855 elf_try_debugfile (struct backtrace_state *state, const char *prefix,
856 		   size_t prefix_len, const char *prefix2, size_t prefix2_len,
857 		   const char *debuglink_name,
858 		   backtrace_error_callback error_callback, void *data)
859 {
860   size_t debuglink_len;
861   size_t try_len;
862   char *try;
863   int does_not_exist;
864   int ret;
865 
866   debuglink_len = strlen (debuglink_name);
867   try_len = prefix_len + prefix2_len + debuglink_len + 1;
868   try = backtrace_alloc (state, try_len, error_callback, data);
869   if (try == NULL)
870     return -1;
871 
872   memcpy (try, prefix, prefix_len);
873   memcpy (try + prefix_len, prefix2, prefix2_len);
874   memcpy (try + prefix_len + prefix2_len, debuglink_name, debuglink_len);
875   try[prefix_len + prefix2_len + debuglink_len] = '\0';
876 
877   ret = backtrace_open (try, error_callback, data, &does_not_exist);
878 
879   backtrace_free (state, try, try_len, error_callback, data);
880 
881   return ret;
882 }
883 
884 /* Find a separate debug info file, using the debuglink section data
885    to find it.  Returns an open file descriptor, or -1.  */
886 
887 static int
888 elf_find_debugfile_by_debuglink (struct backtrace_state *state,
889 				 const char *filename,
890 				 const char *debuglink_name,
891 				 backtrace_error_callback error_callback,
892 				 void *data)
893 {
894   int ret;
895   char *alc;
896   size_t alc_len;
897   const char *slash;
898   int ddescriptor;
899   const char *prefix;
900   size_t prefix_len;
901 
902   /* Resolve symlinks in FILENAME.  Since FILENAME is fairly likely to
903      be /proc/self/exe, symlinks are common.  We don't try to resolve
904      the whole path name, just the base name.  */
905   ret = -1;
906   alc = NULL;
907   alc_len = 0;
908   while (elf_is_symlink (filename))
909     {
910       char *new_buf;
911       size_t new_len;
912 
913       new_buf = elf_readlink (state, filename, error_callback, data, &new_len);
914       if (new_buf == NULL)
915 	break;
916 
917       if (new_buf[0] == '/')
918 	filename = new_buf;
919       else
920 	{
921 	  slash = strrchr (filename, '/');
922 	  if (slash == NULL)
923 	    filename = new_buf;
924 	  else
925 	    {
926 	      size_t clen;
927 	      char *c;
928 
929 	      slash++;
930 	      clen = slash - filename + strlen (new_buf) + 1;
931 	      c = backtrace_alloc (state, clen, error_callback, data);
932 	      if (c == NULL)
933 		goto done;
934 
935 	      memcpy (c, filename, slash - filename);
936 	      memcpy (c + (slash - filename), new_buf, strlen (new_buf));
937 	      c[slash - filename + strlen (new_buf)] = '\0';
938 	      backtrace_free (state, new_buf, new_len, error_callback, data);
939 	      filename = c;
940 	      new_buf = c;
941 	      new_len = clen;
942 	    }
943 	}
944 
945       if (alc != NULL)
946 	backtrace_free (state, alc, alc_len, error_callback, data);
947       alc = new_buf;
948       alc_len = new_len;
949     }
950 
951   /* Look for DEBUGLINK_NAME in the same directory as FILENAME.  */
952 
953   slash = strrchr (filename, '/');
954   if (slash == NULL)
955     {
956       prefix = "";
957       prefix_len = 0;
958     }
959   else
960     {
961       slash++;
962       prefix = filename;
963       prefix_len = slash - filename;
964     }
965 
966   ddescriptor = elf_try_debugfile (state, prefix, prefix_len, "", 0,
967 				   debuglink_name, error_callback, data);
968   if (ddescriptor >= 0)
969     {
970       ret = ddescriptor;
971       goto done;
972     }
973 
974   /* Look for DEBUGLINK_NAME in a .debug subdirectory of FILENAME.  */
975 
976   ddescriptor = elf_try_debugfile (state, prefix, prefix_len, ".debug/",
977 				   strlen (".debug/"), debuglink_name,
978 				   error_callback, data);
979   if (ddescriptor >= 0)
980     {
981       ret = ddescriptor;
982       goto done;
983     }
984 
985   /* Look for DEBUGLINK_NAME in /usr/lib/debug.  */
986 
987   ddescriptor = elf_try_debugfile (state, "/usr/lib/debug/",
988 				   strlen ("/usr/lib/debug/"), prefix,
989 				   prefix_len, debuglink_name,
990 				   error_callback, data);
991   if (ddescriptor >= 0)
992     ret = ddescriptor;
993 
994  done:
995   if (alc != NULL && alc_len > 0)
996     backtrace_free (state, alc, alc_len, error_callback, data);
997   return ret;
998 }
999 
1000 /* Open a separate debug info file, using the debuglink section data
1001    to find it.  Returns an open file descriptor, or -1.  */
1002 
1003 static int
1004 elf_open_debugfile_by_debuglink (struct backtrace_state *state,
1005 				 const char *filename,
1006 				 const char *debuglink_name,
1007 				 uint32_t debuglink_crc,
1008 				 backtrace_error_callback error_callback,
1009 				 void *data)
1010 {
1011   int ddescriptor;
1012 
1013   ddescriptor = elf_find_debugfile_by_debuglink (state, filename,
1014 						 debuglink_name,
1015 						 error_callback, data);
1016   if (ddescriptor < 0)
1017     return -1;
1018 
1019   if (debuglink_crc != 0)
1020     {
1021       uint32_t got_crc;
1022 
1023       got_crc = elf_crc32_file (state, ddescriptor, error_callback, data);
1024       if (got_crc != debuglink_crc)
1025 	{
1026 	  backtrace_close (ddescriptor, error_callback, data);
1027 	  return -1;
1028 	}
1029     }
1030 
1031   return ddescriptor;
1032 }
1033 
1034 /* A function useful for setting a breakpoint for an inflation failure
1035    when this code is compiled with -g.  */
1036 
1037 static void
1038 elf_zlib_failed(void)
1039 {
1040 }
1041 
1042 /* *PVAL is the current value being read from the stream, and *PBITS
1043    is the number of valid bits.  Ensure that *PVAL holds at least 15
1044    bits by reading additional bits from *PPIN, up to PINEND, as
1045    needed.  Updates *PPIN, *PVAL and *PBITS.  Returns 1 on success, 0
1046    on error.  */
1047 
1048 static int
1049 elf_zlib_fetch (const unsigned char **ppin, const unsigned char *pinend,
1050 		uint64_t *pval, unsigned int *pbits)
1051 {
1052   unsigned int bits;
1053   const unsigned char *pin;
1054   uint64_t val;
1055   uint32_t next;
1056 
1057   bits = *pbits;
1058   if (bits >= 15)
1059     return 1;
1060   pin = *ppin;
1061   val = *pval;
1062 
1063   if (unlikely (pinend - pin < 4))
1064     {
1065       elf_zlib_failed ();
1066       return 0;
1067     }
1068 
1069 #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) \
1070     && defined(__ORDER_BIG_ENDIAN__) \
1071     && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ \
1072         || __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1073   /* We've ensured that PIN is aligned.  */
1074   next = *(const uint32_t *)pin;
1075 
1076 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
1077   next = __builtin_bswap32 (next);
1078 #endif
1079 #else
1080   next = pin[0] | (pin[1] << 8) | (pin[2] << 16) | (pin[3] << 24);
1081 #endif
1082 
1083   val |= (uint64_t)next << bits;
1084   bits += 32;
1085   pin += 4;
1086 
1087   /* We will need the next four bytes soon.  */
1088   __builtin_prefetch (pin, 0, 0);
1089 
1090   *ppin = pin;
1091   *pval = val;
1092   *pbits = bits;
1093   return 1;
1094 }
1095 
1096 /* Huffman code tables, like the rest of the zlib format, are defined
1097    by RFC 1951.  We store a Huffman code table as a series of tables
1098    stored sequentially in memory.  Each entry in a table is 16 bits.
1099    The first, main, table has 256 entries.  It is followed by a set of
1100    secondary tables of length 2 to 128 entries.  The maximum length of
1101    a code sequence in the deflate format is 15 bits, so that is all we
1102    need.  Each secondary table has an index, which is the offset of
1103    the table in the overall memory storage.
1104 
1105    The deflate format says that all codes of a given bit length are
1106    lexicographically consecutive.  Perhaps we could have 130 values
1107    that require a 15-bit code, perhaps requiring three secondary
1108    tables of size 128.  I don't know if this is actually possible, but
1109    it suggests that the maximum size required for secondary tables is
1110    3 * 128 + 3 * 64 ... == 768.  The zlib enough program reports 660
1111    as the maximum.  We permit 768, since in addition to the 256 for
1112    the primary table, with two bytes per entry, and with the two
1113    tables we need, that gives us a page.
1114 
1115    A single table entry needs to store a value or (for the main table
1116    only) the index and size of a secondary table.  Values range from 0
1117    to 285, inclusive.  Secondary table indexes, per above, range from
1118    0 to 510.  For a value we need to store the number of bits we need
1119    to determine that value (one value may appear multiple times in the
1120    table), which is 1 to 8.  For a secondary table we need to store
1121    the number of bits used to index into the table, which is 1 to 7.
1122    And of course we need 1 bit to decide whether we have a value or a
1123    secondary table index.  So each entry needs 9 bits for value/table
1124    index, 3 bits for size, 1 bit what it is.  For simplicity we use 16
1125    bits per entry.  */
1126 
1127 /* Number of entries we allocate to for one code table.  We get a page
1128    for the two code tables we need.  */
1129 
1130 #define HUFFMAN_TABLE_SIZE (1024)
1131 
1132 /* Bit masks and shifts for the values in the table.  */
1133 
1134 #define HUFFMAN_VALUE_MASK 0x01ff
1135 #define HUFFMAN_BITS_SHIFT 9
1136 #define HUFFMAN_BITS_MASK 0x7
1137 #define HUFFMAN_SECONDARY_SHIFT 12
1138 
1139 /* For working memory while inflating we need two code tables, we need
1140    an array of code lengths (max value 15, so we use unsigned char),
1141    and an array of unsigned shorts used while building a table.  The
1142    latter two arrays must be large enough to hold the maximum number
1143    of code lengths, which RFC 1951 defines as 286 + 30.  */
1144 
1145 #define ZDEBUG_TABLE_SIZE \
1146   (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1147    + (286 + 30) * sizeof (uint16_t)	      \
1148    + (286 + 30) * sizeof (unsigned char))
1149 
1150 #define ZDEBUG_TABLE_CODELEN_OFFSET \
1151   (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1152    + (286 + 30) * sizeof (uint16_t))
1153 
1154 #define ZDEBUG_TABLE_WORK_OFFSET \
1155   (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t))
1156 
1157 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1158 
1159 /* Used by the main function that generates the fixed table to learn
1160    the table size.  */
1161 static size_t final_next_secondary;
1162 
1163 #endif
1164 
1165 /* Build a Huffman code table from an array of lengths in CODES of
1166    length CODES_LEN.  The table is stored into *TABLE.  ZDEBUG_TABLE
1167    is the same as for elf_zlib_inflate, used to find some work space.
1168    Returns 1 on success, 0 on error.  */
1169 
1170 static int
1171 elf_zlib_inflate_table (unsigned char *codes, size_t codes_len,
1172 			uint16_t *zdebug_table, uint16_t *table)
1173 {
1174   uint16_t count[16];
1175   uint16_t start[16];
1176   uint16_t prev[16];
1177   uint16_t firstcode[7];
1178   uint16_t *next;
1179   size_t i;
1180   size_t j;
1181   unsigned int code;
1182   size_t next_secondary;
1183 
1184   /* Count the number of code of each length.  Set NEXT[val] to be the
1185      next value after VAL with the same bit length.  */
1186 
1187   next = (uint16_t *) (((unsigned char *) zdebug_table)
1188 		       + ZDEBUG_TABLE_WORK_OFFSET);
1189 
1190   memset (&count[0], 0, 16 * sizeof (uint16_t));
1191   for (i = 0; i < codes_len; ++i)
1192     {
1193       if (unlikely (codes[i] >= 16))
1194 	{
1195 	  elf_zlib_failed ();
1196 	  return 0;
1197 	}
1198 
1199       if (count[codes[i]] == 0)
1200 	{
1201 	  start[codes[i]] = i;
1202 	  prev[codes[i]] = i;
1203 	}
1204       else
1205 	{
1206 	  next[prev[codes[i]]] = i;
1207 	  prev[codes[i]] = i;
1208 	}
1209 
1210       ++count[codes[i]];
1211     }
1212 
1213   /* For each length, fill in the table for the codes of that
1214      length.  */
1215 
1216   memset (table, 0, HUFFMAN_TABLE_SIZE * sizeof (uint16_t));
1217 
1218   /* Handle the values that do not require a secondary table.  */
1219 
1220   code = 0;
1221   for (j = 1; j <= 8; ++j)
1222     {
1223       unsigned int jcnt;
1224       unsigned int val;
1225 
1226       jcnt = count[j];
1227       if (jcnt == 0)
1228 	continue;
1229 
1230       if (unlikely (jcnt > (1U << j)))
1231 	{
1232 	  elf_zlib_failed ();
1233 	  return 0;
1234 	}
1235 
1236       /* There are JCNT values that have this length, the values
1237 	 starting from START[j] continuing through NEXT[VAL].  Those
1238 	 values are assigned consecutive values starting at CODE.  */
1239 
1240       val = start[j];
1241       for (i = 0; i < jcnt; ++i)
1242 	{
1243 	  uint16_t tval;
1244 	  size_t ind;
1245 	  unsigned int incr;
1246 
1247 	  /* In the compressed bit stream, the value VAL is encoded as
1248 	     J bits with the value C.  */
1249 
1250 	  if (unlikely ((val & ~HUFFMAN_VALUE_MASK) != 0))
1251 	    {
1252 	      elf_zlib_failed ();
1253 	      return 0;
1254 	    }
1255 
1256 	  tval = val | ((j - 1) << HUFFMAN_BITS_SHIFT);
1257 
1258 	  /* The table lookup uses 8 bits.  If J is less than 8, we
1259 	     don't know what the other bits will be.  We need to fill
1260 	     in all possibilities in the table.  Since the Huffman
1261 	     code is unambiguous, those entries can't be used for any
1262 	     other code.  */
1263 
1264 	  for (ind = code; ind < 0x100; ind += 1 << j)
1265 	    {
1266 	      if (unlikely (table[ind] != 0))
1267 		{
1268 		  elf_zlib_failed ();
1269 		  return 0;
1270 		}
1271 	      table[ind] = tval;
1272 	    }
1273 
1274 	  /* Advance to the next value with this length.  */
1275 	  if (i + 1 < jcnt)
1276 	    val = next[val];
1277 
1278 	  /* The Huffman codes are stored in the bitstream with the
1279 	     most significant bit first, as is required to make them
1280 	     unambiguous.  The effect is that when we read them from
1281 	     the bitstream we see the bit sequence in reverse order:
1282 	     the most significant bit of the Huffman code is the least
1283 	     significant bit of the value we read from the bitstream.
1284 	     That means that to make our table lookups work, we need
1285 	     to reverse the bits of CODE.  Since reversing bits is
1286 	     tedious and in general requires using a table, we instead
1287 	     increment CODE in reverse order.  That is, if the number
1288 	     of bits we are currently using, here named J, is 3, we
1289 	     count as 000, 100, 010, 110, 001, 101, 011, 111, which is
1290 	     to say the numbers from 0 to 7 but with the bits
1291 	     reversed.  Going to more bits, aka incrementing J,
1292 	     effectively just adds more zero bits as the beginning,
1293 	     and as such does not change the numeric value of CODE.
1294 
1295 	     To increment CODE of length J in reverse order, find the
1296 	     most significant zero bit and set it to one while
1297 	     clearing all higher bits.  In other words, add 1 modulo
1298 	     2^J, only reversed.  */
1299 
1300 	  incr = 1U << (j - 1);
1301 	  while ((code & incr) != 0)
1302 	    incr >>= 1;
1303 	  if (incr == 0)
1304 	    code = 0;
1305 	  else
1306 	    {
1307 	      code &= incr - 1;
1308 	      code += incr;
1309 	    }
1310 	}
1311     }
1312 
1313   /* Handle the values that require a secondary table.  */
1314 
1315   /* Set FIRSTCODE, the number at which the codes start, for each
1316      length.  */
1317 
1318   for (j = 9; j < 16; j++)
1319     {
1320       unsigned int jcnt;
1321       unsigned int k;
1322 
1323       jcnt = count[j];
1324       if (jcnt == 0)
1325 	continue;
1326 
1327       /* There are JCNT values that have this length, the values
1328 	 starting from START[j].  Those values are assigned
1329 	 consecutive values starting at CODE.  */
1330 
1331       firstcode[j - 9] = code;
1332 
1333       /* Reverse add JCNT to CODE modulo 2^J.  */
1334       for (k = 0; k < j; ++k)
1335 	{
1336 	  if ((jcnt & (1U << k)) != 0)
1337 	    {
1338 	      unsigned int m;
1339 	      unsigned int bit;
1340 
1341 	      bit = 1U << (j - k - 1);
1342 	      for (m = 0; m < j - k; ++m, bit >>= 1)
1343 		{
1344 		  if ((code & bit) == 0)
1345 		    {
1346 		      code += bit;
1347 		      break;
1348 		    }
1349 		  code &= ~bit;
1350 		}
1351 	      jcnt &= ~(1U << k);
1352 	    }
1353 	}
1354       if (unlikely (jcnt != 0))
1355 	{
1356 	  elf_zlib_failed ();
1357 	  return 0;
1358 	}
1359     }
1360 
1361   /* For J from 9 to 15, inclusive, we store COUNT[J] consecutive
1362      values starting at START[J] with consecutive codes starting at
1363      FIRSTCODE[J - 9].  In the primary table we need to point to the
1364      secondary table, and the secondary table will be indexed by J - 9
1365      bits.  We count down from 15 so that we install the larger
1366      secondary tables first, as the smaller ones may be embedded in
1367      the larger ones.  */
1368 
1369   next_secondary = 0; /* Index of next secondary table (after primary).  */
1370   for (j = 15; j >= 9; j--)
1371     {
1372       unsigned int jcnt;
1373       unsigned int val;
1374       size_t primary; /* Current primary index.  */
1375       size_t secondary; /* Offset to current secondary table.  */
1376       size_t secondary_bits; /* Bit size of current secondary table.  */
1377 
1378       jcnt = count[j];
1379       if (jcnt == 0)
1380 	continue;
1381 
1382       val = start[j];
1383       code = firstcode[j - 9];
1384       primary = 0x100;
1385       secondary = 0;
1386       secondary_bits = 0;
1387       for (i = 0; i < jcnt; ++i)
1388 	{
1389 	  uint16_t tval;
1390 	  size_t ind;
1391 	  unsigned int incr;
1392 
1393 	  if ((code & 0xff) != primary)
1394 	    {
1395 	      uint16_t tprimary;
1396 
1397 	      /* Fill in a new primary table entry.  */
1398 
1399 	      primary = code & 0xff;
1400 
1401 	      tprimary = table[primary];
1402 	      if (tprimary == 0)
1403 		{
1404 		  /* Start a new secondary table.  */
1405 
1406 		  if (unlikely ((next_secondary & HUFFMAN_VALUE_MASK)
1407 				!= next_secondary))
1408 		    {
1409 		      elf_zlib_failed ();
1410 		      return 0;
1411 		    }
1412 
1413 		  secondary = next_secondary;
1414 		  secondary_bits = j - 8;
1415 		  next_secondary += 1 << secondary_bits;
1416 		  table[primary] = (secondary
1417 				    + ((j - 8) << HUFFMAN_BITS_SHIFT)
1418 				    + (1U << HUFFMAN_SECONDARY_SHIFT));
1419 		}
1420 	      else
1421 		{
1422 		  /* There is an existing entry.  It had better be a
1423 		     secondary table with enough bits.  */
1424 		  if (unlikely ((tprimary & (1U << HUFFMAN_SECONDARY_SHIFT))
1425 				== 0))
1426 		    {
1427 		      elf_zlib_failed ();
1428 		      return 0;
1429 		    }
1430 		  secondary = tprimary & HUFFMAN_VALUE_MASK;
1431 		  secondary_bits = ((tprimary >> HUFFMAN_BITS_SHIFT)
1432 				    & HUFFMAN_BITS_MASK);
1433 		  if (unlikely (secondary_bits < j - 8))
1434 		    {
1435 		      elf_zlib_failed ();
1436 		      return 0;
1437 		    }
1438 		}
1439 	    }
1440 
1441 	  /* Fill in secondary table entries.  */
1442 
1443 	  tval = val | ((j - 8) << HUFFMAN_BITS_SHIFT);
1444 
1445 	  for (ind = code >> 8;
1446 	       ind < (1U << secondary_bits);
1447 	       ind += 1U << (j - 8))
1448 	    {
1449 	      if (unlikely (table[secondary + 0x100 + ind] != 0))
1450 		{
1451 		  elf_zlib_failed ();
1452 		  return 0;
1453 		}
1454 	      table[secondary + 0x100 + ind] = tval;
1455 	    }
1456 
1457 	  if (i + 1 < jcnt)
1458 	    val = next[val];
1459 
1460 	  incr = 1U << (j - 1);
1461 	  while ((code & incr) != 0)
1462 	    incr >>= 1;
1463 	  if (incr == 0)
1464 	    code = 0;
1465 	  else
1466 	    {
1467 	      code &= incr - 1;
1468 	      code += incr;
1469 	    }
1470 	}
1471     }
1472 
1473 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1474   final_next_secondary = next_secondary;
1475 #endif
1476 
1477   return 1;
1478 }
1479 
1480 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1481 
1482 /* Used to generate the fixed Huffman table for block type 1.  */
1483 
1484 #include <stdio.h>
1485 
1486 static uint16_t table[ZDEBUG_TABLE_SIZE];
1487 static unsigned char codes[288];
1488 
1489 int
1490 main ()
1491 {
1492   size_t i;
1493 
1494   for (i = 0; i <= 143; ++i)
1495     codes[i] = 8;
1496   for (i = 144; i <= 255; ++i)
1497     codes[i] = 9;
1498   for (i = 256; i <= 279; ++i)
1499     codes[i] = 7;
1500   for (i = 280; i <= 287; ++i)
1501     codes[i] = 8;
1502   if (!elf_zlib_inflate_table (&codes[0], 288, &table[0], &table[0]))
1503     {
1504       fprintf (stderr, "elf_zlib_inflate_table failed\n");
1505       exit (EXIT_FAILURE);
1506     }
1507 
1508   printf ("static const uint16_t elf_zlib_default_table[%#zx] =\n",
1509 	  final_next_secondary + 0x100);
1510   printf ("{\n");
1511   for (i = 0; i < final_next_secondary + 0x100; i += 8)
1512     {
1513       size_t j;
1514 
1515       printf (" ");
1516       for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1517 	printf (" %#x,", table[j]);
1518       printf ("\n");
1519     }
1520   printf ("};\n");
1521   printf ("\n");
1522 
1523   for (i = 0; i < 32; ++i)
1524     codes[i] = 5;
1525   if (!elf_zlib_inflate_table (&codes[0], 32, &table[0], &table[0]))
1526     {
1527       fprintf (stderr, "elf_zlib_inflate_table failed\n");
1528       exit (EXIT_FAILURE);
1529     }
1530 
1531   printf ("static const uint16_t elf_zlib_default_dist_table[%#zx] =\n",
1532 	  final_next_secondary + 0x100);
1533   printf ("{\n");
1534   for (i = 0; i < final_next_secondary + 0x100; i += 8)
1535     {
1536       size_t j;
1537 
1538       printf (" ");
1539       for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1540 	printf (" %#x,", table[j]);
1541       printf ("\n");
1542     }
1543   printf ("};\n");
1544 
1545   return 0;
1546 }
1547 
1548 #endif
1549 
1550 /* The fixed tables generated by the #ifdef'ed out main function
1551    above.  */
1552 
1553 static const uint16_t elf_zlib_default_table[0x170] =
1554 {
1555   0xd00, 0xe50, 0xe10, 0xf18, 0xd10, 0xe70, 0xe30, 0x1230,
1556   0xd08, 0xe60, 0xe20, 0x1210, 0xe00, 0xe80, 0xe40, 0x1250,
1557   0xd04, 0xe58, 0xe18, 0x1200, 0xd14, 0xe78, 0xe38, 0x1240,
1558   0xd0c, 0xe68, 0xe28, 0x1220, 0xe08, 0xe88, 0xe48, 0x1260,
1559   0xd02, 0xe54, 0xe14, 0xf1c, 0xd12, 0xe74, 0xe34, 0x1238,
1560   0xd0a, 0xe64, 0xe24, 0x1218, 0xe04, 0xe84, 0xe44, 0x1258,
1561   0xd06, 0xe5c, 0xe1c, 0x1208, 0xd16, 0xe7c, 0xe3c, 0x1248,
1562   0xd0e, 0xe6c, 0xe2c, 0x1228, 0xe0c, 0xe8c, 0xe4c, 0x1268,
1563   0xd01, 0xe52, 0xe12, 0xf1a, 0xd11, 0xe72, 0xe32, 0x1234,
1564   0xd09, 0xe62, 0xe22, 0x1214, 0xe02, 0xe82, 0xe42, 0x1254,
1565   0xd05, 0xe5a, 0xe1a, 0x1204, 0xd15, 0xe7a, 0xe3a, 0x1244,
1566   0xd0d, 0xe6a, 0xe2a, 0x1224, 0xe0a, 0xe8a, 0xe4a, 0x1264,
1567   0xd03, 0xe56, 0xe16, 0xf1e, 0xd13, 0xe76, 0xe36, 0x123c,
1568   0xd0b, 0xe66, 0xe26, 0x121c, 0xe06, 0xe86, 0xe46, 0x125c,
1569   0xd07, 0xe5e, 0xe1e, 0x120c, 0xd17, 0xe7e, 0xe3e, 0x124c,
1570   0xd0f, 0xe6e, 0xe2e, 0x122c, 0xe0e, 0xe8e, 0xe4e, 0x126c,
1571   0xd00, 0xe51, 0xe11, 0xf19, 0xd10, 0xe71, 0xe31, 0x1232,
1572   0xd08, 0xe61, 0xe21, 0x1212, 0xe01, 0xe81, 0xe41, 0x1252,
1573   0xd04, 0xe59, 0xe19, 0x1202, 0xd14, 0xe79, 0xe39, 0x1242,
1574   0xd0c, 0xe69, 0xe29, 0x1222, 0xe09, 0xe89, 0xe49, 0x1262,
1575   0xd02, 0xe55, 0xe15, 0xf1d, 0xd12, 0xe75, 0xe35, 0x123a,
1576   0xd0a, 0xe65, 0xe25, 0x121a, 0xe05, 0xe85, 0xe45, 0x125a,
1577   0xd06, 0xe5d, 0xe1d, 0x120a, 0xd16, 0xe7d, 0xe3d, 0x124a,
1578   0xd0e, 0xe6d, 0xe2d, 0x122a, 0xe0d, 0xe8d, 0xe4d, 0x126a,
1579   0xd01, 0xe53, 0xe13, 0xf1b, 0xd11, 0xe73, 0xe33, 0x1236,
1580   0xd09, 0xe63, 0xe23, 0x1216, 0xe03, 0xe83, 0xe43, 0x1256,
1581   0xd05, 0xe5b, 0xe1b, 0x1206, 0xd15, 0xe7b, 0xe3b, 0x1246,
1582   0xd0d, 0xe6b, 0xe2b, 0x1226, 0xe0b, 0xe8b, 0xe4b, 0x1266,
1583   0xd03, 0xe57, 0xe17, 0xf1f, 0xd13, 0xe77, 0xe37, 0x123e,
1584   0xd0b, 0xe67, 0xe27, 0x121e, 0xe07, 0xe87, 0xe47, 0x125e,
1585   0xd07, 0xe5f, 0xe1f, 0x120e, 0xd17, 0xe7f, 0xe3f, 0x124e,
1586   0xd0f, 0xe6f, 0xe2f, 0x122e, 0xe0f, 0xe8f, 0xe4f, 0x126e,
1587   0x290, 0x291, 0x292, 0x293, 0x294, 0x295, 0x296, 0x297,
1588   0x298, 0x299, 0x29a, 0x29b, 0x29c, 0x29d, 0x29e, 0x29f,
1589   0x2a0, 0x2a1, 0x2a2, 0x2a3, 0x2a4, 0x2a5, 0x2a6, 0x2a7,
1590   0x2a8, 0x2a9, 0x2aa, 0x2ab, 0x2ac, 0x2ad, 0x2ae, 0x2af,
1591   0x2b0, 0x2b1, 0x2b2, 0x2b3, 0x2b4, 0x2b5, 0x2b6, 0x2b7,
1592   0x2b8, 0x2b9, 0x2ba, 0x2bb, 0x2bc, 0x2bd, 0x2be, 0x2bf,
1593   0x2c0, 0x2c1, 0x2c2, 0x2c3, 0x2c4, 0x2c5, 0x2c6, 0x2c7,
1594   0x2c8, 0x2c9, 0x2ca, 0x2cb, 0x2cc, 0x2cd, 0x2ce, 0x2cf,
1595   0x2d0, 0x2d1, 0x2d2, 0x2d3, 0x2d4, 0x2d5, 0x2d6, 0x2d7,
1596   0x2d8, 0x2d9, 0x2da, 0x2db, 0x2dc, 0x2dd, 0x2de, 0x2df,
1597   0x2e0, 0x2e1, 0x2e2, 0x2e3, 0x2e4, 0x2e5, 0x2e6, 0x2e7,
1598   0x2e8, 0x2e9, 0x2ea, 0x2eb, 0x2ec, 0x2ed, 0x2ee, 0x2ef,
1599   0x2f0, 0x2f1, 0x2f2, 0x2f3, 0x2f4, 0x2f5, 0x2f6, 0x2f7,
1600   0x2f8, 0x2f9, 0x2fa, 0x2fb, 0x2fc, 0x2fd, 0x2fe, 0x2ff,
1601 };
1602 
1603 static const uint16_t elf_zlib_default_dist_table[0x100] =
1604 {
1605   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1606   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1607   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1608   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1609   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1610   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1611   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1612   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1613   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1614   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1615   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1616   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1617   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1618   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1619   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1620   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1621   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1622   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1623   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1624   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1625   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1626   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1627   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1628   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1629   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1630   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1631   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1632   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1633   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1634   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1635   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1636   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1637 };
1638 
1639 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT.  Return 1 on
1640    success, 0 on some error parsing the stream.  */
1641 
1642 static int
1643 elf_zlib_inflate (const unsigned char *pin, size_t sin, uint16_t *zdebug_table,
1644 		  unsigned char *pout, size_t sout)
1645 {
1646   unsigned char *porigout;
1647   const unsigned char *pinend;
1648   unsigned char *poutend;
1649 
1650   /* We can apparently see multiple zlib streams concatenated
1651      together, so keep going as long as there is something to read.
1652      The last 4 bytes are the checksum.  */
1653   porigout = pout;
1654   pinend = pin + sin;
1655   poutend = pout + sout;
1656   while ((pinend - pin) > 4)
1657     {
1658       uint64_t val;
1659       unsigned int bits;
1660       int last;
1661 
1662       /* Read the two byte zlib header.  */
1663 
1664       if (unlikely ((pin[0] & 0xf) != 8)) /* 8 is zlib encoding.  */
1665 	{
1666 	  /* Unknown compression method.  */
1667 	  elf_zlib_failed ();
1668 	  return 0;
1669 	}
1670       if (unlikely ((pin[0] >> 4) > 7))
1671 	{
1672 	  /* Window size too large.  Other than this check, we don't
1673 	     care about the window size.  */
1674 	  elf_zlib_failed ();
1675 	  return 0;
1676 	}
1677       if (unlikely ((pin[1] & 0x20) != 0))
1678 	{
1679 	  /* Stream expects a predefined dictionary, but we have no
1680 	     dictionary.  */
1681 	  elf_zlib_failed ();
1682 	  return 0;
1683 	}
1684       val = (pin[0] << 8) | pin[1];
1685       if (unlikely (val % 31 != 0))
1686 	{
1687 	  /* Header check failure.  */
1688 	  elf_zlib_failed ();
1689 	  return 0;
1690 	}
1691       pin += 2;
1692 
1693       /* Align PIN to a 32-bit boundary.  */
1694 
1695       val = 0;
1696       bits = 0;
1697       while ((((uintptr_t) pin) & 3) != 0)
1698 	{
1699 	  val |= (uint64_t)*pin << bits;
1700 	  bits += 8;
1701 	  ++pin;
1702 	}
1703 
1704       /* Read blocks until one is marked last.  */
1705 
1706       last = 0;
1707 
1708       while (!last)
1709 	{
1710 	  unsigned int type;
1711 	  const uint16_t *tlit;
1712 	  const uint16_t *tdist;
1713 
1714 	  if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1715 	    return 0;
1716 
1717 	  last = val & 1;
1718 	  type = (val >> 1) & 3;
1719 	  val >>= 3;
1720 	  bits -= 3;
1721 
1722 	  if (unlikely (type == 3))
1723 	    {
1724 	      /* Invalid block type.  */
1725 	      elf_zlib_failed ();
1726 	      return 0;
1727 	    }
1728 
1729 	  if (type == 0)
1730 	    {
1731 	      uint16_t len;
1732 	      uint16_t lenc;
1733 
1734 	      /* An uncompressed block.  */
1735 
1736 	      /* If we've read ahead more than a byte, back up.  */
1737 	      while (bits > 8)
1738 		{
1739 		  --pin;
1740 		  bits -= 8;
1741 		}
1742 
1743 	      val = 0;
1744 	      bits = 0;
1745 	      if (unlikely ((pinend - pin) < 4))
1746 		{
1747 		  /* Missing length.  */
1748 		  elf_zlib_failed ();
1749 		  return 0;
1750 		}
1751 	      len = pin[0] | (pin[1] << 8);
1752 	      lenc = pin[2] | (pin[3] << 8);
1753 	      pin += 4;
1754 	      lenc = ~lenc;
1755 	      if (unlikely (len != lenc))
1756 		{
1757 		  /* Corrupt data.  */
1758 		  elf_zlib_failed ();
1759 		  return 0;
1760 		}
1761 	      if (unlikely (len > (unsigned int) (pinend - pin)
1762 			    || len > (unsigned int) (poutend - pout)))
1763 		{
1764 		  /* Not enough space in buffers.  */
1765 		  elf_zlib_failed ();
1766 		  return 0;
1767 		}
1768 	      memcpy (pout, pin, len);
1769 	      pout += len;
1770 	      pin += len;
1771 
1772 	      /* Align PIN.  */
1773 	      while ((((uintptr_t) pin) & 3) != 0)
1774 		{
1775 		  val |= (uint64_t)*pin << bits;
1776 		  bits += 8;
1777 		  ++pin;
1778 		}
1779 
1780 	      /* Go around to read the next block.  */
1781 	      continue;
1782 	    }
1783 
1784 	  if (type == 1)
1785 	    {
1786 	      tlit = elf_zlib_default_table;
1787 	      tdist = elf_zlib_default_dist_table;
1788 	    }
1789 	  else
1790 	    {
1791 	      unsigned int nlit;
1792 	      unsigned int ndist;
1793 	      unsigned int nclen;
1794 	      unsigned char codebits[19];
1795 	      unsigned char *plenbase;
1796 	      unsigned char *plen;
1797 	      unsigned char *plenend;
1798 
1799 	      /* Read a Huffman encoding table.  The various magic
1800 		 numbers here are from RFC 1951.  */
1801 
1802 	      if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1803 		return 0;
1804 
1805 	      nlit = (val & 0x1f) + 257;
1806 	      val >>= 5;
1807 	      ndist = (val & 0x1f) + 1;
1808 	      val >>= 5;
1809 	      nclen = (val & 0xf) + 4;
1810 	      val >>= 4;
1811 	      bits -= 14;
1812 	      if (unlikely (nlit > 286 || ndist > 30))
1813 		{
1814 		  /* Values out of range.  */
1815 		  elf_zlib_failed ();
1816 		  return 0;
1817 		}
1818 
1819 	      /* Read and build the table used to compress the
1820 		 literal, length, and distance codes.  */
1821 
1822 	      memset(&codebits[0], 0, 19);
1823 
1824 	      /* There are always at least 4 elements in the
1825 		 table.  */
1826 
1827 	      if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1828 		return 0;
1829 
1830 	      codebits[16] = val & 7;
1831 	      codebits[17] = (val >> 3) & 7;
1832 	      codebits[18] = (val >> 6) & 7;
1833 	      codebits[0] = (val >> 9) & 7;
1834 	      val >>= 12;
1835 	      bits -= 12;
1836 
1837 	      if (nclen == 4)
1838 		goto codebitsdone;
1839 
1840 	      codebits[8] = val & 7;
1841 	      val >>= 3;
1842 	      bits -= 3;
1843 
1844 	      if (nclen == 5)
1845 		goto codebitsdone;
1846 
1847 	      if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1848 		return 0;
1849 
1850 	      codebits[7] = val & 7;
1851 	      val >>= 3;
1852 	      bits -= 3;
1853 
1854 	      if (nclen == 6)
1855 		goto codebitsdone;
1856 
1857 	      codebits[9] = val & 7;
1858 	      val >>= 3;
1859 	      bits -= 3;
1860 
1861 	      if (nclen == 7)
1862 		goto codebitsdone;
1863 
1864 	      codebits[6] = val & 7;
1865 	      val >>= 3;
1866 	      bits -= 3;
1867 
1868 	      if (nclen == 8)
1869 		goto codebitsdone;
1870 
1871 	      codebits[10] = val & 7;
1872 	      val >>= 3;
1873 	      bits -= 3;
1874 
1875 	      if (nclen == 9)
1876 		goto codebitsdone;
1877 
1878 	      codebits[5] = val & 7;
1879 	      val >>= 3;
1880 	      bits -= 3;
1881 
1882 	      if (nclen == 10)
1883 		goto codebitsdone;
1884 
1885 	      if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1886 		return 0;
1887 
1888 	      codebits[11] = val & 7;
1889 	      val >>= 3;
1890 	      bits -= 3;
1891 
1892 	      if (nclen == 11)
1893 		goto codebitsdone;
1894 
1895 	      codebits[4] = val & 7;
1896 	      val >>= 3;
1897 	      bits -= 3;
1898 
1899 	      if (nclen == 12)
1900 		goto codebitsdone;
1901 
1902 	      codebits[12] = val & 7;
1903 	      val >>= 3;
1904 	      bits -= 3;
1905 
1906 	      if (nclen == 13)
1907 		goto codebitsdone;
1908 
1909 	      codebits[3] = val & 7;
1910 	      val >>= 3;
1911 	      bits -= 3;
1912 
1913 	      if (nclen == 14)
1914 		goto codebitsdone;
1915 
1916 	      codebits[13] = val & 7;
1917 	      val >>= 3;
1918 	      bits -= 3;
1919 
1920 	      if (nclen == 15)
1921 		goto codebitsdone;
1922 
1923 	      if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1924 		return 0;
1925 
1926 	      codebits[2] = val & 7;
1927 	      val >>= 3;
1928 	      bits -= 3;
1929 
1930 	      if (nclen == 16)
1931 		goto codebitsdone;
1932 
1933 	      codebits[14] = val & 7;
1934 	      val >>= 3;
1935 	      bits -= 3;
1936 
1937 	      if (nclen == 17)
1938 		goto codebitsdone;
1939 
1940 	      codebits[1] = val & 7;
1941 	      val >>= 3;
1942 	      bits -= 3;
1943 
1944 	      if (nclen == 18)
1945 		goto codebitsdone;
1946 
1947 	      codebits[15] = val & 7;
1948 	      val >>= 3;
1949 	      bits -= 3;
1950 
1951 	    codebitsdone:
1952 
1953 	      if (!elf_zlib_inflate_table (codebits, 19, zdebug_table,
1954 					   zdebug_table))
1955 		return 0;
1956 
1957 	      /* Read the compressed bit lengths of the literal,
1958 		 length, and distance codes.  We have allocated space
1959 		 at the end of zdebug_table to hold them.  */
1960 
1961 	      plenbase = (((unsigned char *) zdebug_table)
1962 			  + ZDEBUG_TABLE_CODELEN_OFFSET);
1963 	      plen = plenbase;
1964 	      plenend = plen + nlit + ndist;
1965 	      while (plen < plenend)
1966 		{
1967 		  uint16_t t;
1968 		  unsigned int b;
1969 		  uint16_t v;
1970 
1971 		  if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1972 		    return 0;
1973 
1974 		  t = zdebug_table[val & 0xff];
1975 
1976 		  /* The compression here uses bit lengths up to 7, so
1977 		     a secondary table is never necessary.  */
1978 		  if (unlikely ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) != 0))
1979 		    {
1980 		      elf_zlib_failed ();
1981 		      return 0;
1982 		    }
1983 
1984 		  b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
1985 		  val >>= b + 1;
1986 		  bits -= b + 1;
1987 
1988 		  v = t & HUFFMAN_VALUE_MASK;
1989 		  if (v < 16)
1990 		    *plen++ = v;
1991 		  else if (v == 16)
1992 		    {
1993 		      unsigned int c;
1994 		      unsigned int prev;
1995 
1996 		      /* Copy previous entry 3 to 6 times.  */
1997 
1998 		      if (unlikely (plen == plenbase))
1999 			{
2000 			  elf_zlib_failed ();
2001 			  return 0;
2002 			}
2003 
2004 		      /* We used up to 7 bits since the last
2005 			 elf_zlib_fetch, so we have at least 8 bits
2006 			 available here.  */
2007 
2008 		      c = 3 + (val & 0x3);
2009 		      val >>= 2;
2010 		      bits -= 2;
2011 		      if (unlikely ((unsigned int) (plenend - plen) < c))
2012 			{
2013 			  elf_zlib_failed ();
2014 			  return 0;
2015 			}
2016 
2017 		      prev = plen[-1];
2018 		      switch (c)
2019 			{
2020 			case 6:
2021 			  *plen++ = prev;
2022 			  /* fallthrough */
2023 			case 5:
2024 			  *plen++ = prev;
2025 			  /* fallthrough */
2026 			case 4:
2027 			  *plen++ = prev;
2028 			}
2029 		      *plen++ = prev;
2030 		      *plen++ = prev;
2031 		      *plen++ = prev;
2032 		    }
2033 		  else if (v == 17)
2034 		    {
2035 		      unsigned int c;
2036 
2037 		      /* Store zero 3 to 10 times.  */
2038 
2039 		      /* We used up to 7 bits since the last
2040 			 elf_zlib_fetch, so we have at least 8 bits
2041 			 available here.  */
2042 
2043 		      c = 3 + (val & 0x7);
2044 		      val >>= 3;
2045 		      bits -= 3;
2046 		      if (unlikely ((unsigned int) (plenend - plen) < c))
2047 			{
2048 			  elf_zlib_failed ();
2049 			  return 0;
2050 			}
2051 
2052 		      switch (c)
2053 			{
2054 			case 10:
2055 			  *plen++ = 0;
2056 			  /* fallthrough */
2057 			case 9:
2058 			  *plen++ = 0;
2059 			  /* fallthrough */
2060 			case 8:
2061 			  *plen++ = 0;
2062 			  /* fallthrough */
2063 			case 7:
2064 			  *plen++ = 0;
2065 			  /* fallthrough */
2066 			case 6:
2067 			  *plen++ = 0;
2068 			  /* fallthrough */
2069 			case 5:
2070 			  *plen++ = 0;
2071 			  /* fallthrough */
2072 			case 4:
2073 			  *plen++ = 0;
2074 			}
2075 		      *plen++ = 0;
2076 		      *plen++ = 0;
2077 		      *plen++ = 0;
2078 		    }
2079 		  else if (v == 18)
2080 		    {
2081 		      unsigned int c;
2082 
2083 		      /* Store zero 11 to 138 times.  */
2084 
2085 		      /* We used up to 7 bits since the last
2086 			 elf_zlib_fetch, so we have at least 8 bits
2087 			 available here.  */
2088 
2089 		      c = 11 + (val & 0x7f);
2090 		      val >>= 7;
2091 		      bits -= 7;
2092 		      if (unlikely ((unsigned int) (plenend - plen) < c))
2093 			{
2094 			  elf_zlib_failed ();
2095 			  return 0;
2096 			}
2097 
2098 		      memset (plen, 0, c);
2099 		      plen += c;
2100 		    }
2101 		  else
2102 		    {
2103 		      elf_zlib_failed ();
2104 		      return 0;
2105 		    }
2106 		}
2107 
2108 	      /* Make sure that the stop code can appear.  */
2109 
2110 	      plen = plenbase;
2111 	      if (unlikely (plen[256] == 0))
2112 		{
2113 		  elf_zlib_failed ();
2114 		  return 0;
2115 		}
2116 
2117 	      /* Build the decompression tables.  */
2118 
2119 	      if (!elf_zlib_inflate_table (plen, nlit, zdebug_table,
2120 					   zdebug_table))
2121 		return 0;
2122 	      if (!elf_zlib_inflate_table (plen + nlit, ndist, zdebug_table,
2123 					   zdebug_table + HUFFMAN_TABLE_SIZE))
2124 		return 0;
2125 	      tlit = zdebug_table;
2126 	      tdist = zdebug_table + HUFFMAN_TABLE_SIZE;
2127 	    }
2128 
2129 	  /* Inflate values until the end of the block.  This is the
2130 	     main loop of the inflation code.  */
2131 
2132 	  while (1)
2133 	    {
2134 	      uint16_t t;
2135 	      unsigned int b;
2136 	      uint16_t v;
2137 	      unsigned int lit;
2138 
2139 	      if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2140 		return 0;
2141 
2142 	      t = tlit[val & 0xff];
2143 	      b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2144 	      v = t & HUFFMAN_VALUE_MASK;
2145 
2146 	      if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2147 		{
2148 		  lit = v;
2149 		  val >>= b + 1;
2150 		  bits -= b + 1;
2151 		}
2152 	      else
2153 		{
2154 		  t = tlit[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2155 		  b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2156 		  lit = t & HUFFMAN_VALUE_MASK;
2157 		  val >>= b + 8;
2158 		  bits -= b + 8;
2159 		}
2160 
2161 	      if (lit < 256)
2162 		{
2163 		  if (unlikely (pout == poutend))
2164 		    {
2165 		      elf_zlib_failed ();
2166 		      return 0;
2167 		    }
2168 
2169 		  *pout++ = lit;
2170 
2171 		  /* We will need to write the next byte soon.  We ask
2172 		     for high temporal locality because we will write
2173 		     to the whole cache line soon.  */
2174 		  __builtin_prefetch (pout, 1, 3);
2175 		}
2176 	      else if (lit == 256)
2177 		{
2178 		  /* The end of the block.  */
2179 		  break;
2180 		}
2181 	      else
2182 		{
2183 		  unsigned int dist;
2184 		  unsigned int len;
2185 
2186 		  /* Convert lit into a length.  */
2187 
2188 		  if (lit < 265)
2189 		    len = lit - 257 + 3;
2190 		  else if (lit == 285)
2191 		    len = 258;
2192 		  else if (unlikely (lit > 285))
2193 		    {
2194 		      elf_zlib_failed ();
2195 		      return 0;
2196 		    }
2197 		  else
2198 		    {
2199 		      unsigned int extra;
2200 
2201 		      if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2202 			return 0;
2203 
2204 		      /* This is an expression for the table of length
2205 			 codes in RFC 1951 3.2.5.  */
2206 		      lit -= 265;
2207 		      extra = (lit >> 2) + 1;
2208 		      len = (lit & 3) << extra;
2209 		      len += 11;
2210 		      len += ((1U << (extra - 1)) - 1) << 3;
2211 		      len += val & ((1U << extra) - 1);
2212 		      val >>= extra;
2213 		      bits -= extra;
2214 		    }
2215 
2216 		  if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2217 		    return 0;
2218 
2219 		  t = tdist[val & 0xff];
2220 		  b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2221 		  v = t & HUFFMAN_VALUE_MASK;
2222 
2223 		  if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2224 		    {
2225 		      dist = v;
2226 		      val >>= b + 1;
2227 		      bits -= b + 1;
2228 		    }
2229 		  else
2230 		    {
2231 		      t = tdist[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2232 		      b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2233 		      dist = t & HUFFMAN_VALUE_MASK;
2234 		      val >>= b + 8;
2235 		      bits -= b + 8;
2236 		    }
2237 
2238 		  /* Convert dist to a distance.  */
2239 
2240 		  if (dist == 0)
2241 		    {
2242 		      /* A distance of 1.  A common case, meaning
2243 			 repeat the last character LEN times.  */
2244 
2245 		      if (unlikely (pout == porigout))
2246 			{
2247 			  elf_zlib_failed ();
2248 			  return 0;
2249 			}
2250 
2251 		      if (unlikely ((unsigned int) (poutend - pout) < len))
2252 			{
2253 			  elf_zlib_failed ();
2254 			  return 0;
2255 			}
2256 
2257 		      memset (pout, pout[-1], len);
2258 		      pout += len;
2259 		    }
2260 		  else if (unlikely (dist > 29))
2261 		    {
2262 		      elf_zlib_failed ();
2263 		      return 0;
2264 		    }
2265 		  else
2266 		    {
2267 		      if (dist < 4)
2268 			dist = dist + 1;
2269 		      else
2270 			{
2271 			  unsigned int extra;
2272 
2273 			  if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2274 			    return 0;
2275 
2276 			  /* This is an expression for the table of
2277 			     distance codes in RFC 1951 3.2.5.  */
2278 			  dist -= 4;
2279 			  extra = (dist >> 1) + 1;
2280 			  dist = (dist & 1) << extra;
2281 			  dist += 5;
2282 			  dist += ((1U << (extra - 1)) - 1) << 2;
2283 			  dist += val & ((1U << extra) - 1);
2284 			  val >>= extra;
2285 			  bits -= extra;
2286 			}
2287 
2288 		      /* Go back dist bytes, and copy len bytes from
2289 			 there.  */
2290 
2291 		      if (unlikely ((unsigned int) (pout - porigout) < dist))
2292 			{
2293 			  elf_zlib_failed ();
2294 			  return 0;
2295 			}
2296 
2297 		      if (unlikely ((unsigned int) (poutend - pout) < len))
2298 			{
2299 			  elf_zlib_failed ();
2300 			  return 0;
2301 			}
2302 
2303 		      if (dist >= len)
2304 			{
2305 			  memcpy (pout, pout - dist, len);
2306 			  pout += len;
2307 			}
2308 		      else
2309 			{
2310 			  while (len > 0)
2311 			    {
2312 			      unsigned int copy;
2313 
2314 			      copy = len < dist ? len : dist;
2315 			      memcpy (pout, pout - dist, copy);
2316 			      len -= copy;
2317 			      pout += copy;
2318 			    }
2319 			}
2320 		    }
2321 		}
2322 	    }
2323 	}
2324     }
2325 
2326   /* We should have filled the output buffer.  */
2327   if (unlikely (pout != poutend))
2328     {
2329       elf_zlib_failed ();
2330       return 0;
2331     }
2332 
2333   return 1;
2334 }
2335 
2336 /* Verify the zlib checksum.  The checksum is in the 4 bytes at
2337    CHECKBYTES, and the uncompressed data is at UNCOMPRESSED /
2338    UNCOMPRESSED_SIZE.  Returns 1 on success, 0 on failure.  */
2339 
2340 static int
2341 elf_zlib_verify_checksum (const unsigned char *checkbytes,
2342 			  const unsigned char *uncompressed,
2343 			  size_t uncompressed_size)
2344 {
2345   unsigned int i;
2346   unsigned int cksum;
2347   const unsigned char *p;
2348   uint32_t s1;
2349   uint32_t s2;
2350   size_t hsz;
2351 
2352   cksum = 0;
2353   for (i = 0; i < 4; i++)
2354     cksum = (cksum << 8) | checkbytes[i];
2355 
2356   s1 = 1;
2357   s2 = 0;
2358 
2359   /* Minimize modulo operations.  */
2360 
2361   p = uncompressed;
2362   hsz = uncompressed_size;
2363   while (hsz >= 5552)
2364     {
2365       for (i = 0; i < 5552; i += 16)
2366 	{
2367 	  /* Manually unroll loop 16 times.  */
2368 	  s1 = s1 + *p++;
2369 	  s2 = s2 + s1;
2370 	  s1 = s1 + *p++;
2371 	  s2 = s2 + s1;
2372 	  s1 = s1 + *p++;
2373 	  s2 = s2 + s1;
2374 	  s1 = s1 + *p++;
2375 	  s2 = s2 + s1;
2376 	  s1 = s1 + *p++;
2377 	  s2 = s2 + s1;
2378 	  s1 = s1 + *p++;
2379 	  s2 = s2 + s1;
2380 	  s1 = s1 + *p++;
2381 	  s2 = s2 + s1;
2382 	  s1 = s1 + *p++;
2383 	  s2 = s2 + s1;
2384 	  s1 = s1 + *p++;
2385 	  s2 = s2 + s1;
2386 	  s1 = s1 + *p++;
2387 	  s2 = s2 + s1;
2388 	  s1 = s1 + *p++;
2389 	  s2 = s2 + s1;
2390 	  s1 = s1 + *p++;
2391 	  s2 = s2 + s1;
2392 	  s1 = s1 + *p++;
2393 	  s2 = s2 + s1;
2394 	  s1 = s1 + *p++;
2395 	  s2 = s2 + s1;
2396 	  s1 = s1 + *p++;
2397 	  s2 = s2 + s1;
2398 	  s1 = s1 + *p++;
2399 	  s2 = s2 + s1;
2400 	}
2401       hsz -= 5552;
2402       s1 %= 65521;
2403       s2 %= 65521;
2404     }
2405 
2406   while (hsz >= 16)
2407     {
2408       /* Manually unroll loop 16 times.  */
2409       s1 = s1 + *p++;
2410       s2 = s2 + s1;
2411       s1 = s1 + *p++;
2412       s2 = s2 + s1;
2413       s1 = s1 + *p++;
2414       s2 = s2 + s1;
2415       s1 = s1 + *p++;
2416       s2 = s2 + s1;
2417       s1 = s1 + *p++;
2418       s2 = s2 + s1;
2419       s1 = s1 + *p++;
2420       s2 = s2 + s1;
2421       s1 = s1 + *p++;
2422       s2 = s2 + s1;
2423       s1 = s1 + *p++;
2424       s2 = s2 + s1;
2425       s1 = s1 + *p++;
2426       s2 = s2 + s1;
2427       s1 = s1 + *p++;
2428       s2 = s2 + s1;
2429       s1 = s1 + *p++;
2430       s2 = s2 + s1;
2431       s1 = s1 + *p++;
2432       s2 = s2 + s1;
2433       s1 = s1 + *p++;
2434       s2 = s2 + s1;
2435       s1 = s1 + *p++;
2436       s2 = s2 + s1;
2437       s1 = s1 + *p++;
2438       s2 = s2 + s1;
2439       s1 = s1 + *p++;
2440       s2 = s2 + s1;
2441 
2442       hsz -= 16;
2443     }
2444 
2445   for (i = 0; i < hsz; ++i)
2446     {
2447       s1 = s1 + *p++;
2448       s2 = s2 + s1;
2449     }
2450 
2451   s1 %= 65521;
2452   s2 %= 65521;
2453 
2454   if (unlikely ((s2 << 16) + s1 != cksum))
2455     {
2456       elf_zlib_failed ();
2457       return 0;
2458     }
2459 
2460   return 1;
2461 }
2462 
2463 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT, and verify the
2464    checksum.  Return 1 on success, 0 on error.  */
2465 
2466 static int
2467 elf_zlib_inflate_and_verify (const unsigned char *pin, size_t sin,
2468 			     uint16_t *zdebug_table, unsigned char *pout,
2469 			     size_t sout)
2470 {
2471   if (!elf_zlib_inflate (pin, sin, zdebug_table, pout, sout))
2472     return 0;
2473   if (!elf_zlib_verify_checksum (pin + sin - 4, pout, sout))
2474     return 0;
2475   return 1;
2476 }
2477 
2478 /* Uncompress the old compressed debug format, the one emitted by
2479    --compress-debug-sections=zlib-gnu.  The compressed data is in
2480    COMPRESSED / COMPRESSED_SIZE, and the function writes to
2481    *UNCOMPRESSED / *UNCOMPRESSED_SIZE.  ZDEBUG_TABLE is work space to
2482    hold Huffman tables.  Returns 0 on error, 1 on successful
2483    decompression or if something goes wrong.  In general we try to
2484    carry on, by returning 1, even if we can't decompress.  */
2485 
2486 static int
2487 elf_uncompress_zdebug (struct backtrace_state *state,
2488 		       const unsigned char *compressed, size_t compressed_size,
2489 		       uint16_t *zdebug_table,
2490 		       backtrace_error_callback error_callback, void *data,
2491 		       unsigned char **uncompressed, size_t *uncompressed_size)
2492 {
2493   size_t sz;
2494   size_t i;
2495   unsigned char *po;
2496 
2497   *uncompressed = NULL;
2498   *uncompressed_size = 0;
2499 
2500   /* The format starts with the four bytes ZLIB, followed by the 8
2501      byte length of the uncompressed data in big-endian order,
2502      followed by a zlib stream.  */
2503 
2504   if (compressed_size < 12 || memcmp (compressed, "ZLIB", 4) != 0)
2505     return 1;
2506 
2507   sz = 0;
2508   for (i = 0; i < 8; i++)
2509     sz = (sz << 8) | compressed[i + 4];
2510 
2511   if (*uncompressed != NULL && *uncompressed_size >= sz)
2512     po = *uncompressed;
2513   else
2514     {
2515       po = (unsigned char *) backtrace_alloc (state, sz, error_callback, data);
2516       if (po == NULL)
2517 	return 0;
2518     }
2519 
2520   if (!elf_zlib_inflate_and_verify (compressed + 12, compressed_size - 12,
2521 				    zdebug_table, po, sz))
2522     return 1;
2523 
2524   *uncompressed = po;
2525   *uncompressed_size = sz;
2526 
2527   return 1;
2528 }
2529 
2530 /* Uncompress the new compressed debug format, the official standard
2531    ELF approach emitted by --compress-debug-sections=zlib-gabi.  The
2532    compressed data is in COMPRESSED / COMPRESSED_SIZE, and the
2533    function writes to *UNCOMPRESSED / *UNCOMPRESSED_SIZE.
2534    ZDEBUG_TABLE is work space as for elf_uncompress_zdebug.  Returns 0
2535    on error, 1 on successful decompression or if something goes wrong.
2536    In general we try to carry on, by returning 1, even if we can't
2537    decompress.  */
2538 
2539 static int
2540 elf_uncompress_chdr (struct backtrace_state *state,
2541 		     const unsigned char *compressed, size_t compressed_size,
2542 		     uint16_t *zdebug_table,
2543 		     backtrace_error_callback error_callback, void *data,
2544 		     unsigned char **uncompressed, size_t *uncompressed_size)
2545 {
2546   const b_elf_chdr *chdr;
2547   unsigned char *po;
2548 
2549   *uncompressed = NULL;
2550   *uncompressed_size = 0;
2551 
2552   /* The format starts with an ELF compression header.  */
2553   if (compressed_size < sizeof (b_elf_chdr))
2554     return 1;
2555 
2556   chdr = (const b_elf_chdr *) compressed;
2557 
2558   if (chdr->ch_type != ELFCOMPRESS_ZLIB)
2559     {
2560       /* Unsupported compression algorithm.  */
2561       return 1;
2562     }
2563 
2564   if (*uncompressed != NULL && *uncompressed_size >= chdr->ch_size)
2565     po = *uncompressed;
2566   else
2567     {
2568       po = (unsigned char *) backtrace_alloc (state, chdr->ch_size,
2569 					      error_callback, data);
2570       if (po == NULL)
2571 	return 0;
2572     }
2573 
2574   if (!elf_zlib_inflate_and_verify (compressed + sizeof (b_elf_chdr),
2575 				    compressed_size - sizeof (b_elf_chdr),
2576 				    zdebug_table, po, chdr->ch_size))
2577     return 1;
2578 
2579   *uncompressed = po;
2580   *uncompressed_size = chdr->ch_size;
2581 
2582   return 1;
2583 }
2584 
2585 /* This function is a hook for testing the zlib support.  It is only
2586    used by tests.  */
2587 
2588 int
2589 backtrace_uncompress_zdebug (struct backtrace_state *state,
2590 			     const unsigned char *compressed,
2591 			     size_t compressed_size,
2592 			     backtrace_error_callback error_callback,
2593 			     void *data, unsigned char **uncompressed,
2594 			     size_t *uncompressed_size)
2595 {
2596   uint16_t *zdebug_table;
2597   int ret;
2598 
2599   zdebug_table = ((uint16_t *) backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
2600 						error_callback, data));
2601   if (zdebug_table == NULL)
2602     return 0;
2603   ret = elf_uncompress_zdebug (state, compressed, compressed_size,
2604 			       zdebug_table, error_callback, data,
2605 			       uncompressed, uncompressed_size);
2606   backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
2607 		  error_callback, data);
2608   return ret;
2609 }
2610 
2611 /* Add the backtrace data for one ELF file.  Returns 1 on success,
2612    0 on failure (in both cases descriptor is closed) or -1 if exe
2613    is non-zero and the ELF file is ET_DYN, which tells the caller that
2614    elf_add will need to be called on the descriptor again after
2615    base_address is determined.  */
2616 
2617 static int
2618 elf_add (struct backtrace_state *state, const char *filename, int descriptor,
2619 	 uintptr_t base_address, backtrace_error_callback error_callback,
2620 	 void *data, fileline *fileline_fn, int *found_sym, int *found_dwarf,
2621 	 struct dwarf_data **fileline_entry, int exe, int debuginfo,
2622 	 const char *with_buildid_data, uint32_t with_buildid_size)
2623 {
2624   struct backtrace_view ehdr_view;
2625   b_elf_ehdr ehdr;
2626   off_t shoff;
2627   unsigned int shnum;
2628   unsigned int shstrndx;
2629   struct backtrace_view shdrs_view;
2630   int shdrs_view_valid;
2631   const b_elf_shdr *shdrs;
2632   const b_elf_shdr *shstrhdr;
2633   size_t shstr_size;
2634   off_t shstr_off;
2635   struct backtrace_view names_view;
2636   int names_view_valid;
2637   const char *names;
2638   unsigned int symtab_shndx;
2639   unsigned int dynsym_shndx;
2640   unsigned int i;
2641   struct debug_section_info sections[DEBUG_MAX];
2642   struct debug_section_info zsections[DEBUG_MAX];
2643   struct backtrace_view symtab_view;
2644   int symtab_view_valid;
2645   struct backtrace_view strtab_view;
2646   int strtab_view_valid;
2647   struct backtrace_view buildid_view;
2648   int buildid_view_valid;
2649   const char *buildid_data;
2650   uint32_t buildid_size;
2651   struct backtrace_view debuglink_view;
2652   int debuglink_view_valid;
2653   const char *debuglink_name;
2654   uint32_t debuglink_crc;
2655   struct backtrace_view debugaltlink_view;
2656   int debugaltlink_view_valid;
2657   const char *debugaltlink_name;
2658   const char *debugaltlink_buildid_data;
2659   uint32_t debugaltlink_buildid_size;
2660   off_t min_offset;
2661   off_t max_offset;
2662   struct backtrace_view debug_view;
2663   int debug_view_valid;
2664   unsigned int using_debug_view;
2665   uint16_t *zdebug_table;
2666   struct elf_ppc64_opd_data opd_data, *opd;
2667   struct dwarf_sections dwarf_sections;
2668 
2669   if (!debuginfo)
2670     {
2671       *found_sym = 0;
2672       *found_dwarf = 0;
2673     }
2674 
2675   shdrs_view_valid = 0;
2676   names_view_valid = 0;
2677   symtab_view_valid = 0;
2678   strtab_view_valid = 0;
2679   buildid_view_valid = 0;
2680   buildid_data = NULL;
2681   buildid_size = 0;
2682   debuglink_view_valid = 0;
2683   debuglink_name = NULL;
2684   debuglink_crc = 0;
2685   debugaltlink_view_valid = 0;
2686   debugaltlink_name = NULL;
2687   debugaltlink_buildid_data = NULL;
2688   debugaltlink_buildid_size = 0;
2689   debug_view_valid = 0;
2690   opd = NULL;
2691 
2692   if (!backtrace_get_view (state, descriptor, 0, sizeof ehdr, error_callback,
2693 			   data, &ehdr_view))
2694     goto fail;
2695 
2696   memcpy (&ehdr, ehdr_view.data, sizeof ehdr);
2697 
2698   backtrace_release_view (state, &ehdr_view, error_callback, data);
2699 
2700   if (ehdr.e_ident[EI_MAG0] != ELFMAG0
2701       || ehdr.e_ident[EI_MAG1] != ELFMAG1
2702       || ehdr.e_ident[EI_MAG2] != ELFMAG2
2703       || ehdr.e_ident[EI_MAG3] != ELFMAG3)
2704     {
2705       error_callback (data, "executable file is not ELF", 0);
2706       goto fail;
2707     }
2708   if (ehdr.e_ident[EI_VERSION] != EV_CURRENT)
2709     {
2710       error_callback (data, "executable file is unrecognized ELF version", 0);
2711       goto fail;
2712     }
2713 
2714 #if BACKTRACE_ELF_SIZE == 32
2715 #define BACKTRACE_ELFCLASS ELFCLASS32
2716 #else
2717 #define BACKTRACE_ELFCLASS ELFCLASS64
2718 #endif
2719 
2720   if (ehdr.e_ident[EI_CLASS] != BACKTRACE_ELFCLASS)
2721     {
2722       error_callback (data, "executable file is unexpected ELF class", 0);
2723       goto fail;
2724     }
2725 
2726   if (ehdr.e_ident[EI_DATA] != ELFDATA2LSB
2727       && ehdr.e_ident[EI_DATA] != ELFDATA2MSB)
2728     {
2729       error_callback (data, "executable file has unknown endianness", 0);
2730       goto fail;
2731     }
2732 
2733   /* If the executable is ET_DYN, it is either a PIE, or we are running
2734      directly a shared library with .interp.  We need to wait for
2735      dl_iterate_phdr in that case to determine the actual base_address.  */
2736   if (exe && ehdr.e_type == ET_DYN)
2737     return -1;
2738 
2739   shoff = ehdr.e_shoff;
2740   shnum = ehdr.e_shnum;
2741   shstrndx = ehdr.e_shstrndx;
2742 
2743   if ((shnum == 0 || shstrndx == SHN_XINDEX)
2744       && shoff != 0)
2745     {
2746       struct backtrace_view shdr_view;
2747       const b_elf_shdr *shdr;
2748 
2749       if (!backtrace_get_view (state, descriptor, shoff, sizeof shdr,
2750 			       error_callback, data, &shdr_view))
2751 	goto fail;
2752 
2753       shdr = (const b_elf_shdr *) shdr_view.data;
2754 
2755       if (shnum == 0)
2756 	shnum = shdr->sh_size;
2757 
2758       if (shstrndx == SHN_XINDEX)
2759 	{
2760 	  shstrndx = shdr->sh_link;
2761 
2762 	  /* Versions of the GNU binutils between 2.12 and 2.18 did
2763 	     not handle objects with more than SHN_LORESERVE sections
2764 	     correctly.  All large section indexes were offset by
2765 	     0x100.  There is more information at
2766 	     http://sourceware.org/bugzilla/show_bug.cgi?id-5900 .
2767 	     Fortunately these object files are easy to detect, as the
2768 	     GNU binutils always put the section header string table
2769 	     near the end of the list of sections.  Thus if the
2770 	     section header string table index is larger than the
2771 	     number of sections, then we know we have to subtract
2772 	     0x100 to get the real section index.  */
2773 	  if (shstrndx >= shnum && shstrndx >= SHN_LORESERVE + 0x100)
2774 	    shstrndx -= 0x100;
2775 	}
2776 
2777       backtrace_release_view (state, &shdr_view, error_callback, data);
2778     }
2779 
2780   /* To translate PC to file/line when using DWARF, we need to find
2781      the .debug_info and .debug_line sections.  */
2782 
2783   /* Read the section headers, skipping the first one.  */
2784 
2785   if (!backtrace_get_view (state, descriptor, shoff + sizeof (b_elf_shdr),
2786 			   (shnum - 1) * sizeof (b_elf_shdr),
2787 			   error_callback, data, &shdrs_view))
2788     goto fail;
2789   shdrs_view_valid = 1;
2790   shdrs = (const b_elf_shdr *) shdrs_view.data;
2791 
2792   /* Read the section names.  */
2793 
2794   shstrhdr = &shdrs[shstrndx - 1];
2795   shstr_size = shstrhdr->sh_size;
2796   shstr_off = shstrhdr->sh_offset;
2797 
2798   if (!backtrace_get_view (state, descriptor, shstr_off, shstrhdr->sh_size,
2799 			   error_callback, data, &names_view))
2800     goto fail;
2801   names_view_valid = 1;
2802   names = (const char *) names_view.data;
2803 
2804   symtab_shndx = 0;
2805   dynsym_shndx = 0;
2806 
2807   memset (sections, 0, sizeof sections);
2808   memset (zsections, 0, sizeof zsections);
2809 
2810   /* Look for the symbol table.  */
2811   for (i = 1; i < shnum; ++i)
2812     {
2813       const b_elf_shdr *shdr;
2814       unsigned int sh_name;
2815       const char *name;
2816       int j;
2817 
2818       shdr = &shdrs[i - 1];
2819 
2820       if (shdr->sh_type == SHT_SYMTAB)
2821 	symtab_shndx = i;
2822       else if (shdr->sh_type == SHT_DYNSYM)
2823 	dynsym_shndx = i;
2824 
2825       sh_name = shdr->sh_name;
2826       if (sh_name >= shstr_size)
2827 	{
2828 	  error_callback (data, "ELF section name out of range", 0);
2829 	  goto fail;
2830 	}
2831 
2832       name = names + sh_name;
2833 
2834       for (j = 0; j < (int) DEBUG_MAX; ++j)
2835 	{
2836 	  if (strcmp (name, dwarf_section_names[j]) == 0)
2837 	    {
2838 	      sections[j].offset = shdr->sh_offset;
2839 	      sections[j].size = shdr->sh_size;
2840 	      sections[j].compressed = (shdr->sh_flags & SHF_COMPRESSED) != 0;
2841 	      break;
2842 	    }
2843 	}
2844 
2845       if (name[0] == '.' && name[1] == 'z')
2846 	{
2847 	  for (j = 0; j < (int) DEBUG_MAX; ++j)
2848 	    {
2849 	      if (strcmp (name + 2, dwarf_section_names[j] + 1) == 0)
2850 		{
2851 		  zsections[j].offset = shdr->sh_offset;
2852 		  zsections[j].size = shdr->sh_size;
2853 		  break;
2854 		}
2855 	    }
2856 	}
2857 
2858       /* Read the build ID if present.  This could check for any
2859 	 SHT_NOTE section with the right note name and type, but gdb
2860 	 looks for a specific section name.  */
2861       if ((!debuginfo || with_buildid_data != NULL)
2862 	  && !buildid_view_valid
2863 	  && strcmp (name, ".note.gnu.build-id") == 0)
2864 	{
2865 	  const b_elf_note *note;
2866 
2867 	  if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2868 				   shdr->sh_size, error_callback, data,
2869 				   &buildid_view))
2870 	    goto fail;
2871 
2872 	  buildid_view_valid = 1;
2873 	  note = (const b_elf_note *) buildid_view.data;
2874 	  if (note->type == NT_GNU_BUILD_ID
2875 	      && note->namesz == 4
2876 	      && strncmp (note->name, "GNU", 4) == 0
2877 	      && shdr->sh_size <= 12 + ((note->namesz + 3) & ~ 3) + note->descsz)
2878 	    {
2879 	      buildid_data = &note->name[0] + ((note->namesz + 3) & ~ 3);
2880 	      buildid_size = note->descsz;
2881 	    }
2882 
2883 	  if (with_buildid_size != 0)
2884 	    {
2885 	      if (buildid_size != with_buildid_size)
2886 		goto fail;
2887 
2888 	      if (memcmp (buildid_data, with_buildid_data, buildid_size) != 0)
2889 		goto fail;
2890 	    }
2891 	}
2892 
2893       /* Read the debuglink file if present.  */
2894       if (!debuginfo
2895 	  && !debuglink_view_valid
2896 	  && strcmp (name, ".gnu_debuglink") == 0)
2897 	{
2898 	  const char *debuglink_data;
2899 	  size_t crc_offset;
2900 
2901 	  if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2902 				   shdr->sh_size, error_callback, data,
2903 				   &debuglink_view))
2904 	    goto fail;
2905 
2906 	  debuglink_view_valid = 1;
2907 	  debuglink_data = (const char *) debuglink_view.data;
2908 	  crc_offset = strnlen (debuglink_data, shdr->sh_size);
2909 	  crc_offset = (crc_offset + 3) & ~3;
2910 	  if (crc_offset + 4 <= shdr->sh_size)
2911 	    {
2912 	      debuglink_name = debuglink_data;
2913 	      debuglink_crc = *(const uint32_t*)(debuglink_data + crc_offset);
2914 	    }
2915 	}
2916 
2917       if (!debugaltlink_view_valid
2918 	  && strcmp (name, ".gnu_debugaltlink") == 0)
2919 	{
2920 	  const char *debugaltlink_data;
2921 	  size_t debugaltlink_name_len;
2922 
2923 	  if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2924 				   shdr->sh_size, error_callback, data,
2925 				   &debugaltlink_view))
2926 	    goto fail;
2927 
2928 	  debugaltlink_view_valid = 1;
2929 	  debugaltlink_data = (const char *) debugaltlink_view.data;
2930 	  debugaltlink_name = debugaltlink_data;
2931 	  debugaltlink_name_len = strnlen (debugaltlink_data, shdr->sh_size);
2932 	  if (debugaltlink_name_len < shdr->sh_size)
2933 	    {
2934 	      /* Include terminating zero.  */
2935 	      debugaltlink_name_len += 1;
2936 
2937 	      debugaltlink_buildid_data
2938 		= debugaltlink_data + debugaltlink_name_len;
2939 	      debugaltlink_buildid_size = shdr->sh_size - debugaltlink_name_len;
2940 	    }
2941 	}
2942 
2943       /* Read the .opd section on PowerPC64 ELFv1.  */
2944       if (ehdr.e_machine == EM_PPC64
2945 	  && (ehdr.e_flags & EF_PPC64_ABI) < 2
2946 	  && shdr->sh_type == SHT_PROGBITS
2947 	  && strcmp (name, ".opd") == 0)
2948 	{
2949 	  if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2950 				   shdr->sh_size, error_callback, data,
2951 				   &opd_data.view))
2952 	    goto fail;
2953 
2954 	  opd = &opd_data;
2955 	  opd->addr = shdr->sh_addr;
2956 	  opd->data = (const char *) opd_data.view.data;
2957 	  opd->size = shdr->sh_size;
2958 	}
2959     }
2960 
2961   if (symtab_shndx == 0)
2962     symtab_shndx = dynsym_shndx;
2963   if (symtab_shndx != 0 && !debuginfo)
2964     {
2965       const b_elf_shdr *symtab_shdr;
2966       unsigned int strtab_shndx;
2967       const b_elf_shdr *strtab_shdr;
2968       struct elf_syminfo_data *sdata;
2969 
2970       symtab_shdr = &shdrs[symtab_shndx - 1];
2971       strtab_shndx = symtab_shdr->sh_link;
2972       if (strtab_shndx >= shnum)
2973 	{
2974 	  error_callback (data,
2975 			  "ELF symbol table strtab link out of range", 0);
2976 	  goto fail;
2977 	}
2978       strtab_shdr = &shdrs[strtab_shndx - 1];
2979 
2980       if (!backtrace_get_view (state, descriptor, symtab_shdr->sh_offset,
2981 			       symtab_shdr->sh_size, error_callback, data,
2982 			       &symtab_view))
2983 	goto fail;
2984       symtab_view_valid = 1;
2985 
2986       if (!backtrace_get_view (state, descriptor, strtab_shdr->sh_offset,
2987 			       strtab_shdr->sh_size, error_callback, data,
2988 			       &strtab_view))
2989 	goto fail;
2990       strtab_view_valid = 1;
2991 
2992       sdata = ((struct elf_syminfo_data *)
2993 	       backtrace_alloc (state, sizeof *sdata, error_callback, data));
2994       if (sdata == NULL)
2995 	goto fail;
2996 
2997       if (!elf_initialize_syminfo (state, base_address,
2998 				   symtab_view.data, symtab_shdr->sh_size,
2999 				   strtab_view.data, strtab_shdr->sh_size,
3000 				   error_callback, data, sdata, opd))
3001 	{
3002 	  backtrace_free (state, sdata, sizeof *sdata, error_callback, data);
3003 	  goto fail;
3004 	}
3005 
3006       /* We no longer need the symbol table, but we hold on to the
3007 	 string table permanently.  */
3008       backtrace_release_view (state, &symtab_view, error_callback, data);
3009       symtab_view_valid = 0;
3010 
3011       *found_sym = 1;
3012 
3013       elf_add_syminfo_data (state, sdata);
3014     }
3015 
3016   backtrace_release_view (state, &shdrs_view, error_callback, data);
3017   shdrs_view_valid = 0;
3018   backtrace_release_view (state, &names_view, error_callback, data);
3019   names_view_valid = 0;
3020 
3021   /* If the debug info is in a separate file, read that one instead.  */
3022 
3023   if (buildid_data != NULL)
3024     {
3025       int d;
3026 
3027       d = elf_open_debugfile_by_buildid (state, buildid_data, buildid_size,
3028 					 error_callback, data);
3029       if (d >= 0)
3030 	{
3031 	  int ret;
3032 
3033 	  backtrace_release_view (state, &buildid_view, error_callback, data);
3034 	  if (debuglink_view_valid)
3035 	    backtrace_release_view (state, &debuglink_view, error_callback,
3036 				    data);
3037 	  if (debugaltlink_view_valid)
3038 	    backtrace_release_view (state, &debugaltlink_view, error_callback,
3039 				    data);
3040 	  ret = elf_add (state, "", d, base_address, error_callback, data,
3041 			 fileline_fn, found_sym, found_dwarf, NULL, 0, 1, NULL,
3042 			 0);
3043 	  if (ret < 0)
3044 	    backtrace_close (d, error_callback, data);
3045 	  else
3046 	    backtrace_close (descriptor, error_callback, data);
3047 	  return ret;
3048 	}
3049     }
3050 
3051   if (buildid_view_valid)
3052     {
3053       backtrace_release_view (state, &buildid_view, error_callback, data);
3054       buildid_view_valid = 0;
3055     }
3056 
3057   if (opd)
3058     {
3059       backtrace_release_view (state, &opd->view, error_callback, data);
3060       opd = NULL;
3061     }
3062 
3063   if (debuglink_name != NULL)
3064     {
3065       int d;
3066 
3067       d = elf_open_debugfile_by_debuglink (state, filename, debuglink_name,
3068 					   debuglink_crc, error_callback,
3069 					   data);
3070       if (d >= 0)
3071 	{
3072 	  int ret;
3073 
3074 	  backtrace_release_view (state, &debuglink_view, error_callback,
3075 				  data);
3076 	  if (debugaltlink_view_valid)
3077 	    backtrace_release_view (state, &debugaltlink_view, error_callback,
3078 				    data);
3079 	  ret = elf_add (state, "", d, base_address, error_callback, data,
3080 			 fileline_fn, found_sym, found_dwarf, NULL, 0, 1, NULL,
3081 			 0);
3082 	  if (ret < 0)
3083 	    backtrace_close (d, error_callback, data);
3084 	  else
3085 	    backtrace_close(descriptor, error_callback, data);
3086 	  return ret;
3087 	}
3088     }
3089 
3090   if (debuglink_view_valid)
3091     {
3092       backtrace_release_view (state, &debuglink_view, error_callback, data);
3093       debuglink_view_valid = 0;
3094     }
3095 
3096   struct dwarf_data *fileline_altlink = NULL;
3097   if (debugaltlink_name != NULL)
3098     {
3099       int d;
3100 
3101       d = elf_open_debugfile_by_debuglink (state, filename, debugaltlink_name,
3102 					   0, error_callback, data);
3103       if (d >= 0)
3104 	{
3105 	  int ret;
3106 
3107 	  ret = elf_add (state, filename, d, base_address, error_callback, data,
3108 			 fileline_fn, found_sym, found_dwarf, &fileline_altlink,
3109 			 0, 1, debugaltlink_buildid_data,
3110 			 debugaltlink_buildid_size);
3111 	  backtrace_release_view (state, &debugaltlink_view, error_callback,
3112 				  data);
3113 	  debugaltlink_view_valid = 0;
3114 	  if (ret < 0)
3115 	    {
3116 	      backtrace_close (d, error_callback, data);
3117 	      return ret;
3118 	    }
3119 	}
3120     }
3121 
3122   if (debugaltlink_view_valid)
3123     {
3124       backtrace_release_view (state, &debugaltlink_view, error_callback, data);
3125       debugaltlink_view_valid = 0;
3126     }
3127 
3128   /* Read all the debug sections in a single view, since they are
3129      probably adjacent in the file.  If any of sections are
3130      uncompressed, we never release this view.  */
3131 
3132   min_offset = 0;
3133   max_offset = 0;
3134   for (i = 0; i < (int) DEBUG_MAX; ++i)
3135     {
3136       off_t end;
3137 
3138       if (sections[i].size != 0)
3139 	{
3140 	  if (min_offset == 0 || sections[i].offset < min_offset)
3141 	    min_offset = sections[i].offset;
3142 	  end = sections[i].offset + sections[i].size;
3143 	  if (end > max_offset)
3144 	    max_offset = end;
3145 	}
3146       if (zsections[i].size != 0)
3147 	{
3148 	  if (min_offset == 0 || zsections[i].offset < min_offset)
3149 	    min_offset = zsections[i].offset;
3150 	  end = zsections[i].offset + zsections[i].size;
3151 	  if (end > max_offset)
3152 	    max_offset = end;
3153 	}
3154     }
3155   if (min_offset == 0 || max_offset == 0)
3156     {
3157       if (!backtrace_close (descriptor, error_callback, data))
3158 	goto fail;
3159       return 1;
3160     }
3161 
3162   if (!backtrace_get_view (state, descriptor, min_offset,
3163 			   max_offset - min_offset,
3164 			   error_callback, data, &debug_view))
3165     goto fail;
3166   debug_view_valid = 1;
3167 
3168   /* We've read all we need from the executable.  */
3169   if (!backtrace_close (descriptor, error_callback, data))
3170     goto fail;
3171   descriptor = -1;
3172 
3173   using_debug_view = 0;
3174   for (i = 0; i < (int) DEBUG_MAX; ++i)
3175     {
3176       if (sections[i].size == 0)
3177 	sections[i].data = NULL;
3178       else
3179 	{
3180 	  sections[i].data = ((const unsigned char *) debug_view.data
3181 			      + (sections[i].offset - min_offset));
3182 	  ++using_debug_view;
3183 	}
3184 
3185       if (zsections[i].size == 0)
3186 	zsections[i].data = NULL;
3187       else
3188 	zsections[i].data = ((const unsigned char *) debug_view.data
3189 			     + (zsections[i].offset - min_offset));
3190     }
3191 
3192   /* Uncompress the old format (--compress-debug-sections=zlib-gnu).  */
3193 
3194   zdebug_table = NULL;
3195   for (i = 0; i < (int) DEBUG_MAX; ++i)
3196     {
3197       if (sections[i].size == 0 && zsections[i].size > 0)
3198 	{
3199 	  unsigned char *uncompressed_data;
3200 	  size_t uncompressed_size;
3201 
3202 	  if (zdebug_table == NULL)
3203 	    {
3204 	      zdebug_table = ((uint16_t *)
3205 			      backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
3206 					       error_callback, data));
3207 	      if (zdebug_table == NULL)
3208 		goto fail;
3209 	    }
3210 
3211 	  uncompressed_data = NULL;
3212 	  uncompressed_size = 0;
3213 	  if (!elf_uncompress_zdebug (state, zsections[i].data,
3214 				      zsections[i].size, zdebug_table,
3215 				      error_callback, data,
3216 				      &uncompressed_data, &uncompressed_size))
3217 	    goto fail;
3218 	  sections[i].data = uncompressed_data;
3219 	  sections[i].size = uncompressed_size;
3220 	  sections[i].compressed = 0;
3221 	}
3222     }
3223 
3224   /* Uncompress the official ELF format
3225      (--compress-debug-sections=zlib-gabi).  */
3226   for (i = 0; i < (int) DEBUG_MAX; ++i)
3227     {
3228       unsigned char *uncompressed_data;
3229       size_t uncompressed_size;
3230 
3231       if (sections[i].size == 0 || !sections[i].compressed)
3232 	continue;
3233 
3234       if (zdebug_table == NULL)
3235 	{
3236 	  zdebug_table = ((uint16_t *)
3237 			  backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
3238 					   error_callback, data));
3239 	  if (zdebug_table == NULL)
3240 	    goto fail;
3241 	}
3242 
3243       uncompressed_data = NULL;
3244       uncompressed_size = 0;
3245       if (!elf_uncompress_chdr (state, sections[i].data, sections[i].size,
3246 				zdebug_table, error_callback, data,
3247 				&uncompressed_data, &uncompressed_size))
3248 	goto fail;
3249       sections[i].data = uncompressed_data;
3250       sections[i].size = uncompressed_size;
3251       sections[i].compressed = 0;
3252 
3253       --using_debug_view;
3254     }
3255 
3256   if (zdebug_table != NULL)
3257     backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
3258 		    error_callback, data);
3259 
3260   if (debug_view_valid && using_debug_view == 0)
3261     {
3262       backtrace_release_view (state, &debug_view, error_callback, data);
3263       debug_view_valid = 0;
3264     }
3265 
3266   for (i = 0; i < (int) DEBUG_MAX; ++i)
3267     {
3268       dwarf_sections.data[i] = sections[i].data;
3269       dwarf_sections.size[i] = sections[i].size;
3270     }
3271 
3272   if (!backtrace_dwarf_add (state, base_address, &dwarf_sections,
3273 			    ehdr.e_ident[EI_DATA] == ELFDATA2MSB,
3274 			    fileline_altlink,
3275 			    error_callback, data, fileline_fn,
3276 			    fileline_entry))
3277     goto fail;
3278 
3279   *found_dwarf = 1;
3280 
3281   return 1;
3282 
3283  fail:
3284   if (shdrs_view_valid)
3285     backtrace_release_view (state, &shdrs_view, error_callback, data);
3286   if (names_view_valid)
3287     backtrace_release_view (state, &names_view, error_callback, data);
3288   if (symtab_view_valid)
3289     backtrace_release_view (state, &symtab_view, error_callback, data);
3290   if (strtab_view_valid)
3291     backtrace_release_view (state, &strtab_view, error_callback, data);
3292   if (debuglink_view_valid)
3293     backtrace_release_view (state, &debuglink_view, error_callback, data);
3294   if (debugaltlink_view_valid)
3295     backtrace_release_view (state, &debugaltlink_view, error_callback, data);
3296   if (buildid_view_valid)
3297     backtrace_release_view (state, &buildid_view, error_callback, data);
3298   if (debug_view_valid)
3299     backtrace_release_view (state, &debug_view, error_callback, data);
3300   if (opd)
3301     backtrace_release_view (state, &opd->view, error_callback, data);
3302   if (descriptor != -1)
3303     backtrace_close (descriptor, error_callback, data);
3304   return 0;
3305 }
3306 
3307 /* Data passed to phdr_callback.  */
3308 
3309 struct phdr_data
3310 {
3311   struct backtrace_state *state;
3312   backtrace_error_callback error_callback;
3313   void *data;
3314   fileline *fileline_fn;
3315   int *found_sym;
3316   int *found_dwarf;
3317   const char *exe_filename;
3318   int exe_descriptor;
3319 };
3320 
3321 /* Callback passed to dl_iterate_phdr.  Load debug info from shared
3322    libraries.  */
3323 
3324 static int
3325 #ifdef __i386__
3326 __attribute__ ((__force_align_arg_pointer__))
3327 #endif
3328 phdr_callback (struct dl_phdr_info *info, size_t size ATTRIBUTE_UNUSED,
3329 	       void *pdata)
3330 {
3331   struct phdr_data *pd = (struct phdr_data *) pdata;
3332   const char *filename;
3333   int descriptor;
3334   int does_not_exist;
3335   fileline elf_fileline_fn;
3336   int found_dwarf;
3337 
3338   /* There is not much we can do if we don't have the module name,
3339      unless executable is ET_DYN, where we expect the very first
3340      phdr_callback to be for the PIE.  */
3341   if (info->dlpi_name == NULL || info->dlpi_name[0] == '\0')
3342     {
3343       if (pd->exe_descriptor == -1)
3344 	return 0;
3345       filename = pd->exe_filename;
3346       descriptor = pd->exe_descriptor;
3347       pd->exe_descriptor = -1;
3348     }
3349   else
3350     {
3351       if (pd->exe_descriptor != -1)
3352 	{
3353 	  backtrace_close (pd->exe_descriptor, pd->error_callback, pd->data);
3354 	  pd->exe_descriptor = -1;
3355 	}
3356 
3357       filename = info->dlpi_name;
3358       descriptor = backtrace_open (info->dlpi_name, pd->error_callback,
3359 				   pd->data, &does_not_exist);
3360       if (descriptor < 0)
3361 	return 0;
3362     }
3363 
3364   if (elf_add (pd->state, filename, descriptor, info->dlpi_addr,
3365 	       pd->error_callback, pd->data, &elf_fileline_fn, pd->found_sym,
3366 	       &found_dwarf, NULL, 0, 0, NULL, 0))
3367     {
3368       if (found_dwarf)
3369 	{
3370 	  *pd->found_dwarf = 1;
3371 	  *pd->fileline_fn = elf_fileline_fn;
3372 	}
3373     }
3374 
3375   return 0;
3376 }
3377 
3378 /* Initialize the backtrace data we need from an ELF executable.  At
3379    the ELF level, all we need to do is find the debug info
3380    sections.  */
3381 
3382 int
3383 backtrace_initialize (struct backtrace_state *state, const char *filename,
3384 		      int descriptor, backtrace_error_callback error_callback,
3385 		      void *data, fileline *fileline_fn)
3386 {
3387   int ret;
3388   int found_sym;
3389   int found_dwarf;
3390   fileline elf_fileline_fn = elf_nodebug;
3391   struct phdr_data pd;
3392 
3393   ret = elf_add (state, filename, descriptor, 0, error_callback, data,
3394 		 &elf_fileline_fn, &found_sym, &found_dwarf, NULL, 1, 0, NULL,
3395 		 0);
3396   if (!ret)
3397     return 0;
3398 
3399   pd.state = state;
3400   pd.error_callback = error_callback;
3401   pd.data = data;
3402   pd.fileline_fn = &elf_fileline_fn;
3403   pd.found_sym = &found_sym;
3404   pd.found_dwarf = &found_dwarf;
3405   pd.exe_filename = filename;
3406   pd.exe_descriptor = ret < 0 ? descriptor : -1;
3407 
3408   dl_iterate_phdr (phdr_callback, (void *) &pd);
3409 
3410   if (!state->threaded)
3411     {
3412       if (found_sym)
3413 	state->syminfo_fn = elf_syminfo;
3414       else if (state->syminfo_fn == NULL)
3415 	state->syminfo_fn = elf_nosyms;
3416     }
3417   else
3418     {
3419       if (found_sym)
3420 	backtrace_atomic_store_pointer (&state->syminfo_fn, elf_syminfo);
3421       else
3422 	(void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
3423 					     elf_nosyms);
3424     }
3425 
3426   if (!state->threaded)
3427     *fileline_fn = state->fileline_fn;
3428   else
3429     *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
3430 
3431   if (*fileline_fn == NULL || *fileline_fn == elf_nodebug)
3432     *fileline_fn = elf_fileline_fn;
3433 
3434   return 1;
3435 }
3436