boost.png (6897 bytes) Home Libraries People FAQ More

PrevUpHomeNext

Case study 1: Win32 Fibers

Introduction

This section will shortly describe the Win32 fibers facility, compare them to the POSIX makecontext/swapcontext API and finally show how Boost.Coroutine can be implemented in term of fibers.

POSIX compliance does not guarantee the presence of the context API, as this is an optional feature. It is required by the Single Unix Specification, also known as X/Open System Interface.

The APIs

The fiber API in practice implements pure symmetric coroutines. While argument passing from coroutine to coroutine is not explicitly supported, it can be implemented easily on top of the existing facilities.

The makecontext/swapcontext API is extremely similar as it supports argument-less symmetric coroutine switching.

The SwitchToFiber function is used to yield from the current fiber to a new one. Notice that it requires that a fiber is already running. The current context is saved in the current fiber.

Win32 also provides SwitchToFiberEx that can optionally save the floating point context. The Microsoft documentation warns that if the appropriate flag is not set the floating point context may not be saved and restored correctly. In practice this seems not to be needed because the calling conventions on this platform requires the floating point register stack to be empty before calling any function, SwitchToFiber included. The exception is that if the floating point control word is modified, other fibers will see the new floating point status. This should be expected thought, because the control word should be treated as any other shared state. Currently Boost.Coroutine does not set the "save floating point" flag (saving the floating point control word is a very expensive operation), but seems to work fine anyway. To complicate the matter more, recent Win32 documentation reveal that the FIBER_FLAG_FLOAT_SWITCH flag is no longer supported since Windows XP and Windows 2000 SP4.

The corresponding function in the POSIX standard is swapcontext that saves the current context in a memory area pointed by the first argument and restores the context pointed by the second argument. This function is more flexible than SwitchToFiber because it has no concept of current fiber. Unfortunately it is also deeply flawed because the standard requires requires the signal mask to be saved and restored. This in turn requires a function call. Because of this, at least on Linux, swapcontext is about a thousand times slower than an hand rolled context switch. SwitchToFiber has no such a problem and is close to optimal.

The fiber API requires a context to be created with a call to CreateFiber. The stack size, the address of the function that will be run on the new fiber, and a void pointer to pass to this function must be provided. This function is simple to use but the user cannot provide its own stack pointer (useful if a custom allocator is used). The function will return a pointer to the initialized fiber.

POSIX has makecontext, that takes as parameter a context previously initialized, a function pointer to bind to the context and a void pointer to be passed to the function. The function is a bit more awkward to use because the context to be initialized by a call to getcontext and some fields (specifically the stack pointer and stack size) to be manually initialized. On the other hand the user can specify the area that will be used as a stack.

The fiber API provides a DeleteFiber function that must be called to delete a fiber. POSIX has no such facility, because contexts are not internally heap allocated and require no special cleanup. The user is responsible of freeing the stack area when no longer necessary.

A quirk of the fiber API is the requirement that the current thread be converted to fiber before calling SwitchToFiber. (POSIX doesn't require this because swapcontext will initialize automatically the context that it is saving to). A thread is converted with a call to ConvertThreadToFiber. When the fiber is not longer needed a call to ConvertFiberToThread must be performed (It is not required that the fiber to be converted to thread was the original one) or fibrous resources are leaked. Calling ConvertThreadToFibermore than once will also leak resources. Unfortunately the Win32 does not include a function to detect if a thread has been already converted. This makes hard for different libraries to cooperate. In practice it is possible, although undocumented, to detect if a thread has been converted, and Boost.Coroutine does so. Longhorn will provide an IsFiber function that can be used for this purpose.

For the sake of information we document here how IsFiber can be implemented. If a thread has not been converted, GetCurrentFiber will return null on some systems (this appears to be the case on Windows95 derived OSs), or 0x1E00 on others (this appears to be the case on NT derived systems; after a thread has been converted and reconverted it may then return null). What the magic number 0x1E00 means can only be guessed, it is probably related to the alternate meaning of the fiber pointer field in the Thread Identification Block. This field in fact is also marked as TIB Verion. What version is meant is not documented. This is probably related to compatibility to the common ancestor of NT and OS/2 where this field is also identified with this name. While this magic number is not guaranteed to stay fixed in future system (although unlikely to change as the OS vendor is very concerned about backward compatibility), this is not a problem as future Win32 OSs will have a native IsFiber functions.

The environments

Win32 explicitly guarantees that contexts will be swapped correctly with fibers, especially exception handlers. Exceptions, in the form of Structured Exception Handling, are a documented area of the operating system, and in practice most programming language on this environment use SEH for exception handling. Fibers guarantee that exceptions will work correctly.

The POSIX API has no concept of exceptions, thus there is no guarantee that they are automatically handled by makecontext/swapcontext  (and in fact on many systems they not work correctly). In practice systems that use fame unwind tables for exception handling (the so-called no overhead exception handling) should be safe, while systems that use a setjmp/longjmp based system will not without some compiler specific help.

Win32 guarantees that a fiber can be saved in one thread and restored on another, as long as fiber local storage is used instead of thread local storage. Unfortunately most third party libraries use only thread local storage. The standard C library should be safe though.

POSIX does not specify the behavior of contexts in conjunction with threads, and in practice complier optimizations often prevent contexts to be migrated between threads.

The implementation

Boost.Coroutine can be straightforwardly implemented with the makecontext/swapcontext API. These functions can be directly mapped to yield_to(), while a transformation similar to the one described here is used to implement asymmetric functionality.

It is more interesting to analyze the implementation of Boost.Coroutine on top fibers.

When a coroutine is created a new fiber is associated with it. This fiber is deleted when the coroutine is destroyed. Yielding form coroutine to coroutine is done straight forwardly using SwitchToFiber.

Switching from the main context to a coroutine is a bit more involved. Boost.Coroutine does not require the main context to be a coroutine, thus ConvertThreadToFiberis only called lazily when a coroutine call need to be performed and ConvertFiberToThread is called immediately after the coroutine yields to the main context. This implies a huge performance penalty, but correctness has been preferred above performance. If the thread has been already converted by the user, the calls to the two functions above are skipped and there is no penalty. Thus performance sensitive programs should always call ConvertThreadToFiber explicitly for every thread that may use coroutines.

Conclusions

Of the two APIs, the POSIX one is simpler to use and more flexible from a programmer point of view, but in practice it is not very useful because it is often very slow and there are no guarantees that it will work correctly on all circumstances.

On the other hand the fiber API is a bit more complex, and matches less with the spirit of Boost.Coroutine, but the detailed description of the API, the guarantee that the operating system supports it and the support for migration, make it the most solid implementation of coroutines available.

Finally, while makecontext and family are considered obsolescent since the last POSIX edition, the fiber API is here to stay, especially because it seems that the new .NET environment makes use of it.

Copyright © 2006 Giovanni P. Deretta

PrevUpHomeNext