Skip to content
zit Artifact [2e6c342598]
Login

Artifact [2e6c342598]

Check-ins Using Download Hex

Artifact 2e6c3425989051ec826b0f1208fa9716808011e71c98ff0a5ae2e38de524caea:

//! Fuzz targets for `crc32.zig`: the differential property that the vendored
//! slicing-by-8 implementation is bit-identical to `std.hash.Crc32` for ANY byte
//! sequence under ANY chunk splitting.
//!
//! Why this surface earns a fuzz lane. The CRC value is frozen into four on-disk
//! formats (the log's file header, frame prefix, frame header and whole-frame
//! trailer; the repocache image; the bisect session; the undo journal), so a
//! divergence orphans existing files rather than degrading. Every other lane in
//! this tree round-trips WITHIN zit — it writes a checksum and reads the same
//! checksum back — so an implementation that is internally consistent but
//! numerically shifted passes all of them. Only a differential against an
//! outside oracle can see that class, and "for any bytes, under any splitting"
//! is a property statement, not an example: enumerated cases pick the split
//! points someone thought of, which is exactly the bug class a resume error
//! lives in.
//!
//! `std.hash.Crc32` is the oracle rather than the thing under test. It is the
//! implementation whose output the formats were defined by.

const std = @import("std");
const crc32 = @import("zit").crc32;

/// The largest buffer a round builds. Comfortably past two 8-byte folds plus a
/// tail, and past the 4096-byte chunk the store's scan actually uses, so a
/// round can straddle both loop boundaries and the real chunk size.
const max_len: usize = 9000;

/// Bit-identical to `std.hash.Crc32` one-shot, over random bytes at random
/// lengths. Catches a wrong table, a wrong tail, a wrong init or final xor.
///
/// Lengths are drawn to over-sample the boundaries rather than uniformly: the
/// 0..15 range (where the fold loop runs zero or one times and the tail carries
/// everything) is where an off-by-one lives, and a uniform draw over 0..9000
/// would visit it about one round in six hundred.
pub fn oneShot(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var buf: [max_len]u8 = undefined;
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        const len: usize = switch (rand.uintLessThan(u8, 4)) {
            // Boundary classes, deliberately weighted to 3/4 of all rounds.
            0 => rand.uintLessThan(usize, 16), // 0..15: fold runs 0 or 1 times
            1 => 8 * (1 + rand.uintLessThan(usize, 8)), // exact fold multiples
            2 => 4096 + rand.uintLessThan(usize, 9) -| 4, // around the scan chunk
            else => rand.uintLessThan(usize, max_len + 1),
        };
        // Asserted, not clamped. A clamp turns a future out-of-range length
        // class into a silent one: every draw would collapse to exactly
        // `max_len`, so the boundary the new class was added to reach would
        // never be tested and every round would still pass.
        std.debug.assert(len <= max_len);
        const bytes = buf[0..len];
        for (bytes) |*b| b.* = rand.int(u8);

        try std.testing.expectEqual(std.hash.Crc32.hash(bytes), crc32.Crc32.hash(bytes));
    }
}

/// Bit-identical under arbitrary streaming splits: the register after every
/// `update` must equal std's register after the same prefix, because
/// `logstore.zig`'s `scanOneFrame` and `readFrameAt` both resume one CRC across
/// separately-read buffers. Agreement on `final()` alone is not the contract.
///
/// This lane owns the SPLIT-POINT axis: chunks are drawn small (mostly <= 64
/// bytes) precisely because a dense population of boundaries is what a resume
/// bug hides behind — a chunk of length 0, a chunk of 1 straddling a fold, a
/// fold-aligned run followed by a 7-byte remainder. One round in eight instead
/// draws from the whole remainder, so a single large update is reachable here
/// too rather than being purely someone else's problem.
///
/// It does NOT own the large-single-update axis. A bug triggered only by a long
/// `update` is caught by `oneShot` (up to `max_len` in one call) and by
/// `scanChunking` (4096-byte updates), not reliably by this lane — measured, by
/// injecting a fault conditional on `bytes.len > 100`: the other two lanes went
/// red and this one stayed green.
pub fn streamingSplits(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var buf: [max_len]u8 = undefined;
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        const len = rand.uintLessThan(usize, max_len + 1);
        const bytes = buf[0..len];
        for (bytes) |*b| b.* = rand.int(u8);

        var ours = crc32.Crc32.init();
        var theirs = std.hash.Crc32.init();
        var pos: usize = 0;
        // Bounded: `pos` is non-decreasing and the loop exits at `len`; a
        // zero-length chunk is deliberately reachable but cannot spin, because
        // the guard below forces progress once one has been fed.
        var fed_empty = false;
        while (pos < len) {
            const remaining = len - pos;
            // Mostly small (the split-point bias this lane exists for); one
            // round in eight the whole remainder is in play, so a single large
            // update is reachable without giving up the dense boundaries.
            const cap = if (rand.uintLessThan(u8, 8) == 0) remaining else @min(remaining, 64);
            var take = rand.uintLessThan(usize, cap + 1);
            if (take == 0) {
                if (fed_empty) take = 1 else fed_empty = true;
            } else {
                fed_empty = false;
            }
            ours.update(bytes[pos .. pos + take]);
            theirs.update(bytes[pos .. pos + take]);
            // The register must agree at EVERY boundary, not just at the end —
            // this is the assertion that a resume bug cannot hide from.
            try std.testing.expectEqual(theirs.final(), ours.final());
            pos += take;
        }
        try std.testing.expectEqual(theirs.final(), ours.final());
    }
}

/// The store's real shape: a header seed of 22 + hash_len bytes (never a
/// multiple of 8 for any hash zit uses) followed by 4096-byte payload chunks
/// with an arbitrary remainder — exactly `scanOneFrame`'s update sequence. A
/// generic splitting fuzzer reaches this eventually; naming it means a
/// regression on the hot path fails here rather than probabilistically.
pub fn scanChunking(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        const hash_len: usize = if (rand.boolean()) 20 else 32;
        const seed_len = 22 + hash_len;
        const payload_len = rand.uintLessThan(usize, 3 * 4096 + 1);

        const bytes = try gpa.alloc(u8, seed_len + payload_len);
        defer gpa.free(bytes);
        for (bytes) |*b| b.* = rand.int(u8);

        var ours = crc32.Crc32.init();
        var theirs = std.hash.Crc32.init();
        ours.update(bytes[0..seed_len]);
        theirs.update(bytes[0..seed_len]);
        var pos = seed_len;
        while (pos < bytes.len) {
            const take = @min(bytes.len - pos, 4096);
            ours.update(bytes[pos .. pos + take]);
            theirs.update(bytes[pos .. pos + take]);
            pos += take;
        }
        try std.testing.expectEqual(theirs.final(), ours.final());
    }
}

// ---------------------------------------------------------------------------
// Fixed-seed smoke: the same differential properties under `zig build test`
// (reached through dst.zig's aggregation), at a round count sized for the
// inner loop rather than for a sweep.
//
// Without this, all three targets above run only under an explicit
// `zig build fuzz -- <target>`, which no gate invokes — the exact hazard
// `fuzz_tests.zig`'s registration pin names, one level down: the target is
// registered, so the pin is satisfied, and still nothing ever runs it.
// ---------------------------------------------------------------------------

test "crc32 fuzz: bit-identity to std holds on random input and random splits (smoke)" {
    const gpa = std.testing.allocator;
    try oneShot(gpa, 0x5C21_0E4B, 512);
    try streamingSplits(gpa, 0x1D93_77A2, 512);
    try scanChunking(gpa, 0x6BE4_2F08, 256);
}