clang-tools-extra/clangd/support/Threading.h

   1 //===--- Threading.h - Abstractions for multithreading -----------*- 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 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_THREADING_H
  10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_THREADING_H
  11
  12 #include "support/Context.h"
  13 #include "llvm/ADT/FunctionExtras.h"
  14 #include "llvm/ADT/Twine.h"
  15 #include <atomic>
  16 #include <cassert>
  17 #include <condition_variable>
  18 #include <future>
  19 #include <memory>
  20 #include <mutex>
  21 #include <optional>
  22 #include <thread>
  23 #include <vector>
  24
  25 namespace clang {
  26 namespace clangd {
  27
  28 /// Limits the number of threads that can acquire the lock at the same time.
  29 class Semaphore {
  30 public:
  31   Semaphore(std::size_t MaxLocks);
  32
  33   bool try_lock();
  34   void lock();
  35   void unlock();
  36
  37 private:
  38   std::mutex Mutex;
  39   std::condition_variable SlotsChanged;
  40   std::size_t FreeSlots;
  41 };
  42
  43 /// A point in time we can wait for.
  44 /// Can be zero (don't wait) or infinity (wait forever).
  45 /// (Not time_point::max(), because many std::chrono implementations overflow).
  46 class Deadline {
  47 public:
  48   Deadline(std::chrono::steady_clock::time_point Time)
  49       : Type(Finite), Time(Time) {}
  50   static Deadline zero() { return Deadline(Zero); }
  51   static Deadline infinity() { return Deadline(Infinite); }
  52
  53   std::chrono::steady_clock::time_point time() const {
  54     assert(Type == Finite);
  55     return Time;
  56   }
  57   bool expired() const {
  58     return (Type == Zero) ||
  59            (Type == Finite && Time < std::chrono::steady_clock::now());
  60   }
  61   bool operator==(const Deadline &Other) const {
  62     return (Type == Other.Type) && (Type != Finite || Time == Other.Time);
  63   }
  64
  65 private:
  66   enum Type { Zero, Infinite, Finite };
  67
  68   Deadline(enum Type Type) : Type(Type) {}
  69   enum Type Type;
  70   std::chrono::steady_clock::time_point Time;
  71 };
  72
  73 /// Makes a deadline from a timeout in seconds. std::nullopt means wait forever.
  74 Deadline timeoutSeconds(std::optional<double> Seconds);
  75 /// Wait once on CV for the specified duration.
  76 void wait(std::unique_lock<std::mutex> &Lock, std::condition_variable &CV,
  77           Deadline D);
  78 /// Waits on a condition variable until F() is true or D expires.
  79 template <typename Func>
  80 [[nodiscard]] bool wait(std::unique_lock<std::mutex> &Lock,
  81                         std::condition_variable &CV, Deadline D, Func F) {
  82   while (!F()) {
  83     if (D.expired())
  84       return false;
  85     wait(Lock, CV, D);
  86   }
  87   return true;
  88 }
  89
  90 /// A threadsafe flag that is initially clear.
  91 class Notification {
  92 public:
  93   // Sets the flag. No-op if already set.
  94   void notify();
  95   // Blocks until flag is set.
  96   void wait() const { (void)wait(Deadline::infinity()); }
  97   [[nodiscard]] bool wait(Deadline D) const;
  98
  99 private:
 100   bool Notified = false;
 101   mutable std::condition_variable CV;
 102   mutable std::mutex Mu;
 103 };
 104
 105 /// Runs tasks on separate (detached) threads and wait for all tasks to finish.
 106 /// Objects that need to spawn threads can own an AsyncTaskRunner to ensure they
 107 /// all complete on destruction.
 108 class AsyncTaskRunner {
 109 public:
 110   /// Destructor waits for all pending tasks to finish.
 111   ~AsyncTaskRunner();
 112
 113   void wait() const { (void)wait(Deadline::infinity()); }
 114   [[nodiscard]] bool wait(Deadline D) const;
 115   // The name is used for tracing and debugging (e.g. to name a spawned thread).
 116   void runAsync(const llvm::Twine &Name, llvm::unique_function<void()> Action);
 117
 118 private:
 119   mutable std::mutex Mutex;
 120   mutable std::condition_variable TasksReachedZero;
 121   std::size_t InFlightTasks = 0;
 122 };
 123
 124 /// Runs \p Action asynchronously with a new std::thread. The context will be
 125 /// propagated.
 126 template <typename T>
 127 std::future<T> runAsync(llvm::unique_function<T()> Action) {
 128   return std::async(
 129       std::launch::async,
 130       [](llvm::unique_function<T()> &&Action, Context Ctx) {
 131         WithContext WithCtx(std::move(Ctx));
 132         return Action();
 133       },
 134       std::move(Action), Context::current().clone());
 135 }
 136
 137 /// Memoize is a cache to store and reuse computation results based on a key.
 138 ///
 139 ///   Memoize<DenseMap<int, bool>> PrimeCache;
 140 ///   for (int I : RepetitiveNumbers)
 141 ///     if (PrimeCache.get(I, [&] { return expensiveIsPrime(I); }))
 142 ///       llvm::errs() << "Prime: " << I << "\n";
 143 ///
 144 /// The computation will only be run once for each key.
 145 /// This class is threadsafe. Concurrent calls for the same key may run the
 146 /// computation multiple times, but each call will return the same result.
 147 template <typename Container> class Memoize {
 148   mutable Container Cache;
 149   std::unique_ptr<std::mutex> Mu;
 150
 151 public:
 152   Memoize() : Mu(std::make_unique<std::mutex>()) {}
 153
 154   template <typename T, typename Func>
 155   typename Container::mapped_type get(T &&Key, Func Compute) const {
 156     {
 157       std::lock_guard<std::mutex> Lock(*Mu);
 158       auto It = Cache.find(Key);
 159       if (It != Cache.end())
 160         return It->second;
 161     }
 162     // Don't hold the mutex while computing.
 163     auto V = Compute();
 164     {
 165       std::lock_guard<std::mutex> Lock(*Mu);
 166       auto R = Cache.try_emplace(std::forward<T>(Key), V);
 167       // Insert into cache may fail if we raced with another thread.
 168       if (!R.second)
 169         return R.first->second; // Canonical value, from other thread.
 170     }
 171     return V;
 172   }
 173 };
 174
 175 /// Used to guard an operation that should run at most every N seconds.
 176 ///
 177 /// Usage:
 178 ///   mutable PeriodicThrottler ShouldLog(std::chrono::seconds(1));
 179 ///   void calledFrequently() {
 180 ///     if (ShouldLog())
 181 ///       log("this is not spammy");
 182 ///   }
 183 ///
 184 /// This class is threadsafe. If multiple threads are involved, then the guarded
 185 /// operation still needs to be threadsafe!
 186 class PeriodicThrottler {
 187   using Stopwatch = std::chrono::steady_clock;
 188   using Rep = Stopwatch::duration::rep;
 189
 190   Rep Period;
 191   std::atomic<Rep> Next;
 192
 193 public:
 194   /// If Period is zero, the throttler will return true every time.
 195   PeriodicThrottler(Stopwatch::duration Period, Stopwatch::duration Delay = {})
 196       : Period(Period.count()),
 197         Next((Stopwatch::now() + Delay).time_since_epoch().count()) {}
 198
 199   /// Returns whether the operation should run at this time.
 200   /// operator() is safe to call concurrently.
 201   bool operator()();
 202 };
 203
 204 } // namespace clangd
 205 } // namespace clang
 206 #endif