1//===- DependencyScanningFilesystem.cpp - Optimized Scanning FS -----------===//
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#include "clang/DependencyScanning/DependencyScanningFilesystem.h"
10#include "llvm/Support/MemoryBuffer.h"
11#include "llvm/Support/Threading.h"
12#include <optional>
13
14using namespace clang;
15using namespace dependencies;
16
17llvm::ErrorOr<DependencyScanningWorkerFilesystem::TentativeEntry>
18DependencyScanningWorkerFilesystem::readFile(StringRef Filename) {
19 // Load the file and its content from the file system.
20 auto MaybeFile = getUnderlyingFS().openFileForRead(Path: Filename);
21 if (!MaybeFile)
22 return MaybeFile.getError();
23 auto File = std::move(*MaybeFile);
24
25 auto MaybeStat = File->status();
26 if (!MaybeStat)
27 return MaybeStat.getError();
28 auto Stat = std::move(*MaybeStat);
29
30 auto MaybeBuffer = File->getBuffer(Name: Stat.getName());
31 if (!MaybeBuffer)
32 return MaybeBuffer.getError();
33 auto Buffer = std::move(*MaybeBuffer);
34
35 // If the file size changed between read and stat, pretend it didn't.
36 if (Stat.getSize() != Buffer->getBufferSize())
37 Stat = llvm::vfs::Status::copyWithNewSize(In: Stat, NewSize: Buffer->getBufferSize());
38
39 return TentativeEntry(Stat, std::move(Buffer));
40}
41
42bool DependencyScanningWorkerFilesystem::ensureDirectiveTokensArePopulated(
43 EntryRef Ref) {
44 auto &Entry = Ref.Entry;
45
46 if (Entry.isError() || Entry.isDirectory())
47 return false;
48
49 CachedFileContents *Contents = Entry.getCachedContents();
50 assert(Contents && "contents not initialized");
51
52 // Double-checked locking.
53 if (Contents->DepDirectives.load())
54 return true;
55
56 std::lock_guard<std::mutex> GuardLock(Contents->ValueLock);
57
58 // Double-checked locking.
59 if (Contents->DepDirectives.load())
60 return true;
61
62 SmallVector<dependency_directives_scan::Directive, 64> Directives;
63 // Scan the file for preprocessor directives that might affect the
64 // dependencies.
65 if (scanSourceForDependencyDirectives(Input: Contents->Original->getBuffer(),
66 Tokens&: Contents->DepDirectiveTokens,
67 Directives)) {
68 Contents->DepDirectiveTokens.clear();
69 // FIXME: Propagate the diagnostic if desired by the client.
70 Contents->DepDirectives.store(p: new std::optional<DependencyDirectivesTy>());
71 return false;
72 }
73
74 // This function performed double-checked locking using `DepDirectives`.
75 // Assigning it must be the last thing this function does, otherwise other
76 // threads may skip the critical section (`DepDirectives != nullptr`), leading
77 // to a data race.
78 Contents->DepDirectives.store(
79 p: new std::optional<DependencyDirectivesTy>(std::move(Directives)));
80 return true;
81}
82
83DependencyScanningFilesystemSharedCache::
84 DependencyScanningFilesystemSharedCache() {
85 // This heuristic was chosen using a empirical testing on a
86 // reasonably high core machine (iMacPro 18 cores / 36 threads). The cache
87 // sharding gives a performance edge by reducing the lock contention.
88 // FIXME: A better heuristic might also consider the OS to account for
89 // the different cost of lock contention on different OSes.
90 NumShards =
91 std::max(a: 2u, b: llvm::hardware_concurrency().compute_thread_count() / 4);
92 CacheShards = std::make_unique<CacheShard[]>(num: NumShards);
93}
94
95DependencyScanningFilesystemSharedCache::CacheShard &
96DependencyScanningFilesystemSharedCache::getShardForFilename(
97 StringRef Filename) const {
98 assert(llvm::sys::path::is_absolute_gnu(Filename));
99 return CacheShards[llvm::hash_value(S: Filename) % NumShards];
100}
101
102DependencyScanningFilesystemSharedCache::CacheShard &
103DependencyScanningFilesystemSharedCache::getShardForUID(
104 llvm::sys::fs::UniqueID UID) const {
105 auto Hash = llvm::hash_combine(args: UID.getDevice(), args: UID.getFile());
106 return CacheShards[Hash % NumShards];
107}
108
109std::vector<DependencyScanningFilesystemSharedCache::OutOfDateEntry>
110DependencyScanningFilesystemSharedCache::getOutOfDateEntries(
111 llvm::vfs::FileSystem &UnderlyingFS) const {
112 // Iterate through all shards and look for cached stat errors.
113 std::vector<OutOfDateEntry> InvalidDiagInfo;
114 for (unsigned i = 0; i < NumShards; i++) {
115 const CacheShard &Shard = CacheShards[i];
116 std::lock_guard<std::mutex> LockGuard(Shard.CacheLock);
117 for (const auto &[Path, CachedPair] : Shard.CacheByFilename) {
118 const CachedFileSystemEntry *Entry = CachedPair.first;
119 llvm::ErrorOr<llvm::vfs::Status> Status = UnderlyingFS.status(Path);
120 if (Status) {
121 if (Entry->getError()) {
122 // This is the case where we have cached the non-existence
123 // of the file at Path first, and a file at the path is created
124 // later. The cache entry is not invalidated (as we have no good
125 // way to do it now), which may lead to missing file build errors.
126 InvalidDiagInfo.emplace_back(args: Path.data());
127 } else {
128 llvm::vfs::Status CachedStatus = Entry->getStatus();
129 if (Status->getType() == llvm::sys::fs::file_type::regular_file &&
130 Status->getType() == CachedStatus.getType()) {
131 // We only check regular files. Directory files sizes could change
132 // due to content changes, and reporting directory size changes can
133 // lead to false positives.
134 // TODO: At the moment, we do not detect symlinks to files whose
135 // size may change. We need to decide if we want to detect cached
136 // symlink size changes. We can also expand this to detect file
137 // type changes.
138 uint64_t CachedSize = CachedStatus.getSize();
139 uint64_t ActualSize = Status->getSize();
140 if (CachedSize != ActualSize) {
141 // This is the case where the cached file has a different size
142 // from the actual file that comes from the underlying FS.
143 InvalidDiagInfo.emplace_back(args: Path.data(), args&: CachedSize, args&: ActualSize);
144 }
145 }
146 }
147 }
148 }
149 }
150 return InvalidDiagInfo;
151}
152
153const CachedFileSystemEntry *
154DependencyScanningFilesystemSharedCache::CacheShard::findEntryByFilename(
155 StringRef Filename) const {
156 assert(llvm::sys::path::is_absolute_gnu(Filename));
157 std::lock_guard<std::mutex> LockGuard(CacheLock);
158 auto It = CacheByFilename.find(Key: Filename);
159 return It == CacheByFilename.end() ? nullptr : It->getValue().first;
160}
161
162const CachedFileSystemEntry *
163DependencyScanningFilesystemSharedCache::CacheShard::findEntryByUID(
164 llvm::sys::fs::UniqueID UID) const {
165 std::lock_guard<std::mutex> LockGuard(CacheLock);
166 auto It = EntriesByUID.find(Val: UID);
167 return It == EntriesByUID.end() ? nullptr : It->getSecond();
168}
169
170const CachedFileSystemEntry &
171DependencyScanningFilesystemSharedCache::CacheShard::
172 getOrEmplaceEntryForFilename(StringRef Filename,
173 llvm::ErrorOr<llvm::vfs::Status> Stat) {
174 std::lock_guard<std::mutex> LockGuard(CacheLock);
175 auto [It, Inserted] = CacheByFilename.insert(KV: {Filename, {nullptr, nullptr}});
176 auto &[CachedEntry, CachedRealPath] = It->getValue();
177 if (!CachedEntry) {
178 // The entry is not present in the shared cache. Either the cache doesn't
179 // know about the file at all, or it only knows about its real path.
180 assert((Inserted || CachedRealPath) && "existing file with empty pair");
181 CachedEntry =
182 new (EntryStorage.Allocate()) CachedFileSystemEntry(std::move(Stat));
183 }
184 return *CachedEntry;
185}
186
187const CachedFileSystemEntry &
188DependencyScanningFilesystemSharedCache::CacheShard::getOrEmplaceEntryForUID(
189 llvm::sys::fs::UniqueID UID, llvm::vfs::Status Stat,
190 std::unique_ptr<llvm::MemoryBuffer> Contents) {
191 std::lock_guard<std::mutex> LockGuard(CacheLock);
192 auto [It, Inserted] = EntriesByUID.try_emplace(Key: UID);
193 auto &CachedEntry = It->getSecond();
194 if (Inserted) {
195 CachedFileContents *StoredContents = nullptr;
196 if (Contents)
197 StoredContents = new (ContentsStorage.Allocate())
198 CachedFileContents(std::move(Contents));
199 CachedEntry = new (EntryStorage.Allocate())
200 CachedFileSystemEntry(std::move(Stat), StoredContents);
201 }
202 return *CachedEntry;
203}
204
205const CachedFileSystemEntry &
206DependencyScanningFilesystemSharedCache::CacheShard::
207 getOrInsertEntryForFilename(StringRef Filename,
208 const CachedFileSystemEntry &Entry) {
209 std::lock_guard<std::mutex> LockGuard(CacheLock);
210 auto [It, Inserted] = CacheByFilename.insert(KV: {Filename, {&Entry, nullptr}});
211 auto &[CachedEntry, CachedRealPath] = It->getValue();
212 if (!Inserted || !CachedEntry)
213 CachedEntry = &Entry;
214 return *CachedEntry;
215}
216
217const CachedRealPath *
218DependencyScanningFilesystemSharedCache::CacheShard::findRealPathByFilename(
219 StringRef Filename) const {
220 assert(llvm::sys::path::is_absolute_gnu(Filename));
221 std::lock_guard<std::mutex> LockGuard(CacheLock);
222 auto It = CacheByFilename.find(Key: Filename);
223 return It == CacheByFilename.end() ? nullptr : It->getValue().second;
224}
225
226const CachedRealPath &DependencyScanningFilesystemSharedCache::CacheShard::
227 getOrEmplaceRealPathForFilename(StringRef Filename,
228 llvm::ErrorOr<llvm::StringRef> RealPath) {
229 std::lock_guard<std::mutex> LockGuard(CacheLock);
230
231 const CachedRealPath *&StoredRealPath = CacheByFilename[Filename].second;
232 if (!StoredRealPath) {
233 auto OwnedRealPath = [&]() -> CachedRealPath {
234 if (!RealPath)
235 return RealPath.getError();
236 return RealPath->str();
237 }();
238
239 StoredRealPath = new (RealPathStorage.Allocate())
240 CachedRealPath(std::move(OwnedRealPath));
241 }
242
243 return *StoredRealPath;
244}
245
246bool DependencyScanningWorkerFilesystem::shouldBypass(StringRef Path) const {
247 return BypassedPathPrefix && Path.starts_with(Prefix: *BypassedPathPrefix);
248}
249
250DependencyScanningWorkerFilesystem::DependencyScanningWorkerFilesystem(
251 DependencyScanningFilesystemSharedCache &SharedCache,
252 IntrusiveRefCntPtr<llvm::vfs::FileSystem> FS)
253 : llvm::RTTIExtends<DependencyScanningWorkerFilesystem,
254 llvm::vfs::ProxyFileSystem>(std::move(FS)),
255 SharedCache(SharedCache),
256 WorkingDirForCacheLookup(llvm::errc::invalid_argument) {
257 updateWorkingDirForCacheLookup();
258}
259
260const CachedFileSystemEntry &
261DependencyScanningWorkerFilesystem::getOrEmplaceSharedEntryForUID(
262 TentativeEntry TEntry) {
263 auto &Shard = SharedCache.getShardForUID(UID: TEntry.Status.getUniqueID());
264 return Shard.getOrEmplaceEntryForUID(UID: TEntry.Status.getUniqueID(),
265 Stat: std::move(TEntry.Status),
266 Contents: std::move(TEntry.Contents));
267}
268
269const CachedFileSystemEntry *
270DependencyScanningWorkerFilesystem::findEntryByFilenameWithWriteThrough(
271 StringRef Filename) {
272 if (const auto *Entry = LocalCache.findEntryByFilename(Filename))
273 return Entry;
274 auto &Shard = SharedCache.getShardForFilename(Filename);
275 if (const auto *Entry = Shard.findEntryByFilename(Filename))
276 return &LocalCache.insertEntryForFilename(Filename, Entry: *Entry);
277 return nullptr;
278}
279
280llvm::ErrorOr<const CachedFileSystemEntry &>
281DependencyScanningWorkerFilesystem::computeAndStoreResult(
282 StringRef OriginalFilename, StringRef FilenameForLookup) {
283 llvm::ErrorOr<llvm::vfs::Status> Stat =
284 getUnderlyingFS().status(Path: OriginalFilename);
285 if (!Stat) {
286 const auto &Entry =
287 getOrEmplaceSharedEntryForFilename(Filename: FilenameForLookup, EC: Stat.getError());
288 return insertLocalEntryForFilename(Filename: FilenameForLookup, Entry);
289 }
290
291 if (const auto *Entry = findSharedEntryByUID(Stat: *Stat))
292 return insertLocalEntryForFilename(Filename: FilenameForLookup, Entry: *Entry);
293
294 auto TEntry =
295 Stat->isDirectory() ? TentativeEntry(*Stat) : readFile(Filename: OriginalFilename);
296
297 const CachedFileSystemEntry *SharedEntry = [&]() {
298 if (TEntry) {
299 const auto &UIDEntry = getOrEmplaceSharedEntryForUID(TEntry: std::move(*TEntry));
300 return &getOrInsertSharedEntryForFilename(Filename: FilenameForLookup, Entry: UIDEntry);
301 }
302 return &getOrEmplaceSharedEntryForFilename(Filename: FilenameForLookup,
303 EC: TEntry.getError());
304 }();
305
306 return insertLocalEntryForFilename(Filename: FilenameForLookup, Entry: *SharedEntry);
307}
308
309llvm::ErrorOr<EntryRef>
310DependencyScanningWorkerFilesystem::getOrCreateFileSystemEntry(
311 StringRef OriginalFilename) {
312 SmallString<256> PathBuf;
313 auto FilenameForLookup = tryGetFilenameForLookup(OriginalFilename, PathBuf);
314 if (!FilenameForLookup)
315 return FilenameForLookup.getError();
316
317 if (const auto *Entry =
318 findEntryByFilenameWithWriteThrough(Filename: *FilenameForLookup))
319 return EntryRef(OriginalFilename, *Entry).unwrapError();
320 auto MaybeEntry = computeAndStoreResult(OriginalFilename, FilenameForLookup: *FilenameForLookup);
321 if (!MaybeEntry)
322 return MaybeEntry.getError();
323 return EntryRef(OriginalFilename, *MaybeEntry).unwrapError();
324}
325
326llvm::ErrorOr<llvm::vfs::Status>
327DependencyScanningWorkerFilesystem::status(const Twine &Path) {
328 SmallString<256> OwnedFilename;
329 StringRef Filename = Path.toStringRef(Out&: OwnedFilename);
330
331 if (shouldBypass(Path: Filename))
332 return getUnderlyingFS().status(Path);
333
334 llvm::ErrorOr<EntryRef> Result = getOrCreateFileSystemEntry(OriginalFilename: Filename);
335 if (!Result)
336 return Result.getError();
337 return Result->getStatus();
338}
339
340bool DependencyScanningWorkerFilesystem::exists(const Twine &Path) {
341 // While some VFS overlay filesystems may implement more-efficient
342 // mechanisms for `exists` queries, `DependencyScanningWorkerFilesystem`
343 // typically wraps `RealFileSystem` which does not specialize `exists`,
344 // so it is not likely to benefit from such optimizations. Instead,
345 // it is more-valuable to have this query go through the
346 // cached-`status` code-path of the `DependencyScanningWorkerFilesystem`.
347 llvm::ErrorOr<llvm::vfs::Status> Status = status(Path);
348 return Status && Status->exists();
349}
350
351namespace {
352
353/// The VFS that is used by clang consumes the \c CachedFileSystemEntry using
354/// this subclass.
355class DepScanFile final : public llvm::vfs::File {
356public:
357 DepScanFile(std::unique_ptr<llvm::MemoryBuffer> Buffer,
358 llvm::vfs::Status Stat)
359 : Buffer(std::move(Buffer)), Stat(std::move(Stat)) {}
360
361 static llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>> create(EntryRef Entry);
362
363 llvm::ErrorOr<llvm::vfs::Status> status() override { return Stat; }
364
365 llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
366 getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
367 bool IsVolatile) override {
368 return llvm::MemoryBuffer::getMemBuffer(Ref: Buffer->getMemBufferRef(),
369 RequiresNullTerminator);
370 }
371
372 std::error_code close() override { return {}; }
373
374private:
375 std::unique_ptr<llvm::MemoryBuffer> Buffer;
376 llvm::vfs::Status Stat;
377};
378
379} // end anonymous namespace
380
381llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>
382DepScanFile::create(EntryRef Entry) {
383 assert(!Entry.isError() && "error");
384
385 if (Entry.isDirectory())
386 return std::make_error_code(e: std::errc::is_a_directory);
387
388 auto Result = std::make_unique<DepScanFile>(
389 args: llvm::MemoryBuffer::getMemBuffer(InputData: Entry.getContents(),
390 BufferName: Entry.getStatus().getName(),
391 /*RequiresNullTerminator=*/false),
392 args: Entry.getStatus());
393
394 return llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>(
395 std::unique_ptr<llvm::vfs::File>(std::move(Result)));
396}
397
398llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>
399DependencyScanningWorkerFilesystem::openFileForRead(const Twine &Path) {
400 SmallString<256> OwnedFilename;
401 StringRef Filename = Path.toStringRef(Out&: OwnedFilename);
402
403 if (shouldBypass(Path: Filename))
404 return getUnderlyingFS().openFileForRead(Path);
405
406 llvm::ErrorOr<EntryRef> Result = getOrCreateFileSystemEntry(OriginalFilename: Filename);
407 if (!Result)
408 return Result.getError();
409 return DepScanFile::create(Entry: Result.get());
410}
411
412std::error_code
413DependencyScanningWorkerFilesystem::getRealPath(const Twine &Path,
414 SmallVectorImpl<char> &Output) {
415 SmallString<256> OwnedFilename;
416 StringRef OriginalFilename = Path.toStringRef(Out&: OwnedFilename);
417
418 if (shouldBypass(Path: OriginalFilename))
419 return getUnderlyingFS().getRealPath(Path, Output);
420
421 SmallString<256> PathBuf;
422 auto FilenameForLookup = tryGetFilenameForLookup(OriginalFilename, PathBuf);
423 if (!FilenameForLookup)
424 return FilenameForLookup.getError();
425
426 auto HandleCachedRealPath =
427 [&Output](const CachedRealPath &RealPath) -> std::error_code {
428 if (!RealPath)
429 return RealPath.getError();
430 Output.assign(in_start: RealPath->begin(), in_end: RealPath->end());
431 return {};
432 };
433
434 // If we already have the result in local cache, no work required.
435 if (const auto *RealPath =
436 LocalCache.findRealPathByFilename(Filename: *FilenameForLookup))
437 return HandleCachedRealPath(*RealPath);
438
439 // If we have the result in the shared cache, cache it locally.
440 auto &Shard = SharedCache.getShardForFilename(Filename: *FilenameForLookup);
441 if (const auto *ShardRealPath =
442 Shard.findRealPathByFilename(Filename: *FilenameForLookup)) {
443 const auto &RealPath = LocalCache.insertRealPathForFilename(
444 Filename: *FilenameForLookup, RealPath: *ShardRealPath);
445 return HandleCachedRealPath(RealPath);
446 }
447
448 // If we don't know the real path, compute it...
449 std::error_code EC = getUnderlyingFS().getRealPath(Path: OriginalFilename, Output);
450 llvm::ErrorOr<llvm::StringRef> ComputedRealPath = EC;
451 if (!EC)
452 ComputedRealPath = StringRef{Output.data(), Output.size()};
453
454 // ...and try to write it into the shared cache. In case some other thread won
455 // this race and already wrote its own result there, just adopt it. Write
456 // whatever is in the shared cache into the local one.
457 const auto &RealPath = Shard.getOrEmplaceRealPathForFilename(
458 Filename: *FilenameForLookup, RealPath: ComputedRealPath);
459 return HandleCachedRealPath(
460 LocalCache.insertRealPathForFilename(Filename: *FilenameForLookup, RealPath));
461}
462
463std::error_code DependencyScanningWorkerFilesystem::setCurrentWorkingDirectory(
464 const Twine &Path) {
465 std::error_code EC = ProxyFileSystem::setCurrentWorkingDirectory(Path);
466 updateWorkingDirForCacheLookup();
467 return EC;
468}
469
470void DependencyScanningWorkerFilesystem::updateWorkingDirForCacheLookup() {
471 llvm::ErrorOr<std::string> CWD =
472 getUnderlyingFS().getCurrentWorkingDirectory();
473 if (!CWD) {
474 WorkingDirForCacheLookup = CWD.getError();
475 } else if (!llvm::sys::path::is_absolute_gnu(path: *CWD)) {
476 WorkingDirForCacheLookup = llvm::errc::invalid_argument;
477 } else {
478 WorkingDirForCacheLookup = *CWD;
479 }
480 assert(!WorkingDirForCacheLookup ||
481 llvm::sys::path::is_absolute_gnu(*WorkingDirForCacheLookup));
482}
483
484llvm::ErrorOr<StringRef>
485DependencyScanningWorkerFilesystem::tryGetFilenameForLookup(
486 StringRef OriginalFilename, llvm::SmallVectorImpl<char> &PathBuf) const {
487 StringRef FilenameForLookup;
488 if (llvm::sys::path::is_absolute_gnu(path: OriginalFilename)) {
489 FilenameForLookup = OriginalFilename;
490 } else if (!WorkingDirForCacheLookup) {
491 return WorkingDirForCacheLookup.getError();
492 } else {
493 StringRef RelFilename = OriginalFilename;
494 RelFilename.consume_front(Prefix: "./");
495 PathBuf.assign(in_start: WorkingDirForCacheLookup->begin(),
496 in_end: WorkingDirForCacheLookup->end());
497 llvm::sys::path::append(path&: PathBuf, a: RelFilename);
498 FilenameForLookup = StringRef{PathBuf.begin(), PathBuf.size()};
499 }
500 assert(llvm::sys::path::is_absolute_gnu(FilenameForLookup));
501 return FilenameForLookup;
502}
503
504const char DependencyScanningWorkerFilesystem::ID = 0;
505