2019-12-08

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されます。

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

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

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

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

という動きになり、 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

2019-12-03

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

2019-05-28

OculusQuestめっちゃ楽しい

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

f:id:ryotaway:20190528223323j:plain

主にYouTube VRを見てる。

超控えめに言って最高。

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

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

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

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

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

2018-12-20

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
- firecrackerを使うときは、unix socketを使ってjson形式の設定を送信する必要があります
- 詳細は firecracker/getting-started.md at master · firecracker-microvm/firecracker · GitHub を参照すればわかります
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でデスクトップアプリの自動テスト」について書くそうです。自動テストいいですね。楽しみです。

それでは。

はじめに

BFとは

今回作るBFの仕様

仕様

基本設計

メモリ

レジスタ

命令セット

実装

ファイルのロード

命令の実行

[ と ]

ビルド

サンプルの実行

[ H: 72]

] の直後のスペース

++++++++++

[

>+++++++<-]

>++.>

おわりに

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

BFの実行結果

WebGLで描画した結果

はじめに

マンデルブロ集合？

WebGL？

まずは結果

実装

html

javascript

実装のポイント

まとめ

はじめに

Firecrackerとはなにか

実装について

と意気込んだものの

おわりに

`[` と `]`

`[ H: 72]`

`]` の直後のスペース

`++++++++++`

`[`

`>+++++++<-]`

`>++.>`