FIL-C の簡略化モデル

近年、Fil-C に関する多くの議論を目にします。Fil-C とは、C/C++ のメモリーセーフ実装を謳うプロジェクトです。その仕組みの詳細な内実は既にご存じの方も多いかと思いますが、初めて Fil-C に触れる方々には、簡略化されたモデルを紹介する価値があると考えます。一度この簡易版を理解すれば、本番向けの実装への理解のハードルは格段に低くなるからです。

現実の Fil-C では LLVM IR を書き換えるコンパイラパスが採用されていますが、ここではソースコードレベルで C/C++ コードを自動的に再記述するモデルを考えます。具体的には、セーフなコードへと不安全なコードの変換を行います。この変換的第一步として、各関数内のポインタ型ローカル変数のそれぞれについて、

AllocationRecord*

型の伴いローカル変数が追加されます。例えば：

元のソースコード:

void f() {
  T1* p1;
  T2* p2;
  uint64_t x;
  ...
}

Fil-C 変換後のコード:

void f() {
  T1* p1; AllocationRecord* p1ar = NULL;
  T2* p2; AllocationRecord* p2ar = NULL;
  uint64_t x;
  ...
}

ここで用いられる

AllocationRecord

の定義は、概ね以下の通りです：

struct AllocationRecord {
  char* visible_bytes;
  char* invisible_bytes;
  size_t length;
};

ポインタ型ローカル変数に対する単純な操作についても、

AllocationRecord*

を同時に扱うように書き換えられます：

元のソースコード:

p1 = p2;
p1 = p2 + 10;
p1 = (T1*)x;
x = (uintptr_t)p1;

Fil-C 変換後のコード:

p1 = p2, p1ar = p2ar;
p1 = p2 + 10, p1ar = p2ar;
p1 = (T1*)x, p1ar = NULL;
x = (uintptr_t)p1;

関数への引数渡しや戻り値の返送においても、元のポインタに加えて

AllocationRecord*

を含めた形でコードが書き換えられます。また、特定の標準ライブラリ関数の呼び出しについても、Fil-C 版のそれらに置き換えられます。これらを組み合わせると以下のような様相になります：

元のソースコード:

p1 = malloc(x);
...
free(p1);

Fil-C 変換後のコード:

{p1, p1ar} = filc_malloc(x);
...
filc_free(p1, p1ar);

ここで実装される簡略版の

filc_malloc

は、要求された割り当てだけでなく、実際には 3 つの異なるメモリ領域を割り当てます：

void* filc_malloc(size_t length) {
  AllocationRecord* ar = malloc(sizeof(AllocationRecord));
  ar->visible_bytes = malloc(length);
  ar->invisible_bytes = calloc(length, 1);
  ar->length = length;
  return {ar->visible_bytes, ar};
}

ポインタ変数のデレファレンスを行う際、伴う

AllocationRecord*

が境界チェックを実行するために利用されます：

元のソースコード:

x = *p1;
...
*p2 = x;

Fil-C 変換後のコード:

assert(p1ar != NULL);
uint64_t i = (char*)p1 - p1ar->visible_bytes;
assert(i < p1ar->length);
assert((p1ar->length - i) >= sizeof(*p1));
x = *p1;

...

assert(p2ar != NULL);
uint64_t i = (char*)p2 - p2ar->visible_bytes;
assert(i < p2ar->length);
assert((p2ar->length - i) >= sizeof(*p2));
*p2 = x;

処理がより複雑になるのは、格納または読み出す値そのものがポインタの場合です。前述のように、コンパイラはローカル変数のすべてに対して完全な制御と可視性を有しているため、各関数内のポインタ型ローカル変数については、必ず

AllocationRecord*

が伴うように自動的に挿入されます。一方、スタック上のローカル変数だけでなくヒープ上に存在するポインタに対しても同様の扱いを行うには困難を伴いますが、そこで活躍するのが

invisible_bytes

です：もし

visible_bytes + i

の位置にポインタが存在する場合、その伴う

AllocationRecord*

は

invisible_bytes + i

の位置にあります。換言すれば、

invisible_bytes

は要素型が

AllocationRecord*

である配列と見なせます。この配列に対する健全なアクセスを確保するためには、インデックス

i

が

sizeof(AllocationRecord*)

の倍数である必要があるという追加のロジックが存在します（以下では緑色で強調表示）：

元のソースコード:

p2 = *p1;
...
*p1 = p2;

Fil-C 変換後のコード:

assert(p1ar != NULL);
uint64_t i = (char*)p1 - p1ar->visible_bytes;
assert(i < p1ar->length);
assert((p1ar->length - i) >= sizeof(*p1));
assert((i % sizeof(AllocationRecord*)) == 0);
p2 = *p1;
p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i);

...

assert(p1ar != NULL);
uint64_t i = (char*)p1 - p1ar->visible_bytes;
assert(i < p1ar->length);
assert((p1ar->length - i) >= sizeof(*p1));
assert((i % sizeof(AllocationRecord*)) == 0);
*p1 = p2;
*(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar;

これまで見ていない

filc_free

の挙動についても触れます。これは、概ね以下のような動作を行います：

void filc_free(void* p, AllocationRecord* par) {
  if (p != NULL) {
    assert(par != NULL);
    assert(p == par->visible_bytes);
    free(par->visible_bytes);
    free(par->invisible_bytes);
    par->visible_bytes = NULL;
    par->invisible_bytes = NULL;
    par->length = 0;
  }
}

細心の注意を払う方におかれて、「

filc_malloc

では 3 つの割り当てが行われていたのに、

filc_free

で解放されているのはそのうち 2 つだけではないか？」と指摘されるかもしれません。これは意図的な設計であり、

AllocationRecord

オブジェクト自体は

filc_free

によって解放されません。この「ギャップ」を補完するのがガーベージコレクター（GC）の追加です。まさにその通りです：C/C++ に GC が付与されたシステムなのです。本番向けの Fil-C では並行して動作する増量型（incremental）コlector が採用されていますが、簡易モデルにおいてはスタッップザワールド（stop-the-world）型のコレクタで十分です。このコレクターは

AllocationRecord

オブジェクトを辿り、到達不能なものを解放します。さらに以下の 2 つの重要な役割も果たします：

1. 到達不能な

   AllocationRecord

   を解放する際に、それに対して

   filc_free

   を呼び出すこと。

2. AllocationRecord

   の長さが 0 であれば、その領域へのすべてのポインタは、長さ 0 の単一の標準的な

   AllocationRecord

   に変更されること。

第 1 の点は、Fil-C を使用している場合、解放の呼び出しを忘れたとしてもメモリーリークにはならないことを意味します：メモリは自動的に GC によって回収されるためです。ただし、これは「

free

を呼ぶことが無意味である」というわけではありません；実際、GC が選択するタイミングよりも早めにメモリを解放したい場合には、明示的に

free

を呼び出すことでその効果を得られるからです。第 2 の点については、何かに対して

free

を呼び出した後、伴う

AllocationRecord

は次第に到達不能となり、結果として自身がいつかは解放されることになります。

GC が存在すると、より積極的に利用したくなる誘惑が生まれます。そのような用途の一つとして、「ローカル変数のアドレスを取得することさえも安全に行える」ようにするのが挙げられます。すなわち、そのポインタがローカル変数の寿命を超えて使用されてしまう場合でも安全です。コンパイラがローカル変数のアドレスが取り出されていることを確認でき、かつそれがローカル変数の寿命を越えて漏洩しないと証明できない場合は、Fil-C の変換処理によって、該当地域はスタック割り当てからヘープ割り当て（

malloc

による）へと昇格されます。対応する

free

の挿入も不要です；GC がそれを処理するからです。

最後に強調したいのは、Fil-C 版の

memmove

です。この C 標準ライブラリの関数は恊意的にメモリを操作するため、コンパイラは当該メモリー領域内にどのようなポインタが存在するかを知り得ません。この問題を回避するためには、合理的なヒューリスティクスが必要です：任意のメモリー内にあるポインタは、完全にそのメモリー範囲内に収まっており、かつ適切なアラインメントを持たなければならない、という条件を課します。これにより興味深い結果が得られます：8 バイトのアラインメントされたデータを 1 つの

memmove

で移動する場合と、構成要素である各バイトに対して個別に 8 回の 1 バイト単位の

memmove

を行う場合では動作が異なります。前者の場合には対応する範囲の

invisible_bytes

もまた移動される一方、後者においてはそうはなりません。

以上の簡略モデルの説明至此で終了します。本番版の実装における追加的な複雑さとしては、以下のような項目があります：

• スレッド: 並行処理は GC をより複雑にします。また、解放するスレッドと下位レイヤーのメモリーをアクセスしようとする別のスレッドとの競合を防ぐため、

  filc_free

  は即座に何らかのオブジェクトを解放できません。ポインタに対する原子操作についても、通常のリソクリプタはポインタの読み取りや書き込みを 2 つのロード/ストアに展開するため、アトミック性を損なう恐れがある点で追加の処理が要ります。
• 関数ポインタ:

  AllocationRecord

  のメタデータには、

  visible_bytes

  ポインタが通常のデータではなく実行可能コードへのポインタであることを示すフラグが含まれています。関数ポインタ p1 経由での呼び出しでは、p1 == p1ar->visible_bytes が成立し、かつ p1ar が関数ポインタを表していることが確認されます。関数ポインタを介した型混同攻撃を防ぐためには、関数呼出の ABI もまた、型シグネチャが正しいことを検証する必要があります。その一つのアプローチとしては、すべての関数が同一の型シグネチャを受け取るように構成します：パラメータはすべて構造体の中にパッキングされ、メモリーを介して渡されるものとして扱われ、ABI の境界では各関数は単一の

  AllocationRecord

  （当該構造体に相当するもの）のみを受信すると仮定します。
• メモリー使用量の最適化:

  filc_malloc

  で即座に

  invisible_bytes

  を割り当てる代わりに、必要になった場合にオンデマンドで分配するというアプローチも魅力的です。また、

  AllocationRecord

  と

  visible_bytes

  を単一のメモリ領域に配置することも検討されます。下位レイヤーの

  malloc

  がすべての配列にメタデータを先頭に入れる場合、そのメタデータを

  AllocationRecord

  内に格納することも思いつきます。
• パフォーマンス最適化: Fil-C のメモリー安全性はパフォーマンスのコストを伴うため、失われたパフォーマンスの一部を取り戻すための様々な工夫が検討されます。

この基礎的な理解を踏まえ、最後に次の問いかけを残します：「Fil-C を使用するに適したシナリオとは何か？」個人的には以下のような回答となります：

• 大量の C/C++ コードがあり、動作は確認されているもののメモリー安全性については未検証であり、GC を導入し、大幅なパフォーマンス低下を許容する代わりにメモリー安全性を取得したい場合（例えば、Java や Go や Rust に書き換えるまでの暫定的な対策として）。
• ASan を使って C/C++ コードを実行してメモリーバグを検出するように、Fil-C 下でも同様に実行し、バグを発見できる。
• コンパイル時における型安全な物語が強く確立されている言語があり、かつコンパイル時言語とランタイム時の言語が同一である場合（例：Zig）であれば、ランタイム評価が不安全であっても、コンパイル時評価を安全に行うために Fil-C スタックアップを利用できる。

一部の研究者らはポインタの起源（provenance）についての考察を楽しんでいますが、もしこれまでこの概念に出会ったことがない方へ、以下のような「ネールサンパイプ」的な問いかけをしてみたい：p1 と p2 が同じ型であると仮定したとき、コンパイラが

if (p1 == p2) { f(p1); }

を

if (p1 == p2) { f(p2); }

に書き換えることは妥当でしょうか？Fil-C の答えは明確に「いいえ」です；それは関数 f に渡される

AllocationRecord*

がどれになるかを変更する bowiem からです。この性質から、Fil-C はポインタの起源（pointer provenance）を具体的に持つシステムの良い例となります。