err.no Git - linux-2.6/blob - 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/uaccess.h>
  20 #include <asm/unaligned.h>
  21
  22 extern 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 typedef unsigned long uleb128_t;
  97 typedef   signed long sleb128_t;
  98 #define sleb128abs __builtin_labs
  99
 100 static struct unwind_table {
 101         struct {
 102                 unsigned long pc;
 103                 unsigned long range;
 104         } core, init;
 105         const void *address;
 106         unsigned long size;
 107         const unsigned char *header;
 108         unsigned long hdrsz;
 109         struct unwind_table *link;
 110         const char *name;
 111 } root_table;
 112
 113 struct unwind_item {
 114         enum item_location {
 115                 Nowhere,
 116                 Memory,
 117                 Register,
 118                 Value
 119         } where;
 120         uleb128_t value;
 121 };
 122
 123 struct unwind_state {
 124         uleb128_t loc, org;
 125         const u8 *cieStart, *cieEnd;
 126         uleb128_t codeAlign;
 127         sleb128_t dataAlign;
 128         struct cfa {
 129                 uleb128_t reg, offs;
 130         } cfa;
 131         struct unwind_item regs[ARRAY_SIZE(reg_info)];
 132         unsigned stackDepth:8;
 133         unsigned version:8;
 134         const u8 *label;
 135         const u8 *stack[MAX_STACK_DEPTH];
 136 };
 137
 138 static const struct cfa badCFA = { ARRAY_SIZE(reg_info), 1 };
 139
 140 static struct unwind_table *find_table(unsigned long pc)
 141 {
 142         struct unwind_table *table;
 143
 144         for (table = &root_table; table; table = table->link)
 145                 if ((pc >= table->core.pc
 146                      && pc < table->core.pc + table->core.range)
 147                     || (pc >= table->init.pc
 148                         && pc < table->init.pc + table->init.range))
 149                         break;
 150
 151         return table;
 152 }
 153
 154 static unsigned long read_pointer(const u8 **pLoc,
 155                                   const void *end,
 156                                   signed ptrType);
 157
 158 static void init_unwind_table(struct unwind_table *table,
 159                               const char *name,
 160                               const void *core_start,
 161                               unsigned long core_size,
 162                               const void *init_start,
 163                               unsigned long init_size,
 164                               const void *table_start,
 165                               unsigned long table_size,
 166                               const u8 *header_start,
 167                               unsigned long header_size)
 168 {
 169         const u8 *ptr = header_start + 4;
 170         const u8 *end = header_start + header_size;
 171
 172         table->core.pc = (unsigned long)core_start;
 173         table->core.range = core_size;
 174         table->init.pc = (unsigned long)init_start;
 175         table->init.range = init_size;
 176         table->address = table_start;
 177         table->size = table_size;
 178         /* See if the linker provided table looks valid. */
 179         if (header_size <= 4
 180             || header_start[0] != 1
 181             || (void *)read_pointer(&ptr, end, header_start[1]) != table_start
 182             || header_start[2] == DW_EH_PE_omit
 183             || read_pointer(&ptr, end, header_start[2]) <= 0
 184             || header_start[3] == DW_EH_PE_omit)
 185                 header_start = NULL;
 186         table->hdrsz = header_size;
 187         smp_wmb();
 188         table->header = header_start;
 189         table->link = NULL;
 190         table->name = name;
 191 }
 192
 193 void __init unwind_init(void)
 194 {
 195         init_unwind_table(&root_table, "kernel",
 196                           _text, _end - _text,
 197                           NULL, 0,
 198                           __start_unwind, __end_unwind - __start_unwind,
 199                           __start_unwind_hdr, __end_unwind_hdr - __start_unwind_hdr);
 200 }
 201
 202 static const u32 bad_cie, not_fde;
 203 static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *);
 204 static signed fde_pointer_type(const u32 *cie);
 205
 206 struct eh_frame_hdr_table_entry {
 207         unsigned long start, fde;
 208 };
 209
 210 static int cmp_eh_frame_hdr_table_entries(const void *p1, const void *p2)
 211 {
 212         const struct eh_frame_hdr_table_entry *e1 = p1;
 213         const struct eh_frame_hdr_table_entry *e2 = p2;
 214
 215         return (e1->start > e2->start) - (e1->start < e2->start);
 216 }
 217
 218 static void swap_eh_frame_hdr_table_entries(void *p1, void *p2, int size)
 219 {
 220         struct eh_frame_hdr_table_entry *e1 = p1;
 221         struct eh_frame_hdr_table_entry *e2 = p2;
 222         unsigned long v;
 223
 224         v = e1->start;
 225         e1->start = e2->start;
 226         e2->start = v;
 227         v = e1->fde;
 228         e1->fde = e2->fde;
 229         e2->fde = v;
 230 }
 231
 232 static void __init setup_unwind_table(struct unwind_table *table,
 233                                         void *(*alloc)(unsigned long))
 234 {
 235         const u8 *ptr;
 236         unsigned long tableSize = table->size, hdrSize;
 237         unsigned n;
 238         const u32 *fde;
 239         struct {
 240                 u8 version;
 241                 u8 eh_frame_ptr_enc;
 242                 u8 fde_count_enc;
 243                 u8 table_enc;
 244                 unsigned long eh_frame_ptr;
 245                 unsigned int fde_count;
 246                 struct eh_frame_hdr_table_entry table[];
 247         } __attribute__((__packed__)) *header;
 248
 249         if (table->header)
 250                 return;
 251
 252         if (table->hdrsz)
 253                 printk(KERN_WARNING ".eh_frame_hdr for '%s' present but unusable\n",
 254                        table->name);
 255
 256         if (tableSize & (sizeof(*fde) - 1))
 257                 return;
 258
 259         for (fde = table->address, n = 0;
 260              tableSize > sizeof(*fde) && tableSize - sizeof(*fde) >= *fde;
 261              tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
 262                 const u32 *cie = cie_for_fde(fde, table);
 263                 signed ptrType;
 264
 265                 if (cie == &not_fde)
 266                         continue;
 267                 if (cie == NULL
 268                     || cie == &bad_cie
 269                     || (ptrType = fde_pointer_type(cie)) < 0)
 270                         return;
 271                 ptr = (const u8 *)(fde + 2);
 272                 if (!read_pointer(&ptr,
 273                                   (const u8 *)(fde + 1) + *fde,
 274                                   ptrType))
 275                         return;
 276                 ++n;
 277         }
 278
 279         if (tableSize || !n)
 280                 return;
 281
 282         hdrSize = 4 + sizeof(unsigned long) + sizeof(unsigned int)
 283                 + 2 * n * sizeof(unsigned long);
 284         header = alloc(hdrSize);
 285         if (!header)
 286                 return;
 287         header->version          = 1;
 288         header->eh_frame_ptr_enc = DW_EH_PE_abs|DW_EH_PE_native;
 289         header->fde_count_enc    = DW_EH_PE_abs|DW_EH_PE_data4;
 290         header->table_enc        = DW_EH_PE_abs|DW_EH_PE_native;
 291         put_unaligned((unsigned long)table->address, &header->eh_frame_ptr);
 292         BUILD_BUG_ON(offsetof(typeof(*header), fde_count)
 293                      % __alignof(typeof(header->fde_count)));
 294         header->fde_count        = n;
 295
 296         BUILD_BUG_ON(offsetof(typeof(*header), table)
 297                      % __alignof(typeof(*header->table)));
 298         for (fde = table->address, tableSize = table->size, n = 0;
 299              tableSize;
 300              tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
 301                 const u32 *cie = fde + 1 - fde[1] / sizeof(*fde);
 302
 303                 if (!fde[1])
 304                         continue; /* this is a CIE */
 305                 ptr = (const u8 *)(fde + 2);
 306                 header->table[n].start = read_pointer(&ptr,
 307                                                       (const u8 *)(fde + 1) + *fde,
 308                                                       fde_pointer_type(cie));
 309                 header->table[n].fde = (unsigned long)fde;
 310                 ++n;
 311         }
 312         WARN_ON(n != header->fde_count);
 313
 314         sort(header->table,
 315              n,
 316              sizeof(*header->table),
 317              cmp_eh_frame_hdr_table_entries,
 318              swap_eh_frame_hdr_table_entries);
 319
 320         table->hdrsz = hdrSize;
 321         smp_wmb();
 322         table->header = (const void *)header;
 323 }
 324
 325 static void *__init balloc(unsigned long sz)
 326 {
 327         return __alloc_bootmem_nopanic(sz,
 328                                        sizeof(unsigned int),
 329                                        __pa(MAX_DMA_ADDRESS));
 330 }
 331
 332 void __init unwind_setup(void)
 333 {
 334         setup_unwind_table(&root_table, balloc);
 335 }
 336
 337 #ifdef CONFIG_MODULES
 338
 339 static struct unwind_table *last_table;
 340
 341 /* Must be called with module_mutex held. */
 342 void *unwind_add_table(struct module *module,
 343                        const void *table_start,
 344                        unsigned long table_size)
 345 {
 346         struct unwind_table *table;
 347
 348         if (table_size <= 0)
 349                 return NULL;
 350
 351         table = kmalloc(sizeof(*table), GFP_KERNEL);
 352         if (!table)
 353                 return NULL;
 354
 355         init_unwind_table(table, module->name,
 356                           module->module_core, module->core_size,
 357                           module->module_init, module->init_size,
 358                           table_start, table_size,
 359                           NULL, 0);
 360
 361         if (last_table)
 362                 last_table->link = table;
 363         else
 364                 root_table.link = table;
 365         last_table = table;
 366
 367         return table;
 368 }
 369
 370 struct unlink_table_info
 371 {
 372         struct unwind_table *table;
 373         int init_only;
 374 };
 375
 376 static int unlink_table(void *arg)
 377 {
 378         struct unlink_table_info *info = arg;
 379         struct unwind_table *table = info->table, *prev;
 380
 381         for (prev = &root_table; prev->link && prev->link != table; prev = prev->link)
 382                 ;
 383
 384         if (prev->link) {
 385                 if (info->init_only) {
 386                         table->init.pc = 0;
 387                         table->init.range = 0;
 388                         info->table = NULL;
 389                 } else {
 390                         prev->link = table->link;
 391                         if (!prev->link)
 392                                 last_table = prev;
 393                 }
 394         } else
 395                 info->table = NULL;
 396
 397         return 0;
 398 }
 399
 400 /* Must be called with module_mutex held. */
 401 void unwind_remove_table(void *handle, int init_only)
 402 {
 403         struct unwind_table *table = handle;
 404         struct unlink_table_info info;
 405
 406         if (!table || table == &root_table)
 407                 return;
 408
 409         if (init_only && table == last_table) {
 410                 table->init.pc = 0;
 411                 table->init.range = 0;
 412                 return;
 413         }
 414
 415         info.table = table;
 416         info.init_only = init_only;
 417         stop_machine_run(unlink_table, &info, NR_CPUS);
 418
 419         if (info.table)
 420                 kfree(table);
 421 }
 422
 423 #endif /* CONFIG_MODULES */
 424
 425 static uleb128_t get_uleb128(const u8 **pcur, const u8 *end)
 426 {
 427         const u8 *cur = *pcur;
 428         uleb128_t value;
 429         unsigned shift;
 430
 431         for (shift = 0, value = 0; cur < end; shift += 7) {
 432                 if (shift + 7 > 8 * sizeof(value)
 433                     && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
 434                         cur = end + 1;
 435                         break;
 436                 }
 437                 value |= (uleb128_t)(*cur & 0x7f) << shift;
 438                 if (!(*cur++ & 0x80))
 439                         break;
 440         }
 441         *pcur = cur;
 442
 443         return value;
 444 }
 445
 446 static sleb128_t get_sleb128(const u8 **pcur, const u8 *end)
 447 {
 448         const u8 *cur = *pcur;
 449         sleb128_t value;
 450         unsigned shift;
 451
 452         for (shift = 0, value = 0; cur < end; shift += 7) {
 453                 if (shift + 7 > 8 * sizeof(value)
 454                     && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
 455                         cur = end + 1;
 456                         break;
 457                 }
 458                 value |= (sleb128_t)(*cur & 0x7f) << shift;
 459                 if (!(*cur & 0x80)) {
 460                         value |= -(*cur++ & 0x40) << shift;
 461                         break;
 462                 }
 463         }
 464         *pcur = cur;
 465
 466         return value;
 467 }
 468
 469 static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *table)
 470 {
 471         const u32 *cie;
 472
 473         if (!*fde || (*fde & (sizeof(*fde) - 1)))
 474                 return &bad_cie;
 475         if (!fde[1])
 476                 return &not_fde; /* this is a CIE */
 477         if ((fde[1] & (sizeof(*fde) - 1))
 478             || fde[1] > (unsigned long)(fde + 1) - (unsigned long)table->address)
 479                 return NULL; /* this is not a valid FDE */
 480         cie = fde + 1 - fde[1] / sizeof(*fde);
 481         if (*cie <= sizeof(*cie) + 4
 482             || *cie >= fde[1] - sizeof(*fde)
 483             || (*cie & (sizeof(*cie) - 1))
 484             || cie[1])
 485                 return NULL; /* this is not a (valid) CIE */
 486         return cie;
 487 }
 488
 489 static unsigned long read_pointer(const u8 **pLoc,
 490                                   const void *end,
 491                                   signed ptrType)
 492 {
 493         unsigned long value = 0;
 494         union {
 495                 const u8 *p8;
 496                 const u16 *p16u;
 497                 const s16 *p16s;
 498                 const u32 *p32u;
 499                 const s32 *p32s;
 500                 const unsigned long *pul;
 501         } ptr;
 502
 503         if (ptrType < 0 || ptrType == DW_EH_PE_omit)
 504                 return 0;
 505         ptr.p8 = *pLoc;
 506         switch(ptrType & DW_EH_PE_FORM) {
 507         case DW_EH_PE_data2:
 508                 if (end < (const void *)(ptr.p16u + 1))
 509                         return 0;
 510                 if(ptrType & DW_EH_PE_signed)
 511                         value = get_unaligned(ptr.p16s++);
 512                 else
 513                         value = get_unaligned(ptr.p16u++);
 514                 break;
 515         case DW_EH_PE_data4:
 516 #ifdef CONFIG_64BIT
 517                 if (end < (const void *)(ptr.p32u + 1))
 518                         return 0;
 519                 if(ptrType & DW_EH_PE_signed)
 520                         value = get_unaligned(ptr.p32s++);
 521                 else
 522                         value = get_unaligned(ptr.p32u++);
 523                 break;
 524         case DW_EH_PE_data8:
 525                 BUILD_BUG_ON(sizeof(u64) != sizeof(value));
 526 #else
 527                 BUILD_BUG_ON(sizeof(u32) != sizeof(value));
 528 #endif
 529         case DW_EH_PE_native:
 530                 if (end < (const void *)(ptr.pul + 1))
 531                         return 0;
 532                 value = get_unaligned(ptr.pul++);
 533                 break;
 534         case DW_EH_PE_leb128:
 535                 BUILD_BUG_ON(sizeof(uleb128_t) > sizeof(value));
 536                 value = ptrType & DW_EH_PE_signed
 537                         ? get_sleb128(&ptr.p8, end)
 538                         : get_uleb128(&ptr.p8, end);
 539                 if ((const void *)ptr.p8 > end)
 540                         return 0;
 541                 break;
 542         default:
 543                 return 0;
 544         }
 545         switch(ptrType & DW_EH_PE_ADJUST) {
 546         case DW_EH_PE_abs:
 547                 break;
 548         case DW_EH_PE_pcrel:
 549                 value += (unsigned long)*pLoc;
 550                 break;
 551         default:
 552                 return 0;
 553         }
 554         if ((ptrType & DW_EH_PE_indirect)
 555             && probe_kernel_address((unsigned long *)value, value))
 556                 return 0;
 557         *pLoc = ptr.p8;
 558
 559         return value;
 560 }
 561
 562 static signed fde_pointer_type(const u32 *cie)
 563 {
 564         const u8 *ptr = (const u8 *)(cie + 2);
 565         unsigned version = *ptr;
 566
 567         if (version != 1)
 568                 return -1; /* unsupported */
 569         if (*++ptr) {
 570                 const char *aug;
 571                 const u8 *end = (const u8 *)(cie + 1) + *cie;
 572                 uleb128_t len;
 573
 574                 /* check if augmentation size is first (and thus present) */
 575                 if (*ptr != 'z')
 576                         return -1;
 577                 /* check if augmentation string is nul-terminated */
 578                 if ((ptr = memchr(aug = (const void *)ptr, 0, end - ptr)) == NULL)
 579                         return -1;
 580                 ++ptr; /* skip terminator */
 581                 get_uleb128(&ptr, end); /* skip code alignment */
 582                 get_sleb128(&ptr, end); /* skip data alignment */
 583                 /* skip return address column */
 584                 version <= 1 ? (void)++ptr : (void)get_uleb128(&ptr, end);
 585                 len = get_uleb128(&ptr, end); /* augmentation length */
 586                 if (ptr + len < ptr || ptr + len > end)
 587                         return -1;
 588                 end = ptr + len;
 589                 while (*++aug) {
 590                         if (ptr >= end)
 591                                 return -1;
 592                         switch(*aug) {
 593                         case 'L':
 594                                 ++ptr;
 595                                 break;
 596                         case 'P': {
 597                                         signed ptrType = *ptr++;
 598
 599                                         if (!read_pointer(&ptr, end, ptrType) || ptr > end)
 600                                                 return -1;
 601                                 }
 602                                 break;
 603                         case 'R':
 604                                 return *ptr;
 605                         default:
 606                                 return -1;
 607                         }
 608                 }
 609         }
 610         return DW_EH_PE_native|DW_EH_PE_abs;
 611 }
 612
 613 static int advance_loc(unsigned long delta, struct unwind_state *state)
 614 {
 615         state->loc += delta * state->codeAlign;
 616
 617         return delta > 0;
 618 }
 619
 620 static void set_rule(uleb128_t reg,
 621                      enum item_location where,
 622                      uleb128_t value,
 623                      struct unwind_state *state)
 624 {
 625         if (reg < ARRAY_SIZE(state->regs)) {
 626                 state->regs[reg].where = where;
 627                 state->regs[reg].value = value;
 628         }
 629 }
 630
 631 static int processCFI(const u8 *start,
 632                       const u8 *end,
 633                       unsigned long targetLoc,
 634                       signed ptrType,
 635                       struct unwind_state *state)
 636 {
 637         union {
 638                 const u8 *p8;
 639                 const u16 *p16;
 640                 const u32 *p32;
 641         } ptr;
 642         int result = 1;
 643
 644         if (start != state->cieStart) {
 645                 state->loc = state->org;
 646                 result = processCFI(state->cieStart, state->cieEnd, 0, ptrType, state);
 647                 if (targetLoc == 0 && state->label == NULL)
 648                         return result;
 649         }
 650         for (ptr.p8 = start; result && ptr.p8 < end; ) {
 651                 switch(*ptr.p8 >> 6) {
 652                         uleb128_t value;
 653
 654                 case 0:
 655                         switch(*ptr.p8++) {
 656                         case DW_CFA_nop:
 657                                 break;
 658                         case DW_CFA_set_loc:
 659                                 if ((state->loc = read_pointer(&ptr.p8, end, ptrType)) == 0)
 660                                         result = 0;
 661                                 break;
 662                         case DW_CFA_advance_loc1:
 663                                 result = ptr.p8 < end && advance_loc(*ptr.p8++, state);
 664                                 break;
 665                         case DW_CFA_advance_loc2:
 666                                 result = ptr.p8 <= end + 2
 667                                          && advance_loc(*ptr.p16++, state);
 668                                 break;
 669                         case DW_CFA_advance_loc4:
 670                                 result = ptr.p8 <= end + 4
 671                                          && advance_loc(*ptr.p32++, state);
 672                                 break;
 673                         case DW_CFA_offset_extended:
 674                                 value = get_uleb128(&ptr.p8, end);
 675                                 set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
 676                                 break;
 677                         case DW_CFA_val_offset:
 678                                 value = get_uleb128(&ptr.p8, end);
 679                                 set_rule(value, Value, get_uleb128(&ptr.p8, end), state);
 680                                 break;
 681                         case DW_CFA_offset_extended_sf:
 682                                 value = get_uleb128(&ptr.p8, end);
 683                                 set_rule(value, Memory, get_sleb128(&ptr.p8, end), state);
 684                                 break;
 685                         case DW_CFA_val_offset_sf:
 686                                 value = get_uleb128(&ptr.p8, end);
 687                                 set_rule(value, Value, get_sleb128(&ptr.p8, end), state);
 688                                 break;
 689                         case DW_CFA_restore_extended:
 690                         case DW_CFA_undefined:
 691                         case DW_CFA_same_value:
 692                                 set_rule(get_uleb128(&ptr.p8, end), Nowhere, 0, state);
 693                                 break;
 694                         case DW_CFA_register:
 695                                 value = get_uleb128(&ptr.p8, end);
 696                                 set_rule(value,
 697                                          Register,
 698                                          get_uleb128(&ptr.p8, end), state);
 699                                 break;
 700                         case DW_CFA_remember_state:
 701                                 if (ptr.p8 == state->label) {
 702                                         state->label = NULL;
 703                                         return 1;
 704                                 }
 705                                 if (state->stackDepth >= MAX_STACK_DEPTH)
 706                                         return 0;
 707                                 state->stack[state->stackDepth++] = ptr.p8;
 708                                 break;
 709                         case DW_CFA_restore_state:
 710                                 if (state->stackDepth) {
 711                                         const uleb128_t loc = state->loc;
 712                                         const u8 *label = state->label;
 713
 714                                         state->label = state->stack[state->stackDepth - 1];
 715                                         memcpy(&state->cfa, &badCFA, sizeof(state->cfa));
 716                                         memset(state->regs, 0, sizeof(state->regs));
 717                                         state->stackDepth = 0;
 718                                         result = processCFI(start, end, 0, ptrType, state);
 719                                         state->loc = loc;
 720                                         state->label = label;
 721                                 } else
 722                                         return 0;
 723                                 break;
 724                         case DW_CFA_def_cfa:
 725                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 726                                 /*nobreak*/
 727                         case DW_CFA_def_cfa_offset:
 728                                 state->cfa.offs = get_uleb128(&ptr.p8, end);
 729                                 break;
 730                         case DW_CFA_def_cfa_sf:
 731                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 732                                 /*nobreak*/
 733                         case DW_CFA_def_cfa_offset_sf:
 734                                 state->cfa.offs = get_sleb128(&ptr.p8, end)
 735                                                   * state->dataAlign;
 736                                 break;
 737                         case DW_CFA_def_cfa_register:
 738                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 739                                 break;
 740                         /*todo case DW_CFA_def_cfa_expression: */
 741                         /*todo case DW_CFA_expression: */
 742                         /*todo case DW_CFA_val_expression: */
 743                         case DW_CFA_GNU_args_size:
 744                                 get_uleb128(&ptr.p8, end);
 745                                 break;
 746                         case DW_CFA_GNU_negative_offset_extended:
 747                                 value = get_uleb128(&ptr.p8, end);
 748                                 set_rule(value,
 749                                          Memory,
 750                                          (uleb128_t)0 - get_uleb128(&ptr.p8, end), state);
 751                                 break;
 752                         case DW_CFA_GNU_window_save:
 753                         default:
 754                                 result = 0;
 755                                 break;
 756                         }
 757                         break;
 758                 case 1:
 759                         result = advance_loc(*ptr.p8++ & 0x3f, state);
 760                         break;
 761                 case 2:
 762                         value = *ptr.p8++ & 0x3f;
 763                         set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
 764                         break;
 765                 case 3:
 766                         set_rule(*ptr.p8++ & 0x3f, Nowhere, 0, state);
 767                         break;
 768                 }
 769                 if (ptr.p8 > end)
 770                         result = 0;
 771                 if (result && targetLoc != 0 && targetLoc < state->loc)
 772                         return 1;
 773         }
 774
 775         return result
 776            && ptr.p8 == end
 777            && (targetLoc == 0
 778             || (/*todo While in theory this should apply, gcc in practice omits
 779                   everything past the function prolog, and hence the location
 780                   never reaches the end of the function.
 781                 targetLoc < state->loc &&*/ state->label == NULL));
 782 }
 783
 784 /* Unwind to previous to frame.  Returns 0 if successful, negative
 785  * number in case of an error. */
 786 int unwind(struct unwind_frame_info *frame)
 787 {
 788 #define FRAME_REG(r, t) (((t *)frame)[reg_info[r].offs])
 789         const u32 *fde = NULL, *cie = NULL;
 790         const u8 *ptr = NULL, *end = NULL;
 791         unsigned long pc = UNW_PC(frame) - frame->call_frame, sp;
 792         unsigned long startLoc = 0, endLoc = 0, cfa;
 793         unsigned i;
 794         signed ptrType = -1;
 795         uleb128_t retAddrReg = 0;
 796         const struct unwind_table *table;
 797         struct unwind_state state;
 798
 799         if (UNW_PC(frame) == 0)
 800                 return -EINVAL;
 801         if ((table = find_table(pc)) != NULL
 802             && !(table->size & (sizeof(*fde) - 1))) {
 803                 const u8 *hdr = table->header;
 804                 unsigned long tableSize;
 805
 806                 smp_rmb();
 807                 if (hdr && hdr[0] == 1) {
 808                         switch(hdr[3] & DW_EH_PE_FORM) {
 809                         case DW_EH_PE_native: tableSize = sizeof(unsigned long); break;
 810                         case DW_EH_PE_data2: tableSize = 2; break;
 811                         case DW_EH_PE_data4: tableSize = 4; break;
 812                         case DW_EH_PE_data8: tableSize = 8; break;
 813                         default: tableSize = 0; break;
 814                         }
 815                         ptr = hdr + 4;
 816                         end = hdr + table->hdrsz;
 817                         if (tableSize
 818                             && read_pointer(&ptr, end, hdr[1])
 819                                == (unsigned long)table->address
 820                             && (i = read_pointer(&ptr, end, hdr[2])) > 0
 821                             && i == (end - ptr) / (2 * tableSize)
 822                             && !((end - ptr) % (2 * tableSize))) {
 823                                 do {
 824                                         const u8 *cur = ptr + (i / 2) * (2 * tableSize);
 825
 826                                         startLoc = read_pointer(&cur,
 827                                                                 cur + tableSize,
 828                                                                 hdr[3]);
 829                                         if (pc < startLoc)
 830                                                 i /= 2;
 831                                         else {
 832                                                 ptr = cur - tableSize;
 833                                                 i = (i + 1) / 2;
 834                                         }
 835                                 } while (startLoc && i > 1);
 836                                 if (i == 1
 837                                     && (startLoc = read_pointer(&ptr,
 838                                                                 ptr + tableSize,
 839                                                                 hdr[3])) != 0
 840                                     && pc >= startLoc)
 841                                         fde = (void *)read_pointer(&ptr,
 842                                                                    ptr + tableSize,
 843                                                                    hdr[3]);
 844                         }
 845                 }
 846
 847                 if (fde != NULL) {
 848                         cie = cie_for_fde(fde, table);
 849                         ptr = (const u8 *)(fde + 2);
 850                         if(cie != NULL
 851                            && cie != &bad_cie
 852                            && cie != &not_fde
 853                            && (ptrType = fde_pointer_type(cie)) >= 0
 854                            && read_pointer(&ptr,
 855                                            (const u8 *)(fde + 1) + *fde,
 856                                            ptrType) == startLoc) {
 857                                 if (!(ptrType & DW_EH_PE_indirect))
 858                                         ptrType &= DW_EH_PE_FORM|DW_EH_PE_signed;
 859                                 endLoc = startLoc
 860                                          + read_pointer(&ptr,
 861                                                         (const u8 *)(fde + 1) + *fde,
 862                                                         ptrType);
 863                                 if(pc >= endLoc)
 864                                         fde = NULL;
 865                         } else
 866                                 fde = NULL;
 867                 }
 868                 if (fde == NULL) {
 869                         for (fde = table->address, tableSize = table->size;
 870                              cie = NULL, tableSize > sizeof(*fde)
 871                              && tableSize - sizeof(*fde) >= *fde;
 872                              tableSize -= sizeof(*fde) + *fde,
 873                              fde += 1 + *fde / sizeof(*fde)) {
 874                                 cie = cie_for_fde(fde, table);
 875                                 if (cie == &bad_cie) {
 876                                         cie = NULL;
 877                                         break;
 878                                 }
 879                                 if (cie == NULL
 880                                     || cie == &not_fde
 881                                     || (ptrType = fde_pointer_type(cie)) < 0)
 882                                         continue;
 883                                 ptr = (const u8 *)(fde + 2);
 884                                 startLoc = read_pointer(&ptr,
 885                                                         (const u8 *)(fde + 1) + *fde,
 886                                                         ptrType);
 887                                 if (!startLoc)
 888                                         continue;
 889                                 if (!(ptrType & DW_EH_PE_indirect))
 890                                         ptrType &= DW_EH_PE_FORM|DW_EH_PE_signed;
 891                                 endLoc = startLoc
 892                                          + read_pointer(&ptr,
 893                                                         (const u8 *)(fde + 1) + *fde,
 894                                                         ptrType);
 895                                 if (pc >= startLoc && pc < endLoc)
 896                                         break;
 897                         }
 898                 }
 899         }
 900         if (cie != NULL) {
 901                 memset(&state, 0, sizeof(state));
 902                 state.cieEnd = ptr; /* keep here temporarily */
 903                 ptr = (const u8 *)(cie + 2);
 904                 end = (const u8 *)(cie + 1) + *cie;
 905                 frame->call_frame = 1;
 906                 if ((state.version = *ptr) != 1)
 907                         cie = NULL; /* unsupported version */
 908                 else if (*++ptr) {
 909                         /* check if augmentation size is first (and thus present) */
 910                         if (*ptr == 'z') {
 911                                 while (++ptr < end && *ptr) {
 912                                         switch(*ptr) {
 913                                         /* check for ignorable (or already handled)
 914                                          * nul-terminated augmentation string */
 915                                         case 'L':
 916                                         case 'P':
 917                                         case 'R':
 918                                                 continue;
 919                                         case 'S':
 920                                                 frame->call_frame = 0;
 921                                                 continue;
 922                                         default:
 923                                                 break;
 924                                         }
 925                                         break;
 926                                 }
 927                         }
 928                         if (ptr >= end || *ptr)
 929                                 cie = NULL;
 930                 }
 931                 ++ptr;
 932         }
 933         if (cie != NULL) {
 934                 /* get code aligment factor */
 935                 state.codeAlign = get_uleb128(&ptr, end);
 936                 /* get data aligment factor */
 937                 state.dataAlign = get_sleb128(&ptr, end);
 938                 if (state.codeAlign == 0 || state.dataAlign == 0 || ptr >= end)
 939                         cie = NULL;
 940                 else if (UNW_PC(frame) % state.codeAlign
 941                          || UNW_SP(frame) % sleb128abs(state.dataAlign))
 942                         return -EPERM;
 943                 else {
 944                         retAddrReg = state.version <= 1 ? *ptr++ : get_uleb128(&ptr, end);
 945                         /* skip augmentation */
 946                         if (((const char *)(cie + 2))[1] == 'z') {
 947                                 uleb128_t augSize = get_uleb128(&ptr, end);
 948
 949                                 ptr += augSize;
 950                         }
 951                         if (ptr > end
 952                            || retAddrReg >= ARRAY_SIZE(reg_info)
 953                            || REG_INVALID(retAddrReg)
 954                            || reg_info[retAddrReg].width != sizeof(unsigned long))
 955                                 cie = NULL;
 956                 }
 957         }
 958         if (cie != NULL) {
 959                 state.cieStart = ptr;
 960                 ptr = state.cieEnd;
 961                 state.cieEnd = end;
 962                 end = (const u8 *)(fde + 1) + *fde;
 963                 /* skip augmentation */
 964                 if (((const char *)(cie + 2))[1] == 'z') {
 965                         uleb128_t augSize = get_uleb128(&ptr, end);
 966
 967                         if ((ptr += augSize) > end)
 968                                 fde = NULL;
 969                 }
 970         }
 971         if (cie == NULL || fde == NULL) {
 972 #ifdef CONFIG_FRAME_POINTER
 973                 unsigned long top, bottom;
 974
 975                 if ((UNW_SP(frame) | UNW_FP(frame)) % sizeof(unsigned long))
 976                         return -EPERM;
 977                 top = STACK_TOP(frame->task);
 978                 bottom = STACK_BOTTOM(frame->task);
 979 # if FRAME_RETADDR_OFFSET < 0
 980                 if (UNW_SP(frame) < top
 981                     && UNW_FP(frame) <= UNW_SP(frame)
 982                     && bottom < UNW_FP(frame)
 983 # else
 984                 if (UNW_SP(frame) > top
 985                     && UNW_FP(frame) >= UNW_SP(frame)
 986                     && bottom > UNW_FP(frame)
 987 # endif
 988                    && !((UNW_SP(frame) | UNW_FP(frame))
 989                         & (sizeof(unsigned long) - 1))) {
 990                         unsigned long link;
 991
 992                         if (!probe_kernel_address(
 993                                         (unsigned long *)(UNW_FP(frame)
 994                                                           + FRAME_LINK_OFFSET),
 995                                                   link)
 996 # if FRAME_RETADDR_OFFSET < 0
 997                            && link > bottom && link < UNW_FP(frame)
 998 # else
 999                            && link > UNW_FP(frame) && link < bottom
1000 # endif
1001                            && !(link & (sizeof(link) - 1))
1002                            && !probe_kernel_address(
1003                                           (unsigned long *)(UNW_FP(frame)
1004                                                             + FRAME_RETADDR_OFFSET), UNW_PC(frame))) {
1005                                 UNW_SP(frame) = UNW_FP(frame) + FRAME_RETADDR_OFFSET
1006 # if FRAME_RETADDR_OFFSET < 0
1007                                         -
1008 # else
1009                                         +
1010 # endif
1011                                           sizeof(UNW_PC(frame));
1012                                 UNW_FP(frame) = link;
1013                                 return 0;
1014                         }
1015                 }
1016 #endif
1017                 return -ENXIO;
1018         }
1019         state.org = startLoc;
1020         memcpy(&state.cfa, &badCFA, sizeof(state.cfa));
1021         /* process instructions */
1022         if (!processCFI(ptr, end, pc, ptrType, &state)
1023            || state.loc > endLoc
1024            || state.regs[retAddrReg].where == Nowhere
1025            || state.cfa.reg >= ARRAY_SIZE(reg_info)
1026            || reg_info[state.cfa.reg].width != sizeof(unsigned long)
1027            || FRAME_REG(state.cfa.reg, unsigned long) % sizeof(unsigned long)
1028            || state.cfa.offs % sizeof(unsigned long))
1029                 return -EIO;
1030         /* update frame */
1031 #ifndef CONFIG_AS_CFI_SIGNAL_FRAME
1032         if(frame->call_frame
1033            && !UNW_DEFAULT_RA(state.regs[retAddrReg], state.dataAlign))
1034                 frame->call_frame = 0;
1035 #endif
1036         cfa = FRAME_REG(state.cfa.reg, unsigned long) + state.cfa.offs;
1037         startLoc = min((unsigned long)UNW_SP(frame), cfa);
1038         endLoc = max((unsigned long)UNW_SP(frame), cfa);
1039         if (STACK_LIMIT(startLoc) != STACK_LIMIT(endLoc)) {
1040                 startLoc = min(STACK_LIMIT(cfa), cfa);
1041                 endLoc = max(STACK_LIMIT(cfa), cfa);
1042         }
1043 #ifndef CONFIG_64BIT
1044 # define CASES CASE(8); CASE(16); CASE(32)
1045 #else
1046 # define CASES CASE(8); CASE(16); CASE(32); CASE(64)
1047 #endif
1048         pc = UNW_PC(frame);
1049         sp = UNW_SP(frame);
1050         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1051                 if (REG_INVALID(i)) {
1052                         if (state.regs[i].where == Nowhere)
1053                                 continue;
1054                         return -EIO;
1055                 }
1056                 switch(state.regs[i].where) {
1057                 default:
1058                         break;
1059                 case Register:
1060                         if (state.regs[i].value >= ARRAY_SIZE(reg_info)
1061                            || REG_INVALID(state.regs[i].value)
1062                            || reg_info[i].width > reg_info[state.regs[i].value].width)
1063                                 return -EIO;
1064                         switch(reg_info[state.regs[i].value].width) {
1065 #define CASE(n) \
1066                         case sizeof(u##n): \
1067                                 state.regs[i].value = FRAME_REG(state.regs[i].value, \
1068                                                                 const u##n); \
1069                                 break
1070                         CASES;
1071 #undef CASE
1072                         default:
1073                                 return -EIO;
1074                         }
1075                         break;
1076                 }
1077         }
1078         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1079                 if (REG_INVALID(i))
1080                         continue;
1081                 switch(state.regs[i].where) {
1082                 case Nowhere:
1083                         if (reg_info[i].width != sizeof(UNW_SP(frame))
1084                            || &FRAME_REG(i, __typeof__(UNW_SP(frame)))
1085                               != &UNW_SP(frame))
1086                                 continue;
1087                         UNW_SP(frame) = cfa;
1088                         break;
1089                 case Register:
1090                         switch(reg_info[i].width) {
1091 #define CASE(n) case sizeof(u##n): \
1092                                 FRAME_REG(i, u##n) = state.regs[i].value; \
1093                                 break
1094                         CASES;
1095 #undef CASE
1096                         default:
1097                                 return -EIO;
1098                         }
1099                         break;
1100                 case Value:
1101                         if (reg_info[i].width != sizeof(unsigned long))
1102                                 return -EIO;
1103                         FRAME_REG(i, unsigned long) = cfa + state.regs[i].value
1104                                                             * state.dataAlign;
1105                         break;
1106                 case Memory: {
1107                                 unsigned long addr = cfa + state.regs[i].value
1108                                                            * state.dataAlign;
1109
1110                                 if ((state.regs[i].value * state.dataAlign)
1111                                     % sizeof(unsigned long)
1112                                     || addr < startLoc
1113                                     || addr + sizeof(unsigned long) < addr
1114                                     || addr + sizeof(unsigned long) > endLoc)
1115                                         return -EIO;
1116                                 switch(reg_info[i].width) {
1117 #define CASE(n)     case sizeof(u##n): \
1118                                         probe_kernel_address((u##n *)addr, FRAME_REG(i, u##n)); \
1119                                         break
1120                                 CASES;
1121 #undef CASE
1122                                 default:
1123                                         return -EIO;
1124                                 }
1125                         }
1126                         break;
1127                 }
1128         }
1129
1130         if (UNW_PC(frame) % state.codeAlign
1131             || UNW_SP(frame) % sleb128abs(state.dataAlign)
1132             || (pc == UNW_PC(frame) && sp == UNW_SP(frame)))
1133                 return -EIO;
1134
1135         return 0;
1136 #undef CASES
1137 #undef FRAME_REG
1138 }
1139 EXPORT_SYMBOL(unwind);
1140
1141 int unwind_init_frame_info(struct unwind_frame_info *info,
1142                            struct task_struct *tsk,
1143                            /*const*/ struct pt_regs *regs)
1144 {
1145         info->task = tsk;
1146         info->call_frame = 0;
1147         arch_unw_init_frame_info(info, regs);
1148
1149         return 0;
1150 }
1151 EXPORT_SYMBOL(unwind_init_frame_info);
1152
1153 /*
1154  * Prepare to unwind a blocked task.
1155  */
1156 int unwind_init_blocked(struct unwind_frame_info *info,
1157                         struct task_struct *tsk)
1158 {
1159         info->task = tsk;
1160         info->call_frame = 0;
1161         arch_unw_init_blocked(info);
1162
1163         return 0;
1164 }
1165 EXPORT_SYMBOL(unwind_init_blocked);
1166
1167 /*
1168  * Prepare to unwind the currently running thread.
1169  */
1170 int unwind_init_running(struct unwind_frame_info *info,
1171                         asmlinkage int (*callback)(struct unwind_frame_info *,
1172                                                    void *arg),
1173                         void *arg)
1174 {
1175         info->task = current;
1176         info->call_frame = 0;
1177
1178         return arch_unwind_init_running(info, callback, arg);
1179 }
1180 EXPORT_SYMBOL(unwind_init_running);
1181
1182 /*
1183  * Unwind until the return pointer is in user-land (or until an error
1184  * occurs).  Returns 0 if successful, negative number in case of
1185  * error.
1186  */
1187 int unwind_to_user(struct unwind_frame_info *info)
1188 {
1189         while (!arch_unw_user_mode(info)) {
1190                 int err = unwind(info);
1191
1192                 if (err < 0)
1193                         return err;
1194         }
1195
1196         return 0;
1197 }
1198 EXPORT_SYMBOL(unwind_to_user);