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 */
67extern 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 */
97struct 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 */
103static __inline int32_t
104expand_prel31(uint32_t prel31)
105{
106
107	return ((int32_t)(prel31 & 0x7fffffffu) << 1) / 2;
108}
109
110struct search_context {
111	uint32_t addr;
112	caddr_t exidx_start;
113	caddr_t exidx_end;
114};
115
116static int
117module_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 */
146static struct unwind_idx *
147find_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 */
195static uint8_t
196unwind_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 */
215static int
216unwind_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 */
340static int
341unwind_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
385int
386unwind_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