lib/cook/src/cache.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Sha256 = std.crypto.hash.sha2.Sha256;
3 const Allocator = std.mem.Allocator;
4
5 pub const Limits = struct {
6 max_entry_bytes: u64 = 256 * 1024 * 1024,
7 max_cache_bytes: u64 = 2 * 1024 * 1024 * 1024,
8 max_entries: u32 = 128,
9 max_files: u32 = 8192,
10 max_directories: u32 = 8192,
11 max_depth: u8 = 16,
12 max_path_bytes: usize = 1024,
13 };
14
15 pub const Summary = struct {
16 files: u32,
17 bytes: u64,
18 };
19
20 pub const Key = struct {
21 digest: [32]u8,
22
23 pub fn fromCodeFile(io: std.Io, deriver: []const u8, code_file: std.Io.File, input: []const u8) !Key {
24 return init(deriver, try digestFile(io, code_file), input);
25 }
26
27 pub fn parseHex(hex_bytes: []const u8) !Key {
28 if (hex_bytes.len != 64) return error.InvalidKey;
29 var digest: [32]u8 = undefined;
30 _ = std.fmt.hexToBytes(&digest, hex_bytes) catch return error.InvalidKey;
31 if (!std.mem.eql(u8, hex_bytes, &std.fmt.bytesToHex(digest, .lower))) return error.InvalidKey;
32 return .{ .digest = digest };
33 }
34
35 fn init(deriver: []const u8, code: [32]u8, input: []const u8) Key {
36 var hasher = Sha256.init(.{});
37 hasher.update("tiny-cook-key-v1");
38 hashFramed(&hasher, deriver);
39 hashFramed(&hasher, &code);
40 hashFramed(&hasher, input);
41 var digest: [32]u8 = undefined;
42 hasher.final(&digest);
43 return .{ .digest = digest };
44 }
45
46 pub fn hex(key: Key) [64]u8 {
47 return std.fmt.bytesToHex(key.digest, .lower);
48 }
49 };
50
51 fn hashFramed(hasher: *Sha256, bytes: []const u8) void {
52 var length: [8]u8 = undefined;
53 std.mem.writeInt(u64, &length, bytes.len, .little);
54 hasher.update(&length);
55 hasher.update(bytes);
56 }
57
58 pub fn digestFile(io: std.Io, file: std.Io.File) ![32]u8 {
59 const stat = try file.stat(io);
60 var hasher = Sha256.init(.{});
61 var buffer: [64 * 1024]u8 = undefined;
62 var offset: u64 = 0;
63 while (offset < stat.size) {
64 const wanted: usize = @intCast(@min(stat.size - offset, buffer.len));
65 const count = try file.readPositionalAll(io, buffer[0..wanted], offset);
66 if (count != wanted) return error.ShortRead;
67 hasher.update(buffer[0..count]);
68 offset += count;
69 }
70 var digest: [32]u8 = undefined;
71 hasher.final(&digest);
72 return digest;
73 }
74
75 pub fn defaultPath(gpa: Allocator, environ: *const std.process.Environ.Map) ![]u8 {
76 if (environ.get("TINY_COOK_CACHE")) |path| {
77 if (!std.fs.path.isAbsolute(path)) return error.CachePathNotAbsolute;
78 return gpa.dupe(u8, path);
79 }
80 if (environ.get("XDG_CACHE_HOME")) |path| {
81 if (!std.fs.path.isAbsolute(path)) return error.CachePathNotAbsolute;
82 return std.fs.path.join(gpa, &.{ path, "tiny", "cook" });
83 }
84 const home = environ.get("HOME") orelse return error.CacheHomeUnset;
85 if (!std.fs.path.isAbsolute(home)) return error.CachePathNotAbsolute;
86 return std.fs.path.join(gpa, &.{ home, ".cache", "tiny", "cook" });
87 }
88
89 pub const Entry = struct {
90 io: std.Io,
91 gpa: Allocator,
92 path: []u8,
93 lock: std.Io.File,
94 dir: std.Io.Dir,
95 summary: Summary,
96 hit: bool,
97
98 pub fn deinit(entry: *Entry) void {
99 entry.dir.close(entry.io);
100 entry.lock.close(entry.io);
101 entry.gpa.free(entry.path);
102 entry.* = undefined;
103 }
104 };
105
106 pub const Store = struct {
107 gpa: Allocator,
108 io: std.Io,
109 path: []const u8,
110 limits: Limits,
111
112 pub fn init(gpa: Allocator, io: std.Io, path: []const u8, limits: Limits) !Store {
113 if (!std.fs.path.isAbsolute(path)) return error.CachePathNotAbsolute;
114 if (limits.max_entry_bytes == 0 or limits.max_cache_bytes < limits.max_entry_bytes or
115 limits.max_entries == 0 or limits.max_files == 0 or
116 limits.max_directories == 0 or limits.max_depth == 0 or
117 limits.max_path_bytes < 64) return error.InvalidLimits;
118 return .{ .gpa = gpa, .io = io, .path = path, .limits = limits };
119 }
120
121 /// The callback writes ordinary files below an empty directory. The
122 /// returned entry holds its manifest lease until deinit.
123 pub fn getOrDerive(
124 store: Store,
125 key: Key,
126 context: anytype,
127 comptime derive: fn (@TypeOf(context), std.Io, std.Io.Dir) anyerror!void,
128 ) !Entry {
129 try std.Io.Dir.cwd().createDirPath(store.io, store.path);
130 const hex = key.hex();
131 const prefix = try std.fs.path.join(store.gpa, &.{ store.path, "v2", hex[0..2] });
132 defer store.gpa.free(prefix);
133 try std.Io.Dir.cwd().createDirPath(store.io, prefix);
134 var key_lock = try store.keyLock(prefix, key);
135 defer key_lock.close(store.io);
136 try key_lock.lock(store.io, .shared);
137 const path = try std.fmt.allocPrint(store.gpa, "{s}/{s}", .{ prefix, hex[2..] });
138 errdefer store.gpa.free(path);
139 if (try store.exists(path)) return store.load(&key_lock, key, path, true, null);
140 key_lock.unlock(store.io);
141 try key_lock.lock(store.io, .exclusive);
142 if (try store.exists(path)) return store.load(&key_lock, key, path, true, null);
143 const summary = try store.publish(prefix, path, key, context, derive);
144 return store.load(&key_lock, key, path, false, summary);
145 }
146
147 pub fn open(store: Store, key: Key) !Entry {
148 const hex = key.hex();
149 const prefix = try std.fs.path.join(store.gpa, &.{ store.path, "v2", hex[0..2] });
150 defer store.gpa.free(prefix);
151 if (!try store.exists(prefix)) return error.CacheMiss;
152 const path = try std.fmt.allocPrint(store.gpa, "{s}/v2/{s}/{s}", .{ store.path, hex[0..2], hex[2..] });
153 errdefer store.gpa.free(path);
154 if (!try store.exists(path)) return error.CacheMiss;
155 var key_lock = try store.keyLock(prefix, key);
156 defer key_lock.close(store.io);
157 try key_lock.lock(store.io, .shared);
158 if (!try store.exists(path)) return error.CacheMiss;
159 return store.load(&key_lock, key, path, true, null);
160 }
161
162 fn keyLock(store: Store, prefix: []const u8, key: Key) !std.Io.File {
163 const hex = key.hex();
164 const lock_path = try std.fmt.allocPrint(store.gpa, "{s}/.key-{s}", .{ prefix, &hex });
165 defer store.gpa.free(lock_path);
166 return std.Io.Dir.createFileAbsolute(store.io, lock_path, .{
167 .truncate = false,
168 .read = true,
169 .permissions = .fromMode(0o600),
170 });
171 }
172
173 fn load(store: Store, key_lock: *std.Io.File, key: Key, path: []u8, hit: bool, published: ?Summary) !Entry {
174 var dir = try std.Io.Dir.openDirAbsolute(store.io, path, .{ .iterate = true, .follow_symlinks = false });
175 errdefer dir.close(store.io);
176 var manifest = dir.openFile(store.io, ".cook", .{ .mode = .read_write }) catch return error.CorruptEntry;
177 errdefer manifest.close(store.io);
178 try manifest.lock(store.io, .shared);
179 key_lock.unlock(store.io);
180 const summary = published orelse try store.verify(dir, key);
181 try store.touch(manifest);
182 return .{ .io = store.io, .gpa = store.gpa, .path = path, .lock = manifest, .dir = dir, .summary = summary, .hit = hit };
183 }
184
185 fn exists(store: Store, path: []const u8) !bool {
186 _ = std.Io.Dir.cwd().statFile(store.io, path, .{ .follow_symlinks = false }) catch |err| switch (err) {
187 error.FileNotFound => return false,
188 else => return err,
189 };
190 return true;
191 }
192
193 fn publish(
194 store: Store,
195 prefix: []const u8,
196 path: []const u8,
197 key: Key,
198 context: anytype,
199 comptime derive: fn (@TypeOf(context), std.Io, std.Io.Dir) anyerror!void,
200 ) !Summary {
201 const hex = key.hex();
202 const stage_path = try std.fmt.allocPrint(store.gpa, "{s}/.stage-{s}", .{ prefix, &hex });
203 defer store.gpa.free(stage_path);
204 try std.Io.Dir.cwd().deleteTree(store.io, stage_path);
205 try std.Io.Dir.cwd().createDir(store.io, stage_path, .default_dir);
206 errdefer std.Io.Dir.cwd().deleteTree(store.io, stage_path) catch {};
207 var stage = try std.Io.Dir.openDirAbsolute(store.io, stage_path, .{ .iterate = true, .follow_symlinks = false });
208 defer stage.close(store.io);
209 try derive(context, store.io, stage);
210 const tree = try store.snapshot(stage, true);
211 const encoded = encodeManifest(key, tree);
212 var manifest = try stage.createFile(store.io, ".cook", .{ .exclusive = true, .permissions = .fromMode(0o600) });
213 defer manifest.close(store.io);
214 try manifest.writePositionalAll(store.io, &encoded, 0);
215 try manifest.sync(store.io);
216 try syncDirectory(store.io, stage);
217 const lock_path = try std.fs.path.join(store.gpa, &.{ store.path, ".lock" });
218 defer store.gpa.free(lock_path);
219 var root_lock = try std.Io.Dir.createFileAbsolute(store.io, lock_path, .{
220 .truncate = false,
221 .read = true,
222 .permissions = .fromMode(0o600),
223 });
224 defer root_lock.close(store.io);
225 try root_lock.lock(store.io, .exclusive);
226 try store.prune(tree.summary);
227 var parent = try std.Io.Dir.openDirAbsolute(store.io, prefix, .{});
228 defer parent.close(store.io);
229 try std.Io.Dir.cwd().rename(stage_path, std.Io.Dir.cwd(), path, store.io);
230 try syncDirectory(store.io, parent);
231 return tree.summary;
232 }
233
234 fn verify(store: Store, dir: std.Io.Dir, key: Key) !Summary {
235 const encoded = dir.readFileAlloc(store.io, ".cook", store.gpa, .limited(85)) catch return error.CorruptEntry;
236 defer store.gpa.free(encoded);
237 if (encoded.len != 84 or !std.mem.eql(u8, encoded[0..8], "TCOOK001") or
238 !std.mem.eql(u8, encoded[8..40], &key.digest)) return error.CorruptEntry;
239 const tree = try store.snapshot(dir, false);
240 const expected = encodeManifest(key, tree);
241 if (!std.mem.eql(u8, encoded, &expected)) return error.CorruptEntry;
242 return tree.summary;
243 }
244
245 fn touch(store: Store, manifest: std.Io.File) !void {
246 try manifest.writePositionalAll(store.io, "T", 0);
247 try manifest.sync(store.io);
248 }
249
250 fn prune(store: Store, pending: Summary) !void {
251 const version = try std.fs.path.join(store.gpa, &.{ store.path, "v2" });
252 defer store.gpa.free(version);
253 var root = try std.Io.Dir.openDirAbsolute(store.io, version, .{ .iterate = true, .follow_symlinks = false });
254 defer root.close(store.io);
255 var stages: std.ArrayList(Candidate) = .empty;
256 defer {
257 for (stages.items) |item| store.gpa.free(item.path);
258 stages.deinit(store.gpa);
259 }
260 var candidates: std.ArrayList(Candidate) = .empty;
261 defer {
262 for (candidates.items) |item| store.gpa.free(item.path);
263 candidates.deinit(store.gpa);
264 }
265 var total_bytes: u64 = 0;
266 var prefixes = root.iterate();
267 while (try prefixes.next(store.io)) |prefix| {
268 if (prefix.kind != .directory or prefix.name.len != 2) continue;
269 const prefix_path = try std.fs.path.join(store.gpa, &.{ version, prefix.name });
270 defer store.gpa.free(prefix_path);
271 var shard = try root.openDir(store.io, prefix.name, .{ .iterate = true, .follow_symlinks = false });
272 defer shard.close(store.io);
273 var children = shard.iterate();
274 while (try children.next(store.io)) |child| {
275 if (child.kind != .directory) continue;
276 const path = try std.fs.path.join(store.gpa, &.{ prefix_path, child.name });
277 errdefer store.gpa.free(path);
278 if (std.mem.startsWith(u8, child.name, ".stage-")) {
279 if (child.name.len != 71) {
280 store.gpa.free(path);
281 continue;
282 }
283 if (stages.items.len == 65536) return error.CacheInventoryExceeded;
284 try stages.append(store.gpa, .{
285 .path = path,
286 .key = Key.parseHex(child.name[7..]) catch return error.CacheInventoryExceeded,
287 .bytes = 0,
288 .mtime = 0,
289 });
290 continue;
291 }
292 if (child.name.len != 62) {
293 store.gpa.free(path);
294 continue;
295 }
296 if (candidates.items.len == 65536) return error.CacheInventoryExceeded;
297 var hex: [64]u8 = undefined;
298 @memcpy(hex[0..2], prefix.name);
299 @memcpy(hex[2..], child.name);
300 const key = Key.parseHex(&hex) catch return error.CacheInventoryExceeded;
301 var entry_dir = try shard.openDir(store.io, child.name, .{ .follow_symlinks = false });
302 defer entry_dir.close(store.io);
303 const stat = try entry_dir.statFile(store.io, ".cook", .{ .follow_symlinks = false });
304 const encoded = try entry_dir.readFileAlloc(store.io, ".cook", store.gpa, .limited(85));
305 defer store.gpa.free(encoded);
306 const bytes = if (encoded.len == 84 and std.mem.eql(u8, encoded[0..8], "TCOOK001"))
307 std.mem.readInt(u64, encoded[44..52], .little)
308 else
309 store.limits.max_entry_bytes;
310 total_bytes = std.math.add(u64, total_bytes, bytes) catch return error.CacheInventoryExceeded;
311 try candidates.append(store.gpa, .{
312 .path = path,
313 .key = key,
314 .bytes = bytes,
315 .mtime = @intCast(stat.mtime.nanoseconds),
316 });
317 }
318 }
319 for (stages.items) |stage| {
320 const parent_path = std.fs.path.dirname(stage.path).?;
321 var key_lock = try store.keyLock(parent_path, stage.key);
322 defer key_lock.close(store.io);
323 if (!try key_lock.tryLock(store.io, .exclusive)) continue;
324 try std.Io.Dir.cwd().deleteTree(store.io, stage.path);
325 var parent = try std.Io.Dir.openDirAbsolute(store.io, parent_path, .{});
326 defer parent.close(store.io);
327 try syncDirectory(store.io, parent);
328 }
329 std.mem.sortUnstable(Candidate, candidates.items, {}, candidateLessThan);
330 var count: usize = candidates.items.len;
331 total_bytes = std.math.add(u64, total_bytes, pending.bytes) catch return error.CacheInventoryExceeded;
332 count += 1;
333 for (candidates.items) |candidate| {
334 if (count <= store.limits.max_entries and total_bytes <= store.limits.max_cache_bytes) break;
335 const parent_path = std.fs.path.dirname(candidate.path).?;
336 var key_lock = try store.keyLock(parent_path, candidate.key);
337 defer key_lock.close(store.io);
338 if (!try key_lock.tryLock(store.io, .exclusive)) continue;
339 const manifest_path = try std.fs.path.join(store.gpa, &.{ candidate.path, ".cook" });
340 defer store.gpa.free(manifest_path);
341 var manifest = try std.Io.Dir.openFileAbsolute(store.io, manifest_path, .{ .mode = .read_write });
342 defer manifest.close(store.io);
343 if (!try manifest.tryLock(store.io, .exclusive)) continue;
344 try std.Io.Dir.cwd().deleteTree(store.io, candidate.path);
345 var parent = try std.Io.Dir.openDirAbsolute(store.io, parent_path, .{});
346 defer parent.close(store.io);
347 try syncDirectory(store.io, parent);
348 total_bytes -= candidate.bytes;
349 count -= 1;
350 }
351 if (count > store.limits.max_entries or total_bytes > store.limits.max_cache_bytes) return error.CacheFull;
352 }
353
354 fn snapshot(store: Store, dir: std.Io.Dir, sync_files: bool) !Snapshot {
355 var records: std.ArrayList(Record) = .empty;
356 defer {
357 for (records.items) |record| store.gpa.free(record.path);
358 records.deinit(store.gpa);
359 }
360 var summary: Summary = .{ .files = 0, .bytes = 0 };
361 var directories: u32 = 0;
362 try store.walk(dir, "", 0, sync_files, &records, &summary, &directories);
363 std.mem.sortUnstable(Record, records.items, {}, recordLessThan);
364 var hasher = Sha256.init(.{});
365 for (records.items) |record| {
366 hashFramed(&hasher, record.path);
367 hasher.update(&.{record.kind});
368 var size: [8]u8 = undefined;
369 std.mem.writeInt(u64, &size, record.size, .little);
370 hasher.update(&size);
371 hasher.update(&record.digest);
372 }
373 var digest: [32]u8 = undefined;
374 hasher.final(&digest);
375 return .{ .summary = summary, .digest = digest };
376 }
377
378 fn walk(
379 store: Store,
380 dir: std.Io.Dir,
381 relative: []const u8,
382 depth: u8,
383 sync_files: bool,
384 records: *std.ArrayList(Record),
385 summary: *Summary,
386 directories: *u32,
387 ) !void {
388 var iterator = dir.iterate();
389 while (try iterator.next(store.io)) |item| {
390 if (depth == 0 and std.mem.eql(u8, item.name, ".cook")) {
391 if (sync_files) return error.ReservedPath;
392 continue;
393 }
394 const child_path = if (relative.len == 0)
395 try store.gpa.dupe(u8, item.name)
396 else
397 try std.fs.path.join(store.gpa, &.{ relative, item.name });
398 errdefer store.gpa.free(child_path);
399 if (child_path.len > store.limits.max_path_bytes) return error.PathLimitExceeded;
400 switch (item.kind) {
401 .directory => {
402 if (depth == store.limits.max_depth) return error.DepthLimitExceeded;
403 if (directories.* == store.limits.max_directories) return error.DirectoryLimitExceeded;
404 directories.* += 1;
405 var child = try dir.openDir(store.io, item.name, .{ .iterate = true, .follow_symlinks = false });
406 defer child.close(store.io);
407 try store.walk(child, child_path, depth + 1, sync_files, records, summary, directories);
408 if (sync_files) try syncDirectory(store.io, child);
409 try records.append(store.gpa, .{ .path = child_path, .kind = 0, .size = 0, .digest = @splat(0) });
410 },
411 .file => {
412 if (summary.files == store.limits.max_files) return error.FileLimitExceeded;
413 var file = try dir.openFile(store.io, item.name, .{});
414 defer file.close(store.io);
415 const stat = try file.stat(store.io);
416 if (stat.size > store.limits.max_entry_bytes -| summary.bytes) return error.EntrySizeExceeded;
417 const digest = try digestFile(store.io, file);
418 if (sync_files) try file.sync(store.io);
419 try records.append(store.gpa, .{ .path = child_path, .kind = 1, .size = stat.size, .digest = digest });
420 summary.files += 1;
421 summary.bytes += stat.size;
422 },
423 else => return error.UnsupportedFileType,
424 }
425 }
426 }
427 };
428
429 const Candidate = struct { path: []u8, key: Key, bytes: u64, mtime: i128 };
430
431 fn candidateLessThan(_: void, left: Candidate, right: Candidate) bool {
432 if (left.mtime != right.mtime) return left.mtime < right.mtime;
433 return std.mem.lessThan(u8, left.path, right.path);
434 }
435
436 const Record = struct { path: []u8, kind: u8, size: u64, digest: [32]u8 };
437 const Snapshot = struct { summary: Summary, digest: [32]u8 };
438
439 fn recordLessThan(_: void, left: Record, right: Record) bool {
440 return std.mem.lessThan(u8, left.path, right.path);
441 }
442
443 fn encodeManifest(key: Key, snapshot: Snapshot) [84]u8 {
444 var bytes: [84]u8 = undefined;
445 @memcpy(bytes[0..8], "TCOOK001");
446 @memcpy(bytes[8..40], &key.digest);
447 std.mem.writeInt(u32, bytes[40..44], snapshot.summary.files, .little);
448 std.mem.writeInt(u64, bytes[44..52], snapshot.summary.bytes, .little);
449 @memcpy(bytes[52..84], &snapshot.digest);
450 return bytes;
451 }
452
453 fn syncDirectory(io: std.Io, dir: std.Io.Dir) !void {
454 var file = try dir.openFile(io, ".", .{ .allow_directory = true });
455 defer file.close(io);
456 try file.sync(io);
457 }