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