LCOV - code coverage report
Current view: top level - lib/DebugInfo/CodeView - TypeStreamMerger.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 98 115 85.2 %
Date: 2018-07-13 00:08:38 Functions: 15 17 88.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- TypeStreamMerger.cpp ------------------------------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
      11             : #include "llvm/ADT/SmallString.h"
      12             : #include "llvm/ADT/StringExtras.h"
      13             : #include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
      14             : #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
      15             : #include "llvm/DebugInfo/CodeView/TypeIndex.h"
      16             : #include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
      17             : #include "llvm/DebugInfo/CodeView/TypeRecord.h"
      18             : #include "llvm/Support/Error.h"
      19             : 
      20             : using namespace llvm;
      21             : using namespace llvm::codeview;
      22             : 
      23             : static inline size_t slotForIndex(TypeIndex Idx) {
      24             :   assert(!Idx.isSimple() && "simple type indices have no slots");
      25        2036 :   return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
      26             : }
      27             : 
      28             : namespace {
      29             : 
      30             : /// Implementation of CodeView type stream merging.
      31             : ///
      32             : /// A CodeView type stream is a series of records that reference each other
      33             : /// through type indices. A type index is either "simple", meaning it is less
      34             : /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
      35             : /// refers to a prior type record in the current stream. The type index of a
      36             : /// record is equal to the number of records before it in the stream plus
      37             : /// 0x1000.
      38             : ///
      39             : /// Type records are only allowed to use type indices smaller than their own, so
      40             : /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
      41             : /// the type graph of the source program are resolved with forward declarations
      42             : /// of composite types. This class implements the following type stream merging
      43             : /// algorithm, which relies on this DAG structure:
      44             : ///
      45             : /// - Begin with a new empty stream, and a new empty hash table that maps from
      46             : ///   type record contents to new type index.
      47             : /// - For each new type stream, maintain a map from source type index to
      48             : ///   destination type index.
      49             : /// - For each record, copy it and rewrite its type indices to be valid in the
      50             : ///   destination type stream.
      51             : /// - If the new type record is not already present in the destination stream
      52             : ///   hash table, append it to the destination type stream, assign it the next
      53             : ///   type index, and update the two hash tables.
      54             : /// - If the type record already exists in the destination stream, discard it
      55             : ///   and update the type index map to forward the source type index to the
      56             : ///   existing destination type index.
      57             : ///
      58             : /// As an additional complication, type stream merging actually produces two
      59             : /// streams: an item (or IPI) stream and a type stream, as this is what is
      60             : /// actually stored in the final PDB. We choose which records go where by
      61             : /// looking at the record kind.
      62         118 : class TypeStreamMerger {
      63             : public:
      64             :   explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest)
      65         236 :       : IndexMap(SourceToDest) {
      66             :     SourceToDest.clear();
      67             :   }
      68             : 
      69             :   static const TypeIndex Untranslated;
      70             : 
      71             :   // Local hashing entry points
      72             :   Error mergeTypesAndIds(MergingTypeTableBuilder &DestIds,
      73             :                          MergingTypeTableBuilder &DestTypes,
      74             :                          const CVTypeArray &IdsAndTypes);
      75             :   Error mergeIdRecords(MergingTypeTableBuilder &Dest,
      76             :                        ArrayRef<TypeIndex> TypeSourceToDest,
      77             :                        const CVTypeArray &Ids);
      78             :   Error mergeTypeRecords(MergingTypeTableBuilder &Dest,
      79             :                          const CVTypeArray &Types);
      80             : 
      81             :   // Global hashing entry points
      82             :   Error mergeTypesAndIds(GlobalTypeTableBuilder &DestIds,
      83             :                          GlobalTypeTableBuilder &DestTypes,
      84             :                          const CVTypeArray &IdsAndTypes,
      85             :                          ArrayRef<GloballyHashedType> Hashes);
      86             :   Error mergeIdRecords(GlobalTypeTableBuilder &Dest,
      87             :                        ArrayRef<TypeIndex> TypeSourceToDest,
      88             :                        const CVTypeArray &Ids,
      89             :                        ArrayRef<GloballyHashedType> Hashes);
      90             :   Error mergeTypeRecords(GlobalTypeTableBuilder &Dest, const CVTypeArray &Types,
      91             :                          ArrayRef<GloballyHashedType> Hashes);
      92             : 
      93             : private:
      94             :   Error doit(const CVTypeArray &Types);
      95             : 
      96             :   Error remapAllTypes(const CVTypeArray &Types);
      97             : 
      98             :   Error remapType(const CVType &Type);
      99             : 
     100             :   void addMapping(TypeIndex Idx);
     101             : 
     102        2470 :   inline bool remapTypeIndex(TypeIndex &Idx) {
     103             :     // If we're mapping a pure index stream, then IndexMap only contains
     104             :     // mappings from OldIdStream -> NewIdStream, in which case we will need to
     105             :     // use the special mapping from OldTypeStream -> NewTypeStream which was
     106             :     // computed externally.  Regardless, we use this special map if and only if
     107             :     // we are doing an id-only mapping.
     108        2470 :     if (!hasTypeStream())
     109          18 :       return remapIndex(Idx, TypeLookup);
     110             : 
     111             :     assert(TypeLookup.empty());
     112        4904 :     return remapIndex(Idx, IndexMap);
     113             :   }
     114         672 :   inline bool remapItemIndex(TypeIndex &Idx) {
     115             :     assert(hasIdStream());
     116        1344 :     return remapIndex(Idx, IndexMap);
     117             :   }
     118             : 
     119             :   bool hasTypeStream() const {
     120        2470 :     return (UseGlobalHashes) ? (!!DestGlobalTypeStream) : (!!DestTypeStream);
     121             :   }
     122             : 
     123             :   bool hasIdStream() const {
     124             :     return (UseGlobalHashes) ? (!!DestGlobalIdStream) : (!!DestIdStream);
     125             :   }
     126             : 
     127             :   ArrayRef<uint8_t> remapIndices(const CVType &OriginalType,
     128             :                                  MutableArrayRef<uint8_t> Storage);
     129             : 
     130        3142 :   inline bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
     131        3142 :     if (LLVM_LIKELY(remapIndexSimple(Idx, Map)))
     132             :       return true;
     133             : 
     134          15 :     return remapIndexFallback(Idx, Map);
     135             :   }
     136             : 
     137             :   inline bool remapIndexSimple(TypeIndex &Idx, ArrayRef<TypeIndex> Map) const {
     138             :     // Simple types are unchanged.
     139        3142 :     if (Idx.isSimple())
     140             :       return true;
     141             : 
     142             :     // Check if this type index refers to a record we've already translated
     143             :     // successfully. If it refers to a type later in the stream or a record we
     144             :     // had to defer, defer it until later pass.
     145             :     unsigned MapPos = slotForIndex(Idx);
     146        4003 :     if (LLVM_UNLIKELY(MapPos >= Map.size() || Map[MapPos] == Untranslated))
     147             :       return false;
     148             : 
     149        1989 :     Idx = Map[MapPos];
     150             :     return true;
     151             :   }
     152             : 
     153             :   bool remapIndexFallback(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
     154             : 
     155             :   Error errorCorruptRecord() const {
     156           0 :     return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
     157             :   }
     158             : 
     159             :   Optional<Error> LastError;
     160             : 
     161             :   bool UseGlobalHashes = false;
     162             : 
     163             :   bool IsSecondPass = false;
     164             : 
     165             :   unsigned NumBadIndices = 0;
     166             : 
     167             :   TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
     168             : 
     169             :   MergingTypeTableBuilder *DestIdStream = nullptr;
     170             :   MergingTypeTableBuilder *DestTypeStream = nullptr;
     171             : 
     172             :   GlobalTypeTableBuilder *DestGlobalIdStream = nullptr;
     173             :   GlobalTypeTableBuilder *DestGlobalTypeStream = nullptr;
     174             : 
     175             :   ArrayRef<GloballyHashedType> GlobalHashes;
     176             : 
     177             :   // If we're only mapping id records, this array contains the mapping for
     178             :   // type records.
     179             :   ArrayRef<TypeIndex> TypeLookup;
     180             : 
     181             :   /// Map from source type index to destination type index. Indexed by source
     182             :   /// type index minus 0x1000.
     183             :   SmallVectorImpl<TypeIndex> &IndexMap;
     184             : 
     185             :   /// Temporary storage that we use to copy a record's data while re-writing
     186             :   /// its type indices.
     187             :   SmallVector<uint8_t, 256> RemapStorage;
     188             : };
     189             : 
     190             : } // end anonymous namespace
     191             : 
     192             : const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
     193             : 
     194             : static bool isIdRecord(TypeLeafKind K) {
     195        1541 :   switch (K) {
     196             :   case TypeLeafKind::LF_FUNC_ID:
     197             :   case TypeLeafKind::LF_MFUNC_ID:
     198             :   case TypeLeafKind::LF_STRING_ID:
     199             :   case TypeLeafKind::LF_SUBSTR_LIST:
     200             :   case TypeLeafKind::LF_BUILDINFO:
     201             :   case TypeLeafKind::LF_UDT_SRC_LINE:
     202             :   case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
     203             :     return true;
     204             :   default:
     205             :     return false;
     206             :   }
     207             : }
     208             : 
     209        1541 : void TypeStreamMerger::addMapping(TypeIndex Idx) {
     210        1541 :   if (!IsSecondPass) {
     211             :     assert(IndexMap.size() == slotForIndex(CurIndex) &&
     212             :            "visitKnownRecord should add one index map entry");
     213        1524 :     IndexMap.push_back(Idx);
     214             :   } else {
     215             :     assert(slotForIndex(CurIndex) < IndexMap.size());
     216          34 :     IndexMap[slotForIndex(CurIndex)] = Idx;
     217             :   }
     218        1541 : }
     219             : 
     220          15 : bool TypeStreamMerger::remapIndexFallback(TypeIndex &Idx,
     221             :                                           ArrayRef<TypeIndex> Map) {
     222             :   size_t MapPos = slotForIndex(Idx);
     223             : 
     224             :   // If this is the second pass and this index isn't in the map, then it points
     225             :   // outside the current type stream, and this is a corrupt record.
     226          15 :   if (IsSecondPass && MapPos >= Map.size()) {
     227             :     // FIXME: Print a more useful error. We can give the current record and the
     228             :     // index that we think its pointing to.
     229           0 :     LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
     230             :   }
     231             : 
     232          15 :   ++NumBadIndices;
     233             : 
     234             :   // This type index is invalid. Remap this to "not translated by cvpack",
     235             :   // and return failure.
     236          15 :   Idx = Untranslated;
     237          15 :   return false;
     238             : }
     239             : 
     240             : // Local hashing entry points
     241             : Error TypeStreamMerger::mergeTypeRecords(MergingTypeTableBuilder &Dest,
     242             :                                          const CVTypeArray &Types) {
     243           8 :   DestTypeStream = &Dest;
     244           8 :   UseGlobalHashes = false;
     245             : 
     246           8 :   return doit(Types);
     247             : }
     248             : 
     249             : Error TypeStreamMerger::mergeIdRecords(MergingTypeTableBuilder &Dest,
     250             :                                        ArrayRef<TypeIndex> TypeSourceToDest,
     251             :                                        const CVTypeArray &Ids) {
     252           6 :   DestIdStream = &Dest;
     253           6 :   TypeLookup = TypeSourceToDest;
     254           6 :   UseGlobalHashes = false;
     255             : 
     256           6 :   return doit(Ids);
     257             : }
     258             : 
     259             : Error TypeStreamMerger::mergeTypesAndIds(MergingTypeTableBuilder &DestIds,
     260             :                                          MergingTypeTableBuilder &DestTypes,
     261             :                                          const CVTypeArray &IdsAndTypes) {
     262          41 :   DestIdStream = &DestIds;
     263          41 :   DestTypeStream = &DestTypes;
     264          41 :   UseGlobalHashes = false;
     265          41 :   return doit(IdsAndTypes);
     266             : }
     267             : 
     268             : // Global hashing entry points
     269             : Error TypeStreamMerger::mergeTypeRecords(GlobalTypeTableBuilder &Dest,
     270             :                                          const CVTypeArray &Types,
     271             :                                          ArrayRef<GloballyHashedType> Hashes) {
     272           0 :   DestGlobalTypeStream = &Dest;
     273           0 :   UseGlobalHashes = true;
     274           0 :   GlobalHashes = Hashes;
     275             : 
     276           0 :   return doit(Types);
     277             : }
     278             : 
     279             : Error TypeStreamMerger::mergeIdRecords(GlobalTypeTableBuilder &Dest,
     280             :                                        ArrayRef<TypeIndex> TypeSourceToDest,
     281             :                                        const CVTypeArray &Ids,
     282             :                                        ArrayRef<GloballyHashedType> Hashes) {
     283           0 :   DestGlobalIdStream = &Dest;
     284           0 :   TypeLookup = TypeSourceToDest;
     285           0 :   UseGlobalHashes = true;
     286           0 :   GlobalHashes = Hashes;
     287             : 
     288           0 :   return doit(Ids);
     289             : }
     290             : 
     291             : Error TypeStreamMerger::mergeTypesAndIds(GlobalTypeTableBuilder &DestIds,
     292             :                                          GlobalTypeTableBuilder &DestTypes,
     293             :                                          const CVTypeArray &IdsAndTypes,
     294             :                                          ArrayRef<GloballyHashedType> Hashes) {
     295           4 :   DestGlobalIdStream = &DestIds;
     296           4 :   DestGlobalTypeStream = &DestTypes;
     297           4 :   UseGlobalHashes = true;
     298           4 :   GlobalHashes = Hashes;
     299           4 :   return doit(IdsAndTypes);
     300             : }
     301             : 
     302          59 : Error TypeStreamMerger::doit(const CVTypeArray &Types) {
     303         118 :   if (auto EC = remapAllTypes(Types))
     304             :     return EC;
     305             : 
     306             :   // If we found bad indices but no other errors, try doing another pass and see
     307             :   // if we can resolve the indices that weren't in the map on the first pass.
     308             :   // This may require multiple passes, but we should always make progress. MASM
     309             :   // is the only known CodeView producer that makes type streams that aren't
     310             :   // topologically sorted. The standard library contains MASM-produced objects,
     311             :   // so this is important to handle correctly, but we don't have to be too
     312             :   // efficient. MASM type streams are usually very small.
     313          61 :   while (!LastError && NumBadIndices > 0) {
     314             :     unsigned BadIndicesRemaining = NumBadIndices;
     315           3 :     IsSecondPass = true;
     316           3 :     NumBadIndices = 0;
     317           3 :     CurIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex);
     318             : 
     319           6 :     if (auto EC = remapAllTypes(Types))
     320             :       return EC;
     321             : 
     322             :     assert(NumBadIndices <= BadIndicesRemaining &&
     323             :            "second pass found more bad indices");
     324           3 :     if (!LastError && NumBadIndices == BadIndicesRemaining) {
     325             :       return llvm::make_error<CodeViewError>(
     326             :           cv_error_code::corrupt_record, "input type graph contains cycles");
     327             :     }
     328             :   }
     329             : 
     330          58 :   if (LastError)
     331             :     return std::move(*LastError);
     332             :   return Error::success();
     333             : }
     334             : 
     335          62 : Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
     336             :   BinaryStreamRef Stream = Types.getUnderlyingStream();
     337          62 :   ArrayRef<uint8_t> Buffer;
     338         124 :   cantFail(Stream.readBytes(0, Stream.getLength(), Buffer));
     339             : 
     340             :   return forEachCodeViewRecord<CVType>(
     341        1665 :       Buffer, [this](const CVType &T) { return remapType(T); });
     342             : }
     343             : 
     344        1541 : Error TypeStreamMerger::remapType(const CVType &Type) {
     345             :   auto DoSerialize =
     346        1579 :       [this, Type](MutableArrayRef<uint8_t> Storage) -> ArrayRef<uint8_t> {
     347        1525 :     return remapIndices(Type, Storage);
     348        1541 :   };
     349             : 
     350        1541 :   TypeIndex DestIdx = Untranslated;
     351        1541 :   if (LLVM_LIKELY(UseGlobalHashes)) {
     352             :     GlobalTypeTableBuilder &Dest =
     353          16 :         isIdRecord(Type.kind()) ? *DestGlobalIdStream : *DestGlobalTypeStream;
     354         108 :     GloballyHashedType H = GlobalHashes[CurIndex.toArrayIndex()];
     355          54 :     DestIdx = Dest.insertRecordAs(H, Type.RecordData.size(), DoSerialize);
     356             :   } else {
     357             :     MergingTypeTableBuilder &Dest =
     358         953 :         isIdRecord(Type.kind()) ? *DestIdStream : *DestTypeStream;
     359             : 
     360        1487 :     RemapStorage.resize(Type.RecordData.size());
     361        1487 :     ArrayRef<uint8_t> Result = DoSerialize(RemapStorage);
     362        1487 :     if (!Result.empty())
     363        1472 :       DestIdx = Dest.insertRecordBytes(Result);
     364             :   }
     365        1541 :   addMapping(DestIdx);
     366             : 
     367             :   ++CurIndex;
     368             :   assert((IsSecondPass || IndexMap.size() == slotForIndex(CurIndex)) &&
     369             :          "visitKnownRecord should add one index map entry");
     370        1541 :   return Error::success();
     371             : }
     372             : 
     373             : ArrayRef<uint8_t>
     374        1525 : TypeStreamMerger::remapIndices(const CVType &OriginalType,
     375             :                                MutableArrayRef<uint8_t> Storage) {
     376             :   SmallVector<TiReference, 4> Refs;
     377        1525 :   discoverTypeIndices(OriginalType.RecordData, Refs);
     378        1525 :   if (Refs.empty())
     379          95 :     return OriginalType.RecordData;
     380             : 
     381        1430 :   ::memcpy(Storage.data(), OriginalType.RecordData.data(),
     382             :            OriginalType.RecordData.size());
     383             : 
     384             :   uint8_t *DestContent = Storage.data() + sizeof(RecordPrefix);
     385             : 
     386        5780 :   for (auto &Ref : Refs) {
     387             :     TypeIndex *DestTIs =
     388        2190 :         reinterpret_cast<TypeIndex *>(DestContent + Ref.Offset);
     389             : 
     390        8444 :     for (size_t I = 0; I < Ref.Count; ++I) {
     391        3142 :       TypeIndex &TI = DestTIs[I];
     392        3142 :       bool Success = (Ref.Kind == TiRefKind::IndexRef) ? remapItemIndex(TI)
     393             :                                                        : remapTypeIndex(TI);
     394        3142 :       if (LLVM_UNLIKELY(!Success))
     395          15 :         return {};
     396             :     }
     397             :   }
     398        1415 :   return Storage;
     399             : }
     400             : 
     401           8 : Error llvm::codeview::mergeTypeRecords(MergingTypeTableBuilder &Dest,
     402             :                                        SmallVectorImpl<TypeIndex> &SourceToDest,
     403             :                                        const CVTypeArray &Types) {
     404           8 :   TypeStreamMerger M(SourceToDest);
     405           8 :   return M.mergeTypeRecords(Dest, Types);
     406             : }
     407             : 
     408           6 : Error llvm::codeview::mergeIdRecords(MergingTypeTableBuilder &Dest,
     409             :                                      ArrayRef<TypeIndex> TypeSourceToDest,
     410             :                                      SmallVectorImpl<TypeIndex> &SourceToDest,
     411             :                                      const CVTypeArray &Ids) {
     412           6 :   TypeStreamMerger M(SourceToDest);
     413           6 :   return M.mergeIdRecords(Dest, TypeSourceToDest, Ids);
     414             : }
     415             : 
     416          41 : Error llvm::codeview::mergeTypeAndIdRecords(
     417             :     MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes,
     418             :     SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes) {
     419          41 :   TypeStreamMerger M(SourceToDest);
     420          41 :   return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes);
     421             : }
     422             : 
     423           4 : Error llvm::codeview::mergeTypeAndIdRecords(
     424             :     GlobalTypeTableBuilder &DestIds, GlobalTypeTableBuilder &DestTypes,
     425             :     SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes,
     426             :     ArrayRef<GloballyHashedType> Hashes) {
     427           4 :   TypeStreamMerger M(SourceToDest);
     428           4 :   return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes, Hashes);
     429             : }
     430             : 
     431           0 : Error llvm::codeview::mergeTypeRecords(GlobalTypeTableBuilder &Dest,
     432             :                                        SmallVectorImpl<TypeIndex> &SourceToDest,
     433             :                                        const CVTypeArray &Types,
     434             :                                        ArrayRef<GloballyHashedType> Hashes) {
     435           0 :   TypeStreamMerger M(SourceToDest);
     436           0 :   return M.mergeTypeRecords(Dest, Types, Hashes);
     437             : }
     438             : 
     439           0 : Error llvm::codeview::mergeIdRecords(GlobalTypeTableBuilder &Dest,
     440             :                                      ArrayRef<TypeIndex> Types,
     441             :                                      SmallVectorImpl<TypeIndex> &SourceToDest,
     442             :                                      const CVTypeArray &Ids,
     443             :                                      ArrayRef<GloballyHashedType> Hashes) {
     444           0 :   TypeStreamMerger M(SourceToDest);
     445           0 :   return M.mergeIdRecords(Dest, Types, Ids, Hashes);
     446      199486 : }

Generated by: LCOV version 1.13