平成29年度卒業論文 CbC 言語による OS 記述

琉球大学工学部情報工学科 135756F 宮城光希指導教員河野真治目次

第 1 章メタ計算の重要性 1

第 2 章 Continuation based C (CbC) 2 2.1 Continuation based C (CbC) . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Code Gear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.3 環境付き継続 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

第 3 章 Gears OS 6 3.1 Gears OS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 stub Code Gear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.4 interface の記述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

第 4 章 LLVM/clang による CbC の実装 8 4.1 LLVM clang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2 clang の基本構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.3 LLVM の基本構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.4 LLVM/clang のデバッグ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

第 5 章 Context、 stub Code Segment の自動生成 12 5.1 stub Code Segment の生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 Context の生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

第 6 章今後の課題 18

図目次

2.1 goto による code gear 間の継続 . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 code segment の軽量継続 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 階乗を求める CbC プログラムの軽量継続図 . . . . . . . . . . . . . . . . . 4 2.4 環境付き継続 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4.1 clang の処理過程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 LLVM の処理過程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

リスト目次

2.1 code segment の軽量継続 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 階乗を求める CbC プログラムの例 . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 環境付き継続 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.1 interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 createSingleLinkedStack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.1 LLVM IR コード修正前 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 LLVM IR コード修正後 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.1 SingleLinkedStack.cbc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 SingleLinkedStack.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.3 context の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.4 生成された context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

第1章メタ計算の重要性

プログラムを記述する際、通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等、記述しなければならない処理が存在する。これらの計算を Meta Computation と呼ぶ。

Meta Computation を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。

そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Gear、 Data Gear という単位を提案している。

Code Gear は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。 Code Gear、 Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、 Meta Data Gear が存在し、これらを用いて Meta Computation を実現する。

Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。

CbC は軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。

また、当研究室で開発している Gears OS は Code Gear、 Data Gear の単位を用いて開発されており、 CbC で記述されている。

本研究では CbC を用いての Gears OS の実装と CbC におけるユーザーの関知しない Meta Computation の自動生成を行なう。

第2章 Continuation based C (CbC)

2.1 Continuation based C (CbC)

CbC は処理を Code Gear とした単位を用いて記述するプログラミング言語である。 Code Gear は入力と出力を持ち、 CbC では引数が入出力となっている。 Code Gear から次の Code Gear へと goto による継続で遷移で処理を行い、引数として出力を与える。図 2.1 は Code Gear 間の処理の流れを表している。

図 2.1: goto による code gear 間の継続

2.2 Code Gear

Code Gear は CbC における最も基本的な処理単位である。リスト 2.1 は最も基本的な CbC のコードの一例で、図 2.2 はそれを図示したものである。 CbC では Code Gear は code という型を持つ関数の構文で定義される。ただし、これは code 型の戻り値を返すという意味ではなく、 Code Gear であることを示すフラグのようなものである。

Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。 goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する。リスト 2.1 の goto cs1(a+b); などがこれにたる。この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。 Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。したがってこれを軽量継続と呼ぶこともある。軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。

リスト 2.1: code segment の軽量継続

 1 __code cs0(int a, int b){
 2 goto cs1(a+b);
 3 }

4

 5 __code cs1(int c){
 6 goto cs2(c);
 7 }

図 2.2: code segment の軽量継続

もう少し複雑な CbC のプログラムの例が以下のリスト 2.2 である。これは与えられた数値の階乗を算出するプログラムである。このコードの factorial0 という Code Gear に注目すると、条件判別を行い、その結果に応じて自分自身への再帰的な継続を行うか別の Code Gear への継続を行うかという処理を行っていることがわかる。 CbC ではこのようにしてループ処理を制御する。

リスト 2.2: 階乗を求める CbC プログラムの例

 1 __code print_factorial(int prod)
 2 {
 3 printf("factorial␣=␣%d\n",prod);
 4 exit(0);
 5 }

6

 7 __code factorial0(int prod, int x)
 8 {
 9 if ( x >= 1) {
10  goto factorial0(prod*x, x-1);
11 }else{
12  goto print_factorial(prod);

13 }

14

15 }

16

17 __code factorial(int x)

18 {

19 goto factorial0(1, x);

20 }

21

22 int main(int argc, char **argv)

23 {

24 int i;
25 i = atoi(argv[1]);

26

27 goto factorial(i);

28 }

図 2.3: 階乗を求める CbC プログラムの軽量継続図

2.3 環境付き継続

環境付き継続は C との互換性のために必要な機能である。 CbC と C の記述を交える際、 CbC の Code Gear から C の関数の呼び出しは問題なく行える。しかし、 C の関数から CbC の Code Gear へと継続する場合、呼び出し元の環境に戻るための特殊な継続が必要となる。これを環境付き継続と呼ぶ。

環境付き継続を用いる場合、 C の関数から Code Gear へ継続する際に return、 environment という変数を渡す。 return は code (*)(return type, void*) 型の変数で環境付き継続先が元の環境に戻る際に利用する Code Gear を表す。 environment は void** 型の変数で元の関数の環境を表す。リスト 2.3 では関数 funcB から Code Gear cs に継続する際に環境付き継続を利用している。 cs は funcB から渡された Code Gear へ継続することで元の C の環境に復帰することが可能となる。但し復帰先は return を渡した関数が終了する位置である。このプログラムの例では、関数 funcA は戻り値として funcB の終わりにある -1 ではなく、環境付き継続によって渡される 1 を受け取る。図 2.4 にこの様子を表した。

リスト 2.3: 環境付き継続

   1 __code cs(__code (*ret)(int, void*), void *env){
   2 /* C0 */
   3 goto ret(1, env);
   4 }

5

   6 int funcB(){
   7 /* B0 */
   8 goto cs(__return, __environment);
   9 /* B1 (never reached). */
  10 return -1;

11 }

12

  13 int funcA(){
  14 /* A0 */
  15 int retval;
  16 retval = funcB();
  17 /* A1 */
  18 printf("retval␣=␣%d\n", retval);
  19 /* retval should not be -1 but be 1. */
  20 return 0;

21 }

図 2.4: 環境付き継続このように、環境付き継続を用いることで C、 CbC 間の処理の移動が可能になる。 5

第3章 Gears OS

3.1 Gears OS

Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、 Output Data Gear の組で表現する。 Data Gear はデータの単位であり、 int や文字列などの Primitive Type を持っている。 Code Gear は任意の数の Input Data Gear を参照して処理を行い、 Output Data Gear を出力し処理を終える。また、接続された Data Gear 以外には参照を行わない。 Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。処理やデータの構造が Code Gear、 Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。

Gears OS では Meta Computation を Meta Code Gear、 Meta Data Gear で表現する。 Meta Code Gear は通常の Code Gear の直後に遷移され、 Meta Computation を実行する。

CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、 Gears OS の Code Gear を記述するのに適している。

3.2 Context

Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、 TaskQueue へのポインタ、 Persistent Data Tree へのポインタ、 Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear である。 Gears OS は必要な Code/Data Gear に参照したい場合、この Context を通す必要がある。

3.3 stub Code Gear

Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。しかし、 Context を直接扱うのはセキュリティ上好ましくない。そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。 stub Code Gear は Code Gear が Code Gear へと継続する間に挟まれる。必要とする Data Gear を Context から取り出すという処理を行うものである。 stub Code Gear は Code Gear 毎に生成される。

3.4 interface の記述

interface を記述することで Context から Code Gear が呼び出せるようになった。 create は関数呼び出しで呼び出され、 interface と impliment の初期化と Code Gear のポインタの設定を行う。 return で interface を返し、その先で interface で指定した Code Gear へ継続できるようになった。

リスト 3.1: interface

1 typedef struct Stack<Impl>{
2  union Data* stack;
3  union Data* data;
4  union Data* data1;
5  __code whenEmpty(...);
6  __code clear(Impl* stack,__code next(...));
7  __code push(Impl* stack,union Data* data, __code next(...));
8  __code pop(Impl* stack, __code next(union Data*, ...));
9  __code pop2(Impl* stack, union Data** data, union Data** data1, __code
             next(union Data**, union Data**, ...));
10  __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));
11  __code get(Impl* stack, union Data** data, __code next(...));
12  __code get2(Impl* stack,..., __code next(...));
13  __code next(...);
14 } Stack;

リスト 3.2: createSingleLinkedStack

1 Stack* createSingleLinkedStack(struct Context* context) {
2  struct Stack* stack = new Stack();
3  struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
4  stack->stack = (union Data*)singleLinkedStack;
5  singleLinkedStack->top = NULL;
6  stack->push = C_pushSingleLinkedStack;
7  stack->pop = C_popSingleLinkedStack;
8  stack->pop2 = C_pop2SingleLinkedStack;
9  stack->get = C_getSingleLinkedStack;
10  stack->get2 = C_get2SingleLinkedStack;
11  stack->isEmpty = C_isEmptySingleLinkedStack;
12  stack->clear = C_clearSingleLinkedStack;
13  return stack;

14 }

第4章 LLVM/clang による CbC の 実装

4.1 LLVM clang

LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。 LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語に変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。

clang は LLVM をバックエンドとして利用する C/C++/Ob jective-C のコンパイラである。

4.2 clang の基本構造

clang は library-based architecture というコンセプトの元に設計されており、字句解析を行う liblex、構文解析を行う libparse といったように処理機構ごとに複数のライブラリに分割されている。 clang はこれらのライブラリを与えられた引数に応じて呼び出し、コンパイルを行う。さらに、必要な場合はリンカを呼び出してリンクを行い、ソースコードを実行可能な状態まで変換することも可能である。

ここで、そのライブラリの中でもコンパイルに関連するものについて説明する。

libast Abstract Syntax Tree (AST) や C の型等をクラスとして利用できるようにしたライブラリ。

liblex 字句解析ライブラリ、マクロの展開等の前処理系も担当する。

libparse 構文解析ライブラリ、解析結果を元に後述する libsema を使用して AST を生成する。

libsema 意味解析ライブラリ。 parser (libparse) に AST を生成する機能を提供する。 libcodegen

コード生成ライブラリ。生成された AST を LLVM IR に変換する。

clang ドライバ、各ライブラリを用いて求められた処理を行う。

これを踏まえて clang が C のコードを LLVM IR に変換する処理について説明する。 clang が C のコードを LLVM IR に変換する処理の過程を簡潔に図示したものである。以下の図 4.1 は clang が C のコードを LLVM IR に変換する処理の過程を簡潔に図示したものである。 clang は C のソースコードを受け取るとまずその解析を libparser による parser を用いて行い、 libsema を用いて解析結果から AST を構築する。そしてその AST を libcodegen を用いて LLVM IR に変換する。

図 4.1: clang の処理過程

4.3 LLVM の基本構造

LLVM は LLVM IR をターゲットのアセンブリ言語に直接的に変換を行うわけではない。 LLVM では、最適化や中間表現の変換を何段階か行う。この変換を行う処理は全て pass が行う。多くの pass は最適化のために存在し、そのなかから任意のものを利用することができる。 pass には以下のようなものがある。

SelectionDAG Instruction Selection (SelectionDAGISel)

LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し、最適化を行う。その後 Machine Code を生成する。

SSA-based Machine Code Optimizations SSA-based Machine Code に対する最適化を行う。各最適化はそれぞれ独立した pass になっている。

Register Allocation 仮装レジスタから物理レジスタへの割り当てを行う。ここで PHI 命令が削除され、 SSA-based でなくなる。

Prolog/Epilog Code Insertion Prolog/Epilog Code の挿入を行う、どちらも関数呼び出しに関わるものであり、 Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理、 Epilog は呼び出し元の関数に戻る際に行う処理である。 Late Machine Code Optimizations

Machine Code に対してさらに最適化を行う。

Code Emission Machine Code を MC Layer での表現に変換する。その後さらにターゲットのアセンブリ言語へ変換し、その出力を行う。

これらの処理の流れを図示したものが以下の図 4.2 である。前述した通りこれらの処理は全て pass によって行われる。 pass にはいくつかの種類があり、関数単位で処理を行うもの、ファイル単位で処理を行うもの、ループ単位で処理を行うもの等がある。

図 4.2: LLVM の処理過程

4.4 LLVM/clang のデバッグ

LLVM/clang で CbC をコンパイルした際 Code Gear 内の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。

局所変数でポインタを参照していると clang は生成する LLVM IR にオブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。

ここでリスト 4.2 のようにオブジェクトの lifetime の終わりを示す lifetime.end が tail call の後に書き出されてしまうことにより、 tail call の際に局所変数が解放されておらず lifetime が残っているので tail call が無視されてしまう。

しかし CbC では継続を行った後、継続前の Code Segment に戻ることはないので局所変数の解放は継続前に行っても良い。そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。

修正後に生成された LLVM IR コード (リスト 4.1) では tail call の直前に生成された。

リスト 4.1: LLVM IR コード修正前

   1 if.then: ; preds = %entry
   2 %code_stack = getelementptr inbounds %struct.Context, %struct.Context* %context
           , i64 0, i32 8
   3 %4 = load %struct.stack*, %struct.stack** %code_stack, align 8, !tbaa !7

 4 %next = getelementptr inbounds %struct.Context, %struct.Context* %context, i64
         0, i32 0
 5 %call1 = call i32 (%struct.stack*, i32*, ...) bitcast (i32 (...)* @stack_pop to
          i32 (%struct.stack*, i32*, ...)*)(%struct.stack* %4, i32* %next) #3
 6 %5 = load i32, i32* %next, align 8, !tbaa !11
 7 tail call fastcc void @meta(%struct.Context* nonnull %context, i32 %5) #3
 8 br label %cleanup

9

10 if.end: ; preds = %entry
11 %6 = load %struct.stack*, %struct.stack** %node_stack, align 8, !tbaa !24
12 %call4 = call i32 (%struct.stack*, %struct.Node**, ...) bitcast (i32 (...)*
         @stack_push to i32 (%struct.stack*, %struct.Node**, ...)*)(%struct.stack*
         %6, %struct.Node** nonnull %parent) #3
13 tail call fastcc void @meta(%struct.Context* nonnull %context, i32 18) #3
14 br label %cleanup

15

16 cleanup: ; preds = %if.end, %if.then
17 call void @llvm.lifetime.end(i64 8, i8* %0) #3
18 ret void

リスト 4.2: LLVM IR コード修正後

 1 if.then: ; preds = %entry
 2 %code_stack = getelementptr inbounds %struct.Context, %struct.Context* %context
         , i64 0, i32 8
 3 %4 = load %struct.stack*, %struct.stack** %code_stack, align 8, !tbaa !7
 4 %next = getelementptr inbounds %struct.Context, %struct.Context* %context, i64
         0, i32 0
 5 %call1 = call i32 (%struct.stack*, i32*, ...) bitcast (i32 (...)* @stack_pop to
          i32 (%struct.stack*, i32*, ...)*) (%struct.stack* %4, i32* %next) #3
 6 %5 = load i32, i32* %next, align 8, !tbaa !11
 7 call void @llvm.lifetime.end(i64 8, i8* %0) #3
 8 tail call fastcc void @meta(%struct.Context* nonnull %context, i32 %5) #3
 9 br label %cleanup

10

11 if.end: ; preds = %entry
12 %6 = load %struct.stack*, %struct.stack** %node_stack, align 8, !tbaa !24
13 %call4 = call i32 (%struct.stack*, %struct.Node**, ...) bitcast (i32 (...)*
         @stack_push to i32 (%struct.stack*, % struct.Node**, ...)*)(%struct.stack*
         %6, %struct.Node** nonnull %parent) #3
14 call void @llvm.lifetime.end(i64 8, i8* %0) #3
15 tail call fastcc void @meta(%struct.Context* nonnull %context, i32 18) #3
16 br label %cleanup

17

18 cleanup: ; preds = %if.end, %if.then
19 ret void

第5章 Context、 stub Code Segment の自動生成

Gears OS では 3 章で述べたように通常の Computation の他に Context や stub などの Meta Computation を記述する必要がある。 Gears OS を現在の CbC の機能のみを用いて記述すると Context や stub Code Gear の記述を行わなくてはならず、これには多くの労力を要する。そのため、この記述を助けるために Context や stub Code Gear を生成するスクリプトを作成した。

5.1 stub Code Segment の生成

stub Code Gear は Code Gear 間の継続に挟まれる Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。 stub Code Gear は Code Gear 毎に記述する必要があり、その Code Gear の引数を見て取り出す Data Gear を選択する。 stub Code Gear を自動生成することによって Code Gear の記述量を約半分にすることができる。

stub を生成するために perl スクリプトは指定された cbc ファイルの code 型である Code Gear を取得し、引数から必要な Data Gear を選択する。この時既に stub Code Gear が生成されている Code Gear は無視される。

cbc ファイル (リスト 5.1) に生成した stub Code Gear を c ファイル (5.2) を出力する。

リスト 5.1: SingleLinkedStack.cbc

 1 #include "../context.h"

2

 3 Stack* createSingleLinkedStack(struct Context* context) {
 4  struct Stack* stack = new Stack();
 5  struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
 6  stack->stack = (union Data*)singleLinkedStack;
 7  singleLinkedStack->top = NULL;
 8  stack->push = C_pushSingleLinkedStack;
 9  stack->pop = C_popSingleLinkedStack;
10  stack->get = C_getSingleLinkedStack;
11  stack->isEmpty = C_isEmptySingleLinkedStack;
12  stack->clear = C_clearSingleLinkedStack;
13  return stack;

14 }

15

16 __code clearSingleLinkedStack(struct SingleLinkedStack* stack,__code next(...)) {
17  stack->top = NULL;
18  goto next(...);

19 }

20

21 __code pushSingleLinkedStack(struct SingleLinkedStack* stack,union Data* data,
       __code next(...)) {
22  Element* element = new Element();
23  element->next = stack->top;
24  element->data = data;
25  stack->top = element;
26  goto next(...);

27 }

28

29 __code popSingleLinkedStack(struct SingleLinkedStack* stack, __code next(union
       Data* data, ...)) {
30  if (stack->top) {
31  data = stack->top->data;
32  stack->top = stack->top->next;
33  } else {
34  data = NULL;

35  }

36  goto next(data, ...);

37 }

38

39 __code getSingleLinkedStack(struct SingleLinkedStack* stack, __code next(union
       Data* data, ...)) {
40  if (stack->top)
41  data = stack->top->data;
42  else
43  data = NULL;
44  goto next(data, ...);

45 }

46

47 __code isEmptySingleLinkedStack(struct SingleLinkedStack* stack, __code next(...)
       , __code whenEmpty(...)) {
48  if (stack->top)
49  goto next(...);
50  else
51  goto whenEmpty(...);

52 }

リスト 5.2: SingleLinkedStack.c

 1 #include "../context.h"

2

 3 Stack* createSingleLinkedStack(struct Context* context) {
 4  struct Stack* stack = &ALLOCATE(context, Stack)->Stack;
 5  struct SingleLinkedStack* singleLinkedStack = &ALLOCATE(context,
          SingleLinkedStack)->SingleLinkedStack;
 6  stack->stack = (union Data*)singleLinkedStack;
 7  singleLinkedStack->top = NULL;
 8  stack->push = C_pushSingleLinkedStack;
 9  stack->pop = C_popSingleLinkedStack;
10  stack->pop2 = C_pop2SingleLinkedStack;
11  stack->get = C_getSingleLinkedStack;
12  stack->get2 = C_get2SingleLinkedStack;
13  stack->isEmpty = C_isEmptySingleLinkedStack;
14  stack->clear = C_clearSingleLinkedStack;
15  return stack;

16 }

17

18 __code clearSingleLinkedStack(struct Context *context,struct SingleLinkedStack*
       stack,enum Code next) {
19  stack->top = NULL;
20  goto meta(context, next);

21 }

22

23 __code clearSingleLinkedStack_stub(struct Context* context) {
24  SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack

          );
25  enum Code next = Gearef(context, Stack)->next;
26  goto clearSingleLinkedStack(context, stack, next);

27 }

28

29 __code pushSingleLinkedStack(struct Context *context,struct SingleLinkedStack*
       stack,union Data* data, enum Code next) {
30  Element* element = &ALLOCATE(context, Element)->Element;
31  element->next = stack->top;
32  element->data = data;
33  stack->top = element;
34  goto meta(context, next);

35 }

36

37 __code pushSingleLinkedStack_stub(struct Context* context) {
38  SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack
          );
39  Data* data = Gearef(context, Stack)->data;
40  enum Code next = Gearef(context, Stack)->next;
41  goto pushSingleLinkedStack(context, stack, data, next);

42 }

43

44 __code popSingleLinkedStack(struct Context *context,struct SingleLinkedStack*
       stack, enum Code next,union Data **O_data) {
45  Data* data;
46  if (stack->top) {
47  data = stack->top->data;
48  stack->top = stack->top->next;
49  } else {
50  data = NULL;

51  }

52  *O_data = data;
53  goto meta(context, next);

54 }

55

56 __code popSingleLinkedStack_stub(struct Context* context) {
57  SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack
          );
58  enum Code next = Gearef(context, Stack)->next;
59  Data** O_data = &Gearef(context, Stack)->data;
60  goto popSingleLinkedStack(context, stack, next, O_data);

61 }

62

63 __code getSingleLinkedStack(struct Context *context,struct SingleLinkedStack*
       stack, enum Code next,union Data **O_data) {
64  Data* data;
65  if (stack->top)
66  data = stack->top->data;
67  else
68  data = NULL;
69  *O_data = data;
70  goto meta(context, next);

71 }

72

73 __code getSingleLinkedStack_stub(struct Context* context) {
74  SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack
          );
75  enum Code next = Gearef(context, Stack)->next;
76  Data** O_data = &Gearef(context, Stack)->data;
77  goto getSingleLinkedStack(context, stack, next, O_data);

78 }

79

80 __code isEmptySingleLinkedStack(struct Context *context,struct SingleLinkedStack*
        stack, enum Code next, enum Code whenEmpty) {
81  if (stack->top)
82  goto meta(context, next);

83  else
84  goto meta(context, whenEmpty);

85 }

86 87

88 __code isEmptySingleLinkedStack_stub(struct Context* context) {
89  SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack
          );
90  enum Code next = Gearef(context, Stack)->next;
91  enum Code whenEmpty = Gearef(context, Stack)->whenEmpty;
92  goto isEmptySingleLinkedStack(context, stack, next, whenEmpty);

93 }

5.2 Context の生成

Context は Meta Data Gear に相当し、 Code Gear や Data Gear を管理している。 Data Gear を取得するために perl スクリプトは context の定義 (リスト 5.3) を読み宣言された Data Gear を取得する。 Code Gear は指定された cbc ファイルから stub を見て取得を行う。

Context では Code Gear の名前とポインタの対応は生成する enum Code によって表現される。実際に Code Gear に接続する際は enum Code を指定することで接続を行う。取得した Code/Data Gear の enum の定義は enumCode.h、 enumData.h に生成される。取得した Code/Data Gear から Context の生成を行うコード (リスト 5.4) を生成する。

Context には Allocation 等で生成した Data Gear へのポインタが格納されている。 Code Gear は Context を通して Data Gear へアクセスする。 Data Gear の Allocation を行うコードは dataGearInit.c に生成される。

Data Gear は union Data とその中の struct によって表現される。 Context には Data Gear の Data Type の情報が格納されている。この情報から確保される Data Gear のサイズなどを決定する。

リスト 5.3: context の定義

 1 #define ALLOCATE_SIZE 20000000
 2 #define NEW(type) (type*)(calloc(1, sizeof(type)))
 3 #define NEWN(n, type) (type*)(calloc(n, sizeof(type)))

4

 5 #define ALLOC_DATA(context, dseg) ({\
 6  struct Meta* meta = (struct Meta*)context->heap;\
 7  meta->type = D_##dseg;\
 8  meta->size = 1;\
 9  context->heap += sizeof(struct Meta);\
10  context->data[D_##dseg] = context->heap; context->heap += sizeof(struct dseg)
          ; (struct dseg *)context->data[D_##dseg]; })

11

12 #define ALLOCATE(context, t) ({ \
13  struct Meta* meta = (struct Meta*)context->heap;\
14  context->heap += sizeof(struct Meta);\
15  union Data* data = context->heap; \
16  context->heap += sizeof(struct t); \
17  meta->type = D_##t; \
18  meta->size = 1; \
19  data; })

21 #define Gearef(context, t) (&(context)->data[D_##t]->t)
22 #define GearImpl(context, intf, name) (Gearef(context, intf)->name->intf.name)

23

24 #include "c/enumCode.h"

25

26 #include "c/enumData.h"

27

28 struct Context {
29  enum Code next;
30  struct Worker* worker;
31  struct TaskManager* taskManager;
32  int codeNum;
33  __code (**code) (struct Context*);
34  void* heapStart;
35  void* heap;
36  long heapLimit;
37  int dataNum;
38  int idgCount; //number of waiting dataGear
39  int odg;
40  int maxOdg;
41  int workerId;
42  union Data **data;
43 };

44

45 union Data {
46  struct Meta {
47  enum DataType type;
48  long size;
49  struct Queue* wait; // tasks waiting this dataGear
50  } meta;
51  struct Task {
52  enum Code code;
53  struct Queue* dataGears;
54  int idsCount;
55  } Task;
56  // Stack Interface
57  struct Stack {
58  union Data* stack;
59  union Data* data;
60  union Data* data1;
61  enum Code whenEmpty;
62  enum Code clear;
63  enum Code push;
64  enum Code pop;
65  enum Code isEmpty;
66  enum Code get;
67  enum Code next;
68  } Stack;
69  // Stack implementations
70  struct SingleLinkedStack {
71  struct Element* top;
72  } SingleLinkedStack;
73  struct Element {
74  union Data* data;
75  struct Element* next;
76  } Element;
77  struct Node {
78  int key; // comparable data segment
79  union Data* value;
80  struct Node* left;
81  struct Node* right;
82  // need to balancing
83  enum Color {
84  Red,
85  Black,

86  } color;
87  } Node;
88 }; // union Data end this is necessary for context generator

リスト 5.4: 生成された context

1

 2 #include <stdlib.h>

3

 4 #include "../context.h"

5

 6 void initContext(struct Context* context) {
 7  context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
 8  context->code = (__code(**) (struct Context*)) NEWN(ALLOCATE_SIZE, void*);
 9  context->data = NEWN(ALLOCATE_SIZE, union Data*);
10  context->heapStart = NEWN(context->heapLimit, char);
11  context->heap = context->heapStart;

12

13  context->code[C_clearSingleLinkedStack] = clearSingleLinkedStack_stub;
14  context->code[C_exit_code] = exit_code_stub;
15  context->code[C_getSingleLinkedStack] = getSingleLinkedStack_stub;
16  context->code[C_isEmptySingleLinkedStack] = isEmptySingleLinkedStack_stub;
17  context->code[C_popSingleLinkedStack] = popSingleLinkedStack_stub;
18  context->code[C_pushSingleLinkedStack] = pushSingleLinkedStack_stub;
19  context->code[C_stack_test1] = stack_test1_stub;
20  context->code[C_stack_test2] = stack_test2_stub;
21  context->code[C_stack_test3] = stack_test3_stub;
22  context->code[C_stack_test4] = stack_test4_stub;
23  context->code[C_start_code] = start_code_stub;

24

25 #include "dataGearInit.c"

26

27 }

28

29 __code meta(struct Context* context, enum Code next) {
30  // printf("meta %d\n",next);
31  goto (context->code[next])(context);

32 }

33

34 __code start_code(struct Context* context) {
35  goto meta(context, context->next);

36 }

37

38 __code start_code_stub(struct Context* context) {
39  goto start_code(context);

40 }

41

42 __code exit_code(struct Context* context) {
43  free(context->code);
44  free(context->data);
45  free(context->heapStart);
46  goto exit(0);

47 }

48

49 __code exit_code_stub(struct Context* context) {
50  goto exit_code(context);

51 }

52

53 // end context_c

第6章今後の課題^{本研究では}

18

参考文献

19

謝辞