Backtrace (call stack) support. More...

Data Structures
struct	symtable_header_t
	Symbol table file header. More...

struct	symtable_entry_t
	Symbol table entry. More...

Macros
#define	BACKTRACE_DEBUG 0
	Enable to debug why a backtrace is wrong.

#define	FUNCTION_ALIGNMENT 32
	Function alignment enfored by the compiler (-falign-functions).

#define	ADDRENTRY_ADDR(e) ((e) & ~3)
	Address (without the flags9)

#define	ADDRENTRY_IS_FUNC(e) ((e) & 1)
	True if the address is the start of a function.

#define	ADDRENTRY_IS_INLINE(e) ((e) & 2)
	True if the address is an inline duplicate.

#define	MIPS_OP_ADDIU_SP(op) (((op) & 0xFFFF0000) == 0x27BD0000)
	Matches: addiu $sp, $sp, imm.

#define	MIPS_OP_DADDIU_SP(op) (((op) & 0xFFFF0000) == 0x67BD0000)
	Matches: daddiu $sp, $sp, imm.

#define	MIPS_OP_JR_RA(op) (((op) & 0xFFFFFFFF) == 0x03E00008)
	Matches: jr $ra.

#define	MIPS_OP_SD_RA_SP(op) (((op) & 0xFFFF0000) == 0xFFBF0000)
	Matches: sd $ra, imm($sp)

#define	MIPS_OP_SD_FP_SP(op) (((op) & 0xFFFF0000) == 0xFFBE0000)
	Matches: sd $fp, imm($sp)

#define	MIPS_OP_LUI_GP(op) (((op) & 0xFFFF0000) == 0x3C1C0000)
	Matches: lui $gp, imm.

#define	MIPS_OP_NOP(op) ((op) == 0x00000000)
	Matches: nop.

#define	MIPS_OP_MOVE_FP_SP(op) ((op) == 0x03A0F025)
	Matches: move $fp, $sp.

Typedefs
typedef uint32_t	addrtable_entry_t
	Entry in the address table.

Functions
char *	__symbolize (void vaddr, char buf, int size)
	Return the symbol associated to a given address.

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).

int	backtrace (void **buffer, int size)
	Walk the stack and return the current call stack.

bool	backtrace_symbols_cb (void *buffer, int size, uint32_t flags, void(cb)(void , backtrace_frame_t ), void *cb_arg)
	Symbolize the buffer returned by backtrace, calling a callback for each frame.

char **	backtrace_symbols (void **buffer, int size)
	Translate the buffer returned by backtrace into a list of strings.

void	backtrace_frame_print (backtrace_frame_t frame, FILE out)
	Print a single frame of a backtrace.

void	backtrace_frame_print_compact (backtrace_frame_t frame, FILE out, int width)
	Print a single frame of a backtrace, in a compact format.

Variables
uint32_t	inthandler []
	Exception handler (see inthandler.S)

uint32_t	inthandler_end []
	End of exception handler (see inthandler.S)

Detailed Description

Backtrace (call stack) support.

This file contains the implementation of the backtrace support. See backtrace.h for an overview of the API. Here follows some implementation details.

Backtrace

MIPS ABIs do not generally provide a way to walk the stack, as the frame pointer is not guaranteed to be present. It is possible to force its presence via "-fno-omit-frame-pointer", but we tried to provide a solution that works with standard compilation settings.

To perform backtracing, we scan the code backward starting from the return address of each frame. While scanning, we note some special instructions that we look for. The two main instructions that we look for are sd ra, offset(sp) which is used to save the previous return address to the stack, and addiu sp, sp, offset which creates the stack frame for the current function. When we find both, we know how to get back to the previous frame.

Notice that this also works through exceptions, as the exception handler does create a stack frame exactly like a standard function (see inthandler.S).

Only a few functions do use a frame pointer: those that allocate a runtime-calculated amount of stack (eg: using alloca). Because of this, we actually look for usages of the frame pointer register fp, and track those as well to be able to correctly walk the stack in those cases.

Symbolization

To symbolize the backtrace, we use a symbol table file (SYMT) that is generated by the n64sym tool during the build process. The symbol table is put into the rompak (see rompak_internal.h) and is structured in a way that can be queried directly from ROM, without even allocating memory. This is especially useful to provide backtrace in catastrophic situations where the heap is not available.

The symbol table file contains the source code references (function name, file name, line number) for a number of addresses in the ROM. Since it would be impractical to save information for all the addresses in the text segment, only special addresses are saved: in particular, those where a function call is made (ie: the address of JAL / JALR instructions), which are the ones that are commonly found in backtraces and thus need to be symbolized. In addition to these, the symbol table contains also information associated to the addresses that mark the start of each function, so that it's always possible to infer the function a certain address belongs to.

Given that not all addresses are saved, it is important to provide accurate source code references for stack frames that are interrupted by interrupts or exceptions; in those cases, the symbolization will simply return the function name the addresses belongs to, without any source code reference.

To see more details on how the symbol table is structured in the ROM, see symtable_header_t and the source code of the n64sym tool.

Data Structure Documentation

◆ symtable_header_t

struct symtable_header_t

Symbol table file header.

The SYMT file is made of three main tables:

Address table: this is a sequence of 32-bit integers, each representing an address in the ROM. The table is sorted in ascending order to allow for binary search. Moreover, the lowest 2 bits of each address can store additional information: If bit 0 is set to 1, the address is the start of a function. If bit 1 is set to 1, the address is an inline duplicate. In fact, there might be multiple symbols at the same address for inlined functions, so we need one entry in this table for each entry; all of them will have the same address, and all but the last one will have bit 1 set to 1.
Symbol table: this is a sequence of symbol table entries, each representing a symbol. The size of this table (in number of entries) is exactly the same as the address table. In fact, each address of the address table can be thought of as an external member of this structure; it's split externally to allow for efficiency reasons. Each entry stores the function name, the source file name and line number, and the binary offset of the symbol within the containing function.
String table: this table can be thought as a large buffer holding all the strings needed by all symbol entries (function names and file names). Each symbol entry stores a string as an offset within the symbol table and a length. This allows to reuse the same string (or prefix thereof) multiple times. Notice that strings are not null terminated in the string table.

The SYMT file is generated by the n64sym tool during the build process.

Data Fields
char	head[4]	Magic ID "SYMT".
uint32_t	version	Version of the symbol table.
uint32_t	addrtab_off	Offset of the address table in the file.
uint32_t	addrtab_size	Size of the address table in the file (number of entries)
uint32_t	symtab_off	Offset of the symbol table in the file.
uint32_t	symtab_size	Size of the symbol table in the file (number of entries); always equal to addrtab_size.
uint32_t	strtab_off	Offset of the string table in the file.
uint32_t	strtab_size	Size of the string table in the file (number of entries)

◆ symtable_entry_t

struct symtable_entry_t

Symbol table entry.

Data Fields
uint32_t	func_sidx	Offset of the function name in the string table.
uint32_t	file_sidx	Offset of the file name in the string table.
uint16_t	func_len	Length of the function name.
uint16_t	file_len	Length of the file name.
uint16_t	line	Line number (or 0 if this symbol generically refers to a whole function)
uint16_t	func_off	Offset of the symbol within its function.

Macro Definition Documentation

◆ FUNCTION_ALIGNMENT

#define FUNCTION_ALIGNMENT 32

Function alignment enfored by the compiler (-falign-functions).

Note: This must be kept in sync with n64.mk.

Typedef Documentation

◆ addrtable_entry_t

typedef uint32_t addrtable_entry_t

Entry in the address table.

This is an address in RAM, with the lowest 2 bits used to store additional information. See the ADDRENTRY_* macros to access the various components.

Function Documentation

◆ __symbolize()

char * __symbolize	(	void *	vaddr,
		char *	buf,
		int	size
	)

Return the symbol associated to a given address.

This function inspect the symbol table (if any) to search for the specified address. It returns the function name the address belongs to, and the offset within the function as a string in the format "function_name+0x1234".

If the symbol table is not found in the rompack or the address is not found, the return string is "???".

Parameters

vaddr	Address to symbolize
buf	Buffer where to store the result
size	Size of the buffer

Returns: char* Pointer to the return string. This is within the provided buffer, but not necessarily at the beginning because of DMA alignment constraints.

◆ __bt_analyze_func()

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).

This function implements the core heuristic used by the backtrace engine. It analyzes the actual code of a function in memory instruction by instruction, trying to find out whether the function uses a stack frame or not, whether it uses a frame pointer, and where the return address is stored.

Since we do not have DWARF informations or similar metadata, we can just do educated guesses. A mistake in the heuristic will result probably in a wrong backtrace from this point on.

The heuristic works as follows:

Most functions do have a stack frame. In fact, 99.99% of the functions you can find in a call stack must have a stack frame, because the only functions without a stack frame are leaf functions (functions that do not call other functions), which in turns can never be part of a stack trace.
The heuristic walks the function code backwards, looking for the stack frame. Specifically, it looks for an instruction saving the RA register to the stack (eg: sd $ra, nn($sp)), and an instruction creating the stack frame (eg: addiu $sp, $sp, -nn). Once both are found, the heuristic knows how to fill in .stack_size and .ra_offset fields of the function description structure, and it can stop.
Some functions also modify $fp (the frame pointer register): sometimes, they just use it as one additional free register, and other times they really use it as frame pointer. If the heuristic finds the instruction move $fp, $sp, it knows that the function uses $fp as frame pointer, and will mark the function as BT_FUNCTION_FRAMEPOINTER. In any case, the field .fp_offset will be filled in with the offset in the stack where $fp is stored, so that the backtrace engine can track the current value of the register in any case.
The 0.01% of the functions that do not have a stack frame but appear in the call stack are leaf functions interrupted by exceptions. Leaf functions pose two important problems: first, $ra is not saved into the stack so there is no way to know where to go back. Second, there is no clear indication where the function begins (as we normally stops analysis when we see the stack frame creation). So in this case the heuristic would fail. We rely thus on two hints coming from the caller:
- First, we expect the caller to set from_exception=true, so that we know that we might potentially deal with a leaf function.
- Second, the caller should provide the function start address, so that we stop the analysis when we reach it, and mark the function as BT_LEAF.
- If the function start address is not provided (because e.g. the symbol table was not found and thus we have no information about function starts), the last ditch heuristic is to look for the nops that are normally used to align the function start to the FUNCTION_ALIGNMENT boundary. Obviously this is a very fragile heuristic (it will fail if the function required no nops to be properly aligned), but it is the best we can do. Worst case, in this specific case of a leaf function interrupted by the exception, the stack trace will be wrong from this point on.