Closed7

runtime/malloc.goを読む

nasanasa

まずは概要

まずはgolangのアロケーターの概要がまとまっているコメントを読んでいこう。

https://github.com/golang/go/blob/ab9d31da9e088a271e656120a3d99cd3b1103ab6/src/runtime/malloc.go#L1..L99

tcmallocをベースにしていたが、結構分岐したらしい。

メインアロケーターはページ単位で動く。
感想: メイン以外があるのか?1ページは8KiBだった気がする。設定値によるのかな

32KiBまでは小さなアロケーションサイズに分類され、67個のサイズに分類される(12byte割当だったら16byteサイズクラスに割り当てられる)

サイズクラスの種類についてはこちらを参照

https://github.com/golang/go/blob/ab9d31da9e088a271e656120a3d99cd3b1103ab6/src/runtime/sizeclasses.go#L6-L20

それぞれのサイズクラスは、そのサイズのオブジェクトのフリーセット(?)を持っているらしい
よく分からなかったが、使われていないメモリ(free)の集合(set)という理解でいいのかな〜。とりあえずこの理解で読み進めてみる。

メモリの空きページはサイズクラスのオブジェクトに分割されるらしい。サイズクラスの一覧からも1ページ1サイズクラスではないように見える。1~Nページでサイズクラスが構成されるはず

構造

次の6つから構成される。

https://github.com/golang/go/blob/ab9d31da9e088a271e656120a3d99cd3b1103ab6/src/runtime/malloc.go#L19-L25

  • fixalloc: 固定サイズのアロケーター。使用箇所を見るとmheapの中なのでgolangアロケーターのためのアロケーターに見える
  • mheap: ヒープメモリ。ページ単位で管理される(8KiB)
  • mspan: ちょっとよく分からず
  • mcentral: よく分からず。spanが集まる場所なんかな?
  • mcache: Pごとに持っているキャッシュ(Pは論理プロセッサーだが、OSスレッドと読み替えて問題ないはず。goroutineではなくOSスレッドであることに注意)
  • mstats: メモリの統計情報

軽くtcmallocについて調べたときの知識を組み合わせると、次のような関係になると予想できる。果たしてこの通りなのか?(とにかくspanがなにか分かっていないのでそのあたり知りたい)

画像を見るにspanはオブジェクトのフリーリストと呼んでいたものかな

mspan
ref: https://deepu.tech/memory-management-in-golang/

スモールオブジェクト(32KiBまで)の割当

  1. サイズクラスに切り上げて、Pのmcacheのmspanを探す。mspanの空きビットマップを走査し空いているところを探す。あったら確保する。Pごとにこれらは行われるのでロック無しでメモリ確保できるというのがポイント。
  2. mspanに空きがないとき。新しいmspanをmcentralから取得する。mcentralは全体から触られるのでロックを伴う。このときmspan全体を取得するためロックのコストは少なくなるように設計されているらしい。
  3. mcentralのmspanが空の場合heapからページを得でmspanを作る
  4. mheapが足りないときはOSからページを取得する。多めに割り当ててOSとのやり取りコストを減らしてるらしい。

オブジェクトの解放

1の条件がよくわかってない。。

  1. mspanがmcacheに返される。
  2. mspanに割り当てられたオブジェクトがあるとき、オブジェクトはmcentralのfree listに返される。
  3. mspan内のオブジェクト全てが解放されたとき、mheapにmspanで使っていたページ返される。

ラージオブジェクトの割当(32KiBより上)

ラージオブジェクトはmcentral, mcacheを使わず、mheapでだけ行われる。

その他

needzeroという引数や構造体フィールドの説明があるが飛ばしてしまう。
また、仮想メモリのレイアウトについての話もあったが読み飛ばしてしまう。

ヒープはアリーナの集合で構成されるということだけ知っておくと良さそう。

nasanasa

アロケーターのコードは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
===============================================================================
nasanasa

メインを探す

どこから読んでいけばよく分からないのでアロケーターのエントリーポイントを探してみましょう。

次のように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)
  ...

https://github.com/golang/go/blob/ab9d31da9e088a271e656120a3d99cd3b1103ab6/src/runtime/slice.go#L103

makesliceのコードを見ていくとmallocgcを読んでいますね。

これがmallocgcのコードです。ここがアロケーターのエントリーポイントに見えますね。
(ビンゴ!)

https://github.com/golang/go/blob/ab9d31da9e088a271e656120a3d99cd3b1103ab6/src/runtime/malloc.go#L832-L839

nasanasa

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

サマリ

大きく分ける。

  1. 前処理
  2. アロケーション
  3. 後処理

アロケーションは3種類のアロケーターによって行われる。

Tiny allocator

要求されたメモリが16byte以下である、ポインタを含まないオブジェクトである(noscan)の時に使用される。

Small allocator

要求されたメモリが3KiB以下の時に使用される

Learge allocator

3KiBより大きい時に使用される。

nasanasa

tiny allocatorを読む

コメントがあるので先ほどと同じように概要を追っていく

https://github.com/golang/go/blob/ab9d31da9e088a271e656120a3d99cd3b1103ab6/src/runtime/malloc.go#L931-L937

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
nasanasa

余談。アライメントは次のように行われる

byte align
2 2
4 4
6 2
8 8
10 2
12 4
14 2
それ以外 アラインしない
nasanasa

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)
}
このスクラップは2023/01/28にクローズされました