8
\$\begingroup\$

I need a Read-Write lock that is fast and generally portable on Windows machines (including XP, otherwise I'd just use the SRWLock that was introduced with Vista). I've written this custom implementation, partly as an exercise, and partly to avoid including Boost just for the one class.

I'm an amateur, though, and concurrency objects like this are notoriously hard to test. I'm posting the code here so that other people can look it over, and also so that anyone who has a need for it can use it. I'm hoping if there are any problems with the implementation somebody will spot it.

For the record, this implementation has roughly comparable (but generally worse) performance to the native SRWLock on my Vista machine.

#include <windows.h>
class FastReadWriteLock
{
public:        

    FastReadWriteLock()
    {
        m_lockState = 0; // init state
        m_hReadSem = CreateSemaphore(0,0,0x10000,0); // create ananymous semaphores with maximum value much larger
        m_hWriteSem = CreateSemaphore(0,0,0x10000,0); // than any possible value of waiting count fields
    }

    ~FastReadWriteLock()
    {
        CloseHandle(m_hReadSem); // release semaphores
        CloseHandle(m_hWriteSem);
    }

    void WaitForReadLock()
    {
        while (true)
        {
            LockState lockState = m_lockState; // get local copy of lock state
            if (lockState.writeLock || lockState.writeWaiting || lockState.readLock == -1) // write lock is held/pending or read lock overflow
            {
                if (lockState.readWaiting == -1) Sleep(0); // wait overflow; force a context switch in lieu of proper waiting
                else
                {
                    LockState newState = lockState; newState.readWaiting++; // create new state with incremented wait
                    if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) // wait aquired successfully
                    {
                        WaitForSingleObject(m_hReadSem,INFINITE); // block until an unlock event occurs
                        while (true) // attempt to decrement wait count until successful
                        {
                            lockState = m_lockState; // update local copy of lock state
                            newState = lockState; newState.readWaiting--; // create new state with decremented wait
                            if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) break; // wait released successfully
                        }
                    }
                }
            }
            else
            {                
                LockState newState = lockState; newState.readLock++; // create new state with incremented read lock count
                if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) break; // lock aquired successfully
            }
        } // loop continues if state was modified concurrently or wait expired
    }

    bool TryReadLock()
    {
        LockState lockState = m_lockState; // get local copy of lock state
        if (lockState.writeLock || lockState.writeWaiting || lockState.readLock == -1) return false; // write lock is held/pending or read lock overflow
        LockState newState = lockState; newState.readLock++; // create new state with incremented read lock count
        return lockState == InterlockedCompareExchange(&m_lockState,newState,lockState); // attempt to aquire lock
    }

    void ReleaseReadLock()
    {
        LockState lockState = m_lockState; // get local copy of lock state
        while (lockState.readLock) // attempt to decrement read lock until successful
        {
            LockState newState = lockState; newState.readLock--; // create new state with decremented read lock count
            if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) break; // lock released successfully
            lockState = m_lockState; // failure, reset local state copy
        } 
        if (lockState.writeWaiting)
        {
            ReleaseSemaphore(m_hWriteSem,1,NULL); // release a single waiting writer
        }
        else if (lockState.readWaiting)
        {
            ReleaseSemaphore(m_hReadSem,lockState.readWaiting,NULL); // release all waiting readers
        }
    }

    void WaitForWriteLock()
    {
        while (true)
        {
            LockState lockState = m_lockState; // get local copy of lock state
            if (lockState.writeLock || lockState.readLock) // read or write lock is currently held
            {
                if (lockState.writeWaiting == -1) Sleep(0); // wait overflow; force a context switch in lieu of proper waiting
                else
                {
                    LockState newState = lockState; newState.writeWaiting++; // create new state with incremented wait
                    if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) // wait aquired successfully
                    {
                        WaitForSingleObject(m_hWriteSem,INFINITE); // block until an unlock event occurs
                        while (true) // attempt to decrement wait count until successful
                        {
                            lockState = m_lockState; // update local copy of lock state
                            newState = lockState; newState.writeWaiting--; // create new state with decremented wait
                            if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) break; // wait released successfully
                        }
                    }
                }
            }
            else
            {                
                LockState newState = lockState; newState.writeLock = 1; // create new state with write lock
                if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) break; // lock aquired successfully
            }
        } // loop continues if state was modified concurrently or wait expired
    }

    bool TryWriteLock()
    {
        LockState lockState = m_lockState; // get local copy of lock state
        if (lockState.writeLock || lockState.readLock) return false; // read or write lock is currently held
        LockState newState = lockState; newState.writeLock = 1; // create new state with write lock
        return lockState == InterlockedCompareExchange(&m_lockState,newState,lockState); // attempt to aquire lock
    }

    void ReleaseWriteLock()
    {
        LockState lockState = m_lockState; // get local copy of lock state
        while (lockState.writeLock) // attempt to zero write lock until successful
        {
            LockState newState = lockState; newState.writeLock = 0; // create new state with no write lock
            if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) break; // lock released successfully
            lockState = m_lockState; // failure, reset local state copy
        } 
        if (lockState.writeWaiting)
        {
            ReleaseSemaphore(m_hWriteSem,1,NULL); // release a single waiting writer
        }
        else if (lockState.readWaiting)
        {
            ReleaseSemaphore(m_hReadSem,lockState.readWaiting,NULL); // release all waiting readers
        }
    }

protected:

    struct LockState
    {
        // state encoded in 32 bit word
        unsigned long   readWaiting     :11,
                        readLock        :11,                    
                        writeWaiting    :9,
                        writeLock       :1;
        // methods
        inline LockState(LONG value = 0) { *(LONG*)this = value; }
        inline operator LONG() const { return *reinterpret_cast<const unsigned long*>(this); }
        inline LockState& operator =(LONG value) { *(LONG*)this = value; return *this; }
        inline LockState& operator =(const LockState& rhs) { *(LONG*)this = (LONG)rhs; return *this; }
        inline bool operator ==(LONG value) const { return (LONG)*this == value; }
    };

    volatile LONG   m_lockState;
    HANDLE          m_hReadSem;
    HANDLE          m_hWriteSem;
};
\$\endgroup\$
  • \$\begingroup\$ Why not use TBBs or boosts existing and well tested solutions? \$\endgroup\$ – ronag Dec 2 '11 at 23:47
  • \$\begingroup\$ I'm not fond of boost. And I didn't know TBB existed until you mentioned it. But as I said, this was also an exercise to get me familiar with Windows synchronization primitives. \$\endgroup\$ – JRoush Dec 3 '11 at 0:19
  • \$\begingroup\$ nice example on Arrowhead Code Pattern (codinghorror.com/blog/2006/01/flattening-arrow-code.html) \$\endgroup\$ – Abyx Dec 3 '11 at 20:56
  • 2
    \$\begingroup\$ Really? I appreciate advice on formatting, Abyx, but if that's really the extent of your insight here then I'm not sure why you bothered. \$\endgroup\$ – JRoush Dec 3 '11 at 21:31
2
\$\begingroup\$

This looks like a writer biased reader/writer lock. That may be fine, but beware of reader starvation if there is a high rater of writers.

Note, also, that the Vista+ reader/writer lock is neither reader nor writer biased. I've not been able to find explicit documentation about how it deals with this, but in my experience, it tends to operate in a FIFO mode.

~FastReadWriteLock()

What about the copy constructor, assignment operator, move constructor, and move assignment operator? I'd delete them unless they're needed.

m_hReadSem = CreateSemaphore(0,0,0x10000,0);

CreateSemaphore can return an error. The code probably should check for errors and do some something sensible. An RAII wrapper (even if a private class) around a Win32 semaphore is the route I'd use initially.

This comment applies to the other Win32 API calls being made. If used correctly, they don't often fail. But under high load or high concurrency, failure it likely to be disastrous.

if (lockState.writeLock || lockState.writeWaiting || lockState.readLock == -1)

Since .writeLock and .writeWaiting are not booleans but counters, consider explicit > 0 tests.

ReleaseReadLock

If two calls to ReleaseReadLock both run the if (lockState.writeWaiting) ReleaseSemaphore(m_hWriteSem,1,NULL); branch, we'll wakeup two writers. Only one will be able to acquire. The other will experience a spurious wakeup. This is probably okay, but I feel like I should still point it out. The reader path can also exhibit this.

while (true) // attempt to decrement wait count until successful
{
    lockState = m_lockState; // update local copy of lock state
    newState = lockState; newState.writeWaiting--; // create new state with decremented wait
    if (lockState == InterlockedCompareExchange(&m_lockState,newState,lockState)) break; // wait released successfully
}

There are a number of blocks of code that are very similar to this. I wonder if there's a nice way to refactor this. I'm not coming up with a really nice, clean refactoring right now. Since the mutation being made in each block is different, functors might be an option...

protected:

Is private okay? Do we expect derived implementations? The destructor implies no.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.