lib/content/src/memory/store.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const alloc_phase = @import("alloc_phase");
2 const std = @import("std");
3
4 const content = @import("../root.zig");
5
6 /// One binding: a reference and the offset at which its bytes start in the
7 /// content region. Entries make up the metadata array the caller sizes. The
8 /// entry size has to equal the metadata entry size a capacity was derived with,
9 /// and a compile-time check refuses the build otherwise.
10 pub const Entry = struct {
11 reference: content.Reference,
12 offset: u64,
13 };
14
15 comptime {
16 if (@sizeOf(Entry) != content.metadata_entry_bytes) {
17 @compileError("content memory metadata must match Capacity.metadata_bytes");
18 }
19 }
20
21 pub const InitError = error{
22 CapacityHostWidthExceeded,
23 ContentStorageTooShort,
24 EntryStorageTooShort,
25 StagingStorageTooShort,
26 StorageOverlap,
27 };
28
29 /// Provides a content store over three buffers the caller laid out, the
30 /// metadata array, the content region, and the staging region, kept as borrowed
31 /// slices so the caller keeps the memory. The owner tracks how many bindings it
32 /// holds and how many content bytes it has used, and serializes every provider
33 /// call behind a process-local spin lock.
34 pub const Owner = struct {
35 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
36 .transition_steps_max = 1,
37 .cleanup_steps_per_call_max = 0,
38 .cleanup_calls_at_capacity_max = 0,
39 };
40
41 pub const claim: alloc_phase.capacity.Declaration = .{
42 .source = .{
43 .id = "content.memory",
44 .kind = .startup_static,
45 .limit_source = .caller,
46 .storage = .{
47 .covered = &.{
48 .{
49 .id = "identity_entries",
50 .lifetime = .steady,
51 .detail = "one exact reference and byte offset per admitted object",
52 },
53 .{
54 .id = "committed_content",
55 .lifetime = .steady,
56 .detail = "caller-selected immutable content byte region",
57 },
58 .{
59 .id = "publication_staging",
60 .lifetime = .steady,
61 .detail = "one maximum-size private publication staging region",
62 },
63 },
64 .excluded = &.{
65 "caller input and read-output slices",
66 "provider-independent Reader and Sink values",
67 },
68 },
69 .capacity = .{
70 .inputs = &.{
71 alloc_phase.capacity.bindInput(content.Limits, "objects", "objects"),
72 alloc_phase.capacity.bindInput(content.Limits, "object_bytes", "object_bytes"),
73 alloc_phase.capacity.bindInput(content.Limits, "total_bytes", "total_bytes"),
74 },
75 .type_selectors = &.{
76 alloc_phase.capacity.bindType(Entry, "entry"),
77 },
78 .nodes = &.{
79 .{ .input = 0 },
80 .{ .input = 1 },
81 .{ .input = 2 },
82 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
83 .{ .add = .{ .left = 3, .right = 2 } },
84 .{ .add = .{ .left = 4, .right = 1 } },
85 },
86 .assertions = &.{.{
87 .scope = .closure_total,
88 .measure = .retained,
89 .relation = .exact,
90 .expression = 5,
91 }},
92 },
93 .overload = .{
94 .kind = .reject_before_mutation,
95 .detail = "capacity, digest, extent, and staging checks precede committed metadata mutation",
96 },
97 .risks = .{
98 .transitive = .{
99 .status = .excluded,
100 .detail = "all lookup, hashing, copy, and teardown work is bounded by checked Capacity fields",
101 },
102 .foreign = .{
103 .status = .excluded,
104 .detail = "caller-owned memory and a process-local mutex perform no filesystem or foreign-runtime work",
105 },
106 },
107 .obligations = &.{
108 .{ .key = "content_memory_capacity", .role = .capacity_model },
109 .{ .key = "content_memory_overload", .role = .overload },
110 .{ .key = "content_memory_convergence", .role = .custom },
111 .{ .key = "content_memory_teardown", .role = .custom },
112 },
113 },
114 .bindings = .{
115 .owner = @This(),
116 .seal = .{
117 .family = alloc_phase.capacity.selector(@This().activate),
118 .premise = .{
119 .class = .checked_semantic_fact,
120 .authority = .checker,
121 },
122 },
123 .teardown = .{
124 .family = alloc_phase.capacity.selector(@This().deinit),
125 .premise = .{
126 .class = .checked_semantic_fact,
127 .authority = .checker,
128 },
129 },
130 },
131 };
132
133 phase: alloc_phase.capacity.Phase,
134 capacity: content.Capacity,
135 entries: []Entry,
136 content: []u8,
137 staging: []u8,
138 entry_count: usize = 0,
139 used: usize = 0,
140 mutex: std.atomic.Mutex = .unlocked,
141
142 const reader_vtable: content.Reader.VTable = .{ .read = readProvider };
143 const sink_vtable: content.Sink.VTable = .{ .put = putProvider };
144
145 /// Binds a derived capacity to the three buffers it calls for, once the
146 /// caller has laid them out. The call returns `CapacityHostWidthExceeded`
147 /// when one of the capacity's counts is wider than a host `usize`, returns
148 /// `EntryStorageTooShort`, `ContentStorageTooShort`, or
149 /// `StagingStorageTooShort` when a buffer is smaller than the capacity
150 /// calls for, and returns `StorageOverlap` when any two of the three
151 /// buffers share bytes, because staging and committed content have to stay
152 /// apart. Successful initialization cuts each buffer to the size the
153 /// capacity names, keeps that slice, and leaves the owner in the
154 /// initialization phase, where capabilities are still refused.
155 pub fn init(
156 capacity: content.Capacity,
157 entries: []Entry,
158 content_storage: []u8,
159 staging: []u8,
160 ) InitError!Owner {
161 const object_count = std.math.cast(usize, capacity.limits.objects) orelse
162 return error.CapacityHostWidthExceeded;
163 const total_bytes = std.math.cast(usize, capacity.limits.total_bytes) orelse
164 return error.CapacityHostWidthExceeded;
165 const object_bytes = std.math.cast(usize, capacity.limits.object_bytes) orelse
166 return error.CapacityHostWidthExceeded;
167 if (entries.len < object_count) return error.EntryStorageTooShort;
168 if (content_storage.len < total_bytes) return error.ContentStorageTooShort;
169 if (staging.len < object_bytes) return error.StagingStorageTooShort;
170 const selected_entries = entries[0..object_count];
171 const selected_content = content_storage[0..total_bytes];
172 const selected_staging = staging[0..object_bytes];
173 const entry_bytes = std.mem.sliceAsBytes(selected_entries);
174 if (slicesOverlap(entry_bytes, selected_content) or
175 slicesOverlap(entry_bytes, selected_staging) or
176 slicesOverlap(selected_content, selected_staging))
177 {
178 return error.StorageOverlap;
179 }
180 return .{
181 .phase = .initialization,
182 .capacity = capacity,
183 .entries = selected_entries,
184 .content = selected_content,
185 .staging = selected_staging,
186 };
187 }
188
189 /// Opens the store for use once after init by moving the owner from
190 /// initialization into the steady phase. Every capability accessor asserts
191 /// the steady phase, so no Reader or Sink escapes before this call.
192 pub fn activate(self: *Owner) void {
193 std.debug.assert(self.phase == .initialization);
194 std.debug.assert(self.entry_count == 0);
195 std.debug.assert(self.used == 0);
196 self.phase = .steady;
197 }
198
199 /// Returns a Reader to hand to code that may reopen bytes and do nothing
200 /// else, bound to this owner and carrying the owner's capacity. The
201 /// returned value borrows the owner, so the owner outlives it.
202 pub fn reader(self: *Owner) content.Reader {
203 std.debug.assert(self.phase == .steady);
204 return .{
205 .context = self,
206 .capacity = self.capacity,
207 .vtable = &reader_vtable,
208 };
209 }
210
211 /// Returns a Sink to hand to code that may add bytes and do nothing else,
212 /// bound to this owner and carrying the owner's capacity. The returned
213 /// value borrows the owner, so the owner outlives it.
214 pub fn sink(self: *Owner) content.Sink {
215 std.debug.assert(self.phase == .steady);
216 return .{
217 .context = self,
218 .capacity = self.capacity,
219 .vtable = &sink_vtable,
220 };
221 }
222
223 /// Returns the owner's Reader and Sink as one Store to hand to code trusted
224 /// with both authorities at once. Both halves carry the same capacity, so
225 /// the composition always succeeds.
226 pub fn store(self: *Owner) content.Store {
227 return content.Store.init(self.reader(), self.sink()) catch unreachable;
228 }
229
230 /// Drops every binding and resets the store to empty, for a caller that has
231 /// finished with the store and keeps the buffers for something else. This
232 /// overwrites the live metadata entries and returns the binding count and
233 /// the used byte count to zero. The call leaves all three buffers with
234 /// their caller, who decides what happens to the bytes, and moves the owner
235 /// into the teardown phase, after which the capability accessors refuse.
236 pub fn deinit(self: *Owner) void {
237 self.lock();
238 defer self.mutex.unlock();
239 std.debug.assert(self.phase == .steady);
240 for (self.entries[0..self.entry_count]) |*entry| entry.* = undefined;
241 self.entry_count = 0;
242 self.used = 0;
243 self.phase = .teardown;
244 }
245
246 /// Reports how many bindings the store holds, for a test or a diagnostic.
247 /// The call takes the same lock the provider calls take, so the answer is a
248 /// consistent one.
249 pub fn count(self: *Owner) usize {
250 self.lock();
251 defer self.mutex.unlock();
252 std.debug.assert(self.phase == .steady);
253 return self.entry_count;
254 }
255
256 fn readProvider(
257 context: *anyopaque,
258 identifier: content.Identifier,
259 output: []u8,
260 ) error{ ContentMissing, ReadFailed }!u64 {
261 const self: *Owner = @ptrCast(@alignCast(context));
262 self.lock();
263 defer self.mutex.unlock();
264 std.debug.assert(self.phase == .steady);
265 const index = self.find(identifier) orelse return error.ContentMissing;
266 const entry = self.entries[index];
267 const actual = entry.reference.extent.bytes;
268 if (actual > output.len) return actual;
269 const start = std.math.cast(usize, entry.offset) orelse
270 return error.ReadFailed;
271 const end = std.math.add(usize, start, actual) catch
272 return error.ReadFailed;
273 if (end > self.content.len or end > self.used) return error.ReadFailed;
274 @memcpy(output[0..actual], self.content[start..end]);
275 return actual;
276 }
277
278 fn putProvider(
279 context: *anyopaque,
280 reference: content.Reference,
281 bytes: []const u8,
282 ) error{
283 ContentMutated,
284 PublicationConflict,
285 PublicationFailed,
286 StoreCapacityExceeded,
287 }!content.Publication {
288 const self: *Owner = @ptrCast(@alignCast(context));
289 self.lock();
290 defer self.mutex.unlock();
291 std.debug.assert(self.phase == .steady);
292 if (!reference.identifier.matches(bytes)) return error.ContentMutated;
293 if (self.find(reference.identifier)) |index| {
294 const entry = self.entries[index];
295 if (entry.reference.extent.bytes != reference.extent.bytes) {
296 return error.PublicationConflict;
297 }
298 const start = std.math.cast(usize, entry.offset) orelse
299 return error.PublicationConflict;
300 const end = std.math.add(usize, start, bytes.len) catch
301 return error.PublicationConflict;
302 if (end > self.used or end > self.content.len or
303 !std.mem.eql(u8, self.content[start..end], bytes))
304 {
305 return error.PublicationConflict;
306 }
307 if (!reference.identifier.matches(bytes)) return error.ContentMutated;
308 return .exists_same;
309 }
310 if (self.entry_count >= self.entries.len) {
311 return error.StoreCapacityExceeded;
312 }
313 const next_used = std.math.add(usize, self.used, bytes.len) catch
314 return error.StoreCapacityExceeded;
315 if (next_used > self.content.len or bytes.len > self.staging.len) {
316 return error.StoreCapacityExceeded;
317 }
318 @memcpy(self.staging[0..bytes.len], bytes);
319 const staged = self.staging[0..bytes.len];
320 if (!reference.identifier.matches(staged) or
321 !reference.identifier.matches(bytes))
322 {
323 return error.ContentMutated;
324 }
325 @memcpy(self.content[self.used..next_used], staged);
326 self.entries[self.entry_count] = .{
327 .reference = reference,
328 .offset = self.used,
329 };
330 self.entry_count += 1;
331 self.used = next_used;
332 return .created;
333 }
334
335 fn find(self: *const Owner, identifier: content.Identifier) ?usize {
336 var index: usize = 0;
337 while (index < self.entry_count) : (index += 1) {
338 if (self.entries[index].reference.identifier.eql(identifier)) {
339 return index;
340 }
341 }
342 return null;
343 }
344
345 fn lock(self: *Owner) void {
346 while (!self.mutex.tryLock()) std.atomic.spinLoopHint();
347 }
348 };
349
350 fn slicesOverlap(first: []const u8, second: []const u8) bool {
351 if (first.len == 0 or second.len == 0) return false;
352 const first_address = @intFromPtr(first.ptr);
353 const second_address = @intFromPtr(second.ptr);
354 if (first_address <= second_address) {
355 return second_address - first_address < first.len;
356 }
357 return first_address - second_address < second.len;
358 }