使用Rust编写操作系统 - 3.4 - 内存分配器设计

本文所有内容均为翻译，原文：Allocator Designs；原项目：Writing an OS in Rust

本文将展示如何从零编写堆分配器，并讨论不同的分配器设计，包括线性分配，链表分配和固定大小块分配。我们将为这三种分配器分别创建一个可用于内核的基本实现。

这个博客是在GitHub上公开开发的。如果你有任何问题或疑问，请在那里开一个issue。你也可以在底部留言。这篇文章的完整源代码可以在post-11分支中找到。

介绍

在上一篇文章中，我们向内核添加了对堆分配的基本支持。为此，我们在页表中创建了一个新的内存区域，并使用linked_list_allocatorcrate来管理该内存。现在我们有了一个工作堆，但大部分工作留给了该分配器crate，并没有去了解分配器是如何工作的。

在这篇文章中，我们将展示如何从头开始创建堆分配器，而不是依赖现有的分配器crate。我们还将讨论不同的分配器设计，包括简单的线性分配器和基本的固定大小块分配器，并使用此知识来实现性能提高的分配器（与linked_list_allocatorcrate相比）。

设计目标

分配器的主要任务是管理可用的堆内存，它需要在alloc调用中返回未使用的内存，并跟踪用dealloc释放的内存，以便实现内存重用。最重要的是，它绝不能分配已经在其他地方使用的内存，因为这将会导致未定义的行为。

除了确保正确性之外，还有许多次要任务。例如，分配器应有效地利用可用内存并减少内存碎片。此外，它应该能够很好的用于并发应用程序，并可以扩展到任意数量的处理器。为了获得最佳性能，它甚至可以针对CPU缓存优化内存布局，以提高缓存局部性并避免伪共享。

这些要求会使好的分配器非常复杂。比如jemalloc具有超过30.000行代码。不过，我们通常并不希望在内核中使用如此复杂的代码，因为在内核中一个bug就会导致严重的安全漏洞。幸运的是，与用户空间代码相比，内核代码的分配模式通常要简单得多，因此使用较为简单的分配器设计通常就足够了。

在下面的内容中，我们将介绍三种可能的内核分配器设计，并说明它们的优缺点。

线性分配器

最简单的分配器设计是线性分配器（也称为栈分配器）。它线性的分配内存，并且仅跟踪分配的字节数和分配数。线性分配器仅在非常特定的用例中使用，因为它有一个严格的限制：只能一次释放所有内存。

思路

线性分配器的思路是通过增加（“肿起来”）一个next变量来线性分配内存，该变量指向未使用内存的起点。一开始，next就是堆的起始地址。每次分配时，next都会增加，因此它始终指向已用内存和未用内存之间的边界：

next指针只会向前单方向移动，因此该方案永远不会将相同的存储区域分配出去两次。当指针到达堆尾时，已经没有更多的内存可供分配，因此下一次分配将引发一个内存不足错误。

线性分配器通常通过分配计数器实现，分配计数器在每次alloc调用时加1，在每次dealloc调用时减1。当分配计数器为零时，表示堆上的所有分配都已释放。在这种情况下，可以将next指针重置为堆的起始地址，以便再次分配完整的堆内存。

实现

我们通过声明一个新的allocator::bump子模块开始我们的实现：

in src/allocator.rs

pub mod bump;

子模块的代码位于新的src/allocator/bump.rs文件中，内容如下：

in src/allocator/bump.rs

pub struct BumpAllocator {
    heap_start: usize,
    heap_end: usize,
    next: usize,
    allocations: usize,
}

impl BumpAllocator {
    /// 创建一个空的线性分配器
    pub const fn new() -> Self {
        BumpAllocator {
            heap_start: 0,
            heap_end: 0,
            next: 0,
            allocations: 0,
        }
    }
    
    /// 使用给定的堆边界初始化线性分配器
    /// 
    /// 该方法为非安全，因为调用者必须保证提供的内存范围未被使用。
    /// 同时，该方法只能被调用一次。
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        self.heap_start = heap_start;
        self.heap_end = heap_start + heap_size;
        self.next = heap_start;
    }
}

heap_start和heap_end字段为堆内存区域的下限和上限。调用者需要确保这些地址有效，否则分配器将返回无效的内存。因此，init函数需要被标记为unsafe调用。

next字段将始终指向堆内存中的首个未使用字节，即下一次分配的起始地址。在初始化函数中将其设置为heap_start，因为在一开始整个堆都是未使用状态。在每次分配时，该字段都会增加分配出去的大小（“肿起来”），以确保我们不会两次返回相同的内存区域。

allocations字段是活动中已分配内存的简单计数器，目标是在释放最后一块已分配内存后重置分配器。初始化为0。

选择创建一个单独的init函数，而不是在new函数中直接执行初始化，是为了是我们的分配器接口与linked_list_allocatorcrate提供的分配器接口一致。这样，无需更改其他代码即可切换分配器。

为线性分配器实现GlobalAlloc

如上一篇文章所述，所有堆分配器都需要实现GlobalAlloctrait，其定义如下：

pub unsafe trait GlobalAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8;
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { ... }
    unsafe fn realloc(
        &self,
        ptr: *mut u8,
        layout: Layout,
        new_size: usize
    ) -> *mut u8 { ... }
}

仅需要实现alloc和dealloc方法，其他两个方法均具有默认实现，我们在实现时可以忽略。

首次实现尝试

让我们试着为BumpAllocator实现alloc方法：

in src/allocator/bump.rs

use alloc::alloc::{GlobalAlloc, Layout};

unsafe impl GlobalAlloc for BumpAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // TODO 对齐及边界检查
        let alloc_start = self.next;
        self.next = alloc_start + layout.size();
        self.allocations += 1;
        alloc_start as *mut u8
    }

    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
        todo!();
    }
}

首先将next字段用作分配的起始地址。然后更新next字段，使其指向分配的结束地址，即堆上的下一个未使用的地址。最后，在将分配的起始地址作为* mut u8指针返回之前，我们将分配计数器加1。

请注意，我们不执行任何边界检查或对齐调整，因此此实现尚不安全。这无关紧要，因为无论如何它都无法通过编译：

error[E0594]: cannot assign to `self.next` which is behind a `&` reference
  --> src/allocator/bump.rs:29:9
   |
26 |     unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
   |                     ----- help: consider changing this to be a mutable reference: `&mut self`
...
29 |         self.next = alloc_start + layout.size();
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be written

（self.allocations += 1行也会报告相同的错误，在此省略。）

发生错误是因为GlobalAlloctrait的alloc和dealloc方法仅使用不可变的&self引用执行，因此无法修改next和allocations字段。这是不行的，因为在分配后更新next是线性分配器的基本原理。

注意，在方法声明中将&self更改为&mut self的编译器建议在这里并不会起作用。因为该方法签名是由GlobalAlloctrait定义的，不能在实现时进行更改。（我在Rust代码库中开了一个关于无效建议的issue。）

GlobalAlloc与可变性

在研究这个可变性问题可能的解决方案之前，让我们尝试理解GlobalAlloctrait中的方法为什么使用&self定义参数的原因：正如我们在上一篇文章中看到的那样，全局堆分配器是通过将#[global_allocator]属性添加到一个实现GlobalAlloctrait的static变量来定义的。静态变量在Rust中是不可变的，所以不能使用静态分配器的&mut self引用来调用方法。因此，GlobalAlloc的所有方法仅采用不可变的&self引用。

幸运的是，有一种方法可以从&self引用中获取&mut self引用：我们可以通过将分配器封装在spin::Mutex自旋锁中来使用同步的内部可变性。该类型提供互斥方法lock，从而安全地将&self引用转换为&mut self引用。我们已经在内核中多次使用了该封装类型，比如用在VGA文本缓冲区中。

Locked封装类型

借助spin::Mutex封装类型，我们可以为线性分配器实现GlobalAlloc特性。这里的技巧是不是直接为BumpAllocator实现trait，而是为封装的spin::Mutex <BumpAllocator>类型实现trait：

unsafe impl GlobalAlloc for spin::Mutex<BumpAllocator> {…}

很不幸这仍然不起作用，因为Rust编译器不允许为其他crate中定义的类型的实现trait：

error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
  --> src/allocator/bump.rs:28:1
   |
28 | unsafe impl GlobalAlloc for spin::Mutex<BumpAllocator> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^--------------------------
   | |                           |
   | |                           `spin::mutex::Mutex` is not defined in the current crate
   | impl doesn't use only types from inside the current crate
   |
   = note: define and implement a trait or new type instead

要解决此问题，我们需要再次封装spin::Mutex以创建自己的封装类型：

in src/allocator.rs

/// 封装spin::Mutex，以允许为其实现trait
pub struct Locked<A> {
    inner: spin::Mutex<A>,
}

impl<A> Locked<A> {
    pub const fn new(inner: A) -> Self {
        Locked {
            inner: spin::Mutex::new(inner),
        }
    }

    pub fn lock(&self) -> spin::MutexGuard<A> {
        self.inner.lock()
    }
}

该类型是对spin::Mutex<A>的泛型封装。它对封装的类型A没有任何限制，因此可以用于封装所有类型，而不仅仅是分配器。它提供了一个简单的构造函数new，用于封装给定值。为了方便调用，它还提供了lock函数，该函数可调用被封装的Mutex上的lock函数。由于Locked类型非常通用，也可用在其他分配器实现中，因此我们将它放在父级模块allocator中。

实现Locked<BumpAllocator>

Locked类型是在我们自己的crate中定义的（与spin::Mutex不同），因此可以用来为线性分配器实现GlobalAlloc。完整实现如下：

in src/allocator/bump.rs

use super::{align_up, Locked};
use alloc::alloc::{GlobalAlloc, Layout};
use core::ptr;

unsafe impl GlobalAlloc for Locked<BumpAllocator> {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        let mut bump = self.lock(); // 获取可变引用

        let alloc_start = align_up(bump.next, layout.align());
        let alloc_end = match alloc_start.checked_add(layout.size()) {
            Some(end) => end,
            None => return ptr::null_mut(),
        };

        if alloc_end > bump.heap_end {
            ptr::null_mut() // 内存不足
        } else {
            bump.next = alloc_end;
            bump.allocations += 1;
            alloc_start as *mut u8
        }
    }

    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
        let mut bump = self.lock(); // 获取可变引用

        bump.allocations -= 1;
        if bump.allocations == 0 {
            bump.next = bump.heap_start;
        }
    }
}

alloc和dealloc的第一步是通过inner字段调用Mutex::lock方法，以获取被封装分配器类型的可变引用。该实例将保持锁定状态，直到方法结束，即使在多线程环境中也不会发生数据竞争（我们将很快添加线程支持）。

与前面的原型实现相比，alloc现在的实现遵守对齐要求并执行边界检查，以确保分配器分配的内存块仍在堆内存区域范围内。第一步是将next地址向上界对齐到Layout参数上。我们稍后再展示align_up函数的代码。然后将请求的分配大小加上alloc_start以获得这次分配的结束地址。为了防止在执行大尺寸分配时整型溢出，我们使用checked_add方法进行检查。如果发生溢出或分配结果的结束地址大于堆的结束地址，我们将返回空指针以表示内存不足的情况。否则，我们将更新next地址，并像以前一样将allocations计数器加1。最后返回转换为*mut u8指针的alloc_start地址。

dealloc函数将忽略给定的指针和Layout参数。它仅用于为allocations计数器减1。如果计数器再次归0，则意味着所有分配都已被释放。在这种情况下，它将next地址重置为heap_start地址，以使完整的堆内存再次可用。

地址对齐

align_up函数非常通用，可以将其放入父级模块allocator中。其实现如下：

in src/allocator.rs

/// 将给定的`addr`向上对齐到`align`
fn align_up(addr: usize, align: usize) -> usize {
    let remainder = addr % align;
    if remainder == 0 {
        addr // `addr`已对齐
    } else {
        addr - remainder + align
    }
}

函数首先结算addr除以align的余数。如果余数为0，则地址已经与给定的参数对齐。否则，我们通过减去余数（这样新的余数为0）然后加上对齐参数（保证新地址不会变得小于原地址）来对齐地址。

请注意，这并不是实现此函数最高效的实现。更快的实现如下所示：

/// 将给定的`addr`向上对齐到`align`
///
/// 要求`align`是2的幂
fn align_up(addr: usize, align: usize) -> usize {
    (addr + align - 1) & !(align - 1)
}

该函数利用GlobalAlloctrait确保align始终是2的幂。这样就可以非常高效的通过创建位掩码的方式来执行地址对齐。让我们从右往左一步一步理解其工作原理：

• 由于align是2的幂，因此它的二进制表示只会有一位被置为1（例如0b000100000）。这意味着align-1操作会将所有低位置为1（例如0b00011111）。
• 通过!执行按位NOT运算，我们得到一个除低于align的位外（例如0b…111111111100000）其余位均置为1的数字。
• 通过对地址和!(align-1)进行按位AND，地址将向下对齐，即清除所有低于align的位。
• 由于需要的是要向上对齐而不是向下对齐，因此在执行按位与运算之前，需要给addr增加align-1。如此，已对齐的地址将保持不变，而未对齐的地址将在下一个对齐边界处取整。

你可以选择任意一种实现方式，它们的计算结果是相同的。

使用线性分配器

要使用线性分配器而不是linked_list_allocatorcrate，我们需要修改allocator.rs中的静态变量ALLOCATOR：

in src/allocator.rs

use bump::BumpAllocator;

#[global_allocator]
static ALLOCATOR: Locked<BumpAllocator> = Locked::new(BumpAllocator::new());

注意，这里的BumpAllocator::new和Locked::new均已声明为const函数。如果它们是普通函数，则会发生编译错误，因为static变量的初始化表达式必须在编译期求值。

我们不需要在init_heap函数中修改ALLOCATOR.lock().init(HEAP_START, HEAP_SIZE)调用，因为线性分配器提供的接口与linked_list_allocator相同。

现在内核使用了线性分配器！原来的代码应该仍然有效，包括我们在上一篇文章中创建的heap_allocation测试：

> cargo test --test heap_allocation
[…]
Running 3 tests
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]

关于线性分配器的讨论

线性分配的最大优点是效率极高。与需要主动寻找合适的内存块并在alloc和dealloc上执行各种跟踪记录任务的其他分配器设计（参见下文）相比，线性分配器甚至可以被优化为一组汇编指令。因此，在分配器性能优化任务中，线性分配器就十分有用，例如在创建虚拟DOM库时。

不过线性分配器很少被当做全局分配器使用，它通常出现在“分配竞技场”中，即将多个独立的分配器组合在一起以提高性能。Rust中的竞技场分配器的一个实现是toolshed。

线性分配器的缺点

线性分配器的主要局限性在于，它只有在释放了所有分配后才能重新使用释放的内存再次进行分配。这意味着一个长期独占的分配就足以拖延内存的重用。我们只需对many_boxes测试稍加修改就可以演示这个现象：

in tests/heap_allocation.rs

#[test_case]
fn many_boxes_long_lived() {
    let long_lived = Box::new(1); // new
    for i in 0..HEAP_SIZE {
        let x = Box::new(i);
        assert_eq!(*x, i);
    }
    assert_eq!(*long_lived, 1); // new
}

像many_boxes一样，此测试也会创建大量分配，如果分配器不重新使用释放的内存，将引发内存不足的错误。此外，测试会创建一个long_lived分配，该分配在整个循环执行期间均有效。

当我们尝试运行新测试时将发行测试确实失败了：

> cargo test --test heap_allocation
Running 4 tests
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]
many_boxes_long_lived... [failed]

Error: panicked at 'allocation error: Layout { size_: 8, align_: 8 }', src/lib.rs:86:5

详细讨论一下测试为什么会失败：首先，在堆的开头创建long_lived分配，从而将allocations计数器加1。在每次循环中，都会创建一个短暂的分配并在下一次迭代开始之前就被释放。这意味着allocations计数器在迭代开始时临时增加到2，在迭代结束时减少为1。现在的问题是，线性分配器仅在所有分配释放后才可以重用内存，即allocations计数器减至0。不过这在整个循环完全结束之前都不会发生，因此每次循环迭代都将会分配出去一个新的内存块，从而使得内存在多次迭代后耗尽。

修复这个测试？

有两个的技巧可以用来修复这个线性分配器的测试：

• 我们可以修改dealloc，通过比较被释放内存的结束地址与next指针是否一致，来判断本次内存释放是否为刚刚才分配出去的内存。如果二者相等，我们可以安全地将next重置为刚刚被释放的分配的起始地址。如此，每次循环都将会重复同一个内存块。
• 我们也可以添加一个alloc_back方法，该方法使用额外的next_back字段从堆尾开始分配内存。然后，我们就可以为所有长期分配手动调用方法，从而在堆上将短期分配和长期分配分隔开。请注意，只有事先清楚每个分配的有效期限，才能使用这种分隔。该方法的另一个缺点是需要手动执行分配，麻烦且存在安全风险。

虽然这两种方法都可以修复测试，但它们并不是通用的解决方案，因为它们都只能在非常特殊的情况下重用内存。问题是：是否有一个通用的解决方案可以重用所有已释放的内存？

重用所有被释放的内存

正如我们在上一篇文章中了解到的那样，分配可能具有任意的生命周期，并且可以按照任意顺序释放。这意味着我们需要跟踪数量未知且非连续的未使用内存区域，如以下示例所示：

上图显示了堆的分配状态随时间的变化。一开始，整个堆都是未使用的，此时next地址等于heap_start（第1行）。然后出现了第一次分配（第2行）。在第3行中，第二个存储块被分配出去，同时第一个分配被释放了。在第4行中新增了更多分配。其中一半有效期很短，它们在第5行中已被释放，而且在这一行中还新增了另一个分配。

第5行显示了一个基本问题：我们共有五个未使用的内存区域，它们的大小各不相同，但是next指针只能指向最后一个区域的开始。尽管对于本示例，我们可以将其他未使用的存储区域的起始地址和大小存储在大小为4的数组中，但这并不是一个通用的解决方案，因为我们同样可以轻松地创建一个包含8个、16个或1000个未使用的存储区域的例子。

通常，当我们需要处理数量未知的项目时，会倾向于使用在堆上进行分配的集合类型。但在现在并不可行，因为堆分配器不能依赖于自身（这将导致无限递归或死锁）。因此，我们需要找到其他解决方案。

链表分配器

在实现分配器时，跟踪任意数量的空闲内存区域的常见技巧，就是将这些区域本身用作后备存储。这利用了一个事实：这些已释放的内存区域仍被映射到虚拟地址上，其背后都有一个对应的物理帧，但是我们已经不再需要其上存储的信息了。通过使用区域本身存储该区域相关的内存释放信息，我们就可以跟踪任意数量的释放区域，而无需额外的内存。

最常见的实现方法是在释放的内存中构造一个链表，每个节点都是一个已释放的内存区域：

每个列表节点包含两个字段：此内存区域的大小和指向下一个未使用的内存区域的指针。使用这种方法，我们只需要那个指向第一个未使用区域的指针（称为head）即可跟踪所有未使用区域，而与它们的数量无关。产生的数据结构通常称为空闲列表。

你可能已经从名称中猜到，这正是linked_list_allocatorcrate使用的技术。使用此技术的分配器通常也被称为池分配器。

实现链表分配器

接下来，我们将使用上述跟踪已释放的内存区域的方法，自己实现一个简单的LinkedListAllocator类型。以后的文章并不需要这一部分的内容，因此你可以根据需要选择跳过实现细节。

分配器类型

我们首先在新的allocator::linked_list子模块中创建一个私有ListNode结构：

in src/allocator.rs

pub mod linked_list;

in src/allocator/linked_list.rs

struct ListNode {
    size: usize,
    next: Option<&'static mut ListNode>,
}

就像在上图中描述的那样，列表节点具有一个size字段和一个指向下一个节点的可选指针，由Option<&'static mut ListNode>类型表示。静态mut类型在语义上描述了指针拥有其后指向的对象。这就基本上就是一个Box类型，只不过它没有能够在作用域末尾释放持有对象的析构函数。

我们为ListNode实现下列方法：

in src/allocator/linked_list.rs

impl ListNode {
    const fn new(size: usize) -> Self {
        ListNode { size, next: None }
    }

    fn start_addr(&self) -> usize {
        self as *const Self as usize
    }

    fn end_addr(&self) -> usize {
        self.start_addr() + self.size
    }
}

该类型具有一个简单的构造函数new，以及用于计算所表示内存区域的开始地址和结束地址的方法。我们将新函数设为const函数，因为稍后会在构造静态链表分配器时使用到它。请注意，在const函数中使用可变引用（包括将next字段设置为None）仍然不稳定。为了能够编译，我们需要在lib.rs的开头添加#![feature(const_mut_refs)]。

我们现在可以使用ListNode结构作为积木，来创建LinkedListAllocator结构体：

in src/allocator/linked_list.rs

pub struct LinkedListAllocator {
    head: ListNode,
}

impl LinkedListAllocator {
    /// 创建一个空的`LinkedListAllocator`.
    pub const fn new() -> Self {
        Self {
            head: ListNode::new(0),
        }
    }

    /// 使用给定的堆边界初始化分配器
    /// 
    /// 该方法为非安全，因为调用者必须保证提供的内存范围未被使用。
    /// 同时，该方法只能被调用一次。
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        self.add_free_region(heap_start, heap_size);
    }

    /// 将给定的内存区域添加至链表前端
    unsafe fn add_free_region(&mut self, addr: usize, size: usize) {
        todo!();
    }
}

结构体包含一个head节点，指向第一个堆区域。我们只对next指针的值感兴趣，因此在ListNode::new函数中将大小设为0。将head设置为ListNode而不是仅使用&'static mut ListNode的优点是相应的alloc方法的实现将会更加简单。

就像线性分配器一样，new函数并不会直接使用堆边界来初始化分配器。除了希望保持API兼容性之外，原因还在于初始化过程需要将一个节点写入堆内存，这只能在运行时发生。然而，new函数必须是可以在编译时求值的const函数，因为它将用于初始化静态变量ALLOCATOR。出于这个原因，我们仍然使用一个独立的非-常函数init。

init方法使用add_free_region方法，稍后将展示其实现。现在，我们使用todo!宏提供一个总是panic的实现占位符。

add_free_region方法

add_free_region方法为链表提供了基本的push操作。目前，我们仅在init中调用此方法，但它也将成为我们dealloc实现中的核心方法。请记住，当释放分配的内存区域时，将调用dealloc方法。为了跟踪此次释放产生的的未使用内存区域，我们希望将其push到链表中。

add_free_region方法的实现如下：

in src/allocator/linked_list.rs

use super::align_up;
use core::mem;

impl LinkedListAllocator {
    /// 将给定的内存区域添加至链表前端
    unsafe fn add_free_region(&mut self, addr: usize, size: usize) {
        // 确保此空闲区域足以容纳一个`ListNode`
        assert_eq!(align_up(addr, mem::align_of::<ListNode>()), addr);
        assert!(size >= mem::size_of::<ListNode>());

        // 创建一个新的`ListNode`并将其添加至链表前端
        let mut node = ListNode::new(size);
        node.next = self.head.next.take();
        let node_ptr = addr as *mut ListNode;
        node_ptr.write(node);
        self.head.next = Some(&mut *node_ptr)
    }
}

该方法获取一个内存区域的地址和大小作为参数，将该区域添加到列表前端。首先要保证给定的内存区域具有存储ListNode所需的大小和对齐方式。然后再按照下图中的步骤创建节点并将其插入到列表中：

步骤0显示了调用add_free_region前堆的状态。在步骤1中，使用图中标记为freed的内存区域作为参数调用该方法。初步检查后，该方法使用空闲区域大小作为参数，在其调用栈上创建了一个新node。然后，它使用Option::take方法将新node的next指针设置为当前的头指针，并将头指针重置为None。

在步骤2中，该方法使用write方法将新创建的node（译注：目前仍在调用栈中）写入空闲内存区域的开头。最后将head指针指向这个新节点。图中最后呈现出来的指针结构略显混乱，这是因为释放区域总是在列表的开头插入，不过如果我们跟随指针，就会从head指针开始依次到达每个空闲区域了。

find_region函数

链表的另一个基本操作是查找条目并将其从列表中移除。这是实现alloc方法所需的核心操作。我们通过以下方式将该操作实现为find_region方法：

in src/allocator/linked_list.rs

impl LinkedListAllocator {
    /// 按照给定大小和对齐方式查找一个空闲内存区域
    /// 并将其从链表中删除
    ///
    /// 返回一个包含`ListNode`和其开始地址的分配
    fn find_region(&mut self, size: usize, align: usize)
        -> Option<(&'static mut ListNode, usize)>
    {
        // 当前链表节点的引用，会在每次迭代中更新
        let mut current = &mut self.head;
        // 在链表中查找一个足够大的内存区域
        while let Some(ref mut region) = current.next {
            if let Ok(alloc_start) = Self::alloc_from_region(&region, size, align) {
                // 该区域可以容纳所需的分配，则将该区域从链表中删除
                let next = region.next.take();
                let ret = Some((current.next.take().unwrap(), alloc_start));
                current.next = next;
                return ret;
            } else {
                // 该区域不可以容纳所需的分配，则继续下一轮迭代查找
                current = current.next.as_mut().unwrap();
            }
        }

        // 已经找不到合适的内存区域了
        None
    }
}

该方法使用一个current变量和一个while let循环来遍历列表元素。首先，将current设置到（假的）head节点。然后，在每次迭代中，它都会更新为当前节点的next字段（在else块中）。如果该区域适合于具有给定大小和对齐方式的分配，则将该区域从链表中删除，并与alloc_start地址一起返回。

当current.next指针变为None时，循环退出。这意味着我们遍历了整个链表，却没并有找到适合于给定分配的区域。在这种情况下，我们将返回None。检查区域是否合适由alloc_from_region函数完成，我们将在稍后展示其实现。

先让我们更加详细地研究如何从列表中删除合适的区域：

步骤0显示了链表指针调整之前的状态。region区域、current区域、region.next指针和current.next指针均已在图中标出。在步骤1中，使用Option::take方法将region.next和current.next指针都重置为None。原来的指针分别存储在局部变量next和ret中。

在步骤2中，将局部变量next指针赋给current.next指针，也就是原来的region.next指针。结果是current现在直接指向region之后的下一个区域，因此region就不再是链表中的元素了。最后将存储在局部变量ret中的指针返回。

alloc_from_region函数

alloc_from_region函数返回给定内存区域是否适合于具有给定大小和对齐方式的分配。其实现如下：

in src/allocator/linked_list.rs

impl LinkedListAllocator {
    /// 尝试使用给定内存区域，为给定大小和对齐方式的分配做出分配
    ///
    /// 如果成功则返回分配的开始地址。
    fn alloc_from_region(region: &ListNode, size: usize, align: usize)
        -> Result<usize, ()>
    {
        let alloc_start = align_up(region.start_addr(), align);
        let alloc_end = alloc_start.checked_add(size).ok_or(())?;

        if alloc_end > region.end_addr() {
            // 内存区域太小
            return Err(());
        }

        let excess_size = region.end_addr() - alloc_end;
        if excess_size > 0 && excess_size < mem::size_of::<ListNode>() {
            // 该内存区域的剩余部分太小，无法容纳一个`ListNode`
            // （这是必须的，因为分配动作会将该区域分为已使用和未使用两个部分）
            return Err(());
        }

        // 该区域适合于给定的分配
        Ok(alloc_start)
    }
}

首先，该函数使用我们之前定义的align_up函数和checked_add方法来计算给定分配的起始地址和结束地址。若发生溢出，或结束地址在给定区域的结束地址之后，则给定区域过小，不适合给定分配，所以我们返回错误。

接下来，函数执行的检查可能不太直观。不过这个检查是必要的，因为在大多数情况下，给定区域不可能正好就适合给定分配，因此分配过后，该区域的一部分仍为未使用区域。而此次分配之后，该区域的这一空闲部分必须足够大，以存储其自己的ListNode。该检查将准确地验证：分配是否完全合适（excess_size == 0）或多余的大小是否足以存储一个ListNode。

为链表分配器实现GlobalAlloc

使用add_free_region和find_region方法提供的基本操作，就可以实现GlobalAlloctrait了。与线性分配器一样，我们不直接为LinkedListAllocator实现trait，而是为封装类型Locked<LinkedListAllocator>实现trait。Locked封装类型使用自旋锁增加了内部可变性，这使我们可以修改分配器实例，尽管alloc和dealloc方法只使用了不可变引用&self。

实现看起来像这样：

in src/allocator/linked_list.rs

use super::Locked;
use alloc::alloc::{GlobalAlloc, Layout};
use core::ptr;

unsafe impl GlobalAlloc for Locked<LinkedListAllocator> {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // 调整对齐布局
        let (size, align) = LinkedListAllocator::size_align(layout);
        let mut allocator = self.lock();

        if let Some((region, alloc_start)) = allocator.find_region(size, align) {
            let alloc_end = alloc_start.checked_add(size).expect("overflow");
            let excess_size = region.end_addr() - alloc_end;
            if excess_size > 0 {
                allocator.add_free_region(alloc_end, excess_size);
            }
            alloc_start as *mut u8
        } else {
            ptr::null_mut()
        }
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        // 调整对齐布局
        let (size, _) = LinkedListAllocator::size_align(layout);

        self.lock().add_free_region(ptr as usize, size)
    }
}

我们西安从更简单的dealloc方法看起：首先执行一些布局调整，我们将在稍后进行解释，并通过在Locked封装上调用Mutex::lock函数来获取分配器的可变引用&mut LinkedListAllocator。然后调用add_free_region函数将释放的区域添加到空闲链表中。

alloc方法有点复杂。类似的，先进行布局调整，再调用Mutex::lock函数以获取分配器的可变引用。然后使用find_region找到适合这次分配的内存区域，并将其从空闲链表中删除。如果没找到返回None时，方法会因为没有合适的内存区域而返回null_mut，以表示分配错误。

在分配成功的情况下，find_region方法将返回包含合适区域（已从空闲链表中移除）和分配起始地址的元组。使用alloc_start、给定的分配大小、区域的结束地址，方法将重新计算分配的结束地址以及该区域的剩余大小。如果确实有剩余大小，方法将调用add_free_region将区域的剩余部分重新添加回空闲列表。最后将alloc_start地址转换为*mut u8类型并返回。

布局调整

那么，我们在alloc和dealloc开头都进行了哪些布局调整？其实就是为了确保每个分配的块都能够存储ListNode。这一点很重要，因为在某个时刻，该内存块将要被释放时，我们需要向其写入一个ListNode记录。如果该内存块小于ListNode或并没有正确的对齐，就会引发未定义行为。

布局调整由size_align函数执行，该函数实现如下：

in src/allocator/linked_list.rs

impl LinkedListAllocator {
    /// 调整给定布局，使生成的用以分配的内存区域也能够存储`ListNode`。
    ///
    /// 以元组`(size, align)`的形式返回调整后的大小和对齐方式。
    fn size_align(layout: Layout) -> (usize, usize) {
        let layout = layout
            .align_to(mem::align_of::<ListNode>())
            .expect("adjusting alignment failed")
            .pad_to_align();
        let size = layout.size().max(mem::size_of::<ListNode>());
        (size, layout.align())
    }
}

首先，函数在传入的Layout上调用align_to方法，以在必要时为ListNode增加空间以对齐。然后使用pad_to_align方法将布局大小向上对齐，以确保下一个内存块的起始地址也将具有正确的对齐方式，从而能再储一个ListNode。接下来，函数使用max方法强制所分配的大小至少要为mem::size_of::<ListNode>。如此，dealloc函数就可以安全地将ListNode写入已释放的内存块中了。

使用链表分配器

现在，我们只需要在allocator模块中更新静态变量ALLOCATOR，就可以使用新的LinkedListAllocator了：

in src/allocator.rs

use linked_list::LinkedListAllocator;

#[global_allocator]
static ALLOCATOR: Locked<LinkedListAllocator> =
    Locked::new(LinkedListAllocator::new());

由于线性分配器和链接列表分配器的init函数行为一致，因此我们无需修改init_heap中的init调用。

现在，当我们再次运行heap_allocation测试时，可以看到所有测试都通过了，其中包括在线性分配器中失败的many_boxes_long_lived测试：

> cargo test --test heap_allocation
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]
many_boxes_long_lived... [ok]

这说明了我们的链表分配器能够将释放的内存重新用于后续分配。

关于链表分配器的讨论

与线性分配器相比，链表分配器更适合作为通用分配器使用，主要是因为它能够立刻重用释放的内存。当然，链表分配器也有一些缺点。其中一部分是由于我们的实现过于简单引起的，另一些则是由于链表分配器的设计本身存在的固有缺陷。

合并空闲块

我们实现的主要问题是，它只会将堆拆分为越来越小的块，而不会再将小块合并成大块。考虑下面的例子：

在第一行中，堆上创建了三个分配。它们中的两个在第2行中被释放，而第三个在第3行中被释放。现在虽然整个堆处于空闲状态，但仍旧被分成四个单独的块。此时，可能会由于四个块中的任何一个都不足够大，导致内核不能再进行大型分配了。随着时间的流逝，该过程将持续进行，并将堆分成越来越小的块。最后可能出现的情况就是，堆中的块过于分散过于小，使得哪怕正常大小的分配都无法进行了。

要解决此问题，我们需要将相邻的释放块重新合并在一起。对于上面的示例，这意味着：

跟第一张图一样，第2行同样释放了三个分配中的两个。与第一张图不同的是，这次不在留着堆碎片不管，我们现在添加一个额外的2a行合并操作，将两个最右边的块重新合并在一起。在第3行中，第三个分配被释放（跟第一张图一样），从而产生由三个独立的块组成的一整个空闲的堆。同样的，我们再添加额外的3a行合并操作，将三个相邻的块重新合并成一整块未使用的堆。

linked_list_allocatorcrate使用以下方式实现此合并策略：与我们的实现不同，该实现并不向列表前端插入deallocate释放的内存块，而是始终将列表按开始地址排序。这样，可以通过检查列表中两个相邻块的地址和大小，直接在deallocate调用时执行合并。当然，这种方式的释放速度稍慢，但是可以防止在我们的实现中出现的堆碎片。

性能

正如我们在前文了解到的，线性分配器非常快，可以被优化为一组汇编操作。链表分配器作为分配器，性能则要差很多。问题在于，分配请求可能需要遍历完整的链表才能找到合适的块。

由于链表长度取决于未使用的存储块的数量，因此对于不同的程序，其性能可能会发生极大的变化。对于仅创建几个分配的程序，其分配性能较好。但是，对于一个用很多分配将堆碎片化的程序，其分配性能将非常差，因为链表将变得很长，且可能包含非常多非常小的块。

值得注意的是，这个性能问题并不是因为我们的实现过于简单而引起的，这是链表分配器设计的固有缺陷。由于分配器的性能对于内核级代码极其重要，因此，我们将在下文中探讨第三种分配器设计，该设计以降低内存利用率为代价来提高的性能。

固定大小的块分配器

接下来，我们将介绍一种使用固定大小的内存块来进行分配的分配器。这种分配器通常会返回大于分配所需的内存块，产生内部碎片从而导致一定的内存浪费。不过，它也大大降低了找到合适块所需的时间（与链表分配器相比），从而大幅提升分配性能。

简介

固定大小的块分配器的思路是：我们不再分配跟请求大小完全一致的块，而是定义少量种类的块，并为每一次分配选择一个大小向上取整的块。例如，我们可以定义16、64和512字节的块，分配需要4字节时就返回一个16字节的块，分配需要48字节时就返回一个64字节的块，而分配需要128字节时就返回一个512字节的块。

像链表分配器一样，我们通过在未使用的内存中创建链表来跟踪未使用的内存。不同的是，这次不是像链表分配器那样用一个链表来跟踪不同大小的块，而是为不同大小的块分别设置各自的跟踪链表。于是，每个链表仅存储同一种大小的块。例如，在定义了16、64和512字节块的情况下，内存中将存在三个单独的链表：

原先的链表分配器仅有一个head指针，现在有head_16、head_64和head_512三个了，它们分别指向各自对应大小的第一个未使用的块。而每个链表中的所有节点都具有相同的大小。例如，由head_16指针开始的链表仅包含16字节的块。这意味着我们不再需要在每个列表节点中存储块的大小，因为它已经由头指针的名称决定了。

由于链表中的每个节点都具有相同的大小，因此对一个分配请求来说，用链表中的哪个节点都是一样的。这意味着我们可以使用下列步骤非常有效地执行分配：

• 将请求的分配大小向上取整到最接近的块大小。比如在请求分配12个字节时，按照上例，我们将选择分配一个大小为16的块。
• （例如从数组中）取出链表的头指针。对于大小为16的块，我们需要用到head_16。
• 从链表中移除并返回第一个块。

值得注意的是，此处仅需要返回链表的第一个元素，而不再需要遍历整个链表。因此，这种分配器会比链表分配器快得多。

块大小与内存浪费

我们在取整时将浪费的多少内存，取决于块大小的设置。例如，当返回一个分配请求128字节而我们返回一个512字节的块时，分配出去的内存中有四分之三被浪费了。通过定义合理的块大小，可以在一定程度上限制浪费的内存。例如，当使用2的幂（4、8、16、32、64、128等）作为块大小时，在最坏的情况下也只会浪费一半的内存，平均而言仅浪费四分之一的内存。

基于程序中的公共分配尺寸来优化块大小也是很常见的。例如，我们可以额外增加大小为24的块，以提高经常执行24字节分配的程序的内存使用率。这样通常可以减少浪费的内存量，而且不会造成性能损失。

释放

像分配一样，释放也非常高效。它涉及以下步骤：

• 将释放的分配大小向上取整到最接近的块大小。这是必需的，因为编译器传递给dealloc的并不是alloc返回的块的大小，而只是所请求的分配大小。通过在alloc和dealloc中使用相同的向上取整函数，就可以确保释放的内存量始终正确。
• （例如从数组中）取出链表的头指针。
• 更新头指针，将释放的块添加到链表的前端。

值得注意的是，释放过程也不需要遍历链表。这意味着无论链表有多长，dealloc调用所需的时间都是一个常量。

后备分配器

鉴于大容量分配（大于2KB）通常是很少见的，尤其是在操作系统内核中，因此对于这些分配，使用不同的分配器可能也是合理的。例如，为了减少内存浪费，我们可以转而使用链表分配器，以进行大于2048字节的分配。因为这种尺寸的分配应该非常少，所以链表也将保持较小的状态，而分配/释放也仍将保持相当快的速度。

创建新块

前面我们始终假设特定大小的链表中始终有足够多的块来满足所有分配请求。但是，有时候某种大小的块的链表中没有多余的块了。此时，有两种方法可以创建特定大小的空闲新块来满足分配请求：

• 从后备分配器中分配一个新块（如果有后备分配器的话）。
• 从其他链表中拆分更大的块。如果块大小设置为2的幂，那么此方法将最有效。例如，一个32字节的块可以分为两个16字节的块。

在我们的实现中，将选择从后备分配器中分配新的块，因为这种实现要简单得多。

实现固定大小的块分配器

现在我们知道了固定大小的块分配器是如何工作的，就可以着手实现它了。我们将不会依赖上一节中创建的链表分配器的实现，因此即使你跳过了链表分配器的实现，也可以正常阅读这一部分。

链表节点

我们通过在新的allocator::fixed_size_block模块中创建ListNode类型来开始实现：

in src/allocator.rs

pub mod fixed_size_block;

in src/allocator/fixed_size_block.rs

struct ListNode {
    next: Option<&'static mut ListNode>,
}

该类型很像我们在链表分配器中实现的ListNode类型，不同之处在于这里没有了第二个字段size。不需要size字段，是因为在固定大小的块分配器的设计思路中，同一个链表中的每个块大小都相同。

块大小

接下来，我们定义一个常量切片BLOCK_SIZES，包含了实现中将会用到的块大小：

in src/allocator/fixed_size_block.rs

/// 将会用到的块大小
///
/// 块大小必须是2的幂，因为它们也将用于块对齐
///（对齐方式必须为2的幂）
const BLOCK_SIZES: &[usize] = &[8, 16, 32, 64, 128, 256, 512, 1024, 2048];

我们使用从8到2048的2的幂作为块大小。我们不定义任何小于8的块，因为每个块在被释放时必须能够存储指向下一个块的64位指针。对于大于2048字节的分配，我们将使用链表分配器。

为了简化实现，我们定义：一个块的大小也是其在内存中所需的对齐方式。因此，一个16字节的块始终在16字节的边界上对齐，而512字节的块始终在512字节的边界上对齐。由于对齐始终需要是2的幂，因此也排除了任何其他块大小。如果将来需要的块大小不是2的幂，我们仍然可以为此调整执行方式（例如，再定义一个BLOCK_ALIGNMENTS数组）。

分配器类型

使用ListNode类型和BLOCK_SIZES切片，我们现在可以定义分配器类型：

in src/allocator/fixed_size_block.rs

pub struct FixedSizeBlockAllocator {
    list_heads: [Option<&'static mut ListNode>; BLOCK_SIZES.len()],
    fallback_allocator: linked_list_allocator::Heap,
}

list_heads字段是head指针的数组，每个块大小对应一个头指针。使用BLOCK_SIZES切片的len()作为数组长度创建数组。对于那些大于最大块尺寸的分配，我们使用linked_list_allocator提供的分配器作为后备分配器。当然，也可以改用我们自己实现的LinkedListAllocator，但是它并不会自动合并空闲块。

为了构造一个FixedSizeBlockAllocator，我们依旧提供与其他类型分配器相同的new函数和init函数：

in src/allocator/fixed_size_block.rs

impl FixedSizeBlockAllocator {
    /// 创建一个空的`FixedSizeBlockAllocator`.
    pub const fn new() -> Self {
        const EMPTY: Option<&'static mut ListNode> = None;
        FixedSizeBlockAllocator {
            list_heads: [EMPTY; BLOCK_SIZES.len()],
            fallback_allocator: linked_list_allocator::Heap::empty(),
        }
    }

    /// 使用给定的堆边界初始化线性分配器
    /// 
    /// 该方法为非安全，因为调用者必须保证提供的内存范围未被使用。
    /// 同时，该方法只能被调用一次。
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        self.fallback_allocator.init(heap_start, heap_size);
    }
}

新函数只是使用空节点初始化list_heads数组，并创建一个空链表分配器作为fallback_allocator。EMPTY必须为常量的原因是要告诉Rust编译器我们要使用常量值初始化数组。直接将数组初始化为[None; BLOCK_SIZES.len()]会有编译错误，因为之后编译器会要求Option<&'static mut ListNode>需要实现Copytrait，对于这点我们无能为力。这是目前的Rust编译器所具有的局限性，在未来的编译器中可能会解决这个问题。

如果你跳过了LinkedListAllocator的实现一节，则还需要在lib.rs的开头添加#![feature(const_mut_refs)]。原因是在const函数中使用可变引用类型仍然不稳定，包括list_heads字段的数组元素Option<&'static mut ListNode>类型（即使我们将其设置为None）也是如此。

非安全的init函数仅用于调用fallback_allocator的init函数，而无需对list_heads数组进行任何其他初始化。此后我们将在alloc和dealloc调用上延迟初始化该列表。

为了方便起见，我们还创建了一个私有的fallback_alloc方法，该方法使用fallback_allocator执行分配：

in src/allocator/fixed_size_block.rs

use alloc::alloc::Layout;
use core::ptr;

impl FixedSizeBlockAllocator {
    /// 使用后备分配器执行分配.
    fn fallback_alloc(&mut self, layout: Layout) -> *mut u8 {
        match self.fallback_allocator.allocate_first_fit(layout) {
            Ok(ptr) => ptr.as_ptr(),
            Err(_) => ptr::null_mut(),
        }
    }
}

由于linked_list_allocatorcrate的Heap类型无法实现GlobalAlloc（因为不使用锁就不可能实现）。而是提供了一个略有不同的接口的allocate_first_fit方法。它不返回*mut u8也不使用空指针来指示分配错误，而是返回Result<NonNull<u8>, ()>。 NonNull类型是是对那些能够保证自己是非空指针的裸指针的抽象。通过在匹配到Ok时返回NonNull::as_ptr方法，匹配到Err时返回null指针，我们可以方便地将其转换回*mut u8类型。

计算块大小列表索引

在实现GlobalAlloctrait之前，我们定义一个list_index帮助函数，用来返回适合给定Layout的最小块大小：

in src/allocator/fixed_size_block.rs

/// 为给定的`layout`选择一个合适的块大小
///
/// 返回该块大小在`BLOCK_SIZES`中的索引
fn list_index(layout: &Layout) -> Option<usize> {
    let required_block_size = layout.size().max(layout.align());
    BLOCK_SIZES.iter().position(|&s| s >= required_block_size)
}

块必须至少具有给定Layout所需的大小和对齐方式。由于我们定义了块的大小也是它的对齐方式，因此这意味着required_block_size应为布局的size()和align()属性中的较大值。为了在BLOCK_SIZES切片中查找最接近向上取整的块大小，我们首先使用iter()方法获取迭代器，然后使用position()方法在切片中查找第一个不小于required_block_size的块的索引并返回该索引。

请注意，这里并不返回块大小本身，而是返回BLOCK_SIZES切片的索引。原因是我们还要使用该索引作为list_heads数组的索引。

为固定大小的块分配器实现GlobalAlloc

最后一步是实现GlobalAlloctrait：

in src/allocator/fixed_size_block.rs

use super::Locked;
use alloc::alloc::GlobalAlloc;

unsafe impl GlobalAlloc for Locked<FixedSizeBlockAllocator> {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        todo!();
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        todo!();
    }
}

同其他分配器一样，我们仍不直接为分配器类型实现GlobalAlloctrait，而是使用Locked封装为其添加同步的内部可变性。由于alloc和dealloc的实现相对复杂，因此我们将在接下来的文章中逐一介绍它们。

alloc

alloc方法的实现如下所示：

in src/allocator/fixed_size_block.rs

unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
    let mut allocator = self.lock();
    match list_index(&layout) {
        Some(index) => {
            match allocator.list_heads[index].take() {
                Some(node) => {
                    allocator.list_heads[index] = node.next.take();
                    node as *mut ListNode as *mut u8
                }
                None => {
                    // 链表中没有多余的块了，于是创建并分配新块
                    let block_size = BLOCK_SIZES[index];
                    // 这只在所有块大小均为2的幂时有效
                    let block_align = block_size;
                    let layout = Layout::from_size_align(block_size, block_align)
                        .unwrap();
                    allocator.fallback_alloc(layout)
                }
            }
        }
        None => allocator.fallback_alloc(layout),
    }
}

我们来一步一步看：

首先调用Locked::lock方法获取对封装中的分配器实例的可变引用。然后调用刚刚定义的list_index函数来计算合适于给定布局的块大小，并尝试使用块大小索引从list_heads数组中取出对应链表的头指针。如果列表索引为None，则说明这次分配没有合适的块大小，于是使用fallback_alloc函数调用fallback_allocator进行分配。

如果列表索引为Some，就尝试使用Option::take方法取出（译注：获取并移除）list_heads[index]所在的链表的第一个节点node。如果该链表不为空，则进入match语句的Some(node)分支，将该链表的头指针指向node的后继节点（也是使用take）。最后，我们将取出的node以*mut u8指针的形式返回。

如果链表头指针为None，则表示该块大小对应的链表为空。这意味着我们需要按照上面描述的那样创建一个新块。为此，我们首先从BLOCK_SIZES切片中获取该块大小的具体值，并将其用作新块的大小和对齐方式，再从中创建一个新的Layout，并调用fallback_alloc方法执行分配。之所以需要调整布局和对齐方式，是因为该块将在释放时会被添加到相应的块链表中。

dealloc

dealloc方法的实现如下所示：

in src/allocator/fixed_size_block.rs

use core::{mem, ptr::NonNull};

// 在`unsafe impl GlobalAlloc`内

unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
    let mut allocator = self.lock();
    match list_index(&layout) {
        Some(index) => {
            let new_node = ListNode {
                next: allocator.list_heads[index].take(),
            };
            // 为存储的节点验证块大小和块对齐方式
            // verify that block has size and alignment required for storing node
            assert!(mem::size_of::<ListNode>() <= BLOCK_SIZES[index]);
            assert!(mem::align_of::<ListNode>() <= BLOCK_SIZES[index]);
            let new_node_ptr = ptr as *mut ListNode;
            new_node_ptr.write(new_node);
            allocator.list_heads[index] = Some(&mut *new_node_ptr);
        }
        None => {
            let ptr = NonNull::new(ptr).unwrap();
            allocator.fallback_allocator.deallocate(ptr, layout);
        }
    }
}

类似alloc中的操作，首先调用lock方法获取分配器的可变引用，然后使用list_index函数获取与给定Layout大小相适应的块链表。如果索引为None，则BLOCK_SIZES中并没有合适的块大小，这说明该分配是由后备分配器创建的。因此，这里也应调用后备分配器的deallocate来释放内存。该方法期望使用NonNull而不是*mut u8，因此我们需要做指针转换。（仅当指针为空时，调用unwrap才会失败，而在编译器调用dealloc时这不可能发生。）

如果list_index返回一个块大小的索引，则需要将已释放的内存块添加到相应块大小的链表中。为此，我们首先创建一个指向当前链表头的新ListNode（仍然使用Option::take）。在将新节点写入释放的内存块之前，我们首先断言由index指定的块大小具有存储ListNode所需的大小和对齐方式。然后，我们通过将参数给定的*mut u8指针转换为*mut ListNode指针，并在其上调用非安全的write方法来将new_node写入内存块。最后一步是将列表的头部指针指向新建的ListNode，该链表的目前的指针为None，因为我们在前面使用take取走了原指针而留下一个None。为此，我们将裸指针new_node_ptr转换为一个可变引用。

这里有几点值得注意：

• 我们不区分某个块究竟是从块链表分配的，还是从后备分配器中分配。这意味着将在alloc中创建的新块在dealloc时能够添加到相应的块链表中，从而增加该块大小链表中所包含的块数。
• 在我们的实现中，alloc方法是唯一能够创建新块的地方。这意味着我们初始化时仅有一系列空的块链表，且仅在执行针对特定块大小的分配时，才惰性填充相应的链表。
• 即使我们执行了一些unsafe操作，我们也不需要在alloc和dealloc中使用unsafe块。原因是Rust目前将整个非安全函数的函数体视为一个大的unsafe块。由于使用显式unsafe块的优点是很能够明显指出哪些操作是非安全的哪些操是安全的，因此已经有一个RFC提案讨论更改Rust当前的这种行为。

使用固定大小的块分配器

要使用新的FixedSizeBlockAllocator，我们需要在allocator模块中修改静态变量ALLOCATOR：

in src/allocator.rs

use fixed_size_block::FixedSizeBlockAllocator;

#[global_allocator]
static ALLOCATOR: Locked<FixedSizeBlockAllocator> = Locked::new(
    FixedSizeBlockAllocator::new());

由于init函数在我们实现的所有分配器中均具有相同的行为，因此无需修改init_heap中的init调用。

现在，当我们再次运行heap_allocation测试时，所有测试仍应通过：

> cargo test --test heap_allocation
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]
many_boxes_long_lived... [ok]

这个新分配器看起来也能够正常工作！

关于固定大小的块分配器的讨论

尽管固定大小的块分配器性能好于链表分配器，但是当使用2的幂作为块大小时，它可能会浪费了多达一半的内存。至于这种权衡是否值得，在很大程度上取决于应用程序类型。对于性能至关重要的操作系统内核而言，固定大小的块分配器似乎是更好的选择。

在实现方面，我们可以在当前实现的基础上继续进行多项改进：

• 与其使用后备分配器惰性分配块，不如在初始化时预先填充各链表，以提高初始的分配的性能。
• 为了简化实现，我们只允许块大小为2的幂，以便我们也可以将快大小也当做块对齐方式使用。通过以不同方式存储（或计算）对齐方式，我们还可以允许任意其他块大小。如此，我们就可以增加更多的块大小，例如为常见的分配建立块大小链表，以最大程度地减少内存浪费。
• 我们目前仅创建新的块，但不再释放它们，这将产生块碎片，最终可能会导致在进行大型分配时分配失败。为每个块大小强制设置最大链表长度可能也是合理的。当达到最大长度时，不应继续将其添加到链表中，而应当使用后备分配器直接将其彻底释放。
• 我们可以使用一个特殊的分配器来分配大于4KiB的内存，而不是使用后备的链表分配器。这个思路是利用大小恰好为4KiB的内存分页，将连续的虚拟内存块映射到非连续的物理帧。这样，未使用的内存碎片对于大型分配来说就不再是问题。
• 使用这样的页面分配器，可能有必要将块大小的上限提高到4KiB，并完全弃用链表分配器。这样的主要优点是减少了碎片并提高了性能可预测性，即在非理想情况下也能获取较好的性能。

要注意，上面提出的这些仅仅是改进建议。操作系统内核中使用的分配器通常会针对内核的特定工作负载进行高度优化，这只有通过广泛的性能分析才能实现。

其他分配器变体

固定大小的块分配器设计也有很多变体。slab分配器和伙伴分配器是两个流行的示例，它们也用在诸如Linux之类的流行内核中。下面，我们对这两种设计进行简短介绍。

Slab分配器

Slab分配器的思路是使用直接使用内核选定类型的大小作文的块大小。这样，对于这些类型的分配将恰好适合块大小，且不会浪费内存。有时，甚至有可能在未使用的块中预先初始化某些类型实例，以进一步提高性能。

Slab分配器通常与其他分配器结合使用。例如，它可以与固定大小的块分配器一起使用，以进一步拆分分配的块，从而减少内存浪费。此外，它还经常用于在单个大型分配时实现对象池模式。

伙伴分配器

伙伴分配器不是使用链表，而是使用二叉树来管理释放的块，同时配合使用2的幂作为块大小。当需要一定大小的新块时，它将一个较大的块分成两半，从而在树中创建两个子节点。每当释放一个块时，都会分析树中的邻居块。如果邻居也是空闲块，则将这两个块合并，重新成为双倍大小的块。

此合并过程的优点是减少了外部碎片，于是那些较小的释放块就可以重新用于较大的分配了。此外，它无需使用后备分配器，因此其性能更加可预测。它最大的缺点是只能使用2幂作为块大小，这可能会由于内部碎片而导致大量的内存浪费。因此，伙伴分配器通常与slab分配器一起使用，以将分配的块进一步拆分为多个较小的块。

小结

这篇文章概述了不同的分配器设计。我们学习了如何实现基本的线性分配器，它通过增加单个next指针来线性分配内存。虽然线性分配非常快，但是只有释放所有分配之后，它才能重新使用内存。因此，线性分配器很少用作全局分配器。

接下来，我们创建了一个链表分配器，该分配器使用释放的内存块本身来存放节点并组成链表，即所谓的空闲链表。该链表可以存储任意数量的大小不同的已释放块。尽管不会发生内存浪费，但是由于分配请求可能需要遍历整个列表，因此这种方法的性能很差。同时，我们的实现还遭受外部碎片的困扰，因为这个最小化的实现并不会将相邻的释放块重新合并在一起。

为了解决链表方法的性能问题，我们创建了一个固定大小的块分配器，该分配器预定义了一组固定的块大小。并为每个块大小设置一个单独的空闲链表，因此分配与释放只需要在相应列表的前端执行插入/取出，因此速度非常快。由于每个分配都向上取整到最接近的块大小，所以会因为内部碎片而浪费一些内存。

还有更多具有权衡不同取舍的分配器设计。Slab分配器可以为常见的固定大小的结构优化出更好地分配，但并非在所有情况下都适用。伙伴分配器使用二叉树将释放的块合并回去，但是可能会浪费大量内存，因为它仅支持的块大小只能为2的幂。重要的是要记住，每一个内核实现都有一个独特的工作量，因此并没有一个对所有情况都能保持“最佳”的分配器设计。

下期预告

目前，我就使用本文作为内存管理实现的尾声。接下来，我们将从线程开始探索对多任务的支持。在随后的文章中，我们将探讨多进程、进程、以及async/await形式的协作式多任务处理。

支持本项目

创建和维护这个博客和相关库是一项繁重的工作，但我真的很喜欢。通过支持我，您可以让我在新内容、新功能和持续维护上投入更多时间。

支持我的最好方式是在GitHub上赞助我，因为他们不收取任何中间费用。如果你喜欢其他平台，我也有Patreon和Donorbox账户。后者是最灵活的，因为它支持多种货币和一次性捐款。

感谢您的支持！