[libcxx] Fix bug in shared_timed_mutex that could cause a program to hang.

[EricWF]

Summary

The summary of the bug, provided by Stephan T. Lavavej:

In shared_timed_mutex::try_lock_until() (line 195 in 3.6.0), you need to deliver a notification. The scenario is:

• There are N threads holding the shared lock.
• One thread calls try_lock_until() to attempt to acquire the exclusive lock. It sets the "I want to write" bool/bit, then waits for the N readers to drain away.
• K more threads attempt to acquire the shared lock, but they notice that someone said "I want to write", so they block on a condition_variable.
• At least one of the N readers is stubborn and doesn't release the shared lock.
• The wannabe-writer times out, gives up, and unsets the "I want to write" bool/bit.

At this point, a notification (it needs to be notify_all) must be delivered to the condition_variable that the K wannabe-readers are waiting on. Otherwise, they can block forever without waking up.

[EricWF]

Change notify_one() to notify_all(), using notify_one() can still cause deadlock. Also modify test so it would have caught that bug.

[EricWF]

I think my last fix where we released the lock before calling notify_all() introduced a race condition where another thread could enter the lock() method reach gate2_ before gate1_ was notified. The thread waiting on __gate2_ would never be notified.

[jyasskin]

There must be better names for those variables than gate1 and gate2.

It's weird that the condition_variable::wait_until() loops aren't using the predicate versions of wait_until() so they wouldn't need the loops. Even in C++98 mode where you'd have to name the predicates, it seems like it'd be worth it.

The fix itself looks correct to me.

test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_until_deadlock_bug.pass.cpp

29

Nit: Can't you initialize this as:

std::atomic<int> readers_started(0);

?

32

This comment is out of date.

46

"blocked by main()."

[EricWF]

The fix itself looks correct to me.

Good! The fix I had before released the mutex before calling notify_all(). I was hoping to do that as an optimization but I don't think it is possible. Should I be at all concerned about notifying other threads while holding the lock?

[EricWF]

Address review comments.

[EricWF]

Because the initialism for Stefan's name and that of the Standard Template Library are the same, I'd rather see this named something reflecting what the bug was, instead of the initials of the guy who reported it. This avoids the
confused question of "isn't every libc++ bug an STL bug?", despite him having made a big name for himself in the community.

Good point. I've changed it.

Also, did he file a PR for this?

No PR unfortunately. He emailed this bug out to a couple of people.

[jyasskin]

In D8796#151237, @EricWF wrote:

The fix itself looks correct to me.

Good! The fix I had before released the mutex before calling notify_all(). I was hoping to do that as an optimization but I don't think it is possible. Should I be at all concerned about notifying other threads while holding the lock?

There's no requirement that the mutex be either locked or unlocked when you call notify_*(). One choice might be faster than the other, but it depends on the mutex+condvar implementation. (A smart mutex+condvar can ensure that no thread is unblocked before the mutex is unlocked.) If you're tempted to optimize this, consider optimizing the fact that std::mutex uses pthread_mutex, which is big and slow, first.

include/shared_mutex

             if (__status == cv_status::timeout)
             {
                 __state_ &= ~__write_entered_;
+                __gate1_.notify_all();
                 return false;
             }
         }

test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_until_deadlock_bug.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+// UNSUPPORTED: c++03, c++98, c++11
+
+// <shared_mutex>
+
+// class shared_timed_mutex;
+
+#include <shared_mutex>
+
+#include <atomic>
+#include <chrono>
+#include <thread>
+#include <cstdlib>
+#include <cassert>
+
+std::shared_timed_mutex m;
+
+const int total_readers = 2;
+std::atomic<int> readers_started(0);
+std::atomic<int> readers_finished(0);
+
+// Wait for the readers to start then try and acquire the write lock.
+void writer_one() {
+  while (readers_started != total_readers) {}
+  bool b = m.try_lock_for(std::chrono::milliseconds(500));
+  assert(b == false);
+}
+
+void blocked_reader() {
+  ++readers_started;
+  // Wait until writer_one is waiting for the write lock.
+  while (m.try_lock_shared()) {
+    m.unlock_shared();
+  }
+  // Attempt to get the read lock. writer_one should be blocking us because
+  // writer_one is blocked by main.
+  m.lock_shared();
+  ++readers_finished;
+  m.unlock_shared();
+}
+
+int main()
+{
+  typedef std::chrono::steady_clock Clock;
+
+  m.lock_shared();
+  std::thread t1(writer_one);
+  // create some readers
+  std::thread t2(blocked_reader);
+  std::thread t3(blocked_reader);
+  // Kill the test after 10 seconds if it hasn't completed.
+  auto end_point = Clock::now() + std::chrono::seconds(10);
+  while (readers_finished != total_readers && Clock::now() < end_point) {
+    std::this_thread::sleep_for(std::chrono::seconds(1));
+  }
+  assert(readers_finished == total_readers);
+  m.unlock_shared();
+  t1.join();
+  t2.join();
+  t3.join();
+}