1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// This file implements OnDiskGraphDB, an on-disk CAS nodes database,
11/// independent of a particular hashing algorithm. It only needs to be
12/// 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, or
17/// allocated inside a datapool.
18/// - How references to other objects inside the same database is stored. They
19/// are stored as internal references, instead of full hash value to save
20/// space.
21/// - How to chain databases together and import objects from upstream
22/// 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 \a
27/// IndexTableName and managed by \a TrieRawHashMap. The contents are 8B
28/// that are accessed atomically, describing the object kind and where/how
29/// it's stored (including an optional file offset). See \a TrieRecord for
30/// more details.
31/// - db/data.<version>: a file for the "data" table, named by \a
32/// DataPoolTableName and managed by \a DataStore. New objects within
33/// TrieRecord::MaxEmbeddedSize are inserted here as \a
34/// TrieRecord::StorageKind::DataPool.
35/// - db/obj.<offset>.<version>: a file storing an object outside the main
36/// "data" table, named by its offset into the "index" table, with the
37/// format of \a TrieRecord::StorageKind::Standalone.
38/// - db/leaf.<offset>.<version>: a file storing a leaf node outside the
39/// main "data" table, named by its offset into the "index" table, with
40/// the format of \a TrieRecord::StorageKind::StandaloneLeaf.
41/// - db/leaf+0.<offset>.<version>: a file storing a null-terminated leaf object
42/// 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/OnDiskCASLogger.h"
53#include "llvm/CAS/OnDiskDataAllocator.h"
54#include "llvm/CAS/OnDiskTrieRawHashMap.h"
55#include "llvm/Support/Alignment.h"
56#include "llvm/Support/Compiler.h"
57#include "llvm/Support/Errc.h"
58#include "llvm/Support/Error.h"
59#include "llvm/Support/ErrorHandling.h"
60#include "llvm/Support/FileSystem.h"
61#include "llvm/Support/IOSandbox.h"
62#include "llvm/Support/MemoryBuffer.h"
63#include "llvm/Support/Path.h"
64#include "llvm/Support/Process.h"
65#include <atomic>
66#include <mutex>
67#include <optional>
68#include <variant>
69
70#define DEBUG_TYPE "on-disk-cas"
71
72using namespace llvm;
73using namespace llvm::cas;
74using namespace llvm::cas::ondisk;
75
76static constexpr StringLiteral IndexTableName = "llvm.cas.index";
77static constexpr StringLiteral DataPoolTableName = "llvm.cas.data";
78
79static constexpr StringLiteral IndexFilePrefix = "index.";
80static constexpr StringLiteral DataPoolFilePrefix = "data.";
81
82static constexpr StringLiteral FilePrefixObject = "obj.";
83static constexpr StringLiteral FilePrefixLeaf = "leaf.";
84static constexpr StringLiteral FilePrefixLeaf0 = "leaf+0.";
85
86static Error createCorruptObjectError(Expected<ArrayRef<uint8_t>> ID) {
87 if (!ID)
88 return ID.takeError();
89
90 return createStringError(EC: llvm::errc::invalid_argument,
91 S: "corrupt object '" + toHex(Input: *ID) + "'");
92}
93
94namespace {
95
96/// Trie record data: 8 bytes, atomic<uint64_t>
97/// - 1-byte: StorageKind
98/// - 7-bytes: DataStoreOffset (offset into referenced file)
99class TrieRecord {
100public:
101 enum class StorageKind : uint8_t {
102 /// Unknown object.
103 Unknown = 0,
104
105 /// data.vX: main pool, full DataStore record.
106 DataPool = 1,
107
108 /// obj.<TrieRecordOffset>.vX: standalone, with a full DataStore record.
109 Standalone = 10,
110
111 /// leaf.<TrieRecordOffset>.vX: standalone, just the data. File contents
112 /// exactly the data content and file size matches the data size. No refs.
113 StandaloneLeaf = 11,
114
115 /// leaf+0.<TrieRecordOffset>.vX: standalone, just the data plus an
116 /// extra null character ('\0'). File size is 1 bigger than the data size.
117 /// No refs.
118 StandaloneLeaf0 = 12,
119 };
120
121 static StringRef getStandaloneFilePrefix(StorageKind SK) {
122 switch (SK) {
123 default:
124 llvm_unreachable("Expected standalone storage kind");
125 case TrieRecord::StorageKind::Standalone:
126 return FilePrefixObject;
127 case TrieRecord::StorageKind::StandaloneLeaf:
128 return FilePrefixLeaf;
129 case TrieRecord::StorageKind::StandaloneLeaf0:
130 return FilePrefixLeaf0;
131 }
132 }
133
134 enum Limits : int64_t {
135 /// Saves files bigger than 64KB standalone instead of embedding them.
136 MaxEmbeddedSize = 64LL * 1024LL - 1,
137 };
138
139 struct Data {
140 StorageKind SK = StorageKind::Unknown;
141 FileOffset Offset;
142 };
143
144 /// Pack StorageKind and Offset from Data into 8 byte TrieRecord.
145 static uint64_t pack(Data D) {
146 assert(D.Offset.get() < (int64_t)(1ULL << 56));
147 uint64_t Packed = uint64_t(D.SK) << 56 | D.Offset.get();
148 assert(D.SK != StorageKind::Unknown || Packed == 0);
149#ifndef NDEBUG
150 Data RoundTrip = unpack(Packed);
151 assert(D.SK == RoundTrip.SK);
152 assert(D.Offset.get() == RoundTrip.Offset.get());
153#endif
154 return Packed;
155 }
156
157 // Unpack TrieRecord into Data.
158 static Data unpack(uint64_t Packed) {
159 Data D;
160 if (!Packed)
161 return D;
162 D.SK = (StorageKind)(Packed >> 56);
163 D.Offset = FileOffset(Packed & (UINT64_MAX >> 8));
164 return D;
165 }
166
167 TrieRecord() : Storage(0) {}
168
169 Data load() const { return unpack(Packed: Storage); }
170 bool compare_exchange_strong(Data &Existing, Data New);
171
172private:
173 std::atomic<uint64_t> Storage;
174};
175
176/// DataStore record data: 4B + size? + refs? + data + 0
177/// - 4-bytes: Header
178/// - {0,4,8}-bytes: DataSize (may be packed in Header)
179/// - {0,4,8}-bytes: NumRefs (may be packed in Header)
180/// - NumRefs*{4,8}-bytes: Refs[] (end-ptr is 8-byte aligned)
181/// - <data>
182/// - 1-byte: 0-term
183struct DataRecordHandle {
184 /// NumRefs storage: 4B, 2B, 1B, or 0B (no refs). Or, 8B, for alignment
185 /// convenience to avoid computing padding later.
186 enum class NumRefsFlags : uint8_t {
187 Uses0B = 0U,
188 Uses1B = 1U,
189 Uses2B = 2U,
190 Uses4B = 3U,
191 Uses8B = 4U,
192 Max = Uses8B,
193 };
194
195 /// DataSize storage: 8B, 4B, 2B, or 1B.
196 enum class DataSizeFlags {
197 Uses1B = 0U,
198 Uses2B = 1U,
199 Uses4B = 2U,
200 Uses8B = 3U,
201 Max = Uses8B,
202 };
203
204 /// Kind of ref stored in Refs[]: InternalRef or InternalRef4B.
205 enum class RefKindFlags {
206 InternalRef = 0U,
207 InternalRef4B = 1U,
208 Max = InternalRef4B,
209 };
210
211 enum Counts : int {
212 NumRefsShift = 0,
213 NumRefsBits = 3,
214 DataSizeShift = NumRefsShift + NumRefsBits,
215 DataSizeBits = 2,
216 RefKindShift = DataSizeShift + DataSizeBits,
217 RefKindBits = 1,
218 };
219 static_assert(((UINT32_MAX << NumRefsBits) & (uint32_t)NumRefsFlags::Max) ==
220 0,
221 "Not enough bits");
222 static_assert(((UINT32_MAX << DataSizeBits) & (uint32_t)DataSizeFlags::Max) ==
223 0,
224 "Not enough bits");
225 static_assert(((UINT32_MAX << RefKindBits) & (uint32_t)RefKindFlags::Max) ==
226 0,
227 "Not enough bits");
228
229 /// Layout of the DataRecordHandle and how to decode it.
230 struct LayoutFlags {
231 NumRefsFlags NumRefs;
232 DataSizeFlags DataSize;
233 RefKindFlags RefKind;
234
235 static uint64_t pack(LayoutFlags LF) {
236 unsigned Packed = ((unsigned)LF.NumRefs << NumRefsShift) |
237 ((unsigned)LF.DataSize << DataSizeShift) |
238 ((unsigned)LF.RefKind << RefKindShift);
239#ifndef NDEBUG
240 LayoutFlags RoundTrip = unpack(Packed);
241 assert(LF.NumRefs == RoundTrip.NumRefs);
242 assert(LF.DataSize == RoundTrip.DataSize);
243 assert(LF.RefKind == RoundTrip.RefKind);
244#endif
245 return Packed;
246 }
247 static LayoutFlags unpack(uint64_t Storage) {
248 assert(Storage <= UINT8_MAX && "Expect storage to fit in a byte");
249 LayoutFlags LF;
250 LF.NumRefs =
251 (NumRefsFlags)((Storage >> NumRefsShift) & ((1U << NumRefsBits) - 1));
252 LF.DataSize = (DataSizeFlags)((Storage >> DataSizeShift) &
253 ((1U << DataSizeBits) - 1));
254 LF.RefKind =
255 (RefKindFlags)((Storage >> RefKindShift) & ((1U << RefKindBits) - 1));
256 return LF;
257 }
258 };
259
260 /// Header layout:
261 /// - 1-byte: LayoutFlags
262 /// - 1-byte: 1B size field
263 /// - {0,2}-bytes: 2B size field
264 struct Header {
265 using PackTy = uint32_t;
266 PackTy Packed;
267
268 static constexpr unsigned LayoutFlagsShift =
269 (sizeof(PackTy) - 1) * CHAR_BIT;
270 };
271
272 struct Input {
273 InternalRefArrayRef Refs;
274 ArrayRef<char> Data;
275 };
276
277 LayoutFlags getLayoutFlags() const {
278 return LayoutFlags::unpack(Storage: H->Packed >> Header::LayoutFlagsShift);
279 }
280
281 uint64_t getDataSize() const;
282 void skipDataSize(LayoutFlags LF, int64_t &RelOffset) const;
283 uint32_t getNumRefs() const;
284 void skipNumRefs(LayoutFlags LF, int64_t &RelOffset) const;
285 int64_t getRefsRelOffset() const;
286 int64_t getDataRelOffset() const;
287
288 static uint64_t getTotalSize(uint64_t DataRelOffset, uint64_t DataSize) {
289 return DataRelOffset + DataSize + 1;
290 }
291 uint64_t getTotalSize() const {
292 return getDataRelOffset() + getDataSize() + 1;
293 }
294
295 /// Describe the layout of data stored and how to decode from
296 /// DataRecordHandle.
297 struct Layout {
298 explicit Layout(const Input &I);
299
300 LayoutFlags Flags;
301 uint64_t DataSize = 0;
302 uint32_t NumRefs = 0;
303 int64_t RefsRelOffset = 0;
304 int64_t DataRelOffset = 0;
305 uint64_t getTotalSize() const {
306 return DataRecordHandle::getTotalSize(DataRelOffset, DataSize);
307 }
308 };
309
310 InternalRefArrayRef getRefs() const {
311 assert(H && "Expected valid handle");
312 auto *BeginByte = reinterpret_cast<const char *>(H) + getRefsRelOffset();
313 size_t Size = getNumRefs();
314 if (!Size)
315 return InternalRefArrayRef();
316 if (getLayoutFlags().RefKind == RefKindFlags::InternalRef4B)
317 return ArrayRef(reinterpret_cast<const InternalRef4B *>(BeginByte), Size);
318 return ArrayRef(reinterpret_cast<const InternalRef *>(BeginByte), Size);
319 }
320
321 ArrayRef<char> getData() const {
322 assert(H && "Expected valid handle");
323 return ArrayRef(reinterpret_cast<const char *>(H) + getDataRelOffset(),
324 getDataSize());
325 }
326
327 static Expected<DataRecordHandle>
328 createWithError(function_ref<Expected<char *>(size_t Size)> Alloc,
329 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 ArrayRef<char> getData() const {
356 if (Bytes)
357 return *Bytes;
358 assert(Record && "Expected record or bytes");
359 return Record->getData();
360 }
361};
362
363/// Data loaded inside the memory from standalone file.
364class StandaloneDataInMemory {
365public:
366 OnDiskContent getContent() const;
367
368 OnDiskGraphDB::FileBackedData
369 getInternalFileBackedObjectData(StringRef RootPath) const;
370
371 /// Read this object's data from its file again, so the result does not
372 /// reference \a Region and stays valid after this object is gone.
373 ///
374 /// \returns \c nullptr when it does not apply, and the caller is
375 /// expected to copy instead.
376 std::unique_ptr<MemoryBuffer>
377 getStandaloneMemoryBuffer(StringRef RootPath, StringRef Name,
378 bool RequiresNullTerminator) const;
379
380 StandaloneDataInMemory(std::unique_ptr<sys::fs::mapped_file_region> Region,
381 TrieRecord::StorageKind SK, FileOffset IndexOffset)
382 : Region(std::move(Region)), SK(SK), IndexOffset(IndexOffset) {
383#ifndef NDEBUG
384 bool IsStandalone = false;
385 switch (SK) {
386 case TrieRecord::StorageKind::Standalone:
387 case TrieRecord::StorageKind::StandaloneLeaf:
388 case TrieRecord::StorageKind::StandaloneLeaf0:
389 IsStandalone = true;
390 break;
391 default:
392 break;
393 }
394 assert(IsStandalone);
395#endif
396 }
397
398private:
399 std::unique_ptr<sys::fs::mapped_file_region> Region;
400 TrieRecord::StorageKind SK;
401 FileOffset IndexOffset;
402};
403
404/// Container to lookup loaded standalone objects.
405template <size_t NumShards> class StandaloneDataMap {
406 static_assert(isPowerOf2_64(Value: NumShards), "Expected power of 2");
407
408public:
409 uintptr_t insert(ArrayRef<uint8_t> Hash, TrieRecord::StorageKind SK,
410 std::unique_ptr<sys::fs::mapped_file_region> Region,
411 FileOffset IndexOffset);
412
413 const StandaloneDataInMemory *lookup(ArrayRef<uint8_t> Hash) const;
414 bool count(ArrayRef<uint8_t> Hash) const { return bool(lookup(Hash)); }
415
416private:
417 struct Shard {
418 /// Needs to store a std::unique_ptr for a stable address identity.
419 DenseMap<const uint8_t *, std::unique_ptr<StandaloneDataInMemory>> Map;
420 mutable std::mutex Mutex;
421 };
422 Shard &getShard(ArrayRef<uint8_t> Hash) {
423 return const_cast<Shard &>(
424 const_cast<const StandaloneDataMap *>(this)->getShard(Hash));
425 }
426 const Shard &getShard(ArrayRef<uint8_t> Hash) const {
427 static_assert(NumShards <= 256, "Expected only 8 bits of shard");
428 return Shards[Hash[0] % NumShards];
429 }
430
431 Shard Shards[NumShards];
432};
433
434using StandaloneDataMapTy = StandaloneDataMap<16>;
435
436/// A vector of internal node references.
437class InternalRefVector {
438public:
439 void push_back(InternalRef Ref) {
440 if (NeedsFull)
441 return FullRefs.push_back(Elt: Ref);
442 if (std::optional<InternalRef4B> Small = InternalRef4B::tryToShrink(Ref))
443 return SmallRefs.push_back(Elt: *Small);
444 NeedsFull = true;
445 assert(FullRefs.empty());
446 FullRefs.reserve(N: SmallRefs.size() + 1);
447 for (InternalRef4B Small : SmallRefs)
448 FullRefs.push_back(Elt: Small);
449 FullRefs.push_back(Elt: Ref);
450 SmallRefs.clear();
451 }
452
453 operator InternalRefArrayRef() const {
454 assert(SmallRefs.empty() || FullRefs.empty());
455 return NeedsFull ? InternalRefArrayRef(FullRefs)
456 : InternalRefArrayRef(SmallRefs);
457 }
458
459private:
460 bool NeedsFull = false;
461 SmallVector<InternalRef4B> SmallRefs;
462 SmallVector<InternalRef> FullRefs;
463};
464
465} // namespace
466
467Expected<DataRecordHandle> DataRecordHandle::createWithError(
468 function_ref<Expected<char *>(size_t Size)> Alloc, const Input &I) {
469 Layout L(I);
470 if (Expected<char *> Mem = Alloc(L.getTotalSize()))
471 return constructImpl(Mem: *Mem, I, L);
472 else
473 return Mem.takeError();
474}
475
476ObjectHandle ObjectHandle::fromFileOffset(FileOffset Offset) {
477 // Store the file offset as it is.
478 assert(!(Offset.get() & 0x1));
479 return ObjectHandle(Offset.get());
480}
481
482ObjectHandle ObjectHandle::fromMemory(uintptr_t Ptr) {
483 // Store the pointer from memory with lowest bit set.
484 assert(!(Ptr & 0x1));
485 return ObjectHandle(Ptr | 1);
486}
487
488/// Proxy for an on-disk index record.
489struct OnDiskGraphDB::IndexProxy {
490 FileOffset Offset;
491 ArrayRef<uint8_t> Hash;
492 TrieRecord &Ref;
493};
494
495template <size_t N>
496uintptr_t StandaloneDataMap<N>::insert(
497 ArrayRef<uint8_t> Hash, TrieRecord::StorageKind SK,
498 std::unique_ptr<sys::fs::mapped_file_region> Region,
499 FileOffset IndexOffset) {
500 auto &S = getShard(Hash);
501 std::lock_guard<std::mutex> Lock(S.Mutex);
502 auto &V = S.Map[Hash.data()];
503 if (!V)
504 V = std::make_unique<StandaloneDataInMemory>(args: std::move(Region), args&: SK,
505 args&: IndexOffset);
506 return reinterpret_cast<uintptr_t>(V.get());
507}
508
509template <size_t N>
510const StandaloneDataInMemory *
511StandaloneDataMap<N>::lookup(ArrayRef<uint8_t> Hash) const {
512 auto &S = getShard(Hash);
513 std::lock_guard<std::mutex> Lock(S.Mutex);
514 auto I = S.Map.find(Hash.data());
515 if (I == S.Map.end())
516 return nullptr;
517 return &*I->second;
518}
519
520namespace {
521
522/// Copy of \a sys::fs::TempFile that skips RemoveOnSignal, which is too
523/// expensive to register/unregister at this rate.
524///
525/// FIXME: Add a TempFileManager that maintains a thread-safe list of open temp
526/// files and has a signal handler registerd that removes them all.
527class TempFile {
528 bool Done = false;
529 TempFile(StringRef Name, int FD, OnDiskCASLogger *Logger)
530 : TmpName(std::string(Name)), FD(FD), Logger(Logger) {}
531
532public:
533 /// This creates a temporary file with createUniqueFile.
534 static Expected<TempFile> create(const Twine &Model, OnDiskCASLogger *Logger);
535 TempFile(TempFile &&Other) { *this = std::move(Other); }
536 TempFile &operator=(TempFile &&Other) {
537 TmpName = std::move(Other.TmpName);
538 FD = Other.FD;
539 Logger = Other.Logger;
540 Other.Done = true;
541 Other.FD = -1;
542 return *this;
543 }
544
545 // Name of the temporary file.
546 std::string TmpName;
547
548 // The open file descriptor.
549 int FD = -1;
550
551 OnDiskCASLogger *Logger = nullptr;
552
553 // Keep this with the given name.
554 Error keep(const Twine &Name);
555 Error discard();
556
557 // This checks that keep or delete was called.
558 ~TempFile() { consumeError(Err: discard()); }
559};
560
561class MappedTempFile {
562public:
563 char *data() const { return Map.data(); }
564 size_t size() const { return Map.size(); }
565
566 Error discard() {
567 assert(Map && "Map already destroyed");
568 Map.unmap();
569 return Temp.discard();
570 }
571
572 Error keep(const Twine &Name) {
573 assert(Map && "Map already destroyed");
574 Map.unmap();
575 return Temp.keep(Name);
576 }
577
578 MappedTempFile(TempFile Temp, sys::fs::mapped_file_region Map)
579 : Temp(std::move(Temp)), Map(std::move(Map)) {}
580
581private:
582 TempFile Temp;
583 sys::fs::mapped_file_region Map;
584};
585} // namespace
586
587Error TempFile::discard() {
588 Done = true;
589 if (FD != -1) {
590 sys::fs::file_t File = sys::fs::convertFDToNativeFile(FD);
591 if (std::error_code EC = sys::fs::closeFile(F&: File))
592 return errorCodeToError(EC);
593 }
594 FD = -1;
595
596 // Always try to close and remove.
597 std::error_code RemoveEC;
598 if (!TmpName.empty()) {
599 std::error_code EC = sys::fs::remove(path: TmpName);
600 if (Logger)
601 Logger->logTempFileRemove(TmpName, EC);
602 if (EC)
603 return errorCodeToError(EC);
604 }
605 TmpName = "";
606
607 return Error::success();
608}
609
610Error TempFile::keep(const Twine &Name) {
611 assert(!Done);
612 Done = true;
613 // Always try to close and rename.
614 std::error_code RenameEC = sys::fs::rename(from: TmpName, to: Name);
615
616 if (Logger)
617 Logger->logTempFileKeep(TmpName, Name: Name.str(), EC: RenameEC);
618
619 if (!RenameEC)
620 TmpName = "";
621
622 sys::fs::file_t File = sys::fs::convertFDToNativeFile(FD);
623 if (std::error_code EC = sys::fs::closeFile(F&: File))
624 return errorCodeToError(EC);
625 FD = -1;
626
627 return errorCodeToError(EC: RenameEC);
628}
629
630Expected<TempFile> TempFile::create(const Twine &Model,
631 OnDiskCASLogger *Logger) {
632 int FD;
633 SmallString<128> ResultPath;
634 if (std::error_code EC = sys::fs::createUniqueFile(Model, ResultFD&: FD, ResultPath))
635 return errorCodeToError(EC);
636
637 if (Logger)
638 Logger->logTempFileCreate(Name: ResultPath);
639
640 TempFile Ret(ResultPath, FD, Logger);
641 return std::move(Ret);
642}
643
644bool TrieRecord::compare_exchange_strong(Data &Existing, Data New) {
645 uint64_t ExistingPacked = pack(D: Existing);
646 uint64_t NewPacked = pack(D: New);
647 if (Storage.compare_exchange_strong(i1&: ExistingPacked, i2: NewPacked))
648 return true;
649 Existing = unpack(Packed: ExistingPacked);
650 return false;
651}
652
653Expected<DataRecordHandle>
654DataRecordHandle::getFromDataPool(const OnDiskDataAllocator &Pool,
655 FileOffset Offset) {
656 auto HeaderData = Pool.get(Offset, Size: sizeof(DataRecordHandle::Header));
657 if (!HeaderData)
658 return HeaderData.takeError();
659
660 auto Record = DataRecordHandle::get(Mem: HeaderData->data());
661 if (Record.getTotalSize() + Offset.get() > Pool.size())
662 return createStringError(
663 EC: make_error_code(e: std::errc::illegal_byte_sequence),
664 S: "data record span passed the end of the data pool");
665
666 return Record;
667}
668
669DataRecordHandle DataRecordHandle::constructImpl(char *Mem, const Input &I,
670 const Layout &L) {
671 char *Next = Mem + sizeof(Header);
672
673 // Fill in Packed and set other data, then come back to construct the header.
674 Header::PackTy Packed = 0;
675 Packed |= LayoutFlags::pack(LF: L.Flags) << Header::LayoutFlagsShift;
676
677 // Construct DataSize.
678 switch (L.Flags.DataSize) {
679 case DataSizeFlags::Uses1B:
680 assert(I.Data.size() <= UINT8_MAX);
681 Packed |= (Header::PackTy)I.Data.size()
682 << ((sizeof(Packed) - 2) * CHAR_BIT);
683 break;
684 case DataSizeFlags::Uses2B:
685 assert(I.Data.size() <= UINT16_MAX);
686 Packed |= (Header::PackTy)I.Data.size()
687 << ((sizeof(Packed) - 4) * CHAR_BIT);
688 break;
689 case DataSizeFlags::Uses4B:
690 support::endian::write32le(P: Next, V: I.Data.size());
691 Next += 4;
692 break;
693 case DataSizeFlags::Uses8B:
694 support::endian::write64le(P: Next, V: I.Data.size());
695 Next += 8;
696 break;
697 }
698
699 // Construct NumRefs.
700 //
701 // NOTE: May be writing NumRefs even if there are zero refs in order to fix
702 // alignment.
703 switch (L.Flags.NumRefs) {
704 case NumRefsFlags::Uses0B:
705 break;
706 case NumRefsFlags::Uses1B:
707 assert(I.Refs.size() <= UINT8_MAX);
708 Packed |= (Header::PackTy)I.Refs.size()
709 << ((sizeof(Packed) - 2) * CHAR_BIT);
710 break;
711 case NumRefsFlags::Uses2B:
712 assert(I.Refs.size() <= UINT16_MAX);
713 Packed |= (Header::PackTy)I.Refs.size()
714 << ((sizeof(Packed) - 4) * CHAR_BIT);
715 break;
716 case NumRefsFlags::Uses4B:
717 support::endian::write32le(P: Next, V: I.Refs.size());
718 Next += 4;
719 break;
720 case NumRefsFlags::Uses8B:
721 support::endian::write64le(P: Next, V: I.Refs.size());
722 Next += 8;
723 break;
724 }
725
726 // Construct Refs[].
727 if (!I.Refs.empty()) {
728 assert((L.Flags.RefKind == RefKindFlags::InternalRef4B) == I.Refs.is4B());
729 ArrayRef<uint8_t> RefsBuffer = I.Refs.getBuffer();
730 llvm::copy(Range&: RefsBuffer, Out: Next);
731 Next += RefsBuffer.size();
732 }
733
734 // Construct Data and the trailing null.
735 assert(isAddrAligned(Align(8), Next));
736 llvm::copy(Range: I.Data, Out: Next);
737 Next[I.Data.size()] = 0;
738
739 // Construct the header itself and return.
740 Header *H = new (Mem) Header{.Packed: Packed};
741 DataRecordHandle Record(*H);
742 assert(Record.getData() == I.Data);
743 assert(Record.getNumRefs() == I.Refs.size());
744 assert(Record.getRefs() == I.Refs);
745 assert(Record.getLayoutFlags().DataSize == L.Flags.DataSize);
746 assert(Record.getLayoutFlags().NumRefs == L.Flags.NumRefs);
747 assert(Record.getLayoutFlags().RefKind == L.Flags.RefKind);
748 return Record;
749}
750
751DataRecordHandle::Layout::Layout(const Input &I) {
752 // Start initial relative offsets right after the Header.
753 uint64_t RelOffset = sizeof(Header);
754
755 // Initialize the easy stuff.
756 DataSize = I.Data.size();
757 NumRefs = I.Refs.size();
758
759 // Check refs size.
760 Flags.RefKind =
761 I.Refs.is4B() ? RefKindFlags::InternalRef4B : RefKindFlags::InternalRef;
762
763 // Find the smallest slot available for DataSize.
764 bool Has1B = true;
765 bool Has2B = true;
766 if (DataSize <= UINT8_MAX && Has1B) {
767 Flags.DataSize = DataSizeFlags::Uses1B;
768 Has1B = false;
769 } else if (DataSize <= UINT16_MAX && Has2B) {
770 Flags.DataSize = DataSizeFlags::Uses2B;
771 Has2B = false;
772 } else if (DataSize <= UINT32_MAX) {
773 Flags.DataSize = DataSizeFlags::Uses4B;
774 RelOffset += 4;
775 } else {
776 Flags.DataSize = DataSizeFlags::Uses8B;
777 RelOffset += 8;
778 }
779
780 // Find the smallest slot available for NumRefs. Never sets NumRefs8B here.
781 if (!NumRefs) {
782 Flags.NumRefs = NumRefsFlags::Uses0B;
783 } else if (NumRefs <= UINT8_MAX && Has1B) {
784 Flags.NumRefs = NumRefsFlags::Uses1B;
785 Has1B = false;
786 } else if (NumRefs <= UINT16_MAX && Has2B) {
787 Flags.NumRefs = NumRefsFlags::Uses2B;
788 Has2B = false;
789 } else {
790 Flags.NumRefs = NumRefsFlags::Uses4B;
791 RelOffset += 4;
792 }
793
794 // Helper to "upgrade" either DataSize or NumRefs by 4B to avoid complicated
795 // padding rules when reading and writing. This also bumps RelOffset.
796 //
797 // The value for NumRefs is strictly limited to UINT32_MAX, but it can be
798 // stored as 8B. This means we can *always* find a size to grow.
799 //
800 // NOTE: Only call this once.
801 auto GrowSizeFieldsBy4B = [&]() {
802 assert(isAligned(Align(4), RelOffset));
803 RelOffset += 4;
804
805 assert(Flags.NumRefs != NumRefsFlags::Uses8B &&
806 "Expected to be able to grow NumRefs8B");
807
808 // First try to grow DataSize. NumRefs will not (yet) be 8B, and if
809 // DataSize is upgraded to 8B it'll already be aligned.
810 //
811 // Failing that, grow NumRefs.
812 if (Flags.DataSize < DataSizeFlags::Uses4B)
813 Flags.DataSize = DataSizeFlags::Uses4B; // DataSize: Packed => 4B.
814 else if (Flags.DataSize < DataSizeFlags::Uses8B)
815 Flags.DataSize = DataSizeFlags::Uses8B; // DataSize: 4B => 8B.
816 else if (Flags.NumRefs < NumRefsFlags::Uses4B)
817 Flags.NumRefs = NumRefsFlags::Uses4B; // NumRefs: Packed => 4B.
818 else
819 Flags.NumRefs = NumRefsFlags::Uses8B; // NumRefs: 4B => 8B.
820 };
821
822 assert(isAligned(Align(4), RelOffset));
823 if (Flags.RefKind == RefKindFlags::InternalRef) {
824 // List of 8B refs should be 8B-aligned. Grow one of the sizes to get this
825 // without padding.
826 if (!isAligned(Lhs: Align(8), SizeInBytes: RelOffset))
827 GrowSizeFieldsBy4B();
828
829 assert(isAligned(Align(8), RelOffset));
830 RefsRelOffset = RelOffset;
831 RelOffset += 8 * NumRefs;
832 } else {
833 // The array of 4B refs doesn't need 8B alignment, but the data will need
834 // to be 8B-aligned. Detect this now, and, if necessary, shift everything
835 // by 4B by growing one of the sizes.
836 // If we remove the need for 8B-alignment for data there is <1% savings in
837 // disk storage for a clang build using MCCAS but the 8B-alignment may be
838 // useful in the future so keep it for now.
839 uint64_t RefListSize = 4 * NumRefs;
840 if (!isAligned(Lhs: Align(8), SizeInBytes: RelOffset + RefListSize))
841 GrowSizeFieldsBy4B();
842 RefsRelOffset = RelOffset;
843 RelOffset += RefListSize;
844 }
845
846 assert(isAligned(Align(8), RelOffset));
847 DataRelOffset = RelOffset;
848}
849
850uint64_t DataRecordHandle::getDataSize() const {
851 int64_t RelOffset = sizeof(Header);
852 auto *DataSizePtr = reinterpret_cast<const char *>(H) + RelOffset;
853 switch (getLayoutFlags().DataSize) {
854 case DataSizeFlags::Uses1B:
855 return (H->Packed >> ((sizeof(Header::PackTy) - 2) * CHAR_BIT)) & UINT8_MAX;
856 case DataSizeFlags::Uses2B:
857 return (H->Packed >> ((sizeof(Header::PackTy) - 4) * CHAR_BIT)) &
858 UINT16_MAX;
859 case DataSizeFlags::Uses4B:
860 return support::endian::read32le(P: DataSizePtr);
861 case DataSizeFlags::Uses8B:
862 return support::endian::read64le(P: DataSizePtr);
863 }
864 llvm_unreachable("Unknown DataSizeFlags enum");
865}
866
867void DataRecordHandle::skipDataSize(LayoutFlags LF, int64_t &RelOffset) const {
868 if (LF.DataSize >= DataSizeFlags::Uses4B)
869 RelOffset += 4;
870 if (LF.DataSize >= DataSizeFlags::Uses8B)
871 RelOffset += 4;
872}
873
874uint32_t DataRecordHandle::getNumRefs() const {
875 LayoutFlags LF = getLayoutFlags();
876 int64_t RelOffset = sizeof(Header);
877 skipDataSize(LF, RelOffset);
878 auto *NumRefsPtr = reinterpret_cast<const char *>(H) + RelOffset;
879 switch (LF.NumRefs) {
880 case NumRefsFlags::Uses0B:
881 return 0;
882 case NumRefsFlags::Uses1B:
883 return (H->Packed >> ((sizeof(Header::PackTy) - 2) * CHAR_BIT)) & UINT8_MAX;
884 case NumRefsFlags::Uses2B:
885 return (H->Packed >> ((sizeof(Header::PackTy) - 4) * CHAR_BIT)) &
886 UINT16_MAX;
887 case NumRefsFlags::Uses4B:
888 return support::endian::read32le(P: NumRefsPtr);
889 case NumRefsFlags::Uses8B:
890 return support::endian::read64le(P: NumRefsPtr);
891 }
892 llvm_unreachable("Unknown NumRefsFlags enum");
893}
894
895void DataRecordHandle::skipNumRefs(LayoutFlags LF, int64_t &RelOffset) const {
896 if (LF.NumRefs >= NumRefsFlags::Uses4B)
897 RelOffset += 4;
898 if (LF.NumRefs >= NumRefsFlags::Uses8B)
899 RelOffset += 4;
900}
901
902int64_t DataRecordHandle::getRefsRelOffset() const {
903 LayoutFlags LF = getLayoutFlags();
904 int64_t RelOffset = sizeof(Header);
905 skipDataSize(LF, RelOffset);
906 skipNumRefs(LF, RelOffset);
907 return RelOffset;
908}
909
910int64_t DataRecordHandle::getDataRelOffset() const {
911 LayoutFlags LF = getLayoutFlags();
912 int64_t RelOffset = sizeof(Header);
913 skipDataSize(LF, RelOffset);
914 skipNumRefs(LF, RelOffset);
915 uint32_t RefSize = LF.RefKind == RefKindFlags::InternalRef4B ? 4 : 8;
916 RelOffset += RefSize * getNumRefs();
917 return RelOffset;
918}
919
920Error OnDiskGraphDB::validate(bool Deep, HashingFuncT Hasher) const {
921 if (UpstreamDB) {
922 if (auto E = UpstreamDB->validate(Deep, Hasher))
923 return E;
924 }
925 if (!isAligned(Lhs: Align(8), SizeInBytes: DataPool.size()))
926 return createStringError(EC: llvm::errc::illegal_byte_sequence,
927 S: "data pool bump pointer is not aligned");
928 return Index.validate(RecordVerifier: [&](FileOffset Offset,
929 OnDiskTrieRawHashMap::ConstValueProxy Record)
930 -> Error {
931 auto formatError = [&](Twine Msg) {
932 return createStringError(
933 EC: llvm::errc::illegal_byte_sequence,
934 S: "bad record at 0x" +
935 utohexstr(X: (unsigned)Offset.get(), /*LowerCase=*/true) + ": " +
936 Msg);
937 };
938
939 if (Record.Data.size() != sizeof(TrieRecord))
940 return formatError("wrong data record size");
941 if (!isAligned(Lhs: Align::Of<TrieRecord>(), SizeInBytes: Record.Data.size()))
942 return formatError("wrong data record alignment");
943
944 auto *R = reinterpret_cast<const TrieRecord *>(Record.Data.data());
945 TrieRecord::Data D = R->load();
946 std::unique_ptr<MemoryBuffer> FileBuffer;
947 if ((uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::Unknown &&
948 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::DataPool &&
949 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::Standalone &&
950 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::StandaloneLeaf &&
951 (uint8_t)D.SK != (uint8_t)TrieRecord::StorageKind::StandaloneLeaf0)
952 return formatError("invalid record kind value");
953
954 auto Ref = InternalRef::getFromOffset(Offset);
955 auto I = getIndexProxyFromRef(Ref);
956 if (!I)
957 return I.takeError();
958
959 switch (D.SK) {
960 case TrieRecord::StorageKind::Unknown:
961 // This could be an abandoned entry due to a termination before updating
962 // the record. It can be reused by later insertion so just skip this entry
963 // for now.
964 return Error::success();
965 case TrieRecord::StorageKind::DataPool: {
966 // Check offset is a postive value, and large enough to hold the
967 // header for the data record.
968 if (D.Offset.get() <= 0 ||
969 D.Offset.get() + sizeof(DataRecordHandle::Header) >= DataPool.size())
970 return formatError("datapool record out of bound");
971
972 // DataRecord start needs to be aligned.
973 if (!isAligned(Lhs: Align(8), SizeInBytes: D.Offset.get()))
974 return formatError("data record offset is not aligned");
975
976 // Validate the layout flags before getFromDataPool calls getTotalSize().
977 auto HeaderData =
978 DataPool.get(Offset: D.Offset, Size: sizeof(DataRecordHandle::Header));
979 if (!HeaderData)
980 return formatError(toString(E: HeaderData.takeError()));
981 auto LF = DataRecordHandle::get(Mem: HeaderData->data()).getLayoutFlags();
982 if (LF.NumRefs > DataRecordHandle::NumRefsFlags::Max ||
983 LF.DataSize > DataRecordHandle::DataSizeFlags::Max)
984 return formatError("data record has invalid layout flags");
985 break;
986 }
987 case TrieRecord::StorageKind::Standalone:
988 case TrieRecord::StorageKind::StandaloneLeaf:
989 case TrieRecord::StorageKind::StandaloneLeaf0:
990 SmallString<256> Path;
991 getStandalonePath(FileSuffix: TrieRecord::getStandaloneFilePrefix(SK: D.SK), IndexOffset: I->Offset,
992 Path);
993 // If need to validate the content of the file later, just load the
994 // buffer here. Otherwise, just check the existance of the file.
995 if (Deep) {
996 auto File = MemoryBuffer::getFile(Filename: Path, /*IsText=*/false,
997 /*RequiresNullTerminator=*/false);
998 if (!File || !*File)
999 return formatError("record file \'" + Path + "\' does not exist");
1000
1001 FileBuffer = std::move(*File);
1002 } else if (!llvm::sys::fs::exists(Path))
1003 return formatError("record file \'" + Path + "\' does not exist");
1004 }
1005
1006 if (!Deep)
1007 return Error::success();
1008
1009 auto dataError = [&](Twine Msg) {
1010 return createStringError(EC: llvm::errc::illegal_byte_sequence,
1011 S: "bad data for digest \'" + toHex(Input: I->Hash) +
1012 "\': " + Msg);
1013 };
1014 SmallVector<ArrayRef<uint8_t>> Refs;
1015 ArrayRef<char> StoredData;
1016
1017 switch (D.SK) {
1018 case TrieRecord::StorageKind::Unknown:
1019 llvm_unreachable("already handled");
1020 case TrieRecord::StorageKind::DataPool: {
1021 auto DataRecord = DataRecordHandle::getFromDataPool(Pool: DataPool, Offset: D.Offset);
1022 if (!DataRecord)
1023 return dataError(toString(E: DataRecord.takeError()));
1024
1025 for (auto InternRef : DataRecord->getRefs()) {
1026 if (InternRef.getFileOffset().get() <= 0)
1027 return dataError("invalid ref offset");
1028 auto Index = getIndexProxyFromRef(Ref: InternRef);
1029 if (!Index)
1030 return Index.takeError();
1031 Refs.push_back(Elt: Index->Hash);
1032 }
1033 StoredData = DataRecord->getData();
1034 break;
1035 }
1036 case TrieRecord::StorageKind::Standalone: {
1037 if (FileBuffer->getBufferSize() < sizeof(DataRecordHandle::Header))
1038 return dataError("data record is not big enough to read the header");
1039 auto DataRecord = DataRecordHandle::get(Mem: FileBuffer->getBufferStart());
1040 if (DataRecord.getTotalSize() < FileBuffer->getBufferSize())
1041 return dataError(
1042 "data record span passed the end of the standalone file");
1043 for (auto InternRef : DataRecord.getRefs()) {
1044 if (InternRef.getFileOffset().get() <= 0)
1045 return dataError("invalid ref offset");
1046 auto Index = getIndexProxyFromRef(Ref: InternRef);
1047 if (!Index)
1048 return Index.takeError();
1049 Refs.push_back(Elt: Index->Hash);
1050 }
1051 StoredData = DataRecord.getData();
1052 break;
1053 }
1054 case TrieRecord::StorageKind::StandaloneLeaf:
1055 case TrieRecord::StorageKind::StandaloneLeaf0: {
1056 StoredData = arrayRefFromStringRef<char>(Input: FileBuffer->getBuffer());
1057 if (D.SK == TrieRecord::StorageKind::StandaloneLeaf0) {
1058 if (!FileBuffer->getBuffer().ends_with(Suffix: '\0'))
1059 return dataError("standalone file is not zero terminated");
1060 StoredData = StoredData.drop_back(N: 1);
1061 }
1062 break;
1063 }
1064 }
1065
1066 SmallVector<uint8_t> ComputedHash;
1067 Hasher(Refs, StoredData, ComputedHash);
1068 if (I->Hash != ArrayRef(ComputedHash))
1069 return dataError("hash mismatch, got \'" + toHex(Input: ComputedHash) +
1070 "\' instead");
1071
1072 return Error::success();
1073 });
1074}
1075
1076Error OnDiskGraphDB::validateObjectID(ObjectID ExternalRef) const {
1077 auto formatError = [&](Twine Msg) {
1078 return createStringError(
1079 EC: llvm::errc::illegal_byte_sequence,
1080 S: "bad ref=0x" +
1081 utohexstr(X: ExternalRef.getOpaqueData(), /*LowerCase=*/true) + ": " +
1082 Msg);
1083 };
1084
1085 if (ExternalRef.getOpaqueData() == 0)
1086 return formatError("zero is not a valid ref");
1087
1088 InternalRef InternalRef = getInternalRef(Ref: ExternalRef);
1089 auto I = getIndexProxyFromRef(Ref: InternalRef);
1090 if (!I)
1091 return formatError(llvm::toString(E: I.takeError()));
1092 auto Hash = getDigest(I: *I);
1093
1094 OnDiskTrieRawHashMap::ConstOnDiskPtr P = Index.find(Hash);
1095 if (!P)
1096 return formatError("not found using hash " + toHex(Input: Hash));
1097 IndexProxy OtherI = getIndexProxyFromPointer(P);
1098 ObjectID OtherRef = getExternalReference(Ref: makeInternalRef(IndexOffset: OtherI.Offset));
1099 if (OtherRef != ExternalRef)
1100 return formatError("ref does not match indexed offset " +
1101 utohexstr(X: OtherRef.getOpaqueData(), /*LowerCase=*/true) +
1102 " for hash " + toHex(Input: Hash));
1103 return Error::success();
1104}
1105
1106void OnDiskGraphDB::print(raw_ostream &OS) const {
1107 OS << "on-disk-root-path: " << RootPath << "\n";
1108
1109 struct PoolInfo {
1110 uint64_t Offset;
1111 };
1112 SmallVector<PoolInfo> Pool;
1113
1114 OS << "\n";
1115 OS << "index:\n";
1116 Index.print(OS, PrintRecordData: [&](ArrayRef<char> Data) {
1117 assert(Data.size() == sizeof(TrieRecord));
1118 assert(isAligned(Align::Of<TrieRecord>(), Data.size()));
1119 auto *R = reinterpret_cast<const TrieRecord *>(Data.data());
1120 TrieRecord::Data D = R->load();
1121 OS << " SK=";
1122 switch (D.SK) {
1123 case TrieRecord::StorageKind::Unknown:
1124 OS << "unknown ";
1125 break;
1126 case TrieRecord::StorageKind::DataPool:
1127 OS << "datapool ";
1128 Pool.push_back(Elt: {.Offset: D.Offset.get()});
1129 break;
1130 case TrieRecord::StorageKind::Standalone:
1131 OS << "standalone-data ";
1132 break;
1133 case TrieRecord::StorageKind::StandaloneLeaf:
1134 OS << "standalone-leaf ";
1135 break;
1136 case TrieRecord::StorageKind::StandaloneLeaf0:
1137 OS << "standalone-leaf+0";
1138 break;
1139 }
1140 OS << " Offset=" << (void *)D.Offset.get();
1141 });
1142 if (Pool.empty())
1143 return;
1144
1145 OS << "\n";
1146 OS << "pool:\n";
1147 llvm::sort(
1148 C&: Pool, Comp: [](PoolInfo LHS, PoolInfo RHS) { return LHS.Offset < RHS.Offset; });
1149 for (PoolInfo PI : Pool) {
1150 OS << "- addr=" << (void *)PI.Offset << " ";
1151 auto D = DataRecordHandle::getFromDataPool(Pool: DataPool, Offset: FileOffset(PI.Offset));
1152 if (!D) {
1153 OS << "error: " << toString(E: D.takeError());
1154 return;
1155 }
1156
1157 OS << "record refs=" << D->getNumRefs() << " data=" << D->getDataSize()
1158 << " size=" << D->getTotalSize()
1159 << " end=" << (void *)(PI.Offset + D->getTotalSize()) << "\n";
1160 }
1161}
1162
1163Expected<OnDiskGraphDB::IndexProxy>
1164OnDiskGraphDB::indexHash(ArrayRef<uint8_t> Hash) {
1165 auto P = Index.insertLazy(
1166 Hash, OnConstruct: [](FileOffset TentativeOffset,
1167 OnDiskTrieRawHashMap::ValueProxy TentativeValue) {
1168 assert(TentativeValue.Data.size() == sizeof(TrieRecord));
1169 assert(
1170 isAddrAligned(Align::Of<TrieRecord>(), TentativeValue.Data.data()));
1171 new (TentativeValue.Data.data()) TrieRecord();
1172 });
1173 if (LLVM_UNLIKELY(!P))
1174 return P.takeError();
1175
1176 assert(*P && "Expected insertion");
1177 return getIndexProxyFromPointer(P: *P);
1178}
1179
1180OnDiskGraphDB::IndexProxy OnDiskGraphDB::getIndexProxyFromPointer(
1181 OnDiskTrieRawHashMap::ConstOnDiskPtr P) const {
1182 assert(P);
1183 assert(P.getOffset());
1184 return IndexProxy{.Offset: P.getOffset(), .Hash: P->Hash,
1185 .Ref: *const_cast<TrieRecord *>(
1186 reinterpret_cast<const TrieRecord *>(P->Data.data()))};
1187}
1188
1189Expected<ObjectID> OnDiskGraphDB::getReference(ArrayRef<uint8_t> Hash) {
1190 auto I = indexHash(Hash);
1191 if (LLVM_UNLIKELY(!I))
1192 return I.takeError();
1193 return getExternalReference(I: *I);
1194}
1195
1196ObjectID OnDiskGraphDB::getExternalReference(const IndexProxy &I) {
1197 return getExternalReference(Ref: makeInternalRef(IndexOffset: I.Offset));
1198}
1199
1200std::optional<ObjectID>
1201OnDiskGraphDB::getExistingReference(ArrayRef<uint8_t> Digest,
1202 bool CheckUpstream) {
1203 auto tryUpstream =
1204 [&](std::optional<IndexProxy> I) -> std::optional<ObjectID> {
1205 if (!CheckUpstream || !UpstreamDB)
1206 return std::nullopt;
1207 std::optional<ObjectID> UpstreamID =
1208 UpstreamDB->getExistingReference(Digest);
1209 if (LLVM_UNLIKELY(!UpstreamID))
1210 return std::nullopt;
1211 auto Ref = expectedToOptional(E: indexHash(Hash: Digest));
1212 if (!Ref)
1213 return std::nullopt;
1214 if (!I)
1215 I.emplace(args&: *Ref);
1216 return getExternalReference(I: *I);
1217 };
1218
1219 OnDiskTrieRawHashMap::ConstOnDiskPtr P = Index.find(Hash: Digest);
1220 if (!P)
1221 return tryUpstream(std::nullopt);
1222 IndexProxy I = getIndexProxyFromPointer(P);
1223 TrieRecord::Data Obj = I.Ref.load();
1224 if (Obj.SK == TrieRecord::StorageKind::Unknown)
1225 return tryUpstream(I);
1226 return getExternalReference(Ref: makeInternalRef(IndexOffset: I.Offset));
1227}
1228
1229Expected<OnDiskGraphDB::IndexProxy>
1230OnDiskGraphDB::getIndexProxyFromRef(InternalRef Ref) const {
1231 auto P = Index.recoverFromFileOffset(Offset: Ref.getFileOffset());
1232 if (LLVM_UNLIKELY(!P))
1233 return P.takeError();
1234 return getIndexProxyFromPointer(P: *P);
1235}
1236
1237Expected<ArrayRef<uint8_t>> OnDiskGraphDB::getDigest(InternalRef Ref) const {
1238 auto I = getIndexProxyFromRef(Ref);
1239 if (!I)
1240 return I.takeError();
1241 return I->Hash;
1242}
1243
1244ArrayRef<uint8_t> OnDiskGraphDB::getDigest(const IndexProxy &I) const {
1245 return I.Hash;
1246}
1247
1248static std::variant<const StandaloneDataInMemory *, DataRecordHandle>
1249getStandaloneDataOrDataRecord(const OnDiskDataAllocator &DataPool,
1250 ObjectHandle OH) {
1251 // Decode ObjectHandle to locate the stored content.
1252 uint64_t Data = OH.getOpaqueData();
1253 if (Data & 1) {
1254 const auto *SDIM =
1255 reinterpret_cast<const StandaloneDataInMemory *>(Data & (-1ULL << 1));
1256 return SDIM;
1257 }
1258
1259 auto DataHandle =
1260 cantFail(ValOrErr: DataRecordHandle::getFromDataPool(Pool: DataPool, Offset: FileOffset(Data)));
1261 assert(DataHandle.getData().end()[0] == 0 && "Null termination");
1262 return DataHandle;
1263}
1264
1265static OnDiskContent getContentFromHandle(const OnDiskDataAllocator &DataPool,
1266 ObjectHandle OH) {
1267 auto SDIMOrRecord = getStandaloneDataOrDataRecord(DataPool, OH);
1268 if (std::holds_alternative<const StandaloneDataInMemory *>(v: SDIMOrRecord)) {
1269 return std::get<const StandaloneDataInMemory *>(v&: SDIMOrRecord)->getContent();
1270 } else {
1271 auto DataHandle = std::get<DataRecordHandle>(v: std::move(SDIMOrRecord));
1272 return OnDiskContent{.Record: std::move(DataHandle), .Bytes: std::nullopt};
1273 }
1274}
1275
1276ArrayRef<char> OnDiskGraphDB::getObjectData(ObjectHandle Node) const {
1277 OnDiskContent Content = getContentFromHandle(DataPool, OH: Node);
1278 return Content.getData();
1279}
1280
1281InternalRefArrayRef OnDiskGraphDB::getInternalRefs(ObjectHandle Node) const {
1282 if (std::optional<DataRecordHandle> Record =
1283 getContentFromHandle(DataPool, OH: Node).Record)
1284 return Record->getRefs();
1285 return std::nullopt;
1286}
1287
1288OnDiskGraphDB::FileBackedData
1289OnDiskGraphDB::getInternalFileBackedObjectData(ObjectHandle Node) const {
1290 auto SDIMOrRecord = getStandaloneDataOrDataRecord(DataPool, OH: Node);
1291 if (std::holds_alternative<const StandaloneDataInMemory *>(v: SDIMOrRecord)) {
1292 auto *SDIM = std::get<const StandaloneDataInMemory *>(v&: SDIMOrRecord);
1293 return SDIM->getInternalFileBackedObjectData(RootPath);
1294 } else {
1295 auto DataHandle = std::get<DataRecordHandle>(v: std::move(SDIMOrRecord));
1296 return FileBackedData{.Data: DataHandle.getData(), /*FileInfo=*/std::nullopt};
1297 }
1298}
1299
1300std::unique_ptr<MemoryBuffer>
1301OnDiskGraphDB::getStandaloneMemoryBuffer(ObjectHandle Node, StringRef Name,
1302 bool RequiresNullTerminator) const {
1303 // Only an object with a file to itself can be read back on its own; one in
1304 // the shared data pool is a subrange of a file holding unrelated objects.
1305 auto SDIMOrRecord = getStandaloneDataOrDataRecord(DataPool, OH: Node);
1306 if (auto **SDIM =
1307 std::get_if<const StandaloneDataInMemory *>(ptr: &SDIMOrRecord)) {
1308 if (std::unique_ptr<MemoryBuffer> Standalone =
1309 (*SDIM)->getStandaloneMemoryBuffer(RootPath, Name,
1310 RequiresNullTerminator))
1311 return Standalone;
1312 }
1313
1314 return MemoryBuffer::getMemBufferCopy(InputData: toStringRef(Input: getObjectData(Node)), BufferName: Name);
1315}
1316
1317Expected<std::optional<ObjectHandle>>
1318OnDiskGraphDB::load(ObjectID ExternalRef) {
1319 InternalRef Ref = getInternalRef(Ref: ExternalRef);
1320 auto I = getIndexProxyFromRef(Ref);
1321 if (!I)
1322 return I.takeError();
1323 TrieRecord::Data Object = I->Ref.load();
1324
1325 if (Object.SK == TrieRecord::StorageKind::Unknown)
1326 return faultInFromUpstream(PrimaryID: ExternalRef);
1327
1328 if (Object.SK == TrieRecord::StorageKind::DataPool)
1329 return ObjectHandle::fromFileOffset(Offset: Object.Offset);
1330
1331 // Only TrieRecord::StorageKind::Standalone (and variants) need to be
1332 // explicitly loaded.
1333 //
1334 // There's corruption if standalone objects have offsets, or if we get here
1335 // for something that isn't standalone.
1336 if (Object.Offset)
1337 return createCorruptObjectError(ID: getDigest(I: *I));
1338 switch (Object.SK) {
1339 case TrieRecord::StorageKind::Unknown:
1340 case TrieRecord::StorageKind::DataPool:
1341 llvm_unreachable("unexpected storage kind");
1342 case TrieRecord::StorageKind::Standalone:
1343 case TrieRecord::StorageKind::StandaloneLeaf0:
1344 case TrieRecord::StorageKind::StandaloneLeaf:
1345 break;
1346 }
1347
1348 // Search in StandaloneMap to see if data is already loaded.
1349 auto *StandaloneMap = static_cast<StandaloneDataMapTy *>(StandaloneData);
1350 if (const StandaloneDataInMemory *SDIM = StandaloneMap->lookup(Hash: I->Hash))
1351 return ObjectHandle::fromMemory(Ptr: reinterpret_cast<uintptr_t>(SDIM));
1352
1353 // Load it from disk.
1354 //
1355 // Note: Creation logic guarantees that data that needs null-termination is
1356 // suitably 0-padded. Requiring null-termination here would be too expensive
1357 // for extremely large objects that happen to be page-aligned.
1358 SmallString<256> Path;
1359 getStandalonePath(FileSuffix: TrieRecord::getStandaloneFilePrefix(SK: Object.SK), IndexOffset: I->Offset,
1360 Path);
1361
1362 auto BypassSandbox = sys::sandbox::scopedDisable();
1363
1364 auto File = sys::fs::openNativeFileForRead(Name: Path);
1365 if (!File)
1366 return createFileError(F: Path, E: File.takeError());
1367
1368 llvm::scope_exit CloseFile([&]() { sys::fs::closeFile(F&: *File); });
1369
1370 sys::fs::file_status Status;
1371 if (std::error_code EC = sys::fs::status(F: *File, Result&: Status))
1372 return createCorruptObjectError(ID: getDigest(I: *I));
1373
1374 std::error_code EC;
1375 auto Region = std::make_unique<sys::fs::mapped_file_region>(
1376 args&: *File, args: sys::fs::mapped_file_region::readonly, args: Status.getSize(), args: 0, args&: EC);
1377 if (EC)
1378 return createCorruptObjectError(ID: getDigest(I: *I));
1379
1380 return ObjectHandle::fromMemory(
1381 Ptr: StandaloneMap->insert(Hash: I->Hash, SK: Object.SK, Region: std::move(Region), IndexOffset: I->Offset));
1382}
1383
1384Expected<bool> OnDiskGraphDB::isMaterialized(ObjectID Ref) {
1385 auto Presence = getObjectPresence(Ref, /*CheckUpstream=*/true);
1386 if (!Presence)
1387 return Presence.takeError();
1388
1389 switch (*Presence) {
1390 case ObjectPresence::Missing:
1391 return false;
1392 case ObjectPresence::InPrimaryDB:
1393 return true;
1394 case ObjectPresence::OnlyInUpstreamDB:
1395 if (auto FaultInResult = faultInFromUpstream(PrimaryID: Ref); !FaultInResult)
1396 return FaultInResult.takeError();
1397 return true;
1398 }
1399 llvm_unreachable("Unknown ObjectPresence enum");
1400}
1401
1402Expected<OnDiskGraphDB::ObjectPresence>
1403OnDiskGraphDB::getObjectPresence(ObjectID ExternalRef,
1404 bool CheckUpstream) const {
1405 InternalRef Ref = getInternalRef(Ref: ExternalRef);
1406 auto I = getIndexProxyFromRef(Ref);
1407 if (!I)
1408 return I.takeError();
1409
1410 TrieRecord::Data Object = I->Ref.load();
1411 if (Object.SK != TrieRecord::StorageKind::Unknown)
1412 return ObjectPresence::InPrimaryDB;
1413
1414 if (!CheckUpstream || !UpstreamDB)
1415 return ObjectPresence::Missing;
1416
1417 std::optional<ObjectID> UpstreamID =
1418 UpstreamDB->getExistingReference(Digest: getDigest(I: *I));
1419 return UpstreamID.has_value() ? ObjectPresence::OnlyInUpstreamDB
1420 : ObjectPresence::Missing;
1421}
1422
1423InternalRef OnDiskGraphDB::makeInternalRef(FileOffset IndexOffset) {
1424 return InternalRef::getFromOffset(Offset: IndexOffset);
1425}
1426
1427static void getStandalonePath(StringRef RootPath, StringRef Prefix,
1428 FileOffset IndexOffset,
1429 SmallVectorImpl<char> &Path) {
1430 Path.assign(in_start: RootPath.begin(), in_end: RootPath.end());
1431 sys::path::append(path&: Path,
1432 a: Prefix + Twine(IndexOffset.get()) + "." + CASFormatVersion);
1433}
1434
1435void OnDiskGraphDB::getStandalonePath(StringRef Prefix, FileOffset IndexOffset,
1436 SmallVectorImpl<char> &Path) const {
1437 return ::getStandalonePath(RootPath, Prefix, IndexOffset, Path);
1438}
1439
1440OnDiskContent StandaloneDataInMemory::getContent() const {
1441 bool Leaf0 = false;
1442 bool Leaf = false;
1443 switch (SK) {
1444 default:
1445 llvm_unreachable("Storage kind must be standalone");
1446 case TrieRecord::StorageKind::Standalone:
1447 break;
1448 case TrieRecord::StorageKind::StandaloneLeaf0:
1449 Leaf = Leaf0 = true;
1450 break;
1451 case TrieRecord::StorageKind::StandaloneLeaf:
1452 Leaf = true;
1453 break;
1454 }
1455
1456 if (Leaf) {
1457 StringRef Data(Region->data(), Region->size());
1458 assert(Data.drop_back(Leaf0).end()[0] == 0 &&
1459 "Standalone node data missing null termination");
1460 return OnDiskContent{.Record: std::nullopt,
1461 .Bytes: arrayRefFromStringRef<char>(Input: Data.drop_back(N: Leaf0))};
1462 }
1463
1464 DataRecordHandle Record = DataRecordHandle::get(Mem: Region->data());
1465 assert(Record.getData().end()[0] == 0 &&
1466 "Standalone object record missing null termination for data");
1467 return OnDiskContent{.Record: Record, .Bytes: std::nullopt};
1468}
1469
1470OnDiskGraphDB::FileBackedData
1471StandaloneDataInMemory::getInternalFileBackedObjectData(
1472 StringRef RootPath) const {
1473 switch (SK) {
1474 case TrieRecord::StorageKind::Unknown:
1475 case TrieRecord::StorageKind::DataPool:
1476 llvm_unreachable("unexpected storage kind");
1477 case TrieRecord::StorageKind::Standalone:
1478 return OnDiskGraphDB::FileBackedData{.Data: getContent().getData(),
1479 /*FileInfo=*/std::nullopt};
1480 case TrieRecord::StorageKind::StandaloneLeaf0:
1481 case TrieRecord::StorageKind::StandaloneLeaf:
1482 bool IsFileNulTerminated = SK == TrieRecord::StorageKind::StandaloneLeaf0;
1483 SmallString<256> Path;
1484 ::getStandalonePath(RootPath, Prefix: TrieRecord::getStandaloneFilePrefix(SK),
1485 IndexOffset, Path);
1486 return OnDiskGraphDB::FileBackedData{
1487 .Data: getContent().getData(), .FileInfo: OnDiskGraphDB::FileBackedData::FileInfoTy{
1488 .FilePath: std::string(Path), .IsFileNulTerminated: IsFileNulTerminated}};
1489 }
1490 llvm_unreachable("Unknown StorageKind enum");
1491}
1492
1493namespace {
1494/// A MemoryBuffer exposing a subrange of another buffer's bytes, under its own
1495/// name.
1496class AdoptedMemoryBuffer final : public MemoryBuffer {
1497public:
1498 AdoptedMemoryBuffer(std::unique_ptr<MemoryBuffer> Buffer, StringRef Name,
1499 uint64_t Offset, uint64_t Size)
1500 : Buffer(std::move(Buffer)), Name(Name.str()) {
1501 const char *Start = this->Buffer->getBufferStart() + Offset;
1502 init(BufStart: Start, BufEnd: Start + Size, /*RequiresNullTerminator=*/false);
1503 }
1504
1505 StringRef getBufferIdentifier() const final { return Name; }
1506
1507 BufferKind getBufferKind() const final { return Buffer->getBufferKind(); }
1508
1509private:
1510 std::unique_ptr<MemoryBuffer> Buffer;
1511 std::string Name;
1512};
1513} // end anonymous namespace
1514
1515std::unique_ptr<MemoryBuffer> StandaloneDataInMemory::getStandaloneMemoryBuffer(
1516 StringRef RootPath, StringRef Name, bool RequiresNullTerminator) const {
1517 // A plain leaf's file is exactly the data, with no nul after it to map. The
1518 // other kinds have one: a record's own terminator, or the one appended to a
1519 // "leaf+0".
1520 if (RequiresNullTerminator && SK == TrieRecord::StorageKind::StandaloneLeaf)
1521 return nullptr;
1522
1523 // Read the file again instead of sharing \a Region, whose lifetime is tied
1524 // to this object. These files are written once and never modified, so the
1525 // second read sees the same bytes. Whether that ends up mapping the file or
1526 // copying it is up to MemoryBuffer; either way the result stands alone.
1527 SmallString<256> Path;
1528 ::getStandalonePath(RootPath, Prefix: TrieRecord::getStandaloneFilePrefix(SK),
1529 IndexOffset, Path);
1530 auto BypassSandbox = sys::sandbox::scopedDisable();
1531 ErrorOr<std::unique_ptr<MemoryBuffer>> Mapped =
1532 MemoryBuffer::getFile(Filename: Path, /*IsText=*/false,
1533 /*RequiresNullTerminator=*/false,
1534 /*IsVolatile=*/false);
1535 if (!Mapped)
1536 return nullptr;
1537
1538 // Find the data within the mapping. A leaf's file holds just the data; a
1539 // record's also holds its header and refs.
1540 OnDiskContent Content = getContent();
1541 ArrayRef<char> Data = Content.getData();
1542 uint64_t Offset = Content.Record ? Data.data() - Region->data() : 0;
1543 if (Offset + Data.size() > (*Mapped)->getBufferSize())
1544 return nullptr;
1545
1546 return std::make_unique<AdoptedMemoryBuffer>(args: std::move(*Mapped), args&: Name, args&: Offset,
1547 args: Data.size());
1548}
1549
1550static Expected<MappedTempFile>
1551createTempFile(StringRef FinalPath, uint64_t Size, OnDiskCASLogger *Logger) {
1552 auto BypassSandbox = sys::sandbox::scopedDisable();
1553
1554 assert(Size && "Unexpected request for an empty temp file");
1555 Expected<TempFile> File = TempFile::create(Model: FinalPath + ".%%%%%%", Logger);
1556 if (!File)
1557 return File.takeError();
1558
1559 if (Error E = preallocateFileTail(FD: File->FD, CurrentSize: 0, NewSize: Size).takeError())
1560 return createFileError(F: File->TmpName, E: std::move(E));
1561
1562 if (auto EC = sys::fs::resize_file_before_mapping_readwrite(FD: File->FD, Size))
1563 return createFileError(F: File->TmpName, EC);
1564
1565 std::error_code EC;
1566 sys::fs::mapped_file_region Map(sys::fs::convertFDToNativeFile(FD: File->FD),
1567 sys::fs::mapped_file_region::readwrite, Size,
1568 0, EC);
1569 if (EC)
1570 return createFileError(F: File->TmpName, EC);
1571 return MappedTempFile(std::move(*File), std::move(Map));
1572}
1573
1574static size_t getPageSize() {
1575 static int PageSize = sys::Process::getPageSizeEstimate();
1576 return PageSize;
1577}
1578
1579Error OnDiskGraphDB::createStandaloneLeaf(IndexProxy &I, ArrayRef<char> Data) {
1580 assert(Data.size() > TrieRecord::MaxEmbeddedSize &&
1581 "Expected a bigger file for external content...");
1582
1583 bool Leaf0 = isAligned(Lhs: Align(getPageSize()), SizeInBytes: Data.size());
1584 TrieRecord::StorageKind SK = Leaf0 ? TrieRecord::StorageKind::StandaloneLeaf0
1585 : TrieRecord::StorageKind::StandaloneLeaf;
1586
1587 SmallString<256> Path;
1588 int64_t FileSize = Data.size() + Leaf0;
1589 getStandalonePath(Prefix: TrieRecord::getStandaloneFilePrefix(SK), IndexOffset: I.Offset, Path);
1590
1591 // Write the file. Don't reuse this mapped_file_region, which is read/write.
1592 // Let load() pull up one that's read-only.
1593 Expected<MappedTempFile> File = createTempFile(FinalPath: Path, Size: FileSize, Logger: Logger.get());
1594 if (!File)
1595 return File.takeError();
1596 assert(File->size() == (uint64_t)FileSize);
1597 llvm::copy(Range&: Data, Out: File->data());
1598 if (Leaf0)
1599 File->data()[Data.size()] = 0;
1600 assert(File->data()[Data.size()] == 0);
1601 if (Error E = File->keep(Name: Path))
1602 return E;
1603
1604 // Store the object reference.
1605 TrieRecord::Data Existing;
1606 {
1607 TrieRecord::Data Leaf{.SK: SK, .Offset: FileOffset()};
1608 if (I.Ref.compare_exchange_strong(Existing, New: Leaf)) {
1609 recordStandaloneSizeIncrease(SizeIncrease: FileSize);
1610 return Error::success();
1611 }
1612 }
1613
1614 // If there was a race, confirm that the new value has valid storage.
1615 if (Existing.SK == TrieRecord::StorageKind::Unknown)
1616 return createCorruptObjectError(ID: getDigest(I));
1617
1618 return Error::success();
1619}
1620
1621Error OnDiskGraphDB::store(ObjectID ID, ArrayRef<ObjectID> Refs,
1622 ArrayRef<char> Data) {
1623 auto I = getIndexProxyFromRef(Ref: getInternalRef(Ref: ID));
1624 if (LLVM_UNLIKELY(!I))
1625 return I.takeError();
1626
1627 // Early return in case the node exists.
1628 {
1629 TrieRecord::Data Existing = I->Ref.load();
1630 if (Existing.SK != TrieRecord::StorageKind::Unknown)
1631 return Error::success();
1632 }
1633
1634 auto BypassSandbox = sys::sandbox::scopedDisable();
1635
1636 // Big leaf nodes.
1637 if (Refs.empty() && Data.size() > TrieRecord::MaxEmbeddedSize)
1638 return createStandaloneLeaf(I&: *I, Data);
1639
1640 // TODO: Check whether it's worth checking the index for an already existing
1641 // object (like storeTreeImpl() does) before building up the
1642 // InternalRefVector.
1643 InternalRefVector InternalRefs;
1644 for (ObjectID Ref : Refs)
1645 InternalRefs.push_back(Ref: getInternalRef(Ref));
1646
1647 // Create the object.
1648
1649 DataRecordHandle::Input Input{.Refs: InternalRefs, .Data: Data};
1650
1651 // Compute the storage kind, allocate it, and create the record.
1652 TrieRecord::StorageKind SK = TrieRecord::StorageKind::Unknown;
1653 FileOffset PoolOffset;
1654 SmallString<256> Path;
1655 std::optional<MappedTempFile> File;
1656 std::optional<uint64_t> FileSize;
1657 auto AllocStandaloneFile = [&](size_t Size) -> Expected<char *> {
1658 getStandalonePath(Prefix: TrieRecord::getStandaloneFilePrefix(
1659 SK: TrieRecord::StorageKind::Standalone),
1660 IndexOffset: I->Offset, Path);
1661 if (Error E = createTempFile(FinalPath: Path, Size, Logger: Logger.get()).moveInto(Value&: File))
1662 return std::move(E);
1663 assert(File->size() == Size);
1664 FileSize = Size;
1665 SK = TrieRecord::StorageKind::Standalone;
1666 return File->data();
1667 };
1668 auto Alloc = [&](size_t Size) -> Expected<char *> {
1669 if (Size <= TrieRecord::MaxEmbeddedSize) {
1670 SK = TrieRecord::StorageKind::DataPool;
1671 auto P = DataPool.allocate(Size);
1672 if (LLVM_UNLIKELY(!P)) {
1673 char *NewAlloc = nullptr;
1674 auto NewE = handleErrors(
1675 E: P.takeError(), Hs: [&](std::unique_ptr<StringError> E) -> Error {
1676 if (E->convertToErrorCode() == std::errc::not_enough_memory)
1677 return AllocStandaloneFile(Size).moveInto(Value&: NewAlloc);
1678 return Error(std::move(E));
1679 });
1680 if (!NewE)
1681 return NewAlloc;
1682 return std::move(NewE);
1683 }
1684 PoolOffset = P->getOffset();
1685 LLVM_DEBUG({
1686 dbgs() << "pool-alloc addr=" << (void *)PoolOffset.get()
1687 << " size=" << Size
1688 << " end=" << (void *)(PoolOffset.get() + Size) << "\n";
1689 });
1690 return (*P)->data();
1691 }
1692 return AllocStandaloneFile(Size);
1693 };
1694
1695 DataRecordHandle Record;
1696 if (Error E =
1697 DataRecordHandle::createWithError(Alloc, I: Input).moveInto(Value&: Record))
1698 return E;
1699 assert(Record.getData().end()[0] == 0 && "Expected null-termination");
1700 assert(Record.getData() == Input.Data && "Expected initialization");
1701 assert(SK != TrieRecord::StorageKind::Unknown);
1702 assert(bool(File) != bool(PoolOffset) &&
1703 "Expected either a mapped file or a pooled offset");
1704
1705 // Check for a race before calling MappedTempFile::keep().
1706 //
1707 // Then decide what to do with the file. Better to discard than overwrite if
1708 // another thread/process has already added this.
1709 TrieRecord::Data Existing = I->Ref.load();
1710 {
1711 TrieRecord::Data NewObject{.SK: SK, .Offset: PoolOffset};
1712 if (File) {
1713 if (Existing.SK == TrieRecord::StorageKind::Unknown) {
1714 // Keep the file!
1715 if (Error E = File->keep(Name: Path))
1716 return E;
1717 } else {
1718 File.reset();
1719 }
1720 }
1721
1722 // If we didn't already see a racing/existing write, then try storing the
1723 // new object. If that races, confirm that the new value has valid storage.
1724 //
1725 // TODO: Find a way to reuse the storage from the new-but-abandoned record
1726 // handle.
1727 if (Existing.SK == TrieRecord::StorageKind::Unknown) {
1728 if (I->Ref.compare_exchange_strong(Existing, New: NewObject)) {
1729 if (FileSize)
1730 recordStandaloneSizeIncrease(SizeIncrease: *FileSize);
1731 return Error::success();
1732 }
1733 }
1734 }
1735
1736 if (Existing.SK == TrieRecord::StorageKind::Unknown)
1737 return createCorruptObjectError(ID: getDigest(I: *I));
1738
1739 // Load existing object.
1740 return Error::success();
1741}
1742
1743Error OnDiskGraphDB::storeFile(ObjectID ID, StringRef FilePath) {
1744 return storeFile(ID, FilePath, /*ImportKind=*/std::nullopt);
1745}
1746
1747Error OnDiskGraphDB::storeFile(
1748 ObjectID ID, StringRef FilePath,
1749 std::optional<InternalUpstreamImportKind> ImportKind) {
1750 auto I = getIndexProxyFromRef(Ref: getInternalRef(Ref: ID));
1751 if (LLVM_UNLIKELY(!I))
1752 return I.takeError();
1753
1754 // Early return in case the node exists.
1755 {
1756 TrieRecord::Data Existing = I->Ref.load();
1757 if (Existing.SK != TrieRecord::StorageKind::Unknown)
1758 return Error::success();
1759 }
1760
1761 auto BypassSandbox = sys::sandbox::scopedDisable();
1762
1763 uint64_t FileSize;
1764 if (std::error_code EC = sys::fs::file_size(Path: FilePath, Result&: FileSize))
1765 return createFileError(F: FilePath, EC);
1766
1767 if (FileSize <= TrieRecord::MaxEmbeddedSize) {
1768 auto Buf = MemoryBuffer::getFile(Filename: FilePath);
1769 if (!Buf)
1770 return createFileError(F: FilePath, EC: Buf.getError());
1771 return store(ID, Refs: {}, Data: arrayRefFromStringRef<char>(Input: (*Buf)->getBuffer()));
1772 }
1773
1774 UniqueTempFile UniqueTmp;
1775 auto ExpectedPath = UniqueTmp.createAndCopyFrom(ParentPath: RootPath, CopyFromPath: FilePath);
1776 if (!ExpectedPath)
1777 return ExpectedPath.takeError();
1778 StringRef TmpPath = *ExpectedPath;
1779
1780 TrieRecord::StorageKind SK;
1781 if (ImportKind.has_value()) {
1782 // Importing the file from upstream, the nul is already added if necessary.
1783 switch (*ImportKind) {
1784 case InternalUpstreamImportKind::Leaf:
1785 SK = TrieRecord::StorageKind::StandaloneLeaf;
1786 break;
1787 case InternalUpstreamImportKind::Leaf0:
1788 SK = TrieRecord::StorageKind::StandaloneLeaf0;
1789 break;
1790 }
1791 } else {
1792 bool Leaf0 = isAligned(Lhs: Align(getPageSize()), SizeInBytes: FileSize);
1793 SK = Leaf0 ? TrieRecord::StorageKind::StandaloneLeaf0
1794 : TrieRecord::StorageKind::StandaloneLeaf;
1795
1796 if (Leaf0) {
1797 // Add a nul byte at the end.
1798 std::error_code EC;
1799 raw_fd_ostream OS(TmpPath, EC, sys::fs::CD_OpenExisting,
1800 sys::fs::FA_Write, sys::fs::OF_Append);
1801 if (EC)
1802 return createFileError(F: TmpPath, EC);
1803 OS.write(C: 0);
1804 OS.close();
1805 if (OS.has_error())
1806 return createFileError(F: TmpPath, EC: OS.error());
1807 }
1808 }
1809
1810 SmallString<256> StandalonePath;
1811 getStandalonePath(Prefix: TrieRecord::getStandaloneFilePrefix(SK), IndexOffset: I->Offset,
1812 Path&: StandalonePath);
1813 if (Error E = UniqueTmp.renameTo(RenameToPath: StandalonePath))
1814 return E;
1815
1816 // Store the object reference.
1817 TrieRecord::Data Existing;
1818 {
1819 TrieRecord::Data Leaf{.SK: SK, .Offset: FileOffset()};
1820 if (I->Ref.compare_exchange_strong(Existing, New: Leaf)) {
1821 recordStandaloneSizeIncrease(SizeIncrease: FileSize);
1822 return Error::success();
1823 }
1824 }
1825
1826 // If there was a race, confirm that the new value has valid storage.
1827 if (Existing.SK == TrieRecord::StorageKind::Unknown)
1828 return createCorruptObjectError(ID: getDigest(I: *I));
1829
1830 return Error::success();
1831}
1832
1833void OnDiskGraphDB::recordStandaloneSizeIncrease(size_t SizeIncrease) {
1834 standaloneStorageSize().fetch_add(i: SizeIncrease, m: std::memory_order_relaxed);
1835}
1836
1837std::atomic<uint64_t> &OnDiskGraphDB::standaloneStorageSize() const {
1838 MutableArrayRef<uint8_t> UserHeader = DataPool.getUserHeader();
1839 assert(UserHeader.size() == sizeof(std::atomic<uint64_t>));
1840 assert(isAddrAligned(Align(8), UserHeader.data()));
1841 return *reinterpret_cast<std::atomic<uint64_t> *>(UserHeader.data());
1842}
1843
1844uint64_t OnDiskGraphDB::getStandaloneStorageSize() const {
1845 return standaloneStorageSize().load(m: std::memory_order_relaxed);
1846}
1847
1848size_t OnDiskGraphDB::getStorageSize() const {
1849 return Index.size() + DataPool.size() + getStandaloneStorageSize();
1850}
1851
1852unsigned OnDiskGraphDB::getHardStorageLimitUtilization() const {
1853 unsigned IndexPercent = Index.size() * 100ULL / Index.capacity();
1854 unsigned DataPercent = DataPool.size() * 100ULL / DataPool.capacity();
1855 return std::max(a: IndexPercent, b: DataPercent);
1856}
1857
1858Expected<std::unique_ptr<OnDiskGraphDB>>
1859OnDiskGraphDB::open(StringRef AbsPath, StringRef HashName,
1860 unsigned HashByteSize, OnDiskGraphDB *UpstreamDB,
1861 std::shared_ptr<OnDiskCASLogger> Logger,
1862 FaultInPolicy Policy) {
1863 if (std::error_code EC = sys::fs::create_directories(path: AbsPath))
1864 return createFileError(F: AbsPath, EC);
1865
1866 constexpr uint64_t MB = 1024ull * 1024ull;
1867 constexpr uint64_t GB = 1024ull * 1024ull * 1024ull;
1868
1869 uint64_t MaxIndexSize = 12 * GB;
1870 uint64_t MaxDataPoolSize = 24 * GB;
1871
1872 if (useSmallMappingSize(Path: AbsPath)) {
1873 MaxIndexSize = 1 * GB;
1874 MaxDataPoolSize = 2 * GB;
1875 }
1876
1877 auto CustomSize = getOverriddenMaxMappingSize();
1878 if (!CustomSize)
1879 return CustomSize.takeError();
1880 if (*CustomSize)
1881 MaxIndexSize = MaxDataPoolSize = **CustomSize;
1882
1883 SmallString<256> IndexPath(AbsPath);
1884 sys::path::append(path&: IndexPath, a: IndexFilePrefix + CASFormatVersion);
1885 std::optional<OnDiskTrieRawHashMap> Index;
1886 if (Error E = OnDiskTrieRawHashMap::create(
1887 Path: IndexPath, TrieName: IndexTableName + "[" + HashName + "]",
1888 NumHashBits: HashByteSize * CHAR_BIT,
1889 /*DataSize=*/sizeof(TrieRecord), MaxFileSize: MaxIndexSize,
1890 /*MinFileSize=*/NewFileInitialSize: MB, Logger)
1891 .moveInto(Value&: Index))
1892 return std::move(E);
1893
1894 uint32_t UserHeaderSize = sizeof(std::atomic<uint64_t>);
1895
1896 SmallString<256> DataPoolPath(AbsPath);
1897 sys::path::append(path&: DataPoolPath, a: DataPoolFilePrefix + CASFormatVersion);
1898 std::optional<OnDiskDataAllocator> DataPool;
1899 StringRef PolicyName =
1900 Policy == FaultInPolicy::SingleNode ? "single" : "full";
1901 if (Error E = OnDiskDataAllocator::create(
1902 Path: DataPoolPath,
1903 TableName: DataPoolTableName + "[" + HashName + "]" + PolicyName,
1904 MaxFileSize: MaxDataPoolSize, /*MinFileSize=*/NewFileInitialSize: MB, UserHeaderSize, Logger,
1905 UserHeaderInit: [](void *UserHeaderPtr) {
1906 new (UserHeaderPtr) std::atomic<uint64_t>(0);
1907 })
1908 .moveInto(Value&: DataPool))
1909 return std::move(E);
1910 if (DataPool->getUserHeader().size() != UserHeaderSize)
1911 return createStringError(EC: llvm::errc::argument_out_of_domain,
1912 S: "unexpected user header in '" + DataPoolPath +
1913 "'");
1914
1915 return std::unique_ptr<OnDiskGraphDB>(
1916 new OnDiskGraphDB(AbsPath, std::move(*Index), std::move(*DataPool),
1917 UpstreamDB, Policy, std::move(Logger)));
1918}
1919
1920OnDiskGraphDB::OnDiskGraphDB(StringRef RootPath, OnDiskTrieRawHashMap Index,
1921 OnDiskDataAllocator DataPool,
1922 OnDiskGraphDB *UpstreamDB, FaultInPolicy Policy,
1923 std::shared_ptr<OnDiskCASLogger> Logger)
1924 : Index(std::move(Index)), DataPool(std::move(DataPool)),
1925 RootPath(RootPath.str()), UpstreamDB(UpstreamDB), FIPolicy(Policy),
1926 Logger(std::move(Logger)) {
1927 /// Lifetime for "big" objects not in DataPool.
1928 ///
1929 /// NOTE: Could use ThreadSafeTrieRawHashMap here. For now, doing something
1930 /// simpler on the assumption there won't be much contention since most data
1931 /// is not big. If there is contention, and we've already fixed ObjectProxy
1932 /// object handles to be cheap enough to use consistently, the fix might be
1933 /// to use better use of them rather than optimizing this map.
1934 ///
1935 /// FIXME: Figure out the right number of shards, if any.
1936 StandaloneData = new StandaloneDataMapTy();
1937}
1938
1939OnDiskGraphDB::~OnDiskGraphDB() {
1940 delete static_cast<StandaloneDataMapTy *>(StandaloneData);
1941}
1942
1943Error OnDiskGraphDB::importFullTree(ObjectID PrimaryID,
1944 ObjectHandle UpstreamNode) {
1945 // Copies the full CAS tree from upstream. Uses depth-first copying to protect
1946 // against the process dying during importing and leaving the database with an
1947 // incomplete tree. Note that if the upstream has missing nodes then the tree
1948 // will be copied with missing nodes as well, it won't be considered an error.
1949 struct UpstreamCursor {
1950 ObjectHandle Node;
1951 size_t RefsCount;
1952 object_refs_iterator RefI;
1953 object_refs_iterator RefE;
1954 };
1955 /// Keeps track of the state of visitation for current node and all of its
1956 /// parents.
1957 SmallVector<UpstreamCursor, 16> CursorStack;
1958 /// Keeps track of the currently visited nodes as they are imported into
1959 /// primary database, from current node and its parents. When a node is
1960 /// entered for visitation it appends its own ID, then appends referenced IDs
1961 /// as they get imported. When a node is fully imported it removes the
1962 /// referenced IDs from the bottom of the stack which leaves its own ID at the
1963 /// bottom, adding to the list of referenced IDs for the parent node.
1964 SmallVector<ObjectID, 128> PrimaryNodesStack;
1965
1966 auto enqueueNode = [&](ObjectID PrimaryID, std::optional<ObjectHandle> Node) {
1967 PrimaryNodesStack.push_back(Elt: PrimaryID);
1968 if (!Node)
1969 return;
1970 auto Refs = UpstreamDB->getObjectRefs(Node: *Node);
1971 CursorStack.push_back(
1972 Elt: {.Node: *Node, .RefsCount: (size_t)llvm::size(Range&: Refs), .RefI: Refs.begin(), .RefE: Refs.end()});
1973 };
1974
1975 enqueueNode(PrimaryID, UpstreamNode);
1976
1977 while (!CursorStack.empty()) {
1978 UpstreamCursor &Cur = CursorStack.back();
1979 if (Cur.RefI == Cur.RefE) {
1980 // Copy the node data into the primary store.
1981
1982 // The bottom of \p PrimaryNodesStack contains the primary ID for the
1983 // current node plus the list of imported referenced IDs.
1984 assert(PrimaryNodesStack.size() >= Cur.RefsCount + 1);
1985 ObjectID PrimaryID = *(PrimaryNodesStack.end() - Cur.RefsCount - 1);
1986 auto PrimaryRefs = ArrayRef(PrimaryNodesStack)
1987 .slice(N: PrimaryNodesStack.size() - Cur.RefsCount);
1988 if (Error E = importUpstreamData(PrimaryID, PrimaryRefs, UpstreamNode: Cur.Node))
1989 return E;
1990 // Remove the current node and its IDs from the stack.
1991 PrimaryNodesStack.truncate(N: PrimaryNodesStack.size() - Cur.RefsCount);
1992 CursorStack.pop_back();
1993 continue;
1994 }
1995
1996 ObjectID UpstreamID = *(Cur.RefI++);
1997 auto PrimaryID = getReference(Hash: UpstreamDB->getDigest(Ref: UpstreamID));
1998 if (LLVM_UNLIKELY(!PrimaryID))
1999 return PrimaryID.takeError();
2000 if (containsObject(Ref: *PrimaryID, /*CheckUpstream=*/false)) {
2001 // This \p ObjectID already exists in the primary. Either it was imported
2002 // via \p importFullTree or the client created it, in which case the
2003 // client takes responsibility for how it was formed.
2004 enqueueNode(*PrimaryID, std::nullopt);
2005 continue;
2006 }
2007 Expected<std::optional<ObjectHandle>> UpstreamNode =
2008 UpstreamDB->load(ExternalRef: UpstreamID);
2009 if (!UpstreamNode)
2010 return UpstreamNode.takeError();
2011 enqueueNode(*PrimaryID, *UpstreamNode);
2012 }
2013
2014 assert(PrimaryNodesStack.size() == 1);
2015 assert(PrimaryNodesStack.front() == PrimaryID);
2016 return Error::success();
2017}
2018
2019Error OnDiskGraphDB::importSingleNode(ObjectID PrimaryID,
2020 ObjectHandle UpstreamNode) {
2021 // Copies only a single node, it doesn't copy the referenced nodes.
2022
2023 auto UpstreamRefs = UpstreamDB->getObjectRefs(Node: UpstreamNode);
2024 SmallVector<ObjectID, 64> Refs;
2025 Refs.reserve(N: llvm::size(Range&: UpstreamRefs));
2026 for (ObjectID UpstreamRef : UpstreamRefs) {
2027 auto Ref = getReference(Hash: UpstreamDB->getDigest(Ref: UpstreamRef));
2028 if (LLVM_UNLIKELY(!Ref))
2029 return Ref.takeError();
2030 Refs.push_back(Elt: *Ref);
2031 }
2032
2033 return importUpstreamData(PrimaryID, PrimaryRefs: Refs, UpstreamNode);
2034}
2035
2036Error OnDiskGraphDB::importUpstreamData(ObjectID PrimaryID,
2037 ArrayRef<ObjectID> PrimaryRefs,
2038 ObjectHandle UpstreamNode) {
2039 // If there are references we can't copy an upstream's standalone file because
2040 // we need to re-resolve the reference offsets it contains.
2041 if (PrimaryRefs.empty()) {
2042 auto FBData = UpstreamDB->getInternalFileBackedObjectData(Node: UpstreamNode);
2043 if (FBData.FileInfo.has_value()) {
2044 // Disk-space optimization, import the file directly since it is a
2045 // standalone leaf.
2046 return storeFile(
2047 ID: PrimaryID, FilePath: FBData.FileInfo->FilePath,
2048 /*InternalUpstreamImport=*/ImportKind: FBData.FileInfo->IsFileNulTerminated
2049 ? InternalUpstreamImportKind::Leaf0
2050 : InternalUpstreamImportKind::Leaf);
2051 }
2052 }
2053
2054 auto Data = UpstreamDB->getObjectData(Node: UpstreamNode);
2055 return store(ID: PrimaryID, Refs: PrimaryRefs, Data);
2056}
2057
2058Expected<std::optional<ObjectHandle>>
2059OnDiskGraphDB::faultInFromUpstream(ObjectID PrimaryID) {
2060 if (!UpstreamDB)
2061 return std::nullopt;
2062
2063 auto UpstreamID = UpstreamDB->getReference(Hash: getDigest(Ref: PrimaryID));
2064 if (LLVM_UNLIKELY(!UpstreamID))
2065 return UpstreamID.takeError();
2066
2067 Expected<std::optional<ObjectHandle>> UpstreamNode =
2068 UpstreamDB->load(ExternalRef: *UpstreamID);
2069 if (!UpstreamNode)
2070 return UpstreamNode.takeError();
2071 if (!*UpstreamNode)
2072 return std::nullopt;
2073
2074 if (Error E = FIPolicy == FaultInPolicy::SingleNode
2075 ? importSingleNode(PrimaryID, UpstreamNode: **UpstreamNode)
2076 : importFullTree(PrimaryID, UpstreamNode: **UpstreamNode))
2077 return std::move(E);
2078 return load(ExternalRef: PrimaryID);
2079}
2080