page_table_generic/
walk.rs

1use crate::{FrameAllocator, PageTableEntry, PageTableRef, TableMeta, VirtAddr, frame::Frame};
2
3use heapless::Vec;
4
5/// Maximum stack depth for page table walker
6const MAX_WALK_DEPTH: usize = 8;
7
8/// 页表项信息，包含原PTE对象
9#[derive(Debug, Clone, Copy)]
10pub struct PteInfo<P: PageTableEntry> {
11    /// 页表级别（1=叶子页表，数字越大级别越高）
12    pub level: usize,
13    /// 此页表项对应的虚拟地址
14    pub vaddr: VirtAddr,
15    /// 此页表项是否为最终映射（叶子级别或大页）
16    /// - true: 有效的叶子级别映射或大页映射
17    /// - false: 无效项或中间级别的页表指针
18    pub is_final_mapping: bool,
19    /// 原页表项对象
20    pub pte: P,
21}
22
23/// 页表遍历配置
24#[derive(Debug, Clone, Copy)]
25pub struct WalkConfig {
26    /// 起始虚拟地址（包含）
27    pub start_vaddr: VirtAddr,
28    /// 结束虚拟地址（不包含）
29    pub end_vaddr: VirtAddr,
30}
31
32/// 页表遍历迭代器
33pub struct PageTableWalker<'a, T: TableMeta, A: FrameAllocator> {
34    _phantom: core::marker::PhantomData<&'a ()>,
35    config: WalkConfig,
36    // 内部状态管理 - 使用heapless::Vec
37    stack: Vec<WalkState<T, A>, MAX_WALK_DEPTH>,
38    finished: bool,
39}
40
41/// 遍历状态
42#[derive(Clone, Copy)]
43struct WalkState<T: TableMeta, A: FrameAllocator> {
44    frame: Frame<T, A>,
45    level: usize,
46    index: usize,
47    base_vaddr: VirtAddr,
48}
49
50impl<'a, T: TableMeta, A: FrameAllocator> PageTableWalker<'a, T, A> {
51    /// 创建新的页表遍历器
52    pub fn new(page_table: &'a PageTableRef<T, A>, config: WalkConfig) -> Self {
53        let mut walker = Self {
54            _phantom: core::marker::PhantomData,
55            config,
56            stack: Vec::new(),
57            finished: false,
58        };
59
60        // 初始化栈，从根页表开始
61        if walker.config.start_vaddr < walker.config.end_vaddr {
62            let root_state = WalkState {
63                frame: Frame::from_paddr(page_table.root.paddr, page_table.root.allocator.clone()),
64                level: Frame::<T, A>::PT_LEVEL,
65                index: 0,
66                base_vaddr: VirtAddr::new(0),
67            };
68            walker.stack.push(root_state).ok(); // 栈容量足够时一定成功
69        } else {
70            walker.finished = true;
71        }
72
73        walker
74    }
75
76    /// 查找下一个页表项（遍历所有项）
77    fn find_next_entry(&mut self) -> Option<PteInfo<T::P>> {
78        loop {
79            if self.finished {
80                return None;
81            }
82
83            if self.stack.is_empty() {
84                self.finished = true;
85                return None;
86            }
87
88            let state = self.stack.last_mut().unwrap();
89
90            // 检查当前级别是否还有更多条目
91            if state.index >= Frame::<T, A>::LEN {
92                self.stack.pop();
93                continue;
94            }
95
96            // 获取页表项
97            let entries = state.frame.as_slice();
98            let pte = entries[state.index];
99            state.index += 1;
100
101            // 获取当前条目的虚拟地址 - 重建完整的虚拟地址
102            let current_vaddr =
103                Frame::<T, A>::reconstruct_vaddr(state.index - 1, state.level, state.base_vaddr);
104
105            // 跳过不在范围内的地址
106            if current_vaddr < self.config.start_vaddr {
107                continue;
108            }
109
110            if current_vaddr >= self.config.end_vaddr {
111                self.finished = true;
112                return None;
113            }
114
115            // 判断是否为最终映射
116            // - 无效项：不是最终映射
117            // - 有效且是大页：是最终映射
118            // - 有效且在叶子级别（level == 1）：是最终映射
119            // - 有效但在中间级别且不是大页：不是最终映射（页表指针）
120            let pte_config = pte.to_config(state.level > 1);
121            let is_final_mapping = pte_config.valid && (pte_config.huge || state.level == 1);
122
123            // 如果是有效的子页表项（中间级别的页表指针），需要深入下一级
124            if pte_config.valid && !pte_config.huge && state.level > 1 {
125                let child_frame =
126                    Frame::from_paddr(pte_config.paddr, state.frame.allocator.clone());
127
128                // 计算子页表的基地址：当前条目的虚拟地址就是子页表覆盖的地址范围起点
129                let child_base_vaddr = current_vaddr;
130
131                // 创建子页表状态并压入栈中
132                let child_state = WalkState {
133                    frame: child_frame,
134                    level: state.level - 1,
135                    index: 0,
136                    base_vaddr: child_base_vaddr,
137                };
138
139                // 先返回当前中间级别的页表项，然后压入子页表状态
140                let level = state.level;
141                let vaddr = current_vaddr;
142
143                self.stack.push(child_state).ok();
144
145                return Some(PteInfo {
146                    level,
147                    vaddr,
148                    pte,
149                    is_final_mapping,
150                });
151            }
152
153            // 返回页表项信息（无效项、叶子级别或大页）
154            return Some(PteInfo {
155                level: state.level,
156                vaddr: current_vaddr,
157                pte,
158                is_final_mapping,
159            });
160        }
161    }
162}
163
164impl<'a, T: TableMeta, A: FrameAllocator> Iterator for PageTableWalker<'a, T, A> {
165    type Item = PteInfo<T::P>;
166
167    fn next(&mut self) -> Option<Self::Item> {
168        self.find_next_entry()
169    }
170}
page_table_generic/walk.rs

page_table_generic/
walk.rs
