Introspecting the Stack: Building a custom backtrace() from scratch

When a systems program crashes, a well-behaved segmentation fault handler uses libc’s backtrace() and backtrace_symbols_fd() to print a call stack before dying.

It works flawlessly, but in systems programming, “flawlessly” usually means there is a mountain of complex machinery hidden behind a convenient API. How does a process actually read its own call stack while running? And more importantly, how does it translate raw memory addresses back into human-readable function names?

To demystify this, we are going to ditch backtrace() and C built-ins. We are going one level deeper to build our own stack unwinder for Linux (ELF) in pure assembly, working directly with the registers. We’ll still use dladdr to look up symbol names, but we will write the unwinding loop ourselves. In the process, we will uncover a massive blind spot in the dynamic linker that trips up both C and assembly programmers.

The Stack Unwinding Theory

As we explored in The Anatomy of a Perfect Stack Trace, modern debuggers often use Call Frame Information (CFI) to unwind stacks. However, to do this dynamically at runtime without parsing .eh_frame DWARF metadata, we rely on a simpler mechanism: the Frame Pointer.

If you compile your C code with -fno-omit-frame-pointer, the compiler guarantees a specific structure on the stack.

x86_64 (AMD64)

On x86_64, the base pointer register %rbp acts as the frame pointer. At the start of every function, the old %rbp is pushed to the stack, and the new %rbp points to that exact location. Because the call instruction pushes the return address right before this, memory looks like this:

• [rbp] contains the previous frame pointer.
• [rbp + 8] contains the return address.

ARM64 (AArch64)

On ARM64, the convention uses x29 as the frame pointer and x30 as the link register (which holds the return address). During the function prologue, these two registers are stored side-by-side on the stack:

• [x29] contains the previous frame pointer.
• [x29 + 8] contains the return address (saved x30).

By dereferencing the frame pointer, we can walk a linked list of frames up the stack.

The Assembly Implementation

We need to write a loop in assembly that traverses this linked list. For every return address we find, we must call dladdr() from the C dynamic linking API (dlfcn.h) to resolve the symbol name.

The Dl_info struct in C looks like this:

typedef struct {
  const char *dli_fname;  /* Pathname of shared object */
  void       *dli_fbase;  /* Base address of shared object */
  const char *dli_sname;  /* Name of nearest symbol */
  void       *dli_saddr;  /* Exact address of symbol */
} Dl_info;

This is a 32-byte struct (four 8-byte pointers). To call dladdr(address, &info) from assembly, we must allocate space on the stack, pass the return address as the first argument, and pass the stack pointer as the second argument.

The x86_64 Unwinder

Here is the complete implementation in GNU Assembler (GAS) for x86_64. We use .intel_syntax noprefix for readability. We walk the %rbp chain, allocate the Dl_info struct, and invoke dladdr and printf. We also allocate 40 bytes instead of 32 to guarantee the 16-byte stack alignment required by the System V ABI before making C function calls.

.intel_syntax noprefix
.global custom_backtrace
.type custom_backtrace, @function

.section .rodata
.Lfmt_found: .string "#%d  %p in %s (%s)
"
.Lfmt_unknown: .string "#%d  %p in ??? (%s)
"
.Lstr_unknown_path: .string "???"

.text
custom_backtrace:
  push rbp
  mov rbp, rsp
  
  # Save callee-saved registers we plan to use
  push rbx
  push r12
  push r13
  
  # rbx = current frame. Start at our own frame record; 
  # its return address belongs to our caller.
  mov rbx, rbp
  
  # r12 = depth counter
  xor r12, r12

.Lloop:
  test rbx, rbx          # If frame pointer is NULL, we are done
  jz .Ldone
  
  cmp r12, 50            # Max depth safeguard
  jge .Ldone

  # Extract return address into r13
  mov r13, [rbx + 8]
  test r13, r13
  jz .Ldone
  
  # Allocate 40 bytes for Dl_info struct on the stack.
  # (32 bytes for struct + 8 bytes padding to keep stack 16-byte aligned.
  #  The 'call' instruction breaks alignment, 'push rbp' restores it, 
  #  the 3 pushes break it again, and 'sub 40' fixes it).
  sub rsp, 40
  
  # Zero out the 32 bytes of Dl_info so we don't read garbage if dladdr fails
  mov qword ptr [rsp], 0
  mov qword ptr [rsp + 8], 0
  mov qword ptr [rsp + 16], 0
  mov qword ptr [rsp + 24], 0
  
  # Call dladdr(return_addr, &info)
  mov rdi, r13           # Arg 1: return address
  mov rsi, rsp           # Arg 2: pointer to Dl_info struct
  call dladdr
  
  # Safely get info.dli_fname (offset 0), fallback to "???" if NULL
  mov r8, [rsp]
  test r8, r8
  jnz .Lfname_ok
  lea r8, [rip + .Lstr_unknown_path]
.Lfname_ok:

  # Check if dladdr succeeded (returns non-zero)
  test eax, eax
  jz .Lprint_unknown
  
  # Check if info.dli_sname (offset 16) is not NULL
  mov rcx, [rsp + 16]
  test rcx, rcx
  jz .Lprint_unknown

.Lprint_found:
  # printf("#%d  %p in %s (%s)
", depth, ret_addr, sname, fname)
  lea rdi, [rip + .Lfmt_found]
  mov rsi, r12
  mov rdx, r13
  # rcx already holds info.dli_sname
  # r8 already holds info.dli_fname
  xor eax, eax           # 0 floating point args for printf
  call printf
  jmp .Lnext_frame

.Lprint_unknown:
  # printf("#%d  %p in ??? (%s)
", depth, ret_addr, fname)
  lea rdi, [rip + .Lfmt_unknown]
  mov rsi, r12
  mov rdx, r13
  mov rcx, r8            # Safe fname pointer
  xor eax, eax
  call printf

.Lnext_frame:
  add rsp, 40            # Deallocate Dl_info struct
  
  # Load next frame pointer and perform a safety check:
  # The stack grows downward, so older frames must be at higher addresses.
  mov rax, [rbx]
  cmp rax, rbx           # next_frame <= current_frame?
  jbe .Ldone             # If so, the chain is broken, exit.
  
  mov rbx, rax
  inc r12                # depth++
  jmp .Lloop

.Ldone:
  pop r13
  pop r12
  pop rbx
  pop rbp
  ret
.size custom_backtrace, .-custom_backtrace

The ARM64 Unwinder

The logic is identical on ARM64, but we use x29 and x30. We must also strictly adhere to the AAPCS64 requirement that the stack pointer (sp) is always 16-byte aligned. (Note: This assumes the Linux AAPCS64 ABI where variadic arguments are passed in registers. macOS uses a different convention where variadic arguments are passed on the stack).

.global custom_backtrace
.type custom_backtrace, %function

.section .rodata
.Lfmt_found: .string "#%d  %p in %s (%s)
"
.Lfmt_unknown: .string "#%d  %p in ??? (%s)
"
.Lstr_unknown_path: .string "???"

.text
.align 2
custom_backtrace:
  // Prologue: save FP and LR
  stp x29, x30, [sp, -16]!
  mov x29, sp
  
  // Save callee-saved registers
  stp x19, x20, [sp, -16]!
  str x21, [sp, -16]!
  
  // x19 = current frame. Start at our own frame record;
  // its return address belongs to our caller.
  mov x19, x29
  // x20 = depth counter
  mov x20, 0

.Lloop:
  cbz x19, .Ldone        // If FP is NULL, exit
  cmp x20, 50            // Max depth
  b.ge .Ldone

  // Extract return address (FP + 8)
  ldr x21, [x19, 8]
  cbz x21, .Ldone
  
  // Allocate 32 bytes for Dl_info (maintains 16-byte alignment)
  sub sp, sp, 32
  
  // Zero out Dl_info so we don't read garbage if dladdr fails
  str xzr, [sp, 0]
  str xzr, [sp, 8]
  str xzr, [sp, 16]
  str xzr, [sp, 24]
  
  // Call dladdr(return_addr, &info)
  mov x0, x21
  mov x1, sp
  bl dladdr
  
  // Safely get info.dli_fname, fallback to "???" if NULL
  ldr x4, [sp, 0]
  cbnz x4, .Lfname_ok
  adrp x4, .Lstr_unknown_path
  add x4, x4, :lo12:.Lstr_unknown_path
.Lfname_ok:

  // Check if dladdr succeeded
  cbz w0, .Lprint_unknown
  
  // Check if info.dli_sname (offset 16) is not NULL
  ldr x3, [sp, 16]
  cbz x3, .Lprint_unknown

.Lprint_found:
  // printf args: x0=fmt, x1=depth, x2=ret, x3=sname, x4=fname
  adrp x0, .Lfmt_found
  add x0, x0, :lo12:.Lfmt_found
  mov x1, x20
  mov x2, x21
  // x3 already contains sname
  // x4 already contains safe fname
  bl printf
  b .Lnext_frame

.Lprint_unknown:
  // printf args: x0=fmt, x1=depth, x2=ret, x3=fname
  adrp x0, .Lfmt_unknown
  add x0, x0, :lo12:.Lfmt_unknown
  mov x1, x20
  mov x2, x21
  mov x3, x4             // Safe fname pointer
  bl printf

.Lnext_frame:
  add sp, sp, 32         // Deallocate Dl_info
  
  // Load next frame pointer and verify it grows upward in memory
  ldr x0, [x19]
  cmp x0, x19            // next_frame <= current_frame?
  b.ls .Ldone            // If so, the chain is broken, exit.
  
  mov x19, x0
  add x20, x20, 1        // depth++
  b .Lloop

.Ldone:
  ldr x21, [sp], 16
  ldp x19, x20, [sp], 16
  ldp x29, x30, [sp], 16
  ret
.size custom_backtrace, .-custom_backtrace

The C Driver

To test this, we link our assembly file with a simple C driver:

extern void custom_backtrace();

void func_c() { custom_backtrace(); }
void func_b() { func_c(); }
void func_a() { func_b(); }

int main() {
  func_a();
  return 0;
}

The First Roadblock: The Symbol Table

Let’s compile this on Linux and run it. We will use -no-pie to force predictable non-PIE memory addresses so the output is easier to read.

$ gcc -fno-omit-frame-pointer -no-pie main.c unwinder.s -o my_app
$ ./my_app

The Output:

#0  0x40123c in ??? ()
#1  0x40124c in ??? ()
#2  0x40125c in ??? ()
#3  0x40126c in ??? ()
#4  0x7fb68c429d90 in ??? (/lib/x86_64-linux-gnu/libc.so.6)

Wait. The unwinder successfully walked the frame pointers up through main, and found a 5th frame inside libc.so.6. (It safely truncates after this frame because glibc’s _start zeroes %rbp to mark the outermost frame, as the System V ABI recommends. Our ascending-frame safety check sees 0x0 and safely stops the loop).

But notice what happened. dladdr() successfully identified the shared object path for the libc frame (proving the API call worked), but all of the actual function names (func_c, func_b, func_a, main, and __libc_start_call_main) show up as ???. Why did it find the library file, but not the names? (And why is the main executable’s path empty? On glibc, the dynamic loader’s link map name for the main program is simply the empty string, yielding ()).

The answer lies in how dladdr works. When you ask the dynamic loader to resolve an address, it does not look at the standard static symbol table (.symtab) that a debugger like GDB uses.

Instead, it scans the dynamic symbol table (.dynsym).

By default, the ELF linker only places symbols in the .dynsym table if they need to be exported to (or imported from) a shared library. Since our functions are internal to the executable, the linker completely strips them from the dynamic symbol table to save space and reduce resolution overhead. (The same is true for internal libc functions like __libc_start_call_main—it’s a local symbol stripped from libc’s dynamic exports).

To fix this on Linux, we must explicitly tell the linker to export all symbols to the dynamic symbol table using the -rdynamic flag:

$ gcc -fno-omit-frame-pointer -no-pie -rdynamic main.c unwinder.s -o my_app

Let’s run it again:

#0  0x40123c in func_c ()
#1  0x40124c in func_b ()
#2  0x40125c in func_a ()
#3  0x40126c in main ()
#4  0x7fb68c429d90 in ??? (/lib/x86_64-linux-gnu/libc.so.6)

Perfect! dladdr() can finally see our internal code.

The Second Roadblock: Assembly and Size Directives

Now, let’s say we had written func_c in raw assembly rather than C (assuming we still emitted the standard push rbp; mov rbp, rsp prologue to maintain the frame chain). We link it in, compile with -rdynamic, and run the trace.

#0  0x40123c in ??? ()
#1  0x40124c in func_b ()
#2  0x40125c in func_a ()
#3  0x40126c in main ()
#4  0x7fb68c429d90 in ??? (/lib/x86_64-linux-gnu/libc.so.6)

It’s broken again. Even with -rdynamic, an assembly function will often refuse to resolve!

When the C compiler generates code, it doesn’t just emit machine instructions; it emits ELF metadata. For glibc’s dladdr() to match a raw instruction pointer to a function, it looks through .dynsym for a symbol where the instruction pointer falls between st_value (the start address) and st_value + st_size (the end address).

If you write a raw assembly function and forget to specify its size, st_size defaults to 0. dladdr() treats a zero-sized symbol as matching only its exact start address. Since our return address points to the instruction after the call (inside the function body), dladdr assumes the address cannot possibly be inside it, and skips it!

To fix this, you must explicitly declare the .type and .size of your assembly function. Notice how we did this at the end of our custom unwinder files:

For x86_64

.global custom_backtrace
.type custom_backtrace, @function

custom_backtrace:
  # ... code ...
  ret

.size custom_backtrace, .-custom_backtrace

For ARM64

.global custom_backtrace
.type custom_backtrace, %function

custom_backtrace:
  // ... code ...
  ret

.size custom_backtrace, .-custom_backtrace

With those directives, st_size is populated (by calculating the difference between the current address . and the function’s start label). The dynamic loader now knows the boundaries of the function, and dladdr() perfectly resolves the backtrace.

A Note on Signal Handlers

We opened this article by talking about segmentation fault handlers, but there is a crucial catch to our implementation: neither printf() nor dladdr() are async-signal-safe.

printf acquires stream locks, and dladdr acquires dynamic loader locks. If your program crashes while holding one of those locks, calling these functions inside the SIGSEGV handler risks an unrecoverable deadlock.

This is exactly why libc provides backtrace_symbols_fd() instead of relying on printf. It avoids malloc() and uses the safe write() syscall to dump output directly to a file descriptor. However, even backtrace_symbols_fd() must look up symbols via the dynamic loader, meaning it is still vulnerable to the loader-lock hazard. Furthermore, libc’s backtrace() itself lazily loads the libgcc unwinder on first use, which can trigger a dangerous dlopen inside your crash path.

In a robust production crash handler, you should call backtrace() once during program startup to force the unwinder to load. Then, in the actual crash handler, safely dump the raw return addresses directly to a file descriptor and resolve the symbol names later via an out-of-process tool.

Stripping Away the Magic

By writing the unwinding loop by hand in assembly, we’ve stripped away the abstraction. A backtrace isn’t a mystical capability embedded in the operating system; it is nothing more than a linked list of stack frames and a dynamic symbol table lookup.