// elf.c: #include #include #include #include #include #include #ifdef HAVE_DL_ITERATE_PHDR #include #endif #ifndef S_ISLNK #ifndef S_IFLNK #define S_IFLNK 0120000 #endif #ifndef S_IFMT #define S_IFMT 0170000 #endif #define S_ISLNK(m) (((m)&S_IFMT) == S_IFLNK) #endif #ifndef __GNUC__ #define __builtin_prefetch(p, r, l) #define unlikely(x) (x) #else #define unlikely(x) __builtin_expect(!!(x), 0) #endif #if !defined(HAVE_DECL_STRNLEN) || !HAVE_DECL_STRNLEN static size_t xstrnlen(const char *s, size_t maxlen) { size_t i; for (i = 0; i < maxlen; ++i) if (s[i] == '\0') break; return i; } #define strnlen xstrnlen #endif #ifndef HAVE_LSTAT static int xlstat(const char *path ATTRIBUTE_UNUSED, struct stat *st ATTRIBUTE_UNUSED) { return -1; } #define lstat xlstat #endif #ifndef HAVE_READLINK static ssize_t xreadlink(const char *path ATTRIBUTE_UNUSED, char *buf ATTRIBUTE_UNUSED, size_t bufsz ATTRIBUTE_UNUSED) { return -1; } #define readlink xreadlink #endif #ifndef HAVE_DL_ITERATE_PHDR #define dl_phdr_info x_dl_phdr_info #define dl_iterate_phdr x_dl_iterate_phdr struct dl_phdr_info { uintptr_t dlpi_addr; const char *dlpi_name; }; static int dl_iterate_phdr(int (*callback)(struct dl_phdr_info *, size_t, void *) ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) { return 0; } #endif #if BACKTRACE_ELF_SIZE != 32 && BACKTRACE_ELF_SIZE != 64 #error "Unknown BACKTRACE_ELF_SIZE" #endif #undef EI_NIDENT #undef EI_MAG0 #undef EI_MAG1 #undef EI_MAG2 #undef EI_MAG3 #undef EI_CLASS #undef EI_DATA #undef EI_VERSION #undef ELF_MAG0 #undef ELF_MAG1 #undef ELF_MAG2 #undef ELF_MAG3 #undef ELFCLASS32 #undef ELFCLASS64 #undef ELFDATA2LSB #undef ELFDATA2MSB #undef EV_CURRENT #undef ET_DYN #undef EM_PPC64 #undef EF_PPC64_ABI #undef SHN_LORESERVE #undef SHN_XINDEX #undef SHN_UNDEF #undef SHT_PROGBITS #undef SHT_SYMTAB #undef SHT_STRTAB #undef SHT_DYNSYM #undef SHF_COMPRESSED #undef STT_OBJECT #undef STT_FUNC #undef NT_GNU_BUILD_ID #undef ELFCOMPRESS_ZLIB typedef uint16_t b_elf_half; typedef uint32_t b_elf_word; typedef int32_t b_elf_sword; #if BACKTRACE_ELF_SIZE == 32 typedef uint32_t b_elf_addr; typedef uint32_t b_elf_off; typedef uint32_t b_elf_wxword; #else typedef uint64_t b_elf_addr; typedef uint64_t b_elf_off; typedef uint64_t b_elf_xword; typedef int64_t b_elf_sxword; typedef uint64_t b_elf_wxword; #endif #define EI_NIDENT 16 typedef struct { unsigned char e_ident[EI_NIDENT]; b_elf_half e_type; b_elf_half e_machine; b_elf_word e_version; b_elf_addr e_entry; b_elf_off e_phoff; b_elf_off e_shoff; b_elf_word e_flags; b_elf_half e_ehsize; b_elf_half e_phentsize; b_elf_half e_phnum; b_elf_half e_shentsize; b_elf_half e_shnum; b_elf_half e_shstrndx; } b_elf_ehdr; #define EI_MAG0 0 #define EI_MAG1 1 #define EI_MAG2 2 #define EI_MAG3 3 #define EI_CLASS 4 #define EI_DATA 5 #define EI_VERSION 6 #define ELFMAG0 0x7f #define ELFMAG1 'E' #define ELFMAG2 'L' #define ELFMAG3 'F' #define ELFCLASS32 1 #define ELFCLASS64 2 #define ELFDATA2LSB 1 #define ELFDATA2MSB 2 #define EV_CURRENT 1 #define ET_DYN 3 #define EM_PPC64 21 #define EF_PPC64_ABI 3 typedef struct { b_elf_word sh_name; b_elf_word sh_type; b_elf_wxword sh_flags; b_elf_addr sh_addr; b_elf_off sh_offset; b_elf_wxword sh_size; b_elf_word sh_link; b_elf_word sh_info; b_elf_wxword sh_addralign; b_elf_wxword sh_entsize; } b_elf_shdr; #define SHN_UNDEF 0x0000 #define SHN_LORESERVE 0xFF00 #define SHN_XINDEX 0xFFFF #define SHT_PROGBITS 1 #define SHT_SYMTAB 2 #define SHT_STRTAB 3 #define SHT_DYNSYM 11 #define SHF_COMPRESSED 0x800 #if BACKTRACE_ELF_SIZE == 32 typedef struct { b_elf_word st_name; b_elf_addr st_value; b_elf_word st_size; unsigned char st_info; unsigned char st_other; b_elf_half st_shndx; } b_elf_sym; #else typedef struct { b_elf_word st_name; unsigned char st_info; unsigned char st_other; b_elf_half st_shndx; b_elf_addr st_value; b_elf_xword st_size; } b_elf_sym; #endif #define STT_OBJECT 1 #define STT_FUNC 2 typedef struct { uint32_t namesz; uint32_t descsz; uint32_t type; char name[1]; } b_elf_note; #define NT_GNU_BUILD_ID 3 #if BACKTRACE_ELF_SIZE == 32 typedef struct { b_elf_word ch_type; b_elf_word ch_size; b_elf_word ch_addralign; } b_elf_chdr; #else typedef struct { b_elf_word ch_type; b_elf_word ch_reserved; b_elf_xword ch_size; b_elf_xword ch_addralign; } b_elf_chdr; #endif #define ELFCOMPRESS_ZLIB 1 static const char *const dwarf_section_names[DEBUG_MAX] = { ".debug_info", ".debug_line", ".debug_abbrev", ".debug_ranges", ".debug_str", ".debug_addr", ".debug_str_offsets", ".debug_line_str", ".debug_rnglists"}; struct debug_section_info { off_t offset; size_t size; const unsigned char *data; int compressed; }; struct elf_symbol { const char *name; uintptr_t address; size_t size; }; struct elf_syminfo_data { struct elf_syminfo_data *next; struct elf_symbol *symbols; size_t count; }; struct elf_view { struct backtrace_view view; int release; }; struct elf_ppc64_opd_data { b_elf_addr addr; const char *data; size_t size; struct elf_view view; }; static int elf_get_view(struct backtrace_state *state, int descriptor, const unsigned char *memory, size_t memory_size, off_t offset, uint64_t size, backtrace_error_callback error_callback, void *data, struct elf_view *view) { if (memory == NULL) { view->release = 1; return backtrace_get_view(state, descriptor, offset, size, error_callback, data, &view->view); } else { if ((uint64_t)offset + size > (uint64_t)memory_size) { error_callback(data, "out of range for in-memory file", 0); return 0; } view->view.data = (const void *)(memory + offset); view->view.base = NULL; view->view.len = size; view->release = 0; return 1; } } static void elf_release_view(struct backtrace_state *state, struct elf_view *view, backtrace_error_callback error_callback, void *data) { if (view->release) backtrace_release_view(state, &view->view, error_callback, data); } static uint32_t elf_crc32(uint32_t crc, const unsigned char *buf, size_t len) { static const uint32_t crc32_table[256] = { 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d}; const unsigned char *end; crc = ~crc; for (end = buf + len; buf < end; ++buf) crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8); return ~crc; } static uint32_t elf_crc32_file(struct backtrace_state *state, int descriptor, backtrace_error_callback error_callback, void *data) { struct stat st; struct backtrace_view file_view; uint32_t ret; if (fstat(descriptor, &st) < 0) { error_callback(data, "fstat", errno); return 0; } if (!backtrace_get_view(state, descriptor, 0, st.st_size, error_callback, data, &file_view)) return 0; ret = elf_crc32(0, (const unsigned char *)file_view.data, st.st_size); backtrace_release_view(state, &file_view, error_callback, data); return ret; } static void elf_nosyms(struct backtrace_state *state ATTRIBUTE_UNUSED, uintptr_t addr ATTRIBUTE_UNUSED, backtrace_syminfo_callback callback ATTRIBUTE_UNUSED, backtrace_error_callback error_callback, void *data) { error_callback(data, "no symbol table in ELF executable", -1); } static int elf_nodebug(struct backtrace_state *state, uintptr_t pc, backtrace_full_callback callback, backtrace_error_callback error_callback, void *data) { if (state->syminfo_fn != NULL && state->syminfo_fn != elf_nosyms) { struct backtrace_call_full bdata; bdata.full_callback = callback; bdata.full_error_callback = error_callback; bdata.full_data = data; bdata.ret = 0; state->syminfo_fn(state, pc, backtrace_syminfo_to_full_callback, backtrace_syminfo_to_full_error_callback, &bdata); return bdata.ret; } error_callback(data, "no debug info in ELF executable", -1); return 0; } static int elf_symbol_compare(const void *v1, const void *v2) { const struct elf_symbol *e1 = (const struct elf_symbol *)v1; const struct elf_symbol *e2 = (const struct elf_symbol *)v2; if (e1->address < e2->address) return -1; else if (e1->address > e2->address) return 1; else return 0; } static int elf_symbol_search(const void *vkey, const void *ventry) { const uintptr_t *key = (const uintptr_t *)vkey; const struct elf_symbol *entry = (const struct elf_symbol *)ventry; uintptr_t addr; addr = *key; if (addr < entry->address) return -1; else if (addr >= entry->address + entry->size) return 1; else return 0; } static int elf_initialize_syminfo( struct backtrace_state *state, uintptr_t base_address, const unsigned char *symtab_data, size_t symtab_size, const unsigned char *strtab, size_t strtab_size, backtrace_error_callback error_callback, void *data, struct elf_syminfo_data *sdata, struct elf_ppc64_opd_data *opd) { size_t sym_count; const b_elf_sym *sym; size_t elf_symbol_count; size_t elf_symbol_size; struct elf_symbol *elf_symbols; size_t i; unsigned int j; sym_count = symtab_size / sizeof(b_elf_sym); sym = (const b_elf_sym *)symtab_data; elf_symbol_count = 0; for (i = 0; i < sym_count; ++i, ++sym) { int info; info = sym->st_info & 0xf; if ((info == STT_FUNC || info == STT_OBJECT) && sym->st_shndx != SHN_UNDEF) ++elf_symbol_count; } elf_symbol_size = elf_symbol_count * sizeof(struct elf_symbol); elf_symbols = ((struct elf_symbol *)backtrace_alloc(state, elf_symbol_size, error_callback, data)); if (elf_symbols == NULL) return 0; sym = (const b_elf_sym *)symtab_data; j = 0; for (i = 0; i < sym_count; ++i, ++sym) { int info; info = sym->st_info & 0xf; if (info != STT_FUNC && info != STT_OBJECT) continue; if (sym->st_shndx == SHN_UNDEF) continue; if (sym->st_name >= strtab_size) { error_callback(data, "symbol string index out of range", 0); backtrace_free(state, elf_symbols, elf_symbol_size, error_callback, data); return 0; } elf_symbols[j].name = (const char *)strtab + sym->st_name; if (opd && sym->st_value >= opd->addr && sym->st_value < opd->addr + opd->size) elf_symbols[j].address = *(const b_elf_addr *)(opd->data + (sym->st_value - opd->addr)); else elf_symbols[j].address = sym->st_value; elf_symbols[j].address += base_address; elf_symbols[j].size = sym->st_size; ++j; } backtrace_qsort(elf_symbols, elf_symbol_count, sizeof(struct elf_symbol), elf_symbol_compare); sdata->next = NULL; sdata->symbols = elf_symbols; sdata->count = elf_symbol_count; return 1; } static void elf_add_syminfo_data(struct backtrace_state *state, struct elf_syminfo_data *edata) { if (!state->threaded) { struct elf_syminfo_data **pp; for (pp = (struct elf_syminfo_data **)(void *)&state->syminfo_data; *pp != NULL; pp = &(*pp)->next) ; *pp = edata; } else { while (1) { struct elf_syminfo_data **pp; pp = (struct elf_syminfo_data **)(void *)&state->syminfo_data; while (1) { struct elf_syminfo_data *p; p = backtrace_atomic_load_pointer(pp); if (p == NULL) break; pp = &p->next; } if (__sync_bool_compare_and_swap(pp, NULL, edata)) break; } } } static void elf_syminfo( struct backtrace_state *state, uintptr_t addr, backtrace_syminfo_callback callback, backtrace_error_callback error_callback ATTRIBUTE_UNUSED, void *data) { struct elf_syminfo_data *edata; struct elf_symbol *sym = NULL; if (!state->threaded) { for (edata = (struct elf_syminfo_data *)state->syminfo_data; edata != NULL; edata = edata->next) { sym = ((struct elf_symbol *)bsearch(&addr, edata->symbols, edata->count, sizeof(struct elf_symbol), elf_symbol_search)); if (sym != NULL) break; } } else { struct elf_syminfo_data **pp; pp = (struct elf_syminfo_data **)(void *)&state->syminfo_data; while (1) { edata = backtrace_atomic_load_pointer(pp); if (edata == NULL) break; sym = ((struct elf_symbol *)bsearch(&addr, edata->symbols, edata->count, sizeof(struct elf_symbol), elf_symbol_search)); if (sym != NULL) break; pp = &edata->next; } } if (sym == NULL) callback(data, addr, NULL, 0, 0); else callback(data, addr, sym->name, sym->address, sym->size); } static int elf_is_symlink(const char *filename) { struct stat st; if (lstat(filename, &st) < 0) return 0; return S_ISLNK(st.st_mode); } static char *elf_readlink(struct backtrace_state *state, const char *filename, backtrace_error_callback error_callback, void *data, size_t *plen) { size_t len; char *buf; len = 128; while (1) { ssize_t rl; buf = backtrace_alloc(state, len, error_callback, data); if (buf == NULL) return NULL; rl = readlink(filename, buf, len); if (rl < 0) { backtrace_free(state, buf, len, error_callback, data); return NULL; } if ((size_t)rl < len - 1) { buf[rl] = '\0'; *plen = len; return buf; } backtrace_free(state, buf, len, error_callback, data); len *= 2; } } #define SYSTEM_BUILD_ID_DIR "/usr/lib/debug/.build-id/" static int elf_open_debugfile_by_buildid( struct backtrace_state *state, const char *buildid_data, size_t buildid_size, backtrace_error_callback error_callback, void *data) { const char *const prefix = SYSTEM_BUILD_ID_DIR; const size_t prefix_len = strlen(prefix); const char *const suffix = ".debug"; const size_t suffix_len = strlen(suffix); size_t len; char *bd_filename; char *t; size_t i; int ret; int does_not_exist; len = prefix_len + buildid_size * 2 + suffix_len + 2; bd_filename = backtrace_alloc(state, len, error_callback, data); if (bd_filename == NULL) return -1; t = bd_filename; memcpy(t, prefix, prefix_len); t += prefix_len; for (i = 0; i < buildid_size; i++) { unsigned char b; unsigned char nib; b = (unsigned char)buildid_data[i]; nib = (b & 0xf0) >> 4; *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10; nib = b & 0x0f; *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10; if (i == 0) *t++ = '/'; } memcpy(t, suffix, suffix_len); t[suffix_len] = '\0'; ret = backtrace_open(bd_filename, error_callback, data, &does_not_exist); backtrace_free(state, bd_filename, len, error_callback, data); return ret; } static int elf_try_debugfile(struct backtrace_state *state, const char *prefix, size_t prefix_len, const char *prefix2, size_t prefix2_len, const char *debuglink_name, backtrace_error_callback error_callback, void *data) { size_t debuglink_len; size_t try_len; char *try; int does_not_exist; int ret; debuglink_len = strlen(debuglink_name); try_len = prefix_len + prefix2_len + debuglink_len + 1; try = backtrace_alloc(state, try_len, error_callback, data); if (try == NULL) return -1; memcpy(try, prefix, prefix_len); memcpy(try + prefix_len, prefix2, prefix2_len); memcpy(try + prefix_len + prefix2_len, debuglink_name, debuglink_len); try[prefix_len + prefix2_len + debuglink_len] = '\0'; ret = backtrace_open(try, error_callback, data, &does_not_exist); backtrace_free(state, try, try_len, error_callback, data); return ret; } static int elf_find_debugfile_by_debuglink( struct backtrace_state *state, const char *filename, const char *debuglink_name, backtrace_error_callback error_callback, void *data) { int ret; char *alc; size_t alc_len; const char *slash; int ddescriptor; const char *prefix; size_t prefix_len; ret = -1; alc = NULL; alc_len = 0; while (elf_is_symlink(filename)) { char *new_buf; size_t new_len; new_buf = elf_readlink(state, filename, error_callback, data, &new_len); if (new_buf == NULL) break; if (new_buf[0] == '/') filename = new_buf; else { slash = strrchr(filename, '/'); if (slash == NULL) filename = new_buf; else { size_t clen; char *c; slash++; clen = slash - filename + strlen(new_buf) + 1; c = backtrace_alloc(state, clen, error_callback, data); if (c == NULL) goto done; memcpy(c, filename, slash - filename); memcpy(c + (slash - filename), new_buf, strlen(new_buf)); c[slash - filename + strlen(new_buf)] = '\0'; backtrace_free(state, new_buf, new_len, error_callback, data); filename = c; new_buf = c; new_len = clen; } } if (alc != NULL) backtrace_free(state, alc, alc_len, error_callback, data); alc = new_buf; alc_len = new_len; } slash = strrchr(filename, '/'); if (slash == NULL) { prefix = ""; prefix_len = 0; } else { slash++; prefix = filename; prefix_len = slash - filename; } ddescriptor = elf_try_debugfile(state, prefix, prefix_len, "", 0, debuglink_name, error_callback, data); if (ddescriptor >= 0) { ret = ddescriptor; goto done; } ddescriptor = elf_try_debugfile(state, prefix, prefix_len, ".debug/", strlen(".debug/"), debuglink_name, error_callback, data); if (ddescriptor >= 0) { ret = ddescriptor; goto done; } ddescriptor = elf_try_debugfile(state, "/usr/lib/debug/", strlen("/usr/lib/debug/"), prefix, prefix_len, debuglink_name, error_callback, data); if (ddescriptor >= 0) ret = ddescriptor; done: if (alc != NULL && alc_len > 0) backtrace_free(state, alc, alc_len, error_callback, data); return ret; } static int elf_open_debugfile_by_debuglink( struct backtrace_state *state, const char *filename, const char *debuglink_name, uint32_t debuglink_crc, backtrace_error_callback error_callback, void *data) { int ddescriptor; ddescriptor = elf_find_debugfile_by_debuglink(state, filename, debuglink_name, error_callback, data); if (ddescriptor < 0) return -1; if (debuglink_crc != 0) { uint32_t got_crc; got_crc = elf_crc32_file(state, ddescriptor, error_callback, data); if (got_crc != debuglink_crc) { backtrace_close(ddescriptor, error_callback, data); return -1; } } return ddescriptor; } static void elf_uncompress_failed(void) {} static int elf_zlib_fetch(const unsigned char **ppin, const unsigned char *pinend, uint64_t *pval, unsigned int *pbits) { unsigned int bits; const unsigned char *pin; uint64_t val; uint32_t next; bits = *pbits; if (bits >= 15) return 1; pin = *ppin; val = *pval; if (unlikely(pinend - pin < 4)) { elf_uncompress_failed(); return 0; } #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \ defined(__ORDER_BIG_ENDIAN__) && \ (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ || \ __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) next = *(const uint32_t *)pin; #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ next = __builtin_bswap32(next); #endif #else next = pin[0] | (pin[1] << 8) | (pin[2] << 16) | (pin[3] << 24); #endif val |= (uint64_t)next << bits; bits += 32; pin += 4; __builtin_prefetch(pin, 0, 0); *ppin = pin; *pval = val; *pbits = bits; return 1; } #define HUFFMAN_TABLE_SIZE (1024) #define HUFFMAN_VALUE_MASK 0x01ff #define HUFFMAN_BITS_SHIFT 9 #define HUFFMAN_BITS_MASK 0x7 #define HUFFMAN_SECONDARY_SHIFT 12 #define ZDEBUG_TABLE_SIZE \ (2 * HUFFMAN_TABLE_SIZE * sizeof(uint16_t) + (286 + 30) * sizeof(uint16_t) + \ (286 + 30) * sizeof(unsigned char)) #define ZDEBUG_TABLE_CODELEN_OFFSET \ (2 * HUFFMAN_TABLE_SIZE * sizeof(uint16_t) + (286 + 30) * sizeof(uint16_t)) #define ZDEBUG_TABLE_WORK_OFFSET (2 * HUFFMAN_TABLE_SIZE * sizeof(uint16_t)) #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE static size_t final_next_secondary; #endif static int elf_zlib_inflate_table(unsigned char *codes, size_t codes_len, uint16_t *zdebug_table, uint16_t *table) { uint16_t count[16]; uint16_t start[16]; uint16_t prev[16]; uint16_t firstcode[7]; uint16_t *next; size_t i; size_t j; unsigned int code; size_t next_secondary; next = (uint16_t *)(((unsigned char *)zdebug_table) + ZDEBUG_TABLE_WORK_OFFSET); memset(&count[0], 0, 16 * sizeof(uint16_t)); for (i = 0; i < codes_len; ++i) { if (unlikely(codes[i] >= 16)) { elf_uncompress_failed(); return 0; } if (count[codes[i]] == 0) { start[codes[i]] = i; prev[codes[i]] = i; } else { next[prev[codes[i]]] = i; prev[codes[i]] = i; } ++count[codes[i]]; } memset(table, 0, HUFFMAN_TABLE_SIZE * sizeof(uint16_t)); code = 0; for (j = 1; j <= 8; ++j) { unsigned int jcnt; unsigned int val; jcnt = count[j]; if (jcnt == 0) continue; if (unlikely(jcnt > (1U << j))) { elf_uncompress_failed(); return 0; } val = start[j]; for (i = 0; i < jcnt; ++i) { uint16_t tval; size_t ind; unsigned int incr; if (unlikely((val & ~HUFFMAN_VALUE_MASK) != 0)) { elf_uncompress_failed(); return 0; } tval = val | ((j - 1) << HUFFMAN_BITS_SHIFT); for (ind = code; ind < 0x100; ind += 1 << j) { if (unlikely(table[ind] != 0)) { elf_uncompress_failed(); return 0; } table[ind] = tval; } if (i + 1 < jcnt) val = next[val]; incr = 1U << (j - 1); while ((code & incr) != 0) incr >>= 1; if (incr == 0) code = 0; else { code &= incr - 1; code += incr; } } } for (j = 9; j < 16; j++) { unsigned int jcnt; unsigned int k; jcnt = count[j]; if (jcnt == 0) continue; firstcode[j - 9] = code; for (k = 0; k < j; ++k) { if ((jcnt & (1U << k)) != 0) { unsigned int m; unsigned int bit; bit = 1U << (j - k - 1); for (m = 0; m < j - k; ++m, bit >>= 1) { if ((code & bit) == 0) { code += bit; break; } code &= ~bit; } jcnt &= ~(1U << k); } } if (unlikely(jcnt != 0)) { elf_uncompress_failed(); return 0; } } next_secondary = 0; for (j = 15; j >= 9; j--) { unsigned int jcnt; unsigned int val; size_t primary; size_t secondary; size_t secondary_bits; jcnt = count[j]; if (jcnt == 0) continue; val = start[j]; code = firstcode[j - 9]; primary = 0x100; secondary = 0; secondary_bits = 0; for (i = 0; i < jcnt; ++i) { uint16_t tval; size_t ind; unsigned int incr; if ((code & 0xff) != primary) { uint16_t tprimary; primary = code & 0xff; tprimary = table[primary]; if (tprimary == 0) { if (unlikely((next_secondary & HUFFMAN_VALUE_MASK) != next_secondary)) { elf_uncompress_failed(); return 0; } secondary = next_secondary; secondary_bits = j - 8; next_secondary += 1 << secondary_bits; table[primary] = (secondary + ((j - 8) << HUFFMAN_BITS_SHIFT) + (1U << HUFFMAN_SECONDARY_SHIFT)); } else { if (unlikely((tprimary & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)) { elf_uncompress_failed(); return 0; } secondary = tprimary & HUFFMAN_VALUE_MASK; secondary_bits = ((tprimary >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK); if (unlikely(secondary_bits < j - 8)) { elf_uncompress_failed(); return 0; } } } tval = val | ((j - 8) << HUFFMAN_BITS_SHIFT); for (ind = code >> 8; ind < (1U << secondary_bits); ind += 1U << (j - 8)) { if (unlikely(table[secondary + 0x100 + ind] != 0)) { elf_uncompress_failed(); return 0; } table[secondary + 0x100 + ind] = tval; } if (i + 1 < jcnt) val = next[val]; incr = 1U << (j - 1); while ((code & incr) != 0) incr >>= 1; if (incr == 0) code = 0; else { code &= incr - 1; code += incr; } } } #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE final_next_secondary = next_secondary; #endif return 1; } static const uint16_t elf_zlib_default_table[0x170] = { 0xd00, 0xe50, 0xe10, 0xf18, 0xd10, 0xe70, 0xe30, 0x1230, 0xd08, 0xe60, 0xe20, 0x1210, 0xe00, 0xe80, 0xe40, 0x1250, 0xd04, 0xe58, 0xe18, 0x1200, 0xd14, 0xe78, 0xe38, 0x1240, 0xd0c, 0xe68, 0xe28, 0x1220, 0xe08, 0xe88, 0xe48, 0x1260, 0xd02, 0xe54, 0xe14, 0xf1c, 0xd12, 0xe74, 0xe34, 0x1238, 0xd0a, 0xe64, 0xe24, 0x1218, 0xe04, 0xe84, 0xe44, 0x1258, 0xd06, 0xe5c, 0xe1c, 0x1208, 0xd16, 0xe7c, 0xe3c, 0x1248, 0xd0e, 0xe6c, 0xe2c, 0x1228, 0xe0c, 0xe8c, 0xe4c, 0x1268, 0xd01, 0xe52, 0xe12, 0xf1a, 0xd11, 0xe72, 0xe32, 0x1234, 0xd09, 0xe62, 0xe22, 0x1214, 0xe02, 0xe82, 0xe42, 0x1254, 0xd05, 0xe5a, 0xe1a, 0x1204, 0xd15, 0xe7a, 0xe3a, 0x1244, 0xd0d, 0xe6a, 0xe2a, 0x1224, 0xe0a, 0xe8a, 0xe4a, 0x1264, 0xd03, 0xe56, 0xe16, 0xf1e, 0xd13, 0xe76, 0xe36, 0x123c, 0xd0b, 0xe66, 0xe26, 0x121c, 0xe06, 0xe86, 0xe46, 0x125c, 0xd07, 0xe5e, 0xe1e, 0x120c, 0xd17, 0xe7e, 0xe3e, 0x124c, 0xd0f, 0xe6e, 0xe2e, 0x122c, 0xe0e, 0xe8e, 0xe4e, 0x126c, 0xd00, 0xe51, 0xe11, 0xf19, 0xd10, 0xe71, 0xe31, 0x1232, 0xd08, 0xe61, 0xe21, 0x1212, 0xe01, 0xe81, 0xe41, 0x1252, 0xd04, 0xe59, 0xe19, 0x1202, 0xd14, 0xe79, 0xe39, 0x1242, 0xd0c, 0xe69, 0xe29, 0x1222, 0xe09, 0xe89, 0xe49, 0x1262, 0xd02, 0xe55, 0xe15, 0xf1d, 0xd12, 0xe75, 0xe35, 0x123a, 0xd0a, 0xe65, 0xe25, 0x121a, 0xe05, 0xe85, 0xe45, 0x125a, 0xd06, 0xe5d, 0xe1d, 0x120a, 0xd16, 0xe7d, 0xe3d, 0x124a, 0xd0e, 0xe6d, 0xe2d, 0x122a, 0xe0d, 0xe8d, 0xe4d, 0x126a, 0xd01, 0xe53, 0xe13, 0xf1b, 0xd11, 0xe73, 0xe33, 0x1236, 0xd09, 0xe63, 0xe23, 0x1216, 0xe03, 0xe83, 0xe43, 0x1256, 0xd05, 0xe5b, 0xe1b, 0x1206, 0xd15, 0xe7b, 0xe3b, 0x1246, 0xd0d, 0xe6b, 0xe2b, 0x1226, 0xe0b, 0xe8b, 0xe4b, 0x1266, 0xd03, 0xe57, 0xe17, 0xf1f, 0xd13, 0xe77, 0xe37, 0x123e, 0xd0b, 0xe67, 0xe27, 0x121e, 0xe07, 0xe87, 0xe47, 0x125e, 0xd07, 0xe5f, 0xe1f, 0x120e, 0xd17, 0xe7f, 0xe3f, 0x124e, 0xd0f, 0xe6f, 0xe2f, 0x122e, 0xe0f, 0xe8f, 0xe4f, 0x126e, 0x290, 0x291, 0x292, 0x293, 0x294, 0x295, 0x296, 0x297, 0x298, 0x299, 0x29a, 0x29b, 0x29c, 0x29d, 0x29e, 0x29f, 0x2a0, 0x2a1, 0x2a2, 0x2a3, 0x2a4, 0x2a5, 0x2a6, 0x2a7, 0x2a8, 0x2a9, 0x2aa, 0x2ab, 0x2ac, 0x2ad, 0x2ae, 0x2af, 0x2b0, 0x2b1, 0x2b2, 0x2b3, 0x2b4, 0x2b5, 0x2b6, 0x2b7, 0x2b8, 0x2b9, 0x2ba, 0x2bb, 0x2bc, 0x2bd, 0x2be, 0x2bf, 0x2c0, 0x2c1, 0x2c2, 0x2c3, 0x2c4, 0x2c5, 0x2c6, 0x2c7, 0x2c8, 0x2c9, 0x2ca, 0x2cb, 0x2cc, 0x2cd, 0x2ce, 0x2cf, 0x2d0, 0x2d1, 0x2d2, 0x2d3, 0x2d4, 0x2d5, 0x2d6, 0x2d7, 0x2d8, 0x2d9, 0x2da, 0x2db, 0x2dc, 0x2dd, 0x2de, 0x2df, 0x2e0, 0x2e1, 0x2e2, 0x2e3, 0x2e4, 0x2e5, 0x2e6, 0x2e7, 0x2e8, 0x2e9, 0x2ea, 0x2eb, 0x2ec, 0x2ed, 0x2ee, 0x2ef, 0x2f0, 0x2f1, 0x2f2, 0x2f3, 0x2f4, 0x2f5, 0x2f6, 0x2f7, 0x2f8, 0x2f9, 0x2fa, 0x2fb, 0x2fc, 0x2fd, 0x2fe, 0x2ff, }; static const uint16_t elf_zlib_default_dist_table[0x100] = { 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c, 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e, 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d, 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f, }; static int elf_zlib_inflate(const unsigned char *pin, size_t sin, uint16_t *zdebug_table, unsigned char *pout, size_t sout) { unsigned char *porigout; const unsigned char *pinend; unsigned char *poutend; porigout = pout; pinend = pin + sin; poutend = pout + sout; while ((pinend - pin) > 4) { uint64_t val; unsigned int bits; int last; if (unlikely((pin[0] & 0xf) != 8)) { elf_uncompress_failed(); return 0; } if (unlikely((pin[0] >> 4) > 7)) { elf_uncompress_failed(); return 0; } if (unlikely((pin[1] & 0x20) != 0)) { elf_uncompress_failed(); return 0; } val = (pin[0] << 8) | pin[1]; if (unlikely(val % 31 != 0)) { elf_uncompress_failed(); return 0; } pin += 2; val = 0; bits = 0; while ((((uintptr_t)pin) & 3) != 0) { val |= (uint64_t)*pin << bits; bits += 8; ++pin; } last = 0; while (!last) { unsigned int type; const uint16_t *tlit; const uint16_t *tdist; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; last = val & 1; type = (val >> 1) & 3; val >>= 3; bits -= 3; if (unlikely(type == 3)) { elf_uncompress_failed(); return 0; } if (type == 0) { uint16_t len; uint16_t lenc; while (bits >= 8) { --pin; bits -= 8; } val = 0; bits = 0; if (unlikely((pinend - pin) < 4)) { elf_uncompress_failed(); return 0; } len = pin[0] | (pin[1] << 8); lenc = pin[2] | (pin[3] << 8); pin += 4; lenc = ~lenc; if (unlikely(len != lenc)) { elf_uncompress_failed(); return 0; } if (unlikely(len > (unsigned int)(pinend - pin) || len > (unsigned int)(poutend - pout))) { elf_uncompress_failed(); return 0; } memcpy(pout, pin, len); pout += len; pin += len; while ((((uintptr_t)pin) & 3) != 0) { val |= (uint64_t)*pin << bits; bits += 8; ++pin; } continue; } if (type == 1) { tlit = elf_zlib_default_table; tdist = elf_zlib_default_dist_table; } else { unsigned int nlit; unsigned int ndist; unsigned int nclen; unsigned char codebits[19]; unsigned char *plenbase; unsigned char *plen; unsigned char *plenend; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; nlit = (val & 0x1f) + 257; val >>= 5; ndist = (val & 0x1f) + 1; val >>= 5; nclen = (val & 0xf) + 4; val >>= 4; bits -= 14; if (unlikely(nlit > 286 || ndist > 30)) { elf_uncompress_failed(); return 0; } memset(&codebits[0], 0, 19); if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; codebits[16] = val & 7; codebits[17] = (val >> 3) & 7; codebits[18] = (val >> 6) & 7; codebits[0] = (val >> 9) & 7; val >>= 12; bits -= 12; if (nclen == 4) goto codebitsdone; codebits[8] = val & 7; val >>= 3; bits -= 3; if (nclen == 5) goto codebitsdone; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; codebits[7] = val & 7; val >>= 3; bits -= 3; if (nclen == 6) goto codebitsdone; codebits[9] = val & 7; val >>= 3; bits -= 3; if (nclen == 7) goto codebitsdone; codebits[6] = val & 7; val >>= 3; bits -= 3; if (nclen == 8) goto codebitsdone; codebits[10] = val & 7; val >>= 3; bits -= 3; if (nclen == 9) goto codebitsdone; codebits[5] = val & 7; val >>= 3; bits -= 3; if (nclen == 10) goto codebitsdone; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; codebits[11] = val & 7; val >>= 3; bits -= 3; if (nclen == 11) goto codebitsdone; codebits[4] = val & 7; val >>= 3; bits -= 3; if (nclen == 12) goto codebitsdone; codebits[12] = val & 7; val >>= 3; bits -= 3; if (nclen == 13) goto codebitsdone; codebits[3] = val & 7; val >>= 3; bits -= 3; if (nclen == 14) goto codebitsdone; codebits[13] = val & 7; val >>= 3; bits -= 3; if (nclen == 15) goto codebitsdone; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; codebits[2] = val & 7; val >>= 3; bits -= 3; if (nclen == 16) goto codebitsdone; codebits[14] = val & 7; val >>= 3; bits -= 3; if (nclen == 17) goto codebitsdone; codebits[1] = val & 7; val >>= 3; bits -= 3; if (nclen == 18) goto codebitsdone; codebits[15] = val & 7; val >>= 3; bits -= 3; codebitsdone: if (!elf_zlib_inflate_table(codebits, 19, zdebug_table, zdebug_table)) return 0; plenbase = (((unsigned char *)zdebug_table) + ZDEBUG_TABLE_CODELEN_OFFSET); plen = plenbase; plenend = plen + nlit + ndist; while (plen < plenend) { uint16_t t; unsigned int b; uint16_t v; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; t = zdebug_table[val & 0xff]; if (unlikely((t & (1U << HUFFMAN_SECONDARY_SHIFT)) != 0)) { elf_uncompress_failed(); return 0; } b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK; val >>= b + 1; bits -= b + 1; v = t & HUFFMAN_VALUE_MASK; if (v < 16) *plen++ = v; else if (v == 16) { unsigned int c; unsigned int prev; if (unlikely(plen == plenbase)) { elf_uncompress_failed(); return 0; } c = 3 + (val & 0x3); val >>= 2; bits -= 2; if (unlikely((unsigned int)(plenend - plen) < c)) { elf_uncompress_failed(); return 0; } prev = plen[-1]; switch (c) { case 6: *plen++ = prev; ATTRIBUTE_FALLTHROUGH; case 5: *plen++ = prev; ATTRIBUTE_FALLTHROUGH; case 4: *plen++ = prev; } *plen++ = prev; *plen++ = prev; *plen++ = prev; } else if (v == 17) { unsigned int c; c = 3 + (val & 0x7); val >>= 3; bits -= 3; if (unlikely((unsigned int)(plenend - plen) < c)) { elf_uncompress_failed(); return 0; } switch (c) { case 10: *plen++ = 0; ATTRIBUTE_FALLTHROUGH; case 9: *plen++ = 0; ATTRIBUTE_FALLTHROUGH; case 8: *plen++ = 0; ATTRIBUTE_FALLTHROUGH; case 7: *plen++ = 0; ATTRIBUTE_FALLTHROUGH; case 6: *plen++ = 0; ATTRIBUTE_FALLTHROUGH; case 5: *plen++ = 0; ATTRIBUTE_FALLTHROUGH; case 4: *plen++ = 0; } *plen++ = 0; *plen++ = 0; *plen++ = 0; } else if (v == 18) { unsigned int c; c = 11 + (val & 0x7f); val >>= 7; bits -= 7; if (unlikely((unsigned int)(plenend - plen) < c)) { elf_uncompress_failed(); return 0; } memset(plen, 0, c); plen += c; } else { elf_uncompress_failed(); return 0; } } plen = plenbase; if (unlikely(plen[256] == 0)) { elf_uncompress_failed(); return 0; } if (!elf_zlib_inflate_table(plen, nlit, zdebug_table, zdebug_table)) return 0; if (!elf_zlib_inflate_table(plen + nlit, ndist, zdebug_table, zdebug_table + HUFFMAN_TABLE_SIZE)) return 0; tlit = zdebug_table; tdist = zdebug_table + HUFFMAN_TABLE_SIZE; } while (1) { uint16_t t; unsigned int b; uint16_t v; unsigned int lit; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; t = tlit[val & 0xff]; b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK; v = t & HUFFMAN_VALUE_MASK; if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0) { lit = v; val >>= b + 1; bits -= b + 1; } else { t = tlit[v + 0x100 + ((val >> 8) & ((1U << b) - 1))]; b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK; lit = t & HUFFMAN_VALUE_MASK; val >>= b + 8; bits -= b + 8; } if (lit < 256) { if (unlikely(pout == poutend)) { elf_uncompress_failed(); return 0; } *pout++ = lit; __builtin_prefetch(pout, 1, 3); } else if (lit == 256) { break; } else { unsigned int dist; unsigned int len; if (lit < 265) len = lit - 257 + 3; else if (lit == 285) len = 258; else if (unlikely(lit > 285)) { elf_uncompress_failed(); return 0; } else { unsigned int extra; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; lit -= 265; extra = (lit >> 2) + 1; len = (lit & 3) << extra; len += 11; len += ((1U << (extra - 1)) - 1) << 3; len += val & ((1U << extra) - 1); val >>= extra; bits -= extra; } if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; t = tdist[val & 0xff]; b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK; v = t & HUFFMAN_VALUE_MASK; if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0) { dist = v; val >>= b + 1; bits -= b + 1; } else { t = tdist[v + 0x100 + ((val >> 8) & ((1U << b) - 1))]; b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK; dist = t & HUFFMAN_VALUE_MASK; val >>= b + 8; bits -= b + 8; } if (dist == 0) { if (unlikely(pout == porigout)) { elf_uncompress_failed(); return 0; } if (unlikely((unsigned int)(poutend - pout) < len)) { elf_uncompress_failed(); return 0; } memset(pout, pout[-1], len); pout += len; } else if (unlikely(dist > 29)) { elf_uncompress_failed(); return 0; } else { if (dist < 4) dist = dist + 1; else { unsigned int extra; if (!elf_zlib_fetch(&pin, pinend, &val, &bits)) return 0; dist -= 4; extra = (dist >> 1) + 1; dist = (dist & 1) << extra; dist += 5; dist += ((1U << (extra - 1)) - 1) << 2; dist += val & ((1U << extra) - 1); val >>= extra; bits -= extra; } if (unlikely((unsigned int)(pout - porigout) < dist)) { elf_uncompress_failed(); return 0; } if (unlikely((unsigned int)(poutend - pout) < len)) { elf_uncompress_failed(); return 0; } if (dist >= len) { memcpy(pout, pout - dist, len); pout += len; } else { while (len > 0) { unsigned int copy; copy = len < dist ? len : dist; memcpy(pout, pout - dist, copy); len -= copy; pout += copy; } } } } } } } if (unlikely(pout != poutend)) { elf_uncompress_failed(); return 0; } return 1; } static int elf_zlib_verify_checksum(const unsigned char *checkbytes, const unsigned char *uncompressed, size_t uncompressed_size) { unsigned int i; unsigned int cksum; const unsigned char *p; uint32_t s1; uint32_t s2; size_t hsz; cksum = 0; for (i = 0; i < 4; i++) cksum = (cksum << 8) | checkbytes[i]; s1 = 1; s2 = 0; p = uncompressed; hsz = uncompressed_size; while (hsz >= 5552) { for (i = 0; i < 5552; i += 16) { s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; } hsz -= 5552; s1 %= 65521; s2 %= 65521; } while (hsz >= 16) { s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; s1 = s1 + *p++; s2 = s2 + s1; hsz -= 16; } for (i = 0; i < hsz; ++i) { s1 = s1 + *p++; s2 = s2 + s1; } s1 %= 65521; s2 %= 65521; if (unlikely((s2 << 16) + s1 != cksum)) { elf_uncompress_failed(); return 0; } return 1; } static int elf_zlib_inflate_and_verify(const unsigned char *pin, size_t sin, uint16_t *zdebug_table, unsigned char *pout, size_t sout) { if (!elf_zlib_inflate(pin, sin, zdebug_table, pout, sout)) return 0; if (!elf_zlib_verify_checksum(pin + sin - 4, pout, sout)) return 0; return 1; } static int elf_uncompress_zdebug(struct backtrace_state *state, const unsigned char *compressed, size_t compressed_size, uint16_t *zdebug_table, backtrace_error_callback error_callback, void *data, unsigned char **uncompressed, size_t *uncompressed_size) { size_t sz; size_t i; unsigned char *po; *uncompressed = NULL; *uncompressed_size = 0; if (compressed_size < 12 || memcmp(compressed, "ZLIB", 4) != 0) return 1; sz = 0; for (i = 0; i < 8; i++) sz = (sz << 8) | compressed[i + 4]; if (*uncompressed != NULL && *uncompressed_size >= sz) po = *uncompressed; else { po = (unsigned char *)backtrace_alloc(state, sz, error_callback, data); if (po == NULL) return 0; } if (!elf_zlib_inflate_and_verify(compressed + 12, compressed_size - 12, zdebug_table, po, sz)) return 1; *uncompressed = po; *uncompressed_size = sz; return 1; } static int elf_uncompress_chdr(struct backtrace_state *state, const unsigned char *compressed, size_t compressed_size, uint16_t *zdebug_table, backtrace_error_callback error_callback, void *data, unsigned char **uncompressed, size_t *uncompressed_size) { const b_elf_chdr *chdr; unsigned char *po; *uncompressed = NULL; *uncompressed_size = 0; if (compressed_size < sizeof(b_elf_chdr)) return 1; chdr = (const b_elf_chdr *)compressed; if (chdr->ch_type != ELFCOMPRESS_ZLIB) { return 1; } if (*uncompressed != NULL && *uncompressed_size >= chdr->ch_size) po = *uncompressed; else { po = (unsigned char *)backtrace_alloc(state, chdr->ch_size, error_callback, data); if (po == NULL) return 0; } if (!elf_zlib_inflate_and_verify(compressed + sizeof(b_elf_chdr), compressed_size - sizeof(b_elf_chdr), zdebug_table, po, chdr->ch_size)) return 1; *uncompressed = po; *uncompressed_size = chdr->ch_size; return 1; } int backtrace_uncompress_zdebug(struct backtrace_state *state, const unsigned char *compressed, size_t compressed_size, backtrace_error_callback error_callback, void *data, unsigned char **uncompressed, size_t *uncompressed_size) { uint16_t *zdebug_table; int ret; zdebug_table = ((uint16_t *)backtrace_alloc(state, ZDEBUG_TABLE_SIZE, error_callback, data)); if (zdebug_table == NULL) return 0; ret = elf_uncompress_zdebug(state, compressed, compressed_size, zdebug_table, error_callback, data, uncompressed, uncompressed_size); backtrace_free(state, zdebug_table, ZDEBUG_TABLE_SIZE, error_callback, data); return ret; } #define LZMA_STATES (12) #define LZMA_POS_STATES (16) #define LZMA_DIST_STATES (4) #define LZMA_DIST_SLOTS (64) #define LZMA_DIST_MODEL_START (4) #define LZMA_DIST_MODEL_END (14) #define LZMA_FULL_DISTANCES (128) #define LZMA_ALIGN_SIZE (16) #define LZMA_LEN_LOW_SYMBOLS (8) #define LZMA_LEN_MID_SYMBOLS (8) #define LZMA_LEN_HIGH_SYMBOLS (256) #define LZMA_LITERAL_CODERS_MAX (16) #define LZMA_LITERAL_CODER_SIZE (0x300) #define LZMA_PROB_IS_MATCH_LEN (LZMA_STATES * LZMA_POS_STATES) #define LZMA_PROB_IS_REP_LEN LZMA_STATES #define LZMA_PROB_IS_REP0_LEN LZMA_STATES #define LZMA_PROB_IS_REP1_LEN LZMA_STATES #define LZMA_PROB_IS_REP2_LEN LZMA_STATES #define LZMA_PROB_IS_REP0_LONG_LEN (LZMA_STATES * LZMA_POS_STATES) #define LZMA_PROB_DIST_SLOT_LEN (LZMA_DIST_STATES * LZMA_DIST_SLOTS) #define LZMA_PROB_DIST_SPECIAL_LEN (LZMA_FULL_DISTANCES - LZMA_DIST_MODEL_END) #define LZMA_PROB_DIST_ALIGN_LEN LZMA_ALIGN_SIZE #define LZMA_PROB_MATCH_LEN_CHOICE_LEN 1 #define LZMA_PROB_MATCH_LEN_CHOICE2_LEN 1 #define LZMA_PROB_MATCH_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS) #define LZMA_PROB_MATCH_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS) #define LZMA_PROB_MATCH_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS #define LZMA_PROB_REP_LEN_CHOICE_LEN 1 #define LZMA_PROB_REP_LEN_CHOICE2_LEN 1 #define LZMA_PROB_REP_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS) #define LZMA_PROB_REP_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS) #define LZMA_PROB_REP_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS #define LZMA_PROB_LITERAL_LEN \ (LZMA_LITERAL_CODERS_MAX * LZMA_LITERAL_CODER_SIZE) #define LZMA_PROB_IS_MATCH_OFFSET 0 #define LZMA_PROB_IS_REP_OFFSET \ (LZMA_PROB_IS_MATCH_OFFSET + LZMA_PROB_IS_MATCH_LEN) #define LZMA_PROB_IS_REP0_OFFSET \ (LZMA_PROB_IS_REP_OFFSET + LZMA_PROB_IS_REP_LEN) #define LZMA_PROB_IS_REP1_OFFSET \ (LZMA_PROB_IS_REP0_OFFSET + LZMA_PROB_IS_REP0_LEN) #define LZMA_PROB_IS_REP2_OFFSET \ (LZMA_PROB_IS_REP1_OFFSET + LZMA_PROB_IS_REP1_LEN) #define LZMA_PROB_IS_REP0_LONG_OFFSET \ (LZMA_PROB_IS_REP2_OFFSET + LZMA_PROB_IS_REP2_LEN) #define LZMA_PROB_DIST_SLOT_OFFSET \ (LZMA_PROB_IS_REP0_LONG_OFFSET + LZMA_PROB_IS_REP0_LONG_LEN) #define LZMA_PROB_DIST_SPECIAL_OFFSET \ (LZMA_PROB_DIST_SLOT_OFFSET + LZMA_PROB_DIST_SLOT_LEN) #define LZMA_PROB_DIST_ALIGN_OFFSET \ (LZMA_PROB_DIST_SPECIAL_OFFSET + LZMA_PROB_DIST_SPECIAL_LEN) #define LZMA_PROB_MATCH_LEN_CHOICE_OFFSET \ (LZMA_PROB_DIST_ALIGN_OFFSET + LZMA_PROB_DIST_ALIGN_LEN) #define LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET \ (LZMA_PROB_MATCH_LEN_CHOICE_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE_LEN) #define LZMA_PROB_MATCH_LEN_LOW_OFFSET \ (LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE2_LEN) #define LZMA_PROB_MATCH_LEN_MID_OFFSET \ (LZMA_PROB_MATCH_LEN_LOW_OFFSET + LZMA_PROB_MATCH_LEN_LOW_LEN) #define LZMA_PROB_MATCH_LEN_HIGH_OFFSET \ (LZMA_PROB_MATCH_LEN_MID_OFFSET + LZMA_PROB_MATCH_LEN_MID_LEN) #define LZMA_PROB_REP_LEN_CHOICE_OFFSET \ (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + LZMA_PROB_MATCH_LEN_HIGH_LEN) #define LZMA_PROB_REP_LEN_CHOICE2_OFFSET \ (LZMA_PROB_REP_LEN_CHOICE_OFFSET + LZMA_PROB_REP_LEN_CHOICE_LEN) #define LZMA_PROB_REP_LEN_LOW_OFFSET \ (LZMA_PROB_REP_LEN_CHOICE2_OFFSET + LZMA_PROB_REP_LEN_CHOICE2_LEN) #define LZMA_PROB_REP_LEN_MID_OFFSET \ (LZMA_PROB_REP_LEN_LOW_OFFSET + LZMA_PROB_REP_LEN_LOW_LEN) #define LZMA_PROB_REP_LEN_HIGH_OFFSET \ (LZMA_PROB_REP_LEN_MID_OFFSET + LZMA_PROB_REP_LEN_MID_LEN) #define LZMA_PROB_LITERAL_OFFSET \ (LZMA_PROB_REP_LEN_HIGH_OFFSET + LZMA_PROB_REP_LEN_HIGH_LEN) #define LZMA_PROB_TOTAL_COUNT (LZMA_PROB_LITERAL_OFFSET + LZMA_PROB_LITERAL_LEN) #if LZMA_PROB_TOTAL_COUNT != 1846 + (1 << 4) * 0x300 #error Wrong number of LZMA probabilities #endif #define LZMA_IS_MATCH(state, pos) \ (LZMA_PROB_IS_MATCH_OFFSET + (state)*LZMA_POS_STATES + (pos)) #define LZMA_IS_REP(state) (LZMA_PROB_IS_REP_OFFSET + (state)) #define LZMA_IS_REP0(state) (LZMA_PROB_IS_REP0_OFFSET + (state)) #define LZMA_IS_REP1(state) (LZMA_PROB_IS_REP1_OFFSET + (state)) #define LZMA_IS_REP2(state) (LZMA_PROB_IS_REP2_OFFSET + (state)) #define LZMA_IS_REP0_LONG(state, pos) \ (LZMA_PROB_IS_REP0_LONG_OFFSET + (state)*LZMA_POS_STATES + (pos)) #define LZMA_DIST_SLOT(dist, slot) \ (LZMA_PROB_DIST_SLOT_OFFSET + (dist)*LZMA_DIST_SLOTS + (slot)) #define LZMA_DIST_SPECIAL(dist) (LZMA_PROB_DIST_SPECIAL_OFFSET + (dist)) #define LZMA_DIST_ALIGN(dist) (LZMA_PROB_DIST_ALIGN_OFFSET + (dist)) #define LZMA_MATCH_LEN_CHOICE LZMA_PROB_MATCH_LEN_CHOICE_OFFSET #define LZMA_MATCH_LEN_CHOICE2 LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET #define LZMA_MATCH_LEN_LOW(pos, sym) \ (LZMA_PROB_MATCH_LEN_LOW_OFFSET + (pos)*LZMA_LEN_LOW_SYMBOLS + (sym)) #define LZMA_MATCH_LEN_MID(pos, sym) \ (LZMA_PROB_MATCH_LEN_MID_OFFSET + (pos)*LZMA_LEN_MID_SYMBOLS + (sym)) #define LZMA_MATCH_LEN_HIGH(sym) (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + (sym)) #define LZMA_REP_LEN_CHOICE LZMA_PROB_REP_LEN_CHOICE_OFFSET #define LZMA_REP_LEN_CHOICE2 LZMA_PROB_REP_LEN_CHOICE2_OFFSET #define LZMA_REP_LEN_LOW(pos, sym) \ (LZMA_PROB_REP_LEN_LOW_OFFSET + (pos)*LZMA_LEN_LOW_SYMBOLS + (sym)) #define LZMA_REP_LEN_MID(pos, sym) \ (LZMA_PROB_REP_LEN_MID_OFFSET + (pos)*LZMA_LEN_MID_SYMBOLS + (sym)) #define LZMA_REP_LEN_HIGH(sym) (LZMA_PROB_REP_LEN_HIGH_OFFSET + (sym)) #define LZMA_LITERAL(code, size) \ (LZMA_PROB_LITERAL_OFFSET + (code)*LZMA_LITERAL_CODER_SIZE + (size)) static int elf_lzma_varint(const unsigned char *compressed, size_t compressed_size, size_t *poffset, uint64_t *val) { size_t off; int i; uint64_t v; unsigned char b; off = *poffset; i = 0; v = 0; while (1) { if (unlikely(off >= compressed_size)) { elf_uncompress_failed(); return 0; } b = compressed[off]; v |= (b & 0x7f) << (i * 7); ++off; if ((b & 0x80) == 0) { *poffset = off; *val = v; return 1; } ++i; if (unlikely(i >= 9)) { elf_uncompress_failed(); return 0; } } } static void elf_lzma_range_normalize(const unsigned char *compressed, size_t compressed_size, size_t *poffset, uint32_t *prange, uint32_t *pcode) { if (*prange < (1U << 24)) { if (unlikely(*poffset >= compressed_size)) { elf_uncompress_failed(); return; } *prange <<= 8; *pcode <<= 8; *pcode += compressed[*poffset]; ++*poffset; } } static int elf_lzma_bit(const unsigned char *compressed, size_t compressed_size, uint16_t *prob, size_t *poffset, uint32_t *prange, uint32_t *pcode) { uint32_t bound; elf_lzma_range_normalize(compressed, compressed_size, poffset, prange, pcode); bound = (*prange >> 11) * (uint32_t)*prob; if (*pcode < bound) { *prange = bound; *prob += ((1U << 11) - *prob) >> 5; return 0; } else { *prange -= bound; *pcode -= bound; *prob -= *prob >> 5; return 1; } } static uint32_t elf_lzma_integer(const unsigned char *compressed, size_t compressed_size, uint16_t *probs, uint32_t bits, size_t *poffset, uint32_t *prange, uint32_t *pcode) { uint32_t sym; uint32_t i; sym = 1; for (i = 0; i < bits; i++) { int bit; bit = elf_lzma_bit(compressed, compressed_size, probs + sym, poffset, prange, pcode); sym <<= 1; sym += bit; } return sym - (1 << bits); } static uint32_t elf_lzma_reverse_integer(const unsigned char *compressed, size_t compressed_size, uint16_t *probs, uint32_t bits, size_t *poffset, uint32_t *prange, uint32_t *pcode) { uint32_t sym; uint32_t val; uint32_t i; sym = 1; val = 0; for (i = 0; i < bits; i++) { int bit; bit = elf_lzma_bit(compressed, compressed_size, probs + sym, poffset, prange, pcode); sym <<= 1; sym += bit; val += bit << i; } return val; } static uint32_t elf_lzma_len(const unsigned char *compressed, size_t compressed_size, uint16_t *probs, int is_rep, unsigned int pos_state, size_t *poffset, uint32_t *prange, uint32_t *pcode) { uint16_t *probs_choice; uint16_t *probs_sym; uint32_t bits; uint32_t len; probs_choice = probs + (is_rep ? LZMA_REP_LEN_CHOICE : LZMA_MATCH_LEN_CHOICE); if (elf_lzma_bit(compressed, compressed_size, probs_choice, poffset, prange, pcode)) { probs_choice = probs + (is_rep ? LZMA_REP_LEN_CHOICE2 : LZMA_MATCH_LEN_CHOICE2); if (elf_lzma_bit(compressed, compressed_size, probs_choice, poffset, prange, pcode)) { probs_sym = probs + (is_rep ? LZMA_REP_LEN_HIGH(0) : LZMA_MATCH_LEN_HIGH(0)); bits = 8; len = 2 + 8 + 8; } else { probs_sym = probs + (is_rep ? LZMA_REP_LEN_MID(pos_state, 0) : LZMA_MATCH_LEN_MID(pos_state, 0)); bits = 3; len = 2 + 8; } } else { probs_sym = probs + (is_rep ? LZMA_REP_LEN_LOW(pos_state, 0) : LZMA_MATCH_LEN_LOW(pos_state, 0)); bits = 3; len = 2; } len += elf_lzma_integer(compressed, compressed_size, probs_sym, bits, poffset, prange, pcode); return len; } static int elf_uncompress_lzma_block(const unsigned char *compressed, size_t compressed_size, unsigned char check, uint16_t *probs, unsigned char *uncompressed, size_t uncompressed_size, size_t *poffset) { size_t off; size_t block_header_offset; size_t block_header_size; unsigned char block_flags; uint64_t header_compressed_size; uint64_t header_uncompressed_size; unsigned char lzma2_properties; uint32_t computed_crc; uint32_t stream_crc; size_t uncompressed_offset; size_t dict_start_offset; unsigned int lc; unsigned int lp; unsigned int pb; uint32_t range; uint32_t code; uint32_t lstate; uint32_t dist[4]; off = *poffset; block_header_offset = off; if (unlikely(off >= compressed_size)) { elf_uncompress_failed(); return 0; } block_header_size = (compressed[off] + 1) * 4; if (unlikely(off + block_header_size > compressed_size)) { elf_uncompress_failed(); return 0; } block_flags = compressed[off + 1]; if (unlikely((block_flags & 0x3c) != 0)) { elf_uncompress_failed(); return 0; } off += 2; header_compressed_size = 0; if ((block_flags & 0x40) != 0) { *poffset = off; if (!elf_lzma_varint(compressed, compressed_size, poffset, &header_compressed_size)) return 0; off = *poffset; } header_uncompressed_size = 0; if ((block_flags & 0x80) != 0) { *poffset = off; if (!elf_lzma_varint(compressed, compressed_size, poffset, &header_uncompressed_size)) return 0; off = *poffset; } if (unlikely((block_flags & 0x3) != 0)) { elf_uncompress_failed(); return 0; } if (unlikely(off + 2 >= block_header_offset + block_header_size)) { elf_uncompress_failed(); return 0; } if (unlikely(compressed[off] != 0x21)) { elf_uncompress_failed(); return 0; } ++off; if (unlikely(compressed[off] != 1)) { elf_uncompress_failed(); return 0; } ++off; lzma2_properties = compressed[off]; ++off; if (unlikely(lzma2_properties > 40)) { elf_uncompress_failed(); return 0; } if (unlikely(off + 4 > compressed_size)) { elf_uncompress_failed(); return 0; } off = (off + 3) & ~(size_t)3; if (unlikely(off + 4 > compressed_size)) { elf_uncompress_failed(); return 0; } computed_crc = elf_crc32(0, compressed + block_header_offset, block_header_size - 4); stream_crc = (compressed[off] | (compressed[off + 1] << 8) | (compressed[off + 2] << 16) | (compressed[off + 3] << 24)); if (unlikely(computed_crc != stream_crc)) { elf_uncompress_failed(); return 0; } off += 4; uncompressed_offset = 0; dict_start_offset = 0; lc = 0; lp = 0; pb = 0; lstate = 0; while (off < compressed_size) { unsigned char control; range = 0xffffffff; code = 0; control = compressed[off]; ++off; if (unlikely(control == 0)) { break; } if (control == 1 || control >= 0xe0) { dict_start_offset = uncompressed_offset; } if (control < 0x80) { size_t chunk_size; if (unlikely(control > 2)) { elf_uncompress_failed(); return 0; } if (unlikely(off + 2 > compressed_size)) { elf_uncompress_failed(); return 0; } chunk_size = compressed[off] << 8; chunk_size += compressed[off + 1]; ++chunk_size; off += 2; if (unlikely(off + chunk_size > compressed_size)) { elf_uncompress_failed(); return 0; } if (unlikely(uncompressed_offset + chunk_size > uncompressed_size)) { elf_uncompress_failed(); return 0; } memcpy(uncompressed + uncompressed_offset, compressed + off, chunk_size); uncompressed_offset += chunk_size; off += chunk_size; } else { size_t uncompressed_chunk_start; size_t uncompressed_chunk_size; size_t compressed_chunk_size; size_t limit; if (unlikely(off + 4 >= compressed_size)) { elf_uncompress_failed(); return 0; } uncompressed_chunk_start = uncompressed_offset; uncompressed_chunk_size = (control & 0x1f) << 16; uncompressed_chunk_size += compressed[off] << 8; uncompressed_chunk_size += compressed[off + 1]; ++uncompressed_chunk_size; compressed_chunk_size = compressed[off + 2] << 8; compressed_chunk_size += compressed[off + 3]; ++compressed_chunk_size; off += 4; if (control >= 0xc0) { unsigned char props; if (unlikely(off >= compressed_size)) { elf_uncompress_failed(); return 0; } props = compressed[off]; ++off; if (unlikely(props > (4 * 5 + 4) * 9 + 8)) { elf_uncompress_failed(); return 0; } pb = 0; while (props >= 9 * 5) { props -= 9 * 5; ++pb; } lp = 0; while (props > 9) { props -= 9; ++lp; } lc = props; if (unlikely(lc + lp > 4)) { elf_uncompress_failed(); return 0; } } if (control >= 0xa0) { size_t i; lstate = 0; memset(&dist, 0, sizeof dist); for (i = 0; i < LZMA_PROB_TOTAL_COUNT; i++) probs[i] = 1 << 10; range = 0xffffffff; code = 0; } if (unlikely(off + 5 > compressed_size)) { elf_uncompress_failed(); return 0; } code = ((compressed[off + 1] << 24) + (compressed[off + 2] << 16) + (compressed[off + 3] << 8) + compressed[off + 4]); off += 5; limit = off + compressed_chunk_size; *poffset = off; while (*poffset < limit) { unsigned int pos_state; if (unlikely(uncompressed_offset == (uncompressed_chunk_start + uncompressed_chunk_size))) { break; } pos_state = ((uncompressed_offset - dict_start_offset) & ((1 << pb) - 1)); if (elf_lzma_bit(compressed, compressed_size, probs + LZMA_IS_MATCH(lstate, pos_state), poffset, &range, &code)) { uint32_t len; if (elf_lzma_bit(compressed, compressed_size, probs + LZMA_IS_REP(lstate), poffset, &range, &code)) { int short_rep; uint32_t next_dist; short_rep = 0; if (elf_lzma_bit(compressed, compressed_size, probs + LZMA_IS_REP0(lstate), poffset, &range, &code)) { if (elf_lzma_bit(compressed, compressed_size, probs + LZMA_IS_REP1(lstate), poffset, &range, &code)) { if (elf_lzma_bit(compressed, compressed_size, probs + LZMA_IS_REP2(lstate), poffset, &range, &code)) { next_dist = dist[3]; dist[3] = dist[2]; } else { next_dist = dist[2]; } dist[2] = dist[1]; } else { next_dist = dist[1]; } dist[1] = dist[0]; dist[0] = next_dist; } else { if (!elf_lzma_bit(compressed, compressed_size, (probs + LZMA_IS_REP0_LONG(lstate, pos_state)), poffset, &range, &code)) short_rep = 1; } if (lstate < 7) lstate = short_rep ? 9 : 8; else lstate = 11; if (short_rep) len = 1; else len = elf_lzma_len(compressed, compressed_size, probs, 1, pos_state, poffset, &range, &code); } else { uint32_t dist_state; uint32_t dist_slot; uint16_t *probs_dist; if (lstate < 7) lstate = 7; else lstate = 10; dist[3] = dist[2]; dist[2] = dist[1]; dist[1] = dist[0]; len = elf_lzma_len(compressed, compressed_size, probs, 0, pos_state, poffset, &range, &code); if (len < 4 + 2) dist_state = len - 2; else dist_state = 3; probs_dist = probs + LZMA_DIST_SLOT(dist_state, 0); dist_slot = elf_lzma_integer(compressed, compressed_size, probs_dist, 6, poffset, &range, &code); if (dist_slot < LZMA_DIST_MODEL_START) dist[0] = dist_slot; else { uint32_t limit; limit = (dist_slot >> 1) - 1; dist[0] = 2 + (dist_slot & 1); if (dist_slot < LZMA_DIST_MODEL_END) { dist[0] <<= limit; probs_dist = (probs + LZMA_DIST_SPECIAL(dist[0] - dist_slot - 1)); dist[0] += elf_lzma_reverse_integer(compressed, compressed_size, probs_dist, limit, poffset, &range, &code); } else { uint32_t dist0; uint32_t i; dist0 = dist[0]; for (i = 0; i < limit - 4; i++) { uint32_t mask; elf_lzma_range_normalize(compressed, compressed_size, poffset, &range, &code); range >>= 1; code -= range; mask = -(code >> 31); code += range & mask; dist0 <<= 1; dist0 += mask + 1; } dist0 <<= 4; probs_dist = probs + LZMA_DIST_ALIGN(0); dist0 += elf_lzma_reverse_integer(compressed, compressed_size, probs_dist, 4, poffset, &range, &code); dist[0] = dist0; } } } if (unlikely(uncompressed_offset - dict_start_offset < dist[0] + 1)) { elf_uncompress_failed(); return 0; } if (unlikely(uncompressed_offset + len > uncompressed_size)) { elf_uncompress_failed(); return 0; } if (dist[0] == 0) { memset(uncompressed + uncompressed_offset, uncompressed[uncompressed_offset - 1], len); uncompressed_offset += len; } else if (dist[0] + 1 >= len) { memcpy(uncompressed + uncompressed_offset, uncompressed + uncompressed_offset - dist[0] - 1, len); uncompressed_offset += len; } else { while (len > 0) { uint32_t copy; copy = len < dist[0] + 1 ? len : dist[0] + 1; memcpy(uncompressed + uncompressed_offset, (uncompressed + uncompressed_offset - dist[0] - 1), copy); len -= copy; uncompressed_offset += copy; } } } else { unsigned char prev; unsigned char low; size_t high; uint16_t *lit_probs; unsigned int sym; if (uncompressed_offset > 0) prev = uncompressed[uncompressed_offset - 1]; else prev = 0; low = prev >> (8 - lc); high = (((uncompressed_offset - dict_start_offset) & ((1 << lp) - 1)) << lc); lit_probs = probs + LZMA_LITERAL(low + high, 0); if (lstate < 7) sym = elf_lzma_integer(compressed, compressed_size, lit_probs, 8, poffset, &range, &code); else { unsigned int match; unsigned int bit; unsigned int match_bit; unsigned int idx; sym = 1; if (uncompressed_offset >= dist[0] + 1) match = uncompressed[uncompressed_offset - dist[0] - 1]; else match = 0; match <<= 1; bit = 0x100; do { match_bit = match & bit; match <<= 1; idx = bit + match_bit + sym; sym <<= 1; if (elf_lzma_bit(compressed, compressed_size, lit_probs + idx, poffset, &range, &code)) { ++sym; bit &= match_bit; } else { bit &= ~match_bit; } } while (sym < 0x100); } if (unlikely(uncompressed_offset >= uncompressed_size)) { elf_uncompress_failed(); return 0; } uncompressed[uncompressed_offset] = (unsigned char)sym; ++uncompressed_offset; if (lstate <= 3) lstate = 0; else if (lstate <= 9) lstate -= 3; else lstate -= 6; } } elf_lzma_range_normalize(compressed, compressed_size, poffset, &range, &code); off = *poffset; } } off = (off + 3) & ~(size_t)3; if (unlikely(off > compressed_size)) { elf_uncompress_failed(); return 0; } switch (check) { case 0: break; case 1: if (unlikely(off + 4 > compressed_size)) { elf_uncompress_failed(); return 0; } computed_crc = elf_crc32(0, uncompressed, uncompressed_offset); stream_crc = (compressed[off] | (compressed[off + 1] << 8) | (compressed[off + 2] << 16) | (compressed[off + 3] << 24)); if (computed_crc != stream_crc) { elf_uncompress_failed(); return 0; } off += 4; break; case 4: if (unlikely(off + 8 > compressed_size)) { elf_uncompress_failed(); return 0; } off += 8; break; case 10: if (unlikely(off + 32 > compressed_size)) { elf_uncompress_failed(); return 0; } off += 32; break; default: elf_uncompress_failed(); return 0; } *poffset = off; return 1; } static int elf_uncompress_lzma(struct backtrace_state *state, const unsigned char *compressed, size_t compressed_size, backtrace_error_callback error_callback, void *data, unsigned char **uncompressed, size_t *uncompressed_size) { size_t header_size; size_t footer_size; unsigned char check; uint32_t computed_crc; uint32_t stream_crc; size_t offset; size_t index_size; size_t footer_offset; size_t index_offset; uint64_t index_compressed_size; uint64_t index_uncompressed_size; unsigned char *mem; uint16_t *probs; size_t compressed_block_size; header_size = 12; footer_size = 12; if (unlikely(compressed_size < header_size + footer_size)) { elf_uncompress_failed(); return 0; } if (unlikely(memcmp(compressed, "\375" "7zXZ\0", 6) != 0)) { elf_uncompress_failed(); return 0; } if (unlikely(compressed[6] != 0)) { elf_uncompress_failed(); return 0; } check = compressed[7]; if (unlikely((check & 0xf8) != 0)) { elf_uncompress_failed(); return 0; } computed_crc = elf_crc32(0, compressed + 6, 2); stream_crc = (compressed[8] | (compressed[9] << 8) | (compressed[10] << 16) | (compressed[11] << 24)); if (unlikely(computed_crc != stream_crc)) { elf_uncompress_failed(); return 0; } offset = compressed_size; if (unlikely(memcmp(compressed + offset - 2, "YZ", 2) != 0)) { elf_uncompress_failed(); return 0; } offset -= 2; if (unlikely(compressed[offset - 2] != 0 || compressed[offset - 1] != check)) { elf_uncompress_failed(); return 0; } offset -= 2; index_size = (compressed[offset - 4] | (compressed[offset - 3] << 8) | (compressed[offset - 2] << 16) | (compressed[offset - 1] << 24)); index_size = (index_size + 1) * 4; offset -= 4; computed_crc = elf_crc32(0, compressed + offset, 6); stream_crc = (compressed[offset - 4] | (compressed[offset - 3] << 8) | (compressed[offset - 2] << 16) | (compressed[offset - 1] << 24)); if (unlikely(computed_crc != stream_crc)) { elf_uncompress_failed(); return 0; } offset -= 4; if (unlikely(offset < index_size + header_size)) { elf_uncompress_failed(); return 0; } footer_offset = offset; offset -= index_size; index_offset = offset; if (unlikely(compressed[offset] != 0)) { elf_uncompress_failed(); return 0; } ++offset; if (unlikely(compressed[offset] == 0)) { *uncompressed = NULL; *uncompressed_size = 0; return 1; } if (unlikely(compressed[offset] != 1)) { elf_uncompress_failed(); return 0; } ++offset; if (!elf_lzma_varint(compressed, compressed_size, &offset, &index_compressed_size)) return 0; if (!elf_lzma_varint(compressed, compressed_size, &offset, &index_uncompressed_size)) return 0; offset = (offset + 3) & ~(size_t)3; computed_crc = elf_crc32(0, compressed + index_offset, offset - index_offset); stream_crc = (compressed[offset] | (compressed[offset + 1] << 8) | (compressed[offset + 2] << 16) | (compressed[offset + 3] << 24)); if (unlikely(computed_crc != stream_crc)) { elf_uncompress_failed(); return 0; } offset += 4; if (unlikely(offset != footer_offset)) { elf_uncompress_failed(); return 0; } mem = (unsigned char *)backtrace_alloc(state, index_uncompressed_size, error_callback, data); if (unlikely(mem == NULL)) return 0; *uncompressed = mem; *uncompressed_size = index_uncompressed_size; probs = ((uint16_t *)backtrace_alloc( state, LZMA_PROB_TOTAL_COUNT * sizeof(uint16_t), error_callback, data)); if (unlikely(probs == NULL)) { backtrace_free(state, mem, index_uncompressed_size, error_callback, data); return 0; } offset = 12; if (!elf_uncompress_lzma_block(compressed, compressed_size, check, probs, mem, index_uncompressed_size, &offset)) { backtrace_free(state, mem, index_uncompressed_size, error_callback, data); return 0; } compressed_block_size = offset - 12; if (unlikely(compressed_block_size != ((index_compressed_size + 3) & ~(size_t)3))) { elf_uncompress_failed(); backtrace_free(state, mem, index_uncompressed_size, error_callback, data); return 0; } offset = (offset + 3) & ~(size_t)3; if (unlikely(offset != index_offset)) { elf_uncompress_failed(); backtrace_free(state, mem, index_uncompressed_size, error_callback, data); return 0; } return 1; } int backtrace_uncompress_lzma(struct backtrace_state *state, const unsigned char *compressed, size_t compressed_size, backtrace_error_callback error_callback, void *data, unsigned char **uncompressed, size_t *uncompressed_size) { return elf_uncompress_lzma(state, compressed, compressed_size, error_callback, data, uncompressed, uncompressed_size); } static int elf_add(struct backtrace_state *state, const char *filename, int descriptor, const unsigned char *memory, size_t memory_size, uintptr_t base_address, backtrace_error_callback error_callback, void *data, fileline *fileline_fn, int *found_sym, int *found_dwarf, struct dwarf_data **fileline_entry, int exe, int debuginfo, const char *with_buildid_data, uint32_t with_buildid_size) { struct elf_view ehdr_view; b_elf_ehdr ehdr; off_t shoff; unsigned int shnum; unsigned int shstrndx; struct elf_view shdrs_view; int shdrs_view_valid; const b_elf_shdr *shdrs; const b_elf_shdr *shstrhdr; size_t shstr_size; off_t shstr_off; struct elf_view names_view; int names_view_valid; const char *names; unsigned int symtab_shndx; unsigned int dynsym_shndx; unsigned int i; struct debug_section_info sections[DEBUG_MAX]; struct debug_section_info zsections[DEBUG_MAX]; struct elf_view symtab_view; int symtab_view_valid; struct elf_view strtab_view; int strtab_view_valid; struct elf_view buildid_view; int buildid_view_valid; const char *buildid_data; uint32_t buildid_size; struct elf_view debuglink_view; int debuglink_view_valid; const char *debuglink_name; uint32_t debuglink_crc; struct elf_view debugaltlink_view; int debugaltlink_view_valid; const char *debugaltlink_name; const char *debugaltlink_buildid_data; uint32_t debugaltlink_buildid_size; struct elf_view gnu_debugdata_view; int gnu_debugdata_view_valid; size_t gnu_debugdata_size; unsigned char *gnu_debugdata_uncompressed; size_t gnu_debugdata_uncompressed_size; off_t min_offset; off_t max_offset; off_t debug_size; struct elf_view debug_view; int debug_view_valid; unsigned int using_debug_view; uint16_t *zdebug_table; struct elf_view split_debug_view[DEBUG_MAX]; unsigned char split_debug_view_valid[DEBUG_MAX]; struct elf_ppc64_opd_data opd_data, *opd; struct dwarf_sections dwarf_sections; if (!debuginfo) { *found_sym = 0; *found_dwarf = 0; } shdrs_view_valid = 0; names_view_valid = 0; symtab_view_valid = 0; strtab_view_valid = 0; buildid_view_valid = 0; buildid_data = NULL; buildid_size = 0; debuglink_view_valid = 0; debuglink_name = NULL; debuglink_crc = 0; debugaltlink_view_valid = 0; debugaltlink_name = NULL; debugaltlink_buildid_data = NULL; debugaltlink_buildid_size = 0; gnu_debugdata_view_valid = 0; gnu_debugdata_size = 0; debug_view_valid = 0; memset(&split_debug_view_valid[0], 0, sizeof split_debug_view_valid); opd = NULL; if (!elf_get_view(state, descriptor, memory, memory_size, 0, sizeof ehdr, error_callback, data, &ehdr_view)) goto fail; memcpy(&ehdr, ehdr_view.view.data, sizeof ehdr); elf_release_view(state, &ehdr_view, error_callback, data); if (ehdr.e_ident[EI_MAG0] != ELFMAG0 || ehdr.e_ident[EI_MAG1] != ELFMAG1 || ehdr.e_ident[EI_MAG2] != ELFMAG2 || ehdr.e_ident[EI_MAG3] != ELFMAG3) { error_callback(data, "executable file is not ELF", 0); goto fail; } if (ehdr.e_ident[EI_VERSION] != EV_CURRENT) { error_callback(data, "executable file is unrecognized ELF version", 0); goto fail; } #if BACKTRACE_ELF_SIZE == 32 #define BACKTRACE_ELFCLASS ELFCLASS32 #else #define BACKTRACE_ELFCLASS ELFCLASS64 #endif if (ehdr.e_ident[EI_CLASS] != BACKTRACE_ELFCLASS) { error_callback(data, "executable file is unexpected ELF class", 0); goto fail; } if (ehdr.e_ident[EI_DATA] != ELFDATA2LSB && ehdr.e_ident[EI_DATA] != ELFDATA2MSB) { error_callback(data, "executable file has unknown endianness", 0); goto fail; } if (exe && ehdr.e_type == ET_DYN) return -1; shoff = ehdr.e_shoff; shnum = ehdr.e_shnum; shstrndx = ehdr.e_shstrndx; if ((shnum == 0 || shstrndx == SHN_XINDEX) && shoff != 0) { struct elf_view shdr_view; const b_elf_shdr *shdr; if (!elf_get_view(state, descriptor, memory, memory_size, shoff, sizeof shdr, error_callback, data, &shdr_view)) goto fail; shdr = (const b_elf_shdr *)shdr_view.view.data; if (shnum == 0) shnum = shdr->sh_size; if (shstrndx == SHN_XINDEX) { shstrndx = shdr->sh_link; if (shstrndx >= shnum && shstrndx >= SHN_LORESERVE + 0x100) shstrndx -= 0x100; } elf_release_view(state, &shdr_view, error_callback, data); } if (shnum == 0 || shstrndx == 0) goto fail; if (!elf_get_view( state, descriptor, memory, memory_size, shoff + sizeof(b_elf_shdr), (shnum - 1) * sizeof(b_elf_shdr), error_callback, data, &shdrs_view)) goto fail; shdrs_view_valid = 1; shdrs = (const b_elf_shdr *)shdrs_view.view.data; shstrhdr = &shdrs[shstrndx - 1]; shstr_size = shstrhdr->sh_size; shstr_off = shstrhdr->sh_offset; if (!elf_get_view(state, descriptor, memory, memory_size, shstr_off, shstrhdr->sh_size, error_callback, data, &names_view)) goto fail; names_view_valid = 1; names = (const char *)names_view.view.data; symtab_shndx = 0; dynsym_shndx = 0; memset(sections, 0, sizeof sections); memset(zsections, 0, sizeof zsections); for (i = 1; i < shnum; ++i) { const b_elf_shdr *shdr; unsigned int sh_name; const char *name; int j; shdr = &shdrs[i - 1]; if (shdr->sh_type == SHT_SYMTAB) symtab_shndx = i; else if (shdr->sh_type == SHT_DYNSYM) dynsym_shndx = i; sh_name = shdr->sh_name; if (sh_name >= shstr_size) { error_callback(data, "ELF section name out of range", 0); goto fail; } name = names + sh_name; for (j = 0; j < (int)DEBUG_MAX; ++j) { if (strcmp(name, dwarf_section_names[j]) == 0) { sections[j].offset = shdr->sh_offset; sections[j].size = shdr->sh_size; sections[j].compressed = (shdr->sh_flags & SHF_COMPRESSED) != 0; break; } } if (name[0] == '.' && name[1] == 'z') { for (j = 0; j < (int)DEBUG_MAX; ++j) { if (strcmp(name + 2, dwarf_section_names[j] + 1) == 0) { zsections[j].offset = shdr->sh_offset; zsections[j].size = shdr->sh_size; break; } } } if ((!debuginfo || with_buildid_data != NULL) && !buildid_view_valid && strcmp(name, ".note.gnu.build-id") == 0) { const b_elf_note *note; if (!elf_get_view(state, descriptor, memory, memory_size, shdr->sh_offset, shdr->sh_size, error_callback, data, &buildid_view)) goto fail; buildid_view_valid = 1; note = (const b_elf_note *)buildid_view.view.data; if (note->type == NT_GNU_BUILD_ID && note->namesz == 4 && strncmp(note->name, "GNU", 4) == 0 && shdr->sh_size <= 12 + ((note->namesz + 3) & ~3) + note->descsz) { buildid_data = ¬e->name[0] + ((note->namesz + 3) & ~3); buildid_size = note->descsz; } if (with_buildid_size != 0) { if (buildid_size != with_buildid_size) goto fail; if (memcmp(buildid_data, with_buildid_data, buildid_size) != 0) goto fail; } } if (!debuginfo && !debuglink_view_valid && strcmp(name, ".gnu_debuglink") == 0) { const char *debuglink_data; size_t crc_offset; if (!elf_get_view(state, descriptor, memory, memory_size, shdr->sh_offset, shdr->sh_size, error_callback, data, &debuglink_view)) goto fail; debuglink_view_valid = 1; debuglink_data = (const char *)debuglink_view.view.data; crc_offset = strnlen(debuglink_data, shdr->sh_size); crc_offset = (crc_offset + 3) & ~3; if (crc_offset + 4 <= shdr->sh_size) { debuglink_name = debuglink_data; debuglink_crc = *(const uint32_t *)(debuglink_data + crc_offset); } } if (!debugaltlink_view_valid && strcmp(name, ".gnu_debugaltlink") == 0) { const char *debugaltlink_data; size_t debugaltlink_name_len; if (!elf_get_view(state, descriptor, memory, memory_size, shdr->sh_offset, shdr->sh_size, error_callback, data, &debugaltlink_view)) goto fail; debugaltlink_view_valid = 1; debugaltlink_data = (const char *)debugaltlink_view.view.data; debugaltlink_name = debugaltlink_data; debugaltlink_name_len = strnlen(debugaltlink_data, shdr->sh_size); if (debugaltlink_name_len < shdr->sh_size) { debugaltlink_name_len += 1; debugaltlink_buildid_data = debugaltlink_data + debugaltlink_name_len; debugaltlink_buildid_size = shdr->sh_size - debugaltlink_name_len; } } if (!gnu_debugdata_view_valid && strcmp(name, ".gnu_debugdata") == 0) { if (!elf_get_view(state, descriptor, memory, memory_size, shdr->sh_offset, shdr->sh_size, error_callback, data, &gnu_debugdata_view)) goto fail; gnu_debugdata_size = shdr->sh_size; gnu_debugdata_view_valid = 1; } if (ehdr.e_machine == EM_PPC64 && (ehdr.e_flags & EF_PPC64_ABI) < 2 && shdr->sh_type == SHT_PROGBITS && strcmp(name, ".opd") == 0) { if (!elf_get_view(state, descriptor, memory, memory_size, shdr->sh_offset, shdr->sh_size, error_callback, data, &opd_data.view)) goto fail; opd = &opd_data; opd->addr = shdr->sh_addr; opd->data = (const char *)opd_data.view.view.data; opd->size = shdr->sh_size; } } if (symtab_shndx == 0) symtab_shndx = dynsym_shndx; if (symtab_shndx != 0 && !debuginfo) { const b_elf_shdr *symtab_shdr; unsigned int strtab_shndx; const b_elf_shdr *strtab_shdr; struct elf_syminfo_data *sdata; symtab_shdr = &shdrs[symtab_shndx - 1]; strtab_shndx = symtab_shdr->sh_link; if (strtab_shndx >= shnum) { error_callback(data, "ELF symbol table strtab link out of range", 0); goto fail; } strtab_shdr = &shdrs[strtab_shndx - 1]; if (!elf_get_view(state, descriptor, memory, memory_size, symtab_shdr->sh_offset, symtab_shdr->sh_size, error_callback, data, &symtab_view)) goto fail; symtab_view_valid = 1; if (!elf_get_view(state, descriptor, memory, memory_size, strtab_shdr->sh_offset, strtab_shdr->sh_size, error_callback, data, &strtab_view)) goto fail; strtab_view_valid = 1; sdata = ((struct elf_syminfo_data *)backtrace_alloc(state, sizeof *sdata, error_callback, data)); if (sdata == NULL) goto fail; if (!elf_initialize_syminfo(state, base_address, symtab_view.view.data, symtab_shdr->sh_size, strtab_view.view.data, strtab_shdr->sh_size, error_callback, data, sdata, opd)) { backtrace_free(state, sdata, sizeof *sdata, error_callback, data); goto fail; } elf_release_view(state, &symtab_view, error_callback, data); symtab_view_valid = 0; strtab_view_valid = 0; *found_sym = 1; elf_add_syminfo_data(state, sdata); } elf_release_view(state, &shdrs_view, error_callback, data); shdrs_view_valid = 0; elf_release_view(state, &names_view, error_callback, data); names_view_valid = 0; if (buildid_data != NULL) { int d; d = elf_open_debugfile_by_buildid(state, buildid_data, buildid_size, error_callback, data); if (d >= 0) { int ret; elf_release_view(state, &buildid_view, error_callback, data); if (debuglink_view_valid) elf_release_view(state, &debuglink_view, error_callback, data); if (debugaltlink_view_valid) elf_release_view(state, &debugaltlink_view, error_callback, data); ret = elf_add(state, "", d, NULL, 0, base_address, error_callback, data, fileline_fn, found_sym, found_dwarf, NULL, 0, 1, NULL, 0); if (ret < 0) backtrace_close(d, error_callback, data); else if (descriptor >= 0) backtrace_close(descriptor, error_callback, data); return ret; } } if (buildid_view_valid) { elf_release_view(state, &buildid_view, error_callback, data); buildid_view_valid = 0; } if (opd) { elf_release_view(state, &opd->view, error_callback, data); opd = NULL; } if (debuglink_name != NULL) { int d; d = elf_open_debugfile_by_debuglink(state, filename, debuglink_name, debuglink_crc, error_callback, data); if (d >= 0) { int ret; elf_release_view(state, &debuglink_view, error_callback, data); if (debugaltlink_view_valid) elf_release_view(state, &debugaltlink_view, error_callback, data); ret = elf_add(state, "", d, NULL, 0, base_address, error_callback, data, fileline_fn, found_sym, found_dwarf, NULL, 0, 1, NULL, 0); if (ret < 0) backtrace_close(d, error_callback, data); else if (descriptor >= 0) backtrace_close(descriptor, error_callback, data); return ret; } } if (debuglink_view_valid) { elf_release_view(state, &debuglink_view, error_callback, data); debuglink_view_valid = 0; } struct dwarf_data *fileline_altlink = NULL; if (debugaltlink_name != NULL) { int d; d = elf_open_debugfile_by_debuglink(state, filename, debugaltlink_name, 0, error_callback, data); if (d >= 0) { int ret; ret = elf_add(state, filename, d, NULL, 0, base_address, error_callback, data, fileline_fn, found_sym, found_dwarf, &fileline_altlink, 0, 1, debugaltlink_buildid_data, debugaltlink_buildid_size); elf_release_view(state, &debugaltlink_view, error_callback, data); debugaltlink_view_valid = 0; if (ret < 0) { backtrace_close(d, error_callback, data); return ret; } } } if (debugaltlink_view_valid) { elf_release_view(state, &debugaltlink_view, error_callback, data); debugaltlink_view_valid = 0; } if (gnu_debugdata_view_valid) { int ret; ret = elf_uncompress_lzma( state, ((const unsigned char *)gnu_debugdata_view.view.data), gnu_debugdata_size, error_callback, data, &gnu_debugdata_uncompressed, &gnu_debugdata_uncompressed_size); elf_release_view(state, &gnu_debugdata_view, error_callback, data); gnu_debugdata_view_valid = 0; if (ret) { ret = elf_add(state, filename, -1, gnu_debugdata_uncompressed, gnu_debugdata_uncompressed_size, base_address, error_callback, data, fileline_fn, found_sym, found_dwarf, NULL, 0, 0, NULL, 0); if (ret >= 0 && descriptor >= 0) backtrace_close(descriptor, error_callback, data); return ret; } } min_offset = 0; max_offset = 0; debug_size = 0; for (i = 0; i < (int)DEBUG_MAX; ++i) { off_t end; if (sections[i].size != 0) { if (min_offset == 0 || sections[i].offset < min_offset) min_offset = sections[i].offset; end = sections[i].offset + sections[i].size; if (end > max_offset) max_offset = end; debug_size += sections[i].size; } if (zsections[i].size != 0) { if (min_offset == 0 || zsections[i].offset < min_offset) min_offset = zsections[i].offset; end = zsections[i].offset + zsections[i].size; if (end > max_offset) max_offset = end; debug_size += zsections[i].size; } } if (min_offset == 0 || max_offset == 0) { if (descriptor >= 0) { if (!backtrace_close(descriptor, error_callback, data)) goto fail; } return 1; } if (max_offset - min_offset < 0x20000000 || max_offset - min_offset < debug_size + 0x10000) { if (!elf_get_view(state, descriptor, memory, memory_size, min_offset, max_offset - min_offset, error_callback, data, &debug_view)) goto fail; debug_view_valid = 1; } else { memset(&split_debug_view[0], 0, sizeof split_debug_view); for (i = 0; i < (int)DEBUG_MAX; ++i) { struct debug_section_info *dsec; if (sections[i].size != 0) dsec = §ions[i]; else if (zsections[i].size != 0) dsec = &zsections[i]; else continue; if (!elf_get_view(state, descriptor, memory, memory_size, dsec->offset, dsec->size, error_callback, data, &split_debug_view[i])) goto fail; split_debug_view_valid[i] = 1; if (sections[i].size != 0) sections[i].data = ((const unsigned char *)split_debug_view[i].view.data); else zsections[i].data = ((const unsigned char *)split_debug_view[i].view.data); } } if (descriptor >= 0) { if (!backtrace_close(descriptor, error_callback, data)) goto fail; descriptor = -1; } using_debug_view = 0; if (debug_view_valid) { for (i = 0; i < (int)DEBUG_MAX; ++i) { if (sections[i].size == 0) sections[i].data = NULL; else { sections[i].data = ((const unsigned char *)debug_view.view.data + (sections[i].offset - min_offset)); ++using_debug_view; } if (zsections[i].size == 0) zsections[i].data = NULL; else zsections[i].data = ((const unsigned char *)debug_view.view.data + (zsections[i].offset - min_offset)); } } zdebug_table = NULL; for (i = 0; i < (int)DEBUG_MAX; ++i) { if (sections[i].size == 0 && zsections[i].size > 0) { unsigned char *uncompressed_data; size_t uncompressed_size; if (zdebug_table == NULL) { zdebug_table = ((uint16_t *)backtrace_alloc(state, ZDEBUG_TABLE_SIZE, error_callback, data)); if (zdebug_table == NULL) goto fail; } uncompressed_data = NULL; uncompressed_size = 0; if (!elf_uncompress_zdebug(state, zsections[i].data, zsections[i].size, zdebug_table, error_callback, data, &uncompressed_data, &uncompressed_size)) goto fail; sections[i].data = uncompressed_data; sections[i].size = uncompressed_size; sections[i].compressed = 0; if (split_debug_view_valid[i]) { elf_release_view(state, &split_debug_view[i], error_callback, data); split_debug_view_valid[i] = 0; } } } for (i = 0; i < (int)DEBUG_MAX; ++i) { unsigned char *uncompressed_data; size_t uncompressed_size; if (sections[i].size == 0 || !sections[i].compressed) continue; if (zdebug_table == NULL) { zdebug_table = ((uint16_t *)backtrace_alloc(state, ZDEBUG_TABLE_SIZE, error_callback, data)); if (zdebug_table == NULL) goto fail; } uncompressed_data = NULL; uncompressed_size = 0; if (!elf_uncompress_chdr(state, sections[i].data, sections[i].size, zdebug_table, error_callback, data, &uncompressed_data, &uncompressed_size)) goto fail; sections[i].data = uncompressed_data; sections[i].size = uncompressed_size; sections[i].compressed = 0; if (debug_view_valid) --using_debug_view; else if (split_debug_view_valid[i]) { elf_release_view(state, &split_debug_view[i], error_callback, data); split_debug_view_valid[i] = 0; } } if (zdebug_table != NULL) backtrace_free(state, zdebug_table, ZDEBUG_TABLE_SIZE, error_callback, data); if (debug_view_valid && using_debug_view == 0) { elf_release_view(state, &debug_view, error_callback, data); debug_view_valid = 0; } for (i = 0; i < (int)DEBUG_MAX; ++i) { dwarf_sections.data[i] = sections[i].data; dwarf_sections.size[i] = sections[i].size; } if (!backtrace_dwarf_add(state, base_address, &dwarf_sections, ehdr.e_ident[EI_DATA] == ELFDATA2MSB, fileline_altlink, error_callback, data, fileline_fn, fileline_entry)) goto fail; *found_dwarf = 1; return 1; fail: if (shdrs_view_valid) elf_release_view(state, &shdrs_view, error_callback, data); if (names_view_valid) elf_release_view(state, &names_view, error_callback, data); if (symtab_view_valid) elf_release_view(state, &symtab_view, error_callback, data); if (strtab_view_valid) elf_release_view(state, &strtab_view, error_callback, data); if (debuglink_view_valid) elf_release_view(state, &debuglink_view, error_callback, data); if (debugaltlink_view_valid) elf_release_view(state, &debugaltlink_view, error_callback, data); if (gnu_debugdata_view_valid) elf_release_view(state, &gnu_debugdata_view, error_callback, data); if (buildid_view_valid) elf_release_view(state, &buildid_view, error_callback, data); if (debug_view_valid) elf_release_view(state, &debug_view, error_callback, data); for (i = 0; i < (int)DEBUG_MAX; ++i) { if (split_debug_view_valid[i]) elf_release_view(state, &split_debug_view[i], error_callback, data); } if (opd) elf_release_view(state, &opd->view, error_callback, data); if (descriptor >= 0) backtrace_close(descriptor, error_callback, data); return 0; } struct phdr_data { struct backtrace_state *state; backtrace_error_callback error_callback; void *data; fileline *fileline_fn; int *found_sym; int *found_dwarf; const char *exe_filename; int exe_descriptor; }; static int #ifdef __i386__ __attribute__((__force_align_arg_pointer__)) #endif phdr_callback(struct dl_phdr_info *info, size_t size ATTRIBUTE_UNUSED, void *pdata) { struct phdr_data *pd = (struct phdr_data *)pdata; const char *filename; int descriptor; int does_not_exist; fileline elf_fileline_fn; int found_dwarf; if (info->dlpi_name == NULL || info->dlpi_name[0] == '\0') { if (pd->exe_descriptor == -1) return 0; filename = pd->exe_filename; descriptor = pd->exe_descriptor; pd->exe_descriptor = -1; } else { if (pd->exe_descriptor != -1) { backtrace_close(pd->exe_descriptor, pd->error_callback, pd->data); pd->exe_descriptor = -1; } filename = info->dlpi_name; descriptor = backtrace_open(info->dlpi_name, pd->error_callback, pd->data, &does_not_exist); if (descriptor < 0) return 0; } if (elf_add(pd->state, filename, descriptor, NULL, 0, info->dlpi_addr, pd->error_callback, pd->data, &elf_fileline_fn, pd->found_sym, &found_dwarf, NULL, 0, 0, NULL, 0)) { if (found_dwarf) { *pd->found_dwarf = 1; *pd->fileline_fn = elf_fileline_fn; } } return 0; } int backtrace_initialize(struct backtrace_state *state, const char *filename, int descriptor, backtrace_error_callback error_callback, void *data, fileline *fileline_fn) { int ret; int found_sym; int found_dwarf; fileline elf_fileline_fn = elf_nodebug; struct phdr_data pd; ret = elf_add(state, filename, descriptor, NULL, 0, 0, error_callback, data, &elf_fileline_fn, &found_sym, &found_dwarf, NULL, 1, 0, NULL, 0); if (!ret) return 0; pd.state = state; pd.error_callback = error_callback; pd.data = data; pd.fileline_fn = &elf_fileline_fn; pd.found_sym = &found_sym; pd.found_dwarf = &found_dwarf; pd.exe_filename = filename; pd.exe_descriptor = ret < 0 ? descriptor : -1; dl_iterate_phdr(phdr_callback, (void *)&pd); if (!state->threaded) { if (found_sym) state->syminfo_fn = elf_syminfo; else if (state->syminfo_fn == NULL) state->syminfo_fn = elf_nosyms; } else { if (found_sym) backtrace_atomic_store_pointer(&state->syminfo_fn, elf_syminfo); else (void)__sync_bool_compare_and_swap(&state->syminfo_fn, NULL, elf_nosyms); } if (!state->threaded) *fileline_fn = state->fileline_fn; else *fileline_fn = backtrace_atomic_load_pointer(&state->fileline_fn); if (*fileline_fn == NULL || *fileline_fn == elf_nodebug) *fileline_fn = elf_fileline_fn; return 1; } // mmapio.c: #include #include #include #include #ifndef HAVE_DECL_GETPAGESIZE extern int getpagesize(void); #endif #ifndef MAP_FAILED #define MAP_FAILED ((void *)-1) #endif int backtrace_get_view(struct backtrace_state *state ATTRIBUTE_UNUSED, int descriptor, off_t offset, uint64_t size, backtrace_error_callback error_callback, void *data, struct backtrace_view *view) { size_t pagesize; unsigned int inpage; off_t pageoff; void *map; if ((uint64_t)(size_t)size != size) { error_callback(data, "file size too large", 0); return 0; } pagesize = getpagesize(); inpage = offset % pagesize; pageoff = offset - inpage; size += inpage; size = (size + (pagesize - 1)) & ~(pagesize - 1); map = mmap(NULL, size, PROT_READ, MAP_PRIVATE, descriptor, pageoff); if (map == MAP_FAILED) { error_callback(data, "mmap", errno); return 0; } view->data = (char *)map + inpage; view->base = map; view->len = size; return 1; } void backtrace_release_view(struct backtrace_state *state ATTRIBUTE_UNUSED, struct backtrace_view *view, backtrace_error_callback error_callback, void *data) { union { const void *cv; void *v; } const_cast; const_cast.cv = view->base; if (munmap(const_cast.v, view->len) < 0) error_callback(data, "munmap", errno); } // mmap.c: #include #include #include #include #include #include #ifndef HAVE_DECL_GETPAGESIZE extern int getpagesize(void); #endif #ifndef MAP_ANONYMOUS #define MAP_ANONYMOUS MAP_ANON #endif #ifndef MAP_FAILED #define MAP_FAILED ((void *)-1) #endif struct backtrace_freelist_struct { struct backtrace_freelist_struct *next; size_t size; }; static void backtrace_free_locked(struct backtrace_state *state, void *addr, size_t size) { if (size >= sizeof(struct backtrace_freelist_struct)) { size_t c; struct backtrace_freelist_struct **ppsmall; struct backtrace_freelist_struct **pp; struct backtrace_freelist_struct *p; c = 0; ppsmall = NULL; for (pp = &state->freelist; *pp != NULL; pp = &(*pp)->next) { if (ppsmall == NULL || (*pp)->size < (*ppsmall)->size) ppsmall = pp; ++c; } if (c >= 16) { if (size <= (*ppsmall)->size) return; *ppsmall = (*ppsmall)->next; } p = (struct backtrace_freelist_struct *)addr; p->next = state->freelist; p->size = size; state->freelist = p; } } void *backtrace_alloc(struct backtrace_state *state, size_t size, backtrace_error_callback error_callback, void *data) { void *ret; int locked; struct backtrace_freelist_struct **pp; size_t pagesize; size_t asksize; void *page; ret = NULL; if (!state->threaded) locked = 1; else locked = __sync_lock_test_and_set(&state->lock_alloc, 1) == 0; if (locked) { for (pp = &state->freelist; *pp != NULL; pp = &(*pp)->next) { if ((*pp)->size >= size) { struct backtrace_freelist_struct *p; p = *pp; *pp = p->next; size = (size + 7) & ~(size_t)7; if (size < p->size) backtrace_free_locked(state, (char *)p + size, p->size - size); ret = (void *)p; break; } } if (state->threaded) __sync_lock_release(&state->lock_alloc); } if (ret == NULL) { pagesize = getpagesize(); asksize = (size + pagesize - 1) & ~(pagesize - 1); page = mmap(NULL, asksize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (page == MAP_FAILED) { if (error_callback) error_callback(data, "mmap", errno); } else { size = (size + 7) & ~(size_t)7; if (size < asksize) backtrace_free(state, (char *)page + size, asksize - size, error_callback, data); ret = page; } } return ret; } void backtrace_free(struct backtrace_state *state, void *addr, size_t size, backtrace_error_callback error_callback ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) { int locked; if (size >= 16 * 4096) { size_t pagesize; pagesize = getpagesize(); if (((uintptr_t)addr & (pagesize - 1)) == 0 && (size & (pagesize - 1)) == 0) { if (munmap(addr, size) == 0) return; } } if (!state->threaded) locked = 1; else locked = __sync_lock_test_and_set(&state->lock_alloc, 1) == 0; if (locked) { backtrace_free_locked(state, addr, size); if (state->threaded) __sync_lock_release(&state->lock_alloc); } } void *backtrace_vector_grow(struct backtrace_state *state, size_t size, backtrace_error_callback error_callback, void *data, struct backtrace_vector *vec) { void *ret; if (size > vec->alc) { size_t pagesize; size_t alc; void *base; pagesize = getpagesize(); alc = vec->size + size; if (vec->size == 0) alc = 16 * size; else if (alc < pagesize) { alc *= 2; if (alc > pagesize) alc = pagesize; } else { alc *= 2; alc = (alc + pagesize - 1) & ~(pagesize - 1); } base = backtrace_alloc(state, alc, error_callback, data); if (base == NULL) return NULL; if (vec->base != NULL) { memcpy(base, vec->base, vec->size); backtrace_free(state, vec->base, vec->size + vec->alc, error_callback, data); } vec->base = base; vec->alc = alc - vec->size; } ret = (char *)vec->base + vec->size; vec->size += size; vec->alc -= size; return ret; } void *backtrace_vector_finish(struct backtrace_state *state ATTRIBUTE_UNUSED, struct backtrace_vector *vec, backtrace_error_callback error_callback ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) { void *ret; ret = vec->base; vec->base = (char *)vec->base + vec->size; vec->size = 0; return ret; } int backtrace_vector_release(struct backtrace_state *state, struct backtrace_vector *vec, backtrace_error_callback error_callback, void *data) { size_t size; size_t alc; size_t aligned; size = vec->size; alc = vec->alc; aligned = (size + 7) & ~(size_t)7; alc -= aligned - size; backtrace_free(state, (char *)vec->base + aligned, alc, error_callback, data); vec->alc = 0; if (vec->size == 0) vec->base = NULL; return 1; }