はじめに

前回の PartitionAlloc の記事に続いて、PartitionAlloc と双璧をなす Chromium のメモリ管理 Oilpan について紹介します。

本文中に出てくるデバッガーコマンドは、以下のエクステンションに含まれています。

GitHub - msmania/chromium-debug: Debugger extension for Chromium
https://github.com/msmania/chromium-debug

Oilpan 概要

Chromium プロジェクト公式のページはこちらです。

Blink GC Design
https://chromium.googlesource.com/chromium/src.git/+/master/third_party/blink/renderer/platform/heap/BlinkGCDesign.md

Oilpan は単なるヒープマネージャーではなく、ガベージコレクターでもあります。C++ で書かれているものの、マクロやテンプレートを華麗に組み合わせることで C++ でも GC してくれます。つまり、Oilpan で確保した領域を指すポインターは使ったまま放置しておけば OK です。むしろ delete を使ってはいけません。

具体例を見てみましょう。Oilpan を使うオブジェクトには、DOM ツリーノード、CSS (の値を保持する) オブジェクト、ハッシュテーブルなどがあります。このうち DOM ノードは、基底クラスである blink::Node の new 演算子が以下のようにオーバーロードされているため、Oilpan から領域が確保されるようになっています。解放は Oilpan がほぼ自動的にやってくれるので、delete 演算子はオーバーロードされていません。

  void* operator new(size_t size) { return AllocateObject(size, false); }
  static void* AllocateObject(size_t size, bool is_eager) {
    ThreadState* state =
        ThreadStateFor<ThreadingTrait<Node>::kAffinity>::GetState();
    const char* type_name = "blink::Node";
    return state->Heap().AllocateOnArenaIndex(
        state, size,
        is_eager ? BlinkGC::kEagerSweepArenaIndex : BlinkGC::kNodeArenaIndex,
        GCInfoTrait<EventTarget>::Index(), type_name);
  }

上述の公式デザインドキュメントに書かれている通り、Oilpan の GC はマーク & スイープ方式です。すなわち、適当なタイミングで Stop-The-World してアプリケーションの動作を止め、ルートオブジェクトのリストから辿っていけるオブジェクトをマークし、マークされなかったオブジェクトを解放する、という処理が継続的に実行されます。

PartitionAlloc における Partition のように、Oilpan には Arena という単位があり、Arena はオブジェクトの種類毎に分離されています。したがって、例えば DOM ノードと CSS オブジェクトがメモリ上で隣接することはありません。GC である Oilpan では理論的に UAF は発生しないはずなので、Arena を設ける目的はセキュリティの観点ではなく、メモリ断片化の抑制やメモリキャッシュ率の向上といったパフォーマンスの観点からの工夫と考えられます。さらに、Arena はスレッド毎に存在するため、メモリを確保するときの排他制御が不要である点もパフォーマンスの向上に貢献しています。

本記事は、Oilpan のヒープ管理としての側面に重点をおいています。マーク & スイープ周りの GC 関連の処理はその複雑さのため完全解明するに至っていません。その都度書き足す予定です（と言って更新しないパターンのやつや・・）。

Oilpan の管理単位

ThreadState, ThreadHeap

Oilpan の各データは、スレッド毎に存在する ThreadState という構造体から始まります。デバッガー上でメイン UI スレッドの ThreadState 構造体を取得できるようにコマンドを作りました。このコマンドは、グローバル変数の chrome_child!blink::ThreadState::main_thread_state_storage_ を見ているだけです。

0:000> !ts
Target Engine = 67.3396

MainThreadState() = chrome_child!blink::ThreadState::main_thread_state_storage_
chrome_child!blink::ThreadState 00007ffe`1b828f10
chrome_child!blink::ThreadHeap 00000187`f28f40d0
chrome_child!blink::PersistentRegion 0000668e`a6c04020

もしメイン UI 以外の ThreadState が知りたい場合、static メンバーとして定義されている chrome_child!blink::ThreadState::thread_specific_ から辿ります。thread_specific_ そのものはスレッドローカルではなくグローバルで、以下の構造を持っています。

0:000> dt chrome_child!WTF::ThreadSpecific<blink::ThreadState *>
   +0x000 main_thread_storage_ : Ptr64 Ptr64 blink::ThreadState
   +0x008 slot_            : base::ThreadLocalStorage::Slot

メイン UI 用のインスタンスだけ特別なメンバーとして main_thread_storage_ というポインターのポインターで保持されています。これを辿ると

0:000> x chrome_child!blink::ThreadState::thread_specific_
00007ffe`1b828f08 chrome_child!blink::ThreadState::thread_specific_ = <no type information>
0:000> dq 00007ffe`1b828f08 l2
00007ffe`1b828f08  0000668e`a6c04010 00000187`f28f40d0
0:000> dq 0000668e`a6c04010 l1
0000668e`a6c04010  0000668e`a6c18008
0:000> dq 0000668e`a6c18008 l1
0000668e`a6c18008  00007ffe`1b828f10

!ts コマンドで出力された 00007ffe`1b828f10 が出てきました。メインスレッド以外の ThreadState は、自前のラッパークラスを使って TLS から引っ張ってくるようですが、そこから先は調べていないのでパス。

ThreadState は、heap_ というメンバーとして ThreadHeap という構造体を保持しており、ThreadHeap は arenas_ というメンバーとして Arena の配列を保持しています。!ts コマンドで得られた ThreadHeap のアドレスに対して !heap コマンドを実行すると、Arena の一覧が得られます。

0:000> !heap 00000187`f28f40d0
arenas:
  0 blink::NormalPageArena 0000668e`a6c44000
  1 blink::NormalPageArena 0000668e`a6c440e0
  2 blink::NormalPageArena 0000668e`a6c441c0
  3 blink::NormalPageArena 0000668e`a6c442a0
  4 blink::NormalPageArena 0000668e`a6c44380
  5 blink::NormalPageArena 0000668e`a6c44460
  6 blink::NormalPageArena 0000668e`a6c44540
  7 blink::NormalPageArena 0000668e`a6c44620
  8 blink::NormalPageArena 0000668e`a6c44700
  9 blink::NormalPageArena 0000668e`a6c447e0
 10 blink::NormalPageArena 0000668e`a6c448c0
 11 blink::NormalPageArena 0000668e`a6c449a0
 12 blink::NormalPageArena 0000668e`a6c44a80
 13 blink::LargeObjectArena 0000668e`a6c4c000
free page pool entries:
  0 blink::PagePool::PoolEntry 0000668e`a6c04310 6
  1 blink::PagePool::PoolEntry 0000668e`a6c04230 1
  2 blink::PagePool::PoolEntry 0000668e`a748aaa0 5
  3 blink::PagePool::PoolEntry 0000668e`a748a840 6
  4 blink::PagePool::PoolEntry 0000668e`a748a890 7
  5 blink::PagePool::PoolEntry 0000668e`a7598280 8
  6 blink::PagePool::PoolEntry 0000668e`a759a9a0 9
  7 blink::PagePool::PoolEntry 0000668e`a7598610 8
  8 blink::PagePool::PoolEntry 0000668e`a7599880 9
  9 blink::PagePool::PoolEntry 0000668e`a6c045c0 9
 10 blink::PagePool::PoolEntry 0000668e`a75998e0 19
 11 blink::PagePool::PoolEntry 0000668e`a748a980 8
 12 blink::PagePool::PoolEntry 0000668e`a6c047c0 7
region tree:
 00007cc3`f8f60000
  00006c00`54d20000
   00001091`b9da0000
    00000699`3d840000
     00000142`d5500000
...
   00007189`f8d00000
    000074fa`ac420000
     00007c53`e4fa0000
  00007ff6`29ee0000

Arena

Oilpan では、メモリは Arena という構造から確保します。現時点で Arena の数は 14 と定められており、14 という数字は以下に示す ArenaIndices という列挙型で定義されます。FOR_EACH_TYPED_ARENA(TypedArenaEnumName) の部分からプリプロセッサーマジックでkNodeArenaIndex と kCSSValueArenaIndex という 2 つのラベルが生成され、kNumberOfArenas が 14 になります。

  enum ArenaIndices {
    kEagerSweepArenaIndex = 0,
    kNormalPage1ArenaIndex,
    kNormalPage2ArenaIndex,
    kNormalPage3ArenaIndex,
    kNormalPage4ArenaIndex,
    kVector1ArenaIndex,
    kVector2ArenaIndex,
    kVector3ArenaIndex,
    kVector4ArenaIndex,
    kInlineVectorArenaIndex,
    kHashTableArenaIndex,
    FOR_EACH_TYPED_ARENA(TypedArenaEnumName) kLargeObjectArenaIndex,
    // Values used for iteration of heap segments.
    kNumberOfArenas,
  };

Arena の配列の実体は chrome_child!blink::ThreadHeap::arenas_ であり、静的配列です。PartitionAlloc では、サイズによって自動的に Bucket が選ばれていましたが、オブジェクトの種類に応じた Arena を自動的に選ぶことはできないため、Oilpan でメモリを確保するためには、配列のインデックスを明示して Arena を選択する必要があります。冒頭で引用した DOM ノード確保部分では is_eager ? BlinkGC::kEagerSweepArenaIndex : BlinkGC::kNodeArenaIndex という式で Arena のインデックスを指定しています。

オブジェクトの種類に関わらず、一定以上の大きさのオブジェクトは LargeObjectArena という特別な Arena で管理します。LargeObjectArena は Arena 配列の末尾に配置され、インデックスは 13 です。PartitionAlloc で言うところの Direct Map に似ています。

BlinkPage, Region

Oilpan が管理するメモリも、元を辿れば OS の API 経由で提供されます。Windows の場合は VirtualAlloc です。

Arena は、BlinkPage と呼ばれる単位でメモリリソースを管理しており、BlinkPage のサイズは 2^17 = 128KB です。ただし、OS からは 10 個分の BlinkPage をまとめた 1280KB の Region というサイズで予約し、これを 10 個の BlinkPage に切って使います。PartitionAlloc の Super page と類似する構造で、メモリ断片化の抑制や、TLB 効率をよくするための工夫でしょう。

BlinkPage 128KB のうち、最初と最後のメモリページ 4K は Guard Page としてコミットせずに保持しておき、先頭の Guard Page の直後に BlinkPage 自身のメタ情報を配置します。メタ情報は二種類あり、NormakArena 用の blink::NormalPage、LargeObjectArena 用のblink::LargeObjectPage です。

メタ情報直後から末尾の GuardPage までの領域が、Oilpan のヒープメモリとして使われる部分です。領域サイズが固定されていた PartitionAlloc の Bucket とは異なり、各 Arena は様々なサイズの領域を管理するため、切り出された領域それぞれにメタ情報が必要です。このメタ情報には、領域サイズの他、マーク & スイープ時のマーキング情報も含まれます。メタ情報は構造体で言うと blink::HeapObjectHeader です。

BlinkPage のレイアウトを図示しました。

メモリ確保処理

Oilpan の管理単位、ThreadState, ThreadHeap, Arena, Region, BlinkPage について説明しました。メモリの確保処理において特に重要なのは Arena と BlinkPage です。前述の通り、メモリを確保するときには、配列のインデックスを指定して特定の Arena に対して要求を出します。その後 Arena がどのように BlinkPage を使ってメモリを確保するのかを説明します。コード上で言うと、確保処理は blink::NormalPageArena::AllocateObject から始まります。

デバッガーで Arena の情報をダンプすると以下のような出力が得られます。Arena は複数の BlinkPage をリソースとして保持しており、それが上記出力の active pages: セクションで表示されている部分です。具体的にはblink::NormalPageArena::first_page_ をヘッドとするリンクトリストです。

0:000> !arena 0000668e`a6c44000
blink::NormalPageArena 0000668e`a6c44000
blink::ThreadHeap 00000187`f28f40d0 Arena#0
current_allocation_point       00006b3e`fcdaef28
remaining_allocation_size      28688
last_remaining_allocation_size 83712
active pages:
blink::NormalPage 00006b3e`fcda1000 [00006b3e`fcda1838-00006b3e`fcdbf000] #
blink::NormalPage 00006b3e`fcdc1000 [00006b3e`fcdc1838-00006b3e`fcddf000]
blink::NormalPage 00006b3e`fcde1000 [00006b3e`fcde1838-00006b3e`fcdff000]
blink::NormalPage 00006b3e`fccc1000 [00006b3e`fccc1838-00006b3e`fccdf000]
unswept pages:
free chunks:
  4 00006b3e`fccd1e40 16
  7 00006b3e`fcdb5fd8 184 00006b3e`fcde9b10 184 00006b3e`fccd02c8 160 00006b3e`fccc27e8 160
  8 00006b3e`fcdeb4c8 504 00006b3e`fcdeb0f0 344 00006b3e`fcde9890 480 00006b3e`fcde5da8 448
    00006b3e`fccda030 312 00006b3e`fccc2670 264
  9 00006b3e`fcdeb800 824 00006b3e`fcde9c68 800 00006b3e`fcde7970 768 00006b3e`fccd0f88 800
    00006b3e`fccd0bf0 608 00006b3e`fccc4cc0 936
 10 00006b3e`fcdea860 1584 00006b3e`fcdea168 1144 00006b3e`fcde5880 1160 00006b3e`fccc3f68 1544
    00006b3e`fccc1900 1720
 11 00006b3e`fcdb6130 3776 00006b3e`fccd1ef0 3192 00006b3e`fccc29c8 3712
 12 00006b3e`fcdc1838 4760 00006b3e`fcde7d10 6880 00006b3e`fcde6310 5568 00006b3e`fcde3180 5376
    00006b3e`fcde1838 6160 00006b3e`fccc5680 8136
 13 00006b3e`fccd77c8 8800
 14 00006b3e`fcdb7110 32496 00006b3e`fccda3c8 19512 00006b3e`fccd2ca8 17600 00006b3e`fccc8758 31440
 15 00006b3e`fcdd55f8 39432 00006b3e`fcdf4090 44912 00006b3e`fcdebdb8 33336
 16 00006b3e`fcdc2b70 76264

Fast path

Fast path では、Arena 内で保持されている current_allocation_point と remaining_allocation_size という値を使います。上記出力における 00006b3e`fcdaef28 と 28688 です。

Oilpanは、保持する BlinkPage の中に要求されたサイズを確保できる空き領域があるかどうかを逐一把握していません。その代わり、current_allocation_point は active pages の中の領域のどこかを指しており、そのアドレスを開始地点として remaining_allocation_size のサイズの分だけは空き領域があることが分かっています。

もし要求されたサイズが remaining_allocation_size 以下であれば、current_allocation_point から要求されたサイズ分だけ領域を切り出して要求元に返し、次の Fast path でも使えるように current_allocation_point と remaining_allocation_size を更新します。これが Fast path で、数回の加減算で済んでしまうため計算量は余裕で O(1) です。実装箇所は NormalPageArena::AllocateObject です。

Slow path 1

要求されたサイズが remaining_allocation_size よりも大きかった場合、current_allocation_point の情報を利用することはできません。次いで使う情報は、上記デバッガー出力における free chunks: です。これは、Arena の管理する BlinkPage の中に存在する空き領域をリンクトリストの形式で保持したものです。コードでいうと blink::NormalPageArena::free_list_ です。

空き領域は、1 つのリンクトリストでまとめて管理するのではなく、サイズ毎にグループ化されています。具体的には 17 個のリンクトリストが用意されており、x 番目のリストが $[2^x, 2^{x+1})$ の範囲に収まるサイズの空き領域を保持しています。

free_list から領域を確保する場合、サイズの大きいグループから小さいグループに向って、各リストの先頭要素のみを順に探索します。もし要求サイズが収まるサイズの空き領域が見つかれば、その領域を free_list から外し、空き領域を切り出し、残りの領域を current_allocation_point と remaining_allocation_size として保存します。これで次回は Fast path が使えます。

サイズの大きいグループから探索する理由は、なるべく大きい領域を current_allocation_point に置いて、Fast path をできるだけ長く使えるようにする工夫だと思います。各リンクトリストの先頭要素だけをチェックするため、もし、リストの 2 番目の空き領域の方が先頭要素の空き領域より大きかったとしても、使うのは先頭要素です。Fast path をできるだけ長く使いたいという意味ではリスト内の最大の空き領域を使いたいところですが、リストの長さが不定であるため、探索パフォーマンスがリストの長さに依存してしまうのは危険です。リストの先頭だけをチェックするのであれば、探索は最長でも配列長に等しい 17 回に限られるため、計算量は O(1) で済みます。こういう細かいテクニックがいちいち憎いです。

Slow path 2

current_allocation_point に十分な容量がなく、free_list 各リストの先頭にちょうどいい空き領域がなかった場合でも、リストを探索することはしません。次にやることは BlinkPage を新たに用意することです。

各 Arena は、予約済みでコミットされていない BlinkPage を PagePool というリンクトリストとして保持しています。具体的には、chrome_child!blink::ThreadHeap::free_page_pool_ が要素数 14 の blink::PagePool::PoolEntry 型の配列を保持しており、その配列の各要素が各 Arena の保持する PagePool に対応します。上記 !heap 出力の以下の部分がそのリンクトリストの先頭要素です。

free page pool entries:
  0 blink::PagePool::PoolEntry 0000668e`a6c04310 6
  1 blink::PagePool::PoolEntry 0000668e`a6c04230 1
  2 blink::PagePool::PoolEntry 0000668e`a748aaa0 5
  3 blink::PagePool::PoolEntry 0000668e`a748a840 6
  4 blink::PagePool::PoolEntry 0000668e`a748a890 7
  5 blink::PagePool::PoolEntry 0000668e`a7598280 8
  6 blink::PagePool::PoolEntry 0000668e`a759a9a0 9
  7 blink::PagePool::PoolEntry 0000668e`a7598610 8
  8 blink::PagePool::PoolEntry 0000668e`a7599880 9
  9 blink::PagePool::PoolEntry 0000668e`a6c045c0 9
 10 blink::PagePool::PoolEntry 0000668e`a75998e0 19
 11 blink::PagePool::PoolEntry 0000668e`a748a980 8
 12 blink::PagePool::PoolEntry 0000668e`a6c047c0 7

DOM ノードを保持するのが Arena#10 だったので、PoolEntry#10 は DOM ノード用に使われます。!pool を使ってリンクトリストの各要素を確認できます。

0:000> !pool 0000668e`a75998e0
blink::PagePool::PoolEntry chain:
0000668e`a75998e0 000074fa`ac420000 #0 000074fa`ac421000 122880
0000668e`a75999e0 000010c2`56120000 #4 000010c2`561a1000 122880
0000668e`a7598270 000010c2`56120000 #3 000010c2`56181000 122880
0000668e`a759a980 000074fa`ac420000 #9 000074fa`ac541000 122880
0000668e`a7489b10 000074fa`ac420000 #2 000074fa`ac461000 122880
0000668e`a7489b20 000010c2`56120000 #0 000010c2`56121000 122880
0000668e`a748aa00 000010c2`56120000 #7 000010c2`56201000 122880
0000668e`a748a8f0 000010c2`56120000 #5 000010c2`561c1000 122880
0000668e`a748a9e0 000010c2`56120000 #1 000010c2`56141000 122880
0000668e`a748a9d0 00004f53`86020000 #0 00004f53`86021000 122880
0000668e`a748a870 00004f53`86020000 #9 00004f53`86141000 122880
0000668e`a748a730 00004f53`86020000 #8 00004f53`86121000 122880
0000668e`a748a720 00004f53`86020000 #7 00004f53`86101000 122880
0000668e`a748a760 00004f53`86020000 #6 00004f53`860e1000 122880
0000668e`a748a790 00004f53`86020000 #5 00004f53`860c1000 122880
0000668e`a748a780 00004f53`86020000 #4 00004f53`860a1000 122880
0000668e`a748a7c0 00004f53`86020000 #3 00004f53`86081000 122880
0000668e`a748a860 00004f53`86020000 #2 00004f53`86061000 122880
0000668e`a748a770 00004f53`86020000 #1 00004f53`86041000 122880

上記出力の状態で Arena#10 に BlinkPage を割り当てるとしたら、先頭の000074fa`ac421000 を PagePool の先頭から外し、BlinkPage のメタ情報を先頭に埋め、その直後のアドレスである000074fa`ac421838を Arena の free_list の末尾、すなわち 16 番目の要素に空き領域として追加します。なぜなら、NormalPage のサイズは 120KB で固定であり、メタ情報は 0x838 なので、PagePool から持ってきた領域で使える分は必ず 120 * 1024 - 0x838 = 120776 バイトになるからです。120776 は 2^16 = 65536 以上なので 16 番目の要素に入ります。

逆に言えば、NormalPageArena で確保できるのは 120776 が最大です。厳密には 120776 にはペイロードのメタ情報 8 バイトも含むので、120768 バイトが最大となり、120769 バイト以上の領域には LargePageArena が使われます。が、実際には NormalPageArena::OutOfLineAllocate の最初の条件 allocation_size >= kLargeObjectSizeThreshold が LargeObjectArena を使うかどうかを決める条件で、メタ情報を含めて 2^16 バイト以上の場合に LargeObjectArena が使われます。

ページプールが空だった場合は VirtualAlloc で Region を確保し、10 個の BlinkPage を PagePool に入れてから上記のロジックを実行します。PoolEntry を free_list に追加した後は、前回の Slow path 1 を実行できます。

メモリ解放処理 (マーク & スイープ)

Oilpan はガベージコレクターなので、メモリを使った側が解放処理を呼び出して領域を free_list に戻す、という処理は発生しません。適当なタイミングで Oilpan 自身がマーク & スイープ処理を実行し、未使用領域を free_list に返却しています。

マーク & スイープの動作については、冒頭で紹介した Blink GC Design に細かい処理まで記述されているので、それを基に動作を見ていきます。

マーク

デザインドキュメントの記述を引用します。

Step 2. The GCing thread waits for all other threads to enter safe points. A safe point is a place where it‘s guaranteed that the thread does not mutate the object graph of objects in Oilpan’s heap. In common cases the thread stops at the safe point but doesn‘t necessarily need to stop. For example, the thread is allowed to execute a synchronous IO at the safe point as long as it doesn’t mutate the object graph. Safe points are inserted into many places so that the thread can enter the safe point as soon as possible when the GCing thread requests the thread to do so. For example, safe points are inserted into V8 interruptors, at the end of event loops, before acquiring a mutex, before starting a synchronous IO operation etc.

例えば blink::ThreadState::SafePoint という関数があり、おそらくこれがイベントループの後に実行される safe point です。その他の safe point は確認できていません。というか V8 のコードを理解できない。力不足じゃ・・・。

ルートセット

ドキュメントの記述はこう続きます。

The marking phase (the step 3 in the above description) consists of the following steps. The marking phase is executed in a stop-the-world manner.
Step 3-1. The GCing thread marks all objects reachable from the root set by calling trace() methods defined on each object.
Step 3-2. The GCing thread clears out all trivial WeakMembers.

どうやって stop-the-world をしているかもよく分からなかったのでこれも飛ばすとして、マーキング処理は、Oilpan が管理しているルートセットと呼ばれるオブジェクト群から、オブジェクト毎に定義された trace() 関数を使って辿れるオブジェクト全てに印を付ける作業です。

ルートセットは以下 3 つの場所にあり、いずれも blink::PersistentRegion クラスで表されます。

blink::ThreadState::persistent_region_
blink::ProcessHeap::GetCrossThreadPersistentRegion 内の static 変数
blink::ProcessHeap::GetCrossThreadWeakPersistentRegion 内の static 変数

例えば以下の出力例では、0000668e`a6c04020、0000668e`a6c06390、0000668e`a704e610 がそれぞれ blink::PersistentRegion オブジェクトを指しています。

0:000> !ts 00007ffe`1b828f10
MainThreadState() = chrome_child!blink::ThreadState::main_thread_state_storage_
chrome_child!blink::ThreadState 00007ffe`1b828f10
chrome_child!blink::ThreadHeap 00000187`f28f40d0
chrome_child!blink::PersistentRegion 0000668e`a6c04020

0:000> x chrome_child!s_persistent_region
00007ffe`1b828ed0 chrome_child!s_persistent_region = class WTF::StaticSingleton<blink::CrossThreadPersistentRegion>
00007ffe`1b828ee0 chrome_child!s_persistent_region = class WTF::StaticSingleton<blink::CrossThreadPersistentRegion>

0:000> dq 00007ffe`1b828ed0 l1
00007ffe`1b828ed0  0000668e`a6c8acd8 <<<< 0000668e`a6c8acd8 = blink::CrossThreadPersistentRegion
0:000> dq 0000668e`a6c8acd8 l1
0000668e`a6c8acd8  0000668e`a6c06390

0:000> dq 00007ffe`1b828ee0 l1
00007ffe`1b828ee0  0000668e`a6c8ce18 <<<< 0000668e`a6c8acd8 = blink::CrossThreadPersistentRegion
0:000> dq 0000668e`a6c8ce18 l1
0000668e`a6c8ce18  0000668e`a704e610

blink::PersistentRegion は、256 個のオブジェクトを 1 スロットとして、各スロットをリンクトリストとして保持しています。!persistent コマンドで、PersistentRegion が保持するオブジェクトを全て出力できます。

0:000> !persistent 0000668e`a6c04020
slot#0 0000668e`a713f600
 113 0000668e`a6d2db50 00007ffe`1796528c 00006c00`54d27350 0000668e`a713fd18
 132 0000668e`a718cfc0 00007ffe`179652e0 00006c00`54dcbfa8 0000668e`a713fe48
 135 0000668e`a6d30bc8 00007ffe`1796528c 00006c00`54d27350 0000668e`a713fe78
...
 254 0000668e`a718b550 00007ffe`17b28b70 00001091`b9ea80e0 0000668e`a71405e8
 255 0000668e`a6d2ffc0 00007ffe`1796528c 00006c00`54d27350 0000668e`a71405f8
slot#1 0000668e`a7141a00
   0 00001c2f`ccb66660 00007ffe`17965050 00001c2f`ccb66628 0000668e`a7141a08
   1 0000668e`a72d2b50 00007ffe`17965380 00001091`b9df6540 0000668e`a7141a18
...
slot#7 0000668e`a6c9d200
   0 00007cc3`f8fca450 00007ffe`17965050 00007cc3`f8fca418 0000668e`a6c9d208
   1 00007cc3`f8fa87e0 00007ffe`17965050 00007cc3`f8fa87a8 0000668e`a6c9d218
...
 254 0000668e`a6ca8020 00007ffe`17689f10 00007cc3`f8f618c0 0000668e`a6c9e1e8
 255 0000668e`a6c04070 00007ffe`17965a24 00007cc3`f8f61840 0000668e`a6c9e1f8

上記出力の場合、ThreadState の PersistentRegion は 1000 を超えるオブジェクトが 7 スロットに渡って保存されています。Oilpan は、これら全てのオブジェクトに対して trace() 関数を実行します。デバッガー出力の各列の意味は、左から

スロット内のインデックス
chrome_child!blink::PersistentNodeSlots::slot_[x]::self_
chrome_child!blink::PersistentNodeSlots::slot_[x]::trace_
*(chrome_child!blink::PersistentNodeSlots::slot_[x]::self_)
*(chrome_child!blink::PersistentNodeSlots::slot_[x]::self_ + 1)

です。3 列目の値が Oilpan が直接呼び出す trace 関数のアドレスで、その関数を呼ぶときに第二引数として 2 列目の self_ の値が渡されます。オブジェクトの種類によって trace 関数が異なるため、self_ の使われ方も異なりますが、基本的には self_ のアドレスが指すアドレスがマーキング対象のオブジェクトのアドレスを示しています。すなわち !persistent 出力の 4 列目、上記例で言えば 00006c00`54d27350 などが Oilpan で確保されたオブジェクトです。

マークビット

マーキングとは、ペイロードヘッダー blink::HeapObjectHeader にある Mark bit という 1 ビットのフラグを立てる処理です。Mark bit は blink::HeapObjectHeader::encoded_ の最下位ビットです。ルートセット内のオブジェクトがマークされる瞬間を、アクセスブレークポイントで捕えてみます。

少し前に出てきた !persistent の出力の、最後のオブジェクト 00002293`35fe1840 で試します。PersistentRegion が管理するのはヘッダーを含まないオブジェクトの先頭なので、ペイロードヘッダーはそこから 8 バイト上流、すなわち 00002293`35fe1838 にあります。

0:005> !chunk 00002293`35fe1838
blink::NormalPage 00002293`35fe1000
Size:         104
GCinfo index: 1
Free:         N
Mark:         N
DOM mark:     N
0:005> dt blink::HeapObjectHeader 00002293`35fe1838
chrome_child!blink::HeapObjectHeader
   +0x000 magic_           : 0x6e0be9e6
   +0x004 encoded_         : 0x40068 
0:005> ba w4 00002293`35fe183c
0:005> g

encoded_ はヘッダー内のオフセット +4 の位置なので、そこにブレークポイントを置きました。ヒットを待ちます。

0:000> g
Breakpoint 0 hit
chrome_child!blink::Worklist<blink::MarkingItem,512,1>::View::Push [inlined in chrome_child!blink::MarkingVisitor::Visit+0xc4]:
0:000> ub .
chrome_child!blink::HeapObjectHeader::GetMagic+0x5 [C:\b\c\b\win64_clang\src\third_party\blink\renderer\platform\heap\marking_visitor.h @ 99] [inlined in chrome_child!blink::MarkingVisitor::Visit+0xad [C:\b\c\b\win64_clang\src\third_party\blink\renderer\platform\heap\marking_visitor.h @ 99]]:
00007ffd`757351cd 35ad6e0b6e      xor     eax,6E0B6EADh
00007ffd`757351d2 3b43f8          cmp     eax,dword ptr [rbx-8]
00007ffd`757351d5 754f            jne     chrome_child!blink::MarkingVisitor::Visit+0x106 (00007ffd`75735226)
00007ffd`757351d7 8b43fc          mov     eax,dword ptr [rbx-4]
00007ffd`757351da a801            test    al,1
00007ffd`757351dc 751d            jne     chrome_child!blink::MarkingVisitor::Visit+0xdb (00007ffd`757351fb)
00007ffd`757351de 83c801          or      eax,1
00007ffd`757351e1 8943fc          mov     dword ptr [rbx-4],eax
0:000>  r eax
eax=40069
0:000> bd*
0:000> bp 00007ffd`757351de

変更後の encoded_ の値を確かめると 0x40068 が 0x40069 になっているので、マークビットが on になったことが分かります。ブレークは、encoded_ を 32bit 整数として代入しているときにヒットするので、その少し前のマーキングビット立てている or 命令のところにブレークポイントを設定し直して再度ブレークを待ちます。

0:000> g
Breakpoint 1 hit
chrome_child!blink::HeapObjectHeader::TryMark+0x16 [inlined in chrome_child!blink::MarkingVisitor::Visit+0xbe]:
0:000> kL10
Child-SP          RetAddr           Call Site
(Inline Function) --------`-------- chrome_child!blink::HeapObjectHeader::TryMark+0x16
(Inline Function) --------`-------- chrome_child!blink::MarkingVisitor::MarkHeaderNoTracing+0x16
(Inline Function) --------`-------- chrome_child!blink::MarkingVisitor::MarkHeader+0x16
0000000a`393fd890 00007ffd`7573611d chrome_child!blink::MarkingVisitor::Visit+0xbe
(Inline Function) --------`-------- chrome_child!blink::Visitor::Trace+0x2a
0000000a`393fd8f0 00007ffd`7573605d chrome_child!blink::DOMWrapperTracer::VisitPersistentHandle+0x7d
(Inline Function) --------`-------- chrome_child!v8::internal::GlobalHandles::ApplyPersistentHandleVisitor+0x14
0000000a`393fd950 00007ffd`75735fbe chrome_child!v8::internal::GlobalHandles::IterateAllRootsWithClassIds+0x6d
0000000a`393fd9b0 00007ffd`75734eb8 chrome_child!blink::V8GCController::TraceDOMWrappers+0x2e
0000000a`393fd9f0 00007ffd`75734d5f chrome_child!blink::ThreadState::VisitPersistents+0x86
0000000a`393fdae0 00007ffd`75734c81 chrome_child!blink::ThreadHeap::VisitPersistentRoots+0x4d
0000000a`393fdbd0 00007ffd`75733e57 chrome_child!blink::ThreadState::MarkPhaseVisitRoots+0x35
0000000a`393fdc30 00007ffd`75733b82 chrome_child!blink::ThreadState::CollectGarbage+0x141
0000000a`393fdec0 00007ffd`75733a52 chrome_child!blink::ThreadState::PerformIdleGC+0x106
(Inline Function) --------`-------- chrome_child!base::OnceCallback<void (double)>::Run+0x14
0000000a`393fe010 00007ffd`757339f5 chrome_child!blink::scheduler::WebSchedulerImpl::RunIdleTask+0x46

上記コールスタックから、or 命令は blink::HeapObjectHeader::TryMark という関数内の処理で、この関数がルートオブジェクトの探索中 (blink::ThreadState::VisitPersistents) に呼ばれて、マーキングが行われていることが確認できました。

トレース

!persistent コマンドの出力から Trace() 関数のアドレスも得られるので、トレースが行われるタイミングもデバッガーで捕えることができます。

0:018> !ts
MainThreadState() = chrome_child!blink::ThreadState::main_thread_state_storage_
chrome_child!blink::ThreadState 00007ffd`795f8ed0
chrome_child!blink::ThreadHeap 000001a0`f17affd0
chrome_child!blink::PersistentRegion 000042a6`52804020
0:018> !persistent 000042a6`52804020
...
slot#7 000042a6`528ac000
 253 00007ffd`79752900 00007ffd`75735f20 00007301`f1623d28 00000001`00000008
 254 00007ffd`79752940 00007ffd`75735f20 00007301`f1623ce0 00000001`00000008
 255 000042a6`5289c020 00007ffd`75459f50 00002293`35fe1840 000042a6`528acff8

3 列目が関数のアドレスでした。00007ffd`75735f20 を選んでブレークポイントを設定します。

0:018> bp 00007ffd`75735f20
0:018> g
Breakpoint 0 hit
rax=0000000000000001 rbx=0000000000000000 rcx=000001a0f708d2d0
rdx=00007ffd79752900 rsi=00007ffd750ac8c0 rdi=000001a0f708d2d0
rip=00007ffd75735f20 rsp=0000000a393fdbc8 rbp=0000000000000000
 r8=0000000a393fdb40  r9=0000000a393fdba8 r10=00007ffd78b24150
r11=00000dcdc6134c00 r12=0000000000000000 r13=0000000000000000
r14=000042a6528ac008 r15=0000000000000fd0
iopl=0         nv up ei pl nz na pe nc
cs=0033  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00000202
chrome_child!blink::TraceMethodDelegate<blink::PersistentHeapCollectionBase<blink::HeapHashSet<blink::WeakMember<blink::Page>,WTF::MemberHash<blink::Page>,WTF::HashTraits<blink::WeakMember<blink::Page> > > >,&blink::PersistentHeapCollectionBase<blink::HeapHashSet<blink::WeakMember<blink::Page>, WTF::MemberHash<blink::Page>, WTF::HashTraits<blink::WeakMember<blink::Page> > > >::TracePersistent>::Trampoline:
00007ffd`75735f20 4883ec58        sub     rsp,58h
0:000> kL10
Child-SP          RetAddr           Call Site
0000000a`393fdbc8 00007ffd`75735026 chrome_child!blink::TraceMethodDelegate<blink::PersistentHeapCollectionBase<blink::HeapHashSet<blink::WeakMember<blink::Page>,WTF::MemberHash<blink::Page>,WTF::HashTraits<blink::WeakMember<blink::Page> > > >,&blink::PersistentHeapCollectionBase<blink::HeapHashSet<blink::WeakMember<blink::Page>, WTF::MemberHash<blink::Page>, WTF::HashTraits<blink::WeakMember<blink::Page> > > >::TracePersistent>::Trampoline
(Inline Function) --------`-------- chrome_child!blink::PersistentNode::TracePersistentNode+0xc
0000000a`393fdbd0 00007ffd`75734e81 chrome_child!blink::PersistentRegion::TracePersistentNodes+0x9a
0000000a`393fdc60 00007ffd`75734d5f chrome_child!blink::ThreadState::VisitPersistents+0x4f
0000000a`393fdd50 00007ffd`75734c81 chrome_child!blink::ThreadHeap::VisitPersistentRoots+0x4d
0000000a`393fde40 00007ffd`75733e57 chrome_child!blink::ThreadState::MarkPhaseVisitRoots+0x35
0000000a`393fdea0 00007ffd`751610b9 chrome_child!blink::ThreadState::CollectGarbage+0x141
0000000a`393fe130 00007ffd`751605fc chrome_child!blink::ThreadState::RunScheduledGC+0x89
0000000a`393fe160 00007ffd`7514af88 chrome_child!blink::ThreadState::SafePoint+0x1a
0000000a`393fe1a0 00007ffd`7514acef chrome_child!blink::scheduler::TaskQueueManagerImpl::NotifyDidProcessTask+0x268
0000000a`393fe350 00007ffd`7514871b chrome_child!blink::scheduler::TaskQueueManagerImpl::DidRunTask+0x55
0000000a`393fe3c0 00007ffd`750eac85 chrome_child!blink::scheduler::internal::ThreadControllerImpl::DoWork+0x199
(Inline Function) --------`-------- chrome_child!base::OnceCallback<void ()>::Run+0x1e
0000000a`393fe5e0 00007ffd`750e91bc chrome_child!base::debug::TaskAnnotator::RunTask+0x135
0000000a`393fe700 00007ffd`750e0228 chrome_child!base::MessageLoop::RunTask+0x23c
(Inline Function) --------`-------- chrome_child!base::MessageLoop::DeferOrRunPendingTask+0x96

ブレークポイントがヒットした時点で、第二引数、すなわち rdx レジスターの値が 00007ffd`79752900 になっており、!persistent コマンド出力の 2 列目である self_ の値に一致していることが分かります。

このブレークポイントからもう少し実行を進めると、WTF::HashSet の Trace() が呼ばれ、それがWTF::HashTable の Trace() を呼んでいることが分かります。テンプレートのせいで関数名が凶悪なのと、インライン展開が連発しているのでログが読みにくいです。

0:000> r
rax=000042a6530e5ee0 rbx=0000000000000000 rcx=000042a6530e5ee0
rdx=0000000000000000 rsi=00007ffd750ac8c0 rdi=000001a0f70245b0
rip=00007ffd7573580e rsp=0000000a393fdb28 rbp=0000000000000000
 r8=0000000a393fdb50  r9=0000000a393fdba8 r10=00007ffd78b24150
r11=00000dcdc7424d80 r12=0000000000000000 r13=0000000000000000
r14=000042a6528ac008 r15=0000000000000fd0
iopl=0         nv up ei ng nz ac po cy
cs=0033  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00000297
chrome_child!blink::Worklist<blink::MarkingItem,256,1>::Push:
00007ffd`7573580e 4157            push    r15

0:000> kL10
Child-SP          RetAddr           Call Site
0000000a`393fdb28 00007ffd`764d41be chrome_child!blink::Worklist<blink::MarkingItem,256,1>::Push
(Inline Function) --------`-------- chrome_child!blink::Worklist<blink::MarkingItem,256,1>::View::Push+0x25
(Inline Function) --------`-------- chrome_child!blink::MarkingVisitor::RegisterWeakCallback+0x2b
0000000a`393fdb30 00007ffd`75735f71 chrome_child!blink::MarkingVisitor::VisitBackingStoreWeakly+0x3e
(Inline Function) --------`-------- chrome_child!blink::Visitor::TraceBackingStoreWeakly+0x33
(Inline Function) --------`-------- chrome_child!blink::HeapAllocator::TraceHashTableBackingWeakly+0x33
(Inline Function) --------`-------- chrome_child!WTF::HashTable<blink::WeakMember<blink::Page>,blink::WeakMember<blink::Page>,WTF::IdentityExtractor,WTF::MemberHash<blink::Page>,WTF::HashTraits<blink::WeakMember<blink::Page> >,WTF::HashTraits<blink::WeakMember<blink::Page> >,blink::HeapAllocator>::Trace+0x3b
(Inline Function) --------`-------- chrome_child!WTF::HashSet<blink::WeakMember<blink::Page>,WTF::MemberHash<blink::Page>,WTF::HashTraits<blink::WeakMember<blink::Page> >,blink::HeapAllocator>::Trace+0x3b
(Inline Function) --------`-------- chrome_child!blink::TraceTrait<blink::HeapHashSet<blink::WeakMember<blink::Page>,WTF::MemberHash<blink::Page>,WTF::HashTraits<blink::WeakMember<blink::Page> > > >::Trace+0x3b
(Inline Function) --------`-------- chrome_child!blink::Visitor::Trace+0x3b
(Inline Function) --------`-------- chrome_child!blink::PersistentHeapCollectionBase<blink::HeapHashSet<blink::WeakMember<blink::Page>,WTF::MemberHash<blink::Page>,WTF::HashTraits<blink::WeakMember<blink::Page> > > >::TracePersistent+0x3b
0000000a`393fdb70 00007ffd`75735026 chrome_child!blink::TraceMethodDelegate<blink::PersistentHeapCollectionBase<blink::HeapHashSet<blink::WeakMember<blink::Page>,WTF::MemberHash<blink::Page>,WTF::HashTraits<blink::WeakMember<blink::Page> > > >,&blink::PersistentHeapCollectionBase<blink::HeapHashSet<blink::WeakMember<blink::Page>, WTF::MemberHash<blink::Page>, WTF::HashTraits<blink::WeakMember<blink::Page> > > >::TracePersistent>::Trampoline+0x51
(Inline Function) --------`-------- chrome_child!blink::PersistentNode::TracePersistentNode+0xc
0000000a`393fdbd0 00007ffd`75734e81 chrome_child!blink::PersistentRegion::TracePersistentNodes+0x9a
0000000a`393fdc60 00007ffd`75734d5f chrome_child!blink::ThreadState::VisitPersistents+0x4f
0000000a`393fdd50 00007ffd`75734c81 chrome_child!blink::ThreadHeap::VisitPersistentRoots+0x4d
0:000>

これで、PersistentRegion が保持するルートセットの各オブジェクトに対して Trace() 関数が呼ばれていることを確認できました。さて、マーク対象のオブジェクトがそのクラスのメンバー変数として別の Oilpan オブジェクトを保持している場合、そのメンバーに対する Trace() 関数を連鎖的に呼び出す必要があります。

例えば、HTML の Link タグを示すクラスは blink::HTMLLinkElement ですが、その Trace() 関数は以下のように定義されており、blink::HTMLLinkElement がトレースされると、そのメンバーである link_ など 4 つのメンバー変数がトレースされるようになっています。これが、デザインドキュメントの "all objects reachable from the root set by calling trace() methods defined on each object." という記述に相当する部分です。ルートセット内の各オブジェクトをルートとするツリーを DFS する感じです。

void HTMLLinkElement::Trace(blink::Visitor* visitor) {
  visitor->Trace(link_);
  visitor->Trace(sizes_);
  visitor->Trace(link_loader_);
  visitor->Trace(rel_list_);
  HTMLElement::Trace(visitor);
  LinkLoaderClient::Trace(visitor);
}

スタックメモリーのスキャン

Safe point がイベントループの最後にある Safe point だった場合、ルートセットからのトレースだけでマーキングは完了です。このときに実行される GC を Precise GC と呼びます。もしそれ以外の Safe point で GC が実行された場合、ルートセットだけでなく、スタックメモリー上にある Oilpan オブジェクトも調べる必要があります。なぜなら、ルートセット内のオブジェクトには依存していないが、Safe point に到達するまでの関数のローカル変数としてオブジェクトが保持されているかもしれないからです。このときの GC を Conservative GC と呼びます。

ルートセットやスタック以外の場所、例えば PartitionAlloc で確保したオブジェクトのメンバー変数に Oilpan オブジェクトが存在した場合、Oilpan はそのオブジェクトを検知する手段を持たないため、マーク処理が行われません。そのようなオブジェクトはスイープ処理で解放されてしまい、UAF が発生します。言語として C++ を使用する以上、この問題を根本的に防ぐことはできません。Oilpan 利用時には、利用者の責任で、予め決められたマクロやテンプレートを使ってクラスを定義したり、Trace() 関数を定義することが求められます。

スタック領域にあるオブジェクトのトレース処理は、blink::ThreadState::VisitStack に実装されています。例えば以下のコールスタックは、スタック上に見つかったアドレスのオブジェクトをマークしている瞬間を捉えています。

0:000> kL10
Child-SP          RetAddr           Call Site
(Inline Function) --------`-------- chrome_child!blink::HeapObjectHeader::TryMark+0x15
(Inline Function) --------`-------- chrome_child!blink::MarkingVisitor::MarkHeaderNoTracing+0x15
(Inline Function) --------`-------- chrome_child!blink::MarkingVisitor::MarkHeader+0x15
000000c2`8a1fb9e0 00007ffd`7984072c chrome_child!blink::MarkingVisitor::ConservativelyMarkHeader+0x57
000000c2`8a1fba40 00007ffd`78aa63bb chrome_child!blink::ThreadHeap::CheckAndMarkPointer+0x3e
000000c2`8a1fba80 00007ffd`78aa62a9 chrome_child!blink::ThreadState::VisitStack+0x3f
000000c2`8a1fbad0 00007ffd`78aa4cbd chrome_child!blink::ThreadHeap::VisitStackRoots+0x4d
000000c2`8a1fbbc0 00007ffd`78aa3e57 chrome_child!blink::ThreadState::MarkPhaseVisitRoots+0x71
000000c2`8a1fbc20 00007ffd`78521cc6 chrome_child!blink::ThreadState::CollectGarbage+0x141
000000c2`8a1fbeb0 00007ffd`78521537 chrome_child!blink::ThreadState::ScheduleGCIfNeeded+0x242
000000c2`8a1fc000 00007ffd`7883c70a chrome_child!blink::NormalPageArena::OutOfLineAllocate+0x97
(Inline Function) --------`-------- chrome_child!blink::NormalPageArena::AllocateObject+0x9e
(Inline Function) --------`-------- chrome_child!blink::ThreadHeap::AllocateOnArenaIndex+0xac
(Inline Function) --------`-------- chrome_child!blink::HeapAllocator::AllocateHashTableBacking+0xda
(Inline Function) --------`-------- chrome_child!blink::HeapAllocator::AllocateZeroedHashTableBacking+0xda
000000c2`8a1fc050 00007ffd`7883c3c9 chrome_child!WTF::HashTable<blink::WeakMember<blink::Node>,WTF::KeyValuePair<blink::WeakMember<blink::Node>,blink::TraceWrapperMember<blink::EventTargetData> >,WTF::KeyValuePairKeyExtractor,WTF::MemberHash<blink::Node>,WTF::HashMapValueTraits<WTF::HashTraits<blink::WeakMember<blink::Node> >,WTF::HashTraits<blink::TraceWrapperMember<blink::EventTargetData> > >,WTF::HashTraits<blink::WeakMember<blink::Node> >,blink::HeapAllocator>::AllocateTable+0xea

処理内容は単純で、トレース開始時に SafePointScope クラスのインスタンスをローカル変数としてスタックに置き、そのスレッドのスタックベースアドレスまでをループし、Oilpan で管理しているページのアドレスが見つかればそれをマークするという実装になっています。

ある数値が Oilpan の管理しているページかどうかを判別するには、blink::ThreadState::region_tree_ にある RegionTree というデータを利用します。

RegionTree は、Oilpan がこれまでに確保した Region (BlinkPage 10 個分の領域) を単純なバイナリ探索木で表したものです。もしスタック上に既存の Region の範囲内の数値があれば、それは Oilpan で確保したアドレスだろうと推測できます。もちろん、単なる数値データがたまたまその範囲のアドレスに含まれていたという可能性もありますが、そういう場合も含めて Oilpan はそのアドレスのオブジェクトをマークします。使用していないオブジェクトを使用中とみなしてマークすることは、無駄にメモリが消費してしまうデメリットはありますが、それによって UAF を引き起こすことはありません。逆に、使用中のオブジェクトを使用していないとみなしてしまうと UAF が起こるので、これは絶対に避けないといけません。これが Conservative と呼ばれる所以です。

スタック上の値を含む Region が存在すれば、その値が Region の中のどの BlinkPage に所属しているかは簡単に分かります。次に、その値のペイロードヘッダーを見つけないといけませんが、単純にスタック上の値から -8 するのでは駄目です。なぜなら、スタック上の値がオブジェクトの先頭ではなく、途中のアドレスを示している可能性があるからです。

BlinkPage 上のアドレスから、そのアドレスが所属するオブジェクトのヘッダーを求めるためには、BlinkPage のメタ情報にある blink::NormalPage::object_start_bit_map_ という blink::ObjectStartBitmap 型のビットマップデータを利用します。詳細は後述しますが、blink::ObjectStartBitmap は、BlinkPage 内にある全てのペイロードヘッダーがある場所を管理しています。

スタック上にあった値 X が、RegionTree の情報から BlinkPage の範囲にあると分かった場合、その BlinkPage のビットマップを参照して、X から上流方向を見て一番近いところに存在するヘッダーのアドレスを見つけます。あとは、そのペイロードのマークビットを on にしてマーキングは終わります。

ビットマップ探索の処理は blink::ObjectStartBitmap::FindHeader であり、実に Google らしい華麗なビット処理で実現されています。こういうのをさらっと面接で思いつく人が Google に入社するんですかね。さらにマニアックですがアセンブリを見ても美しいです。ここで Bit Scan Reverse 使うのかよ、みたいな。

(補足) blink::ObjectStartBitmap の構造

blink::ObjectStartBitmap が管理するビットマップでは、x 番目のビットが、ペイロードの先頭から x 番目の 8 バイト (= Oilpan が管理する領域の最小粒度) 境界のアドレスにヘッダー (blink::HeapObjectHeader) が存在するかどうかを表しています。あまり綺麗ではありませんが、これも図を作ってみました。

図が示す通り、object_start_bit_map_.offset_ の値は必ず BlinkPage の先頭 + 0x1838 になり、ビットマップの最初のビットは、そのオフセット +0x1838 にヘッダーがあるかどうか、2 番目のビットは +0x1840 にヘッダーがあるかどうか、etc. を表します。

ビットマップのサイズは 2048 バイト = 2^14 ビットです。BlinkPage のサイズ（メタ情報などの領域を無視して）が 2^17 バイトであり、これを全て最小粒度 8 バイトの領域で埋めたとしてもヘッダーの数は 2^14 個で収まるため、2048 バイトは十分な大きさであると言えます。実際にはメタ情報や GuardPage があるので、ビットマップ後半部分は使われません。

これまで見てきた例で、00006b3e`fcda1000 の位置に NormalPage のメタデータがありました。このページのビットマップの先頭を見ると、以下のようになります。

0:000> dt chrome_child!blink::NormalPage 00006b3e`fcda1000 object_start_bit_map_.
   +0x030 object_start_bit_map_  :
      +0x000 offset_                : 0x00006b3e`fcda1838  "???"
      +0x008 object_start_bit_map_  : [2048]  "???"
0:000> db 00006b3e`fcda1000+38 l10
00006b3e`fcda1038  01 00 10 00 00 01 00 10-00 00 01 00 10 00 00 01  ................

!scan コマンドを使って、ビットマップをスキャンし、ペイロードが存在する (= ビットが on になっている) アドレスを列挙できるようにしました。

0:000> !scan -bitmap 00006b3e`fcda1000
   0 00006b3e`fcda1838         283    160
   1 00006b3e`fcda18d8         283    160
...
 328 00006b3e`fcdaee70         389    184
 329 00006b3e`fcdb5f38         283    160
 330 00006b3e`fcdb5fd8 F         0    184
 331 00006b3e`fcdb6090         283    160
 332 00006b3e`fcdb6130 F         0   3776
 333 00006b3e`fcdb6ff0         288    128
 334 00006b3e`fcdb7070         283    160
 335 00006b3e`fcdb7110 F         0  32496

BlinkPage 00006b3e`fcda1000 には 0~335 のヘッダーがありました。右端の数値がヘッダー + ペイロードの合計サイズを示しており、例えば #0 と #1 に着目すると 00006b3e`fcda18d8 - 00006b3e`fcda1838 = 0xa0 = 160 なので、ヘッダーを含めて隙間なくペイロードが埋まっている様子が分かります。

#328 と #329 の間は例外で、この間には 00006b3e`fcdb5f38 - 00006b3e`fcdaee70 = 0x70c8 = 28872 バイトの隙間がありますが、#328 のサイズは 184 バイトなので 28688 バイト隙間が空いています。この隙間の理由は、この BlinkPage を保持する Arena を見ると分かります。

0:000> !arena 0000668e`a6c44000
blink::NormalPageArena 0000668e`a6c44000
blink::ThreadHeap 00000187`f28f40d0 Arena#0
current_allocation_point       00006b3e`fcdaef28
remaining_allocation_size      28688
last_remaining_allocation_size 83712
active pages:
blink::NormalPage 00006b3e`fcda1000 [00006b3e`fcda1838-00006b3e`fcdbf000] #
blink::NormalPage 00006b3e`fcdc1000 [00006b3e`fcdc1838-00006b3e`fcddf000]
...

#328 の直後 00006b3e`fcdaee70 + 0n184 = 00006b3e`fcdaef28 がぴったり current_allocation_point として管理されており、隙間の 28688 バイトも把握できています。これまで見てきた通り、Oilpan のメモリ確保処理では、Fast path としてまずこの隙間を埋めようとします。実際には #335 の位置により大きな 32496 バイトの領域があるのですが、それが使われるにはスイープ処理を待たなければなりません。

マーキングまとめ

長くなったのでマーキングについてまとめます。

マーキング対象となるのは、PersistentRegion としてスレッド内外で管理されているルートセットと、マーキング処理を始めるときのスタックの位置からそのスレッドのスタックベースの間にあるオブジェクトそれぞれから、オブジェクト毎に定義された Trace() 関数で DFS して得られるオブジェクトでした。

各オブジェクトに対するマーキング処理は、そのオブジェクトのペイロードヘッダーにあるマークビットを on にする処理です。

スタックのアドレスが Oilpan のアドレスかどうかを判別するためには、RegionTree と、BlinkPage 内のビットマップというデータを使っていました。

スイープ

スイープはとても単純な処理で、コードで言うと blink::NormalPage::Sweep だけです。

マーキングが終わると、使われているオブジェクトにはマークビットが立っているので、BlinkPage 内のオブジェクトを順番にチェックし、マークビットが立っているものはそのまま、立っていないものは空き領域として解放、すなわち free_list に追加できます。当然隣り合った空き領域はマージします。

デバッガーを使い、スイープの前後で BlinkPage の様子がどう変わるかを見ると理解が早いです。blink::NormalPage::Sweep で止めて、!scan でページのペイロードをスキャンし、blink::NormalPage::Sweep 実行後にもう一度ペイロードをスキャンした結果が以下の出力です。

0:000> g
Breakpoint 0 hit
chrome_child!blink::NormalPage::Sweep:
00007ff9`dd5ae39a 55              push    rbp

0:000> !hpage @rcx
blink::NormalPage 00002283`4b961000 [00002283`4b961838-00002283`4b97f000]
Arena#6 0000010b`03a44540
ThreadState 00007ff9`e145a050

0:000> !arena 0000010b`03a44540
blink::NormalPageArena 0000010b`03a44540
blink::ThreadHeap 0000024e`50bbde20 Arena#6
current_allocation_point       00000000
remaining_allocation_size      0
last_remaining_allocation_size 0
active pages:
unswept pages:
blink::NormalPage 00002283`4b961000 [00002283`4b961838-00002283`4b97f000]
blink::NormalPage 00002283`4ba61000 [00002283`4ba61838-00002283`4ba7f000]
free chunks:

0:000> !scan @rcx
   0 00002283`4b961838         140    416
   1 00002283`4b9619d8         140    872
   2 00002283`4b961d40         140    872
...
  26 00002283`4b965168         140    416
  27 00002283`4b965308   M     247     40
  28 00002283`4b965330   M     247     40
  29 00002283`4b965358   M     247     40
  30 00002283`4b965380   M     247     40
  31 00002283`4b9653a8   M     247     40
  32 00002283`4b9653d0   M     247     40
  33 00002283`4b9653f8   M     247     40
  34 00002283`4b965420         374     40
...
 207 00002283`4b969018         336     40
 208 00002283`4b969040   M     140    200
 209 00002283`4b969108         374     40
 210 00002283`4b969130         328     40
 211 00002283`4b969158 F         0  89768

0:000> gu
    could step in/over inline function frames ...
01 000000f3`6b3fdef0 00007ff9`dd011722 chrome_child!blink::NormalPageArena::LazySweepPages+0x58
chrome_child!blink::NormalPageArena::LazySweepPages+0x58:
00007ff9`dd5afaf8 488b4720        mov     rax,qword ptr [rdi+20h] ds:00002283`4b961020=000022834ba61000

0:000> !scan 00002283`4b961000
   0 00002283`4b961838 F         0  15056
   1 00002283`4b965308         247     40
   2 00002283`4b965330         247     40
   3 00002283`4b965358         247     40
   4 00002283`4b965380         247     40
   5 00002283`4b9653a8         247     40
   6 00002283`4b9653d0         247     40
   7 00002283`4b9653f8         247     40
   8 00002283`4b965420 F         0  15392
   9 00002283`4b969040         140    200
  10 00002283`4b969108 F         0  89848

0:000> !arena 0000010b`03a44540
blink::NormalPageArena 0000010b`03a44540
blink::ThreadHeap 0000024e`50bbde20 Arena#6
current_allocation_point       00000000
remaining_allocation_size      0
last_remaining_allocation_size 0
active pages:
unswept pages:
blink::NormalPage 00002283`4b961000 [00002283`4b961838-00002283`4b97f000]
blink::NormalPage 00002283`4ba61000 [00002283`4ba61838-00002283`4ba7f000]
free chunks:
 13 00002283`4b965420 15392 00002283`4b961838 15056
 16 00002283`4b969108 89848

上記例では、BlinkPage 00002283`4b961000 に対してスイープを行なっています。

blink::NormalPage::Sweep が開始する時点で既にマーキングは終わっています。ページ内には #0 から #211 までのヘッダーがあり、マークされているのは #27 から #33 までと、#208 の 8 個だけです。ほとんどのスペースは使用されていないオブジェクトの領域で占められていることが分かります。

blink::NormalPage::Sweep の後にもう一度スキャンすると、ヘッダーは 11 個と劇的に減っており、かなりコンパクトになりました。スイープ前後での変化を詳しく見ると、マーク済みの領域はその場所とサイズが維持されたままマークビットが off になり、それ以外の領域は連続する領域がマージされ、その領域の free ビットが on になっています。末尾のペイロードも、ペイロードの終わりが BlinkPage の末尾に一致するように拡大されています (00002283`4b969108 + 0n89848 = 00002283`4b97f000)。

BlinkPage 00002283`4b961000 が所属する Arena 0000010b`03a44540 を見ると、空き領域である #0, #8, #10 全てがの free_list に追加されています。この後のタイミングで Arena 0000010b`03a44540 に対してメモリ確保要求が来た場合、最大の空き領域である 00002283`4b969108 の先頭から領域が切り出され、残りの領域が current_allocation_point にセットされて Fast path が利用可能になります。

おわりに

PartitionAlloc の記事から 2 週間も経ってしまいましたが、何とかまとめました。ヒープの構造や Fast path/Slow path のロジックは単純ですが、ガベージコレクションは調べだすとキリがないですね。個人的な課題で言うと、GC の Write barrier という概念がよく分からなかったので何とか調べたいところ。Stop-the-world の処理や、他の Safe point の位置、スレッド間の関係なども気になります。

おそらく Oilpan のマーク & スイープはわりと教科書的な実装です。例えば、Ruby における GC もマーク & スイープ型らしく、以下のページに実装の説明が載っていますが、概ね似ている感じです。Chromium Project の Blink GC Design を見ると、"It doesn't (yet) implement a generational or incremental GC." という記述があるので、世代別 GC を実装する計画もあるようです。

Rubyソースコード完全解説：第5章ガ－ベージコレクション
http://i.loveruby.net/ja/rhg/book/gc.html

記事を書くためにコードを眺めていたところ、LargeObjectArena にしょぼいバグがあるのを見つけたので Chromium に issue 登録しました。

847679 - blink::LargeObjectPage::PayloadEnd returns a wrong value - chromium - Monorail
https://bugs.chromium.org/p/chromium/issues/detail?id=847679

あまり期待していなかったのですが、2 週間後に Priority が 2 に引き上げられて、さくっとマージされました。よかったよかった。

[oilpan] Fix LargeObjectPage sizes (I36061d52) · Gerrit Code Review
https://chromium-review.googlesource.com/c/chromium/src/+/1098746

余談ですが、字面から Oilpan というのはフライパンの親戚みたいなキッチン用品だろうと思っていたら、車のエンジンの部品でした。オイルってエンジンオイルかよ。

Chromium のメモリ管理 (Oilpan)