物理内存探测和分配的一个alternative版本
匿名2023/07/31 19:51:19提问
    lab4student
338

原文实在是太NOI-istic。小生在此抛砖引玉给出一个人类可读版本的:

// root at one as routine
// inline helper funtion, they can be better to be written in marco or association function
impl SegmentTreeAllocator {
    #[inline]
    fn left_child(&self, idx : usize) -> usize {idx << 1}
    #[inline]
    fn right_child(&self, idx : usize) -> usize {(idx << 1) | 1}
    #[inline]
    fn update(&mut self, idx : usize) {
        let mut temp = idx >> 1;
        while temp > 0 {
            // if left child and right child is full, then nodes[p] is full
            self.nodes[temp] = self.nodes[self.left_child(temp)] & self.nodes[self.right_child(temp)];
            temp >>= 1;
        }
    }
}

// consturct a complete binary tree and put all real node into leaves.
// so [l,r) length assignment needs pow(2, log(2,r-l)+1) leaves to store, from lfet most child to right
impl SegmentTreeAllocator {
// init [l,r) interval
pub fn init(&mut self, l : usize, r : usize) {
self.offset = l;
self.total = r - l; // total may be not a power of 2
// compute the first key index
self.leaf_begin = 1;
// why add 2?
// one for root start from one instead of zero
// another one for total number is contained, say we have 10 number,
// naturally, the condition shall be less than 11, you need to take 10 into account
while self.leaf_begin < self.total + 2 {
self.leaf_begin <<= 1;
}
// since [l,r) may not be aligned, we need to let extra element marked as invalid
// on level of leaf, you have pow(2,leaf_begin)'s leaves.
// so total elements of this complete binary tree should be
// 1 + 2 + 4 + ... + pow(2,leaf_begin)
// pow(2,leaf_begin+1) - 1, namely range from [1,pow(2,leaf_begin+1)
for i in (1..(self.leaf_begin << 1)) {self.nodes[i] = 1;}
// avaiable part, please notice it shall start from left child, which is even
// different from origin version,
// so you can see above self.offset is l, not l-1
for i in (0..self.total) {self.nodes[self.leaf_begin + i] = 0;}
// update parents who are available
for i in (1..self.leaf_begin).rev() {
self.nodes[i] = self.nodes[self.left_child(i)] & self.nodes[self.right_child(i)];
}
}

// allocate a physical page, return a physical page number
pub fn alloc(&amp;mut self) -&gt; usize {
    // assume that we never run out of physical memory
    if self.nodes[1] == 1 {
        panic!(&#34;physical memory depleted!&#34;);
    }
    // from top, find first available page
    let mut p = 1;
    while p &lt; self.leaf_begin {
        if self.nodes[self.left_child(p)] == 0 {
            p = self.left_child(p);
        } else{
            p = self.right_child(p);
        }
    }
    // since it has offset, we need to compute
    let result = (p - self.leaf_begin) &#43; self.offset;
    // it has been allocated, we need to mark it as used
    self.nodes[p] = 1;
    // update its ancestor
    self.update(p);
    result
}

// recycle the target page
pub fn dealloc(&amp;mut self, idx : usize) {
    // notice there is a difference between alloc and de-alloc
    // the operation order is inversed.
    let pos_in_tree = (idx - self.offset) &#43; self.leaf_begin;
    // we recycle a used one
    assert!(self.nodes[pos_in_tree] == 1);
    self.nodes[pos_in_tree] = 0;
    self.update(pos_in_tree);
}

}

// singleton
pub static SEGMENT_TREE_ALLOCATOR: Mutex<SegmentTreeAllocator> = Mutex::new(SegmentTreeAllocator {
nodes: [0; MAX_PHYSICAL_PAGES << 1],
leaf_begin: 0,
total: 0,
offset: 0
});

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