Cross-Platform Coroutines in C++

Coroutine Specifics

Coroutines are mutual subroutines with the following three properties:

• Local data to a coroutine persists between successive calls.
• Execution is suspended at the point where control leaves a coroutine (perhaps to allow another coroutine to produce something for it). When control reenters the coroutine, execution is resumed at the point where it previously left off.

• Control can be passed from one coroutine to another, causing the current coroutine to suspend its execution and transfer control to the new coroutine.

In a traditional subroutine program structure there is an asymmetric master/slave relationship between a calling program and a subroutine. When a subroutine gets control via its single port of entry, all nonparameter variables that are not global are undefined (or perhaps set to some "zero" value). Coroutines are subroutines that may call each other but do not have the master/slave relationship. On exit from a coroutine, its state is saved and the next time the coroutine is called it resumes execution at exactly the point where it left off. In addition, its variables are maintained in the same state as at the end of the previous suspension (via a private stack).

Since the location of the subroutine in the aforementioned definition is not tied to any specific operating-system resource, coroutines can be modeled as completely separate processes (possibly on different machines), different threads in a single process, or as special subroutines in a single thread of computation. In this article, coroutines will be presented as the latter, although the code could be used as a basis for generalization into a multithreaded/multiprocessor environment.

The Coroutine Interface

To illustrate the basic requirements of a coroutine interface, I'll use the Odd Word problem described by E.W. Dijkstra (see "Notes on Structured Programming," Structured Programming, Academic Press of London, 1972). Consider a character set consisting of letters, a space, and a point. Words consist of one or more, but at most 20 letters. An input text consists of one or more words separated from each other by one or more spaces and terminated by 0 or more spaces followed by a point. Input should be read from and, including the first letter of the first word, up to and including the terminating point. The output text is to be produced such that successive words are separated by a single space with the last word being terminated by a single point. Odd words 1, 3, 5, ... are copied in reverse order while even words 0, 2, 4, ... are merely echoed. For example, the input string:

"whats the matter with Kansas"

becomes:

"whats eht matter htiw Kansas."

The problem is further restricted in that the characters must be read and printed one at a time.

Although somewhat contrived, this problem lends itself well to a solution using coroutines because you can interleave the reading of words and the printing of either the word itself or its reverse. One of the coroutines in the solution described at the end of the article (PrintRoutine) has a main routine that alternately reads a word, "pretties" it by removing spaces, and then prints it. It then does the same thing but this time prints the word in reverse order. PrintRoutine's requirements are straightforward. As a coroutine it must be created and initially started. It must also have the ability to suspend itself and then transfer control to another coroutine (in this case the coroutine that strips spaces).

Class CCoroutine provides the capability to do this. It contains a constructor, destructor, and an initialize routine that returns a pointer to a CCoroutine that has just been created. The initialize method is used to possibly preinitialize any variables needed by the coroutine after it is created but before it starts execution. The pure virtual method go is the point of entry for the coroutine. It must be overridden and will either contain code or a call to another function. Finally, the method resume transfers control out of the coroutine (suspending it at the point where resume is invoked) to the CCoroutine object stored in the argument to resume. Example 1 presents the class (excluding some of the bookkeeping details). This interface is suitable for solving the illustrative example in this article and also for more sophisticated applications. From this simple interface the platform-specific versions are constructed. I'll start with the Microsoft Windows NT implementation.

Coroutines for Microsoft Windows NT

Listing One is the code for the Microsoft Windows NT implementation of coroutines. The NT class CTargetPlatformCoroutine is based on the Windows fiber library. A fiber is a thread-like pseudoprocess that is manually scheduled by the application. Fibers run in the context of the threads that schedule them (but have their own fiber-specific stacks). A thread is allowed to schedule multiple fibers. The only state information maintained for a fiber is its stack, the state of its registers that are typically preserved across a function call, and the fiber data provided during fiber creation.

The ConvertToFiber API routine creates an area in which to save fiber state information. Subsequently, you can start the new fiber or convert to a new one by calling CreateFiber. A fiber is preempted by the application when another fiber or thread calls SwitchToFiber. However, when the thread that scheduled the fiber is preempted by the system, the fibers of the thread are also suspended. If a fiber calls ExitThread, execution terminates for the thread that created it.

The class CCoroutineState is used as a helper class to wrap, in this case, the main fiber of the coroutine. At construction, a new CCoroutineState object state_ is created, given a default stack (whose size can be customized by the user with the constructor argument), and its fiber is created. The initialize method of the CCoroutine class is used in the NT implementation to create fiber-specific state information using ConvertToFiber. Initialize serves as a coroutine factory. Once a CTargetPlatformCoroutine has been initialized it is ready to "go" and can be used in a call to resume. In Example 2, you switch to the new coroutine if necessary (other != this); otherwise, the actual coroutine context switch is accomplished with the fiber API call SwitchToFiber.

Coroutines for Solaris

Listing Two is the Solaris code that implements the CCoroutine interface. POSIX threads are the building blocks of the coroutine class for Solaris. Although pthreads implementations exist for Win32, they don't match the coroutine functionality as naturally as do fibers, thus the variance between the two platforms. There are ports of the fiber library on UNIX — namely via the Mainwin toolset from Mainsoft (http://www.mainsoft.com/); also see my article "Porting C++ Code from NT to UNIX Using the Mainwin XDE Toolkit" (DDJ, April 1999) — but these implementations invariably sit on the POSIX thread library, which leads to our direct use of it here. Since there are several excellent descriptions of pthreads (Programming with POSIX Threads, by D. Butenhof, Addison-Wesley, 1997, for example), I will proceed directly to the description of the Solaris extension of CCoroutine, also called class "CTargetPlatformCoroutine."

In this class, all of the work needed to construct the coroutine and get it ready to go is in the constructor. I start by creating and initializing a pthread_attr_t object attr (which is the type of thread attribute object). The stack size for the coroutine is then negotiated and assigned with pthread_attr_setstacksize. The final three statements of the constructor (Example 3) set the state of the pthread to PTHREAD_CREATE_DETACHED, allowing resources to be freed when the thread terminates, create the thread, and then destroy the pthread_attr_t object.

Helper class CCoroutineState is more involved in the Solaris case since we have to explicitly control access to the pthread. The two important methods are waitToGo and signalToGo. They make use of a condition variable synchronization primitive go_cond_ and a mutex go_mutex_. waitToGo grabs the go_mutex_ and loops while go_ is False (someone else has the mutex). Finally, when go_ is True, the mutex is released and the caller knows it is safe to execute. signalToGo is called when it is time to broadcast that the caller is ready to yield (this is where go_ is set to True). Notice that this will block if pthread_mutex_lock can't initially get the mutex. The third argument to pthread_create in the constructor passes the static method crstart to the thread. This uses waitToGo to signal the start criterion for the coroutine. pthread_create passes this->state to crstart and after calling waitToGo, the coroutine's go method is called; see Example 4. resume is similar to its counterpart in the Windows NT implementation. After making sure that the caller isn't trying to switch to the present coroutine, resume calls signalToGo and waits until the next coroutine (other) is ready to begin execution. After this, blocking call returns, resume calls waitToGo, and control is transferred to the CCoroutine object other; see Example 5.

In both extensions of the coroutine interface, the method go just asserts if called. This points to the usage model for the class. A coroutine should extend the appropriate class and then override the virtual go method. The actual code of the coroutine is called from go (or possibly resides in that method depending on the complexity). go will likely contain one or more calls to resume. This is demonstrated in the solution to the Odd Word problem that uses coroutines.

Solution to the Odd Word Problem

Although the solution to the Odd Word problem is simple, it is an apt example of the use of coroutines and can be generalized to more complex tasks (see Listing Three). Three coroutine classes are used: ReadWord, ReadSpace, and PrintRoutine. Each is an extension of class CTargetPlatformCoroutine. Because the amount of code used in the problem solution is relatively small for each coroutine instance, the bodies of the coroutines have been left in the public method go.

The program takes a single argument, a string of characters that is interpreted as a sequence of words separated by spaces. If no argument is given, the default string in the main function is used as an example. The input is stored in the variable InputString. After the input is read in, the three coroutine objects are created: rwrd, rspc, and prtn. I begin by calling rspc->go(), which transfers control to the first coroutine, a ReadSpace object. ReadSpace looks at the characters of InputString one at a time starting at the beginning and skips spaces. If a period is encountered, it is echoed to standard output and processing ceases. Spaces are skipped and if one was encountered, a single space is echoed to standard out in its place.

Once the first character of a word is examined, the ReadSpace object suspends itself and transfers control to the ReadWord object with the call resume(rwrd). The code in this coroutine copies characters of the current word into a character buffer Word1 that is globally accessible to all the coroutines. When the word has been completely parsed, the ReadWord coroutine suspends itself and transfers control to the PrintRoutine. Example 6, the body of PrintRoutine::go, consists of an infinite loop that does two things: The first time through the loop it echoes the current word to standard output in order and then resumes execution in ReadSpace. Once control is transferred back, the PrintRoutine object echoes the current word to standard output in reverse order (and again transfers control to ReadSpace). The consecutive nature of the print loops keeps track of whether the word is odd or even and prints the correct order of the characters. Again, processing ends in ReadSpace::go when a period is encountered.

Conclusion

Coroutines are a natural solution to parsing problems and have been used widely by assembly language programmers. Because they closely mimic the interactions between certain hardware devices and electronic components, coroutines are also a natural programming tool for architects of electronics design tools. Since languages such as Lisp have language-level coroutines, they are also known to the AI community and have been employed in solutions to intelligent scheduling problems.

Although coroutines do not provide an advantage over a well-designed multithreaded application for typical GUI scenarios, they are very useful when the design calls for careful control over scheduling and can certainly make such a design easier to understand by exploiting any inherently mutual subroutines in a solution.

DDJ

Listing One

#ifndef _CWinNTCoroutine_h_
#define _CWinNTCoroutine_h_
//////////////////////////////////////////
// CWinNTCoroutine.h
#ifdef _WIN32
#ifdef _COROUTINE_DLL
#define ExportStatus _declspec(dllexport)
#else
#define ExportStatus _declspec(dllimport)
#endif
#else
#define ExportStatus
#endif
#include <assert.h>
/////////////////////////////////////////////////////////
class ExportStatus CTargetPlatformCoroutine : public CCoroutine {
public:
    CTargetPlatformCoroutine(unsigned stackSizeInBytes = DEFSTACKSIZE);
    virtual ~CTargetPlatformCoroutine();
    virtual void go(){assert(0);}
    virtual void resume(CCoroutine *next);
};
#endif
/////////////////////////////////////////////////////
// CWinNTCoroutine.cpp
/////////////////////////////////////////////////////
// CCoroutineNT.cpp
// NT implementation of Coroutine interface.
#if (!defined(_WINNT) || !defined(_WIN32_WINNT))
#error "This module is only for Windows NT."
#endif

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <assert.h>

#include "CCoroutine.h"
#include "CWinNTCoroutine.h"

///////////////////////////////////////////////////////////
class CCoroutineState
{
public:
    CCoroutineState() : fiber_(0) {}
    LPVOID fiber_;
};
static void WINAPI startCoroutine(PVOID lpParameter)
{
    CCoroutine *c = (CCoroutine *) lpParameter;
    c->go();
    assert(0);
}
///////////////////////////////////////////////////////////
CTargetPlatformCoroutine::CTargetPlatformCoroutine(unsigned 
                            stackSizeInBytes) : CCoroutine(INITCOROUTINE)
{
    state_ = new CCoroutineState();
    if (stackSizeInBytes == INITCOROUTINE)
        return;
    state_->fiber_ = CreateFiber(0, startCoroutine, this);
    assert(state_->fiber_);
}
CTargetPlatformCoroutine::~CTargetPlatformCoroutine()
{
    assert(state_->fiber_);
    DeleteFiber(state_->fiber_);
    state_->fiber_ = 0;
    delete state_;
}
void CTargetPlatformCoroutine::resume(CCoroutine *other)
{
    if (other == this) return;

    assert(other->state_->fiber_);
    SwitchToFiber(other->state_->fiber_);
}
/////////////////////////////////////////////////////////
// This can't be pure virtual because it is static
CCoroutine *CCoroutine::initialize()
{
    CCoroutine *thisCoroutine = new CTargetPlatformCoroutine();
    LPVOID thisFiber = ConvertThreadToFiber(thisCoroutine);
    assert(thisFiber != 0);
    thisCoroutine->state_->fiber_ = thisFiber;
    return thisCoroutine;
}

Back to Article

Listing Two

////////////////////////////////////////////
// CSolarisCoroutine.h
////////////////////////////////////////////

#ifndef _CSolarisCoroutine_h_#define _CSolarisCoroutine_h_#include 
          <assert.h>class CTargetPlatformCoroutine : public CCoroutine {
public:
    CTargetPlatformCoroutine(unsigned stackSizeInBytes = DEFSTACKSIZE);
    virtual ~CTargetPlatformCoroutine();
    virtual void go() {assert(0);}
    virtual void resume(CCoroutine *next);
};
#endif

////////////////////////////////////////////
// CSolarisCoroutine.cpp
////////////////////////////////////////////
#include "CCoroutine.h"
#include "CSolarisCoroutine.h"

#include <pthread.h>
#include <assert.h>

////////////////////////////////////////////////
class CCoroutineState
{
public:
  CCoroutineState(CCoroutine *parent)
  : parent_(parent), go_(false)
  {
      pthread_mutex_init(&go_mutex_, 0);
      pthread_cond_init(&go_cond_, 0);
  }
  CCoroutine *parent_;
  pthread_t thread_;
  int go_;
  pthread_mutex_t go_mutex_;
  pthread_cond_t go_cond_;

  inline void waitToGo() {
    pthread_mutex_lock(&go_mutex_);
    while (!go_)
      pthread_cond_wait(&go_cond_, &go_mutex_);
    go_ = false;
    pthread_mutex_unlock(&go_mutex_);
  }
  inline void signalToGo() {
    // Tell the other guy to go.
    pthread_mutex_lock(&go_mutex_);
    go_ = true;
    pthread_cond_signal(&go_cond_);
    pthread_mutex_unlock(&go_mutex_);
  }
};
static void *crstart(void *thunk) {
  CCoroutineState *s = (CCoroutineState *) thunk;
  s->waitToGo();
  s->parent_->go();
  assert(0);
  return 0;
}
/////////////////////////////////////////////////////////////
CTargetPlatformCoroutine::CTargetPlatformCoroutine(unsigned 
                 requestedStackSizeInBytes) : CCoroutine(INITCOROUTINE)
{
  state_ = new CCoroutineState(this); 
  if (requestedStackSizeInBytes == INITCOROUTINE)
    return;
    pthread_attr_t attr;
    pthread_attr_init(&attr);
#ifdef _POSIX_THREAD_ATTR_STACKSIZE
    size_t stackSize = 8192;
    if (requestedStackSizeInBytes != DEFSTACKSIZE)
      stackSize = requestedStackSizeInBytes;
#ifdef PTHREAD_STACK_MIN                    // Solaris is missing this.
    if (stackSize < PTHREAD_STACK_MIN)
      stackSize = PTHREAD_STACK_MIN;
#endif
    pthread_attr_setstacksize(&attr, stackSize);
#endif
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
    pthread_create(&state_->thread_, &attr, crstart, this->state_);
    pthread_attr_destroy(&attr);
}
CTargetPlatformCoroutine::~CTargetPlatformCoroutine()
{
  state_ = 0;
}
void CTargetPlatformCoroutine::resume(CCoroutine *other)
{
  if (other == this) return;

  // Tell the other guy to go.
  assert(other->state_);
  other->state_->signalToGo();

  // Wait until someone tells us to go.
  assert(state_);
  state_->waitToGo();
}
///////////////////////////////////////////////////////////
CCoroutine *CCoroutine::initialize()
{
  return new CTargetPlatformCoroutine();
}

Back to Article

Listing Three

// oddword.cpp : Defines the entry point for the console application. 
#include <iostream.h>
#include <string>
#include "CCoroutine.h"
#ifdef _WIN32
#include "CWinNTCoroutine.h"
#else
#include "CSolarisCoroutine.h"
#endif

CTargetPlatformCoroutine *rwrd;
CTargetPlatformCoroutine *rspc;

CTargetPlatformCoroutine *prtn;
std::string InputString;
int InputPointer = 0;
int k;
char Word1[20];

class ReadWord : public CTargetPlatformCoroutine
{
public:
    ReadWord() : CTargetPlatformCoroutine() {this->initialize();}
    virtual void go();
};
class ReadSpace : public CTargetPlatformCoroutine
{
public:
    ReadSpace() : CTargetPlatformCoroutine() {this->initialize();}
    virtual void go();
};
class PrintRoutine : public CTargetPlatformCoroutine
{
public:
    PrintRoutine() : CTargetPlatformCoroutine() {this->initialize();}
    virtual void go();
};
void ReadWord::go()
{
    char ch;
    while (true)
    {
        k = 0;
        memset(Word1, 0, 20);
        ch = InputString[InputPointer];
        while (ch != ' ' && ch != '.' && k < 20)
        {
            Word1[k] = ch;
            k++;
            InputPointer++;
            ch = InputString[InputPointer];
        }
        resume(prtn);

    }
}
void ReadSpace::go()
{
    while (true)
    {
         bool bSawSpace = false;
         if (InputPointer >= InputString.length())
             return;
         // assume that this thing ends with '.'
         while (InputString[InputPointer] == ' ')
         {
             InputPointer++;
             bSawSpace = true;

        }
         if (InputString[InputPointer] == '.')
         {
             cout << "." << endl;
             exit(0);
         }
         else
         {
             if (bSawSpace)
                 cout << " ";
             resume(rwrd);
         }
    }
}
void PrintRoutine::go()
{
    int j;
    while (true)
    {
        for (j = 0; j < k; j++)
            cout << Word1[j];
        resume(rspc);
        for (j = k - 1; j >= 0; j--)
            cout << Word1[j];
        resume(rspc);
    }
}
// Let the user enter a string on the command line. Store it in memory in 
// the variable InputString then read characters one at a time from 
// InputString to solve the odd word problem. Make sure to enclose your 
// command-line argument in double quotes
int main(int argc, char* argv[])
{
    if (argc != 2)
    {
        InputString = "whats      the     matter with Kansas.";
    }
    else
    {
        InputString = argv[1];
    }
    rwrd = new ReadWord();
    rspc = new ReadSpace();
    prtn = new PrintRoutine();

    rspc->go();
    return 0;
}

Back to Article