sv_sim_sim/state/

huge_mirror.rs

//! Windowed commits for huge (`> 65535`-bit) signals (lane `wide-commit`).
//!
//! A compiled process keeps a *shadow* of every huge signal it touches: the
//! PK image (`pk_words(N) = ceil(2N/64)` words, the val plane at bit 0 and the
//! unk plane at bit `N`) that `sv_rt_wide` selects/inserts into. Before this
//! module existed, each segment re-primed the shadow from the arena planes
//! (`O(N)`), and every write through the shadow was committed by converting
//! the whole image back to planes and diffing the whole value (`O(N)` again,
//! twice over), even for a one-bit write.
//!
//! The arena now keeps, per huge signal, one long-lived **mirror**: the PK
//! image itself, at a stable heap address, plus a *dirty window* `[lo, hi)` of
//! value bits the compiled code has written since the last commit.
//!
//! Invariant: **a valid mirror equals the planes outside its dirty window.**
//!
//! * [`huge_prime`] returns the mirror's image (what the shadow used to be).
//!   A valid mirror is returned as is (no copy); an invalid one -- or one the
//!   caller asked to rebuild after external code may have written the planes
//!   -- is rebuilt from the planes, `O(N)`, once.
//! * [`huge_mark`] widens the dirty window to cover bits the caller wrote to
//!   the image.
//! * [`huge_commit`] converts only the words the window covers back to
//!   planes, compares them with what the planes hold (the whole-value
//!   "did anything change" test, restricted to the only words that can have
//!   changed), stores them and reports the lsb transition for edge
//!   classification. A clean window is a no-op.
//! * Every other writer of the planes ([`super::write::write_slot`],
//!   `rollback::restore`) invalidates the mirrors it overlaps, so a stale
//!   image is never trusted. The commit's own plane stores bypass that hook.
//!
//! The windowed path replaces `commit_write_at` only when `commit_write_at`
//! would do nothing the window skips: no force filter for this cell, no
//! value-change record. Otherwise the whole image is committed through the
//! normal path (the pre-existing behaviour, `O(N)`).
//!
//! `SV_SIM_HUGE_VERIFY=1` makes every prime and every commit check the whole
//! mirror against the planes and abort on a divergence -- a missed `mark` or a
//! missed invalidation would otherwise lose a write silently.

use std::cell::{Cell, RefCell};
use std::collections::BTreeMap;

use sv_sim_abi::{Bit4, SimHandle, SlotId};

use super::accessor_impl::{resolve_foreign_slot, slot_location_for};
use super::instance::InstanceHandle;
use super::write::SlotLocation;
use super::{Arena, ChangeDelta, FourStateValue, SlotClass, StateCellId};

/// One huge signal's long-lived PK image and its dirty window.
struct HugeMirror {
    /// The signal's bit width `N`.
    width: u32,
    /// The PK image: `ceil(2N/64)` words plus two zero guard words (the word
    /// reader looks one word past the end for an unaligned tail).
    pk: Box<[u64]>,
    /// Whether the image reflects the planes outside the dirty window.
    valid: bool,
    /// The value bits `[dirty_lo, dirty_hi)` written since the last commit;
    /// empty when `dirty_lo >= dirty_hi`.
    dirty_lo: u32,
    dirty_hi: u32,
}

impl HugeMirror {
    fn new(width: u32) -> Self {
        let words = (2 * width as usize).div_ceil(64) + 2;
        HugeMirror {
            width,
            pk: vec![0u64; words].into_boxed_slice(),
            valid: false,
            dirty_lo: 0,
            dirty_hi: 0,
        }
    }

    fn clear_dirty(&mut self) {
        self.dirty_lo = 0;
        self.dirty_hi = 0;
    }

    fn dirty(&self) -> bool {
        self.dirty_lo < self.dirty_hi
    }

    fn plane_words(&self) -> usize {
        (self.width as usize).div_ceil(64)
    }
}

/// The arena's registry of huge-signal mirrors, keyed by the signal's absolute
/// wide-plane word offset.
pub(crate) struct HugeMirrors {
    map: RefCell<BTreeMap<u32, HugeMirror>>,
    /// `map.len()`, so the write hook's common case (no mirror at all) is one
    /// load.
    count: Cell<usize>,
    /// `SV_SIM_HUGE_VERIFY` was set when the arena was built: every prime and
    /// commit checks the whole mirror against the planes.
    verify: bool,
}

impl Default for HugeMirrors {
    fn default() -> Self {
        HugeMirrors {
            map: RefCell::default(),
            count: Cell::new(0),
            verify: std::env::var_os("SV_SIM_HUGE_VERIFY").is_some_and(|v| v != "0"),
        }
    }
}

impl HugeMirrors {
    /// Marks every mirror overlapping the wide-plane words
    /// `[start, start + words)` invalid: some writer other than the commit
    /// just changed them.
    pub(crate) fn invalidate_range(&self, start: usize, words: usize) {
        if self.count.get() == 0 || words == 0 {
            return;
        }
        let end = start + words;
        let mut map = self.map.borrow_mut();
        // Mirrors never overlap each other, so walking down from the last key
        // below `end`, the first one that ends at or before `start` ends the
        // overlap.
        for (&key, m) in map.range_mut(..end as u32).rev() {
            if key as usize + m.plane_words() <= start {
                break;
            }
            m.valid = false;
        }
    }

    /// Marks every mirror invalid (`rollback::restore` rewrites the planes
    /// wholesale).
    pub(crate) fn invalidate_all(&self) {
        if self.count.get() == 0 {
            return;
        }
        for m in self.map.borrow_mut().values_mut() {
            m.valid = false;
        }
    }
}

fn low_mask(n: usize) -> u64 {
    if n >= 64 { u64::MAX } else { (1u64 << n) - 1 }
}

/// Writes the low `n <= 64` bits of `v` into `dst` at bit `pos`.
fn put_word(dst: &mut [u64], pos: usize, v: u64, n: usize) {
    let wi = pos / 64;
    let bo = pos % 64;
    let m = low_mask(n);
    let v = v & m;
    dst[wi] = (dst[wi] & !(m << bo)) | (v << bo);
    if bo + n > 64 {
        dst[wi + 1] = (dst[wi + 1] & !(m >> (64 - bo))) | (v >> (64 - bo));
    }
}

/// `len <= 64` bits of `img` from bit `pos`.
fn pk_word(img: &[u64], pos: usize, len: usize) -> u64 {
    let (wi, bo) = (pos / 64, pos % 64);
    let lo = img.get(wi).copied().unwrap_or(0) >> bo;
    let hi = if bo == 0 {
        0
    } else {
        img.get(wi + 1).copied().unwrap_or(0) << (64 - bo)
    };
    (lo | hi) & low_mask(len)
}

/// The IEEE planes' word `i` of the value held by `img`.
fn planes_word(img: &[u64], w: usize, i: usize) -> (u64, u64) {
    let len = (w - i * 64).min(64);
    let v = pk_word(img, i * 64, len);
    let u = pk_word(img, w + i * 64, len);
    (v ^ u, u)
}

/// The bits of plane word `i` that the value bits `[lo, hi)` cover.
fn window_mask(lo: usize, hi: usize, i: usize) -> u64 {
    let base = i * 64;
    let wl = lo.saturating_sub(base).min(64);
    let wh = hi.saturating_sub(base).min(64);
    if wh <= wl {
        return 0;
    }
    low_mask(wh) & !low_mask(wl)
}

/// Rebuilds the whole image from the planes at `start` (the signal's absolute
/// word offset) and clears the window.
fn rebuild(arena: &Arena, start: usize, m: &mut HugeMirror) {
    let w = m.width as usize;
    let n = m.plane_words();
    let (a, b) = (arena.wide_aval(), arena.wide_bval());
    m.pk.fill(0);
    for i in 0..n {
        let len = (w - i * 64).min(64);
        let (av, bv) = (a[start + i], b[start + i]);
        put_word(&mut m.pk, i * 64, av ^ bv, len);
        put_word(&mut m.pk, w + i * 64, bv, len);
    }
    m.valid = true;
    m.clear_dirty();
}

/// `SV_SIM_HUGE_VERIFY`: the whole mirror must equal the planes.
fn verify_matches(arena: &Arena, start: usize, m: &HugeMirror, what: &str) {
    let w = m.width as usize;
    let (a, b) = (arena.wide_aval(), arena.wide_bval());
    for i in 0..m.plane_words() {
        let len = (w - i * 64).min(64);
        let mask = low_mask(len);
        let (na, nb) = planes_word(&m.pk, w, i);
        let (oa, ob) = (a[start + i], b[start + i]);
        assert!(
            ((oa ^ na) | (ob ^ nb)) & mask == 0,
            "SV_SIM_HUGE_VERIFY ({what}): huge signal at wide word {start} (width {w}) \
             diverges from its mirror in plane word {i}: planes ({oa:#x},{ob:#x}) vs \
             mirror ({na:#x},{nb:#x}); dirty window [{}, {})",
            m.dirty_lo,
            m.dirty_hi
        );
    }
}

/// The signal `(handle, slot)` resolved to its owner: the owner's handle, the
/// owner's absolute location.
fn locate(handle: SimHandle, slot: SlotId) -> (&'static InstanceHandle, SlotLocation) {
    let (owner, oslot) = resolve_foreign_slot(handle, slot);
    // SAFETY: see `accessor_impl::sv_get_scalar` -- every handle a compiled
    // kernel passes was minted by `into_sim_handle` and lives for the whole
    // run, which is what makes `'static` sound here.
    let ih: &'static InstanceHandle = unsafe { InstanceHandle::from_sim_handle(owner) };
    (ih, slot_location_for(ih, oslot))
}

/// The process shadow of the huge signal `(handle, slot)` of `width` bits: the
/// signal's mirror, valid and current. `force_rebuild` re-reads the planes
/// even from a valid mirror -- for the caller that knows external code wrote
/// them behind the mirror's back.
///
/// The returned image is `ceil(2*width/64)` words (plus guards) at an address
/// that never changes for the life of the arena.
pub fn huge_prime(handle: SimHandle, slot: SlotId, width: u32, force_rebuild: bool) -> *mut u64 {
    let (ih, loc) = locate(handle, slot);
    debug_assert_eq!(loc.class, SlotClass::Wide);
    debug_assert_eq!(loc.bit_width, width);
    let arena = ih.arena();
    let start = loc.word_offset as usize;
    let mut map = arena.huge.map.borrow_mut();
    let m = map.entry(loc.word_offset).or_insert_with(|| {
        arena.huge.count.set(arena.huge.count.get() + 1);
        HugeMirror::new(width)
    });
    debug_assert_eq!(m.width, width);
    if !m.valid || force_rebuild {
        rebuild(arena, start, m);
    } else if arena.huge.verify {
        verify_matches(arena, start, m, "prime");
    }
    m.pk.as_mut_ptr()
}

/// Widens the dirty window of `(handle, slot)`'s mirror by the value bits
/// `[start, start + len)` (clipped to the signal; `len <= 0` is a no-op, which
/// is what an out-of-range select that wrote nothing passes).
pub fn huge_mark(handle: SimHandle, slot: SlotId, start: i64, len: i64) {
    if len <= 0 {
        return;
    }
    let (ih, loc) = locate(handle, slot);
    let arena = ih.arena();
    let mut map = arena.huge.map.borrow_mut();
    let Some(m) = map.get_mut(&loc.word_offset) else {
        return;
    };
    let lo = i128::from(start).max(0);
    let hi = (i128::from(start) + i128::from(len)).min(i128::from(m.width));
    if lo >= hi {
        return;
    }
    let (lo, hi) = (lo as u32, hi as u32);
    if m.dirty() {
        m.dirty_lo = m.dirty_lo.min(lo);
        m.dirty_hi = m.dirty_hi.max(hi);
    } else {
        m.dirty_lo = lo;
        m.dirty_hi = hi;
    }
}

/// What [`huge_commit`] decided; the caller (`sched::kernel_adapter`, which
/// owns the scheduler hooks this crate layer cannot name) carries it out.
pub enum HugeCommit {
    /// Nothing was dirty.
    Nothing,
    /// The window's words were stored and nothing changed.
    Unchanged,
    /// The window's words were stored and the value changed; `old`/`new` are
    /// bit 0 before and after (the only bit an edge event looks at).
    Changed {
        cell: StateCellId,
        old: Bit4,
        new: Bit4,
        /// The window's old and new plane words, when `wants_delta` asked
        /// for them (a process waits on a select of this signal).
        delta: Option<ChangeDelta>,
    },
    /// The window could not be committed on its own (a forced cell or a
    /// change log): commit `value` (the whole signal) through
    /// `SchedulerOps::commit_blocking_write`, then call
    /// [`huge_commit_full_done`].
    Full {
        cell: StateCellId,
        value: FourStateValue,
        /// Whether the mirror is still current once that write is done.
        revalidate: bool,
    },
}

/// Commits the dirty window of `(handle, slot)`'s mirror to the planes.
pub fn huge_commit(
    handle: SimHandle,
    slot: SlotId,
    width: u32,
    wants_delta: &dyn Fn(StateCellId) -> bool,
) -> HugeCommit {
    let (ih, loc) = locate(handle, slot);
    let arena = ih.arena();
    let start = loc.word_offset as usize;
    let mut map = arena.huge.map.borrow_mut();
    let Some(m) = map.get_mut(&loc.word_offset) else {
        return HugeCommit::Nothing;
    };
    if !m.dirty() {
        return HugeCommit::Nothing;
    }
    debug_assert_eq!(m.width, width);
    let w = m.width as usize;
    let (lo, hi) = (m.dirty_lo as usize, m.dirty_hi as usize);
    let (wlo, whi) = (lo / 64, (hi - 1) / 64);

    // SAFETY: see `accessor_impl::sv_get_scalar`.
    let this = unsafe { InstanceHandle::from_sim_handle(handle) };
    let cell = this.cell_for_slot(slot.0 as usize);
    let forced = ih.vc().force.borrow().contains(cell);
    if forced || ih.vc().records_changes() {
        // `commit_write_at` filters through the force table and records the
        // old/new values: do exactly that, over the whole value. The value is
        // the planes overlaid with the mirror's window words when the mirror
        // is stale, else the whole mirror.
        let n = m.plane_words();
        let (pa, pb) = (arena.wide_aval(), arena.wide_bval());
        let mut aval = pa[start..start + n].to_vec();
        let mut bval = pb[start..start + n].to_vec();
        if m.valid {
            for i in 0..n {
                (aval[i], bval[i]) = planes_word(&m.pk, w, i);
            }
        } else {
            // A stale mirror is right only inside its window.
            for i in wlo..=whi {
                let (a, b) = planes_word(&m.pk, w, i);
                let k = window_mask(lo, hi, i);
                aval[i] = (aval[i] & !k) | (a & k);
                bval[i] = (bval[i] & !k) | (b & k);
            }
        }
        m.clear_dirty();
        return HugeCommit::Full {
            cell,
            value: FourStateValue::Wide { aval, bval },
            revalidate: m.valid && !forced,
        };
    }

    // SAFETY: `start + plane_words` is this signal's reserved range of the
    // wide planes; the raw-pointer accessors never form a slice over the
    // plane (see their doc comments), so retained `WideView`s stay valid.
    let (ap, bp) = unsafe {
        (
            arena.wide_aval_ptr().add(start),
            arena.wide_bval_ptr().add(start),
        )
    };
    let mut changed = false;
    let (mut old0, mut new0) = (Bit4::Zero, Bit4::Zero);
    let mut delta = wants_delta(cell).then(|| ChangeDelta {
        lo_word: wlo,
        ..ChangeDelta::default()
    });
    for i in wlo..=whi {
        let len = (w - i * 64).min(64);
        let mask = low_mask(len);
        let (na, nb) = planes_word(&m.pk, w, i);
        // SAFETY: `i < plane_words()`, see above.
        let (oa, ob) = unsafe { (ap.add(i).read(), bp.add(i).read()) };
        // A stale mirror is right only inside its window.
        let (na, nb) = if m.valid {
            (na, nb)
        } else {
            let k = window_mask(lo, hi, i);
            ((oa & !k) | (na & k), (ob & !k) | (nb & k))
        };
        if i == 0 {
            old0 = Bit4::from_aval_bval(oa & 1 != 0, ob & 1 != 0);
            new0 = Bit4::from_aval_bval(na & 1 != 0, nb & 1 != 0);
        }
        if ((oa ^ na) | (ob ^ nb)) & mask != 0 {
            changed = true;
        }
        if let Some(d) = delta.as_mut() {
            d.old_a.push(oa);
            d.old_b.push(ob);
            d.new_a.push(na);
            d.new_b.push(nb);
        }
        if oa != na || ob != nb {
            // SAFETY: as above; single logical writer.
            unsafe {
                ap.add(i).write(na);
                bp.add(i).write(nb);
            }
        }
    }
    m.clear_dirty();
    if arena.huge.verify && m.valid {
        verify_matches(arena, start, m, "commit");
    }
    if changed {
        HugeCommit::Changed {
            cell,
            old: old0,
            new: new0,
            delta,
        }
    } else {
        HugeCommit::Unchanged
    }
}

/// A nonblocking write to part of a huge signal, in plane words: `aval`/
/// `bval`/`mask` cover the plane words from `window` on.
pub struct NbaWindow {
    pub cell: StateCellId,
    pub window: u32,
    pub aval: Vec<u64>,
    pub bval: Vec<u64>,
    pub mask: Vec<u64>,
}

/// The windowed form of `sig[start +: len] <= image`: `img` is the PK image of
/// the `len`-bit right-hand side (val plane at bit 0, unk plane at bit `len`).
/// The target bits `[start, start + len)` are clipped to the signal, as a
/// part-select write clips; `None` when nothing is left (the write has no
/// effect). Costs `O(len)`, never `O(width)`.
pub fn huge_nba_window(
    handle: SimHandle,
    slot: SlotId,
    width: u32,
    start: i64,
    len: i64,
    img: &[u64],
) -> Option<NbaWindow> {
    let lo = i128::from(start).max(0);
    let hi = (i128::from(start) + i128::from(len)).min(i128::from(width));
    if len <= 0 || lo >= hi {
        return None;
    }
    let (lo, hi) = (lo as usize, hi as usize);
    let (start, len) = (start as i128, len as usize);
    let (wlo, whi) = (lo / 64, (hi - 1) / 64);
    let words = whi - wlo + 1;
    let (mut aval, mut bval, mut mask) = (
        Vec::with_capacity(words),
        Vec::with_capacity(words),
        Vec::with_capacity(words),
    );
    for i in wlo..=whi {
        let base = i * 64;
        let (s, e) = (lo.max(base), hi.min(base + 64));
        let (n, sh) = (e - s, s - base);
        let src = (s as i128 - start) as usize;
        let v = pk_word(img, src, n);
        let u = pk_word(img, len + src, n);
        aval.push((v ^ u) << sh);
        bval.push(u << sh);
        mask.push(low_mask(n) << sh);
    }
    // SAFETY: see `accessor_impl::sv_get_scalar`.
    let this = unsafe { InstanceHandle::from_sim_handle(handle) };
    Some(NbaWindow {
        cell: this.cell_for_slot(slot.0 as usize),
        window: wlo as u32,
        aval,
        bval,
        mask,
    })
}

/// The plane words `[lo_word, lo_word + words)` of the huge signal at the
/// wide-plane word offset `start`.
pub(crate) fn read_window(
    arena: &Arena,
    start: usize,
    lo_word: usize,
    words: usize,
) -> (Vec<u64>, Vec<u64>) {
    let at = start + lo_word;
    (
        arena.wide_aval()[at..at + words].to_vec(),
        arena.wide_bval()[at..at + words].to_vec(),
    )
}

/// Stores the plane words `aval`/`bval` at `[lo_word, lo_word + aval.len())`
/// of the huge signal whose planes begin at `start` (`width` bits), the
/// windowed twin of a whole-value `commit_write_at` for the nonblocking
/// commit. The caller has already ruled out a force filter and a change log.
/// Returns whether any bit changed. The signal's mirror, if any, is brought
/// up to date outside its dirty window so the invariant of this module keeps
/// holding without an `O(N)` rebuild.
pub(crate) fn store_window(
    arena: &Arena,
    start: usize,
    width: u32,
    lo_word: usize,
    aval: &[u64],
    bval: &[u64],
) -> bool {
    let w = width as usize;
    let plane_words = w.div_ceil(64);
    debug_assert_eq!(aval.len(), bval.len());
    debug_assert!(lo_word + aval.len() <= plane_words);
    // SAFETY: `start + plane_words` is this signal's reserved range of the
    // wide planes; the raw-pointer accessors never form a slice over the
    // plane, so retained `WideView`s stay valid.
    let (ap, bp) = unsafe {
        (
            arena.wide_aval_ptr().add(start),
            arena.wide_bval_ptr().add(start),
        )
    };
    let mut changed = false;
    for (j, (&na, &nb)) in aval.iter().zip(bval).enumerate() {
        let i = lo_word + j;
        let mask = low_mask((w - i * 64).min(64));
        // SAFETY: `i < plane_words`, see above.
        let (oa, ob) = unsafe { (ap.add(i).read(), bp.add(i).read()) };
        if ((oa ^ na) | (ob ^ nb)) & mask != 0 {
            changed = true;
        }
        if oa != na || ob != nb {
            // SAFETY: as above; single logical writer.
            unsafe {
                ap.add(i).write(na);
                bp.add(i).write(nb);
            }
        }
    }
    if changed {
        let mut map = arena.huge.map.borrow_mut();
        if let Some(m) = map.get_mut(&(start as u32)).filter(|m| m.valid) {
            let (dlo, dhi) = if m.dirty() {
                (m.dirty_lo as usize, m.dirty_hi as usize)
            } else {
                (0, 0)
            };
            for (j, (&na, &nb)) in aval.iter().zip(bval).enumerate() {
                let i = lo_word + j;
                let len = (w - i * 64).min(64);
                // Bits the compiled code has written to the image but not
                // yet committed keep their image value.
                let keep = window_mask(dlo, dhi, i);
                let (ca, cb) = planes_word(&m.pk, w, i);
                let (ma, mb) = ((ca & keep) | (na & !keep), (cb & keep) | (nb & !keep));
                put_word(&mut m.pk, i * 64, ma ^ mb, len);
                put_word(&mut m.pk, w + i * 64, mb, len);
            }
            if arena.huge.verify && !m.dirty() {
                verify_matches(arena, start, m, "nba");
            }
        }
    }
    changed
}

/// Called after the [`HugeCommit::Full`] write: the write itself went through
/// `write_slot`, which invalidated the mirror; a mirror that is still current
/// (`revalidate`) is made valid again.
pub fn huge_commit_full_done(handle: SimHandle, slot: SlotId, revalidate: bool) {
    if !revalidate {
        return;
    }
    let (ih, loc) = locate(handle, slot);
    let arena = ih.arena();
    if let Some(m) = arena.huge.map.borrow_mut().get_mut(&loc.word_offset) {
        m.valid = true;
        m.clear_dirty();
    }
}