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