page_table_generic/
frame.rs

1use crate::{
2    FrameAllocator, PageTableEntry, PagingError, PagingResult, PhysAddr, PteConfigOf, TableMeta,
3    VirtAddr,
4};
5
6/// 页表帧，代表一个物理页面上的页表
7#[derive(Clone, Copy)]
8pub struct Frame<T: TableMeta, A: FrameAllocator> {
9    pub paddr: PhysAddr,
10    pub allocator: A,
11    frames: usize,
12    _marker: core::marker::PhantomData<T>,
13}
14
15impl<T: TableMeta, A: FrameAllocator> core::fmt::Debug for Frame<T, A> {
16    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
17        f.debug_struct("Frame")
18            .field("paddr", &format_args!("{:#x}", self.paddr.as_usize()))
19            .finish()
20    }
21}
22
23impl<T, A> Frame<T, A>
24where
25    T: TableMeta,
26    A: FrameAllocator,
27{
28    pub(crate) const PT_INDEX_SHIFT: usize = T::PAGE_SIZE.trailing_zeros() as usize;
29    pub(crate) const PT_INDEX_BITS: usize = cal_index_bits::<T>();
30    pub(crate) const PT_VALID_BITS: usize = Self::PT_INDEX_BITS + Self::PT_INDEX_SHIFT;
31    pub(crate) const LEN: usize = T::PAGE_SIZE / core::mem::size_of::<T::P>();
32    pub(crate) const ROOT_LEN: usize = 1usize << T::LEVEL_BITS[0];
33    pub(crate) const ROOT_FRAMES: usize =
34        (Self::ROOT_LEN * core::mem::size_of::<T::P>()).div_ceil(T::PAGE_SIZE);
35    pub(crate) const PT_LEVEL: usize = T::LEVEL_BITS.len();
36
37    /// 创建新的页表帧（分配并清零）
38    pub fn new(allocator: A) -> PagingResult<Self> {
39        let paddr = allocator.alloc_frame().ok_or(PagingError::NoMemory)?;
40        unsafe {
41            let vaddr = allocator.phys_to_virt(paddr);
42            core::ptr::write_bytes(vaddr, 0, T::PAGE_SIZE);
43        }
44
45        Ok(Self {
46            paddr,
47            allocator,
48            frames: 1,
49            _marker: core::marker::PhantomData,
50        })
51    }
52
53    /// 创建新的根页表帧。
54    pub fn new_root(allocator: A) -> PagingResult<Self> {
55        let align = T::PAGE_SIZE * Self::ROOT_FRAMES;
56        let paddr = allocator
57            .alloc_frames(Self::ROOT_FRAMES, align)
58            .ok_or(PagingError::NoMemory)?;
59        unsafe {
60            let vaddr = allocator.phys_to_virt(paddr);
61            core::ptr::write_bytes(vaddr, 0, T::PAGE_SIZE * Self::ROOT_FRAMES);
62        }
63
64        Ok(Self {
65            paddr,
66            allocator,
67            frames: Self::ROOT_FRAMES,
68            _marker: core::marker::PhantomData,
69        })
70    }
71
72    /// 从物理地址创建Frame（不分配）
73    pub fn from_paddr(paddr: PhysAddr, allocator: A) -> Self {
74        Self {
75            paddr,
76            allocator,
77            frames: 1,
78            _marker: core::marker::PhantomData,
79        }
80    }
81
82    /// 从根页表物理地址创建Frame（不分配）
83    pub fn from_root_paddr(paddr: PhysAddr, allocator: A) -> Self {
84        Self {
85            paddr,
86            allocator,
87            frames: Self::ROOT_FRAMES,
88            _marker: core::marker::PhantomData,
89        }
90    }
91
92    /// 从PTE创建子Frame（用于遍历子页表）
93    pub fn from_pte(pte: &T::P, level: usize, allocator: A) -> Self {
94        Self::from_paddr(pte.paddr(level > 1), allocator)
95    }
96
97    /// 获取页表项的可变切片
98    pub fn as_slice_mut(&mut self) -> &mut [T::P] {
99        let vaddr = self.allocator.phys_to_virt(self.paddr);
100        unsafe { core::slice::from_raw_parts_mut(vaddr as *mut T::P, self.len()) }
101    }
102
103    /// 获取页表项的不可变切片
104    pub fn as_slice(&self) -> &[T::P] {
105        let vaddr = self.allocator.phys_to_virt(self.paddr);
106        unsafe { core::slice::from_raw_parts(vaddr as *const T::P, self.len()) }
107    }
108
109    pub fn len(&self) -> usize {
110        self.frames * Self::LEN
111    }
112
113    /// Returns whether this frame range contains no page-table entries.
114    pub fn is_empty(&self) -> bool {
115        self.len() == 0
116    }
117
118    /// 计算指定级别对应的映射大小
119    /// - Level 1 (叶子): PAGE_SIZE
120    /// - Level 2: PAGE_SIZE << LEVEL_BITS[最后一级]
121    /// - Level 3: PAGE_SIZE << (LEVEL_BITS[最后一级] + LEVEL_BITS[倒数第二级])
122    /// - Level N: PAGE_SIZE << (sum of LEVEL_BITS from last to N-1)
123    pub fn level_size(level: usize) -> usize {
124        if level == 1 {
125            return T::PAGE_SIZE;
126        }
127        // 从最后一级开始累加位数，直到当前级别的前一级
128        // 例如：对于 4 级页表 [9,9,9,9]，level=3 时，累加 LEVEL_BITS[3] (即最后一级 9 位)
129        let total_levels = T::LEVEL_BITS.len();
130        let shift = T::LEVEL_BITS
131            .iter()
132            .skip(total_levels - level + 1)
133            .sum::<usize>();
134        T::PAGE_SIZE << shift
135    }
136
137    /// 计算指定级别的页表索引
138    /// 从虚拟地址中提取对应级别的索引位
139    pub fn virt_to_index(vaddr: VirtAddr, level: usize) -> usize {
140        if level == 0 || level > Self::PT_LEVEL {
141            panic!("Invalid level: {} (valid: 1..={})", level, Self::PT_LEVEL);
142        }
143
144        // 计算需要跳过的位数（页面偏移 + 低级别索引位）
145        // Level 1 (叶子): shift = page_shift（只跳过页面偏移）
146        // Level 2: shift = page_shift + LEVEL_BITS[最后一级]
147        // Level 3: shift = page_shift + LEVEL_BITS[最后一级] + LEVEL_BITS[倒数第二级]
148        // Level N: shift = page_shift + sum(LEVEL_BITS[N+1..end])
149        let page_shift = T::PAGE_SIZE.trailing_zeros() as usize;
150        let total_levels = T::LEVEL_BITS.len();
151
152        // 累加从最后一级到当前级别之后的所有位数
153        let shift = if level == 1 {
154            page_shift
155        } else {
156            page_shift
157                + T::LEVEL_BITS
158                    .iter()
159                    .skip(total_levels - level + 1)
160                    .sum::<usize>()
161        };
162
163        // 当前级别的索引位数
164        let level_index_bits = T::LEVEL_BITS[total_levels - level];
165        let mask = (1 << level_index_bits) - 1;
166
167        (vaddr.as_usize() >> shift) & mask
168    }
169
170    pub(crate) fn level_for_page_size(page_size: usize) -> Option<usize> {
171        (1..=Self::PT_LEVEL).find(|level| Self::level_size(*level) == page_size)
172    }
173
174    pub fn protect_recursive(
175        &mut self,
176        vaddr: VirtAddr,
177        config: PteConfigOf<T>,
178        level: usize,
179    ) -> PagingResult<usize> {
180        let index = Self::virt_to_index(vaddr, level);
181        let entry = self.as_slice()[index];
182        if entry.unused() {
183            return Err(PagingError::not_mapped());
184        }
185        let is_dir = level > 1;
186        let is_huge = entry.huge(is_dir);
187        if is_huge || level == 1 {
188            self.as_slice_mut()[index] = T::P::new_page(entry.paddr(is_dir), config, is_huge);
189            return Ok(Self::level_size(level));
190        }
191        if !entry.present() {
192            return Err(PagingError::not_mapped());
193        }
194
195        let mut child = Self::from_paddr(entry.paddr(is_dir), self.allocator.clone());
196        child.protect_recursive(vaddr, config, level - 1)
197    }
198
199    /// Splits the block mapping that contains `vaddr` until `boundary` is also
200    /// a mapping boundary. Existing leaf attributes and physical addresses are
201    /// preserved in every child entry.
202    pub(crate) fn split_leaf_for_boundary(
203        &mut self,
204        vaddr: VirtAddr,
205        boundary: VirtAddr,
206        level: usize,
207    ) -> PagingResult {
208        let index = Self::virt_to_index(vaddr, level);
209        let entry = self.as_slice()[index];
210        if entry.unused() || !entry.present() || level == 1 {
211            return Ok(());
212        }
213
214        if entry.huge(true) {
215            let block_size = Self::level_size(level);
216            if boundary.as_usize().is_multiple_of(block_size) {
217                return Ok(());
218            }
219
220            let child_level = level - 1;
221            let child_size = Self::level_size(child_level);
222            let child_entries = 1usize << T::LEVEL_BITS[T::LEVEL_BITS.len() - child_level];
223            let mut child = Self::new(self.allocator.clone())?;
224            let child_is_huge = child_level > 1;
225            let block_paddr = entry.paddr(true);
226            let block_config = entry.config(true);
227            for (child_index, child_entry) in child
228                .as_slice_mut()
229                .iter_mut()
230                .take(child_entries)
231                .enumerate()
232            {
233                *child_entry = T::P::new_page(
234                    block_paddr + child_index * child_size,
235                    block_config,
236                    child_is_huge,
237                );
238            }
239
240            // Break-before-make prevents a CPU from observing the old block
241            // descriptor and the new table descriptor at the same time.
242            self.as_slice_mut()[index].clear();
243            T::flush(None);
244            self.as_slice_mut()[index] = T::P::new_table(child.paddr);
245            T::flush(None);
246
247            child.split_leaf_for_boundary(vaddr, boundary, child_level)
248        } else {
249            let mut child = Self::from_paddr(entry.paddr(true), self.allocator.clone());
250            child.split_leaf_for_boundary(vaddr, boundary, level - 1)
251        }
252    }
253
254    pub fn remap_recursive(
255        &mut self,
256        vaddr: VirtAddr,
257        paddr: PhysAddr,
258        config: PteConfigOf<T>,
259        level: usize,
260    ) -> PagingResult<usize> {
261        let index = Self::virt_to_index(vaddr, level);
262        let entry = self.as_slice()[index];
263        if entry.unused() {
264            return Err(PagingError::not_mapped());
265        }
266        let is_dir = level > 1;
267        let is_huge = entry.huge(is_dir);
268        if is_huge || level == 1 {
269            let page_size = Self::level_size(level);
270            let aligned_paddr = PhysAddr::from_usize(paddr.as_usize() & !(page_size - 1));
271            self.as_slice_mut()[index] = T::P::new_page(aligned_paddr, config, is_huge);
272            return Ok(page_size);
273        }
274        if !entry.present() {
275            return Err(PagingError::not_mapped());
276        }
277
278        let mut child = Self::from_paddr(entry.paddr(is_dir), self.allocator.clone());
279        child.remap_recursive(vaddr, paddr, config, level - 1)
280    }
281
282    /// 重建完整的虚拟地址
283    /// 从基地址和索引计算完整的虚拟地址
284    pub fn reconstruct_vaddr(index: usize, level: usize, base_vaddr: VirtAddr) -> VirtAddr {
285        let entry_size = Self::level_size(level);
286        base_vaddr + index * entry_size
287    }
288
289    /// 递归释放当前帧及所有子帧
290    ///
291    /// 此方法会：
292    /// 1. 递归释放所有有效的子页表帧
293    /// 2. 清除所有页表项（设为invalid）
294    /// 3. 释放当前帧
295    ///
296    /// 注意：只释放页表帧，不释放映射的物理页（数据页/大页）
297    ///
298    /// # Parameters
299    /// - `level`: 当前帧所在的页表级别（1=叶子，数字越大级别越高）
300    ///
301    /// # Safety
302    /// 调用者必须确保：
303    /// - 没有其他代码在访问这些页表
304    /// - 没有CPU正在使用这些页表进行地址翻译
305    pub fn deallocate_recursive(&mut self, level: usize) {
306        // 先递归释放所有子帧
307        self.deallocate_children(level);
308
309        // 再释放当前帧
310        self.allocator
311            .dealloc_frames(self.paddr, self.frames, T::PAGE_SIZE);
312    }
313
314    /// 只释放子页表帧，保留当前帧
315    ///
316    /// 遍历当前帧中的所有页表项：
317    /// - 如果是大页或叶子级别的数据页：跳过（不释放物理页，也不清除映射）
318    /// - 如果是非叶子级别的页表指针：递归释放子页表帧，并清除PTE
319    ///
320    /// # Parameters
321    /// - `level`: 当前帧所在的页表级别（1=叶子，数字越大级别越高）
322    pub fn deallocate_children(&mut self, level: usize) {
323        // 反向遍历以避免索引变化问题
324        for i in (0..self.len()).rev() {
325            // 先获取当前PTE的状态
326            let entry_info = {
327                let entries = self.as_slice();
328                if i < entries.len() {
329                    let entry = entries[i];
330                    (
331                        entry.present(),
332                        entry.huge(level > 1),
333                        entry.paddr(level > 1),
334                    )
335                } else {
336                    (false, false, crate::PhysAddr::from_usize(0))
337                }
338            };
339
340            let (is_valid, is_huge, paddr) = entry_info;
341
342            if !is_valid {
343                continue;
344            }
345
346            // 如果是大页或叶子级别的数据页：跳过，保持映射不变
347            if is_huge || level == 1 {
348                continue;
349            }
350            // 否则是非叶子级别的页表指针，递归释放子页表帧
351            else {
352                let mut child_frame = Frame::<T, A>::from_paddr(paddr, self.allocator.clone());
353                child_frame.deallocate_recursive(level - 1);
354
355                // 子页表帧已释放，清除PTE
356                let entries_mut = self.as_slice_mut();
357                entries_mut[i].clear();
358            }
359        }
360    }
361
362    /// 递归查找虚拟地址对应的页表项
363    ///
364    /// # 参数
365    /// - `vaddr`: 要查找的虚拟地址
366    /// - `level`: 当前页表级别
367    ///
368    /// # 返回值
369    /// - `Ok(T::P)`: 找到的页表项
370    /// - `Err(PagingError)`: 查找失败
371    pub fn translate_recursive(&self, vaddr: VirtAddr, level: usize) -> PagingResult<T::P> {
372        let (pte, _) = self.translate_recursive_with_level(vaddr, level)?;
373        Ok(pte)
374    }
375
376    /// 递归查找虚拟地址对应的页表项，同时返回该PTE所在的级别
377    ///
378    /// # 参数
379    /// - `vaddr`: 要查找的虚拟地址
380    /// - `level`: 当前页表级别
381    ///
382    /// # 返回值
383    /// - `Ok((T::P, usize))`: 找到的页表项及其所在的级别
384    /// - `Err(PagingError)`: 查找失败
385    pub fn translate_recursive_with_level(
386        &self,
387        vaddr: VirtAddr,
388        level: usize,
389    ) -> PagingResult<(T::P, usize)> {
390        let (pte, level) = self.find_occupied_leaf(vaddr, level)?;
391        if !pte.present() {
392            return Err(PagingError::not_mapped());
393        }
394        Ok((pte, level))
395    }
396
397    pub(crate) fn find_occupied_leaf(
398        &self,
399        vaddr: VirtAddr,
400        level: usize,
401    ) -> PagingResult<(T::P, usize)> {
402        // 计算当前级别的页表索引
403        let index = Self::virt_to_index(vaddr, level);
404
405        // 获取页表项
406        let entries = self.as_slice();
407        let pte = entries[index];
408
409        if pte.unused() {
410            return Err(PagingError::not_mapped());
411        }
412
413        // 如果是大页映射或叶子级别，直接返回页表项及其级别
414        if pte.huge(level > 1) || level == 1 {
415            return Ok((pte, level));
416        }
417
418        // 否则，继续递归到下一级页表
419        if level > 1 {
420            if !pte.present() {
421                return Err(PagingError::hierarchy_error(
422                    "Non-present intermediate entry is not a leaf",
423                ));
424            }
425            let child_frame: Frame<T, A> = Frame::from_pte(&pte, level, self.allocator.clone());
426            return child_frame.find_occupied_leaf(vaddr, level - 1);
427        }
428
429        // 不应该到达这里
430        Err(PagingError::hierarchy_error(
431            "Invalid page table level during translation",
432        ))
433    }
434
435    /// 递归释放指定的单个页表项
436    ///
437    /// 如果该PTE指向有效的子页表，则递归释放该子页表及其所有子帧
438    /// 在释放前将PTE设为invalid
439    ///
440    /// 注意：只释放页表帧，不释放映射的物理页
441    ///
442    /// # Parameters
443    /// - `index`: 要释放的PTE索引
444    /// - `level`: 当前帧所在的页表级别
445    pub fn dealloc_entry_recursive(&mut self, index: usize, level: usize) -> bool {
446        if index >= self.len() || level <= 1 {
447            return false;
448        }
449
450        let entries = self.as_slice();
451        let entry = &entries[index];
452        if entry.present() && !entry.huge(true) {
453            // 递归释放子帧（子帧的级别是 level - 1）
454            let mut child_frame = Frame::<T, A>::from_pte(entry, level, self.allocator.clone());
455            child_frame.deallocate_recursive(level - 1);
456
457            // 将当前PTE设为invalid
458            let entries_mut = self.as_slice_mut();
459            entries_mut[index].clear();
460
461            true
462        } else {
463            false
464        }
465    }
466
467    pub(crate) fn clone_entry_from(
468        &mut self,
469        source: &Self,
470        index: usize,
471        level: usize,
472    ) -> PagingResult<bool> {
473        if index >= self.len() || index >= source.len() {
474            return Err(PagingError::hierarchy_error(
475                "Entry index exceeds page-table frame size",
476            ));
477        }
478        if !self.as_slice()[index].unused() {
479            return Ok(false);
480        }
481
482        let source_entry = source.as_slice()[index];
483        if source_entry.unused() {
484            return Ok(false);
485        }
486        if level == 1 || source_entry.huge(true) {
487            self.as_slice_mut()[index] = source_entry;
488            return Ok(true);
489        }
490        if !source_entry.present() {
491            return Err(PagingError::hierarchy_error(
492                "Non-present intermediate entry is not a leaf",
493            ));
494        }
495
496        let source_child = Self::from_paddr(source_entry.paddr(true), source.allocator.clone());
497        let mut target_child = Self::new(self.allocator.clone())?;
498        if let Err(err) = target_child.clone_children_from(&source_child, level - 1) {
499            target_child.deallocate_recursive(level - 1);
500            return Err(err);
501        }
502
503        self.as_slice_mut()[index] = T::P::new_table(target_child.paddr);
504        Ok(true)
505    }
506
507    fn clone_children_from(&mut self, source: &Self, level: usize) -> PagingResult {
508        for index in 0..source.len() {
509            self.clone_entry_from(source, index, level)?;
510        }
511        Ok(())
512    }
513}
514
515const fn cal_index_bits<T: TableMeta>() -> usize {
516    let mut bits = 0;
517    let len = T::LEVEL_BITS.len();
518    let mut i = 0;
519    while i < len {
520        bits += T::LEVEL_BITS[i];
521        i += 1;
522    }
523    bits
524}
page_table_generic/frame.rs

page_table_generic/
frame.rs
