ハクソク

世界を動かす技術を、日本語で。

Cの出所メモリモデル

329日前原文(gustedt.wordpress.com)

概要

  • C言語 における ポインタの由来（provenance） に基づく新しいメモリモデルの紹介
  • ISO/IEC TS6010 として国際標準化された技術仕様の意義
  • ポインタエイリアス解析 が最適化と安全性に与える影響
  • エイリアス解析の課題と、 provenance model による解決策
  • 最適化機会とバグ回避のための 実践的指針

C言語のためのProvenance Memory Model

  • Kayvan Memarian （Cambridge）、 Peter Sewell （Cambridge）、 Martin Uecker （Graz）、 Jens Gustedt （ICube/Inria）らによる 長年の共同研究
  • C言語コミュニティ が合意した pointer provenance （ポインタの由来）という概念の導入
  • プログラム実行中に ポインタ値の起源追跡 を数学的に厳密に定義
  • 曖昧だった従来の C標準 の仕様を補完する技術仕様（ISO/IEC TS6010）
  • C/C++/Rust/コンパイラ 分野での議論や実装の指針

ポインタエイリアスとプログラム最適化

  • ポインタpとqが同じメモリオブジェクトを指す場合、「エイリアス」 と呼ぶ

  • エイリアスの有無は プログラム最適化 に直接影響

  • 例：逆数近似関数（recip）では、2つのポインタ引数が

    • 異なるオブジェクト を指す場合
    • 同じオブジェクト を指す場合

  • 最適化版recip（recip⁺）は、 エイリアスがない前提 でのみ安全に動作

    • ローカル変数への読み出し・書き込みの最適化 が可能

  • エイリアスの可能性がある限り、コンパイラは大胆な最適化を自動で適用できない

    • メモリアクセスの最適化が制限
    • 本質的に異なるアルゴリズム となるリスク

  • エイリアス解析 は、どのポインタが同一オブジェクトを指すかを静的に解析する技術

    • 誤った仮定 による最適化は、バグや未定義動作の原因

    • 現代のコンパイラ における最重要解析の一つ

Provenance Modelの意義と標準化

  • ISO/IEC TS6010 による公式な技術仕様化
    • Henry Kleynhans （Bloomberg）編集
  • 情報システムの安全性・セキュリティ向上 を目的とした指針
  • ポインタの由来 に基づく一貫したメモリモデルの普及
  • 業界全体でのプラットフォーム・ツールの収束 を促進

実践的な指針とまとめ

  • エイリアスの意図を明確に

    • 同じオブジェクトを指す可能性がある場合、 仕様や実装で明示

  • restrict修飾子 など、コンパイラにヒントを与える手法の活用

  • provenance model の理解と活用による、最適化機会の最大化とバグ回避

  • プログラムの可読性・保守性 の向上

    • 安全で効率的なCプログラム設計 への道筋

Hackerたちの意見

Cは今、Unicode識別子を許可してるの？それともこれは擬似コード？コードスニペットには&も含まれてるから、HTMLへの変換で何かがうまくいかなかったみたい。

└

cppreferenceからの引用: 「識別子は、桁、アンダースコア、小文字と大文字のラテン文字、そしてUnicode文字の任意の長いシーケンスで、\uおよび\Uエスケープ表記を使って指定される（C99以降）、クラスXID_Continue（C23以降）。有効な識別子は、数字以外の文字（ラテン文字、アンダースコア、またはUnicodeの数字以外の文字（C99以降）（C23まで）、またはクラスXID_StartのUnicode文字（C23以降））で始まらなければならない。識別子は大文字と小文字を区別する（小文字と大文字は異なる）。すべての識別子は正規化形式Cに準拠しなければならない（C23以降）。実際にはコンパイラに依存する。」

└

投稿が見れないんだけど、ページがJSONみたいな内容管理システムのようになってて、白地にピンクで表示されてる。めっちゃ混乱してる。:| あなたの質問への答えは（まだ）「いいえ」みたいだね。

└

C23に関する兄弟コメントの他にも、GCCではちゃんと動くよ。https://godbolt.org/z/qKejzc1Kb 一方、clangは大きな声で文句を言ってるね、https://godbolt.org/z/qWrccWzYW

└

C99までは実装依存だったけど、C99以降はUCNsを使えば明示的に可能になったし、C23からは明示的なエンコーディングで可能になったけど、リテラルはまだ実装依存なんだよね。

おそらくこれはマークダウンか何かから変換されたもので、変換が部分的に失敗したか、入力が壊れてるね。PVIセクション以降はなんとか復旧してるけど、もし著者がこれを見てたら、投稿を修正して再変換してほしいな。編集したけど、いや、もっと後の方にもエラーがある。投稿する前にちゃんと校正が必要だったと思う。自分はこのトピックを知ってるからなんとか理解できるけど、新しい人に紹介するつもりだったら、かなり混乱するだろうね。

└

問題は、WordPressがどこかを編集するとこれらの設定が変わっちゃうことだよ。多分、全部再生成することになると思う。

コードブロックが正しく閉じられてないみたい、これより前のフレーズ: > 関数 recip と recip⁺ は同等ではない その後の数段落がコードブロックに飲み込まれちゃった。編集: あ、この記事が「Modern C」の著者によるものだって気づかなかった。いろんなところでおすすめされてるのを見たことある。 > Modern CのC23版は、今、無料でダウンロードできるよ https://hal.inria.fr/hal-02383654

└

いい本だよ。最新の版じゃなくて、第二版の方が好きかな。いわゆる「肥大化したC」はちょっと苦手。

└

コードサンプルを見た瞬間、ジェンだってすぐに分かったよ。

└

コードブロックがちゃんと閉じてないみたいだね。今は修正されたみたい。

これを見てる人には、最近統合されたLLVMの型ベースエイリアシングサニタイザーTySanも興味深いかもね: https://clang.llvm.org/docs/TypeSanitizer.html https://www.phoronix.com/news/LLVM-Merge-TySan-Type-Sanitize...

└

現在、TySanはLLVMが悪用できるエイリアス違反しか捕まえられないってことは、覚えておく価値があるかも。例えば、ユニオンのような型では、Clangが正確な型ベースのエイリアス情報を出さないから、TySanはそれを捕まえられないんだよね。

うわぁ。C言語でユニコードの変数名が使えるようになったの？それはひどいね。

└

「今」っていうのはC99から、つまり25年前のことだよ。あの時はいいアイデアだと思ったけどね。

└

ひどい？もし君の（人間の）言語が違うアルファベットを使ってたら、そうは思わないかもね。

└

なんでダメなの？もう2000年代じゃないし、ユニコードのサポートは普遍的だよ。これを表示できないような古い技術を引っ張り出さないといけないね。ソースコードは人間のためのものだから、読みやすく書きやすく理解しやすい方法で書かれるべきだよ。もし君の言語がASCIIにマッピングできないなら、ユニコードのサポートがその目標を改善するんだ。もし君のコードが物理の公式を直接実装するためのものであれば、適切なユニコード文字を使うことで読みやすくなるかもしれないし（それによって転写ミスを見つけやすくなる、これは物理シミュレーションでよくあることだよね）。

└

数学系の人にはコードを書く権利なんてないと思う。ユニコードのせいじゃなくて、変数名がめっちゃ短すぎるのが問題なんだよね。

└

void recip(double* aₚ, double* řₚ) > { > for (;;) > { > register double Π = (aₚ)(řₚ); これを見たとき、最初に思ったのは「これは物を作る人たちの記事なのか、それとも何も作らない“学者”のものなのか」ってこと。まあ、すぐに答えが出てよかったけど。

MarkdownからWordPress内部へのランダムな翻訳エラーは、今修正されたはず。ご迷惑をおかけしました！

ざっと見た感じ、オブジェクト表現の読み書きに関する露出/合成については気になることがあるね。結果として、デッド整数ロードは排除できないんだ。なぜなら、露出の副作用があるかもしれないから。Cは厳密なエイリアスルールとの相互作用でうまくやれるかもしれないけど、ここで合意に逆らっているのには驚きだよ（これが実装者に採用される可能性を減らしているし）。

└

（気にしないで、最初にコメントを読み間違えた。）そう、表現へのアクセスについては議論が必要だね…この文書を公開するのに数年かかったよ。もっと重要なのは、ptr2intの露出が実装できるかどうかだね。

└

Cは厳密なエイリアスルールとの相互作用でうまくやれるかもしれないけど、char型のアクセスではそうはいかない。さらに大きな型でも、ポインタ型のメモリから整数型のメモリにmemcpyしてから整数をロードする組み合わせについて心配しなきゃいけないと思う。デッド整数ロードを排除するなら、memcpyを排除しないといけないね。

└

これに対してどんなコンセンサスがあるのか、もう少し詳しく教えてくれる？

残念ながら、どのCコンパイラもこの最適化を自動的に行うことはできない: > 関数recipとrecip⁺は同等ではない。これは、最適化されたコードが可読性や堅牢性を向上させる例の一つだね。最初の実装では、副作用が関数の結果を変えることができる。でも問題なのは、ループの途中で誰かが値を変更することを期待して書かれていないコードだってこと。これは間違った挙動で、そのせいでパフォーマンスにも悪影響が出る。ファンクショナルコアのコードはこの問題が少ないんだ。データのスナップショットを渡して、答えかエラーが返ってくるだけだから。ユーザーがまだログインしているか、タスクを実行する権限があるかを3回もチェックするコードを見たことがあるけど、最初の呼び出しで一つの答え、次の呼び出しで別の答えに対応するように設定されているものは一つもなかった。結局、未定義の挙動に突入しちゃうんだよね。

この記事を読んで、mallocの上に独自の異種割り当てスキーム（例えばTLSF）を実装したらどうなるんだろうって考えちゃった。そうすると、すべてのオブジェクトが同じmallocされたストレージ領域に属することになるよね。オブジェクトのオフセットは生ポインタを使って計算するけど、プロヴナンスは返された各オブジェクトを、まるで別々の独立したストレージから割り当てられたかのように扱う可能性があると思う。だから、私の質問は、このプロヴナンスモデルは、各レベルで「ストレージ」の別の概念を持つアロケーターの再帰的なネスティングを許可するの？

└

コンパイラはmallocについて知ってるから、mallocが返すポインタが他のポインタとエイリアスしないことも分かってるんだよね。あなたのコンパイラは、この点でmallocのように振る舞う関数をマークするための属性をサポートしているかもしれない。そうじゃないと、コンパイラは返り値が他のポインタとエイリアスする可能性があると仮定せざるを得なくなる。

ちょっと余談だけど、ここで紹介されているXORの二重リンクリストの例はめっちゃクールだね。