//! The witness's per-commit half, spilled to a working file of the run.
//!
//! Held in memory, the witness cost about a kilobyte and a quarter a commit --
//! two gigabytes at the Linux kernel's length, alongside the importer it was
//! copied from -- while every clause that reads it walks it in stream order.
//! So each commit is written once, at capture, as one record, and the
//! verifier reads the file back a window at a time.
//!
//! The file sits in staging, beside the evidence it is compared against, so
//! it must be no easier to alter than the in-memory copy it replaces. Every
//! record is authenticated under a key drawn per run and never written down,
//! over its position in the stream as well as its bytes: a flipped byte, a
//! truncation, a reordering or a record carried over from another run reads
//! as `error.Corrupt`, never as a different commit.
//!
//! Record: payload length (u32, little-endian), payload, SipHash-128 tag of
//! (index ‖ payload). Strings are a u32 length then their bytes.
const std = @import("std");
const impl = @import("git_import_impl.zig");
const WitnessCommit = impl.WitnessCommit;
const WitnessIdentity = impl.WitnessIdentity;
const WitnessCandidate = impl.WitnessCandidate;
const candidate_paths = impl.mirror_candidate_names;
const Mac = std.crypto.auth.siphash.SipHash128(2, 4);
pub const Key = [Mac.key_length]u8;
/// The longest payload either side admits. A record holds two identities of
/// at most one fast-export line each and a commit's parent run, so this
/// refuses only a corrupt length -- before it becomes an allocation.
pub const max_payload: usize = 64 << 20;
pub const Error = error{ Corrupt, ReadFailed, OutOfMemory };
pub const Writer = struct {
gpa: std.mem.Allocator,
out: *std.Io.Writer,
key: Key,
scratch: std.ArrayList(u8) = .empty,
count: u64 = 0,
pub fn deinit(self: *Writer) void {
self.scratch.deinit(self.gpa);
}
pub fn add(self: *Writer, commit: *const WitnessCommit) !void {
const payload = &self.scratch;
payload.clearRetainingCapacity();
const gpa = self.gpa;
try payload.append(gpa, @intFromBool(commit.oid != null));
if (commit.oid) |oid| try putString(gpa, payload, oid);
try putString(gpa, payload, commit.checkin);
try putStrings(gpa, payload, commit.parents);
try putStrings(gpa, payload, commit.parent_oids);
try putIdentity(gpa, payload, commit.author);
try putIdentity(gpa, payload, commit.committer);
try payload.appendSlice(gpa, &commit.tree_digest);
try payload.appendSlice(gpa, &commit.provenance_digest);
try payload.append(gpa, @backingInt(commit.decision));
try payload.append(gpa, @backingInt(commit.reason));
for (commit.candidates) |slot| {
const candidate = slot orelse {
try payload.append(gpa, 0);
continue;
};
const path = for (candidate_paths, 0..) |name, at| {
if (std.mem.eql(u8, name, candidate.path)) break at;
} else return error.WitnessCandidatePathUnknown;
try payload.append(gpa, 1 + @as(u8, @intCast(path)));
try putString(gpa, payload, candidate.name);
try payload.append(gpa, @intFromBool(candidate.oid != null));
if (candidate.oid) |oid| try putString(gpa, payload, oid);
}
if (payload.items.len > max_payload) return error.WitnessRecordTooLong;
try self.out.writeInt(u32, @intCast(payload.items.len), .little);
try self.out.writeAll(payload.items);
try self.out.writeAll(&tag(&self.key, self.count, payload.items));
self.count += 1;
}
fn putString(gpa: std.mem.Allocator, payload: *std.ArrayList(u8), text: []const u8) !void {
if (text.len > max_payload) return error.WitnessRecordTooLong;
var length: [4]u8 = undefined;
std.mem.writeInt(u32, &length, @intCast(text.len), .little);
try payload.appendSlice(gpa, &length);
try payload.appendSlice(gpa, text);
}
fn putStrings(gpa: std.mem.Allocator, payload: *std.ArrayList(u8), texts: []const []const u8) !void {
var count: [4]u8 = undefined;
std.mem.writeInt(u32, &count, @intCast(texts.len), .little);
try payload.appendSlice(gpa, &count);
for (texts) |text| try putString(gpa, payload, text);
}
fn putIdentity(gpa: std.mem.Allocator, payload: *std.ArrayList(u8), identity: WitnessIdentity) !void {
try putString(gpa, payload, identity.name);
try putString(gpa, payload, identity.email);
var fixed: [10]u8 = undefined;
std.mem.writeInt(i64, fixed[0..8], identity.timestamp, .little);
std.mem.writeInt(i16, fixed[8..10], identity.timezone_offset_minutes, .little);
try payload.appendSlice(gpa, &fixed);
}
};
/// Reads the records back in order. Every string a returned commit holds is
/// a slice of the payload allocated from `arena`, so a window of commits is
/// freed by resetting it.
pub const Reader = struct {
in: *std.Io.Reader,
key: *const Key,
count: u64,
index: u64 = 0,
/// The next commit, or null after the last -- which is also where a file
/// that carries more than `count` records is refused.
pub fn next(self: *Reader, arena: std.mem.Allocator) Error!?WitnessCommit {
if (self.index == self.count) {
var extra: [1]u8 = undefined;
const read = self.in.readSliceShort(&extra) catch return error.ReadFailed;
if (read != 0) return error.Corrupt;
return null;
}
var length_bytes: [4]u8 = undefined;
try self.readAll(&length_bytes);
const length = std.mem.readInt(u32, &length_bytes, .little);
if (length > max_payload) return error.Corrupt;
const payload = try arena.alloc(u8, length);
try self.readAll(payload);
var stored: [Mac.mac_length]u8 = undefined;
try self.readAll(&stored);
const expected = tag(self.key, self.index, payload);
if (!std.crypto.timing_safe.eql([Mac.mac_length]u8, stored, expected)) return error.Corrupt;
self.index += 1;
var cursor: Cursor = .{ .bytes = payload };
const commit = cursor.commit(arena) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => return error.Corrupt,
};
if (cursor.at != payload.len) return error.Corrupt;
return commit;
}
fn readAll(self: *Reader, buffer: []u8) Error!void {
self.in.readSliceAll(buffer) catch |e| switch (e) {
error.EndOfStream => return error.Corrupt,
error.ReadFailed => return error.ReadFailed,
};
}
};
fn tag(key: *const Key, index: u64, payload: []const u8) [Mac.mac_length]u8 {
var mac = Mac.init(key);
var position: [8]u8 = undefined;
std.mem.writeInt(u64, &position, index, .little);
mac.update(&position);
mac.update(payload);
return mac.finalResult();
}
/// Decodes one authenticated payload. Authenticated is not the same as well
/// formed -- a writer defect would be authenticated too -- so every length,
/// enum and flag is still checked.
const Cursor = struct {
bytes: []const u8,
at: usize = 0,
fn commit(self: *Cursor, arena: std.mem.Allocator) error{ Corrupt, OutOfMemory }!WitnessCommit {
const oid = try self.optionalString();
const checkin = try self.string();
const parents = try self.strings(arena);
const parent_oids = try self.strings(arena);
const author = try self.identity();
const committer = try self.identity();
const tree_digest = (try self.take(32))[0..32].*;
const provenance_digest = (try self.take(32))[0..32].*;
const decision = std.enums.fromInt(impl.MirrorDecisionKind, try self.byte()) orelse return error.Corrupt;
const reason = std.enums.fromInt(impl.MirrorRetainReason, try self.byte()) orelse return error.Corrupt;
var candidates: [candidate_paths.len]?WitnessCandidate = @splat(null);
for (&candidates) |*slot| {
const path = try self.byte();
if (path == 0) continue;
if (path > candidate_paths.len) return error.Corrupt;
slot.* = .{
.path = candidate_paths[path - 1],
.name = try self.string(),
.oid = try self.optionalString(),
};
}
return .{
.oid = oid,
.checkin = checkin,
.parents = parents,
.parent_oids = parent_oids,
.author = author,
.committer = committer,
.tree_digest = tree_digest,
.provenance_digest = provenance_digest,
.decision = decision,
.reason = reason,
.candidates = candidates,
};
}
fn take(self: *Cursor, len: usize) error{Corrupt}![]const u8 {
if (self.bytes.len - self.at < len) return error.Corrupt;
defer self.at += len;
return self.bytes[self.at..][0..len];
}
fn byte(self: *Cursor) error{Corrupt}!u8 {
return (try self.take(1))[0];
}
fn int(self: *Cursor, comptime T: type) error{Corrupt}!T {
return std.mem.readInt(T, (try self.take(@sizeOf(T)))[0..@sizeOf(T)], .little);
}
fn string(self: *Cursor) error{Corrupt}![]const u8 {
return self.take(try self.int(u32));
}
fn optionalString(self: *Cursor) error{Corrupt}!?[]const u8 {
return switch (try self.byte()) {
0 => null,
1 => try self.string(),
else => error.Corrupt,
};
}
fn strings(self: *Cursor, arena: std.mem.Allocator) error{ Corrupt, OutOfMemory }![]const []const u8 {
const count = try self.int(u32);
// Each string costs at least its length word, so a count the payload
// cannot hold is refused before it sizes an allocation.
if (count > (self.bytes.len - self.at) / 4) return error.Corrupt;
const out = try arena.alloc([]const u8, count);
for (out) |*text| text.* = try self.string();
return out;
}
fn identity(self: *Cursor) error{Corrupt}!WitnessIdentity {
return .{
.name = try self.string(),
.email = try self.string(),
.timestamp = try self.int(i64),
.timezone_offset_minutes = try self.int(i16),
};
}
};
// -- tests ------------------------------------------------------------------
const testing = std.testing;
fn fixtureCommits() [3]WitnessCommit {
const none: [candidate_paths.len]?WitnessCandidate = @splat(null);
var with_candidates = none;
with_candidates[0] = .{ .path = candidate_paths[0], .name = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", .oid = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" };
with_candidates[2] = .{ .path = candidate_paths[2], .name = "cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc", .oid = null };
return .{
.{
.oid = "1111111111111111111111111111111111111111",
.checkin = "d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1",
.parents = &.{},
.parent_oids = &.{},
.author = .{ .name = "A U Thor", .email = "[email protected]", .timestamp = 1_100_000_000, .timezone_offset_minutes = -420 },
.committer = .{ .name = "C O Mitter", .email = "[email protected]", .timestamp = 1_100_000_001, .timezone_offset_minutes = 60 },
.tree_digest = @splat(0x11),
.provenance_digest = @splat(0x22),
.decision = .none,
.reason = .no_candidates,
.candidates = none,
},
.{
.oid = null,
.checkin = "d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2",
.parents = &.{ "d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1d1", "d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0d0" },
.parent_oids = &.{ "1111111111111111111111111111111111111111", "" },
.author = .{ .name = "", .email = "", .timestamp = -1, .timezone_offset_minutes = 0 },
.committer = .{ .name = "\xff\x00 bytes", .email = "x", .timestamp = 0, .timezone_offset_minutes = 840 },
.tree_digest = @splat(0x33),
.provenance_digest = @splat(0x44),
.decision = .retained,
.reason = .incomplete_pair,
.candidates = with_candidates,
},
.{
.oid = "3333333333333333333333333333333333333333",
.checkin = "d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3",
.parents = &.{"d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2"},
.parent_oids = &.{""},
.author = .{ .name = "A U Thor", .email = "[email protected]", .timestamp = 7, .timezone_offset_minutes = 1 },
.committer = .{ .name = "A U Thor", .email = "[email protected]", .timestamp = 7, .timezone_offset_minutes = 1 },
.tree_digest = @splat(0x55),
.provenance_digest = @splat(0x66),
.decision = .omitted,
.reason = .no_candidates,
.candidates = with_candidates,
},
};
}
fn expectSameCommit(want: WitnessCommit, got: WitnessCommit) !void {
if (want.oid) |oid| try testing.expectEqualStrings(oid, got.oid.?) else try testing.expect(got.oid == null);
try testing.expectEqualStrings(want.checkin, got.checkin);
try testing.expectEqual(want.parents.len, got.parents.len);
for (want.parents, got.parents) |a, b| try testing.expectEqualStrings(a, b);
try testing.expectEqual(want.parent_oids.len, got.parent_oids.len);
for (want.parent_oids, got.parent_oids) |a, b| try testing.expectEqualStrings(a, b);
for ([_]WitnessIdentity{ want.author, want.committer }, [_]WitnessIdentity{ got.author, got.committer }) |a, b| {
try testing.expectEqualStrings(a.name, b.name);
try testing.expectEqualStrings(a.email, b.email);
try testing.expectEqual(a.timestamp, b.timestamp);
try testing.expectEqual(a.timezone_offset_minutes, b.timezone_offset_minutes);
}
try testing.expectEqualSlices(u8, &want.tree_digest, &got.tree_digest);
try testing.expectEqualSlices(u8, &want.provenance_digest, &got.provenance_digest);
try testing.expectEqual(want.decision, got.decision);
try testing.expectEqual(want.reason, got.reason);
for (want.candidates, got.candidates) |a, b| {
const x = a orelse {
try testing.expect(b == null);
continue;
};
const y = b.?;
try testing.expectEqualStrings(x.path, y.path);
try testing.expectEqualStrings(x.name, y.name);
if (x.oid) |oid| try testing.expectEqualStrings(oid, y.oid.?) else try testing.expect(y.oid == null);
}
}
const test_key: Key = "witness-test-key".*;
fn spillFixture(gpa: std.mem.Allocator, commits: []const WitnessCommit, key: Key) ![]u8 {
var out: std.Io.Writer.Allocating = .init(gpa);
defer out.deinit();
var writer: Writer = .{ .gpa = gpa, .out = &out.writer, .key = key };
defer writer.deinit();
for (commits) |*commit| try writer.add(commit);
return out.toOwnedSlice();
}
/// Reads every record of `bytes` through a file reader whose buffer is
/// `buffer_len` bytes, so records straddle refills at every offset.
fn readSpill(bytes: []const u8, count: u64, key: *const Key, buffer_len: usize, sink: ?[]const WitnessCommit) Error!void {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const file = tmp.dir.createFile(io, "spill", .{ .read = true }) catch return error.ReadFailed;
defer file.close(io);
file.writePositionalAll(io, bytes, 0) catch return error.ReadFailed;
var buffer: [64]u8 = undefined;
var file_reader = file.reader(io, buffer[0..buffer_len]);
var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
defer arena_state.deinit();
var reader: Reader = .{ .in = &file_reader.interface, .key = key, .count = count };
var at: usize = 0;
while (try reader.next(arena_state.allocator())) |commit| : (at += 1) {
if (sink) |want| expectSameCommit(want[at], commit) catch return error.Corrupt;
}
if (at != count) return error.Corrupt;
}
test "witness spill round-trips every field through any read buffer" {
const commits = fixtureCommits();
const bytes = try spillFixture(testing.allocator, &commits, test_key);
defer testing.allocator.free(bytes);
for ([_]usize{ 1, 3, 7, 16, 64 }) |buffer_len| {
try readSpill(bytes, commits.len, &test_key, buffer_len, &commits);
}
}
test "witness spill refuses every flipped byte, truncation and extension" {
const commits = fixtureCommits();
const bytes = try spillFixture(testing.allocator, &commits, test_key);
defer testing.allocator.free(bytes);
const copy = try testing.allocator.dupe(u8, bytes);
defer testing.allocator.free(copy);
for (0..copy.len) |at| {
copy[at] ^= 0x01;
defer copy[at] ^= 0x01;
try testing.expectError(error.Corrupt, readSpill(copy, commits.len, &test_key, 5, null));
}
for (0..bytes.len) |len| {
try testing.expectError(error.Corrupt, readSpill(bytes[0..len], commits.len, &test_key, 5, null));
}
const longer = try std.mem.concat(testing.allocator, u8, &.{ bytes, "\x00" });
defer testing.allocator.free(longer);
try testing.expectError(error.Corrupt, readSpill(longer, commits.len, &test_key, 5, null));
}
test "witness spill refuses reordered records and another run's key" {
const commits = fixtureCommits();
const swapped_commits = [_]WitnessCommit{ commits[1], commits[0], commits[2] };
const bytes = try spillFixture(testing.allocator, &commits, test_key);
defer testing.allocator.free(bytes);
const reordered = try spillFixture(testing.allocator, &swapped_commits, test_key);
defer testing.allocator.free(reordered);
// The records of `reordered`, each moved to the other's position: every
// one is a genuine record of this key, just not at the index it claims.
const first_len = 4 + std.mem.readInt(u32, reordered[0..4], .little) + Mac.mac_length;
const second_len = 4 + std.mem.readInt(u32, reordered[first_len..][0..4], .little) + Mac.mac_length;
const moved = try std.mem.concat(testing.allocator, u8, &.{
reordered[first_len..][0..second_len],
reordered[0..first_len],
reordered[first_len + second_len ..],
});
defer testing.allocator.free(moved);
try testing.expectError(error.Corrupt, readSpill(moved, commits.len, &test_key, 64, null));
const other_key: Key = "another-run-key!".*;
try testing.expectError(error.Corrupt, readSpill(bytes, commits.len, &other_key, 64, null));
}