#![allow(dead_code)]
use vmi_core::{Va, VmiError, VmiState, driver::VmiRead};
use crate::{LinuxOs, arch::ArchAdapter};
#[derive(Debug)]
enum MapleType {
Dense,
Leaf64,
Range64,
Arange64,
}
const fn xa_mk_internal(v: u64) -> Va {
Va::new((v << 2) | 2)
}
const fn xa_to_internal(entry: Va) -> u64 {
entry.0 >> 2
}
const fn xa_is_internal(entry: Va) -> bool {
(entry.0 & 3) == 2
}
const fn xa_is_zero(entry: Va) -> bool {
const XA_ZERO_ENTRY: Va = xa_mk_internal(257);
entry.0 == XA_ZERO_ENTRY.0
}
const fn xa_to_value(entry: Va) -> u64 {
entry.0 >> 1
}
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
}
const fn mt_is_reserved(entry: Va ) -> 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 ) -> 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 ) -> Va {
const MAPLE_NODE_MASK: u64 = 255;
Va::new(entry.0 & !MAPLE_NODE_MASK)
}
const fn mte_is_leaf(entry: Va ) -> bool {
match mte_node_type(entry) {
Some(typ) => ma_is_leaf(typ),
None => false,
}
}
pub struct MapleTreeIterator<'a, Driver>
where
Driver: VmiRead,
Driver::Architecture: ArchAdapter<Driver>,
{
vmi: VmiState<'a, LinuxOs<Driver>>,
root: Va,
node: Option<Va>,
index: u64,
last: u64,
min: u64,
max: u64,
offset: u8,
node_type: Option<MapleType>,
initialized: bool,
}
impl<'a, Driver> MapleTreeIterator<'a, Driver>
where
Driver: VmiRead,
Driver::Architecture: ArchAdapter<Driver>,
{
pub fn new(vmi: VmiState<'a, LinuxOs<Driver>>, root: Va) -> Self {
Self {
vmi,
root,
node: None,
index: 0,
last: u64::MAX,
min: 0,
max: u64::MAX,
offset: 0,
node_type: None,
initialized: false,
}
}
fn initialize(&mut self) -> Result<(), VmiError> {
if self.initialized {
return Ok(());
}
let offsets = &self.vmi.underlying_os().offsets;
let __maple_tree = &offsets.maple_tree;
let entry = self
.vmi
.read_va_native(self.root + __maple_tree.ma_root.offset())?;
if !xa_is_node(entry) {
self.node = Some(entry);
}
else if !entry.is_null() {
self.node = Some(entry);
self.node_type = mte_node_type(entry);
self.walk_to_first()?;
}
self.initialized = true;
Ok(())
}
fn walk_to_first(&mut self) -> Result<(), VmiError> {
while let Some(node) = self.node {
if mte_is_leaf(node) {
break;
}
let child = self.read_slot(0)?;
if child.is_null() {
break;
}
self.node = Some(child);
self.node_type = mte_node_type(child);
self.offset = 0;
}
Ok(())
}
fn walk_next(&mut self) -> Result<Option<Va>, VmiError> {
let Some(current_node) = self.node
else {
return Ok(None);
};
if !xa_is_node(current_node) {
let entry = if xa_is_value(current_node) {
Va::new(xa_to_value(current_node))
}
else if xa_is_zero(current_node) {
Va::new(xa_to_internal(current_node))
}
else if !mt_is_reserved(current_node) {
current_node
}
else {
return Ok(None);
};
self.offset += 1;
let next = match self.node_type {
Some(MapleType::Dense) => self.walk_next_dense()?,
Some(MapleType::Leaf64 | MapleType::Range64) => self.walk_next_range64()?,
Some(MapleType::Arange64) => self.walk_next_arange64()?,
None => None,
};
if let Some(next) = next {
self.node = Some(next);
}
else {
self.node = None;
}
return Ok(Some(entry));
}
let next = match self.node_type {
Some(MapleType::Dense) => self.walk_next_dense()?,
Some(MapleType::Leaf64 | MapleType::Range64) => self.walk_next_range64()?,
Some(MapleType::Arange64) => self.walk_next_arange64()?,
None => return Ok(None),
};
if let Some(next) = next {
self.node = Some(next);
self.walk_next()
}
else {
Ok(None)
}
}
fn walk_next_dense(&mut self) -> Result<Option<Va>, VmiError> {
let node = mte_to_node(self.node.unwrap());
let offsets = &self.vmi.underlying_os().offsets;
let __maple_node = &offsets.maple_node;
while self.offset < 31 {
self.offset += 1;
let slot = self
.vmi
.read_va_native(node + __maple_node.slot.offset() + (self.offset as u64 * 8))?;
if !slot.is_null() {
return Ok(Some(slot));
}
}
self.node = None;
Ok(None)
}
fn walk_next_range64(&mut self) -> Result<Option<Va>, VmiError> {
let node = mte_to_node(self.node.unwrap());
let offsets = &self.vmi.underlying_os().offsets;
let __maple_node = &offsets.maple_node;
let __maple_range_64 = &offsets.maple_range_64;
let node = node + __maple_node.mr64.offset();
if self.offset >= 16 {
return Ok(None);
}
let slot = self
.vmi
.read_va_native(node + __maple_range_64.slot.offset() + (self.offset as u64 * 8))?;
if slot.is_null() {
return Ok(None);
}
let last = if self.offset < 15 {
self.vmi
.read_u64(node + __maple_range_64.pivot.offset() + (self.offset as u64 * 8))?
}
else {
self.max
};
self.last = last;
if mte_is_leaf(self.node.unwrap()) {
Ok(Some(slot))
}
else {
self.node = Some(slot);
self.node_type = mte_node_type(slot);
self.offset = 0;
self.walk_to_first()?;
self.walk_next()
}
}
fn walk_next_arange64(&mut self) -> Result<Option<Va>, VmiError> {
let node = mte_to_node(self.node.unwrap());
let offsets = &self.vmi.underlying_os().offsets;
let __maple_node = &offsets.maple_node;
let __maple_arange_64 = &offsets.maple_arange_64;
let node = node + __maple_node.ma64.offset();
#[expect(clippy::never_loop)]
while self.offset < 10 {
self.offset += 1;
let slot = self.vmi.read_va_native(
node + __maple_arange_64.slot.offset() + (self.offset as u64 * 8),
)?;
if slot.is_null() {
self.node = None;
return Ok(None);
}
let last = if self.offset < 9 {
self.vmi
.read_u64(node + __maple_arange_64.pivot.offset() + (self.offset as u64 * 8))?
}
else {
self.max
};
self.last = last;
if mte_is_leaf(self.node.unwrap()) {
return Ok(Some(slot));
}
else {
self.node = Some(slot);
self.node_type = mte_node_type(slot);
self.offset = 0;
self.walk_to_first()?;
return self.walk_next();
}
}
self.node = None;
Ok(None)
}
fn read_slot(&self, offset: u8) -> Result<Va, VmiError> {
let node = mte_to_node(self.node.unwrap());
let offsets = &self.vmi.underlying_os().offsets;
let __maple_node = &offsets.maple_node;
match self.node_type {
Some(MapleType::Dense) => self
.vmi
.read_va_native(node + __maple_node.slot.offset() + (offset as u64 * 8)),
Some(MapleType::Leaf64 | MapleType::Range64) => {
let node = node + __maple_node.mr64.offset();
self.vmi.read_va_native(
node + offsets.maple_range_64.slot.offset() + (offset as u64 * 8),
)
}
Some(MapleType::Arange64) => {
let node = node + __maple_node.ma64.offset();
self.vmi.read_va_native(
node + offsets.maple_arange_64.slot.offset() + (offset as u64 * 8),
)
}
None => Ok(Va(0)),
}
}
}
impl<Driver> Iterator for MapleTreeIterator<'_, Driver>
where
Driver: VmiRead,
Driver::Architecture: ArchAdapter<Driver>,
{
type Item = Result<Va, VmiError>;
fn next(&mut self) -> Option<Self::Item> {
if !self.initialized
&& let Err(err) = self.initialize()
{
return Some(Err(err));
}
self.walk_next().transpose()
}
}