kernel/unwind.c

   1 /*
   2  * Copyright (C) 2002-2006 Novell, Inc.
   3  *      Jan Beulich <jbeulich@novell.com>
   4  * This code is released under version 2 of the GNU GPL.
   5  *
   6  * A simple API for unwinding kernel stacks.  This is used for
   7  * debugging and error reporting purposes.  The kernel doesn't need
   8  * full-blown stack unwinding with all the bells and whistles, so there
   9  * is not much point in implementing the full Dwarf2 unwind API.
  10  */
  11
  12 #include <linux/unwind.h>
  13 #include <linux/module.h>
  14 #include <linux/bootmem.h>
  15 #include <linux/sort.h>
  16 #include <linux/stop_machine.h>
  17 #include <linux/uaccess.h>
  18 #include <asm/sections.h>
  19 #include <asm/unaligned.h>
  20 #include <linux/slab.h>
  21
  22 extern const char __start_unwind[], __end_unwind[];
  23 extern const u8 __start_unwind_hdr[], __end_unwind_hdr[];
  24
  25 #define MAX_STACK_DEPTH 8
  26
  27 #define EXTRA_INFO(f) { \
  28                 BUILD_BUG_ON_ZERO(offsetof(struct unwind_frame_info, f) \
  29                                   % FIELD_SIZEOF(struct unwind_frame_info, f)) \
  30                 + offsetof(struct unwind_frame_info, f) \
  31                   / FIELD_SIZEOF(struct unwind_frame_info, f), \
  32                 FIELD_SIZEOF(struct unwind_frame_info, f) \
  33         }
  34 #define PTREGS_INFO(f) EXTRA_INFO(regs.f)
  35
  36 static const struct {
  37         unsigned offs:BITS_PER_LONG / 2;
  38         unsigned width:BITS_PER_LONG / 2;
  39 } reg_info[] = {
  40         UNW_REGISTER_INFO
  41 };
  42
  43 #undef PTREGS_INFO
  44 #undef EXTRA_INFO
  45
  46 #ifndef REG_INVALID
  47 #define REG_INVALID(r) (reg_info[r].width == 0)
  48 #endif
  49
  50 #define DW_CFA_nop                          0x00
  51 #define DW_CFA_set_loc                      0x01
  52 #define DW_CFA_advance_loc1                 0x02
  53 #define DW_CFA_advance_loc2                 0x03
  54 #define DW_CFA_advance_loc4                 0x04
  55 #define DW_CFA_offset_extended              0x05
  56 #define DW_CFA_restore_extended             0x06
  57 #define DW_CFA_undefined                    0x07
  58 #define DW_CFA_same_value                   0x08
  59 #define DW_CFA_register                     0x09
  60 #define DW_CFA_remember_state               0x0a
  61 #define DW_CFA_restore_state                0x0b
  62 #define DW_CFA_def_cfa                      0x0c
  63 #define DW_CFA_def_cfa_register             0x0d
  64 #define DW_CFA_def_cfa_offset               0x0e
  65 #define DW_CFA_def_cfa_expression           0x0f
  66 #define DW_CFA_expression                   0x10
  67 #define DW_CFA_offset_extended_sf           0x11
  68 #define DW_CFA_def_cfa_sf                   0x12
  69 #define DW_CFA_def_cfa_offset_sf            0x13
  70 #define DW_CFA_val_offset                   0x14
  71 #define DW_CFA_val_offset_sf                0x15
  72 #define DW_CFA_val_expression               0x16
  73 #define DW_CFA_lo_user                      0x1c
  74 #define DW_CFA_GNU_window_save              0x2d
  75 #define DW_CFA_GNU_args_size                0x2e
  76 #define DW_CFA_GNU_negative_offset_extended 0x2f
  77 #define DW_CFA_hi_user                      0x3f
  78
  79 #define DW_EH_PE_FORM     0x07
  80 #define DW_EH_PE_native   0x00
  81 #define DW_EH_PE_leb128   0x01
  82 #define DW_EH_PE_data2    0x02
  83 #define DW_EH_PE_data4    0x03
  84 #define DW_EH_PE_data8    0x04
  85 #define DW_EH_PE_signed   0x08
  86 #define DW_EH_PE_ADJUST   0x70
  87 #define DW_EH_PE_abs      0x00
  88 #define DW_EH_PE_pcrel    0x10
  89 #define DW_EH_PE_textrel  0x20
  90 #define DW_EH_PE_datarel  0x30
  91 #define DW_EH_PE_funcrel  0x40
  92 #define DW_EH_PE_aligned  0x50
  93 #define DW_EH_PE_indirect 0x80
  94 #define DW_EH_PE_omit     0xff
  95
  96 #define DW_OP_addr        0x03
  97 #define DW_OP_deref       0x06
  98 #define DW_OP_const1u     0x08
  99 #define DW_OP_const1s     0x09
 100 #define DW_OP_const2u     0x0a
 101 #define DW_OP_const2s     0x0b
 102 #define DW_OP_const4u     0x0c
 103 #define DW_OP_const4s     0x0d
 104 #define DW_OP_const8u     0x0e
 105 #define DW_OP_const8s     0x0f
 106 #define DW_OP_constu      0x10
 107 #define DW_OP_consts      0x11
 108 #define DW_OP_dup         0x12
 109 #define DW_OP_drop        0x13
 110 #define DW_OP_over        0x14
 111 #define DW_OP_pick        0x15
 112 #define DW_OP_swap        0x16
 113 #define DW_OP_rot         0x17
 114 #define DW_OP_xderef      0x18
 115 #define DW_OP_abs         0x19
 116 #define DW_OP_and         0x1a
 117 #define DW_OP_div         0x1b
 118 #define DW_OP_minus       0x1c
 119 #define DW_OP_mod         0x1d
 120 #define DW_OP_mul         0x1e
 121 #define DW_OP_neg         0x1f
 122 #define DW_OP_not         0x20
 123 #define DW_OP_or          0x21
 124 #define DW_OP_plus        0x22
 125 #define DW_OP_plus_uconst 0x23
 126 #define DW_OP_shl         0x24
 127 #define DW_OP_shr         0x25
 128 #define DW_OP_shra        0x26
 129 #define DW_OP_xor         0x27
 130 #define DW_OP_bra         0x28
 131 #define DW_OP_eq          0x29
 132 #define DW_OP_ge          0x2a
 133 #define DW_OP_gt          0x2b
 134 #define DW_OP_le          0x2c
 135 #define DW_OP_lt          0x2d
 136 #define DW_OP_ne          0x2e
 137 #define DW_OP_skip        0x2f
 138 #define DW_OP_lit0        0x30
 139 #define DW_OP_lit31       0x4f
 140 #define DW_OP_reg0        0x50
 141 #define DW_OP_reg31       0x6f
 142 #define DW_OP_breg0       0x70
 143 #define DW_OP_breg31      0x8f
 144 #define DW_OP_regx        0x90
 145 #define DW_OP_fbreg       0x91
 146 #define DW_OP_bregx       0x92
 147 #define DW_OP_piece       0x93
 148 #define DW_OP_deref_size  0x94
 149 #define DW_OP_xderef_size 0x95
 150 #define DW_OP_nop         0x96
 151
 152 typedef unsigned long uleb128_t;
 153 typedef   signed long sleb128_t;
 154 #define sleb128abs __builtin_labs
 155
 156 static struct unwind_table {
 157         struct {
 158                 unsigned long pc;
 159                 unsigned long range;
 160         } core, init;
 161         const void *address;
 162         unsigned long size;
 163         const unsigned char *header;
 164         unsigned long hdrsz;
 165         struct unwind_table *link;
 166         const char *name;
 167 } root_table;
 168
 169 struct unwind_item {
 170         enum item_location {
 171                 Nowhere,
 172                 Memory,
 173                 Register,
 174                 Value
 175         } where;
 176         uleb128_t value;
 177 };
 178
 179 struct unwind_state {
 180         uleb128_t loc, org;
 181         const u8 *cieStart, *cieEnd;
 182         uleb128_t codeAlign;
 183         sleb128_t dataAlign;
 184         struct cfa {
 185                 uleb128_t reg, offs, elen;
 186                 const u8 *expr;
 187         } cfa;
 188         struct unwind_item regs[ARRAY_SIZE(reg_info)];
 189         unsigned stackDepth:8;
 190         unsigned version:8;
 191         const u8 *label;
 192         const u8 *stack[MAX_STACK_DEPTH];
 193 };
 194
 195 static const struct cfa badCFA = { ARRAY_SIZE(reg_info), 1 };
 196
 197 static unsigned unwind_debug;
 198 static int __init unwind_debug_setup(char *s)
 199 {
 200         unwind_debug = simple_strtoul(s, NULL, 0);
 201         return 1;
 202 }
 203 __setup("unwind_debug=", unwind_debug_setup);
 204 #define dprintk(lvl, fmt, args...) \
 205         ((void)(lvl > unwind_debug \
 206          || printk(KERN_DEBUG "unwind: " fmt "\n", ##args)))
 207
 208 static struct unwind_table *find_table(unsigned long pc)
 209 {
 210         struct unwind_table *table;
 211
 212         for (table = &root_table; table; table = table->link)
 213                 if ((pc >= table->core.pc
 214                      && pc < table->core.pc + table->core.range)
 215                     || (pc >= table->init.pc
 216                         && pc < table->init.pc + table->init.range))
 217                         break;
 218
 219         return table;
 220 }
 221
 222 static unsigned long read_pointer(const u8 **pLoc,
 223                                   const void *end,
 224                                   signed ptrType,
 225                                   unsigned long text_base,
 226                                   unsigned long data_base);
 227
 228 static void init_unwind_table(struct unwind_table *table,
 229                               const char *name,
 230                               const void *core_start,
 231                               unsigned long core_size,
 232                               const void *init_start,
 233                               unsigned long init_size,
 234                               const void *table_start,
 235                               unsigned long table_size,
 236                               const u8 *header_start,
 237                               unsigned long header_size)
 238 {
 239         const u8 *ptr = header_start + 4;
 240         const u8 *end = header_start + header_size;
 241
 242         table->core.pc = (unsigned long)core_start;
 243         table->core.range = core_size;
 244         table->init.pc = (unsigned long)init_start;
 245         table->init.range = init_size;
 246         table->address = table_start;
 247         table->size = table_size;
 248         /* See if the linker provided table looks valid. */
 249         if (header_size <= 4
 250             || header_start[0] != 1
 251             || (void *)read_pointer(&ptr, end, header_start[1], 0, 0)
 252                != table_start
 253             || !read_pointer(&ptr, end, header_start[2], 0, 0)
 254             || !read_pointer(&ptr, end, header_start[3], 0,
 255                              (unsigned long)header_start)
 256             || !read_pointer(&ptr, end, header_start[3], 0,
 257                              (unsigned long)header_start))
 258                 header_start = NULL;
 259         table->hdrsz = header_size;
 260         smp_wmb();
 261         table->header = header_start;
 262         table->link = NULL;
 263         table->name = name;
 264 }
 265
 266 void __init unwind_init(void)
 267 {
 268         init_unwind_table(&root_table, "kernel",
 269                           _text, _end - _text,
 270                           NULL, 0,
 271                           __start_unwind, __end_unwind - __start_unwind,
 272                           __start_unwind_hdr, __end_unwind_hdr - __start_unwind_hdr);
 273 }
 274
 275 static const u32 bad_cie, not_fde;
 276 static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *);
 277 static signed fde_pointer_type(const u32 *cie);
 278
 279 struct eh_frame_hdr_table_entry {
 280         unsigned long start, fde;
 281 };
 282
 283 static int cmp_eh_frame_hdr_table_entries(const void *p1, const void *p2)
 284 {
 285         const struct eh_frame_hdr_table_entry *e1 = p1;
 286         const struct eh_frame_hdr_table_entry *e2 = p2;
 287
 288         return (e1->start > e2->start) - (e1->start < e2->start);
 289 }
 290
 291 static void swap_eh_frame_hdr_table_entries(void *p1, void *p2, int size)
 292 {
 293         struct eh_frame_hdr_table_entry *e1 = p1;
 294         struct eh_frame_hdr_table_entry *e2 = p2;
 295         unsigned long v;
 296
 297         v = e1->start;
 298         e1->start = e2->start;
 299         e2->start = v;
 300         v = e1->fde;
 301         e1->fde = e2->fde;
 302         e2->fde = v;
 303 }
 304
 305 static void __init setup_unwind_table(struct unwind_table *table,
 306                                         void *(*alloc)(unsigned long))
 307 {
 308         const u8 *ptr;
 309         unsigned long tableSize = table->size, hdrSize;
 310         unsigned n;
 311         const u32 *fde;
 312         struct {
 313                 u8 version;
 314                 u8 eh_frame_ptr_enc;
 315                 u8 fde_count_enc;
 316                 u8 table_enc;
 317                 unsigned long eh_frame_ptr;
 318                 unsigned int fde_count;
 319                 struct eh_frame_hdr_table_entry table[];
 320         } __attribute__((__packed__)) *header;
 321
 322         if (table->header)
 323                 return;
 324
 325         if (table->hdrsz)
 326                 printk(KERN_WARNING ".eh_frame_hdr for '%s' present but unusable\n",
 327                        table->name);
 328
 329         if (tableSize & (sizeof(*fde) - 1))
 330                 return;
 331
 332         for (fde = table->address, n = 0;
 333              tableSize > sizeof(*fde) && tableSize - sizeof(*fde) >= *fde;
 334              tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
 335                 const u32 *cie = cie_for_fde(fde, table);
 336                 signed ptrType;
 337
 338                 if (cie == &not_fde)
 339                         continue;
 340                 if (cie == NULL
 341                     || cie == &bad_cie
 342                     || (ptrType = fde_pointer_type(cie)) < 0)
 343                         return;
 344                 ptr = (const u8 *)(fde + 2);
 345                 if (!read_pointer(&ptr,
 346                                   (const u8 *)(fde + 1) + *fde,
 347                                   ptrType, 0, 0))
 348                         return;
 349                 ++n;
 350         }
 351
 352         if (tableSize || !n)
 353                 return;
 354
 355         hdrSize = 4 + sizeof(unsigned long) + sizeof(unsigned int)
 356                 + 2 * n * sizeof(unsigned long);
 357         dprintk(2, "Binary lookup table size for %s: %lu bytes", table->name, hdrSize);
 358         header = alloc(hdrSize);
 359         if (!header)
 360                 return;
 361         header->version          = 1;
 362         header->eh_frame_ptr_enc = DW_EH_PE_abs|DW_EH_PE_native;
 363         header->fde_count_enc    = DW_EH_PE_abs|DW_EH_PE_data4;
 364         header->table_enc        = DW_EH_PE_abs|DW_EH_PE_native;
 365         put_unaligned((unsigned long)table->address, &header->eh_frame_ptr);
 366         BUILD_BUG_ON(offsetof(typeof(*header), fde_count)
 367                      % __alignof(typeof(header->fde_count)));
 368         header->fde_count        = n;
 369
 370         BUILD_BUG_ON(offsetof(typeof(*header), table)
 371                      % __alignof(typeof(*header->table)));
 372         for (fde = table->address, tableSize = table->size, n = 0;
 373              tableSize;
 374              tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
 375                 const u32 *cie = fde + 1 - fde[1] / sizeof(*fde);
 376
 377                 if (!fde[1])
 378                         continue; /* this is a CIE */
 379                 ptr = (const u8 *)(fde + 2);
 380                 header->table[n].start = read_pointer(&ptr,
 381                                                       (const u8 *)(fde + 1) + *fde,
 382                                                       fde_pointer_type(cie), 0, 0);
 383                 header->table[n].fde = (unsigned long)fde;
 384                 ++n;
 385         }
 386         WARN_ON(n != header->fde_count);
 387
 388         sort(header->table,
 389              n,
 390              sizeof(*header->table),
 391              cmp_eh_frame_hdr_table_entries,
 392              swap_eh_frame_hdr_table_entries);
 393
 394         table->hdrsz = hdrSize;
 395         smp_wmb();
 396         table->header = (const void *)header;
 397 }
 398
 399 static void *__init balloc(unsigned long sz)
 400 {
 401         return __alloc_bootmem_nopanic(sz,
 402                                        sizeof(unsigned int),
 403                                        __pa(MAX_DMA_ADDRESS));
 404 }
 405
 406 void __init unwind_setup(void)
 407 {
 408         setup_unwind_table(&root_table, balloc);
 409 }
 410
 411 #ifdef CONFIG_MODULES
 412
 413 static struct unwind_table *last_table;
 414
 415 /* Must be called with module_mutex held. */
 416 void *unwind_add_table(struct module *module,
 417                        const void *table_start,
 418                        unsigned long table_size)
 419 {
 420         struct unwind_table *table;
 421
 422         if (table_size <= 0)
 423                 return NULL;
 424
 425         table = kmalloc(sizeof(*table), GFP_KERNEL);
 426         if (!table)
 427                 return NULL;
 428
 429         init_unwind_table(table, module->name,
 430                           module->module_core, module->core_size,
 431                           module->module_init, module->init_size,
 432                           table_start, table_size,
 433                           NULL, 0);
 434
 435         if (last_table)
 436                 last_table->link = table;
 437         else
 438                 root_table.link = table;
 439         last_table = table;
 440
 441         return table;
 442 }
 443
 444 struct unlink_table_info
 445 {
 446         struct unwind_table *table;
 447         int init_only;
 448 };
 449
 450 static int unlink_table(void *arg)
 451 {
 452         struct unlink_table_info *info = arg;
 453         struct unwind_table *table = info->table, *prev;
 454
 455         for (prev = &root_table; prev->link && prev->link != table; prev = prev->link)
 456                 ;
 457
 458         if (prev->link) {
 459                 if (info->init_only) {
 460                         table->init.pc = 0;
 461                         table->init.range = 0;
 462                         info->table = NULL;
 463                 } else {
 464                         prev->link = table->link;
 465                         if (!prev->link)
 466                                 last_table = prev;
 467                 }
 468         } else
 469                 info->table = NULL;
 470
 471         return 0;
 472 }
 473
 474 /* Must be called with module_mutex held. */
 475 void unwind_remove_table(void *handle, int init_only)
 476 {
 477         struct unwind_table *table = handle;
 478         struct unlink_table_info info;
 479
 480         if (!table || table == &root_table)
 481                 return;
 482
 483         if (init_only && table == last_table) {
 484                 table->init.pc = 0;
 485                 table->init.range = 0;
 486                 return;
 487         }
 488
 489         info.table = table;
 490         info.init_only = init_only;
 491         stop_machine(unlink_table, &info, NULL);
 492
 493         if (info.table)
 494                 kfree(table);
 495 }
 496
 497 #endif /* CONFIG_MODULES */
 498
 499 static uleb128_t get_uleb128(const u8 **pcur, const u8 *end)
 500 {
 501         const u8 *cur = *pcur;
 502         uleb128_t value;
 503         unsigned shift;
 504
 505         for (shift = 0, value = 0; cur < end; shift += 7) {
 506                 if (shift + 7 > 8 * sizeof(value)
 507                     && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
 508                         cur = end + 1;
 509                         break;
 510                 }
 511                 value |= (uleb128_t)(*cur & 0x7f) << shift;
 512                 if (!(*cur++ & 0x80))
 513                         break;
 514         }
 515         *pcur = cur;
 516
 517         return value;
 518 }
 519
 520 static sleb128_t get_sleb128(const u8 **pcur, const u8 *end)
 521 {
 522         const u8 *cur = *pcur;
 523         sleb128_t value;
 524         unsigned shift;
 525
 526         for (shift = 0, value = 0; cur < end; shift += 7) {
 527                 if (shift + 7 > 8 * sizeof(value)
 528                     && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
 529                         cur = end + 1;
 530                         break;
 531                 }
 532                 value |= (sleb128_t)(*cur & 0x7f) << shift;
 533                 if (!(*cur & 0x80)) {
 534                         value |= -(*cur++ & 0x40) << shift;
 535                         break;
 536                 }
 537         }
 538         *pcur = cur;
 539
 540         return value;
 541 }
 542
 543 static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *table)
 544 {
 545         const u32 *cie;
 546
 547         if (!*fde || (*fde & (sizeof(*fde) - 1)))
 548                 return &bad_cie;
 549         if (!fde[1])
 550                 return &not_fde; /* this is a CIE */
 551         if ((fde[1] & (sizeof(*fde) - 1))
 552             || fde[1] > (unsigned long)(fde + 1) - (unsigned long)table->address)
 553                 return NULL; /* this is not a valid FDE */
 554         cie = fde + 1 - fde[1] / sizeof(*fde);
 555         if (*cie <= sizeof(*cie) + 4
 556             || *cie >= fde[1] - sizeof(*fde)
 557             || (*cie & (sizeof(*cie) - 1))
 558             || cie[1])
 559                 return NULL; /* this is not a (valid) CIE */
 560         return cie;
 561 }
 562
 563 static unsigned long read_pointer(const u8 **pLoc,
 564                                   const void *end,
 565                                   signed ptrType,
 566                                   unsigned long text_base,
 567                                   unsigned long data_base)
 568 {
 569         unsigned long value = 0;
 570         union {
 571                 const u8 *p8;
 572                 const u16 *p16u;
 573                 const s16 *p16s;
 574                 const u32 *p32u;
 575                 const s32 *p32s;
 576                 const unsigned long *pul;
 577         } ptr;
 578
 579         if (ptrType < 0 || ptrType == DW_EH_PE_omit) {
 580                 dprintk(1, "Invalid pointer encoding %02X (%p,%p).", ptrType, *pLoc, end);
 581                 return 0;
 582         }
 583         ptr.p8 = *pLoc;
 584         switch (ptrType & DW_EH_PE_FORM) {
 585         case DW_EH_PE_data2:
 586                 if (end < (const void *)(ptr.p16u + 1)) {
 587                         dprintk(1, "Data16 overrun (%p,%p).", ptr.p8, end);
 588                         return 0;
 589                 }
 590                 if (ptrType & DW_EH_PE_signed)
 591                         value = get_unaligned(ptr.p16s++);
 592                 else
 593                         value = get_unaligned(ptr.p16u++);
 594                 break;
 595         case DW_EH_PE_data4:
 596 #ifdef CONFIG_64BIT
 597                 if (end < (const void *)(ptr.p32u + 1)) {
 598                         dprintk(1, "Data32 overrun (%p,%p).", ptr.p8, end);
 599                         return 0;
 600                 }
 601                 if (ptrType & DW_EH_PE_signed)
 602                         value = get_unaligned(ptr.p32s++);
 603                 else
 604                         value = get_unaligned(ptr.p32u++);
 605                 break;
 606         case DW_EH_PE_data8:
 607                 BUILD_BUG_ON(sizeof(u64) != sizeof(value));
 608 #else
 609                 BUILD_BUG_ON(sizeof(u32) != sizeof(value));
 610 #endif
 611         case DW_EH_PE_native:
 612                 if (end < (const void *)(ptr.pul + 1)) {
 613                         dprintk(1, "DataUL overrun (%p,%p).", ptr.p8, end);
 614                         return 0;
 615                 }
 616                 value = get_unaligned(ptr.pul++);
 617                 break;
 618         case DW_EH_PE_leb128:
 619                 BUILD_BUG_ON(sizeof(uleb128_t) > sizeof(value));
 620                 value = ptrType & DW_EH_PE_signed
 621                         ? get_sleb128(&ptr.p8, end)
 622                         : get_uleb128(&ptr.p8, end);
 623                 if ((const void *)ptr.p8 > end) {
 624                         dprintk(1, "DataLEB overrun (%p,%p).", ptr.p8, end);
 625                         return 0;
 626                 }
 627                 break;
 628         default:
 629                 dprintk(2, "Cannot decode pointer type %02X (%p,%p).",
 630                         ptrType, ptr.p8, end);
 631                 return 0;
 632         }
 633         switch (ptrType & DW_EH_PE_ADJUST) {
 634         case DW_EH_PE_abs:
 635                 break;
 636         case DW_EH_PE_pcrel:
 637                 value += (unsigned long)*pLoc;
 638                 break;
 639         case DW_EH_PE_textrel:
 640                 if (likely(text_base)) {
 641                         value += text_base;
 642                         break;
 643                 }
 644                 dprintk(2, "Text-relative encoding %02X (%p,%p), but zero text base.",
 645                         ptrType, *pLoc, end);
 646                 return 0;
 647         case DW_EH_PE_datarel:
 648                 if (likely(data_base)) {
 649                         value += data_base;
 650                         break;
 651                 }
 652                 dprintk(2, "Data-relative encoding %02X (%p,%p), but zero data base.",
 653                         ptrType, *pLoc, end);
 654                 return 0;
 655         default:
 656                 dprintk(2, "Cannot adjust pointer type %02X (%p,%p).",
 657                         ptrType, *pLoc, end);
 658                 return 0;
 659         }
 660         if ((ptrType & DW_EH_PE_indirect)
 661             && probe_kernel_address(value, value)) {
 662                 dprintk(1, "Cannot read indirect value %lx (%p,%p).",
 663                         value, *pLoc, end);
 664                 return 0;
 665         }
 666         *pLoc = ptr.p8;
 667
 668         return value;
 669 }
 670
 671 static signed fde_pointer_type(const u32 *cie)
 672 {
 673         const u8 *ptr = (const u8 *)(cie + 2);
 674         unsigned version = *ptr;
 675
 676         if (version != 1)
 677                 return -1; /* unsupported */
 678         if (*++ptr) {
 679                 const char *aug;
 680                 const u8 *end = (const u8 *)(cie + 1) + *cie;
 681                 uleb128_t len;
 682
 683                 /* check if augmentation size is first (and thus present) */
 684                 if (*ptr != 'z')
 685                         return -1;
 686                 /* check if augmentation string is nul-terminated */
 687                 if ((ptr = memchr(aug = (const void *)ptr, 0, end - ptr)) == NULL)
 688                         return -1;
 689                 ++ptr; /* skip terminator */
 690                 get_uleb128(&ptr, end); /* skip code alignment */
 691                 get_sleb128(&ptr, end); /* skip data alignment */
 692                 /* skip return address column */
 693                 version <= 1 ? (void)++ptr : (void)get_uleb128(&ptr, end);
 694                 len = get_uleb128(&ptr, end); /* augmentation length */
 695                 if (ptr + len < ptr || ptr + len > end)
 696                         return -1;
 697                 end = ptr + len;
 698                 while (*++aug) {
 699                         if (ptr >= end)
 700                                 return -1;
 701                         switch (*aug) {
 702                         case 'L':
 703                                 ++ptr;
 704                                 break;
 705                         case 'P': {
 706                                         signed ptrType = *ptr++;
 707
 708                                         if (!read_pointer(&ptr, end, ptrType, 0, 0)
 709                                             || ptr > end)
 710                                                 return -1;
 711                                 }
 712                                 break;
 713                         case 'R':
 714                                 return *ptr;
 715                         default:
 716                                 return -1;
 717                         }
 718                 }
 719         }
 720         return DW_EH_PE_native|DW_EH_PE_abs;
 721 }
 722
 723 static int advance_loc(unsigned long delta, struct unwind_state *state)
 724 {
 725         state->loc += delta * state->codeAlign;
 726
 727         return delta > 0;
 728 }
 729
 730 static void set_rule(uleb128_t reg,
 731                      enum item_location where,
 732                      uleb128_t value,
 733                      struct unwind_state *state)
 734 {
 735         if (reg < ARRAY_SIZE(state->regs)) {
 736                 state->regs[reg].where = where;
 737                 state->regs[reg].value = value;
 738         }
 739 }
 740
 741 static int processCFI(const u8 *start,
 742                       const u8 *end,
 743                       unsigned long targetLoc,
 744                       signed ptrType,
 745                       struct unwind_state *state)
 746 {
 747         union {
 748                 const u8 *p8;
 749                 const u16 *p16;
 750                 const u32 *p32;
 751         } ptr;
 752         int result = 1;
 753
 754         if (start != state->cieStart) {
 755                 state->loc = state->org;
 756                 result = processCFI(state->cieStart, state->cieEnd, 0, ptrType, state);
 757                 if (targetLoc == 0 && state->label == NULL)
 758                         return result;
 759         }
 760         for (ptr.p8 = start; result && ptr.p8 < end; ) {
 761                 switch (*ptr.p8 >> 6) {
 762                         uleb128_t value;
 763
 764                 case 0:
 765                         switch (*ptr.p8++) {
 766                         case DW_CFA_nop:
 767                                 break;
 768                         case DW_CFA_set_loc:
 769                                 state->loc = read_pointer(&ptr.p8, end, ptrType, 0, 0);
 770                                 if (state->loc == 0)
 771                                         result = 0;
 772                                 break;
 773                         case DW_CFA_advance_loc1:
 774                                 result = ptr.p8 < end && advance_loc(*ptr.p8++, state);
 775                                 break;
 776                         case DW_CFA_advance_loc2:
 777                                 result = ptr.p8 <= end + 2
 778                                          && advance_loc(*ptr.p16++, state);
 779                                 break;
 780                         case DW_CFA_advance_loc4:
 781                                 result = ptr.p8 <= end + 4
 782                                          && advance_loc(*ptr.p32++, state);
 783                                 break;
 784                         case DW_CFA_offset_extended:
 785                                 value = get_uleb128(&ptr.p8, end);
 786                                 set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
 787                                 break;
 788                         case DW_CFA_val_offset:
 789                                 value = get_uleb128(&ptr.p8, end);
 790                                 set_rule(value, Value, get_uleb128(&ptr.p8, end), state);
 791                                 break;
 792                         case DW_CFA_offset_extended_sf:
 793                                 value = get_uleb128(&ptr.p8, end);
 794                                 set_rule(value, Memory, get_sleb128(&ptr.p8, end), state);
 795                                 break;
 796                         case DW_CFA_val_offset_sf:
 797                                 value = get_uleb128(&ptr.p8, end);
 798                                 set_rule(value, Value, get_sleb128(&ptr.p8, end), state);
 799                                 break;
 800                         /*todo case DW_CFA_expression: */
 801                         /*todo case DW_CFA_val_expression: */
 802                         case DW_CFA_restore_extended:
 803                         case DW_CFA_undefined:
 804                         case DW_CFA_same_value:
 805                                 set_rule(get_uleb128(&ptr.p8, end), Nowhere, 0, state);
 806                                 break;
 807                         case DW_CFA_register:
 808                                 value = get_uleb128(&ptr.p8, end);
 809                                 set_rule(value,
 810                                          Register,
 811                                          get_uleb128(&ptr.p8, end), state);
 812                                 break;
 813                         case DW_CFA_remember_state:
 814                                 if (ptr.p8 == state->label) {
 815                                         state->label = NULL;
 816                                         return 1;
 817                                 }
 818                                 if (state->stackDepth >= MAX_STACK_DEPTH) {
 819                                         dprintk(1, "State stack overflow (%p,%p).", ptr.p8, end);
 820                                         return 0;
 821                                 }
 822                                 state->stack[state->stackDepth++] = ptr.p8;
 823                                 break;
 824                         case DW_CFA_restore_state:
 825                                 if (state->stackDepth) {
 826                                         const uleb128_t loc = state->loc;
 827                                         const u8 *label = state->label;
 828
 829                                         state->label = state->stack[state->stackDepth - 1];
 830                                         memcpy(&state->cfa, &badCFA, sizeof(state->cfa));
 831                                         memset(state->regs, 0, sizeof(state->regs));
 832                                         state->stackDepth = 0;
 833                                         result = processCFI(start, end, 0, ptrType, state);
 834                                         state->loc = loc;
 835                                         state->label = label;
 836                                 } else {
 837                                         dprintk(1, "State stack underflow (%p,%p).", ptr.p8, end);
 838                                         return 0;
 839                                 }
 840                                 break;
 841                         case DW_CFA_def_cfa:
 842                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 843                                 state->cfa.elen = 0;
 844                                 /*nobreak*/
 845                         case DW_CFA_def_cfa_offset:
 846                                 state->cfa.offs = get_uleb128(&ptr.p8, end);
 847                                 break;
 848                         case DW_CFA_def_cfa_sf:
 849                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 850                                 state->cfa.elen = 0;
 851                                 /*nobreak*/
 852                         case DW_CFA_def_cfa_offset_sf:
 853                                 state->cfa.offs = get_sleb128(&ptr.p8, end)
 854                                                   * state->dataAlign;
 855                                 break;
 856                         case DW_CFA_def_cfa_register:
 857                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 858                                 state->cfa.elen = 0;
 859                                 break;
 860                         case DW_CFA_def_cfa_expression:
 861                                 state->cfa.elen = get_uleb128(&ptr.p8, end);
 862                                 if (!state->cfa.elen) {
 863                                         dprintk(1, "Zero-length CFA expression.");
 864                                         return 0;
 865                                 }
 866                                 state->cfa.expr = ptr.p8;
 867                                 ptr.p8 += state->cfa.elen;
 868                                 break;
 869                         case DW_CFA_GNU_args_size:
 870                                 get_uleb128(&ptr.p8, end);
 871                                 break;
 872                         case DW_CFA_GNU_negative_offset_extended:
 873                                 value = get_uleb128(&ptr.p8, end);
 874                                 set_rule(value,
 875                                          Memory,
 876                                          (uleb128_t)0 - get_uleb128(&ptr.p8, end), state);
 877                                 break;
 878                         case DW_CFA_GNU_window_save:
 879                         default:
 880                                 dprintk(1, "Unrecognized CFI op %02X (%p,%p).", ptr.p8[-1], ptr.p8 - 1, end);
 881                                 result = 0;
 882                                 break;
 883                         }
 884                         break;
 885                 case 1:
 886                         result = advance_loc(*ptr.p8++ & 0x3f, state);
 887                         break;
 888                 case 2:
 889                         value = *ptr.p8++ & 0x3f;
 890                         set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
 891                         break;
 892                 case 3:
 893                         set_rule(*ptr.p8++ & 0x3f, Nowhere, 0, state);
 894                         break;
 895                 }
 896                 if (ptr.p8 > end) {
 897                         dprintk(1, "Data overrun (%p,%p).", ptr.p8, end);
 898                         result = 0;
 899                 }
 900                 if (result && targetLoc != 0 && targetLoc < state->loc)
 901                         return 1;
 902         }
 903
 904         if (result && ptr.p8 < end)
 905                 dprintk(1, "Data underrun (%p,%p).", ptr.p8, end);
 906
 907         return result
 908                && ptr.p8 == end
 909                && (targetLoc == 0
 910                    || (/*todo While in theory this should apply, gcc in practice omits
 911                          everything past the function prolog, and hence the location
 912                          never reaches the end of the function.
 913                        targetLoc < state->loc &&*/ state->label == NULL));
 914 }
 915
 916 static unsigned long evaluate(const u8 *expr, const u8 *end,
 917                               const struct unwind_frame_info *frame)
 918 {
 919         union {
 920                 const u8 *pu8;
 921                 const s8 *ps8;
 922                 const u16 *pu16;
 923                 const s16 *ps16;
 924                 const u32 *pu32;
 925                 const s32 *ps32;
 926                 const u64 *pu64;
 927                 const s64 *ps64;
 928         } ptr = { expr };
 929         unsigned long stack[8], val1, val2;
 930         unsigned int stidx = 0;
 931 #define PUSH(v) ({ unsigned long v__ = (v); if (stidx >= ARRAY_SIZE(stack)) return 0; stack[stidx++] = v__; })
 932 #define POP() ({ if (!stidx) return 0; stack[--stidx]; })
 933
 934         while (ptr.pu8 < end) {
 935                 switch (*ptr.pu8++) {
 936                 /*todo case DW_OP_addr: */
 937                 case DW_OP_deref:
 938                         val1 = POP();
 939                         if (probe_kernel_address(val1, val2)) {
 940                                 dprintk(1, "Cannot de-reference %lx (%p,%p).", val1, ptr.pu8 - 1, end);
 941                                 return 0;
 942                         }
 943                         PUSH(val2);
 944                         break;
 945                 /*todo? case DW_OP_xderef: */
 946                 /*todo case DW_OP_deref_size: */
 947                 /*todo? case DW_OP_xderef_size: */
 948                 case DW_OP_const1u:
 949                         if (ptr.pu8 < end)
 950                                 PUSH(*ptr.pu8);
 951                         ++ptr.pu8;
 952                         break;
 953                 case DW_OP_const1s:
 954                         if (ptr.pu8 < end)
 955                                 PUSH(*ptr.ps8);
 956                         ++ptr.ps8;
 957                         break;
 958                 case DW_OP_const2u:
 959                         if (ptr.pu8 + 1 < end)
 960                                 PUSH(*ptr.pu16);
 961                         ++ptr.pu16;
 962                         break;
 963                 case DW_OP_const2s:
 964                         if (ptr.pu8 + 1 < end)
 965                                 PUSH(*ptr.ps16);
 966                         ++ptr.ps16;
 967                         break;
 968                 case DW_OP_const4u:
 969                         if (ptr.pu8 + 3 < end)
 970                                 PUSH(*ptr.pu32);
 971                         ++ptr.pu32;
 972                         break;
 973                 case DW_OP_const4s:
 974                         if (ptr.pu8 + 3 < end)
 975                                 PUSH(*ptr.ps32);
 976                         ++ptr.ps32;
 977                         break;
 978                 case DW_OP_const8u:
 979                         if (ptr.pu8 + 7 < end)
 980                                 PUSH(*ptr.pu64);
 981                         ++ptr.pu64;
 982                         break;
 983                 case DW_OP_const8s:
 984                         if (ptr.pu8 + 7 < end)
 985                                 PUSH(*ptr.ps64);
 986                         ++ptr.ps64;
 987                         break;
 988                 case DW_OP_constu:
 989                         PUSH(get_uleb128(&ptr.pu8, end));
 990                         break;
 991                 case DW_OP_consts:
 992                         PUSH(get_sleb128(&ptr.pu8, end));
 993                         break;
 994                 case DW_OP_dup:
 995                         if (!stidx)
 996                                 return 0;
 997                         PUSH(stack[stidx - 1]);
 998                         break;
 999                 case DW_OP_drop:
1000                         (void)POP();
1001                         break;
1002                 case DW_OP_over:
1003                         if (stidx <= 1)
1004                                 return 0;
1005                         PUSH(stack[stidx - 2]);
1006                         break;
1007                 case DW_OP_pick:
1008                         if (ptr.pu8 < end) {
1009                                 if (stidx <= *ptr.pu8)
1010                                         return 0;
1011                                 PUSH(stack[stidx - *ptr.pu8 - 1]);
1012                         }
1013                         ++ptr.pu8;
1014                         break;
1015                 case DW_OP_swap:
1016                         if (stidx <= 1)
1017                                 return 0;
1018                         val1 = stack[stidx - 1];
1019                         stack[stidx - 1] = stack[stidx - 2];
1020                         stack[stidx - 2] = val1;
1021                         break;
1022                 case DW_OP_rot:
1023                         if (stidx <= 2)
1024                                 return 0;
1025                         val1 = stack[stidx - 1];
1026                         stack[stidx - 1] = stack[stidx - 2];
1027                         stack[stidx - 2] = stack[stidx - 3];
1028                         stack[stidx - 3] = val1;
1029                         break;
1030                 case DW_OP_abs:
1031                         PUSH(__builtin_labs(POP()));
1032                         break;
1033                 case DW_OP_and:
1034                         val1 = POP();
1035                         val2 = POP();
1036                         PUSH(val2 & val1);
1037                         break;
1038                 case DW_OP_div:
1039                         val1 = POP();
1040                         if (!val1)
1041                                 return 0;
1042                         val2 = POP();
1043                         PUSH(val2 / val1);
1044                         break;
1045                 case DW_OP_minus:
1046                         val1 = POP();
1047                         val2 = POP();
1048                         PUSH(val2 - val1);
1049                         break;
1050                 case DW_OP_mod:
1051                         val1 = POP();
1052                         if (!val1)
1053                                 return 0;
1054                         val2 = POP();
1055                         PUSH(val2 % val1);
1056                         break;
1057                 case DW_OP_mul:
1058                         val1 = POP();
1059                         val2 = POP();
1060                         PUSH(val2 * val1);
1061                         break;
1062                 case DW_OP_neg:
1063                         PUSH(-(long)POP());
1064                         break;
1065                 case DW_OP_not:
1066                         PUSH(~POP());
1067                         break;
1068                 case DW_OP_or:
1069                         val1 = POP();
1070                         val2 = POP();
1071                         PUSH(val2 | val1);
1072                         break;
1073                 case DW_OP_plus:
1074                         val1 = POP();
1075                         val2 = POP();
1076                         PUSH(val2 + val1);
1077                         break;
1078                 case DW_OP_plus_uconst:
1079                         PUSH(POP() + get_uleb128(&ptr.pu8, end));
1080                         break;
1081                 case DW_OP_shl:
1082                         val1 = POP();
1083                         val2 = POP();
1084                         PUSH(val1 < BITS_PER_LONG ? val2 << val1 : 0);
1085                         break;
1086                 case DW_OP_shr:
1087                         val1 = POP();
1088                         val2 = POP();
1089                         PUSH(val1 < BITS_PER_LONG ? val2 >> val1 : 0);
1090                         break;
1091                 case DW_OP_shra:
1092                         val1 = POP();
1093                         val2 = POP();
1094                         PUSH(val1 < BITS_PER_LONG ? (long)val2 >> val1 : (val2 < 0 ? -1 : 0));
1095                         break;
1096                 case DW_OP_xor:
1097                         val1 = POP();
1098                         val2 = POP();
1099                         PUSH(val2 ^ val1);
1100                         break;
1101                 case DW_OP_bra:
1102                         if (!POP()) {
1103                                 ++ptr.ps16;
1104                                 break;
1105                         }
1106                         /*nobreak*/
1107                 case DW_OP_skip:
1108                         if (ptr.pu8 + 1 < end) {
1109                                 ptr.pu8 += *ptr.ps16;
1110                                 if (ptr.pu8 < expr)
1111                                         return 0;
1112                         } else
1113                                 ++ptr.ps16;
1114                         break;
1115                 case DW_OP_eq:
1116                         val1 = POP();
1117                         val2 = POP();
1118                         PUSH(val2 == val1);
1119                         break;
1120                 case DW_OP_ne:
1121                         val1 = POP();
1122                         val2 = POP();
1123                         PUSH(val2 != val1);
1124                         break;
1125                 case DW_OP_lt:
1126                         val1 = POP();
1127                         val2 = POP();
1128                         PUSH(val2 < val1);
1129                         break;
1130                 case DW_OP_le:
1131                         val1 = POP();
1132                         val2 = POP();
1133                         PUSH(val2 <= val1);
1134                 case DW_OP_ge:
1135                         val1 = POP();
1136                         val2 = POP();
1137                         PUSH(val2 >= val1);
1138                         break;
1139                 case DW_OP_gt:
1140                         val1 = POP();
1141                         val2 = POP();
1142                         PUSH(val2 > val1);
1143                         break;
1144                 case DW_OP_lit0 ... DW_OP_lit31:
1145                         PUSH(ptr.pu8[-1] - DW_OP_lit0);
1146                         break;
1147                 case DW_OP_breg0 ... DW_OP_breg31:
1148                         val1 = ptr.pu8[-1] - DW_OP_breg0;
1149                         if (0)
1150                 case DW_OP_bregx:
1151                                 val1 = get_uleb128(&ptr.pu8, end);
1152                         if (val1 >= ARRAY_SIZE(reg_info)
1153                             || reg_info[val1].width != sizeof(unsigned long))
1154                                 return 0;
1155                         PUSH(((const unsigned long *)frame)[reg_info[val1].offs]
1156                              + get_sleb128(&ptr.pu8, end));
1157                         break;
1158                 /*todo? case DW_OP_fbreg: */
1159                 /*todo? case DW_OP_piece: */
1160                 case DW_OP_nop:
1161                         break;
1162                 default:
1163                         dprintk(1, "Unsupported expression op %02x (%p,%p).", ptr.pu8[-1], ptr.pu8 - 1, end);
1164                         return 0;
1165                 }
1166         }
1167         if (ptr.pu8 > end)
1168                 return 0;
1169         val1 = POP();
1170 #undef POP
1171 #undef PUSH
1172         return val1;
1173 }
1174
1175 /* Unwind to previous to frame.  Returns 0 if successful, negative
1176  * number in case of an error. */
1177 int unwind(struct unwind_frame_info *frame)
1178 {
1179 #define FRAME_REG(r, t) (((t *)frame)[reg_info[r].offs])
1180         const u32 *fde = NULL, *cie = NULL;
1181         const u8 *ptr = NULL, *end = NULL;
1182         unsigned long pc = UNW_PC(frame) - frame->call_frame, sp;
1183         unsigned long startLoc = 0, endLoc = 0, cfa;
1184         unsigned i;
1185         signed ptrType = -1;
1186         uleb128_t retAddrReg = 0;
1187         const struct unwind_table *table;
1188         struct unwind_state state;
1189
1190         if (UNW_PC(frame) == 0)
1191                 return -EINVAL;
1192         if ((table = find_table(pc)) != NULL
1193             && !(table->size & (sizeof(*fde) - 1))) {
1194                 const u8 *hdr = table->header;
1195                 unsigned long tableSize;
1196
1197                 smp_rmb();
1198                 if (hdr && hdr[0] == 1) {
1199                         switch (hdr[3] & DW_EH_PE_FORM) {
1200                         case DW_EH_PE_native: tableSize = sizeof(unsigned long); break;
1201                         case DW_EH_PE_data2: tableSize = 2; break;
1202                         case DW_EH_PE_data4: tableSize = 4; break;
1203                         case DW_EH_PE_data8: tableSize = 8; break;
1204                         default: tableSize = 0; break;
1205                         }
1206                         ptr = hdr + 4;
1207                         end = hdr + table->hdrsz;
1208                         if (tableSize
1209                             && read_pointer(&ptr, end, hdr[1], 0, 0)
1210                                == (unsigned long)table->address
1211                             && (i = read_pointer(&ptr, end, hdr[2], 0, 0)) > 0
1212                             && i == (end - ptr) / (2 * tableSize)
1213                             && !((end - ptr) % (2 * tableSize))) {
1214                                 do {
1215                                         const u8 *cur = ptr + (i / 2) * (2 * tableSize);
1216
1217                                         startLoc = read_pointer(&cur,
1218                                                                 cur + tableSize,
1219                                                                 hdr[3], 0,
1220                                                                 (unsigned long)hdr);
1221                                         if (pc < startLoc)
1222                                                 i /= 2;
1223                                         else {
1224                                                 ptr = cur - tableSize;
1225                                                 i = (i + 1) / 2;
1226                                         }
1227                                 } while (startLoc && i > 1);
1228                                 if (i == 1
1229                                     && (startLoc = read_pointer(&ptr,
1230                                                                 ptr + tableSize,
1231                                                                 hdr[3], 0,
1232                                                                 (unsigned long)hdr)) != 0
1233                                     && pc >= startLoc)
1234                                         fde = (void *)read_pointer(&ptr,
1235                                                                    ptr + tableSize,
1236                                                                    hdr[3], 0,
1237                                                                    (unsigned long)hdr);
1238                         }
1239                 }
1240                 if (hdr && !fde)
1241                         dprintk(3, "Binary lookup for %lx failed.", pc);
1242
1243                 if (fde != NULL) {
1244                         cie = cie_for_fde(fde, table);
1245                         ptr = (const u8 *)(fde + 2);
1246                         if (cie != NULL
1247                             && cie != &bad_cie
1248                             && cie != &not_fde
1249                             && (ptrType = fde_pointer_type(cie)) >= 0
1250                             && read_pointer(&ptr,
1251                                             (const u8 *)(fde + 1) + *fde,
1252                                             ptrType, 0, 0) == startLoc) {
1253                                 if (!(ptrType & DW_EH_PE_indirect))
1254                                         ptrType &= DW_EH_PE_FORM|DW_EH_PE_signed;
1255                                 endLoc = startLoc
1256                                          + read_pointer(&ptr,
1257                                                         (const u8 *)(fde + 1) + *fde,
1258                                                         ptrType, 0, 0);
1259                                 if (pc >= endLoc)
1260                                         fde = NULL;
1261                         } else
1262                                 fde = NULL;
1263                         if (!fde)
1264                                 dprintk(1, "Binary lookup result for %lx discarded.", pc);
1265                 }
1266                 if (fde == NULL) {
1267                         for (fde = table->address, tableSize = table->size;
1268                              cie = NULL, tableSize > sizeof(*fde)
1269                              && tableSize - sizeof(*fde) >= *fde;
1270                              tableSize -= sizeof(*fde) + *fde,
1271                              fde += 1 + *fde / sizeof(*fde)) {
1272                                 cie = cie_for_fde(fde, table);
1273                                 if (cie == &bad_cie) {
1274                                         cie = NULL;
1275                                         break;
1276                                 }
1277                                 if (cie == NULL
1278                                     || cie == &not_fde
1279                                     || (ptrType = fde_pointer_type(cie)) < 0)
1280                                         continue;
1281                                 ptr = (const u8 *)(fde + 2);
1282                                 startLoc = read_pointer(&ptr,
1283                                                         (const u8 *)(fde + 1) + *fde,
1284                                                         ptrType, 0, 0);
1285                                 if (!startLoc)
1286                                         continue;
1287                                 if (!(ptrType & DW_EH_PE_indirect))
1288                                         ptrType &= DW_EH_PE_FORM|DW_EH_PE_signed;
1289                                 endLoc = startLoc
1290                                          + read_pointer(&ptr,
1291                                                         (const u8 *)(fde + 1) + *fde,
1292                                                         ptrType, 0, 0);
1293                                 if (pc >= startLoc && pc < endLoc)
1294                                         break;
1295                         }
1296                         if (!fde)
1297                                 dprintk(3, "Linear lookup for %lx failed.", pc);
1298                 }
1299         }
1300         if (cie != NULL) {
1301                 memset(&state, 0, sizeof(state));
1302                 state.cieEnd = ptr; /* keep here temporarily */
1303                 ptr = (const u8 *)(cie + 2);
1304                 end = (const u8 *)(cie + 1) + *cie;
1305                 frame->call_frame = 1;
1306                 if ((state.version = *ptr) != 1)
1307                         cie = NULL; /* unsupported version */
1308                 else if (*++ptr) {
1309                         /* check if augmentation size is first (and thus present) */
1310                         if (*ptr == 'z') {
1311                                 while (++ptr < end && *ptr) {
1312                                         switch (*ptr) {
1313                                         /* check for ignorable (or already handled)
1314                                          * nul-terminated augmentation string */
1315                                         case 'L':
1316                                         case 'P':
1317                                         case 'R':
1318                                                 continue;
1319                                         case 'S':
1320                                                 frame->call_frame = 0;
1321                                                 continue;
1322                                         default:
1323                                                 break;
1324                                         }
1325                                         break;
1326                                 }
1327                         }
1328                         if (ptr >= end || *ptr)
1329                                 cie = NULL;
1330                 }
1331                 if (!cie)
1332                         dprintk(1, "CIE unusable (%p,%p).", ptr, end);
1333                 ++ptr;
1334         }
1335         if (cie != NULL) {
1336                 /* get code aligment factor */
1337                 state.codeAlign = get_uleb128(&ptr, end);
1338                 /* get data aligment factor */
1339                 state.dataAlign = get_sleb128(&ptr, end);
1340                 if (state.codeAlign == 0 || state.dataAlign == 0 || ptr >= end)
1341                         cie = NULL;
1342                 else if (UNW_PC(frame) % state.codeAlign
1343                          || UNW_SP(frame) % sleb128abs(state.dataAlign)) {
1344                         dprintk(1, "Input pointer(s) misaligned (%lx,%lx).",
1345                                 UNW_PC(frame), UNW_SP(frame));
1346                         return -EPERM;
1347                 } else {
1348                         retAddrReg = state.version <= 1 ? *ptr++ : get_uleb128(&ptr, end);
1349                         /* skip augmentation */
1350                         if (((const char *)(cie + 2))[1] == 'z') {
1351                                 uleb128_t augSize = get_uleb128(&ptr, end);
1352
1353                                 ptr += augSize;
1354                         }
1355                         if (ptr > end
1356                             || retAddrReg >= ARRAY_SIZE(reg_info)
1357                             || REG_INVALID(retAddrReg)
1358                             || reg_info[retAddrReg].width != sizeof(unsigned long))
1359                                 cie = NULL;
1360                 }
1361                 if (!cie)
1362                         dprintk(1, "CIE validation failed (%p,%p).", ptr, end);
1363         }
1364         if (cie != NULL) {
1365                 state.cieStart = ptr;
1366                 ptr = state.cieEnd;
1367                 state.cieEnd = end;
1368                 end = (const u8 *)(fde + 1) + *fde;
1369                 /* skip augmentation */
1370                 if (((const char *)(cie + 2))[1] == 'z') {
1371                         uleb128_t augSize = get_uleb128(&ptr, end);
1372
1373                         if ((ptr += augSize) > end)
1374                                 fde = NULL;
1375                 }
1376                 if (!fde)
1377                         dprintk(1, "FDE validation failed (%p,%p).", ptr, end);
1378         }
1379         if (cie == NULL || fde == NULL) {
1380 #ifdef CONFIG_FRAME_POINTER
1381                 unsigned long top = TSK_STACK_TOP(frame->task);
1382                 unsigned long bottom = STACK_BOTTOM(frame->task);
1383                 unsigned long fp = UNW_FP(frame);
1384                 unsigned long sp = UNW_SP(frame);
1385                 unsigned long link;
1386
1387                 if ((sp | fp) & (sizeof(unsigned long) - 1))
1388                         return -EPERM;
1389
1390 # if FRAME_RETADDR_OFFSET < 0
1391                 if (!(sp < top && fp <= sp && bottom < fp))
1392 # else
1393                 if (!(sp > top && fp >= sp && bottom > fp))
1394 # endif
1395                         return -ENXIO;
1396
1397                 if (probe_kernel_address(fp + FRAME_LINK_OFFSET, link))
1398                         return -ENXIO;
1399
1400 # if FRAME_RETADDR_OFFSET < 0
1401                 if (!(link > bottom && link < fp))
1402 # else
1403                 if (!(link < bottom && link > fp))
1404 # endif
1405                         return -ENXIO;
1406
1407                 if (link & (sizeof(link) - 1))
1408                         return -ENXIO;
1409
1410                 fp += FRAME_RETADDR_OFFSET;
1411                 if (probe_kernel_address(fp, UNW_PC(frame)))
1412                         return -ENXIO;
1413
1414                 /* Ok, we can use it */
1415 # if FRAME_RETADDR_OFFSET < 0
1416                 UNW_SP(frame) = fp - sizeof(UNW_PC(frame));
1417 # else
1418                 UNW_SP(frame) = fp + sizeof(UNW_PC(frame));
1419 # endif
1420                 UNW_FP(frame) = link;
1421                 return 0;
1422 #else
1423                 return -ENXIO;
1424 #endif
1425         }
1426         state.org = startLoc;
1427         memcpy(&state.cfa, &badCFA, sizeof(state.cfa));
1428         /* process instructions */
1429         if (!processCFI(ptr, end, pc, ptrType, &state)
1430             || state.loc > endLoc
1431             || state.regs[retAddrReg].where == Nowhere) {
1432                 dprintk(1, "Unusable unwind info (%p,%p).", ptr, end);
1433                 return -EIO;
1434         }
1435         if (state.cfa.elen) {
1436                 cfa = evaluate(state.cfa.expr, state.cfa.expr + state.cfa.elen, frame);
1437                 if (!cfa) {
1438                         dprintk(1, "Bad CFA expr (%p:%lu).", state.cfa.expr, state.cfa.elen);
1439                         return -EIO;
1440                 }
1441         } else if (state.cfa.reg >= ARRAY_SIZE(reg_info)
1442                    || reg_info[state.cfa.reg].width != sizeof(unsigned long)
1443                    || FRAME_REG(state.cfa.reg, unsigned long) % sizeof(unsigned long)
1444                    || state.cfa.offs % sizeof(unsigned long)) {
1445                 dprintk(1, "Bad CFA (%lu,%lx).", state.cfa.reg, state.cfa.offs);
1446                 return -EIO;
1447         } else
1448                 cfa = FRAME_REG(state.cfa.reg, unsigned long) + state.cfa.offs;
1449         /* update frame */
1450 #ifndef CONFIG_AS_CFI_SIGNAL_FRAME
1451         if (frame->call_frame
1452             && !UNW_DEFAULT_RA(state.regs[retAddrReg], state.dataAlign))
1453                 frame->call_frame = 0;
1454 #endif
1455         startLoc = min((unsigned long)UNW_SP(frame), cfa);
1456         endLoc = max((unsigned long)UNW_SP(frame), cfa);
1457         if (STACK_LIMIT(startLoc) != STACK_LIMIT(endLoc)) {
1458                 startLoc = min(STACK_LIMIT(cfa), cfa);
1459                 endLoc = max(STACK_LIMIT(cfa), cfa);
1460         }
1461 #ifndef CONFIG_64BIT
1462 # define CASES CASE(8); CASE(16); CASE(32)
1463 #else
1464 # define CASES CASE(8); CASE(16); CASE(32); CASE(64)
1465 #endif
1466         pc = UNW_PC(frame);
1467         sp = UNW_SP(frame);
1468         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1469                 if (REG_INVALID(i)) {
1470                         if (state.regs[i].where == Nowhere)
1471                                 continue;
1472                         dprintk(1, "Cannot restore register %u (%d).",
1473                                 i, state.regs[i].where);
1474                         return -EIO;
1475                 }
1476                 switch (state.regs[i].where) {
1477                 default:
1478                         break;
1479                 case Register:
1480                         if (state.regs[i].value >= ARRAY_SIZE(reg_info)
1481                             || REG_INVALID(state.regs[i].value)
1482                             || reg_info[i].width > reg_info[state.regs[i].value].width) {
1483                                 dprintk(1, "Cannot restore register %u from register %lu.",
1484                                         i, state.regs[i].value);
1485                                 return -EIO;
1486                         }
1487                         switch (reg_info[state.regs[i].value].width) {
1488 #define CASE(n) \
1489                         case sizeof(u##n): \
1490                                 state.regs[i].value = FRAME_REG(state.regs[i].value, \
1491                                                                 const u##n); \
1492                                 break
1493                         CASES;
1494 #undef CASE
1495                         default:
1496                                 dprintk(1, "Unsupported register size %u (%lu).",
1497                                         reg_info[state.regs[i].value].width,
1498                                         state.regs[i].value);
1499                                 return -EIO;
1500                         }
1501                         break;
1502                 }
1503         }
1504         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1505                 if (REG_INVALID(i))
1506                         continue;
1507                 switch (state.regs[i].where) {
1508                 case Nowhere:
1509                         if (reg_info[i].width != sizeof(UNW_SP(frame))
1510                             || &FRAME_REG(i, __typeof__(UNW_SP(frame)))
1511                                != &UNW_SP(frame))
1512                                 continue;
1513                         UNW_SP(frame) = cfa;
1514                         break;
1515                 case Register:
1516                         switch (reg_info[i].width) {
1517 #define CASE(n) case sizeof(u##n): \
1518                                 FRAME_REG(i, u##n) = state.regs[i].value; \
1519                                 break
1520                         CASES;
1521 #undef CASE
1522                         default:
1523                                 dprintk(1, "Unsupported register size %u (%u).",
1524                                         reg_info[i].width, i);
1525                                 return -EIO;
1526                         }
1527                         break;
1528                 case Value:
1529                         if (reg_info[i].width != sizeof(unsigned long)) {
1530                                 dprintk(1, "Unsupported value size %u (%u).",
1531                                         reg_info[i].width, i);
1532                                 return -EIO;
1533                         }
1534                         FRAME_REG(i, unsigned long) = cfa + state.regs[i].value
1535                                                             * state.dataAlign;
1536                         break;
1537                 case Memory: {
1538                                 unsigned long addr = cfa + state.regs[i].value
1539                                                            * state.dataAlign;
1540
1541                                 if ((state.regs[i].value * state.dataAlign)
1542                                     % sizeof(unsigned long)
1543                                     || addr < startLoc
1544                                     || addr + sizeof(unsigned long) < addr
1545                                     || addr + sizeof(unsigned long) > endLoc) {
1546                                         dprintk(1, "Bad memory location %lx (%lx).",
1547                                                 addr, state.regs[i].value);
1548                                         return -EIO;
1549                                 }
1550                                 switch (reg_info[i].width) {
1551 #define CASE(n)                 case sizeof(u##n): \
1552                                         if (probe_kernel_address(addr, \
1553                                                                  FRAME_REG(i, u##n))) \
1554                                                 return -EFAULT; \
1555                                         break
1556                                 CASES;
1557 #undef CASE
1558                                 default:
1559                                         dprintk(1, "Unsupported memory size %u (%u).",
1560                                                 reg_info[i].width, i);
1561                                         return -EIO;
1562                                 }
1563                         }
1564                         break;
1565                 }
1566         }
1567
1568         if (UNW_PC(frame) % state.codeAlign
1569             || UNW_SP(frame) % sleb128abs(state.dataAlign)) {
1570                 dprintk(1, "Output pointer(s) misaligned (%lx,%lx).",
1571                         UNW_PC(frame), UNW_SP(frame));
1572                 return -EIO;
1573         }
1574         if (pc == UNW_PC(frame) && sp == UNW_SP(frame)) {
1575                 dprintk(1, "No progress (%lx,%lx).", pc, sp);
1576                 return -EIO;
1577         }
1578
1579         return 0;
1580 #undef CASES
1581 #undef FRAME_REG
1582 }
1583 EXPORT_SYMBOL_GPL(unwind);
1584
1585 int unwind_init_frame_info(struct unwind_frame_info *info,
1586                            struct task_struct *tsk,
1587                            /*const*/ struct pt_regs *regs)
1588 {
1589         info->task = tsk;
1590         info->call_frame = 0;
1591         arch_unw_init_frame_info(info, regs);
1592
1593         return 0;
1594 }
1595 EXPORT_SYMBOL_GPL(unwind_init_frame_info);
1596
1597 /*
1598  * Prepare to unwind a blocked task.
1599  */
1600 int unwind_init_blocked(struct unwind_frame_info *info,
1601                         struct task_struct *tsk)
1602 {
1603         info->task = tsk;
1604         info->call_frame = 0;
1605         arch_unw_init_blocked(info);
1606
1607         return 0;
1608 }
1609 EXPORT_SYMBOL_GPL(unwind_init_blocked);
1610
1611 /*
1612  * Prepare to unwind the currently running thread.
1613  */
1614 int unwind_init_running(struct unwind_frame_info *info,
1615                         asmlinkage unwind_callback_fn callback,
1616                         const struct stacktrace_ops *ops, void *data)
1617 {
1618         info->task = current;
1619         info->call_frame = 0;
1620
1621         return arch_unwind_init_running(info, callback, ops, data);
1622 }
1623 EXPORT_SYMBOL_GPL(unwind_init_running);
1624
1625 /*
1626  * Unwind until the return pointer is in user-land (or until an error
1627  * occurs).  Returns 0 if successful, negative number in case of
1628  * error.
1629  */
1630 int unwind_to_user(struct unwind_frame_info *info)
1631 {
1632         while (!arch_unw_user_mode(info)) {
1633                 int err = unwind(info);
1634
1635                 if (err < 0)
1636                         return err;
1637         }
1638
1639         return 0;
1640 }
1641 EXPORT_SYMBOL_GPL(unwind_to_user);