Gooseの非階層的メモリ管理:slot_poolでグラフを作る
ヒープもGCもないGooseで、生存期間が階層化しない木構造やグラフをどう構築するのか?slot_poolとslice_poolの仕組みを解説。
前回の記事では、汎用ヒープアロケータを完全に排除し、ガベージコレクタ(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.mdtextユーザーは docs/ を作った後に bin/ を作り、途中で docs/readme.md を削除し、後から bin/tools を追加します。各ノードの生成と破棄の順序は完全に非同期的であり、関数のコールスタックのような「後入れ先出し(LIFO)」の順序を保ちません。
もし単一のデータスタックしか存在しない場合:
- 伸長中の配列の途中に存在するノードだけを個別に削除することはできません。
- 他のノードが生存している状態で、特定の要素のメモリだけを回収することができません。
この制約を解消するために設計されたのが、Gooseの slot_pool<T> と slice_pool<T> です。
2. 2層のプールアーキテクチャ:slot_pool と slice_pool#
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 という設計原則によってこの問題を解決しています。
[!TIP] Gooseの安全性ルール: プール全体のスコープが生きている限り、個別のスロットのメモリがOSへ解放されることはありません。万が一、解放済みのスロットを指す古い参照を読み取ったとしても、そこに存在するのは 型
Tとして完全に整合性のとれた正規のデータ です。論理的な不具合(ロジックバグ)にはなり得ますが、メモリ破壊や任意コード実行のセキュリティホールになることは物理的にあり得ません。
4. 実践:N分木ディレクトリ構造の構築(26_file_tree.goose)#
Goose公式リポジトリのサンプルコードをもとに、2つのプールがどのように連携するかを見てみましょう。
// nodes プール基準の 4 バイト狭相対参照
type Link = Node&<u32 in nodes>?;
struct Node {
name: u8[..15], // 15バイト以下のインライン固定長文字列
entries: Link[:], // 子ノード群への連続スライスのリンク
}
// 2つのメモリプールを定義
reusable var nodes: Node[>..] = [];
reusable[] var runs: Link[>..] = [];
// プール内にノードを生成する関数
fn make(name: u8[:]) -> Node& {
return nodes.alloc_ref(Node {
name: name,
entries: runs.alloc_slice(0)
});
}
// ルートディレクトリを作成
let root .= make("/");
// ディレクトリに子要素リンクを追加
fn link(dir: Node&, n: Node&) {
let k = dir.entries.len;
// runs プール内でスライスを再割り当て
dir.entries = runs.realloc_slice(dir.entries, k + 1);
dir.entries[k] .= n;
}
// ファイルまたはフォルダを追加
fn add(dir: Node&, name: u8[:]) -> Node& {
let n .= make(name);
link(dir, n);
return n;
}
// 自然にツリーを拡張
let home .= add(root, "home");
let user .= add(home, "alice");
let doc .= add(user, "project.txt");rust設計のメリット:#
- わずか4バイトの超狭ポインタ(
Node&<u32 in nodes>?): 通常の8バイトポインタではなく、nodesプールの先頭からの32ビット相対オフセット(4バイト)のみを格納します。0はそのままnull(?)として扱われます。 - CPUキャッシュに優しい連続配置:
ディレクトリの子要素リストはフラットなスライス
Link[:]としてメモリ上に隙間なく並びます。走査時にポインタをあちこちジャンプする必要がなく、L1/L2キャッシュ効率が極限まで高まります。 - その場伸長(In-Place Expansion):
realloc_sliceはスライスの直後に空きがあればその場で拡張します。後方に別データが詰まっている場合のみ、空き領域へ移動させ、旧領域をフリーリストへ返却します。 - OSヒープ割り当てはゼロ: 数百万ノードの木構造であっても、事前に確保された2つのデータスタック上だけで完結します。ツリー全体のスコープを抜けた瞬間、2回のCPUストア命令だけで数百万要素が一斉に破棄されます。
5. 循環参照グラフ(Cyclic Graphs)の実装#
Rustではボローチェッカーの制限により、ノード間の循環参照(A ➔ B ➔ C ➔ A)を作るのは非常に骨の折れる作業です。C++では std::shared_ptr の循環参照によるメモリリークが頻発します。
Gooseでは、何ら特別な細工なしに循環参照グラフを極めて自然に記述できます。
struct Vertex {
id: i32,
neighbors: VertexLink[:]
}
type VertexLink = Vertex&<u32 in vertices>?;
reusable var vertices: Vertex[>..] = [];
reusable[] var edges: VertexLink[>..] = [];
fn create_vertex(id: i32) -> Vertex& {
return vertices.alloc_ref(Vertex {
id: id,
neighbors: edges.alloc_slice(0)
});
}
fn add_edge(from: Vertex&, to: Vertex&) {
let k = from.neighbors.len;
from.neighbors = edges.realloc_slice(from.neighbors, k + 1);
from.neighbors[k] .= to;
}
// 有向トライアングル(循環)を作成: A -> B -> C -> A
let vA .= create_vertex(1);
let vB .= create_vertex(2);
let vC .= create_vertex(3);
add_edge(vA, vB);
add_edge(vB, vC);
add_edge(vC, vA); // エラーなし、安全に循環グラフが構築可能!rustすべての頂点は 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>) |
| 割り当てコスト | ノードごとにヒープ確保 | ノードごとにヒープ確保 | 補助配列の拡張 | ポインタ前進のみ() |
| 破棄コスト | 参照カウントを順次減算 | 参照カウントを順次減算 | 配列のDrop | スコープ終了時の単一命令 |
| 循環リーク耐性 | ❌ weak_ptr なしでは漏洩 | ❌ Weak なしでは漏洩 | ✅ Map破棄時に解放 | ✅ 漏洩の可能性ゼロ |
7. まとめ#
Gooseの メモリプール機構 は、システム言語が「データ構造の自由度」と「確実なメモリ安全性」を両立できることを鮮やかに示しています。
- 循環グラフの回収にガベージコレクタは不要。
- ノード間の自由な相互リンクに過剰なボローチェッカーの制約は不要。
- 断片化やロック競合を招くOSヒープアロケータは不要。
静的データスタック、slot_pool、そして 4バイト相対参照 を組み合わせることで、Gooseは柔軟なデータ構造と極限のキャッシュパフォーマンスを同時に手に入れています。