11. 内存分配器设计

---

title: 内存分配器设计 date: 2020-01-22 18:31:30 tags: [Memory Management]

summary: 这篇文章介绍了如何从头开始实现堆分配器。它提出并讨论了不同的分配器设计，包括Bump分配，基于链表的分配和固定大小的块分配。 对于这三种设计中的每一种，我们将创建一个可用于我们的内核的基本实现。

介绍

linked_list_allocator

linked_list_allocator

设计目标

allocdealloc

除了正确性之外，还有许多次要设计目标。 例如，分配器应有效地利用可用内存并使碎片)减少。此外，它对于并发应用程序应能很好地工作，并可扩展到任意数量的处理器。 为了获得最佳性能，它甚至可以针对CPU缓存优化内存布局，以提高缓存亲和性并避免False Sharing 。

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

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

Bump分配器

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

基本想法

nextnextnext

nextnext

allocdeallocnext

实现

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 {
    /// Creates a new empty bump allocator.
    pub const fn new() -> Self {
        BumpAllocator {
            heap_start: 0,
            heap_end: 0,
            next: 0,
            allocations: 0,
        }
    }
    /// Initializes the bump allocator with the given heap bounds.
    ///
    /// This method is unsafe because the caller must ensure that the given
    /// memory range is unused. Also, this method must be called only once.
    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_startheap_endinitunsafe

nextinitheap_start

allocations

initnewlinked_list_allocator

GlobalAlloc

GlobalAlloc trait

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 { ... }
}

allocdealloc

首次尝试实现

BumpAllocatoralloc

// in src/allocator/bump.rs
use alloc::alloc::{GlobalAlloc, Layout};
unsafe impl GlobalAlloc for BumpAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // TODO alignment and bounds check
        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!();
    }
}

nextnext*mut u8allocations

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

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

GlobalAllocallocdealloc&selfnextallocationsnext

&self&mut selfGlobalAlloc

GlobalAlloc

&selfGlobalAlloc#[global_allocator]GlobalAllocstatic&mut selfGlobalAlloc&self

&self&mut selfspin::Mutexlock&self&mut self

Locked

spin::MutexGlobalAllocBumpAllocatorspin::Mutex

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
/// A wrapper around spin::Mutex to permit trait implementations.
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::MutexAnewlockMutexlockLockedallocator

Locked

Lockedspin::MutexGlobalAlloc

// 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(); // get a mutable reference
        let alloc_start = align_up(bump.next, layout.align());
        let alloc_end = alloc_start + layout.size();
        if alloc_end > bump.heap_end {
            ptr::null_mut() // out of memory
        } 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(); // get a mutable reference
        bump.allocations -= 1;
        if bump.allocations == 0 {
            bump.next = bump.heap_start;
        }
    }
}

allocdeallocinnerMutex::lock

allocnextLayoutalign_upalign_upalloc_startnextallocations*mut u8alloc_start

deallocLayoutallocations0nextheap_start

align_upallocator

// in src/allocator.rs
fn align_up(addr: usize, align: usize) -> usize {
    let remainder = addr % align;
    if remainder == 0 {
        addr // addr already aligned
    } else {
        addr - remainder + align
    }
}

alignaddr0align

使用

linked_list_allocatorallocator.rsALLOCATOR

// in src/allocator.rs
use bump::BumpAllocator;
#[global_allocator]
static ALLOCATOR: Locked<BumpAllocator> = Locked::new(BumpAllocator::new());

BumpAllocator::newLocked::newconststatic

init_heapALLOCATOR.lock().init(HEAP_START, HEAP_SIZE)linked_list_allocator

heap_allocationheap_allocation

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

讨论

allocdealloc

toolshed

Bump分配器的缺点

many_boxes

// in tests/heap_allocation.rs
#[test_case]
fn many_boxes_long_lived() {
    serial_print!("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
    serial_println!("[ok]");
}

many_boxeslong_lived

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

> cargo xtest --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_livedallocationsallocationsallocations

重用释放的内存？

问题是：我们可以通过某种方式扩展凹凸分配器以消除此限制吗？

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

nextheap_start

next

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

链表分配器

在实现分配器时，跟踪任意数量的空闲内存区域的常见技巧是将这些区域本身用作后备存储。 这利用了以下事实：区域仍被映射到虚拟地址并由物理帧支持，但是不再需要存储信息。 通过在已被释放的区域中存储有关的信息，我们可以跟踪无限制数量的已被释放的区域，而无需额外的内存。

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

head

linked_list_allocator

实现

LinkedListAllocator

分配器类型

allocator::linked_listListNode

// in src/allocator.rs
pub mod linked_list;

// in src/allocator/linked_list.rs
struct ListNode {
    size: usize,
    next: Option<&'static mut ListNode>,
}

sizeOption<&'static mut ListNode>&'static mutBox

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
    }
}

newnewnextNonelib.rs#![feature(const_mut_refs)]

ListNodeLinkedListAllocator

// in src/allocator/linked_list.rs
pub struct LinkedListAllocator {
    head: ListNode,
}
impl LinkedListAllocator {
    /// Creates an empty LinkedListAllocator.
    pub const fn new() -> Self {
        Self {
            head: ListNode::new(0),
        }
    }
    /// Initialize the allocator with the given heap bounds.
    ///
    /// This function is unsafe because the caller must guarantee that the given
    /// heap bounds are valid and that the heap is unused. This method must be
    /// called only once.
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        self.add_free_region(heap_start, heap_size);
    }
    /// Adds the given memory region to the front of the list.
    unsafe fn add_free_region(&mut self, addr: usize, size: usize) {
        todo!();
    }
}

headnextListNone::newsizeheadListNode&'static mut ListNodealloc

newnewconstALLOCATORinit

initadd_free_regiontodo!

add_free_region

add_free_regioninitdeallocdealloc

add_free_region

// in src/allocator/linked_list.rs
use super::align_up;
use core::mem;
impl LinkedListAllocator {
    /// Adds the given memory region to the front of the list.
    unsafe fn add_free_region(&mut self, addr: usize, size: usize) {
        // ensure that the freed region is capable of holding ListNode
        assert!(align_up(addr, mem::align_of::<ListNode>()) == addr);
        assert!(size >= mem::size_of::<ListNode>());
        // create a new list node and append it at the start of the list
        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

add_free_regionfreednodeOption::takenextheadheadNone

writenodeheadhead

find_region

allocfind_region

// in src/allocator/linked_list.rs
impl LinkedListAllocator {
    /// Looks for a free region with the given size and alignment and removes
    /// it from the list.
    ///
    /// Returns a tuple of the list node and the start address of the allocation.
    fn find_region(&mut self, size: usize, align: usize)
        -> Option<(&'static mut ListNode, usize)>
    {
        // reference to current list node, updated for each iteration
        let mut current = &mut self.head;
        // look for a large enough memory region in linked list
        while let Some(ref mut region) = current.next {
            if let Ok(alloc_start) = Self::alloc_from_region(&region, size, align) {
                // region suitable for allocation -> remove node from list
                let next = region.next.take();
                let ret = Some((current.next.take().unwrap(), alloc_start));
                current.next = next;
                return ret;
            } else {
                // region not suitable -> continue with next region
                current = current.next.as_mut().unwrap();
            }
        }
        // no suitable region found
        None
    }
}

currentwhile letcurrentheadnextelsealloc_start

current.nextNoneNonealloc_from_region

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

regioncurrentregion.nextcurrent.nextOption::takeregion.nextcurrent.nextNonenextret

current.nextnextregion.nextcurrentregionregionret

alloc_from_region

alloc_from_region

// in src/allocator/linked_list.rs
impl LinkedListAllocator {
    /// Try to use the given region for an allocation with given size and
    /// alignment.
    ///
    /// Returns the allocation start address on success.
    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 + size;
        if alloc_end > region.end_addr() {
            // region too small
            return Err(());
        }
        let excess_size = region.end_addr() - alloc_end;
        if excess_size > 0 && excess_size < mem::size_of::<ListNode>() {
            // rest of region too small to hold a ListNode (required because the
            // allocation splits the region in a used and a free part)
            return Err(());
        }
        // region suitable for allocation
        Ok(alloc_start)
    }
}

align_up

ListNodeexcess_size == 0ListNode

GlobalAlloc

add_free_regionfind_regionGlobalAllocLinkedListAllocatorLockedLockedallocdealloc&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 {
        // perform layout adjustments
        let (size, align) = LinkedListAllocator::size_align(layout);
        let mut allocator = self.inner.lock();
        if let Some((region, alloc_start)) = allocator.find_region(size, align) {
            let alloc_end = alloc_start + size;
            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) {
        // perform layout adjustments
        let (size, _) = LinkedListAllocator::size_align(layout);
        self.inner.lock().add_free_region(ptr as usize, size)
    }
}

deallocMutex::lock&mut LinkedListAllocatoradd_free_region

allocMutex::lockfind_regionNonenull_mut

find_regionalloc_startadd_free_region*mut u8alloc_start

布局调整

allocdeallocListNodeListNodeListNode

size_align

// in src/allocator/linked_list.rs
impl LinkedListAllocator {
    /// Adjust the given layout so that the resulting allocated memory
    /// region is also capable of storing a `ListNode`.
    ///
    /// Returns the adjusted size and alignment as a (size, align) tuple.
    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())
    }
}

Layoutalign_toListNodepad_to_alignListNodemaxmem::size_of::deallocListNode

align_topad_to_align#![feature(alloc_layout_extra)]lib.rs

使用

allocatorALLOCATORLinkedListAllocator

// in src/allocator.rs
use linked_list::LinkedListAllocator;
#[global_allocator]
static ALLOCATOR: Locked<LinkedListAllocator> =
    Locked::new(LinkedListAllocator::new());

initinit_heapinit

heap_allocationmany_boxes_long_lived

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

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

讨论

与Bump分配器相比，链表分配器更适合用作通用分配器，主要是因为它能够直接重用释放的内存。但是，它也有一些缺点。其中一些是由我们的实现引起的，但是链表分配器这种设计本身也存在一些缺点。

合并释放的块

我们实现的主要问题是，它只会将堆拆分为较小的块，而不会将它们重新合并在一起。考虑以下示例：

在第一行中，在堆上进行了三次分配。它们中的两个在第2行中再次被释放，而第三个在第3行中被释放。现在整个堆都不再被使用，但仍被分成四个单独的块。此时，可能无法再进行大分配，因为四个块都不足够大。随着时间的流逝，该过程将继续进行，并将堆分成越来越小的块。这样下去总有一天，堆中会充满此类碎片，以至于正常大小的分配都将失败。

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

22a33a

linked_list_allocatordeallocatedeallocate

性能

正如我们在上面学到的，Bump分配器非常快，可以优化为仅需几个汇编指令操作。链表分配器的性能要差得多。其问题是分配请求可能需要遍历完整的链表，直到找到合适的块为止。

由于列表长度取决于未使用的存储块的数量，因此对于不同的程序，其性能可能会发生极大的变化。仅创建几个分配的程序将有相对较快的分配性能。但是，对于一个会进行很多次分配，导致堆变得碎片化的程序，分配性能将非常糟糕，因为链表将非常长，并且其中大多数包含的块都非常小。

值得注意的是，这类性能问题不是由我们的实现引起的问题，而是链表方法的根本问题。由于分配性能对于内核级代码非常重要，因此我们在下面探讨了第三种分配器设计，该设计以降低内存利用率代价来提高性能。

固定大小的块分配器

下面，我们介绍一种分配器设计，该设计使用固定大小的内存块来满足分配请求。这样，分配器通常返回的块大于分配所需的块，这会由于内部碎片#Internal_fragmentation)而导致内存浪费。另一方面，它大大减少了找到合适块所需的时间（与链表分配器相比），从而有更好的分配性能。

介绍

固定大小的块分配器背后的思想是：并不恰好分配大小等于所需的内存，而是固定一些块大小并将每个分配舍入到能装下它的最小块大小。例如，对于16、64和512字节的块大小，分配4个字节将返回一个16字节的块，分配一个48字节将返回一个64字节的块，而分配128个字节将返回一个512字节的块。 。

像链表分配器一样，我们通过在未使用的内存中创建链表来跟踪未使用的内存。但是，我们不使用具有不同块大小的单个列表，而是为每个大小类创建一个单独的列表。然后，每个链表仅存储单个大小的块。例如，对于块大小为16、64和512的内存，将有三个单独的链表：

head_16head_64head_512headhead_16

由于列表中的每个元素都具有相同的大小，因此每个列表元素都同样适用于分配请求。这意味着我们可以使用以下步骤非常有效地执行分配：

head_16

最值得注意的是，我们总是可以返回链表的第一个元素，而不再需要遍历整个链表。因此，分配比使用链表分配器快得多。

块大小和浪费的内存

根据块大小，我们通过舍入会损失很多内存。例如，当返回一个512字节的块以进行128字节的分配时，分配的内存中有四分之三未被使用。通过定义合理的块大小，可以在某种程度上限制浪费的内存量。例如，当使用2的幂（4、8、16、32、64、128、…）作为块大小时，在最坏的情况下，我们可以将内存浪费限制为分配大小的一半，平均情况下为分配的四分之一。

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

释放

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

deallocallocallocdealloc

dealloc

后备分配器

鉴于大容量分配（> 2KB）通常是很少见的，尤其是在操作系统内核中，因此有可能需要退回到其他分配器进行这些分配。例如，为了减少内存浪费，我们可以退回到链表分配器中进行大于2048字节的分配。由于预期该大小的分配非常少，因此这个链表将保持较小状态，因此分配和释放仍会相当快。

创建新块

上面，我们始终假定列表中始终有足够的特定大小的块来满足所有分配请求。但是，在某个时候，块大小的链接列表将为空。此时，有两种方法可以创建特定大小的未使用的新块来满足分配请求：

• 从后备分配器分配一个新块（如果有）。
• 从其他列表中拆分较大的块。如果块大小为2的幂，则此方法最有效。例如，一个32字节的块可以分为两个16字节的块。

对于我们的实现，为了简单考虑，因此我们将从后备分配器分配新块。

实现

现在我们知道了固定大小的块分配器是如何工作的，我们可以开始实现它了。我们将不依赖于上一节中创建的链表分配器的实现，因此即使您跳过了链表分配器的实现，也可以看这一部分。

列表节点

allocator::fixed_size_blockListNode

// in src/allocator.rs
pub mod fixed_size_block;

// in src/allocator/fixed_size_block.rs
struct ListNode {
    next: Option<&'static mut ListNode>,
}

ListNodesize

块大小

BLOCK_SIZES

// in src/allocator/fixed_size_block.rs
/// The block sizes to use.
///
/// The sizes must each be power of 2 because they are also used as
/// the block alignment (alignments must be always powers of 2).
const BLOCK_SIZES: &[usize] = &[8, 16, 32, 64, 128, 256, 512, 1024, 2048];

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

BLOCK_ALIGNMENTS

分配器类型

ListNodeBLOCK_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_headsheadlen()BLOCK_SIZESlinked_list_allocatorLinkedListAllocator

FixedSizeBlockAllocatornewinit

// in src/allocator/fixed_size_block.rs
impl FixedSizeBlockAllocator {
    /// Creates an empty FixedSizeBlockAllocator.
    pub const fn new() -> Self {
        FixedSizeBlockAllocator {
            list_heads: [None; BLOCK_SIZES.len()],
            fallback_allocator: linked_list_allocator::Heap::empty(),
        }
    }
    /// Initialize the allocator with the given heap bounds.
    ///
    /// This function is unsafe because the caller must guarantee that the given
    /// heap bounds are valid and that the heap is unused. This method must be
    /// called only once.
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        self.fallback_allocator.init(heap_start, heap_size);
    }
}

newlist_headsfallback_allocatorCopy#![feature(const_in_array_repeat_expressions)]NoneCopyListNodeCopyOptionNoneCopy

fallback_allocatorlist_headsallocdealloc

fallback_allocfallback_allocator

// in src/allocator/fixed_size_block.rs
use alloc::alloc::Layout;
use core::ptr;
impl FixedSizeBlockAllocator {
    /// Allocates using the fallback allocator.
    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_allocatorHeapGlobalAllocallocate_first_fitResult, AllocErr>*mut u8NonNullAllocErrOkNonNull::as_ptrErr*mut u8
计算链表索引
GlobalAlloclist_indexLayout
// in src/allocator/fixed_size_block.rs
/// Choose an appropriate block size for the given layout.
///
/// Returns an index into the `BLOCK_SIZES` array.
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)
}
Layoutrequired_block_sizesize()align()BLOCK_SIZESiter()position
BLOCK_SIZESlist_heads
GlobalAlloc
GlobalAlloc
// 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!();
    }
}
GlobalAllocLockedallocdealloc
alloc
alloc
// in `impl` block 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 => {
                    // no block exists in list => allocate new block
                    let block_size = BLOCK_SIZES[index];
                    // only works if all block sizes are a power of 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::locklist_indexlist_headsNonefallback_allocatorfallback_alloc
Somelist_heads[index]Option::takeSome(node)matchnodetakenode*mut u8
NoneBLOCK_SIZESLayoutfallback_alloc
dealloc
dealloc
// in src/allocator/fixed_size_block.rs
use core::{mem, ptr::NonNull};
// inside the `unsafe impl GlobalAlloc` block
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);
        }
    }
}
alloclocklist_indexLayoutNoneBLOCK_SIZESdeallocateNonNull*mut u8unwrapdealloc
list_indexListNodeOption::takeindexListNode*mut u8*mut ListNodewritenew_node_ptr
有几件事值得注意： 
allocdeallocallocunsafeallocdeallocunsafeunsafeunsafe
使用
FixedSizeBlockAllocatorallocatorALLOCATOR
// in src/allocator.rs
use fixed_size_block::FixedSizeBlockAllocator;
#[global_allocator]
static ALLOCATOR: Locked<FixedSizeBlockAllocator> = Locked::new(
    FixedSizeBlockAllocator::new());
initinit_heapinit
heap_allocation
> cargo xtest --test heap_allocation
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]
many_boxes_long_lived... [ok]
我们的新分配器似乎可以正常工作！ 
讨论
尽管固定大小的块方法比链表方法具有更好的性能，但是当使用2的幂作为块大小时，它最差情况下会浪费多达一半的内存。这种权衡是否值得，在很大程度上取决于应用程序类型。对于性能至关重要的操作系统内核，固定大小块方法似乎是更好的选择。
在实现方面，我们可以在当前的实现中进行很多改进： 

与其仅使用后备分配器Lazy地分配块，还不如预先填充列表以提高初始分配的性能。 
为了简化实现，我们只允许块大小为2的幂，以便我们也可以将它们用作块对齐。通过以不同的方式存储（或计算）对齐方式，我们还可以允许任意其他块大小。这样，我们可以增加更多的块大小，例如常见的分配大小，以最大程度地减少浪费的内存。
目前，我们仅创建新的块，但不再释放它们。这会导致碎片，最终可能导致大块内存的分配请求失败。为每种块大小列表强制设置最大长度可能是一个好的选择。当达到最大长度时，后续的释放使用后备分配器进行，而不是将其添加到列表中。
我们可以使用一个特殊的分配器来分配大于4KiB的内存，而不是使用链表分配器。这个想法利用了在4KiB页面上运行的分页可以将连续的虚拟内存块映射到非连续的物理帧。这样，未分配内存的碎片对于大分配而言不再是问题。
使用这样的页面分配器，可能有必要添加最大4KiB的块大小并完全删除链表分配器。这样做的主要优点是减少了碎片并提高了性能可预测性，即更好的最坏情况性能。
请务必注意，上面概述的实现上的改进仅是建议。操作系统内核中使用的分配器通常会针对内核的特定工作负载进行高度优化，这只有通过广泛的性能分析才能实现。
变化
固定大小的块分配器设计也有很多变体。slab分配器和伙伴分配器是两个流行的示例，它们也用在诸如Linux之类的流行内核中。下面，我们对这两种设计进行简短介绍。
slab分配器
slab分配器的思想是使用与内核中选定类型直接对应的块大小。这样，那些类型的分配恰好适合块大小，并且不会浪费内存。有时，甚至有可能在未使用的块中预先初始化好类型实例，以进一步提高性能。
slab分配通常与其他分配器结合使用。例如，它可以与固定大小的块分配器一起使用，以进一步拆分分配的块，以减少内存浪费。它还经常用于在一次分配大块内存，然后在这块内存上实现对象池模式。
伙伴分配器
伙伴分配器设计不是使用链表来管理释放的块，而是使用二叉树数据结构以及2的幂次方块大小。当需要一定大小的新块时，它将一个较大的块分成两半，从而在树中创建两个子节点。每当再次释放一个块时，就会分析树中的相邻块。如果邻居也是空的，则将两个块重新连接在一起，成为一个大小两倍的块。
此合并过程的优点是减少了外部碎片#Externalfragmentation)，因此可以将较小的释放块重新用于较大的分配。它还不使用后备分配器，因此性能更可预测。最大的缺点是只能使用2的幂次的块大小，这可能会由于[内部碎片](https://en.wikipedia.org/wiki/Fragmentation(computing)#Internal_fragmentation)而导致大量的内存浪费。因此，伙伴分配器通常与slab分配器结合使用，以将分配的块进一步拆分为多个较小的块。
总结
next
接下来，我们创建了一个链表分配器，该分配器使用空闲的内存块本身来创建链表，即所谓的链表。该列表可以存储任意数量的大小不同的已释放块。尽管不会发生内存浪费，但是由于分配请求可能需要完整遍历列表，因此该方法的性能很差。我们的实现还遭受外部碎片#External_fragmentation)的困扰，因为它不会将相邻的释放块重新合并在一起。
为了解决链表方法的性能问题，我们创建了一个固定大小块分配器，该分配器预定义了一组固定的块大小。对于每个块大小，都存在一个单独的空闲列表，因此分配和取消分配只需要在列表的开头插入/弹出，因此非常快。由于每个分配都向上舍入到下一个更大的块大小，因此由于内部碎片#Internal_fragmentation)而浪费了一些内存。
还有更多具有不同权衡取舍的分配器设计。slab分配可以很好地优化常见固定大小结构的分配，但并非在所有情况下都适用。伙伴分配使用二叉树将释放的块合并回去，但浪费了大量内存，因为它仅支持2次幂的块大小。同样重要的是要记住，每个内核实现都有独特的工作负载，因此没有适合所有情况的“最佳”分配器设计。
接下来是什么？
通过这篇文章，我们现在就结束了我们的内存管理部分。接下来，我们将开始探索多任务处理，从线程)开始。在随后的文章中，我们将探索多处理器、进程以及基于async/await的协作式多任务处理。