MCS atomic transferring cond var

// 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);

    }

};