---
marp: true
title: GearsOSのメタ計算
paginate: true
---


#  GearsOSのメタ計算

- 清水 隆博
    - 琉球大学理工学研究科
    - 198584B
    - 河野研
- [修論本体](http://www.cr.ie.u-ryukyu.ac.jp/hg/Papers/2021/anatofuz-master/raw-file/tip/paper/master_paper.pdf)
- [修論審査スライド](http://www.cr.ie.u-ryukyu.ac.jp/hg/Papers/2021/anatofuz-master/raw-file/tip/slide/index.html)

---
# ノーマル、メタレベルの計算とGearsOS
- ノーマル/メタレベルを一貫して記述できる言語にContinuation Based Cがある
    - CbCを用いてGearsOSを開発している
- GearsOSではメタ計算の生成にトランスパイラを使っている
    - トランスパイラとはコードからコードを生成する処理系のこと
    - 生成しなければならないメタ計算の量が多いため、自動的に生成する
    - CMakeとPerlでビルド時にノーマルレベルのコードをメタレベルに変換する
    - ノーマルレベルで書いた記述がそのままコンパイルされる訳ではない

---
# ノーマルレベル/メタレベルのCodeGear

- ノーマルレベルのCodeGearから見ると、直接別のCodeGearに継続している
- 実際はCodeGearの実行の前後にメタレベルの計算をするCodeGearが実行される
    - メタレベルの計算をするCodeGearをMetaCodeGearと呼ぶ

![h:220 w:800](./metacg.svg)

---
# GearsOSのシステム構成
- MetaDataGearであるContext, TaskManager, Workerによって構成

![](./gears_structure.svg)


---
# GearsOSのビルドシステム
- CMakeとPerlを使ってビルドする
    - CMakeはMakefileやbuild.ninjaを生成する
    - Perlは2種類のスクリプトが自動的に呼ばれる
- Perlによってコード変換・ファイル生成が行われた後にコンパイルが走る
    - Perlの実行前はノーマルレベルだけのコード、実行後はメタが入る

![w:632 h:10cm](./geasflow1.svg)



---

# Context
- 従来のOSのプロセスに相当するMetaDataGear
- GearsOSでのプログラム実行に必要な情報を持っている
    - DataGearの型定義
    - CodeGearの名前とStubCodeGearへの対応
    - goto時に引数を書き込むDataGearごとの場所
    - DataGearを管理するヒープ情報
---
# Context
- GearsOSでcontextを触るのはメタ計算部分だけ
    - ノーマルレベルではcontextに触れない
- 従来は手書きでcontext.hの中で定義
- Context自体は構造体で定義されている
![w:532 h:10cm](./context.svg)


---
# メタレベルでのDataGearの管理
- メタレベルではDataGearを纏めて管理する必要がある
- すべてのDataGearはCの共用体を使って定義される
    - `union Data`型
- `union Data`はすべてのDataGearにキャストすることが可能
    - Contextには`union Data`としてDataGearを保存する
- メタレベルの計算では必ずこの`union Data`が利用される

```c
union Data {
    struct Stack {
        ...
    } Stack;
    struct SingleLinkedStack {
        ...
    } SingleLinkedStack;
    struct Context Context;
    ...
}
```

---
# union Dataの定義

- union Data型はcontext.hに定義されている
- 計算で使うすべてのDataGearの構造体の定義を列挙する
    - 従来は手書きですべて記述
    - Intefaceの定義を書き、CbCを書き、context.hに追記...
- 手書きで生成していたので、いくつかの問題があった
    - 整理しないと計算に使わないDataGearの定義が残る
    - Interfaceの定義ファイルと食い違うケースがある
    - DataGearの数が増えると手書きするのが煩雑
- すべてのメタレベルの計算の元となる重要なデータ
    - 手書きの場合ミスが発生する可能性が高い




---
# メタレベルに変換されたGearsOSの実装
- ノーマルレベルのCodeGearの継続は、contextとCodeGearの番号のみ指定する
    - 次の継続を番号で指定する
    - 次の継続への引数も値をcontextに書き込むように変更される

- CodeGearの継続は直接行かず、MetaCodeGearを経由して継続する
    - 呼び出したいCodeGearはMetaCodeGearが番号から取り出す
    - アドレスを直接使うのはメタ計算のみ
    - 各CodeGearはContextのみ持ち歩き、入力はStubCodeGearから与えられる

---
# CodeGear、DataGearの番号
- Perlで変換するとCodeGear/DataGear番号の形に抽象化される
    - 番号から具体的なCodeGear/DataGearを取り出すのはメタレベル
        - `goto meta`でcontextからCodeGearの取り出し
        - StubCodeGearでcotnextからDataGearの取り出し

---
# CodeGearの番号
- ビルドするCbCファイルをPerlで解析し、`__code`を数え上げる
    - 連番でenumを生成する
- Contextの中にCodeGearの配列がある
    - StubCodeGearへの参照が含まれている

```c
enum Code {
    C_checkAndSetAtomicReference,
    C_clearSingleLinkedStack,
    C_clearSynchronizedQueue,
    C_createTask,
    C_decrementTaskCountTaskManagerImpl,
    C_exit_code,
    C_get2SingleLinkedStack,
    ...
};
```
---
# DataGearの番号
- union Dataで定義されている構造体一覧からPerlで生成される
    - context.hの内容に依存する

```c
enum DataType {
    D_Code,
    D_Atomic,
    D_AtomicReference,
    D_CPUWorker,
    D_Context,
    D_Element,
    ...
};
```

---
# StubCodeGear
- DataGearにアクセスするにはContextから番号を指定して行う
- メタレベルのCodeGearは引数はContextのみになっている
    - CodeGearの引数に指定していたものは、ContextからMetaCodeGearで取り出す必要がある
- StubCodeGearはCodeGearの直前に実行されて、DataGearをContextから取得する


![w:540 h:400](./contextContinuation.svg)


---
# GearsOSの新機能
- **自由なMetaCodeGearの作製、継続の入れ替え機能**
- Perlトランスパイラの変換ルーチンのデバッグ機能の追加
    - トランスパイラそのもののデバッグが困難であった
- ジェネリクスのサポート

---
# メタ計算の切り替えAPI
- 通常だとCodeGearの実行後、`goto meta`に継続するようにPerlで変換される
    - 継続するMetaCodeGearを自由に選択したい
```c
__code thinkingPhilsImpl(struct Context *context,struct PhilsImpl* phils,
                                        struct Fork* fork, enum Code next) {
    printf("%d: thinking\n", phils->self);
    goto meta(context, C_pickup_lforkPhilsImpl);
}
```

- 例えばモデル検査用のMetaCodeGear(`mcMeta`)にgotoさせたい

```c
__code thinkingPhilsImpl(struct Context *context,struct PhilsImpl* phils,
                                        struct Fork* fork, enum Code next) {
    printf("%d: thinking\n", phils->self);
    goto mcMeta(context, C_pickup_lforkPhilsImpl);
}
```


---
# mta.pm
- CodeGearが継続するMetaCodeGearを自由に選択できるPerlモジュールを導入した
- APIに沿ってPerlモジュールを書くことで特定のCodeGearの継続先を変更可能
    - Perlトランスパイラがコード変換時に自動ロードして実行する
![w:932 h:10cm](./metapm.svg)



---
# meta.pm

- `replaceMeta`関数に置換対象と生成する`goto`の組をリストで登録
    - `qr//`に正規表現リテラルで置換対象のCodeGearの名前を指定
    - `=>`の先に対応するgoto文の生成関数を指定する
- この例では`PhilsImpl`が名前についているCodeGearが一括で`goto mcMeta`になる

```perl
package meta;

sub replaceMeta {
  return (
    [qr/PhilsImpl/ => \&generateMcMeta],
  );
}

sub generateMcMeta {
  my ($context, $next) = @_;
  return "goto mcMeta($context, $next);";
}
```



---
# 今後の課題
- Perlトランスパイラのリファクタリング・GearsOSのビルド方法の見直し
    - 機能が充実したが複雑度が全体的に増してしまった
- PerlトランスパイラのGearsOS本体への組み込み
    - Perlトランスパイラが行っている処理はリンカ、ローダーに近い
    - OSが機能としてサポートしていてほしい
    - GearsOS自身で記述したい
- xv6への組み込み
    - GearsOSを既存のUNIXの置き換えとして実行したい
- ノーマルレベルの記述の純粋関数化、別の言語での定義
    - CbC/Cベースの記述ではノーマルレベルの記述に限界がある
    - Perlトランスパイラの機能をさらに拡張すると、PerlでCbCコンパイラを実装することに近くなってしまう
---
# まとめ
- Perlトランスパイラのフレームワークの機能を充実させた
- Interfaceシステムを改良した
    - 型定義ファイルの導入を行った
        - 定義方法に一貫性が出た
    - Perlトランスパイラで警告を発生させるようになった
- 従来手書きしていたメタな定義をビルド時に自動的に生成するようにした
    - 煩雑な処理や手で実装することによるバグの混入を回避
- MetaCodeGearの制御をユーザー側で行えるようにした
    - モデル検査をメタ計算として自在に組み込むことが可能となった