LLVM 22.0.0git
InMemoryCAS.cpp
Go to the documentation of this file.
1//===- InMemoryCAS.cpp ------------------------------------------*- C++ -*-===//
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#include "BuiltinCAS.h"
17
18using namespace llvm;
19using namespace llvm::cas;
20using namespace llvm::cas::builtin;
21
22namespace {
23
24class InMemoryObject;
25
26/// Index of referenced IDs (map: Hash -> InMemoryObject*). Uses
27/// LazyAtomicPointer to coordinate creation of objects.
28using InMemoryIndexT =
30 sizeof(HashType)>;
31
32/// Values in \a InMemoryIndexT. \a InMemoryObject's point at this to access
33/// their hash.
34using InMemoryIndexValueT = InMemoryIndexT::value_type;
35
36/// Builtin InMemory CAS that stores CAS object in the memory.
37class InMemoryObject {
38public:
39 enum class Kind {
40 /// Node with refs and data.
41 RefNode,
42
43 /// Node with refs and data co-allocated.
44 InlineNode,
45
46 Max = InlineNode,
47 };
48
49 Kind getKind() const { return IndexAndKind.getInt(); }
50 const InMemoryIndexValueT &getIndex() const {
51 assert(IndexAndKind.getPointer());
52 return *IndexAndKind.getPointer();
53 }
54
55 ArrayRef<uint8_t> getHash() const { return getIndex().Hash; }
56
57 InMemoryObject() = delete;
58 InMemoryObject(InMemoryObject &&) = delete;
59 InMemoryObject(const InMemoryObject &) = delete;
60
61protected:
62 InMemoryObject(Kind K, const InMemoryIndexValueT &I) : IndexAndKind(&I, K) {}
63
64private:
65 enum Counts : int {
66 NumKindBits = 2,
67 };
69 static_assert((1U << NumKindBits) <= alignof(InMemoryIndexValueT),
70 "Kind will clobber pointer");
71 static_assert(((int)Kind::Max >> NumKindBits) == 0, "Kind will be truncated");
72
73public:
74 ArrayRef<char> getData() const;
75
77};
78
79class InMemoryRefObject final : public InMemoryObject {
80public:
81 static constexpr Kind KindValue = Kind::RefNode;
82 static bool classof(const InMemoryObject *O) {
83 return O->getKind() == KindValue;
84 }
85
86 ArrayRef<const InMemoryObject *> getRefsImpl() const { return Refs; }
87 ArrayRef<const InMemoryObject *> getRefs() const { return Refs; }
88 ArrayRef<char> getDataImpl() const { return Data; }
89 ArrayRef<char> getData() const { return Data; }
90
91 static InMemoryRefObject &create(function_ref<void *(size_t Size)> Allocate,
92 const InMemoryIndexValueT &I,
94 ArrayRef<char> Data) {
95 void *Mem = Allocate(sizeof(InMemoryRefObject));
96 return *new (Mem) InMemoryRefObject(I, Refs, Data);
97 }
98
99private:
100 InMemoryRefObject(const InMemoryIndexValueT &I,
102 : InMemoryObject(KindValue, I), Refs(Refs), Data(Data) {
103 assert(isAddrAligned(Align(8), this) && "Expected 8-byte alignment");
104 assert(isAddrAligned(Align(8), Data.data()) && "Expected 8-byte alignment");
105 assert(*Data.end() == 0 && "Expected null-termination");
106 }
107
109 ArrayRef<char> Data;
110};
111
112class InMemoryInlineObject final
113 : public InMemoryObject,
114 public TrailingObjects<InMemoryInlineObject, const InMemoryObject *,
115 char> {
116public:
117 static constexpr Kind KindValue = Kind::InlineNode;
118 static bool classof(const InMemoryObject *O) {
119 return O->getKind() == KindValue;
120 }
121
122 ArrayRef<const InMemoryObject *> getRefs() const { return getRefsImpl(); }
123 ArrayRef<const InMemoryObject *> getRefsImpl() const {
124 return ArrayRef(getTrailingObjects<const InMemoryObject *>(), NumRefs);
125 }
126
127 ArrayRef<char> getData() const { return getDataImpl(); }
128 ArrayRef<char> getDataImpl() const {
129 return ArrayRef(getTrailingObjects<char>(), DataSize);
130 }
131
132 static InMemoryInlineObject &
133 create(function_ref<void *(size_t Size)> Allocate,
134 const InMemoryIndexValueT &I, ArrayRef<const InMemoryObject *> Refs,
135 ArrayRef<char> Data) {
136 void *Mem = Allocate(sizeof(InMemoryInlineObject) +
137 sizeof(uintptr_t) * Refs.size() + Data.size() + 1);
138 return *new (Mem) InMemoryInlineObject(I, Refs, Data);
139 }
140
141 size_t numTrailingObjects(OverloadToken<const InMemoryObject *>) const {
142 return NumRefs;
143 }
144
145private:
146 InMemoryInlineObject(const InMemoryIndexValueT &I,
148 ArrayRef<char> Data)
149 : InMemoryObject(KindValue, I), NumRefs(Refs.size()),
150 DataSize(Data.size()) {
151 auto *BeginRefs = reinterpret_cast<const InMemoryObject **>(this + 1);
152 llvm::copy(Refs, BeginRefs);
153 auto *BeginData = reinterpret_cast<char *>(BeginRefs + NumRefs);
154 llvm::copy(Data, BeginData);
155 BeginData[Data.size()] = 0;
156 }
157 uint32_t NumRefs;
158 uint32_t DataSize;
159};
160
161/// In-memory CAS database and action cache (the latter should be separated).
162class InMemoryCAS : public BuiltinCAS {
163public:
166 ArrayRef<char> Data) final;
167
170 sys::fs::mapped_file_region Map) override;
171
172 CASID getID(const InMemoryIndexValueT &I) const {
173 StringRef Hash = toStringRef(I.Hash);
174 return CASID::create(&getContext(), Hash);
175 }
176 CASID getID(const InMemoryObject &O) const { return getID(O.getIndex()); }
177
178 ObjectHandle getObjectHandle(const InMemoryObject &Node) const {
179 assert(!(reinterpret_cast<uintptr_t>(&Node) & 0x1ULL));
180 return makeObjectHandle(reinterpret_cast<uintptr_t>(&Node));
181 }
182
184 return getObjectHandle(asInMemoryObject(Ref));
185 }
186
187 InMemoryIndexValueT &indexHash(ArrayRef<uint8_t> Hash) {
188 return *Index.insertLazy(
189 Hash, [](auto ValueConstructor) { ValueConstructor.emplace(nullptr); });
190 }
191
192 /// TODO: Consider callers to actually do an insert and to return a handle to
193 /// the slot in the trie.
194 const InMemoryObject *getInMemoryObject(CASID ID) const {
195 assert(ID.getContext().getHashSchemaIdentifier() ==
196 getContext().getHashSchemaIdentifier() &&
197 "Expected ID from same hash schema");
198 if (InMemoryIndexT::const_pointer P = Index.find(ID.getHash()))
199 return P->Data;
200 return nullptr;
201 }
202
203 const InMemoryObject &getInMemoryObject(ObjectHandle OH) const {
204 return *reinterpret_cast<const InMemoryObject *>(
205 (uintptr_t)OH.getInternalRef(*this));
206 }
207
208 const InMemoryObject &asInMemoryObject(ReferenceBase Ref) const {
209 uintptr_t P = Ref.getInternalRef(*this);
210 return *reinterpret_cast<const InMemoryObject *>(P);
211 }
212 ObjectRef toReference(const InMemoryObject &O) const {
213 return makeObjectRef(reinterpret_cast<uintptr_t>(&O));
214 }
215
216 CASID getID(ObjectRef Ref) const final { return getIDImpl(Ref); }
217 CASID getIDImpl(ReferenceBase Ref) const {
218 return getID(asInMemoryObject(Ref));
219 }
220
221 std::optional<ObjectRef> getReference(const CASID &ID) const final {
222 if (const InMemoryObject *Object = getInMemoryObject(ID))
223 return toReference(*Object);
224 return std::nullopt;
225 }
226
227 Expected<bool> isMaterialized(ObjectRef Ref) const final { return true; }
228
230 return cast<InMemoryObject>(asInMemoryObject(Node)).getData();
231 }
232
233 InMemoryCAS() = default;
234
235private:
236 size_t getNumRefs(ObjectHandle Node) const final {
237 return getInMemoryObject(Node).getRefs().size();
238 }
239 ObjectRef readRef(ObjectHandle Node, size_t I) const final {
240 return toReference(*getInMemoryObject(Node).getRefs()[I]);
241 }
243 function_ref<Error(ObjectRef)> Callback) const final;
244
245 /// Index of referenced IDs (map: Hash -> InMemoryObject*). Mapped to nullptr
246 /// as a convenient way to store hashes.
247 ///
248 /// - Insert nullptr on lookups.
249 /// - InMemoryObject points back to here.
250 InMemoryIndexT Index;
251
254 MemoryMaps;
255};
256
257} // end anonymous namespace
258
259ArrayRef<char> InMemoryObject::getData() const {
260 if (auto *Derived = dyn_cast<InMemoryRefObject>(this))
261 return Derived->getDataImpl();
262 return cast<InMemoryInlineObject>(this)->getDataImpl();
263}
264
265ArrayRef<const InMemoryObject *> InMemoryObject::getRefs() const {
266 if (auto *Derived = dyn_cast<InMemoryRefObject>(this))
267 return Derived->getRefsImpl();
268 return cast<InMemoryInlineObject>(this)->getRefsImpl();
269}
270
272InMemoryCAS::storeFromNullTerminatedRegion(ArrayRef<uint8_t> ComputedHash,
274 // Look up the hash in the index, initializing to nullptr if it's new.
275 ArrayRef<char> Data(Map.data(), Map.size());
276 auto &I = indexHash(ComputedHash);
277
278 // Load or generate.
279 auto Allocator = [&](size_t Size) -> void * {
280 return Objects.Allocate(Size, alignof(InMemoryObject));
281 };
282 auto Generator = [&]() -> const InMemoryObject * {
283 return &InMemoryRefObject::create(Allocator, I, {}, Data);
284 };
285 const InMemoryObject &Node =
286 cast<InMemoryObject>(I.Data.loadOrGenerate(Generator));
287
288 // Save Map if the winning node uses it.
289 if (auto *RefNode = dyn_cast<InMemoryRefObject>(&Node))
290 if (RefNode->getData().data() == Map.data())
291 new (MemoryMaps.Allocate(1)) sys::fs::mapped_file_region(std::move(Map));
292
293 return toReference(Node);
294}
295
296Expected<ObjectRef> InMemoryCAS::storeImpl(ArrayRef<uint8_t> ComputedHash,
298 ArrayRef<char> Data) {
299 // Look up the hash in the index, initializing to nullptr if it's new.
300 auto &I = indexHash(ComputedHash);
301
302 // Create the node.
304 for (ObjectRef Ref : Refs)
305 InternalRefs.push_back(&asInMemoryObject(Ref));
306 auto Allocator = [&](size_t Size) -> void * {
307 return Objects.Allocate(Size, alignof(InMemoryObject));
308 };
309 auto Generator = [&]() -> const InMemoryObject * {
310 return &InMemoryInlineObject::create(Allocator, I, InternalRefs, Data);
311 };
312 return toReference(cast<InMemoryObject>(I.Data.loadOrGenerate(Generator)));
313}
314
315Error InMemoryCAS::forEachRef(ObjectHandle Handle,
316 function_ref<Error(ObjectRef)> Callback) const {
317 auto &Node = getInMemoryObject(Handle);
318 for (const InMemoryObject *Ref : Node.getRefs())
319 if (Error E = Callback(toReference(*Ref)))
320 return E;
321 return Error::success();
322}
323
324std::unique_ptr<ObjectStore> cas::createInMemoryCAS() {
325 return std::make_unique<InMemoryCAS>();
326}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the BumpPtrAllocator interface.
uint64_t Size
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
This file defines the PointerIntPair class.
Basic Register Allocator
This header defines support for implementing classes that have some trailing object (or arrays of obj...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:147
Lightweight error class with error context and mandatory checking.
Definition: Error.h:159
static ErrorSuccess success()
Create a success value.
Definition: Error.h:336
Tagged union holding either a T or a Error.
Definition: Error.h:485
PointerIntPair - This class implements a pair of a pointer and small integer.
void push_back(const T &Elt)
Definition: SmallVector.h:414
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1197
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:55
Thread-safe allocator adaptor.
Lock-free thread-safe hash-mapped trie.
See the file comment for details on the usage of the TrailingObjects type.
Unique identifier for a CAS object.
Definition: CASID.h:58
static CASID create(const CASContext *Context, StringRef Hash)
Create CASID from CASContext and raw hash bytes.
Definition: CASID.h:117
Handle to a loaded object in a ObjectStore instance.
Definition: CASReference.h:150
Reference to an object in an ObjectStore instance.
Definition: CASReference.h:108
virtual Expected< bool > isMaterialized(ObjectRef Ref) const =0
virtual CASID getID(ObjectRef Ref) const =0
Get an ID for Ref.
virtual Expected< std::optional< ObjectHandle > > loadIfExists(ObjectRef Ref)=0
Load the object referenced by Ref.
const CASContext & getContext() const
Get CASContext.
Definition: ObjectStore.h:222
virtual ObjectRef readRef(ObjectHandle Node, size_t I) const =0
virtual size_t getNumRefs(ObjectHandle Node) const =0
virtual std::optional< ObjectRef > getReference(const CASID &ID) const =0
Get an existing reference to the object called ID.
virtual Error forEachRef(ObjectHandle Node, function_ref< Error(ObjectRef)> Callback) const =0
Methods for handling objects.
Base class for references to things in ObjectStore.
Definition: CASReference.h:27
uint64_t getInternalRef(const ObjectStore &ExpectedCAS) const
Get an internal reference.
Definition: CASReference.h:36
Common base class for builtin CAS implementations using the same CASContext.
Definition: BuiltinCAS.h:21
virtual Expected< ObjectRef > storeFromNullTerminatedRegion(ArrayRef< uint8_t > ComputedHash, sys::fs::mapped_file_region Map)
Definition: BuiltinCAS.h:34
virtual ArrayRef< char > getDataConst(ObjectHandle Node) const =0
Both builtin CAS implementations provide lifetime for free, so this can be const, and readData() and ...
virtual Expected< ObjectRef > storeImpl(ArrayRef< uint8_t > ComputedHash, ArrayRef< ObjectRef > Refs, ArrayRef< char > Data)=0
An efficient, type-erasing, non-owning reference to a callable.
This class represents a memory mapped file.
Definition: FileSystem.h:1287
decltype(HasherT::hash(std::declval< ArrayRef< uint8_t > & >())) HashType
std::unique_ptr< ObjectStore > createInMemoryCAS()
StringRef toStringRef(const std::optional< DWARFFormValue > &V, StringRef Default={})
Take an optional DWARFFormValue and try to extract a string value from it.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1702
@ Ref
The access may reference the value stored in memory.
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1854
bool isAddrAligned(Align Lhs, const void *Addr)
Checks that Addr is a multiple of the alignment.
Definition: Alignment.h:150
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39