有栈协程实现原理

协程

进程、线程

进程地址空间

1. 栈：栈用于维护函数调用的上下文，包括函数的参数，局部变量等等。

2. 堆：用来容纳程序中动态分配的内存区域，当程序使用malloc和new分配的内存就来自于堆里

3. 可执行文件映像。

4. 保留区，是对内存中受到保护而禁止访问的内存区域的总称。

栈的增长方式

1. 函数的返回地址和参数

2. 临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量

3. 保存的上下文：包括在函数调用前后需要保存不变的寄存器的值

[E|R]SP表示esp或者rsp寄存器，esp表示32位x86架构下的栈指针寄存器，rsp表示64位x86架构下的栈指针寄存器，同理于[E|R]BP。 帧指针并不是必须的, x86-64过程中的栈帧通常有固定的大小，在调用过程中栈指针保持固定的位置，使得可以通过相对于栈指针的偏移量来访问数据^1。

int foo(int m, int n){
  int a = 0; // #i
  ....
}

1. 把所有或一部分参数加入栈中，如果有其他参数没有入栈，那么使用某些寄存器传递

2. 把当前指令的下一条指令地址压入栈中

3. 跳转到函数体执行:

4. 把[e|r]bp压入栈中，指向上一个函数堆栈帧中的帧指针的位置

5. 保存调用前后需要保存不变的寄存器的值

6. 将局部变量压入栈中

7. ...

线程

线程上下文切换

实现协程的理论依据

ucontext

typedef struct ucontext {
  struct ucontext *uc_link;
  sigset_t         uc_sigmask;
  stack_t          uc_stack;
  mcontext_t       uc_mcontext;
  ...
} ucontext_t;

  int getcontext(ucontext_t *ucp);

 void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...);

int setcontext(const ucontext_t *ucp);

 int swapcontext(ucontext_t *oucp, ucontext_t *ucp);

#include <ucontext.h>
#include <stdio.h>

int func(void *arg) {
  puts("this is func");
}

void coroutine_test() {
  char stack[1024 * 128];
  ucontext_t child, main;
  // 获取当前上下文
  getcontext(&child);

  // 分配栈空间 uc_stack.ss_sp 指向栈顶
  child.uc_stack.ss_sp = stack;
  child.uc_stack.ss_size = sizeof(stack);
  child.uc_stack.ss_flags = 0;
  // 指定后继上下文
  child.uc_link = &main;
  // child.uc_link = NULL;

  makecontext(&child, (void (*)(void))func, 0);

  //切换到child上下文，保存当前上下文到main
  swapcontext(&main, &child);
  // 如果设置了后继上下文，func函数指向完后会返回此处 如果设置为NULL，就不会执行这一步
  puts("this is coroutine_test");
}

int main() {
  coroutine_test();
  return 0;
}

this is func
this is coroutine_test

coroutine实现

coroutine例子

#include "coroutine.h"
#include <stdio.h>

struct args {
    int n;
};

static void
foo(struct schedule * S, void *ud) {
    struct args * arg = ud;
    int start = arg->n;
    int i;
    for (i=0;i<5;i++) {
        printf("coroutine %d : %d\n",coroutine_running(S) , start + i);
        // 切出当前协程
        coroutine_yield(S);
    }
}

static void
test(struct schedule *S) {
    struct args arg1 = { 0 };
    struct args arg2 = { 100 };

    // 创建两个协程
    int co1 = coroutine_new(S, foo, &arg1);
    int co2 = coroutine_new(S, foo, &arg2);
    printf("main start\n");
    while (coroutine_status(S,co1) && coroutine_status(S,co2)) {
        // 使用协程co1
        coroutine_resume(S,co1);
        // 使用协程co2
        coroutine_resume(S,co2);
    }
    printf("main end\n");
}

int
main() {
    // 创建一个协程调度器
    struct schedule * S = coroutine_open();
    test(S);
    // 关闭协程调度器
    coroutine_close(S);
    return 0;
}

核心对象

1. struct schedule* S 协程调度器

 struct schedule {
     char stack[STACK_SIZE]; // 运行时栈，此栈即是共享栈
     ucontext_t main; // 主协程的上下文
     int nco;        // 当前存活的协程个数
     int cap;        // 协程管理器的当前最大容量，即可以同时支持多少个协程。如果不够了，则进行2倍扩容
     int running;    // 正在运行的协程ID
     struct coroutine **co; // 一个一维数组，用于存放所有协程。其长度等于cap
 };

协程状态

READY -> RUNNING

// coroutine_resume
switch(status) {
    case COROUTINE_READY:
        //初始化ucontext_t结构体,将当前的上下文放到C->ctx里面
        getcontext(&C->ctx);
        // 将当前协程的运行时栈的栈顶设置为S->stack，每个协程都这么设置，这就是所谓的共享栈。（注意，这里是栈顶）
        C->ctx.uc_stack.ss_sp = S->stack;
        C->ctx.uc_stack.ss_size = STACK_SIZE;
        C->ctx.uc_link = &S->main; // 如果协程执行完，将切换到主协程中执行
        S->running = id;
        C->status = COROUTINE_RUNNING;

        // 设置执行C->ctx函数, 并将S作为参数传进去
        uintptr_t ptr = (uintptr_t)S;
        makecontext(&C->ctx, (void (*)(void)) mainfunc, 2, (uint32_t)ptr, (uint32_t)(ptr>>32));

        // 将当前的上下文放入S->main中，并将C->ctx的上下文替换到当前上下文
        swapcontext(&S->main, &C->ctx);
        break;
}

RUNNING -> SUSPEND

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);
}

SUSPEND -> RUNNING

case COROUTINE_SUSPEND:
        // 将协程所保存的栈的内容，拷贝到当前运行时栈中
        // 其中C->size在yield时有保存
        memcpy(S->stack + STACK_SIZE - C->size, C->stack, C->size);
        S->running = id;
        C->status = COROUTINE_RUNNING;
        swapcontext(&S->main, &C->ctx);
        break;

运行栈保存

static void
_save_stack(struct coroutine *C, char *top) {
    // 这个dummy很关键，是求取整个栈的关键
    // 这个非常经典，涉及到linux的内存分布，栈是从高地址向低地址扩展，因此
    // S->stack + STACK_SIZE就是运行时栈的栈底
    // dummy，此时在栈中，肯定是位于最底的位置的，即栈顶
    // top - &dummy 即整个栈的容量
    char dummy = 0;
    assert(top - &dummy <= STACK_SIZE);
    if (C->cap < top - &dummy) {
        free(C->stack);
        C->cap = top-&dummy;
        C->stack = malloc(C->cap);
    }
    C->size = top - &dummy;
    memcpy(C->stack, &dummy, C->size);
}

goroutine实现

参考文献

1. Operating Systems

2. 程序员的自我修养