rhdl_dsig_scalable_core/

cache_bank.rs

//! One bank of a slice's key cache: 34,816 rows of one 18-byte chain node.
//!
//! # The problem: keys are made long before they are spent
//!
//! The [key factory](crate::slice_factory) finishes one one-time key every 68
//! clocks. A key may not sign anything until its *batch certificate* (the
//! Ed25519 signature over the batch's Merkle root) comes back from the shared
//! [cert unit](crate::cert_unit), and that takes many batches' worth of time.
//! Until then the key has to wait somewhere on chip. That waiting room is the
//! key cache.
//!
//! What waits is the part of the key a signature reveals. W-OTS+ with w = 4
//! (the one-time signature scheme DSig uses) has 68 hash *chains* per key. A
//! signature reveals one *node* of each chain: which node depends on the
//! message digit (0, 1, 2 or 3) for that chain. So the cache stores four
//! nodes per chain ("positions" 0 to 3), each one 18-byte hash value
//! ([`ELEMENT_BYTES`]).
//!
//! # The decision: four banks, one per position
//!
//! The factory produces all four positions of a chain in the same clock. If
//! they all went into one memory, that memory would need four write ports.
//! Instead a slice has four banks, one per position. Each bank gets one write
//! per chain, and each bank has the identical row layout. When the signer
//! reads a chain, it presents the same row address to all four banks and keeps
//! the node whose position matches the digit. This module is one such bank;
//! [`Slice`](crate::slice::Slice) builds four of them.
//!
//! ```text
//!   key cache of one slice (4 banks; this file is one of them)
//!
//!   row                bank0 (pos 0)  bank1 (pos 1)  bank2 (pos 2)  bank3 (pos 3)
//!   0                  slot 0 ch 0    slot 0 ch 0    slot 0 ch 0    slot 0 ch 0
//!   1                  slot 0 ch 1    slot 0 ch 1    ...            ...
//!   ...
//!   67                 slot 0 ch 67
//!   68                 slot 1 ch 0         row  = slot × 68 + chain
//!   ...                                    slot = key number mod 512
//!   34,815             slot 511 ch 67      cell = one 18-byte node
//! ```
//!
//! # The power-of-two problem
//!
//! A slice caches 512 keys × 68 chains, one bank per chain position. RHDL's
//! [`SyncBRAM`] always holds a power-of-two number of rows, and rounding
//! 34,816 up to 65,536 would almost double the UltraRAM. So a bank is built from
//! two `SyncBRAM`s whose sizes add up exactly:
//!
//! ```text
//!                  row < 32,768 ──▶ low  : SyncBRAM<[b8; 18], 15>  (32,768 rows)
//!   row (16 bits) ─┤                                                         ├─▶ mux ─▶ node
//!                  row ≥ 32,768 ──▶ high : SyncBRAM<[b8; 18], 11>  ( 2,048 rows)
//!                                    which half was read ─▶ DFF ────────────┘
//!                                                           (then one output register)
//! ```
//!
//! Address bit 15 picks the half: 32,768 is `0x8000`, so every row with bit 15
//! set lives in `high`. The low 15 bits (for `low`) or the low 11 bits (for
//! `high`) address the row inside the half. Rows 34,816 and up would also land
//! in `high`, but they are never addressed.
//!
//! # The timing story
//!
//! Each half's 32,768 rows span a cascade of several UltraRAMs. A read that
//! ripples through that cascade and straight into logic took 5.3 ns in the
//! first Vivado run (the slice's critical path), more than a 205 MHz cycle. So
//! each half's output passes through [`READ_PIPE`] more registers *before* the
//! half-select mux, where Vivado folds them into the UltraRAM output and
//! cascade registers.
//!
//! Folding is also how the second run went wrong. In build v5 the pipe
//! registers had a reset, which UltraRAM cannot absorb, so one of them
//! stayed in the fabric. Build v6 made them reset-free
//! ([`DFF::resetless`]); Vivado then moved *both* into the 8-deep cascade,
//! and the last UltraRAMs' unregistered output fed the mux, the signer's
//! control and its packer across an SLR boundary: the worst path of v6
//! (-0.916 ns, 795 of its 2,000 worst paths). So the mux result now goes
//! through one more register, `out`, which Vivado cannot fold into the RAM
//! (a LUT sits in front of it). Data appears [`CACHE_READ_LATENCY`] cycles
//! after its address. Reading and writing the same row in one cycle returns the *old*
//! contents (read-before-write).
//!
//! ```text
//!   cycle 0   read address on the bank's input port
//!   cycle 1   `inputs` register holds it and drives both RAM addresses
//!   cycle 2   RAM read register holds the node      read_high[0] = bit 15
//!   cycle 3   low_pipe[0] / high_pipe[0]            read_high[1]
//!   cycle 4   low_pipe[1] / high_pipe[1]            read_high[2] ──▶ mux ──▶ out
//!   cycle 5   `out` drives the bank's output
//! ```
//!
//! The "which half" bit travels through as many registers as the data, so the
//! mux at the end always selects the half that *the same* address went to.
//! A new address can be presented every cycle; the nodes come out one per
//! cycle, in order, five cycles later.
//!
//! Rows are `slot × 68 + chain` ([`cache_address_kernel`]); rows at or beyond
//! [`CACHE_ROWS`] are never addressed.
//!
//! Both halves are `SyncBRAM`s marked [`RamStyle::Ultra`] (a vendored
//! rhdl-fpga option that emits `ram_style = "ultra"`). Without it, Vivado put
//! each bank in ~136 block RAMs spread over the die, and the address and
//! write-enable fan-out missed 205 MHz by 2.2 ns. The bank also registers its
//! incoming address, data and write enable once, next to the RAMs.
//!
//! # Neighbors
//!
//! * Writes come from the [factory](crate::slice_factory): its `cache_write`
//!   output is turned into a RAM port by
//!   [`bank_port_kernel`](crate::slice::bank_port_kernel) in [`crate::slice`].
//! * Reads come from the [signer](crate::slice_signer), which knows
//!   [`CACHE_READ_LATENCY`] and carries a token alongside each read so it
//!   knows what the returning node is for.
//! * A slot is overwritten only after its old key was burned; that rule is
//!   enforced by the slice's admission limit
//!   ([`ADMIT_LIMIT`](crate::slice::ADMIT_LIMIT)), not by the bank. The bank
//!   itself is plain storage.
//!
//! [`cache_address_kernel`]: crate::slice_factory::cache_address_kernel

use crate::ELEMENT_BYTES;
use crate::slice_factory::{CACHE_ADDRESS_BITS, CACHE_ROWS};
use rhdl::prelude::*;
use rhdl_fpga::core::{
    dff::DFF,
    ram::synchronous::{In as RamIn, RamStyle, SyncBRAM, Write as RamWrite},
};

/// Extra output registers after each RAM read (see the module docs).
///
/// Two registers give Vivado room to absorb the UltraRAM cascade delay at
/// 205 MHz. Changing this changes [`CACHE_READ_LATENCY`], which the signer
/// follows automatically.
pub const READ_PIPE: usize = 2;
/// Cycles from presenting a read address to its node on the output: one
/// input register, the RAM's own read register, [`READ_PIPE`], then the
/// output register after the half-select mux.
///
/// With `READ_PIPE = 2` this is 5 cycles. The
/// [signer](crate::slice_signer) sizes its in-flight read tokens by it.
pub const CACHE_READ_LATENCY: usize = 3 + READ_PIPE;

/// Registers from the RAM read to the output (RAM register + [`READ_PIPE`]).
///
/// This is the length of the `read_high` delay line, so the "which half" bit
/// arrives at the mux in the same cycle as its data.
const RAM_TO_OUTPUT: usize = 1 + READ_PIPE;
/// Index of the last "which half" register (the one that drives the mux).
const LAST: usize = RAM_TO_OUTPUT - 1;
/// Index of the last data register in `low_pipe` / `high_pipe` (the one the
/// mux reads).
const TAIL: usize = READ_PIPE - 1;

/// Rows in the low half: 2^15 = 32,768 (rows `0..32,768`).
pub const LOW_ROWS: usize = 1 << 15;
/// Rows in the high half: 2^11 = 2,048 (rows `32,768..34,816`).
pub const HIGH_ROWS: usize = 1 << 11;

// The two halves must hold exactly the bank's rows, no more and no less.
const _: () = assert!(LOW_ROWS + HIGH_ROWS == CACHE_ROWS);
// The kernel picks the half with bit 15 of a 16-bit address.
const _: () = assert!(CACHE_ADDRESS_BITS == 16);

/// One cache bank. Ports match `SyncBRAM<[b8; 18], 16>`.
///
/// To its user it looks like a single 65,536-row synchronous RAM with one
/// read port and one write port (only the first 34,816 rows are real), with a
/// read latency of [`CACHE_READ_LATENCY`] instead of 1.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct CacheBank {
    /// Address, data and write enable, registered next to the RAMs.
    inputs: DFF<RamIn<[b8; ELEMENT_BYTES], 16>>,
    /// Rows `0..32,768`, addressed by the low 15 address bits. UltraRAM.
    low: SyncBRAM<[b8; ELEMENT_BYTES], 15>,
    /// Rows `32,768..34,816`, addressed by the low 11 address bits. UltraRAM.
    high: SyncBRAM<[b8; ELEMENT_BYTES], 11>,
    /// [`READ_PIPE`] registers behind the low half's read output.
    low_pipe: [DFF<[b8; ELEMENT_BYTES]>; READ_PIPE],
    /// [`READ_PIPE`] registers behind the high half's read output.
    high_pipe: [DFF<[b8; ELEMENT_BYTES]>; READ_PIPE],
    /// Delay line for "this read went to the high half", one entry per data
    /// register after the RAM, so it reaches the mux with its data.
    read_high: [DFF<bool>; RAM_TO_OUTPUT],
    /// The selected node, registered after the mux (see the module docs).
    out: DFF<[b8; ELEMENT_BYTES]>,
}

impl Default for CacheBank {
    /// Both halves in UltraRAM, no write pending, data registers don't-care.
    ///
    /// The RAMs start with unknown contents; UltraRAM cannot be preloaded,
    /// and nothing reads a row before the factory has written it.
    fn default() -> Self {
        Self {
            // No write enabled and address 0 at power-up.
            inputs: DFF::new(RamIn::<[b8; ELEMENT_BYTES], 16> {
                read_addr: b16(0),
                write: RamWrite::<[b8; ELEMENT_BYTES], 16> {
                    addr: b16(0),
                    value: [b8(0); ELEMENT_BYTES],
                    enable: false,
                },
            }),
            // `RamStyle::Ultra` asks Vivado for UltraRAM (see module docs).
            low: SyncBRAM::default().with_style(RamStyle::Ultra),
            high: SyncBRAM::default().with_style(RamStyle::Ultra),
            // Data pipes need no reset: their contents are ignored until a
            // real read flows through.
            low_pipe: core::array::from_fn(|_| DFF::resetless()),
            high_pipe: core::array::from_fn(|_| DFF::resetless()),
            read_high: core::array::from_fn(|_| DFF::new(false)),
            out: DFF::resetless(),
        }
    }
}

/// Input: one read address plus one optional write per cycle. Output: the
/// node read [`CACHE_READ_LATENCY`] cycles earlier.
impl SynchronousIO for CacheBank {
    type I = RamIn<[b8; ELEMENT_BYTES], 16>;
    type O = [b8; ELEMENT_BYTES];
    type Kernel = cache_bank_kernel;
}

/// Route each row to its half; delay both halves' data and the "which half"
/// bit equally; select at the end.
///
/// * `input`: this cycle's read address and optional write (16-bit rows,
///   18-byte value). It is only registered here; it takes effect next cycle.
/// * `q`: the current register and RAM outputs.
/// * Returns the 18-byte node for the address presented
///   [`CACHE_READ_LATENCY`] cycles ago, and the next register/RAM inputs.
///
/// The write goes to exactly one half (bit 15 picks it), so a row is never
/// stored twice. Reads go to both halves at once; the mux discards the wrong
/// one at the end.
#[allow(clippy::needless_range_loop)]
#[kernel]
pub fn cache_bank_kernel(
    _clock_reset: ClockReset,
    input: RamIn<[b8; ELEMENT_BYTES], 16>,
    q: CacheBankQ,
) -> ([b8; ELEMENT_BYTES], CacheBankD) {
    // Everything below works on last cycle's (registered) inputs.
    let held = q.inputs;
    // Bit 15 of the read address: true when the row lives in the high half.
    let read_high = (held.read_addr & b16(0x8000)) != b16(0);
    // Same test for the write address: picks which half's write enable fires.
    let write_high = (held.write.addr & b16(0x8000)) != b16(0);
    // Both halves see the same (truncated) addresses and data; only the
    // write enable differs. `resize()` keeps the low 15 or 11 bits.
    let mut d = CacheBankD {
        low: RamIn::<[b8; ELEMENT_BYTES], 15> {
            read_addr: held.read_addr.resize(),
            write: RamWrite::<[b8; ELEMENT_BYTES], 15> {
                addr: held.write.addr.resize(),
                value: held.write.value,
                enable: held.write.enable && !write_high,
            },
        },
        high: RamIn::<[b8; ELEMENT_BYTES], 11> {
            read_addr: held.read_addr.resize(),
            write: RamWrite::<[b8; ELEMENT_BYTES], 11> {
                addr: held.write.addr.resize(),
                value: held.write.value,
                enable: held.write.enable && write_high,
            },
        },
        // Register this cycle's request for use next cycle.
        inputs: input,
        // Placeholders; the pipe stages are filled in just below.
        low_pipe: q.low_pipe,
        high_pipe: q.high_pipe,
        read_high: q.read_high,
        out: q.out,
    };
    // Shift: RAM output enters stage 0; stage k feeds stage k + 1.
    d.low_pipe[0] = q.low;
    d.high_pipe[0] = q.high;
    for k in 1..READ_PIPE {
        d.low_pipe[k] = q.low_pipe[k - 1];
        d.high_pipe[k] = q.high_pipe[k - 1];
    }
    // The half-select bit enters its own delay line in step with the RAM read.
    d.read_high[0] = read_high;
    for k in 1..RAM_TO_OUTPUT {
        d.read_high[k] = q.read_high[k - 1];
    }
    // Final mux: the oldest half-select bit picks between the two oldest
    // data registers. Both belong to the same read. Its result is
    // registered once more before it leaves the bank.
    d.out = if q.read_high[LAST] {
        q.high_pipe[TAIL]
    } else {
        q.low_pipe[TAIL]
    };
    (q.out, d)
}

/// Simulation tests for the split and the read pipeline.
#[cfg(test)]
mod tests {
    use super::*;

    /// A recognizable test pattern for row `r` (each byte depends on `r` and
    /// the byte position), so a wrong row or a wrong half shows up at once.
    fn row(r: u128) -> [b8; ELEMENT_BYTES] {
        core::array::from_fn(|i| b8((r * 7 + i as u128 * 13) & 0xff))
    }

    /// Run one full clock (low then high edge) with read address `read` and
    /// an optional `(row, value)` write; returns the bank output after it.
    fn step(
        bank: &CacheBank,
        state: &mut <CacheBank as Synchronous>::S,
        read: u128,
        write: Option<(u128, [b8; ELEMENT_BYTES])>,
    ) -> [b8; ELEMENT_BYTES] {
        // With no write, present address 0 with the enable low.
        let (addr, value) = write.unwrap_or((0, [b8(0); ELEMENT_BYTES]));
        let input = RamIn::<[b8; ELEMENT_BYTES], 16> {
            read_addr: b16(read),
            write: RamWrite::<[b8; ELEMENT_BYTES], 16> {
                addr: b16(addr),
                value,
                enable: write.is_some(),
            },
        };
        bank.sim(clock_reset(clock(false), reset(false)), input, state);
        bank.sim(clock_reset(clock(true), reset(false)), input, state)
    }

    /// Present one read (and optional write), then idle until its data is out.
    fn read(
        bank: &CacheBank,
        state: &mut <CacheBank as Synchronous>::S,
        row: u128,
        write: Option<(u128, [b8; ELEMENT_BYTES])>,
    ) -> [b8; ELEMENT_BYTES] {
        let mut out = step(bank, state, row, write);
        // Idle cycles until the read has crossed the whole pipeline.
        for _ in 1..CACHE_READ_LATENCY {
            out = step(bank, state, 0, None);
        }
        out
    }

    /// Rows at both edges of the 32,768 split (and the last real row) read
    /// back correctly, singly and back to back, and same-cycle read/write is
    /// read-before-write.
    #[test]
    fn rows_on_both_sides_of_the_split_read_back_after_the_pipeline() {
        let bank = CacheBank::default();
        let mut state = bank.init();
        // First rows, last low row, first high rows, last real row.
        let rows = [0, 1, 32_767, 32_768, 32_769, 34_815];
        for &r in &rows {
            step(&bank, &mut state, 0, Some((r, row(r))));
        }
        for &r in &rows {
            assert_eq!(read(&bank, &mut state, r, None), row(r), "row {r}");
        }
        // Back-to-back reads stream one node per cycle, in order.
        let mut out = Vec::new();
        for (k, &r) in rows
            .iter()
            .chain([0_u128; CACHE_READ_LATENCY - 1].iter())
            .enumerate()
        {
            let o = step(&bank, &mut state, r, None);
            // Skip the outputs that predate the first read.
            if k + 1 >= CACHE_READ_LATENCY {
                out.push(o);
            }
        }
        assert_eq!(out, rows.map(row).to_vec());
        // Read-before-write: a same-cycle write is not visible to that read.
        let fresh = [b8(0xAA); ELEMENT_BYTES];
        assert_eq!(read(&bank, &mut state, 1, Some((1, fresh))), row(1));
        assert_eq!(read(&bank, &mut state, 1, None), fresh);
    }

    /// The generated Verilog asks for UltraRAM for both halves and does not
    /// try to preload them (UltraRAM has no initial contents).
    #[test]
    fn both_halves_lower_to_ultraram_without_initial_contents() -> Result<(), RHDLError> {
        let hdl = CacheBank::default()
            .descriptor("bank".into())?
            .hdl_unchecked()?
            .modules
            .pretty();
        assert_eq!(hdl.matches("ram_style = \"ultra\"").count(), 2, "{hdl}");
        // Registers have `initial` blocks for their reset values; the memories
        // must have no preloaded rows.
        assert!(!hdl.contains("mem[0] ="), "UltraRAM cannot be preloaded");
        Ok(())
    }
}