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