solana_sbpf/

memory_region.rs

//! This module defines memory regions

use crate::{
    aligned_memory::Pod,
    ebpf,
    error::{EbpfError, ProgramResult},
    program::SBPFVersion,
    vm::Config,
};
use std::fmt::Formatter;
use std::{array, cell::UnsafeCell, fmt, mem, ops::Range, ptr};

/* Explanation of the Gapped Memory

    The MemoryMapping supports a special mapping mode which is used for the stack MemoryRegion.
    In this mode the backing address space of the host is sliced in power-of-two aligned frames.
    The exponent of this alignment is specified in vm_gap_shift. Then the virtual address space
    of the guest is spread out in a way which leaves gaps, the same size as the frames, in
    between the frames. This effectively doubles the size of the guests virtual address space.
    But the actual mapped memory stays the same, as the gaps are not mapped and accessing them
    results in an AccessViolation.

    Guest: frame 0 | gap 0 | frame 1 | gap 1 | frame 2 | gap 2 | ...
              |                /                 /
              |          *----*    *------------*
              |         /         /
    Host:  frame 0 | frame 1 | frame 2 | ...
*/

/// Callback executed before generate_access_violation()
pub type AccessViolationHandler = Box<dyn Fn(&mut MemoryRegion, u64, AccessType, u64, u64)>;
/// Fail always
#[allow(clippy::result_unit_err)]
pub fn default_access_violation_handler(
    _region: &mut MemoryRegion,
    _region_max_len: u64,
    _access_type: AccessType,
    _vm_addr: u64,
    _len: u64,
) {
}

/// Types that can be used as backing memory for memory mappings.
///
/// ## Safety
///
/// The implementers must ensure that the returned address and byte length are contained by the
/// implementing type's objects.
pub unsafe trait HostMemoryObject {
    /// Should the mapping region constructed by this object be considered writable?
    const WRITABLE: bool;

    /// The provenance-exposed address in the host address space for this object.
    ///
    /// Normally this is just an address of the pointer.
    fn host_address(self) -> usize;
    /// Number of contiguous bytes this object occupies.
    fn byte_length(&self) -> usize;
}

/// Types that can be directly mapped into VM memory space should implement this trait.
///
/// The blanket implementations of [`HostMemoryObject`] for `*const T` where `T: VmExposable` allow
/// exposing the implementing types to the guests directly.
pub trait VmExposable {}

/// Types that can be directly and mutably mapped into VM memory space.
///
/// The blanket implementations of [`HostMemoryObject`] for `*mut T` where `T: VmExposableMut` allow
/// mutably exposing the implementing types to the guests directly.
///
/// ## Safety
///
/// The type must not have any invariants that could be broken by the guest's modifications to the
/// data within objects of this type.
pub unsafe trait VmExposableMut {}

unsafe impl VmExposableMut for u8 {}
impl<T: VmExposableMut> VmExposable for T {}

unsafe impl<T: VmExposable> HostMemoryObject for *const T {
    const WRITABLE: bool = false;
    fn host_address(self) -> usize {
        self.expose_provenance()
    }
    fn byte_length(&self) -> usize {
        std::mem::size_of::<T>()
    }
}

unsafe impl<T: VmExposableMut> HostMemoryObject for *mut T {
    const WRITABLE: bool = true;
    fn host_address(self) -> usize {
        self.expose_provenance()
    }
    fn byte_length(&self) -> usize {
        std::mem::size_of::<T>()
    }
}

unsafe impl<T: VmExposable> HostMemoryObject for *const [T] {
    const WRITABLE: bool = false;
    fn host_address(self) -> usize {
        self.expose_provenance()
    }
    fn byte_length(&self) -> usize {
        self.len().checked_mul(core::mem::size_of::<T>()).unwrap()
    }
}

unsafe impl<T: VmExposableMut> HostMemoryObject for *mut [T] {
    const WRITABLE: bool = true;
    fn host_address(self) -> usize {
        self.expose_provenance()
    }
    fn byte_length(&self) -> usize {
        self.len().checked_mul(core::mem::size_of::<T>()).unwrap()
    }
}

unsafe impl<T: VmExposable, const N: usize> HostMemoryObject for *const [T; N] {
    const WRITABLE: bool = false;
    fn host_address(self) -> usize {
        self.expose_provenance()
    }
    fn byte_length(&self) -> usize {
        N.checked_mul(core::mem::size_of::<T>()).unwrap()
    }
}

unsafe impl<T: VmExposableMut, const N: usize> HostMemoryObject for *mut [T; N] {
    const WRITABLE: bool = true;
    fn host_address(self) -> usize {
        self.expose_provenance()
    }
    fn byte_length(&self) -> usize {
        N.checked_mul(core::mem::size_of::<T>()).unwrap()
    }
}

/// Memory region for bounds checking and address translation
#[derive(Default, Eq, PartialEq, Clone)]
#[repr(C, align(32))]
pub struct MemoryRegion {
    /// start host address
    pub host_addr: u64,
    /// start virtual address
    pub vm_addr: u64,
    /// Length in bytes
    pub len: u64,
    /// Size of regular gaps as bit shift (63 means this region is continuous)
    pub vm_gap_shift: u8,
    /// Is `AccessType::Store` allowed without triggering an access violation
    pub writable: bool,
    /// User defined payload for the [AccessViolationHandler]
    pub access_violation_handler_payload: Option<u16>,
}

impl MemoryRegion {
    /// Create a VM memory region with host `address` pointing to a `len` bytes of data.
    ///
    /// This region will be made available in the guest at `vm_addr`.
    fn new_internal(
        address: usize,
        len: usize,
        vm_addr: u64,
        vm_gap_size: u64,
        writable: bool,
    ) -> Self {
        let mut vm_gap_shift = (std::mem::size_of::<u64>() as u8)
            .saturating_mul(8)
            .saturating_sub(1);
        if vm_gap_size > 0 {
            vm_gap_shift = vm_gap_shift.saturating_sub(vm_gap_size.leading_zeros() as u8);
            debug_assert_eq!(Some(vm_gap_size), 1_u64.checked_shl(vm_gap_shift as u32));
        };
        MemoryRegion {
            host_addr: address as u64,
            vm_addr,
            len: len as u64,
            vm_gap_shift,
            writable,
            access_violation_handler_payload: None,
        }
    }

    /// Creates a new `MemoryRegion` backed by the provided host memory.
    ///
    /// The backing memory must remain allocated for the duration of the returned `MemoryRegion`.
    pub fn new<HO: HostMemoryObject>(host: HO, vm_addr: u64) -> Self {
        let bytes = host.byte_length();
        Self::new_internal(host.host_address(), bytes, vm_addr, 0, HO::WRITABLE)
    }

    /// Creates a new gapped `MemoryRegion` backed by the provided host memory.
    ///
    /// The backing memory must remain allocated for the duration of the returned `MemoryRegion`.
    pub fn new_gapped<HO: HostMemoryObject>(host: HO, vm_addr: u64, vm_gap_size: u64) -> Self {
        let bytes = host.byte_length();
        let host_address = host.host_address();
        Self::new_internal(host_address, bytes, vm_addr, vm_gap_size, HO::WRITABLE)
    }

    /// Returns the vm address space covered by this MemoryRegion
    pub fn vm_addr_range(&self) -> Range<u64> {
        if self.vm_gap_shift == 63 {
            self.vm_addr..self.vm_addr.saturating_add(self.len)
        } else {
            self.vm_addr..self.vm_addr.saturating_add(self.len.saturating_mul(2))
        }
    }

    /// Convert a virtual machine address into a host address
    pub fn vm_to_host(&self, access_type: AccessType, vm_addr: u64, len: u64) -> Option<u64> {
        if access_type == AccessType::Store && !self.writable {
            return None;
        }

        // This can happen if a region starts at an offset from the base region
        // address, eg with rodata regions if config.optimize_rodata = true, see
        // Elf::get_ro_region.
        if vm_addr < self.vm_addr {
            return None;
        }

        let begin_offset = vm_addr.saturating_sub(self.vm_addr);
        if self.vm_gap_shift == 63 {
            // fast path for non-gapped regions
            if let Some(end_offset) = begin_offset.checked_add(len) {
                if end_offset <= self.len {
                    return Some(self.host_addr.saturating_add(begin_offset));
                }
            }
            return None;
        }

        let is_in_gap = (begin_offset
            .checked_shr(self.vm_gap_shift as u32)
            .unwrap_or(0)
            & 1)
            == 1;
        let gap_mask = (-1i64).checked_shl(self.vm_gap_shift as u32).unwrap_or(0) as u64;
        let gapped_offset =
            (begin_offset & gap_mask).checked_shr(1).unwrap_or(0) | (begin_offset & !gap_mask);
        if let Some(end_offset) = gapped_offset.checked_add(len) {
            if end_offset <= self.len && !is_in_gap {
                return Some(self.host_addr.saturating_add(gapped_offset));
            }
        }
        None
    }
}

impl fmt::Debug for MemoryRegion {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "host_addr: {:#x?}-{:#x?}, vm_addr: {:#x?}-{:#x?}, len: {}, writable: {}, payload {:?}",
            self.host_addr,
            self.host_addr.saturating_add(self.len),
            self.vm_addr,
            self.vm_addr_range().end,
            self.len,
            self.writable,
            self.access_violation_handler_payload,
        )
    }
}

impl std::cmp::PartialOrd for MemoryRegion {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl std::cmp::Ord for MemoryRegion {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.vm_addr.cmp(&other.vm_addr)
    }
}

/// Type of memory access
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum AccessType {
    /// Read
    Load,
    /// Write
    Store,
}

impl std::fmt::Display for AccessType {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        f.write_str(match self {
            Self::Load => "reading",
            Self::Store => "writing",
        })
    }
}

/// Memory mapping based on eytzinger search.
pub struct UnalignedMemoryMapping {
    /// Common parts
    regions: Box<[MemoryRegion]>,
    /// Regions vm_addr fields in Eytzinger order
    region_addresses: Box<[u64]>,
    /// Converts the Eytzinger order back to the original order
    region_index_lookup: Box<[usize]>,
    /// Cache of the last `MappingCache::SIZE` vm_addr => region_index lookups
    cache: UnsafeCell<MappingCache>,
}

impl fmt::Debug for UnalignedMemoryMapping {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("UnalignedMemoryMapping")
            .field("regions", &self.regions)
            .field("cache", &self.cache)
            .finish()
    }
}

impl UnalignedMemoryMapping {
    fn construct_eytzinger_order(&mut self, mut in_index: usize, out_index: usize) -> usize {
        if out_index >= self.regions.len() {
            return in_index;
        }
        in_index =
            self.construct_eytzinger_order(in_index, out_index.saturating_mul(2).saturating_add(1));
        self.region_addresses[out_index] = self.regions[in_index].vm_addr;
        self.region_index_lookup[out_index] = in_index;
        self.construct_eytzinger_order(
            in_index.saturating_add(1),
            out_index.saturating_mul(2).saturating_add(2),
        )
    }

    /// Create an uninitialized UnalignedMapping
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    pub unsafe fn new_uninitialized(regions: Vec<MemoryRegion>) -> Self {
        let number_of_regions = regions.len();
        Self {
            regions: regions.into_boxed_slice(),
            region_addresses: vec![0; number_of_regions].into_boxed_slice(),
            region_index_lookup: vec![0; number_of_regions].into_boxed_slice(),
            cache: UnsafeCell::new(MappingCache::new()),
        }
    }

    /// Creates a new MemoryMapping structure from the given regions
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    pub unsafe fn new(regions: Vec<MemoryRegion>) -> Result<Self, EbpfError> {
        let mut mapping = Self::new_uninitialized(regions);
        mapping.initialize()?;
        Ok(mapping)
    }

    /// Initialize the memory mapping
    pub fn initialize(&mut self) -> Result<(), EbpfError> {
        self.regions.sort();
        let number_of_regions = self.regions.len();
        for index in 1..number_of_regions {
            let first = &self.regions[index.saturating_sub(1)];
            let second = &self.regions[index];
            if first.vm_addr_range().end > second.vm_addr {
                return Err(EbpfError::InvalidMemoryRegion(index));
            }
        }

        self.construct_eytzinger_order(0, 0);
        Ok(())
    }

    /// Returns the `MemoryRegion` which may contain the given address.
    #[allow(clippy::arithmetic_side_effects)]
    #[inline(always)]
    pub fn find_region(&self, vm_addr: u64) -> Option<(usize, &MemoryRegion)> {
        // Safety:
        // &mut references to the mapping cache are only created internally from methods that do not
        // invoke each other. UnalignedMemoryMapping is !Sync, so the cache reference below is
        // guaranteed to be unique.
        let cache = unsafe { &mut *self.cache.get() };
        if let Some(index) = cache.find(vm_addr) {
            // Safety:
            // Cached index, we validated it before caching it. See the corresponding safety section
            // in the miss branch.
            Some((index, unsafe { self.regions.get_unchecked(index) }))
        } else {
            let mut index = 1;
            while index <= self.region_addresses.len() {
                // Safety:
                // we start the search at index=1 and in the loop condition check
                // for index <= len, so bound checks can be avoided
                index = (index << 1)
                    + unsafe { *self.region_addresses.get_unchecked(index - 1) <= vm_addr }
                        as usize;
            }
            index >>= index.trailing_zeros() + 1;
            if index == 0 {
                return None;
            }
            // Safety:
            // we check for index==0 above, and by construction if we get here index
            // must be contained in region
            index = unsafe { *self.region_index_lookup.get_unchecked(index - 1) };
            let region = unsafe { self.regions.get_unchecked(index) };
            cache.insert(region.vm_addr_range(), index);
            Some((index, region))
        }
    }

    /// Replaces the `MemoryRegion` at the given index
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    #[inline(always)]
    pub unsafe fn replace_region(
        &mut self,
        index: usize,
        region: MemoryRegion,
    ) -> Result<(), EbpfError> {
        self.regions[index] = region;
        self.cache.get_mut().flush();
        Ok(())
    }
}

/// Memory mapping that uses the upper half of an address to identify the
/// underlying memory region.
#[derive(Debug)]
pub struct AlignedMemoryMapping {
    regions: Vec<MemoryRegion>,
    allow_memory_region_zero: bool,
}

impl AlignedMemoryMapping {
    /// Creates a new initialized MemoryMapping structure from the given regions
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    pub unsafe fn new(regions: Vec<MemoryRegion>, config: &Config) -> Result<Self, EbpfError> {
        let mut mapping = Self::new_uninitialized(regions, config);
        mapping.initialize()?;
        Ok(mapping)
    }

    /// Create an uninitialized MemoryMapping
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    pub unsafe fn new_uninitialized(regions: Vec<MemoryRegion>, config: &Config) -> Self {
        Self {
            regions,
            allow_memory_region_zero: config.allow_memory_region_zero,
        }
    }

    /// Initialize the memory mapping by sorting its regions and filling gaps
    pub fn initialize(&mut self) -> Result<(), EbpfError> {
        static EMPTY_SLICE: &[u8] = &[];
        if self.allow_memory_region_zero {
            self.regions.sort();
            let mut expected_region_index = 0;
            while expected_region_index < self.regions.len() {
                let actual_region_index = self
                    .regions
                    .get(expected_region_index)
                    .unwrap()
                    .vm_addr
                    .checked_shr(ebpf::VIRTUAL_ADDRESS_BITS as u32)
                    .unwrap_or(0) as usize;
                if actual_region_index > expected_region_index {
                    self.regions.insert(
                        expected_region_index,
                        MemoryRegion::new(
                            &raw const *EMPTY_SLICE,
                            (expected_region_index as u64).saturating_mul(ebpf::MM_REGION_SIZE),
                        ),
                    );
                } else if actual_region_index < expected_region_index {
                    return Err(EbpfError::InvalidMemoryRegion(actual_region_index));
                }
                expected_region_index = expected_region_index.saturating_add(1);
            }
        } else {
            self.regions
                .push(MemoryRegion::new(&raw const *EMPTY_SLICE, 0));
            self.regions.sort();
            for (index, region) in self.regions.iter().enumerate() {
                if region
                    .vm_addr
                    .checked_shr(ebpf::VIRTUAL_ADDRESS_BITS as u32)
                    .unwrap_or(0)
                    != index as u64
                {
                    return Err(EbpfError::InvalidMemoryRegion(index));
                }
            }
        }

        Ok(())
    }

    /// Returns the `MemoryRegion` which may contain the given address.
    #[inline(always)]
    pub fn find_region(&self, vm_addr: u64) -> Option<(usize, &MemoryRegion)> {
        let index = vm_addr.wrapping_shr(ebpf::VIRTUAL_ADDRESS_BITS as u32) as usize;
        if index < self.regions.len() && (index > 0 || self.allow_memory_region_zero) {
            // Safety: bounds check above
            let region = unsafe { self.regions.get_unchecked(index) };
            return Some((index, region));
        }
        None
    }

    /// Replaces the `MemoryRegion` at the given index
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    #[inline(always)]
    pub unsafe fn replace_region(
        &mut self,
        index: usize,
        region: MemoryRegion,
    ) -> Result<(), EbpfError> {
        let begin_index = region
            .vm_addr
            .checked_shr(ebpf::VIRTUAL_ADDRESS_BITS as u32)
            .unwrap_or(0) as usize;
        let end_index = region
            .vm_addr
            .saturating_add(region.len.saturating_sub(1))
            .checked_shr(ebpf::VIRTUAL_ADDRESS_BITS as u32)
            .unwrap_or(0) as usize;
        if begin_index != index || end_index != index {
            return Err(EbpfError::InvalidMemoryRegion(index));
        }
        self.regions[index] = region;
        Ok(())
    }
}

/// Common parts of [UnalignedMemoryMapping] and [AlignedMemoryMapping]
pub struct MemoryMapping {
    /// Access violation handler
    access_violation_handler: AccessViolationHandler,
    max_call_depth: i64,
    stack_frame_size: i64,
    disable_address_translation: bool,
    /// Executable sbpf_version
    sbpf_version: SBPFVersion,
    initialized: bool,
    ty: MemoryMappingType,
}

impl fmt::Debug for MemoryMapping {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        f.debug_struct("MemoryMapping")
            .field("max_call_depth", &self.max_call_depth)
            .field("stack_frame_size", &self.stack_frame_size)
            .field("sbpf_version", &self.sbpf_version)
            .field("ty", &self.ty)
            .finish()
    }
}

/// Maps virtual memory to host memory.
#[derive(Debug)]
pub enum MemoryMappingType {
    /// Aligned memory mapping which uses the upper half of an address to
    /// identify the underlying memory region.
    Aligned(AlignedMemoryMapping),
    /// Memory mapping that allows mapping unaligned memory regions.
    Unaligned(UnalignedMemoryMapping),
}

impl MemoryMapping {
    /// Creates a new memory mapping.
    ///
    /// Uses aligned or unaligned memory mapping depending on the value of
    /// `config.aligned_memory_mapping=true`.
    ///
    /// # Safety
    ///
    /// In addition to the requirements of [`MemoryMapping::new_uninitialized`], the provided
    /// `access_violation_handler` must return with its [`MemoryRegion`] unmodified, or initialized
    /// to another equally correct [`MemoryRegion`] as described in the safety invariants for
    /// `new_uninitialized`.
    pub unsafe fn new_with_access_violation_handler(
        regions: Vec<MemoryRegion>,
        config: &Config,
        sbpf_version: SBPFVersion,
        access_violation_handler: AccessViolationHandler,
    ) -> Result<Self, EbpfError> {
        let mut mapping =
            Self::new_uninitialized(regions, config, sbpf_version, access_violation_handler);
        mapping.initialize()?;
        Ok(mapping)
    }

    /// Creates an unitialized memory mapping
    ///
    /// # Safety
    ///
    /// The memory pointed to by the [`MemoryRegion`]s must point to a valid object live for the
    /// duration of this `MemoryMapping`.
    ///
    /// For `MemoryRegion`s marked writable, the memory pointed to by the memory region must accept
    /// arbitrary bytes being overwritten without it resulting in unsoundness (due to e.g. broken
    /// internal type invariants.)
    pub unsafe fn new_uninitialized(
        regions: Vec<MemoryRegion>,
        config: &Config,
        sbpf_version: SBPFVersion,
        access_violation_handler: AccessViolationHandler,
    ) -> Self {
        let ty = if sbpf_version >= SBPFVersion::V4 || config.aligned_memory_mapping {
            MemoryMappingType::Aligned(AlignedMemoryMapping::new_uninitialized(regions, config))
        } else {
            debug_assert!(
                sbpf_version <= SBPFVersion::V3,
                "SBPFv4 and later versions do not support unaligned memory"
            );
            MemoryMappingType::Unaligned(UnalignedMemoryMapping::new_uninitialized(regions))
        };

        Self {
            access_violation_handler: Box::new(access_violation_handler),
            max_call_depth: config.max_call_depth as i64,
            stack_frame_size: config.stack_frame_size as i64,
            disable_address_translation: !config.enable_address_translation,
            sbpf_version,
            initialized: false,
            ty,
        }
    }

    /// Creates a new memory mapping for tests and benches.
    ///
    /// `access_violation_handler` defaults to a function which always returns an error.
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    pub unsafe fn new(
        regions: Vec<MemoryRegion>,
        config: &Config,
        sbpf_version: SBPFVersion,
    ) -> Result<Self, EbpfError> {
        Self::new_with_access_violation_handler(
            regions,
            config,
            sbpf_version,
            Box::new(default_access_violation_handler),
        )
    }

    /// Map virtual memory to host memory.
    pub fn map(&self, access_type: AccessType, vm_addr: u64, len: u64) -> ProgramResult {
        debug_assert!(self.initialized);
        if self.disable_address_translation {
            return ProgramResult::Ok(vm_addr);
        }

        if let Some((_index, region)) = self.find_region(vm_addr) {
            if let Some(host_addr) = region.vm_to_host(access_type, vm_addr, len) {
                return ProgramResult::Ok(host_addr);
            }
        }
        self.generate_access_violation(access_type, vm_addr, len)
    }

    /// Map virtual memory to host memory and potentially call the [AccessViolationHandler].
    ///
    /// This requires the [MemoryMapping] to be mutable and
    /// can cause previously translated addresses to become invalid.
    #[inline(always)]
    pub fn map_with_access_violation_handler(
        &mut self,
        access_type: AccessType,
        vm_addr: u64,
        len: u64,
    ) -> ProgramResult {
        debug_assert!(self.initialized);
        if self.disable_address_translation {
            return ProgramResult::Ok(vm_addr);
        }

        if let Some((index, region)) = self.find_region(vm_addr) {
            if let Some(host_addr) = region.vm_to_host(access_type, vm_addr, len) {
                return ProgramResult::Ok(host_addr);
            }
            let mut region = (*region).clone();
            let max_len = self
                .get_regions()
                .get(index.saturating_add(1))
                .map_or(u64::MAX, |next_region| next_region.vm_addr)
                .saturating_sub(region.vm_addr);
            (self.access_violation_handler)(&mut region, max_len, access_type, vm_addr, len);
            if let Some(host_addr) = region.vm_to_host(access_type, vm_addr, len) {
                if let Err(err) = unsafe { self.replace_region(index, region) } {
                    return ProgramResult::Err(err);
                }
                return ProgramResult::Ok(host_addr);
            }
        }
        self.generate_access_violation(access_type, vm_addr, len)
    }

    /// Loads `size_of::<T>()` bytes from the given address.
    pub fn load<T: Pod + Into<u64>>(&mut self, vm_addr: u64) -> ProgramResult {
        let len = mem::size_of::<T>() as u64;
        debug_assert!(len <= mem::size_of::<u64>() as u64);
        debug_assert!(self.initialized);
        match self.map_with_access_violation_handler(AccessType::Load, vm_addr, len) {
            ProgramResult::Ok(host_addr) => {
                ProgramResult::Ok(unsafe { ptr::read_unaligned::<T>(host_addr as *const T) }.into())
            }
            err => err,
        }
    }

    /// Store `value` at the given address.
    #[inline]
    pub fn store<T: Pod>(&mut self, value: T, vm_addr: u64) -> ProgramResult {
        let len = mem::size_of::<T>() as u64;
        debug_assert!(len <= mem::size_of::<u64>() as u64);
        debug_assert!(self.initialized);
        match self.map_with_access_violation_handler(AccessType::Store, vm_addr, len) {
            ProgramResult::Ok(host_addr) => {
                unsafe { ptr::write_unaligned(host_addr as *mut T, value) };
                ProgramResult::Ok(host_addr)
            }
            err => err,
        }
    }

    /// Returns the `MemoryRegion` which may contain the given address.
    #[inline(always)]
    pub fn find_region(&self, vm_addr: u64) -> Option<(usize, &MemoryRegion)> {
        debug_assert!(self.initialized);
        match &self.ty {
            MemoryMappingType::Aligned(inner) => inner.find_region(vm_addr),
            MemoryMappingType::Unaligned(inner) => inner.find_region(vm_addr),
        }
    }

    /// Returns the `MemoryRegion`s in this mapping.
    #[inline(always)]
    pub fn get_regions(&self) -> &[MemoryRegion] {
        match &self.ty {
            MemoryMappingType::Aligned(inner) => &inner.regions,
            MemoryMappingType::Unaligned(inner) => &inner.regions,
        }
    }

    /// Returns the [`MemoryRegion`]s as mutable.
    ///
    /// Modifying the regions might break the initialization constraints, so this function
    /// uninitializes the mapping. The memory mappings must be initialized
    /// again with [`Self::initialize`] before further use.
    pub fn get_regions_mut(&mut self) -> &mut [MemoryRegion] {
        self.initialized = false;

        let regions = match &mut self.ty {
            MemoryMappingType::Aligned(inner) => inner.regions.as_mut_slice(),
            MemoryMappingType::Unaligned(inner) => &mut inner.regions,
        };

        regions
    }

    /// Replaces the `MemoryRegion` at the given index
    ///
    /// # Safety
    ///
    /// Refer to [`MemoryMapping::new_uninitialized`].
    #[inline(always)]
    pub unsafe fn replace_region(
        &mut self,
        index: usize,
        region: MemoryRegion,
    ) -> Result<(), EbpfError> {
        debug_assert!(self.initialized);
        let regions = self.get_regions();
        let next_region_start = regions
            .get(index.saturating_add(1))
            .map_or(u64::MAX, |next_region| next_region.vm_addr);
        if index >= regions.len()
            || regions[index].vm_addr != region.vm_addr
            || region.vm_addr_range().end > next_region_start
        {
            return Err(EbpfError::InvalidMemoryRegion(index));
        }
        match &mut self.ty {
            MemoryMappingType::Aligned(inner) => inner.replace_region(index, region),
            MemoryMappingType::Unaligned(inner) => inner.replace_region(index, region),
        }
    }

    /// Initialize the MemoryMapping
    pub fn initialize(&mut self) -> Result<(), EbpfError> {
        let result = match &mut self.ty {
            MemoryMappingType::Aligned(inner) => inner.initialize(),
            MemoryMappingType::Unaligned(inner) => inner.initialize(),
        };
        self.initialized = result.is_ok();
        result
    }

    fn generate_access_violation(
        &self,
        access_type: AccessType,
        vm_addr: u64,
        len: u64,
    ) -> ProgramResult {
        let stack_frame = (vm_addr as i64)
            .saturating_sub(ebpf::MM_STACK_START as i64)
            .checked_div(self.stack_frame_size)
            .unwrap_or(0);
        if !self.sbpf_version.manual_stack_frame_bump()
            && (-1..self.max_call_depth.saturating_add(1)).contains(&stack_frame)
        {
            ProgramResult::Err(EbpfError::StackAccessViolation(
                access_type,
                vm_addr,
                len,
                stack_frame,
            ))
        } else {
            let region = self.find_region(vm_addr);
            let region_name = match vm_addr & (!ebpf::MM_BYTECODE_START.saturating_sub(1)) {
                _ if region.map(|(_, r)| r.vm_addr_range().contains(&vm_addr)) != Some(true) => {
                    "unallocated"
                }
                ebpf::MM_BYTECODE_START => "program",
                ebpf::MM_STACK_START => "stack",
                ebpf::MM_HEAP_START => "heap",
                ebpf::MM_INPUT_START => "input",
                _ => "allocated",
            };
            ProgramResult::Err(EbpfError::AccessViolation(
                access_type,
                vm_addr,
                len,
                region_name,
            ))
        }
    }
}

/// Fast, small linear cache used to speed up unaligned memory mapping.
#[derive(Debug)]
struct MappingCache {
    // The cached entries.
    entries: [(Range<u64>, usize); MappingCache::SIZE],
    // Index of the last accessed memory region.
    //
    // New entries are written backwards, so that find() can always scan
    // forward which is faster.
    head: usize,
}

impl MappingCache {
    // must be a power of two
    const SIZE: usize = 4;

    fn new() -> MappingCache {
        MappingCache {
            entries: array::from_fn(|_| (0..0, 0)),
            head: 0,
        }
    }

    #[inline]
    fn find(&self, vm_addr: u64) -> Option<usize> {
        for i in 0..Self::SIZE {
            let index = self.head.wrapping_add(i) % Self::SIZE;
            // Safety:
            // index is guaranteed to be between 0..Self::SIZE
            let (vm_range, region_index) = unsafe { self.entries.get_unchecked(index) };
            if vm_range.contains(&vm_addr) {
                return Some(*region_index);
            }
        }

        None
    }

    #[inline]
    fn insert(&mut self, vm_range: Range<u64>, region_index: usize) {
        self.head = self.head.wrapping_sub(1) % Self::SIZE;
        // Safety:
        // self.head is guaranteed to be between 0..Self::SIZE
        unsafe { *self.entries.get_unchecked_mut(self.head) = (vm_range, region_index) };
    }

    #[inline]
    fn flush(&mut self) {
        self.entries = array::from_fn(|_| (0..0, 0));
        self.head = 0;
    }
}

#[cfg(test)]
mod test {
    use std::{cell::RefCell, rc::Rc};
    use test_utils::assert_error;

    use super::*;

    #[test]
    fn test_mapping_cache() {
        let mut cache = MappingCache::new();
        assert_eq!(cache.find(0), None);

        let mut ranges = vec![10u64..20, 20..30, 30..40, 40..50];
        for (region, range) in ranges.iter().cloned().enumerate() {
            cache.insert(range, region);
        }
        for (region, range) in ranges.iter().enumerate() {
            if region > 0 {
                assert_eq!(cache.find(range.start - 1), Some(region - 1));
            } else {
                assert_eq!(cache.find(range.start - 1), None);
            }
            assert_eq!(cache.find(range.start), Some(region));
            assert_eq!(cache.find(range.start + 1), Some(region));
            assert_eq!(cache.find(range.end - 1), Some(region));
            if region < 3 {
                assert_eq!(cache.find(range.end), Some(region + 1));
            } else {
                assert_eq!(cache.find(range.end), None);
            }
        }

        cache.insert(50..60, 4);
        ranges.push(50..60);
        for (region, range) in ranges.iter().enumerate() {
            if region == 0 {
                assert_eq!(cache.find(range.start), None);
                continue;
            }
            if region > 1 {
                assert_eq!(cache.find(range.start - 1), Some(region - 1));
            } else {
                assert_eq!(cache.find(range.start - 1), None);
            }
            assert_eq!(cache.find(range.start), Some(region));
            assert_eq!(cache.find(range.start + 1), Some(region));
            assert_eq!(cache.find(range.end - 1), Some(region));
            if region < 4 {
                assert_eq!(cache.find(range.end), Some(region + 1));
            } else {
                assert_eq!(cache.find(range.end), None);
            }
        }
    }

    #[test]
    fn test_mapping_cache_flush() {
        let mut cache = MappingCache::new();
        assert_eq!(cache.find(0), None);
        cache.insert(0..10, 0);
        assert_eq!(cache.find(0), Some(0));
        cache.flush();
        assert_eq!(cache.find(0), None);
    }

    #[test]
    fn test_map_empty() {
        for aligned_memory_mapping in [false, true] {
            let config = Config {
                aligned_memory_mapping,
                ..Config::default()
            };
            let m = unsafe { MemoryMapping::new(vec![], &config, SBPFVersion::V3) }.unwrap();
            assert_error!(
                m.map(AccessType::Load, ebpf::MM_REGION_SIZE, 8),
                "AccessViolation"
            );
        }
    }

    #[test]
    fn test_gapped_map() {
        for aligned_memory_mapping in [false, true] {
            let config = Config {
                aligned_memory_mapping,
                ..Config::default()
            };
            let mut mem1 = [0xff; 8];
            let mem2 = [0; 8];
            let mut m = unsafe {
                MemoryMapping::new(
                    vec![
                        MemoryRegion::new(&raw const mem2[..], ebpf::MM_REGION_SIZE),
                        MemoryRegion::new_gapped(&raw mut mem1[..], ebpf::MM_REGION_SIZE * 2, 2),
                    ],
                    &config,
                    SBPFVersion::V3,
                )
                .unwrap()
            };
            for frame in 0..4 {
                let address = ebpf::MM_STACK_START + frame * 4;
                assert!(m.find_region(address).is_some());
                assert!(m.map(AccessType::Load, address, 2).is_ok());
                assert_error!(m.map(AccessType::Load, address + 2, 2), "AccessViolation");
                assert_eq!(m.load::<u16>(address).unwrap(), 0xFFFF);
                assert_error!(m.load::<u16>(address + 2), "AccessViolation");
                assert!(m.store::<u16>(0xFFFF, address).is_ok());
                assert_error!(m.store::<u16>(0xFFFF, address + 2), "AccessViolation");
            }
        }
    }

    #[test]
    fn test_unaligned_map_overlap() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };
        let mem1 = [1, 2, 3, 4];
        let mem2 = [5, 6];
        assert_error!(
            unsafe {
                MemoryMapping::new(
                    vec![
                        MemoryRegion::new(&raw const mem1, ebpf::MM_REGION_SIZE),
                        MemoryRegion::new(
                            &raw const mem2,
                            ebpf::MM_REGION_SIZE + mem1.len() as u64 - 1,
                        ),
                    ],
                    &config,
                    SBPFVersion::V3,
                )
            },
            "InvalidMemoryRegion(1)"
        );
        assert!(unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw const mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE + mem1.len() as u64),
                ],
                &config,
                SBPFVersion::V3,
            )
        }
        .is_ok());
    }

    #[test]
    fn test_unaligned_map() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };
        let mut mem1 = [11];
        let mem2 = [22, 22];
        let mem3 = [33];
        let mem4 = [44, 44];
        let m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw mut mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE + mem1.len() as u64),
                    MemoryRegion::new(
                        &raw const mem3,
                        ebpf::MM_REGION_SIZE + (mem1.len() + mem2.len()) as u64,
                    ),
                    MemoryRegion::new(
                        &raw const mem4,
                        ebpf::MM_REGION_SIZE + (mem1.len() + mem2.len() + mem3.len()) as u64,
                    ),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };

        assert_eq!(
            m.map(AccessType::Load, ebpf::MM_REGION_SIZE, 1).unwrap(),
            mem1.as_ptr() as u64
        );

        assert_eq!(
            m.map(AccessType::Store, ebpf::MM_REGION_SIZE, 1).unwrap(),
            mem1.as_ptr() as u64
        );

        assert_error!(
            m.map(AccessType::Load, ebpf::MM_REGION_SIZE, 2),
            "AccessViolation"
        );

        assert_eq!(
            m.map(
                AccessType::Load,
                ebpf::MM_REGION_SIZE + mem1.len() as u64,
                1,
            )
            .unwrap(),
            mem2.as_ptr() as u64
        );

        assert_eq!(
            m.map(
                AccessType::Load,
                ebpf::MM_REGION_SIZE + (mem1.len() + mem2.len()) as u64,
                1,
            )
            .unwrap(),
            mem3.as_ptr() as u64
        );

        assert_eq!(
            m.map(
                AccessType::Load,
                ebpf::MM_REGION_SIZE + (mem1.len() + mem2.len() + mem3.len()) as u64,
                1,
            )
            .unwrap(),
            mem4.as_ptr() as u64
        );

        assert_error!(
            m.map(
                AccessType::Load,
                ebpf::MM_REGION_SIZE + (mem1.len() + mem2.len() + mem3.len() + mem4.len()) as u64,
                1,
            ),
            "AccessViolation"
        );
    }

    #[test]
    fn test_unaligned_region() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };

        let mut mem1 = [0xFF; 4];
        let mem2 = [0xDD; 4];
        let m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw mut mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE + 4),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };
        assert!(m.find_region(ebpf::MM_REGION_SIZE - 1).is_none());
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE).unwrap().1.host_addr,
            mem1.as_ptr() as u64
        );
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE + 3).unwrap().1.host_addr,
            mem1.as_ptr() as u64
        );
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE + 4).unwrap().1.host_addr,
            mem2.as_ptr() as u64
        );
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE + 7).unwrap().1.host_addr,
            mem2.as_ptr() as u64
        );
        assert!(m.find_region(ebpf::MM_REGION_SIZE + 8).is_some());
    }

    #[test]
    fn test_aligned_region() {
        let config = Config {
            aligned_memory_mapping: true,
            ..Config::default()
        };

        let mut mem1 = [0xFF; 4];
        let mem2 = [0xDD; 4];
        let m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw mut mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE * 2),
                ],
                &config,
                SBPFVersion::V4,
            )
            .unwrap()
        };
        assert_eq!(m.find_region(ebpf::MM_REGION_SIZE - 1).unwrap().1.len, 0);
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE).unwrap().1.host_addr,
            mem1.as_ptr() as u64
        );
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE + 3).unwrap().1.host_addr,
            mem1.as_ptr() as u64
        );
        assert!(m.find_region(ebpf::MM_REGION_SIZE + 4).is_some());
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE * 2).unwrap().1.host_addr,
            mem2.as_ptr() as u64
        );
        assert_eq!(
            m.find_region(ebpf::MM_REGION_SIZE * 2 + 3)
                .unwrap()
                .1
                .host_addr,
            mem2.as_ptr() as u64
        );
        assert!(m.find_region(ebpf::MM_REGION_SIZE * 3 + 4).is_none());
    }

    #[test]
    fn test_unaligned_map_load() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };
        let mem1 = [0x11, 0x22];
        let mem2 = [0x33];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw const mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE + mem1.len() as u64),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };

        assert_eq!(m.load::<u16>(ebpf::MM_REGION_SIZE).unwrap(), 0x2211);
        assert_error!(m.load::<u32>(ebpf::MM_REGION_SIZE), "AccessViolation");
        assert_error!(m.load::<u32>(ebpf::MM_REGION_SIZE + 4), "AccessViolation");
    }

    #[test]
    fn test_unaligned_map_store() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };
        let mut mem1 = [0xff, 0xff];
        let mut mem2 = [0xff];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw mut mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw mut mem2, ebpf::MM_REGION_SIZE + mem1.len() as u64),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };

        m.store(0x1122u16, ebpf::MM_REGION_SIZE).unwrap();
        assert_eq!(m.load::<u16>(ebpf::MM_REGION_SIZE).unwrap(), 0x1122);

        assert_error!(
            m.store(0x33445566u32, ebpf::MM_REGION_SIZE),
            "AccessViolation"
        );
    }

    #[test]
    fn test_unaligned_map_store_out_of_bounds() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };

        let mut mem1 = [0xFF];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![MemoryRegion::new(&raw mut mem1, ebpf::MM_REGION_SIZE)],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };
        m.store(0x11u8, ebpf::MM_REGION_SIZE).unwrap();
        assert_error!(m.store(0x11u8, ebpf::MM_REGION_SIZE - 1), "AccessViolation");
        assert_error!(m.store(0x11u8, ebpf::MM_REGION_SIZE + 1), "AccessViolation");
        // this gets us line coverage for the case where we're completely
        // outside the address space (the case above is just on the edge)
        assert_error!(m.store(0x11u8, ebpf::MM_REGION_SIZE + 2), "AccessViolation");

        let mut mem1 = [0xFF; 4];
        let mut mem2 = [0xDD; 4];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw mut mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw mut mem2, ebpf::MM_REGION_SIZE + 4),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };
        assert_error!(
            m.store(0x1122334455667788u64, ebpf::MM_REGION_SIZE),
            "AccessViolation"
        );
    }

    #[test]
    fn test_unaligned_map_load_out_of_bounds() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };

        let mem1 = [0xff];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![MemoryRegion::new(&raw const mem1, ebpf::MM_REGION_SIZE)],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };
        assert_eq!(m.load::<u8>(ebpf::MM_REGION_SIZE).unwrap(), 0xff);
        assert_error!(m.load::<u8>(ebpf::MM_REGION_SIZE - 1), "AccessViolation");
        assert_error!(m.load::<u8>(ebpf::MM_REGION_SIZE + 1), "AccessViolation");
        assert_error!(m.load::<u8>(ebpf::MM_REGION_SIZE + 2), "AccessViolation");

        let mem1 = [0xFF; 4];
        let mem2 = [0xDD; 4];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw const mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE + 4),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };
        assert_error!(m.load::<u64>(ebpf::MM_REGION_SIZE), "AccessViolation");
    }

    #[test]
    #[should_panic(expected = "AccessViolation")]
    fn test_store_readonly() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };
        let mut mem1 = [0xff, 0xff];
        let mem2 = [0xff, 0xff];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw mut mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE + mem1.len() as u64),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };
        m.store(0x11223344, ebpf::MM_REGION_SIZE).unwrap();
    }

    #[test]
    fn test_unaligned_map_replace_region() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };
        let mem1 = [11];
        let mem2 = [22, 22];
        let mem3 = [33];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw const mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE + mem1.len() as u64),
                ],
                &config,
                SBPFVersion::V3,
            )
            .unwrap()
        };

        assert_eq!(
            m.map(AccessType::Load, ebpf::MM_REGION_SIZE, 1).unwrap(),
            mem1.as_ptr() as u64
        );

        assert_eq!(
            m.map(
                AccessType::Load,
                ebpf::MM_REGION_SIZE + mem1.len() as u64,
                1,
            )
            .unwrap(),
            mem2.as_ptr() as u64
        );

        assert_error!(
            unsafe {
                m.replace_region(
                    2,
                    MemoryRegion::new(&raw const mem3, ebpf::MM_REGION_SIZE + mem1.len() as u64),
                )
            },
            "InvalidMemoryRegion(2)"
        );

        let region_index = m
            .get_regions()
            .iter()
            .position(|mem| mem.vm_addr == ebpf::MM_REGION_SIZE + mem1.len() as u64)
            .unwrap();

        // old.vm_addr != new.vm_addr
        assert_error!(
            unsafe {
                m.replace_region(
                    region_index,
                    MemoryRegion::new(
                        &raw const mem3,
                        ebpf::MM_REGION_SIZE + mem1.len() as u64 + 1,
                    ),
                )
            },
            "InvalidMemoryRegion({})",
            region_index
        );

        unsafe {
            m.replace_region(
                region_index,
                MemoryRegion::new(&raw const mem3, ebpf::MM_REGION_SIZE + mem1.len() as u64),
            )
            .unwrap()
        };

        assert_eq!(
            m.map(
                AccessType::Load,
                ebpf::MM_REGION_SIZE + mem1.len() as u64,
                1,
            )
            .unwrap(),
            mem3.as_ptr() as u64
        );
    }

    #[test]
    fn test_aligned_map_replace_region() {
        let config = Config {
            aligned_memory_mapping: true,
            ..Config::default()
        };
        let mem1 = [11];
        let mem2 = [22, 22];
        let mem3 = [33, 33];
        let mut m = unsafe {
            MemoryMapping::new(
                vec![
                    MemoryRegion::new(&raw const mem1, ebpf::MM_REGION_SIZE),
                    MemoryRegion::new(&raw const mem2, ebpf::MM_REGION_SIZE * 2),
                ],
                &config,
                SBPFVersion::V4,
            )
            .unwrap()
        };

        assert_eq!(
            m.map(AccessType::Load, ebpf::MM_REGION_SIZE * 2, 1)
                .unwrap(),
            mem2.as_ptr() as u64
        );

        // index > regions.len()
        assert_error!(
            unsafe {
                m.replace_region(
                    3,
                    MemoryRegion::new(&raw const mem3, ebpf::MM_REGION_SIZE * 2),
                )
            },
            "InvalidMemoryRegion(3)"
        );

        // index != addr >> VIRTUAL_ADDRESS_BITS
        assert_error!(
            unsafe {
                m.replace_region(
                    2,
                    MemoryRegion::new(&raw const mem3, ebpf::MM_REGION_SIZE * 3),
                )
            },
            "InvalidMemoryRegion(2)"
        );

        // index + len != addr >> VIRTUAL_ADDRESS_BITS
        assert_error!(
            unsafe {
                m.replace_region(
                    2,
                    MemoryRegion::new(&raw const mem3, ebpf::MM_REGION_SIZE * 3 - 1),
                )
            },
            "InvalidMemoryRegion(2)"
        );

        unsafe {
            m.replace_region(
                2,
                MemoryRegion::new(&raw const mem3, ebpf::MM_REGION_SIZE * 2),
            )
            .unwrap()
        };

        assert_eq!(
            m.map(AccessType::Load, ebpf::MM_REGION_SIZE * 2, 1)
                .unwrap(),
            mem3.as_ptr() as u64
        );
    }

    #[test]
    fn test_access_violation_handler_map() {
        for aligned_memory_mapping in [true, false] {
            let config = Config {
                aligned_memory_mapping,
                ..Config::default()
            };
            let original = [11, 22];
            let copied = Rc::new(RefCell::new(Vec::new()));
            let mut regions = vec![MemoryRegion::new(&raw const original, ebpf::MM_REGION_SIZE)];
            regions[0].access_violation_handler_payload = Some(0);

            let c = Rc::clone(&copied);
            let mut m = unsafe {
                MemoryMapping::new_with_access_violation_handler(
                    regions,
                    &config,
                    SBPFVersion::V3,
                    Box::new(move |region, _, _, _, _| {
                        c.borrow_mut().extend_from_slice(&original);
                        region.writable = true;
                        region.host_addr = c.borrow().as_slice().as_ptr() as u64;
                    }),
                )
                .unwrap()
            };

            assert_eq!(
                m.map_with_access_violation_handler(AccessType::Load, ebpf::MM_REGION_SIZE, 1)
                    .unwrap(),
                original.as_ptr() as u64
            );
            assert_eq!(
                m.map_with_access_violation_handler(AccessType::Store, ebpf::MM_REGION_SIZE, 1)
                    .unwrap(),
                copied.borrow().as_ptr() as u64
            );
        }
    }

    #[test]
    fn test_access_violation_handler_load_store() {
        for aligned_memory_mapping in [true, false] {
            let config = Config {
                aligned_memory_mapping,
                ..Config::default()
            };
            let original = [11, 22];
            let copied = Rc::new(RefCell::new(Vec::new()));
            let mut regions = vec![MemoryRegion::new(&raw const original, ebpf::MM_REGION_SIZE)];
            regions[0].access_violation_handler_payload = Some(0);

            let c = Rc::clone(&copied);
            let mut m = unsafe {
                MemoryMapping::new_with_access_violation_handler(
                    regions,
                    &config,
                    SBPFVersion::V3,
                    Box::new(move |region, _, _, _, _| {
                        c.borrow_mut().extend_from_slice(&original);
                        region.writable = true;
                        region.host_addr = c.borrow().as_slice().as_ptr() as u64;
                    }),
                )
                .unwrap()
            };

            assert_eq!(
                m.map(AccessType::Load, ebpf::MM_REGION_SIZE, 1).unwrap(),
                original.as_ptr() as u64
            );

            assert_eq!(m.load::<u8>(ebpf::MM_REGION_SIZE).unwrap(), 11);
            assert_eq!(m.load::<u8>(ebpf::MM_REGION_SIZE + 1).unwrap(), 22);
            assert!(copied.borrow().is_empty());

            m.store(33u8, ebpf::MM_REGION_SIZE).unwrap();
            assert_eq!(original[0], 11);
            assert_eq!(m.load::<u8>(ebpf::MM_REGION_SIZE).unwrap(), 33);
            assert_eq!(m.load::<u8>(ebpf::MM_REGION_SIZE + 1).unwrap(), 22);
        }
    }

    #[test]
    fn test_access_violation_handler_region_id() {
        for aligned_memory_mapping in [true, false] {
            let config = Config {
                aligned_memory_mapping,
                ..Config::default()
            };
            let original1 = [11, 22];
            let original2 = [33, 44];
            let copied = Rc::new(RefCell::new(Vec::new()));

            let mut regions = vec![
                MemoryRegion::new(&raw const original1, ebpf::MM_REGION_SIZE),
                MemoryRegion::new(&raw const original2, ebpf::MM_REGION_SIZE * 2),
            ];
            regions[0].access_violation_handler_payload = Some(42);

            let c = Rc::clone(&copied);
            let mut m = unsafe {
                MemoryMapping::new_with_access_violation_handler(
                    regions,
                    &config,
                    SBPFVersion::V3,
                    Box::new(move |region, _, _, _, _| {
                        // check that the argument passed to MemoryRegion::new is then passed to the
                        // callback
                        assert_eq!(region.access_violation_handler_payload, Some(42));
                        c.borrow_mut().extend_from_slice(&original1);
                        region.writable = true;
                        region.host_addr = c.borrow().as_slice().as_ptr() as u64;
                    }),
                )
                .unwrap()
            };

            m.store(55u8, ebpf::MM_REGION_SIZE).unwrap();
            assert_eq!(original1[0], 11);
            assert_eq!(m.load::<u8>(ebpf::MM_REGION_SIZE).unwrap(), 55);
        }
    }

    #[test]
    #[should_panic(expected = "AccessViolation")]
    fn test_map_access_violation_handler_error() {
        let config = Config::default();
        let original = [11, 22];

        let m = unsafe {
            MemoryMapping::new_with_access_violation_handler(
                vec![MemoryRegion::new(&raw const original, ebpf::MM_REGION_SIZE)],
                &config,
                SBPFVersion::V4,
                Box::new(default_access_violation_handler),
            )
            .unwrap()
        };

        m.map(AccessType::Store, ebpf::MM_REGION_SIZE, 1).unwrap();
    }

    #[test]
    #[should_panic(expected = "AccessViolation")]
    fn test_store_access_violation_handler_error() {
        let config = Config::default();
        let original = [11, 22];

        let mut m = unsafe {
            MemoryMapping::new_with_access_violation_handler(
                vec![MemoryRegion::new(&raw const original, ebpf::MM_REGION_SIZE)],
                &config,
                SBPFVersion::V4,
                Box::new(default_access_violation_handler),
            )
            .unwrap()
        };

        m.store(33u8, ebpf::MM_REGION_SIZE).unwrap();
    }

    #[test]
    fn test_access_violation_region_identification() {
        let config = Config::default();
        let original = [11, 22];
        let region = 0x10_0000_0000;
        let mut m = unsafe {
            MemoryMapping::new(
                vec![MemoryRegion::new(&raw const original, region)],
                &config,
                SBPFVersion::V4,
            )
            .unwrap()
        };
        let store_err_inbound = m.store(33u8, region).unwrap_err();
        assert_eq!(
            store_err_inbound.to_string(),
            "Access violation writing 1 bytes at address 0x1000000000 (in allocated region)"
        );
        let store_err_oob = m.load::<u64>(region + 3).unwrap_err();
        assert_eq!(
            store_err_oob.to_string(),
            "Access violation reading 8 bytes at address 0x1000000003 (in unallocated region)"
        );
    }

    #[test]
    fn v4_aligned_mapping() {
        let config = Config {
            aligned_memory_mapping: false,
            ..Config::default()
        };

        let mem = [11, 12];
        let mapping = unsafe {
            MemoryMapping::new_with_access_violation_handler(
                vec![MemoryRegion::new(&raw const mem, ebpf::MM_REGION_SIZE)],
                &config,
                SBPFVersion::V4,
                Box::new(default_access_violation_handler),
            )
            .unwrap()
        };

        assert!(matches!(mapping.ty, MemoryMappingType::Aligned(_)));
    }
}