rsemu 0.0.3

//! virtio-rng: an entropy source behind the MMIO transport.
//!
//! # Source
//!
//! *Virtual I/O Device (VIRTIO) Version 1.2*, OASIS Standard, §5.4 ("Entropy
//! Device"): device ID 4, one virtqueue, no configuration space, no feature
//! bits. The driver offers write-only buffers; the device fills them and
//! reports how many bytes it wrote. That is the whole protocol.
//!
//! # The entropy is deterministic, and it says so
//!
//! rsemu's determinism rule (`ROADMAP.md` §0) says a machine run twice must
//! produce a bit-identical state hash, and `CLAUDE.md` adds that any
//! non-deterministic input crossing into the machine goes through the
//! record/replay seam or it is a bug. That seam does not exist yet, and reading
//! a host entropy source would be a wall-clock read by another name.
//!
//! So this device is a **seeded pseudo-random generator**: the same machine
//! file produces the same bytes every run. That is honest and useful — a guest
//! that blocks waiting for entropy stops blocking, which is the point of
//! attaching one at all — and it is *not* a security primitive. A guest that
//! needs unpredictable bytes must not get them from here, and the device tree
//! node says nothing to suggest otherwise.
//!
//! When the record/replay seam lands, a `source = "host"` property becomes the
//! obvious addition, with the drawn bytes logged against a virtual timestamp.
//!
//! # The generator
//!
//! SplitMix64, from Steele, Lea and Flood, *Fast Splittable Pseudorandom Number
//! Generators* (OOPSLA 2014) — a published algorithm, four lines long, with
//! good enough statistical properties for this and no claim to be more.

use alloc::vec::Vec;

use crate::core::error::Result;
use crate::core::state::{ChunkReader, ChunkWriter, Sink, Source};
use crate::core::sync::{LockRank, Mutex};

use super::queue::{Descriptor, Queue};
use super::{Backend, DEVICE_ID_ENTROPY};

/// How many bytes are generated per call before the buffer is flushed out.
const CHUNK: usize = 256;

/// SplitMix64's golden-ratio increment.
const GAMMA: u64 = 0x9e37_79b9_7f4a_7c15;

/// A deterministic entropy source.
#[derive(Debug)]
pub struct VirtioRng {
    seed: u64,
    state: Mutex<u64>,
}

impl VirtioRng {
    /// A generator started from `seed`.
    #[must_use]
    pub fn new(seed: u64) -> VirtioRng {
        VirtioRng {
            seed,
            state: Mutex::with_rank(LockRank::DEVICE, seed),
        }
    }

    /// The seed this device was built with.
    #[must_use]
    pub fn seed(&self) -> u64 {
        self.seed
    }

    /// The next 64 bits (Steele, Lea and Flood, §4).
    fn next(&self) -> u64 {
        let mut state = self.state.lock();
        *state = state.wrapping_add(GAMMA);
        let mut z = *state;
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
        z ^ (z >> 31)
    }

    /// Fill `dst` with generated bytes.
    pub fn fill(&self, dst: &mut [u8]) {
        for piece in dst.chunks_mut(8) {
            let word = self.next().to_le_bytes();
            piece.copy_from_slice(&word[..piece.len()]);
        }
    }
}

impl Backend for VirtioRng {
    fn device_id(&self) -> u32 {
        DEVICE_ID_ENTROPY
    }

    fn queue_count(&self) -> usize {
        // §5.4.2: exactly one, called `requestq`.
        1
    }

    fn features(&self) -> u64 {
        // §5.4.3: none are defined.
        0
    }

    fn config_read(&self, _offset: u64, dst: &mut [u8]) {
        // §5.4.4: there is no configuration space.
        dst.fill(0);
    }

    fn handle(&self, _queue: usize, q: &Queue<'_>, chain: &[Descriptor]) -> u32 {
        let want = Queue::writable_len(chain);
        if want == 0 {
            return 0;
        }
        let mut written = 0u64;
        let mut buf = alloc::vec![0u8; CHUNK];
        while written < want {
            let take = ((want - written) as usize).min(CHUNK);
            self.fill(&mut buf[..take]);
            match q.write_chain(chain, written, &buf[..take]) {
                Ok(0) | Err(_) => break,
                Ok(n) => written += n as u64,
            }
        }
        written as u32
    }

    fn reset(&self) {
        // Back to the seed, so a machine reset gives the same stream again —
        // which is what makes a reset-and-rerun reproducible.
        *self.state.lock() = self.seed;
    }

    fn save(&self, w: &mut ChunkWriter<'_>) -> Result<()> {
        // The generator's position is architectural: a guest that restores a
        // snapshot and draws again must get what it would have got.
        w.write_u64(*self.state.lock())
    }

    fn load(&self, r: &mut ChunkReader<'_>) -> Result<()> {
        *self.state.lock() = r.read_u64()?;
        Ok(())
    }
}

/// The bytes this generator produces from `seed`, for a test or a fixture.
#[must_use]
pub fn stream(seed: u64, len: usize) -> Vec<u8> {
    let rng = VirtioRng::new(seed);
    let mut out = alloc::vec![0u8; len];
    rng.fill(&mut out);
    out
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::core::space::{AddressSpace, MemAttrs, RamStore, Region, RequesterId};
    use crate::core::value::Width;
    use crate::dev::riscv::virtio::queue::{DESC_F_NEXT, DESC_F_WRITE, Layout};
    use alloc::sync::Arc;

    const DESC: u64 = 0x1000;
    const BUF: u64 = 0x5000;

    fn guest() -> (AddressSpace, Layout) {
        let space = AddressSpace::new("mem", 64);
        space
            .topology()
            .map(Region::ram("ram", Arc::new(RamStore::new(0x1_0000))), 0)
            .unwrap();
        (
            space,
            Layout {
                size: 8,
                desc: DESC,
                avail: 0x2000,
                used: 0x3000,
                ready: true,
            },
        )
    }

    fn descriptor(space: &AddressSpace, index: u64, addr: u64, len: u32, flags: u16, next: u16) {
        let at = DESC + index * 16;
        for (off, width, value) in [
            (0u64, Width::U64, addr),
            (8, Width::U32, u64::from(len)),
            (12, Width::U16, u64::from(flags)),
            (14, Width::U16, u64::from(next)),
        ] {
            space
                .write(at + off, width, value, MemAttrs::DEFAULT)
                .unwrap();
        }
    }

    #[test]
    fn the_same_seed_gives_the_same_bytes_every_run() {
        // The determinism claim, asserted rather than assumed.
        assert_eq!(stream(42, 64), stream(42, 64));
        assert_ne!(stream(42, 64), stream(43, 64));
        // And a partial word at the end is still filled.
        assert_eq!(stream(1, 13).len(), 13);
        assert_eq!(stream(1, 13)[..8], stream(1, 8)[..]);
    }

    #[test]
    fn a_writable_chain_is_filled_and_the_length_reported() {
        let (space, layout) = guest();
        descriptor(&space, 0, BUF, 32, DESC_F_WRITE, 0);
        let q = Queue::new(layout, &space, RequesterId(1));
        let chain = q.chain(0).unwrap();
        let rng = VirtioRng::new(7);
        assert_eq!(rng.handle(0, &q, &chain), 32);

        let expected = stream(7, 32);
        for (i, want) in expected.iter().enumerate() {
            let got = space
                .read(BUF + i as u64, Width::U8, MemAttrs::DEBUG)
                .unwrap() as u8;
            assert_eq!(got, *want, "byte {i}");
        }
    }

    #[test]
    fn a_chain_longer_than_one_generation_chunk_is_filled_end_to_end() {
        let (space, layout) = guest();
        let len = CHUNK as u32 + 40;
        descriptor(&space, 0, BUF, len, DESC_F_WRITE, 0);
        let q = Queue::new(layout, &space, RequesterId(1));
        let chain = q.chain(0).unwrap();
        assert_eq!(VirtioRng::new(3).handle(0, &q, &chain), len);
        // The stream continues across the chunk boundary rather than
        // restarting, which a naive loop gets wrong.
        let expected = stream(3, len as usize);
        for i in [0usize, CHUNK - 1, CHUNK, len as usize - 1] {
            let got = space
                .read(BUF + i as u64, Width::U8, MemAttrs::DEBUG)
                .unwrap() as u8;
            assert_eq!(got, expected[i], "byte {i}");
        }
    }

    #[test]
    fn a_chain_with_nothing_writable_produces_nothing() {
        let (space, layout) = guest();
        descriptor(&space, 0, BUF, 32, 0, 0);
        let q = Queue::new(layout, &space, RequesterId(1));
        let chain = q.chain(0).unwrap();
        assert_eq!(VirtioRng::new(1).handle(0, &q, &chain), 0);
    }

    #[test]
    fn a_reset_puts_the_stream_back_to_the_seed() {
        let rng = VirtioRng::new(9);
        let mut first = [0u8; 16];
        rng.fill(&mut first);
        rng.reset();
        let mut again = [0u8; 16];
        rng.fill(&mut again);
        assert_eq!(first, again);
    }

    #[test]
    fn a_snapshot_carries_the_position_and_not_just_the_seed() {
        use crate::core::state::{MachineShape, Migrations, StateReader, StateWriter};

        let saved = VirtioRng::new(5);
        let mut skip = [0u8; 24];
        saved.fill(&mut skip);

        let mut shape = MachineShape::new();
        shape.add_device("rng", "virtio.rng").unwrap();
        let mut w = StateWriter::new(shape);
        {
            let mut chunk = w.chunk("rng", "virtio.rng", 1).unwrap();
            saved.save(&mut chunk).unwrap();
        }
        let bytes = w.to_vec().unwrap();

        let restored = VirtioRng::new(5);
        let reader = StateReader::new(&bytes).unwrap();
        let chunk = reader
            .load("rng", "virtio.rng", 1, &Migrations::new())
            .unwrap();
        restored.load(&mut chunk.reader()).unwrap();

        let mut a = [0u8; 16];
        let mut b = [0u8; 16];
        saved.fill(&mut a);
        restored.fill(&mut b);
        assert_eq!(a, b, "the stream continues where the snapshot left it");
    }

    #[test]
    fn multi_descriptor_chains_are_filled_across_the_boundary() {
        let (space, layout) = guest();
        descriptor(&space, 0, BUF, 8, DESC_F_WRITE | DESC_F_NEXT, 1);
        descriptor(&space, 1, BUF + 0x100, 8, DESC_F_WRITE, 0);
        let q = Queue::new(layout, &space, RequesterId(1));
        let chain = q.chain(0).unwrap();
        assert_eq!(VirtioRng::new(11).handle(0, &q, &chain), 16);
        let expected = stream(11, 16);
        let first = space.read(BUF, Width::U64, MemAttrs::DEBUG).unwrap();
        let second = space
            .read(BUF + 0x100, Width::U64, MemAttrs::DEBUG)
            .unwrap();
        assert_eq!(first.to_le_bytes()[..], expected[..8]);
        assert_eq!(second.to_le_bytes()[..], expected[8..]);
    }
}