//! The text/binary class of blobs `ls --long` has already read, kept in
//! `.zit-cache` so a later listing can reuse the class after verifying content.
//!
//! A blob's class is a NUL anywhere in its bytes (`textdiff.isBinary`), so it
//! is a pure function of the bytes, and the bytes are a pure function of the
//! blob's name. A record keyed by the name can therefore never go stale: no
//! log key, no shun fingerprint, and no write path has to know about it. The
//! memo says nothing about availability. A reader still asks the store whether
//! the blob can be produced, so a blob shunned or elided after it was recorded
//! is still reported as absent.
//!
//! The memo is filled lazily: a lookup that misses costs the read it always
//! did, and the class it learns is merged in when the listing ends. It holds
//! only blobs that were listed, never the whole store, and at most
//! `max_records` of them. A missing, damaged or foreign sidecar is a miss,
//! never an error. Every write replaces the whole file atomically, so two
//! concurrent writers cannot corrupt it: the last one wins, and the loser's
//! classes are simply learned again.
//!
//! Blob layout:
//!
//! magic(8) | version(2) | count(4) | count x record | crc(4)
//! record = digest(32) | meta(1)
//!
//! `digest` is the binary artifact name, a SHA1 name zero-padded to 32 bytes.
//! `meta` bit 0 is the class (1 = binary), bit 1 marks a SHA1 name. Records
//! are sorted ascending by (digest, SHA1 bit) with no key repeated, so a
//! lookup is a binary search over the stored bytes, with no per-record decode.
const std = @import("std");
const repocache = @import("repocache.zig");
const crc32 = @import("crc32.zig");
const magic: *const [8]u8 = "zitbcls\x00";
const version: u16 = 1;
pub const header_len = 8 + 2 + 4;
pub const record_len = 32 + 1;
/// The most records a memo keeps. A listing that would grow it past this
/// starts it over with what that listing learned: the blobs being listed now
/// are the ones worth remembering.
pub const max_records: u32 = 1 << 21;
const meta_binary: u8 = 1;
const meta_sha1: u8 = 2;
pub const Class = enum { text, binary };
/// A memo key: the binary form of an artifact name.
pub const Key = struct {
digest: [32]u8,
sha1: bool,
/// The key for a 40-hex (SHA1) or 64-hex (SHA3-256) artifact name, or
/// null for anything else. A null key is never memoized.
pub fn ofName(name: []const u8) ?Key {
var k: Key = .{ .digest = @splat(0), .sha1 = name.len == 40 };
if (name.len != 40 and name.len != 64) return null;
_ = std.fmt.hexToBytes(k.digest[0 .. name.len / 2], name) catch return null;
return k;
}
};
fn recordOf(key: Key, class: Class) [record_len]u8 {
var r: [record_len]u8 = undefined;
r[0..32].* = key.digest;
r[32] = (if (key.sha1) meta_sha1 else 0) | (if (class == .binary) meta_binary else 0);
return r;
}
/// Order two records by key alone; the class bit never takes part.
fn orderRecords(a: []const u8, b: []const u8) std.math.Order {
std.debug.assert(a.len == record_len and b.len == record_len);
const o = std.mem.order(u8, a[0..32], b[0..32]);
if (o != .eq) return o;
return std.math.order(a[32] & meta_sha1, b[32] & meta_sha1);
}
fn lessRecord(_: void, a: [record_len]u8, b: [record_len]u8) bool {
return orderRecords(&a, &b) == .lt;
}
/// The record bytes of a stored blob, or null when it is not a memo this
/// build wrote: wrong magic or version, a length that is not a whole number
/// of records, a failed CRC, or records out of order. The slice borrows
/// `blob`.
pub fn parse(blob: []const u8) ?[]const u8 {
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;
const count = std.mem.readInt(u32, blob[10..14], .little);
if (count > max_records) return null;
if (blob.len != header_len + @as(usize, count) * record_len + 4) return null;
if (std.mem.readInt(u32, blob[blob.len - 4 ..][0..4], .little) != crc32.Crc32.hash(blob[0 .. blob.len - 4])) return null;
const records = blob[header_len .. blob.len - 4];
var i: usize = record_len;
while (i < records.len) : (i += record_len) {
const prev = records[i - record_len ..][0..record_len];
if (orderRecords(prev, records[i..][0..record_len]) != .lt) return null;
}
return records;
}
/// The class recorded for `key` in `records` (as `parse` returned them).
pub fn lookup(records: []const u8, key: Key) ?Class {
std.debug.assert(records.len % record_len == 0);
const want = recordOf(key, .text);
var lo: usize = 0;
var hi: usize = records.len / record_len;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
const r = records[mid * record_len ..][0..record_len];
switch (orderRecords(r, &want)) {
.lt => lo = mid + 1,
.gt => hi = mid,
.eq => return if (r[32] & meta_binary != 0) .binary else .text,
}
}
return null;
}
/// Serialize the union of `records` (sorted, as `parse` returned them) and
/// `learned` (any order, repeats allowed). `learned` is sorted in place. A
/// union past `max_records` keeps only `learned`, capped.
pub fn merge(gpa: std.mem.Allocator, records: []const u8, learned: [][record_len]u8) error{OutOfMemory}![]u8 {
return mergeCapped(gpa, records, learned, max_records);
}
fn mergeCapped(gpa: std.mem.Allocator, records: []const u8, learned: [][record_len]u8, cap: u32) error{OutOfMemory}![]u8 {
std.debug.assert(records.len % record_len == 0);
std.debug.assert(cap <= max_records);
std.mem.sort([record_len]u8, learned, {}, lessRecord);
var old = records;
if (old.len / record_len + learned.len > cap) old = &.{};
const fresh = learned[0..@min(learned.len, cap)];
const bound = old.len / record_len + fresh.len;
const blob = try gpa.alloc(u8, header_len + bound * record_len + 4);
errdefer gpa.free(blob);
var pos: usize = header_len;
var i: usize = 0; // into old, by record
var j: usize = 0; // into fresh
while (i < old.len or j < fresh.len) {
const take_old = j == fresh.len or
(i < old.len and orderRecords(old[i..][0..record_len], &fresh[j]) == .lt);
const r: []const u8 = if (take_old) old[i..][0..record_len] else &fresh[j];
if (take_old) i += record_len else j += 1;
// Equal keys carry equal classes, so a repeat is dropped, whichever
// side it came from.
if (pos > header_len and orderRecords(blob[pos - record_len ..][0..record_len], r) == .eq) continue;
@memcpy(blob[pos..][0..record_len], r);
pos += record_len;
}
const count = (pos - header_len) / record_len;
std.debug.assert(count <= cap);
const out = blob[0 .. pos + 4];
@memcpy(out[0..8], magic);
std.mem.writeInt(u16, out[8..10], version, .little);
std.mem.writeInt(u32, out[10..14], @intCast(count), .little);
std.mem.writeInt(u32, out[pos..][0..4], crc32.Crc32.hash(out[0..pos]), .little);
return gpa.realloc(blob, out.len);
}
/// One listing's view of the memo: the records loaded from `.zit-cache`, and
/// what this listing learns on top of them.
pub const Memo = struct {
stored: ?[]u8 = null,
records: []const u8 = &.{},
learned: std.ArrayList([record_len]u8) = .empty,
learned_index: std.AutoHashMapUnmanaged(Key, Class) = .empty,
/// Load the memo from `dir`'s `.zit-cache`. Absent or damaged is empty.
pub fn load(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) error{OutOfMemory}!Memo {
const blob = (try repocache.loadMember(gpa, io, dir, repocache.blobclass_member)) orelse return .{};
const records = parse(blob) orelse {
gpa.free(blob);
return .{};
};
return .{ .stored = blob, .records = records };
}
pub fn deinit(self: *Memo, gpa: std.mem.Allocator) void {
if (self.stored) |b| gpa.free(b);
self.learned.deinit(gpa);
self.learned_index.deinit(gpa);
self.* = undefined;
}
pub fn get(self: *const Memo, name: []const u8) ?Class {
const key = Key.ofName(name) orelse return null;
return self.learned_index.get(key) orelse lookup(self.records, key);
}
/// Note `name`'s class, visible immediately and later written by `store`.
pub fn put(self: *Memo, gpa: std.mem.Allocator, name: []const u8, class: Class) error{OutOfMemory}!void {
const key = Key.ofName(name) orelse return;
if (self.learned_index.contains(key) or lookup(self.records, key) != null) return;
try self.learned_index.ensureUnusedCapacity(gpa, 1);
try self.learned.append(gpa, recordOf(key, class));
self.learned_index.putAssumeCapacity(key, class);
}
/// Write the merged memo back, atomically, when anything was learned.
/// Advisory: an unwritable cache is simply not kept.
pub fn store(self: *Memo, gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) error{OutOfMemory}!void {
if (self.learned.items.len == 0) return;
const blob = try merge(gpa, self.records, self.learned.items);
defer gpa.free(blob);
repocache.storeNamedMember(io, dir, repocache.blobclass_member, blob);
}
};
const testing = std.testing;
fn testName(buf: *[64]u8, len: usize, seed: u8) []const u8 {
for (buf[0..len], 0..) |*c, i| c.* = "0123456789abcdef"[(seed + i * 7) % 16];
return buf[0..len];
}
test "blobclass: merge then parse answers every learned name, and only those" {
const gpa = testing.allocator;
var b1: [64]u8 = undefined;
var b2: [64]u8 = undefined;
var b3: [64]u8 = undefined;
const sha3 = testName(&b1, 64, 3);
const sha1 = testName(&b2, 40, 3); // same leading bytes as `sha3`
const other = testName(&b3, 64, 9);
var learned = [_][record_len]u8{
recordOf(Key.ofName(sha3).?, .binary),
recordOf(Key.ofName(sha1).?, .text),
recordOf(Key.ofName(sha3).?, .binary), // a repeat within one listing
};
const blob = try merge(gpa, &.{}, &learned);
defer gpa.free(blob);
const records = parse(blob).?;
try testing.expectEqual(@as(usize, 2 * record_len), records.len);
try testing.expectEqual(Class.binary, lookup(records, Key.ofName(sha3).?).?);
try testing.expectEqual(Class.text, lookup(records, Key.ofName(sha1).?).?);
try testing.expectEqual(@as(?Class, null), lookup(records, Key.ofName(other).?));
// A second merge keeps the old records and adds the new one.
var more = [_][record_len]u8{recordOf(Key.ofName(other).?, .text)};
const blob2 = try merge(gpa, records, &more);
defer gpa.free(blob2);
const records2 = parse(blob2).?;
try testing.expectEqual(@as(usize, 3 * record_len), records2.len);
try testing.expectEqual(Class.binary, lookup(records2, Key.ofName(sha3).?).?);
try testing.expectEqual(Class.text, lookup(records2, Key.ofName(other).?).?);
}
test "blobclass: a damaged, truncated or foreign blob is a miss" {
const gpa = testing.allocator;
var b1: [64]u8 = undefined;
var learned = [_][record_len]u8{recordOf(Key.ofName(testName(&b1, 64, 1)).?, .binary)};
const blob = try merge(gpa, &.{}, &learned);
defer gpa.free(blob);
try testing.expect(parse(blob) != null);
const copy = try gpa.dupe(u8, blob);
defer gpa.free(copy);
copy[header_len + 32] ^= meta_binary; // flip the class bit
try testing.expectEqual(@as(?[]const u8, null), parse(copy));
try testing.expectEqual(@as(?[]const u8, null), parse(blob[0 .. blob.len - 1]));
try testing.expectEqual(@as(?[]const u8, null), parse(""));
try testing.expectEqual(@as(?[]const u8, null), parse("zitxxxx\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00"));
// Out of order but correctly checksummed is still refused.
var two = [_][record_len]u8{
recordOf(Key.ofName(testName(&b1, 64, 1)).?, .text),
recordOf(Key.ofName(testName(&b1, 64, 5)).?, .text),
};
const ordered = try merge(gpa, &.{}, &two);
defer gpa.free(ordered);
const swapped = try gpa.dupe(u8, ordered);
defer gpa.free(swapped);
const recs = swapped[header_len..][0 .. 2 * record_len];
var tmp: [record_len]u8 = recs[0..record_len].*;
@memcpy(recs[0..record_len], recs[record_len..]);
@memcpy(recs[record_len..], &tmp);
std.mem.writeInt(u32, swapped[swapped.len - 4 ..][0..4], crc32.Crc32.hash(swapped[0 .. swapped.len - 4]), .little);
try testing.expectEqual(@as(?[]const u8, null), parse(swapped));
}
test "blobclass: a union past the cap starts over with what was learned" {
const gpa = testing.allocator;
var b: [64]u8 = undefined;
var first = [_][record_len]u8{
recordOf(Key.ofName(testName(&b, 64, 1)).?, .text),
recordOf(Key.ofName(testName(&b, 64, 2)).?, .text),
};
const blob = try mergeCapped(gpa, &.{}, &first, 2);
defer gpa.free(blob);
var next = [_][record_len]u8{recordOf(Key.ofName(testName(&b, 64, 3)).?, .binary)};
const blob2 = try mergeCapped(gpa, parse(blob).?, &next, 2);
defer gpa.free(blob2);
const records = parse(blob2).?;
try testing.expectEqual(@as(usize, record_len), records.len);
try testing.expectEqual(Class.binary, lookup(records, Key.ofName(testName(&b, 64, 3)).?).?);
try testing.expectEqual(@as(?Class, null), lookup(records, Key.ofName(testName(&b, 64, 1)).?));
}
test "blobclass: a listing immediately sees newly learned classes" {
var m: Memo = .{};
defer m.deinit(testing.allocator);
var buf: [64]u8 = undefined;
const name = testName(&buf, 64, 3);
try testing.expectEqual(@as(?Class, null), m.get(name));
try m.put(testing.allocator, name, .binary);
try testing.expectEqual(@as(?Class, .binary), m.get(name));
try m.put(testing.allocator, name, .binary);
try testing.expectEqual(@as(usize, 1), m.learned.items.len);
}
test "blobclass: learning is allocation-failure safe" {
try testing.checkAllAllocationFailures(testing.allocator, struct {
fn run(gpa: std.mem.Allocator) !void {
var m: Memo = .{};
defer m.deinit(gpa);
var buf: [64]u8 = undefined;
const name = testName(&buf, 64, 3);
try m.put(gpa, name, .binary);
try testing.expectEqual(@as(?Class, .binary), m.get(name));
}
}.run, .{});
}
test "blobclass: names that are not artifact hashes are never memoized" {
try testing.expectEqual(@as(?Key, null), Key.ofName("abc"));
try testing.expectEqual(@as(?Key, null), Key.ofName("z000000000000000000000000000000000000000"));
var m: Memo = .{};
defer m.deinit(testing.allocator);
try m.put(testing.allocator, "not-a-hash", .binary);
try testing.expectEqual(@as(usize, 0), m.learned.items.len);
try testing.expectEqual(@as(?Class, null), m.get("not-a-hash"));
}