sys/arm/arm/unwind.c

   1 /*
   2  * Copyright 2013-2014 Andrew Turner.
   3  * Copyright 2013-2014 Ian Lepore.
   4  * Copyright 2013-2014 Rui Paulo.
   5  * Copyright 2013 Eitan Adler.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions are
  10  * met:
  11  *
  12  *  1. Redistributions of source code must retain the above copyright
  13  *     notice, this list of conditions and the following disclaimer.
  14  *  2. Redistributions in binary form must reproduce the above copyright
  15  *     notice, this list of conditions and the following disclaimer in the
  16  *     documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  25  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  26  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  27  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  28  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include <sys/cdefs.h>
  32 __FBSDID("$FreeBSD$");
  33
  34 #include <sys/param.h>
  35 #include <sys/systm.h>
  36 #include <sys/linker.h>
  37
  38 #include <machine/stack.h>
  39
  40 #include "linker_if.h"
  41
  42 /*
  43  * Definitions for the instruction interpreter.
  44  *
  45  * The ARM EABI specifies how to perform the frame unwinding in the
  46  * Exception Handling ABI for the ARM Architecture document. To perform
  47  * the unwind we need to know the initial frame pointer, stack pointer,
  48  * link register and program counter. We then find the entry within the
  49  * index table that points to the function the program counter is within.
  50  * This gives us either a list of three instructions to process, a 31-bit
  51  * relative offset to a table of instructions, or a value telling us
  52  * we can't unwind any further.
  53  *
  54  * When we have the instructions to process we need to decode them
  55  * following table 4 in section 9.3. This describes a collection of bit
  56  * patterns to encode that steps to take to update the stack pointer and
  57  * link register to the correct values at the start of the function.
  58  */
  59
  60 /* A special case when we are unable to unwind past this function */
  61 #define EXIDX_CANTUNWIND        1
  62
  63 /*
  64  * These are set in the linker script. Their addresses will be
  65  * either the start or end of the exception table or index.
  66  */
  67 extern int exidx_start, exidx_end;
  68
  69 /*
  70  * Entry types.
  71  * These are the only entry types that have been seen in the kernel.
  72  */
  73 #define ENTRY_MASK      0xff000000
  74 #define ENTRY_ARM_SU16  0x80000000
  75 #define ENTRY_ARM_LU16  0x81000000
  76
  77 /* Instruction masks. */
  78 #define INSN_VSP_MASK           0xc0
  79 #define INSN_VSP_SIZE_MASK      0x3f
  80 #define INSN_STD_MASK           0xf0
  81 #define INSN_STD_DATA_MASK      0x0f
  82 #define INSN_POP_TYPE_MASK      0x08
  83 #define INSN_POP_COUNT_MASK     0x07
  84 #define INSN_VSP_LARGE_INC_MASK 0xff
  85
  86 /* Instruction definitions */
  87 #define INSN_VSP_INC            0x00
  88 #define INSN_VSP_DEC            0x40
  89 #define INSN_POP_MASKED         0x80
  90 #define INSN_VSP_REG            0x90
  91 #define INSN_POP_COUNT          0xa0
  92 #define INSN_FINISH             0xb0
  93 #define INSN_POP_REGS           0xb1
  94 #define INSN_VSP_LARGE_INC      0xb2
  95
  96 /* An item in the exception index table */
  97 struct unwind_idx {
  98         uint32_t offset;
  99         uint32_t insn;
 100 };
 101
 102 /* Expand a 31-bit signed value to a 32-bit signed value */
 103 static __inline int32_t
 104 expand_prel31(uint32_t prel31)
 105 {
 106
 107         return ((int32_t)(prel31 & 0x7fffffffu) << 1) / 2;
 108 }
 109
 110 struct search_context {
 111         uint32_t addr;
 112         caddr_t exidx_start;
 113         caddr_t exidx_end;
 114 };
 115
 116 static int
 117 module_search(linker_file_t lf, void *context)
 118 {
 119         struct search_context *sc = context;
 120         linker_symval_t symval;
 121         c_linker_sym_t sym;
 122
 123         if (lf->address <= (caddr_t)sc->addr &&
 124             (lf->address + lf->size) >= (caddr_t)sc->addr) {
 125                 if ((LINKER_LOOKUP_SYMBOL(lf, "__exidx_start", &sym) == 0 ||
 126                     LINKER_LOOKUP_SYMBOL(lf, "exidx_start", &sym) == 0) &&
 127                     LINKER_SYMBOL_VALUES(lf, sym, &symval) == 0)
 128                         sc->exidx_start = symval.value;
 129
 130                 if ((LINKER_LOOKUP_SYMBOL(lf, "__exidx_end", &sym) == 0 ||
 131                     LINKER_LOOKUP_SYMBOL(lf, "exidx_end", &sym) == 0) &&
 132                     LINKER_SYMBOL_VALUES(lf, sym, &symval) == 0)
 133                         sc->exidx_end = symval.value;
 134
 135                 if (sc->exidx_start != NULL && sc->exidx_end != NULL)
 136                         return (1);
 137                 panic("Invalid module %s, no unwind tables\n", lf->filename);
 138         }
 139         return (0);
 140 }
 141
 142 /*
 143  * Perform a binary search of the index table to find the function
 144  * with the largest address that doesn't exceed addr.
 145  */
 146 static struct unwind_idx *
 147 find_index(uint32_t addr, int search_modules)
 148 {
 149         struct search_context sc;
 150         caddr_t idx_start, idx_end;
 151         unsigned int min, mid, max;
 152         struct unwind_idx *start;
 153         struct unwind_idx *item;
 154         int32_t prel31_addr;
 155         uint32_t func_addr;
 156
 157         start = (struct unwind_idx *)&exidx_start;
 158         idx_start = (caddr_t)&exidx_start;
 159         idx_end = (caddr_t)&exidx_end;
 160
 161         /* This may acquire a lock */
 162         if (search_modules) {
 163                 bzero(&sc, sizeof(sc));
 164                 sc.addr = addr;
 165                 if (linker_file_foreach(module_search, &sc) != 0 &&
 166                    sc.exidx_start != NULL && sc.exidx_end != NULL) {
 167                         start = (struct unwind_idx *)sc.exidx_start;
 168                         idx_start = sc.exidx_start;
 169                         idx_end = sc.exidx_end;
 170                 }
 171         }
 172
 173         min = 0;
 174         max = (idx_end - idx_start) / sizeof(struct unwind_idx);
 175
 176         while (min != max) {
 177                 mid = min + (max - min + 1) / 2;
 178
 179                 item = &start[mid];
 180
 181                 prel31_addr = expand_prel31(item->offset);
 182                 func_addr = (uint32_t)&item->offset + prel31_addr;
 183
 184                 if (func_addr <= addr) {
 185                         min = mid;
 186                 } else {
 187                         max = mid - 1;
 188                 }
 189         }
 190
 191         return &start[min];
 192 }
 193
 194 /* Reads the next byte from the instruction list */
 195 static uint8_t
 196 unwind_exec_read_byte(struct unwind_state *state)
 197 {
 198         uint8_t insn;
 199
 200         /* Read the unwind instruction */
 201         insn = (*state->insn) >> (state->byte * 8);
 202
 203         /* Update the location of the next instruction */
 204         if (state->byte == 0) {
 205                 state->byte = 3;
 206                 state->insn++;
 207                 state->entries--;
 208         } else
 209                 state->byte--;
 210
 211         return insn;
 212 }
 213
 214 /* Executes the next instruction on the list */
 215 static int
 216 unwind_exec_insn(struct unwind_state *state)
 217 {
 218         unsigned int insn;
 219         uint32_t *vsp = (uint32_t *)state->registers[SP];
 220         int update_vsp = 0;
 221
 222         /* This should never happen */
 223         if (state->entries == 0)
 224                 return 1;
 225
 226         /* Read the next instruction */
 227         insn = unwind_exec_read_byte(state);
 228
 229         if ((insn & INSN_VSP_MASK) == INSN_VSP_INC) {
 230                 state->registers[SP] += ((insn & INSN_VSP_SIZE_MASK) << 2) + 4;
 231
 232         } else if ((insn & INSN_VSP_MASK) == INSN_VSP_DEC) {
 233                 state->registers[SP] -= ((insn & INSN_VSP_SIZE_MASK) << 2) + 4;
 234
 235         } else if ((insn & INSN_STD_MASK) == INSN_POP_MASKED) {
 236                 unsigned int mask, reg;
 237
 238                 /* Load the mask */
 239                 mask = unwind_exec_read_byte(state);
 240                 mask |= (insn & INSN_STD_DATA_MASK) << 8;
 241
 242                 /* We have a refuse to unwind instruction */
 243                 if (mask == 0)
 244                         return 1;
 245
 246                 /* Update SP */
 247                 update_vsp = 1;
 248
 249                 /* Load the registers */
 250                 for (reg = 4; mask && reg < 16; mask >>= 1, reg++) {
 251                         if (mask & 1) {
 252                                 state->registers[reg] = *vsp++;
 253                                 state->update_mask |= 1 << reg;
 254
 255                                 /* If we have updated SP kep its value */
 256                                 if (reg == SP)
 257                                         update_vsp = 0;
 258                         }
 259                 }
 260
 261         } else if ((insn & INSN_STD_MASK) == INSN_VSP_REG &&
 262             ((insn & INSN_STD_DATA_MASK) != 13) &&
 263             ((insn & INSN_STD_DATA_MASK) != 15)) {
 264                 /* sp = register */
 265                 state->registers[SP] =
 266                     state->registers[insn & INSN_STD_DATA_MASK];
 267
 268         } else if ((insn & INSN_STD_MASK) == INSN_POP_COUNT) {
 269                 unsigned int count, reg;
 270
 271                 /* Read how many registers to load */
 272                 count = insn & INSN_POP_COUNT_MASK;
 273
 274                 /* Update sp */
 275                 update_vsp = 1;
 276
 277                 /* Pop the registers */
 278                 for (reg = 4; reg <= 4 + count; reg++) {
 279                         state->registers[reg] = *vsp++;
 280                         state->update_mask |= 1 << reg;
 281                 }
 282
 283                 /* Check if we are in the pop r14 version */
 284                 if ((insn & INSN_POP_TYPE_MASK) != 0) {
 285                         state->registers[14] = *vsp++;
 286                 }
 287
 288         } else if (insn == INSN_FINISH) {
 289                 /* Stop processing */
 290                 state->entries = 0;
 291
 292         } else if (insn == INSN_POP_REGS) {
 293                 unsigned int mask, reg;
 294
 295                 mask = unwind_exec_read_byte(state);
 296                 if (mask == 0 || (mask & 0xf0) != 0)
 297                         return 1;
 298
 299                 /* Update SP */
 300                 update_vsp = 1;
 301
 302                 /* Load the registers */
 303                 for (reg = 0; mask && reg < 4; mask >>= 1, reg++) {
 304                         if (mask & 1) {
 305                                 state->registers[reg] = *vsp++;
 306                                 state->update_mask |= 1 << reg;
 307                         }
 308                 }
 309
 310         } else if ((insn & INSN_VSP_LARGE_INC_MASK) == INSN_VSP_LARGE_INC) {
 311                 unsigned int uleb128;
 312
 313                 /* Read the increment value */
 314                 uleb128 = unwind_exec_read_byte(state);
 315
 316                 state->registers[SP] += 0x204 + (uleb128 << 2);
 317
 318         } else {
 319                 /* We hit a new instruction that needs to be implemented */
 320 #if 0
 321                 db_printf("Unhandled instruction %.2x\n", insn);
 322 #endif
 323                 return 1;
 324         }
 325
 326         if (update_vsp) {
 327                 state->registers[SP] = (uint32_t)vsp;
 328         }
 329
 330 #if 0
 331         db_printf("fp = %08x, sp = %08x, lr = %08x, pc = %08x\n",
 332             state->registers[FP], state->registers[SP], state->registers[LR],
 333             state->registers[PC]);
 334 #endif
 335
 336         return 0;
 337 }
 338
 339 /* Performs the unwind of a function */
 340 static int
 341 unwind_tab(struct unwind_state *state)
 342 {
 343         uint32_t entry;
 344
 345         /* Set PC to a known value */
 346         state->registers[PC] = 0;
 347
 348         /* Read the personality */
 349         entry = *state->insn & ENTRY_MASK;
 350
 351         if (entry == ENTRY_ARM_SU16) {
 352                 state->byte = 2;
 353                 state->entries = 1;
 354         } else if (entry == ENTRY_ARM_LU16) {
 355                 state->byte = 1;
 356                 state->entries = ((*state->insn >> 16) & 0xFF) + 1;
 357         } else {
 358 #if 0
 359                 db_printf("Unknown entry: %x\n", entry);
 360 #endif
 361                 return 1;
 362         }
 363
 364         while (state->entries > 0) {
 365                 if (unwind_exec_insn(state) != 0)
 366                         return 1;
 367         }
 368
 369         /*
 370          * The program counter was not updated, load it from the link register.
 371          */
 372         if (state->registers[PC] == 0) {
 373                 state->registers[PC] = state->registers[LR];
 374
 375                 /*
 376                  * If the program counter changed, flag it in the update mask.
 377                  */
 378                 if (state->start_pc != state->registers[PC])
 379                         state->update_mask |= 1 << PC;
 380         }
 381
 382         return 0;
 383 }
 384
 385 int
 386 unwind_stack_one(struct unwind_state *state, int can_lock)
 387 {
 388         struct unwind_idx *index;
 389         int finished;
 390
 391         /* Reset the mask of updated registers */
 392         state->update_mask = 0;
 393
 394         /* The pc value is correct and will be overwritten, save it */
 395         state->start_pc = state->registers[PC];
 396
 397         /* Find the item to run */
 398         index = find_index(state->start_pc, can_lock);
 399
 400         finished = 0;
 401         if (index->insn != EXIDX_CANTUNWIND) {
 402                 if (index->insn & (1U << 31)) {
 403                         /* The data is within the instruction */
 404                         state->insn = &index->insn;
 405                 } else {
 406                         /* A prel31 offset to the unwind table */
 407                         state->insn = (uint32_t *)
 408                             ((uintptr_t)&index->insn +
 409                              expand_prel31(index->insn));
 410                 }
 411                 /* Run the unwind function */
 412                 finished = unwind_tab(state);
 413         }
 414
 415         /* This is the top of the stack, finish */
 416         if (index->insn == EXIDX_CANTUNWIND)
 417                 finished = 1;
 418
 419         return (finished);
 420 }