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