207 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_THREADING_H10#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_THREADING_H11 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 25namespace clang {26namespace clangd {27 28/// Limits the number of threads that can acquire the lock at the same time.29class Semaphore {30public:31 Semaphore(std::size_t MaxLocks);32 33 bool try_lock();34 void lock();35 void unlock();36 37private: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).46class Deadline {47public: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 65private: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.74Deadline timeoutSeconds(std::optional<double> Seconds);75/// Wait once on CV for the specified duration.76void 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.79template <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.91class Notification {92public: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 99private: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 they107/// all complete on destruction.108class AsyncTaskRunner {109public: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 118private: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 be125/// propagated.126template <typename T>127std::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 the146/// computation multiple times, but each call will return the same result.147template <typename Container> class Memoize {148 mutable Container Cache;149 std::unique_ptr<std::mutex> Mu;150 151public: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 guarded185/// operation still needs to be threadsafe!186class PeriodicThrottler {187 using Stopwatch = std::chrono::steady_clock;188 using Rep = Stopwatch::duration::rep;189 190 Rep Period;191 std::atomic<Rep> Next;192 193public: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 clangd205} // namespace clang206#endif207