协程原理

协程的本质都是通过修改 ESP 和 EIP 指针来实现的。其理论上还是单线程在运行，要想实现真正的并发，其实是需要多个CPU才能的。并发是并行的充分条件，并发是在程序级别上实现的，而并行是在机器级别上实现的，要想实现并行，程序上必须以并发实现，但是程序上实现了并发并不代表是真正的并行，当只有一个CPU的时候还是属于单线程。

程序在CPU上运行时依赖2个条件：

堆栈指针 ESP 寄存器，指向当前指令需要的数据

指令指针 EIP 寄存器，指向当前需要运行的指令

这两个寄存器指针的改变可以修改当前需要加载到 CPU 运行的指令和数据，当某个操作陷入到耗时的等待中时，通过修改这两个指针即可让出CPU，交给其他的任务去使用，每个任务都必须主动的让出CPU，然后等待下一次的调度来继续未完成的任务，这样就可以最大程度的利用CPU，当一个任务等待过程非常短的时候，就出现了多个任务并行运行的效果，也就是协程。
目前常见的协程库有云风的coroutine , libtask 库，腾讯的 libco ，以下以最简单的 coroutine 库讲解一下。

云风的协程库实现

C语言实现协程主要依赖于一组 glibc 库里的上下文操作函数：

getcontext()  : 获取当前context
setcontext()  : 切换到指定context
makecontext() : 设置 函数指针 和 堆栈 到对应context保存的sp和pc寄存器中,调用之前要先调用 getcontext()
swapcontext() : 保存当前context，并且切换到指定context

可以看下 makecontext 的原理

void makecontext(ucontext_t *uc, void (*fn)(void), int argc, ...)
{
    int i, *sp;
    va_list arg;
    // 将函数参数陆续设置到r0, r1, r2 .. 等参数寄存器中
    sp = (int*)uc->uc_stack.ss_sp + uc->uc_stack.ss_size / 4;
    va_start(arg, argc);
    for(i=0; i<4 && i<argc; i++)
        uc->uc_mcontext.gregs[i] = va_arg(arg, uint);
    va_end(arg);
    // 设置堆栈指针到sp寄存器
    uc->uc_mcontext.gregs[13] = (uint)sp;
    // 设置函数指针到lr寄存器，切换时会设置到pc寄存器中进行跳转到fn
    uc->uc_mcontext.gregs[14] = (uint)fn;
}

因此我们可以知道一个协程就是一组包含了上下文运行环境和一个私有栈的结构。在设计时一个协程需要有以下数据成员

struct coroutine {
    coroutine_func func;    //协程运行主体函数
    void *ud;               //func 的参数
    ucontext_t ctx;         //该协程的上下文信息
    struct schedule * sch;  //对应的调度器
    ptrdiff_t cap;          //协程容量
    ptrdiff_t size;         //协程实际大小
    int status;             //运行状态： 初始化->
    char *stack;            //栈
};

由于每个协程需要自己主动让出CPU，至于让出的CPU交给谁运行，是由调度器来决定的。所以还需要一个调度者来管理这些协程，包括保存，切换协程等。

struct schedule {
    char stack[STACK_SIZE]; //栈大小
    ucontext_t main;        //当前上下文
    int nco;                //协程数
    int cap;                //协程栈容量
    int running;            //是否正在运行
    struct coroutine **co;  //协程数组
};

协程的运行是一个有限状态机，可以简单的将状态分为以下四种：

#define COROUTINE_DEAD 0
#define COROUTINE_READY 1
#define COROUTINE_RUNNING 2
#define COROUTINE_SUSPEND 3

协程操作集：

void coroutine_resume(struct schedule *, int id);//恢复协程的运行，从主协程跳到子协程
void coroutine_yield(struct schedule *);         //挂起当前协程，让出CPU，从子协程跳到主协程

最开始初始化一个协程时，状态都是READY 的，协程调度器的状态是非 running 的调度器主要有以下操作：coroutine_resume() : 恢复某个协程的运行。

void coroutine_resume(struct schedule * S, int id) {
    assert(S->running == -1);
    assert(id >=0 && id < S->cap);
    struct coroutine *C = S->co[id];
    if (C == NULL)
        return;
    int status = C->status;
    switch(status) {
    case COROUTINE_READY:
        //ready 状态下，第一次切换，要设置该协程的栈空间。
        //1. 初始化当前的上下文
        getcontext(&C->ctx); 
        //2. 指定执行函数，
        C->ctx.uc_stack.ss_sp = S->stack;
        C->ctx.uc_stack.ss_size = STACK_SIZE;
        //3. 指定执行完之后要调转的地方
        C->ctx.uc_link = &S->main;
        S->running = id;
        C->status = COROUTINE_RUNNING;
        uintptr_t ptr = (uintptr_t)S;
        //4. makecontext() 创建协程
        makecontext(&C->ctx, (void (*)(void)) mainfunc, 2, (uint32_t)ptr, (uint32_t)(ptr>>32));
        //5. swapcontext() 将当前上下文保存在 main 中，并切换到 C->ctx 中去执行
        swapcontext(&S->main, &C->ctx);
        break;
    case COROUTINE_SUSPEND:
        //恢复运行栈
        memcpy(S->stack + STACK_SIZE - C->size, C->stack, C->size);
        S->running = id;
        C->status = COROUTINE_RUNNING;
        //suspend 状态就很简单了，直接用 swapcontext() 切换到 C->ctx 中去执行。
        swapcontext(&S->main, &C->ctx);
        break;
    default:
        assert(0);
    }  
}

协程的初始化和切换操作都很简单，主要就是调用 getcontext(), makecontext() , swapcontext() 。

最难理解的是如何保存和恢复协程的运行栈。

在此先看下linux的内存布局，程序的堆栈是向下生长的，最低部从下到上依次是 text 段，data 段，bss 段之类的。

保存现场

协程在从 RUNNING 到 COROUTINE_SUSPEND 状态时需要保存运行栈，即调用 coroutine_yield 之后挂起协程，让出CPU的过程。

void coroutine_yield(struct schedule * S) {
    int id = S->running;
    assert(id >= 0);
    struct coroutine * C = S->co[id];
    assert((char *)&C > S->stack);
    // 为了在下次回到这个协程时能回到之前的执行点继续执行，必须要保存其执行的上下文
    _save_stack(C,S->stack + STACK_SIZE);
    C->status = COROUTINE_SUSPEND;
    S->running = -1;
    swapcontext(&C->ctx , &S->main);
}

coroutine_yield 调用 _save_stack 来保存运行栈：

static void _save_stack(struct coroutine *C, char *top) {
    printf("top:%p n", top);
    //获取当前栈底，top 是栈顶，top-dummy 即该协程的私有栈空间
    char dummy = 0; 
    printf("dummy:%p n", &dummy);
    assert(top - &dummy <= STACK_SIZE);
    printf("stack_size :%d n", top-&dummy);
    //如果协程私有栈空间大小不够放下运行时的栈空间，则要重新扩容
    if (C->cap < top - &dummy) {
        free(C->stack);
        C->cap = top-&dummy;
        C->stack = malloc(C->cap);
    }
    C->size = top - &dummy;
    //从栈底到栈顶的数据全都拷到 C->stack 中
    memcpy(C->stack, &dummy, C->size);
}

top 代表当前协程运行栈的栈顶，从 coroutine_yield 我们知道

top = S->stack + STACK_SIZE

为什么是 S->stack + STACK_SIZE 呢，因为该协程在初始化的时候设置为：

c
C->ctx.uc_stack.ss_sp = S->stack;
C->ctx.uc_stack.ss_size = STACK_SIZE;
makecontext(&C->ctx, (void (*)(void)) mainfunc, 2, (uint32_t)ptr, (uint32_t)(ptr>>32));


即表示该协程栈的栈顶设置为 S->stack，mainfunc 的运行使用 S->stack 作为栈顶，大小为 STACK_SIZE 。

由此可以看到，schedule 的 stack[STACK_SIZE] 是子协程运行的公共栈空间，但是每个协程的栈不一样，所以需要单独建立一个私有栈空间来保存执行现场。

下面回到_save_stack函数

C->cap表示该控制结构对应的协程的私有栈空间的大小，因此

if(C->cap < top - &dummy)

的作用是判断该用户协程的私有栈空间能否大于它运行时栈空间。前面说过top 表示栈顶，而dummy表示该用户协程当前的栈底，所以 top-dummy 就表示该用户协程运行时栈所占空间。如果用来保存私有栈的 C->stack 的大小不能放下运行时栈空间，则需要重新申请。

将运行时栈的数据全部拷贝到该协程的C->stack中，这样，以后别的协程使用S->stack做运行时栈空间时，就不会覆写掉该协程原来栈中的数据了。

memcpy(C->stack, &dummy, C->size);

恢复现场

接下来再看协程从 SUSPEND 到 RUNNING 状态时，如何恢复当时的运行栈，由于C 的运行时栈空间始终是在

S->main中的，因此恢复栈空间，其实就是将各自私有的C->stack 空间中的数据恢复到S->main中：

memcpy(S->stack + STACK_SIZE - C->size, C->stack, C->size);

最后保存和恢复均要注意栈的生长方向

memcpy(C->stack, &dummy, C->size);//保存
memcpy(S->stack + STACK_SIZE - C->size, C->stack, C->size); //恢复

资料：

http://www.chenzhenianqing.cn/articles/1204.html

http://blog.csdn.net/waruqi/article/details/53201416

打造业务零入侵的自用协程库(待续)

为了将协程库合并到业务中，首先肯定不能让业务自己调用yield，一个是对使用者的要求高，一个是对现有业务代码的侵入性太高。实际上考虑到现实场景，真正需要协程切换的地方无非是耗时的IO 操作，而分布式的IO 操作基本上就是网络请求，不论是数据库也好还是业务RPC也好，如果底层都是使用同一套事件触发机制，就可以尝试将协程无缝集成到底层中去，做到对业务代码零入侵。