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