clang-tools-extra/clangd/index/BackgroundQueue.cpp

   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