過ぎるだけの時間じゃ悔しい
[malloc] Redox OS Slab Allocator読む.
Posted on

Redox OS Slab Allocator読む

  • [[2022-03-07]]

slab: 厚切り

Rustはdefaultで jemalloc 使っている. baremetalでは誰も面倒みないので自力で管理する

core::alloc

GlobalAlloc trait を実装する

Slab Allocator

  1. 大きなメモリ領域を確保する
  2. 領域に分割
  3. allocate で適切なサイズに割り当てる
  4. dealloc でまた使えるように

alloc, dealloc が $O(1)$

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

slab_{n}_bytes は単位が n byte

ex. メモリ領域 4kB のとき, slab_64_bytes は 64byte * 64個

FreeBlockList

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

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

core:alloc::alloc::Layout

pub struct Layout {
    // size of the requested block of memory, measured in bytes.
    size_: usize,

    // alignment of the requested block of memory, measured in bytes.
    // we ensure that this is always a power-of-two, because API's
    // like `posix_memalign` require it and it is a reasonable
    // constraint to impose on Layout constructors.
    //
    // (However, we do not analogously require `align >= sizeof(void*)`,
    //  even though that is *also* a requirement of `posix_memalign`.)
    align_: NonZeroUsize,
}

Layout から適切な Slabサイズを選ぶ

Optionは倍の容量使う

RustでOption型のサイズを調べた - Qiita Option型とNull Pointer Optimization - yohhoyの日記

  • null pointer optimization

  • だからといって2倍にする必要はないのでは, 1bitでよさそう

    • 理由はわからない

  • Cでは malloc は stdlib.h

Buddy Allocator

#todo 分割がより細やか?

core::alloc と alloc::alloc どう違う?

![[20220306124915.png]]

extern

editio2018以降では基本的に必要ないが, 例外

どう対応すべきか - Rustで独自のスライス型を定義する本

edition 2018 であっても、 alloc のためには extern crate alloc; と書かなければならない。 いずれ改善されることを期待したい。 std 環境では use なしに String や Vec 等が使えているが、これは std::prelude::v1 内のアイテムが自動で探索されることになっているからである。 しかし no_std な alloc 環境では、 prelude が使えない1。 このままではj, alloc と std でできることはほとんど同じなのに std から use するか alloc から use するか書き分けが必要になってしまい、不便である。 これを解決するのが #[cfg(feature = "alloc")] extern crate alloc; である。 「alloc feature が有効化されているとき」というのが std が有効化されている場合も含むのがミソで、つまり std 環境でも同じ型がたとえば String (これは prelude 経由でアクセスできる std::string::String である) と alloc::string::String の2種類の名前で使えるようになるのである。 2種類のうち alloc 環境で使える方を std 環境でも常に使ってやることにすれば、 (Error トレイト以外では) 書き分けの必要がなくなる。

UnsafeCell

get(): *mut T

Cell, RefCell, UnsafeCellの違いとその使い分け - Qiita

printしないと何が起きているかわからない

-> syscall で

init_heap() したいけどheapの場所がわからない

-> std でプログラムから領域を得る方法ないのか

misc

  • ssh, authorized_keys に pk おいて, sk 配って ngrok すればssh出来る

参考文献