| 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 |
|
| 18 |
void BackgroundQueue::preventThreadStarvationInTests() { |
| 19 |
PreventStarvation.store(true); |
| 20 |
} |
| 21 |
|
| 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 |
|
| 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. |
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 143 |
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 |