LCOV - code coverage report
Current view: top level - lib/DebugInfo/CodeView - TypeStreamMerger.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 93 100 93.0 %
Date: 2017-09-14 15:23:50 Functions: 13 13 100.0 %
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/TypeDeserializer.h"
      14             : #include "llvm/DebugInfo/CodeView/TypeIndex.h"
      15             : #include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
      16             : #include "llvm/DebugInfo/CodeView/TypeRecord.h"
      17             : #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
      18             : #include "llvm/Support/Error.h"
      19             : #include "llvm/Support/ScopedPrinter.h"
      20             : 
      21             : using namespace llvm;
      22             : using namespace llvm::codeview;
      23             : 
      24             : namespace {
      25             : 
      26             : /// Implementation of CodeView type stream merging.
      27             : ///
      28             : /// A CodeView type stream is a series of records that reference each other
      29             : /// through type indices. A type index is either "simple", meaning it is less
      30             : /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
      31             : /// refers to a prior type record in the current stream. The type index of a
      32             : /// record is equal to the number of records before it in the stream plus
      33             : /// 0x1000.
      34             : ///
      35             : /// Type records are only allowed to use type indices smaller than their own, so
      36             : /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
      37             : /// the type graph of the source program are resolved with forward declarations
      38             : /// of composite types. This class implements the following type stream merging
      39             : /// algorithm, which relies on this DAG structure:
      40             : ///
      41             : /// - Begin with a new empty stream, and a new empty hash table that maps from
      42             : ///   type record contents to new type index.
      43             : /// - For each new type stream, maintain a map from source type index to
      44             : ///   destination type index.
      45             : /// - For each record, copy it and rewrite its type indices to be valid in the
      46             : ///   destination type stream.
      47             : /// - If the new type record is not already present in the destination stream
      48             : ///   hash table, append it to the destination type stream, assign it the next
      49             : ///   type index, and update the two hash tables.
      50             : /// - If the type record already exists in the destination stream, discard it
      51             : ///   and update the type index map to forward the source type index to the
      52             : ///   existing destination type index.
      53             : ///
      54             : /// As an additional complication, type stream merging actually produces two
      55             : /// streams: an item (or IPI) stream and a type stream, as this is what is
      56             : /// actually stored in the final PDB. We choose which records go where by
      57             : /// looking at the record kind.
      58          90 : class TypeStreamMerger {
      59             : public:
      60             :   explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest)
      61         135 :       : IndexMap(SourceToDest) {
      62          45 :     SourceToDest.clear();
      63             :   }
      64             : 
      65             :   static const TypeIndex Untranslated;
      66             : 
      67             :   Error mergeTypesAndIds(TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
      68             :                          const CVTypeArray &IdsAndTypes);
      69             :   Error mergeIdRecords(TypeTableBuilder &Dest,
      70             :                        ArrayRef<TypeIndex> TypeSourceToDest,
      71             :                        const CVTypeArray &Ids);
      72             :   Error mergeTypeRecords(TypeTableBuilder &Dest, const CVTypeArray &Types);
      73             : 
      74             : private:
      75             :   Error doit(const CVTypeArray &Types);
      76             : 
      77             :   Error remapAllTypes(const CVTypeArray &Types);
      78             : 
      79             :   Error remapType(const CVType &Type);
      80             : 
      81             :   void addMapping(TypeIndex Idx);
      82             : 
      83             :   bool remapTypeIndex(TypeIndex &Idx);
      84             :   bool remapItemIndex(TypeIndex &Idx);
      85             : 
      86             :   bool remapIndices(RemappedType &Record, ArrayRef<TiReference> Refs);
      87             : 
      88             :   bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
      89             : 
      90             :   size_t slotForIndex(TypeIndex Idx) const {
      91             :     assert(!Idx.isSimple() && "simple type indices have no slots");
      92        1266 :     return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
      93             :   }
      94             : 
      95             :   Error errorCorruptRecord() const {
      96           0 :     return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
      97             :   }
      98             : 
      99        1017 :   Error writeRecord(TypeTableBuilder &Dest, const RemappedType &Record,
     100             :                     bool RemapSuccess) {
     101        1017 :     TypeIndex DestIdx = Untranslated;
     102        1017 :     if (RemapSuccess)
     103        1002 :       DestIdx = Dest.writeSerializedRecord(Record);
     104        1017 :     addMapping(DestIdx);
     105        3051 :     return Error::success();
     106             :   }
     107             : 
     108             :   Optional<Error> LastError;
     109             : 
     110             :   bool IsSecondPass = false;
     111             : 
     112             :   unsigned NumBadIndices = 0;
     113             : 
     114             :   TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
     115             : 
     116             :   TypeTableBuilder *DestIdStream = nullptr;
     117             :   TypeTableBuilder *DestTypeStream = nullptr;
     118             : 
     119             :   // If we're only mapping id records, this array contains the mapping for
     120             :   // type records.
     121             :   ArrayRef<TypeIndex> TypeLookup;
     122             : 
     123             :   /// Map from source type index to destination type index. Indexed by source
     124             :   /// type index minus 0x1000.
     125             :   SmallVectorImpl<TypeIndex> &IndexMap;
     126             : };
     127             : 
     128             : } // end anonymous namespace
     129             : 
     130             : const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
     131             : 
     132             : static bool isIdRecord(TypeLeafKind K) {
     133        1017 :   switch (K) {
     134             :   case TypeLeafKind::LF_FUNC_ID:
     135             :   case TypeLeafKind::LF_MFUNC_ID:
     136             :   case TypeLeafKind::LF_STRING_ID:
     137             :   case TypeLeafKind::LF_SUBSTR_LIST:
     138             :   case TypeLeafKind::LF_BUILDINFO:
     139             :   case TypeLeafKind::LF_UDT_SRC_LINE:
     140             :   case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
     141             :     return true;
     142             :   default:
     143             :     return false;
     144             :   }
     145             : }
     146             : 
     147        1017 : void TypeStreamMerger::addMapping(TypeIndex Idx) {
     148        1017 :   if (!IsSecondPass) {
     149             :     assert(IndexMap.size() == slotForIndex(CurIndex) &&
     150             :            "visitKnownRecord should add one index map entry");
     151        1000 :     IndexMap.push_back(Idx);
     152             :   } else {
     153             :     assert(slotForIndex(CurIndex) < IndexMap.size());
     154          51 :     IndexMap[slotForIndex(CurIndex)] = Idx;
     155             :   }
     156        1017 : }
     157             : 
     158        2012 : bool TypeStreamMerger::remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
     159             :   // Simple types are unchanged.
     160        2012 :   if (Idx.isSimple())
     161             :     return true;
     162             : 
     163             :   // Check if this type index refers to a record we've already translated
     164             :   // successfully. If it refers to a type later in the stream or a record we
     165             :   // had to defer, defer it until later pass.
     166        2498 :   unsigned MapPos = slotForIndex(Idx);
     167        3737 :   if (MapPos < Map.size() && Map[MapPos] != Untranslated) {
     168        1234 :     Idx = Map[MapPos];
     169        1234 :     return true;
     170             :   }
     171             : 
     172             :   // If this is the second pass and this index isn't in the map, then it points
     173             :   // outside the current type stream, and this is a corrupt record.
     174          15 :   if (IsSecondPass && MapPos >= Map.size()) {
     175             :     // FIXME: Print a more useful error. We can give the current record and the
     176             :     // index that we think its pointing to.
     177           0 :     LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
     178             :   }
     179             : 
     180          15 :   ++NumBadIndices;
     181             : 
     182             :   // This type index is invalid. Remap this to "not translated by cvpack",
     183             :   // and return failure.
     184          15 :   Idx = Untranslated;
     185          15 :   return false;
     186             : }
     187             : 
     188        1482 : bool TypeStreamMerger::remapTypeIndex(TypeIndex &Idx) {
     189             :   // If we're mapping a pure index stream, then IndexMap only contains mappings
     190             :   // from OldIdStream -> NewIdStream, in which case we will need to use the
     191             :   // special mapping from OldTypeStream -> NewTypeStream which was computed
     192             :   // externally.  Regardless, we use this special map if and only if we are
     193             :   // doing an id-only mapping.
     194        1482 :   if (DestTypeStream == nullptr)
     195          14 :     return remapIndex(Idx, TypeLookup);
     196             : 
     197             :   assert(TypeLookup.empty());
     198        2936 :   return remapIndex(Idx, IndexMap);
     199             : }
     200             : 
     201         530 : bool TypeStreamMerger::remapItemIndex(TypeIndex &Idx) {
     202             :   assert(DestIdStream);
     203        1060 :   return remapIndex(Idx, IndexMap);
     204             : }
     205             : 
     206             : Error TypeStreamMerger::mergeTypeRecords(TypeTableBuilder &Dest,
     207             :                                          const CVTypeArray &Types) {
     208           7 :   DestTypeStream = &Dest;
     209             : 
     210           7 :   return doit(Types);
     211             : }
     212             : 
     213             : Error TypeStreamMerger::mergeIdRecords(TypeTableBuilder &Dest,
     214             :                                        ArrayRef<TypeIndex> TypeSourceToDest,
     215             :                                        const CVTypeArray &Ids) {
     216           5 :   DestIdStream = &Dest;
     217           5 :   TypeLookup = TypeSourceToDest;
     218             : 
     219           5 :   return doit(Ids);
     220             : }
     221             : 
     222             : Error TypeStreamMerger::mergeTypesAndIds(TypeTableBuilder &DestIds,
     223             :                                          TypeTableBuilder &DestTypes,
     224             :                                          const CVTypeArray &IdsAndTypes) {
     225          33 :   DestIdStream = &DestIds;
     226          33 :   DestTypeStream = &DestTypes;
     227          33 :   return doit(IdsAndTypes);
     228             : }
     229             : 
     230          45 : Error TypeStreamMerger::doit(const CVTypeArray &Types) {
     231         135 :   if (auto EC = remapAllTypes(Types))
     232           0 :     return EC;
     233             : 
     234             :   // If we found bad indices but no other errors, try doing another pass and see
     235             :   // if we can resolve the indices that weren't in the map on the first pass.
     236             :   // This may require multiple passes, but we should always make progress. MASM
     237             :   // is the only known CodeView producer that makes type streams that aren't
     238             :   // topologically sorted. The standard library contains MASM-produced objects,
     239             :   // so this is important to handle correctly, but we don't have to be too
     240             :   // efficient. MASM type streams are usually very small.
     241          47 :   while (!LastError && NumBadIndices > 0) {
     242           3 :     unsigned BadIndicesRemaining = NumBadIndices;
     243           3 :     IsSecondPass = true;
     244           3 :     NumBadIndices = 0;
     245           3 :     CurIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex);
     246             : 
     247           9 :     if (auto EC = remapAllTypes(Types))
     248           0 :       return EC;
     249             : 
     250             :     assert(NumBadIndices <= BadIndicesRemaining &&
     251             :            "second pass found more bad indices");
     252           3 :     if (!LastError && NumBadIndices == BadIndicesRemaining) {
     253             :       return llvm::make_error<CodeViewError>(
     254           2 :           cv_error_code::corrupt_record, "input type graph contains cycles");
     255             :     }
     256             :   }
     257             : 
     258          44 :   if (LastError)
     259           0 :     return std::move(*LastError);
     260         132 :   return Error::success();
     261             : }
     262             : 
     263          48 : Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
     264        1257 :   for (const CVType &Type : Types)
     265        3051 :     if (auto EC = remapType(Type))
     266           0 :       return EC;
     267         144 :   return Error::success();
     268             : }
     269             : 
     270        1017 : Error TypeStreamMerger::remapType(const CVType &Type) {
     271        2034 :   RemappedType R(Type);
     272        2034 :   SmallVector<TiReference, 32> Refs;
     273        1017 :   discoverTypeIndices(Type.RecordData, Refs);
     274        1017 :   bool MappedAllIndices = remapIndices(R, Refs);
     275             :   TypeTableBuilder &Dest =
     276        1432 :       isIdRecord(Type.kind()) ? *DestIdStream : *DestTypeStream;
     277        3051 :   if (auto EC = writeRecord(Dest, R, MappedAllIndices))
     278           0 :     return EC;
     279             : 
     280        2034 :   ++CurIndex;
     281             :   assert((IsSecondPass || IndexMap.size() == slotForIndex(CurIndex)) &&
     282             :          "visitKnownRecord should add one index map entry");
     283        3051 :   return Error::success();
     284             : }
     285             : 
     286        1017 : bool TypeStreamMerger::remapIndices(RemappedType &Record,
     287             :                                     ArrayRef<TiReference> Refs) {
     288        2034 :   ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.content();
     289        1017 :   bool Success = true;
     290        3454 :   for (auto &Ref : Refs) {
     291        1420 :     uint32_t Offset = Ref.Offset;
     292        2840 :     ArrayRef<uint8_t> Bytes = OriginalData.slice(Ref.Offset, sizeof(TypeIndex));
     293        1420 :     ArrayRef<TypeIndex> TIs(reinterpret_cast<const TypeIndex *>(Bytes.data()),
     294        2840 :                             Ref.Count);
     295        4852 :     for (auto TI : TIs) {
     296        2012 :       TypeIndex NewTI = TI;
     297        2012 :       bool ThisSuccess = (Ref.Kind == TiRefKind::IndexRef)
     298        2012 :                              ? remapItemIndex(NewTI)
     299        2012 :                              : remapTypeIndex(NewTI);
     300        4009 :       if (ThisSuccess && NewTI != TI)
     301        1012 :         Record.Mappings.emplace_back(Offset, NewTI);
     302        2012 :       Offset += sizeof(TypeIndex);
     303        2012 :       Success &= ThisSuccess;
     304             :     }
     305             :   }
     306        1017 :   return Success;
     307             : }
     308             : 
     309           7 : Error llvm::codeview::mergeTypeRecords(TypeTableBuilder &Dest,
     310             :                                        SmallVectorImpl<TypeIndex> &SourceToDest,
     311             :                                        const CVTypeArray &Types) {
     312          14 :   TypeStreamMerger M(SourceToDest);
     313          14 :   return M.mergeTypeRecords(Dest, Types);
     314             : }
     315             : 
     316           5 : Error llvm::codeview::mergeIdRecords(TypeTableBuilder &Dest,
     317             :                                      ArrayRef<TypeIndex> TypeSourceToDest,
     318             :                                      SmallVectorImpl<TypeIndex> &SourceToDest,
     319             :                                      const CVTypeArray &Ids) {
     320          10 :   TypeStreamMerger M(SourceToDest);
     321          10 :   return M.mergeIdRecords(Dest, TypeSourceToDest, Ids);
     322             : }
     323             : 
     324          33 : Error llvm::codeview::mergeTypeAndIdRecords(
     325             :     TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
     326             :     SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes) {
     327          66 :   TypeStreamMerger M(SourceToDest);
     328          66 :   return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes);
     329      144612 : }

Generated by: LCOV version 1.13