1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
//! This module provides the [`PageFormat`] struct that is used to describe the page table
//! hierarchy.
use core::ops::Range;
use crate::level::PageLevel;
use crate::walker::PteType;
use num_traits::{FromPrimitive, PrimInt, Unsigned};
/// Describes the page format of the page hierarchy and the mask of bits in the PTE that refer to
/// the actual physical address and are not used for metadata.
#[derive(Clone, Debug)]
pub struct PageFormat<'a, PTE>
where
PTE: FromPrimitive + PrimInt + Unsigned,
{
/// Describes the page table hierarchy as a slice of [`crate::level::PageLevel`] structs that
/// each describe a single level in this hierarchy, where the level at index zero is the leaf
/// node and the last page level is the root.
pub levels: &'a [PageLevel<PTE>],
/// The physical mask of bits that refer to an actual physical address and are not used for PTE
/// metadata.
pub physical_mask: PTE,
}
impl<'a, PTE> PageFormat<'a, PTE>
where
PTE: FromPrimitive + PrimInt + Unsigned,
{
/// Calculates the full virtual address mask by setting all the bits for each page level and
/// finding the largest mask. This is used by the [`PageFormat::sign_extend`] method to
/// determine the sign bit.
pub fn virtual_mask(&self) -> usize {
self.levels
.iter()
.map(|level| level.mask() | level.page_size() - 1)
.max()
.unwrap()
}
/// Sign extends a given virtual address by extending the sign bit into the unused upper bits
/// of the virtual address.
pub fn sign_extend(&self, address: usize) -> usize {
let sign_bit = 1 << self.virtual_mask().trailing_ones() - 1;
if address & sign_bit == sign_bit {
// Invert the virtual mask and mask it with the address to sign extend the address.
!self.virtual_mask() | address
} else {
address
}
}
/// This is a recursive helper function used to traverse the page table hierarchy for a given
/// virtual address range and the given physical address of the page table for the current page
/// table level. It invokes the appropriate user callbacks in [`crate::walker::PageWalker`],
/// while traversing the page tables.
fn do_walk<PageWalker, Error>(
&self,
phys_addr: PTE,
mut index: usize,
range: Range<usize>,
walker: &mut PageWalker,
) -> Result<(), Error>
where
PageWalker: crate::walker::PageWalker<PTE, Error>,
{
// Ensure that the index is valid.
if index >= self.levels.len() {
index = self.levels.len() - 1;
}
let level = &self.levels[index];
// Split up the range by page boundaries, such that we have a range for each page that is
// inclusive of the original range. For instance, the range 0x0000..0x1fff spans two 4K
// pages, so this iterator would return 0x0000..0x0fff and 0x1000..0x1fff. We also make
// sure that the page ranges are sign extended where appropriate. In addition, calculate
// the PTE index.
let page_ranges = (level.pte_index(range.start)..=level.pte_index(range.end))
.scan(self.sign_extend(range.start), |state, pte_index| {
let page_range = *state..level.end(*state).min(range.end);
*state = self.sign_extend(level.end(*state) + 1);
Some((pte_index, page_range))
});
for (pte_index, page_range) in page_ranges {
// Get the PTE index for this page range, and then index into the page table to get the
// corresponding PTE.
let offset: PTE = PTE::from_usize(pte_index * core::mem::size_of::<PTE>()).unwrap();
let pte = walker.read_pte(phys_addr + offset)?;
// Determine whether the PTE refers to a page or a page table. That is, it is a page if
// we are at a leaf page table or if the PTE refers to a huge page. Otherwise, it is a
// page table.
let page_type = match index == 0 || level.is_huge_page(pte) {
true => PteType::Page(index),
_ => PteType::PageTable(index),
};
// Invoke the user callback to handle this PTE.
walker.handle_pte(page_type, page_range.clone(), &pte)?;
// Invoke the user callback to handle this PTE hole, i.e. when the PTE is not marked as
// present.
if !level.is_present(pte) {
walker.handle_pte_hole(index, page_range.clone(), &pte)?;
}
// If the user did not decide to unmap this page, then we are done with this PTE and
// can resume to the next one.
if index == 0 || level.is_huge_page(pte) {
continue;
}
// At this point we are dealing with a normal page table. Extract the physical address
// from the current PTE, and recurse the page table hierarchy.
let phys_addr = pte & self.physical_mask;
self.do_walk(phys_addr, index - 1, page_range.clone(), walker)?;
// Provide an opportunity to the user to handle the PTE of the page table upon
// recursion. For instance, to free the page table.
walker.handle_post_pte(index, page_range, &pte)?;
}
Ok(())
}
/// This is a recursive function used to traverse the page table hierarchy for a given virtual
/// address range and the given physical address of the root page table of the page table
/// hierarchy. It invokes the appropriate user callbacks in [`crate::walker::PageWalker`],
/// while traversing the page tables.
pub fn walk<PageWalker, Error>(
&self,
phys_addr: PTE,
range: Range<usize>,
walker: &mut PageWalker,
) -> Result<(), Error>
where
PageWalker: crate::walker::PageWalker<PTE, Error>,
{
self.do_walk(phys_addr, self.levels.len() - 1, range, walker)
}
/// This is a recursive helper function used to traverse the page table hierarchy for a given
/// virtual address range and the given physical address of the page table for the current page
/// table level. It invokes the appropriate user callbacks in [`crate::walker::PageWalkerMut`],
/// while traversing the page tables.
fn do_walk_mut<PageWalkerMut, Error>(
&self,
phys_addr: PTE,
mut index: usize,
range: Range<usize>,
walker: &mut PageWalkerMut,
) -> Result<(), Error>
where
PageWalkerMut: crate::walker::PageWalkerMut<PTE, Error>,
{
// Ensure that the index is valid.
if index >= self.levels.len() {
index = self.levels.len() - 1;
}
let level = &self.levels[index];
// Split up the range by page boundaries, such that we have a range for each page that is
// inclusive of the original range. For instance, the range 0x0000..0x1fff spans two 4K
// pages, so this iterator would return 0x0000..0x0fff and 0x1000..0x1fff. We also make
// sure that the page ranges are sign extended where appropriate. In addition, calculate
// the PTE index.
let page_ranges = (level.pte_index(range.start)..=level.pte_index(range.end))
.scan(self.sign_extend(range.start), |state, pte_index| {
let page_range = *state..level.end(*state).min(range.end);
*state = self.sign_extend(level.end(*state) + 1);
Some((pte_index, page_range))
});
for (pte_index, page_range) in page_ranges {
// Get the PTE index for this page range, and then index into the page table to get the
// corresponding PTE.
let offset: PTE = PTE::from_usize(pte_index * core::mem::size_of::<PTE>()).unwrap();
let mut pte = walker.read_pte(phys_addr + offset)?;
// Determine whether the PTE refers to a page or a page table. That is, it is a page if
// we are at a leaf page table or if the PTE refers to a huge page. Otherwise, it is a
// page table.
let page_type = match index == 0 || level.is_huge_page(pte) {
true => PteType::Page(index),
_ => PteType::PageTable(index),
};
// Invoke the user callback to handle this PTE.
walker.handle_pte(page_type, page_range.clone(), &mut pte)?;
// Invoke the user callback to handle this PTE hole, i.e. when the PTE is not marked as
// present.
if !level.is_present(pte) {
walker.handle_pte_hole(index, page_range.clone(), &mut pte)?;
}
// If the user did not decide to unmap this page, then we are done with this PTE and
// can resume to the next one.
walker.write_pte(phys_addr + offset, pte)?;
if index == 0 || level.is_huge_page(pte) {
continue;
}
// At this point we are dealing with a normal page table. Extract the physical address
// from the current PTE, and recurse the page table hierarchy.
let phys_addr = pte & self.physical_mask;
self.do_walk_mut(phys_addr, index - 1, page_range.clone(), walker)?;
// Provide an opportunity to the user to handle the PTE of the page table upon
// recursion. For instance, to free the page table.
walker.handle_post_pte(index, page_range, &mut pte)?;
walker.write_pte(phys_addr + offset, pte)?;
}
Ok(())
}
/// This is a recursive function used to traverse the page table hierarchy for a given virtual
/// address range and the given physical address of the root page table of the page table
/// hierarchy. It invokes the appropriate user callbacks in [`crate::walker::PageWalker`],
/// while traversing the page tables.
pub fn walk_mut<PageWalkerMut, Error>(
&self,
phys_addr: PTE,
range: Range<usize>,
walker: &mut PageWalkerMut,
) -> Result<(), Error>
where
PageWalkerMut: crate::walker::PageWalkerMut<PTE, Error>,
{
self.do_walk_mut(phys_addr, self.levels.len() - 1, range, walker)
}
}