| 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 |