跟羽夏去实现协程

写在前面

  此系列是本人一个字一个字码出来的，包括示例和实验截图。本人非计算机专业，可能对本教程涉及的事物没有了解的足够深入，如有错误，欢迎批评指正。 如有好的建议，欢迎反馈。码字不易，如果本篇文章有帮助你的，如有闲钱，可以打赏支持我的创作。如想转载，请把我的转载信息附在文章后面，并声明我的个人信息和本人博客地址即可，但必须事先通知我。

引入

协程（英语：coroutine）是计算机程序的一类组件，推广了协作式多任务的子例程，允许执行被挂起与被恢复。 相对子例程而言，协程更为一般和灵活，但在实践中使用没有子例程那样广泛。 协程更适合于用来实现彼此熟悉的程序组件，如协作式多任务、异常处理、事件循环、迭代器、无限列表和管道。 —— 维基百科

  我相信很多人看完这个其实是看不明白什么是协程的，提起协程，会经常拿线程作比较：

用户级线程是协作式多任务的轻量级线程，本质上描述了同协程一样的概念。其区别，如果一定要说有的话，是协程是语言层级的构造，可看作一种形式的控制流程，而线程是系统层级的构造。 —— 维基百科

  做过并发同步相关编程开发的人肯定对线程多多少少的都会清楚一些。不过继续后面的内容之前，我要增加继续引入一个概念：状态机。
  什么是状态机？维基百科解释如下：

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机（英语：finite-state automaton，缩写：FSA），简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。

  看起来很抽象的一个概念。其实状态机也是一个应用于万物的一个概念，打个比方：每个人都有状态，比如心情的好坏、身体健不健康、劳不劳累，这些都是状态。我们作为人每天的心情、身体状态等都随时发生着变化，不同时间都会有不同的状态，所以人是一个状态机。
  对于计算机来说，CPU是一个十分重要的器件，它拥有众多寄存器。在执行代码时，寄存器的值不断的发生变化，所以CPU也是一个状态机。对于线程的切换，其实就是CPU把寄存器的状态进行保存，把之前保存的另一个状态重新加载到寄存器中继续执行。

基础

  好了，按照我写博文的惯例，我要开始劝退啦。如果基础不够的话，要自己参考我的其他博文或者书籍补漏再回来，要不就不要继续了。

• AT&T 格式汇编（这次我要用它写内联汇编）
• 64 位 Intel 汇编（32 位的最起码会）
• 会 C 语言和使用一些编译器扩展（这次用 gcc）
• x64 平台下的调用约定

  我的相关博文：

• 进程线程篇——简述
• 羽夏笔记—— AT&T 与 GCC
• 深入 x64
• x64 简介

声明

  当然，看完本篇之后或者在阅读之前你拥有基础，你可以实现自己版本的。我们这次介绍在Windows基于 Intel CPU 下的 64 位的实现。你可以实现Linux版本的，或者其他硬件平台的比如ARM平台或 32 位的硬件平台，这都你随意，因为它们的原理是相通的。
  我也有已经实现的两个版本，一个是本篇要用的代码，我放到文章后面去了。等你写完了之后再回去看作为完整参考。我还实现了一个跨Windows和Linux操作系统的 Intel CPU 下的 64 位一个协程库，功能稍微多一点，感兴趣你也可以看看，我也附到文章后面。我也会对该库提出几个问题来供你思考。
  强调一点：在你没有亲自写完一个协程之前，不要看我的代码参考，一定不要看！写完再看！
  如果你学过我的跟羽夏学 Win 内核系列的课程，里面的进程线程篇其实就已经介绍了 Intel CPU 下的 32 位的实现。不妨在看完 x64 与 x86 不同之处之后，自己来实现一份协程库之后，再来看看！

实现

  线程切换其实就是把线程的当前状态保存起来，然后加载到准备切换的线程状态。进程的状态其实就是CPU里面一堆寄存器的值，只要对这些值通过某些方式进行保存，之后加载之前保存的，不就实现线程切换了吗？
  为了尽可能的简单，这次用纯C代码来实现协程，就只实现协程创建和最简单的调度，以及程序退出之后的善后清理资源操作。
  如果你学过我的跟羽夏学 Win 内核系列的进程线程篇，你知道线程的状态是保存在栈上的。如果你没学过也没关系，知道这个结论就行。所以定义一个协程首先有个栈，还得有个栈顶指针表示使用状态。
  我们创建线程的时候必须交给一个函数指针来执行代码，当然也可以传参。传参就不在这里搞了，因为涉及调用约定的问题，就不搞稍微增加复杂度的东西。
  当然，线程也有线程的状态，比如运行中、挂起状态、死亡状态。综上所述，这个最简单的协程结构体就这么定义出来了：

typedef void (*thread_pointer)();
typedef enum thread_state { DEAD, RUNNING, SLEEP } thread_state;
typedef struct thread {
    void *stack;
    void *stackpc;
    thread_pointer pc;
    thread_state state;
} thread;

  然后我们再定义一个数组装协程（简单处理），还有一个指针指向当前运行的协程：

thread thread_table[THREAD_TABLE_MAX_SIZE];
thread *current_thread = &thread_table[0];

  如果没有时钟中断，线程切换都是主动切换的，这通常发生在调用WinAPI的时候。所以，我们需要写一个协程切换的函数：

#define THREAD_TABLE_MAX_SIZE (5)

static int swap_context_i = 0;

void swap_context_caller() {
    thread *new_thread = NULL;
    thread *old_thread = NULL;
    bool notfounded = true;
    while (true) {
        for (; swap_context_i < THREAD_TABLE_MAX_SIZE; swap_context_i++) {
            if (thread_table[swap_context_i].state == SLEEP) {
                old_thread = current_thread;
                new_thread = &thread_table[swap_context_i];
                current_thread = new_thread;
                swap_context(old_thread, new_thread);
                notfounded = false;
                break;
            }
        }
        if (notfounded) {
            swap_context_i = 0;
        } else {
            break;
        }
    }
}

  如果你有相关知识的学习很容易的发现，这其实是一个最简单的调度器。swap_context是真正实现我们协程调度的函数，但这个函数是十分特殊的，定义如下：

__attribute__((naked)) __attribute__((fastcall)) void
swap_context(thread *old, thread *new);

  __attribute__((...))是 GNU 系列编译器声明属性的一个扩展，naked是声称这个函数是裸函数，让编译器不要生成栈维护的代码。fastcall强调传参请使用这个调用约定，当然在 x64 下，这个声明是没有用的，因为默认就是这个。
  好了，不啰嗦了，给出我写的协程切换的核心函数：

#define DECLARE_STRUCT_OFFSET(type, member) [member] "i"(offsetof(type, member))

__attribute__((naked)) __attribute__((fastcall)) void
swap_context(thread *old, thread *new) {
    asm volatile("pushq %rax;"
                 "pushq %rbx;"
                 "pushq %rcx;"
                 "pushq %rdx;"
                 "pushq %rbp;"
                 "pushq %rsi;"
                 "pushq %r8;"
                 "pushq %r9;"
                 "pushq %r10;"
                 "pushq %r11;"
                 "pushq %r12;"
                 "pushq %r13;"
                 "pushq %r14;"
                 "pushq %r15;"
                 "pushfq");

    // rcx: old, rdx: new
    asm volatile("movq %%rsp,%c[stackpc](%%rcx);" ::DECLARE_STRUCT_OFFSET(
                     thread, stackpc)
                 : "rcx", "rdx");
    asm volatile("movq %0,%c[state](%%rcx);"
                 "incq %1;" ::"i"(SLEEP),
                 "m"(swap_context_i), DECLARE_STRUCT_OFFSET(thread, state)
                 : "rcx", "rdx");

    asm volatile("movq %c[pc](%%rdx),%%rax;"
                 "test %%rax,%%rax;"
                 //> if not first started
                 "jz pcnull%=;"
                 // r8 : function handler
                 "movq %%rax,%%r8;"
                 "xor %%eax,%%eax;"
                 "movq %%rax,%c[pc](%%rdx);"
                 "movq %c[stack](%%rdx),%%rbp;"
                 "movq %%rbp,%%rsp;"
                 // fill up stack info
                 "lea idle%=(%%rip), %%rax;"
                 "push %%rax;"
                 "callq *%%r8;"
                 "pcnull%=:;"
                 //> if first started
                 "movq %1,%c[state](%%rdx);"
                 "movq %c[stackpc](%%rdx),%%rsp;"
                 "jmp sw%=;"

                 "idle%=:;"
                 "call %P0;"
                 "jmp idle%=;"
                 "sw%=:;" ::"i"(swap_context),
                 "i"(RUNNING), DECLARE_STRUCT_OFFSET(thread, state),
                 DECLARE_STRUCT_OFFSET(thread, pc),
                 DECLARE_STRUCT_OFFSET(thread, stack),
                 DECLARE_STRUCT_OFFSET(thread, stackpc)
                 : "rax", "rcx", "rdx");

    asm volatile("popfq;"
                 "popq %r15;"
                 "popq %r14;"
                 "popq %r13;"
                 "popq %r12;"
                 "popq %r11;"
                 "popq %r10;"
                 "popq %r9;"
                 "popq %r8;"
                 "popq %rsi;"
                 "popq %rbp;"
                 "popq %rdx;"
                 "popq %rcx;"
                 "popq %rbx;"
                 "popq %rax;"
                 "ret;");
}

  如果你看不懂DECLARE_STRUCT_OFFSET这个东西，这个是使用了 GCC 的内联汇编扩展。这里提一嘴，微软系列的 x64 版本不能直接内联汇编，需要单独放到一个汇编代码文件中，这样十分不方便。
  如果这个协程上下文切换看不懂的话， 基本就是 AT&T 汇编不扎实或者没有画堆栈图，那就自己补补漏吧！
  创建协程的函数也就是填写一个结构体，没啥难度，先放到这里了：

bool create_thread(thread_pointer func) {
    if (func == NULL) {
        puts("create_thread failed: please input invalid excution address");
        return false;
    }

    for (int i = 0; i < THREAD_TABLE_MAX_SIZE; i++) {
        if (thread_table[i].state != DEAD) {
            continue;
        }
        thread *th = &thread_table[i];
        th->pc = func;
        th->stack = (void *)((char *)(malloc(STACK_SIZE)) + STACK_SIZE);
        th->stackpc = th->stack;
        if (th->stack == NULL) {
            puts("create_thread failed: malloc thread stack");
            return false;
        }
        th->state = SLEEP;
        return true;
    }
    return false;
}

  至此，就结束了，剩下的就靠你自己练习了。

练习与思考

1. 我写好了，本篇文章的总示例代码在哪里？

🔒 点击查看答案 🔒

---

在我的 Gitee 上：https://gitee.com/wingsummer/coroutine

---

2. 请自己实现与该文章相同功能的协程实现，并尝试增加协程终止函数（如果可以增加对 Linux 平台的支持）。

🔒 点击查看答案 🔒

---

参考请看问题 4 。

---

3. 在问题 1 中的代码中，如果你尝试改为 C++ 的并使用了标准库的东西，协程运行时会崩溃，为什么？

🔒 点击查看答案 🔒

---

答案其实就就在问题 4 提供的代码中，其实就是调用约定没遵守好的问题：栈帧对齐。

---

4. 功能更全版本的代码在哪里获取？ （完成问题 2 之前请不要看）

🔒 点击查看答案 🔒

---

在我的 Gitee 上：https://gitee.com/wingsummer/wing-coroutine

---