From 579d6ed48cf9a893a21bfb20418b659d183a51a1 Mon Sep 17 00:00:00 2001
From: David Zarzycki <dave@znu.io>
Date: Wed, 3 Jun 2020 08:44:45 -0400
Subject: [PATCH] [libcxx testing] Fix lingering bugs in notify_one.pass.cpp

This test is arguably fatally flawed, at least as long as C++ condition
variables are just trivial wrappers around POSIX. I've added some notes
to the test for future authors to consider.
---
 .../thread.condition.condvar/notify_one.pass.cpp   | 87 ++++++++++++++--------
 1 file changed, 54 insertions(+), 33 deletions(-)

diff --git a/libcxx/test/std/thread/thread.condition/thread.condition.condvar/notify_one.pass.cpp b/libcxx/test/std/thread/thread.condition/thread.condition.condvar/notify_one.pass.cpp
index 60e4448..b373050 100644
--- a/libcxx/test/std/thread/thread.condition/thread.condition.condvar/notify_one.pass.cpp
+++ b/libcxx/test/std/thread/thread.condition/thread.condition.condvar/notify_one.pass.cpp
@@ -14,6 +14,27 @@
 
 // void notify_one();
 
+
+// NOTE: `notify_one` is just a wrapper around pthread_cond_signal, but
+// POSIX does not guarantee that one and only one thread will be woken:
+//
+// https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_signal.html
+//
+// Quote:
+//     Multiple Awakenings by Condition Signal
+//     On a multi-processor, it may be impossible for an implementation of
+//     pthread_cond_signal() to avoid the unblocking of more than one thread
+//     blocked on a condition variable. For example...
+
+
+
+// NOTE: In previous versions of this test, `notify_one` was called WITHOUT
+// holding the lock but POSIX says (in the aforementioned URL) that:
+//     ...if predictable scheduling behavior is required, then that mutex shall
+//     be locked by the thread calling pthread_cond_broadcast() or
+//     pthread_cond_signal().
+
+
 #include <condition_variable>
 #include <atomic>
 #include <mutex>
@@ -33,9 +54,9 @@ std::atomic_int which(0);
 
 void f1()
 {
-  --ready;
   std::unique_lock<std::mutex> lk(mut);
   assert(test1 == 0);
+  --ready;
   while (test1 == 0)
     cv.wait(lk);
   which = 1;
@@ -45,9 +66,9 @@ void f1()
 
 void f2()
 {
-  --ready;
   std::unique_lock<std::mutex> lk(mut);
   assert(test2 == 0);
+  --ready;
   while (test2 == 0)
     cv.wait(lk);
   which = 2;
@@ -59,49 +80,49 @@ int main(int, char**)
 {
   std::thread t1(f1);
   std::thread t2(f2);
-  while (ready > 0)
-    std::this_thread::yield();
-  // In case the threads were preempted right after the atomic decrement but
-  // before cv.wait(), we yield one more time.
-  std::this_thread::yield();
   {
-    std::unique_lock<std::mutex>lk(mut);
+    while (ready > 0)
+      std::this_thread::yield();
+    // At this point:
+    // 1) Both f1 and f2 have entered their condition variable wait.
+    // 2) Either f1 or f2 has the mutex locked and is about to wait.
+    std::unique_lock<std::mutex> lk(mut);
     test1 = 1;
     test2 = 1;
     ready = 1;
+    cv.notify_one();
   }
-  cv.notify_one();
   {
     while (which == 0)
       std::this_thread::yield();
-    std::unique_lock<std::mutex>lk(mut);
-  }
-  if (test1 == 2) {
-    assert(test2 == 1);
-    t1.join();
-    test1 = 0;
-  } else {
-    assert(test1 == 1);
-    assert(test2 == 2);
-    t2.join();
-    test2 = 0;
+    std::unique_lock<std::mutex> lk(mut);
+    if (test1 == 2) {
+      assert(test2 == 1);
+      t1.join();
+      test1 = 0;
+    } else {
+      assert(test1 == 1);
+      assert(test2 == 2);
+      t2.join();
+      test2 = 0;
+    }
+    which = 0;
+    cv.notify_one();
   }
-  which = 0;
-  cv.notify_one();
   {
     while (which == 0)
       std::this_thread::yield();
-    std::unique_lock<std::mutex>lk(mut);
-  }
-  if (test1 == 2) {
-    assert(test2 == 0);
-    t1.join();
-    test1 = 0;
-  } else {
-    assert(test1 == 0);
-    assert(test2 == 2);
-    t2.join();
-    test2 = 0;
+    std::unique_lock<std::mutex> lk(mut);
+    if (test1 == 2) {
+      assert(test2 == 0);
+      t1.join();
+      test1 = 0;
+    } else {
+      assert(test1 == 0);
+      assert(test2 == 2);
+      t2.join();
+      test2 = 0;
+    }
   }
 
   return 0;
-- 
2.7.4