• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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