首先感谢助教组精心编写的文档。rcore 实验物理内存页式管理一节中给出的 `SegmentTreeAllocator` 实现我有些许疑惑的地方。

首先，结构体中各字段没有给出注释，结合上下文的代码，我推测：

1. 线段树的根的index是1，底层叶子节点表示每个物理页是否可用。
2. `m` 是定位第一个物理页结点在线段树中的index的。

但是仔细分析了代码，并结合我自己的样例，发现程序实际会比预期多分配一层的线段树结点，造成不必要的浪费，而且导致实际访问到的线段树结点可能会超出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;
        }
    }
}

}
```