ryotaway’s diary

字句解析器生成系の話

この記事は 弥生 Advent Calendar 2021の18日目の記事です。

昨日は @takuya_kawamoto さんによる、社内のタスク管理ツールをTracからBacklogに移行した話 の記事でした。

タスク管理って必要なんだけど、見にくい・扱いづらいとほんとツライんですよね。ツール乗り換えの際の苦労が見えて「ありがとうございます！」という気持ちになりました。

お仕事で、古いツールでタスク管理をされてる方もおられると思います。 ご参考になる部分があるかと思いますので、ぜひご覧くださいませ。

はじめに

エンジニアって専門書をよく読みますよね？

で、読んでいるときに、「そういえばこれ実装したことなかったな」みたいなことにぶち当たりますよね？

先日 コンパイラ（以降、書籍という）を読み返していて、「そういえば字句解析器生成系ってよくわかってないし作ったことないなぁ」と思ったので、勉強しなおして、作ってみました。

そのときの勉強や実装を共有しますのでお時間のある方はお付き合いくださいませ。

この記事を読むとわかること

  • 字句解析器生成系(lex)が何をしているのか
  • 正規表現の基礎的な理論
  • 実装

がわかりるようになります。

「字句解析器の生成ツールってどうやったら作れるの？」「正規表現の処理ってどうやったら作れるの？」という人にはよいかなと思います。

この記事では書籍に載ってる範囲での理論の紹介であり、基本的なアルゴリズムしか述べていません。

もっと字句解析器（を含めコンパイラ全般）について知りたい！という方はぜひ書籍をぜひ読んでみてください。ハイパフォーマンスな正規表現を作りたい！という方は論文などにあたってくださいませ。

字句解析器生成系（理論編）

字句パターンは正規表現で。

書籍によれば、

字句パターンを規定するための便利な方法である正規表現

とのこと。lex（超有名な字句解析器生成ツール）も正規表現を使って字句を定義します。

確かにシンプルに字句を定義できるよな〜って思いましたが、この記事をご覧の方はいかがでしょうか？同じ思いですかね。

書籍ではlexの正規表現のアルゴリズムを説明しています。

というわけでこの記事でも、以降はlexでの正規表現の説明となります。

正規表現って？

エンジニアの人にはお馴染みの、こういう呪文みたいなヤツです→ (a|b)*c

文字列検索なんかでよく使いますよね。

正規表現の処理では、この 文字列を木構造に変換 して、それをさらに 文字列が一致してるかをチェックしやすい形（状態遷移表）に変換し 、 文字列が一致するかを状態遷移表を使って調べます 。

（一般の正規表現エンジンではパフォーマンスを出すために状態遷移表ではなく仮想マシンのコードに変換してしまう処理系も存在するようですが、書籍ではlexのアルゴリズムの説明をしているので上記のみの説明になります）

木構造

文字列から木構造に変換する際、木の節（ノード）と葉（リーフ）が必要になります。

木の種類は、アルゴリズムが2分木を前提に作られているため、2分木とします。

先にくる文字列は左側、後にくる文字列は右側の子ノードのサブツリーで表現します。

  • 順接
    • 文字が続けて現れることを表します。
    • 例えば、 ab と書いた場合、 a のあと b が現れることを表しています
    • 必ずノードになります
  • 選択
    • 一般的に | を使って表します
    • どちらかの文字が現れることを表します
    • 例えば、 a|b と書けば、 a か b どちらかが現れることを表しています
    • 必ずノードになります
  • スター
    • 一般的に * を使って表します
    • 同じ文字列の、0回以上の繰り返しを表します
    • 例えば、 a* と書けば、 ` 、a、aa、aaa`、...と無限に続く文字列にマッチすることを表しています
    • 必ずノードになります
  • 文字クラス
    • 一般的には [a-z] のような鉤括弧付きの表現で、1文字を表します
    • この記事では説明の都合上 a など1文字も文字クラスとして扱います
    • 必ずリーフになります
  • 終端（受理可能状態を示すもの）
    • これは文字列上には現れませんが、字句の終端を表します
    • 必ずリーフになります

です。

説明の中でノードとリーフを使い分けるのが大変なので、以降はノードという呼び方で統一します。

例えば ab という正規表現では、下図のような木になります。 なお、○の中に＋が入ってるのが順接を、a, bなど文字が入っているのは文字クラスを、＃は受理可能状態をそれぞれ表します。

f:id:ryotaway:20211217124811p:plain

a|b という正規表現では、下図のような木になります。

f:id:ryotaway:20211217124813p:plain

スターを表す木は下図のようになります。 スターは左ノードのみ持つノードで、特殊です。

f:id:ryotaway:20211217124815p:plain

ということで木構造の説明は終わりです。

ちなみに、冒頭の正規表現 (a|b)*c の例を木にするとこうなります。

f:id:ryotaway:20211217132328p:plain

正規表現には他にも指定方法があるけど、それはどうするの？と思った方へ

書籍には載ってませんが、基本的には、順接、選択、スターの３種類を組み合わせて表現できます。 たとえば普通 1回以上繰り返す という表現として a+ のようにかけますが、これは aa* と等価です。

また、 0回か1回 の表現として a? のようにかけますが、これは a| と等価です（ | の右側は何も無いことを表しています）

他の表現も同様にできると思います。

木は作った！で、それをどうするの？

コンピュータが処理しやすいよう、状態遷移表に変換します。

状態遷移図を見たことはありますか？例えば以下のような図です。 これをデータで表現しやすい形にしたのが状態遷移表です。

f:id:ryotaway:20211217134525p:plain

上図では、1、2、3、＃が状態を表しています。＃は受理可能状態。初期状態は1です。 a, b, cが入力文字列です。

例えば、 状態1 のときに文字 a があれば、 状態2 に遷移し、次の文字をチェックする。 その次の文字が b なら、次は 状態3 に遷移し、次の文字をチェック…という感じでマッチング処理を進めます。 最後に#の状態になればこの正規表現にマッチした、と判定できます。

状態をつくる

木から状態遷移表を作るアルゴリズムが存在します。 ざっくり手順の全体像を示すと、

  1. nullableを求める
    • 空文字の場合があるかを示します
    • True/Falseのどちらかです
      • 空文字の場合があればTrue
      • 空文字がありえないならFalse
  2. firstposを求める
    • 最初になりえる文字クラス、終端ノードの集合です
      • 例えば (a|b)c だと先頭の文字が a か b になります
  3. lastposを求める
    • 最後になりえる文字クラス、終端ノードの集合です
      • 例えば a(b|c) だと最後の文字が b か c になります
  4. followposを求める
    • 次にくる可能性のある文字クラス、終端ノードの集合です
    • 例えば abc で、a の次にくる文字（followpos）は必ず bになります
  5. 遷移の状態の求める
    • followposを組み合わせて遷移の状態を作っていきます
  6. 遷移表をつくる 5.とほぼ同時に遷移の情報を作ります

となります。

1~3は各ノードごとに、下（リーフ側）から計算していきます（なぜかは後述します）。 それが終わったあと、4~6と手順を進めます。

詳細は以降に続きます。

nullable、firstpos、lastposを求める

nullable、firstpos、lastposの計算は下表のとおりです。

下表では、左の子ノードを left、右の子ノードを right と表現しています。

また、nullable、firstpos、lastposは関数のように表現することとします。

例えば nullable(left) だと左の子ノードのnullableの値を意味します。

また、集合の計算で ∪ がありますが、和集合を表しています。

ノード nullable firstpos lastpos 備考
文字クラス、終端 False { 自ノード } { 自ノード } firstpos、lastposは文字クラスが表現している文字のみ入った集合です
順接 nullable(left) and nullable(right) if (nullable(left)) { firstpos(left) ∪ firstpos(right) } else { firstpos(left) } if (nullable(right)) { lastpos(left) ∪ lastpos(right) } else { lastpos(right) } -
選択 nullable(right) or nullable(right) firstpos(left) ∪ firstpos(right) lastpos(left) ∪ lastpos(right) -
スター True firstpos(left) lastpos(left) スターにはleftしかありません

表から読み取れること

上表をみると気づくと思いますが、

  • 文字クラス、終端は自ノードを集合に入れます。nullableは固定でFalseです
    • 本当は空文字を許すかどうかでnullableが変わるのですが、この記事では省きます
  • 順接、選択、スターは子ノードの値を計算に使います

ということがわかります。

つまり、nullable、firstpos、lastposの計算を子ノード側から行えばよいことがわかります。

また、nullableの情報をfirstpos、lastposの計算に利用しているので、nullable→firstpos、lastposの順に計算する必要があるとわかります。

実装時には計算順序に気をつけましょう。

また、集合の要素になるのは、必ず文字クラスか終端 です。

firstpos、lastposのif文は何をしているの？

例えば、順接のfirstposを整形するとこんな文になっています。

if (nullable(left)) {
    firstpos(left) ∪ firstpos(right)
} else {
    firstpos(left)
}

これは、

左の子ノードが空の可能性がある場合、右の子ノードのfirstposも最初になり得る。
そうでない場合は、必ず左の子ノードの集合だけがfirstposになる

ということを表してます。

a*b という正規表現では、最初の文字が a か b になるはずです。そういうことです。

他のノードについても、ゆっくり考えればわかるはずです。

followposを求める

ここまでで求めてきた firstpos、lastposは、followposを求めるために必要な計算でした。

followposを求めるには次の2パターンを考えるだけでよいです。

  1. 順接ノードの場合
    • lastpos(left)集合の各要素のfollowposに、firstpos(right)の集合を加える
  2. スターノードの場合
    • lastpos(スターノード)集合の各要素のfollowposに、firstpos(スターノード)の集合を加える

（加える、と書いたのは和集合を取って、それを新たなfollowposとする、的な意味で書いてます）

遷移の状態を求め、遷移表を作る

以下のアルゴリズムに従えばOKです。

なお、 state は1状態を表します。 state は 処理されたかどうかを示すフラグと、ノードの集合を持ちます。

states は state の集合です。

transition は遷移情報を表します。

すべての入力記号 は正規表現内で取り得る文字のすべてを表します。 正規表現が ab なら { 'a' 'b' }がすべての入力記号で、 a と b が入力記号となります。

while (statesの中にフラグがFalseのstate 'S' がある) {
  'S' のフラグをTrueにする
  foreach (入力記号 in すべての入力記号) {
    state の中で、入力記号に対応するすべての要素について followposを取得して和集合をとり、それを 'U' とする
    if 'U' が空集合でない {
        if (states の中に 'U' が含まれていない) {
          'U' をフラグFalseの状態でstatesに追加する
        }
        transitionに、入力： 'S', 入力記号 、遷移先：'U' として情報を保存する
        （ コードっぽく書くとこんな感じ→ transition[S, 入力記号 ] = U ）
    }
  }
}

上記処理により、transitionが求まります。

見てわかるとおり、 ある状態と入力記号の組み合わせから次の遷移先の状態を決めるための情報がtransitionに集まります。

これを表に展開すれば遷移表が完成です。

えっ？ これで終わり？

state数の最小化、遷移表を小さくする方法などは載ってますが、基本的には以上で理論的な説明は終わりです。

これしか書かれてないんです。

でも実際に実装するとなると、他にいろいろ考えないといけないことがあります。

というわけで、以降は実装について述べていきます。

字句解析器生成系（実装編）

あくまでも私の好みによる実装例です。

みなさんの参考になると思い以降で説明をしますが、基本的に仕様はご自由になさってください。

決めなきゃいけないこと

以下は好みや要求で決めれば良いと思います。

  • 言語
  • 使用するライブラリなど
  • 字句パターン定義の構文
  • 複数の正規表現の優先順位
  • 出力の形
  • 正規表現で使える文字の種類（UTF-8とか、ascii文字のみにするとか）

以降の説明では、

  • 言語 → C言語
  • 使用するライブラリなど → 標準的なもののみ
  • 字句パターン定義の構文 → 後述
  • 複数の正規表現の優先順位 → 先に定義されたものから順に受理可能か確認していく
  • 出力の形 → 後述
  • 正規表現で使える文字の種類 → ascii文字のみ

でやっていきます

字句パターン定義の構文

実装が大変なのでlex互換は捨て、1行で字句パターンを1つ書けるようにしました。

例えば以下のようになります。

identifier = [a-zA-Z_][a-zA-Z0-9_]*
number = [1-9][0-9]

正規表現部分は↓のようにしました。この辺りは好みがでますね。 LL(1)でいけそうかなーと思いながら書きましたが、真面目には計算してません。

簡単なEBNFで書いたのでお気づきかと思いますが、めちゃくちゃシンプルな仕様にしています。 でも基本を学ぶための仕様なので、これで十分かなぁとも思っています。

regexが最上位のルールです。

regex := expr+
expr := fact ('|' expr)?
fact := ( '(' expr ')' | term ) option?
term := letter | charclass
letter := alnum | '_'
charclass := '[' charclass_arg+ ']'
charclass_arg := '_' | alnum ('-' alnum)?
alnum := [a-zA-Z0-9]
option := '*'

C言語での実装について

私は、 C言語のコードをオブジェクト指向っぽく書きたい 派閥に属してるので、以下のマイルールに従って書いてます。私のコードを参照される方はルールがあることを頭に入れておくと読みやすいかと思います

  1. 大文字は使いません
  2. クラスを表現する構造体にはすべて typedef で型定義します
  3. typedefした型の名前には _t をサフィックスに付けます
  4. 関数名は <クラス名>_<動詞>_<名詞など> と付けます
  5. フィールドにアクセスするだけの関数は <クラス名>_<名詞など> と付けます
  6. 引数は、第１引数にクラスのオブジェクトを入れます
  7. 継承では、スーパークラスのオブジェクトを、サブクラスの構造体の一番上に配置します
  8. 上記のルールが守られてないことがあります :-p

以上を頭に入れた状態で実装をお読みいただければ、内容がわかるかなーと思います。

なお、C言語の標準ライブラリしか使わないません。集合・双方向リスト・文字列を表現するクラスなどは自前実装です。突貫工事で作ったコードではありますが、それらもご参考にどうぞ。

テストにはgoogle testを利用しています（よいテストフレームワークをありがとうございます、googleの中の人）。

Githubのレポジトリはこちら

納得いかないコードがあるのでまだ非公開です。修正が終わったら公開します🙇‍♂️

おわりに

長文にお付き合いいただきありがとうございました。

字句解析器生成系、あるいは正規表現の理論・実装例の説明は以上で終わりです。

少しは実装できそうな気持ちになれたでしょうか。そうであればこの記事を書いたかいはあったかなぁと思います。

今回作った実装はテストが足りてないのでバグはあるだろうし、機能も不足しているので、今後チクチク更新していこうかなと思ってます。時折除いてもらえると嬉しいです。

明日は @atsushi_sasaki_yayoi さんの記事で、「DexAx::achademyを全社でやってみた」です。

私もDexAx::achademy参加してました！よい経験でいろいろ勉強なりましたが、atsushi_sasaki_yayoiさんの視点ではどうだったのかな？と楽しみにしています。

会社でAWSをすでにお使いの方、これから使おうと考えておられる方はご参考になるかと思いますので、ぜひご覧くださいませ。

それでは、引き続き 弥生 Advent Calendar 2021 をお楽しみください。

では ✋

自作アプリのパフォーマンス改善

この記事は 弥生 Advent Calendar 2020 の9日目です。

はじめに

こんにちは。 寒さにやられて体調不良な日々を過ごしていたりいなかったりな私です😷

そんな体調不良な日々の中、Rustの勉強のために自作アプリをRustで書き直していたのですが、処理が遅くなるという悲しい（けどありがちな）事象が発生。

そのままにするのも嫌だったのでパフォーマンス改善を試みてました。

この記事では改善作業について書きました。

誰かの参考になると嬉しいなぁ。

「遅い」

「遅い」は相対的な言葉ですよね。

今回は自作アプリを書き直す前後で、同じ処理をさせたときにかかる時間を計測して差を測りました。

基準は「書き直す前」のアプリ（昨年作成したBrainF***処理系）で、mandelbrot.rsを動かしたときの時間を測ってます。

BrainF***がわからない、というかたはwikipediaのページをどうぞ。

ちなみに実行結果はこうなります。ほんといつみてもカッコいい。 f:id:ryotaway:20201209013242p:plain

計測にはtimeコマンドを使いました。

計測した環境は↓

結果は↓

No. バージョン 処理時間 [s]
1 C版
27.09
2 Rust版（書直しVer）
34.92

8秒くらい遅くなってる😩

仮説と改善、そして検証

「遅い」は「悪い」。原因について検討し、↓の仮説を立てました。

  1. 無駄な処理がある
  2. 言語仕様上、遅くなる処理がある

1. 無駄な処理がある

まず1. については、'[' と ']'のペアを探す処理が無駄だなーと昨年C言語版を開発した時から気になっていたので、そこを解消しようと思いました。

気になってたのはこのwhile()でグリングリン回してるところ。

改善として、

としてみました。

2. 言語仕様上、遅くなる処理がある

次に2. についてですが、BrainF***のコードを眺めていると

+++

のように繰り返し同じ命令が登場するのが気になりました。 BrainF***では1つの命令で+1, -1などができるだけで、まとめて+10とかはできません。なので繰り返し同じ命令が登場しやすくなるのですが…。

また、各命令の総実行回数も気になりました。どのくらいなのかな。

ということでまずは計測。

mandelbrot.bfを動かしたときの、各命令の総実行回数は↓となりました。

命令 実行回数
>
4,453,036,023
<
4,453,036,013
+
179,053,599
-
177,623,022
.
6,240
,
0
[
422,534,152
]
835,818,921

冗談みたいな数字が並んでますが、あってるっぽい😩

'>' は44億回以上実行されてるし、'+'は1億8千万回くらい実行されているようです。

例えば'.' は文字を出力する命令なんですが、
mandelbrot.bfでは、画面表示は１行につき
    129文字＋改行1文字 = 130文字
表示されます。
それが48行出力されるので、
    130*48 = 6420
となります。

計測は命令を処理するときにカウントするコードを仕込んだだけです。簡単🙃

本当は処理時間の計測をできるようにするつもりだったんですが、
結局作業の最後までやりませんでした。
なので Profiler という構造体名になってますが名前負けしてますね。
責務としてはせいぜいがCounterといった程度です。

まぁとにかく、処理する命令数が結構多いなぁと思ったので命令の圧縮を考えるのがよさそう、ということがわかりました。

というわけで改善のためコンパイラ（というほど大仰なものではない）を作りました。

やってることは単純で、

  1. 命令を、種類と回数の組みと定義する
  2. いくつかの命令については連続したものをまとめて一つの命令にする

ということをしているだけです。

改善の結果

結果を表.1にまとめました。

表.1

No. バージョン 処理時間 [s]
1 C版
27.09
2 Rust版（書直しVer）
34.92
3 Rust版（無駄を省いたVer）
37.32
4 Rust版（コンパイラ導入Ver）
14.04
5 Rust版（無駄を省いた＆コンパイラ導入Ver）
23.07

🤔

結果の検討

表.1 のNo.3はNo.2よりも遅くなってました。

No.3の改善では実装にHashMapを使ったのですが、このHashMapのアクセスにかかる時間より'['と']'を一文字ずつサーチする方が速い、ということを意味してます。多分。 そんなことある？って思ってるので、処理がバグってるんじゃないかとも疑ってますが。

No.４の命令をまとめるという改善はだいぶ効きましたね。 処理時間がC版の50%近くまでになってます。mandelbrot.bfは処理する命令の回数が非常に多いので、連続した命令をまとめて1回で処理する、という方針は効果的だったんですね。これは嬉しい結果です🤗

次に処理時間が速かったのはNo.5ですが、これは単にコンパイラを導入して早くなったけどHashMapを使った部分が足を引っ張っているだけに見えます。組み合わせてもあまり意味はありませんでしたね。

まとめ

当たり前の結論になりましたが、

  • 原因を頭で考えるよりも実際の計測結果の方がボトルネックを調べるときはあてになる（なった）
  • 処理される命令の数（≠プログラム上の命令の数）を把握するのってボトルネック調べるのに大事

あたりが、今回得られた知見でしょうか。

実は↓を実装したら速度改善するか、という疑問がまだ残っていますが、まぁそれはまた来年にでも。

  • プログラム自体の最適化
  • 頻出のイディオム（ [-] など）を1命令で実行できるようにする
  • JITコンパイル
  • 処理の依存関係の発見と並列化処理

なお、今回の最終的なコードは以下にあります。

github.com

ご参考まで。

それでは、また👋

BFのすゝめ

この記事は Misoca+弥生 Advent Calendar 2019 の8日目です。

はじめに

生きてると処理系を書きたくなることありますよね。私はあります。

今回は衝動の赴くまま、今回は Brainf*** を作ることにしました。

正規式名称にfから始まる4文字ワードが含まれているので、* で伏字しています。あまり書いてて気持ち良いものではないので、以降この文章ではBFと呼びます。

みなさん。BF作りましょう。

BFとは

シンプルな仕様で、使うのが難しいプログラミング言語です。

BFの特徴は、

  • 8つの命令しかない
  • メモリが、リニアな30000バイトの空間を持つ

くらいしょうか。

(チューリング完全という特徴もあるのですが、説明すると長くなるのでここでは書きません)

この記事を書くためにBFの仕様を調べていて、 The Brainfuck Programming Language を読んで知ったのですが、最初に作られたのは Amiga OS2.0 用の実装だったんですね。...Amiga...この記事を読む人は知ってるかな...。

今回作るBFの仕様

最初に仕様が世にでてからもうだいぶ立ちます。 Brainfuck - Wikipedia によれば登場時期は1993年だそうなので、26年前ですね（...だいぶ前だな）。

それくらい前から仕様が存在しているので、実装は世の中にあまた存在しています。すでに他の実装をご存知の方も多いことでしょうし、自作されたことがある方もいることでしょう。

世に出ている実装には元の仕様から機能拡張されているものもありますが、今回は単純かつ小さめな仕様・実装でいきます。 基本は The Brainfuck Programming Language の仕様に従いますが、メモリサイズなど独自なところもあります(仕様で定義されていないところも含みます)。

仕様

基本設計

メモリ

  • メモリは、次の二つを持ちます
    • instructions メモリ
    • data メモリ
  • 二つのメモリはどちらも64KBのサイズとします
  • instructions メモリは起動時にプログラムを格納します
    • プログラムのサイズが64KB未満の場合は0で初期化します
  • data メモリは起動時に、すべて0で初期化します

レジスタ

レジスタとして以下を持ちます。

  • instruction pointer
    • 実行中の命令の位置を保持します
    • 16bit
  • data pointer
    • 命令実行中のメモリの読み書き位置を保持します
    • 16bit
  • bracket depth
    • [ ]のネストの深さを保持します（詳細は後述）
    • 16bit

命令セット

The Brainfuck Programming Language に書かれている命令だけを実装します。 それ以外の文字はすべて無視します。 各命令がASCIIコードの1文字となります。マルチバイト文字は考慮しません。

>    Increment the pointer.
<    Decrement the pointer.
+    Increment the byte at the pointer.
-    Decrement the byte at the pointer.
.    Output the byte at the pointer.
,    Input a byte and store it in the byte at the pointer.
[    Jump forward past the matching ] if the byte at the pointer is zero.
]    Jump backward to the matching [ unless the byte at the pointer is zero.

上記説明の pointer は、今回作るBFにおける data pointer にあたります。

実装

実装は https://github.com/ryotarokawakami/bf に置きました。cloneするなどして自由にご確認ください。

C言語で実装しているので、実行のためにはビルドが必要です。

(macbookで開発していたので、他の環境だとmakefileを書き換えないとダメかもしれません)

ファイルのロード

https://github.com/ryotarokawakami/bf/blob/master/src/utils.h を見ればわかりますが、ファイルのロード、ロードしたデータの削除は utils で提供しています。BFのインタプリタではファイルは扱いません。メモリ上にある命令列だけを対象に処理をします。

命令の実行

実装は https://github.com/ryotarokawakami/bf/blob/master/src/vm.c#L40 のあたりになります。

CPUのエミュレーションを実装するときにインタプリタの形式を採用すると同じような実装になります。1命令ずつ読み込んで実行する流れが見えると思います。 （読み込んだ値が 0 の場合は命令がないと解釈して処理を終えるようループの条件を作っているので、 HALT命令が実装されていると言えばされていますね）

[ と ] はちょっとだけ面倒な仕様になっているので、ちょっとだけ面倒な実装になっています。

[ と ]

仕様では、

[    Jump forward past the matching ] if the byte at the pointer is zero.
]    Jump backward to the matching [ unless the byte at the pointer is zero.

と書かれているので、対応する括弧を探す必要があります。 たとえば、

++[[++-]-]++

のようにプログラムがあるとき、最初の [ の括弧に対応する ] は、プログラムの一番右側に現れる ] であって、その2つ前にある ] ではないということです。

レジスタに bracket depth を持たせたのは、対応する括弧を探しやすくするためです。 [ が見つかると bracket depth を +1、] が見つかると bracket depth を -1 するようにしています。 ジャンプする場合は https://github.com/ryotarokawakami/bf/blob/master/src/vm.c#L77 や https://github.com/ryotarokawakami/bf/blob/master/src/vm.c#L96 で処理します。 それぞれが 20 行に満たない処理なので、読めばすぐにわかると思います。シンプル。

ビルド

トップディレクトリで make してください。 bf という実行ファイルがトップディレクトリに作成されるはずです。

macbookで開発していたので他の環境ではビルドを試していませんが、もしビルドに失敗するとしても makefile を少し変更するだけでビルドできるようになると思います。 オプションに -std=c11 をつけてますが c99 でもビルドできると思います。

サンプルの実行

さて、 ビルドして bf という実行ファイルが作れたでしょうか。

サンプルとして samples/hello.bf を入れたので実行してみましょう。

./bf samples/hello.bf

どうでしょうか。実行結果はこんな感じになったでしょうか。

Hello, World!

BFのプログラムはなにしろ難解になるので、わかりやすさ優先で書いてみましたがいかがでしょうか。何をしているか理解できるでしょうか。

理解できない人がいるかもしれないので、最初の1行だけ解説してみます。

[ H: 72]

行頭の [ H: 72] の部分は、単なるコメントです。

BF のインタプリタは初期化時に data pointer を0 にします。data[0] は 0 です。そのため [ ] の中は処理されず、 instruction pointer は ] の後まで飛びます。 突然 data[0] が出てきたようにみえるかもしれませんが、基本設計のところで書いた data メモリ の0番地を data[0] と表記しているだけです。

] の直後のスペース

続いて、] の直後には (半角スペース) があります。 これは命令ではないので、無視されます。

++++++++++

この時点で data pointerは 0 を指しています。そのため、+ を一つ処理すると data[0] の値が+1されます。 + は10個あるので、すべて処理すると data[0] の値は10となります。

[

この時点ではまだ data pointer は 0 です。bracket depth も 0 です。 data[0] の値が 10 なので [ では対応する ] に飛びません。[ を処理するときに bracket depth を+1して 1 にします。

>+++++++<-]

> で data pointer が +1 されます。 続く +++++++ で data[1] の値が 7 になります。

さらに < で data pointer が-1され、 - で data[0] の値が-1されます。

そして ] で対応する [ に飛ぶかどうかを判定します。

大丈夫でしょうか。理解が追いついているでしょうか。

つまりここまでの ++++++++++[>+++++++<-] という処理は、

  1. data[0] を10にする
  2. ループに入る
  3. data[1] を7にする
  4. data[0] を9にする
  5. data[1] を14にする
  6. data[0] を8にする
  7. ...
  8. data[1] を70にする
  9. data[0] を0にする
  10. ループを出る

という動きになり、 7を10回足す 、つまり 7 × 10 の計算をしているのと同じことになります。 7 × 10 の掛け算をするだけで22命令使うなんてかわいいやつですね。

>++.>

ループから出たとき、 data pointer は 0 を指しています。

> で data pointer を +1 します。 ++ で data[1] を +2 するので、 この時点で data[1] は 72 となります。 . で data[1] をputchar() します。72 は ASCII コード で H です。 > で data pointer を +1 します。ここで data pointer は 2 となります。 data[2] は初期値のまま 0 です。 改行コードは命令にない文字なので無視されます。

これで1行分の解説は終わりです。

おわりに

いかがでしたでしょうか。8命令という単純な仕様でいろいろプログラミングができてしまうなんて、BF 楽しくないですか？私は実装していてすごく楽しかったです。

この記事の冒頭でも書きましたが、BFは26年も前から存在する仕様で、実装も世の中にあまたあります。 実装者はみんな、仕様が単純かつ短時間で書けるプログラミングのお題として楽しんでいたのではないかなと思ってます。

BFのプログラムも多くの人が公開しています。 HelloWorldをはじめ、実に様々なプログラムが存在します。 個人的にお気に入りのコードが マンデルブロ集合の印字 です。 いやスゴイですね。プログラムしようという発想も実行結果も実にカッコイイです。 プログラムの内容は安定の難解さですが、読み解きたい気持ちが湧き上がってきますね（読み解いたとは言っていない）。

世のプログラマの多くが楽しんできた BF 、みなさんも年末年始のお休みあたりに楽しんでみてはいかがでしょうか。たぶん2時間もあれば実装できると思います。

最後になりますが、私が実装した BF でマンデルブロ集合のプログラム実行結果と、比較のために WegGLで作成したマンデルブロ集合 の画像を貼っておきます。

次回、 Misoca+弥生 Advent Calendar 2019 の9日目は mai_goto さんです。お楽しみに！

BFの実行結果とWebGLでの描画との比較

BFの実行結果

f:id:ryotaway:20191208000605p:plain:w400

WebGLで描画した結果

f:id:ryotaway:20191203010226p:plain:w400

マンデルブロ集合をWebGLで描画してみる

この記事は Misoca+弥生 Advent Calendar 2019 の3日目です。

はじめに

12月に入り、だいぶ寒くなりましたね。今年は紅葉が遅いと聞いていたので、紅葉狩りがてら犬山城を観に行ってきました。 犬山城ファンなので行った時は必ず写真を撮るのですが、ことのときは「アドベントカレンダー何書こうかな。WebGL使いたいな。」ってぼんやり考えながら撮り続けてました。

f:id:ryotaway:20191202231415j:plain:w500
木曽川から撮った犬山城

で、撮った写真をみてて思ったんですよね。

マンデルブロ集合の描画をやろうって。*1

というわけでやりました。

マンデルブロ集合？

マンデルブロ 集合が何かわからない人のために、wikipediaのページへのリンクを貼っておきます。 ただし数学が大好きな人以外はリンク先へ飛ぶ必要はありません。青っぽい色した画像を眺めていただければそれで十分です。

ja.wikipedia.org

今回は、この青っぽい画像と同じような出力結果を得られればよしとすることにしました。

WebGL？

WebGL Overview - The Khronos Group Inc によれば、

WebGL is a cross-platform, royalty-free web standard for a low-level 3D graphics API based on OpenGL ES, exposed to ECMAScript via the HTML5 Canvas element.

というわけで、ブラウザで3Dグラフィクスを扱うための仕様です。W3Cに仕様があるのかと思っていたけど違うんですね。知りませんでした。これを機に詳しくなっていこうと思います。

今回WebGLを学ぶ上でいくつかのサイトや書籍を参照しました。たとえば、

WebGL 開発支援サイト wgld.org は非常に丁寧に解説があり、WebGLをこれから勉強する人にとてもオススメなサイトです。 勉強中にコードを写経していた影響で、後述する私の実装が非常に似通ってしまっています。その点はごめんなさい。

また、 WebGL Insights 日本語版 は海面の表現や、グラフィクスエンジンの設計、Mozillaでの実装などが取り上げられていて興味深かったです。 少し高価かなと思いますがオススメです。

まずは結果

このような画像を生成できました。

f:id:ryotaway:20191203010226p:plain:w300
まぁまぁ近い色合い

f:id:ryotaway:20191203011810p:plain:w300
小さい円と大きい円のくっついているところを拡大したもの。タツノオトシゴの谷と呼ばれているそう。

実装

実装は html と javascript の２ファイルです。 手元で試したい人は、それぞれ index.html , script.js と名付けて同じディレクトリに配置してください。 index.html をブラウザから開けばマンデルブロ 集合が表示されると思います。 （githubにリポジトリ作るまでもないかなと思ったので...）

html

実装は長いので折りたたんでおきます

<!DOCTYPE html>
<html>
  <head>
    <title>mandelbrot set</title>
    <script id="fragment" type="shader">
      precision mediump float;
      uniform vec2 resolution;

      vec3 hsv2rgb(float h, float s, float v) {
        return ((clamp(abs(fract(h + vec3(0.01, 2.0 ,1.0) / 3.0) * 6.0 - 3.0) - 1.0, 0.0, 1.0) - 1.0) * s + 1.0) * v;
      }

      void main() {
        vec2 p = (gl_FragCoord.xy * 2.0 - resolution) / min(resolution.x, resolution.y);
        vec2 x = p + vec2(-0.50, 0.0);
        float y = 1.25;
        vec2 z = vec2(0.0, 0.0);

        for (int i = 0; i < 80; i++) {
          z = vec2(z.x * z.x - z.y * z.y, 2.0 * z.x * z.y) + x * y;
          if (length(z) > 2.0) {
            vec3 rgb = hsv2rgb(
              0.68 - 0.40*float(i)/80.0,
              1.0,
              0.6 + 1.20*float(i)/80.0
            );
            gl_FragColor = vec4(rgb, 1.0);
            return;
          }
        }
        gl_FragColor = vec4(0.0, 0.0, 0.0, 1.0);
      }
    </script>

    <script id="vertex" type="shader">
      attribute vec3 position;
      void main() {
        gl_Position = vec4(position, 1.0);
      }
    </script>

    <script src="script.js" type="text/javascript"></script>

    <style type="text/css">
      body {
        text-align: center;
        margin: 20px auto;
        padding: 0;
      }
    </style>
  </head>
  <body>
    <canvas id="canvas"></canvas>
  </body>
</html>

javascript

実装は長いので折りたたんでおきます

var gl_context;
var uniform_locations = [];

const CANVAS_WIDTH = 512;
const CANVAS_HEIGHT = 512;
const ORIGIN_X = 0.5;
const ORIGIN_Y = 0.5;

window.onload = function() {
    var canvas = get_canvas(canvas);
    gl_context = get_context_from_canvas();

    var prg = create_program(create_shader('vertex'), create_shader('fragment'));
    uniform_locations[2] = gl_context.getUniformLocation(prg, 'resolution');

    var attrib_location = gl_context.getAttribLocation(prg, 'position');
    gl_context.bindBuffer(gl_context.ARRAY_BUFFER, create_vbo(
        [
            -1.0,  1.0,  0.0,
             1.0,  1.0,  0.0,
            -1.0, -1.0,  0.0,
             1.0, -1.0,  0.0,
        ]));
    gl_context.enableVertexAttribArray(attrib_location);
    gl_context.vertexAttribPointer(attrib_location, 3, gl_context.FLOAT, false, 0, 0);
    gl_context.bindBuffer(gl_context.ELEMENT_ARRAY_BUFFER, create_ibo(
        [
            0, 2, 1,
            1, 2, 3
        ]));

    gl_context.clearColor(0.0, 0.0, 0.0, 1.0);
    render();
};

function render() {
    gl_context.clear(gl_context.COLOR_BUFFER_BIT);
    gl_context.uniform2fv(uniform_locations[1], [ORIGIN_X, ORIGIN_Y]);
    gl_context.uniform2fv(uniform_locations[2], [CANVAS_WIDTH, CANVAS_HEIGHT]);

    gl_context.drawElements(gl_context.TRIANGLES, 6, gl_context.UNSIGNED_SHORT, 0);
    gl_context.flush();
}

function create_shader(id) {
    var elem = document.getElementById(id);
    var shader = get_shader(id)
    if (shader == null) {
        return null;
    }
    
    gl_context.shaderSource(shader, elem.text);
    gl_context.compileShader(shader);

    if (gl_context.getShaderParameter(shader, gl_context.COMPILE_STATUS)) {
        return shader;
    } else {
        console.log(gl_context.getShaderInfoLog(shader));
    }
}

function create_program(vs, fs) {
    var program = gl_context.createProgram();

    gl_context.attachShader(program, vs);
    gl_context.attachShader(program, fs);
    gl_context.linkProgram(program);
    
    if (gl_context.getProgramParameter(program, gl_context.LINK_STATUS)) {
        gl_context.useProgram(program);
        return program;
    } else {
        return null;
    }
}

function create_vbo(data) {
    var vbo = gl_context.createBuffer();
    gl_context.bindBuffer(gl_context.ARRAY_BUFFER, vbo);
    gl_context.bufferData(gl_context.ARRAY_BUFFER, new Float32Array(data), gl_context.STATIC_DRAW);
    gl_context.bindBuffer(gl_context.ARRAY_BUFFER, null);
    return vbo;
}

function create_ibo(data) {
    var ibo = gl_context.createBuffer();
    gl_context.bindBuffer(gl_context.ELEMENT_ARRAY_BUFFER, ibo);
    gl_context.bufferData(gl_context.ELEMENT_ARRAY_BUFFER, new Int16Array(data), gl_context.STATIC_DRAW);
    gl_context.bindBuffer(gl_context.ELEMENT_ARRAY_BUFFER, null);
    return ibo;
}

function setup_canvas(canvas) {
    canvas.width = CANVAS_WIDTH;
    canvas.height = CANVAS_HEIGHT;
}

function get_canvas() {
    canvas = document.getElementById('canvas');
    setup_canvas(canvas);
    return canvas
}

function get_context_from_canvas() {
    return canvas.getContext('webgl') || canvas.getContext('experimental-webgl');
}

function get_shader(id) {
        switch (id) {
        case 'vertex':
            return gl_context.createShader(gl_context.VERTEX_SHADER);
        case 'fragment':
            return gl_context.createShader(gl_context.FRAGMENT_SHADER);
        default :
            return null;
        }
}

実装のポイント

index.htmlにあるfragment shaderの次の箇所が実装がポイントです。

       for (int i = 0; i < 80; i++) {
          z = vec2(z.x * z.x - z.y * z.y, 2.0 * z.x * z.y) + x * y;
          if (length(z) >= 2.0) {
            vec3 rgb = hsv2rgb(
              0.68 - 0.40*float(i)/80.0,
              1.0,
              0.6 + 1.20*float(i)/80.0
            );
            gl_FragColor = vec4(rgb, 1.0);
            return;
          }
        }
        gl_FragColor = vec4(0.0, 0.0, 0.0, 1.0);

マンデルブロ集合とは、複素数列の漸化式

  • Z_{n+1}=Z_{n}^2+C
  • Z_{0}=0

のnを無限大に飛ばした時に値が収束する複素数の集合のことをいいます。

この Z_{n} を実数平面上点 Z_{n} ( X_{n} , Y_{n} )に置くことにすると、漸化式は次のようになります。

  • X_{n+1}=X_{n}^2-Y_{n}^2+a
  • Y_{n+1}=2X_{n}Y_{n}+b

これが発散するか収束するかをチェックすればよいことになります。 発散する場合はマンデルブロ 集合に含まれません。収束する時は含まれます。

ある点がマンデルブロ集合に含まれないときは、 |Z_{n}|=\sqrt {X_{n}^2+Y_{n}^2} が 2以上になることがわかっているそうです。 nを無限大に飛ばすことはできないので80に留めることとし、最大 |Z_{80}| まで計算して2以上になることがあるかを調べます。

よって次のコードとなるわけです。

 for (int i = 0; i < 80; i++) {
  z = vec2(z.x * z.x - z.y * z.y, 2.0 * z.x * z.y) + x * y;
    if (length(z) >= 2.0) {
      ...

rgbは色を計算する箇所なので、いろいろ変更してみると楽しいと思います。

vec3 rgb = hsv2rgb(...)

上述したコードは、 計算した回数が多いと色が明るくなるようにしています。 また、マンデルブロ 集合に含まれている点は黒にしています。

まとめ

WebGLを使ってマンデルブロ 集合の画像を生成しました。

いつかやりたいなと思っていたマンデルブロ 集合だったので楽しく調査・実装することができました。 今回の記事では触れませんでしたが、GPGPUを使ってやりたいことがあるので、徐々にでも慣れて思いどおりに操れるようになるといいなぁと思っています。

最後までお読みいただきありがとうございました。

Misoca+弥生 Advent Calendar 2019 の4日目は yoshoku さんです。お楽しみに！

*1:なぜかわからない人はマンデルブロ集合の画像をみた後、犬山城の写真を目を細くして見てみよう。ほら、わかるでしょ？

OculusQuestめっちゃ楽しい

5/22あたりに届いてた。

f:id:ryotaway:20190528223323j:plain

主にYouTube VRを見てる。

超控えめに言って最高。

大画面で動画を見たかったのでOptomaのプロジェクタを検討していたのだけど、買わずにOculus Questを選んでよかった。一人で楽しむならOculus Questのほうがいいな。

ちなみに、欲しかったOptomaのプロジェクタは以下。 超単焦点プロジェクタなので壁に近い位置に配置できるし、明るさが4000ルーメンなので照明が付いていても動画が楽しめる（らしい）。 www.optoma.jp

Oculus Questのガーディアンの仕組み、いいですね。 どこが動いて良い領域かがわかりやすい。 カメラの画質がイマイチ（モノクロでガサついた画質）なのにこれで十分なんだなぁって驚いています。

しかしまだアプリが足りない。 まだまだ欲しいアプリがない。

早くHuluのアプリでないかな。 Netflixは専用アプリがすでに出てるので、そちらに乗り換えるかな。

Firecrackerの実装を眺めた感想

はじめに

f:id:ryotaway:20181220162340j:plain

こんにちは。 id:ryotaway です。プログラマをしています。

この記事は Misoca+弥生+ALTOA Advent Calendar 2018 - Qiitaの20日目の記事です。 昨日は naoki_hayashi さんの「AWS ECS+EFSでwordpressサイト構築 - 弥生開発者ブログ」でした。

昨日の記事でもAWSが登場していますが、AWSのサービスって便利ですよね！ 仕事でも大変お世話になっています。

この記事ではAWSで作られたFirecrackerについて書きます。

Firecrackerとはなにか

Firecrackerとは、2018/11/27に AWS re:Invent 2018で発表されたOSSで、LambdaやFargateの基盤として開発されたマイクロ仮想マシンだそうです。詳細については、 Firecracker や GitHub - firecracker-microvm/firecracker: Secure and fast microVMs for serverless computing. などをご覧ください。

Firecrackerとは爆竹という意味ですが、束になってるやつではなく爆竹1つをイメージしているのかなと思います。 仮想マシンの起動からユーザーコードの実行、仮想マシン終了までのライフサイクルを短時間でパッと実行するイメージを表しているのかなと思ったので、なるほどずいぶんと格好いい名前だなぁという印象を持ちました。

実装について

FirecrackerはRustで書かれてます。Rustは新しめなシステムプログラミング言語で、所有権や借用などの概念も盛り込んだプログラミング言語です。詳細は Rust programming language などをどうぞ。

Rustのコードや仮想マシンの実装に馴染みのない人がFirecrackerの実装を読むのは大変だとは思うのですが、せっかくOSSになっているのですから、プログラマはみんな読んだらいいんじゃないかなと思ってます。得るものがあるのではないかな。

この記事では仮装マシンの実装に慣れていない人のために、Firecrackerの実装を説明していきます。

と意気込んだものの

コード量はそれほど多くないのですが、説明をブログに書くとなるとかなり長く読みにくい記事になってしまい、「余白が足りない」といいたくなる気持ちが湧いてきます。なので、この記事ではざっくりとディレクトリごとにどんな機能が入っているのかをくらいの軽い説明にとどめようと思います。

すでにFirecrackerの実装を読んだ人や仮想マシンの実装に慣れた人には「ディレクトリやファイルの名前を見ればわかるよ！」程度のことしか書きませんが、ご了承くださいませ。

なお、調査対象は Firecracker release v0.12.0 のコードとしています。 （この記事を書いている時点での最新版です）

GitHub - firecracker-microvm/firecracker: Secure and fast microVMs for serverless computing.

以下から説明開始です。

  • api_server
  • cpuid
    • 仮想CPUの情報があります
      • brand_string.rs とかを眺めると、 fn from_host_cpuid() が定義されていたりして、なるほどなぁって思えます
      • c3_template.rs や t2_template.rs というファイル名をみると、AWSだなぁという気持ちになれますね
        • 実装のほうはCPUのcpuid命令を知らないと何もわからないと思うので、検索してから実装を読むのがよいかと思います
  • devices
    • legacyとvirtioのサブディレクトリがあります
    • legacyはキーボードとシリアルポートの実装が入ってまして、なんとなく実装を眺めればわかるんじゃないかと思います
      • 仕様を知らない人は調べましょう
      • 全然たいしたことないことがわかるはずです
    • virtioはblockデバイス、メモリマップトIO、ネットなどがありますが、guest osとhost osの間でやりとりするときにvirtioを使う仮装デバイスの実装がここに置かれているようです
  • docs
    • 資料が入っているディレクトリなので説明は省略します
  • dumbo
    • ネットワーク系の実装が置かれています
      • pdu (protocol data unit)のディレクトリには、arpやethernet、ipv4などの実装が置かれています
        • 見ればわかると思いますが、ipv6はありません
      • tcpのディレクトリには、connectionなどがあり、ファイル名をみるだけで「ふーん」って思うこと請け合いです
  • fc_util
    • 時間関係のユーティリティが入ってます
      • 実装がすごく小さいので説明は省略します
  • jailer
    • jailerは非常に重要な立ち位置にいるアプリで、単独でdocs内に説明のmarkdownファイルが置かれています
    • ここの図 でわかるように、chrootやcgroupなど、コンテナ型の仮想化をおこなっています
    • プロダクション環境ではjailerからfirecrackerを呼ぶ事で、上記設計にあるような2重バリアを作ってるんですね
  • kernel
    • firecrackerは起動後、ネットワークを介してvmlinux.binの場所やパラメータを指定します
    • ここの実装では、受け取ったカーネルのイメージをメモリに展開したり、パラメータをvalidationしたりしているようです
    • 実装をちょっと眺めただけで深掘りしていないので間違ってたらごめんなさい
  • kvm
    • KVMで定義されている定数を、enumに再定義しているだけの実装があります
    • firecrackerはKVMを使ってます
    • だからコンテナではなくて仮想マシンなんですよね
  • kvm_gen
    • 自動生成されている実装のようですが、生成器を見た方が良さそうなので読んでません
  • logger
    • みたまんまロガーなので説明は省略します
  • memory_model
    • 実装がすごい簡素なので読んだらわかります
    • ゲストOSのアドレスをいじる実装が入ってます
  • micro_http
    • 名前のとおり、ちっちゃいhttpの実装がはいってます
      • common下にheaderの実装が入っていて、ここではContent-Typeとかのhttp headerを処理しています
      • このあたりはhttpのプロトコルがわかっていればスルッと理解できるはず
      • 知らない人はマスタリングTCP/IPとか読めばいいんじゃないですかね
  • mmds
    • コメントにThe Mmds is the Microvm Metadata Service represented as an untyped json. って説明があります
      • ここに限らず、コメントが結構書かれているので理解の手助けになりますね
    • 小さなデータストアです
    • 実装自体は100行くらいの小さいものなので読めばわかります
  • net_gen
    • 自動生成されている実装のようなので生成器の側を読みたい
    • なのでここは読んでません
  • net_util
    • macアドレスやtapを使って通信するための処理があります
    • 小さいユーティリティで読みやすいかなと思います
  • rate_limiter
    • token bucketを使って処理をブロックしたり解除したりすることでリミッタをかけるんだそうです（コメント読んだだけ）
    • へー、って感じです
    • ファイルを眺めた感じだと、コメントに振る舞いがいっぱい書いてあるので読んで理解するのはそんなに大変じゃなさそうです
    • コメントに ## limitation ってあるのが面白いですね
  • resources
    • microvm-kernel-configというファイルがあります
    • 単に自動生成されたコンフィグファイルですね
  • seccomp
    • システムコールを制限するためのフィルターを提供しています
    • seccompはたくさん情報がインターネット上にあがっているので、理解するにはそれらを先に読むのがいいかなと思います
  • src
    • main.rsがあります
    • ご存知？のとおり、一番上のレベルのメソッドなので、シーケンスを上から追いたい人はここから読むのがいいのかもしれません
  • sys_util
    • OS寄りな処理がはいってます
      • シグナルとかTTYとかioctlとかいろいろな実装が入ってますが、個々の要素はたいしたことない（と思う）ので、概念を知ってから読めばいいだけかなって思います。
      • 実装を眺めていたらpthreadがでてきたので、へー、って思いました
        • 今回の記事とは関係ないですが、macのHypervisor.FrameworkのAPIのドキュメントを読んでいた時もpthreadがでてきたので、ここでもかー、まぁそうだよなーって思っただけです
  • tests
    • テスト
  • tools
    • devtoolとか入ってるところです
    • devtoolはシェルスクリプトでした（最初はてっきりバイナリだと思ってました）
  • vhost_backend
    • なんですかね、これ
    • vsockがらみっぽいので、vsockと通信するためにhost側に用意するもの？うーん
  • vhost_gen
    • 省略
  • virtio_gen
    • 省略
  • vmm
    • microvmの本体！ 間違い。vmmだからvirtual machine monitorでした
      • device_managerは、上で書いたlegacyやmmioのデバイスを管理するためのモジュールのようです
      • vmm_configには、いろいろな設定を処理するモジュールが入ってます
        • microvmの状態やエラーなんかの定義もここにはいってますね
      • 他にもシグナルのハンドラがあったりと、microvmを表現するためのモジュールの塊という印象でした
  • x86_64
    • 仮装CPUのレジスタの保存・復元や、ページテーブルの設定・読み書きなど、CPU周りの処理が入ってます
    • CPUの仕様を参照しながら読むのが良さそうです（けっして全ての仕様を理解してから実装を読もうとしないでください）
      • 本当にツライので

だいぶ駆け足になりました。 説明を書こうとしたら感想文になってしまったのですが、別の機会にちゃんとした説明を書こうと思いますのでご容赦を。

おわりに

f:id:ryotaway:20181220162336j:plain

Firecrackerの実装のさわりの説明というか、さっと眺めた感想を書きました。 なんか、簡単そうだな、という印象を受けてもらえると嬉しいなと思ってますがいかがでしたでしょうか。

この記事は Misoca+弥生+ALTOA Advent Calendar 2018 - Qiitaの20日目の記事でした。 明日は ucho_yayoi さんが「UWSCでデスクトップアプリの自動テスト」について書くそうです。自動テストいいですね。楽しみです。

それでは。