vmi-os-linux 0.13.0

Linux OS specific code for VMI
Documentation
//! A MapleTree implementation based on the Linux kernel's data structure.
//!
//! The Maple Tree is a data structure used in the Linux kernel for efficiently storing
//! and searching ranges of values. It's particularly used for managing virtual memory
//! areas (VMAs) in the memory management subsystem.
//!
//! # References
//!
//! - [Linux Kernel Source - maple_tree.c](https://elixir.bootlin.com/linux/v6.10.5/source/lib/maple_tree.c)
//! - [Linux Kernel Source - maple_tree.h](https://elixir.bootlin.com/linux/v6.10.5/source/include/linux/maple_tree.h)
//! - [Process Address Space Documentation](https://students.mimuw.edu.pl/ZSO/Wyklady/04_processes2/ProcessAddressSpace.pdf)
//! - [Maple Tree: Storing Ranges](https://blogs.oracle.com/linux/post/maple-tree-storing-ranges)
//! - [Kernel Documentation - Maple Tree](https://docs.kernel.org/core-api/maple_tree.html)

#![allow(dead_code)]
use std::iter::FusedIterator;

use vmi_core::{Architecture, Registers as _, Va, VmiDriver, VmiError, VmiState};

use crate::{ArchAdapter, LinuxOs, Offsets};

/// Represents different node types in a Maple Tree.
#[derive(Debug)]
enum MapleType {
    /// Dense nodes contain directly addressable slots.
    Dense,

    /// Leaf nodes.
    Leaf64,

    /// Range nodes.
    Range64,

    /// Allocation range nodes.
    Arange64,
}

/// Create an internal entry.
/// @v: Value to turn into an internal entry.
///
/// Internal entries are used for a number of purposes.  Entries 0-255 are
/// used for sibling entries (only 0-62 are used by the current code).  256
/// is used for the retry entry.  257 is used for the reserved / zero entry.
/// Negative internal entries are used to represent errnos.  Node pointers
/// are also tagged as internal entries in some situations.
///
/// Context: Any context.
/// Return: An XArray internal entry corresponding to this value.
const fn xa_mk_internal(v: u64) -> Va {
    Va::new((v << 2) | 2)
}

/// Extract the value from an internal entry.
/// @entry: XArray entry.
///
/// Context: Any context.
/// Return: The value which was stored in the internal entry.
const fn xa_to_internal(entry: Va) -> u64 {
    entry.0 >> 2
}

/// Is the entry an internal entry?
/// @entry: XArray entry.
///
/// Context: Any context.
/// Return: %true if the entry is an internal entry.
const fn xa_is_internal(entry: Va) -> bool {
    (entry.0 & 3) == 2
}

/// Is the entry a zero entry?
/// @entry: Entry retrieved from the XArray
///
/// The normal API will return NULL as the contents of a slot containing
/// a zero entry.  You can only see zero entries by using the advanced API.
///
/// Return: %true if the entry is a zero entry.
const fn xa_is_zero(entry: Va) -> bool {
    const XA_ZERO_ENTRY: Va = xa_mk_internal(257);
    entry.0 == XA_ZERO_ENTRY.0
}

/// Get value stored in an XArray entry.
/// @entry: XArray entry.
///
/// Context: Any context.
/// Return: The value stored in the XArray entry.
const fn xa_to_value(entry: Va) -> u64 {
    entry.0 >> 1
}

/// Determine if an entry is a value.
/// @entry: XArray entry.
///
/// Context: Any context.
/// Return: True if the entry is a value, false if it is a pointer.
const fn xa_is_value(entry: Va) -> bool {
    (entry.0 & 1) == 1
}

const fn xa_is_node(entry: Va) -> bool {
    xa_is_internal(entry) && entry.0 > 4096
}

const fn mt_flags_height(ma_flags: u32) -> u32 {
    const MT_FLAGS_HEIGHT_OFFSET: u32 = 0x02;
    const MT_FLAGS_HEIGHT_MASK: u32 = 0x7C;

    (ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET
}

/// We also reserve values with the bottom two bits set to '10' which are
/// below 4096
const fn mt_is_reserved(entry: Va /* void* */) -> bool {
    const MAPLE_RESERVED_RANGE: u64 = 4096;
    (entry.0 < MAPLE_RESERVED_RANGE) && xa_is_internal(entry)
}

const fn mt_node_max(entry: Va) -> Option<u64> {
    match mte_node_type(entry) {
        Some(MapleType::Dense) => Some(31),
        Some(MapleType::Leaf64) => Some(u64::MAX),
        Some(MapleType::Range64) => Some(u64::MAX),
        Some(MapleType::Arange64) => Some(u64::MAX),
        None => None,
    }
}

const fn mte_node_type(entry: Va /* maple_enode */) -> Option<MapleType> {
    const MAPLE_NODE_TYPE_MASK: u64 = 0x0F;
    const MAPLE_NODE_TYPE_SHIFT: u64 = 0x03;
    match (entry.0 >> MAPLE_NODE_TYPE_SHIFT) & MAPLE_NODE_TYPE_MASK {
        0x00 => Some(MapleType::Dense),
        0x01 => Some(MapleType::Leaf64),
        0x02 => Some(MapleType::Range64),
        0x03 => Some(MapleType::Arange64),
        _ => None,
    }
}

const fn ma_is_leaf(typ: MapleType) -> bool {
    matches!(typ, MapleType::Dense | MapleType::Leaf64)
}

const fn mte_to_node(entry: Va /* maple_enode */) -> Va {
    const MAPLE_NODE_MASK: u64 = 255;
    Va::new(entry.0 & !MAPLE_NODE_MASK)
}

const fn mte_is_leaf(entry: Va /* maple_enode */) -> bool {
    match mte_node_type(entry) {
        Some(typ) => ma_is_leaf(typ),
        None => false,
    }
}

pub struct MapleTreeIterator<'a, Driver>
where
    Driver: VmiDriver,
    Driver::Architecture: Architecture + ArchAdapter<Driver>,
{
    vmi: VmiState<'a, Driver, LinuxOs<Driver>>,
    root: Va,
    stack: Vec<Va>,
    done: bool,
}

impl<'a, Driver> MapleTreeIterator<'a, Driver>
where
    Driver: VmiDriver,
    Driver::Architecture: Architecture + ArchAdapter<Driver>,
{
    pub fn new(vmi: VmiState<'a, Driver, LinuxOs<Driver>>, root: Va) -> Result<Self, VmiError> {
        Ok(Self {
            vmi,
            root,
            stack: Vec::new(),
            done: false,
        })
    }

    fn offsets(&self) -> &Offsets {
        &self.vmi.underlying_os().offsets
    }

    fn parent(&self, node: Va) -> Result<Va, VmiError> {
        let offsets = self.offsets();
        let __maple_node = &offsets.maple_node;

        self.vmi.read_va_native(node + __maple_node.parent.offset())
    }

    fn num_slots(&self, node: Va) -> Result<u64, VmiError> {
        let address_width = self.vmi.registers().address_width();

        match mte_node_type(node) {
            Some(MapleType::Dense) => {
                const MAPLE_NODE_SLOTS_32: u64 = 63; // 32 bit OS
                const MAPLE_NODE_SLOTS_64: u64 = 31; // 64 bit OS

                match address_width {
                    4 => Ok(MAPLE_NODE_SLOTS_32),
                    8 => Ok(MAPLE_NODE_SLOTS_64),
                    _ => Err(VmiError::NotSupported),
                }
            }
            Some(MapleType::Leaf64 | MapleType::Range64) => {
                const MAPLE_RANGE64_SLOTS_32: u64 = 32; // 32 bit OS
                const MAPLE_RANGE64_SLOTS_64: u64 = 16; // 64 bit OS

                match address_width {
                    4 => Ok(MAPLE_RANGE64_SLOTS_32),
                    8 => Ok(MAPLE_RANGE64_SLOTS_64),
                    _ => Err(VmiError::NotSupported),
                }
            }
            Some(MapleType::Arange64) => {
                const MAPLE_ARANGE64_SLOTS_32: u64 = 21; // 32 bit OS
                const MAPLE_ARANGE64_SLOTS_64: u64 = 10; // 64 bit OS

                match address_width {
                    4 => Ok(MAPLE_ARANGE64_SLOTS_32),
                    8 => Ok(MAPLE_ARANGE64_SLOTS_64),
                    _ => Err(VmiError::NotSupported),
                }
            }
            None => Err(VmiError::NotSupported),
        }
    }

    fn slot(&self, node: Va, slot: u64) -> Result<Va, VmiError> {
        let offsets = self.offsets();
        let __maple_node = &offsets.maple_node;
        let __maple_range_64 = &offsets.maple_range_64;
        let __maple_arange_64 = &offsets.maple_arange_64;

        let address_width = self.vmi.registers().address_width() as u64;
        let array_offset = slot * address_width;

        let offset = match mte_node_type(node) {
            Some(MapleType::Dense) => __maple_node.slot.offset() + array_offset,
            Some(MapleType::Leaf64) => __maple_range_64.slot.offset() + array_offset,
            Some(MapleType::Range64) => __maple_range_64.slot.offset() + array_offset,
            Some(MapleType::Arange64) => __maple_arange_64.slot.offset() + array_offset,
            _ => return Err(VmiError::NotSupported),
        };

        self.vmi.read_va_native(node + offset)
    }

    fn pivot(&self, node: Va, slot: u64) -> Result<u64, VmiError> {
        let offsets = self.offsets();
        let __maple_range_64 = &offsets.maple_range_64;
        let __maple_arange_64 = &offsets.maple_arange_64;

        let address_width = self.vmi.registers().address_width() as u64;
        let array_offset = slot * address_width;

        let offset = match mte_node_type(node) {
            Some(MapleType::Leaf64) => __maple_range_64.pivot.offset() + array_offset,
            Some(MapleType::Range64) => __maple_range_64.pivot.offset() + array_offset,
            Some(MapleType::Arange64) => __maple_arange_64.pivot.offset() + array_offset,
            _ => return Err(VmiError::NotSupported),
        };

        Ok(self.vmi.read_va_native(node + offset)?.0)
    }

    fn __next(&mut self) -> Result<Option<Va>, VmiError> {
        Ok(None)
    }
}

impl<Driver> Iterator for MapleTreeIterator<'_, Driver>
where
    Driver: VmiDriver,
    Driver::Architecture: Architecture + ArchAdapter<Driver>,
{
    type Item = Result<Va, VmiError>;

    fn next(&mut self) -> Option<Self::Item> {
        self.__next().transpose()
    }
}

impl<Driver> FusedIterator for MapleTreeIterator<'_, Driver>
where
    Driver: VmiDriver,
    Driver::Architecture: Architecture + ArchAdapter<Driver>,
{
}