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 "support/Trace.h" 24 #include "clang/Tooling/CompilationDatabase.h" 25 #include "llvm/ADT/StringMap.h" 26 #include "llvm/Support/Threading.h" 27 #include <atomic> 28 #include <condition_variable> 29 #include <deque> 30 #include <mutex> 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<llvm::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 { TaskTask73 explicit Task(std::function<void()> Run) : Run(std::move(Run)) {} 74 75 std::function<void()> Run; 76 llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Background; 77 unsigned QueuePri = 0; // Higher-priority tasks will run first. 78 std::string Tag; // Allows priority to be boosted later. 79 80 bool operator<(const Task &O) const { return QueuePri < O.QueuePri; } 81 }; 82 83 // Describes the number of tasks processed by the queue. 84 struct Stats { 85 unsigned Enqueued = 0; // Total number of tasks ever enqueued. 86 unsigned Active = 0; // Tasks being currently processed by a worker. 87 unsigned Completed = 0; // Tasks that have been finished. 88 unsigned LastIdle = 0; // Number of completed tasks when last empty. 89 }; 90 91 BackgroundQueue(std::function<void(Stats)> OnProgress = nullptr) OnProgress(OnProgress)92 : OnProgress(OnProgress) {} 93 94 // Add tasks to the queue. 95 void push(Task); 96 void append(std::vector<Task>); 97 // Boost priority of current and new tasks with matching Tag, if they are 98 // lower priority. 99 // Reducing the boost of a tag affects future tasks but not current ones. 100 void boost(llvm::StringRef Tag, unsigned NewPriority); 101 102 // Process items on the queue until the queue is stopped. 103 // If the queue becomes empty, OnIdle will be called (on one worker). 104 void work(std::function<void()> OnIdle = nullptr); 105 106 // Stop processing new tasks, allowing all work() calls to return soon. 107 void stop(); 108 109 // Disables thread priority lowering to ensure progress on loaded systems. 110 // Only affects tasks that run after the call. 111 static void preventThreadStarvationInTests(); 112 LLVM_NODISCARD bool 113 blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds); 114 115 private: 116 void notifyProgress() const; // Requires lock Mu 117 118 std::mutex Mu; 119 Stats Stat; 120 std::condition_variable CV; 121 bool ShouldStop = false; 122 std::vector<Task> Queue; // max-heap 123 llvm::StringMap<unsigned> Boosts; 124 std::function<void(Stats)> OnProgress; 125 }; 126 127 // Builds an in-memory index by by running the static indexer action over 128 // all commands in a compilation database. Indexing happens in the background. 129 // FIXME: it should watch for changes to files on disk. 130 class BackgroundIndex : public SwapIndex { 131 public: 132 struct Options { 133 // Arbitrary value to ensure some concurrency in tests. 134 // In production an explicit value is specified. 135 size_t ThreadPoolSize = 4; 136 // Callback that provides notifications as indexing makes progress. 137 std::function<void(BackgroundQueue::Stats)> OnProgress = nullptr; 138 // Function called to obtain the Context to use while indexing the specified 139 // file. Called with the empty string for other tasks. 140 // (When called, the context from BackgroundIndex construction is active). 141 std::function<Context(PathRef)> ContextProvider = nullptr; 142 // Whether to collect references to main-file-only symbols. 143 bool CollectMainFileRefs = false; 144 }; 145 146 /// Creates a new background index and starts its threads. 147 /// The current Context will be propagated to each worker thread. 148 BackgroundIndex(const ThreadsafeFS &, const GlobalCompilationDatabase &CDB, 149 BackgroundIndexStorage::Factory IndexStorageFactory, 150 Options Opts); 151 ~BackgroundIndex(); // Blocks while the current task finishes. 152 153 // Enqueue translation units for indexing. 154 // The indexing happens in a background thread, so the symbols will be 155 // available sometime later. enqueue(const std::vector<std::string> & ChangedFiles)156 void enqueue(const std::vector<std::string> &ChangedFiles) { 157 Queue.push(changedFilesTask(ChangedFiles)); 158 } 159 160 /// Boosts priority of indexing related to Path. 161 /// Typically used to index TUs when headers are opened. 162 void boostRelated(llvm::StringRef Path); 163 164 // Cause background threads to stop after ther current task, any remaining 165 // tasks will be discarded. stop()166 void stop() { 167 Rebuilder.shutdown(); 168 Queue.stop(); 169 } 170 171 // Wait until the queue is empty, to allow deterministic testing. 172 LLVM_NODISCARD bool 173 blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10) { 174 return Queue.blockUntilIdleForTest(TimeoutSeconds); 175 } 176 177 void profile(MemoryTree &MT) const; 178 179 private: 180 /// Represents the state of a single file when indexing was performed. 181 struct ShardVersion { 182 FileDigest Digest{{0}}; 183 bool HadErrors = false; 184 }; 185 186 /// Given index results from a TU, only update symbols coming from files with 187 /// different digests than \p ShardVersionsSnapshot. Also stores new index 188 /// information on IndexStorage. 189 void update(llvm::StringRef MainFile, IndexFileIn Index, 190 const llvm::StringMap<ShardVersion> &ShardVersionsSnapshot, 191 bool HadErrors); 192 193 // configuration 194 const ThreadsafeFS &TFS; 195 const GlobalCompilationDatabase &CDB; 196 std::function<Context(PathRef)> ContextProvider; 197 bool CollectMainFileRefs; 198 199 llvm::Error index(tooling::CompileCommand); 200 201 FileSymbols IndexedSymbols; 202 BackgroundIndexRebuilder Rebuilder; 203 llvm::StringMap<ShardVersion> ShardVersions; // Key is absolute file path. 204 std::mutex ShardVersionsMu; 205 206 BackgroundIndexStorage::Factory IndexStorageFactory; 207 // Tries to load shards for the MainFiles and their dependencies. 208 std::vector<std::string> loadProject(std::vector<std::string> MainFiles); 209 210 BackgroundQueue::Task 211 changedFilesTask(const std::vector<std::string> &ChangedFiles); 212 BackgroundQueue::Task indexFileTask(std::string Path); 213 214 // from lowest to highest priority 215 enum QueuePriority { 216 IndexFile, 217 IndexBoostedFile, 218 LoadShards, 219 }; 220 BackgroundQueue Queue; 221 AsyncTaskRunner ThreadPool; 222 GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged; 223 }; 224 225 } // namespace clangd 226 } // namespace clang 227 228 #endif 229