title: CbC による xv6 の FileSystem の書き換え
author: Takahiro Sakamoto, Shinji Kono

profile: 琉球大学工学部情報工学科並列信頼研

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

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

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

- CbCは処理の基本単位をCodeGearとし、stackに値を積む事なくCodeGear間を遷移する

- CodeGear間は状態遷移であるためOS内部を明確化することができる

- 本研究ではOS内部の明確化を実現し信頼性を向上させるためにCbCを用いFileSystemを書き換える

## 研究概要
-
## Continuation based C
* Continuation based C (CbC) はこの Code Gear 処理の単位としてプログラミング言語として開発している。
* Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する
* この goto 文による遷移を軽量継続と呼ぶ
* 継続を用いることによって状態遷移ベースでのプログラミングが可能である
* CbC は C と互換性のある言語なので、C の関数も呼び出すことができる
## CbC のコード例
* CbC では Code Gear は \_\_code Code Gear 名 (引数) の形で記述される
* Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない
* goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する

## CbC のコード例
* この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる

```
__code cg0(int a, int b){
  goto cg1(a+b);
}

__code cg1(int c){
  goto cg2(c);
}
```
## CbC の継続

## Gears におけるメタ計算
* Gears OS ではメタ計算を Meta Code Gear、Meta Data Gear で表現する
* Meta Code Gear はノーマルレベルの Code Gear の直後に遷移され、メタ計算を実行する
* Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う

## Meta Gear
* Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する
* 通常の計算からはメタ計算は見ることができない


## Context
* Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている
* Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある
* Context は Meta Data Gear であるため、Meta Code Gear を介してアクセスする

## Context
* Context は全ての Code Gear のリストを持っており、enum で番号とアドレスを対応付けている
```
enum Code {
    C_popSingleLinkedStack,
    C_pushSingleLinkedStack,
    C_stackTest3,
    C_assert3,
    ...
};
```
```
context->code[C_popSingleLinkedStack] = popSingleLinkedStack_stub;
context->code[C_pushSingleLinkedStack]  = pushSingleLinkedStack_stub;
context->code[C_stackTest3] = stackTest3_stub;
context->code[C_assert3] = assert3_stub;
```

## Context
* Data Gear も Code Gear と同様に Context が全ての Data Gear のリストを持っている
* Data Gear のリストも enum で管理されている
* これは引数格納用の Data Gear の番号である
```
enum DataType {
    D_Code,
    D_SingleLinkedStack,
    D_Stack,
    D_TaskManager,
    D_Worker,
    ...
    };
```

## Interface
* Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される
* Interface は GearsOS でのモジュール化の仕組み
* Interface は使用される Data Gear の定義と、それに対する Code Gear の集合である
* Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる

## Interface の定義
* Stack の Interface の例である
* typedef struct Interface 名で記述する
* Impl は実際に実装した際のデータ構造の型になる

```
typedef struct Stack<Impl> {
    union Data* stack;
    union Data* data;
    __code next(...);
    __code whenEmpty(...);

    __code clear(Impl* stack, __code next(...));
    __code push(Impl* stack, union Data* data, __code next(...));
    __code pop(Impl* stack, __code next(union Data* ...));
    __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));

}
```
## Interface の定義
* Data Gear は 操作する Data Gear と
操作に必要な全ての Data Gear Gear が記述されている
* \_\_code で記述されているものが操作の Code Gear である

```
typedef struct Stack<Impl> {
    union Data* stack;
    union Data* data;
    __code next(...);
    __code whenEmpty(...);

    __code clear(Impl* stack, __code next(...));
    __code push(Impl* stack, union Data* data, __code next(...));
    __code pop(Impl* stack, __code next(union Data* ...));
    __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));

}
```
## Interface の実装の記述
* ソースコードは Interface の実装の初期化のコードである
* 操作の Code Gear には実装した Code Gear の番号が代入されるが、ここを入れ替えることで、複数の実装を持つことができる
```
Stack* createSingleLinkedStack(struct Context* context) {
    struct Stack* stack = new Stack();
    struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
    stack->stack = (union Data*)singleLinkedStack;
    singleLinkedStack->top = NULL;
    stack->push = C_pushSingleLinkedStack;
    stack->pop  = C_popSingleLinkedStack;
    stack->isEmpty = C_isEmptySingleLinkedStack;
    stack->clear = C_clearSingleLinkedStack;
    return stack;
}   
```
## xv6 の書き換えの方針
* xv6 を CbC で書き換え、Gears OS の機能と置き換えることで Gears OS に OS の基本構造を持たせたい
* このためには xv6 をモジュール化することで、xv6 の機能を明らかにする必要がある
* xv6 の Interface を定義し、Gears OS の機能をこれに合わせることによって実現したい

## CbC による FileSystem の書き換え

## まとめと今後の方針