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/systm.h> 36 #include <sys/linker.h> 37 38 #include <machine/stack.h> 39 40 #include "linker_if.h" 41 42 /* 43 * Definitions for the instruction interpreter. 44 * 45 * The ARM EABI specifies how to perform the frame unwinding in the 46 * Exception Handling ABI for the ARM Architecture document. To perform 47 * the unwind we need to know the initial frame pointer, stack pointer, 48 * link register and program counter. We then find the entry within the 49 * index table that points to the function the program counter is within. 50 * This gives us either a list of three instructions to process, a 31-bit 51 * relative offset to a table of instructions, or a value telling us 52 * we can't unwind any further. 53 * 54 * When we have the instructions to process we need to decode them 55 * following table 4 in section 9.3. This describes a collection of bit 56 * patterns to encode that steps to take to update the stack pointer and 57 * link register to the correct values at the start of the function. 58 */ 59 60 /* A special case when we are unable to unwind past this function */ 61 #define EXIDX_CANTUNWIND 1 62 63 /* 64 * These are set in the linker script. Their addresses will be 65 * either the start or end of the exception table or index. 66 */ 67 extern int exidx_start, exidx_end; 68 69 /* 70 * Entry types. 71 * These are the only entry types that have been seen in the kernel. 72 */ 73 #define ENTRY_MASK 0xff000000 74 #define ENTRY_ARM_SU16 0x80000000 75 #define ENTRY_ARM_LU16 0x81000000 76 77 /* Instruction masks. */ 78 #define INSN_VSP_MASK 0xc0 79 #define INSN_VSP_SIZE_MASK 0x3f 80 #define INSN_STD_MASK 0xf0 81 #define INSN_STD_DATA_MASK 0x0f 82 #define INSN_POP_TYPE_MASK 0x08 83 #define INSN_POP_COUNT_MASK 0x07 84 #define INSN_VSP_LARGE_INC_MASK 0xff 85 86 /* Instruction definitions */ 87 #define INSN_VSP_INC 0x00 88 #define INSN_VSP_DEC 0x40 89 #define INSN_POP_MASKED 0x80 90 #define INSN_VSP_REG 0x90 91 #define INSN_POP_COUNT 0xa0 92 #define INSN_FINISH 0xb0 93 #define INSN_POP_REGS 0xb1 94 #define INSN_VSP_LARGE_INC 0xb2 95 96 /* An item in the exception index table */ 97 struct unwind_idx { 98 uint32_t offset; 99 uint32_t insn; 100 }; 101 102 /* Expand a 31-bit signed value to a 32-bit signed value */ 103 static __inline int32_t 104 expand_prel31(uint32_t prel31) 105 { 106 107 return ((int32_t)(prel31 & 0x7fffffffu) << 1) / 2; 108 } 109 110 struct search_context { 111 uint32_t addr; 112 caddr_t exidx_start; 113 caddr_t exidx_end; 114 }; 115 116 static int 117 module_search(linker_file_t lf, void *context) 118 { 119 struct search_context *sc = context; 120 linker_symval_t symval; 121 c_linker_sym_t sym; 122 123 if (lf->address <= (caddr_t)sc->addr && 124 (lf->address + lf->size) >= (caddr_t)sc->addr) { 125 if ((LINKER_LOOKUP_SYMBOL(lf, "__exidx_start", &sym) == 0 || 126 LINKER_LOOKUP_SYMBOL(lf, "exidx_start", &sym) == 0) && 127 LINKER_SYMBOL_VALUES(lf, sym, &symval) == 0) 128 sc->exidx_start = symval.value; 129 130 if ((LINKER_LOOKUP_SYMBOL(lf, "__exidx_end", &sym) == 0 || 131 LINKER_LOOKUP_SYMBOL(lf, "exidx_end", &sym) == 0) && 132 LINKER_SYMBOL_VALUES(lf, sym, &symval) == 0) 133 sc->exidx_end = symval.value; 134 135 if (sc->exidx_start != NULL && sc->exidx_end != NULL) 136 return (1); 137 panic("Invalid module %s, no unwind tables\n", lf->filename); 138 } 139 return (0); 140 } 141 142 /* 143 * Perform a binary search of the index table to find the function 144 * with the largest address that doesn't exceed addr. 145 */ 146 static struct unwind_idx * 147 find_index(uint32_t addr, int search_modules) 148 { 149 struct search_context sc; 150 caddr_t idx_start, idx_end; 151 unsigned int min, mid, max; 152 struct unwind_idx *start; 153 struct unwind_idx *item; 154 int32_t prel31_addr; 155 uint32_t func_addr; 156 157 start = (struct unwind_idx *)&exidx_start; 158 idx_start = (caddr_t)&exidx_start; 159 idx_end = (caddr_t)&exidx_end; 160 161 /* This may acquire a lock */ 162 if (search_modules) { 163 bzero(&sc, sizeof(sc)); 164 sc.addr = addr; 165 if (linker_file_foreach(module_search, &sc) != 0 && 166 sc.exidx_start != NULL && sc.exidx_end != NULL) { 167 start = (struct unwind_idx *)sc.exidx_start; 168 idx_start = sc.exidx_start; 169 idx_end = sc.exidx_end; 170 } 171 } 172 173 min = 0; 174 max = (idx_end - idx_start) / sizeof(struct unwind_idx); 175 176 while (min != max) { 177 mid = min + (max - min + 1) / 2; 178 179 item = &start[mid]; 180 181 prel31_addr = expand_prel31(item->offset); 182 func_addr = (uint32_t)&item->offset + prel31_addr; 183 184 if (func_addr <= addr) { 185 min = mid; 186 } else { 187 max = mid - 1; 188 } 189 } 190 191 return &start[min]; 192 } 193 194 /* Reads the next byte from the instruction list */ 195 static uint8_t 196 unwind_exec_read_byte(struct unwind_state *state) 197 { 198 uint8_t insn; 199 200 /* Read the unwind instruction */ 201 insn = (*state->insn) >> (state->byte * 8); 202 203 /* Update the location of the next instruction */ 204 if (state->byte == 0) { 205 state->byte = 3; 206 state->insn++; 207 state->entries--; 208 } else 209 state->byte--; 210 211 return insn; 212 } 213 214 /* Executes the next instruction on the list */ 215 static int 216 unwind_exec_insn(struct unwind_state *state) 217 { 218 unsigned int insn; 219 uint32_t *vsp = (uint32_t *)state->registers[SP]; 220 int update_vsp = 0; 221 222 /* This should never happen */ 223 if (state->entries == 0) 224 return 1; 225 226 /* Read the next instruction */ 227 insn = unwind_exec_read_byte(state); 228 229 if ((insn & INSN_VSP_MASK) == INSN_VSP_INC) { 230 state->registers[SP] += ((insn & INSN_VSP_SIZE_MASK) << 2) + 4; 231 232 } else if ((insn & INSN_VSP_MASK) == INSN_VSP_DEC) { 233 state->registers[SP] -= ((insn & INSN_VSP_SIZE_MASK) << 2) + 4; 234 235 } else if ((insn & INSN_STD_MASK) == INSN_POP_MASKED) { 236 unsigned int mask, reg; 237 238 /* Load the mask */ 239 mask = unwind_exec_read_byte(state); 240 mask |= (insn & INSN_STD_DATA_MASK) << 8; 241 242 /* We have a refuse to unwind instruction */ 243 if (mask == 0) 244 return 1; 245 246 /* Update SP */ 247 update_vsp = 1; 248 249 /* Load the registers */ 250 for (reg = 4; mask && reg < 16; mask >>= 1, reg++) { 251 if (mask & 1) { 252 state->registers[reg] = *vsp++; 253 state->update_mask |= 1 << reg; 254 255 /* If we have updated SP kep its value */ 256 if (reg == SP) 257 update_vsp = 0; 258 } 259 } 260 261 } else if ((insn & INSN_STD_MASK) == INSN_VSP_REG && 262 ((insn & INSN_STD_DATA_MASK) != 13) && 263 ((insn & INSN_STD_DATA_MASK) != 15)) { 264 /* sp = register */ 265 state->registers[SP] = 266 state->registers[insn & INSN_STD_DATA_MASK]; 267 268 } else if ((insn & INSN_STD_MASK) == INSN_POP_COUNT) { 269 unsigned int count, reg; 270 271 /* Read how many registers to load */ 272 count = insn & INSN_POP_COUNT_MASK; 273 274 /* Update sp */ 275 update_vsp = 1; 276 277 /* Pop the registers */ 278 for (reg = 4; reg <= 4 + count; reg++) { 279 state->registers[reg] = *vsp++; 280 state->update_mask |= 1 << reg; 281 } 282 283 /* Check if we are in the pop r14 version */ 284 if ((insn & INSN_POP_TYPE_MASK) != 0) { 285 state->registers[14] = *vsp++; 286 } 287 288 } else if (insn == INSN_FINISH) { 289 /* Stop processing */ 290 state->entries = 0; 291 292 } else if (insn == INSN_POP_REGS) { 293 unsigned int mask, reg; 294 295 mask = unwind_exec_read_byte(state); 296 if (mask == 0 || (mask & 0xf0) != 0) 297 return 1; 298 299 /* Update SP */ 300 update_vsp = 1; 301 302 /* Load the registers */ 303 for (reg = 0; mask && reg < 4; mask >>= 1, reg++) { 304 if (mask & 1) { 305 state->registers[reg] = *vsp++; 306 state->update_mask |= 1 << reg; 307 } 308 } 309 310 } else if ((insn & INSN_VSP_LARGE_INC_MASK) == INSN_VSP_LARGE_INC) { 311 unsigned int uleb128; 312 313 /* Read the increment value */ 314 uleb128 = unwind_exec_read_byte(state); 315 316 state->registers[SP] += 0x204 + (uleb128 << 2); 317 318 } else { 319 /* We hit a new instruction that needs to be implemented */ 320 #if 0 321 db_printf("Unhandled instruction %.2x\n", insn); 322 #endif 323 return 1; 324 } 325 326 if (update_vsp) { 327 state->registers[SP] = (uint32_t)vsp; 328 } 329 330 #if 0 331 db_printf("fp = %08x, sp = %08x, lr = %08x, pc = %08x\n", 332 state->registers[FP], state->registers[SP], state->registers[LR], 333 state->registers[PC]); 334 #endif 335 336 return 0; 337 } 338 339 /* Performs the unwind of a function */ 340 static int 341 unwind_tab(struct unwind_state *state) 342 { 343 uint32_t entry; 344 345 /* Set PC to a known value */ 346 state->registers[PC] = 0; 347 348 /* Read the personality */ 349 entry = *state->insn & ENTRY_MASK; 350 351 if (entry == ENTRY_ARM_SU16) { 352 state->byte = 2; 353 state->entries = 1; 354 } else if (entry == ENTRY_ARM_LU16) { 355 state->byte = 1; 356 state->entries = ((*state->insn >> 16) & 0xFF) + 1; 357 } else { 358 #if 0 359 db_printf("Unknown entry: %x\n", entry); 360 #endif 361 return 1; 362 } 363 364 while (state->entries > 0) { 365 if (unwind_exec_insn(state) != 0) 366 return 1; 367 } 368 369 /* 370 * The program counter was not updated, load it from the link register. 371 */ 372 if (state->registers[PC] == 0) { 373 state->registers[PC] = state->registers[LR]; 374 375 /* 376 * If the program counter changed, flag it in the update mask. 377 */ 378 if (state->start_pc != state->registers[PC]) 379 state->update_mask |= 1 << PC; 380 } 381 382 return 0; 383 } 384 385 int 386 unwind_stack_one(struct unwind_state *state, int can_lock) 387 { 388 struct unwind_idx *index; 389 int finished; 390 391 /* Reset the mask of updated registers */ 392 state->update_mask = 0; 393 394 /* The pc value is correct and will be overwritten, save it */ 395 state->start_pc = state->registers[PC]; 396 397 /* Find the item to run */ 398 index = find_index(state->start_pc, can_lock); 399 400 finished = 0; 401 if (index->insn != EXIDX_CANTUNWIND) { 402 if (index->insn & (1U << 31)) { 403 /* The data is within the instruction */ 404 state->insn = &index->insn; 405 } else { 406 /* A prel31 offset to the unwind table */ 407 state->insn = (uint32_t *) 408 ((uintptr_t)&index->insn + 409 expand_prel31(index->insn)); 410 } 411 /* Run the unwind function */ 412 finished = unwind_tab(state); 413 } 414 415 /* This is the top of the stack, finish */ 416 if (index->insn == EXIDX_CANTUNWIND) 417 finished = 1; 418 419 return (finished); 420 } 421