Uthread, a user mode threading library

  — Wim Couwenberg, Sun 30 September 2007

This file describes version 0.2 of the uthread library.

  1. Before we begin...
  2. Introduction to user mode threading
  3. Supported platforms
  4. Mixing system threads and user threads
  5. The API
  6. Build instructions
  7. References
  8. License

Before we begin...

The uthread library was my pet project for the 2006 holidays period. I am aware that other approaches exist (see the references section below). It was a pleasant and enlightening pastime. Getting uthread to run under several operating systems and processor architectures taught me a thing or two (PowerPC basics for instance). I am also pleased with the result. The API is kept small and to the point and the whole library is tiny (around 1400 lines of code according to a simple “wc -l”).

Introduction to user mode threading

The uthread library offers user mode threading support. User mode threads also go by the names “cooperative threads”, “coroutines” or “fibers”. Unlike (pre-emptive) system threads, user mode threads are implemented entirely in user mode so the operating system kernel is not involved in scheduling user mode threads. The main advantages of this are:

  1. Faster context switching between threads
  2. Easier synchronisation of threads

Thread switching in user mode does not need scheduling support from the kernel. Basically all that it takes is swapping the contents of some CPU registers with values that were saved earlier in another thread context. Just to get an idea of the cost of context switching: on my 2 GHz core duo processor, running OS X 10.4, uthread achieves about seven million thread switches per second! (And that's just using one core, as will be explained later.)

The uthread library allows to create multiple user threads within each system thread. That means that each system thread executes the code for each and every user thread that was created in it. The kernel remains unaware of the fact that a system thread is divided into several user threads though. This unawareness has a few consequences.

  1. User thread switches are not automatic (pre-emptive) but must be invoked explicitly. The uthread library functions uthread_run, uthread_wait and uthread_yield take care of this.
  2. A user thread should never block. If a user thread makes a blocking call (e.g. perform synchronous I/O or wait for an external event) then all user threads in the same system thread are blocked.
  3. Synchronisation between user threads (in the same kernel thread) is easy. Since a user thread must explicitly yield to allow other user threads to run, there's almost no need to synchronize operations. Suppose that a user thread wants to increment a counter by retrieving it, add one to its value and then store the counter again. For a user thread this procedure is safe, while for a system thread the access to the counter must be protected by a mutex, since another system thread might get scheduled and access the same counter in between retrieving and storing it. Of course, user threads running in different system threads still need synchronization.
  4. All user threads within the same system thread execute on the same processor (or core). The operating system assigns kernel threads to a fixed processor or core and thereby all user threads that are created in that system thread.

Supported platforms

The uthread library is available for Windows starting from Windows 98, 32-bit OS X (both ppc and i386, tested on 10.4 Tiger) and operating systems that support ucontext, which should include all major Linux distributions for i386 architectures.

Context switching is implemented with fibers (Windows), _setjmp and _longjmp (OS X, both architectures) or ucontext (others).

To allocate aligned memory for extra stacks uthread uses an anonymous mmap (OS X and Linux) or memalign (GNU). For Windows the stacks don't need to be allocated explicitly since this is already taken care of by the fiber API.

The uthread library uses thread local storage facilities from pthread on systems other than Windows to maintain per system thread state. The fiber API takes care of thread local storage on Windows. I'd rather not depend on pthread at all but I'm not sure how I can rely on other possibly cheaper mechanisms (like the __thread directive of gcc) purely based on compile time conditional checks.

If you got uthread to run on other platforms or have any other generally useful tips that could improve uthread then please let me know.

Mixing system threads and user threads

The uthread library and native threading models (like pthread or Windows threads) can be used together in the same process. Any native system thread can be turned into a "user thread universe" (by the uthread_init) call. You can create any number of user threads in each such universe. Remember that all user threads in the same universe are running in the same system thread. (Which is exactly the point of user mode threading.)

The uthread library is fully reantrant but, surprisingly, not thread safe. A uthread object created in one system thread (universe) must as a rule not be used by any other system thread. The only exception to this rule is the uthread_event_broadcast call. Any system thread can broadcast an event that was created in another system thread. However, the access to the event must be synchronised explicitly (by a mutex or semaphore) between system threads in that case. The uthread library does not synchronise any call by itself.

The API

The following types and functions are declared in the public interface header file uthread.h. This is the only header file you need to include to use the uthread library.

typedef struct uthread_t *uthread_h;

The type uthread_h is used as an opaque object handle. An object can be a thread, an event or a queue.
typedef void (*uthread_func_t)(void *args);
The type uthread_func_t is the signature of a function that can be executed in a new user thread.
UTHREAD_API void uthread_init(void);
This function must be called in any system thread that wants to use the uthread library. It turns the system thread into a main user thread. uthread_init can be called in any number of system threads, each with their own main user thread. The uthread library can then be used in the system thread until uthread_exit is called from the main user thread.
UTHREAD_API int uthread_wait(uthread_h object);
Makes the calling user thread wait for an object to become signaled or until the object is closed. The object must have been created in the caller's system thread. A user thread is signaled when its start function finishes execution. The thread handle is not implicitly closed, unless the thread exited with a call to uthread_exit. An event is signaled when uthread_event_broadcast is called for that event and becomes non-signaled again after scheduling all its waiting threads. A queue is signaled if and only if an observed state change is available in the queue. Use uthread_queue_get to retrieve the change.

If the object is already signaled then the effect is the same as calling uthread_yield, i.e. execution can still be interrupted in favour of other scheduled threads.

A call to uthread_wait will never block the underlying system thread. If no other user thread is scheduled for execution then one of two things can happen: If uthread_wait is called from the main user thread, then it returns immediately with a result UTHREAD_NONSIGNALED. If it is called from another user thread, then execution is forced back to the main thread. In that case, the main thread gets a UTHREAD_NONSIGNALED result if it was blocked on a uthread_wait or uthread_run call.

uthread_wait returns UTHREAD_NONSIGNALED if the thread was released while the object was non-signaled, UTHREAD_SIGNALED if the object was signaled and UTHREAD_CLOSED if the object was closed. If uthread_wait returns UTHREAD_CLOSED then the object handle is no longer valid.

UTHREAD_API void uthread_close(uthread_h object);
Closes the object handle. The object handle cannot be used after it has been closed. The object must have been created in the caller's system thread. Any uthread_wait call blocking on this object will return with a UTHREAD_CLOSED result.
UTHREAD_API int uthread_run(void);
This function can only be called in a main user thread. It suspends the main user thread until all other user threads (in the same system thread) are either signaled or suspended in a wait. A user thread is signaled if its start function finished. If no other user threads remain or all remaining user threads are signaled then the return value is UTHREAD_SIGNALED. If at least one other user thread is suspended then the return value is UTHREAD_NONSIGNALED.
UTHREAD_API uthread_h uthread_create(int stack_size, uthread_func_t start_func, void *args);
Create a new user thread. If stack_size is positive then a stack of at least that size in bytes is created for the thread. If stack_size is zero then a default stack size is chosen (1 Mb for Windows, 16K for other systems). The new thread will not execute immediately but it is scheduled for execution. When it becomes active for the first time it starts executing start_func with argument args. The returned object handle will get signaled when start_func returns. Calling uthread_exit in the new user thread will unconditionally stop execution and close the thread handle. A user thread (except the main thread) can close its own handle, which has the same effect as calling uthread_exit.
UTHREAD_API void uthread_exit(void);
When called from the main thread this will uncoditionally free all threads, events and queues that were created in the same system thread. The uthread library cannot be used in that system thread until uthread_init is called again. (Caveat: for Windows systems prior to XP, uthread_init can only be called once for each system thread.)

When called from a thread other than the main thread it interrupts the execution of that thread and closes its handle. The uthread_exit call does not return. If no other threads are scheduled to execute then execution is forced back to the main thread.

UTHREAD_API uthread_h uthread_self(void);
Returns the calling thread's handle or NULL if called in the main thread. Note that NULL is not a valid thread handle, so you cannot wait for it or close it.
UTHREAD_API void uthread_yield(void);
If other threads are scheduled to execute then this call switches execution to another thread. If no other threads are scheduled then this call returns immediately.
UTHREAD_API uthread_h uthread_event_create(void);
Create a new event object. The object can only be used in calls from the same system thread that created it. An event handle can be close with uthread_close.
UTHREAD_API void uthread_event_broadcast(uthread_h event);
Set the event's state to signaled. All threads that are waiting for this event are scheduled to execute, after which the event's state is set to non-signaled again. This function can be called from another system thread than the one in which the event was created. In that case the access to the event must be synchronised between the two system threads. The uthread library itseld does not synchronise this call for you.
UTHREAD_API uthread_h uthread_queue_create(void);
Create a new queue object. Other objects that were created in the same system thread can be added to a queue to be watched for state changes (when the object is signaled or closed). After such a state change, the object is removed from the queue. Observed changes can be retrieved via uthread_queue_get. An object can be added multiple times to a queue. In that case a state change for that object is also reported multiple times. The created queue object can only be used from the caller's system thread. Close the queue handle with uthread_close if it is no longer needed.
UTHREAD_API void uthread_queue_add(uthread_h queue, uthread_h object);
Add and object to be watched by the queue. Both the queue and the object to add must have been created in the caller's system thread. When an object that is added to the queue gets signaled or is closed then the object is removed from the queue and the change is obtainable via uthread_queue_get. A queue is signaled precisely if observed changes are available.
UTHREAD_API int uthread_queue_get(uthread_h queue, uthread_h *object, int *state);
Obtain state change information for an object that was added to the queue with uthread_queue_add. If no information is available then this call returns 0. Otherwise the object handle for which a change is reported is placed in *object and the changed state of the object is placed in *state. The state can be UTHREAD_SIGNALED or UHTREAD_CLOSED. If the state is UTHREAD_CLOSED then the object handle was closed and is no longer valid. Otherwise, if you want to watch the object again you should add it to the queue with uthread_queue_add.
UTHREAD_API void uthread_queue_reset(uthread_h queue);
Reset the queue. All objects will be removed from the queue and any available state change information is flushed. The queue will be in the same state as if it had been just created with uthread_queue_create.

Build instructions

The source files to compile for Windows are uthread.c and uswap.c. (The file ustack.c is not needed since fibers allocate their own stack.) If you want to build a DLL then define the macro UTHREAD_EXPORT and compile with the appropriate compiler switches. Make sure that the _WIN32_WINNT macro is defined to a value that is appropriate for your Windows platform (at least 0x0400). See MSDN for more information.

For other systems compile uthread.c, uswap.c and ustack.c. If you want to build a shared library, dynamic library or bundle then define the macro UTHREAD_EXPORT. This will export only the public symbols when you use a gcc version that supports the visibility attribute. Enable pthread support for thread local storage.

To compile without assertions define the macro NDEBUG. To compile with a custom assertion macro either define uthread_assert accordingly or adjust the uassert.h header file.

References

Here are some other interesting links related to the subject.
  1. Edgar Toernig, CORO
  2. Steve Dekorte, libCoroutine, a small, portable coroutine implementation
  3. Ralf S. Engelschall, GNU Pth, The GNU Portable Threads
  4. Russ Cox, thread section from Plan 9 from User Space
  5. Fibers entry on MSDN

License

The uthread library is distributed under the liberal MIT license as stated in the file “COPYRIGHT”.