lewissbaker coroutine
Asymmetric Transfer 对 coroutine 的分析十分深入、易懂。
Coroutine Theory
NOTE: 作者采用的是"对比"的思路来进行描述: 以我们熟知的subroutine即function为例来作为对照，来对coroutine进行描述，核心观点是在"In summary"段中提出的:
coroutines as being a generalization of a function that has three additional operations - ‘Suspend’, ‘Resume’ and ‘Destroy’
Coroutines are Functions are Coroutines
NOTE: function的专业说法是subroutine，显然，它和coroutine是能够对应的
A coroutine is a generalisation of a function that allows the function to be suspended and then later resumed.
“Normal” Functions
A normal function can be thought of as having two operations: Call and Return (Note that I’m lumping “throwing an exception” here broadly under the Return operation).
The Call operation creates an activation frame, suspends execution of the calling function and transfers execution to the start of the function being called.
The Return operation passes the return-value to the caller, destroys the activation frame and then resumes execution of the caller just after the point at which it called the function.
Let’s analyse these semantics a little more…
Activation Frames
NOTE: 原文这一段，其实是在分析是stack frame，这些内容是一些基础知识
When an activation frame is allocated on this stack data structure it is often called a “stack frame”.
This stack data-structure is so common that most (all?) CPU architectures have a dedicated register for holding a pointer to the top of the stack (eg. in X64 it is the rsp register).
To allocate space for a new activation frame, you just increment this register by the frame-size. To free space for an activation frame, you just decrement this register by the frame-size.
The ‘Call’ Operation
When a function calls another function, the caller must first prepare itself for suspension.
The ‘Return’ Operation
When a function returns via a return-statement, the function first stores the return value (if any) where the caller can access it.
Coroutines
Coroutines generalize the operations of a function by separating out(分离出) some of the steps performed in the Call and Return operations into three extra operations: Suspend, Resume and Destroy.
The Suspend operation suspends execution of the coroutine at the current point within the function and transfers execution back to the caller or resumer without destroying the activation frame. Any objects in-scope at the point of suspension remain alive after the coroutine execution is suspended.
Note that, like the Return operation of a function, a coroutine can only be suspended from within the coroutine itself at well-defined suspend-points.
The Resume operation resumes execution of a suspended coroutine at the point at which it was suspended. This reactivates the coroutine’s activation frame.
The Destroy operation destroys the activation frame without resuming execution of the coroutine. Any objects that were in-scope at the suspend point will be destroyed. Memory used to store the activation frame is freed.
Coroutine activation frames
Since coroutines can be suspended without destroying the activation frame, we can no longer guarantee that activation frame lifetimes will be strictly nested. This means that activation frames cannot in general be allocated using a stack data-structure and so may need to be stored on the heap instead.
NOTE: nesting relation
There are some provisions(规定) in the C++ Coroutines TS to allow the memory for the coroutine frame to be allocated from the activation frame of the caller if the compiler can prove that the lifetime of the coroutine is indeed strictly nested within the lifetime of the caller. This can avoid heap allocations in many cases provided you have a sufficiently smart compiler.
NOTE: optimization，上述涉及了stack VS heap，参见
Software-analysis\Performance\Memory章节
With coroutines there are some parts of the activation frame that need to be preserved across coroutine suspension and there are some parts that only need to be kept around while the coroutine is executing. For example, the lifetime of a variable with a scope that does not span any coroutine suspend-points can potentially be stored on the stack.
NOTE: 上面提到了coroutine suspend point概念;
最后一段话的意思是: 在**coroutine suspend-points**之前的variable，是可以store on the stack的。
You can logically think of the activation frame of a coroutine as being comprised of two parts:
1) the ‘coroutine frame’ and
2) the ‘stack frame’.
The ‘coroutine frame’ holds part of the coroutine’s activation frame that persists while the coroutine is suspended and the ‘stack frame’ part only exists while the coroutine is executing and is freed when the coroutine suspends and transfers execution back to the caller/resumer.
NOTE: 后面的内容涉及到了calling convention。
The ‘Suspend’ operation
The Suspend operation of a coroutine allows the coroutine to suspend execution in the middle of the function and transfer execution back to the caller or resumer of the coroutine.
There are certain points within the body of a coroutine that are designated as suspend-points. In the C++ Coroutines TS, these suspend-points are identified by usages of the co_await or co_yield keywords.
When a coroutine hits one of these suspend-points it first prepares the coroutine for resumption(恢复) by:
- Ensuring any values held in registers are written to the coroutine frame
- Writing a value to the coroutine frame that indicates which suspend-point the coroutine is being suspended at. This allows a subsequent Resume operation to know where to resume execution of the coroutine or so a subsequent Destroy to know what values were in-scope and need to be destroyed.
Once the coroutine has been prepared for resumption(恢复), the coroutine is considered ‘suspended’.
The coroutine then has the opportunity to execute some additional logic before execution is transferred back to the caller/resumer. This additional logic is given access to a handle to the coroutine-frame that can be used to later resume or destroy it.
This ability to execute logic after the coroutine enters the ‘suspended’ state allows the coroutine to be scheduled for resumption without the need for synchronisation that would otherwise be required if the coroutine was scheduled for resumption prior to entering the ‘suspended’ state due to the potential for suspension and resumption of the coroutine to race. I’ll go into this in more detail in future posts.
The coroutine can then choose to either immediately resume/continue execution of the coroutine or can choose to transfer execution back to the caller/resumer.
If execution is transferred to the caller/resumer the stack-frame part of the coroutine’s activation frame is freed and popped off the stack.
The ‘Resume’ operation
The ‘Destroy’ operation
The ‘Call’ operation of a coroutine
The ‘Return’ operation of a coroutine
An illustration
To help put these concepts into pictures, I want to walk through a simple example of what happens when a coroutine is called, suspends and is later resumed.
So let’s say we have a function (or coroutine), f() that calls a coroutine, x(int a).
Before the call we have a situation that looks a bit like this:
STACK REGISTERS HEAP
+------+
+---------------+ <------ | rsp |
| f() | +------+
+---------------+
| ... |
| |
Then when x(42) is called, it first creates a stack frame for x(), as with normal functions.
STACK REGISTERS HEAP
+----------------+ <-+
| x() | |
| a = 42 | |
| ret= f()+0x123 | | +------+
+----------------+ +--- | rsp |
| f() | +------+
+----------------+
| ... |
| |
Then, once the coroutine x() has allocated memory for the coroutine frame on the heap and copied/moved parameter values into the coroutine frame we’ll end up with something that looks like the next diagram. Note that the compiler will typically hold the address of the coroutine frame in a separate register to the stack pointer (eg. MSVC stores this in the rbp register).
STACK REGISTERS HEAP
+----------------+ <-+
| x() | |
| a = 42 | | +--> +-----------+
| ret= f()+0x123 | | +------+ | | x() |
+----------------+ +--- | rsp | | | a = 42 |
| f() | +------+ | +-----------+
+----------------+ | rbp | ------+
| ... | +------+
| |
If the coroutine x() then calls another normal function g() it will look something like this.
STACK REGISTERS HEAP
+----------------+ <-+
| g() | |
| ret= x()+0x45 | |
+----------------+ |
| x() | |
| coroframe | --|-------------------+
| a = 42 | | +--> +-----------+
| ret= f()+0x123 | | +------+ | x() |
+----------------+ +--- | rsp | | a = 42 |
| f() | +------+ +-----------+
+----------------+ | rbp |
| ... | +------+
| |
When g() returns it will destroy its activation frame and restore x()’s activation frame. Let’s say we save g()’s return value in a local variable b which is stored in the coroutine frame.
STACK REGISTERS HEAP
+----------------+ <-+
| x() | |
| a = 42 | | +--> +-----------+
| ret= f()+0x123 | | +------+ | | x() |
+----------------+ +--- | rsp | | | a = 42 |
| f() | +------+ | | b = 789 |
+----------------+ | rbp | ------+ +-----------+
| ... | +------+
| |
If x() now hits a suspend-point and suspends execution without destroying its activation frame then execution returns to f().
This results in the stack-frame part of x() being popped off the stack while leaving the coroutine-frame on the heap. When the coroutine suspends for the first time, a return-value is returned to the caller. This return value often holds a handle to the coroutine-frame that suspended that can be used to later resume it. When x() suspends it also stores the address of the resumption-point of x() in the coroutine frame (call it RP for resume-point).
STACK REGISTERS HEAP
+----> +-----------+
+------+ | | x() |
+----------------+ <----- | rsp | | | a = 42 |
| f() | +------+ | | b = 789 |
| handle ----|---+ | rbp | | | RP=x()+99 |
| ... | | +------+ | +-----------+
| | | |
| | +------------------+
This handle may now be passed around as a normal value between functions. At some point later, potentially from a different call-stack or even on a different thread, something (say, h()) will decide to resume execution of that coroutine. For example, when an async I/O operation completes.
The function that resumes the coroutine calls a void resume(handle) function to resume execution of the coroutine. To the caller, this looks just like any other normal call to a void-returning function with a single argument.
This creates a new stack-frame that records the return-address of the caller to resume(), activates the coroutine-frame by loading its address into a register and resumes execution of x() at the resume-point stored in the coroutine-frame.
STACK REGISTERS HEAP
+----------------+ <-+
| x() | | +--> +-----------+
| ret= h()+0x87 | | +------+ | | x() |
+----------------+ +--- | rsp | | | a = 42 |
| h() | +------+ | | b = 789 |
| handle | | rbp | ------+ +-----------+
+----------------+ +------+
| ... |
| |