LLVM 22.0.0git
OnDiskTrieRawHashMap.cpp
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
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/// \file Implements OnDiskTrieRawHashMap.
10///
11//===----------------------------------------------------------------------===//
12
14#include "DatabaseFile.h"
18#include "llvm/Config/llvm-config.h"
22
23using namespace llvm;
24using namespace llvm::cas;
25using namespace llvm::cas::ondisk;
26
27#if LLVM_ENABLE_ONDISK_CAS
28
29//===----------------------------------------------------------------------===//
30// TrieRawHashMap data structures.
31//===----------------------------------------------------------------------===//
32
33namespace {
34
35class SubtrieHandle;
36class TrieRawHashMapHandle;
37class TrieVisitor;
38
39/// A value stored in the slots inside a SubTrie. A stored value can either be a
40/// subtrie (encoded after negation) which is the file offset to another
41/// subtrie, or it can be a fileset to a DataRecord.
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 {
49 assert(isData());
50 return Offset;
51 }
52 uint64_t asSubtrie() const {
53 assert(isSubtrie());
54 return -Offset;
55 }
56
57 FileOffset asSubtrieFileOffset() const { return FileOffset(asSubtrie()); }
58
59 FileOffset asDataFileOffset() const { return FileOffset(asData()); }
60
61 int64_t getRawOffset() const { return Offset; }
62
63 static SubtrieSlotValue getDataOffset(int64_t Offset) {
64 return SubtrieSlotValue(Offset);
65 }
66
67 static SubtrieSlotValue getSubtrieOffset(int64_t Offset) {
68 return SubtrieSlotValue(-Offset);
69 }
70
71 static SubtrieSlotValue getDataOffset(FileOffset Offset) {
72 return getDataOffset(Offset.get());
73 }
74
75 static SubtrieSlotValue getSubtrieOffset(FileOffset Offset) {
76 return getDataOffset(Offset.get());
77 }
78
79 static SubtrieSlotValue getFromSlot(std::atomic<int64_t> &Slot) {
80 return SubtrieSlotValue(Slot.load());
81 }
82
83 SubtrieSlotValue() = default;
84
85private:
86 friend class SubtrieHandle;
87 explicit SubtrieSlotValue(int64_t Offset) : Offset(Offset) {}
88 int64_t Offset = 0;
89};
90
91/// Subtrie layout:
92/// - 2-bytes: StartBit
93/// - 1-bytes: NumBits=lg(num-slots)
94/// - 5-bytes: 0-pad
95/// - <slots>
96class SubtrieHandle {
97public:
98 struct Header {
99 /// The bit this subtrie starts on.
100 uint16_t StartBit;
101
102 /// The number of bits this subtrie handles. It has 2^NumBits slots.
103 uint8_t NumBits;
104
105 /// 0-pad to 8B.
106 uint8_t ZeroPad1B;
107 uint32_t ZeroPad4B;
108 };
109
110 /// Slot storage:
111 /// - zero: Empty
112 /// - positive: RecordOffset
113 /// - negative: SubtrieOffset
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
124 int64_t getSize() const { return getSize(H->NumBits); }
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 /// Return None on success, or the existing offset on failure.
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 /// Sink \p V from \p I in this subtrie down to \p NewI in a new subtrie with
143 /// \p NumSubtrieBits.
144 ///
145 /// \p UnusedSubtrie maintains a 1-item "free" list of unused subtries. If a
146 /// new subtrie is created that isn't used because of a lost race, then it If
147 /// it's already valid, it should be used instead of allocating a new one.
148 /// should be returned as an out parameter to be passed back in the future.
149 /// If it's already valid, it should be used instead of allocating a new one.
150 ///
151 /// Returns the subtrie that now lives at \p I.
152 Expected<SubtrieHandle> sink(size_t I, SubtrieSlotValue V,
153 MappedFileRegionArena &Alloc,
154 size_t NumSubtrieBits,
155 SubtrieHandle &UnusedSubtrie, size_t NewI);
156
157 /// Only safe if the subtrie is empty.
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<SubtrieHandle> create(MappedFileRegionArena &Alloc,
174 uint32_t StartBit, uint32_t NumBits);
175
176 static SubtrieHandle getFromFileOffset(MappedFileRegion &Region,
177 FileOffset Offset) {
178 return SubtrieHandle(Region, SubtrieSlotValue::getSubtrieOffset(Offset));
179 }
180
181 SubtrieHandle() = default;
182 SubtrieHandle(MappedFileRegion &Region, Header &H)
183 : Region(&Region), H(&H), Slots(getSlots(H)) {}
184 SubtrieHandle(MappedFileRegion &Region, SubtrieSlotValue Offset)
185 : SubtrieHandle(Region, *reinterpret_cast<Header *>(
186 Region.data() + Offset.asSubtrie())) {}
187
188private:
189 MappedFileRegion *Region = nullptr;
190 Header *H = nullptr;
192
193 static MutableArrayRef<SlotT> getSlots(Header &H) {
194 return MutableArrayRef(reinterpret_cast<SlotT *>(&H + 1),
195 1ull << H.NumBits);
196 }
197};
198
199/// Handle for a TrieRawHashMap table.
200///
201/// TrieRawHashMap table layout:
202/// - [8-bytes: Generic table header]
203/// - 1-byte: NumSubtrieBits
204/// - 1-byte: Flags (not used yet)
205/// - 2-bytes: NumHashBits
206/// - 4-bytes: RecordDataSize (in bytes)
207/// - 8-bytes: RootTrieOffset
208/// - 8-bytes: AllocatorOffset (reserved for implementing free lists)
209/// - <name> '\0'
210///
211/// Record layout:
212/// - <hash>
213/// - <data>
214class TrieRawHashMapHandle {
215public:
216 static constexpr TableHandle::TableKind Kind =
217 TableHandle::TableKind::TrieRawHashMap;
218
219 struct Header {
220 TableHandle::Header GenericHeader;
221 uint8_t NumSubtrieBits;
222 uint8_t Flags; ///< None used yet.
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 (!H)
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 /// Seems like 65528 hash bits ought to be enough.
243 MaxNumHashBytes = UINT16_MAX >> 3,
244 MaxNumHashBits = MaxNumHashBytes << 3,
245
246 /// 2^16 bits in a trie is 65536 slots. This restricts us to a 16-bit
247 /// index. This many slots is suspicously large anyway.
248 MaxNumRootBits = 16,
249
250 /// 2^10 bits in a trie is 1024 slots. This many slots seems suspiciously
251 /// large for subtries.
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);
265 Expected<RecordData> createRecord(MappedFileRegionArena &Alloc,
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<SubtrieHandle> getOrCreateRoot(MappedFileRegionArena &Alloc);
272 MappedFileRegion &getRegion() const { return *Region; }
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<TrieRawHashMapHandle>
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<char>)> PrintRecordData = nullptr) const;
299
301 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>
302 RecordVerifier) const;
303 TrieRawHashMapHandle() = default;
304 TrieRawHashMapHandle(MappedFileRegion &Region, Header &H)
305 : Region(&Region), H(&H) {}
306 TrieRawHashMapHandle(MappedFileRegion &Region, intptr_t HeaderOffset)
307 : TrieRawHashMapHandle(
308 Region, *reinterpret_cast<Header *>(Region.data() + HeaderOffset)) {
309 }
310
311private:
312 MappedFileRegion *Region = nullptr;
313 Header *H = nullptr;
314};
315
316} // end anonymous namespace
317
319 DatabaseFile File;
320 TrieRawHashMapHandle Trie;
321};
322
324 uint32_t StartBit,
325 uint32_t NumBits) {
326 assert(StartBit <= TrieRawHashMapHandle::MaxNumHashBits);
327 assert(NumBits <= UINT8_MAX);
328 assert(NumBits <= TrieRawHashMapHandle::MaxNumRootBits);
329
330 auto Mem = Alloc.allocate(getSize(NumBits));
331 if (LLVM_UNLIKELY(!Mem))
332 return Mem.takeError();
333 auto *H =
334 new (*Mem) SubtrieHandle::Header{(uint16_t)StartBit, (uint8_t)NumBits,
335 /*ZeroPad1B=*/0, /*ZeroPad4B=*/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
349TrieRawHashMapHandle::getOrCreateRoot(MappedFileRegionArena &Alloc) {
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);
356 if (LLVM_UNLIKELY(!LazyRoot))
357 return LazyRoot.takeError();
358 if (H->RootTrieOffset.compare_exchange_strong(
359 Race, LazyRoot->getOffset().asSubtrie()))
360 return *LazyRoot;
361
362 // There was a race. Return the other root.
363 //
364 // TODO: Avoid leaking the lazy root by storing it in an allocator.
365 return SubtrieHandle(getRegion(), SubtrieSlotValue::getSubtrieOffset(Race));
366}
367
369TrieRawHashMapHandle::create(MappedFileRegionArena &Alloc, StringRef Name,
370 std::optional<uint64_t> NumRootBits,
371 uint64_t NumSubtrieBits, uint64_t NumHashBits,
372 uint64_t RecordDataSize) {
373 // Allocate.
374 auto Offset = Alloc.allocateOffset(sizeof(Header) + Name.size() + 1);
375 if (LLVM_UNLIKELY(!Offset))
376 return Offset.takeError();
377
378 // Construct the header and the name.
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");
383 auto *H = new (Alloc.getRegion().data() + *Offset)
385 (uint32_t)sizeof(Header)},
386 (uint8_t)NumSubtrieBits,
387 /*Flags=*/0,
388 (uint16_t)NumHashBits,
389 (uint32_t)RecordDataSize,
390 /*RootTrieOffset=*/{0},
391 /*AllocatorOffset=*/{0}};
392 char *NameStorage = reinterpret_cast<char *>(H + 1);
393 llvm::copy(Name, NameStorage);
394 NameStorage[Name.size()] = 0;
395
396 // Construct a root trie, if requested.
397 TrieRawHashMapHandle Trie(Alloc.getRegion(), *H);
398 auto Sub = SubtrieHandle::create(Alloc, 0, *NumRootBits);
399 if (LLVM_UNLIKELY(!Sub))
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();
410 Proxy.Data = MutableArrayRef(Begin, getRecordDataSize());
411 Proxy.Hash = ArrayRef(reinterpret_cast<const uint8_t *>(Proxy.Data.end()),
412 getNumHashBytes());
413 return RecordData{Proxy, Offset};
414}
415
417TrieRawHashMapHandle::createRecord(MappedFileRegionArena &Alloc,
418 ArrayRef<uint8_t> Hash) {
419 assert(&Alloc.getRegion() == Region);
420 assert(Hash.size() == getNumHashBytes());
421 auto Offset = Alloc.allocateOffset(getRecordSize());
422 if (LLVM_UNLIKELY(!Offset))
423 return Offset.takeError();
424
425 RecordData Record = getRecord(SubtrieSlotValue::getDataOffset(*Offset));
426 llvm::copy(Hash, const_cast<uint8_t *>(Record.Proxy.Hash.begin()));
427 return Record;
428}
429
432 // Check alignment.
434 return createStringError(make_error_code(std::errc::protocol_error),
435 "unaligned file offset at 0x" +
436 utohexstr(Offset.get(), /*LowerCase=*/true));
437
438 // Check bounds.
439 //
440 // Note: There's no potential overflow when using \c uint64_t because Offset
441 // is in valid offset range and the record size is in \c [0,UINT32_MAX].
442 if (!validOffset(Offset) ||
443 Offset.get() + Impl->Trie.getRecordSize() > Impl->File.getAlloc().size())
444 return createStringError(make_error_code(std::errc::protocol_error),
445 "file offset too large: 0x" +
446 utohexstr(Offset.get(), /*LowerCase=*/true));
447
448 // Looks okay...
449 TrieRawHashMapHandle::RecordData D =
450 Impl->Trie.getRecord(SubtrieSlotValue::getDataOffset(Offset));
451 return const_pointer(D.Proxy, D.getFileOffset());
452}
453
455OnDiskTrieRawHashMap::find(ArrayRef<uint8_t> Hash) const {
456 TrieRawHashMapHandle Trie = Impl->Trie;
457 assert(Hash.size() == Trie.getNumHashBytes() && "Invalid hash");
458
459 SubtrieHandle S = Trie.getRoot();
460 if (!S)
461 return const_pointer();
462
463 TrieHashIndexGenerator IndexGen = Trie.getIndexGen(S, Hash);
464 size_t Index = IndexGen.next();
465 for (;;) {
466 // Try to set the content.
467 SubtrieSlotValue V = S.load(Index);
468 if (!V)
469 return const_pointer();
470
471 // Check for an exact match.
472 if (V.isData()) {
473 TrieRawHashMapHandle::RecordData D = Trie.getRecord(V);
474 return D.Proxy.Hash == Hash ? const_pointer(D.Proxy, D.getFileOffset())
475 : const_pointer();
476 }
477
478 Index = IndexGen.next();
479 S = SubtrieHandle(Trie.getRegion(), V);
480 }
481}
482
483/// Only safe if the subtrie is empty.
484void SubtrieHandle::reinitialize(uint32_t StartBit, uint32_t NumBits) {
485 assert(StartBit > H->StartBit);
486 assert(NumBits <= H->NumBits);
487 // Ideally would also assert that all slots are empty, but that's expensive.
488
489 H->StartBit = StartBit;
490 H->NumBits = NumBits;
491}
492
493Expected<OnDiskTrieRawHashMap::pointer>
494OnDiskTrieRawHashMap::insertLazy(ArrayRef<uint8_t> Hash,
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<SubtrieHandle> S;
502 auto Err = Trie.getOrCreateRoot(Alloc).moveInto(S);
503 if (LLVM_UNLIKELY(Err))
504 return std::move(Err);
505
506 TrieHashIndexGenerator IndexGen = Trie.getIndexGen(*S, Hash);
507 size_t Index = IndexGen.next();
508
509 // Walk through the hash bytes and insert into correct trie position.
510 std::optional<TrieRawHashMapHandle::RecordData> NewRecord;
511 SubtrieHandle UnusedSubtrie;
512 for (;;) {
513 SubtrieSlotValue Existing = S->load(Index);
514
515 // Try to set it, if it's empty.
516 if (!Existing) {
517 if (!NewRecord) {
518 auto Err = Trie.createRecord(Alloc, Hash).moveInto(NewRecord);
519 if (LLVM_UNLIKELY(Err))
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 pointer(NewRecord->Proxy, NewRecord->Offset.asDataFileOffset());
527
528 // Race means that Existing is no longer empty; fall through...
529 }
530
531 if (Existing.isSubtrie()) {
532 S = SubtrieHandle(Trie.getRegion(), Existing);
533 Index = IndexGen.next();
534 continue;
535 }
536
537 // Check for an exact match.
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());
545 }
546
547 // Sink the existing content as long as the indexes match.
548 for (;;) {
549 size_t NextIndex = IndexGen.next();
550 size_t NewIndexForExistingContent =
551 IndexGen.getCollidingBits(ExistingRecord.Proxy.Hash);
552
553 auto Err = S->sink(Index, Existing, Alloc, IndexGen.getNumBits(),
554 UnusedSubtrie, NewIndexForExistingContent)
555 .moveInto(S);
556 if (LLVM_UNLIKELY(Err))
557 return std::move(Err);
558 Index = NextIndex;
559
560 // Found the difference.
561 if (NextIndex != NewIndexForExistingContent)
562 break;
563 }
564 }
565}
566
567Expected<SubtrieHandle> SubtrieHandle::sink(size_t I, SubtrieSlotValue V,
569 size_t NumSubtrieBits,
570 SubtrieHandle &UnusedSubtrie,
571 size_t NewI) {
572 std::optional<SubtrieHandle> NewS;
573 if (UnusedSubtrie) {
574 // Steal UnusedSubtrie and initialize it.
575 NewS.emplace();
576 std::swap(*NewS, UnusedSubtrie);
577 NewS->reinitialize(getStartBit() + getNumBits(), NumSubtrieBits);
578 } else {
579 // Allocate a new, empty subtrie.
580 auto Err = SubtrieHandle::create(Alloc, getStartBit() + getNumBits(),
581 NumSubtrieBits)
582 .moveInto(NewS);
583 if (LLVM_UNLIKELY(Err))
584 return std::move(Err);
585 }
586
587 NewS->store(NewI, V);
588 if (compare_exchange_strong(I, V, NewS->getOffset()))
589 return *NewS; // Success!
590
591 // Raced.
592 assert(V.isSubtrie() && "Expected racing sink() to add a subtrie");
593
594 // Wipe out the new slot so NewS can be reused and set the out parameter.
595 NewS->store(NewI, SubtrieSlotValue());
596 UnusedSubtrie = *NewS;
597
598 // Return the subtrie added by the concurrent sink() call.
599 return SubtrieHandle(Alloc.getRegion(), V);
600}
601
603 raw_ostream &OS, function_ref<void(ArrayRef<char>)> PrintRecordData) const {
604 Impl->Trie.print(OS, PrintRecordData);
605}
606
608 function_ref<Error(FileOffset, ConstValueProxy)> RecordVerifier) const {
609 return Impl->Trie.validate(RecordVerifier);
610}
611
612// Helper function that prints hexdigit and have a sub-byte starting position.
613static void printHexDigits(raw_ostream &OS, ArrayRef<uint8_t> Bytes,
614 size_t StartBit, size_t NumBits) {
615 assert(StartBit % 4 == 0);
616 assert(NumBits % 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;
620 OS << hexdigit(HexDigit, /*LowerCase=*/true);
621 }
622}
623
624static void printBits(raw_ostream &OS, ArrayRef<uint8_t> Bytes, size_t StartBit,
625 size_t NumBits) {
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)
631 Byte >>= ByteShift;
632 OS << (Byte & 0x1 ? '1' : '0');
633 }
634}
635
636void SubtrieHandle::printHash(raw_ostream &OS, ArrayRef<uint8_t> Bytes) const {
637 // afb[1c:00*01110*0]def
638 size_t EndBit = getStartBit() + getNumBits();
639 size_t HashEndBit = Bytes.size() * 8u;
640
641 size_t FirstBinaryBit = getStartBit() & ~0x3u;
642 printHexDigits(OS, Bytes, 0, FirstBinaryBit);
643
644 size_t LastBinaryBit = (EndBit + 3u) & ~0x3u;
645 OS << "[";
646 printBits(OS, Bytes, FirstBinaryBit, LastBinaryBit - FirstBinaryBit);
647 OS << "]";
648
649 printHexDigits(OS, Bytes, LastBinaryBit, HashEndBit - LastBinaryBit);
650}
651
652static void appendIndexBits(std::string &Prefix, size_t Index,
653 size_t NumSlots) {
654 std::string Bits;
655 for (size_t NumBits = 1u; NumBits < NumSlots; NumBits <<= 1) {
656 Bits.push_back('0' + (Index & 0x1));
657 Index >>= 1;
658 }
659 for (char Ch : llvm::reverse(Bits))
660 Prefix += Ch;
661}
662
663static void printPrefix(raw_ostream &OS, StringRef Prefix) {
664 while (Prefix.size() >= 4) {
665 uint8_t Digit;
666 bool ErrorParsingBinary = Prefix.take_front(4).getAsInteger(2, Digit);
667 assert(!ErrorParsingBinary);
668 (void)ErrorParsingBinary;
669 OS << hexdigit(Digit, /*LowerCase=*/true);
670 Prefix = Prefix.drop_front(4);
671 }
672 if (!Prefix.empty())
673 OS << "[" << Prefix << "]";
674}
675
677
678static Expected<size_t> checkParameter(StringRef Label, size_t Max,
679 std::optional<size_t> Value,
680 std::optional<size_t> Default,
681 StringRef Path, StringRef TableName) {
682 assert(Value || Default);
683 assert(!Default || *Default <= Max);
684 if (!Value)
685 return *Default;
686
687 if (*Value <= Max)
688 return *Value;
690 std::errc::argument_out_of_domain, Path, TableName,
691 "invalid " + Label + ": " + Twine(*Value) + " (max: " + Twine(Max) + ")");
692}
693
694size_t OnDiskTrieRawHashMap::size() const { return Impl->File.size(); }
695size_t OnDiskTrieRawHashMap::capacity() const {
696 return Impl->File.getRegion().size();
697}
698
699Expected<OnDiskTrieRawHashMap>
700OnDiskTrieRawHashMap::create(const Twine &PathTwine, const Twine &TrieNameTwine,
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;
707 StringRef Path = PathTwine.toStringRef(PathStorage);
708 SmallString<128> TrieNameStorage;
709 StringRef TrieName = TrieNameTwine.toStringRef(TrieNameStorage);
710
711 constexpr size_t DefaultNumRootBits = 10;
712 constexpr size_t DefaultNumSubtrieBits = 6;
713
714 size_t NumRootBits;
715 if (Error E = checkParameter(
716 "root bits", TrieRawHashMapHandle::MaxNumRootBits,
717 NewTableNumRootBits, DefaultNumRootBits, Path, TrieName)
718 .moveInto(NumRootBits))
719 return std::move(E);
720
721 size_t NumSubtrieBits;
722 if (Error E = checkParameter("subtrie bits",
723 TrieRawHashMapHandle::MaxNumSubtrieBits,
724 NewTableNumSubtrieBits, DefaultNumSubtrieBits,
725 Path, TrieName)
726 .moveInto(NumSubtrieBits))
727 return std::move(E);
728
729 size_t NumHashBytes = NumHashBits >> 3;
730 if (Error E =
731 checkParameter("hash size", TrieRawHashMapHandle::MaxNumHashBits,
732 NumHashBits, std::nullopt, Path, TrieName)
733 .takeError())
734 return std::move(E);
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)");
741
742 // Constructor for if the file doesn't exist.
743 auto NewDBConstructor = [&](DatabaseFile &DB) -> Error {
744 auto Trie =
745 TrieRawHashMapHandle::create(DB.getAlloc(), TrieName, NumRootBits,
746 NumSubtrieBits, NumHashBits, DataSize);
747 if (LLVM_UNLIKELY(!Trie))
748 return Trie.takeError();
749
750 return DB.addTable(*Trie);
751 };
752
753 // Get or create the file.
754 Expected<DatabaseFile> File =
755 DatabaseFile::create(Path, MaxFileSize, NewDBConstructor);
756 if (!File)
757 return File.takeError();
758
759 // Find the trie and validate it.
760 std::optional<TableHandle> Table = File->findTable(TrieName);
761 if (!Table)
762 return createTableConfigError(std::errc::argument_out_of_domain, Path,
763 TrieName, "table not found");
764 if (Error E = checkTable("table kind", (size_t)TrieRawHashMapHandle::Kind,
765 (size_t)Table->getHeader().Kind, Path, TrieName))
766 return std::move(E);
767 auto Trie = Table->cast<TrieRawHashMapHandle>();
768 assert(Trie && "Already checked the kind");
769
770 // Check the hash and data size.
771 if (Error E = checkTable("hash size", NumHashBits, Trie.getNumHashBits(),
772 Path, TrieName))
773 return std::move(E);
774 if (Error E = checkTable("data size", DataSize, Trie.getRecordDataSize(),
775 Path, TrieName))
776 return std::move(E);
777
778 // No flags supported right now. Either corrupt, or coming from a future
779 // writer.
780 if (size_t Flags = Trie.getFlags())
781 return createTableConfigError(std::errc::invalid_argument, Path, TrieName,
782 "unsupported flags: " + Twine(Flags));
783
784 // Success.
785 OnDiskTrieRawHashMap::ImplType Impl{DatabaseFile(std::move(*File)), Trie};
786 return OnDiskTrieRawHashMap(std::make_unique<ImplType>(std::move(Impl)));
787}
788
789static Error createInvalidTrieError(uint64_t Offset, const Twine &Msg) {
790 return createStringError(make_error_code(std::errc::protocol_error),
791 "invalid trie at 0x" +
792 utohexstr(Offset, /*LowerCase=*/true) + ": " +
793 Msg);
794}
795
796//===----------------------------------------------------------------------===//
797// TrieVisitor data structures.
798//===----------------------------------------------------------------------===//
799
800namespace {
801/// A multi-threaded vistior to traverse the Trie.
802///
803/// TODO: add more sanity checks that isn't just plain data corruption. For
804/// example, some ill-formed data can be constructed to form a cycle using
805/// Sub-Tries and it can lead to inifinite loop when visiting (or inserting
806/// data).
807class TrieVisitor {
808public:
809 TrieVisitor(TrieRawHashMapHandle Trie, unsigned ThreadCount = 0,
810 unsigned ErrorLimit = 50)
811 : Trie(Trie), ErrorLimit(ErrorLimit),
813 virtual ~TrieVisitor() = default;
814 Error visit();
815
816private:
817 // Virtual method to implement the action when visiting a sub-trie.
818 virtual Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) {
819 return Error::success();
820 }
821
822 // Virtual method to implement the action when visiting a slot in a trie node.
823 virtual Error visitSlot(unsigned I, SubtrieHandle Subtrie, StringRef Prefix,
824 SubtrieSlotValue Slot) {
825 return Error::success();
826 }
827
828protected:
829 TrieRawHashMapHandle Trie;
830
831private:
832 Error traverseTrieNode(SubtrieHandle Node, StringRef Prefix);
833
834 Error validateSubTrie(SubtrieHandle Node, bool IsRoot);
835
836 // Helper function to capture errors when visiting the trie nodes.
837 void addError(Error NewError) {
838 assert(NewError && "not an error");
839 std::lock_guard<std::mutex> ErrorLock(Lock);
840 if (NumError >= ErrorLimit) {
841 // Too many errors.
842 consumeError(std::move(NewError));
843 return;
844 }
845
846 if (Err)
847 Err = joinErrors(std::move(*Err), std::move(NewError));
848 else
849 Err = std::move(NewError);
850 NumError++;
851 }
852
853 bool tooManyErrors() {
854 std::lock_guard<std::mutex> ErrorLock(Lock);
855 return (bool)Err && NumError >= ErrorLimit;
856 }
857
858 const unsigned ErrorLimit;
859 std::optional<Error> Err;
860 unsigned NumError = 0;
861 std::mutex Lock;
862 DefaultThreadPool Threads;
863};
864
865/// A visitor that traverse and print the Trie.
866class TriePrinter : public TrieVisitor {
867public:
868 TriePrinter(TrieRawHashMapHandle Trie, raw_ostream &OS,
869 function_ref<void(ArrayRef<char>)> PrintRecordData)
870 : TrieVisitor(Trie, /*ThreadCount=*/1), OS(OS),
871 PrintRecordData(PrintRecordData) {}
872
873 Error printRecords() {
874 if (Records.empty())
875 return Error::success();
876
877 OS << "records\n";
878 llvm::sort(Records);
879 for (int64_t Offset : Records) {
880 TrieRawHashMapHandle::RecordData Record =
881 Trie.getRecord(SubtrieSlotValue::getDataOffset(Offset));
882 if (auto Err = printRecord(Record))
883 return Err;
884 }
885 return Error::success();
886 }
887
888 Error printRecord(TrieRawHashMapHandle::RecordData &Record) {
889 OS << "- addr=" << (void *)Record.getFileOffset().get() << " ";
890 if (PrintRecordData) {
891 PrintRecordData(Record.Proxy.Data);
892 } else {
893 OS << "bytes=";
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);
898 }
899 OS << "\n";
900 return Error::success();
901 }
902
903 Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) override {
904 if (Prefix.empty()) {
905 OS << "root";
906 } else {
907 OS << "subtrie=";
908 printPrefix(OS, Prefix);
909 }
910
911 OS << " addr="
912 << (void *)(reinterpret_cast<const char *>(&SubTrie.getHeader()) -
913 Trie.getRegion().data());
914 OS << " num-slots=" << SubTrie.getNumSlots() << "\n";
915 return Error::success();
916 }
917
918 Error visitSlot(unsigned I, SubtrieHandle Subtrie, StringRef Prefix,
919 SubtrieSlotValue Slot) override {
920 OS << "- index=";
921 for (size_t Pad : {10, 100, 1000})
922 if (I < Pad && Subtrie.getNumSlots() >= Pad)
923 OS << "0";
924 OS << I << " ";
925 if (Slot.isSubtrie()) {
926 OS << "addr=" << (void *)Slot.asSubtrie();
927 OS << " subtrie=";
928 printPrefix(OS, Prefix);
929 OS << "\n";
930 return Error::success();
931 }
932 TrieRawHashMapHandle::RecordData Record = Trie.getRecord(Slot);
933 OS << "addr=" << (void *)Record.getFileOffset().get();
934 OS << " content=";
935 Subtrie.printHash(OS, Record.Proxy.Hash);
936 OS << "\n";
937 Records.push_back(Slot.asData());
938 return Error::success();
939 }
940
941private:
942 raw_ostream &OS;
943 function_ref<void(ArrayRef<char>)> PrintRecordData;
945};
946
947/// TrieVerifier that adds additional verification on top of the basic visitor.
948class TrieVerifier : public TrieVisitor {
949public:
950 TrieVerifier(
951 TrieRawHashMapHandle Trie,
952 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>
953 RecordVerifier)
954 : TrieVisitor(Trie), RecordVerifier(RecordVerifier) {}
955
956private:
957 Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) final {
958 return Error::success();
959 }
960
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");
966
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});
972 }
973 return Error::success();
974 }
975
976 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>
977 RecordVerifier;
978};
979} // namespace
980
981Error TrieVisitor::visit() {
982 auto Root = Trie.getRoot();
983 if (!Root)
984 return Error::success();
985
986 if (auto Err = validateSubTrie(Root, /*IsRoot=*/true))
987 return Err;
988
989 if (auto Err = visitSubTrie("", Root))
990 return Err;
991
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);
997 if (!Slot)
998 continue;
999 uint64_t Offset = Slot.isSubtrie() ? Slot.asSubtrie() : Slot.asData();
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);
1006 Subs.push_back(S);
1007 Prefixes.push_back(SubtriePrefix);
1008 }
1009 if (auto Err = visitSlot(I, Root, SubtriePrefix, Slot))
1010 return Err;
1011 }
1012
1013 for (size_t I = 0, E = Subs.size(); I != E; ++I) {
1014 Threads.async(
1015 [&](unsigned Idx) {
1016 // Don't run if there is an error already.
1017 if (tooManyErrors())
1018 return;
1019 if (auto Err = traverseTrieNode(Subs[Idx], Prefixes[Idx]))
1020 addError(std::move(Err));
1021 },
1022 I);
1023 }
1024
1025 Threads.wait();
1026 if (Err)
1027 return std::move(*Err);
1028 return Error::success();
1029}
1030
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");
1037
1038 if (!IsRoot &&
1039 Node.getStartBit() + Node.getNumBits() > Trie.getNumHashBits()) {
1040 return createInvalidTrieError(Offset,
1041 "subtrie represents too many hash bits");
1042 }
1043
1044 if (IsRoot) {
1045 if (Node.getStartBit() != 0)
1046 return createInvalidTrieError(Offset,
1047 "root node doesn't start at 0 index");
1048
1049 return Error::success();
1050 }
1051
1052 if (Node.getNumBits() > Trie.getNumSubtrieBits())
1053 return createInvalidTrieError(Offset, "subtrie has wrong number of slots");
1054
1055 return Error::success();
1056}
1057
1058Error TrieVisitor::traverseTrieNode(SubtrieHandle Node, StringRef Prefix) {
1059 if (auto Err = validateSubTrie(Node, /*IsRoot=*/false))
1060 return Err;
1061
1062 if (auto Err = visitSubTrie(Prefix, Node))
1063 return Err;
1064
1066 SmallVector<std::string> Prefixes;
1067 const size_t NumSlots = Node.getNumSlots();
1068 for (size_t I = 0, E = NumSlots; I != E; ++I) {
1069 SubtrieSlotValue Slot = Node.load(I);
1070 if (!Slot)
1071 continue;
1072 uint64_t Offset = Slot.isSubtrie() ? Slot.asSubtrie() : Slot.asData();
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);
1079 Subs.push_back(S);
1080 Prefixes.push_back(SubtriePrefix);
1081 }
1082 if (auto Err = visitSlot(I, Node, SubtriePrefix, Slot))
1083 return Err;
1084 }
1085 for (size_t I = 0, E = Subs.size(); I != E; ++I)
1086 if (auto Err = traverseTrieNode(Subs[I], Prefixes[I]))
1087 return Err;
1088
1089 return Error::success();
1090}
1091
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";
1097
1098 TriePrinter Printer(*this, OS, PrintRecordData);
1099 if (auto Err = Printer.visit())
1100 OS << "error: " << toString(std::move(Err)) << "\n";
1101
1102 if (auto Err = Printer.printRecords())
1103 OS << "error: " << toString(std::move(Err)) << "\n";
1104
1105 return;
1106}
1107
1108Error TrieRawHashMapHandle::validate(
1110 RecordVerifier) const {
1111 // Use the base TrieVisitor to identify the errors inside trie first.
1112 TrieVisitor BasicVerifier(*this);
1113 if (auto Err = BasicVerifier.visit())
1114 return Err;
1115
1116 // If the trie data structure is sound, do a second pass to verify data and
1117 // verifier function can assume the index is correct. However, there can be
1118 // newly added bad entries that can still produce error.
1119 TrieVerifier Verifier(*this, RecordVerifier);
1120 return Verifier.visit();
1121}
1122
1123#else // !LLVM_ENABLE_ONDISK_CAS
1124
1126
1128OnDiskTrieRawHashMap::create(const Twine &PathTwine, const Twine &TrieNameTwine,
1129 size_t NumHashBits, uint64_t DataSize,
1130 uint64_t MaxFileSize,
1131 std::optional<uint64_t> NewFileInitialSize,
1132 std::optional<size_t> NewTableNumRootBits,
1133 std::optional<size_t> NewTableNumSubtrieBits) {
1134 return createStringError(make_error_code(std::errc::not_supported),
1135 "OnDiskTrieRawHashMap is not supported");
1136}
1137
1140 LazyInsertOnConstructCB OnConstruct,
1141 LazyInsertOnLeakCB OnLeak) {
1142 return createStringError(make_error_code(std::errc::not_supported),
1143 "OnDiskTrieRawHashMap is not supported");
1144}
1145
1148 return createStringError(make_error_code(std::errc::not_supported),
1149 "OnDiskTrieRawHashMap is not supported");
1150}
1151
1156
1158 raw_ostream &OS, function_ref<void(ArrayRef<char>)> PrintRecordData) const {
1159}
1160
1163 RecordVerifier) const {
1164 return createStringError(make_error_code(std::errc::not_supported),
1165 "OnDiskTrieRawHashMap is not supported");
1166}
1167
1168size_t OnDiskTrieRawHashMap::size() const { return 0; }
1169size_t OnDiskTrieRawHashMap::capacity() const { return 0; }
1170
1171#endif // LLVM_ENABLE_ONDISK_CAS
1172
1173OnDiskTrieRawHashMap::OnDiskTrieRawHashMap(std::unique_ptr<ImplType> Impl)
1174 : Impl(std::move(Impl)) {}
1176 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)
Definition Compiler.h:336
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
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 ...
Definition LICM.cpp:1577
#define I(x, y, z)
Definition MD5.cpp:58
#define H(x, y, z)
Definition MD5.cpp:57
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 Split data
This file contains some functions that are useful when dealing with strings.
static RecordT createRecord(const CVSymbol &sym)
static uint32_t getFlags(const Symbol *Sym)
Definition TapiFile.cpp:26
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),...
Definition ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition ArrayRef.h:147
Lightweight error class with error context and mandatory checking.
Definition Error.h:159
static ErrorSuccess success()
Create a success value.
Definition Error.h:336
Tagged union holding either a T or a Error.
Definition Error.h:485
iterator end() const
Definition ArrayRef.h:348
void push_back(const T &Elt)
StringRef - Represent a constant reference to a string, i.e.
Definition StringRef.h:55
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
StringRef toStringRef(SmallVectorImpl< char > &Out) const
This returns the twine as a single StringRef if it can be represented as such.
Definition Twine.h:461
FileOffset is a wrapper around uint64_t to represent the offset of data from the beginning of the fil...
Definition FileOffset.h:24
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.
Definition raw_ostream.h:53
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
Definition RDFGraph.h:381
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,...
Definition Threading.h:185
@ Offset
Definition DWP.cpp:477
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
std::error_code make_error_code(BitcodeError E)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition Alignment.h:134
FunctionAddr VTableAddr uintptr_t uintptr_t DataSize
Definition InstrProf.h:267
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.
Definition Error.h:1305
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
Error joinErrors(Error E1, Error E2)
Concatenate errors.
Definition Error.h:442
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1624
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
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
Definition InstrProf.h:189
@ Sub
Subtraction of integers.
SingleThreadExecutor DefaultThreadPool
Definition ThreadPool.h:250
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)
Definition STLExtras.h:1815
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1847
@ Default
The result values are uniform if and only if all operands are uniform.
Definition Uniformity.h:20
void consumeError(Error Err)
Consume a Error without doing anything.
Definition Error.h:1083
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:870
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:872
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.