FileManager: std::map => BumpPtrAllocator + DenseMap of pointers

[sammccall]

Summary

This is both smaller and faster.

[kadircet]

thanks! maybe put an NFC in the patch name?

clang/lib/Basic/FileManager.cpp

583

seems like just formatting change, same for next 2 chunks.

[dexonsmith]

Nice!

[dexonsmith]

clang/lib/Basic/FileManager.cpp

318

I'm trying to figure out why ReusingEntry was necessary. It looks to me like you could just call UFE->isValid() here and avoid introducing that bool... or am I missing something?

[sammccall]

clang/lib/Basic/FileManager.cpp

318

You're right, but I think we can get rid of isValid, and plan to send a patch.

A FileEntry handed out by FileManager always has isValid = true. It's not possible to create a useful FileEntry outside FileManager (and this is never done outside FileManagerTest). So the concept of validity isn't needed.

(IMO the main cost of having the isValid flag is conceptual complexity - lots of places check it, which means people must be thinking about how to handle this case)

[dexonsmith]

clang/lib/Basic/FileManager.cpp

318

Sure, SGTM.

clang/include/clang/Basic/FileManager.h

 ///
 /// This also handles more advanced properties, such as uniquing files based
 /// on "inode", so that a file with two names (e.g. symlinked) will be treated
 /// as a single file.
 ///
 class FileManager : public RefCountedBase<FileManager> {
   IntrusiveRefCntPtr<llvm::vfs::FileSystem> FS;
   FileSystemOptions FileSystemOpts;
+  llvm::SpecificBumpPtrAllocator<FileEntry> FilesAlloc;
+  llvm::SpecificBumpPtrAllocator<DirectoryEntry> DirsAlloc;
 
   /// Cache for existing real directories.
-  std::map<llvm::sys::fs::UniqueID, DirectoryEntry> UniqueRealDirs;
+  llvm::DenseMap<llvm::sys::fs::UniqueID, DirectoryEntry *> UniqueRealDirs;
 
   /// Cache for existing real files.
-  std::map<llvm::sys::fs::UniqueID, FileEntry> UniqueRealFiles;
+  llvm::DenseMap<llvm::sys::fs::UniqueID, FileEntry *> UniqueRealFiles;
 
   /// The virtual directories that we have allocated.
   ///
   /// For each virtual file (e.g. foo/bar/baz.cpp), we add all of its parent
   /// directories (foo/ and foo/bar/) here.
-  SmallVector<std::unique_ptr<DirectoryEntry>, 4> VirtualDirectoryEntries;
+  SmallVector<DirectoryEntry *, 4> VirtualDirectoryEntries;
   /// The virtual files that we have allocated.
-  SmallVector<std::unique_ptr<FileEntry>, 4> VirtualFileEntries;
+  SmallVector<FileEntry *, 4> VirtualFileEntries;
 
   /// A set of files that bypass the maps and uniquing.  They can have
   /// conflicting filenames.
-  SmallVector<std::unique_ptr<FileEntry>, 0> BypassFileEntries;
+  SmallVector<FileEntry *, 0> BypassFileEntries;
 
   /// A cache that maps paths to directory entries (either real or
   /// virtual) we have looked up, or an error that occurred when we looked up
   /// the directory.
   ///
   /// The actual Entries for real directories/files are
   /// owned by UniqueRealDirs/UniqueRealFiles above, while the Entries
   /// for virtual directories/files are owned by

clang/lib/Basic/FileManager.cpp

void FileManager::addAncestorsAsVirtualDirs(StringRef Path) {
   // When caching a virtual directory, we always cache its ancestors
   // at the same time.  Therefore, if DirName is already in the cache,
   // we don't need to recurse as its ancestors must also already be in
   // the cache (or it's a known non-virtual directory).
   if (NamedDirEnt.second)
     return;
 
   // Add the virtual directory to the cache.
-  auto UDE = std::make_unique<DirectoryEntry>();
+  auto *UDE = new (DirsAlloc.Allocate()) DirectoryEntry();
   UDE->Name = NamedDirEnt.first();
-  NamedDirEnt.second = *UDE.get();
-  VirtualDirectoryEntries.push_back(std::move(UDE));
+  NamedDirEnt.second = *UDE;
+  VirtualDirectoryEntries.push_back(UDE);
 
   // Recursively add the other ancestors.
   addAncestorsAsVirtualDirs(DirName);
 }
 
 llvm::Expected<DirectoryEntryRef>
 FileManager::getDirectoryRef(StringRef DirName, bool CacheFailure) {
   // stat doesn't like trailing separators except for root directory.
else
       SeenDirEntries.erase(DirName);
     return llvm::errorCodeToError(statError);
   }
 
   // It exists.  See if we have already opened a directory with the
   // same inode (this occurs on Unix-like systems when one dir is
   // symlinked to another, for example) or the same path (on
   // Windows).
-  DirectoryEntry &UDE = UniqueRealDirs[Status.getUniqueID()];
+  DirectoryEntry *&UDE = UniqueRealDirs[Status.getUniqueID()];
 
-  NamedDirEnt.second = UDE;
-  if (UDE.getName().empty()) {
+  if (!UDE) {
     // We don't have this directory yet, add it.  We use the string
     // key from the SeenDirEntries map as the string.
-    UDE.Name  = InterndDirName;
+    UDE = new (DirsAlloc.Allocate()) DirectoryEntry();
+    UDE->Name = InterndDirName;
   }
+  NamedDirEnt.second = *UDE;
 
   return DirectoryEntryRef(NamedDirEnt);
 }
 
 llvm::ErrorOr<const DirectoryEntry *>
 FileManager::getDirectory(StringRef DirName, bool CacheFailure) {
   auto Result = getDirectoryRef(DirName, CacheFailure);
   if (Result)
if (statError) {
 
     return llvm::errorCodeToError(statError);
   }
 
   assert((openFile || !F) && "undesired open file");
 
   // It exists.  See if we have already opened a file with the same inode.
   // This occurs when one dir is symlinked to another, for example.
-  FileEntry &UFE = UniqueRealFiles[Status.getUniqueID()];
+  FileEntry *&UFE = UniqueRealFiles[Status.getUniqueID()];
+  bool ReusingEntry = UFE != nullptr;
+  if (!UFE)
+    UFE = new (FilesAlloc.Allocate()) FileEntry();
 
   // FIXME: This should just check `!Status.ExposesExternalVFSPath`, but the
   // else branch also ends up fixing up relative paths to be the actually
   // looked up absolute path. This isn't necessarily desired, but does seem to
   // be relied on in some clients.
   if (Status.getName() == Filename) {
     // The name matches. Set the FileEntry.
-    NamedFileEnt->second = FileEntryRef::MapValue(UFE, DirInfo);
+    NamedFileEnt->second = FileEntryRef::MapValue(*UFE, DirInfo);
   } else {
     // We need a redirect. First grab the actual entry we want to return.
     //
     // This redirection logic intentionally leaks the external name of a
     // redirected file that uses 'use-external-name' in \a
     // vfs::RedirectionFileSystem. This allows clang to report the external
     // name to users (in diagnostics) and to tools that don't have access to
     // the VFS (in debug info and dependency '.d' files).
     //
     // FIXME: This is pretty complicated. It's also inconsistent with how
     // "real" filesystems behave and confuses parts of clang expect to see the
     // name-as-accessed on the \a FileEntryRef. To remove this we should
     // implement the FIXME on `ExposesExternalVFSPath`, ie. update the
     // `FileEntryRef::getName()` path to *always* be the virtual path and have
     // clients request the external path only when required through a separate
     // API.
     auto &Redirection =
         *SeenFileEntries
-             .insert({Status.getName(), FileEntryRef::MapValue(UFE, DirInfo)})
+             .insert({Status.getName(), FileEntryRef::MapValue(*UFE, DirInfo)})
              .first;
     assert(Redirection.second->V.is<FileEntry *>() &&
            "filename redirected to a non-canonical filename?");
-    assert(Redirection.second->V.get<FileEntry *>() == &UFE &&
+    assert(Redirection.second->V.get<FileEntry *>() == UFE &&
            "filename from getStatValue() refers to wrong file");
 
     // Cache the redirection in the previously-inserted entry, still available
     // in the tentative return value.
     NamedFileEnt->second = FileEntryRef::MapValue(Redirection);
 
     // Fix the tentative return value.
     NamedFileEnt = &Redirection;
   }
 
   FileEntryRef ReturnedRef(*NamedFileEnt);
-  if (UFE.isValid()) { // Already have an entry with this inode, return it.
+  if (ReusingEntry) { // Already have an entry with this inode, return it.
 
     // FIXME: This hack ensures that `getDir()` will use the path that was
     // used to lookup this file, even if we found a file by different path
     // first. This is required in order to find a module's structure when its
     // headers/module map are mapped in the VFS.
     //
     // This should be removed once `HeaderSearch` is updated to use `*Ref`s
     // *and* the redirection hack above is removed. The removal of the latter
     // is required since otherwise the ref will have the exposed external VFS
     // path still.
-    if (&DirInfo.getDirEntry() != UFE.Dir && Status.ExposesExternalVFSPath)
-      UFE.Dir = &DirInfo.getDirEntry();
+    if (&DirInfo.getDirEntry() != UFE->Dir && Status.ExposesExternalVFSPath)
+      UFE->Dir = &DirInfo.getDirEntry();
 
     // Always update LastRef to the last name by which a file was accessed.
     // FIXME: Neither this nor always using the first reference is correct; we
     // want to switch towards a design where we return a FileName object that
     // encapsulates both the name by which the file was accessed and the
     // corresponding FileEntry.
     // FIXME: LastRef should be removed from FileEntry once all clients adopt
     // FileEntryRef.
-    UFE.LastRef = ReturnedRef;
+    UFE->LastRef = ReturnedRef;
 
     return ReturnedRef;
   }
 
   // Otherwise, we don't have this file yet, add it.
-  UFE.LastRef = ReturnedRef;
-  UFE.Size    = Status.getSize();
-  UFE.ModTime = llvm::sys::toTimeT(Status.getLastModificationTime());
-  UFE.Dir     = &DirInfo.getDirEntry();
-  UFE.UID     = NextFileUID++;
-  UFE.UniqueID = Status.getUniqueID();
-  UFE.IsNamedPipe = Status.getType() == llvm::sys::fs::file_type::fifo_file;
-  UFE.File = std::move(F);
-  UFE.IsValid = true;
-
-  if (UFE.File) {
-    if (auto PathName = UFE.File->getName())
-      fillRealPathName(&UFE, *PathName);
+  UFE->LastRef = ReturnedRef;
+  UFE->Size = Status.getSize();
+  UFE->ModTime = llvm::sys::toTimeT(Status.getLastModificationTime());
+  UFE->Dir = &DirInfo.getDirEntry();
+  UFE->UID = NextFileUID++;
+  UFE->UniqueID = Status.getUniqueID();
+  UFE->IsNamedPipe = Status.getType() == llvm::sys::fs::file_type::fifo_file;
+  UFE->File = std::move(F);
+  UFE->IsValid = true;
+
+  if (UFE->File) {
+    if (auto PathName = UFE->File->getName())
+      fillRealPathName(UFE, *PathName);
   } else if (!openFile) {
     // We should still fill the path even if we aren't opening the file.
-    fillRealPathName(&UFE, InterndFileName);
+    fillRealPathName(UFE, InterndFileName);
   }
   return ReturnedRef;
 }
 
 llvm::Expected<FileEntryRef> FileManager::getSTDIN() {
   // Only read stdin once.
   if (STDIN)
     return *STDIN;
auto DirInfo = expectedToOptional(getDirectoryFromFile(
       *this, Filename.empty() ? "." : Filename, /*CacheFailure=*/true));
   assert(DirInfo &&
          "The directory of a virtual file should already be in the cache.");
 
   // Check to see if the file exists. If so, drop the virtual file
   llvm::vfs::Status Status;
   const char *InterndFileName = NamedFileEnt.first().data();
   if (!getStatValue(InterndFileName, Status, true, nullptr)) {
-    UFE = &UniqueRealFiles[Status.getUniqueID()];
     Status = llvm::vfs::Status(
       Status.getName(), Status.getUniqueID(),
       llvm::sys::toTimePoint(ModificationTime),
       Status.getUser(), Status.getGroup(), Size,
       Status.getType(), Status.getPermissions());
 
-    NamedFileEnt.second = FileEntryRef::MapValue(*UFE, *DirInfo);
-
+    auto &RealFE = UniqueRealFiles[Status.getUniqueID()];
+    if (RealFE) {
       // If we had already opened this file, close it now so we don't
       // leak the descriptor. We're not going to use the file
       // descriptor anyway, since this is a virtual file.
-    if (UFE->File)
-      UFE->closeFile();
-
+      if (RealFE->File)
+        RealFE->closeFile();
       // If we already have an entry with this inode, return it.
       //
       // FIXME: Surely this should add a reference by the new name, and return
       // it instead...
-    if (UFE->isValid())
+      NamedFileEnt.second = FileEntryRef::MapValue(*RealFE, *DirInfo);
       return FileEntryRef(NamedFileEnt);
+    }
+    // File exists, but no entry - create it.
+    RealFE = new (FilesAlloc.Allocate()) FileEntry();
+    RealFE->UniqueID = Status.getUniqueID();
+    RealFE->IsNamedPipe =
+        Status.getType() == llvm::sys::fs::file_type::fifo_file;
+    fillRealPathName(RealFE, Status.getName());
 
-    UFE->UniqueID = Status.getUniqueID();
-    UFE->IsNamedPipe = Status.getType() == llvm::sys::fs::file_type::fifo_file;
-    fillRealPathName(UFE, Status.getName());
+    UFE = RealFE;
   } else {
-    VirtualFileEntries.push_back(std::make_unique<FileEntry>());
-    UFE = VirtualFileEntries.back().get();
-    NamedFileEnt.second = FileEntryRef::MapValue(*UFE, *DirInfo);
+    // File does not exist, create a virtual entry.
+    UFE = new (FilesAlloc.Allocate()) FileEntry();
+    VirtualFileEntries.push_back(UFE);
   }
 
+  NamedFileEnt.second = FileEntryRef::MapValue(*UFE, *DirInfo);
   UFE->LastRef = FileEntryRef(NamedFileEnt);
   UFE->Size    = Size;
   UFE->ModTime = ModificationTime;
   UFE->Dir     = &DirInfo->getDirEntry();
   UFE->UID     = NextFileUID++;
   UFE->IsValid = true;
   UFE->File.reset();
   return FileEntryRef(NamedFileEnt);
llvm::Optional<FileEntryRef> FileManager::getBypassFile(FileEntryRef VF) {
 
   // If we've already bypassed just use the existing one.
   auto Insertion = SeenBypassFileEntries->insert(
       {VF.getName(), std::errc::no_such_file_or_directory});
   if (!Insertion.second)
     return FileEntryRef(*Insertion.first);
 
   // Fill in the new entry from the stat.
-  BypassFileEntries.push_back(std::make_unique<FileEntry>());
-  const FileEntry &VFE = VF.getFileEntry();
-  FileEntry &BFE = *BypassFileEntries.back();
-  Insertion.first->second = FileEntryRef::MapValue(BFE, VF.getDir());
-  BFE.LastRef = FileEntryRef(*Insertion.first);
-  BFE.Size = Status.getSize();
-  BFE.Dir = VFE.Dir;
-  BFE.ModTime = llvm::sys::toTimeT(Status.getLastModificationTime());
-  BFE.UID = NextFileUID++;
-  BFE.IsValid = true;
+  FileEntry *BFE = new (FilesAlloc.Allocate()) FileEntry();
+  BypassFileEntries.push_back(BFE);
+  Insertion.first->second = FileEntryRef::MapValue(*BFE, VF.getDir());
+  BFE->LastRef = FileEntryRef(*Insertion.first);
+  BFE->Size = Status.getSize();
+  BFE->Dir = VF.getFileEntry().Dir;
+  BFE->ModTime = llvm::sys::toTimeT(Status.getLastModificationTime());
+  BFE->UID = NextFileUID++;
+  BFE->IsValid = true;
 
   // Save the entry in the bypass table and return.
   return FileEntryRef(*Insertion.first);
 }
 
 bool FileManager::FixupRelativePath(SmallVectorImpl<char> &path) const {
   StringRef pathRef(path.data(), path.size());
 

 
 /// getStatValue - Get the 'stat' information for the specified path,
 /// using the cache to accelerate it if possible.  This returns true
 /// if the path points to a virtual file or does not exist, or returns
 /// false if it's an existent real file.  If FileDescriptor is NULL,
 /// do directory look-up instead of file look-up.
 std::error_code
 FileManager::getStatValue(StringRef Path, llvm::vfs::Status &Status,
                           bool isFile, std::unique_ptr<llvm::vfs::File> *F) {
   // FIXME: FileSystemOpts shouldn't be passed in here, all paths should be
   // absolute!
   if (FileSystemOpts.WorkingDir.empty())
     return FileSystemStatCache::get(Path, Status, isFile, F,
                                     StatCache.get(), *FS);
 
   SmallString<128> FilePath(Path);
   FixupRelativePath(FilePath);
FileManager::getNoncachedStatValue(StringRef Path,
   llvm::ErrorOr<llvm::vfs::Status> S = FS->status(FilePath.c_str());
   if (!S)
     return S.getError();
   Result = *S;
   return std::error_code();
 }
 
 void FileManager::GetUniqueIDMapping(
-                   SmallVectorImpl<const FileEntry *> &UIDToFiles) const {
   UIDToFiles.clear();
   UIDToFiles.resize(NextFileUID);
 
   // Map file entries
   for (llvm::StringMap<llvm::ErrorOr<FileEntryRef::MapValue>,
                        llvm::BumpPtrAllocator>::const_iterator
            FE = SeenFileEntries.begin(),
            FEEnd = SeenFileEntries.end();
        FE != FEEnd; ++FE)
     if (llvm::ErrorOr<FileEntryRef::MapValue> Entry = FE->getValue()) {
       if (const auto *FE = Entry->V.dyn_cast<FileEntry *>())
         UIDToFiles[FE->getUID()] = FE;
     }
 
   // Map virtual file entries
   for (const auto &VFE : VirtualFileEntries)
-    UIDToFiles[VFE->getUID()] = VFE.get();
+    UIDToFiles[VFE->getUID()] = VFE;
 }
 
 StringRef FileManager::getCanonicalName(const DirectoryEntry *Dir) {
   llvm::DenseMap<const void *, llvm::StringRef>::iterator Known
     = CanonicalNames.find(Dir);
   if (Known != CanonicalNames.end())
     return Known->second;