contrib/llvm/lib/DebugInfo/CodeView/TypeSerializer.cpp

   1 //===- TypeSerialzier.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/TypeSerializer.h"
  11
  12 #include "llvm/ADT/DenseSet.h"
  13 #include "llvm/Support/BinaryStreamWriter.h"
  14
  15 #include <string.h>
  16
  17 using namespace llvm;
  18 using namespace llvm::codeview;
  19
  20 namespace {
  21 struct HashedType {
  22   uint64_t Hash;
  23   const uint8_t *Data;
  24   unsigned Size; // FIXME: Go to uint16_t?
  25   TypeIndex Index;
  26 };
  27
  28 /// Wrapper around a poitner to a HashedType. Hash and equality operations are
  29 /// based on data in the pointee.
  30 struct HashedTypePtr {
  31   HashedTypePtr() = default;
  32   HashedTypePtr(HashedType *Ptr) : Ptr(Ptr) {}
  33   HashedType *Ptr = nullptr;
  34 };
  35 } // namespace
  36
  37 namespace llvm {
  38 template <> struct DenseMapInfo<HashedTypePtr> {
  39   static inline HashedTypePtr getEmptyKey() { return HashedTypePtr(nullptr); }
  40   static inline HashedTypePtr getTombstoneKey() {
  41     return HashedTypePtr(reinterpret_cast<HashedType *>(1));
  42   }
  43   static unsigned getHashValue(HashedTypePtr Val) {
  44     assert(Val.Ptr != getEmptyKey().Ptr && Val.Ptr != getTombstoneKey().Ptr);
  45     return Val.Ptr->Hash;
  46   }
  47   static bool isEqual(HashedTypePtr LHSP, HashedTypePtr RHSP) {
  48     HashedType *LHS = LHSP.Ptr;
  49     HashedType *RHS = RHSP.Ptr;
  50     if (RHS == getEmptyKey().Ptr || RHS == getTombstoneKey().Ptr)
  51       return LHS == RHS;
  52     if (LHS->Hash != RHS->Hash || LHS->Size != RHS->Size)
  53       return false;
  54     return ::memcmp(LHS->Data, RHS->Data, LHS->Size) == 0;
  55   }
  56 };
  57 }
  58
  59 /// Private implementation so that we don't leak our DenseMap instantiations to
  60 /// users.
  61 class llvm::codeview::TypeHasher {
  62 private:
  63   /// Storage for type record provided by the caller. Records will outlive the
  64   /// hasher object, so they should be allocated here.
  65   BumpPtrAllocator &RecordStorage;
  66
  67   /// Storage for hash keys. These only need to live as long as the hashing
  68   /// operation.
  69   BumpPtrAllocator KeyStorage;
  70
  71   /// Hash table. We really want a DenseMap<ArrayRef<uint8_t>, TypeIndex> here,
  72   /// but DenseMap is inefficient when the keys are long (like type records)
  73   /// because it recomputes the hash value of every key when it grows. This
  74   /// value type stores the hash out of line in KeyStorage, so that table
  75   /// entries are small and easy to rehash.
  76   DenseSet<HashedTypePtr> HashedRecords;
  77
  78 public:
  79   TypeHasher(BumpPtrAllocator &RecordStorage) : RecordStorage(RecordStorage) {}
  80
  81   void reset() { HashedRecords.clear(); }
  82
  83   /// Takes the bytes of type record, inserts them into the hash table, saves
  84   /// them, and returns a pointer to an identical stable type record along with
  85   /// its type index in the destination stream.
  86   TypeIndex getOrCreateRecord(ArrayRef<uint8_t> &Record, TypeIndex TI);
  87 };
  88
  89 TypeIndex TypeHasher::getOrCreateRecord(ArrayRef<uint8_t> &Record,
  90                                         TypeIndex TI) {
  91   assert(Record.size() < UINT32_MAX && "Record too big");
  92   assert(Record.size() % 4 == 0 && "Record is not aligned to 4 bytes!");
  93
  94   // Compute the hash up front so we can store it in the key.
  95   HashedType TempHashedType = {hash_value(Record), Record.data(),
  96                                unsigned(Record.size()), TI};
  97   auto Result = HashedRecords.insert(HashedTypePtr(&TempHashedType));
  98   HashedType *&Hashed = Result.first->Ptr;
  99
 100   if (Result.second) {
 101     // This was a new type record. We need stable storage for both the key and
 102     // the record. The record should outlive the hashing operation.
 103     Hashed = KeyStorage.Allocate<HashedType>();
 104     *Hashed = TempHashedType;
 105
 106     uint8_t *Stable = RecordStorage.Allocate<uint8_t>(Record.size());
 107     memcpy(Stable, Record.data(), Record.size());
 108     Hashed->Data = Stable;
 109     assert(Hashed->Size == Record.size());
 110   }
 111
 112   // Update the caller's copy of Record to point a stable copy.
 113   Record = ArrayRef<uint8_t>(Hashed->Data, Hashed->Size);
 114   return Hashed->Index;
 115 }
 116
 117 TypeIndex TypeSerializer::nextTypeIndex() const {
 118   return TypeIndex::fromArrayIndex(SeenRecords.size());
 119 }
 120
 121 bool TypeSerializer::isInFieldList() const {
 122   return TypeKind.hasValue() && *TypeKind == TypeLeafKind::LF_FIELDLIST;
 123 }
 124
 125 MutableArrayRef<uint8_t> TypeSerializer::getCurrentSubRecordData() {
 126   assert(isInFieldList());
 127   return getCurrentRecordData().drop_front(CurrentSegment.length());
 128 }
 129
 130 MutableArrayRef<uint8_t> TypeSerializer::getCurrentRecordData() {
 131   return MutableArrayRef<uint8_t>(RecordBuffer).take_front(Writer.getOffset());
 132 }
 133
 134 Error TypeSerializer::writeRecordPrefix(TypeLeafKind Kind) {
 135   RecordPrefix Prefix;
 136   Prefix.RecordKind = Kind;
 137   Prefix.RecordLen = 0;
 138   if (auto EC = Writer.writeObject(Prefix))
 139     return EC;
 140   return Error::success();
 141 }
 142
 143 Expected<MutableArrayRef<uint8_t>>
 144 TypeSerializer::addPadding(MutableArrayRef<uint8_t> Record) {
 145   uint32_t Align = Record.size() % 4;
 146   if (Align == 0)
 147     return Record;
 148
 149   int PaddingBytes = 4 - Align;
 150   int N = PaddingBytes;
 151   while (PaddingBytes > 0) {
 152     uint8_t Pad = static_cast<uint8_t>(LF_PAD0 + PaddingBytes);
 153     if (auto EC = Writer.writeInteger(Pad))
 154       return std::move(EC);
 155     --PaddingBytes;
 156   }
 157   return MutableArrayRef<uint8_t>(Record.data(), Record.size() + N);
 158 }
 159
 160 TypeSerializer::TypeSerializer(BumpPtrAllocator &Storage, bool Hash)
 161     : RecordStorage(Storage), RecordBuffer(MaxRecordLength * 2),
 162       Stream(RecordBuffer, llvm::support::little), Writer(Stream),
 163       Mapping(Writer) {
 164   // RecordBuffer needs to be able to hold enough data so that if we are 1
 165   // byte short of MaxRecordLen, and then we try to write MaxRecordLen bytes,
 166   // we won't overflow.
 167   if (Hash)
 168     Hasher = make_unique<TypeHasher>(Storage);
 169 }
 170
 171 TypeSerializer::~TypeSerializer() = default;
 172
 173 ArrayRef<ArrayRef<uint8_t>> TypeSerializer::records() const {
 174   return SeenRecords;
 175 }
 176
 177 void TypeSerializer::reset() {
 178   if (Hasher)
 179     Hasher->reset();
 180   Writer.setOffset(0);
 181   CurrentSegment = RecordSegment();
 182   FieldListSegments.clear();
 183   TypeKind.reset();
 184   MemberKind.reset();
 185   SeenRecords.clear();
 186 }
 187
 188 TypeIndex TypeSerializer::insertRecordBytes(ArrayRef<uint8_t> &Record) {
 189   assert(!TypeKind.hasValue() && "Already in a type mapping!");
 190   assert(Writer.getOffset() == 0 && "Stream has data already!");
 191
 192   if (Hasher) {
 193     TypeIndex ActualTI = Hasher->getOrCreateRecord(Record, nextTypeIndex());
 194     if (nextTypeIndex() == ActualTI)
 195       SeenRecords.push_back(Record);
 196     return ActualTI;
 197   }
 198
 199   TypeIndex NewTI = nextTypeIndex();
 200   uint8_t *Stable = RecordStorage.Allocate<uint8_t>(Record.size());
 201   memcpy(Stable, Record.data(), Record.size());
 202   Record = ArrayRef<uint8_t>(Stable, Record.size());
 203   SeenRecords.push_back(Record);
 204   return NewTI;
 205 }
 206
 207 TypeIndex TypeSerializer::insertRecord(const RemappedType &Record) {
 208   assert(!TypeKind.hasValue() && "Already in a type mapping!");
 209   assert(Writer.getOffset() == 0 && "Stream has data already!");
 210
 211   TypeIndex TI;
 212   ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.RecordData;
 213   if (Record.Mappings.empty()) {
 214     // This record did not remap any type indices.  Just write it.
 215     return insertRecordBytes(OriginalData);
 216   }
 217
 218   // At least one type index was remapped.  Before we can hash it we have to
 219   // copy the full record bytes, re-write each type index, then hash the copy.
 220   // We do this in temporary storage since only the DenseMap can decide whether
 221   // this record already exists, and if it does we don't want the memory to
 222   // stick around.
 223   RemapStorage.resize(OriginalData.size());
 224   ::memcpy(&RemapStorage[0], OriginalData.data(), OriginalData.size());
 225   uint8_t *ContentBegin = RemapStorage.data() + sizeof(RecordPrefix);
 226   for (const auto &M : Record.Mappings) {
 227     // First 4 bytes of every record are the record prefix, but the mapping
 228     // offset is relative to the content which starts after.
 229     *(TypeIndex *)(ContentBegin + M.first) = M.second;
 230   }
 231   auto RemapRef = makeArrayRef(RemapStorage);
 232   return insertRecordBytes(RemapRef);
 233 }
 234
 235 Error TypeSerializer::visitTypeBegin(CVType &Record) {
 236   assert(!TypeKind.hasValue() && "Already in a type mapping!");
 237   assert(Writer.getOffset() == 0 && "Stream has data already!");
 238
 239   if (auto EC = writeRecordPrefix(Record.kind()))
 240     return EC;
 241
 242   TypeKind = Record.kind();
 243   if (auto EC = Mapping.visitTypeBegin(Record))
 244     return EC;
 245
 246   return Error::success();
 247 }
 248
 249 Expected<TypeIndex> TypeSerializer::visitTypeEndGetIndex(CVType &Record) {
 250   assert(TypeKind.hasValue() && "Not in a type mapping!");
 251   if (auto EC = Mapping.visitTypeEnd(Record))
 252     return std::move(EC);
 253
 254   // Update the record's length and fill out the CVType members to point to
 255   // the stable memory holding the record's data.
 256   auto ThisRecordData = getCurrentRecordData();
 257   auto ExpectedData = addPadding(ThisRecordData);
 258   if (!ExpectedData)
 259     return ExpectedData.takeError();
 260   ThisRecordData = *ExpectedData;
 261
 262   RecordPrefix *Prefix =
 263       reinterpret_cast<RecordPrefix *>(ThisRecordData.data());
 264   Prefix->RecordLen = ThisRecordData.size() - sizeof(uint16_t);
 265
 266   Record.Type = *TypeKind;
 267   Record.RecordData = ThisRecordData;
 268
 269   // insertRecordBytes assumes we're not in a mapping, so do this first.
 270   TypeKind.reset();
 271   Writer.setOffset(0);
 272
 273   TypeIndex InsertedTypeIndex = insertRecordBytes(Record.RecordData);
 274
 275   // Write out each additional segment in reverse order, and update each
 276   // record's continuation index to point to the previous one.
 277   for (auto X : reverse(FieldListSegments)) {
 278     auto CIBytes = X.take_back(sizeof(uint32_t));
 279     support::ulittle32_t *CI =
 280         reinterpret_cast<support::ulittle32_t *>(CIBytes.data());
 281     assert(*CI == 0xB0C0B0C0 && "Invalid TypeIndex placeholder");
 282     *CI = InsertedTypeIndex.getIndex();
 283     InsertedTypeIndex = insertRecordBytes(X);
 284   }
 285
 286   FieldListSegments.clear();
 287   CurrentSegment.SubRecords.clear();
 288
 289   return InsertedTypeIndex;
 290 }
 291
 292 Error TypeSerializer::visitTypeEnd(CVType &Record) {
 293   auto ExpectedIndex = visitTypeEndGetIndex(Record);
 294   if (!ExpectedIndex)
 295     return ExpectedIndex.takeError();
 296   return Error::success();
 297 }
 298
 299 Error TypeSerializer::visitMemberBegin(CVMemberRecord &Record) {
 300   assert(isInFieldList() && "Not in a field list!");
 301   assert(!MemberKind.hasValue() && "Already in a member record!");
 302   MemberKind = Record.Kind;
 303
 304   if (auto EC = Mapping.visitMemberBegin(Record))
 305     return EC;
 306
 307   return Error::success();
 308 }
 309
 310 Error TypeSerializer::visitMemberEnd(CVMemberRecord &Record) {
 311   if (auto EC = Mapping.visitMemberEnd(Record))
 312     return EC;
 313
 314   // Check if this subrecord makes the current segment not fit in 64K minus
 315   // the space for a continuation record (8 bytes). If the segment does not
 316   // fit, insert a continuation record.
 317   if (Writer.getOffset() > MaxRecordLength - ContinuationLength) {
 318     MutableArrayRef<uint8_t> Data = getCurrentRecordData();
 319     SubRecord LastSubRecord = CurrentSegment.SubRecords.back();
 320     uint32_t CopySize = CurrentSegment.length() - LastSubRecord.Size;
 321     auto CopyData = Data.take_front(CopySize);
 322     auto LeftOverData = Data.drop_front(CopySize);
 323     assert(LastSubRecord.Size == LeftOverData.size());
 324
 325     // Allocate stable storage for the record and copy the old record plus
 326     // continuation over.
 327     uint16_t LengthWithSize = CopySize + ContinuationLength;
 328     assert(LengthWithSize <= MaxRecordLength);
 329     RecordPrefix *Prefix = reinterpret_cast<RecordPrefix *>(CopyData.data());
 330     Prefix->RecordLen = LengthWithSize - sizeof(uint16_t);
 331
 332     uint8_t *SegmentBytes = RecordStorage.Allocate<uint8_t>(LengthWithSize);
 333     auto SavedSegment = MutableArrayRef<uint8_t>(SegmentBytes, LengthWithSize);
 334     MutableBinaryByteStream CS(SavedSegment, llvm::support::little);
 335     BinaryStreamWriter CW(CS);
 336     if (auto EC = CW.writeBytes(CopyData))
 337       return EC;
 338     if (auto EC = CW.writeEnum(TypeLeafKind::LF_INDEX))
 339       return EC;
 340     if (auto EC = CW.writeInteger<uint16_t>(0))
 341       return EC;
 342     if (auto EC = CW.writeInteger<uint32_t>(0xB0C0B0C0))
 343       return EC;
 344     FieldListSegments.push_back(SavedSegment);
 345
 346     // Write a new placeholder record prefix to mark the start of this new
 347     // top-level record.
 348     Writer.setOffset(0);
 349     if (auto EC = writeRecordPrefix(TypeLeafKind::LF_FIELDLIST))
 350       return EC;
 351
 352     // Then move over the subrecord that overflowed the old segment to the
 353     // beginning of this segment.  Note that we have to use memmove here
 354     // instead of Writer.writeBytes(), because the new and old locations
 355     // could overlap.
 356     ::memmove(Stream.data().data() + sizeof(RecordPrefix), LeftOverData.data(),
 357               LeftOverData.size());
 358     // And point the segment writer at the end of that subrecord.
 359     Writer.setOffset(LeftOverData.size() + sizeof(RecordPrefix));
 360
 361     CurrentSegment.SubRecords.clear();
 362     CurrentSegment.SubRecords.push_back(LastSubRecord);
 363   }
 364
 365   // Update the CVMemberRecord since we may have shifted around or gotten
 366   // padded.
 367   Record.Data = getCurrentSubRecordData();
 368
 369   MemberKind.reset();
 370   return Error::success();
 371 }