From b60354d82e3dc0e219cf08e956c94aa2585c104b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Bri=C3=A8re?= Date: Wed, 2 Oct 2019 22:05:01 -0400 Subject: Move t_rwmutex_reader/writer definitions into mutex.cpp These classes are about to get more complex, so let's move them ahead of time into mutex.cpp. --- src/threads/mutex.cpp | 28 ++++++++++++++++++++++++++++ src/threads/mutex.h | 20 ++++---------------- 2 files changed, 32 insertions(+), 16 deletions(-) diff --git a/src/threads/mutex.cpp b/src/threads/mutex.cpp index 744cd7b..9c6a762 100644 --- a/src/threads/mutex.cpp +++ b/src/threads/mutex.cpp @@ -124,3 +124,31 @@ void t_rwmutex::unlock() { pthread_rwlock_unlock(&_lock); } + +/////////////////////////// +// t_rwmutex_guard +/////////////////////////// + +t_rwmutex_reader::t_rwmutex_reader(t_rwmutex& mutex) : _mutex(mutex) +{ + // std::cout << "mtx rd lock " << (void*)&_mutex << std::endl; + _mutex.lockRead(); +} + +t_rwmutex_reader::~t_rwmutex_reader() +{ + // std::cout << "mtx rd unlock " << (void*)&_mutex << std::endl; + _mutex.unlock(); +} + +t_rwmutex_writer::t_rwmutex_writer(t_rwmutex& mutex) : _mutex(mutex) +{ + // std::cout << "mtx wr lock " << (void*)&_mutex << std::endl; + _mutex.lockWrite(); +} + +t_rwmutex_writer::~t_rwmutex_writer() +{ + // std::cout << "mtx wr unlock " << (void*)&_mutex << std::endl; + _mutex.unlock(); +} diff --git a/src/threads/mutex.h b/src/threads/mutex.h index 1fc07d1..15d5181 100644 --- a/src/threads/mutex.h +++ b/src/threads/mutex.h @@ -99,28 +99,16 @@ class t_rwmutex_reader { private: t_rwmutex& _mutex; 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; 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(); }; -- cgit v1.2.3 From 3d126cd9a7f9029e199e9220e2ffa08ac4e23227 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Bri=C3=A8re?= Date: Wed, 2 Oct 2019 22:13:56 -0400 Subject: Create t_rwmutex_guard base class (Doing this ahead of time to simplify the next commit a bit.) --- src/threads/mutex.cpp | 11 +++++++++-- src/threads/mutex.h | 15 ++++++++++----- 2 files changed, 19 insertions(+), 7 deletions(-) diff --git a/src/threads/mutex.cpp b/src/threads/mutex.cpp index 9c6a762..7eaa329 100644 --- a/src/threads/mutex.cpp +++ b/src/threads/mutex.cpp @@ -129,7 +129,13 @@ void t_rwmutex::unlock() // t_rwmutex_guard /////////////////////////// -t_rwmutex_reader::t_rwmutex_reader(t_rwmutex& mutex) : _mutex(mutex) +t_rwmutex_guard::t_rwmutex_guard(t_rwmutex& mutex) : + _mutex(mutex) +{ +} + +t_rwmutex_reader::t_rwmutex_reader(t_rwmutex& mutex) : + t_rwmutex_guard(mutex) { // std::cout << "mtx rd lock " << (void*)&_mutex << std::endl; _mutex.lockRead(); @@ -141,7 +147,8 @@ t_rwmutex_reader::~t_rwmutex_reader() _mutex.unlock(); } -t_rwmutex_writer::t_rwmutex_writer(t_rwmutex& mutex) : _mutex(mutex) +t_rwmutex_writer::t_rwmutex_writer(t_rwmutex& mutex) : + t_rwmutex_guard(mutex) { // std::cout << "mtx wr lock " << (void*)&_mutex << std::endl; _mutex.lockWrite(); diff --git a/src/threads/mutex.h b/src/threads/mutex.h index 15d5181..d757d61 100644 --- a/src/threads/mutex.h +++ b/src/threads/mutex.h @@ -95,17 +95,22 @@ public: void unlock(); }; -class t_rwmutex_reader { -private: +// Base (abstract) class +class t_rwmutex_guard { +protected: t_rwmutex& _mutex; + + // A protected constructor to keep this class abstract + t_rwmutex_guard(t_rwmutex& mutex); +}; + +class t_rwmutex_reader : public t_rwmutex_guard { public: t_rwmutex_reader(t_rwmutex& mutex); ~t_rwmutex_reader(); }; -class t_rwmutex_writer { -private: - t_rwmutex& _mutex; +class t_rwmutex_writer : public t_rwmutex_guard { public: t_rwmutex_writer(t_rwmutex& mutex); ~t_rwmutex_writer(); -- cgit v1.2.3 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 From 21ad823ba038f28a58f0f660cc7ebe902dd459b8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Bri=C3=A8re?= Date: Sun, 29 Sep 2019 00:07:00 -0400 Subject: Fix "INVITE with Replaces header" deadlock This occurs on reception of an INVITE with a Replaces header, due to the following path: - recvd_invite() acquires a read lock on lines_mtx - recvd_initial_invite() is called - A write lock over lines_mtx is acquired --- src/phone.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/phone.cpp b/src/phone.cpp index 8de3834..a609bef 100644 --- a/src/phone.cpp +++ b/src/phone.cpp @@ -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 -- cgit v1.2.3 From 52fbf19819e911d590da3766898615d6c21027c8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Bri=C3=A8re?= Date: Sun, 29 Sep 2019 00:20:23 -0400 Subject: Fix "NOTIFY received when line is idle" deadlock This can easily be triggered by starting a blind transfer, and hanging up before the other end has accepted/rejected it, due to the following path: - recvd_notify() acquires a read lock on lines_mtx - cleanup_dead_lines() is called - A write lock on lines_mtx is acquired --- src/phone.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/phone.cpp b/src/phone.cpp index a609bef..c4e515f 100644 --- a/src/phone.cpp +++ b/src/phone.cpp @@ -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); -- cgit v1.2.3 From 31a25748fccca729e402aca15fca67eb9cc43c03 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Bri=C3=A8re?= Date: Sun, 29 Sep 2019 00:27:52 -0400 Subject: Fix "Transfer with consultation without Replaces" deadlock This occurs when performing a consult transfer if the target does not support the Replaces extension, due to the following path: - refer() acquires a read lock over lines_mtx - refer_consultation() is called - A write lock over lines_mtx is acquired Closes #118 --- src/phone.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/phone.cpp b/src/phone.cpp index c4e515f..401abb1 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' -- cgit v1.2.3 From f1102b9a5e4e45434fb6e581b40f06d8ef39c911 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Bri=C3=A8re?= Date: Sun, 29 Sep 2019 00:38:15 -0400 Subject: Fix "REFER declined" deadlock This occurs when the user declines an incoming call transfer request, due to the following path: - recvd_refer_permission() acquires a read lock over lines_mtx - move_releasing_lines_to_background() is called - A write lock over lines_mtx is acquired --- src/phone.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/phone.cpp b/src/phone.cpp index 401abb1..2718c82 100644 --- a/src/phone.cpp +++ b/src/phone.cpp @@ -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) { -- cgit v1.2.3