diff options
Diffstat (limited to 'src/pardes/input_rescue.zig')
| -rw-r--r-- | src/pardes/input_rescue.zig | 248 |
1 files changed, 248 insertions, 0 deletions
diff --git a/src/pardes/input_rescue.zig b/src/pardes/input_rescue.zig new file mode 100644 index 0000000..ea242b2 --- /dev/null +++ b/src/pardes/input_rescue.zig @@ -0,0 +1,248 @@ +//! 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 (`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 in `zig build test`. + +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); +} |