Hacking mruby binary format for mruby-2.0.1

mruby のバイナリフォーマットについての覚え書きです。
mruby-2.0.1 から採用されたものを対象としています。

mruby-2.0 より前のものについては [mrubyのバイトコードフォーマット解説 « 他人の空似](https://resemblances.click3.org/?p=1594) が参考になります。

メモリ上における構造体の配置を概略図で表すため、次の形を用いています。

```
+---+
|   |  <- 1 バイトフィールド
+---+

+---+---+
|       |  <- 2 バイトフィールド
+---+---+

+---+---+---+---+
|               |  <- 4 バイトフィールド
+---+---+---+---+

+===============+
|               |  <- 可変長・4バイトを超えるフィールド
+===============+
```


## 全体の構造

最初にヘッダがあり、データはセクションという単位によって構造化されています。

```
+===============+ +===================+ +===============+     +=====================+
|     ヘッダ    | | セクション "IREP" | |  セクション2  | ... | セクション "END\0"  |
+===============+ +===================+ +===============+     +=====================+
```

未知のセクション (認識できないセクション) は単純に読み飛ばす仕組みになっており、同じバージョン間での拡張を可能としています。

また、いったん出力した mruby バイナリを後から加工することも容易です。

### バイトオーダ (エンディアン)

16ビット整数や32ビット整数を格納する場合、ネットワークエンディアンを用いています。


## ヘッダ

mruby バイナリフォーマットとして認識するための情報が記述されています。

必ずファイルの始めに位置します。

mruby-2.0.1 から引用した構造体定義:

> ```c:mruby-2.0.1/include/mruby/dump.h
> struct rite_binary_header {
>   uint8_t binary_ident[4];    /* Binary Identifier */
>   uint8_t binary_version[4];  /* Binary Format Version */
>   uint8_t binary_crc[2];      /* Binary CRC */
>   uint8_t binary_size[4];     /* Binary Size */
>   uint8_t compiler_name[4];   /* Compiler name */
>   uint8_t compiler_version[4];
> };
> ```

メモリレイアウトを図に表すと次のようになります:

```
バイナリヘッダ (22バイト):
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
    |   identifier  |    version    |  crc  |      size     | compiler name | compiler ver  |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```

`identifier` フィールドは mruby binary であることを示す識別子で、`"RITE"` 固定です。
もし `"ETIR"` であればリトルエンディアンとして扱うことになりますが、mruby-2.0.0 からはあってもなくても同じような処理になってます。
特にバイト指向の可変長命令に変更されているため、いつの時代も悩みのタネの一つであるバイトオーダの変換がなくなっています。
まだいくつかバイトオーダ関係のコードが残っていますが、削除してしまっても問題ない気がします (プルリクエストのチャンス？)。

`version` フィールドは mruby binary format のバージョンを示し、`"0006"` となります。
バイナリ形式が異なると、無限ループや `SIGSEGV` を起こします。

`crc` フィールドは CRC-16-CCITT によってバイナリデータを検査するために用いられます。
範囲は `crc` フィールドの次のバイト位置から、バイナリデータの終わりまでです。
mruby に実装されている CRC-16-CCITT はビット単位で処理しているため低速ですが、生成されるオブジェクトコードを小さく出来ます。
[mruby の CRC-16-CCITT を Slicing by 4 で実装](https://qiita.com/dearblue/items/b429f80ba0a4730b94f2)したことがありますが、テーブルが大きくなるので (2048バイト) 流石にプルリクエストにはしませんでした。

`size` フィールドは `identifier` を含んだバイナリデータの終わりまでのバイト数です。
このフィールドは符号なし32ビット整数値が埋め込まれており、なおかつアライメントが4バイト境界にありません。

`compiler name` と `compiler version` フィールドは mruby binary format を生成するために用いたコンパイラを示すものです。
読み出し時には使われません。


## セクション

セクションは共通のヘッダから始まり、セクション固有のデータを保持しています。

mruby 仮想マシンの実行コードを保持する "IREP" セクションと終わりを示す "END\0" セクションのみが必須で、他のセクションは任意です。

共通のセクションヘッダ:

> ```c:mruby-2.0.1/include/mruby/dump.h
> #define RITE_SECTION_HEADER \
>   uint8_t section_ident[4]; \
>   uint8_t section_size[4]
> ```

メモリレイアウトを図に表すと次のようになります:

```
セクションヘッダ (8バイト):
    +---+---+---+---+---+---+---+---+
    | section ident | section size  |
    +---+---+---+---+---+---+---+---+
```

`section ident` フィールドは、そのセクションが何であるかを示す識別子です。

`section size` フィールドは、セクションヘッダを含めたそのセクション全体の大きさをバイト数で示しています。

### "END\0" セクション

mruby binary format が終わりであることを示しています。
これ以降に続くあらゆるデータは無視されます。

### "IREP" セクション

追加セクションヘッダ:

> ```c:mruby-2.0.1/include/mruby/dump.h
>   uint8_t rite_version[4];    /* Rite Instruction Specification Version */
> ```

mruby の実行コード本体となるデータを納めているセクションです。

追加セクションヘッダの `rite_version` フィールドさんはいない子扱いされててカワイソス。

追加セクションヘッダの直後から irep レコードが続きます。

irep レコードはブロック・クラス・モジュール・メソッドによって区切られており、概念的には入れ子になっています。
しかし外から眺めただけでは、ただ irep レコードが順に詰まっているかのように配置されます。

irep レコードの構造については構造体の定義がないため、`read_irep_record()` および `read_irep_record_1()` 関数を眺めて理解する必要があります。

```
irep レコード (可変長バイト):
    +================+ +===============+ +================+ +==================+ +=======================+
    | レコードヘッダ | | iseq ブロック | | プールブロック | | シンボルブロック | | 次の irep レコード... |
    +================+ +===============+ +================+ +==================+ +=======================+

レコードヘッダ (10バイト):
    +---+---+---+---+---+---+---+---+---+---+
    |  record size  | nlvar | nrvar | nirep |
    +---+---+---+---+---+---+---+---+---+---+
```

`record size` フィールドは、irep レコードヘッダを含め、子 irep を含めない irep レコードの大きさを、符号なし32ビット整数値として格納しています。
……と思わせておいて、少なくとも mruby-2.0.1 では計算が間違っているため***無視しなければらない値***です (プルリクエストのチャンス！！)。

`nlvar` (number of local variable) フィールドはローカル変数の数を、符号なし16ビット整数値として格納しています。
バイトコードに変換するとローカル変数の変数名が失われるため、後で紹介する "LVAR" セクションで使います。

`nrvar` (number of register variable) フィールドはこの irep を実行するために必要なレジスタ数を、符号なし16ビット整数値として格納します。

`nirep` (number of child irep) フィールドは、この irep が直接保持するブロック・クラス・モジュール・メソッドの irep の数です。

#### iseq ブロック

```
iseq ブロック (4バイト以上):
    +---+---+---+---+=======+===============+
    |   iseq size   |  PAD  |     iseq      |
    +---+---+---+---+=======+===============+
```

`iseq size` フィールドは、`instruction sequence` のバイト長です。

`PAD` (padding) は、iseq を配置する時4バイト境界に合わせるために置かれます。0〜3の値を取ります。
iseq はすでにバイト指向となっているため、不要に出来るかもしれません (プルリクエストのチャンス？)。

`instruction sequence` フィールドは、mruby 仮想機械に与えるバイトコード本体です。

#### プールブロック

```
プールブロック (4バイト以上):
    +---+---+---+---+===============+
    |  num of pool  | プールデータ  |
    +---+---+---+---+===============+

プールデータ:
    +===============+ +===============+     +===============+
    |  pool entry1  | |  pool entry2  | ... |  pool entryN  |
    +===============+ +===============+     +===============+

pool entry:
    +---+---+---+===============+
    | T |  len  |   pool body   |
    +---+---+---+===============+

    T: type
    len: length
```

`num of pool` (number of pool) フィールドは、irep に埋め込まれたオブジェクトの数を符号なし32ビット整数値で格納します。

`type` フィールドは `enum irep_pool_type` の値を取ります。

`length` フィールドはオブジェクトデータのバイト長です。

`pool body` がオブジェクトデータ本体となります。

オブジェクトが複数ある場合は、さらに `enum irep_pool_type`、バイト長、データ本体が繰り返されます。
埋め込み可能なオブジェクトの種類は限定されており、`String` と `Fixnum`、 それに `Float` です。
これら以外のオブジェクト形式は `nil` として構築されます。

#### シンボルブロック

```
シンボルブロック (4バイト以上):
    +---+---+---+---+===================+
    |  num of pool  |  シンボルデータ   |
    +---+---+---+---+===================+
```

`num of symbol` (number of symbol) フィールドは、irep に埋め込まれたシンボルの数を符号なし32ビット整数値で格納します。

`symbol data` フィールドには、埋め込まれたシンボルの実体がベタ詰めされています。
最初の2バイトがシンボルを表す文字列のバイト長 (`NUL` 文字を含まず)、シンボルとしての文字列、`NUL` 文字が続き、一つのシンボルとなります。
複数個のシンボルがある場合は、連続して埋め込まれています。

(雑音) 以前この後に `rescue` や `ensure` のためのエラーハンドリングテーブルを置こうと個人的に画策していましたが、今まで忘れてました……。
これは CRuby のような仕組み、さらに言えば DWARF 形式の C++ 例外の仕組みを後追いしようとしたものです。
iseq の生成をいじったはいいけど仮想機械の内部状態が把握できていないままほったらかしになってます……。

### "DBG\0" セクション

レコード単位で別れており、これは既に読み込まれていなければならない入れ子となっている irep レコード一つ一つに対応付けされます。

このセクションは、ファイル名テーブルとデバッグレコードによって構成されます。

```
セクションデータ (可変長バイト):
    +=======================+ +===================+
    |  ファイル名テーブル   | | デバッグレコード  |
    +=======================+ +===================+
```

ファイル名テーブルはファイル名がいくつ含まれているか、そして複数個のファイル名そのものによって構成されます。

```
ファイル名テーブル (2バイト以上):
    +---+---+===============+
    | fnnum |   file names  |
    +---+---+===============+

file names:
    +---+---+===============+
    | fnlen |   file name   |
    +---+---+===============+
```

`debug record` はレコードサイズ、複数個のデバッグ情報ファイルによって構成されます。
※(妄想) ここで使われている「ファイル」は「レジスタファイル」と同じで、器・入れ物といった意味合いかもしれません。

```
debug record:
    +---+---+---+---+ +---+---+===============+
    |  record size  | |  flen | dbg info file |
    +---+---+---+---+ +---+---+===============+
```

デバッグ情報ファイルは、iseq の開始位置、ファイル名インデックス、行に関する情報から構成されます。

```
dbg info file (debug information file):
    +---+---+---+---+ +---+---+ +---+---+---+---+ +---+ +===============+
    |   start pos   | | fnidx | |  line ent cnt | | t | |   line entry  |
    +---+---+---+---+ +---+---+ +---+---+---+---+ +---+ +===============+

    start pos:    start position
    fnidx:        filename index
    line ent cnt: line entry count
    t:            line type
    line entry:   line entry
```

デバッグ情報ファイルに開始位置とファイル名が紐づけされている理由は、`mrbc` コマンドによって複数の `.rb` ファイルをまとめて一つの `.mrb` ファイルへとまとめることが出来るためでしょう。

`line entry` は可変長配列です。さらに、`line type` によって構造が異なる点に注意する必要があります。

```
line entry (line type = mrb_debug_line_ary):
    +---+---+    +---+---+
    | line1 | .. | lineN |
    +---+---+    +---+---+

line entry (line type = mrb_debug_line_flat_map):
    +---+---+---+---+---+---+    +---+---+---+---+---+---+
    |   start pos1  | line1 | .. |   start posN  | lineN |
    +---+---+---+---+---+---+    +---+---+---+---+---+---+
```

`line type` が `mrb_debug_line_ary` の場合、命令一つ一つに対して行番号が紐付けられるっぽい？

`line type` が `mrb_debug_line_flat_map` の場合、複数の命令をまとめて行番号を紐づけているっぽい？


### "LVAR" セクション

レコード単位で別れており、これは既に読み込まれていなければならない入れ子となっている irep レコード一つ一つに対応付けされます。

```
LVAR セクション:
    +===================+ +===============+
    | シンボルテーブル  | |   レコード    |
    +===================+ +===============+
```

レコードの前には、シンボルテーブルが置かれます。
使われる変数名がスコープごとに異なることは少ないので、メモリ効率と "LVAR" セクションの読み込み効率を両立させる事を目的としているんじゃないかなと思います。

```
シンボルテーブル:
    +---+---+---+---+ +===========+    +===========+
    |   symbol num  | |  symbol1  | .. |  symbolN  |
    +---+---+---+---+ +===========+    +===========+

symbol:
    +---+---+===============+
    | symln |  symbol name  |
    +---+---+===============+
```

そしてレコードが続きます。

```
レコード:
    +---+---+---+---+    +---+---+---+---+
    |   lvar link1  | .. |   lvar linkN  |
    +---+---+---+---+    +---+---+---+---+

lvar link:
    +---+---+---+---+
    | symix | regid |
    +---+---+---+---+

```

`lvar link` とローカル変数の添字を合わせ、`symix` で示されたシンボルテーブルのシンボルおよび `regid` で示されたレジスタ番号を結びつけます。
`symix` が `RITE_LV_NULL_MARK` であれば、無名変数として扱われます。
`lvar link` の個数は、irep レコードの `lvnum` (ソースコードの構造体定義だと `nlocals`) から `-1` した数となります。
この `-1` が何のためなのかは、そのうち探ります。

続けて `irep->rlen` で示された子 irep の数だけ子レコードを読み込みます。

### "LINE" セクション

mruby-2.0.1 では出力しないようになっているんですね。だけど読み込み処理は書かれてる…… (コード削除のチャンス？)。

レコード単位で別れており、これは既に読み込まれていなければならない入れ子となっている irep レコード一つ一つに対応付けされます。

```
レコードヘッダ:
    +---+---+---+---+---+---+===============+===============+
    |  record size  | fnlen |   file name   |   iseq num    |
    +---+---+---+---+---+---+===============+===============+

iseq num:
    +---+---+---+---+     +---+---+
    | line1 | line2 | ... | lineN |
    +---+---+---+---+     +---+---+
```

`record size` フィールドは、そのレコード自身のバイト長が符号なし32ビット整数値で格納されています。……irep レコードの時と同じようにいない子扱い……。

`fnlen` (length of file name) フィールドは、ファイル名のバイト長が符号なし16ビット整数値で格納されています。

`file name` フィールドは、ファイル名を表す可変長バイト列が格納されています。

`number of iseq` フィールドは、対応する iseq レコードの命令長と同じ長さが格納されています。

`line1` 〜 `lineN` フィールドは、対応する命令が Ruby スクリプトの何行目に当たるかを示しています。

mruby-2.0.1 の `mrbc` コマンドは、複数の `.rb` ファイルを一つの `.mrb` ファイルにすることが出来るので、一つの `.rb` ファイルしか想定していないこの "LINE" セクションはお役御免となっているように感じます。


## mruby-2.0.0 バイナリフォーマットとの差異

irep レコードのプールブロックに置かれる浮動小数点数の扱いが異なります。

<https://github.com/mruby/mruby/pull/4219>


## 最後に

プルリクエストのネタになりそうな所がいくつかありました。

他のネタとしては、"DBG\0" セクションや "LVAR" セクションもテーブルをヒープメモリに展開しているので、そんなことはしないで必要になった時に必要なものをピンポイントで取り出せる仕組みを導入することで RAM の消費が抑えられそうだなと感じました。

固定長データ配列を基本にして可変長はそこへのカーソルを記録しても、デバッグ情報が必要にならなければ負担も無視できるように思います。
ただしいくらか ROM が増えそうですけどね。

## 寝言

<sup><sub>実は irep レコードの遅延読み込みを画策して、そのためにまとめた資料です。
irep レコードの <code>record size</code> が壊れて使われていないので、これを再利用して子 irep レコードを含めたバイト長を表すようにすれば出来そうです。
僕が実現できるかどうかはまた別ですけどね……。</sub></sup>