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