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
preventThreadStarvationInTests()17 void BackgroundQueue::preventThreadStarvationInTests() {
18 PreventStarvation.store(true);
19 }
20
work(std::function<void ()> OnIdle)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
stop()67 void BackgroundQueue::stop() {
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.
adjust(Task & T)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
push(Task T)88 void BackgroundQueue::push(Task T) {
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
append(std::vector<Task> Tasks)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
boost(llvm::StringRef Tag,unsigned NewPriority)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
blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds)135 bool BackgroundQueue::blockUntilIdleForTest(
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
notifyProgress() const142 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
151