Mutex for many-readers, single writer

read_write_mutex.hpp

// Created by Emil Ernerfeldt on 2013-01-24.
// Cleaned up 2016-01-28.
#pragma once

#include <atomic>
#include <condition_variable>
#include <mutex>
#include <thread>

namespace util {

/* TODO: make two classes - one spin-waiting (for quick read ops)
 and one with a sleeping writer lock for waiting out slow reads (e.g. file system access).
*/
#define SLOW_READER 0

/*
 Mutex optimized for locking things that are often read, seldom written.
 * Many can read at the same time.
 * Only one can write at the same time.
 * No-one can read while someone is writing.
 In the case of no writes, each read lock/unlock consists of:
 * Checking an atomic bool (quick - doesn't change)
 * Incrementing and decrementing an atomic int (slight bottleneck - cache syncing)
 With SLOW_READER = 0 the WriteLock will spin-wait for zero readers.
 This is the natural choice for quick reader locks.
 With SLOW_READER = 1 there are no spin-locks in WriteLock.
 This is useful if the read operation can take a long time, e.g. file or network access.
 */
class ReadWriteMutex
{
public:
	ReadWriteMutex() { }

private:
	ReadWriteMutex(ReadWriteMutex&) = delete;
	ReadWriteMutex(ReadWriteMutex&&) = delete;
	ReadWriteMutex& operator=(ReadWriteMutex&) = delete;
	ReadWriteMutex& operator=(ReadWriteMutex&&) = delete;

	friend class ReadLock;
	friend class WriteLock;

	std::atomic<int>  _num_readers {0};
	std::atomic<bool> _has_writer  {false}; // Is there a writer working (or trying to) ?
	std::mutex        _write_mutex;

#if SLOW_READER
	std::condition_variable _reader_done_cond;  // Signals a waiting writer that a read has finishes
	std::mutex              _reader_done_mutex; // TODO: this mutex isn't really needed, but can't use a condition_variable without it
#endif
};


class ReadLock
{
public:
	explicit ReadLock(ReadWriteMutex& m_) : _rw_mutex(m_)
	{
		lock();
	}

	// Won't lock right away
	ReadLock(ReadWriteMutex& m_, std::defer_lock_t) : _rw_mutex(m_)
	{
	}

	~ReadLock() { unlock(); }

	void lock()
	{
		if (_locked) {
			return;
		}

		while (_rw_mutex._has_writer) {
			// First check here to stop readers while write is in progress.
			// This is to ensure _rw_mutex._num_readers can go to zero (needed for write to start).
			std::lock_guard<std::mutex> l(_rw_mutex._write_mutex); // wait for the writer to be done
		}

		// If a writer starts here, it may think there are no readers, which is why we re-check _rw_mutex._has_writer again.

		++_rw_mutex._num_readers; // Tell any writers that there is now someone reading

		// Check so no write began before we incremented _rw_mutex._num_readers
		while (_rw_mutex._has_writer) {
			// A write is in progress or is waiting to start!
			--_rw_mutex._num_readers; // We changed our mind

#if SLOW_READER
			{
				std::unique_lock<std::mutex> l(_rw_mutex._reader_done_mutex);
				_rw_mutex._reader_done_cond.notify_one(); // Tell the writer we did (he may be waiting for _rw_mutex._num_readers to go to zero)
			}
#endif

			std::lock_guard<std::mutex> l(_rw_mutex._write_mutex); // wait for the writer to be done

			++_rw_mutex._num_readers; // Let's try again
		}

		_locked = true;
	}

	void unlock()
	{
		if (_locked)
		{
			--_rw_mutex._num_readers;

#if SLOW_READER
			if (_rw_mutex._has_writer) {
				// A writer is waiting for all readers to finish. Tell him one more has:
				std::unique_lock<std::mutex> l(_rw_mutex._reader_done_mutex);
				_rw_mutex._reader_done_cond.notify_one();
			}
#endif

			_locked = false;
		}
	}

private:
	ReadLock(ReadLock&) = delete;
	ReadLock(ReadLock&&) = delete;
	ReadLock& operator=(ReadLock&) = delete;
	ReadLock& operator=(ReadLock&&) = delete;

	ReadWriteMutex& _rw_mutex;
	bool            _locked = false;
};


class WriteLock {
public:
	explicit WriteLock(ReadWriteMutex& m_) : _rw_mutex(m_)
	{
		lock();
	}

	// Won't lock right away
	WriteLock(ReadWriteMutex& m_, std::defer_lock_t) : _rw_mutex(m_)
	{
	}

	~WriteLock() { unlock(); }

	void lock()
	{
		if (_locked) {
			return;
		}

		_rw_mutex._write_mutex.lock(); // Ensure we are the only one writing
		_rw_mutex._has_writer = true; // Steer new readers into a lock (provided by the above mutex)

		// Wait for all readers to finish.
#if SLOW_READER
		if (_rw_mutex._num_readers!=0) {
			std::unique_lock<std::mutex> l(_rw_mutex._reader_done_mutex); // TODO: this mutex isn't really needed, but can't use a condition_variable without it
			_rw_mutex._reader_done_cond.wait(l, [=]{ return _rw_mutex._num_readers==0; });
		}
#else
		// Busy spin-waiting
		while (_rw_mutex._num_readers != 0) {
			std::this_thread::yield(); // Give the reader-threads a chance to finish.
		}
#endif

		// All readers have finished - time to write!
		_locked = true;
	}

	// Return false if there is a write in progress.
	// Still waits for any reads to finish.
	//bool try_lock() { // TODO

	void unlock()
	{
		if (_locked) {
			_rw_mutex._has_writer = false;
			_rw_mutex._write_mutex.unlock();
			_locked = false;
		}
	}

private:
	WriteLock(WriteLock&) = delete;
	WriteLock(WriteLock&&) = delete;
	WriteLock& operator=(WriteLock&) = delete;
	WriteLock& operator=(WriteLock&&) = delete;

	ReadWriteMutex& _rw_mutex;
	bool            _locked = false;
};

}