clang-tools-extra/clangd/index/Background.h

   1 //===--- Background.h - Build an index in a background thread ----*- C++-*-===//
   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 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
  10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
  11
  12 #include "GlobalCompilationDatabase.h"
  13 #include "SourceCode.h"
  14 #include "index/BackgroundRebuild.h"
  15 #include "index/FileIndex.h"
  16 #include "index/Index.h"
  17 #include "index/Serialization.h"
  18 #include "support/Context.h"
  19 #include "support/MemoryTree.h"
  20 #include "support/Path.h"
  21 #include "support/Threading.h"
  22 #include "support/ThreadsafeFS.h"
  23 #include "clang/Tooling/CompilationDatabase.h"
  24 #include "llvm/ADT/StringMap.h"
  25 #include "llvm/Support/Threading.h"
  26 #include <atomic>
  27 #include <condition_variable>
  28 #include <deque>
  29 #include <mutex>
  30 #include <optional>
  31 #include <queue>
  32 #include <string>
  33 #include <thread>
  34 #include <vector>
  35
  36 namespace clang {
  37 namespace clangd {
  38
  39 // Handles storage and retrieval of index shards. Both store and load
  40 // operations can be called from multiple-threads concurrently.
  41 class BackgroundIndexStorage {
  42 public:
  43   virtual ~BackgroundIndexStorage() = default;
  44
  45   // Shards of the index are stored and retrieved independently, keyed by shard
  46   // identifier - in practice this is a source file name
  47   virtual llvm::Error storeShard(llvm::StringRef ShardIdentifier,
  48                                  IndexFileOut Shard) const = 0;
  49
  50   // Tries to load shard with given identifier, returns nullptr if shard
  51   // couldn't be loaded.
  52   virtual std::unique_ptr<IndexFileIn>
  53   loadShard(llvm::StringRef ShardIdentifier) const = 0;
  54
  55   // The factory provides storage for each File.
  56   // It keeps ownership of the storage instances, and should manage caching
  57   // itself. Factory must be threadsafe and never returns nullptr.
  58   using Factory = llvm::unique_function<BackgroundIndexStorage *(PathRef)>;
  59
  60   // Creates an Index Storage that saves shards into disk. Index storage uses
  61   // CDBDirectory + ".cache/clangd/index/" as the folder to save shards.
  62   // CDBDirectory is the first directory containing a CDB in parent directories
  63   // of a file, or user cache directory if none was found, e.g. stdlib headers.
  64   static Factory createDiskBackedStorageFactory(
  65       std::function<std::optional<ProjectInfo>(PathRef)> GetProjectInfo);
  66 };
  67
  68 // A priority queue of tasks which can be run on (external) worker threads.
  69 class BackgroundQueue {
  70 public:
  71   /// A work item on the thread pool's queue.
  72   struct Task {
  73     explicit Task(std::function<void()> Run) : Run(std::move(Run)) {}
  74
  75     std::function<void()> Run;
  76     llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Low;
  77     unsigned QueuePri = 0; // Higher-priority tasks will run first.
  78     std::string Tag;       // Allows priority to be boosted later.
  79     uint64_t Key = 0;      // If the key matches a previous task, drop this one.
  80                            // (in practice this means we never reindex a file).
  81
  82     bool operator<(const Task &O) const { return QueuePri < O.QueuePri; }
  83   };
  84
  85   // Describes the number of tasks processed by the queue.
  86   struct Stats {
  87     unsigned Enqueued = 0;  // Total number of tasks ever enqueued.
  88     unsigned Active = 0;    // Tasks being currently processed by a worker.
  89     unsigned Completed = 0; // Tasks that have been finished.
  90     unsigned LastIdle = 0;  // Number of completed tasks when last empty.
  91   };
  92
  93   BackgroundQueue(std::function<void(Stats)> OnProgress = nullptr)
  94       : OnProgress(OnProgress) {}
  95
  96   // Add tasks to the queue.
  97   void push(Task);
  98   void append(std::vector<Task>);
  99   // Boost priority of current and new tasks with matching Tag, if they are
 100   // lower priority.
 101   // Reducing the boost of a tag affects future tasks but not current ones.
 102   void boost(llvm::StringRef Tag, unsigned NewPriority);
 103
 104   // Process items on the queue until the queue is stopped.
 105   // If the queue becomes empty, OnIdle will be called (on one worker).
 106   void work(std::function<void()> OnIdle = nullptr);
 107
 108   // Stop processing new tasks, allowing all work() calls to return soon.
 109   void stop();
 110
 111   // Disables thread priority lowering to ensure progress on loaded systems.
 112   // Only affects tasks that run after the call.
 113   static void preventThreadStarvationInTests();
 114   [[nodiscard]] bool
 115   blockUntilIdleForTest(std::optional<double> TimeoutSeconds);
 116
 117 private:
 118   void notifyProgress() const; // Requires lock Mu
 119   bool adjust(Task &T);
 120
 121   std::mutex Mu;
 122   Stats Stat;
 123   std::condition_variable CV;
 124   bool ShouldStop = false;
 125   std::vector<Task> Queue; // max-heap
 126   llvm::StringMap<unsigned> Boosts;
 127   std::function<void(Stats)> OnProgress;
 128   llvm::DenseSet<uint64_t> SeenKeys;
 129 };
 130
 131 // Builds an in-memory index by by running the static indexer action over
 132 // all commands in a compilation database. Indexing happens in the background.
 133 // FIXME: it should watch for changes to files on disk.
 134 class BackgroundIndex : public SwapIndex {
 135 public:
 136   struct Options {
 137     // Arbitrary value to ensure some concurrency in tests.
 138     // In production an explicit value is specified.
 139     size_t ThreadPoolSize = 4;
 140     // Thread priority when indexing files.
 141     llvm::ThreadPriority IndexingPriority = llvm::ThreadPriority::Low;
 142     // Callback that provides notifications as indexing makes progress.
 143     std::function<void(BackgroundQueue::Stats)> OnProgress = nullptr;
 144     // Function called to obtain the Context to use while indexing the specified
 145     // file. Called with the empty string for other tasks.
 146     // (When called, the context from BackgroundIndex construction is active).
 147     std::function<Context(PathRef)> ContextProvider = nullptr;
 148   };
 149
 150   /// Creates a new background index and starts its threads.
 151   /// The current Context will be propagated to each worker thread.
 152   BackgroundIndex(const ThreadsafeFS &, const GlobalCompilationDatabase &CDB,
 153                   BackgroundIndexStorage::Factory IndexStorageFactory,
 154                   Options Opts);
 155   ~BackgroundIndex(); // Blocks while the current task finishes.
 156
 157   // Enqueue translation units for indexing.
 158   // The indexing happens in a background thread, so the symbols will be
 159   // available sometime later.
 160   void enqueue(const std::vector<std::string> &ChangedFiles) {
 161     Queue.push(changedFilesTask(ChangedFiles));
 162   }
 163
 164   /// Boosts priority of indexing related to Path.
 165   /// Typically used to index TUs when headers are opened.
 166   void boostRelated(llvm::StringRef Path);
 167
 168   // Cause background threads to stop after ther current task, any remaining
 169   // tasks will be discarded.
 170   void stop() {
 171     Rebuilder.shutdown();
 172     Queue.stop();
 173   }
 174
 175   // Wait until the queue is empty, to allow deterministic testing.
 176   [[nodiscard]] bool
 177   blockUntilIdleForTest(std::optional<double> TimeoutSeconds = 10) {
 178     return Queue.blockUntilIdleForTest(TimeoutSeconds);
 179   }
 180
 181   void profile(MemoryTree &MT) const;
 182
 183 private:
 184   /// Represents the state of a single file when indexing was performed.
 185   struct ShardVersion {
 186     FileDigest Digest{{0}};
 187     bool HadErrors = false;
 188   };
 189
 190   /// Given index results from a TU, only update symbols coming from files with
 191   /// different digests than \p ShardVersionsSnapshot. Also stores new index
 192   /// information on IndexStorage.
 193   void update(llvm::StringRef MainFile, IndexFileIn Index,
 194               const llvm::StringMap<ShardVersion> &ShardVersionsSnapshot,
 195               bool HadErrors);
 196
 197   // configuration
 198   const ThreadsafeFS &TFS;
 199   const GlobalCompilationDatabase &CDB;
 200   llvm::ThreadPriority IndexingPriority;
 201   std::function<Context(PathRef)> ContextProvider;
 202
 203   llvm::Error index(tooling::CompileCommand);
 204
 205   FileSymbols IndexedSymbols;
 206   BackgroundIndexRebuilder Rebuilder;
 207   llvm::StringMap<ShardVersion> ShardVersions; // Key is absolute file path.
 208   std::mutex ShardVersionsMu;
 209
 210   BackgroundIndexStorage::Factory IndexStorageFactory;
 211   // Tries to load shards for the MainFiles and their dependencies.
 212   std::vector<std::string> loadProject(std::vector<std::string> MainFiles);
 213
 214   BackgroundQueue::Task
 215   changedFilesTask(const std::vector<std::string> &ChangedFiles);
 216   BackgroundQueue::Task indexFileTask(std::string Path);
 217
 218   // from lowest to highest priority
 219   enum QueuePriority {
 220     IndexFile,
 221     IndexBoostedFile,
 222     LoadShards,
 223   };
 224   BackgroundQueue Queue;
 225   AsyncTaskRunner ThreadPool;
 226   GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
 227 };
 228
 229 } // namespace clangd
 230 } // namespace clang
 231
 232 #endif