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
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(D: 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 they
107/// 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(D: 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 be
125/// 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 the
146/// 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 guarded
185/// 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 clangd
205} // namespace clang
206#endif
207

source code of clang-tools-extra/clangd/support/Threading.h