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