From 2b06a7168bbcbb11384350d918767ab1804b9cdc Mon Sep 17 00:00:00 2001 From: Andrii Grynenko Date: Fri, 16 Dec 2016 13:27:33 -0800 Subject: [PATCH] Fix TimedMutex deadlock when used both from fiber and main context Summary: TimedMutex is a fair mutex, which can cause a deadlock if same mutex is requested first in a fiber, and then in main context. Reviewed By: yfeldblum Differential Revision: D4209155 fbshipit-source-id: 0623d9a2e6a0b5cc310fb71ad1b1cf33afd6a30e --- folly/fibers/TimedMutex-inl.h | 141 ++++++++++++++++++++----------- folly/fibers/TimedMutex.h | 36 ++++---- folly/fibers/test/FibersTest.cpp | 59 +++++++++++++ 3 files changed, 170 insertions(+), 66 deletions(-) diff --git a/folly/fibers/TimedMutex-inl.h b/folly/fibers/TimedMutex-inl.h index 96ee6064..26e523c7 100644 --- a/folly/fibers/TimedMutex-inl.h +++ b/folly/fibers/TimedMutex-inl.h @@ -22,80 +22,127 @@ namespace fibers { // TimedMutex implementation // -template -void TimedMutex::lock() { - pthread_spin_lock(&lock_); +template +TimedMutex::LockResult TimedMutex::lockHelper(WaitFunc&& waitFunc) { + std::unique_lock lock(lock_); if (!locked_) { locked_ = true; - pthread_spin_unlock(&lock_); - return; + return LockResult::SUCCESS; + } + + const auto isOnFiber = onFiber(); + + if (!isOnFiber && notifiedFiber_ != nullptr) { + // lock() was called on a thread and while some other fiber was already + // notified, it hasn't be run yet. We steal the lock from that fiber then + // to avoid potential deadlock. + DCHECK(threadWaiters_.empty()); + notifiedFiber_ = nullptr; + return LockResult::SUCCESS; } // Delay constructing the waiter until it is actually required. // This makes a huge difference, at least in the benchmarks, // when the mutex isn't locked. MutexWaiter waiter; - waiters_.push_back(waiter); - pthread_spin_unlock(&lock_); - waiter.baton.wait(); + if (isOnFiber) { + fiberWaiters_.push_back(waiter); + } else { + threadWaiters_.push_back(waiter); + } + + lock.unlock(); + + if (!waitFunc(waiter)) { + return LockResult::TIMEOUT; + } + + if (isOnFiber) { + auto lockStolen = [&] { + std::lock_guard lg(lock_); + + auto lockStolen = notifiedFiber_ != &waiter; + notifiedFiber_ = nullptr; + return lockStolen; + }(); + + if (lockStolen) { + return LockResult::STOLEN; + } + } + + return LockResult::SUCCESS; } -template -template -bool TimedMutex::timed_lock( - const std::chrono::duration& duration) { - pthread_spin_lock(&lock_); - if (!locked_) { - locked_ = true; - pthread_spin_unlock(&lock_); +inline void TimedMutex::lock() { + auto result = lockHelper([](MutexWaiter& waiter) { + waiter.baton.wait(); return true; + }); + + DCHECK(result != LockResult::TIMEOUT); + if (result == LockResult::SUCCESS) { + return; } + lock(); +} - MutexWaiter waiter; - waiters_.push_back(waiter); - pthread_spin_unlock(&lock_); +template +bool TimedMutex::timed_lock( + const std::chrono::duration& duration) { + auto result = lockHelper([&](MutexWaiter& waiter) { + if (!waiter.baton.timed_wait(duration)) { + // We timed out. Two cases: + // 1. We're still in the waiter list and we truly timed out + // 2. We're not in the waiter list anymore. This could happen if the baton + // times out but the mutex is unlocked before we reach this code. In + // this + // case we'll pretend we got the lock on time. + std::lock_guard lg(lock_); + if (waiter.hook.is_linked()) { + waiter.hook.unlink(); + return false; + } + } + return true; + }); - if (!waiter.baton.timed_wait(duration)) { - // We timed out. Two cases: - // 1. We're still in the waiter list and we truly timed out - // 2. We're not in the waiter list anymore. This could happen if the baton - // times out but the mutex is unlocked before we reach this code. In this - // case we'll pretend we got the lock on time. - pthread_spin_lock(&lock_); - if (waiter.hook.is_linked()) { - waiters_.erase(waiters_.iterator_to(waiter)); - pthread_spin_unlock(&lock_); + switch (result) { + case LockResult::SUCCESS: + return true; + case LockResult::TIMEOUT: return false; - } - pthread_spin_unlock(&lock_); + case LockResult::STOLEN: + // We don't respect the duration if lock was stolen + lock(); + return true; } - return true; + assume_unreachable(); } -template -bool TimedMutex::try_lock() { - pthread_spin_lock(&lock_); +inline bool TimedMutex::try_lock() { + std::lock_guard lg(lock_); if (locked_) { - pthread_spin_unlock(&lock_); return false; } locked_ = true; - pthread_spin_unlock(&lock_); return true; } -template -void TimedMutex::unlock() { - pthread_spin_lock(&lock_); - if (waiters_.empty()) { +inline void TimedMutex::unlock() { + std::lock_guard lg(lock_); + if (!threadWaiters_.empty()) { + auto& to_wake = threadWaiters_.front(); + threadWaiters_.pop_front(); + to_wake.baton.post(); + } else if (!fiberWaiters_.empty()) { + auto& to_wake = fiberWaiters_.front(); + fiberWaiters_.pop_front(); + notifiedFiber_ = &to_wake; + to_wake.baton.post(); + } else { locked_ = false; - pthread_spin_unlock(&lock_); - return; } - MutexWaiter& to_wake = waiters_.front(); - waiters_.pop_front(); - to_wake.baton.post(); - pthread_spin_unlock(&lock_); } // diff --git a/folly/fibers/TimedMutex.h b/folly/fibers/TimedMutex.h index e21f246c..6dbe50ba 100644 --- a/folly/fibers/TimedMutex.h +++ b/folly/fibers/TimedMutex.h @@ -17,6 +17,8 @@ #include +#include +#include #include namespace folly { @@ -27,15 +29,14 @@ namespace fibers { * * Like mutex but allows timed_lock in addition to lock and try_lock. **/ -template class TimedMutex { public: - TimedMutex() { - pthread_spin_init(&lock_, PTHREAD_PROCESS_PRIVATE); - } + TimedMutex() {} ~TimedMutex() { - pthread_spin_destroy(&lock_); + DCHECK(threadWaiters_.empty()); + DCHECK(fiberWaiters_.empty()); + DCHECK(notifiedFiber_ == nullptr); } TimedMutex(const TimedMutex& rhs) = delete; @@ -59,28 +60,25 @@ class TimedMutex { void unlock(); private: - typedef boost::intrusive::list_member_hook<> MutexWaiterHookType; + enum class LockResult { SUCCESS, TIMEOUT, STOLEN }; + + template + LockResult lockHelper(WaitFunc&& waitFunc); // represents a waiter waiting for the lock. The waiter waits on the // baton until it is woken up by a post or timeout expires. struct MutexWaiter { - BatonType baton; - MutexWaiterHookType hook; + Baton baton; + folly::IntrusiveListHook hook; }; - typedef boost::intrusive:: - member_hook - MutexWaiterHook; - - typedef boost::intrusive::list< - MutexWaiter, - MutexWaiterHook, - boost::intrusive::constant_time_size> - MutexWaiterList; + using MutexWaiterList = folly::IntrusiveList; - pthread_spinlock_t lock_; //< lock to protect waiter list + folly::SpinLock lock_; //< lock to protect waiter list bool locked_ = false; //< is this locked by some thread? - MutexWaiterList waiters_; //< list of waiters + MutexWaiterList threadWaiters_; //< list of waiters + MutexWaiterList fiberWaiters_; //< list of waiters + MutexWaiter* notifiedFiber_{nullptr}; //< Fiber waiter which has been notified }; /** diff --git a/folly/fibers/test/FibersTest.cpp b/folly/fibers/test/FibersTest.cpp index d1b60cee..d096839a 100644 --- a/folly/fibers/test/FibersTest.cpp +++ b/folly/fibers/test/FibersTest.cpp @@ -31,6 +31,7 @@ #include #include #include +#include #include #include #include @@ -2072,6 +2073,64 @@ TEST(FiberManager, VirtualEventBase) { EXPECT_TRUE(done2); } +TEST(TimedMutex, ThreadFiberDeadlockOrder) { + folly::EventBase evb; + auto& fm = getFiberManager(evb); + TimedMutex mutex; + + mutex.lock(); + std::thread unlockThread([&] { + /* sleep override */ std::this_thread::sleep_for( + std::chrono::milliseconds{100}); + mutex.unlock(); + }); + + fm.addTask([&] { std::lock_guard lg(mutex); }); + fm.addTask([&] { + runInMainContext([&] { + auto locked = mutex.timed_lock(std::chrono::seconds{1}); + EXPECT_TRUE(locked); + if (locked) { + mutex.unlock(); + } + }); + }); + + evb.loopOnce(); + EXPECT_EQ(0, fm.hasTasks()); + + unlockThread.join(); +} + +TEST(TimedMutex, ThreadFiberDeadlockRace) { + folly::EventBase evb; + auto& fm = getFiberManager(evb); + TimedMutex mutex; + + mutex.lock(); + + fm.addTask([&] { + auto locked = mutex.timed_lock(std::chrono::seconds{1}); + EXPECT_TRUE(locked); + if (locked) { + mutex.unlock(); + } + }); + fm.addTask([&] { + mutex.unlock(); + runInMainContext([&] { + auto locked = mutex.timed_lock(std::chrono::seconds{1}); + EXPECT_TRUE(locked); + if (locked) { + mutex.unlock(); + } + }); + }); + + evb.loopOnce(); + EXPECT_EQ(0, fm.hasTasks()); +} + /** * Test that we can properly track fiber stack usage. * -- 2.34.1