oscamp：字节分配器 Chaos

分析内存结构

堆中的 `Vec<Vec<u8>>` 结构数据

使用 Slab 分配器，并在 alloc 和 dealloc 函数，中分别打印 Layout。在打印结果中可以看到一些比较特殊的内存大小分别为 96、192、384

这是什么呢？根据 lab1/src/main.rs 中的测例代码分析可得知 let mut items: Vec<Vec<u8>> = Vec::new(); 的内层 Vec 将存放在堆内存中。

而 Rust 中的堆数据结构中的一张图片展示了 Vec 的内存结构为指针、长度和容量，每一部分各占 usize，在 64 位系统中，uszie 大小为 8 字节，即一个空数组内存占用为 24 字节，这与 96 字节仍有出入。

再观察分配情况，在 Indicator: 0 时，96 字节的 alloc 是在第一次 32 字节 alloc 后产生的，猜测是在 items.push 后进行了一次扩容，alloc_pass 修改为如下代码进行验证：

fn alloc_pass(delta: usize) -> Vec<Vec<u8>> {
    let mut items = Vec::new();
    let mut base = 32;
    loop {
        let c = (delta % 256) as u8;
        let a = vec![c; base+delta];
        items.push(a);
        println!("Item Capacity: {}", items.capacity());
        if base >= 512*1024 {
            break;
        }
        base *= 2;
    }
    items
}

结果为：

Running bumb tests...
Indicator: 0
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16

就对上了，24 * 4 = 96 24 * 8 = 192 24 * 16 = 384

同时，至少在这里来说，Vec 初始容量为 0，第一次扩容时为 4，扩容机制为每次容量翻倍。

存放数据的堆空间

再回到测例代码：

fn free_pass(items: &mut Vec<Vec<u8>>, delta: u8) {
    let total = items.len();
    for j in (0..total).rev() {
        if j % 2 == 0 {
            let ret = items.remove(j);
            assert_eq!(delta, ret[0]);
            assert_eq!(delta, ret[ret.len()-1]);
        }
    }
}

这段代码在检查是否为偶数项，偶数项数组才会被 free_pass 的 remove() 释放。

因此针对这段代码，可以在分配器中设置一个奇偶标志位，当标志位为奇数时将数据从内存的起始位置开始分配，偶数时分配在末尾位置且向起始位置增长。扩容时，不考虑内存扩容时传入的内存地址起始位置而只改变结尾位置时也无需多余操作。

Chaos 真的不 Chaos

整体结构

考虑：

堆中的 Vec<Vec<u8>> 数据结构，大小固定为 96 + 192 + 384 = 672 字节，位于可分配内存的起始位置
奇数项堆，动态增长，紧跟 672 字节
偶数项堆，动态增长，位于可分配内存的末尾位置

使用以下结构体来描述整个可分配内存区域

pub struct Chaos {
    pub vec_reserve: (usize, usize, usize),

    pub start: usize,
    pub end: usize,
    pub head: usize,
    pub tail: usize,
    pub is_even: bool,

    pub allocated: usize,
    pub total: usize,
}

内存结构如下：

!https://ice.frostsky.com/2024/12/04/31665acefb8e6fbfa3315cc85b607994.png

vec_reserve: (usize, usize, usize) 用作存储先前描述的三片特殊的堆中 Vec 元数据结构，vec_reserve 为固定长度：96 + 192 + 384 字节。

pub start: usize 和 pub end: usize 分别存储 init 或是 add_to_heap 时给定的可分配内存地址范围。

pub head: usize 和 pub tail: usize 分别存储当前奇数堆的末尾位置和偶数堆的起始位置，通过 head - start + vec_reserve 可以得出奇数堆大小，通过 end - tail 则可以得出偶数堆大小。

pub is_even: bool 用于记录上一次分配是奇数还是偶数，在分配的最后将其翻转。

实现

在开始之前，还要确定一个很重要的问题。目前的设计，并没有考虑扩容时分配在本程序堆内存前内存区域的地址，因此使用代码简单判断下：

pub fn add_to_heap(&mut self, start: usize, end: usize) {
    log::warn!("head: 0x{:x}, tail: 0x{:x}, start: 0x{:x}, end: 0x{:x}", self.head, self.tail, start, end);

    self.head = start;
    self.tail = end;

    panic!("add_to_heap");
}

从 add_to_heap 的输出：

Running bumb tests...
Indicator: 0
[  0.082919 0 lab_allocator::chaos:66] head, tail: 0xffffffc08026d2a0, 0xffffffc080275000
[  0.087323 0 lab_allocator::chaos:44] head: 0xffffffc08026d2a0, tail: 0xffffffc080275000, start: 0xffffffc080275000, end: 0xffffffc08027d000
[  0.091091 0 axruntime::lang_items:5] panicked at labs/lab_allocator/src/chaos.rs:49:9:
add_to_heap

可以看到后续追加的内存与当前程序的堆尾部是连续的，只需要更改 tail 字段扩容当前内存即可。

初始化以及扩容

pub unsafe fn init(&mut self, start: usize, size: usize) {
        self.vec_reserve = (start, start + 96, start + 96 + 192);

        self.start = start + 96 + 192 + 384;
        self.head = start + 96 + 192 + 384;

        self.end = start + size;
        self.tail = start + size;

        self.allocated = 96 + 192 + 384;
        self.total = self.end - self.start;
    }

    pub fn add_to_heap(&mut self, start: usize, end: usize) {
        self.end = end;
        self.tail = end;

        self.total += end - start;
    }

分配

pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> {
    let vec_reserve_ptr = match layout.size() {
        96 => Some(self.vec_reserve.0 as *const u8),
        192 => Some(self.vec_reserve.1 as *const u8),
        384 => Some(self.vec_reserve.2 as *const u8),
        _ => None,
    };

    if vec_reserve_ptr.is_some() {
        return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap());
    }

    // check if memory is overflow
    if self.tail - layout.size() <= self.head {
        return Err(());
    }

    let ptr = if self.is_even {
        let mem = self.tail - layout.size();
        self.tail = mem;

        NonNull::new(mem as *mut u8).unwrap()
    } else {
        let mem = self.head;
        self.head = mem + layout.size();

        NonNull::new(mem as *mut u8).unwrap()
    };

    self.is_even = !self.is_even;
    self.allocated += layout.size();

    Ok(ptr)
}

释放

pub fn dealloc(&mut self, pos: NonNull<u8>, layout: Layout) {
    if (pos.as_ptr() as usize) < self.start + 96 + 192 + 384 {
        return;
    }

    self.tail +=layout.size();
    self.allocated -= layout.size();
}

越界访问

第 32 轮分配时发生了 Unhandled Supervisor Page Fault，本机的 panic 位置为 0xffffffc0802005fc，远在可分配的起始地址 0xffffffc08026d2a0 前，猜测本次的 panic 发生在栈区或是发生在从 tail 进行分配或释放时发生的。

说起来很好笑，let mut pool = Vec::new(); 和 items 一样，也会占用一些堆区内存，但因为其只写不读，即使内部全部都是无效的堆内存地址也没有问题。但这提醒到了一点：在分配用于 items: Vec<Vec<u8>> 的堆内存时，使用了一个特判：

let vec_reserve_ptr = match layout.size() {
    96 => Some(self.vec_reserve.0 as *const u8),
    192 => Some(self.vec_reserve.1 as *const u8),
    384 => Some(self.vec_reserve.2 as *const u8),
    _ => None,
};

这几个数字并没有问题，但先前我们忽略了 let a = vec![c; base+delta]; 的 base 总是从 32 开始，每次 alloc 翻倍，delta 则每轮增加 1。恰好，第 32 轮的第二次 alloc 时那么不恰好的 base = 64 和 delta = 32，这不是 96 了嘛 uwu，所以到这时候，原本该分配给 items: Vec<Vec<u8>> 的地址被当作了 tail 堆的起始地址，又因为 tail 是 tail = tail - size 取得空闲地址，所以结果是越界了。

根据观察后，在 Layout 中存在字段 align，align 字段在 items: Vec<Vec<u8>> 分配中总是 8，而普通分配总是 1。

因此简单写个判断就可以解决了：

if vec_reserve_ptr.is_some() && layout.align() == 8 {
    return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap());
}

处理完这个问题后，算法成功跑到 152 轮。

Indicator: 152
[ 25.511024 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015be2, size=0xb8
[ 25.513985 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015b2a
[ 25.516487 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015b2a, size=0xd8
[ 25.519232 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f352a8
[ 25.521127 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015b2a, size=0x118
[ 25.523938 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015a12
[ 25.525770 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015a12, size=0x198
[ 25.528492 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35380
[ 25.530458 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc085015a12, size=0x298
[ 25.533267 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08501577a
[ 25.535172 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f35518, 0xffffffc08501577a
[ 25.537270 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f000, size=0x60
[ 25.540115 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc08501577a, size=0x498
[ 25.542925 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35518
[ 25.544869 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc08501577a, size=0x898
[ 25.547528 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085014ee2
[ 25.549466 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc085014ee2, size=0x1098
[ 25.552112 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f359b0
[ 25.554013 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085014ee2, size=0x2098
[ 25.558305 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085012e4a
[ 25.560458 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f36a48, 0xffffffc085012e4a
[ 25.562665 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f060, size=0xc0
[ 25.564900 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085012e4a, size=0x4098
[ 25.567790 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f36a48
[ 25.569725 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc085012e4a, size=0x8098
[ 25.572420 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08500adb2
[ 25.575027 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc08500adb2, size=0x10098
[ 25.577664 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f3aae0
[ 25.579570 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc08500adb2, size=0x20098
[ 25.582385 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084fead1a
[ 25.584478 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc084fead1a, size=0x40098
[ 25.587429 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f4ab78
[ 25.591690 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

预分配：尽可能使用更多的内存

在观察 152 轮和 add_memory 的 log 时发现：

本轮的偶数区并没有得到释放。
内存从一开始分配起，每次扩容即为前一次空间 x2，最大为 32 MB。而 qemu 虚拟机分配的是 128MB，只分配到了 32MB，显然还不是极限。

pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> { Err(()) }

Indicator: 0
[  0.088199 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080275000, end=0xffffffc08027d000 # 32768
[  0.090785 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08027d000, end=0xffffffc08028d000 # 65536
[  0.093210 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08028d000, end=0xffffffc0802ad000 # 131072
[  0.095720 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ad000, end=0xffffffc0802ed000 # 262144
[  0.098368 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ed000, end=0xffffffc08036d000 # 524288
[  0.100928 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08036d000, end=0xffffffc08046d000 # 1048576
[  0.103497 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08046d000, end=0xffffffc08066d000 # 2097152
[  0.106127 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08066d000, end=0xffffffc080a6d000 # 4194304
[  0.108677 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080a6d000, end=0xffffffc08126d000 # 8388608
[  0.111219 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08126d000, end=0xffffffc08226d000 # 16777216
[  0.114057 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08226d000, end=0xffffffc08426d000 # 33554432 byte = 32MB
[  0.117634 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

因此，我们可以打第一次 alloc 开始就强迫系统预分配一大堆内存给测例。比如在 pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> 的合理位置添加下面的代码：

// get as much memory as possible
if self.end <= 0xffffffc08426d000 {
    return Err(());
}

修改后，轮数为 189。此时，内存分配量到达了 64MB，这样下来仍有很多剩余空间。

再挤一挤，内存还是有的

看一眼 axalloc 中：

let old_size = balloc.total_bytes();
let expand_size = old_size
    .max(layout.size())
    .next_power_of_two()
    .max(PAGE_SIZE);
let heap_ptr = match self.alloc_pages(expand_size / PAGE_SIZE, PAGE_SIZE) {
    Ok(ptr) => ptr,
    Err(e) => panic!("Bumb: {:?}.", e),
};

不难发现 axalloc 是依赖于 total_bytes() 来判断该扩容多少内存。

简单一些处理，只需要修改原先的 total_bytes 代码，使得 total_bytes 永远返回 0。

pub fn total_bytes(&self) -> usize {
    0
}

修改后的最终轮数为 245。