ternaria_vm/

lib.rs

//! The reference interpreter.
//!
//! A fetch, decode, execute loop written for clarity rather than speed. Later
//! implementations, including the phase 7 JIT, are checked against it.
//!
//! # Machine state
//!
//! - 27 registers numbered -13 to 13 (D-05). `r0` reads as zero and discards
//!   writes.
//! - `pc` holds the tryte address of the instruction being executed. It
//!   advances by 3 trytes unless an instruction redirects it.
//! - Memory is passed in rather than owned, so one [`Cpu`] can run against
//!   different memories and state stays separable from storage.
//!
//! # Traps
//!
//! Every abnormal condition raises a [`Trap`] carrying the `pc` that caused it.
//! Arithmetic overflow traps rather than wrapping, uninitialised reads trap
//! rather than returning zero, and undefined opcodes trap.
//!
//! Wrapping arithmetic exists in `ternaria-arith` and can be exposed as
//! separate opcodes if a program needs it.

#![forbid(unsafe_code)]
#![warn(missing_docs)]

use std::fmt;

use ternaria_arith::{Trit, Tryte, Word};
use ternaria_isa::REG_COUNT;
use ternaria_mem::{Addressable, MemoryError, WORD_TRYTES};

// Re-exported so a caller needs only this crate. `DecodeError` and
// `MemoryError` appear in [`Trap`], so they are public regardless.
pub mod csr;
pub mod mmu;

pub use csr::{Cause, Csrs, Priv};
pub use mmu::{Access, Entry as PageEntry};
pub use ternaria_isa::{DecodeError, Imm, Instruction, Opcode, Reg, asm};
pub use ternaria_mem::MemoryError as MemError;

/// Something stopped execution.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Trap {
    /// The word at `pc` is not a valid instruction.
    IllegalInstruction {
        /// Where it happened.
        pc: i64,
        /// Why the decode failed.
        cause: DecodeError,
    },
    /// A memory access failed.
    Memory {
        /// Where it happened.
        pc: i64,
        /// Why the access failed.
        cause: MemoryError,
    },
    /// Division or remainder by zero.
    DivideByZero {
        /// Where it happened.
        pc: i64,
    },
    /// A result left the 27-trit range.
    Overflow {
        /// Where it happened.
        pc: i64,
        /// Which operation overflowed.
        op: Opcode,
    },
    /// Control flow left the address space.
    PcOutOfRange {
        /// Where it happened.
        pc: i64,
    },
    /// An `ecall`. Not a fault: the deliberate way into the operating system.
    Ecall {
        /// Where it happened.
        pc: i64,
    },
    /// An instruction needed a privilege the machine was not at.
    Privilege {
        /// Where it happened.
        pc: i64,
        /// The level the instruction required.
        needed: Priv,
    },
    /// Address translation failed.
    PageFault {
        /// Where it happened.
        pc: i64,
        /// The virtual address that could not be translated.
        addr: i64,
    },
    /// [`Cpu::run`] reached its step budget without halting.
    StepLimit {
        /// Where it was when the budget ran out.
        pc: i64,
        /// How many steps had run.
        steps: u64,
    },
}

impl fmt::Display for Trap {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Trap::IllegalInstruction { pc, cause } => {
                write!(f, "illegal instruction at pc={pc}: {cause}")
            }
            Trap::Memory { pc, cause } => write!(f, "memory fault at pc={pc}: {cause}"),
            Trap::DivideByZero { pc } => write!(f, "divide by zero at pc={pc}"),
            Trap::Overflow { pc, op } => {
                write!(f, "arithmetic overflow in {} at pc={pc}", op.mnemonic())
            }
            Trap::PcOutOfRange { pc } => write!(f, "pc left the address space at pc={pc}"),
            Trap::Ecall { pc } => write!(f, "ecall at pc={pc} with no trap vector set"),
            Trap::Privilege { pc, needed } => {
                write!(f, "instruction at pc={pc} requires {needed:?} privilege")
            }
            Trap::PageFault { pc, addr } => {
                write!(f, "page fault on address {addr} at pc={pc}")
            }
            Trap::StepLimit { pc, steps } => {
                write!(f, "step limit reached after {steps} steps at pc={pc}")
            }
        }
    }
}

impl std::error::Error for Trap {}

/// The cause, the value the handler sees in `tval`, and the pc to save.
fn describe(trap: Trap) -> (Cause, i64, i64) {
    match trap {
        Trap::IllegalInstruction { pc, .. } => (Cause::IllegalInstruction, 0, pc),
        Trap::Memory { pc, cause } => (Cause::Memory, faulting_address(cause), pc),
        Trap::DivideByZero { pc } => (Cause::DivideByZero, 0, pc),
        Trap::Overflow { pc, op } => (Cause::Overflow, op.value(), pc),
        Trap::PcOutOfRange { pc } => (Cause::PcOutOfRange, pc, pc),
        Trap::Ecall { pc } => (Cause::Ecall, 0, pc),
        Trap::Privilege { pc, needed } => {
            (Cause::PrivilegeViolation, needed.trit() as i8 as i64, pc)
        }
        Trap::PageFault { pc, addr } => (Cause::PageFault, addr, pc),
        // Filtered out before this is reached.
        Trap::StepLimit { pc, .. } => (Cause::IllegalInstruction, 0, pc),
    }
}

/// The address a memory error names, for `tval`.
fn faulting_address(e: MemoryError) -> i64 {
    match e {
        MemoryError::Uninitialised { addr }
        | MemoryError::Misaligned { addr }
        | MemoryError::Device { addr, .. }
        | MemoryError::AddressOverflow { addr, .. } => addr,
        MemoryError::NotAByte { value } => value,
    }
}

/// Result of a completed run.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Halted {
    /// How many instructions executed.
    pub steps: u64,
}

/// The processor.
#[derive(Clone)]
pub struct Cpu {
    regs: [Word; REG_COUNT],
    pc: Word,
    halted: bool,
    steps: u64,
    /// Control and status registers. Public so a host can set a trap vector or
    /// inspect a cause without going through guest instructions.
    pub csrs: Csrs,
    privilege: Priv,
}

impl Cpu {
    /// A processor with every register zero, starting at `entry`.
    pub fn new(entry: Word) -> Cpu {
        Cpu {
            regs: [Word::ZERO; REG_COUNT],
            pc: entry,
            halted: false,
            steps: 0,
            csrs: Csrs::default(),
            // Reset is at machine level, so a program loaded without an
            // operating system under it can still reach devices.
            privilege: Priv::Machine,
        }
    }

    /// Reads a register. `r0` always reads zero.
    #[inline]
    pub fn reg(&self, r: Reg) -> Word {
        if r == Reg::ZERO {
            Word::ZERO
        } else {
            self.regs[r.index()]
        }
    }

    /// Writes a register. Writes to `r0` are discarded, which lets `r0` serve
    /// as a destination for instructions run only for their side effects, such
    /// as `jalr r0, r3, 0` to return without saving a link.
    #[inline]
    pub fn set_reg(&mut self, r: Reg, value: Word) {
        if r != Reg::ZERO {
            self.regs[r.index()] = value;
        }
    }

    /// The program counter - the tryte address of the next instruction.
    pub fn pc(&self) -> Word {
        self.pc
    }

    /// Sets the program counter.
    pub fn set_pc(&mut self, pc: Word) {
        self.pc = pc;
    }

    /// True once a `halt` has executed.
    pub fn halted(&self) -> bool {
        self.halted
    }

    /// How many instructions have executed.
    pub fn steps(&self) -> u64 {
        self.steps
    }

    /// The current privilege level.
    pub fn privilege(&self) -> Priv {
        self.privilege
    }

    /// Sets the privilege level directly.
    ///
    /// For a host bringing a machine up, or a test. A guest changes privilege
    /// only by taking a trap or executing `tret`.
    pub fn set_privilege(&mut self, level: Priv) {
        self.privilege = level;
    }

    /// The value in register `n`, numbered -13 to 13.
    ///
    /// # Panics
    /// If `n` is outside the register range.
    pub fn reg_value(&self, n: i8) -> i64 {
        self.reg(Reg::new(n).expect("register number out of range"))
            .value()
    }

    /// Loads a word through translation, as an instruction would.
    ///
    /// Exposed so a host or a test can see what an address means at the
    /// machine's current privilege without assembling a program to do it.
    pub fn load_word<A: Addressable>(&self, virt: i64, mem: &mut A) -> Result<Word, Trap> {
        let addr = self.access(virt, Access::Read, mem)?;
        mem.read_word(addr).map_err(|cause| Trap::Memory {
            pc: self.pc.value(),
            cause,
        })
    }

    /// Turns a virtual address into a physical one.
    ///
    /// Translation is off at machine level and off whenever `ptbr` is zero,
    /// which is the reset state. Both cases are the identity, so a program
    /// loaded without an operating system under it never walks a table.
    fn translate<A: Addressable>(
        &self,
        virt: i64,
        access: Access,
        mem: &mut A,
    ) -> Result<i64, Trap> {
        if self.privilege == Priv::Machine || self.csrs.ptbr == 0 {
            return Ok(virt);
        }
        let pc = self.pc.value();
        let fault = || Trap::PageFault { pc, addr: virt };
        let va = Word::new(virt).ok_or_else(fault)?;
        if !mmu::is_canonical(va) {
            return Err(fault());
        }

        let mut table = self.csrs.ptbr;
        for level in (0..mmu::LEVELS).rev() {
            let slot = table
                .checked_add(
                    mmu::index(va, level)
                        .checked_mul(WORD_TRYTES)
                        .ok_or_else(fault)?,
                )
                .ok_or_else(fault)?;
            let word = mem
                .read_word(Word::new(slot).ok_or_else(fault)?)
                .map_err(|_| fault())?;
            let entry = mmu::Entry(word);
            if !entry.flag(mmu::flag::VALID) {
                return Err(fault());
            }
            if entry.flag(mmu::flag::LEAF) {
                if !entry.flag(access.flag()) {
                    return Err(fault());
                }
                if self.privilege == Priv::User && !entry.flag(mmu::flag::USER) {
                    return Err(fault());
                }
                // A leaf above level 0 maps a superpage, so the index trits the
                // walk never reached stay part of the offset.
                let base = entry
                    .ppn()
                    .checked_mul(mmu::PAGE_TRYTES)
                    .ok_or_else(fault)?;
                return base
                    .checked_add(mmu::passthrough(va, level))
                    .ok_or_else(fault);
            }
            table = entry
                .ppn()
                .checked_mul(mmu::PAGE_TRYTES)
                .ok_or_else(fault)?;
        }
        // Every level was a table and none was a leaf.
        Err(fault())
    }

    /// Translates and checks that the access is one this privilege may make.
    fn access<A: Addressable>(&self, virt: i64, access: Access, mem: &mut A) -> Result<Word, Trap> {
        let phys = self.translate(virt, access, mem)?;
        let addr = Word::new(phys).ok_or(Trap::Memory {
            pc: self.pc.value(),
            cause: MemoryError::AddressOverflow {
                addr: phys,
                len: WORD_TRYTES,
            },
        })?;
        if mem.is_privileged(addr) {
            self.require(Priv::Supervisor, self.pc.value())?;
        }
        Ok(addr)
    }

    /// Fails unless the machine is at `needed` or above.
    fn require(&self, needed: Priv, pc: i64) -> Result<(), Trap> {
        if self.privilege >= needed {
            Ok(())
        } else {
            Err(Trap::Privilege { pc, needed })
        }
    }

    /// Moves `pc` by a number of instructions, scaling by 3 to get trytes.
    /// Branch targets are therefore word-aligned by construction.
    fn jump_by(&mut self, instructions: i64) -> Result<(), Trap> {
        let here = self.pc.value();
        let target = instructions
            .checked_mul(WORD_TRYTES)
            .and_then(|d| here.checked_add(d))
            .ok_or(Trap::PcOutOfRange { pc: here })?;
        self.pc = Word::new(target).ok_or(Trap::PcOutOfRange { pc: here })?;
        Ok(())
    }

    /// Executes one instruction. Returns `Ok(false)` once halted; further
    /// calls do nothing.
    ///
    /// # Traps
    ///
    /// What a trap does depends on whether an operating system has claimed
    /// them. With `tvec` zero, which is the reset state, a trap stops the
    /// machine and is returned to the host. With `tvec` set, the trap is
    /// vectored to the handler and `step` returns normally, so a program that
    /// faults no longer takes the machine down.
    pub fn step<A: Addressable>(&mut self, mem: &mut A) -> Result<bool, Trap> {
        if self.halted {
            return Ok(false);
        }

        // An interrupt is taken between instructions, before the fetch, so the
        // saved pc names the instruction that has not run rather than one that
        // has half run.
        self.csrs.ip = mem.interrupts();
        if let Some(cause) = self.csrs.pending_interrupt()
            && self.csrs.tvec != 0
        {
            self.enter_trap(cause, 0, self.pc.value())?;
            return Ok(true);
        }

        match self.step_once(mem) {
            Ok(()) => {
                self.steps += 1;
                Ok(!self.halted)
            }
            Err(trap) => {
                self.steps += 1;
                self.take(trap).map(|()| !self.halted)
            }
        }
    }

    /// One fetch, decode and execute, with no trap handling.
    fn step_once<A: Addressable>(&mut self, mem: &mut A) -> Result<(), Trap> {
        let here = self.pc.value();
        let phys = self.translate(here, Access::Execute, mem)?;
        let word = mem
            .read_word(Word::from_value(phys))
            .map_err(|cause| Trap::Memory { pc: here, cause })?;
        let instr = Instruction::decode(word)
            .map_err(|cause| Trap::IllegalInstruction { pc: here, cause })?;
        self.execute(instr, mem)
    }

    /// Vectors a trap to the handler, or passes it to the host if none is set.
    fn take(&mut self, trap: Trap) -> Result<(), Trap> {
        // The step limit is a property of the host's budget, not of the guest,
        // so there is nothing for a guest handler to do about it.
        if self.csrs.tvec == 0 || matches!(trap, Trap::StepLimit { .. }) {
            return Err(trap);
        }
        let (cause, tval, pc) = describe(trap);
        self.enter_trap(cause, tval, pc)
    }

    /// Saves the interrupted state and enters the handler at machine level.
    fn enter_trap(&mut self, cause: Cause, tval: i64, pc: i64) -> Result<(), Trap> {
        self.csrs.tepc = pc;
        self.csrs.tcause = cause.value();
        self.csrs.tval = tval;
        self.csrs.tpriv = self.privilege;
        // Interrupts off inside the handler, restored by `tret`. A pending
        // source is level-triggered, so without this it would re-fire before
        // the handler's first instruction and the handler would never run.
        self.csrs.tie = self.csrs.ie;
        self.csrs.ie = Word::ZERO;
        self.privilege = Priv::Machine;
        self.pc = Word::new(self.csrs.tvec).ok_or(Trap::PcOutOfRange { pc: self.csrs.tvec })?;
        Ok(())
    }

    /// Runs until halt or trap, at most `max_steps` instructions. The budget
    /// bounds programs that do not terminate.
    pub fn run<A: Addressable>(&mut self, mem: &mut A, max_steps: u64) -> Result<Halted, Trap> {
        while self.steps < max_steps {
            if !self.step(mem)? {
                return Ok(Halted { steps: self.steps });
            }
        }
        Err(Trap::StepLimit {
            pc: self.pc.value(),
            steps: self.steps,
        })
    }

    /// Applies one decoded instruction.
    fn execute<A: Addressable>(&mut self, instr: Instruction, mem: &mut A) -> Result<(), Trap> {
        let here = self.pc.value();
        let op = instr.op;
        let a = self.reg(instr.rs1);
        let b = self.reg(instr.rs2);
        let imm = instr.imm.value() as i64;

        // Overflow is a trap, never a wrap.
        let checked =
            |r: Option<Word>| -> Result<Word, Trap> { r.ok_or(Trap::Overflow { pc: here, op }) };

        // Control-flow arms set pc and return early; the rest fall through.
        match op {
            Opcode::Nop => {}
            Opcode::Add => {
                let v = checked(a.checked_add(b))?;
                self.set_reg(instr.rd, v);
            }
            Opcode::Sub => {
                let v = checked(a.checked_sub(b))?;
                self.set_reg(instr.rd, v);
            }
            Opcode::Mul => {
                let v = checked(a.checked_mul(b))?;
                self.set_reg(instr.rd, v);
            }
            Opcode::Div => {
                let v = a.checked_div(b).ok_or(Trap::DivideByZero { pc: here })?;
                self.set_reg(instr.rd, v);
            }
            Opcode::Rem => {
                let v = a.checked_rem(b).ok_or(Trap::DivideByZero { pc: here })?;
                self.set_reg(instr.rd, v);
            }
            Opcode::Min => self.set_reg(instr.rd, a.trit_and(b)),
            Opcode::Max => self.set_reg(instr.rd, a.trit_or(b)),
            Opcode::Cmp3 => {
                let t = a.cmp3(b);
                self.set_reg(instr.rd, Word::from_value(t.value() as i64));
            }
            // Neither can overflow; the range is symmetric.
            Opcode::Neg => self.set_reg(instr.rd, a.neg()),
            Opcode::Abs => self.set_reg(instr.rd, a.abs()),
            Opcode::Addi => {
                let v = checked(a.checked_add(Word::from_value(imm)))?;
                self.set_reg(instr.rd, v);
            }
            // A negative shift distance shifts the other way.
            Opcode::Shl => {
                let v = if imm >= 0 {
                    checked(a.checked_shl_trits(imm as u32))?
                } else {
                    a.shr_trits((-imm) as u32)
                };
                self.set_reg(instr.rd, v);
            }
            Opcode::Shr => {
                let v = if imm >= 0 {
                    a.shr_trits(imm as u32)
                } else {
                    checked(a.checked_shl_trits((-imm) as u32))?
                };
                self.set_reg(instr.rd, v);
            }
            Opcode::Lw => {
                let virt = checked(a.checked_add(Word::from_value(imm)))?;
                let addr = self.access(virt.value(), Access::Read, mem)?;
                let v = mem
                    .read_word(addr)
                    .map_err(|cause| Trap::Memory { pc: here, cause })?;
                self.set_reg(instr.rd, v);
            }
            Opcode::Lt => {
                let virt = checked(a.checked_add(Word::from_value(imm)))?;
                let addr = self.access(virt.value(), Access::Read, mem)?;
                let v = mem
                    .read_tryte(addr)
                    .map_err(|cause| Trap::Memory { pc: here, cause })?;
                self.set_reg(instr.rd, Word::from_value(v.value() as i64));
            }
            Opcode::St => {
                let virt = checked(a.checked_add(Word::from_value(imm)))?;
                let addr = self.access(virt.value(), Access::Write, mem)?;
                let v = self.reg(instr.rd);
                // Values outside the tryte range are a program error rather
                // than a silent truncation.
                let t = i32::try_from(v.value())
                    .ok()
                    .and_then(Tryte::new)
                    .ok_or(Trap::Overflow { pc: here, op })?;
                mem.write_tryte(addr, t)
                    .map_err(|cause| Trap::Memory { pc: here, cause })?;
            }
            Opcode::Sw => {
                let virt = checked(a.checked_add(Word::from_value(imm)))?;
                let addr = self.access(virt.value(), Access::Write, mem)?;
                let v = self.reg(instr.rd);
                mem.write_word(addr, v)
                    .map_err(|cause| Trap::Memory { pc: here, cause })?;
            }
            Opcode::Jal => {
                let link = self.next_pc()?;
                self.set_reg(instr.rd, link);
                self.jump_by(imm)?;
                return Ok(());
            }
            Opcode::Jalr => {
                let link = self.next_pc()?;
                // Read the target before writing rd, or `jalr r1, r1, 0` would
                // read back its own link.
                let target = a.value();
                self.set_reg(instr.rd, link);
                let dest = imm
                    .checked_mul(WORD_TRYTES)
                    .and_then(|d| target.checked_add(d))
                    .ok_or(Trap::PcOutOfRange { pc: here })?;
                self.pc = Word::new(dest).ok_or(Trap::PcOutOfRange { pc: here })?;
                return Ok(());
            }
            Opcode::Br3 => {
                // Forward if positive, backward if negative, next if zero.
                match a.signum() {
                    Trit::Pos => self.jump_by(imm)?,
                    Trit::Neg => self.jump_by(-imm)?,
                    Trit::Zero => self.jump_by(1)?,
                }
                return Ok(());
            }
            Opcode::Brz => {
                let taken = a.signum() == Trit::Zero;
                self.jump_by(if taken { imm } else { 1 })?;
                return Ok(());
            }
            // brn and brp take a single target each, for the cases where the
            // two br3 targets cannot be mirrored about the branch.
            Opcode::Brn => {
                let taken = a.signum() == Trit::Neg;
                self.jump_by(if taken { imm } else { 1 })?;
                return Ok(());
            }
            Opcode::Csrr => {
                self.require(Priv::Supervisor, here)?;
                let v = self
                    .csrs
                    .read(imm, self.privilege)
                    .ok_or(Trap::IllegalInstruction {
                        pc: here,
                        cause: DecodeError::UnknownOpcode { value: imm },
                    })?;
                self.set_reg(instr.rd, Word::from_value(v));
            }
            Opcode::Csrw => {
                self.require(Priv::Supervisor, here)?;
                self.csrs
                    .write(imm, a.value())
                    .ok_or(Trap::IllegalInstruction {
                        pc: here,
                        cause: DecodeError::UnknownOpcode { value: imm },
                    })?;
            }
            Opcode::Tret => {
                self.require(Priv::Supervisor, here)?;
                self.privilege = self.csrs.tpriv;
                self.csrs.ie = self.csrs.tie;
                self.pc =
                    Word::new(self.csrs.tepc).ok_or(Trap::PcOutOfRange { pc: self.csrs.tepc })?;
                return Ok(());
            }
            // Not a fault. The vectoring in `step` treats it like one because
            // the mechanism is identical; only the cause differs.
            Opcode::Ecall => return Err(Trap::Ecall { pc: here }),
            Opcode::Brp => {
                let taken = a.signum() == Trit::Pos;
                self.jump_by(if taken { imm } else { 1 })?;
                return Ok(());
            }
            Opcode::Halt => {
                self.halted = true;
                self.steps += 1;
                return Ok(());
            }
        }

        self.jump_by(1)
    }

    /// The address of the following instruction, for a link register.
    fn next_pc(&self) -> Result<Word, Trap> {
        let here = self.pc.value();
        here.checked_add(WORD_TRYTES)
            .and_then(Word::new)
            .ok_or(Trap::PcOutOfRange { pc: here })
    }
}

/// Writes instructions into memory as consecutive words. `at` must be
/// word-aligned.
pub fn load<A: Addressable>(
    mem: &mut A,
    at: Word,
    program: &[Instruction],
) -> Result<(), MemoryError> {
    let mut addr = at.value();
    for instr in program {
        mem.write_word(Word::from_value(addr), instr.encode())?;
        addr += WORD_TRYTES;
    }
    Ok(())
}

/// Assembles source, loads it at `at`, and returns a [`Cpu`] ready to run.
pub fn assemble_and_load<A: Addressable>(
    mem: &mut A,
    at: Word,
    source: &str,
) -> Result<Cpu, Box<dyn std::error::Error>> {
    // Assembled for where it is loaded, so `@label` names a real address.
    let program = ternaria_isa::asm::assemble_at(source, at.value())?;
    load(mem, at, &program.instructions)?;
    Ok(Cpu::new(at))
}