sys/arm/arm/unwind.c

   1 /*
   2  * Copyright 2013-2014 Andrew Turner.
   3  * Copyright 2013-2014 Ian Lepore.
   4  * Copyright 2013-2014 Rui Paulo.
   5  * Copyright 2013 Eitan Adler.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions are
  10  * met:
  11  *
  12  *  1. Redistributions of source code must retain the above copyright
  13  *     notice, this list of conditions and the following disclaimer.
  14  *  2. Redistributions in binary form must reproduce the above copyright
  15  *     notice, this list of conditions and the following disclaimer in the
  16  *     documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  25  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  26  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  27  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  28  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include <sys/cdefs.h>
  32 __FBSDID("$FreeBSD$");
  33
  34 #include <sys/param.h>
  35 #include <sys/kernel.h>
  36 #include <sys/linker.h>
  37 #include <sys/malloc.h>
  38 #include <sys/queue.h>
  39 #include <sys/systm.h>
  40
  41 #include <machine/machdep.h>
  42 #include <machine/stack.h>
  43
  44 #include "linker_if.h"
  45
  46 /*
  47  * Definitions for the instruction interpreter.
  48  *
  49  * The ARM EABI specifies how to perform the frame unwinding in the
  50  * Exception Handling ABI for the ARM Architecture document. To perform
  51  * the unwind we need to know the initial frame pointer, stack pointer,
  52  * link register and program counter. We then find the entry within the
  53  * index table that points to the function the program counter is within.
  54  * This gives us either a list of three instructions to process, a 31-bit
  55  * relative offset to a table of instructions, or a value telling us
  56  * we can't unwind any further.
  57  *
  58  * When we have the instructions to process we need to decode them
  59  * following table 4 in section 9.3. This describes a collection of bit
  60  * patterns to encode that steps to take to update the stack pointer and
  61  * link register to the correct values at the start of the function.
  62  */
  63
  64 /* A special case when we are unable to unwind past this function */
  65 #define EXIDX_CANTUNWIND        1
  66
  67 /*
  68  * Entry types.
  69  * These are the only entry types that have been seen in the kernel.
  70  */
  71 #define ENTRY_MASK      0xff000000
  72 #define ENTRY_ARM_SU16  0x80000000
  73 #define ENTRY_ARM_LU16  0x81000000
  74
  75 /* Instruction masks. */
  76 #define INSN_VSP_MASK           0xc0
  77 #define INSN_VSP_SIZE_MASK      0x3f
  78 #define INSN_STD_MASK           0xf0
  79 #define INSN_STD_DATA_MASK      0x0f
  80 #define INSN_POP_TYPE_MASK      0x08
  81 #define INSN_POP_COUNT_MASK     0x07
  82 #define INSN_VSP_LARGE_INC_MASK 0xff
  83
  84 /* Instruction definitions */
  85 #define INSN_VSP_INC            0x00
  86 #define INSN_VSP_DEC            0x40
  87 #define INSN_POP_MASKED         0x80
  88 #define INSN_VSP_REG            0x90
  89 #define INSN_POP_COUNT          0xa0
  90 #define INSN_FINISH             0xb0
  91 #define INSN_POP_REGS           0xb1
  92 #define INSN_VSP_LARGE_INC      0xb2
  93
  94 /* An item in the exception index table */
  95 struct unwind_idx {
  96         uint32_t offset;
  97         uint32_t insn;
  98 };
  99
 100 /*
 101  * Local cache of unwind info for loaded modules.
 102  *
 103  * To unwind the stack through the code in a loaded module, we need to access
 104  * the module's exidx unwind data.  To locate that data, one must search the
 105  * elf section headers for the SHT_ARM_EXIDX section.  Those headers are
 106  * available at the time the module is being loaded, but are discarded by time
 107  * the load process has completed.  Code in kern/link_elf.c locates the data we
 108  * need and stores it into the linker_file structure before calling the arm
 109  * machdep routine for handling loaded modules (in arm/elf_machdep.c).  That
 110  * function calls into this code to pass along the unwind info, which we save
 111  * into one of these module_info structures.
 112  *
 113  * Because we have to help stack(9) gather stack info at any time, including in
 114  * contexts where sleeping is not allowed, we cannot use linker_file_foreach()
 115  * to walk the kernel's list of linker_file structs, because doing so requires
 116  * acquiring an exclusive sx_lock.  So instead, we keep a local list of these
 117  * structures, one for each loaded module (and one for the kernel itself that we
 118  * synthesize at init time).  New entries are added to the end of this list as
 119  * needed, but entries are never deleted from the list.  Instead, they are
 120  * cleared out in-place to mark them as unused.  That means the code doing stack
 121  * unwinding can always safely walk the list without locking, because the
 122  * structure of the list never changes in a way that would cause the walker to
 123  * follow a bad link.
 124  *
 125  * A cleared-out entry on the list has module start=UINTPTR_MAX and end=0, so
 126  * start <= addr < end cannot be true for any value of addr being searched for.
 127  * We also don't have to worry about races where we look up the unwind info just
 128  * before a module is unloaded and try to access it concurrently with or just
 129  * after the unloading happens in another thread, because that means the path of
 130  * execution leads through a now-unloaded module, and that's already well into
 131  * undefined-behavior territory.
 132  *
 133  * List entries marked as unused get reused when new modules are loaded.  We
 134  * don't worry about holding a few unused bytes of memory in the list after
 135  * unloading a module.
 136  */
 137 struct module_info {
 138         uintptr_t       module_start;   /* Start of loaded module */
 139         uintptr_t       module_end;     /* End of loaded module */
 140         uintptr_t       exidx_start;    /* Start of unwind data */
 141         uintptr_t       exidx_end;      /* End of unwind data */
 142         STAILQ_ENTRY(module_info)
 143                         link;           /* Link to next entry */
 144 };
 145 static STAILQ_HEAD(, module_info) module_list;
 146
 147 /*
 148  * Hide ugly casting in somewhat-less-ugly macros.
 149  *  CADDR - cast a pointer or number to caddr_t.
 150  *  UADDR - cast a pointer or number to uintptr_t.
 151  */
 152 #define CADDR(addr)     ((caddr_t)(void*)(uintptr_t)(addr))
 153 #define UADDR(addr)     ((uintptr_t)(addr))
 154
 155 /*
 156  * Clear the info in an existing module_info entry on the list.  The
 157  * module_start/end addresses are set to values that cannot match any real
 158  * memory address.  The entry remains on the list, but will be ignored until it
 159  * is populated with new data.
 160  */
 161 static void
 162 clear_module_info(struct module_info *info)
 163 {
 164         info->module_start = UINTPTR_MAX;
 165         info->module_end   = 0;
 166 }
 167
 168 /*
 169  * Populate an existing module_info entry (which is already on the list) with
 170  * the info for a new module.
 171  */
 172 static void
 173 populate_module_info(struct module_info *info, linker_file_t lf)
 174 {
 175
 176         /*
 177          * Careful!  The module_start and module_end fields must not be set
 178          * until all other data in the structure is valid.
 179          */
 180         info->exidx_start  = UADDR(lf->exidx_addr);
 181         info->exidx_end    = UADDR(lf->exidx_addr) + lf->exidx_size;
 182         info->module_start = UADDR(lf->address);
 183         info->module_end   = UADDR(lf->address) + lf->size;
 184 }
 185
 186 /*
 187  * Create a new empty module_info entry and add it to the tail of the list.
 188  */
 189 static struct module_info *
 190 create_module_info(void)
 191 {
 192         struct module_info *info;
 193
 194         info = malloc(sizeof(*info), M_CACHE, M_WAITOK | M_ZERO);
 195         clear_module_info(info);
 196         STAILQ_INSERT_TAIL(&module_list, info, link);
 197         return (info);
 198 }
 199
 200 /*
 201  * Search for a module_info entry on the list whose address range contains the
 202  * given address.  If the search address is zero (no module will be loaded at
 203  * zero), then we're looking for an empty item to reuse, which is indicated by
 204  * module_start being set to UINTPTR_MAX in the entry.
 205  */
 206 static struct module_info *
 207 find_module_info(uintptr_t addr)
 208 {
 209         struct module_info *info;
 210
 211         STAILQ_FOREACH(info, &module_list, link) {
 212                 if ((addr >= info->module_start && addr < info->module_end) ||
 213                     (addr == 0 && info->module_start == UINTPTR_MAX))
 214                         return (info);
 215         }
 216         return (NULL);
 217 }
 218
 219 /*
 220  * Handle the loading of a new module by populating a module_info for it.  This
 221  * is called for both preloaded and dynamically loaded modules.
 222  */
 223 void
 224 unwind_module_loaded(struct linker_file *lf)
 225 {
 226         struct module_info *info;
 227
 228         /*
 229          * A module that contains only data may have no unwind info; don't
 230          * create any module info for it.
 231          */
 232         if (lf->exidx_size == 0)
 233                 return;
 234
 235         /*
 236          * Find an unused entry in the existing list to reuse.  If we don't find
 237          * one, create a new one and link it into the list.  This is the only
 238          * place the module_list is modified.  Adding a new entry to the list
 239          * will not perturb any other threads currently walking the list.  This
 240          * function is invoked while kern_linker is still holding its lock
 241          * to prevent its module list from being modified, so we don't have to
 242          * worry about racing other threads doing an insert concurrently.
 243          */
 244         if ((info = find_module_info(0)) == NULL) {
 245                 info = create_module_info();
 246         }
 247         populate_module_info(info, lf);
 248 }
 249
 250 /* Handle the unloading of a module. */
 251 void
 252 unwind_module_unloaded(struct linker_file *lf)
 253 {
 254         struct module_info *info;
 255
 256         /*
 257          * A module that contains only data may have no unwind info and there
 258          * won't be a list entry for it.
 259          */
 260         if (lf->exidx_size == 0)
 261                 return;
 262
 263         /*
 264          * When a module is unloaded, we clear the info out of its entry in the
 265          * module list, making that entry available for later reuse.
 266          */
 267         if ((info = find_module_info(UADDR(lf->address))) == NULL) {
 268                 printf("arm unwind: module '%s' not on list at unload time\n",
 269                     lf->filename);
 270                 return;
 271         }
 272         clear_module_info(info);
 273 }
 274
 275 /*
 276  * Initialization must run fairly early, as soon as malloc(9) is available, and
 277  * definitely before witness, which uses stack(9).  We synthesize a module_info
 278  * entry for the kernel, because unwind_module_loaded() doesn't get called for
 279  * it.  Also, it is unlike other modules in that the elf metadata for locating
 280  * the unwind tables might be stripped, so instead we have to use the
 281  * _exidx_start/end symbols created by ldscript.arm.
 282  */
 283 static int
 284 module_info_init(void *arg __unused)
 285 {
 286         struct linker_file thekernel;
 287
 288         STAILQ_INIT(&module_list);
 289
 290         thekernel.filename   = "kernel";
 291         thekernel.address    = CADDR(&_start);
 292         thekernel.size       = UADDR(&_end) - UADDR(&_start);
 293         thekernel.exidx_addr = CADDR(&_exidx_start);
 294         thekernel.exidx_size = UADDR(&_exidx_end) - UADDR(&_exidx_start);
 295         populate_module_info(create_module_info(), &thekernel);
 296
 297         return (0);
 298 }
 299 SYSINIT(unwind_init, SI_SUB_KMEM, SI_ORDER_ANY, module_info_init, NULL);
 300
 301 /* Expand a 31-bit signed value to a 32-bit signed value */
 302 static __inline int32_t
 303 expand_prel31(uint32_t prel31)
 304 {
 305
 306         return ((int32_t)(prel31 & 0x7fffffffu) << 1) / 2;
 307 }
 308
 309 /*
 310  * Perform a binary search of the index table to find the function
 311  * with the largest address that doesn't exceed addr.
 312  */
 313 static struct unwind_idx *
 314 find_index(uint32_t addr)
 315 {
 316         struct module_info *info;
 317         unsigned int min, mid, max;
 318         struct unwind_idx *start;
 319         struct unwind_idx *item;
 320         int32_t prel31_addr;
 321         uint32_t func_addr;
 322
 323         info = find_module_info(addr);
 324         if (info == NULL)
 325                 return NULL;
 326
 327         min = 0;
 328         max = (info->exidx_end - info->exidx_start) / sizeof(struct unwind_idx);
 329         start = (struct unwind_idx *)CADDR(info->exidx_start);
 330
 331         while (min != max) {
 332                 mid = min + (max - min + 1) / 2;
 333
 334                 item = &start[mid];
 335
 336                 prel31_addr = expand_prel31(item->offset);
 337                 func_addr = (uint32_t)&item->offset + prel31_addr;
 338
 339                 if (func_addr <= addr) {
 340                         min = mid;
 341                 } else {
 342                         max = mid - 1;
 343                 }
 344         }
 345
 346         return &start[min];
 347 }
 348
 349 /* Reads the next byte from the instruction list */
 350 static uint8_t
 351 unwind_exec_read_byte(struct unwind_state *state)
 352 {
 353         uint8_t insn;
 354
 355         /* Read the unwind instruction */
 356         insn = (*state->insn) >> (state->byte * 8);
 357
 358         /* Update the location of the next instruction */
 359         if (state->byte == 0) {
 360                 state->byte = 3;
 361                 state->insn++;
 362                 state->entries--;
 363         } else
 364                 state->byte--;
 365
 366         return insn;
 367 }
 368
 369 /* Executes the next instruction on the list */
 370 static int
 371 unwind_exec_insn(struct unwind_state *state)
 372 {
 373         unsigned int insn;
 374         uint32_t *vsp = (uint32_t *)state->registers[SP];
 375         int update_vsp = 0;
 376
 377         /* This should never happen */
 378         if (state->entries == 0)
 379                 return 1;
 380
 381         /* Read the next instruction */
 382         insn = unwind_exec_read_byte(state);
 383
 384         if ((insn & INSN_VSP_MASK) == INSN_VSP_INC) {
 385                 state->registers[SP] += ((insn & INSN_VSP_SIZE_MASK) << 2) + 4;
 386
 387         } else if ((insn & INSN_VSP_MASK) == INSN_VSP_DEC) {
 388                 state->registers[SP] -= ((insn & INSN_VSP_SIZE_MASK) << 2) + 4;
 389
 390         } else if ((insn & INSN_STD_MASK) == INSN_POP_MASKED) {
 391                 unsigned int mask, reg;
 392
 393                 /* Load the mask */
 394                 mask = unwind_exec_read_byte(state);
 395                 mask |= (insn & INSN_STD_DATA_MASK) << 8;
 396
 397                 /* We have a refuse to unwind instruction */
 398                 if (mask == 0)
 399                         return 1;
 400
 401                 /* Update SP */
 402                 update_vsp = 1;
 403
 404                 /* Load the registers */
 405                 for (reg = 4; mask && reg < 16; mask >>= 1, reg++) {
 406                         if (mask & 1) {
 407                                 state->registers[reg] = *vsp++;
 408                                 state->update_mask |= 1 << reg;
 409
 410                                 /* If we have updated SP kep its value */
 411                                 if (reg == SP)
 412                                         update_vsp = 0;
 413                         }
 414                 }
 415
 416         } else if ((insn & INSN_STD_MASK) == INSN_VSP_REG &&
 417             ((insn & INSN_STD_DATA_MASK) != 13) &&
 418             ((insn & INSN_STD_DATA_MASK) != 15)) {
 419                 /* sp = register */
 420                 state->registers[SP] =
 421                     state->registers[insn & INSN_STD_DATA_MASK];
 422
 423         } else if ((insn & INSN_STD_MASK) == INSN_POP_COUNT) {
 424                 unsigned int count, reg;
 425
 426                 /* Read how many registers to load */
 427                 count = insn & INSN_POP_COUNT_MASK;
 428
 429                 /* Update sp */
 430                 update_vsp = 1;
 431
 432                 /* Pop the registers */
 433                 for (reg = 4; reg <= 4 + count; reg++) {
 434                         state->registers[reg] = *vsp++;
 435                         state->update_mask |= 1 << reg;
 436                 }
 437
 438                 /* Check if we are in the pop r14 version */
 439                 if ((insn & INSN_POP_TYPE_MASK) != 0) {
 440                         state->registers[14] = *vsp++;
 441                 }
 442
 443         } else if (insn == INSN_FINISH) {
 444                 /* Stop processing */
 445                 state->entries = 0;
 446
 447         } else if (insn == INSN_POP_REGS) {
 448                 unsigned int mask, reg;
 449
 450                 mask = unwind_exec_read_byte(state);
 451                 if (mask == 0 || (mask & 0xf0) != 0)
 452                         return 1;
 453
 454                 /* Update SP */
 455                 update_vsp = 1;
 456
 457                 /* Load the registers */
 458                 for (reg = 0; mask && reg < 4; mask >>= 1, reg++) {
 459                         if (mask & 1) {
 460                                 state->registers[reg] = *vsp++;
 461                                 state->update_mask |= 1 << reg;
 462                         }
 463                 }
 464
 465         } else if ((insn & INSN_VSP_LARGE_INC_MASK) == INSN_VSP_LARGE_INC) {
 466                 unsigned int uleb128;
 467
 468                 /* Read the increment value */
 469                 uleb128 = unwind_exec_read_byte(state);
 470
 471                 state->registers[SP] += 0x204 + (uleb128 << 2);
 472
 473         } else {
 474                 /* We hit a new instruction that needs to be implemented */
 475 #if 0
 476                 db_printf("Unhandled instruction %.2x\n", insn);
 477 #endif
 478                 return 1;
 479         }
 480
 481         if (update_vsp) {
 482                 state->registers[SP] = (uint32_t)vsp;
 483         }
 484
 485 #if 0
 486         db_printf("fp = %08x, sp = %08x, lr = %08x, pc = %08x\n",
 487             state->registers[FP], state->registers[SP], state->registers[LR],
 488             state->registers[PC]);
 489 #endif
 490
 491         return 0;
 492 }
 493
 494 /* Performs the unwind of a function */
 495 static int
 496 unwind_tab(struct unwind_state *state)
 497 {
 498         uint32_t entry;
 499
 500         /* Set PC to a known value */
 501         state->registers[PC] = 0;
 502
 503         /* Read the personality */
 504         entry = *state->insn & ENTRY_MASK;
 505
 506         if (entry == ENTRY_ARM_SU16) {
 507                 state->byte = 2;
 508                 state->entries = 1;
 509         } else if (entry == ENTRY_ARM_LU16) {
 510                 state->byte = 1;
 511                 state->entries = ((*state->insn >> 16) & 0xFF) + 1;
 512         } else {
 513 #if 0
 514                 db_printf("Unknown entry: %x\n", entry);
 515 #endif
 516                 return 1;
 517         }
 518
 519         while (state->entries > 0) {
 520                 if (unwind_exec_insn(state) != 0)
 521                         return 1;
 522         }
 523
 524         /*
 525          * The program counter was not updated, load it from the link register.
 526          */
 527         if (state->registers[PC] == 0) {
 528                 state->registers[PC] = state->registers[LR];
 529
 530                 /*
 531                  * If the program counter changed, flag it in the update mask.
 532                  */
 533                 if (state->start_pc != state->registers[PC])
 534                         state->update_mask |= 1 << PC;
 535         }
 536
 537         return 0;
 538 }
 539
 540 /*
 541  * Unwind a single stack frame.
 542  * Return 0 on success or 1 if the stack cannot be unwound any further.
 543  *
 544  * XXX The can_lock argument is no longer germane; a sweep of callers should be
 545  * made to remove it after this new code has proven itself for a while.
 546  */
 547 int
 548 unwind_stack_one(struct unwind_state *state, int can_lock __unused)
 549 {
 550         struct unwind_idx *index;
 551
 552         /* Reset the mask of updated registers */
 553         state->update_mask = 0;
 554
 555         /* The pc value is correct and will be overwritten, save it */
 556         state->start_pc = state->registers[PC];
 557
 558         /* Find the item to run */
 559         index = find_index(state->start_pc);
 560         if (index == NULL || index->insn == EXIDX_CANTUNWIND)
 561                 return 1;
 562
 563         if (index->insn & (1U << 31)) {
 564                 /* The data is within the instruction */
 565                 state->insn = &index->insn;
 566         } else {
 567                 /* A prel31 offset to the unwind table */
 568                 state->insn = (uint32_t *)
 569                     ((uintptr_t)&index->insn +
 570                      expand_prel31(index->insn));
 571         }
 572
 573         /* Run the unwind function, return its finished/not-finished status. */
 574         return (unwind_tab(state));
 575 }