1 /* 2 * Copyright 2015 Linaro Limited 3 * Copyright 2013-2014 Andrew Turner. 4 * Copyright 2013-2014 Ian Lepore. 5 * Copyright 2013-2014 Rui Paulo. 6 * Copyright 2013 Eitan Adler. 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions are 11 * met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE 23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 26 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #include <arm.h> 33 #include <kernel/linker.h> 34 #include <kernel/misc.h> 35 #include <kernel/unwind.h> 36 #include <string.h> 37 #include <trace.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 /* Expand a 31-bit signed value to a 32-bit signed value */ 100 static int32_t expand_prel31(uint32_t prel31) 101 { 102 return prel31 | SHIFT_U32(prel31 & BIT32(30), 1); 103 } 104 105 /* 106 * Perform a binary search of the index table to find the function 107 * with the largest address that doesn't exceed addr. 108 */ 109 static struct unwind_idx *find_index(uint32_t addr, vaddr_t exidx, 110 size_t exidx_sz) 111 { 112 vaddr_t idx_start, idx_end; 113 unsigned int min, mid, max; 114 struct unwind_idx *start; 115 struct unwind_idx *item; 116 int32_t prel31_addr; 117 vaddr_t func_addr; 118 119 start = (struct unwind_idx *)exidx; 120 idx_start = exidx; 121 idx_end = exidx + exidx_sz; 122 123 min = 0; 124 max = (idx_end - idx_start) / sizeof(struct unwind_idx); 125 126 while (min != max) { 127 mid = min + (max - min + 1) / 2; 128 129 item = &start[mid]; 130 131 prel31_addr = expand_prel31(item->offset); 132 func_addr = (vaddr_t)&item->offset + prel31_addr; 133 134 if (func_addr <= addr) { 135 min = mid; 136 } else { 137 max = mid - 1; 138 } 139 } 140 141 return &start[min]; 142 } 143 144 /* Reads the next byte from the instruction list */ 145 static uint8_t unwind_exec_read_byte(struct unwind_state_arm32 *state) 146 { 147 uint8_t insn; 148 149 /* Read the unwind instruction */ 150 insn = (*state->insn) >> (state->byte * 8); 151 152 /* Update the location of the next instruction */ 153 if (state->byte == 0) { 154 state->byte = 3; 155 state->insn++; 156 state->entries--; 157 } else 158 state->byte--; 159 160 return insn; 161 } 162 163 /* Executes the next instruction on the list */ 164 static bool unwind_exec_insn(struct unwind_state_arm32 *state) 165 { 166 unsigned int insn; 167 uint32_t *vsp = (uint32_t *)(uintptr_t)state->registers[SP]; 168 int update_vsp = 0; 169 170 /* This should never happen */ 171 if (state->entries == 0) 172 return false; 173 174 /* Read the next instruction */ 175 insn = unwind_exec_read_byte(state); 176 177 if ((insn & INSN_VSP_MASK) == INSN_VSP_INC) { 178 state->registers[SP] += ((insn & INSN_VSP_SIZE_MASK) << 2) + 4; 179 180 } else if ((insn & INSN_VSP_MASK) == INSN_VSP_DEC) { 181 state->registers[SP] -= ((insn & INSN_VSP_SIZE_MASK) << 2) + 4; 182 183 } else if ((insn & INSN_STD_MASK) == INSN_POP_MASKED) { 184 unsigned int mask, reg; 185 186 /* Load the mask */ 187 mask = unwind_exec_read_byte(state); 188 mask |= (insn & INSN_STD_DATA_MASK) << 8; 189 190 /* We have a refuse to unwind instruction */ 191 if (mask == 0) 192 return false; 193 194 /* Update SP */ 195 update_vsp = 1; 196 197 /* Load the registers */ 198 for (reg = 4; mask && reg < 16; mask >>= 1, reg++) { 199 if (mask & 1) { 200 state->registers[reg] = *vsp++; 201 state->update_mask |= 1 << reg; 202 203 /* If we have updated SP kep its value */ 204 if (reg == SP) 205 update_vsp = 0; 206 } 207 } 208 209 } else if ((insn & INSN_STD_MASK) == INSN_VSP_REG && 210 ((insn & INSN_STD_DATA_MASK) != 13) && 211 ((insn & INSN_STD_DATA_MASK) != 15)) { 212 /* sp = register */ 213 state->registers[SP] = 214 state->registers[insn & INSN_STD_DATA_MASK]; 215 216 } else if ((insn & INSN_STD_MASK) == INSN_POP_COUNT) { 217 unsigned int count, reg; 218 219 /* Read how many registers to load */ 220 count = insn & INSN_POP_COUNT_MASK; 221 222 /* Update sp */ 223 update_vsp = 1; 224 225 /* Pop the registers */ 226 for (reg = 4; reg <= 4 + count; reg++) { 227 state->registers[reg] = *vsp++; 228 state->update_mask |= 1 << reg; 229 } 230 231 /* Check if we are in the pop r14 version */ 232 if ((insn & INSN_POP_TYPE_MASK) != 0) { 233 state->registers[14] = *vsp++; 234 } 235 236 } else if (insn == INSN_FINISH) { 237 /* Stop processing */ 238 state->entries = 0; 239 240 } else if (insn == INSN_POP_REGS) { 241 unsigned int mask, reg; 242 243 mask = unwind_exec_read_byte(state); 244 if (mask == 0 || (mask & 0xf0) != 0) 245 return false; 246 247 /* Update SP */ 248 update_vsp = 1; 249 250 /* Load the registers */ 251 for (reg = 0; mask && reg < 4; mask >>= 1, reg++) { 252 if (mask & 1) { 253 state->registers[reg] = *vsp++; 254 state->update_mask |= 1 << reg; 255 } 256 } 257 258 } else if ((insn & INSN_VSP_LARGE_INC_MASK) == INSN_VSP_LARGE_INC) { 259 unsigned int uleb128; 260 261 /* Read the increment value */ 262 uleb128 = unwind_exec_read_byte(state); 263 264 state->registers[SP] += 0x204 + (uleb128 << 2); 265 266 } else { 267 /* We hit a new instruction that needs to be implemented */ 268 DMSG("Unhandled instruction %.2x\n", insn); 269 return false; 270 } 271 272 if (update_vsp) { 273 state->registers[SP] = (uint32_t)(uintptr_t)vsp; 274 } 275 276 return true; 277 } 278 279 /* Performs the unwind of a function */ 280 static bool unwind_tab(struct unwind_state_arm32 *state) 281 { 282 uint32_t entry; 283 284 /* Set PC to a known value */ 285 state->registers[PC] = 0; 286 287 /* Read the personality */ 288 entry = *state->insn & ENTRY_MASK; 289 290 if (entry == ENTRY_ARM_SU16) { 291 state->byte = 2; 292 state->entries = 1; 293 } else if (entry == ENTRY_ARM_LU16) { 294 state->byte = 1; 295 state->entries = ((*state->insn >> 16) & 0xFF) + 1; 296 } else { 297 DMSG("Unknown entry: %x\n", entry); 298 return true; 299 } 300 301 while (state->entries > 0) { 302 if (!unwind_exec_insn(state)) 303 return true; 304 } 305 306 /* 307 * The program counter was not updated, load it from the link register. 308 */ 309 if (state->registers[PC] == 0) { 310 state->registers[PC] = state->registers[LR]; 311 312 /* 313 * If the program counter changed, flag it in the update mask. 314 */ 315 if (state->start_pc != state->registers[PC]) 316 state->update_mask |= 1 << PC; 317 } 318 319 return false; 320 } 321 322 bool unwind_stack_arm32(struct unwind_state_arm32 *state, uaddr_t exidx, 323 size_t exidx_sz) 324 { 325 struct unwind_idx *index; 326 bool finished; 327 328 /* Reset the mask of updated registers */ 329 state->update_mask = 0; 330 331 /* The pc value is correct and will be overwritten, save it */ 332 state->start_pc = state->registers[PC]; 333 334 /* Find the item to run */ 335 index = find_index(state->start_pc, exidx, exidx_sz); 336 337 finished = false; 338 if (index->insn != EXIDX_CANTUNWIND) { 339 if (index->insn & (1U << 31)) { 340 /* The data is within the instruction */ 341 state->insn = &index->insn; 342 } else { 343 /* A prel31 offset to the unwind table */ 344 state->insn = (uint32_t *) 345 ((uintptr_t)&index->insn + 346 expand_prel31(index->insn)); 347 } 348 /* Run the unwind function */ 349 finished = unwind_tab(state); 350 } 351 352 /* This is the top of the stack, finish */ 353 if (index->insn == EXIDX_CANTUNWIND) 354 finished = true; 355 356 return !finished; 357 } 358 359 #if defined(CFG_UNWIND) && (TRACE_LEVEL > 0) 360 361 void print_stack_arm32(int level, struct unwind_state_arm32 *state, uaddr_t exidx, 362 size_t exidx_sz) 363 { 364 trace_printf_helper_raw(level, true, "Call stack:"); 365 do { 366 trace_printf_helper_raw(level, true, " 0x%08" PRIx32, 367 state->registers[PC]); 368 } while (unwind_stack_arm32(state, exidx, exidx_sz)); 369 } 370 371 #endif 372 373 #if defined(CFG_UNWIND) && defined(ARM32) && (TRACE_LEVEL > 0) 374 375 void print_kernel_stack(int level) 376 { 377 struct unwind_state_arm32 state; 378 uaddr_t exidx = (vaddr_t)__exidx_start; 379 size_t exidx_sz = (vaddr_t)__exidx_end - (vaddr_t)__exidx_start; 380 381 memset(state.registers, 0, sizeof(state.registers)); 382 /* r7: Thumb-style frame pointer */ 383 state.registers[7] = read_r7(); 384 /* r11: ARM-style frame pointer */ 385 state.registers[FP] = read_fp(); 386 state.registers[SP] = read_sp(); 387 state.registers[LR] = read_lr(); 388 state.registers[PC] = (uint32_t)print_kernel_stack; 389 390 print_stack_arm32(level, &state, exidx, exidx_sz); 391 } 392 393 #endif 394