1 // SPDX-License-Identifier: BSD-2-Clause 2 /* 3 * Copyright 2015 Linaro Limited 4 * Copyright 2013-2014 Andrew Turner. 5 * Copyright 2013-2014 Ian Lepore. 6 * Copyright 2013-2014 Rui Paulo. 7 * Copyright 2013 Eitan Adler. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions are 12 * met: 13 * 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE 24 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 27 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 28 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 29 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 30 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 #include <arm.h> 34 #include <kernel/linker.h> 35 #include <kernel/misc.h> 36 #include <kernel/tee_misc.h> 37 #include <kernel/unwind.h> 38 #include <string.h> 39 #include <tee_api_types.h> 40 #include <tee/tee_svc.h> 41 #include <trace.h> 42 #include <util.h> 43 44 #include "unwind_private.h" 45 46 /* The register names */ 47 #define FP 11 48 #define SP 13 49 #define LR 14 50 #define PC 15 51 52 /* 53 * Definitions for the instruction interpreter. 54 * 55 * The ARM EABI specifies how to perform the frame unwinding in the 56 * Exception Handling ABI for the ARM Architecture document. To perform 57 * the unwind we need to know the initial frame pointer, stack pointer, 58 * link register and program counter. We then find the entry within the 59 * index table that points to the function the program counter is within. 60 * This gives us either a list of three instructions to process, a 31-bit 61 * relative offset to a table of instructions, or a value telling us 62 * we can't unwind any further. 63 * 64 * When we have the instructions to process we need to decode them 65 * following table 4 in section 9.3. This describes a collection of bit 66 * patterns to encode that steps to take to update the stack pointer and 67 * link register to the correct values at the start of the function. 68 */ 69 70 /* A special case when we are unable to unwind past this function */ 71 #define EXIDX_CANTUNWIND 1 72 73 /* 74 * Entry types. 75 * These are the only entry types that have been seen in the kernel. 76 */ 77 #define ENTRY_MASK 0xff000000 78 #define ENTRY_ARM_SU16 0x80000000 79 #define ENTRY_ARM_LU16 0x81000000 80 81 /* Instruction masks. */ 82 #define INSN_VSP_MASK 0xc0 83 #define INSN_VSP_SIZE_MASK 0x3f 84 #define INSN_STD_MASK 0xf0 85 #define INSN_STD_DATA_MASK 0x0f 86 #define INSN_POP_TYPE_MASK 0x08 87 #define INSN_POP_COUNT_MASK 0x07 88 #define INSN_VSP_LARGE_INC_MASK 0xff 89 90 /* Instruction definitions */ 91 #define INSN_VSP_INC 0x00 92 #define INSN_VSP_DEC 0x40 93 #define INSN_POP_MASKED 0x80 94 #define INSN_VSP_REG 0x90 95 #define INSN_POP_COUNT 0xa0 96 #define INSN_FINISH 0xb0 97 #define INSN_POP_REGS 0xb1 98 #define INSN_VSP_LARGE_INC 0xb2 99 100 /* An item in the exception index table */ 101 struct unwind_idx { 102 uint32_t offset; 103 uint32_t insn; 104 }; 105 106 static bool copy_in(void *dst, const void *src, size_t n, bool kernel_data) 107 { 108 if (!kernel_data) 109 return !tee_svc_copy_from_user(dst, src, n); 110 111 memcpy(dst, src, n); 112 return true; 113 } 114 115 /* Expand a 31-bit signed value to a 32-bit signed value */ 116 static int32_t expand_prel31(uint32_t prel31) 117 { 118 return prel31 | SHIFT_U32(prel31 & BIT32(30), 1); 119 } 120 121 /* 122 * Perform a binary search of the index table to find the function 123 * with the largest address that doesn't exceed addr. 124 */ 125 static struct unwind_idx *find_index(uint32_t addr, vaddr_t exidx, 126 size_t exidx_sz) 127 { 128 vaddr_t idx_start, idx_end; 129 unsigned int min, mid, max; 130 struct unwind_idx *start; 131 struct unwind_idx *item; 132 int32_t prel31_addr; 133 vaddr_t func_addr; 134 135 start = (struct unwind_idx *)exidx; 136 idx_start = exidx; 137 idx_end = exidx + exidx_sz; 138 139 min = 0; 140 max = (idx_end - idx_start) / sizeof(struct unwind_idx); 141 142 while (min != max) { 143 mid = min + (max - min + 1) / 2; 144 145 item = &start[mid]; 146 147 prel31_addr = expand_prel31(item->offset); 148 func_addr = (vaddr_t)&item->offset + prel31_addr; 149 150 if (func_addr <= addr) { 151 min = mid; 152 } else { 153 max = mid - 1; 154 } 155 } 156 157 return &start[min]; 158 } 159 160 /* Reads the next byte from the instruction list */ 161 static bool unwind_exec_read_byte(struct unwind_state_arm32 *state, 162 uint32_t *ret_insn, bool kernel_stack) 163 { 164 uint32_t insn; 165 166 if (!copy_in(&insn, (void *)state->insn, sizeof(insn), kernel_stack)) 167 return false; 168 169 /* Read the unwind instruction */ 170 *ret_insn = (insn >> (state->byte * 8)) & 0xff; 171 172 /* Update the location of the next instruction */ 173 if (state->byte == 0) { 174 state->byte = 3; 175 state->insn += sizeof(uint32_t); 176 state->entries--; 177 } else 178 state->byte--; 179 180 return true; 181 } 182 183 static bool pop_vsp(uint32_t *reg, vaddr_t *vsp, bool kernel_stack, 184 vaddr_t stack, size_t stack_size) 185 { 186 if (!core_is_buffer_inside(*vsp, sizeof(*reg), stack, stack_size)) { 187 DMSG("vsp out of bounds %#" PRIxVA, *vsp); 188 return false; 189 } 190 if (!copy_in(reg, (void *)*vsp, sizeof(*reg), kernel_stack)) 191 return false; 192 (*vsp) += sizeof(*reg); 193 return true; 194 } 195 196 /* Executes the next instruction on the list */ 197 static bool unwind_exec_insn(struct unwind_state_arm32 *state, 198 bool kernel_stack, vaddr_t stack, 199 size_t stack_size) 200 { 201 uint32_t insn; 202 vaddr_t vsp = state->registers[SP]; 203 int update_vsp = 0; 204 205 /* Read the next instruction */ 206 if (!unwind_exec_read_byte(state, &insn, kernel_stack)) 207 return false; 208 209 if ((insn & INSN_VSP_MASK) == INSN_VSP_INC) { 210 state->registers[SP] += ((insn & INSN_VSP_SIZE_MASK) << 2) + 4; 211 212 } else if ((insn & INSN_VSP_MASK) == INSN_VSP_DEC) { 213 state->registers[SP] -= ((insn & INSN_VSP_SIZE_MASK) << 2) + 4; 214 215 } else if ((insn & INSN_STD_MASK) == INSN_POP_MASKED) { 216 uint32_t mask; 217 unsigned int reg; 218 219 /* Load the mask */ 220 if (!unwind_exec_read_byte(state, &mask, kernel_stack)) 221 return false; 222 mask |= (insn & INSN_STD_DATA_MASK) << 8; 223 224 /* We have a refuse to unwind instruction */ 225 if (mask == 0) 226 return false; 227 228 /* Update SP */ 229 update_vsp = 1; 230 231 /* Load the registers */ 232 for (reg = 4; mask && reg < 16; mask >>= 1, reg++) { 233 if (mask & 1) { 234 if (!pop_vsp(&state->registers[reg], &vsp, 235 kernel_stack, stack, stack_size)) 236 return false; 237 state->update_mask |= 1 << reg; 238 239 /* If we have updated SP kep its value */ 240 if (reg == SP) 241 update_vsp = 0; 242 } 243 } 244 245 } else if ((insn & INSN_STD_MASK) == INSN_VSP_REG && 246 ((insn & INSN_STD_DATA_MASK) != 13) && 247 ((insn & INSN_STD_DATA_MASK) != 15)) { 248 /* sp = register */ 249 state->registers[SP] = 250 state->registers[insn & INSN_STD_DATA_MASK]; 251 252 } else if ((insn & INSN_STD_MASK) == INSN_POP_COUNT) { 253 unsigned int count, reg; 254 255 /* Read how many registers to load */ 256 count = insn & INSN_POP_COUNT_MASK; 257 258 /* Update sp */ 259 update_vsp = 1; 260 261 /* Pop the registers */ 262 for (reg = 4; reg <= 4 + count; reg++) { 263 if (!pop_vsp(&state->registers[reg], &vsp, 264 kernel_stack, stack, stack_size)) 265 return false; 266 state->update_mask |= 1 << reg; 267 } 268 269 /* Check if we are in the pop r14 version */ 270 if ((insn & INSN_POP_TYPE_MASK) != 0) { 271 if (!pop_vsp(&state->registers[14], &vsp, kernel_stack, 272 stack, stack_size)) 273 return false; 274 } 275 276 } else if (insn == INSN_FINISH) { 277 /* Stop processing */ 278 state->entries = 0; 279 280 } else if (insn == INSN_POP_REGS) { 281 uint32_t mask; 282 unsigned int reg; 283 284 if (!unwind_exec_read_byte(state, &mask, kernel_stack)) 285 return false; 286 if (mask == 0 || (mask & 0xf0) != 0) 287 return false; 288 289 /* Update SP */ 290 update_vsp = 1; 291 292 /* Load the registers */ 293 for (reg = 0; mask && reg < 4; mask >>= 1, reg++) { 294 if (mask & 1) { 295 if (!pop_vsp(&state->registers[reg], &vsp, 296 kernel_stack, stack, stack_size)) 297 return false; 298 state->update_mask |= 1 << reg; 299 } 300 } 301 302 } else if ((insn & INSN_VSP_LARGE_INC_MASK) == INSN_VSP_LARGE_INC) { 303 uint32_t uleb128; 304 305 /* Read the increment value */ 306 if (!unwind_exec_read_byte(state, &uleb128, kernel_stack)) 307 return false; 308 309 state->registers[SP] += 0x204 + (uleb128 << 2); 310 311 } else { 312 /* We hit a new instruction that needs to be implemented */ 313 DMSG("Unhandled instruction %.2x\n", insn); 314 return false; 315 } 316 317 if (update_vsp) 318 state->registers[SP] = vsp; 319 320 return true; 321 } 322 323 /* Performs the unwind of a function */ 324 static bool unwind_tab(struct unwind_state_arm32 *state, bool kernel_stack, 325 vaddr_t stack, size_t stack_size) 326 { 327 uint32_t entry; 328 uint32_t insn; 329 330 /* Set PC to a known value */ 331 state->registers[PC] = 0; 332 333 if (!copy_in(&insn, (void *)state->insn, sizeof(insn), kernel_stack)) { 334 DMSG("Bad insn addr %p", (void *)state->insn); 335 return true; 336 } 337 338 /* Read the personality */ 339 entry = insn & ENTRY_MASK; 340 341 if (entry == ENTRY_ARM_SU16) { 342 state->byte = 2; 343 state->entries = 1; 344 } else if (entry == ENTRY_ARM_LU16) { 345 state->byte = 1; 346 state->entries = ((insn >> 16) & 0xFF) + 1; 347 } else { 348 DMSG("Unknown entry: %x\n", entry); 349 return true; 350 } 351 352 while (state->entries > 0) { 353 if (!unwind_exec_insn(state, kernel_stack, stack, stack_size)) 354 return true; 355 } 356 357 /* 358 * The program counter was not updated, load it from the link register. 359 */ 360 if (state->registers[PC] == 0) { 361 state->registers[PC] = state->registers[LR]; 362 363 /* 364 * If the program counter changed, flag it in the update mask. 365 */ 366 if (state->start_pc != state->registers[PC]) 367 state->update_mask |= 1 << PC; 368 } 369 370 return false; 371 } 372 373 bool unwind_stack_arm32(struct unwind_state_arm32 *state, vaddr_t exidx, 374 size_t exidx_sz, bool kernel_stack, vaddr_t stack, 375 size_t stack_size) 376 { 377 struct unwind_idx *index; 378 bool finished; 379 380 if (!exidx_sz) 381 return false; 382 383 /* Reset the mask of updated registers */ 384 state->update_mask = 0; 385 386 /* The pc value is correct and will be overwritten, save it */ 387 state->start_pc = state->registers[PC]; 388 389 /* Find the item to run */ 390 index = find_index(state->start_pc, exidx, exidx_sz); 391 392 finished = false; 393 if (index->insn != EXIDX_CANTUNWIND) { 394 if (index->insn & (1U << 31)) { 395 /* The data is within the instruction */ 396 state->insn = (vaddr_t)&index->insn; 397 } else { 398 /* A prel31 offset to the unwind table */ 399 state->insn = (vaddr_t)&index->insn + 400 expand_prel31(index->insn); 401 } 402 403 /* Run the unwind function */ 404 finished = unwind_tab(state, kernel_stack, stack, stack_size); 405 } 406 407 /* This is the top of the stack, finish */ 408 if (index->insn == EXIDX_CANTUNWIND) 409 finished = true; 410 411 return !finished; 412 } 413 414 static uint32_t offset_prel31(uint32_t addr, int32_t offset) 415 { 416 return (addr + offset) & 0x7FFFFFFFUL; 417 } 418 419 TEE_Result relocate_exidx(void *exidx, size_t exidx_sz, int32_t offset) 420 { 421 size_t num_items = exidx_sz / sizeof(struct unwind_idx); 422 struct unwind_idx *start = (struct unwind_idx *)exidx; 423 size_t n; 424 425 for (n = 0; n < num_items; n++) { 426 struct unwind_idx *item = &start[n]; 427 428 if (item->offset & BIT32(31)) 429 return TEE_ERROR_BAD_FORMAT; 430 431 /* Offset to the start of the function has to be adjusted */ 432 item->offset = offset_prel31(item->offset, offset); 433 434 if (item->insn == EXIDX_CANTUNWIND) 435 continue; 436 if (item->insn & BIT32(31)) { 437 /* insn is a table entry itself */ 438 continue; 439 } 440 /* 441 * insn is an offset to an entry in .ARM.extab so it has to be 442 * adjusted 443 */ 444 item->insn = offset_prel31(item->insn, offset); 445 } 446 return TEE_SUCCESS; 447 } 448 449 #if defined(CFG_UNWIND) && (TRACE_LEVEL > 0) 450 451 void print_stack_arm32(int level, struct unwind_state_arm32 *state, 452 vaddr_t exidx, size_t exidx_sz, bool kernel_stack, 453 vaddr_t stack, size_t stack_size) 454 { 455 trace_printf_helper_raw(level, true, "Call stack:"); 456 do { 457 trace_printf_helper_raw(level, true, " 0x%08" PRIx32, 458 state->registers[PC]); 459 } while (unwind_stack_arm32(state, exidx, exidx_sz, 460 kernel_stack, stack, stack_size)); 461 } 462 463 #endif 464 465 #if defined(CFG_UNWIND) && defined(ARM32) && (TRACE_LEVEL > 0) 466 467 void print_kernel_stack(int level) 468 { 469 struct unwind_state_arm32 state; 470 uaddr_t exidx = (vaddr_t)__exidx_start; 471 size_t exidx_sz = (vaddr_t)__exidx_end - (vaddr_t)__exidx_start; 472 vaddr_t stack = thread_stack_start(); 473 size_t stack_size = thread_stack_size(); 474 475 memset(&state, 0, sizeof(state)); 476 /* r7: Thumb-style frame pointer */ 477 state.registers[7] = read_r7(); 478 /* r11: ARM-style frame pointer */ 479 state.registers[FP] = read_fp(); 480 state.registers[SP] = read_sp(); 481 state.registers[LR] = read_lr(); 482 state.registers[PC] = (uint32_t)print_kernel_stack; 483 484 print_stack_arm32(level, &state, exidx, exidx_sz, 485 true /*kernel_stack*/, stack, stack_size); 486 } 487 488 #endif 489 490 #if defined(ARM32) 491 vaddr_t *unw_get_kernel_stack(void) 492 { 493 size_t n = 0; 494 size_t size = 0; 495 size_t exidx_sz = 0; 496 vaddr_t *tmp = NULL; 497 vaddr_t *addr = NULL; 498 struct unwind_state_arm32 state = { 0 }; 499 uaddr_t exidx = (vaddr_t)__exidx_start; 500 vaddr_t stack = thread_stack_start(); 501 size_t stack_size = thread_stack_size(); 502 503 if (SUB_OVERFLOW((vaddr_t)__exidx_end, (vaddr_t)__exidx_start, 504 &exidx_sz)) 505 return NULL; 506 507 /* r7: Thumb-style frame pointer */ 508 state.registers[7] = read_r7(); 509 /* r11: ARM-style frame pointer */ 510 state.registers[FP] = read_fp(); 511 state.registers[SP] = read_sp(); 512 state.registers[LR] = read_lr(); 513 state.registers[PC] = (uint32_t)unw_get_kernel_stack; 514 515 while (unwind_stack_arm32(&state, exidx, exidx_sz, 516 true /*kernel stack*/, stack, stack_size)) { 517 tmp = unw_grow(addr, &size, (n + 1) * sizeof(vaddr_t)); 518 if (!tmp) 519 goto err; 520 addr = tmp; 521 addr[n] = state.registers[PC]; 522 n++; 523 } 524 525 if (addr) { 526 tmp = unw_grow(addr, &size, (n + 1) * sizeof(vaddr_t)); 527 if (!tmp) 528 goto err; 529 addr = tmp; 530 addr[n] = 0; 531 } 532 533 return addr; 534 err: 535 EMSG("Out of memory"); 536 free(addr); 537 return NULL; 538 } 539 #endif 540