os/mm/
page_table.rs

1//! Implementation of [`PageTableEntry`] and [`PageTable`].
2
3use super::{FrameTracker, PhysAddr, PhysPageNum, StepByOne, VirtAddr, VirtPageNum, frame_alloc};
4use alloc::string::String;
5use alloc::vec;
6use alloc::vec::Vec;
7use bitflags::*;
8
9bitflags! {
10    pub struct PTEFlags: u8 {
11        const V = 1 << 0;
12        const R = 1 << 1;
13        const W = 1 << 2;
14        const X = 1 << 3;
15        const U = 1 << 4;
16        const G = 1 << 5;
17        const A = 1 << 6;
18        const D = 1 << 7;
19    }
20}
21
22#[derive(Copy, Clone)]
23#[repr(C)]
24/// page table entry structure
25pub struct PageTableEntry {
26    ///PTE
27    pub bits: usize,
28}
29
30impl PageTableEntry {
31    ///Create a PTE from ppn
32    pub fn new(ppn: PhysPageNum, flags: PTEFlags) -> Self {
33        PageTableEntry {
34            bits: ppn.0 << 10 | flags.bits as usize,
35        }
36    }
37    ///Return an empty PTE
38    pub fn empty() -> Self {
39        PageTableEntry { bits: 0 }
40    }
41    ///Return 44bit ppn
42    pub fn ppn(&self) -> PhysPageNum {
43        (self.bits >> 10 & ((1usize << 44) - 1)).into()
44    }
45    ///Return 10bit flag
46    pub fn flags(&self) -> PTEFlags {
47        PTEFlags::from_bits(self.bits as u8).unwrap()
48    }
49    ///Check PTE valid
50    pub fn is_valid(&self) -> bool {
51        (self.flags() & PTEFlags::V) != PTEFlags::empty()
52    }
53    ///Check PTE readable
54    pub fn readable(&self) -> bool {
55        (self.flags() & PTEFlags::R) != PTEFlags::empty()
56    }
57    ///Check PTE writable
58    pub fn writable(&self) -> bool {
59        (self.flags() & PTEFlags::W) != PTEFlags::empty()
60    }
61    ///Check PTE executable
62    pub fn executable(&self) -> bool {
63        (self.flags() & PTEFlags::X) != PTEFlags::empty()
64    }
65}
66///Record root ppn and has the same lifetime as 1 and 2 level `PageTableEntry`
67pub struct PageTable {
68    root_ppn: PhysPageNum,
69    frames: Vec<FrameTracker>,
70}
71
72/// Assume that it won't oom when creating/mapping.
73impl PageTable {
74    /// Create an empty `PageTable`
75    pub fn new() -> Self {
76        let frame = frame_alloc().unwrap();
77        PageTable {
78            root_ppn: frame.ppn,
79            frames: vec![frame],
80        }
81    }
82    /// Temporarily used to get arguments from user space.
83    pub fn from_token(satp: usize) -> Self {
84        Self {
85            root_ppn: PhysPageNum::from(satp & ((1usize << 44) - 1)),
86            frames: Vec::new(),
87        }
88    }
89    /// Find phsical address by virtual address, create a frame if not exist
90    fn find_pte_create(&mut self, vpn: VirtPageNum) -> Option<&mut PageTableEntry> {
91        let idxs = vpn.indexes();
92        let mut ppn = self.root_ppn;
93        let mut result: Option<&mut PageTableEntry> = None;
94        for (i, idx) in idxs.iter().enumerate() {
95            let pte = &mut ppn.get_pte_array()[*idx];
96            if i == 2 {
97                result = Some(pte);
98                break;
99            }
100            if !pte.is_valid() {
101                let frame = frame_alloc().unwrap();
102                *pte = PageTableEntry::new(frame.ppn, PTEFlags::V);
103                self.frames.push(frame);
104            }
105            ppn = pte.ppn();
106        }
107        result
108    }
109    /// Find phsical address by virtual address
110    fn find_pte(&self, vpn: VirtPageNum) -> Option<&mut PageTableEntry> {
111        let idxs = vpn.indexes();
112        let mut ppn = self.root_ppn;
113        let mut result: Option<&mut PageTableEntry> = None;
114        for (i, idx) in idxs.iter().enumerate() {
115            let pte = &mut ppn.get_pte_array()[*idx];
116            if i == 2 {
117                result = Some(pte);
118                break;
119            }
120            if !pte.is_valid() {
121                return None;
122            }
123            ppn = pte.ppn();
124        }
125        result
126    }
127    #[allow(unused)]
128    /// Create a mapping form `vpn` to `ppn`
129    pub fn map(&mut self, vpn: VirtPageNum, ppn: PhysPageNum, flags: PTEFlags) {
130        let pte = self.find_pte_create(vpn).unwrap();
131        assert!(!pte.is_valid(), "vpn {:?} is mapped before mapping", vpn);
132        *pte = PageTableEntry::new(ppn, flags | PTEFlags::V);
133    }
134    #[allow(unused)]
135    /// Delete a mapping form `vpn`
136    pub fn unmap(&mut self, vpn: VirtPageNum) {
137        let pte = self.find_pte(vpn).unwrap();
138        assert!(pte.is_valid(), "vpn {:?} is invalid before unmapping", vpn);
139        *pte = PageTableEntry::empty();
140    }
141    /// Translate `VirtPageNum` to `PageTableEntry`
142    pub fn translate(&self, vpn: VirtPageNum) -> Option<PageTableEntry> {
143        self.find_pte(vpn).map(|pte| *pte)
144    }
145    /// Translate `VirtAddr` to `PhysAddr`
146    pub fn translate_va(&self, va: VirtAddr) -> Option<PhysAddr> {
147        self.find_pte(va.clone().floor()).map(|pte| {
148            let aligned_pa: PhysAddr = pte.ppn().into();
149            let offset = va.page_offset();
150            let aligned_pa_usize: usize = aligned_pa.into();
151            (aligned_pa_usize + offset).into()
152        })
153    }
154    /// Get root ppn
155    pub fn token(&self) -> usize {
156        8usize << 60 | self.root_ppn.0
157    }
158}
159/// Translate a pointer to a mutable u8 Vec through page table
160pub fn translated_byte_buffer(token: usize, ptr: *const u8, len: usize) -> Vec<&'static mut [u8]> {
161    let page_table = PageTable::from_token(token);
162    let mut start = ptr as usize;
163    let end = start + len;
164    let mut v = Vec::new();
165    while start < end {
166        let start_va = VirtAddr::from(start);
167        let mut vpn = start_va.floor();
168        let ppn = page_table.translate(vpn).unwrap().ppn();
169        vpn.step();
170        let mut end_va: VirtAddr = vpn.into();
171        end_va = end_va.min(VirtAddr::from(end));
172        if end_va.page_offset() == 0 {
173            v.push(&mut ppn.get_bytes_array()[start_va.page_offset()..]);
174        } else {
175            v.push(&mut ppn.get_bytes_array()[start_va.page_offset()..end_va.page_offset()]);
176        }
177        start = end_va.into();
178    }
179    v
180}
181
182/// Translate a pointer to a mutable u8 Vec end with `\0` through page table to a `String`
183pub fn translated_str(token: usize, ptr: *const u8) -> String {
184    let page_table = PageTable::from_token(token);
185    let mut string = String::new();
186    let mut va = ptr as usize;
187    loop {
188        let ch: u8 = *(page_table
189            .translate_va(VirtAddr::from(va))
190            .unwrap()
191            .get_mut());
192        if ch == 0 {
193            break;
194        }
195        string.push(ch as char);
196        va += 1;
197    }
198    string
199}
200
201#[allow(unused)]
202///Translate a generic through page table and return a reference
203pub fn translated_ref<T>(token: usize, ptr: *const T) -> &'static T {
204    let page_table = PageTable::from_token(token);
205    page_table
206        .translate_va(VirtAddr::from(ptr as usize))
207        .unwrap()
208        .get_ref()
209}
210///Translate a generic through page table and return a mutable reference
211pub fn translated_refmut<T>(token: usize, ptr: *mut T) -> &'static mut T {
212    let page_table = PageTable::from_token(token);
213    let va = ptr as usize;
214    page_table
215        .translate_va(VirtAddr::from(va))
216        .unwrap()
217        .get_mut()
218}
219///Array of u8 slice that user communicate with os
220pub struct UserBuffer {
221    ///U8 vec
222    pub buffers: Vec<&'static mut [u8]>,
223}
224
225impl UserBuffer {
226    ///Create a `UserBuffer` by parameter
227    pub fn new(buffers: Vec<&'static mut [u8]>) -> Self {
228        Self { buffers }
229    }
230    ///Length of `UserBuffer`
231    pub fn len(&self) -> usize {
232        let mut total: usize = 0;
233        for b in self.buffers.iter() {
234            total += b.len();
235        }
236        total
237    }
238}
239
240impl IntoIterator for UserBuffer {
241    type Item = *mut u8;
242    type IntoIter = UserBufferIterator;
243    fn into_iter(self) -> Self::IntoIter {
244        UserBufferIterator {
245            buffers: self.buffers,
246            current_buffer: 0,
247            current_idx: 0,
248        }
249    }
250}
251/// Iterator of `UserBuffer`
252pub struct UserBufferIterator {
253    buffers: Vec<&'static mut [u8]>,
254    current_buffer: usize,
255    current_idx: usize,
256}
257
258impl Iterator for UserBufferIterator {
259    type Item = *mut u8;
260    fn next(&mut self) -> Option<Self::Item> {
261        if self.current_buffer >= self.buffers.len() {
262            None
263        } else {
264            let r = &mut self.buffers[self.current_buffer][self.current_idx] as *mut _;
265            if self.current_idx + 1 == self.buffers[self.current_buffer].len() {
266                self.current_idx = 0;
267                self.current_buffer += 1;
268            } else {
269                self.current_idx += 1;
270            }
271            Some(r)
272        }
273    }
274}
os/mm/page_table.rs

os/mm/
page_table.rs
