1#![allow(dead_code)]
16use vmi_core::{Registers as _, Va, VmiError, VmiState, VmiVa, driver::VmiRead};
17
18use crate::{LinuxOs, Offsets, arch::ArchAdapter};
19
20#[derive(Debug)]
22enum MapleType {
23 Dense,
25
26 Leaf64,
28
29 Range64,
31
32 Arange64,
34}
35
36const fn xa_mk_internal(v: u64) -> Va {
48 Va::new((v << 2) | 2)
49}
50
51const fn xa_to_internal(entry: Va) -> u64 {
57 entry.0 >> 2
58}
59
60const fn xa_is_internal(entry: Va) -> bool {
66 (entry.0 & 3) == 2
67}
68
69const 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
81const fn xa_to_value(entry: Va) -> u64 {
87 entry.0 >> 1
88}
89
90const 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
110const fn mt_is_reserved(entry: Va ) -> 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 ) -> 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 ) -> 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 ) -> bool {
149 match mte_node_type(entry) {
150 Some(typ) => ma_is_leaf(typ),
151 None => false,
152 }
153}
154
155pub struct MapleTree<'a, Driver>
160where
161 Driver: VmiRead,
162 Driver::Architecture: ArchAdapter<Driver>,
163{
164 vmi: VmiState<'a, LinuxOs<Driver>>,
166
167 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 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 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 = 31; 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; const MAPLE_RANGE64_SLOTS_64: u64 = 16; #[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; const MAPLE_ARANGE64_SLOTS_64: u64 = 10; #[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 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 = 31; 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 = 16; 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 = 10; 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 }