blog.dopana

戻る

前回の記事では、汎用ヒープアロケータを完全に排除し、ガベージコレクタ(GC)も使わずに データスタック(Data Stacks) とスコープ管理によって圧倒的な実行速度を誇る Goose 言語の基本アーキテクチャを紹介しました。

しかし、この説明を聞いたシステムエンジニアであれば、必ず次のような疑問に直面します。

「すべてのメモリがスコープの終了時にスタック単位で破棄されるなら、生存期間が階層的(LIFO)に従わないデータ構造 はどう実装するのか? ファイルが自由に追加・削除されるディレクトリツリーや、相互参照のある有向グラフ、ECS(Entity Component System)、LRUキャッシュはどう作るのか?」

C/C++ではこれを malloc/free で解決しますが、Use-After-Free(UAF)やメモリ断片化(フラグメンテーション)のリスクを抱えます。Rustでは循環参照やグラフの構築は最も困難な課題の1つであり、Rc<RefCell<T>> や SlotMap による世代付きインデックス管理が必要となります。

Gooseはこの難問に対し、極めて安全で無駄のない解答を用意しています。それが標準ライブラリの メモリプール(slot_pool<T> と slice_pool<T>) です。

1. 課題の本質:スコープに従わないデータ生存期間#

現実のファイルシステム(ディレクトリツリー)を想像してください。

/ (root)
├─bin/
│   ├─app
│   └─util
└─docs/
  └─readme.md
text

ユーザーは docs/ を作った後に bin/ を作り、途中で docs/readme.md を削除し、後から bin/tools を追加します。各ノードの生成と破棄の順序は完全に非同期的であり、関数のコールスタックのような「後入れ先出し(LIFO)」の順序を保ちません。

もし単一のデータスタックしか存在しない場合:

  • 伸長中の配列の途中に存在するノードだけを個別に削除することはできません。
  • 他のノードが生存している状態で、特定の要素のメモリだけを回収することができません。

この制約を解消するために設計されたのが、Gooseの slot_pool<T> と slice_pool<T> です。

2. 2層のプールアーキテクチャ:slot_pool と slice_pool#

slice_pool: 可変長子リストの連続管理slot_pool: 固定長ノードの割り当て管理Relative Reference: Link u32 innodesItems配列 (データスタック上のNode[>..])Freelist (解放済みスロット番号リスト)alloc_ref: 空きスロット再利用または Pushfree: スロット番号をFreelistへ返却リンク配列バッファ (Link[>..])Span Freelist (隣接空き領域の自動結合)alloc_slice または realloc_slice

1. slot_pool<T>:固定長要素のライフサイクル管理#

  • データスタック上の伸長配列(T[>..])と、解放済みスロット番号を保持する フリーリスト(Freelist) を組み合わせた構造体です。
  • alloc_ref(value): フリーリストに空きスロットがあれば、それを即座に再利用します。空きがなければスタックポインタを進めて(push)新しいスロットを確保します。
  • free(slot): メモリをOSに返却することはしません。スロット番号をフリーリストに登録し、次回の alloc_ref で再利用できるようにマークするだけです。

2. slice_pool<T>:可変長の連続配列(スライス)の管理#

  • ディレクトリ内の子要素リストなど、サイズが変化する連続要素列を管理します。
  • 主な操作関数:alloc_slice(n)、realloc_slice(s, n)、free_slice(s)。
  • スライスが解放されると、隣接する空きスパン同士を自動的にマージ(結合)し、OSのヒープを介さずにメモリ断片化を防止します。

3. 最大の安全装置:Type-Safe Reuse(型安全な再利用)#

C/C++における free() が危険とされる最大の理由は、解放されたメモリ領域がOSによって回収され、別のプロセスや全く異なるデータ型として再割り当てされる点にあります。古いポインタ(stale pointer)が誤ってそこを読み書きした場合、クラッシュ(Segfault)や遠隔コード実行(RCE)の脆弱性 を引き起こします。

Gooseは Type-Safe Reuse という設計原則によってこの問題を解決しています。

Goose slot_pool: 型安全な再利用C / C++: ダングリングポインタとクラッシュNode確保 (malloc)Node解放 (free)メモリがOS回収または別型へ再割り当て古いポインタ参照: Segfault や脆弱性スロット確保 (alloc_ref)スロット返却 (free)メモリはスタック上にそのまま保持古い参照を誤読: 型Tの有効な別データが得られる (安全)

[!TIP] Gooseの安全性ルール: プール全体のスコープが生きている限り、個別のスロットのメモリがOSへ解放されることはありません。万が一、解放済みのスロットを指す古い参照を読み取ったとしても、そこに存在するのは 型 T として完全に整合性のとれた正規のデータ です。論理的な不具合(ロジックバグ)にはなり得ますが、メモリ破壊や任意コード実行のセキュリティホールになることは物理的にあり得ません。

4. 実践:N分木ディレクトリ構造の構築(26_file_tree.goose)#

Goose公式リポジトリのサンプルコードをもとに、2つのプールがどのように連携するかを見てみましょう。

設計のメリット:#

  1. わずか4バイトの超狭ポインタ(Node&<u32 in nodes>?): 通常の8バイトポインタではなく、nodes プールの先頭からの32ビット相対オフセット(4バイト)のみを格納します。0 はそのまま null(?)として扱われます。
  2. CPUキャッシュに優しい連続配置: ディレクトリの子要素リストはフラットなスライス Link[:] としてメモリ上に隙間なく並びます。走査時にポインタをあちこちジャンプする必要がなく、L1/L2キャッシュ効率が極限まで高まります。
  3. その場伸長(In-Place Expansion): realloc_slice はスライスの直後に空きがあればその場で拡張します。後方に別データが詰まっている場合のみ、空き領域へ移動させ、旧領域をフリーリストへ返却します。
  4. OSヒープ割り当てはゼロ: 数百万ノードの木構造であっても、事前に確保された2つのデータスタック上だけで完結します。ツリー全体のスコープを抜けた瞬間、2回のCPUストア命令だけで数百万要素が一斉に破棄されます。

5. 循環参照グラフ(Cyclic Graphs)の実装#

Rustではボローチェッカーの制限により、ノード間の循環参照(A ➔ B ➔ C ➔ A)を作るのは非常に骨の折れる作業です。C++では std::shared_ptr の循環参照によるメモリリークが頻発します。

Gooseでは、何ら特別な細工なしに循環参照グラフを極めて自然に記述できます。

すべての頂点は vertices プールに、すべてのエッジは edges プールに格納されます。スコープ終了時にプール単位で一括破棄されるため、循環参照による解放漏れは絶対に起こりません。

6. 各言語におけるグラフ・木構造管理の比較#

比較項目C++ (std::shared_ptr)Rust (Rc<RefCell<T>>)Rust (SlotMap + Id)Goose (slot_pool + slice_pool)
構文の直感性複雑、循環リークのリスク大非常に冗長、実行時パニックの危険インデックス手動管理の手間自然な参照構文(.=)
リンクのサイズ16バイト(ptr + 制御ブロック)16バイト(ptr + 強弱参照カウント)8バイト(Index + Generation)4バイト(Node&<u32>)
割り当てコストノードごとにヒープ確保ノードごとにヒープ確保補助配列の拡張ポインタ前進のみ(O(1)O(1))
破棄コスト参照カウントを順次減算参照カウントを順次減算配列のDropスコープ終了時の単一命令
循環リーク耐性❌ weak_ptr なしでは漏洩❌ Weak なしでは漏洩✅ Map破棄時に解放✅ 漏洩の可能性ゼロ

7. まとめ#

Gooseの メモリプール機構 は、システム言語が「データ構造の自由度」と「確実なメモリ安全性」を両立できることを鮮やかに示しています。

  1. 循環グラフの回収にガベージコレクタは不要。
  2. ノード間の自由な相互リンクに過剰なボローチェッカーの制約は不要。
  3. 断片化やロック競合を招くOSヒープアロケータは不要。

静的データスタック、slot_pool、そして 4バイト相対参照 を組み合わせることで、Gooseは柔軟なデータ構造と極限のキャッシュパフォーマンスを同時に手に入れています。

参考文献#