clang-tools  14.0.0git
BackgroundQueue.cpp
Go to the documentation of this file.
1 //===-- BackgroundQueue.cpp - Task queue for background index -------------===//
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 #include "index/Background.h"
10 #include "support/Logger.h"
11 
12 namespace clang {
13 namespace clangd {
14 
15 static std::atomic<bool> PreventStarvation = {false};
16 
18  PreventStarvation.store(true);
19 }
20 
21 void BackgroundQueue::work(std::function<void()> OnIdle) {
22  while (true) {
23  llvm::Optional<Task> Task;
24  {
25  std::unique_lock<std::mutex> Lock(Mu);
26  CV.wait(Lock, [&] { return ShouldStop || !Queue.empty(); });
27  if (ShouldStop) {
28  Queue.clear();
29  CV.notify_all();
30  return;
31  }
32  ++Stat.Active;
33  std::pop_heap(Queue.begin(), Queue.end());
34  Task = std::move(Queue.back());
35  Queue.pop_back();
36  notifyProgress();
37  }
38 
39  if (Task->ThreadPri != llvm::ThreadPriority::Default &&
40  !PreventStarvation.load())
41  llvm::set_thread_priority(Task->ThreadPri);
42  Task->Run();
43  if (Task->ThreadPri != llvm::ThreadPriority::Default)
44  llvm::set_thread_priority(llvm::ThreadPriority::Default);
45 
46  {
47  std::unique_lock<std::mutex> Lock(Mu);
48  ++Stat.Completed;
49  if (Stat.Active == 1 && Queue.empty()) {
50  // We just finished the last item, the queue is going idle.
51  assert(ShouldStop || Stat.Completed == Stat.Enqueued);
52  Stat.LastIdle = Stat.Completed;
53  if (OnIdle) {
54  Lock.unlock();
55  OnIdle();
56  Lock.lock();
57  }
58  }
59  assert(Stat.Active > 0 && "before decrementing");
60  --Stat.Active;
61  notifyProgress();
62  }
63  CV.notify_all();
64  }
65 }
66 
68  {
69  std::lock_guard<std::mutex> QueueLock(Mu);
70  ShouldStop = true;
71  }
72  CV.notify_all();
73 }
74 
75 // Tweaks the priority of a newly-enqueued task, or returns false to cancel it.
76 bool BackgroundQueue::adjust(Task &T) {
77  // It is tempting to drop duplicates of queued tasks, and merely deprioritize
78  // duplicates of completed tasks (i.e. reindexing on CDB changes). But:
79  // - the background indexer doesn't support reindexing well, e.g. staleness
80  // is checked at *enqueue* time only, and doesn't account for compile flags
81  // - reindexing on compile flags is often a poor use of CPU in practice
82  if (T.Key && !SeenKeys.insert(T.Key).second)
83  return false;
84  T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
85  return true;
86 }
87 
89  {
90  std::lock_guard<std::mutex> Lock(Mu);
91  if (!adjust(T))
92  return;
93  Queue.push_back(std::move(T));
94  std::push_heap(Queue.begin(), Queue.end());
95  ++Stat.Enqueued;
96  notifyProgress();
97  }
98  CV.notify_all();
99 }
100 
101 void BackgroundQueue::append(std::vector<Task> Tasks) {
102  {
103  std::lock_guard<std::mutex> Lock(Mu);
104  for (Task &T : Tasks) {
105  if (!adjust(T))
106  continue;
107  Queue.push_back(std::move(T));
108  ++Stat.Enqueued;
109  }
110  std::make_heap(Queue.begin(), Queue.end());
111  notifyProgress();
112  }
113  CV.notify_all();
114 }
115 
116 void BackgroundQueue::boost(llvm::StringRef Tag, unsigned NewPriority) {
117  std::lock_guard<std::mutex> Lock(Mu);
118  unsigned &Boost = Boosts[Tag];
119  bool Increase = NewPriority > Boost;
120  Boost = NewPriority;
121  if (!Increase)
122  return; // existing tasks unaffected
123 
124  unsigned Changes = 0;
125  for (Task &T : Queue)
126  if (Tag == T.Tag && NewPriority > T.QueuePri) {
127  T.QueuePri = NewPriority;
128  ++Changes;
129  }
130  if (Changes)
131  std::make_heap(Queue.begin(), Queue.end());
132  // No need to signal, only rearranged items in the queue.
133 }
134 
136  llvm::Optional<double> TimeoutSeconds) {
137  std::unique_lock<std::mutex> Lock(Mu);
138  return wait(Lock, CV, timeoutSeconds(TimeoutSeconds),
139  [&] { return Queue.empty() && Stat.Active == 0; });
140 }
141 
142 void BackgroundQueue::notifyProgress() const {
143  dlog("Queue: {0}/{1} ({2} active). Last idle at {3}", Stat.Completed,
144  Stat.Enqueued, Stat.Active, Stat.LastIdle);
145  if (OnProgress)
146  OnProgress(Stat);
147 }
148 
149 } // namespace clangd
150 } // namespace clang
dlog
#define dlog(...)
Definition: Logger.h:102
clang::clangd::BackgroundQueue::Task
A work item on the thread pool's queue.
Definition: Background.h:72
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
Background.h
clang::clangd::BackgroundQueue::append
void append(std::vector< Task >)
Definition: BackgroundQueue.cpp:101
clang::clangd::BackgroundQueue::push
void push(Task)
Definition: BackgroundQueue.cpp:88
clang::clangd::BackgroundQueue::Task::ThreadPri
llvm::ThreadPriority ThreadPri
Definition: Background.h:76
clang::clangd::BackgroundQueue::work
void work(std::function< void()> OnIdle=nullptr)
Definition: BackgroundQueue.cpp:21
Changes
tooling::Replacements Changes
Definition: Format.cpp:110
clang::clangd::PreventStarvation
static std::atomic< bool > PreventStarvation
Definition: BackgroundQueue.cpp:15
clang::clangd::BackgroundQueue::Stats::LastIdle
unsigned LastIdle
Definition: Background.h:90
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::BackgroundQueue::stop
void stop()
Definition: BackgroundQueue.cpp:67
clang::clangd::BackgroundQueue::Stats::Completed
unsigned Completed
Definition: Background.h:89
clang::clangd::BackgroundQueue::boost
void boost(llvm::StringRef Tag, unsigned NewPriority)
Definition: BackgroundQueue.cpp:116
Logger.h
clang::clangd::BackgroundQueue::preventThreadStarvationInTests
static void preventThreadStarvationInTests()
Definition: BackgroundQueue.cpp:17
clang::clangd::BackgroundQueue::blockUntilIdleForTest
LLVM_NODISCARD bool blockUntilIdleForTest(llvm::Optional< double > TimeoutSeconds)
Definition: BackgroundQueue.cpp:135
clang::clangd::BackgroundQueue::Stats::Enqueued
unsigned Enqueued
Definition: Background.h:87
clang::clangd::BackgroundQueue::Stats::Active
unsigned Active
Definition: Background.h:88
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::clangd::BackgroundQueue::Task::Run
std::function< void()> Run
Definition: Background.h:75
Tag
HTMLTag Tag
Definition: HTMLGenerator.cpp:90