Expand description
This module implements support for breakpad’s text-based STACK CFI and STACK WIN unwinding instructions. This isn’t something you need to actually use directly, it’s just public so these docs will get a nice pretty rendering.
The rest of this documentation is discussion of STACK CFI and STACK WIN format – both how to parse and evaluate them.
Each STACK line provides instructions on how to unwind the program at a given instruction address. Specifically this means how to restore registers, which most importantly include the instruction pointer ($rip/$eip/pc) and stack pointer ($rsp/$esp/sp).
STACK WIN lines are completely self-contained while STACK CFI lines may depend on the lines above them.
Note that all addresses are relative to the start of the module – resolving the module and applying that offset is left as an exercise to the reader.
See also the upstream breakpad docs which are ok but can be a bit hazy around the details (I think they’ve just partially bitrotted). To the best of my ability I have tried to make these docs as accurate and detailed as possible.
I also try to be honest about the places where I’m uncertain about the semantics.
§Known Differences Between This Implementation and Breakpad
I haven’t thoroughly tested the two implementations for compatibility, but where I have noticed a difference I’ll put it here so it’s documented somewhere.
§Register Names
Breakpad assumes register names are prefixed with $ EXCEPT
on ARM variants. These prefixes are hardcoded, so if you hand it
$rax or x11 it will be happy, but if you hand it rax or $x11
it will freak out and be unable to parse the CFI expressions.
This implementation doesn’t have any notion of “valid” registers
for a particular execution, and so just unconditionally strips leading
$’s. So $rax, $x11, rax, and x11 should all be valid.
Registers names are otherwise only “validated” by the FrameWalker,
in that it will return an error if we try to get or set a register name
it doesn’t recognize (or doesn’t have a valid value for). But it
doesn’t ever expect $’s, so that detail has been erased by
the time it’s involved.
The author of this document may or may not know this as a result of
accidentally causing mozilla/dump_syms to emit $x11 in some situations.
If that is the case, they fixed it, so everything’s fine, right?
It’s bad to be a permissive parser, but symbol files are already an inconsistent mess, so you kind of have to be permissive in random places? And we don’t have a conformance test suite to keep everything perfectly bug-compatible with breakpad when it doesn’t document everything enough to know what’s “intended”.
§cfi_scan hacks
This is technically a technique that the user of walker.rs would implement, but it’s worth discussing here since it relates to cfi evaluation.
When evaluating STACK WIN expressions, breakpad will apply several heuristics to adjust values. This includes scanning the stack to try to “refine” the inputs and outputs.
At the moment, we implement very few of these heuristics. We definitely don’t do any scanning when evaluating STACK WIN.
The ones we do implement (and that I can recall) are:
-
changing the value of searchStart based on whether the program includes an
@. -
trying to forward the value of
$ebxin more situations than the STACK WIN suggests you should.
At this point I don’t recall if these were implemented to fix actual issues found during development, or if I just cargo-culted them because they seemed relatively inoffensive.
§STACK CFI
STACK CFI lines comes in two forms:
STACK CFI INIT instruction_address num_bytes registers
STACK CFI instruction_address registers
A STACK CFI INIT line specifies how to restore registers for the given
range of addresses.
Example: STACK CFI INIT 804c4b0 40 .cfa: $esp 4 + $eip: .cfa 4 - ^
Arguments:
- instruction_address (hex u64) is the first address in the module this line applies to
- num_bytes (hex u64) is the number of bytes it (and its child STACK CFI lines) covers
- registers (string) is the register restoring instructions (see the next section)
A STACK CFI line always follows a “parent” STACK CFI INIT line. It
updates the instructions on how to restore registers for anything within
the parent STACK CFI INIT’s range after the given address (inclusive).
It only specifies rules for registers that have new instructions.
To get the final rules for a given address, start with its STACK CFI INIT
and then apply all the applicable STACK CFI “diffs” in order.
Example: STACK CFI 804c4b1 .cfa: $esp 8 + $ebp: .cfa 8 - ^
Arguments:
- instruction_address (hex u64) is the first address to apply these instructions
- registers (string) is the new register restoring instructions (see the next section)
§STACK CFI registers
A line’s STACK CFI registers are of the form
REG: EXPR REG: EXPR REG: EXPR...
Where REG is .cfa, .ra, $<alphanumeric>, or <alphanumeric>
(but not a valid integer literal).
And EXPR is <anything but ":"> (see next section for details)
Each REG: EXPR pair specifies how to compute the register REG for the
caller. There are three kinds of registers:
-
$XXXorXXXrefers to an actual general-purpose register. In REG position it refers to the caller, in an EXPR it refers to the callee. Register names can in theory be any alphanumeric string that isn’t a valid integer literal. e.g.$rax,x11.$prefixes are expected for all platforms except ARM variants. This parser is more permissive and allows for either form on all platforms. Completely invalid register names (x99) will be caught at evaluation time. -
.cfais the “canonical frame address” (CFA), as used in DWARF CFI. It abstractly represents the base address of the frame. On x86, x64, and ARM64 the CFA is the caller’s stack pointer from before the call. As such on those platforms you will never see instructions to restore the frame pointer – it must be implicitly restored from the cfa..cfaalways refers to the caller, and therefore must be computed without use of itself. -
.rais the “return address”, which just abstractly refers to the instruction pointer/program counter. It only ever appears in REG position.
.cfa and .ra must always have defined rules, or the STACK CFI is malformed.
The CFA is special because its computed value can be used by every other EXPR. As such it should always be computed first so that its value is available. The purpose of the CFA is to cleanly handle the very common case of registers saved to the stack. Every register saved this way lives at a fixed offset from the start of the frame. So we can specify their rules once, and just update the CFA.
For example:
STACK CFI INIT 0x10 16 .cfa: $rsp 8 + .ra: .cfa -8 + ^
STACK CFI 0x11 .cfa: $rsp 16 + $rax: .cfa -16 + ^
STACK CFI 0x12 .cfa: $rsp 24 +Can be understood as (pseudo-rust):
let mut cfa = 0;
let mut ra = None;
let mut caller_rax = None;
// STACK CFI INIT 0x10's original state
cfa = callee_rsp + 8;
ra = Some(|| { *(cfa - 8) }); // Defer evaluation
// STACK CFI 0x11's diff
if address >= 0x11 {
cfa = callee_rsp + 16;
caller_rax = Some(|| { *(cfa - 16) }); // Defer evaluation
}
// STACK CFI 0x12's diff
if address >= 0x12 {
cfa = callee_rsp + 24;
}
caller.stack_pointer = cfa;
// Finally evaluate all other registers using the current cfa
caller.instruction_pointer = ra.unwrap()();
caller.rax = caller_rax.map(|func| func());§STACK CFI expressions
STACK CFI expressions are in postfix (Reverse Polish) notation with tokens separated by whitespace. e.g.
.cfa $rsp 3 + * ^Is the postfix form of
^(.cfa * ($rsp + 3))The benefit of postfix notation is that it can be evaluated while processing the input left-to-right without needing to maintain any kind of parse tree.
The only state a postfix evaluator needs to maintain is a stack of computed values. When a value (see below) is encountered, it is pushed onto the stack. When an operator (see below) is encountered, it can be evaluated immediately by popping its inputs off the stack and pushing its output onto the stack.
If the postfix expression is valid, then at the end of the token stream the stack should contain a single value, which is the result.
For binary operators the right-hand-side (rhs) will be the first value popped from the stack.
Supported operations are:
+: Binary Add-: Binary Subtract*: Binary Multiply/: Binary Divide%: Binary Remainder@: Binary Align (truncate lhs to be a multiple of rhs)^: Unary Dereference (load from stack memory)
Supported values are:
.cfa: read the CFA.undef: terminate execution, the output is explicitly unknown<a signed decimal integer>: read this integer constant (limited to i64 precision)$<alphanumeric>: read a general purpose register from the callee’s frame<alphanumeric>: same as above (can’t be an integer literal)
Whether registers should be $reg or reg depends on the platform.
This parser is permissive, and just accepts both on all platforms.
But I believe $ is “supposed” to be used on every platform except for
ARM variants.
§STACK WIN
STACK WIN lines try to encode the more complex unwinding rules produced by x86 Windows toolchains. On any other target (x64 windows, x86 linux, etc), only STACK CFI should be used. This is a good thing, because STACK WIN is a bit of a hacky mess, as you’ll see.
STACK WIN type instruction_address num_bytes prologue_size epilogue_size parameter_size
saved_register_size local_size max_stack_size has_program_string
program_string_OR_allocates_base_pointerExamples:
STACK WIN 4 a1080 fa 9 0 c 0 0 0 1 $T0 .raSearch = $eip $T0 ^ = $esp $T0 4 + =`
STACK WIN 0 1cab960 68 0 0 10 0 8 0 0 0Arguments:
- type is either 4 (“framedata”) or 0 (“fpo”), see their sections below
- instruction_address (hex u64) is the first address in the module this line applies to
- num_bytes (hex u64) is the number of bytes it covers
- has_program_string (0 or 1) indicates the meaning of the next argument (implied by type?)
- program_string_OR_allocates_base_pointer is one of:
- program_string (string) is the expression to evaluate for “framedata” (see that section)
- allocates_base_pointer (0 or 1) whether ebp is pushed for “fpo” (see that section)
The rest of the arguments are just values you may need to use in the STACK WIN evaluation algorithms:
- prologue_size
- epilogue_size
- parameter_size
- saved_register_size
- local_size
- max_stack_size
Two useful values derived from these values are:
grand_callee_parameter_size = callee.parameter_size
frame_size = local_size + saved_register_size + grand_callee_parameter_sizeHaving frame_size allows you to find the offset from $esp to the return address (and other saved registers). This requires grand_callee_parameter_size because certain windows calling conventions makes the caller responsible for destroying the callee’s arguments, which means they are part of the caller’s frame, and therefore change the offset to the return address. (During unwinding we generally refer to the current frame as the “callee” and the next frame as the “caller”, but here we’re concerned with callee’s callee, hence grand_callee.)
Note that grand_callee_paramter_size is using the STACK WIN entry of the previous frame. Although breakpad symbol files have FUNC entries which claim to provide parameter_size as well, those values are not to be trusted (or at least, the grand-callee’s STACK WIN entry is to be preferred). The two values are frequently different, and the STACK WIN ones are more accurate.
If there is no grand_callee (i.e. you are unwinding the first frame of the stack), grand_callee_parameter_size can be defaulted to 0.
§STACK WIN frame pointer mode (“fpo”)
This is an older mode that just gives you minimal information to unwind:
the size of the stack frame (frame_size). All you can do is find the
return address, update $esp, and optionally restore $ebp (if allocates_base_pointer).
This is best described by pseudocode:
$eip := *($esp + frame_size)
if allocates_base_pointer:
// $ebp was being used as a general purpose register, old value saved here
$ebp := *($esp + grand_callee_parameter_size + saved_register_size - 8)
else:
// Assume both ebp and ebx are preserved (if they were previously valid)
$ebp := $ebp
$ebx := $ebx
$esp := $esp + frame_size + 4I don’t have an interesting explanation for why that position is specifically where $ebp is saved, it just is. The algorithm tries to forward $ebx when $ebp wasn’t messed with as a bit of a hacky way to encourage certain Windows system functions to unwind better. Evidently some of them have framedata expressions that depend on $ebx, so preserving it whenever it’s plausible is desirable?
§STACK WIN expression mode (“framedata”)
This is the general purpose mode that has you execute a tiny language to compute arbitrary registers.
STACK WIN expressions use many of the same concepts as STACK CFI, but rather
than using REG: EXPR pairs to specify outputs, it maintains a map of variables
whose values can be read and written by each expression.
I personally find this easiest to understand as an extension to the STACK CFI expressions, so I’ll describe it in those terms:
The supported operations add one binary operation:
=: Binary Assign (assign the rhs’s integer to the lhs’s variable)
This operation requires us to have a distinction between integers and variables, which the postfix evaluator’s stack must hold.
All other operators operate only on integers. If a variable is passed where an integer is expected, that means the current value of the variable should be used.
“values” then become:
.<alphanumeric>: a variable containing some initial constants (see below)$<alphanumeric>: a variable representing a general purpose register or temporary<alphanumeric>: same as above, but can’t be an integer literal.undef: delete the variable if this is assigned to it (like Option::None)<a signed decimal integer>: read this integer constant (limited to i64 precision)
Before evaluating a STACK WIN expression:
-
The variables
$ebpand$espshould be initialized from the callee’s values for those registers (error out if those are unknown).$ebxshould similarly be initialized if it’s available, since some things use it, but it’s optional. -
The following constant variables should be set accordingly:
.cbParams = parameter_size.cbCalleeParams = grand_callee_parameter_size(only for breakpad-generated exprs?).cbSavedRegs = saved_register_size.cbLocals = local_size.raSearch = $esp + frame_size.raSearchStart = .raSearch(synonym that sometimes shows up?)
Note that .raSearch(Start) roughly corresponds to STACK CFI’s .cfa, in that
it generally points to where the return address is. However breakpad seems to
believe there are many circumstances where this value can be slightly wrong
(due to the frame pointer having mysterious extra alignment?). As such,
breakpad has several messy heuristics to “refine” .raSearchStart, such as
scanning the stack. This implementation does not (yet?) implement those
heuristics. As of this writing I have not encountered an instance of this
problem in the wild (but I haven’t done much testing!).
After evaluating a STACK WIN expression:
The caller’s registers are stored in $eip, $esp, $ebp, $ebx, $esi,
and $edi. If those variables are undefined, then their values in the caller
are unknown. Do not implicitly forward registers that weren’t explicitly set.
(Should it be an error if the stack isn’t empty at the end? It’s arguably malformed input but also it doesn’t matter since the output is in the variables? shrug)
§Example STACK WIN framedata evaluation
Here is an example of framedata for a function with the standard prologue. Given the input:
$T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + =and initial state:
ebp: 16, esp: 1600Then evaluation proceeds as follows:
Token | Stack | Vars
---------+--------------+----------------------------------------------------
| | $ebp: 16, $esp: 1600,
$T0 | $T0 | $ebp: 16, $esp: 1600,
$ebp | $T0 $ebp | $ebp: 16, $esp: 1600,
= | | $ebp: 16, $esp: 1600, $T0: 16,
$eip | $eip | $ebp: 16, $esp: 1600, $T0: 16,
$T0 | $eip $T0 | $ebp: 16, $esp: 1600, $T0: 16,
4 | $eip $T0 4 | $ebp: 16, $esp: 1600, $T0: 16,
+ | $eip 20 | $ebp: 16, $esp: 1600, $T0: 16,
^ | $eip (*20) | $ebp: 16, $esp: 1600, $T0: 16,
= | | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
$ebp | $ebp | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
$T0 | $ebp $T0 | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
^ | $ebp (*16) | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
= | | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
$esp | $esp | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
$T0 | $esp $T0 | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
8 | $esp $T0 8 | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
+ | $esp 24 | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
= | | $ebp: (*16), $esp: 24, $T0: 16, $eip: (*20)Giving a final output of ebp=(*16), esp=24, eip=(*20).