首先感谢助教组精心编写的文档。rcore 实验物理内存页式管理一节中给出的 `SegmentTreeAllocator` 实现我有些许疑惑的地方。
首先,结构体中各字段没有给出注释,结合上下文的代码,我推测:
但是仔细分析了代码,并结合我自己的样例,发现程序实际会比预期多分配一层的线段树结点,造成不必要的浪费,而且导致实际访问到的线段树结点可能会超出a数组的长度 `MAX_PHYSICAL_PAGES << 1` 。这是因为 m 可能取 n 的2倍左右,而代码在`init`的时候有一个 `for i in (1..(self.m << 1)) {...}`
同时,原有实现的 alloc 和 dealloc 程序也有若干有待优化的点(例如提前结束循环)
综上,我对现有 `SegmentTreeAllocator` 实现表示质疑,并尝试给出在细节处理上稍有不同的下面这种实现,经本人的测试,运行结果暂时没有bug,表达逻辑可能有待优化,但理论上应该更比原实现更优。欢迎大家提出疑议和指正!
```rust
pub struct SegmentTreeAllocator {
// assume the tree root's index is 1
// availability data buffer, 1 - available, 0 - occupied
a: [bool; MAX_PHYSICAL_PAGES << 1],
// number of internal nodes
m: usize,
// number of ppn
n: usize,
// size of buffer used
size: usize,
offset: usize,
}
#[inline(always)]
fn ceil_to_power_of_2(n: usize) -> usize {
let mut p = 1;
while p < n { p <<= 1; }
p
}
#[inline(always)]
fn l_child(n: usize) -> usize { (n << 1) }
#[inline(always)]
fn r_child(n: usize) -> usize { (n << 1) | 1 }
#[inline(always)]
fn parent(n: usize) -> usize { (n >> 1) }
impl SegmentTreeAllocator {
// init with ppn ranged [l, r)
pub fn init(&mut self, l: usize, r: usize) {
self.n = r - l;
assert!(self.n > 1);
self.m = ceil_to_power_of_2(self.n) - 1;
self.size = r_child(self.m);
self.offset = l;
for i in (1..=self.m + self.n) { self.a[i] = true; }
for i in (self.m + self.n + 1..=self.size) { self.a[i] = false; };
}
// allocate a physical page (left comes first), return the ppn
pub fn alloc(&mut self) -> Option<usize> {
if !self.a[1] {
println!("No available physical page!");
return None;
}
let mut p: usize = 2;
while p <= self.m { // not at the leaves
if self.a[p] {
p = l_child(p);
} else if self.a[p + 1] {
p = l_child(p + 1);
} else {
unreachable!()
}
}
if self.a[p] { // at some leaf
;
} else if self.a[p + 1] {
p = p + 1;
} else {
unreachable!()
}
self.a[p] = false; // mark
let ppn = self.offset + p - self.m - 1;
// update ancestors
p = parent(p);
while p > 0 {
let available = self.a[l_child(p)] | self.a[r_child(p)];
if available { break; }
self.a[p] = false;
p = parent(p);
}
Some(ppn)
}
// deallocate a physical page `p`, panic if the specified page not found
pub fn dealloc(&mut self, ppn: usize) {
assert!(ppn >= self.offset);
let mut p = ppn - self.offset;
assert!(p < self.n);
p += self.m + 1;
if self.a[p] {
println!("Cannot dealloc physical page {}, which is already free!", p);
return;
}
self.a[p] = true;
// update ancestors
p = parent(p);
while p > 0 {
let available = self.a[l_child(p)] | self.a[r_child(p)];
if !self.a[p] && available { // has update
self.a[p] = true;
p = parent(p);
} else { // no update
break;
}
}
}
}
```