libbacktrace/elf.c

   1 /* elf.c -- Get debug data from an ELF file for backtraces.
   2    Copyright (C) 2012-2021 Free Software Foundation, Inc.
   3    Written by Ian Lance Taylor, Google.
   4
   5 Redistribution and use in source and binary forms, with or without
   6 modification, are permitted provided that the following conditions are
   7 met:
   8
   9     (1) Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11
  12     (2) Redistributions in binary form must reproduce the above copyright
  13     notice, this list of conditions and the following disclaimer in
  14     the documentation and/or other materials provided with the
  15     distribution.
  16
  17     (3) The name of the author may not be used to
  18     endorse or promote products derived from this software without
  19     specific prior written permission.
  20
  21 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  22 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  23 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  24 DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  25 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  26 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  29 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  30 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31 POSSIBILITY OF SUCH DAMAGE.  */
  32
  33 #include "config.h"
  34
  35 #include <errno.h>
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include <sys/types.h>
  39 #include <sys/stat.h>
  40 #include <unistd.h>
  41
  42 #ifdef HAVE_DL_ITERATE_PHDR
  43 #include <link.h>
  44 #endif
  45
  46 #include "backtrace.h"
  47 #include "internal.h"
  48
  49 #ifndef S_ISLNK
  50  #ifndef S_IFLNK
  51   #define S_IFLNK 0120000
  52  #endif
  53  #ifndef S_IFMT
  54   #define S_IFMT 0170000
  55  #endif
  56  #define S_ISLNK(m) (((m) & S_IFMT) == S_IFLNK)
  57 #endif
  58
  59 #ifndef __GNUC__
  60 #define __builtin_prefetch(p, r, l)
  61 #define unlikely(x) (x)
  62 #else
  63 #define unlikely(x) __builtin_expect(!!(x), 0)
  64 #endif
  65
  66 #if !defined(HAVE_DECL_STRNLEN) || !HAVE_DECL_STRNLEN
  67
  68 /* If strnlen is not declared, provide our own version.  */
  69
  70 static size_t
  71 xstrnlen (const char *s, size_t maxlen)
  72 {
  73   size_t i;
  74
  75   for (i = 0; i < maxlen; ++i)
  76     if (s[i] == '\0')
  77       break;
  78   return i;
  79 }
  80
  81 #define strnlen xstrnlen
  82
  83 #endif
  84
  85 #ifndef HAVE_LSTAT
  86
  87 /* Dummy version of lstat for systems that don't have it.  */
  88
  89 static int
  90 xlstat (const char *path ATTRIBUTE_UNUSED, struct stat *st ATTRIBUTE_UNUSED)
  91 {
  92   return -1;
  93 }
  94
  95 #define lstat xlstat
  96
  97 #endif
  98
  99 #ifndef HAVE_READLINK
 100
 101 /* Dummy version of readlink for systems that don't have it.  */
 102
 103 static ssize_t
 104 xreadlink (const char *path ATTRIBUTE_UNUSED, char *buf ATTRIBUTE_UNUSED,
 105            size_t bufsz ATTRIBUTE_UNUSED)
 106 {
 107   return -1;
 108 }
 109
 110 #define readlink xreadlink
 111
 112 #endif
 113
 114 #ifndef HAVE_DL_ITERATE_PHDR
 115
 116 /* Dummy version of dl_iterate_phdr for systems that don't have it.  */
 117
 118 #define dl_phdr_info x_dl_phdr_info
 119 #define dl_iterate_phdr x_dl_iterate_phdr
 120
 121 struct dl_phdr_info
 122 {
 123   uintptr_t dlpi_addr;
 124   const char *dlpi_name;
 125 };
 126
 127 static int
 128 dl_iterate_phdr (int (*callback) (struct dl_phdr_info *,
 129                                   size_t, void *) ATTRIBUTE_UNUSED,
 130                  void *data ATTRIBUTE_UNUSED)
 131 {
 132   return 0;
 133 }
 134
 135 #endif /* ! defined (HAVE_DL_ITERATE_PHDR) */
 136
 137 /* The configure script must tell us whether we are 32-bit or 64-bit
 138    ELF.  We could make this code test and support either possibility,
 139    but there is no point.  This code only works for the currently
 140    running executable, which means that we know the ELF mode at
 141    configure time.  */
 142
 143 #if BACKTRACE_ELF_SIZE != 32 && BACKTRACE_ELF_SIZE != 64
 144 #error "Unknown BACKTRACE_ELF_SIZE"
 145 #endif
 146
 147 /* <link.h> might #include <elf.h> which might define our constants
 148    with slightly different values.  Undefine them to be safe.  */
 149
 150 #undef EI_NIDENT
 151 #undef EI_MAG0
 152 #undef EI_MAG1
 153 #undef EI_MAG2
 154 #undef EI_MAG3
 155 #undef EI_CLASS
 156 #undef EI_DATA
 157 #undef EI_VERSION
 158 #undef ELF_MAG0
 159 #undef ELF_MAG1
 160 #undef ELF_MAG2
 161 #undef ELF_MAG3
 162 #undef ELFCLASS32
 163 #undef ELFCLASS64
 164 #undef ELFDATA2LSB
 165 #undef ELFDATA2MSB
 166 #undef EV_CURRENT
 167 #undef ET_DYN
 168 #undef EM_PPC64
 169 #undef EF_PPC64_ABI
 170 #undef SHN_LORESERVE
 171 #undef SHN_XINDEX
 172 #undef SHN_UNDEF
 173 #undef SHT_PROGBITS
 174 #undef SHT_SYMTAB
 175 #undef SHT_STRTAB
 176 #undef SHT_DYNSYM
 177 #undef SHF_COMPRESSED
 178 #undef STT_OBJECT
 179 #undef STT_FUNC
 180 #undef NT_GNU_BUILD_ID
 181 #undef ELFCOMPRESS_ZLIB
 182
 183 /* Basic types.  */
 184
 185 typedef uint16_t b_elf_half;    /* Elf_Half.  */
 186 typedef uint32_t b_elf_word;    /* Elf_Word.  */
 187 typedef int32_t  b_elf_sword;   /* Elf_Sword.  */
 188
 189 #if BACKTRACE_ELF_SIZE == 32
 190
 191 typedef uint32_t b_elf_addr;    /* Elf_Addr.  */
 192 typedef uint32_t b_elf_off;     /* Elf_Off.  */
 193
 194 typedef uint32_t b_elf_wxword;  /* 32-bit Elf_Word, 64-bit ELF_Xword.  */
 195
 196 #else
 197
 198 typedef uint64_t b_elf_addr;    /* Elf_Addr.  */
 199 typedef uint64_t b_elf_off;     /* Elf_Off.  */
 200 typedef uint64_t b_elf_xword;   /* Elf_Xword.  */
 201 typedef int64_t  b_elf_sxword;  /* Elf_Sxword.  */
 202
 203 typedef uint64_t b_elf_wxword;  /* 32-bit Elf_Word, 64-bit ELF_Xword.  */
 204
 205 #endif
 206
 207 /* Data structures and associated constants.  */
 208
 209 #define EI_NIDENT 16
 210
 211 typedef struct {
 212   unsigned char e_ident[EI_NIDENT];     /* ELF "magic number" */
 213   b_elf_half    e_type;                 /* Identifies object file type */
 214   b_elf_half    e_machine;              /* Specifies required architecture */
 215   b_elf_word    e_version;              /* Identifies object file version */
 216   b_elf_addr    e_entry;                /* Entry point virtual address */
 217   b_elf_off     e_phoff;                /* Program header table file offset */
 218   b_elf_off     e_shoff;                /* Section header table file offset */
 219   b_elf_word    e_flags;                /* Processor-specific flags */
 220   b_elf_half    e_ehsize;               /* ELF header size in bytes */
 221   b_elf_half    e_phentsize;            /* Program header table entry size */
 222   b_elf_half    e_phnum;                /* Program header table entry count */
 223   b_elf_half    e_shentsize;            /* Section header table entry size */
 224   b_elf_half    e_shnum;                /* Section header table entry count */
 225   b_elf_half    e_shstrndx;             /* Section header string table index */
 226 } b_elf_ehdr;  /* Elf_Ehdr.  */
 227
 228 #define EI_MAG0 0
 229 #define EI_MAG1 1
 230 #define EI_MAG2 2
 231 #define EI_MAG3 3
 232 #define EI_CLASS 4
 233 #define EI_DATA 5
 234 #define EI_VERSION 6
 235
 236 #define ELFMAG0 0x7f
 237 #define ELFMAG1 'E'
 238 #define ELFMAG2 'L'
 239 #define ELFMAG3 'F'
 240
 241 #define ELFCLASS32 1
 242 #define ELFCLASS64 2
 243
 244 #define ELFDATA2LSB 1
 245 #define ELFDATA2MSB 2
 246
 247 #define EV_CURRENT 1
 248
 249 #define ET_DYN 3
 250
 251 #define EM_PPC64 21
 252 #define EF_PPC64_ABI 3
 253
 254 typedef struct {
 255   b_elf_word    sh_name;                /* Section name, index in string tbl */
 256   b_elf_word    sh_type;                /* Type of section */
 257   b_elf_wxword  sh_flags;               /* Miscellaneous section attributes */
 258   b_elf_addr    sh_addr;                /* Section virtual addr at execution */
 259   b_elf_off     sh_offset;              /* Section file offset */
 260   b_elf_wxword  sh_size;                /* Size of section in bytes */
 261   b_elf_word    sh_link;                /* Index of another section */
 262   b_elf_word    sh_info;                /* Additional section information */
 263   b_elf_wxword  sh_addralign;           /* Section alignment */
 264   b_elf_wxword  sh_entsize;             /* Entry size if section holds table */
 265 } b_elf_shdr;  /* Elf_Shdr.  */
 266
 267 #define SHN_UNDEF       0x0000          /* Undefined section */
 268 #define SHN_LORESERVE   0xFF00          /* Begin range of reserved indices */
 269 #define SHN_XINDEX      0xFFFF          /* Section index is held elsewhere */
 270
 271 #define SHT_PROGBITS 1
 272 #define SHT_SYMTAB 2
 273 #define SHT_STRTAB 3
 274 #define SHT_DYNSYM 11
 275
 276 #define SHF_COMPRESSED 0x800
 277
 278 #if BACKTRACE_ELF_SIZE == 32
 279
 280 typedef struct
 281 {
 282   b_elf_word    st_name;                /* Symbol name, index in string tbl */
 283   b_elf_addr    st_value;               /* Symbol value */
 284   b_elf_word    st_size;                /* Symbol size */
 285   unsigned char st_info;                /* Symbol binding and type */
 286   unsigned char st_other;               /* Visibility and other data */
 287   b_elf_half    st_shndx;               /* Symbol section index */
 288 } b_elf_sym;  /* Elf_Sym.  */
 289
 290 #else /* BACKTRACE_ELF_SIZE != 32 */
 291
 292 typedef struct
 293 {
 294   b_elf_word    st_name;                /* Symbol name, index in string tbl */
 295   unsigned char st_info;                /* Symbol binding and type */
 296   unsigned char st_other;               /* Visibility and other data */
 297   b_elf_half    st_shndx;               /* Symbol section index */
 298   b_elf_addr    st_value;               /* Symbol value */
 299   b_elf_xword   st_size;                /* Symbol size */
 300 } b_elf_sym;  /* Elf_Sym.  */
 301
 302 #endif /* BACKTRACE_ELF_SIZE != 32 */
 303
 304 #define STT_OBJECT 1
 305 #define STT_FUNC 2
 306
 307 typedef struct
 308 {
 309   uint32_t namesz;
 310   uint32_t descsz;
 311   uint32_t type;
 312   char name[1];
 313 } b_elf_note;
 314
 315 #define NT_GNU_BUILD_ID 3
 316
 317 #if BACKTRACE_ELF_SIZE == 32
 318
 319 typedef struct
 320 {
 321   b_elf_word    ch_type;                /* Compresstion algorithm */
 322   b_elf_word    ch_size;                /* Uncompressed size */
 323   b_elf_word    ch_addralign;           /* Alignment for uncompressed data */
 324 } b_elf_chdr;  /* Elf_Chdr */
 325
 326 #else /* BACKTRACE_ELF_SIZE != 32 */
 327
 328 typedef struct
 329 {
 330   b_elf_word    ch_type;                /* Compression algorithm */
 331   b_elf_word    ch_reserved;            /* Reserved */
 332   b_elf_xword   ch_size;                /* Uncompressed size */
 333   b_elf_xword   ch_addralign;           /* Alignment for uncompressed data */
 334 } b_elf_chdr;  /* Elf_Chdr */
 335
 336 #endif /* BACKTRACE_ELF_SIZE != 32 */
 337
 338 #define ELFCOMPRESS_ZLIB 1
 339
 340 /* Names of sections, indexed by enum dwarf_section in internal.h.  */
 341
 342 static const char * const dwarf_section_names[DEBUG_MAX] =
 343 {
 344   ".debug_info",
 345   ".debug_line",
 346   ".debug_abbrev",
 347   ".debug_ranges",
 348   ".debug_str",
 349   ".debug_addr",
 350   ".debug_str_offsets",
 351   ".debug_line_str",
 352   ".debug_rnglists"
 353 };
 354
 355 /* Information we gather for the sections we care about.  */
 356
 357 struct debug_section_info
 358 {
 359   /* Section file offset.  */
 360   off_t offset;
 361   /* Section size.  */
 362   size_t size;
 363   /* Section contents, after read from file.  */
 364   const unsigned char *data;
 365   /* Whether the SHF_COMPRESSED flag is set for the section.  */
 366   int compressed;
 367 };
 368
 369 /* Information we keep for an ELF symbol.  */
 370
 371 struct elf_symbol
 372 {
 373   /* The name of the symbol.  */
 374   const char *name;
 375   /* The address of the symbol.  */
 376   uintptr_t address;
 377   /* The size of the symbol.  */
 378   size_t size;
 379 };
 380
 381 /* Information to pass to elf_syminfo.  */
 382
 383 struct elf_syminfo_data
 384 {
 385   /* Symbols for the next module.  */
 386   struct elf_syminfo_data *next;
 387   /* The ELF symbols, sorted by address.  */
 388   struct elf_symbol *symbols;
 389   /* The number of symbols.  */
 390   size_t count;
 391 };
 392
 393 /* A view that works for either a file or memory.  */
 394
 395 struct elf_view
 396 {
 397   struct backtrace_view view;
 398   int release; /* If non-zero, must call backtrace_release_view.  */
 399 };
 400
 401 /* Information about PowerPC64 ELFv1 .opd section.  */
 402
 403 struct elf_ppc64_opd_data
 404 {
 405   /* Address of the .opd section.  */
 406   b_elf_addr addr;
 407   /* Section data.  */
 408   const char *data;
 409   /* Size of the .opd section.  */
 410   size_t size;
 411   /* Corresponding section view.  */
 412   struct elf_view view;
 413 };
 414
 415 /* Create a view of SIZE bytes from DESCRIPTOR/MEMORY at OFFSET.  */
 416
 417 static int
 418 elf_get_view (struct backtrace_state *state, int descriptor,
 419               const unsigned char *memory, size_t memory_size, off_t offset,
 420               uint64_t size, backtrace_error_callback error_callback,
 421               void *data, struct elf_view *view)
 422 {
 423   if (memory == NULL)
 424     {
 425       view->release = 1;
 426       return backtrace_get_view (state, descriptor, offset, size,
 427                                  error_callback, data, &view->view);
 428     }
 429   else
 430     {
 431       if ((uint64_t) offset + size > (uint64_t) memory_size)
 432         {
 433           error_callback (data, "out of range for in-memory file", 0);
 434           return 0;
 435         }
 436       view->view.data = (const void *) (memory + offset);
 437       view->view.base = NULL;
 438       view->view.len = size;
 439       view->release = 0;
 440       return 1;
 441     }
 442 }
 443
 444 /* Release a view read by elf_get_view.  */
 445
 446 static void
 447 elf_release_view (struct backtrace_state *state, struct elf_view *view,
 448                   backtrace_error_callback error_callback, void *data)
 449 {
 450   if (view->release)
 451     backtrace_release_view (state, &view->view, error_callback, data);
 452 }
 453
 454 /* Compute the CRC-32 of BUF/LEN.  This uses the CRC used for
 455    .gnu_debuglink files.  */
 456
 457 static uint32_t
 458 elf_crc32 (uint32_t crc, const unsigned char *buf, size_t len)
 459 {
 460   static const uint32_t crc32_table[256] =
 461     {
 462       0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
 463       0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
 464       0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
 465       0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
 466       0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
 467       0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
 468       0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
 469       0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
 470       0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
 471       0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
 472       0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
 473       0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 474       0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
 475       0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
 476       0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
 477       0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 478       0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
 479       0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
 480       0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
 481       0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 482       0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
 483       0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
 484       0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
 485       0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 486       0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
 487       0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
 488       0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
 489       0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 490       0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
 491       0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
 492       0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
 493       0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 494       0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
 495       0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
 496       0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
 497       0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 498       0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
 499       0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
 500       0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
 501       0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 502       0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
 503       0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 504       0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
 505       0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 506       0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
 507       0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
 508       0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
 509       0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 510       0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
 511       0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
 512       0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
 513       0x2d02ef8d
 514     };
 515   const unsigned char *end;
 516
 517   crc = ~crc;
 518   for (end = buf + len; buf < end; ++ buf)
 519     crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8);
 520   return ~crc;
 521 }
 522
 523 /* Return the CRC-32 of the entire file open at DESCRIPTOR.  */
 524
 525 static uint32_t
 526 elf_crc32_file (struct backtrace_state *state, int descriptor,
 527                 backtrace_error_callback error_callback, void *data)
 528 {
 529   struct stat st;
 530   struct backtrace_view file_view;
 531   uint32_t ret;
 532
 533   if (fstat (descriptor, &st) < 0)
 534     {
 535       error_callback (data, "fstat", errno);
 536       return 0;
 537     }
 538
 539   if (!backtrace_get_view (state, descriptor, 0, st.st_size, error_callback,
 540                            data, &file_view))
 541     return 0;
 542
 543   ret = elf_crc32 (0, (const unsigned char *) file_view.data, st.st_size);
 544
 545   backtrace_release_view (state, &file_view, error_callback, data);
 546
 547   return ret;
 548 }
 549
 550 /* A dummy callback function used when we can't find a symbol
 551    table.  */
 552
 553 static void
 554 elf_nosyms (struct backtrace_state *state ATTRIBUTE_UNUSED,
 555             uintptr_t addr ATTRIBUTE_UNUSED,
 556             backtrace_syminfo_callback callback ATTRIBUTE_UNUSED,
 557             backtrace_error_callback error_callback, void *data)
 558 {
 559   error_callback (data, "no symbol table in ELF executable", -1);
 560 }
 561
 562 /* A callback function used when we can't find any debug info.  */
 563
 564 static int
 565 elf_nodebug (struct backtrace_state *state, uintptr_t pc,
 566              backtrace_full_callback callback,
 567              backtrace_error_callback error_callback, void *data)
 568 {
 569   if (state->syminfo_fn != NULL && state->syminfo_fn != elf_nosyms)
 570     {
 571       struct backtrace_call_full bdata;
 572
 573       /* Fetch symbol information so that we can least get the
 574          function name.  */
 575
 576       bdata.full_callback = callback;
 577       bdata.full_error_callback = error_callback;
 578       bdata.full_data = data;
 579       bdata.ret = 0;
 580       state->syminfo_fn (state, pc, backtrace_syminfo_to_full_callback,
 581                          backtrace_syminfo_to_full_error_callback, &bdata);
 582       return bdata.ret;
 583     }
 584
 585   error_callback (data, "no debug info in ELF executable", -1);
 586   return 0;
 587 }
 588
 589 /* Compare struct elf_symbol for qsort.  */
 590
 591 static int
 592 elf_symbol_compare (const void *v1, const void *v2)
 593 {
 594   const struct elf_symbol *e1 = (const struct elf_symbol *) v1;
 595   const struct elf_symbol *e2 = (const struct elf_symbol *) v2;
 596
 597   if (e1->address < e2->address)
 598     return -1;
 599   else if (e1->address > e2->address)
 600     return 1;
 601   else
 602     return 0;
 603 }
 604
 605 /* Compare an ADDR against an elf_symbol for bsearch.  We allocate one
 606    extra entry in the array so that this can look safely at the next
 607    entry.  */
 608
 609 static int
 610 elf_symbol_search (const void *vkey, const void *ventry)
 611 {
 612   const uintptr_t *key = (const uintptr_t *) vkey;
 613   const struct elf_symbol *entry = (const struct elf_symbol *) ventry;
 614   uintptr_t addr;
 615
 616   addr = *key;
 617   if (addr < entry->address)
 618     return -1;
 619   else if (addr >= entry->address + entry->size)
 620     return 1;
 621   else
 622     return 0;
 623 }
 624
 625 /* Initialize the symbol table info for elf_syminfo.  */
 626
 627 static int
 628 elf_initialize_syminfo (struct backtrace_state *state,
 629                         uintptr_t base_address,
 630                         const unsigned char *symtab_data, size_t symtab_size,
 631                         const unsigned char *strtab, size_t strtab_size,
 632                         backtrace_error_callback error_callback,
 633                         void *data, struct elf_syminfo_data *sdata,
 634                         struct elf_ppc64_opd_data *opd)
 635 {
 636   size_t sym_count;
 637   const b_elf_sym *sym;
 638   size_t elf_symbol_count;
 639   size_t elf_symbol_size;
 640   struct elf_symbol *elf_symbols;
 641   size_t i;
 642   unsigned int j;
 643
 644   sym_count = symtab_size / sizeof (b_elf_sym);
 645
 646   /* We only care about function symbols.  Count them.  */
 647   sym = (const b_elf_sym *) symtab_data;
 648   elf_symbol_count = 0;
 649   for (i = 0; i < sym_count; ++i, ++sym)
 650     {
 651       int info;
 652
 653       info = sym->st_info & 0xf;
 654       if ((info == STT_FUNC || info == STT_OBJECT)
 655           && sym->st_shndx != SHN_UNDEF)
 656         ++elf_symbol_count;
 657     }
 658
 659   elf_symbol_size = elf_symbol_count * sizeof (struct elf_symbol);
 660   elf_symbols = ((struct elf_symbol *)
 661                  backtrace_alloc (state, elf_symbol_size, error_callback,
 662                                   data));
 663   if (elf_symbols == NULL)
 664     return 0;
 665
 666   sym = (const b_elf_sym *) symtab_data;
 667   j = 0;
 668   for (i = 0; i < sym_count; ++i, ++sym)
 669     {
 670       int info;
 671
 672       info = sym->st_info & 0xf;
 673       if (info != STT_FUNC && info != STT_OBJECT)
 674         continue;
 675       if (sym->st_shndx == SHN_UNDEF)
 676         continue;
 677       if (sym->st_name >= strtab_size)
 678         {
 679           error_callback (data, "symbol string index out of range", 0);
 680           backtrace_free (state, elf_symbols, elf_symbol_size, error_callback,
 681                           data);
 682           return 0;
 683         }
 684       elf_symbols[j].name = (const char *) strtab + sym->st_name;
 685       /* Special case PowerPC64 ELFv1 symbols in .opd section, if the symbol
 686          is a function descriptor, read the actual code address from the
 687          descriptor.  */
 688       if (opd
 689           && sym->st_value >= opd->addr
 690           && sym->st_value < opd->addr + opd->size)
 691         elf_symbols[j].address
 692           = *(const b_elf_addr *) (opd->data + (sym->st_value - opd->addr));
 693       else
 694         elf_symbols[j].address = sym->st_value;
 695       elf_symbols[j].address += base_address;
 696       elf_symbols[j].size = sym->st_size;
 697       ++j;
 698     }
 699
 700   backtrace_qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
 701                    elf_symbol_compare);
 702
 703   sdata->next = NULL;
 704   sdata->symbols = elf_symbols;
 705   sdata->count = elf_symbol_count;
 706
 707   return 1;
 708 }
 709
 710 /* Add EDATA to the list in STATE.  */
 711
 712 static void
 713 elf_add_syminfo_data (struct backtrace_state *state,
 714                       struct elf_syminfo_data *edata)
 715 {
 716   if (!state->threaded)
 717     {
 718       struct elf_syminfo_data **pp;
 719
 720       for (pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
 721            *pp != NULL;
 722            pp = &(*pp)->next)
 723         ;
 724       *pp = edata;
 725     }
 726   else
 727     {
 728       while (1)
 729         {
 730           struct elf_syminfo_data **pp;
 731
 732           pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
 733
 734           while (1)
 735             {
 736               struct elf_syminfo_data *p;
 737
 738               p = backtrace_atomic_load_pointer (pp);
 739
 740               if (p == NULL)
 741                 break;
 742
 743               pp = &p->next;
 744             }
 745
 746           if (__sync_bool_compare_and_swap (pp, NULL, edata))
 747             break;
 748         }
 749     }
 750 }
 751
 752 /* Return the symbol name and value for an ADDR.  */
 753
 754 static void
 755 elf_syminfo (struct backtrace_state *state, uintptr_t addr,
 756              backtrace_syminfo_callback callback,
 757              backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
 758              void *data)
 759 {
 760   struct elf_syminfo_data *edata;
 761   struct elf_symbol *sym = NULL;
 762
 763   if (!state->threaded)
 764     {
 765       for (edata = (struct elf_syminfo_data *) state->syminfo_data;
 766            edata != NULL;
 767            edata = edata->next)
 768         {
 769           sym = ((struct elf_symbol *)
 770                  bsearch (&addr, edata->symbols, edata->count,
 771                           sizeof (struct elf_symbol), elf_symbol_search));
 772           if (sym != NULL)
 773             break;
 774         }
 775     }
 776   else
 777     {
 778       struct elf_syminfo_data **pp;
 779
 780       pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
 781       while (1)
 782         {
 783           edata = backtrace_atomic_load_pointer (pp);
 784           if (edata == NULL)
 785             break;
 786
 787           sym = ((struct elf_symbol *)
 788                  bsearch (&addr, edata->symbols, edata->count,
 789                           sizeof (struct elf_symbol), elf_symbol_search));
 790           if (sym != NULL)
 791             break;
 792
 793           pp = &edata->next;
 794         }
 795     }
 796
 797   if (sym == NULL)
 798     callback (data, addr, NULL, 0, 0);
 799   else
 800     callback (data, addr, sym->name, sym->address, sym->size);
 801 }
 802
 803 /* Return whether FILENAME is a symlink.  */
 804
 805 static int
 806 elf_is_symlink (const char *filename)
 807 {
 808   struct stat st;
 809
 810   if (lstat (filename, &st) < 0)
 811     return 0;
 812   return S_ISLNK (st.st_mode);
 813 }
 814
 815 /* Return the results of reading the symlink FILENAME in a buffer
 816    allocated by backtrace_alloc.  Return the length of the buffer in
 817    *LEN.  */
 818
 819 static char *
 820 elf_readlink (struct backtrace_state *state, const char *filename,
 821               backtrace_error_callback error_callback, void *data,
 822               size_t *plen)
 823 {
 824   size_t len;
 825   char *buf;
 826
 827   len = 128;
 828   while (1)
 829     {
 830       ssize_t rl;
 831
 832       buf = backtrace_alloc (state, len, error_callback, data);
 833       if (buf == NULL)
 834         return NULL;
 835       rl = readlink (filename, buf, len);
 836       if (rl < 0)
 837         {
 838           backtrace_free (state, buf, len, error_callback, data);
 839           return NULL;
 840         }
 841       if ((size_t) rl < len - 1)
 842         {
 843           buf[rl] = '\0';
 844           *plen = len;
 845           return buf;
 846         }
 847       backtrace_free (state, buf, len, error_callback, data);
 848       len *= 2;
 849     }
 850 }
 851
 852 #define SYSTEM_BUILD_ID_DIR "/usr/lib/debug/.build-id/"
 853
 854 /* Open a separate debug info file, using the build ID to find it.
 855    Returns an open file descriptor, or -1.
 856
 857    The GDB manual says that the only place gdb looks for a debug file
 858    when the build ID is known is in /usr/lib/debug/.build-id.  */
 859
 860 static int
 861 elf_open_debugfile_by_buildid (struct backtrace_state *state,
 862                                const char *buildid_data, size_t buildid_size,
 863                                backtrace_error_callback error_callback,
 864                                void *data)
 865 {
 866   const char * const prefix = SYSTEM_BUILD_ID_DIR;
 867   const size_t prefix_len = strlen (prefix);
 868   const char * const suffix = ".debug";
 869   const size_t suffix_len = strlen (suffix);
 870   size_t len;
 871   char *bd_filename;
 872   char *t;
 873   size_t i;
 874   int ret;
 875   int does_not_exist;
 876
 877   len = prefix_len + buildid_size * 2 + suffix_len + 2;
 878   bd_filename = backtrace_alloc (state, len, error_callback, data);
 879   if (bd_filename == NULL)
 880     return -1;
 881
 882   t = bd_filename;
 883   memcpy (t, prefix, prefix_len);
 884   t += prefix_len;
 885   for (i = 0; i < buildid_size; i++)
 886     {
 887       unsigned char b;
 888       unsigned char nib;
 889
 890       b = (unsigned char) buildid_data[i];
 891       nib = (b & 0xf0) >> 4;
 892       *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
 893       nib = b & 0x0f;
 894       *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
 895       if (i == 0)
 896         *t++ = '/';
 897     }
 898   memcpy (t, suffix, suffix_len);
 899   t[suffix_len] = '\0';
 900
 901   ret = backtrace_open (bd_filename, error_callback, data, &does_not_exist);
 902
 903   backtrace_free (state, bd_filename, len, error_callback, data);
 904
 905   /* gdb checks that the debuginfo file has the same build ID note.
 906      That seems kind of pointless to me--why would it have the right
 907      name but not the right build ID?--so skipping the check.  */
 908
 909   return ret;
 910 }
 911
 912 /* Try to open a file whose name is PREFIX (length PREFIX_LEN)
 913    concatenated with PREFIX2 (length PREFIX2_LEN) concatenated with
 914    DEBUGLINK_NAME.  Returns an open file descriptor, or -1.  */
 915
 916 static int
 917 elf_try_debugfile (struct backtrace_state *state, const char *prefix,
 918                    size_t prefix_len, const char *prefix2, size_t prefix2_len,
 919                    const char *debuglink_name,
 920                    backtrace_error_callback error_callback, void *data)
 921 {
 922   size_t debuglink_len;
 923   size_t try_len;
 924   char *try;
 925   int does_not_exist;
 926   int ret;
 927
 928   debuglink_len = strlen (debuglink_name);
 929   try_len = prefix_len + prefix2_len + debuglink_len + 1;
 930   try = backtrace_alloc (state, try_len, error_callback, data);
 931   if (try == NULL)
 932     return -1;
 933
 934   memcpy (try, prefix, prefix_len);
 935   memcpy (try + prefix_len, prefix2, prefix2_len);
 936   memcpy (try + prefix_len + prefix2_len, debuglink_name, debuglink_len);
 937   try[prefix_len + prefix2_len + debuglink_len] = '\0';
 938
 939   ret = backtrace_open (try, error_callback, data, &does_not_exist);
 940
 941   backtrace_free (state, try, try_len, error_callback, data);
 942
 943   return ret;
 944 }
 945
 946 /* Find a separate debug info file, using the debuglink section data
 947    to find it.  Returns an open file descriptor, or -1.  */
 948
 949 static int
 950 elf_find_debugfile_by_debuglink (struct backtrace_state *state,
 951                                  const char *filename,
 952                                  const char *debuglink_name,
 953                                  backtrace_error_callback error_callback,
 954                                  void *data)
 955 {
 956   int ret;
 957   char *alc;
 958   size_t alc_len;
 959   const char *slash;
 960   int ddescriptor;
 961   const char *prefix;
 962   size_t prefix_len;
 963
 964   /* Resolve symlinks in FILENAME.  Since FILENAME is fairly likely to
 965      be /proc/self/exe, symlinks are common.  We don't try to resolve
 966      the whole path name, just the base name.  */
 967   ret = -1;
 968   alc = NULL;
 969   alc_len = 0;
 970   while (elf_is_symlink (filename))
 971     {
 972       char *new_buf;
 973       size_t new_len;
 974
 975       new_buf = elf_readlink (state, filename, error_callback, data, &new_len);
 976       if (new_buf == NULL)
 977         break;
 978
 979       if (new_buf[0] == '/')
 980         filename = new_buf;
 981       else
 982         {
 983           slash = strrchr (filename, '/');
 984           if (slash == NULL)
 985             filename = new_buf;
 986           else
 987             {
 988               size_t clen;
 989               char *c;
 990
 991               slash++;
 992               clen = slash - filename + strlen (new_buf) + 1;
 993               c = backtrace_alloc (state, clen, error_callback, data);
 994               if (c == NULL)
 995                 goto done;
 996
 997               memcpy (c, filename, slash - filename);
 998               memcpy (c + (slash - filename), new_buf, strlen (new_buf));
 999               c[slash - filename + strlen (new_buf)] = '\0';
1000               backtrace_free (state, new_buf, new_len, error_callback, data);
1001               filename = c;
1002               new_buf = c;
1003               new_len = clen;
1004             }
1005         }
1006
1007       if (alc != NULL)
1008         backtrace_free (state, alc, alc_len, error_callback, data);
1009       alc = new_buf;
1010       alc_len = new_len;
1011     }
1012
1013   /* Look for DEBUGLINK_NAME in the same directory as FILENAME.  */
1014
1015   slash = strrchr (filename, '/');
1016   if (slash == NULL)
1017     {
1018       prefix = "";
1019       prefix_len = 0;
1020     }
1021   else
1022     {
1023       slash++;
1024       prefix = filename;
1025       prefix_len = slash - filename;
1026     }
1027
1028   ddescriptor = elf_try_debugfile (state, prefix, prefix_len, "", 0,
1029                                    debuglink_name, error_callback, data);
1030   if (ddescriptor >= 0)
1031     {
1032       ret = ddescriptor;
1033       goto done;
1034     }
1035
1036   /* Look for DEBUGLINK_NAME in a .debug subdirectory of FILENAME.  */
1037
1038   ddescriptor = elf_try_debugfile (state, prefix, prefix_len, ".debug/",
1039                                    strlen (".debug/"), debuglink_name,
1040                                    error_callback, data);
1041   if (ddescriptor >= 0)
1042     {
1043       ret = ddescriptor;
1044       goto done;
1045     }
1046
1047   /* Look for DEBUGLINK_NAME in /usr/lib/debug.  */
1048
1049   ddescriptor = elf_try_debugfile (state, "/usr/lib/debug/",
1050                                    strlen ("/usr/lib/debug/"), prefix,
1051                                    prefix_len, debuglink_name,
1052                                    error_callback, data);
1053   if (ddescriptor >= 0)
1054     ret = ddescriptor;
1055
1056  done:
1057   if (alc != NULL && alc_len > 0)
1058     backtrace_free (state, alc, alc_len, error_callback, data);
1059   return ret;
1060 }
1061
1062 /* Open a separate debug info file, using the debuglink section data
1063    to find it.  Returns an open file descriptor, or -1.  */
1064
1065 static int
1066 elf_open_debugfile_by_debuglink (struct backtrace_state *state,
1067                                  const char *filename,
1068                                  const char *debuglink_name,
1069                                  uint32_t debuglink_crc,
1070                                  backtrace_error_callback error_callback,
1071                                  void *data)
1072 {
1073   int ddescriptor;
1074
1075   ddescriptor = elf_find_debugfile_by_debuglink (state, filename,
1076                                                  debuglink_name,
1077                                                  error_callback, data);
1078   if (ddescriptor < 0)
1079     return -1;
1080
1081   if (debuglink_crc != 0)
1082     {
1083       uint32_t got_crc;
1084
1085       got_crc = elf_crc32_file (state, ddescriptor, error_callback, data);
1086       if (got_crc != debuglink_crc)
1087         {
1088           backtrace_close (ddescriptor, error_callback, data);
1089           return -1;
1090         }
1091     }
1092
1093   return ddescriptor;
1094 }
1095
1096 /* A function useful for setting a breakpoint for an inflation failure
1097    when this code is compiled with -g.  */
1098
1099 static void
1100 elf_uncompress_failed(void)
1101 {
1102 }
1103
1104 /* *PVAL is the current value being read from the stream, and *PBITS
1105    is the number of valid bits.  Ensure that *PVAL holds at least 15
1106    bits by reading additional bits from *PPIN, up to PINEND, as
1107    needed.  Updates *PPIN, *PVAL and *PBITS.  Returns 1 on success, 0
1108    on error.  */
1109
1110 static int
1111 elf_zlib_fetch (const unsigned char **ppin, const unsigned char *pinend,
1112                 uint64_t *pval, unsigned int *pbits)
1113 {
1114   unsigned int bits;
1115   const unsigned char *pin;
1116   uint64_t val;
1117   uint32_t next;
1118
1119   bits = *pbits;
1120   if (bits >= 15)
1121     return 1;
1122   pin = *ppin;
1123   val = *pval;
1124
1125   if (unlikely (pinend - pin < 4))
1126     {
1127       elf_uncompress_failed ();
1128       return 0;
1129     }
1130
1131 #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) \
1132     && defined(__ORDER_BIG_ENDIAN__) \
1133     && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ \
1134         || __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1135   /* We've ensured that PIN is aligned.  */
1136   next = *(const uint32_t *)pin;
1137
1138 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
1139   next = __builtin_bswap32 (next);
1140 #endif
1141 #else
1142   next = pin[0] | (pin[1] << 8) | (pin[2] << 16) | (pin[3] << 24);
1143 #endif
1144
1145   val |= (uint64_t)next << bits;
1146   bits += 32;
1147   pin += 4;
1148
1149   /* We will need the next four bytes soon.  */
1150   __builtin_prefetch (pin, 0, 0);
1151
1152   *ppin = pin;
1153   *pval = val;
1154   *pbits = bits;
1155   return 1;
1156 }
1157
1158 /* Huffman code tables, like the rest of the zlib format, are defined
1159    by RFC 1951.  We store a Huffman code table as a series of tables
1160    stored sequentially in memory.  Each entry in a table is 16 bits.
1161    The first, main, table has 256 entries.  It is followed by a set of
1162    secondary tables of length 2 to 128 entries.  The maximum length of
1163    a code sequence in the deflate format is 15 bits, so that is all we
1164    need.  Each secondary table has an index, which is the offset of
1165    the table in the overall memory storage.
1166
1167    The deflate format says that all codes of a given bit length are
1168    lexicographically consecutive.  Perhaps we could have 130 values
1169    that require a 15-bit code, perhaps requiring three secondary
1170    tables of size 128.  I don't know if this is actually possible, but
1171    it suggests that the maximum size required for secondary tables is
1172    3 * 128 + 3 * 64 ... == 768.  The zlib enough program reports 660
1173    as the maximum.  We permit 768, since in addition to the 256 for
1174    the primary table, with two bytes per entry, and with the two
1175    tables we need, that gives us a page.
1176
1177    A single table entry needs to store a value or (for the main table
1178    only) the index and size of a secondary table.  Values range from 0
1179    to 285, inclusive.  Secondary table indexes, per above, range from
1180    0 to 510.  For a value we need to store the number of bits we need
1181    to determine that value (one value may appear multiple times in the
1182    table), which is 1 to 8.  For a secondary table we need to store
1183    the number of bits used to index into the table, which is 1 to 7.
1184    And of course we need 1 bit to decide whether we have a value or a
1185    secondary table index.  So each entry needs 9 bits for value/table
1186    index, 3 bits for size, 1 bit what it is.  For simplicity we use 16
1187    bits per entry.  */
1188
1189 /* Number of entries we allocate to for one code table.  We get a page
1190    for the two code tables we need.  */
1191
1192 #define HUFFMAN_TABLE_SIZE (1024)
1193
1194 /* Bit masks and shifts for the values in the table.  */
1195
1196 #define HUFFMAN_VALUE_MASK 0x01ff
1197 #define HUFFMAN_BITS_SHIFT 9
1198 #define HUFFMAN_BITS_MASK 0x7
1199 #define HUFFMAN_SECONDARY_SHIFT 12
1200
1201 /* For working memory while inflating we need two code tables, we need
1202    an array of code lengths (max value 15, so we use unsigned char),
1203    and an array of unsigned shorts used while building a table.  The
1204    latter two arrays must be large enough to hold the maximum number
1205    of code lengths, which RFC 1951 defines as 286 + 30.  */
1206
1207 #define ZDEBUG_TABLE_SIZE \
1208   (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1209    + (286 + 30) * sizeof (uint16_t)           \
1210    + (286 + 30) * sizeof (unsigned char))
1211
1212 #define ZDEBUG_TABLE_CODELEN_OFFSET \
1213   (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1214    + (286 + 30) * sizeof (uint16_t))
1215
1216 #define ZDEBUG_TABLE_WORK_OFFSET \
1217   (2 * HUFFMAN_TABLE_SIZE * sizeof (uint16_t))
1218
1219 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1220
1221 /* Used by the main function that generates the fixed table to learn
1222    the table size.  */
1223 static size_t final_next_secondary;
1224
1225 #endif
1226
1227 /* Build a Huffman code table from an array of lengths in CODES of
1228    length CODES_LEN.  The table is stored into *TABLE.  ZDEBUG_TABLE
1229    is the same as for elf_zlib_inflate, used to find some work space.
1230    Returns 1 on success, 0 on error.  */
1231
1232 static int
1233 elf_zlib_inflate_table (unsigned char *codes, size_t codes_len,
1234                         uint16_t *zdebug_table, uint16_t *table)
1235 {
1236   uint16_t count[16];
1237   uint16_t start[16];
1238   uint16_t prev[16];
1239   uint16_t firstcode[7];
1240   uint16_t *next;
1241   size_t i;
1242   size_t j;
1243   unsigned int code;
1244   size_t next_secondary;
1245
1246   /* Count the number of code of each length.  Set NEXT[val] to be the
1247      next value after VAL with the same bit length.  */
1248
1249   next = (uint16_t *) (((unsigned char *) zdebug_table)
1250                        + ZDEBUG_TABLE_WORK_OFFSET);
1251
1252   memset (&count[0], 0, 16 * sizeof (uint16_t));
1253   for (i = 0; i < codes_len; ++i)
1254     {
1255       if (unlikely (codes[i] >= 16))
1256         {
1257           elf_uncompress_failed ();
1258           return 0;
1259         }
1260
1261       if (count[codes[i]] == 0)
1262         {
1263           start[codes[i]] = i;
1264           prev[codes[i]] = i;
1265         }
1266       else
1267         {
1268           next[prev[codes[i]]] = i;
1269           prev[codes[i]] = i;
1270         }
1271
1272       ++count[codes[i]];
1273     }
1274
1275   /* For each length, fill in the table for the codes of that
1276      length.  */
1277
1278   memset (table, 0, HUFFMAN_TABLE_SIZE * sizeof (uint16_t));
1279
1280   /* Handle the values that do not require a secondary table.  */
1281
1282   code = 0;
1283   for (j = 1; j <= 8; ++j)
1284     {
1285       unsigned int jcnt;
1286       unsigned int val;
1287
1288       jcnt = count[j];
1289       if (jcnt == 0)
1290         continue;
1291
1292       if (unlikely (jcnt > (1U << j)))
1293         {
1294           elf_uncompress_failed ();
1295           return 0;
1296         }
1297
1298       /* There are JCNT values that have this length, the values
1299          starting from START[j] continuing through NEXT[VAL].  Those
1300          values are assigned consecutive values starting at CODE.  */
1301
1302       val = start[j];
1303       for (i = 0; i < jcnt; ++i)
1304         {
1305           uint16_t tval;
1306           size_t ind;
1307           unsigned int incr;
1308
1309           /* In the compressed bit stream, the value VAL is encoded as
1310              J bits with the value C.  */
1311
1312           if (unlikely ((val & ~HUFFMAN_VALUE_MASK) != 0))
1313             {
1314               elf_uncompress_failed ();
1315               return 0;
1316             }
1317
1318           tval = val | ((j - 1) << HUFFMAN_BITS_SHIFT);
1319
1320           /* The table lookup uses 8 bits.  If J is less than 8, we
1321              don't know what the other bits will be.  We need to fill
1322              in all possibilities in the table.  Since the Huffman
1323              code is unambiguous, those entries can't be used for any
1324              other code.  */
1325
1326           for (ind = code; ind < 0x100; ind += 1 << j)
1327             {
1328               if (unlikely (table[ind] != 0))
1329                 {
1330                   elf_uncompress_failed ();
1331                   return 0;
1332                 }
1333               table[ind] = tval;
1334             }
1335
1336           /* Advance to the next value with this length.  */
1337           if (i + 1 < jcnt)
1338             val = next[val];
1339
1340           /* The Huffman codes are stored in the bitstream with the
1341              most significant bit first, as is required to make them
1342              unambiguous.  The effect is that when we read them from
1343              the bitstream we see the bit sequence in reverse order:
1344              the most significant bit of the Huffman code is the least
1345              significant bit of the value we read from the bitstream.
1346              That means that to make our table lookups work, we need
1347              to reverse the bits of CODE.  Since reversing bits is
1348              tedious and in general requires using a table, we instead
1349              increment CODE in reverse order.  That is, if the number
1350              of bits we are currently using, here named J, is 3, we
1351              count as 000, 100, 010, 110, 001, 101, 011, 111, which is
1352              to say the numbers from 0 to 7 but with the bits
1353              reversed.  Going to more bits, aka incrementing J,
1354              effectively just adds more zero bits as the beginning,
1355              and as such does not change the numeric value of CODE.
1356
1357              To increment CODE of length J in reverse order, find the
1358              most significant zero bit and set it to one while
1359              clearing all higher bits.  In other words, add 1 modulo
1360              2^J, only reversed.  */
1361
1362           incr = 1U << (j - 1);
1363           while ((code & incr) != 0)
1364             incr >>= 1;
1365           if (incr == 0)
1366             code = 0;
1367           else
1368             {
1369               code &= incr - 1;
1370               code += incr;
1371             }
1372         }
1373     }
1374
1375   /* Handle the values that require a secondary table.  */
1376
1377   /* Set FIRSTCODE, the number at which the codes start, for each
1378      length.  */
1379
1380   for (j = 9; j < 16; j++)
1381     {
1382       unsigned int jcnt;
1383       unsigned int k;
1384
1385       jcnt = count[j];
1386       if (jcnt == 0)
1387         continue;
1388
1389       /* There are JCNT values that have this length, the values
1390          starting from START[j].  Those values are assigned
1391          consecutive values starting at CODE.  */
1392
1393       firstcode[j - 9] = code;
1394
1395       /* Reverse add JCNT to CODE modulo 2^J.  */
1396       for (k = 0; k < j; ++k)
1397         {
1398           if ((jcnt & (1U << k)) != 0)
1399             {
1400               unsigned int m;
1401               unsigned int bit;
1402
1403               bit = 1U << (j - k - 1);
1404               for (m = 0; m < j - k; ++m, bit >>= 1)
1405                 {
1406                   if ((code & bit) == 0)
1407                     {
1408                       code += bit;
1409                       break;
1410                     }
1411                   code &= ~bit;
1412                 }
1413               jcnt &= ~(1U << k);
1414             }
1415         }
1416       if (unlikely (jcnt != 0))
1417         {
1418           elf_uncompress_failed ();
1419           return 0;
1420         }
1421     }
1422
1423   /* For J from 9 to 15, inclusive, we store COUNT[J] consecutive
1424      values starting at START[J] with consecutive codes starting at
1425      FIRSTCODE[J - 9].  In the primary table we need to point to the
1426      secondary table, and the secondary table will be indexed by J - 9
1427      bits.  We count down from 15 so that we install the larger
1428      secondary tables first, as the smaller ones may be embedded in
1429      the larger ones.  */
1430
1431   next_secondary = 0; /* Index of next secondary table (after primary).  */
1432   for (j = 15; j >= 9; j--)
1433     {
1434       unsigned int jcnt;
1435       unsigned int val;
1436       size_t primary; /* Current primary index.  */
1437       size_t secondary; /* Offset to current secondary table.  */
1438       size_t secondary_bits; /* Bit size of current secondary table.  */
1439
1440       jcnt = count[j];
1441       if (jcnt == 0)
1442         continue;
1443
1444       val = start[j];
1445       code = firstcode[j - 9];
1446       primary = 0x100;
1447       secondary = 0;
1448       secondary_bits = 0;
1449       for (i = 0; i < jcnt; ++i)
1450         {
1451           uint16_t tval;
1452           size_t ind;
1453           unsigned int incr;
1454
1455           if ((code & 0xff) != primary)
1456             {
1457               uint16_t tprimary;
1458
1459               /* Fill in a new primary table entry.  */
1460
1461               primary = code & 0xff;
1462
1463               tprimary = table[primary];
1464               if (tprimary == 0)
1465                 {
1466                   /* Start a new secondary table.  */
1467
1468                   if (unlikely ((next_secondary & HUFFMAN_VALUE_MASK)
1469                                 != next_secondary))
1470                     {
1471                       elf_uncompress_failed ();
1472                       return 0;
1473                     }
1474
1475                   secondary = next_secondary;
1476                   secondary_bits = j - 8;
1477                   next_secondary += 1 << secondary_bits;
1478                   table[primary] = (secondary
1479                                     + ((j - 8) << HUFFMAN_BITS_SHIFT)
1480                                     + (1U << HUFFMAN_SECONDARY_SHIFT));
1481                 }
1482               else
1483                 {
1484                   /* There is an existing entry.  It had better be a
1485                      secondary table with enough bits.  */
1486                   if (unlikely ((tprimary & (1U << HUFFMAN_SECONDARY_SHIFT))
1487                                 == 0))
1488                     {
1489                       elf_uncompress_failed ();
1490                       return 0;
1491                     }
1492                   secondary = tprimary & HUFFMAN_VALUE_MASK;
1493                   secondary_bits = ((tprimary >> HUFFMAN_BITS_SHIFT)
1494                                     & HUFFMAN_BITS_MASK);
1495                   if (unlikely (secondary_bits < j - 8))
1496                     {
1497                       elf_uncompress_failed ();
1498                       return 0;
1499                     }
1500                 }
1501             }
1502
1503           /* Fill in secondary table entries.  */
1504
1505           tval = val | ((j - 8) << HUFFMAN_BITS_SHIFT);
1506
1507           for (ind = code >> 8;
1508                ind < (1U << secondary_bits);
1509                ind += 1U << (j - 8))
1510             {
1511               if (unlikely (table[secondary + 0x100 + ind] != 0))
1512                 {
1513                   elf_uncompress_failed ();
1514                   return 0;
1515                 }
1516               table[secondary + 0x100 + ind] = tval;
1517             }
1518
1519           if (i + 1 < jcnt)
1520             val = next[val];
1521
1522           incr = 1U << (j - 1);
1523           while ((code & incr) != 0)
1524             incr >>= 1;
1525           if (incr == 0)
1526             code = 0;
1527           else
1528             {
1529               code &= incr - 1;
1530               code += incr;
1531             }
1532         }
1533     }
1534
1535 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1536   final_next_secondary = next_secondary;
1537 #endif
1538
1539   return 1;
1540 }
1541
1542 #ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1543
1544 /* Used to generate the fixed Huffman table for block type 1.  */
1545
1546 #include <stdio.h>
1547
1548 static uint16_t table[ZDEBUG_TABLE_SIZE];
1549 static unsigned char codes[288];
1550
1551 int
1552 main ()
1553 {
1554   size_t i;
1555
1556   for (i = 0; i <= 143; ++i)
1557     codes[i] = 8;
1558   for (i = 144; i <= 255; ++i)
1559     codes[i] = 9;
1560   for (i = 256; i <= 279; ++i)
1561     codes[i] = 7;
1562   for (i = 280; i <= 287; ++i)
1563     codes[i] = 8;
1564   if (!elf_zlib_inflate_table (&codes[0], 288, &table[0], &table[0]))
1565     {
1566       fprintf (stderr, "elf_zlib_inflate_table failed\n");
1567       exit (EXIT_FAILURE);
1568     }
1569
1570   printf ("static const uint16_t elf_zlib_default_table[%#zx] =\n",
1571           final_next_secondary + 0x100);
1572   printf ("{\n");
1573   for (i = 0; i < final_next_secondary + 0x100; i += 8)
1574     {
1575       size_t j;
1576
1577       printf (" ");
1578       for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1579         printf (" %#x,", table[j]);
1580       printf ("\n");
1581     }
1582   printf ("};\n");
1583   printf ("\n");
1584
1585   for (i = 0; i < 32; ++i)
1586     codes[i] = 5;
1587   if (!elf_zlib_inflate_table (&codes[0], 32, &table[0], &table[0]))
1588     {
1589       fprintf (stderr, "elf_zlib_inflate_table failed\n");
1590       exit (EXIT_FAILURE);
1591     }
1592
1593   printf ("static const uint16_t elf_zlib_default_dist_table[%#zx] =\n",
1594           final_next_secondary + 0x100);
1595   printf ("{\n");
1596   for (i = 0; i < final_next_secondary + 0x100; i += 8)
1597     {
1598       size_t j;
1599
1600       printf (" ");
1601       for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1602         printf (" %#x,", table[j]);
1603       printf ("\n");
1604     }
1605   printf ("};\n");
1606
1607   return 0;
1608 }
1609
1610 #endif
1611
1612 /* The fixed tables generated by the #ifdef'ed out main function
1613    above.  */
1614
1615 static const uint16_t elf_zlib_default_table[0x170] =
1616 {
1617   0xd00, 0xe50, 0xe10, 0xf18, 0xd10, 0xe70, 0xe30, 0x1230,
1618   0xd08, 0xe60, 0xe20, 0x1210, 0xe00, 0xe80, 0xe40, 0x1250,
1619   0xd04, 0xe58, 0xe18, 0x1200, 0xd14, 0xe78, 0xe38, 0x1240,
1620   0xd0c, 0xe68, 0xe28, 0x1220, 0xe08, 0xe88, 0xe48, 0x1260,
1621   0xd02, 0xe54, 0xe14, 0xf1c, 0xd12, 0xe74, 0xe34, 0x1238,
1622   0xd0a, 0xe64, 0xe24, 0x1218, 0xe04, 0xe84, 0xe44, 0x1258,
1623   0xd06, 0xe5c, 0xe1c, 0x1208, 0xd16, 0xe7c, 0xe3c, 0x1248,
1624   0xd0e, 0xe6c, 0xe2c, 0x1228, 0xe0c, 0xe8c, 0xe4c, 0x1268,
1625   0xd01, 0xe52, 0xe12, 0xf1a, 0xd11, 0xe72, 0xe32, 0x1234,
1626   0xd09, 0xe62, 0xe22, 0x1214, 0xe02, 0xe82, 0xe42, 0x1254,
1627   0xd05, 0xe5a, 0xe1a, 0x1204, 0xd15, 0xe7a, 0xe3a, 0x1244,
1628   0xd0d, 0xe6a, 0xe2a, 0x1224, 0xe0a, 0xe8a, 0xe4a, 0x1264,
1629   0xd03, 0xe56, 0xe16, 0xf1e, 0xd13, 0xe76, 0xe36, 0x123c,
1630   0xd0b, 0xe66, 0xe26, 0x121c, 0xe06, 0xe86, 0xe46, 0x125c,
1631   0xd07, 0xe5e, 0xe1e, 0x120c, 0xd17, 0xe7e, 0xe3e, 0x124c,
1632   0xd0f, 0xe6e, 0xe2e, 0x122c, 0xe0e, 0xe8e, 0xe4e, 0x126c,
1633   0xd00, 0xe51, 0xe11, 0xf19, 0xd10, 0xe71, 0xe31, 0x1232,
1634   0xd08, 0xe61, 0xe21, 0x1212, 0xe01, 0xe81, 0xe41, 0x1252,
1635   0xd04, 0xe59, 0xe19, 0x1202, 0xd14, 0xe79, 0xe39, 0x1242,
1636   0xd0c, 0xe69, 0xe29, 0x1222, 0xe09, 0xe89, 0xe49, 0x1262,
1637   0xd02, 0xe55, 0xe15, 0xf1d, 0xd12, 0xe75, 0xe35, 0x123a,
1638   0xd0a, 0xe65, 0xe25, 0x121a, 0xe05, 0xe85, 0xe45, 0x125a,
1639   0xd06, 0xe5d, 0xe1d, 0x120a, 0xd16, 0xe7d, 0xe3d, 0x124a,
1640   0xd0e, 0xe6d, 0xe2d, 0x122a, 0xe0d, 0xe8d, 0xe4d, 0x126a,
1641   0xd01, 0xe53, 0xe13, 0xf1b, 0xd11, 0xe73, 0xe33, 0x1236,
1642   0xd09, 0xe63, 0xe23, 0x1216, 0xe03, 0xe83, 0xe43, 0x1256,
1643   0xd05, 0xe5b, 0xe1b, 0x1206, 0xd15, 0xe7b, 0xe3b, 0x1246,
1644   0xd0d, 0xe6b, 0xe2b, 0x1226, 0xe0b, 0xe8b, 0xe4b, 0x1266,
1645   0xd03, 0xe57, 0xe17, 0xf1f, 0xd13, 0xe77, 0xe37, 0x123e,
1646   0xd0b, 0xe67, 0xe27, 0x121e, 0xe07, 0xe87, 0xe47, 0x125e,
1647   0xd07, 0xe5f, 0xe1f, 0x120e, 0xd17, 0xe7f, 0xe3f, 0x124e,
1648   0xd0f, 0xe6f, 0xe2f, 0x122e, 0xe0f, 0xe8f, 0xe4f, 0x126e,
1649   0x290, 0x291, 0x292, 0x293, 0x294, 0x295, 0x296, 0x297,
1650   0x298, 0x299, 0x29a, 0x29b, 0x29c, 0x29d, 0x29e, 0x29f,
1651   0x2a0, 0x2a1, 0x2a2, 0x2a3, 0x2a4, 0x2a5, 0x2a6, 0x2a7,
1652   0x2a8, 0x2a9, 0x2aa, 0x2ab, 0x2ac, 0x2ad, 0x2ae, 0x2af,
1653   0x2b0, 0x2b1, 0x2b2, 0x2b3, 0x2b4, 0x2b5, 0x2b6, 0x2b7,
1654   0x2b8, 0x2b9, 0x2ba, 0x2bb, 0x2bc, 0x2bd, 0x2be, 0x2bf,
1655   0x2c0, 0x2c1, 0x2c2, 0x2c3, 0x2c4, 0x2c5, 0x2c6, 0x2c7,
1656   0x2c8, 0x2c9, 0x2ca, 0x2cb, 0x2cc, 0x2cd, 0x2ce, 0x2cf,
1657   0x2d0, 0x2d1, 0x2d2, 0x2d3, 0x2d4, 0x2d5, 0x2d6, 0x2d7,
1658   0x2d8, 0x2d9, 0x2da, 0x2db, 0x2dc, 0x2dd, 0x2de, 0x2df,
1659   0x2e0, 0x2e1, 0x2e2, 0x2e3, 0x2e4, 0x2e5, 0x2e6, 0x2e7,
1660   0x2e8, 0x2e9, 0x2ea, 0x2eb, 0x2ec, 0x2ed, 0x2ee, 0x2ef,
1661   0x2f0, 0x2f1, 0x2f2, 0x2f3, 0x2f4, 0x2f5, 0x2f6, 0x2f7,
1662   0x2f8, 0x2f9, 0x2fa, 0x2fb, 0x2fc, 0x2fd, 0x2fe, 0x2ff,
1663 };
1664
1665 static const uint16_t elf_zlib_default_dist_table[0x100] =
1666 {
1667   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1668   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1669   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1670   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1671   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1672   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1673   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1674   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1675   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1676   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1677   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1678   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1679   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1680   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1681   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1682   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1683   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1684   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1685   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1686   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1687   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1688   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1689   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1690   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1691   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1692   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1693   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1694   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1695   0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1696   0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1697   0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1698   0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1699 };
1700
1701 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT.  Return 1 on
1702    success, 0 on some error parsing the stream.  */
1703
1704 static int
1705 elf_zlib_inflate (const unsigned char *pin, size_t sin, uint16_t *zdebug_table,
1706                   unsigned char *pout, size_t sout)
1707 {
1708   unsigned char *porigout;
1709   const unsigned char *pinend;
1710   unsigned char *poutend;
1711
1712   /* We can apparently see multiple zlib streams concatenated
1713      together, so keep going as long as there is something to read.
1714      The last 4 bytes are the checksum.  */
1715   porigout = pout;
1716   pinend = pin + sin;
1717   poutend = pout + sout;
1718   while ((pinend - pin) > 4)
1719     {
1720       uint64_t val;
1721       unsigned int bits;
1722       int last;
1723
1724       /* Read the two byte zlib header.  */
1725
1726       if (unlikely ((pin[0] & 0xf) != 8)) /* 8 is zlib encoding.  */
1727         {
1728           /* Unknown compression method.  */
1729           elf_uncompress_failed ();
1730           return 0;
1731         }
1732       if (unlikely ((pin[0] >> 4) > 7))
1733         {
1734           /* Window size too large.  Other than this check, we don't
1735              care about the window size.  */
1736           elf_uncompress_failed ();
1737           return 0;
1738         }
1739       if (unlikely ((pin[1] & 0x20) != 0))
1740         {
1741           /* Stream expects a predefined dictionary, but we have no
1742              dictionary.  */
1743           elf_uncompress_failed ();
1744           return 0;
1745         }
1746       val = (pin[0] << 8) | pin[1];
1747       if (unlikely (val % 31 != 0))
1748         {
1749           /* Header check failure.  */
1750           elf_uncompress_failed ();
1751           return 0;
1752         }
1753       pin += 2;
1754
1755       /* Align PIN to a 32-bit boundary.  */
1756
1757       val = 0;
1758       bits = 0;
1759       while ((((uintptr_t) pin) & 3) != 0)
1760         {
1761           val |= (uint64_t)*pin << bits;
1762           bits += 8;
1763           ++pin;
1764         }
1765
1766       /* Read blocks until one is marked last.  */
1767
1768       last = 0;
1769
1770       while (!last)
1771         {
1772           unsigned int type;
1773           const uint16_t *tlit;
1774           const uint16_t *tdist;
1775
1776           if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1777             return 0;
1778
1779           last = val & 1;
1780           type = (val >> 1) & 3;
1781           val >>= 3;
1782           bits -= 3;
1783
1784           if (unlikely (type == 3))
1785             {
1786               /* Invalid block type.  */
1787               elf_uncompress_failed ();
1788               return 0;
1789             }
1790
1791           if (type == 0)
1792             {
1793               uint16_t len;
1794               uint16_t lenc;
1795
1796               /* An uncompressed block.  */
1797
1798               /* If we've read ahead more than a byte, back up.  */
1799               while (bits > 8)
1800                 {
1801                   --pin;
1802                   bits -= 8;
1803                 }
1804
1805               val = 0;
1806               bits = 0;
1807               if (unlikely ((pinend - pin) < 4))
1808                 {
1809                   /* Missing length.  */
1810                   elf_uncompress_failed ();
1811                   return 0;
1812                 }
1813               len = pin[0] | (pin[1] << 8);
1814               lenc = pin[2] | (pin[3] << 8);
1815               pin += 4;
1816               lenc = ~lenc;
1817               if (unlikely (len != lenc))
1818                 {
1819                   /* Corrupt data.  */
1820                   elf_uncompress_failed ();
1821                   return 0;
1822                 }
1823               if (unlikely (len > (unsigned int) (pinend - pin)
1824                             || len > (unsigned int) (poutend - pout)))
1825                 {
1826                   /* Not enough space in buffers.  */
1827                   elf_uncompress_failed ();
1828                   return 0;
1829                 }
1830               memcpy (pout, pin, len);
1831               pout += len;
1832               pin += len;
1833
1834               /* Align PIN.  */
1835               while ((((uintptr_t) pin) & 3) != 0)
1836                 {
1837                   val |= (uint64_t)*pin << bits;
1838                   bits += 8;
1839                   ++pin;
1840                 }
1841
1842               /* Go around to read the next block.  */
1843               continue;
1844             }
1845
1846           if (type == 1)
1847             {
1848               tlit = elf_zlib_default_table;
1849               tdist = elf_zlib_default_dist_table;
1850             }
1851           else
1852             {
1853               unsigned int nlit;
1854               unsigned int ndist;
1855               unsigned int nclen;
1856               unsigned char codebits[19];
1857               unsigned char *plenbase;
1858               unsigned char *plen;
1859               unsigned char *plenend;
1860
1861               /* Read a Huffman encoding table.  The various magic
1862                  numbers here are from RFC 1951.  */
1863
1864               if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1865                 return 0;
1866
1867               nlit = (val & 0x1f) + 257;
1868               val >>= 5;
1869               ndist = (val & 0x1f) + 1;
1870               val >>= 5;
1871               nclen = (val & 0xf) + 4;
1872               val >>= 4;
1873               bits -= 14;
1874               if (unlikely (nlit > 286 || ndist > 30))
1875                 {
1876                   /* Values out of range.  */
1877                   elf_uncompress_failed ();
1878                   return 0;
1879                 }
1880
1881               /* Read and build the table used to compress the
1882                  literal, length, and distance codes.  */
1883
1884               memset(&codebits[0], 0, 19);
1885
1886               /* There are always at least 4 elements in the
1887                  table.  */
1888
1889               if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1890                 return 0;
1891
1892               codebits[16] = val & 7;
1893               codebits[17] = (val >> 3) & 7;
1894               codebits[18] = (val >> 6) & 7;
1895               codebits[0] = (val >> 9) & 7;
1896               val >>= 12;
1897               bits -= 12;
1898
1899               if (nclen == 4)
1900                 goto codebitsdone;
1901
1902               codebits[8] = val & 7;
1903               val >>= 3;
1904               bits -= 3;
1905
1906               if (nclen == 5)
1907                 goto codebitsdone;
1908
1909               if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1910                 return 0;
1911
1912               codebits[7] = val & 7;
1913               val >>= 3;
1914               bits -= 3;
1915
1916               if (nclen == 6)
1917                 goto codebitsdone;
1918
1919               codebits[9] = val & 7;
1920               val >>= 3;
1921               bits -= 3;
1922
1923               if (nclen == 7)
1924                 goto codebitsdone;
1925
1926               codebits[6] = val & 7;
1927               val >>= 3;
1928               bits -= 3;
1929
1930               if (nclen == 8)
1931                 goto codebitsdone;
1932
1933               codebits[10] = val & 7;
1934               val >>= 3;
1935               bits -= 3;
1936
1937               if (nclen == 9)
1938                 goto codebitsdone;
1939
1940               codebits[5] = val & 7;
1941               val >>= 3;
1942               bits -= 3;
1943
1944               if (nclen == 10)
1945                 goto codebitsdone;
1946
1947               if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1948                 return 0;
1949
1950               codebits[11] = val & 7;
1951               val >>= 3;
1952               bits -= 3;
1953
1954               if (nclen == 11)
1955                 goto codebitsdone;
1956
1957               codebits[4] = val & 7;
1958               val >>= 3;
1959               bits -= 3;
1960
1961               if (nclen == 12)
1962                 goto codebitsdone;
1963
1964               codebits[12] = val & 7;
1965               val >>= 3;
1966               bits -= 3;
1967
1968               if (nclen == 13)
1969                 goto codebitsdone;
1970
1971               codebits[3] = val & 7;
1972               val >>= 3;
1973               bits -= 3;
1974
1975               if (nclen == 14)
1976                 goto codebitsdone;
1977
1978               codebits[13] = val & 7;
1979               val >>= 3;
1980               bits -= 3;
1981
1982               if (nclen == 15)
1983                 goto codebitsdone;
1984
1985               if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
1986                 return 0;
1987
1988               codebits[2] = val & 7;
1989               val >>= 3;
1990               bits -= 3;
1991
1992               if (nclen == 16)
1993                 goto codebitsdone;
1994
1995               codebits[14] = val & 7;
1996               val >>= 3;
1997               bits -= 3;
1998
1999               if (nclen == 17)
2000                 goto codebitsdone;
2001
2002               codebits[1] = val & 7;
2003               val >>= 3;
2004               bits -= 3;
2005
2006               if (nclen == 18)
2007                 goto codebitsdone;
2008
2009               codebits[15] = val & 7;
2010               val >>= 3;
2011               bits -= 3;
2012
2013             codebitsdone:
2014
2015               if (!elf_zlib_inflate_table (codebits, 19, zdebug_table,
2016                                            zdebug_table))
2017                 return 0;
2018
2019               /* Read the compressed bit lengths of the literal,
2020                  length, and distance codes.  We have allocated space
2021                  at the end of zdebug_table to hold them.  */
2022
2023               plenbase = (((unsigned char *) zdebug_table)
2024                           + ZDEBUG_TABLE_CODELEN_OFFSET);
2025               plen = plenbase;
2026               plenend = plen + nlit + ndist;
2027               while (plen < plenend)
2028                 {
2029                   uint16_t t;
2030                   unsigned int b;
2031                   uint16_t v;
2032
2033                   if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2034                     return 0;
2035
2036                   t = zdebug_table[val & 0xff];
2037
2038                   /* The compression here uses bit lengths up to 7, so
2039                      a secondary table is never necessary.  */
2040                   if (unlikely ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) != 0))
2041                     {
2042                       elf_uncompress_failed ();
2043                       return 0;
2044                     }
2045
2046                   b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2047                   val >>= b + 1;
2048                   bits -= b + 1;
2049
2050                   v = t & HUFFMAN_VALUE_MASK;
2051                   if (v < 16)
2052                     *plen++ = v;
2053                   else if (v == 16)
2054                     {
2055                       unsigned int c;
2056                       unsigned int prev;
2057
2058                       /* Copy previous entry 3 to 6 times.  */
2059
2060                       if (unlikely (plen == plenbase))
2061                         {
2062                           elf_uncompress_failed ();
2063                           return 0;
2064                         }
2065
2066                       /* We used up to 7 bits since the last
2067                          elf_zlib_fetch, so we have at least 8 bits
2068                          available here.  */
2069
2070                       c = 3 + (val & 0x3);
2071                       val >>= 2;
2072                       bits -= 2;
2073                       if (unlikely ((unsigned int) (plenend - plen) < c))
2074                         {
2075                           elf_uncompress_failed ();
2076                           return 0;
2077                         }
2078
2079                       prev = plen[-1];
2080                       switch (c)
2081                         {
2082                         case 6:
2083                           *plen++ = prev;
2084                           ATTRIBUTE_FALLTHROUGH;
2085                         case 5:
2086                           *plen++ = prev;
2087                           ATTRIBUTE_FALLTHROUGH;
2088                         case 4:
2089                           *plen++ = prev;
2090                         }
2091                       *plen++ = prev;
2092                       *plen++ = prev;
2093                       *plen++ = prev;
2094                     }
2095                   else if (v == 17)
2096                     {
2097                       unsigned int c;
2098
2099                       /* Store zero 3 to 10 times.  */
2100
2101                       /* We used up to 7 bits since the last
2102                          elf_zlib_fetch, so we have at least 8 bits
2103                          available here.  */
2104
2105                       c = 3 + (val & 0x7);
2106                       val >>= 3;
2107                       bits -= 3;
2108                       if (unlikely ((unsigned int) (plenend - plen) < c))
2109                         {
2110                           elf_uncompress_failed ();
2111                           return 0;
2112                         }
2113
2114                       switch (c)
2115                         {
2116                         case 10:
2117                           *plen++ = 0;
2118                           ATTRIBUTE_FALLTHROUGH;
2119                         case 9:
2120                           *plen++ = 0;
2121                           ATTRIBUTE_FALLTHROUGH;
2122                         case 8:
2123                           *plen++ = 0;
2124                           ATTRIBUTE_FALLTHROUGH;
2125                         case 7:
2126                           *plen++ = 0;
2127                           ATTRIBUTE_FALLTHROUGH;
2128                         case 6:
2129                           *plen++ = 0;
2130                           ATTRIBUTE_FALLTHROUGH;
2131                         case 5:
2132                           *plen++ = 0;
2133                           ATTRIBUTE_FALLTHROUGH;
2134                         case 4:
2135                           *plen++ = 0;
2136                         }
2137                       *plen++ = 0;
2138                       *plen++ = 0;
2139                       *plen++ = 0;
2140                     }
2141                   else if (v == 18)
2142                     {
2143                       unsigned int c;
2144
2145                       /* Store zero 11 to 138 times.  */
2146
2147                       /* We used up to 7 bits since the last
2148                          elf_zlib_fetch, so we have at least 8 bits
2149                          available here.  */
2150
2151                       c = 11 + (val & 0x7f);
2152                       val >>= 7;
2153                       bits -= 7;
2154                       if (unlikely ((unsigned int) (plenend - plen) < c))
2155                         {
2156                           elf_uncompress_failed ();
2157                           return 0;
2158                         }
2159
2160                       memset (plen, 0, c);
2161                       plen += c;
2162                     }
2163                   else
2164                     {
2165                       elf_uncompress_failed ();
2166                       return 0;
2167                     }
2168                 }
2169
2170               /* Make sure that the stop code can appear.  */
2171
2172               plen = plenbase;
2173               if (unlikely (plen[256] == 0))
2174                 {
2175                   elf_uncompress_failed ();
2176                   return 0;
2177                 }
2178
2179               /* Build the decompression tables.  */
2180
2181               if (!elf_zlib_inflate_table (plen, nlit, zdebug_table,
2182                                            zdebug_table))
2183                 return 0;
2184               if (!elf_zlib_inflate_table (plen + nlit, ndist, zdebug_table,
2185                                            zdebug_table + HUFFMAN_TABLE_SIZE))
2186                 return 0;
2187               tlit = zdebug_table;
2188               tdist = zdebug_table + HUFFMAN_TABLE_SIZE;
2189             }
2190
2191           /* Inflate values until the end of the block.  This is the
2192              main loop of the inflation code.  */
2193
2194           while (1)
2195             {
2196               uint16_t t;
2197               unsigned int b;
2198               uint16_t v;
2199               unsigned int lit;
2200
2201               if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2202                 return 0;
2203
2204               t = tlit[val & 0xff];
2205               b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2206               v = t & HUFFMAN_VALUE_MASK;
2207
2208               if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2209                 {
2210                   lit = v;
2211                   val >>= b + 1;
2212                   bits -= b + 1;
2213                 }
2214               else
2215                 {
2216                   t = tlit[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2217                   b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2218                   lit = t & HUFFMAN_VALUE_MASK;
2219                   val >>= b + 8;
2220                   bits -= b + 8;
2221                 }
2222
2223               if (lit < 256)
2224                 {
2225                   if (unlikely (pout == poutend))
2226                     {
2227                       elf_uncompress_failed ();
2228                       return 0;
2229                     }
2230
2231                   *pout++ = lit;
2232
2233                   /* We will need to write the next byte soon.  We ask
2234                      for high temporal locality because we will write
2235                      to the whole cache line soon.  */
2236                   __builtin_prefetch (pout, 1, 3);
2237                 }
2238               else if (lit == 256)
2239                 {
2240                   /* The end of the block.  */
2241                   break;
2242                 }
2243               else
2244                 {
2245                   unsigned int dist;
2246                   unsigned int len;
2247
2248                   /* Convert lit into a length.  */
2249
2250                   if (lit < 265)
2251                     len = lit - 257 + 3;
2252                   else if (lit == 285)
2253                     len = 258;
2254                   else if (unlikely (lit > 285))
2255                     {
2256                       elf_uncompress_failed ();
2257                       return 0;
2258                     }
2259                   else
2260                     {
2261                       unsigned int extra;
2262
2263                       if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2264                         return 0;
2265
2266                       /* This is an expression for the table of length
2267                          codes in RFC 1951 3.2.5.  */
2268                       lit -= 265;
2269                       extra = (lit >> 2) + 1;
2270                       len = (lit & 3) << extra;
2271                       len += 11;
2272                       len += ((1U << (extra - 1)) - 1) << 3;
2273                       len += val & ((1U << extra) - 1);
2274                       val >>= extra;
2275                       bits -= extra;
2276                     }
2277
2278                   if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2279                     return 0;
2280
2281                   t = tdist[val & 0xff];
2282                   b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2283                   v = t & HUFFMAN_VALUE_MASK;
2284
2285                   if ((t & (1U << HUFFMAN_SECONDARY_SHIFT)) == 0)
2286                     {
2287                       dist = v;
2288                       val >>= b + 1;
2289                       bits -= b + 1;
2290                     }
2291                   else
2292                     {
2293                       t = tdist[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2294                       b = (t >> HUFFMAN_BITS_SHIFT) & HUFFMAN_BITS_MASK;
2295                       dist = t & HUFFMAN_VALUE_MASK;
2296                       val >>= b + 8;
2297                       bits -= b + 8;
2298                     }
2299
2300                   /* Convert dist to a distance.  */
2301
2302                   if (dist == 0)
2303                     {
2304                       /* A distance of 1.  A common case, meaning
2305                          repeat the last character LEN times.  */
2306
2307                       if (unlikely (pout == porigout))
2308                         {
2309                           elf_uncompress_failed ();
2310                           return 0;
2311                         }
2312
2313                       if (unlikely ((unsigned int) (poutend - pout) < len))
2314                         {
2315                           elf_uncompress_failed ();
2316                           return 0;
2317                         }
2318
2319                       memset (pout, pout[-1], len);
2320                       pout += len;
2321                     }
2322                   else if (unlikely (dist > 29))
2323                     {
2324                       elf_uncompress_failed ();
2325                       return 0;
2326                     }
2327                   else
2328                     {
2329                       if (dist < 4)
2330                         dist = dist + 1;
2331                       else
2332                         {
2333                           unsigned int extra;
2334
2335                           if (!elf_zlib_fetch (&pin, pinend, &val, &bits))
2336                             return 0;
2337
2338                           /* This is an expression for the table of
2339                              distance codes in RFC 1951 3.2.5.  */
2340                           dist -= 4;
2341                           extra = (dist >> 1) + 1;
2342                           dist = (dist & 1) << extra;
2343                           dist += 5;
2344                           dist += ((1U << (extra - 1)) - 1) << 2;
2345                           dist += val & ((1U << extra) - 1);
2346                           val >>= extra;
2347                           bits -= extra;
2348                         }
2349
2350                       /* Go back dist bytes, and copy len bytes from
2351                          there.  */
2352
2353                       if (unlikely ((unsigned int) (pout - porigout) < dist))
2354                         {
2355                           elf_uncompress_failed ();
2356                           return 0;
2357                         }
2358
2359                       if (unlikely ((unsigned int) (poutend - pout) < len))
2360                         {
2361                           elf_uncompress_failed ();
2362                           return 0;
2363                         }
2364
2365                       if (dist >= len)
2366                         {
2367                           memcpy (pout, pout - dist, len);
2368                           pout += len;
2369                         }
2370                       else
2371                         {
2372                           while (len > 0)
2373                             {
2374                               unsigned int copy;
2375
2376                               copy = len < dist ? len : dist;
2377                               memcpy (pout, pout - dist, copy);
2378                               len -= copy;
2379                               pout += copy;
2380                             }
2381                         }
2382                     }
2383                 }
2384             }
2385         }
2386     }
2387
2388   /* We should have filled the output buffer.  */
2389   if (unlikely (pout != poutend))
2390     {
2391       elf_uncompress_failed ();
2392       return 0;
2393     }
2394
2395   return 1;
2396 }
2397
2398 /* Verify the zlib checksum.  The checksum is in the 4 bytes at
2399    CHECKBYTES, and the uncompressed data is at UNCOMPRESSED /
2400    UNCOMPRESSED_SIZE.  Returns 1 on success, 0 on failure.  */
2401
2402 static int
2403 elf_zlib_verify_checksum (const unsigned char *checkbytes,
2404                           const unsigned char *uncompressed,
2405                           size_t uncompressed_size)
2406 {
2407   unsigned int i;
2408   unsigned int cksum;
2409   const unsigned char *p;
2410   uint32_t s1;
2411   uint32_t s2;
2412   size_t hsz;
2413
2414   cksum = 0;
2415   for (i = 0; i < 4; i++)
2416     cksum = (cksum << 8) | checkbytes[i];
2417
2418   s1 = 1;
2419   s2 = 0;
2420
2421   /* Minimize modulo operations.  */
2422
2423   p = uncompressed;
2424   hsz = uncompressed_size;
2425   while (hsz >= 5552)
2426     {
2427       for (i = 0; i < 5552; i += 16)
2428         {
2429           /* Manually unroll loop 16 times.  */
2430           s1 = s1 + *p++;
2431           s2 = s2 + s1;
2432           s1 = s1 + *p++;
2433           s2 = s2 + s1;
2434           s1 = s1 + *p++;
2435           s2 = s2 + s1;
2436           s1 = s1 + *p++;
2437           s2 = s2 + s1;
2438           s1 = s1 + *p++;
2439           s2 = s2 + s1;
2440           s1 = s1 + *p++;
2441           s2 = s2 + s1;
2442           s1 = s1 + *p++;
2443           s2 = s2 + s1;
2444           s1 = s1 + *p++;
2445           s2 = s2 + s1;
2446           s1 = s1 + *p++;
2447           s2 = s2 + s1;
2448           s1 = s1 + *p++;
2449           s2 = s2 + s1;
2450           s1 = s1 + *p++;
2451           s2 = s2 + s1;
2452           s1 = s1 + *p++;
2453           s2 = s2 + s1;
2454           s1 = s1 + *p++;
2455           s2 = s2 + s1;
2456           s1 = s1 + *p++;
2457           s2 = s2 + s1;
2458           s1 = s1 + *p++;
2459           s2 = s2 + s1;
2460           s1 = s1 + *p++;
2461           s2 = s2 + s1;
2462         }
2463       hsz -= 5552;
2464       s1 %= 65521;
2465       s2 %= 65521;
2466     }
2467
2468   while (hsz >= 16)
2469     {
2470       /* Manually unroll loop 16 times.  */
2471       s1 = s1 + *p++;
2472       s2 = s2 + s1;
2473       s1 = s1 + *p++;
2474       s2 = s2 + s1;
2475       s1 = s1 + *p++;
2476       s2 = s2 + s1;
2477       s1 = s1 + *p++;
2478       s2 = s2 + s1;
2479       s1 = s1 + *p++;
2480       s2 = s2 + s1;
2481       s1 = s1 + *p++;
2482       s2 = s2 + s1;
2483       s1 = s1 + *p++;
2484       s2 = s2 + s1;
2485       s1 = s1 + *p++;
2486       s2 = s2 + s1;
2487       s1 = s1 + *p++;
2488       s2 = s2 + s1;
2489       s1 = s1 + *p++;
2490       s2 = s2 + s1;
2491       s1 = s1 + *p++;
2492       s2 = s2 + s1;
2493       s1 = s1 + *p++;
2494       s2 = s2 + s1;
2495       s1 = s1 + *p++;
2496       s2 = s2 + s1;
2497       s1 = s1 + *p++;
2498       s2 = s2 + s1;
2499       s1 = s1 + *p++;
2500       s2 = s2 + s1;
2501       s1 = s1 + *p++;
2502       s2 = s2 + s1;
2503
2504       hsz -= 16;
2505     }
2506
2507   for (i = 0; i < hsz; ++i)
2508     {
2509       s1 = s1 + *p++;
2510       s2 = s2 + s1;
2511     }
2512
2513   s1 %= 65521;
2514   s2 %= 65521;
2515
2516   if (unlikely ((s2 << 16) + s1 != cksum))
2517     {
2518       elf_uncompress_failed ();
2519       return 0;
2520     }
2521
2522   return 1;
2523 }
2524
2525 /* Inflate a zlib stream from PIN/SIN to POUT/SOUT, and verify the
2526    checksum.  Return 1 on success, 0 on error.  */
2527
2528 static int
2529 elf_zlib_inflate_and_verify (const unsigned char *pin, size_t sin,
2530                              uint16_t *zdebug_table, unsigned char *pout,
2531                              size_t sout)
2532 {
2533   if (!elf_zlib_inflate (pin, sin, zdebug_table, pout, sout))
2534     return 0;
2535   if (!elf_zlib_verify_checksum (pin + sin - 4, pout, sout))
2536     return 0;
2537   return 1;
2538 }
2539
2540 /* Uncompress the old compressed debug format, the one emitted by
2541    --compress-debug-sections=zlib-gnu.  The compressed data is in
2542    COMPRESSED / COMPRESSED_SIZE, and the function writes to
2543    *UNCOMPRESSED / *UNCOMPRESSED_SIZE.  ZDEBUG_TABLE is work space to
2544    hold Huffman tables.  Returns 0 on error, 1 on successful
2545    decompression or if something goes wrong.  In general we try to
2546    carry on, by returning 1, even if we can't decompress.  */
2547
2548 static int
2549 elf_uncompress_zdebug (struct backtrace_state *state,
2550                        const unsigned char *compressed, size_t compressed_size,
2551                        uint16_t *zdebug_table,
2552                        backtrace_error_callback error_callback, void *data,
2553                        unsigned char **uncompressed, size_t *uncompressed_size)
2554 {
2555   size_t sz;
2556   size_t i;
2557   unsigned char *po;
2558
2559   *uncompressed = NULL;
2560   *uncompressed_size = 0;
2561
2562   /* The format starts with the four bytes ZLIB, followed by the 8
2563      byte length of the uncompressed data in big-endian order,
2564      followed by a zlib stream.  */
2565
2566   if (compressed_size < 12 || memcmp (compressed, "ZLIB", 4) != 0)
2567     return 1;
2568
2569   sz = 0;
2570   for (i = 0; i < 8; i++)
2571     sz = (sz << 8) | compressed[i + 4];
2572
2573   if (*uncompressed != NULL && *uncompressed_size >= sz)
2574     po = *uncompressed;
2575   else
2576     {
2577       po = (unsigned char *) backtrace_alloc (state, sz, error_callback, data);
2578       if (po == NULL)
2579         return 0;
2580     }
2581
2582   if (!elf_zlib_inflate_and_verify (compressed + 12, compressed_size - 12,
2583                                     zdebug_table, po, sz))
2584     return 1;
2585
2586   *uncompressed = po;
2587   *uncompressed_size = sz;
2588
2589   return 1;
2590 }
2591
2592 /* Uncompress the new compressed debug format, the official standard
2593    ELF approach emitted by --compress-debug-sections=zlib-gabi.  The
2594    compressed data is in COMPRESSED / COMPRESSED_SIZE, and the
2595    function writes to *UNCOMPRESSED / *UNCOMPRESSED_SIZE.
2596    ZDEBUG_TABLE is work space as for elf_uncompress_zdebug.  Returns 0
2597    on error, 1 on successful decompression or if something goes wrong.
2598    In general we try to carry on, by returning 1, even if we can't
2599    decompress.  */
2600
2601 static int
2602 elf_uncompress_chdr (struct backtrace_state *state,
2603                      const unsigned char *compressed, size_t compressed_size,
2604                      uint16_t *zdebug_table,
2605                      backtrace_error_callback error_callback, void *data,
2606                      unsigned char **uncompressed, size_t *uncompressed_size)
2607 {
2608   const b_elf_chdr *chdr;
2609   unsigned char *po;
2610
2611   *uncompressed = NULL;
2612   *uncompressed_size = 0;
2613
2614   /* The format starts with an ELF compression header.  */
2615   if (compressed_size < sizeof (b_elf_chdr))
2616     return 1;
2617
2618   chdr = (const b_elf_chdr *) compressed;
2619
2620   if (chdr->ch_type != ELFCOMPRESS_ZLIB)
2621     {
2622       /* Unsupported compression algorithm.  */
2623       return 1;
2624     }
2625
2626   if (*uncompressed != NULL && *uncompressed_size >= chdr->ch_size)
2627     po = *uncompressed;
2628   else
2629     {
2630       po = (unsigned char *) backtrace_alloc (state, chdr->ch_size,
2631                                               error_callback, data);
2632       if (po == NULL)
2633         return 0;
2634     }
2635
2636   if (!elf_zlib_inflate_and_verify (compressed + sizeof (b_elf_chdr),
2637                                     compressed_size - sizeof (b_elf_chdr),
2638                                     zdebug_table, po, chdr->ch_size))
2639     return 1;
2640
2641   *uncompressed = po;
2642   *uncompressed_size = chdr->ch_size;
2643
2644   return 1;
2645 }
2646
2647 /* This function is a hook for testing the zlib support.  It is only
2648    used by tests.  */
2649
2650 int
2651 backtrace_uncompress_zdebug (struct backtrace_state *state,
2652                              const unsigned char *compressed,
2653                              size_t compressed_size,
2654                              backtrace_error_callback error_callback,
2655                              void *data, unsigned char **uncompressed,
2656                              size_t *uncompressed_size)
2657 {
2658   uint16_t *zdebug_table;
2659   int ret;
2660
2661   zdebug_table = ((uint16_t *) backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
2662                                                 error_callback, data));
2663   if (zdebug_table == NULL)
2664     return 0;
2665   ret = elf_uncompress_zdebug (state, compressed, compressed_size,
2666                                zdebug_table, error_callback, data,
2667                                uncompressed, uncompressed_size);
2668   backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
2669                   error_callback, data);
2670   return ret;
2671 }
2672
2673 /* Number of LZMA states.  */
2674 #define LZMA_STATES (12)
2675
2676 /* Number of LZMA position states.  The pb value of the property byte
2677    is the number of bits to include in these states, and the maximum
2678    value of pb is 4.  */
2679 #define LZMA_POS_STATES (16)
2680
2681 /* Number of LZMA distance states.  These are used match distances
2682    with a short match length: up to 4 bytes.  */
2683 #define LZMA_DIST_STATES (4)
2684
2685 /* Number of LZMA distance slots.  LZMA uses six bits to encode larger
2686    match lengths, so 1 << 6 possible probabilities.  */
2687 #define LZMA_DIST_SLOTS (64)
2688
2689 /* LZMA distances 0 to 3 are encoded directly, larger values use a
2690    probability model.  */
2691 #define LZMA_DIST_MODEL_START (4)
2692
2693 /* The LZMA probability model ends at 14.  */
2694 #define LZMA_DIST_MODEL_END (14)
2695
2696 /* LZMA distance slots for distances less than 127.  */
2697 #define LZMA_FULL_DISTANCES (128)
2698
2699 /* LZMA uses four alignment bits.  */
2700 #define LZMA_ALIGN_SIZE (16)
2701
2702 /* LZMA match length is encoded with 4, 5, or 10 bits, some of which
2703    are already known.  */
2704 #define LZMA_LEN_LOW_SYMBOLS (8)
2705 #define LZMA_LEN_MID_SYMBOLS (8)
2706 #define LZMA_LEN_HIGH_SYMBOLS (256)
2707
2708 /* LZMA literal encoding.  */
2709 #define LZMA_LITERAL_CODERS_MAX (16)
2710 #define LZMA_LITERAL_CODER_SIZE (0x300)
2711
2712 /* LZMA is based on a large set of probabilities, each managed
2713    independently.  Each probability is an 11 bit number that we store
2714    in a uint16_t.  We use a single large array of probabilities.  */
2715
2716 /* Lengths of entries in the LZMA probabilities array.  The names used
2717    here are copied from the Linux kernel implementation.  */
2718
2719 #define LZMA_PROB_IS_MATCH_LEN (LZMA_STATES * LZMA_POS_STATES)
2720 #define LZMA_PROB_IS_REP_LEN LZMA_STATES
2721 #define LZMA_PROB_IS_REP0_LEN LZMA_STATES
2722 #define LZMA_PROB_IS_REP1_LEN LZMA_STATES
2723 #define LZMA_PROB_IS_REP2_LEN LZMA_STATES
2724 #define LZMA_PROB_IS_REP0_LONG_LEN (LZMA_STATES * LZMA_POS_STATES)
2725 #define LZMA_PROB_DIST_SLOT_LEN (LZMA_DIST_STATES * LZMA_DIST_SLOTS)
2726 #define LZMA_PROB_DIST_SPECIAL_LEN (LZMA_FULL_DISTANCES - LZMA_DIST_MODEL_END)
2727 #define LZMA_PROB_DIST_ALIGN_LEN LZMA_ALIGN_SIZE
2728 #define LZMA_PROB_MATCH_LEN_CHOICE_LEN 1
2729 #define LZMA_PROB_MATCH_LEN_CHOICE2_LEN 1
2730 #define LZMA_PROB_MATCH_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS)
2731 #define LZMA_PROB_MATCH_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS)
2732 #define LZMA_PROB_MATCH_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS
2733 #define LZMA_PROB_REP_LEN_CHOICE_LEN 1
2734 #define LZMA_PROB_REP_LEN_CHOICE2_LEN 1
2735 #define LZMA_PROB_REP_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS)
2736 #define LZMA_PROB_REP_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS)
2737 #define LZMA_PROB_REP_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS
2738 #define LZMA_PROB_LITERAL_LEN \
2739   (LZMA_LITERAL_CODERS_MAX * LZMA_LITERAL_CODER_SIZE)
2740
2741 /* Offsets into the LZMA probabilities array.  This is mechanically
2742    generated from the above lengths.  */
2743
2744 #define LZMA_PROB_IS_MATCH_OFFSET 0
2745 #define LZMA_PROB_IS_REP_OFFSET \
2746   (LZMA_PROB_IS_MATCH_OFFSET + LZMA_PROB_IS_MATCH_LEN)
2747 #define LZMA_PROB_IS_REP0_OFFSET \
2748   (LZMA_PROB_IS_REP_OFFSET + LZMA_PROB_IS_REP_LEN)
2749 #define LZMA_PROB_IS_REP1_OFFSET \
2750   (LZMA_PROB_IS_REP0_OFFSET + LZMA_PROB_IS_REP0_LEN)
2751 #define LZMA_PROB_IS_REP2_OFFSET \
2752   (LZMA_PROB_IS_REP1_OFFSET + LZMA_PROB_IS_REP1_LEN)
2753 #define LZMA_PROB_IS_REP0_LONG_OFFSET \
2754   (LZMA_PROB_IS_REP2_OFFSET + LZMA_PROB_IS_REP2_LEN)
2755 #define LZMA_PROB_DIST_SLOT_OFFSET \
2756   (LZMA_PROB_IS_REP0_LONG_OFFSET + LZMA_PROB_IS_REP0_LONG_LEN)
2757 #define LZMA_PROB_DIST_SPECIAL_OFFSET \
2758   (LZMA_PROB_DIST_SLOT_OFFSET + LZMA_PROB_DIST_SLOT_LEN)
2759 #define LZMA_PROB_DIST_ALIGN_OFFSET \
2760   (LZMA_PROB_DIST_SPECIAL_OFFSET + LZMA_PROB_DIST_SPECIAL_LEN)
2761 #define LZMA_PROB_MATCH_LEN_CHOICE_OFFSET \
2762   (LZMA_PROB_DIST_ALIGN_OFFSET + LZMA_PROB_DIST_ALIGN_LEN)
2763 #define LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET \
2764   (LZMA_PROB_MATCH_LEN_CHOICE_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE_LEN)
2765 #define LZMA_PROB_MATCH_LEN_LOW_OFFSET \
2766   (LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE2_LEN)
2767 #define LZMA_PROB_MATCH_LEN_MID_OFFSET \
2768   (LZMA_PROB_MATCH_LEN_LOW_OFFSET + LZMA_PROB_MATCH_LEN_LOW_LEN)
2769 #define LZMA_PROB_MATCH_LEN_HIGH_OFFSET \
2770   (LZMA_PROB_MATCH_LEN_MID_OFFSET + LZMA_PROB_MATCH_LEN_MID_LEN)
2771 #define LZMA_PROB_REP_LEN_CHOICE_OFFSET \
2772   (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + LZMA_PROB_MATCH_LEN_HIGH_LEN)
2773 #define LZMA_PROB_REP_LEN_CHOICE2_OFFSET \
2774   (LZMA_PROB_REP_LEN_CHOICE_OFFSET + LZMA_PROB_REP_LEN_CHOICE_LEN)
2775 #define LZMA_PROB_REP_LEN_LOW_OFFSET \
2776   (LZMA_PROB_REP_LEN_CHOICE2_OFFSET + LZMA_PROB_REP_LEN_CHOICE2_LEN)
2777 #define LZMA_PROB_REP_LEN_MID_OFFSET \
2778   (LZMA_PROB_REP_LEN_LOW_OFFSET + LZMA_PROB_REP_LEN_LOW_LEN)
2779 #define LZMA_PROB_REP_LEN_HIGH_OFFSET \
2780   (LZMA_PROB_REP_LEN_MID_OFFSET + LZMA_PROB_REP_LEN_MID_LEN)
2781 #define LZMA_PROB_LITERAL_OFFSET \
2782   (LZMA_PROB_REP_LEN_HIGH_OFFSET + LZMA_PROB_REP_LEN_HIGH_LEN)
2783
2784 #define LZMA_PROB_TOTAL_COUNT \
2785   (LZMA_PROB_LITERAL_OFFSET + LZMA_PROB_LITERAL_LEN)
2786
2787 /* Check that the number of LZMA probabilities is the same as the
2788    Linux kernel implementation.  */
2789
2790 #if LZMA_PROB_TOTAL_COUNT != 1846 + (1 << 4) * 0x300
2791  #error Wrong number of LZMA probabilities
2792 #endif
2793
2794 /* Expressions for the offset in the LZMA probabilities array of a
2795    specific probability.  */
2796
2797 #define LZMA_IS_MATCH(state, pos) \
2798   (LZMA_PROB_IS_MATCH_OFFSET + (state) * LZMA_POS_STATES + (pos))
2799 #define LZMA_IS_REP(state) \
2800   (LZMA_PROB_IS_REP_OFFSET + (state))
2801 #define LZMA_IS_REP0(state) \
2802   (LZMA_PROB_IS_REP0_OFFSET + (state))
2803 #define LZMA_IS_REP1(state) \
2804   (LZMA_PROB_IS_REP1_OFFSET + (state))
2805 #define LZMA_IS_REP2(state) \
2806   (LZMA_PROB_IS_REP2_OFFSET + (state))
2807 #define LZMA_IS_REP0_LONG(state, pos) \
2808   (LZMA_PROB_IS_REP0_LONG_OFFSET + (state) * LZMA_POS_STATES + (pos))
2809 #define LZMA_DIST_SLOT(dist, slot) \
2810   (LZMA_PROB_DIST_SLOT_OFFSET + (dist) * LZMA_DIST_SLOTS + (slot))
2811 #define LZMA_DIST_SPECIAL(dist) \
2812   (LZMA_PROB_DIST_SPECIAL_OFFSET + (dist))
2813 #define LZMA_DIST_ALIGN(dist) \
2814   (LZMA_PROB_DIST_ALIGN_OFFSET + (dist))
2815 #define LZMA_MATCH_LEN_CHOICE \
2816   LZMA_PROB_MATCH_LEN_CHOICE_OFFSET
2817 #define LZMA_MATCH_LEN_CHOICE2 \
2818   LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET
2819 #define LZMA_MATCH_LEN_LOW(pos, sym) \
2820   (LZMA_PROB_MATCH_LEN_LOW_OFFSET + (pos) * LZMA_LEN_LOW_SYMBOLS + (sym))
2821 #define LZMA_MATCH_LEN_MID(pos, sym) \
2822   (LZMA_PROB_MATCH_LEN_MID_OFFSET + (pos) * LZMA_LEN_MID_SYMBOLS + (sym))
2823 #define LZMA_MATCH_LEN_HIGH(sym) \
2824   (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + (sym))
2825 #define LZMA_REP_LEN_CHOICE \
2826   LZMA_PROB_REP_LEN_CHOICE_OFFSET
2827 #define LZMA_REP_LEN_CHOICE2 \
2828   LZMA_PROB_REP_LEN_CHOICE2_OFFSET
2829 #define LZMA_REP_LEN_LOW(pos, sym) \
2830   (LZMA_PROB_REP_LEN_LOW_OFFSET + (pos) * LZMA_LEN_LOW_SYMBOLS + (sym))
2831 #define LZMA_REP_LEN_MID(pos, sym) \
2832   (LZMA_PROB_REP_LEN_MID_OFFSET + (pos) * LZMA_LEN_MID_SYMBOLS + (sym))
2833 #define LZMA_REP_LEN_HIGH(sym) \
2834   (LZMA_PROB_REP_LEN_HIGH_OFFSET + (sym))
2835 #define LZMA_LITERAL(code, size) \
2836   (LZMA_PROB_LITERAL_OFFSET + (code) * LZMA_LITERAL_CODER_SIZE + (size))
2837
2838 /* Read an LZMA varint from BUF, reading and updating *POFFSET,
2839    setting *VAL.  Returns 0 on error, 1 on success.  */
2840
2841 static int
2842 elf_lzma_varint (const unsigned char *compressed, size_t compressed_size,
2843                  size_t *poffset, uint64_t *val)
2844 {
2845   size_t off;
2846   int i;
2847   uint64_t v;
2848   unsigned char b;
2849
2850   off = *poffset;
2851   i = 0;
2852   v = 0;
2853   while (1)
2854     {
2855       if (unlikely (off >= compressed_size))
2856         {
2857           elf_uncompress_failed ();
2858           return 0;
2859         }
2860       b = compressed[off];
2861       v |= (b & 0x7f) << (i * 7);
2862       ++off;
2863       if ((b & 0x80) == 0)
2864         {
2865           *poffset = off;
2866           *val = v;
2867           return 1;
2868         }
2869       ++i;
2870       if (unlikely (i >= 9))
2871         {
2872           elf_uncompress_failed ();
2873           return 0;
2874         }
2875     }
2876 }
2877
2878 /* Normalize the LZMA range decoder, pulling in an extra input byte if
2879    needed.  */
2880
2881 static void
2882 elf_lzma_range_normalize (const unsigned char *compressed,
2883                           size_t compressed_size, size_t *poffset,
2884                           uint32_t *prange, uint32_t *pcode)
2885 {
2886   if (*prange < (1U << 24))
2887     {
2888       if (unlikely (*poffset >= compressed_size))
2889         {
2890           /* We assume this will be caught elsewhere.  */
2891           elf_uncompress_failed ();
2892           return;
2893         }
2894       *prange <<= 8;
2895       *pcode <<= 8;
2896       *pcode += compressed[*poffset];
2897       ++*poffset;
2898     }
2899 }
2900
2901 /* Read and return a single bit from the LZMA stream, reading and
2902    updating *PROB.  Each bit comes from the range coder.  */
2903
2904 static int
2905 elf_lzma_bit (const unsigned char *compressed, size_t compressed_size,
2906               uint16_t *prob, size_t *poffset, uint32_t *prange,
2907               uint32_t *pcode)
2908 {
2909   uint32_t bound;
2910
2911   elf_lzma_range_normalize (compressed, compressed_size, poffset,
2912                             prange, pcode);
2913   bound = (*prange >> 11) * (uint32_t) *prob;
2914   if (*pcode < bound)
2915     {
2916       *prange = bound;
2917       *prob += ((1U << 11) - *prob) >> 5;
2918       return 0;
2919     }
2920   else
2921     {
2922       *prange -= bound;
2923       *pcode -= bound;
2924       *prob -= *prob >> 5;
2925       return 1;
2926     }
2927 }
2928
2929 /* Read an integer of size BITS from the LZMA stream, most significant
2930    bit first.  The bits are predicted using PROBS.  */
2931
2932 static uint32_t
2933 elf_lzma_integer (const unsigned char *compressed, size_t compressed_size,
2934                   uint16_t *probs, uint32_t bits, size_t *poffset,
2935                   uint32_t *prange, uint32_t *pcode)
2936 {
2937   uint32_t sym;
2938   uint32_t i;
2939
2940   sym = 1;
2941   for (i = 0; i < bits; i++)
2942     {
2943       int bit;
2944
2945       bit = elf_lzma_bit (compressed, compressed_size, probs + sym, poffset,
2946                           prange, pcode);
2947       sym <<= 1;
2948       sym += bit;
2949     }
2950   return sym - (1 << bits);
2951 }
2952
2953 /* Read an integer of size BITS from the LZMA stream, least
2954    significant bit first.  The bits are predicted using PROBS.  */
2955
2956 static uint32_t
2957 elf_lzma_reverse_integer (const unsigned char *compressed,
2958                           size_t compressed_size, uint16_t *probs,
2959                           uint32_t bits, size_t *poffset, uint32_t *prange,
2960                           uint32_t *pcode)
2961 {
2962   uint32_t sym;
2963   uint32_t val;
2964   uint32_t i;
2965
2966   sym = 1;
2967   val = 0;
2968   for (i = 0; i < bits; i++)
2969     {
2970       int bit;
2971
2972       bit = elf_lzma_bit (compressed, compressed_size, probs + sym, poffset,
2973                           prange, pcode);
2974       sym <<= 1;
2975       sym += bit;
2976       val += bit << i;
2977     }
2978   return val;
2979 }
2980
2981 /* Read a length from the LZMA stream.  IS_REP picks either LZMA_MATCH
2982    or LZMA_REP probabilities.  */
2983
2984 static uint32_t
2985 elf_lzma_len (const unsigned char *compressed, size_t compressed_size,
2986               uint16_t *probs, int is_rep, unsigned int pos_state,
2987               size_t *poffset, uint32_t *prange, uint32_t *pcode)
2988 {
2989   uint16_t *probs_choice;
2990   uint16_t *probs_sym;
2991   uint32_t bits;
2992   uint32_t len;
2993
2994   probs_choice = probs + (is_rep
2995                           ? LZMA_REP_LEN_CHOICE
2996                           : LZMA_MATCH_LEN_CHOICE);
2997   if (elf_lzma_bit (compressed, compressed_size, probs_choice, poffset,
2998                     prange, pcode))
2999     {
3000       probs_choice = probs + (is_rep
3001                               ? LZMA_REP_LEN_CHOICE2
3002                               : LZMA_MATCH_LEN_CHOICE2);
3003       if (elf_lzma_bit (compressed, compressed_size, probs_choice,
3004                         poffset, prange, pcode))
3005         {
3006           probs_sym = probs + (is_rep
3007                                ? LZMA_REP_LEN_HIGH (0)
3008                                : LZMA_MATCH_LEN_HIGH (0));
3009           bits = 8;
3010           len = 2 + 8 + 8;
3011         }
3012       else
3013         {
3014           probs_sym = probs + (is_rep
3015                                ? LZMA_REP_LEN_MID (pos_state, 0)
3016                                : LZMA_MATCH_LEN_MID (pos_state, 0));
3017           bits = 3;
3018           len = 2 + 8;
3019         }
3020     }
3021   else
3022     {
3023       probs_sym = probs + (is_rep
3024                            ? LZMA_REP_LEN_LOW (pos_state, 0)
3025                            : LZMA_MATCH_LEN_LOW (pos_state, 0));
3026       bits = 3;
3027       len = 2;
3028     }
3029
3030   len += elf_lzma_integer (compressed, compressed_size, probs_sym, bits,
3031                            poffset, prange, pcode);
3032   return len;
3033 }
3034
3035 /* Uncompress one LZMA block from a minidebug file.  The compressed
3036    data is at COMPRESSED + *POFFSET.  Update *POFFSET.  Store the data
3037    into the memory at UNCOMPRESSED, size UNCOMPRESSED_SIZE.  CHECK is
3038    the stream flag from the xz header.  Return 1 on successful
3039    decompression.  */
3040
3041 static int
3042 elf_uncompress_lzma_block (const unsigned char *compressed,
3043                            size_t compressed_size, unsigned char check,
3044                            uint16_t *probs, unsigned char *uncompressed,
3045                            size_t uncompressed_size, size_t *poffset)
3046 {
3047   size_t off;
3048   size_t block_header_offset;
3049   size_t block_header_size;
3050   unsigned char block_flags;
3051   uint64_t header_compressed_size;
3052   uint64_t header_uncompressed_size;
3053   unsigned char lzma2_properties;
3054   uint32_t computed_crc;
3055   uint32_t stream_crc;
3056   size_t uncompressed_offset;
3057   size_t dict_start_offset;
3058   unsigned int lc;
3059   unsigned int lp;
3060   unsigned int pb;
3061   uint32_t range;
3062   uint32_t code;
3063   uint32_t lstate;
3064   uint32_t dist[4];
3065
3066   off = *poffset;
3067   block_header_offset = off;
3068
3069   /* Block header size is a single byte.  */
3070   if (unlikely (off >= compressed_size))
3071     {
3072       elf_uncompress_failed ();
3073       return 0;
3074     }
3075   block_header_size = (compressed[off] + 1) * 4;
3076   if (unlikely (off + block_header_size > compressed_size))
3077     {
3078       elf_uncompress_failed ();
3079       return 0;
3080     }
3081
3082   /* Block flags.  */
3083   block_flags = compressed[off + 1];
3084   if (unlikely ((block_flags & 0x3c) != 0))
3085     {
3086       elf_uncompress_failed ();
3087       return 0;
3088     }
3089
3090   off += 2;
3091
3092   /* Optional compressed size.  */
3093   header_compressed_size = 0;
3094   if ((block_flags & 0x40) != 0)
3095     {
3096       *poffset = off;
3097       if (!elf_lzma_varint (compressed, compressed_size, poffset,
3098                             &header_compressed_size))
3099         return 0;
3100       off = *poffset;
3101     }
3102
3103   /* Optional uncompressed size.  */
3104   header_uncompressed_size = 0;
3105   if ((block_flags & 0x80) != 0)
3106     {
3107       *poffset = off;
3108       if (!elf_lzma_varint (compressed, compressed_size, poffset,
3109                             &header_uncompressed_size))
3110         return 0;
3111       off = *poffset;
3112     }
3113
3114   /* The recipe for creating a minidebug file is to run the xz program
3115      with no arguments, so we expect exactly one filter: lzma2.  */
3116
3117   if (unlikely ((block_flags & 0x3) != 0))
3118     {
3119       elf_uncompress_failed ();
3120       return 0;
3121     }
3122
3123   if (unlikely (off + 2 >= block_header_offset + block_header_size))
3124     {
3125       elf_uncompress_failed ();
3126       return 0;
3127     }
3128
3129   /* The filter ID for LZMA2 is 0x21.  */
3130   if (unlikely (compressed[off] != 0x21))
3131     {
3132       elf_uncompress_failed ();
3133       return 0;
3134     }
3135   ++off;
3136
3137   /* The size of the filter properties for LZMA2 is 1.  */
3138   if (unlikely (compressed[off] != 1))
3139     {
3140       elf_uncompress_failed ();
3141       return 0;
3142     }
3143   ++off;
3144
3145   lzma2_properties = compressed[off];
3146   ++off;
3147
3148   if (unlikely (lzma2_properties > 40))
3149     {
3150       elf_uncompress_failed ();
3151       return 0;
3152     }
3153
3154   /* The properties describe the dictionary size, but we don't care
3155      what that is.  */
3156
3157   /* Block header padding.  */
3158   if (unlikely (off + 4 > compressed_size))
3159     {
3160       elf_uncompress_failed ();
3161       return 0;
3162     }
3163
3164   off = (off + 3) &~ (size_t) 3;
3165
3166   if (unlikely (off + 4 > compressed_size))
3167     {
3168       elf_uncompress_failed ();
3169       return 0;
3170     }
3171
3172   /* Block header CRC.  */
3173   computed_crc = elf_crc32 (0, compressed + block_header_offset,
3174                             block_header_size - 4);
3175   stream_crc = ((uint32_t)compressed[off]
3176                 | ((uint32_t)compressed[off + 1] << 8)
3177                 | ((uint32_t)compressed[off + 2] << 16)
3178                 | ((uint32_t)compressed[off + 3] << 24));
3179   if (unlikely (computed_crc != stream_crc))
3180     {
3181       elf_uncompress_failed ();
3182       return 0;
3183     }
3184   off += 4;
3185
3186   /* Read a sequence of LZMA2 packets.  */
3187
3188   uncompressed_offset = 0;
3189   dict_start_offset = 0;
3190   lc = 0;
3191   lp = 0;
3192   pb = 0;
3193   lstate = 0;
3194   while (off < compressed_size)
3195     {
3196       unsigned char control;
3197
3198       range = 0xffffffff;
3199       code = 0;
3200
3201       control = compressed[off];
3202       ++off;
3203       if (unlikely (control == 0))
3204         {
3205           /* End of packets.  */
3206           break;
3207         }
3208
3209       if (control == 1 || control >= 0xe0)
3210         {
3211           /* Reset dictionary to empty.  */
3212           dict_start_offset = uncompressed_offset;
3213         }
3214
3215       if (control < 0x80)
3216         {
3217           size_t chunk_size;
3218
3219           /* The only valid values here are 1 or 2.  A 1 means to
3220              reset the dictionary (done above).  Then we see an
3221              uncompressed chunk.  */
3222
3223           if (unlikely (control > 2))
3224             {
3225               elf_uncompress_failed ();
3226               return 0;
3227             }
3228
3229           /* An uncompressed chunk is a two byte size followed by
3230              data.  */
3231
3232           if (unlikely (off + 2 > compressed_size))
3233             {
3234               elf_uncompress_failed ();
3235               return 0;
3236             }
3237
3238           chunk_size = compressed[off] << 8;
3239           chunk_size += compressed[off + 1];
3240           ++chunk_size;
3241
3242           off += 2;
3243
3244           if (unlikely (off + chunk_size > compressed_size))
3245             {
3246               elf_uncompress_failed ();
3247               return 0;
3248             }
3249           if (unlikely (uncompressed_offset + chunk_size > uncompressed_size))
3250             {
3251               elf_uncompress_failed ();
3252               return 0;
3253             }
3254
3255           memcpy (uncompressed + uncompressed_offset, compressed + off,
3256                   chunk_size);
3257           uncompressed_offset += chunk_size;
3258           off += chunk_size;
3259         }
3260       else
3261         {
3262           size_t uncompressed_chunk_start;
3263           size_t uncompressed_chunk_size;
3264           size_t compressed_chunk_size;
3265           size_t limit;
3266
3267           /* An LZMA chunk.  This starts with an uncompressed size and
3268              a compressed size.  */
3269
3270           if (unlikely (off + 4 >= compressed_size))
3271             {
3272               elf_uncompress_failed ();
3273               return 0;
3274             }
3275
3276           uncompressed_chunk_start = uncompressed_offset;
3277
3278           uncompressed_chunk_size = (control & 0x1f) << 16;
3279           uncompressed_chunk_size += compressed[off] << 8;
3280           uncompressed_chunk_size += compressed[off + 1];
3281           ++uncompressed_chunk_size;
3282
3283           compressed_chunk_size = compressed[off + 2] << 8;
3284           compressed_chunk_size += compressed[off + 3];
3285           ++compressed_chunk_size;
3286
3287           off += 4;
3288
3289           /* Bit 7 (0x80) is set.
3290              Bits 6 and 5 (0x40 and 0x20) are as follows:
3291              0: don't reset anything
3292              1: reset state
3293              2: reset state, read properties
3294              3: reset state, read properties, reset dictionary (done above) */
3295
3296           if (control >= 0xc0)
3297             {
3298               unsigned char props;
3299
3300               /* Bit 6 is set, read properties.  */
3301
3302               if (unlikely (off >= compressed_size))
3303                 {
3304                   elf_uncompress_failed ();
3305                   return 0;
3306                 }
3307               props = compressed[off];
3308               ++off;
3309               if (unlikely (props > (4 * 5 + 4) * 9 + 8))
3310                 {
3311                   elf_uncompress_failed ();
3312                   return 0;
3313                 }
3314               pb = 0;
3315               while (props >= 9 * 5)
3316                 {
3317                   props -= 9 * 5;
3318                   ++pb;
3319                 }
3320               lp = 0;
3321               while (props > 9)
3322                 {
3323                   props -= 9;
3324                   ++lp;
3325                 }
3326               lc = props;
3327               if (unlikely (lc + lp > 4))
3328                 {
3329                   elf_uncompress_failed ();
3330                   return 0;
3331                 }
3332             }
3333
3334           if (control >= 0xa0)
3335             {
3336               size_t i;
3337
3338               /* Bit 5 or 6 is set, reset LZMA state.  */
3339
3340               lstate = 0;
3341               memset (&dist, 0, sizeof dist);
3342               for (i = 0; i < LZMA_PROB_TOTAL_COUNT; i++)
3343                 probs[i] = 1 << 10;
3344               range = 0xffffffff;
3345               code = 0;
3346             }
3347
3348           /* Read the range code.  */
3349
3350           if (unlikely (off + 5 > compressed_size))
3351             {
3352               elf_uncompress_failed ();
3353               return 0;
3354             }
3355
3356           /* The byte at compressed[off] is ignored for some
3357              reason.  */
3358
3359           code = ((compressed[off + 1] << 24)
3360                   + (compressed[off + 2] << 16)
3361                   + (compressed[off + 3] << 8)
3362                   + compressed[off + 4]);
3363           off += 5;
3364
3365           /* This is the main LZMA decode loop.  */
3366
3367           limit = off + compressed_chunk_size;
3368           *poffset = off;
3369           while (*poffset < limit)
3370             {
3371               unsigned int pos_state;
3372
3373               if (unlikely (uncompressed_offset
3374                             == (uncompressed_chunk_start
3375                                 + uncompressed_chunk_size)))
3376                 {
3377                   /* We've decompressed all the expected bytes.  */
3378                   break;
3379                 }
3380
3381               pos_state = ((uncompressed_offset - dict_start_offset)
3382                            & ((1 << pb) - 1));
3383
3384               if (elf_lzma_bit (compressed, compressed_size,
3385                                 probs + LZMA_IS_MATCH (lstate, pos_state),
3386                                 poffset, &range, &code))
3387                 {
3388                   uint32_t len;
3389
3390                   if (elf_lzma_bit (compressed, compressed_size,
3391                                     probs + LZMA_IS_REP (lstate),
3392                                     poffset, &range, &code))
3393                     {
3394                       int short_rep;
3395                       uint32_t next_dist;
3396
3397                       /* Repeated match.  */
3398
3399                       short_rep = 0;
3400                       if (elf_lzma_bit (compressed, compressed_size,
3401                                         probs + LZMA_IS_REP0 (lstate),
3402                                         poffset, &range, &code))
3403                         {
3404                           if (elf_lzma_bit (compressed, compressed_size,
3405                                             probs + LZMA_IS_REP1 (lstate),
3406                                             poffset, &range, &code))
3407                             {
3408                               if (elf_lzma_bit (compressed, compressed_size,
3409                                                 probs + LZMA_IS_REP2 (lstate),
3410                                                 poffset, &range, &code))
3411                                 {
3412                                   next_dist = dist[3];
3413                                   dist[3] = dist[2];
3414                                 }
3415                               else
3416                                 {
3417                                   next_dist = dist[2];
3418                                 }
3419                               dist[2] = dist[1];
3420                             }
3421                           else
3422                             {
3423                               next_dist = dist[1];
3424                             }
3425
3426                           dist[1] = dist[0];
3427                           dist[0] = next_dist;
3428                         }
3429                       else
3430                         {
3431                           if (!elf_lzma_bit (compressed, compressed_size,
3432                                             (probs
3433                                              + LZMA_IS_REP0_LONG (lstate,
3434                                                                   pos_state)),
3435                                             poffset, &range, &code))
3436                             short_rep = 1;
3437                         }
3438
3439                       if (lstate < 7)
3440                         lstate = short_rep ? 9 : 8;
3441                       else
3442                         lstate = 11;
3443
3444                       if (short_rep)
3445                         len = 1;
3446                       else
3447                         len = elf_lzma_len (compressed, compressed_size,
3448                                             probs, 1, pos_state, poffset,
3449                                             &range, &code);
3450                     }
3451                   else
3452                     {
3453                       uint32_t dist_state;
3454                       uint32_t dist_slot;
3455                       uint16_t *probs_dist;
3456
3457                       /* Match.  */
3458
3459                       if (lstate < 7)
3460                         lstate = 7;
3461                       else
3462                         lstate = 10;
3463                       dist[3] = dist[2];
3464                       dist[2] = dist[1];
3465                       dist[1] = dist[0];
3466                       len = elf_lzma_len (compressed, compressed_size,
3467                                           probs, 0, pos_state, poffset,
3468                                           &range, &code);
3469
3470                       if (len < 4 + 2)
3471                         dist_state = len - 2;
3472                       else
3473                         dist_state = 3;
3474                       probs_dist = probs + LZMA_DIST_SLOT (dist_state, 0);
3475                       dist_slot = elf_lzma_integer (compressed,
3476                                                     compressed_size,
3477                                                     probs_dist, 6,
3478                                                     poffset, &range,
3479                                                     &code);
3480                       if (dist_slot < LZMA_DIST_MODEL_START)
3481                         dist[0] = dist_slot;
3482                       else
3483                         {
3484                           uint32_t limit;
3485
3486                           limit = (dist_slot >> 1) - 1;
3487                           dist[0] = 2 + (dist_slot & 1);
3488                           if (dist_slot < LZMA_DIST_MODEL_END)
3489                             {
3490                               dist[0] <<= limit;
3491                               probs_dist = (probs
3492                                             + LZMA_DIST_SPECIAL(dist[0]
3493                                                                 - dist_slot
3494                                                                 - 1));
3495                               dist[0] +=
3496                                 elf_lzma_reverse_integer (compressed,
3497                                                           compressed_size,
3498                                                           probs_dist,
3499                                                           limit, poffset,
3500                                                           &range, &code);
3501                             }
3502                           else
3503                             {
3504                               uint32_t dist0;
3505                               uint32_t i;
3506
3507                               dist0 = dist[0];
3508                               for (i = 0; i < limit - 4; i++)
3509                                 {
3510                                   uint32_t mask;
3511
3512                                   elf_lzma_range_normalize (compressed,
3513                                                             compressed_size,
3514                                                             poffset,
3515                                                             &range, &code);
3516                                   range >>= 1;
3517                                   code -= range;
3518                                   mask = -(code >> 31);
3519                                   code += range & mask;
3520                                   dist0 <<= 1;
3521                                   dist0 += mask + 1;
3522                                 }
3523                               dist0 <<= 4;
3524                               probs_dist = probs + LZMA_DIST_ALIGN (0);
3525                               dist0 +=
3526                                 elf_lzma_reverse_integer (compressed,
3527                                                           compressed_size,
3528                                                           probs_dist, 4,
3529                                                           poffset,
3530                                                           &range, &code);
3531                               dist[0] = dist0;
3532                             }
3533                         }
3534                     }
3535
3536                   if (unlikely (uncompressed_offset
3537                                 - dict_start_offset < dist[0] + 1))
3538                     {
3539                       elf_uncompress_failed ();
3540                       return 0;
3541                     }
3542                   if (unlikely (uncompressed_offset + len > uncompressed_size))
3543                     {
3544                       elf_uncompress_failed ();
3545                       return 0;
3546                     }
3547
3548                   if (dist[0] == 0)
3549                     {
3550                       /* A common case, meaning repeat the last
3551                          character LEN times.  */
3552                       memset (uncompressed + uncompressed_offset,
3553                               uncompressed[uncompressed_offset - 1],
3554                               len);
3555                       uncompressed_offset += len;
3556                     }
3557                   else if (dist[0] + 1 >= len)
3558                     {
3559                       memcpy (uncompressed + uncompressed_offset,
3560                               uncompressed + uncompressed_offset - dist[0] - 1,
3561                               len);
3562                       uncompressed_offset += len;
3563                     }
3564                   else
3565                     {
3566                       while (len > 0)
3567                         {
3568                           uint32_t copy;
3569
3570                           copy = len < dist[0] + 1 ? len : dist[0] + 1;
3571                           memcpy (uncompressed + uncompressed_offset,
3572                                   (uncompressed + uncompressed_offset
3573                                    - dist[0] - 1),
3574                                   copy);
3575                           len -= copy;
3576                           uncompressed_offset += copy;
3577                         }
3578                     }
3579                 }
3580               else
3581                 {
3582                   unsigned char prev;
3583                   unsigned char low;
3584                   size_t high;
3585                   uint16_t *lit_probs;
3586                   unsigned int sym;
3587
3588                   /* Literal value.  */
3589
3590                   if (uncompressed_offset > 0)
3591                     prev = uncompressed[uncompressed_offset - 1];
3592                   else
3593                     prev = 0;
3594                   low = prev >> (8 - lc);
3595                   high = (((uncompressed_offset - dict_start_offset)
3596                            & ((1 << lp) - 1))
3597                           << lc);
3598                   lit_probs = probs + LZMA_LITERAL (low + high, 0);
3599                   if (lstate < 7)
3600                     sym = elf_lzma_integer (compressed, compressed_size,
3601                                             lit_probs, 8, poffset, &range,
3602                                             &code);
3603                   else
3604                     {
3605                       unsigned int match;
3606                       unsigned int bit;
3607                       unsigned int match_bit;
3608                       unsigned int idx;
3609
3610                       sym = 1;
3611                       if (uncompressed_offset >= dist[0] + 1)
3612                         match = uncompressed[uncompressed_offset - dist[0] - 1];
3613                       else
3614                         match = 0;
3615                       match <<= 1;
3616                       bit = 0x100;
3617                       do
3618                         {
3619                           match_bit = match & bit;
3620                           match <<= 1;
3621                           idx = bit + match_bit + sym;
3622                           sym <<= 1;
3623                           if (elf_lzma_bit (compressed, compressed_size,
3624                                             lit_probs + idx, poffset,
3625                                             &range, &code))
3626                             {
3627                               ++sym;
3628                               bit &= match_bit;
3629                             }
3630                           else
3631                             {
3632                               bit &= ~ match_bit;
3633                             }
3634                         }
3635                       while (sym < 0x100);
3636                     }
3637
3638                   if (unlikely (uncompressed_offset >= uncompressed_size))
3639                     {
3640                       elf_uncompress_failed ();
3641                       return 0;
3642                     }
3643
3644                   uncompressed[uncompressed_offset] = (unsigned char) sym;
3645                   ++uncompressed_offset;
3646                   if (lstate <= 3)
3647                     lstate = 0;
3648                   else if (lstate <= 9)
3649                     lstate -= 3;
3650                   else
3651                     lstate -= 6;
3652                 }
3653             }
3654
3655           elf_lzma_range_normalize (compressed, compressed_size, poffset,
3656                                     &range, &code);
3657
3658           off = *poffset;
3659         }
3660     }
3661
3662   /* We have reached the end of the block.  Pad to four byte
3663      boundary.  */
3664   off = (off + 3) &~ (size_t) 3;
3665   if (unlikely (off > compressed_size))
3666     {
3667       elf_uncompress_failed ();
3668       return 0;
3669     }
3670
3671   switch (check)
3672     {
3673     case 0:
3674       /* No check.  */
3675       break;
3676
3677     case 1:
3678       /* CRC32 */
3679       if (unlikely (off + 4 > compressed_size))
3680         {
3681           elf_uncompress_failed ();
3682           return 0;
3683         }
3684       computed_crc = elf_crc32 (0, uncompressed, uncompressed_offset);
3685       stream_crc = (compressed[off]
3686                     | (compressed[off + 1] << 8)
3687                     | (compressed[off + 2] << 16)
3688                     | (compressed[off + 3] << 24));
3689       if (computed_crc != stream_crc)
3690         {
3691           elf_uncompress_failed ();
3692           return 0;
3693         }
3694       off += 4;
3695       break;
3696
3697     case 4:
3698       /* CRC64.  We don't bother computing a CRC64 checksum.  */
3699       if (unlikely (off + 8 > compressed_size))
3700         {
3701           elf_uncompress_failed ();
3702           return 0;
3703         }
3704       off += 8;
3705       break;
3706
3707     case 10:
3708       /* SHA.  We don't bother computing a SHA checksum.  */
3709       if (unlikely (off + 32 > compressed_size))
3710         {
3711           elf_uncompress_failed ();
3712           return 0;
3713         }
3714       off += 32;
3715       break;
3716
3717     default:
3718       elf_uncompress_failed ();
3719       return 0;
3720     }
3721
3722   *poffset = off;
3723
3724   return 1;
3725 }
3726
3727 /* Uncompress LZMA data found in a minidebug file.  The minidebug
3728    format is described at
3729    https://sourceware.org/gdb/current/onlinedocs/gdb/MiniDebugInfo.html.
3730    Returns 0 on error, 1 on successful decompression.  For this
3731    function we return 0 on failure to decompress, as the calling code
3732    will carry on in that case.  */
3733
3734 static int
3735 elf_uncompress_lzma (struct backtrace_state *state,
3736                      const unsigned char *compressed, size_t compressed_size,
3737                      backtrace_error_callback error_callback, void *data,
3738                      unsigned char **uncompressed, size_t *uncompressed_size)
3739 {
3740   size_t header_size;
3741   size_t footer_size;
3742   unsigned char check;
3743   uint32_t computed_crc;
3744   uint32_t stream_crc;
3745   size_t offset;
3746   size_t index_size;
3747   size_t footer_offset;
3748   size_t index_offset;
3749   uint64_t index_compressed_size;
3750   uint64_t index_uncompressed_size;
3751   unsigned char *mem;
3752   uint16_t *probs;
3753   size_t compressed_block_size;
3754
3755   /* The format starts with a stream header and ends with a stream
3756      footer.  */
3757   header_size = 12;
3758   footer_size = 12;
3759   if (unlikely (compressed_size < header_size + footer_size))
3760     {
3761       elf_uncompress_failed ();
3762       return 0;
3763     }
3764
3765   /* The stream header starts with a magic string.  */
3766   if (unlikely (memcmp (compressed, "\375" "7zXZ\0", 6) != 0))
3767     {
3768       elf_uncompress_failed ();
3769       return 0;
3770     }
3771
3772   /* Next come stream flags.  The first byte is zero, the second byte
3773      is the check.  */
3774   if (unlikely (compressed[6] != 0))
3775     {
3776       elf_uncompress_failed ();
3777       return 0;
3778     }
3779   check = compressed[7];
3780   if (unlikely ((check & 0xf8) != 0))
3781     {
3782       elf_uncompress_failed ();
3783       return 0;
3784     }
3785
3786   /* Next comes a CRC of the stream flags.  */
3787   computed_crc = elf_crc32 (0, compressed + 6, 2);
3788   stream_crc = ((uint32_t)compressed[8]
3789                 | ((uint32_t)compressed[9] << 8)
3790                 | ((uint32_t)compressed[10] << 16)
3791                 | ((uint32_t)compressed[11] << 24));
3792   if (unlikely (computed_crc != stream_crc))
3793     {
3794       elf_uncompress_failed ();
3795       return 0;
3796     }
3797
3798   /* Now that we've parsed the header, parse the footer, so that we
3799      can get the uncompressed size.  */
3800
3801   /* The footer ends with two magic bytes.  */
3802
3803   offset = compressed_size;
3804   if (unlikely (memcmp (compressed + offset - 2, "YZ", 2) != 0))
3805     {
3806       elf_uncompress_failed ();
3807       return 0;
3808     }
3809   offset -= 2;
3810
3811   /* Before that are the stream flags, which should be the same as the
3812      flags in the header.  */
3813   if (unlikely (compressed[offset - 2] != 0
3814                 || compressed[offset - 1] != check))
3815     {
3816       elf_uncompress_failed ();
3817       return 0;
3818     }
3819   offset -= 2;
3820
3821   /* Before that is the size of the index field, which precedes the
3822      footer.  */
3823   index_size = (compressed[offset - 4]
3824                 | (compressed[offset - 3] << 8)
3825                 | (compressed[offset - 2] << 16)
3826                 | (compressed[offset - 1] << 24));
3827   index_size = (index_size + 1) * 4;
3828   offset -= 4;
3829
3830   /* Before that is a footer CRC.  */
3831   computed_crc = elf_crc32 (0, compressed + offset, 6);
3832   stream_crc = ((uint32_t)compressed[offset - 4]
3833                 | ((uint32_t)compressed[offset - 3] << 8)
3834                 | ((uint32_t)compressed[offset - 2] << 16)
3835                 | ((uint32_t)compressed[offset - 1] << 24));
3836   if (unlikely (computed_crc != stream_crc))
3837     {
3838       elf_uncompress_failed ();
3839       return 0;
3840     }
3841   offset -= 4;
3842
3843   /* The index comes just before the footer.  */
3844   if (unlikely (offset < index_size + header_size))
3845     {
3846       elf_uncompress_failed ();
3847       return 0;
3848     }
3849
3850   footer_offset = offset;
3851   offset -= index_size;
3852   index_offset = offset;
3853
3854   /* The index starts with a zero byte.  */
3855   if (unlikely (compressed[offset] != 0))
3856     {
3857       elf_uncompress_failed ();
3858       return 0;
3859     }
3860   ++offset;
3861
3862   /* Next is the number of blocks.  We expect zero blocks for an empty
3863      stream, and otherwise a single block.  */
3864   if (unlikely (compressed[offset] == 0))
3865     {
3866       *uncompressed = NULL;
3867       *uncompressed_size = 0;
3868       return 1;
3869     }
3870   if (unlikely (compressed[offset] != 1))
3871     {
3872       elf_uncompress_failed ();
3873       return 0;
3874     }
3875   ++offset;
3876
3877   /* Next is the compressed size and the uncompressed size.  */
3878   if (!elf_lzma_varint (compressed, compressed_size, &offset,
3879                         &index_compressed_size))
3880     return 0;
3881   if (!elf_lzma_varint (compressed, compressed_size, &offset,
3882                         &index_uncompressed_size))
3883     return 0;
3884
3885   /* Pad to a four byte boundary.  */
3886   offset = (offset + 3) &~ (size_t) 3;
3887
3888   /* Next is a CRC of the index.  */
3889   computed_crc = elf_crc32 (0, compressed + index_offset,
3890                             offset - index_offset);
3891   stream_crc = ((uint32_t)compressed[offset]
3892                 | ((uint32_t)compressed[offset + 1] << 8)
3893                 | ((uint32_t)compressed[offset + 2] << 16)
3894                 | ((uint32_t)compressed[offset + 3] << 24));
3895   if (unlikely (computed_crc != stream_crc))
3896     {
3897       elf_uncompress_failed ();
3898       return 0;
3899     }
3900   offset += 4;
3901
3902   /* We should now be back at the footer.  */
3903   if (unlikely (offset != footer_offset))
3904     {
3905       elf_uncompress_failed ();
3906       return 0;
3907     }
3908
3909   /* Allocate space to hold the uncompressed data.  If we succeed in
3910      uncompressing the LZMA data, we never free this memory.  */
3911   mem = (unsigned char *) backtrace_alloc (state, index_uncompressed_size,
3912                                            error_callback, data);
3913   if (unlikely (mem == NULL))
3914     return 0;
3915   *uncompressed = mem;
3916   *uncompressed_size = index_uncompressed_size;
3917
3918   /* Allocate space for probabilities.  */
3919   probs = ((uint16_t *)
3920            backtrace_alloc (state,
3921                             LZMA_PROB_TOTAL_COUNT * sizeof (uint16_t),
3922                             error_callback, data));
3923   if (unlikely (probs == NULL))
3924     {
3925       backtrace_free (state, mem, index_uncompressed_size, error_callback,
3926                       data);
3927       return 0;
3928     }
3929
3930   /* Uncompress the block, which follows the header.  */
3931   offset = 12;
3932   if (!elf_uncompress_lzma_block (compressed, compressed_size, check, probs,
3933                                   mem, index_uncompressed_size, &offset))
3934     {
3935       backtrace_free (state, mem, index_uncompressed_size, error_callback,
3936                       data);
3937       return 0;
3938     }
3939
3940   compressed_block_size = offset - 12;
3941   if (unlikely (compressed_block_size
3942                 != ((index_compressed_size + 3) &~ (size_t) 3)))
3943     {
3944       elf_uncompress_failed ();
3945       backtrace_free (state, mem, index_uncompressed_size, error_callback,
3946                       data);
3947       return 0;
3948     }
3949
3950   offset = (offset + 3) &~ (size_t) 3;
3951   if (unlikely (offset != index_offset))
3952     {
3953       elf_uncompress_failed ();
3954       backtrace_free (state, mem, index_uncompressed_size, error_callback,
3955                       data);
3956       return 0;
3957     }
3958
3959   return 1;
3960 }
3961
3962 /* This function is a hook for testing the LZMA support.  It is only
3963    used by tests.  */
3964
3965 int
3966 backtrace_uncompress_lzma (struct backtrace_state *state,
3967                            const unsigned char *compressed,
3968                            size_t compressed_size,
3969                            backtrace_error_callback error_callback,
3970                            void *data, unsigned char **uncompressed,
3971                            size_t *uncompressed_size)
3972 {
3973   return elf_uncompress_lzma (state, compressed, compressed_size,
3974                               error_callback, data, uncompressed,
3975                               uncompressed_size);
3976 }
3977
3978 /* Add the backtrace data for one ELF file.  Returns 1 on success,
3979    0 on failure (in both cases descriptor is closed) or -1 if exe
3980    is non-zero and the ELF file is ET_DYN, which tells the caller that
3981    elf_add will need to be called on the descriptor again after
3982    base_address is determined.  */
3983
3984 static int
3985 elf_add (struct backtrace_state *state, const char *filename, int descriptor,
3986          const unsigned char *memory, size_t memory_size,
3987          uintptr_t base_address, backtrace_error_callback error_callback,
3988          void *data, fileline *fileline_fn, int *found_sym, int *found_dwarf,
3989          struct dwarf_data **fileline_entry, int exe, int debuginfo,
3990          const char *with_buildid_data, uint32_t with_buildid_size)
3991 {
3992   struct elf_view ehdr_view;
3993   b_elf_ehdr ehdr;
3994   off_t shoff;
3995   unsigned int shnum;
3996   unsigned int shstrndx;
3997   struct elf_view shdrs_view;
3998   int shdrs_view_valid;
3999   const b_elf_shdr *shdrs;
4000   const b_elf_shdr *shstrhdr;
4001   size_t shstr_size;
4002   off_t shstr_off;
4003   struct elf_view names_view;
4004   int names_view_valid;
4005   const char *names;
4006   unsigned int symtab_shndx;
4007   unsigned int dynsym_shndx;
4008   unsigned int i;
4009   struct debug_section_info sections[DEBUG_MAX];
4010   struct debug_section_info zsections[DEBUG_MAX];
4011   struct elf_view symtab_view;
4012   int symtab_view_valid;
4013   struct elf_view strtab_view;
4014   int strtab_view_valid;
4015   struct elf_view buildid_view;
4016   int buildid_view_valid;
4017   const char *buildid_data;
4018   uint32_t buildid_size;
4019   struct elf_view debuglink_view;
4020   int debuglink_view_valid;
4021   const char *debuglink_name;
4022   uint32_t debuglink_crc;
4023   struct elf_view debugaltlink_view;
4024   int debugaltlink_view_valid;
4025   const char *debugaltlink_name;
4026   const char *debugaltlink_buildid_data;
4027   uint32_t debugaltlink_buildid_size;
4028   struct elf_view gnu_debugdata_view;
4029   int gnu_debugdata_view_valid;
4030   size_t gnu_debugdata_size;
4031   unsigned char *gnu_debugdata_uncompressed;
4032   size_t gnu_debugdata_uncompressed_size;
4033   off_t min_offset;
4034   off_t max_offset;
4035   off_t debug_size;
4036   struct elf_view debug_view;
4037   int debug_view_valid;
4038   unsigned int using_debug_view;
4039   uint16_t *zdebug_table;
4040   struct elf_view split_debug_view[DEBUG_MAX];
4041   unsigned char split_debug_view_valid[DEBUG_MAX];
4042   struct elf_ppc64_opd_data opd_data, *opd;
4043   struct dwarf_sections dwarf_sections;
4044
4045   if (!debuginfo)
4046     {
4047       *found_sym = 0;
4048       *found_dwarf = 0;
4049     }
4050
4051   shdrs_view_valid = 0;
4052   names_view_valid = 0;
4053   symtab_view_valid = 0;
4054   strtab_view_valid = 0;
4055   buildid_view_valid = 0;
4056   buildid_data = NULL;
4057   buildid_size = 0;
4058   debuglink_view_valid = 0;
4059   debuglink_name = NULL;
4060   debuglink_crc = 0;
4061   debugaltlink_view_valid = 0;
4062   debugaltlink_name = NULL;
4063   debugaltlink_buildid_data = NULL;
4064   debugaltlink_buildid_size = 0;
4065   gnu_debugdata_view_valid = 0;
4066   gnu_debugdata_size = 0;
4067   debug_view_valid = 0;
4068   memset (&split_debug_view_valid[0], 0, sizeof split_debug_view_valid);
4069   opd = NULL;
4070
4071   if (!elf_get_view (state, descriptor, memory, memory_size, 0, sizeof ehdr,
4072                      error_callback, data, &ehdr_view))
4073     goto fail;
4074
4075   memcpy (&ehdr, ehdr_view.view.data, sizeof ehdr);
4076
4077   elf_release_view (state, &ehdr_view, error_callback, data);
4078
4079   if (ehdr.e_ident[EI_MAG0] != ELFMAG0
4080       || ehdr.e_ident[EI_MAG1] != ELFMAG1
4081       || ehdr.e_ident[EI_MAG2] != ELFMAG2
4082       || ehdr.e_ident[EI_MAG3] != ELFMAG3)
4083     {
4084       error_callback (data, "executable file is not ELF", 0);
4085       goto fail;
4086     }
4087   if (ehdr.e_ident[EI_VERSION] != EV_CURRENT)
4088     {
4089       error_callback (data, "executable file is unrecognized ELF version", 0);
4090       goto fail;
4091     }
4092
4093 #if BACKTRACE_ELF_SIZE == 32
4094 #define BACKTRACE_ELFCLASS ELFCLASS32
4095 #else
4096 #define BACKTRACE_ELFCLASS ELFCLASS64
4097 #endif
4098
4099   if (ehdr.e_ident[EI_CLASS] != BACKTRACE_ELFCLASS)
4100     {
4101       error_callback (data, "executable file is unexpected ELF class", 0);
4102       goto fail;
4103     }
4104
4105   if (ehdr.e_ident[EI_DATA] != ELFDATA2LSB
4106       && ehdr.e_ident[EI_DATA] != ELFDATA2MSB)
4107     {
4108       error_callback (data, "executable file has unknown endianness", 0);
4109       goto fail;
4110     }
4111
4112   /* If the executable is ET_DYN, it is either a PIE, or we are running
4113      directly a shared library with .interp.  We need to wait for
4114      dl_iterate_phdr in that case to determine the actual base_address.  */
4115   if (exe && ehdr.e_type == ET_DYN)
4116     return -1;
4117
4118   shoff = ehdr.e_shoff;
4119   shnum = ehdr.e_shnum;
4120   shstrndx = ehdr.e_shstrndx;
4121
4122   if ((shnum == 0 || shstrndx == SHN_XINDEX)
4123       && shoff != 0)
4124     {
4125       struct elf_view shdr_view;
4126       const b_elf_shdr *shdr;
4127
4128       if (!elf_get_view (state, descriptor, memory, memory_size, shoff,
4129                          sizeof shdr, error_callback, data, &shdr_view))
4130         goto fail;
4131
4132       shdr = (const b_elf_shdr *) shdr_view.view.data;
4133
4134       if (shnum == 0)
4135         shnum = shdr->sh_size;
4136
4137       if (shstrndx == SHN_XINDEX)
4138         {
4139           shstrndx = shdr->sh_link;
4140
4141           /* Versions of the GNU binutils between 2.12 and 2.18 did
4142              not handle objects with more than SHN_LORESERVE sections
4143              correctly.  All large section indexes were offset by
4144              0x100.  There is more information at
4145              http://sourceware.org/bugzilla/show_bug.cgi?id-5900 .
4146              Fortunately these object files are easy to detect, as the
4147              GNU binutils always put the section header string table
4148              near the end of the list of sections.  Thus if the
4149              section header string table index is larger than the
4150              number of sections, then we know we have to subtract
4151              0x100 to get the real section index.  */
4152           if (shstrndx >= shnum && shstrndx >= SHN_LORESERVE + 0x100)
4153             shstrndx -= 0x100;
4154         }
4155
4156       elf_release_view (state, &shdr_view, error_callback, data);
4157     }
4158
4159   if (shnum == 0 || shstrndx == 0)
4160     goto fail;
4161
4162   /* To translate PC to file/line when using DWARF, we need to find
4163      the .debug_info and .debug_line sections.  */
4164
4165   /* Read the section headers, skipping the first one.  */
4166
4167   if (!elf_get_view (state, descriptor, memory, memory_size,
4168                      shoff + sizeof (b_elf_shdr),
4169                      (shnum - 1) * sizeof (b_elf_shdr),
4170                      error_callback, data, &shdrs_view))
4171     goto fail;
4172   shdrs_view_valid = 1;
4173   shdrs = (const b_elf_shdr *) shdrs_view.view.data;
4174
4175   /* Read the section names.  */
4176
4177   shstrhdr = &shdrs[shstrndx - 1];
4178   shstr_size = shstrhdr->sh_size;
4179   shstr_off = shstrhdr->sh_offset;
4180
4181   if (!elf_get_view (state, descriptor, memory, memory_size, shstr_off,
4182                      shstrhdr->sh_size, error_callback, data, &names_view))
4183     goto fail;
4184   names_view_valid = 1;
4185   names = (const char *) names_view.view.data;
4186
4187   symtab_shndx = 0;
4188   dynsym_shndx = 0;
4189
4190   memset (sections, 0, sizeof sections);
4191   memset (zsections, 0, sizeof zsections);
4192
4193   /* Look for the symbol table.  */
4194   for (i = 1; i < shnum; ++i)
4195     {
4196       const b_elf_shdr *shdr;
4197       unsigned int sh_name;
4198       const char *name;
4199       int j;
4200
4201       shdr = &shdrs[i - 1];
4202
4203       if (shdr->sh_type == SHT_SYMTAB)
4204         symtab_shndx = i;
4205       else if (shdr->sh_type == SHT_DYNSYM)
4206         dynsym_shndx = i;
4207
4208       sh_name = shdr->sh_name;
4209       if (sh_name >= shstr_size)
4210         {
4211           error_callback (data, "ELF section name out of range", 0);
4212           goto fail;
4213         }
4214
4215       name = names + sh_name;
4216
4217       for (j = 0; j < (int) DEBUG_MAX; ++j)
4218         {
4219           if (strcmp (name, dwarf_section_names[j]) == 0)
4220             {
4221               sections[j].offset = shdr->sh_offset;
4222               sections[j].size = shdr->sh_size;
4223               sections[j].compressed = (shdr->sh_flags & SHF_COMPRESSED) != 0;
4224               break;
4225             }
4226         }
4227
4228       if (name[0] == '.' && name[1] == 'z')
4229         {
4230           for (j = 0; j < (int) DEBUG_MAX; ++j)
4231             {
4232               if (strcmp (name + 2, dwarf_section_names[j] + 1) == 0)
4233                 {
4234                   zsections[j].offset = shdr->sh_offset;
4235                   zsections[j].size = shdr->sh_size;
4236                   break;
4237                 }
4238             }
4239         }
4240
4241       /* Read the build ID if present.  This could check for any
4242          SHT_NOTE section with the right note name and type, but gdb
4243          looks for a specific section name.  */
4244       if ((!debuginfo || with_buildid_data != NULL)
4245           && !buildid_view_valid
4246           && strcmp (name, ".note.gnu.build-id") == 0)
4247         {
4248           const b_elf_note *note;
4249
4250           if (!elf_get_view (state, descriptor, memory, memory_size,
4251                              shdr->sh_offset, shdr->sh_size, error_callback,
4252                              data, &buildid_view))
4253             goto fail;
4254
4255           buildid_view_valid = 1;
4256           note = (const b_elf_note *) buildid_view.view.data;
4257           if (note->type == NT_GNU_BUILD_ID
4258               && note->namesz == 4
4259               && strncmp (note->name, "GNU", 4) == 0
4260               && shdr->sh_size <= 12 + ((note->namesz + 3) & ~ 3) + note->descsz)
4261             {
4262               buildid_data = &note->name[0] + ((note->namesz + 3) & ~ 3);
4263               buildid_size = note->descsz;
4264             }
4265
4266           if (with_buildid_size != 0)
4267             {
4268               if (buildid_size != with_buildid_size)
4269                 goto fail;
4270
4271               if (memcmp (buildid_data, with_buildid_data, buildid_size) != 0)
4272                 goto fail;
4273             }
4274         }
4275
4276       /* Read the debuglink file if present.  */
4277       if (!debuginfo
4278           && !debuglink_view_valid
4279           && strcmp (name, ".gnu_debuglink") == 0)
4280         {
4281           const char *debuglink_data;
4282           size_t crc_offset;
4283
4284           if (!elf_get_view (state, descriptor, memory, memory_size,
4285                              shdr->sh_offset, shdr->sh_size, error_callback,
4286                              data, &debuglink_view))
4287             goto fail;
4288
4289           debuglink_view_valid = 1;
4290           debuglink_data = (const char *) debuglink_view.view.data;
4291           crc_offset = strnlen (debuglink_data, shdr->sh_size);
4292           crc_offset = (crc_offset + 3) & ~3;
4293           if (crc_offset + 4 <= shdr->sh_size)
4294             {
4295               debuglink_name = debuglink_data;
4296               debuglink_crc = *(const uint32_t*)(debuglink_data + crc_offset);
4297             }
4298         }
4299
4300       if (!debugaltlink_view_valid
4301           && strcmp (name, ".gnu_debugaltlink") == 0)
4302         {
4303           const char *debugaltlink_data;
4304           size_t debugaltlink_name_len;
4305
4306           if (!elf_get_view (state, descriptor, memory, memory_size,
4307                              shdr->sh_offset, shdr->sh_size, error_callback,
4308                              data, &debugaltlink_view))
4309             goto fail;
4310
4311           debugaltlink_view_valid = 1;
4312           debugaltlink_data = (const char *) debugaltlink_view.view.data;
4313           debugaltlink_name = debugaltlink_data;
4314           debugaltlink_name_len = strnlen (debugaltlink_data, shdr->sh_size);
4315           if (debugaltlink_name_len < shdr->sh_size)
4316             {
4317               /* Include terminating zero.  */
4318               debugaltlink_name_len += 1;
4319
4320               debugaltlink_buildid_data
4321                 = debugaltlink_data + debugaltlink_name_len;
4322               debugaltlink_buildid_size = shdr->sh_size - debugaltlink_name_len;
4323             }
4324         }
4325
4326       if (!gnu_debugdata_view_valid
4327           && strcmp (name, ".gnu_debugdata") == 0)
4328         {
4329           if (!elf_get_view (state, descriptor, memory, memory_size,
4330                              shdr->sh_offset, shdr->sh_size, error_callback,
4331                              data, &gnu_debugdata_view))
4332             goto fail;
4333
4334           gnu_debugdata_size = shdr->sh_size;
4335           gnu_debugdata_view_valid = 1;
4336         }
4337
4338       /* Read the .opd section on PowerPC64 ELFv1.  */
4339       if (ehdr.e_machine == EM_PPC64
4340           && (ehdr.e_flags & EF_PPC64_ABI) < 2
4341           && shdr->sh_type == SHT_PROGBITS
4342           && strcmp (name, ".opd") == 0)
4343         {
4344           if (!elf_get_view (state, descriptor, memory, memory_size,
4345                              shdr->sh_offset, shdr->sh_size, error_callback,
4346                              data, &opd_data.view))
4347             goto fail;
4348
4349           opd = &opd_data;
4350           opd->addr = shdr->sh_addr;
4351           opd->data = (const char *) opd_data.view.view.data;
4352           opd->size = shdr->sh_size;
4353         }
4354     }
4355
4356   if (symtab_shndx == 0)
4357     symtab_shndx = dynsym_shndx;
4358   if (symtab_shndx != 0 && !debuginfo)
4359     {
4360       const b_elf_shdr *symtab_shdr;
4361       unsigned int strtab_shndx;
4362       const b_elf_shdr *strtab_shdr;
4363       struct elf_syminfo_data *sdata;
4364
4365       symtab_shdr = &shdrs[symtab_shndx - 1];
4366       strtab_shndx = symtab_shdr->sh_link;
4367       if (strtab_shndx >= shnum)
4368         {
4369           error_callback (data,
4370                           "ELF symbol table strtab link out of range", 0);
4371           goto fail;
4372         }
4373       strtab_shdr = &shdrs[strtab_shndx - 1];
4374
4375       if (!elf_get_view (state, descriptor, memory, memory_size,
4376                          symtab_shdr->sh_offset, symtab_shdr->sh_size,
4377                          error_callback, data, &symtab_view))
4378         goto fail;
4379       symtab_view_valid = 1;
4380
4381       if (!elf_get_view (state, descriptor, memory, memory_size,
4382                          strtab_shdr->sh_offset, strtab_shdr->sh_size,
4383                          error_callback, data, &strtab_view))
4384         goto fail;
4385       strtab_view_valid = 1;
4386
4387       sdata = ((struct elf_syminfo_data *)
4388                backtrace_alloc (state, sizeof *sdata, error_callback, data));
4389       if (sdata == NULL)
4390         goto fail;
4391
4392       if (!elf_initialize_syminfo (state, base_address,
4393                                    symtab_view.view.data, symtab_shdr->sh_size,
4394                                    strtab_view.view.data, strtab_shdr->sh_size,
4395                                    error_callback, data, sdata, opd))
4396         {
4397           backtrace_free (state, sdata, sizeof *sdata, error_callback, data);
4398           goto fail;
4399         }
4400
4401       /* We no longer need the symbol table, but we hold on to the
4402          string table permanently.  */
4403       elf_release_view (state, &symtab_view, error_callback, data);
4404       symtab_view_valid = 0;
4405       strtab_view_valid = 0;
4406
4407       *found_sym = 1;
4408
4409       elf_add_syminfo_data (state, sdata);
4410     }
4411
4412   elf_release_view (state, &shdrs_view, error_callback, data);
4413   shdrs_view_valid = 0;
4414   elf_release_view (state, &names_view, error_callback, data);
4415   names_view_valid = 0;
4416
4417   /* If the debug info is in a separate file, read that one instead.  */
4418
4419   if (buildid_data != NULL)
4420     {
4421       int d;
4422
4423       d = elf_open_debugfile_by_buildid (state, buildid_data, buildid_size,
4424                                          error_callback, data);
4425       if (d >= 0)
4426         {
4427           int ret;
4428
4429           elf_release_view (state, &buildid_view, error_callback, data);
4430           if (debuglink_view_valid)
4431             elf_release_view (state, &debuglink_view, error_callback, data);
4432           if (debugaltlink_view_valid)
4433             elf_release_view (state, &debugaltlink_view, error_callback, data);
4434           ret = elf_add (state, "", d, NULL, 0, base_address, error_callback,
4435                          data, fileline_fn, found_sym, found_dwarf, NULL, 0,
4436                          1, NULL, 0);
4437           if (ret < 0)
4438             backtrace_close (d, error_callback, data);
4439           else if (descriptor >= 0)
4440             backtrace_close (descriptor, error_callback, data);
4441           return ret;
4442         }
4443     }
4444
4445   if (buildid_view_valid)
4446     {
4447       elf_release_view (state, &buildid_view, error_callback, data);
4448       buildid_view_valid = 0;
4449     }
4450
4451   if (opd)
4452     {
4453       elf_release_view (state, &opd->view, error_callback, data);
4454       opd = NULL;
4455     }
4456
4457   if (debuglink_name != NULL)
4458     {
4459       int d;
4460
4461       d = elf_open_debugfile_by_debuglink (state, filename, debuglink_name,
4462                                            debuglink_crc, error_callback,
4463                                            data);
4464       if (d >= 0)
4465         {
4466           int ret;
4467
4468           elf_release_view (state, &debuglink_view, error_callback, data);
4469           if (debugaltlink_view_valid)
4470             elf_release_view (state, &debugaltlink_view, error_callback, data);
4471           ret = elf_add (state, "", d, NULL, 0, base_address, error_callback,
4472                          data, fileline_fn, found_sym, found_dwarf, NULL, 0,
4473                          1, NULL, 0);
4474           if (ret < 0)
4475             backtrace_close (d, error_callback, data);
4476           else if (descriptor >= 0)
4477             backtrace_close(descriptor, error_callback, data);
4478           return ret;
4479         }
4480     }
4481
4482   if (debuglink_view_valid)
4483     {
4484       elf_release_view (state, &debuglink_view, error_callback, data);
4485       debuglink_view_valid = 0;
4486     }
4487
4488   struct dwarf_data *fileline_altlink = NULL;
4489   if (debugaltlink_name != NULL)
4490     {
4491       int d;
4492
4493       d = elf_open_debugfile_by_debuglink (state, filename, debugaltlink_name,
4494                                            0, error_callback, data);
4495       if (d >= 0)
4496         {
4497           int ret;
4498
4499           ret = elf_add (state, filename, d, NULL, 0, base_address,
4500                          error_callback, data, fileline_fn, found_sym,
4501                          found_dwarf, &fileline_altlink, 0, 1,
4502                          debugaltlink_buildid_data, debugaltlink_buildid_size);
4503           elf_release_view (state, &debugaltlink_view, error_callback, data);
4504           debugaltlink_view_valid = 0;
4505           if (ret < 0)
4506             {
4507               backtrace_close (d, error_callback, data);
4508               return ret;
4509             }
4510         }
4511     }
4512
4513   if (debugaltlink_view_valid)
4514     {
4515       elf_release_view (state, &debugaltlink_view, error_callback, data);
4516       debugaltlink_view_valid = 0;
4517     }
4518
4519   if (gnu_debugdata_view_valid)
4520     {
4521       int ret;
4522
4523       ret = elf_uncompress_lzma (state,
4524                                  ((const unsigned char *)
4525                                   gnu_debugdata_view.view.data),
4526                                  gnu_debugdata_size, error_callback, data,
4527                                  &gnu_debugdata_uncompressed,
4528                                  &gnu_debugdata_uncompressed_size);
4529
4530       elf_release_view (state, &gnu_debugdata_view, error_callback, data);
4531       gnu_debugdata_view_valid = 0;
4532
4533       if (ret)
4534         {
4535           ret = elf_add (state, filename, -1, gnu_debugdata_uncompressed,
4536                          gnu_debugdata_uncompressed_size, base_address,
4537                          error_callback, data, fileline_fn, found_sym,
4538                          found_dwarf, NULL, 0, 0, NULL, 0);
4539           if (ret >= 0 && descriptor >= 0)
4540             backtrace_close(descriptor, error_callback, data);
4541           return ret;
4542         }
4543     }
4544
4545   /* Read all the debug sections in a single view, since they are
4546      probably adjacent in the file.  If any of sections are
4547      uncompressed, we never release this view.  */
4548
4549   min_offset = 0;
4550   max_offset = 0;
4551   debug_size = 0;
4552   for (i = 0; i < (int) DEBUG_MAX; ++i)
4553     {
4554       off_t end;
4555
4556       if (sections[i].size != 0)
4557         {
4558           if (min_offset == 0 || sections[i].offset < min_offset)
4559             min_offset = sections[i].offset;
4560           end = sections[i].offset + sections[i].size;
4561           if (end > max_offset)
4562             max_offset = end;
4563           debug_size += sections[i].size;
4564         }
4565       if (zsections[i].size != 0)
4566         {
4567           if (min_offset == 0 || zsections[i].offset < min_offset)
4568             min_offset = zsections[i].offset;
4569           end = zsections[i].offset + zsections[i].size;
4570           if (end > max_offset)
4571             max_offset = end;
4572           debug_size += zsections[i].size;
4573         }
4574     }
4575   if (min_offset == 0 || max_offset == 0)
4576     {
4577       if (descriptor >= 0)
4578         {
4579           if (!backtrace_close (descriptor, error_callback, data))
4580             goto fail;
4581         }
4582       return 1;
4583     }
4584
4585   /* If the total debug section size is large, assume that there are
4586      gaps between the sections, and read them individually.  */
4587
4588   if (max_offset - min_offset < 0x20000000
4589       || max_offset - min_offset < debug_size + 0x10000)
4590     {
4591       if (!elf_get_view (state, descriptor, memory, memory_size, min_offset,
4592                          max_offset - min_offset, error_callback, data,
4593                          &debug_view))
4594         goto fail;
4595       debug_view_valid = 1;
4596     }
4597   else
4598     {
4599       memset (&split_debug_view[0], 0, sizeof split_debug_view);
4600       for (i = 0; i < (int) DEBUG_MAX; ++i)
4601         {
4602           struct debug_section_info *dsec;
4603
4604           if (sections[i].size != 0)
4605             dsec = &sections[i];
4606           else if (zsections[i].size != 0)
4607             dsec = &zsections[i];
4608           else
4609             continue;
4610
4611           if (!elf_get_view (state, descriptor, memory, memory_size,
4612                              dsec->offset, dsec->size, error_callback, data,
4613                              &split_debug_view[i]))
4614             goto fail;
4615           split_debug_view_valid[i] = 1;
4616
4617           if (sections[i].size != 0)
4618             sections[i].data = ((const unsigned char *)
4619                                 split_debug_view[i].view.data);
4620           else
4621             zsections[i].data = ((const unsigned char *)
4622                                  split_debug_view[i].view.data);
4623         }
4624     }
4625
4626   /* We've read all we need from the executable.  */
4627   if (descriptor >= 0)
4628     {
4629       if (!backtrace_close (descriptor, error_callback, data))
4630         goto fail;
4631       descriptor = -1;
4632     }
4633
4634   using_debug_view = 0;
4635   if (debug_view_valid)
4636     {
4637       for (i = 0; i < (int) DEBUG_MAX; ++i)
4638         {
4639           if (sections[i].size == 0)
4640             sections[i].data = NULL;
4641           else
4642             {
4643               sections[i].data = ((const unsigned char *) debug_view.view.data
4644                                   + (sections[i].offset - min_offset));
4645               ++using_debug_view;
4646             }
4647
4648           if (zsections[i].size == 0)
4649             zsections[i].data = NULL;
4650           else
4651             zsections[i].data = ((const unsigned char *) debug_view.view.data
4652                                  + (zsections[i].offset - min_offset));
4653         }
4654     }
4655
4656   /* Uncompress the old format (--compress-debug-sections=zlib-gnu).  */
4657
4658   zdebug_table = NULL;
4659   for (i = 0; i < (int) DEBUG_MAX; ++i)
4660     {
4661       if (sections[i].size == 0 && zsections[i].size > 0)
4662         {
4663           unsigned char *uncompressed_data;
4664           size_t uncompressed_size;
4665
4666           if (zdebug_table == NULL)
4667             {
4668               zdebug_table = ((uint16_t *)
4669                               backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
4670                                                error_callback, data));
4671               if (zdebug_table == NULL)
4672                 goto fail;
4673             }
4674
4675           uncompressed_data = NULL;
4676           uncompressed_size = 0;
4677           if (!elf_uncompress_zdebug (state, zsections[i].data,
4678                                       zsections[i].size, zdebug_table,
4679                                       error_callback, data,
4680                                       &uncompressed_data, &uncompressed_size))
4681             goto fail;
4682           sections[i].data = uncompressed_data;
4683           sections[i].size = uncompressed_size;
4684           sections[i].compressed = 0;
4685
4686           if (split_debug_view_valid[i])
4687             {
4688               elf_release_view (state, &split_debug_view[i],
4689                                 error_callback, data);
4690               split_debug_view_valid[i] = 0;
4691             }
4692         }
4693     }
4694
4695   /* Uncompress the official ELF format
4696      (--compress-debug-sections=zlib-gabi).  */
4697   for (i = 0; i < (int) DEBUG_MAX; ++i)
4698     {
4699       unsigned char *uncompressed_data;
4700       size_t uncompressed_size;
4701
4702       if (sections[i].size == 0 || !sections[i].compressed)
4703         continue;
4704
4705       if (zdebug_table == NULL)
4706         {
4707           zdebug_table = ((uint16_t *)
4708                           backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
4709                                            error_callback, data));
4710           if (zdebug_table == NULL)
4711             goto fail;
4712         }
4713
4714       uncompressed_data = NULL;
4715       uncompressed_size = 0;
4716       if (!elf_uncompress_chdr (state, sections[i].data, sections[i].size,
4717                                 zdebug_table, error_callback, data,
4718                                 &uncompressed_data, &uncompressed_size))
4719         goto fail;
4720       sections[i].data = uncompressed_data;
4721       sections[i].size = uncompressed_size;
4722       sections[i].compressed = 0;
4723
4724       if (debug_view_valid)
4725         --using_debug_view;
4726       else if (split_debug_view_valid[i])
4727         {
4728           elf_release_view (state, &split_debug_view[i], error_callback, data);
4729           split_debug_view_valid[i] = 0;
4730         }
4731     }
4732
4733   if (zdebug_table != NULL)
4734     backtrace_free (state, zdebug_table, ZDEBUG_TABLE_SIZE,
4735                     error_callback, data);
4736
4737   if (debug_view_valid && using_debug_view == 0)
4738     {
4739       elf_release_view (state, &debug_view, error_callback, data);
4740       debug_view_valid = 0;
4741     }
4742
4743   for (i = 0; i < (int) DEBUG_MAX; ++i)
4744     {
4745       dwarf_sections.data[i] = sections[i].data;
4746       dwarf_sections.size[i] = sections[i].size;
4747     }
4748
4749   if (!backtrace_dwarf_add (state, base_address, &dwarf_sections,
4750                             ehdr.e_ident[EI_DATA] == ELFDATA2MSB,
4751                             fileline_altlink,
4752                             error_callback, data, fileline_fn,
4753                             fileline_entry))
4754     goto fail;
4755
4756   *found_dwarf = 1;
4757
4758   return 1;
4759
4760  fail:
4761   if (shdrs_view_valid)
4762     elf_release_view (state, &shdrs_view, error_callback, data);
4763   if (names_view_valid)
4764     elf_release_view (state, &names_view, error_callback, data);
4765   if (symtab_view_valid)
4766     elf_release_view (state, &symtab_view, error_callback, data);
4767   if (strtab_view_valid)
4768     elf_release_view (state, &strtab_view, error_callback, data);
4769   if (debuglink_view_valid)
4770     elf_release_view (state, &debuglink_view, error_callback, data);
4771   if (debugaltlink_view_valid)
4772     elf_release_view (state, &debugaltlink_view, error_callback, data);
4773   if (gnu_debugdata_view_valid)
4774     elf_release_view (state, &gnu_debugdata_view, error_callback, data);
4775   if (buildid_view_valid)
4776     elf_release_view (state, &buildid_view, error_callback, data);
4777   if (debug_view_valid)
4778     elf_release_view (state, &debug_view, error_callback, data);
4779   for (i = 0; i < (int) DEBUG_MAX; ++i)
4780     {
4781       if (split_debug_view_valid[i])
4782         elf_release_view (state, &split_debug_view[i], error_callback, data);
4783     }
4784   if (opd)
4785     elf_release_view (state, &opd->view, error_callback, data);
4786   if (descriptor >= 0)
4787     backtrace_close (descriptor, error_callback, data);
4788   return 0;
4789 }
4790
4791 /* Data passed to phdr_callback.  */
4792
4793 struct phdr_data
4794 {
4795   struct backtrace_state *state;
4796   backtrace_error_callback error_callback;
4797   void *data;
4798   fileline *fileline_fn;
4799   int *found_sym;
4800   int *found_dwarf;
4801   const char *exe_filename;
4802   int exe_descriptor;
4803 };
4804
4805 /* Callback passed to dl_iterate_phdr.  Load debug info from shared
4806    libraries.  */
4807
4808 static int
4809 #ifdef __i386__
4810 __attribute__ ((__force_align_arg_pointer__))
4811 #endif
4812 phdr_callback (struct dl_phdr_info *info, size_t size ATTRIBUTE_UNUSED,
4813                void *pdata)
4814 {
4815   struct phdr_data *pd = (struct phdr_data *) pdata;
4816   const char *filename;
4817   int descriptor;
4818   int does_not_exist;
4819   fileline elf_fileline_fn;
4820   int found_dwarf;
4821
4822   /* There is not much we can do if we don't have the module name,
4823      unless executable is ET_DYN, where we expect the very first
4824      phdr_callback to be for the PIE.  */
4825   if (info->dlpi_name == NULL || info->dlpi_name[0] == '\0')
4826     {
4827       if (pd->exe_descriptor == -1)
4828         return 0;
4829       filename = pd->exe_filename;
4830       descriptor = pd->exe_descriptor;
4831       pd->exe_descriptor = -1;
4832     }
4833   else
4834     {
4835       if (pd->exe_descriptor != -1)
4836         {
4837           backtrace_close (pd->exe_descriptor, pd->error_callback, pd->data);
4838           pd->exe_descriptor = -1;
4839         }
4840
4841       filename = info->dlpi_name;
4842       descriptor = backtrace_open (info->dlpi_name, pd->error_callback,
4843                                    pd->data, &does_not_exist);
4844       if (descriptor < 0)
4845         return 0;
4846     }
4847
4848   if (elf_add (pd->state, filename, descriptor, NULL, 0, info->dlpi_addr,
4849                pd->error_callback, pd->data, &elf_fileline_fn, pd->found_sym,
4850                &found_dwarf, NULL, 0, 0, NULL, 0))
4851     {
4852       if (found_dwarf)
4853         {
4854           *pd->found_dwarf = 1;
4855           *pd->fileline_fn = elf_fileline_fn;
4856         }
4857     }
4858
4859   return 0;
4860 }
4861
4862 /* Initialize the backtrace data we need from an ELF executable.  At
4863    the ELF level, all we need to do is find the debug info
4864    sections.  */
4865
4866 int
4867 backtrace_initialize (struct backtrace_state *state, const char *filename,
4868                       int descriptor, backtrace_error_callback error_callback,
4869                       void *data, fileline *fileline_fn)
4870 {
4871   int ret;
4872   int found_sym;
4873   int found_dwarf;
4874   fileline elf_fileline_fn = elf_nodebug;
4875   struct phdr_data pd;
4876
4877   ret = elf_add (state, filename, descriptor, NULL, 0, 0, error_callback, data,
4878                  &elf_fileline_fn, &found_sym, &found_dwarf, NULL, 1, 0, NULL,
4879                  0);
4880   if (!ret)
4881     return 0;
4882
4883   pd.state = state;
4884   pd.error_callback = error_callback;
4885   pd.data = data;
4886   pd.fileline_fn = &elf_fileline_fn;
4887   pd.found_sym = &found_sym;
4888   pd.found_dwarf = &found_dwarf;
4889   pd.exe_filename = filename;
4890   pd.exe_descriptor = ret < 0 ? descriptor : -1;
4891
4892   dl_iterate_phdr (phdr_callback, (void *) &pd);
4893
4894   if (!state->threaded)
4895     {
4896       if (found_sym)
4897         state->syminfo_fn = elf_syminfo;
4898       else if (state->syminfo_fn == NULL)
4899         state->syminfo_fn = elf_nosyms;
4900     }
4901   else
4902     {
4903       if (found_sym)
4904         backtrace_atomic_store_pointer (&state->syminfo_fn, elf_syminfo);
4905       else
4906         (void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
4907                                              elf_nosyms);
4908     }
4909
4910   if (!state->threaded)
4911     *fileline_fn = state->fileline_fn;
4912   else
4913     *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
4914
4915   if (*fileline_fn == NULL || *fileline_fn == elf_nodebug)
4916     *fileline_fn = elf_fileline_fn;
4917
4918   return 1;
4919 }