page_table/table/
visit.rs

1use super::Pos;
2use crate::{PageTable, Pte, VmMeta};
3use core::ptr::NonNull;
4
5/// `Meta` 方案的页表访问机制。
6pub trait Visitor<Meta: VmMeta> {
7    /// 到达 `target_hint` 节点。
8    fn arrive(&mut self, pte: Pte<Meta>, target: Pos<Meta>) -> Pos<Meta>;
9
10    /// 在访问 `target` 的过程中，经过一个包括 `target` 的 `level` 级页表项 `pte`，并且这个页表项指向一个中间页表节点。
11    fn meet(
12        &mut self,
13        level: usize,
14        pte: Pte<Meta>,
15        target: Pos<Meta>,
16    ) -> Option<NonNull<Pte<Meta>>>;
17
18    /// 在访问 `target` 的过程中，经过一个包括 `target` 的 `level` 级页表项 `pte`，但这个页表项没有指向一个子页表。
19    ///
20    /// 以下两种情况会调用这个方法：
21    ///
22    /// - 访问到包含目标虚页的大页节点；
23    /// - 访问到包含目标虚页的无效节点；
24    fn block(&mut self, level: usize, pte: Pte<Meta>, target: Pos<Meta>) -> Pos<Meta>;
25}
26
27/// `Meta` 方案的页表访问机制。
28pub trait Decorator<Meta: VmMeta> {
29    /// 到达 `target_hint` 节点。
30    fn arrive(&mut self, pte: &mut Pte<Meta>, target_hint: Pos<Meta>) -> Pos<Meta>;
31
32    /// 在访问 `target` 的过程中，经过一个包括 `target` 的 `level` 级页表项 `pte`，并且这个页表项指向一个中间页表节点。
33    fn meet(
34        &mut self,
35        level: usize,
36        pte: Pte<Meta>,
37        target: Pos<Meta>,
38    ) -> Option<NonNull<Pte<Meta>>>;
39
40    /// 在访问 `target` 的过程中，经过一个包括 `target` 的 `level` 级页表项 `pte`。
41    ///
42    /// 以下两种情况会调用这个方法：
43    ///
44    /// - 访问到包含目标虚页的大页节点；
45    /// - 访问到包含目标虚页的无效节点；
46    fn block(&mut self, level: usize, pte: Pte<Meta>, target_hint: Pos<Meta>) -> Update<Meta>;
47}
48
49/// 遍历中断时的更新方案。
50pub enum Update<Meta: VmMeta> {
51    /// 修改目标。
52    Target(Pos<Meta>),
53    /// 新建中间页表。
54    Pte(Pte<Meta>, NonNull<Pte<Meta>>),
55}
56
57/// 递归遍历。
58pub(super) fn walk_inner<Meta: VmMeta>(
59    table: &PageTable<Meta>,
60    visitor: &mut impl Visitor<Meta>,
61    target: &mut Pos<Meta>,
62) {
63    let range = table.range();
64    let level = table.level;
65    // 如果目标虚页不在当前页表覆盖范围内，回到上一级页表
66    while level >= target.level && range.contains(&target.vpn) {
67        // 计算作为页表项的序号
68        let index = target.vpn.index_in(level);
69        // 借出页表项
70        let pte = table.mem[index];
71        // 目标节点等级比当前低需要查页表
72        if level > target.level {
73            // 有效且不是叶子的页表项是子页表
74            if pte.is_valid() && !pte.is_leaf() {
75                match visitor.meet(level, pte, *target) {
76                    Some(ptr) => {
77                        let table = unsafe {
78                            PageTable::from_raw_parts(
79                                ptr,
80                                range.start + index * Meta::pages_in_table(level - 1),
81                                level - 1,
82                            )
83                        };
84                        walk_inner(&table, visitor, target);
85                    }
86                    None => *target = Pos::stop(),
87                }
88            }
89            // 否则请求用户操作
90            else {
91                *target = visitor.block(level, pte, *target);
92            }
93        }
94        // 访问目标节点
95        else {
96            *target = visitor.arrive(pte, *target);
97        }
98    }
99}
100
101/// 递归遍历。
102pub(super) fn walk_inner_mut<Meta: VmMeta>(
103    table: &mut PageTable<Meta>,
104    visitor: &mut impl Decorator<Meta>,
105    target: &mut Pos<Meta>,
106) {
107    let range = table.range();
108    let level = table.level;
109    // 如果目标虚页不在当前页表覆盖范围内，回到上一级页表
110    while level >= target.level && range.contains(&target.vpn) {
111        // 计算作为页表项的序号
112        let index = target.vpn.index_in(level);
113        // 借出页表项
114        let pte = &mut table.mem[index];
115        // 目标节点等级比当前低需要查页表
116        if level > target.level {
117            // 有效且不是叶子的页表项是子页表
118            if pte.is_valid() && !pte.is_leaf() {
119                match visitor.meet(level, *pte, *target) {
120                    Some(ptr) => {
121                        let mut table = unsafe {
122                            PageTable::from_raw_parts(
123                                ptr,
124                                range.start + index * Meta::pages_in_table(level - 1),
125                                level - 1,
126                            )
127                        };
128                        walk_inner_mut(&mut table, visitor, target);
129                    }
130                    None => *target = Pos::stop(),
131                }
132            }
133            // 否则请求用户操作
134            else {
135                match visitor.block(level, *pte, *target) {
136                    // 重设目标
137                    Update::Target(new) => *target = new,
138                    // 修改页表
139                    Update::Pte(new, ptr) => {
140                        *pte = new;
141                        let mut table = unsafe {
142                            PageTable::from_raw_parts(
143                                ptr,
144                                range.start + index * Meta::pages_in_table(level - 1),
145                                level - 1,
146                            )
147                        };
148                        walk_inner_mut(&mut table, visitor, target);
149                    }
150                }
151            }
152        }
153        // 访问目标节点
154        else {
155            *target = visitor.arrive(pte, *target);
156        }
157    }
158}
page_table/table/visit.rs

page_table/table/
visit.rs
