//! The purge graveyard: removed artifacts, kept recoverable.
//!
//! `zit shun` is permanent and PROPAGATES — its table travels to clones so a
//! peer can never re-offer what an operator ordered removed. That is the right
//! tool once content has escaped, and the wrong one for the ordinary accident:
//! a `zit add .` that swept in a build tree, noticed before anyone else has it.
//!
//! Fossil draws exactly that line with `fossil purge`, whose removed content
//! goes to a graveyard that `purge undo` can restore and `purge obliterate`
//! empties for good. This is that graveyard.
//!
//! It is LOCAL and DISPOSABLE, like the stash and the undo journal: never an
//! artifact, never synced, and losing it costs recoverability rather than data
//! — the purge itself already happened. That locality is also what makes purge
//! honest about its limits: a purge says nothing to a peer that already holds
//! the content, which is why the help points at `shun` for that case.
//!
//! Format: `magic(8) | fmt(1) | count u32 | event... | crc32 le(4)`, crc over
//! all preceding bytes. An event is
//! `id u32 | when i64 | reason_len u16 | reason | artifact_count u32 | artifact...`,
//! and an artifact is `hash_len u8 | hash | bytes_len u32 | bytes`. Every length
//! is bounds-checked against the remaining input before use, consumption must be
//! exact, and the crc must match; any violation is `error.Corrupt` and leaves
//! the file untouched — the undo journal's discipline, for the same reason.
const std = @import("std");
const repeat = @import("repeat.zig").repeat;
pub const filename: []const u8 = ".zit-graveyard";
const magic: [8]u8 = .{ 'z', 'i', 't', 'g', 'r', 'a', 'v', 'e' };
const fmt_version: u8 = 1;
/// TigerStyle bounds. A purge that names more artifacts than this is a repack,
/// not an accident recovery, and the operator should reach for `shun`.
pub const max_events: usize = 256;
pub const max_artifacts_per_event: usize = 1 << 20;
pub const max_reason_len: usize = 256;
/// The whole graveyard is read into memory to rewrite it, so it carries a
/// stated ceiling rather than growing until a read fails.
pub const max_file_bytes: usize = 2 << 30;
pub const Error = error{ Storage, Corrupt, OutOfMemory, NotFound, Full };
pub const Artifact = struct {
hash: []const u8,
bytes: []const u8,
};
pub const Event = struct {
id: u32,
when: i64,
reason: []const u8,
artifacts: []const Artifact,
/// Total bytes this event is holding, for `list` — the number an operator
/// weighs when deciding whether to obliterate.
pub fn size(self: Event) u64 {
var total: u64 = 0;
for (self.artifacts) |a| total += a.bytes.len;
return total;
}
};
/// Every event currently held. Arena-owned; the caller frees the arena.
pub fn read(a: std.mem.Allocator, io: std.Io, root: std.Io.Dir) Error![]Event {
const raw = root.readFileAlloc(io, filename, a, .limited(max_file_bytes)) catch |e| switch (e) {
error.FileNotFound => return &.{},
error.OutOfMemory => return error.OutOfMemory,
else => return error.Storage,
};
if (raw.len == 0) return &.{};
return parse(a, raw);
}
fn parse(a: std.mem.Allocator, raw: []const u8) Error![]Event {
if (raw.len < magic.len + 1 + 4 + 4) return error.Corrupt;
if (!std.mem.eql(u8, raw[0..magic.len], &magic)) return error.Corrupt;
if (raw[magic.len] != fmt_version) return error.Corrupt;
const body = raw[0 .. raw.len - 4];
const want = std.mem.readInt(u32, raw[raw.len - 4 ..][0..4], .little);
if (std.hash.Crc32.hash(body) != want) return error.Corrupt;
var at: usize = magic.len + 1;
const count = std.mem.readInt(u32, body[at..][0..4], .little);
at += 4;
if (count > max_events) return error.Corrupt;
const events = try a.alloc(Event, count);
var i: usize = 0;
while (i < count) : (i += 1) {
if (body.len - at < 4 + 8 + 2) return error.Corrupt;
const id = std.mem.readInt(u32, body[at..][0..4], .little);
at += 4;
const when = std.mem.readInt(i64, body[at..][0..8], .little);
at += 8;
const rlen = std.mem.readInt(u16, body[at..][0..2], .little);
at += 2;
if (rlen > max_reason_len or body.len - at < rlen) return error.Corrupt;
const reason = body[at..][0..rlen];
at += rlen;
if (body.len - at < 4) return error.Corrupt;
const acount = std.mem.readInt(u32, body[at..][0..4], .little);
at += 4;
if (acount > max_artifacts_per_event) return error.Corrupt;
const arts = try a.alloc(Artifact, acount);
var j: usize = 0;
while (j < acount) : (j += 1) {
if (body.len - at < 1) return error.Corrupt;
const hlen = body[at];
at += 1;
if (hlen == 0 or body.len - at < hlen) return error.Corrupt;
const hash = body[at..][0..hlen];
at += hlen;
if (body.len - at < 4) return error.Corrupt;
const blen = std.mem.readInt(u32, body[at..][0..4], .little);
at += 4;
if (body.len - at < blen) return error.Corrupt;
arts[j] = .{ .hash = hash, .bytes = body[at..][0..blen] };
at += blen;
}
events[i] = .{ .id = id, .when = when, .reason = reason, .artifacts = arts };
}
// Consumption must be exact: trailing bytes mean this is not the file we
// think it is, and guessing about a recovery store is how recovery fails.
if (at != body.len) return error.Corrupt;
return events;
}
/// Rewrite the graveyard to exactly `events`. Atomic (write-temp, fsync,
/// rename), the same sequence every durable control record here uses; an empty
/// set removes the file so a repository with nothing buried carries nothing.
pub fn write(gpa: std.mem.Allocator, io: std.Io, root: std.Io.Dir, events: []const Event) Error!void {
if (events.len > max_events) return error.Full;
if (events.len == 0) {
root.deleteFile(io, filename) catch {};
return;
}
var buf: std.ArrayList(u8) = .empty;
defer buf.deinit(gpa);
try buf.appendSlice(gpa, &magic);
try buf.append(gpa, fmt_version);
try appendInt(gpa, &buf, u32, @intCast(events.len));
for (events) |ev| {
try appendInt(gpa, &buf, u32, ev.id);
try appendInt(gpa, &buf, i64, ev.when);
try appendInt(gpa, &buf, u16, @intCast(@min(ev.reason.len, max_reason_len)));
try buf.appendSlice(gpa, ev.reason[0..@min(ev.reason.len, max_reason_len)]);
try appendInt(gpa, &buf, u32, @intCast(ev.artifacts.len));
for (ev.artifacts) |art| {
try buf.append(gpa, @intCast(art.hash.len));
try buf.appendSlice(gpa, art.hash);
try appendInt(gpa, &buf, u32, @intCast(art.bytes.len));
try buf.appendSlice(gpa, art.bytes);
}
}
try appendInt(gpa, &buf, u32, std.hash.Crc32.hash(buf.items));
var af = root.createFileAtomic(io, filename, .{ .replace = true }) catch return error.Storage;
defer af.deinit(io);
af.file.writePositionalAll(io, buf.items, 0) catch return error.Storage;
af.file.sync(io) catch return error.Storage; // fsync before the rename
af.replace(io) catch return error.Storage;
}
fn appendInt(gpa: std.mem.Allocator, buf: *std.ArrayList(u8), comptime T: type, v: T) Error!void {
var tmp: [@sizeOf(T)]u8 = undefined;
std.mem.writeInt(T, &tmp, v, .little);
try buf.appendSlice(gpa, &tmp);
}
/// The next unused event id: one past the highest held, so an id is never
/// reused even after the event bearing it is obliterated. `purge undo 3` must
/// never mean a different purge than it did yesterday.
pub fn nextId(events: []const Event) u32 {
var high: u32 = 0;
for (events) |ev| high = @max(high, ev.id);
return high + 1;
}
test "graveyard: an event round-trips through write and read" {
const gpa = std.testing.allocator;
const io = std.testing.io;
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const arts = [_]Artifact{
.{ .hash = repeat("aa", 32), .bytes = "the first buried artifact" },
.{ .hash = repeat("bb", 32), .bytes = "" }, // an empty artifact is legal
};
const evs = [_]Event{.{ .id = 7, .when = 1234567890, .reason = "swept in a build tree", .artifacts = &arts }};
try write(gpa, io, tmp.dir, &evs);
var arena = std.heap.ArenaAllocator.init(gpa);
defer arena.deinit();
const back = try read(arena.allocator(), io, tmp.dir);
try std.testing.expectEqual(@as(usize, 1), back.len);
try std.testing.expectEqual(@as(u32, 7), back[0].id);
try std.testing.expectEqualStrings("swept in a build tree", back[0].reason);
try std.testing.expectEqual(@as(usize, 2), back[0].artifacts.len);
try std.testing.expectEqualStrings("the first buried artifact", back[0].artifacts[0].bytes);
try std.testing.expectEqual(@as(u64, 25), back[0].size());
// Ids never reuse, so the next one clears the highest held.
try std.testing.expectEqual(@as(u32, 8), nextId(back));
}
test "graveyard: an absent file is empty, and a damaged one is Corrupt not empty" {
const gpa = std.testing.allocator;
const io = std.testing.io;
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
var arena = std.heap.ArenaAllocator.init(gpa);
defer arena.deinit();
// Nothing buried: an empty set, never an error — the state of every
// repository that has not purged.
try std.testing.expectEqual(@as(usize, 0), (try read(arena.allocator(), io, tmp.dir)).len);
// A damaged graveyard must NOT read as "nothing buried": that would turn a
// recovery store into a silent loss exactly when it is needed.
const evs = [_]Event{.{ .id = 1, .when = 0, .reason = "r", .artifacts = &.{} }};
try write(gpa, io, tmp.dir, &evs);
var f = try tmp.dir.openFile(io, filename, .{ .mode = .read_write });
defer f.close(io);
try f.writePositionalAll(io, "X", magic.len + 1); // corrupt the count
try std.testing.expectError(error.Corrupt, read(arena.allocator(), io, tmp.dir));
}