シェル再実装の課題「minishell」振り返り
先日42Tokyoの課題のひとつで、bashの再実装を行う「minishell」という課題を終えました。
実装の詳細はすでに先輩方が執筆されているブログがあるのでそちらを確認していただくとして（嘘です、書くのが面倒になっただけです）、minishellを通して学んだこと、便利ツールや参考にしたサイトなどをまとめます。今後minishellに取り組む方の参考になれば幸いです。
minishellとは
minishellはその名前の通りbashの一部の機能をC言語で再実装する課題です。
最低限実装するべき機能は以下の通り。
- プロンプトを表示
- readlineライブラリを使って実装
- コマンドの実行
- クォート（
'、"） - パイプライン（
|） - リダイレクト（
<、>、<<、>>） - 環境変数の展開（
$） - 終了ステータスの展開（
$?） - シグナルの扱い（
Ctrl-C、Ctrl-D、Ctrl-\） - ビルトインコマンド（
echo、cd、pwd、export、unset、env、exit）
42でチームで取り組む最初の課題であり、2人1組で取り組むことになります。難易度が少し高めで、大きな関門となる課題です。
この課題を終えることができれば42生として一人前くらいのスキルが身についたと言えるのではないかと思います。
シェルの構成
今回作成したminishellの構成はおおよそ以下のようなコンポーネントに分かれています。
私がニートなのに対して、チームメイトは大学生で期末試験と就活があったので、私の実装量が多めになっています。
| 機能 | 概要 | 担当 |
|---|---|---|
| 環境変数 | ハッシュマップを用いて環境変数を管理する | 私 |
| 入力処理 | readlineを用いてユーザーからの入力を受け取る | 私 |
| トークナイザ | 入力をトークンに分割する | 私 |
| パーサ | トークンを解析して構文木を生成する | 私 |
| 展開 | クォートや環境変数の展開を行う | 私 |
| ヒアドキュメント | ヒアドキュメントを処理する | 私 |
| 実行 | パイプラインやリダイレクトを処理してコマンドを実行する | 私 |
| シグナル | シグナルを処理する | チームメイト |
| ビルトイン | ビルトインコマンドを実装する | チームメイト |
まずはじめに簡単なプロトタイプとテストケースを作成し、設計の見直しを行った上で提出用のコードを書きました。これは、シェルの機能が複雑であるため、最初から完璧な設計を立てることは難しいと考えたためです。
実装においてはインクリメンタルな開発を心がけました。常に動く状態を保ちながら機能を追加していくことで、簡単に開発を進めることができたと思います。
また、テストケースはおおよそ300ケースほど作成し、コーナーケースを含めて網羅的にテストを行いました。実際、機能の追加やリファクタリングによってバグを引き起こすことがあり、テストケースが役立ちました。1
実装の詳細は、42の先輩方が執筆されたブログが多数あるのでそちらを参照してください。私は以下のnafukaさんとjunさんのブログを参考にしました。（あとで気が向いたら自分の実装の詳細を書きます）
参考にしたサイト・書籍
bashのマニュアル
すべてが書いてあるので、課題に取り組む前に一度ざっくりと目を通すことをおすすめします。
The Arecitecture of Open Source Applications / Bash
bashのアーキテクチャについて詳しく解説されています。この記事を参考にしておおよそのデータ構造を作成しました。日本語訳も存在します。
低レイヤを知りたい人のためのCコンパイラ作成入門
コンパイラの作り方について解説されているサイト。Step1~5を読むことで字句解析・構文解析についての理解を深めることができると思います。
ふつうのLinuxプログラミング 第2版
Linuxでシステムプログラミングをする際の入門的な書籍。Linuxの基本的な概念・システムコール・ライブラリ関数の解説と簡単なUnixコマンドを実装する例が掲載されています。
Linuxシステムプログラミングインタフェース
Linuxを構成する要素と、システムコール、ライブラリ関数などが詳しく解説されています。
1600ページほどありすべてを読むのは難しいため、リファレンス的に参照するのが良いと思いますが、minishellで使用するシステムコールやライブラリ関数を解説している箇所については目を通すことをおすすめします。
第1章-3章（Linux/Unixの歴史と基本的な概念）、第4・5章（ファイルI/O）、第6章（プロセス）、第7章（メモリ割り当て）、第20-22章（シグナル）、第24章-28章（プロセスの作成・終了・子プロセスの監視・プログラムの実行）が特に参考になりました。2
上記にあげた2冊の書籍はminishellに限らず42Tokyoの課題全般において非常に参考になると思いますので、ぜひ読んでみてください。
入門bash
リンク先は第3版ですが、第2版の付録としてbashのBNFが掲載されています。minishellのパーサを実装する際に参考にしました。
参考にしたリポジトリ
bash
bashの再実装をやるので当然これを参照することになりますが、古のK&RスタイルのC言語で実装されているため少々読みにくいと感じます。そもそもコードベースが巨大でありマクロ等も入り組んでいるため根気が必要ですが、copilot等のツールを使いつつ少しずつ読んでいくことで理解が深まります。GitHubに非公式のミラーが存在します。
fish
fishは最近Rustで書き直されたシェルで、bash本家よりも読みやすいのでたびたび参考にしました。Rustがわからない場合でもある程度の処理の流れは理解できると思います。ところどころbashとは異なる仕様になっているので注意が必要です。
xv6のシェル
xv6に実装されているシェルは高度な機能が実装されていない代わりにシンプルな構造になっているため、シェルの基本的な機能を理解するには最適だと思います。
minishellのひとつ前の課題であるpipexの実装にも参考にしました。
Tips
minishellを実装する際に役立ったツールやデバッグ方法について紹介します。
true・false
trueコマンドは常に0を返すコマンドで、falseコマンドは常に1を返すコマンドです。終了ステータスを確認する際に便利です。
$ true$ echo $?0$ false$ echo $?1/proc/self/fd
/proc/self/fdを見ることでプロセスが開いているファイルディスクリプタの内容を確認することができます。
リダイレクトやパイプライン、ヒアドキュメントの実装ではよくファイルディスクリプタに関わるバグを引くことがあるので便利です。
$ ls -l /proc/self/fdpstree
pstreeコマンドを使うことでプロセスの親子関係を確認することができます。
minishellとbashのプロセスの親子関係を確認することで、minishellの実装が正しいかどうかを確認することができます。
pidはプロセスIDを指定します。getpid()関数で取得することができるので、デバッグ用途でminishellを起動した際に表示できるようにしておくといいでしょう。
$ pstree [pid]strace
straceコマンドは、プロセスが使用するシステムコールとシグナルをトレースするためのツールです。
minishell本体が意図していない挙動をしている場合にシステムコールの引数や返り値を確認することで問題の絞り込みをするなど、デバッグに役立てることができます。printfをソースコードに埋め込む必要がないほか、gdbなどのデバッガを使用するよりも比較的簡単に使うことができます。
デバッグのみならず、bashなどの調査したいソフトウェアをトレースすることで、おおよその処理の流れやシステムコールの使い方を把握することができます。実際にbashのソースコードは巨大であり、いちから実装を確認していくのが難しかったため、straceを用いて概要を把握したり、コードを読む前に挙動を確認しすることであたりをつけたりすることができました。
$ strace ./minishell便利なオプションとしては以下のものがあります。
-f:forkした子プロセスもトレースする-e: トレースするシステムコールを指定する-o: 出力先を指定する
詳細についてはman straceや以下のサイトを参照してください。
callgrind・kcachegrind
callgrindはValgrindのツールの一つで、プログラムの実行時の関数呼び出しの回数や時間を計測することができます。
bashのような巨大なプログラムを読む際にどの関数がどのように呼ばれているかを把握し、処理の流れを追うために使用しました。
valgrind --tool=callgrind bashcallgrindの出力結果はcallgrind.out.[pid]というファイルに保存されます。kcachegrindを使うことで、ビジュアライズされた結果を見ることができます。
kcachegrind callgrind.out.[pid]
bashをcallgrindでトレースし、kcachegrindで可視化している様子
valgrind
valgrindは動的解析によりメモリリークなどを検出するツールです。
課題のルールではメモリリークをおこなさないことが求められているため、valgrindを使ってメモリリークがないかを確認します。
valgrind --leak-check=full ./minishellオプションとしては以下のものがあります。
--leak-check=full: メモリリークを検出する--show-leak-kinds=all: すべてのメモリリークを表示する--trace-children=yes: 子プロセスもトレースする--track-fds=yes: ファイルディスクリプタをトレースする
minishellではreadlineライブラリを使用している関係上、valgrindがreadlineの内部でメモリリークを検出することがあります。これを抑制するため以下のようなサプレッションファイルを作成し、オプションとして--suppressions=[ファイル名]を指定します。
{ ignore_readline_leaks Memcheck:Leak ... obj:*/libreadline.so.*}clang sanitizer
clangにはメモリリークや未定義動作などを検出するためのサニタイザが搭載されています。
今回はメモリ領域外アクセスやuse-after-free、メモリリークなどを検出するAddressSanitizerと、符号付き整数のオーバーフローなど未定義動作を検出するUndefinedBehaviorSanitizerを使用しました。
valgrindと同時に使用するとバグるので、valgrindでメモリリークを確認する際は-fsanitizeオプションを外してコンパイルしなおしましょう。
clang -fsanitize=address,undefined -g -o [output] [source]ASTの可視化
構文解析を実装する際に、抽象構文木（AST）をdot記法を用いて出力して可視化することで、構文解析の結果を直感的に把握できるようにしました。
Graphvizなどのソフトやオンラインエディタを使うことで、dotファイルを描画することができます。
感想・振り返り
今回のminishellの課題は42でこれまでに取り組んできた課題の中でも難易度が高く、また実装するべき分量も桁違いに多くとても大変でした。実際に課題に取り組み始めてから提出まで2ヶ月かかってしまいました。しかし、その分だけ（Linuxの）システムプログラミングについて理解を深めることができ、コードを読む・書く・デバッグするスキルが向上したと感じています。
また、42では初めてのチーム課題であったため、コミュニケーションの重要性やタスクの分割、チームでの開発の流れやコードレビューなどを学ぶことができました。進捗の報告をおろそかにしてしまうなど、改善するべき点が多く見つかったため、今後のチーム課題に活かしていきたいと思います。
実装の過程においては、思ってもいなかったようなbashの仕様に気づくことが多くあり、manや実際のソースコードをじっくり読むこと、様々な入力を試してみることが大切だと感じました。そうはいっても、bashのソースコードは巨大でかつ古いフォーマットで書かれていることもあり、理解するには時間と根気が必要でした。しかし、straceやcallgrindなどのツールを併せてじっくり観察することで、読み解くことができました。
bashの調査やminishellのデバッグに際しては、「仮説を立てる」→「検証を行う」→「結果を確認する」というサイクルを意識しながら進めました。適切に整理すること、可能な限りの手段で検証すること、検証結果を元にじっくり考察をすることの繰り返しで時間はかかりますが、正確な結果を得ることができたのではないかと思います。行き詰まるとついつい適当にコードを直したり、場当たり的な行動をしたりしてしまいがちですが、そのようなことがないように意識しました。3この辺りは、ちょうどこの前42の知人がデバッグの方法という記事を書いていたので、興味があれば読んでみてください。
チーム課題であったことや仕様が複雑であったことで、コメントの重要性を再認識しました。コメントには実装の流れや行っていることは当然として、「なぜそのような実装になっているのか・なっていないのか」「どのような仕様に注意するべきか」といった、コードからは読み取れないようなことを意識的に書き残すようにしました。また、リファレンスとしたサイトやコードを書き残すことで、後から振り返る際にも役立ちました。
また、チームで共有のnotionを使って調査したことや実装に際してのメモをしっかりと残すことで、あとから振り返る際にも役立ちました。
終わりに
調査や実装、デバッグは大変でしたが、minishellが動いた時の達成感はとても大きく、楽しい課題だったと思います。
minishellは名前の通りシェルのほんの一部の機能しか実装されておらず完璧に「シェルを理解した」とまでは言えないので、今後ジョブコントロールやより多くのビルトインコマンドを実装していきたいなと思っています。でもCじゃなくてRustで書きたいな…。
脚注
記事の要約を生成(beta)
※要約はGemini Nanoによって生成されたものです。内容の正確性を保証するものではありません。
Chrome組み込みのLLM「Gemini Nano」を利用して記事の要約を生成します。 生成には数十秒程度かかることがあります。 デバイスのCPUやメモリ、バッテリーの使用率が上昇することがありますのでご注意ください。