Merge pull request #180 from fbriere/issue/165-deadlocks-complex

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

4 files changed, 243 insertions, 29 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 01f4997..0770bce 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -81,6 +81,7 @@ add_executable(twinkle-console
 )
 
 set(twinkle_LIBS
+	-latomic
 	-lpthread
 	-lresolv
 	${LibMagic_LIBRARY}
diff --git a/src/phone.cpp b/src/phone.cpp
index c97ccce..df4f24d 100644
--- a/src/phone.cpp
+++ b/src/phone.cpp
@@ -339,7 +339,7 @@ void t_phone::refer(const t_url &uri, const string &display) {
 
 void t_phone::refer(unsigned short lineno_from, unsigned short lineno_to) 
 {
-	t_rwmutex_reader x(lines_mtx);
+	t_rwmutex_future_writer x(lines_mtx);
 
 	// The nicest transfer is an attended transfer. An attended transfer
 	// is only possible of the transfer target supports the 'replaces'
@@ -905,7 +905,7 @@ void t_phone::post_process_response(t_response *r, t_tuid tuid, t_tid tid) {
 }
 
 void t_phone::recvd_invite(t_request *r, t_tid tid) {
-	t_rwmutex_reader x(lines_mtx);
+	t_rwmutex_future_writer x(lines_mtx);
 
 	// Check if this INVITE is a retransmission.
 	// Once the TU sent a 2XX repsonse on an INVITE it has to deal
@@ -1704,7 +1704,7 @@ void t_phone::recvd_notify(t_request *r, t_tid tid) {
 	}
 
 	// REFER notification
-	t_rwmutex_reader x(lines_mtx);
+	t_rwmutex_future_writer x(lines_mtx);
 	for (unsigned short i = 0; i < lines.size(); i++) {
 		if (lines[i]->match(r)) {
 			lines[i]->recvd_notify(r, tid);
@@ -1871,7 +1871,7 @@ void t_phone::recvd_refer_permission(bool permission) {
 	t_phone_user *pu = incoming_refer_data->get_phone_user();
 	t_user *user_config = pu->get_user_profile();
 			
-	t_rwmutex_reader x(lines_mtx);
+	t_rwmutex_future_writer x(lines_mtx);
 	lines[i]->recvd_refer_permission(permission, r);
 	
 	if (!permission) {
diff --git a/src/threads/mutex.cpp b/src/threads/mutex.cpp
index 744cd7b..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,21 +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),
+	_previously_owned_upgrade(_mutex.isUpgradeOwnershipOurs())
+{
+}
+
+t_rwmutex_reader::t_rwmutex_reader(t_rwmutex& mutex) :
+	t_rwmutex_guard(mutex)
+{
+	// No-op if we are nested within a writer/future_writer guard
+	if (!_previously_owned_upgrade) {
+		_mutex.lockRead();
+	}
+}
+
+t_rwmutex_reader::~t_rwmutex_reader()
+{
+	// 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)
+{
+	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()
+{
+	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 1fc07d1..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,44 +84,104 @@ 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();
 };
 
-class t_rwmutex_reader {
-private:
+
+// 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) : _mutex(mutex) {
-		// std::cout << "mtx rd lock " << (void*)&_mutex << std::endl;
-		_mutex.lockRead();
-	}
-	~t_rwmutex_reader() {
-		// std::cout << "mtx rd unlock " << (void*)&_mutex << std::endl;
-		_mutex.unlock();
-	}
+	t_rwmutex_reader(t_rwmutex& mutex);
+	~t_rwmutex_reader();
 };
 
-class t_rwmutex_writer {
-private:
-	t_rwmutex& _mutex;
+// 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) : _mutex(mutex) {
-		// std::cout << "mtx wr lock " << (void*)&_mutex << std::endl;
-		_mutex.lockWrite();
-	}
-	~t_rwmutex_writer() {
-		// std::cout << "mtx wr unlock " << (void*)&_mutex << std::endl;
-		_mutex.unlock();
-	}
+	t_rwmutex_writer(t_rwmutex& mutex);
+	~t_rwmutex_writer();
 };