被提起 Split Stacks 技术，做了一些简单的笔记。

栈的基本结构

数据结构上的栈是一个简单的先近后出的数据结构，在此不再赘述。

程序在内存中运行时的栈遵循了栈先近先出的基本特性，同时承载了函数运行的一些相关的逻辑。函数的调用依赖于栈，栈中维护了程序运行时的上下文，包括函数返回地址、函数的调用参数以及函数空间内声明的栈上变量等。

以下面简单的 C 程序为例：

int add(int a, int b) {
    int ret = a + b;
    return ret;
}

int main() {
    int ret = add(1, 2);
    return 0;
}

得到的汇编程序如下：

add:
        pushq %rbp
        movq %rsp, %rbp
        movl %edi, -20(%rbp)
        movl %esi, -24(%rbp)
        movl -20(%rbp), %edx
        movl -24(%rbp), %eax
        addl %edx, %eax
        movl %eax, -4(%rbp)
        movl -4(%rbp), %eax
        popq %rbp
        ret
main:
        pushq %rbp
        movq %rsp, %rbp
        subq $16, %rsp
        movl $2, %esi
        movl $1, %edi
        call add
        movl %eax, -4(%rbp)
        movl $0, %eax
        leave
        ret

函数的调用需要借助寄存器或栈传递参数，下面是传递参数相关的代码段，在本程序中，参数传递借助寄存器完成，调用者将参数赋给寄存器，调用者在函数体内通过读取寄存器的值来获取参数。在参数较多的情况下，函数的参数可以借助栈来传递，参数会被调用方由右到左推入栈中，在进入被调用函数体后通过读取栈中元素将传递的参数取出。

movl $2, %esi
movl $1, %edi
...
movl -20(%rbp), %edx
movl -24(%rbp), %eax

函数的真正调用通过 call 指令或其衍生指令完成，如下面的代码段， call ptr 简单来说相当于 push IP; jmp ptr，即向栈中推入下面要执行的地址，然后跳转到被调用函数的代码段段。这里简单介绍一下寄存器 IP，IP 是指令指针寄存器，其中存入的是当前要读取的指令的地址。push 和 pop 指令分别对应入栈和出栈，push a 是将在栈顶存入元素 a，并将栈顶向外移动一个元素，pop x 是将栈顶元素存入寄存器 x，并将栈顶向内移动一个元素。

call add

栈空间的更替主要由下面的代码段完成，其中 rbq 寄存器为栈空间底的寄存器，rsp 寄存器为栈空间顶的寄存器。进入函数体之后，需要保存调用者栈空间地址，并更新被调用者的栈空间地址，具体为将栈空间底的地址放入栈中，再将新的栈底更新为当前栈顶。

1 2	pushq %rbp movq %rsp, %rbp

函数的运行中需要许多临时空间，这些临时空间除了通过寄存器实现，还有一部分通过栈上空间来临时寄存，如下面的代码段。

movl %edi, -20(%rbp)
movl %esi, -24(%rbp)
...
addl %edx, %eax

以下主要是处理函数返回值相关的代码段。函数的返回值在当前版本下通过栈空间来传递，具体为将返回值放入本函数栈内栈顶，在其他情况中，还支持通过寄存器传递给被调用者。

1 2	movl -4(%rbp), %eax popq %rbp

跳转回被调用者由 ret 完成。ret 指令相当于 pop IP，将栈顶的数据放入 IP 寄存器，即返回到之前调用者的代码段。

ret

内存栈的增长方向和操作系统及 CPU 相关，对于常见的 x86/Linux 结构来说，栈的增长是从高地址走向低地址的。简单来说，向栈空间中加入元素后，栈顶的地址会减小。

可以看出函数的调用过程与栈操作息息相关，经典的栈空间是预分配的、连续的，其限制会限制函数的调用的深度或支持的线程数量。

Split Stacks in GCC

Split Stacks 简单来说是一个支持自动增长的非连续栈。这种设计主要可以运行大量线程的问题，同时节约原先预分配的连续内存空间，每个线程初始可分配较少的栈空间，在后续需要的时候动态增长。

从 GCC 初版的实现上来说，Split Stacks 主要分为两个部分：一是检查当前的分裂栈是否够函数使用，二是如果空间不足拓展分裂栈。

实现策略

在实现上，GCC 考虑了以下的策略：

根据函数的不同，GCC 中会保留不同的栈空间大小，在实现中需要一个寄存器来存储当前栈底加上保留空间大小后的地址，通过这个寄存器可以方便检查是否需要对栈拓展。
在使用动态库时，需要函数 __tls_get_addr 来延迟分配 TLS，由于 Split Stacks 的栈空间变化， __tls_get_addr 的调用受限于不能以外额外的栈空间。除非整个系统使用了 Split Stacks 技术，不适用额外的栈空间是不可能的。这种情况可以通过 LD_BIND_NOW 的设置来缓解，通过设置重定位的执行时间，__tls_get_addr 可以统一程序开始时被调用，但这种方案无法解决 dlopen 这种动态加载的情况。
为了方便处理并照顾内存对齐，实现上每个分裂栈的大小通常为 2 的 n 次方大小，这种实现可以通过位运算来优化剩余空间的计算，从而得到性能上的收益。
需要引入一个函数来检查栈指针并负责栈拓展，这个函数会被内建为线程库的一部分，在每个函数执行的开始会被调用，可以和 PIC 部分合并。
可以重用原来的栈保护机制（Stack Guard 一类的）来保护已分裂的栈。
至少在 x86 上使用 FS 和 GS 寄存器来进行 TCB 头上新变量空间的分配，在 i386 和 x86_64 上使用类似的机制。

栈空间拓展

对栈进行拓展上，GCC 考虑了以下的问题：

所有进行 Split Stacks 分配的函数不能使用 Split Stacks，毕竟可能导致无限的递归，需要定义函数修饰符 no_split_stack 来标识不使用 Split Stacks 的逻辑，这部分逻辑同时需要保证当前栈空间对这些函数可用。
由于函数的参数传递需要栈的辅助，在进行栈分裂的时候需要考虑参数的拷贝，对于普通的 C++ 对象调用拷贝或移动构造函数就好，而对于变参函数的参数拷贝，可以通过取参函数的二次封装，将原有的参数还定位至未分裂的栈上。
在 ret 返回调用者代码段的时候，需要释放被分裂的栈并恢复原栈结构。

后向兼容

因为存在支持 Split Stacks 和不支持 Split Stacks 函数的混合调用，所以在后向兼容方面 GCC 考虑了一些策略：

通过空段 .note.GNU-split-stack 来表明编译中是启动了 Split Stacks 的，同时如果存在某些函数被 no_split_stack 所修饰，那么编译后产生的文件内还需增加 .note.GNU-no-split-stack 一段。
当 Linker 链接动态库时，需要寻找存在非 Split Stacks 调用的 Split Stacks 调用，并进行相应的处理。Linker 会修改存在非 Split Stacks 调用的 Split Stacks 调用的初始化部分，使得该函数运行时会进行额外的栈空间大小校验，从而支持非 Split Stacks 函数的调用。
针对不能确定函数指针指向的函数是否支持 Split Stacks 的问题，会通过一个中间调用 __fnptr_morestack 来处理，__fnptr_morestack 以函数指针和函数指针传递的参数尺寸作为自身参数。将函数指针的参数传递完毕后，会优先调用 __fnptr_morestack 来处理，__fnptr_morestack 会额外检查函数指针是否支持 Split Stacks。

Split Stacks in Golang

与 GCC 相似，在 Golang 的 goroutine 的实现中也应用了类似的技术。在 1.3 版本及以前采用的是分段栈的实现，在初始时会对每个 goroutine 分配 8KB 的内存，而在 goroutine 内部每个函数的调用时，会检查栈空间是否足够使用，若不够则调用 morestack 进行额外的栈空间申请，申请完毕后连接到旧栈空间上，在函数结束时会调用 lessstack 来回收多余的栈空间。

由于栈的缩减是一个相对来说开销较大的逻辑，尤其在一个较深的递归中，会有较多的 morestack 和 lessstack 调用，这种问题被成为热分裂问题。Golang 1.4 通过栈复制法来解决这个问题，在栈空间不足时，不会申请一个新的栈空间块链接到老的栈空间快上，而是创建一个原来两倍大小的栈空间块，并将旧栈信息拷贝至新栈中。这样对于栈的缩减，没有多余的开销，同时在第二次拓展栈时，也无需再次申请空间。针对栈复制中指针的问题，由于垃圾回收机制的存在，可以找到哪部分的栈使用了指针，通过对应可以将指针地址进行相应的更新。

参考资料：