embassy_preempt设计文档

整体设计

分成两个接口，一个接口是对于c/rust的普通函数的，另一个接口是对于rust的异步函数的。

然而对于c/rust普通函数，我们对它进行包装，在接口内转为一个future 对象，从而将调度都统一到执行器进行。

后续可以通过宏或者接口中直接区别rust的普通函数和异步函数从而对于rust普通函数和异步函数进行合并

下面以表格形式给出各种情况的上下文切换情况：

栈部分的分析

首先将上下文切换的分类分成抢占和让权两种； 在对于抢占的时候需要分为保存和恢复两步：

• 对于保存：不管什么情况，都是先给当前任务分配一个堆栈，然后将当前任务的上下文保存到堆栈中
• 对于恢复： 需要先判定需要转移的任务是否有堆栈，如果没有，说明是协程，那么直接poll就能恢复调度执行，而对于有堆栈的情况，需要将堆栈中的上下文恢复到寄存器中（这里面就包括了pc的恢复从而跳转到任务执行）

仔细考虑一下栈的动态分配问题：

对于普通的线程，通常由用户指定一个栈的区域，从而我们将栈分配给任务，但是这样的话，我们无法做到栈的动态分配，我想做到在可能的情况下，如果不存在抢占，那么所有的线程以及协程都是共用一套栈，等到遇到抢占的时候再分配

动态分配时，首先所有的协程以及线程（实际上我们也把线程处理为了一个没有await点的协程从而做到统一的调度），都是共用一套栈,我们这里统一术语称为程序栈。当遇到抢占的时候，我们需要将当前任务的栈保存起来，也就是说之前协程共用的这一套栈（程序栈）被分给了当前任务用于它的上下文保存，然而程序的运行是需要栈的，所以这个时候需要立刻分配一个新的栈给所有的协程（也就是程序栈），然后恢复的时候，需要根据恢复的任务是协程还是线程（其实是根据任务是有栈还是无栈）来分情况处理。 换句话说就是，程序运行肯定会有一个栈（分配出来的），这个栈也是所有协程开始执行的时候所在的公共堆栈，如果没有发生抢占那么这个栈就会复用。而发生抢占的时候当前的这个堆栈就认为是当前这个协程所占有的堆栈，然后重新分配一个新的栈给执行器用来继续执行整个程序（也就是协程）

这里强调一下恢复运行后的任务的栈不一定就是所有协程所在的栈（也就是说恢复后的任务不一定就变成协程，也可能是线程）：因为恢复的任务可能之前是被抢占的，那么恢复的时候就需要从堆栈中恢复上下文（包括pc与sp等）从而继续执行。而这里注意，是不可以在恢复现场的时候释放掉栈的，因为还有一些现场本身是放在栈里面的，这个栈需要继续使用，但是继续执行之后，如果遇到await（也就主动让权的情况）或者整个任务完成退出，那么就可以释放掉自己使用的栈到栈池了。

这里实际上最关键的就是这个栈分配器的实现，我感觉这里就和堆分配器一样（实际上就是堆分配了已经），考虑就直接用堆分配器的算法进行动态的栈分配（采取fixed-sized的算法进行分配） 我们这里复用的堆分配器的实现，新建了一个栈分配器的实例，将0x20000000开始的40KB分配给栈使用，heap可以用后续的空间（不过目前还没有涉及）
而fixed-sized支持的固定大小数组是：[128, 256, 512, 1024, 2048, 4096, 8192, 16384] 单位Byte
不在这个枚举里面的值，是可以支持分配的（因为底层我们使用了linked-list的分配算法进行优化，从而支持非固定大小的支持，但是在栈分配里面我们不会利用这个，这个特性我们只是给堆空间的分配使用提供）

最后总结一下抢占下切换的时候关于栈的处理：在保存现场的时候，我们将当前的堆栈给到当前任务，它就拥有了这个堆栈，并且需要给程序执行重新分配一个堆栈（也同样是协程的公共堆栈），然后进入恢复阶段，如果恢复的任务是一个线程，直接就把sp恢复，因为线程有sp，如果任务没有堆栈指针（也就是说是个协程），那么就使用程序的堆栈（刚刚分配了的），这个堆栈是给所有协程任务使用的。

第一阶段+第二阶段

第一阶段：在uCOS中没有中断的场景下，引入embassy，以支持协程；（线程被视为不会暂停的协程）

• 统一线程和协程的控制块结构TCB（Task Control Block）；
• 只有让权情况出现，让权时栈空，可以复用栈；（解决堆栈的分配和回收问题） 第二阶段：在uCOS中没有中断的场景下，引入embassy和优先级，以支持线程和协程的优先级调度；
• 按优先级选就绪任务（可能是线程，也可能是协程）；

第一阶段&第二阶段设计

为了将协程与线程统一，我们采取lazy的策略为线程分配栈空间。只有当线程开始运行时，该线程才会占有当前执行器所使用的栈。而在线程结束之后，其所拥有的线程栈将被回收。因此在第一阶段&第二阶段这种没有抢占的情况下，在进行调度时，线程(同步任务)与协程(异步任务)的表现将完全一致。可以查看我们的测试程序，

• tests/integration.rs
• src/bin/ucosii_main.rs
• src/bin/prio_test.rs
• src/heap/stack_allocator.rs(里面有个独立的测试模块)

第一阶段&第二阶段调试记录

栈初始化

在操作系统启动之前，需要进行若干初始化的操作，而此时的栈指针sp将被设定为链接脚本中指定的值(下面简称为初始化栈)。因此在操作系统启动之前(还未使用我们的栈分配器之前)，所有的系统初始化相关的部分都将保存在初始化栈中。因此在系统启动、准备换栈之前，需要提前将初始化栈上的变量等drop，如果将drop操作延后至换栈之后，就将找不到需要drop的变量进而导致错误。

爆栈问题

在调试的过程中我们多次遇到了爆栈的问题。经过调试，我们发现主要有以下两个原因会导致爆栈：

• copy or clone 在内存空间紧张的嵌入式设备中，如果在一个函数中需要使用某一个变量时，使用的是copy或clone，而非引用的话，就极有可能会导致当前函数所占用的栈空间过大(这是由于局部变量也保存在函数栈中)，进而导致爆栈。 实际上在Embassy Book中也有相关的提示：

However, in most embedded applications you don’t want to spend resources on an allocator and end up placing buffers on the stack. This, however, can easily blow up your stack if you are not careful.
--from: https://embassy.dev/book/#_passing_buffers_by_reference

• 优化 在我们解决copy&clone导致的爆栈之后，我们发现我们的栈空间的利用率还是很低(通过查看反汇编代码发现似乎局部变量与函数传参的存储并不紧凑)，因此我们怀疑是由于我们没有开启优化导致部分函数携带了许多额外的信息。在我们调高了优化等级之后，栈空间的利用率得到了提高，爆栈问题得到了解决。

更细致的设计、调试、分析记录在链接文档（notion）：https://liamy.notion.site/7b079c095dbe40018de93c3092664ca1?pvs=4

第三阶段

在uCOS中有中断的场景下，引入embassy和优先级，以支持线程和协程的优先级调度；

- 中断就是抢占情况，需要保存堆栈，并（有可能）分配新堆栈，用于恢复下一个任务；

第三阶段设计

第三阶段有几个关键点：

• 哪一部分代码属于任务执行的代码？

  • 设计思路：我们认为只有当从任务中返回到执行器代码时，才代表着该任务结束，即将状态转移等编译器生成的代码的执行也认为是任务的执行。

• 如何让中断程序知道当前在执行哪部分代码？

  • 设计思路：将执行器代码放入临界区中，让其不可被打断，那么这样就会使得所有的中断都将在执行任务代码时产生，这样所有将导致抢占的中断都可以无脑分配一个栈给当前任务，使得处理得以简化。
  • 长远计划：尝试在执行器代码(即poll函数)中任何对正确性没有影响的代码处都允许中断的发生，这样可以进一步提高系统的实时性，并且可能对空间开销没有影响。
    • 初步设计思路：为全局执行器增加一个成员变量以标记当前正在执行的代码。

• 中断服务程序如何设计？

  • 设计思路：在中断服务程序中，我们还应该在中断返回时增加几个功能：

    • 栈分配模块(仅在发生抢占时执行，即新任务的优先级更高)：用于分配一个新栈以供系统继续运行。而旧栈将用于保存原有任务的执行现场
    • 唤醒模块：将新任务设置为就绪状态
    • 抢占调度模块：用于在中断返回时进行重调度

    我们将把前两个模块作为唤醒器Waker的功能。而对于抢占重调度，我们将尝试复用原有的普通调度函数。

• 抢占调度如何设计？

  • poll函数的重构：由于我们在一二阶段实现poll函数时考虑的情况过于混杂，导致poll函数的质量并不是很高。在第三阶段中，我们将对poll函数进行重构，以更好地支持抢占调度的情况。重写后的poll函数应该保证以下几点：
    • 任何任务在执行时都是无栈状态：为了满足这种条件，在poll函数执行时，如果新任务无栈，则正常执行；若新任务有栈，则将从该栈中恢复现场并将原栈回收。
    • 只有主动让权的任务才会有对应的中断来唤醒该任务：如果满足了这种条件，则在发生抢占时，新任务一定是无栈的情况（因为一个任务有栈，就代表他曾经被抢占过）
  • 设计思路：假设目前有一个优先级更高的任务需要抢占当前任务，那么在中断服务程序的抢占调度中，我们应该在抢占调度之前将旧任务的执行现场保存在原有的栈上，然后额外分配一个新栈以供剩余的所有任务共用。

第三阶段实现

中断/抢占流程

1. 中断抢占发生, 一部分现场立刻被保存到当前程序栈(psp)上（xPSR, PC, LR, R12, R0-R3，由硬件实现），同时栈会切换到msp异常堆栈
2. 中断处理程序需要响应的事务结束之后，需要将对应的任务唤醒，即设置对应的任务为就绪
3. 接下来我们将调用执行器的中断poll函数。在执行器的中断poll函数中，会找到最高优先级任务，然后将程序栈分配给被打断的程序（需要判断是否当前任务就是最高优先级的，是的话就不分配栈，直接异常/中断返回原任务继续执行即可）。此外还需要继续保存硬件未保存的、旧任务的执行现场到旧栈上。这样当前任务的上下文就保存了。然后将转向最高优先级任务的处理。

详细说明最后一步的处理方式：

• 这里我们把任务切换的实际过程放在pendsv中断中进行处理

  因为如果不在中断中处理，有个关键的过程很难完成：在抢占时，需要压入所有的寄存器（上下文）到程序栈，并且将这个程序栈分配给任务，如果不是在中断里面而是tread模式下，那么本身就在使用这个程序栈，在这种情况下操作，可能需要大量的汇编代码的设计（来控制栈的使用），这样实现可读性也不好。

• pendsv会马上保存中断前的上下文到psp栈上（后续这个psp栈可能会分配给旧任务，也有可能直接被回收，因为抢占的情况进入的pendsv是需要保存现场给当前优先级任务，然而正常thread下poll的时候恢复到有栈的任务是不需要保存现场给当前任务，这两者的区别在于当前优先级任务和最高优先级任务是否是同一个），如果是由于中断抢占后，调用的pendsv，那么对应的当前任务prio和最高优先级任务prio是不同的（最高优先级任务prio在中断抢占里面被设置为了新的最高优先级任务的值），而正常thread下poll的时候恢复到有栈的任务，进入pendsv时，当前优先级任务和最高优先级任务是同一个。
• pendsv保存了上下文到psp栈后，就会将程序栈设置为最高优先级任务的栈，并且将原来保存的栈的所有权弹出到一个临时变量，如果需要上下文保存，那么最终这个所有权会被转移给旧任务的TCB里面，如果不需要保存，那么这个栈就会被回收。
• 最后就是恢复最高优先级任务的现场，这里就是将psp栈的上下文恢复到寄存器中，从而异常返回到最高优先级任务的执行。

模拟压栈

由于在中断返回时，硬件将自动执行一部分恢复现场的工作(即恢复硬件自动保存的部分：xPSR, PC, LR, R12, R0-R3)，因此在中断服务程序中进行栈分配时，我们需要对分配的新栈进行模拟压栈。其中xpsr赋值为0x01000000，PC赋值为执行器poll的地址，LR为一个TASK_RETURN函数地址，R12，R0-R3的值任意，然后是R4-R11赋值为任意, LR赋值为0xFFFFFFFD。经过模拟压栈之后，在中断服务程序返回时，就将自动复用普通的poll函数，并且将使用新分配的栈空间继续进行任务调度了。

poll函数的改造

对于执行到有栈的新任务的时候，就需要进行栈回收，因为切换到新任务执行后就是把整个psp函数栈都切换走了，那么实际上当前的这个psp栈就不需要了，所以需要将当前的程序栈设置为新任务的私有栈(即将私有栈作为公共栈)，并将新任务的栈指针设置为None，以表示该任务已经没有私有栈了，最后将原来的栈dealloc掉。