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