[CodeView] Fix cycles in debug info when merging Types with global hashes

[aganea]

Summary

When type streams with forward references were merged using GHashes, cycles were introduced in the debug info. This was caused by GlobalTypeTableBuilder::insertRecordAs() not inserting the record on the second pass, thus yielding an empty ArrayRef at that record slot. Later on, upon PDB emission, TpiStreamBuilder::commit() would skip that empty record, thus offseting all indices that came after in the stream.

The solution comes in two steps:

1. Fix the hash calculation, by doing a multiple-step resolution, iff there are forward references in the input stream.
2. Fix merge by resolving with multiple passes, therefore moving records with forward references at the end of the stream.

I had to make some esthetic changes, such as to support GHashes in llvm-readoj - I could commit that separately.
There's also a bugfix for dumpCodeViewMergedTypes() which previously could reference deleted memory (see comment in llvm-readobj.cpp).

Fixes PR40221

[rnk]

include/llvm/DebugInfo/CodeView/TypeCollection.h

33

I guess this is a question for @zturner.

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

I think this would have to go to fix point, not just two passes. Consider the case where each record in the type stream refers to the next, i.e. a pointer to a pointer to a pointer ... to void, and everything is backwards. =(

[aganea]

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

Good point. I can make a test case, and modify to handle that.

[zturner]

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

I think we can do slightly better than go to fixed point. First go forwards, then go backwards over the remaining records. That's verrrrrry likely to get you to the end in 2 passes. If nothing else, definitely a better heuristic then always going forward.

[zturner]

include/llvm/DebugInfo/CodeView/TypeCollection.h

33

I'm not sold on this method. It doesn't make much sense in the base class here, because you could theoretically have implementations that aren't backed by an array. It sounds like you even ran into this in LazyRandomTypeCollection. However, I don't actually think you need this anyway. More on why later in a later comment.

tools/llvm-readobj/COFFDumper.cpp

1929

Instead of constructing a TypeTableCollection here and passing it CVTypes.records(), I think you can just use the CVTypes directly. Specifically, something like this should work:

{
  ListScope S(Writer, "MergedTypeStream");
  TypeDumpVisitor TDV(CVTypes, &Writer, opts::CodeViewSubsectionBytes);
  error(codeview::visitTypeStream(TpiTypes, TDV);
  Writer.flush();
}

and similarly for the code below.

[aganea]

Simplified, following comments.

I made the test a bit more complicated, how I'm not sure such things happen with real life OBJs. The whole test resolves in 1+3 passes (1 initial and 3 extra). Evidently if we could walk backwards it could resolve in 1+2 passes, but I think it's not worth it. This whole bug only happens with very small MASM OBJs.

[aganea]

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

Tried that, but given we're dealing with CVTypeArray as a Range type, we can't iterate back; unless we use something like LazyRandomTypeCollection for caching after the first run. Given that forward references seem to happen on MASM OBJs only, using a LazyRandomTypeCollection for every OBJ sounds a bit overkill. So instead I opted for several passes, like TypeStreamMerger.

tools/llvm-readobj/llvm-readobj.cpp

647

I had to move this here, because otherwise in the old place the TPI stream would reference deleted memory (because BinaryOrErr is deleted above when dumpInput() exits)

[rnk]

include/llvm/DebugInfo/CodeView/TypeHashing.h

120

I think there should be a comment before this loop explaining why it's needed, and that it's not performance critical because most objs don't have forward references.

tools/llvm-readobj/llvm-readobj.cpp

647

Hm, but won't this print the merged stream once per obj? And won't we still reference deleted memory on the second obj input? I guess the proper fix is to std::move the OwningBinary into a vector in the global ReadObjTypeTableBuilder object.

[aganea]

Removed changes that aren't critical for this fix.

[rnk]

lgtm!

test/tools/llvm-readobj/codeview-merging-ghash.test

108

Nice test!

include/llvm/DebugInfo/CodeView/AppendingTypeTableBuilder.h

public:
   Optional<TypeIndex> getFirst() override;
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
 
+  ArrayRef<ArrayRef<uint8_t>> records() const override;
+
   // public interface
   void reset();
   TypeIndex nextTypeIndex() const;
 
   BumpPtrAllocator &getAllocator() { return RecordStorage; }
 
-  ArrayRef<ArrayRef<uint8_t>> records() const;
   TypeIndex insertRecordBytes(ArrayRef<uint8_t> &Record);
   TypeIndex insertRecord(ContinuationRecordBuilder &Builder);
 
   template <typename T> TypeIndex writeLeafType(T &Record) {
     ArrayRef<uint8_t> Data = SimpleSerializer.serialize(Record);
     return insertRecordBytes(Data);
   }
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_TYPETABLEBUILDER_H

include/llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h

public:
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
 
   // public interface
-  void reset();
   TypeIndex nextTypeIndex() const;
 
   BumpPtrAllocator &getAllocator() { return RecordStorage; }
 
-  ArrayRef<ArrayRef<uint8_t>> records() const;
+  ArrayRef<ArrayRef<uint8_t>> records() const override;
   ArrayRef<GloballyHashedType> hashes() const;
 
   template <typename CreateFunc>
   TypeIndex insertRecordAs(GloballyHashedType Hash, size_t RecordSize,
                            CreateFunc Create) {
     auto Result = HashedRecords.try_emplace(Hash, nextTypeIndex());
 
-    if (LLVM_UNLIKELY(Result.second)) {
+    if (LLVM_UNLIKELY(Result.second /*inserted*/ ||
+                      Result.first->second.isSimple())) {
       uint8_t *Stable = RecordStorage.Allocate<uint8_t>(RecordSize);
       MutableArrayRef<uint8_t> Data(Stable, RecordSize);
-      SeenRecords.push_back(Create(Data));
+      ArrayRef<uint8_t> StableRecord = Create(Data);
+      if (StableRecord.empty()) {
+        // Records with forward references into the Type stream will be deferred
+        // for insertion at a later time, on the second pass.
+        Result.first->getSecond() = TypeIndex(SimpleTypeKind::NotTranslated);
+        return TypeIndex(SimpleTypeKind::NotTranslated);
+      }
+      if (Result.first->second.isSimple()) {
+        assert(Result.first->second.getIndex() ==
+               (uint32_t)SimpleTypeKind::NotTranslated);
+        // On the second pass, update with index to remapped record. The
+        // (initially misbehaved) record will now come *after* other records
+        // resolved in the first pass, with proper *back* references in the
+        // stream.
+        Result.first->second = nextTypeIndex();
+      }
+      SeenRecords.push_back(StableRecord);
       SeenHashes.push_back(Hash);
     }
 
-    // Update the caller's copy of Record to point a stable copy.
     return Result.first->second;
   }
 
   TypeIndex insertRecordBytes(ArrayRef<uint8_t> Data);
   TypeIndex insertRecord(ContinuationRecordBuilder &Builder);
 
   template <typename T> TypeIndex writeLeafType(T &Record) {
     ArrayRef<uint8_t> Data = SimpleSerializer.serialize(Record);
     return insertRecordBytes(Data);
   }
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_MERGINGTYPETABLEBUILDER_H

include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h

class LazyRandomTypeCollection : public TypeCollection {
   struct CacheEntry {
     CVType Type;
     uint32_t Offset;
     StringRef Name;
   };
 
 public:
   explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
-  LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
-  LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
                            PartialOffsetArray PartialOffsets);
   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
 
   void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
   void reset(StringRef Data, uint32_t RecordCountHint);
   void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
 
   uint32_t getOffsetOfType(TypeIndex Index);
 
   Optional<CVType> tryGetType(TypeIndex Index);
 
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
   Optional<TypeIndex> getFirst() override;
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
 
+  ArrayRef<ArrayRef<uint8_t>> records() const override;
+
 private:
   Error ensureTypeExists(TypeIndex Index);
   void ensureCapacityFor(TypeIndex Index);
 
   Error visitRangeForType(TypeIndex TI);
   Error fullScanForType(TypeIndex TI);
   void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
 
   /// Number of actual records.
   uint32_t Count = 0;
 
   /// The largest type index which we've visited.
   TypeIndex LargestTypeIndex = TypeIndex::None();
 
   BumpPtrAllocator Allocator;
   StringSaver NameStorage;
 
   /// The type array to allow random access visitation of.
   CVTypeArray Types;
 
   std::vector<CacheEntry> Records;
+  std::vector<ArrayRef<uint8_t>> DataRecords;
 
   /// An array of index offsets for the given type stream, allowing log(N)
   /// lookups of a type record by index.  Similar to KnownOffsets but only
   /// contains offsets for some type indices, some of which may not have
   /// ever been visited.
   PartialOffsetArray PartialOffsets;
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H

include/llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h

public:
   uint32_t capacity() override;
 
   // public interface
   void reset();
   TypeIndex nextTypeIndex() const;
 
   BumpPtrAllocator &getAllocator() { return RecordStorage; }
 
-  ArrayRef<ArrayRef<uint8_t>> records() const;
+  ArrayRef<ArrayRef<uint8_t>> records() const override;
 
   TypeIndex insertRecordAs(hash_code Hash, ArrayRef<uint8_t> &Record);
   TypeIndex insertRecordBytes(ArrayRef<uint8_t> &Record);
   TypeIndex insertRecord(ContinuationRecordBuilder &Builder);
 
   template <typename T> TypeIndex writeLeafType(T &Record) {
     ArrayRef<uint8_t> Data = SimpleSerializer.serialize(Record);
     return insertRecordBytes(Data);
   }
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_MERGINGTYPETABLEBUILDER_H

include/llvm/DebugInfo/CodeView/TypeCollection.h

public:
   virtual Optional<TypeIndex> getFirst() = 0;
   virtual Optional<TypeIndex> getNext(TypeIndex Prev) = 0;
 
   virtual CVType getType(TypeIndex Index) = 0;
   virtual StringRef getTypeName(TypeIndex Index) = 0;
   virtual bool contains(TypeIndex Index) = 0;
   virtual uint32_t size() = 0;
   virtual uint32_t capacity() = 0;
+  virtual ArrayRef<ArrayRef<uint8_t>> records() const = 0;
 
   template <typename TFunc> void ForEachRecord(TFunc Func) {
     Optional<TypeIndex> Next = getFirst();
 
     while (Next.hasValue()) {
       TypeIndex N = *Next;
       Func(N, getType(N));
       Next = getNext(N);
     }
   }
 };
 }
 }
 
 #endif

include/llvm/DebugInfo/CodeView/TypeHashing.h

struct GloballyHashedType {
   GloballyHashedType(StringRef H)
       : GloballyHashedType(ArrayRef<uint8_t>(H.bytes_begin(), H.bytes_end())) {}
   GloballyHashedType(ArrayRef<uint8_t> H) {
     assert(H.size() == 8);
     ::memcpy(Hash.data(), H.data(), 8);
   }
   std::array<uint8_t, 8> Hash;
 
+  bool empty() const { return *(const uint64_t*)Hash.data() == 0; }
+
   /// Given a sequence of bytes representing a record, compute a global hash for
   /// this record.  Due to the nature of global hashes incorporating the hashes
   /// of referenced records, this function requires a list of types and ids
   /// that RecordData might reference, indexable by TypeIndex.
   static GloballyHashedType hashType(ArrayRef<uint8_t> RecordData,
                                      ArrayRef<GloballyHashedType> PreviousTypes,
                                      ArrayRef<GloballyHashedType> PreviousIds);
 
   /// Given a sequence of bytes representing a record, compute a global hash for
   /// this record.  Due to the nature of global hashes incorporating the hashes
   /// of referenced records, this function requires a list of types and ids
   /// that RecordData might reference, indexable by TypeIndex.
   static GloballyHashedType hashType(CVType Type,
                                      ArrayRef<GloballyHashedType> PreviousTypes,
                                      ArrayRef<GloballyHashedType> PreviousIds) {
     return hashType(Type.RecordData, PreviousTypes, PreviousIds);
   }
 
   /// Given a sequence of combined type and ID records, compute global hashes
   /// for each of them, returning the results in a vector of hashed types.
   template <typename Range>
   static std::vector<GloballyHashedType> hashTypes(Range &&Records) {
     std::vector<GloballyHashedType> Hashes;
-    for (const auto &R : Records)
-      Hashes.push_back(hashType(R, Hashes, Hashes));
+    bool ReqSecondPass = false;
+    for (const auto &R : Records) {
+      GloballyHashedType H = hashType(R, Hashes, Hashes);
+      if (H.empty())
+        ReqSecondPass = true;
+      Hashes.push_back(H);
+    }
+    if (ReqSecondPass) {
+      auto HashIt = Hashes.begin();
+      for (const auto &R : Records) {
+        if (HashIt->empty()) {
+          GloballyHashedType H = hashType(R, Hashes, Hashes);
+          assert(!H.empty());
+          *HashIt = H;
+        }
+        ++HashIt;
+      }
+    }
 
     return Hashes;
   }
 
   /// Given a sequence of combined type and ID records, compute global hashes
   /// for each of them, returning the results in a vector of hashed types.
   template <typename Range>
   static std::vector<GloballyHashedType>

include/llvm/DebugInfo/CodeView/TypeTableCollection.h

public:
   Optional<TypeIndex> getFirst() override;
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
 
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
+  ArrayRef<ArrayRef<uint8_t>> records() const override;
 
 private:
   BumpPtrAllocator Allocator;
   StringSaver NameStorage;
   std::vector<StringRef> Names;
   ArrayRef<ArrayRef<uint8_t>> Records;
 };
 }
 }
 
 #endif

include/llvm/Support/BinaryStreamArray.h

public:
   BinaryStreamRef getUnderlyingStream() const { return Stream; }
   void setUnderlyingStream(BinaryStreamRef S, uint32_t Skew = 0) {
     Stream = S;
     this->Skew = Skew;
   }
 
   void drop_front() { Skew += begin()->length(); }
 
+  ArrayRef<uint8_t> getBytes() const {
+    ArrayRef<uint8_t> Buffer;
+    cantFail(Stream.readBytes(Skew, Stream.getLength() - Skew, Buffer));
+    return Buffer;
+  }
+
 private:
   BinaryStreamRef Stream;
   Extractor E;
   uint32_t Skew;
 };
 
 template <typename ValueType, typename Extractor>
 class VarStreamArrayIterator

lib/DebugInfo/CodeView/GlobalTypeTableBuilder.cpp

 ArrayRef<ArrayRef<uint8_t>> GlobalTypeTableBuilder::records() const {
   return SeenRecords;
 }
 
 ArrayRef<GloballyHashedType> GlobalTypeTableBuilder::hashes() const {
   return SeenHashes;
 }
 
-void GlobalTypeTableBuilder::reset() {
-  HashedRecords.clear();
-  SeenRecords.clear();
-}
-
 TypeIndex GlobalTypeTableBuilder::insertRecordBytes(ArrayRef<uint8_t> Record) {
   GloballyHashedType GHT =
       GloballyHashedType::hashType(Record, SeenHashes, SeenHashes);
   return insertRecordAs(GHT, Record.size(),
                         [Record](MutableArrayRef<uint8_t> Data) {
                           assert(Data.size() == Record.size());
                           ::memcpy(Data.data(), Record.data(), Record.size());
                           return Data;

lib/DebugInfo/CodeView/LazyRandomTypeCollection.cpp

LazyRandomTypeCollection::LazyRandomTypeCollection(uint32_t RecordCountHint)
     : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
                                PartialOffsetArray()) {}
 
 LazyRandomTypeCollection::LazyRandomTypeCollection(
     const CVTypeArray &Types, uint32_t RecordCountHint,
     PartialOffsetArray PartialOffsets)
     : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
   Records.resize(RecordCountHint);
-}
-
-LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
-                                                   uint32_t RecordCountHint)
-    : LazyRandomTypeCollection(RecordCountHint) {
-}
-
-LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
-                                                   uint32_t RecordCountHint)
-    : LazyRandomTypeCollection(
-          makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
+  DataRecords.resize(RecordCountHint);
 }
 
 LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
                                                    uint32_t NumRecords)
     : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
 
 void LazyRandomTypeCollection::reset(BinaryStreamReader &Reader,
                                      uint32_t RecordCountHint) {
   Count = 0;
   PartialOffsets = PartialOffsetArray();
 
   error(Reader.readArray(Types, Reader.bytesRemaining()));
 
   // Clear and then resize, to make sure existing data gets destroyed.
   Records.clear();
   Records.resize(RecordCountHint);
+  DataRecords.clear();
+  DataRecords.resize(RecordCountHint);
 }
 
 void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
   BinaryStreamReader Reader(Data, support::little);
   reset(Reader, RecordCountHint);
 }
 
 void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
if (!Records[Index.toArrayIndex()].Type.valid())
     return false;
   return true;
 }
 
 uint32_t LazyRandomTypeCollection::size() { return Count; }
 
 uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
 
+ArrayRef<ArrayRef<uint8_t>> LazyRandomTypeCollection::records() const {
+  return DataRecords;
+}
+
 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
   if (contains(TI))
     return Error::success();
 
   return visitRangeForType(TI);
 }
 
 void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
   assert(!Index.isSimple());
   uint32_t MinSize = Index.toArrayIndex() + 1;
 
   if (MinSize <= capacity())
     return;
 
   uint32_t NewCapacity = MinSize * 3 / 2;
 
   assert(NewCapacity > capacity());
   Records.resize(NewCapacity);
+  DataRecords.resize(NewCapacity);
 }
 
 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
   assert(!TI.isSimple());
   if (PartialOffsets.empty())
     return fullScanForType(TI);
 
   auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
                                [](TypeIndex Value, const TypeIndexOffset &IO) {
                                  return Value < IO.Type;
                                });
 
   assert(Next != PartialOffsets.begin());
   auto Prev = std::prev(Next);
 
   TypeIndex TIB = Prev->Type;
   if (contains(TIB)) {
     // They've asked us to fetch a type index, but the entry we found in the
     // partial offsets array has already been visited.  Since we visit an entire
     // block every time, that means this record should have been previously
-    // discovered.  Ultimately, this means this is a request for a non-existant
+    // discovered.  Ultimately, this means this is a request for a non-existent
     // type index.
     return make_error<CodeViewError>("Invalid type index");
   }
 
   TypeIndex TIE;
   if (Next == PartialOffsets.end()) {
     TIE = TypeIndex::fromArrayIndex(capacity());
   } else {
Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
 
   auto End = Types.end();
   while (Begin != End) {
     ensureCapacityFor(CurrentTI);
     LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
     auto Idx = CurrentTI.toArrayIndex();
     Records[Idx].Type = *Begin;
     Records[Idx].Offset = Begin.offset();
+    DataRecords[Idx] = (*Begin).data();
     ++Count;
     ++Begin;
     ++CurrentTI;
   }
   if (CurrentTI <= TI) {
     return make_error<CodeViewError>("Type Index does not exist!");
   }
   return Error::success();
 }
 
 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
                                           TypeIndex End) {
   auto RI = Types.at(BeginOffset);
   assert(RI != Types.end());
 
   ensureCapacityFor(End);
   while (Begin != End) {
     LargestTypeIndex = std::max(LargestTypeIndex, Begin);
     auto Idx = Begin.toArrayIndex();
     Records[Idx].Type = *RI;
     Records[Idx].Offset = RI.offset();
+    DataRecords[Idx] = (*RI).data();
     ++Count;
     ++Begin;
     ++RI;
   }
 }

lib/DebugInfo/CodeView/TypeHashing.cpp

for (const auto &Ref : Refs) {
 
     auto RefData = RecordData.slice(Ref.Offset, Ref.Count * sizeof(TypeIndex));
     // For each type index referenced, add in the previously computed hash
     // value of that type.
     ArrayRef<TypeIndex> Indices(
         reinterpret_cast<const TypeIndex *>(RefData.data()), Ref.Count);
     for (TypeIndex TI : Indices) {
       ArrayRef<uint8_t> BytesToHash;
-      if (TI.isSimple() || TI.isNoneType() || TI.toArrayIndex() >= Prev.size()) {
+      if (TI.isSimple() || TI.isNoneType()) {
         const uint8_t *IndexBytes = reinterpret_cast<const uint8_t *>(&TI);
         BytesToHash = makeArrayRef(IndexBytes, sizeof(TypeIndex));
       } else {
+        if (TI.toArrayIndex() >= Prev.size()) {
+          // There are forward references to yet-unhashed records. Suspend
+          // hashing for this record until all the other records are processed.
+          return {};
+        }
         BytesToHash = Prev[TI.toArrayIndex()].Hash;
       }
       S.update(BytesToHash);
     }
 
     Off = Ref.Offset + Ref.Count * sizeof(TypeIndex);
   }
 
   // Don't forget to add in any trailing bytes.
   auto TrailingBytes = RecordData.drop_front(Off);
   S.update(TrailingBytes);
 
   return {S.final().take_back(8)};
 }

lib/DebugInfo/CodeView/TypeStreamMerger.cpp

Error TypeStreamMerger::doit(const CVTypeArray &Types) {
   }
 
   if (LastError)
     return std::move(*LastError);
   return Error::success();
 }
 
 Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
-  BinaryStreamRef Stream = Types.getUnderlyingStream();
-  ArrayRef<uint8_t> Buffer;
-  cantFail(Stream.readBytes(0, Stream.getLength(), Buffer));
-
   return forEachCodeViewRecord<CVType>(
-      Buffer, [this](const CVType &T) { return remapType(T); });
+      Types.getBytes(), [this](const CVType &T) { return remapType(T); });
 }
 
 Error TypeStreamMerger::remapType(const CVType &Type) {
   auto R = shouldRemapType(Type);
   if (!R)
     return R.takeError();
 
   TypeIndex DestIdx = Untranslated;

lib/DebugInfo/CodeView/TypeTableCollection.cpp

 
 bool TypeTableCollection::contains(TypeIndex Index) {
   return Index.toArrayIndex() <= size();
 }
 
 uint32_t TypeTableCollection::size() { return Records.size(); }
 
 uint32_t TypeTableCollection::capacity() { return Records.size(); }
+
+ArrayRef<ArrayRef<uint8_t>> TypeTableCollection::records() const {
+  return Records;
+}

lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp

Error TpiStreamBuilder::commit(const msf::MSFLayout &Layout,
 
   auto InfoS = WritableMappedBlockStream::createIndexedStream(Layout, Buffer,
                                                               Idx, Allocator);
 
   BinaryStreamWriter Writer(*InfoS);
   if (auto EC = Writer.writeObject(*Header))
     return EC;
 
-  for (auto Rec : TypeRecords)
+  for (auto Rec : TypeRecords) {
+    assert(!Rec.empty()); // An empty record will not write anything, but it
+                          // will shift all offsets from here on.
     if (auto EC = Writer.writeBytes(Rec))
       return EC;
+  }
 
   if (HashStreamIndex != kInvalidStreamIndex) {
     auto HVS = WritableMappedBlockStream::createIndexedStream(
         Layout, Buffer, HashStreamIndex, Allocator);
     BinaryStreamWriter HW(*HVS);
     if (HashValueStream) {
       if (auto EC = HW.writeStreamRef(*HashValueStream))
         return EC;

test/tools/llvm-readobj/codeview-merging-ghash.test

+# RUN: yaml2obj %s -o=%t.obj
+# RUN: llvm-readobj -codeview-merged-types %t.obj | FileCheck %s --check-prefix=MERGED
+# RUN: llvm-readobj -codeview-merged-types -codeview-ghash %t.obj | FileCheck %s --check-prefix=MERGED
+
+# MERGED: MergedTypeStream [
+# MERGED-NEXT: ArgList (0x1000) {
+# MERGED-NEXT:    TypeLeafKind: LF_ARGLIST (0x1201)
+# MERGED-NEXT:    NumArgs: 0
+# MERGED-NEXT:    Arguments [
+# MERGED-NEXT:    ]
+# MERGED-NEXT:  }
+# MERGED-NEXT:  Procedure (0x1001) {
+# MERGED-NEXT:    TypeLeafKind: LF_PROCEDURE (0x1008)
+# MERGED-NEXT:    ReturnType: void (0x3)
+# MERGED-NEXT:    CallingConvention: NearC (0x0)
+# MERGED-NEXT:    FunctionOptions [ (0x0)
+# MERGED-NEXT:    ]
+# MERGED-NEXT:    NumParameters: 0
+# MERGED-NEXT:    ArgListType: () (0x1000)
+# MERGED-NEXT:  }
+# MERGED-NEXT: ]
+
+--- !COFF
+header:          
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:        
+  - Name:            '.debug$T'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_DISCARDABLE, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    Types:           
+      - Kind:            LF_PROCEDURE
+        Procedure:       
+          ReturnType:      3
+          CallConv:        NearC
+          Options:         [ None ]
+          ParameterCount:  0
+          ArgumentList:    4097
+      - Kind:            LF_ARGLIST
+        ArgList:         
+          ArgIndices:      [  ]
+symbols:         
+...

tools/llvm-readobj/COFFDumper.cpp

public:
   void printCOFFImports() override;
   void printCOFFExports() override;
   void printCOFFDirectives() override;
   void printCOFFBaseReloc() override;
   void printCOFFDebugDirectory() override;
   void printCOFFResources() override;
   void printCOFFLoadConfig() override;
   void printCodeViewDebugInfo() override;
-  void
-  mergeCodeViewTypes(llvm::codeview::MergingTypeTableBuilder &CVIDs,
-                     llvm::codeview::MergingTypeTableBuilder &CVTypes) override;
+  void mergeCodeViewTypes(llvm::codeview::MergingTypeTableBuilder &CVIDs,
+                          llvm::codeview::MergingTypeTableBuilder &CVTypes,
+                          llvm::codeview::GlobalTypeTableBuilder &GlobalCVIDs,
+                          llvm::codeview::GlobalTypeTableBuilder &GlobalCVTypes,
+                          bool GHash) override;
   void printStackMap() const override;
   void printAddrsig() override;
 private:
   void printSymbols() override;
   void printDynamicSymbols() override;
   void printSymbol(const SymbolRef &Sym);
   void printRelocation(const SectionRef &Section, const RelocationRef &Reloc,
                        uint64_t Bias = 0);
StringRef COFFDumper::getFileNameForFileOffset(uint32_t FileOffset) {
   return error(CVStringTable.getString(Iter->FileNameOffset));
 }
 
 void COFFDumper::printFileNameForOffset(StringRef Label, uint32_t FileOffset) {
   W.printHex(Label, getFileNameForFileOffset(FileOffset), FileOffset);
 }
 
 void COFFDumper::mergeCodeViewTypes(MergingTypeTableBuilder &CVIDs,
-                                    MergingTypeTableBuilder &CVTypes) {
+                                    MergingTypeTableBuilder &CVTypes,
+                                    GlobalTypeTableBuilder &GlobalCVIDs,
+                                    GlobalTypeTableBuilder &GlobalCVTypes,
+                                    bool GHash) {
   for (const SectionRef &S : Obj->sections()) {
     StringRef SectionName;
     error(S.getName(SectionName));
     if (SectionName == ".debug$T") {
       StringRef Data;
       error(S.getContents(Data));
       uint32_t Magic;
       error(consume(Data, Magic));
       if (Magic != 4)
         error(object_error::parse_failed);
 
       CVTypeArray Types;
       BinaryStreamReader Reader(Data, llvm::support::little);
       if (auto EC = Reader.readArray(Types, Reader.getLength())) {
         consumeError(std::move(EC));
         W.flush();
         error(object_error::parse_failed);
       }
       SmallVector<TypeIndex, 128> SourceToDest;
       Optional<uint32_t> PCHSignature;
+      if (GHash) {
+        std::vector<GloballyHashedType> Hashes =
+            GloballyHashedType::hashTypes(Types);
+        if (auto EC = mergeTypeAndIdRecords(GlobalCVIDs, GlobalCVTypes, SourceToDest, Types,
+                                            Hashes, PCHSignature))
+          return error(std::move(EC));
+      } else {
         if (auto EC = mergeTypeAndIdRecords(CVIDs, CVTypes, SourceToDest, Types,
                                             PCHSignature))
           return error(std::move(EC));
       }
     }
   }
+}
 
 void COFFDumper::printCodeViewTypeSection(StringRef SectionName,
                                           const SectionRef &Section) {
   ListScope D(W, "CodeViewTypes");
   W.printNumber("Section", SectionName, Obj->getSectionID(Section));
 
   StringRef Data;
   error(Section.getContents(Data));
while (Cur != End) {
     }
 
     W.printNumber("Sym", SymName, SymIndex);
     Cur += Size;
   }
 }
 
 void llvm::dumpCodeViewMergedTypes(
-    ScopedPrinter &Writer, llvm::codeview::MergingTypeTableBuilder &IDTable,
-    llvm::codeview::MergingTypeTableBuilder &CVTypes) {
+    ScopedPrinter &Writer, llvm::codeview::TypeCollection &IDTable,
+    llvm::codeview::TypeCollection &CVTypes) {
   // Flatten it first, then run our dumper on it.
   SmallString<0> TypeBuf;
   CVTypes.ForEachRecord([&](TypeIndex TI, const CVType &Record) {
     TypeBuf.append(Record.RecordData.begin(), Record.RecordData.end());
   });
 
   TypeTableCollection TpiTypes(CVTypes.records());
   {
     ListScope S(Writer, "MergedTypeStream");
     TypeDumpVisitor TDV(TpiTypes, &Writer, opts::CodeViewSubsectionBytes);
     error(codeview::visitTypeStream(TpiTypes, TDV));
     Writer.flush();
   }
 
   // Flatten the id stream and print it next. The ID stream refers to names from

tools/llvm-readobj/ObjDumper.h

 #include "llvm/Support/CommandLine.h"
 
 namespace llvm {
 namespace object {
 class COFFImportFile;
 class ObjectFile;
 }
 namespace codeview {
+class GlobalTypeTableBuilder;
 class MergingTypeTableBuilder;
-}
+class TypeCollection;
+} // namespace codeview
 
 class ScopedPrinter;
 
 class ObjDumper {
 public:
   ObjDumper(ScopedPrinter &Writer);
   virtual ~ObjDumper();
 
public:
   virtual void printCOFFDirectives() { }
   virtual void printCOFFBaseReloc() { }
   virtual void printCOFFDebugDirectory() { }
   virtual void printCOFFResources() {}
   virtual void printCOFFLoadConfig() { }
   virtual void printCodeViewDebugInfo() { }
   virtual void
   mergeCodeViewTypes(llvm::codeview::MergingTypeTableBuilder &CVIDs,
-                     llvm::codeview::MergingTypeTableBuilder &CVTypes) {}
+                     llvm::codeview::MergingTypeTableBuilder &CVTypes,
+                     llvm::codeview::GlobalTypeTableBuilder &GlobalCVIDs,
+                     llvm::codeview::GlobalTypeTableBuilder &GlobalCVTypes,
+                     bool GHash) {}
 
   // Only implemented for MachO.
   virtual void printMachODataInCode() { }
   virtual void printMachOVersionMin() { }
   virtual void printMachODysymtab() { }
   virtual void printMachOSegment() { }
   virtual void printMachOIndirectSymbols() { }
   virtual void printMachOLinkerOptions() { }

 
 std::error_code createWasmDumper(const object::ObjectFile *Obj,
                                  ScopedPrinter &Writer,
                                  std::unique_ptr<ObjDumper> &Result);
 
 void dumpCOFFImportFile(const object::COFFImportFile *File,
                         ScopedPrinter &Writer);
 
-void dumpCodeViewMergedTypes(
-    ScopedPrinter &Writer, llvm::codeview::MergingTypeTableBuilder &IDTable,
-    llvm::codeview::MergingTypeTableBuilder &TypeTable);
+void dumpCodeViewMergedTypes(ScopedPrinter &Writer,
+                             llvm::codeview::TypeCollection &IDTable,
+                             llvm::codeview::TypeCollection &TypeTable);
 
 } // namespace llvm
 
 #endif

tools/llvm-readobj/llvm-readobj.cpp

 // Output should be specialized for each format where appropriate.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm-readobj.h"
 #include "Error.h"
 #include "ObjDumper.h"
 #include "WindowsResourceDumper.h"
+#include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/COFFImportFile.h"
 #include "llvm/Object/MachOUniversal.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Object/WindowsResource.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
namespace opts {
   cl::opt<bool> CodeView("codeview",
                          cl::desc("Display CodeView debug information"));
 
   // -codeview-merged-types
   cl::opt<bool>
       CodeViewMergedTypes("codeview-merged-types",
                           cl::desc("Display the merged CodeView type stream"));
 
+  // -codeview-ghash
+  cl::opt<bool> CodeViewEnableGHash(
+      "codeview-ghash",
+      cl::desc(
+          "Enable global hashing for CodeView type stream de-duplication"));
+
   // -codeview-subsection-bytes
   cl::opt<bool> CodeViewSubsectionBytes(
       "codeview-subsection-bytes",
       cl::desc("Dump raw contents of codeview debug sections and records"));
 
   // -arm-attributes
   cl::opt<bool> ARMAttributes("arm-attributes",
                               cl::desc("Display the ARM attributes section"));
case llvm::Triple::mips64el:
     return true;
   default:
     return false;
   }
 }
 namespace {
 struct ReadObjTypeTableBuilder {
   ReadObjTypeTableBuilder()
-      : Allocator(), IDTable(Allocator), TypeTable(Allocator) {}
+      : Allocator(), IDTable(Allocator), TypeTable(Allocator),
+        GlobalIDTable(Allocator), GlobalTypeTable(Allocator) {}
 
   llvm::BumpPtrAllocator Allocator;
   llvm::codeview::MergingTypeTableBuilder IDTable;
   llvm::codeview::MergingTypeTableBuilder TypeTable;
+  llvm::codeview::GlobalTypeTableBuilder GlobalIDTable;
+  llvm::codeview::GlobalTypeTableBuilder GlobalTypeTable;
 };
-}
+} // namespace
 static ReadObjTypeTableBuilder CVTypes;
 
 /// Creates an format-specific object file dumper.
 static std::error_code createDumper(const ObjectFile *Obj,
                                     ScopedPrinter &Writer,
                                     std::unique_ptr<ObjDumper> &Result) {
   if (!Obj)
     return readobj_error::unsupported_file_format;
if (opts::COFFResources)
       Dumper->printCOFFResources();
     if (opts::COFFLoadConfig)
       Dumper->printCOFFLoadConfig();
     if (opts::Addrsig)
       Dumper->printAddrsig();
     if (opts::CodeView)
       Dumper->printCodeViewDebugInfo();
     if (opts::CodeViewMergedTypes)
-      Dumper->mergeCodeViewTypes(CVTypes.IDTable, CVTypes.TypeTable);
+      Dumper->mergeCodeViewTypes(CVTypes.IDTable, CVTypes.TypeTable,
+                                 CVTypes.GlobalIDTable, CVTypes.GlobalTypeTable,
+                                 opts::CodeViewEnableGHash);
   }
   if (Obj->isMachO()) {
     if (opts::MachODataInCode)
       Dumper->printMachODataInCode();
     if (opts::MachOIndirectSymbols)
       Dumper->printMachOIndirectSymbols();
     if (opts::MachOLinkerOptions)
       Dumper->printMachOLinkerOptions();
else if (ObjectFile *Obj = dyn_cast<ObjectFile>(&Binary))
     dumpObject(Obj, Writer);
   else if (COFFImportFile *Import = dyn_cast<COFFImportFile>(&Binary))
     dumpCOFFImportFile(Import, Writer);
   else if (WindowsResource *WinRes = dyn_cast<WindowsResource>(&Binary))
     dumpWindowsResourceFile(WinRes);
   else
     reportError(File, readobj_error::unrecognized_file_format);
 }
 
 /// Registers aliases that should only be allowed by readobj.
 static void registerReadobjAliases() {
   // -s has meant --sections for a very long time in llvm-readobj despite
   // meaning --symbols in readelf.
   static cl::alias SectionsShort("s", cl::desc("Alias for --section-headers"),
                                  cl::aliasopt(opts::SectionHeaders),
                                  cl::NotHidden);
 
int main(int argc, const char *argv[]) {
   // Default to stdin if no filename is specified.
   if (opts::InputFilenames.empty())
     opts::InputFilenames.push_back("-");
 
   llvm::for_each(opts::InputFilenames, dumpInput);
 
   if (opts::CodeViewMergedTypes) {
     ScopedPrinter W(outs());
+    if (opts::CodeViewEnableGHash)
+      dumpCodeViewMergedTypes(W, CVTypes.GlobalIDTable,
+                              CVTypes.GlobalTypeTable);
+    else
       dumpCodeViewMergedTypes(W, CVTypes.IDTable, CVTypes.TypeTable);
   }
 
   return 0;
 }