[libcxx testing] Make three locking tests more reliable

[davezarzycki]

Summary

The challenge with measuring time in tests is that slow and/or busy machines can cause tests to fail in unexpected ways. After this change, three tests should be much more robust. The only remaining and tiny race that I can think of is preemption after --countDown. That being said, the race isn't fixable because the standard library doesn't provide a way to count threads that are waiting to acquire a lock.

[davezarzycki]

Ran the patch through clang-format and then manually fixed style problems that clang-format did not fix.

[ldionne]

Thanks a lot for taking a look! These tests are a pain because they keep breaking CI.

Would it make sense to apply a similar transformation to other time-sensitive tests? Off the top of my head, I can find:

libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/lock.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/lock_shared.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_for.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_shared.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_shared_for.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_shared_until.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_until.pass.cpp:

libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.timedmutex.requirements/thread.timedmutex.class/try_lock.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.timedmutex.requirements/thread.timedmutex.class/try_lock_for.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.timedmutex.requirements/thread.timedmutex.class/try_lock_until.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.timedmutex.requirements/thread.timedmutex.recursive/lock.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.timedmutex.requirements/thread.timedmutex.recursive/try_lock.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.timedmutex.requirements/thread.timedmutex.recursive/try_lock_for.pass.cpp:
libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.timedmutex.requirements/thread.timedmutex.recursive/try_lock_until.pass.cpp:

I'm not sure which ones of these would make sense for this transformation, but would you mind taking a quick look? I think most of these tests are very similar to the one you modified.

[davezarzycki]

Hi @ldionne – Ya, it looks like a lot of those tests need fixing. The "tolerance" goal is within them is fundamentally flawed. These tests are not testing "real time" APIs where one can hopefully reason about precise timing. These APIs are best-effort APIs and on a slow and/or heavily loaded machine, best-effort can get really slow. I don't have the time to fix all of the tests but here is the gist of what needs fixing is twofold:

1. Use an atomic variable to ensure that all the created threads have started. This isn't perfect, but it's far better than not verifying that they've started.
2. Think hard about each "tolerance" test and convert it to either >= WaitTime or <= WaitTime

I'd also like to add that there seem to be other issues. For example: lock_shared.pass.cpp has two tests, and the latter probably meant to test that a writer lock must wait for readers to finish, but instead it "tests" that a reader lock "waited" (the 'q' thread) but due to signed arithmetic, a negative wait time passes the tolerance test. :-( I'll supply a fix, but really, I don't have the time to audit all of these tests.

[davezarzycki]

Fixed two more tests as an example of how to fix the other thread tests.

[davezarzycki]

Ran through git clang-format to fix formatting issues that predate these fixes.

[davezarzycki]

Hi @ldionne – I've looked a few more tests that use lit's ALLOW_RETRIES feature. I don't think this is a straightforward scenario. While the flawed assumptions are often the same, the fixes are not. Do you want 46 Phab requests? Personally speaking, this seems like one of those cases where the cost of code review discourages bug fixes. If I create decent enough commit messages, would you be open to post-commit review for these test fixes? After all, the tests are already buggy, and we can always revert back to the known buggy version that we have today.

[ldionne]

In D79406#2024856, @davezarzycki wrote:

Hi @ldionne – I've looked a few more tests that use lit's ALLOW_RETRIES feature. I don't think this is a straightforward scenario. While the flawed assumptions are often the same, the fixes are not. Do you want 46 Phab requests? Personally speaking, this seems like one of those cases where the cost of code review discourages bug fixes. If I create decent enough commit messages, would you be open to post-commit review for these test fixes? After all, the tests are already buggy, and we can always revert back to the known buggy version that we have today.

I'm entirely fine with that approach! Thanks a lot for taking a look.

[davezarzycki]

4f4ce13944b88bcd678e615d340c21ea1cf5d3ec

libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/lock.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // UNSUPPORTED: libcpp-has-no-threads
 // UNSUPPORTED: c++98, c++03, c++11
 
-// ALLOW_RETRIES: 2
-
 // shared_timed_mutex was introduced in macosx10.12
 // UNSUPPORTED: with_system_cxx_lib=macosx10.11
 // UNSUPPORTED: with_system_cxx_lib=macosx10.10
 // UNSUPPORTED: with_system_cxx_lib=macosx10.9
 
 // <shared_mutex>
 
 // class shared_timed_mutex;

 std::shared_timed_mutex m;
 
 typedef std::chrono::system_clock Clock;
 typedef Clock::time_point time_point;
 typedef Clock::duration duration;
 typedef std::chrono::milliseconds ms;
 typedef std::chrono::nanoseconds ns;
 
+std::atomic<bool> ready(false);
+time_point start;
 
 ms WaitTime = ms(250);
 
-// Thread sanitizer causes more overhead and will sometimes cause this test
-// to fail. To prevent this we give Thread sanitizer more time to complete the
-// test.
-#if !TEST_HAS_FEATURE(thread_sanitizer)
-ms Tolerance = ms(50);
-#else
-ms Tolerance = ms(100);
-#endif
-
-
 void f()
 {
-    time_point t0 = Clock::now();
-    m.lock();
-    time_point t1 = Clock::now();
-    m.unlock();
-    ns d = t1 - t0 - ms(250);
-    assert(d < ms(50));  // within 50ms
+  ready.store(true);
+  time_point t0 = start;
+  assert(t0.time_since_epoch() > ms(0));
+  assert(t1 - t0 >= WaitTime);
 }
 
 int main(int, char**)
 {
-    m.lock();
-    std::thread t(f);
-    std::this_thread::sleep_for(ms(250));
-    m.unlock();
-    t.join();
+  while (!ready)
+    std::this_thread::yield();
+  start = Clock::now();
+  std::this_thread::sleep_for(WaitTime);
 
   return 0;
 }

libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/lock_shared.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // UNSUPPORTED: libcpp-has-no-threads
 // UNSUPPORTED: c++98, c++03, c++11
 
-// ALLOW_RETRIES: 2
-
 // shared_timed_mutex was introduced in macosx10.12
 // UNSUPPORTED: with_system_cxx_lib=macosx10.11
 // UNSUPPORTED: with_system_cxx_lib=macosx10.10
 // UNSUPPORTED: with_system_cxx_lib=macosx10.9
 
 // <shared_mutex>
 
 // class shared_timed_mutex;

 std::shared_timed_mutex m;
 
 typedef std::chrono::system_clock Clock;
 typedef Clock::time_point time_point;
 typedef Clock::duration duration;
 typedef std::chrono::milliseconds ms;
 typedef std::chrono::nanoseconds ns;
 
+std::atomic<unsigned> countDown;
+time_point readerStart; // Protected by the above mutex 'm'
+time_point writerStart; // Protected by the above mutex 'm'
 
 ms WaitTime = ms(250);
 
-// Thread sanitizer causes more overhead and will sometimes cause this test
-// to fail. To prevent this we give Thread sanitizer more time to complete the
-// test.
-#if !defined(TEST_HAS_SANITIZERS)
-ms Tolerance = ms(50);
-#else
-ms Tolerance = ms(50 * 5);
-#endif
-
-
-void f()
-{
-    time_point t0 = Clock::now();
-    m.lock_shared();
-    time_point t1 = Clock::now();
-    m.unlock_shared();
-    ns d = t1 - t0 - WaitTime;
-    assert(d < Tolerance);  // within tolerance
+void readerMustWait() {
+  --countDown;
+  time_point t0 = readerStart;
+  assert(t0.time_since_epoch() > ms(0));
+  assert(t1 - t0 >= WaitTime);
 }
 
-void g()
-{
-    time_point t0 = Clock::now();
-    m.lock_shared();
-    time_point t1 = Clock::now();
-    m.unlock_shared();
-    ns d = t1 - t0;
-    assert(d < Tolerance);  // within tolerance
+void reader() {
+  --countDown;
 }
 
+void writerMustWait() {
+  --countDown;
+  m.lock();
+  time_point t1 = Clock::now();
+  time_point t0 = writerStart;
+  m.unlock();
+  assert(t0.time_since_epoch() > ms(0));
+  assert(t1 - t0 >= WaitTime);
+}
 
 int main(int, char**)
 {
-    m.lock();
-    std::vector<std::thread> v;
-    for (int i = 0; i < 5; ++i)
-        v.push_back(std::thread(f));
-    std::this_thread::sleep_for(WaitTime);
-    m.unlock();
-    for (auto& t : v)
-        t.join();
-    m.lock_shared();
-    for (auto& t : v)
-        t = std::thread(g);
-    std::thread q(f);
-    std::this_thread::sleep_for(WaitTime);
-    m.unlock_shared();
-    for (auto& t : v)
-        t.join();
-    q.join();
+  int threads = 5;
+
+  countDown.store(threads);
+  for (int i = 0; i < threads; ++i)
+    v.push_back(std::thread(readerMustWait));
+  while (countDown > 0)
+    std::this_thread::yield();
+  readerStart = Clock::now();
+
+  countDown.store(threads + 1);
+    t = std::thread(reader);
+  std::thread q(writerMustWait);
+  while (countDown > 0)
+    std::this_thread::yield();
+  writerStart = Clock::now();
 
   return 0;
 }

libcxx/test/std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_shared_until.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // UNSUPPORTED: libcpp-has-no-threads
 // UNSUPPORTED: c++98, c++03, c++11
 
-// ALLOW_RETRIES: 2
-
 // shared_timed_mutex was introduced in macosx10.12
 // UNSUPPORTED: with_system_cxx_lib=macosx10.11
 // UNSUPPORTED: with_system_cxx_lib=macosx10.10
 // UNSUPPORTED: with_system_cxx_lib=macosx10.9
 
 // <shared_mutex>
 
 // class shared_timed_mutex;

 std::shared_timed_mutex m;
 
 typedef std::chrono::steady_clock Clock;
 typedef Clock::time_point time_point;
 typedef Clock::duration duration;
 typedef std::chrono::milliseconds ms;
 typedef std::chrono::nanoseconds ns;
 
-ms WaitTime = ms(250);
+ms SuccessWaitTime = ms(5000); // Some machines are busy or slow or both
+ms FailureWaitTime = ms(50);
 
-// Thread sanitizer causes more overhead and will sometimes cause this test
-// to fail. To prevent this we give Thread sanitizer more time to complete the
-// test.
-#if !defined(TEST_HAS_SANITIZERS)
-ms Tolerance = ms(50);
-#else
-ms Tolerance = ms(50 * 5);
-#endif
+// On busy or slow machines, there can be a significant delay between thread
+// creation and thread start, so we use an atomic variable to signal that the
+// thread is actually executing.
+static std::atomic<unsigned> countDown;
 
 void f1()
 {
-    time_point t0 = Clock::now();
-    assert(m.try_lock_shared_until(Clock::now() + WaitTime + Tolerance) == true);
-    time_point t1 = Clock::now();
-    m.unlock_shared();
-    ns d = t1 - t0 - WaitTime;
-    assert(d < Tolerance);  // within 50ms
+  --countDown;
+  assert(m.try_lock_shared_until(Clock::now() + SuccessWaitTime) == true);
+  assert(t1 - t0 <= SuccessWaitTime);
 }
 
 void f2()
 {
-    time_point t0 = Clock::now();
-    assert(m.try_lock_shared_until(Clock::now() + WaitTime) == false);
-    time_point t1 = Clock::now();
-    ns d = t1 - t0 - WaitTime;
-    assert(d < Tolerance);  // within tolerance
+  assert(m.try_lock_shared_until(Clock::now() + FailureWaitTime) == false);
+  assert(Clock::now() - t0 >= FailureWaitTime);
 }
 
 int main(int, char**)
 {
-    {
-        m.lock();
-        std::vector<std::thread> v;
-        for (int i = 0; i < 5; ++i)
-            v.push_back(std::thread(f1));
-        std::this_thread::sleep_for(WaitTime);
-        m.unlock();
-        for (auto& t : v)
-            t.join();
-    }
-    {
-        m.lock();
-        std::vector<std::thread> v;
-        for (int i = 0; i < 5; ++i)
-            v.push_back(std::thread(f2));
-        std::this_thread::sleep_for(WaitTime + Tolerance);
-        m.unlock();
-        for (auto& t : v)
-            t.join();
-    }
+  int threads = 5;
+    countDown.store(threads);
+    for (int i = 0; i < threads; ++i)
+    while (countDown > 0)
+      std::this_thread::yield();
+    for (int i = 0; i < threads; ++i)
+    m.unlock();
 
   return 0;
 }