page_table_generic/
walk.rs

1use heapless::Vec;
2
3use crate::{FrameAllocator, PageTableEntry, PageTableRef, TableMeta, VirtAddr, frame::Frame};
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: page_table.root.clone(),
64                level: Frame::<T, A>::PT_LEVEL,
65                index: 0,
66                base_vaddr: VirtAddr::from_usize(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 >= state.frame.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 = T::canonicalize_vaddr(Frame::<T, A>::reconstruct_vaddr(
103                state.index - 1,
104                state.level,
105                state.base_vaddr,
106            ));
107
108            // 跳过不在范围内的地址
109            if current_vaddr < self.config.start_vaddr {
110                continue;
111            }
112
113            if current_vaddr >= self.config.end_vaddr {
114                self.finished = true;
115                return None;
116            }
117
118            // 判断是否为最终映射
119            // - 无效项：不是最终映射
120            // - 有效且是大页：是最终映射
121            // - 有效且在叶子级别（level == 1）：是最终映射
122            // - 有效但在中间级别且不是大页：不是最终映射（页表指针）
123            let is_dir = state.level > 1;
124            let is_huge = pte.huge(is_dir);
125            let is_final_mapping = pte.present() && (is_huge || state.level == 1);
126
127            // 如果是有效的子页表项（中间级别的页表指针），需要深入下一级
128            if pte.present() && !is_huge && state.level > 1 {
129                let child_frame = Frame::from_paddr(pte.paddr(true), state.frame.allocator.clone());
130
131                // 计算子页表的基地址：当前条目的虚拟地址就是子页表覆盖的地址范围起点
132                let child_base_vaddr = current_vaddr;
133
134                // 创建子页表状态并压入栈中
135                let child_state = WalkState {
136                    frame: child_frame,
137                    level: state.level - 1,
138                    index: 0,
139                    base_vaddr: child_base_vaddr,
140                };
141
142                // 先返回当前中间级别的页表项，然后压入子页表状态
143                let level = state.level;
144                let vaddr = current_vaddr;
145
146                self.stack.push(child_state).ok();
147
148                return Some(PteInfo {
149                    level,
150                    vaddr,
151                    pte,
152                    is_final_mapping,
153                });
154            }
155
156            // 返回页表项信息（无效项、叶子级别或大页）
157            return Some(PteInfo {
158                level: state.level,
159                vaddr: current_vaddr,
160                pte,
161                is_final_mapping,
162            });
163        }
164    }
165}
166
167impl<'a, T: TableMeta, A: FrameAllocator> Iterator for PageTableWalker<'a, T, A> {
168    type Item = PteInfo<T::P>;
169
170    fn next(&mut self) -> Option<Self::Item> {
171        self.find_next_entry()
172    }
173}
page_table_generic/walk.rs

page_table_generic/
walk.rs
