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