Daily bump.
[official-gcc.git] / libbacktrace / elf.c
blob79d56146fc67206d6f7f883a55b27eda7d168e23
1 /* elf.c -- Get debug data from an ELF file for backtraces.
2 Copyright (C) 2012-2021 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 /* Names of sections, indexed by enum dwarf_section in internal.h. */
342 static const char * const dwarf_section_names[DEBUG_MAX] =
344 ".debug_info",
345 ".debug_line",
346 ".debug_abbrev",
347 ".debug_ranges",
348 ".debug_str",
349 ".debug_addr",
350 ".debug_str_offsets",
351 ".debug_line_str",
352 ".debug_rnglists"
355 /* Information we gather for the sections we care about. */
357 struct debug_section_info
359 /* Section file offset. */
360 off_t offset;
361 /* Section size. */
362 size_t size;
363 /* Section contents, after read from file. */
364 const unsigned char *data;
365 /* Whether the SHF_COMPRESSED flag is set for the section. */
366 int compressed;
369 /* Information we keep for an ELF symbol. */
371 struct elf_symbol
373 /* The name of the symbol. */
374 const char *name;
375 /* The address of the symbol. */
376 uintptr_t address;
377 /* The size of the symbol. */
378 size_t size;
381 /* Information to pass to elf_syminfo. */
383 struct elf_syminfo_data
385 /* Symbols for the next module. */
386 struct elf_syminfo_data *next;
387 /* The ELF symbols, sorted by address. */
388 struct elf_symbol *symbols;
389 /* The number of symbols. */
390 size_t count;
393 /* A view that works for either a file or memory. */
395 struct elf_view
397 struct backtrace_view view;
398 int release; /* If non-zero, must call backtrace_release_view. */
401 /* Information about PowerPC64 ELFv1 .opd section. */
403 struct elf_ppc64_opd_data
405 /* Address of the .opd section. */
406 b_elf_addr addr;
407 /* Section data. */
408 const char *data;
409 /* Size of the .opd section. */
410 size_t size;
411 /* Corresponding section view. */
412 struct elf_view view;
415 /* Create a view of SIZE bytes from DESCRIPTOR/MEMORY at OFFSET. */
417 static int
418 elf_get_view (struct backtrace_state *state, int descriptor,
419 const unsigned char *memory, size_t memory_size, off_t offset,
420 uint64_t size, backtrace_error_callback error_callback,
421 void *data, struct elf_view *view)
423 if (memory == NULL)
425 view->release = 1;
426 return backtrace_get_view (state, descriptor, offset, size,
427 error_callback, data, &view->view);
429 else
431 if ((uint64_t) offset + size > (uint64_t) memory_size)
433 error_callback (data, "out of range for in-memory file", 0);
434 return 0;
436 view->view.data = (const void *) (memory + offset);
437 view->view.base = NULL;
438 view->view.len = size;
439 view->release = 0;
440 return 1;
444 /* Release a view read by elf_get_view. */
446 static void
447 elf_release_view (struct backtrace_state *state, struct elf_view *view,
448 backtrace_error_callback error_callback, void *data)
450 if (view->release)
451 backtrace_release_view (state, &view->view, error_callback, data);
454 /* Compute the CRC-32 of BUF/LEN. This uses the CRC used for
455 .gnu_debuglink files. */
457 static uint32_t
458 elf_crc32 (uint32_t crc, const unsigned char *buf, size_t len)
460 static const uint32_t crc32_table[256] =
462 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
463 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
464 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
465 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
466 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
467 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
468 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
469 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
470 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
471 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
472 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
473 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
474 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
475 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
476 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
477 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
478 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
479 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
480 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
481 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
482 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
483 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
484 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
485 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
486 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
487 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
488 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
489 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
490 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
491 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
492 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
493 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
494 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
495 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
496 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
497 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
498 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
499 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
500 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
501 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
502 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
503 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
504 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
505 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
506 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
507 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
508 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
509 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
510 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
511 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
512 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
513 0x2d02ef8d
515 const unsigned char *end;
517 crc = ~crc;
518 for (end = buf + len; buf < end; ++ buf)
519 crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8);
520 return ~crc;
523 /* Return the CRC-32 of the entire file open at DESCRIPTOR. */
525 static uint32_t
526 elf_crc32_file (struct backtrace_state *state, int descriptor,
527 backtrace_error_callback error_callback, void *data)
529 struct stat st;
530 struct backtrace_view file_view;
531 uint32_t ret;
533 if (fstat (descriptor, &st) < 0)
535 error_callback (data, "fstat", errno);
536 return 0;
539 if (!backtrace_get_view (state, descriptor, 0, st.st_size, error_callback,
540 data, &file_view))
541 return 0;
543 ret = elf_crc32 (0, (const unsigned char *) file_view.data, st.st_size);
545 backtrace_release_view (state, &file_view, error_callback, data);
547 return ret;
550 /* A dummy callback function used when we can't find a symbol
551 table. */
553 static void
554 elf_nosyms (struct backtrace_state *state ATTRIBUTE_UNUSED,
555 uintptr_t addr ATTRIBUTE_UNUSED,
556 backtrace_syminfo_callback callback ATTRIBUTE_UNUSED,
557 backtrace_error_callback error_callback, void *data)
559 error_callback (data, "no symbol table in ELF executable", -1);
562 /* A callback function used when we can't find any debug info. */
564 static int
565 elf_nodebug (struct backtrace_state *state, uintptr_t pc,
566 backtrace_full_callback callback,
567 backtrace_error_callback error_callback, void *data)
569 if (state->syminfo_fn != NULL && state->syminfo_fn != elf_nosyms)
571 struct backtrace_call_full bdata;
573 /* Fetch symbol information so that we can least get the
574 function name. */
576 bdata.full_callback = callback;
577 bdata.full_error_callback = error_callback;
578 bdata.full_data = data;
579 bdata.ret = 0;
580 state->syminfo_fn (state, pc, backtrace_syminfo_to_full_callback,
581 backtrace_syminfo_to_full_error_callback, &bdata);
582 return bdata.ret;
585 error_callback (data, "no debug info in ELF executable", -1);
586 return 0;
589 /* Compare struct elf_symbol for qsort. */
591 static int
592 elf_symbol_compare (const void *v1, const void *v2)
594 const struct elf_symbol *e1 = (const struct elf_symbol *) v1;
595 const struct elf_symbol *e2 = (const struct elf_symbol *) v2;
597 if (e1->address < e2->address)
598 return -1;
599 else if (e1->address > e2->address)
600 return 1;
601 else
602 return 0;
605 /* Compare an ADDR against an elf_symbol for bsearch. We allocate one
606 extra entry in the array so that this can look safely at the next
607 entry. */
609 static int
610 elf_symbol_search (const void *vkey, const void *ventry)
612 const uintptr_t *key = (const uintptr_t *) vkey;
613 const struct elf_symbol *entry = (const struct elf_symbol *) ventry;
614 uintptr_t addr;
616 addr = *key;
617 if (addr < entry->address)
618 return -1;
619 else if (addr >= entry->address + entry->size)
620 return 1;
621 else
622 return 0;
625 /* Initialize the symbol table info for elf_syminfo. */
627 static int
628 elf_initialize_syminfo (struct backtrace_state *state,
629 uintptr_t base_address,
630 const unsigned char *symtab_data, size_t symtab_size,
631 const unsigned char *strtab, size_t strtab_size,
632 backtrace_error_callback error_callback,
633 void *data, struct elf_syminfo_data *sdata,
634 struct elf_ppc64_opd_data *opd)
636 size_t sym_count;
637 const b_elf_sym *sym;
638 size_t elf_symbol_count;
639 size_t elf_symbol_size;
640 struct elf_symbol *elf_symbols;
641 size_t i;
642 unsigned int j;
644 sym_count = symtab_size / sizeof (b_elf_sym);
646 /* We only care about function symbols. Count them. */
647 sym = (const b_elf_sym *) symtab_data;
648 elf_symbol_count = 0;
649 for (i = 0; i < sym_count; ++i, ++sym)
651 int info;
653 info = sym->st_info & 0xf;
654 if ((info == STT_FUNC || info == STT_OBJECT)
655 && sym->st_shndx != SHN_UNDEF)
656 ++elf_symbol_count;
659 elf_symbol_size = elf_symbol_count * sizeof (struct elf_symbol);
660 elf_symbols = ((struct elf_symbol *)
661 backtrace_alloc (state, elf_symbol_size, error_callback,
662 data));
663 if (elf_symbols == NULL)
664 return 0;
666 sym = (const b_elf_sym *) symtab_data;
667 j = 0;
668 for (i = 0; i < sym_count; ++i, ++sym)
670 int info;
672 info = sym->st_info & 0xf;
673 if (info != STT_FUNC && info != STT_OBJECT)
674 continue;
675 if (sym->st_shndx == SHN_UNDEF)
676 continue;
677 if (sym->st_name >= strtab_size)
679 error_callback (data, "symbol string index out of range", 0);
680 backtrace_free (state, elf_symbols, elf_symbol_size, error_callback,
681 data);
682 return 0;
684 elf_symbols[j].name = (const char *) strtab + sym->st_name;
685 /* Special case PowerPC64 ELFv1 symbols in .opd section, if the symbol
686 is a function descriptor, read the actual code address from the
687 descriptor. */
688 if (opd
689 && sym->st_value >= opd->addr
690 && sym->st_value < opd->addr + opd->size)
691 elf_symbols[j].address
692 = *(const b_elf_addr *) (opd->data + (sym->st_value - opd->addr));
693 else
694 elf_symbols[j].address = sym->st_value;
695 elf_symbols[j].address += base_address;
696 elf_symbols[j].size = sym->st_size;
697 ++j;
700 backtrace_qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
701 elf_symbol_compare);
703 sdata->next = NULL;
704 sdata->symbols = elf_symbols;
705 sdata->count = elf_symbol_count;
707 return 1;
710 /* Add EDATA to the list in STATE. */
712 static void
713 elf_add_syminfo_data (struct backtrace_state *state,
714 struct elf_syminfo_data *edata)
716 if (!state->threaded)
718 struct elf_syminfo_data **pp;
720 for (pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
721 *pp != NULL;
722 pp = &(*pp)->next)
724 *pp = edata;
726 else
728 while (1)
730 struct elf_syminfo_data **pp;
732 pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
734 while (1)
736 struct elf_syminfo_data *p;
738 p = backtrace_atomic_load_pointer (pp);
740 if (p == NULL)
741 break;
743 pp = &p->next;
746 if (__sync_bool_compare_and_swap (pp, NULL, edata))
747 break;
752 /* Return the symbol name and value for an ADDR. */
754 static void
755 elf_syminfo (struct backtrace_state *state, uintptr_t addr,
756 backtrace_syminfo_callback callback,
757 backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
758 void *data)
760 struct elf_syminfo_data *edata;
761 struct elf_symbol *sym = NULL;
763 if (!state->threaded)
765 for (edata = (struct elf_syminfo_data *) state->syminfo_data;
766 edata != NULL;
767 edata = edata->next)
769 sym = ((struct elf_symbol *)
770 bsearch (&addr, edata->symbols, edata->count,
771 sizeof (struct elf_symbol), elf_symbol_search));
772 if (sym != NULL)
773 break;
776 else
778 struct elf_syminfo_data **pp;
780 pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
781 while (1)
783 edata = backtrace_atomic_load_pointer (pp);
784 if (edata == NULL)
785 break;
787 sym = ((struct elf_symbol *)
788 bsearch (&addr, edata->symbols, edata->count,
789 sizeof (struct elf_symbol), elf_symbol_search));
790 if (sym != NULL)
791 break;
793 pp = &edata->next;
797 if (sym == NULL)
798 callback (data, addr, NULL, 0, 0);
799 else
800 callback (data, addr, sym->name, sym->address, sym->size);
803 /* Return whether FILENAME is a symlink. */
805 static int
806 elf_is_symlink (const char *filename)
808 struct stat st;
810 if (lstat (filename, &st) < 0)
811 return 0;
812 return S_ISLNK (st.st_mode);
815 /* Return the results of reading the symlink FILENAME in a buffer
816 allocated by backtrace_alloc. Return the length of the buffer in
817 *LEN. */
819 static char *
820 elf_readlink (struct backtrace_state *state, const char *filename,
821 backtrace_error_callback error_callback, void *data,
822 size_t *plen)
824 size_t len;
825 char *buf;
827 len = 128;
828 while (1)
830 ssize_t rl;
832 buf = backtrace_alloc (state, len, error_callback, data);
833 if (buf == NULL)
834 return NULL;
835 rl = readlink (filename, buf, len);
836 if (rl < 0)
838 backtrace_free (state, buf, len, error_callback, data);
839 return NULL;
841 if ((size_t) rl < len - 1)
843 buf[rl] = '\0';
844 *plen = len;
845 return buf;
847 backtrace_free (state, buf, len, error_callback, data);
848 len *= 2;
852 #define SYSTEM_BUILD_ID_DIR "/usr/lib/debug/.build-id/"
854 /* Open a separate debug info file, using the build ID to find it.
855 Returns an open file descriptor, or -1.
857 The GDB manual says that the only place gdb looks for a debug file
858 when the build ID is known is in /usr/lib/debug/.build-id. */
860 static int
861 elf_open_debugfile_by_buildid (struct backtrace_state *state,
862 const char *buildid_data, size_t buildid_size,
863 backtrace_error_callback error_callback,
864 void *data)
866 const char * const prefix = SYSTEM_BUILD_ID_DIR;
867 const size_t prefix_len = strlen (prefix);
868 const char * const suffix = ".debug";
869 const size_t suffix_len = strlen (suffix);
870 size_t len;
871 char *bd_filename;
872 char *t;
873 size_t i;
874 int ret;
875 int does_not_exist;
877 len = prefix_len + buildid_size * 2 + suffix_len + 2;
878 bd_filename = backtrace_alloc (state, len, error_callback, data);
879 if (bd_filename == NULL)
880 return -1;
882 t = bd_filename;
883 memcpy (t, prefix, prefix_len);
884 t += prefix_len;
885 for (i = 0; i < buildid_size; i++)
887 unsigned char b;
888 unsigned char nib;
890 b = (unsigned char) buildid_data[i];
891 nib = (b & 0xf0) >> 4;
892 *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
893 nib = b & 0x0f;
894 *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
895 if (i == 0)
896 *t++ = '/';
898 memcpy (t, suffix, suffix_len);
899 t[suffix_len] = '\0';
901 ret = backtrace_open (bd_filename, error_callback, data, &does_not_exist);
903 backtrace_free (state, bd_filename, len, error_callback, data);
905 /* gdb checks that the debuginfo file has the same build ID note.
906 That seems kind of pointless to me--why would it have the right
907 name but not the right build ID?--so skipping the check. */
909 return ret;
912 /* Try to open a file whose name is PREFIX (length PREFIX_LEN)
913 concatenated with PREFIX2 (length PREFIX2_LEN) concatenated with
914 DEBUGLINK_NAME. Returns an open file descriptor, or -1. */
916 static int
917 elf_try_debugfile (struct backtrace_state *state, const char *prefix,
918 size_t prefix_len, const char *prefix2, size_t prefix2_len,
919 const char *debuglink_name,
920 backtrace_error_callback error_callback, void *data)
922 size_t debuglink_len;
923 size_t try_len;
924 char *try;
925 int does_not_exist;
926 int ret;
928 debuglink_len = strlen (debuglink_name);
929 try_len = prefix_len + prefix2_len + debuglink_len + 1;
930 try = backtrace_alloc (state, try_len, error_callback, data);
931 if (try == NULL)
932 return -1;
934 memcpy (try, prefix, prefix_len);
935 memcpy (try + prefix_len, prefix2, prefix2_len);
936 memcpy (try + prefix_len + prefix2_len, debuglink_name, debuglink_len);
937 try[prefix_len + prefix2_len + debuglink_len] = '\0';
939 ret = backtrace_open (try, error_callback, data, &does_not_exist);
941 backtrace_free (state, try, try_len, error_callback, data);
943 return ret;
946 /* Find a separate debug info file, using the debuglink section data
947 to find it. Returns an open file descriptor, or -1. */
949 static int
950 elf_find_debugfile_by_debuglink (struct backtrace_state *state,
951 const char *filename,
952 const char *debuglink_name,
953 backtrace_error_callback error_callback,
954 void *data)
956 int ret;
957 char *alc;
958 size_t alc_len;
959 const char *slash;
960 int ddescriptor;
961 const char *prefix;
962 size_t prefix_len;
964 /* Resolve symlinks in FILENAME. Since FILENAME is fairly likely to
965 be /proc/self/exe, symlinks are common. We don't try to resolve
966 the whole path name, just the base name. */
967 ret = -1;
968 alc = NULL;
969 alc_len = 0;
970 while (elf_is_symlink (filename))
972 char *new_buf;
973 size_t new_len;
975 new_buf = elf_readlink (state, filename, error_callback, data, &new_len);
976 if (new_buf == NULL)
977 break;
979 if (new_buf[0] == '/')
980 filename = new_buf;
981 else
983 slash = strrchr (filename, '/');
984 if (slash == NULL)
985 filename = new_buf;
986 else
988 size_t clen;
989 char *c;
991 slash++;
992 clen = slash - filename + strlen (new_buf) + 1;
993 c = backtrace_alloc (state, clen, error_callback, data);
994 if (c == NULL)
995 goto done;
997 memcpy (c, filename, slash - filename);
998 memcpy (c + (slash - filename), new_buf, strlen (new_buf));
999 c[slash - filename + strlen (new_buf)] = '\0';
1000 backtrace_free (state, new_buf, new_len, error_callback, data);
1001 filename = c;
1002 new_buf = c;
1003 new_len = clen;
1007 if (alc != NULL)
1008 backtrace_free (state, alc, alc_len, error_callback, data);
1009 alc = new_buf;
1010 alc_len = new_len;
1013 /* Look for DEBUGLINK_NAME in the same directory as FILENAME. */
1015 slash = strrchr (filename, '/');
1016 if (slash == NULL)
1018 prefix = "";
1019 prefix_len = 0;
1021 else
1023 slash++;
1024 prefix = filename;
1025 prefix_len = slash - filename;
1028 ddescriptor = elf_try_debugfile (state, prefix, prefix_len, "", 0,
1029 debuglink_name, error_callback, data);
1030 if (ddescriptor >= 0)
1032 ret = ddescriptor;
1033 goto done;
1036 /* Look for DEBUGLINK_NAME in a .debug subdirectory of FILENAME. */
1038 ddescriptor = elf_try_debugfile (state, prefix, prefix_len, ".debug/",
1039 strlen (".debug/"), debuglink_name,
1040 error_callback, data);
1041 if (ddescriptor >= 0)
1043 ret = ddescriptor;
1044 goto done;
1047 /* Look for DEBUGLINK_NAME in /usr/lib/debug. */
1049 ddescriptor = elf_try_debugfile (state, "/usr/lib/debug/",
1050 strlen ("/usr/lib/debug/"), prefix,
1051 prefix_len, debuglink_name,
1052 error_callback, data);
1053 if (ddescriptor >= 0)
1054 ret = ddescriptor;
1056 done:
1057 if (alc != NULL && alc_len > 0)
1058 backtrace_free (state, alc, alc_len, error_callback, data);
1059 return ret;
1062 /* Open a separate debug info file, using the debuglink section data
1063 to find it. Returns an open file descriptor, or -1. */
1065 static int
1066 elf_open_debugfile_by_debuglink (struct backtrace_state *state,
1067 const char *filename,
1068 const char *debuglink_name,
1069 uint32_t debuglink_crc,
1070 backtrace_error_callback error_callback,
1071 void *data)
1073 int ddescriptor;
1075 ddescriptor = elf_find_debugfile_by_debuglink (state, filename,
1076 debuglink_name,
1077 error_callback, data);
1078 if (ddescriptor < 0)
1079 return -1;
1081 if (debuglink_crc != 0)
1083 uint32_t got_crc;
1085 got_crc = elf_crc32_file (state, ddescriptor, error_callback, data);
1086 if (got_crc != debuglink_crc)
1088 backtrace_close (ddescriptor, error_callback, data);
1089 return -1;
1093 return ddescriptor;
1096 /* A function useful for setting a breakpoint for an inflation failure
1097 when this code is compiled with -g. */
1099 static void
1100 elf_uncompress_failed(void)
1104 /* *PVAL is the current value being read from the stream, and *PBITS
1105 is the number of valid bits. Ensure that *PVAL holds at least 15
1106 bits by reading additional bits from *PPIN, up to PINEND, as
1107 needed. Updates *PPIN, *PVAL and *PBITS. Returns 1 on success, 0
1108 on error. */
1110 static int
1111 elf_zlib_fetch (const unsigned char **ppin, const unsigned char *pinend,
1112 uint64_t *pval, unsigned int *pbits)
1114 unsigned int bits;
1115 const unsigned char *pin;
1116 uint64_t val;
1117 uint32_t next;
1119 bits = *pbits;
1120 if (bits >= 15)
1121 return 1;
1122 pin = *ppin;
1123 val = *pval;
1125 if (unlikely (pinend - pin < 4))
1127 elf_uncompress_failed ();
1128 return 0;
1131 #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) \
1132 && defined(__ORDER_BIG_ENDIAN__) \
1133 && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ \
1134 || __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1135 /* We've ensured that PIN is aligned. */
1136 next = *(const uint32_t *)pin;
1138 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
1139 next = __builtin_bswap32 (next);
1140 #endif
1141 #else
1142 next = pin[0] | (pin[1] << 8) | (pin[2] << 16) | (pin[3] << 24);
1143 #endif
1145 val |= (uint64_t)next << bits;
1146 bits += 32;
1147 pin += 4;
1149 /* We will need the next four bytes soon. */
1150 __builtin_prefetch (pin, 0, 0);
1152 *ppin = pin;
1153 *pval = val;
1154 *pbits = bits;
1155 return 1;
1158 /* Huffman code tables, like the rest of the zlib format, are defined
1159 by RFC 1951. We store a Huffman code table as a series of tables
1160 stored sequentially in memory. Each entry in a table is 16 bits.
1161 The first, main, table has 256 entries. It is followed by a set of
1162 secondary tables of length 2 to 128 entries. The maximum length of
1163 a code sequence in the deflate format is 15 bits, so that is all we
1164 need. Each secondary table has an index, which is the offset of
1165 the table in the overall memory storage.
1167 The deflate format says that all codes of a given bit length are
1168 lexicographically consecutive. Perhaps we could have 130 values
1169 that require a 15-bit code, perhaps requiring three secondary
1170 tables of size 128. I don't know if this is actually possible, but
1171 it suggests that the maximum size required for secondary tables is
1172 3 * 128 + 3 * 64 ... == 768. The zlib enough program reports 660
1173 as the maximum. We permit 768, since in addition to the 256 for
1174 the primary table, with two bytes per entry, and with the two
1175 tables we need, that gives us a page.
1177 A single table entry needs to store a value or (for the main table
1178 only) the index and size of a secondary table. Values range from 0
1179 to 285, inclusive. Secondary table indexes, per above, range from
1180 0 to 510. For a value we need to store the number of bits we need
1181 to determine that value (one value may appear multiple times in the
1182 table), which is 1 to 8. For a secondary table we need to store
1183 the number of bits used to index into the table, which is 1 to 7.
1184 And of course we need 1 bit to decide whether we have a value or a
1185 secondary table index. So each entry needs 9 bits for value/table
1186 index, 3 bits for size, 1 bit what it is. For simplicity we use 16
1187 bits per entry. */
1189 /* Number of entries we allocate to for one code table. We get a page
1190 for the two code tables we need. */
1192 #define HUFFMAN_TABLE_SIZE (1024)
1194 /* Bit masks and shifts for the values in the table. */
1196 #define HUFFMAN_VALUE_MASK 0x01ff
1197 #define HUFFMAN_BITS_SHIFT 9
1198 #define HUFFMAN_BITS_MASK 0x7
1199 #define HUFFMAN_SECONDARY_SHIFT 12
1201 /* For working memory while inflating we need two code tables, we need
1202 an array of code lengths (max value 15, so we use unsigned char),
1203 and an array of unsigned shorts used while building a table. The
1204 latter two arrays must be large enough to hold the maximum number
1205 of code lengths, which RFC 1951 defines as 286 + 30. */
1207 #define ZDEBUG_TABLE_SIZE \
1208 (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1209 + (286 + 30) * sizeof (uint16_t) \
1210 + (286 + 30) * sizeof (unsigned char))
1212 #define ZDEBUG_TABLE_CODELEN_OFFSET \
1213 (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1214 + (286 + 30) * sizeof (uint16_t))
1216 #define ZDEBUG_TABLE_WORK_OFFSET \
1217 (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t))
1219 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1221 /* Used by the main function that generates the fixed table to learn
1222 the table size. */
1223 static size_t final_next_secondary;
1225 #endif
1227 /* Build a Huffman code table from an array of lengths in CODES of
1228 length CODES_LEN. The table is stored into *TABLE. ZDEBUG_TABLE
1229 is the same as for elf_zlib_inflate, used to find some work space.
1230 Returns 1 on success, 0 on error. */
1232 static int
1233 elf_zlib_inflate_table (unsigned char *codes, size_t codes_len,
1234 uint16_t *zdebug_table, uint16_t *table)
1236 uint16_t count[16];
1237 uint16_t start[16];
1238 uint16_t prev[16];
1239 uint16_t firstcode[7];
1240 uint16_t *next;
1241 size_t i;
1242 size_t j;
1243 unsigned int code;
1244 size_t next_secondary;
1246 /* Count the number of code of each length. Set NEXT[val] to be the
1247 next value after VAL with the same bit length. */
1249 next = (uint16_t *) (((unsigned char *) zdebug_table)
1250 + ZDEBUG_TABLE_WORK_OFFSET);
1252 memset (&count[0], 0, 16 * sizeof (uint16_t));
1253 for (i = 0; i < codes_len; ++i)
1255 if (unlikely (codes[i] >= 16))
1257 elf_uncompress_failed ();
1258 return 0;
1261 if (count[codes[i]] == 0)
1263 start[codes[i]] = i;
1264 prev[codes[i]] = i;
1266 else
1268 next[prev[codes[i]]] = i;
1269 prev[codes[i]] = i;
1272 ++count[codes[i]];
1275 /* For each length, fill in the table for the codes of that
1276 length. */
1278 memset (table, 0, HUFFMAN_TABLE_SIZE * sizeof (uint16_t));
1280 /* Handle the values that do not require a secondary table. */
1282 code = 0;
1283 for (j = 1; j <= 8; ++j)
1285 unsigned int jcnt;
1286 unsigned int val;
1288 jcnt = count[j];
1289 if (jcnt == 0)
1290 continue;
1292 if (unlikely (jcnt > (1U << j)))
1294 elf_uncompress_failed ();
1295 return 0;
1298 /* There are JCNT values that have this length, the values
1299 starting from START[j] continuing through NEXT[VAL]. Those
1300 values are assigned consecutive values starting at CODE. */
1302 val = start[j];
1303 for (i = 0; i < jcnt; ++i)
1305 uint16_t tval;
1306 size_t ind;
1307 unsigned int incr;
1309 /* In the compressed bit stream, the value VAL is encoded as
1310 J bits with the value C. */
1312 if (unlikely ((val & ~HUFFMAN_VALUE_MASK) != 0))
1314 elf_uncompress_failed ();
1315 return 0;
1318 tval = val | ((j - 1) << HUFFMAN_BITS_SHIFT);
1320 /* The table lookup uses 8 bits. If J is less than 8, we
1321 don't know what the other bits will be. We need to fill
1322 in all possibilities in the table. Since the Huffman
1323 code is unambiguous, those entries can't be used for any
1324 other code. */
1326 for (ind = code; ind < 0x100; ind += 1 << j)
1328 if (unlikely (table[ind] != 0))
1330 elf_uncompress_failed ();
1331 return 0;
1333 table[ind] = tval;
1336 /* Advance to the next value with this length. */
1337 if (i + 1 < jcnt)
1338 val = next[val];
1340 /* The Huffman codes are stored in the bitstream with the
1341 most significant bit first, as is required to make them
1342 unambiguous. The effect is that when we read them from
1343 the bitstream we see the bit sequence in reverse order:
1344 the most significant bit of the Huffman code is the least
1345 significant bit of the value we read from the bitstream.
1346 That means that to make our table lookups work, we need
1347 to reverse the bits of CODE. Since reversing bits is
1348 tedious and in general requires using a table, we instead
1349 increment CODE in reverse order. That is, if the number
1350 of bits we are currently using, here named J, is 3, we
1351 count as 000, 100, 010, 110, 001, 101, 011, 111, which is
1352 to say the numbers from 0 to 7 but with the bits
1353 reversed. Going to more bits, aka incrementing J,
1354 effectively just adds more zero bits as the beginning,
1355 and as such does not change the numeric value of CODE.
1357 To increment CODE of length J in reverse order, find the
1358 most significant zero bit and set it to one while
1359 clearing all higher bits. In other words, add 1 modulo
1360 2^J, only reversed. */
1362 incr = 1U << (j - 1);
1363 while ((code & incr) != 0)
1364 incr >>= 1;
1365 if (incr == 0)
1366 code = 0;
1367 else
1369 code &= incr - 1;
1370 code += incr;
1375 /* Handle the values that require a secondary table. */
1377 /* Set FIRSTCODE, the number at which the codes start, for each
1378 length. */
1380 for (j = 9; j < 16; j++)
1382 unsigned int jcnt;
1383 unsigned int k;
1385 jcnt = count[j];
1386 if (jcnt == 0)
1387 continue;
1389 /* There are JCNT values that have this length, the values
1390 starting from START[j]. Those values are assigned
1391 consecutive values starting at CODE. */
1393 firstcode[j - 9] = code;
1395 /* Reverse add JCNT to CODE modulo 2^J. */
1396 for (k = 0; k < j; ++k)
1398 if ((jcnt & (1U << k)) != 0)
1400 unsigned int m;
1401 unsigned int bit;
1403 bit = 1U << (j - k - 1);
1404 for (m = 0; m < j - k; ++m, bit >>= 1)
1406 if ((code & bit) == 0)
1408 code += bit;
1409 break;
1411 code &= ~bit;
1413 jcnt &= ~(1U << k);
1416 if (unlikely (jcnt != 0))
1418 elf_uncompress_failed ();
1419 return 0;
1423 /* For J from 9 to 15, inclusive, we store COUNT[J] consecutive
1424 values starting at START[J] with consecutive codes starting at
1425 FIRSTCODE[J - 9]. In the primary table we need to point to the
1426 secondary table, and the secondary table will be indexed by J - 9
1427 bits. We count down from 15 so that we install the larger
1428 secondary tables first, as the smaller ones may be embedded in
1429 the larger ones. */
1431 next_secondary = 0; /* Index of next secondary table (after primary). */
1432 for (j = 15; j >= 9; j--)
1434 unsigned int jcnt;
1435 unsigned int val;
1436 size_t primary; /* Current primary index. */
1437 size_t secondary; /* Offset to current secondary table. */
1438 size_t secondary_bits; /* Bit size of current secondary table. */
1440 jcnt = count[j];
1441 if (jcnt == 0)
1442 continue;
1444 val = start[j];
1445 code = firstcode[j - 9];
1446 primary = 0x100;
1447 secondary = 0;
1448 secondary_bits = 0;
1449 for (i = 0; i < jcnt; ++i)
1451 uint16_t tval;
1452 size_t ind;
1453 unsigned int incr;
1455 if ((code & 0xff) != primary)
1457 uint16_t tprimary;
1459 /* Fill in a new primary table entry. */
1461 primary = code & 0xff;
1463 tprimary = table[primary];
1464 if (tprimary == 0)
1466 /* Start a new secondary table. */
1468 if (unlikely ((next_secondary & HUFFMAN_VALUE_MASK)
1469 != next_secondary))
1471 elf_uncompress_failed ();
1472 return 0;
1475 secondary = next_secondary;
1476 secondary_bits = j - 8;
1477 next_secondary += 1 << secondary_bits;
1478 table[primary] = (secondary
1479 + ((j - 8) << HUFFMAN_BITS_SHIFT)
1480 + (1U << HUFFMAN_SECONDARY_SHIFT));
1482 else
1484 /* There is an existing entry. It had better be a
1485 secondary table with enough bits. */
1486 if (unlikely ((tprimary & (1U << HUFFMAN_SECONDARY_SHIFT))
1487 == 0))
1489 elf_uncompress_failed ();
1490 return 0;
1492 secondary = tprimary & HUFFMAN_VALUE_MASK;
1493 secondary_bits = ((tprimary >> HUFFMAN_BITS_SHIFT)
1494 & HUFFMAN_BITS_MASK);
1495 if (unlikely (secondary_bits < j - 8))
1497 elf_uncompress_failed ();
1498 return 0;
1503 /* Fill in secondary table entries. */
1505 tval = val | ((j - 8) << HUFFMAN_BITS_SHIFT);
1507 for (ind = code >> 8;
1508 ind < (1U << secondary_bits);
1509 ind += 1U << (j - 8))
1511 if (unlikely (table[secondary + 0x100 + ind] != 0))
1513 elf_uncompress_failed ();
1514 return 0;
1516 table[secondary + 0x100 + ind] = tval;
1519 if (i + 1 < jcnt)
1520 val = next[val];
1522 incr = 1U << (j - 1);
1523 while ((code & incr) != 0)
1524 incr >>= 1;
1525 if (incr == 0)
1526 code = 0;
1527 else
1529 code &= incr - 1;
1530 code += incr;
1535 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1536 final_next_secondary = next_secondary;
1537 #endif
1539 return 1;
1542 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1544 /* Used to generate the fixed Huffman table for block type 1. */
1546 #include <stdio.h>
1548 static uint16_t table[ZDEBUG_TABLE_SIZE];
1549 static unsigned char codes[288];
1552 main ()
1554 size_t i;
1556 for (i = 0; i <= 143; ++i)
1557 codes[i] = 8;
1558 for (i = 144; i <= 255; ++i)
1559 codes[i] = 9;
1560 for (i = 256; i <= 279; ++i)
1561 codes[i] = 7;
1562 for (i = 280; i <= 287; ++i)
1563 codes[i] = 8;
1564 if (!elf_zlib_inflate_table (&codes[0], 288, &table[0], &table[0]))
1566 fprintf (stderr, "elf_zlib_inflate_table failed\n");
1567 exit (EXIT_FAILURE);
1570 printf ("static const uint16_t elf_zlib_default_table[%#zx] =\n",
1571 final_next_secondary + 0x100);
1572 printf ("{\n");
1573 for (i = 0; i < final_next_secondary + 0x100; i += 8)
1575 size_t j;
1577 printf (" ");
1578 for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1579 printf (" %#x,", table[j]);
1580 printf ("\n");
1582 printf ("};\n");
1583 printf ("\n");
1585 for (i = 0; i < 32; ++i)
1586 codes[i] = 5;
1587 if (!elf_zlib_inflate_table (&codes[0], 32, &table[0], &table[0]))
1589 fprintf (stderr, "elf_zlib_inflate_table failed\n");
1590 exit (EXIT_FAILURE);
1593 printf ("static const uint16_t elf_zlib_default_dist_table[%#zx] =\n",
1594 final_next_secondary + 0x100);
1595 printf ("{\n");
1596 for (i = 0; i < final_next_secondary + 0x100; i += 8)
1598 size_t j;
1600 printf (" ");
1601 for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1602 printf (" %#x,", table[j]);
1603 printf ("\n");
1605 printf ("};\n");
1607 return 0;
1610 #endif
1612 /* The fixed tables generated by the #ifdef'ed out main function
1613 above. */
1615 static const uint16_t elf_zlib_default_table[0x170] =
1617 0xd00, 0xe50, 0xe10, 0xf18, 0xd10, 0xe70, 0xe30, 0x1230,
1618 0xd08, 0xe60, 0xe20, 0x1210, 0xe00, 0xe80, 0xe40, 0x1250,
1619 0xd04, 0xe58, 0xe18, 0x1200, 0xd14, 0xe78, 0xe38, 0x1240,
1620 0xd0c, 0xe68, 0xe28, 0x1220, 0xe08, 0xe88, 0xe48, 0x1260,
1621 0xd02, 0xe54, 0xe14, 0xf1c, 0xd12, 0xe74, 0xe34, 0x1238,
1622 0xd0a, 0xe64, 0xe24, 0x1218, 0xe04, 0xe84, 0xe44, 0x1258,
1623 0xd06, 0xe5c, 0xe1c, 0x1208, 0xd16, 0xe7c, 0xe3c, 0x1248,
1624 0xd0e, 0xe6c, 0xe2c, 0x1228, 0xe0c, 0xe8c, 0xe4c, 0x1268,
1625 0xd01, 0xe52, 0xe12, 0xf1a, 0xd11, 0xe72, 0xe32, 0x1234,
1626 0xd09, 0xe62, 0xe22, 0x1214, 0xe02, 0xe82, 0xe42, 0x1254,
1627 0xd05, 0xe5a, 0xe1a, 0x1204, 0xd15, 0xe7a, 0xe3a, 0x1244,
1628 0xd0d, 0xe6a, 0xe2a, 0x1224, 0xe0a, 0xe8a, 0xe4a, 0x1264,
1629 0xd03, 0xe56, 0xe16, 0xf1e, 0xd13, 0xe76, 0xe36, 0x123c,
1630 0xd0b, 0xe66, 0xe26, 0x121c, 0xe06, 0xe86, 0xe46, 0x125c,
1631 0xd07, 0xe5e, 0xe1e, 0x120c, 0xd17, 0xe7e, 0xe3e, 0x124c,
1632 0xd0f, 0xe6e, 0xe2e, 0x122c, 0xe0e, 0xe8e, 0xe4e, 0x126c,
1633 0xd00, 0xe51, 0xe11, 0xf19, 0xd10, 0xe71, 0xe31, 0x1232,
1634 0xd08, 0xe61, 0xe21, 0x1212, 0xe01, 0xe81, 0xe41, 0x1252,
1635 0xd04, 0xe59, 0xe19, 0x1202, 0xd14, 0xe79, 0xe39, 0x1242,
1636 0xd0c, 0xe69, 0xe29, 0x1222, 0xe09, 0xe89, 0xe49, 0x1262,
1637 0xd02, 0xe55, 0xe15, 0xf1d, 0xd12, 0xe75, 0xe35, 0x123a,
1638 0xd0a, 0xe65, 0xe25, 0x121a, 0xe05, 0xe85, 0xe45, 0x125a,
1639 0xd06, 0xe5d, 0xe1d, 0x120a, 0xd16, 0xe7d, 0xe3d, 0x124a,
1640 0xd0e, 0xe6d, 0xe2d, 0x122a, 0xe0d, 0xe8d, 0xe4d, 0x126a,
1641 0xd01, 0xe53, 0xe13, 0xf1b, 0xd11, 0xe73, 0xe33, 0x1236,
1642 0xd09, 0xe63, 0xe23, 0x1216, 0xe03, 0xe83, 0xe43, 0x1256,
1643 0xd05, 0xe5b, 0xe1b, 0x1206, 0xd15, 0xe7b, 0xe3b, 0x1246,
1644 0xd0d, 0xe6b, 0xe2b, 0x1226, 0xe0b, 0xe8b, 0xe4b, 0x1266,
1645 0xd03, 0xe57, 0xe17, 0xf1f, 0xd13, 0xe77, 0xe37, 0x123e,
1646 0xd0b, 0xe67, 0xe27, 0x121e, 0xe07, 0xe87, 0xe47, 0x125e,
1647 0xd07, 0xe5f, 0xe1f, 0x120e, 0xd17, 0xe7f, 0xe3f, 0x124e,
1648 0xd0f, 0xe6f, 0xe2f, 0x122e, 0xe0f, 0xe8f, 0xe4f, 0x126e,
1649 0x290, 0x291, 0x292, 0x293, 0x294, 0x295, 0x296, 0x297,
1650 0x298, 0x299, 0x29a, 0x29b, 0x29c, 0x29d, 0x29e, 0x29f,
1651 0x2a0, 0x2a1, 0x2a2, 0x2a3, 0x2a4, 0x2a5, 0x2a6, 0x2a7,
1652 0x2a8, 0x2a9, 0x2aa, 0x2ab, 0x2ac, 0x2ad, 0x2ae, 0x2af,
1653 0x2b0, 0x2b1, 0x2b2, 0x2b3, 0x2b4, 0x2b5, 0x2b6, 0x2b7,
1654 0x2b8, 0x2b9, 0x2ba, 0x2bb, 0x2bc, 0x2bd, 0x2be, 0x2bf,
1655 0x2c0, 0x2c1, 0x2c2, 0x2c3, 0x2c4, 0x2c5, 0x2c6, 0x2c7,
1656 0x2c8, 0x2c9, 0x2ca, 0x2cb, 0x2cc, 0x2cd, 0x2ce, 0x2cf,
1657 0x2d0, 0x2d1, 0x2d2, 0x2d3, 0x2d4, 0x2d5, 0x2d6, 0x2d7,
1658 0x2d8, 0x2d9, 0x2da, 0x2db, 0x2dc, 0x2dd, 0x2de, 0x2df,
1659 0x2e0, 0x2e1, 0x2e2, 0x2e3, 0x2e4, 0x2e5, 0x2e6, 0x2e7,
1660 0x2e8, 0x2e9, 0x2ea, 0x2eb, 0x2ec, 0x2ed, 0x2ee, 0x2ef,
1661 0x2f0, 0x2f1, 0x2f2, 0x2f3, 0x2f4, 0x2f5, 0x2f6, 0x2f7,
1662 0x2f8, 0x2f9, 0x2fa, 0x2fb, 0x2fc, 0x2fd, 0x2fe, 0x2ff,
1665 static const uint16_t elf_zlib_default_dist_table[0x100] =
1667 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1668 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1669 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1670 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1671 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1672 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1673 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1674 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1675 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1676 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1677 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1678 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1679 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1680 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1681 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1682 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1683 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1684 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1685 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1686 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1687 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1688 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1689 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1690 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1691 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1692 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1693 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1694 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1695 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1696 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1697 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1698 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1701 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT. Return 1 on
1702 success, 0 on some error parsing the stream. */
1704 static int
1705 elf_zlib_inflate (const unsigned char *pin, size_t sin, uint16_t *zdebug_table,
1706 unsigned char *pout, size_t sout)
1708 unsigned char *porigout;
1709 const unsigned char *pinend;
1710 unsigned char *poutend;
1712 /* We can apparently see multiple zlib streams concatenated
1713 together, so keep going as long as there is something to read.
1714 The last 4 bytes are the checksum. */
1715 porigout = pout;
1716 pinend = pin + sin;
1717 poutend = pout + sout;
1718 while ((pinend - pin) > 4)
1720 uint64_t val;
1721 unsigned int bits;
1722 int last;
1724 /* Read the two byte zlib header. */
1726 if (unlikely ((pin[0] & 0xf) != 8)) /* 8 is zlib encoding. */
1728 /* Unknown compression method. */
1729 elf_uncompress_failed ();
1730 return 0;
1732 if (unlikely ((pin[0] >> 4) > 7))
1734 /* Window size too large. Other than this check, we don't
1735 care about the window size. */
1736 elf_uncompress_failed ();
1737 return 0;
1739 if (unlikely ((pin[1] & 0x20) != 0))
1741 /* Stream expects a predefined dictionary, but we have no
1742 dictionary. */
1743 elf_uncompress_failed ();
1744 return 0;
1746 val = (pin[0] << 8) | pin[1];
1747 if (unlikely (val % 31 != 0))
1749 /* Header check failure. */
1750 elf_uncompress_failed ();
1751 return 0;
1753 pin += 2;
1755 /* Align PIN to a 32-bit boundary. */
1757 val = 0;
1758 bits = 0;
1759 while ((((uintptr_t) pin) & 3) != 0)
1761 val |= (uint64_t)*pin << bits;
1762 bits += 8;
1763 ++pin;
1766 /* Read blocks until one is marked last. */
1768 last = 0;
1770 while (!last)
1772 unsigned int type;
1773 const uint16_t *tlit;
1774 const uint16_t *tdist;
1776 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1777 return 0;
1779 last = val & 1;
1780 type = (val >> 1) & 3;
1781 val >>= 3;
1782 bits -= 3;
1784 if (unlikely (type == 3))
1786 /* Invalid block type. */
1787 elf_uncompress_failed ();
1788 return 0;
1791 if (type == 0)
1793 uint16_t len;
1794 uint16_t lenc;
1796 /* An uncompressed block. */
1798 /* If we've read ahead more than a byte, back up. */
1799 while (bits > 8)
1801 --pin;
1802 bits -= 8;
1805 val = 0;
1806 bits = 0;
1807 if (unlikely ((pinend - pin) < 4))
1809 /* Missing length. */
1810 elf_uncompress_failed ();
1811 return 0;
1813 len = pin[0] | (pin[1] << 8);
1814 lenc = pin[2] | (pin[3] << 8);
1815 pin += 4;
1816 lenc = ~lenc;
1817 if (unlikely (len != lenc))
1819 /* Corrupt data. */
1820 elf_uncompress_failed ();
1821 return 0;
1823 if (unlikely (len > (unsigned int) (pinend - pin)
1824 || len > (unsigned int) (poutend - pout)))
1826 /* Not enough space in buffers. */
1827 elf_uncompress_failed ();
1828 return 0;
1830 memcpy (pout, pin, len);
1831 pout += len;
1832 pin += len;
1834 /* Align PIN. */
1835 while ((((uintptr_t) pin) & 3) != 0)
1837 val |= (uint64_t)*pin << bits;
1838 bits += 8;
1839 ++pin;
1842 /* Go around to read the next block. */
1843 continue;
1846 if (type == 1)
1848 tlit = elf_zlib_default_table;
1849 tdist = elf_zlib_default_dist_table;
1851 else
1853 unsigned int nlit;
1854 unsigned int ndist;
1855 unsigned int nclen;
1856 unsigned char codebits[19];
1857 unsigned char *plenbase;
1858 unsigned char *plen;
1859 unsigned char *plenend;
1861 /* Read a Huffman encoding table. The various magic
1862 numbers here are from RFC 1951. */
1864 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1865 return 0;
1867 nlit = (val & 0x1f) + 257;
1868 val >>= 5;
1869 ndist = (val & 0x1f) + 1;
1870 val >>= 5;
1871 nclen = (val & 0xf) + 4;
1872 val >>= 4;
1873 bits -= 14;
1874 if (unlikely (nlit > 286 || ndist > 30))
1876 /* Values out of range. */
1877 elf_uncompress_failed ();
1878 return 0;
1881 /* Read and build the table used to compress the
1882 literal, length, and distance codes. */
1884 memset(&codebits[0], 0, 19);
1886 /* There are always at least 4 elements in the
1887 table. */
1889 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1890 return 0;
1892 codebits[16] = val & 7;
1893 codebits[17] = (val >> 3) & 7;
1894 codebits[18] = (val >> 6) & 7;
1895 codebits[0] = (val >> 9) & 7;
1896 val >>= 12;
1897 bits -= 12;
1899 if (nclen == 4)
1900 goto codebitsdone;
1902 codebits[8] = val & 7;
1903 val >>= 3;
1904 bits -= 3;
1906 if (nclen == 5)
1907 goto codebitsdone;
1909 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1910 return 0;
1912 codebits[7] = val & 7;
1913 val >>= 3;
1914 bits -= 3;
1916 if (nclen == 6)
1917 goto codebitsdone;
1919 codebits[9] = val & 7;
1920 val >>= 3;
1921 bits -= 3;
1923 if (nclen == 7)
1924 goto codebitsdone;
1926 codebits[6] = val & 7;
1927 val >>= 3;
1928 bits -= 3;
1930 if (nclen == 8)
1931 goto codebitsdone;
1933 codebits[10] = val & 7;
1934 val >>= 3;
1935 bits -= 3;
1937 if (nclen == 9)
1938 goto codebitsdone;
1940 codebits[5] = val & 7;
1941 val >>= 3;
1942 bits -= 3;
1944 if (nclen == 10)
1945 goto codebitsdone;
1947 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1948 return 0;
1950 codebits[11] = val & 7;
1951 val >>= 3;
1952 bits -= 3;
1954 if (nclen == 11)
1955 goto codebitsdone;
1957 codebits[4] = val & 7;
1958 val >>= 3;
1959 bits -= 3;
1961 if (nclen == 12)
1962 goto codebitsdone;
1964 codebits[12] = val & 7;
1965 val >>= 3;
1966 bits -= 3;
1968 if (nclen == 13)
1969 goto codebitsdone;
1971 codebits[3] = val & 7;
1972 val >>= 3;
1973 bits -= 3;
1975 if (nclen == 14)
1976 goto codebitsdone;
1978 codebits[13] = val & 7;
1979 val >>= 3;
1980 bits -= 3;
1982 if (nclen == 15)
1983 goto codebitsdone;
1985 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1986 return 0;
1988 codebits[2] = val & 7;
1989 val >>= 3;
1990 bits -= 3;
1992 if (nclen == 16)
1993 goto codebitsdone;
1995 codebits[14] = val & 7;
1996 val >>= 3;
1997 bits -= 3;
1999 if (nclen == 17)
2000 goto codebitsdone;
2002 codebits[1] = val & 7;
2003 val >>= 3;
2004 bits -= 3;
2006 if (nclen == 18)
2007 goto codebitsdone;
2009 codebits[15] = val & 7;
2010 val >>= 3;
2011 bits -= 3;
2013 codebitsdone:
2015 if (!elf_zlib_inflate_table (codebits, 19, zdebug_table,
2016 zdebug_table))
2017 return 0;
2019 /* Read the compressed bit lengths of the literal,
2020 length, and distance codes. We have allocated space
2021 at the end of zdebug_table to hold them. */
2023 plenbase = (((unsigned char *) zdebug_table)
2024 + ZDEBUG_TABLE_CODELEN_OFFSET);
2025 plen = plenbase;
2026 plenend = plen + nlit + ndist;
2027 while (plen < plenend)
2029 uint16_t t;
2030 unsigned int b;
2031 uint16_t v;
2033 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2034 return 0;
2036 t = zdebug_table[val & 0xff];
2038 /* The compression here uses bit lengths up to 7, so
2039 a secondary table is never necessary. */
2040 if (unlikely ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) != 0))
2042 elf_uncompress_failed ();
2043 return 0;
2046 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2047 val >>= b + 1;
2048 bits -= b + 1;
2050 v = t & HUFFMAN_VALUE_MASK;
2051 if (v < 16)
2052 *plen++ = v;
2053 else if (v == 16)
2055 unsigned int c;
2056 unsigned int prev;
2058 /* Copy previous entry 3 to 6 times. */
2060 if (unlikely (plen == plenbase))
2062 elf_uncompress_failed ();
2063 return 0;
2066 /* We used up to 7 bits since the last
2067 elf_zlib_fetch, so we have at least 8 bits
2068 available here. */
2070 c = 3 + (val & 0x3);
2071 val >>= 2;
2072 bits -= 2;
2073 if (unlikely ((unsigned int) (plenend - plen) < c))
2075 elf_uncompress_failed ();
2076 return 0;
2079 prev = plen[-1];
2080 switch (c)
2082 case 6:
2083 *plen++ = prev;
2084 ATTRIBUTE_FALLTHROUGH;
2085 case 5:
2086 *plen++ = prev;
2087 ATTRIBUTE_FALLTHROUGH;
2088 case 4:
2089 *plen++ = prev;
2091 *plen++ = prev;
2092 *plen++ = prev;
2093 *plen++ = prev;
2095 else if (v == 17)
2097 unsigned int c;
2099 /* Store zero 3 to 10 times. */
2101 /* We used up to 7 bits since the last
2102 elf_zlib_fetch, so we have at least 8 bits
2103 available here. */
2105 c = 3 + (val & 0x7);
2106 val >>= 3;
2107 bits -= 3;
2108 if (unlikely ((unsigned int) (plenend - plen) < c))
2110 elf_uncompress_failed ();
2111 return 0;
2114 switch (c)
2116 case 10:
2117 *plen++ = 0;
2118 ATTRIBUTE_FALLTHROUGH;
2119 case 9:
2120 *plen++ = 0;
2121 ATTRIBUTE_FALLTHROUGH;
2122 case 8:
2123 *plen++ = 0;
2124 ATTRIBUTE_FALLTHROUGH;
2125 case 7:
2126 *plen++ = 0;
2127 ATTRIBUTE_FALLTHROUGH;
2128 case 6:
2129 *plen++ = 0;
2130 ATTRIBUTE_FALLTHROUGH;
2131 case 5:
2132 *plen++ = 0;
2133 ATTRIBUTE_FALLTHROUGH;
2134 case 4:
2135 *plen++ = 0;
2137 *plen++ = 0;
2138 *plen++ = 0;
2139 *plen++ = 0;
2141 else if (v == 18)
2143 unsigned int c;
2145 /* Store zero 11 to 138 times. */
2147 /* We used up to 7 bits since the last
2148 elf_zlib_fetch, so we have at least 8 bits
2149 available here. */
2151 c = 11 + (val & 0x7f);
2152 val >>= 7;
2153 bits -= 7;
2154 if (unlikely ((unsigned int) (plenend - plen) < c))
2156 elf_uncompress_failed ();
2157 return 0;
2160 memset (plen, 0, c);
2161 plen += c;
2163 else
2165 elf_uncompress_failed ();
2166 return 0;
2170 /* Make sure that the stop code can appear. */
2172 plen = plenbase;
2173 if (unlikely (plen[256] == 0))
2175 elf_uncompress_failed ();
2176 return 0;
2179 /* Build the decompression tables. */
2181 if (!elf_zlib_inflate_table (plen, nlit, zdebug_table,
2182 zdebug_table))
2183 return 0;
2184 if (!elf_zlib_inflate_table (plen + nlit, ndist, zdebug_table,
2185 zdebug_table + HUFFMAN_TABLE_SIZE))
2186 return 0;
2187 tlit = zdebug_table;
2188 tdist = zdebug_table + HUFFMAN_TABLE_SIZE;
2191 /* Inflate values until the end of the block. This is the
2192 main loop of the inflation code. */
2194 while (1)
2196 uint16_t t;
2197 unsigned int b;
2198 uint16_t v;
2199 unsigned int lit;
2201 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2202 return 0;
2204 t = tlit[val & 0xff];
2205 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2206 v = t & HUFFMAN_VALUE_MASK;
2208 if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2210 lit = v;
2211 val >>= b + 1;
2212 bits -= b + 1;
2214 else
2216 t = tlit[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2217 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2218 lit = t & HUFFMAN_VALUE_MASK;
2219 val >>= b + 8;
2220 bits -= b + 8;
2223 if (lit < 256)
2225 if (unlikely (pout == poutend))
2227 elf_uncompress_failed ();
2228 return 0;
2231 *pout++ = lit;
2233 /* We will need to write the next byte soon. We ask
2234 for high temporal locality because we will write
2235 to the whole cache line soon. */
2236 __builtin_prefetch (pout, 1, 3);
2238 else if (lit == 256)
2240 /* The end of the block. */
2241 break;
2243 else
2245 unsigned int dist;
2246 unsigned int len;
2248 /* Convert lit into a length. */
2250 if (lit < 265)
2251 len = lit - 257 + 3;
2252 else if (lit == 285)
2253 len = 258;
2254 else if (unlikely (lit > 285))
2256 elf_uncompress_failed ();
2257 return 0;
2259 else
2261 unsigned int extra;
2263 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2264 return 0;
2266 /* This is an expression for the table of length
2267 codes in RFC 1951 3.2.5. */
2268 lit -= 265;
2269 extra = (lit >> 2) + 1;
2270 len = (lit & 3) << extra;
2271 len += 11;
2272 len += ((1U << (extra - 1)) - 1) << 3;
2273 len += val & ((1U << extra) - 1);
2274 val >>= extra;
2275 bits -= extra;
2278 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2279 return 0;
2281 t = tdist[val & 0xff];
2282 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2283 v = t & HUFFMAN_VALUE_MASK;
2285 if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2287 dist = v;
2288 val >>= b + 1;
2289 bits -= b + 1;
2291 else
2293 t = tdist[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2294 b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2295 dist = t & HUFFMAN_VALUE_MASK;
2296 val >>= b + 8;
2297 bits -= b + 8;
2300 /* Convert dist to a distance. */
2302 if (dist == 0)
2304 /* A distance of 1. A common case, meaning
2305 repeat the last character LEN times. */
2307 if (unlikely (pout == porigout))
2309 elf_uncompress_failed ();
2310 return 0;
2313 if (unlikely ((unsigned int) (poutend - pout) < len))
2315 elf_uncompress_failed ();
2316 return 0;
2319 memset (pout, pout[-1], len);
2320 pout += len;
2322 else if (unlikely (dist > 29))
2324 elf_uncompress_failed ();
2325 return 0;
2327 else
2329 if (dist < 4)
2330 dist = dist + 1;
2331 else
2333 unsigned int extra;
2335 if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2336 return 0;
2338 /* This is an expression for the table of
2339 distance codes in RFC 1951 3.2.5. */
2340 dist -= 4;
2341 extra = (dist >> 1) + 1;
2342 dist = (dist & 1) << extra;
2343 dist += 5;
2344 dist += ((1U << (extra - 1)) - 1) << 2;
2345 dist += val & ((1U << extra) - 1);
2346 val >>= extra;
2347 bits -= extra;
2350 /* Go back dist bytes, and copy len bytes from
2351 there. */
2353 if (unlikely ((unsigned int) (pout - porigout) < dist))
2355 elf_uncompress_failed ();
2356 return 0;
2359 if (unlikely ((unsigned int) (poutend - pout) < len))
2361 elf_uncompress_failed ();
2362 return 0;
2365 if (dist >= len)
2367 memcpy (pout, pout - dist, len);
2368 pout += len;
2370 else
2372 while (len > 0)
2374 unsigned int copy;
2376 copy = len < dist ? len : dist;
2377 memcpy (pout, pout - dist, copy);
2378 len -= copy;
2379 pout += copy;
2388 /* We should have filled the output buffer. */
2389 if (unlikely (pout != poutend))
2391 elf_uncompress_failed ();
2392 return 0;
2395 return 1;
2398 /* Verify the zlib checksum. The checksum is in the 4 bytes at
2399 CHECKBYTES, and the uncompressed data is at UNCOMPRESSED /
2400 UNCOMPRESSED_SIZE. Returns 1 on success, 0 on failure. */
2402 static int
2403 elf_zlib_verify_checksum (const unsigned char *checkbytes,
2404 const unsigned char *uncompressed,
2405 size_t uncompressed_size)
2407 unsigned int i;
2408 unsigned int cksum;
2409 const unsigned char *p;
2410 uint32_t s1;
2411 uint32_t s2;
2412 size_t hsz;
2414 cksum = 0;
2415 for (i = 0; i < 4; i++)
2416 cksum = (cksum << 8) | checkbytes[i];
2418 s1 = 1;
2419 s2 = 0;
2421 /* Minimize modulo operations. */
2423 p = uncompressed;
2424 hsz = uncompressed_size;
2425 while (hsz >= 5552)
2427 for (i = 0; i < 5552; i += 16)
2429 /* Manually unroll loop 16 times. */
2430 s1 = s1 + *p++;
2431 s2 = s2 + s1;
2432 s1 = s1 + *p++;
2433 s2 = s2 + s1;
2434 s1 = s1 + *p++;
2435 s2 = s2 + s1;
2436 s1 = s1 + *p++;
2437 s2 = s2 + s1;
2438 s1 = s1 + *p++;
2439 s2 = s2 + s1;
2440 s1 = s1 + *p++;
2441 s2 = s2 + s1;
2442 s1 = s1 + *p++;
2443 s2 = s2 + s1;
2444 s1 = s1 + *p++;
2445 s2 = s2 + s1;
2446 s1 = s1 + *p++;
2447 s2 = s2 + s1;
2448 s1 = s1 + *p++;
2449 s2 = s2 + s1;
2450 s1 = s1 + *p++;
2451 s2 = s2 + s1;
2452 s1 = s1 + *p++;
2453 s2 = s2 + s1;
2454 s1 = s1 + *p++;
2455 s2 = s2 + s1;
2456 s1 = s1 + *p++;
2457 s2 = s2 + s1;
2458 s1 = s1 + *p++;
2459 s2 = s2 + s1;
2460 s1 = s1 + *p++;
2461 s2 = s2 + s1;
2463 hsz -= 5552;
2464 s1 %= 65521;
2465 s2 %= 65521;
2468 while (hsz >= 16)
2470 /* Manually unroll loop 16 times. */
2471 s1 = s1 + *p++;
2472 s2 = s2 + s1;
2473 s1 = s1 + *p++;
2474 s2 = s2 + s1;
2475 s1 = s1 + *p++;
2476 s2 = s2 + s1;
2477 s1 = s1 + *p++;
2478 s2 = s2 + s1;
2479 s1 = s1 + *p++;
2480 s2 = s2 + s1;
2481 s1 = s1 + *p++;
2482 s2 = s2 + s1;
2483 s1 = s1 + *p++;
2484 s2 = s2 + s1;
2485 s1 = s1 + *p++;
2486 s2 = s2 + s1;
2487 s1 = s1 + *p++;
2488 s2 = s2 + s1;
2489 s1 = s1 + *p++;
2490 s2 = s2 + s1;
2491 s1 = s1 + *p++;
2492 s2 = s2 + s1;
2493 s1 = s1 + *p++;
2494 s2 = s2 + s1;
2495 s1 = s1 + *p++;
2496 s2 = s2 + s1;
2497 s1 = s1 + *p++;
2498 s2 = s2 + s1;
2499 s1 = s1 + *p++;
2500 s2 = s2 + s1;
2501 s1 = s1 + *p++;
2502 s2 = s2 + s1;
2504 hsz -= 16;
2507 for (i = 0; i < hsz; ++i)
2509 s1 = s1 + *p++;
2510 s2 = s2 + s1;
2513 s1 %= 65521;
2514 s2 %= 65521;
2516 if (unlikely ((s2 << 16) + s1 != cksum))
2518 elf_uncompress_failed ();
2519 return 0;
2522 return 1;
2525 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT, and verify the
2526 checksum. Return 1 on success, 0 on error. */
2528 static int
2529 elf_zlib_inflate_and_verify (const unsigned char *pin, size_t sin,
2530 uint16_t *zdebug_table, unsigned char *pout,
2531 size_t sout)
2533 if (!elf_zlib_inflate (pin, sin, zdebug_table, pout, sout))
2534 return 0;
2535 if (!elf_zlib_verify_checksum (pin + sin - 4, pout, sout))
2536 return 0;
2537 return 1;
2540 /* Uncompress the old compressed debug format, the one emitted by
2541 --compress-debug-sections=zlib-gnu. The compressed data is in
2542 COMPRESSED / COMPRESSED_SIZE, and the function writes to
2543 *UNCOMPRESSED / *UNCOMPRESSED_SIZE. ZDEBUG_TABLE is work space to
2544 hold Huffman tables. Returns 0 on error, 1 on successful
2545 decompression or if something goes wrong. In general we try to
2546 carry on, by returning 1, even if we can't decompress. */
2548 static int
2549 elf_uncompress_zdebug (struct backtrace_state *state,
2550 const unsigned char *compressed, size_t compressed_size,
2551 uint16_t *zdebug_table,
2552 backtrace_error_callback error_callback, void *data,
2553 unsigned char **uncompressed, size_t *uncompressed_size)
2555 size_t sz;
2556 size_t i;
2557 unsigned char *po;
2559 *uncompressed = NULL;
2560 *uncompressed_size = 0;
2562 /* The format starts with the four bytes ZLIB, followed by the 8
2563 byte length of the uncompressed data in big-endian order,
2564 followed by a zlib stream. */
2566 if (compressed_size < 12 || memcmp (compressed, "ZLIB", 4) != 0)
2567 return 1;
2569 sz = 0;
2570 for (i = 0; i < 8; i++)
2571 sz = (sz << 8) | compressed[i + 4];
2573 if (*uncompressed != NULL && *uncompressed_size >= sz)
2574 po = *uncompressed;
2575 else
2577 po = (unsigned char *) backtrace_alloc (state, sz, error_callback, data);
2578 if (po == NULL)
2579 return 0;
2582 if (!elf_zlib_inflate_and_verify (compressed + 12, compressed_size - 12,
2583 zdebug_table, po, sz))
2584 return 1;
2586 *uncompressed = po;
2587 *uncompressed_size = sz;
2589 return 1;
2592 /* Uncompress the new compressed debug format, the official standard
2593 ELF approach emitted by --compress-debug-sections=zlib-gabi. The
2594 compressed data is in COMPRESSED / COMPRESSED_SIZE, and the
2595 function writes to *UNCOMPRESSED / *UNCOMPRESSED_SIZE.
2596 ZDEBUG_TABLE is work space as for elf_uncompress_zdebug. Returns 0
2597 on error, 1 on successful decompression or if something goes wrong.
2598 In general we try to carry on, by returning 1, even if we can't
2599 decompress. */
2601 static int
2602 elf_uncompress_chdr (struct backtrace_state *state,
2603 const unsigned char *compressed, size_t compressed_size,
2604 uint16_t *zdebug_table,
2605 backtrace_error_callback error_callback, void *data,
2606 unsigned char **uncompressed, size_t *uncompressed_size)
2608 const b_elf_chdr *chdr;
2609 unsigned char *po;
2611 *uncompressed = NULL;
2612 *uncompressed_size = 0;
2614 /* The format starts with an ELF compression header. */
2615 if (compressed_size < sizeof (b_elf_chdr))
2616 return 1;
2618 chdr = (const b_elf_chdr *) compressed;
2620 if (chdr->ch_type != ELFCOMPRESS_ZLIB)
2622 /* Unsupported compression algorithm. */
2623 return 1;
2626 if (*uncompressed != NULL && *uncompressed_size >= chdr->ch_size)
2627 po = *uncompressed;
2628 else
2630 po = (unsigned char *) backtrace_alloc (state, chdr->ch_size,
2631 error_callback, data);
2632 if (po == NULL)
2633 return 0;
2636 if (!elf_zlib_inflate_and_verify (compressed + sizeof (b_elf_chdr),
2637 compressed_size - sizeof (b_elf_chdr),
2638 zdebug_table, po, chdr->ch_size))
2639 return 1;
2641 *uncompressed = po;
2642 *uncompressed_size = chdr->ch_size;
2644 return 1;
2647 /* This function is a hook for testing the zlib support. It is only
2648 used by tests. */
2651 backtrace_uncompress_zdebug (struct backtrace_state *state,
2652 const unsigned char *compressed,
2653 size_t compressed_size,
2654 backtrace_error_callback error_callback,
2655 void *data, unsigned char **uncompressed,
2656 size_t *uncompressed_size)
2658 uint16_t *zdebug_table;
2659 int ret;
2661 zdebug_table = ((uint16_t *) backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
2662 error_callback, data));
2663 if (zdebug_table == NULL)
2664 return 0;
2665 ret = elf_uncompress_zdebug (state, compressed, compressed_size,
2666 zdebug_table, error_callback, data,
2667 uncompressed, uncompressed_size);
2668 backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
2669 error_callback, data);
2670 return ret;
2673 /* Number of LZMA states. */
2674 #define LZMA_STATES (12)
2676 /* Number of LZMA position states. The pb value of the property byte
2677 is the number of bits to include in these states, and the maximum
2678 value of pb is 4. */
2679 #define LZMA_POS_STATES (16)
2681 /* Number of LZMA distance states. These are used match distances
2682 with a short match length: up to 4 bytes. */
2683 #define LZMA_DIST_STATES (4)
2685 /* Number of LZMA distance slots. LZMA uses six bits to encode larger
2686 match lengths, so 1 << 6 possible probabilities. */
2687 #define LZMA_DIST_SLOTS (64)
2689 /* LZMA distances 0 to 3 are encoded directly, larger values use a
2690 probability model. */
2691 #define LZMA_DIST_MODEL_START (4)
2693 /* The LZMA probability model ends at 14. */
2694 #define LZMA_DIST_MODEL_END (14)
2696 /* LZMA distance slots for distances less than 127. */
2697 #define LZMA_FULL_DISTANCES (128)
2699 /* LZMA uses four alignment bits. */
2700 #define LZMA_ALIGN_SIZE (16)
2702 /* LZMA match length is encoded with 4, 5, or 10 bits, some of which
2703 are already known. */
2704 #define LZMA_LEN_LOW_SYMBOLS (8)
2705 #define LZMA_LEN_MID_SYMBOLS (8)
2706 #define LZMA_LEN_HIGH_SYMBOLS (256)
2708 /* LZMA literal encoding. */
2709 #define LZMA_LITERAL_CODERS_MAX (16)
2710 #define LZMA_LITERAL_CODER_SIZE (0x300)
2712 /* LZMA is based on a large set of probabilities, each managed
2713 independently. Each probability is an 11 bit number that we store
2714 in a uint16_t. We use a single large array of probabilities. */
2716 /* Lengths of entries in the LZMA probabilities array. The names used
2717 here are copied from the Linux kernel implementation. */
2719 #define LZMA_PROB_IS_MATCH_LEN (LZMA_STATES * LZMA_POS_STATES)
2720 #define LZMA_PROB_IS_REP_LEN LZMA_STATES
2721 #define LZMA_PROB_IS_REP0_LEN LZMA_STATES
2722 #define LZMA_PROB_IS_REP1_LEN LZMA_STATES
2723 #define LZMA_PROB_IS_REP2_LEN LZMA_STATES
2724 #define LZMA_PROB_IS_REP0_LONG_LEN (LZMA_STATES * LZMA_POS_STATES)
2725 #define LZMA_PROB_DIST_SLOT_LEN (LZMA_DIST_STATES * LZMA_DIST_SLOTS)
2726 #define LZMA_PROB_DIST_SPECIAL_LEN (LZMA_FULL_DISTANCES - LZMA_DIST_MODEL_END)
2727 #define LZMA_PROB_DIST_ALIGN_LEN LZMA_ALIGN_SIZE
2728 #define LZMA_PROB_MATCH_LEN_CHOICE_LEN 1
2729 #define LZMA_PROB_MATCH_LEN_CHOICE2_LEN 1
2730 #define LZMA_PROB_MATCH_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS)
2731 #define LZMA_PROB_MATCH_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS)
2732 #define LZMA_PROB_MATCH_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS
2733 #define LZMA_PROB_REP_LEN_CHOICE_LEN 1
2734 #define LZMA_PROB_REP_LEN_CHOICE2_LEN 1
2735 #define LZMA_PROB_REP_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS)
2736 #define LZMA_PROB_REP_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS)
2737 #define LZMA_PROB_REP_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS
2738 #define LZMA_PROB_LITERAL_LEN \
2739 (LZMA_LITERAL_CODERS_MAX * LZMA_LITERAL_CODER_SIZE)
2741 /* Offsets into the LZMA probabilities array. This is mechanically
2742 generated from the above lengths. */
2744 #define LZMA_PROB_IS_MATCH_OFFSET 0
2745 #define LZMA_PROB_IS_REP_OFFSET \
2746 (LZMA_PROB_IS_MATCH_OFFSET + LZMA_PROB_IS_MATCH_LEN)
2747 #define LZMA_PROB_IS_REP0_OFFSET \
2748 (LZMA_PROB_IS_REP_OFFSET + LZMA_PROB_IS_REP_LEN)
2749 #define LZMA_PROB_IS_REP1_OFFSET \
2750 (LZMA_PROB_IS_REP0_OFFSET + LZMA_PROB_IS_REP0_LEN)
2751 #define LZMA_PROB_IS_REP2_OFFSET \
2752 (LZMA_PROB_IS_REP1_OFFSET + LZMA_PROB_IS_REP1_LEN)
2753 #define LZMA_PROB_IS_REP0_LONG_OFFSET \
2754 (LZMA_PROB_IS_REP2_OFFSET + LZMA_PROB_IS_REP2_LEN)
2755 #define LZMA_PROB_DIST_SLOT_OFFSET \
2756 (LZMA_PROB_IS_REP0_LONG_OFFSET + LZMA_PROB_IS_REP0_LONG_LEN)
2757 #define LZMA_PROB_DIST_SPECIAL_OFFSET \
2758 (LZMA_PROB_DIST_SLOT_OFFSET + LZMA_PROB_DIST_SLOT_LEN)
2759 #define LZMA_PROB_DIST_ALIGN_OFFSET \
2760 (LZMA_PROB_DIST_SPECIAL_OFFSET + LZMA_PROB_DIST_SPECIAL_LEN)
2761 #define LZMA_PROB_MATCH_LEN_CHOICE_OFFSET \
2762 (LZMA_PROB_DIST_ALIGN_OFFSET + LZMA_PROB_DIST_ALIGN_LEN)
2763 #define LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET \
2764 (LZMA_PROB_MATCH_LEN_CHOICE_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE_LEN)
2765 #define LZMA_PROB_MATCH_LEN_LOW_OFFSET \
2766 (LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE2_LEN)
2767 #define LZMA_PROB_MATCH_LEN_MID_OFFSET \
2768 (LZMA_PROB_MATCH_LEN_LOW_OFFSET + LZMA_PROB_MATCH_LEN_LOW_LEN)
2769 #define LZMA_PROB_MATCH_LEN_HIGH_OFFSET \
2770 (LZMA_PROB_MATCH_LEN_MID_OFFSET + LZMA_PROB_MATCH_LEN_MID_LEN)
2771 #define LZMA_PROB_REP_LEN_CHOICE_OFFSET \
2772 (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + LZMA_PROB_MATCH_LEN_HIGH_LEN)
2773 #define LZMA_PROB_REP_LEN_CHOICE2_OFFSET \
2774 (LZMA_PROB_REP_LEN_CHOICE_OFFSET + LZMA_PROB_REP_LEN_CHOICE_LEN)
2775 #define LZMA_PROB_REP_LEN_LOW_OFFSET \
2776 (LZMA_PROB_REP_LEN_CHOICE2_OFFSET + LZMA_PROB_REP_LEN_CHOICE2_LEN)
2777 #define LZMA_PROB_REP_LEN_MID_OFFSET \
2778 (LZMA_PROB_REP_LEN_LOW_OFFSET + LZMA_PROB_REP_LEN_LOW_LEN)
2779 #define LZMA_PROB_REP_LEN_HIGH_OFFSET \
2780 (LZMA_PROB_REP_LEN_MID_OFFSET + LZMA_PROB_REP_LEN_MID_LEN)
2781 #define LZMA_PROB_LITERAL_OFFSET \
2782 (LZMA_PROB_REP_LEN_HIGH_OFFSET + LZMA_PROB_REP_LEN_HIGH_LEN)
2784 #define LZMA_PROB_TOTAL_COUNT \
2785 (LZMA_PROB_LITERAL_OFFSET + LZMA_PROB_LITERAL_LEN)
2787 /* Check that the number of LZMA probabilities is the same as the
2788 Linux kernel implementation. */
2790 #if LZMA_PROB_TOTAL_COUNT != 1846 + (1 << 4) * 0x300
2791 #error Wrong number of LZMA probabilities
2792 #endif
2794 /* Expressions for the offset in the LZMA probabilities array of a
2795 specific probability. */
2797 #define LZMA_IS_MATCH(state, pos) \
2798 (LZMA_PROB_IS_MATCH_OFFSET + (state) * LZMA_POS_STATES + (pos))
2799 #define LZMA_IS_REP(state) \
2800 (LZMA_PROB_IS_REP_OFFSET + (state))
2801 #define LZMA_IS_REP0(state) \
2802 (LZMA_PROB_IS_REP0_OFFSET + (state))
2803 #define LZMA_IS_REP1(state) \
2804 (LZMA_PROB_IS_REP1_OFFSET + (state))
2805 #define LZMA_IS_REP2(state) \
2806 (LZMA_PROB_IS_REP2_OFFSET + (state))
2807 #define LZMA_IS_REP0_LONG(state, pos) \
2808 (LZMA_PROB_IS_REP0_LONG_OFFSET + (state) * LZMA_POS_STATES + (pos))
2809 #define LZMA_DIST_SLOT(dist, slot) \
2810 (LZMA_PROB_DIST_SLOT_OFFSET + (dist) * LZMA_DIST_SLOTS + (slot))
2811 #define LZMA_DIST_SPECIAL(dist) \
2812 (LZMA_PROB_DIST_SPECIAL_OFFSET + (dist))
2813 #define LZMA_DIST_ALIGN(dist) \
2814 (LZMA_PROB_DIST_ALIGN_OFFSET + (dist))
2815 #define LZMA_MATCH_LEN_CHOICE \
2816 LZMA_PROB_MATCH_LEN_CHOICE_OFFSET
2817 #define LZMA_MATCH_LEN_CHOICE2 \
2818 LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET
2819 #define LZMA_MATCH_LEN_LOW(pos, sym) \
2820 (LZMA_PROB_MATCH_LEN_LOW_OFFSET + (pos) * LZMA_LEN_LOW_SYMBOLS + (sym))
2821 #define LZMA_MATCH_LEN_MID(pos, sym) \
2822 (LZMA_PROB_MATCH_LEN_MID_OFFSET + (pos) * LZMA_LEN_MID_SYMBOLS + (sym))
2823 #define LZMA_MATCH_LEN_HIGH(sym) \
2824 (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + (sym))
2825 #define LZMA_REP_LEN_CHOICE \
2826 LZMA_PROB_REP_LEN_CHOICE_OFFSET
2827 #define LZMA_REP_LEN_CHOICE2 \
2828 LZMA_PROB_REP_LEN_CHOICE2_OFFSET
2829 #define LZMA_REP_LEN_LOW(pos, sym) \
2830 (LZMA_PROB_REP_LEN_LOW_OFFSET + (pos) * LZMA_LEN_LOW_SYMBOLS + (sym))
2831 #define LZMA_REP_LEN_MID(pos, sym) \
2832 (LZMA_PROB_REP_LEN_MID_OFFSET + (pos) * LZMA_LEN_MID_SYMBOLS + (sym))
2833 #define LZMA_REP_LEN_HIGH(sym) \
2834 (LZMA_PROB_REP_LEN_HIGH_OFFSET + (sym))
2835 #define LZMA_LITERAL(code, size) \
2836 (LZMA_PROB_LITERAL_OFFSET + (code) * LZMA_LITERAL_CODER_SIZE + (size))
2838 /* Read an LZMA varint from BUF, reading and updating *POFFSET,
2839 setting *VAL. Returns 0 on error, 1 on success. */
2841 static int
2842 elf_lzma_varint (const unsigned char *compressed, size_t compressed_size,
2843 size_t *poffset, uint64_t *val)
2845 size_t off;
2846 int i;
2847 uint64_t v;
2848 unsigned char b;
2850 off = *poffset;
2851 i = 0;
2852 v = 0;
2853 while (1)
2855 if (unlikely (off >= compressed_size))
2857 elf_uncompress_failed ();
2858 return 0;
2860 b = compressed[off];
2861 v |= (b & 0x7f) << (i * 7);
2862 ++off;
2863 if ((b & 0x80) == 0)
2865 *poffset = off;
2866 *val = v;
2867 return 1;
2869 ++i;
2870 if (unlikely (i >= 9))
2872 elf_uncompress_failed ();
2873 return 0;
2878 /* Normalize the LZMA range decoder, pulling in an extra input byte if
2879 needed. */
2881 static void
2882 elf_lzma_range_normalize (const unsigned char *compressed,
2883 size_t compressed_size, size_t *poffset,
2884 uint32_t *prange, uint32_t *pcode)
2886 if (*prange < (1U << 24))
2888 if (unlikely (*poffset >= compressed_size))
2890 /* We assume this will be caught elsewhere. */
2891 elf_uncompress_failed ();
2892 return;
2894 *prange <<= 8;
2895 *pcode <<= 8;
2896 *pcode += compressed[*poffset];
2897 ++*poffset;
2901 /* Read and return a single bit from the LZMA stream, reading and
2902 updating *PROB. Each bit comes from the range coder. */
2904 static int
2905 elf_lzma_bit (const unsigned char *compressed, size_t compressed_size,
2906 uint16_t *prob, size_t *poffset, uint32_t *prange,
2907 uint32_t *pcode)
2909 uint32_t bound;
2911 elf_lzma_range_normalize (compressed, compressed_size, poffset,
2912 prange, pcode);
2913 bound = (*prange >> 11) * (uint32_t) *prob;
2914 if (*pcode < bound)
2916 *prange = bound;
2917 *prob += ((1U << 11) - *prob) >> 5;
2918 return 0;
2920 else
2922 *prange -= bound;
2923 *pcode -= bound;
2924 *prob -= *prob >> 5;
2925 return 1;
2929 /* Read an integer of size BITS from the LZMA stream, most significant
2930 bit first. The bits are predicted using PROBS. */
2932 static uint32_t
2933 elf_lzma_integer (const unsigned char *compressed, size_t compressed_size,
2934 uint16_t *probs, uint32_t bits, size_t *poffset,
2935 uint32_t *prange, uint32_t *pcode)
2937 uint32_t sym;
2938 uint32_t i;
2940 sym = 1;
2941 for (i = 0; i < bits; i++)
2943 int bit;
2945 bit = elf_lzma_bit (compressed, compressed_size, probs + sym, poffset,
2946 prange, pcode);
2947 sym <<= 1;
2948 sym += bit;
2950 return sym - (1 << bits);
2953 /* Read an integer of size BITS from the LZMA stream, least
2954 significant bit first. The bits are predicted using PROBS. */
2956 static uint32_t
2957 elf_lzma_reverse_integer (const unsigned char *compressed,
2958 size_t compressed_size, uint16_t *probs,
2959 uint32_t bits, size_t *poffset, uint32_t *prange,
2960 uint32_t *pcode)
2962 uint32_t sym;
2963 uint32_t val;
2964 uint32_t i;
2966 sym = 1;
2967 val = 0;
2968 for (i = 0; i < bits; i++)
2970 int bit;
2972 bit = elf_lzma_bit (compressed, compressed_size, probs + sym, poffset,
2973 prange, pcode);
2974 sym <<= 1;
2975 sym += bit;
2976 val += bit << i;
2978 return val;
2981 /* Read a length from the LZMA stream. IS_REP picks either LZMA_MATCH
2982 or LZMA_REP probabilities. */
2984 static uint32_t
2985 elf_lzma_len (const unsigned char *compressed, size_t compressed_size,
2986 uint16_t *probs, int is_rep, unsigned int pos_state,
2987 size_t *poffset, uint32_t *prange, uint32_t *pcode)
2989 uint16_t *probs_choice;
2990 uint16_t *probs_sym;
2991 uint32_t bits;
2992 uint32_t len;
2994 probs_choice = probs + (is_rep
2995 ? LZMA_REP_LEN_CHOICE
2996 : LZMA_MATCH_LEN_CHOICE);
2997 if (elf_lzma_bit (compressed, compressed_size, probs_choice, poffset,
2998 prange, pcode))
3000 probs_choice = probs + (is_rep
3001 ? LZMA_REP_LEN_CHOICE2
3002 : LZMA_MATCH_LEN_CHOICE2);
3003 if (elf_lzma_bit (compressed, compressed_size, probs_choice,
3004 poffset, prange, pcode))
3006 probs_sym = probs + (is_rep
3007 ? LZMA_REP_LEN_HIGH (0)
3008 : LZMA_MATCH_LEN_HIGH (0));
3009 bits = 8;
3010 len = 2 + 8 + 8;
3012 else
3014 probs_sym = probs + (is_rep
3015 ? LZMA_REP_LEN_MID (pos_state, 0)
3016 : LZMA_MATCH_LEN_MID (pos_state, 0));
3017 bits = 3;
3018 len = 2 + 8;
3021 else
3023 probs_sym = probs + (is_rep
3024 ? LZMA_REP_LEN_LOW (pos_state, 0)
3025 : LZMA_MATCH_LEN_LOW (pos_state, 0));
3026 bits = 3;
3027 len = 2;
3030 len += elf_lzma_integer (compressed, compressed_size, probs_sym, bits,
3031 poffset, prange, pcode);
3032 return len;
3035 /* Uncompress one LZMA block from a minidebug file. The compressed
3036 data is at COMPRESSED + *POFFSET. Update *POFFSET. Store the data
3037 into the memory at UNCOMPRESSED, size UNCOMPRESSED_SIZE. CHECK is
3038 the stream flag from the xz header. Return 1 on successful
3039 decompression. */
3041 static int
3042 elf_uncompress_lzma_block (const unsigned char *compressed,
3043 size_t compressed_size, unsigned char check,
3044 uint16_t *probs, unsigned char *uncompressed,
3045 size_t uncompressed_size, size_t *poffset)
3047 size_t off;
3048 size_t block_header_offset;
3049 size_t block_header_size;
3050 unsigned char block_flags;
3051 uint64_t header_compressed_size;
3052 uint64_t header_uncompressed_size;
3053 unsigned char lzma2_properties;
3054 uint32_t computed_crc;
3055 uint32_t stream_crc;
3056 size_t uncompressed_offset;
3057 size_t dict_start_offset;
3058 unsigned int lc;
3059 unsigned int lp;
3060 unsigned int pb;
3061 uint32_t range;
3062 uint32_t code;
3063 uint32_t lstate;
3064 uint32_t dist[4];
3066 off = *poffset;
3067 block_header_offset = off;
3069 /* Block header size is a single byte. */
3070 if (unlikely (off >= compressed_size))
3072 elf_uncompress_failed ();
3073 return 0;
3075 block_header_size = (compressed[off] + 1) * 4;
3076 if (unlikely (off + block_header_size > compressed_size))
3078 elf_uncompress_failed ();
3079 return 0;
3082 /* Block flags. */
3083 block_flags = compressed[off + 1];
3084 if (unlikely ((block_flags & 0x3c) != 0))
3086 elf_uncompress_failed ();
3087 return 0;
3090 off += 2;
3092 /* Optional compressed size. */
3093 header_compressed_size = 0;
3094 if ((block_flags & 0x40) != 0)
3096 *poffset = off;
3097 if (!elf_lzma_varint (compressed, compressed_size, poffset,
3098 &header_compressed_size))
3099 return 0;
3100 off = *poffset;
3103 /* Optional uncompressed size. */
3104 header_uncompressed_size = 0;
3105 if ((block_flags & 0x80) != 0)
3107 *poffset = off;
3108 if (!elf_lzma_varint (compressed, compressed_size, poffset,
3109 &header_uncompressed_size))
3110 return 0;
3111 off = *poffset;
3114 /* The recipe for creating a minidebug file is to run the xz program
3115 with no arguments, so we expect exactly one filter: lzma2. */
3117 if (unlikely ((block_flags & 0x3) != 0))
3119 elf_uncompress_failed ();
3120 return 0;
3123 if (unlikely (off + 2 >= block_header_offset + block_header_size))
3125 elf_uncompress_failed ();
3126 return 0;
3129 /* The filter ID for LZMA2 is 0x21. */
3130 if (unlikely (compressed[off] != 0x21))
3132 elf_uncompress_failed ();
3133 return 0;
3135 ++off;
3137 /* The size of the filter properties for LZMA2 is 1. */
3138 if (unlikely (compressed[off] != 1))
3140 elf_uncompress_failed ();
3141 return 0;
3143 ++off;
3145 lzma2_properties = compressed[off];
3146 ++off;
3148 if (unlikely (lzma2_properties > 40))
3150 elf_uncompress_failed ();
3151 return 0;
3154 /* The properties describe the dictionary size, but we don't care
3155 what that is. */
3157 /* Block header padding. */
3158 if (unlikely (off + 4 > compressed_size))
3160 elf_uncompress_failed ();
3161 return 0;
3164 off = (off + 3) &~ (size_t) 3;
3166 if (unlikely (off + 4 > compressed_size))
3168 elf_uncompress_failed ();
3169 return 0;
3172 /* Block header CRC. */
3173 computed_crc = elf_crc32 (0, compressed + block_header_offset,
3174 block_header_size - 4);
3175 stream_crc = (compressed[off]
3176 | (compressed[off + 1] << 8)
3177 | (compressed[off + 2] << 16)
3178 | (compressed[off + 3] << 24));
3179 if (unlikely (computed_crc != stream_crc))
3181 elf_uncompress_failed ();
3182 return 0;
3184 off += 4;
3186 /* Read a sequence of LZMA2 packets. */
3188 uncompressed_offset = 0;
3189 dict_start_offset = 0;
3190 lc = 0;
3191 lp = 0;
3192 pb = 0;
3193 lstate = 0;
3194 while (off < compressed_size)
3196 unsigned char control;
3198 range = 0xffffffff;
3199 code = 0;
3201 control = compressed[off];
3202 ++off;
3203 if (unlikely (control == 0))
3205 /* End of packets. */
3206 break;
3209 if (control == 1 || control >= 0xe0)
3211 /* Reset dictionary to empty. */
3212 dict_start_offset = uncompressed_offset;
3215 if (control < 0x80)
3217 size_t chunk_size;
3219 /* The only valid values here are 1 or 2. A 1 means to
3220 reset the dictionary (done above). Then we see an
3221 uncompressed chunk. */
3223 if (unlikely (control > 2))
3225 elf_uncompress_failed ();
3226 return 0;
3229 /* An uncompressed chunk is a two byte size followed by
3230 data. */
3232 if (unlikely (off + 2 > compressed_size))
3234 elf_uncompress_failed ();
3235 return 0;
3238 chunk_size = compressed[off] << 8;
3239 chunk_size += compressed[off + 1];
3240 ++chunk_size;
3242 off += 2;
3244 if (unlikely (off + chunk_size > compressed_size))
3246 elf_uncompress_failed ();
3247 return 0;
3249 if (unlikely (uncompressed_offset + chunk_size > uncompressed_size))
3251 elf_uncompress_failed ();
3252 return 0;
3255 memcpy (uncompressed + uncompressed_offset, compressed + off,
3256 chunk_size);
3257 uncompressed_offset += chunk_size;
3258 off += chunk_size;
3260 else
3262 size_t uncompressed_chunk_start;
3263 size_t uncompressed_chunk_size;
3264 size_t compressed_chunk_size;
3265 size_t limit;
3267 /* An LZMA chunk. This starts with an uncompressed size and
3268 a compressed size. */
3270 if (unlikely (off + 4 >= compressed_size))
3272 elf_uncompress_failed ();
3273 return 0;
3276 uncompressed_chunk_start = uncompressed_offset;
3278 uncompressed_chunk_size = (control & 0x1f) << 16;
3279 uncompressed_chunk_size += compressed[off] << 8;
3280 uncompressed_chunk_size += compressed[off + 1];
3281 ++uncompressed_chunk_size;
3283 compressed_chunk_size = compressed[off + 2] << 8;
3284 compressed_chunk_size += compressed[off + 3];
3285 ++compressed_chunk_size;
3287 off += 4;
3289 /* Bit 7 (0x80) is set.
3290 Bits 6 and 5 (0x40 and 0x20) are as follows:
3291 0: don't reset anything
3292 1: reset state
3293 2: reset state, read properties
3294 3: reset state, read properties, reset dictionary (done above) */
3296 if (control >= 0xc0)
3298 unsigned char props;
3300 /* Bit 6 is set, read properties. */
3302 if (unlikely (off >= compressed_size))
3304 elf_uncompress_failed ();
3305 return 0;
3307 props = compressed[off];
3308 ++off;
3309 if (unlikely (props > (4 * 5 + 4) * 9 + 8))
3311 elf_uncompress_failed ();
3312 return 0;
3314 pb = 0;
3315 while (props >= 9 * 5)
3317 props -= 9 * 5;
3318 ++pb;
3320 lp = 0;
3321 while (props > 9)
3323 props -= 9;
3324 ++lp;
3326 lc = props;
3327 if (unlikely (lc + lp > 4))
3329 elf_uncompress_failed ();
3330 return 0;
3334 if (control >= 0xa0)
3336 size_t i;
3338 /* Bit 5 or 6 is set, reset LZMA state. */
3340 lstate = 0;
3341 memset (&dist, 0, sizeof dist);
3342 for (i = 0; i < LZMA_PROB_TOTAL_COUNT; i++)
3343 probs[i] = 1 << 10;
3344 range = 0xffffffff;
3345 code = 0;
3348 /* Read the range code. */
3350 if (unlikely (off + 5 > compressed_size))
3352 elf_uncompress_failed ();
3353 return 0;
3356 /* The byte at compressed[off] is ignored for some
3357 reason. */
3359 code = ((compressed[off + 1] << 24)
3360 + (compressed[off + 2] << 16)
3361 + (compressed[off + 3] << 8)
3362 + compressed[off + 4]);
3363 off += 5;
3365 /* This is the main LZMA decode loop. */
3367 limit = off + compressed_chunk_size;
3368 *poffset = off;
3369 while (*poffset < limit)
3371 unsigned int pos_state;
3373 if (unlikely (uncompressed_offset
3374 == (uncompressed_chunk_start
3375 + uncompressed_chunk_size)))
3377 /* We've decompressed all the expected bytes. */
3378 break;
3381 pos_state = ((uncompressed_offset - dict_start_offset)
3382 & ((1 << pb) - 1));
3384 if (elf_lzma_bit (compressed, compressed_size,
3385 probs + LZMA_IS_MATCH (lstate, pos_state),
3386 poffset, &range, &code))
3388 uint32_t len;
3390 if (elf_lzma_bit (compressed, compressed_size,
3391 probs + LZMA_IS_REP (lstate),
3392 poffset, &range, &code))
3394 int short_rep;
3395 uint32_t next_dist;
3397 /* Repeated match. */
3399 short_rep = 0;
3400 if (elf_lzma_bit (compressed, compressed_size,
3401 probs + LZMA_IS_REP0 (lstate),
3402 poffset, &range, &code))
3404 if (elf_lzma_bit (compressed, compressed_size,
3405 probs + LZMA_IS_REP1 (lstate),
3406 poffset, &range, &code))
3408 if (elf_lzma_bit (compressed, compressed_size,
3409 probs + LZMA_IS_REP2 (lstate),
3410 poffset, &range, &code))
3412 next_dist = dist[3];
3413 dist[3] = dist[2];
3415 else
3417 next_dist = dist[2];
3419 dist[2] = dist[1];
3421 else
3423 next_dist = dist[1];
3426 dist[1] = dist[0];
3427 dist[0] = next_dist;
3429 else
3431 if (!elf_lzma_bit (compressed, compressed_size,
3432 (probs
3433 + LZMA_IS_REP0_LONG (lstate,
3434 pos_state)),
3435 poffset, &range, &code))
3436 short_rep = 1;
3439 if (lstate < 7)
3440 lstate = short_rep ? 9 : 8;
3441 else
3442 lstate = 11;
3444 if (short_rep)
3445 len = 1;
3446 else
3447 len = elf_lzma_len (compressed, compressed_size,
3448 probs, 1, pos_state, poffset,
3449 &range, &code);
3451 else
3453 uint32_t dist_state;
3454 uint32_t dist_slot;
3455 uint16_t *probs_dist;
3457 /* Match. */
3459 if (lstate < 7)
3460 lstate = 7;
3461 else
3462 lstate = 10;
3463 dist[3] = dist[2];
3464 dist[2] = dist[1];
3465 dist[1] = dist[0];
3466 len = elf_lzma_len (compressed, compressed_size,
3467 probs, 0, pos_state, poffset,
3468 &range, &code);
3470 if (len < 4 + 2)
3471 dist_state = len - 2;
3472 else
3473 dist_state = 3;
3474 probs_dist = probs + LZMA_DIST_SLOT (dist_state, 0);
3475 dist_slot = elf_lzma_integer (compressed,
3476 compressed_size,
3477 probs_dist, 6,
3478 poffset, &range,
3479 &code);
3480 if (dist_slot < LZMA_DIST_MODEL_START)
3481 dist[0] = dist_slot;
3482 else
3484 uint32_t limit;
3486 limit = (dist_slot >> 1) - 1;
3487 dist[0] = 2 + (dist_slot & 1);
3488 if (dist_slot < LZMA_DIST_MODEL_END)
3490 dist[0] <<= limit;
3491 probs_dist = (probs
3492 + LZMA_DIST_SPECIAL(dist[0]
3493 - dist_slot
3494 - 1));
3495 dist[0] +=
3496 elf_lzma_reverse_integer (compressed,
3497 compressed_size,
3498 probs_dist,
3499 limit, poffset,
3500 &range, &code);
3502 else
3504 uint32_t dist0;
3505 uint32_t i;
3507 dist0 = dist[0];
3508 for (i = 0; i < limit - 4; i++)
3510 uint32_t mask;
3512 elf_lzma_range_normalize (compressed,
3513 compressed_size,
3514 poffset,
3515 &range, &code);
3516 range >>= 1;
3517 code -= range;
3518 mask = -(code >> 31);
3519 code += range & mask;
3520 dist0 <<= 1;
3521 dist0 += mask + 1;
3523 dist0 <<= 4;
3524 probs_dist = probs + LZMA_DIST_ALIGN (0);
3525 dist0 +=
3526 elf_lzma_reverse_integer (compressed,
3527 compressed_size,
3528 probs_dist, 4,
3529 poffset,
3530 &range, &code);
3531 dist[0] = dist0;
3536 if (unlikely (uncompressed_offset
3537 - dict_start_offset < dist[0] + 1))
3539 elf_uncompress_failed ();
3540 return 0;
3542 if (unlikely (uncompressed_offset + len > uncompressed_size))
3544 elf_uncompress_failed ();
3545 return 0;
3548 if (dist[0] == 0)
3550 /* A common case, meaning repeat the last
3551 character LEN times. */
3552 memset (uncompressed + uncompressed_offset,
3553 uncompressed[uncompressed_offset - 1],
3554 len);
3555 uncompressed_offset += len;
3557 else if (dist[0] + 1 >= len)
3559 memcpy (uncompressed + uncompressed_offset,
3560 uncompressed + uncompressed_offset - dist[0] - 1,
3561 len);
3562 uncompressed_offset += len;
3564 else
3566 while (len > 0)
3568 uint32_t copy;
3570 copy = len < dist[0] + 1 ? len : dist[0] + 1;
3571 memcpy (uncompressed + uncompressed_offset,
3572 (uncompressed + uncompressed_offset
3573 - dist[0] - 1),
3574 copy);
3575 len -= copy;
3576 uncompressed_offset += copy;
3580 else
3582 unsigned char prev;
3583 unsigned char low;
3584 size_t high;
3585 uint16_t *lit_probs;
3586 unsigned int sym;
3588 /* Literal value. */
3590 if (uncompressed_offset > 0)
3591 prev = uncompressed[uncompressed_offset - 1];
3592 else
3593 prev = 0;
3594 low = prev >> (8 - lc);
3595 high = (((uncompressed_offset - dict_start_offset)
3596 & ((1 << lp) - 1))
3597 << lc);
3598 lit_probs = probs + LZMA_LITERAL (low + high, 0);
3599 if (lstate < 7)
3600 sym = elf_lzma_integer (compressed, compressed_size,
3601 lit_probs, 8, poffset, &range,
3602 &code);
3603 else
3605 unsigned int match;
3606 unsigned int bit;
3607 unsigned int match_bit;
3608 unsigned int idx;
3610 sym = 1;
3611 if (uncompressed_offset >= dist[0] + 1)
3612 match = uncompressed[uncompressed_offset - dist[0] - 1];
3613 else
3614 match = 0;
3615 match <<= 1;
3616 bit = 0x100;
3619 match_bit = match & bit;
3620 match <<= 1;
3621 idx = bit + match_bit + sym;
3622 sym <<= 1;
3623 if (elf_lzma_bit (compressed, compressed_size,
3624 lit_probs + idx, poffset,
3625 &range, &code))
3627 ++sym;
3628 bit &= match_bit;
3630 else
3632 bit &= ~ match_bit;
3635 while (sym < 0x100);
3638 if (unlikely (uncompressed_offset >= uncompressed_size))
3640 elf_uncompress_failed ();
3641 return 0;
3644 uncompressed[uncompressed_offset] = (unsigned char) sym;
3645 ++uncompressed_offset;
3646 if (lstate <= 3)
3647 lstate = 0;
3648 else if (lstate <= 9)
3649 lstate -= 3;
3650 else
3651 lstate -= 6;
3655 elf_lzma_range_normalize (compressed, compressed_size, poffset,
3656 &range, &code);
3658 off = *poffset;
3662 /* We have reached the end of the block. Pad to four byte
3663 boundary. */
3664 off = (off + 3) &~ (size_t) 3;
3665 if (unlikely (off > compressed_size))
3667 elf_uncompress_failed ();
3668 return 0;
3671 switch (check)
3673 case 0:
3674 /* No check. */
3675 break;
3677 case 1:
3678 /* CRC32 */
3679 if (unlikely (off + 4 > compressed_size))
3681 elf_uncompress_failed ();
3682 return 0;
3684 computed_crc = elf_crc32 (0, uncompressed, uncompressed_offset);
3685 stream_crc = (compressed[off]
3686 | (compressed[off + 1] << 8)
3687 | (compressed[off + 2] << 16)
3688 | (compressed[off + 3] << 24));
3689 if (computed_crc != stream_crc)
3691 elf_uncompress_failed ();
3692 return 0;
3694 off += 4;
3695 break;
3697 case 4:
3698 /* CRC64. We don't bother computing a CRC64 checksum. */
3699 if (unlikely (off + 8 > compressed_size))
3701 elf_uncompress_failed ();
3702 return 0;
3704 off += 8;
3705 break;
3707 case 10:
3708 /* SHA. We don't bother computing a SHA checksum. */
3709 if (unlikely (off + 32 > compressed_size))
3711 elf_uncompress_failed ();
3712 return 0;
3714 off += 32;
3715 break;
3717 default:
3718 elf_uncompress_failed ();
3719 return 0;
3722 *poffset = off;
3724 return 1;
3727 /* Uncompress LZMA data found in a minidebug file. The minidebug
3728 format is described at
3729 https://sourceware.org/gdb/current/onlinedocs/gdb/MiniDebugInfo.html.
3730 Returns 0 on error, 1 on successful decompression. For this
3731 function we return 0 on failure to decompress, as the calling code
3732 will carry on in that case. */
3734 static int
3735 elf_uncompress_lzma (struct backtrace_state *state,
3736 const unsigned char *compressed, size_t compressed_size,
3737 backtrace_error_callback error_callback, void *data,
3738 unsigned char **uncompressed, size_t *uncompressed_size)
3740 size_t header_size;
3741 size_t footer_size;
3742 unsigned char check;
3743 uint32_t computed_crc;
3744 uint32_t stream_crc;
3745 size_t offset;
3746 size_t index_size;
3747 size_t footer_offset;
3748 size_t index_offset;
3749 uint64_t index_compressed_size;
3750 uint64_t index_uncompressed_size;
3751 unsigned char *mem;
3752 uint16_t *probs;
3753 size_t compressed_block_size;
3755 /* The format starts with a stream header and ends with a stream
3756 footer. */
3757 header_size = 12;
3758 footer_size = 12;
3759 if (unlikely (compressed_size < header_size + footer_size))
3761 elf_uncompress_failed ();
3762 return 0;
3765 /* The stream header starts with a magic string. */
3766 if (unlikely (memcmp (compressed, "\375" "7zXZ\0", 6) != 0))
3768 elf_uncompress_failed ();
3769 return 0;
3772 /* Next come stream flags. The first byte is zero, the second byte
3773 is the check. */
3774 if (unlikely (compressed[6] != 0))
3776 elf_uncompress_failed ();
3777 return 0;
3779 check = compressed[7];
3780 if (unlikely ((check & 0xf8) != 0))
3782 elf_uncompress_failed ();
3783 return 0;
3786 /* Next comes a CRC of the stream flags. */
3787 computed_crc = elf_crc32 (0, compressed + 6, 2);
3788 stream_crc = (compressed[8]
3789 | (compressed[9] << 8)
3790 | (compressed[10] << 16)
3791 | (compressed[11] << 24));
3792 if (unlikely (computed_crc != stream_crc))
3794 elf_uncompress_failed ();
3795 return 0;
3798 /* Now that we've parsed the header, parse the footer, so that we
3799 can get the uncompressed size. */
3801 /* The footer ends with two magic bytes. */
3803 offset = compressed_size;
3804 if (unlikely (memcmp (compressed + offset - 2, "YZ", 2) != 0))
3806 elf_uncompress_failed ();
3807 return 0;
3809 offset -= 2;
3811 /* Before that are the stream flags, which should be the same as the
3812 flags in the header. */
3813 if (unlikely (compressed[offset - 2] != 0
3814 || compressed[offset - 1] != check))
3816 elf_uncompress_failed ();
3817 return 0;
3819 offset -= 2;
3821 /* Before that is the size of the index field, which precedes the
3822 footer. */
3823 index_size = (compressed[offset - 4]
3824 | (compressed[offset - 3] << 8)
3825 | (compressed[offset - 2] << 16)
3826 | (compressed[offset - 1] << 24));
3827 index_size = (index_size + 1) * 4;
3828 offset -= 4;
3830 /* Before that is a footer CRC. */
3831 computed_crc = elf_crc32 (0, compressed + offset, 6);
3832 stream_crc = (compressed[offset - 4]
3833 | (compressed[offset - 3] << 8)
3834 | (compressed[offset - 2] << 16)
3835 | (compressed[offset - 1] << 24));
3836 if (unlikely (computed_crc != stream_crc))
3838 elf_uncompress_failed ();
3839 return 0;
3841 offset -= 4;
3843 /* The index comes just before the footer. */
3844 if (unlikely (offset < index_size + header_size))
3846 elf_uncompress_failed ();
3847 return 0;
3850 footer_offset = offset;
3851 offset -= index_size;
3852 index_offset = offset;
3854 /* The index starts with a zero byte. */
3855 if (unlikely (compressed[offset] != 0))
3857 elf_uncompress_failed ();
3858 return 0;
3860 ++offset;
3862 /* Next is the number of blocks. We expect zero blocks for an empty
3863 stream, and otherwise a single block. */
3864 if (unlikely (compressed[offset] == 0))
3866 *uncompressed = NULL;
3867 *uncompressed_size = 0;
3868 return 1;
3870 if (unlikely (compressed[offset] != 1))
3872 elf_uncompress_failed ();
3873 return 0;
3875 ++offset;
3877 /* Next is the compressed size and the uncompressed size. */
3878 if (!elf_lzma_varint (compressed, compressed_size, &offset,
3879 &index_compressed_size))
3880 return 0;
3881 if (!elf_lzma_varint (compressed, compressed_size, &offset,
3882 &index_uncompressed_size))
3883 return 0;
3885 /* Pad to a four byte boundary. */
3886 offset = (offset + 3) &~ (size_t) 3;
3888 /* Next is a CRC of the index. */
3889 computed_crc = elf_crc32 (0, compressed + index_offset,
3890 offset - index_offset);
3891 stream_crc = (compressed[offset]
3892 | (compressed[offset + 1] << 8)
3893 | (compressed[offset + 2] << 16)
3894 | (compressed[offset + 3] << 24));
3895 if (unlikely (computed_crc != stream_crc))
3897 elf_uncompress_failed ();
3898 return 0;
3900 offset += 4;
3902 /* We should now be back at the footer. */
3903 if (unlikely (offset != footer_offset))
3905 elf_uncompress_failed ();
3906 return 0;
3909 /* Allocate space to hold the uncompressed data. If we succeed in
3910 uncompressing the LZMA data, we never free this memory. */
3911 mem = (unsigned char *) backtrace_alloc (state, index_uncompressed_size,
3912 error_callback, data);
3913 if (unlikely (mem == NULL))
3914 return 0;
3915 *uncompressed = mem;
3916 *uncompressed_size = index_uncompressed_size;
3918 /* Allocate space for probabilities. */
3919 probs = ((uint16_t *)
3920 backtrace_alloc (state,
3921 LZMA_PROB_TOTAL_COUNT * sizeof (uint16_t),
3922 error_callback, data));
3923 if (unlikely (probs == NULL))
3925 backtrace_free (state, mem, index_uncompressed_size, error_callback,
3926 data);
3927 return 0;
3930 /* Uncompress the block, which follows the header. */
3931 offset = 12;
3932 if (!elf_uncompress_lzma_block (compressed, compressed_size, check, probs,
3933 mem, index_uncompressed_size, &offset))
3935 backtrace_free (state, mem, index_uncompressed_size, error_callback,
3936 data);
3937 return 0;
3940 compressed_block_size = offset - 12;
3941 if (unlikely (compressed_block_size
3942 != ((index_compressed_size + 3) &~ (size_t) 3)))
3944 elf_uncompress_failed ();
3945 backtrace_free (state, mem, index_uncompressed_size, error_callback,
3946 data);
3947 return 0;
3950 offset = (offset + 3) &~ (size_t) 3;
3951 if (unlikely (offset != index_offset))
3953 elf_uncompress_failed ();
3954 backtrace_free (state, mem, index_uncompressed_size, error_callback,
3955 data);
3956 return 0;
3959 return 1;
3962 /* This function is a hook for testing the LZMA support. It is only
3963 used by tests. */
3966 backtrace_uncompress_lzma (struct backtrace_state *state,
3967 const unsigned char *compressed,
3968 size_t compressed_size,
3969 backtrace_error_callback error_callback,
3970 void *data, unsigned char **uncompressed,
3971 size_t *uncompressed_size)
3973 return elf_uncompress_lzma (state, compressed, compressed_size,
3974 error_callback, data, uncompressed,
3975 uncompressed_size);
3978 /* Add the backtrace data for one ELF file. Returns 1 on success,
3979 0 on failure (in both cases descriptor is closed) or -1 if exe
3980 is non-zero and the ELF file is ET_DYN, which tells the caller that
3981 elf_add will need to be called on the descriptor again after
3982 base_address is determined. */
3984 static int
3985 elf_add (struct backtrace_state *state, const char *filename, int descriptor,
3986 const unsigned char *memory, size_t memory_size,
3987 uintptr_t base_address, backtrace_error_callback error_callback,
3988 void *data, fileline *fileline_fn, int *found_sym, int *found_dwarf,
3989 struct dwarf_data **fileline_entry, int exe, int debuginfo,
3990 const char *with_buildid_data, uint32_t with_buildid_size)
3992 struct elf_view ehdr_view;
3993 b_elf_ehdr ehdr;
3994 off_t shoff;
3995 unsigned int shnum;
3996 unsigned int shstrndx;
3997 struct elf_view shdrs_view;
3998 int shdrs_view_valid;
3999 const b_elf_shdr *shdrs;
4000 const b_elf_shdr *shstrhdr;
4001 size_t shstr_size;
4002 off_t shstr_off;
4003 struct elf_view names_view;
4004 int names_view_valid;
4005 const char *names;
4006 unsigned int symtab_shndx;
4007 unsigned int dynsym_shndx;
4008 unsigned int i;
4009 struct debug_section_info sections[DEBUG_MAX];
4010 struct debug_section_info zsections[DEBUG_MAX];
4011 struct elf_view symtab_view;
4012 int symtab_view_valid;
4013 struct elf_view strtab_view;
4014 int strtab_view_valid;
4015 struct elf_view buildid_view;
4016 int buildid_view_valid;
4017 const char *buildid_data;
4018 uint32_t buildid_size;
4019 struct elf_view debuglink_view;
4020 int debuglink_view_valid;
4021 const char *debuglink_name;
4022 uint32_t debuglink_crc;
4023 struct elf_view debugaltlink_view;
4024 int debugaltlink_view_valid;
4025 const char *debugaltlink_name;
4026 const char *debugaltlink_buildid_data;
4027 uint32_t debugaltlink_buildid_size;
4028 struct elf_view gnu_debugdata_view;
4029 int gnu_debugdata_view_valid;
4030 size_t gnu_debugdata_size;
4031 unsigned char *gnu_debugdata_uncompressed;
4032 size_t gnu_debugdata_uncompressed_size;
4033 off_t min_offset;
4034 off_t max_offset;
4035 off_t debug_size;
4036 struct elf_view debug_view;
4037 int debug_view_valid;
4038 unsigned int using_debug_view;
4039 uint16_t *zdebug_table;
4040 struct elf_view split_debug_view[DEBUG_MAX];
4041 unsigned char split_debug_view_valid[DEBUG_MAX];
4042 struct elf_ppc64_opd_data opd_data, *opd;
4043 struct dwarf_sections dwarf_sections;
4045 if (!debuginfo)
4047 *found_sym = 0;
4048 *found_dwarf = 0;
4051 shdrs_view_valid = 0;
4052 names_view_valid = 0;
4053 symtab_view_valid = 0;
4054 strtab_view_valid = 0;
4055 buildid_view_valid = 0;
4056 buildid_data = NULL;
4057 buildid_size = 0;
4058 debuglink_view_valid = 0;
4059 debuglink_name = NULL;
4060 debuglink_crc = 0;
4061 debugaltlink_view_valid = 0;
4062 debugaltlink_name = NULL;
4063 debugaltlink_buildid_data = NULL;
4064 debugaltlink_buildid_size = 0;
4065 gnu_debugdata_view_valid = 0;
4066 gnu_debugdata_size = 0;
4067 debug_view_valid = 0;
4068 memset (&split_debug_view_valid[0], 0, sizeof split_debug_view_valid);
4069 opd = NULL;
4071 if (!elf_get_view (state, descriptor, memory, memory_size, 0, sizeof ehdr,
4072 error_callback, data, &ehdr_view))
4073 goto fail;
4075 memcpy (&ehdr, ehdr_view.view.data, sizeof ehdr);
4077 elf_release_view (state, &ehdr_view, error_callback, data);
4079 if (ehdr.e_ident[EI_MAG0] != ELFMAG0
4080 || ehdr.e_ident[EI_MAG1] != ELFMAG1
4081 || ehdr.e_ident[EI_MAG2] != ELFMAG2
4082 || ehdr.e_ident[EI_MAG3] != ELFMAG3)
4084 error_callback (data, "executable file is not ELF", 0);
4085 goto fail;
4087 if (ehdr.e_ident[EI_VERSION] != EV_CURRENT)
4089 error_callback (data, "executable file is unrecognized ELF version", 0);
4090 goto fail;
4093 #if BACKTRACE_ELF_SIZE == 32
4094 #define BACKTRACE_ELFCLASS ELFCLASS32
4095 #else
4096 #define BACKTRACE_ELFCLASS ELFCLASS64
4097 #endif
4099 if (ehdr.e_ident[EI_CLASS] != BACKTRACE_ELFCLASS)
4101 error_callback (data, "executable file is unexpected ELF class", 0);
4102 goto fail;
4105 if (ehdr.e_ident[EI_DATA] != ELFDATA2LSB
4106 && ehdr.e_ident[EI_DATA] != ELFDATA2MSB)
4108 error_callback (data, "executable file has unknown endianness", 0);
4109 goto fail;
4112 /* If the executable is ET_DYN, it is either a PIE, or we are running
4113 directly a shared library with .interp. We need to wait for
4114 dl_iterate_phdr in that case to determine the actual base_address. */
4115 if (exe && ehdr.e_type == ET_DYN)
4116 return -1;
4118 shoff = ehdr.e_shoff;
4119 shnum = ehdr.e_shnum;
4120 shstrndx = ehdr.e_shstrndx;
4122 if ((shnum == 0 || shstrndx == SHN_XINDEX)
4123 && shoff != 0)
4125 struct elf_view shdr_view;
4126 const b_elf_shdr *shdr;
4128 if (!elf_get_view (state, descriptor, memory, memory_size, shoff,
4129 sizeof shdr, error_callback, data, &shdr_view))
4130 goto fail;
4132 shdr = (const b_elf_shdr *) shdr_view.view.data;
4134 if (shnum == 0)
4135 shnum = shdr->sh_size;
4137 if (shstrndx == SHN_XINDEX)
4139 shstrndx = shdr->sh_link;
4141 /* Versions of the GNU binutils between 2.12 and 2.18 did
4142 not handle objects with more than SHN_LORESERVE sections
4143 correctly. All large section indexes were offset by
4144 0x100. There is more information at
4145 http://sourceware.org/bugzilla/show_bug.cgi?id-5900 .
4146 Fortunately these object files are easy to detect, as the
4147 GNU binutils always put the section header string table
4148 near the end of the list of sections. Thus if the
4149 section header string table index is larger than the
4150 number of sections, then we know we have to subtract
4151 0x100 to get the real section index. */
4152 if (shstrndx >= shnum && shstrndx >= SHN_LORESERVE + 0x100)
4153 shstrndx -= 0x100;
4156 elf_release_view (state, &shdr_view, error_callback, data);
4159 if (shnum == 0 || shstrndx == 0)
4160 goto fail;
4162 /* To translate PC to file/line when using DWARF, we need to find
4163 the .debug_info and .debug_line sections. */
4165 /* Read the section headers, skipping the first one. */
4167 if (!elf_get_view (state, descriptor, memory, memory_size,
4168 shoff + sizeof (b_elf_shdr),
4169 (shnum - 1) * sizeof (b_elf_shdr),
4170 error_callback, data, &shdrs_view))
4171 goto fail;
4172 shdrs_view_valid = 1;
4173 shdrs = (const b_elf_shdr *) shdrs_view.view.data;
4175 /* Read the section names. */
4177 shstrhdr = &shdrs[shstrndx - 1];
4178 shstr_size = shstrhdr->sh_size;
4179 shstr_off = shstrhdr->sh_offset;
4181 if (!elf_get_view (state, descriptor, memory, memory_size, shstr_off,
4182 shstrhdr->sh_size, error_callback, data, &names_view))
4183 goto fail;
4184 names_view_valid = 1;
4185 names = (const char *) names_view.view.data;
4187 symtab_shndx = 0;
4188 dynsym_shndx = 0;
4190 memset (sections, 0, sizeof sections);
4191 memset (zsections, 0, sizeof zsections);
4193 /* Look for the symbol table. */
4194 for (i = 1; i < shnum; ++i)
4196 const b_elf_shdr *shdr;
4197 unsigned int sh_name;
4198 const char *name;
4199 int j;
4201 shdr = &shdrs[i - 1];
4203 if (shdr->sh_type == SHT_SYMTAB)
4204 symtab_shndx = i;
4205 else if (shdr->sh_type == SHT_DYNSYM)
4206 dynsym_shndx = i;
4208 sh_name = shdr->sh_name;
4209 if (sh_name >= shstr_size)
4211 error_callback (data, "ELF section name out of range", 0);
4212 goto fail;
4215 name = names + sh_name;
4217 for (j = 0; j < (int) DEBUG_MAX; ++j)
4219 if (strcmp (name, dwarf_section_names[j]) == 0)
4221 sections[j].offset = shdr->sh_offset;
4222 sections[j].size = shdr->sh_size;
4223 sections[j].compressed = (shdr->sh_flags & SHF_COMPRESSED) != 0;
4224 break;
4228 if (name[0] == '.' && name[1] == 'z')
4230 for (j = 0; j < (int) DEBUG_MAX; ++j)
4232 if (strcmp (name + 2, dwarf_section_names[j] + 1) == 0)
4234 zsections[j].offset = shdr->sh_offset;
4235 zsections[j].size = shdr->sh_size;
4236 break;
4241 /* Read the build ID if present. This could check for any
4242 SHT_NOTE section with the right note name and type, but gdb
4243 looks for a specific section name. */
4244 if ((!debuginfo || with_buildid_data != NULL)
4245 && !buildid_view_valid
4246 && strcmp (name, ".note.gnu.build-id") == 0)
4248 const b_elf_note *note;
4250 if (!elf_get_view (state, descriptor, memory, memory_size,
4251 shdr->sh_offset, shdr->sh_size, error_callback,
4252 data, &buildid_view))
4253 goto fail;
4255 buildid_view_valid = 1;
4256 note = (const b_elf_note *) buildid_view.view.data;
4257 if (note->type == NT_GNU_BUILD_ID
4258 && note->namesz == 4
4259 && strncmp (note->name, "GNU", 4) == 0
4260 && shdr->sh_size <= 12 + ((note->namesz + 3) & ~ 3) + note->descsz)
4262 buildid_data = &note->name[0] + ((note->namesz + 3) & ~ 3);
4263 buildid_size = note->descsz;
4266 if (with_buildid_size != 0)
4268 if (buildid_size != with_buildid_size)
4269 goto fail;
4271 if (memcmp (buildid_data, with_buildid_data, buildid_size) != 0)
4272 goto fail;
4276 /* Read the debuglink file if present. */
4277 if (!debuginfo
4278 && !debuglink_view_valid
4279 && strcmp (name, ".gnu_debuglink") == 0)
4281 const char *debuglink_data;
4282 size_t crc_offset;
4284 if (!elf_get_view (state, descriptor, memory, memory_size,
4285 shdr->sh_offset, shdr->sh_size, error_callback,
4286 data, &debuglink_view))
4287 goto fail;
4289 debuglink_view_valid = 1;
4290 debuglink_data = (const char *) debuglink_view.view.data;
4291 crc_offset = strnlen (debuglink_data, shdr->sh_size);
4292 crc_offset = (crc_offset + 3) & ~3;
4293 if (crc_offset + 4 <= shdr->sh_size)
4295 debuglink_name = debuglink_data;
4296 debuglink_crc = *(const uint32_t*)(debuglink_data + crc_offset);
4300 if (!debugaltlink_view_valid
4301 && strcmp (name, ".gnu_debugaltlink") == 0)
4303 const char *debugaltlink_data;
4304 size_t debugaltlink_name_len;
4306 if (!elf_get_view (state, descriptor, memory, memory_size,
4307 shdr->sh_offset, shdr->sh_size, error_callback,
4308 data, &debugaltlink_view))
4309 goto fail;
4311 debugaltlink_view_valid = 1;
4312 debugaltlink_data = (const char *) debugaltlink_view.view.data;
4313 debugaltlink_name = debugaltlink_data;
4314 debugaltlink_name_len = strnlen (debugaltlink_data, shdr->sh_size);
4315 if (debugaltlink_name_len < shdr->sh_size)
4317 /* Include terminating zero. */
4318 debugaltlink_name_len += 1;
4320 debugaltlink_buildid_data
4321 = debugaltlink_data + debugaltlink_name_len;
4322 debugaltlink_buildid_size = shdr->sh_size - debugaltlink_name_len;
4326 if (!gnu_debugdata_view_valid
4327 && strcmp (name, ".gnu_debugdata") == 0)
4329 if (!elf_get_view (state, descriptor, memory, memory_size,
4330 shdr->sh_offset, shdr->sh_size, error_callback,
4331 data, &gnu_debugdata_view))
4332 goto fail;
4334 gnu_debugdata_size = shdr->sh_size;
4335 gnu_debugdata_view_valid = 1;
4338 /* Read the .opd section on PowerPC64 ELFv1. */
4339 if (ehdr.e_machine == EM_PPC64
4340 && (ehdr.e_flags & EF_PPC64_ABI) < 2
4341 && shdr->sh_type == SHT_PROGBITS
4342 && strcmp (name, ".opd") == 0)
4344 if (!elf_get_view (state, descriptor, memory, memory_size,
4345 shdr->sh_offset, shdr->sh_size, error_callback,
4346 data, &opd_data.view))
4347 goto fail;
4349 opd = &opd_data;
4350 opd->addr = shdr->sh_addr;
4351 opd->data = (const char *) opd_data.view.view.data;
4352 opd->size = shdr->sh_size;
4356 if (symtab_shndx == 0)
4357 symtab_shndx = dynsym_shndx;
4358 if (symtab_shndx != 0 && !debuginfo)
4360 const b_elf_shdr *symtab_shdr;
4361 unsigned int strtab_shndx;
4362 const b_elf_shdr *strtab_shdr;
4363 struct elf_syminfo_data *sdata;
4365 symtab_shdr = &shdrs[symtab_shndx - 1];
4366 strtab_shndx = symtab_shdr->sh_link;
4367 if (strtab_shndx >= shnum)
4369 error_callback (data,
4370 "ELF symbol table strtab link out of range", 0);
4371 goto fail;
4373 strtab_shdr = &shdrs[strtab_shndx - 1];
4375 if (!elf_get_view (state, descriptor, memory, memory_size,
4376 symtab_shdr->sh_offset, symtab_shdr->sh_size,
4377 error_callback, data, &symtab_view))
4378 goto fail;
4379 symtab_view_valid = 1;
4381 if (!elf_get_view (state, descriptor, memory, memory_size,
4382 strtab_shdr->sh_offset, strtab_shdr->sh_size,
4383 error_callback, data, &strtab_view))
4384 goto fail;
4385 strtab_view_valid = 1;
4387 sdata = ((struct elf_syminfo_data *)
4388 backtrace_alloc (state, sizeof *sdata, error_callback, data));
4389 if (sdata == NULL)
4390 goto fail;
4392 if (!elf_initialize_syminfo (state, base_address,
4393 symtab_view.view.data, symtab_shdr->sh_size,
4394 strtab_view.view.data, strtab_shdr->sh_size,
4395 error_callback, data, sdata, opd))
4397 backtrace_free (state, sdata, sizeof *sdata, error_callback, data);
4398 goto fail;
4401 /* We no longer need the symbol table, but we hold on to the
4402 string table permanently. */
4403 elf_release_view (state, &symtab_view, error_callback, data);
4404 symtab_view_valid = 0;
4405 strtab_view_valid = 0;
4407 *found_sym = 1;
4409 elf_add_syminfo_data (state, sdata);
4412 elf_release_view (state, &shdrs_view, error_callback, data);
4413 shdrs_view_valid = 0;
4414 elf_release_view (state, &names_view, error_callback, data);
4415 names_view_valid = 0;
4417 /* If the debug info is in a separate file, read that one instead. */
4419 if (buildid_data != NULL)
4421 int d;
4423 d = elf_open_debugfile_by_buildid (state, buildid_data, buildid_size,
4424 error_callback, data);
4425 if (d >= 0)
4427 int ret;
4429 elf_release_view (state, &buildid_view, error_callback, data);
4430 if (debuglink_view_valid)
4431 elf_release_view (state, &debuglink_view, error_callback, data);
4432 if (debugaltlink_view_valid)
4433 elf_release_view (state, &debugaltlink_view, error_callback, data);
4434 ret = elf_add (state, "", d, NULL, 0, base_address, error_callback,
4435 data, fileline_fn, found_sym, found_dwarf, NULL, 0,
4436 1, NULL, 0);
4437 if (ret < 0)
4438 backtrace_close (d, error_callback, data);
4439 else if (descriptor >= 0)
4440 backtrace_close (descriptor, error_callback, data);
4441 return ret;
4445 if (buildid_view_valid)
4447 elf_release_view (state, &buildid_view, error_callback, data);
4448 buildid_view_valid = 0;
4451 if (opd)
4453 elf_release_view (state, &opd->view, error_callback, data);
4454 opd = NULL;
4457 if (debuglink_name != NULL)
4459 int d;
4461 d = elf_open_debugfile_by_debuglink (state, filename, debuglink_name,
4462 debuglink_crc, error_callback,
4463 data);
4464 if (d >= 0)
4466 int ret;
4468 elf_release_view (state, &debuglink_view, error_callback, data);
4469 if (debugaltlink_view_valid)
4470 elf_release_view (state, &debugaltlink_view, error_callback, data);
4471 ret = elf_add (state, "", d, NULL, 0, base_address, error_callback,
4472 data, fileline_fn, found_sym, found_dwarf, NULL, 0,
4473 1, NULL, 0);
4474 if (ret < 0)
4475 backtrace_close (d, error_callback, data);
4476 else if (descriptor >= 0)
4477 backtrace_close(descriptor, error_callback, data);
4478 return ret;
4482 if (debuglink_view_valid)
4484 elf_release_view (state, &debuglink_view, error_callback, data);
4485 debuglink_view_valid = 0;
4488 struct dwarf_data *fileline_altlink = NULL;
4489 if (debugaltlink_name != NULL)
4491 int d;
4493 d = elf_open_debugfile_by_debuglink (state, filename, debugaltlink_name,
4494 0, error_callback, data);
4495 if (d >= 0)
4497 int ret;
4499 ret = elf_add (state, filename, d, NULL, 0, base_address,
4500 error_callback, data, fileline_fn, found_sym,
4501 found_dwarf, &fileline_altlink, 0, 1,
4502 debugaltlink_buildid_data, debugaltlink_buildid_size);
4503 elf_release_view (state, &debugaltlink_view, error_callback, data);
4504 debugaltlink_view_valid = 0;
4505 if (ret < 0)
4507 backtrace_close (d, error_callback, data);
4508 return ret;
4513 if (debugaltlink_view_valid)
4515 elf_release_view (state, &debugaltlink_view, error_callback, data);
4516 debugaltlink_view_valid = 0;
4519 if (gnu_debugdata_view_valid)
4521 int ret;
4523 ret = elf_uncompress_lzma (state,
4524 ((const unsigned char *)
4525 gnu_debugdata_view.view.data),
4526 gnu_debugdata_size, error_callback, data,
4527 &gnu_debugdata_uncompressed,
4528 &gnu_debugdata_uncompressed_size);
4530 elf_release_view (state, &gnu_debugdata_view, error_callback, data);
4531 gnu_debugdata_view_valid = 0;
4533 if (ret)
4535 ret = elf_add (state, filename, -1, gnu_debugdata_uncompressed,
4536 gnu_debugdata_uncompressed_size, base_address,
4537 error_callback, data, fileline_fn, found_sym,
4538 found_dwarf, NULL, 0, 0, NULL, 0);
4539 if (ret >= 0 && descriptor >= 0)
4540 backtrace_close(descriptor, error_callback, data);
4541 return ret;
4545 /* Read all the debug sections in a single view, since they are
4546 probably adjacent in the file. If any of sections are
4547 uncompressed, we never release this view. */
4549 min_offset = 0;
4550 max_offset = 0;
4551 debug_size = 0;
4552 for (i = 0; i < (int) DEBUG_MAX; ++i)
4554 off_t end;
4556 if (sections[i].size != 0)
4558 if (min_offset == 0 || sections[i].offset < min_offset)
4559 min_offset = sections[i].offset;
4560 end = sections[i].offset + sections[i].size;
4561 if (end > max_offset)
4562 max_offset = end;
4563 debug_size += sections[i].size;
4565 if (zsections[i].size != 0)
4567 if (min_offset == 0 || zsections[i].offset < min_offset)
4568 min_offset = zsections[i].offset;
4569 end = zsections[i].offset + zsections[i].size;
4570 if (end > max_offset)
4571 max_offset = end;
4572 debug_size += zsections[i].size;
4575 if (min_offset == 0 || max_offset == 0)
4577 if (descriptor >= 0)
4579 if (!backtrace_close (descriptor, error_callback, data))
4580 goto fail;
4582 return 1;
4585 /* If the total debug section size is large, assume that there are
4586 gaps between the sections, and read them individually. */
4588 if (max_offset - min_offset < 0x20000000
4589 || max_offset - min_offset < debug_size + 0x10000)
4591 if (!elf_get_view (state, descriptor, memory, memory_size, min_offset,
4592 max_offset - min_offset, error_callback, data,
4593 &debug_view))
4594 goto fail;
4595 debug_view_valid = 1;
4597 else
4599 memset (&split_debug_view[0], 0, sizeof split_debug_view);
4600 for (i = 0; i < (int) DEBUG_MAX; ++i)
4602 struct debug_section_info *dsec;
4604 if (sections[i].size != 0)
4605 dsec = &sections[i];
4606 else if (zsections[i].size != 0)
4607 dsec = &zsections[i];
4608 else
4609 continue;
4611 if (!elf_get_view (state, descriptor, memory, memory_size,
4612 dsec->offset, dsec->size, error_callback, data,
4613 &split_debug_view[i]))
4614 goto fail;
4615 split_debug_view_valid[i] = 1;
4617 if (sections[i].size != 0)
4618 sections[i].data = ((const unsigned char *)
4619 split_debug_view[i].view.data);
4620 else
4621 zsections[i].data = ((const unsigned char *)
4622 split_debug_view[i].view.data);
4626 /* We've read all we need from the executable. */
4627 if (descriptor >= 0)
4629 if (!backtrace_close (descriptor, error_callback, data))
4630 goto fail;
4631 descriptor = -1;
4634 using_debug_view = 0;
4635 if (debug_view_valid)
4637 for (i = 0; i < (int) DEBUG_MAX; ++i)
4639 if (sections[i].size == 0)
4640 sections[i].data = NULL;
4641 else
4643 sections[i].data = ((const unsigned char *) debug_view.view.data
4644 + (sections[i].offset - min_offset));
4645 ++using_debug_view;
4648 if (zsections[i].size == 0)
4649 zsections[i].data = NULL;
4650 else
4651 zsections[i].data = ((const unsigned char *) debug_view.view.data
4652 + (zsections[i].offset - min_offset));
4656 /* Uncompress the old format (--compress-debug-sections=zlib-gnu). */
4658 zdebug_table = NULL;
4659 for (i = 0; i < (int) DEBUG_MAX; ++i)
4661 if (sections[i].size == 0 && zsections[i].size > 0)
4663 unsigned char *uncompressed_data;
4664 size_t uncompressed_size;
4666 if (zdebug_table == NULL)
4668 zdebug_table = ((uint16_t *)
4669 backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
4670 error_callback, data));
4671 if (zdebug_table == NULL)
4672 goto fail;
4675 uncompressed_data = NULL;
4676 uncompressed_size = 0;
4677 if (!elf_uncompress_zdebug (state, zsections[i].data,
4678 zsections[i].size, zdebug_table,
4679 error_callback, data,
4680 &uncompressed_data, &uncompressed_size))
4681 goto fail;
4682 sections[i].data = uncompressed_data;
4683 sections[i].size = uncompressed_size;
4684 sections[i].compressed = 0;
4686 if (split_debug_view_valid[i])
4688 elf_release_view (state, &split_debug_view[i],
4689 error_callback, data);
4690 split_debug_view_valid[i] = 0;
4695 /* Uncompress the official ELF format
4696 (--compress-debug-sections=zlib-gabi). */
4697 for (i = 0; i < (int) DEBUG_MAX; ++i)
4699 unsigned char *uncompressed_data;
4700 size_t uncompressed_size;
4702 if (sections[i].size == 0 || !sections[i].compressed)
4703 continue;
4705 if (zdebug_table == NULL)
4707 zdebug_table = ((uint16_t *)
4708 backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
4709 error_callback, data));
4710 if (zdebug_table == NULL)
4711 goto fail;
4714 uncompressed_data = NULL;
4715 uncompressed_size = 0;
4716 if (!elf_uncompress_chdr (state, sections[i].data, sections[i].size,
4717 zdebug_table, error_callback, data,
4718 &uncompressed_data, &uncompressed_size))
4719 goto fail;
4720 sections[i].data = uncompressed_data;
4721 sections[i].size = uncompressed_size;
4722 sections[i].compressed = 0;
4724 if (debug_view_valid)
4725 --using_debug_view;
4726 else if (split_debug_view_valid[i])
4728 elf_release_view (state, &split_debug_view[i], error_callback, data);
4729 split_debug_view_valid[i] = 0;
4733 if (zdebug_table != NULL)
4734 backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
4735 error_callback, data);
4737 if (debug_view_valid && using_debug_view == 0)
4739 elf_release_view (state, &debug_view, error_callback, data);
4740 debug_view_valid = 0;
4743 for (i = 0; i < (int) DEBUG_MAX; ++i)
4745 dwarf_sections.data[i] = sections[i].data;
4746 dwarf_sections.size[i] = sections[i].size;
4749 if (!backtrace_dwarf_add (state, base_address, &dwarf_sections,
4750 ehdr.e_ident[EI_DATA] == ELFDATA2MSB,
4751 fileline_altlink,
4752 error_callback, data, fileline_fn,
4753 fileline_entry))
4754 goto fail;
4756 *found_dwarf = 1;
4758 return 1;
4760 fail:
4761 if (shdrs_view_valid)
4762 elf_release_view (state, &shdrs_view, error_callback, data);
4763 if (names_view_valid)
4764 elf_release_view (state, &names_view, error_callback, data);
4765 if (symtab_view_valid)
4766 elf_release_view (state, &symtab_view, error_callback, data);
4767 if (strtab_view_valid)
4768 elf_release_view (state, &strtab_view, error_callback, data);
4769 if (debuglink_view_valid)
4770 elf_release_view (state, &debuglink_view, error_callback, data);
4771 if (debugaltlink_view_valid)
4772 elf_release_view (state, &debugaltlink_view, error_callback, data);
4773 if (gnu_debugdata_view_valid)
4774 elf_release_view (state, &gnu_debugdata_view, error_callback, data);
4775 if (buildid_view_valid)
4776 elf_release_view (state, &buildid_view, error_callback, data);
4777 if (debug_view_valid)
4778 elf_release_view (state, &debug_view, error_callback, data);
4779 for (i = 0; i < (int) DEBUG_MAX; ++i)
4781 if (split_debug_view_valid[i])
4782 elf_release_view (state, &split_debug_view[i], error_callback, data);
4784 if (opd)
4785 elf_release_view (state, &opd->view, error_callback, data);
4786 if (descriptor >= 0)
4787 backtrace_close (descriptor, error_callback, data);
4788 return 0;
4791 /* Data passed to phdr_callback. */
4793 struct phdr_data
4795 struct backtrace_state *state;
4796 backtrace_error_callback error_callback;
4797 void *data;
4798 fileline *fileline_fn;
4799 int *found_sym;
4800 int *found_dwarf;
4801 const char *exe_filename;
4802 int exe_descriptor;
4805 /* Callback passed to dl_iterate_phdr. Load debug info from shared
4806 libraries. */
4808 static int
4809 #ifdef __i386__
4810 __attribute__ ((__force_align_arg_pointer__))
4811 #endif
4812 phdr_callback (struct dl_phdr_info *info, size_t size ATTRIBUTE_UNUSED,
4813 void *pdata)
4815 struct phdr_data *pd = (struct phdr_data *) pdata;
4816 const char *filename;
4817 int descriptor;
4818 int does_not_exist;
4819 fileline elf_fileline_fn;
4820 int found_dwarf;
4822 /* There is not much we can do if we don't have the module name,
4823 unless executable is ET_DYN, where we expect the very first
4824 phdr_callback to be for the PIE. */
4825 if (info->dlpi_name == NULL || info->dlpi_name[0] == '\0')
4827 if (pd->exe_descriptor == -1)
4828 return 0;
4829 filename = pd->exe_filename;
4830 descriptor = pd->exe_descriptor;
4831 pd->exe_descriptor = -1;
4833 else
4835 if (pd->exe_descriptor != -1)
4837 backtrace_close (pd->exe_descriptor, pd->error_callback, pd->data);
4838 pd->exe_descriptor = -1;
4841 filename = info->dlpi_name;
4842 descriptor = backtrace_open (info->dlpi_name, pd->error_callback,
4843 pd->data, &does_not_exist);
4844 if (descriptor < 0)
4845 return 0;
4848 if (elf_add (pd->state, filename, descriptor, NULL, 0, info->dlpi_addr,
4849 pd->error_callback, pd->data, &elf_fileline_fn, pd->found_sym,
4850 &found_dwarf, NULL, 0, 0, NULL, 0))
4852 if (found_dwarf)
4854 *pd->found_dwarf = 1;
4855 *pd->fileline_fn = elf_fileline_fn;
4859 return 0;
4862 /* Initialize the backtrace data we need from an ELF executable. At
4863 the ELF level, all we need to do is find the debug info
4864 sections. */
4867 backtrace_initialize (struct backtrace_state *state, const char *filename,
4868 int descriptor, backtrace_error_callback error_callback,
4869 void *data, fileline *fileline_fn)
4871 int ret;
4872 int found_sym;
4873 int found_dwarf;
4874 fileline elf_fileline_fn = elf_nodebug;
4875 struct phdr_data pd;
4877 ret = elf_add (state, filename, descriptor, NULL, 0, 0, error_callback, data,
4878 &elf_fileline_fn, &found_sym, &found_dwarf, NULL, 1, 0, NULL,
4880 if (!ret)
4881 return 0;
4883 pd.state = state;
4884 pd.error_callback = error_callback;
4885 pd.data = data;
4886 pd.fileline_fn = &elf_fileline_fn;
4887 pd.found_sym = &found_sym;
4888 pd.found_dwarf = &found_dwarf;
4889 pd.exe_filename = filename;
4890 pd.exe_descriptor = ret < 0 ? descriptor : -1;
4892 dl_iterate_phdr (phdr_callback, (void *) &pd);
4894 if (!state->threaded)
4896 if (found_sym)
4897 state->syminfo_fn = elf_syminfo;
4898 else if (state->syminfo_fn == NULL)
4899 state->syminfo_fn = elf_nosyms;
4901 else
4903 if (found_sym)
4904 backtrace_atomic_store_pointer (&state->syminfo_fn, elf_syminfo);
4905 else
4906 (void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
4907 elf_nosyms);
4910 if (!state->threaded)
4911 *fileline_fn = state->fileline_fn;
4912 else
4913 *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
4915 if (*fileline_fn == NULL || *fileline_fn == elf_nodebug)
4916 *fileline_fn = elf_fileline_fn;
4918 return 1;