runtime/unwind.c

   1 /* -*- linux-c -*-
   2  * kernel stack unwinding
   3  * Copyright (C) 2008-2009 Red Hat Inc.
   4  *
   5  * Based on old kernel code that is
   6  * Copyright (C) 2002-2006 Novell, Inc.
   7  *      Jan Beulich <jbeulich@novell.com>
   8  *
   9  * This code is released under version 2 of the GNU GPL.
  10  *
  11  * This code currently does stack unwinding in the kernel and modules.
  12  * It has been extended to handle userspace unwinding using systemtap
  13  * data structures.
  14  */
  15
  16 #include "unwind/unwind.h"
  17
  18 #ifdef STP_USE_DWARF_UNWINDER
  19
  20 struct eh_frame_hdr_table_entry {
  21         unsigned long start, fde;
  22 };
  23
  24 static int cmp_eh_frame_hdr_table_entries(const void *p1, const void *p2)
  25 {
  26         const struct eh_frame_hdr_table_entry *e1 = p1;
  27         const struct eh_frame_hdr_table_entry *e2 = p2;
  28         return (e1->start > e2->start) - (e1->start < e2->start);
  29 }
  30
  31 static void swap_eh_frame_hdr_table_entries(void *p1, void *p2, int size)
  32 {
  33         struct eh_frame_hdr_table_entry *e1 = p1;
  34         struct eh_frame_hdr_table_entry *e2 = p2;
  35         unsigned long v;
  36
  37         v = e1->start;
  38         e1->start = e2->start;
  39         e2->start = v;
  40         v = e1->fde;
  41         e1->fde = e2->fde;
  42         e2->fde = v;
  43 }
  44
  45 static uleb128_t get_uleb128(const u8 **pcur, const u8 *end)
  46 {
  47         const u8 *cur = *pcur;
  48         uleb128_t value = 0;
  49         unsigned shift;
  50
  51         for (shift = 0; cur < end; shift += 7) {
  52                 if (shift + 7 > 8 * sizeof(value)
  53                     && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
  54                         cur = end + 1;
  55                         break;
  56                 }
  57                 value |= (uleb128_t)(*cur & 0x7f) << shift;
  58                 if (!(*cur++ & 0x80))
  59                         break;
  60         }
  61         *pcur = cur;
  62
  63         return value;
  64 }
  65
  66 static sleb128_t get_sleb128(const u8 **pcur, const u8 *end)
  67 {
  68         const u8 *cur = *pcur;
  69         sleb128_t value = 0;
  70         unsigned shift;
  71
  72         for (shift = 0; cur < end; shift += 7) {
  73                 if (shift + 7 > 8 * sizeof(value)
  74                     && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
  75                         cur = end + 1;
  76                         break;
  77                 }
  78                 value |= (sleb128_t)(*cur & 0x7f) << shift;
  79                 if (!(*cur & 0x80)) {
  80                         value |= -(*cur++ & 0x40) << shift;
  81                         break;
  82                 }
  83         }
  84         *pcur = cur;
  85
  86         return value;
  87 }
  88
  89 /* given an FDE, find its CIE */
  90 static const u32 *cie_for_fde(const u32 *fde, void *unwind_data,
  91                               uint32_t table_len, int is_ehframe)
  92 {
  93         const u32 *cie;
  94
  95         /* check that length is proper */
  96         if (!*fde || (*fde & (sizeof(*fde) - 1)))
  97                 return &bad_cie;
  98
  99         /* CIE id for eh_frame is 0, otherwise 0xffffffff */
 100         if (is_ehframe && fde[1] == 0)
 101                 return &not_fde;
 102         else if (fde[1] == 0xffffffff)
 103                 return &not_fde;
 104
 105         /* OK, must be an FDE.  Now find its CIE. */
 106
 107         /* CIE_pointer must be a proper offset */
 108         if ((fde[1] & (sizeof(*fde) - 1)) || fde[1] > (unsigned long)(fde + 1) - (unsigned long)unwind_data) {
 109                 dbug_unwind(1, "fde[1]=%lx fde+1=%lx, unwind_data=%lx  %lx\n",
 110                             (unsigned long)fde[1], (unsigned long)(fde + 1),
 111                             (unsigned long)unwind_data, (unsigned long)(fde + 1) - (unsigned long)unwind_data);
 112                 return NULL;    /* this is not a valid FDE */
 113         }
 114
 115         /* cie pointer field is different in eh_frame vs debug_frame */
 116         if (is_ehframe)
 117                 cie = fde + 1 - fde[1] / sizeof(*fde);
 118         else
 119                 cie = unwind_data + fde[1];
 120
 121         /* Make sure address falls in the table */
 122         if (((void *)cie) < ((void*)unwind_data)
 123             || ((void*)cie) > ((void*)(unwind_data + table_len)))
 124           return NULL;
 125
 126         if (*cie <= sizeof(*cie) + 4 || *cie >= fde[1] - sizeof(*fde)
 127             || (*cie & (sizeof(*cie) - 1))
 128             || (cie[1] != 0xffffffff && cie[1] != 0)) {
 129                 dbug_unwind(1, "cie is not valid %lx %x %x %x\n", (unsigned long)cie, *cie, fde[1], cie[1]);
 130                 return NULL;    /* this is not a (valid) CIE */
 131         }
 132
 133         return cie;
 134 }
 135
 136 /* read an encoded pointer */
 137 static unsigned long read_pointer(const u8 **pLoc, const void *end, signed ptrType)
 138 {
 139         unsigned long value = 0;
 140         union {
 141                 const u8 *p8;
 142                 const u16 *p16u;
 143                 const s16 *p16s;
 144                 const u32 *p32u;
 145                 const s32 *p32s;
 146                 const unsigned long *pul;
 147         } ptr;
 148
 149         if (ptrType < 0 || ptrType == DW_EH_PE_omit)
 150                 return 0;
 151
 152         ptr.p8 = *pLoc;
 153         switch (ptrType & DW_EH_PE_FORM) {
 154         case DW_EH_PE_data2:
 155                 if (end < (const void *)(ptr.p16u + 1))
 156                         return 0;
 157                 if (ptrType & DW_EH_PE_signed)
 158                         value = _stp_get_unaligned(ptr.p16s++);
 159                 else
 160                         value = _stp_get_unaligned(ptr.p16u++);
 161                 break;
 162         case DW_EH_PE_data4:
 163 #ifdef CONFIG_64BIT
 164                 if (end < (const void *)(ptr.p32u + 1))
 165                         return 0;
 166                 if (ptrType & DW_EH_PE_signed)
 167                         value = _stp_get_unaligned(ptr.p32s++);
 168                 else
 169                         value = _stp_get_unaligned(ptr.p32u++);
 170                 break;
 171         case DW_EH_PE_data8:
 172                 BUILD_BUG_ON(sizeof(u64) != sizeof(value));
 173 #else
 174                 BUILD_BUG_ON(sizeof(u32) != sizeof(value));
 175 #endif
 176         case DW_EH_PE_absptr:
 177                 if (end < (const void *)(ptr.pul + 1))
 178                         return 0;
 179                 value = _stp_get_unaligned(ptr.pul++);
 180                 break;
 181         case DW_EH_PE_leb128:
 182                 BUILD_BUG_ON(sizeof(uleb128_t) > sizeof(value));
 183                 value = ptrType & DW_EH_PE_signed ? get_sleb128(&ptr.p8, end)
 184                     : get_uleb128(&ptr.p8, end);
 185                 if ((const void *)ptr.p8 > end)
 186                         return 0;
 187                 break;
 188         default:
 189                 return 0;
 190         }
 191         switch (ptrType & DW_EH_PE_ADJUST) {
 192         case DW_EH_PE_absptr:
 193                 break;
 194         case DW_EH_PE_pcrel:
 195                 value += (unsigned long)*pLoc;
 196                 break;
 197         default:
 198                 return 0;
 199         }
 200         if ((ptrType & DW_EH_PE_indirect)
 201             && _stp_read_address(value, (unsigned long *)value, KERNEL_DS))
 202                 return 0;
 203         *pLoc = ptr.p8;
 204
 205         return value;
 206 }
 207
 208 static signed fde_pointer_type(const u32 *cie, void *unwind_data,
 209                                uint32_t table_len)
 210 {
 211         const u8 *ptr = (const u8 *)(cie + 2);
 212         unsigned version = *ptr;
 213
 214         if (version != 1)
 215                 return -1;      /* unsupported */
 216         if (*++ptr) {
 217                 const char *aug;
 218                 const u8 *end = (const u8 *)(cie + 1) + *cie;
 219                 uleb128_t len;
 220
 221                 /* end of cie should fall within unwind table. */
 222                 if (((void*)end) < ((void *)unwind_data)
 223                     || ((void *)end) > ((void *)(unwind_data + table_len)))
 224                   return -1;
 225
 226                 /* check if augmentation size is first (and thus present) */
 227                 if (*ptr != 'z')
 228                         return -1;
 229                 /* check if augmentation string is nul-terminated */
 230                 if ((ptr = memchr(aug = (const void *)ptr, 0, end - ptr)) == NULL)
 231                         return -1;
 232                 ++ptr;          /* skip terminator */
 233                 get_uleb128(&ptr, end); /* skip code alignment */
 234                 get_sleb128(&ptr, end); /* skip data alignment */
 235                 /* skip return address column */
 236                 version <= 1 ? (void)++ptr : (void)get_uleb128(&ptr, end);
 237                 len = get_uleb128(&ptr, end);   /* augmentation length */
 238                 if (ptr + len < ptr || ptr + len > end)
 239                         return -1;
 240                 end = ptr + len;
 241                 while (*++aug) {
 242                         if (ptr >= end)
 243                                 return -1;
 244                         switch (*aug) {
 245                         case 'L':
 246                                 ++ptr;
 247                                 break;
 248                         case 'P':{
 249                                         signed ptrType = *ptr++;
 250
 251                                         if (!read_pointer(&ptr, end, ptrType) || ptr > end)
 252                                                 return -1;
 253                                 }
 254                                 break;
 255                         case 'R':
 256                                 return *ptr;
 257                         default:
 258                                 return -1;
 259                         }
 260                 }
 261         }
 262         return DW_EH_PE_absptr;
 263 }
 264
 265 static int advance_loc(unsigned long delta, struct unwind_state *state)
 266 {
 267         state->loc += delta * state->codeAlign;
 268         dbug_unwind(1, "state->loc=%lx\n", state->loc);
 269         return delta > 0;
 270 }
 271
 272 static void set_rule(uleb128_t reg, enum item_location where, uleb128_t value, struct unwind_state *state)
 273 {
 274         dbug_unwind(1, "reg=%lx, where=%d, value=%lx\n", reg, where, value);
 275         if (reg < ARRAY_SIZE(state->regs)) {
 276                 state->regs[reg].where = where;
 277                 state->regs[reg].value = value;
 278         }
 279 }
 280
 281 static int processCFI(const u8 *start, const u8 *end, unsigned long targetLoc, signed ptrType, struct unwind_state *state)
 282 {
 283         union {
 284                 const u8 *p8;
 285                 const u16 *p16;
 286                 const u32 *p32;
 287         } ptr;
 288         int result = 1;
 289
 290         dbug_unwind(1, "targetLoc=%lx state->loc=%lx\n", targetLoc, state->loc);
 291         if (start != state->cieStart) {
 292                 state->loc = state->org;
 293                 result = processCFI(state->cieStart, state->cieEnd, 0, ptrType, state);
 294                 if (targetLoc == 0 && state->label == NULL)
 295                         return result;
 296         }
 297
 298         for (ptr.p8 = start; result && ptr.p8 < end;) {
 299                 switch (*ptr.p8 >> 6) {
 300                         uleb128_t value;
 301                 case 0:
 302                         switch (*ptr.p8++) {
 303                         case DW_CFA_nop:
 304                                 dbug_unwind(1, "DW_CFA_nop\n");
 305                                 break;
 306                         case DW_CFA_set_loc:
 307                                 if ((state->loc = read_pointer(&ptr.p8, end, ptrType)) == 0)
 308                                         result = 0;
 309                                 dbug_unwind(1, "DW_CFA_set_loc %lx (result=%d)\n", state->loc, result);
 310                                 break;
 311                         case DW_CFA_advance_loc1:
 312                                 result = ptr.p8 < end && advance_loc(*ptr.p8++, state);
 313                                 dbug_unwind(1, "DW_CFA_advance_loc1 %d\n", result);
 314                                 break;
 315                         case DW_CFA_advance_loc2:
 316                                 result = ptr.p8 <= end + 2 && advance_loc(*ptr.p16++, state);
 317                                 dbug_unwind(1, "DW_CFA_advance_loc2 %d\n", result);
 318                                 break;
 319                         case DW_CFA_advance_loc4:
 320                                 result = ptr.p8 <= end + 4 && advance_loc(*ptr.p32++, state);
 321                                 dbug_unwind(1, "DW_CFA_advance_loc4 %d\n", result);
 322                                 break;
 323                         case DW_CFA_offset_extended:
 324                                 value = get_uleb128(&ptr.p8, end);
 325                                 set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
 326                                 dbug_unwind(1, "DW_CFA_offset_extended\n");
 327                                 break;
 328                         case DW_CFA_val_offset:
 329                                 value = get_uleb128(&ptr.p8, end);
 330                                 set_rule(value, Value, get_uleb128(&ptr.p8, end), state);
 331                                 dbug_unwind(1, "DW_CFA_val_offset\n");
 332                                 break;
 333                         case DW_CFA_offset_extended_sf:
 334                                 value = get_uleb128(&ptr.p8, end);
 335                                 set_rule(value, Memory, get_sleb128(&ptr.p8, end), state);
 336                                 dbug_unwind(1, "DW_CFA_offset_extended_sf\n");
 337                                 break;
 338                         case DW_CFA_val_offset_sf:
 339                                 value = get_uleb128(&ptr.p8, end);
 340                                 set_rule(value, Value, get_sleb128(&ptr.p8, end), state);
 341                                 dbug_unwind(1, "DW_CFA_val_offset_sf\n");
 342                                 break;
 343                         case DW_CFA_restore_extended:
 344                         case DW_CFA_undefined:
 345                         case DW_CFA_same_value:
 346                                 set_rule(get_uleb128(&ptr.p8, end), Nowhere, 0, state);
 347                                 dbug_unwind(1, "DW_CFA_undefined\n");
 348                                 break;
 349                         case DW_CFA_register:
 350                                 value = get_uleb128(&ptr.p8, end);
 351                                 set_rule(value, Register, get_uleb128(&ptr.p8, end), state);
 352                                 dbug_unwind(1, "DW_CFA_register\n");
 353                                 break;
 354                         case DW_CFA_remember_state:
 355                                 dbug_unwind(1, "DW_CFA_remember_state\n");
 356                                 if (ptr.p8 == state->label) {
 357                                         state->label = NULL;
 358                                         return 1;
 359                                 }
 360                                 if (state->stackDepth >= STP_MAX_STACK_DEPTH)
 361                                         return 0;
 362                                 state->stack[state->stackDepth++] = ptr.p8;
 363                                 break;
 364                         case DW_CFA_restore_state:
 365                                 dbug_unwind(1, "DW_CFA_restore_state\n");
 366                                 if (state->stackDepth) {
 367                                         const uleb128_t loc = state->loc;
 368                                         const u8 *label = state->label;
 369
 370                                         state->label = state->stack[state->stackDepth - 1];
 371                                         memcpy(&state->cfa, &badCFA, sizeof(state->cfa));
 372                                         memset(state->regs, 0, sizeof(state->regs));
 373                                         state->stackDepth = 0;
 374                                         result = processCFI(start, end, 0, ptrType, state);
 375                                         state->loc = loc;
 376                                         state->label = label;
 377                                 } else
 378                                         return 0;
 379                                 break;
 380                         case DW_CFA_def_cfa:
 381                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 382                                 dbug_unwind(1, "DW_CFA_def_cfa reg=%ld\n", state->cfa.reg);
 383                                 /*nobreak */
 384                         case DW_CFA_def_cfa_offset:
 385                                 state->cfa.offs = get_uleb128(&ptr.p8, end);
 386                                 dbug_unwind(1, "DW_CFA_def_cfa_offset offs=%lx\n", state->cfa.offs);
 387                                 break;
 388                         case DW_CFA_def_cfa_sf:
 389                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 390                                 dbug_unwind(1, "DW_CFA_def_cfa_sf reg=%ld\n", state->cfa.reg);
 391                                 /*nobreak */
 392                         case DW_CFA_def_cfa_offset_sf:
 393                                 state->cfa.offs = get_sleb128(&ptr.p8, end) * state->dataAlign;
 394                                 dbug_unwind(1, "DW_CFA_def_cfa_offset_sf offs=%lx\n", state->cfa.offs);
 395                                 break;
 396                         case DW_CFA_def_cfa_register:
 397                                 state->cfa.reg = get_uleb128(&ptr.p8, end);
 398                                 dbug_unwind(1, "DW_CFA_def_cfa_register reg=%ld\n", state->cfa.reg);
 399                                 break;
 400                                 /*todo case DW_CFA_def_cfa_expression: */
 401                                 /*todo case DW_CFA_expression: */
 402                                 /*todo case DW_CFA_val_expression: */
 403                         case DW_CFA_GNU_args_size:
 404                                 get_uleb128(&ptr.p8, end);
 405                                 dbug_unwind(1, "DW_CFA_GNU_args_size\n");
 406                                 break;
 407                         case DW_CFA_GNU_negative_offset_extended:
 408                                 value = get_uleb128(&ptr.p8, end);
 409                                 set_rule(value, Memory, (uleb128_t)0 - get_uleb128(&ptr.p8, end), state);
 410                                 dbug_unwind(1, "DW_CFA_GNU_negative_offset_extended\n");
 411                                 break;
 412                         case DW_CFA_GNU_window_save:
 413                         default:
 414                                 dbug_unwind(1, "unimplemented call frame instruction: 0x%x\n", *(ptr.p8 - 1));
 415                                 result = 0;
 416                                 break;
 417                         }
 418                         break;
 419                 case 1:
 420                         result = advance_loc(*ptr.p8++ & 0x3f, state);
 421                         dbug_unwind(1, "case 1\n");
 422                         break;
 423                 case 2:
 424                         value = *ptr.p8++ & 0x3f;
 425                         set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
 426                         dbug_unwind(1, "case 2\n");
 427                         break;
 428                 case 3:
 429                         set_rule(*ptr.p8++ & 0x3f, Nowhere, 0, state);
 430                         dbug_unwind(1, "case 3\n");
 431                         break;
 432                 }
 433                 dbug_unwind(1, "targetLoc=%lx state->loc=%lx\n", targetLoc, state->loc);
 434                 if (ptr.p8 > end)
 435                         result = 0;
 436                 if (result && targetLoc != 0 && targetLoc < state->loc)
 437                         return 1;
 438         }
 439         return result && ptr.p8 == end && (targetLoc == 0 || state->label == NULL);
 440 }
 441
 442 #ifdef DEBUG_UNWIND
 443 static const char *_stp_enc_hi_name[] = {
 444         "DW_EH_PE",
 445         "DW_EH_PE_pcrel",
 446         "DW_EH_PE_textrel",
 447         "DW_EH_PE_datarel",
 448         "DW_EH_PE_funcrel",
 449         "DW_EH_PE_aligned"
 450 };
 451 static const char *_stp_enc_lo_name[] = {
 452         "_absptr",
 453         "_uleb128",
 454         "_udata2",
 455         "_udata4",
 456         "_udata8",
 457         "_sleb128",
 458         "_sdata2",
 459         "_sdata4",
 460         "_sdata8"
 461 };
 462 static char *_stp_eh_enc_name(signed type)
 463 {
 464         static char buf[64];
 465         int hi, low;
 466         if (type == DW_EH_PE_omit)
 467                 return "DW_EH_PE_omit";
 468
 469         hi = (type & DW_EH_PE_ADJUST) >> 4;
 470         low = type & DW_EH_PE_FORM;
 471         if (hi > 5 || low > 4 || (low == 0 && (type & DW_EH_PE_signed))) {
 472                 sprintf(buf, "ERROR:encoding=0x%x", type);
 473                 return buf;
 474         }
 475
 476         buf[0] = 0;
 477         if (type & DW_EH_PE_indirect)
 478                 strlcpy(buf, "DW_EH_PE_indirect|", sizeof(buf));
 479         strlcat(buf, _stp_enc_hi_name[hi], sizeof(buf));
 480
 481         if (type & DW_EH_PE_signed)
 482                 low += 4;
 483         strlcat(buf, _stp_enc_lo_name[low], sizeof(buf));
 484         return buf;
 485 }
 486 #endif /* DEBUG_UNWIND */
 487
 488 // If this is an address inside a module, adjust for section relocation
 489 // and the elfutils base relocation done during loading of the .dwarf_frame
 490 // in translate.cxx.
 491 static unsigned long
 492 adjustStartLoc (unsigned long startLoc,
 493                 struct _stp_module *m,
 494                 struct _stp_section *s,
 495                 unsigned ptrType, int is_ehframe)
 496 {
 497   /* XXX - some, or all, of this should really be done by
 498      _stp_module_relocate and/or read_pointer. */
 499   dbug_unwind(2, "adjustStartLoc=%lx, ptrType=%s, m=%s, s=%s eh=%d\n",
 500               startLoc, _stp_eh_enc_name(ptrType), m->name, s->name, is_ehframe);
 501   if (startLoc == 0
 502       || strcmp (m->name, "kernel")  == 0
 503       || (strcmp (s->name, ".absolute") == 0 && !is_ehframe))
 504     return startLoc;
 505
 506   /* eh_frame data has been loaded in the kernel, so readjust offset. */
 507   if (is_ehframe) {
 508     dbug_unwind(2, "eh_frame=%lx, eh_frame_addr=%lx\n", (unsigned long) m->eh_frame, m->eh_frame_addr);
 509     if ((ptrType & DW_EH_PE_ADJUST) == DW_EH_PE_pcrel) {
 510       startLoc -= (unsigned long) m->eh_frame;
 511       startLoc += m->eh_frame_addr;
 512     }
 513     if (strcmp (s->name, ".absolute") == 0)
 514       return startLoc;
 515   }
 516
 517   if (strcmp (s->name, ".dynamic") == 0)
 518     return startLoc + s->addr;
 519
 520   startLoc = _stp_module_relocate (m->name, s->name, startLoc);
 521   startLoc -= m->dwarf_module_base;
 522   return startLoc;
 523 }
 524
 525 /* If we previously created an unwind header, then use it now to binary search */
 526 /* for the FDE corresponding to pc. XXX FIXME not currently supported. */
 527
 528 static u32 *_stp_search_unwind_hdr(unsigned long pc,
 529                                    struct _stp_module *m,
 530                                    struct _stp_section *s)
 531 {
 532         const u8 *ptr, *end, *hdr = m->unwind_hdr;
 533         unsigned long startLoc;
 534         u32 *fde = NULL;
 535         unsigned num, tableSize, t2;
 536
 537         if (hdr == NULL || hdr[0] != 1)
 538                 return NULL;
 539
 540         dbug_unwind(1, "search for %lx", pc);
 541
 542         /* table_enc */
 543         switch (hdr[3] & DW_EH_PE_FORM) {
 544         case DW_EH_PE_absptr:
 545                 tableSize = sizeof(unsigned long);
 546                 break;
 547         case DW_EH_PE_data2:
 548                 tableSize = 2;
 549                 break;
 550         case DW_EH_PE_data4:
 551                 tableSize = 4;
 552                 break;
 553         case DW_EH_PE_data8:
 554                 tableSize = 8;
 555                 break;
 556         default:
 557                 dbug_unwind(1, "bad table encoding");
 558                 return NULL;
 559         }
 560         ptr = hdr + 4;
 561         end = hdr + m->unwind_hdr_len;
 562
 563         if (read_pointer(&ptr, end, hdr[1]) != (unsigned long)m->debug_frame) {
 564                 dbug_unwind(1, "eh_frame_ptr not valid");
 565                 return NULL;
 566         }
 567
 568         num = read_pointer(&ptr, end, hdr[2]);
 569         if (num == 0 || num != (end - ptr) / (2 * tableSize) || (end - ptr) % (2 * tableSize)) {
 570                 dbug_unwind(1, "Bad num=%d end-ptr=%ld 2*tableSize=%d", num, (long)(end - ptr), 2 * tableSize);
 571                 return NULL;
 572         }
 573
 574         do {
 575                 const u8 *cur = ptr + (num / 2) * (2 * tableSize);
 576                 startLoc = read_pointer(&cur, cur + tableSize, hdr[3]);
 577                 startLoc = adjustStartLoc(startLoc, m, s, hdr[3], 1);
 578                 if (pc < startLoc)
 579                         num /= 2;
 580                 else {
 581                         ptr = cur - tableSize;
 582                         num = (num + 1) / 2;
 583                 }
 584         } while (startLoc && num > 1);
 585
 586         if (num == 1 && (startLoc = adjustStartLoc(read_pointer(&ptr, ptr + tableSize, hdr[3]), m, s, hdr[3], 1)) != 0 && pc >= startLoc)
 587                 fde = (void *)read_pointer(&ptr, ptr + tableSize, hdr[3]);
 588
 589         dbug_unwind(1, "returning fde=%lx startLoc=%lx", (unsigned long) fde, startLoc);
 590         return fde;
 591 }
 592
 593 /* Unwind to previous to frame.  Returns 0 if successful, negative
 594  * number in case of an error.  A positive return means unwinding is finished;
 595  * don't try to fallback to dumping addresses on the stack. */
 596 static int unwind_frame(struct unwind_frame_info *frame,
 597                         struct _stp_module *m, struct _stp_section *s,
 598                         void *table, uint32_t table_len, int is_ehframe)
 599 {
 600 #define FRAME_REG(r, t) (((t *)frame)[reg_info[r].offs])
 601         const u32 *fde, *cie = NULL;
 602         const u8 *ptr = NULL, *end = NULL;
 603         unsigned long pc = UNW_PC(frame) - frame->call_frame;
 604         unsigned long tableSize, startLoc = 0, endLoc = 0, cfa;
 605         unsigned i;
 606         signed ptrType = -1;
 607         uleb128_t retAddrReg = 0;
 608         struct unwind_state state;
 609
 610         if (unlikely(table_len == 0 || table_len & (sizeof(*fde) - 1))) {
 611                 dbug_unwind(1, "Module %s: frame_len=%d", m->name, table_len);
 612                 goto err;
 613         }
 614
 615         fde = _stp_search_unwind_hdr(pc, m, s);
 616         dbug_unwind(1, "%s: fde=%lx\n", m->name, (unsigned long) fde);
 617
 618         /* found the fde, now set startLoc and endLoc */
 619         if (fde != NULL) {
 620                 cie = cie_for_fde(fde, table, table_len, is_ehframe);
 621                 if (likely(cie != NULL && cie != &bad_cie && cie != &not_fde)) {
 622                         ptr = (const u8 *)(fde + 2);
 623                         ptrType = fde_pointer_type(cie, table, table_len);
 624                         startLoc = read_pointer(&ptr, (const u8 *)(fde + 1) + *fde, ptrType);
 625                         startLoc = adjustStartLoc(startLoc, m, s, ptrType, is_ehframe);
 626
 627                         dbug_unwind(2, "startLoc=%lx, ptrType=%s\n", startLoc, _stp_eh_enc_name(ptrType));
 628                         if (!(ptrType & DW_EH_PE_indirect))
 629                                 ptrType &= DW_EH_PE_FORM | DW_EH_PE_signed;
 630                         endLoc = startLoc + read_pointer(&ptr, (const u8 *)(fde + 1) + *fde, ptrType);
 631                         if (pc > endLoc) {
 632                                 dbug_unwind(1, "pc (%lx) > endLoc(%lx)\n", pc, endLoc);
 633                                 goto done;
 634                         }
 635                 } else {
 636                         dbug_unwind(1, "fde found in header, but cie is bad!\n");
 637                         fde = NULL;
 638                 }
 639         }
 640
 641         /* did not a good fde find with binary search, so do slow linear search */
 642         if (fde == NULL) {
 643             for (fde = table, tableSize = table_len; cie = NULL, tableSize > sizeof(*fde)
 644                  && tableSize - sizeof(*fde) >= *fde; tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
 645                         dbug_unwind(3, "fde=%lx tableSize=%d\n", (long)*fde, (int)tableSize);
 646                         cie = cie_for_fde(fde, table, table_len, is_ehframe);
 647                         if (cie == &bad_cie) {
 648                                 cie = NULL;
 649                                 break;
 650                         }
 651                         if (cie == NULL || cie == &not_fde || (ptrType = fde_pointer_type(cie, table, table_len)) < 0)
 652                                 continue;
 653
 654                         ptr = (const u8 *)(fde + 2);
 655                         startLoc = read_pointer(&ptr, (const u8 *)(fde + 1) + *fde, ptrType);
 656                         startLoc = adjustStartLoc(startLoc, m, s, ptrType, is_ehframe);
 657                         dbug_unwind(2, "startLoc=%lx, ptrType=%s\n", startLoc, _stp_eh_enc_name(ptrType));
 658                         if (!startLoc)
 659                                 continue;
 660                         if (!(ptrType & DW_EH_PE_indirect))
 661                                 ptrType &= DW_EH_PE_FORM | DW_EH_PE_signed;
 662                         endLoc = startLoc + read_pointer(&ptr, (const u8 *)(fde + 1) + *fde, ptrType);
 663                         dbug_unwind(3, "endLoc=%lx\n", endLoc);
 664                         if (pc >= startLoc && pc < endLoc)
 665                                 break;
 666                 }
 667         }
 668
 669         dbug_unwind(1, "cie=%lx fde=%lx startLoc=%lx endLoc=%lx, pc=%lx\n",
 670                     (unsigned long) cie, (unsigned long)fde, (unsigned long) startLoc, (unsigned long) endLoc, pc);
 671         if (cie == NULL || fde == NULL)
 672                 goto err;
 673
 674         /* found the CIE and FDE */
 675
 676         memset(&state, 0, sizeof(state));
 677         state.cieEnd = ptr;     /* keep here temporarily */
 678         ptr = (const u8 *)(cie + 2);
 679         end = (const u8 *)(cie + 1) + *cie;
 680         frame->call_frame = 1;
 681         if ((state.version = *ptr) != 1) {
 682                 dbug_unwind(1, "CIE version number is %d.  1 is supported.\n", state.version);
 683                 goto err;       /* unsupported version */
 684         }
 685         if (*++ptr) {
 686                 /* check if augmentation size is first (and thus present) */
 687                 if (*ptr == 'z') {
 688                         while (++ptr < end && *ptr) {
 689                                 switch (*ptr) {
 690                                         /* check for ignorable (or already handled)
 691                                          * nul-terminated augmentation string */
 692                                 case 'L':
 693                                 case 'P':
 694                                 case 'R':
 695                                         continue;
 696                                 case 'S':
 697                                         dbug_unwind(1, "This is a signal frame\n");
 698                                         frame->call_frame = 0;
 699                                         continue;
 700                                 default:
 701                                         break;
 702                                 }
 703                                 break;
 704                         }
 705                 }
 706                 if (ptr >= end || *ptr) {
 707                         dbug_unwind(1, "Problem parsing the augmentation string.\n");
 708                         goto err;
 709                 }
 710         }
 711         ++ptr;
 712
 713         /* get code aligment factor */
 714         state.codeAlign = get_uleb128(&ptr, end);
 715         /* get data aligment factor */
 716         state.dataAlign = get_sleb128(&ptr, end);
 717         if (state.codeAlign == 0 || state.dataAlign == 0 || ptr >= end)
 718                 goto err;;
 719
 720         retAddrReg = state.version <= 1 ? *ptr++ : get_uleb128(&ptr, end);
 721
 722         /* skip augmentation */
 723         if (((const char *)(cie + 2))[1] == 'z') {
 724                 uleb128_t augSize = get_uleb128(&ptr, end);
 725                 ptr += augSize;
 726         }
 727         if (ptr > end || retAddrReg >= ARRAY_SIZE(reg_info)
 728             || REG_INVALID(retAddrReg)
 729             || reg_info[retAddrReg].width != sizeof(unsigned long))
 730                 goto err;
 731
 732         state.cieStart = ptr;
 733         ptr = state.cieEnd;
 734         state.cieEnd = end;
 735         end = (const u8 *)(fde + 1) + *fde;
 736
 737         /* skip augmentation */
 738         if (((const char *)(cie + 2))[1] == 'z') {
 739                 uleb128_t augSize = get_uleb128(&ptr, end);
 740                 if ((ptr += augSize) > end)
 741                         goto err;
 742         }
 743
 744         state.org = startLoc;
 745         memcpy(&state.cfa, &badCFA, sizeof(state.cfa));
 746         /* process instructions */
 747         if (!processCFI(ptr, end, pc, ptrType, &state)
 748             || state.loc > endLoc || state.regs[retAddrReg].where == Nowhere || state.cfa.reg >= ARRAY_SIZE(reg_info)
 749             || reg_info[state.cfa.reg].width != sizeof(unsigned long)
 750             || state.cfa.offs % sizeof(unsigned long))
 751                 goto err;
 752
 753         /* update frame */
 754 #ifndef CONFIG_AS_CFI_SIGNAL_FRAME
 755         if (frame->call_frame && !UNW_DEFAULT_RA(state.regs[retAddrReg], state.dataAlign))
 756                 frame->call_frame = 0;
 757 #endif
 758         cfa = FRAME_REG(state.cfa.reg, unsigned long) + state.cfa.offs;
 759         startLoc = min((unsigned long)UNW_SP(frame), cfa);
 760         endLoc = max((unsigned long)UNW_SP(frame), cfa);
 761         dbug_unwind(1, "cfa=%lx startLoc=%lx, endLoc=%lx\n", cfa, startLoc, endLoc);
 762         if (STACK_LIMIT(startLoc) != STACK_LIMIT(endLoc)) {
 763                 startLoc = min(STACK_LIMIT(cfa), cfa);
 764                 endLoc = max(STACK_LIMIT(cfa), cfa);
 765                 dbug_unwind(1, "cfa startLoc=%lx, endLoc=%lx\n",
 766                             (unsigned long)startLoc, (unsigned long)endLoc);
 767         }
 768 #ifndef CONFIG_64BIT
 769 # define CASES CASE(8); CASE(16); CASE(32)
 770 #else
 771 # define CASES CASE(8); CASE(16); CASE(32); CASE(64)
 772 #endif
 773         dbug_unwind(1, "cie=%lx fde=%lx\n", (unsigned long) cie, (unsigned long) fde);
 774         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
 775                 if (REG_INVALID(i)) {
 776                         if (state.regs[i].where == Nowhere)
 777                                 continue;
 778                         dbug_unwind(2, "REG_INVALID %d\n", i);
 779                         goto err;
 780                 }
 781                 dbug_unwind(2, "register %d. where=%d\n", i, state.regs[i].where);
 782                 switch (state.regs[i].where) {
 783                 default:
 784                         break;
 785                 case Register:
 786                         if (state.regs[i].value >= ARRAY_SIZE(reg_info)
 787                             || REG_INVALID(state.regs[i].value)
 788                             || reg_info[i].width > reg_info[state.regs[i].value].width) {
 789                                 dbug_unwind(2, "case Register bad\n");
 790                                 goto err;
 791                         }
 792                         switch (reg_info[state.regs[i].value].width) {
 793 #define CASE(n) \
 794                         case sizeof(u##n): \
 795                                 state.regs[i].value = FRAME_REG(state.regs[i].value, \
 796                                                                 const u##n); \
 797                                 break
 798                                 CASES;
 799 #undef CASE
 800                         default:
 801                                 dbug_unwind(2, "default\n");
 802                                 goto err;
 803                         }
 804                         break;
 805                 }
 806         }
 807         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
 808                 dbug_unwind(2, "register %d. invalid=%d\n", i, REG_INVALID(i));
 809                 if (REG_INVALID(i))
 810                         continue;
 811                 dbug_unwind(2, "register %d. where=%d\n", i, state.regs[i].where);
 812                 switch (state.regs[i].where) {
 813                 case Nowhere:
 814                         if (reg_info[i].width != sizeof(UNW_SP(frame))
 815                             || &FRAME_REG(i, __typeof__(UNW_SP(frame)))
 816                             != &UNW_SP(frame))
 817                                 continue;
 818                         UNW_SP(frame) = cfa;
 819                         break;
 820                 case Register:
 821                         switch (reg_info[i].width) {
 822 #define CASE(n) case sizeof(u##n): \
 823                                 FRAME_REG(i, u##n) = state.regs[i].value; \
 824                                 break
 825                                 CASES;
 826 #undef CASE
 827                         default:
 828                                 dbug_unwind(2, "default\n");
 829                                 goto err;
 830                         }
 831                         break;
 832                 case Value:
 833                         if (reg_info[i].width != sizeof(unsigned long)) {
 834                                 dbug_unwind(2, "Value\n");
 835                                 goto err;
 836                         }
 837                         FRAME_REG(i, unsigned long) = cfa + state.regs[i].value * state.dataAlign;
 838                         break;
 839                 case Memory:{
 840                                 unsigned long addr = cfa + state.regs[i].value * state.dataAlign;
 841                                 dbug_unwind(2, "addr=%lx width=%d\n", addr, reg_info[i].width);
 842                                 switch (reg_info[i].width) {
 843 #define CASE(n)     case sizeof(u##n): \
 844                                         if (unlikely(_stp_read_address(FRAME_REG(i, u##n), (u##n *)addr, KERNEL_DS))) \
 845                                                 goto copy_failed;\
 846                                         dbug_unwind(1, "set register %d to %lx\n", i, (long)FRAME_REG(i,u##n));\
 847                                         break
 848                                         CASES;
 849 #undef CASE
 850                                 default:
 851                                         dbug_unwind(2, "default\n");
 852                                         goto err;
 853                                 }
 854                         }
 855                         break;
 856                 }
 857         }
 858         dbug_unwind(1, "returning 0 (%lx)\n", UNW_PC(frame));
 859         return 0;
 860
 861 copy_failed:
 862         dbug_unwind(1, "_stp_read_address failed to access memory\n");
 863 err:
 864         return -EIO;
 865
 866 done:
 867         /* PC was in a range convered by a module but no unwind info */
 868         /* found for the specific PC. This seems to happen only for kretprobe */
 869         /* trampolines and at the end of interrupt backtraces. */
 870         return 1;
 871 #undef CASES
 872 #undef FRAME_REG
 873 }
 874
 875 static int unwind(struct unwind_frame_info *frame, struct task_struct *tsk)
 876 {
 877         struct _stp_module *m;
 878         struct _stp_section *s = NULL;
 879         unsigned long pc = UNW_PC(frame) - frame->call_frame;
 880         int res;
 881
 882         dbug_unwind(1, "pc=%lx, %lx", pc, UNW_PC(frame));
 883
 884         if (UNW_PC(frame) == 0)
 885                 return -EINVAL;
 886
 887         m = _stp_mod_sec_lookup (pc, tsk, &s);
 888         if (unlikely(m == NULL)) {
 889                 dbug_unwind(1, "No module found for pc=%lx", pc);
 890                 return -EINVAL;
 891         }
 892
 893         dbug_unwind(1, "trying debug_frame\n");
 894         res = unwind_frame (frame, m, s, m->debug_frame,
 895                             m->debug_frame_len, 0);
 896         if (res != 0) {
 897           dbug_unwind(1, "debug_frame failed: %d, trying eh_frame\n", res);
 898           res = unwind_frame (frame, m, s, m->eh_frame,
 899                               m->eh_frame_len, 1);
 900         }
 901
 902         return res;
 903 }
 904
 905 #endif /* STP_USE_DWARF_UNWINDER */