基于setjmp的协程厍实现

开学有一周了,博客还是要写的,今后可以写点从paper中汲取到的技术,不过请放心,不会是纯理论的,毕竟这不是我的风格。

继上回《谈一谈setjmp和longjmp》之后,我创建了一个新的分类——编程技法,总觉得把好好的一篇文章放到Linux分类下,并不能很好地凸显其价值。

今天就把关于协程的内容补完,还是主要以思想为主,细枝末节部分,请各位根据需求自行处理。

0x00 协程的领域特征

协程到底是什么?各位读者可以先读一读我之前的文章《D语言的协程——Fiber》,里面介绍了协程的基本特点和通用的操作方式。简而言之,协程是位于user-space的进程切换,我这么说是有一定依据的,这几天在看xinu操作系统的源码,发现其ctxsw的实现和协程的实现如出一辙。

既然提到了切换的问题,那么首先需要解决一个问题,为何要进行切换?

这个问题能够在异步IO中找到答案,有过相关开发经验的朋友一定知道有EAGAIN和EWOULDBLOCK这俩恶心的errno存在,它们的作用就是告知当前IO设备忙或者缓冲区已经达到高/低水位的阀值了,需要过一会再来取数据。当然,我个人并不认为它们属于错误,只能说是一种提醒,它们的存在本身并没有什么问题,关键是这给其之后的操作带来了很大的麻烦,增加了一定的复杂度。

我们以web服务器为例,当服务器从socket读取数据后,需要进行http协议的解析,如果说存在EAGAIN这种情况,那么我们的解析器将会变成一个状态机,而且是比较复杂的那种,因为我们无法确定到底能够读到多少的数据,因此需要记录解析的当前位置。假如我们在这里加入了协程,形成一个中间层,这样服务器就能够在EAGAIN,buf满,buf空等情况下切出,在buf获取一定数据后再切入,如此能够极大地简化http解析器,这就是一个简单的线性解析。

从上述描述和中,我们可以得知协程最主要解决的就是状态切换的问题,它能够通过简单的上下文操作来确保后续操作的连贯性,这是一种典型的控制复杂度的方法。如果大家想进一步研究协程,可以看一下这篇paper

0x01 难点分析

《谈谈setjmp和longjmp》中,我们提到了如何使用setjmp来实现跨函数的跳转,以及跳转使用不当造成的问题,同时我们也分析了setjmp和longjmp的基本实现,在阅读本文之前,各位需要熟悉setjmp/longjmp的操作及其内部机制,这一部分极易造成难以理解的问题。

上文中,我们分析了setjmp的不足,由于栈帧的限制,无法实现类似yield的操作。那么要真正实现协程,我们就需要先克服这个问题。

什么是完整的上下文?

完整的上下文,包含现场的寄存器和栈帧。我们说过,共享的栈必然会造成问题,可以联想为何进程会有独立的栈空间。我查找了一下相关的解决方案,总体而言有两种:

  1. 独立的栈空间
  2. 栈的保存与恢复

前者整体的效率较高,它的特点就是在协程创建之初就为其分配独立的栈空间,并直接将sp定位到栈顶,因为不涉及任何栈的拷贝,因此效率很高,当然它也有缺点,这种方案无法在其中进行深度递归,会直接“爆”掉;后者的协程在执行时用的是共享的栈,只不过在切换时我们会把当前栈的内容保存起来,如此一来只要进程的栈能够承受的递归,协程也一样能够接受,只不过由于拷贝操作的存在,效率相对会较低。

在本文的实现中,我们采用第一种实现方式,因为我并不期望它能够普适。

0x02 实现细节

尽管我们在之前提到过协程很适合解决异步IO的问题,也提到了切换,但是这并不意味着我们就会将协程和epoll结合。我个人的习惯是控制库的粒度,但又为未来的整合提供一定的空间。

在这里我们采用的是一种非对称协程的实现方式,所谓对称与非对称,差别在于切换函数,如果采用了yield,resume独立的函数来实现协程的切换,那么我们就称之为“非对称”,而如果使用诸如xinu、libco等类似的实现,仅用一个函数进行切换,则称之为“对称”。在这里我们避免关于对称与非对称的争论,我只是觉得非对称的实现在添加些新的特性时更加方便,就采用了这种设计。

好,那么就先来描述如何实现独立的栈,以及sp指针的切换,这里用的是setjmp.h中的jmp_buf,但是这个结构体的size为200,似乎有自己实现的必要,请看相关代码:

void coroutine_init(coroutine_t coro, jmp_buf* ctx, coro_cb_t main) {
    if(setreg(coro->env)) {
        __bridge();
    }
    coro->ctx = ctx;
    coro->main = main;
    coro->sp = (void*)coro->env->__jmpbuf[0];
    coro->env->__jmpbuf[0] = (long)coro->top;
    void* keys = coro->stk + (STK_DEFAULT_SIZE - sizeof(void*) * 12);
    ((void**)keys)[0] = coro;
}

其实创建一个栈是相当简单的事情,但是需要注意大小端的问题和内存对其的问题。关于sp设置,我们需要在这之前获取当前协程的寄存器内容,至于保存的寄存器范围和技巧,我在之前的博客中有已经所描述。

static void __bridge() {
    coroutine_t coro = (coroutine_t)__keys()[0];
    coro->main(coro);
}

请注意,这里我们必读调用一个无参的__bridge函数,由于在进入__bridge之前,已经涉及到了切换,因此我们无法保证栈的内容是否已经被破坏,因此这里最保险的方式就是调用一个无参的桥接函数。

但是又有一个问题,因为没有任何参数,并且我们并未使用全局变量,那么如何将coroutine的指针传到桥接函数内呢?大家已经注意到了__keys这个函数,我们使用的解决方案比较简单粗暴,就是在sp之前分配一定的空间,用来保存需要传递的变量,可以从 sizeof(void*) * 12 得知,我们的实现允许传递至多12个指针,我想应该够用了。关键是如何定位到这些指针存储的位置呢?得益于内存对齐,我们可以轻易地从一个函数内部找到这个对齐点,具体实现,请看下方的__keys函数,没有过多的技巧,就不费笔墨详细解释了,这也是一种常用的计算方式。

static void** __keys() {
    void* zone;
    zone = (void*)(((long)&zone + PAGE_SIZE - 1) / PAGE_SIZE * PAGE_SIZE);
    zone += -sizeof(void*) * 12;
    return (void**)zone;
}

至此协程的核心部分写完了,我想余下的yield和resume绝对是难不倒大家的,无非就是一点macro。

0x02 本实现的局限性

目前这种实现还是比较简单的,存在的问题也颇多,比如:

  1. 如何确定stackoverflow
  2. 如何确定协程是否已经执行结束
  3. 协程结束后如何复原堆栈以供后续使用
  4. 如何实现栈的自动伸缩,以在一定程度上适应深度递归

对于第一个问题,或许我们可以通过mprotect来解决,不过这部分细节我也没仔细看,有待验证。至于2、3都是实现方面的问题,只要我们能够确定协程执行结束,大家就能够通过修改sp指针实现栈的重置,而前者并不是一个难点。

栈的自动收缩确实是一个值得研究的问题,不过我们也可以在yield和resume操作中采用一定的手段来尽可能缓解这个问题,要根除的话,还是需要在下层构建一个兼容层,比如依靠编译器植入检测代码。只不过是否值得这么做,就见仁见智了,你要是不用yield和resume,仅仅用协程来做常规的深度递归,这不是自找没趣吗?或许我们可以将栈空间大小的设置责任推给使用者,这也是一个很好的方案,state-threads就是这么做的。

最后,还有一点需要指明,协程并不是万灵药,协程之间的切换是有代价的,你也可以设想下用协程来处理C10K问题,光协程的内存占用有多少?因此选择使用协程前一定要谨慎,看看是否值得为了复杂度来承受上述的代价。

说两句: