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 17 void BackgroundQueue::preventThreadStarvationInTests() { 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 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. 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 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 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 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 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 151