commit 240a564a2bb3bc70c5983300037a199d751c7727
author Hyangseok Chae <neo.chae@lge.com> Wed Jul 25 16:45:08 2018 +0900
committer Hyangseok Chae <neo.chae@lge.com> Fri Jul 27 09:16:02 2018 +0900
tree 132585fa41a9580f0abd4820abfa7c43dfb41d42
parent be272b93ffcec3ccfd2311a58fd28c3927561ed1

Ensure seq_cst memory ordering for num_contenders

Problem.
Mutexes and ReaderWriterMutexes can lose wakeups due to
weak memory ordering. An unlocking thread may overlook waiters.

Thread A
0. ExclusiveLock
1. increase num_contenders as default ordering.
  (fetch_add, std::memory_order_seq_cst)
2. futex waiting
...permently waiting
3. wakeup
4. decrease num_contenders
5. running

Thread B
0. Reset lock state to unlocked using seq_cst CAS.
1. load num_contenders with LoadRelaxed
   (std::memory_order_relaxed)
2. if num_contenders is bigger than 0, wakeup waiters.

Thread B's load of num_contenders may be reordered with the store
in the preceding CAS (step 0).

We can then get the following interleaving:
A.0 (fails: lock held.)
B.0a (CAS load acquire sees lock as held)
B.1 (sees num_contenders = 0)
A.1 num_contenders++;
A.2 futex starts waiting (state unchanged)
B.0b (CAS store release sets state to unlocked)
B.2 (does nothing since num_contenders was 0)

We observed this hang with state_ = 0,
exclusive_owner_ = 0, num_contenders_ = 1
Indeed, the preceding comment strongly suggests that the num_contenders
load should not be relaxed.

Test: test-art-host, test-art-target

Change-Id: I912bcd3a186d9c36fb3da8a41c1f9aa1f7b39be5
Signed-off-by: Hyangseok Chae <neo.chae@lge.com>

runtime/base/mutex-inl.h

diff --git a/runtime/base/mutex-inl.h b/runtime/base/mutex-inl.h
index 51ca274..74db312 100644
--- a/runtime/base/mutex-inl.h
+++ b/runtime/base/mutex-inl.h
@@ -193,8 +193,8 @@
       // a status bit into the state on contention.
       done = state_.CompareAndSetWeakSequentiallyConsistent(cur_state, cur_state - 1);
       if (done && (cur_state - 1) == 0) {  // Weak CAS may fail spuriously.
-        if (num_pending_writers_.load(std::memory_order_relaxed) > 0 ||
-            num_pending_readers_.load(std::memory_order_relaxed) > 0) {
+        if (num_pending_writers_.load(std::memory_order_seq_cst) > 0 ||
+            num_pending_readers_.load(std::memory_order_seq_cst) > 0) {
           // Wake any exclusive waiters as there are now no readers.
           futex(state_.Address(), FUTEX_WAKE, -1, nullptr, nullptr, 0);
         }

runtime/base/mutex.cc

diff --git a/runtime/base/mutex.cc b/runtime/base/mutex.cc
index dd58d75..7b888b1 100644
--- a/runtime/base/mutex.cc
+++ b/runtime/base/mutex.cc
@@ -553,7 +553,7 @@
         done = state_.CompareAndSetWeakSequentiallyConsistent(cur_state, 0 /* new state */);
         if (LIKELY(done)) {  // Spurious fail?
           // Wake a contender.
-          if (UNLIKELY(num_contenders_.load(std::memory_order_relaxed) > 0)) {
+          if (UNLIKELY(num_contenders_.load(std::memory_order_seq_cst) > 0)) {
             futex(state_.Address(), FUTEX_WAKE, 1, nullptr, nullptr, 0);
           }
         }
@@ -690,8 +690,8 @@
       done = state_.CompareAndSetWeakSequentiallyConsistent(-1 /* cur_state*/, 0 /* new state */);
       if (LIKELY(done)) {  // Weak CAS may fail spuriously.
         // Wake any waiters.
-        if (UNLIKELY(num_pending_readers_.load(std::memory_order_relaxed) > 0 ||
-                     num_pending_writers_.load(std::memory_order_relaxed) > 0)) {
+        if (UNLIKELY(num_pending_readers_.load(std::memory_order_seq_cst) > 0 ||
+                     num_pending_writers_.load(std::memory_order_seq_cst) > 0)) {
           futex(state_.Address(), FUTEX_WAKE, -1, nullptr, nullptr, 0);
         }
       }