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 */ 95struct 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 */ 137struct 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}; 145static 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 */ 161static void 162clear_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 */ 172static void 173populate_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 */ 189static struct module_info * 190create_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 */ 206static struct module_info * 207find_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 */ 223void 224unwind_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. */ 251void 252unwind_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 */ 283static int 284module_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} 299SYSINIT(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 */ 302static __inline int32_t 303expand_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 */ 313static struct unwind_idx * 314find_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 */ 350static uint8_t 351unwind_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 */ 370static int 371unwind_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 */ 495static int 496unwind_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 */ 547int 548unwind_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} 576