旧石器時代のポインタをご利用の皆様へ～provenance入門～

現代のプログラミング言語ではポインタは単なるアドレスではなく，provenanceを伴った参照として扱われています．知識をアップデートしましょう．

概要

ポインタは単なるアドレスではありません．
ポインタにはprovenanceという，どのオブジェクト由来かの情報が含まれています．
Provenanceを使うことで，最適化が効きやすくなったり，堅牢なプログラムを書きやすくなったりします．

ポインタはアドレスではない

次のCプログラムを見てみましょう．

#include <stdio.h>
#include <string.h>

int main() {
    int a = 100;
    int b = 200;
    
    int *p = &a + 1;
    int *q = &b;
    printf("p = %p, q = %p, (p == q) = %d\n", p, q, p == q);
    if (p == q) {
        printf("p == q!\n");
    }
    
    printf("a = %d, b = %d", a, b);
}

このコードをGCC 10.1.0で実行すると次の結果が得られます．

p = 0x7ffd5d140d1c, q = 0x7ffd5d140d1c, (p == q) = 0
a = 100, b = 200

注目すべき点は，ポインタpとqがそれぞれ0x7ffd5d140d1cという同じアドレス値¹をとっているのにも関わらず，p == qという比較が偽を返している(pとqとが異なるポインタである)ということです．つまり，ポインタの等しさにはアドレス以外の何者かが関わってくるのです！

それはポインタのprovenance(由来)と呼ばれるものです．provenanceはポインタがどのオブジェクトから由来するものかを表します．さきほどのプログラムの場合はポインタpのprovenanceは変数a，ポインタqは変数bとなっています．ポインタのprovenanceが異なっているため，pとqは(たとえアドレスが同じでも)異なるポインタと判定されるのです．

注意しなければならないのは，このようなprovenanceを用いた推論は既に行われているという点です．文書としての初出は2004年です．これはC20の提案などではなく，10年以上続いている現状なのです²．

Provenanceの何が嬉しいのか

最適化能力の向上

コンパイラはprovenance情報をポインタのエイリアス解析に活用しています．つまり，provenanceを解析することでポインタを経由した読み込み/書き込みの影響範囲を計算でき，この情報によって最適化が可能かどうかより正確に判定できるようになります．例えば，次の関数

int func(int *p) {
    int x = 100;
    *p = 300;
    return x;
}

は直観的には

int func2(int *p) {
    *p = 300;
    return 100; // xの値を伝播させた
}

と最適化することができそうです．この最適化を正当化するためには「ポインタpが変数xを指すことは無い」ということを証明する必要があります．

ここで，ポインタを単なるアドレスと同一視した場合，

func((int*)rand()); // たまたまxのアドレスが出てしまった！

というケースが存在するのでfunc → func2の最適化が不正なものとなってしまいます．

一方で，provenanceを使った場合は(int*)rand()がxのprovenanceを持つことはありません(まだxが登場していないため)．ですから，func → func2という最適化が正当化できます．

サニタイザの強化

ポインタのprovenanceは「オブジェクトを指すもの」としてのポインタを捉えた概念です．これを活用することでプログラムの堅牢性を向上させることもできるかもしれません．

サニタイザはプログラムが不正な動作を起こしていないかどうか実行時にチェックするツールです． AddressSanitizerやValgrindといったサニタイザを利用することで，バッファオーバーフローやメモリリークといったバグを検出することが可能です．

ですが，サニタイザは全てのバグを検出できるわけではありません．この記事の最初に取り上げたプログラムの場合，ポインタpは大元の変数aの範囲からははみ出ていますから，ある意味でバッファオーバーフローが起きていると言えます³．しかし，ポインタpのアドレス値は変数bのアドレスであり，アドレスだけを見た場合はこのバッファオーバーフローは検出できません．

しかし，ポインタのprovenanceも考慮した場合，ポインタpは変数aの範囲内に収まっていなければならないということがサニタイザからも分かるので，バッファオーバーフローの検出が可能です．

このようなサニタイザは既に登場しつつあります．例えば，RustのMIRIインタプリタにはサニタイザが標準搭載されており，未初期化メモリやダングリングポインタといった典型的な未定義動作だけではなくprovenance的な未定義動作の検出⁴も可能です． MIRIインタプリタはRust Playgroundからも簡単に実行でき，unsafe Rustを書く人々に重用されています．C言語にも同様のサニタイザが導入される未来は想像に難くありません．

更に詳しく

ポインタのprovenanceの取り扱いは確定したとは言い難く，プログラミング言語研究における最先端の一つと言えるでしょう．例えば，次のような問題に答えていく必要があります．

ポインタをmemcpyしたときのprovenanceはどうなる？
ポインタ↔整数キャストの場合は？
MMIO等特殊なポインタの取り扱いは？

気になる方は次の文献をチェックしてみるのはいかがでしょうか．

Ralf Jung (Rust研究者)のブログ．分かりやすいのでオススメ
- Pointers Are Complicated, or: What's in a Byte?
- "What The Hardware Does" is not What Your Program Does: Uninitialized Memory
C2xへのprovenance提案
自分もいくつかprovenance関連の論文メモを残しています

謝辞

素晴らしいタイトルを提供してくれた親友に感謝します．

アドレス値自体は実行ごとに変わります． ↩
C2xへのprovenance提案は現状を明文化するものと捉えるのが良いでしょう． ↩
厳密には1個先のアドレスはアクセスしない限り大丈夫なはずですが，ここでは問題があるということにします． ↩
Rustの場合はprovenanceではなくStacked Borrowsと呼ばれる定式化を用いて参照の由来を表現しています． ↩

pandaman64/pointers_in_Paleolithic_age.md

旧石器時代のポインタをご利用の皆様へ ～provenance入門～

概要