rowlVM/GC ブロック・ページの管理

rowl

この論文
Compacting Garbage Collection with Ambiguous Roots
ではあらかじめ固定長のメモリブロックがあって個定数のページがあるような実装になっているので直します。
GHCのアロケータ実装を参考にしています。

まず、メモリはブロック単位(1Mbyte)でアロケートすることにします。
1ページは512バイトにします。

ページデスクリプタには

  • joined flag (前のページと連結しているかを表すフラグ。512バイトより大きいオブジェクトのアロケートに必要)
  • generation (Copy-GCにおける世代番号)
  • next (GC時にスキャン待ち行列に突っ込むので、そのためのポインタ)

が必要です。前者二つは1ワードにパックすることにして、２ワード(8バイト)必要です。
このページデスクリプタ(pd)の配列をブロックの先頭に配置します。

そうすると最大ページ数は(512+8)*N <= 1Mbyteより2016ページになります。末尾の1M - (512+8)*2016 = 256byteはもったいないですが、使用され
ません。

|<------------------ 1Mbyte --------------------------->|
|<--- 8*2016 byte --->|<------ 512*2016 byte ------>|
|pd0|pd1|pd2|...|pdN-1|page0|page1|page2|...|pageN-1|...|

ページアドレスの計算

各ブロックは1Mbyte境界に配置します。
すると
ページデスクリプタ(pd)のアドレスがpの場合、

p&~((1<<20)-1) == pdが属するブロックの先頭
p&((1<<11)-1) == pdのブロック先頭からのオフセット
(pdのオフセット)>>3 == pdの番号
ブロック先頭+8*2016+pdの番号*512 == ページのアドレス

となります。
これを整理して

ページのアドレス == p&~((1<<20)-1) + 16128 + (p&((1<<11)-1))<<6

となります。~((1<<20)-1)と((1<<11)-1)は定数なので見た目ほどステップ数はいりません。

オブジェクトが属するページの計算

オブジェクトのアドレスがpの場合
(p-8*2016)/512がページ番号になります。