May 2011
Volume 26 Number 05
Windows API Wait Functions - DynWaitList: ID-Based Windows Event Multiplexing
By Alex Gimenez | May 2011
Microsoft Windows provides multiplexed listening to several events via the WaitForMultipleObjects method and its variants. These functions are powerful, but inconvenient to use when the event list is dynamic.
The difficulty is that event signals are identified by indexes into an array of object handles. Such indexes will shift when events are added to or removed from the middle of the array.
This type of problem is commonly addressed by having a container that stores the handles, wrapping the array and performing insertion, removal and lookups on behalf of client applications.
This article discusses the design and implementation of such a container class. The container stores the event handles used with the WaitForMultipleObjects method. Users of the container class refer to individual handles by a numeric ID that won’t change for the lifetime of the container, even as events are added or removed.
Exploring the Issue
The interface to WaitForMultipleObjects/MsgWaitForMultipleObjects is best suited for the simpler cases where:
- You know beforehand how many handles you’re going to wait on.
- The number of handles you’re waiting on doesn’t change over time.
When a handle is signaled, you get the index of the handle as a return value. This index—the position within the event array passed as input—isn’t directly meaningful. What you really want out of these functions is the handle that was signaled or some non-ephemeral information that leads you to that handle.
Figure 1 shows an example that illustrates the issue. Its code—part of a theoretical media-streaming application—is waiting for a signal from an audio device or from the network (this and other code samples can be found in the code download for this article).
Figure 1 Media-Streaming App Waiting for a Signal
#define MY_AUDIO_EVENT (WAIT_OBJECT_0)
#define MY_SOCKET_EVENT (WAIT_OBJECT_0 + 1)
HANDLE handles[2];
handles[0] = audioInHandle;
handles[1] = socketHandle;
...
switch( WaitForMultipleObjects(handles) )
{
case MY_AUDIO_EVENT:
// Handle audio event
break;
case MY_SOCKET_EVENT:
// Handle socket event
// What happens if we need to stop audio here?
break;
}
Getting a result of WAIT_OBJECT_0 (index 0) means the audio device was signaled. Getting an index of 1 means the network was signaled. Now, what happens if you need to close audioInHandle in response to an event triggered from socketHandle? You would then have to get rid of index 0 in the handles array, which would shift the indexes greater than 0—meaning that the MY_SOCKET_EVENT value needs to be dynamic, not a constant.
There are ways to work around this situation, of course (for example, keep the optional handles at the end of the array, or shift the start of the array), but they get messy quickly when you add a few more events and the handling of error paths (indexes off of WAIT_ABANDONED_0).
At first glance, the issue is that you can’t use constants to identify the event handles. Looking closer, we see that the root problem with this interface is that it uses array indexes to identify the event handles. Indexes then play an inconvenient double-duty here, representing both the handle’s position in memory and the fact that the event is signaled.
It would be nice if the signaled events were identifiable independently from the indexes in the array. That’s what the DynWaitList class does for us.
Using DynWaitList
The DynWaitList class is a container list for the array of handles to be passed for the WaitForMultipleObjects method. The internal collection of handles has a static maximum size. The class is implemented as a template, where the maximum size of the collection is the only template parameter.
The container interface has the methods you’d expect: Add to insert an event and specify its ID, Remove to remove an event and a few variants of Wait. Figure 2 shows how DynWaitList is used to solve the issue presented earlier.
Figure 2 Using DynWaitList
WORD idAudioEvent, idSocketEvent;
DynWaitList<10> handles(100); // Max 10 events, first ID is 100
handles.Add( socketHandle, &idSocketEvent );
handles.Add( audioInHandle, &idAudioEvent );
...
switch( handles.Wait(2000) )
{
case (HANDLE_SIGNALED| idAudioEvent ):
// Handle audio event
break;
case (HANDLE_SIGNALED| idSocketEvent):
// Handle socket event
if( decided_to_drop_audio )
{
// Array will shift within; the same ID
// can be reused later with a different
// handle if, say, we reopen audio
handles.Remove(idAudioEvent);
// Any value outside the
// 100...109 range is fine
idAudioEvent = 0;
}
break;
case (HANDLE_ABANDONED| idSocketEvent):
case (HANDLE_ABANDONED| idAudioEvent):
// Critical error paths
break;
case WAIT_TIMEOUT:
break;
}
Common Uses of DynWaitList
The example presented here shows a small number of well-known event IDs. There are, however, cases where the IDs are many, and aren’t known beforehand. These are some common cases:
- A TCP server, which would hold an event ID for each currently connected client socket. This is the case that makes the most of the dynamic event list, as client sockets do come and go with each connection.
- An audio mixing application or IP phone application, which would have a handle to wait for the frame-ready/timer signal of each audio device on the system.
The examples so far show a common theme: The dynamic list of handles is representative of the changing external environment around the application.
Design and Performance Considerations
Implementing a container is a balancing act of picking between conflicting goals of performance, simplicity and storage space. These have to be evaluated under the light of the most frequent container uses—the ones shown earlier. Then, it helps to enumerate the operations to perform on the container and their rate of occurrence:
- Adding a handle: quite frequent
- Removing a handle: about the same frequency as adding a handle
- Changing a handle: not applicable (you can’t change the handle of an existing object in Windows)
- Translating the container into the flat array that Windows needs: quite frequent
- Retrieving the value of a handle that was just signaled: quite frequent
With these operations in mind, I decided to have internal storage be an array of event handles (the one required by Windows), plus a parallel array of IDs, which are 16-bit values. This parallel-array arrangement allows for efficient translation between indexes and event IDs. Specifically:
- The array that Windows needs is always available.
- Given the index returned by Windows, looking up its ID is an order-1 operation.
One other important consideration is thread safety. Given the purpose of this container, it’s fair to require the operations to be serialized, so I chose not to protect the internal arrays.
Figure 3 shows the declaration of the class showing the main interface and container internals.
Figure 3 Class Declaration Showing Main Interface and Container Internals
class DynWaitlistImpl
{
protected:
DynWaitlistImpl( WORD nMaxHandles, HANDLE *pHandles,
WORD *pIds, WORD wFirstId );
// Adds a handle to the list; returns TRUE if successful
BOOL Add( HANDLE hNewHandle, WORD *pwNewId );
// Removes a handle from the list; returns TRUE if successful
BOOL Remove( WORD wId );
DWORD Wait(DWORD dwTimeoutMs, BOOL bWaitAll = FALSE);
// ... Some snipped code shown later ...
private:
HANDLE *m_pHandles;
WORD *m_pIds;
WORD m_nHandles;
WORD m_nMaxHandles;
};
template <int _nMaxHandles> class DynWaitlist: public DynWaitlistImpl
{
public:
DynWaitlist(WORD wFirstId):
DynWaitlistImpl( _nMaxHandles, handles, ids, wFirstId ) { }
virtual ~DynWaitlist() { }
private:
HANDLE handles[ _nMaxHandles ];
WORD ids[ _nMaxHandles ];
};
Notice how the class is broken in two, with a base class holding an array pointer, and a template-derived class holding the actual storage. This provides flexibility for dynamic array allocation—if needed—by deriving a different template class. This implementation uses solely static storage.
Adding a Handle
Adding a handle to the array is straightforward, except for the act of finding a free ID to represent a newly created event. Per the chosen design, there’s an array of IDs in the container. This array is pre-allocated to hold up to the maximum number of IDs the container can hold. Thus, the array can conveniently hold two groups of IDs:
- The first Nelements are the IDs in use, where N is how many handles are actually allocated.
- The remaining elements are a pool of free IDs.
This requires the ID array to be filled with all possible ID values upon construction. Given that, it’s trivial to find a free ID using the ID just past the last one used. No search is required. The code for the class constructor and the Add method is shown in Figure 4. These two methods cooperate to build and use the pool of free IDs.
Figure 4 Class Constructor and Add Method
DynWaitlistImpl::DynWaitlistImpl(
WORD nMaxHandles, // Number of handles
HANDLE *pHandles, // Pointer to array of handle slots
WORD *pIds, // Pointer to array of IDs
WORD wFirstID) // Value of first ID to use
// Class Constructor. Initializes object state
: m_nMaxHandles(nMaxHandles)
, m_pHandles(pHandles)
, m_pIds(pIds)
, m_nHandles(0)
{
// Fill the pool of available IDs
WORD wId = wFirstID;
for( WORD i = 0; i < nMaxHandles; ++i )
{
m_pIds[i] = wId;
wId++;
}
}
BOOL DynWaitlistImpl::Add(
HANDLE hNewHandle, // Handle to be added
WORD *pwNewId ) // OUT parameter - value of new ID picked
// Adds one element to the array of handles
{
if( m_nHandles >= m_nMaxHandles )
{
// No more room, no can do
return FALSE;
}
m_pHandles[ m_nHandles ] = hNewHandle;
// Pick the first available ID
(*pwNewId) = m_pIds[ m_nHandles ];
++m_nHandles;
return TRUE;
}
Removing a Handle
To remove a handle from the container given its ID, we must find the handle’s index. The translation from index to ID is optimized to order-1 by this implementation, but this comes at the expense of the reverse translation’s performance. Given an ID, it takes a linear search (order-N) to find its index in the array. I decided to take that hit because, in the case of a server, users aren’t as mindful of response time upon disconnecting. After finding the index to remove, the removal operation is quick and simple—just swap the handle found with the last “in-use” handle (see Figure 5).
Figure 5 The Removal Operation
BOOL DynWaitlistImpl::Remove(
WORD wId ) // ID of handle being removed
// Removes one element from the array of handles
{
WORD i;
BOOL bFoundIt = FALSE;
for( i = 0; i < m_nHandles; ++i )
{
// If we found the one we want to remove
if( m_pIds[i] == wId )
{
// Found it!
bFoundIt = TRUE;
break;
}
}
// Found the ID we were looking for?
if( bFoundIt )
{
WORD wMaxIdx = (m_nHandles - 1);
if( i < wMaxIdx ) // if it isn't the last item being removed
{
// Take what used to be the last item and move it down,
// so it takes the place of the item that was deleted
m_pIds [i] = m_pIds [ wMaxIdx ];
m_pHandles[i] = m_pHandles[ wMaxIdx ];
// Save the ID being removed, so it can be reused in a future Add
m_pIds [ wMaxIdx ] = wId;
}
--m_nHandles;
m_pHandles[m_nHandles] = 0;
return TRUE;
}
else
{
return FALSE;
}
}
Detecting Signals
Detecting signals is the main work performed by DynWaitList. Calling WaitForMultipleObjects is trivial because all the data is kept pre-archived for the call. Translating the signal detected into an ID that the upper layer can reference is also trivial because of the parallel array of IDs. That code is the meat of the Waitmethod, shown in Figure 6. There are a few variations of Wait, all of which use the internal TranslateWaitResult method to perform the index-to-ID translation.
Figure 6 Detecting Signals
// Snippet from the header file – Wait is a quick, inline method
DWORD Wait(DWORD dwTimeoutMs, BOOL bWaitAll = FALSE)
{
return TranslateWaitResult(
WaitForMultipleObjects( m_nHandles,
m_pHandles,
bWaitAll,
dwTimeoutMs )
);
}
// Snippet from the CPP file – method called by all flavors of Wait
DWORD DynWaitlistImpl::TranslateWaitResult(
DWORD dwWaitResult ) // Value returned by WaitForMultipleObjectsXXX
// translates the index-based value returned by Windows into
// an ID-based value for comparison
{
if( (dwWaitResult >= WAIT_OBJECT_0) &&
(dwWaitResult < (DWORD)(WAIT_OBJECT_0 + m_nHandles) ) )
{
return HANDLE_SIGNALED | m_pIds[dwWaitResult - WAIT_OBJECT_0];
}
if( (dwWaitResult >= WAIT_ABANDONED_0) &&
(dwWaitResult < (DWORD)(WAIT_ABANDONED_0 + m_nHandles) ) )
{
return HANDLE_ABANDONED | m_pIds[dwWaitResult - WAIT_ABANDONED_0];
}
return dwWaitResult; // No translation needed for other values
}
Multi-Core Considerations
We’re marching toward a “manycore” computing world, where we extract efficiency from computers by performing work in multiple threads. In that world, is event multiplexing even important? Could it be that most applications will end up having one event per thread, thus neutralizing the benefits of DynWaitList?
I bet not. I believe event multiplexing is important even in computers with multiple cores, at least because of these two reasons:
- Some operations simply don’t benefit from parallelism, because they touch hardware devices that must be accessed serially. Low-level networking is one such example.
- One key benefit of event multiplexing—especially in utility libraries—is not to push a particular threading model upon an application. The top-level application should dictate the threading model. In this manner, the application should be free to choose the distribution of events into its threads, making the encapsulation of event wait lists even more important.
Simple Code, Fewer Bugs
Summing up, associating non-ephemeral IDs to each event passed to Windows WaitForMultipleObjects functions can lead to code simplification and reduce the likelihood of bugs, as it removes the burden placed upon the application to translate meaningless event indexes into useful object handles or pointers. The DynWaitList class efficiently encapsulates this association process into a wrapper around these Windows API wait functions. All operations involved are of order-1, except for construction and handle removal, which are of order-N. Further optimization can be achieved by sorting the array, which would add a slight penalty to handle addition while making handle removal much faster.
Alex Gimenez currently works as a developer near Seattle, writing real-time audio/video/networking software with the team responsible for delivering Microsoft Lync. His prior experience spans just about two decades dealing with point-of-sale, embedded, device-driver and telecommunications software. In his spare time, he enjoys biking, drumming and studying Japanese. He can be reached at alexgim@microsoft.com.
Thanks to the following technical experts for reviewing this article: Bart Holmberg, Warren Lam and Jiannan Zheng