Mercurial > hg > Document > Growi

# CbC による xv6 の FileSystem の書き換え
- 並列信頼研

- 坂本昂弘
## 研究目的
- OSに対し高い信頼性を実現させたい

- そのために当研究室ではContinuation based C (CbC)を用いたGearsOSを設計中である

- 前段階としてシンプルであるが基本的な機能を揃えたOSであるxv6をCbCで書き換える

- xv6のFilleSystemをCbCで記述し、なるべく処理を細分化実装してやる

---

# Continuation based C
- 状態遷移ベースで記述できる言語(以下CbC)
- C の関数呼び出しとは異なり、stack に値を積まない
- Code Gear
    - 基本的な処理の単位
    - goto 文で遷移する
- Data Gear
    - Code Gear からアクセスできるデータの単位
    - 引数など


---
# Code Gear による継続
- Code Gear の処理の間を goto によって遷移していく
- __code CodeGear名 で定義
![](https://i.imgur.com/etfQund.png)


---

# Data Gear の受け渡し
- Code Gear からアクセスできるデータ
- Code Gear の計算の入力と、計算の出力が存在する

![](https://i.imgur.com/3E0DGWA.png)


---

# Data Gear の一種であるContext

- Contextには実行するプログラムの全てのData Gear と Code Gear が登録されている
- ユーザープロセスに対応して1つのcontextが存在する
- CodeGearの入出力は、一度Contextに書き込まれる
- Contextは実行している処理の状態を保持している
    - そのためContextを見れば、実行中の処理がわかる
 ![](http://ie.u-ryukyu.ac.jp/~e165723/context.pdf)

---

# Xv6
- MIT の講義用教材として作られたOS
- xv6 は Unix の基本的な構造を持っている。
    - プロセス
    - 仮想メモリ
    - ファイルシステム
- Xv6 をCbCで書き換える

---

# Xv6のFileSystem
- FileSystem は コンピュータの資源を操作するための OS が持つ機能である
- xv6 の FileSystem は、デバイスやプロセス、カーネル内の処理をする際の情報などをファイルとして扱う
- inodeを用いファイルの管理や操作を行う
- inodeはディスク上にブロックを持つ木構造のデータ構造
---

# Xv6の書き換え方針
- 段階的に書き換えていきたい
- FileSystem を書き換える理由
    - FileSystem は状態が複雑に変化するため、信頼性を保証する必要がある
- インターフェースを定義、実装する
- 状態遷移ベースにしてやる

---

# インターフェースの導入
- CbC のモジュール化の方法
- Javaのインターフェースと同様
- インターフェースによるメリット
    - 複雑な状態の解消
    - 入力の切り替えによる実装の入れ替え
- 実装は別で定義し、呼び出す
    - 後ほど説明

---

# インターフェースの定義
- Xv6 の FileSystem の インターフェース
- typedef struct の直後にインターフェース名(fs)を書く
- fs で使う Code Gear を登録する
- Code Gear は __code CodeGear名(引数); で記述する
    - 引数が Data Gear に相当する
- 第1引数の Impl* fs がインターフェースの実装の型になる
- privateな実装側のヘッダーファイルも インターフェース と同じように用意する
``` 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(...));
....
} fs;
```
---


# インターフェース実装内の CbC
- for文やif文がある場合はさらに実装を分ける
    - Basic Block をもとに状態遷移ベースで記述することを目標とする
- インターフェースは外から呼び出されるAPI
- それに対してインターフェースの実装の Code Gearから明示的に呼び出される Code Gearは、Java の private メソッドのように扱われる。
- 実際に書き換えた一部の例として fs.c の ialloc の実装を分けた記述を説明する

![](https://ie.u-ryukyu.ac.jp/~e165723/seni.pdf)
```clike
__code iallocfs_impl(struct fs_impl* fs, uint dev, short type, __code next(...)) {
    goto allocinode(fs, dev, sb, next(...));
}
```
- 関数が呼び出されるとprivate実装に遷移する

---

# ialloc の CbCによる書き換え
- FileSystemの代表的なAPIであるiallocをCbCで書き直した
- ialloc
    - inodeにi-numberという番号を割り当てている

## 元ソースコード
- ialloc のソースコードの一部
- for文の中でif文の処理が行われ、複雑である
- for文とif文を切り分けてやる
```clike
    for (inum = 1; inum < sb.ninodes; inum++) {
        bp = bread(dev, IBLOCK(inum));
        dip = (struct dinode*) bp->data + inum % IPB;

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

```

## iallocの処理の流れ
![](https://ie.u-ryukyu.ac.jp/~e165723/iallocloop.pdf)

## CbCで書き換えたiallc
### 書き換え前
- まずfor文のループするかどうか、条件を確認する
```clike
for (inum = 1; inum < sb.ninodes; inum++) {
    ....
}
```
### 書き換え後
- ループの条件に合うかどうかを確認するためのCodeGearに遷移する
```clike
__code allocinode(struct fs_impl* fs_impl, uint dev, struct superblock* sb, __code next(...)){ //:skip
....
    goto allocinode_loopcheck(fs_impl, inum, dev, sb, bp, dip, next(...));
}
```
- allocinode_loopcheckに遷移しループの条件の確認を行う
```clike
__code allocinode_loopcheck(struct fs_impl* fs_impl, uint inum, uint dev, struct superblock* sb, struct buf* bp, struct dinode* dip, __code next(...)){ //:skip
    if( inum < sb->ninodes){
        goto allocinode_loop(fs_impl, inum, dev, type, sb, bp, dip, next(...));
    }
    ....
}
```
- ループ文の条件に当てはまらなかった場合panicへ遷移し処理が終わる
```clike
__code allocinode_loopcheck(struct fs_impl* fs_impl, uint inum, uint dev, struct superblock* sb, struct buf* bp, struct dinode* dip, __code next(...)){ //:skip
    ....
    char* msg = "failed allocinode...";
    struct Err* err = createKernelError(&proc->cbc_context);
    Gearef(cbc_context, Err)->msg = msg;
    goto meta(cbc_context, err->panic);
}
```
### 書き換え前
- for文の中で処理が行われているif文
- ループを抜けるか確認
```clike
if (dip->type == 0) {
    ....
}
```
### 書き換え後
- ループから抜けるかどうかを確認する
- 抜ける場合はallocinode_noloopへ遷移する
```clike
__code allocinode_loop(struct fs_impl* fs_impl, uint inum, uint dev, short type, struct superblock* sb, struct buf* bp, struct dinode* dip, __code next(...)){ //:skip
    ....
    if(dip->type = 0){
        goto allocinode_noloop(fs_impl, inum, dev, sb, bp, dip, next(...));
    }
    ....
}
```
- ループから抜けなかった場合
- inumの値をインクリメント
- 再びallocinode_loopcheckへと遷移する
```clike
__code allocinode_loop(struct fs_impl* fs_impl, uint inum, uint dev, short type, struct superblock* sb, struct buf* bp, struct dinode* dip, __code next(...)){ //:skip
....
inum++;
goto allocinode_loopcheck(fs_impl, inum, dev, type, sb, bp, dip, next(...));
}
```
### 書き換え前
- 処理が抜けた場合
- 変更された値などを更新
- logに書き込んでやり保持していた値解放
- returnでigetを返し終了
```clike
    memset(dip, 0, sizeof(*dip));
    dip->type = type;
    log_write(bp);
    brelse(bp);
    return iget(dev, inum);
```
### 書き換え後
-　処理を抜けた場合allocinode_noloopへ遷移
-　処理を行い値を返し終了
```clike
__code allocinode_noloop(struct fs_impl* fs_impl, uint inum, uint dev, short type, struct superblock* sb, struct buf* bp, struct dinode* dip, __code next(int ret, ...)){ //:skip
    memset(dip, 0, sizeof(*dip));
    dip->type = type;
    log_write(bp);
    brelse(bp);
    ret = iget(dev, inum);
    goto next(ret, ...);
}

```

---
# 書き換えの評価
- 今回はfor文やif文がある場合切り出してやり、Basic Block 単位に書き換えることができた
- Basic Block 単位に書き換えたことによって、組み合わせを変え処理の改善などに利用可能


## まとめと今後の方針
- OS 内部で CbC インターフェースを扱えるようになった
- CbC の書き換えが完了すれば、継続の入力と出力を検査することで OS の信頼性を保証したり、インターフェースの実装の入れ替えが可能になり拡張性が実現可能
- デバックをまだ行っていないため正常に動くかどうか確認することが求められる
author	autobackup
date	Wed, 26 May 2021 00:10:03 +0900
parents	b6c284fd5ae4
children