Go GC 栈对象与栈跟踪

GC扫描栈

问题的关键在于这段代码：

t := T{...}
p := &t
for {
   if … { p = … }
}

编译器决定在栈上分配 T，并且因为编译器无法跟踪其地址结束的位置，所以编译器保守地决定 t 始终是存活的。

但是在 for 循环中，当 p 被赋值时，t 变成死亡的。
所以在 p 被重新分配之后，t 中的任何指针都可能保持一个它不应该保持的对象存活。

我们将在栈上调用其地址被 “栈对象” 占用的变量，目标是仅在栈对象中的数据真实存活时扫描栈对象，即如果对象再次直接引用（如，t.x）或间接引用（如，p.x）。

我们开始像往常一样扫描一个栈，从最低（最新）的栈帧开始，一直向上。
我们使用指针位图来查找每个栈帧中的所有存活的指针。
通常，栈对象的指针不会标记为存活（但请参见下文）。
所有指向堆的指针都像往常一样被标记，任何指向栈的指针都被忽略(目前)。
对于遇到的每一帧，我们查看该帧是否有栈对象。
对于该帧中的每个栈对象，我们将其添加到栈对象列表中。

如果我们到达栈顶部并找不到栈对象，那么就结束了。

如果我们确实找到了一些栈对象，我们必须再次扫描栈。

首先，我们将栈对象组织成一个数据结构，该结构提供按地址快速查找的功能，可能是一个二叉树。由于我们可以按地址顺序枚举栈对象，所以应该很容易使用它们的地址作为 key 来生成二叉树（在 O(n) 时间内）。

然后我们再次扫描栈，只查找指向栈的指针。
对于任何这样的指针，我们在二叉树中查找它们，看看它们是否指向任何栈对象。
如果是，我们将栈对象标记为存活（如果我们还没有这样做），并将其放入正在扫描的工作列表中。当我们完成栈扫描时，我们现在在工作列表中有了栈对象的根集（root set）。
然后，我们不断从工作列表中弹出一个对象并扫描它（可能将堆对象或其他栈对象标记为存活），直到工作列表为空。

我们可以为每个栈对象分配相邻的空间来使用这个算法。我们称之为栈对象“header”。
header 可能包含二叉树的左右指针，一个标记位和用于单链表工作队列的指针。
header 有一些空间开销，但是它应该很小，并且可以自由分配，因为它只是使栈帧更大一点。
header 只需要在第一次扫描是找到栈对象时才初始化。因此我们可以在正常执行期间将垃圾留在那里。

记录栈对象

我们在funcdata中为函数保留了一个额外的映射，该函数包含帧中每个栈对象的帧偏移，大小和指针映射的列表。

请注意，只需要记录具有指针的栈对象。

_FUNCDATA_StackObjects = 4

堆栈对象相对较少，因此栈对象数据的编码不是很关键。
我们可以像这样编码栈对象funcdata：

（偏移大小（isptr）*）*

其中，每个对象在帧中编码它的起始偏移量、它的大小以及该对象中每个指针 slot 的size/ptrSize 0/1项。

含糊不清的存活对象（ambiguously live objects）

有了这种新机制，我们就可以在当前编译器中为含糊不清的存活对象去掉所有代码。
我们只需要在存活的 ptr 位图中标记那些通过直接访问（而不是通过指针）存活的指针。
我们的新机制包含以前用于跟踪栈对象的逻辑，该逻辑是：存活只是因为指向它们的指针可能是存活的。

其他说明

对象可以作为栈对象被列出，并在存活的 ptr 位图中被标记。
例如：

t := T{}
p := &t
f()
println(t.a)
g()
println(p.b)

在调用 f 时，t 中的指针将在 ptr 位图中标记为存活的（可能只标记 t 的 a 字段）。在调用 g 时不会。

清除

清扫器（sweeper）由两种不同的算法组成：

• 对象回收器查找和释放 span 中未标记的 slots。
  如果没有标记任何对象，它可以释放整个 span，但这不是它的目标。
  可以通过 mcentral.cacheSpan（for mcentral spans）同步驱动，也可以通过 mheap_.sweepSpans 中所有正在使用的 spans 列表中的 sweepone 异步驱动。

• span 回收器查找不包含标记对象的 span，并释放整个 span。
  这是一个单独的算法，因为释放整个 spans 对于对象回收器来说是最困难的任务，但是在分配新 spans 时非常关键。
  这个的入口点是 mheap_.reclaim，它是由堆区域中的页面标记位图的顺序扫描驱动的。

两种算法最终都调用 mspan.sweep，它扫描单个堆 span。

栈对象和栈跟踪

堆跟踪解决了确定栈的哪些部分是存活的并且应该被扫描的问题。它作为扫描单个 goroutine 栈的一部分运行。

通常，静态地确定堆栈的哪些部分是存活的很容易，因为用户代码对栈对象有显式的引用（读和写）。
编译器可以进行简单的数据流分析，以确定代码中每个点的栈变量的活跃性。
有关该分析，请参阅：$GOROOT/src/cmd/compile/internal/gc/plive.go

但是，当我们获取堆栈变量的地址时，确定该变量是否仍然存活就不太清楚了。
我们仍然可以查找静态访问，但是通过指向变量的指针进行的访问通常很难静态跟踪。
该指针可以在栈上的函数之间传递，有条件地保留等。

相反，我们将动态跟踪指向栈变量的指针。
所有指向栈分配的变量的指针本身都将位于栈的某个位置（或者在相关位置，如 defer），因此我们可以有效地找到它们。

栈跟踪被组织为迷你的垃圾收集跟踪通道。这个垃圾收集中的对象是栈上的所有变量，这些变量的地址已被占用，它们本身包含一个指针。我们称这些变量为 “栈对象”。

我们首先确定堆栈上的所有栈对象和可能指向栈的所有静态存活指针。然后我们处理每个指针，看它是否指向栈对象。如果是，我们扫描该栈对象。栈对象可能包含指向堆的指针，在这种情况下，这些指针将被传递给 主 GC。栈对象也可能包含指向栈的指针，在这种情况下，我们将它们添加到栈指针集中。

一旦我们处理完所有指针（包括我们在处理过程中添加的指针），我们就找到了所有存活的栈对象。
任何死亡的栈对象都不会被扫描，并且它们的内容也不会保持堆对象存活。与 主 GC 不同，我们无法清除死亡的栈对象；它们一直处于垂死状态，直到包含它们的栈帧被弹出。

栈可能如下所示：

 +----------+
 | foo()    |
 | +------+ |
 | |  A   | | <---\
 | +------+ |     |
 |          |     |
 | +------+ |     |
 | |  B   | |     |
 | +------+ |     |
 |          |     |
 +----------+     |
 | bar()    |     |
 | +------+ |     |
 | |  C   | | <-\ |
 | +----|-+ |   | |
 |      |   |   | |
 | +----v-+ |   | |
 | |  D  ---------/
 | +------+ |   |
 |          |   |
 +----------+   |
 | baz()    |   |
 | +------+ |   |
 | |  E  -------/
 | +------+ |
 |      ^   |
 | F: --/   |
 |          |
 +----------+

foo() 调用 bar() 调用 baz()。每个方法在栈上都有一个桢。

foo() 有栈对象 A 和 B。

bar() 有栈对象 C 和 D, C 指向 D, D 指向 A。

baz() 有一个栈对象 E 指向 C，一个局部变量 F 指向 E。

从局部变量 F 中的指针开始，我们最终将扫描所有 E、C、D 和 A （按照这个顺序）。

B 不会被扫描，因为没有指向它的存活指针。

如果 B 也是静态死的（这意味着 foo() 在调用 bar() 之后再也不会访问 B），那么 B 指向堆的指针就不被认为是存活的。

tips：栈对象与栈扫描

// stackObject 表示栈上的一个变量，该变量的地址已被占用。
//
//go:notinheap
type stackObject struct {
    off   uint32       // stack.lo 之上的偏移
    size  uint32       // 对象的大小
    typ   *_type       // 类型信息（对于 ptr/nonptr 位），如果对象已被扫描，则为 nil
    left  *stackObject // 低地址对象
    right *stackObject // 高地址对象
}

// 如上可以看出栈对象是一个双向链表
// 参见：go1.12beta2/src/runtime/mgcstack.go

---

// scanstack 扫描 goroutine 的栈，标灰所有在该栈上找到的指针。
//
// scanstack 被标记为 go:systemstack，因为它在使用 workbuf 时不能被抢占。
//
//go:nowritebarrier
//go:systemstack
func scanstack(gp *g, gcw *gcWork) {
......
    var state stackScanState
    state.stack = gp.stack
......
    // 查找并且扫描所有可达的栈对象。
    // buildIndex 将 state.root 初始化为二叉搜索树。
    // 应该在所有 addObject 调用之后但在调用 findObject 之前调用它。
    // 使用栈对象数组构造了一颗二叉查找树。
    state.buildIndex()
    for {

        // 删除并返回指向堆栈对象的潜在指针。
        // 如果没有更多可用指针，则返回0。
        p := state.getPtr()
        if p == 0 {
            break
         }

        // findObject 返回包含地址 a 的堆栈对象（如果有）
        obj := state.findObject(p)
        if obj == nil {
            continue
         }
......
     }
......
}

// 参见：go1.12beta2/src/runtime/mgcmark.go