问题 如何创建并行堆栈并在其上运行协同程序?


我决定尝试执行协同程序(我认为这就是我应该如何称呼它们)以获得乐趣和利润。我希望不得不使用汇编程序,如果我想让它实际上对任何东西都有用,可能还需要一些C.

请记住,这是出于教育目的。使用已经构建的协程库太容易了(而且真的没什么乐趣)。

你们知道 setjmp 和 longjmp?它们允许您将堆栈展开到预定义的位置,并从那里继续执行。但是,它无法回滚到堆栈上的“稍后”。只能早点回来。

jmpbuf_t checkpoint;
int retval = setjmp(&checkpoint); // returns 0 the first time
/* lots of stuff, lots of calls, ... We're not even in the same frame anymore! */
longjmp(checkpoint, 0xcafebabe); // execution resumes where setjmp is, and now it returns 0xcafebabe instead of 0

我想要的是一种在不同堆栈上运行而无需线程化的两种函数的方法。 (显然,一次只能运行一次。我说没有线程。)这两个函数必须能够恢复另一个执行(并暂停自己的执行)。有点像他们是 longjmp对方。一旦它返回到另一个函数,它必须从它离开的地方恢复(也就是说,在给另一个函数控制的调用期间或之后),有点像 longjmp 回到 setjmp

这就是我的想法:

  1. 功能 A 创建并归零并行堆栈(分配内存和所有这些)。
  2. 功能 A 将其所有寄存器推送到当前堆栈。
  3. 功能 A 将堆栈指针和基指针设置为该新位置,然后按下 神秘的数据结构 指示跳回的位置以及将指令指针放回的位置。
  4. 功能 A 将大多数寄存器归零并将指令指针设置为函数的开头 B

这是初始化。现在,以下情况将无限循环:

  1. 功能 B 在该堆栈上工作,完成它需要的任何工作。
  2. 功能 B 到了需要打断和给予的地步 A 再次控制。
  3. 功能 B 将其所有寄存器推送到其堆栈,获取 神秘的数据结构  A 在最开始时给出它,并将堆栈指针和指令指针设置到哪里 A 告诉它。在此过程中,它会退回 A 一个新的,修改过的 数据结构 告诉我们要恢复的地方 B
  4. 功能 A 醒来,弹出它推送到堆栈的所有寄存器,然后一直工作直到它需要中断并给出 B 再次控制。

这一切听起来都不错。但是,有很多事情我并不是很放心。

  • 显然,在好的'x86上,有这个 pusha 将所有寄存器发送到堆栈的指令。然而,处理器架构不断发展,现在使用x86_64,我们有了更多的通用寄存器,可能还有几个SSE寄存器。我找不到任何证据 pusha 推他们。在现代的x86 CPU中有大约40个公共寄存器。我必须做所有的事情 push我自己?而且,没有 push 对于SSE寄存器(虽然必然是一个等价的 - 我对这整个“x86汇编程序”的新东西)。
  • 更改指令指针就像说它一样容易吗?我可以这样做吗 mov rip, rax (英特尔语法)?此外,从中获取价值必须有点特殊,因为它会不断变化。如果我喜欢 mov rax, rip (英特尔语法再次),将 rip 被安置在 mov 指令,之后的指令,或介于两者之间的某个地方? 只是 jmp foo。假。
  • 我已经提到过了 神秘的数据结构 几次。到目前为止,我认为它至少需要包含三件事:基指针,堆栈指针和指令指针。还有别的事吗?
  • 我忘了什么吗?
  • 虽然我真的很喜欢 理解 事情是如何运作的,我很确定有少数几个库可以做到这一点。你知道任何?是否有任何POSIX或BSD定义的标准方法,如 pthread 对于线程?

感谢您阅读我的  textwall。


10823
2018-06-22 02:24


起源

我记得上个学期我在编程语言课程中读过协程和仙人掌堆栈。我只能说是幸运的,请不要将你的野心用于邪恶。 - samoz
在[3]中:'59 6F 75 20 73 68 6F 75 6C 64 20 67 65 74 20 61 20 6C 69 66 65 2E 20 53 65 72 69 6F 75 73 6C 79 2E'.replace('','')。解码('hex')Out [3]:'你应该得到生命。严重“。 FFFUUU - L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳


答案:


你是对的 PUSHA 不会在x64上工作,它会引发异常 #UD作为 PUSHA  只要 推送16位或32位通用寄存器。见 英特尔手册 了解您想知道的所有信息。

设置 RIP 很简单, jmp rax 将设定 RIP 至 RAX。要检索RIP,您可以在编译时获取它,如果您已经知道所有协同程序退出源,或者您可以在运行时获取它,则可以在该调用之后调用下一个地址。喜欢这个:

a:
call b
b:
pop rax

RAX 现在会 b。这是因为 CALL 按下下一条指令的地址。这种技术也适用于IA32(虽然我认为在x64上有更好的方法,因为它支持RIP相对寻址,但我不知道一个)。当然,如果你做了一个功能 coroutine_yield,它只能截取来电地址:)

由于您不能在一条指令中将所有寄存器都压入堆栈,因此我不建议将协程状态存储在堆栈中,因为这会使事情变得复杂。我认为最好的做法是为每个协程实例分配一个数据结构。

为什么要将功能归零 A?这可能没有必要。

这是我如何处理整个事情,试图让它尽可能简单:

创建一个结构 coroutine_state 包含以下内容:

  • initarg
  • arg
  • registers (还包含标志)
  • caller_registers

创建一个功能:

coroutine_state* coroutine_init(void (*coro_func)(coroutine_state*), void* initarg);

哪里 coro_func 是指向协程函数体的指针。

此功能执行以下操作:

  1. 分配一个 coroutine_state 结构体 cs
  2. 分配 initarg 至 cs.initarg,这些将是协程的最初论据
  3. 分配 coro_func 至 cs.registers.rip
  4. 将当前标志复制到 cs.registers (不是寄存器,只有标志,因为我们需要一些理智的标志来防止天启)
  5. 为协程的堆栈分配一些适当大小的区域并将其分配给 cs.registers.rsp
  6. 返回指向已分配的指针 coroutine_state 结构体

现在我们有另一个功能:

void* coroutine_next(coroutine_state cs, void* arg)

哪里 cs 是从中返回的结构 coroutine_init代表一个协程实例,和 arg 将在恢复执行时被送入协程。

协程调用程序调用此函数将一些新参数传递给协程并恢复它,该函数的返回值是由协程返回(产生)的任意数据结构。

  1. 存储所有当前标志/寄存器 cs.caller_registers 除了 RSP,见第3步。
  2. 存储 arg 在 cs.arg
  3. 修复调用程序堆栈指针(cs.caller_registers.rsp),补充说 2*sizeof(void*) 如果你很幸运,你将不得不查看它,你可能希望这个函数是stdcall所以在调用之前没有寄存器被篡改
  4. mov rax, [rsp], 分配 RAX 至 cs.caller_registers.rip;解释:除非你的编译器破解, [RSP] 将保存指向调用此函数的调用指令后面的指令的指令指针(即:返回地址)
  5. 从中加载标志和寄存器 cs.registers
  6. jmp cs.registers.rip,有效地恢复执行协程

请注意,我们永远不会从这个函数返回,我们为我们跳转到“返回”的协程(参见 coroutine_yield)。另请注意,在此函数中,您可能遇到许多复杂问题,例如由C编译器生成的函数序言和结尾,也许还有寄存器参数,您必须处理所有这些。就像我说的,stdcall会救你 地段 麻烦,我认为gcc的-fomit-frame_pointer将删除结尾的东西。

最后一个函数声明为:

void coroutine_yield(void* ret);

在协同程序内部调用此函数以“暂停”协程的执行并返回到调用者 coroutine_next

  1. 存储标志/寄存器 in cs.registers
  2. 修复协程栈指针(cs.registers.rsp),再次补充 2*sizeof(void*) 对它,你想要这个函数也是stdcall
  3. mov rax, arg (让我们假装编译器中的所有函数都返回它们的参数 RAX
  4. 加载标志/寄存器 cs.caller_registers
  5. jmp cs.caller_registers.rip 这基本上是从 coroutine_next 调用coroutine调用者的堆栈帧,并且因为返回值被传入 RAX, 我们回来了 arg。我们只想说一下 arg 是 NULL然后协程已经终止,否则它是一个任意的数据结构。

所以回顾一下,你使用初始化一个协同程序 coroutine_init,然后你可以反复调用实例化的协同程序 coroutine_next

协程的函数本身被声明: void my_coro(coroutine_state cs)

cs.initarg 保存初始函数参数(想想构造函数)。每一次 my_coro 叫做, cs.arg 有一个不同的参数由指定 coroutine_next。这是协程调用者与协程通信的方式。最后,每当协同程序想要暂停时,它就会调用 coroutine_yield,并传递一个参数,这是协同程序调用程序的返回值。

好吧,您现在可能会认为“那很简单!”但是我遗漏了以正确的顺序加载寄存器和标志的所有复杂情况,同时仍然保持一个未损坏的堆栈帧并以某种方式保留您的协程数据结构的地址(您只是以线程安全的方式覆盖所有寄存器。对于那部分,您将需要了解您的编译器如何在内部工作...祝你好运:)


9
2018-06-22 05:38



哇,这么多话要说,每条评论中允许的字符很少!首先要做的事情。是的,归零寄存器可能没用。四处寻找,我从XNU项目中找到了Apple的getcontext / setcontext实现: opensource.apple.com/source/Libc/Libc-594.1.4/x86_64/gen 他们抓住了 rip 通过解除引用 rsp (没有触及整个函数的堆栈),这是有道理的,因为我们希望返回的调用从哪里开始 getcontext 将离开,而不是在某个地方 getcontext。它们也会留下非GPR寄存器。 - zneak
为什么我们需要复制标志?不复制它们会让它们不受影响,不是吗?对于通过寄存器传递的参数,在Mac OS x86上没有太多可做的事情。 八 寄存器专用于传递参数。在手上,这可能是一个优势,因为这意味着我必须节省更少的东西(他们是来电保存)。 - zneak
@zneak:好吧,说一个正在执行的协程函数以某种方式设置方向标志,然后产生。恢复时,我猜你想要恢复那个标志。 (然后,在调用普通函数时,没有人通常会保存标志...)我不确定,在你粘贴的链接中有一个RFLAGS的定义,但它们从不接触它,这一切都取决于你的编译器和运行时是如何的建立。 - L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳
实际上,他们在DEBUG中构建时保存它并在RELEASE中保留它。我不认为他们曾经恢复它(也许这真的是为了调试目的,就像在“通过getcontext在某个时刻检查rflags中的内容”)。 - zneak


好的学习参考: libcoroutine,尤其是他们的setjmp / longjmp实现。我知道使用现有的库并不好玩,但是你至少可以对你要去的地方有所了解。


1
2018-06-22 02:30



非常感谢你!我会调查它(特别是 ucontext,因为它似乎只是现场解决它没有完成所有工作所解决的问题)。 - zneak


西蒙塔特姆有一个 C中协同程序的有趣实现 这不需要任何特定于架构的知识或堆栈摆弄。这并不完全是你所追求的,但我认为它至少可能具有学术兴趣。


1
2018-06-22 04:57





boost.org上的boost.coroutine(boost.context)为你做了一切


-1
2018-03-11 12:10