Upgrade to Pro — share decks privately, control downloads, hide ads and more …

C言語プログラムの構造とほんの少し解釈

 C言語プログラムの構造とほんの少し解釈

Kernel/VM探検隊online part3 発表資料

Keisuke Nishimura

July 10, 2021
Tweet

More Decks by Keisuke Nishimura

Other Decks in Research

Transcript

  1. 背景:大規模なコードのメンテは難しい Linuxでの実例:kmalloc()のメモリ確保とmemset()の ゼロクリアをkzalloc()に置換したい.どうする? fh = kmalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh)

    { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } memset(fh, 0, sizeof(struct zoran_fh)); fh = kzalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh) { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } New API : kzalloc (=kmalloc + memset) OLD NEW (from 2.6.14) 例
  2. 背景:大規模なコードのメンテは難しい Linuxでの実例:kmalloc()のメモリ確保とmemset()の ゼロクリアをkzalloc()に置換したい.どうする? fh = kmalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh)

    { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } memset(fh, 0, sizeof(struct zoran_fh)); fh = kzalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh) { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } New API : kzalloc (=kmalloc + memset) OLD NEW (from 2.6.14) 例 難しさ 1 そもそもコードが大規模で 人力は厳しい.
  3. 背景:大規模なコードのメンテは難しい Linuxでの実例:kmalloc()のメモリ確保とmemset()の ゼロクリアをkzalloc()に置換したい.どうする? fh = kmalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh)

    { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } memset(fh, 0, sizeof(struct zoran_fh)); fh = kzalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh) { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } New API : kzalloc (=kmalloc + memset) OLD NEW (from 2.6.14) 例 難しさ 1 そもそもコードが大規模で 人力は厳しい. 難しさ 2 全て修正したとして,それを パッチとして投函?
  4. 背景:大規模なコードのメンテは難しい Linuxでの実例:kmalloc()のメモリ確保とmemset()の ゼロクリアをkzalloc()に置換したい.どうする? fh = kmalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh)

    { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } memset(fh, 0, sizeof(struct zoran_fh)); fh = kzalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh) { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } New API : kzalloc (=kmalloc + memset) OLD NEW (from 2.6.14) 例 難しさ 1 そもそもコードが大規模で 人力は厳しい. 難しさ 2 全て修正したとして,それを パッチとして投函? 難しさ 3 (C言語の文法の範囲で) 色々なバリエーションが存在
  5. 背景:大規模なコードのメンテは難しい Linuxでの実例:kmalloc()のメモリ確保とmemset()の ゼロクリアをkzalloc()に置換したい.どうする? fh = kmalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh)

    { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } memset(fh, 0, sizeof(struct zoran_fh)); fh = kzalloc(sizeof(struct zoran_fh), GFP_KERNEL); if (!fh) { dprintk(1,KERN_ERR"%s: zoran_open(): … ¥n", ZR_DEVNAME(zr)); return -ENOMEM; } New API : kzalloc (=kmalloc + memset) OLD NEW (from 2.6.14) 例 難しさ 1 そもそもコードが大規模で 人力は厳しい. 難しさ 2 全て修正したとして,それを パッチとして投函? 難しさ 3 (C言語の文法の範囲で) 色々なバリエーションが存在 難しさ 4 カッコの対応などは 拡張正規表現で扱いにくい.
  6. 解決策: Semantic Patch Semantic Patch Language (SmPL) で変更を記述 ✓WYSIWYG スタイルで変換ルールを直感的に記述可能

    ✓メタVariableやメタExpressionを使用した柔軟な表現 ✓C言語の文法を考慮したマッチング @@ expression E1,E2; @@ -x=kmalloc(E1,E2); +x=kzalloc(E1,E2); ... -memset(x,0,E1);
  7. 解決策: Semantic Patch Semantic Patch Language (SmPL) で変更を記述 ✓WYSIWYG スタイルで変換ルールを直感的に記述可能

    ✓メタVariableやメタExpressionを使用した柔軟な表現 ✓C言語の文法を考慮したマッチング @@ expression E1,E2; @@ -x=kmalloc(E1,E2); +x=kzalloc(E1,E2); ... -memset(x,0,E1); 任意のExpressionにマッチング
  8. 解決策: Semantic Patch Semantic Patch Language (SmPL) で変更を記述 ✓WYSIWYG スタイルで変換ルールを直感的に記述可能

    ✓メタVariableやメタExpressionを使用した柔軟な表現 ✓C言語の文法を考慮したマッチング @@ expression E1,E2; @@ -x=kmalloc(E1,E2); +x=kzalloc(E1,E2); ... -memset(x,0,E1); ここでの“...”はC言語の任意の statementsに最小マッチング
  9. Coccinelle: SmPLの実行エンジン C言語プログラムのマッチングと変換ツール [EuroSys ‘08] @@ expressionx,E1,E2; @@ -x=kmalloc(E1,E2); +x=kzalloc(E1,E2);

    ... -memset(x,0,E1); Semantic Patch C言語のコード (e.g. Linux) 変換されたコード Coccinelle Logo: https://isc.tamu.edu/~lewing/linux/
  10. Coccinelleの性能 [ATC ‘18] • 性能向上の工夫点 • Parmapによる並列実行 • SmPLから抽出したキーワードでgrep (内部実装)

    • 関数名や文字列等が特定のものだと,かなり性能に寄与 • まだつらい点 • 巨大プロジェクトは巨大(e.g. Linuxは16M LoC以上) • パースとバックトラックが遅い
  11. Coccinelleの応用: バグの検出 • Linuxのバグ検出 [ASPLOS ‘11] • Linux 2.4.1 /2.6.x

    を対象に典型的なバグの存在を静的解析 • Linux 2.6.33 に対して 736 のバグを報告 • 従来の 「OSはドライバにバグが多い」という主張 [SOSP ‘01] は比較的新しいLinux 2.6.xにも当てはまるが,さらにHALレイ ヤの方がコードに対するバグが多いことを指摘 • OpenSSLのバグ検出への応用 [EDCC’10] • OpenSSLの特定の関数の返り値のチェックが不十分な問題 • そういった関数はソースコード全体に分散 • Coccinelleで機械的にチェックして 30 以上のバグを発見
  12. その他 • 関連プロジェクト • Coccinelle4j [ECOOP ‘19] : Java向けのCoccinelle •

    Spoon:同じくJava向けでSmPLを扱える. • Semgrep:マッチングのみ,多言語対応 • Difftastic:マッチングのみ,トークン単位で比較 … • 開発体制 • 公式リポジトリ https://gitlab.inria.fr/coccinelle/coccinelle • 開発言語:OCaml • ライセンス:GPLv2 • メイン開発機関:INRIA • 使用プロジェクト:Linux, QEMU, systemd etc...
  13. まとめ • Coccinelle/SmPLによる大規模ソースコードの管理 • Coccinelleの仕組み • CTL-VWによるモデルチェック • CPPも直接ASTに変換 •

    その他難しい点/性能 • Coccinelleの現在 • Linuxへのコミット 5000 ~ • バグ検出への応用
  14. 参考文献 1/2 [ATC ‘18] Lawall, Julia, and Gilles Muller. “Coccinelle:

    10 years of automated evolution in the Linux kernel.” USENIX ATC 2018 [ASPLOS ‘11] Palix, Nicolas, et al. “Faults in Linux: Ten years later.” ASPLOS 2011. [POPL ‘09] Brunel, Julien, et al. “A Foundation for Flow-Based Program Matching Using Temporal Logic and Model Checking.” POPL 2009 [EuroSys ‘08] Padioleau, Yoann, et al. “Documenting and automating collateral evolutions in Linux device drivers.” EuroSys 2008
  15. 参考文献 2/2 [EDCC’ 10] Lawall, Julia, et al. "Finding error

    handling bugs in OpenSSL using Coccinelle.“ EDCC ’10 [SOSP ‘01] Chou, Andy, et al. "An empirical study of operating systems errors." SOSP 2001. [ECOOP ‘19] Kang, Hong Jin, et al. “Semantic patches for Java program transformation (experience report)” ECOOP 2019 [CC ‘09] Padioleau, Yoann. "Parsing C/C++ code without pre- processing." International Conference on Compiler Construction. Springer, Berlin, Heidelberg, 2009.