blob: 71b5f79fd425a130eb2f7cdc2b7eac07f7f04feb [file]
// Copyright 2023 The Fuchsia Authors
//
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
// https://opensource.org/licenses/MIT
use crate::kernel::types::{PAddr, VAddr};
/// Helper that tracks a virtual address range for performing MMU operations. This can be used
/// directly, or as part of a [`MappingCursor`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct VirtualAddressCursor {
/// Initial starting virtual address of the cursor.
start_vaddr: VAddr,
/// Current virtual address of the cursor.
vaddr: VAddr,
/// Offset subtracted when computing [`Self::vaddr_rel`].
vaddr_rel_offset: VAddr,
/// Remaining size in bytes to process.
size: usize,
}
impl VirtualAddressCursor {
/// Creates a new cursor for the virtual address range `[vaddr, vaddr + size)`.
#[inline]
pub const fn new(vaddr: VAddr, size: usize) -> Self {
Self { start_vaddr: vaddr, vaddr, vaddr_rel_offset: VAddr(0), size }
}
/// Sets offset used for `vaddr_rel` and returns true if the cursor lies within that offset and
/// some specified maximum. Should only be called before the cursor has started to be used.
#[must_use]
#[inline]
pub fn set_vaddr_relative_offset(
&mut self,
vaddr_rel_offset: VAddr,
vaddr_rel_max: usize,
) -> bool {
debug_assert!(self.start_vaddr == self.vaddr);
let vaddr_rel = VAddr(self.start_vaddr.0.wrapping_sub(vaddr_rel_offset.0));
if vaddr_rel.0 > vaddr_rel_max.wrapping_sub(self.size) || self.size > vaddr_rel_max {
return false;
}
self.vaddr_rel_offset = vaddr_rel_offset;
true
}
/// Update the cursor to skip over a not-present page table entry.
#[inline]
pub fn skip_entry(&mut self, ps: usize) {
// Cannot just increase by given size as both the current or final vaddr may not be aligned
// to this given size. These cases only happen as the very first or very last entry we will
// examine respectively, but still must be handled here.
// Calculate the amount the cursor should skip to get to the next entry at
// this page table level.
let next_entry_offset = ps.wrapping_sub(self.vaddr.0 & ps.wrapping_sub(1));
// If our endpoint was in the middle of this range, clamp the
// amount we remove from the cursor
let consume = if self.size > next_entry_offset { next_entry_offset } else { self.size };
debug_assert!(self.size >= consume);
self.size -= consume;
self.vaddr = VAddr(self.vaddr.0.wrapping_add(consume));
}
/// Consumes `ps` bytes from the cursor.
#[inline]
pub fn consume(&mut self, ps: usize) {
debug_assert!(self.size >= ps);
self.vaddr = VAddr(self.vaddr.0.wrapping_add(ps));
self.size -= ps;
}
/// Returns a new cursor to the, possibly empty, virtual range that has already been processed
/// by this cursor. The returned cursor will always be a subset of the original cursor's range.
#[must_use]
#[inline]
pub const fn processed_range(&self) -> VirtualAddressCursor {
let mut ret = VirtualAddressCursor::new(
self.start_vaddr,
self.vaddr.0.wrapping_sub(self.start_vaddr.0),
);
// As our new cursor is a subrange we know the relative offset will always be valid.
ret.vaddr_rel_offset = self.vaddr_rel_offset;
ret
}
/// Returns the current virtual address.
#[inline]
pub const fn vaddr(&self) -> VAddr {
self.vaddr
}
/// Returns the current virtual address relative to the configured offset.
#[inline]
pub const fn vaddr_rel(&self) -> VAddr {
VAddr(self.vaddr.0.wrapping_sub(self.vaddr_rel_offset.0))
}
/// Returns the remaining size in bytes.
#[inline]
pub const fn size(&self) -> usize {
self.size
}
}
/// Helper class for MMU implementations to track physical address ranges when installing mappings.
/// If just processing a virtual address range, such as for unmapping, then the
/// [`VirtualAddressCursor`] can be used instead.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct MappingCursor<'a> {
/// Remaining physical addresses to map.
paddrs: &'a [PAddr],
/// Bytes consumed within the current `page_size` physical region.
paddr_consumed: usize,
/// Size in bytes of each physical region in `paddrs`.
page_size: usize,
/// Underlying virtual address range cursor.
vaddr_cursor: VirtualAddressCursor,
}
impl<'a> MappingCursor<'a> {
/// Creates a new mapping cursor over `paddrs`, where each entry covers `page_size` bytes
/// starting at `vaddr`.
#[inline]
pub const fn new(paddrs: &'a [PAddr], page_size: usize, vaddr: VAddr) -> Self {
Self {
paddrs,
paddr_consumed: 0,
page_size,
vaddr_cursor: VirtualAddressCursor::new(vaddr, page_size.saturating_mul(paddrs.len())),
}
}
/// See [`VirtualAddressCursor::set_vaddr_relative_offset`].
#[must_use]
#[inline]
pub fn set_vaddr_relative_offset(
&mut self,
vaddr_rel_offset: VAddr,
vaddr_rel_max: usize,
) -> bool {
self.vaddr_cursor.set_vaddr_relative_offset(vaddr_rel_offset, vaddr_rel_max)
}
/// Consumes `ps` bytes from both the physical and virtual ranges.
#[inline]
pub fn consume(&mut self, ps: usize) {
self.paddr_consumed = self.paddr_consumed.wrapping_add(ps);
debug_assert!(self.paddr_consumed <= self.page_size);
if self.paddr_consumed == self.page_size {
debug_assert!(!self.paddrs.is_empty());
self.paddrs = &self.paddrs[1..];
self.paddr_consumed = 0;
}
self.vaddr_cursor.consume(ps);
}
/// Returns the current physical address.
#[inline]
pub const fn paddr(&self) -> PAddr {
debug_assert!(self.paddr_consumed < self.page_size);
debug_assert!(!self.paddrs.is_empty());
PAddr(self.paddrs[0].0.wrapping_add(self.paddr_consumed))
}
/// Returns the remaining unconsumed bytes in the current physical page entry.
#[inline]
pub const fn page_remaining(&self) -> usize {
self.page_size.wrapping_sub(self.paddr_consumed)
}
/// Returns a new cursor to the, possibly empty, virtual range that has already been processed
/// by this cursor. The returned cursor will always be a subset of the original cursor's range
/// and does not include the `paddrs`.
#[must_use]
#[inline]
pub const fn processed_range(&self) -> VirtualAddressCursor {
self.vaddr_cursor.processed_range()
}
/// Returns the current virtual address.
#[inline]
pub const fn vaddr(&self) -> VAddr {
self.vaddr_cursor.vaddr()
}
/// Returns the current virtual address relative to the configured offset.
#[inline]
pub const fn vaddr_rel(&self) -> VAddr {
self.vaddr_cursor.vaddr_rel()
}
/// Returns the remaining size in bytes.
#[inline]
pub const fn size(&self) -> usize {
self.vaddr_cursor.size()
}
}
/// Unit tests for [`VirtualAddressCursor`] and [`MappingCursor`].
#[cfg(ktest)]
#[unittest::suite(name = "mapping_cursor")]
mod tests {
use super::{MappingCursor, VirtualAddressCursor};
use crate::kernel::types::{PAddr, VAddr};
use unittest::{expect_eq, expect_false, expect_true};
const PAGE_SIZE: usize = page::SIZE;
const LARGE_PAGE_SIZE: usize = 512 * PAGE_SIZE;
/// Verifies relative offset bounds checking and top-of-address-space wrapping arithmetic.
#[test]
fn virtual_address_cursor_relative_offset() {
let offset = VAddr(0xffff_0000_0000_0000);
let max_size: usize = 1usize << 48;
// Below offset wraps to a large relative address and must be rejected.
let mut below = VirtualAddressCursor::new(VAddr(0x1000), PAGE_SIZE);
expect_false!(below.set_vaddr_relative_offset(offset, max_size));
expect_eq!(below.vaddr_rel().0, 0x1000);
// Size larger than max_size must be rejected without underflow panic.
let mut oversized = VirtualAddressCursor::new(offset, max_size + PAGE_SIZE);
expect_false!(oversized.set_vaddr_relative_offset(offset, max_size));
// Range extending past offset + max_size must be rejected.
let mut past_end =
VirtualAddressCursor::new(VAddr(usize::MAX - PAGE_SIZE + 1), 2 * PAGE_SIZE);
expect_false!(past_end.set_vaddr_relative_offset(offset, max_size));
// Range ending at the top of the 64-bit address space (wrapping end to 0) is valid.
let top_start = VAddr(0usize.wrapping_sub(2 * PAGE_SIZE));
let mut top = VirtualAddressCursor::new(top_start, 2 * PAGE_SIZE);
expect_true!(top.set_vaddr_relative_offset(offset, max_size));
expect_eq!(top.vaddr_rel().0, max_size - 2 * PAGE_SIZE);
top.consume(PAGE_SIZE);
expect_eq!(top.vaddr().0, 0usize.wrapping_sub(PAGE_SIZE));
expect_eq!(top.vaddr_rel().0, max_size - PAGE_SIZE);
top.consume(PAGE_SIZE);
expect_eq!(top.vaddr().0, 0);
expect_eq!(top.size(), 0);
let processed = top.processed_range();
expect_eq!(processed.vaddr().0, top_start.0);
expect_eq!(processed.vaddr_rel().0, max_size - 2 * PAGE_SIZE);
expect_eq!(processed.size(), 2 * PAGE_SIZE);
}
/// Verifies `skip_entry`, `consume`, and `processed_range` across unaligned start/end ranges.
#[test]
fn virtual_address_cursor_skip_and_consume() {
let start = VAddr(0x1000_0000 + PAGE_SIZE);
let total = 2 * LARGE_PAGE_SIZE + 2 * PAGE_SIZE;
let mut cursor = VirtualAddressCursor::new(start, total);
expect_true!(cursor.set_vaddr_relative_offset(VAddr(0x1000_0000), 1usize << 30));
expect_eq!(cursor.processed_range().size(), 0);
// Unaligned start: skips only up to the next `LARGE_PAGE_SIZE` boundary.
cursor.skip_entry(LARGE_PAGE_SIZE);
expect_eq!(cursor.vaddr().0, 0x1000_0000 + LARGE_PAGE_SIZE);
expect_eq!(cursor.size(), LARGE_PAGE_SIZE + 3 * PAGE_SIZE);
// Aligned middle entry: consumes an entire `LARGE_PAGE_SIZE` block.
cursor.consume(LARGE_PAGE_SIZE);
expect_eq!(cursor.vaddr().0, 0x1000_0000 + 2 * LARGE_PAGE_SIZE);
expect_eq!(cursor.size(), 3 * PAGE_SIZE);
let partial = cursor.processed_range();
expect_eq!(partial.vaddr().0, start.0);
expect_eq!(partial.vaddr_rel().0, PAGE_SIZE);
expect_eq!(partial.size(), total - 3 * PAGE_SIZE);
// Unaligned end: clamps to the remaining 3 pages rather than overshooting.
cursor.skip_entry(LARGE_PAGE_SIZE);
expect_eq!(cursor.vaddr().0, start.0 + total);
expect_eq!(cursor.size(), 0);
}
/// Verifies `MappingCursor` sub-page consumption, physical array advancement, and rollback.
#[test]
fn mapping_cursor_consume_and_processed_range() {
let empty = MappingCursor::new(&[], PAGE_SIZE, VAddr(0x2000));
expect_eq!(empty.size(), 0);
expect_eq!(empty.processed_range().size(), 0);
let paddrs = [PAddr(0x4000_0000), PAddr(0x8000_0000)];
let base = VAddr(0x1000_0000);
// Overflowing `page_size * paddrs.len()` saturates to `usize::MAX` and is rejected by
// `set_vaddr_relative_offset`.
let mut overflow = MappingCursor::new(&paddrs, 1usize << 63, base);
expect_eq!(overflow.size(), usize::MAX);
expect_false!(overflow.set_vaddr_relative_offset(base, 1usize << 48));
let mut cursor = MappingCursor::new(&paddrs, 2 * PAGE_SIZE, VAddr(base.0 + 0x4000));
expect_true!(cursor.set_vaddr_relative_offset(base, 0x20000));
expect_eq!(cursor.size(), 4 * PAGE_SIZE);
expect_eq!(cursor.paddr().0, 0x4000_0000);
expect_eq!(cursor.page_remaining(), 2 * PAGE_SIZE);
expect_eq!(cursor.vaddr_rel().0, 0x4000);
// Consume half of the first `2 * PAGE_SIZE` entry.
cursor.consume(PAGE_SIZE);
expect_eq!(cursor.paddr().0, 0x4000_0000 + PAGE_SIZE);
expect_eq!(cursor.page_remaining(), PAGE_SIZE);
expect_eq!(cursor.vaddr().0, base.0 + 0x4000 + PAGE_SIZE);
expect_eq!(cursor.size(), 3 * PAGE_SIZE);
// Finish the first entry and advance to the second physical entry.
cursor.consume(PAGE_SIZE);
expect_eq!(cursor.paddr().0, 0x8000_0000);
expect_eq!(cursor.page_remaining(), 2 * PAGE_SIZE);
expect_eq!(cursor.size(), 2 * PAGE_SIZE);
let processed = cursor.processed_range();
expect_eq!(processed.vaddr().0, base.0 + 0x4000);
expect_eq!(processed.vaddr_rel().0, 0x4000);
expect_eq!(processed.size(), 2 * PAGE_SIZE);
// Consume the entire second entry at once.
cursor.consume(2 * PAGE_SIZE);
expect_eq!(cursor.size(), 0);
expect_eq!(cursor.page_remaining(), 2 * PAGE_SIZE);
}
}