Coroutine for C发布

有一段时间没发博客了,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库的特性:

  1. 不依赖setjmp及ucontext
  2. 跨平台(x86 & amd64 with gcc/clang,不含mac os x)
  3. 对称式协程
  4. 支持栈以及寄存器的dump
  5. 支持协程嵌套

基本实现方式和之前文章中描述的大致相同,只不过它不再依赖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种状态:

  1. INIT: 协程初始状态,此时尚未执行main
  2. PEND: 协程挂起
  3. RUN: 协程运行中
  4. END: 协程main函数执行结束

状态转换图如下所示:

请输入图片描述

它们会对协程的运行产生一定的约束,避免出现不必要的错误,例如:

  1. reset操作只能对处于END状态的协程实施
  2. yield操作只能对处于RUN状态的协程实施
  3. resume操作只能对处于PEND/INIT状态的协程实施

main的类型为coro_cb_t,它是一个函数指针,声明如下:

typedef void* (*coro_cb_t)(struct coroutine*, void*);

这里使用coroutine作为参数的有2大原因:

  1. yield和resume操作均需要coro变量作为参数
  2. res可以用以保存上下文数据,至于参数和返回值,请按平常的方式使用

0x02 相关函数

Coroutine Coroutine_new(size_t)
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

void Coroutine_bind(Coroutine)

  • 绑定协程的main函数,协程不可为RUN或PEND

void Coroutine_yield(Coroutine)
void* Coroutine_yield(Coroutine, void*)

  • 跳出当前main函数,其返回值为Coroutine_resume的参数,参数为Coroutine_resume的返回值

void Coroutine_resume(Coroutine)
void* Coroutine_resume(Coroutine, void*)

  • 跳入挂起的main函数,其返回值为Coroutine_yield的参数或main函数的返回值,参数为Coroutine_yield的返回值或者main函数的参数,取决于当前协程的状态

void Coroutine_reset(Coroutine)
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下一阶段的目标:

  1. 提供对arm平台的支持(主要是安卓平台)
  2. 改进性能

关于栈的自动化扩展机制已经有解决方案了,其中一种方案是每次切换都复制栈,似乎libconcurrency就是这么做的,但是我认为这个比较傻,假设我由5MB的栈内容,你每次都去复制一遍?So keep it stupid!

我也思考了一种解决方案,成本集中在Coroutine_new,之后的开销只有在栈扩展时才有影响,但是实现这个机制的成本已经远超过了Coroutine库的规模,可以想象一下,它的规模有多广:

  1. 你需要关注coroutine main函数本身
  2. 你需要关注任何在coroutine main函数中调用的函数
  3. 你需要关注任何位于第三级以及之后级别的函数依赖
  4. 你需要区分在Coroutine中和非Coroutine中所有上述依赖的区别

我将其作为未来的潜在研究目标,暂时不会提交到主干中。

欢迎各位试用Coroutine库,如果你觉得它好用,还望赏颗star。

如发现任何bug,请尽快通过github反馈,我会在第一时间解决,当然,也欢迎各位提交pull request。

说两句: