ternaria_vm/mmu.rs
1//! Address translation: trit-sliced page tables.
2//!
3//! # Why these numbers
4//!
5//! A page is 3^6 = 729 trytes, matching the emulator's allocation granule. A
6//! page table entry is one word, three trytes, so a page holds 3^5 = 243
7//! entries and an index into a table is five trits.
8//!
9//! Five-trit indices are what make the layout work: **a page table is exactly
10//! one page**. Allocating a table is allocating a page, with nothing left over
11//! and nothing spanning a boundary. Seven-trit indices would give a three-level
12//! walk instead of four, but each table would then be nine pages.
13//!
14//! Four levels of five trits is twenty trits of page number, which with the
15//! six-trit offset makes a 26-trit virtual address. That is one trit short of
16//! the architectural word, so the top trit of a virtual address must be zero
17//! while translation is on. This is the same bargain x86-64 strikes in
18//! requiring canonical addresses, and it costs a third of a space nothing is
19//! close to filling.
20//!
21//! ```text
22//! trits 0..6 offset within the page
23//! trits 6..11 level 0 index
24//! trits 11..16 level 1 index
25//! trits 16..21 level 2 index
26//! trits 21..26 level 3 index
27//! trit 26 must be zero
28//! ```
29//!
30//! # Entry format
31//!
32//! ```text
33//! trits 0..20 physical page number
34//! trit 20 valid
35//! trit 21 readable
36//! trit 22 writable
37//! trit 23 executable
38//! trit 24 user-accessible
39//! trit 25 leaf: maps a page rather than naming the next table
40//! trit 26 reserved, must be zero
41//! ```
42//!
43//! A leaf above level 0 maps a superpage: the index trits not yet consumed
44//! join the offset, so a leaf at level 1 maps 3^11 trytes.
45
46use ternaria_arith::{Trit, Word};
47
48/// Trytes per page: 3^6.
49pub const PAGE_TRYTES: i64 = 729;
50/// Trits of offset within a page.
51pub const OFFSET_TRITS: u32 = 6;
52/// Trits of index per level.
53pub const INDEX_TRITS: u32 = 5;
54/// How many levels the walk descends.
55pub const LEVELS: u32 = 4;
56/// Trits of physical page number in an entry.
57pub const PPN_TRITS: u32 = 20;
58
59/// Trit positions of the entry's flags.
60pub mod flag {
61 /// The entry is in use.
62 pub const VALID: usize = 20;
63 /// Loads are permitted.
64 pub const READ: usize = 21;
65 /// Stores are permitted.
66 pub const WRITE: usize = 22;
67 /// Instruction fetch is permitted.
68 pub const EXECUTE: usize = 23;
69 /// User-level access is permitted.
70 pub const USER: usize = 24;
71 /// The entry maps a page rather than naming the next table.
72 pub const LEAF: usize = 25;
73}
74
75/// What an access is for. Each needs a different permission.
76#[derive(Clone, Copy, PartialEq, Eq, Debug)]
77pub enum Access {
78 /// A load.
79 Read,
80 /// A store.
81 Write,
82 /// An instruction fetch.
83 Execute,
84}
85
86impl Access {
87 /// The flag position this access requires.
88 pub const fn flag(self) -> usize {
89 match self {
90 Access::Read => flag::READ,
91 Access::Write => flag::WRITE,
92 Access::Execute => flag::EXECUTE,
93 }
94 }
95}
96
97/// One page table entry.
98#[derive(Clone, Copy, PartialEq, Eq, Debug)]
99pub struct Entry(pub Word);
100
101impl Entry {
102 /// Reads one flag.
103 pub fn flag(self, position: usize) -> bool {
104 self.0.trits()[position] == Trit::Pos
105 }
106
107 /// The physical page number.
108 pub fn ppn(self) -> i64 {
109 let trits = self.0.trits();
110 let mut acc: i64 = 0;
111 let mut weight: i64 = 1;
112 for &t in trits.iter().take(PPN_TRITS as usize) {
113 acc += (t as i8 as i64) * weight;
114 weight *= 3;
115 }
116 acc
117 }
118
119 /// Builds an entry. `perms` names the accesses the mapping permits.
120 pub fn new(ppn: i64, leaf: bool, user: bool, perms: &[Access]) -> Entry {
121 let mut trits = Word::from_value(ppn).trits();
122 // The page number occupies the low trits; clear anything above it that
123 // a negative ppn would have sign-extended into.
124 for t in trits.iter_mut().skip(PPN_TRITS as usize) {
125 *t = Trit::Zero;
126 }
127 trits[flag::VALID] = Trit::Pos;
128 if leaf {
129 trits[flag::LEAF] = Trit::Pos;
130 }
131 if user {
132 trits[flag::USER] = Trit::Pos;
133 }
134 for p in perms {
135 trits[p.flag()] = Trit::Pos;
136 }
137 Entry(Word::from_trits(trits))
138 }
139}
140
141/// The index this level takes from a virtual address.
142pub fn index(virt: Word, level: u32) -> i64 {
143 let trits = virt.trits();
144 let base = (OFFSET_TRITS + level * INDEX_TRITS) as usize;
145 let mut acc: i64 = 0;
146 let mut weight: i64 = 1;
147 for k in 0..INDEX_TRITS as usize {
148 acc += (trits[base + k] as i8 as i64) * weight;
149 weight *= 3;
150 }
151 acc
152}
153
154/// The part of a virtual address a leaf at `level` passes through unchanged.
155///
156/// At level 0 this is the page offset. Higher up it is the offset plus the
157/// index trits the walk did not reach, which is what makes a superpage.
158pub fn passthrough(virt: Word, level: u32) -> i64 {
159 let trits = virt.trits();
160 let width = (OFFSET_TRITS + level * INDEX_TRITS) as usize;
161 let mut acc: i64 = 0;
162 let mut weight: i64 = 1;
163 for &t in trits.iter().take(width) {
164 acc += (t as i8 as i64) * weight;
165 weight *= 3;
166 }
167 acc
168}
169
170/// The size in trytes of a page mapped by a leaf at `level`.
171pub fn page_span(level: u32) -> i64 {
172 3i64.pow(OFFSET_TRITS + level * INDEX_TRITS)
173}
174
175/// True if the address fits the 26 trits translation can express.
176pub fn is_canonical(virt: Word) -> bool {
177 virt.trits()[(OFFSET_TRITS + LEVELS * INDEX_TRITS) as usize] == Trit::Zero
178}