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