From 91de36717a119f9501698af97550bfcdffd2875a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Bri=C3=A8re?= Date: Fri, 27 Dec 2019 02:26:38 -0500 Subject: 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.) --- src/CMakeLists.txt | 1 + src/threads/mutex.cpp | 143 +++++++++++++++++++++++++++++++++++++++++++++----- src/threads/mutex.h | 68 ++++++++++++++++++++++++ 3 files changed, 199 insertions(+), 13 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/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 #include // #include +#include /** * @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, 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 _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); -- cgit v1.2.3