协程
对于协程做一个整体的描述，从概念、原理、实现三个方面叙述。侧重有栈协程。
1 概览
1.1 什么是协程
有很多与协程相关的名字：轻量级线程、微线程、纤程、协程、goroutine等等。其本质，都是大学操作系统课程上学到的用户态线程。
后文统一使用协程来描述它。
协程，能让你以同步的方式编写高性能的异步代码，而不用像使用epoll一样维护大量状态机和回调函数；其性能在大多业务场景（计算密集型业务以外的场景），都会优于操作系统线程，其优势主要是以下几点：
- 协程往往在同一线程内执行，需要同步语义的场景，不需要依赖操作系统的互斥锁等系统调用，用一个全局的bool变量作为锁即可，同步操作开销极低
- 协程栈往往比较小，只有几十到几百KB（无栈协程甚至可能只有几KB），相比于线程默认的8MB，同样的配置，能够启动大量的协程，而不影响系统的性能
- 协程的切换由用户自行实现，只需要切换寄存器和用户栈，十分轻量
1.2 有栈协程和无栈协程
协程可以划分为两类
- 有栈协程
- 无栈协程
有栈协程，在创建时，除了创建用于管理协程的对象，还会预先在heap/mmap上分配固定大小（比如128KB）的栈空间，后续协程栈切换时，只需要修改%rsp和%rbp寄存器，将其由程序的函数栈空间，指向协程自己的位于堆上的栈空间即可。有栈协程相对比较灵活，能够在程序任何位置，随时随地进行suspend和resume。
无栈协程，在创建时，只分配管理协程的对象，并不会去heap/mmap上分配协程的栈空间，无栈协程与主程序共用同一个栈，其布局与普通的函数调用栈一致。很明显，这让无栈协程的内存占用更加小，它不需要预先分配独立的栈空间，只是在suspend时，才在堆上按需分配空间，把主程序栈中需要保存的变量restore起来。但这也带来了更多的限制，无栈协程不能随时进行suspend，必须在协程的top-level函数中才能进行进行suspend操作。（且完全体的无栈协程一般需要编译器原生支持。）
有栈协程和无栈协程都支持协程的嵌套调用，都支持将协程绑定到不同线程使用（虽然一般不会这样做）。
1.3 协程库
协程其实和函数调用有些像，其思路就是手动能够保存函数当前的上下文，将执行权让给其他函数，并能在恰当的场合，恢复被保存函数的执行。
当前c/c++中，第三方有栈协程的实现比较多，主流的协程库，都是参考 setjmp/longjmp 或者 swapcontext 两个系列的系统调用实现的，比如libco，boost coroutine。
无栈协程，一般不需要汇编操作，在suspend时，需要能够准确保存要切换的变量，比如asio stackless coroutine、C++20引入的协程。
2 函数栈帧和寄存器约定：x64 UNIX - System V ABI
如前文所说，协程调用和函数调用十分类似，要理解和实现协程，首先要对函数调用过程的栈布局和寄存器使用约定有所了解。一般linux下的栈帧布局为System V，通过readelf命令可以查看elf文件的ABI。
# readelf -h a.out
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x400410
Start of program headers: 64 (bytes into file)
Start of section headers: 7160 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 9
Size of section headers: 64 (bytes)
Number of section headers: 36
Section header string table index: 35
如果你对进程的内存布局不太了解，建议先去google一下，再继续阅读。
函数，主要有函数栈帧、寄存器、指令（汇编）几部分。
2.1 函数栈帧
下图是一个典型的x64函数栈帧布局，相对清晰的描绘了函数的栈帧布局。
image.png
当一个函数被调用，首先要做的是按照ABI规范，保存caller函数的相关寄存器；然后从ABI约定的寄存器和栈中获取函数的参数，执行函数代码；执行完成后，将返回值存入指定寄存器，恢复caller函数的相关寄存器，并从栈帧中获取函数的返回地址，ret到caller函数继续执行。
下图对于%rsp和%rbp的一些细节做了补充（不要纠结return address属于caller函数还是callee函数，这个只是角度问题，不重要）。%rsp寄存器一般存放栈顶指针，顾名思义，指向函数栈的顶端；%rbp寄存器一般存放当前函数的栈帧起始地址，作为基址定位栈帧中的其他变量。
image.png
通过callq指令进入callee函数时，其%rsp指向caller函数的return address。在朴素情形下，接下来的几条指令一般是将%rbp寄存器入栈，然后将%rbp的值设为%rsp寄存器中的地址。在函数指定retq指令返回之前，会将%rbp指针出栈，此时%rsp指针重新指向caller函数的return address，调用retq指令返回caller函数，完成一轮函数调用。
开启了一定级别的编译优化后，上述提到的%rbp寄存器，往往不在作为栈帧顶部指针，而是作为通用寄存器来使用。这可以节省两条指令，并多出一个通用寄存器。栈帧内寻址操作直接使用%rsp指针进行。
The conventional use of %rbp as a frame pointer for the stack frame may be avoided by using
%rsp (the stack pointer) to index into the stack frame. This technique saves two instructions in
the prologue and epilogue and makes one additional general-purpose register (%rbp) available.
另一个优化是%rsp，在入栈、出栈变量时，需要两条指令修改%rsp指针的值，这两条指令同样可以优化。这涉及到上图最下面的一个区域red zone，先给出x64 System V ABI中对其的描述：
The 128-byte area beyond the location pointed to by %rsp is considered to
be reserved and shall not be modified by signal or interrupt handlers. Therefore,
functions may use this area for temporary data that is not needed across function
calls. In particular, leaf functions may use this area for their entire stack frame,
rather than adjusting the stack pointer in the prologue and epilogue. This area is
known as the red zone.
简而言之，程序可以假定，这128字节一定不会被其他线程、信号、中断等异步修改，所以可以直接通过%rsp使用这128字节的内存，而不需要增减%rsp指针。但red zone在函数调用过程会被覆盖，所以这一优化，一般用于叶子函数（即不会调用其他函数的函数）。
2.2 寄存器
下图是x64 System V ABI中对寄存器的一个概览。
image.png
抛开寄存器的用途不谈，从寄存器的易失性（上图最后一列）角度考虑，寄存器可以分成易失性寄存器和非易失性寄存器。
易失性寄存器可以看作临时寄存器，在函数调用过程被调函数可以随意修改覆盖，不需要保留其值。
非易失性寄存器在函数调用过程后，返回原函数时，需要保证其值与原来一致，被调函数需要保存其原值，并负责恢复。
根据x64 System V ABI，x64的非易失性寄存器包括：
- %rbp, %rbx, %r12, %r13, %r14, %r15
- %rsp
- mxcsr
- x87 CW
x64 System V ABI规范中有关非易失性寄存器的相关描述：
Registers %rbp, %rbx and %r12 through %r15 “belong” to the calling function
and the called function is required to preserve their values.
In other words, a called function must preserve these registers’ values for its caller.
Remaining registers “belong” to the called function.
The control bits of the MXCSR register are callee-saved (preserved across
calls), while the status bits are caller-saved (not preserved). The x87 status word
register is caller-saved, whereas the x87 control word is callee-saved.
易失性寄存器一般为参数传递寄存器、结果返回寄存器、临时寄存器等；非易失性寄存器包括栈指针寄存器、帧指针寄存器、规定的一些callee-save寄存器、以及几个特殊寄存器。
有关各寄存器的详细用途，内容比较多，在此不做展开，可以参考官方ABI规范，描述的很详细：System V Application Binary Interface AMD64 Architecture Processor Supplement Version 1.0
2.3 指令（汇编）
这里我们搞一个简单的实例，用下面的程序来展示。
int fuck(int l, int r) {
return l+r;
}
int main(){
int a(1);
int b(2);
int c = fuck(a, b);
return 0;
}
函数对应的汇编代码如下（编译时，没有加任何优化参数），代码后附详细描述。
(gdb) disassemble main
Dump of assembler code for function main():
0x0000000000400511 <+0>: push %rbp
0x0000000000400512 <+1>: mov %rsp,%rbp
0x0000000000400515 <+4>: sub $0x10,%rsp
0x0000000000400519 <+8>: movl $0x1,-0x4(%rbp)
0x0000000000400520 <+15>: movl $0x2,-0x8(%rbp)
0x0000000000400527 <+22>: mov -0x8(%rbp),%edx
0x000000000040052a <+25>: mov -0x4(%rbp),%eax
0x000000000040052d <+28>: mov %edx,%esi
0x000000000040052f <+30>: mov %eax,%edi
0x0000000000400531 <+32>: callq 0x4004fd <fuck(int, int)>
0x0000000000400536 <+37>: mov %eax,-0xc(%rbp)
0x0000000000400539 <+40>: mov $0x0,%eax
0x000000000040053e <+45>: leaveq
0x000000000040053f <+46>: retq
End of assembler dump.
在main函数中：
- 保存%rbp寄存器的值（帧指针），然后将%rbp指向%rsp（当前的栈指针）
- 然后为局部变量a和b分配空间并初始化，将栈指针下移16字节（因为栈帧指针要求16字节对齐，所以虽然我们用了12字节，仍然要分配16字节）
- 因为a和b都是integer类型的变量，根据ABI，前六个整形参数使用
%rdi,%rsi, %rdx, %rcx, %r8 and %r9进行传参，所以这里将a和b的值，分别赋给%edi和%esi寄存器（e表示对应寄存器的低32bit位置） - 因为没用用到caller-save的寄存器，接下来直接通过callq指令调用将
return address压栈，并转到fuck函数执行 - 执行fuck函数内容，在fuck函数末尾通过retq指令将
return address从栈中取出，并返回到main函数 - 从%eax寄存器中取出函数的返回结果，存入变量c对应的栈空间
- 在函数结束前，通过leaveq指令（等同于
mov %rbp,%rsp然后pop %rbp），将%rsp寄存器指向%rbp（当前的帧指针），并从栈中弹出函数开头保存的旧帧指针，赋给%rbp寄存器 - 调用retq返回caller函数
(gdb) disassemble fuck
Dump of assembler code for function fuck(int, int):
0x00000000004004fd <+0>: push %rbp
0x00000000004004fe <+1>: mov %rsp,%rbp
0x0000000000400501 <+4>: mov %edi,-0x4(%rbp)
0x0000000000400504 <+7>: mov %esi,-0x8(%rbp)
0x0000000000400507 <+10>: mov -0x8(%rbp),%eax
0x000000000040050a <+13>: mov -0x4(%rbp),%edx
0x000000000040050d <+16>: add %edx,%eax
0x000000000040050f <+18>: pop %rbp
0x0000000000400510 <+19>: retq
End of assembler dump.
在fuck函数中：
- 保存%rbp寄存器的值（帧指针），然后将%rbp指向%rsp（当前的栈指针）
- 为a和b在栈上分配空间（这里因为fuck函数是leaf function，所以直接使用了%rsp栈指针下的128字节
red zone，省略了增减%rsp寄存器的步骤），并从%edi和%esi寄存器中取出参数a和b的值，存入栈中 - 执行运算，并将结果存入%eax寄存器（%rax寄存器用于存储函数的第一个整型返回值）
- 从栈中恢复%rbp集群器的值
- 调用retq返回caller函数
上面的描述对于我们在栈帧和寄存器两节，提到的栈指针%rsp、帧指针%rbp, red zone、局部变量分配、函数参数传递寄存器、函数结果返回寄存器等要点都有体现。
唯一不太明朗的是栈帧布局中的return address的位置，我们打个断点，确认下这一点。
在程序的第2行，也就是fuck函数内部打一个断点。按汇编代码来看，此时，%rbp寄存器已经入栈，栈顶第一个值为旧%rbp寄存器的值，栈顶第二个值应该为我们的函数返回地址，也就是main函数中callq指令下一条指令的地址：0x0000000000400536。
(gdb) disassemble /m fuck
Dump of assembler code for function fuck(int, int):
1 int fuck(int l, int r) {
0x00000000004004fd <+0>: push %rbp
0x00000000004004fe <+1>: mov %rsp,%rbp
0x0000000000400501 <+4>: mov %edi,-0x4(%rbp)
0x0000000000400504 <+7>: mov %esi,-0x8(%rbp)
2 return l+r;
0x0000000000400507 <+10>: mov -0x8(%rbp),%eax
0x000000000040050a <+13>: mov -0x4(%rbp),%edx
0x000000000040050d <+16>: add %edx,%eax
3 }
0x000000000040050f <+18>: pop %rbp
0x0000000000400510 <+19>: retq
End of assembler dump.
(gdb) b 2
Breakpoint 1 at 0x400507: file main.cc, line 2.
(gdb) r
Breakpoint 1, fuck (l=1, r=2) at main.cc:2
2 return l+r;
输出下栈顶第二个8字节位置的值，为0x00400536，确实是main函数下一条指令的地址，与我们预期的一致。
(gdb) x /x $rsp+0x8
0x7fffffffe3b8: 0x00400536
至此，函数栈帧和寄存器相关的内容已经全部理清。
本节涉及的gdb命令：
# 打印函数汇编代码
disassemble func_name
# 带代码打印函数汇编代码
disassemble /m func_name
# 打印寄存器列表
info registers
# 上面命令的输出不包括浮点寄存器和向量寄存器的内容，要打印所有寄存器，使用
info all-registers
# 打印rsp寄存器的值（/x表示以十六进制打印）
p /x $rsp
# 打印指定地址处的值
x /x $rsp
x /x $rsp+0x8
3 协程实现
理解了前文的函数栈帧和寄存器，对于协程的实现，会感觉相当自然。本节会说明如何实现协程，并给出一个完备的协程切换函数的实现。
在寄存器一节我们知道了，x64的非易失性寄存器。
在协程切换时，我们需要保存的上下文，除了这些非易失性寄存器，还有协程未来恢复后要执行的下一条指令的地址，即next instruction。如下：
- %rbp, %rbx, %r12, %r13, %r14, %r15
- %rsp
- mxcsr
- x87 CW
- next instruction
下面是具体实现的协程切换函数：
- coctx_save保存当前协程的上下文
- coctx_resume恢复指定协程的上下文
- coctx_swap存储当前上下文，并切换到指定协程执行。
coctx_save和coctx_resume仅用于展示如何实现协程上下文的保存和恢复；并不能真实的用于协程切换。如果确实要使用，需要处理一些细节，coctx_save执行后，ctx中保存的是调用coctx_save后的返回地址，但这个地址之后，往往会执行coctx_resume以切换到其他协程，所以这里需要通过一些机制，保证在当前协程被重新切换回来时，不会再执行一次coctx_resume。
coctx_swap通过将save和resume放到一个函数中，规避了这个问题，保存的返回地址就是协程接下来应该执行的代码地址。
这里仅展示了协程切换函数的实现，如果需要实现一套能够使用的协程库，还需要维护协程的栈、状态等信息，并需要一个全局的调度器，某个协程执行完成或者切出时，由调度器决定下一个执行的协程。如果要在实际程序中使用，调度器往往要基于epoll实现，并要有定时器、hook系统调用等功能。
coctx_op.h
/* C++ needs to know that types and declarations are C, not C++. */
#ifdef __cplusplus
# define __M_BEGIN_DECLS extern "C" {
# define __M_END_DECLS }
#else
# define __M_BEGIN_DECLS
# define __M_END_DECLS
#endif
#ifndef _COCTX_OP_H
#define _COCTX_OP_H 1
__M_BEGIN_DECLS
typedef unsigned char byte1_t;
typedef unsigned short byte2_t;
typedef unsigned int byte4_t;
typedef unsigned long long byte8_t;
typedef struct {
byte8_t retaddr;
byte8_t registers[7];
byte4_t mxcsr;
byte2_t x87cw;
byte2_t padding; // not used, just padding explictly
} coctx_t;
extern int coctx_save(coctx_t *old_ctx);
extern int coctx_resume(coctx_t *new_ctx);
extern int coctx_swap(coctx_t *old_ctx, coctx_t *new_ctx);
__M_END_DECLS
#endif /* coctx_op.h */
coctx_op.S
#define _retaddr 0
#define _rsp 8
#define _rbp 16
#define _rbx 24
#define _r12 32
#define _r13 40
#define _r14 48
#define _r15 56
#define _mxcsr 64
#define _x87 68
.text
.globl coctx_save
.type coctx_save, @function
coctx_save:
/* save retaddr */
movq (%rsp), %r11
movq %r11, _retaddr(%rdi)
/* save rsp after pop retaddr */
leaq 8(%rsp), %r11
movq %r11, _rsp(%rdi)
/* save callee-save registers */
movq %rbp, _rbp(%rdi)
movq %rbx, _rbx(%rdi)
movq %r12, _r12(%rdi)
movq %r13, _r13(%rdi)
movq %r14, _r14(%rdi)
movq %r15, _r15(%rdi)
stmxcsr _mxcsr(%rdi)
fnstcw _x87(%rdi)
/* return code 0 */
movl $0, %eax
/* pop retaddr from stack to %rip and return */
retq
.size coctx_save, .-coctx_save
.globl coctx_resume
.type coctx_resume, @function
coctx_resume:
/* resume rsp and retaddr*/
movq _rsp(%rdi), %rsp
movq _retaddr(%rdi), %r11
pushq %r11
/* resume callee-save registers */
movq _rbp(%rdi), %rbp
movq _rbx(%rdi), %rbx
movq _r12(%rdi), %r12
movq _r13(%rdi), %r13
movq _r14(%rdi), %r14
movq _r15(%rdi), %r15
ldmxcsr _mxcsr(%rdi)
fldcw _x87(%rdi)
/* return code 0 */
movl $0, %eax
/* pop retaddr from stack to %rip and return */
retq
.size coctx_resume, .-coctx_resume
.globl coctx_swap
.type coctx_swap, @function
coctx_swap:
/* save retaddr */
movq (%rsp), %r11
movq %r11, _retaddr(%rdi)
/* save rsp after pop retaddr */
leaq 8(%rsp), %r11
movq %r11, _rsp(%rsp)
/* save callee-save registers */
movq %rbp, _rbp(%rdi)
movq %rbx, _rbx(%rdi)
movq %r12, _r12(%rdi)
movq %r13, _r13(%rdi)
movq %r14, _r14(%rdi)
movq %r15, _r15(%rdi)
stmxcsr _mxcsr(%rdi)
fnstcw _x87(%rdi)
/* resume rsp and retaddr*/
movq _rsp(%rsi), %rsp
movq _retaddr(%rsi), %r11
pushq %r11
/* resume callee-save registers */
movq _rbp(%rsi), %rbp
movq _rbx(%rsi), %rbx
movq _r12(%rsi), %r12
movq _r13(%rsi), %r13
movq _r14(%rsi), %r14
movq _r15(%rsi), %r15
ldmxcsr _mxcsr(%rsi)
fldcw _x87(%rsi)
/* return code 0 */
movl $0, %eax
/* pop retaddr from stack to %rip and return */
retq
.size coctx_swap, .-coctx_swap
注：有关x87 CW和mxcsr寄存器，我没有做深入的研究，仅用一般情形下的参数作为其初始值进行初始化，并随coctx切换而保存，想要了解这两个寄存器的具体信息，可以参考下面这些文章。
https://xem.github.io/minix86/manual/intel-x86-and-64-manual-vol1/o_7281d5ea06a5b67a-197.html
https://docs.roguewave.com/en/totalview/2019/html/index.html#page/Reference_Guide/Intelx86MXSCRRegister_2.html
https://stackoverflow.com/questions/50308366/storing-the-x87-fpu-control-word
https://xem.github.io/minix86/manual/intel-x86-and-64-manual-vol1/o_7281d5ea06a5b67a-214.html
https://wiki.osdev.org/SSE
