//! Per-block checksums for the advisory `.zit-cache` sidecars.
//!
//! A sidecar carried one CRC over the whole file, so every open paid a pass
//! over every byte even when the call read a few records: on a 42k-file store
//! that was most of what a one-shot `zit info` cost. Here the body is cut into
//! fixed `block_len` blocks, each with its own CRC in a table; a reader checks
//! a block the first time it touches one and remembers the answer, so the work
//! follows what the call reads. A reader that needs every byte calls
//! `checkAll` and pays what the single CRC cost.
//!
//! The table itself is short (4 bytes per block) and is checked whole by the
//! owner at open, against a CRC its header carries; the header has its own
//! CRC too. So a block is trusted only through two checked links, and a
//! damaged table refuses the sidecar before any block is read.
const std = @import("std");
const crc32 = @import("crc32.zig");
/// One page: a lookup that bisects a sorted table touches a handful of
/// blocks, and each costs about a microsecond to check. Larger blocks made a
/// bisection over a 2 MB index check most of the file.
pub const block_len: usize = 4096;
/// Blocks checksummed by any `Verifier`, process-wide: the evidence tests
/// use to show a reader touched part of a file, or none of it.
pub var blocks_checked: std.atomic.Value(usize) = .init(0);
pub fn blockCount(body_len: usize) usize {
return std.math.divCeil(usize, body_len, block_len) catch unreachable;
}
pub fn tableLen(body_len: usize) usize {
return blockCount(body_len) * 4;
}
/// Fill `table` (`tableLen(body.len)` bytes) with the CRC of each block.
pub fn writeTable(body: []const u8, table: []u8) void {
std.debug.assert(table.len == tableLen(body.len));
var k: usize = 0;
while (k * block_len < body.len) : (k += 1) {
const block = body[k * block_len .. @min(body.len, (k + 1) * block_len)];
std.mem.writeInt(u32, table[k * 4 ..][0..4], crc32.Crc32.hash(block), .little);
}
}
/// Checks blocks of a body against its table on first touch.
pub const Verifier = struct {
body: []const u8,
table: []const u8,
/// Blocks already found good. A bad block is never marked, and `bad`
/// latches so every later check of any block fails too: once one block
/// is known damaged the caller discards the sidecar rather than mixing
/// answers from a file it has stopped trusting.
verified: std.DynamicBitSetUnmanaged,
bad: bool = false,
pub fn init(gpa: std.mem.Allocator, body: []const u8, table: []const u8) error{OutOfMemory}!Verifier {
// A table that does not fit the body checks nothing: every read
// fails, as a damaged block would.
const fits = table.len == tableLen(body.len);
return .{ .body = body, .table = table, .verified = try .initEmpty(gpa, blockCount(body.len)), .bad = !fits };
}
pub fn deinit(self: *Verifier, gpa: std.mem.Allocator) void {
self.verified.deinit(gpa);
self.* = undefined;
}
/// Whether `body[at..at+len]` lies in the body and every block it
/// touches matches its CRC.
pub fn check(self: *Verifier, at: usize, len: usize) bool {
if (self.bad) return false;
if (at > self.body.len or len > self.body.len - at) {
self.bad = true;
return false;
}
if (len == 0) return true;
const first = at / block_len;
const last = (at + len - 1) / block_len;
var k = first;
while (k <= last) : (k += 1) {
if (self.verified.isSet(k)) continue;
const block = self.body[k * block_len .. @min(self.body.len, (k + 1) * block_len)];
_ = blocks_checked.fetchAdd(1, .monotonic);
if (crc32.Crc32.hash(block) != std.mem.readInt(u32, self.table[k * 4 ..][0..4], .little)) {
self.bad = true;
return false;
}
self.verified.set(k);
}
return true;
}
pub fn checkAll(self: *Verifier) bool {
return self.check(0, self.body.len);
}
/// How many blocks have been checked and found good: the evidence that
/// a reader touched only part of the file.
pub fn verifiedCount(self: *const Verifier) usize {
return self.verified.count();
}
};
test "blockcrc: blocks are checked on first touch, and a flip is found only where it lies" {
const gpa = std.testing.allocator;
const body = try gpa.alloc(u8, block_len * 3 + 100);
defer gpa.free(body);
for (body, 0..) |*b, i| b.* = @truncate(i *% 31);
const table = try gpa.alloc(u8, tableLen(body.len));
defer gpa.free(table);
writeTable(body, table);
try std.testing.expectEqual(@as(usize, 16), table.len);
var v = try Verifier.init(gpa, body, table);
defer v.deinit(gpa);
try std.testing.expect(v.check(10, 20));
try std.testing.expectEqual(@as(usize, 1), v.verifiedCount());
// A span across a boundary checks both blocks it touches.
try std.testing.expect(v.check(block_len - 4, 8));
try std.testing.expectEqual(@as(usize, 2), v.verifiedCount());
try std.testing.expect(v.checkAll());
try std.testing.expectEqual(@as(usize, 4), v.verifiedCount());
// Out of range is a failure, never an index past the body.
var w = try Verifier.init(gpa, body, table);
defer w.deinit(gpa);
try std.testing.expect(!w.check(body.len - 2, 4));
// A flip in the last (short) block: the first blocks still check, the
// damaged one does not, and from then on nothing does.
body[block_len * 3 + 50] ^= 0x40;
var x = try Verifier.init(gpa, body, table);
defer x.deinit(gpa);
try std.testing.expect(x.check(0, block_len * 3));
try std.testing.expect(!x.check(block_len * 3, 1));
try std.testing.expect(!x.check(0, 1));
try std.testing.expect(!x.checkAll());
}
test "blockcrc: an empty body has no blocks and checks clean" {
const gpa = std.testing.allocator;
var v = try Verifier.init(gpa, &.{}, &.{});
defer v.deinit(gpa);
try std.testing.expect(v.checkAll());
try std.testing.expect(v.check(0, 0));
try std.testing.expect(!v.check(0, 1));
}