# HG changeset patch # User anatofuz # Date 1588399282 -32400 # Node ID ea11eb7df53eb4963fa72ec5b73b66039df2037c # Parent 586757336bdd6a265dcb05ad78de5dfc936e09c0 update diff -r 586757336bdd -r ea11eb7df53e paper/Makefile --- a/paper/Makefile Sat May 02 14:39:45 2020 +0900 +++ b/paper/Makefile Sat May 02 15:01:22 2020 +0900 @@ -27,11 +27,11 @@ .dvi.pdf: $(DVIPDF) $(DVIPDF_OPT) $< -tex: $(TARGET).tex - all: $(TARGET).pdf open $(TARGET).pdf +tex: $(TARGET).tex + dvi: $(TARGET).dvi pdf: $(TARGET).pdf diff -r 586757336bdd -r ea11eb7df53e paper/anatofuz-sigos.md --- a/paper/anatofuz-sigos.md Sat May 02 14:39:45 2020 +0900 +++ b/paper/anatofuz-sigos.md Sat May 02 15:01:22 2020 +0900 @@ -37,21 +37,25 @@ またユーザー空間とカーネル空間が分離されており、 シェルやlsなどのユーザーコマンドも存在する。 本論文ではxv6のファイルシステム関連の内部処理と、システムコール実行時に実行される処理について分析を行う。 -xv6 kernelのファイルシステムは階層構造で表現されており、 最も低レベルなものにディスク階層、 抽象度が最も高いレベルのものにファイルディスクリプタがある。 +xv6 kernelのファイルシステムは階層構造で表現されており、 最も低レベルなものにディスク階層、 抽象度が最も高いレベルのものにファイル記述子がある。 # Continuation Based C Continuation Based C(CbC)とはC言語の下位言語であり、 関数呼び出しではなく継続を導入したプログラミング言語である。 -CbCでは通常の関数呼び出しの他に、 関数呼び出し時のスタックの操作を行わず、次のコードブロックにjmp命令で移動する継続が導入されている。 +CbCでは通常の関数呼び出しの他に、 関数呼び出し時のスタックの操作を行わず、次のコードブロックに`jmp`命令で移動する継続が導入されている。 この継続はSchemeなどの環境を持つ継続とは異なり、 スタックを持たず環境を保存しない継続である為に軽量である事から軽量継続と呼べる。 -またCbCではこの軽量継続を用いた再帰呼び出しを利用することで、 for文などのループ文を廃し関数型プログラミングに近いスタイルでプログラミングすることが可能である。 +またCbCではこの軽量継続を用いた再帰呼び出しを利用することで`for`文などのループ文を廃し、 関数型プログラミングに近いスタイルでプログラミングが可能となる。 現在CbCはGCC及びLLVM/clang上にそれぞれ実装されている。 +CbCでは関数の代わりにCodeGearという単位でプログラミングを行う。 +CodeGearは通常のCの関数宣言の返り値の型の代わりに`__code`で宣言を行う。 + CbCで階乗を求める例題をCode \ref{src:cbc_example}に示す。 -CbCでは関数の代わりにCodeGearという単位でプログラミングを行う。 -CodeGearはコード中では、型の代わりに`__code`で関数の様に宣言を行う。 +例題ではCodeGearとして`factorial`を宣言している。 +`factorial`はCodeGearの引数として`struct F`型の変数`arg`を受け取り、`arg`のメンバー変数によって`factorial`の再帰呼び出しを行う。 +CodeGearの呼び出しは`goto`文によって行われる。 ``` src:cbc_example, Cbで階乗を求める処理 @@ -69,6 +73,13 @@ } ``` +CodeGearは関数呼び出し時のスタックを持たない為、一度あるCodeGearに遷移してしまうと元の処理に戻ってくることができない。 +しかしCodeGearを呼び出す直前のスタックは保存されるため、 部分的にCbCを適用する場合はCodeGearを呼び出す`void`型などの関数を経由することで呼び出しが可能となる。 + +この他にCbCからCへ復帰する為のAPIとして、 環境付きgotoという機能がある。 +これはGCCでは内部コードを生成、 LLVM/clangでは`setjmp`と`longjmp`を使うことでCodeGearの次の継続対象として呼び出し元の関数を設定することが可能となる。 +したがってプログラマから見ると、通常のCの関数呼び出しの返り値をCodeGearから取得する事が可能となる。 + # xv6のファイルシステムの一部の分析 xv6のファイルシステムに関する定義ファイルはfs.c中に記述されている。 @@ -76,6 +87,6 @@ まず関数内でif文などの分岐を持たない基本単位であるBasic Blockに着目した。 CbCのCodeGearの粒度はCの関数とアセンブラの中間であるといえるので、 BasicBlockをCodeGearに置き換える事が可能である。 -したがって特定の関数内の処理のBasicBlockを分析し、 BasicBlockに対応したCodeGearに変換することで状態遷移系への変換を行った。 +したがって特定の関数内の処理のBasicBlockを分析し、 BasicBlockに対応したCodeGearへ変換することで状態遷移系への変換を行った。 diff -r 586757336bdd -r ea11eb7df53e paper/anatofuz-sigos.pdf Binary file paper/anatofuz-sigos.pdf has changed diff -r 586757336bdd -r ea11eb7df53e paper/anatofuz-sigos.tex --- a/paper/anatofuz-sigos.tex Sat May 02 14:39:45 2020 +0900 +++ b/paper/anatofuz-sigos.tex Sat May 02 15:01:22 2020 +0900 @@ -113,21 +113,25 @@ またユーザー空間とカーネル空間が分離されており、 シェルやlsなどのユーザーコマンドも存在する。 本論文ではxv6のファイルシステム関連の内部処理と、システムコール実行時に実行される処理について分析を行う。 -xv6 kernelのファイルシステムは階層構造で表現されており、 最も低レベルなものにディスク階層、 抽象度が最も高いレベルのものにファイルディスクリプタがある。 +xv6 kernelのファイルシステムは階層構造で表現されており、 最も低レベルなものにディスク階層、 抽象度が最も高いレベルのものにファイル記述子がある。 \section{Continuation Based C} Continuation Based C(CbC)とはC言語の下位言語であり、 関数呼び出しではなく継続を導入したプログラミング言語である。 -CbCでは通常の関数呼び出しの他に、 関数呼び出し時のスタックの操作を行わず、次のコードブロックにjmp命令で移動する継続が導入されている。 +CbCでは通常の関数呼び出しの他に、 関数呼び出し時のスタックの操作を行わず、次のコードブロックに\texttt{jmp}命令で移動する継続が導入されている。 この継続はSchemeなどの環境を持つ継続とは異なり、 スタックを持たず環境を保存しない継続である為に軽量である事から軽量継続と呼べる。 -またCbCではこの軽量継続を用いた再帰呼び出しを利用することで、 for文などのループ文を廃し関数型プログラミングに近いスタイルでプログラミングすることが可能である。 +またCbCではこの軽量継続を用いた再帰呼び出しを利用することで\texttt{for}文などのループ文を廃し、 関数型プログラミングに近いスタイルでプログラミングが可能となる。 現在CbCはGCC及びLLVM/clang上にそれぞれ実装されている。 +CbCでは関数の代わりにCodeGearという単位でプログラミングを行う。 +CodeGearは通常のCの関数宣言の返り値の型の代わりに\texttt{\_\_code}で宣言を行う。 + CbCで階乗を求める例題をCode \ref{src:cbc_example}に示す。 -CbCでは関数の代わりにCodeGearという単位でプログラミングを行う。 -CodeGearはコード中では、型の代わりに\texttt{\_\_code}で関数の様に宣言を行う。 +例題ではCodeGearとして\texttt{factorial}を宣言している。 +\texttt{factorial}はCodeGearの引数として`struct F`型の変数`arg`を受け取り、`arg`のメンバー変数によって`factorial`の再帰呼び出しを行う。 +CodeGearの呼び出しは\texttt{goto}文によって行われる。 \begin{lstlisting}[frame=lrbt,label=src:cbc_example,caption={Cbで階乗を求める処理}] @@ -145,6 +149,13 @@ } \end{lstlisting} +CodeGearは関数呼び出し時のスタックを持たない為、一度あるCodeGearに遷移してしまうと元の処理に戻ってくることができない。 +しかしCodeGearを呼び出す直前のスタックは保存されるため、 部分的にCbCを適用する場合はCodeGearを呼び出す\texttt{void}型などの関数を経由することで呼び出しが可能となる。 + +この他にCbCからCへ復帰する為のAPIとして、 環境付きgotoという機能がある。 +これはGCCでは内部コードを生成、 LLVM/clangでは\texttt{setjmp}と`longjmp`を使うことでCodeGearの次の継続対象として呼び出し元の関数を設定することが可能となる。 +したがってプログラマから見ると、通常のCの関数呼び出しの返り値をCodeGearから取得する事が可能となる。 + \section{xv6のファイルシステムの一部の分析} xv6のファイルシステムに関する定義ファイルはfs.c中に記述されている。 @@ -152,7 +163,7 @@ まず関数内でif文などの分岐を持たない基本単位であるBasic Blockに着目した。 CbCのCodeGearの粒度はCの関数とアセンブラの中間であるといえるので、 BasicBlockをCodeGearに置き換える事が可能である。 -したがって特定の関数内の処理のBasicBlockを分析し、 BasicBlockに対応したCodeGearに変換することで状態遷移系への変換を行った。 +したがって特定の関数内の処理のBasicBlockを分析し、 BasicBlockに対応したCodeGearへ変換することで状態遷移系への変換を行った。