栈内存管理

引言

使用过go的程序猿都应该很熟悉，其之所以并发能力强悍，主要得益于可以创建大量的比线程更加轻量的协程以及协程调度机制，那么一个协程有多轻量或者说初始的栈空间是多大呢？对于我而言，在写这篇文章之前会毫不犹豫的说:"2KB!"，到底对不对，下文会给出解答。接下来我们以go1.12.5版本为研究对象，看看源码(runtime/stack.go)中是如何管理栈内存的。

主要内容：

• 堆内存管理
• 全局栈内存初始化
• 申请内存
• 栈扩容
• 栈收缩

堆内存管理

在go的程序中，协程属于一种用户态线程，所以其调用栈内存其实也是从堆上申请的, 而谈到堆内存时，我们首先需要了解几个内存管理单元：mspan、mcache、mcentral、mheap, 在公众号<<学而思网校技术团队>>的往期内容中朱清伟老师有专门介绍，标题为“Golang内存分配”https://mp.weixin.qq.com/s/izjdImIZGvfGaSO-N_aCUA

全局栈内存初始化

在go程序启动的时候会调用stackinit()函数，进行初始化，其中涉及到两个重要的全局变量stackpool和stackLarge

//小空间内存池
//_NumStackOrders是一个常量，在不同的系统中值是不一样，有如下对应关系
//   OS               | FixedStack | NumStackOrders
//   -----------------+------------+---------------
//   linux/darwin/bsd | 2KB        | 4
//   windows/32       | 4KB        | 3
//   windows/64       | 8KB        | 2
//   plan9            | 4KB        | 3
var stackpool [_NumStackOrders]mSpanList

//大空间内存池
var stackLarge struct {
        //由于是全局共享变量，所以使用时会加锁
    lock mutex

    //heapAddrBits，
    //pageShift=13,go的内存管理中一页的大小为8kb，此值代表log2(8*1024) = 13
    //索引其实是从2开始才可能有空闲内存
    //2 => 全为2^2 * page大小的mspan   （注：page大小为8KB）
    //3 => 全为2^3 * page大小的mspan
    //...
    free [heapAddrBits - pageShift]mSpanList 
}

//mspan结构中有三个指针next、prev、list(指向mSpanList)
type mSpanList struct {
    first *mspan // first span in list, or nil if none
    last  *mspan // last span in list, or nil if none
}

对mSpanList 初始化，设置first 和 last 都为nil

// 初始化mSpanList链表
func (list *mSpanList) init() {
    list.first = nil
    list.last = nil
}

上述的两个变量就是栈内存管理的基本单元，初始化时并没有预分配空间，而是在程序执行时，按需申请的,其结构如下：

image.png

stackLarge 是一个自定义结构体，它成员变量free 和 stackpool 的结构是一样的

申请内存

我们从以创建协程g来举例子，走一遍申请的过程。
由于在newproc1()方法中定义了创建协程时所申请初始栈内存的大小，所以直接从这里开始

//文件位置：runtime/proc.go

//使用从argp开始的narg个参数字节创建一个运行fn的新g。 
//callerpc是创建它的go语句的地址。 
//新g放入g等待运行的队列中。
func newproc1(fn *funcval, argp *uint8, narg int32, callergp *g, callerpc uintptr) {
    
    //...

    _p_ := _g_.m.p.ptr()
    newg := gfget(_p_)
    if newg == nil {
        //此行是关键 
        //申请内存，大小为_StackMin个字节
        newg = malg(_StackMin)
        casgstatus(newg, _Gidle, _Gdead)
        allgadd(newg) // publishes with a g->status of Gdead so GC scanner doesn't look at uninitialized stack.
    }

    //...
}

//给新的g分配足以容纳stacksize 字节的空间,即至少stacksize 个字节
func malg(stacksize int32) *g {
    newg := new(g)
    if stacksize >= 0 {
        stacksize = round2(_StackSystem + stacksize)
        systemstack(func() {
            //真正申请内存stacksize大小的内存
            newg.stack = stackalloc(uint32(stacksize))
        })
        newg.stackguard0 = newg.stack.lo + _StackGuard
        newg.stackguard1 = ^uintptr(0)
    }
    return newg
}

//函数的功能：取得一个值使得不等式 2^n >= x 成立且左边是所有成立值中的最小值
//如：round2(15) = 16 ; round2(18)=32 ...
func round2(x int32) int32 {
    s := uint(0)
    for 1<<s < x {
        s++
    }
    return 1 << s
}

过程中有几个常量需要说明下：

• _StackMin：值为2048,表示go 代码使用最小的栈空间大小
• _StackSystem：是在常规保护区域下方的每个堆栈中添加的一些额外字节，用于特定于OS的目的（例如信号处理）。 在Windows，Plan 9和iOS上使用，因为它们不使用单独的堆栈,定义如下

//文件位置：runtime/malloc.go

_StackSystem = sys.GoosWindows*512*sys.PtrSize + sys.GoosPlan9*512 + sys.GoosDarwin*sys.GoarchArm*1024 + sys.GoosDarwin*sys.GoarchArm64*1024
//解释
//os        /   _StackSystem 
//----------+---------------------
//win32     /  2048
//win64     /  4096
//GoosPlan9 /  512
//linux     / 0
//...

• 由此我们可以算出，传给stackalloc()的stacksize 是一个根据当前系统计算出来的值，也就是说，win64为8kb、win32为4kb、plan9为4kb、其他系统如linux/bsd/drawin才是2kb！

接下来我们看下stackalloc()的关键源码

func stackalloc(n uint32) stack {
    //必须在调度程序堆栈上调用Stackalloc，
    //以防止在正在执行此动作时发送栈扩导致的死锁
    thisg := getg()
    if thisg != thisg.m.g0 {
        throw("stackalloc not on scheduler stack")
    }
    
    //...省略部分代码

    //需要小堆栈在固定大小空闲列表中分配，大堆栈则到专用span中申请分配
    //_StackCacheSize 是一个常量32*1024 即32KB
    //_FixedStack 和 _NumStackOrders 上文已有说明
    var v unsafe.Pointer
    if n < _FixedStack<<_NumStackOrders && n < _StackCacheSize {
        order := uint8(0)
        n2 := n
        //order 代表: n是_FixedStack的几倍
        // 0: _FixedStack大小，1：代表2倍_FixedStack大小；2代表四倍
        for n2 > _FixedStack {
            order++
            n2 >>= 1
        }
        
        var x gclinkptr
        //首先去本地内存缓存mcache.stackcache中获取可用内存
        //如果本地缓存中存在，则直接获取，并更新链表
        //如果不存在则 调用stackpoolalloc 向mheap去申请 
        c := thisg.m.mcache
        if stackNoCache != 0 || c == nil || thisg.m.preemptoff != "" {
            lock(&stackpoolmu)
            //从小栈池中获取内存
            x = stackpoolalloc(order)
            unlock(&stackpoolmu)
        } else {
            x = c.stackcache[order].list
            if x.ptr() == nil {
                //stackcacherefill会调用stackpoolalloc然后把申请到的内存填充到c.stackcache 中
                stackcacherefill(c, order)
                x = c.stackcache[order].list
            }
            c.stackcache[order].list = x.ptr().next
            c.stackcache[order].size -= uintptr(n)
        }
        v = unsafe.Pointer(x)
    } else {
        
        //如果是大空间(大于等于32KB)
        //则先到stackLarge的数组中获取，如果对应下标的数组为空则向mheap申请
        var s *mspan
        npage := uintptr(n) >> _PageShift
        // stacklog2 返回 log_2(n)
        log2npage := stacklog2(npage)

        //stackLarge数组所指向的空闲内存空间全部是通过栈回收来获得的。
        lock(&stackLarge.lock)
        if !stackLarge.free[log2npage].isEmpty() {
            s = stackLarge.free[log2npage].first
            stackLarge.free[log2npage].remove(s)
        }
        unlock(&stackLarge.lock)

        if s == nil {
            //向mheap申请npage大小的内存空间用于栈
            s = mheap_.allocManual(npage, &memstats.stacks_inuse)
            if s == nil {
                throw("out of memory")
            }
            osStackAlloc(s)
            s.elemsize = uintptr(n)
        }
        v = unsafe.Pointer(s.base())
    }

    //... 省略部分代码
    
    return stack{uintptr(v), uintptr(v) + uintptr(n)}
}

从空闲池中分配栈空间，如果池为空，则向mheap申请内存，并把多余的空间缓存到池中

func stackpoolalloc(order uint8) gclinkptr {
    list := &stackpool[order]
    //s为指向span的指针
    s := list.first
    if s == nil {
        //一次申请32KB内存即4页
        s = mheap_.allocManual(_StackCacheSize>>_PageShift, &memstats.stacks_inuse)
        
        //... 
        
        //对新申请的内存，在使用之前先初始化系统栈
        osStackAlloc(s)
        s.elemsize = _FixedStack << order
        for i := uintptr(0); i < _StackCacheSize; i += s.elemsize {
            //gclinkptr 也是一个指针类型
            //作用是屏蔽gc扫描
            x := gclinkptr(s.base() + i)
            //链表头插法
            x.ptr().next = s.manualFreeList
            s.manualFreeList = x
        }
        list.insert(s)
    }
    x := s.manualFreeList
    if x.ptr() == nil {
        throw("span has no free stacks")
    }
    s.manualFreeList = x.ptr().next
    s.allocCount++
    if s.manualFreeList.ptr() == nil {
        //所有内存已经分配完毕，删除节点s
        list.remove(s)
    }
    return x
}

到空闲池stackpoolalloc中获取内存，并缓存到mcache的stackcache数组中

func stackcacherefill(c *mcache, order uint8) {
    if stackDebug >= 1 {
        print("stackcacherefill order=", order, "\n")
    }

    var list gclinkptr
    var size uintptr
    lock(&stackpoolmu)
    //为什么_StackCacheSize/2 ？
    for size < _StackCacheSize/2 {
        x := stackpoolalloc(order)
        x.ptr().next = list
        list = x
        size += _FixedStack << order
    }
    unlock(&stackpoolmu)
    c.stackcache[order].list = list
    c.stackcache[order].size = size
}

stackcache的结构图示

image.png

我们用一个流程图来归纳下栈空间分配的流程

image.png

栈扩容

刚才我们已经了解到了，linux系统下协程初始栈空间大小为仅仅只有2KB很小，仅分配了保障协程运行的最小空间。go的策略是按需申请，动态扩容，尽量减少内存浪费，每次扩容时会调用运行时方法runtime·morestack(SB) -> runtime·newstack(SB) 。
我们先看一个调用栈扩容的例子

//main.go
package main

import "fmt"

func main() {
    //调用递归方法Fun
    //
    result := Fun(0)
    fmt.Printf("递归调用结果: %d\n", result)
}

func Fun(n int) int {
    if n == 1 {
        return n
    }
    return n + Fun(n-1)
}

通过汇编代码我们可以看到运行时代码的调用过程

$ go tool compile -S -N -l main.go 
//... 省略
"".main STEXT size=386 args=0x0 locals=0xb8
    0x0000 00000 (main.go:5)    TEXT    "".main(SB), ABIInternal, $184-0
//...
    0x0178 00376 (main.go:5)    CALL    runtime.morestack_noctxt(SB)
    0x017d 00381 (main.go:5)    JMP 0
//...
"".Fun STEXT size=125 args=0x10 locals=0x20
    0x0000 00000 (main.go:12)   TEXT    "".Fun(SB), ABIInternal, $32-16
//...
    0x0076 00118 (main.go:12)   CALL    runtime.morestack_noctxt(SB)
    0x007b 00123 (main.go:12)   JMP 0
//...

输出结果：

runtime: goroutine stack exceeds 1000000000-byte limit 
fatal error: stack overflow

runtime stack:
runtime.throw(0x4bb0dd, 0xe)
....

栈内存增长到超过了1GB，并触发了栈溢出的错误！
栈扩容对应的源码如下：

//runtime/stack.go
func newstack() {
    //...
    //2倍大小增长栈空间
    oldsize := gp.stack.hi - gp.stack.lo
    newsize := oldsize * 2
    if newsize > maxstacksize {
        print("runtime: goroutine stack exceeds ", maxstacksize, "-byte limit\n")
        throw("stack overflow")
    }

    //更改当前g的状态  _Grunning -> _Gcopystack
    //处于_Gcopystack 状态时 GC不会扫描栈空间
    casgstatus(gp, _Grunning, _Gcopystack)

    copystack(gp, newsize, true)
    if stackDebug >= 1 {
        print("stack grow done\n")
    }
    casgstatus(gp, _Gcopystack, _Grunning)
    gogo(&gp.sched)
}

//栈空间调整信息
type adjustinfo struct {
    old   stack    //旧的栈空间，stack.hi,   stack.lo
    delta uintptr //旧栈栈底到新栈栈底的偏移量
    cache pcvalueCache  //调整栈帧时会用到

    //sudog.elem 在栈上的最高位置
    sghi uintptr
}

func copystack(gp *g, newsize uintptr, sync bool) {
    //...
    old := gp.stack
    if old.lo == 0 {
        throw("nil stackbase")
    }
    used := old.hi - gp.sched.sp

    // allocate new stack
    new := stackalloc(uint32(newsize))
    //...
    //计算调整信息
    var adjinfo adjustinfo
    adjinfo.old = old
    adjinfo.delta = new.hi - old.hi

    // Adjust sudogs, synchronizing with channel ops if necessary.
    ncopy := used
    if sync {
        //
        adjustsudogs(gp, &adjinfo)
    } else {
        adjinfo.sghi = findsghi(gp, old)
        ncopy -= syncadjustsudogs(gp, used, &adjinfo)
    }

    //内存操作：拷贝到新的空间
    memmove(unsafe.Pointer(new.hi-ncopy), unsafe.Pointer(old.hi-ncopy), ncopy)

    //修改指针地址
    gp.stack = new
    gp.stackguard0 = new.lo + _StackGuard 
    gp.sched.sp = new.hi - used
    gp.stktopsp += adjinfo.delta
  
    //释放旧空间
    stackfree(old)
}

栈扩容的示意图

image.png

其实stackfree 就是栈申请空间的逆向操作，我们仅用图示表示其过程

image.png

栈收缩

栈收缩是由gc触发执行的源码位置runtime/mgcmark.go， 收缩时调用方法shrinkstack()

func shrinkstack(gp *g) {
    gstatus := readgstatus(gp)
    if gstatus&^_Gscan == _Gdead {
        if gp.stack.lo != 0 {
            //如果当前的g的运行状态为_Gdead 则全部回收
            stackfree(gp.stack)
            gp.stack.lo = 0
            gp.stack.hi = 0
        }
        return
    }
    //...

    oldsize := gp.stack.hi - gp.stack.lo
    newsize := oldsize / 2
    if newsize < _FixedStack {
        return
    }
    
    //当所有的已使用的空间小于栈总空间的1/4时，栈收缩为原来的一半
    //gp.sched.sp 为栈顶指针kongjian
    //_StackLimit 在不扩容情况下执行被调函数所能用的最大空间
    avail := gp.stack.hi - gp.stack.lo
    if used := gp.stack.hi - gp.sched.sp + _StackLimit; used >= avail/4 {
        return
    }

    //...

    //拷贝到小空间中
    copystack(gp, newsize, false)
}

结语

本文主要讲了栈内存初始化、分配、释放以及相关栈内存管理组件的执行逻辑，希望能帮助大家在看相关源码时能有一个大体的认识。

有疑问加站长微信联系（非本文作者）