Cross-platform stack traces
Stack traces are a big help when something goes wrong in our program and we need to find out where the error occured. Pretty much all interpreted programming languages and even some recent system languages support them, so there's really no excuse for not implementing them in my Banjo programming language. Let's do it!
Platform APIs
Banjo is a compiled programming language, so we need to trace the actual
hardware stack. POSIX systems like Linux and macOS provide a simple function
called backtrace that does exactly that. There is even an accompanying
function called backtrace_symbols that translates every entry in the call
stack into a human-readable string. How convenient! Together, these APIs are
used like this:
#include <execinfo.h>
#include <stdio.h>
#define MAX_ADDR_COUNT 128
void print_stack() {
void *addrs[MAX_ADDR_COUNT];
int addr_count = backtrace(addrs, MAX_ADDR_COUNT);
char **symbols = backtrace_symbols(addrs, addr_count);
if (!symbols) {
return;
}
for (int i = 0; i < addr_count; i++) {
printf("%s\n", symbols[i]);
}
}
void some_function() {
print_stack();
}
int main(int argc, const char **argv) {
some_function();
return 0;
}
Compiling and running this on my MacBook prints the following:
$ clang ./stacktrace.c && ./a.out
0 a.out 0x0000000104290490 print_stack + 48
1 a.out 0x0000000104290544 some_function + 12
2 a.out 0x0000000104290570 main + 36
3 dyld 0x00000001855344e4 start + 6992
For each entry in the call stack, backtrace_symbols gives us the file name,
the address, the function name, and the offset into the function. On Linux, the
format is a bit different, but we get the same information:
$ clang ./stacktrace.c && ./a.out
./a.out() [0x40078c]
./a.out() [0x400818]
./a.out() [0x400844]
/lib64/libc.so.6(+0x26f1c) [0xffffaff26f1c]
/lib64/libc.so.6(__libc_start_main+0x9c) [0xffffaff2705c]
./a.out() [0x400670]
But wait, where are the function names in our stack trace? It turns out, the
linker doesn't put all symbol names into the final binary by default. To do so,
we need to add the -rdynamic flag:
$ clang -rdynamic ./stacktrace.c && ./a.out
./a.out(print_stack+0x20) [0x40098c]
./a.out(some_function+0xc) [0x400a18]
./a.out(main+0x24) [0x400a44]
/lib64/libc.so.6(+0x26f1c) [0xffffac0b6f1c]
/lib64/libc.so.6(__libc_start_main+0x9c) [0xffffac0b705c]
./a.out(_start+0x30) [0x400870]
The Windows API provides function called CaptureStackBackTrace that is very
similar to backtrace. To resolve function names, we use the SymFromAddr
function from dbghelp.dll. As is often the case, things are slightly more
insane on Windows:
#include <windows.h>
#include <dbghelp.h>
#include <stdio.h>
#define MAX_ADDR_COUNT 128
void print_stack() {
HANDLE process = GetCurrentProcess();
SymInitialize(process, NULL, TRUE);
PVOID addrs[MAX_ADDR_COUNT];
WORD addr_count = CaptureStackBackTrace(0, MAX_ADDR_COUNT, addrs, NULL);
for (int i = 0; i < addr_count; i++) {
DWORD64 address = (DWORD64)addrs[i];
DWORD64 displacement = 0;
char symbol_buffer[sizeof(SYMBOL_INFO) + MAX_SYM_NAME * sizeof(TCHAR)];
PSYMBOL_INFO symbol = (PSYMBOL_INFO)symbol_buffer;
symbol->SizeOfStruct = sizeof(SYMBOL_INFO);
symbol->MaxNameLen = MAX_SYM_NAME;
if (SymFromAddr(process, address, &displacement, symbol)) {
printf("%s (0x%0llX)\n", symbol->Name, address);
}
}
}
void some_function() {
print_stack();
}
int main(int argc, const char **argv) {
some_function();
return 0;
}
SymFromAddr only works if we set the /Z7 compiler option to enable debug
information for our executable:
$ clang-cl /Z7 .\stacktrace.c dbghelp.lib; .\stacktrace.exe
print_stack (0x7FF785601059)
some_function (0x7FF785601139)
main (0x7FF78560115A)
__scrt_common_main_seh (0x7FF785601C00)
BaseThreadInitThunk (0x7FFAAC42CCB7)
RtlUserThreadStart (0x7FFAADEEAD6C)
In theory, we now have a way to get stack traces on all major target platforms, we just have to convert these C functions into Banjo code. However, this approach has a few limitations:
- The printed format is different on all platforms.
- On some platforms, we have to set specific linker flags to resolve function names at runtime.
- We can't access extra information like line numbers using these APIs 1.
- We have to limit the depth of the call stack (
MAX_ADDR_COUNT). - Symbols coming from Banjo code would have to be demangled.
Instead of finding workarounds for all these issues, it's easier to implement stack tracing ourselves.
Frames and pointers
In order to replace these platform APIs, we have to understand how they work. A typical stack layout looks like this 2:
o-----------------------o <-- top of stack
| |
| locals and args |
| |
|.......................|
| other saved registers |
|.......................|
| saved frame pointer |
|.......................|
| return address |
|-----------------------| <-- stack frame of `print_stack`
| |
| locals and args |
| |
|.......................|
| other saved registers |
|.......................|
| saved frame pointer |
|.......................|
| return address |
|-----------------------| <-- stack frame of `some_function`
| more stack frames... |
o-----------------------o
Every time we call a function, a new stack frame is pushed onto the stack. A stack frame contains a few things:
- The return address so the function knows where to return to
- Some registers that need to be saved because they are modified by the function
- Storage for local variables and function call arguments
The return addresses are what we're interested in because every return address is between the start and end address of its function. Therefore, we can trace the call stack by collecting all return addresses and determining which function they belong to.
On both x86 and Arm architectures, there is a special register called the frame
pointer. Every time we enter a function, the old value of the frame pointer is
pushed onto the stack and the register is updated to point to the current stack
frame. On x86-64, this register is called rbp, on AArch64 (arm64), it's called
x29.
The frame pointer stores the address of the current frame record (as Arm calls
it). The frame record stores two values: the saved frame pointer of the caller
and the return address. The frame pointers form a linked list of frame records
ending with a null pointer:
o----- frame pointer
|
| o-----------------------o
| | |
| | locals and args |
| | |
| |.......................|
| | other saved registers |
| |.......................|
o-----> | saved frame pointer | ------o
|.......................| |
| return address | |
|-----------------------| |
| | |
| locals and args | |
| | |
|.......................| |
| other saved registers | |
|.......................| |
o------ | saved frame pointer | <-----o
| |.......................|
| | return address |
| |-----------------------|
o-----> | more stack frames... | ------> null
o-----------------------o
As you can see, the return address is stored right next to the saved frame pointer on the stack, so we can also visualize the linked list of frame records like this:
in frame record of frame record of
`print_stack` `print_stack` `some_function`
o----------------o o----------------o
frame pointer --> | frame pointer | --> | frame pointer | --> ... --> null
(rbp/x29) |----------------| |----------------|
| return address | | return address |
o----------------o o----------------o
To walk the stack, we simply dereference frame pointers until we get to the end of the call hierarchy. While doing this, we collect the stack addresses into an array. Here's an implementation in Banjo:
func trace_stack() -> Array[addr] {
var frames: Array[addr] = []
var fp = __builtin_frame_address() as *addr
while fp != null {
frames.append(fp[1])
fp = fp[0] as *addr
}
return frames
}
Note: __builtin_frame_address is a built-in function that returns the value of
the frame pointer register.
Let's try it out:
func print_stack() {
println("stack trace:")
for frame in trace_stack() {
fprintln(" - 0x{:016x}", frame as u64)
}
}
func some_function() {
print_stack()
}
func main() {
some_function()
}
Here's the output I'm getting on macOS:
$ banjo run
stack trace:
- 0x0000004343979728
- 0x0000004343979888
- 0x0000004343979916
- 0x0000006531794148
- 0x0000000000000000
The first few addresses are close together, so we can guess they're from our
Banjo code (print_stack, some_function, and main). The next address is
probably the entry point of the executable and the last address is null to
mark the end of the call stack. Pretty good!
...but not very useful because we only get return addresses instead of function names. We will get to symbolizing these in a minute, but before, we have to take care of a platform where this approach of chasing frame pointers isn't possible.
Unwinding on Windows
In Windows land things work very differently. Microsoft's Visual C++ compiler does not use the frame pointer (probably for performance reasons). Instead, the call stack is traced by reading the return address from the same place the CPU would when returning from the function. It turns out, finding this return address on the stack isn't straightforward because the stack also contains other data like local variables and saved registers.
To solve this issue, the MSVC compiler embeds information about how to unwind every function into the executable. This information is basically a mini language that describes the layout of the stack frame and is known as unwind information. The format and encoding of unwind information are specified here as part of Microsoft's x64 ABI.
To better understand how this works, we need to drop down to assembly level. Here's an example function:
int function(int a, int b) {
char c[128];
another_function(c);
return a + b;
}
We'll compile this into a Windows object file using clang-cl:
$ clang-cl /c /GS- /O2 .\unwind.c
The object file contains the following instructions:
$ llvm-objdump --disassemble -Mintel .\unwind.obj
.\unwind.obj: file format coff-x86-64
Disassembly of section .text:
0000000000000000 <function>:
0: 56 push rsi
1: 57 push rdi
2: 48 81 ec a8 00 00 00 sub rsp, 0xa8
9: 89 d6 mov esi, edx
b: 89 cf mov edi, ecx
d: 48 8d 4c 24 20 lea rcx, [rsp + 0x20]
12: e8 00 00 00 00 call 0x17 <function+0x17>
17: 01 f7 add edi, esi
19: 89 f8 mov eax, edi
1b: 48 81 c4 a8 00 00 00 add rsp, 0xa8
22: 5f pop rdi
23: 5e pop rsi
24: c3 ret
Basically, we're only interested in the following instructions because they set up and tear down the stack frame:
push rsi ; Save the register `rsi` on the stack
push rdi ; Save the register `rdi` on the stack
sub rsp, 168 ; Allocate 168 bytes on the stack for local variables
... ; Instructions for calling `another_function`...
add rsp, 168 ; Deallocate the storage for locals
pop rdi ; Restore the previous value of `rdi`
pop rsi ; Restore the previous value of `rsi`
ret ; Return from the function
Let's take a look at the unwind information stored in the object file. This
information is stored in special sections called .pdata and .xdata that are
part of every Windows binary. Fortunately, llvm-objdump is able to read and
decode these sections for us:
$ llvm-objdump --unwind-info .\unwind.obj
.\unwind.obj: file format coff-x86-64
Unwind info:
Function Table:
Start Address: .text
End Address: .text + 0x0025
Unwind Info Address: .xdata
Version: 1
Flags: 0
Size of prolog: 9
Number of Codes: 4
No frame pointer used
Unwind Codes:
0x09: UOP_AllocLarge 21
0x02: UOP_PushNonVol RDI
0x01: UOP_PushNonVol RSI
We can see that the compiler has emitted three unwind codes for our function:
0x09: UOP_AllocLarge 21
0x02: UOP_PushNonVol RDI
0x01: UOP_PushNonVol RSI
These unwind codes declare that the function allocates 21 * 8 = 168 bytes of
stack memory for local variables and that it saves rsi and rdi by pushing
them onto the stack. Each unwind code is attached to an instruction:
push rsi <-- UOP_PushNonVol RSI
push rdi <-- UOP_PushNonVol RDI
sub rsp, 168 <-- UOP_AllocLarge 21
...
add rsp, 168
pop rdi
pop rsi
ret
In order to conform to Microsoft's ABI, we have to emit this unwind information
into the binary. To do so, the Banjo compiler tracks all instructions that
modify the stack in the x86-64 backend. When generating the binary, it encodes
the unwind information into the .pdata and .xdata sections. This has to be
done very carefully because even small errors in the unwind codes or the stack
frame layout can break unwinding entirely.
I've decided that unwinding the stack manually on Windows is too much work for
now, so we'll keep using CaptureStackBackTrace:
use os.winapi;
func trace_stack_windows() -> Array[addr] {
var frames = Array[addr].sized(4096)
var frame_count = winapi.capture_stack_back_trace(
1,
&frames.length() as winapi.Ulong,
&frames[0],
null,
)
frames.resize(frame_count as usize)
return frames
}
Embedding debug symbols
Since we want to print human-readable function names, we need to embed this
information into the executable somehow. We don't want to depend on the linker
to do this, so we add a custom debug section to each executable. Let's call this
section .bnjdbg because it contains debug information for the Banjo language.
The .bnjdbg section has the following layout:
number of function entries u64
end of last function address
first function address address
first function name offset u64
second function address address
second function name offset u64
[...]
first function name null-terminated string
second function name null-terminated string
[...]
Putting it all together
Now that the compiler has prepared the necessary debug information, we're able to resolve function names in our Banjo code like this:
use std.cursor.Cursor
func get_debug_info() -> Slice[u8] {
# Compiler magic that returns the data in the `.bnjdbg` section.
}
func symbol_name(address: addr) -> ?StringSlice {
var debug_info = get_debug_info()
var cursor = Cursor.new(debug_info)
var num_functions = cursor.read_u64_native().unwrap()
var text_end = cursor.read_u64_native().unwrap()
var start = cursor.read_u64_native().unwrap()
for i in 0..num_functions {
var name_offset = cursor.read_u64_native().unwrap()
var end = text_end
if i != num_functions - 1 {
end = cursor.read_u64_native().unwrap()
}
if address as u64 >= start && address as u64 < end {
var pointer = &self.slice[name_offset as usize]
return StringSlice.of_cstring(pointer)
} else {
start = end
}
}
return none
}
Let's hook up this function to print_stack:
func print_stack() {
println("stack trace:")
for frame in trace_stack() {
try name in symbol_name(frame) {
fprintln(" - 0x{:016x} {}", frame as u64, name)
}
}
}
And here's the output (drumroll, please):
$ banjo run
stack trace:
- 0x0000004310969520 print_stack
- 0x0000004310969824 some_function
- 0x0000004310969852 main
Et voilà! We've got cross-platform stack traces in a compiled language!
Better runtime panics
This functionality is now part of Banjo's standard library so we can print a stack trace when a runtime panic happens. For example, the following code tries to decode an invalid UTF-8 sequence:
func decode_utf8(slice: Slice[u8]) -> String {
var string = StringSlice.new(slice.data(), slice.length());
return String.from(string);
}
func main() {
var garbage: Slice[u8] = [0xAA, 0xBB, 0xCC, 0xDD];
var string = decode_utf8(garbage);
}
If we try to run this, we'll get the following output:
$ banjo run
panic: invalid utf-8 sequence
stack trace:
#001 0x0000004306375104 panic
#002 0x0000004306374108 panic_invalid_utf8
#003 0x0000004306385348 StringSlice.new
#004 0x0000004306396428 decode_utf8
#005 0x0000004306396552 main
Future improvements
The obvious next step would be attaching line numbers and file names to the call stack. This would require more information to be passed through the compilation pipeline but shouldn't be too difficult.
I'd also like to support stack traces when compiling to WebAssembly, but I don't
think there's a browser API for accessing the call stack (apart from
console.trace()). I think languages like Go maintain their own shadow stack to
do this, so I'd have to look into that.
No LLM was used to write this post, all grammar mistakes are human-made :)