Paper Mario DX
Paper Mario (N64) modding
 
Loading...
Searching...
No Matches
backtrace.c
Go to the documentation of this file.
1// Backtrace (call stack) support.
2// Heavily based on libdragon: https://github.com/DragonMinded/libdragon/blob/trunk/src/backtrace.c
3
4#include "common.h"
5#include <string.h>
6#include <stdint.h>
7#include <stdbool.h>
8#include "nu/nusys.h"
9#include "backtrace.h"
10#include "PR/osint.h"
11
13#define BACKTRACE_DEBUG 0
14
16#define FUNCTION_ALIGNMENT 32
17
25
33
34#define MIPS_OP_ADDIU_SP(op) (((op) & 0xFFFF0000) == 0x27BD0000)
35#define MIPS_OP_DADDIU_SP(op) (((op) & 0xFFFF0000) == 0x67BD0000)
36#define MIPS_OP_JR_RA(op) (((op) & 0xFFFFFFFF) == 0x03E00008)
37#define MIPS_OP_SD_RA_SP(op) (((op) & 0xFFFF0000) == 0xFFBF0000)
38#define MIPS_OP_SW_RA_SP(op) (((op) & 0xFFFF0000) == 0xAFBF0000)
39#define MIPS_OP_SD_FP_SP(op) (((op) & 0xFFFF0000) == 0xFFBE0000)
40#define MIPS_OP_SW_FP_SP(op) (((op) & 0xFFFF0000) == 0xAFBE0000)
41#define MIPS_OP_LUI_GP(op) (((op) & 0xFFFF0000) == 0x3C1C0000)
42#define MIPS_OP_NOP(op) ((op) == 0x00000000)
43#define MIPS_OP_MOVE_FP_SP(op) ((op) == 0x03A0F025)
44
45#define debugf printf
46
48
54static u32 get_physical_address(u32 addr) {
55 return 0x80000000 | osVirtualToPhysical((void*)addr);
56}
57
59static bool is_valid_address(uint32_t addr) {
60 addr = get_physical_address(addr);
61 return addr >= 0x80000400 && addr < 0x80800000 && (addr & 3) == 0;
62}
63
64static void backtrace_foreach(void (*cb)(void *arg, void *ptr), void *arg) {
65 /*
66 * This function is called in very risky contexts, for instance as part of an exception
67 * handler or during an assertion. We try to always provide as much information as
68 * possible in these cases, with graceful degradation if something more elaborate cannot
69 * be extracted. Thus, this function:
70 *
71 * * Must not use malloc(). The heap might be corrupted or empty.
72 * * Must not use assert(), because that might trigger recursive assertions.
73 * * Must avoid raising exceptions. Specifically, it must avoid risky memory accesses
74 * to wrong addresses.
75 */
76
79
80 // Current value of SP/RA/FP registers.
81 uint32_t *sp, *ra, *fp;
82 asm volatile (
83 "move %0, $ra\n"
84 "move %1, $sp\n"
85 "move %2, $fp\n"
86 : "=r"(ra), "=r"(sp), "=r"(fp)
87 );
88
89 #if BACKTRACE_DEBUG
90 debugf("backtrace: start\n");
91 #endif
92
93 exception_ra = NULL; // If != NULL,
94 func_start = 0; // Start of the current function (when known)
95
96 // Start from the backtrace function itself. Put the start pointer somewhere after the initial
97 // prolog (eg: 64 instructions after start), so that we parse the prolog itself to find sp/fp/ra offsets.
98 ra = (uint32_t*)backtrace_foreach + 64;
99
100 while (1) {
101 // Analyze the function pointed by ra, passing information about the previous exception frame if any.
102 // If the analysis fail (for invalid memory accesses), stop right away.
103 bt_func_t func;
104 if (!__bt_analyze_func(&func, ra, func_start, (bool)exception_ra))
105 return;
106
107 #if BACKTRACE_DEBUG
108 debugf("backtrace: %s, ra=%p, sp=%p, fp=%p ra_offset=%d, fp_offset=%d, stack_size=%d\n",
109 func.type == BT_FUNCTION ? "BT_FUNCTION" : (func.type == BT_EXCEPTION ? "BT_EXCEPTION" : (func.type == BT_FUNCTION_FRAMEPOINTER ? "BT_FRAMEPOINTER" : "BT_LEAF")),
110 ra, sp, fp, func.ra_offset, func.fp_offset, func.stack_size);
111 #endif
112
113 switch (func.type) {
115 if (!func.fp_offset) {
116 debugf("backtrace: framepointer used but not saved onto stack at %p\n", ra);
117 } else {
118 // Use the frame pointer to refer to the current frame.
119 sp = fp;
120 if (!is_valid_address((uint32_t)sp)) {
121 debugf("backtrace: interrupted because of invalid frame pointer 0x%08lx\n", (uint32_t)sp);
122 return;
123 }
124 }
125 // FALLTHROUGH!
126 case BT_FUNCTION:
127 if (func.fp_offset)
128 fp = *(uint32_t**)((uint32_t)sp + func.fp_offset);
129 ra = *(uint32_t**)((uint32_t)sp + func.ra_offset) - 2;
130 sp = (uint32_t*)((uint32_t)sp + func.stack_size);
132 func_start = 0;
133 break;
134 /*
135 case BT_EXCEPTION: {
136 // Exception frame. We must return back to EPC, but let's keep the
137 // RA value. If the interrupted function is a leaf function, we
138 // will need it to further walk back.
139 // Notice that FP is a callee-saved register so we don't need to
140 // recover it from the exception frame (also, it isn't saved there
141 // during interrupts).
142 exception_ra = *(uint32_t**)((uint32_t)sp + func.ra_offset);
143
144 // reg_block_t = __OSThreadContext ?
145
146 // Read EPC from exception frame and adjust it with CAUSE BD bit
147 ra = *(uint32_t**)((uint32_t)sp + offsetof(reg_block_t, epc) + 32);
148 uint32_t cause = *(uint32_t*)((uint32_t)sp + offsetof(reg_block_t, cr) + 32);
149 if (cause & C0_CAUSE_BD) ra++;
150
151 sp = (uint32_t*)((uint32_t)sp + func.stack_size);
152
153 // Special case: if the exception is due to an invalid EPC
154 // (eg: a null function pointer call), we can rely on RA to get
155 // back to the caller. This assumes that we got there via a function call
156 // rather than a raw jump, but that's a reasonable assumption. It's anyway
157 // the best we can do.
158 if ((C0_GET_CAUSE_EXC_CODE(cause) == EXCEPTION_CODE_TLB_LOAD_I_MISS ||
159 C0_GET_CAUSE_EXC_CODE(cause) == EXCEPTION_CODE_LOAD_I_ADDRESS_ERROR) &&
160 !is_valid_address((uint32_t)ra)) {
161
162 // Store the invalid address in the backtrace, so that it will appear in dumps.
163 // This makes it easier for the user to understand the reason for the exception.
164 cb(arg, ra);
165 #if BACKTRACE_DEBUG
166 debugf("backtrace: %s, ra=%p, sp=%p, fp=%p ra_offset=%d, fp_offset=%d, stack_size=%d\n",
167 "BT_INVALID", ra, sp, fp, func.ra_offset, func.fp_offset, func.stack_size);
168 #endif
169
170 ra = exception_ra - 2;
171
172 // The function that jumped into an invalid PC was not interrupted by the exception: it
173 // is a regular function
174 // call now.
175 exception_ra = NULL;
176 break;
177 }
178
179 // The next frame might be a leaf function, for which we will not be able
180 // to find a stack frame. It is useful to try finding the function start.
181 // Try to open the symbol table: if we find it, we can search for the start
182 // address of the function.
183 symtable_header_t symt = symt_open();
184 if (symt.head[0]) {
185 int idx;
186 addrtable_entry_t entry = symt_addrtab_search(&symt, (uint32_t)ra, &idx);
187 while (!ADDRENTRY_IS_FUNC(entry))
188 entry = symt_addrtab_entry(&symt, --idx);
189 func_start = ADDRENTRY_ADDR(entry);
190 #if BACKTRACE_DEBUG
191 debugf("Found interrupted function start address: %08lx\n", func_start);
192 #endif
193 }
194 } break;
195 */
196 case BT_LEAF:
197 ra = exception_ra - 2;
198 // A leaf function has no stack. On the other hand, an exception happening at the
199 // beginning of a standard function (before RA is saved), does have a stack but
200 // will be marked as a leaf function. In this case, we mus update the stack pointer.
201 sp = (uint32_t*)((uint32_t)sp + func.stack_size);
203 func_start = 0;
204 break;
205 }
206
207 if (is_valid_address((uint32_t)ra)) {
208 // Call the callback with this stack frame
209 cb(arg, ra);
210 }
211 }
212}
213
214static void backtrace_foreach_foreign(void (*cb)(void *arg, void *ptr), void *arg, uint32_t *sp, uint32_t *ra, uint32_t *fp) {
217
218 exception_ra = NULL; // If != NULL,
219 func_start = 0; // Start of the current function (when known)
220
221 while (1) {
222 // Analyze the function pointed by ra, passing information about the previous exception frame if any.
223 // If the analysis fail (for invalid memory accesses), stop right away.
224 bt_func_t func;
225 if (!__bt_analyze_func(&func, ra, func_start, (bool)exception_ra))
226 return;
227
228 #if BACKTRACE_DEBUG
229 debugf("backtrace: %s, ra=%p, sp=%p, fp=%p ra_offset=%d, fp_offset=%d, stack_size=%d\n",
230 func.type == BT_FUNCTION ? "BT_FUNCTION" : (func.type == BT_EXCEPTION ? "BT_EXCEPTION" : (func.type == BT_FUNCTION_FRAMEPOINTER ? "BT_FRAMEPOINTER" : "BT_LEAF")),
231 ra, sp, fp, func.ra_offset, func.fp_offset, func.stack_size);
232 #endif
233
234 switch (func.type) {
236 if (!func.fp_offset) {
237 debugf("backtrace: framepointer used but not saved onto stack at %p\n", ra);
238 } else {
239 // Use the frame pointer to refer to the current frame.
240 sp = fp;
241 if (!is_valid_address((uint32_t)sp)) {
242 debugf("backtrace: interrupted because of invalid frame pointer 0x%08lx\n", (uint32_t)sp);
243 return;
244 }
245 }
246 // FALLTHROUGH!
247 case BT_FUNCTION:
248 if (func.fp_offset)
249 fp = *(uint32_t**)((uint32_t)sp + func.fp_offset);
250 ra = *(uint32_t**)((uint32_t)sp + func.ra_offset) - 2;
251 sp = (uint32_t*)((uint32_t)sp + func.stack_size);
253 func_start = 0;
254 break;
255 case BT_LEAF:
256 ra = exception_ra - 2;
257 // A leaf function has no stack. On the other hand, an exception happening at the
258 // beginning of a standard function (before RA is saved), does have a stack but
259 // will be marked as a leaf function. In this case, we mus update the stack pointer.
260 sp = (uint32_t*)((uint32_t)sp + func.stack_size);
262 func_start = 0;
263 break;
264 }
265
266 if (is_valid_address((uint32_t)ra)) {
267 // Call the callback with this stack frame
268 cb(arg, ra);
269 }
270 }
271}
272
274 void **buffer;
275 int size;
276 int i;
277};
278
279static void backtrace_cb(void *arg, void *ptr) {
280 struct backtrace_cb_ctx *ctx = arg;
281 if (ctx->i >= 0 && ctx->i < ctx->size)
282 ctx->buffer[ctx->i] = ptr;
283 if (ctx->i < ctx->size)
284 ctx->i++;
285}
286
287int backtrace(void **buffer, int size) {
288 struct backtrace_cb_ctx ctx = {
289 buffer,
290 size,
291 -1, // skip backtrace itself
292 };
293 backtrace_foreach(backtrace_cb, &ctx);
294 return ctx.i;
295}
296
297int backtrace_thread(void **buffer, int size, OSThread *thread) {
298 struct backtrace_cb_ctx ctx = {
299 buffer,
300 size,
301 0,
302 };
303 u32 sp = (u32)thread->context.sp;
304 u32 pc = (u32)thread->context.pc;
305 u32 fp = (u32)thread->context.s8;
306 backtrace_cb(&ctx, (void*)pc);
307 backtrace_foreach_foreign(backtrace_cb, &ctx, (uint32_t*)sp, (uint32_t*)pc, (uint32_t*)fp);
308 return ctx.i;
309}
310
320s32 address2symbol(u32 address, Symbol* out) {
321 #define symbolsPerChunk 0x1000
322 #define chunkSize ((sizeof(Symbol) * symbolsPerChunk))
323
324 static u32 romHeader[0x10];
325 nuPiReadRom(0, &romHeader, sizeof(romHeader));
326
328 if (symbolTableRomAddr == NULL) {
329 debugf("address2symbol: no symbols available (SYMBOL_TABLE_PTR is NULL)\n");
330 return -1;
331 }
332
333 // Read the header
336 if (symt.magic[0] != 'S' || symt.magic[1] != 'Y' || symt.magic[2] != 'M' || symt.magic[3] != 'S') {
337 debugf("address2symbol: no symbols available (invalid magic '%c%c%c%c')\n", symt.magic[0], symt.magic[1], symt.magic[2], symt.magic[3]);
338 return -1;
339 }
340 if (symt.symbolCount <= 0) {
341 debugf("address2symbol: no symbols available (symbolCount=%d)\n", symt.symbolCount);
342 return -1;
343 }
344
345 // Read symbols in chunks
346 static Symbol chunk[chunkSize];
347 s32 i;
348 for (i = 0; i < symt.symbolCount; i++) {
349 // Do we need to load the next chunk?
350 if (i % symbolsPerChunk == 0) {
353 }
354
356
357 if (sym.address == address) {
358 *out = sym;
359 return 0;
360 } else if (address < sym.address) {
361 // Symbols are sorted by address, so if we passed the address, we can stop
362 break;
363 } else {
364 // Keep searching, but remember this as the last symbol
365 // incase we don't find an exact match
366 *out = sym;
367 }
368 }
369 return address - out->address;
370}
371
372char* load_symbol_string(char* dest, u32 addr, int n) {
373 if (addr == NULL) {
374 return NULL;
375 }
376
377 u32 aligned = addr & ~3;
378 nuPiReadRom(aligned, dest, n);
379 dest[n-1] = '\0'; // Ensure null-termination
380
381 // Shift to start of string
382 return (char*)((u32)dest + (addr & 3));
383}
384
385void backtrace_address_to_string(u32 address, char* dest) {
386 Symbol sym;
387 s32 offset = address2symbol(address, &sym);
388
389 if (offset >= 0 && offset < 0x1000) { // 0x1000 = arbitrary func size limit
390 char name[0x40];
391 char file[0x40];
392 char* namep = load_symbol_string(name, sym.nameOffset, ARRAY_COUNT(name));
393 char* filep = load_symbol_string(file, sym.fileOffset, ARRAY_COUNT(file));
394
395 offset = 0; // Don't show offsets
396
397 if (filep == NULL)
398 if (offset == 0)
399 sprintf(dest, "%s", namep);
400 else
401 sprintf(dest, "%s+0x%X", namep, offset);
402 else
403 if (offset == 0)
404 sprintf(dest, "%s (%s)", namep, filep);
405 else
406 sprintf(dest, "%s (%s+0x%X)", namep, filep, offset);
407 } else {
408 sprintf(dest, "%p", address);
409 }
410}
411
412void debug_backtrace(void) {
413 s32 bt[32];
414 s32 max = backtrace((void**)bt, ARRAY_COUNT(bt));
415 s32 i;
416 char buf[128];
417
418 debugf("Backtrace:\n");
419 for (i = 0; i < max; i++) {
421 debugf(" %s\n", buf);
422 }
423}
424
480 // exceptasm.s
481 #define inthandler ((uint32_t*)0x8006A9F0)
482 #define inthandler_end ((uint32_t*)0x8006B35C)
483
484 uint32_t addr;
485
486 *func = (bt_func_t){
487 .type = (ptr >= inthandler && ptr < inthandler_end) ? BT_EXCEPTION : BT_FUNCTION,
488 .stack_size = 0, .ra_offset = 0, .fp_offset = 0
489 };
490
491 addr = (uint32_t)ptr;
492 while (1) {
493 uint32_t op;
494
495 // Validate that we can dereference the virtual address without raising an exception
496 if (!is_valid_address(addr)) {
497 // This address is invalid, probably something is corrupted. Avoid looking further.
498 debugf("backtrace: interrupted because of invalid return address 0x%08x\n", addr);
499 return false;
500 }
501 op = *(uint32_t*)get_physical_address(addr);
503 // Extract the stack size only from the start of the function, where the
504 // stack is allocated (negative value). This is important because the RA
505 // could point to a leaf basis block at the end of the function (like in the
506 // assert case), and if we picked the positive ADDIU SP at the end of the
507 // proper function body, we might miss a fp_offset.
508 if (op & 0x8000)
509 func->stack_size = -(int16_t)(op & 0xFFFF);
510 } else if (MIPS_OP_SD_RA_SP(op)) {
511 func->ra_offset = (int16_t)(op & 0xFFFF) + 4; // +4 = load low 32 bit of RA
512 // If we found a stack size, it might be a red herring (an alloca); we need one
513 // happening "just before" sd ra,xx(sp)
514 func->stack_size = 0;
515 } else if (MIPS_OP_SW_RA_SP(op)) {
516 // 32-bit version of above
517 func->ra_offset = (int16_t)(op & 0xFFFF);
518 func->stack_size = 0;
519 } else if (MIPS_OP_SD_FP_SP(op)) {
520 func->fp_offset = (int16_t)(op & 0xFFFF) + 4; // +4 = load low 32 bit of FP
521 } else if (MIPS_OP_SW_FP_SP(op)) {
522 // 32-bit version of above
523 func->fp_offset = (int16_t)(op & 0xFFFF);
524 } else if (MIPS_OP_LUI_GP(op)) {
525 // Loading gp is commonly done in _start, so it's useless to go back more
526 return false;
527 } else if (MIPS_OP_MOVE_FP_SP(op)) {
528 // This function uses the frame pointer. Uses that as base of the stack.
529 // Even with -fomit-frame-pointer (default on our toolchain), the compiler
530 // still emits a framepointer for functions using a variable stack size
531 // (eg: using alloca() or VLAs).
533 }
534 // We found the stack frame size and the offset of the return address in the stack frame
535 // We can stop looking and process the frame
536 if (func->stack_size != 0 && func->ra_offset != 0)
537 break;
538 if (from_exception) {
539 // The function we are analyzing was interrupted by an exception, so it might
540 // potentially be a leaf function (no stack frame). We need to make sure to stop
541 // at the beginning of the function and mark it as leaf function. Use
542 // func_start if specified, or try to guess using the nops used to align the function
543 // (crossing fingers that they're there).
544 if (addr == func_start) {
545 // The frame that was interrupted by an interrupt handler is a special case: the
546 // function could be a leaf function with no stack. If we were able to identify
547 // the function start (via the symbol table) and we reach it, it means that
548 // we are in a real leaf function.
549 func->type = BT_LEAF;
550 break;
551 } else if (!func_start && MIPS_OP_NOP(op) && (addr + 4) % FUNCTION_ALIGNMENT == 0) {
552 // If we are in the frame interrupted by an interrupt handler, and we does not know
553 // the start of the function (eg: no symbol table), then try to stop by looking for
554 // a NOP that pads between functions. Obviously the NOP we find can be either a false
555 // positive or a false negative, but we can't do any better without symbols.
556 func->type = BT_LEAF;
557 break;
558 }
559 }
560 addr -= 4;
561 }
562 return true;
563}
BSS s32 PopupMenu_SelectedIndex
#define MIPS_OP_LUI_GP(op)
Matches: lui $gp, imm.
Definition backtrace.c:41
int backtrace(void **buffer, int size)
Walk the stack and return the current call stack.
Definition backtrace.c:287
#define MIPS_OP_DADDIU_SP(op)
Matches: daddiu $sp, $sp, imm.
Definition backtrace.c:35
#define MIPS_OP_SD_FP_SP(op)
Matches: sd $fp, imm($sp)
Definition backtrace.c:39
char * load_symbol_string(char *dest, u32 addr, int n)
Definition backtrace.c:372
#define debugf
Definition backtrace.c:45
#define inthandler_end
#define symbolsPerChunk
void debug_backtrace(void)
Print a backtrace.
Definition backtrace.c:412
bool __bt_analyze_func(bt_func_t *func, uint32_t *ptr, uint32_t func_start, bool from_exception)
Analyze a function to find out its stack frame layout and properties (useful for backtracing).
Definition backtrace.c:479
int stack_size
Size of the stack frame.
Definition backtrace.c:29
int backtrace_thread(void **buffer, int size, OSThread *thread)
Definition backtrace.c:297
void backtrace_address_to_string(u32 address, char *dest)
Converts a function address to a string representation using its name, offset, and file.
Definition backtrace.c:385
#define chunkSize
int ra_offset
Offset of the return address from the top of the stack frame.
Definition backtrace.c:30
#define MIPS_OP_SD_RA_SP(op)
Matches: sd $ra, imm($sp)
Definition backtrace.c:37
s32 address2symbol(u32 address, Symbol *out)
Uses the symbol table to look up the symbol corresponding to the given address.
Definition backtrace.c:320
bt_func_type
The "type" of funciton as categorized by the backtrace heuristic (__bt_analyze_func)
Definition backtrace.c:19
@ BT_FUNCTION_FRAMEPOINTER
The function uses the register fp as frame pointer (normally, this happens only when the function use...
Definition backtrace.c:21
@ BT_LEAF
Leaf function (no calls), no stack frame allocated, sp/ra not modified.
Definition backtrace.c:23
@ BT_EXCEPTION
This is an exception handler (inthandler.S)
Definition backtrace.c:22
@ BT_FUNCTION
Regular function with a stack frame.
Definition backtrace.c:20
#define MIPS_OP_SW_RA_SP(op)
Matches: sw $ra, imm($sp)
Definition backtrace.c:38
#define MIPS_OP_NOP(op)
Matches: nop.
Definition backtrace.c:42
int fp_offset
Offset of the saved fp from the top of the stack frame; this is != 0 only if the function modifies fp...
Definition backtrace.c:31
#define MIPS_OP_ADDIU_SP(op)
Matches: addiu $sp, $sp, imm.
Definition backtrace.c:34
bt_func_type type
Type of the function.
Definition backtrace.c:28
#define MIPS_OP_SW_FP_SP(op)
Matches: sw $fp, imm($sp)
Definition backtrace.c:40
#define inthandler
#define MIPS_OP_MOVE_FP_SP(op)
Matches: move $fp, $sp.
Definition backtrace.c:43
#define FUNCTION_ALIGNMENT
Function alignment enfored by the compiler (-falign-functions).
Definition backtrace.c:16
Description of a function for the purpose of backtracing (filled by __bt_analyze_func)
Definition backtrace.c:27
#define SYMBOL_TABLE_PTR_ROM_ADDR
ROM address of the pointer to the symbol table.
Definition backtrace.h:12
u32 address
RAM address.
Definition backtrace.h:15
#define ARRAY_COUNT(arr)
Definition macros.h:40