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