LLVM  7.0.0svn
TypeStreamMerger.cpp
Go to the documentation of this file.
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 
11 #include "llvm/ADT/SmallString.h"
12 #include "llvm/ADT/StringExtras.h"
18 #include "llvm/Support/Error.h"
19 
20 using namespace llvm;
21 using namespace llvm::codeview;
22 
23 namespace {
24 
25 /// Implementation of CodeView type stream merging.
26 ///
27 /// A CodeView type stream is a series of records that reference each other
28 /// through type indices. A type index is either "simple", meaning it is less
29 /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
30 /// refers to a prior type record in the current stream. The type index of a
31 /// record is equal to the number of records before it in the stream plus
32 /// 0x1000.
33 ///
34 /// Type records are only allowed to use type indices smaller than their own, so
35 /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
36 /// the type graph of the source program are resolved with forward declarations
37 /// of composite types. This class implements the following type stream merging
38 /// algorithm, which relies on this DAG structure:
39 ///
40 /// - Begin with a new empty stream, and a new empty hash table that maps from
41 /// type record contents to new type index.
42 /// - For each new type stream, maintain a map from source type index to
43 /// destination type index.
44 /// - For each record, copy it and rewrite its type indices to be valid in the
45 /// destination type stream.
46 /// - If the new type record is not already present in the destination stream
47 /// hash table, append it to the destination type stream, assign it the next
48 /// type index, and update the two hash tables.
49 /// - If the type record already exists in the destination stream, discard it
50 /// and update the type index map to forward the source type index to the
51 /// existing destination type index.
52 ///
53 /// As an additional complication, type stream merging actually produces two
54 /// streams: an item (or IPI) stream and a type stream, as this is what is
55 /// actually stored in the final PDB. We choose which records go where by
56 /// looking at the record kind.
57 class TypeStreamMerger {
58 public:
59  explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest)
60  : IndexMap(SourceToDest) {
61  SourceToDest.clear();
62  }
63 
64  static const TypeIndex Untranslated;
65 
66  // Local hashing entry points
67  Error mergeTypesAndIds(MergingTypeTableBuilder &DestIds,
68  MergingTypeTableBuilder &DestTypes,
69  const CVTypeArray &IdsAndTypes);
71  ArrayRef<TypeIndex> TypeSourceToDest,
72  const CVTypeArray &Ids);
74  const CVTypeArray &Types);
75 
76  // Global hashing entry points
77  Error mergeTypesAndIds(GlobalTypeTableBuilder &DestIds,
78  GlobalTypeTableBuilder &DestTypes,
79  const CVTypeArray &IdsAndTypes,
82  ArrayRef<TypeIndex> TypeSourceToDest,
83  const CVTypeArray &Ids,
87 
88 private:
89  Error doit(const CVTypeArray &Types);
90 
91  Error remapAllTypes(const CVTypeArray &Types);
92 
93  Error remapType(const CVType &Type);
94 
95  void addMapping(TypeIndex Idx);
96 
97  bool remapTypeIndex(TypeIndex &Idx);
98  bool remapItemIndex(TypeIndex &Idx);
99 
100  bool hasTypeStream() const {
101  return (UseGlobalHashes) ? (!!DestGlobalTypeStream) : (!!DestTypeStream);
102  }
103 
104  bool hasIdStream() const {
105  return (UseGlobalHashes) ? (!!DestGlobalIdStream) : (!!DestIdStream);
106  }
107 
108  ArrayRef<uint8_t> serializeRemapped(const RemappedType &Record);
109 
110  bool remapIndices(RemappedType &Record, ArrayRef<TiReference> Refs);
111 
112  bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
113 
114  size_t slotForIndex(TypeIndex Idx) const {
115  assert(!Idx.isSimple() && "simple type indices have no slots");
117  }
118 
119  Error errorCorruptRecord() const {
120  return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
121  }
122 
123  Optional<Error> LastError;
124 
125  bool UseGlobalHashes = false;
126 
127  bool IsSecondPass = false;
128 
129  unsigned NumBadIndices = 0;
130 
132 
133  MergingTypeTableBuilder *DestIdStream = nullptr;
134  MergingTypeTableBuilder *DestTypeStream = nullptr;
135 
136  GlobalTypeTableBuilder *DestGlobalIdStream = nullptr;
137  GlobalTypeTableBuilder *DestGlobalTypeStream = nullptr;
138 
139  ArrayRef<GloballyHashedType> GlobalHashes;
140 
141  // If we're only mapping id records, this array contains the mapping for
142  // type records.
143  ArrayRef<TypeIndex> TypeLookup;
144 
145  /// Map from source type index to destination type index. Indexed by source
146  /// type index minus 0x1000.
147  SmallVectorImpl<TypeIndex> &IndexMap;
148 
149  /// Temporary storage that we use to copy a record's data while re-writing
150  /// its type indices.
151  SmallVector<uint8_t, 256> RemapStorage;
152 };
153 
154 } // end anonymous namespace
155 
157 TypeStreamMerger::serializeRemapped(const RemappedType &Record) {
158  TypeIndex TI;
159  ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.RecordData;
160  if (Record.Mappings.empty())
161  return OriginalData;
162 
163  // At least one type index was remapped. We copy the full record bytes,
164  // re-write each type index, then return that.
165  RemapStorage.resize(OriginalData.size());
166  ::memcpy(&RemapStorage[0], OriginalData.data(), OriginalData.size());
167  uint8_t *ContentBegin = RemapStorage.data() + sizeof(RecordPrefix);
168  for (const auto &M : Record.Mappings) {
169  // First 4 bytes of every record are the record prefix, but the mapping
170  // offset is relative to the content which starts after.
171  *(TypeIndex *)(ContentBegin + M.first) = M.second;
172  }
173  auto RemapRef = makeArrayRef(RemapStorage);
174  return RemapRef;
175 }
176 
177 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
178 
179 static bool isIdRecord(TypeLeafKind K) {
180  switch (K) {
181  case TypeLeafKind::LF_FUNC_ID:
182  case TypeLeafKind::LF_MFUNC_ID:
183  case TypeLeafKind::LF_STRING_ID:
184  case TypeLeafKind::LF_SUBSTR_LIST:
185  case TypeLeafKind::LF_BUILDINFO:
186  case TypeLeafKind::LF_UDT_SRC_LINE:
187  case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
188  return true;
189  default:
190  return false;
191  }
192 }
193 
194 void TypeStreamMerger::addMapping(TypeIndex Idx) {
195  if (!IsSecondPass) {
196  assert(IndexMap.size() == slotForIndex(CurIndex) &&
197  "visitKnownRecord should add one index map entry");
198  IndexMap.push_back(Idx);
199  } else {
200  assert(slotForIndex(CurIndex) < IndexMap.size());
201  IndexMap[slotForIndex(CurIndex)] = Idx;
202  }
203 }
204 
205 bool TypeStreamMerger::remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
206  // Simple types are unchanged.
207  if (Idx.isSimple())
208  return true;
209 
210  // Check if this type index refers to a record we've already translated
211  // successfully. If it refers to a type later in the stream or a record we
212  // had to defer, defer it until later pass.
213  unsigned MapPos = slotForIndex(Idx);
214  if (MapPos < Map.size() && Map[MapPos] != Untranslated) {
215  Idx = Map[MapPos];
216  return true;
217  }
218 
219  // If this is the second pass and this index isn't in the map, then it points
220  // outside the current type stream, and this is a corrupt record.
221  if (IsSecondPass && MapPos >= Map.size()) {
222  // FIXME: Print a more useful error. We can give the current record and the
223  // index that we think its pointing to.
224  LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
225  }
226 
227  ++NumBadIndices;
228 
229  // This type index is invalid. Remap this to "not translated by cvpack",
230  // and return failure.
231  Idx = Untranslated;
232  return false;
233 }
234 
235 bool TypeStreamMerger::remapTypeIndex(TypeIndex &Idx) {
236  // If we're mapping a pure index stream, then IndexMap only contains mappings
237  // from OldIdStream -> NewIdStream, in which case we will need to use the
238  // special mapping from OldTypeStream -> NewTypeStream which was computed
239  // externally. Regardless, we use this special map if and only if we are
240  // doing an id-only mapping.
241  if (!hasTypeStream())
242  return remapIndex(Idx, TypeLookup);
243 
244  assert(TypeLookup.empty());
245  return remapIndex(Idx, IndexMap);
246 }
247 
248 bool TypeStreamMerger::remapItemIndex(TypeIndex &Idx) {
249  assert(hasIdStream());
250  return remapIndex(Idx, IndexMap);
251 }
252 
253 // Local hashing entry points
255  const CVTypeArray &Types) {
256  DestTypeStream = &Dest;
257  UseGlobalHashes = false;
258 
259  return doit(Types);
260 }
261 
263  ArrayRef<TypeIndex> TypeSourceToDest,
264  const CVTypeArray &Ids) {
265  DestIdStream = &Dest;
266  TypeLookup = TypeSourceToDest;
267  UseGlobalHashes = false;
268 
269  return doit(Ids);
270 }
271 
272 Error TypeStreamMerger::mergeTypesAndIds(MergingTypeTableBuilder &DestIds,
273  MergingTypeTableBuilder &DestTypes,
274  const CVTypeArray &IdsAndTypes) {
275  DestIdStream = &DestIds;
276  DestTypeStream = &DestTypes;
277  UseGlobalHashes = false;
278  return doit(IdsAndTypes);
279 }
280 
281 // Global hashing entry points
283  const CVTypeArray &Types,
285  DestGlobalTypeStream = &Dest;
286  UseGlobalHashes = true;
287  GlobalHashes = Hashes;
288 
289  return doit(Types);
290 }
291 
293  ArrayRef<TypeIndex> TypeSourceToDest,
294  const CVTypeArray &Ids,
296  DestGlobalIdStream = &Dest;
297  TypeLookup = TypeSourceToDest;
298  UseGlobalHashes = true;
299  GlobalHashes = Hashes;
300 
301  return doit(Ids);
302 }
303 
304 Error TypeStreamMerger::mergeTypesAndIds(GlobalTypeTableBuilder &DestIds,
305  GlobalTypeTableBuilder &DestTypes,
306  const CVTypeArray &IdsAndTypes,
308  DestGlobalIdStream = &DestIds;
309  DestGlobalTypeStream = &DestTypes;
310  UseGlobalHashes = true;
311  GlobalHashes = Hashes;
312  return doit(IdsAndTypes);
313 }
314 
315 Error TypeStreamMerger::doit(const CVTypeArray &Types) {
316  if (auto EC = remapAllTypes(Types))
317  return EC;
318 
319  // If we found bad indices but no other errors, try doing another pass and see
320  // if we can resolve the indices that weren't in the map on the first pass.
321  // This may require multiple passes, but we should always make progress. MASM
322  // is the only known CodeView producer that makes type streams that aren't
323  // topologically sorted. The standard library contains MASM-produced objects,
324  // so this is important to handle correctly, but we don't have to be too
325  // efficient. MASM type streams are usually very small.
326  while (!LastError && NumBadIndices > 0) {
327  unsigned BadIndicesRemaining = NumBadIndices;
328  IsSecondPass = true;
329  NumBadIndices = 0;
331 
332  if (auto EC = remapAllTypes(Types))
333  return EC;
334 
335  assert(NumBadIndices <= BadIndicesRemaining &&
336  "second pass found more bad indices");
337  if (!LastError && NumBadIndices == BadIndicesRemaining) {
338  return llvm::make_error<CodeViewError>(
339  cv_error_code::corrupt_record, "input type graph contains cycles");
340  }
341  }
342 
343  if (LastError)
344  return std::move(*LastError);
345  return Error::success();
346 }
347 
348 Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
349  BinaryStreamRef Stream = Types.getUnderlyingStream();
350  ArrayRef<uint8_t> Buffer;
351  cantFail(Stream.readBytes(0, Stream.getLength(), Buffer));
352 
353  return forEachCodeViewRecord<CVType>(
354  Buffer, [this](const CVType &T) { return remapType(T); });
355 }
356 
357 Error TypeStreamMerger::remapType(const CVType &Type) {
358  auto DoSerialize = [this, Type]() -> ArrayRef<uint8_t> {
359  RemappedType R(Type);
361  discoverTypeIndices(Type.RecordData, Refs);
362  if (!remapIndices(R, Refs))
363  return {};
364  return serializeRemapped(R);
365  };
366 
367  TypeIndex DestIdx = Untranslated;
368  if (UseGlobalHashes) {
369  GlobalTypeTableBuilder &Dest =
370  isIdRecord(Type.kind()) ? *DestGlobalIdStream : *DestGlobalTypeStream;
371  GloballyHashedType H = GlobalHashes[CurIndex.toArrayIndex()];
372  DestIdx = Dest.insertRecordAs(H, DoSerialize);
373  } else {
375  isIdRecord(Type.kind()) ? *DestIdStream : *DestTypeStream;
376 
377  auto Data = DoSerialize();
378  if (!Data.empty())
379  DestIdx = Dest.insertRecordBytes(Data);
380  }
381  addMapping(DestIdx);
382 
383  ++CurIndex;
384  assert((IsSecondPass || IndexMap.size() == slotForIndex(CurIndex)) &&
385  "visitKnownRecord should add one index map entry");
386  return Error::success();
387 }
388 
389 bool TypeStreamMerger::remapIndices(RemappedType &Record,
390  ArrayRef<TiReference> Refs) {
391  ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.content();
392  bool Success = true;
393  for (auto &Ref : Refs) {
394  uint32_t Offset = Ref.Offset;
395  ArrayRef<uint8_t> Bytes = OriginalData.slice(Ref.Offset, sizeof(TypeIndex));
396  ArrayRef<TypeIndex> TIs(reinterpret_cast<const TypeIndex *>(Bytes.data()),
397  Ref.Count);
398  for (auto TI : TIs) {
399  TypeIndex NewTI = TI;
400  bool ThisSuccess = (Ref.Kind == TiRefKind::IndexRef)
401  ? remapItemIndex(NewTI)
402  : remapTypeIndex(NewTI);
403  if (ThisSuccess && NewTI != TI)
404  Record.Mappings.emplace_back(Offset, NewTI);
405  Offset += sizeof(TypeIndex);
406  Success &= ThisSuccess;
407  }
408  }
409  return Success;
410 }
411 
413  SmallVectorImpl<TypeIndex> &SourceToDest,
414  const CVTypeArray &Types) {
415  TypeStreamMerger M(SourceToDest);
416  return M.mergeTypeRecords(Dest, Types);
417 }
418 
420  ArrayRef<TypeIndex> TypeSourceToDest,
421  SmallVectorImpl<TypeIndex> &SourceToDest,
422  const CVTypeArray &Ids) {
423  TypeStreamMerger M(SourceToDest);
424  return M.mergeIdRecords(Dest, TypeSourceToDest, Ids);
425 }
426 
429  SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes) {
430  TypeStreamMerger M(SourceToDest);
431  return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes);
432 }
433 
435  GlobalTypeTableBuilder &DestIds, GlobalTypeTableBuilder &DestTypes,
436  SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes,
438  TypeStreamMerger M(SourceToDest);
439  return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes, Hashes);
440 }
441 
443  SmallVectorImpl<TypeIndex> &SourceToDest,
444  const CVTypeArray &Types,
446  TypeStreamMerger M(SourceToDest);
447  return M.mergeTypeRecords(Dest, Types, Hashes);
448 }
449 
451  ArrayRef<TypeIndex> Types,
452  SmallVectorImpl<TypeIndex> &SourceToDest,
453  const CVTypeArray &Ids,
455  TypeStreamMerger M(SourceToDest);
456  return M.mergeIdRecords(Dest, Types, Ids, Hashes);
457 }
void cantFail(Error Err, const char *Msg=nullptr)
Report a fatal error if Err is a failure value.
Definition: Error.h:688
void discoverTypeIndices(ArrayRef< uint8_t > RecordData, SmallVectorImpl< TiReference > &Refs)
Kind kind() const
Definition: CVRecord.h:37
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
TypeLeafKind
Duplicate copy of the above enum, but using the official CV names.
Definition: CodeView.h:34
Error mergeTypeAndIdRecords(MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &IdsAndTypes)
Merge a unified set of type and id records, splitting them into separate output streams.
BinaryStreamRef getUnderlyingStream() const
Error mergeTypeRecords(MergingTypeTableBuilder &Dest, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &Types)
Merge one set of type records into another.
SmallVector< std::pair< uint32_t, TypeIndex >, 8 > Mappings
Definition: CVRecord.h:61
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
CVRecord< Kind > OriginalRecord
Definition: CVRecord.h:60
#define T
static const uint32_t FirstNonSimpleIndex
Definition: TypeIndex.h:98
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
A 32-bit type reference.
Definition: TypeIndex.h:96
A globally hashed type represents a hash value that is sufficient to uniquely identify a record acros...
Definition: TypeHashing.h:75
Error readBytes(uint32_t Offset, uint32_t Size, ArrayRef< uint8_t > &Buffer) const
Given an Offset into this StreamRef and a Size, return a reference to a buffer owned by the stream...
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
#define H(x, y, z)
Definition: MD5.cpp:57
const T * data() const
Definition: ArrayRef.h:146
uint32_t getIndex() const
Definition: TypeIndex.h:111
uint32_t getLength() const
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
BinaryStreamRef is to BinaryStream what ArrayRef is to an Array.
static bool isIdRecord(TypeLeafKind K)
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array...
Definition: ArrayRef.h:179
#define Success
ArrayRef< uint8_t > RecordData
Definition: CVRecord.h:53
TypeIndex insertRecordAs(GloballyHashedType Hash, CreateRecord Create)
Error joinErrors(Error E1, Error E2)
Concatenate errors.
Definition: Error.h:408
TypeIndex insertRecordBytes(ArrayRef< uint8_t > &Record)
Error mergeIdRecords(MergingTypeTableBuilder &Dest, ArrayRef< TypeIndex > Types, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &Ids)
Merge one set of id records into another.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
The access may reference the value stored in memory.