Coroutine lab

Deadline：2023-12-06 23:59:59

Warning：本次实验难度较高，可能需要花费较长时间。

Warning：本次实验难度较高，实验的分数与投入并非成正比，请合理安排时间。

Warning：本次实验难度较高，请理性看待，不必过度追求完美。

Warning：本次实验难度较高，但也不要忘记学术诚信（什么事情能做，什么不能）

看到上述警告，或许你会有一些担忧。但请放心，我们的目的并非为难各位同学们，而是希望大家在能够在实践中灵活运用所学知识。

正如前文所提，实验可能不同于您之前经历的，不一定会花费很少时间就能取得满分。然而，人生不如意事十有八九，而生活本身就是一个trade-off的过程。

尽管我们说了很多，您可能仍然感到担忧。但回想一下《小马过河》的故事，难度因人而异，实验可能对您来说只是稍微有些挑战而已。

因此，请做好心理准备，让我们开始吧！

一、实验简介

本次实验对应 CSAPP 第三章、第四章的内容。

在本次实验中，我们将逐步迭代开发一个简易的协程库，从使用系统调用实现协程，到使用汇编实现协程，从有栈协程到C++ 20引入的无栈协程。

这里并不是说无栈协程会比有栈协程更好，而是为了让大家了解协程的实现原理，以及不同实现方式的优缺点。两种实现方式没有优劣之分。

本次实验开发语言为C++，由于在部分代码中使用到了C++ 20的新特性，因此要求g++版本大于等于11。

Ubuntu 20.04 LTS自带的g++版本为9.3.0，因此需要手动升级g++版本。

Ubuntu 22.04 LTS自带的g++版本为11.2.0，因此无需手动升级g++版本。

关于Ubuntu上g++版本升级，可以参考这篇博文。如果怕破坏环境，可以只跟做博文中的前4步。并使用命令g++-11来使用g++ 11。

本次实验发布包包含如下文件：

├── libco_v1    
│   ├── Makefile
│   ├── coro.cpp
│   ├── coro.h  
│   └── main.cpp
├── libco_v2
│   ├── coro_ctx.cpp
│   ├── coro_ctx.h
│   ├── coro_ctx_swap.S
│   ├── coroutine.cpp
│   ├── coroutine.h
│   ├── main.cpp
│   └── makefile
├── libco_v3
│   ├── main.cpp
│   └── makefile
├── libco_v4
│   ├── generator.h
│   ├── main.cpp
│   └── makefile
└── libco_v5
    ├── generator.h
    ├── main.cpp
    ├── makefile
    └── sleep.h

发布包下载链接：libco-handout

本次实验分为五个部分，每个部分都是一个独立的协程库，每个部分都会有一个main.cpp文件，用于测试协程库的功能。

可能同学们会觉得5个部分太多了，但实际上每个部分都是在上一个部分的基础上进行迭代开发，在此过程中你可以愉快的ctrl + c & ctrl + v。并且正因如此，实验难度的梯度不会很大。

hint：实验中会牵涉到的新概念较多，建议大家好好阅读文档中的提示以及参考资料。

二、实验内容

hint：以下标注了任务？（？分）的问题，需要在提交的实验报告中回答，并计入实验分数。

part 0

作为实验的第一部分，我们将在这里逐步介绍实验中你可能遇到的新概念。

我们首先考虑一个普通的函数调用过程。

int add(int a, int b) {
    int ret = a + b;
    return ret;
}

int foo() {
    int a = 40;
    int b = 2;
    int ret = add(a, b);
    return ret;
}

int main() {
    int ret = foo();
    std::cout << ret << std::endl;
}

任务一（5分） 使用GDB，在提交的实验报告中，分析函数的调用过程，并画出从 main 函数中调用 foo 函数开始，一直到 foo 函数返回 ret 的过程中的栈帧变化。

hint：分析过程中可以注意以下几点：

• rbp、rsp的变化

  • 每次压栈的内容是什么

• 函数参数是如何传递的

• 函数的返回值是如何传递的

重点是画出栈帧上存了什么东西。

通过课堂上的学习，结合上面的小实验，我们不难发现，在函数的调用到运行再到返回的过程中，栈帧起到了至关重要的作用。它为函数的调用提供了一个运行环境，存储了函数的参数、局部变量、返回值以及返回地址等信息。

如果，我们希望一个函数能够在运行过程中暂停，然后再恢复运行（这就是我们本次实验中将要实现的协程），此时栈并不能满足我们的需求，这是为什么？

任务二（4分） 阅读Coroutine Theory这篇文章，回答以下问题：

1. 一个“普通”的函数支持哪两个操作，分别承担了什么功能？
2. 为什么我们说调用栈不能满足协程的要求？
3. 协程作为一种泛化的函数，支持了哪几个操作，分别承担了什么功能？
4. 如果不能使用栈来实现协程，那么我们可以将函数运行时所需的信息存储在哪里？

都是些很简单的小问题，也不用回答的过于严肃，不要求结果正确，主要是体现思考的过程。最最主要的是为了让大家好好看这篇文章，虽然这篇文章有点长，但是真的是一篇很好的文章。

在看了文章后，你可能已经对协程有了一个初步的了解。但在这里，我还想就一些概念进行一些补充。

我们不难发现，想要暂停并恢复一个函数的运行，我们需要保存一些数据，我们称之为上下文（context）。在Wikipedia中，上下文的定义如下：

任务的上下文（context）是一个任务所必不可少的一组数据。这些数据完全描述了这个任务的执行状态，通过存储这些数据，我们可以将任务暂停并在另一个地方恢复正常执行，也可以在不影响执行的情况下复制任务。

因此，实现协程的关键在于如何保存和恢复上下文。

回忆第四章讲的内容，程序最终运行在CPU上，而CPU可以视作是一个复杂的状态机，它一条一条的读入汇编指令，改变自己的状态。

任务三（3分） CPU的状态包括哪些？一个显然的问题是，我们不能一下保存所有的状态，结合函数调用约定，以及任务二中第四个问题的回答，你认为我们需要保存哪些状态用于暂停并恢复一个函数的运行？

结合上面的讨论，我们可以推测协程就是上下文+函数。理论部分的介绍就先到这里，接下来我们将逐步实现一个协程库。

part 1 （10分）

本部分对应libco/libco_v1。 在本部分中，我们将暂时不会深入到上下文的具体细节，而是使用Linux提供的ucontext库来实现一个简单的协程。

实验要求在Linux环境下完成，因为ucontext库只在Linux环境下可用。

在ucontext库中，为我们提供了一个存储了上下文的结构体ucontext_t，以及一组操作上下文的函数。

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

1. getcontext函数用于获取当前上下文并保存在ucp中。

2. setcontext函数用于当前的上下文为ucp。
   setcontext的上下文ucp应该通过getcontext或者makecontext取得。

3. swapcontext函数用于保存当前上下文到oucp，并将ucp设置为当前上下文

4. makecontext函数用于修改ucp。

需要注意的是，在调用makecontext之前必须调用getcontext初始化该上下文，然后为该上下文分配一个栈空间；当上下文通过setcontext或者swapcontext激活后，就会紧接着调用第二个参数指向的函数func；最后，参数argc代表func所需的参数，在调用makecontext之前可以初始化ucp->uc_link，表示func()执行之后，将要切换到ucp->uc_link所代表的上下文，其实是隐式的调用了setcontext函数，如果设置为NULL，那么当func()执行完毕后，程序将会继续中止。

如果看了上面的说明，你还是不太清楚的话，我们也为你准备了一些使用的例子：

int main() {
    ucontext_t ctx;

    getcontext(&ctx);
    std::cout << "Hello, ICS 2023!" << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(1));
    setcontext(&ctx);
}

不难发现，上面的代码在运行时会死循环。因为程序通过setcontext重新回到来getcontext记录的地方，然后输出Hello, ICS 2023!，接着再次调用setcontext，如此循环。

更详细的介绍可以参考这篇博文。

回到我们的实验，在libco_v1/coro.h中，你需要补全coroutine结构体的实现，为了实现后续的功能，你可能需要在coroutine结构体中添加一些成员变量。

接下来我们介绍coroutine_env的概念，它是一个全局的结构体，用于存储协程的调用信息。类似于普通函数的调用，协程间自然也会存在调用关系，因此，你需要在其内部实现一个栈结构，用于记录协程间的调用关系。

由于我们的实验不涉及多线程环境，因此协程最终是并发执行的，从而我们只需要及时的将协程从栈中压入、弹出即可。当然，在返回时，我们可能需要获取栈中的元素，因此我们也提供了get_coro函数。不必担心没有存储所有的协程会导致资源泄露，协程在main函数中创建时，会返回其指针，因此我们可以通过这个指针来释放协程的资源。

hint：你可能需要在coroutine_env压入一个主协程main_coro，用于记录main函数的上下文。这可以在coroutine_env的构造函数中完成。

另外，在目前的实验中，不会涉及到协程的递归调用，所以栈的深度可以只设置为2。

另外，多用<cassert>的assert函数，可以帮助你在调试时快速检查和定位错误。

这便是libco_v1/coro.h中需要完善的内容。如果有不清楚的地方，及时向助教提问！！！

完成了libco_v1/coro.h中的内容后，你需要在libco_v1/coro.cpp中实现协程的创建（create）、释放（release）、恢复（resume）、暂停（yield）这四个函数。

create函数用于创建一个协程，并返回该协程的指针。

hint：如果你在coroutine的构造函数中完成了部分资源的初始化，那么在create函数中，你只需要使用new来创建一个coroutine对象即可。

你可能会感到疑惑，为什么这里不需要设置上述提到的coroutine上下文中的相关内容。对此，我们采用lazy的策略，即只有在协程被激活时，才会设置其上下文。

release函数用于释放一个协程的资源。

如果你在create函数中使用了new，那么在release函数中，你需要使用delete来释放协程的资源。

注意：你需要完成coroutine的析构函数，用于释放协程的资源。否则会发生内存泄露。

func_wrap是一个辅助函数，从它的实现可以看出，它同一了协程的进入，并在协程退出时，设置相关标志位。最后使用yield函数回到主协程。在这里，我们约定yield返回-1表示协程的结束。

resume函数用于恢复一个协程的运行。其第一个参数是需要恢复的协程；第二个参数是传递给协程的参数，该参数会通过yield函数返回给调用者。

yield函数用于暂停一个协程的运行，并返回给调用者。其第一个参数是传递给调用者的返回值，该参数会通过resume函数返回给调用者。

这里奇怪的点在于，从执行流来看，resume会返回到yield，而yield会返回到resume。因此，在这个过程中，你可能需要通过一些方式保存函数的参数和返回值。

一个自然的想法是在每个coroutine结构体内设置一个data字段，用于双方的通信。

resume时将要传入的参数保存在即将恢复的协程的该字段，并通过yield返回自身的data字段。反过来，yield时将要返回的参数保存在主协程的data字段，并通过resume返回的data字段。

hint：从上面的提示可以发现，这中间存在上下文的切换。注意函数的调用时机，以及函数的返回值。

在实现完上面的代码后，就可以进入到libco/libco_v1文件夹下，使用make命令编译代码，并使用./main命令运行代码了。

如果一切正常，会看到对应的输出。

main函数很简单的，可以自己看看。

part 2 （18分）

本部分对应libco/libco_v2。

在这里，我们将自己使用汇编来实现协程的上下文切换。

首先是我们自定义的coro_ctx结构体，你需要在其中添加需要保存的上下文。

hint：其中可能包括所有的callee-save寄存器，以及用于传递参数的六个寄存器。

另外，考虑到我们需要伪造函数调用环境，你可能需要保存栈指针和函数地址。此处存函数地址，并在第一次被resume时，设置好所有寄存器的值后，将其压入栈中，那么resume返回时，就会依据调用约定，将rsp指向的地址作为返回地址，从而跳转到函数地址处，实现函数切换。在后续暂停和恢复中，我们都会这样做，使得函数恢复到上次暂停的位置。

因此，保存当前上下文，恢复下一个上下文，这两个操作都需要在汇编中完成。通过调用约定我们知道，函数的第一个参数是rdi，第二个参数是rsi，在此基础上，我们就可以编写对应的汇编操作了。

需要补充的一点是，结构体的内存布局是从低地址到高地址的，保存和恢复上下文时，需要注意上下文中变量的顺序（也就是相对于rdi/rsi的偏移量）。

通过上面的解释，你可能已经大致了解了什么叫context swap。你需要在coro_ctx_swap.S中实现coro_ctx_swap函数。

然后，你需要在coro_ctx.cpp中实现ctx_make函数，用于初始化coro_ctx结构体。

在这里，你需要初始化coro_ctx结构体中的成员变量。

在完成了part 1后，你已经发现了我们需要为协程提供栈，我们的实现方法是从堆上申请一大片空间将其作为栈。在这里，我们已经给出了stack_mem的框架，你需要补全其中的代码并在后续的代码中使用。关于share_stack，我们会在后续介绍到。

对于coroutine结构体，你可以仿照part 1中的实现。

在coroutine_env中，你需要拓展part 1中的实现，使其支持协程的嵌套调用。

其实只是让调用栈的深度变大了而已。

接着是coroutine.cpp中的四个函数。语义与part 1中的函数保持一致。

此外，我们定义了辅助函数swap用于切换上下文，在part 1的基础上，你已经大致了解了这个函数中需要做什么，其核心coro_ctx_swap你也已经实现，那么这里并不复杂。

part 2.5 （10分）

在上面的实现中，你可能会觉得我们对栈的申请有点浪费，因为并不是每个协程都需要一个这么大的栈。因此，我们引入了share_stack的概念，即多个协程共享一个栈。在coroutine.h中，你需要实现share_stack的相关代码。

为了不修改coroutine结构体，其内部就是一个stack_mem的数组。

注意：当count不为1时，你需要维护一种stack_mem的使用方式，以减少拷贝带来的开销。

所谓共享栈，就是所有协程在运行时，使用一个较大的栈，当协程暂停时，只将其使用到的栈空间进行保存（也就是申请一片刚刚好的空间，然后memcpy），当协程恢复时，再将其使用到的栈空间进行恢复（也就是将之前memcpy的内容再copy回来）。

我们使用coroutine_attr结构体在创建时指定协程的属性，其中stack_size表示需要为协程分配的栈大小，sstack表示是否使用共享栈。如果使用共享栈，那么sstack指向一个share_stack结构体，否则为nullptr。

这里可能会出现stack_size与sstack所指的share_stack不一致的情况，这种情况下，你需要将协程的stack_size设置为sstack的大小。

为了实现上面的操作，你需要修改create函数。你可能也需要在其中检测attr传入的数据是否合理，例如栈大小应该在8k到128k之间，否则强制修改到边界值。另外，最好让stack_size为4k的倍数，可以通过位操作来检验和修改。

然后，你需要修改swap函数，使其支持共享栈的切换。在这里，你可能也需要向全局的coroutine_env中添加一些成员变量，用于记录协程的切换信息（因为中间会发生上下文切换！）。对于栈的保存，我们给出了辅助函数save_stack的框架。

需要指出的是，在共享栈有多于一个栈时，我们为了减小开销，也会使用lazy的方式，只有当改栈有新的协程使用时，才进行保存操作，因此，你可能需要修改stack_mem使其记住上一个使用者，当其被驱逐时，需要保存栈到对应的协程中（此处也需要向coroutine添加成员变量）。

此外，你需要判断如果新来的和上一个使用者是同一个协程，那么就不需要保存。

另外，需要补充的是，共享栈和私有栈是会同时存在的，至少main_coro是私有栈。作为库的编写者，我们也需要给用户更多选择的权力。

比较技术（魔法）的一点是，你需要在swap函数中知道当前协程使用了多少的栈空间。对此我们不直接给出，一个提示是考虑任务一中你观察到的结果。

以上操作都发生在swap函数中，如无必要，其它函数不需要修改。

在完成了上述的代码后，你可以进入到libco/libco_v2文件夹下，使用make命令编译代码，并使用./main命令运行代码了。

到这里，关于有栈协程的实现就告一段落了。你是否已经对其有了一定的了解了呢？

需要补充的是，我们这里实现的是一个极为简略的协程库，实际上，协程库还需要考虑很多问题，例如协程的调度等等。但这些问题并不是我们本次实验的重点，因此我们不会在这里进行讨论。如果你对此感兴趣，可以自行查阅资料。

part 3 （10分）

本部分对应libco/libco_v3。

通过上面的讨论，你可能存在一些疑惑，例如，使用独享栈太浪费了，使用共享栈又会带来额外的开销，那么有没有一种更好的方式呢？为什么协程函数只能返回给调用者，而不能返回给其他协程呢？

在这里，我们将引入无栈协程的概念。

再次回到之前谈论的内容，我们说CPU本质上是一个状态机，那么我们可不可以把我们的程序看作是一个更复杂的状态机呢？

当然可以，我们完全可以把函数的每一条语句当作是一条指令，函数的局部变量看作是函数的状态。

关于这一点的讨论，可以看应用视角的操作系统 (程序的状态机模型；编译优化) [南京大学2023操作系统-P2] (蒋炎岩)

因此，我们通过如下例子来逐步将一个函数改写，使之可以在运行时暂停并恢复。

考虑以下需求，函数每打印一次，就挂起。

void foo() {
    int cnt = 0;
    while(true) {
        std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;
        // susspend
    }
}

而挂起本质上就是返回，因此我们可以将其改写为：

void foo() {
    while(true) {
        int cnt = 0;
        std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;
        return;
    }
}

这可以解决函数无法返回的问题，但是，每次返回后并不是从挂起点恢复，而是重新运行函数，这显然不是我们想要的结果。

为此，我们想到了“黑魔法”——goto

void foo() {
    goto resume;

    int cnt = 0;
    label:
    std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;
    return;
resume:
    ;
}

这依然存在问题：

1. 上述代码即使是第一次执行，也会直接“恢复”

2. 计数器cnt每次都会被初始化为0，而不能保持状态

对此的解决办法可以使用一个变量记录当前是否是resume，并且将所有变量改写为static。

但这样也存在问题，由于变量是static的，因此，我们无法创建多个协程，因为它们共享了同一份变量。

因此，我们考虑将函数改写为一个类，在类的内部记录函数的运行状态，并重载其operator()使其可以像函数一样被调用。

class foo_frame {
private:
    bool started = false;
    int cnt = 0;
public:
    void operator()() {
        if (!started) {
            started = true;
            goto resume;
        }
        std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;
        return;
    resume:
        ;
    }
}

在上面的代码中，我们已经实现的函数的暂停和恢复。但如果有多个暂停点，又该如何处理呢？

我们的解决办法是使用switch + goto。

class foo_frame {
private:
    int started = 0;
    int cnt = 0;
public:
    void operator()() {
        switch (started) {
            case 0: break;
            case 1: goto resume_1;
            case 2: goto resume_2;
        }
        while (true) {
           std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;
           started = 1; return; resume_1:

           std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;
           started = 2; return; resume_2:
        }
    }
}

从上面的代码可以看出，每次挂起都存在重复的代码，我们希望可以尽量少的重复我们的代码，你可能会考虑到宏，但当任然存在几个问题：

• switch需要知道函数体内有几个暂停点，宏无法做到这一点。除非使用宏参数，但这样每次增加或减少一个挂起点，都需要进行相应的修改。

• 暂停点记录当前位置的方式是记录下当前是第几个暂停点，同样不是宏定义能做到的。如果使用宏参数，则依然有修改复杂的问题。

为此我们可以对当前代码做出一些修改

class foo_frame {
private:
    int started = 0;
    int cnt = 0;
public:
    void operator()() {
        switch(started) {
            case 0:

            while (true) {
                std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;

                started = __LINE__; return; case __LINE__:;

                std::cout << cnt++ << ": Hello, ICS 2023!" << std::endl;

                started = __LINE__; return; case __LINE__:;
            }
        }
    }
}

这样，我们就可以通过__LINE__来记录当前的位置了。但是，当前仍然存在代码重复问题，并且也还没有实现yield的功能。不过，大致的思想已经展示出来了。

现在，你可以在libco_v3/main.cpp中，实现CO_BEGIN、CO_END、CO_YIELD、CO_RETURN这几个宏，coroutine_base、fib这两个类，使得能够通过main函数中的测试。

part 4 （10分）

本部分对应libco/libco_v4。

在part 3中，你可能会想到，如果每个协程都需要手动写一个类，那么会很麻烦。并且，这么无聊的一件事，怎么不交给机器来做呢？

是的，在C++ 20中，我们可以让编译器来帮助我们做这件事。

在本部分实验中，我们需要你熟悉C++ 20中协程的使用方法，并自己动手实现一个generator。

任务四（10分） 阅读链接中的这几篇文章，结合网上的资料，回答以下问题：

1. 协程函数的返回值Coroutine Functor需要有哪些成员？
2. Promise对象需要提供哪些函数？
3. Awaitable object需要提供哪些接口？
4. Coroutine handle通常需要提供哪些函数？
5. 为什么说co_yield和co_return是co_await的语法糖？
6. 简述协程函数的调用过程并阐述上述每个接口函数的功能。（5分）

看完上面给出的参考资料后，你需要在libco_v4/generator.h中实现generator的相关内容。

hint：你需要补全缺失的类以及标准规定的成员函数。

另外，直接使用resume函数来访问迭代器过于麻烦，因此，我们需要实现一个generator::iterator类，从而可以基于迭代器的语法糖来访问generator。

具体要求和提示以及在libco_v4/generator.h中的注释中给出。

在完成了上述的代码后，你可以进入到libco/libco_v4文件夹下，使用make命令编译代码，并使用./main命令运行代码了。

part 5 （20分）

本部分对应libco/libco_v5。

在本部分中，你需要在part 4的基础上，实现一个可以递归的generator。另外，你还需要实现sleep.h中的内容，使得main函数中的测试可以通过。

hint：为了实现可递归，你可能需要维护一颗调用树以及修改一部分代码。

关于sleep类并不复杂，只是熟悉一下Awaitable object的定义。

在完成了上述的代码后，你可以进入到libco/libco_v5文件夹下，使用make命令编译代码，并使用./main命令运行代码了。

final

恭喜你，你已经完成了本次实验的所有内容。

四、提交事项

1. 新建文件夹，以你的学号命名，将实验报告和代码放入其中。最终的文件夹结构如下：

<student-id>
├── report.pdf
└── libco
    ├── libco_v1
    ...

2. 在上级文件夹使用 tar -cf <student-id>.tar <student-id> 将文件夹压缩成 tar 包。

你的实验报告应包含以下内容：

1. 姓名和学号
2. 本文档中指出需要在实验报告中回答的问题。
3. 你实现的libco的代码。
4. 通过每个测试的截图。
5. 简要的实现思路。
6. 如果有，请列出引用的内容以及参考的资料
7. 对本实验和课程的意见或建议
8. 一只可爱的猫猫

五、参考资料

1. libco_v1参考自云风实现的coroutine
2. libco_v2参考自微信开源的libco
3. libco_v5参考自提案，对应的代码