[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

62

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?

62

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

[CodaFi]

clang/include/clang/Serialization/ModuleManager.h

62

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

62

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;
 
-  /// All loaded modules, indexed by name.
-  llvm::DenseMap<const FileEntry *, ModuleFile *> Modules;
+  /// All loaded modules, indexed by file name.
+  llvm::StringMap<ModuleFile *> Modules;
 
   /// FileManager that handles translating between filenames and
   /// FileEntry *.
   FileManager &FileMgr;
 
   /// Cache of PCM files.
   IntrusiveRefCntPtr<InMemoryModuleCache> ModuleCache;
 

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(File->getName());
   if (Known == Modules.end())
     return nullptr;
 
   return Known->second;
 }
 
 std::unique_ptr<llvm::MemoryBuffer>
 ModuleManager::lookupBuffer(StringRef Name) {
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)) {
+  auto EntryKey = Entry ? Entry->getName() : FileName;
+  if (ModuleFile *ModuleEntry = Modules.lookup(EntryKey)) {
     // 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] = 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(victim->File->getName());
 
     if (modMap) {
       StringRef ModuleName = victim->ModuleName;
       if (Module *mod = modMap->findModule(ModuleName)) {
         mod->setASTFile(nullptr);
       }
     }
   }

clang/test/Modules/stress1.cpp

 // RUN:   -fmodule-file=%t/m03.pcm \
 // RUN:   -fmodule-file=%t/merge00.pcm \
 // RUN:   -verify stress1.cpp -S -emit-llvm -o %t/stress1_check.ll
 //
 // RUN: diff -u %t/stress1.ll %t/stress1_check.ll
 //
 // RUN: %clang_cc1 -fmodules -x c++ -std=c++11 \
 // RUN:   -I Inputs/stress1 \
+// RUN:   -fno-implicit-modules \
 // RUN:   -fmodules-cache-path=%t \
 // RUN:   -fmodule-map-file-home-is-cwd \
 // RUN:   -fmodule-file=%t/m00.pcm \
 // RUN:   -fmodule-file=%t/m01.pcm \
 // RUN:   -fmodule-file=%t/m02.pcm \
 // RUN:   -fmodule-file=%t/m03.pcm \
 // RUN:   -emit-module -fmodule-name=merge00 -o /dev/null \
 // RUN:   -DMERGE_NO_REEXPORT \