Stack unwinding

Stack unwinding主要有以下作用:

  • 获取stack trace,用于debugger、crash reporter、profiler等
  • 加上personality routine和language specific data area后实现C++ exceptions(Itanium C++ ABI)

Stack unwinding可以分成两类:

  • synchronous: 程序自身触发的,C++ throw、获取自身stack trace等。这类stack unwinding只发生在函数调用处(在function body内,不会出现在prologue/epilogue)
  • asynchronous: 由signal或外部程序触发,这类stack unwinding可以发生在prologue/epilogue

Frame pointer

最经典、最简单的stack unwinding基于frame pointer:固定一个寄存器为frame pointer(在x86-64上为RBP),函数prologue处把frame pointer放入栈帧,并更新frame pointer为保存的frame pointer的地址。
frame pointer值形成了一个单链表。获取初始frame pointer值(__builtin_frame_address)后,不停解引用frame pointer即可得到所有栈帧的frame pointer值。
这种方法不适用于prologue/epilogue的部分指令。

1
2
3
4
5
pushq %rbp
movq %rsp, %rbp # after this, RBP references the current frame
...
popq %rbp
retq # RBP references the previous frame

下面是个简单的stack unwinding例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
[[gnu::noinline]] void qux() {
void **fp = __builtin_frame_address(0);
for (;;) {
printf("%p\n", fp);
void **next_fp = *fp;
if (next_fp <= fp) break;
fp = next_fp;
}
}
[[gnu::noinline]] void bar() { qux(); }
[[gnu::noinline]] void foo() { bar(); }
int main() { foo(); }

基于frame pointer的方法简单,但是有若干缺陷。

上面的代码用-O1或以上编译时foo和bar会tail call,程序输出不会包含foo bar的栈帧(-fomit-leaf-frame-pointer并不阻碍tail call)。

实践中,有时候不能保证所有库都包含frame pointer。unwind一个线程时,为了增强健壮性需要检测一个next_fp是否像栈地址。检测的一种方法是解析/proc/*/maps判断地址是否可读(慢),另一种是

1
2
3
4
// Or use the write end of a pipe.
int fd = open("/dev/random", O_WRONLY);
if (write(fd, address, 1) < 0)
// not readable

另外,预留一个寄存器用于frame pointer会有性能开销(prologue、epilogue额外的指令开销和少一个寄存器带来的寄存器压力),在寄存器贫乏的x86-32可能相当显著,在寄存器较为充足的x86-64可能也有1%以上的性能损失。

  • -O0: 预设-fno-omit-frame-pointer,所有函数都有frame pointer
  • -O1或以上: 预设-fomit-frame-pointer,只有必要情况才设置frame pointer。指定-fno-omit-leaf-frame-pointer则可得到类似-O0效果。可以额外指定-momti-leaf-frame-pointer去除leaf functions的frame pointer

libunwind

C++ exception、profiler/crash reporter的stack unwinding通常用libunwind API和DWARF Call Frame Information。上个世纪90年代Hewlett-Packard定义了一套libunwind API,分为两类:

  • unw_*: 入口是unw_init_local(local unwinding,当前进程)和unw_init_remote(remote unwinding,其他进程)。通常使用libunwind的应用使用这套API。比如Linux perf会调用unw_init_remote
  • _Unwind_*: 这部分标准化为Itanium C++ ABI: Exception Handling的Level 1: Base ABI。Level 2 C++ ABI调用这些_Unwind_* API。其中的_Unwind_Resume是唯一被C++编译后的代码直接调用的API,其中的_Unwind_Backtrace被少数应用用于获取backtrace,其他函数则会被libsupc++/libc++abi调用。

Hewlett-Packard开源了https://www.nongnu.org/libunwind/(除此之外还有很多叫做”libunwind”的项目)。这套API在Linux上的常见实现是:

  • libgcc/unwind-* (libgcc_s.so.1libgcc_eh.a): 实现了_Unwind_*并引入了一些扩展:_Unwind_Resume_or_Rethrow, _Unwind_FindEnclosingFunction, __register_frame
  • llvm-project/libunwind (libunwind.solibunwind.a)是HP API的一个简化实现,提供了部分unw_*,但没有实现unw_init_remote。部分代码取自ld64。使用Clang的话可以用--rtlib=compiler-rt --unwindlib=libunwind选择
  • glibc的_Unwind_Find_FDE内部实现,通常不导出,和__register_frame_info有关

DWARF Call Frame Information

程序不同区域需要的unwind指令由DWARF Call Frame Information (CFI)描述,在ELF平台上由.eh_frame存储。Compiler/assembler/linker/libunwind提供相应支持。

.eh_frame由Common Information Entry (CIE)和Frame Description Entry (FDE)组成。CIE有这些字段:

  • length
  • CIE_id: 常数0。该字段用于区分CIE和FDE,在FDE中该字段为非0 CIE_pointer
  • version: 常数1
  • augmentation_string: 描述CIE/FDE参数列表的字串。P字符表示personality routine指针;L字符表示FDE的augmentation data存储了language-specific data area (LSDA)
  • address_size: 一般为4或8
  • segment_selector_size: for x86
  • code_alignment_factor: 假设指令长度都是2或4的倍数(用于RISC),影响DW_CFA_advance_loc等的参数的乘数
  • data_alignment_factor: 影响DW_CFA_offset DW_CFA_val_offset等的参数的乘数
  • return_address_register
  • augmentation_data_length
  • augmentation_data: personality
  • initial_instructions
  • padding

每个FDE有一个关联的CIE。FDE有这些字段:

  • length: FDE自身长度。若为0xffffffff,接下来8字节(extended_length)记录实际长度。除非特别构造,extended_length是用不到的
  • CIE_pointer: 从当前位置减去CIE_pointer得到关联的CIE
  • initial_location: 该FDE描述的第一个位置的地址。在.o中此处有一个引用section symbol的relocation
  • address_range: initial_location和address_range描述了一个地址区间
  • instructions: unwind时的指令
  • augmentation_data_length
  • augmentation_data: 如果关联的CIE augmentation包含L字符,这里会记录language-specific data area
  • padding

CIE引用text section中的personality。FDE引用.gcc_except_table中的LSDA。personality和lsda用于Itanium C++ ABI的Level 2: C++ ABI。

.eh_frame基于DWARF v2引入的.debug_frame。它们有一些区别:

  • .eh_frame带有SHF_ALLOC flag(标志一个section是否应为内存中镜像的一部分)而.debug_frame没有,因此后者的使用场景非常少。
  • debug_frame支持DWARF64格式(支持64-bit offsets但体积会稍大)而.eh_frame不支持(其实可以拓展,但是缺乏需求)
  • .debug_frame的CIE中没有augmentation_data_length和augmentation_data
  • CIE中version的值不同
  • FDE中CIE_pointer的含义不同。.debug_frame中表示一个section offset(absolute)而.eh_frame中表示一个relative offset。.eh_frame作出的这一改变很好。如果.eh_frame长度超过32-bit,.debug_frame得转换成DWARF64才能表示CIE_pointer,而relative offset则无需担心这一问题(如果FDE到CIE的距离超过32-bit了,追加一个CIE即可)

对于如下的函数:

1
2
3
void f() {
__builtin_unwind_init();
}

编译器用.cfi_*(CFI directive)标注汇编,.cfi_startproc.cfi_endproc标识FDE区域,其他CFI directives描述CFI instructions。
一个call frame用栈上的一个地址表示。这个地址叫做Canonical Frame Address (CFA),通常是call site的stack pointer值。下面用一个例子描述CFI instructions的作用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
f:
# At the function entry, CFA = rsp+8
.cfi_startproc
# %bb.0:
pushq %rbp
# Redefine CFA = rsp+16
.cfi_def_cfa_offset 16
# rbp is saved at the address CFA-16
.cfi_offset %rbp, -16
movq %rsp, %rbp
# CFA = rbp+16. CFA does not needed to be redefined when rsp changes
.cfi_def_cfa_register %rbp
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rbx
# rbx is saved at the address CFA-56
.cfi_offset %rbx, -56
.cfi_offset %r12, -48
.cfi_offset %r13, -40
.cfi_offset %r14, -32
.cfi_offset %r15, -24
popq %rbx
popq %r12
popq %r13
popq %r14
popq %r15
popq %rbp
# CFA = rsp+8
.cfi_def_cfa %rsp, 8
retq
.Lfunc_end0:
.size f, .Lfunc_end0-f
.cfi_endproc

汇编器根据CFI directives生成.eh_frame(这套机制由Alan Modra在2003年引入)。Linker收集.o中的.eh_frame input sections生成output .eh_frame
2006年GNU as引入了.cfi_personality.cfi_lsda

.eh_frame_hdrPT_EH_FRAME

定位一个pc所在的FDE需要从头扫描.eh_frame,找到合适的FDE(pc是否落在initial_location和address_range表示的区间),所花时间和扫描的CIE和FDE记录数相关。
https://sourceware.org/pipermail/binutils/2001-December/015674.html引入了.eh_frame_hdr,包含binary search index table描述(initial_location, FDE address) pairs。

ld --eh-frame-hdr可以生成.eh_frame_hdr。Linker会另外创建program header PT_EH_FRAME来包含.eh_frame_hdr
Unwinder会寻找PT_EH_FRAME来定位.eh_frame_hdr,见下文的例子。

__register_frame_info

.eh_frame_hdrPT_EH_FRAME发明之前,crtbegin (crtstuff.c)中有一个static constructor frame_dummy:调用__register_frame_info注册可执行文件的.eh_frame

现在__register_frame_info只有-static链接的程序才会用到。相应地,如果链接时指定-Wl,--no-eh-frame-hdr,就无法unwind(如果使用C++ exception则会导致std::terminate)。

libunwind例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <libunwind.h>
#include <stdio.h>

void backtrace() {
unw_context_t context;
unw_cursor_t cursor;
// Store register values into context.
unw_getcontext(&context);
// Locate the PT_GNU_EH_FRAME which contains PC.
unw_init_local(&cursor, &context);
size_t rip, rsp;
do {
unw_get_reg(&cursor, UNW_X86_64_RIP, &rip);
unw_get_reg(&cursor, UNW_X86_64_RSP, &rsp);
printf("rip: %zx rsp: %zx\n", rip, rsp);
} while (unw_step(&cursor) > 0);
}

void bar() {backtrace();}
void foo() {bar();}
int main() {foo();}

如果使用llvm-project/libunwind:

1
$CC a.c -Ipath/to/include -Lpath/to/lib -lunwind

如果使用nongnu.org/libunwind,两种选择:(a) #include <libunwind.h>前添加#define UNW_LOCAL_ONLY (b) 多链接一个库,x86-64上是-l:libunwind-x86_64.so
使用Clang的话也可用clang --rtlib=compiler-rt --unwindlib=libunwind -I path/to/include a.c,除了提供unw_*外,能确保不链接libgcc_s.so

  • unw_getcontext: 获取寄存器值(包含PC)
  • unw_init_local
    • 使用dl_iterate_phdr遍历可执行文件和shared objects,找到包含PC的PT_LOAD program header
    • 找到所在module的PT_EH_FRAME(.eh_frame_hdr),存入cursor
  • unw_step
    • 二分搜索PC对应的.eh_frame_hdr项,记录找到的FDE和其指向的CIE
    • 执行CIE中的initial_instructions
    • 执行FDE中的instructions。维护一个location、CFA,初始指向FDE的initial_location,指令中DW_CFA_advance_loc增加location;DW_CFA_def_cfa_*更新CFA;DW_CFA_offset表示一个寄存器的值保存在CFA+offset处
    • location大于等于PC时停止。也就是说,执行的指令是FDE instructions的一个前缀

Unwinder根据program counter找到适用的FDE,执行所有在program counter之前的CFI instructions。

有几种重要的

  • DW_CFA_def_cfa_*
  • DW_CFA_offset
  • DW_CFA_advance_loc

一个-DCMAKE_BUILD_TYPE=Release -DLLVM_TARGETS_TO_BUILD=X86的clang,.text 51.7MiB、.eh_frame 4.2MiB、.eh_frame_hdr 646、2个CIE、82745个FDE。

注记

CFI instructions适合编译器生成代码,而手写汇编要准确标准每一条指令是繁琐的,也很容易出错。
2015年Alex Dowad也musl libc贡献了awk脚本,解析assembly并自动标注CFI directives。
其实对于编译器生成的代码也不容易,对于一个不用frame pointer的函数,调整SP就得同时输出一条CFI directive重定义CFA。GCC是不解析inline assembly的,因此inline assembly里调整SP往往会造成不准确的CFI。

1
2
3
4
5
6
7
8
9
10
void foo() {
asm("subq $128, %rsp\n"
// Cannot unwind if -fomit-leaf-frame-pointer
"nop\n"
"addq $128, %rsp\n");
}

int main() {
foo();
}

而LLVM里的CFIInstrInserter可以插入.cfi_def_cfa_* .cfi_offset .cfi_restore调整CFA和callee-saved寄存器。

SHT_X86_64_UNWIND

.eh_frame在linker/dynamic loader里有特殊处理,照理应该用一个单独的section type,但当初设计时却用了SHT_PROGBITS
在x86-64 psABI中.eh_frame的型别为SHT_X86_64_UNWIND(可能是受到Solaris影响)。

  • GNU as中,.section .eh_frame,"a",@unwind会生成SHT_X86_64_UNWIND,而.cfi_*则生成SHT_PROGBITS
  • Clang 3.8起,.cfi_*生成SHT_X86_64_UNWIND

.section .eh_frame,"a",@unwind很少见(glibc’s x86 port,libffi,LuaJIT等少数包),因此检查.eh_frame的型别是个辨别Clang/GCC object file的好方法:)
我有一个LLD 11.0.0 commit就是在relocatable link时接受两种型别的.eh_frame;-)

建议:未来的架构在定义processor-specific section types时,请不要把0x70000001 (SHT_ARM_EXIDX=SHT_IA_64_UNWIND=SHT_PARISC_UNWIND=SHT_X86_64_UNWIND=SHT_LOPROC+1)用于unwinding以外的用途:)
SHT_CSKY_ATTRIBUTES=0x70000001:)

Linker角度的问题

.eh_frame是一个monolithic section。通常在COMDAT group和启用-ffunction-sections的情况下,.data/.rodata需要像.text那样分裂开,但是.eh_frame的实现没有。
Linker在处理.eh_frame时,需要在概念上分裂.eh_frame成CIE/FDE。
--gc-sections时,概念上的引用关系和实际的relocation是相反的:FDE含有指向text section的引用;GC时,若被指向的text section被丢弃,引用它的FDE也可以被丢弃。

LLD处理.eh_frame时有些特殊判断:

  • -M需要特别判断.eh_frame
  • --gc-sections发生在.eh_frame deduplication/GC前。CIE中的personality是有效的reference,FDE中的initial_location应该忽略,FDE中的lsda引用只考虑non-section-group情形
  • Relocatable link,需要允许.eh_frame指向discarded section (due to section group)的STT_SECTION symbol的relocation

Compact unwind descriptors

在macOS上,Apple设计了compact unwind descriptors机制加速unwinding,理论上这种技术可以用于节省一些__eh_frame空间,但并没有实现。
主要思想是:

  • 大多数函数的FDE都有固定的模式(prologue处指定CFA、存储callee-saved registers),可以把FDE instructions压缩为32-bit。
  • CIE/FDE augmentation data描述的personality/lsda很常见,可以提取出来成为固定字段。

下面只讨论64-bit。一个descriptor占32字节

1
2
3
4
5
6
.quad _foo
.set L1, Lfoo_end-_foo
.long L1
.long compact_unwind_description
.quad personality
.quad lsda_address

如果研究.eh_frame_hdr(binary search index table)和.ARM.exidx的话,可以知道length字段是冗余的。

Compact unwind descriptor编码为:

1
2
3
uint32_t : 24; // vary with different modes
uint32_t mode : 4;
uint32_t flags : 4;

定义了5种mode:

  • 0: reserved
  • 1: FP-based frame: RBP为frame pointer,frame size可变
  • 2: SP-based frame: 不用frame pointer,frame size编译期固定
  • 3: large SP-based frame: 不用frame pointer,frame size编译期固定但数值较大,无法用mode 2表示
  • 4: DWARF CFI escape

FP-based frame (UNWIND_MODE_BP_FRAME)

Compact unwind descriptor编码为:

1
2
3
4
5
uint32_t regs : 15;
uint32_t : 1; // 0
uint32_t stack_adjust : 8;
uint32_t mode : 4;
uint32_t flags : 4;

x86-64上callee-saved寄存器有:RBX,R12,R13,R14,R15,RBP。3 bits可以编码一个寄存器,15 bits足够表示除RBP外的5个寄存器(是否保存及保存在哪里)。
stack_adjust记录保存寄存器外的额外栈空间。

SP-based frame (UNWIND_MODE_STACK_IMMD)

Compact unwind descriptor编码为:

1
2
3
4
5
6
uint32_t reg_permutation : 10;
uint32_t cnt : 3;
uint32_t : 3;
uint32_t size : 8;
uint32_t mode : 4;
uint32_t flags : 4;

cnt表示保存的寄存器数(最大6)。
reg_permutation表示保存的寄存器的排列的序号。
size*8表示栈帧大小。

Large SP-based frame (UNWIND_MODE_STACK_IND)

Compact unwind descriptor编码为:

1
2
3
4
5
6
uint32_t reg_permutation : 10;
uint32_t cnt : 3;
uint32_t adj : 3;
uint32_t size_offset : 8;
uint32_t mode : 4;
uint32_t flags : 4;

和SP-based frame类似。特别的是:栈帧大小是从text section读取的。RSP调整量通常由subq imm, %rsp表示,用size_offset表示该指令到函数开头的距离。
实际表示的stack size还要算上adj*8。

DWARF CFI escape

如果因为各种原因,compact unwind descriptor无法表示,就要回退到DWARF CFI。

LLVM实现里,每一个函数只用一个compact unwind descriptor表示。如果asynchronous stack unwinding发生在epilogue,已有实现无法把它和发生在function body的stack unwinding区分开来。
Canonical Frame Address会计算错误,caller-saved寄存器也会错误地读取。
如果发生在prologue,且prologue在push寄存器和subq imm, $rsp外有其他指令,也会出错。
另外如果一个函数启用了shrink wrapping,prologue可能不在函数开头处。开头到prologue间的asynchronous stack unwinding也会出错。
这个问题似乎多数人都不关心,可能是因为profiler丢失几个百分点的profile大家不在乎吧。

其实如果用多个descriptors描述一个函数的各个区域,还是可以准确unwind的。
OpenVMS 2018年提出了[RFC] Improving compact x86-64 compact unwind descriptors,可惜没有相关实现。

ARM exception handling

分为.ARM.exidx.ARM.extab

.ARM.exidx是个binary search index table,由2-word pairs组成。
第一个word是31-bit PC-relative offset to the start of the region。
第二个word用程序描述更加清晰:

1
2
3
4
5
6
7
8
9
if (indexData == EXIDX_CANTUNWIND)
return false; // like an absent .eh_frame entry. In the case of C++ exceptions, std::terminate
if (indexData & 0x80000000) {
extabAddr = &indexData;
extabData = indexData; // inline
} else {
extabAddr = &indexData + signExtendPrel31(indexData);
extabData = read32(&indexData + signExtendPrel31(indexData)); // stored in .ARM.extab
}

tableData & 0x80000000表示一个compact model entry,否则表示一个generic model entry。

.ARM.exidx相当于增强的.eh_frame_hdr,compact model相当于内联了.eh_frame中的personality和lsda。考虑下面三种情况:

  • 如果不会触发C++ exception且不会调用可能触发exception的函数:不需要personality,只需要一个EXIDX_CANTUNWIND entry,不需要.ARM.extab
  • 如果会触发C++ exception但是不需要landing pad:personality是__aeabi_unwind_cpp_pr0,只需要一个compact model的entry,不需要.ARM.extab
  • 如果有catch:需要__gxx_personality_v0,需要.ARM.extab

.ARM.extab相当于合并的.eh_frame.gcc_except_table

Generic model

1
2
3
4
5
uint32_t personality; // bit 31 is 0
uint32_t : 24;
uint32_t num : 8;
uint32_t opcodes[]; // opcodes, variable length
uint8_t lsda[]; // variable length

待补充

Windows ARM64 exception handling

参见https://docs.microsoft.com/en-us/cpp/build/arm64-exception-handling,这是我最欣赏的编码方案。
支持mid-prolog和mid-epilog的unwinding。支持function fragments(用来表示shrink wrapping等非常规栈帧)。

保存在.pdata.xdata两个sections。

1
2
3
uint32_t function_start_rva;
uint32_t Flag : 2;
uint32_t Data : 30;

对于canonical form的函数,使用Packed Unwind Data,不需要.xdata记录;对于Packed Unwind Data无法表示的descriptor,保存在.xdata

Packed Unwind Data

1
2
3
4
5
6
7
8
uint32_t FunctionStartRVA;
uint32_t Flag : 2;
uint32_t FunctionLength : 11;
uint32_t RegF : 3;
uint32_t RegI : 4;
uint32_t H : 1;
uint32_t CR : 2;
uint32_t FrameSize : 9;

MIPS compact exception tables

待补充