Support skewed Stream Arrays

[zturner]

Summary

VarStreamArray was built on the assumption that it is backed by a StreamRef, and offset 0 of that StreamRef is the first byte of the first record in the array.

This is a logical and intuitive assumption, but unfortunately we have use cases where it doesn't hold. Specifically, a PDB module's symbol stream is prefixed by 4 bytes containing a magic value, and the first byte of record data in the array is actually at offset 4 of this byte sequence.

Previously, we would just truncate the first 4 bytes and then construct the VarStreamArray with the resulting StreamRef, so that offset 0 of the underlying stream did correspond to the first byte of the first record, but this is problematic, because symbol records reference other symbol records by the absolute offset including that initial magic 4 bytes. So if another record wants to refer to the first record in the array, it would say "the record at offset 4".

This led to extremely confusing hacks and semantics in loading code, and after spending 30 minutes trying to get some math right and failing, I decided to fix this in the underlying implementation of VarStreamArray. Now, we can say that a stream is skewed by a particular amount. This way, when we access a record by absolute offset, we can use the same values that the records themselves contain, instead of having to do fixups.

[aganea]

LGTM, thank you for cleaning that up!

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

60 ↗

(On Diff #176888)

Could you please indicate in a comment what sizeof(uint32_t) refers to? Eg.

if (auto EC = SymbolReader.readArray(
        SymbolArray, SymbolReader.bytesRemaining(), /*skip Signature*/ sizeof(uint32_t)))

[aganea]

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

50 ↗

(On Diff #176888)

Maybe a one-line explanation would be needed here too? To explain why we're reading the Signature, then reseting, the reading the whole stream?

[amccarth]

If there is a magic value, should we be checking it?

Does the skew need to be taken into account in any existing boundary checks?

lldb/trunk/source/Plugins/SymbolFile/NativePDB/PdbIndex.cpp

199

So is the above comment obsolete now?

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

60

Perhaps a comment should go here to explain that the sizeof(uint32_t) accounts for CodeView's magic value at the beginning of the stream.

lldb/trunk/source/Plugins/SymbolFile/NativePDB/PdbIndex.cpp

void PdbIndex::BuildAddrToSymbolMap(CompilandIndexItem &cci) {
   const CVSymbolArray &syms = cci.m_debug_stream.getSymbolArray();
   for (auto iter = syms.begin(); iter != syms.end(); ++iter) {
     if (!SymbolHasAddress(*iter))
       continue;
 
     SegmentOffset so = GetSegmentAndOffset(*iter);
     lldb::addr_t va = MakeVirtualAddress(so);
 
-    // We need to add 4 here to adjust for the codeview debug magic
-    // at the beginning of the debug info stream.
-    uint32_t sym_offset = iter.offset() + 4;
-    PdbCompilandSymId cu_sym_id(modi, sym_offset);
+    PdbCompilandSymId cu_sym_id(modi, iter.offset());
 
     // If the debug info is incorrect, we could have multiple symbols with the
     // same address.  So use try_emplace instead of insert, and the first one
     // will win.
     auto insert_result =
         cci.m_symbols_by_va.insert(std::make_pair(va, PdbSymUid(cu_sym_id)));
     (void)insert_result;
 
if (va >= start && va < end)
       result.push_back({std::move(sym), iter->second});
   }
 
   return result;
 }
 
 CVSymbol PdbIndex::ReadSymbolRecord(PdbCompilandSymId cu_sym) const {
   // We need to subtract 4 here to adjust for the codeview debug magic
   // at the beginning of the debug info stream.
   const CompilandIndexItem *cci = compilands().GetCompiland(cu_sym.modi);
-  auto iter = cci->m_debug_stream.getSymbolArray().at(cu_sym.offset - 4);
+  auto iter = cci->m_debug_stream.getSymbolArray().at(cu_sym.offset);
   lldbassert(iter != cci->m_debug_stream.getSymbolArray().end());
   return *iter;
 }

llvm/trunk/include/llvm/Support/BinaryStreamArray.h

 
 public:
   typedef VarStreamArrayIterator<ValueType, Extractor> Iterator;
 
   VarStreamArray() = default;
 
   explicit VarStreamArray(const Extractor &E) : E(E) {}
 
-  explicit VarStreamArray(BinaryStreamRef Stream) : Stream(Stream) {}
+  explicit VarStreamArray(BinaryStreamRef Stream, uint32_t Skew = 0)
+      : Stream(Stream), Skew(Skew) {}
 
-  VarStreamArray(BinaryStreamRef Stream, const Extractor &E)
-      : Stream(Stream), E(E) {}
+  VarStreamArray(BinaryStreamRef Stream, const Extractor &E, uint32_t Skew = 0)
+      : Stream(Stream), E(E), Skew(Skew) {}
 
   Iterator begin(bool *HadError = nullptr) const {
-    return Iterator(*this, E, HadError);
+    return Iterator(*this, E, Skew, nullptr);
   }
 
   bool valid() const { return Stream.valid(); }
 
+  uint32_t skew() const { return Skew; }
   Iterator end() const { return Iterator(E); }
 
   bool empty() const { return Stream.getLength() == 0; }
 
   /// given an offset into the array's underlying stream, return an
   /// iterator to the record at that offset.  This is considered unsafe
   /// since the behavior is undefined if \p Offset does not refer to the
   /// beginning of a valid record.
   Iterator at(uint32_t Offset) const {
     return Iterator(*this, E, Offset, nullptr);
   }
 
   const Extractor &getExtractor() const { return E; }
   Extractor &getExtractor() { return E; }
 
   BinaryStreamRef getUnderlyingStream() const { return Stream; }
-  void setUnderlyingStream(BinaryStreamRef S) { Stream = S; }
+  void setUnderlyingStream(BinaryStreamRef S, uint32_t Skew = 0) {
+    Stream = S;
+    this->Skew = Skew;
+  }
 
   void drop_front() { Stream = Stream.drop_front(begin()->length()); }
 
 private:
   BinaryStreamRef Stream;
   Extractor E;
+  uint32_t Skew;
 };
 
 template <typename ValueType, typename Extractor>
 class VarStreamArrayIterator
     : public iterator_facade_base<VarStreamArrayIterator<ValueType, Extractor>,
                                   std::forward_iterator_tag, ValueType> {
   typedef VarStreamArrayIterator<ValueType, Extractor> IterType;
   typedef VarStreamArray<ValueType, Extractor> ArrayType;
 
 public:
   VarStreamArrayIterator(const ArrayType &Array, const Extractor &E,
-                         bool *HadError)
-      : VarStreamArrayIterator(Array, E, 0, HadError) {}
-
-  VarStreamArrayIterator(const ArrayType &Array, const Extractor &E,
                          uint32_t Offset, bool *HadError)
       : IterRef(Array.Stream.drop_front(Offset)), Extract(E),
         Array(&Array), AbsOffset(Offset), HadError(HadError) {
     if (IterRef.getLength() == 0)
       moveToEnd();
     else {
       auto EC = Extract(IterRef, ThisLen, ThisValue);
       if (EC) {

llvm/trunk/include/llvm/Support/BinaryStreamReader.h

public:
   /// \p Array.  Updates the stream's offset to point after the newly read
   /// array.  Never causes a copy (although iterating the elements of the
   /// VarStreamArray may, depending upon the implementation of the underlying
   /// stream).
   ///
   /// \returns a success error code if the data was successfully read, otherwise
   /// returns an appropriate error code.
   template <typename T, typename U>
-  Error readArray(VarStreamArray<T, U> &Array, uint32_t Size) {
+  Error readArray(VarStreamArray<T, U> &Array, uint32_t Size,
+                  uint32_t Skew = 0) {
     BinaryStreamRef S;
     if (auto EC = readStreamRef(S, Size))
       return EC;
-    Array.setUnderlyingStream(S);
+    Array.setUnderlyingStream(S, Skew);
     return Error::success();
   }
 
   /// Read a FixedStreamArray of \p NumItems elements and store the result into
   /// \p Array.  Updates the stream's offset to point after the newly read
   /// array.  Never causes a copy (although iterating the elements of the
   /// FixedStreamArray may, depending upon the implementation of the underlying
   /// stream).

llvm/trunk/lib/DebugInfo/CodeView/CVSymbolVisitor.cpp

if (auto EC = visitSymbolRecord(I))
       return EC;
   }
   return Error::success();
 }
 
 Error CVSymbolVisitor::visitSymbolStream(const CVSymbolArray &Symbols,
                                          uint32_t InitialOffset) {
   for (auto I : Symbols) {
-    if (auto EC = visitSymbolRecord(I, InitialOffset))
+    if (auto EC = visitSymbolRecord(I, InitialOffset + Symbols.skew()))
       return EC;
     InitialOffset += I.length();
   }
   return Error::success();
 }

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

Error ModuleDebugStreamRef::reload() {
   if (C11Size > 0 && C13Size > 0)
     return make_error<RawError>(raw_error_code::corrupt_file,
                                 "Module has both C11 and C13 line info");
 
   BinaryStreamRef S;
 
   if (auto EC = Reader.readInteger(Signature))
     return EC;
-  if (auto EC = Reader.readSubstream(SymbolsSubstream, SymbolSize - 4))
+  Reader.setOffset(0);
+  if (auto EC = Reader.readSubstream(SymbolsSubstream, SymbolSize))
     return EC;
   if (auto EC = Reader.readSubstream(C11LinesSubstream, C11Size))
     return EC;
   if (auto EC = Reader.readSubstream(C13LinesSubstream, C13Size))
     return EC;
 
   BinaryStreamReader SymbolReader(SymbolsSubstream.StreamData);
-  if (auto EC =
-          SymbolReader.readArray(SymbolArray, SymbolReader.bytesRemaining()))
+  if (auto EC = SymbolReader.readArray(
+          SymbolArray, SymbolReader.bytesRemaining(), sizeof(uint32_t)))
     return EC;
 
   BinaryStreamReader SubsectionsReader(C13LinesSubstream.StreamData);
   if (auto EC = SubsectionsReader.readArray(Subsections,
                                             SubsectionsReader.bytesRemaining()))
     return EC;
 
   uint32_t GlobalRefsSize;

 }
 
 iterator_range<codeview::CVSymbolArray::Iterator>
 ModuleDebugStreamRef::symbols(bool *HadError) const {
   return make_range(SymbolArray.begin(HadError), SymbolArray.end());
 }
 
 CVSymbol ModuleDebugStreamRef::readSymbolAtOffset(uint32_t Offset) const {
-  // Offsets include the size of the 4-byte magic at the beginning, but lookup
-  // doesn't take that into account, so subtract it here.
-  auto Iter = SymbolArray.at(Offset - 4);
+  auto Iter = SymbolArray.at(Offset);
   assert(Iter != SymbolArray.end());
   return *Iter;
 }
 
 iterator_range<ModuleDebugStreamRef::DebugSubsectionIterator>
 ModuleDebugStreamRef::subsections() const {
   return make_range(Subsections.begin(), Subsections.end());
 }

llvm/trunk/test/DebugInfo/PDB/module-bytes.test

 SPLIT-CHUNKS-NEXT:       checksums (
 SPLIT-CHUNKS-NEXT:         6108: F4000000 18000000 56000000 1001A0A5 BD0D3ECD 93FC29D1 9DE826FB F4BC0000  |........V.........>...)...&.....|
 SPLIT-CHUNKS-NEXT:       )
 
 SYMS:                             Module Symbols
 SYMS-NEXT: ============================================================
 SYMS-NEXT:     Mod 0000 | `d:\src\llvm\test\DebugInfo\PDB\Inputs\empty.obj`:
 SYMS-NEXT:       Symbols (
-SYMS-NEXT:         6004: 36000111 00000000 643A5C73 72635C6C 6C766D5C 74657374 5C446562 7567496E  |6.......d:\src\llvm\test\DebugIn|
-SYMS-NEXT:         6024: 666F5C50 44425C49 6E707574 735C656D 7074792E 6F626A00 3A003C11 01200000  |fo\PDB\Inputs\empty.obj.:.<.. ..|
-SYMS-NEXT:         6044: 07001200 00007D79 00001200 00007D79 00004D69 63726F73 6F667420 28522920  |......}y......}y..Microsoft (R) |
-SYMS-NEXT:         6064: 4F707469 6D697A69 6E672043 6F6D7069 6C657200 2A001011 00000000 C4000000  |Optimizing Compiler.*...........|
-SYMS-NEXT:         6084: 00000000 0A000000 03000000 08000000 01100000 10000000 0100016D 61696E00  |...........................main.|
-SYMS-NEXT:         60A4: 1E001210 00000000 00000000 00000000 00000000 00000000 00000082 12000000  |................................|
-SYMS-NEXT:         60C4: 02000600 06004C11 0E100000                                               |......L.....|
+SYMS-NEXT:         6000: 04000000 36000111 00000000 643A5C73 72635C6C 6C766D5C 74657374 5C446562  |....6.......d:\src\llvm\test\Deb|
+SYMS-NEXT:         6020: 7567496E 666F5C50 44425C49 6E707574 735C656D 7074792E 6F626A00 3A003C11  |ugInfo\PDB\Inputs\empty.obj.:.<.|
+SYMS-NEXT:         6040: 01200000 07001200 00007D79 00001200 00007D79 00004D69 63726F73 6F667420  |. ........}y......}y..Microsoft |
+SYMS-NEXT:         6060: 28522920 4F707469 6D697A69 6E672043 6F6D7069 6C657200 2A001011 00000000  |(R) Optimizing Compiler.*.......|
+SYMS-NEXT:         6080: C4000000 00000000 0A000000 03000000 08000000 01100000 10000000 0100016D  |...............................m|
+SYMS-NEXT:         60A0: 61696E00 1E001210 00000000 00000000 00000000 00000000 00000000 00000082  |ain.............................|
+SYMS-NEXT:         60C0: 12000000 02000600 06004C11 0E100000                                      |..........L.....|
 SYMS-NEXT:       )
 SYMS-NEXT:     Mod 0001 | `* Linker *`:
 SYMS-NEXT:       Symbols (
-SYMS-NEXT:         7004: 12000111 00000000 2A204C69 6E6B6572 202A0000 2E003C11 07000000 03000000  |........* Linker *....<.........|
-SYMS-NEXT:         7024: 00000000 00000C00 00007D79 00004D69 63726F73 6F667420 28522920 4C494E4B  |..........}y..Microsoft (R) LINK|
-SYMS-NEXT:         7044: 00000000 AA003D11 00637764 00643A5C 7372635C 6C6C766D 5C746573 745C4465  |......=..cwd.d:\src\llvm\test\De|
-SYMS-NEXT:         7064: 62756749 6E666F5C 5044425C 496E7075 74730065 78650043 3A5C5072 6F677261  |bugInfo\PDB\Inputs.exe.C:\Progra|
-SYMS-NEXT:         7084: 6D204669 6C657320 28783836 295C4D69 63726F73 6F667420 56697375 616C2053  |m Files (x86)\Microsoft Visual S|
-SYMS-NEXT:         70A4: 74756469 6F203132 2E305C56 435C4249 4E5C6C69 6E6B2E65 78650070 64620064  |tudio 12.0\VC\BIN\link.exe.pdb.d|
-SYMS-NEXT:         70C4: 3A5C7372 635C6C6C 766D5C74 6573745C 44656275 67496E66 6F5C5044 425C496E  |:\src\llvm\test\DebugInfo\PDB\In|
-SYMS-NEXT:         70E4: 70757473 5C656D70 74792E70 64620000 12002C11 00000500 05000000 10000000  |puts\empty.pdb....,.............|
-SYMS-NEXT:         7104: 01000100 1A003611 01000C00 00100000 1A100000 20000060 2E746578 74000000  |......6............. ..`.text...|
-SYMS-NEXT:         7124: 1A003711 1A100000 20000060 00000000 01002E74 65787424 6D6E0000 1A003611  |..7..... ..`.......text$mn....6.|
-SYMS-NEXT:         7144: 02000C00 00300000 B2020000 40000040 2E726461 74610000 1A003711 43010000  |.....0......@..@.rdata....7.C...|
-SYMS-NEXT:         7164: 40000040 00000000 02002E72 64617461 00000000 1A003711 00000000 40000040  |@..@.......rdata......7.....@..@|
-SYMS-NEXT:         7184: 43010000 02002E65 64617461 00000000 1E003711 6E010000 40000040 44010000  |C......edata......7.n...@..@D...|
-SYMS-NEXT:         71A4: 02002E72 64617461 24646562 75670000 1A003611 03000C00 00400000 04000000  |...rdata$debug....6......@......|
-SYMS-NEXT:         71C4: 400000C0 2E646174 61000000 16003711 04000000 800000C0 00000000 03002E62  |@....data.....7................b|
-SYMS-NEXT:         71E4: 73730000 1A003611 04000C00 00500000 08000000 40000042 2E72656C 6F630000  |ss....6......P......@..B.reloc..|
+SYMS-NEXT:         7000: 04000000 12000111 00000000 2A204C69 6E6B6572 202A0000 2E003C11 07000000  |............* Linker *....<.....|
+SYMS-NEXT:         7020: 03000000 00000000 00000C00 00007D79 00004D69 63726F73 6F667420 28522920  |..............}y..Microsoft (R) |
+SYMS-NEXT:         7040: 4C494E4B 00000000 AA003D11 00637764 00643A5C 7372635C 6C6C766D 5C746573  |LINK......=..cwd.d:\src\llvm\tes|
+SYMS-NEXT:         7060: 745C4465 62756749 6E666F5C 5044425C 496E7075 74730065 78650043 3A5C5072  |t\DebugInfo\PDB\Inputs.exe.C:\Pr|
+SYMS-NEXT:         7080: 6F677261 6D204669 6C657320 28783836 295C4D69 63726F73 6F667420 56697375  |ogram Files (x86)\Microsoft Visu|
+SYMS-NEXT:         70A0: 616C2053 74756469 6F203132 2E305C56 435C4249 4E5C6C69 6E6B2E65 78650070  |al Studio 12.0\VC\BIN\link.exe.p|
+SYMS-NEXT:         70C0: 64620064 3A5C7372 635C6C6C 766D5C74 6573745C 44656275 67496E66 6F5C5044  |db.d:\src\llvm\test\DebugInfo\PD|
+SYMS-NEXT:         70E0: 425C496E 70757473 5C656D70 74792E70 64620000 12002C11 00000500 05000000  |B\Inputs\empty.pdb....,.........|
+SYMS-NEXT:         7100: 10000000 01000100 1A003611 01000C00 00100000 1A100000 20000060 2E746578  |..........6............. ..`.tex|
+SYMS-NEXT:         7120: 74000000 1A003711 1A100000 20000060 00000000 01002E74 65787424 6D6E0000  |t.....7..... ..`.......text$mn..|
+SYMS-NEXT:         7140: 1A003611 02000C00 00300000 B2020000 40000040 2E726461 74610000 1A003711  |..6......0......@..@.rdata....7.|
+SYMS-NEXT:         7160: 43010000 40000040 00000000 02002E72 64617461 00000000 1A003711 00000000  |C...@..@.......rdata......7.....|
+SYMS-NEXT:         7180: 40000040 43010000 02002E65 64617461 00000000 1E003711 6E010000 40000040  |@..@C......edata......7.n...@..@|
+SYMS-NEXT:         71A0: 44010000 02002E72 64617461 24646562 75670000 1A003611 03000C00 00400000  |D......rdata$debug....6......@..|
+SYMS-NEXT:         71C0: 04000000 400000C0 2E646174 61000000 16003711 04000000 800000C0 00000000  |....@....data.....7.............|
+SYMS-NEXT:         71E0: 03002E62 73730000 1A003611 04000C00 00500000 08000000 40000042 2E72656C  |...bss....6......P......@..B.rel|
+SYMS-NEXT:         7200: 6F630000                                                                 |oc..|
 SYMS-NEXT:       )
 
 FILTERED-SYMS:                             Module Symbols
 FILTERED-SYMS-NEXT: ============================================================
 FILTERED-SYMS-NEXT:     Mod 0000 | `d:\src\llvm\test\DebugInfo\PDB\Inputs\empty.obj`:
 FILTERED-SYMS-NEXT:       Symbols (
-FILTERED-SYMS-NEXT:         6004: 36000111 00000000 643A5C73 72635C6C 6C766D5C 74657374 5C446562 7567496E  |6.......d:\src\llvm\test\DebugIn|
-FILTERED-SYMS-NEXT:         6024: 666F5C50 44425C49 6E707574 735C656D 7074792E 6F626A00 3A003C11 01200000  |fo\PDB\Inputs\empty.obj.:.<.. ..|
-FILTERED-SYMS-NEXT:         6044: 07001200 00007D79 00001200 00007D79 00004D69 63726F73 6F667420 28522920  |......}y......}y..Microsoft (R) |
-FILTERED-SYMS-NEXT:         6064: 4F707469 6D697A69 6E672043 6F6D7069 6C657200 2A001011 00000000 C4000000  |Optimizing Compiler.*...........|
-FILTERED-SYMS-NEXT:         6084: 00000000 0A000000 03000000 08000000 01100000 10000000 0100016D 61696E00  |...........................main.|
-FILTERED-SYMS-NEXT:         60A4: 1E001210 00000000 00000000 00000000 00000000 00000000 00000082 12000000  |................................|
-FILTERED-SYMS-NEXT:         60C4: 02000600 06004C11 0E100000                                               |......L.....|
+FILTERED-SYMS-NEXT:         6000: 04000000 36000111 00000000 643A5C73 72635C6C 6C766D5C 74657374 5C446562  |....6.......d:\src\llvm\test\Deb|
+FILTERED-SYMS-NEXT:         6020: 7567496E 666F5C50 44425C49 6E707574 735C656D 7074792E 6F626A00 3A003C11  |ugInfo\PDB\Inputs\empty.obj.:.<.|
+FILTERED-SYMS-NEXT:         6040: 01200000 07001200 00007D79 00001200 00007D79 00004D69 63726F73 6F667420  |. ........}y......}y..Microsoft |
+FILTERED-SYMS-NEXT:         6060: 28522920 4F707469 6D697A69 6E672043 6F6D7069 6C657200 2A001011 00000000  |(R) Optimizing Compiler.*.......|
+FILTERED-SYMS-NEXT:         6080: C4000000 00000000 0A000000 03000000 08000000 01100000 10000000 0100016D  |...............................m|
+FILTERED-SYMS-NEXT:         60A0: 61696E00 1E001210 00000000 00000000 00000000 00000000 00000000 00000082  |ain.............................|
+FILTERED-SYMS-NEXT:         60C0: 12000000 02000600 06004C11 0E100000                                      |..........L.....|
 FILTERED-SYMS-NEXT:       )
 FILTERED-SYMS-NOT:      Mod 0001