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