Introduce read-write-update locks and guards to prevent deadlocks

This converts t_rwmutex and t_rwmutex_guard into a read-write-update[*]
lock and guard, in an attempt to circumvent the various deadlocks that
were introduced with the addition of lines_mtx in 38bb6b7.

[*] For more details, see https://stackoverflow.com/a/18785300 and
http://lkml.iu.edu/hypermail/linux/kernel/0004.3/0117.html.

Note that this is not a real fix; this would require analyzing and
refactoring phone.cpp, which is well beyond my abilities.  This is at
best a workaround that appears to conveniently dodge all the deadlocks
I've encountered so far.

(It would have been more proper to introduce a separate class for this
purpose, but this would have required modifying over 80 lines just to
change one type for another.  As phone_users_mtx is the only other
instance of this class, the impact of subverting t_rwmutex directly is
minimal.)

2 files changed, 198 insertions, 13 deletions

diff --git a/src/threads/mutex.cpp b/src/threads/mutex.cpp
index 7eaa329..4c8c078 100644
--- a/src/threads/mutex.cpp
+++ b/src/threads/mutex.cpp
@@ -94,7 +94,13 @@ t_mutex_guard::~t_mutex_guard() {
 // t_rwmutex
 ///////////////////////////
 
-t_rwmutex::t_rwmutex()
+// Equivalent of an invalid thread ID, to be used when initializing t_rwmutex
+// or when releasing upgrade ownership; the use of pthread_self() is only to
+// provide a dummy value of the appropriate type.
+static const optional_pthread_t invalid_thread_id = { false, pthread_self() };
+
+t_rwmutex::t_rwmutex() :
+	_up_mutex_thread( invalid_thread_id )
 {
 	int ret = pthread_rwlock_init(&_lock, nullptr);
 	if (ret != 0) throw string(
@@ -106,56 +112,167 @@ t_rwmutex::~t_rwmutex()
 	pthread_rwlock_destroy(&_lock);
 }
 
-void t_rwmutex::lockRead()
+void t_rwmutex::getUpgradeOwnership()
+{
+	_up_mutex.lock();
+	_up_mutex_thread = { true, pthread_self() };
+}
+
+void t_rwmutex::releaseUpgradeOwnership()
+{
+	_up_mutex_thread = invalid_thread_id;
+	_up_mutex.unlock();
+}
+
+bool t_rwmutex::isUpgradeOwnershipOurs() const
+{
+	// Note that we don't need a mutex over _up_mutex_thread, being atomic
+	// is enough for our purposes.  (We don't care about *who* owns
+	// _up_mutex, only about whether or not *we* own it, a fact which only
+	// our own thread can modify.)
+	optional_pthread_t lockOwner = _up_mutex_thread;
+	return lockOwner.has_value && pthread_equal(lockOwner.value, pthread_self());
+}
+
+void t_rwmutex::_lockRead()
 {
 	int err = pthread_rwlock_rdlock(&_lock);
 	if (err != 0)
 		throw std::logic_error("Mutex lock failed");
 }
 
-void t_rwmutex::lockWrite()
+void t_rwmutex::_lockWrite()
 {
 	int err = pthread_rwlock_wrlock(&_lock);
 	if (err != 0)
 		throw std::logic_error("Mutex lock failed");
 }
 
-void t_rwmutex::unlock()
+void t_rwmutex::_unlock()
 {
 	pthread_rwlock_unlock(&_lock);
 }
 
+void t_rwmutex::lockRead()
+{
+	if (isUpgradeOwnershipOurs()) {
+		throw std::logic_error("Acquiring read lock while holding update/write lock is not supported");
+	}
+
+	_lockRead();
+}
+
+void t_rwmutex::lockUpdate()
+{
+	if (isUpgradeOwnershipOurs()) {
+		throw std::logic_error("Acquiring update lock while holding update/write lock is not supported");
+	}
+
+	getUpgradeOwnership();
+	_lockRead();
+}
+
+void t_rwmutex::lockWrite()
+{
+	if (isUpgradeOwnershipOurs()) {
+		throw std::logic_error("Acquiring write lock while holding update/write lock is not supported");
+	}
+
+	getUpgradeOwnership();
+	_lockWrite();
+}
+
+void t_rwmutex::unlock()
+{
+	_unlock();
+
+	if (isUpgradeOwnershipOurs()) {
+		releaseUpgradeOwnership();
+	}
+}
+
+void t_rwmutex::upgradeLock()
+{
+	if (!isUpgradeOwnershipOurs()) {
+		throw std::logic_error("Attempting to upgrade a lock without upgrade ownership");
+	}
+
+	_unlock();
+	_lockWrite();
+}
+
+void t_rwmutex::downgradeLock()
+{
+	if (!isUpgradeOwnershipOurs()) {
+		throw std::logic_error("Attempting to downgrade a lock without upgrade ownership");
+	}
+
+	_unlock();
+	_lockRead();
+}
+
 ///////////////////////////
 // t_rwmutex_guard
 ///////////////////////////
 
 t_rwmutex_guard::t_rwmutex_guard(t_rwmutex& mutex) :
-	_mutex(mutex)
+	_mutex(mutex),
+	_previously_owned_upgrade(_mutex.isUpgradeOwnershipOurs())
 {
 }
 
 t_rwmutex_reader::t_rwmutex_reader(t_rwmutex& mutex) :
 	t_rwmutex_guard(mutex)
 {
-	// std::cout << "mtx rd lock " << (void*)&_mutex << std::endl;
-	_mutex.lockRead();
+	// No-op if we are nested within a writer/future_writer guard
+	if (!_previously_owned_upgrade) {
+		_mutex.lockRead();
+	}
 }
 
 t_rwmutex_reader::~t_rwmutex_reader()
 {
-	// std::cout << "mtx rd unlock " << (void*)&_mutex << std::endl;
-	_mutex.unlock();
+	// No-op if we are nested within a writer/future_writer guard
+	if (!_previously_owned_upgrade) {
+		_mutex.unlock();
+	}
+}
+
+t_rwmutex_future_writer::t_rwmutex_future_writer(t_rwmutex& mutex) :
+	t_rwmutex_guard(mutex)
+{
+	// No-op if we are nested within a future_writer guard
+	if (!_previously_owned_upgrade) {
+		_mutex.lockUpdate();
+	}
+}
+
+t_rwmutex_future_writer::~t_rwmutex_future_writer() {
+	// No-op if we are nested within a future_writer guard
+	if (!_previously_owned_upgrade) {
+		_mutex.unlock();
+	}
 }
 
 t_rwmutex_writer::t_rwmutex_writer(t_rwmutex& mutex) :
 	t_rwmutex_guard(mutex)
 {
-	// std::cout << "mtx wr lock " << (void*)&_mutex << std::endl;
-	_mutex.lockWrite();
+	if (_previously_owned_upgrade) {
+		// Writer nested inside a future_writer: upgrade lock
+		_mutex.upgradeLock();
+	} else {
+		// Stand-alone writer guard
+		_mutex.lockWrite();
+	}
 }
 
 t_rwmutex_writer::~t_rwmutex_writer()
 {
-	// std::cout << "mtx wr unlock " << (void*)&_mutex << std::endl;
-	_mutex.unlock();
+	if (_previously_owned_upgrade) {
+		// We were nested within a future_writer guard, so return
+		// the mutex to its previous state
+		_mutex.downgradeLock();
+	} else {
+		_mutex.unlock();
+	}
 }
diff --git a/src/threads/mutex.h b/src/threads/mutex.h
index d757d61..0d45a5f 100644
--- a/src/threads/mutex.h
+++ b/src/threads/mutex.h
@@ -21,6 +21,7 @@
 #include <errno.h>
 #include <pthread.h>
 // #include <iostream>
+#include <atomic>
 
 /**
  * @file
@@ -83,33 +84,100 @@ public:
 	~t_mutex_guard();
 };
 
+
+// Read-write-update lock
+//
+// Read-write lock with an additional "update" type of lock, which can later
+// be upgraded to "write" (and downgraded back to "update" again).  An update
+// lock can co-exist with other read locks, but only one update lock can be
+// held at any time, representing ownership of upgrade rights.
+//
+// See https://stackoverflow.com/a/18785300 for details and further references.
+//
+// Note that our version is rather simplistic, and does not allow downgrading
+// from update/write to read.
+
+// A cheap substitute for std::optional<pthread_t>, only available in C++14.
+// Unfortunately, POSIX.1-2004 no longer requires pthread_t to be an arithmetic
+// type, so we can't simply use 0 as an (unofficial) invalid thread ID.
+struct optional_pthread_t {
+	bool has_value;
+	pthread_t value;
+};
+
 class t_rwmutex {
 protected:
+	// Standard read-write lock
 	pthread_rwlock_t _lock;
+	// Mutex for upgrade ownership
+	t_mutex _up_mutex;
+	// Thread ID that currently owns the _up_mutex lock, if any
+	std::atomic<optional_pthread_t> _up_mutex_thread;
+
+	// Get/release upgrade ownership
+	void getUpgradeOwnership();
+	void releaseUpgradeOwnership();
+
+	// Internal methods to manipulate _lock directly
+	void _lockRead();
+	void _lockWrite();
+	void _unlock();
 public:
 	t_rwmutex();
 	~t_rwmutex();
 
+	// Returns true if the calling thread currently owns the _up_mutex lock
+	bool isUpgradeOwnershipOurs() const;
+
+	// The usual methods for obtaining/releasing locks
 	void lockRead();
+	void lockUpdate();
 	void lockWrite();
 	void unlock();
+
+	// Upgrade an update lock to a write lock, or downgrade in the
+	// opposite direction.  Note that this does not count as an additional
+	// lock, so only one unlock() call will be needed at the end.
+	void upgradeLock();
+	void downgradeLock();
 };
 
+
+// Equivalent of t_mutex_guard for t_rwmutex
+//
+// These can be nested as indicated below.  Note that nesting a weaker guard
+// will not downgrade the lock; for example, a Reader guard within a Writer
+// guard will maintain the write lock.
+
 // Base (abstract) class
 class t_rwmutex_guard {
 protected:
+	// The lock itself
 	t_rwmutex& _mutex;
 
+	// Whether or not we had upgrade ownership beforehand, indicating that
+	// we are nested within the scope of a writer/future_writer guard
+	bool _previously_owned_upgrade;
+
 	// A protected constructor to keep this class abstract
 	t_rwmutex_guard(t_rwmutex& mutex);
 };
 
+// Reader: Can be nested within the scope of any guard
 class t_rwmutex_reader : public t_rwmutex_guard {
 public:
 	t_rwmutex_reader(t_rwmutex& mutex);
 	~t_rwmutex_reader();
 };
 
+// Future writer: Can be nested within the scope of a future_writer guard
+class t_rwmutex_future_writer : public t_rwmutex_guard {
+public:
+	t_rwmutex_future_writer(t_rwmutex& mutex);
+	~t_rwmutex_future_writer();
+};
+
+// Writer: Can be nested within the scope of a future_writer guard
 class t_rwmutex_writer : public t_rwmutex_guard {
 public:
 	t_rwmutex_writer(t_rwmutex& mutex);