// MCS Cond Var with atomic ownership transfer
// by Charles Bloom (www.cbloom.com)
// copyright 2011
// public domain
struct mcs_node
{
std::atomic<mcs_node *> m_next;
std::atomic<HANDLE> m_event;
mcs_node()
{
m_next($).store(0);
m_event($).store(0);
}
};
struct mcs_cond_var
{
public:
// m_lock points to the tail of the waiter list all the time
std::atomic<mcs_node *> m_tail;
//-------------
std::mutex m_waiter_mutex;
VAR_T(mcs_node *) m_waiters;
//-------------
mcs_cond_var() : m_waiters(NULL)
{
m_tail($).store( NULL );
}
~mcs_cond_var()
{
RL_ASSERT( m_waiters($) == NULL );
mcs_node * n = m_tail($).exchange(0);
if ( n )
delete n;
}
// note : handle should come from TLS - no need to ever Create/Close
static HANDLE alloc_event() { return CreateEvent(NULL,0,0,NULL); }
static void free_event(HANDLE h) { if ( h ) CloseHandle(h); }
struct guard
{
mcs_node m_node; // provide node on the stack
guard() { }
~guard() { }
};
void lock(guard & g)
{
mcs_node * me = &(g.m_node);
ASSERT( me->m_next($).load(std::mo_relaxed) == NULL );
// publish my node as the new tail :
VAR_T(mcs_node *) pred = m_tail($).exchange(me, std::mo_acq_rel);
if ( pred($) != NULL )
{
// pred can't see me until I store to m_next
// can choose if I want to spin or wait :
HANDLE h = alloc_event();
me->m_event($).store( h , std::mo_relaxed );
// publish me to previous lock-holder :
pred($)->m_next($).store(me, std::mo_release );
// now this is the spin -
// wait on predecessor setting my flag -
WaitForSingleObject(h,INFINITE);
free_event(h);
RL_ASSERT( me->m_event($).load(std::mo_relaxed) == h );
me->m_event($).store( 0 , std::mo_relaxed );
}
}
// unlock_internal does all the work up to but not including waking up the next owner
HANDLE unlock_internal(guard & g, mcs_node * new_tail)
{
mcs_node * me = &(g.m_node);
VAR_T(mcs_node *) next = me->m_next($).load(std::mo_acquire);
if ( next($) == NULL )
{
mcs_node * tail_was_me = me;
if ( m_tail($).compare_exchange_strong( tail_was_me,new_tail,std::mo_acq_rel) )
{
// got null in tail, mutex is unlocked
return 0;
}
// if tail was changed, then I will get something stored in my next
// wait for it ...
rl::linear_backoff bo;
for(;;)
{
next($) = me->m_next($).load(std::mo_acquire);
if ( next($) != NULL )
break;
bo.yield($);
}
}
// let next guy in :
HANDLE h = next($)->m_event($).load( std::mo_relaxed );
RL_ASSERT( h != 0 );
return h;
}
void unlock(guard & g)
{
HANDLE h = unlock_internal(g,NULL);
if ( h )
SetEvent(h);
// prep for reuse :
g.m_node.m_next($).store(NULL,std::mo_relaxed);
}
void signal_unlock(guard & g)
{
mcs_node * me = &(g.m_node);
// if there is no waiter, just unlock
// if there is a waiter, transfer the mutex directly to him
// he will then do the unlock that I would have done
// first, get the waiter while mutex is held
VAR_T(mcs_node *) waiter = NULL;
{
m_waiter_mutex.lock($);
// pop one off front :
waiter($) = m_waiters($);
if ( waiter($) != NULL )
m_waiters($) = waiter($)->m_next($).load(std::mo_relaxed);
m_waiter_mutex.unlock($);
}
if ( ! waiter($) )
{
unlock(g);
return;
}
// waiter might get put in tail, so make sure it's a valid lock node now :
waiter($)->m_next($).store( NULL , std::mo_relaxed );
// there's a race here just like in unlock
// someone trying to grab the mutex may be trying to set me->m_next
// I need to wait for him to be done :
HANDLE next_locker = unlock_internal(g,waiter($));
// now me->next should be set (if it will be set)
HANDLE waiter_h = waiter($)->m_event($).load(std::mo_relaxed);
RL_ASSERT( waiter_h != 0 );
// if next_locker was 0, waiter got set to the tail, so don't touch waiter->next
VAR_T(mcs_node *) next = me->m_next($).load(std::mo_relaxed);
if ( next_locker != 0 )
{
RL_ASSERT( next($) != NULL );
waiter($)->m_next($).store( next($) , std::mo_release );
}
else
{
// tail moved to waiter; he now holds the lock
RL_ASSERT( next($) == NULL );
//waiter->m_next($).store( NULL , std::mo_relaxed );
}
// transfer mutex for him :
SetEvent(waiter_h);
// me is not visible to anyone ; prep for reuse :
me->m_next($).store(NULL,std::mo_relaxed);
}
void broadcast_unlock(guard & g)
{
mcs_node * me = &(g.m_node);
// first, get the waiter while mutex is held
mcs_node * waiters = NULL;
{
m_waiter_mutex.lock($);
// exchange out the list
waiters = m_waiters($);
m_waiters($) = NULL;
m_waiter_mutex.unlock($);
}
if ( ! waiters )
{
unlock(g);
return;
}
for(;;)
{
mcs_node * nextWaiter = waiters->m_next($).load(std::mo_relaxed);
waiters->m_next($).store(NULL,std::mo_relaxed);
VAR_T(mcs_node *) waiter = waiters;
// waiter might get put in tail, so make sure it's a valid lock node now :
waiter($)->m_next($).store( NULL , std::mo_relaxed );
// there's a race here just like in unlock
// someone trying to grab the mutex may be trying to set me->m_next
// I need to wait for him to be done :
HANDLE next_locker = unlock_internal(g,waiter($));
// now me->next should be set (if it will be set)
HANDLE waiter_h = waiter($)->m_event($).load(std::mo_relaxed);
RL_ASSERT( waiter_h != 0 );
// if next_locker was 0, waiter got set to the tail, so don't touch waiter->next
mcs_node * next = me->m_next($).load(std::mo_relaxed);
if ( next_locker != 0 )
{
RL_ASSERT( next != NULL );
waiter($)->m_next($).store( next , std::mo_relaxed );
}
else
{
RL_ASSERT( next == NULL );
}
// transfer mutex for him :
SetEvent(waiter_h);
// mutex is now locked by someone else
me->m_next($).store(NULL,std::mo_relaxed);
if ( nextWaiter == NULL )
return; // done signaling
// relock mutex :
lock(g);
waiters = nextWaiter;
}
}
void unlock_wait_lock(guard & g)
{
HANDLE unlock_h;
HANDLE wait_handle = alloc_event();
{
m_waiter_mutex.lock($);
// unlock must be inside waiter mutex ?
// yes, if not then signal can get missed between unlock and adding waiter
// and we go into a deadlock wait
// you can move this out if signal incs an atomic count
// and you check the count before & after unlock and if they're not the same abort the wait
unlock_h = unlock_internal(g,NULL);
// mutex may now be unlocked if tail was set to null
// after unlock, node is now mine to reuse :
mcs_node * node = &(g.m_node);
node->m_next($).store( 0 , std::mo_relaxed );
node->m_event($).store( wait_handle , std::mo_relaxed );
// put on end of list :
if ( m_waiters($) == NULL )
{
m_waiters($) = node;
}
else
{
// dumb way of doing FIFO but whatever for this sketch
mcs_node * parent = m_waiters($);
while ( parent->m_next($).load(std::mo_relaxed) != NULL )
parent = parent->m_next($).load(std::mo_relaxed);
parent->m_next($).store(node,std::mo_relaxed);
}
m_waiter_mutex.unlock($);
}
if ( unlock_h )
{
// wake new lock-holder and also wait for the signal :
SignalObjectAndWait(unlock_h,wait_handle,INFINITE,FALSE);
}
else
{
WaitForSingleObject(wait_handle,INFINITE);
}
// I am woken and now own the lock
// my node has been filled with the guy I should unlock
free_event(wait_handle);
RL_ASSERT( g.m_node.m_event($).load(std::mo_relaxed) == wait_handle );
g.m_node.m_event($).store(0,std::mo_relaxed);
}
};