Courgette アルゴリズムについて その1

6月ごろにCourgette のスタンドアローン化に取り組んだ記録を紹介した。

hiromi-mi.hatenadiary.jp

本稿からは Courgette のアルゴリズムの実際について説明していく。まず パッチ生成アルゴリズムの概要 について考える。

概要

パッチ生成アルゴリズムは以下の構成となっている。

Courgette はバイナリファイル中のアドレス情報を解析することで効率のよいパッチ生成を実現しているが、一口にアドレス情報といっても、 2種類に大別して扱われておりそれぞれ処理が異なる。

  • リロケーションテーブルにアドレスが保存されているもの: abs32
  • 分岐命令や CALL 命令中に含まれていて、相対アドレスの形で記述されているもの: rel32

また、便宜上旧バージョンのバイナリファイルを旧バイナリ, 新バージョンのバイナリファイルを新バイナリ とする。

  1. 旧バイナリと新バイナリを読み込む
  2. 旧バイナリ、新バイナリそれぞれについて、アドレス abs32, rel32 を取得する。バイナリファイル中のリロケーションテーブルを参照して abs32 を取得する。バイナリファイル中の .text を参照して jmp 命令列を切り出す
  3. 旧バイナリ、新バイナリそれぞれについて、abs32 の対応先アドレスを計算する
  4. 旧バイナリと新バイナリとの間で、 Adjustment を実行する
  5. 旧バイナリと新バイナリとの間で、bsdiff を走らせる
  6. bsdiff の結果と Adjustment 結果をパッチファイルとして保存する

このうち、Adjustment と呼ばれる、旧バイナリと新バイナリ同士の対応付け作業は他の作業から分離されており、ここではそれ以外の項について説明する。

前提

https://chromium.googlesource.com/chromium/src/+/21264cc9649f454255bdea9fae22342df25862d1/courgette/image_utils.h#20 にコメントがあるようにアドレス情報はさまざまな扱われ方をしており、場合によって適宜変換が行なわれている:

  • VA: バイナリファイルがロードされた際の仮想メモリ上のアドレス
  • RVA: バイナリファイルがロードされた際の仮想メモリ上のアドレスで、相対位置となったもの

また、呼出元アドレス情報の場合は ファイル開始地点からのそのアドレスがある位置へのオフセット (File Offset) として扱うこもある。

更に、TypedRVA, TypedRVAX86 は 呼出元アドレスのFile Offsetと呼出先アドレスの RVA, 命令長を一括で扱うためのクラスである。

abs32 命令取得

まずは簡単な abs32の命令取得について述べる。これは ELF のリロケーションテーブルを参照することで行い、DisassemblerElf32::ExtractAbs32Locations 関数 にて実装されている。

      // Loop through relocation objects in the relocation section
      for (int rel_id = 0; rel_id < relocs_table_count; ++rel_id) {
        RVA rva;
        // Quite a few of these conversions fail, and we simply skip
        // them, that's okay.
        if (RelToRVA(relocs_table[rel_id], &rva) && CheckSection(rva))
          abs32_locations_.push_back(rva);

セクションヘッダの SHT_REL にあるリロケーションテーブルを参照しつつ、そのセクションが境界内にあれば登録する形で行なっている。

rel32 命令取得

これは Windows 向けと Linux 向けで大幅に実装が異なる。本節では Linux (ELF)向けを前提に述べていく。

パッチ生成のためにはアドレスが書き変わりうる命令を見つける必要があり、具体的には以下の通りである。

  • JMP/CALL
  • MOV/LEA
  • JCC (JPO/JPE を除く)

具体的には、.text セクションごとに、ヒューリスティックに探索していく形でディスアセンブル処理を行なう。 disassembler_elf_32_x86.cc の151行目ソースコードがあり、バイナリ列で特定命令の並びを見つけ次第そのニーモニックをrel32候補として登録している。

    if (p + 5 <= end_pointer) {
      if (*p == 0xE8 || *p == 0xE9) {  // jmp rel32 and call rel32
        rel32 = p + 1;
      }
    }
    if (p + 6 <= end_pointer) {
      if (*p == 0x0F && (p[1] & 0xF0) == 0x80) {  // Jcc long form
        if (p[1] != 0x8A && p[1] != 0x8B)  // JPE/JPO unlikely
          rel32 = p + 2;
      }

この結果、false positive として実際には命令ではない部分が紛れこむことがある。そこで、DisassemblerElf32::IsValidTargetRVA 関数 で RVA が呼出先プログラム中のどこかに存在することを確認した上で、rel32 を登録している。

なお、 Windows 向けの実装は Rel32Finder, Rel32FinderX32, Rel32FinderX64 などにあり、以下のソースコードからたどることができる。 chromium.googlesource.com

abs32, rel32 の対応先アドレスを計算する

この時点では、abs32 の対応先アドレスは登録されていないなど、Adjustment で利用するために不十分な情報しか取得できていない。

DisassemblerElf32::ParseFile 関数 にて対応先アドレスを計算し、EncodedProgram として作成する。

具体的には、 disassembler_elf_32.cc の466行目 にあるように、セクションヘッダから SHT_RELSHT_PROGBITS を再度取り出し、 rel32, abs32とを見比べて不整合がないことを確認している。

https://chromium.googlesource.com/chromium/src/+/21264cc9649f454255bdea9fae22342df25862d1/courgette/disassembler_elf_32.cc#528

  for (Elf32_Half section_id : section_header_file_offset_order_) {
    const Elf32_Shdr* section_header = SectionHeader(section_id);
    if (section_header->sh_type == SHT_NOBITS)
      continue;
    if (!ParseSimpleRegion(file_offset, section_header->sh_offset, receptor))
      return false;
    file_offset = section_header->sh_offset;
    switch (section_header->sh_type) {
      case SHT_REL:
        if (!ParseRelocationSection(section_header, receptor))
          return false;
        file_offset = section_header->sh_offset + section_header->sh_size;
        break;
      case SHT_PROGBITS:
        if (!ParseProgbitsSection(section_header, &current_abs_offset,
                                  end_abs_offset, &current_rel, end_rel,
                                  program, receptor)) {
          return false;
        }

最後に、ELFファイル中のデバッグ情報など、今まで無視してきた情報を登録している。https://chromium.googlesource.com/chromium/src/+/21264cc9649f454255bdea9fae22342df25862d1/courgette/disassembler_elf_32.cc#466

Courgette スタンドアローン化について

これはなに

筆者はサイボウズラボユース開発支援制度を受けつつ、実行バイナリの差分生成についていろいろと調べています。 今日は、その活動紹介の一環として、最近やったことを記しておきたいとおもいます。 なお、以下の内容は 3月にやった成果発表スライドhttps://blog.cybozu.io/entry/2021/04/02/170042 を先に眺めてもらってからのほうが理解しやすいかと思います。

Courgette という Google Chrome に附属した高性能な実行バイナリ差分ソフトウエアがあります。これはGoogle Chrome のソフトウエアアップデートの高速化に使われています。

効果としては公式サイトを読んでもらえたらと思いますが、Chromium 190.1 -> 190.6 のアップデート容量が以下のように大幅に減少しています。

Full update 10,385,920

bsdiff update 704,512

Courgette update 78,848

しかし、これはChromiumソースコードと密結合していて普通に使えるものではないので、ソースコードが4万個以上ある Chromiumソースコードから、実行バイナリ差分生成プログラム Courgette のソースコードから肝心なものを取り出し、100ファイルほどと簡単に利用できるようにしました。

本稿では、どのようにやってきたかの概要を記したいと思います。リポジトリはここにあります: https://github.com/hiromi-mi/standalone-courgette

まず、先に使い方だけ紹介しておきます。

使い方

ビルド方法

$ git clone --recurse-submodules https://github.com/hiromi-mi/standalone-courgette
$ cd standalone-courgette
$ bash build.sh

こうすると courgetteout/Default 以下に生成されます。

$ ./out/Default/courgette --help

パッチ生成

パッチを それぞれ old_filenew_file とします。

./courgette -gen $(realpath old_file) $(realpath new_file) $(realpath diff.courgette)

すると diff.courgette という差分ファイルが生成されます。

パッチ適用

生成された差分ファイルの適用は以下でできます:

./courgette -apply $(realpath old_file) $(realpath diff.courgette) $(realpath out_file)

Chromium の大規模さについて

  • 翻訳単位の個数が4万個以上
  • ビルド時に /tmp 20GBを使いきる、中間生成物が多すぎてinode不足になる
  • 独自ビルドシステムを使っていて、使い回しがきかない
  • Core i9-10900X で 90分かかる (デバッグシンボルなし)
  • 基盤ライブラリ base だけでソースコードが4000ファイル
    • この基盤ライブラリでは std::string などSTLのほぼ全部の内容が再定義されているので、STLまわりの知識が使えない
  • モノシリックなソースコード
    • base なのにbase 以外に依存している

方法

基本的には、4万以上のソースコードファイルからいかに必要な関数を取り出すかが大事になってきます。

まず、メタビルドシステムを ninja を生成するために、gn というGoogle の独自ビルドシステムのビルドファイルを書きます。 トップレベル BUILD.gn からはじまり、その依存ファイルに沢山 .gn とか BUILD.gn とか *.gni というファイル群があるので、それらを Chromium のビルドファイルをもとに書き換えます。

次に、ビルドエラーを直します。前述の通り Chromium 本体の base/ は4000ファイルぐらいあり、他ライブラリに依存していて、かつインターフェースが頻繁にかわるなどで使いにくいです。 そのため、mini_chromium の利用を試みました。 これは base library の独立して使える縮小版.... のはずが Courgette をビルドするには未対応なものが多くあります。そこでパッチ をあてました。 その方法ですが、以下のとおりとても泥臭い手法です。

  1. . まず Courgette のビルドエラーになる箇所とその原因関数を特定します
  2. . その関数やクラスが含まれたファイルを Chromium 本体のbase/からコピーします
  3. . mini_chromium の base/ と Chromium 本体の base/ とがコンフリクトする箇所を書き換えます
    • 例: C++ で書かれているのですが、String 型が mini_chromium の string と base の string と STLの std::string が混ざっていてつらいです
    • 例: File クラスのAPIが微妙に違うものを使っています
  4. . 書き換えますが、コピーしたファイルが依存するヘッダファイルが不足するので、やはりビルドエラーになります
  5. . 1. から 4. をくりかえし、ビルドエラーがなくなるまで修正します。 また、(base のはずなのに) 他ライブラリに依存していることなどがあり、まともに修正できないこともあります。そのときは、Courgetteで使用している関数やクラスや、それに依存しているAPIを全部調べ上げて、使われていない関数定義などを全部コメントアウトしたり、使わないようにソースコードを書き換えます。

以上、1から6をただひたすらに繰りかえしていきました。50ファイルほどは書き換えたと思います。

そして、Courgette 自身にも同様にパッチを書きます。https://github.com/hiromi-mi/courgette/commit/58628c4a839860ca0ad061af96eb3b2cb9260d81

最後に、依存するサードパーティライブラリにパッチを当てて、ビルドシステムを作っていきました。

苦労した点と今後について

苦労した点はいろいろとあるのですが、 - ソースコードの分量が多すぎて、読み解くだけで数十時間 (総和) かかりました。 - ドキュメントが少ない。あるとしてもブラウザーChromiumソースコード解説だけで、それを取り出すことについては述べられていません。 - モノシリックなソースコードはその中で完結している分には分かりやすいが、一部だけ取り出そうとすると大変です。

今後については: - このアルゴリズムをそのままに、現在再実装に取り組んでいます。いずれできたら公開して別のソフトウエアアップデートシステムに組み込めたらと思っています。 - また、アルゴリズムの改良をしたいと思っています。

宣伝

このソフトウエアは サイボウズラボユース開発支援制度の支援を受け作成されたものです。

表記ゆれを nvcheck で自動的に検出する

表記揺れチェッカには何種類かありますが、筆者は nvcheck を使っています。本稿では nvcheck の使い方についてまとめます。

github.com

使い方

https://github.com/koron/nvcheck/blob/master/README.md にある README にも記されていますが、ここでも使い方をまとめておきます。

インストール

まず 公式サイト にあるように Go言語の環境を構築します。

次に、nvcheck をインストールします。

$ cd $(mktemp -d); GO111MODULE=on go get github.com/koron/nvcheck

なお Go 1.16 以降では

$ go install github.com/koron/nvcheck@latest

とするようです*1

すると

$ go env GOBIN

に記された場所に nvcheck コマンドが追加されます。

使い方

対象にしたいテキストファイル file.txt があるディレクトリに dict.yaml を置きます:


正しい表記:
  - 誤りの表記1
  - 誤りの表記2
# コメント

したがう:
  - 従う
したがって:
  - 従って

file.txt をチェックしたいときは:

$ nvcheck file.txt

これを Makefile か何かに書いておくと Vim の quickfix 機能で確認できます。

また、次のようにすると file.txt が自動的に修正され、標準出力に出力されます。

$ nvcheck -r file.txt

さらに、-i オプションを使うとfile.txt 自体を自動的に修正できますが、バグがあった際にデータが消失する可能性があります。

$ nvcheck -i file.txt