关于rcore中的SegmentTreeAllocator实现的疑问和想法
匿名2023/07/31 19:50:24提问
    lab2student
323

首先感谢助教组精心编写的文档。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 &lt;&lt; 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(&amp;mut self) -&gt; Option&lt;usize&gt; {
    if !self.a[1] {
        println!(&#34;No available physical page!&#34;);
        return None;
    }
    let mut p: usize = 2;
    while p &lt;= self.m { // not at the leaves
        if self.a[p] {
            p = l_child(p);
        } else if self.a[p &#43; 1] {
            p = l_child(p &#43; 1);
        } else {
            unreachable!()
        }
    }
    if self.a[p] { // at some leaf
        ;
    } else if self.a[p &#43; 1] {
        p = p &#43; 1;
    } else {
        unreachable!()
    }
    self.a[p] = false; // mark
    let ppn = self.offset &#43; p - self.m - 1;
    // update ancestors
    p = parent(p);
    while p &gt; 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 &#96;p&#96;, panic if the specified page not found
pub fn dealloc(&amp;mut self, ppn: usize) {
    assert!(ppn &gt;= self.offset);
    let mut p = ppn - self.offset;
    assert!(p &lt; self.n);
    p &#43;= self.m &#43; 1;
    if self.a[p] {
        println!(&#34;Cannot dealloc physical page {}, which is already free!&#34;, p);
        return;
    }
    self.a[p] = true;
    // update ancestors
    p = parent(p);
    while p &gt; 0 {
        let available = self.a[l_child(p)] | self.a[r_child(p)];
        if !self.a[p] &amp;&amp; available { // has update
            self.a[p] = true;
            p = parent(p);
        } else { // no update
            break;
        }
    }
}

}
```

回答(0
    推荐问答
      Simple Empty
      暂无数据