本文中只包含了最核心的功能代码，一些工具函数等则不会列出，如果想要了解完整的实现，请前往 GitHub
鉴于本系列的目的是实现一个内存管理器，因此在内存分配器这方面，我并不打算下太多功夫，但是在此刻不放让我们抛出一个问题来抛砖引玉：内存管理器和内存分配器究竟又有什么区别呢？
这个问题的答案倒也没那么复杂，内存分配器可以视作内存管理器的一部分，在一个编程语言的运行时中，一个内存管理器应当能够分配对象，销毁对象，合理的利用和管理内存资源，保证利用效率的最大化。许多人会认为垃圾回收器是内存管理器的一部分，然而在很多语言的实现中，这两者实际上是同义词：垃圾回收器不仅要负责回收不用的对象，还要负责压缩内存空间，以及分配新内存。
如果我们要分配一个对象，第一部自然是分配和这个对象的大小相同的一块内存，那么内存分配器该如何实现呢？现在的大部分 OS 上，都有现成的暴露出来的内存分配和回收函数（例如 C 的 malloc 和 free 等函数在 Unix 和 Windows 上实际会指向不同的平台实现），我们所要做的只是调用这些函数而已，不过对于一个完整的内存管理器来说，我们还需要考虑另外一点：内存碎片
想必点进本文的读者应该都知道，应用的内存区域中有一块空间叫做堆空间，专门用来给程序运行时的较大内存分配使用，可是，堆内存的空间是有限的，其中的对象不会自己移动，如果我们随便的在堆中分配并且释放对象，整个堆就会像被扎满孔的海绵一样，虽然总体来看剩的空间还很多，但是分开来看每一段都是一块很小的内存碎片，难以容下需要一大块连续内存的对象分配。
这个问题——尽管相当有年头，却也是一个非常棘手的问题，一些内存分配器会采取一些聪明的策略，比如用类似线段树这样的结构去维护被分配的内存区间，一旦其中有两块相邻的内存碎片都被回收，就马上把他们两个合成一块大的碎片。这样的策略相当之有效，然而其问题依然在于无法做到 100% 的利用内存空间，总有些内存碎片碎片不会那么恰巧的被一同回收，使用这样内存分配器的语言于是会相当的考验其实现者和使用该语言的人的技术。
幸运的是，我们不需要考虑这个问题，我们所要实现的内存管理器，正是一个垃圾回收器，确切的说，是一个 标记-压缩垃圾回收器，这意味着每当一批对象被回收之后，我们的内存管理器就会通过移动剩余的对象来压缩空间（有点像是把一管松散的羽毛球全部捅到最里面），从而彻底避免内存碎片的问题，不仅如此，因为不用思考内存碎片的问题，我们的内存分配器可以采用一种叫做 Bumping Pointer 相当简单而且速度异常快的内存分配策略，简单来说，如果把内存想象成一个线性的字节数组，那么我们的内存分配器会有一个指针指向尚未分配的内存起始，当我们需要特定大小的内存的时候，只需要将这个指针向后移动对应长度的距离，接着返回指向这一段内存的一个指针就好了。无须任何复杂的数据结构，这样的一个内存分配器的分配速度永远是常数级别的。
说了这么多，也终于到了该写一点代码的时候了，首先，我们的内存分配器应当在在最开始向操作系统申请一大块内存，叫做已提交的内存，在程序的运行过程中，像这样“从操作系统申请一大块内存”的操作可能会发生多次，因为上一次申请的内存可能不够用，我们把每次申请到的这一大块内存称为一个 HeapBlock，这样，我们的内存分配器就至少需要一个列表，来维护所有分配的 HeapBlock，而 HeapBlock 的实现如下：
#[derive(PartialEq, Eq, Hash, Copy, Clone)]
pub struct HeapBlock {
pub start: *mut u8,
pub unallocated_start: *mut u8,
pub size: usize,
}
impl HeapBlock {
pub fn contains(&self, ptr: *mut u8) -> bool {
let start = self.start as usize;
let end = start + self.size;
let ptr = ptr as usize;
ptr >= start && ptr < end
}
pub fn relative_offset<T>(&self, ptr: *const T) -> usize {
let start = self.start as usize;
let ptr = ptr as usize;
ptr - start
}
pub fn absolute_offset<T>(&self, offset: usize) -> *mut T {
unsafe { self.start.add(offset) as *mut T }
}
pub fn block_end(&self) -> *mut u8 {
unsafe { self.start.add(self.size) }
}
pub fn allocated_size(&self) -> usize {
unsafe { self.unallocated_start.sub_ptr(self.start) }
}
}
其所包含的都是一些相当基本的函数：unallocated_start 是我们指向未分配内存块的指针，start 是当前 HeapBlock 的起始位置的指针，而 size 是这块内存块的长度。其余的函数应该都是不言自明的，我们有：
contains检查某个指针是否位于当前HeapBlock内relative_offset返回某个指针相对于当前HeapBlock起始的距离absolute_offset返回距离当前HeapBlock起始位置距离为offset的指针block_end返回当前HeapBlock的末尾allocated_size返回当前HeapBlock中已被分配的内存的大小
接下来，我们就要实现基于此的 HeapAllocator，也就是我们的内存分配器了，其描述如下：
pub struct HeapAllocator {
pub size: usize,
pub committed_regions: LinkedHashMap<Layout, HeapBlock>,
pub expand_callback: Box<dyn FnMut(HeapBlock)>
}
其中 committed_regions 即为程序所持有的所有内存块，Layout 是 Rust 中的一个类型，描述了这个内存块的布局，在此不用过多了解，expand_callback 是在分配新的内存块，也就是向 committed_regions 中插入新的项时被调用的回调。而 size 则是目前分配器已经分配的内存的总大小
在程序开始执行之前，我们还没有向操作系统申请任何内存，因此，向操作系统申请一块新的内存，自然是我们要做的第一件事，这个函数被命名为 expand，这个函数的签名如下：
unsafe fn expand(&mut self, desired_size: usize, align: usize) -> Result<(), AllocatorError>
desired_size 告诉操作系统我们要申请的内存块有多大，而 align 则表明了这块内存的对齐（也就是说，这块内存的大小应该是 align的整数倍），这是因为现代 CPU 对于地址对齐之后的读写操作效率更高。在这个函数中，我们首先要判断真正要申请的内存块究竟有多大：
let mut new_layout_size = if self.size == 0 { INITIAL_SIZE } else { self.size * EXPAND_FACTOR };
if new_layout_size < desired_size {
new_layout_size = (desired_size + ((!desired_size + 1) & (align - 1))) * EXPAND_FACTOR;
}
如果 desired_size 是0，那么我们就会用一个默认大小作为分配大小，如果不是0，我们首先会尝试将分配大小设定为当前已分配总大小的 EXPAND_FACTOR 倍，其中这个倍率大小可以自由决定（如果我们不考虑一些硬件层面的优化的话），这样是为了使每次扩展堆时，堆大小的增长符合一个大致的规律，不至于太大浪费内存，也不至于太小让分配的内存总是不够用（我相信一定有一些启发性的算法来动态决定这个 EXPAND_FACTOR 的大小，可惜这样的内容不在本文的范围之内）。如果这样尝试之后，新内存块的大小依然不足以容纳 desired_size，那么我们会干脆把其大小设置为 desired_size 的 EXPAND_FACTOR 倍，这里用了一点小小的位运算，这个位运算的作用是把新内存块的大小向上取至 align 的整数倍，从而满足对齐的要求。
在完成新内存块大小的分配后，要做的事情就是分配内存了，这里要利用到 Rust 的内存分配API，准确来说，是 std::alloc 下的类型，Rust 的内存分配要求传入一个用于描述要分配的类型的对象，也就是 Layout 对象，在这里，我们要分配的应该是一个指定大小的字节数组（也就是内存的本质），因此我们会首先创建这样的一个 Layout，接着修改目前已分配的总内存大小，最后，我们调用 std::alloc::alloc_zeroed(new_layout) 来向操作系统申请一块新内存，这个函数会返回一个指向我们申请的内存的首地址：
let new_layout = match Layout::array::<u8>(new_layout_size) {
Ok(l) => l,
Err(_) => return Err(AllocatorError::FailedToCreateLayout)
};
self.size += new_layout.size();
let ptr = alloc::alloc_zeroed(new_layout);
最终，在申请完成之后，我们要为这片内存创建一个对应的 HeapBlock 对象，用来在我们之后的代码中作为这一块内存的抽象和描述符（Rust 自带的 Layout 显然是不够用的）
let region = HeapBlock {
start: ptr,
unallocated_start: ptr,
size: new_layout.size()
};
self.committed_regions.insert(new_layout, region);
(self.expand_callback)(region);
（注意此处调用了 self.expand_callback，也就是我们说的在堆扩容时会被调用的函数）
于是最终，我们的堆扩容函数就变成了这个样子：
unsafe fn expand(&mut self, desired_size: usize, align: usize) -> Result<(), AllocatorError> {
// 计算要扩容的真实大小
let mut new_layout_size = if self.size == 0 { INITIAL_SIZE } else { self.size * EXPAND_FACTOR };
if new_layout_size < desired_size {
new_layout_size = (desired_size + ((!desired_size + 1) & (align - 1))) * EXPAND_FACTOR;
}
// 向操作系统申请内存
let new_layout = match Layout::array::<u8>(new_layout_size) {
Ok(l) => l,
Err(_) => return Err(AllocatorError::FailedToCreateLayout)
};
self.size += new_layout.size();
let ptr = alloc::alloc_zeroed(new_layout);
// 创建这一块已分配内存的描述符，也即 HeapBlock
let region = HeapBlock {
start: ptr,
unallocated_start: ptr,
size: new_layout.size()
};
self.committed_regions.insert(new_layout, region);
(self.expand_callback)(region);
Ok(())
}
在实现了 expand 函数之后，就如同上面所说的，用于分配的 alloc 函数就要简单的多了，它的函数签名如下：
unsafe fn alloc(&mut self, size: usize, align: usize) -> Result<*mut u8, AllocatorError>
其中 size 的含义不言自明，而 align 这次则和 expand 中的有些不同，在 expand 中，内存分配是操作系统负责的，我们只需要保证分配的内存大小是对齐的，而不需要思考其地址是否对齐，但是在 alloc 函数中，我们需要自己分配内存，因此在此处我们要手动将分配内存的起始位置对齐为 align 的整数倍，如果不是整数倍，我们就需要在前面 垫 一下，跳过几个地址，来保证分配的地址始终是整数倍的，这些被跳过的地址被称为 padding。在 alloc 函数中，我们首先应当找到所有已分配内存块中第一个能容纳下我们要分配的大小的那个：
// 找到第一块有足够空间的内存块
let first: Option<&Layout, &mut HeapBlock> = self.committed_regions.iter_mut().find(|entry| entry.1.allocated_size() + size <= entry.1.size);
接下来，如果其返回的对应的内存块，说明我们还有足够的空间直接在里面进行分配，如果不是，则说明我们的堆空间耗尽，需要向操作系统申请新的内存，也即扩容，之后再重新尝试分配：
match first {
Some((_, tracker)) => { // tracker: &mut HeapBlock
// 注意这里是让分配的起始地址对齐
let padding = (!(tracker.unallocated_start as usize) + 1) & (align - 1);
// 向 unallocated_start 填充 padding
tracker.unallocated_start = tracker.unallocated_start.byte_add(padding);
let ptr = tracker.unallocated_start;
// 将未分配内存起始的指针向后移动对应长度，代表我们“分配”了这一块内存
tracker.unallocated_start = tracker.unallocated_start.byte_add(size);
Ok(ptr)
},
None => {
// 如果找不到能容纳所需大小的内存块，则对堆进行扩容
self.expand(size, align)?;
// 之后再尝试分配
self.alloc(size, align).map(identity_once)
}
}
因此在最后，我们的 alloc 函数就变成了这样子：
pub unsafe fn alloc(&mut self, size: usize, align: usize) -> Result<*mut u8, AllocatorError> {
if !self.available {
return Err(AllocatorError::AllocatorClosed);
}
let first = self.committed_regions.iter_mut().find(|entry| entry.1.allocated_size() + size <= entry.1.size);
match first {
Some((_, tracker)) => {
let padding = (!(tracker.unallocated_start as usize) + 1) & (align - 1);
tracker.unallocated_start = tracker.unallocated_start.byte_add(padding);
let ptr = tracker.unallocated_start;
tracker.unallocated_start = tracker.unallocated_start.byte_add(size);
Ok(ptr)
},
None => {
self.expand(size, align)?;
self.alloc(size, align).map(identity_once)
}
}
}
现在可以说我们的内存分配器已经处于“整装待发”的状态了，要说还缺点什么，那就是释放内存的能力了，不过这倒也很好实现
pub unsafe fn free(&mut self) {
for (layout, tracker) in self.committed_regions.iter() {
alloc::dealloc(tracker.start, *layout);
}
self.available = false;
}
不过，想必你已经注意到，这个函数会一次性释放堆中的所有内存，它的作用是在程序执行完毕时释放程序占用的内存空间，至于针对单个对象的 free 函数——我们都有垃圾回收器了，为什么还需要这种东西呢？
既然内存分配器的部分已经讲完了，本文的下一节就将会讲述更抽象的概念：我们该如何分配一个对象呢？与内存分配器的简单相比，对象分配器则要复杂得多，在下一节中，我们将会讨论对象的内存布局，对象头与对象数据，向内存中写入对象，以及从内存中的某个地址读取对象，其所使用到的内存分配器就将会是我们本节所实现的。本文实现的详细代码位于 src/allocator/heap_allocator.rs 中，如果对本文的实现有疑问，或者想要完整的了解代码，包括一些工具函数，可以前往该项目查看。
Comments NOTHING