[RS6000] No inline PLT for V4 bss-plt, implement -mno-pltseq
[official-gcc.git] / libbacktrace / elf.c
blobf3988ec02a05400b5631eea810589035a269a632
1 /* elf.c -- Get debug data from an ELF file for backtraces.
2 Copyright (C) 2012-2019 Free Software Foundation, Inc.
3 Written by Ian Lance Taylor, Google.
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are
7 met:
9 (1) Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
12 (2) Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in
14 the documentation and/or other materials provided with the
15 distribution.
17 (3) The name of the author may not be used to
18 endorse or promote products derived from this software without
19 specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
25 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
29 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
30 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 POSSIBILITY OF SUCH DAMAGE. */
33 #include "config.h"
35 #include <errno.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <sys/types.h>
39 #include <sys/stat.h>
40 #include <unistd.h>
42 #ifdef HAVE_DL_ITERATE_PHDR
43 #include <link.h>
44 #endif
46 #include "backtrace.h"
47 #include "internal.h"
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
59 #ifndef __GNUC__
60 #define __builtin_prefetch(p, r, l)
61 #define unlikely(x) (x)
62 #else
63 #define unlikely(x) __builtin_expect(!!(x), 0)
64 #endif
66 #if !defined(HAVE_DECL_STRNLEN) || !HAVE_DECL_STRNLEN
68 /* If strnlen is not declared, provide our own version. */
70 static size_t
71 xstrnlen (const char *s, size_t maxlen)
73 size_t i;
75 for (i = 0; i < maxlen; ++i)
76 if (s[i] == '\0')
77 break;
78 return i;
81 #define strnlen xstrnlen
83 #endif
85 #ifndef HAVE_LSTAT
87 /* Dummy version of lstat for systems that don't have it. */
89 static int
90 xlstat (const char *path ATTRIBUTE_UNUSED, struct stat *st ATTRIBUTE_UNUSED)
92 return -1;
95 #define lstat xlstat
97 #endif
99 #ifndef HAVE_READLINK
101 /* Dummy version of readlink for systems that don't have it. */
103 static ssize_t
104 xreadlink (const char *path ATTRIBUTE_UNUSED, char *buf ATTRIBUTE_UNUSED,
105 size_t bufsz ATTRIBUTE_UNUSED)
107 return -1;
110 #define readlink xreadlink
112 #endif
114 #ifndef HAVE_DL_ITERATE_PHDR
116 /* Dummy version of dl_iterate_phdr for systems that don't have it. */
118 #define dl_phdr_info x_dl_phdr_info
119 #define dl_iterate_phdr x_dl_iterate_phdr
121 struct dl_phdr_info
123 uintptr_t dlpi_addr;
124 const char *dlpi_name;
127 static int
128 dl_iterate_phdr (int (*callback) (struct dl_phdr_info *,
129 size_t, void *) ATTRIBUTE_UNUSED,
130 void *data ATTRIBUTE_UNUSED)
132 return 0;
135 #endif /* ! defined (HAVE_DL_ITERATE_PHDR) */
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. */
143 #if BACKTRACE_ELF_SIZE != 32 && BACKTRACE_ELF_SIZE != 64
144 #error "Unknown BACKTRACE_ELF_SIZE"
145 #endif
147 /* <link.h> might #include <elf.h> which might define our constants
148 with slightly different values. Undefine them to be safe. */
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
183 /* Basic types. */
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. */
189 #if BACKTRACE_ELF_SIZE == 32
191 typedef uint32_t b_elf_addr; /* Elf_Addr. */
192 typedef uint32_t b_elf_off; /* Elf_Off. */
194 typedef uint32_t b_elf_wxword; /* 32-bit Elf_Word, 64-bit ELF_Xword. */
196 #else
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. */
203 typedef uint64_t b_elf_wxword; /* 32-bit Elf_Word, 64-bit ELF_Xword. */
205 #endif
207 /* Data structures and associated constants. */
209 #define EI_NIDENT 16
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. */
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
236 #define ELFMAG0 0x7f
237 #define ELFMAG1 'E'
238 #define ELFMAG2 'L'
239 #define ELFMAG3 'F'
241 #define ELFCLASS32 1
242 #define ELFCLASS64 2
244 #define ELFDATA2LSB 1
245 #define ELFDATA2MSB 2
247 #define EV_CURRENT 1
249 #define ET_DYN 3
251 #define EM_PPC64 21
252 #define EF_PPC64_ABI 3
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. */
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 */
271 #define SHT_PROGBITS 1
272 #define SHT_SYMTAB 2
273 #define SHT_STRTAB 3
274 #define SHT_DYNSYM 11
276 #define SHF_COMPRESSED 0x800
278 #if BACKTRACE_ELF_SIZE == 32
280 typedef struct
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. */
290 #else /* BACKTRACE_ELF_SIZE != 32 */
292 typedef struct
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. */
302 #endif /* BACKTRACE_ELF_SIZE != 32 */
304 #define STT_OBJECT 1
305 #define STT_FUNC 2
307 typedef struct
309 uint32_t namesz;
310 uint32_t descsz;
311 uint32_t type;
312 char name[1];
313 } b_elf_note;
315 #define NT_GNU_BUILD_ID 3
317 #if BACKTRACE_ELF_SIZE == 32
319 typedef struct
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 */
326 #else /* BACKTRACE_ELF_SIZE != 32 */
328 typedef struct
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 */
336 #endif /* BACKTRACE_ELF_SIZE != 32 */
338 #define ELFCOMPRESS_ZLIB 1
340 /* An index of ELF sections we care about. */
342 enum debug_section
344 DEBUG_INFO,
345 DEBUG_LINE,
346 DEBUG_ABBREV,
347 DEBUG_RANGES,
348 DEBUG_STR,
350 /* The old style compressed sections. This list must correspond to
351 the list of normal debug sections. */
352 ZDEBUG_INFO,
353 ZDEBUG_LINE,
354 ZDEBUG_ABBREV,
355 ZDEBUG_RANGES,
356 ZDEBUG_STR,
358 DEBUG_MAX
361 /* Names of sections, indexed by enum elf_section. */
363 static const char * const debug_section_names[DEBUG_MAX] =
365 ".debug_info",
366 ".debug_line",
367 ".debug_abbrev",
368 ".debug_ranges",
369 ".debug_str",
370 ".zdebug_info",
371 ".zdebug_line",
372 ".zdebug_abbrev",
373 ".zdebug_ranges",
374 ".zdebug_str"
377 /* Information we gather for the sections we care about. */
379 struct debug_section_info
381 /* Section file offset. */
382 off_t offset;
383 /* Section size. */
384 size_t size;
385 /* Section contents, after read from file. */
386 const unsigned char *data;
387 /* Whether the SHF_COMPRESSED flag is set for the section. */
388 int compressed;
391 /* Information we keep for an ELF symbol. */
393 struct elf_symbol
395 /* The name of the symbol. */
396 const char *name;
397 /* The address of the symbol. */
398 uintptr_t address;
399 /* The size of the symbol. */
400 size_t size;
403 /* Information to pass to elf_syminfo. */
405 struct elf_syminfo_data
407 /* Symbols for the next module. */
408 struct elf_syminfo_data *next;
409 /* The ELF symbols, sorted by address. */
410 struct elf_symbol *symbols;
411 /* The number of symbols. */
412 size_t count;
415 /* Information about PowerPC64 ELFv1 .opd section. */
417 struct elf_ppc64_opd_data
419 /* Address of the .opd section. */
420 b_elf_addr addr;
421 /* Section data. */
422 const char *data;
423 /* Size of the .opd section. */
424 size_t size;
425 /* Corresponding section view. */
426 struct backtrace_view view;
429 /* Compute the CRC-32 of BUF/LEN. This uses the CRC used for
430 .gnu_debuglink files. */
432 static uint32_t
433 elf_crc32 (uint32_t crc, const unsigned char *buf, size_t len)
435 static const uint32_t crc32_table[256] =
437 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
438 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
439 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
440 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
441 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
442 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
443 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
444 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
445 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
446 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
447 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
448 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
449 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
450 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
451 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
452 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
453 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
454 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
455 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
456 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
457 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
458 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
459 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
460 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
461 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
462 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
463 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
464 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
465 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
466 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
467 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
468 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
469 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
470 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
471 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
472 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
473 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
474 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
475 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
476 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
477 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
478 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
479 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
480 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
481 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
482 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
483 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
484 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
485 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
486 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
487 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
488 0x2d02ef8d
490 const unsigned char *end;
492 crc = ~crc;
493 for (end = buf + len; buf < end; ++ buf)
494 crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8);
495 return ~crc;
498 /* Return the CRC-32 of the entire file open at DESCRIPTOR. */
500 static uint32_t
501 elf_crc32_file (struct backtrace_state *state, int descriptor,
502 backtrace_error_callback error_callback, void *data)
504 struct stat st;
505 struct backtrace_view file_view;
506 uint32_t ret;
508 if (fstat (descriptor, &st) < 0)
510 error_callback (data, "fstat", errno);
511 return 0;
514 if (!backtrace_get_view (state, descriptor, 0, st.st_size, error_callback,
515 data, &file_view))
516 return 0;
518 ret = elf_crc32 (0, (const unsigned char *) file_view.data, st.st_size);
520 backtrace_release_view (state, &file_view, error_callback, data);
522 return ret;
525 /* A dummy callback function used when we can't find any debug info. */
527 static int
528 elf_nodebug (struct backtrace_state *state ATTRIBUTE_UNUSED,
529 uintptr_t pc ATTRIBUTE_UNUSED,
530 backtrace_full_callback callback ATTRIBUTE_UNUSED,
531 backtrace_error_callback error_callback, void *data)
533 error_callback (data, "no debug info in ELF executable", -1);
534 return 0;
537 /* A dummy callback function used when we can't find a symbol
538 table. */
540 static void
541 elf_nosyms (struct backtrace_state *state ATTRIBUTE_UNUSED,
542 uintptr_t addr ATTRIBUTE_UNUSED,
543 backtrace_syminfo_callback callback ATTRIBUTE_UNUSED,
544 backtrace_error_callback error_callback, void *data)
546 error_callback (data, "no symbol table in ELF executable", -1);
549 /* Compare struct elf_symbol for qsort. */
551 static int
552 elf_symbol_compare (const void *v1, const void *v2)
554 const struct elf_symbol *e1 = (const struct elf_symbol *) v1;
555 const struct elf_symbol *e2 = (const struct elf_symbol *) v2;
557 if (e1->address < e2->address)
558 return -1;
559 else if (e1->address > e2->address)
560 return 1;
561 else
562 return 0;
565 /* Compare an ADDR against an elf_symbol for bsearch. We allocate one
566 extra entry in the array so that this can look safely at the next
567 entry. */
569 static int
570 elf_symbol_search (const void *vkey, const void *ventry)
572 const uintptr_t *key = (const uintptr_t *) vkey;
573 const struct elf_symbol *entry = (const struct elf_symbol *) ventry;
574 uintptr_t addr;
576 addr = *key;
577 if (addr < entry->address)
578 return -1;
579 else if (addr >= entry->address + entry->size)
580 return 1;
581 else
582 return 0;
585 /* Initialize the symbol table info for elf_syminfo. */
587 static int
588 elf_initialize_syminfo (struct backtrace_state *state,
589 uintptr_t base_address,
590 const unsigned char *symtab_data, size_t symtab_size,
591 const unsigned char *strtab, size_t strtab_size,
592 backtrace_error_callback error_callback,
593 void *data, struct elf_syminfo_data *sdata,
594 struct elf_ppc64_opd_data *opd)
596 size_t sym_count;
597 const b_elf_sym *sym;
598 size_t elf_symbol_count;
599 size_t elf_symbol_size;
600 struct elf_symbol *elf_symbols;
601 size_t i;
602 unsigned int j;
604 sym_count = symtab_size / sizeof (b_elf_sym);
606 /* We only care about function symbols. Count them. */
607 sym = (const b_elf_sym *) symtab_data;
608 elf_symbol_count = 0;
609 for (i = 0; i < sym_count; ++i, ++sym)
611 int info;
613 info = sym->st_info & 0xf;
614 if ((info == STT_FUNC || info == STT_OBJECT)
615 && sym->st_shndx != SHN_UNDEF)
616 ++elf_symbol_count;
619 elf_symbol_size = elf_symbol_count * sizeof (struct elf_symbol);
620 elf_symbols = ((struct elf_symbol *)
621 backtrace_alloc (state, elf_symbol_size, error_callback,
622 data));
623 if (elf_symbols == NULL)
624 return 0;
626 sym = (const b_elf_sym *) symtab_data;
627 j = 0;
628 for (i = 0; i < sym_count; ++i, ++sym)
630 int info;
632 info = sym->st_info & 0xf;
633 if (info != STT_FUNC && info != STT_OBJECT)
634 continue;
635 if (sym->st_shndx == SHN_UNDEF)
636 continue;
637 if (sym->st_name >= strtab_size)
639 error_callback (data, "symbol string index out of range", 0);
640 backtrace_free (state, elf_symbols, elf_symbol_size, error_callback,
641 data);
642 return 0;
644 elf_symbols[j].name = (const char *) strtab + sym->st_name;
645 /* Special case PowerPC64 ELFv1 symbols in .opd section, if the symbol
646 is a function descriptor, read the actual code address from the
647 descriptor. */
648 if (opd
649 && sym->st_value >= opd->addr
650 && sym->st_value < opd->addr + opd->size)
651 elf_symbols[j].address
652 = *(const b_elf_addr *) (opd->data + (sym->st_value - opd->addr));
653 else
654 elf_symbols[j].address = sym->st_value;
655 elf_symbols[j].address += base_address;
656 elf_symbols[j].size = sym->st_size;
657 ++j;
660 backtrace_qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
661 elf_symbol_compare);
663 sdata->next = NULL;
664 sdata->symbols = elf_symbols;
665 sdata->count = elf_symbol_count;
667 return 1;
670 /* Add EDATA to the list in STATE. */
672 static void
673 elf_add_syminfo_data (struct backtrace_state *state,
674 struct elf_syminfo_data *edata)
676 if (!state->threaded)
678 struct elf_syminfo_data **pp;
680 for (pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
681 *pp != NULL;
682 pp = &(*pp)->next)
684 *pp = edata;
686 else
688 while (1)
690 struct elf_syminfo_data **pp;
692 pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
694 while (1)
696 struct elf_syminfo_data *p;
698 p = backtrace_atomic_load_pointer (pp);
700 if (p == NULL)
701 break;
703 pp = &p->next;
706 if (__sync_bool_compare_and_swap (pp, NULL, edata))
707 break;
712 /* Return the symbol name and value for an ADDR. */
714 static void
715 elf_syminfo (struct backtrace_state *state, uintptr_t addr,
716 backtrace_syminfo_callback callback,
717 backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
718 void *data)
720 struct elf_syminfo_data *edata;
721 struct elf_symbol *sym = NULL;
723 if (!state->threaded)
725 for (edata = (struct elf_syminfo_data *) state->syminfo_data;
726 edata != NULL;
727 edata = edata->next)
729 sym = ((struct elf_symbol *)
730 bsearch (&addr, edata->symbols, edata->count,
731 sizeof (struct elf_symbol), elf_symbol_search));
732 if (sym != NULL)
733 break;
736 else
738 struct elf_syminfo_data **pp;
740 pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
741 while (1)
743 edata = backtrace_atomic_load_pointer (pp);
744 if (edata == NULL)
745 break;
747 sym = ((struct elf_symbol *)
748 bsearch (&addr, edata->symbols, edata->count,
749 sizeof (struct elf_symbol), elf_symbol_search));
750 if (sym != NULL)
751 break;
753 pp = &edata->next;
757 if (sym == NULL)
758 callback (data, addr, NULL, 0, 0);
759 else
760 callback (data, addr, sym->name, sym->address, sym->size);
763 /* Return whether FILENAME is a symlink. */
765 static int
766 elf_is_symlink (const char *filename)
768 struct stat st;
770 if (lstat (filename, &st) < 0)
771 return 0;
772 return S_ISLNK (st.st_mode);
775 /* Return the results of reading the symlink FILENAME in a buffer
776 allocated by backtrace_alloc. Return the length of the buffer in
777 *LEN. */
779 static char *
780 elf_readlink (struct backtrace_state *state, const char *filename,
781 backtrace_error_callback error_callback, void *data,
782 size_t *plen)
784 size_t len;
785 char *buf;
787 len = 128;
788 while (1)
790 ssize_t rl;
792 buf = backtrace_alloc (state, len, error_callback, data);
793 if (buf == NULL)
794 return NULL;
795 rl = readlink (filename, buf, len);
796 if (rl < 0)
798 backtrace_free (state, buf, len, error_callback, data);
799 return NULL;
801 if ((size_t) rl < len - 1)
803 buf[rl] = '\0';
804 *plen = len;
805 return buf;
807 backtrace_free (state, buf, len, error_callback, data);
808 len *= 2;
812 #define SYSTEM_BUILD_ID_DIR "/usr/lib/debug/.build-id/"
814 /* Open a separate debug info file, using the build ID to find it.
815 Returns an open file descriptor, or -1.
817 The GDB manual says that the only place gdb looks for a debug file
818 when the build ID is known is in /usr/lib/debug/.build-id. */
820 static int
821 elf_open_debugfile_by_buildid (struct backtrace_state *state,
822 const char *buildid_data, size_t buildid_size,
823 backtrace_error_callback error_callback,
824 void *data)
826 const char * const prefix = SYSTEM_BUILD_ID_DIR;
827 const size_t prefix_len = strlen (prefix);
828 const char * const suffix = ".debug";
829 const size_t suffix_len = strlen (suffix);
830 size_t len;
831 char *bd_filename;
832 char *t;
833 size_t i;
834 int ret;
835 int does_not_exist;
837 len = prefix_len + buildid_size * 2 + suffix_len + 2;
838 bd_filename = backtrace_alloc (state, len, error_callback, data);
839 if (bd_filename == NULL)
840 return -1;
842 t = bd_filename;
843 memcpy (t, prefix, prefix_len);
844 t += prefix_len;
845 for (i = 0; i < buildid_size; i++)
847 unsigned char b;
848 unsigned char nib;
850 b = (unsigned char) buildid_data[i];
851 nib = (b & 0xf0) >> 4;
852 *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
853 nib = b & 0x0f;
854 *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
855 if (i == 0)
856 *t++ = '/';
858 memcpy (t, suffix, suffix_len);
859 t[suffix_len] = '\0';
861 ret = backtrace_open (bd_filename, error_callback, data, &does_not_exist);
863 backtrace_free (state, bd_filename, len, error_callback, data);
865 /* gdb checks that the debuginfo file has the same build ID note.
866 That seems kind of pointless to me--why would it have the right
867 name but not the right build ID?--so skipping the check. */
869 return ret;
872 /* Try to open a file whose name is PREFIX (length PREFIX_LEN)
873 concatenated with PREFIX2 (length PREFIX2_LEN) concatenated with
874 DEBUGLINK_NAME. Returns an open file descriptor, or -1. */
876 static int
877 elf_try_debugfile (struct backtrace_state *state, const char *prefix,
878 size_t prefix_len, const char *prefix2, size_t prefix2_len,
879 const char *debuglink_name,
880 backtrace_error_callback error_callback, void *data)
882 size_t debuglink_len;
883 size_t try_len;
884 char *try;
885 int does_not_exist;
886 int ret;
888 debuglink_len = strlen (debuglink_name);
889 try_len = prefix_len + prefix2_len + debuglink_len + 1;
890 try = backtrace_alloc (state, try_len, error_callback, data);
891 if (try == NULL)
892 return -1;
894 memcpy (try, prefix, prefix_len);
895 memcpy (try + prefix_len, prefix2, prefix2_len);
896 memcpy (try + prefix_len + prefix2_len, debuglink_name, debuglink_len);
897 try[prefix_len + prefix2_len + debuglink_len] = '\0';
899 ret = backtrace_open (try, error_callback, data, &does_not_exist);
901 backtrace_free (state, try, try_len, error_callback, data);
903 return ret;
906 /* Find a separate debug info file, using the debuglink section data
907 to find it. Returns an open file descriptor, or -1. */
909 static int
910 elf_find_debugfile_by_debuglink (struct backtrace_state *state,
911 const char *filename,
912 const char *debuglink_name,
913 backtrace_error_callback error_callback,
914 void *data)
916 int ret;
917 char *alc;
918 size_t alc_len;
919 const char *slash;
920 int ddescriptor;
921 const char *prefix;
922 size_t prefix_len;
924 /* Resolve symlinks in FILENAME. Since FILENAME is fairly likely to
925 be /proc/self/exe, symlinks are common. We don't try to resolve
926 the whole path name, just the base name. */
927 ret = -1;
928 alc = NULL;
929 alc_len = 0;
930 while (elf_is_symlink (filename))
932 char *new_buf;
933 size_t new_len;
935 new_buf = elf_readlink (state, filename, error_callback, data, &new_len);
936 if (new_buf == NULL)
937 break;
939 if (new_buf[0] == '/')
940 filename = new_buf;
941 else
943 slash = strrchr (filename, '/');
944 if (slash == NULL)
945 filename = new_buf;
946 else
948 size_t clen;
949 char *c;
951 slash++;
952 clen = slash - filename + strlen (new_buf) + 1;
953 c = backtrace_alloc (state, clen, error_callback, data);
954 if (c == NULL)
955 goto done;
957 memcpy (c, filename, slash - filename);
958 memcpy (c + (slash - filename), new_buf, strlen (new_buf));
959 c[slash - filename + strlen (new_buf)] = '\0';
960 backtrace_free (state, new_buf, new_len, error_callback, data);
961 filename = c;
962 new_buf = c;
963 new_len = clen;
967 if (alc != NULL)
968 backtrace_free (state, alc, alc_len, error_callback, data);
969 alc = new_buf;
970 alc_len = new_len;
973 /* Look for DEBUGLINK_NAME in the same directory as FILENAME. */
975 slash = strrchr (filename, '/');
976 if (slash == NULL)
978 prefix = "";
979 prefix_len = 0;
981 else
983 slash++;
984 prefix = filename;
985 prefix_len = slash - filename;
988 ddescriptor = elf_try_debugfile (state, prefix, prefix_len, "", 0,
989 debuglink_name, error_callback, data);
990 if (ddescriptor >= 0)
992 ret = ddescriptor;
993 goto done;
996 /* Look for DEBUGLINK_NAME in a .debug subdirectory of FILENAME. */
998 ddescriptor = elf_try_debugfile (state, prefix, prefix_len, ".debug/",
999 strlen (".debug/"), debuglink_name,
1000 error_callback, data);
1001 if (ddescriptor >= 0)
1003 ret = ddescriptor;
1004 goto done;
1007 /* Look for DEBUGLINK_NAME in /usr/lib/debug. */
1009 ddescriptor = elf_try_debugfile (state, "/usr/lib/debug/",
1010 strlen ("/usr/lib/debug/"), prefix,
1011 prefix_len, debuglink_name,
1012 error_callback, data);
1013 if (ddescriptor >= 0)
1014 ret = ddescriptor;
1016 done:
1017 if (alc != NULL && alc_len > 0)
1018 backtrace_free (state, alc, alc_len, error_callback, data);
1019 return ret;
1022 /* Open a separate debug info file, using the debuglink section data
1023 to find it. Returns an open file descriptor, or -1. */
1025 static int
1026 elf_open_debugfile_by_debuglink (struct backtrace_state *state,
1027 const char *filename,
1028 const char *debuglink_name,
1029 uint32_t debuglink_crc,
1030 backtrace_error_callback error_callback,
1031 void *data)
1033 int ddescriptor;
1035 ddescriptor = elf_find_debugfile_by_debuglink (state, filename,
1036 debuglink_name,
1037 error_callback, data);
1038 if (ddescriptor < 0)
1039 return -1;
1041 if (debuglink_crc != 0)
1043 uint32_t got_crc;
1045 got_crc = elf_crc32_file (state, ddescriptor, error_callback, data);
1046 if (got_crc != debuglink_crc)
1048 backtrace_close (ddescriptor, error_callback, data);
1049 return -1;
1053 return ddescriptor;
1056 /* A function useful for setting a breakpoint for an inflation failure
1057 when this code is compiled with -g. */
1059 static void
1060 elf_zlib_failed(void)
1064 /* *PVAL is the current value being read from the stream, and *PBITS
1065 is the number of valid bits. Ensure that *PVAL holds at least 15
1066 bits by reading additional bits from *PPIN, up to PINEND, as
1067 needed. Updates *PPIN, *PVAL and *PBITS. Returns 1 on success, 0
1068 on error. */
1070 static int
1071 elf_zlib_fetch (const unsigned char **ppin, const unsigned char *pinend,
1072 uint64_t *pval, unsigned int *pbits)
1074 unsigned int bits;
1075 const unsigned char *pin;
1076 uint64_t val;
1077 uint32_t next;
1079 bits = *pbits;
1080 if (bits >= 15)
1081 return 1;
1082 pin = *ppin;
1083 val = *pval;
1085 if (unlikely (pinend - pin < 4))
1087 elf_zlib_failed ();
1088 return 0;
1091 #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) \
1092 && defined(__ORDER_BIG_ENDIAN__) \
1093 && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ \
1094 || __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1095 /* We've ensured that PIN is aligned. */
1096 next = *(const uint32_t *)pin;
1098 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
1099 next = __builtin_bswap32 (next);
1100 #endif
1101 #else
1102 next = pin[0] | (pin[1] << 8) | (pin[2] << 16) | (pin[3] << 24);
1103 #endif
1105 val |= (uint64_t)next << bits;
1106 bits += 32;
1107 pin += 4;
1109 /* We will need the next four bytes soon. */
1110 __builtin_prefetch (pin, 0, 0);
1112 *ppin = pin;
1113 *pval = val;
1114 *pbits = bits;
1115 return 1;
1118 /* Huffman code tables, like the rest of the zlib format, are defined
1119 by RFC 1951. We store a Huffman code table as a series of tables
1120 stored sequentially in memory. Each entry in a table is 16 bits.
1121 The first, main, table has 256 entries. It is followed by a set of
1122 secondary tables of length 2 to 128 entries. The maximum length of
1123 a code sequence in the deflate format is 15 bits, so that is all we
1124 need. Each secondary table has an index, which is the offset of
1125 the table in the overall memory storage.
1127 The deflate format says that all codes of a given bit length are
1128 lexicographically consecutive. Perhaps we could have 130 values
1129 that require a 15-bit code, perhaps requiring three secondary
1130 tables of size 128. I don't know if this is actually possible, but
1131 it suggests that the maximum size required for secondary tables is
1132 3 * 128 + 3 * 64 ... == 768. The zlib enough program reports 660
1133 as the maximum. We permit 768, since in addition to the 256 for
1134 the primary table, with two bytes per entry, and with the two
1135 tables we need, that gives us a page.
1137 A single table entry needs to store a value or (for the main table
1138 only) the index and size of a secondary table. Values range from 0
1139 to 285, inclusive. Secondary table indexes, per above, range from
1140 0 to 510. For a value we need to store the number of bits we need
1141 to determine that value (one value may appear multiple times in the
1142 table), which is 1 to 8. For a secondary table we need to store
1143 the number of bits used to index into the table, which is 1 to 7.
1144 And of course we need 1 bit to decide whether we have a value or a
1145 secondary table index. So each entry needs 9 bits for value/table
1146 index, 3 bits for size, 1 bit what it is. For simplicity we use 16
1147 bits per entry. */
1149 /* Number of entries we allocate to for one code table. We get a page
1150 for the two code tables we need. */
1152 #define HUFFMAN_TABLE_SIZE (1024)
1154 /* Bit masks and shifts for the values in the table. */
1156 #define HUFFMAN_VALUE_MASK 0x01ff
1157 #define HUFFMAN_BITS_SHIFT 9
1158 #define HUFFMAN_BITS_MASK 0x7
1159 #define HUFFMAN_SECONDARY_SHIFT 12
1161 /* For working memory while inflating we need two code tables, we need
1162 an array of code lengths (max value 15, so we use unsigned char),
1163 and an array of unsigned shorts used while building a table. The
1164 latter two arrays must be large enough to hold the maximum number
1165 of code lengths, which RFC 1951 defines as 286 + 30. */
1167 #define ZDEBUG_TABLE_SIZE \
1168 (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1169 + (286 + 30) * sizeof (uint16_t) \
1170 + (286 + 30) * sizeof (unsigned char))
1172 #define ZDEBUG_TABLE_CODELEN_OFFSET \
1173 (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1174 + (286 + 30) * sizeof (uint16_t))
1176 #define ZDEBUG_TABLE_WORK_OFFSET \
1177 (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t))
1179 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1181 /* Used by the main function that generates the fixed table to learn
1182 the table size. */
1183 static size_t final_next_secondary;
1185 #endif
1187 /* Build a Huffman code table from an array of lengths in CODES of
1188 length CODES_LEN. The table is stored into *TABLE. ZDEBUG_TABLE
1189 is the same as for elf_zlib_inflate, used to find some work space.
1190 Returns 1 on success, 0 on error. */
1192 static int
1193 elf_zlib_inflate_table (unsigned char *codes, size_t codes_len,
1194 uint16_t *zdebug_table, uint16_t *table)
1196 uint16_t count[16];
1197 uint16_t start[16];
1198 uint16_t prev[16];
1199 uint16_t firstcode[7];
1200 uint16_t *next;
1201 size_t i;
1202 size_t j;
1203 unsigned int code;
1204 size_t next_secondary;
1206 /* Count the number of code of each length. Set NEXT[val] to be the
1207 next value after VAL with the same bit length. */
1209 next = (uint16_t *) (((unsigned char *) zdebug_table)
1210 + ZDEBUG_TABLE_WORK_OFFSET);
1212 memset (&count[0], 0, 16 * sizeof (uint16_t));
1213 for (i = 0; i < codes_len; ++i)
1215 if (unlikely (codes[i] >= 16))
1217 elf_zlib_failed ();
1218 return 0;
1221 if (count[codes[i]] == 0)
1223 start[codes[i]] = i;
1224 prev[codes[i]] = i;
1226 else
1228 next[prev[codes[i]]] = i;
1229 prev[codes[i]] = i;
1232 ++count[codes[i]];
1235 /* For each length, fill in the table for the codes of that
1236 length. */
1238 memset (table, 0, HUFFMAN_TABLE_SIZE * sizeof (uint16_t));
1240 /* Handle the values that do not require a secondary table. */
1242 code = 0;
1243 for (j = 1; j <= 8; ++j)
1245 unsigned int jcnt;
1246 unsigned int val;
1248 jcnt = count[j];
1249 if (jcnt == 0)
1250 continue;
1252 if (unlikely (jcnt > (1U << j)))
1254 elf_zlib_failed ();
1255 return 0;
1258 /* There are JCNT values that have this length, the values
1259 starting from START[j] continuing through NEXT[VAL]. Those
1260 values are assigned consecutive values starting at CODE. */
1262 val = start[j];
1263 for (i = 0; i < jcnt; ++i)
1265 uint16_t tval;
1266 size_t ind;
1267 unsigned int incr;
1269 /* In the compressed bit stream, the value VAL is encoded as
1270 J bits with the value C. */
1272 if (unlikely ((val & ~HUFFMAN_VALUE_MASK) != 0))
1274 elf_zlib_failed ();
1275 return 0;
1278 tval = val | ((j - 1) << HUFFMAN_BITS_SHIFT);
1280 /* The table lookup uses 8 bits. If J is less than 8, we
1281 don't know what the other bits will be. We need to fill
1282 in all possibilities in the table. Since the Huffman
1283 code is unambiguous, those entries can't be used for any
1284 other code. */
1286 for (ind = code; ind < 0x100; ind += 1 << j)
1288 if (unlikely (table[ind] != 0))
1290 elf_zlib_failed ();
1291 return 0;
1293 table[ind] = tval;
1296 /* Advance to the next value with this length. */
1297 if (i + 1 < jcnt)
1298 val = next[val];
1300 /* The Huffman codes are stored in the bitstream with the
1301 most significant bit first, as is required to make them
1302 unambiguous. The effect is that when we read them from
1303 the bitstream we see the bit sequence in reverse order:
1304 the most significant bit of the Huffman code is the least
1305 significant bit of the value we read from the bitstream.
1306 That means that to make our table lookups work, we need
1307 to reverse the bits of CODE. Since reversing bits is
1308 tedious and in general requires using a table, we instead
1309 increment CODE in reverse order. That is, if the number
1310 of bits we are currently using, here named J, is 3, we
1311 count as 000, 100, 010, 110, 001, 101, 011, 111, which is
1312 to say the numbers from 0 to 7 but with the bits
1313 reversed. Going to more bits, aka incrementing J,
1314 effectively just adds more zero bits as the beginning,
1315 and as such does not change the numeric value of CODE.
1317 To increment CODE of length J in reverse order, find the
1318 most significant zero bit and set it to one while
1319 clearing all higher bits. In other words, add 1 modulo
1320 2^J, only reversed. */
1322 incr = 1U << (j - 1);
1323 while ((code & incr) != 0)
1324 incr >>= 1;
1325 if (incr == 0)
1326 code = 0;
1327 else
1329 code &= incr - 1;
1330 code += incr;
1335 /* Handle the values that require a secondary table. */
1337 /* Set FIRSTCODE, the number at which the codes start, for each
1338 length. */
1340 for (j = 9; j < 16; j++)
1342 unsigned int jcnt;
1343 unsigned int k;
1345 jcnt = count[j];
1346 if (jcnt == 0)
1347 continue;
1349 /* There are JCNT values that have this length, the values
1350 starting from START[j]. Those values are assigned
1351 consecutive values starting at CODE. */
1353 firstcode[j - 9] = code;
1355 /* Reverse add JCNT to CODE modulo 2^J. */
1356 for (k = 0; k < j; ++k)
1358 if ((jcnt & (1U << k)) != 0)
1360 unsigned int m;
1361 unsigned int bit;
1363 bit = 1U << (j - k - 1);
1364 for (m = 0; m < j - k; ++m, bit >>= 1)
1366 if ((code & bit) == 0)
1368 code += bit;
1369 break;
1371 code &= ~bit;
1373 jcnt &= ~(1U << k);
1376 if (unlikely (jcnt != 0))
1378 elf_zlib_failed ();
1379 return 0;
1383 /* For J from 9 to 15, inclusive, we store COUNT[J] consecutive
1384 values starting at START[J] with consecutive codes starting at
1385 FIRSTCODE[J - 9]. In the primary table we need to point to the
1386 secondary table, and the secondary table will be indexed by J - 9
1387 bits. We count down from 15 so that we install the larger
1388 secondary tables first, as the smaller ones may be embedded in
1389 the larger ones. */
1391 next_secondary = 0; /* Index of next secondary table (after primary). */
1392 for (j = 15; j >= 9; j--)
1394 unsigned int jcnt;
1395 unsigned int val;
1396 size_t primary; /* Current primary index. */
1397 size_t secondary; /* Offset to current secondary table. */
1398 size_t secondary_bits; /* Bit size of current secondary table. */
1400 jcnt = count[j];
1401 if (jcnt == 0)
1402 continue;
1404 val = start[j];
1405 code = firstcode[j - 9];
1406 primary = 0x100;
1407 secondary = 0;
1408 secondary_bits = 0;
1409 for (i = 0; i < jcnt; ++i)
1411 uint16_t tval;
1412 size_t ind;
1413 unsigned int incr;
1415 if ((code & 0xff) != primary)
1417 uint16_t tprimary;
1419 /* Fill in a new primary table entry. */
1421 primary = code & 0xff;
1423 tprimary = table[primary];
1424 if (tprimary == 0)
1426 /* Start a new secondary table. */
1428 if (unlikely ((next_secondary & HUFFMAN_VALUE_MASK)
1429 != next_secondary))
1431 elf_zlib_failed ();
1432 return 0;
1435 secondary = next_secondary;
1436 secondary_bits = j - 8;
1437 next_secondary += 1 << secondary_bits;
1438 table[primary] = (secondary
1439 + ((j - 8) << HUFFMAN_BITS_SHIFT)
1440 + (1U << HUFFMAN_SECONDARY_SHIFT));
1442 else
1444 /* There is an existing entry. It had better be a
1445 secondary table with enough bits. */
1446 if (unlikely ((tprimary & (1U << HUFFMAN_SECONDARY_SHIFT))
1447 == 0))
1449 elf_zlib_failed ();
1450 return 0;
1452 secondary = tprimary & HUFFMAN_VALUE_MASK;
1453 secondary_bits = ((tprimary >> HUFFMAN_BITS_SHIFT)
1454 & HUFFMAN_BITS_MASK);
1455 if (unlikely (secondary_bits < j - 8))
1457 elf_zlib_failed ();
1458 return 0;
1463 /* Fill in secondary table entries. */
1465 tval = val | ((j - 8) << HUFFMAN_BITS_SHIFT);
1467 for (ind = code >> 8;
1468 ind < (1U << secondary_bits);
1469 ind += 1U << (j - 8))
1471 if (unlikely (table[secondary + 0x100 + ind] != 0))
1473 elf_zlib_failed ();
1474 return 0;
1476 table[secondary + 0x100 + ind] = tval;
1479 if (i + 1 < jcnt)
1480 val = next[val];
1482 incr = 1U << (j - 1);
1483 while ((code & incr) != 0)
1484 incr >>= 1;
1485 if (incr == 0)
1486 code = 0;
1487 else
1489 code &= incr - 1;
1490 code += incr;
1495 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1496 final_next_secondary = next_secondary;
1497 #endif
1499 return 1;
1502 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1504 /* Used to generate the fixed Huffman table for block type 1. */
1506 #include <stdio.h>
1508 static uint16_t table[ZDEBUG_TABLE_SIZE];
1509 static unsigned char codes[288];
1512 main ()
1514 size_t i;
1516 for (i = 0; i <= 143; ++i)
1517 codes[i] = 8;
1518 for (i = 144; i <= 255; ++i)
1519 codes[i] = 9;
1520 for (i = 256; i <= 279; ++i)
1521 codes[i] = 7;
1522 for (i = 280; i <= 287; ++i)
1523 codes[i] = 8;
1524 if (!elf_zlib_inflate_table (&codes[0], 288, &table[0], &table[0]))
1526 fprintf (stderr, "elf_zlib_inflate_table failed\n");
1527 exit (EXIT_FAILURE);
1530 printf ("static const uint16_t elf_zlib_default_table[%#zx] =\n",
1531 final_next_secondary + 0x100);
1532 printf ("{\n");
1533 for (i = 0; i < final_next_secondary + 0x100; i += 8)
1535 size_t j;
1537 printf (" ");
1538 for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1539 printf (" %#x,", table[j]);
1540 printf ("\n");
1542 printf ("};\n");
1543 printf ("\n");
1545 for (i = 0; i < 32; ++i)
1546 codes[i] = 5;
1547 if (!elf_zlib_inflate_table (&codes[0], 32, &table[0], &table[0]))
1549 fprintf (stderr, "elf_zlib_inflate_table failed\n");
1550 exit (EXIT_FAILURE);
1553 printf ("static const uint16_t elf_zlib_default_dist_table[%#zx] =\n",
1554 final_next_secondary + 0x100);
1555 printf ("{\n");
1556 for (i = 0; i < final_next_secondary + 0x100; i += 8)
1558 size_t j;
1560 printf (" ");
1561 for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1562 printf (" %#x,", table[j]);
1563 printf ("\n");
1565 printf ("};\n");
1567 return 0;
1570 #endif
1572 /* The fixed tables generated by the #ifdef'ed out main function
1573 above. */
1575 static const uint16_t elf_zlib_default_table[0x170] =
1577 0xd00, 0xe50, 0xe10, 0xf18, 0xd10, 0xe70, 0xe30, 0x1230,
1578 0xd08, 0xe60, 0xe20, 0x1210, 0xe00, 0xe80, 0xe40, 0x1250,
1579 0xd04, 0xe58, 0xe18, 0x1200, 0xd14, 0xe78, 0xe38, 0x1240,
1580 0xd0c, 0xe68, 0xe28, 0x1220, 0xe08, 0xe88, 0xe48, 0x1260,
1581 0xd02, 0xe54, 0xe14, 0xf1c, 0xd12, 0xe74, 0xe34, 0x1238,
1582 0xd0a, 0xe64, 0xe24, 0x1218, 0xe04, 0xe84, 0xe44, 0x1258,
1583 0xd06, 0xe5c, 0xe1c, 0x1208, 0xd16, 0xe7c, 0xe3c, 0x1248,
1584 0xd0e, 0xe6c, 0xe2c, 0x1228, 0xe0c, 0xe8c, 0xe4c, 0x1268,
1585 0xd01, 0xe52, 0xe12, 0xf1a, 0xd11, 0xe72, 0xe32, 0x1234,
1586 0xd09, 0xe62, 0xe22, 0x1214, 0xe02, 0xe82, 0xe42, 0x1254,
1587 0xd05, 0xe5a, 0xe1a, 0x1204, 0xd15, 0xe7a, 0xe3a, 0x1244,
1588 0xd0d, 0xe6a, 0xe2a, 0x1224, 0xe0a, 0xe8a, 0xe4a, 0x1264,
1589 0xd03, 0xe56, 0xe16, 0xf1e, 0xd13, 0xe76, 0xe36, 0x123c,
1590 0xd0b, 0xe66, 0xe26, 0x121c, 0xe06, 0xe86, 0xe46, 0x125c,
1591 0xd07, 0xe5e, 0xe1e, 0x120c, 0xd17, 0xe7e, 0xe3e, 0x124c,
1592 0xd0f, 0xe6e, 0xe2e, 0x122c, 0xe0e, 0xe8e, 0xe4e, 0x126c,
1593 0xd00, 0xe51, 0xe11, 0xf19, 0xd10, 0xe71, 0xe31, 0x1232,
1594 0xd08, 0xe61, 0xe21, 0x1212, 0xe01, 0xe81, 0xe41, 0x1252,
1595 0xd04, 0xe59, 0xe19, 0x1202, 0xd14, 0xe79, 0xe39, 0x1242,
1596 0xd0c, 0xe69, 0xe29, 0x1222, 0xe09, 0xe89, 0xe49, 0x1262,
1597 0xd02, 0xe55, 0xe15, 0xf1d, 0xd12, 0xe75, 0xe35, 0x123a,
1598 0xd0a, 0xe65, 0xe25, 0x121a, 0xe05, 0xe85, 0xe45, 0x125a,
1599 0xd06, 0xe5d, 0xe1d, 0x120a, 0xd16, 0xe7d, 0xe3d, 0x124a,
1600 0xd0e, 0xe6d, 0xe2d, 0x122a, 0xe0d, 0xe8d, 0xe4d, 0x126a,
1601 0xd01, 0xe53, 0xe13, 0xf1b, 0xd11, 0xe73, 0xe33, 0x1236,
1602 0xd09, 0xe63, 0xe23, 0x1216, 0xe03, 0xe83, 0xe43, 0x1256,
1603 0xd05, 0xe5b, 0xe1b, 0x1206, 0xd15, 0xe7b, 0xe3b, 0x1246,
1604 0xd0d, 0xe6b, 0xe2b, 0x1226, 0xe0b, 0xe8b, 0xe4b, 0x1266,
1605 0xd03, 0xe57, 0xe17, 0xf1f, 0xd13, 0xe77, 0xe37, 0x123e,
1606 0xd0b, 0xe67, 0xe27, 0x121e, 0xe07, 0xe87, 0xe47, 0x125e,
1607 0xd07, 0xe5f, 0xe1f, 0x120e, 0xd17, 0xe7f, 0xe3f, 0x124e,
1608 0xd0f, 0xe6f, 0xe2f, 0x122e, 0xe0f, 0xe8f, 0xe4f, 0x126e,
1609 0x290, 0x291, 0x292, 0x293, 0x294, 0x295, 0x296, 0x297,
1610 0x298, 0x299, 0x29a, 0x29b, 0x29c, 0x29d, 0x29e, 0x29f,
1611 0x2a0, 0x2a1, 0x2a2, 0x2a3, 0x2a4, 0x2a5, 0x2a6, 0x2a7,
1612 0x2a8, 0x2a9, 0x2aa, 0x2ab, 0x2ac, 0x2ad, 0x2ae, 0x2af,
1613 0x2b0, 0x2b1, 0x2b2, 0x2b3, 0x2b4, 0x2b5, 0x2b6, 0x2b7,
1614 0x2b8, 0x2b9, 0x2ba, 0x2bb, 0x2bc, 0x2bd, 0x2be, 0x2bf,
1615 0x2c0, 0x2c1, 0x2c2, 0x2c3, 0x2c4, 0x2c5, 0x2c6, 0x2c7,
1616 0x2c8, 0x2c9, 0x2ca, 0x2cb, 0x2cc, 0x2cd, 0x2ce, 0x2cf,
1617 0x2d0, 0x2d1, 0x2d2, 0x2d3, 0x2d4, 0x2d5, 0x2d6, 0x2d7,
1618 0x2d8, 0x2d9, 0x2da, 0x2db, 0x2dc, 0x2dd, 0x2de, 0x2df,
1619 0x2e0, 0x2e1, 0x2e2, 0x2e3, 0x2e4, 0x2e5, 0x2e6, 0x2e7,
1620 0x2e8, 0x2e9, 0x2ea, 0x2eb, 0x2ec, 0x2ed, 0x2ee, 0x2ef,
1621 0x2f0, 0x2f1, 0x2f2, 0x2f3, 0x2f4, 0x2f5, 0x2f6, 0x2f7,
1622 0x2f8, 0x2f9, 0x2fa, 0x2fb, 0x2fc, 0x2fd, 0x2fe, 0x2ff,
1625 static const uint16_t elf_zlib_default_dist_table[0x100] =
1627 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1628 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1629 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1630 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1631 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1632 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1633 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1634 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1635 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1636 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1637 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1638 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1639 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1640 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1641 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1642 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1643 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1644 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1645 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1646 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1647 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1648 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1649 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1650 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1651 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1652 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1653 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1654 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1655 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1656 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1657 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1658 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1661 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT. Return 1 on
1662 success, 0 on some error parsing the stream. */
1664 static int
1665 elf_zlib_inflate (const unsigned char *pin, size_t sin, uint16_t *zdebug_table,
1666 unsigned char *pout, size_t sout)
1668 unsigned char *porigout;
1669 const unsigned char *pinend;
1670 unsigned char *poutend;
1672 /* We can apparently see multiple zlib streams concatenated
1673 together, so keep going as long as there is something to read.
1674 The last 4 bytes are the checksum. */
1675 porigout = pout;
1676 pinend = pin + sin;
1677 poutend = pout + sout;
1678 while ((pinend - pin) > 4)
1680 uint64_t val;
1681 unsigned int bits;
1682 int last;
1684 /* Read the two byte zlib header. */
1686 if (unlikely ((pin[0] & 0xf) != 8)) /* 8 is zlib encoding. */
1688 /* Unknown compression method. */
1689 elf_zlib_failed ();
1690 return 0;
1692 if (unlikely ((pin[0] >> 4) > 7))
1694 /* Window size too large. Other than this check, we don't
1695 care about the window size. */
1696 elf_zlib_failed ();
1697 return 0;
1699 if (unlikely ((pin[1] & 0x20) != 0))
1701 /* Stream expects a predefined dictionary, but we have no
1702 dictionary. */
1703 elf_zlib_failed ();
1704 return 0;
1706 val = (pin[0] << 8) | pin[1];
1707 if (unlikely (val % 31 != 0))
1709 /* Header check failure. */
1710 elf_zlib_failed ();
1711 return 0;
1713 pin += 2;
1715 /* Align PIN to a 32-bit boundary. */
1717 val = 0;
1718 bits = 0;
1719 while ((((uintptr_t) pin) & 3) != 0)
1721 val |= (uint64_t)*pin << bits;
1722 bits += 8;
1723 ++pin;
1726 /* Read blocks until one is marked last. */
1728 last = 0;
1730 while (!last)
1732 unsigned int type;
1733 const uint16_t *tlit;
1734 const uint16_t *tdist;
1736 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1737 return 0;
1739 last = val & 1;
1740 type = (val >> 1) & 3;
1741 val >>= 3;
1742 bits -= 3;
1744 if (unlikely (type == 3))
1746 /* Invalid block type. */
1747 elf_zlib_failed ();
1748 return 0;
1751 if (type == 0)
1753 uint16_t len;
1754 uint16_t lenc;
1756 /* An uncompressed block. */
1758 /* If we've read ahead more than a byte, back up. */
1759 while (bits > 8)
1761 --pin;
1762 bits -= 8;
1765 val = 0;
1766 bits = 0;
1767 if (unlikely ((pinend - pin) < 4))
1769 /* Missing length. */
1770 elf_zlib_failed ();
1771 return 0;
1773 len = pin[0] | (pin[1] << 8);
1774 lenc = pin[2] | (pin[3] << 8);
1775 pin += 4;
1776 lenc = ~lenc;
1777 if (unlikely (len != lenc))
1779 /* Corrupt data. */
1780 elf_zlib_failed ();
1781 return 0;
1783 if (unlikely (len > (unsigned int) (pinend - pin)
1784 || len > (unsigned int) (poutend - pout)))
1786 /* Not enough space in buffers. */
1787 elf_zlib_failed ();
1788 return 0;
1790 memcpy (pout, pin, len);
1791 pout += len;
1792 pin += len;
1794 /* Align PIN. */
1795 while ((((uintptr_t) pin) & 3) != 0)
1797 val |= (uint64_t)*pin << bits;
1798 bits += 8;
1799 ++pin;
1802 /* Go around to read the next block. */
1803 continue;
1806 if (type == 1)
1808 tlit = elf_zlib_default_table;
1809 tdist = elf_zlib_default_dist_table;
1811 else
1813 unsigned int nlit;
1814 unsigned int ndist;
1815 unsigned int nclen;
1816 unsigned char codebits[19];
1817 unsigned char *plenbase;
1818 unsigned char *plen;
1819 unsigned char *plenend;
1821 /* Read a Huffman encoding table. The various magic
1822 numbers here are from RFC 1951. */
1824 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1825 return 0;
1827 nlit = (val & 0x1f) + 257;
1828 val >>= 5;
1829 ndist = (val & 0x1f) + 1;
1830 val >>= 5;
1831 nclen = (val & 0xf) + 4;
1832 val >>= 4;
1833 bits -= 14;
1834 if (unlikely (nlit > 286 || ndist > 30))
1836 /* Values out of range. */
1837 elf_zlib_failed ();
1838 return 0;
1841 /* Read and build the table used to compress the
1842 literal, length, and distance codes. */
1844 memset(&codebits[0], 0, 19);
1846 /* There are always at least 4 elements in the
1847 table. */
1849 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1850 return 0;
1852 codebits[16] = val & 7;
1853 codebits[17] = (val >> 3) & 7;
1854 codebits[18] = (val >> 6) & 7;
1855 codebits[0] = (val >> 9) & 7;
1856 val >>= 12;
1857 bits -= 12;
1859 if (nclen == 4)
1860 goto codebitsdone;
1862 codebits[8] = val & 7;
1863 val >>= 3;
1864 bits -= 3;
1866 if (nclen == 5)
1867 goto codebitsdone;
1869 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1870 return 0;
1872 codebits[7] = val & 7;
1873 val >>= 3;
1874 bits -= 3;
1876 if (nclen == 6)
1877 goto codebitsdone;
1879 codebits[9] = val & 7;
1880 val >>= 3;
1881 bits -= 3;
1883 if (nclen == 7)
1884 goto codebitsdone;
1886 codebits[6] = val & 7;
1887 val >>= 3;
1888 bits -= 3;
1890 if (nclen == 8)
1891 goto codebitsdone;
1893 codebits[10] = val & 7;
1894 val >>= 3;
1895 bits -= 3;
1897 if (nclen == 9)
1898 goto codebitsdone;
1900 codebits[5] = val & 7;
1901 val >>= 3;
1902 bits -= 3;
1904 if (nclen == 10)
1905 goto codebitsdone;
1907 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1908 return 0;
1910 codebits[11] = val & 7;
1911 val >>= 3;
1912 bits -= 3;
1914 if (nclen == 11)
1915 goto codebitsdone;
1917 codebits[4] = val & 7;
1918 val >>= 3;
1919 bits -= 3;
1921 if (nclen == 12)
1922 goto codebitsdone;
1924 codebits[12] = val & 7;
1925 val >>= 3;
1926 bits -= 3;
1928 if (nclen == 13)
1929 goto codebitsdone;
1931 codebits[3] = val & 7;
1932 val >>= 3;
1933 bits -= 3;
1935 if (nclen == 14)
1936 goto codebitsdone;
1938 codebits[13] = val & 7;
1939 val >>= 3;
1940 bits -= 3;
1942 if (nclen == 15)
1943 goto codebitsdone;
1945 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1946 return 0;
1948 codebits[2] = val & 7;
1949 val >>= 3;
1950 bits -= 3;
1952 if (nclen == 16)
1953 goto codebitsdone;
1955 codebits[14] = val & 7;
1956 val >>= 3;
1957 bits -= 3;
1959 if (nclen == 17)
1960 goto codebitsdone;
1962 codebits[1] = val & 7;
1963 val >>= 3;
1964 bits -= 3;
1966 if (nclen == 18)
1967 goto codebitsdone;
1969 codebits[15] = val & 7;
1970 val >>= 3;
1971 bits -= 3;
1973 codebitsdone:
1975 if (!elf_zlib_inflate_table (codebits, 19, zdebug_table,
1976 zdebug_table))
1977 return 0;
1979 /* Read the compressed bit lengths of the literal,
1980 length, and distance codes. We have allocated space
1981 at the end of zdebug_table to hold them. */
1983 plenbase = (((unsigned char *) zdebug_table)
1984 + ZDEBUG_TABLE_CODELEN_OFFSET);
1985 plen = plenbase;
1986 plenend = plen + nlit + ndist;
1987 while (plen < plenend)
1989 uint16_t t;
1990 unsigned int b;
1991 uint16_t v;
1993 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1994 return 0;
1996 t = zdebug_table[val & 0xff];
1998 /* The compression here uses bit lengths up to 7, so
1999 a secondary table is never necessary. */
2000 if (unlikely ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) != 0))
2002 elf_zlib_failed ();
2003 return 0;
2006 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2007 val >>= b + 1;
2008 bits -= b + 1;
2010 v = t & HUFFMAN_VALUE_MASK;
2011 if (v < 16)
2012 *plen++ = v;
2013 else if (v == 16)
2015 unsigned int c;
2016 unsigned int prev;
2018 /* Copy previous entry 3 to 6 times. */
2020 if (unlikely (plen == plenbase))
2022 elf_zlib_failed ();
2023 return 0;
2026 /* We used up to 7 bits since the last
2027 elf_zlib_fetch, so we have at least 8 bits
2028 available here. */
2030 c = 3 + (val & 0x3);
2031 val >>= 2;
2032 bits -= 2;
2033 if (unlikely ((unsigned int) (plenend - plen) < c))
2035 elf_zlib_failed ();
2036 return 0;
2039 prev = plen[-1];
2040 switch (c)
2042 case 6:
2043 *plen++ = prev;
2044 /* fallthrough */
2045 case 5:
2046 *plen++ = prev;
2047 /* fallthrough */
2048 case 4:
2049 *plen++ = prev;
2051 *plen++ = prev;
2052 *plen++ = prev;
2053 *plen++ = prev;
2055 else if (v == 17)
2057 unsigned int c;
2059 /* Store zero 3 to 10 times. */
2061 /* We used up to 7 bits since the last
2062 elf_zlib_fetch, so we have at least 8 bits
2063 available here. */
2065 c = 3 + (val & 0x7);
2066 val >>= 3;
2067 bits -= 3;
2068 if (unlikely ((unsigned int) (plenend - plen) < c))
2070 elf_zlib_failed ();
2071 return 0;
2074 switch (c)
2076 case 10:
2077 *plen++ = 0;
2078 /* fallthrough */
2079 case 9:
2080 *plen++ = 0;
2081 /* fallthrough */
2082 case 8:
2083 *plen++ = 0;
2084 /* fallthrough */
2085 case 7:
2086 *plen++ = 0;
2087 /* fallthrough */
2088 case 6:
2089 *plen++ = 0;
2090 /* fallthrough */
2091 case 5:
2092 *plen++ = 0;
2093 /* fallthrough */
2094 case 4:
2095 *plen++ = 0;
2097 *plen++ = 0;
2098 *plen++ = 0;
2099 *plen++ = 0;
2101 else if (v == 18)
2103 unsigned int c;
2105 /* Store zero 11 to 138 times. */
2107 /* We used up to 7 bits since the last
2108 elf_zlib_fetch, so we have at least 8 bits
2109 available here. */
2111 c = 11 + (val & 0x7f);
2112 val >>= 7;
2113 bits -= 7;
2114 if (unlikely ((unsigned int) (plenend - plen) < c))
2116 elf_zlib_failed ();
2117 return 0;
2120 memset (plen, 0, c);
2121 plen += c;
2123 else
2125 elf_zlib_failed ();
2126 return 0;
2130 /* Make sure that the stop code can appear. */
2132 plen = plenbase;
2133 if (unlikely (plen[256] == 0))
2135 elf_zlib_failed ();
2136 return 0;
2139 /* Build the decompression tables. */
2141 if (!elf_zlib_inflate_table (plen, nlit, zdebug_table,
2142 zdebug_table))
2143 return 0;
2144 if (!elf_zlib_inflate_table (plen + nlit, ndist, zdebug_table,
2145 zdebug_table + HUFFMAN_TABLE_SIZE))
2146 return 0;
2147 tlit = zdebug_table;
2148 tdist = zdebug_table + HUFFMAN_TABLE_SIZE;
2151 /* Inflate values until the end of the block. This is the
2152 main loop of the inflation code. */
2154 while (1)
2156 uint16_t t;
2157 unsigned int b;
2158 uint16_t v;
2159 unsigned int lit;
2161 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2162 return 0;
2164 t = tlit[val & 0xff];
2165 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2166 v = t & HUFFMAN_VALUE_MASK;
2168 if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2170 lit = v;
2171 val >>= b + 1;
2172 bits -= b + 1;
2174 else
2176 t = tlit[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2177 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2178 lit = t & HUFFMAN_VALUE_MASK;
2179 val >>= b + 8;
2180 bits -= b + 8;
2183 if (lit < 256)
2185 if (unlikely (pout == poutend))
2187 elf_zlib_failed ();
2188 return 0;
2191 *pout++ = lit;
2193 /* We will need to write the next byte soon. We ask
2194 for high temporal locality because we will write
2195 to the whole cache line soon. */
2196 __builtin_prefetch (pout, 1, 3);
2198 else if (lit == 256)
2200 /* The end of the block. */
2201 break;
2203 else
2205 unsigned int dist;
2206 unsigned int len;
2208 /* Convert lit into a length. */
2210 if (lit < 265)
2211 len = lit - 257 + 3;
2212 else if (lit == 285)
2213 len = 258;
2214 else if (unlikely (lit > 285))
2216 elf_zlib_failed ();
2217 return 0;
2219 else
2221 unsigned int extra;
2223 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2224 return 0;
2226 /* This is an expression for the table of length
2227 codes in RFC 1951 3.2.5. */
2228 lit -= 265;
2229 extra = (lit >> 2) + 1;
2230 len = (lit & 3) << extra;
2231 len += 11;
2232 len += ((1U << (extra - 1)) - 1) << 3;
2233 len += val & ((1U << extra) - 1);
2234 val >>= extra;
2235 bits -= extra;
2238 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2239 return 0;
2241 t = tdist[val & 0xff];
2242 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2243 v = t & HUFFMAN_VALUE_MASK;
2245 if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2247 dist = v;
2248 val >>= b + 1;
2249 bits -= b + 1;
2251 else
2253 t = tdist[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2254 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2255 dist = t & HUFFMAN_VALUE_MASK;
2256 val >>= b + 8;
2257 bits -= b + 8;
2260 /* Convert dist to a distance. */
2262 if (dist == 0)
2264 /* A distance of 1. A common case, meaning
2265 repeat the last character LEN times. */
2267 if (unlikely (pout == porigout))
2269 elf_zlib_failed ();
2270 return 0;
2273 if (unlikely ((unsigned int) (poutend - pout) < len))
2275 elf_zlib_failed ();
2276 return 0;
2279 memset (pout, pout[-1], len);
2280 pout += len;
2282 else if (unlikely (dist > 29))
2284 elf_zlib_failed ();
2285 return 0;
2287 else
2289 if (dist < 4)
2290 dist = dist + 1;
2291 else
2293 unsigned int extra;
2295 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2296 return 0;
2298 /* This is an expression for the table of
2299 distance codes in RFC 1951 3.2.5. */
2300 dist -= 4;
2301 extra = (dist >> 1) + 1;
2302 dist = (dist & 1) << extra;
2303 dist += 5;
2304 dist += ((1U << (extra - 1)) - 1) << 2;
2305 dist += val & ((1U << extra) - 1);
2306 val >>= extra;
2307 bits -= extra;
2310 /* Go back dist bytes, and copy len bytes from
2311 there. */
2313 if (unlikely ((unsigned int) (pout - porigout) < dist))
2315 elf_zlib_failed ();
2316 return 0;
2319 if (unlikely ((unsigned int) (poutend - pout) < len))
2321 elf_zlib_failed ();
2322 return 0;
2325 if (dist >= len)
2327 memcpy (pout, pout - dist, len);
2328 pout += len;
2330 else
2332 while (len > 0)
2334 unsigned int copy;
2336 copy = len < dist ? len : dist;
2337 memcpy (pout, pout - dist, copy);
2338 len -= copy;
2339 pout += copy;
2348 /* We should have filled the output buffer. */
2349 if (unlikely (pout != poutend))
2351 elf_zlib_failed ();
2352 return 0;
2355 return 1;
2358 /* Verify the zlib checksum. The checksum is in the 4 bytes at
2359 CHECKBYTES, and the uncompressed data is at UNCOMPRESSED /
2360 UNCOMPRESSED_SIZE. Returns 1 on success, 0 on failure. */
2362 static int
2363 elf_zlib_verify_checksum (const unsigned char *checkbytes,
2364 const unsigned char *uncompressed,
2365 size_t uncompressed_size)
2367 unsigned int i;
2368 unsigned int cksum;
2369 const unsigned char *p;
2370 uint32_t s1;
2371 uint32_t s2;
2372 size_t hsz;
2374 cksum = 0;
2375 for (i = 0; i < 4; i++)
2376 cksum = (cksum << 8) | checkbytes[i];
2378 s1 = 1;
2379 s2 = 0;
2381 /* Minimize modulo operations. */
2383 p = uncompressed;
2384 hsz = uncompressed_size;
2385 while (hsz >= 5552)
2387 for (i = 0; i < 5552; i += 16)
2389 /* Manually unroll loop 16 times. */
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 s1 = s1 + *p++;
2401 s2 = s2 + s1;
2402 s1 = s1 + *p++;
2403 s2 = s2 + s1;
2404 s1 = s1 + *p++;
2405 s2 = s2 + s1;
2406 s1 = s1 + *p++;
2407 s2 = s2 + s1;
2408 s1 = s1 + *p++;
2409 s2 = s2 + s1;
2410 s1 = s1 + *p++;
2411 s2 = s2 + s1;
2412 s1 = s1 + *p++;
2413 s2 = s2 + s1;
2414 s1 = s1 + *p++;
2415 s2 = s2 + s1;
2416 s1 = s1 + *p++;
2417 s2 = s2 + s1;
2418 s1 = s1 + *p++;
2419 s2 = s2 + s1;
2420 s1 = s1 + *p++;
2421 s2 = s2 + s1;
2423 hsz -= 5552;
2424 s1 %= 65521;
2425 s2 %= 65521;
2428 while (hsz >= 16)
2430 /* Manually unroll loop 16 times. */
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 s1 = s1 + *p++;
2442 s2 = s2 + s1;
2443 s1 = s1 + *p++;
2444 s2 = s2 + s1;
2445 s1 = s1 + *p++;
2446 s2 = s2 + s1;
2447 s1 = s1 + *p++;
2448 s2 = s2 + s1;
2449 s1 = s1 + *p++;
2450 s2 = s2 + s1;
2451 s1 = s1 + *p++;
2452 s2 = s2 + s1;
2453 s1 = s1 + *p++;
2454 s2 = s2 + s1;
2455 s1 = s1 + *p++;
2456 s2 = s2 + s1;
2457 s1 = s1 + *p++;
2458 s2 = s2 + s1;
2459 s1 = s1 + *p++;
2460 s2 = s2 + s1;
2461 s1 = s1 + *p++;
2462 s2 = s2 + s1;
2464 hsz -= 16;
2467 for (i = 0; i < hsz; ++i)
2469 s1 = s1 + *p++;
2470 s2 = s2 + s1;
2473 s1 %= 65521;
2474 s2 %= 65521;
2476 if (unlikely ((s2 << 16) + s1 != cksum))
2478 elf_zlib_failed ();
2479 return 0;
2482 return 1;
2485 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT, and verify the
2486 checksum. Return 1 on success, 0 on error. */
2488 static int
2489 elf_zlib_inflate_and_verify (const unsigned char *pin, size_t sin,
2490 uint16_t *zdebug_table, unsigned char *pout,
2491 size_t sout)
2493 if (!elf_zlib_inflate (pin, sin, zdebug_table, pout, sout))
2494 return 0;
2495 if (!elf_zlib_verify_checksum (pin + sin - 4, pout, sout))
2496 return 0;
2497 return 1;
2500 /* Uncompress the old compressed debug format, the one emitted by
2501 --compress-debug-sections=zlib-gnu. The compressed data is in
2502 COMPRESSED / COMPRESSED_SIZE, and the function writes to
2503 *UNCOMPRESSED / *UNCOMPRESSED_SIZE. ZDEBUG_TABLE is work space to
2504 hold Huffman tables. Returns 0 on error, 1 on successful
2505 decompression or if something goes wrong. In general we try to
2506 carry on, by returning 1, even if we can't decompress. */
2508 static int
2509 elf_uncompress_zdebug (struct backtrace_state *state,
2510 const unsigned char *compressed, size_t compressed_size,
2511 uint16_t *zdebug_table,
2512 backtrace_error_callback error_callback, void *data,
2513 unsigned char **uncompressed, size_t *uncompressed_size)
2515 size_t sz;
2516 size_t i;
2517 unsigned char *po;
2519 *uncompressed = NULL;
2520 *uncompressed_size = 0;
2522 /* The format starts with the four bytes ZLIB, followed by the 8
2523 byte length of the uncompressed data in big-endian order,
2524 followed by a zlib stream. */
2526 if (compressed_size < 12 || memcmp (compressed, "ZLIB", 4) != 0)
2527 return 1;
2529 sz = 0;
2530 for (i = 0; i < 8; i++)
2531 sz = (sz << 8) | compressed[i + 4];
2533 if (*uncompressed != NULL && *uncompressed_size >= sz)
2534 po = *uncompressed;
2535 else
2537 po = (unsigned char *) backtrace_alloc (state, sz, error_callback, data);
2538 if (po == NULL)
2539 return 0;
2542 if (!elf_zlib_inflate_and_verify (compressed + 12, compressed_size - 12,
2543 zdebug_table, po, sz))
2544 return 1;
2546 *uncompressed = po;
2547 *uncompressed_size = sz;
2549 return 1;
2552 /* Uncompress the new compressed debug format, the official standard
2553 ELF approach emitted by --compress-debug-sections=zlib-gabi. The
2554 compressed data is in COMPRESSED / COMPRESSED_SIZE, and the
2555 function writes to *UNCOMPRESSED / *UNCOMPRESSED_SIZE.
2556 ZDEBUG_TABLE is work space as for elf_uncompress_zdebug. Returns 0
2557 on error, 1 on successful decompression or if something goes wrong.
2558 In general we try to carry on, by returning 1, even if we can't
2559 decompress. */
2561 static int
2562 elf_uncompress_chdr (struct backtrace_state *state,
2563 const unsigned char *compressed, size_t compressed_size,
2564 uint16_t *zdebug_table,
2565 backtrace_error_callback error_callback, void *data,
2566 unsigned char **uncompressed, size_t *uncompressed_size)
2568 const b_elf_chdr *chdr;
2569 unsigned char *po;
2571 *uncompressed = NULL;
2572 *uncompressed_size = 0;
2574 /* The format starts with an ELF compression header. */
2575 if (compressed_size < sizeof (b_elf_chdr))
2576 return 1;
2578 chdr = (const b_elf_chdr *) compressed;
2580 if (chdr->ch_type != ELFCOMPRESS_ZLIB)
2582 /* Unsupported compression algorithm. */
2583 return 1;
2586 if (*uncompressed != NULL && *uncompressed_size >= chdr->ch_size)
2587 po = *uncompressed;
2588 else
2590 po = (unsigned char *) backtrace_alloc (state, chdr->ch_size,
2591 error_callback, data);
2592 if (po == NULL)
2593 return 0;
2596 if (!elf_zlib_inflate_and_verify (compressed + sizeof (b_elf_chdr),
2597 compressed_size - sizeof (b_elf_chdr),
2598 zdebug_table, po, chdr->ch_size))
2599 return 1;
2601 *uncompressed = po;
2602 *uncompressed_size = chdr->ch_size;
2604 return 1;
2607 /* This function is a hook for testing the zlib support. It is only
2608 used by tests. */
2611 backtrace_uncompress_zdebug (struct backtrace_state *state,
2612 const unsigned char *compressed,
2613 size_t compressed_size,
2614 backtrace_error_callback error_callback,
2615 void *data, unsigned char **uncompressed,
2616 size_t *uncompressed_size)
2618 uint16_t *zdebug_table;
2619 int ret;
2621 zdebug_table = ((uint16_t *) backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
2622 error_callback, data));
2623 if (zdebug_table == NULL)
2624 return 0;
2625 ret = elf_uncompress_zdebug (state, compressed, compressed_size,
2626 zdebug_table, error_callback, data,
2627 uncompressed, uncompressed_size);
2628 backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
2629 error_callback, data);
2630 return ret;
2633 /* Add the backtrace data for one ELF file. Returns 1 on success,
2634 0 on failure (in both cases descriptor is closed) or -1 if exe
2635 is non-zero and the ELF file is ET_DYN, which tells the caller that
2636 elf_add will need to be called on the descriptor again after
2637 base_address is determined. */
2639 static int
2640 elf_add (struct backtrace_state *state, const char *filename, int descriptor,
2641 uintptr_t base_address, backtrace_error_callback error_callback,
2642 void *data, fileline *fileline_fn, int *found_sym, int *found_dwarf,
2643 struct dwarf_data **fileline_entry, int exe, int debuginfo,
2644 const char *with_buildid_data, uint32_t with_buildid_size)
2646 struct backtrace_view ehdr_view;
2647 b_elf_ehdr ehdr;
2648 off_t shoff;
2649 unsigned int shnum;
2650 unsigned int shstrndx;
2651 struct backtrace_view shdrs_view;
2652 int shdrs_view_valid;
2653 const b_elf_shdr *shdrs;
2654 const b_elf_shdr *shstrhdr;
2655 size_t shstr_size;
2656 off_t shstr_off;
2657 struct backtrace_view names_view;
2658 int names_view_valid;
2659 const char *names;
2660 unsigned int symtab_shndx;
2661 unsigned int dynsym_shndx;
2662 unsigned int i;
2663 struct debug_section_info sections[DEBUG_MAX];
2664 struct backtrace_view symtab_view;
2665 int symtab_view_valid;
2666 struct backtrace_view strtab_view;
2667 int strtab_view_valid;
2668 struct backtrace_view buildid_view;
2669 int buildid_view_valid;
2670 const char *buildid_data;
2671 uint32_t buildid_size;
2672 struct backtrace_view debuglink_view;
2673 int debuglink_view_valid;
2674 const char *debuglink_name;
2675 uint32_t debuglink_crc;
2676 struct backtrace_view debugaltlink_view;
2677 int debugaltlink_view_valid;
2678 const char *debugaltlink_name;
2679 const char *debugaltlink_buildid_data;
2680 uint32_t debugaltlink_buildid_size;
2681 off_t min_offset;
2682 off_t max_offset;
2683 struct backtrace_view debug_view;
2684 int debug_view_valid;
2685 unsigned int using_debug_view;
2686 uint16_t *zdebug_table;
2687 struct elf_ppc64_opd_data opd_data, *opd;
2689 if (!debuginfo)
2691 *found_sym = 0;
2692 *found_dwarf = 0;
2695 shdrs_view_valid = 0;
2696 names_view_valid = 0;
2697 symtab_view_valid = 0;
2698 strtab_view_valid = 0;
2699 buildid_view_valid = 0;
2700 buildid_data = NULL;
2701 buildid_size = 0;
2702 debuglink_view_valid = 0;
2703 debuglink_name = NULL;
2704 debuglink_crc = 0;
2705 debugaltlink_view_valid = 0;
2706 debugaltlink_name = NULL;
2707 debugaltlink_buildid_data = NULL;
2708 debugaltlink_buildid_size = 0;
2709 debug_view_valid = 0;
2710 opd = NULL;
2712 if (!backtrace_get_view (state, descriptor, 0, sizeof ehdr, error_callback,
2713 data, &ehdr_view))
2714 goto fail;
2716 memcpy (&ehdr, ehdr_view.data, sizeof ehdr);
2718 backtrace_release_view (state, &ehdr_view, error_callback, data);
2720 if (ehdr.e_ident[EI_MAG0] != ELFMAG0
2721 || ehdr.e_ident[EI_MAG1] != ELFMAG1
2722 || ehdr.e_ident[EI_MAG2] != ELFMAG2
2723 || ehdr.e_ident[EI_MAG3] != ELFMAG3)
2725 error_callback (data, "executable file is not ELF", 0);
2726 goto fail;
2728 if (ehdr.e_ident[EI_VERSION] != EV_CURRENT)
2730 error_callback (data, "executable file is unrecognized ELF version", 0);
2731 goto fail;
2734 #if BACKTRACE_ELF_SIZE == 32
2735 #define BACKTRACE_ELFCLASS ELFCLASS32
2736 #else
2737 #define BACKTRACE_ELFCLASS ELFCLASS64
2738 #endif
2740 if (ehdr.e_ident[EI_CLASS] != BACKTRACE_ELFCLASS)
2742 error_callback (data, "executable file is unexpected ELF class", 0);
2743 goto fail;
2746 if (ehdr.e_ident[EI_DATA] != ELFDATA2LSB
2747 && ehdr.e_ident[EI_DATA] != ELFDATA2MSB)
2749 error_callback (data, "executable file has unknown endianness", 0);
2750 goto fail;
2753 /* If the executable is ET_DYN, it is either a PIE, or we are running
2754 directly a shared library with .interp. We need to wait for
2755 dl_iterate_phdr in that case to determine the actual base_address. */
2756 if (exe && ehdr.e_type == ET_DYN)
2757 return -1;
2759 shoff = ehdr.e_shoff;
2760 shnum = ehdr.e_shnum;
2761 shstrndx = ehdr.e_shstrndx;
2763 if ((shnum == 0 || shstrndx == SHN_XINDEX)
2764 && shoff != 0)
2766 struct backtrace_view shdr_view;
2767 const b_elf_shdr *shdr;
2769 if (!backtrace_get_view (state, descriptor, shoff, sizeof shdr,
2770 error_callback, data, &shdr_view))
2771 goto fail;
2773 shdr = (const b_elf_shdr *) shdr_view.data;
2775 if (shnum == 0)
2776 shnum = shdr->sh_size;
2778 if (shstrndx == SHN_XINDEX)
2780 shstrndx = shdr->sh_link;
2782 /* Versions of the GNU binutils between 2.12 and 2.18 did
2783 not handle objects with more than SHN_LORESERVE sections
2784 correctly. All large section indexes were offset by
2785 0x100. There is more information at
2786 http://sourceware.org/bugzilla/show_bug.cgi?id-5900 .
2787 Fortunately these object files are easy to detect, as the
2788 GNU binutils always put the section header string table
2789 near the end of the list of sections. Thus if the
2790 section header string table index is larger than the
2791 number of sections, then we know we have to subtract
2792 0x100 to get the real section index. */
2793 if (shstrndx >= shnum && shstrndx >= SHN_LORESERVE + 0x100)
2794 shstrndx -= 0x100;
2797 backtrace_release_view (state, &shdr_view, error_callback, data);
2800 /* To translate PC to file/line when using DWARF, we need to find
2801 the .debug_info and .debug_line sections. */
2803 /* Read the section headers, skipping the first one. */
2805 if (!backtrace_get_view (state, descriptor, shoff + sizeof (b_elf_shdr),
2806 (shnum - 1) * sizeof (b_elf_shdr),
2807 error_callback, data, &shdrs_view))
2808 goto fail;
2809 shdrs_view_valid = 1;
2810 shdrs = (const b_elf_shdr *) shdrs_view.data;
2812 /* Read the section names. */
2814 shstrhdr = &shdrs[shstrndx - 1];
2815 shstr_size = shstrhdr->sh_size;
2816 shstr_off = shstrhdr->sh_offset;
2818 if (!backtrace_get_view (state, descriptor, shstr_off, shstrhdr->sh_size,
2819 error_callback, data, &names_view))
2820 goto fail;
2821 names_view_valid = 1;
2822 names = (const char *) names_view.data;
2824 symtab_shndx = 0;
2825 dynsym_shndx = 0;
2827 memset (sections, 0, sizeof sections);
2829 /* Look for the symbol table. */
2830 for (i = 1; i < shnum; ++i)
2832 const b_elf_shdr *shdr;
2833 unsigned int sh_name;
2834 const char *name;
2835 int j;
2837 shdr = &shdrs[i - 1];
2839 if (shdr->sh_type == SHT_SYMTAB)
2840 symtab_shndx = i;
2841 else if (shdr->sh_type == SHT_DYNSYM)
2842 dynsym_shndx = i;
2844 sh_name = shdr->sh_name;
2845 if (sh_name >= shstr_size)
2847 error_callback (data, "ELF section name out of range", 0);
2848 goto fail;
2851 name = names + sh_name;
2853 for (j = 0; j < (int) DEBUG_MAX; ++j)
2855 if (strcmp (name, debug_section_names[j]) == 0)
2857 sections[j].offset = shdr->sh_offset;
2858 sections[j].size = shdr->sh_size;
2859 sections[j].compressed = (shdr->sh_flags & SHF_COMPRESSED) != 0;
2860 break;
2864 /* Read the build ID if present. This could check for any
2865 SHT_NOTE section with the right note name and type, but gdb
2866 looks for a specific section name. */
2867 if ((!debuginfo || with_buildid_data != NULL)
2868 && !buildid_view_valid
2869 && strcmp (name, ".note.gnu.build-id") == 0)
2871 const b_elf_note *note;
2873 if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2874 shdr->sh_size, error_callback, data,
2875 &buildid_view))
2876 goto fail;
2878 buildid_view_valid = 1;
2879 note = (const b_elf_note *) buildid_view.data;
2880 if (note->type == NT_GNU_BUILD_ID
2881 && note->namesz == 4
2882 && strncmp (note->name, "GNU", 4) == 0
2883 && shdr->sh_size <= 12 + ((note->namesz + 3) & ~ 3) + note->descsz)
2885 buildid_data = &note->name[0] + ((note->namesz + 3) & ~ 3);
2886 buildid_size = note->descsz;
2889 if (with_buildid_size != 0)
2891 if (buildid_size != with_buildid_size)
2892 goto fail;
2894 if (memcmp (buildid_data, with_buildid_data, buildid_size) != 0)
2895 goto fail;
2899 /* Read the debuglink file if present. */
2900 if (!debuginfo
2901 && !debuglink_view_valid
2902 && strcmp (name, ".gnu_debuglink") == 0)
2904 const char *debuglink_data;
2905 size_t crc_offset;
2907 if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2908 shdr->sh_size, error_callback, data,
2909 &debuglink_view))
2910 goto fail;
2912 debuglink_view_valid = 1;
2913 debuglink_data = (const char *) debuglink_view.data;
2914 crc_offset = strnlen (debuglink_data, shdr->sh_size);
2915 crc_offset = (crc_offset + 3) & ~3;
2916 if (crc_offset + 4 <= shdr->sh_size)
2918 debuglink_name = debuglink_data;
2919 debuglink_crc = *(const uint32_t*)(debuglink_data + crc_offset);
2923 if (!debugaltlink_view_valid
2924 && strcmp (name, ".gnu_debugaltlink") == 0)
2926 const char *debugaltlink_data;
2927 size_t debugaltlink_name_len;
2929 if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2930 shdr->sh_size, error_callback, data,
2931 &debugaltlink_view))
2932 goto fail;
2934 debugaltlink_view_valid = 1;
2935 debugaltlink_data = (const char *) debugaltlink_view.data;
2936 debugaltlink_name = debugaltlink_data;
2937 debugaltlink_name_len = strnlen (debugaltlink_data, shdr->sh_size);
2938 if (debugaltlink_name_len < shdr->sh_size)
2940 /* Include terminating zero. */
2941 debugaltlink_name_len += 1;
2943 debugaltlink_buildid_data
2944 = debugaltlink_data + debugaltlink_name_len;
2945 debugaltlink_buildid_size = shdr->sh_size - debugaltlink_name_len;
2949 /* Read the .opd section on PowerPC64 ELFv1. */
2950 if (ehdr.e_machine == EM_PPC64
2951 && (ehdr.e_flags & EF_PPC64_ABI) < 2
2952 && shdr->sh_type == SHT_PROGBITS
2953 && strcmp (name, ".opd") == 0)
2955 if (!backtrace_get_view (state, descriptor, shdr->sh_offset,
2956 shdr->sh_size, error_callback, data,
2957 &opd_data.view))
2958 goto fail;
2960 opd = &opd_data;
2961 opd->addr = shdr->sh_addr;
2962 opd->data = (const char *) opd_data.view.data;
2963 opd->size = shdr->sh_size;
2967 if (symtab_shndx == 0)
2968 symtab_shndx = dynsym_shndx;
2969 if (symtab_shndx != 0 && !debuginfo)
2971 const b_elf_shdr *symtab_shdr;
2972 unsigned int strtab_shndx;
2973 const b_elf_shdr *strtab_shdr;
2974 struct elf_syminfo_data *sdata;
2976 symtab_shdr = &shdrs[symtab_shndx - 1];
2977 strtab_shndx = symtab_shdr->sh_link;
2978 if (strtab_shndx >= shnum)
2980 error_callback (data,
2981 "ELF symbol table strtab link out of range", 0);
2982 goto fail;
2984 strtab_shdr = &shdrs[strtab_shndx - 1];
2986 if (!backtrace_get_view (state, descriptor, symtab_shdr->sh_offset,
2987 symtab_shdr->sh_size, error_callback, data,
2988 &symtab_view))
2989 goto fail;
2990 symtab_view_valid = 1;
2992 if (!backtrace_get_view (state, descriptor, strtab_shdr->sh_offset,
2993 strtab_shdr->sh_size, error_callback, data,
2994 &strtab_view))
2995 goto fail;
2996 strtab_view_valid = 1;
2998 sdata = ((struct elf_syminfo_data *)
2999 backtrace_alloc (state, sizeof *sdata, error_callback, data));
3000 if (sdata == NULL)
3001 goto fail;
3003 if (!elf_initialize_syminfo (state, base_address,
3004 symtab_view.data, symtab_shdr->sh_size,
3005 strtab_view.data, strtab_shdr->sh_size,
3006 error_callback, data, sdata, opd))
3008 backtrace_free (state, sdata, sizeof *sdata, error_callback, data);
3009 goto fail;
3012 /* We no longer need the symbol table, but we hold on to the
3013 string table permanently. */
3014 backtrace_release_view (state, &symtab_view, error_callback, data);
3015 symtab_view_valid = 0;
3017 *found_sym = 1;
3019 elf_add_syminfo_data (state, sdata);
3022 backtrace_release_view (state, &shdrs_view, error_callback, data);
3023 shdrs_view_valid = 0;
3024 backtrace_release_view (state, &names_view, error_callback, data);
3025 names_view_valid = 0;
3027 /* If the debug info is in a separate file, read that one instead. */
3029 if (buildid_data != NULL)
3031 int d;
3033 d = elf_open_debugfile_by_buildid (state, buildid_data, buildid_size,
3034 error_callback, data);
3035 if (d >= 0)
3037 int ret;
3039 backtrace_release_view (state, &buildid_view, error_callback, data);
3040 if (debuglink_view_valid)
3041 backtrace_release_view (state, &debuglink_view, error_callback,
3042 data);
3043 if (debugaltlink_view_valid)
3044 backtrace_release_view (state, &debugaltlink_view, error_callback,
3045 data);
3046 ret = elf_add (state, "", d, base_address, error_callback, data,
3047 fileline_fn, found_sym, found_dwarf, NULL, 0, 1, NULL,
3049 if (ret < 0)
3050 backtrace_close (d, error_callback, data);
3051 else
3052 backtrace_close (descriptor, error_callback, data);
3053 return ret;
3057 if (buildid_view_valid)
3059 backtrace_release_view (state, &buildid_view, error_callback, data);
3060 buildid_view_valid = 0;
3063 if (opd)
3065 backtrace_release_view (state, &opd->view, error_callback, data);
3066 opd = NULL;
3069 if (debuglink_name != NULL)
3071 int d;
3073 d = elf_open_debugfile_by_debuglink (state, filename, debuglink_name,
3074 debuglink_crc, error_callback,
3075 data);
3076 if (d >= 0)
3078 int ret;
3080 backtrace_release_view (state, &debuglink_view, error_callback,
3081 data);
3082 if (debugaltlink_view_valid)
3083 backtrace_release_view (state, &debugaltlink_view, error_callback,
3084 data);
3085 ret = elf_add (state, "", d, base_address, error_callback, data,
3086 fileline_fn, found_sym, found_dwarf, NULL, 0, 1, NULL,
3088 if (ret < 0)
3089 backtrace_close (d, error_callback, data);
3090 else
3091 backtrace_close(descriptor, error_callback, data);
3092 return ret;
3096 if (debuglink_view_valid)
3098 backtrace_release_view (state, &debuglink_view, error_callback, data);
3099 debuglink_view_valid = 0;
3102 struct dwarf_data *fileline_altlink = NULL;
3103 if (debugaltlink_name != NULL)
3105 int d;
3107 d = elf_open_debugfile_by_debuglink (state, filename, debugaltlink_name,
3108 0, error_callback, data);
3109 if (d >= 0)
3111 int ret;
3113 ret = elf_add (state, filename, d, base_address, error_callback, data,
3114 fileline_fn, found_sym, found_dwarf, &fileline_altlink,
3115 0, 1, debugaltlink_buildid_data,
3116 debugaltlink_buildid_size);
3117 backtrace_release_view (state, &debugaltlink_view, error_callback,
3118 data);
3119 debugaltlink_view_valid = 0;
3120 if (ret < 0)
3122 backtrace_close (d, error_callback, data);
3123 return ret;
3128 if (debugaltlink_view_valid)
3130 backtrace_release_view (state, &debugaltlink_view, error_callback, data);
3131 debugaltlink_view_valid = 0;
3134 /* Read all the debug sections in a single view, since they are
3135 probably adjacent in the file. We never release this view. */
3137 min_offset = 0;
3138 max_offset = 0;
3139 for (i = 0; i < (int) DEBUG_MAX; ++i)
3141 off_t end;
3143 if (sections[i].size == 0)
3144 continue;
3145 if (min_offset == 0 || sections[i].offset < min_offset)
3146 min_offset = sections[i].offset;
3147 end = sections[i].offset + sections[i].size;
3148 if (end > max_offset)
3149 max_offset = end;
3151 if (min_offset == 0 || max_offset == 0)
3153 if (!backtrace_close (descriptor, error_callback, data))
3154 goto fail;
3155 return 1;
3158 if (!backtrace_get_view (state, descriptor, min_offset,
3159 max_offset - min_offset,
3160 error_callback, data, &debug_view))
3161 goto fail;
3162 debug_view_valid = 1;
3164 /* We've read all we need from the executable. */
3165 if (!backtrace_close (descriptor, error_callback, data))
3166 goto fail;
3167 descriptor = -1;
3169 using_debug_view = 0;
3170 for (i = 0; i < (int) DEBUG_MAX; ++i)
3172 if (sections[i].size == 0)
3173 sections[i].data = NULL;
3174 else
3176 sections[i].data = ((const unsigned char *) debug_view.data
3177 + (sections[i].offset - min_offset));
3178 if (i < ZDEBUG_INFO)
3179 ++using_debug_view;
3183 /* Uncompress the old format (--compress-debug-sections=zlib-gnu). */
3185 zdebug_table = NULL;
3186 for (i = 0; i < ZDEBUG_INFO; ++i)
3188 struct debug_section_info *pz;
3190 pz = &sections[i + ZDEBUG_INFO - DEBUG_INFO];
3191 if (sections[i].size == 0 && pz->size > 0)
3193 unsigned char *uncompressed_data;
3194 size_t uncompressed_size;
3196 if (zdebug_table == NULL)
3198 zdebug_table = ((uint16_t *)
3199 backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
3200 error_callback, data));
3201 if (zdebug_table == NULL)
3202 goto fail;
3205 uncompressed_data = NULL;
3206 uncompressed_size = 0;
3207 if (!elf_uncompress_zdebug (state, pz->data, pz->size, zdebug_table,
3208 error_callback, data,
3209 &uncompressed_data, &uncompressed_size))
3210 goto fail;
3211 sections[i].data = uncompressed_data;
3212 sections[i].size = uncompressed_size;
3213 sections[i].compressed = 0;
3217 /* Uncompress the official ELF format
3218 (--compress-debug-sections=zlib-gabi). */
3219 for (i = 0; i < ZDEBUG_INFO; ++i)
3221 unsigned char *uncompressed_data;
3222 size_t uncompressed_size;
3224 if (sections[i].size == 0 || !sections[i].compressed)
3225 continue;
3227 if (zdebug_table == NULL)
3229 zdebug_table = ((uint16_t *)
3230 backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
3231 error_callback, data));
3232 if (zdebug_table == NULL)
3233 goto fail;
3236 uncompressed_data = NULL;
3237 uncompressed_size = 0;
3238 if (!elf_uncompress_chdr (state, sections[i].data, sections[i].size,
3239 zdebug_table, error_callback, data,
3240 &uncompressed_data, &uncompressed_size))
3241 goto fail;
3242 sections[i].data = uncompressed_data;
3243 sections[i].size = uncompressed_size;
3244 sections[i].compressed = 0;
3246 --using_debug_view;
3249 if (zdebug_table != NULL)
3250 backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
3251 error_callback, data);
3253 if (debug_view_valid && using_debug_view == 0)
3255 backtrace_release_view (state, &debug_view, error_callback, data);
3256 debug_view_valid = 0;
3259 if (!backtrace_dwarf_add (state, base_address,
3260 sections[DEBUG_INFO].data,
3261 sections[DEBUG_INFO].size,
3262 sections[DEBUG_LINE].data,
3263 sections[DEBUG_LINE].size,
3264 sections[DEBUG_ABBREV].data,
3265 sections[DEBUG_ABBREV].size,
3266 sections[DEBUG_RANGES].data,
3267 sections[DEBUG_RANGES].size,
3268 sections[DEBUG_STR].data,
3269 sections[DEBUG_STR].size,
3270 ehdr.e_ident[EI_DATA] == ELFDATA2MSB,
3271 fileline_altlink,
3272 error_callback, data, fileline_fn,
3273 fileline_entry))
3274 goto fail;
3276 *found_dwarf = 1;
3278 return 1;
3280 fail:
3281 if (shdrs_view_valid)
3282 backtrace_release_view (state, &shdrs_view, error_callback, data);
3283 if (names_view_valid)
3284 backtrace_release_view (state, &names_view, error_callback, data);
3285 if (symtab_view_valid)
3286 backtrace_release_view (state, &symtab_view, error_callback, data);
3287 if (strtab_view_valid)
3288 backtrace_release_view (state, &strtab_view, error_callback, data);
3289 if (debuglink_view_valid)
3290 backtrace_release_view (state, &debuglink_view, error_callback, data);
3291 if (debugaltlink_view_valid)
3292 backtrace_release_view (state, &debugaltlink_view, error_callback, data);
3293 if (buildid_view_valid)
3294 backtrace_release_view (state, &buildid_view, error_callback, data);
3295 if (debug_view_valid)
3296 backtrace_release_view (state, &debug_view, error_callback, data);
3297 if (opd)
3298 backtrace_release_view (state, &opd->view, error_callback, data);
3299 if (descriptor != -1)
3300 backtrace_close (descriptor, error_callback, data);
3301 return 0;
3304 /* Data passed to phdr_callback. */
3306 struct phdr_data
3308 struct backtrace_state *state;
3309 backtrace_error_callback error_callback;
3310 void *data;
3311 fileline *fileline_fn;
3312 int *found_sym;
3313 int *found_dwarf;
3314 const char *exe_filename;
3315 int exe_descriptor;
3318 /* Callback passed to dl_iterate_phdr. Load debug info from shared
3319 libraries. */
3321 static int
3322 #ifdef __i386__
3323 __attribute__ ((__force_align_arg_pointer__))
3324 #endif
3325 phdr_callback (struct dl_phdr_info *info, size_t size ATTRIBUTE_UNUSED,
3326 void *pdata)
3328 struct phdr_data *pd = (struct phdr_data *) pdata;
3329 const char *filename;
3330 int descriptor;
3331 int does_not_exist;
3332 fileline elf_fileline_fn;
3333 int found_dwarf;
3335 /* There is not much we can do if we don't have the module name,
3336 unless executable is ET_DYN, where we expect the very first
3337 phdr_callback to be for the PIE. */
3338 if (info->dlpi_name == NULL || info->dlpi_name[0] == '\0')
3340 if (pd->exe_descriptor == -1)
3341 return 0;
3342 filename = pd->exe_filename;
3343 descriptor = pd->exe_descriptor;
3344 pd->exe_descriptor = -1;
3346 else
3348 if (pd->exe_descriptor != -1)
3350 backtrace_close (pd->exe_descriptor, pd->error_callback, pd->data);
3351 pd->exe_descriptor = -1;
3354 filename = info->dlpi_name;
3355 descriptor = backtrace_open (info->dlpi_name, pd->error_callback,
3356 pd->data, &does_not_exist);
3357 if (descriptor < 0)
3358 return 0;
3361 if (elf_add (pd->state, filename, descriptor, info->dlpi_addr,
3362 pd->error_callback, pd->data, &elf_fileline_fn, pd->found_sym,
3363 &found_dwarf, NULL, 0, 0, NULL, 0))
3365 if (found_dwarf)
3367 *pd->found_dwarf = 1;
3368 *pd->fileline_fn = elf_fileline_fn;
3372 return 0;
3375 /* Initialize the backtrace data we need from an ELF executable. At
3376 the ELF level, all we need to do is find the debug info
3377 sections. */
3380 backtrace_initialize (struct backtrace_state *state, const char *filename,
3381 int descriptor, backtrace_error_callback error_callback,
3382 void *data, fileline *fileline_fn)
3384 int ret;
3385 int found_sym;
3386 int found_dwarf;
3387 fileline elf_fileline_fn = elf_nodebug;
3388 struct phdr_data pd;
3390 ret = elf_add (state, filename, descriptor, 0, error_callback, data,
3391 &elf_fileline_fn, &found_sym, &found_dwarf, NULL, 1, 0, NULL,
3393 if (!ret)
3394 return 0;
3396 pd.state = state;
3397 pd.error_callback = error_callback;
3398 pd.data = data;
3399 pd.fileline_fn = &elf_fileline_fn;
3400 pd.found_sym = &found_sym;
3401 pd.found_dwarf = &found_dwarf;
3402 pd.exe_filename = filename;
3403 pd.exe_descriptor = ret < 0 ? descriptor : -1;
3405 dl_iterate_phdr (phdr_callback, (void *) &pd);
3407 if (!state->threaded)
3409 if (found_sym)
3410 state->syminfo_fn = elf_syminfo;
3411 else if (state->syminfo_fn == NULL)
3412 state->syminfo_fn = elf_nosyms;
3414 else
3416 if (found_sym)
3417 backtrace_atomic_store_pointer (&state->syminfo_fn, elf_syminfo);
3418 else
3419 (void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
3420 elf_nosyms);
3423 if (!state->threaded)
3424 *fileline_fn = state->fileline_fn;
3425 else
3426 *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
3428 if (*fileline_fn == NULL || *fileline_fn == elf_nodebug)
3429 *fileline_fn = elf_fileline_fn;
3431 return 1;