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 #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