协程理论(译)

本篇是 C++ 协程规范系列文章的第一篇,描述了函数与协程之间的区别,并简要介绍了它们支持的操作

本文译自 Coroutine Theory | Asymmetric Transfer

协程即函数,函数即协程

协程是对函数的一种泛化,允许函数被挂起,并在之后恢复执行。

在详细地解释这意味着什么之前,我们先来回顾一个“普通”的 C++ 函数是如何工作的。

“普通”函数

一个普通的函数可以看作有两个操作:调用返回(注意,在广义上我将“抛出异常”这一行为归类为返回操作)。

  • 调用操作创建一个激活帧(activation frame),暂停当前函数的执行,并将执行权转移到被调用函数的起始处。
  • 返回操作则将返回值传递给调用者,销毁激活帧,然后从调用该函数的调用点之后恢复执行。

让我们更深入地分析这些语义。

激活帧(Activation Frames)

所以什么是“激活帧”呢?激活帧可以看作是存储特定函数调用的当前状态的内存块,此状态包括了传递给函数的参数值和局部变量值。

对于“普通”函数,激活帧还包括了返回地址(即函数返回后需要跳转执行的指令地址),以及调用该函数的激活帧的地址。你可以将这些信息看作是对函数调用“延续”(continuation)的描述。即,它们描述了当该函数完成时,应当在哪个函数的哪次调用的哪个位置继续执行。

对于“普通”函数,所有激活帧的生命周期都是严格嵌套的,这种严格嵌套使得内存管理可以使用一种高效的数据结构来分配和释放每次函数调用的激活帧,这种数据结构通常被称为“栈”(stack)。

当一个激活帧被分配到这种栈数据结构上时,它通常被称为“栈帧”。

这种栈数据结构非常常见,几乎所有的 CPU 架构都有专门的寄存器用来保存指向栈顶的指针(例如,在 X86 架构中是 rsp 寄存器)。

要为新的激活帧分配空间,只需将该寄存器增加一个帧大小,相对的,要释放激活帧的空间,只需将该寄存器减少一个帧大小。

调用操作(Call Operation)

当一个函数调用另一个函数时,调用者必须先为自身的挂起做好准备。

这个“挂起”步骤通常涉及将当前存储在 CPU 寄存器中的值保存到内存,以便在函数恢复执行时(如果需要)恢复这些值。根据函数的调用约定,调用者和被调用者可能需要协作来决定由谁保存这些寄存器的值,但你仍然可以将这些操作视为调用操作的一部分。

调用者还会将传递给被调用函数的参数值存储到新的激活帧中,以便该函数可以访问它们。

最后,调用者将自身的恢复点地址写入新的激活帧,并将执行权转移到被调用函数的起始位置。

在 X86/X64 架构中,这个最终操作有专门的指令,即 call 指令,它会将下一条指令的地址压入栈中,增大栈寄存器以适应地址大小,然后跳转到指令操作数指定的地址执行。

返回操作(Return Operation)

当一个函数通过 return 语句返回时,它首先会将返回值(如果有的话)存储在调用者可以访问到的位置,这可能是在调用者的激活帧中,也可能是在当前函数的激活帧中(对于跨越两个激活帧边界的参数和返回值,这一区别可能会有些模糊)。

然后,函数通过一下步骤销毁激活帧:

  • 销毁返回点处仍在作用域内的所有局部变量。
  • 销毁所有参数对象。
  • 释放激活帧所占用的内存。

最后,函数通过以下步骤恢复调用者的执行:

  • 通过将栈寄存器指向调用者的激活帧,并恢复可能被该函数修改的寄存器,来还原调用者的激活帧。
  • 跳转到“调用”操作时存储的调用者恢复点。

需要注意的是,与“调用”操作一样,一些调用约定可能会将“返回”操作的职责分摊到调用者和被调用者的指令中。

协程

协程通过将调用返回操作中的一些步骤分离出来,进一步推广了函数的操作,这些步骤被分解为三个额外的操作:挂起(suspend)、恢复(resume)和销毁(destroy)。

挂起操作在当前函数执行点暂停协程的执行,并将执行权还给调用者而不销毁激活帧。挂起时作用域内的任何对象在协程的执行被暂停后仍然保持有效。需要注意的是,就像函数的返回操作一样,协程只能在其内部被明确定义的挂起点被挂起。

恢复操作会在协程被挂起的位置恢复执行,这会重新激活协程的激活帧。

销毁操作会销毁激活帧,且不会恢复协程的执行,挂起点作用域内的任何对象将被销毁,存储激活帧的内存也会被释放。

协程激活帧

由于协程可以在不销毁激活帧的情况下被挂起,我们无法再保证激活帧的生命周期是严格嵌套的,这意味着激活帧通常不能再使用栈数据结构来分配,因此可能需要改为存储在堆上。

C++ 协程技术规范(Coroutines TS)中有一些规定,允许在编译器能够证明协程的生命周期确实是严格嵌套在调用者生命周期内的情况下,从调用者的激活帧中分配协程帧的内存。如果编译器足够智能,这可以在许多情况下避免堆分配。

对于协程,激活帧的有些部分需要在协程挂起时保持有效,而有些部分只需要在协程执行期间保持有效。例如,生命周期不跨越任何协程挂起点的变量,其内存有可能存储在栈上。

你可以在逻辑上将协程的激活帧分为两部分:协程帧和栈帧。协程帧保存了协程激活帧的一部分,该部分在协程挂起时依然保持有效;栈帧只在协程执行期间存在,并在协程挂起并将执行权转移给调用者或恢复者时被释放。

挂起操作(Suspend Operation)

挂起操作允许协程在函数的中间暂停执行,并将执行权转移回调用者或恢复者。

在协程函数体内,某些点被指定为挂起点。在 C++ 协程技术规范中,这些挂起点通过使用 co_await 或者 co_yield 关键字来标识。

当协程遇到这些挂起点的时候,它首先通过以下步骤为恢复做好准备:

  • 确保所有存储在寄存器中的值被写入协程帧。
  • 将一个指示协程当前挂起点的值写入协程帧中,这使后续的恢复操作知道从哪里恢复协程的执行,也使后续的销毁操作知道哪些值在作用域中并需要被销毁。

一旦协程为恢复执行做好了准备,协程就被视为“挂起”状态。

随后,协程可以在将执行权还给调用者或恢复者之前执行一些额外的逻辑,这部分额外的逻辑可以访问协程帧的句柄,该句柄可用于稍后恢复或销毁协程。

在协程进入“挂起”状态后执行逻辑的能力使得协程可以在不需要同步机制的情况下就能被调度恢复,否则如果协程在进入“挂起”状态之前被调度恢复,那么协程的挂起和恢复可能会发生竞争,此时就需要同步机制。我将在之后的文章中更详细地讨论这一点。

随后,协程可以选择立即恢复执行或继续执行,也可以选择将执行权还给调用者或恢复者。

如果执行权被还给调用者或恢复者,协程激活帧中的栈帧部分会被释放,并从栈中弹出。

恢复操作(Resume Operation)

恢复操作可以在一个当前处于“挂起”状态的协程上执行。

当一个函数希望恢复协程的时候需要有效地“调用”到该函数中的一个特定调用。恢复者通过调用协程帧句柄的 void resume() 方法来标识需要恢复的特殊调用,该句柄是在对应的挂起操作中提供的。

就像一个普通函数调用,对 resume() 的调用会分配一个新的栈帧,并在栈帧中存储调用者的返回地址,然后再将执行权转移到该函数。

但是,与直接转移到函数的开始处不同,它会将执行权转移到上次挂起的位置。具体来讲,它会从协程帧中加载恢复点,然后跳转到该位置继续执行。

当协程下一次挂起或运行完成时,当前对 resume() 的调用将返回,并恢复调用者的执行。[1]

销毁操作(Destroy Operation)

销毁操作会直接销毁协程帧,而不会恢复协程的执行。

这个操作只能在一个被挂起的协程上执行。

销毁操作的行为类似于恢复操作,因为它会重新激活协程的激活帧,包括分配一个新的栈帧并存储销毁操作调用者的返回地址。

然而,它并不会将执行权转移到协程体的上一个挂起点,而是转移到另一条代码路径,该路径会先调用挂起点处作用域内的左右局部变量的析构函数,然后再释放协程帧所占用的内存。

恢复操作类似,销毁操作通过调用协程挂起时提供的协程帧句柄的 void destroy() 方法来找到并销毁对应的激活帧。

调用操作(Call Operation)

协程的调用操作与普通函数的调用操作非常相似,实际上,从调用者的角度看两者没有区别。

不过,普通函数会一直运行到结束才返回,而协程在调用时会在执行到第一个挂起点时将执行权归还给调用者。

当执行协程的调用操作时,调用者会分配一个新的栈帧,将参数和返回地址写入栈帧,并将执行权转移到协程中。这与调用一个普通函数完全相同。

协程首先在堆上分配一个协程帧,并将参数从栈帧复制或移动到协程帧中,以确保这些参数的生命周期能够延续到第一个挂起点之后。

返回操作(Return Operation)

协程的返回操作与普通函数的返回操作有一点不同。

当协程在执行 return 语句(在技术规范中是 co_return)时,它会先将返回值存储到某个位置(具体存储位置可以由协程自行定义),然后销毁当前作用域内的所有局部变量(但不会销毁参数)。

接下来,协程可以执行一些额外的逻辑,然后再将执行权还给调用者或恢复者。

这些额外的逻辑可能执行一些操作来发布返回值,或者恢复另一个正在等待结果的协程,这是完全自定义的。

之后,协程要么执行挂起操作(保持协程帧存活),要么执行销毁操作(销毁协程帧)。

最后,执行权按照挂起操作或销毁操作的语义返回给调用者或恢复者,同时从栈中弹出激活帧的栈帧部分。

需要注意的是,传递给返回操作的返回值并不等同于调用操作返回的返回值,因为返回操作可能在调用者从最初的调用操作恢复很久之后才被执行。

一个示例

为了更直观地理解这些概念,我们可以通过一个简单的示例来演示协程的调用、挂起以及后续恢复的过程。

假设我们有一个函数(或协程)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 中,而这个变量是存放在 x() 的协程帧中的。

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

如果 x() 现在遇到一个挂起点并挂起而不销毁它的激活帧,那么执行将返回到 f()

这时,x() 的栈帧部分会从栈中弹出,但协程帧仍然保留在堆上。当协程第一次挂起时,会返回一个返回值给调用者。这个返回值通常包含指向挂起的协程帧的句柄,后续可以使用这个句柄来恢复协程的执行。当 x() 挂起时,它还会在协程帧中存储一个恢复点的地址(我们称之为 RP,Resume-Point)。

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  | ------+     +-----------+
+----------------+        +------+
| ...            |
|                |

总结

我已经将协程描述为函数的一个扩展,它除了包含 “调用”和 “返回”操作外,还增加了三个额外的操作 ——“挂起”、“恢复”和 “销毁”。

我希望这能为理解协程及其控制流提供一些有用的思路。

在下一篇文章中,我将介绍 C++ 协程技术规范(TS)语言扩展的机制,并解释编译器如何将你编写的代码转换为协程。


  1. 译者注:简单来说,调用 resume() 函数时会从挂起点恢复协程的执行,当协程执行完毕或者再次挂起时才会返回。 

updatedupdated2025-02-032025-02-03