7.3 栈空间内存管理

7.3.1 设计原理

栈内存一般由编译器自动分配和释放，其中存储着函数的入参以及局部变量，这些参数会随着函数的创建而创建，函数的返回而消亡。

寄存器

寄存器是 CPU 中的稀缺资源,存储能力非常有限，但是能提供最快的读写速度，充分利用寄存器的速度可以构建高性能的应用程序。

栈寄存器是 CPU 寄存器中的一种，它的主要作用是跟踪函数的调用栈，Go 语言的汇编代码包含 BP 和 SP 两个栈寄存器，分别存储了栈的基址指针和栈顶的地址，BP 和 SP 之间的内存就是当前函数的调用栈。

stack-registers

栈区内存都是从高地址向低地址扩展的，当应用程序申请或者释放栈内存时只需要修改 SP 寄存器的值，这种线性的内存分配方式与堆内存相比更加快速，仅会带来极少的额外开销。

线程栈

在 Linux 操作系统中执行 pthread_create 系统调用，进程会启动一个新的线程，如果用户没有通过软资源限制 RLIMIT_STACK 指定线程栈的大小，那么操作系统会根据架构选择不同的默认栈大小。

逃逸分析

在 C 语言和 C++ 这类需要手动管理内存的编程语言中，将对象或者结构体分配到栈上或者堆上是由工程师自主决定的，但是手动分配内存会导致如下的两个问题：

1. 若不需要分配到堆上的对象分配到了堆上：浪费内存空间
2. 需要分配到堆上的对象分配到了栈上：悬挂指针、影响内存安全

在 C 语言中，栈上的变量被函数作为返回值返回给调用方是一个常见的错误，在如下所示的代码中，栈上的变量 i 被错误返回：

int *dangling_pointer() {
    int i = 2;
    return &i;
}

当 dangling_pointer 函数返回后，它的本地变量会被编译器回收，调用方获取的是危险的悬挂指针，我们不确定当前指针指向的值是否合法时，这种问题在大型项目中是比较难以发现和定位的。

在编译器优化中，逃逸分析是用来决定指针动态作用域的方法。

Go 语言的编译器使用逃逸分析决定哪些变量应该在栈上分配，哪些变量应该在堆上分配，其中包括使用 new、make 和字面量等方法隐式分配的内存，Go 语言的逃逸分析遵循以下两个不变性：

1. 指向栈对象的指针不能存在于堆中
2. 指向栈对象的指针不能在栈对象回收后存活

escape-analysis-and-key-invariants

逃逸分析是静态分析的一种，在编译器解析了 Go 语言源文件后，它可以获得整个程序的抽象语法树（Abstract syntax tree，AST），编译器可以根据抽象语法树分析静态的数据流，我们会通过以下几个步骤实现静态分析的全过程：

1. 构建带权重的有向图，其中顶点 cmd/compile/internal/gc.EscLocation 表示被分配的变量，边 cmd/compile/internal/gc.EscEdge 表示变量之间的分配关系，权重表示寻址和取地址的次数；
2. 遍历对象分配图并查找违反两条不变性的变量分配关系，如果堆上的变量指向了栈上的变量，那么该变量需要分配在堆上；
3. 记录从函数的调用参数到堆以及返回值的数据流，增强函数参数的逃逸分析

栈内存空间

Go 语言使用用户态线程 Goroutine 作为执行上下文，它的额外开销和默认栈大小都比线程小很多，然而 Goroutine 的栈内存空间和栈结构也在早期几个版本中发生过一些变化：

1. v1.0 ~ v1.1 — 最小栈内存空间为 4KB
2. v1.2 — 将最小栈内存提升到了 8KB
3. v1.3 — 使用连续栈替换之前版本的分段栈
4. v1.4 — 将最小栈内存降低到了 2KB

分段栈

分段栈是 Go 语言在 v1.3 版本之前的实现。

segmented-stacks

分段栈机制虽然能够按需为当前 Goroutine 分配内存并且及时减少内存的占用，但是它也存在两个比较大的问题：

1. 如果当前 Goroutine 的栈几乎充满，那么任意的函数调用都会触发栈扩容，当函数返回后又会触发栈的收缩，如果在一个循环中调用函数，栈的分配和释放就会造成巨大的额外开销，这被称为热分裂问题（Hot split）；
2. 一旦 Goroutine 使用的内存越过了分段栈的扩缩容阈值，运行时会触发栈的扩容和缩容，带来额外的工作量；

连续栈

连续栈可以解决分段栈中存在的两个问题，其核心原理是每当程序的栈空间不足时，初始化一片更大的栈空间并将原栈中的所有值都迁移到新栈中，新的局部变量或者函数调用就有充足的内存空间。

使用连续栈机制时，栈空间不足导致的扩容会经历以下几个步骤：

1. 在内存空间中分配更大的栈内存空间；
2. 将旧栈中的所有内容复制到新栈中；
3. 将指向旧栈对应变量的指针重新指向新栈；
4. 销毁并回收旧栈的内存空间；

在扩容的过程中，最重要的是调整指针的第三步，这一步能够保证指向栈的指针的正确性，因为栈中的所有变量内存都会发生变化，所以原本指向栈中变量的指针也需要调整。我们在前面提到过经过逃逸分析的 Go 语言程序的遵循以下不变性 —— 指向栈对象的指针不能存在于堆中，所以指向栈中变量的指针只能在栈上，我们只需要调整栈中的所有变量就可以保证内存的安全了。

continuous-stacks

7.3.2 栈操作

Go 语言中的执行栈由 runtime.stack 表示，该结构体中只包含两个字段，分别表示栈的顶部和栈的底部，每个栈结构体都表示范围为 [lo, hi) 的内存空间：

type stack struct {
	lo uintptr
	hi uintptr
}

栈初始化

栈空间在运行时中包含两个重要的全局变量，分别是 runtime.stackpool 和 runtime.stackLarge，这两个变量分别表示全局的栈缓存和大栈缓存，前者可以分配小于 32KB 的内存，后者用来分配大于 32KB 的栈空间：

var stackpool [_NumStackOrders]struct {
	item stackpoolItem
	_    [cpu.CacheLinePadSize - unsafe.Sizeof(stackpoolItem{})%cpu.CacheLinePadSize]byte
}

type stackpoolItem struct {
	mu   mutex
	span mSpanList
}

var stackLarge struct {
	lock mutex
	free [heapAddrBits - pageShift]mSpanList
}

这两个用于分配空间的全局变量都与内存管理单元 runtime.mspan 有关，我们可以认为 Go 语言的栈内存都是分配在堆上的，运行时初始化会调用 runtime.stackinit 初始化这些全局变量：

func stackinit() {
	for i := range stackpool {
		stackpool[i].item.span.init()
	}
	for i := range stackLarge.free {
		stackLarge.free[i].init()
	}
}

如果运行时只使用全局变量来分配内存的话，会造成线程之间的锁竞争进而影响程序的执行效率，栈内存由于与线程关系比较密切，所以我们在每一个线程缓存 runtime.mcache 中都加入了栈缓存减少锁竞争影响。

type mcache struct {
	stackcache [_NumStackOrders]stackfreelist
}

type stackfreelist struct {
	list gclinkptr
	size uintptr
}

stack-memory

运行时使用全局的 runtime.stackpool 和线程缓存中的空闲链表分配 32KB 以下的栈内存，使用全局的 runtime.stackLarge 和堆内存分配 32KB 以上的栈内存，提高本地分配栈内存的性能。

栈分配

运行时会在 Goroutine 的初始化函数 runtime.malg 中调用 runtime.stackalloc 分配一个大小足够栈内存空间，根据线程缓存和申请栈的大小，该函数会通过三种不同的方法分配栈空间：

1. 如果栈空间较小，使用全局栈缓存或者线程缓存上固定大小的空闲链表分配内存；
2. 如果栈空间较大，从全局的大栈缓存 runtime.stackLarge 中获取内存空间；
3. 如果栈空间较大并且 runtime.stackLarge 空间不足，在堆上申请一片大小足够内存空间；

栈扩容

编译器会在 cmd/internal/obj/x86.stacksplit 中为函数调用插入 runtime.morestack 运行时检查，它会在几乎所有的函数调用之前检查当前 Goroutine 的栈内存是否充足，如果当前栈需要扩容，我们会保存一些栈的相关信息并调用 runtime.newstack 创建新的栈：

func newstack() {
	thisg := getg()
	gp := thisg.m.curg
	...
	preempt := atomic.Loaduintptr(&gp.stackguard0) == stackPreempt
	if preempt {
		if !canPreemptM(thisg.m) {
			gp.stackguard0 = gp.stack.lo + _StackGuard
			gogo(&gp.sched)
		}
	}

	sp := gp.sched.sp
	if preempt {
		if gp.preemptShrink {
			gp.preemptShrink = false
			shrinkstack(gp)
		}

		if gp.preemptStop {
			preemptPark(gp)
		}

		gopreempt_m(gp)
	}
	...
}

runtime.newstack 会先做一些准备工作并检查当前 Goroutine 是否发出了抢占请求，如果发出了抢占请求：

1. 当前线程可以被抢占时，直接调用 runtime.gogo 触发调度器的调度；
2. 如果当前 Goroutine 在垃圾回收被 runtime.scanstack 标记成了需要收缩栈，调用 runtime.shrinkstack；
3. 如果当前 Goroutine 被 runtime.suspendG 函数挂起，调用 runtime.preemptPark 被动让出当前处理器的控制权并将 Goroutine 的状态修改至 _Gpreempted；
4. 调用 runtime.gopreempt_m 主动让出当前处理器的控制权；

如果当前 Goroutine 不需要被抢占，意味着我们需要新的栈空间来支持函数调用和本地变量的初始化，运行时会先检查目标大小的栈是否会溢出：

func newstack() {
	...
	oldsize := gp.stack.hi - gp.stack.lo
	newsize := oldsize * 2
	if newsize > maxstacksize {
		print("runtime: goroutine stack exceeds ", maxstacksize, "-byte limit\n")
		print("runtime: sp=", hex(sp), " stack=[", hex(gp.stack.lo), ", ", hex(gp.stack.hi), "]\n")
		throw("stack overflow")
	}

	casgstatus(gp, _Grunning, _Gcopystack)
	copystack(gp, newsize)
	casgstatus(gp, _Gcopystack, _Grunning)
	gogo(&gp.sched)
}

如果目标栈的大小没有超出程序的限制，我们会将 Goroutine 切换至 _Gcopystack 状态并调用 runtime.copystack 开始栈拷贝。在拷贝栈内存之前，运行时会通过 runtime.stackalloc 分配新的栈空间：

func copystack(gp *g, newsize uintptr) {
	old := gp.stack
	used := old.hi - gp.sched.sp

	new := stackalloc(uint32(newsize))
	...
}

新栈的初始化和数据的复制是一个比较简单的过程，不过这不是整个过程中最复杂的地方，我们还需要将指向源栈中内存指向新的栈，在这期间我们需要分别调整以下的指针：

1. 调用 runtime.adjustsudogs 或者 runtime.syncadjustsudogs 调整 runtime.sudog 结构体的指针；
2. 调用 runtime.memmove 将源栈中的整片内存拷贝到新的栈中；
3. 调用 runtime.adjustctxt、runtime.adjustdefers 和 runtime.adjustpanics 调整剩余 Goroutine 相关数据结构的指针；

func copystack(gp *g, newsize uintptr) {
	...
	var adjinfo adjustinfo
	adjinfo.old = old
	adjinfo.delta = new.hi - old.hi // 计算新栈和旧栈之间内存地址差

	ncopy := used
	if !gp.activeStackChans {
		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)

	adjustctxt(gp, &adjinfo)
	adjustdefers(gp, &adjinfo)
	adjustpanics(gp, &adjinfo)

	gp.stack = new
	gp.stackguard0 = new.lo + _StackGuard
	gp.sched.sp = new.hi - used
	gp.stktopsp += adjinfo.delta
	...
	stackfree(old)
}

调整指向栈内存的指针都会调用 runtime.adjustpointer，该函数会利用 runtime.adjustinfo 计算的新栈和旧栈之间的内存地址差来调整指针。所有的指针都被调整后，我们就可以更新 Goroutine 的几个变量并通过 runtime.stackfree 释放原始栈的内存空间了。

栈缩容

runtime.shrinkstack 栈缩容时调用的函数：

func shrinkstack(gp *g) {
	...
	oldsize := gp.stack.hi - gp.stack.lo
	newsize := oldsize / 2
	if newsize < _FixedStack {
		return
	}
	avail := gp.stack.hi - gp.stack.lo
	if used := gp.stack.hi - gp.sched.sp + _StackLimit; used >= avail/4 {
		return
	}

	copystack(gp, newsize)
}

如果要触发栈的缩容，新栈的大小会是原始栈的一半，不过如果新栈的大小低于程序的最低限制 2KB，那么缩容的过程就会停止。

shrink-stacks

运行时只会在栈内存使用不足 1/4 时进行缩容，缩容也会调用扩容时使用的 runtime.copystack 开辟新的栈空间。

Reference

1. https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-stack-management/