1746 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/// \file10/// This file implements OnDiskGraphDB, an on-disk CAS nodes database,11/// independent of a particular hashing algorithm. It only needs to be12/// configured for the hash size and controls the schema of the storage.13///14/// OnDiskGraphDB defines:15///16/// - How the data is stored inside database, either as a standalone file, or17/// allocated inside a datapool.18/// - How references to other objects inside the same database is stored. They19/// are stored as internal references, instead of full hash value to save20/// space.21/// - How to chain databases together and import objects from upstream22/// databases.23///24/// Here's a top-level description of the current layout:25///26/// - db/index.<version>: a file for the "index" table, named by \a27/// IndexTableName and managed by \a TrieRawHashMap. The contents are 8B28/// that are accessed atomically, describing the object kind and where/how29/// it's stored (including an optional file offset). See \a TrieRecord for30/// more details.31/// - db/data.<version>: a file for the "data" table, named by \a32/// DataPoolTableName and managed by \a DataStore. New objects within33/// TrieRecord::MaxEmbeddedSize are inserted here as \a34/// TrieRecord::StorageKind::DataPool.35/// - db/obj.<offset>.<version>: a file storing an object outside the main36/// "data" table, named by its offset into the "index" table, with the37/// format of \a TrieRecord::StorageKind::Standalone.38/// - db/leaf.<offset>.<version>: a file storing a leaf node outside the39/// main "data" table, named by its offset into the "index" table, with40/// the format of \a TrieRecord::StorageKind::StandaloneLeaf.41/// - db/leaf+0.<offset>.<version>: a file storing a null-terminated leaf object42/// outside the main "data" table, named by its offset into the "index" table,43/// with the format of \a TrieRecord::StorageKind::StandaloneLeaf0.44//45//===----------------------------------------------------------------------===//46 47#include "llvm/CAS/OnDiskGraphDB.h"48#include "OnDiskCommon.h"49#include "llvm/ADT/DenseMap.h"50#include "llvm/ADT/ScopeExit.h"51#include "llvm/ADT/StringExtras.h"52#include "llvm/CAS/OnDiskDataAllocator.h"53#include "llvm/CAS/OnDiskTrieRawHashMap.h"54#include "llvm/Support/Alignment.h"55#include "llvm/Support/Compiler.h"56#include "llvm/Support/Errc.h"57#include "llvm/Support/Error.h"58#include "llvm/Support/ErrorHandling.h"59#include "llvm/Support/FileSystem.h"60#include "llvm/Support/MemoryBuffer.h"61#include "llvm/Support/Path.h"62#include "llvm/Support/Process.h"63#include <atomic>64#include <mutex>65#include <optional>66 67#define DEBUG_TYPE "on-disk-cas"68 69using namespace llvm;70using namespace llvm::cas;71using namespace llvm::cas::ondisk;72 73static constexpr StringLiteral IndexTableName = "llvm.cas.index";74static constexpr StringLiteral DataPoolTableName = "llvm.cas.data";75 76static constexpr StringLiteral IndexFilePrefix = "index.";77static constexpr StringLiteral DataPoolFilePrefix = "data.";78 79static constexpr StringLiteral FilePrefixObject = "obj.";80static constexpr StringLiteral FilePrefixLeaf = "leaf.";81static constexpr StringLiteral FilePrefixLeaf0 = "leaf+0.";82 83static Error createCorruptObjectError(Expected<ArrayRef<uint8_t>> ID) {84 if (!ID)85 return ID.takeError();86 87 return createStringError(llvm::errc::invalid_argument,88 "corrupt object '" + toHex(*ID) + "'");89}90 91namespace {92 93/// Trie record data: 8 bytes, atomic<uint64_t>94/// - 1-byte: StorageKind95/// - 7-bytes: DataStoreOffset (offset into referenced file)96class TrieRecord {97public:98 enum class StorageKind : uint8_t {99 /// Unknown object.100 Unknown = 0,101 102 /// data.vX: main pool, full DataStore record.103 DataPool = 1,104 105 /// obj.<TrieRecordOffset>.vX: standalone, with a full DataStore record.106 Standalone = 10,107 108 /// leaf.<TrieRecordOffset>.vX: standalone, just the data. File contents109 /// exactly the data content and file size matches the data size. No refs.110 StandaloneLeaf = 11,111 112 /// leaf+0.<TrieRecordOffset>.vX: standalone, just the data plus an113 /// extra null character ('\0'). File size is 1 bigger than the data size.114 /// No refs.115 StandaloneLeaf0 = 12,116 };117 118 static StringRef getStandaloneFilePrefix(StorageKind SK) {119 switch (SK) {120 default:121 llvm_unreachable("Expected standalone storage kind");122 case TrieRecord::StorageKind::Standalone:123 return FilePrefixObject;124 case TrieRecord::StorageKind::StandaloneLeaf:125 return FilePrefixLeaf;126 case TrieRecord::StorageKind::StandaloneLeaf0:127 return FilePrefixLeaf0;128 }129 }130 131 enum Limits : int64_t {132 /// Saves files bigger than 64KB standalone instead of embedding them.133 MaxEmbeddedSize = 64LL * 1024LL - 1,134 };135 136 struct Data {137 StorageKind SK = StorageKind::Unknown;138 FileOffset Offset;139 };140 141 /// Pack StorageKind and Offset from Data into 8 byte TrieRecord.142 static uint64_t pack(Data D) {143 assert(D.Offset.get() < (int64_t)(1ULL << 56));144 uint64_t Packed = uint64_t(D.SK) << 56 | D.Offset.get();145 assert(D.SK != StorageKind::Unknown || Packed == 0);146#ifndef NDEBUG147 Data RoundTrip = unpack(Packed);148 assert(D.SK == RoundTrip.SK);149 assert(D.Offset.get() == RoundTrip.Offset.get());150#endif151 return Packed;152 }153 154 // Unpack TrieRecord into Data.155 static Data unpack(uint64_t Packed) {156 Data D;157 if (!Packed)158 return D;159 D.SK = (StorageKind)(Packed >> 56);160 D.Offset = FileOffset(Packed & (UINT64_MAX >> 8));161 return D;162 }163 164 TrieRecord() : Storage(0) {}165 166 Data load() const { return unpack(Storage); }167 bool compare_exchange_strong(Data &Existing, Data New);168 169private:170 std::atomic<uint64_t> Storage;171};172 173/// DataStore record data: 4B + size? + refs? + data + 0174/// - 4-bytes: Header175/// - {0,4,8}-bytes: DataSize (may be packed in Header)176/// - {0,4,8}-bytes: NumRefs (may be packed in Header)177/// - NumRefs*{4,8}-bytes: Refs[] (end-ptr is 8-byte aligned)178/// - <data>179/// - 1-byte: 0-term180struct DataRecordHandle {181 /// NumRefs storage: 4B, 2B, 1B, or 0B (no refs). Or, 8B, for alignment182 /// convenience to avoid computing padding later.183 enum class NumRefsFlags : uint8_t {184 Uses0B = 0U,185 Uses1B = 1U,186 Uses2B = 2U,187 Uses4B = 3U,188 Uses8B = 4U,189 Max = Uses8B,190 };191 192 /// DataSize storage: 8B, 4B, 2B, or 1B.193 enum class DataSizeFlags {194 Uses1B = 0U,195 Uses2B = 1U,196 Uses4B = 2U,197 Uses8B = 3U,198 Max = Uses8B,199 };200 201 /// Kind of ref stored in Refs[]: InternalRef or InternalRef4B.202 enum class RefKindFlags {203 InternalRef = 0U,204 InternalRef4B = 1U,205 Max = InternalRef4B,206 };207 208 enum Counts : int {209 NumRefsShift = 0,210 NumRefsBits = 3,211 DataSizeShift = NumRefsShift + NumRefsBits,212 DataSizeBits = 2,213 RefKindShift = DataSizeShift + DataSizeBits,214 RefKindBits = 1,215 };216 static_assert(((UINT32_MAX << NumRefsBits) & (uint32_t)NumRefsFlags::Max) ==217 0,218 "Not enough bits");219 static_assert(((UINT32_MAX << DataSizeBits) & (uint32_t)DataSizeFlags::Max) ==220 0,221 "Not enough bits");222 static_assert(((UINT32_MAX << RefKindBits) & (uint32_t)RefKindFlags::Max) ==223 0,224 "Not enough bits");225 226 /// Layout of the DataRecordHandle and how to decode it.227 struct LayoutFlags {228 NumRefsFlags NumRefs;229 DataSizeFlags DataSize;230 RefKindFlags RefKind;231 232 static uint64_t pack(LayoutFlags LF) {233 unsigned Packed = ((unsigned)LF.NumRefs << NumRefsShift) |234 ((unsigned)LF.DataSize << DataSizeShift) |235 ((unsigned)LF.RefKind << RefKindShift);236#ifndef NDEBUG237 LayoutFlags RoundTrip = unpack(Packed);238 assert(LF.NumRefs == RoundTrip.NumRefs);239 assert(LF.DataSize == RoundTrip.DataSize);240 assert(LF.RefKind == RoundTrip.RefKind);241#endif242 return Packed;243 }244 static LayoutFlags unpack(uint64_t Storage) {245 assert(Storage <= UINT8_MAX && "Expect storage to fit in a byte");246 LayoutFlags LF;247 LF.NumRefs =248 (NumRefsFlags)((Storage >> NumRefsShift) & ((1U << NumRefsBits) - 1));249 LF.DataSize = (DataSizeFlags)((Storage >> DataSizeShift) &250 ((1U << DataSizeBits) - 1));251 LF.RefKind =252 (RefKindFlags)((Storage >> RefKindShift) & ((1U << RefKindBits) - 1));253 return LF;254 }255 };256 257 /// Header layout:258 /// - 1-byte: LayoutFlags259 /// - 1-byte: 1B size field260 /// - {0,2}-bytes: 2B size field261 struct Header {262 using PackTy = uint32_t;263 PackTy Packed;264 265 static constexpr unsigned LayoutFlagsShift =266 (sizeof(PackTy) - 1) * CHAR_BIT;267 };268 269 struct Input {270 InternalRefArrayRef Refs;271 ArrayRef<char> Data;272 };273 274 LayoutFlags getLayoutFlags() const {275 return LayoutFlags::unpack(H->Packed >> Header::LayoutFlagsShift);276 }277 278 uint64_t getDataSize() const;279 void skipDataSize(LayoutFlags LF, int64_t &RelOffset) const;280 uint32_t getNumRefs() const;281 void skipNumRefs(LayoutFlags LF, int64_t &RelOffset) const;282 int64_t getRefsRelOffset() const;283 int64_t getDataRelOffset() const;284 285 static uint64_t getTotalSize(uint64_t DataRelOffset, uint64_t DataSize) {286 return DataRelOffset + DataSize + 1;287 }288 uint64_t getTotalSize() const {289 return getDataRelOffset() + getDataSize() + 1;290 }291 292 /// Describe the layout of data stored and how to decode from293 /// DataRecordHandle.294 struct Layout {295 explicit Layout(const Input &I);296 297 LayoutFlags Flags;298 uint64_t DataSize = 0;299 uint32_t NumRefs = 0;300 int64_t RefsRelOffset = 0;301 int64_t DataRelOffset = 0;302 uint64_t getTotalSize() const {303 return DataRecordHandle::getTotalSize(DataRelOffset, DataSize);304 }305 };306 307 InternalRefArrayRef getRefs() const {308 assert(H && "Expected valid handle");309 auto *BeginByte = reinterpret_cast<const char *>(H) + getRefsRelOffset();310 size_t Size = getNumRefs();311 if (!Size)312 return InternalRefArrayRef();313 if (getLayoutFlags().RefKind == RefKindFlags::InternalRef4B)314 return ArrayRef(reinterpret_cast<const InternalRef4B *>(BeginByte), Size);315 return ArrayRef(reinterpret_cast<const InternalRef *>(BeginByte), Size);316 }317 318 ArrayRef<char> getData() const {319 assert(H && "Expected valid handle");320 return ArrayRef(reinterpret_cast<const char *>(H) + getDataRelOffset(),321 getDataSize());322 }323 324 static DataRecordHandle create(function_ref<char *(size_t Size)> Alloc,325 const Input &I);326 static Expected<DataRecordHandle>327 createWithError(function_ref<Expected<char *>(size_t Size)> Alloc,328 const Input &I);329 static DataRecordHandle construct(char *Mem, const Input &I);330 331 static DataRecordHandle get(const char *Mem) {332 return DataRecordHandle(333 *reinterpret_cast<const DataRecordHandle::Header *>(Mem));334 }335 static Expected<DataRecordHandle>336 getFromDataPool(const OnDiskDataAllocator &Pool, FileOffset Offset);337 338 explicit operator bool() const { return H; }339 const Header &getHeader() const { return *H; }340 341 DataRecordHandle() = default;342 explicit DataRecordHandle(const Header &H) : H(&H) {}343 344private:345 static DataRecordHandle constructImpl(char *Mem, const Input &I,346 const Layout &L);347 const Header *H = nullptr;348};349 350/// Proxy for any on-disk object or raw data.351struct OnDiskContent {352 std::optional<DataRecordHandle> Record;353 std::optional<ArrayRef<char>> Bytes;354};355 356/// Data loaded inside the memory from standalone file.357class StandaloneDataInMemory {358public:359 OnDiskContent getContent() const;360 361 StandaloneDataInMemory(std::unique_ptr<sys::fs::mapped_file_region> Region,362 TrieRecord::StorageKind SK)363 : Region(std::move(Region)), SK(SK) {364#ifndef NDEBUG365 bool IsStandalone = false;366 switch (SK) {367 case TrieRecord::StorageKind::Standalone:368 case TrieRecord::StorageKind::StandaloneLeaf:369 case TrieRecord::StorageKind::StandaloneLeaf0:370 IsStandalone = true;371 break;372 default:373 break;374 }375 assert(IsStandalone);376#endif377 }378 379private:380 std::unique_ptr<sys::fs::mapped_file_region> Region;381 TrieRecord::StorageKind SK;382};383 384/// Container to lookup loaded standalone objects.385template <size_t NumShards> class StandaloneDataMap {386 static_assert(isPowerOf2_64(NumShards), "Expected power of 2");387 388public:389 uintptr_t insert(ArrayRef<uint8_t> Hash, TrieRecord::StorageKind SK,390 std::unique_ptr<sys::fs::mapped_file_region> Region);391 392 const StandaloneDataInMemory *lookup(ArrayRef<uint8_t> Hash) const;393 bool count(ArrayRef<uint8_t> Hash) const { return bool(lookup(Hash)); }394 395private:396 struct Shard {397 /// Needs to store a std::unique_ptr for a stable address identity.398 DenseMap<const uint8_t *, std::unique_ptr<StandaloneDataInMemory>> Map;399 mutable std::mutex Mutex;400 };401 Shard &getShard(ArrayRef<uint8_t> Hash) {402 return const_cast<Shard &>(403 const_cast<const StandaloneDataMap *>(this)->getShard(Hash));404 }405 const Shard &getShard(ArrayRef<uint8_t> Hash) const {406 static_assert(NumShards <= 256, "Expected only 8 bits of shard");407 return Shards[Hash[0] % NumShards];408 }409 410 Shard Shards[NumShards];411};412 413using StandaloneDataMapTy = StandaloneDataMap<16>;414 415/// A vector of internal node references.416class InternalRefVector {417public:418 void push_back(InternalRef Ref) {419 if (NeedsFull)420 return FullRefs.push_back(Ref);421 if (std::optional<InternalRef4B> Small = InternalRef4B::tryToShrink(Ref))422 return SmallRefs.push_back(*Small);423 NeedsFull = true;424 assert(FullRefs.empty());425 FullRefs.reserve(SmallRefs.size() + 1);426 for (InternalRef4B Small : SmallRefs)427 FullRefs.push_back(Small);428 FullRefs.push_back(Ref);429 SmallRefs.clear();430 }431 432 operator InternalRefArrayRef() const {433 assert(SmallRefs.empty() || FullRefs.empty());434 return NeedsFull ? InternalRefArrayRef(FullRefs)435 : InternalRefArrayRef(SmallRefs);436 }437 438private:439 bool NeedsFull = false;440 SmallVector<InternalRef4B> SmallRefs;441 SmallVector<InternalRef> FullRefs;442};443 444} // namespace445 446Expected<DataRecordHandle> DataRecordHandle::createWithError(447 function_ref<Expected<char *>(size_t Size)> Alloc, const Input &I) {448 Layout L(I);449 if (Expected<char *> Mem = Alloc(L.getTotalSize()))450 return constructImpl(*Mem, I, L);451 else452 return Mem.takeError();453}454 455ObjectHandle ObjectHandle::fromFileOffset(FileOffset Offset) {456 // Store the file offset as it is.457 assert(!(Offset.get() & 0x1));458 return ObjectHandle(Offset.get());459}460 461ObjectHandle ObjectHandle::fromMemory(uintptr_t Ptr) {462 // Store the pointer from memory with lowest bit set.463 assert(!(Ptr & 0x1));464 return ObjectHandle(Ptr | 1);465}466 467/// Proxy for an on-disk index record.468struct OnDiskGraphDB::IndexProxy {469 FileOffset Offset;470 ArrayRef<uint8_t> Hash;471 TrieRecord &Ref;472};473 474template <size_t N>475uintptr_t StandaloneDataMap<N>::insert(476 ArrayRef<uint8_t> Hash, TrieRecord::StorageKind SK,477 std::unique_ptr<sys::fs::mapped_file_region> Region) {478 auto &S = getShard(Hash);479 std::lock_guard<std::mutex> Lock(S.Mutex);480 auto &V = S.Map[Hash.data()];481 if (!V)482 V = std::make_unique<StandaloneDataInMemory>(std::move(Region), SK);483 return reinterpret_cast<uintptr_t>(V.get());484}485 486template <size_t N>487const StandaloneDataInMemory *488StandaloneDataMap<N>::lookup(ArrayRef<uint8_t> Hash) const {489 auto &S = getShard(Hash);490 std::lock_guard<std::mutex> Lock(S.Mutex);491 auto I = S.Map.find(Hash.data());492 if (I == S.Map.end())493 return nullptr;494 return &*I->second;495}496 497namespace {498 499/// Copy of \a sys::fs::TempFile that skips RemoveOnSignal, which is too500/// expensive to register/unregister at this rate.501///502/// FIXME: Add a TempFileManager that maintains a thread-safe list of open temp503/// files and has a signal handler registerd that removes them all.504class TempFile {505 bool Done = false;506 TempFile(StringRef Name, int FD) : TmpName(std::string(Name)), FD(FD) {}507 508public:509 /// This creates a temporary file with createUniqueFile.510 static Expected<TempFile> create(const Twine &Model);511 TempFile(TempFile &&Other) { *this = std::move(Other); }512 TempFile &operator=(TempFile &&Other) {513 TmpName = std::move(Other.TmpName);514 FD = Other.FD;515 Other.Done = true;516 Other.FD = -1;517 return *this;518 }519 520 // Name of the temporary file.521 std::string TmpName;522 523 // The open file descriptor.524 int FD = -1;525 526 // Keep this with the given name.527 Error keep(const Twine &Name);528 Error discard();529 530 // This checks that keep or delete was called.531 ~TempFile() { consumeError(discard()); }532};533 534class MappedTempFile {535public:536 char *data() const { return Map.data(); }537 size_t size() const { return Map.size(); }538 539 Error discard() {540 assert(Map && "Map already destroyed");541 Map.unmap();542 return Temp.discard();543 }544 545 Error keep(const Twine &Name) {546 assert(Map && "Map already destroyed");547 Map.unmap();548 return Temp.keep(Name);549 }550 551 MappedTempFile(TempFile Temp, sys::fs::mapped_file_region Map)552 : Temp(std::move(Temp)), Map(std::move(Map)) {}553 554private:555 TempFile Temp;556 sys::fs::mapped_file_region Map;557};558} // namespace559 560Error TempFile::discard() {561 Done = true;562 if (FD != -1) {563 sys::fs::file_t File = sys::fs::convertFDToNativeFile(FD);564 if (std::error_code EC = sys::fs::closeFile(File))565 return errorCodeToError(EC);566 }567 FD = -1;568 569 // Always try to close and remove.570 std::error_code RemoveEC;571 if (!TmpName.empty()) {572 std::error_code EC = sys::fs::remove(TmpName);573 if (EC)574 return errorCodeToError(EC);575 }576 TmpName = "";577 578 return Error::success();579}580 581Error TempFile::keep(const Twine &Name) {582 assert(!Done);583 Done = true;584 // Always try to close and rename.585 std::error_code RenameEC = sys::fs::rename(TmpName, Name);586 587 if (!RenameEC)588 TmpName = "";589 590 sys::fs::file_t File = sys::fs::convertFDToNativeFile(FD);591 if (std::error_code EC = sys::fs::closeFile(File))592 return errorCodeToError(EC);593 FD = -1;594 595 return errorCodeToError(RenameEC);596}597 598Expected<TempFile> TempFile::create(const Twine &Model) {599 int FD;600 SmallString<128> ResultPath;601 if (std::error_code EC = sys::fs::createUniqueFile(Model, FD, ResultPath))602 return errorCodeToError(EC);603 604 TempFile Ret(ResultPath, FD);605 return std::move(Ret);606}607 608bool TrieRecord::compare_exchange_strong(Data &Existing, Data New) {609 uint64_t ExistingPacked = pack(Existing);610 uint64_t NewPacked = pack(New);611 if (Storage.compare_exchange_strong(ExistingPacked, NewPacked))612 return true;613 Existing = unpack(ExistingPacked);614 return false;615}616 617Expected<DataRecordHandle>618DataRecordHandle::getFromDataPool(const OnDiskDataAllocator &Pool,619 FileOffset Offset) {620 auto HeaderData = Pool.get(Offset, sizeof(DataRecordHandle::Header));621 if (!HeaderData)622 return HeaderData.takeError();623 624 auto Record = DataRecordHandle::get(HeaderData->data());625 if (Record.getTotalSize() + Offset.get() > Pool.size())626 return createStringError(627 make_error_code(std::errc::illegal_byte_sequence),628 "data record span passed the end of the data pool");629 630 return Record;631}632 633DataRecordHandle DataRecordHandle::constructImpl(char *Mem, const Input &I,634 const Layout &L) {635 char *Next = Mem + sizeof(Header);636 637 // Fill in Packed and set other data, then come back to construct the header.638 Header::PackTy Packed = 0;639 Packed |= LayoutFlags::pack(L.Flags) << Header::LayoutFlagsShift;640 641 // Construct DataSize.642 switch (L.Flags.DataSize) {643 case DataSizeFlags::Uses1B:644 assert(I.Data.size() <= UINT8_MAX);645 Packed |= (Header::PackTy)I.Data.size()646 << ((sizeof(Packed) - 2) * CHAR_BIT);647 break;648 case DataSizeFlags::Uses2B:649 assert(I.Data.size() <= UINT16_MAX);650 Packed |= (Header::PackTy)I.Data.size()651 << ((sizeof(Packed) - 4) * CHAR_BIT);652 break;653 case DataSizeFlags::Uses4B:654 support::endian::write32le(Next, I.Data.size());655 Next += 4;656 break;657 case DataSizeFlags::Uses8B:658 support::endian::write64le(Next, I.Data.size());659 Next += 8;660 break;661 }662 663 // Construct NumRefs.664 //665 // NOTE: May be writing NumRefs even if there are zero refs in order to fix666 // alignment.667 switch (L.Flags.NumRefs) {668 case NumRefsFlags::Uses0B:669 break;670 case NumRefsFlags::Uses1B:671 assert(I.Refs.size() <= UINT8_MAX);672 Packed |= (Header::PackTy)I.Refs.size()673 << ((sizeof(Packed) - 2) * CHAR_BIT);674 break;675 case NumRefsFlags::Uses2B:676 assert(I.Refs.size() <= UINT16_MAX);677 Packed |= (Header::PackTy)I.Refs.size()678 << ((sizeof(Packed) - 4) * CHAR_BIT);679 break;680 case NumRefsFlags::Uses4B:681 support::endian::write32le(Next, I.Refs.size());682 Next += 4;683 break;684 case NumRefsFlags::Uses8B:685 support::endian::write64le(Next, I.Refs.size());686 Next += 8;687 break;688 }689 690 // Construct Refs[].691 if (!I.Refs.empty()) {692 assert((L.Flags.RefKind == RefKindFlags::InternalRef4B) == I.Refs.is4B());693 ArrayRef<uint8_t> RefsBuffer = I.Refs.getBuffer();694 llvm::copy(RefsBuffer, Next);695 Next += RefsBuffer.size();696 }697 698 // Construct Data and the trailing null.699 assert(isAddrAligned(Align(8), Next));700 llvm::copy(I.Data, Next);701 Next[I.Data.size()] = 0;702 703 // Construct the header itself and return.704 Header *H = new (Mem) Header{Packed};705 DataRecordHandle Record(*H);706 assert(Record.getData() == I.Data);707 assert(Record.getNumRefs() == I.Refs.size());708 assert(Record.getRefs() == I.Refs);709 assert(Record.getLayoutFlags().DataSize == L.Flags.DataSize);710 assert(Record.getLayoutFlags().NumRefs == L.Flags.NumRefs);711 assert(Record.getLayoutFlags().RefKind == L.Flags.RefKind);712 return Record;713}714 715DataRecordHandle::Layout::Layout(const Input &I) {716 // Start initial relative offsets right after the Header.717 uint64_t RelOffset = sizeof(Header);718 719 // Initialize the easy stuff.720 DataSize = I.Data.size();721 NumRefs = I.Refs.size();722 723 // Check refs size.724 Flags.RefKind =725 I.Refs.is4B() ? RefKindFlags::InternalRef4B : RefKindFlags::InternalRef;726 727 // Find the smallest slot available for DataSize.728 bool Has1B = true;729 bool Has2B = true;730 if (DataSize <= UINT8_MAX && Has1B) {731 Flags.DataSize = DataSizeFlags::Uses1B;732 Has1B = false;733 } else if (DataSize <= UINT16_MAX && Has2B) {734 Flags.DataSize = DataSizeFlags::Uses2B;735 Has2B = false;736 } else if (DataSize <= UINT32_MAX) {737 Flags.DataSize = DataSizeFlags::Uses4B;738 RelOffset += 4;739 } else {740 Flags.DataSize = DataSizeFlags::Uses8B;741 RelOffset += 8;742 }743 744 // Find the smallest slot available for NumRefs. Never sets NumRefs8B here.745 if (!NumRefs) {746 Flags.NumRefs = NumRefsFlags::Uses0B;747 } else if (NumRefs <= UINT8_MAX && Has1B) {748 Flags.NumRefs = NumRefsFlags::Uses1B;749 Has1B = false;750 } else if (NumRefs <= UINT16_MAX && Has2B) {751 Flags.NumRefs = NumRefsFlags::Uses2B;752 Has2B = false;753 } else {754 Flags.NumRefs = NumRefsFlags::Uses4B;755 RelOffset += 4;756 }757 758 // Helper to "upgrade" either DataSize or NumRefs by 4B to avoid complicated759 // padding rules when reading and writing. This also bumps RelOffset.760 //761 // The value for NumRefs is strictly limited to UINT32_MAX, but it can be762 // stored as 8B. This means we can *always* find a size to grow.763 //764 // NOTE: Only call this once.765 auto GrowSizeFieldsBy4B = [&]() {766 assert(isAligned(Align(4), RelOffset));767 RelOffset += 4;768 769 assert(Flags.NumRefs != NumRefsFlags::Uses8B &&770 "Expected to be able to grow NumRefs8B");771 772 // First try to grow DataSize. NumRefs will not (yet) be 8B, and if773 // DataSize is upgraded to 8B it'll already be aligned.774 //775 // Failing that, grow NumRefs.776 if (Flags.DataSize < DataSizeFlags::Uses4B)777 Flags.DataSize = DataSizeFlags::Uses4B; // DataSize: Packed => 4B.778 else if (Flags.DataSize < DataSizeFlags::Uses8B)779 Flags.DataSize = DataSizeFlags::Uses8B; // DataSize: 4B => 8B.780 else if (Flags.NumRefs < NumRefsFlags::Uses4B)781 Flags.NumRefs = NumRefsFlags::Uses4B; // NumRefs: Packed => 4B.782 else783 Flags.NumRefs = NumRefsFlags::Uses8B; // NumRefs: 4B => 8B.784 };785 786 assert(isAligned(Align(4), RelOffset));787 if (Flags.RefKind == RefKindFlags::InternalRef) {788 // List of 8B refs should be 8B-aligned. Grow one of the sizes to get this789 // without padding.790 if (!isAligned(Align(8), RelOffset))791 GrowSizeFieldsBy4B();792 793 assert(isAligned(Align(8), RelOffset));794 RefsRelOffset = RelOffset;795 RelOffset += 8 * NumRefs;796 } else {797 // The array of 4B refs doesn't need 8B alignment, but the data will need798 // to be 8B-aligned. Detect this now, and, if necessary, shift everything799 // by 4B by growing one of the sizes.800 // If we remove the need for 8B-alignment for data there is <1% savings in801 // disk storage for a clang build using MCCAS but the 8B-alignment may be802 // useful in the future so keep it for now.803 uint64_t RefListSize = 4 * NumRefs;804 if (!isAligned(Align(8), RelOffset + RefListSize))805 GrowSizeFieldsBy4B();806 RefsRelOffset = RelOffset;807 RelOffset += RefListSize;808 }809 810 assert(isAligned(Align(8), RelOffset));811 DataRelOffset = RelOffset;812}813 814uint64_t DataRecordHandle::getDataSize() const {815 int64_t RelOffset = sizeof(Header);816 auto *DataSizePtr = reinterpret_cast<const char *>(H) + RelOffset;817 switch (getLayoutFlags().DataSize) {818 case DataSizeFlags::Uses1B:819 return (H->Packed >> ((sizeof(Header::PackTy) - 2) * CHAR_BIT)) & UINT8_MAX;820 case DataSizeFlags::Uses2B:821 return (H->Packed >> ((sizeof(Header::PackTy) - 4) * CHAR_BIT)) &822 UINT16_MAX;823 case DataSizeFlags::Uses4B:824 return support::endian::read32le(DataSizePtr);825 case DataSizeFlags::Uses8B:826 return support::endian::read64le(DataSizePtr);827 }828 llvm_unreachable("Unknown DataSizeFlags enum");829}830 831void DataRecordHandle::skipDataSize(LayoutFlags LF, int64_t &RelOffset) const {832 if (LF.DataSize >= DataSizeFlags::Uses4B)833 RelOffset += 4;834 if (LF.DataSize >= DataSizeFlags::Uses8B)835 RelOffset += 4;836}837 838uint32_t DataRecordHandle::getNumRefs() const {839 LayoutFlags LF = getLayoutFlags();840 int64_t RelOffset = sizeof(Header);841 skipDataSize(LF, RelOffset);842 auto *NumRefsPtr = reinterpret_cast<const char *>(H) + RelOffset;843 switch (LF.NumRefs) {844 case NumRefsFlags::Uses0B:845 return 0;846 case NumRefsFlags::Uses1B:847 return (H->Packed >> ((sizeof(Header::PackTy) - 2) * CHAR_BIT)) & UINT8_MAX;848 case NumRefsFlags::Uses2B:849 return (H->Packed >> ((sizeof(Header::PackTy) - 4) * CHAR_BIT)) &850 UINT16_MAX;851 case NumRefsFlags::Uses4B:852 return support::endian::read32le(NumRefsPtr);853 case NumRefsFlags::Uses8B:854 return support::endian::read64le(NumRefsPtr);855 }856 llvm_unreachable("Unknown NumRefsFlags enum");857}858 859void DataRecordHandle::skipNumRefs(LayoutFlags LF, int64_t &RelOffset) const {860 if (LF.NumRefs >= NumRefsFlags::Uses4B)861 RelOffset += 4;862 if (LF.NumRefs >= NumRefsFlags::Uses8B)863 RelOffset += 4;864}865 866int64_t DataRecordHandle::getRefsRelOffset() const {867 LayoutFlags LF = getLayoutFlags();868 int64_t RelOffset = sizeof(Header);869 skipDataSize(LF, RelOffset);870 skipNumRefs(LF, RelOffset);871 return RelOffset;872}873 874int64_t DataRecordHandle::getDataRelOffset() const {875 LayoutFlags LF = getLayoutFlags();876 int64_t RelOffset = sizeof(Header);877 skipDataSize(LF, RelOffset);878 skipNumRefs(LF, RelOffset);879 uint32_t RefSize = LF.RefKind == RefKindFlags::InternalRef4B ? 4 : 8;880 RelOffset += RefSize * getNumRefs();881 return RelOffset;882}883 884Error OnDiskGraphDB::validate(bool Deep, HashingFuncT Hasher) const {885 if (UpstreamDB) {886 if (auto E = UpstreamDB->validate(Deep, Hasher))887 return E;888 }889 return Index.validate([&](FileOffset Offset,890 OnDiskTrieRawHashMap::ConstValueProxy Record)891 -> Error {892 auto formatError = [&](Twine Msg) {893 return createStringError(894 llvm::errc::illegal_byte_sequence,895 "bad record at 0x" +896 utohexstr((unsigned)Offset.get(), /*LowerCase=*/true) + ": " +897 Msg.str());898 };899 900 if (Record.Data.size() != sizeof(TrieRecord))901 return formatError("wrong data record size");902 if (!isAligned(Align::Of<TrieRecord>(), Record.Data.size()))903 return formatError("wrong data record alignment");904 905 auto *R = reinterpret_cast<const TrieRecord *>(Record.Data.data());906 TrieRecord::Data D = R->load();907 std::unique_ptr<MemoryBuffer> FileBuffer;908 if ((uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::Unknown &&909 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::DataPool &&910 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::Standalone &&911 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::StandaloneLeaf &&912 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::StandaloneLeaf0)913 return formatError("invalid record kind value");914 915 auto Ref = InternalRef::getFromOffset(Offset);916 auto I = getIndexProxyFromRef(Ref);917 if (!I)918 return I.takeError();919 920 switch (D.SK) {921 case TrieRecord::StorageKind::Unknown:922 // This could be an abandoned entry due to a termination before updating923 // the record. It can be reused by later insertion so just skip this entry924 // for now.925 return Error::success();926 case TrieRecord::StorageKind::DataPool:927 // Check offset is a postive value, and large enough to hold the928 // header for the data record.929 if (D.Offset.get() <= 0 ||930 D.Offset.get() + sizeof(DataRecordHandle::Header) >= DataPool.size())931 return formatError("datapool record out of bound");932 break;933 case TrieRecord::StorageKind::Standalone:934 case TrieRecord::StorageKind::StandaloneLeaf:935 case TrieRecord::StorageKind::StandaloneLeaf0:936 SmallString<256> Path;937 getStandalonePath(TrieRecord::getStandaloneFilePrefix(D.SK), *I, Path);938 // If need to validate the content of the file later, just load the939 // buffer here. Otherwise, just check the existance of the file.940 if (Deep) {941 auto File = MemoryBuffer::getFile(Path, /*IsText=*/false,942 /*RequiresNullTerminator=*/false);943 if (!File || !*File)944 return formatError("record file \'" + Path + "\' does not exist");945 946 FileBuffer = std::move(*File);947 } else if (!llvm::sys::fs::exists(Path))948 return formatError("record file \'" + Path + "\' does not exist");949 }950 951 if (!Deep)952 return Error::success();953 954 auto dataError = [&](Twine Msg) {955 return createStringError(llvm::errc::illegal_byte_sequence,956 "bad data for digest \'" + toHex(I->Hash) +957 "\': " + Msg.str());958 };959 SmallVector<ArrayRef<uint8_t>> Refs;960 ArrayRef<char> StoredData;961 962 switch (D.SK) {963 case TrieRecord::StorageKind::Unknown:964 llvm_unreachable("already handled");965 case TrieRecord::StorageKind::DataPool: {966 auto DataRecord = DataRecordHandle::getFromDataPool(DataPool, D.Offset);967 if (!DataRecord)968 return dataError(toString(DataRecord.takeError()));969 970 for (auto InternRef : DataRecord->getRefs()) {971 auto Index = getIndexProxyFromRef(InternRef);972 if (!Index)973 return Index.takeError();974 Refs.push_back(Index->Hash);975 }976 StoredData = DataRecord->getData();977 break;978 }979 case TrieRecord::StorageKind::Standalone: {980 if (FileBuffer->getBufferSize() < sizeof(DataRecordHandle::Header))981 return dataError("data record is not big enough to read the header");982 auto DataRecord = DataRecordHandle::get(FileBuffer->getBufferStart());983 if (DataRecord.getTotalSize() < FileBuffer->getBufferSize())984 return dataError(985 "data record span passed the end of the standalone file");986 for (auto InternRef : DataRecord.getRefs()) {987 auto Index = getIndexProxyFromRef(InternRef);988 if (!Index)989 return Index.takeError();990 Refs.push_back(Index->Hash);991 }992 StoredData = DataRecord.getData();993 break;994 }995 case TrieRecord::StorageKind::StandaloneLeaf:996 case TrieRecord::StorageKind::StandaloneLeaf0: {997 StoredData = arrayRefFromStringRef<char>(FileBuffer->getBuffer());998 if (D.SK == TrieRecord::StorageKind::StandaloneLeaf0) {999 if (!FileBuffer->getBuffer().ends_with('\0'))1000 return dataError("standalone file is not zero terminated");1001 StoredData = StoredData.drop_back(1);1002 }1003 break;1004 }1005 }1006 1007 SmallVector<uint8_t> ComputedHash;1008 Hasher(Refs, StoredData, ComputedHash);1009 if (I->Hash != ArrayRef(ComputedHash))1010 return dataError("hash mismatch, got \'" + toHex(ComputedHash) +1011 "\' instead");1012 1013 return Error::success();1014 });1015}1016 1017void OnDiskGraphDB::print(raw_ostream &OS) const {1018 OS << "on-disk-root-path: " << RootPath << "\n";1019 1020 struct PoolInfo {1021 uint64_t Offset;1022 };1023 SmallVector<PoolInfo> Pool;1024 1025 OS << "\n";1026 OS << "index:\n";1027 Index.print(OS, [&](ArrayRef<char> Data) {1028 assert(Data.size() == sizeof(TrieRecord));1029 assert(isAligned(Align::Of<TrieRecord>(), Data.size()));1030 auto *R = reinterpret_cast<const TrieRecord *>(Data.data());1031 TrieRecord::Data D = R->load();1032 OS << " SK=";1033 switch (D.SK) {1034 case TrieRecord::StorageKind::Unknown:1035 OS << "unknown ";1036 break;1037 case TrieRecord::StorageKind::DataPool:1038 OS << "datapool ";1039 Pool.push_back({D.Offset.get()});1040 break;1041 case TrieRecord::StorageKind::Standalone:1042 OS << "standalone-data ";1043 break;1044 case TrieRecord::StorageKind::StandaloneLeaf:1045 OS << "standalone-leaf ";1046 break;1047 case TrieRecord::StorageKind::StandaloneLeaf0:1048 OS << "standalone-leaf+0";1049 break;1050 }1051 OS << " Offset=" << (void *)D.Offset.get();1052 });1053 if (Pool.empty())1054 return;1055 1056 OS << "\n";1057 OS << "pool:\n";1058 llvm::sort(1059 Pool, [](PoolInfo LHS, PoolInfo RHS) { return LHS.Offset < RHS.Offset; });1060 for (PoolInfo PI : Pool) {1061 OS << "- addr=" << (void *)PI.Offset << " ";1062 auto D = DataRecordHandle::getFromDataPool(DataPool, FileOffset(PI.Offset));1063 if (!D) {1064 OS << "error: " << toString(D.takeError());1065 return;1066 }1067 1068 OS << "record refs=" << D->getNumRefs() << " data=" << D->getDataSize()1069 << " size=" << D->getTotalSize()1070 << " end=" << (void *)(PI.Offset + D->getTotalSize()) << "\n";1071 }1072}1073 1074Expected<OnDiskGraphDB::IndexProxy>1075OnDiskGraphDB::indexHash(ArrayRef<uint8_t> Hash) {1076 auto P = Index.insertLazy(1077 Hash, [](FileOffset TentativeOffset,1078 OnDiskTrieRawHashMap::ValueProxy TentativeValue) {1079 assert(TentativeValue.Data.size() == sizeof(TrieRecord));1080 assert(1081 isAddrAligned(Align::Of<TrieRecord>(), TentativeValue.Data.data()));1082 new (TentativeValue.Data.data()) TrieRecord();1083 });1084 if (LLVM_UNLIKELY(!P))1085 return P.takeError();1086 1087 assert(*P && "Expected insertion");1088 return getIndexProxyFromPointer(*P);1089}1090 1091OnDiskGraphDB::IndexProxy OnDiskGraphDB::getIndexProxyFromPointer(1092 OnDiskTrieRawHashMap::ConstOnDiskPtr P) const {1093 assert(P);1094 assert(P.getOffset());1095 return IndexProxy{P.getOffset(), P->Hash,1096 *const_cast<TrieRecord *>(1097 reinterpret_cast<const TrieRecord *>(P->Data.data()))};1098}1099 1100Expected<ObjectID> OnDiskGraphDB::getReference(ArrayRef<uint8_t> Hash) {1101 auto I = indexHash(Hash);1102 if (LLVM_UNLIKELY(!I))1103 return I.takeError();1104 return getExternalReference(*I);1105}1106 1107ObjectID OnDiskGraphDB::getExternalReference(const IndexProxy &I) {1108 return getExternalReference(makeInternalRef(I.Offset));1109}1110 1111std::optional<ObjectID>1112OnDiskGraphDB::getExistingReference(ArrayRef<uint8_t> Digest) {1113 auto tryUpstream =1114 [&](std::optional<IndexProxy> I) -> std::optional<ObjectID> {1115 if (!UpstreamDB)1116 return std::nullopt;1117 std::optional<ObjectID> UpstreamID =1118 UpstreamDB->getExistingReference(Digest);1119 if (LLVM_UNLIKELY(!UpstreamID))1120 return std::nullopt;1121 auto Ref = expectedToOptional(indexHash(Digest));1122 if (!Ref)1123 return std::nullopt;1124 if (!I)1125 I.emplace(*Ref);1126 return getExternalReference(*I);1127 };1128 1129 OnDiskTrieRawHashMap::ConstOnDiskPtr P = Index.find(Digest);1130 if (!P)1131 return tryUpstream(std::nullopt);1132 IndexProxy I = getIndexProxyFromPointer(P);1133 TrieRecord::Data Obj = I.Ref.load();1134 if (Obj.SK == TrieRecord::StorageKind::Unknown)1135 return tryUpstream(I);1136 return getExternalReference(makeInternalRef(I.Offset));1137}1138 1139Expected<OnDiskGraphDB::IndexProxy>1140OnDiskGraphDB::getIndexProxyFromRef(InternalRef Ref) const {1141 auto P = Index.recoverFromFileOffset(Ref.getFileOffset());1142 if (LLVM_UNLIKELY(!P))1143 return P.takeError();1144 return getIndexProxyFromPointer(*P);1145}1146 1147Expected<ArrayRef<uint8_t>> OnDiskGraphDB::getDigest(InternalRef Ref) const {1148 auto I = getIndexProxyFromRef(Ref);1149 if (!I)1150 return I.takeError();1151 return I->Hash;1152}1153 1154ArrayRef<uint8_t> OnDiskGraphDB::getDigest(const IndexProxy &I) const {1155 return I.Hash;1156}1157 1158static OnDiskContent getContentFromHandle(const OnDiskDataAllocator &DataPool,1159 ObjectHandle OH) {1160 // Decode ObjectHandle to locate the stored content.1161 uint64_t Data = OH.getOpaqueData();1162 if (Data & 1) {1163 const auto *SDIM =1164 reinterpret_cast<const StandaloneDataInMemory *>(Data & (-1ULL << 1));1165 return SDIM->getContent();1166 }1167 1168 auto DataHandle =1169 cantFail(DataRecordHandle::getFromDataPool(DataPool, FileOffset(Data)));1170 assert(DataHandle.getData().end()[0] == 0 && "Null termination");1171 return OnDiskContent{DataHandle, std::nullopt};1172}1173 1174ArrayRef<char> OnDiskGraphDB::getObjectData(ObjectHandle Node) const {1175 OnDiskContent Content = getContentFromHandle(DataPool, Node);1176 if (Content.Bytes)1177 return *Content.Bytes;1178 assert(Content.Record && "Expected record or bytes");1179 return Content.Record->getData();1180}1181 1182InternalRefArrayRef OnDiskGraphDB::getInternalRefs(ObjectHandle Node) const {1183 if (std::optional<DataRecordHandle> Record =1184 getContentFromHandle(DataPool, Node).Record)1185 return Record->getRefs();1186 return std::nullopt;1187}1188 1189Expected<std::optional<ObjectHandle>>1190OnDiskGraphDB::load(ObjectID ExternalRef) {1191 InternalRef Ref = getInternalRef(ExternalRef);1192 auto I = getIndexProxyFromRef(Ref);1193 if (!I)1194 return I.takeError();1195 TrieRecord::Data Object = I->Ref.load();1196 1197 if (Object.SK == TrieRecord::StorageKind::Unknown)1198 return faultInFromUpstream(ExternalRef);1199 1200 if (Object.SK == TrieRecord::StorageKind::DataPool)1201 return ObjectHandle::fromFileOffset(Object.Offset);1202 1203 // Only TrieRecord::StorageKind::Standalone (and variants) need to be1204 // explicitly loaded.1205 //1206 // There's corruption if standalone objects have offsets, or if we get here1207 // for something that isn't standalone.1208 if (Object.Offset)1209 return createCorruptObjectError(getDigest(*I));1210 switch (Object.SK) {1211 case TrieRecord::StorageKind::Unknown:1212 case TrieRecord::StorageKind::DataPool:1213 llvm_unreachable("unexpected storage kind");1214 case TrieRecord::StorageKind::Standalone:1215 case TrieRecord::StorageKind::StandaloneLeaf0:1216 case TrieRecord::StorageKind::StandaloneLeaf:1217 break;1218 }1219 1220 // Load it from disk.1221 //1222 // Note: Creation logic guarantees that data that needs null-termination is1223 // suitably 0-padded. Requiring null-termination here would be too expensive1224 // for extremely large objects that happen to be page-aligned.1225 SmallString<256> Path;1226 getStandalonePath(TrieRecord::getStandaloneFilePrefix(Object.SK), *I, Path);1227 1228 auto File = sys::fs::openNativeFileForRead(Path);1229 if (!File)1230 return createFileError(Path, File.takeError());1231 1232 auto CloseFile = make_scope_exit([&]() { sys::fs::closeFile(*File); });1233 1234 sys::fs::file_status Status;1235 if (std::error_code EC = sys::fs::status(*File, Status))1236 return createCorruptObjectError(getDigest(*I));1237 1238 std::error_code EC;1239 auto Region = std::make_unique<sys::fs::mapped_file_region>(1240 *File, sys::fs::mapped_file_region::readonly, Status.getSize(), 0, EC);1241 if (EC)1242 return createCorruptObjectError(getDigest(*I));1243 1244 return ObjectHandle::fromMemory(1245 static_cast<StandaloneDataMapTy *>(StandaloneData)1246 ->insert(I->Hash, Object.SK, std::move(Region)));1247}1248 1249Expected<bool> OnDiskGraphDB::isMaterialized(ObjectID Ref) {1250 auto Presence = getObjectPresence(Ref, /*CheckUpstream=*/true);1251 if (!Presence)1252 return Presence.takeError();1253 1254 switch (*Presence) {1255 case ObjectPresence::Missing:1256 return false;1257 case ObjectPresence::InPrimaryDB:1258 return true;1259 case ObjectPresence::OnlyInUpstreamDB:1260 if (auto FaultInResult = faultInFromUpstream(Ref); !FaultInResult)1261 return FaultInResult.takeError();1262 return true;1263 }1264 llvm_unreachable("Unknown ObjectPresence enum");1265}1266 1267Expected<OnDiskGraphDB::ObjectPresence>1268OnDiskGraphDB::getObjectPresence(ObjectID ExternalRef,1269 bool CheckUpstream) const {1270 InternalRef Ref = getInternalRef(ExternalRef);1271 auto I = getIndexProxyFromRef(Ref);1272 if (!I)1273 return I.takeError();1274 1275 TrieRecord::Data Object = I->Ref.load();1276 if (Object.SK != TrieRecord::StorageKind::Unknown)1277 return ObjectPresence::InPrimaryDB;1278 1279 if (!CheckUpstream || !UpstreamDB)1280 return ObjectPresence::Missing;1281 1282 std::optional<ObjectID> UpstreamID =1283 UpstreamDB->getExistingReference(getDigest(*I));1284 return UpstreamID.has_value() ? ObjectPresence::OnlyInUpstreamDB1285 : ObjectPresence::Missing;1286}1287 1288InternalRef OnDiskGraphDB::makeInternalRef(FileOffset IndexOffset) {1289 return InternalRef::getFromOffset(IndexOffset);1290}1291 1292void OnDiskGraphDB::getStandalonePath(StringRef Prefix, const IndexProxy &I,1293 SmallVectorImpl<char> &Path) const {1294 Path.assign(RootPath.begin(), RootPath.end());1295 sys::path::append(Path,1296 Prefix + Twine(I.Offset.get()) + "." + CASFormatVersion);1297}1298 1299OnDiskContent StandaloneDataInMemory::getContent() const {1300 bool Leaf0 = false;1301 bool Leaf = false;1302 switch (SK) {1303 default:1304 llvm_unreachable("Storage kind must be standalone");1305 case TrieRecord::StorageKind::Standalone:1306 break;1307 case TrieRecord::StorageKind::StandaloneLeaf0:1308 Leaf = Leaf0 = true;1309 break;1310 case TrieRecord::StorageKind::StandaloneLeaf:1311 Leaf = true;1312 break;1313 }1314 1315 if (Leaf) {1316 StringRef Data(Region->data(), Region->size());1317 assert(Data.drop_back(Leaf0).end()[0] == 0 &&1318 "Standalone node data missing null termination");1319 return OnDiskContent{std::nullopt,1320 arrayRefFromStringRef<char>(Data.drop_back(Leaf0))};1321 }1322 1323 DataRecordHandle Record = DataRecordHandle::get(Region->data());1324 assert(Record.getData().end()[0] == 0 &&1325 "Standalone object record missing null termination for data");1326 return OnDiskContent{Record, std::nullopt};1327}1328 1329static Expected<MappedTempFile> createTempFile(StringRef FinalPath,1330 uint64_t Size) {1331 assert(Size && "Unexpected request for an empty temp file");1332 Expected<TempFile> File = TempFile::create(FinalPath + ".%%%%%%");1333 if (!File)1334 return File.takeError();1335 1336 if (Error E = preallocateFileTail(File->FD, 0, Size).takeError())1337 return createFileError(File->TmpName, std::move(E));1338 1339 if (auto EC = sys::fs::resize_file_before_mapping_readwrite(File->FD, Size))1340 return createFileError(File->TmpName, EC);1341 1342 std::error_code EC;1343 sys::fs::mapped_file_region Map(sys::fs::convertFDToNativeFile(File->FD),1344 sys::fs::mapped_file_region::readwrite, Size,1345 0, EC);1346 if (EC)1347 return createFileError(File->TmpName, EC);1348 return MappedTempFile(std::move(*File), std::move(Map));1349}1350 1351static size_t getPageSize() {1352 static int PageSize = sys::Process::getPageSizeEstimate();1353 return PageSize;1354}1355 1356Error OnDiskGraphDB::createStandaloneLeaf(IndexProxy &I, ArrayRef<char> Data) {1357 assert(Data.size() > TrieRecord::MaxEmbeddedSize &&1358 "Expected a bigger file for external content...");1359 1360 bool Leaf0 = isAligned(Align(getPageSize()), Data.size());1361 TrieRecord::StorageKind SK = Leaf0 ? TrieRecord::StorageKind::StandaloneLeaf01362 : TrieRecord::StorageKind::StandaloneLeaf;1363 1364 SmallString<256> Path;1365 int64_t FileSize = Data.size() + Leaf0;1366 getStandalonePath(TrieRecord::getStandaloneFilePrefix(SK), I, Path);1367 1368 // Write the file. Don't reuse this mapped_file_region, which is read/write.1369 // Let load() pull up one that's read-only.1370 Expected<MappedTempFile> File = createTempFile(Path, FileSize);1371 if (!File)1372 return File.takeError();1373 assert(File->size() == (uint64_t)FileSize);1374 llvm::copy(Data, File->data());1375 if (Leaf0)1376 File->data()[Data.size()] = 0;1377 assert(File->data()[Data.size()] == 0);1378 if (Error E = File->keep(Path))1379 return E;1380 1381 // Store the object reference.1382 TrieRecord::Data Existing;1383 {1384 TrieRecord::Data Leaf{SK, FileOffset()};1385 if (I.Ref.compare_exchange_strong(Existing, Leaf)) {1386 recordStandaloneSizeIncrease(FileSize);1387 return Error::success();1388 }1389 }1390 1391 // If there was a race, confirm that the new value has valid storage.1392 if (Existing.SK == TrieRecord::StorageKind::Unknown)1393 return createCorruptObjectError(getDigest(I));1394 1395 return Error::success();1396}1397 1398Error OnDiskGraphDB::store(ObjectID ID, ArrayRef<ObjectID> Refs,1399 ArrayRef<char> Data) {1400 auto I = getIndexProxyFromRef(getInternalRef(ID));1401 if (LLVM_UNLIKELY(!I))1402 return I.takeError();1403 1404 // Early return in case the node exists.1405 {1406 TrieRecord::Data Existing = I->Ref.load();1407 if (Existing.SK != TrieRecord::StorageKind::Unknown)1408 return Error::success();1409 }1410 1411 // Big leaf nodes.1412 if (Refs.empty() && Data.size() > TrieRecord::MaxEmbeddedSize)1413 return createStandaloneLeaf(*I, Data);1414 1415 // TODO: Check whether it's worth checking the index for an already existing1416 // object (like storeTreeImpl() does) before building up the1417 // InternalRefVector.1418 InternalRefVector InternalRefs;1419 for (ObjectID Ref : Refs)1420 InternalRefs.push_back(getInternalRef(Ref));1421 1422 // Create the object.1423 1424 DataRecordHandle::Input Input{InternalRefs, Data};1425 1426 // Compute the storage kind, allocate it, and create the record.1427 TrieRecord::StorageKind SK = TrieRecord::StorageKind::Unknown;1428 FileOffset PoolOffset;1429 SmallString<256> Path;1430 std::optional<MappedTempFile> File;1431 std::optional<uint64_t> FileSize;1432 auto AllocStandaloneFile = [&](size_t Size) -> Expected<char *> {1433 getStandalonePath(TrieRecord::getStandaloneFilePrefix(1434 TrieRecord::StorageKind::Standalone),1435 *I, Path);1436 if (Error E = createTempFile(Path, Size).moveInto(File))1437 return std::move(E);1438 assert(File->size() == Size);1439 FileSize = Size;1440 SK = TrieRecord::StorageKind::Standalone;1441 return File->data();1442 };1443 auto Alloc = [&](size_t Size) -> Expected<char *> {1444 if (Size <= TrieRecord::MaxEmbeddedSize) {1445 SK = TrieRecord::StorageKind::DataPool;1446 auto P = DataPool.allocate(Size);1447 if (LLVM_UNLIKELY(!P)) {1448 char *NewAlloc = nullptr;1449 auto NewE = handleErrors(1450 P.takeError(), [&](std::unique_ptr<StringError> E) -> Error {1451 if (E->convertToErrorCode() == std::errc::not_enough_memory)1452 return AllocStandaloneFile(Size).moveInto(NewAlloc);1453 return Error(std::move(E));1454 });1455 if (!NewE)1456 return NewAlloc;1457 return std::move(NewE);1458 }1459 PoolOffset = P->getOffset();1460 LLVM_DEBUG({1461 dbgs() << "pool-alloc addr=" << (void *)PoolOffset.get()1462 << " size=" << Size1463 << " end=" << (void *)(PoolOffset.get() + Size) << "\n";1464 });1465 return (*P)->data();1466 }1467 return AllocStandaloneFile(Size);1468 };1469 1470 DataRecordHandle Record;1471 if (Error E =1472 DataRecordHandle::createWithError(Alloc, Input).moveInto(Record))1473 return E;1474 assert(Record.getData().end()[0] == 0 && "Expected null-termination");1475 assert(Record.getData() == Input.Data && "Expected initialization");1476 assert(SK != TrieRecord::StorageKind::Unknown);1477 assert(bool(File) != bool(PoolOffset) &&1478 "Expected either a mapped file or a pooled offset");1479 1480 // Check for a race before calling MappedTempFile::keep().1481 //1482 // Then decide what to do with the file. Better to discard than overwrite if1483 // another thread/process has already added this.1484 TrieRecord::Data Existing = I->Ref.load();1485 {1486 TrieRecord::Data NewObject{SK, PoolOffset};1487 if (File) {1488 if (Existing.SK == TrieRecord::StorageKind::Unknown) {1489 // Keep the file!1490 if (Error E = File->keep(Path))1491 return E;1492 } else {1493 File.reset();1494 }1495 }1496 1497 // If we didn't already see a racing/existing write, then try storing the1498 // new object. If that races, confirm that the new value has valid storage.1499 //1500 // TODO: Find a way to reuse the storage from the new-but-abandoned record1501 // handle.1502 if (Existing.SK == TrieRecord::StorageKind::Unknown) {1503 if (I->Ref.compare_exchange_strong(Existing, NewObject)) {1504 if (FileSize)1505 recordStandaloneSizeIncrease(*FileSize);1506 return Error::success();1507 }1508 }1509 }1510 1511 if (Existing.SK == TrieRecord::StorageKind::Unknown)1512 return createCorruptObjectError(getDigest(*I));1513 1514 // Load existing object.1515 return Error::success();1516}1517 1518void OnDiskGraphDB::recordStandaloneSizeIncrease(size_t SizeIncrease) {1519 standaloneStorageSize().fetch_add(SizeIncrease, std::memory_order_relaxed);1520}1521 1522std::atomic<uint64_t> &OnDiskGraphDB::standaloneStorageSize() const {1523 MutableArrayRef<uint8_t> UserHeader = DataPool.getUserHeader();1524 assert(UserHeader.size() == sizeof(std::atomic<uint64_t>));1525 assert(isAddrAligned(Align(8), UserHeader.data()));1526 return *reinterpret_cast<std::atomic<uint64_t> *>(UserHeader.data());1527}1528 1529uint64_t OnDiskGraphDB::getStandaloneStorageSize() const {1530 return standaloneStorageSize().load(std::memory_order_relaxed);1531}1532 1533size_t OnDiskGraphDB::getStorageSize() const {1534 return Index.size() + DataPool.size() + getStandaloneStorageSize();1535}1536 1537unsigned OnDiskGraphDB::getHardStorageLimitUtilization() const {1538 unsigned IndexPercent = Index.size() * 100ULL / Index.capacity();1539 unsigned DataPercent = DataPool.size() * 100ULL / DataPool.capacity();1540 return std::max(IndexPercent, DataPercent);1541}1542 1543Expected<std::unique_ptr<OnDiskGraphDB>>1544OnDiskGraphDB::open(StringRef AbsPath, StringRef HashName,1545 unsigned HashByteSize, OnDiskGraphDB *UpstreamDB,1546 FaultInPolicy Policy) {1547 if (std::error_code EC = sys::fs::create_directories(AbsPath))1548 return createFileError(AbsPath, EC);1549 1550 constexpr uint64_t MB = 1024ull * 1024ull;1551 constexpr uint64_t GB = 1024ull * 1024ull * 1024ull;1552 1553 uint64_t MaxIndexSize = 12 * GB;1554 uint64_t MaxDataPoolSize = 24 * GB;1555 1556 if (useSmallMappingSize(AbsPath)) {1557 MaxIndexSize = 1 * GB;1558 MaxDataPoolSize = 2 * GB;1559 }1560 1561 auto CustomSize = getOverriddenMaxMappingSize();1562 if (!CustomSize)1563 return CustomSize.takeError();1564 if (*CustomSize)1565 MaxIndexSize = MaxDataPoolSize = **CustomSize;1566 1567 SmallString<256> IndexPath(AbsPath);1568 sys::path::append(IndexPath, IndexFilePrefix + CASFormatVersion);1569 std::optional<OnDiskTrieRawHashMap> Index;1570 if (Error E = OnDiskTrieRawHashMap::create(1571 IndexPath, IndexTableName + "[" + HashName + "]",1572 HashByteSize * CHAR_BIT,1573 /*DataSize=*/sizeof(TrieRecord), MaxIndexSize,1574 /*MinFileSize=*/MB)1575 .moveInto(Index))1576 return std::move(E);1577 1578 uint32_t UserHeaderSize = sizeof(std::atomic<uint64_t>);1579 1580 SmallString<256> DataPoolPath(AbsPath);1581 sys::path::append(DataPoolPath, DataPoolFilePrefix + CASFormatVersion);1582 std::optional<OnDiskDataAllocator> DataPool;1583 StringRef PolicyName =1584 Policy == FaultInPolicy::SingleNode ? "single" : "full";1585 if (Error E = OnDiskDataAllocator::create(1586 DataPoolPath,1587 DataPoolTableName + "[" + HashName + "]" + PolicyName,1588 MaxDataPoolSize, /*MinFileSize=*/MB, UserHeaderSize,1589 [](void *UserHeaderPtr) {1590 new (UserHeaderPtr) std::atomic<uint64_t>(0);1591 })1592 .moveInto(DataPool))1593 return std::move(E);1594 if (DataPool->getUserHeader().size() != UserHeaderSize)1595 return createStringError(llvm::errc::argument_out_of_domain,1596 "unexpected user header in '" + DataPoolPath +1597 "'");1598 1599 return std::unique_ptr<OnDiskGraphDB>(new OnDiskGraphDB(1600 AbsPath, std::move(*Index), std::move(*DataPool), UpstreamDB, Policy));1601}1602 1603OnDiskGraphDB::OnDiskGraphDB(StringRef RootPath, OnDiskTrieRawHashMap Index,1604 OnDiskDataAllocator DataPool,1605 OnDiskGraphDB *UpstreamDB, FaultInPolicy Policy)1606 : Index(std::move(Index)), DataPool(std::move(DataPool)),1607 RootPath(RootPath.str()), UpstreamDB(UpstreamDB), FIPolicy(Policy) {1608 /// Lifetime for "big" objects not in DataPool.1609 ///1610 /// NOTE: Could use ThreadSafeTrieRawHashMap here. For now, doing something1611 /// simpler on the assumption there won't be much contention since most data1612 /// is not big. If there is contention, and we've already fixed ObjectProxy1613 /// object handles to be cheap enough to use consistently, the fix might be1614 /// to use better use of them rather than optimizing this map.1615 ///1616 /// FIXME: Figure out the right number of shards, if any.1617 StandaloneData = new StandaloneDataMapTy();1618}1619 1620OnDiskGraphDB::~OnDiskGraphDB() {1621 delete static_cast<StandaloneDataMapTy *>(StandaloneData);1622}1623 1624Error OnDiskGraphDB::importFullTree(ObjectID PrimaryID,1625 ObjectHandle UpstreamNode) {1626 // Copies the full CAS tree from upstream. Uses depth-first copying to protect1627 // against the process dying during importing and leaving the database with an1628 // incomplete tree. Note that if the upstream has missing nodes then the tree1629 // will be copied with missing nodes as well, it won't be considered an error.1630 struct UpstreamCursor {1631 ObjectHandle Node;1632 size_t RefsCount;1633 object_refs_iterator RefI;1634 object_refs_iterator RefE;1635 };1636 /// Keeps track of the state of visitation for current node and all of its1637 /// parents.1638 SmallVector<UpstreamCursor, 16> CursorStack;1639 /// Keeps track of the currently visited nodes as they are imported into1640 /// primary database, from current node and its parents. When a node is1641 /// entered for visitation it appends its own ID, then appends referenced IDs1642 /// as they get imported. When a node is fully imported it removes the1643 /// referenced IDs from the bottom of the stack which leaves its own ID at the1644 /// bottom, adding to the list of referenced IDs for the parent node.1645 SmallVector<ObjectID, 128> PrimaryNodesStack;1646 1647 auto enqueueNode = [&](ObjectID PrimaryID, std::optional<ObjectHandle> Node) {1648 PrimaryNodesStack.push_back(PrimaryID);1649 if (!Node)1650 return;1651 auto Refs = UpstreamDB->getObjectRefs(*Node);1652 CursorStack.push_back(1653 {*Node, (size_t)llvm::size(Refs), Refs.begin(), Refs.end()});1654 };1655 1656 enqueueNode(PrimaryID, UpstreamNode);1657 1658 while (!CursorStack.empty()) {1659 UpstreamCursor &Cur = CursorStack.back();1660 if (Cur.RefI == Cur.RefE) {1661 // Copy the node data into the primary store.1662 // FIXME: Use hard-link or cloning if the file-system supports it and data1663 // is stored into a separate file.1664 1665 // The bottom of \p PrimaryNodesStack contains the primary ID for the1666 // current node plus the list of imported referenced IDs.1667 assert(PrimaryNodesStack.size() >= Cur.RefsCount + 1);1668 ObjectID PrimaryID = *(PrimaryNodesStack.end() - Cur.RefsCount - 1);1669 auto PrimaryRefs = ArrayRef(PrimaryNodesStack)1670 .slice(PrimaryNodesStack.size() - Cur.RefsCount);1671 auto Data = UpstreamDB->getObjectData(Cur.Node);1672 if (Error E = store(PrimaryID, PrimaryRefs, Data))1673 return E;1674 // Remove the current node and its IDs from the stack.1675 PrimaryNodesStack.truncate(PrimaryNodesStack.size() - Cur.RefsCount);1676 CursorStack.pop_back();1677 continue;1678 }1679 1680 ObjectID UpstreamID = *(Cur.RefI++);1681 auto PrimaryID = getReference(UpstreamDB->getDigest(UpstreamID));1682 if (LLVM_UNLIKELY(!PrimaryID))1683 return PrimaryID.takeError();1684 if (containsObject(*PrimaryID, /*CheckUpstream=*/false)) {1685 // This \p ObjectID already exists in the primary. Either it was imported1686 // via \p importFullTree or the client created it, in which case the1687 // client takes responsibility for how it was formed.1688 enqueueNode(*PrimaryID, std::nullopt);1689 continue;1690 }1691 Expected<std::optional<ObjectHandle>> UpstreamNode =1692 UpstreamDB->load(UpstreamID);1693 if (!UpstreamNode)1694 return UpstreamNode.takeError();1695 enqueueNode(*PrimaryID, *UpstreamNode);1696 }1697 1698 assert(PrimaryNodesStack.size() == 1);1699 assert(PrimaryNodesStack.front() == PrimaryID);1700 return Error::success();1701}1702 1703Error OnDiskGraphDB::importSingleNode(ObjectID PrimaryID,1704 ObjectHandle UpstreamNode) {1705 // Copies only a single node, it doesn't copy the referenced nodes.1706 1707 // Copy the node data into the primary store.1708 // FIXME: Use hard-link or cloning if the file-system supports it and data is1709 // stored into a separate file.1710 auto Data = UpstreamDB->getObjectData(UpstreamNode);1711 auto UpstreamRefs = UpstreamDB->getObjectRefs(UpstreamNode);1712 SmallVector<ObjectID, 64> Refs;1713 Refs.reserve(llvm::size(UpstreamRefs));1714 for (ObjectID UpstreamRef : UpstreamRefs) {1715 auto Ref = getReference(UpstreamDB->getDigest(UpstreamRef));1716 if (LLVM_UNLIKELY(!Ref))1717 return Ref.takeError();1718 Refs.push_back(*Ref);1719 }1720 1721 return store(PrimaryID, Refs, Data);1722}1723 1724Expected<std::optional<ObjectHandle>>1725OnDiskGraphDB::faultInFromUpstream(ObjectID PrimaryID) {1726 if (!UpstreamDB)1727 return std::nullopt;1728 1729 auto UpstreamID = UpstreamDB->getReference(getDigest(PrimaryID));1730 if (LLVM_UNLIKELY(!UpstreamID))1731 return UpstreamID.takeError();1732 1733 Expected<std::optional<ObjectHandle>> UpstreamNode =1734 UpstreamDB->load(*UpstreamID);1735 if (!UpstreamNode)1736 return UpstreamNode.takeError();1737 if (!*UpstreamNode)1738 return std::nullopt;1739 1740 if (Error E = FIPolicy == FaultInPolicy::SingleNode1741 ? importSingleNode(PrimaryID, **UpstreamNode)1742 : importFullTree(PrimaryID, **UpstreamNode))1743 return std::move(E);1744 return load(PrimaryID);1745}1746