//! 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>,
{
}