greenlet是stackless Python中剥离出来的一个项目，可以作为官方CPython的一个扩展来使用，从而支持Python协程。gevent正是基于greenlet实现。
协程实现原理
实现协程主要是在协程切换时，将协程当前的执行上下文保存到协程关联的context中。在c/c++这种native程序中实现协程，需要将栈内容和CPU各个寄存器的内容保存起来。在Python这种VM中则有些不同。例如，在以下基于greenlet协程的python程序中：
1
2
3
4
5
6
7
8
9
10
11
12
13
def foo():
bar()
def bar():
a = 3 + 1
gr2.switch()
def func():
pass
gr1 = greenlet(foo)
gr2 = greenlet(func)
gr1.switch()
在bar中gr2.switch切换到gr2时，协程库需要保存gr1协程的执行上下文。这个上下文包括:
- Python VM的stack
Python VM中解释执行的上下文 理解以上两点非常重要，至于为什么呢？想象一下如何去实现一个Python VM，去解释执行一段Python代码。其实这在任何基于VM的语言中，原理都是一样的（native程序可以把x86物理CPU也视作特殊的VM)。可以参考Python解释器简介-深入主循环。主要包含两方面内容：
- VM在执行代码时，其自身调用栈通常都是递归的
- VM在执行代码时，通常会创建相应的数据结构来表示代码执行块，例如通常会有个
struct Frame来表示一个函数
在VM的实现中通常会有类似以下的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Frame {
unsigned char *codes; // 存放代码指令
size_t pc; // 当前执行的指令位置
int *stack; // stack-based的VM会有一个栈用于存放指令操作数
};
void op_call(frame) {
switch (OP_CODE()) {
case OP_CALL:
child_frame = new_frame()
op_call(child_frame)
...
case OP_ADD:
op_add(...)
}
}
对应到前面的Python例子代码，在某一时刻VM的call stack可能是这样的：
1
2
3
op_add
op_call
op_call
理解了以上内容后，就可以推测出greenlet本质上也是做了以上两件事。
greenlet实现原理
greenlet库中每一个协程称为一个greenlet。greenlet都有一个栈空间，如下图：
图中未表达出来的，greenlet的栈空间地址可能是重叠的。对于活跃的（当前正在运行）的greenlet，其栈内容必然在c程序栈顶。而不活跃的被切走的greenlet，其栈内容会被copy到新分配的堆内存中。greenlet的栈空间是动态的，其起始地址是固定的，但栈顶地址不固定。以下代码展示一个greenlet的栈空间如何确定：
1
2
3
4
579 if (!PyGreenlet_STARTED(target)) { // greenlet未启动，是一个需要新创建的greenlet
580 void* dummymarker; // 该局部变量的地址成为新的greenlet的栈底
581 ts_target = target;
582 err = g_initialstub(&dummymarker); // 创建该greenlet并运行
以上greenlet->stack_stop确定了栈底，而栈顶则是动态的，在切换到其他greenlet前，对当前greenlet进行上下文的保存时，获取当前的RSP（程序实际运行的栈顶地址）：
1
2
3
4
5
6
7
8
9
10
410 static int GREENLET_NOINLINE(slp_save_state)(char* stackref)
411 {
412 /* must free all the C stack up to target_stop */
413 char* target_stop = ts_target->stack_stop;
414 PyGreenlet* owner = ts_current;
415 assert(owner->stack_saved == 0);
416 if (owner->stack_start == NULL)
417 owner = owner->stack_prev; /* not saved if dying */
418 else
419 owner->stack_start = stackref; // stack_start指向栈顶
stackref是通过汇编获取当前RSP寄存器的值：
1
__asm__ ("movl %%esp, %0" : "=g" (stackref));
保存栈内容到堆内存参看g_save的实现，没什么特别的。除了保存栈内容外，如上一节讲的，还需要保存VM执行函数所对应的Frame对象，这个在g_switchstack中体现：
1
2
3
4
5
6
7
8
9
10
460 PyThreadState* tstate = PyThreadState_GET(); // 获取当前线程的VM执行上下文
461 current->recursion_depth = tstate->recursion_depth;
462 current->top_frame = tstate->frame; // 保存当前正在执行的frame到当前正在执行的greenlet
...
473 slp_switch(); // 做栈切换
...
487 PyThreadState* tstate = PyThreadState_GET();
488 tstate->recursion_depth = target->recursion_depth;
489 tstate->frame = target->top_frame; // 切换回来
上面的代码展示VM frame的切换。接下来看下最复杂的部分，当切换到目标greenlet时，如何恢复目标greenlet的执行上下文，这里主要就是恢复目标greenlet的栈空间。假设有如下greenlet应用代码：
1
2
3
4
5
6
7
8
9
10
def test1():
gr2.switch()
def test2():
print('test2')
gr1 = greenlet(test1)
gr2 = greenlet(test2)
gr1.switch()
在gr1中切换到gr2时，也就是gr2.switch，会发生什么事情。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// g_switch 实现
574 if (PyGreenlet_ACTIVE(target)) {
575 ts_target = target; // 找到目标greenlet，也就是gr2
576 err = g_switchstack(); // 开始切换
// g_switchstack 实现
462 current->top_frame = tstate->frame;
...
473 err = slp_switch();
// slp_switch 实现，根据不同平台实现方式不同，原理相同
69 SLP_SAVE_STATE(stackref, stsizediff);
// 这个很重要，强行将当前的栈指针ESP/EBP (32位OS)通过加上一个与目标greenlet栈地址的偏移，而回到了
// 目标greenlet的栈空间。可以在下文看到stsizediff的获取实现
70 __asm__ volatile (
71 "addl %0, %%esp\n"
72 "addl %0, %%ebp\n"
73 :
74 : "r" (stsizediff)
75 );
76 SLP_RESTORE_STATE();
// SLP_SAVE_STATE 实现
316 #define SLP_SAVE_STATE(stackref, stsizediff) \
317 stackref += STACK_MAGIC; \
318 if (slp_save_state((char*)stackref)) return -1; \
319 if (!PyGreenlet_ACTIVE(ts_target)) return 1; \
// 获取目标greenlet的栈空间与当前栈地址的偏移，用于稍后设置当前栈地址回目标greenlet的栈地址
320 stsizediff = ts_target->stack_start - (char*)stackref
// slp_save_state 没啥看的，前面也提过了，主要就是复制当前greenlet栈内容到堆内存
// SLP_RESTORE_STATE 也没什么看的，主要就是把greenlet堆内存复制回栈空间
以上，首先将ESP/EBP的值改回目标greenlet当初切换走时的ESP/EBP值，然后再把greenlet的栈空间内存（存放于堆内存中）全部复制回来，就实现了greenlet栈的回切。尤其注意的是，这个栈中是保存了各种函数的return地址的，所以当slp_switch返回时，就完全恢复到了目标greenlet当初被切走时栈上的内容，包括各种函数调用栈。而当前greenlet的栈，则停留在了类似以下的函数调用栈：
1
2
3
g_switchstack
g_switch
...