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