Redox Slab Allocatorで学ぶRustベアメタル環境のヒープアロケータ

はじめに

Redox Slab Allocator

Redox はRustで書かれたUnix-likeなマイクロカーネルOSです。

Redox Slab allocator はRedoxで使用されているSlab allocatorの実装です。もちろん、no_std(ベアメタル)環境での利用が可能です。

ソースコードは、約350行とコンパクトで、Rustのベアメタル環境でのヒープアロケータを学習する目的で読むにはうってつけです。

現在はメンテナンスが滞っているようで、1.31.0-nightly環境ではビルドできません。
この点も調査を実施したので、合わせて本記事内で紹介します。

想定する読者

Rustで以下のことをやりたい、興味がある方。

• ベアメタルプログラミング
• OS自作
• ヒープアロケータ自作

ベアメタルや自作OSで、VecやBoxなど、ヒープを利用する機能を、利用可能とする方法を調査します。
前半は、Slab Allocatorの実装を解説しますが、ご存じの方にとっては有用な情報はないと思います。

環境

項目	バージョンなど
ソースコード	slab_allocator a9e2bb08
Rustツールチェーン	nightly-x86_64-unknown-linux-gnu unchanged - rustc 1.31.0-nightly (77af31408 2018-10-11)

Slab Allocator

大雑把な動作

Slab allocatorは、大雑把に言うと、次のようなものです。

1. 大きなメモリ領域を確保しておく。
2. 確保したメモリ領域を、サイズの異なる小さな領域に分割する。
3. allocate要求に対して、適切なサイズの領域を割り当てる。
4. allocateされた領域がdeallocateされると、allocate要求で再び割り当てできるようになる。

コードを見ながら実際の動作を追いかけると、わかりやすいと思います。

何が嬉しいかというと、既に確保されている領域をやりくりするだけで、メモリの割り当てができ、メモリの割り当ておよび解放がO(1)になります。
また、メモリのフラグメンテーションを最小化できます。

このあたりは、先日の開催された技術書典5で頒布されたMemory Allocator Aquariumで紹介されています。

Redox Slab Allocatorソースコード解析

Heap struct

データ構造

アロケータとなるstructです。
Slab(説明は後述)の数は8つで固定、各Slabは最低4KBのサイズ、最小のヒープサイズは8×4KB=32KBです。

pub const NUM_OF_SLABS: usize = 8;
pub const MIN_SLAB_SIZE: usize = 4096;
pub const MIN_HEAP_SIZE: usize = NUM_OF_SLABS * MIN_SLAB_SIZE;

pub struct Heap {
    slab_64_bytes: Slab,
    slab_128_bytes: Slab,
    slab_256_bytes: Slab,
    slab_512_bytes: Slab,
    slab_1024_bytes: Slab,
    slab_2048_bytes: Slab,
    slab_4096_bytes: Slab,
    linked_list_allocator: linked_list_allocator::Heap,
}

Slabは、あるブロックサイズのメモリを管理するもの、と捉えてください。
これは、Slabの定義を見ると理解しやすいです。

pub struct Slab {
    block_size: usize,
    free_block_list: FreeBlockList,
}

各Slabのサイズを4KBと仮定した場合、例えば、Heap.slab_64_bytesは、64 bytesのメモリブロックを64個管理するSlabになります(64 bytes * 64 = 4KB)。
4KB以下のメモリ領域確保は、slab_64_bytesからslab_4096_bytesのメンバで対応します。

linked_list_allocatorは、4KBより大きいメモリ領域確保の要求があった場合に使用します。
本記事では、linked_list_allocatorに関しては説明しません。

初期化

ヒープ領域の開始アドレスと、ヒープ領域のサイズを渡して初期化します。与えられたアドレスが無効の場合、未定義動作となるため、本初期化関数はunsafeです。

impl Heap {
    /// Creates a new heap with the given `heap_start_addr` and `heap_size`. The start address must be valid
    /// and the memory in the `[heap_start_addr, heap_start_addr + heap_size)` range must not be used for
    /// anything else. This function is unsafe because it can cause undefined behavior if the
    /// given address is invalid.
    pub unsafe fn new(heap_start_addr: usize, heap_size: usize) -> Heap {
        // アライメントとヒープ領域のサイズが適正か、を最初に検証しています。
        assert!(
            heap_start_addr % 4096 == 0,
            "Start address should be page aligned"
        );
        assert!(
            heap_size >= MIN_HEAP_SIZE,
            "Heap size should be greater or equal to minimum heap size"
        );
        assert!(
            heap_size % MIN_HEAP_SIZE == 0,
            "Heap size should be a multiple of minimum heap size"
        );
        // 与えられたヒープサイズを8等分し、Slabサイズとして割り当て、Slabのインスタンスを作成します。
        let slab_size = heap_size / NUM_OF_SLABS;
        Heap {
            slab_64_bytes: Slab::new(heap_start_addr, slab_size, 64),
            slab_128_bytes: Slab::new(heap_start_addr + slab_size, slab_size, 128),
            slab_256_bytes: Slab::new(heap_start_addr + 2 * slab_size, slab_size, 256),
            slab_512_bytes: Slab::new(heap_start_addr + 3 * slab_size, slab_size, 512),
            slab_1024_bytes: Slab::new(heap_start_addr + 4 * slab_size, slab_size, 1024),
            slab_2048_bytes: Slab::new(heap_start_addr + 5 * slab_size, slab_size, 2048),
            slab_4096_bytes: Slab::new(heap_start_addr + 6 * slab_size, slab_size, 4096),
            linked_list_allocator: linked_list_allocator::Heap::new(heap_start_addr + 7 * slab_size, slab_size),
        }
    }

続いて、Slabの初期化を見ていきます。

64_bytesのSlab初期化呼び出し

    slab_64_bytes: Slab::new(heap_start_addr, slab_size, 64),

slab_sizeは与えられたヒープ領域を8等分したサイズです。64はblockサイズ、つまりSlabが管理するブロックの大きさです。

pub struct Slab {
    block_size: usize,
    free_block_list: FreeBlockList,
}

impl Slab {
    pub unsafe fn new(start_addr: usize, slab_size: usize, block_size: usize) -> Slab {
        // Slabが管理するブロックの個数を計算しています。
        let num_of_blocks = slab_size / block_size;
        Slab {
            block_size: block_size,
            // FreeBlockListのインスタンスを作成します。
            free_block_list: FreeBlockList::new(start_addr, block_size, num_of_blocks),
        }
    }
...

Slabのインスタンスを返しているだけです。管理対象のメモリブロックリスト、FreeBlockListのインスタンスを作成しています。

FreeBlockListの初期化を見てみましょう。
ここで、64 bytesのSlabにおいて、FreeBlockは64 bytesです。そのFreeBlockの先頭の8 bytes (next: Option<&'static mut FreeBlock>)を使ってListを構成します。残りの56 bytesは未使用のまま、空けておきます。
FreeBlockとして管理しているブロックは、誰にも割り当てていないため、その領域内をアロケータが管理情報に利用しても問題ありません。

struct FreeBlockList {
    len: usize,
    head: Option<&'static mut FreeBlock>,
}

impl FreeBlockList {
    unsafe fn new(start_addr: usize, block_size: usize, num_of_blocks: usize) -> FreeBlockList {
        let mut new_list = FreeBlockList::new_empty();
        // Listを後ろから構成しています。リストの順序をアドレス順に初期化するためだと思われます。あまり意味があるようには思えないですが。
        for i in (0..num_of_blocks).rev() {
            // FreeBlockを、block_size間隔で、メモリに配置していきます。
            let new_block = (start_addr + i * block_size) as *mut FreeBlock;
            new_list.push(&mut *new_block);
        }
        new_list
    }
...
    // pushされたFreeBlockをheadに追加します。
    fn push(&mut self, free_block: &'static mut FreeBlock) {
        free_block.next = self.head.take();
        self.len += 1;
        self.head = Some(free_block);
    }
...

// 次のFreeBlockへのポインタを持ちます。
struct FreeBlock {
    next: Option<&'static mut FreeBlock>,
}

さて、一番下のモジュールまで初期化処理を見たので、Heapに戻ります。

Heap初期化再掲載

impl Heap {
    pub unsafe fn new(heap_start_addr: usize, heap_size: usize) -> Heap {
...
        Heap {
            slab_64_bytes: Slab::new(heap_start_addr, slab_size, 64),
            slab_128_bytes: Slab::new(heap_start_addr + slab_size, slab_size, 128),
            slab_256_bytes: Slab::new(heap_start_addr + 2 * slab_size, slab_size, 256),
            slab_512_bytes: Slab::new(heap_start_addr + 3 * slab_size, slab_size, 512),
            slab_1024_bytes: Slab::new(heap_start_addr + 4 * slab_size, slab_size, 1024),
            slab_2048_bytes: Slab::new(heap_start_addr + 5 * slab_size, slab_size, 2048),
            slab_4096_bytes: Slab::new(heap_start_addr + 6 * slab_size, slab_size, 4096),
            linked_list_allocator: linked_list_allocator::Heap::new(heap_start_addr + 7 * slab_size, slab_size),
        }
    }

linked_list_allocatorは少し置いておいて、これで、Heapがどのように初期化されるかがわかりました。
Slabサイズが4KB(与えられたヒープ領域が32KB)だとすると、次の通りです。

Slab	初期化後	開始アドレス(ヒープ領域開始アドレスからの相対値)
64 bytes	64 bytes FreeBlock × 64個のリスト	0x0000
128 bytes	128 bytes FreeBlock × 32個のリスト	0x1000
256 bytes	256 bytes FreeBlock × 16個のリスト	0x2000
512 bytes	512 bytes FreeBlock × 8個のリスト	0x3000
1024 bytes	1024 bytes FreeBlock × 4個のリスト	0x4000
2048 bytes	2048 bytes FreeBlock × 2個のリスト	0x5000
4096 bytes	4096 bytes FreeBlock × 1個のリスト	0x6000

allocate/deallocate

allocateでは、ヒープ領域の割り当て要求に対して、適切なサイズのSlabから、FreeBlockを割り当てます。
deallocateでは、解放されたヒープ領域をFreeBlockに戻します。

まず、allocateからいきましょう。

pub enum HeapAllocator {
    Slab64Bytes,
    Slab128Bytes,
    Slab256Bytes,
    Slab512Bytes,
    Slab1024Bytes,
    Slab2048Bytes,
    Slab4096Bytes,
    LinkedListAllocator,
}
...
impl Heap {
...
    /// Allocates a chunk of the given size with the given alignment. Returns a pointer to the
    /// beginning of that chunk if it was successful. Else it returns `Err`.
    /// This function finds the slab of lowest size which can still accomodate the given chunk.
    /// The runtime is in `O(1)` for chunks of size <= 4096, and `O(n)` when chunk size is > 4096,
    pub fn allocate(&mut self, layout: Layout) -> Result<*mut u8, AllocErr> {
        // layout_to_allocator()で適切なサイズのSlabを見つけ、Slab.allocate()でブロックを割り当てます。
        match Heap::layout_to_allocator(&layout) {
            HeapAllocator::Slab64Bytes => self.slab_64_bytes.allocate(layout),
            HeapAllocator::Slab128Bytes => self.slab_128_bytes.allocate(layout),
            HeapAllocator::Slab256Bytes => self.slab_256_bytes.allocate(layout),
            HeapAllocator::Slab512Bytes => self.slab_512_bytes.allocate(layout),
            HeapAllocator::Slab1024Bytes => self.slab_1024_bytes.allocate(layout),
            HeapAllocator::Slab2048Bytes => self.slab_2048_bytes.allocate(layout),
            HeapAllocator::Slab4096Bytes => self.slab_4096_bytes.allocate(layout),
            HeapAllocator::LinkedListAllocator => self.linked_list_allocator.allocate_first_fit(layout),
        }
    }

layout_to_allocator()は次の通りです。確保要求のヒープ領域サイズとアライメントをチェックして、マッチする最小のサイズを返しています。

impl Heap {
    ///Finds allocator to use based on layout size and alignment
    pub fn layout_to_allocator(layout: &Layout) -> HeapAllocator {
        if layout.size() > 4096 {
            HeapAllocator::LinkedListAllocator
        } else if layout.size() <= 64 && layout.align() <= 64 {
            HeapAllocator::Slab64Bytes
        } else if layout.size() <= 128 && layout.align() <= 128 {
            HeapAllocator::Slab128Bytes
        } else if layout.size() <= 256 && layout.align() <= 256 {
            HeapAllocator::Slab256Bytes
        } else if layout.size() <= 512 && layout.align() <= 512 {
            HeapAllocator::Slab512Bytes
        } else if layout.size() <= 1024 && layout.align() <= 1024 {
            HeapAllocator::Slab1024Bytes
        } else if layout.size() <= 2048 && layout.align() <= 2048 {
            HeapAllocator::Slab2048Bytes
        } else {
            HeapAllocator::Slab4096Bytes
        }
    }
}

では、Slabのallocate()を見ていきます。ほぼ、FreeBlockListのpop()を呼び出しているだけなので、合わせて見ていきましょう。

impl Slab {
...
    pub fn allocate(&mut self, layout: Layout) -> Result<*mut u8, AllocErr> {
        match self.free_block_list.pop() {
            Some(block) => Ok(block.addr() as *mut u8),
            None => Err(AllocErr::Exhausted { request: layout }),
        }
    }
...

impl FreeBlockList {
...
    fn pop(&mut self) -> Option<&'static mut FreeBlock> {
        // headがNoneでなければ(FreeBlockが存在すれば)、map()を実行します。
        self.head.take().map(|node| {
            // head.nextをheadに更新します。
            self.head = node.next.take();
            self.len -= 1;
            node
        })
    }
...

想像通りの内容ですね。
deallocateは、逆のことをやるだけです。関連するコードをまとめておきます。

impl Heap {
...
    /// Frees the given allocation. `ptr` must be a pointer returned
    /// by a call to the `allocate` function with identical size and alignment. Undefined
    /// behavior may occur for invalid arguments, thus this function is unsafe.
    ///
    /// This function finds the slab which contains address of `ptr` and adds the blocks beginning
    /// with `ptr` address to the list of free blocks.
    /// This operation is in `O(1)` for blocks <= 4096 bytes and `O(n)` for blocks > 4096 bytes.
    pub unsafe fn deallocate(&mut self, ptr: *mut u8, layout: Layout) {
        match Heap::layout_to_allocator(&layout) {
            HeapAllocator::Slab64Bytes => self.slab_64_bytes.deallocate(ptr),
            HeapAllocator::Slab128Bytes => self.slab_128_bytes.deallocate(ptr),
            HeapAllocator::Slab256Bytes => self.slab_256_bytes.deallocate(ptr),
            HeapAllocator::Slab512Bytes => self.slab_512_bytes.deallocate(ptr),
            HeapAllocator::Slab1024Bytes => self.slab_1024_bytes.deallocate(ptr),
            HeapAllocator::Slab2048Bytes => self.slab_2048_bytes.deallocate(ptr),
            HeapAllocator::Slab4096Bytes => self.slab_4096_bytes.deallocate(ptr),
            HeapAllocator::LinkedListAllocator => self.linked_list_allocator.deallocate(ptr, layout),
        }
    }
...
}

impl Slab {
...
    pub fn deallocate(&mut self, ptr: *mut u8) {
        let ptr = ptr as *mut FreeBlock;
        unsafe {self.free_block_list.push(&mut *ptr);}
    }
...
}

impl FreeBlockList {
...
    fn push(&mut self, free_block: &'static mut FreeBlock) {
        free_block.next = self.head.take();
        self.len += 1;
        self.head = Some(free_block);
    }
...
}

特に難しい部分はないかと思います。

排他制御

ヒープアロケータは、複数のスレッドから呼び出されても正しく動作する必要があります。
そこで、spin lockをかけてHeapにアクセスします。

// Mutexでラップします。spin lockを使用します。
pub struct LockedHeap(Mutex<Option<Heap>>);

impl LockedHeap {
    // 空のLockedHeapを作成します。staticにインスタンスを作成するのに使います。
    pub const fn empty() -> LockedHeap {
        LockedHeap(Mutex::new(None))
    }

    // Heapインスタンスを作成します。
    pub unsafe fn init(&mut self, heap_start_addr: usize, size: usize) {
        *self.0.lock() = Some(Heap::new(heap_start_addr, size));
    }
...
}

// Alloc traitについては後述します。
unsafe impl<'a> Alloc for &'a LockedHeap {
    unsafe fn alloc(&mut self, layout: Layout) -> Result<*mut u8, AllocErr> {
        // lockを取得してからアクセスします。
        if let Some(ref mut heap) = *self.0.lock() {
            heap.allocate(layout)
        } else {
            panic!("allocate: heap not initialized");
        }
    }

    unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout) {
        // lockを取得してからアクセスします。
        if let Some(ref mut heap) = *self.0.lock() {
            heap.deallocate(ptr, layout)
        } else {
            panic!("deallocate: heap not initialized");
        }
    }
...
}

// Deref traitを実装して、Heapへのアクセスを容易にしています。
impl Deref for LockedHeap {
    type Target = Mutex<Option<Heap>>;

    fn deref(&self) -> &Mutex<Option<Heap>> {
        &self.0
    }
}

ここまでで、Redox Slab Allocatorの基本動作解説は終了です。

Rustのヒープアロケータ

ここからが本番です。

前置き

RustのBox、Vecなどは、ヒープ領域を利用します。
Rustでベアメタルプログラミングする際にも、これらの機能を使いたいところです。

Rustのデフォルトでは、メモリアロケータにjemallocを使っているようです。

jemallocについては、詳しくないので、気になる方は別途調査して下さい。
jemalloc について調べたのでまとめた

SMPでのスケーラビリティのためにFreeBSD のlibcに取り込ま標準アロケータとなっている

へー！

ベアメタル環境では、誰もヒープ領域を面倒見てくれないので、自分で何とかする必要があります。
Rustではメモリアロケータをカスタムする機能を提供しています。

core::alloc

Rust Core Libraryは、システムライブラリやlibcに依存しない、Rustのcore機能を提供するライブラリです。
組込み型や、cfgなどのマクロが含まれています。

Rust Core Library

core libraryの中で、メモリアロケータに関連するものは、core::allocです。

core::alloc

GlobalAlloc traitを実装し、#[global_allocator]をつけることで、デフォルトアロケータを登録します。

GlobalAlloc

本記事の前半で実装を追いかけたSlab Allocatorをデフォルトアロケータとして登録してみましょう。

GlobalAlloc trait実装

Required method

alloc/deallocの2つのmethodを実装します。

GlobalAllocのRequiredMethod

unsafe fn alloc(&self, layout: Layout) -> *mut u8
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout)

余談ですが、alloc()の返り値をraw pointerにしている点が理解できません。
このインタフェースでは、アロケートに失敗した場合、panic()するか、Null相当のアドレスを返すしかエラーハンドリングできません。

Redox Slab AllocatorのLockedHeapにalloc()/dealloc()が実装されていますが、これは(当時の)Alloc traitに対する実装です。
GlobalAlloc traitの実装は次のようになります。
ここでは、アロケートに失敗した場合は、アドレス0を指すポインタを返しています。

Heapのallocate()/deallocate()を呼び出すので、復習のために、シグネチャを再掲載しておきます。

Heapのallocate/deallocate

impl Heap {
    unsafe fn allocate(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>
    unsafe fn deallocate(&mut self, ptr: *mut u8, layout: Layout)
}

GlobalAlloc実装

unsafe impl GlobalAlloc for LockedHeap {
    unsafe fn alloc(&mut self, layout: Layout) -> *mut u8 {
        self.0
            .lock()  // spin lockを取得
            .allocate(layout)  // Slab allocatorからヒープ領域を取得
            .unwrap_or_else(|| 0 as *mut u8)  // Resultをraw pointerに変換
    }

    unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout) {
        self.0
            .lock()
            .deallocate(ptr, layout)
    }
}

次に、最上位のモジュールで、staticなHeapインスタンスを作成し、global_allocator attiributeを付けてあげます。

use slab_allocator::LockedHeap;

#[global_allocator]
static ALLOCATOR: LockedHeap = LockedHeap::empty();

最後に、ヒープを初期化してあげると、VecやBoxを利用できるようになります。

pub fn init_heap() {
    let heap_start = …;
    let heap_end = …;
    let heap_size = heap_end - heap_start;
    unsafe {
        ALLOCATOR.lock().init(heap_start, heap_size);
    }
}

登録したヒープロケータの使われ方を追う

さて、ヒープアロケータの登録が済んだので、実際にどう利用されるかを見て、なるほどー、となりましょう。

Vec::with_capacity()でメモリ確保の動作を追う

Vec::with_capacity()を例に、メモリ確保の動作を追いかけてみましょう。
Vec::with_capacity()は次のように定義されています。

vec

liballoc/vec.rs

impl<T> Vec<T> {
...
    pub fn with_capacity(capacity: usize) -> Vec<T> {
        Vec {
            buf: RawVec::with_capacity(capacity),  // ★
            len: 0,
        }
    }
...

bufは、RawVec::with_capacity()で確保しています。
RawVec::with_capacity()の実装は、次の通りです。

raw_vec.rs

liballoc/raw_vec.rs

impl<T> RawVec<T, Global> {
...
    pub fn with_capacity(cap: usize) -> Self {
        RawVec::allocate_in(cap, false, Global)  // ★
    }
...

さらに、RawVec::allocate_in()に処理が移っていきます。
次が、メモリ確保処理の本体になります。
エッジケースの処理はありますが、基本は★印の部分でヒープ領域を確保します。

liballoc/raw_vec.rs

impl<T, A: Alloc> RawVec<T, A> {
...
    fn allocate_in(cap: usize, zeroed: bool, mut a: A) -> Self {
        unsafe {
            let elem_size = mem::size_of::<T>();

            let alloc_size = cap.checked_mul(elem_size).unwrap_or_else(|| capacity_overflow());
            alloc_guard(alloc_size).unwrap_or_else(|_| capacity_overflow());

            // handles ZSTs and `cap = 0` alike
            let ptr = if alloc_size == 0 {
                NonNull::<T>::dangling()
            } else {
                let align = mem::align_of::<T>();
                let layout = Layout::from_size_align(alloc_size, align).unwrap();
                let result = if zeroed {
                    a.alloc_zeroed(layout)
                } else {
                    a.alloc(layout)  // ★
                };
                match result {
                    Ok(ptr) => ptr.cast(),
                    Err(_) => handle_alloc_error(layout),
                }
            };

            RawVec {
                ptr: ptr.into(),
                cap,
                a,
            }
        }
    }
...

★の部分で、ヒープアロケータのalloc()が呼ばれている匂いがします。
a.alloc()に、引数Layoutを渡して呼び出しています。Layoutは、メモリサイズとアライメントを指定する構造体です。

pub struct Layout {
    size: usize,
    align: usize,
}

ここで、aはAllocトレイトを実装している型Aとなります。
この型Aはどこから来ているのでしょうか。

RawVec構造体は次のように定義されています。

liballoc/raw_vec.rs

pub struct RawVec<T, A: Alloc = Global> {
    ptr: Unique<T>,
    cap: usize,
    a: A,
}

A: Alloc = Globalこれが、GlobalAllocなのではないか、という推測をするのは自然なことでしょう。
Globalがどのように定義されているか、調査します。

答えを求めて、alloc.rsを読み進めます。

liballoc/alloc.rs

/// The global memory allocator.
///
/// This type implements the [`Alloc`] trait by forwarding calls
/// to the allocator registered with the `#[global_allocator]` attribute
/// if there is one, or the `std` crate’s default.
#[unstable(feature = "allocator_api", issue = "32838")]
#[derive(Copy, Clone, Default, Debug)]
pub struct Global;

ありました！#[global_allocator] attributeで登録したアロケータに、呼び出しをフォワーディングする、とあります。
Globalは、Alloc traitを実装しています。
RawVecのアロケータ呼び出しでは、Alloc traitを要求していたため、これで繋がります。
Alloc traitの実装は、さらにモジュール内の関数を呼び出しています。

liballoc/alloc.rs

#[unstable(feature = "allocator_api", issue = "32838")]
unsafe impl Alloc for Global {
    #[inline]
    unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
        // モジュール内のalloc()を呼び出します。
        NonNull::new(alloc(layout)).ok_or(AllocErr)
    }

    #[inline]
    unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
        // モジュール内のdealloc()を呼び出します。
        dealloc(ptr.as_ptr(), layout)
    }
...

/// Allocate memory with the global allocator.
///
/// This function forwards calls to the [`GlobalAlloc::alloc`] method
/// of the allocator registered with the `#[global_allocator]` attribute
/// if there is one, or the `std` crate’s default.stable.
#[inline]
pub unsafe fn alloc(layout: Layout) -> *mut u8 {
    __rust_alloc(layout.size(), layout.align())
}
}

/// Deallocate memory with the global allocator.
///
/// This function forwards calls to the [`GlobalAlloc::dealloc`] method
/// of the allocator registered with the `#[global_allocator]` attribute
/// if there is one, or the `std` crate’s default.
#[inline]
pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) {
    __rust_dealloc(ptr, layout.size(), layout.align())
}

コメントを読むと、GlobalAlloc::allocの呼び出しにフォワーディングする、とあります。
これで、GlobalAllocに繋がりましたね！

さて、お気づきでしょうか？
GlobalAlloc traitの実装では、raw pointerを返していましたが、GlobalのAlloc trait実装は、Resultを返しています。

                let result = if zeroed {
                    a.alloc_zeroed(layout)
                } else {
                    a.alloc(layout)
                };
                match result {
                    Ok(ptr) => ptr.cast(),
                    Err(_) => handle_alloc_error(layout),
                }

よく見るとここでNonNull::new()の結果により、Resultでラップしています。
素直にGlobalAllocからResultを返せば良いように思えますが…。

unsafe impl Alloc for Global {
    #[inline]
    unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
        // モジュール内のalloc()を呼び出します。
        NonNull::new(alloc(layout)).ok_or(AllocErr)
...
}

2018年のAllocator事情

今回の調査をしている間に把握できたもののみ掲載します。
昔のコードをビルドする際の参考にして頂ければ。

• GlobalAlloc traitが追加されたようです。(以前はAlloc traitのみだった?)
• global_alloc機能がstableになったようです。(1.28.0以降)
• alloc::allocatorがalloc::allocになったようです。

Redox Slab Allocatorは上記変更に対応していないようです。

BlogOSの著者である、Philipp Oppermann氏が公開しているlinked-list-allocatorはメンテナンスが継続しています。
こちらは、1.31.0-nightlyでもビルドできました。

linked-list-allocator

The Embedded Rust Book

Rustのembedded WGがドキュメントを作成してくれています。
The Embedded Rust Book

この中のcollectionsの章に、ベアメタルでのアロケータの説明があります。

collections

heapless

上記collectionsの章を読んでいて知ったのですが、heaplessというcrateがあります。
これは、条件付きでVecなどのcollectionを、アロケータなしで使えるようにするもののようです。

heapless

条件は、サイズを固定長で定義する必要があったり、pushの結果がResultで返ってくる、というものです。
stackにそのまま展開してくれるようなので、これは納得ですね。

おわりに

今回、初めて、Rustの標準ライブラリを追いかけました。
コード自体は非常に可読性が高く、対象のコードに辿り着いてからは、ほとんど苦労することなく、調査を進めることができました。
ライブラリのコードを読むのは、とても楽しかったです。
まだ、読んだことがない方は、気になるテーマを決めて、ライブラリに行きつくまでコードリーディングしてみてはいかがでしょうか。

反面、いつ、どのような変更が入ったのか、現在議論中なのか、議論に決着がついているのか、というあたりは、イマイチ追いかける勘所がわからず、暗中模索の状態です。

参考文献

参考にさせて頂きました。ありがとうございます。

1. Writing an OS in Rust (First Edition)
2. Memory Allocator Aquarium