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