//! A list of artifact names, kept in `.zit-cache` and keyed to the log
//! prefix it was built over.
//!
//! Some readers need every artifact of one kind: sync the clusters, `landing`
//! the forum posts. Finding them means reading every entry in the store,
//! which is linear in store bytes. The store is append-only, so the answer
//! for a prefix never changes: a list of names built over that prefix stays
//! true, and a later reader only has to walk what was appended since.
//!
//! The list is adopted when the log prefix it was keyed to is still intact
//! (`LogStore.validatePrefix`), extended over the tail, and stored again. A
//! rewrite (`pack`, `shun --force`) replaces the file, the key no longer
//! validates, and the list is rebuilt by one full walk. A missing, damaged or
//! foreign sidecar is a rebuild, never an error: deleting it changes no
//! answer.
//!
//! The list holds NAMES, not content. A reader re-reads each named artifact
//! through the store, which applies the shun mask, so a shunned artifact drops
//! out without the list knowing about shuns. The walk records names without
//! the mask for the same reason: an artifact shunned when the list was built
//! and unshunned later is still found.
//!
//! Blob layout, one per kind, told apart by `magic`:
//!
//! magic(8) | version(2) | end(8) | frame_count(8) | last_frame_offset(8) |
//! last_header_crc(4) | n_rids(8) | count(4) | count x (len(1) name) | crc(4)
const std = @import("std");
const logstore = @import("logstore.zig");
const repocache = @import("repocache.zig");
const crc32 = @import("crc32.zig");
const Rid = logstore.Rid;
const version: u16 = 1;
/// Bytes before the first name.
pub const header_len = 8 + 2 + 8 + 8 + 8 + 4 + 8 + 4;
/// Evidence seam: store entries a walk read to find names. Zero when the list
/// was adopted over an unchanged store.
pub var walk_rids: u64 = 0;
/// Serialize `names`, covering the first `n_rids` store entries, keyed to
/// `log`'s current prefix. Null when the key cannot be read or a name does not
/// fit its length byte; the caller then keeps no sidecar.
pub fn serialize(
gpa: std.mem.Allocator,
magic: *const [8]u8,
log: *const logstore.LogStore,
n_rids: u64,
names: []const []const u8,
) error{OutOfMemory}!?[]u8 {
const key = log.logKey() catch return null;
var body: usize = 0;
for (names) |nm| {
if (nm.len > 255) return null;
body += 1 + nm.len;
}
const blob = try gpa.alloc(u8, header_len + body + 4);
errdefer gpa.free(blob);
@memcpy(blob[0..8], magic);
std.mem.writeInt(u16, blob[8..10], version, .little);
std.mem.writeInt(u64, blob[10..18], key.end, .little);
std.mem.writeInt(u64, blob[18..26], key.frame_count, .little);
std.mem.writeInt(u64, blob[26..34], key.last_frame_offset, .little);
std.mem.writeInt(u32, blob[34..38], key.last_header_crc, .little);
std.mem.writeInt(u64, blob[38..46], n_rids, .little);
std.mem.writeInt(u32, blob[46..50], @intCast(names.len), .little);
var pos: usize = header_len;
for (names) |nm| {
blob[pos] = @intCast(nm.len);
@memcpy(blob[pos + 1 ..][0..nm.len], nm);
pos += 1 + nm.len;
}
std.debug.assert(pos == blob.len - 4);
var crc = crc32.Crc32.init();
crc.update(blob[0 .. blob.len - 4]);
std.mem.writeInt(u32, blob[blob.len - 4 ..][0..4], crc.final(), .little);
return blob;
}
pub const Parsed = struct {
/// Store entries the names cover; a tail walk begins after this rid.
n_rids: u64,
/// Borrowed from the blob.
names: []const []const u8,
};
/// Adopt a sidecar blob against `log`: magic, version, CRC, and the log
/// prefix it was keyed to must all hold, or the answer is null and the caller
/// rebuilds. The name slice is allocated from `arena`; the names borrow `blob`.
pub fn parse(
arena: std.mem.Allocator,
magic: *const [8]u8,
blob: []const u8,
log: *const logstore.LogStore,
) error{OutOfMemory}!?Parsed {
if (blob.len < header_len + 4) return null;
if (!std.mem.eql(u8, blob[0..8], magic)) return null;
if (std.mem.readInt(u16, blob[8..10], .little) != version) return null;
var crc = crc32.Crc32.init();
crc.update(blob[0 .. blob.len - 4]);
if (std.mem.readInt(u32, blob[blob.len - 4 ..][0..4], .little) != crc.final()) return null;
const key = logstore.LogStore.LogKey{
.end = std.mem.readInt(u64, blob[10..18], .little),
.frame_count = std.mem.readInt(u64, blob[18..26], .little),
.last_frame_offset = std.mem.readInt(u64, blob[26..34], .little),
.last_header_crc = std.mem.readInt(u32, blob[34..38], .little),
};
if (!logstore.LogStore.validatePrefix(log.file, key)) return null;
const n_rids = std.mem.readInt(u64, blob[38..46], .little);
const count = std.mem.readInt(u32, blob[46..50], .little);
var names = try arena.alloc([]const u8, count);
var pos: usize = header_len;
var i: usize = 0;
while (i < count) : (i += 1) {
if (pos >= blob.len - 4) return null;
const len: usize = blob[pos];
if (pos + 1 + len > blob.len - 4) return null;
names[i] = blob[pos + 1 ..][0..len];
pos += 1 + len;
}
if (pos != blob.len - 4) return null;
return .{ .n_rids = n_rids, .names = names };
}
/// One kind of index: its sidecar's magic and file name, and which artifacts
/// it names.
pub const Kind = struct {
magic: *const [8]u8,
/// The member's name inside `.zit-cache`.
member: []const u8,
/// Whether an artifact with this (unmasked) content belongs in the list.
keep: *const fn (gpa: std.mem.Allocator, content: []const u8) bool,
};
/// The names of every artifact of `kind` in `log`, in store order: the
/// sidecar in `dir`'s `.zit-cache` adopted when its key validates, the
/// appended tail walked, the refreshed sidecar stored. Names are lowercase hex
/// and allocated from `arena`. Nothing here fails but memory: an unreadable
/// sidecar is a rebuild, an unwritable one is simply not kept, and an entry
/// that cannot be read is not named.
pub fn refresh(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
io: std.Io,
dir: std.Io.Dir,
log: *logstore.LogStore,
kind: Kind,
) error{OutOfMemory}![]const []const u8 {
var names: std.ArrayListUnmanaged([]const u8) = .empty;
var after: Rid = 0;
var adopted = false;
if (try repocache.loadMember(gpa, io, dir, kind.member)) |blob| {
defer gpa.free(blob);
if (try parse(arena, kind.magic, blob, log)) |p| {
try names.ensureTotalCapacity(arena, p.names.len);
for (p.names) |n| names.appendAssumeCapacity(try arena.dupe(u8, n));
after = @intCast(p.n_rids);
adopted = true;
}
}
const n: Rid = @intCast(log.entryCount());
// A list covering more entries than this store has was not built over
// this store's prefix, whatever its key says: rebuild.
if (after > n) {
names.clearRetainingCapacity();
after = 0;
adopted = false;
}
if (after < n) {
var cache = logstore.PlaintextCache.init();
defer cache.deinit(gpa);
var rid: Rid = after + 1;
while (rid <= n) : (rid += 1) {
if (log.isPhantom(rid)) continue;
walk_rids += 1;
const plain = (log.contentUnmasked(gpa, rid, &cache) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Storage, error.Corrupt => continue,
}) orelse continue;
defer gpa.free(plain);
if (!kind.keep(gpa, plain)) continue;
var hex_buf: [64]u8 = undefined;
try names.append(arena, try arena.dupe(u8, hexName(&hex_buf, log.hashOf(rid))));
}
}
if (!adopted or after < n) {
if (try serialize(gpa, kind.magic, log, n, names.items)) |blob| {
defer gpa.free(blob);
repocache.storeNamedMember(io, dir, kind.member, blob);
}
}
return names.items;
}
/// The lowercase-hex name of a stored digest: SHA3-256 (32 bytes) or SHA1
/// (20 bytes).
fn hexName(out: *[64]u8, digest: []const u8) []const u8 {
std.debug.assert(digest.len * 2 <= out.len);
const alphabet = "0123456789abcdef";
for (digest, 0..) |b, i| {
out[2 * i] = alphabet[b >> 4];
out[2 * i + 1] = alphabet[b & 15];
}
return out[0 .. 2 * digest.len];
}
test "nameindex: a list is adopted only under its own magic and its own log prefix" {
const gpa = std.testing.allocator;
const io = std.testing.io;
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const raw = try tmp.dir.createFile(io, "log", .{ .read = true });
var fs = @import("storage.zig").FileStorage.init(io, raw, 0);
var log = try logstore.LogStore.open(gpa, fs.storageFile(), 0);
defer log.deinit(gpa);
var arena = std.heap.ArenaAllocator.init(gpa);
defer arena.deinit();
// A list over an empty log is keyed to an empty prefix, which every log
// extends; key this one to a real frame.
_ = try log.putArtifact(&([_]u8{5} ** 32), "the first artifact", null);
try log.commit();
const names = [_][]const u8{"c" ** 64};
const blob = (try serialize(gpa, "ZITFORM\x00", &log, 1, &names)).?;
defer gpa.free(blob);
const p = (try parse(arena.allocator(), "ZITFORM\x00", blob, &log)).?;
try std.testing.expectEqual(@as(u64, 1), p.n_rids);
try std.testing.expectEqualStrings(names[0], p.names[0]);
// Another kind's sidecar is a rebuild, never a list of the wrong names.
try std.testing.expect((try parse(arena.allocator(), "ZITCLIX\x00", blob, &log)) == null);
// Appending keeps the prefix: still adopted. A different log is not.
_ = try log.putArtifact(&([_]u8{7} ** 32), "an appended artifact", null);
try log.commit();
try std.testing.expect((try parse(arena.allocator(), "ZITFORM\x00", blob, &log)) != null);
const other_raw = try tmp.dir.createFile(io, "other", .{ .read = true });
var other_fs = @import("storage.zig").FileStorage.init(io, other_raw, 0);
var other = try logstore.LogStore.open(gpa, other_fs.storageFile(), 0);
defer other.deinit(gpa);
_ = try other.putArtifact(&([_]u8{9} ** 32), "a different store entirely", null);
try other.commit();
try std.testing.expect((try parse(arena.allocator(), "ZITFORM\x00", blob, &other)) == null);
}