[clang][Modules] Increase the Entropy of ModuleManager Map Keys

[CodaFi]

Summary

The ModuleManager's use of FileEntry nodes as the keys for its map of
loaded modules is less than ideal. Uniqueness for FileEntry nodes is
maintained by FileManager, which in turn uses inode numbers on hosts
that support that. When coupled with the module cache's proclivity for
turning over and deleting stale PCMs, this means entries for different
module files can wind up reusing the same underlying inode. When this
happens, subsequent accesses to the Modules map will disagree on the
ModuleFile associated with a given file.

It's fine to use the file management utilities to guarantee the presence
of module data, but we need a better source of key material that is
invariant with respect to these OS-level details. Using file paths alone
is a similarly frought solution because the ASTWriter performs a custom
canonicalization step (that is not equivalent to path canonicalization)
that renders keys from loaded AST cores useless for looking up cached
entries.

To mitigate the effects of inode reuse, increase the entropy of the key
material by incorporating the modtime and size. This ultimately
decreases the likelihood that a PCM that is swapped on disk will confuse
the cache, but it does not eliminate the possibility of collisions.

rdar://48443680

[vsapsai]

Overall, looks like a reasonable approach to solve inode reuse. The problem with filenames is that they might not be canonicalized and the same file can be known by different filenames. I'm trying to think through the consequences in the following scenarios:

• same name but file content has changed;
• different names but refer to the same file.

[CodaFi]

In D85981#2218583, @vsapsai wrote:

It's good to imagine these attack vectors. But I think the module cache being a relatively fault-tolerant and compiler-controlled system mitigates a lot of the damage you could cause by a well-timed "attack" in these scenarios:

• same name but file content has changed;

If there is a cache entry, the signature check that occurs after the lookup succeeds should catch most shenanigans. Assuming an attacker is able to craft a PCM with an equivalent signature to the victim PCM, and was able to time it such that the PCM were replaced after a subsequent read, you could definitely run into problems. But our "attackers" in most scenarios are usually other cc1 and swiftc invocations trying to build the same module, so we should see signature changes at least.

• different names but refer to the same file.

Then we'll waste space in the cache, but this requires the ability to predict the layout of the module cache ahead of time. It shouldn't affect the consistency of the entries in the table to do extra work - assuming you don't combine this approach with the scenario described above.

I'd also note here that the InMemoryModuleCache is already using a StringMap keyed by file names for its PCM table. You can see this patch as a kind of harmonization between the two approaches.

[aprantl]

clang/include/clang/Serialization/ModuleManager.h

122

Is it literally the file name, or something like the absolute realpath? And just because I'm curious: Is this the name of the .pcm or of the module map file?

122

I just realized @vsapsai already asked the same question :-)

[CodaFi]

clang/include/clang/Serialization/ModuleManager.h

122

It's the file path the module cache has computed for the PCM. I could try to use the real path to the file, but I'm not sure how portable/stable that interface is relative to this one.

[CodaFi]

Okay, I'm done throwing revisions at the bots. This windows-only failure is bizarre. @rsmith Do you have any insight into what's going wrong here?

[CodaFi]

Figured it out for myself. The test is forming paths that are using non-canonical path separators. Naively using those as keys means that the subsequent canonicalization done by the ASTWriter renders the keys useless for lookups into these structures. I'm going to switch to FileEntry::tryGetRealPathName since it's quite literally what ASTWriter is doing as part of its canonicalization phase. I worry about that as a solution in general though. In the future, it would be great to expose the canonicalization utilities in the ASTWriter as a more general kind of facility that could be shared between the implementations so we don't desync things again.

[CodaFi]

Switched tactics here. Rather than just change the source of the entropy, let's increase it from just inodes to (64-bits of inode) plus (file size) plus (mod time). It is still possible to defeat this scheme, but it means an attacker would have to replace the PCM with one that has been padded out to the same size then backdate its modtime to match the one in the cache - or some cascading failure of the syscalls providing these data conspires to make this happen.

[aprantl]

clang/include/clang/Serialization/ModuleManager.h

122

If it's the path to the .pcm there's no point in wasting time on realpath — there should only be one module cache path and we don't care where exactly it is on disk, and the paths inside the module cache ought to be unique anyway, because we just computed them. Thanks!

[aprantl]

clang/include/clang/Serialization/ModuleManager.h

62

Can you add a doxygen comment explaining why we compute our own hashing as opposed to using the FileEntry pointer?

62

Basically what you wrote in the description of the review...

[CodaFi]

@aprantl Good idea. Updated.

[CodaFi]

We have tested this proposed change out on our CI systems and have seen no relief from the symptoms of inode reuse with this approach. Abandoning this revision in favor of a more narrow fix.

clang/include/clang/Serialization/ModuleManager.h

class ModuleManager {
   /// by the user, the last one is the one that doesn't depend on anything
   /// further.
   SmallVector<ModuleFile *, 2> PCHChain;
 
   // The roots of the dependency DAG of AST files. This is used
   // to implement short-circuiting logic when running DFS over the dependencies.
   SmallVector<ModuleFile *, 2> Roots;
 
+  /// An \c EntryKey is a thin wrapper around a \c FileEntry that implements
+  /// a richer notion of identity.
+  ///
+  /// A plain \c FileEntry has its identity tied to inode numbers. When the
+  /// module cache regenerates a PCM, some filesystem allocators may reuse
+  /// inode numbers for distinct modules, which can cause the cache to return
+  /// mismatched entries. An \c EntryKey ensures that the size and modification
+  /// time are taken into account when determining the identity of a key, which
+  /// significantly decreases - but does not eliminate - the chance of
+  /// a collision.
+  struct EntryKey {
+    const FileEntry *Entry;
+    off_t Size;
+    time_t ModTime;
+
+    EntryKey(const FileEntry *Entry) : Entry(Entry), Size(0), ModTime(0) {
+      if (Entry) {
+        Size = Entry->getSize();
+        ModTime = Entry->getModificationTime();
+      }
+    }
+
+    EntryKey(const FileEntry *Entry, off_t Size, time_t ModTime)
+        : Entry(Entry), Size(Size), ModTime(ModTime) {}
+
+    struct Info {
+      static inline EntryKey getEmptyKey() {
+        return EntryKey{
+            llvm::DenseMapInfo<const FileEntry *>::getEmptyKey(),
+            llvm::DenseMapInfo<off_t>::getEmptyKey(),
+            llvm::DenseMapInfo<time_t>::getEmptyKey(),
+        };
+      }
+      static inline EntryKey getTombstoneKey() {
+        return EntryKey{
+            llvm::DenseMapInfo<const FileEntry *>::getTombstoneKey(),
+            llvm::DenseMapInfo<off_t>::getTombstoneKey(),
+            llvm::DenseMapInfo<time_t>::getTombstoneKey(),
+        };
+      }
+      static unsigned getHashValue(const EntryKey &Val) {
+        return llvm::DenseMapInfo<const FileEntry *>::getHashValue(Val.Entry);
+      }
+      static bool isEqual(const EntryKey &LHS, const EntryKey &RHS) {
+        if (LHS.Entry == getEmptyKey().Entry ||
+            LHS.Entry == getTombstoneKey().Entry ||
+            RHS.Entry == getEmptyKey().Entry ||
+            RHS.Entry == getTombstoneKey().Entry) {
+          return LHS.Entry == RHS.Entry;
+        }
+        if (LHS.Entry == nullptr || RHS.Entry == nullptr) {
+          return LHS.Entry == RHS.Entry;
+        }
+        return LHS.Entry == RHS.Entry && LHS.Size == RHS.Size &&
+               LHS.ModTime == RHS.ModTime;
+      }
+    };
+  };
+
   /// All loaded modules, indexed by name.
-  llvm::DenseMap<const FileEntry *, ModuleFile *> Modules;
+  llvm::DenseMap<EntryKey, ModuleFile *, EntryKey::Info> Modules;
 
   /// FileManager that handles translating between filenames and
   /// FileEntry *.
   FileManager &FileMgr;
 
   /// Cache of PCM files.
   IntrusiveRefCntPtr<InMemoryModuleCache> ModuleCache;
 
   /// Knows how to unwrap module containers.
   const PCHContainerReader &PCHContainerRdr;
 
   /// Preprocessor's HeaderSearchInfo containing the module map.
   const HeaderSearch &HeaderSearchInfo;
 
   /// A lookup of in-memory (virtual file) buffers
-  llvm::DenseMap<const FileEntry *, std::unique_ptr<llvm::MemoryBuffer>>
+  llvm::DenseMap<EntryKey, std::unique_ptr<llvm::MemoryBuffer>, EntryKey::Info>
       InMemoryBuffers;
 
   /// The visitation order.
   SmallVector<ModuleFile *, 4> VisitOrder;
 
   /// The list of module files that both we and the global module index
   /// know about.
   ///

clang/lib/Serialization/ModuleManager.cpp

ModuleFile *ModuleManager::lookupByModuleName(StringRef Name) const {
   if (const Module *Mod = HeaderSearchInfo.getModuleMap().findModule(Name))
     if (const FileEntry *File = Mod->getASTFile())
       return lookup(File);
 
   return nullptr;
 }
 
 ModuleFile *ModuleManager::lookup(const FileEntry *File) const {
-  auto Known = Modules.find(File);
+  auto Known = Modules.find(EntryKey{File});
   if (Known == Modules.end())
     return nullptr;
 
   return Known->second;
 }
 
 std::unique_ptr<llvm::MemoryBuffer>
 ModuleManager::lookupBuffer(StringRef Name) {
   auto Entry = FileMgr.getFile(Name, /*OpenFile=*/false,
                                /*CacheFailure=*/false);
   if (!Entry)
     return nullptr;
-  return std::move(InMemoryBuffers[*Entry]);
+  return std::move(InMemoryBuffers[EntryKey{*Entry}]);
 }
 
 static bool checkSignature(ASTFileSignature Signature,
                            ASTFileSignature ExpectedSignature,
                            std::string &ErrorStr) {
   if (!ExpectedSignature || Signature == ExpectedSignature)
     return false;
 
ModuleManager::addModule(StringRef FileName, ModuleKind Type,
   }
 
   if (!Entry && FileName != "-") {
     ErrorStr = "module file not found";
     return Missing;
   }
 
   // Check whether we already loaded this module, before
-  if (ModuleFile *ModuleEntry = Modules.lookup(Entry)) {
+  if (ModuleFile *ModuleEntry = Modules.lookup(EntryKey{Entry})) {
     // Check the stored signature.
     if (checkSignature(ModuleEntry->Signature, ExpectedSignature, ErrorStr))
       return OutOfDate;
 
     Module = ModuleEntry;
     updateModuleImports(*ModuleEntry, ImportedBy, ImportLoc);
     return AlreadyLoaded;
   }
ModuleManager::addModule(StringRef FileName, ModuleKind Type,
 
   // Read the signature eagerly now so that we can check it.  Avoid calling
   // ReadSignature unless there's something to check though.
   if (ExpectedSignature && checkSignature(ReadSignature(NewModule->Data),
                                           ExpectedSignature, ErrorStr))
     return OutOfDate;
 
   // We're keeping this module.  Store it everywhere.
-  Module = Modules[Entry] = NewModule.get();
+  Module = Modules[EntryKey{Entry}] = NewModule.get();
 
   updateModuleImports(*NewModule, ImportedBy, ImportLoc);
 
   if (!NewModule->isModule())
     PCHChain.push_back(NewModule.get());
   if (!ImportedBy)
     Roots.push_back(NewModule.get());
 
for (auto I = First; I != Last; ++I) {
     if (!I->isModule()) {
       PCHChain.erase(llvm::find(PCHChain, &*I), PCHChain.end());
       break;
     }
   }
 
   // Delete the modules and erase them from the various structures.
   for (ModuleIterator victim = First; victim != Last; ++victim) {
-    Modules.erase(victim->File);
+    Modules.erase(EntryKey{victim->File});
 
     if (modMap) {
       StringRef ModuleName = victim->ModuleName;
       if (Module *mod = modMap->findModule(ModuleName)) {
         mod->setASTFile(nullptr);
       }
     }
   }
 
   // Delete the modules.
   Chain.erase(Chain.begin() + (First - begin()), Chain.end());
 }
 
 void
 ModuleManager::addInMemoryBuffer(StringRef FileName,
                                  std::unique_ptr<llvm::MemoryBuffer> Buffer) {
   const FileEntry *Entry =
       FileMgr.getVirtualFile(FileName, Buffer->getBufferSize(), 0);
-  InMemoryBuffers[Entry] = std::move(Buffer);
+  InMemoryBuffers[EntryKey{Entry}] = std::move(Buffer);
 }
 
 ModuleManager::VisitState *ModuleManager::allocateVisitState() {
   // Fast path: if we have a cached state, use it.
   if (FirstVisitState) {
     VisitState *Result = FirstVisitState;
     FirstVisitState = FirstVisitState->NextState;
     Result->NextState = nullptr;