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