可扩展的无锁伙伴系统分配器

算法源： https://hpdcs.github.io/ths/scar17.pdf

简介

伙伴内存分配技术是一种内存分配算法，它将内存划分为分区，以尽可能满足内存请求。该系统通过将内存分为两半来尝试给出最佳匹配。据Donald Knuth所说，伙伴系统由Harry Markowitz于1963年发明，并由Kenneth C. Knowlton首次描述（1965年出版）。伙伴内存分配相对容易实现。它支持内存块的有限但有效的拆分和合并。

此分配器旨在用于操作系统目的，但也可能用于用户空间。

分配器需要任何后端分配器来分配内部数据结构。在操作系统中，它可能基于静态内存的分配器；在用户空间中，std::alloc::Global 是一个好的候选者。依赖于全局分配器似乎是不正确的，因为伙伴系统分配器广泛用作页面分配器，而全局分配器可能在伙伴初始化点未初始化。

待办事项

• 文档
• 代码重构
• 标准基准测试
• 完整的测试用例集
• 支持稳定版Rust（??）

示例

#![feature(allocator_api)]
#![feature(thread_id_value)]

extern crate lock_free_buddy_allocator;

use lock_free_buddy_allocator::buddy_alloc::BuddyAlloc;
use lock_free_buddy_allocator::cpuid;

use std::{alloc::Global, thread};

const PAGE_SIZE: usize = 1 << 12;

struct Cpu;

impl cpuid::Cpu for Cpu {
    fn current_cpu() -> usize {
        thread::current().id().as_u64().get() as usize
    }
}

fn main() {
    let buddy: BuddyAlloc<PAGE_SIZE, Cpu, std::alloc::Global> =
        BuddyAlloc::<PAGE_SIZE, Cpu, _>::new(0, 4096, &Global).unwrap();

    buddy.free(buddy.alloc(2).unwrap(), 2);
}

许可证

lock_free_buddy_allocator 在MIT许可证下分发（见 LICENSE）。