frame_alloc/

allocator.rs

use crate::page_size::PageSize;
use core::num::NonZeroUsize;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AllocError {
    /// No free memory is available to satisfy the request.
    OutOfMemory,
    /// The requested `PageSize` is not managed by this allocator.
    InvalidPageSize,
    /// The request is too large for the allocator's configuration.
    RequestTooLarge,
}

/// Structured failure reason for [`RegionInit::try_init`](RegionInit::try_init).
///
/// These describe the *checkable* preconditions of initialisation. The remaining
/// unverifiable preconditions live in the `# Safety` contract instead.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum InitError {
    /// init already completed successfully.
    AlreadyInitialized,
    /// `phys_base` fails the implementation's alignment requirement.
    Misaligned {
        /// The alignment, in bytes, that was required but not met.
        required: usize,
    },
    /// `span_len` is zero, not a base-frame multiple, or overflows the address space.
    InvalidSpan,
    /// `usable[index]` is empty, misaligned, out of order, overlapping, or escapes
    /// the span.
    InvalidUsable {
        /// Index of the offending range in the `usable` slice.
        index: usize,
    },
    /// No usable range is large enough to host the allocator's metadata.
    MetadataWontFit {
        /// Number of contiguous bytes a single usable range would need.
        required_bytes: usize,
    },
    /// (regioned only) span overlaps the already-initialised region `other`.
    OverlapsRegion {
        /// Index of the already-initialised region the span collides with.
        other: usize,
    },
}

impl core::fmt::Display for InitError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            InitError::AlreadyInitialized => write!(f, "allocator already initialised"),
            InitError::Misaligned { required } => {
                write!(f, "base misaligned: requires alignment {required:#x}")
            }
            InitError::InvalidSpan => write!(
                f,
                "invalid span: zero, not a base-frame multiple, or overflows the address space"
            ),
            InitError::InvalidUsable { index } => {
                write!(f, "invalid usable range at index {index}")
            }
            InitError::MetadataWontFit { required_bytes } => write!(
                f,
                "metadata won't fit: no usable range holds {required_bytes} contiguous bytes"
            ),
            InitError::OverlapsRegion { other } => {
                write!(f, "span overlaps already-initialised region {other}")
            }
        }
    }
}

/// Trait for physical frame allocators.
///
/// # Contract guarantees
///
/// [`allocate_physical`](Self::allocate_physical) is a safe method whose returned
/// address may later be passed to unsafe deallocation paths. Implementors must
/// guarantee that every successful allocation:
///
/// * returns the base of `count` contiguous frames of size `ps`;
/// * returns a base address aligned to `ps.bytes()`;
/// * represents the whole byte range `[base, base + count * ps.bytes())` without
///   arithmetic overflow;
/// * transfers exclusive ownership of that range to the caller until it is
///   returned with [`deallocate_physical`](Self::deallocate_physical); and
/// * never returns a range that overlaps any still-live allocation.
///
/// On `Err`, the allocator must not transfer ownership of any frame.
///
/// # Safety
///
/// This is an unsafe trait because safe callers and generic wrappers may rely on
/// successful allocations being real, unique physical frames. Implementors must
/// ensure that every successful allocation is backed by physical memory managed
/// by this allocator and exclusively owned until deallocation.
///
/// # Errors
///
/// Unsupported page sizes, unrepresentable requests, requests too large for the
/// allocator's configuration, and exhausted memory must be reported with
/// [`AllocError`] rather than by returning an address that violates the contract.
pub unsafe trait PhysicalAllocator {
    /// Allocate `count` contiguous frames of size `ps`.
    ///
    /// Returns the **physical** base address on success. When called on an
    /// uninitialised allocator it returns [`AllocError::OutOfMemory`].
    ///
    /// # Errors
    ///
    /// See the trait-level `# Errors` documentation.
    fn allocate_physical(&self, ps: PageSize, count: NonZeroUsize) -> Result<usize, AllocError>;

    /// Return `count` contiguous frames of size `ps` starting at `phys`.
    ///
    /// # Safety
    ///
    /// `phys` must be the address previously returned by `allocate_physical`
    ///  with the same `ps` and `count`, and must not be used after this call.
    unsafe fn deallocate_physical(&self, ps: PageSize, count: NonZeroUsize, phys: usize);
}

/// A physically-contiguous, base-frame-aligned range of usable RAM.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PhysRange {
    /// Physical base address. Must be aligned to the allocator's base frame size.
    pub base: usize,
    /// Length in bytes. Must be a non-zero multiple of the base frame size.
    pub len: usize,
}

/// Memory-map-aware initialisation interface for physical frame allocators.
///
/// [`try_init`](RegionInit::try_init) configures the allocator's metadata over the
/// whole *span* and frees only the `usable` ranges; holes between them stay
/// reserved (never handed out).
///
/// # Contract guarantees
///
/// * **On `Err`, the allocator is untouched** - it remains in the valid empty
///   state it had before the call, and a corrected retry is permitted.
/// * **At most one successful call.** A returned `Ok(())` consumes the one-time
///   initialisation; a returned `Err(_)` does not, so a caller may retry with
///   corrected arguments after any failure.
///
/// # Safety
///
/// These preconditions are unverifiable from the arguments and so remain the
/// caller's responsibility (violating any of them is undefined behaviour, not an
/// [`InitError`]):
///
/// * Backends reach the managed memory through a [`Provenance`](crate::Provenance)
///   strategy of their own, obtaining pointers for the physical addresses they
///   are given; the caller supplies no mapping pointer. Each backend's `Provenance`
///   `# Safety` contract states what it requires of that mapping.
/// * Each `usable` range's memory must be exclusively owned and not aliased while
///   registered.
/// * Must be called single-threaded, and the allocator must be published to
///   other threads with a happens-before edge (thread spawn, mutex, or a
///   Release store / Acquire load of a ready flag) before any concurrent use.
///
/// # Errors
///
/// The *checkable* preconditions are reported rather than assumed. See
/// [`InitError`] for the full list; in summary `try_init` returns:
///
/// * [`InitError::AlreadyInitialized`] if a previous call already succeeded;
/// * [`InitError::Misaligned`] if `phys_base` is not base-frame aligned (it need
///   not itself be usable RAM);
/// * [`InitError::InvalidSpan`] if `span_len` is zero, not a base-frame multiple,
///   or overflows the address space;
/// * [`InitError::InvalidUsable`] if any `usable` range is empty, misaligned, out
///   of order, overlapping, or escapes the span;
/// * [`InitError::MetadataWontFit`] if no usable range can host the allocator's
///   in-pool metadata.
///
/// An empty `usable` slice is permitted by this interface, but some
/// implementations may reject it with [`InitError::MetadataWontFit`]: an allocator
/// that keeps its metadata inside the managed pool needs enough usable RAM to host
/// that metadata.
pub unsafe trait RegionInit {
    /// Configure metadata over `[phys_base, phys_base + span_len)` and mark only
    /// the `usable` ranges free. Holes stay reserved.
    ///
    /// On success the one-time initialisation is consumed; on failure the
    /// allocator is untouched and the call may be retried. See the trait-level
    /// documentation for the full contract, the `# Errors` conditions, and the
    /// `# Safety` preconditions.
    ///
    /// # Errors
    ///
    /// See the trait-level `# Errors` documentation.
    ///
    /// # Safety
    ///
    /// See the trait-level safety documentation.
    unsafe fn try_init(
        &self,
        phys_base: usize,
        span_len: usize,
        usable: &[PhysRange],
    ) -> Result<(), InitError>;

    /// Transition a reserved (never-freed) in-span range to free. Repeatable
    /// after [`try_init`](RegionInit::try_init). `base`/`len` must satisfy the same
    /// per-range constraints as a `usable` entry.
    ///
    /// # Safety
    ///
    /// `try_init` must have succeeded first. `[base, base + len)` must be
    /// base-frame aligned, lie within the span, be currently reserved (not already
    /// free), exclusively owned, and not aliased while registered.
    unsafe fn add_usable(&self, base: usize, len: usize);

    /// As [`try_init`](RegionInit::try_init) but panic on error.
    ///
    /// # Safety
    ///
    /// See the trait-level safety documentation.
    ///
    /// # Panics
    ///
    /// Panics if [`try_init`](RegionInit::try_init) returns an [`InitError`].
    unsafe fn init(&self, phys_base: usize, span_len: usize, usable: &[PhysRange]) {
        // SAFETY: forwarded under the caller's trait-level guarantees.
        match unsafe { self.try_init(phys_base, span_len, usable) } {
            Ok(()) => {}
            Err(e) => panic!("RegionInit::init failed: {e:?}"),
        }
    }

    /// Convenience: initialise from a single fully-usable contiguous
    /// region `[phys_base, phys_base + len)`.
    ///
    /// # Errors
    ///
    /// See the trait-level `# Errors` documentation.
    ///
    /// # Safety
    ///
    /// See the trait-level safety documentation; the whole region is `usable`.
    unsafe fn try_init_region(&self, phys_base: usize, len: usize) -> Result<(), InitError> {
        let all = [PhysRange {
            base: phys_base,
            len,
        }];
        // SAFETY: forwarded under the caller's trait-level guarantees; the single
        // range covers the whole span and trivially satisfies the slice preconditions.
        unsafe { self.try_init(phys_base, len, &all) }
    }

    /// As [`try_init_region`](RegionInit::try_init_region) but panic on error.
    ///
    /// # Safety
    ///
    /// See the trait-level safety documentation; the whole region is `usable`.
    ///
    /// # Panics
    ///
    /// Panics if initialisation returns an [`InitError`].
    unsafe fn init_region(&self, phys_base: usize, len: usize) {
        let all = [PhysRange {
            base: phys_base,
            len,
        }];
        // SAFETY: forwarded under the caller's trait-level guarantees; the single
        // range covers the whole span and trivially satisfies the slice preconditions.
        unsafe { self.init(phys_base, len, &all) };
    }
}

/// All three figures are in **bytes**. They are diagnostics - utilisation
/// reporting, fragmentation tracking, tests - not a basis for allocation
/// decisions: each is **non-linearizable** under concurrent use, so a value may be
/// stale the instant it is returned. Gated behind the `stats` feature.
#[cfg(any(feature = "stats", test))]
pub trait AllocatorStats {
    /// Total managed capacity in bytes - what the allocator can hand out when
    /// fully free. Counts usable frames only; excludes any metadata the allocator
    /// reserves inside its own pool.
    fn total_bytes(&self) -> usize;

    /// Currently-free bytes.
    fn free_bytes(&self) -> usize;

    /// Largest single allocation, in bytes, that can currently succeed.
    fn largest_free_bytes(&self) -> usize;
}