iOS协程coobjc的设计篇-栈切换

协程 (Coroutine) 是一种轻量级的非抢占式用户态线程。本文主要介绍阿里开源的iOS协程框架coobjc的设计思考。

1. 协程简介

Subroutine: 子程序，可以理解为函数
Coroutine: 协程

Subroutine 的调用顺序是确定的，比如下图左A调B，B执行完毕返回， Subroutine调用和返回是通过压栈出栈来实现的。而Coroutine的调用则和Subroutine不同，比如下图右A调C, 但是在C执行过程中可能会suspend, 然后在其他时候再resume回来继续执行，也就是执行顺序是不确定的。 也就是Coroutine的重要特质: suspend 和 resume,  suspend也会叫做yield.


本图来自：https://llvm.org/devmtg/2016-11/Slides/Nishanov-LLVMCoroutines.pdf

另一个需要理解的概念就是非抢占式，这个概念也比较容易理解，意思就是这里的yield和resume不是抢占式执行的，是由代码主动控制的yield和resume。而不是像线程一样，由内核决定是否分配时间片给他。因此实现一个协程的核心就是实现yield和resume操作。

2. 有栈式 vs 无栈式

协程在实现上分为有栈协程(stackful coroutine)和无栈协程(stackless coroutine)。

首先要了解一个概念： 栈。
创建线程的时候，首先会给你分配一片内存作为它的数据栈。而在线程中执行的子程序(函数)的调用和返回的过程就是压栈和出栈的过程：

图例：一个调用栈： F -> G -> H

如果协程有自己的栈，那就是有栈协程; 如果没有，那就是无栈协程。像现有语言的实现中，Python, Kotlin, c++标准 等中就是定义的无栈协程， go语言中实现的是有栈协程。

有栈协程比较好理解，就是2个调用栈之间互相切换执行，就类似是2个独立的线程；那么无栈协程呢？ 无栈协程更轻量, 不会创建单独的栈空间, 只保存单个frame的状态(一般是到堆上)，然后frame可以多次恢复。

图例: LLVM无栈式协程代码编译示例。

无栈式协程一般需要通过编译器配合，将上图中左边代码编译成右边的带有多个标签的代码段，llvm.coro.begin 传入的内存作为保存当前frame的内存，通过实现方法可重入来达到代码暂停和恢复的效果。 而不使用编译器，通过一些switch case或者go to之类的封装或许可以做做一些简单的demo, 但是想要实用就比较有局限性了。

介绍了两种方式，简单列下他们的优缺点：

• 有栈式协程：

  • 优点： 实现简单；有自己的调用栈，可以在自己调用栈的任意地方yield/resume。
  • 缺点： 自定义栈空间 + 执行顺序不确定可能会踩到坑，比如基于runloop的ObjC的autorelease回收机制；比如backtrace、JSCore等代码里面栈地址检测逻辑。

• 无栈式协程：

  • 优点： 只要保持单个frame, 理论上性能更佳，使用更灵活。不会踩到上述有栈式协程的坑。
  • 缺点： 实现难度较大，需要从编译器入手。

其实上面的比较来看，无栈式协程是更完美的方案，但是牵涉到编译器到语言层面的改动较大，实现较复杂。我们coobjc还是选择了有栈式协程来实现，这也决定了我们会踩到上面说到的坑，不过我们都给出了其中一些问题目前的解决方案。

3. 栈切换

既然是做有栈式协程，那么就要解决最基本的需求： 栈切换。

实现 yield 和 resume 的本质就是从一个调用栈切换到另一个调用栈。切换是简单的，主要的工作就是调用栈上下文的保存和恢复。

网络上流行的切换栈的方案:

• ucontext 
• setjmp 和 longjmp

首先 ucontext 在iOS的arm架构上是没有实现的(x86上是有的)，用不了。 setjmp 和 longjmp 没有保存调用栈的操作，还需要自己写。那不如自己手写汇编来实现ucontext同样的逻辑就可以了。

有同学会疑惑不是有人用 setjmp和 longjmp实现了协程了么？ 这里引用云风blog中的一段话来说明下： “setjmp 也可以用来模拟 coroutine 。但是会遇到一个难以逾越的难点：正确的 coroutine 实现需要为每个 coroutine 配备一个独立的数据栈，这是 setjmp 无法做到的。虽然有一些 C 的 coroutine 库用 setjmp/longjmp 实现。但使用起来都会有一定隐患。多半是在单一栈上预留一块空间，然后给另一个 coroutine 运行时覆盖使用。当数据栈溢出时，程序会发生许多怪异的现象，很难排除这种溢出 bug 。” 原文： https://blog.codingnow.com/2010/05/setjmp.html

这2中方案在iOS上看起来都行不通，但是我们还有办法，那就是用汇编模拟ucontext的原理自己实现一套。

4. 汇编实现

既然是用汇编来模拟ucontext的实现，那么我们看到ucontext的几个方法：

int  getcontext(ucontext_t *ucp);
int  setcontext(const ucontext_t *ucp);
void makecontext(ucontext_t *ucp, (void *func)(), int argc, ...);
int  swapcontext(ucontext_t *oucp, const ucontext_t *ucp);

 
其实我们只需要使用汇编实现getcontext 和 setcontext就够我们来实现栈切换了。 makecontext用c来实现就好了， swapcontext其实就是对get和set的使用。

getcontext：是把当前寄存器里面的需要保存的信息保存到内存。
setcontext：从内存把寄存器的值恢复，然后跳转到需要恢复的地址执行。

做的事情非常简单，也就是寄存器的保存和恢复，但是要保存和恢复哪些寄存器呢？ 而且这两个方法的本身代码也要使用到寄存器，该怎么使用才不会污染到要保存的目标寄存器呢？

这里面需要的知识就是你要知道每个cpu架构的 调用约定 (Calling convention)。因为我们要从这个约定中获取这些关键信息：哪些寄存器是需要保存的，哪些寄存器是可以用的，那个是stack pointer，哪些是参数寄存器，压栈栈怎么执行的。 知道这些信息，我们才能在不污染到寄存器和栈的情况下做保存和恢复。

而这些文档一般都是公开的，直接Google搜索就可以了。如arm64的： http://infocenter.arm.com/help/topic/com.arm.doc.ihi0055b/IHI0055B_aapcs64.pdf

这里贴出了coobjc中arm64的 get_context 的实现来说明：

_coroutine_getcontext:
    stp    x18,x19, [x0, #0x090]
    stp    x20,x21, [x0, #0x0A0]
    stp    x22,x23, [x0, #0x0B0]
    stp    x24,x25, [x0, #0x0C0]
    stp    x26,x27, [x0, #0x0D0]
    str    x28, [x0, #0x0E0];
    stp    x29, x30, [x0, #0x0E8];  // fp, lr
    mov    x9,      sp
    str    x9,      [x0, #0x0F8]
    str    x30,     [x0, #0x100]    // store return address as pc
    stp    d8, d9,  [x0, #0x150]
    stp    d10,d11, [x0, #0x160]
    stp    d12,d13, [x0, #0x170]
    stp    d14,d15, [x0, #0x180]
    mov    x0, #0                   
    ret

其中只保存了 x19 - x30, sp, d8 - d15。 为什么呢？就是基于文档中的 5.1.1和5.1.2节中的内容：

"A subroutine invocation must preserve the contents of the registers r19-r29 and SP."

"Registers v8-v15 must be preserved by a callee across subroutine calls; the remaining registers (v0-v7, v16-v31)
do not need to be preserved (or should be preserved by the caller). Additionally, only the bottom 64-bits of each
value stored in v8-v15 need to be preserved1"

简单说明一下，就是说整形寄存器中的 r19-r29，sp是必须保存的； 浮点型寄存器中的v8-v15也是需要保存的，但是只有低64位需要保存，所以代码中用的是 d8-d15。

而我在代码中间用到了 x9 寄存器，在文档中也可以看到 r9-r15是 “Temporary registers”, 临时寄存器, 也就是可以在这里使用的。

5. 栈地址对齐

如果你看了 coobjc 的源码，可能会注意到在 makecontext 的 x86 实现中有这样奇怪的设置：

// arm64
uctx->GR.__sp = stackBegin;
// armv7
uctx->GR.__sp = stackBegin;
// i386
uctx->GR.__esp = stackBegin - 5 * sizeof(uintptr_t);
// x86
uctx->GR.__rsp = stackBegin - 3 * sizeof(uintptr_t); 

就是我们初始化协程的栈的时候，把stack pointer的值做了一个修正。 为什么要做这样的修正呢？因为在 process entry 的方法中，需要保证 sp 的地址是按16字节对齐的。 无论是在arm还是x86上都需要保证这个约定，否则程序执行就会因为不对齐而crash.

那另一个问题？为什么我们设置的初始值方式不固定，而且看起来并没有按16-Byte对齐呢？ 因为我们是要保证进入到 coroutine_main 方法中执行时的sp是16-Byte对齐的，而不是这里设置的初始值。而编译器在编译函数的时候默认都是需要将frame pointer 和return address压栈，所以我们需要保证的是压栈后的地址是对齐的。

6. yield & resume

有了栈切换了，我们怎么用它来实现 yield 和 resume 这2个基本方法呢？

其实这2个操作就是一次 getcontext 加一次 setcontext 来完成。

下面示例了yield的源码，resume是同样的原理。

// optone 保证 skip 的逻辑不会被编译器优化掉。
__attribute__ ((optnone))
void coroutine_yield(coroutine_t *co)
{
    if (co == NULL) {
        // if null
        co = coroutine_self();
    }
    BOOL skip = false;
    // 保存当前的调用栈信息到 co->context 里面
    coroutine_getcontext(co->context);
    if (skip) {
        // 当调用栈恢复的时候，不必继续执行后面的代码了。直接返回，相当于在调用yield的地方重新恢复了。
        return;
    }
#pragma unused(skip)
    skip = true;
    co->status = COROUTINE_SUSPEND;
    // 将调用栈恢复到co->pre_context记录的堆栈上
    coroutine_setcontext(co->pre_context);
}

7. 小结

本文是coobjc的设计篇的第一篇，主要介绍了coobjc种协程实现基本原理的调研思路， 还有栈切换实现的原理。基于这个原理，我们才能开发整个协程框架。

参考文档：
 https://llvm.org/devmtg/2016-11/Slides/Nishanov-LLVMCoroutines.pdf
 https://blog.codingnow.com/2010/05/setjmp.html
 http://infocenter.arm.com/help/topic/com.arm.doc.ihi0055b/IHI0055B_aapcs64.pdf

本文作者：念纪，来自淘宝客户端iOS架构组
淘宝基础平台团队正在举行2019实习生(2020年毕业)和社招招聘，岗位有iOS Android客户端开发工程师、Java研发工程师、C/C++研发工程师、前端开发工程师、算法工程师，欢迎投递简历至junzhan.yzw@taobao.com
如果你想更详细了解淘宝基础平台团队，欢迎观看团队介绍视频
更多淘宝基础平台团队的技术分享，可关注淘宝技术微信公众号AlibabaMTT