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    pub fn remap_recursive(
200        &mut self,
201        vaddr: VirtAddr,
202        paddr: PhysAddr,
203        config: PteConfigOf<T>,
204        level: usize,
205    ) -> PagingResult<usize> {
206        let index = Self::virt_to_index(vaddr, level);
207        let entry = self.as_slice()[index];
208        if entry.unused() {
209            return Err(PagingError::not_mapped());
210        }
211        let is_dir = level > 1;
212        let is_huge = entry.huge(is_dir);
213        if is_huge || level == 1 {
214            let page_size = Self::level_size(level);
215            let aligned_paddr = PhysAddr::from_usize(paddr.as_usize() & !(page_size - 1));
216            self.as_slice_mut()[index] = T::P::new_page(aligned_paddr, config, is_huge);
217            return Ok(page_size);
218        }
219        if !entry.present() {
220            return Err(PagingError::not_mapped());
221        }
222
223        let mut child = Self::from_paddr(entry.paddr(is_dir), self.allocator.clone());
224        child.remap_recursive(vaddr, paddr, config, level - 1)
225    }
226
227    /// 重建完整的虚拟地址
228    /// 从基地址和索引计算完整的虚拟地址
229    pub fn reconstruct_vaddr(index: usize, level: usize, base_vaddr: VirtAddr) -> VirtAddr {
230        let entry_size = Self::level_size(level);
231        base_vaddr + index * entry_size
232    }
233
234    /// 递归释放当前帧及所有子帧
235    ///
236    /// 此方法会：
237    /// 1. 递归释放所有有效的子页表帧
238    /// 2. 清除所有页表项（设为invalid）
239    /// 3. 释放当前帧
240    ///
241    /// 注意：只释放页表帧，不释放映射的物理页（数据页/大页）
242    ///
243    /// # Parameters
244    /// - `level`: 当前帧所在的页表级别（1=叶子，数字越大级别越高）
245    ///
246    /// # Safety
247    /// 调用者必须确保：
248    /// - 没有其他代码在访问这些页表
249    /// - 没有CPU正在使用这些页表进行地址翻译
250    pub fn deallocate_recursive(&mut self, level: usize) {
251        // 先递归释放所有子帧
252        self.deallocate_children(level);
253
254        // 再释放当前帧
255        self.allocator
256            .dealloc_frames(self.paddr, self.frames, T::PAGE_SIZE);
257    }
258
259    /// 只释放子页表帧，保留当前帧
260    ///
261    /// 遍历当前帧中的所有页表项：
262    /// - 如果是大页或叶子级别的数据页：跳过（不释放物理页，也不清除映射）
263    /// - 如果是非叶子级别的页表指针：递归释放子页表帧，并清除PTE
264    ///
265    /// # Parameters
266    /// - `level`: 当前帧所在的页表级别（1=叶子，数字越大级别越高）
267    pub fn deallocate_children(&mut self, level: usize) {
268        // 反向遍历以避免索引变化问题
269        for i in (0..self.len()).rev() {
270            // 先获取当前PTE的状态
271            let entry_info = {
272                let entries = self.as_slice();
273                if i < entries.len() {
274                    let entry = entries[i];
275                    (
276                        entry.present(),
277                        entry.huge(level > 1),
278                        entry.paddr(level > 1),
279                    )
280                } else {
281                    (false, false, crate::PhysAddr::from_usize(0))
282                }
283            };
284
285            let (is_valid, is_huge, paddr) = entry_info;
286
287            if !is_valid {
288                continue;
289            }
290
291            // 如果是大页或叶子级别的数据页：跳过，保持映射不变
292            if is_huge || level == 1 {
293                continue;
294            }
295            // 否则是非叶子级别的页表指针，递归释放子页表帧
296            else {
297                let mut child_frame = Frame::<T, A>::from_paddr(paddr, self.allocator.clone());
298                child_frame.deallocate_recursive(level - 1);
299
300                // 子页表帧已释放，清除PTE
301                let entries_mut = self.as_slice_mut();
302                entries_mut[i].clear();
303            }
304        }
305    }
306
307    /// 递归查找虚拟地址对应的页表项
308    ///
309    /// # 参数
310    /// - `vaddr`: 要查找的虚拟地址
311    /// - `level`: 当前页表级别
312    ///
313    /// # 返回值
314    /// - `Ok(T::P)`: 找到的页表项
315    /// - `Err(PagingError)`: 查找失败
316    pub fn translate_recursive(&self, vaddr: VirtAddr, level: usize) -> PagingResult<T::P> {
317        let (pte, _) = self.translate_recursive_with_level(vaddr, level)?;
318        Ok(pte)
319    }
320
321    /// 递归查找虚拟地址对应的页表项，同时返回该PTE所在的级别
322    ///
323    /// # 参数
324    /// - `vaddr`: 要查找的虚拟地址
325    /// - `level`: 当前页表级别
326    ///
327    /// # 返回值
328    /// - `Ok((T::P, usize))`: 找到的页表项及其所在的级别
329    /// - `Err(PagingError)`: 查找失败
330    pub fn translate_recursive_with_level(
331        &self,
332        vaddr: VirtAddr,
333        level: usize,
334    ) -> PagingResult<(T::P, usize)> {
335        let (pte, level) = self.find_occupied_leaf(vaddr, level)?;
336        if !pte.present() {
337            return Err(PagingError::not_mapped());
338        }
339        Ok((pte, level))
340    }
341
342    pub(crate) fn find_occupied_leaf(
343        &self,
344        vaddr: VirtAddr,
345        level: usize,
346    ) -> PagingResult<(T::P, usize)> {
347        // 计算当前级别的页表索引
348        let index = Self::virt_to_index(vaddr, level);
349
350        // 获取页表项
351        let entries = self.as_slice();
352        let pte = entries[index];
353
354        if pte.unused() {
355            return Err(PagingError::not_mapped());
356        }
357
358        // 如果是大页映射或叶子级别，直接返回页表项及其级别
359        if pte.huge(level > 1) || level == 1 {
360            return Ok((pte, level));
361        }
362
363        // 否则，继续递归到下一级页表
364        if level > 1 {
365            if !pte.present() {
366                return Err(PagingError::hierarchy_error(
367                    "Non-present intermediate entry is not a leaf",
368                ));
369            }
370            let child_frame: Frame<T, A> = Frame::from_pte(&pte, level, self.allocator.clone());
371            return child_frame.find_occupied_leaf(vaddr, level - 1);
372        }
373
374        // 不应该到达这里
375        Err(PagingError::hierarchy_error(
376            "Invalid page table level during translation",
377        ))
378    }
379
380    /// 递归释放指定的单个页表项
381    ///
382    /// 如果该PTE指向有效的子页表，则递归释放该子页表及其所有子帧
383    /// 在释放前将PTE设为invalid
384    ///
385    /// 注意：只释放页表帧，不释放映射的物理页
386    ///
387    /// # Parameters
388    /// - `index`: 要释放的PTE索引
389    /// - `level`: 当前帧所在的页表级别
390    pub fn dealloc_entry_recursive(&mut self, index: usize, level: usize) -> bool {
391        if index >= self.len() || level <= 1 {
392            return false;
393        }
394
395        let entries = self.as_slice();
396        let entry = &entries[index];
397        if entry.present() && !entry.huge(true) {
398            // 递归释放子帧（子帧的级别是 level - 1）
399            let mut child_frame = Frame::<T, A>::from_pte(entry, level, self.allocator.clone());
400            child_frame.deallocate_recursive(level - 1);
401
402            // 将当前PTE设为invalid
403            let entries_mut = self.as_slice_mut();
404            entries_mut[index].clear();
405
406            true
407        } else {
408            false
409        }
410    }
411
412    pub(crate) fn clone_entry_from(
413        &mut self,
414        source: &Self,
415        index: usize,
416        level: usize,
417    ) -> PagingResult<bool> {
418        if index >= self.len() || index >= source.len() {
419            return Err(PagingError::hierarchy_error(
420                "Entry index exceeds page-table frame size",
421            ));
422        }
423        if !self.as_slice()[index].unused() {
424            return Ok(false);
425        }
426
427        let source_entry = source.as_slice()[index];
428        if source_entry.unused() {
429            return Ok(false);
430        }
431        if level == 1 || source_entry.huge(true) {
432            self.as_slice_mut()[index] = source_entry;
433            return Ok(true);
434        }
435        if !source_entry.present() {
436            return Err(PagingError::hierarchy_error(
437                "Non-present intermediate entry is not a leaf",
438            ));
439        }
440
441        let source_child = Self::from_paddr(source_entry.paddr(true), source.allocator.clone());
442        let mut target_child = Self::new(self.allocator.clone())?;
443        if let Err(err) = target_child.clone_children_from(&source_child, level - 1) {
444            target_child.deallocate_recursive(level - 1);
445            return Err(err);
446        }
447
448        self.as_slice_mut()[index] = T::P::new_table(target_child.paddr);
449        Ok(true)
450    }
451
452    fn clone_children_from(&mut self, source: &Self, level: usize) -> PagingResult {
453        for index in 0..source.len() {
454            self.clone_entry_from(source, index, level)?;
455        }
456        Ok(())
457    }
458}
459
460const fn cal_index_bits<T: TableMeta>() -> usize {
461    let mut bits = 0;
462    let len = T::LEVEL_BITS.len();
463    let mut i = 0;
464    while i < len {
465        bits += T::LEVEL_BITS[i];
466        i += 1;
467    }
468    bits
469}
page_table_generic/frame.rs

page_table_generic/
frame.rs
