Menu

Subscribe

golang 非协作式抢占

on go, go语言, go源码, 非协作式抢占

最近因为dlv里面有个bug，关于go1.14版本之后非协作式抢占扩大了调试状态下的一些协程问题。

于是就找了原始的提议看了看，恩，果然大部分都看不懂！！！

利用google/baidu式的翻译，手敲了一遍，并且存疑的地方都加了一点东西，算是给自己一点做个笔录吧，后面有理解更深的地方会更新一下自己的理解。

翻译笔录英文版本如链接

摘要

go 当前在编译器插入的函数序章中插入协作抢占点。在大多数情况下，这足以让golang开发人员忽略抢占细节，专注于编码清晰的并行代码，但是这种方式有着非常尖锐的问题，以至于我们一次又一次的看到它降低了开发人员的体验。当它出现错误时候，就会呈现出惊人的错误现象，导致未知的系统层面的延迟问题，甚至有时候会完全冻结（就是卡住不动的意思）。因为这个是存在于golang语言语义之外的语言实现问题，这些错误是非常令人吃惊的，并且非常难以调试。

@dr2chase已经投入了大量的精力在循环中建立协作抢占点的原型，这是解决这个问题的一种方法。然而，即使是复杂的方法也会导致在紧密循环（我理解就是死循环或者短时间无法跳出的循环）中无法接受的减速（这种情况，减速通常是不可接受的）。

我建议go的实现方式切换到非协作抢占式，这将允许goroutine在本质上可以在任何时刻被抢占，而不需要显示的抢占检查。这种方式可以解决延迟抢占的问题，并且可以实现运行时零开销。

非协作抢占式是一个具有一整套实现技术的概念。本文描述并推动了向非协作抢占式的转换，并且讨论了go中所有的实现非协作式抢占的共同关注点。具体的实现方式详见文本附属的次级提案。

背景

在go1.10之前（包括go1.10），go只在函数调用使用了安全点的协作抢占（即使这样，如果函数太小或者内联也不会有）。这意味着go只能在特定点进行，当前并发执行的goroutines切换。这样做的主要优点是编译器可以在这些安全点确保有用的不变量（这个不变量是指？？）。特别是，编译器确保所有安全点的所有本地垃圾收集根都是已知的，这对于精确的垃圾回收是至关重要的。它还可以确保没有寄存器在安全点上活动，这意味着go在运行时切换goroutines而不必保存和恢复一个大的寄存器集（其实这个意思就是，golang的协程切换就是一些普通的函数调用，大量的寄存器的保存恢复不需要手动去控制，它只依赖普通函数调用时候的寄存器变化，其中参数和返回值都是通过栈传递的。实际上 golang在协程切换的时候，只有 1. 与栈相关的SP和BP寄存器 2. PC寄存器 3. 用于保存函数闭包的上下文信息，dx寄存器 ）。

然而，在稀少安全点的地方，会导致大量的问题：

  1. 在生产代码中最常见的是，会延迟STW操作，例如启动和结束GC循环。这会增加STW延迟，并且在较大的核心计数器会显著影响吞吐量（例如，如果大量线程在运行时等待一个“落伍者”长时间被停住）（这个例子没有完全看懂，这里面的“落伍者”是啥意思？？）
  2. 这会延迟调度，阻止竞争goroutine及时执行。
  3. 这会延迟堆栈扫描，在运行时等待抢占点消耗CPU，并最终延迟GC终止，从而导致有效的STW，其中系统耗尽堆，无法分配goroutine。(没有完全懂？？)
  4. 在一些极端的例子中，会导致程序停止，例如当在 atomic load 上自旋的goroutine耗尽了负责设置该原子性的gorotinue时。这通常说明代码是错误的或者有缺陷的，但令人惊讶的是，这显然浪费了开发人员大量的调试时间。#543, #12553, #13546, #14561, #15442, #17174, #20793, #21053（我理解这块讲的是，生产代码会有一些内联的小函数，例如 #12553中for{test()}，虽然有函数调用，但是被内联了，所以gc在任何时间点里stop它）

这些问题阻碍了开发人员的生产力和生产效率，并使Go的用户接触到他们本来不必关心的实现细节。

协作循环抢占

@dr2chase 花费大量的精力去尝试使用协作循环抢占来解决问题。这个是运行时采用协作抢占的标准做法，其中编译器在flow graph的 back-edges插入抢占检查和安全点。这个极大程度上提高了抢占的质量，因为代码永远不会在没有 back-edges的情况下执行任意非常长的时间。（这个我理解，是在for循环的生成代码中也加入了协作抢占，其中对应代码在#7efd7bf）。

我们最新的循环抢占方法，我们称之为基于故障的抢占（fault-based preemption）,在x86 和 UNIX 平台（CL 43050）上的循环添加了一条指令，没有分支，也没有寄存器压力。尽管如此，geomean对一套大型基准测试的减速率为7.8%，少数异常值明显更差。即使与go1.9相比，由于一些改进，go1.9的减速只有1%，但是大多数基准测试都会出现一些减速，并且仍然存在显著的异常值。

基于故障的抢占（fault-based preemption）还有几个实现缺点。它不能针对特点的线程或者goroutine，所以对于堆栈扫描、参差不齐的屏障（这个是指写屏蔽吗？？）或常规的调度程序抢占来说，它是不匹配的。它也是“粘滞”的（就是置后的意思），因为在我们恢复所有循环之前，无法恢复任何循环，因此如果安全点发生在不安全的状态下（例如当运行时锁被持有时），安全点就不能简单地恢复。在非 x86 和 非 UNIX平台上，他需要更多的指令（和更多的开销）。最后，他会干扰调试器，调试器会假设错误的内存引用是停止程序的一个很好理性（就是说程序可能会停止程序）。由于一个内核错误，目前还不清楚它是否可以在OSX上的若干调试器下运行。

非协作抢占

非协作抢占发生在并行执行上下文之间切换，而无需显式的抢占检查或来自这些上下文的辅助。所有现代的桌面和服务器系统都使用这种方法在线程之间进行切换。如果没有这一点，一个行为不良（poorly-behaved）的应用程序可能会楔入整个系统，就像一个行为不良的goroutine当前如何楔入Go应用程序一样。这也是一个方便的抽象，隐藏了操作系统对有限数量的CPU进行时间复用（time-multiplexing）的事实，它让我们可以像有无限多个CPU一样进行编程。

操作系统调度器使用硬件中断支持将正在运行的线程切换到操作系统调度器中，这样可以保存该线程的状态，例如它的CPU寄存器，以便以后可以继续运行。在Go中，我们将使用操作系统支持来做同样的事情。在类UNIX的操作系统上，这可以使用信号来完成。

然而，由于GC的存在，Go 有着操作系统没有的要求：Go必须无论goroutine停在哪个位置，都能堆栈上找到活动指针（live pointers）。go中非协作抢占的大多数复杂性都源于此要求。

提议

我提议go通过发送 POSIX 信号（或者等效的OS机制）来停止正在运行的goroutine并捕获其CPU状态，从而实现非协作的goroutine抢占。如果goroutine在必须是GC原子（GC atomic）处中断，如“处理不安全点”（Handing unsafe-points）部分中所述的情况，那么运行时可以先简单地恢复goroutine并稍后再试。

实施Go的非协作抢占的关键困难点是在抢占的goroutine堆栈中查找活动指针（live pointer）。有许多方法可以做到这一点，这些在子提议（sub-proposals）中有详细介绍：

  • “安全点无处不在”(safe-points everywhere proposal) 的提议描述了一种实现，其中编译器几乎为每条指令都记录堆栈并注册映射。这允许运行时在任何地方暂停gorutine并找到GC根。
  • “保守的内帧（inner-frame）扫描 ”（conservative inner-frame scanning proposal ）提议了一种使用保守的GC技术在抢占的goroutine的最内层堆栈帧中查找指针的实现。无需任何额外的安全点元数据即可完成此操作。

处理非安全点

go中任何非协作式抢占的方式都必须处理与GC相关的原子性的代码序列（这个话怎么理解？？？），相对于GC安全点相比，我们称这些为“不安全点”。一些已知的情况是：

  1. 涉及unsafe.Pointer的表达式可以临时将其指向对象的唯一指针表示为uintptr。因此，当从unsafe.Pointer派生的uintptr处于活动状态时，必须将其认为是非安全点。同样的，我们必须将reflect.Value.Pointer，reflect.Value.UnsafeAddr和reflect.Value.InterfaceData识别为unsafe.Pointer到unintptr的转换。或者，如果编译器可以可靠地检测到此类uintptrs，则可以将其标记为指针，但是这样会有存在中间值可能无法标示合法指针的危险。
  2. 在写屏障中，在启动写屏障的检查和直接写入之间的位置一定不是安全点。例如，假设goroutine正在将指向B的指针写入对象A。如果发生了检查，则GC启动并扫描A，然后goroutine将B写入A并将所有对B的引用从其堆栈中删除，GC可能会失败标记B。（这个意思就是有A.B，当扫描A的时候，A还没有B的引用，然后刚好其他协程把A.B这个引用生成了，而此时扫描结束了）
  3. 在某些地方，编译器会生成可能超出分配末尾的临时指针，例如在切片和数组上的范围循环中。当这些指针处于活跃状态时，要么必须避免这些情况，要么就必须禁止安全点。

所有这些情况都必须已经避免了重大的重新排序，以避免在调用时候分裂（我理解这个是指栈分裂）。在内部，这是通过“mem”伪值实现的，该伪值必须顺序地遍历所有操作内存的SSA值。Mem也通过不允许重新排序进行遍历，甚至它们并不接触内存。例如，unsafe.Pointer和uintptr之间的转换是通过特殊的“Convert”操作完成的，该操作仅使用内存来限制重新排序。（所以排序到底是个啥？）

这些问题有几种可能的解决方案，其中一些可以组合使用：

  1. 我们可以标记不应包含抢占点的基本块。对于unsafe.Pointer的转换，我们将选择退出包含该转换的基本块。对于遵循unsafe.Pointer规则的代码，这应该足够了，但是它可能会破坏不正确的代码，如今一旦发生，就会变得难以调试（怎么翻译？？）。对于写屏障，这也是足够的。对于循环，这过于广泛，将需要拆分一些基本块。
  2. 对于unsafe.Pointer转换，我们可以简单地选择退出所有从unsafe.Pointer转换为uintptr的函数。这将很容易实现，甚至可以使损坏的不安全代码像现在一样工作，但是可能会产生广泛的影响，尤其在存在内联的情况下。
  3. 1和2的简单组合是选择退出从unsafe.Pointer到uintptr转换到函数调用（今天是安全点）的所有基本块。
  4. 对于范围循环，编译器可以对他们进行不同的编译，以使她从不构造越界指针（请参见下文）。
  5. 一个更精确，更通用的方法（由于@cherrymui）将是创建新的SSA操作来“taint”和“untaint”内存。“taint”操作将需要一个内存并返回一个新的“taint”的内存。该“taint”将流向本身具有“tainted”值的任何值。“untaint"操作需要一个值和一个内存，并返回一个“untaint”的值和未污染的mem。在活动性分析期间，无论“taint”是否存活，安全点都是被禁用的。这可能最精确的解决方案，并且即使不正确地使用不安全的工作也可能正常运行，但是需要复杂的实现。

更广泛地说，值得考虑让编译器检查不安全，使用指针的代码并主动拒绝不遵循“允许模式”的代码。这可以作为一个简单的类型系统来实现，该系统可以将类似与指针的uintptr与数字unintr区分开。但这超出了本提议的范围。

范围循环

对于Go1.10，范围循环被编译如下：

for i, x := range s { b }  
  ⇓
for i, _n, _p := 0, len(s), &s[0]; i < _n; i, _p = i+1, _p + unsafe.Sizeof(s[0]) { b }  
  ⇓
i, _n, _p := 0, len(s), &s[0]  
goto cond  
body:  
{ b }
i, _p = i+1, _p + unsafe.Sizeof(s[0])  
cond:  
if i < _n { goto body } else { goto end }  
end:

降低（lowering，我理解是递归下降）的问题是_p可能会在循环终止之前临时指向分配结束。当前这是安全的，因为 _p的值处于活动状态时永远不会有安全点（握草，啥个意思？？？）。

这种“降低做法”（lowering，我理解是递归下降）要求编译器将增量和条件块标记为不安全点。但是如果body过小，可能会导致安全点很少。它还需要为增量创建一个单独的块，当前通常将其附加到主体的末尾。分隔这些块会抑制重新排序的机会。（所以跟排序到底关系？？？）

为了准备非协作抢占，Go1.11开始按照如下方式编译范围循环，以避免产生过头（past-the-end）的指针：

i, _n, _p := 0, len(s), &s[0]  
if i >= _n { goto end } else { goto body }  
top:  
_p += unsafe.Sizeof(s[0])  
body:  
{ b }
i++  
if i >= _n { goto end } else { goto top }  
end:

这允许在循环中的任何地方使用安全点。与原始循环编译相比，它生成的代码略多，但是执行条件分支指针(n + 1)的数量相同，并且SSA基本块（basic blocks）相同。

这种“降低做法”（lowering，我理解是递归下降）确实使“边界检查消除”（bounds-check elimination）变得复杂。在Go1.10中，“边界检查消除”（bounds-check elimination） 知道 body 中的 i < _n，因为这个body块受cond块控制支配。但是在新的“下降过程”（我理解是递归下降），推到这个事实是需要检测 body 的两条 路径上的 i <_n，因此在 body中为真。

运行时安全点

除了生成的代码外，通常不会将运行时编写为可任意抢占，而且很多地方都不能被抢占。因此，我们可能会在运行时默认禁用安全点。但是调用时除外（当前发生的位置）。

尽管对于大多数运行时而言，这机会没有什么缺点，甚至运行时的某些部分可能会从非协作抢占中收益，例如像 memmove这样的内存功能。非协作抢占对抢占不减慢的普通case及其友好（原文大概是这个意思，直接翻译完全不会），因为我们只需要标记它们的寄存器映射（对于memmove之类的函数，由于所有指针已经受参数保护了，因此通常为空）。

随着时间的流逝，我们可能对于运行时有着更多的选择。

不安全的标准库代码

windows的系统调用库包含大量的不遵循unsafe.Pointer规则的unsafe.Pointer转换。它广泛地对于安全点的行为、存活性以及何时发生堆栈移动做出了不稳定的假设。这个部分可能需要进行彻底的审核，或者像运行时一样需要选择性退出。

也许更麻烦的是某些windows syscall程序包类型具有uintptr字段，这些字段实际上是指针，因此迫使调用者执行不安全的指针转换。例如，参考 #21376。(这个例子非常棒，个人建议可以直接看@zhangyoufu 指出来的问题)

确保非安全点的进度

我们建议仅在goroutine在不安全的点被中断时放弃并稍后重试。这样做的危险之一是，在紧缩循环（tight loops）中。然而，大量情况下，此方法还有更复杂的替代方法。

对于运行时或者没有安全点（例如汇编）的函数的中断，信号处理程序可以展开堆栈，会插入一个蹦床（trampoline），该蹦床处于下一次返回具有安全点元数据的函数位置（好绕！！！）。接着，运行时可以让goroutine继续运行，而蹦床（trampoline）将尽快将其暂停。

对于写屏障和unsafe.Pointer指针序列（这个“序列”我理解就是汇编指令的意思），编译器可以在序列末尾插入一个廉价的显示抢占检查。例如，运行时可以修改一些在序列末尾检查的寄存器，并让线程继续执行。在写屏障序列中，这甚至可能是写屏障标志被加载到的寄存器，并且编译器可以在序列末尾插入一个简单的寄存器测试和条件分支。为了一进一步缩小序列，运行时可以将stop函数的地址放入该寄存器中，因此stop序列只是一个寄存器调用和一个跳转。

此检查的替代方法包括正向和反向模拟。正向模拟非常棘手，因为编译器仅生成运行时知道如何模拟的操作，这个过程要异常小心。如果编译器始终可以生成可重新启动的序列（简单地往回移动 PC 到写屏障 flag 检查处），那么逆向模拟就很容易完成；但是如果序列中有大量写操作或者更复杂的写入（例如DUFFCOPY），那么反向模拟很快就会变得复杂。

其他注意事项

所有提议的非协作抢占方法都包括通过向其发出OS信号来停止正在运行的goroutine。本节讨论了这种情况的一般后果。

windows支持。与基于故障（fault-based）的循环抢占不同，在windows中很容易支持信号抢占，因为它提供了SuspendThread和GetThreadContext，这使得获取线程的寄存器集变得很简单。

选择一个信号。我们必须选择一个不太可能干扰现有信号使用或者调试器的信号。没有完美的选择，但是有一些启发式方法。

  1. 默认情况下，它应当是能被调试器传递的信号。在linux上，是SIGALRM，SIGURG，SIGCHILD，SIGIO，SIGVTALRM，SIGPROF和SIGWINCH，已经一些glibc内部信号。
  2. libc不应在混合GO/C二进制文件内部使用它，因为libc可能会认为它自己是唯一可以处理这些信号的工具（only thing 应该翻译成啥，比较好，“工具”好像也不太好）。例如 SIGCANCEL或SIGSETID。
  3. 应该选择一个可以虚假（spuriously）发生而且不会产生后果的信号。例如，SIGALRM是一个很错误的选择，因为这个信号处理程序无法判断它是否是由真实进程警报（alarm）引起的（可以说这意味着信号已经损坏了，但是我离题了）。SIGUSR1和SIGUSR2也很糟糕，因为应用程序经常以有意义的方式使用它们。
  4. 我们需要处理没有实时信号的平台（例如macOS），所以这些都是要被淘汰的选项。

我们使用 SIGURG 因为它满足所有这些条件，极大概率上不会因为其“真实”（real）含义而被其他应用程序使用（同样还有一个原因是因为外带数据基本上未被使用，并且因为SIGURG不会报告哪个套接字具有条件，这些使其变得毫无用处），即便这样，该应用程序也必须准备接受虚假的SIGURG。SIGIO也不是一个不好，但可能更可以用于真实（real）。

调度程序抢占。这种机制非常适合临时抢占，在抢占之后，相同的goroutine将继续执行，因为我们不需要保存完整的寄存器状态，并且可以依赖现有的信号返回路径来恢复完整的寄存器状态。这适用于所有与GC相关的抢占，但不适用于调度程序执行的永久抢占。但是，我们仍然可以在此机制上构建。例如，由于大多时候goroutine具有自我抢占功能，我们只需要在不常见的情况下保存完整的信号状态，因此g可以包含一个指向完整保存状态的指针，该指针仅在抢占之后使用。恢复完整的信号状态可以通过编写跟架构相关（architecture-dependent）的代码来恢复完整的寄存器集（增强runtime.gogo功能），或者通过自信令，在所需要的上下文中进行交换，然后操作系统还原完整的寄存器集。

定位与恢复。与基于故障的循环抢占相比，信号抢占可以针对特定线程，并且可以立即恢复。以线程为目标与以goroutine为目标的合作式抢占有所不同。但是，在许多情况下，实际上会更好，因为针对goroutine进行抢占是不明智的，因此需要重试循环，这可能会大大增加STW时间。利用此优势进行堆栈扫描讲需要对我们跟踪GC跟的方式进行一些重组，但是结果应消除我们当前使用的阻塞重试循环。

非指针指针。这有可能暴露unsafe.Pointer对临时存储非指针的不正确使用。此类使用明显违反了unsafe.Pointer规则，但可能会发生（特别是在使用cgo的代码中）。

备选方案

单步执行

相比较努力让程序可以停在在任意指令，编译器可以在只在后端（back-edges）就为安全点发出元数据，而运行时可以使用硬件单补支持线程推到一个安全点（或者编译器提供分支以达到安全点的位置，例如当前循环抢占方法）。这行得通（有点令人惊讶），但是这彻底迷惑了调试器，因为调试器和操作系统都假设调试器拥有单步调试，而不是进程本身。这也就要求编译器为这些安全点提供寄存器刷新存根，这增加了代码大小（并因此增加了指令高速缓存压力）以及堆栈大小，这与协作循环抢占非常类似。但是与协作循环抢占不同，这种方法不会影响主线代码的大小或者性能。

跳转重写

通过在中断点之后重写下一条安全点跳转指令以跳转到抢占路径并且像往常一样执行恢复执行，可以解决单补执行的问题。为了简化次过程，编译器可以留出足够的空间（通过填充NOP)，因此仅需要修改跳转目标。

这种方式具有可修改代码的缺点。这是一种隐患，他会破坏 .text 页面共享，并且在IOS上是完全不被允许的。他也不能以单个goroutine为目标（因为另一个goroutine可能正在执行相同的代码），并且可能与其他内核上的并发执行发生奇怪的交互。

离线执行

同样，但是不需要修改现有.text文本的另一种选择是离线执行。在这种方法中，信号处理程序将指令流从中断点转移到下一个安全点跳转到临时缓冲区中，对其进行修补以最终跳到运行时，然后按此重新定位的顺序恢复执行。

这可以通过单补执行和跳转重新解决大多数问题，但是实现起来非常复杂，并且每一个平台都需要大量的实现工作。IOS上也不允许使用。

这种方法有先例。例如，当linux uprobes注入INT 3 时，它将重写的指令重新定位到“执行离线”区域中，从而避免了从INT3指令恢复时常见的问题。考虑到x86指令编码的复杂性，简化了实现，但是依然非常复杂。