memory allocatorとやらを調べる
nasaGWだし全く知らない領域に触れてみたいね。
ということでmemory allocatorに触れていく。
ゴールはアロケーターの実装を見て行けるようになっていること。
Goのsrc/runtime/malloc.goとか読んでみようと思ったが、allocが何をしているかとかそもそも知らないので単純なアロケーターを実装しつつ雰囲気を掴みたい。
nasa最もシンプルらしい。とりあえずこれを見ていく
mallocで確保したメモリはfreeでOSに返される。
一体どこの誰だ、こんな嘘の解説を世に出したのはぁ！
なるほど。この記事ではOSからはメモリを確保せずにアロケーターを実装してく。
int memory[20];
このようなグローバル変数を切り盛りしメモリ管理を行っていく。
アロケーターの雰囲気がわかってよかった。
割当領域の先頭アドレスを返すことや、割り当てた領域を覚えておく必要があることなど分かった。
(当たり前のことではあるが、実際に配列をガチャガチャやっているコードを見ると理解が深まって良い)
これってグローバル変数を使っているので常にスタック領域のどこかを返すアロケーターになっている理解で良いのかな？プログラム実行開始時に確保したメモリ分しか使わない単純なものになっていると理解している。このときグローバル変数を使っている時点でメモリの動的確保は行えない認識だけどあってるのかしら
nasaせっかくなので簡単なものを実装してみたい。
これを見つつもうちょい理解を深めよう。
Rustの話になるが、GlobalAllocトレイトを実装したものを登録すると自分で実装したアロケーターを使えるみたい。
これで色々と実装して遊んでみよう。
この記事には次の3つのアロケーターが出てくる
- Bump allocator
- LinkedList allocator
- Fixed-Size Block Allocator
これを見つつ簡素なアロケーターを書いてみる
nasa公式のサンプルのほうが参考になったかも
サンプルと、Writing a OS in rustを見ながら超シンプルなアロケーターを書いてみた。
最初に配列を確保して、これを切り盛りした。
メモリの解放はまだない
use core::alloc::{GlobalAlloc, Layout};
use std::{
cell::UnsafeCell,
sync::atomic::{AtomicUsize, Ordering},
};
const MEM_SIZE: usize = 64 * 1024;
#[global_allocator]
static ALLOCATOR: BumpAllocator = BumpAllocator {
mem: UnsafeCell::new([0u8; MEM_SIZE]),
next: AtomicUsize::new(0),
allocations: AtomicUsize::new(0),
};
fn main() {
let s1 = format!("allocating a string1");
let s2 = format!("allocating a string2");
let _v: Vec<usize> = vec![];
println!("{s1}");
println!("{s2}");
// 要素があるとき`bus error`になる
// なんでだろう
// let _v: Vec<usize> = vec![1, 2, 3];
}
struct BumpAllocator {
mem: UnsafeCell<[u8; MEM_SIZE]>,
next: AtomicUsize,
allocations: AtomicUsize,
}
unsafe impl Sync for BumpAllocator {}
unsafe impl GlobalAlloc for BumpAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
let next = self.next.load(Ordering::SeqCst);
self.allocations.fetch_add(1, Ordering::SeqCst);
self.next.fetch_add(layout.size(), Ordering::SeqCst);
(self.mem.get() as *mut u8).add(next)
}
unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
// do not something
}
}
アライメントを気にしていなかったのでvecやBoxを使ったらバグっていた。。。
のでいい感じになるようにアライメント補正をかけてあげるようにした。
これで動くようになったので嬉しい！
アライメントについては正直良く分かっていない。なんで切りよくしてあげないといけないんだろうか
pub const MEM_SIZE: usize = 128 * 1024;
pub struct BumpAllocator {
pub(crate) mem: UnsafeCell<[u8; MEM_SIZE]>,
pub(crate) next: AtomicUsize,
}
unsafe impl Sync for BumpAllocator {}
unsafe impl GlobalAlloc for BumpAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
let next = self.next.load(Ordering::SeqCst);
let res = (self.mem.get() as *mut u8).add(next);
let align = layout.align();
let size = layout.size();
self.next
.fetch_update(Ordering::SeqCst, Ordering::SeqCst, |mut next| {
next += size;
Some(alignment_correction(next, align))
})
.unwrap();
res
}
unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
// do not something
}
}
fn alignment_correction(size: usize, align: usize) -> usize {
(size + align - 1) & !(align - 1)
}
Go Memory Allocatorを最初から作成するためのビジュアルガイド
メモリアロケーターがメモリを確保する流れ
仮想アドレスの話は省く。
メモリは物理アドレスと仮想アドレスがあるよねーという話をしてただけ。
プログラムが今より多くのヒープメモリを要求する可能性は高い。このときどうなるか。
アロケーターはbrkシステムコールを実行する。
brkは次のようなインタフェースになっている。このシステムコールはヒープ領域のbrkアドレス(ヒープ領域の境界となるアドレスのこと)を指定したアドレスに変更するために使う。
int brk(void * end_data_segment );
このシステムコールによってヒープ領域を増やす。(明言されてないけど減らすこともできそう？)
他にもsbrkやmmapというシステムコールでヒープメモリを増やすらしい。
注意点として、ｋのときページ割当はされない。物理メモリに変化はなく仮想メモリだけが増える。
余談
うろ覚えだけど、ページ割当はOSのページフォールトハンドラで行われたはず。
仮想メモリにアクセスした際にページフォールトが発生する。このとき初めてページ割当が行われアクセスできるようになるという認識。
メモリアロケーター
十分ヒープがあればアロケーターはカーネルに頼らなくて良くなる。
- 割当速度
- 断片化の削減
これら2つが重要らしい。
TCMallocがいい感じに頑張っているのでこれを見ていく。(スレッドキャッシュmallocというらしい)
TCMalloc(といいつつかなり派生したものらしい)
次の2つでメモリ管理してるっぽい。
- スレッドメモリ
- ページヒープ
nasaGoにおけるメモリ管理の可視化
こっちのが分かりやすそう。こっちに切り替えるか。
spanとmcentralという概念が出てきた。
1ページ(8KiB)を分割してクラスのブロックを作る。
次のように1ページは1種類のクラスブロックに分割される。
ex. 1ページを分割して8byteクラスのブロックを1024個作る。 8 * 1024 = 8Kib
ex. 1ページを分割して48byteクラスのブロックを170個作る。 48 * 170 = 8Kib
クラスブロックは67種類のものが予め決められている。ここでは省略
こうしてみると8KiB(1ページ)を超えるものもある。spanは複数ページにまたがって構成されるよう。
これらspanはmcentralによって管理される。
8bの要求があった際に8b spanがあれば返すし、なければ作ってくれる。
ページ要求はmheapにたいして行っている。
次のような構造になっている。
mcentralは複数のspanを管理するもの。
8byteクラスであれば1024個のspanがあるはず。(メモリブロックをspanと呼ぶか、メモリブロックの塊をspanと呼ぶかよく分かってない。)
threadから8byteのメモリ要求があった際にspanがmcentralからmcacheに割り当てられる。
このスライドが分かりやすかった