runtime/malloc.goを読む
まずは概要
まずはgolangのアロケーターの概要がまとまっているコメントを読んでいこう。
tcmallocをベースにしていたが、結構分岐したらしい。
メインアロケーターはページ単位で動く。
感想: メイン以外があるのか?1ページは8KiBだった気がする。設定値によるのかな
32KiBまでは小さなアロケーションサイズに分類され、67個のサイズに分類される(12byte割当だったら16byteサイズクラスに割り当てられる)
サイズクラスの種類についてはこちらを参照
それぞれのサイズクラスは、そのサイズのオブジェクトのフリーセット(?)を持っているらしい
よく分からなかったが、使われていないメモリ(free)の集合(set)という理解でいいのかな〜。とりあえずこの理解で読み進めてみる。
メモリの空きページはサイズクラスのオブジェクトに分割されるらしい。サイズクラスの一覧からも1ページ1サイズクラスではないように見える。1~Nページでサイズクラスが構成されるはず
構造
次の6つから構成される。
- fixalloc: 固定サイズのアロケーター。使用箇所を見るとmheapの中なのでgolangアロケーターのためのアロケーターに見える
- mheap: ヒープメモリ。ページ単位で管理される(8KiB)
- mspan: ちょっとよく分からず
- mcentral: よく分からず。spanが集まる場所なんかな?
- mcache: Pごとに持っているキャッシュ(Pは論理プロセッサーだが、OSスレッドと読み替えて問題ないはず。goroutineではなくOSスレッドであることに注意)
- mstats: メモリの統計情報
軽くtcmallocについて調べたときの知識を組み合わせると、次のような関係になると予想できる。果たしてこの通りなのか?(とにかくspanがなにか分かっていないのでそのあたり知りたい)
画像を見るにspanはオブジェクトのフリーリストと呼んでいたものかな
ref: https://deepu.tech/memory-management-in-golang/
スモールオブジェクト(32KiBまで)の割当
- サイズクラスに切り上げて、Pのmcacheのmspanを探す。mspanの空きビットマップを走査し空いているところを探す。あったら確保する。Pごとにこれらは行われるのでロック無しでメモリ確保できるというのがポイント。
- mspanに空きがないとき。新しいmspanをmcentralから取得する。mcentralは全体から触られるのでロックを伴う。このときmspan全体を取得するためロックのコストは少なくなるように設計されているらしい。
- mcentralのmspanが空の場合heapからページを得でmspanを作る
- mheapが足りないときはOSからページを取得する。多めに割り当ててOSとのやり取りコストを減らしてるらしい。
オブジェクトの解放
1の条件がよくわかってない。。
- mspanがmcacheに返される。
- mspanに割り当てられたオブジェクトがあるとき、オブジェクトはmcentralのfree listに返される。
- mspan内のオブジェクト全てが解放されたとき、mheapにmspanで使っていたページ返される。
ラージオブジェクトの割当(32KiBより上)
ラージオブジェクトはmcentral, mcacheを使わず、mheapでだけ行われる。
その他
needzero
という引数や構造体フィールドの説明があるが飛ばしてしまう。
また、仮想メモリのレイアウトについての話もあったが読み飛ばしてしまう。
ヒープはアリーナの集合で構成されるということだけ知っておくと良さそう。
アロケーターのコードは4300行らしい。
詳細に入りすぎないようにまずざっくりと読んでいくぞい。
:) % tokei src/runtime/mheap.go src/runtime/mksizeclasses.go src/runtime/mfixalloc.go src/runtime/msize.go src/runtime/mcentral.go src/runtime/malloc.go
===============================================================================
Language Files Lines Code Comments Blanks
===============================================================================
Go 6 4345 2281 1655 409
===============================================================================
Total 6 4345 2281 1655 409
===============================================================================
メインを探す
どこから読んでいけばよく分からないのでアロケーターのエントリーポイントを探してみましょう。
次のようにsliceを使ってヒープに割当を行ってもらいましょう。
package main
import "fmt"
func main() {
a := make([]int64, 0, 0)
// 使ってない変数があるとコンパイルできないので仕方なく追加
// _ = aで行けるかと思ったけど最適化が働いてアロケーションされないのでprintする
fmt.Println(a)
}
↑のコードをコンパイルして出来たバイナリを逆アセンブルしてみましょう。
goコードに対応するアセンブラが分かりやすく表示されるのでありがたいですね。
$ go tool objdump -S ./alloc_playground
...
...
TEXT main.main(SB) /Users/asan/lab/sandbox/alloc_playground.go
func main() {
0x10008f910 f9400b81 MOVD 16(R28), R1
0x10008f914 910003e2 MOVD RSP, R2
0x10008f918 eb01005f CMP R1, R2
0x10008f91c 54000469 BLS 35(PC)
0x10008f920 f81a0ffe MOVD.W R30, -96(RSP)
0x10008f924 f81f83fd MOVD R29, -8(RSP)
0x10008f928 d10023fd SUB $8, RSP, R29
a := make([]int64, 0, 0)
0x10008f92c 90000140 ADRP 163840(PC), R0
0x10008f930 910a8000 ADD $672, R0, R0
0x10008f934 f90007e0 MOVD R0, 8(RSP)
0x10008f938 a9017fff STP (ZR, ZR), 16(RSP)
0x10008f93c 97fee37d CALL runtime.makeslice(SB)
0x10008f940 f94013e0 MOVD 32(RSP), R0
fmt.Println(a)
0x10008f944 f90007e0 MOVD R0, 8(RSP)
...
ここが完全に怪しいですね。makeslice
を見てみましょう
a := make([]int64, 0, 0)
...
0x10008f93c 97fee37d CALL runtime.makeslice(SB)
...
makeslice
のコードを見ていくとmallocgc
を読んでいますね。
これがmallocgc
のコードです。ここがアロケーターのエントリーポイントに見えますね。
(ビンゴ!)
mallocgcを読む
コードの細部を無視して全体の流れだけを見ていきましょう。
超大枠の処理の流れはコードとして残して、残りはすべてコメントで書きました。
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
// 設定値に応じた処理をなんかやってる
// 1. デバッグ用の処理
// 2. サニタイザーの設定
// ... コードは省略
// 前処理
// 1. GCに触られないようにロックを獲得する。
// 2. mcacheを得る
// ... コードは省略
// ポインタを宣言。このポインタが返り値となる
var x unsafe.Pointer
// ポインタを含まないオブジェクトの割当時に`noscan`がtrueになる
noscan := typ == nil || typ.ptrdata == 0
if size <= maxSmallSize {
if noscan && size < maxTinySize {
// Tiny allocatorが使われる
x = hoge
} else {
// なんやかんや割当が行われる
// small allocator
x = hoge
}
} else {
// large allocatorが使われる
x = hoge
}
if !noscan {
// heap bitmap(?)にオブジェクトを割り当てたりしてる
// ... コードは省略
}
// メモリバリアの設定を行っている関数。
// アセンブラで実装されている
publicationBarrier()
// サニタイザーやメモリプロファイラーの競合状態検知などの実行
// ... コードは省略
// 最初に確保したロックを解放する
releasem(mp)
// サニタイザーやメモリプロファイラーの競合状態検知の後処理?をしてるように見える
// ... コードは省略
// ポインタを返す
return x
}
次の3つに分けてみていけば良さそうですね
- tiny allocator
- smal allocator
- large allocator
サマリ
大きく分ける。
- 前処理
- アロケーション
- 後処理
アロケーションは3種類のアロケーターによって行われる。
Tiny allocator
要求されたメモリが16byte以下である、ポインタを含まないオブジェクトである(noscan)の時に使用される。
Small allocator
要求されたメモリが3KiB以下の時に使用される
Learge allocator
3KiBより大きい時に使用される。
tiny allocatorを読む
コメントがあるので先ほどと同じように概要を追っていく
Tiny allocatorは複数のアロケーション要求を1つのメモリブロックにまとめる。メモリブロックは、すべてのサブオブジェクト(?)が到達不可能になったときに解放される。
サブオブジェクトはnoscanで無ければならない。(noscanのときだけtiny allocatorが動作している)
2022/5/31時点メモリブロックサイズは16byteになっている。この値になっている理由はここでは省略します、詳しくはコードを参照してください
2, 2,4,8byteのメモリ要求があったときに、これは16byteのメモリブロックにまとめられるみたいですね。
4,8,8の順序でメモリ要求があったときにはどのような挙動をするんでしょうか?これら踏まえてコードを見てみましょう。
// メモリブロック(16byte)の内どこまでを使用しているか
off := c.tinyoffset
// アライメントをいい感じにしている
// 詳しくは http://www5d.biglobe.ne.jp/~noocyte/Programming/Alignment.html#WhatIsAlignment
if size&7 == 0 {
off = alignUp(off, 8)
} else if goarch.PtrSize == 4 && size == 12 {
// 32bitアーキテクチャのときに起きるバグ?があるらしい。
// これを防ぐために切り上げている
// https://github.com/golang/go/issues/37262
off = alignUp(off, 8)
} else if size&3 == 0 {
off = alignUp(off, 4)
} else if size&1 == 0 {
off = alignUp(off, 2)
}
// c.tinyはmemory blockの開始アドレスを指している
// 今回割り当てたいオブジェクトが現在扱っているmemory blocksに収まるなら割り当てる
if off+size <= maxTinySize && c.tiny != 0 {
// The object fits into existing tiny block.
x = unsafe.Pointer(c.tiny + off) // オブジェクトの開始アドレス
c.tinyoffset = off + size // offsetを更新しておく
c.tinyAllocs++ // 割り当てられたオブジェクトの数を1増やす
mp.mallocing = 0 // 割当状態から抜け
releasem(mp) // ロックを解放
return x
}
// memory block(span)はリスト構造になっている
// 現在のspanから次のspanを得る
span = c.alloc[tinySpanClass]
v := nextFreeFast(span)
if v == 0 {
// 次のspanがないときには作る。重めの処理になる可能性がある。
v, span, shouldhelpgc = c.nextFree(tinySpanClass)
}
x = unsafe.Pointer(v)
// 新しいmemory blockを0埋めしている
(*[2]uint64)(x)[0] = 0
(*[2]uint64)(x)[1] = 0
if !raceenabled && (size < c.tinyoffset || c.tiny == 0) {
c.tiny = uintptr(x)
c.tinyoffset = size
}
size = maxTinySize
余談。アライメントは次のように行われる
byte | align |
---|---|
2 | 2 |
4 | 4 |
6 | 2 |
8 | 8 |
10 | 2 |
12 | 4 |
14 | 2 |
それ以外 | アラインしない |
Small allocator
tiny allocatorと同じようなことをやっている。
tiny allocatorは16byte領域にオブジェクトを割り当てていたのに対して、small allocatorは要求されたメモリ量によって適したメモリブロックを使う所が異なっている。
このメモリブロックの計算法は省略する
// 最適なmemory block(span)長を求める
var sizeclass uint8
if size <= smallSizeMax-8 {
sizeclass = size_to_class8[divRoundUp(size, smallSizeDiv)]
} else {
sizeclass = size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]
}
size = uintptr(class_to_size[sizeclass])
spc := makeSpanClass(sizeclass, noscan)
// spanを得る
span = c.alloc[spc]
v := nextFreeFast(span)
if v == 0 {
v, span, shouldhelpgc = c.nextFree(spc)
}
x = unsafe.Pointer(v)
if needzero && span.needzero != 0 {
memclrNoHeapPointers(unsafe.Pointer(v), size)
}