libbacktrace/elf.c

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