Skip to main content

vector/
mmu.rs

1//! [Vectorized Emulation: MMU Design](https://gamozolabs.github.io/fuzzing/2018/11/19/vectorized_emulation_mmu.html)
2
3use jit::{GuestMemory, PAGE_SIZE, PagePerms};
4use std::ops::{BitOr, BitOrAssign};
5
6use crate::LANES;
7
8const QWORD_SIZE: usize = 8;
9const CELLS_PER_PAGE: usize = PAGE_SIZE / QWORD_SIZE;
10
11const RADIX_BITS: usize = 13;
12const RADIX_ENTRIES: usize = 1 << RADIX_BITS;
13const RADIX_MASK: u64 = (RADIX_ENTRIES - 1) as u64;
14
15const TLB_ENTRIES: usize = 16;
16
17#[path = "access.rs"]
18mod access;
19use crate::abi::{EXEC_CACHE_SLOTS, ExecCache, ExecFn, LoadFn, StoreFn};
20use access::{exec_callback, load_callback, store_callback};
21
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23pub struct BytePerms(u8);
24
25impl BytePerms {
26    pub const READ: Self = Self(1 << 0);
27    pub const WRITE: Self = Self(1 << 1);
28    pub const EXEC: Self = Self(1 << 2);
29    pub const READ_AFTER_WRITE: Self = Self(1 << 3);
30
31    pub const fn empty() -> Self {
32        Self(0)
33    }
34
35    pub const fn bits(self) -> u8 {
36        self.0
37    }
38
39    pub const fn from_bits(bits: u8) -> Self {
40        Self(bits & 0xf)
41    }
42
43    pub const fn contains(self, other: Self) -> bool {
44        self.0 & other.0 == other.0
45    }
46}
47
48impl BitOr for BytePerms {
49    type Output = Self;
50
51    fn bitor(self, rhs: Self) -> Self::Output {
52        Self(self.0 | rhs.0)
53    }
54}
55
56impl BitOrAssign for BytePerms {
57    fn bitor_assign(&mut self, rhs: Self) {
58        self.0 |= rhs.0;
59    }
60}
61
62impl From<PagePerms> for BytePerms {
63    fn from(value: PagePerms) -> Self {
64        Self::from_bits(value.bits())
65    }
66}
67
68#[repr(C, align(64))]
69#[derive(Clone)]
70struct DataCell {
71    lanes: [u64; LANES],
72}
73
74#[repr(C, align(8))]
75#[derive(Clone)]
76struct PermCell {
77    lanes: [u8; LANES],
78}
79
80#[derive(Clone)]
81struct VectorPage {
82    base: u64,
83    present_mask: u8,
84    data: Box<[DataCell]>,
85    perms: Box<[PermCell]>,
86}
87
88#[derive(Clone)]
89pub(crate) struct MemorySnapshot {
90    baseline: u64,
91    pages: Vec<VectorPage>,
92}
93
94struct RadixTable {
95    levels: [Vec<Box<[usize]>>; 4],
96}
97
98impl RadixTable {
99    fn new() -> Self {
100        let mut levels = std::array::from_fn(|_| Vec::new());
101        levels[0].push(vec![0; RADIX_ENTRIES].into_boxed_slice());
102
103        Self { levels }
104    }
105
106    fn insert(&mut self, guest_page: u64, page_index: usize) {
107        let vpn = guest_page >> 12;
108        let mut node = 0usize;
109
110        for level in 0..3 {
111            let shift = (3 - level) * RADIX_BITS;
112            let slot = ((vpn >> shift) & RADIX_MASK) as usize;
113            let entry = self.levels[level][node][slot];
114
115            node = if entry == 0 {
116                let next = self.levels[level + 1].len();
117
118                self.levels[level + 1].push(vec![0; RADIX_ENTRIES].into_boxed_slice());
119                self.levels[level][node][slot] = next + 1;
120
121                next
122            } else {
123                entry - 1
124            };
125        }
126
127        let slot = (vpn & RADIX_MASK) as usize;
128        self.levels[3][node][slot] = page_index + 1;
129    }
130
131    fn lookup(&self, guest_page: u64) -> Option<usize> {
132        let vpn = guest_page >> 12;
133        let mut node = 0usize;
134
135        for level in 0..3 {
136            let shift = (3 - level) * RADIX_BITS;
137            let slot = ((vpn >> shift) & RADIX_MASK) as usize;
138            let entry = self.levels[level][node][slot];
139
140            if entry == 0 {
141                return None;
142            }
143
144            node = entry - 1;
145        }
146
147        let entry = self.levels[3][node][(vpn & RADIX_MASK) as usize];
148        if entry == 0 { None } else { Some(entry - 1) }
149    }
150
151    fn rebuild(pages: &[VectorPage]) -> Self {
152        let mut table = Self::new();
153
154        for (page_index, page) in pages.iter().enumerate() {
155            table.insert(page.base, page_index);
156        }
157
158        table
159    }
160}
161
162#[derive(Default, Clone, Copy)]
163struct Translation {
164    guest_page: u64,
165    page_index: usize,
166    valid: bool,
167}
168
169pub(crate) struct VectorMemory {
170    exec_cache: [ExecCache; EXEC_CACHE_SLOTS],
171    baseline: u64,
172    pages: Vec<VectorPage>,
173    radix: RadixTable,
174    translations: [[Translation; TLB_ENTRIES]; LANES],
175
176    dirty_cells: Vec<usize>,
177    dirty_count: usize,
178    dirty_bitmap: Vec<u64>,
179    dirty_pages: Vec<usize>,
180    dirty_page_count: usize,
181    dirty_page_bitmap: Vec<u64>,
182}
183
184impl VectorMemory {
185    pub(crate) fn from_guest(memory: &GuestMemory) -> Self {
186        let mut pages = Vec::new();
187        let mut radix = RadixTable::new();
188
189        for (base, page_perms, bytes) in memory.mapped_pages() {
190            let mut data = vec![DataCell { lanes: [0; LANES] }; CELLS_PER_PAGE];
191            let byte_perms = BytePerms::from(page_perms).bits();
192
193            let perms = vec![PermCell { lanes: [byte_perms; LANES] }; PAGE_SIZE];
194
195            for (cell_index, chunk) in bytes.chunks(QWORD_SIZE).enumerate() {
196                let mut raw = [0u8; QWORD_SIZE];
197
198                raw[..chunk.len()].copy_from_slice(chunk);
199                data[cell_index].lanes.fill(u64::from_le_bytes(raw));
200            }
201
202            let page_index = pages.len();
203
204            radix.insert(base, page_index);
205            pages.push(VectorPage {
206                base,
207                present_mask: u8::MAX,
208                data: data.into_boxed_slice(),
209                perms: perms.into_boxed_slice(),
210            });
211        }
212
213        let page_count = pages.len();
214        let cell_count = page_count * CELLS_PER_PAGE;
215
216        Self {
217            baseline: 0,
218            exec_cache: [ExecCache::default(); EXEC_CACHE_SLOTS],
219            pages,
220            radix,
221            translations: [[Translation::default(); TLB_ENTRIES]; LANES], // todo !
222
223            dirty_cells: vec![0; cell_count],
224            dirty_count: 0,
225            dirty_bitmap: vec![0; cell_count.div_ceil(64)],
226            dirty_pages: vec![0; page_count],
227            dirty_page_count: 0,
228            dirty_page_bitmap: vec![0; page_count.div_ceil(64)],
229        }
230    }
231
232    pub(crate) fn as_opaque_mut(&mut self) -> *mut u8 {
233        std::ptr::from_mut(self).cast()
234    }
235
236    pub(crate) fn load_fn() -> LoadFn {
237        load_callback
238    }
239
240    pub(crate) fn store_fn() -> StoreFn {
241        store_callback
242    }
243
244    pub(crate) fn exec_cache_mut(&mut self) -> *mut ExecCache {
245        self.exec_cache.as_mut_ptr()
246    }
247
248    pub(crate) fn exec_fn() -> ExecFn {
249        exec_callback
250    }
251
252    pub(crate) fn snapshot(&mut self) -> MemorySnapshot {
253        static NEXT: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(1);
254        self.baseline = NEXT.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
255
256        self.clear_dirty();
257        MemorySnapshot { baseline: self.baseline, pages: self.pages.clone() }
258    }
259
260    // todo - refactor aug
261    pub(crate) fn restore(&mut self, snapshot: &MemorySnapshot) {
262        if self.baseline != snapshot.baseline {
263            self.pages = snapshot.pages.clone();
264            self.baseline = snapshot.baseline;
265            self.radix = RadixTable::rebuild(&self.pages);
266
267            self.clear_translations();
268            self.resize_dirty_metadata();
269            self.clear_dirty();
270
271            return;
272        }
273
274        let mapping_changed = self.dirty_page_count != 0 || self.pages.len() != snapshot.pages.len();
275
276        for slot in 0..self.dirty_page_count {
277            let page_index = self.dirty_pages[slot];
278
279            let Some(saved) = snapshot.pages.get(page_index) else {
280                continue;
281            };
282
283            self.pages[page_index] = saved.clone();
284        }
285
286        for slot in 0..self.dirty_count {
287            let dirty = self.dirty_cells[slot];
288            let page_index = dirty / CELLS_PER_PAGE;
289
290            if page_index >= snapshot.pages.len() || self.page_is_dirty(page_index) {
291                continue;
292            }
293
294            let cell_index = dirty % CELLS_PER_PAGE;
295            self.pages[page_index].data[cell_index] = snapshot.pages[page_index].data[cell_index].clone();
296
297            let byte_start = cell_index * QWORD_SIZE;
298            let byte_end = byte_start + QWORD_SIZE;
299
300            self.pages[page_index].perms[byte_start..byte_end]
301                .clone_from_slice(&snapshot.pages[page_index].perms[byte_start..byte_end]);
302        }
303
304        // dbg!(self.pages);
305
306        if mapping_changed {
307            self.pages.truncate(snapshot.pages.len());
308            self.radix = RadixTable::rebuild(&self.pages);
309
310            self.clear_translations();
311            self.resize_dirty_metadata();
312        }
313
314        self.clear_dirty();
315    }
316
317    pub(crate) fn can_write(&mut self, lane: usize, address: u64, size: usize) -> bool {
318        size as u64 <= jit::MAX_GUEST_MEMORY && self.check_access(lane, address, size, BytePerms::WRITE).is_ok()
319    }
320
321    // todo - unnötig
322    pub(crate) fn check_execute(&mut self, lane: usize, address: u64, size: usize) -> Result<(), u64> {
323        self.check_access(lane, address, size, BytePerms::EXEC)
324    }
325
326    pub(crate) fn load_guest_bytes(&mut self, lane: usize, address: u64, size: usize) -> Option<Vec<u8>> {
327        if size as u64 > jit::MAX_GUEST_MEMORY
328            || lane >= LANES
329            || self.check_access(lane, address, size, BytePerms::READ).is_err()
330        {
331            return None;
332        }
333
334        let mut bytes = Vec::new();
335        bytes.try_reserve_exact(size).ok()?;
336
337        for offset in 0..size {
338            let addr = address.checked_add(offset as u64)?;
339            bytes.push(self.read_lane_byte_raw(lane, addr)?);
340        }
341
342        Some(bytes)
343    }
344
345    pub(crate) fn load_guest_byte(&mut self, lane: usize, address: u64) -> Option<u8> {
346        if lane >= LANES || self.check_access(lane, address, 1, BytePerms::READ).is_err() {
347            return None;
348        }
349
350        self.read_lane_byte_raw(lane, address)
351    }
352
353    pub(crate) fn store_guest_bytes(&mut self, lane: usize, address: u64, bytes: &[u8]) -> bool {
354        if lane >= LANES || self.check_access(lane, address, bytes.len(), BytePerms::WRITE).is_err() {
355            return false;
356        }
357
358        for (offset, &byte) in bytes.iter().enumerate() {
359            let Some(addr) = address.checked_add(offset as u64) else {
360                return false;
361            };
362
363            if !self.write_lane_byte_raw(lane, addr, byte, true) {
364                return false;
365            }
366        }
367
368        true
369    }
370
371    pub(crate) fn map_zeroed_lane(&mut self, lane: usize, base: u64, size: u64, perms: BytePerms) -> bool {
372        if !self.can_map(base, size)
373            || lane >= LANES
374            || (perms.contains(BytePerms::WRITE) && perms.contains(BytePerms::EXEC))
375        {
376            return false;
377        }
378
379        if size == 0 {
380            return true;
381        }
382
383        let Some((start, end)) = covering_page_range(base, size) else {
384            return false;
385        };
386
387        let mut page_base = start;
388
389        while page_base < end {
390            if let Some(page_index) = self.page_index_for_lane(lane, page_base)
391                && self.pages[page_index].perms.iter().any(|byte| {
392                    let combined = BytePerms::from_bits(byte.lanes[lane] | perms.bits());
393                    combined.contains(BytePerms::WRITE) && combined.contains(BytePerms::EXEC)
394                })
395            {
396                return false;
397            }
398
399            page_base += PAGE_SIZE as u64;
400        }
401
402        let mut page_base = start;
403        while page_base < end {
404            self.map_page_zeroed(lane, page_base, perms);
405            page_base += PAGE_SIZE as u64;
406        }
407
408        self.clear_translations();
409        true
410    }
411
412    pub(crate) fn can_map(&self, base: u64, size: u64) -> bool {
413        let Some((start, end)) = covering_page_range(base, size) else {
414            return false;
415        };
416
417        let existing = self.pages.iter().filter(|p| p.base >= start && p.base < end).count() as u64;
418
419        self.pages.len() as u64 + (end - start) / PAGE_SIZE as u64 - existing
420            <= jit::MAX_GUEST_MEMORY / (4 * PAGE_SIZE as u64)
421    }
422
423    pub(crate) fn replace_mapping_lane(
424        &mut self,
425        lane: usize,
426        base: u64,
427        size: u64,
428        perms: BytePerms,
429        bytes: &[u8],
430    ) -> bool {
431        if lane >= LANES
432            || !self.can_map(base, size)
433            || page_range(base, size).is_none()
434            || (perms.contains(BytePerms::WRITE) && perms.contains(BytePerms::EXEC))
435        {
436            return false;
437        }
438
439        if !self.unmap_lane(lane, base, size) || !self.map_zeroed_lane(lane, base, size, perms) {
440            return false;
441        }
442
443        let count = bytes.len().min(usize::try_from(size).unwrap_or(usize::MAX));
444
445        for (offset, &byte) in bytes[..count].iter().enumerate() {
446            let address = base + offset as u64;
447
448            if !self.write_lane_byte_raw(lane, address, byte, false) {
449                return false;
450            }
451        }
452        true
453    }
454
455    pub(crate) fn protect_lane(&mut self, lane: usize, base: u64, size: u64, perms: BytePerms) -> bool {
456        let Some((start, end)) = page_range(base, size) else {
457            return false;
458        };
459
460        if lane >= LANES || (perms.contains(BytePerms::WRITE) && perms.contains(BytePerms::EXEC)) {
461            return false;
462        }
463
464        let mut page_indexes = Vec::new();
465        let mut page_base = start;
466
467        while page_base < end {
468            let Some(page_index) = self.page_index_for_lane(lane, page_base) else {
469                return false;
470            };
471
472            page_indexes.push(page_index);
473            page_base += PAGE_SIZE as u64;
474        }
475
476        for page_index in page_indexes {
477            if self.page_has_perms(page_index, lane, perms) {
478                continue;
479            }
480
481            self.mark_page_dirty(page_index);
482
483            for byte in self.pages[page_index].perms.iter_mut() {
484                byte.lanes[lane] = perms.bits();
485            }
486        }
487
488        self.clear_translations();
489        true
490    }
491
492    pub(crate) fn unmap_lane(&mut self, lane: usize, base: u64, size: u64) -> bool {
493        let Some((start, end)) = page_range(base, size) else {
494            return false;
495        };
496
497        if lane >= LANES {
498            return false;
499        }
500
501        for page_index in 0..self.pages.len() {
502            let page = &self.pages[page_index];
503
504            if page.base < start || page.base >= end || page.present_mask & (1 << lane) == 0 {
505                continue;
506            }
507
508            self.mark_page_dirty(page_index);
509            let page = &mut self.pages[page_index];
510
511            page.present_mask &= !(1 << lane);
512
513            for byte in page.perms.iter_mut() {
514                byte.lanes[lane] = BytePerms::empty().bits();
515            }
516        }
517
518        self.clear_translations();
519        true
520    }
521
522    pub(crate) fn range_is_free_lane(&self, lane: usize, base: u64, size: u64) -> bool {
523        let Some((start, end)) = page_range(base, size) else {
524            return false;
525        };
526
527        lane < LANES
528            && self
529                .pages
530                .iter()
531                .all(|page| page.present_mask & (1 << lane) == 0 || page.base < start || page.base >= end)
532    }
533
534    pub(crate) fn find_free_range_lane(&self, lane: usize, start: u64, size: u64) -> Option<u64> {
535        if lane >= LANES {
536            return None;
537        }
538
539        let size = align_up(size, PAGE_SIZE as u64)?;
540        let mut base = align_up(start, PAGE_SIZE as u64)?;
541
542        loop {
543            let end = base.checked_add(size)?;
544            let conflict = self
545                .pages
546                .iter()
547                .filter(|page| page.present_mask & (1 << lane) != 0)
548                .filter(|page| page.base >= base && page.base < end)
549                .map(|page| page.base)
550                .min();
551
552            let Some(conflict) = conflict else {
553                return Some(base);
554            };
555
556            base = conflict.checked_add(PAGE_SIZE as u64)?;
557        }
558    }
559
560    pub(crate) fn lane_page_bytes(&self, lane: usize, base: u64) -> Option<Vec<u8>> {
561        let page_index = self.page_index_for_lane(lane, base)?;
562        let mut bytes = Vec::with_capacity(PAGE_SIZE);
563
564        for cell in self.pages[page_index].data.iter() {
565            bytes.extend_from_slice(&cell.lanes[lane].to_le_bytes());
566        }
567
568        Some(bytes)
569    }
570
571    pub(crate) fn read_lane(&mut self, lane: usize, address: u64, bytes: &mut [u8]) -> bool {
572        if lane >= LANES {
573            return false;
574        }
575
576        for (offset, byte) in bytes.iter_mut().enumerate() {
577            let Some(addr) = address.checked_add(offset as u64) else {
578                return false;
579            };
580
581            let Some((page_index, page_offset)) = self.translate(lane, addr) else {
582                return false;
583            };
584
585            let cell = page_offset / QWORD_SIZE;
586            let shift = (page_offset % QWORD_SIZE) * 8;
587
588            *byte = (self.pages[page_index].data[cell].lanes[lane] >> shift) as u8;
589        }
590        true
591    }
592
593    pub(crate) fn write_lane_host(&mut self, lane: usize, address: u64, bytes: &[u8]) -> bool {
594        if lane >= LANES {
595            return false;
596        }
597
598        for offset in 0..bytes.len() {
599            let Some(addr) = address.checked_add(offset as u64) else {
600                return false;
601            };
602
603            let Some((page_index, page_offset)) = self.translate(lane, addr) else {
604                return false;
605            };
606
607            let perms = BytePerms::from_bits(self.pages[page_index].perms[page_offset].lanes[lane]);
608            if perms.contains(BytePerms::EXEC) {
609                return false;
610            }
611        }
612
613        for (offset, &byte) in bytes.iter().enumerate() {
614            let Some(addr) = address.checked_add(offset as u64) else {
615                return false;
616            };
617
618            let Some((page_index, page_offset)) = self.translate(lane, addr) else {
619                return false;
620            };
621
622            let cell = page_offset / QWORD_SIZE;
623            let shift = (page_offset % QWORD_SIZE) * 8;
624
625            self.mark_dirty(page_index, cell);
626
627            let value = &mut self.pages[page_index].data[cell].lanes[lane];
628            *value = (*value & !(0xffu64 << shift)) | ((byte as u64) << shift);
629        }
630        true
631    }
632
633    // todo - code duplication
634    pub(crate) fn set_permissions(&mut self, lane: usize, address: u64, size: usize, perms: BytePerms) -> bool {
635        if lane >= LANES {
636            return false;
637        }
638
639        for offset in 0..size {
640            let Some(addr) = address.checked_add(offset as u64) else {
641                return false;
642            };
643
644            if self.translate(lane, addr).is_none() {
645                return false;
646            }
647        }
648
649        for offset in 0..size {
650            let Some(addr) = address.checked_add(offset as u64) else {
651                return false;
652            };
653
654            let Some((page_index, page_offset)) = self.translate(lane, addr) else {
655                return false;
656            };
657
658            self.mark_dirty(page_index, page_offset / QWORD_SIZE);
659            self.pages[page_index].perms[page_offset].lanes[lane] = perms.bits();
660        }
661
662        self.clear_translations();
663        true
664    }
665
666    fn page_index_for_lane(&self, lane: usize, base: u64) -> Option<usize> {
667        if lane >= LANES || !base.is_multiple_of(PAGE_SIZE as u64) {
668            return None;
669        }
670
671        let page_index = self.radix.lookup(base)?;
672        let page = self.pages.get(page_index)?;
673
674        if page.base != base || page.present_mask & (1 << lane) == 0 {
675            return None;
676        }
677
678        Some(page_index)
679    }
680
681    fn read_lane_byte_raw(&self, lane: usize, address: u64) -> Option<u8> {
682        let page_base = align_down(address, PAGE_SIZE as u64);
683        let page_index = self.page_index_for_lane(lane, page_base)?;
684
685        let page_offset = (address - page_base) as usize;
686
687        let cell = page_offset / QWORD_SIZE;
688        let shift = (page_offset % QWORD_SIZE) * 8;
689
690        Some((self.pages[page_index].data[cell].lanes[lane] >> shift) as u8)
691    }
692
693    fn write_lane_byte_raw(&mut self, lane: usize, address: u64, byte: u8, make_readable: bool) -> bool {
694        let page_base = align_down(address, PAGE_SIZE as u64);
695
696        let Some(page_index) = self.page_index_for_lane(lane, page_base) else {
697            return false;
698        };
699
700        let page_offset = (address - page_base) as usize;
701
702        let cell = page_offset / QWORD_SIZE;
703        let shift = (page_offset % QWORD_SIZE) * 8;
704
705        self.mark_dirty(page_index, cell);
706
707        let page = &mut self.pages[page_index];
708        let value = &mut page.data[cell].lanes[lane];
709        *value = (*value & !(0xffu64 << shift)) | (u64::from(byte) << shift);
710
711        if make_readable && page.perms[page_offset].lanes[lane] & BytePerms::READ_AFTER_WRITE.bits() != 0 {
712            page.perms[page_offset].lanes[lane] |= BytePerms::READ.bits();
713        }
714        true
715    }
716
717    fn map_page_zeroed(&mut self, lane: usize, base: u64, perms: BytePerms) {
718        // dbg!(self.pages);
719
720        if let Some(page_index) = self.radix.lookup(base) {
721            if self.pages[page_index].present_mask & (1 << lane) == 0 {
722                self.mark_page_dirty(page_index);
723
724                let page = &mut self.pages[page_index];
725
726                for cell in page.data.iter_mut() {
727                    cell.lanes[lane] = 0;
728                }
729
730                for byte in page.perms.iter_mut() {
731                    byte.lanes[lane] = perms.bits();
732                }
733
734                page.present_mask |= 1 << lane;
735            } else if self.pages[page_index]
736                .perms
737                .iter()
738                .any(|byte| (byte.lanes[lane] | perms.bits()) != byte.lanes[lane])
739            {
740                self.mark_page_dirty(page_index);
741
742                for byte in self.pages[page_index].perms.iter_mut() {
743                    byte.lanes[lane] |= perms.bits();
744                }
745            }
746
747            return;
748        }
749
750        if let Some(page_index) = self.pages.iter().position(|page| page.present_mask == 0) {
751            self.mark_page_dirty(page_index);
752            let page = &mut self.pages[page_index];
753
754            page.base = base;
755            page.present_mask = 1 << lane;
756
757            for cell in page.data.iter_mut() {
758                cell.lanes.fill(0);
759            }
760
761            for byte in page.perms.iter_mut() {
762                byte.lanes.fill(BytePerms::empty().bits());
763                byte.lanes[lane] = perms.bits();
764            }
765
766            self.radix = RadixTable::rebuild(&self.pages);
767            return;
768        }
769
770        let mut perms_data = vec![PermCell { lanes: [0; LANES] }; PAGE_SIZE];
771        for byte in &mut perms_data {
772            byte.lanes[lane] = perms.bits();
773        }
774
775        let page_index = self.pages.len();
776
777        self.pages.push(VectorPage {
778            base,
779            present_mask: 1 << lane,
780            data: vec![DataCell { lanes: [0; LANES] }; CELLS_PER_PAGE].into_boxed_slice(),
781            perms: perms_data.into_boxed_slice(),
782        });
783
784        self.radix.insert(base, page_index);
785        self.resize_dirty_metadata();
786        self.mark_page_dirty(page_index);
787    }
788
789    fn page_has_perms(&self, page_index: usize, lane: usize, perms: BytePerms) -> bool {
790        self.pages[page_index].perms.iter().all(|byte| byte.lanes[lane] == perms.bits())
791    }
792
793    fn check_access(&mut self, lane: usize, address: u64, size: usize, required: BytePerms) -> Result<(), u64> {
794        let mut offset = 0;
795
796        while offset < size {
797            let addr = address.checked_add(offset as u64).ok_or(u64::MAX)?;
798            let (page_index, page_offset) = self.translate(lane, addr).ok_or(addr)?;
799            let count = (size - offset).min(PAGE_SIZE - page_offset);
800
801            if let Some(index) = self.pages[page_index].perms[page_offset..page_offset + count]
802                .iter()
803                .position(|byte| !BytePerms::from_bits(byte.lanes[lane]).contains(required))
804            {
805                return Err(addr + index as u64);
806            }
807
808            offset += count;
809        }
810        Ok(())
811    }
812
813    fn translate(&mut self, lane: usize, address: u64) -> Option<(usize, usize)> {
814        let guest_page = address & !((PAGE_SIZE as u64) - 1);
815        let slot = ((guest_page >> 12) as usize) & (TLB_ENTRIES - 1);
816        let cached = self.translations[lane][slot];
817
818        let page_index = if cached.valid && cached.guest_page == guest_page {
819            cached.page_index
820        } else {
821            let page_index = self.radix.lookup(guest_page)?;
822
823            self.translations[lane][slot] = Translation { guest_page, page_index, valid: true };
824
825            page_index
826        };
827
828        if self.pages[page_index].present_mask & (1 << lane) == 0 {
829            return None;
830        }
831
832        Some((page_index, (address - guest_page) as usize))
833    }
834
835    // todo - code dup
836
837    fn mark_dirty(&mut self, page_index: usize, cell_index: usize) {
838        if self.page_is_dirty(page_index) {
839            return;
840        }
841
842        let dirty = page_index * CELLS_PER_PAGE + cell_index;
843        let word = dirty / 64;
844        let bit = 1u64 << (dirty % 64);
845
846        if self.dirty_bitmap[word] & bit == 0 {
847            self.dirty_bitmap[word] |= bit;
848            self.dirty_cells[self.dirty_count] = dirty;
849            self.dirty_count += 1;
850        }
851    }
852
853    fn mark_page_dirty(&mut self, page_index: usize) {
854        let word = page_index / 64;
855        let bit = 1u64 << (page_index % 64);
856
857        if self.dirty_page_bitmap[word] & bit == 0 {
858            self.dirty_page_bitmap[word] |= bit;
859            self.dirty_pages[self.dirty_page_count] = page_index;
860            self.dirty_page_count += 1;
861        }
862    }
863
864    fn page_is_dirty(&self, page_index: usize) -> bool {
865        self.dirty_page_bitmap.get(page_index / 64).is_some_and(|word| word & (1u64 << (page_index % 64)) != 0)
866    }
867
868    fn resize_dirty_metadata(&mut self) {
869        let cell_count = self.pages.len() * CELLS_PER_PAGE;
870
871        self.dirty_cells.resize(cell_count, 0);
872        self.dirty_bitmap.resize(cell_count.div_ceil(64), 0);
873        self.dirty_pages.resize(self.pages.len(), 0);
874        self.dirty_page_bitmap.resize(self.pages.len().div_ceil(64), 0);
875    }
876
877    fn clear_dirty(&mut self) {
878        dbg!("clear dirty!!");
879
880        self.dirty_count = 0;
881        self.dirty_bitmap.fill(0);
882        self.dirty_page_count = 0;
883        self.dirty_page_bitmap.fill(0);
884        self.exec_cache.fill(ExecCache::default());
885    }
886
887    fn clear_translations(&mut self) {
888        self.exec_cache.fill(ExecCache::default());
889        self.translations = [[Translation::default(); TLB_ENTRIES]; LANES];
890    }
891}
892
893fn align_down(value: u64, align: u64) -> u64 {
894    value & !(align - 1)
895}
896
897fn align_up(value: u64, align: u64) -> Option<u64> {
898    if value == 0 { Some(0) } else { value.checked_add(align - 1).map(|value| value & !(align - 1)) }
899}
900
901fn covering_page_range(base: u64, size: u64) -> Option<(u64, u64)> {
902    if size == 0 {
903        return None;
904    }
905
906    let start = align_down(base, PAGE_SIZE as u64);
907    let end = align_up(base.checked_add(size)?, PAGE_SIZE as u64)?;
908
909    Some((start, end))
910}
911
912fn page_range(base: u64, size: u64) -> Option<(u64, u64)> {
913    if size == 0 || !base.is_multiple_of(PAGE_SIZE as u64) {
914        return None;
915    }
916
917    Some((base, align_up(base.checked_add(size)?, PAGE_SIZE as u64)?))
918}