有一段时间没发博客了,10月份实验室布置了个任务,写个pl0文法的语言,差不多赶了1个月,编译原理这块一直都是挺有趣的,当然也是有一定难度的,有机会我一定会往编译原理这个分类中添加几篇文章。
好,言归正传。之前发了2篇关于协程的文章,都只是提供了一个大概的思想,并没有给出具体的实现。似乎缺少了实现,协程这一系列就不能算是圆满结束,毕竟XX说过“talk is cheap, show me the code”,好这次就show一下代码。
===CHANGELOG===
2015-11-26
- 去除Coroutine_bind
- 为Coroutine_yield和Coroutine_resume提供参数和返回值支持
2015-12-02
- 简化内部调度器的实现方式,去除位于栈空间顶端的key
2015-12-06
- 实现对win32平台的支持
关于协程的定义以及实现方式,我在之前的两篇博文中已经有了大致的描述,这里给出链接,不再复述,如果各位对协程的实现细节感兴趣,建议阅读这两篇文章。
0x00 Coroutine库介绍
目前发布的这个协程库的名字是Coroutine,如下为github的链接:
Coroutine库的特性:
- 不依赖setjmp及ucontext
- 跨平台(x86 & amd64 with gcc/clang,不含mac os x)
- 对称式协程
- 支持栈以及寄存器的dump
- 支持协程嵌套
基本实现方式和之前文章中描述的大致相同,只不过它不再依赖setjmp.h,而是通过汇编实现了一套类似的机制。
0x01 Coroutine结构体
typedef struct coroutine {
cstat_t state;
regbuf_t env;
void* stk;
void* top;
void* bot;
void* sp;
coro_cb_t main;
void* res;
} coroutine_t, *Coroutine;
这里我们需要关注的是state、main、res几个成员,它们分别表示协程当前的状态,协程的主函数以及内部数据指针。至于其它变量,主要保存的是上下文信息,以及栈的信息,使用时不建议做任何修改,unless you know what you are doing!
Coroutine内部存在4种状态:
- INIT: 协程初始状态,此时尚未执行main
- PEND: 协程挂起
- RUN: 协程运行中
- END: 协程main函数执行结束
状态转换图如下所示:
它们会对协程的运行产生一定的约束,避免出现不必要的错误,例如:
- reset操作只能对处于END状态的协程实施
- yield操作只能对处于RUN状态的协程实施
- resume操作只能对处于PEND/INIT状态的协程实施
main的类型为coro_cb_t,它是一个函数指针,声明如下:
typedef void* (*coro_cb_t)(struct coroutine*, void*);
这里使用coroutine作为参数的有2大原因:
- yield和resume操作均需要coro变量作为参数
- res可以用以保存上下文数据,至于参数和返回值,请按平常的方式使用
0x02 相关函数
<s>Coroutine Coroutine_new(size_t)</s>
Coroutine Coroutine_new(coro_cb_t, size_t)
- 创建协程实例,参数为栈的大小
void Coroutine_close(Coroutine)
- 关闭协程,不可为RUN状态
int Coroutine_status(Coroutine)
- 返回协程当前的状态,通常不使用
int Coroutine_isInit(Coroutine)
- 判断协程的当前状态是否为INIT
int Coroutine_isPend(Coroutine)
- 判断协程的当前状态是否为PEND
int Coroutine_isRun(Coroutine)
- 判断协程的当前状态是否为RUN
int Coroutine_isEnd(Coroutine)
- 判断协程的当前状态是否为END
<s>void Coroutine_bind(Coroutine)</s>
- <s>绑定协程的main函数,协程不可为RUN或PEND</s>
<s>void Coroutine_yield(Coroutine)</s>
void Coroutine_yield(Coroutine, void)
- 跳出当前main函数,其返回值为Coroutine_resume的参数,参数为Coroutine_resume的返回值
<s>void Coroutine_resume(Coroutine)</s>
void Coroutine_resume(Coroutine, void)
- 跳入挂起的main函数,其返回值为Coroutine_yield的参数或main函数的返回值,参数为Coroutine_yield的返回值或者main函数的参数,取决于当前协程的状态
<s>void Coroutine_reset(Coroutine)</s>
void Coroutine_reset(Coroutine, coro_cb_t)
- 重设置协程,由END转变为INIT,可以通过参数重新设置main函数,也可通过传入NULL,保持原有函数
void Coroutine_dumpRegs(Coroutine)
- dump协程的寄存器信息
void Coroutine_dumpStack(Coroutine)
- dump协程的栈信息
dump系列函数在使用前必须定义DEBUG宏。
0x03 使用示例
#include "coroutine.h"
#include <stdio.h>
void* run(Coroutine coro, void* args) {
printf(">> now inside RUN <<\n");
printf("message from run: %s\n", (char*)(args));
args = Coroutine_yield(coro, "OK");
printf("message from run: %s\n", (char*)(args));
return "done";
}
void* run_again(Coroutine coro, void* args) {
printf(">> now inside RUN_AGAIN <<\n");
printf("message from run_again: %s\n", (char*)(args));
args = Coroutine_yield(coro, "OK");
printf("message from run_again: %s\n", (char*)(args));
return "done";
}
void test() {
char* res;
Coroutine coro = Coroutine_new(run, 1024);
assert(Coroutine_isInit(coro));
res = (char*)Coroutine_resume(coro, "hello");
assert(Coroutine_isPend(coro));
printf("message from run: %s\n", res);
res = (char*)Coroutine_resume(coro, "world");
assert(Coroutine_isEnd(coro));
printf("message from run: %s\n", res);
assert(Coroutine_isEnd(coro));
Coroutine_reset(coro, run_again);
assert(Coroutine_isInit(coro));
res = (char*)Coroutine_resume(coro, "hello");
assert(Coroutine_isPend(coro));
printf("message from run_again: %s\n", res);
res = (char*)Coroutine_resume(coro, "world");
assert(Coroutine_isEnd(coro));
printf("message from run_again: %s\n", res);
Coroutine_close(coro);
}
int main() {
test();
return 0;
}
输出结果如下所示:
>> now inside RUN <<
message from run: hello
message from run: OK
message from run: world
message from run: done
>> now inside RUN_AGAIN <<
message from run_again: hello
message from run_again: OK
message from run_again: world
message from run_again: done
这个示例主要用于验证协程的有效性,可以发现我们轻而易举地实现了在test和run之间的切换,甚至是在run运行结束后,将协程重新绑定到run_again继续运行,这里有很多技巧,待大家发掘,或许可以参考下python以及lua中关于协程的一些应用模式,Coroutine提供的API基本和lua中的coroutine一致,这次修正特别增加了yield和resume的参数和返回值支持。
请注意,栈的大小需要用户自己估计,但是最小不得少于系统的页面大小,当前的实现固定为4KB,后续版本中我会通过读取sysconf来确定PAGESIZE。个人不建议各位使用协程实现一些深度递归(无法通过尾递归优化),因为这会占用大量的栈空间,坦白说,如此还真不如用thread干脆。
0x04 结尾
Coroutine下一阶段的目标:
- 提供对arm平台的支持(主要是安卓平台)
- 改进性能
关于栈的自动化扩展机制已经有解决方案了,其中一种方案是每次切换都复制栈,似乎libconcurrency就是这么做的,但是我认为这个比较傻,假设我由5MB的栈内容,你每次都去复制一遍?So keep it stupid!
我也思考了一种解决方案,成本集中在Coroutine_new,之后的开销只有在栈扩展时才有影响,但是实现这个机制的成本已经远超过了Coroutine库的规模,可以想象一下,它的规模有多广:
- 你需要关注coroutine main函数本身
- 你需要关注任何在coroutine main函数中调用的函数
- 你需要关注任何位于第三级以及之后级别的函数依赖
- 你需要区分在Coroutine中和非Coroutine中所有上述依赖的区别
我将其作为未来的潜在研究目标,暂时不会提交到主干中。
欢迎各位试用Coroutine库,如果你觉得它好用,还望赏颗star。
如发现任何bug,请尽快通过github反馈,我会在第一时间解决,当然,也欢迎各位提交pull request。