连续栈
2021.07

3.5 连续栈

Go语言支持goroutine,每个goroutine需要能够运行,所以它们都有自己的栈。假如每个goroutine分配固定栈大小并且不能增长,太小则会导致溢出,太大又会浪费空间,无法存在许多的goroutine。

为了解决这个问题,goroutine可以初始时只给栈分配很小的空间,然后随着使用过程中的需要自动地增长。这就是为什么Go可以开千千万万个goroutine而不会耗尽内存。

Go1.3版本之后则使用的是continuous stack,下面将具体分析一下这种技术。

基本原理

每次执行函数调用时Go的runtime都会进行检测,若当前栈的大小不够用,则会触发“中断”,从当前函数进入到Go的运行时库,Go的运行时库会保存此时的函数上下文环境,然后分配一个新的足够大的栈空间,将旧栈的内容拷贝到新栈中,并做一些设置,使得当函数恢复运行时,函数会在新分配的栈中继续执行,仿佛整个过程都没发生过一样,这个函数会觉得自己使用的是一块大小“无限”的栈空间。

实现过程

在研究Go的实现细节之前让我们先自己思考一下应该如何实现。第一步肯定要有某种机制检测到当前栈大小不够用了,这个应该是把当前的栈寄存器SP跟栈的可用栈空间的边界进行比较。能够检测到栈大小不够用,就相当于捕捉到了“中断”。

捕获完“中断”,第二步要做的,就应该是进入运行时,保存当前goroutine的上下文。别陷入如何保存上下文的细节,先假如我们把函数栈增长时的上下文保存好了,那下一步就是分配新的栈空间了,我们可以将分配空间想象成就是调用一下malloc而已。

接下来怎么办呢?我们要将旧栈中的内容拷贝到新栈中,然后让函数继续在新栈中运行。这里先暂时忽略旧栈内容拷贝到新栈中的一些技术难点,假设在新栈空间中恢复了“中断”时的上下文,从运行时返回到函数。

函数在新的栈中继续运行了,但是还有个问题:函数如何返回。因为函数返回后栈是要缩小的,否则就会内存浪费空间了,所以还需要在函数返回时处理栈缩小的问题。

具体细节

如何捕获到函数的栈空间不足

Go语言和C不同,不是使用栈指针寄存器和栈基址寄存器确定函数的栈的。在Go的运行时库中,每个goroutine对应一个结构体G,大致相当于进程控制块的概念。这个结构体中存了stackbase和stackguard,用于确定这个goroutine使用的栈空间信息。每个Go函数调用的前几条指令,先比较栈指针寄存器跟g->stackguard,检测是否发生栈溢出。如果栈指针寄存器值超越了stackguard就需要扩展栈空间。

为了加深理解,下面让我们跟踪一下代码,并看看实际生成的汇编吧。首先写一个test.go文件,内容如下:

package main
func main() {
    main()
}

然后生成汇编文件:

go tool 6g -S test.go | head -8

可以看以输出是:

000000 00000 (test.go:3)    TEXT    "".main+0(SB),$0-0
000000 00000 (test.go:3)    MOVQ    (TLS),CX
0x0009 00009 (test.go:3)    CMPQ    SP,(CX)
0x000c 00012 (test.go:3)    JHI    ,21
0x000e 00014 (test.go:3)    CALL    ,runtime.morestack00_noctxt(SB)
0x0013 00019 (test.go:3)    JMP    ,0
0x0015 00021 (test.go:3)    NOP    ,

让我们好好看一下这些指令。(TLS)取到的是结构体G的第一个域,也就是g->stackguard地址,将它赋值给CX。然后CX地址的值与SP进行比较,如果SP大于g->stackguard了,则会调用runtime.morestack函数。这几条指令的作用就是检测栈是否溢出。

不过并不是所有函数在链接时都会插入这种指令。如果你读源代码,可能会发现#pragma textflag 7,或者在汇编函数中看到TEXT reuntime.exit(SB),7,$0,这种函数就是不会检测栈溢出的。这个是编译标记,控制是否生成栈溢出检测指令。

runtime.morestack是用汇编实现的,做的事情大致是将一些信息存在M结构体中,这些信息包括当前栈桢,参数,当前函数调用,函数返回地址(两个返回地址,一个是runtime.morestack的函数地址,一个是f的返回地址)。通过这些信息可以把新栈和旧栈链起来。

void runtime.morestack() {
    if(g == g0) {
        panic();
    } else {
        m->morebuf.gobuf_pc = getCallerCallerPC();
        void *SP = getCallerSP();
        m->morebuf.gobuf_sp = SP;
        m->moreargp = SP;
        m->morebuf.gobuf_g = g;
        m->morepc = getCallerPC();

        void *g0 = m->g0;
        g = g0;
        setSP(g0->g_sched.gobuf_sp);
        runtime.newstack();
    }
}

需要注意的就是newstack是切换到m->g0的栈中去调用的。m->g0是调度器栈,go的运行时库的调度器使用的都是m->g0。

旧栈数据复制到新栈

runtime.morestack会调用于runtime.newstack,newstack做的事情很好理解:分配一个足够大的新的空间,将旧的栈中的数据复制到新的栈中,进行适当的修饰,伪装成调用过runtime.lessstack的样子(这样当函数返回时就会调用runtime.lessstack再次进入runtime中做一些栈收缩的处理)。

这里有一个技术难点:旧栈数据复制到新栈的过程,要考虑指针失效问题。

比如有某个指针,引用了旧栈中的地址,如果仅仅是将旧栈内容搬到新栈中,那么该指针就失效了,因为旧栈已被释放,应该修改这个指针让它指向新栈的对应地址。考虑如下代码:

func f1() {
    var a A
    f(&a)
}
func f2(a *A) {
    // modify a
}

如果在f2中发生了栈增长,此时分配更大的空间作为新栈,并将旧栈内容拷贝到新栈中,仅仅这样是不够的,因为f2中的a还是指向旧栈中的f1的,所以必须调整。

Go实现了精确的垃圾回收,运行时知道每一块内存对应的对象的类型信息。在复制之后,会进行指针的调整。具体做法是,对当前栈帧之前的每一个栈帧,对其中的每一个指针,检测指针指向的地址,如果指向地址是落在旧栈范围内的,则将它加上一个偏移使它指向新栈的相应地址。这个偏移值等于新栈基地址减旧栈基地址。

runtime.lessstack比较简单,它其实就是切换到m->g0栈之后调用runtime.oldstack函数。这时之前保存的那个Stktop结构体是时候发挥作用了,从上面可以找到旧栈空间的SP和PC等信息,通过runtime.gogo跳转过去,整个过程就完成了。

gp = m->curg; //当前g
top = (Stktop*)gp->stackbase; //取得Stktop结构体
label = top->gobuf; //从结构体中取出Gobuf
runtime·gogo(&label, cret); //通过Gobuf恢复上下文

小结

使用分段栈的函数头几个指令检测SP和stackguard,调用runtime.morestack

runtime.morestack函数的主要功能是保存当前的栈的一些信息,然后转换成调度器的栈调用runtime.newstack

runtime.newstack函数的主要功能是分配空间,装饰此空间,将旧的frame和arg弄到新空间

使用gogocall的方式切换到新分配的栈,gogocall使用的JMP返回到被中断的函数

继续执行遇到RET指令时会返回到runtime.lessstack,lessstack做的事情跟morestack相反,它要准备好从new stack到old stack

整个过程有点像一次中断,中断处理时保存当时的现场,弄个新的栈,中断恢复时恢复到新栈中运行。栈的收缩是垃圾回收的过程中实现的.当检测到栈只使用了不到1/4时,栈缩小为原来的1/2.