Module 3: x64 Stack Unwinding

How Windows navigates the call stack without frame pointers — and why Draugr must speak the same language.

1. The Frame Pointer Problem

In 32-bit x86, stack walking was simple. Every function established a frame pointer by saving EBP, then setting EBP = ESP. To walk the stack, you simply followed the chain of saved EBP values — each one pointed to the previous frame's EBP, creating a linked list up the call stack:

x86 ASM; x86 standard function prolog:
push ebp           ; Save caller's frame pointer
mov  ebp, esp      ; Establish new frame pointer
sub  esp, 0x20     ; Allocate local variables

; Stack walking: follow EBP chain
; [EBP]     = previous EBP (caller's frame pointer)
; [EBP + 4] = return address (where to resume after RET)

x64 changed everything. The Microsoft x64 ABI does not require frame pointers. Most functions do not save or use RBP as a frame pointer. The reason: RBP is freed up as a general-purpose register, giving the compiler an extra register for optimization. On x64 with only 16 GPRs, that extra register matters.

2. RUNTIME_FUNCTION

Every non-leaf function (a function that calls other functions or modifies RSP) in a PE image has a corresponding RUNTIME_FUNCTION entry in the .pdata section. Leaf functions (which don't call anything and don't change RSP) don't need entries because their stack frame is zero-sized.

Ctypedef struct _RUNTIME_FUNCTION {
    DWORD BeginAddress;   // RVA of function start
    DWORD EndAddress;     // RVA of function end (exclusive)
    DWORD UnwindData;     // RVA of UNWIND_INFO structure
} RUNTIME_FUNCTION, *PRUNTIME_FUNCTION;

Given a return address captured during stack walking, the unwinder calls RtlLookupFunctionEntry to search the .pdata section for a RUNTIME_FUNCTION whose [BeginAddress, EndAddress) range contains that address. This is a binary search — the .pdata entries are sorted by BeginAddress.

C// Given a return address (RIP), find its RUNTIME_FUNCTION
PRUNTIME_FUNCTION RtlLookupFunctionEntry(
    DWORD64                ControlPc,    // The return address to look up
    PDWORD64               ImageBase,    // Output: base address of the module
    PUNWIND_HISTORY_TABLE  HistoryTable  // Optional: cache for repeated lookups
);

// Returns NULL if the address is in a leaf function (no .pdata entry)
// or if the address is not within any loaded module

3. UNWIND_INFO and UNWIND_CODEs

The UNWIND_INFO structure describes what a function's prolog does. The prolog is the sequence of instructions at the start of a function that sets up the stack frame — saving registers, allocating local variable space, establishing a frame pointer.

Ctypedef struct _UNWIND_INFO {
    UBYTE Version       : 3;    // Must be 1 (or 2 for chained)
    UBYTE Flags         : 5;    // UNW_FLAG_EHANDLER, UNW_FLAG_UHANDLER, UNW_FLAG_CHAININFO
    UBYTE SizeOfProlog;         // Size of the function prolog in bytes
    UBYTE CountOfCodes;         // Number of UNWIND_CODE entries
    UBYTE FrameRegister : 4;    // Frame register (0 = no frame register)
    UBYTE FrameOffset   : 4;    // Scaled offset of frame register from RSP
    UNWIND_CODE UnwindCode[1];  // Variable-length array of unwind operations
    // Followed by optional exception handler data
} UNWIND_INFO, *PUNWIND_INFO;

The UnwindCode array contains one or more UNWIND_CODE entries, each describing a single prolog operation. The codes are stored in reverse order (last prolog instruction first) so the unwinder can process them in the order needed to reverse the prolog.

Ctypedef union _UNWIND_CODE {
    struct {
        UBYTE CodeOffset;    // Offset in prolog where this operation occurs
        UBYTE UnwindOp : 4;  // Operation type (UWOP_*)
        UBYTE OpInfo   : 4;  // Operation-specific data
    };
    USHORT FrameOffset;      // Used as a 16-bit value for some operations
} UNWIND_CODE, *PUNWIND_CODE;

UNWIND_CODE Operations

Each unwind code type describes a specific prolog instruction and its effect on the stack:

Concrete Example

Consider a function with this prolog:

x86-64 ASM; Function prolog:
push rbx              ; Save non-volatile register  [UWOP_PUSH_NONVOL, reg=rbx]
push rdi              ; Save non-volatile register  [UWOP_PUSH_NONVOL, reg=rdi]
sub  rsp, 0x28        ; Allocate 40 bytes locals    [UWOP_ALLOC_SMALL, OpInfo=4]
                       ;   (OpInfo * 8 + 8 = 4*8+8 = 40 = 0x28)

; Total stack consumed = 8 (push rbx) + 8 (push rdi) + 40 (sub rsp) = 56 bytes
; Plus the 8-byte return address pushed by CALL = 64 bytes total frame

The UNWIND_INFO for this function would contain 3 UNWIND_CODEs (in reverse order):

UNWIND_CODEs (reverse order)[0] UWOP_ALLOC_SMALL   OpInfo=4   (sub rsp, 0x28)     +40 bytes
[1] UWOP_PUSH_NONVOL   OpInfo=7   (push rdi, reg=RDI)  +8 bytes
[2] UWOP_PUSH_NONVOL   OpInfo=3   (push rbx, reg=RBX)  +8 bytes

Total prolog stack consumption: 40 + 8 + 8 = 56 bytes
Frame size (including return addr): 56 + 8 = 64 bytes

4. RtlVirtualUnwind

RtlVirtualUnwind is the core Windows API that performs a single step of stack unwinding. Given the current PC (program counter/RIP) and a RUNTIME_FUNCTION, it reverses the prolog's effects to compute the caller's register state:

CPEXCEPTION_ROUTINE RtlVirtualUnwind(
    ULONG                          HandlerType,      // UNW_FLAG_NHANDLER usually
    DWORD64                        ImageBase,         // Module base address
    DWORD64                        ControlPc,         // Current RIP
    PRUNTIME_FUNCTION              FunctionEntry,     // From RtlLookupFunctionEntry
    PCONTEXT                       ContextRecord,     // In/out: register state
    PVOID                         *HandlerData,       // Output: exception handler data
    PDWORD64                       EstablisherFrame,  // Output: caller's RSP
    PKNONVOLATILE_CONTEXT_POINTERS ContextPointers    // Output: saved register locations
);

For each UNWIND_CODE, RtlVirtualUnwind reverses the corresponding prolog operation:

5. Chained Unwind Info

Some functions have complex prologs that can't be described by a single UNWIND_INFO. The UNW_FLAG_CHAININFO flag links one RUNTIME_FUNCTION to another, creating a chain of unwind data:

C// In the UNWIND_INFO for a function with chained info:
// Flags field contains UNW_FLAG_CHAININFO (0x04)
// After the UnwindCode array (padded to even count), there's another RUNTIME_FUNCTION

// Draugr handles this in DraugrCalculateStackSize:
// 1. Parse UNWIND_CODEs from the current UNWIND_INFO
// 2. Check if UNW_FLAG_CHAININFO is set
// 3. If yes, follow the chained RUNTIME_FUNCTION and repeat
// 4. Sum all stack sizes from the entire chain

6. Why Draugr Must Parse UNWIND_CODEs

When the stack walker processes a synthetic frame, it performs these steps:

1. Read a return address from the stack (this is the address Draugr placed)
2. Call RtlLookupFunctionEntry to find the RUNTIME_FUNCTION for that address
3. Read the UNWIND_INFO and compute the frame size from UNWIND_CODEs
4. Add the frame size to the current RSP to locate the next return address

Stack Layout (Draugr's Synthetic Frames); After Draugr builds the synthetic stack:
;
; [RSP + 0]                    = return addr into syscall stub (ntdll)
; [RSP + frameSize_BaseThread] = addr inside BaseThreadInitThunk
; [RSP + frameSize_BaseThread
;      + frameSize_RtlUser]    = addr inside RtlUserThreadStart
; [RSP + ... + 8]              = 0x0 (stack walk terminator)
;
; If frameSize_BaseThread is wrong, the unwinder looks at the wrong
; offset for the RtlUserThreadStart return address, and the entire
; spoof collapses.