Keyboard Shortcuts

Ctrl+K
Open search
Esc
Close search / dialog
↑
Back to top

Unwinding, and the Second Language

25 minadvancedModule 2: The Second Description: Unwinding and the AuditContinues from x86-varargs
25 min · The x86-64 ABI

Why this matters

You have spent four concepts learning that a frame is described by a prologue: a push, a sub, a mov. The instructions say what happens. Now imagine you are a profiler, or a crash reporter, or a debugger, and you are standing in a function that has already run its prologue and you want to know where the frame above it is.

You cannot get that from the instructions, and the reason is not that they are hard to read. It is that the information is not there in a form you can use. The prologue ran; its pushes are gone. The return address is at 0(%rsp) and the saved %rbp is at 8(%rsp)if the function pushed one, and whether it pushed one is a property of the code that has already executed. The hardware will not tell you, because the hardware was not told.

So the compiler writes it down. A second time, in a second language, in a table the profiler reads. That is the whole subject of this concept, and it is the reason an ABI has to be more than a register assignment: the calling convention describes how to make a call, and the unwind information describes how to walk back through one, and neither can be derived from the other.

The model: the Canonical Frame Address, and a table of deltas

The unwind information answers one question repeatedly, at every program counter in a function: where is the Canonical Frame Address? The CFA is not a saved register and it is not a memory location. It is defined as the value %rsp would have had, at that program counter, immediately before the function's prologue ran — which is to say, at the function's entry, plus 8 for the return address.

Once you know the CFA, everything else is a fixed offset from it. And so the description of a whole function is a list of (where in the code, what has happened to the CFA, which register is at which offset from it) pairs.

Here is a real one, and it is a function you have already met in this course: f7, the seven-argument function from the calling convention, compiled at -O2 where it has no frame pointer at all.

$ gcc -O2 -S -o abidump.s abidump_corpus.c && sed -n '/^f7:/,/^\.LFE/p' abidump.s
f7:
	.cfi_startproc
	endbr64
	subq	$8, %rsp
	.cfi_def_cfa_offset 16          <- the CFA is now rsp+16
	movq	16(%rsp), %r10
	lea	rdi,[rdi+rsi*1]
	add	rdi,rdx
	add	rdi,rcx
	add	rdi,r8
	add	rdi,r9
	add	rdi,r10
	call	abi_sink
	movl	$7, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 8           <- and back to rsp+8
	.cfi_endproc
  

There is no push %rbp and no frame pointer, so the CFA cannot be recovered by following a chain of saved frame pointers. It is recovered by a rule: at this program counter, the CFA is %rsp plus 16. And that rule is a consequence of the two subq/addq of 8 and the return address.

Now look at the instruction it annotates, because this is the payoff and it links straight back to the first concept:

movq 16(%rsp), %r10 16(%rsp) is the CFA, by the rule above. The CFA is rsp+8 at the function's entry. So 16(%rsp) is entry_rsp + 8. And entry_rsp + 8 is 8 bytes past the return address. THE SEVENTH ARGUMENT. The first concept measured its address as `stack=0x10` in the disassembly, from the other side of the call. The unwind table states the same address as a fact about where the CFA is, and both readers agree.

So the CFI is not a separate piece of bookkeeping bolted onto the end. It is the same frame, described a second time, in a language whose whole purpose is to be read by something that was not there when the frame was built. And the two descriptions can be checked against each other, which is a thing you almost never get to do with a compiler's internal state.

The vocabulary

The directives are few, and each one is a small edit to a small state machine:

THE .cfi_* DIRECTIVES, AND WHAT EACH ONE DOES .cfi_startproc begin a frame description .cfi_endproc end it .cfi_def_cfa_offset N the CFA is %rsp + N from here on .cfi_def_cfa_register R the CFA is the VALUE IN REGISTER R, not %rsp + N -- used once a frame pointer exists, and it is how a function with a frame pointer describes itself without a table at all .cfi_offset R, D register R is saved at CFA + D, and must be restored to unwind past .cfi_restore R and it is back in its original place

Underneath the directives is a byte language with its own opcodes, and the numbers are worth having because they are the first thing you meet when you read an .eh_frame section by hand. The high two bits of a byte select its class: 0x40 is advance the location, 0x80 is register rule, 0xc0 is remember and restore state, and 0x00 is expression and extension. Inside the first class, the low six bits are the primary opcodes — 0x01 set location, 0x02/0x03/0x04 advance by 1, 2 or 4 bytes, 0x0c define the CFA, 0x0d define the CFA register, 0x0e define the CFA offset. So a single byte 0x0e is “the CFA is %rsp plus the following ULEB128” and 0x4c is “advance the program counter by 12”. A whole function's unwind description is a few hundred of those bytes, and a full binary's is a few hundred thousand.

The reality: what a profiler does when the description is absent

The question is not whether the CFI is well-formed. It is what happens to a program compiled without it, and the answer is measurable with a real unwinder rather than a simulation of one.

The instrument is backtrace() from glibc's execinfo — not a stand-in for a profiler but the code gdb, perf and every crash reporter on this machine use. It is run from three nested noinline functions in a program built twice: once normally, and once with -fno-asynchronous-unwind-tables.

$ ./abidump | sed -n '/WHAT A PROFILER CAN AND CANNOT SEE/,/^  ONE FRAME/p'
  DIRECTIVE | cfi_startproc | 33
  DIRECTIVE | cfi_endproc | 33
  DIRECTIVE | cfi_def_cfa_offset | 71
  DIRECTIVE | cfi_def_cfa_register | 0
  DIRECTIVE | cfi_offset | 5
  DIRECTIVE | total | 142
  FDE | with | 33
  EHSIZE | with | 358
  FDE | without | 0
  EHSIZE | without |

  THE INSTRUMENT IS A REAL UNWINDER.  backtrace() from glibc's
  execinfo, which is what gdb, perf and every crash reporter on
  this machine use, run from three nested noinline functions, in a
  program built TWICE: once normally and once with
  -fno-asynchronous-unwind-tables.

    uwprobe, unwind tables present:      FRAMES 7, stack depth 9
    uwprobe, unwind tables REMOVED:     FRAMES 1, stack depth 3
  

Seven frames, or one. The call chain is identical in both builds: the same three nested noinline functions, the same backtrace(), the same machine. The only difference is a compiler flag, and the flag is worth 6 frames out of 7.

And the shape of the failure is the part that matters. The unwinder did not return a wrong answer. It returned the only answer it could: the frame it was called from. One frame. There is no diagnostic, no error code, and no indication in the return value that anything is missing — a caller that does not know the flag was set sees a one-frame backtrace and a plausible-looking program name at the bottom of it.

33 FDEs with the flag, 0 without. And 71 of the directives in that corpus are the single instruction `.cfi_def_cfa_offset`, which is the cheapest possible complete answer: "the CFA is %rsp plus this number". .eh_frame is 358 bytes for 33 functions with no frame pointer, and 428 bytes for the SAME 33 when they keep one. So the price of being walkable is about ELEVEN BYTES a function, and a frame pointer adds about two of them. The first draft of this course put that second number at FORTY. It was never measured, and it is wrong by a factor of about three.

And here is a number that was wrong, and is wrong in the artifact rather than only here. The draft claimed a frame description costs about eleven bytes without a frame pointer and about forty with one. The first half was measured. The second was an estimate written into a page as though it were a measurement, and compiling the same 33 functions three ways says the second half is thirteen bytes — a frame pointer costs about two bytes of table, not thirty. The three builds are the interesting part, and one of them is a lesson about flags: -O2 and -O2 -fomit-frame-pointer produce byte-identical.eh_frame sections, because gcc omits frame pointers at -O2 already, so the flag confirms a default rather than changing it. Only -fno-omit-frame-pointer moves the number. A reader who assumed a flag always changed something would have measured nothing and reported a difference anyway.

The asymmetry worth naming is between the two ways of describing a frame. A frame pointer describes itself in the frame — one register, restored on the way out, costing a push and a pop and making the function slower whether or not anybody ever unwinds it. A CFI table describes itself beside the frame, in a section, costing bytes in the file and nothing at run time. gcc emits the table by default and the frame pointer only when asked, and that default is a considered choice rather than an accident: -O2 omits frame pointers and still produces fully walkable binaries, whereas the reverse is not achievable.

Worked: two descriptions, and the check nobody does

Take the two views of f7 from earlier in this course and put them side by side. The first is the audit's, read from the callee's instructions; the second is the compiler's, read from its own annotations.

  WHAT THE INSTRUCTIONS SAY            WHAT THE CFI SAYS
  ------------------------------------  ------------------------------------
  subq $8, %rsp                        .cfi_def_cfa_offset 16
  movq 16(%rsp), %r10   <- arg 7       the CFA is rsp+16, so
                                           16(%rsp) is CFA
  call abi_sink
  addq $8, %rsp                        .cfi_def_cfa_offset 8
  ret                                  and the CFA is back to rsp+8
  

Both say the same thing about where argument seven is, and they say it without reference to each other. That is the interesting property and it is not an accident: the two descriptions were generated from the same compiler's model of the function, so they cannot disagree, and a compiler that emitted a CFI contradicting its own prologue would break every unwinder on the machine. So the CFI is trustworthy in a way that is unusual for compiler output, and it is worth knowing why rather than merely that it is.

What the pair does not give you is a way to check either one against the architecture. The prologue is checkable — the last concept checks the calling convention by re-deriving it from the bytes, and it is the only part of the ABI where that is possible. The unwind table is not checkable that way, because there is no independent account of what a function's frame should be: it is whatever the compiler decided, and the only oracle is a program that successfully unwinds through it.

Which brings the measurement back round to where it started. The reason the two builds differ by six frames is not that the second build's frames are differently described. They are not described at all. The unwind information is not a second opinion on a frame the first description got wrong; it is the only description there is, for anything that was not there at the time. Strip it and you have not made the description worse, you have removed it, and a consumer that needed it does not get a degraded answer — it gets the truth about how much it does not know.

Apply it

  1. Make a profiler blind and look at what it prints. Build any program with -fno-asynchronous-unwind-tables and run gdb on it, or backtrace() from a function three frames deep. (Expect one frame, and expect nothing in the output to say that anything is wrong. Then readelf --debug-dump=frames the binary and confirm the section is absent rather than empty — the difference matters, because an empty table says “nothing changes here” and an absent one says “this object has no opinion”.)
  2. Count the bytes. Compare the size of a function's .eh_frame contribution with and without a frame pointer. (Expect almost nothing: about two bytes a function, in this course's own corpus. And expect the first thing you try to teach you nothing at all — -fomit-frame-pointer at -O2 is byte-identical to the default, because gcc already omits frame pointers there, so the flag measures the default rather than changing it. Only -fno-omit-frame-pointer moves the number. Then try -fno-asynchronous-unwind-tables -fno-omit-frame-pointer together and confirm that the result is a binary that runs and cannot be profiled, which is the shape of a bad default: a frame pointer walks a frame by arithmetic and needs no table, and the table is gone.)
  3. Find the CFA in a function of your own. Pick any function gcc emits with .cfi_def_cfa_offset and account for the number: count the pushes, the frame-pointer setup and the subs between the function's entry and that point, and check that the annotation equals 8 plus their sum. (Expect it to work the first time, and expect the second function you pick to use .cfi_def_cfa_register instead because it has a frame pointer. The two forms are the two ways of answering the same question, and a function that has both uses the register form and the offset form for different callee-saved registers.)
  4. Read six bytes of .eh_frame by hand.readelf --debug-dump=frames a small binary and find one FDE's instructions. (Expect to find 0x0c (define the CFA register), 0x0e followed by a ULEB128 (define the CFA offset), 0x07 and 0x08 (undefined and same-value rules for the volatile registers) and a run of 0x00 nops padding the rest. Then compare that against the .cfi_* directives gcc emitted for the same function and account for every byte, and note how little of the 358 bytes is not padding.)
  5. Check whether your own project describes its frames. Look for .eh_frame in every binary you ship, and remember the two ways it disappears: a compiler flag, and -static-libgcc with a toolchain that has the tables in a separate object. (Expect a partial description to be worse than none in one specific way: a frame that is described for the first ten instructions and not for the rest will unwind correctly until the eleventh, and the failure will be at whatever was called from there. The sec course's canary concept is the neighbouring version of this problem, where the description that goes missing is a protection rather than a table.)

Connect

Backwards, the stack frame is the subject being described a second time, and the %rbp paragraph at the end of its reality section is the direct link: a frame pointer exists so a frame can be walked by arithmetic, and this concept is what arithmetic is a fallback for. The calling convention supplied the two facts the table confirms, stack=0x10 and the 176-byte save area, and this concept is the point at which they stop being the compiler's private business.

Forwards, the last concept is the one that puts a number on all of it. The audit in the final concept re-derives the calling convention from bytes and checks it against a specification, and the contrast with this concept is the point: that check is possible for the call and impossible for the frame, because the call has an independent oracle and the frame does not. Understanding why one part of an ABI is auditable and another part is not is worth more than either result on its own.

Outward, two neighbours that own the edges. The dynamic-linking course is about how the stack is set up before any of this course's rules have a chance to apply — the kernel hands over a %rsp whose alignment the ABI's rules do not describe, and the two functions that establish the invariant are the first thing that has to fix it. And The linking course's orphans concept is about what happens to a section nobody references: .eh_frame is the section a link command is most likely to drop, precisely because nothing in the program refers to it.

render_lesson_js(&mut page)