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