[PDB] Emit index/offset pairs for TPI and IPI streams

[rnk]

Summary

This lets PDB readers lookup type record data by type index in O(log n)
time. It also enables makes cvdump -t work on PDBs produced by LLD.
cvdump will not dump a PDB that doesn't have an index-to-offset table.

The table is sorted by type index, and has an entry every 8KB. Looking
up a type record by index is a binary search of this table, followed by
a scan of at most 8KB.

[zturner]

The 8KB thing is interesting, because sometimes it's not actually every 8KB. I don't know how important it is though, since it should just change the efficiency of the log(N) search. Run llvm-pdbdump analyze on a large PDB and then paste the results into Spreadsheets and compute differences to see what I mean.

Anyway, thanks for doing this. I'll review in more detail tomorrow when I'm back.

[zturner]

lld/test/COFF/pdb.test

194 ↗

(On Diff #93982)

I would remove all these values, otherwise it's going to be high maintenance as we add more and more stuff to the PDB and stuff shifts around.

355–356 ↗

(On Diff #93982)

Was this intentional? Seems like we should be able to be reasonably certain that 0 source files contribute to the Linker-generated module.

396 ↗

(On Diff #93982)

Same here and with other numbers that you changed.

500–501 ↗

(On Diff #93982)

Intentional?

565 ↗

(On Diff #93982)

Was this intentionally deleted?

llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp

100 ↗

(On Diff #93982)

s/hash tables/hash values/

llvm/lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp

52–55 ↗

(On Diff #93982)

emplace_back? This way you don't have to use the brace initializer syntax. I think TypeIndex constructor is implicit too, so you might even be able to just write TypeIndexOffsets.emplace_back(codeview::TypeIndex::FirstNonSimpleIndex + TypeRecords.size(), ulittle32_t(TypeRecordBytes));

106–107 ↗

(On Diff #93982)

This looks bogus.

llvm/test/DebugInfo/PDB/pdb-yaml-types.test

29–31 ↗

(On Diff #93982)

Maybe I just never knew you could do this, but can you put random text in the middle of a test file with no comment marker?

[rnk]

lld/test/COFF/pdb.test

10 ↗

(On Diff #93982)

What actually happened with this test is that @ruiu removed the llvm-pdbdump raw FileCheck line in rL291739, and these RAW checks became stale. They were essentially a "golden output" style test that looks at the complete PDB output before I touched it, and that's where all the diffs other than the TypeIndexOffsets diff come from.

I've re-added the RUN line and regenerated the output in this change because I want to look for the TypeIndexOffset goo at the end of the type stream.

Here's what I'm going to do: I'll land this change and update the RAW checks and we can figure out what we want to do about them separately. This change will just add the TypeIndexOffset checks.

llvm/lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp

52–55 ↗

(On Diff #93982)

That doesn't work because TypeIndexOffset is POD. The braced init syntax allows you to make something of that type but you can't construct one by calling the constructor like emplace_back does. At least, that's how I interpret this spew:

[1/4] Building CXX object lib\DebugInfo\PDB\CMakeFiles\LLVMDebugInfoPDB.dir\Native\TpiStreamBuilder.cpp.obj
FAILED: lib/DebugInfo/PDB/CMakeFiles/LLVMDebugInfoPDB.dir/Native/TpiStreamBuilder.cpp.obj
C:\src\llvm-project\build_stage2\bin\clang-cl.exe   /nologo -DGTEST_HAS_RTTI=0 -DLLVM_BUILD_GLOBAL_ISEL -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_DEBUG_POINTER_IMPL="" -D_HAS_EXCEPTIONS=0 -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib\DebugInfo\PDB -IC:\src\llvm-project\llvm\lib\DebugInfo\PDB -Iinclude -IC:\src\llvm-project\llvm\include -I"C:\PROGRA~2\MICROS~1.0\DIA SDK\include" /DWIN32 /D_WINDOWS /W3   /Zc:inline /Zc:strictStrings /Oi /Zc:rvalueCast /Brepro -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -Wcovered-switch-default -Wdelete-non-virtual-dtor -Wstring-conversion /MD /O2 /Ob2   -UNDEBUG  /EHs-c- /GR- /showIncludes /Folib\DebugInfo\PDB\CMakeFiles\LLVMDebugInfoPDB.dir\Native\TpiStreamBuilder.cpp.obj /Fdlib\DebugInfo\PDB\CMakeFiles\LLVMDebugInfoPDB.dir\ -c C:\src\llvm-project\llvm\lib\DebugInfo\PDB\Native\TpiStreamBuilder.cpp
In file included from C:\src\llvm-project\llvm\lib\DebugInfo\PDB\Native\TpiStreamBuilder.cpp:10:
In file included from C:\src\llvm-project\llvm\include\llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h:14:
In file included from C:\src\llvm-project\llvm\include\llvm/DebugInfo/CodeView/TypeRecord.h:13:
In file included from C:\src\llvm-project\llvm\include\llvm/ADT/APSInt.h:18:
In file included from C:\src\llvm-project\llvm\include\llvm/ADT/APInt.h:20:
In file included from C:\src\llvm-project\llvm\include\llvm/Support/MathExtras.h:19:
In file included from C:/PROGRA~2/MICROS~1.0/VC/include\algorithm:6:
In file included from C:/PROGRA~2/MICROS~1.0/VC/include\xmemory:6:
C:/PROGRA~2/MICROS~1.0/VC/include\xmemory0(737,24):  error: no matching constructor for initialization of 'llvm::pdb::TypeIndexOffset'
                ::new ((void *)_Ptr) _Objty(_STD forward<_Types>(_Args)...);
                                     ^      ~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA~2/MICROS~1.0/VC/include\xmemory0(857,7):  note: in instantiation of function template specialization 'std::allocator<llvm::pdb::TypeIndexOffset>::construct<llvm::pdb::TypeIndexOffset, llvm::codeview::TypeIndex, llvm::support::detail::packed_endian_specific_integral<unsigned int, llvm::support::endianness::little, 1> >' requested here
                _Al.construct(_Ptr, _STD forward<_Types>(_Args)...);
                    ^
C:/PROGRA~2/MICROS~1.0/VC/include\xmemory0(995,14):  note: in instantiation of function template specialization 'std::allocator_traits<std::allocator<llvm::pdb::TypeIndexOffset> >::construct<llvm::pdb::TypeIndexOffset, llvm::codeview::TypeIndex, llvm::support::detail::packed_endian_specific_integral<unsigned int, llvm::support::endianness::little, 1> >' requested here
                _Mytraits::construct(*this, _Ptr,
                           ^
C:/PROGRA~2/MICROS~1.0/VC/include\vector(929,18):  note: in instantiation of function template specialization 'std::_Wrap_alloc<std::allocator<llvm::pdb::TypeIndexOffset> >::construct<llvm::pdb::TypeIndexOffset, llvm::codeview::TypeIndex, llvm::support::detail::packed_endian_specific_integral<unsigned int, llvm::support::endianness::little, 1> >' requested here
                this->_Getal().construct(_Unfancy(this->_Mylast()),
                               ^
C:\src\llvm-project\llvm\lib\DebugInfo\PDB\Native\TpiStreamBuilder.cpp(52,22):  note: in instantiation of function template specialization 'std::vector<llvm::pdb::TypeIndexOffset, std::allocator<llvm::pdb::TypeIndexOffset> >::emplace_back<llvm::codeview::TypeIndex, llvm::support::detail::packed_endian_specific_integral<unsigned int, llvm::support::endianness::little, 1> >' requested here
    TypeIndexOffsets.emplace_back(
                     ^
C:\src\llvm-project\llvm\include\llvm/DebugInfo/PDB/Native/RawTypes.h(78,8):  note: candidate constructor (the implicit copy constructor) not viable: requires 1 argument, but 2 were provided
struct TypeIndexOffset {
       ^
C:\src\llvm-project\llvm\include\llvm/DebugInfo/PDB/Native/RawTypes.h(78,8):  note: candidate constructor (the implicit move constructor) not viable: requires 1 argument, but 2 were provided
C:\src\llvm-project\llvm\include\llvm/DebugInfo/PDB/Native/RawTypes.h(78,8):  note: candidate constructor (the implicit default constructor) not viable: requires 0 arguments, but 2 were provided

llvm/test/DebugInfo/PDB/pdb-yaml-types.test

29–31 ↗

(On Diff #93982)

Yeah, .test isn't really a file type, it's just an extension that identifies a text file that should get run by lit. lit looks for RUN:, and FileCheck looks for CHECK:, and if you don't use the test as a source file, you don't need comment markers. I could get rid of ; before RUN, I guess.

[rnk]

comments

lld/trunk/test/COFF/pdb.test

 # RAW-NEXT:         CallingConvention: NearC (0x0)
 # RAW-NEXT:         FunctionOptions [ (0x0)
 # RAW-NEXT:         ]
 # RAW-NEXT:         NumParameters: 0
 # RAW-NEXT:         ArgListType: (<no type>) (0x1003)
 # RAW-NEXT:       }
 # RAW-NEXT:     }
 # RAW-NEXT:     TypeIndexOffsets [
+# RAW-NEXT:       Index: 0x1000, Offset: 0
 # RAW-NEXT:     ]
 # RAW-NEXT:   ]
 # RAW-NEXT: }
 # RAW-NEXT: DBI Stream {
 # RAW-NEXT:   Dbi Version: 20091201
 # RAW-NEXT:   Age: 1
 # RAW-NEXT:   Incremental Linking: No
 # RAW-NEXT:   Has CTypes: No

llvm/trunk/include/llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h

 //===- TpiStreamBuilder.h - PDB Tpi Stream Creation -------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_PDB_RAW_PDBTPISTREAMBUILDER_H
 #define LLVM_DEBUGINFO_PDB_RAW_PDBTPISTREAMBUILDER_H
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/PDB/Native/RawConstants.h"
+#include "llvm/DebugInfo/PDB/Native/RawTypes.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/BinaryItemStream.h"
 #include "llvm/Support/BinaryStreamRef.h"
 #include "llvm/Support/Error.h"
 
 #include <vector>
 
public:
   Error finalizeMsfLayout();
 
   Error commit(const msf::MSFLayout &Layout, WritableBinaryStreamRef Buffer);
 
   uint32_t calculateSerializedLength();
 
 private:
   uint32_t calculateHashBufferSize() const;
+  uint32_t calculateIndexOffsetSize() const;
   Error finalize();
 
   msf::MSFBuilder &Msf;
   BumpPtrAllocator &Allocator;
 
   size_t TypeRecordBytes = 0;
 
   Optional<PdbRaw_TpiVer> VerHeader;
   std::vector<ArrayRef<uint8_t>> TypeRecords;
   std::vector<uint32_t> TypeHashes;
+  std::vector<TypeIndexOffset> TypeIndexOffsets;
   uint32_t HashStreamIndex = kInvalidStreamIndex;
   std::unique_ptr<BinaryByteStream> HashValueStream;
 
   const TpiStreamHeader *Header;
   uint32_t Idx;
 };
 }
 }
 
 #endif

llvm/trunk/lib/DebugInfo/PDB/Native/TpiStream.cpp

if (Header->HashStreamIndex != kInvalidStreamIndex) {
     if (Header->HashStreamIndex >= Pdb.getNumStreams())
       return make_error<RawError>(raw_error_code::corrupt_file,
                                   "Invalid TPI hash stream index.");
 
     auto HS = MappedBlockStream::createIndexedStream(
         Pdb.getMsfLayout(), Pdb.getMsfBuffer(), Header->HashStreamIndex);
     BinaryStreamReader HSR(*HS);
 
+    // There should be a hash value for every type record, or no hashes at all.
     uint32_t NumHashValues =
         Header->HashValueBuffer.Length / sizeof(ulittle32_t);
-    if (NumHashValues != NumTypeRecords())
+    if (NumHashValues != NumTypeRecords() && NumHashValues != 0)
       return make_error<RawError>(
           raw_error_code::corrupt_file,
           "TPI hash count does not match with the number of type records.");
     HSR.setOffset(Header->HashValueBuffer.Off);
     if (auto EC = HSR.readArray(HashValues, NumHashValues))
       return EC;
     std::vector<ulittle32_t> HashValueList;
     for (auto I : HashValues)
if (Header->HashAdjBuffer.Length > 0) {
       if (auto EC = HashAdjusters.load(HSR))
         return EC;
     }
 
     HashStream = std::move(HS);
 
     // TPI hash table is a parallel array for the type records.
     // Verify that the hash values match with type records.
+    if (NumHashValues > 0)
       if (auto EC = verifyHashValues())
         return EC;
   }
 
   return Error::success();
 }
 
 PdbRaw_TpiVer TpiStream::getTpiVersion() const {
   uint32_t Value = Header->Version;
   return static_cast<PdbRaw_TpiVer>(Value);

llvm/trunk/lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp

 TpiStreamBuilder::~TpiStreamBuilder() = default;
 
 void TpiStreamBuilder::setVersionHeader(PdbRaw_TpiVer Version) {
   VerHeader = Version;
 }
 
 void TpiStreamBuilder::addTypeRecord(ArrayRef<uint8_t> Record,
                                      Optional<uint32_t> Hash) {
-  TypeRecordBytes += Record.size();
+  // If we just crossed an 8KB threshold, add a type index offset.
+  size_t NewSize = TypeRecordBytes + Record.size();
+  constexpr size_t EightKB = 8 * 1024;
+  if (NewSize / EightKB > TypeRecordBytes / EightKB || TypeRecords.empty()) {
+    TypeIndexOffsets.push_back(
+        {codeview::TypeIndex(codeview::TypeIndex::FirstNonSimpleIndex +
+                             TypeRecords.size()),
+         ulittle32_t(TypeRecordBytes)});
+  }
+  TypeRecordBytes = NewSize;
+
   TypeRecords.push_back(Record);
   if (Hash)
     TypeHashes.push_back(*Hash);
 }
 
 Error TpiStreamBuilder::finalize() {
   if (Header)
     return Error::success();
 
   TpiStreamHeader *H = Allocator.Allocate<TpiStreamHeader>();
 
   uint32_t Count = TypeRecords.size();
-  uint32_t HashBufferSize = calculateHashBufferSize();
 
   H->Version = *VerHeader;
   H->HeaderSize = sizeof(TpiStreamHeader);
   H->TypeIndexBegin = codeview::TypeIndex::FirstNonSimpleIndex;
   H->TypeIndexEnd = H->TypeIndexBegin + Count;
   H->TypeRecordBytes = TypeRecordBytes;
 
   H->HashStreamIndex = HashStreamIndex;
   H->HashAuxStreamIndex = kInvalidStreamIndex;
   H->HashKeySize = sizeof(ulittle32_t);
   H->NumHashBuckets = MinTpiHashBuckets;
 
   // Recall that hash values go into a completely different stream identified by
   // the `HashStreamIndex` field of the `TpiStreamHeader`.  Therefore, the data
   // begins at offset 0 of this independent stream.
   H->HashValueBuffer.Off = 0;
-  H->HashValueBuffer.Length = HashBufferSize;
+  H->HashValueBuffer.Length = calculateHashBufferSize();
+
+  // We never write any adjustments into our PDBs, so this is usually some
+  // offset with zero length.
   H->HashAdjBuffer.Off = H->HashValueBuffer.Off + H->HashValueBuffer.Length;
   H->HashAdjBuffer.Length = 0;
+
   H->IndexOffsetBuffer.Off = H->HashAdjBuffer.Off + H->HashAdjBuffer.Length;
-  H->IndexOffsetBuffer.Length = 0;
+  H->IndexOffsetBuffer.Length = calculateIndexOffsetSize();
 
   Header = H;
   return Error::success();
 }
 
 uint32_t TpiStreamBuilder::calculateSerializedLength() {
   return sizeof(TpiStreamHeader) + TypeRecordBytes;
 }
 
 uint32_t TpiStreamBuilder::calculateHashBufferSize() const {
-  assert(TypeHashes.size() == TypeHashes.size() &&
+  assert((TypeRecords.size() == TypeHashes.size() || TypeHashes.empty()) &&
          "either all or no type records should have hashes");
   return TypeHashes.size() * sizeof(ulittle32_t);
 }
 
+uint32_t TpiStreamBuilder::calculateIndexOffsetSize() const {
+  return TypeIndexOffsets.size() * sizeof(TypeIndexOffset);
+}
+
 Error TpiStreamBuilder::finalizeMsfLayout() {
   uint32_t Length = calculateSerializedLength();
   if (auto EC = Msf.setStreamSize(Idx, Length))
     return EC;
 
-  uint32_t HashBufferSize = calculateHashBufferSize();
+  uint32_t HashStreamSize =
+      calculateHashBufferSize() + calculateIndexOffsetSize();
 
-  if (HashBufferSize == 0)
+  if (HashStreamSize == 0)
     return Error::success();
 
-  auto ExpectedIndex = Msf.addStream(HashBufferSize);
+  auto ExpectedIndex = Msf.addStream(HashStreamSize);
   if (!ExpectedIndex)
     return ExpectedIndex.takeError();
   HashStreamIndex = *ExpectedIndex;
+  if (!TypeHashes.empty()) {
     ulittle32_t *H = Allocator.Allocate<ulittle32_t>(TypeHashes.size());
     MutableArrayRef<ulittle32_t> HashBuffer(H, TypeHashes.size());
     for (uint32_t I = 0; I < TypeHashes.size(); ++I) {
       HashBuffer[I] = TypeHashes[I] % MinTpiHashBuckets;
     }
-  ArrayRef<uint8_t> Bytes(reinterpret_cast<const uint8_t *>(HashBuffer.data()),
-                          HashBufferSize);
+    ArrayRef<uint8_t> Bytes(
+        reinterpret_cast<const uint8_t *>(HashBuffer.data()),
+        calculateHashBufferSize());
     HashValueStream =
         llvm::make_unique<BinaryByteStream>(Bytes, llvm::support::little);
+  }
   return Error::success();
 }
 
 Error TpiStreamBuilder::commit(const msf::MSFLayout &Layout,
                                WritableBinaryStreamRef Buffer) {
   if (auto EC = finalize())
     return EC;
 
   auto InfoS =
       WritableMappedBlockStream::createIndexedStream(Layout, Buffer, Idx);
 
   BinaryStreamWriter Writer(*InfoS);
   if (auto EC = Writer.writeObject(*Header))
     return EC;
 
   for (auto Rec : TypeRecords)
     if (auto EC = Writer.writeBytes(Rec))
       return EC;
 
   if (HashStreamIndex != kInvalidStreamIndex) {
     auto HVS = WritableMappedBlockStream::createIndexedStream(Layout, Buffer,
                                                               HashStreamIndex);
     BinaryStreamWriter HW(*HVS);
+    if (HashValueStream) {
       if (auto EC = HW.writeStreamRef(*HashValueStream))
         return EC;
     }
 
+    for (auto &IndexOffset : TypeIndexOffsets) {
+      if (auto EC = HW.writeObject(IndexOffset))
+        return EC;
+    }
+  }
+
   return Error::success();
 }

llvm/trunk/test/DebugInfo/PDB/pdb-yaml-types.test

+RUN: llvm-pdbdump pdb2yaml -tpi-stream %p/Inputs/big-read.pdb > %t.yaml
+RUN: FileCheck -check-prefix=YAML %s < %t.yaml
+RUN: llvm-pdbdump yaml2pdb %t.yaml -pdb %t.pdb
+RUN: llvm-pdbdump raw -tpi-records %t.pdb | FileCheck %s --check-prefix=PDB
+
+Only verify the beginning of the type stream.
+
+YAML:      TpiStream:       
+YAML-NEXT:   Version:         VC80
+YAML-NEXT:   Records:         
+YAML-NEXT:     - Kind:            LF_ARGLIST
+YAML-NEXT:       ArgList:         
+YAML-NEXT:         ArgIndices:      [  ]
+YAML-NEXT:     - Kind:            LF_PROCEDURE
+YAML-NEXT:       Procedure:       
+YAML-NEXT:         ReturnType:      3
+YAML-NEXT:         CallConv:        NearC
+YAML-NEXT:         Options:         [ None ]
+YAML-NEXT:         ParameterCount:  0
+YAML-NEXT:         ArgumentList:    4096
+YAML-NEXT:     - Kind:            LF_PROCEDURE
+YAML-NEXT:       Procedure:       
+YAML-NEXT:         ReturnType:      116
+YAML-NEXT:         CallConv:        NearC
+YAML-NEXT:         Options:         [ None ]
+YAML-NEXT:         ParameterCount:  0
+YAML-NEXT:         ArgumentList:    4096
+
+This test is mostly checking to make sure we include the type index offset
+table, and eventually hash codes. The type index offsets should be similar to
+what are already present in big-read.pdb.
+
+PDB:      Type Info Stream (TPI) {
+PDB-NEXT:   TPI Version: 20040203
+PDB-NEXT:   Record count: 728
+PDB-NEXT:   Records [
+PDB-NEXT:     {
+PDB-NEXT:       ArgList (0x1000) {
+PDB-NEXT:         TypeLeafKind: LF_ARGLIST (0x1201)
+PDB-NEXT:         NumArgs: 0
+PDB-NEXT:         Arguments [
+PDB-NEXT:         ]
+PDB-NEXT:       }
+PDB-NEXT:     }
+PDB-NEXT:     {
+PDB-NEXT:       Procedure (0x1001) {
+PDB-NEXT:         TypeLeafKind: LF_PROCEDURE (0x1008)
+PDB-NEXT:         ReturnType: void (0x3)
+PDB-NEXT:         CallingConvention: NearC (0x0)
+PDB-NEXT:         FunctionOptions [ (0x0)
+PDB-NEXT:         ]
+PDB-NEXT:         NumParameters: 0
+PDB-NEXT:         ArgListType: () (0x1000)
+PDB-NEXT:       }
+PDB-NEXT:     }
+PDB-NEXT:     {
+PDB-NEXT:       Procedure (0x1002) {
+PDB-NEXT:         TypeLeafKind: LF_PROCEDURE (0x1008)
+PDB-NEXT:         ReturnType: int (0x74)
+PDB-NEXT:         CallingConvention: NearC (0x0)
+PDB-NEXT:         FunctionOptions [ (0x0)
+PDB-NEXT:         ]
+PDB-NEXT:         NumParameters: 0
+PDB-NEXT:         ArgListType: () (0x1000)
+PDB-NEXT:       }
+PDB-NEXT:     }
+...
+PDB:          TypeIndexOffsets [
+PDB-NEXT:       Index: 0x1000, Offset: 0
+PDB-NEXT:       Index: 0x106c, Offset: 8,116
+PDB-NEXT:       Index: 0x1118, Offset: 16,372
+PDB-NEXT:       Index: 0x11df, Offset: 24,564
+PDB-NEXT:       Index: 0x128e, Offset: 32,752
+PDB-NEXT:     ]