os/mm/frame_allocator/
frame_allocator.rs

1//! 物理内存帧分配器模块
2//!
3//! 提供了内核用于管理和分配物理内存页帧（Frame）的机制。
4//! 采用 RAII (Resource Acquisition Is Initialization) 模式，确保分配的帧
5//! 在超出作用域时自动被回收。
6
7use crate::config::PAGE_SIZE;
8use crate::mm::address::{ConvertablePaddr, PageNum, Ppn, PpnRange, UsizeConvert};
9use crate::sync::SpinLock;
10use alloc::vec::Vec;
11use lazy_static::lazy_static;
12
13/// 物理帧跟踪器。
14/// 实现了 RAII 模式：当此结构体被 drop 时，它所管理的物理页帧会被自动回收。
15#[derive(Debug)]
16pub struct FrameTracker(Ppn);
17
18impl FrameTracker {
19    /// 创建一个新的 FrameTracker。
20    /// 在创建时，会自动将该物理页帧清零。
21    pub fn new(ppn: Ppn) -> Self {
22        clear_frame(ppn);
23        FrameTracker(ppn)
24    }
25
26    /// 获取此帧跟踪器所管理的物理页号 (Ppn)。
27    pub fn ppn(&self) -> Ppn {
28        self.0
29    }
30}
31
32/// 将指定的物理页帧清零。
33fn clear_frame(ppn: Ppn) {
34    unsafe {
35        // 将 Ppn 转换为虚拟地址指针
36        let va = ppn.start_addr().to_vaddr().as_mut_ptr::<u8>();
37        // 写入 PAGE_SIZE 字节的 0
38        core::ptr::write_bytes(va, 0, PAGE_SIZE);
39    }
40}
41
42impl Drop for FrameTracker {
43    /// 自动回收物理页帧。
44    fn drop(&mut self) {
45        super::dealloc_frame(self);
46    }
47}
48
49/// 连续物理帧范围跟踪器。
50/// 实现了 RAII 模式：当此结构体被 drop 时，它所管理的物理页帧范围会被自动回收。
51#[derive(Debug)]
52pub struct FrameRangeTracker {
53    range: PpnRange,
54}
55
56impl FrameRangeTracker {
57    /// 创建一个新的 FrameRangeTracker。
58    /// 在创建时，会自动将该范围内的所有物理页帧清零。
59    pub fn new(range: PpnRange) -> Self {
60        for ppn in range {
61            clear_frame(ppn);
62        }
63        FrameRangeTracker { range }
64    }
65
66    /// 获取连续帧范围的起始物理页号 (Ppn)。
67    pub fn start_ppn(&self) -> Ppn {
68        self.range.start()
69    }
70
71    /// 获取连续帧范围的结束物理页号 (Ppn)（不包含）。
72    pub fn end_ppn(&self) -> Ppn {
73        self.range.end()
74    }
75
76    /// 获取连续帧范围内的帧数量。
77    pub fn len(&self) -> usize {
78        self.range.len()
79    }
80
81    /// 获取连续帧范围的引用。
82    pub fn range(&self) -> &PpnRange {
83        &self.range
84    }
85}
86
87impl Drop for FrameRangeTracker {
88    /// 自动回收连续物理页帧。
89    fn drop(&mut self) {
90        super::dealloc_contig_frames(self);
91    }
92}
93
94/// 跟踪的物理帧集合。
95/// 用于封装单个、多个不连续或多个连续的物理帧。
96#[derive(Debug)]
97pub enum TrackedFrames {
98    /// 单个物理帧。
99    Single(FrameTracker),
100    /// 多个不连续物理帧。
101    Multiple(Vec<FrameTracker>),
102    /// 多个连续物理帧。
103    Contiguous(FrameRangeTracker),
104}
105
106lazy_static! {
107    /// 全局物理帧分配器，由自旋锁保护。
108    pub static ref FRAME_ALLOCATOR: SpinLock<FrameAllocator> = SpinLock::new(FrameAllocator::new());
109}
110
111/// 物理帧分配器。
112/// 采用简单的“延迟分配”策略，并使用回收栈来重用已释放的帧。
113pub struct FrameAllocator {
114    /// 物理帧的起始 Ppn。
115    start: Ppn,
116    /// 物理帧的结束 Ppn (不包含)。
117    end: Ppn,
118    /// 下一个要分配的物理帧 Ppn（用于连续分配区域）。
119    cur: Ppn,
120    /// 回收的物理帧堆栈。
121    recycled: Vec<Ppn>,
122}
123
124/// 延迟分配 (lazy frame allocator) 的实现
125impl FrameAllocator {
126    /// 创建一个新的帧分配器实例。
127    pub fn new() -> Self {
128        FrameAllocator {
129            // 使用 usize::MAX 作为初始值，表示未初始化状态
130            start: Ppn::from_usize(usize::MAX),
131            end: Ppn::from_usize(usize::MAX),
132            cur: Ppn::from_usize(usize::MAX),
133            recycled: Vec::new(),
134        }
135    }
136
137    /// 初始化帧分配器，设置可用的物理内存范围。
138    pub fn init(&mut self, start: Ppn, end: Ppn) {
139        self.start = start;
140        self.end = end;
141        self.cur = start;
142    }
143
144    /// 分配一个物理帧。
145    /// 优先从回收栈中取出，否则从连续未分配区域分配。
146    pub fn alloc_frame(&mut self) -> Option<FrameTracker> {
147        if let Some(ppn) = self.recycled.pop() {
148            // 从回收栈中分配
149            Some(FrameTracker::new(ppn))
150        } else if self.cur < self.end {
151            // 从连续未分配区域分配
152            let ppn = self.cur;
153            self.cur.step(); // 移动当前分配指针
154            Some(FrameTracker::new(ppn))
155        } else {
156            // 物理内存耗尽
157            None
158        }
159    }
160
161    /// 分配指定数量的物理帧（不保证连续）。
162    pub fn alloc_frames(&mut self, num: usize) -> Option<Vec<FrameTracker>> {
163        let mut frames = Vec::with_capacity(num);
164        for _ in 0..num {
165            if let Some(frame) = self.alloc_frame() {
166                frames.push(frame);
167            } else {
168                // 分配失败，需要将已分配的帧回收
169                // 由于 FrameTracker 实现了 Drop，这里直接 drop frames 即可
170                return None;
171            }
172        }
173        Some(frames)
174    }
175
176    /// 分配指定数量的**连续**物理帧。
177    pub fn alloc_contig_frames(&mut self, num: usize) -> Option<FrameRangeTracker> {
178        if num == 0 {
179            return None;
180        }
181
182        // 检查是否有足够的连续帧
183        let required_end = self.cur + num;
184        if required_end <= self.end {
185            let start = self.cur;
186            // 移动分配指针到新的连续区域之后
187            self.cur = required_end;
188            let range = PpnRange::from_start_len(start, num);
189            Some(FrameRangeTracker::new(range))
190        } else {
191            // 物理内存不足
192            None
193        }
194    }
195
196    /// 分配指定数量的**连续**物理帧，并确保起始地址对齐到 `align_pages` 页的边界。
197    pub fn alloc_contig_frames_aligned(
198        &mut self,
199        num: usize,
200        align_pages: usize,
201    ) -> Option<FrameRangeTracker> {
202        if num == 0 {
203            return None;
204        }
205
206        debug_assert!(
207            align_pages.is_power_of_two(),
208            "Alignment must be power of 2" // 对齐必须是 2 的幂
209        );
210
211        // 向上对齐当前分配指针 `self.cur`
212        let aligned_cur_val =
213            (self.cur.as_usize() + align_pages - 1).div_ceil(align_pages) * align_pages;
214        let aligned_cur = Ppn::from_usize(aligned_cur_val);
215
216        // 检查对齐后是否有足够的空间
217        let required_end = aligned_cur + num;
218        if required_end <= self.end {
219            // 将跳过的帧（self.cur 到 aligned_cur 之间）加入 recycled 栈
220            for ppn_val in self.cur.as_usize()..aligned_cur.as_usize() {
221                self.recycled.push(Ppn::from_usize(ppn_val));
222            }
223
224            // 更新当前分配指针
225            self.cur = required_end;
226            let range = PpnRange::from_start_len(aligned_cur, num);
227            Some(FrameRangeTracker::new(range))
228        } else {
229            // 物理内存不足
230            None
231        }
232    }
233
234    /// 回收一个物理帧。
235    /// 尝试将回收的帧与当前分配指针前的连续空闲区域合并。
236    pub fn dealloc_frame(&mut self, frame: &FrameTracker) {
237        // 检查帧是否在有效范围内
238        debug_assert!(
239            frame.ppn() >= self.start && frame.ppn() < self.end,
240            "dealloc_frame: frame out of range" // 回收帧超出范围
241        );
242        // 检查帧是否已被分配 (即在当前指针之前且不在回收栈中)
243        debug_assert!(
244            frame.ppn() < self.cur && self.recycled.iter().all(|&ppn| ppn != frame.ppn()),
245        );
246
247        let ppn = frame.ppn();
248        self.recycled.push(ppn);
249        // 对回收栈进行排序，以便于连续合并检查
250        self.recycled.sort_unstable();
251
252        if let Some(&last) = self.recycled.last() {
253            // 检查回收栈顶部的帧是否是当前分配指针前面的连续帧
254            if last + 1 == self.cur {
255                // 回收连续帧
256                let mut new_cur = last;
257                self.recycled.pop();
258                while let Some(&top) = self.recycled.last() {
259                    if top + 1 == new_cur {
260                        new_cur = top;
261                        self.recycled.pop();
262                    } else {
263                        break;
264                    }
265                }
266                self.cur = new_cur;
267            }
268        }
269    }
270
271    /// 回收一个连续的物理帧范围。
272    /// 尝试将回收的帧与当前分配指针前的连续空闲区域合并。
273    pub fn dealloc_contig_frames(&mut self, frame_range: &FrameRangeTracker) {
274        let start = frame_range.start_ppn();
275        let end = frame_range.end_ppn();
276        // 检查范围是否在有效范围内
277        debug_assert!(
278            start >= self.start && end <= self.end,
279            "dealloc_contig_frames: frame range out of range" // 回收帧范围超出范围
280        );
281        // 检查范围是否已被分配 (即在当前指针之前)
282        debug_assert!(
283            end <= self.cur,
284            "dealloc_contig_frames: frame range not allocated" // 回收帧范围未被分配
285        );
286
287        // 将连续帧范围内的所有 Ppn 加入回收栈
288        for ppn in frame_range.range().into_iter() {
289            self.recycled.push(ppn);
290        }
291        // 排序以支持连续合并
292        self.recycled.sort_unstable();
293
294        if let Some(&last) = self.recycled.last() {
295            // 检查回收栈顶部的帧是否是当前分配指针前面的连续帧
296            if last + 1 == self.cur {
297                // 回收连续帧
298                let mut new_cur = last;
299                self.recycled.pop();
300                while let Some(&top) = self.recycled.last() {
301                    if top + 1 == new_cur {
302                        new_cur = top;
303                        self.recycled.pop();
304                    } else {
305                        break;
306                    }
307                }
308                self.cur = new_cur;
309            }
310        }
311    }
312
313    /// 获取总的物理帧数
314    pub fn total_frames(&self) -> usize {
315        self.end.as_usize() - self.start.as_usize()
316    }
317
318    /// 获取已分配的帧数
319    pub fn allocated_frames(&self) -> usize {
320        let allocated = self.cur.as_usize() - self.start.as_usize();
321        let recycled = self.recycled.len();
322        allocated - recycled
323    }
324
325    /// 获取空闲的帧数
326    pub fn free_frames(&self) -> usize {
327        let total = self.total_frames();
328        let allocated = self.allocated_frames();
329        total - allocated
330    }
331
332    /// 获取帧分配器的当前状态
333    /// # 返回值
334    /// - 当前分配指针的 Ppn
335    /// - 物理帧的结束 Ppn (不包含)
336    /// - 回收栈的长度
337    /// - 已分配的帧数
338    /// - 空闲的帧数
339    pub fn get_stats(&self) -> (usize, usize, usize, usize, usize) {
340        (
341            self.cur.as_usize(),
342            self.end.as_usize(),
343            self.recycled.len(),
344            self.allocated_frames(),
345            self.free_frames(),
346        )
347    }
348}
os/mm/frame_allocator/frame_allocator.rs

os/mm/frame_allocator/
frame_allocator.rs
