---
marp: true
title: xv6の構成要素の継続の分析
paginate: true
---


# <!--fit--> xv6の構成要素の継続の分析

- 清水 隆博
    - 琉球大学大学院理工学研究科情報工学専攻
- 河野 真治
    - 琉球大学工学部


---

# 研究目的

- アプリケーションの信頼性を向上させたい
  - その為には土台となる OS 自体の信頼性が重要である
- OSそのものも巨大なプログラムである
- 並列並行処理などに起因するバグや、そもそもOSを構成する処理が巨大
  - テストコードを用いた方法で信頼性を確保することが困難
  - テストではなく定理証明とモデル検査でOSの信頼性を高めたい

---

# ノーマルレベルとメタレベルを用いた信頼性の向上

- プログラムの実行部分は以下の2つからなる
    - 入力と出力の関係を決める計算(ノーマルレベル)
    - プログラムを実行したり、 信頼性を保証するために必要な計算(メタレベル)
- メタレベルの例
    - メモリやCPUの資源管理
    - システムコールの動作(副作用)
    - 並行実行(他のプロセスとの干渉)
    - モデル検査(可能な実行を列挙する方式の実行)
    - 証明(入力時と出力時の論理的な条件)、(invariant)
- メタレベルの計算として信頼性を保証する

---

# モデル検査
- 実際に想定されるパターンを全て動かして検証する
- デッドロック発生の検知
  - JavaPathFinderなど
- 状態爆発が問題になる
- Spinを用いる方法では、 promelaという言語で実装し直す必要がある

---

# 定理証明支援系
- 論理学的なモデルに変更して証明する
  - Agda
  - Coq
- HoareLogicを用いる
    - PreCondition -> Statement -> PostCondition
- 従来の方法ではStatementには限られたコマンドしか使えない
    - ループは不変条件を使うが、 条件を見つけることが一般的には困難
    - 実装言語と同じ記述で証明をすることはできない

---
# GearsOSでの信頼性の保証
- メタレベルのみで信頼性の保証を行う
    - ノーマルレベルでの記述は変更しない
- Continuation Based C(CbC)をつかって、ノーマルレベルとメタレベルの分離を行う
- C言語の下位言語であり、 いくつかのCコンパイラ上で実装している
- C言語の構文は使用可能だが、 関数呼び出しの他に軽量継続を持つ
    - 関数呼び出し時のスタックの操作を行わず`jmp`命令で次の処理に移動する
    - schemaなどと違い環境を持たず継続するために軽量継続と呼ぶ

---
# GearsOSでの信頼性の保証

- デフォルトのメタレベルの計算は自動生成される
- 資源管理あるいは検証用のメタ計算は必要に応じて挿入する
- これにより大きなコード変更が無くモデル検査や定理証明を行うことができる
- モデル検査や定理証明の困難さはメタレベルのプログラミングとして吸収する
    - 例えばOSで使用するデータ構造に合わせたモデル検査用の状態圧縮
    - OSの検証に利用できるinvariantの提供
- CbCを用いたOSであるGearsOSを開発している

---
# CbCとCodeGear(ノーマルレベル)
- 軽量継続で表現する単位をCodeGearと呼ぶ
- CodeGearはCの関数とアセンブラの中間の様に使える
- CodeGearは返り値の型の代わりに`__code`で宣言する

```
__code cbc_read(__code (*next)(int ret)){
    struct file *f;
    int n;
    char *p;

    if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0) {
        goto next(-1);
    }
    goto cbc_fileread(f, p, n, next);
}
```
- cbcで書き直したxv6の`read`システムコールの例


---
# CbCとCodeGear(メタレベル)

- `cbc_read_stub`内で必要な引数をcontextから取り出す
    - 取得するものがなければノーマルレベルのCodeGearに継続する

```c
__code cbc_read_stub(struct Context* cbc_context, enum Code next) {
        goto cbc_read(cbc_context, next);
}
```

---
# cbcで書き直したシステムコールディスパッチの例

- CbCは`goto`文で呼び出す
  - 受け取ったシステムコール番号に対応するCodeGearに継続する

```c
void syscall(void)
{
    int num;
    int ret;

    if((num >= NELEM(syscalls)) && (num <= NELEM(cbccodes)) && cbccodes[num]) {
        proc->cbc_arg.cbc_console_arg.num = num;
        goto (cbccodes[num])(cbc_ret);
    }
```

---

# cbcで書き直したシステムコールディスパッチの例


```c
void syscall(void)
{
    int num;
    int ret;

    if((num >= NELEM(syscalls)) && (num <= NELEM(cbccodes)) && cbccodes[num]) {
        proc->cbc_arg.cbc_console_arg.num = num;
        goto (cbccodes[num])(cbc_ret);
    }
```

- 呼び出し元には帰らず、 特定のCodeGearに継続を行う
    - `goto trapreturn()` ユーザープログラムにディスパッチする
    - `goto panic()` 致命的なエラーとしてOSを止める
    - `goto err()` システムコールのエラー処理
        - その後ユーザープログラムにディスパッチする

---

# CbCを用いたソフトウェアの実装

- 計算を実行するためのメモリ領域が必要
    - MetaDataGearと呼ぶ
- メタレベルから見た実行ではcontextとして持ち歩く    
- ノーマルレベルからはアクセスするDataGearのみが見えていて、 ポインタなどは直接は見えない
- contextはプロセスごとに別に存在する
- kernel内で共有されているデータ構造
    - ページテーブル
    - ファイル構造体
    - キャッシュやバッファ
  - これらはkernel context内に置かれる

---

# CbCのcotnext
- CbCのプログラムで利用するCodeGearとデータの組を管理する機能
  - データをDataGearという単位として扱う
  - 計算で使用する各DataGearを実際に保存している
- ノーマルレベルのCodeGear間を遷移するようにプログラミングする
  - ノーマルレベルからはCodeGearを直接操作できず、 メタレベルで操作する
    - メタ計算中でCodeGearの番号をcontextでディスパッチする
- 実際のデータの入手、保存はcontextを触ることが出来るMeta Code Gearが行う

---

# 通常のCbCプログラム

- プログラマから見るとCodeGearからCodeGearへの継続のみに見える
<img src="assets/context1.svg" alt="" style="padding-left: 100px;">

---

# 実際のCbCプログラム

- 実際は1度contextを参照するMetaCodeGearに継続する
    - 番号から次のCodeGearに対応するMetaCodeGearを取り出す

<img src="assets/context2.svg" alt="" style="padding-left: 100px;">

---

# 実際のCbCプログラム

- MetaCodeGearでは次の計算に必要なDataGearを取り出す
    - 全てのDataGearが確保できたらCodeGearにgotoする

<img src="assets/context_last.svg" alt="" style="padding-left: 100px;">


---

# CbCを用いたOSの再実装

- CbCのCodeGearは状態遷移単位での記述に向いている
- 状態遷移を基本としたモデルに変換し、HoareLogicなどの形式手法を用いて信頼性を高めたい
- CbCや定理証明系を用いてアプリケーションとOSを再実装したい
    - 最初の段階として既存のOSをCbCで再実装する

---

# xv6

- マサチューセッツ工科大学で開発されたv6OSをもとにしたOS
    - x86向けにANSI Cで実装されている
- 比較的小さなUNIX
    - 基本的な機能は実装されている
    - システムコール、 ファイルシステム、 プロセス処理...
- Raspberry Pi上で動作を目指したARM用のバージョンも存在する
  - RaspberryPiで動かしたい
  - 今回は ARMのバージョンをCbCで再実装する


---

# xv6のCbCでの書き換え
- 既存のOSを段階的にCbCで書き換えていく
    - 一部スタックを持っている
    - CbCでOSを実装する際のプロトタイプ実装としての段階
- 今回はシステムコール部分の一部、 メモリ管理部分、 ファイルシステムなどを書き換えた
- CbCのcontextをプロセス構造体に埋め込み、 `goto`文を利用する場合はcontextからデータを参照する

---

# read system callの書き換え
- xv6のシステムコールの一部を書き換えることを検討する
- 最初にread systemcallの処理をCodeGearへの書き換えを行った
- readシステムコールなのでreadする対象によって処理が分岐する
    - ファイル
    - inode
    - コンソール
- 読む対象によってCodeGearを書き換えた
  - スケジューラーに接続する箇所や、 sleepする箇所もCodeGearとして書き換える

---

# read system callの継続の一部

- 実際に処理を切り分けているCodeGear
    - ファイルの`type`によって継続先を変更する

```c
__code cbc_fileread (struct file *f, char *addr, int n, __code (*next)(int ret))
{
    if (f->readable == 0) {
        goto next(-1);
    }

    if (f->type == FD_PIPE) {
        goto cbc_piperead(f->pipe, addr, n, next);
    }

    if (f->type == FD_INODE) {
        ilock(f->ip);
        proc->cbc_arg.cbc_console_arg.f = f;
        goto cbc_readi(f->ip, addr, f->off, n, cbc_fileread1);
    }

    goto cbc_panic("fileread");
}
```


---

# read システムコールの状態遷移図

- システムコール中のCodeGearを状態遷移図にした
    - 自然言語で説明可能となる利点がある
<img src="assets/readsyscall.svg" alt="" style="padding-left: 20px;">

---

# システムコール単位での書き換え
- `cbc_fileread` CodeGearなどは複数のCodeGearの集合となっている
    - CodeGearの数が書き換えに伴って増えてしまう
    - CbCのInterface機能によってAPI単位でCodeGearのモジュール化を行っている

<img src="assets/readsyscall.svg" alt="" style="padding-left: 20px;">

---

# Basic Block単位での書き換え

- Basic Blockとはコンパイラの用語でループやリターンを区切りとするプログラミング単位
    - 長くかかるループは間にgotoを挟むことによりメタ計算を間にいれる
    - 1つのCodeGearにいる間は(論理的に)preemptされないことを保証する
- これによりCodeGearを割り込まれない検証の単位とする事ができる


---
# Basic Block単位での書き換え

- 仮想メモリ管理やファイルシステムなどの関数はxv6の場合Cのファイル単位でまとまっている
    - `fs.c`や`vm.c`など
    - CodeGear用のAPIをいきなり設計するのではなく、 段階的に書き換える
- 今回はこれらの関数の内容をCodeGearで書き直した
    - 各関数への呼び出し時にダミーの関数を呼び出すことでCとCbCの相互移動が可能

---

# ファイルシステム操作の書き換え

- ファイルシステムのAPIが実装されている`fs.c`のAPIからCodeGearの集合を定義する
    - 実装にはCbCのInterfaceを用いる
    - 各APIの内部は複数のCodeGearの継続として実装する

```c
typedef struct fs<Type,Impl> {
    __code readsb(Impl* fs, uint dev, struct superblock* sb, __code next(...));
    __code iinit(Impl* fs, __code next(...));
    __code ialloc(Impl* fs, uint dev, short type, __code next(...));
    __code iupdate(Impl* fs, struct inode* ip, __code next(...));
    __code idup(Impl* fs, struct inode* ip, __code next(...));
    __code ilock(Impl* fs, struct inode* ip, __code next(...));
    __code iunlock(Impl* fs, struct inode* ip, __code next(...));
    __code iput(Impl* fs, struct inode* ip, __code next(...));
....
} fs;
```

---
# もとのialloc関数
- inodeのアロケーションを行う`ialloc`関数を書き換えた

```c
struct inode* ialloc (uint dev, short type)
{
    readsb(dev, &sb);
    for (inum = 1; inum < sb.ninodes; inum++) {
        bp = bread(dev, IBLOCK(inum));
        dip = (struct dinode*) bp->data + inum % IPB;

        if (dip->type == 0) {  // a free inode
            memset(dip, 0, sizeof(*dip));
            ...
            return iget(dev, inum);
        }
        brelse(bp);
    }
    panic("ialloc: no inodes");
}
```

---
# ialloc関数

- 対象のデバイスのinodeを一つずつ取り出すループ処理
- 空のinodeがあれば0で初期化後に`iget`でポインタを返す
- アロケーションができなければpanicする

```c
struct inode* ialloc (uint dev, short type)
{
    readsb(dev, &sb);
    for (inum = 1; inum < sb.ninodes; inum++) {
        bp = bread(dev, IBLOCK(inum));
        dip = (struct dinode*) bp->data + inum % IPB;

        if (dip->type == 0) {  // a free inode
            memset(dip, 0, sizeof(*dip));
            ...
            return iget(dev, inum);
        }
        brelse(bp);
    }
    panic("ialloc: no inodes");
}
```

---

# ループ条件の確認のCodeGear(ノーマルレベル)

- CbCでループ条件の判定を行うCodeGearを実装した
    - `for (inum = 1; inum < sb.ninodes; inum++)`に対応する
    - ループ条件を満たなかった場合はpanicに継続する

```c
__code allocinode_loopcheck(struct fs_impl* fs_impl, uint inum,  struct superblock* sb, __code next(...)){
    if( inum < sb->ninodes){
        goto allocinode_loop(fs_impl, next(...));
    }
    char* msg = "failed allocinode...";
    struct Err* err = createKernelError(&kernel->cbc_context);
    goto err->panic(msg);
}
```

---
# ループ条件の確認のCodeGear(メタレベル)

- ノーマルレベルの直前に実行され、contextから値を取り出す

```c
__code allocinode_loopcheck_stub(struct Context* cbc_context) {
        fs_impl* fs_impl = Gearef(cbc_context, fs_impl);
        uint inum = Gearef(cbc_context, fs_impl)->inum;
        superblock* sb = Gearef(cbc_context, fs_impl)->sb;
        enum Code next = Gearef(cbc_context, fs_impl)->next;
        goto allocinode_loopcheck(cbc_context, fs_impl, inum, sb, next);
}
```

---

# ループに復帰するかの判定(ノーマルレベル)
- 空のinodeがあるかどうか(`dip->type == 0)`で継続を分岐させる
    - 0のものがあった場合は初期化を行うCodeGearに遷移する
    - なければループ条件の確認のCodeGearに継続する
- 次のCodeGearへの引数の整合性の確認はメタ計算で実行される

```c
__code allocinode_loop(struct fs_impl* fs_impl, uint inum, short type,   __code next(...)){
    bp = bread(dev, IBLOCK(inum));
    dip = (struct dinode*) bp->data + inum % IPB;
    if(dip->type == 0){
        goto allocinode_loopexit(fs_impl, inum,  bp, dip, next(...));
    }

    brelse(bp);
    inum++;
    goto allocinode_loopcheck(fs_impl, next(...));
}
```

---
# ループに復帰するかの判定(メタレベル)

- 同様に計算に必要は値を取り出して継続する

```c
__code allocinode_loop_stub(struct Context* cbc_context) {
        fs_impl* fs_impl = Gearef(cbc_context, fs_impl);
        uint inum = Gearef(cbc_context, fs_impl)->inum;
        short type = Gearef(cbc_context, fs_impl)->type;
        enum Code next = Gearef(cbc_context, fs_impl)->next;
        goto allocinode_loop(cbc_context, fs_impl, inum, type, next);
}
```

---
# BasicBlock単位での書き換えの考察

- 従来のxv6の関数呼び出しをもとにしているために、コードの変更点が少ない
- CodeGearへの変換を機械的に行うことが可能
- APIそのものはCodeGearを基本とした状態に書き直していない
    - スタックを前提とした処理と共存している


---
# まとめ
- xv6の処理の一部を継続を用いてcbcで書き換えた
  - システムコールに着目する手法
  - 書き換える関数のBasic Blockに着目する手法
- 部分的にCbCでxv6が書き換え可能なことが解った
- 今後はxv6の完全な書き換えを目指す
    - ユーザーコマンド側の書き換えも検討する
- xv6の証明可能な機能/構文の導入を目指す