1179 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file Implements OnDiskTrieRawHashMap.10///11//===----------------------------------------------------------------------===//12 13#include "llvm/CAS/OnDiskTrieRawHashMap.h"14#include "DatabaseFile.h"15#include "llvm/ADT/StringExtras.h"16#include "llvm/ADT/TrieHashIndexGenerator.h"17#include "llvm/CAS/MappedFileRegionArena.h"18#include "llvm/Config/llvm-config.h"19#include "llvm/Support/ThreadPool.h"20#include "llvm/Support/Threading.h"21#include "llvm/Support/raw_ostream.h"22 23using namespace llvm;24using namespace llvm::cas;25using namespace llvm::cas::ondisk;26 27#if LLVM_ENABLE_ONDISK_CAS28 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 a40/// subtrie (encoded after negation) which is the file offset to another41/// 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: StartBit93/// - 1-bytes: NumBits=lg(num-slots)94/// - 5-bytes: 0-pad95/// - <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: Empty112 /// - positive: RecordOffset113 /// - negative: SubtrieOffset114 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 with143 /// \p NumSubtrieBits.144 ///145 /// \p UnusedSubtrie maintains a 1-item "free" list of unused subtries. If a146 /// new subtrie is created that isn't used because of a lost race, then it If147 /// 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;191 MutableArrayRef<SlotT> Slots;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: NumSubtrieBits204/// - 1-byte: Flags (not used yet)205/// - 2-bytes: NumHashBits206/// - 4-bytes: RecordDataSize (in bytes)207/// - 8-bytes: RootTrieOffset208/// - 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-bit247 /// 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 suspiciously251 /// 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 void297 print(raw_ostream &OS,298 function_ref<void(ArrayRef<char>)> PrintRecordData = nullptr) const;299 300 Error validate(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 namespace317 318struct OnDiskTrieRawHashMap::ImplType {319 DatabaseFile File;320 TrieRawHashMapHandle Trie;321};322 323Expected<SubtrieHandle> SubtrieHandle::create(MappedFileRegionArena &Alloc,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 348Expected<SubtrieHandle>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 368Expected<TrieRawHashMapHandle>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)384 Header{{TableHandle::TableKind::TrieRawHashMap, (uint16_t)Name.size(),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::RecordData407TrieRawHashMapHandle::getRecord(SubtrieSlotValue Offset) {408 char *Begin = Region->data() + Offset.asData();409 OnDiskTrieRawHashMap::ValueProxy Proxy;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 416Expected<TrieRawHashMapHandle::RecordData>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 430Expected<OnDiskTrieRawHashMap::ConstOnDiskPtr>431OnDiskTrieRawHashMap::recoverFromFileOffset(FileOffset Offset) const {432 // Check alignment.433 if (!isAligned(MappedFileRegionArena::getAlign(), Offset.get()))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 Offset441 // 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 ConstOnDiskPtr(D.Proxy, D.getFileOffset());452}453 454OnDiskTrieRawHashMap::ConstOnDiskPtr455OnDiskTrieRawHashMap::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 ConstOnDiskPtr();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 ConstOnDiskPtr();470 471 // Check for an exact match.472 if (V.isData()) {473 TrieRawHashMapHandle::RecordData D = Trie.getRecord(V);474 return D.Proxy.Hash == Hash ? ConstOnDiskPtr(D.Proxy, D.getFileOffset())475 : ConstOnDiskPtr();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::OnDiskPtr>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 OnDiskPtr(NewRecord->Proxy,527 NewRecord->Offset.asDataFileOffset());528 529 // Race means that Existing is no longer empty; fall through...530 }531 532 if (Existing.isSubtrie()) {533 S = SubtrieHandle(Trie.getRegion(), Existing);534 Index = IndexGen.next();535 continue;536 }537 538 // Check for an exact match.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 // Sink the existing content as long as the indexes match.549 for (;;) {550 size_t NextIndex = IndexGen.next();551 size_t NewIndexForExistingContent =552 IndexGen.getCollidingBits(ExistingRecord.Proxy.Hash);553 554 auto Err = S->sink(Index, Existing, Alloc, IndexGen.getNumBits(),555 UnusedSubtrie, NewIndexForExistingContent)556 .moveInto(S);557 if (LLVM_UNLIKELY(Err))558 return std::move(Err);559 Index = NextIndex;560 561 // Found the difference.562 if (NextIndex != NewIndexForExistingContent)563 break;564 }565 }566}567 568Expected<SubtrieHandle> SubtrieHandle::sink(size_t I, SubtrieSlotValue V,569 MappedFileRegionArena &Alloc,570 size_t NumSubtrieBits,571 SubtrieHandle &UnusedSubtrie,572 size_t NewI) {573 std::optional<SubtrieHandle> NewS;574 if (UnusedSubtrie) {575 // Steal UnusedSubtrie and initialize it.576 NewS.emplace();577 std::swap(*NewS, UnusedSubtrie);578 NewS->reinitialize(getStartBit() + getNumBits(), NumSubtrieBits);579 } else {580 // Allocate a new, empty subtrie.581 auto Err = SubtrieHandle::create(Alloc, getStartBit() + getNumBits(),582 NumSubtrieBits)583 .moveInto(NewS);584 if (LLVM_UNLIKELY(Err))585 return std::move(Err);586 }587 588 NewS->store(NewI, V);589 if (compare_exchange_strong(I, V, NewS->getOffset()))590 return *NewS; // Success!591 592 // Raced.593 assert(V.isSubtrie() && "Expected racing sink() to add a subtrie");594 595 // Wipe out the new slot so NewS can be reused and set the out parameter.596 NewS->store(NewI, SubtrieSlotValue());597 UnusedSubtrie = *NewS;598 599 // Return the subtrie added by the concurrent sink() call.600 return SubtrieHandle(Alloc.getRegion(), V);601}602 603void OnDiskTrieRawHashMap::print(604 raw_ostream &OS, function_ref<void(ArrayRef<char>)> PrintRecordData) const {605 Impl->Trie.print(OS, PrintRecordData);606}607 608Error OnDiskTrieRawHashMap::validate(609 function_ref<Error(FileOffset, ConstValueProxy)> RecordVerifier) const {610 return Impl->Trie.validate(RecordVerifier);611}612 613// Helper function that prints hexdigit and have a sub-byte starting position.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, /*LowerCase=*/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 // afb[1c:00*01110*0]def639 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));658 Index >>= 1;659 }660 for (char Ch : llvm::reverse(Bits))661 Prefix += Ch;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, /*LowerCase=*/true);671 Prefix = Prefix.drop_front(4);672 }673 if (!Prefix.empty())674 OS << "[" << Prefix << "]";675}676 677LLVM_DUMP_METHOD void OnDiskTrieRawHashMap::dump() const { print(dbgs()); }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) {683 assert(Value || Default);684 assert(!Default || *Default <= Max);685 if (!Value)686 return *Default;687 688 if (*Value <= Max)689 return *Value;690 return createTableConfigError(691 std::errc::argument_out_of_domain, Path, TableName,692 "invalid " + Label + ": " + Twine(*Value) + " (max: " + Twine(Max) + ")");693}694 695size_t OnDiskTrieRawHashMap::size() const { return Impl->File.size(); }696size_t OnDiskTrieRawHashMap::capacity() const {697 return Impl->File.getRegion().size();698}699 700Expected<OnDiskTrieRawHashMap>701OnDiskTrieRawHashMap::create(const Twine &PathTwine, const Twine &TrieNameTwine,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;708 StringRef Path = PathTwine.toStringRef(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;731 if (Error E =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)739 return createTableConfigError(740 std::errc::argument_out_of_domain, Path, TrieName,741 "invalid hash size: " + Twine(NumHashBits) + " (not byte-aligned)");742 743 // Constructor for if the file doesn't exist.744 auto NewDBConstructor = [&](DatabaseFile &DB) -> Error {745 auto Trie =746 TrieRawHashMapHandle::create(DB.getAlloc(), TrieName, NumRootBits,747 NumSubtrieBits, NumHashBits, DataSize);748 if (LLVM_UNLIKELY(!Trie))749 return Trie.takeError();750 751 return DB.addTable(*Trie);752 };753 754 // Get or create the file.755 Expected<DatabaseFile> File =756 DatabaseFile::create(Path, MaxFileSize, NewDBConstructor);757 if (!File)758 return File.takeError();759 760 // Find the trie and validate it.761 std::optional<TableHandle> Table = File->findTable(TrieName);762 if (!Table)763 return createTableConfigError(std::errc::argument_out_of_domain, Path,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<TrieRawHashMapHandle>();769 assert(Trie && "Already checked the kind");770 771 // Check the hash and data size.772 if (Error E = checkTable("hash size", NumHashBits, Trie.getNumHashBits(),773 Path, TrieName))774 return std::move(E);775 if (Error E = checkTable("data size", DataSize, Trie.getRecordDataSize(),776 Path, TrieName))777 return std::move(E);778 779 // No flags supported right now. Either corrupt, or coming from a future780 // writer.781 if (size_t Flags = Trie.getFlags())782 return createTableConfigError(std::errc::invalid_argument, Path, TrieName,783 "unsupported flags: " + Twine(Flags));784 785 // Success.786 OnDiskTrieRawHashMap::ImplType Impl{DatabaseFile(std::move(*File)), Trie};787 return OnDiskTrieRawHashMap(std::make_unique<ImplType>(std::move(Impl)));788}789 790static Error createInvalidTrieError(uint64_t Offset, const Twine &Msg) {791 return createStringError(make_error_code(std::errc::protocol_error),792 "invalid trie at 0x" +793 utohexstr(Offset, /*LowerCase=*/true) + ": " +794 Msg);795}796 797//===----------------------------------------------------------------------===//798// TrieVisitor data structures.799//===----------------------------------------------------------------------===//800 801namespace {802/// A multi-threaded vistior to traverse the Trie.803///804/// TODO: add more sanity checks that isn't just plain data corruption. For805/// example, some ill-formed data can be constructed to form a cycle using806/// Sub-Tries and it can lead to inifinite loop when visiting (or inserting807/// data).808class TrieVisitor {809public:810 TrieVisitor(TrieRawHashMapHandle Trie, unsigned ThreadCount = 0,811 unsigned ErrorLimit = 50)812 : Trie(Trie), ErrorLimit(ErrorLimit),813 Threads(hardware_concurrency(ThreadCount)) {}814 virtual ~TrieVisitor() = default;815 Error visit();816 817private:818 // Virtual method to implement the action when visiting a sub-trie.819 virtual Error visitSubTrie(StringRef Prefix, SubtrieHandle SubTrie) {820 return Error::success();821 }822 823 // Virtual method to implement the action when visiting a slot in a trie node.824 virtual Error visitSlot(unsigned I, SubtrieHandle Subtrie, StringRef Prefix,825 SubtrieSlotValue Slot) {826 return Error::success();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 // Helper function to capture errors when visiting the trie nodes.838 void addError(Error NewError) {839 assert(NewError && "not an error");840 std::lock_guard<std::mutex> ErrorLock(Lock);841 if (NumError >= ErrorLimit) {842 // Too many errors.843 consumeError(std::move(NewError));844 return;845 }846 847 if (Err)848 Err = joinErrors(std::move(*Err), std::move(NewError));849 else850 Err = std::move(NewError);851 NumError++;852 }853 854 bool tooManyErrors() {855 std::lock_guard<std::mutex> ErrorLock(Lock);856 return (bool)Err && NumError >= ErrorLimit;857 }858 859 const unsigned ErrorLimit;860 std::optional<Error> Err;861 unsigned NumError = 0;862 std::mutex Lock;863 DefaultThreadPool Threads;864};865 866/// A visitor that traverse and print the Trie.867class TriePrinter : public TrieVisitor {868public:869 TriePrinter(TrieRawHashMapHandle Trie, raw_ostream &OS,870 function_ref<void(ArrayRef<char>)> PrintRecordData)871 : TrieVisitor(Trie, /*ThreadCount=*/1), OS(OS),872 PrintRecordData(PrintRecordData) {}873 874 Error printRecords() {875 if (Records.empty())876 return Error::success();877 878 OS << "records\n";879 llvm::sort(Records);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 }886 return Error::success();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";901 return Error::success();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";916 return Error::success();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";931 return Error::success();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";938 Records.push_back(Slot.asData());939 return Error::success();940 }941 942private:943 raw_ostream &OS;944 function_ref<void(ArrayRef<char>)> PrintRecordData;945 SmallVector<int64_t> Records;946};947 948/// TrieVerifier that adds additional verification on top of the basic visitor.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 {959 return Error::success();960 }961 962 Error visitSlot(unsigned I, SubtrieHandle Subtrie, StringRef Prefix,963 SubtrieSlotValue Slot) final {964 if (RecordVerifier && Slot.isData()) {965 if (!isAligned(MappedFileRegionArena::getAlign(), Slot.asData()))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 }974 return Error::success();975 }976 977 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>978 RecordVerifier;979};980} // namespace981 982Error TrieVisitor::visit() {983 auto Root = Trie.getRoot();984 if (!Root)985 return Error::success();986 987 if (auto Err = validateSubTrie(Root, /*IsRoot=*/true))988 return Err;989 990 if (auto Err = visitSubTrie("", Root))991 return Err;992 993 SmallVector<SubtrieHandle> Subs;994 SmallVector<std::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);1007 Subs.push_back(S);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 // Don't run if there is an error already.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);1029 return Error::success();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 1050 return Error::success();1051 }1052 1053 if (Node.getNumBits() > Trie.getNumSubtrieBits())1054 return createInvalidTrieError(Offset, "subtrie has wrong number of slots");1055 1056 return Error::success();1057}1058 1059Error TrieVisitor::traverseTrieNode(SubtrieHandle Node, StringRef Prefix) {1060 if (auto Err = validateSubTrie(Node, /*IsRoot=*/false))1061 return Err;1062 1063 if (auto Err = visitSubTrie(Prefix, Node))1064 return Err;1065 1066 SmallVector<SubtrieHandle> Subs;1067 SmallVector<std::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);1080 Subs.push_back(S);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 1090 return Error::success();1091}1092 1093void TrieRawHashMapHandle::print(1094 raw_ostream &OS, function_ref<void(ArrayRef<char>)> 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(1108 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>1109 RecordVerifier) const {1110 // Use the base TrieVisitor to identify the errors inside trie first.1111 TrieVisitor BasicVerifier(*this);1112 if (auto Err = BasicVerifier.visit())1113 return Err;1114 1115 // If the trie data structure is sound, do a second pass to verify data and1116 // verifier function can assume the index is correct. However, there can be1117 // newly added bad entries that can still produce error.1118 TrieVerifier Verifier(*this, RecordVerifier);1119 return Verifier.visit();1120}1121 1122#else // !LLVM_ENABLE_ONDISK_CAS1123 1124struct OnDiskTrieRawHashMap::ImplType {};1125 1126Expected<OnDiskTrieRawHashMap>1127OnDiskTrieRawHashMap::create(const Twine &PathTwine, const Twine &TrieNameTwine,1128 size_t NumHashBits, uint64_t DataSize,1129 uint64_t MaxFileSize,1130 std::optional<uint64_t> NewFileInitialSize,1131 std::optional<size_t> NewTableNumRootBits,1132 std::optional<size_t> NewTableNumSubtrieBits) {1133 return createStringError(make_error_code(std::errc::not_supported),1134 "OnDiskTrieRawHashMap is not supported");1135}1136 1137Expected<OnDiskTrieRawHashMap::OnDiskPtr>1138OnDiskTrieRawHashMap::insertLazy(ArrayRef<uint8_t> Hash,1139 LazyInsertOnConstructCB OnConstruct,1140 LazyInsertOnLeakCB OnLeak) {1141 return createStringError(make_error_code(std::errc::not_supported),1142 "OnDiskTrieRawHashMap is not supported");1143}1144 1145Expected<OnDiskTrieRawHashMap::ConstOnDiskPtr>1146OnDiskTrieRawHashMap::recoverFromFileOffset(FileOffset Offset) const {1147 return createStringError(make_error_code(std::errc::not_supported),1148 "OnDiskTrieRawHashMap is not supported");1149}1150 1151OnDiskTrieRawHashMap::ConstOnDiskPtr1152OnDiskTrieRawHashMap::find(ArrayRef<uint8_t> Hash) const {1153 return ConstOnDiskPtr();1154}1155 1156void OnDiskTrieRawHashMap::print(1157 raw_ostream &OS, function_ref<void(ArrayRef<char>)> PrintRecordData) const {1158}1159 1160Error OnDiskTrieRawHashMap::validate(1161 function_ref<Error(FileOffset, OnDiskTrieRawHashMap::ConstValueProxy)>1162 RecordVerifier) const {1163 return createStringError(make_error_code(std::errc::not_supported),1164 "OnDiskTrieRawHashMap is not supported");1165}1166 1167size_t OnDiskTrieRawHashMap::size() const { return 0; }1168size_t OnDiskTrieRawHashMap::capacity() const { return 0; }1169 1170#endif // LLVM_ENABLE_ONDISK_CAS1171 1172OnDiskTrieRawHashMap::OnDiskTrieRawHashMap(std::unique_ptr<ImplType> Impl)1173 : Impl(std::move(Impl)) {}1174OnDiskTrieRawHashMap::OnDiskTrieRawHashMap(OnDiskTrieRawHashMap &&RHS) =1175 default;1176OnDiskTrieRawHashMap &1177OnDiskTrieRawHashMap::operator=(OnDiskTrieRawHashMap &&RHS) = default;1178OnDiskTrieRawHashMap::~OnDiskTrieRawHashMap() = default;1179