506 lines · cpp
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-exception6//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(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(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(Stat, 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 the65 // dependencies.66 if (scanSourceForDependencyDirectives(Contents->Original->getBuffer(),67 Contents->DepDirectiveTokens,68 Directives)) {69 Contents->DepDirectiveTokens.clear();70 // FIXME: Propagate the diagnostic if desired by the client.71 Contents->DepDirectives.store(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 other77 // threads may skip the critical section (`DepDirectives != nullptr`), leading78 // to a data race.79 Contents->DepDirectives.store(80 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 a87 // reasonably high core machine (iMacPro 18 cores / 36 threads). The cache88 // sharding gives a performance edge by reducing the lock contention.89 // FIXME: A better heuristic might also consider the OS to account for90 // the different cost of lock contention on different OSes.91 NumShards =92 std::max(2u, llvm::hardware_concurrency().compute_thread_count() / 4);93 CacheShards = std::make_unique<CacheShard[]>(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(Filename) % NumShards];101}102 103DependencyScanningFilesystemSharedCache::CacheShard &104DependencyScanningFilesystemSharedCache::getShardForUID(105 llvm::sys::fs::UniqueID UID) const {106 auto Hash = llvm::hash_combine(UID.getDevice(), 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 llvm::ErrorOr<llvm::vfs::Status> Status = UnderlyingFS.status(Path);121 if (Status) {122 if (Entry->getError()) {123 // This is the case where we have cached the non-existence124 // of the file at Path first, and a file at the path is created125 // later. The cache entry is not invalidated (as we have no good126 // way to do it now), which may lead to missing file build errors.127 InvalidDiagInfo.emplace_back(Path.data());128 } else {129 llvm::vfs::Status CachedStatus = Entry->getStatus();130 if (Status->getType() == llvm::sys::fs::file_type::regular_file &&131 Status->getType() == CachedStatus.getType()) {132 // We only check regular files. Directory files sizes could change133 // due to content changes, and reporting directory size changes can134 // lead to false positives.135 // TODO: At the moment, we do not detect symlinks to files whose136 // size may change. We need to decide if we want to detect cached137 // symlink size changes. We can also expand this to detect file138 // type changes.139 uint64_t CachedSize = CachedStatus.getSize();140 uint64_t ActualSize = Status->getSize();141 if (CachedSize != ActualSize) {142 // This is the case where the cached file has a different size143 // from the actual file that comes from the underlying FS.144 InvalidDiagInfo.emplace_back(Path.data(), CachedSize, ActualSize);145 }146 }147 }148 }149 }150 }151 return InvalidDiagInfo;152}153 154const CachedFileSystemEntry *155DependencyScanningFilesystemSharedCache::CacheShard::findEntryByFilename(156 StringRef Filename) const {157 assert(llvm::sys::path::is_absolute_gnu(Filename));158 std::lock_guard<std::mutex> LockGuard(CacheLock);159 auto It = CacheByFilename.find(Filename);160 return It == CacheByFilename.end() ? nullptr : It->getValue().first;161}162 163const CachedFileSystemEntry *164DependencyScanningFilesystemSharedCache::CacheShard::findEntryByUID(165 llvm::sys::fs::UniqueID UID) const {166 std::lock_guard<std::mutex> LockGuard(CacheLock);167 auto It = EntriesByUID.find(UID);168 return It == EntriesByUID.end() ? nullptr : It->getSecond();169}170 171const CachedFileSystemEntry &172DependencyScanningFilesystemSharedCache::CacheShard::173 getOrEmplaceEntryForFilename(StringRef Filename,174 llvm::ErrorOr<llvm::vfs::Status> Stat) {175 std::lock_guard<std::mutex> LockGuard(CacheLock);176 auto [It, Inserted] = CacheByFilename.insert({Filename, {nullptr, nullptr}});177 auto &[CachedEntry, CachedRealPath] = It->getValue();178 if (!CachedEntry) {179 // The entry is not present in the shared cache. Either the cache doesn't180 // know about the file at all, or it only knows about its real path.181 assert((Inserted || CachedRealPath) && "existing file with empty pair");182 CachedEntry =183 new (EntryStorage.Allocate()) CachedFileSystemEntry(std::move(Stat));184 }185 return *CachedEntry;186}187 188const CachedFileSystemEntry &189DependencyScanningFilesystemSharedCache::CacheShard::getOrEmplaceEntryForUID(190 llvm::sys::fs::UniqueID UID, llvm::vfs::Status Stat,191 std::unique_ptr<llvm::MemoryBuffer> Contents) {192 std::lock_guard<std::mutex> LockGuard(CacheLock);193 auto [It, Inserted] = EntriesByUID.try_emplace(UID);194 auto &CachedEntry = It->getSecond();195 if (Inserted) {196 CachedFileContents *StoredContents = nullptr;197 if (Contents)198 StoredContents = new (ContentsStorage.Allocate())199 CachedFileContents(std::move(Contents));200 CachedEntry = new (EntryStorage.Allocate())201 CachedFileSystemEntry(std::move(Stat), StoredContents);202 }203 return *CachedEntry;204}205 206const CachedFileSystemEntry &207DependencyScanningFilesystemSharedCache::CacheShard::208 getOrInsertEntryForFilename(StringRef Filename,209 const CachedFileSystemEntry &Entry) {210 std::lock_guard<std::mutex> LockGuard(CacheLock);211 auto [It, Inserted] = CacheByFilename.insert({Filename, {&Entry, nullptr}});212 auto &[CachedEntry, CachedRealPath] = It->getValue();213 if (!Inserted || !CachedEntry)214 CachedEntry = &Entry;215 return *CachedEntry;216}217 218const CachedRealPath *219DependencyScanningFilesystemSharedCache::CacheShard::findRealPathByFilename(220 StringRef Filename) const {221 assert(llvm::sys::path::is_absolute_gnu(Filename));222 std::lock_guard<std::mutex> LockGuard(CacheLock);223 auto It = CacheByFilename.find(Filename);224 return It == CacheByFilename.end() ? nullptr : It->getValue().second;225}226 227const CachedRealPath &DependencyScanningFilesystemSharedCache::CacheShard::228 getOrEmplaceRealPathForFilename(StringRef Filename,229 llvm::ErrorOr<llvm::StringRef> RealPath) {230 std::lock_guard<std::mutex> LockGuard(CacheLock);231 232 const CachedRealPath *&StoredRealPath = CacheByFilename[Filename].second;233 if (!StoredRealPath) {234 auto OwnedRealPath = [&]() -> CachedRealPath {235 if (!RealPath)236 return RealPath.getError();237 return RealPath->str();238 }();239 240 StoredRealPath = new (RealPathStorage.Allocate())241 CachedRealPath(std::move(OwnedRealPath));242 }243 244 return *StoredRealPath;245}246 247bool DependencyScanningWorkerFilesystem::shouldBypass(StringRef Path) const {248 return BypassedPathPrefix && Path.starts_with(*BypassedPathPrefix);249}250 251DependencyScanningWorkerFilesystem::DependencyScanningWorkerFilesystem(252 DependencyScanningFilesystemSharedCache &SharedCache,253 IntrusiveRefCntPtr<llvm::vfs::FileSystem> FS)254 : llvm::RTTIExtends<DependencyScanningWorkerFilesystem,255 llvm::vfs::ProxyFileSystem>(std::move(FS)),256 SharedCache(SharedCache),257 WorkingDirForCacheLookup(llvm::errc::invalid_argument) {258 updateWorkingDirForCacheLookup();259}260 261const CachedFileSystemEntry &262DependencyScanningWorkerFilesystem::getOrEmplaceSharedEntryForUID(263 TentativeEntry TEntry) {264 auto &Shard = SharedCache.getShardForUID(TEntry.Status.getUniqueID());265 return Shard.getOrEmplaceEntryForUID(TEntry.Status.getUniqueID(),266 std::move(TEntry.Status),267 std::move(TEntry.Contents));268}269 270const CachedFileSystemEntry *271DependencyScanningWorkerFilesystem::findEntryByFilenameWithWriteThrough(272 StringRef Filename) {273 if (const auto *Entry = LocalCache.findEntryByFilename(Filename))274 return Entry;275 auto &Shard = SharedCache.getShardForFilename(Filename);276 if (const auto *Entry = Shard.findEntryByFilename(Filename))277 return &LocalCache.insertEntryForFilename(Filename, *Entry);278 return nullptr;279}280 281llvm::ErrorOr<const CachedFileSystemEntry &>282DependencyScanningWorkerFilesystem::computeAndStoreResult(283 StringRef OriginalFilename, StringRef FilenameForLookup) {284 llvm::ErrorOr<llvm::vfs::Status> Stat =285 getUnderlyingFS().status(OriginalFilename);286 if (!Stat) {287 const auto &Entry =288 getOrEmplaceSharedEntryForFilename(FilenameForLookup, Stat.getError());289 return insertLocalEntryForFilename(FilenameForLookup, Entry);290 }291 292 if (const auto *Entry = findSharedEntryByUID(*Stat))293 return insertLocalEntryForFilename(FilenameForLookup, *Entry);294 295 auto TEntry =296 Stat->isDirectory() ? TentativeEntry(*Stat) : readFile(OriginalFilename);297 298 const CachedFileSystemEntry *SharedEntry = [&]() {299 if (TEntry) {300 const auto &UIDEntry = getOrEmplaceSharedEntryForUID(std::move(*TEntry));301 return &getOrInsertSharedEntryForFilename(FilenameForLookup, UIDEntry);302 }303 return &getOrEmplaceSharedEntryForFilename(FilenameForLookup,304 TEntry.getError());305 }();306 307 return insertLocalEntryForFilename(FilenameForLookup, *SharedEntry);308}309 310llvm::ErrorOr<EntryRef>311DependencyScanningWorkerFilesystem::getOrCreateFileSystemEntry(312 StringRef OriginalFilename) {313 SmallString<256> PathBuf;314 auto FilenameForLookup = tryGetFilenameForLookup(OriginalFilename, PathBuf);315 if (!FilenameForLookup)316 return FilenameForLookup.getError();317 318 if (const auto *Entry =319 findEntryByFilenameWithWriteThrough(*FilenameForLookup))320 return EntryRef(OriginalFilename, *Entry).unwrapError();321 auto MaybeEntry = computeAndStoreResult(OriginalFilename, *FilenameForLookup);322 if (!MaybeEntry)323 return MaybeEntry.getError();324 return EntryRef(OriginalFilename, *MaybeEntry).unwrapError();325}326 327llvm::ErrorOr<llvm::vfs::Status>328DependencyScanningWorkerFilesystem::status(const Twine &Path) {329 SmallString<256> OwnedFilename;330 StringRef Filename = Path.toStringRef(OwnedFilename);331 332 if (shouldBypass(Filename))333 return getUnderlyingFS().status(Path);334 335 llvm::ErrorOr<EntryRef> Result = getOrCreateFileSystemEntry(Filename);336 if (!Result)337 return Result.getError();338 return Result->getStatus();339}340 341bool DependencyScanningWorkerFilesystem::exists(const Twine &Path) {342 // While some VFS overlay filesystems may implement more-efficient343 // mechanisms for `exists` queries, `DependencyScanningWorkerFilesystem`344 // typically wraps `RealFileSystem` which does not specialize `exists`,345 // so it is not likely to benefit from such optimizations. Instead,346 // it is more-valuable to have this query go through the347 // cached-`status` code-path of the `DependencyScanningWorkerFilesystem`.348 llvm::ErrorOr<llvm::vfs::Status> Status = status(Path);349 return Status && Status->exists();350}351 352namespace {353 354/// The VFS that is used by clang consumes the \c CachedFileSystemEntry using355/// this subclass.356class DepScanFile final : public llvm::vfs::File {357public:358 DepScanFile(std::unique_ptr<llvm::MemoryBuffer> Buffer,359 llvm::vfs::Status Stat)360 : Buffer(std::move(Buffer)), Stat(std::move(Stat)) {}361 362 static llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>> create(EntryRef Entry);363 364 llvm::ErrorOr<llvm::vfs::Status> status() override { return Stat; }365 366 llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>367 getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,368 bool IsVolatile) override {369 return llvm::MemoryBuffer::getMemBuffer(Buffer->getMemBufferRef(),370 RequiresNullTerminator);371 }372 373 std::error_code close() override { return {}; }374 375private:376 std::unique_ptr<llvm::MemoryBuffer> Buffer;377 llvm::vfs::Status Stat;378};379 380} // end anonymous namespace381 382llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>383DepScanFile::create(EntryRef Entry) {384 assert(!Entry.isError() && "error");385 386 if (Entry.isDirectory())387 return std::make_error_code(std::errc::is_a_directory);388 389 auto Result = std::make_unique<DepScanFile>(390 llvm::MemoryBuffer::getMemBuffer(Entry.getContents(),391 Entry.getStatus().getName(),392 /*RequiresNullTerminator=*/false),393 Entry.getStatus());394 395 return llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>(396 std::unique_ptr<llvm::vfs::File>(std::move(Result)));397}398 399llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>400DependencyScanningWorkerFilesystem::openFileForRead(const Twine &Path) {401 SmallString<256> OwnedFilename;402 StringRef Filename = Path.toStringRef(OwnedFilename);403 404 if (shouldBypass(Filename))405 return getUnderlyingFS().openFileForRead(Path);406 407 llvm::ErrorOr<EntryRef> Result = getOrCreateFileSystemEntry(Filename);408 if (!Result)409 return Result.getError();410 return DepScanFile::create(Result.get());411}412 413std::error_code414DependencyScanningWorkerFilesystem::getRealPath(const Twine &Path,415 SmallVectorImpl<char> &Output) {416 SmallString<256> OwnedFilename;417 StringRef OriginalFilename = Path.toStringRef(OwnedFilename);418 419 if (shouldBypass(OriginalFilename))420 return getUnderlyingFS().getRealPath(Path, Output);421 422 SmallString<256> PathBuf;423 auto FilenameForLookup = tryGetFilenameForLookup(OriginalFilename, PathBuf);424 if (!FilenameForLookup)425 return FilenameForLookup.getError();426 427 auto HandleCachedRealPath =428 [&Output](const CachedRealPath &RealPath) -> std::error_code {429 if (!RealPath)430 return RealPath.getError();431 Output.assign(RealPath->begin(), RealPath->end());432 return {};433 };434 435 // If we already have the result in local cache, no work required.436 if (const auto *RealPath =437 LocalCache.findRealPathByFilename(*FilenameForLookup))438 return HandleCachedRealPath(*RealPath);439 440 // If we have the result in the shared cache, cache it locally.441 auto &Shard = SharedCache.getShardForFilename(*FilenameForLookup);442 if (const auto *ShardRealPath =443 Shard.findRealPathByFilename(*FilenameForLookup)) {444 const auto &RealPath = LocalCache.insertRealPathForFilename(445 *FilenameForLookup, *ShardRealPath);446 return HandleCachedRealPath(RealPath);447 }448 449 // If we don't know the real path, compute it...450 std::error_code EC = getUnderlyingFS().getRealPath(OriginalFilename, Output);451 llvm::ErrorOr<llvm::StringRef> ComputedRealPath = EC;452 if (!EC)453 ComputedRealPath = StringRef{Output.data(), Output.size()};454 455 // ...and try to write it into the shared cache. In case some other thread won456 // this race and already wrote its own result there, just adopt it. Write457 // whatever is in the shared cache into the local one.458 const auto &RealPath = Shard.getOrEmplaceRealPathForFilename(459 *FilenameForLookup, ComputedRealPath);460 return HandleCachedRealPath(461 LocalCache.insertRealPathForFilename(*FilenameForLookup, RealPath));462}463 464std::error_code DependencyScanningWorkerFilesystem::setCurrentWorkingDirectory(465 const Twine &Path) {466 std::error_code EC = ProxyFileSystem::setCurrentWorkingDirectory(Path);467 updateWorkingDirForCacheLookup();468 return EC;469}470 471void DependencyScanningWorkerFilesystem::updateWorkingDirForCacheLookup() {472 llvm::ErrorOr<std::string> CWD =473 getUnderlyingFS().getCurrentWorkingDirectory();474 if (!CWD) {475 WorkingDirForCacheLookup = CWD.getError();476 } else if (!llvm::sys::path::is_absolute_gnu(*CWD)) {477 WorkingDirForCacheLookup = llvm::errc::invalid_argument;478 } else {479 WorkingDirForCacheLookup = *CWD;480 }481 assert(!WorkingDirForCacheLookup ||482 llvm::sys::path::is_absolute_gnu(*WorkingDirForCacheLookup));483}484 485llvm::ErrorOr<StringRef>486DependencyScanningWorkerFilesystem::tryGetFilenameForLookup(487 StringRef OriginalFilename, llvm::SmallVectorImpl<char> &PathBuf) const {488 StringRef FilenameForLookup;489 if (llvm::sys::path::is_absolute_gnu(OriginalFilename)) {490 FilenameForLookup = OriginalFilename;491 } else if (!WorkingDirForCacheLookup) {492 return WorkingDirForCacheLookup.getError();493 } else {494 StringRef RelFilename = OriginalFilename;495 RelFilename.consume_front("./");496 PathBuf.assign(WorkingDirForCacheLookup->begin(),497 WorkingDirForCacheLookup->end());498 llvm::sys::path::append(PathBuf, RelFilename);499 FilenameForLookup = StringRef{PathBuf.begin(), PathBuf.size()};500 }501 assert(llvm::sys::path::is_absolute_gnu(FilenameForLookup));502 return FilenameForLookup;503}504 505const char DependencyScanningWorkerFilesystem::ID = 0;506