PHP・GCの話-6話)管理対象の巡回・削除。Garbage Collection Cycle

前書き

• すべての記事は、自分の勉強目的と主観の整理を含めています。あくまで参考レベルで活用してください。もし誤った情報などがあればご意見をいただけるととっても嬉しいです。
• 内容では、省略するか曖昧な説明で、わかりづらいところもあると思います。そこは、連絡いただければ補足などを追加するので、ぜひ負担なくご連絡ください。
• 本文での「GC」は、「Garbage Collection, Garbage Collector」の意味しており、略語として使われています。
• この記事は、連載を前提に構成されています。

※ 連載目録

• PHP・GCの話-1話)なぜ GarbageCollection? メモリと GC を意識する
• PHP・GCの話-2話)変数の管理情報、zval container と reference count
• PHP・GCの話-3話)変数データのメモリからの消滅
• PHP・GCの話-4話)MemoryLeak と解除できない変数データ
• PHP・GCの話-5話)GC 登場。GC 発生条件と root buffer
• PHP・GCの話-6 話)管理対象の巡回・削除。Garbage Collection Cycle (← 現在の記事)
• PHP・GCの話-7話)GC 関連機能紹介 1 (GC Statistics) ⇨ 準備中
• PHP・GCの話-8話)GC 関連機能紹介 2 (Weak Reference Type)(END) ⇨ 準備中

※ 連載で使うサンプルコード

Sample Code Link on Github

● ExampleGc.php : 2 話から 6 話までの内容で使うサンプルコードです。
● ExampleWeakReference : 8話の WeakReference の内容で使うサンプルコードです。

本連載記事は、基本的にこのサンプルコードをベースに説明をしています。
サンプルコードは、必ず見る必要も実行してみる必要もありません。
各話ごとに、コードを分解して動作原理と結果を解説しますので、基本記事の内容で足りるように心がけます。
あくまで、全体コードをみたい、手元で回してみたい、修正して回してみたいという方向けです。

_ GIF 捕捉資料のスライドに関して _

GC Cycles 捕捉資料・スライド(POWERPOINT ONLINE)

本記事では、GC CYCLES の説明のため、多数の GIF アニメーションを添付していますが、みづらい場合もあると存じます。
GIF 捕捉資料の元であるスライドファイルを添付しますので、関心のある方はスライドを参考にしていただければと思います。

今回の話

今回は、以下のものを話そうと思うます。

• 1. メモリ解除・GC のグランドルール説明
• 2. GC-Basic のサンプルコードの説明
• 3. GC-Basic-1) root zval の格納・Mark to Purple
• 4. GC-Basic-2) DFS 探索 ① & refcount の差引 & Mark to Gray
• 5. GC-Basic-3) DFS 探索 ② & recount のチェック & Mark Black or White
• 6. GC-Basic-4) root zval の削除 & White Marked zval のメモリ解除
• 7. GC-Extra) より複数の zval 巡回例 & Black Marked zval に対する refcount 差し戻し過程
• 8. Summary

1. PHP のメモリ解除・GC のグランドルール説明

今までの 5 話までの内容とかぶるところも多いですが、もう一度整理するということで、グランドルールを説明します。
このルールを元に GC Cycle は、巡回対象とその配下のすべて zval の refcount を１づつ減らし、その zval の refcount が最終的に 0 になるのかをチェックすることで、どの変数データがゴミなのかを判別できるようになります。

1) メモリ解除でのグランドルール

• zval の refcount が増加したのは、どこかで仕様されているので、回収しない
• zval の refcount が減少し、0 である場合は、即時に回収されメモリからも解除される
• ★ つまり、GC Cycle は refcount が減少してもまた 1 以上の root zval のみが対象になる。

2) GC においてのグランドルール

• PHP の GC 機能は、以下のシステムモデルを具現している。
  • » Concurrent Cycle Collection in Reference Counted Systems
• GC Cycle の巡回アルゴリズムは DFS を前提としている(Depth First Search)
• GC は仮想的な概念として、GC の巡回と確認過程で、以下のカラーマーキングを定義している
  • mark to Black : 基本色、巡回前 or 巡回・チェック完了、refcount が 1 以上の未回収対象
  • mark to Purple : GC Cycle の対象となった root zval
  • mark to Gray : GC Cycle で巡回済み & refcount - 1 済み（重複で差し引くことを防止）
  • mark to White : GC Cycle でチェック完了、refcount が最終的に 0 で、GC のメモリ解除対象の zval

これからの GC Cycle の過程を説明するのに、カラーマーキングの定義は重要になります。

3) zval の状態変化と life cycle

グランドルールで説明した「カラーマーキング」を元に、zval のステータス変化とライフサイクルを図式化するとこうなります。
角ステータスとの相関関係を意識しておくと GC Cycle を理解するのに役立つと思います。

2. GC-Basic のサンプルコードの説明

4 話、5 話まで見てきたコードを思えていますでしょうか。
そのコードをベースに、GC Cycle の過程を説明していきますので、ここでもう一度確認します。

● サンプルコードパーツ

/**
 * Example to explain
 * 1. Variable Lifetime
 * 2. Memory Leak
 * 3. Root Buffer (root zval buffer)
 * 4. When Garbage Collector works
 * 5. How Garbage Collector works (basics)
 */
private function doExampleGcBasic()
{
    Log::debug(null, ['event' => 'start', 'msg' => __METHOD__]);
    $this->logMemUsage();

    Log::debug(null, ['event' => 'new', 'msg' => 'V']);
    $alive = new AliveInScope('V');
    xdebug_debug_zval('alive');
    $this->logMemUsage();

    Log::debug(null, ['event' => 'new', 'msg' => 'A, B']);
    $circleA = new CircularReference('A');
    $circleB = new CircularReference('B');

    Log::debug(null, ['event' => 'set', 'msg' => '$alive`s reference to A']);
    $circleA->addNode($alive);

    Log::debug(null, ['event' => 'set', 'msg' => 'circluar reference on A B']);
    $circleA->addNode($circleB);
    $circleB->addNode($circleA);

    xdebug_debug_zval('alive');
    xdebug_debug_zval('circleA');
    xdebug_debug_zval('circleB');
    $this->logMemUsage();

    Log::debug(null, ['event' => 'unset', 'msg' => 'A, B']);
    unset($circleA);
    unset($circleB);

    xdebug_debug_zval('alive');
    xdebug_debug_zval('circleA');
    xdebug_debug_zval('circleB');
    $this->logMemUsage();

    Log::debug(null, ['event' => 'invoke', 'msg' => 'garbage collection']);
    $this->makeGarbageReferenceTo10000CountWhichPHPDefaultRootBufferMax();

    xdebug_debug_zval('alive');
    $this->logMemUsage();

    Log::debug(null, ['event' => 'end', 'msg' => __METHOD__]);
}

● 実行結果

[2020-09-27 07:50:32] local.DEBUG: --------------------------------------------------
[2020-09-27 07:50:32] local.DEBUG:  {"event":"doExampleGcBasic","msg":"about Article 3,4,5,6,7"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"start","msg":"App\\Console\\Commands\\ExampleGc::doExampleGcBasic"}
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"16,084,440"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new","msg":"V"}
alive: (refcount=1, is_ref=0)=class App\Console\Commands\AliveInScope { private
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"37,061,192"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new","msg":"A, B"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"set","msg":"
[2020-09-27 07:50:32] local.DEBUG:  {"event":"set","msg":"circluar reference on A B"}
alive: (refcount=2, is_ref=0)=class App\Console\Commands\AliveInScope { private
circleA: (refcount=2, is_ref=0)=class App\Console\Commands\CircularReference { private
circleB: (refcount=2, is_ref=0)=class App\Console\Commands\CircularReference { private
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"79,015,672"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"unset","msg":"A, B"}
alive: (refcount=2, is_ref=0)=class App\Console\Commands\AliveInScope { private
circleA: no such symbol
circleB: no such symbol
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"79,016,312"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"invoke","msg":"garbage collection"}
alive: (refcount=1, is_ref=0)=class App\Console\Commands\AliveInScope { private
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"37,611,984"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"end","msg":"App\\Console\\Commands\\ExampleGc::doExampleGcBasic"}

では、ここからは GC が実際にどういうふうにゴミを回収するかを見ます。

3. GC-Basic-1) root zval の格納・Mark to Purple

...
unset($circleA);
unset($circleB);

5 話の root buffer の話でも見ましたが、ここまでのコードで、以下の絵の状態になります。

● 完了イメージ

この過程が「root zval の格納・Mark to Purple」の過程になります。
GC Cycle の巡回過程ではないですが、まず 1 段階として、root buffer に GC 巡回対象の root zval の格納することから始まります。

4. GC-Basic-2) DFS 探索 ① & refcount の差引 & Mark to Gray

Log::debug(null, ['event' => 'invoke', 'msg' => 'garbage collection']);
$this->makeGarbageReferenceTo10000CountWhichPHPDefaultRootBufferMax();

そして、以下のコードのmakeGarbageReferenceTo10000CountWhichPHPDefaultRootBufferMaxが引き続き実行されることで、GC が発動することになります。

GC が発動すると、root buffer 内の root zval に対して巡回を開始します。
以下の GIF で、その過程を説明しています。（３秒でページが切り替わります。）

① 表紙ページ番号です。
② まず、対象の root zval の refcount を-1 にし、Gray にマーキングします。これで A は巡回済になります。
③ 隣接の子ノードである V の zval を巡回します。同じく refcount を-1 にして Gray にマーキングします。
④ V は、子ノードを持っていないため、親ノードに戻ります。
⑤ A の他の隣接の子ノードである B を巡回します。同じく refcount を-1 にして Gray にマーキングします。
⑥ B の隣接の子ノードである A を巡回しますが、A はすでに Gray にマーキングされているため、何もしません。
⑦ B に戻りましたが、B はその他の子ノードを持っていないため、A に戻ります。
⑧ A に戻りましたが、その他の子ノードを持っていないので
⑨ ここで circleA い対する探索は完了になります。
⑩ root buffer 内の他の root zval である circleB に対しても、同じ過程を実行します。
⑪ これで、root buffer 内にある circleA, circleB に対する「DFS 探索 ① & refcount の差引 & Mark to Gray」過程は終了となります。

これで、GC 対象と関連されている zval の refcount はすべて-１ずつ減らし、Gray にマーキングされた状態になりますた。

5. GC-Basic-3) DFS 探索 ② & recount のチェック & Mark Black or White

① 表紙ページ番号です。
② Gray マーキングが完了した状態で、もう一度巡回を始めます。
③ A の refcount は０なので、White カラーでマーキングします。（後ほど、GC の回収対象になります。）
④ 連接の V を巡回します。refcount は１なので、Black カラーにマーキングします。
(GC 未回収対象です、V の隣接ノードがあれば、連鎖で refcount+1 をしますが、この例ではないので、A に戻ります) ※1
⑤ V の他の連接ノードがなかったため A に戻りました。
⑥ A の他の子ノードである B を巡回します。同じく、refcount は０なので、White カラーでマーキングします。（後ほど、GC の回収対象になります。）
⑦ B の子ノードである A を巡回しますが、すでに White でマーキング済みなので、何もしません。
⑧ B に戻りますが、B の他の子ノードが無いため、A に戻ります。
⑨ A に戻りますが、A の他の子ノードが無いため
⑩ circleA に対する巡回は終了となります。
⑪ root buffer 内の他の root zval である circleB に対しても、同じ過程を実行します。
⑫ これで、root buffer 内にある circleA, circleB に対する「DFS 探索 ② & recount のチェック & Mark Black or White」過程は終了となります。

これで、GC 対象と関連されている zval の refcount はすべて-１ずつ減らし、Gray にマーキングされた状態になりますた。

● 完了イメージ

6. GC-Basic-4) root zval の削除 & White Marked zval のメモリ解除

ここでは、root buffer を空にすると同時に、White Marked zval とデータを、全て解除して、メモリを確保します。
これにて、PHP の GC Cycle の過程は終了となります。

① 表紙ページ番号です。
② Black & White マーキングまで完了した状態です。
③ root buffer の zval とそれに継ががる White Marking zval をすべて解除します。
④ 最終的に V のみ残ることになり、メモリが確保されることになります。

7. GC-Extra) より複数の zval 巡回例 & Black Marked zval に対する refcount 差し戻し過程

今までは、簡単な循環参照の例で、GC Cycle の基本メカニズムを見ました。

今回は、もっと複雑な事例を通して、GC Cycle で起きられる全過程を説明します。
上記のGC-Basicの改定で説明したものは、ある程度省略して説明しますので、まずGC-Basicの内容をご参考ください。

サンプルコードは以下のパーツになります。

● サンプルコードパーツ

/**
 * Example to
 * 1. How Garbage Collector works
 */
private function doExampleGcCycle()
{
    Log::debug(null, ['event' => 'start', 'msg' => __METHOD__]);
    $this->logMemUsage();

    Log::debug(null, ['event' => 'new & set', 'msg' => 'V, X & V→X']);
    $alive = new AliveInScope('V');
    $alive->addNode(new \stdClass('X'));

    Log::debug(null, ['event' => 'new & set', 'msg' => 'F, E & F←→E']);
    $circleB = new CircularReference('F');
    $circleA = new CircularReference('E');
    $circleB->addNode($circleA);
    $circleA->addNode($circleB);

    Log::debug(null, ['event' => 'new & set', 'msg' => 'D & D→E']);
    $circleB = new CircularReference('D');
    $circleB->addNode($circleA);

    Log::debug(null, ['event' => 'new & set', 'msg' => 'C & C←→D']);
    $circleA = new CircularReference('C');
    $circleB->addNode($circleA);
    $circleA->addNode($circleB);

    Log::debug(null, ['event' => 'set', 'msg' => 'V←→C']);
    $alive->addNode($circleA);
    $circleA->addNode($alive);

    Log::debug(null, ['event' => 'new & set', 'msg' => 'B & B→C']);
    $circleB = new CircularReference('B');
    $circleB->addNode($circleA);

    Log::debug(null, ['event' => 'new & set', 'msg' => 'A & A←→B']);
    $circleA = new CircularReference('A');
    $circleB->addNode($circleA);
    $circleA->addNode($circleB);

    $this->logMemUsage();
    Log::debug(null, ['event' => 'unset', 'msg' => 'A, B']);
    unset($circleA);
    unset($circleB);

    $this->logMemUsage();

    Log::debug(null, ['event' => 'invoke', 'msg' => 'garbage collection']);
    $this->makeGarbageReferenceTo10000CountWhichPHPDefaultRootBufferMax();
    $this->logMemUsage();
}

● 実行結果

[2020-09-27 07:50:32] local.DEBUG: --------------------------------------------------
[2020-09-27 07:50:32] local.DEBUG:  {"event":"doExampleGcCycle","msg":"about Article 7"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"start","msg":"App\\Console\\Commands\\ExampleGc::doExampleGcCycle"}
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"16,636,848"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new & set","msg":"V, X & V→X"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new & set","msg":"F, E & F←→E"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new & set","msg":"D & D→E"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new & set","msg":"C & C←→D"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"set","msg":"V←→C"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new & set","msg":"B & B→C"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"new & set","msg":"A & A←→B"}
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"163,472,264"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"unset","msg":"A, B"}
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"163,472,904"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"invoke","msg":"garbage collection"}
[2020-09-27 07:50:32] local.DEBUG:  {"Memory Usage(Bytes)":"121,545,448"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"gc_collect_cycles","msg":"can call gc cycle forcibly. but be careful of using it"}
[2020-09-27 07:50:32] local.DEBUG:  {"event":"gc_collect_cycles","msg":"because gc cycle may can cause using many system resource & stopping program in doing gc cycle."}

1) A ～ F, V,X のオブジェクト初期化 ＆ ノード関係作り(①~④)

①~④ : GC-Basic で話した内容の範囲なので、特に細く説明はありません。

● 完了イメージ

2) A,B に対するシンボルの unset・GC 発動・Mark to Gray(①~②⑦)

①~②⑦ : GC-Basic で話した内容の範囲なので、特に細く説明はありません。

● 完了イメージ

3) refcount チェック・Mark to Black or White (①~⑦)

①~⑦ : GC-Basic で話した内容の範囲なので、特に細く説明はありません。

● 完了イメージ

4) refcount が 1 以上の場合、すべての子ノードの refcount を 1 づつ増加させる (①~①⑦)

① 表紙ページ番号です。
② Mark to Black or White 段階で、もし Black のマーキングは発生した場合、GC は既存の探索を一時中断します。そして、Black の zval を ROOT NODE として設定し DFS 探索を始めます。関連されているすべての zval に対して、refcount の１ずつ上げて Black にマーキングする revert 作業を開始します。ここでは、V が ROOT NODE になります。
③ V の隣接ノードの一つである X の refcount を+① し、Black にマーキングします。
▶ ※以降、同じ作業を revert と命名します。(zval に対して、refcount を+① し Black にマーキング)
④ X の隣接ノードはいないため、V に戻ります。
⑤ V の他の隣接ノードである C に対して revert します。
⑥ C の隣接ノードである D に対して revert します。
⑦ D の隣接ノードの一つで有る C は、すでに revert 済みなので何もしません。
⑧ D に戻ります。
⑨ D の他の隣接ノードである E に対して revert します。
⑩ E の他の隣接ノードである F に対して revert します。
⑪ F の隣接ノードの一つで有る E は、すでに revert 済みなので何もしません。
⑫ F に戻ります。(他の隣接ノードなし)
⑬ E に戻ります。(他の隣接ノードなし)
⑭ D に戻ります。(他の隣接ノードなし)
⑮ C に戻ります。(他の隣接ノードなし)
⑯ V に戻ります。(他の隣接ノードなし)
⑰ すべてのノードを巡回したので、revert のための DFS 探索はこれにて終了になります。引き続き、一時中断していた Mark to Black or White 巡回に戻りますが、この時本段階で Black でマーキングした zval は、巡回対象から外されます。

● 完了イメージ

5) refcount チェック・Mark to Black or White & GC 完了 (①~⑩)

①~⑩ : GC-Basic で話した内容の範囲なので、特に細く説明はありません。
※ 4)の段階で Black マーキングした zval は、巡回から除外対象となります。

● 完了イメージ

8. Summary

今回で、最低限に覚えて頂くと良い内容は以下になります。

• GC Cycle は、削除候補である ROOTBUFFER 内の zval を DFS 探索する
• GC Cycle の段階と、zvals の状態変化（refCount & Color Marking）

後書き

今回は、GC CYCLE のメカニズムを紹介しました。

実際の実装ではそんなに活用するところはないだろうと思ったりもしますが、メモリ管理のために PHP 陣営が導入したコンセプトとアプローチは、十分に興味深い物だと感じます。
最終回である次回では、GC の分析ツールと、GC と密接に関係のある WeakReference 関連クラスを扱います。