Skip to main content

vmi_os_linux/iter/
maple_tree.rs

1//! A MapleTree implementation based on the Linux kernel's data structure.
2//!
3//! The Maple Tree is a data structure used in the Linux kernel for efficiently storing
4//! and searching ranges of values. It's particularly used for managing virtual memory
5//! areas (VMAs) in the memory management subsystem.
6//!
7//! # References
8//!
9//! - [Linux Kernel Source - maple_tree.c](https://elixir.bootlin.com/linux/v6.10.5/source/lib/maple_tree.c)
10//! - [Linux Kernel Source - maple_tree.h](https://elixir.bootlin.com/linux/v6.10.5/source/include/linux/maple_tree.h)
11//! - [Process Address Space Documentation](https://students.mimuw.edu.pl/ZSO/Wyklady/04_processes2/ProcessAddressSpace.pdf)
12//! - [Maple Tree: Storing Ranges](https://blogs.oracle.com/linux/post/maple-tree-storing-ranges)
13//! - [Kernel Documentation - Maple Tree](https://docs.kernel.org/core-api/maple_tree.html)
14
15#![allow(dead_code)]
16use vmi_core::{Registers as _, Va, VmiError, VmiState, VmiVa, driver::VmiRead};
17
18use crate::{LinuxOs, Offsets, arch::ArchAdapter};
19
20/// Represents different node types in a Maple Tree.
21#[derive(Debug)]
22enum MapleType {
23    /// Dense nodes contain directly addressable slots.
24    Dense,
25
26    /// Leaf nodes.
27    Leaf64,
28
29    /// Range nodes.
30    Range64,
31
32    /// Allocation range nodes.
33    Arange64,
34}
35
36/// Create an internal entry.
37/// @v: Value to turn into an internal entry.
38///
39/// Internal entries are used for a number of purposes.  Entries 0-255 are
40/// used for sibling entries (only 0-62 are used by the current code).  256
41/// is used for the retry entry.  257 is used for the reserved / zero entry.
42/// Negative internal entries are used to represent errnos.  Node pointers
43/// are also tagged as internal entries in some situations.
44///
45/// Context: Any context.
46/// Return: An XArray internal entry corresponding to this value.
47const fn xa_mk_internal(v: u64) -> Va {
48    Va::new((v << 2) | 2)
49}
50
51/// Extract the value from an internal entry.
52/// @entry: XArray entry.
53///
54/// Context: Any context.
55/// Return: The value which was stored in the internal entry.
56const fn xa_to_internal(entry: Va) -> u64 {
57    entry.0 >> 2
58}
59
60/// Is the entry an internal entry?
61/// @entry: XArray entry.
62///
63/// Context: Any context.
64/// Return: %true if the entry is an internal entry.
65const fn xa_is_internal(entry: Va) -> bool {
66    (entry.0 & 3) == 2
67}
68
69/// Is the entry a zero entry?
70/// @entry: Entry retrieved from the XArray
71///
72/// The normal API will return NULL as the contents of a slot containing
73/// a zero entry.  You can only see zero entries by using the advanced API.
74///
75/// Return: %true if the entry is a zero entry.
76const fn xa_is_zero(entry: Va) -> bool {
77    const XA_ZERO_ENTRY: Va = xa_mk_internal(257);
78    entry.0 == XA_ZERO_ENTRY.0
79}
80
81/// Get value stored in an XArray entry.
82/// @entry: XArray entry.
83///
84/// Context: Any context.
85/// Return: The value stored in the XArray entry.
86const fn xa_to_value(entry: Va) -> u64 {
87    entry.0 >> 1
88}
89
90/// Determine if an entry is a value.
91/// @entry: XArray entry.
92///
93/// Context: Any context.
94/// Return: True if the entry is a value, false if it is a pointer.
95const fn xa_is_value(entry: Va) -> bool {
96    (entry.0 & 1) == 1
97}
98
99const fn xa_is_node(entry: Va) -> bool {
100    xa_is_internal(entry) && entry.0 > 4096
101}
102
103const fn mt_flags_height(ma_flags: u32) -> u32 {
104    const MT_FLAGS_HEIGHT_OFFSET: u32 = 0x02;
105    const MT_FLAGS_HEIGHT_MASK: u32 = 0x7C;
106
107    (ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET
108}
109
110/// We also reserve values with the bottom two bits set to '10' which are
111/// below 4096
112const fn mt_is_reserved(entry: Va /* void* */) -> bool {
113    const MAPLE_RESERVED_RANGE: u64 = 4096;
114    (entry.0 < MAPLE_RESERVED_RANGE) && xa_is_internal(entry)
115}
116
117const fn mt_node_max(entry: Va) -> Option<u64> {
118    match mte_node_type(entry) {
119        Some(MapleType::Dense) => Some(31),
120        Some(MapleType::Leaf64) => Some(u64::MAX),
121        Some(MapleType::Range64) => Some(u64::MAX),
122        Some(MapleType::Arange64) => Some(u64::MAX),
123        None => None,
124    }
125}
126
127const fn mte_node_type(entry: Va /* maple_enode */) -> Option<MapleType> {
128    const MAPLE_NODE_TYPE_MASK: u64 = 0x0F;
129    const MAPLE_NODE_TYPE_SHIFT: u64 = 0x03;
130    match (entry.0 >> MAPLE_NODE_TYPE_SHIFT) & MAPLE_NODE_TYPE_MASK {
131        0x00 => Some(MapleType::Dense),
132        0x01 => Some(MapleType::Leaf64),
133        0x02 => Some(MapleType::Range64),
134        0x03 => Some(MapleType::Arange64),
135        _ => None,
136    }
137}
138
139const fn ma_is_leaf(typ: MapleType) -> bool {
140    matches!(typ, MapleType::Dense | MapleType::Leaf64)
141}
142
143const fn mte_to_node(entry: Va /* maple_enode */) -> Va {
144    const MAPLE_NODE_MASK: u64 = 255;
145    Va::new(entry.0 & !MAPLE_NODE_MASK)
146}
147
148const fn mte_is_leaf(entry: Va /* maple_enode */) -> bool {
149    match mte_node_type(entry) {
150        Some(typ) => ma_is_leaf(typ),
151        None => false,
152    }
153}
154
155/// A MapleTree traversal and manipulation implementation.
156///
157/// This struct provides methods for traversing and inspecting Linux kernel
158/// Maple Trees, which are used primarily for managing virtual memory areas.
159pub struct MapleTree<'a, Driver>
160where
161    Driver: VmiRead,
162    Driver::Architecture: ArchAdapter<Driver>,
163{
164    /// The VMI state.
165    vmi: VmiState<'a, LinuxOs<Driver>>,
166
167    /// The virtual address of the Maple Tree root.
168    root: Va,
169}
170
171impl<Driver> VmiVa for MapleTree<'_, Driver>
172where
173    Driver: VmiRead,
174    Driver::Architecture: ArchAdapter<Driver>,
175{
176    fn va(&self) -> Va {
177        self.root
178    }
179}
180
181impl<'a, Driver> MapleTree<'a, Driver>
182where
183    Driver: VmiRead,
184    Driver::Architecture: ArchAdapter<Driver>,
185{
186    /// Creates a new MapleTree instance.
187    pub fn new(vmi: VmiState<'a, LinuxOs<Driver>>, root: Va) -> Self {
188        Self { vmi, root }
189    }
190
191    fn offsets(&self) -> &Offsets {
192        &self.vmi.underlying_os().offsets
193    }
194
195    // region: Enumerate
196
197    /// Enumerates all entries in the Maple Tree.
198    ///
199    /// Traverses the tree structure and calls the provided callback for each entry found.
200    pub fn enumerate(&self, mut callback: impl FnMut(Va) -> bool) -> Result<(), VmiError> {
201        let offsets = self.offsets();
202        let __maple_tree = &offsets.maple_tree;
203
204        let entry = self
205            .vmi
206            .read_va_native(self.root + __maple_tree.ma_root.offset())?;
207
208        if !xa_is_node(entry) {
209            self.enumerate_entry(entry, &mut callback);
210        }
211        else if !entry.is_null() {
212            self.enumerate_node(self.root, entry, 0, u64::MAX, &mut callback)?;
213        }
214
215        Ok(())
216    }
217
218    fn enumerate_entry(&self, entry: Va, callback: &mut impl FnMut(Va) -> bool) {
219        if xa_is_value(entry) {
220            callback(Va(xa_to_value(entry)));
221        }
222        else if xa_is_zero(entry) {
223            callback(Va(xa_to_internal(entry)));
224        }
225        else {
226            callback(entry);
227        }
228    }
229
230    fn enumerate_node(
231        &self,
232        mt: Va,
233        entry: Va,
234        min: u64,
235        max: u64,
236        callback: &mut impl FnMut(Va) -> bool,
237    ) -> Result<(), VmiError> {
238        let offsets = self.offsets();
239        let __maple_tree = &offsets.maple_tree;
240        let __maple_node = &offsets.maple_node;
241
242        let node = mte_to_node(entry);
243        let typ = mte_node_type(entry);
244
245        match typ {
246            Some(MapleType::Dense) => {
247                // const MAPLE_NODE_SLOTS: u64 = 63;   // 32 bit OS
248                const MAPLE_NODE_SLOTS: u64 = 31; // 64 bit OS
249                for i in 0..MAPLE_NODE_SLOTS {
250                    let slot = self
251                        .vmi
252                        .read_va_native(node + __maple_node.slot.offset() + i * 8)?;
253
254                    if !slot.is_null() {
255                        self.enumerate_entry(slot, callback);
256                    }
257                }
258            }
259            Some(MapleType::Leaf64 | MapleType::Range64) => {
260                self.enumerate_range64(mt, entry, min, max, callback)?;
261            }
262            Some(MapleType::Arange64) => {
263                self.enumerate_arange64(mt, entry, min, max, callback)?;
264            }
265            None => tracing::warn!(?typ, "unknown node type"),
266        }
267
268        Ok(())
269    }
270
271    fn enumerate_range64(
272        &self,
273        mt: Va,
274        entry: Va,
275        min: u64,
276        max: u64,
277        callback: &mut impl FnMut(Va) -> bool,
278    ) -> Result<(), VmiError> {
279        let offsets = self.offsets();
280        let __maple_node = &offsets.maple_node;
281        let __maple_range_64 = &offsets.maple_range_64;
282
283        let node = mte_to_node(entry) + __maple_node.mr64.offset();
284        let leaf = mte_is_leaf(entry);
285        let mut first = min;
286
287        const MAPLE_RANGE64_SLOTS_32: u64 = 32; // 32 bit OS
288        const MAPLE_RANGE64_SLOTS_64: u64 = 16; // 64 bit OS
289
290        #[expect(non_snake_case)]
291        let MAPLE_RANGE64_SLOTS = match self.vmi.registers().address_width() {
292            4 => MAPLE_RANGE64_SLOTS_32,
293            8 => MAPLE_RANGE64_SLOTS_64,
294            _ => 0,
295        };
296
297        let __pivot = |i: u64| {
298            let offset = i * self.vmi.registers().address_width() as u64;
299            self.vmi
300                .read_va_native(node + __maple_range_64.pivot.offset() + offset)
301                .map(u64::from)
302        };
303
304        let __slot = |i: u64| {
305            let offset = i * self.vmi.registers().address_width() as u64;
306            self.vmi
307                .read_va_native(node + __maple_range_64.slot.offset() + offset)
308        };
309
310        for i in 0..MAPLE_RANGE64_SLOTS {
311            let mut last = max;
312
313            if i < (MAPLE_RANGE64_SLOTS - 1) {
314                last = __pivot(i)?;
315            }
316            else {
317                let slot = __slot(i)?;
318                if slot.is_null() && Some(max) != mt_node_max(entry) {
319                    break;
320                }
321            }
322
323            if last == 0 && i > 0 {
324                break;
325            }
326
327            let slot = __slot(i)?;
328
329            if leaf {
330                self.enumerate_entry(slot, callback)
331            }
332            else if !slot.is_null() {
333                self.enumerate_node(mt, slot, first, last, callback)?;
334            }
335
336            if last == max {
337                break;
338            }
339
340            first = last + 1;
341        }
342
343        Ok(())
344    }
345
346    fn enumerate_arange64(
347        &self,
348        mt: Va,
349        entry: Va,
350        min: u64,
351        max: u64,
352        callback: &mut impl FnMut(Va) -> bool,
353    ) -> Result<(), VmiError> {
354        let offsets = self.offsets();
355        let __maple_node = &offsets.maple_node;
356        let __maple_arange_64 = &offsets.maple_arange_64;
357
358        let node = mte_to_node(entry) + __maple_node.ma64.offset();
359        let leaf = mte_is_leaf(entry);
360        let mut first = min;
361
362        const MAPLE_ARANGE64_SLOTS_32: u64 = 21; // 32 bit OS
363        const MAPLE_ARANGE64_SLOTS_64: u64 = 10; // 64 bit OS
364
365        #[expect(non_snake_case)]
366        let MAPLE_ARANGE64_SLOTS = match self.vmi.registers().address_width() {
367            4 => MAPLE_ARANGE64_SLOTS_32,
368            8 => MAPLE_ARANGE64_SLOTS_64,
369            _ => 0,
370        };
371
372        let __pivot = |i: u64| {
373            let offset = i * self.vmi.registers().address_width() as u64;
374            self.vmi
375                .read_va_native(node + __maple_arange_64.pivot.offset() + offset)
376                .map(u64::from)
377        };
378
379        let __slot = |i: u64| {
380            let offset = i * self.vmi.registers().address_width() as u64;
381            self.vmi
382                .read_va_native(node + __maple_arange_64.slot.offset() + offset)
383        };
384
385        for i in 0..MAPLE_ARANGE64_SLOTS {
386            let mut last = max;
387
388            if i < (MAPLE_ARANGE64_SLOTS - 1) {
389                last = __pivot(i)?;
390            }
391            else {
392                let slot = __slot(i)?;
393                if slot.is_null() {
394                    break;
395                }
396            }
397
398            if last == 0 && i > 0 {
399                break;
400            }
401
402            let slot = __slot(i)?;
403
404            if leaf {
405                self.enumerate_entry(slot, callback)
406            }
407            else if !slot.is_null() {
408                self.enumerate_node(mt, slot, first, last, callback)?;
409            }
410
411            if last == max {
412                break;
413            }
414
415            first = last + 1;
416        }
417
418        Ok(())
419    }
420
421    // endregion
422
423    // region: Dump
424
425    /// Dumps the entire Maple Tree structure for debugging.
426    pub fn dump(&self) -> Result<(), VmiError> {
427        let offsets = self.offsets();
428        let __maple_tree = &offsets.maple_tree;
429
430        let flags = self
431            .vmi
432            .read_u32(self.root + __maple_tree.ma_flags.offset())?;
433        let entry = self
434            .vmi
435            .read_va_native(self.root + __maple_tree.ma_root.offset())?;
436
437        println!(
438            "maple_tree({}) flags {:X}, height {} root {:X}",
439            self.root,
440            flags,
441            mt_flags_height(flags),
442            entry
443        );
444
445        if !xa_is_node(entry) {
446            self.dump_entry(entry, 0, 0, 0);
447        }
448        else if !entry.is_null() {
449            self.dump_node(self.root, entry, 0, u64::MAX, 0)?;
450        }
451
452        Ok(())
453    }
454
455    fn dump_range(&self, min: u64, max: u64, depth: u64) {
456        if min == max {
457            println!("{:width$}{:X}: ", "", min, width = (depth * 2) as usize);
458        }
459        else {
460            println!(
461                "{:width$}{:X}-{:X}: ",
462                "",
463                min,
464                max,
465                width = (depth * 2) as usize
466            );
467        }
468    }
469
470    fn dump_entry(&self, entry: Va, _min: u64, _max: u64, depth: u64) {
471        print!("{:width$}", "", width = (depth * 2) as usize);
472
473        if xa_is_value(entry) {
474            println!("Value: {:#x}", xa_to_value(entry));
475        }
476        else if xa_is_zero(entry) {
477            println!("Zero: {:?}", xa_to_internal(entry));
478        }
479        else if mt_is_reserved(entry) {
480            println!("Reserved: {:?}", entry);
481        }
482        else {
483            println!("{:?}", entry);
484            if entry.is_null() {
485                return;
486            }
487
488            let offsets = self.offsets();
489            let __vm_area_struct = &offsets.vm_area_struct;
490
491            let start = self
492                .vmi
493                .read_u64(entry + __vm_area_struct.vm_start.offset());
494            let end = self.vmi.read_u64(entry + __vm_area_struct.vm_end.offset());
495            let file = self
496                .vmi
497                .read_va_native(entry + __vm_area_struct.vm_file.offset());
498            println!("Range: {:X?}-{:X?}", start, end);
499
500            if let Ok(file) = file
501                && !file.is_null()
502            {
503                let __dentry = &offsets.dentry;
504                let __file = &offsets.file;
505                let __path = &offsets.path;
506                let __qstr = &offsets.qstr;
507
508                let f_path = file + __file.f_path.offset();
509
510                if let Ok(dentry) = self.vmi.read_va_native(f_path + __path.dentry.offset())
511                    && let Ok(d_name) = self
512                        .vmi
513                        .read_va_native(dentry + __dentry.d_name.offset() + __qstr.name.offset())
514                {
515                    let name = self.vmi.read_string(d_name);
516                    println!("    File: {:?}", name);
517                }
518            }
519        }
520    }
521
522    fn dump_node(&self, mt: Va, entry: Va, min: u64, max: u64, depth: u64) -> Result<(), VmiError> {
523        let offsets = self.offsets();
524        let __maple_tree = &offsets.maple_tree;
525        let __maple_node = &offsets.maple_node;
526
527        let node = mte_to_node(entry);
528        let typ = mte_node_type(entry);
529
530        self.dump_range(min, max, depth);
531
532        println!(
533            "node {:X} depth {} type {:?} parent {:?}",
534            node,
535            depth,
536            mte_node_type(entry),
537            if !node.is_null() {
538                self.vmi.read_va_native(node + __maple_node.parent.offset())
539            }
540            else {
541                Ok(Va::default())
542            }
543        );
544
545        match typ {
546            Some(MapleType::Dense) => {
547                // const MAPLE_NODE_SLOTS: u64 = 63;   // 32 bit OS
548                const MAPLE_NODE_SLOTS: u64 = 31; // 64 bit OS
549                for i in 0..MAPLE_NODE_SLOTS {
550                    let slot = self
551                        .vmi
552                        .read_va_native(node + __maple_node.slot.offset() + i * 8)?;
553
554                    if !slot.is_null() {
555                        self.dump_entry(slot, min, max, depth);
556                    }
557                }
558            }
559            Some(MapleType::Leaf64 | MapleType::Range64) => {
560                self.dump_range64(mt, entry, min, max, depth)?;
561            }
562            Some(MapleType::Arange64) => {
563                self.dump_arange64(mt, entry, min, max, depth)?;
564            }
565            None => tracing::warn!(?typ, "unknown node type"),
566        }
567
568        Ok(())
569    }
570
571    fn dump_range64(
572        &self,
573        mt: Va,
574        entry: Va,
575        min: u64,
576        max: u64,
577        depth: u64,
578    ) -> Result<(), VmiError> {
579        let offsets = self.offsets();
580        let __maple_node = &offsets.maple_node;
581        let __maple_range_64 = &offsets.maple_range_64;
582
583        let node = mte_to_node(entry) + __maple_node.mr64.offset();
584        let leaf = mte_is_leaf(entry);
585        let mut first = min;
586
587        // const MAPLE_RANGE64_SLOTS: u64 = 32;   // 32 bit OS
588        const MAPLE_RANGE64_SLOTS: u64 = 16; // 64 bit OS
589
590        let __pivot = |i: u64| {
591            let offset = i * size_of::<u64>() as u64;
592            self.vmi
593                .read_u64(node + __maple_range_64.pivot.offset() + offset)
594        };
595
596        let __slot = |i: u64| {
597            let offset = i * self.vmi.registers().address_width() as u64;
598            self.vmi
599                .read_va_native(node + __maple_range_64.slot.offset() + offset)
600        };
601
602        for i in 0..MAPLE_RANGE64_SLOTS - 1 {
603            println!("pivot {:X} slot {:X}", __pivot(i)?, __slot(i)?);
604        }
605        println!("slot {:X}", __slot(MAPLE_RANGE64_SLOTS - 1)?);
606
607        for i in 0..MAPLE_RANGE64_SLOTS {
608            let mut last = max;
609
610            if i < (MAPLE_RANGE64_SLOTS - 1) {
611                last = __pivot(i)?;
612            }
613            else {
614                let slot = __slot(i)?;
615                if slot.is_null() && Some(max) != mt_node_max(entry) {
616                    break;
617                }
618            }
619
620            if last == 0 && i > 0 {
621                break;
622            }
623
624            let slot = __slot(i)?;
625
626            if leaf {
627                self.dump_entry(slot, first, last, depth + 1)
628            }
629            else if !slot.is_null() {
630                self.dump_node(mt, slot, first, last, depth + 1)?;
631            }
632
633            if last == max {
634                break;
635            }
636
637            first = last + 1;
638        }
639
640        Ok(())
641    }
642
643    fn dump_arange64(
644        &self,
645        mt: Va,
646        entry: Va,
647        min: u64,
648        max: u64,
649        depth: u64,
650    ) -> Result<(), VmiError> {
651        let offsets = self.offsets();
652        let __maple_node = &offsets.maple_node;
653        let __maple_arange_64 = &offsets.maple_arange_64;
654
655        let node = mte_to_node(entry) + __maple_node.ma64.offset();
656        let leaf = mte_is_leaf(entry);
657        let mut first = min;
658
659        // const MAPLE_ARANGE64_SLOTS: u64 = 21;   // 32 bit OS
660        const MAPLE_ARANGE64_SLOTS: u64 = 10; // 64 bit OS
661
662        let __pivot = |i: u64| {
663            let offset = i * size_of::<u64>() as u64;
664            self.vmi
665                .read_u64(node + __maple_arange_64.pivot.offset() + offset)
666        };
667
668        let __slot = |i: u64| {
669            let offset = i * self.vmi.registers().address_width() as u64;
670            self.vmi
671                .read_va_native(node + __maple_arange_64.slot.offset() + offset)
672        };
673
674        for i in 0..MAPLE_ARANGE64_SLOTS - 1 {
675            println!("pivot {:X} slot {:X}", __pivot(i)?, __slot(i)?);
676        }
677        println!("slot {:X}", __slot(MAPLE_ARANGE64_SLOTS - 1)?);
678
679        for i in 0..MAPLE_ARANGE64_SLOTS {
680            let mut last = max;
681
682            if i < (MAPLE_ARANGE64_SLOTS - 1) {
683                last = __pivot(i)?;
684            }
685            else {
686                let slot = __slot(i)?;
687                if slot.is_null() {
688                    break;
689                }
690            }
691
692            if last == 0 && i > 0 {
693                break;
694            }
695
696            let slot = __slot(i)?;
697
698            if leaf {
699                self.dump_entry(slot, first, last, depth + 1)
700            }
701            else if !slot.is_null() {
702                self.dump_node(mt, slot, first, last, depth + 1)?;
703            }
704
705            if last == max {
706                break;
707            }
708
709            first = last + 1;
710        }
711
712        Ok(())
713    }
714
715    // endregion
716}