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
13namespace clang {
14namespace clangd {
15
16static std::atomic<bool> PreventStarvation = {false};
17
18void BackgroundQueue::preventThreadStarvationInTests() {
19 PreventStarvation.store(i: true);
20}
21
22void 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&: Lock, p: [&] { return ShouldStop || !Queue.empty(); });
28 if (ShouldStop) {
29 Queue.clear();
30 CV.notify_all();
31 return;
32 }
33 ++Stat.Active;
34 std::pop_heap(first: Queue.begin(), last: 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
68void 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.
77bool 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(V: T.Key).second)
84 return false;
85 T.QueuePri = std::max(a: T.QueuePri, b: Boosts.lookup(Key: T.Tag));
86 return true;
87}
88
89void BackgroundQueue::push(Task T) {
90 {
91 std::lock_guard<std::mutex> Lock(Mu);
92 if (!adjust(T))
93 return;
94 Queue.push_back(x: std::move(T));
95 std::push_heap(first: Queue.begin(), last: Queue.end());
96 ++Stat.Enqueued;
97 notifyProgress();
98 }
99 CV.notify_all();
100}
101
102void 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(x: std::move(T));
109 ++Stat.Enqueued;
110 }
111 std::make_heap(first: Queue.begin(), last: Queue.end());
112 notifyProgress();
113 }
114 CV.notify_all();
115}
116
117void 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(first: Queue.begin(), last: Queue.end());
133 // No need to signal, only rearranged items in the queue.
134}
135
136bool BackgroundQueue::blockUntilIdleForTest(
137 std::optional<double> TimeoutSeconds) {
138 std::unique_lock<std::mutex> Lock(Mu);
139 return wait(Lock, CV, D: timeoutSeconds(Seconds: TimeoutSeconds),
140 F: [&] { return Queue.empty() && Stat.Active == 0; });
141}
142
143void 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

source code of clang-tools-extra/clangd/index/BackgroundQueue.cpp