(この記事はソフトウェアエンジニアの福井(@eyasy1217)が書きました)
この記事はspan末尾に入る、オブジェクトのポインタ情報であるheap bitsのレイアウトや、どのように読み書きされるかについて書いた記事です。

環境

各種閾値は今後のGoのバージョンで変わる可能性があります。またGreen Tea GCを考慮してない内容になります。

spanに入るheap bitsとは

GCはポインタを持つオブジェクトのポインタを探索します。heap bits(heap bitmaps)はこのオブジェクトのポインタがどこにあるかを、bitで記録するデータ構造です。

Goはヒープに入れる小オブジェクトをページ(8KiB)の連続(run) = spanで管理します。spanはオブジェクトのサイズごとにクラス(種類)があり、全部で67クラスあります。1つのspanに入るオブジェクトのサイズは全て同じになります。spanのサイズはクラスごとに異なり、例えば8Bのオブジェクトが入るspanのサイズは8192B(8KiB)になり、1408Bのオブジェクトの場合は16384B(16KiB)になります。(refs.)

ポインタを持つ小オブジェクトの中でも確保するサイズが512B以下の場合は、heap bitsをspan末尾の領域に入れます。

例えばこのstructは確保するサイズが32Bでありポインタを持つため、heap bitsをspan末尾領域に入れます。

type Node struct {
    val1  int   // 8B
    left  *Node // 8B
    val2  int   // 8B
    right *Node // 8B
}

GCはこのheap bitsを読んで、オブジェクトのポインタの位置を特定し探索します。

spanに入るheap bitsのレイアウト

heap bitsの処理はsrc/runtime/mbitmap.goにあります。

ポインターを含む型はGCDataという内部メタデータを持ちます。これは小さい型はポインターを1、通常のフィールド(スカラと呼ばれます)を0とするbitmap形式で、bitを並べた値です。
前のNode型は次のように10進数で10になります。

spanに入るheap bitsはこれをspan末尾領域に入れます。末尾領域のサイズはspanの1/64です。

32BのNodeオブジェクトが入る8192Bのspanクラス(refs.)では、128Bが末尾領域になります。つまり実際の値は(8192B -128B) / 8 = 1008ワード分入り、末尾領域には128Bのうち1008bit / 8 = 126B分が入ります。(ただGreen Tea GCだと末尾領域のサイズは変わってきます)

spanに入るheap bitsの書き込み

heap bitsをspanに書き込む処理はsrc/runtime/mbitmap.goのwriteHeapBitsSmall関数にあります。この関数は基本的に対象オブジェクトをheapに書き込むごとに呼ばれます。引数のxは書き込むオブジェクトのアドレス、dataTypeは書き込むオブジェクトのサイズです。

関数がやってることは

オブジェクトの型からGCDataの値を取得
span末尾領域を特定
末尾領域に書き込むbit位置の算出
heap bits書き込み

です。

それぞれの詳細を、Node型オブジェクトの書き込みを例に説明します。
先述の通り、このオブジェクトが入るspanクラスは4です。spanの先頭アドレスは0x14000092000、オブジェクトのアドレスは0x14000092020とします。

まず引数についてですが、
xは書き込むオブジェクトのアドレスになるため、

n := Node{val1: 1, left: &Node{val1: 2}, val2: 3, right: &Node{val1: 4}}
fmt.Printf("%p\n", &n)

で表示されるアドレスと同じになります。
dataTypeは先述の通り32になります。

1 オブジェクトの型からGCDataの値を取得
これは単に10を取得します。

2 span末尾領域を特定
spanHeapBitsRange関数を使ってspan末尾領域の先頭アドレスを取得します。
spanHeapBitsRange関数はspanのアドレスとspanのサイズ、spanの1スロットのサイズを使ってspan末尾領域の先頭アドレスを算出します。
ここではspanHeapBitsRange関数を呼ぶ際、spanのサイズは8192Bを固定で渡します。なぜならwriteHeapBitsSmall関数自体がオブジェクトが512B以下のspanでしか入り得なく、オブジェクトが512B以下のspanのサイズは全て8192Bになるためです。

3 末尾領域に書き込むbit位置の算出
spanHeapBitsRange関数を呼んだ後に、末尾領域に書き込むbit位置の算出します。
いくつか変数が出てくるので、それぞれの意味を説明します。

dst
span末尾領域の先頭アドレス
o
heap bitsを書き込むオブジェクトの位置を、spanの先頭アドレスから数えたワード数
i
末尾領域の何番目のワードから入るか
j
ワード内の書き込むheap bitsの開始位置です
bits
書き込むheap bitsのbit数

具体的な値で図にするとこのようになります。

4 heap bits書き込み
dst = (*dst)&^(((1<<bits)-1)<<j) | (src << j)の1行で書き込んでいます。
この式を分解するとこのようになります。

書き込むheap bitsがワードを跨ぐ場合はロジックが変わります。

spanに入るheap bitsの読み込み

読み込む処置はsrc/runtime/mgcmark.goのscanobject関数にあります。
heap bitsに関連する箇所の流れは

maskを取得
maskからスキャンするアドレスを算出
子ポインタのgrey化
子ポインタがなくなるまでループ

です。

1 maskを取得
scanobject関数の引数bは読み込むオブジェクトのアドレスが渡されます。
例だと0x14000092020になります。

typePointersOfUnchecked関数で≒ GCDataと同じ値を、structのmaskフィールドに入れて返します。
maskの取得はheapBitsSmallForAddr関数を呼びます。heapBitsSmallForAddr関数はまず初めに、書き込み時にも出てきたspanHeapBitsRange関数でspan末尾領域を特定した後に、書き込み時と同じようにbit位置を特定してmaskを返します。

2 maskからスキャンするアドレスを算出
maskの下位ビットから1を見つけ、それに対応するアドレスを算出します。nextFast関数でこれをやってます。
またtp.mask &= tp.mask - 1の式で、maskから見つけた1を0に書き戻します。