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/param.h>
32 #include <sys/kernel.h>
33 #include <sys/linker.h>
34 #include <sys/malloc.h>
35 #include <sys/proc.h>
36 #include <sys/queue.h>
37 #include <sys/systm.h>
38
39 #include <machine/machdep.h>
40 #include <machine/stack.h>
41
42 #include "linker_if.h"
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 * Local cache of unwind info for loaded modules.
100 *
101 * To unwind the stack through the code in a loaded module, we need to access
102 * the module's exidx unwind data. To locate that data, one must search the
103 * elf section headers for the SHT_ARM_EXIDX section. Those headers are
104 * available at the time the module is being loaded, but are discarded by time
105 * the load process has completed. Code in kern/link_elf.c locates the data we
106 * need and stores it into the linker_file structure before calling the arm
107 * machdep routine for handling loaded modules (in arm/elf_machdep.c). That
108 * function calls into this code to pass along the unwind info, which we save
109 * into one of these module_info structures.
110 *
111 * Because we have to help stack(9) gather stack info at any time, including in
112 * contexts where sleeping is not allowed, we cannot use linker_file_foreach()
113 * to walk the kernel's list of linker_file structs, because doing so requires
114 * acquiring an exclusive sx_lock. So instead, we keep a local list of these
115 * structures, one for each loaded module (and one for the kernel itself that we
116 * synthesize at init time). New entries are added to the end of this list as
117 * needed, but entries are never deleted from the list. Instead, they are
118 * cleared out in-place to mark them as unused. That means the code doing stack
119 * unwinding can always safely walk the list without locking, because the
120 * structure of the list never changes in a way that would cause the walker to
121 * follow a bad link.
122 *
123 * A cleared-out entry on the list has module start=UINTPTR_MAX and end=0, so
124 * start <= addr < end cannot be true for any value of addr being searched for.
125 * We also don't have to worry about races where we look up the unwind info just
126 * before a module is unloaded and try to access it concurrently with or just
127 * after the unloading happens in another thread, because that means the path of
128 * execution leads through a now-unloaded module, and that's already well into
129 * undefined-behavior territory.
130 *
131 * List entries marked as unused get reused when new modules are loaded. We
132 * don't worry about holding a few unused bytes of memory in the list after
133 * unloading a module.
134 */
135 struct module_info {
136 uintptr_t module_start; /* Start of loaded module */
137 uintptr_t module_end; /* End of loaded module */
138 uintptr_t exidx_start; /* Start of unwind data */
139 uintptr_t exidx_end; /* End of unwind data */
140 STAILQ_ENTRY(module_info)
141 link; /* Link to next entry */
142 };
143 static STAILQ_HEAD(, module_info) module_list;
144
145 /*
146 * Hide ugly casting in somewhat-less-ugly macros.
147 * CADDR - cast a pointer or number to caddr_t.
148 * UADDR - cast a pointer or number to uintptr_t.
149 */
150 #define CADDR(addr) ((caddr_t)(void*)(uintptr_t)(addr))
151 #define UADDR(addr) ((uintptr_t)(addr))
152
153 /*
154 * Clear the info in an existing module_info entry on the list. The
155 * module_start/end addresses are set to values that cannot match any real
156 * memory address. The entry remains on the list, but will be ignored until it
157 * is populated with new data.
158 */
159 static void
clear_module_info(struct module_info * info)160 clear_module_info(struct module_info *info)
161 {
162 info->module_start = UINTPTR_MAX;
163 info->module_end = 0;
164 }
165
166 /*
167 * Populate an existing module_info entry (which is already on the list) with
168 * the info for a new module.
169 */
170 static void
populate_module_info(struct module_info * info,linker_file_t lf)171 populate_module_info(struct module_info *info, linker_file_t lf)
172 {
173
174 /*
175 * Careful! The module_start and module_end fields must not be set
176 * until all other data in the structure is valid.
177 */
178 info->exidx_start = UADDR(lf->exidx_addr);
179 info->exidx_end = UADDR(lf->exidx_addr) + lf->exidx_size;
180 info->module_start = UADDR(lf->address);
181 info->module_end = UADDR(lf->address) + lf->size;
182 }
183
184 /*
185 * Create a new empty module_info entry and add it to the tail of the list.
186 */
187 static struct module_info *
create_module_info(void)188 create_module_info(void)
189 {
190 struct module_info *info;
191
192 info = malloc(sizeof(*info), M_CACHE, M_WAITOK | M_ZERO);
193 clear_module_info(info);
194 STAILQ_INSERT_TAIL(&module_list, info, link);
195 return (info);
196 }
197
198 /*
199 * Search for a module_info entry on the list whose address range contains the
200 * given address. If the search address is zero (no module will be loaded at
201 * zero), then we're looking for an empty item to reuse, which is indicated by
202 * module_start being set to UINTPTR_MAX in the entry.
203 */
204 static struct module_info *
find_module_info(uintptr_t addr)205 find_module_info(uintptr_t addr)
206 {
207 struct module_info *info;
208
209 STAILQ_FOREACH(info, &module_list, link) {
210 if ((addr >= info->module_start && addr < info->module_end) ||
211 (addr == 0 && info->module_start == UINTPTR_MAX))
212 return (info);
213 }
214 return (NULL);
215 }
216
217 /*
218 * Handle the loading of a new module by populating a module_info for it. This
219 * is called for both preloaded and dynamically loaded modules.
220 */
221 void
unwind_module_loaded(struct linker_file * lf)222 unwind_module_loaded(struct linker_file *lf)
223 {
224 struct module_info *info;
225
226 /*
227 * A module that contains only data may have no unwind info; don't
228 * create any module info for it.
229 */
230 if (lf->exidx_size == 0)
231 return;
232
233 /*
234 * Find an unused entry in the existing list to reuse. If we don't find
235 * one, create a new one and link it into the list. This is the only
236 * place the module_list is modified. Adding a new entry to the list
237 * will not perturb any other threads currently walking the list. This
238 * function is invoked while kern_linker is still holding its lock
239 * to prevent its module list from being modified, so we don't have to
240 * worry about racing other threads doing an insert concurrently.
241 */
242 if ((info = find_module_info(0)) == NULL) {
243 info = create_module_info();
244 }
245 populate_module_info(info, lf);
246 }
247
248 /* Handle the unloading of a module. */
249 void
unwind_module_unloaded(struct linker_file * lf)250 unwind_module_unloaded(struct linker_file *lf)
251 {
252 struct module_info *info;
253
254 /*
255 * A module that contains only data may have no unwind info and there
256 * won't be a list entry for it.
257 */
258 if (lf->exidx_size == 0)
259 return;
260
261 /*
262 * When a module is unloaded, we clear the info out of its entry in the
263 * module list, making that entry available for later reuse.
264 */
265 if ((info = find_module_info(UADDR(lf->address))) == NULL) {
266 printf("arm unwind: module '%s' not on list at unload time\n",
267 lf->filename);
268 return;
269 }
270 clear_module_info(info);
271 }
272
273 /*
274 * Initialization must run fairly early, as soon as malloc(9) is available, and
275 * definitely before witness, which uses stack(9). We synthesize a module_info
276 * entry for the kernel, because unwind_module_loaded() doesn't get called for
277 * it. Also, it is unlike other modules in that the elf metadata for locating
278 * the unwind tables might be stripped, so instead we have to use the
279 * _exidx_start/end symbols created by ldscript.arm.
280 */
281 static int
module_info_init(void * arg __unused)282 module_info_init(void *arg __unused)
283 {
284 struct linker_file thekernel;
285
286 STAILQ_INIT(&module_list);
287
288 thekernel.filename = "kernel";
289 thekernel.address = CADDR(&_start);
290 thekernel.size = UADDR(&_end) - UADDR(&_start);
291 thekernel.exidx_addr = CADDR(&_exidx_start);
292 thekernel.exidx_size = UADDR(&_exidx_end) - UADDR(&_exidx_start);
293 populate_module_info(create_module_info(), &thekernel);
294
295 return (0);
296 }
297 SYSINIT(unwind_init, SI_SUB_KMEM, SI_ORDER_ANY, module_info_init, NULL);
298
299 /* Expand a 31-bit signed value to a 32-bit signed value */
300 static __inline int32_t
expand_prel31(uint32_t prel31)301 expand_prel31(uint32_t prel31)
302 {
303
304 return ((int32_t)(prel31 & 0x7fffffffu) << 1) / 2;
305 }
306
307 /*
308 * Perform a binary search of the index table to find the function
309 * with the largest address that doesn't exceed addr.
310 */
311 static struct unwind_idx *
find_index(uint32_t addr)312 find_index(uint32_t addr)
313 {
314 struct module_info *info;
315 unsigned int min, mid, max;
316 struct unwind_idx *start;
317 struct unwind_idx *item;
318 int32_t prel31_addr;
319 uint32_t func_addr;
320
321 info = find_module_info(addr);
322 if (info == NULL)
323 return NULL;
324
325 min = 0;
326 max = (info->exidx_end - info->exidx_start) / sizeof(struct unwind_idx);
327 start = (struct unwind_idx *)CADDR(info->exidx_start);
328
329 while (min != max) {
330 mid = min + (max - min + 1) / 2;
331
332 item = &start[mid];
333
334 prel31_addr = expand_prel31(item->offset);
335 func_addr = (uint32_t)&item->offset + prel31_addr;
336
337 if (func_addr <= addr) {
338 min = mid;
339 } else {
340 max = mid - 1;
341 }
342 }
343
344 return &start[min];
345 }
346
347 /* Reads the next byte from the instruction list */
348 static uint8_t
unwind_exec_read_byte(struct unwind_state * state)349 unwind_exec_read_byte(struct unwind_state *state)
350 {
351 uint8_t insn;
352
353 /* Read the unwind instruction */
354 insn = (*state->insn) >> (state->byte * 8);
355
356 /* Update the location of the next instruction */
357 if (state->byte == 0) {
358 state->byte = 3;
359 state->insn++;
360 state->entries--;
361 } else
362 state->byte--;
363
364 return insn;
365 }
366
367 /* Executes the next instruction on the list */
368 static int
unwind_exec_insn(struct unwind_state * state)369 unwind_exec_insn(struct unwind_state *state)
370 {
371 struct thread *td = curthread;
372 unsigned int insn;
373 uint32_t *vsp = (uint32_t *)state->registers[SP];
374 int update_vsp = 0;
375
376 /* This should never happen */
377 if (state->entries == 0)
378 return 1;
379
380 /* Read the next instruction */
381 insn = unwind_exec_read_byte(state);
382
383 if ((insn & INSN_VSP_MASK) == INSN_VSP_INC) {
384 state->registers[SP] += ((insn & INSN_VSP_SIZE_MASK) << 2) + 4;
385
386 } else if ((insn & INSN_VSP_MASK) == INSN_VSP_DEC) {
387 state->registers[SP] -= ((insn & INSN_VSP_SIZE_MASK) << 2) + 4;
388
389 } else if ((insn & INSN_STD_MASK) == INSN_POP_MASKED) {
390 unsigned int mask, reg;
391
392 /* Load the mask */
393 mask = unwind_exec_read_byte(state);
394 mask |= (insn & INSN_STD_DATA_MASK) << 8;
395
396 /* We have a refuse to unwind instruction */
397 if (mask == 0)
398 return 1;
399
400 if (!__is_aligned(vsp, sizeof(register_t)))
401 return 1;
402
403 /* Update SP */
404 update_vsp = 1;
405
406 /* Load the registers */
407 for (reg = 4; mask && reg < 16; mask >>= 1, reg++) {
408 if (mask & 1) {
409 if (!kstack_contains(td, (uintptr_t)vsp,
410 sizeof(*vsp)))
411 return 1;
412
413 state->registers[reg] = *vsp++;
414 state->update_mask |= 1 << reg;
415
416 /* If we have updated SP kep its value */
417 if (reg == SP)
418 update_vsp = 0;
419 }
420 }
421
422 } else if ((insn & INSN_STD_MASK) == INSN_VSP_REG &&
423 ((insn & INSN_STD_DATA_MASK) != 13) &&
424 ((insn & INSN_STD_DATA_MASK) != 15)) {
425 /* sp = register */
426 state->registers[SP] =
427 state->registers[insn & INSN_STD_DATA_MASK];
428
429 } else if ((insn & INSN_STD_MASK) == INSN_POP_COUNT) {
430 unsigned int count, reg;
431
432 /* Read how many registers to load */
433 count = insn & INSN_POP_COUNT_MASK;
434
435 if (!__is_aligned(vsp, sizeof(register_t)))
436 return 1;
437
438 /* Update sp */
439 update_vsp = 1;
440
441 /* Pop the registers */
442 if (!kstack_contains(td, (uintptr_t)vsp,
443 sizeof(*vsp) * (4 + count)))
444 return 1;
445 for (reg = 4; reg <= 4 + count; reg++) {
446 state->registers[reg] = *vsp++;
447 state->update_mask |= 1 << reg;
448 }
449
450 /* Check if we are in the pop r14 version */
451 if ((insn & INSN_POP_TYPE_MASK) != 0) {
452 if (!kstack_contains(td, (uintptr_t)vsp, sizeof(*vsp)))
453 return 1;
454 state->registers[14] = *vsp++;
455 }
456
457 } else if (insn == INSN_FINISH) {
458 /* Stop processing */
459 state->entries = 0;
460
461 } else if (insn == INSN_POP_REGS) {
462 unsigned int mask, reg;
463
464 mask = unwind_exec_read_byte(state);
465 if (mask == 0 || (mask & 0xf0) != 0)
466 return 1;
467
468 if (!__is_aligned(vsp, sizeof(register_t)))
469 return 1;
470
471 /* Update SP */
472 update_vsp = 1;
473
474 /* Load the registers */
475 for (reg = 0; mask && reg < 4; mask >>= 1, reg++) {
476 if (mask & 1) {
477 if (!kstack_contains(td, (uintptr_t)vsp,
478 sizeof(*vsp)))
479 return 1;
480 state->registers[reg] = *vsp++;
481 state->update_mask |= 1 << reg;
482 }
483 }
484
485 } else if ((insn & INSN_VSP_LARGE_INC_MASK) == INSN_VSP_LARGE_INC) {
486 unsigned int uleb128;
487
488 /* Read the increment value */
489 uleb128 = unwind_exec_read_byte(state);
490
491 state->registers[SP] += 0x204 + (uleb128 << 2);
492
493 } else {
494 /* We hit a new instruction that needs to be implemented */
495 #if 0
496 db_printf("Unhandled instruction %.2x\n", insn);
497 #endif
498 return 1;
499 }
500
501 if (update_vsp) {
502 state->registers[SP] = (uint32_t)vsp;
503 }
504
505 #if 0
506 db_printf("fp = %08x, sp = %08x, lr = %08x, pc = %08x\n",
507 state->registers[FP], state->registers[SP], state->registers[LR],
508 state->registers[PC]);
509 #endif
510
511 return 0;
512 }
513
514 /* Performs the unwind of a function */
515 static int
unwind_tab(struct unwind_state * state)516 unwind_tab(struct unwind_state *state)
517 {
518 uint32_t entry;
519
520 /* Set PC to a known value */
521 state->registers[PC] = 0;
522
523 /* Read the personality */
524 entry = *state->insn & ENTRY_MASK;
525
526 if (entry == ENTRY_ARM_SU16) {
527 state->byte = 2;
528 state->entries = 1;
529 } else if (entry == ENTRY_ARM_LU16) {
530 state->byte = 1;
531 state->entries = ((*state->insn >> 16) & 0xFF) + 1;
532 } else {
533 #if 0
534 db_printf("Unknown entry: %x\n", entry);
535 #endif
536 return 1;
537 }
538
539 while (state->entries > 0) {
540 if (unwind_exec_insn(state) != 0)
541 return 1;
542 }
543
544 /*
545 * The program counter was not updated, load it from the link register.
546 */
547 if (state->registers[PC] == 0) {
548 state->registers[PC] = state->registers[LR];
549
550 /*
551 * If the program counter changed, flag it in the update mask.
552 */
553 if (state->start_pc != state->registers[PC])
554 state->update_mask |= 1 << PC;
555 }
556
557 return 0;
558 }
559
560 /*
561 * Unwind a single stack frame.
562 * Return 0 on success or 1 if the stack cannot be unwound any further.
563 *
564 * XXX The can_lock argument is no longer germane; a sweep of callers should be
565 * made to remove it after this new code has proven itself for a while.
566 */
567 int
unwind_stack_one(struct unwind_state * state,int can_lock __unused)568 unwind_stack_one(struct unwind_state *state, int can_lock __unused)
569 {
570 struct unwind_idx *index;
571
572 /* Reset the mask of updated registers */
573 state->update_mask = 0;
574
575 /* The pc value is correct and will be overwritten, save it */
576 state->start_pc = state->registers[PC];
577
578 /* Find the item to run */
579 index = find_index(state->start_pc);
580 if (index == NULL || index->insn == EXIDX_CANTUNWIND)
581 return 1;
582
583 if (index->insn & (1U << 31)) {
584 /* The data is within the instruction */
585 state->insn = &index->insn;
586 } else {
587 /* A prel31 offset to the unwind table */
588 state->insn = (uint32_t *)
589 ((uintptr_t)&index->insn +
590 expand_prel31(index->insn));
591 }
592
593 /* Run the unwind function, return its finished/not-finished status. */
594 return (unwind_tab(state));
595 }
596