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#include "llvm/CAS/ObjectStore.h"
10#include "llvm/ADT/DenseSet.h"
11#include "llvm/ADT/ScopeExit.h"
12#include "llvm/Support/Debug.h"
13#include "llvm/Support/Errc.h"
14#include "llvm/Support/FileSystem.h"
15#include "llvm/Support/IOSandbox.h"
16#include "llvm/Support/MemoryBuffer.h"
17#include "llvm/Support/Path.h"
18#include <deque>
19
20using namespace llvm;
21using namespace llvm::cas;
22
23void CASContext::anchor() {}
24void ObjectStore::anchor() {}
25
26LLVM_DUMP_METHOD void CASID::dump() const { print(OS&: dbgs()); }
27LLVM_DUMP_METHOD void ObjectStore::dump() const { print(dbgs()); }
28LLVM_DUMP_METHOD void ObjectRef::dump() const { print(OS&: dbgs()); }
29LLVM_DUMP_METHOD void ObjectHandle::dump() const { print(OS&: dbgs()); }
30
31std::string CASID::toString() const {
32 std::string S;
33 raw_string_ostream(S) << *this;
34 return S;
35}
36
37static void printReferenceBase(raw_ostream &OS, StringRef Kind,
38 uint64_t InternalRef, std::optional<CASID> ID) {
39 OS << Kind << "=" << InternalRef;
40 if (ID)
41 OS << "[" << *ID << "]";
42}
43
44void ReferenceBase::print(raw_ostream &OS, const ObjectHandle &This) const {
45 assert(this == &This);
46 printReferenceBase(OS, Kind: "object-handle", InternalRef, ID: std::nullopt);
47}
48
49void ReferenceBase::print(raw_ostream &OS, const ObjectRef &This) const {
50 assert(this == &This);
51
52 std::optional<CASID> ID;
53#if LLVM_ENABLE_ABI_BREAKING_CHECKS
54 if (CAS)
55 ID = CAS->getID(This);
56#endif
57 printReferenceBase(OS, Kind: "object-ref", InternalRef, ID);
58}
59
60Expected<ObjectHandle> ObjectStore::load(ObjectRef Ref) {
61 std::optional<ObjectHandle> Handle;
62 if (Error E = loadIfExists(Ref).moveInto(Value&: Handle))
63 return std::move(E);
64 if (!Handle)
65 return createStringError(EC: errc::invalid_argument,
66 S: "missing object '" + getID(Ref).toString() + "'");
67 return *Handle;
68}
69
70std::unique_ptr<MemoryBuffer>
71ObjectStore::getMemoryBuffer(ObjectHandle Node, StringRef Name,
72 bool RequiresNullTerminator) {
73 return MemoryBuffer::getMemBuffer(
74 InputData: toStringRef(Input: getData(Node, RequiresNullTerminator)), BufferName: Name,
75 RequiresNullTerminator);
76}
77
78std::unique_ptr<MemoryBuffer>
79ObjectStore::getStandaloneMemoryBuffer(ObjectHandle Node, StringRef Name,
80 bool RequiresNullTerminator) {
81 return getStandaloneMemoryBufferImpl(Node, Name, RequiresNullTerminator);
82}
83
84std::unique_ptr<MemoryBuffer>
85ObjectStore::getStandaloneMemoryBufferImpl(ObjectHandle Node, StringRef Name,
86 bool RequiresNullTerminator) {
87 return MemoryBuffer::getMemBufferCopy(
88 InputData: toStringRef(Input: getData(Node, RequiresNullTerminator)), BufferName: Name);
89}
90
91void ObjectStore::readRefs(ObjectHandle Node,
92 SmallVectorImpl<ObjectRef> &Refs) const {
93 consumeError(Err: forEachRef(Node, Callback: [&Refs](ObjectRef Ref) -> Error {
94 Refs.push_back(Elt: Ref);
95 return Error::success();
96 }));
97}
98
99Expected<ObjectProxy> ObjectStore::getProxy(const CASID &ID) {
100 std::optional<ObjectRef> Ref = getReference(ID);
101 if (!Ref)
102 return createUnknownObjectError(ID);
103
104 return getProxy(Ref: *Ref);
105}
106
107Expected<ObjectProxy> ObjectStore::getProxy(ObjectRef Ref) {
108 std::optional<ObjectHandle> H;
109 if (Error E = load(Ref).moveInto(Value&: H))
110 return std::move(E);
111
112 return ObjectProxy::load(CAS&: *this, Ref, Node: *H);
113}
114
115Expected<std::optional<ObjectProxy>>
116ObjectStore::getProxyIfExists(ObjectRef Ref) {
117 std::optional<ObjectHandle> H;
118 if (Error E = loadIfExists(Ref).moveInto(Value&: H))
119 return std::move(E);
120 if (!H)
121 return std::nullopt;
122 return ObjectProxy::load(CAS&: *this, Ref, Node: *H);
123}
124
125Error ObjectStore::createUnknownObjectError(const CASID &ID) {
126 return createStringError(EC: std::make_error_code(e: std::errc::invalid_argument),
127 S: "unknown object '" + ID.toString() + "'");
128}
129
130Expected<ObjectProxy> ObjectStore::createProxy(ArrayRef<ObjectRef> Refs,
131 StringRef Data) {
132 Expected<ObjectRef> Ref = store(Refs, Data: arrayRefFromStringRef<char>(Input: Data));
133 if (!Ref)
134 return Ref.takeError();
135 return getProxy(Ref: *Ref);
136}
137
138Expected<ObjectRef>
139ObjectStore::storeFromOpenFileImpl(sys::fs::file_t FD,
140 std::optional<sys::fs::file_status> Status) {
141 // TODO: For the on-disk CAS implementation use cloning to store it as a
142 // standalone file if the file-system supports it and the file is large.
143 uint64_t Size = Status ? Status->getSize() : -1;
144 auto Buffer = MemoryBuffer::getOpenFile(FD, /*Filename=*/"", FileSize: Size);
145 if (!Buffer)
146 return errorCodeToError(EC: Buffer.getError());
147
148 return store(Refs: {}, Data: arrayRefFromStringRef<char>(Input: (*Buffer)->getBuffer()));
149}
150
151Expected<ObjectRef> ObjectStore::storeFromFile(StringRef Path) {
152 auto BypassSandbox = sys::sandbox::scopedDisable();
153
154 sys::fs::file_t FD;
155 if (Error E = sys::fs::openNativeFileForRead(Name: Path).moveInto(Value&: FD))
156 return E;
157 auto CloseFile = scope_exit([&FD] { sys::fs::closeFile(F&: FD); });
158 return storeFromOpenFile(FD);
159}
160
161Error ObjectStore::exportDataToFile(ObjectHandle Node, StringRef Path) const {
162 auto BypassSandbox = sys::sandbox::scopedDisable();
163
164 SmallString<256> TmpPath;
165 SmallString<256> Model;
166 Model += sys::path::parent_path(path: Path);
167 sys::path::append(path&: Model, a: "%%%%%%%.tmp");
168 if (std::error_code EC = sys::fs::createUniqueFile(Model, ResultPath&: TmpPath))
169 return createFileError(F: Model, EC);
170 auto RemoveTmpFile = scope_exit([&] {
171 if (!TmpPath.empty())
172 sys::fs::remove(path: TmpPath);
173 });
174
175 ArrayRef<char> Data = getData(Node);
176 std::error_code EC;
177 raw_fd_ostream FS(TmpPath, EC);
178 if (EC)
179 return createFileError(F: TmpPath, EC);
180 FS.write(Ptr: Data.begin(), Size: Data.size());
181 FS.close();
182 if (FS.has_error())
183 return createFileError(F: TmpPath, EC: FS.error());
184
185 if (std::error_code EC = sys::fs::rename(from: TmpPath, to: Path))
186 return createFileError(F: Path, EC);
187 TmpPath.clear();
188
189 return Error::success();
190}
191
192Error ObjectStore::validateTree(ObjectRef Root) {
193 SmallDenseSet<ObjectRef> ValidatedRefs;
194 SmallVector<ObjectRef, 16> RefsToValidate;
195 RefsToValidate.push_back(Elt: Root);
196
197 while (!RefsToValidate.empty()) {
198 ObjectRef Ref = RefsToValidate.pop_back_val();
199 auto [I, Inserted] = ValidatedRefs.insert(V: Ref);
200 if (!Inserted)
201 continue; // already validated.
202 if (Error E = validateObject(ID: getID(Ref)))
203 return E;
204 Expected<ObjectHandle> Obj = load(Ref);
205 if (!Obj)
206 return Obj.takeError();
207 if (Error E = forEachRef(Node: *Obj, Callback: [&RefsToValidate](ObjectRef R) -> Error {
208 RefsToValidate.push_back(Elt: R);
209 return Error::success();
210 }))
211 return E;
212 }
213 return Error::success();
214}
215
216Expected<ObjectRef> ObjectStore::importObject(ObjectStore &Upstream,
217 ObjectRef Other) {
218 // Copy the full CAS tree from upstream with depth-first ordering to ensure
219 // all the child nodes are available in downstream CAS before inserting
220 // current object. This uses a similar algorithm as
221 // `OnDiskGraphDB::importFullTree` but doesn't assume the upstream CAS schema
222 // so it can be used to import from any other ObjectStore reguardless of the
223 // CAS schema.
224
225 // There is no work to do if importing from self.
226 if (this == &Upstream)
227 return Other;
228
229 /// Keeps track of the state of visitation for current node and all of its
230 /// parents. Upstream Cursor holds information only from upstream CAS.
231 struct UpstreamCursor {
232 ObjectRef Ref;
233 ObjectHandle Node;
234 size_t RefsCount;
235 std::deque<ObjectRef> Refs;
236 };
237 SmallVector<UpstreamCursor, 16> CursorStack;
238 /// PrimaryNodeStack holds the ObjectRef of the current CAS, with nodes either
239 /// just stored in the CAS or nodes already exists in the current CAS.
240 SmallVector<ObjectRef, 128> PrimaryRefStack;
241 /// A map from upstream ObjectRef to current ObjectRef.
242 llvm::DenseMap<ObjectRef, ObjectRef> CreatedObjects;
243
244 auto enqueueNode = [&](ObjectRef Ref, ObjectHandle Node) {
245 unsigned NumRefs = Upstream.getNumRefs(Node);
246 std::deque<ObjectRef> Refs;
247 for (unsigned I = 0; I < NumRefs; ++I)
248 Refs.push_back(x: Upstream.readRef(Node, I));
249
250 CursorStack.push_back(Elt: {.Ref: Ref, .Node: Node, .RefsCount: NumRefs, .Refs: std::move(Refs)});
251 };
252
253 auto UpstreamHandle = Upstream.load(Ref: Other);
254 if (!UpstreamHandle)
255 return UpstreamHandle.takeError();
256 enqueueNode(Other, *UpstreamHandle);
257
258 while (!CursorStack.empty()) {
259 UpstreamCursor &Cur = CursorStack.back();
260 if (Cur.Refs.empty()) {
261 // Copy the node data into the primary store.
262 // The bottom of \p PrimaryRefStack contains the ObjectRef for the
263 // current node.
264 assert(PrimaryRefStack.size() >= Cur.RefsCount);
265 auto Refs = ArrayRef(PrimaryRefStack)
266 .slice(N: PrimaryRefStack.size() - Cur.RefsCount);
267 auto NewNode = store(Refs, Data: Upstream.getData(Node: Cur.Node));
268 if (!NewNode)
269 return NewNode.takeError();
270
271 // Remove the current node and its IDs from the stack.
272 PrimaryRefStack.truncate(N: PrimaryRefStack.size() - Cur.RefsCount);
273
274 // Push new node into created objects.
275 PrimaryRefStack.push_back(Elt: *NewNode);
276 CreatedObjects.try_emplace(Key: Cur.Ref, Args&: *NewNode);
277
278 // Pop the cursor in the end after all uses.
279 CursorStack.pop_back();
280 continue;
281 }
282
283 // Check if the node exists already.
284 auto CurrentID = Cur.Refs.front();
285 Cur.Refs.pop_front();
286 auto Ref = CreatedObjects.find(Val: CurrentID);
287 if (Ref != CreatedObjects.end()) {
288 // If exists already, just need to enqueue the primary node.
289 PrimaryRefStack.push_back(Elt: Ref->second);
290 continue;
291 }
292
293 // Load child.
294 auto PrimaryID = Upstream.load(Ref: CurrentID);
295 if (LLVM_UNLIKELY(!PrimaryID))
296 return PrimaryID.takeError();
297
298 enqueueNode(CurrentID, *PrimaryID);
299 }
300
301 assert(PrimaryRefStack.size() == 1);
302 return PrimaryRefStack.front();
303}
304
305std::unique_ptr<MemoryBuffer>
306ObjectProxy::getMemoryBuffer(StringRef Name,
307 bool RequiresNullTerminator) const {
308 return CAS->getMemoryBuffer(Node: H, Name, RequiresNullTerminator);
309}
310
311std::unique_ptr<MemoryBuffer>
312ObjectProxy::getStandaloneMemoryBuffer(StringRef Name,
313 bool RequiresNullTerminator) const {
314 return CAS->getStandaloneMemoryBuffer(Node: H, Name, RequiresNullTerminator);
315}
316