clang-tools-extra/clangd/unittests/support/ThreadingTests.cpp

   1 //===-- ThreadingTests.cpp --------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "support/Threading.h"
  10 #include "llvm/ADT/DenseMap.h"
  11 #include "gmock/gmock.h"
  12 #include "gtest/gtest.h"
  13 #include <chrono>
  14 #include <mutex>
  15
  16 namespace clang {
  17 namespace clangd {
  18 class ThreadingTest : public ::testing::Test {};
  19
  20 TEST_F(ThreadingTest, TaskRunner) {
  21   const int TasksCnt = 100;
  22   // This should be const, but MSVC does not allow to use const vars in lambdas
  23   // without capture. On the other hand, clang gives a warning that capture of
  24   // const var is not required.
  25   // Making it non-const makes both compilers happy.
  26   int IncrementsPerTask = 1000;
  27
  28   std::mutex Mutex;
  29   int Counter(0); /* GUARDED_BY(Mutex) */
  30   {
  31     AsyncTaskRunner Tasks;
  32     auto ScheduleIncrements = [&]() {
  33       for (int TaskI = 0; TaskI < TasksCnt; ++TaskI) {
  34         Tasks.runAsync("task", [&Counter, &Mutex, IncrementsPerTask]() {
  35           for (int Increment = 0; Increment < IncrementsPerTask; ++Increment) {
  36             std::lock_guard<std::mutex> Lock(Mutex);
  37             ++Counter;
  38           }
  39         });
  40       }
  41     };
  42
  43     {
  44       // Make sure runAsync is not running tasks synchronously on the same
  45       // thread by locking the Mutex used for increments.
  46       std::lock_guard<std::mutex> Lock(Mutex);
  47       ScheduleIncrements();
  48     }
  49
  50     Tasks.wait();
  51     {
  52       std::lock_guard<std::mutex> Lock(Mutex);
  53       ASSERT_EQ(Counter, TasksCnt * IncrementsPerTask);
  54     }
  55
  56     {
  57       std::lock_guard<std::mutex> Lock(Mutex);
  58       Counter = 0;
  59       ScheduleIncrements();
  60     }
  61   }
  62   // Check that destructor has waited for tasks to finish.
  63   std::lock_guard<std::mutex> Lock(Mutex);
  64   ASSERT_EQ(Counter, TasksCnt * IncrementsPerTask);
  65 }
  66
  67 TEST_F(ThreadingTest, Memoize) {
  68   const unsigned NumThreads = 5;
  69   const unsigned NumKeys = 100;
  70   const unsigned NumIterations = 100;
  71
  72   Memoize<llvm::DenseMap<int, int>> Cache;
  73   std::atomic<unsigned> ComputeCount(0);
  74   std::atomic<int> ComputeResult[NumKeys];
  75   std::fill(std::begin(ComputeResult), std::end(ComputeResult), -1);
  76
  77   AsyncTaskRunner Tasks;
  78   for (unsigned I = 0; I < NumThreads; ++I)
  79     Tasks.runAsync("worker" + std::to_string(I), [&] {
  80       for (unsigned J = 0; J < NumIterations; J++)
  81         for (unsigned K = 0; K < NumKeys; K++) {
  82           int Result = Cache.get(K, [&] { return ++ComputeCount; });
  83           EXPECT_THAT(ComputeResult[K].exchange(Result),
  84                       testing::AnyOf(-1, Result))
  85               << "Got inconsistent results from memoize";
  86         }
  87     });
  88   Tasks.wait();
  89   EXPECT_GE(ComputeCount, NumKeys) << "Computed each key once";
  90   EXPECT_LE(ComputeCount, NumThreads * NumKeys)
  91       << "Worst case, computed each key in every thread";
  92   for (int Result : ComputeResult)
  93     EXPECT_GT(Result, 0) << "All results in expected domain";
  94 }
  95
  96 TEST_F(ThreadingTest, MemoizeDeterministic) {
  97   Memoize<llvm::DenseMap<int, char>> Cache;
  98
  99   // Spawn two parallel computations, A and B.
 100   // Force concurrency: neither can finish until both have started.
 101   // Verify that cache returns consistent results.
 102   AsyncTaskRunner Tasks;
 103   std::atomic<char> ValueA(0), ValueB(0);
 104   Notification ReleaseA, ReleaseB;
 105   Tasks.runAsync("A", [&] {
 106     ValueA = Cache.get(0, [&] {
 107       ReleaseB.notify();
 108       ReleaseA.wait();
 109       return 'A';
 110     });
 111   });
 112   Tasks.runAsync("A", [&] {
 113     ValueB = Cache.get(0, [&] {
 114       ReleaseA.notify();
 115       ReleaseB.wait();
 116       return 'B';
 117     });
 118   });
 119   Tasks.wait();
 120
 121   ASSERT_EQ(ValueA, ValueB);
 122   ASSERT_THAT(ValueA.load(), testing::AnyOf('A', 'B'));
 123 }
 124
 125 // It's hard to write a real test of this class, std::chrono is awkward to mock.
 126 // But test some degenerate cases at least.
 127 TEST(PeriodicThrottlerTest, Minimal) {
 128   PeriodicThrottler Once(std::chrono::hours(24));
 129   EXPECT_TRUE(Once());
 130   EXPECT_FALSE(Once());
 131   EXPECT_FALSE(Once());
 132
 133   PeriodicThrottler Later(std::chrono::hours(24),
 134                           /*Delay=*/std::chrono::hours(24));
 135   EXPECT_FALSE(Later());
 136   EXPECT_FALSE(Later());
 137   EXPECT_FALSE(Later());
 138
 139   PeriodicThrottler Always(std::chrono::seconds(0));
 140   EXPECT_TRUE(Always());
 141   EXPECT_TRUE(Always());
 142   EXPECT_TRUE(Always());
 143 }
 144
 145 } // namespace clangd
 146 } // namespace clang