2008-08-26:

Fibers in a thread

windows:winapi:c:c++
Inspired by noglorps post on OpenRCE I've finally decided to play with Windows fibers, and I found out that it's quite an interesting topic.

What is a fiber anyway? One can say that a fiber is a type of a thread (an execution unit in a process). What's the difference between a fiber and a thread then? The difference lies in th scheduler - the thread scheduler is located in the system kernel, and switched between threads when it wants, in an invisible to the programmer way (a small exception are the Sleep(0) and SwitchToThread() functions, and other functions that block execution). On the opposite, the fiber scheduler must (can?) be created by the programmer himself (so there is no kernel-level scheduler that silently switches the fibers). To do that, the coder gets few simple and intuitive WinAPI functions:

SwitchToFiber(void *pFiber) - like the name suggests, it switched from the currently executed fiber to the given one (one must note that while you cannot tell which thread should be executed to the SwitchToThread function, you have to tell which fiber will be executed to the SwitchToFiber).
ConvertThreadToFiber(void *pParam) - like the name says, converting a thread to a fiber - in truth, it's just making the thread be able to switch between fibers.

Additionally, we get another function to define new fibers:
CreateFiber - is used to create a new fiber; in opposition to CreateThread, the newly created fiber does not begin executing the provided function, because telling when to start lies to the coder-made scheduler (which can even be only one SwitchToFiber call).

There are other functions, but the above are sufficient.

From the logical point of few, the coder has to create a few fibers (CreateFiber) and of course store their handles (the thing returned by CreateFiber). Next, the thread has to be converted to a fiber (ConvertThreadToFiber), and now it can begin switching between fibers (SwitchToFiber, everything inside one thread). One can say that fibers are execution units working inside a thread, but it must be noted that only one fiber works at one time (of course if one converts more threads into fibers, more fibers can work at the same time).

How to create a simple scheduler? Just for tests I've created 4 worker fibers, and one scheduler-fiber. After converting the thread to a fiber, I've switched it (the fiber-thread) to run the fiber-scheduler, which was just a simple loop that switched the worker threads. One must note that SwitchToFiber stores the place where the switch took place in the "old" fiber, and when the execution returns to that fiber (another fibers calls SwitchToFiber with that fiber) it begins at the EXACT same spot where it paused. A worker-fiber then works, and after making a piece of the work, it switches back to the scheduler-fiber, which grants the CPU to yet another worker-fiber. And so it goes until all the fiber have completed their job.

The code looks like this (full version of the code is available to be downloaded at the bottom of the page):

First a few declarations:
#define FIBER_COUNT 4

LPVOID FiberScheduler;
LPVOID Fibers[FIBER_COUNT];
int    FiberDone[FIBER_COUNT];


Next, the worker-functions of the worker-fibers:
void __stdcall MyFiber(void* Param)
{
 int i;
 int FiberNr = (int)Param;
 printf("%i: start\n", FiberNr);

 for(i = 0; i < 5; i++)
 {
   // Do something
   printf("%i: in loop %i, before switch\n", FiberNr, i);
   // Go back to scheduler
   SwitchToFiber(FiberScheduler);
   // Do something again
   printf("%i: in loop %i, back from switch\n", FiberNr, i);
 }

 // End of work
 printf("%i: done\n", FiberNr); fflush(stdout);
 FiberDone[FiberNr] = 1;

 // Back to scheduler
 SwitchToFiber(FiberScheduler);
}


The above function just iterates 5 times a loop, and every iteration it returns to the scheduler.
Now it's time for the scheduler himself:

void __stdcall MyScheduler(void *Param)
{
 int i;
 int CurrentFiber = -1;
 puts("S: start");

 while(1)
 {
   int DoneCount = 0;
   puts("S: schedule loop begining");

   // Check if all done
   for(i = 0; i < FIBER_COUNT; i++)
     DoneCount += FiberDone[i];

   if(DoneCount == FIBER_COUNT)
     break;

   // Switch to next av. fiber
   // There has to be at least one
   do
   {
     CurrentFiber++;
     if(CurrentFiber == FIBER_COUNT)
       CurrentFiber = 0;
   }
   while(FiberDone[CurrentFiber]);

   // Switch to it
   printf("S: schedule loop switching to fiber %i\n", CurrentFiber);
   SwitchToFiber(Fibers[CurrentFiber]);
   printf("S: schedule loop back from fiber %i\n", CurrentFiber);
 }

 puts("S: done");
}


As you can see, the code is rather simple - the scheduler is in a loop, which breaks when all the fibers are done (which is checked at the beginning of the loop). In the loop there is only the previously-mentioned check, selecting another not-finished fiber, and switching to it. After the return from worker-fiber the code executes from the switch place, and makes another loop iteration, until all the fibers finish their work.
The thread execution looks like this: ConvertThreadToFiber -> SwitchToFiber(FiberScheduler) -> SwitchToFiber(Fiber[0]) -> SwitchToFiber(FiberScheduler) -> SwitchToFiber(Fiber[1]) -> SwitchToFiber(FiberScheduler) -> ...

What's interesting, the scheduler doesn't have to have a separate fiber - it can be integrated with the worker-fibers to form a kind of looped linked list - each fiber knows which fiber is "next" in the queue, and performs SwitchToFiber(NextFiber) after a piece of work is done.

Of course the fibers do not have to pretend there are threads (preemption, changing the tasks while executing, etc), they can be task-orientated - each fiber would work uninterrupted from its start to its end, and then would switch to the scheduler which would choose another fiber-task. It sounds useful.

And now let's take a look from another side. How does this all work? After a moment one can figure out that it's rather simple to create such a mechanism. The fiber itself can be described by a simple structure that stores registry values (general purpose, flags, coprocessor and extensions (it's almost the same thing anyway ;>)), the EIP address which tell where to continue the execution, and information about the memory reserved for the fiber (for example the stack - each fiber has it's own stack). When we have such a structure, then the SwitchToFiber is trivial to write (store registry value, restores values from another fibers structure, and jump to it's EIP) and can be done totally in the user mode. Going a step further, CreateFiber just allocates and setups the previously described structure, so it can be done in user mode too. ConvertThreadToFiber doesn't really differ much from the CreateFiber, user mode too. So as one can imagine, the fiber mechanism seems rather simple, and doesn't require the usage of Fiber API (however it's still good that there is such an API).

Are fibers useful? It's a hard question. No usage which would reeeeallly require fibers comes to my mind. However, I don't see any reasons why fibers shouldn't be used in some places. I can suspect that if some daemon does task-based work it would use fibers. I see also some usage in case of some VMs/interpreters - for example, a multi threading in a VM handled by a bunch of threads with several fibers in each. Fibers have one good thing - they have their own stack, so if they mess something bad with the stack, other fibers are untouched.

IMHO fibers are quire interesting, and maybe I'll even use them someplace in the future. If some idea that would make sens comes to my mind, I'll post it here ;>
Btw, Linux doesn't have fibers built-in, but google said that there are several fiber libs (however I don't know if these are the fibers I'm talking about ;>)

OK, thats it for today.

fibers.cpp (3kb)

UPDATE 2009-03-10: I've got a link (from darkjames, thx!) to a great lecture (slides available too) on fibers: Tango conference 2008 - Fibers talk by Mikola Lysenko

Add a comment:

Nick:
URL (optional):
Math captcha: 6 ∗ 1 + 4 =