llvm-project

1
//===- DebugTypes.cpp -----------------------------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8

9
#include "DebugTypes.h"
10
#include "COFFLinkerContext.h"
11
#include "Chunks.h"
12
#include "Driver.h"
13
#include "InputFiles.h"
14
#include "PDB.h"
15
#include "TypeMerger.h"
16
#include "lld/Common/ErrorHandler.h"
17
#include "lld/Common/Memory.h"
18
#include "llvm/ADT/StringExtras.h"
19
#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
20
#include "llvm/DebugInfo/CodeView/TypeRecord.h"
21
#include "llvm/DebugInfo/CodeView/TypeRecordHelpers.h"
22
#include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
23
#include "llvm/DebugInfo/PDB/GenericError.h"
24
#include "llvm/DebugInfo/PDB/Native/InfoStream.h"
25
#include "llvm/DebugInfo/PDB/Native/NativeSession.h"
26
#include "llvm/DebugInfo/PDB/Native/PDBFile.h"
27
#include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
28
#include "llvm/DebugInfo/PDB/Native/TpiStream.h"
29
#include "llvm/Support/FormatVariadic.h"
30
#include "llvm/Support/Parallel.h"
31
#include "llvm/Support/Path.h"
32
#include "llvm/Support/TimeProfiler.h"
33

34
using namespace llvm;
35
using namespace llvm::codeview;
36
using namespace lld;
37
using namespace lld::coff;
38

39
namespace {
40
class TypeServerIpiSource;
41

42
// The TypeServerSource class represents a PDB type server, a file referenced by
43
// OBJ files compiled with MSVC /Zi. A single PDB can be shared by several OBJ
44
// files, therefore there must be only once instance per OBJ lot. The file path
45
// is discovered from the dependent OBJ's debug type stream. The
46
// TypeServerSource object is then queued and loaded by the COFF Driver. The
47
// debug type stream for such PDB files will be merged first in the final PDB,
48
// before any dependent OBJ.
49
class TypeServerSource : public TpiSource {
50
public:
51
  explicit TypeServerSource(COFFLinkerContext &ctx, PDBInputFile *f)
52
      : TpiSource(ctx, PDB, nullptr), pdbInputFile(f) {
53
    if (f->loadErrorStr)
54
      return;
55
    pdb::PDBFile &file = f->session->getPDBFile();
56
    auto expectedInfo = file.getPDBInfoStream();
57
    if (!expectedInfo)
58
      return;
59
    Guid = expectedInfo->getGuid();
60
    auto it = ctx.typeServerSourceMappings.emplace(Guid, this);
61
    if (!it.second) {
62
      // If we hit here we have collision on Guid's in two PDB files.
63
      // This can happen if the PDB Guid is invalid or if we are really
64
      // unlucky. This should fall back on stright file-system lookup.
65
      it.first->second = nullptr;
66
    }
67
  }
68

69
  Error mergeDebugT(TypeMerger *m) override;
70

71
  void loadGHashes() override;
72
  void remapTpiWithGHashes(GHashState *g) override;
73

74
  bool isDependency() const override { return true; }
75

76
  PDBInputFile *pdbInputFile = nullptr;
77

78
  // TpiSource for IPI stream.
79
  TypeServerIpiSource *ipiSrc = nullptr;
80

81
  // The PDB signature GUID.
82
  codeview::GUID Guid;
83
};
84

85
// Companion to TypeServerSource. Stores the index map for the IPI stream in the
86
// PDB. Modeling PDBs with two sources for TPI and IPI helps establish the
87
// invariant of one type index space per source.
88
class TypeServerIpiSource : public TpiSource {
89
public:
90
  explicit TypeServerIpiSource(COFFLinkerContext &ctx)
91
      : TpiSource(ctx, PDBIpi, nullptr) {}
92

93
  friend class TypeServerSource;
94

95
  // All of the TpiSource methods are no-ops. The parent TypeServerSource
96
  // handles both TPI and IPI.
97
  Error mergeDebugT(TypeMerger *m) override { return Error::success(); }
98
  void loadGHashes() override {}
99
  void remapTpiWithGHashes(GHashState *g) override {}
100
  bool isDependency() const override { return true; }
101
};
102

103
// This class represents the debug type stream of an OBJ file that depends on a
104
// PDB type server (see TypeServerSource).
105
class UseTypeServerSource : public TpiSource {
106
  Expected<TypeServerSource *> getTypeServerSource();
107

108
public:
109
  UseTypeServerSource(COFFLinkerContext &ctx, ObjFile *f, TypeServer2Record ts)
110
      : TpiSource(ctx, UsingPDB, f), typeServerDependency(ts) {}
111

112
  Error mergeDebugT(TypeMerger *m) override;
113

114
  // No need to load ghashes from /Zi objects.
115
  void loadGHashes() override {}
116
  void remapTpiWithGHashes(GHashState *g) override;
117

118
  // Information about the PDB type server dependency, that needs to be loaded
119
  // in before merging this OBJ.
120
  TypeServer2Record typeServerDependency;
121
};
122

123
// This class represents the debug type stream of a Microsoft precompiled
124
// headers OBJ (PCH OBJ). This OBJ kind needs to be merged first in the output
125
// PDB, before any other OBJs that depend on this. Note that only MSVC generate
126
// such files, clang does not.
127
class PrecompSource : public TpiSource {
128
public:
129
  PrecompSource(COFFLinkerContext &ctx, ObjFile *f) : TpiSource(ctx, PCH, f) {
130
    // If the S_OBJNAME record contains the PCH signature, we'll register this
131
    // source file right away.
132
    registerMapping();
133
  }
134

135
  Error mergeDebugT(TypeMerger *m) override;
136

137
  void loadGHashes() override;
138

139
  bool isDependency() const override { return true; }
140

141
private:
142
  void registerMapping();
143

144
  // Whether this precomp OBJ was recorded in the precompSourceMappings map.
145
  // Only happens if the file->pchSignature is valid.
146
  bool registered = false;
147
};
148

149
// This class represents the debug type stream of an OBJ file that depends on a
150
// Microsoft precompiled headers OBJ (see PrecompSource).
151
class UsePrecompSource : public TpiSource {
152
public:
153
  UsePrecompSource(COFFLinkerContext &ctx, ObjFile *f, PrecompRecord precomp)
154
      : TpiSource(ctx, UsingPCH, f), precompDependency(precomp) {}
155

156
  Error mergeDebugT(TypeMerger *m) override;
157

158
  void loadGHashes() override;
159
  void remapTpiWithGHashes(GHashState *g) override;
160

161
private:
162
  Error mergeInPrecompHeaderObj();
163

164
  PrecompSource *findObjByName(StringRef fileNameOnly);
165
  PrecompSource *findPrecompSource(ObjFile *file, PrecompRecord &pr);
166
  Expected<PrecompSource *> findPrecompMap(ObjFile *file, PrecompRecord &pr);
167

168
public:
169
  // Information about the Precomp OBJ dependency, that needs to be loaded in
170
  // before merging this OBJ.
171
  PrecompRecord precompDependency;
172
};
173
} // namespace
174

175
TpiSource::TpiSource(COFFLinkerContext &ctx, TpiKind k, ObjFile *f)
176
    : ctx(ctx), kind(k), tpiSrcIdx(ctx.tpiSourceList.size()), file(f) {
177
  ctx.addTpiSource(this);
178
}
179

180
// Vtable key method.
181
TpiSource::~TpiSource() {
182
  // Silence any assertions about unchecked errors.
183
  consumeError(std::move(typeMergingError));
184
}
185

186
TpiSource *lld::coff::makeTpiSource(COFFLinkerContext &ctx, ObjFile *file) {
187
  return make<TpiSource>(ctx, TpiSource::Regular, file);
188
}
189

190
TpiSource *lld::coff::makeTypeServerSource(COFFLinkerContext &ctx,
191
                                           PDBInputFile *pdbInputFile) {
192
  // Type server sources come in pairs: the TPI stream, and the IPI stream.
193
  auto *tpiSource = make<TypeServerSource>(ctx, pdbInputFile);
194
  if (pdbInputFile->session->getPDBFile().hasPDBIpiStream())
195
    tpiSource->ipiSrc = make<TypeServerIpiSource>(ctx);
196
  return tpiSource;
197
}
198

199
TpiSource *lld::coff::makeUseTypeServerSource(COFFLinkerContext &ctx,
200
                                              ObjFile *file,
201
                                              TypeServer2Record ts) {
202
  return make<UseTypeServerSource>(ctx, file, ts);
203
}
204

205
TpiSource *lld::coff::makePrecompSource(COFFLinkerContext &ctx, ObjFile *file) {
206
  return make<PrecompSource>(ctx, file);
207
}
208

209
TpiSource *lld::coff::makeUsePrecompSource(COFFLinkerContext &ctx,
210
                                           ObjFile *file,
211
                                           PrecompRecord precomp) {
212
  return make<UsePrecompSource>(ctx, file, precomp);
213
}
214

215
bool TpiSource::remapTypeIndex(TypeIndex &ti, TiRefKind refKind) const {
216
  if (ti.isSimple())
217
    return true;
218

219
  // This can be an item index or a type index. Choose the appropriate map.
220
  ArrayRef<TypeIndex> tpiOrIpiMap =
221
      (refKind == TiRefKind::IndexRef) ? ipiMap : tpiMap;
222
  if (ti.toArrayIndex() >= tpiOrIpiMap.size())
223
    return false;
224
  ti = tpiOrIpiMap[ti.toArrayIndex()];
225
  return true;
226
}
227

228
void TpiSource::remapRecord(MutableArrayRef<uint8_t> rec,
229
                            ArrayRef<TiReference> typeRefs) {
230
  MutableArrayRef<uint8_t> contents = rec.drop_front(sizeof(RecordPrefix));
231
  for (const TiReference &ref : typeRefs) {
232
    unsigned byteSize = ref.Count * sizeof(TypeIndex);
233
    if (contents.size() < ref.Offset + byteSize)
234
      fatal("symbol record too short");
235

236
    MutableArrayRef<TypeIndex> indices(
237
        reinterpret_cast<TypeIndex *>(contents.data() + ref.Offset), ref.Count);
238
    for (TypeIndex &ti : indices) {
239
      if (!remapTypeIndex(ti, ref.Kind)) {
240
        if (ctx.config.verbose) {
241
          uint16_t kind =
242
              reinterpret_cast<const RecordPrefix *>(rec.data())->RecordKind;
243
          StringRef fname = file ? file->getName() : "<unknown PDB>";
244
          log("failed to remap type index in record of kind 0x" +
245
              utohexstr(kind) + " in " + fname + " with bad " +
246
              (ref.Kind == TiRefKind::IndexRef ? "item" : "type") +
247
              " index 0x" + utohexstr(ti.getIndex()));
248
        }
249
        ti = TypeIndex(SimpleTypeKind::NotTranslated);
250
        continue;
251
      }
252
    }
253
  }
254
}
255

256
void TpiSource::remapTypesInTypeRecord(MutableArrayRef<uint8_t> rec) {
257
  // TODO: Handle errors similar to symbols.
258
  SmallVector<TiReference, 32> typeRefs;
259
  discoverTypeIndices(CVType(rec), typeRefs);
260
  remapRecord(rec, typeRefs);
261
}
262

263
bool TpiSource::remapTypesInSymbolRecord(MutableArrayRef<uint8_t> rec) {
264
  // Discover type index references in the record. Skip it if we don't
265
  // know where they are.
266
  SmallVector<TiReference, 32> typeRefs;
267
  if (!discoverTypeIndicesInSymbol(rec, typeRefs))
268
    return false;
269
  remapRecord(rec, typeRefs);
270
  return true;
271
}
272

273
// A COFF .debug$H section is currently a clang extension.  This function checks
274
// if a .debug$H section is in a format that we expect / understand, so that we
275
// can ignore any sections which are coincidentally also named .debug$H but do
276
// not contain a format we recognize.
277
static bool canUseDebugH(ArrayRef<uint8_t> debugH) {
278
  if (debugH.size() < sizeof(object::debug_h_header))
279
    return false;
280
  auto *header =
281
      reinterpret_cast<const object::debug_h_header *>(debugH.data());
282
  debugH = debugH.drop_front(sizeof(object::debug_h_header));
283
  return header->Magic == COFF::DEBUG_HASHES_SECTION_MAGIC &&
284
         header->Version == 0 &&
285
         header->HashAlgorithm == uint16_t(GlobalTypeHashAlg::BLAKE3) &&
286
         (debugH.size() % 8 == 0);
287
}
288

289
static std::optional<ArrayRef<uint8_t>> getDebugH(ObjFile *file) {
290
  SectionChunk *sec =
291
      SectionChunk::findByName(file->getDebugChunks(), ".debug$H");
292
  if (!sec)
293
    return std::nullopt;
294
  ArrayRef<uint8_t> contents = sec->getContents();
295
  if (!canUseDebugH(contents))
296
    return std::nullopt;
297
  return contents;
298
}
299

300
static ArrayRef<GloballyHashedType>
301
getHashesFromDebugH(ArrayRef<uint8_t> debugH) {
302
  assert(canUseDebugH(debugH));
303
  debugH = debugH.drop_front(sizeof(object::debug_h_header));
304
  uint32_t count = debugH.size() / sizeof(GloballyHashedType);
305
  return {reinterpret_cast<const GloballyHashedType *>(debugH.data()), count};
306
}
307

308
// Merge .debug$T for a generic object file.
309
Error TpiSource::mergeDebugT(TypeMerger *m) {
310
  assert(!ctx.config.debugGHashes &&
311
         "use remapTpiWithGHashes when ghash is enabled");
312

313
  CVTypeArray types;
314
  BinaryStreamReader reader(file->debugTypes, llvm::endianness::little);
315
  cantFail(reader.readArray(types, reader.getLength()));
316

317
  // When dealing with PCH.OBJ, some indices were already merged.
318
  unsigned nbHeadIndices = indexMapStorage.size();
319

320
  std::optional<PCHMergerInfo> pchInfo;
321
  if (auto err = mergeTypeAndIdRecords(m->idTable, m->typeTable,
322
                                       indexMapStorage, types, pchInfo))
323
    fatal("codeview::mergeTypeAndIdRecords failed: " +
324
          toString(std::move(err)));
325
  if (pchInfo) {
326
    file->pchSignature = pchInfo->PCHSignature;
327
    endPrecompIdx = pchInfo->EndPrecompIndex;
328
  }
329

330
  // In an object, there is only one mapping for both types and items.
331
  tpiMap = indexMapStorage;
332
  ipiMap = indexMapStorage;
333

334
  if (ctx.config.showSummary) {
335
    nbTypeRecords = indexMapStorage.size() - nbHeadIndices;
336
    nbTypeRecordsBytes = reader.getLength();
337
    // Count how many times we saw each type record in our input. This
338
    // calculation requires a second pass over the type records to classify each
339
    // record as a type or index. This is slow, but this code executes when
340
    // collecting statistics.
341
    m->tpiCounts.resize(m->getTypeTable().size());
342
    m->ipiCounts.resize(m->getIDTable().size());
343
    uint32_t srcIdx = nbHeadIndices;
344
    for (const CVType &ty : types) {
345
      TypeIndex dstIdx = tpiMap[srcIdx++];
346
      // Type merging may fail, so a complex source type may become the simple
347
      // NotTranslated type, which cannot be used as an array index.
348
      if (dstIdx.isSimple())
349
        continue;
350
      SmallVectorImpl<uint32_t> &counts =
351
          isIdRecord(ty.kind()) ? m->ipiCounts : m->tpiCounts;
352
      ++counts[dstIdx.toArrayIndex()];
353
    }
354
  }
355

356
  return Error::success();
357
}
358

359
// Merge types from a type server PDB.
360
Error TypeServerSource::mergeDebugT(TypeMerger *m) {
361
  assert(!ctx.config.debugGHashes &&
362
         "use remapTpiWithGHashes when ghash is enabled");
363

364
  pdb::PDBFile &pdbFile = pdbInputFile->session->getPDBFile();
365
  Expected<pdb::TpiStream &> expectedTpi = pdbFile.getPDBTpiStream();
366
  if (auto e = expectedTpi.takeError())
367
    fatal("Type server does not have TPI stream: " + toString(std::move(e)));
368
  pdb::TpiStream *maybeIpi = nullptr;
369
  if (pdbFile.hasPDBIpiStream()) {
370
    Expected<pdb::TpiStream &> expectedIpi = pdbFile.getPDBIpiStream();
371
    if (auto e = expectedIpi.takeError())
372
      fatal("Error getting type server IPI stream: " + toString(std::move(e)));
373
    maybeIpi = &*expectedIpi;
374
  }
375

376
  // Merge TPI first, because the IPI stream will reference type indices.
377
  if (auto err = mergeTypeRecords(m->typeTable, indexMapStorage,
378
                                  expectedTpi->typeArray()))
379
    fatal("codeview::mergeTypeRecords failed: " + toString(std::move(err)));
380
  tpiMap = indexMapStorage;
381

382
  // Merge IPI.
383
  if (maybeIpi) {
384
    if (auto err = mergeIdRecords(m->idTable, tpiMap, ipiSrc->indexMapStorage,
385
                                  maybeIpi->typeArray()))
386
      fatal("codeview::mergeIdRecords failed: " + toString(std::move(err)));
387
    ipiMap = ipiSrc->indexMapStorage;
388
  }
389

390
  if (ctx.config.showSummary) {
391
    nbTypeRecords = tpiMap.size() + ipiMap.size();
392
    nbTypeRecordsBytes =
393
        expectedTpi->typeArray().getUnderlyingStream().getLength() +
394
        (maybeIpi ? maybeIpi->typeArray().getUnderlyingStream().getLength()
395
                  : 0);
396

397
    // Count how many times we saw each type record in our input. If a
398
    // destination type index is present in the source to destination type index
399
    // map, that means we saw it once in the input. Add it to our histogram.
400
    m->tpiCounts.resize(m->getTypeTable().size());
401
    m->ipiCounts.resize(m->getIDTable().size());
402
    for (TypeIndex ti : tpiMap)
403
      if (!ti.isSimple())
404
        ++m->tpiCounts[ti.toArrayIndex()];
405
    for (TypeIndex ti : ipiMap)
406
      if (!ti.isSimple())
407
        ++m->ipiCounts[ti.toArrayIndex()];
408
  }
409

410
  return Error::success();
411
}
412

413
Expected<TypeServerSource *> UseTypeServerSource::getTypeServerSource() {
414
  const codeview::GUID &tsId = typeServerDependency.getGuid();
415
  StringRef tsPath = typeServerDependency.getName();
416

417
  TypeServerSource *tsSrc = nullptr;
418
  auto it = ctx.typeServerSourceMappings.find(tsId);
419
  if (it != ctx.typeServerSourceMappings.end()) {
420
    tsSrc = (TypeServerSource *)it->second;
421
  }
422
  if (tsSrc == nullptr) {
423
    // The file failed to load, lookup by name
424
    PDBInputFile *pdb = PDBInputFile::findFromRecordPath(ctx, tsPath, file);
425
    if (!pdb)
426
      return createFileError(tsPath, errorCodeToError(std::error_code(
427
                                         ENOENT, std::generic_category())));
428
    // If an error occurred during loading, throw it now
429
    if (pdb->loadErrorStr)
430
      return createFileError(
431
          tsPath, make_error<StringError>(*pdb->loadErrorStr,
432
                                          llvm::inconvertibleErrorCode()));
433

434
    tsSrc = (TypeServerSource *)pdb->debugTypesObj;
435

436
    // Just because a file with a matching name was found and it was an actual
437
    // PDB file doesn't mean it matches.  For it to match the InfoStream's GUID
438
    // must match the GUID specified in the TypeServer2 record.
439
    if (tsSrc->Guid != tsId) {
440
      return createFileError(tsPath,
441
                             make_error<pdb::PDBError>(
442
                                 pdb::pdb_error_code::signature_out_of_date));
443
    }
444
  }
445
  return tsSrc;
446
}
447

448
Error UseTypeServerSource::mergeDebugT(TypeMerger *m) {
449
  Expected<TypeServerSource *> tsSrc = getTypeServerSource();
450
  if (!tsSrc)
451
    return tsSrc.takeError();
452

453
  pdb::PDBFile &pdbSession = (*tsSrc)->pdbInputFile->session->getPDBFile();
454
  auto expectedInfo = pdbSession.getPDBInfoStream();
455
  if (!expectedInfo)
456
    return expectedInfo.takeError();
457

458
  // Reuse the type index map of the type server.
459
  tpiMap = (*tsSrc)->tpiMap;
460
  ipiMap = (*tsSrc)->ipiMap;
461
  return Error::success();
462
}
463

464
static bool equalsPath(StringRef path1, StringRef path2) {
465
#if defined(_WIN32)
466
  return path1.equals_insensitive(path2);
467
#else
468
  return path1 == path2;
469
#endif
470
}
471

472
// Find by name an OBJ provided on the command line
473
PrecompSource *UsePrecompSource::findObjByName(StringRef fileNameOnly) {
474
  SmallString<128> currentPath;
475
  for (auto kv : ctx.precompSourceMappings) {
476
    StringRef currentFileName = sys::path::filename(kv.second->file->getName(),
477
                                                    sys::path::Style::windows);
478

479
    // Compare based solely on the file name (link.exe behavior)
480
    if (equalsPath(currentFileName, fileNameOnly))
481
      return (PrecompSource *)kv.second;
482
  }
483
  return nullptr;
484
}
485

486
PrecompSource *UsePrecompSource::findPrecompSource(ObjFile *file,
487
                                                   PrecompRecord &pr) {
488
  // Cross-compile warning: given that Clang doesn't generate LF_PRECOMP
489
  // records, we assume the OBJ comes from a Windows build of cl.exe. Thusly,
490
  // the paths embedded in the OBJs are in the Windows format.
491
  SmallString<128> prFileName =
492
      sys::path::filename(pr.getPrecompFilePath(), sys::path::Style::windows);
493

494
  auto it = ctx.precompSourceMappings.find(pr.getSignature());
495
  if (it != ctx.precompSourceMappings.end()) {
496
    return (PrecompSource *)it->second;
497
  }
498
  // Lookup by name
499
  return findObjByName(prFileName);
500
}
501

502
Expected<PrecompSource *> UsePrecompSource::findPrecompMap(ObjFile *file,
503
                                                           PrecompRecord &pr) {
504
  PrecompSource *precomp = findPrecompSource(file, pr);
505

506
  if (!precomp)
507
    return createFileError(
508
        pr.getPrecompFilePath(),
509
        make_error<pdb::PDBError>(pdb::pdb_error_code::no_matching_pch));
510

511
  // Don't rely on the PCH signature to validate the concordance between the PCH
512
  // and the OBJ that uses it. However we do validate here that the
513
  // LF_ENDPRECOMP record index lines up with the number of type records
514
  // LF_PRECOMP is expecting.
515
  if (precomp->endPrecompIdx != pr.getTypesCount())
516
    return createFileError(
517
        toString(file),
518
        make_error<pdb::PDBError>(pdb::pdb_error_code::no_matching_pch));
519

520
  return precomp;
521
}
522

523
/// Merges a precompiled headers TPI map into the current TPI map. The
524
/// precompiled headers object will also be loaded and remapped in the
525
/// process.
526
Error UsePrecompSource::mergeInPrecompHeaderObj() {
527
  auto e = findPrecompMap(file, precompDependency);
528
  if (!e)
529
    return e.takeError();
530

531
  PrecompSource *precompSrc = *e;
532
  if (precompSrc->tpiMap.empty())
533
    return Error::success();
534

535
  assert(precompDependency.getStartTypeIndex() ==
536
         TypeIndex::FirstNonSimpleIndex);
537
  assert(precompDependency.getTypesCount() <= precompSrc->tpiMap.size());
538
  // Use the previously remapped index map from the precompiled headers.
539
  indexMapStorage.insert(indexMapStorage.begin(), precompSrc->tpiMap.begin(),
540
                         precompSrc->tpiMap.begin() +
541
                             precompDependency.getTypesCount());
542

543
  return Error::success();
544
}
545

546
Error UsePrecompSource::mergeDebugT(TypeMerger *m) {
547
  // This object was compiled with /Yu, so process the corresponding
548
  // precompiled headers object (/Yc) first. Some type indices in the current
549
  // object are referencing data in the precompiled headers object, so we need
550
  // both to be loaded.
551
  if (Error e = mergeInPrecompHeaderObj())
552
    return e;
553

554
  return TpiSource::mergeDebugT(m);
555
}
556

557
Error PrecompSource::mergeDebugT(TypeMerger *m) {
558
  // In some cases, the S_OBJNAME record doesn't contain the PCH signature.
559
  // The signature comes later with the LF_ENDPRECOMP record, so we first need
560
  // to merge in all the .PCH.OBJ file type records, before registering below.
561
  if (Error e = TpiSource::mergeDebugT(m))
562
    return e;
563

564
  registerMapping();
565

566
  return Error::success();
567
}
568

569
void PrecompSource::registerMapping() {
570
  if (registered)
571
    return;
572
  if (file->pchSignature && *file->pchSignature) {
573
    auto it = ctx.precompSourceMappings.emplace(*file->pchSignature, this);
574
    if (!it.second)
575
      fatal("a PCH object with the same signature has already been provided (" +
576
            toString(it.first->second->file) + " and " + toString(file) + ")");
577
    registered = true;
578
  }
579
}
580

581
//===----------------------------------------------------------------------===//
582
// Parellel GHash type merging implementation.
583
//===----------------------------------------------------------------------===//
584

585
void TpiSource::loadGHashes() {
586
  if (std::optional<ArrayRef<uint8_t>> debugH = getDebugH(file)) {
587
    ghashes = getHashesFromDebugH(*debugH);
588
    ownedGHashes = false;
589
  } else {
590
    CVTypeArray types;
591
    BinaryStreamReader reader(file->debugTypes, llvm::endianness::little);
592
    cantFail(reader.readArray(types, reader.getLength()));
593
    assignGHashesFromVector(GloballyHashedType::hashTypes(types));
594
  }
595

596
  fillIsItemIndexFromDebugT();
597
}
598

599
// Copies ghashes from a vector into an array. These are long lived, so it's
600
// worth the time to copy these into an appropriately sized vector to reduce
601
// memory usage.
602
void TpiSource::assignGHashesFromVector(
603
    std::vector<GloballyHashedType> &&hashVec) {
604
  if (hashVec.empty())
605
    return;
606
  GloballyHashedType *hashes = new GloballyHashedType[hashVec.size()];
607
  memcpy(hashes, hashVec.data(), hashVec.size() * sizeof(GloballyHashedType));
608
  ghashes = ArrayRef(hashes, hashVec.size());
609
  ownedGHashes = true;
610
}
611

612
// Faster way to iterate type records. forEachTypeChecked is faster than
613
// iterating CVTypeArray. It avoids virtual readBytes calls in inner loops.
614
static void forEachTypeChecked(ArrayRef<uint8_t> types,
615
                               function_ref<void(const CVType &)> fn) {
616
  checkError(
617
      forEachCodeViewRecord<CVType>(types, [fn](const CVType &ty) -> Error {
618
        fn(ty);
619
        return Error::success();
620
      }));
621
}
622

623
// Walk over file->debugTypes and fill in the isItemIndex bit vector.
624
// TODO: Store this information in .debug$H so that we don't have to recompute
625
// it. This is the main bottleneck slowing down parallel ghashing with one
626
// thread over single-threaded ghashing.
627
void TpiSource::fillIsItemIndexFromDebugT() {
628
  uint32_t index = 0;
629
  isItemIndex.resize(ghashes.size());
630
  forEachTypeChecked(file->debugTypes, [&](const CVType &ty) {
631
    if (isIdRecord(ty.kind()))
632
      isItemIndex.set(index);
633
    ++index;
634
  });
635
}
636

637
void TpiSource::mergeTypeRecord(TypeIndex curIndex, CVType ty) {
638
  // Decide if the merged type goes into TPI or IPI.
639
  bool isItem = isIdRecord(ty.kind());
640
  MergedInfo &merged = isItem ? mergedIpi : mergedTpi;
641

642
  // Copy the type into our mutable buffer.
643
  assert(ty.length() <= codeview::MaxRecordLength);
644
  size_t offset = merged.recs.size();
645
  size_t newSize = alignTo(ty.length(), 4);
646
  merged.recs.resize(offset + newSize);
647
  auto newRec = MutableArrayRef(&merged.recs[offset], newSize);
648
  memcpy(newRec.data(), ty.data().data(), newSize);
649

650
  // Fix up the record prefix and padding bytes if it required resizing.
651
  if (newSize != ty.length()) {
652
    reinterpret_cast<RecordPrefix *>(newRec.data())->RecordLen = newSize - 2;
653
    for (size_t i = ty.length(); i < newSize; ++i)
654
      newRec[i] = LF_PAD0 + (newSize - i);
655
  }
656

657
  // Remap the type indices in the new record.
658
  remapTypesInTypeRecord(newRec);
659
  uint32_t pdbHash = check(pdb::hashTypeRecord(CVType(newRec)));
660
  merged.recSizes.push_back(static_cast<uint16_t>(newSize));
661
  merged.recHashes.push_back(pdbHash);
662

663
  // Retain a mapping from PDB function id to PDB function type. This mapping is
664
  // used during symbol processing to rewrite S_GPROC32_ID symbols to S_GPROC32
665
  // symbols.
666
  if (ty.kind() == LF_FUNC_ID || ty.kind() == LF_MFUNC_ID) {
667
    bool success = ty.length() >= 12;
668
    TypeIndex funcId = curIndex;
669
    if (success)
670
      success &= remapTypeIndex(funcId, TiRefKind::IndexRef);
671
    TypeIndex funcType =
672
        *reinterpret_cast<const TypeIndex *>(&newRec.data()[8]);
673
    if (success) {
674
      funcIdToType.push_back({funcId, funcType});
675
    } else {
676
      StringRef fname = file ? file->getName() : "<unknown PDB>";
677
      warn("corrupt LF_[M]FUNC_ID record 0x" + utohexstr(curIndex.getIndex()) +
678
           " in " + fname);
679
    }
680
  }
681
}
682

683
void TpiSource::mergeUniqueTypeRecords(ArrayRef<uint8_t> typeRecords,
684
                                       TypeIndex beginIndex) {
685
  // Re-sort the list of unique types by index.
686
  if (kind == PDB)
687
    assert(llvm::is_sorted(uniqueTypes));
688
  else
689
    llvm::sort(uniqueTypes);
690

691
  // Accumulate all the unique types into one buffer in mergedTypes.
692
  uint32_t ghashIndex = 0;
693
  auto nextUniqueIndex = uniqueTypes.begin();
694
  assert(mergedTpi.recs.empty());
695
  assert(mergedIpi.recs.empty());
696

697
  // Pre-compute the number of elements in advance to avoid std::vector resizes.
698
  unsigned nbTpiRecs = 0;
699
  unsigned nbIpiRecs = 0;
700
  forEachTypeChecked(typeRecords, [&](const CVType &ty) {
701
    if (nextUniqueIndex != uniqueTypes.end() &&
702
        *nextUniqueIndex == ghashIndex) {
703
      assert(ty.length() <= codeview::MaxRecordLength);
704
      size_t newSize = alignTo(ty.length(), 4);
705
      (isIdRecord(ty.kind()) ? nbIpiRecs : nbTpiRecs) += newSize;
706
      ++nextUniqueIndex;
707
    }
708
    ++ghashIndex;
709
  });
710
  mergedTpi.recs.reserve(nbTpiRecs);
711
  mergedIpi.recs.reserve(nbIpiRecs);
712

713
  // Do the actual type merge.
714
  ghashIndex = 0;
715
  nextUniqueIndex = uniqueTypes.begin();
716
  forEachTypeChecked(typeRecords, [&](const CVType &ty) {
717
    if (nextUniqueIndex != uniqueTypes.end() &&
718
        *nextUniqueIndex == ghashIndex) {
719
      mergeTypeRecord(beginIndex + ghashIndex, ty);
720
      ++nextUniqueIndex;
721
    }
722
    ++ghashIndex;
723
  });
724
  assert(nextUniqueIndex == uniqueTypes.end() &&
725
         "failed to merge all desired records");
726
  assert(uniqueTypes.size() ==
727
             mergedTpi.recSizes.size() + mergedIpi.recSizes.size() &&
728
         "missing desired record");
729
}
730

731
void TpiSource::remapTpiWithGHashes(GHashState *g) {
732
  assert(ctx.config.debugGHashes && "ghashes must be enabled");
733
  fillMapFromGHashes(g);
734
  tpiMap = indexMapStorage;
735
  ipiMap = indexMapStorage;
736
  mergeUniqueTypeRecords(file->debugTypes);
737
  // TODO: Free all unneeded ghash resources now that we have a full index map.
738

739
  if (ctx.config.showSummary) {
740
    nbTypeRecords = ghashes.size();
741
    nbTypeRecordsBytes = file->debugTypes.size();
742
  }
743
}
744

745
// PDBs do not actually store global hashes, so when merging a type server
746
// PDB we have to synthesize global hashes.  To do this, we first synthesize
747
// global hashes for the TPI stream, since it is independent, then we
748
// synthesize hashes for the IPI stream, using the hashes for the TPI stream
749
// as inputs.
750
void TypeServerSource::loadGHashes() {
751
  // Don't hash twice.
752
  if (!ghashes.empty())
753
    return;
754
  pdb::PDBFile &pdbFile = pdbInputFile->session->getPDBFile();
755

756
  // Hash TPI stream.
757
  Expected<pdb::TpiStream &> expectedTpi = pdbFile.getPDBTpiStream();
758
  if (auto e = expectedTpi.takeError())
759
    fatal("Type server does not have TPI stream: " + toString(std::move(e)));
760
  assignGHashesFromVector(
761
      GloballyHashedType::hashTypes(expectedTpi->typeArray()));
762
  isItemIndex.resize(ghashes.size());
763

764
  // Hash IPI stream, which depends on TPI ghashes.
765
  if (!pdbFile.hasPDBIpiStream())
766
    return;
767
  Expected<pdb::TpiStream &> expectedIpi = pdbFile.getPDBIpiStream();
768
  if (auto e = expectedIpi.takeError())
769
    fatal("error retrieving IPI stream: " + toString(std::move(e)));
770
  ipiSrc->assignGHashesFromVector(
771
      GloballyHashedType::hashIds(expectedIpi->typeArray(), ghashes));
772

773
  // The IPI stream isItemIndex bitvector should be all ones.
774
  ipiSrc->isItemIndex.resize(ipiSrc->ghashes.size());
775
  ipiSrc->isItemIndex.set(0, ipiSrc->ghashes.size());
776
}
777

778
// Flatten discontiguous PDB type arrays to bytes so that we can use
779
// forEachTypeChecked instead of CVTypeArray iteration. Copying all types from
780
// type servers is faster than iterating all object files compiled with /Z7 with
781
// CVTypeArray, which has high overheads due to the virtual interface of
782
// BinaryStream::readBytes.
783
static ArrayRef<uint8_t> typeArrayToBytes(const CVTypeArray &types) {
784
  BinaryStreamRef stream = types.getUnderlyingStream();
785
  ArrayRef<uint8_t> debugTypes;
786
  checkError(stream.readBytes(0, stream.getLength(), debugTypes));
787
  return debugTypes;
788
}
789

790
// Merge types from a type server PDB.
791
void TypeServerSource::remapTpiWithGHashes(GHashState *g) {
792
  assert(ctx.config.debugGHashes && "ghashes must be enabled");
793

794
  // IPI merging depends on TPI, so do TPI first, then do IPI.  No need to
795
  // propagate errors, those should've been handled during ghash loading.
796
  pdb::PDBFile &pdbFile = pdbInputFile->session->getPDBFile();
797
  pdb::TpiStream &tpi = check(pdbFile.getPDBTpiStream());
798
  fillMapFromGHashes(g);
799
  tpiMap = indexMapStorage;
800
  mergeUniqueTypeRecords(typeArrayToBytes(tpi.typeArray()));
801
  if (pdbFile.hasPDBIpiStream()) {
802
    pdb::TpiStream &ipi = check(pdbFile.getPDBIpiStream());
803
    ipiSrc->indexMapStorage.resize(ipiSrc->ghashes.size());
804
    ipiSrc->fillMapFromGHashes(g);
805
    ipiMap = ipiSrc->indexMapStorage;
806
    ipiSrc->tpiMap = tpiMap;
807
    ipiSrc->ipiMap = ipiMap;
808
    ipiSrc->mergeUniqueTypeRecords(typeArrayToBytes(ipi.typeArray()));
809

810
    if (ctx.config.showSummary) {
811
      nbTypeRecords = ipiSrc->ghashes.size();
812
      nbTypeRecordsBytes = ipi.typeArray().getUnderlyingStream().getLength();
813
    }
814
  }
815

816
  if (ctx.config.showSummary) {
817
    nbTypeRecords += ghashes.size();
818
    nbTypeRecordsBytes += tpi.typeArray().getUnderlyingStream().getLength();
819
  }
820
}
821

822
void UseTypeServerSource::remapTpiWithGHashes(GHashState *g) {
823
  // No remapping to do with /Zi objects. Simply use the index map from the type
824
  // server. Errors should have been reported earlier. Symbols from this object
825
  // will be ignored.
826
  Expected<TypeServerSource *> maybeTsSrc = getTypeServerSource();
827
  if (!maybeTsSrc) {
828
    typeMergingError =
829
        joinErrors(std::move(typeMergingError), maybeTsSrc.takeError());
830
    return;
831
  }
832
  TypeServerSource *tsSrc = *maybeTsSrc;
833
  tpiMap = tsSrc->tpiMap;
834
  ipiMap = tsSrc->ipiMap;
835
}
836

837
void PrecompSource::loadGHashes() {
838
  if (getDebugH(file)) {
839
    warn("ignoring .debug$H section; pch with ghash is not implemented");
840
  }
841

842
  uint32_t ghashIdx = 0;
843
  std::vector<GloballyHashedType> hashVec;
844
  forEachTypeChecked(file->debugTypes, [&](const CVType &ty) {
845
    // Remember the index of the LF_ENDPRECOMP record so it can be excluded from
846
    // the PDB. There must be an entry in the list of ghashes so that the type
847
    // indexes of the following records in the /Yc PCH object line up.
848
    if (ty.kind() == LF_ENDPRECOMP) {
849
      EndPrecompRecord endPrecomp;
850
      cantFail(TypeDeserializer::deserializeAs<EndPrecompRecord>(
851
          const_cast<CVType &>(ty), endPrecomp));
852
      file->pchSignature = endPrecomp.getSignature();
853
      registerMapping();
854
      endPrecompIdx = ghashIdx;
855
    }
856

857
    hashVec.push_back(GloballyHashedType::hashType(ty, hashVec, hashVec));
858
    isItemIndex.push_back(isIdRecord(ty.kind()));
859
    ++ghashIdx;
860
  });
861
  assignGHashesFromVector(std::move(hashVec));
862
}
863

864
void UsePrecompSource::loadGHashes() {
865
  auto e = findPrecompMap(file, precompDependency);
866
  if (!e) {
867
    warn(toString(e.takeError()));
868
    return;
869
  }
870

871
  PrecompSource *pchSrc = *e;
872

873
  // To compute ghashes of a /Yu object file, we need to build on the ghashes of
874
  // the /Yc PCH object. After we are done hashing, discard the ghashes from the
875
  // PCH source so we don't unnecessarily try to deduplicate them.
876
  std::vector<GloballyHashedType> hashVec =
877
      pchSrc->ghashes.take_front(precompDependency.getTypesCount());
878
  forEachTypeChecked(file->debugTypes, [&](const CVType &ty) {
879
    hashVec.push_back(GloballyHashedType::hashType(ty, hashVec, hashVec));
880
    isItemIndex.push_back(isIdRecord(ty.kind()));
881
  });
882
  hashVec.erase(hashVec.begin(),
883
                hashVec.begin() + precompDependency.getTypesCount());
884
  assignGHashesFromVector(std::move(hashVec));
885
}
886

887
void UsePrecompSource::remapTpiWithGHashes(GHashState *g) {
888
  fillMapFromGHashes(g);
889
  // This object was compiled with /Yu, so process the corresponding
890
  // precompiled headers object (/Yc) first. Some type indices in the current
891
  // object are referencing data in the precompiled headers object, so we need
892
  // both to be loaded.
893
  if (Error e = mergeInPrecompHeaderObj()) {
894
    typeMergingError = joinErrors(std::move(typeMergingError), std::move(e));
895
    return;
896
  }
897

898
  tpiMap = indexMapStorage;
899
  ipiMap = indexMapStorage;
900
  mergeUniqueTypeRecords(file->debugTypes,
901
                         TypeIndex(precompDependency.getStartTypeIndex() +
902
                                   precompDependency.getTypesCount()));
903
  if (ctx.config.showSummary) {
904
    nbTypeRecords = ghashes.size();
905
    nbTypeRecordsBytes = file->debugTypes.size();
906
  }
907
}
908

909
namespace {
910
/// A concurrent hash table for global type hashing. It is based on this paper:
911
/// Concurrent Hash Tables: Fast and General(?)!
912
/// https://dl.acm.org/doi/10.1145/3309206
913
///
914
/// This hash table is meant to be used in two phases:
915
/// 1. concurrent insertions
916
/// 2. concurrent reads
917
/// It does not support lookup, deletion, or rehashing. It uses linear probing.
918
///
919
/// The paper describes storing a key-value pair in two machine words.
920
/// Generally, the values stored in this map are type indices, and we can use
921
/// those values to recover the ghash key from a side table. This allows us to
922
/// shrink the table entries further at the cost of some loads, and sidesteps
923
/// the need for a 128 bit atomic compare-and-swap operation.
924
///
925
/// During insertion, a priority function is used to decide which insertion
926
/// should be preferred. This ensures that the output is deterministic. For
927
/// ghashing, lower tpiSrcIdx values (earlier inputs) are preferred.
928
///
929
class GHashCell;
930
struct GHashTable {
931
  GHashCell *table = nullptr;
932
  uint32_t tableSize = 0;
933

934
  GHashTable() = default;
935
  ~GHashTable();
936

937
  /// Initialize the table with the given size. Because the table cannot be
938
  /// resized, the initial size of the table must be large enough to contain all
939
  /// inputs, or insertion may not be able to find an empty cell.
940
  void init(uint32_t newTableSize);
941

942
  /// Insert the cell with the given ghash into the table. Return the insertion
943
  /// position in the table. It is safe for the caller to store the insertion
944
  /// position because the table cannot be resized.
945
  uint32_t insert(COFFLinkerContext &ctx, GloballyHashedType ghash,
946
                  GHashCell newCell);
947
};
948

949
/// A ghash table cell for deduplicating types from TpiSources.
950
class GHashCell {
951
  // Force "data" to be 64-bit aligned; otherwise, some versions of clang
952
  // will generate calls to libatomic when using some versions of libstdc++
953
  // on 32-bit targets.  (Also, in theory, there could be a target where
954
  // new[] doesn't always return an 8-byte-aligned allocation.)
955
  alignas(sizeof(uint64_t)) uint64_t data = 0;
956

957
public:
958
  GHashCell() = default;
959

960
  // Construct data most to least significant so that sorting works well:
961
  // - isItem
962
  // - tpiSrcIdx
963
  // - ghashIdx
964
  // Add one to the tpiSrcIdx so that the 0th record from the 0th source has a
965
  // non-zero representation.
966
  GHashCell(bool isItem, uint32_t tpiSrcIdx, uint32_t ghashIdx)
967
      : data((uint64_t(isItem) << 63U) | (uint64_t(tpiSrcIdx + 1) << 32ULL) |
968
             ghashIdx) {
969
    assert(tpiSrcIdx == getTpiSrcIdx() && "round trip failure");
970
    assert(ghashIdx == getGHashIdx() && "round trip failure");
971
  }
972

973
  explicit GHashCell(uint64_t data) : data(data) {}
974

975
  // The empty cell is all zeros.
976
  bool isEmpty() const { return data == 0ULL; }
977

978
  /// Extract the tpiSrcIdx.
979
  uint32_t getTpiSrcIdx() const {
980
    return ((uint32_t)(data >> 32U) & 0x7FFFFFFF) - 1;
981
  }
982

983
  /// Extract the index into the ghash array of the TpiSource.
984
  uint32_t getGHashIdx() const { return (uint32_t)data; }
985

986
  bool isItem() const { return data & (1ULL << 63U); }
987

988
  /// Get the ghash key for this cell.
989
  GloballyHashedType getGHash(const COFFLinkerContext &ctx) const {
990
    return ctx.tpiSourceList[getTpiSrcIdx()]->ghashes[getGHashIdx()];
991
  }
992

993
  /// The priority function for the cell. The data is stored such that lower
994
  /// tpiSrcIdx and ghashIdx values are preferred, which means that type record
995
  /// from earlier sources are more likely to prevail.
996
  friend inline bool operator<(const GHashCell &l, const GHashCell &r) {
997
    return l.data < r.data;
998
  }
999
};
1000
} // namespace
1001

1002
namespace lld::coff {
1003
/// This type is just a wrapper around GHashTable with external linkage so it
1004
/// can be used from a header.
1005
struct GHashState {
1006
  GHashTable table;
1007
};
1008
} // namespace lld::coff
1009

1010
GHashTable::~GHashTable() { delete[] table; }
1011

1012
void GHashTable::init(uint32_t newTableSize) {
1013
  table = new GHashCell[newTableSize];
1014
  memset(table, 0, newTableSize * sizeof(GHashCell));
1015
  tableSize = newTableSize;
1016
}
1017

1018
uint32_t GHashTable::insert(COFFLinkerContext &ctx, GloballyHashedType ghash,
1019
                            GHashCell newCell) {
1020
  assert(!newCell.isEmpty() && "cannot insert empty cell value");
1021

1022
  // FIXME: The low bytes of SHA1 have low entropy for short records, which
1023
  // type records are. Swap the byte order for better entropy. A better ghash
1024
  // won't need this.
1025
  uint32_t startIdx =
1026
      llvm::byteswap<uint64_t>(*reinterpret_cast<uint64_t *>(&ghash)) %
1027
      tableSize;
1028

1029
  // Do a linear probe starting at startIdx.
1030
  uint32_t idx = startIdx;
1031
  while (true) {
1032
    // Run a compare and swap loop. There are four cases:
1033
    // - cell is empty: CAS into place and return
1034
    // - cell has matching key, earlier priority: do nothing, return
1035
    // - cell has matching key, later priority: CAS into place and return
1036
    // - cell has non-matching key: hash collision, probe next cell
1037
    auto *cellPtr = reinterpret_cast<std::atomic<GHashCell> *>(&table[idx]);
1038
    GHashCell oldCell(cellPtr->load());
1039
    while (oldCell.isEmpty() || oldCell.getGHash(ctx) == ghash) {
1040
      // Check if there is an existing ghash entry with a higher priority
1041
      // (earlier ordering). If so, this is a duplicate, we are done.
1042
      if (!oldCell.isEmpty() && oldCell < newCell)
1043
        return idx;
1044
      // Either the cell is empty, or our value is higher priority. Try to
1045
      // compare and swap. If it succeeds, we are done.
1046
      if (cellPtr->compare_exchange_weak(oldCell, newCell))
1047
        return idx;
1048
      // If the CAS failed, check this cell again.
1049
    }
1050

1051
    // Advance the probe. Wrap around to the beginning if we run off the end.
1052
    ++idx;
1053
    idx = idx == tableSize ? 0 : idx;
1054
    if (idx == startIdx) {
1055
      // If this becomes an issue, we could mark failure and rehash from the
1056
      // beginning with a bigger table. There is no difference between rehashing
1057
      // internally and starting over.
1058
      report_fatal_error("ghash table is full");
1059
    }
1060
  }
1061
  llvm_unreachable("left infloop");
1062
}
1063

1064
TypeMerger::TypeMerger(COFFLinkerContext &c, llvm::BumpPtrAllocator &alloc)
1065
    : typeTable(alloc), idTable(alloc), ctx(c) {}
1066

1067
TypeMerger::~TypeMerger() = default;
1068

1069
void TypeMerger::mergeTypesWithGHash() {
1070
  // Load ghashes. Do type servers and PCH objects first.
1071
  {
1072
    llvm::TimeTraceScope timeScope("Load GHASHes");
1073
    ScopedTimer t1(ctx.loadGHashTimer);
1074
    parallelForEach(dependencySources,
1075
                    [&](TpiSource *source) { source->loadGHashes(); });
1076
    parallelForEach(objectSources,
1077
                    [&](TpiSource *source) { source->loadGHashes(); });
1078
  }
1079

1080
  llvm::TimeTraceScope timeScope("Merge types (GHASH)");
1081
  ScopedTimer t2(ctx.mergeGHashTimer);
1082
  GHashState ghashState;
1083

1084
  // Estimate the size of hash table needed to deduplicate ghashes. This *must*
1085
  // be larger than the number of unique types, or hash table insertion may not
1086
  // be able to find a vacant slot. Summing the input types guarantees this, but
1087
  // it is a gross overestimate. The table size could be reduced to save memory,
1088
  // but it would require implementing rehashing, and this table is generally
1089
  // small compared to total memory usage, at eight bytes per input type record,
1090
  // and most input type records are larger than eight bytes.
1091
  size_t tableSize = 0;
1092
  for (TpiSource *source : ctx.tpiSourceList)
1093
    tableSize += source->ghashes.size();
1094

1095
  // Cap the table size so that we can use 32-bit cell indices. Type indices are
1096
  // also 32-bit, so this is an inherent PDB file format limit anyway.
1097
  tableSize =
1098
      std::min(size_t(INT32_MAX) - TypeIndex::FirstNonSimpleIndex, tableSize);
1099
  ghashState.table.init(static_cast<uint32_t>(tableSize));
1100

1101
  // Insert ghashes in parallel. During concurrent insertion, we cannot observe
1102
  // the contents of the hash table cell, but we can remember the insertion
1103
  // position. Because the table does not rehash, the position will not change
1104
  // under insertion. After insertion is done, the value of the cell can be read
1105
  // to retrieve the final PDB type index.
1106
  parallelFor(0, ctx.tpiSourceList.size(), [&](size_t tpiSrcIdx) {
1107
    TpiSource *source = ctx.tpiSourceList[tpiSrcIdx];
1108
    source->indexMapStorage.resize(source->ghashes.size());
1109
    for (uint32_t i = 0, e = source->ghashes.size(); i < e; i++) {
1110
      if (source->shouldOmitFromPdb(i)) {
1111
        source->indexMapStorage[i] = TypeIndex(SimpleTypeKind::NotTranslated);
1112
        continue;
1113
      }
1114
      GloballyHashedType ghash = source->ghashes[i];
1115
      bool isItem = source->isItemIndex.test(i);
1116
      uint32_t cellIdx =
1117
          ghashState.table.insert(ctx, ghash, GHashCell(isItem, tpiSrcIdx, i));
1118

1119
      // Store the ghash cell index as a type index in indexMapStorage. Later
1120
      // we will replace it with the PDB type index.
1121
      source->indexMapStorage[i] = TypeIndex::fromArrayIndex(cellIdx);
1122
    }
1123
  });
1124

1125
  // Collect all non-empty cells and sort them. This will implicitly assign
1126
  // destination type indices, and partition the entries into type records and
1127
  // item records. It arranges types in this order:
1128
  // - type records
1129
  //   - source 0, type 0...
1130
  //   - source 1, type 1...
1131
  // - item records
1132
  //   - source 0, type 1...
1133
  //   - source 1, type 0...
1134
  std::vector<GHashCell> entries;
1135
  for (const GHashCell &cell : ArrayRef(ghashState.table.table, tableSize)) {
1136
    if (!cell.isEmpty())
1137
      entries.push_back(cell);
1138
  }
1139
  parallelSort(entries, std::less<GHashCell>());
1140
  log(formatv("ghash table load factor: {0:p} (size {1} / capacity {2})\n",
1141
              tableSize ? double(entries.size()) / tableSize : 0,
1142
              entries.size(), tableSize));
1143

1144
  // Find out how many type and item indices there are.
1145
  auto mid = llvm::lower_bound(entries, GHashCell(true, 0, 0));
1146
  assert((mid == entries.end() || mid->isItem()) &&
1147
         (mid == entries.begin() || !std::prev(mid)->isItem()) &&
1148
         "midpoint is not midpoint");
1149
  uint32_t numTypes = std::distance(entries.begin(), mid);
1150
  uint32_t numItems = std::distance(mid, entries.end());
1151
  log("Tpi record count: " + Twine(numTypes));
1152
  log("Ipi record count: " + Twine(numItems));
1153

1154
  // Make a list of the "unique" type records to merge for each tpi source. Type
1155
  // merging will skip indices not on this list. Store the destination PDB type
1156
  // index for these unique types in the tpiMap for each source. The entries for
1157
  // non-unique types will be filled in prior to type merging.
1158
  for (uint32_t i = 0, e = entries.size(); i < e; ++i) {
1159
    auto &cell = entries[i];
1160
    uint32_t tpiSrcIdx = cell.getTpiSrcIdx();
1161
    TpiSource *source = ctx.tpiSourceList[tpiSrcIdx];
1162
    source->uniqueTypes.push_back(cell.getGHashIdx());
1163

1164
    // Update the ghash table to store the destination PDB type index in the
1165
    // table.
1166
    uint32_t pdbTypeIndex = i < numTypes ? i : i - numTypes;
1167
    uint32_t ghashCellIndex =
1168
        source->indexMapStorage[cell.getGHashIdx()].toArrayIndex();
1169
    ghashState.table.table[ghashCellIndex] =
1170
        GHashCell(cell.isItem(), cell.getTpiSrcIdx(), pdbTypeIndex);
1171
  }
1172

1173
  // In parallel, remap all types.
1174
  for (TpiSource *source : dependencySources)
1175
    source->remapTpiWithGHashes(&ghashState);
1176
  parallelForEach(objectSources, [&](TpiSource *source) {
1177
    source->remapTpiWithGHashes(&ghashState);
1178
  });
1179

1180
  // Build a global map of from function ID to function type.
1181
  for (TpiSource *source : ctx.tpiSourceList) {
1182
    for (auto idToType : source->funcIdToType)
1183
      funcIdToType.insert(idToType);
1184
    source->funcIdToType.clear();
1185
  }
1186

1187
  clearGHashes();
1188
}
1189

1190
void TypeMerger::sortDependencies() {
1191
  // Order dependencies first, but preserve the existing order.
1192
  std::vector<TpiSource *> deps;
1193
  std::vector<TpiSource *> objs;
1194
  for (TpiSource *s : ctx.tpiSourceList)
1195
    (s->isDependency() ? deps : objs).push_back(s);
1196
  uint32_t numDeps = deps.size();
1197
  uint32_t numObjs = objs.size();
1198
  ctx.tpiSourceList = std::move(deps);
1199
  ctx.tpiSourceList.insert(ctx.tpiSourceList.end(), objs.begin(), objs.end());
1200
  for (uint32_t i = 0, e = ctx.tpiSourceList.size(); i < e; ++i)
1201
    ctx.tpiSourceList[i]->tpiSrcIdx = i;
1202
  dependencySources = ArrayRef(ctx.tpiSourceList.data(), numDeps);
1203
  objectSources = ArrayRef(ctx.tpiSourceList.data() + numDeps, numObjs);
1204
}
1205

1206
/// Given the index into the ghash table for a particular type, return the type
1207
/// index for that type in the output PDB.
1208
static TypeIndex loadPdbTypeIndexFromCell(GHashState *g,
1209
                                          uint32_t ghashCellIdx) {
1210
  GHashCell cell = g->table.table[ghashCellIdx];
1211
  return TypeIndex::fromArrayIndex(cell.getGHashIdx());
1212
}
1213

1214
/// Free heap allocated ghashes.
1215
void TypeMerger::clearGHashes() {
1216
  for (TpiSource *src : ctx.tpiSourceList) {
1217
    if (src->ownedGHashes)
1218
      delete[] src->ghashes.data();
1219
    src->ghashes = {};
1220
    src->isItemIndex.clear();
1221
    src->uniqueTypes.clear();
1222
  }
1223
}
1224

1225
// Fill in a TPI or IPI index map using ghashes. For each source type, use its
1226
// ghash to lookup its final type index in the PDB, and store that in the map.
1227
void TpiSource::fillMapFromGHashes(GHashState *g) {
1228
  for (size_t i = 0, e = ghashes.size(); i < e; ++i) {
1229
    TypeIndex fakeCellIndex = indexMapStorage[i];
1230
    if (fakeCellIndex.isSimple())
1231
      indexMapStorage[i] = fakeCellIndex;
1232
    else
1233
      indexMapStorage[i] =
1234
          loadPdbTypeIndexFromCell(g, fakeCellIndex.toArrayIndex());
1235
  }
1236
}
1237