path: root/src/esp32p4/input_rescue.zig

//! Keystrokes rescued from the receive FIFO while the transmitter is busy.
//!
//! THE BUG THIS EXISTS FOR. The firmware's loop is read, apply, render, write, and the write blocks
//! while the transmit FIFO is full - real backpressure, because dropping half an escape sequence
//! would leave the host terminal in the wrong colour for the rest of the session. But nothing
//! drained the RECEIVE FIFO during that wait, and the FIFO is 128 bytes (the toolchain package's
//! `src/hal/uart.zig:52`). A frame of 240 bytes is 21 ms of wire at 115200, and 21 ms of a host
//! sending at line rate is ~240 bytes, so everything past the 128th was silently gone.
//!
//! Measured on the die before the fix, typing a burst in one host write and counting what the editor
//! actually held: 128 bytes arrived intact, 200 bytes lost 88, 300 bytes lost all 300. From a
//! keyboard that is a keystroke that never lands, and it looks like a stuck key - the screen is
//! behind what was typed, and typing more appears to fix it because a later frame repaints the cells
//! the lost keystrokes would have changed.
//!
//! WHY THE POLICY LIVES HERE and not in `uart.zig`: the interesting part is a decision - drain the
//! receiver while spinning on the transmitter, and what to do when even that overflows - and the
//! decision is worth testing. `uart.zig` cannot be tested at all without the chip, because every
//! line of it is an MMIO access. `pump` takes the port as `anytype`, so the same code runs against
//! the real UART on the board and against a fake with a two-byte FIFO on the host.
//!
//! WHY IT IS IN THIS REPOSITORY. It was written in the toolchain repository, next to the UART it
//! spins on, and it moved here because every number in it is the EDITOR's. 4 KiB is sized against
//! the ~1.4 KB full repaint `src/esp32p4.zig` emits; "drop the newest, so what survives is a PREFIX of
//! what was typed" is a statement about documents rather than about UARTs, and it is the editor that
//! would otherwise appear to invent input. A policy whose every constant comes from one application
//! belongs beside that application.
//!
//! It expects NOTHING from the toolchain package - no module, no register, no target. `std` is the
//! whole import list, which is what makes the host tests at the bottom possible and what lets the
//! same source compile for riscv32-freestanding and for the host unchanged.
//!
//! ONE COPY, TWO BUILDS. This file is the only copy; the toolchain repository's is gone. Its build
//! reads this tree across a sibling-relative seam, and names this path twice: once as the
//! `input_rescue` module of `-Dpardes`'s application (`05-zig-p4/build.zig:230-231`, whose root is
//! `../02-pardes-code/src/esp32p4/app.zig` by the `-Dapp` default at `:168-169`) and once as the
//! same-named module of `zig build selftest`'s on-die root (`:437-438`). Both spell
//! `../02-pardes-code/src/esp32p4/input_rescue.zig`, so there is nothing to keep in step.
//!
//! Host checks run under `zig build unit-test` here. In `../05-zig-p4`,
//! `zig build selftest` flashes and runs the on-die checks against UART0.

const std = @import("std");

/// Capacity, sized for the worst frame this editor emits.
///
/// A full repaint is ~1.4 KB, which is 121 ms of wire at 115200, and 121 ms of a host pasting at
/// line rate is ~1.4 KB of input. 4 KiB is that with headroom, a power of two so the wrap is a mask
/// rather than a division, and nothing at all against the board's RAM.
pub const capacity = 4096;

/// A byte queue that drops the NEWEST byte when full.
///
/// Dropping the newest rather than the oldest is deliberate: what survives is then a PREFIX of what
/// was typed. An editor that loses the end of a paste has done something a person can see and
/// correct; one that silently reorders keystrokes, or keeps the tail and discards the head, has
/// corrupted the document in a way that looks like the editor inventing input.
pub const Ring = struct {
    buf: [capacity]u8 = undefined,
    head: usize = 0,
    len: usize = 0,
    /// Bytes lost because even this overflowed. Nonzero means input was dropped; it is the honest
    /// version of the bug rather than a cure for it.
    dropped: u32 = 0,

    const mask = capacity - 1;

    comptime {
        std.debug.assert(capacity & mask == 0);
    }

    pub fn push(r: *Ring, b: u8) void {
        if (r.len == capacity) {
            r.dropped +%= 1;
            return;
        }
        r.buf[(r.head + r.len) & mask] = b;
        r.len += 1;
    }

    /// Move as much as fits into `out`, oldest first. Returns the count.
    pub fn pop(r: *Ring, out: []u8) usize {
        const n = @min(out.len, r.len);
        for (out[0..n]) |*slot| {
            slot.* = r.buf[r.head];
            r.head = (r.head + 1) & mask;
        }
        r.len -= n;
        return n;
    }

    pub fn clear(r: *Ring) void {
        r.head = 0;
        r.len = 0;
    }
};

/// Drain everything the port has received into `ring`, without waiting.
pub fn rescue(port: anytype, ring: *Ring) void {
    var waiting = port.rxCount();
    while (waiting > 0) : (waiting -= 1) ring.push(port.popByte());
}

/// Push `bytes` through `port`, rescuing input whenever the transmitter has no room. Returns the
/// number of bytes abandoned because the transmitter stopped making progress altogether.
///
/// The spin bound is why this returns a count rather than blocking forever: a UART whose core clock
/// has been gated never makes progress, and on a board with no debugger an infinite spin is
/// indistinguishable from a crash. A bounded wait turns that into visibly dropped output plus a
/// counter, which is a diagnosis instead of a mystery.
pub fn pump(port: anytype, ring: *Ring, bytes: []const u8, spin_limit: u32) u32 {
    var rest = bytes;
    while (rest.len > 0) {
        // One status read per burst, not per byte: reading `txFree` once and pushing that many cuts
        // the status reads by up to the FIFO depth.
        var room = port.txFree();
        var spins: u32 = 0;
        while (room == 0) {
            // THE FIX. Every iteration of this wait is time the receiver is filling up, and this is
            // the only place that can empty it.
            rescue(port, ring);
            spins += 1;
            if (spins > spin_limit) return @intCast(rest.len);
            room = port.txFree();
        }
        const n = @min(room, rest.len);
        for (rest[0..n]) |b| port.pushByte(b);
        rest = rest[n..];
    }
    return 0;
}

// ------------------------------------------------------------------------------------ host tests

test "the ring hands bytes back in order" {
    var r: Ring = .{};
    for ("hello") |b| r.push(b);
    var out: [8]u8 = undefined;
    try std.testing.expectEqual(@as(usize, 5), r.pop(&out));
    try std.testing.expectEqualStrings("hello", out[0..5]);
    try std.testing.expectEqual(@as(usize, 0), r.pop(&out));
}

test "the ring wraps without reordering" {
    var r: Ring = .{};
    var out: [capacity]u8 = undefined;
    // Push and pop most of the buffer so head sits near the end, then straddle the wrap.
    for (0..capacity - 3) |i| r.push(@intCast(i & 0xff));
    _ = r.pop(out[0 .. capacity - 3]);
    for ("straddle") |b| r.push(b);
    const n = r.pop(&out);
    try std.testing.expectEqualStrings("straddle", out[0..n]);
}

test "a full ring drops the newest and says so" {
    var r: Ring = .{};
    for (0..capacity) |i| r.push(@intCast(i & 0xff));
    try std.testing.expectEqual(@as(u32, 0), r.dropped);
    r.push('!');
    r.push('!');
    try std.testing.expectEqual(@as(u32, 2), r.dropped);
    // The head is intact: what survived is a prefix of what arrived.
    var out: [4]u8 = undefined;
    _ = r.pop(&out);
    try std.testing.expectEqual(@as(u8, 0), out[0]);
    try std.testing.expectEqual(@as(u8, 1), out[1]);
}

/// A UART with a small transmit FIFO, a small RECEIVE FIFO, and a host that keeps typing into it.
///
/// The receive FIFO is the part that matters and it is modelled the way the hardware behaves: it has
/// a fixed depth, and a byte that arrives when it is full is *gone*. That is the whole bug.
///
/// Time advances on each transmitter status read, which is what `pump` does while it waits. The
/// transmitter frees a byte only every fourth tick while a typed byte lands on every one: the
/// transmitter therefore genuinely FILLS, which is the condition the bug needs. A fake whose FIFO
/// drains as fast as it fills never blocks, so `pump` never waits, so the rescue never runs and the
/// test proves nothing - the first version of this fake had exactly that flaw.
const FakePort = struct {
    tx_cap: u32,
    tx_used: u32 = 0,
    sent: std.ArrayList(u8) = .empty,
    gpa: std.mem.Allocator,

    incoming: []const u8,
    delivered: usize = 0,
    rx: [rx_depth]u8 = undefined,
    rx_head: usize = 0,
    rx_len: usize = 0,
    /// Bytes the wire delivered into a full receive FIFO. The hardware has no counter for this,
    /// which is exactly why the bug was invisible.
    lost: u32 = 0,

    ticks: u32 = 0,

    const rx_depth = 8;
    const tx_drain_every = 4;

    fn tick(p: *FakePort) void {
        p.ticks += 1;
        if (p.ticks % tx_drain_every == 0 and p.tx_used > 0) p.tx_used -= 1;
        if (p.delivered < p.incoming.len) {
            const b = p.incoming[p.delivered];
            p.delivered += 1;
            if (p.rx_len == rx_depth) {
                p.lost += 1;
            } else {
                p.rx[(p.rx_head + p.rx_len) % rx_depth] = b;
                p.rx_len += 1;
            }
        }
    }

    fn txFree(p: *FakePort) u32 {
        p.tick();
        return p.tx_cap - p.tx_used;
    }

    fn pushByte(p: *FakePort, b: u8) void {
        p.sent.append(p.gpa, b) catch unreachable;
        p.tx_used += 1;
    }

    fn rxCount(p: *FakePort) u32 {
        return @intCast(p.rx_len);
    }

    fn popByte(p: *FakePort) u8 {
        const b = p.rx[p.rx_head];
        p.rx_head = (p.rx_head + 1) % rx_depth;
        p.rx_len -= 1;
        return b;
    }
};

test "a long transmit does not lose the input that arrives during it" {
    // THE REGRESSION. Delete the `rescue` call inside `pump`'s wait and this fails: the receive FIFO
    // is eight bytes deep, the typing below is far longer than that, and every byte that arrives
    // into a full FIFO is gone with nothing to record it. That is the die's 88-of-200 in miniature.
    const typed = "the quick brown fox jumps over the lazy dog, twice over, and then some more";
    var port: FakePort = .{ .tx_cap = 2, .incoming = typed, .gpa = std.testing.allocator };
    defer port.sent.deinit(std.testing.allocator);
    var ring: Ring = .{};

    const frame = "\x1b[1;1H" ++ "x" ** 400;
    try std.testing.expectEqual(@as(u32, 0), pump(&port, &ring, frame, 1_000_000));

    // Every output byte went out, in order.
    try std.testing.expectEqualStrings(frame, port.sent.items);
    // Nothing the wire delivered was dropped, by the FIFO or by the ring.
    try std.testing.expectEqual(@as(u32, 0), port.lost);
    try std.testing.expectEqual(@as(u32, 0), ring.dropped);
    // And what was rescued, plus whatever is still sitting in the FIFO, is exactly what was typed -
    // in order, which is the other half of the contract.
    var got: [capacity]u8 = undefined;
    var n = ring.pop(&got);
    while (port.rxCount() > 0) : (n += 1) got[n] = port.popByte();
    try std.testing.expectEqualStrings(typed[0..port.delivered], got[0..n]);
    try std.testing.expect(port.delivered == typed.len);
}

test "a transmitter that never drains gives up and reports what it abandoned" {
    var port: FakePort = .{ .tx_cap = 0, .incoming = "", .gpa = std.testing.allocator };
    defer port.sent.deinit(std.testing.allocator);
    var ring: Ring = .{};
    // tx_cap 0 means txFree is always 0, so no byte can ever go out.
    try std.testing.expectEqual(@as(u32, 5), pump(&port, &ring, "abcde", 32));
    try std.testing.expectEqual(@as(usize, 0), port.sent.items.len);
}