18#include "llvm/Config/llvm-config.h"
27#if LLVM_ENABLE_ONDISK_CAS
36class TrieRawHashMapHandle;
42class SubtrieSlotValue {
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 {
52 uint64_t asSubtrie()
const {
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);
67 static SubtrieSlotValue getSubtrieOffset(int64_t
Offset) {
68 return SubtrieSlotValue(-
Offset);
71 static SubtrieSlotValue getDataOffset(FileOffset
Offset) {
72 return getDataOffset(
Offset.get());
75 static SubtrieSlotValue getSubtrieOffset(FileOffset
Offset) {
76 return getDataOffset(
Offset.get());
79 static SubtrieSlotValue getFromSlot(std::atomic<int64_t> &Slot) {
80 return SubtrieSlotValue(
Slot.load());
83 SubtrieSlotValue() =
default;
86 friend class SubtrieHandle;
114 using SlotT = std::atomic<int64_t>;
116 static int64_t getSlotsSize(uint32_t NumBits) {
117 return sizeof(int64_t) * (1ull << NumBits);
120 static int64_t
getSize(uint32_t NumBits) {
121 return sizeof(SubtrieHandle::Header) + getSlotsSize(NumBits);
125 size_t getNumSlots()
const {
return Slots.size(); }
127 SubtrieSlotValue
load(
size_t I)
const {
128 return SubtrieSlotValue(Slots[
I].
load());
130 void store(
size_t I, SubtrieSlotValue V) {
131 return Slots[
I].store(
V.getRawOffset());
134 void printHash(raw_ostream &OS, ArrayRef<uint8_t> Bytes)
const;
137 bool compare_exchange_strong(
size_t I, SubtrieSlotValue &Expected,
138 SubtrieSlotValue New) {
139 return Slots[
I].compare_exchange_strong(Expected.Offset,
New.Offset);
152 Expected<SubtrieHandle>
sink(
size_t I, SubtrieSlotValue V,
153 MappedFileRegionArena &
Alloc,
154 size_t NumSubtrieBits,
155 SubtrieHandle &UnusedSubtrie,
size_t NewI);
158 void reinitialize(uint32_t StartBit, uint32_t NumBits);
161 return SubtrieSlotValue::getSubtrieOffset(
162 reinterpret_cast<const char *
>(
H) -
Region->data());
165 FileOffset getFileOffset()
const {
return getOffset().asSubtrieFileOffset(); }
167 explicit operator bool()
const {
return H; }
169 Header &getHeader()
const {
return *
H; }
170 uint32_t getStartBit()
const {
return H->StartBit; }
171 uint32_t getNumBits()
const {
return H->NumBits; }
173 static Expected<SubtrieHandle> create(MappedFileRegionArena &
Alloc,
174 uint32_t StartBit, uint32_t NumBits);
178 return SubtrieHandle(Region, SubtrieSlotValue::getSubtrieOffset(
Offset));
181 SubtrieHandle() =
default;
185 : SubtrieHandle(
Region, *reinterpret_cast<Header *>(
214class TrieRawHashMapHandle {
217 TableHandle::TableKind::TrieRawHashMap;
220 TableHandle::Header GenericHeader;
221 uint8_t NumSubtrieBits;
223 uint16_t NumHashBits;
224 uint32_t RecordDataSize;
225 std::atomic<int64_t> RootTrieOffset;
226 std::atomic<int64_t> AllocatorOffset;
229 operator TableHandle()
const {
231 return TableHandle();
232 return TableHandle(*Region,
H->GenericHeader);
236 OnDiskTrieRawHashMap::ValueProxy Proxy;
238 FileOffset getFileOffset()
const {
return Offset.asDataFileOffset(); }
241 enum Limits :
size_t {
243 MaxNumHashBytes = UINT16_MAX >> 3,
244 MaxNumHashBits = MaxNumHashBytes << 3,
252 MaxNumSubtrieBits = 10,
255 static constexpr size_t getNumHashBytes(
size_t NumHashBits) {
256 assert(NumHashBits % 8 == 0);
257 return NumHashBits / 8;
259 static constexpr size_t getRecordSize(
size_t RecordDataSize,
260 size_t NumHashBits) {
261 return RecordDataSize + getNumHashBytes(NumHashBits);
264 RecordData getRecord(SubtrieSlotValue
Offset);
266 ArrayRef<uint8_t> Hash);
268 explicit operator bool()
const {
return H; }
269 const Header &getHeader()
const {
return *
H; }
271 Expected<SubtrieHandle> getOrCreateRoot(MappedFileRegionArena &
Alloc);
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);
283 TrieHashIndexGenerator getIndexGen(SubtrieHandle Root,
284 ArrayRef<uint8_t> Hash) {
285 assert(Root.getStartBit() == 0);
288 return TrieHashIndexGenerator{Root.getNumBits(), getNumSubtrieBits(), Hash};
291 static Expected<TrieRawHashMapHandle>
292 create(MappedFileRegionArena &
Alloc, StringRef Name,
293 std::optional<uint64_t> NumRootBits, uint64_t NumSubtrieBits,
294 uint64_t NumHashBits, uint64_t RecordDataSize);
297 print(raw_ostream &OS,
298 function_ref<
void(ArrayRef<char>)> PrintRecordData =
nullptr)
const;
301 function_ref<
Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>
302 RecordVerifier)
const;
303 TrieRawHashMapHandle() =
default;
307 : TrieRawHashMapHandle(
320 TrieRawHashMapHandle Trie;
326 assert(StartBit <= TrieRawHashMapHandle::MaxNumHashBits);
327 assert(NumBits <= UINT8_MAX);
328 assert(NumBits <= TrieRawHashMapHandle::MaxNumRootBits);
332 return Mem.takeError();
336 SubtrieHandle S(
Alloc.getRegion(), *
H);
337 for (
auto I = S.Slots.begin(),
E = S.Slots.end();
I !=
E; ++
I)
342SubtrieHandle TrieRawHashMapHandle::getRoot()
const {
343 if (int64_t Root =
H->RootTrieOffset)
344 return SubtrieHandle(getRegion(), SubtrieSlotValue::getSubtrieOffset(Root));
345 return SubtrieHandle();
351 if (SubtrieHandle Root =
getRoot())
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()))
365 return SubtrieHandle(getRegion(), SubtrieSlotValue::getSubtrieOffset(Race));
370 std::optional<uint64_t> NumRootBits,
376 return Offset.takeError();
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");
392 char *NameStorage =
reinterpret_cast<char *
>(
H + 1);
394 NameStorage[
Name.size()] = 0;
397 TrieRawHashMapHandle Trie(
Alloc.getRegion(), *
H);
398 auto Sub = SubtrieHandle::create(
Alloc, 0, *NumRootBits);
400 return Sub.takeError();
402 H->RootTrieOffset =
Sub->getOffset().asSubtrie();
406TrieRawHashMapHandle::RecordData
407TrieRawHashMapHandle::getRecord(SubtrieSlotValue
Offset) {
413 return RecordData{Proxy,
Offset};
421 auto Offset =
Alloc.allocateOffset(getRecordSize());
423 return Offset.takeError();
425 RecordData
Record = getRecord(SubtrieSlotValue::getDataOffset(*
Offset));
435 "unaligned file offset at 0x" +
443 Offset.get() + Impl->Trie.getRecordSize() > Impl->File.getAlloc().size())
445 "file offset too large: 0x" +
449 TrieRawHashMapHandle::RecordData
D =
450 Impl->Trie.getRecord(SubtrieSlotValue::getDataOffset(
Offset));
456 TrieRawHashMapHandle Trie = Impl->Trie;
457 assert(Hash.
size() == Trie.getNumHashBytes() &&
"Invalid hash");
459 SubtrieHandle S = Trie.getRoot();
463 TrieHashIndexGenerator IndexGen = Trie.getIndexGen(S, Hash);
467 SubtrieSlotValue
V = S.load(Index);
473 TrieRawHashMapHandle::RecordData
D = Trie.getRecord(V);
479 S = SubtrieHandle(Trie.getRegion(), V);
484void SubtrieHandle::reinitialize(uint32_t StartBit, uint32_t NumBits) {
485 assert(StartBit >
H->StartBit);
486 assert(NumBits <= H->NumBits);
489 H->StartBit = StartBit;
490 H->NumBits = NumBits;
493Expected<OnDiskTrieRawHashMap::pointer>
495 LazyInsertOnConstructCB OnConstruct,
496 LazyInsertOnLeakCB OnLeak) {
497 TrieRawHashMapHandle Trie = Impl->Trie;
498 assert(Hash.
size() == Trie.getNumHashBytes() &&
"Invalid hash");
500 MappedFileRegionArena &
Alloc = Impl->File.getAlloc();
501 std::optional<SubtrieHandle> S;
502 auto Err = Trie.getOrCreateRoot(
Alloc).moveInto(S);
504 return std::move(Err);
506 TrieHashIndexGenerator IndexGen = Trie.getIndexGen(*S, Hash);
510 std::optional<TrieRawHashMapHandle::RecordData> NewRecord;
511 SubtrieHandle UnusedSubtrie;
513 SubtrieSlotValue Existing = S->load(Index);
518 auto Err = Trie.createRecord(
Alloc, Hash).moveInto(NewRecord);
520 return std::move(Err);
522 OnConstruct(NewRecord->Offset.asDataFileOffset(), NewRecord->Proxy);
525 if (S->compare_exchange_strong(Index, Existing, NewRecord->Offset))
526 return pointer(NewRecord->Proxy, NewRecord->Offset.asDataFileOffset());
531 if (Existing.isSubtrie()) {
532 S = SubtrieHandle(Trie.getRegion(), Existing);
538 TrieRawHashMapHandle::RecordData ExistingRecord = Trie.getRecord(Existing);
539 if (ExistingRecord.Proxy.Hash == Hash) {
540 if (NewRecord && OnLeak)
541 OnLeak(NewRecord->Offset.asDataFileOffset(), NewRecord->Proxy,
542 ExistingRecord.Offset.asDataFileOffset(), ExistingRecord.Proxy);
543 return pointer(ExistingRecord.Proxy,
544 ExistingRecord.Offset.asDataFileOffset());
549 size_t NextIndex = IndexGen.
next();
550 size_t NewIndexForExistingContent =
554 UnusedSubtrie, NewIndexForExistingContent)
557 return std::move(Err);
561 if (NextIndex != NewIndexForExistingContent)
567Expected<SubtrieHandle> SubtrieHandle::sink(
size_t I, SubtrieSlotValue V,
569 size_t NumSubtrieBits,
570 SubtrieHandle &UnusedSubtrie,
572 std::optional<SubtrieHandle> NewS;
577 NewS->reinitialize(getStartBit() + getNumBits(), NumSubtrieBits);
580 auto Err = SubtrieHandle::create(
Alloc, getStartBit() + getNumBits(),
584 return std::move(Err);
587 NewS->store(NewI, V);
588 if (compare_exchange_strong(
I, V, NewS->getOffset()))
592 assert(
V.isSubtrie() &&
"Expected racing sink() to add a subtrie");
595 NewS->store(NewI, SubtrieSlotValue());
596 UnusedSubtrie = *NewS;
599 return SubtrieHandle(
Alloc.getRegion(), V);
603 raw_ostream &OS, function_ref<
void(ArrayRef<char>)> PrintRecordData)
const {
604 Impl->Trie.print(OS, PrintRecordData);
608 function_ref<
Error(
FileOffset, ConstValueProxy)> RecordVerifier)
const {
609 return Impl->Trie.validate(RecordVerifier);
613static void printHexDigits(raw_ostream &OS, ArrayRef<uint8_t> Bytes,
614 size_t StartBit,
size_t NumBits) {
615 assert(StartBit % 4 == 0);
617 for (
size_t I = StartBit,
E = StartBit + NumBits;
I !=
E;
I += 4) {
618 uint8_t HexPair = Bytes[
I / 8];
619 uint8_t HexDigit =
I % 8 == 0 ? HexPair >> 4 : HexPair & 0xf;
624static void printBits(raw_ostream &OS, ArrayRef<uint8_t> Bytes,
size_t StartBit,
626 assert(StartBit + NumBits <= Bytes.
size() * 8u);
627 for (
size_t I = StartBit,
E = StartBit + NumBits;
I !=
E; ++
I) {
628 uint8_t
Byte = Bytes[
I / 8];
629 size_t ByteOffset =
I % 8;
630 if (
size_t ByteShift = 8 - ByteOffset - 1)
632 OS << (
Byte & 0x1 ?
'1' :
'0');
636void SubtrieHandle::printHash(raw_ostream &OS, ArrayRef<uint8_t> Bytes)
const {
638 size_t EndBit = getStartBit() + getNumBits();
639 size_t HashEndBit = Bytes.
size() * 8u;
641 size_t FirstBinaryBit = getStartBit() & ~0x3u;
642 printHexDigits(OS, Bytes, 0, FirstBinaryBit);
644 size_t LastBinaryBit = (EndBit + 3u) & ~0x3u;
646 printBits(OS, Bytes, FirstBinaryBit, LastBinaryBit - FirstBinaryBit);
649 printHexDigits(OS, Bytes, LastBinaryBit, HashEndBit - LastBinaryBit);
652static void appendIndexBits(std::string &Prefix,
size_t Index,
655 for (
size_t NumBits = 1u; NumBits < NumSlots; NumBits <<= 1) {
656 Bits.push_back(
'0' + (Index & 0x1));
663static void printPrefix(raw_ostream &OS, StringRef Prefix) {
664 while (
Prefix.size() >= 4) {
666 bool ErrorParsingBinary =
Prefix.take_front(4).getAsInteger(2, Digit);
667 assert(!ErrorParsingBinary);
668 (void)ErrorParsingBinary;
673 OS <<
"[" <<
Prefix <<
"]";
678static Expected<size_t> checkParameter(StringRef Label,
size_t Max,
679 std::optional<size_t>
Value,
681 StringRef Path, StringRef TableName) {
690 std::errc::argument_out_of_domain, Path, TableName,
691 "invalid " + Label +
": " + Twine(*
Value) +
" (max: " + Twine(Max) +
")");
696 return Impl->File.getRegion().size();
699Expected<OnDiskTrieRawHashMap>
701 size_t NumHashBits, uint64_t
DataSize,
702 uint64_t MaxFileSize,
703 std::optional<uint64_t> NewFileInitialSize,
704 std::optional<size_t> NewTableNumRootBits,
705 std::optional<size_t> NewTableNumSubtrieBits) {
706 SmallString<128> PathStorage;
708 SmallString<128> TrieNameStorage;
709 StringRef TrieName = TrieNameTwine.
toStringRef(TrieNameStorage);
711 constexpr size_t DefaultNumRootBits = 10;
712 constexpr size_t DefaultNumSubtrieBits = 6;
715 if (
Error E = checkParameter(
716 "root bits", TrieRawHashMapHandle::MaxNumRootBits,
717 NewTableNumRootBits, DefaultNumRootBits, Path, TrieName)
718 .moveInto(NumRootBits))
721 size_t NumSubtrieBits;
722 if (
Error E = checkParameter(
"subtrie bits",
723 TrieRawHashMapHandle::MaxNumSubtrieBits,
724 NewTableNumSubtrieBits, DefaultNumSubtrieBits,
726 .moveInto(NumSubtrieBits))
729 size_t NumHashBytes = NumHashBits >> 3;
731 checkParameter(
"hash size", TrieRawHashMapHandle::MaxNumHashBits,
732 NumHashBits, std::nullopt, Path, TrieName)
735 assert(NumHashBits == NumHashBytes << 3 &&
736 "Expected hash size to be byte-aligned");
737 if (NumHashBits != NumHashBytes << 3)
739 std::errc::argument_out_of_domain, Path, TrieName,
740 "invalid hash size: " + Twine(NumHashBits) +
" (not byte-aligned)");
743 auto NewDBConstructor = [&](DatabaseFile &
DB) ->
Error {
745 TrieRawHashMapHandle::create(
DB.getAlloc(), TrieName, NumRootBits,
746 NumSubtrieBits, NumHashBits,
DataSize);
748 return Trie.takeError();
750 return DB.addTable(*Trie);
754 Expected<DatabaseFile>
File =
757 return File.takeError();
760 std::optional<TableHandle> Table =
File->findTable(TrieName);
763 TrieName,
"table not found");
765 (
size_t)Table->getHeader().Kind, Path, TrieName))
767 auto Trie = Table->cast<TrieRawHashMapHandle>();
768 assert(Trie &&
"Already checked the kind");
780 if (
size_t Flags = Trie.getFlags())
782 "unsupported flags: " + Twine(Flags));
785 OnDiskTrieRawHashMap::ImplType Impl{DatabaseFile(std::move(*File)), Trie};
789static Error createInvalidTrieError(uint64_t
Offset,
const Twine &Msg) {
791 "invalid trie at 0x" +
809 TrieVisitor(TrieRawHashMapHandle Trie,
unsigned ThreadCount = 0,
810 unsigned ErrorLimit = 50)
811 : Trie(Trie), ErrorLimit(ErrorLimit),
813 virtual ~TrieVisitor() =
default;
818 virtual Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) {
823 virtual Error visitSlot(
unsigned I, SubtrieHandle Subtrie, StringRef Prefix,
824 SubtrieSlotValue Slot) {
829 TrieRawHashMapHandle Trie;
832 Error traverseTrieNode(SubtrieHandle Node, StringRef Prefix);
834 Error validateSubTrie(SubtrieHandle Node,
bool IsRoot);
837 void addError(
Error NewError) {
838 assert(NewError &&
"not an error");
839 std::lock_guard<std::mutex> ErrorLock(Lock);
840 if (NumError >= ErrorLimit) {
847 Err =
joinErrors(std::move(*Err), std::move(NewError));
849 Err = std::move(NewError);
853 bool tooManyErrors() {
854 std::lock_guard<std::mutex> ErrorLock(Lock);
855 return (
bool)Err && NumError >= ErrorLimit;
858 const unsigned ErrorLimit;
859 std::optional<Error> Err;
860 unsigned NumError = 0;
866class TriePrinter :
public TrieVisitor {
868 TriePrinter(TrieRawHashMapHandle Trie, raw_ostream &OS,
869 function_ref<
void(ArrayRef<char>)> PrintRecordData)
870 : TrieVisitor(Trie, 1), OS(OS),
871 PrintRecordData(PrintRecordData) {}
873 Error printRecords() {
879 for (int64_t
Offset : Records) {
880 TrieRawHashMapHandle::RecordData Record =
881 Trie.getRecord(SubtrieSlotValue::getDataOffset(
Offset));
882 if (
auto Err = printRecord(Record))
888 Error printRecord(TrieRawHashMapHandle::RecordData &Record) {
889 OS <<
"- addr=" << (
void *)Record.getFileOffset().get() <<
" ";
890 if (PrintRecordData) {
891 PrintRecordData(Record.Proxy.Data);
894 ArrayRef<uint8_t>
Data(
895 reinterpret_cast<const uint8_t *
>(Record.Proxy.Data.data()),
896 Record.Proxy.Data.size());
897 printHexDigits(OS,
Data, 0,
Data.size() * 8);
903 Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie)
override {
908 printPrefix(OS, Prefix);
912 << (
void *)(
reinterpret_cast<const char *
>(&SubTrie.getHeader()) -
913 Trie.getRegion().data());
914 OS <<
" num-slots=" << SubTrie.getNumSlots() <<
"\n";
918 Error visitSlot(
unsigned I, SubtrieHandle Subtrie, StringRef Prefix,
919 SubtrieSlotValue Slot)
override {
921 for (
size_t Pad : {10, 100, 1000})
922 if (
I < Pad && Subtrie.getNumSlots() >= Pad)
925 if (
Slot.isSubtrie()) {
926 OS <<
"addr=" << (
void *)
Slot.asSubtrie();
928 printPrefix(OS, Prefix);
932 TrieRawHashMapHandle::RecordData Record = Trie.getRecord(Slot);
933 OS <<
"addr=" << (
void *)Record.getFileOffset().get();
935 Subtrie.printHash(OS, Record.Proxy.Hash);
943 function_ref<void(ArrayRef<char>)> PrintRecordData;
948class TrieVerifier :
public TrieVisitor {
951 TrieRawHashMapHandle Trie,
952 function_ref<
Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>
954 : TrieVisitor(Trie), RecordVerifier(RecordVerifier) {}
957 Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie)
final {
961 Error visitSlot(
unsigned I, SubtrieHandle Subtrie, StringRef Prefix,
962 SubtrieSlotValue Slot)
final {
963 if (RecordVerifier &&
Slot.isData()) {
965 return createInvalidTrieError(
Slot.asData(),
"mis-aligned data entry");
967 TrieRawHashMapHandle::RecordData Record =
968 Trie.getRecord(SubtrieSlotValue::getDataOffset(
Slot.asData()));
969 return RecordVerifier(
Slot.asDataFileOffset(),
970 OnDiskTrieRawHashMap::ConstValueProxy{
971 Record.Proxy.Hash, Record.Proxy.Data});
976 function_ref<
Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>
981Error TrieVisitor::visit() {
982 auto Root = Trie.getRoot();
986 if (
auto Err = validateSubTrie(Root,
true))
989 if (
auto Err = visitSubTrie(
"", Root))
993 SmallVector<std::string> Prefixes;
994 const size_t NumSlots = Root.getNumSlots();
995 for (
size_t I = 0,
E = NumSlots;
I !=
E; ++
I) {
996 SubtrieSlotValue
Slot = Root.load(
I);
1000 if (
Offset >= (uint64_t)Trie.getRegion().size())
1001 return createInvalidTrieError(
Offset,
"slot points out of bound");
1002 std::string SubtriePrefix;
1003 appendIndexBits(SubtriePrefix,
I, NumSlots);
1004 if (
Slot.isSubtrie()) {
1005 SubtrieHandle S(Trie.getRegion(), Slot);
1009 if (
auto Err = visitSlot(
I, Root, SubtriePrefix, Slot))
1013 for (
size_t I = 0,
E = Subs.
size();
I !=
E; ++
I) {
1017 if (tooManyErrors())
1019 if (
auto Err = traverseTrieNode(Subs[Idx], Prefixes[Idx]))
1020 addError(std::move(Err));
1027 return std::move(*Err);
1031Error TrieVisitor::validateSubTrie(SubtrieHandle Node,
bool IsRoot) {
1032 char *Addr =
reinterpret_cast<char *
>(&
Node.getHeader());
1033 const int64_t
Offset =
Node.getFileOffset().get();
1034 if (Addr +
Node.getSize() >=
1035 Trie.getRegion().data() + Trie.getRegion().size())
1036 return createInvalidTrieError(
Offset,
"subtrie node spans out of bound");
1039 Node.getStartBit() +
Node.getNumBits() > Trie.getNumHashBits()) {
1040 return createInvalidTrieError(
Offset,
1041 "subtrie represents too many hash bits");
1045 if (
Node.getStartBit() != 0)
1046 return createInvalidTrieError(
Offset,
1047 "root node doesn't start at 0 index");
1052 if (
Node.getNumBits() > Trie.getNumSubtrieBits())
1053 return createInvalidTrieError(
Offset,
"subtrie has wrong number of slots");
1058Error TrieVisitor::traverseTrieNode(SubtrieHandle Node, StringRef Prefix) {
1059 if (
auto Err = validateSubTrie(Node,
false))
1062 if (
auto Err = visitSubTrie(Prefix, Node))
1066 SmallVector<std::string> Prefixes;
1067 const size_t NumSlots =
Node.getNumSlots();
1068 for (
size_t I = 0,
E = NumSlots;
I !=
E; ++
I) {
1073 if (
Offset >= (uint64_t)Trie.getRegion().size())
1074 return createInvalidTrieError(
Offset,
"slot points out of bound");
1075 std::string SubtriePrefix =
Prefix.str();
1076 appendIndexBits(SubtriePrefix,
I, NumSlots);
1077 if (
Slot.isSubtrie()) {
1078 SubtrieHandle S(Trie.getRegion(), Slot);
1082 if (
auto Err = visitSlot(
I, Node, SubtriePrefix, Slot))
1085 for (
size_t I = 0,
E = Subs.
size();
I !=
E; ++
I)
1086 if (
auto Err = traverseTrieNode(Subs[
I], Prefixes[
I]))
1092void TrieRawHashMapHandle::print(
1093 raw_ostream &OS, function_ref<
void(ArrayRef<char>)> PrintRecordData)
const {
1094 OS <<
"hash-num-bits=" << getNumHashBits()
1095 <<
" hash-size=" << getNumHashBytes()
1096 <<
" record-data-size=" << getRecordDataSize() <<
"\n";
1098 TriePrinter
Printer(*
this, OS, PrintRecordData);
1099 if (
auto Err =
Printer.visit())
1100 OS <<
"error: " <<
toString(std::move(Err)) <<
"\n";
1102 if (
auto Err =
Printer.printRecords())
1103 OS <<
"error: " <<
toString(std::move(Err)) <<
"\n";
1108Error TrieRawHashMapHandle::validate(
1110 RecordVerifier)
const {
1112 TrieVisitor BasicVerifier(*
this);
1113 if (
auto Err = BasicVerifier.visit())
1119 TrieVerifier
Verifier(*
this, RecordVerifier);
1131 std::optional<uint64_t> NewFileInitialSize,
1132 std::optional<size_t> NewTableNumRootBits,
1133 std::optional<size_t> NewTableNumSubtrieBits) {
1135 "OnDiskTrieRawHashMap is not supported");
1143 "OnDiskTrieRawHashMap is not supported");
1149 "OnDiskTrieRawHashMap is not supported");
1163 RecordVerifier)
const {
1165 "OnDiskTrieRawHashMap is not supported");
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.
const_pointer find(ArrayRef< uint8_t > Hash) const
Find the value from hash.
OnDiskTrieRawHashMap(OnDiskTrieRawHashMap &&RHS)
Expected< pointer > insertLazy(ArrayRef< uint8_t > Hash, LazyInsertOnConstructCB OnConstruct=nullptr, LazyInsertOnLeakCB OnLeak=nullptr)
Insert lazily.
function_ref< void(FileOffset TentativeOffset, ValueProxy TentativeValue)> LazyInsertOnConstructCB
Error validate(function_ref< Error(FileOffset, ConstValueProxy)> RecordVerifier) const
Validate the trie data structure.
static 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.
LLVM_DUMP_METHOD void dump() const
Expected< const_pointer > recoverFromFileOffset(FileOffset Offset) const
Helper function to recover a pointer into the trie from file offset.
static bool validOffset(FileOffset Offset)
Check the valid range of file offset for OnDiskTrieRawHashMap.
OnDiskTrieRawHashMap & operator=(OnDiskTrieRawHashMap &&RHS)
void print(raw_ostream &OS, function_ref< void(ArrayRef< char >)> PrintRecordData=nullptr) const
function_ref< void(FileOffset TentativeOffset, ValueProxy TentativeValue, FileOffset FinalOffset, ValueProxy FinalValue)> LazyInsertOnLeakCB
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