c/c++ 中的协程

Conway Melvin E 1963的文章《Design of a Separable Transition-Diagram Compiler》提出协程是可以挂起 (suspend) 和恢复 (resume) 的子例程 (subroutine), 为了实现这一点需要保存上下文 (context)

如下图 foo 和 bar 两个协程能多次的挂起和恢复, 每次恢复都恢复到上次挂起时的下条语句位置:

从控制流 (control flow) 的角度来说是一种语言层面 (language-level) 的控制流, 进程和线程中的逻辑控制流是由操作系统内核调度的, 而协程则是在语言层由程序员编写

下面我们就对比一下进程, 线程和协程

本文中提到的线程一般指的是 linux 2.6 后 glibc 中的 NPTL (Native POSIX Threads Library) 实现的线程, 一个用户态线程 posix thread 对应一个内核态轻量级进程 light-weight process

操作系统用 task_struct 这个结构体来描述一个进程或线程 (轻量级进程)

task_struct 有两个 id, pid 和 tgid, 类型均为 pid_t (x86_64 下为 int)

• pid 可通过 syscall(SYS_gettid) 获取
• tgid 可通过 getpid(2) 获取, 意为 thread group id, 即同一进程下的不同线程有不同的 pid 和相同的 tgid
• clone(2) 中 flags 如设为 CLONE_THREAD, 意为创建线程 (轻量级进程), 创建出来的线程的 tgid 和调用这个函数的进程的 tgid 一致

#include <sched.h>

int clone(int (*fn)(void *), void *child_stack, int flags, void *arg, ...
            /* pid_t *ptid, void *newtls, pid_t *ctid */ );

同一线程组 (进程) 下的线程共享虚拟内存 (virtual address space), 文件描述符表 (table of file descriptors) 和信号处理表 (table of signal handlers)

信号处理是 process-wide 的, 即对整个线程组产生影响, 但每个线程可以有自己的 signal mask, 信号可以通过 kill(2) 或 tgkill(2) 发送给进程或者线程 (a signal may be process-directed or thread-directed)

协程可以根据 stackfulness 分为有栈和无栈, 根据上下文是否可以作为参数传递分为 first-class continuation 或非 first-class continuation, 根据协程间的关系分为对称和非对称的

stackful

resume 协程时将栈指针指向 user 在堆上运行时创建的一块内存, 可能会破坏 return stack buffer 跳转预测

stackless

不将栈指针指向堆上创建的内存

对于阻塞调用:

• stackful 改变阻塞调用的行为, 让内核调度改为线程内调度
• stackless 将剩余部分定义为一个函数, 注册这个函数为回调函数, 当前函数返回

c/c++ 中自带的 setjmp 和 longjmp 就可以看做是一种协程, 其上下文为 8 个寄存器的值, 存在 __jmp_buf 这个结构体中

/* callee saved */
struct __jmp_buf {
        unsigned long __rbx;
        unsigned long __rsp;    /* post-return */
        unsigned long __rbp;
        unsigned long __r12;
        unsigned long __r13;
        unsigned long __r14;
        unsigned long __r15;
        unsigned long __rip;    /* return address */
};

setjmp 将上下文保存在 __jmp_buf 中

kernel_setjmp:
        pop  %rsi			# Return address, and adjust the stack
        xorl %eax,%eax			# Return value
        movq %rbx,(%rdi)
        movq %rsp,8(%rdi)		# Post-return %rsp!
        push %rsi			# Make the call/return stack happy
        movq %rbp,16(%rdi)
        movq %r12,24(%rdi)
        movq %r13,32(%rdi)
        movq %r14,40(%rdi)
        movq %r15,48(%rdi)
        movq %rsi,56(%rdi)		# Return address
        ret

longjmp 将 __jmp_buf 中的值恢复到寄存器

kernel_longjmp:
        movl %esi,%eax			# Return value (int)
        movq (%rdi),%rbx
        movq 8(%rdi),%rsp
        movq 16(%rdi),%rbp
        movq 24(%rdi),%r12
        movq 32(%rdi),%r13
        movq 40(%rdi),%r14
        movq 48(%rdi),%r15
        jmp *56(%rdi)

达夫设备源自 Duff 尝试使用 switch 和循环对下面这段代码做 unrolling 优化

https://swtch.com/duffs-device/td-1983.txt

send(to, from, count)
register short *to, *from;
register count;
{
        do
                *to = *from++;
        while(--count>0);
}

使用循环展开后:

send(to, from, count)
register short *to, *from;
register count;
{
        register n=(count+7)/8;
        switch(count%8){
        case 0:	do{	*to = *from++;
        case 7:		*to = *from++;
        case 6:		*to = *from++;
        case 5:		*to = *from++;
        case 4:		*to = *from++;
        case 3:		*to = *from++;
        case 2:		*to = *from++;
        case 1:		*to = *from++;
                }while(--n>0);
        }
}

PuTTY 的作者 Simon Tatham 根据达夫设备的特性实现了一种无栈协程

int function(void) {
    static int i, state = 0;
    switch (state) {
        case 0: /* start of function */
        for (i = 0; i < 10; i++) {
            state = 1; /* so we will come back to "case 1" */
            return i;
            case 1:; /* resume control straight after the return */
        }
    }
}

这个协程的 context 为放在 .bss 上的两个 int, 每次进入这个函数时都会根据这两个 int 跳转到不同的语句, 由于使用到了多个线程可访问到的静态数据, 所以这个函数是不可重入的

libco 是微信开源的 c++ 协程库, 属于有栈非对称的协程, 其上下文为 14 个寄存器的值和一块运行时在堆上创建的栈, 寄存器的值保存在一个叫 regs 的数组中:

rsp 指向的是返回的地址(rax), 即上下文切换语句的下一行的汇编指令的第一条

一个协程对应着在堆上创建的一个栈, 也可以使用共享栈模式, 即多个协程共享同一个栈, 但任意时刻只有一个协程在真正执行, 共享栈需要保存和恢复, 相当于用时间换空间

协程上下文的切换在 libco 中使用汇编实现

主协程一直不断地从名为 active_list 的队列中取出就绪的协程恢复, 时间轮中的超时事件会被加到 active_list 中, epoll_wait 返回的事件 events[i].data.ptr 会被加到 active_list 中, 此外也可以主动将一些想要恢复的协程加到 active_list 中, 如官方的生产者消费者例子中

我们可以对比看下生产者消费者问题分别用进/线程和协程如何解决:

• 进程: 通过 futex 同步, 映射到同一个物理内存地址的 futex 变量
• 线程: 通过 futex 同步, 共享虚拟内存空间中的 futex 变量
• 协程: 通过用户定义的变量同步

linux 也提供 ucontext 这个结构体用来便于我们来保存协程上下文, 同时提供了切换上下文的函数, 而不用像 libco 那样自己编写汇编:

#include <ucontext.h>
void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...);
int swapcontext(ucontext_t *oucp, ucontext_t *ucp);
int getcontext(ucontext_t *ucp);
int setcontext(const ucontext_t *ucp);

上下文比 libco 的多了 sigmask 和浮点数

kernel ucontext

user ucontext

startcontext

swapcontext

/* Userlevel context.  */
typedef struct ucontext_t
  {
    unsigned long int __ctx(uc_flags);
    struct ucontext_t *uc_link;
    stack_t uc_stack;
    mcontext_t uc_mcontext;
    sigset_t uc_sigmask;
    struct _libc_fpstate __fpregs_mem;
    unsigned long int __ssp[4];
  } ucontext_t;

ucontext 也是有栈协程, 协程的栈如下图:

This allows for sequential code that executes asynchronously (e.g. to handle non-blocking I/O without explicit callbacks), and also supports algorithms on lazy-computed infinite sequences and other uses.

cppreference coroutine 页面上介绍协程的用处是可以编写异步执行的顺序代码, 如减少异步事件驱动中的显式回调函数注册, c++ 20 标准库中的使用的是无栈协程, 主要有三个关键字:

• 使用 co_await 来 suspend 直到 resumed
• 使用 co_yield 来 suspend 并返回一个值
• 使用 co_return 来完成并返回一个值

我们通常定义协程返回对象和可等待体

asio 中有过三种协程, 基于达夫设备的简单的无栈协程, 基于 boost coroutine2 的有栈协程, 而 boost coroutine2 是基于 ucontext (或 boost 自己对 ucontext 的另外的实现), 基于 c++ 20 标准库协程的无栈协程

最后我们对比一下下面提到的几种协程(setjmp/longjmp, duff's device, libco, ucontext, c++20 coroutine, boost coroutine2) 的上下文

大部分的协程都将上下文保存到了堆上, 大小由 libco 的 128k 左右到几个 int 不等, 通常由实际应用场景决定, 如 libco 中没有浮点数寄存器而 ucontext 中有

协程是在用户态的一种非抢占式的调度, 提供了相对于线程颗粒度更细的并发 (fine-grained concurrency), 提高单个线程的能力, 但只用单个线程无法利用多核的优势实现并行

coroutine wikipedia

Design of a Separable Transition-Diagram Compiler

Art of Computer Programming - Volume 1

asio coroutine

clone(2) — Linux manual page

Page Table Management

take on c++20 coroutine