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