clang-tools  12.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 <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:
60  Deadline(std::chrono::steady_clock::time_point Time)
61  : Type(Finite), Time(Time) {}
62  static Deadline zero() { return Deadline(Zero); }
63  static Deadline infinity() { return Deadline(Infinite); }
64 
65  std::chrono::steady_clock::time_point time() const {
66  assert(Type == Finite);
67  return Time;
68  }
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 
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>
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.
106 public:
107  /// Destructor waits for all pending tasks to finish.
108  ~AsyncTaskRunner();
109 
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>
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:
149  Memoize() : Mu(std::make_unique<std::mutex>()) {}
150 
151  template <typename T, typename Func>
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
A threadsafe flag that is initially clear.
Definition: Threading.h:27
Memoize is a cache to store and reuse computation results based on a key.
Definition: Threading.h:144
bool operator==(const Deadline &Other) const
Definition: Threading.h:73
Limits the number of threads that can acquire the lock at the same time.
Definition: Threading.h:41
std::future< T > runAsync(llvm::unique_function< T()> Action)
Runs Action asynchronously with a new std::thread.
Definition: Threading.h:124
Context Ctx
Context clone() const
Clone this context object.
Definition: Context.cpp:20
static Deadline infinity()
Definition: Threading.h:63
llvm::unique_function< void()> Action
static const Context & current()
Returns the context for the current thread, creating it if needed.
Definition: Context.cpp:27
static constexpr llvm::StringLiteral Name
Runs tasks on separate (detached) threads and wait for all tasks to finish.
Definition: Threading.h:105
A context is an immutable container for per-request data that must be propagated through layers that ...
Definition: Context.h:69
WithContext replaces Context::current() with a provided scope.
Definition: Context.h:189
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
static Deadline zero()
Definition: Threading.h:62
Deadline timeoutSeconds(llvm::Optional< double > Seconds)
Makes a deadline from a timeout in seconds. None means wait forever.
Definition: Threading.cpp:102
Deadline(std::chrono::steady_clock::time_point Time)
Definition: Threading.h:60
A point in time we can wait for.
Definition: Threading.h:58
bool expired() const
Definition: Threading.h:69
std::chrono::steady_clock::time_point time() const
Definition: Threading.h:65
NodeType Type