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