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