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
expand_prel31(uint32_t prel31)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
module_search(linker_file_t lf,void * context)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 *
find_index(uint32_t addr,int search_modules)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
unwind_exec_read_byte(struct unwind_state * state)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
unwind_exec_insn(struct unwind_state * state)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
unwind_tab(struct unwind_state * state)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
unwind_stack_one(struct unwind_state * state,int can_lock)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 }
421