# 機能設計書 2-ガベージコレクション（GC）

## 概要

本ドキュメントは、mrubyのガベージコレクション（GC）機能の設計を記述する。三色インクリメンタルマーク&スイープ方式のGCにより、オブジェクトの自動メモリ管理を提供する。

### 本機能の処理概要

mrubyのGCは三色（White/Gray/Black）インクリメンタルマーク&スイープ方式を採用し、オブジェクトのライフサイクルを自動管理する。ジェネレーショナルGCモードも備え、Minor GC（若い世代のみ）とMajor GC（全オブジェクト）を使い分けることで効率的なメモリ回収を実現する。

**業務上の目的・背景**：mrubyは組み込みシステム向けの言語実装であり、手動メモリ管理の負担を軽減しつつ、リアルタイム性に近い応答性を維持するためにインクリメンタルGCを採用している。三色方式により、GCを小さなステップに分割して実行でき、長時間のストップ・ザ・ワールドを回避する。

**機能の利用シーン**：全てのmrubyオブジェクト割り当て時に自動的に起動される。`mrb_obj_alloc`でのオブジェクト生成、メモリ不足時の強制GC、明示的な`GC.start`呼び出し等で使用される。

**主要な処理内容**：
1. オブジェクト割り当て（`mrb_obj_alloc`）とヒープページ管理
2. インクリメンタルマーク処理（ルートからの到達可能オブジェクトの追跡）
3. スイープ処理（到達不可能オブジェクトの回収）
4. ライトバリア（`mrb_field_write_barrier`, `mrb_write_barrier`）
5. GCアリーナによる一時的なGC保護
6. ジェネレーショナルGC（Minor/Major GCの切り替え）

**関連システム・外部連携**：VM（スタックのマーキング）、全オブジェクト型（型別のマーク・解放処理）、メモリアロケータ。

**権限による制御**：`GC.disable`によるGCの一時無効化、`GC.enable`による再有効化が可能。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面機能マッピングにデータなし |

## 機能種別

メモリ管理処理（自動ガベージコレクション）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| mrb | mrb_state* | Yes | mrubyインタプリタ状態 | NULLでないこと |
| ttype | enum mrb_vtype | Yes | 割り当てるオブジェクト型（mrb_obj_alloc） | MRB_TT_FREE超過 |
| cls | struct RClass* | No | オブジェクトのクラス | 型整合性チェック |

### 入力データソース

ヒープページ（mrb_heap_page）のフリーリストからオブジェクトスロットを取得。ルートオブジェクト群（mrb_state内の各種ポインタ）からマーク処理を開始。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 割り当てオブジェクト | struct RBasic* | mrb_obj_allocの戻り値 |
| GC統計情報 | mrb_gc構造体 | live, threshold, state等の状態 |

### 出力先

呼び出し元への戻り値、およびmrb_gc構造体内のステータス更新。

## 処理フロー

### 処理シーケンス

```
1. mrb_obj_alloc() - オブジェクト割り当て
   ├─ GCストレスモード時: mrb_full_gc()
   ├─ threshold < live 時: mrb_incremental_gc()
   ├─ フリーリスト空時: add_heap()
   └─ フリーリストからオブジェクトスロット取得、初期化
2. mrb_incremental_gc() - インクリメンタルGC
   ├─ MRB_GC_STATE_ROOT: root_scan_phase() → MRB_GC_STATE_MARK
   ├─ MRB_GC_STATE_MARK: incremental_marking_phase()
   └─ MRB_GC_STATE_SWEEP: incremental_sweep_phase()
3. マーク処理
   ├─ ルートマーキング（グローバル変数、スタック、コールスタック等）
   ├─ グレーオブジェクトの子オブジェクトをマーク
   └─ グレースタックオーバーフロー時: ヒープ再スキャン
4. スイープ処理
   ├─ ヒープページ走査
   ├─ デッドオブジェクト（反対色White）の解放
   └─ フリーリストへの追加
```

### フローチャート

```mermaid
flowchart TD
    A[mrb_obj_alloc] --> B{threshold < live?}
    B -->|Yes| C[mrb_incremental_gc]
    B -->|No| D{フリーリスト空?}
    C --> D
    D -->|Yes| E[add_heap]
    D -->|No| F[フリーリストから取得]
    E --> F
    F --> G[オブジェクト初期化]
    G --> H[White色に着色]

    C --> I{GC状態}
    I -->|ROOT| J[root_scan_phase]
    I -->|MARK| K[incremental_marking_phase]
    I -->|SWEEP| L[incremental_sweep_phase]
    J --> K
    K --> M{マーク完了?}
    M -->|No| N[次回に継続]
    M -->|Yes| L
    L --> O{スイープ完了?}
    O -->|No| N
    O -->|Yes| P[GC完了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 三色マーキング | White（未マーク）、Gray（マーク済み/子未マーク）、Black（完全マーク済み）、Red（静的ROM） | 全オブジェクト |
| BR-02 | 二種White | White-AとWhite-Bのフリップフロップでスイープ対象を効率的に切り替え | GCサイクル切り替え時 |
| BR-03 | GC開始閾値 | live > thresholdで増分GCを開始 | オブジェクト割り当て時 |
| BR-04 | ジェネレーショナルGC | デフォルトで有効。MinorGCは若い世代のみ、MajorGCは全オブジェクトを対象 | MRB_GC_TURN_OFF_GENERATIONAL未定義時 |

### 計算ロジック

- GC interval ratio: デフォルト200（`DEFAULT_GC_INTERVAL_RATIO`）
- GC step ratio: デフォルト200（`DEFAULT_GC_STEP_RATIO`）
- Major GC増分比率: 120（`MAJOR_GC_INC_RATIO`）
- ヒープページサイズ: 1024スロット（`MRB_HEAP_PAGE_SIZE`）
- GCステップサイズ: 1024（`GC_STEP_SIZE`）

## データベース操作仕様

該当なし（インメモリ処理のみ）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| NoMemoryError | メモリ不足 | GC後もフリーリストが空でヒープ追加も失敗 | メモリ使用量の見直し |
| TypeError | 型不正 | mrb_obj_allocで不正なttype指定 | 正しいオブジェクト型を指定 |
| RuntimeError | アリーナオーバーフロー | GCアリーナがMRB_GC_ARENA_SIZE超過（固定アリーナ時） | mrb_gc_arena_save/restoreの適切な使用 |

### リトライ仕様

メモリ不足時に`mrb_full_gc`を実行して再試行。それでもメモリ確保できない場合はNoMemoryErrorを発生。

## トランザクション仕様

該当なし

## パフォーマンス要件

- インクリメンタル方式により長時間のGC停止を回避
- ジェネレーショナルGCによりMinor GCの高速化
- GCアリーナサイズ: デフォルト100（`MRB_GC_ARENA_SIZE`）
- グレースタックサイズ: 1024（`MRB_GRAY_STACK_SIZE`）

## セキュリティ考慮事項

- GC中のオブジェクト操作によるメモリ安全性の維持（ライトバリア）
- out_of_memoryフラグによるメモリ枯渇状態の管理

## 備考

- gc.cは約1610行
- `MRB_GC_STRESS`定義時はオブジェクト割り当てごとにフルGCを実行（デバッグ用）
- Red色オブジェクトはROM（静的データ）で、GC対象外

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | gc.h | `include/mruby/gc.h` | mrb_gc構造体（41-69行目）: heaps, free_heaps, gray_stack, live, threshold, state等 |
| 1-2 | gc.c | `src/gc.c` | RVALUE共用体（127-146行目）: 全オブジェクト型をカバーするヒープスロット |
| 1-3 | gc.c | `src/gc.c` | mrb_heap_page構造体（158-164行目）: freelist, objects配列 |
| 1-4 | gc.c | `src/gc.c` | 色定数定義（168-188行目）: GC_GRAY=0, GC_WHITE_A=1, GC_WHITE_B=2, GC_BLACK=4, GC_RED=7 |

**読解のコツ**: 三色の管理はgc_colorフィールドのビット操作で行われる。`is_dead`マクロは「反対色のWhiteまたはFREE型」で判定する。

#### Step 2: GC初期化と破棄を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | gc.c | `src/gc.c` | mrb_gc_init()（331-349行目）: アリーナ確保、ヒープページ追加、閾値設定 |
| 2-2 | gc.c | `src/gc.c` | mrb_gc_destroy()（371-378行目）: ヒープ全解放、アリーナ解放 |
| 2-3 | gc.c | `src/gc.c` | add_heap()（302-321行目）: ヒープページ割り当てとフリーリスト構築 |

**主要処理フロー**:
- **335-336行目**: アリーナの初期確保（MRB_GC_ARENA_SIZE）
- **339行目**: current_white_partをGC_WHITE_Aに初期化
- **342行目**: 最初のヒープページ追加
- **343-344行目**: interval_ratioとstep_ratioをデフォルト200に設定

#### Step 3: オブジェクト割り当てを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | gc.c | `src/gc.c` | mrb_obj_alloc()（467-523行目）: 型チェック、GC起動、フリーリスト取得、初期化 |

**主要処理フロー**:
- **473-494行目**: cls型の整合性チェック
- **502-504行目**: threshold < live 時にインクリメンタルGC起動
- **510-513行目**: フリーリストからスロット取得
- **521行目**: partial_white色に着色

#### Step 4: マーク・スイープ処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | gc.c | `src/gc.c` | mrb_gc_mark()（749-757行目）: Whiteオブジェクトをグレーリストに追加 |
| 4-2 | gc.c | `src/gc.c` | gc_mark_children()（595-747行目）: 型別の子オブジェクトマーキング |
| 4-3 | gc.c | `src/gc.c` | mark_context()（569-593行目）: VMスタック・コールスタックのマーキング |
| 4-4 | gc.c | `src/gc.c` | obj_free()（759-799行目）: 型別のオブジェクト解放 |

### プログラム呼び出し階層図

```
mrb_obj_alloc()
    │
    ├─ mrb_incremental_gc()
    │      │
    │      ├─ root_scan_phase()
    │      │      ├─ mark_context() ─── VMスタック/コールスタックマーク
    │      │      └─ mrb_gc_mark() ─── ルートオブジェクトマーク
    │      │
    │      ├─ incremental_marking_phase()
    │      │      └─ gc_mark_children() ─── 型別子オブジェクトマーク
    │      │
    │      └─ incremental_sweep_phase()
    │             └─ obj_free() ─── 型別オブジェクト解放
    │
    ├─ add_heap() ─── ヒープページ追加
    │
    └─ gc_protect() ─── GCアリーナへの登録

mrb_full_gc()
    └─ mrb_incremental_gc() × N回（完了まで）
```

### データフロー図

```
[入力]                     [処理]                         [出力]

ルートオブジェクト群 ────▶ root_scan_phase()
  (mrb_state内ポインタ)    │
                          ▼
グレーオブジェクト ───────▶ gc_mark_children()           ──▶ Black（到達可能）
                          │
                          ▼
ヒープページ ─────────────▶ incremental_sweep_phase()    ──▶ フリーリスト（回収済み）
                          │
フリーリスト ─────────────▶ mrb_obj_alloc()              ──▶ 新規オブジェクト
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| gc.c | `src/gc.c` | ソース | GC本体（マーク、スイープ、オブジェクト割り当て） |
| gc.h | `include/mruby/gc.h` | ヘッダ | mrb_gc構造体、GC状態列挙型 |
| mruby.h | `include/mruby.h` | ヘッダ | mrb_state構造体（gcフィールド） |
