fishを捌く(後編)_backgroundの処理の実装
はじめに
これは、東京大学電気電子・電気情報工学科の3年次の実験、「大規模ソフトウェアを手探る」実験においてfish_shellのソースコードを手探り、機能の追加を行ったものです。
今回は、並列for文の機能を追加しました。
(前編)で、ソースコードをダウンロードし、ビルドをおこない、デバッグをして、手探り、並列for文(pfor)を(for文と全く同じ挙動ですが)シェルの関数として呼び出すことができるようになりました。前編は以下から
やったこと
並列に処理させるためには、for文での実行の際、一つの処理が終わるまで、残りの(繰り返しを含む)すべての処理をOSに待ってもらっているので、そこで待たないようにする必要がありました。以下のような処理の時に、backgroundで行うと、並列に実行されることから、バックグラウンド処理を使うことで、待たせないことができることがわかりました。
・backgroundで実行されるsleep
よって、for文の処理をbackgroundにするということを目指してやっていきます。
fish-shellを手探る
基本的には、&というbackgroundjobを指示するコマンドを書いた時をデバッグしていきました。(具体的にはsleep infinity &)
fishがjobをbackgroundで行われるものだと決めている場所
parse_execution.cppの中に、
job->set_flag(JOB_FOREGROUND, !tree.job_should_be_backgrounded(job_node));
という文があり、実行しようとしているjobののノードのflagという変数を書き換えている。
job_should_be_backgroundという関数の中身は以下のようになっている。
get_child(job,2,symbol_optional_background)は引数のノード(parse_node_t &job)から見て、順番として二番目の子ノードでかつ、そのノードのtypeという変数がsymbol_optional_backgroundであるもののノードのアドレスをとってきます。
イメージ↓
opt_background(上の図で2の番号のついたノード)のtagがparse_backgroundであれば、
trueを返すようになっている。その後set_flagでflagもbackgroundのものに帰られていたので、tagをparse_backgroundに書き換えればいいのではないかとわかりました。
type = symbol_jobのノードの子ノードの２番目がsymbol_optional_backgroundであることもわかります。
構文木についてもう少し詳しく書いた部分があるので、読みたい人はこちらをクリックしてください。(このページの下部にあります。)
pfor_statementに渡されているnodeからsymbol_optional_backgroundのnodeにたどり着く
前編で出てきた(p)for_statementの引数は以下のようにsymbol_job_listです。
type=symbol_job_listのノードからtype=symbol_jobのノードを取ってくる関数が、parse_tree.cppの中にあったのでこれを用いることにする。
参考用のコード↓
これを用いて、type = symbol_jobのノードを取り出し、job_should_be_background
関数のようにget_childでtype=symbol_optional_backgroundのノードのアドレスを手に入れて、そのtagをparse_backgroundに変えればよいと方針がたった。
実装と結果
以上のことを踏まえて、実装をしたのが↓のコードである。
const_cast<parse_node_t*>はノードがread_onlyだったので、constを外してtagをかきかえるために使いました。
実際に動かしてみると次のようになり、jobが並列に動いていることがわかりました。
しかし、この実装では、pforのブロックの中身も並列に実行されてしまっているようで、本質的な実装ができていないと思われます。
これを解決するためには、blockごとに中のjobidに対して、同じブロックの前の処理が終わるまでは処理をしないように待たせる必要があります。
pipeなどの機能を用いてデバッグをすれば解決の手がかりを得られると思うので、今後の課題としたいと思います。
補足：構文木の構造を探る
構文木の構造が把握できれば、何をしているのかわかるだろうということでやってみました。ここについては、自分でもっと手探りたい人の助けになるようにと、書いたものです。興味のない人は飛ばしてもらって構わないかと思います。
ここで説明するのはfor文の構造です。
1.木の全体像とパターン
はじめにまとめた図を載せます。
ひとつひとつの四角がノードです。ノードの左肩の数字はノードに付与された番号です。ノードの中の文字は、先ほど出てきたノードのもつ変数typeです。(前編)でも出てきたsymbol_for_headerなどもここにあります。大きな流れとしては、次の図のようになっています。
symbol_job_listから少しずつjobが取り出されていく感じですね。また、
symbol_jobの子ノードの二番目は必ずsymbol_optional_backgroundであることもわかりました。
2.ノードの中身
例として上の全体図の番号３のノードを見て見ます。
{source_start = 0, source_length = 32, parent = 1, child_start = 6,
child_count = 1 '\001', type = symbol_statement,
keyword = parse_keyword_none, flags = 0 '\000', tag = 0 '\000'}
source_start・・・ソースコードのどこから始まっているか。０は１文字目のこと。
source_length・・・該当する部分の長さ
parent・・・親ノードのノード番号
child_start・・・子ノードの最も若いノード番号
child_count・・・子ノードの個数
type・・・その部分の型のようなもの、symbol_xxx、parse_xxxと書かれている(parse_xxxは葉に存在する。)
keyword・・・これは、構文解析時にtagを変更したりするのに用いる。
falgs,tag・・・tagによってflagが書き換えられる仕組み
以上で木の説明は終わります。
fish shellを捌く(前編)_pfor文の仮実装まで
これは、東京大学電気電子・電気情報工学科の3年次の実験、「大規模ソフトウェアを手探る」実験においてfish_shellのソースコードを手探り、機能の追加を行ったものです。
目的
通常のfor文で並列処理を行うためには
for i in (seq 10)
echo $i &
end
というように&をつけて実行する必要がありますが、それを省略し、
pfor i in (seq 10)
echo $i
end
とするだけで並列処理を実行できるようにしたいというのが目的です。
環境はubuntuを用いています。
インストール&ビルド
まずはfish-2.7.1-1~artful(Bionic)をfish_2.7.1.orig.tar.gzの形で公式サイトhttps://fishshell.com/からダウンロードします。
その後、適当なフォルダにダウンロードを入れ、ターミナルでそのフォルダに移動します。別にfishのバイナリをインストールするためのフォルダも作っておくと良いでしょう。
この状態で、
tar xfv fish_2.7.1.orig.tar.gz
cd fish-2.7.1/
env CXXFLAGS = “-O0 -g” ./configure --prefix=(インストール先のフォルダのフルパス)
make
make install
とすることでfishがインストールされます。
注意1 --prefixの引数では/から始まるフルパスを記述する必要があります。(例)/home/deno/fish_install
中身を覗くためのツール
使用するツールとしては２つ。linuxに標準で備わっているgrepコマンドとgdbデバッガです。
grepコマンドでは、find -print | xargs grep -n "(探したい文字列)" とすることで特定
の文字列を含んだファイルの行とその位置を表示することができます。
また-vオプションで条件を満たすものを除外して表示するなど非常に便利なコマンドです。
gdbデバッガはオーソドックスなデバッガで、プログラムのステップ実行など一通りのデバッグを行うことができます。
この２つを併用しながらソースコードの中身に切り込んでいくことにしました。
for文の処理を発見するまで
まず最初にforと言うワードをgrepしつつ、for (int i=)などの言語仕様による文章を除外して検索していったところ、L"for"という怪しいワードが散見されます。
これをgrepで調べたところ、ファイルbuiltin.cppのビルトイン関数のforを実行している部分に行き着きました。最初はこれがfor文を実行している部分だと考えましたが、デバッグではその部分を通らず、調べてみたところforと単体で打ち込まれた場合にヘルプを表示するだけの関数だとわかりました。
この部分を弄って新しいビルトイン関数を実装するのも面白そうではあったのですが、仮題とは無関係なので今は割愛します。
一旦仕切りなおし、探索の際出てきたfor文と関係のありそうなワード "parse_keyword_for","symbol_for_header"などのgrep及びgdbによる執念のデバッグの結果、ファイルparse_execution.cpp内にfor文が実際に動いていると思わしき関数run_for_statementを発見しました。
この関数に内在するfor文にブレークポイントを当ててfor文を実行したところ、確かにこの中でループを実行していることがわかりました。
また、処理を追っていくことで実際に命令を実行している関数も発見しました。
pfor文の仮実装まで
run_for_statementの呼び出し元を調べ、この関数が呼び出される条件を探ったところ、symbol_for_headerが条件になっているのが確認できました。
これは処理のブロックを識別するのに使用されていると推測できます。
また、命令のパース部分ではparse_keyword_forが使用されており、こちらは単語としてのforを識別するのに使用されていると推測されます。
これら２つを結びつけている部分がマクロで定義されていたこと、
またparse_keyword_forとL"for"を結びつける場所が見つかっていたことからfor文を識別する要素をこの２つだと判断し、これら２つに対応するsymbol_pfor_header,parse_keyword_pforを挿入(ただし、実際に呼び出される関数はfor文と同じまま)したところ、for文の代わりにpforを使用しても動作するようになりました。
実際の変更点まとめ
・parse_keyword_pforに同じ処理をfor->pforとだけ変えて追加
/parse_productions.cpp:151: case parse_keyword_for:
./parse_productions.cpp:295: case parse_keyword_for: {
./parse_productions.cpp:311:RESOLVE_ONLY(for_header, KEYWORD(parse_keyword_for), parse_token_type_string,
./parse_constants.h:128: parse_keyword_for,
./parse_constants.h:143: {parse_keyword_for, L"for"}, {parse_keyword_function, L"function"},
・symbol_for_headerに同じ処理をfor->pforとだけ変えて追加
./parse_constants.h:25: symbol_for_header,
./parse_constants.h:96: {symbol_for_header, L"symbol_for_header"},
./parse_util.cpp:1244: case symbol_for_header: {
./highlight.cpp:1071: case symbol_for_header: {
./parse_execution.cpp:416: case symbol_for_header: {
./parse_execution.cpp:446: assert(header.type == symbol_for_header);
./parse_tree.cpp:170: case symbol_for_header: {
./parse_productions.cpp:289: P(forh, symbol_for_header);
・その他をfor->pforと変えて追加
./parse_tree.cpp:171: return L"for loop";
./parse_productions.cpp:296: return forh;
./parse_productions.cpp:465: TEST(for_header)
注意
./parse_constants.h:128: parse_keyword_for,
./parse_constants.h:143: {parse_keyword_for, L"for"}, {parse_keyword_function, L"function"}
./parse_constants.h:96: {symbol_for_header, L"symbol_for_header"},
この部分に追加する場合、変数の順序がアルファベット順になるようにしなければなりません。
処理部分としてはrun_pfor_statementという関数を作ってrun_block_statement()からrun_for_statementの代わりに呼び出させるといいでしょう。今のところは関数の内容は全くのコピーで問題ありません。
makeから再実行しインストール先のフォルダでfishを実行してみて、このようにできれば成功です。
後編では、実際に並列処理を実行していきます。
