OnDiskTrieRawHashMap.cpp Source File (original) (raw)

18#include "llvm/Config/llvm-config.h"

23using namespace llvm;

27#if LLVM_ENABLE_ONDISK_CAS

33namespace {

35class SubtrieHandle;

36class TrieRawHashMapHandle;

37class TrieVisitor;

42class SubtrieSlotValue {

43public:

44 explicit operator bool() const { return !isEmpty(); }

45 bool isEmpty() const { return Offset ; }

46 bool isData() const { return Offset > 0; }

47 bool isSubtrie() const { return Offset < 0; }

48 uint64_t asData() const {

51 }

52 uint64_t asSubtrie() const {

55 }

57 FileOffset asSubtrieFileOffset() const { return FileOffset(asSubtrie()); }

59 FileOffset asDataFileOffset() const { return FileOffset(asData()); }

61 int64_t getRawOffset() const { return Offset; }

63 static SubtrieSlotValue getDataOffset(int64_t Offset) {

64 return SubtrieSlotValue(Offset);

65 }

67 static SubtrieSlotValue getSubtrieOffset(int64_t Offset) {

68 return SubtrieSlotValue(-Offset);

69 }

71 static SubtrieSlotValue getDataOffset(FileOffset Offset) {

72 return getDataOffset(Offset.get());

73 }

75 static SubtrieSlotValue getSubtrieOffset(FileOffset Offset) {

76 return getDataOffset(Offset.get());

77 }

79 static SubtrieSlotValue getFromSlot(std::atomic<int64_t> &Slot) {

80 return SubtrieSlotValue(Slot.load());

81 }

83 SubtrieSlotValue() = default;

85private:

86 friend class SubtrieHandle;

89};

96class SubtrieHandle {

97public:

98 struct Header {

100 uint16_t StartBit;

101

102

103 uint8_t NumBits;

104

105

106 uint8_t ZeroPad1B;

107 uint32_t ZeroPad4B;

108 };

109

110

111

112

113

114 using SlotT = std::atomic<int64_t>;

115

116 static int64_t getSlotsSize(uint32_t NumBits) {

117 return sizeof(int64_t) * (1ull << NumBits);

118 }

119

120 static int64_t getSize(uint32_t NumBits) {

121 return sizeof(SubtrieHandle::Header) + getSlotsSize(NumBits);

122 }

123

125 size_t getNumSlots() const { return Slots.size(); }

126

127 SubtrieSlotValue load(size_t I) const {

128 return SubtrieSlotValue(Slots[I].load());

129 }

130 void store(size_t I, SubtrieSlotValue V) {

131 return Slots[I].store(V.getRawOffset());

132 }

133

134 void printHash(raw_ostream &OS, ArrayRef<uint8_t> Bytes) const;

135

136

137 bool compare_exchange_strong(size_t I, SubtrieSlotValue &Expected,

138 SubtrieSlotValue New) {

139 return Slots[I].compare_exchange_strong(Expected.Offset, New.Offset);

140 }

141

142

143

144

145

146

147

148

149

150

151

152 Expected sink(size_t I, SubtrieSlotValue V,

153 MappedFileRegionArena &Alloc,

154 size_t NumSubtrieBits,

155 SubtrieHandle &UnusedSubtrie, size_t NewI);

156

157

158 void reinitialize(uint32_t StartBit, uint32_t NumBits);

159

160 SubtrieSlotValue getOffset() const {

161 return SubtrieSlotValue::getSubtrieOffset(

162 reinterpret_cast<const char *>(H) - Region->data());

163 }

164

165 FileOffset getFileOffset() const { return getOffset().asSubtrieFileOffset(); }

166

167 explicit operator bool() const { return H; }

168

169 Header &getHeader() const { return *H; }

170 uint32_t getStartBit() const { return H->StartBit; }

171 uint32_t getNumBits() const { return H->NumBits; }

172

173 static Expected create(MappedFileRegionArena &Alloc,

174 uint32_t StartBit, uint32_t NumBits);

175

176 static SubtrieHandle getFromFileOffset(MappedFileRegion &Region,

178 return SubtrieHandle(Region, SubtrieSlotValue::getSubtrieOffset(Offset));

179 }

180

181 SubtrieHandle() = default;

185 : SubtrieHandle(Region, *reinterpret_cast<Header *>(

187

188private:

190 Header *H = nullptr;

192

195 1ull << H.NumBits);

196 }

197};

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214class TrieRawHashMapHandle {

215public:

217 TableHandle::TableKind::TrieRawHashMap;

218

219 struct Header {

220 TableHandle::Header GenericHeader;

221 uint8_t NumSubtrieBits;

222 uint8_t Flags;

223 uint16_t NumHashBits;

224 uint32_t RecordDataSize;

225 std::atomic<int64_t> RootTrieOffset;

226 std::atomic<int64_t> AllocatorOffset;

227 };

228

229 operator TableHandle() const {

230 if ()

231 return TableHandle();

232 return TableHandle(*Region, H->GenericHeader);

233 }

234

235 struct RecordData {

236 OnDiskTrieRawHashMap::ValueProxy Proxy;

237 SubtrieSlotValue Offset;

238 FileOffset getFileOffset() const { return Offset.asDataFileOffset(); }

239 };

240

241 enum Limits : size_t {

242

243 MaxNumHashBytes = UINT16_MAX >> 3,

244 MaxNumHashBits = MaxNumHashBytes << 3,

245

246

247

248 MaxNumRootBits = 16,

249

250

251

252 MaxNumSubtrieBits = 10,

253 };

254

255 static constexpr size_t getNumHashBytes(size_t NumHashBits) {

256 assert(NumHashBits % 8 == 0);

257 return NumHashBits / 8;

258 }

259 static constexpr size_t getRecordSize(size_t RecordDataSize,

260 size_t NumHashBits) {

261 return RecordDataSize + getNumHashBytes(NumHashBits);

262 }

263

264 RecordData getRecord(SubtrieSlotValue Offset);

266 ArrayRef<uint8_t> Hash);

267

268 explicit operator bool() const { return H; }

269 const Header &getHeader() const { return *H; }

270 SubtrieHandle getRoot() const;

271 Expected getOrCreateRoot(MappedFileRegionArena &Alloc);

273

274 size_t getFlags() const { return H->Flags; }

275 size_t getNumSubtrieBits() const { return H->NumSubtrieBits; }

276 size_t getNumHashBits() const { return H->NumHashBits; }

277 size_t getNumHashBytes() const { return getNumHashBytes(H->NumHashBits); }

278 size_t getRecordDataSize() const { return H->RecordDataSize; }

279 size_t getRecordSize() const {

280 return getRecordSize(H->RecordDataSize, H->NumHashBits);

281 }

282

283 TrieHashIndexGenerator getIndexGen(SubtrieHandle Root,

284 ArrayRef<uint8_t> Hash) {

285 assert(Root.getStartBit() == 0);

286 assert(getNumHashBytes() == Hash.size());

287 assert(getNumHashBits() == Hash.size() * 8);

288 return TrieHashIndexGenerator{Root.getNumBits(), getNumSubtrieBits(), Hash};

289 }

290

291 static Expected

292 create(MappedFileRegionArena &Alloc, StringRef Name,

293 std::optional<uint64_t> NumRootBits, uint64_t NumSubtrieBits,

294 uint64_t NumHashBits, uint64_t RecordDataSize);

295

296 void

297 print(raw_ostream &OS,

298 function_ref<void(ArrayRef)> PrintRecordData = nullptr) const;

299

301 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>

302 RecordVerifier) const;

303 TrieRawHashMapHandle() = default;

306 TrieRawHashMapHandle(MappedFileRegion &Region, intptr_t HeaderOffset)

307 : TrieRawHashMapHandle(

308 Region, *reinterpret_cast<Header *>(Region.data() + HeaderOffset)) {

309 }

310

311private:

313 Header *H = nullptr;

314};

315

316}

317

319 DatabaseFile File;

320 TrieRawHashMapHandle Trie;

321};

322

326 assert(StartBit <= TrieRawHashMapHandle::MaxNumHashBits);

327 assert(NumBits <= UINT8_MAX);

328 assert(NumBits <= TrieRawHashMapHandle::MaxNumRootBits);

329

332 return Mem.takeError();

333 auto *H =

334 new (*Mem) SubtrieHandle::Header{(uint16_t)StartBit, (uint8_t)NumBits,

335 0, 0};

336 SubtrieHandle S(Alloc.getRegion(), *H);

337 for (auto I = S.Slots.begin(), E = S.Slots.end(); I != E; ++I)

338 new (I) SlotT(0);

339 return S;

340}

341

342SubtrieHandle TrieRawHashMapHandle::getRoot() const {

343 if (int64_t Root = H->RootTrieOffset)

344 return SubtrieHandle(getRegion(), SubtrieSlotValue::getSubtrieOffset(Root));

345 return SubtrieHandle();

346}

347

350 assert(&Alloc.getRegion() == &getRegion());

351 if (SubtrieHandle Root = getRoot())

352 return Root;

353

354 int64_t Race = 0;

355 auto LazyRoot = SubtrieHandle::create(Alloc, 0, H->NumSubtrieBits);

357 return LazyRoot.takeError();

358 if (H->RootTrieOffset.compare_exchange_strong(

359 Race, LazyRoot->getOffset().asSubtrie()))

360 return *LazyRoot;

361

362

363

364

365 return SubtrieHandle(getRegion(), SubtrieSlotValue::getSubtrieOffset(Race));

366}

367

370 std::optional<uint64_t> NumRootBits,

373

374 auto Offset = Alloc.allocateOffset(sizeof(Header) + Name.size() + 1);

376 return Offset.takeError();

377

378

379 assert(Name.size() <= UINT16_MAX && "Expected smaller table name");

380 assert(NumSubtrieBits <= UINT8_MAX && "Expected valid subtrie bits");

381 assert(NumHashBits <= UINT16_MAX && "Expected valid hash size");

382 assert(RecordDataSize <= UINT32_MAX && "Expected smaller table name");

387 0,

390 {0},

391 {0}};

392 char *NameStorage = reinterpret_cast<char *>(H + 1);

394 NameStorage[Name.size()] = 0;

395

396

397 TrieRawHashMapHandle Trie(Alloc.getRegion(), *H);

398 auto Sub = SubtrieHandle::create(Alloc, 0, *NumRootBits);

400 return Sub.takeError();

401 if (NumRootBits)

402 H->RootTrieOffset = Sub->getOffset().asSubtrie();

403 return Trie;

404}

405

406TrieRawHashMapHandle::RecordData

407TrieRawHashMapHandle::getRecord(SubtrieSlotValue Offset) {

408 char *Begin = Region->data() + Offset.asData();

412 getNumHashBytes());

413 return RecordData{Proxy, Offset};

414}

415

420 assert(Hash.size() == getNumHashBytes());

421 auto Offset = Alloc.allocateOffset(getRecordSize());

423 return Offset.takeError();

424

425 RecordData Record = getRecord(SubtrieSlotValue::getDataOffset(*Offset));

428}

429

432

435 "unaligned file offset at 0x" +

437

438

439

440

441

443 Offset.get() + Impl->Trie.getRecordSize() > Impl->File.getAlloc().size())

445 "file offset too large: 0x" +

447

448

449 TrieRawHashMapHandle::RecordData D =

450 Impl->Trie.getRecord(SubtrieSlotValue::getDataOffset(Offset));

452}

453

456 TrieRawHashMapHandle Trie = Impl->Trie;

457 assert(Hash.size() == Trie.getNumHashBytes() && "Invalid hash");

458

459 SubtrieHandle S = Trie.getRoot();

460 if (!S)

462

463 TrieHashIndexGenerator IndexGen = Trie.getIndexGen(S, Hash);

465 for (;;) {

466

467 SubtrieSlotValue V = S.load(Index);

468 if (!V)

470

471

472 if (V.isData()) {

473 TrieRawHashMapHandle::RecordData D = Trie.getRecord(V);

474 return D.Proxy.Hash == Hash ? ConstOnDiskPtr(D.Proxy, D.getFileOffset())

476 }

477

479 S = SubtrieHandle(Trie.getRegion(), V);

480 }

481}

482

483

484void SubtrieHandle::reinitialize(uint32_t StartBit, uint32_t NumBits) {

485 assert(StartBit > H->StartBit);

486 assert(NumBits <= H->NumBits);

487

488

489 H->StartBit = StartBit;

490 H->NumBits = NumBits;

491}

492

493ExpectedOnDiskTrieRawHashMap::OnDiskPtr

495 LazyInsertOnConstructCB OnConstruct,

496 LazyInsertOnLeakCB OnLeak) {

497 TrieRawHashMapHandle Trie = Impl->Trie;

498 assert(Hash.size() == Trie.getNumHashBytes() && "Invalid hash");

499

500 MappedFileRegionArena &Alloc = Impl->File.getAlloc();

501 std::optional S;

502 auto Err = Trie.getOrCreateRoot(Alloc).moveInto(S);

504 return std::move(Err);

505

506 TrieHashIndexGenerator IndexGen = Trie.getIndexGen(*S, Hash);

508

509

510 std::optionalTrieRawHashMapHandle::RecordData NewRecord;

511 SubtrieHandle UnusedSubtrie;

512 for (;;) {

513 SubtrieSlotValue Existing = S->load(Index);

514

515

516 if (!Existing) {

517 if (!NewRecord) {

518 auto Err = Trie.createRecord(Alloc, Hash).moveInto(NewRecord);

520 return std::move(Err);

521 if (OnConstruct)

522 OnConstruct(NewRecord->Offset.asDataFileOffset(), NewRecord->Proxy);

523 }

524

525 if (S->compare_exchange_strong(Index, Existing, NewRecord->Offset))

526 return OnDiskPtr(NewRecord->Proxy,

527 NewRecord->Offset.asDataFileOffset());

528

529

530 }

531

532 if (Existing.isSubtrie()) {

533 S = SubtrieHandle(Trie.getRegion(), Existing);

535 continue;

536 }

537

538

539 TrieRawHashMapHandle::RecordData ExistingRecord = Trie.getRecord(Existing);

540 if (ExistingRecord.Proxy.Hash == Hash) {

541 if (NewRecord && OnLeak)

542 OnLeak(NewRecord->Offset.asDataFileOffset(), NewRecord->Proxy,

543 ExistingRecord.Offset.asDataFileOffset(), ExistingRecord.Proxy);

544 return OnDiskPtr(ExistingRecord.Proxy,

545 ExistingRecord.Offset.asDataFileOffset());

546 }

547

548

549 for (;;) {

550 size_t NextIndex = IndexGen.next();

551 size_t NewIndexForExistingContent =

553

554 auto Err = S->sink(Index, Existing, Alloc, IndexGen.getNumBits(),

555 UnusedSubtrie, NewIndexForExistingContent)

556 .moveInto(S);

558 return std::move(Err);

559 Index = NextIndex;

560

561

562 if (NextIndex != NewIndexForExistingContent)

563 break;

564 }

565 }

566}

567

568Expected SubtrieHandle::sink(size_t I, SubtrieSlotValue V,

570 size_t NumSubtrieBits,

571 SubtrieHandle &UnusedSubtrie,

572 size_t NewI) {

573 std::optional NewS;

574 if (UnusedSubtrie) {

575

576 NewS.emplace();

578 NewS->reinitialize(getStartBit() + getNumBits(), NumSubtrieBits);

579 } else {

580

581 auto Err = SubtrieHandle::create(Alloc, getStartBit() + getNumBits(),

582 NumSubtrieBits)

583 .moveInto(NewS);

585 return std::move(Err);

586 }

587

588 NewS->store(NewI, V);

589 if (compare_exchange_strong(I, V, NewS->getOffset()))

590 return *NewS;

591

592

593 assert(V.isSubtrie() && "Expected racing sink() to add a subtrie");

594

595

596 NewS->store(NewI, SubtrieSlotValue());

597 UnusedSubtrie = *NewS;

598

599

600 return SubtrieHandle(Alloc.getRegion(), V);

601}

602

604 raw_ostream &OS, function_ref<void(ArrayRef)> PrintRecordData) const {

605 Impl->Trie.print(OS, PrintRecordData);

606}

607

609 function_ref<Error(FileOffset, ConstValueProxy)> RecordVerifier) const {

610 return Impl->Trie.validate(RecordVerifier);

611}

612

613

614static void printHexDigits(raw_ostream &OS, ArrayRef<uint8_t> Bytes,

615 size_t StartBit, size_t NumBits) {

616 assert(StartBit % 4 == 0);

617 assert(NumBits % 4 == 0);

618 for (size_t I = StartBit, E = StartBit + NumBits; I != E; I += 4) {

619 uint8_t HexPair = Bytes[I / 8];

620 uint8_t HexDigit = I % 8 == 0 ? HexPair >> 4 : HexPair & 0xf;

621 OS << hexdigit(HexDigit, true);

622 }

623}

624

625static void printBits(raw_ostream &OS, ArrayRef<uint8_t> Bytes, size_t StartBit,

626 size_t NumBits) {

627 assert(StartBit + NumBits <= Bytes.size() * 8u);

628 for (size_t I = StartBit, E = StartBit + NumBits; I != E; ++I) {

629 uint8_t Byte = Bytes[I / 8];

630 size_t ByteOffset = I % 8;

631 if (size_t ByteShift = 8 - ByteOffset - 1)

632 Byte >>= ByteShift;

633 OS << (Byte & 0x1 ? '1' : '0');

634 }

635}

636

637void SubtrieHandle::printHash(raw_ostream &OS, ArrayRef<uint8_t> Bytes) const {

638

639 size_t EndBit = getStartBit() + getNumBits();

640 size_t HashEndBit = Bytes.size() * 8u;

641

642 size_t FirstBinaryBit = getStartBit() & ~0x3u;

643 printHexDigits(OS, Bytes, 0, FirstBinaryBit);

644

645 size_t LastBinaryBit = (EndBit + 3u) & ~0x3u;

646 OS << "[";

647 printBits(OS, Bytes, FirstBinaryBit, LastBinaryBit - FirstBinaryBit);

648 OS << "]";

649

650 printHexDigits(OS, Bytes, LastBinaryBit, HashEndBit - LastBinaryBit);

651}

652

653static void appendIndexBits(std::string &Prefix, size_t Index,

654 size_t NumSlots) {

655 std::string Bits;

656 for (size_t NumBits = 1u; NumBits < NumSlots; NumBits <<= 1) {

657 Bits.push_back('0' + (Index & 0x1));

659 }

662}

663

664static void printPrefix(raw_ostream &OS, StringRef Prefix) {

665 while (Prefix.size() >= 4) {

666 uint8_t Digit;

667 bool ErrorParsingBinary = Prefix.take_front(4).getAsInteger(2, Digit);

668 assert(!ErrorParsingBinary);

669 (void)ErrorParsingBinary;

670 OS << hexdigit(Digit, true);

672 }

674 OS << "[" << Prefix << "]";

675}

676

678

679static Expected<size_t> checkParameter(StringRef Label, size_t Max,

680 std::optional<size_t> Value,

681 std::optional<size_t> Default,

682 StringRef Path, StringRef TableName) {

687

688 if (*Value <= Max)

691 std::errc::argument_out_of_domain, Path, TableName,

692 "invalid " + Label + ": " + Twine(*Value) + " (max: " + Twine(Max) + ")");

693}

694

697 return Impl->File.getRegion().size();

698}

699

700Expected

702 size_t NumHashBits, uint64_t DataSize,

703 uint64_t MaxFileSize,

704 std::optional<uint64_t> NewFileInitialSize,

705 std::optional<size_t> NewTableNumRootBits,

706 std::optional<size_t> NewTableNumSubtrieBits) {

707 SmallString<128> PathStorage;

709 SmallString<128> TrieNameStorage;

710 StringRef TrieName = TrieNameTwine.toStringRef(TrieNameStorage);

711

712 constexpr size_t DefaultNumRootBits = 10;

713 constexpr size_t DefaultNumSubtrieBits = 6;

714

715 size_t NumRootBits;

716 if (Error E = checkParameter(

717 "root bits", TrieRawHashMapHandle::MaxNumRootBits,

718 NewTableNumRootBits, DefaultNumRootBits, Path, TrieName)

719 .moveInto(NumRootBits))

720 return std::move(E);

721

722 size_t NumSubtrieBits;

723 if (Error E = checkParameter("subtrie bits",

724 TrieRawHashMapHandle::MaxNumSubtrieBits,

725 NewTableNumSubtrieBits, DefaultNumSubtrieBits,

726 Path, TrieName)

727 .moveInto(NumSubtrieBits))

728 return std::move(E);

729

730 size_t NumHashBytes = NumHashBits >> 3;

732 checkParameter("hash size", TrieRawHashMapHandle::MaxNumHashBits,

733 NumHashBits, std::nullopt, Path, TrieName)

734 .takeError())

735 return std::move(E);

736 assert(NumHashBits == NumHashBytes << 3 &&

737 "Expected hash size to be byte-aligned");

738 if (NumHashBits != NumHashBytes << 3)

740 std::errc::argument_out_of_domain, Path, TrieName,

741 "invalid hash size: " + Twine(NumHashBits) + " (not byte-aligned)");

742

743

744 auto NewDBConstructor = [&](DatabaseFile &DB) -> Error {

745 auto Trie =

746 TrieRawHashMapHandle::create(DB.getAlloc(), TrieName, NumRootBits,

747 NumSubtrieBits, NumHashBits, DataSize);

749 return Trie.takeError();

750

751 return DB.addTable(*Trie);

752 };

753

754

755 Expected File =

757 if (!File)

758 return File.takeError();

759

760

761 std::optional Table = File->findTable(TrieName);

762 if (!Table)

764 TrieName, "table not found");

765 if (Error E = checkTable("table kind", (size_t)TrieRawHashMapHandle::Kind,

766 (size_t)Table->getHeader().Kind, Path, TrieName))

767 return std::move(E);

768 auto Trie = Table->cast();

769 assert(Trie && "Already checked the kind");

770

771

772 if (Error E = checkTable("hash size", NumHashBits, Trie.getNumHashBits(),

773 Path, TrieName))

774 return std::move(E);

776 Path, TrieName))

777 return std::move(E);

778

779

780

781 if (size_t Flags = Trie.getFlags())

783 "unsupported flags: " + Twine(Flags));

784

785

786 OnDiskTrieRawHashMap::ImplType Impl{DatabaseFile(std::move(*File)), Trie};

788}

789

790static Error createInvalidTrieError(uint64_t Offset, const Twine &Msg) {

792 "invalid trie at 0x" +

794 Msg);

795}

796

797

798

799

800

801namespace {

802

803

804

805

806

807

808class TrieVisitor {

809public:

810 TrieVisitor(TrieRawHashMapHandle Trie, unsigned ThreadCount = 0,

811 unsigned ErrorLimit = 50)

812 : Trie(Trie), ErrorLimit(ErrorLimit),

814 virtual ~TrieVisitor() = default;

816

817private:

818

819 virtual Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) {

821 }

822

823

824 virtual Error visitSlot(unsigned I, SubtrieHandle Subtrie, StringRef Prefix,

825 SubtrieSlotValue Slot) {

827 }

828

829protected:

830 TrieRawHashMapHandle Trie;

831

832private:

833 Error traverseTrieNode(SubtrieHandle Node, StringRef Prefix);

834

835 Error validateSubTrie(SubtrieHandle Node, bool IsRoot);

836

837

838 void addError(Error NewError) {

839 assert(NewError && "not an error");

840 std::lock_guardstd::mutex ErrorLock(Lock);

841 if (NumError >= ErrorLimit) {

842

844 return;

845 }

846

847 if (Err)

848 Err = joinErrors(std::move(*Err), std::move(NewError));

849 else

850 Err = std::move(NewError);

851 NumError++;

852 }

853

854 bool tooManyErrors() {

855 std::lock_guardstd::mutex ErrorLock(Lock);

856 return (bool)Err && NumError >= ErrorLimit;

857 }

858

859 const unsigned ErrorLimit;

860 std::optional Err;

861 unsigned NumError = 0;

862 std::mutex Lock;

864};

865

866

867class TriePrinter : public TrieVisitor {

868public:

869 TriePrinter(TrieRawHashMapHandle Trie, raw_ostream &OS,

870 function_ref<void(ArrayRef)> PrintRecordData)

871 : TrieVisitor(Trie, 1), OS(OS),

872 PrintRecordData(PrintRecordData) {}

873

874 Error printRecords() {

877

878 OS << "records\n";

880 for (int64_t Offset : Records) {

881 TrieRawHashMapHandle::RecordData Record =

882 Trie.getRecord(SubtrieSlotValue::getDataOffset(Offset));

883 if (auto Err = printRecord(Record))

884 return Err;

885 }

887 }

888

889 Error printRecord(TrieRawHashMapHandle::RecordData &Record) {

890 OS << "- addr=" << (void *)Record.getFileOffset().get() << " ";

891 if (PrintRecordData) {

892 PrintRecordData(Record.Proxy.Data);

893 } else {

894 OS << "bytes=";

895 ArrayRef<uint8_t> Data(

896 reinterpret_cast<const uint8_t *>(Record.Proxy.Data.data()),

897 Record.Proxy.Data.size());

898 printHexDigits(OS, Data, 0, Data.size() * 8);

899 }

900 OS << "\n";

902 }

903

904 Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) override {

905 if (Prefix.empty()) {

906 OS << "root";

907 } else {

908 OS << "subtrie=";

909 printPrefix(OS, Prefix);

910 }

911

912 OS << " addr="

913 << (void *)(reinterpret_cast<const char *>(&SubTrie.getHeader()) -

914 Trie.getRegion().data());

915 OS << " num-slots=" << SubTrie.getNumSlots() << "\n";

917 }

918

919 Error visitSlot(unsigned I, SubtrieHandle Subtrie, StringRef Prefix,

920 SubtrieSlotValue Slot) override {

921 OS << "- index=";

922 for (size_t Pad : {10, 100, 1000})

923 if (I < Pad && Subtrie.getNumSlots() >= Pad)

924 OS << "0";

925 OS << I << " ";

926 if (Slot.isSubtrie()) {

927 OS << "addr=" << (void *)Slot.asSubtrie();

928 OS << " subtrie=";

929 printPrefix(OS, Prefix);

930 OS << "\n";

932 }

933 TrieRawHashMapHandle::RecordData Record = Trie.getRecord(Slot);

934 OS << "addr=" << (void *)Record.getFileOffset().get();

935 OS << " content=";

936 Subtrie.printHash(OS, Record.Proxy.Hash);

937 OS << "\n";

940 }

941

942private:

943 raw_ostream &OS;

944 function_ref<void(ArrayRef)> PrintRecordData;

946};

947

948

949class TrieVerifier : public TrieVisitor {

950public:

951 TrieVerifier(

952 TrieRawHashMapHandle Trie,

953 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>

954 RecordVerifier)

955 : TrieVisitor(Trie), RecordVerifier(RecordVerifier) {}

956

957private:

958 Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) final {

960 }

961

962 Error visitSlot(unsigned I, SubtrieHandle Subtrie, StringRef Prefix,

963 SubtrieSlotValue Slot) final {

964 if (RecordVerifier && Slot.isData()) {

966 return createInvalidTrieError(Slot.asData(), "mis-aligned data entry");

967

968 TrieRawHashMapHandle::RecordData Record =

969 Trie.getRecord(SubtrieSlotValue::getDataOffset(Slot.asData()));

970 return RecordVerifier(Slot.asDataFileOffset(),

971 OnDiskTrieRawHashMap::ConstValueProxy{

972 Record.Proxy.Hash, Record.Proxy.Data});

973 }

975 }

976

977 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>

978 RecordVerifier;

979};

980}

981

982Error TrieVisitor::visit() {

983 auto Root = Trie.getRoot();

984 if (!Root)

986

987 if (auto Err = validateSubTrie(Root, true))

988 return Err;

989

990 if (auto Err = visitSubTrie("", Root))

991 return Err;

992

994 SmallVectorstd::string Prefixes;

995 const size_t NumSlots = Root.getNumSlots();

996 for (size_t I = 0, E = NumSlots; I != E; ++I) {

997 SubtrieSlotValue Slot = Root.load(I);

998 if (!Slot)

999 continue;

1000 uint64_t Offset = Slot.isSubtrie() ? Slot.asSubtrie() : Slot.asData();

1001 if (Offset >= (uint64_t)Trie.getRegion().size())

1002 return createInvalidTrieError(Offset, "slot points out of bound");

1003 std::string SubtriePrefix;

1004 appendIndexBits(SubtriePrefix, I, NumSlots);

1005 if (Slot.isSubtrie()) {

1006 SubtrieHandle S(Trie.getRegion(), Slot);

1008 Prefixes.push_back(SubtriePrefix);

1009 }

1010 if (auto Err = visitSlot(I, Root, SubtriePrefix, Slot))

1011 return Err;

1012 }

1013

1014 for (size_t I = 0, E = Subs.size(); I != E; ++I) {

1015 Threads.async(

1016 [&](unsigned Idx) {

1017

1018 if (tooManyErrors())

1019 return;

1020 if (auto Err = traverseTrieNode(Subs[Idx], Prefixes[Idx]))

1021 addError(std::move(Err));

1022 },

1023 I);

1024 }

1025

1026 Threads.wait();

1027 if (Err)

1028 return std::move(*Err);

1030}

1031

1032Error TrieVisitor::validateSubTrie(SubtrieHandle Node, bool IsRoot) {

1033 char *Addr = reinterpret_cast<char *>(&Node.getHeader());

1034 const int64_t Offset = Node.getFileOffset().get();

1035 if (Addr + Node.getSize() >=

1036 Trie.getRegion().data() + Trie.getRegion().size())

1037 return createInvalidTrieError(Offset, "subtrie node spans out of bound");

1038

1039 if (!IsRoot &&

1040 Node.getStartBit() + Node.getNumBits() > Trie.getNumHashBits()) {

1041 return createInvalidTrieError(Offset,

1042 "subtrie represents too many hash bits");

1043 }

1044

1045 if (IsRoot) {

1046 if (Node.getStartBit() != 0)

1047 return createInvalidTrieError(Offset,

1048 "root node doesn't start at 0 index");

1049

1051 }

1052

1053 if (Node.getNumBits() > Trie.getNumSubtrieBits())

1054 return createInvalidTrieError(Offset, "subtrie has wrong number of slots");

1055

1057}

1058

1059Error TrieVisitor::traverseTrieNode(SubtrieHandle Node, StringRef Prefix) {

1060 if (auto Err = validateSubTrie(Node, false))

1061 return Err;

1062

1063 if (auto Err = visitSubTrie(Prefix, Node))

1064 return Err;

1065

1067 SmallVectorstd::string Prefixes;

1068 const size_t NumSlots = Node.getNumSlots();

1069 for (size_t I = 0, E = NumSlots; I != E; ++I) {

1070 SubtrieSlotValue Slot = Node.load(I);

1071 if (!Slot)

1072 continue;

1073 uint64_t Offset = Slot.isSubtrie() ? Slot.asSubtrie() : Slot.asData();

1074 if (Offset >= (uint64_t)Trie.getRegion().size())

1075 return createInvalidTrieError(Offset, "slot points out of bound");

1076 std::string SubtriePrefix = Prefix.str();

1077 appendIndexBits(SubtriePrefix, I, NumSlots);

1078 if (Slot.isSubtrie()) {

1079 SubtrieHandle S(Trie.getRegion(), Slot);

1081 Prefixes.push_back(SubtriePrefix);

1082 }

1083 if (auto Err = visitSlot(I, Node, SubtriePrefix, Slot))

1084 return Err;

1085 }

1086 for (size_t I = 0, E = Subs.size(); I != E; ++I)

1087 if (auto Err = traverseTrieNode(Subs[I], Prefixes[I]))

1088 return Err;

1089

1091}

1092

1093void TrieRawHashMapHandle::print(

1094 raw_ostream &OS, function_ref<void(ArrayRef)> PrintRecordData) const {

1095 OS << "hash-num-bits=" << getNumHashBits()

1096 << " hash-size=" << getNumHashBytes()

1097 << " record-data-size=" << getRecordDataSize() << "\n";

1098

1099 TriePrinter Printer(*this, OS, PrintRecordData);

1100 if (auto Err = Printer.visit())

1101 OS << "error: " << toString(std::move(Err)) << "\n";

1102

1103 if (auto Err = Printer.printRecords())

1104 OS << "error: " << toString(std::move(Err)) << "\n";

1105}

1106

1107Error TrieRawHashMapHandle::validate(

1109 RecordVerifier) const {

1110

1111 TrieVisitor BasicVerifier(*this);

1112 if (auto Err = BasicVerifier.visit())

1113 return Err;

1114

1115

1116

1117

1118 TrieVerifier Verifier(*this, RecordVerifier);

1120}

1121

1122#else

1123

1125

1130 std::optional<uint64_t> NewFileInitialSize,

1131 std::optional<size_t> NewTableNumRootBits,

1132 std::optional<size_t> NewTableNumSubtrieBits) {

1134 "OnDiskTrieRawHashMap is not supported");

1135}

1136

1142 "OnDiskTrieRawHashMap is not supported");

1143}

1144

1148 "OnDiskTrieRawHashMap is not supported");

1149}

1150

1155

1159

1162 RecordVerifier) const {

1164 "OnDiskTrieRawHashMap is not supported");

1165}

1166

1169

1170#endif

1171

1173 : Impl(std::move(Impl)) {}

1175 default;

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

AMDGPU Mark last scratch load

AMDGPU Prepare AGPR Alloc

static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

#define LLVM_UNLIKELY(EXPR)

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

dxil pretty DXIL Metadata Pretty Printer

This file declares the common interface for a DatabaseFile that is used to implement OnDiskCAS.

static DeltaTreeNode * getRoot(void *Root)

static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE)

When an instruction is found to only be used outside of the loop, this function moves it to the exit ...

This file declares interface for MappedFileRegionArena, a bump pointer allocator, backed by a memory-...

This file declares interface for OnDiskTrieRawHashMap, a thread-safe and (mostly) lock-free hash map ...

void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)

verify safepoint Safepoint IR Verifier

static RecordT createRecord(const CVSymbol &sym)

static uint32_t getFlags(const Symbol *Sym)

static cl::opt< int > ThreadCount("threads", cl::init(0))

static unsigned getSize(unsigned Kind)

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

size_t size() const

size - Get the array size.

Lightweight error class with error context and mandatory checking.

static ErrorSuccess success()

Create a success value.

Tagged union holding either a T or a Error.

void push_back(const T &Elt)

StringRef - Represent a constant reference to a string, i.e.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

StringRef toStringRef(SmallVectorImpl< char > &Out) const

This returns the twine as a single StringRef if it can be represented as such.

FileOffset is a wrapper around uint64_t to represent the offset of data from the beginning of the fil...

Allocator for an owned mapped file region that supports thread-safe and process-safe bump pointer all...

static constexpr Align getAlign()

Minimum alignment for allocations, currently hardcoded to 8B.

OnDiskTrieRawHashMap is a persistent trie data structure used as hash maps.

LLVM_ABI_FOR_TEST OnDiskTrieRawHashMap(OnDiskTrieRawHashMap &&RHS)

function_ref< void(FileOffset TentativeOffset, ValueProxy TentativeValue)> LazyInsertOnConstructCB

LLVM_ABI_FOR_TEST Error validate(function_ref< Error(FileOffset, ConstValueProxy)> RecordVerifier) const

Validate the trie data structure.

Definition OnDiskTrieRawHashMap.cpp:1160

static LLVM_ABI_FOR_TEST Expected< OnDiskTrieRawHashMap > create(const Twine &Path, const Twine &TrieName, size_t NumHashBits, uint64_t DataSize, uint64_t MaxFileSize, std::optional< uint64_t > NewFileInitialSize, std::optional< size_t > NewTableNumRootBits=std::nullopt, std::optional< size_t > NewTableNumSubtrieBits=std::nullopt)

Gets or creates a file at Path with a hash-mapped trie named TrieName.

Definition OnDiskTrieRawHashMap.cpp:1127

LLVM_ABI_FOR_TEST ConstOnDiskPtr find(ArrayRef< uint8_t > Hash) const

Find the value from hash.

Definition OnDiskTrieRawHashMap.cpp:1152

LLVM_DUMP_METHOD void dump() const

LLVM_ABI_FOR_TEST size_t size() const

Definition OnDiskTrieRawHashMap.cpp:1167

static bool validOffset(FileOffset Offset)

Check the valid range of file offset for OnDiskTrieRawHashMap.

LLVM_ABI_FOR_TEST Expected< OnDiskPtr > insertLazy(ArrayRef< uint8_t > Hash, LazyInsertOnConstructCB OnConstruct=nullptr, LazyInsertOnLeakCB OnLeak=nullptr)

Insert lazily.

Definition OnDiskTrieRawHashMap.cpp:1138

LLVM_ABI_FOR_TEST size_t capacity() const

Definition OnDiskTrieRawHashMap.cpp:1168

LLVM_ABI_FOR_TEST Expected< ConstOnDiskPtr > recoverFromFileOffset(FileOffset Offset) const

Helper function to recover a pointer into the trie from file offset.

Definition OnDiskTrieRawHashMap.cpp:1146

LLVM_ABI_FOR_TEST OnDiskTrieRawHashMap & operator=(OnDiskTrieRawHashMap &&RHS)

void print(raw_ostream &OS, function_ref< void(ArrayRef< char >)> PrintRecordData=nullptr) const

Definition OnDiskTrieRawHashMap.cpp:1156

function_ref< void(FileOffset TentativeOffset, ValueProxy TentativeValue, FileOffset FinalOffset, ValueProxy FinalValue)> LazyInsertOnLeakCB

LLVM_ABI_FOR_TEST ~OnDiskTrieRawHashMap()

static Expected< DatabaseFile > create(const Twine &Path, uint64_t Capacity, function_ref< Error(DatabaseFile &)> NewDBConstructor)

Create the DatabaseFile at Path with Capacity.

An efficient, type-erasing, non-owning reference to a callable.

This class implements an extremely fast bulk output stream that can only output to a stream.

llvm::SmallVector< std::shared_ptr< RecordsSlice >, 4 > Records

void validate(const Triple &TT, const FeatureBitset &FeatureBits)

Error createTableConfigError(std::errc ErrC, StringRef Path, StringRef TableName, const Twine &Msg)

MappedFileRegionArena::RegionT MappedFileRegion

Error checkTable(StringRef Label, size_t Expected, size_t Observed, StringRef Path, StringRef TrieName)

NodeAddr< NodeBase * > Node

This is an optimization pass for GlobalISel generic memory operations.

ThreadPoolStrategy hardware_concurrency(unsigned ThreadCount=0)

Returns a default thread strategy where all available hardware resources are to be used,...

FunctionAddr VTableAddr Value

std::error_code make_error_code(BitcodeError E)

bool isAligned(Align Lhs, uint64_t SizeInBytes)

Checks that SizeInBytes is a multiple of the alignment.

FunctionAddr VTableAddr uintptr_t uintptr_t DataSize

std::string utohexstr(uint64_t X, bool LowerCase=false, unsigned Width=0)

Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)

Create formatted StringError object.

static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)

auto reverse(ContainerTy &&C)

Error joinErrors(Error E1, Error E2)

Concatenate errors.

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

char hexdigit(unsigned X, bool LowerCase=false)

hexdigit - Return the hexadecimal character for the given number X (which should be less than 16).

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

MutableArrayRef(T &OneElt) -> MutableArrayRef< T >

FunctionAddr VTableAddr uintptr_t uintptr_t Data

@ Sub

Subtraction of integers.

SingleThreadExecutor DefaultThreadPool

ArrayRef(const T &OneElt) -> ArrayRef< T >

std::string toString(const APInt &I, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true, bool InsertSeparators=false)

OutputIt copy(R &&Range, OutputIt Out)

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

@ Default

The result values are uniform if and only if all operands are uniform.

void consumeError(Error Err)

Consume a Error without doing anything.

Implement std::hash so that hash_code can be used in STL containers.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

size_t getNumBits() const

size_t getCollidingBits(ArrayRef< uint8_t > CollidingBits) const

Const value proxy to access the records stored in TrieRawHashMap.

Value proxy to access the records stored in TrieRawHashMap.

MutableArrayRef< char > Data