当前位置： 代码迷 >> 综合 >> How to implement fiber
  详细解决方案

How to implement fiber

热度：66   发布时间：2024-01-17 20:29:41.0

Introduction

我们知道线程是程序执行的一个最基本的单位，任何程序的执行，都依赖于线程的执行。而线程通常是操作系统的基本组成，通常创建一个线程，比如在Win32上，用CreateThread创建一个线程，操作系统实际会创建2个对象，一个是用户态的线程，另一个是内核态的线程，而我们的代码运行在用户态线程。当线程切换时，比如调用WaitForSingleObject，或者调用WriteFile执行阻塞IO时，通常会涉及到线程的切换，而切换需要进入到内核态，由此带来的开销是比较可观的。而Fiber，也就是纤程，完全运行在用户态，各个线程的切换也只在用户态完成，所以切换开销较小。线程的调度，通常是由操作系统的线程调度器完成，在现代OS中，通常使用抢占式调度策略。而纤程的调用，完全依赖于程序员自己，即实现一种合作式调度，只有在主动提出切换时，才会进行切换。

纤程，在其他的语言，比如Python、Lua中都有实现。Python中提供了generate，可以用来简单地模拟纤程，而另外一个强大的greenlet库，则是Python中纤程的另一实现。在Lua中，我们可以使用内置的coroutine库。

Basic Usage

 
Win32

在Win32中，我们可以使用ConvertThreadToFiber/ConvertFiberToThread，CreateFiber/DeleteFiber来管理纤程的创建与销毁。对于一个线程，如果要调用纤程，那么必须调用Convert，将一个线程转化为纤程。当需要切换到另一个纤程时，只需要调用SwitchToFiber，这样现有的线程的一些状态将被保存，等待以后恢复执行。

Linux

Linux中有context api，可以用来完成类似的功能。我们调用getcontext/makecontext，来初始化纤程，用swapcontext/setcontext来切换纤程。

setjmp/longjmp

说到这里，我们不得不提起另一个看似可以用来完成类似工作的古老的C API，setjmp/longjmp。setjmp用来保存当前的执行环境，longjmp用来还原上次的执行，这样可以实现non-local goto的功能。但是这里有一个问题，就是当我们调用longjmp回到setjmp保存的状态继续执行时，如果longjmp的调用者与setjmp的调用者不是同一个函数，那么longjmp所在的栈的状态将是undefined[1]。也就是说，我们不能通过在longjmp之前，save状态，之后再longjmp回来，这是未定义的行为。当然，在win32上，你可以这么做，而且还工作地很好（我在实现中使用了这一技巧）。但是在linux上，你将会遇到运行时错误，提示stack smashing（gcc的stack保护机制，__fortify_fail），也就是栈被破坏了（这令我debug了很长时间，最后放弃，网上看到许多实现用这方法，但是不奏效）。setjmp/longjmp还有其他陷阱，比如，在win32上，他不会保存/恢复SEH异常链，等等。

How Fiber works

其实无论是哪种方法，我们只需要明白Fiber是如果工作的，那么就可以实现出自己的fiber来（当然这里还需要考虑其他一些CPU相关的情况）。

Fibe类似于线程，都有一个栈用来保存当前的调用所需的状态。所以我们首先需要为fiber创建一个栈。其次由于每个fiber肯定需要一个入口函数（就像线程一样），在切换时，需要进入到这个入口，然后执行。其实代码的执行在x86 CPU上，就是修改EIP指针，将其指向这个入口函数即可。在切换纤程时，也就是保存我们的栈的状态，x86上，ESP和EBP是两个重要的寄存器，保存了当前的栈的状态。我们还需要保存其他的通用寄存器，EBX、EDI、ESI，因为不同纤程显然会修改寄存器。这里不保存其他3个寄存器：EAX、ECX、EDX的原因是，这些寄存器都是caller-save的[4]，也就是说，如果调用者使用了这些寄存器，那么在调用其他函数前，必须先保存这些寄存器。

这里涉及到两个问题，一个是修改EIP指针，另一个是保存/恢复寄存器值。

Modify EIP

因为EIP指针只有在特权模式才能够修改（操作系统工作在特权模式），我们用户态程序是无法直接修改的。但是我们知道，jmp指令时可以间接修改EIP的。还有另一个方法是用ret指令，ret指令会从栈顶取出值作为EIP的值，这样就实现了跳转。这里我选择使用push + ret的方式来修改eip，因为jmp要求使用相对于下一条指令的偏移作为操作数（Relative jumpping）。

Save/Restore GPR(general-purpose registers)

保存和回复GPR比较简单，用几条汇编指令即可完成。

Save/Restore Stack Pointer

在Save/Restore EBP/ESP时，需要格外小心，因为一旦我们修改了ESP，那么在之后所有的对栈的操作都将在新的栈上进行。

Implementation

先来看一下fiber_context的成员，这个struct用来保存寄存器和栈的指针/大小等。

struct fiber_context
{
#ifdef FIBER_X86// registersuintptr_t ebp;uintptr_t esp;uintptr_t eip;// callee-save general-purpose registers// see http://www.agner.org/optimize/calling_conventions.pdfuintptr_t ebx;uintptr_t esi;uintptr_t edi;
#else
#  error Unsupported platform
#endifchar* stack;int   stack_size;void* userarg;
};
 
 
所有callee-save的GPR，以及ebp/esp/eip都会被保存。这个比较简单。
 
 
fiber_make_context
 
 
这个函数用来创建一个context，初始化执行环境。
 
 
void fiber_make_context(fiber_context* context, fiber_entry entry, void* arg)
{assert(context && entry);// default alignment of the stackconst int alignment = 16;context->esp = (reinterpret_cast<uintptr_t>(context->stack) + context->stack_size) & ~(alignment - 1);context->ebp = context->esp;context->eip = reinterpret_cast<uintptr_t>(entry);context->userarg = arg;// push the argument onto the stackchar* top = reinterpret_cast<char*>(context->esp);memcpy(top, &context->userarg, sizeof(void*));// make space for the pushed argumentcontext->esp -= sizeof(void*);// clear all callee-save general purpose registerscontext->ebx = context->esi = context->edi = 0;
}

这里，我们初始化了esp，和ebp，同时指向栈顶。注意，x86 CPU使用full-descending stack，也就是逆向增长的栈。因为用户可以提供一个可选参数，所以我们必须事先将这个参数压栈，这样在将EIP重定向后，入口函数就可以正常存取这个参数了。自然，压栈后，我们必须减小esp的值，为参数留出空间。EIP的值指向入口函数的地址，这个很容易理解。其余部分只是简单地初始化GPR的默认值。 
 
 
 
fiber_get_context
 
 
该函数用来保存当前的执行状态。因为我们可以通过fiber_set_context来从一个由fiber_get_context初始化的context中恢复执行，这里必须考虑这种特殊情况。我们不能简单地保存esp/ebp的值，因为一旦我们从fiber_get_context返回，该函数的stack frame将会被销毁，这样如果保存的esp/ebp指向的是fiber_get_context的frame的话，那么很显然会出现运行时错误。我们唯一能够做的就是，保存调用者的栈。
 
 
对于每一个c/c++函数，编译器都会在入口处安插指令来保存调用者的ebp，并且修改ebp/esp来创建新的stack frame。所以我们不能写一个普通函数来完成这个工作。我们需要一种方法，不让编译器生成prolog/epilog，这样我们就有更多的控制权。在VC中，我们可以使用naked函数，在GCC，我们只能写汇编源代码。
 
 
__declspec(naked) void fiber_get_context(fiber_context* context)
{// TODO: how much space need to reserve for assert ?//assert(context);// save the current context in `context' and return__asm{// save current stack pointer to contextmov ecx, dword ptr [esp + 0x4] ;fixup, point to the argument, ignore return addressmov dword ptr [ecx], ebp ; context->ebpmov eax, esp// fixup esp, ignore return address, as the eip is set to the caller's addressadd eax, 0x4mov dword ptr [ecx + 0x4], eax ; context->espmov eax, dword ptr [esp]mov dword ptr [ecx + 0x8], eax ; context->eip// save callee-save general-purpose registersmov dword ptr [ecx + 0xc],  ebx; context->ebxmov dword ptr [ecx + 0x10], esi; context->esimov dword ptr [ecx + 0x14], edi; context->ediret}
}
这里在保存调用者的esp时，我进行了一些修正，以得到调用fiber_get_context之间的值（这个值包括被压栈的参数）。在x86上，当调用一个函数时，调用者与被调用者栈的布局是这样的
 
 

 
 
 
所以，要拿到返回值，只需要将ebp加上4即可。但是由于我们是一个naked function，所以，这里我们只能通过esp来取值，考虑压栈的eax, ebx，对esp加上8，即可得到返回地址。
 
 
fiber_set_context
 
 
该函数用于切换到另一个context，调用该函数后，会直接切换到新的fiber，而控制流不会返回，所以我们可以不用考虑栈的使用情况，而只需简单回复即可。 
 
 
void fiber_set_context(fiber_context* context)
{__asm{; restore the enviroment for contextmov eax, contextmov ebp, dword ptr [eax]        ; context->ebpmov esp, dword ptr [eax + 0x4]  ; context->esp; restore callee-save general-purpose registersmov ebx, dword ptr [eax + 0xc]  ; context->ebxmov edx, dword ptr [eax + 0x10] ; context->edxmov esi, dword ptr [eax + 0x14] ; context->esimov edi, dword ptr [eax + 0x18] ; context->edipush dword ptr [eax + 0x8]      ; context->eipret; should never return here}
}
这个函数看上去比较简单，只是简单地恢复寄存器的值，并设置eip指针。
 
 
fiber_swap_context
 
 
这个函数会保存当前的context，并切换到新的context。这个函数可以用fiber_get_context/fiber_set_context来实现。
 
 
 
void fiber_swap_context(fiber_context* oldcontext, fiber_context* newcontext)
{assert(oldcontext && newcontext);// save the current context in the oldcontext and set the current context from newcontext__asm{push oldcontextcall fiber_get_context// fixup oldcontext->esp, ignore pushed arguments, since we'll resume from restoremov eax, oldcontextadd dword ptr[eax + 0x4], 0x4// fixup return addressmov dword ptr[eax + 0x8], offset restore// switch to newcontextpush newcontextcall fiber_set_contextrestore:}
}
在保存当前执行环境时需要注意一点，因为我们调用fiber_get_context时save的eip指针的值应该是call的下一条指令的地址，在这里就是push eax，但是我们不希望这样，因为随后我们就会调用fiber_set_context。所以我们必须修正EIP，以跳过对fiber_set_context的调用。这里还有一点需要注意，那就是esp的值，由于我们调用fiber_get_context手动对参数进行压栈，所以在从restore恢复执行时，esp的值还包含oldcontext这个参数。但是restore之后我们就直接返回了，所以我们必须修正esp的值，减去压栈的oldcontext（其实这里理论上不用修正esp，因为在函数的epilog中，会自动将ebp赋值给esp，所以修正没有意义，但是由于VC会在函数最后安插栈完整性的检查代码，所以为了防止这个错误，必须修正）。 
 
 
 
TODO
 
 
这里我们只保存了GPRs，没有对其他的寄存器，比如浮点控制寄存器等进行保存。
 
 
Summary
 
 
在无法大量创建线程的环境中，纤程提供了一定的解决方案，因为纤程更加轻量，从而可以实现更高的并发性。
 
 
Source Code
 
 
代码存放在github上便于下载，git url为git://github.com/alexshen/fiber.git，网页地址为https://github.com/alexshen/fiber
 
 
Reference
 
 
[1] setjmp.h Wikipeida
 [2] qemu coroutine
 [3] Gcc Inline Assembly
 [4]Calling conventions for different C++ compilers and operating systems



                  

                  
                  
                  

                

                

              


			  
			

				
				
			


        
             

                
  相关解决方案

                
                

                  
                

              

               
            

            
            

              

                

                 	

				    
				    
                

              

            

            
            
            

          

          

        

        

      

      
      
      

     

         

         
         	代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）

         Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.