[翻译] Coroutine Theory

Posted on

最近在研习C++协程的一些用法，翻到folly::coro作者 Lewis Baker 的几篇文章，都是基于C++20协程，讲解比较详细，翻译如下。
第一篇主要介绍了一下内容，并有配图说明了协程调用的过程：

在这个系列中，我会覆盖C++协程基础原理，以及如何应用到更高层次的抽象，例如在cppcoro库中所提供的。
(注1：Lewis Baker同时也是流行库cppcoro的作者；注2：C++20的协程只是提供了协程源语，要真正用起来，还需要很多封装，例如调度器)

本篇会描述函数与协程之间的区别，以及介绍所支持操作的原理。本篇目标是给读者引入C++协程的基础概念。

协程既是函数，函数又是协程

协程是一类允许运行中挂起以及恢复的函数。
在进一步解释细节前我们来看一下普通的C++函数。

“普通”函数

普通函数可以认为包含两个操作：Call 以及 Return （注意，这里把”抛异常“也包含在广义Return中）。

操作Call创建了一个栈帧，把调用函数挂起，然后转移运行权到新函数的起始。

操作Return把返回值传递给调用者，析构掉栈帧，然后恢复调用者的执行到刚刚调用函数之后。

栈帧

所以，栈帧到底是什么？

栈帧可以认为是一段内存，包含了函数特定调用的当前状态。这个状态包含了传入的参数以及所有局部变量。

对于普通函数，栈帧同时包括了返回地址，就是指示往上转移返回函数的地址，也是调用者函数的栈帧地址。可以认为是描述了函数调用的延续，也就是描述了当前函数完成后应该继续调用哪个函数。

在普通函数中，所有的栈帧都有严格嵌套的生命周期。严格嵌套意味着所有的内存分配，以及每次函数栈帧的析构都可以使用非常高效的栈结构。

在栈结构上分配的栈帧通常被称为栈帧。

栈结构非常常用大部分CPU架构有专门的寄存器来保存栈顶指针（例如，X64中是寄存器rsp）。

对于新栈帧的空间分配，只需要给寄存器增加一个栈大小即可。而通过减少寄存器大小即可完成栈帧的析构。

调用操作 “Call”

当一个函数调用另外一个函数，函数本身就需要为自己的挂起做准备。

“挂起”操作一般包括把当前在CPU寄存器中的数据都保存到内存中，以便于在函数恢复执行时可以恢复这些变量。基于函数的调用约定，调用者和被调者可以协调由谁来保存寄存器值，但还是可以把这些动作视为Call动作的一部分。

调用者同时会把传入函数的参数保存到函数可以访问的新栈帧。

最终，调用者将恢复点的地址写入新的栈帧，并转移执行权给调用的函数。

在X86/X64体系结构中，最后一步有单独指令”call”，即会将下一条指令写入栈上，增加栈寄存器一个地址长度，然后跳到指令中的地址。

返回操作 “Return”

当一个函数通过”return”关键字返回时，函数首先保存返回值到调用者可以访问的地方。这个地方可以是调用者的栈帧或者当前函数的栈帧（在栈帧边界附近的参数和返回值的区别会变得模糊）。

然后函数通过以下步骤销毁栈帧：

  • 析构所有在返回点生命到期的局部变量
  • 析构所有参数对象
  • 释放栈帧使用的内存

最后，再通过以下步骤恢复调用者的执行：

  • 设置栈寄存器指向调用者的栈帧，且恢复可能被当前函数修改过的寄存器
  • 跳到保存在”Call”指令中的调用者的恢复点

注意到通过”Call”操作，一些调用协定会把”Return”操作的任务拆分给调用者和被调者。

协程

协程，概括来说就是把”Call”和”Return”操作分解为3个额外步骤：挂起Suspend、恢复Resume以及销毁Destroy。

挂起操作是指，协程挂起在函数当前的执行位置，并在不销毁栈帧的情况下转移执行权给调用者或者恢复者。生命周期内的任何对象会在协程执行挂起后依旧保持存活。

注意到，类似于函数的返回操作，协程只能在内部定义好的位置挂起。

恢复操作是指，恢复被挂起协程的执行到之前挂起的位置。这会重新激活协程的栈帧。

销毁操作是指，直接销毁协程栈帧而需恢复执行。任何在挂起时保持生命周期的对象都会被销毁。栈帧使用的内存会被释放。

协程栈帧

因为协程的栈帧可以在任意挂起而不销毁栈帧，我们就无法保证栈帧的生命周期是严格嵌套的。也就意味着栈帧不能以通用的方式在栈上分配，或者说应该保存到堆上。

C++ Coroutines标准中提供了一些机制允许协程帧分配在调用者的栈帧上，只要编译器能够确认协程的生命周期是严格嵌套在调用者之内的。这样只要有足够聪明的编译器就可以避免很多情况的堆分配。

协程中，栈帧的一部分需要保留到挂起之后，一部分只需要保留在执行期间。例如变量生命周期不跨过任何协程挂起点的就可以考虑保存在栈上。

逻辑上，我们就可以把协程栈帧分成两部分：协程组(coroutine frame)和栈组(stack frame)。

协程组包括那些协程挂起后依旧要保持的部分，栈组只包括仅需要在协程运行期间存活的部分，也就是协程执行中存在，协程挂起转移时就释放。

挂起操作 Suspend

协程的挂起操作，是允许协程在函数中间挂起执行，并转移执行权给协程调用者或者恢复者。

协程函数体中有特定的点作为挂起点。在C++协程标准中，挂起点通过使用关键字co_await和co_yield来指示。

当协程执行到挂起点之一时，首先会为后续恢复做如下准备：

  • 确保寄存器值都已经写到协程帧上
  • 协程栈上添加一个值来指示协程在哪个位置挂起了。这就提供了之后恢复执行的依据，或者让销毁操作可以确定哪些值还存活需要销毁。

一旦协程做好了恢复准备，协程就可以认为是挂起了。

协程在转移执行权给调用者/恢复者之前，还有机会执行一些额外的逻辑。额外的逻辑拥有访问之后用来恢复或者销毁的协程栈句柄的能力。

协程进入挂起之后执行额外逻辑的能力允许协程被调度恢复而不需要同步操作，否则的话协程被调度恢复优于进入挂起状态时就需要同步，因为协程挂起和恢复可能会有竞争。后面的博客会进一步解释这部分。

然后协程可以选择立即恢复/继续执行，或者选择转移执行权到调用者/恢复者。

如果执行权转移到调用者/恢复者，协程栈中的栈组部分就会释放且从栈中弹出。

恢复操作 Resume

恢复操作可以在当前处于挂起状态的协程上调用。

当一个函数要恢复协程时，需要有效地调用(Call)到函数特定中间执行点。恢复者通过在提供给对应挂起方法的协程栈上调用void resume()来指示恢复这个特定调用。

就像正常函数调用，执行resume()后在转移执行权之前，会分配新的栈帧，且保存调用者的返回地址。

然而，执行点会转移到函数上一次挂起点，而不是函数的开始。这是通过从协程栈中加载恢复点并跳转。

当协程在这次resume()中运行到下一个挂起点或者执行到结束，会返回并恢复执行给调用函数。

销毁操作 Destroy

销毁操作，是指在不恢复协程执行下销毁协程栈。

这个操作仅可以在挂起状态的协程上执行。

销毁操作和恢复操作的行为大体相似，主要是重新激活协程栈帧，包括分配新的栈帧以及保存销毁操作调用者的返回地址。

不同于转移执行权到协程上一次的挂起点，而是转移到另外的代码路径，并且先去调用在协程挂起点还存活的局部变量的析构以及释放协程栈使用的内存。

和恢复类似，销毁操作通过特定的操作来指示销毁动作，通过调用提供给挂起方法的协程栈上的void destroy()方法实现。

协程的调用操作 call

协程的调用操作和普通函数的调用很相似。事实上，从调用者来说没有区别。

然而不同于函数结束后返回调用者，协程内的调用操作在协程执行到第一个挂起点时即会恢复给调用者执行。

当在协程上执行调用操作，调用者会分配一个新的栈帧，将参数和返回地址写入栈帧，并转移执行权给协程。这和调用一个普通函数完全一致。

协程做的第一件事是然后在堆上分配一个协程栈，并拷贝或者移动栈帧上的参数到协程栈，以便于参数的生命周期扩展到第一个挂起点以外。

协程的返回操作 Return

协程的返回动作和普通函数有一点区别。

当协程执行到return语句（C++协程中是co_return）时，会把返回值保存到一个地方（具体什么地方可以由协程决定），然后析构存活中的局部变量（不包括参数）。

协程然后就有机会在转移执行权到调用者/恢复者前，执行一些额外的逻辑。

这额外的逻辑可以包括传递(原词是publish)返回值，或者恢复另外一个等待这个结果的协程。这完全是可定制的。

协程再然后就会执行挂起操作（保持协程存活），或者销毁动作（销毁协程栈帧）。

执行权就会转移到调用者/恢复者，具体取决于挂起还是销毁语义，以及弹出栈帧中属于栈上的部分。

这里比较重要的是，返回值传递给返回(Return)操作和从调用(Call)中返回时不一样的，对于调用者，返回操作的执行要远落后于初始调用操作。

一些图例

为了更好的理解协程被调用、挂起以及恢复时的概念，通过一组例图来说明。

假设我们有一个函数（或者协程） f() 调用了一个协程x(int a)。

在调用之前，当前情形如下：

STACK                     REGISTERS               HEAP

                          +------+
+---------------+ <------ | rsp  |
|  f()          |         +------+
+---------------+
| ...           |
|               |

当x(42)被调用，这里首先和普通函数一样，会为x()创建栈帧。

STACK                     REGISTERS               HEAP
+----------------+ <-+
|  x()           |   |
| a  = 42        |   |
| ret= f()+0x123 |   |    +------+
+----------------+   +--- | rsp  |
|  f()           |        +------+
+----------------+
| ...            |
|                |

然后一旦协程x()从对上分配到了协程栈，且复制/移动了参数到协程栈，就会最终得到如下的例图。注意到通常编译器会保存协程栈地址到栈指针上单独的寄存器中（例如，MSVC会保存到rbp寄存器）。

STACK                     REGISTERS               HEAP
+----------------+ <-+
|  x()           |   |
| a  = 42        |   |                   +-->  +-----------+
| ret= f()+0x123 |   |    +------+       |     |  x()      |
+----------------+   +--- | rsp  |       |     | a =  42   |
|  f()           |        +------+       |     +-----------+
+----------------+        | rbp  | ------+
| ...            |        +------+
|                |

如果协程x()然后调用了另一个普通函数g()，会变成如下情况。

STACK                     REGISTERS               HEAP
+----------------+ <-+
|  g()           |   |
| ret= x()+0x45  |   |
+----------------+   |
|  x()           |   |
| coroframe      | --|-------------------+
| a  = 42        |   |                   +-->  +-----------+
| ret= f()+0x123 |   |    +------+             |  x()      |
+----------------+   +--- | rsp  |             | a =  42   |
|  f()           |        +------+             +-----------+
+----------------+        | rbp  |
| ...            |        +------+
|                |

当g()返回时，会销毁自己的栈帧，并恢复x()的栈帧。假设说我们把g()的返回值保存到了存储在协程栈上的局部变量b中。

STACK                     REGISTERS               HEAP
+----------------+ <-+
|  x()           |   |
| a  = 42        |   |                   +-->  +-----------+
| ret= f()+0x123 |   |    +------+       |     |  x()      |
+----------------+   +--- | rsp  |       |     | a =  42   |
|  f()           |        +------+       |     | b = 789   |
+----------------+        | rbp  | ------+     +-----------+
| ...            |        +------+
|                |

如果x()现在运行到了一个挂起点，挂起执行且不销毁栈帧，然后执行转移给f()。

这也就导致了x()的部分栈帧从栈上弹出了，且同时把协程栈保留在了堆上。当协程第一次挂起时，会有一个返回值返回给调用者。该返回值通常为一个指向处于挂起状态且可以恢复的协程栈的句柄。在x()挂起时，同时存储了x()的恢复点地址在协程栈（称为返回点为RP）。

STACK                     REGISTERS               HEAP
                                        +----> +-----------+
                          +------+      |      |  x()      |
+----------------+ <----- | rsp  |      |      | a =  42   |
|  f()           |        +------+      |      | b = 789   |
| handle     ----|---+    | rbp  |      |      | RP=x()+99 |
| ...            |   |    +------+      |      +-----------+
|                |   |                  |
|                |   +------------------+

这个句柄可以被当做普通纸在函数间传递。在之后的时刻，可以在另外一个调用栈，甚至另外一个线程上，会被（例如h()）恢复协程执行。例如当一个异步I/O操作完成时。

恢复协程的函数会调用void resume(handle)方法来恢复协程的执行。对于调用者，这就类似于调用有一个参数且返回值为void的函数一样。

这个操作会创建一个新的栈帧，记录了调用者到resume()的返回地址，并通过把加载协程栈中的寄存器来激活x()的协程栈，恢复到存储在协程栈中的恢复点。

STACK                     REGISTERS               HEAP
+----------------+ <-+
|  x()           |   |                   +-->  +-----------+
| ret= h()+0x87  |   |    +------+       |     |  x()      |
+----------------+   +--- | rsp  |       |     | a =  42   |
|  h()           |        +------+       |     | b = 789   |
| handle         |        | rbp  | ------+     +-----------+
+----------------+        +------+
| ...            |
|                |

总结

这里我把协程归纳为拥有”Suspend”,”Resume”,”Destroy”三个额外操作，以及额外”Call”和”Return”动作的一类函数。

我希望这能提供一个有用的框架性思路来理解协程以及对应的控制流。

下一章会梳理C++协程标准的语言扩展，以及解释编译器如何转义协程中的代码。