Stack unwinding and exception handling data on x86-64 and x86

To unwind a frame is to compute the state of the caller from that of the function: the address it returns to, the caller’s stack pointer, and the values of the callee-saved registers the function changed. The return address is on the stack, but where depends on how much the function has pushed and allocated so far, which changes instruction by instruction in its prolog and epilog. A debugger showing a backtrace, a profiler sampling where time goes and an exception looking for its handler all repeat this step from frame to frame.

There are two ways to know. A frame pointer turns the frames into a linked list that can be followed without any other data. Unwind tables describe each function, so that its frames can be unwound even without a frame pointer; System V and Windows x64 use them. 32-bit Windows does something else: functions with exception handlers link records on the stack.

Frame pointers#

A function that keeps a frame pointer pushes the caller’s RBP and points RBP at that slot, so each frame’s RBP leads to the saved RBP of the caller, with the return address just above it. Following the chain needs nothing but the stack. The stack frames page shows such a frame; GCC and Clang build one on x86-64 Linux only when asked with -fno-omit-frame-pointer.

Linux’s perf record walks this chain by default to record the call graph of user-space code. Its documentation warns that code built without frame pointers gives bogus call graphs that way, and offers two other methods: dwarf, which copies part of the stack at each sample and unwinds it later with the unwind tables, and lbr, which reads the processor’s record of the last branches taken.

DWARF call frame information#

The x86-64 psABI requires every function to have unwind information in the format of DWARF’s call frame information, and hand-written assembly too. The compiler writes it as .cfi_ directives among the instructions, and the assembler turns them into the function’s entry in the .eh_frame section. GCC and Clang do so by default on x86-64 Linux; the other listings of this site leave them out with -fno-asynchronous-unwind-tables, which a later -fasynchronous-unwind-tables overrides.

The table is built around the canonical frame address, the CFA: the value of the stack pointer at the call, in the caller’s frame, which stays the same for the whole life of the frame. On x86-64 the return address is at CFA-8. For every instruction the table gives a rule for the CFA, a register plus an offset, and says where the function has saved each callee-saved register, at an offset from the CFA. The psABI numbers the registers for this:

/* A function that saves two registers, keeps an array on the stack
   and calls another: its unwind information tells where each is. */
extern long use(long *p);

long work(long a, long b)
{
	long buf[4] = { a, b };
	long r = use(buf);

	return r + a * b;
}

work:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsi, %rbp
        pxor    %xmm0, %xmm0
        pushq   %rbx
        .cfi_def_cfa_offset 24
        .cfi_offset 3, -24
        movq    %rdi, %rbx
        imulq   %rbp, %rbx
        subq    $40, %rsp
        .cfi_def_cfa_offset 64
        movq    %rdi, (%rsp)
        movq    %rsp, %rdi
        movq    %rsi, 8(%rsp)
        movaps  %xmm0, 16(%rsp)
        call    use@PLT
        addq    $40, %rsp
        .cfi_def_cfa_offset 24
        addq    %rbx, %rax
        popq    %rbx
        .cfi_def_cfa_offset 16
        popq    %rbp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc

work:
        .cfi_startproc
        push    rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        mov     rbp, rsi
        pxor    xmm0, xmm0
        push    rbx
        .cfi_def_cfa_offset 24
        .cfi_offset 3, -24
        mov     rbx, rdi
        imul    rbx, rbp
        sub     rsp, 40
        .cfi_def_cfa_offset 64
        mov     QWORD PTR [rsp], rdi
        mov     rdi, rsp
        mov     QWORD PTR 8[rsp], rsi
        movaps  XMMWORD PTR 16[rsp], xmm0
        call    use@PLT
        add     rsp, 40
        .cfi_def_cfa_offset 24
        add     rax, rbx
        pop     rbx
        .cfi_def_cfa_offset 16
        pop     rbp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc

work:
        .cfi_startproc
        pushq   %r14
        .cfi_def_cfa_offset 16
        pushq   %rbx
        .cfi_def_cfa_offset 24
        subq    $40, %rsp
        .cfi_def_cfa_offset 64
        .cfi_offset %rbx, -24
        .cfi_offset %r14, -16
        movq    %rsi, %rbx
        movq    %rdi, %r14
        movq    %rdi, (%rsp)
        movq    %rsi, 8(%rsp)
        xorps   %xmm0, %xmm0
        movaps  %xmm0, 16(%rsp)
        movq    %rsp, %rdi
        callq   use@PLT
        imulq   %r14, %rbx
        addq    %rbx, %rax
        addq    $40, %rsp
        .cfi_def_cfa_offset 24
        popq    %rbx
        .cfi_def_cfa_offset 16
        popq    %r14
        .cfi_def_cfa_offset 8
        retq
        .cfi_endproc

work:
        .cfi_startproc
        push    r14
        .cfi_def_cfa_offset 16
        push    rbx
        .cfi_def_cfa_offset 24
        sub     rsp, 40
        .cfi_def_cfa_offset 64
        .cfi_offset rbx, -24
        .cfi_offset r14, -16
        mov     rbx, rsi
        mov     r14, rdi
        mov     qword ptr [rsp], rdi
        mov     qword ptr [rsp + 8], rsi
        xorps   xmm0, xmm0
        movaps  xmmword ptr [rsp + 16], xmm0
        mov     rdi, rsp
        call    use@PLT
        imul    rbx, r14
        add     rax, rbx
        add     rsp, 40
        .cfi_def_cfa_offset 24
        pop     rbx
        .cfi_def_cfa_offset 16
        pop     r14
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc

GCC’s manual calls such a table asynchronous: it is exact at each instruction boundary, so a debugger or a garbage collector can stop the code anywhere and still unwind it. With a frame pointer the rules become simpler. Once RBP is set, the CFA is RBP+16 whatever RSP does, and only the saved registers need further directives.

/* A function that saves two registers, keeps an array on the stack
   and calls another: its unwind information tells where each is. */
extern long use(long *p);

long work(long a, long b)
{
	long buf[4] = { a, b };
	long r = use(buf);

	return r + a * b;
}

work:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        pxor    %xmm0, %xmm0
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        pushq   %r12
        .cfi_offset 12, -24
        movq    %rsi, %r12
        pushq   %rbx
        .cfi_offset 3, -32
        movq    %rdi, %rbx
        imulq   %r12, %rbx
        subq    $32, %rsp
        movq    %rdi, -48(%rbp)
        leaq    -48(%rbp), %rdi
        movq    %rsi, -40(%rbp)
        movaps  %xmm0, -32(%rbp)
        call    use@PLT
        addq    $32, %rsp
        addq    %rbx, %rax
        popq    %rbx
        popq    %r12
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

work:
        .cfi_startproc
        push    rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        pxor    xmm0, xmm0
        mov     rbp, rsp
        .cfi_def_cfa_register 6
        push    r12
        .cfi_offset 12, -24
        mov     r12, rsi
        push    rbx
        .cfi_offset 3, -32
        mov     rbx, rdi
        imul    rbx, r12
        sub     rsp, 32
        mov     QWORD PTR -48[rbp], rdi
        lea     rdi, -48[rbp]
        mov     QWORD PTR -40[rbp], rsi
        movaps  XMMWORD PTR -32[rbp], xmm0
        call    use@PLT
        add     rsp, 32
        add     rax, rbx
        pop     rbx
        pop     r12
        pop     rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

Exceptions build on these tables. The psABI defines an unwind library, with functions such as _Unwind_RaiseException, which walks the frames in two phases: it first searches for a handler without changing anything, and only when one is found unwinds the frames for real, running their cleanups. At each frame it calls the function’s personality routine, which the language supplies, with data of its own that the unwind information points to. C code gets unwind tables for exceptions with -fexceptions, which GCC enables by default only for languages like C++; the C++ ABIs page shows the data of try and catch.

Windows x64: .pdata and .xdata#

Windows x64 requires unwind data for every function that allocates stack space or calls another function. A table in the .pdata section has one entry per function, RUNTIME_FUNCTION: the function’s start and end and the address of its UNWIND_INFO in .xdata. That holds the size of the prolog, the frame register if the function uses one, an array of unwind codes and, optionally, an exception handler. A function without an entry is a leaf, and RSP points to its return address.

The unwind codes describe only the prolog, each saying what one of its instructions did: pushed a register, allocated so many bytes, set the frame pointer. The epilog has none. When an exception interrupts an epilog, the unwinder recognizes it by reading the code that follows, which is why Microsoft restricts epilogs to a few forms; in the prolog it undoes the codes of the instructions already executed.

/* A function that saves two registers, keeps an array on the stack
   and calls another: its unwind information tells where each is. */
extern long use(long *p);

long work(long a, long b)
{
	long buf[4] = { a, b };
	long r = use(buf);

	return r + a * b;
}

work:
.seh_proc work
        pushq   %rsi
        .seh_pushreg %rsi
        pushq   %rdi
        .seh_pushreg %rdi
        subq    $56, %rsp
        .seh_stackalloc 56
        .seh_endprologue
        movl    %edx, %esi
        movl    %ecx, %edi
        movl    %ecx, 40(%rsp)
        movl    %edx, 44(%rsp)
        movq    $0, 48(%rsp)
        leaq    40(%rsp), %rcx
        callq   use
        imull   %edi, %esi
        addl    %esi, %eax
        .seh_startepilogue
        addq    $56, %rsp
        popq    %rdi
        popq    %rsi
        .seh_endepilogue
        retq
        .seh_endproc

work:
.seh_proc work
        push    rsi
        .seh_pushreg rsi
        push    rdi
        .seh_pushreg rdi
        sub     rsp, 56
        .seh_stackalloc 56
        .seh_endprologue
        mov     esi, edx
        mov     edi, ecx
        mov     dword ptr [rsp + 40], ecx
        mov     dword ptr [rsp + 44], edx
        mov     qword ptr [rsp + 48], 0
        lea     rcx, [rsp + 40]
        call    use
        imul    esi, edi
        add     eax, esi
        .seh_startepilogue
        add     rsp, 56
        pop     rdi
        pop     rsi
        .seh_endepilogue
        ret
        .seh_endproc

        .seh_proc       work
work:
        pushq   %rsi
        .seh_pushreg    %rsi
        pushq   %rbx
        .seh_pushreg    %rbx
        subq    $56, %rsp
        .seh_stackalloc 56
        .seh_endprologue
        movl    %edx, %esi
        movl    %ecx, %ebx
        movl    %ecx, 32(%rsp)
        leaq    32(%rsp), %rcx
        imull   %esi, %ebx
        movl    %edx, 36(%rsp)
        movq    $0, 40(%rsp)
        call    use
        addl    %ebx, %eax
        addq    $56, %rsp
        popq    %rbx
        popq    %rsi
        ret
        .seh_endproc

        .seh_proc       work
work:
        push    rsi
        .seh_pushreg    rsi
        push    rbx
        .seh_pushreg    rbx
        sub     rsp, 56
        .seh_stackalloc 56
        .seh_endprologue
        mov     esi, edx
        mov     ebx, ecx
        mov     DWORD PTR 32[rsp], ecx
        lea     rcx, 32[rsp]
        imul    ebx, esi
        mov     DWORD PTR 36[rsp], edx
        mov     QWORD PTR 40[rsp], 0
        call    use
        add     eax, ebx
        add     rsp, 56
        pop     rbx
        pop     rsi
        ret
        .seh_endproc

When an exception reaches a function whose UNWIND_INFO names a handler, the unwinder calls that handler, which reads the data that follows it, in a format of its own. For __try and __except, the structured exception handling that Microsoft added to C and C++, Clang names the handler of the C runtime and a table of the protected ranges. Nothing runs when the program enters a __try block; the cost comes only when an exception occurs.

/* Structured exception handling, a C extension of Microsoft's
   compilers that Clang implements for Windows targets. */
extern int risky(int *p);

int guarded(int *p)
{
	__try {
		return risky(p);
	} __except (1) {
		return -1;
	}
}

guarded:
.seh_proc guarded
        .seh_handler __C_specific_handler, @unwind, @except
        pushq   %rbp
        .seh_pushreg %rbp
        subq    $32, %rsp
        .seh_stackalloc 32
        leaq    32(%rsp), %rbp
        .seh_setframe %rbp, 32
        .seh_endprologue
.Ltmp0:
        callq   risky
        nop
.Ltmp1:
.LBB0_2:
        .seh_startepilogue
        addq    $32, %rsp
        popq    %rbp
        .seh_endepilogue
        retq
.LBB0_1:
        movl    $-1, %eax
        jmp     .LBB0_2
        .seh_handlerdata
        .long   (.Llsda_end0-.Llsda_begin0)/16
.Llsda_begin0:
        .long   .Ltmp0@IMGREL
        .long   .Ltmp1@IMGREL
        .long   1
        .long   .LBB0_1@IMGREL
.Llsda_end0:
        .seh_endproc

guarded:
.seh_proc guarded
        .seh_handler __C_specific_handler, @unwind, @except
        push    rbp
        .seh_pushreg rbp
        sub     rsp, 32
        .seh_stackalloc 32
        lea     rbp, [rsp + 32]
        .seh_setframe rbp, 32
        .seh_endprologue
.Ltmp0:
        call    risky
        nop
.Ltmp1:
.LBB0_2:
        .seh_startepilogue
        add     rsp, 32
        pop     rbp
        .seh_endepilogue
        ret
.LBB0_1:
        mov     eax, -1
        jmp     .LBB0_2
        .seh_handlerdata
        .long   (.Llsda_end0-.Llsda_begin0)/16
.Llsda_begin0:
        .long   .Ltmp0@IMGREL
        .long   .Ltmp1@IMGREL
        .long   1
        .long   .LBB0_1@IMGREL
.Llsda_end0:
        .seh_endproc

32-bit Windows: SEH frame chains#

32-bit Windows has no unwind tables. The first field of the thread information block at FS:0 points to a chain of exception registration records on the stack, each with a pointer to the next and the address of a handler. A function with a handler builds its record in its frame on entry, links it in front of the chain and unlinks it before it returns. When an exception occurs, the system finds the handlers through this chain.

/* Structured exception handling, a C extension of Microsoft's
   compilers that Clang implements for Windows targets. */
extern int risky(int *p);

int guarded(int *p)
{
	__try {
		return risky(p);
	} __except (1) {
		return -1;
	}
}

_guarded:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        pushl   %edi
        pushl   %esi
        subl    $28, %esp
        movl    %esp, -36(%ebp)
        movl    $-1, -16(%ebp)
        movl    $L__ehtable$guarded, -20(%ebp)
        movl    $__except_handler3, -24(%ebp)
        movl    8(%ebp), %eax
        leal    -28(%ebp), %ecx
Lguarded$frame_escape_0 = -40
        movl    %fs:0, %edx
        movl    %edx, -28(%ebp)
        movl    %ecx, %fs:0
        movl    $0, -16(%ebp)
        pushl   %eax
        calll   _risky
        addl    $4, %esp
LBB0_2:
        movl    -28(%ebp), %ecx
        movl    %ecx, %fs:0
        addl    $28, %esp
        popl    %esi
        popl    %edi
        popl    %ebx
        popl    %ebp
        retl
LBB0_1:
        movl    -24(%ebp), %esp
        addl    $12, %ebp
        movl    $-1, %eax
        jmp     LBB0_2
Lguarded$parent_frame_offset = -36

L__ehtable$guarded:
        .long   -1
        .long   "?filt$0@0@guarded@@"
        .long   LBB0_1

"?filt$0@0@guarded@@":
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %esi
        movl    (%ebp), %eax
        movl    $Lguarded$parent_frame_offset, %esi
        movl    $Lguarded$frame_escape_0, %ecx
        movl    -20(%eax), %edx
        subl    %esi, %eax
        movl    (%edx), %edx
        movl    (%edx), %edx
        movl    %edx, -24(%ecx,%eax)
        movl    $1, %eax
        popl    %esi
        popl    %ebp
        retl
        .safeseh        __except_handler3

_guarded:
        push    ebp
        mov     ebp, esp
        push    ebx
        push    edi
        push    esi
        sub     esp, 28
        mov     dword ptr [ebp - 36], esp
        mov     dword ptr [ebp - 16], -1
        mov     dword ptr [ebp - 20], offset L__ehtable$guarded
        mov     dword ptr [ebp - 24], offset __except_handler3
        mov     eax, dword ptr [ebp + 8]
        lea     ecx, [ebp - 28]
Lguarded$frame_escape_0 = -40
        mov     edx, dword ptr fs:[0]
        mov     dword ptr [ebp - 28], edx
        mov     dword ptr fs:[0], ecx
        mov     dword ptr [ebp - 16], 0
        push    eax
        call    _risky
        add     esp, 4
LBB0_2:
        mov     ecx, dword ptr [ebp - 28]
        mov     dword ptr fs:[0], ecx
        add     esp, 28
        pop     esi
        pop     edi
        pop     ebx
        pop     ebp
        ret
LBB0_1:
        mov     esp, dword ptr [ebp - 24]
        add     ebp, 12
        mov     eax, -1
        jmp     LBB0_2
Lguarded$parent_frame_offset = -36

L__ehtable$guarded:
        .long   -1
        .long   "?filt$0@0@guarded@@"
        .long   LBB0_1

"?filt$0@0@guarded@@":
        push    ebp
        mov     ebp, esp
        push    esi
        mov     eax, dword ptr [ebp]
        mov     esi, offset Lguarded$parent_frame_offset
        mov     ecx, offset Lguarded$frame_escape_0
        mov     edx, dword ptr [eax - 20]
        sub     eax, esi
        mov     edx, dword ptr [edx]
        mov     edx, dword ptr [edx]
        mov     dword ptr [ecx + eax - 24], edx
        mov     eax, 1
        pop     esi
        pop     ebp
        ret
        .safeseh        __except_handler3

The chain costs time in every call of such a function, exception or not, and it keeps the addresses of handlers in writable memory. The linker can also list the valid handlers of an image, with /SAFESEH, which tells the system which handlers belong to it; .safeseh in the listing adds _except_handler3 to that list. The same chain carries C++ exceptions on 32-bit Windows, with the handler __CxxFrameHandler3.

Shadow stacks#

The shadow stack of Intel’s CET is a second stack, which the program cannot write to directly. CALL pushes the return address on both stacks, and RET compares the two copies and raises a control-protection fault if they differ. An object file says in its ELF notes whether it was built for shadow stacks; on Linux the dynamic loader turns them on, per thread, when the program and all the libraries it starts with are marked, and only for 64-bit programs. On Windows, the linker option /CETCOMPAT marks an x64 image as compatible.

Unwinding must keep the two stacks in step. When longjmp or an exception leaves several frames at once, their return addresses stay on the shadow stack, and the next RET would fault. glibc’s longjmp and the unwinder of libgcc therefore count the frames they skip and pop them from the shadow stack with INCSSP, at most 255 per instruction, in a loop. longjmp also uses RSTORSSP when it has to return to a different shadow stack.

Summary#