GNU Coreutils デコード（2018年）

(maizure.org)

4 ポイント投稿者 GN⁺ 2023-09-10 | 1件のコメント | WhatsAppで共有

GNU coreutils 8.3 のソース構造をユーティリティごとに読み解いていく長期解説プロジェクトで、コマンドラインツール設計を学ぶ初心者プログラマ向けになっている
使い方の文書ではなく、ソースコード読解の補助資料であり、各コマンドの名前空間、実行フロー、設計判断、アルゴリズム、UNIX と初期 Coreutils の系譜をあわせて扱う
coreutils には小さく単一目的の C プログラムが多く、グローバル変数・マクロ・goto・長い関数のような現代的観点では粗く見えるコードパターンも、歴史的文脈の中で読む必要がある
共通フローは初期化、オプション解析、入力処理、システムコール実行、失敗処理へと続き、getopt_long(), fts, gnulib ヘルパーが繰り返し登場する
貢献や修正の前には、既存ツールで再現可能か、後方互換性を壊さないか、POSIX からどの程度逸脱するかをまず確認すべきである

GNU coreutils 解説プロジェクトの範囲

GNU coreutils 8.3 の全ユーティリティを解説する長期プロジェクトである
想定読者は、コマンドラインユーティリティ設計を見て学ぶ初心者プログラマである
興味のあるユーティリティの source code を読む際に、背景説明として併せて参照する形が最も適している
この資料はユーザー向けマニュアルではなく、実際の使い方は man pages を参照する必要がある
プロジェクトは複数の段階で構成される
- Phase 1: 各ユーティリティごとの名前空間と実行概要ページを完了
- Phase 2: 主要な設計判断とアルゴリズム、UNIX と初期 Coreutils の系譜、より有用なソースウォークスルー、ソースコード進化の可視化を完了
- Phase indefinite: 各ユーティリティの行単位コードウォークスルーは長期継続対象として残っている
- 行単位ノート収集用の GitHub repo が提供されている

ユーティリティ別の解説ページ

各コマンド名は、そのユーティリティをデコードした詳細ページへリンクしている
各ページには議論、ソースコード、ウォークスルーが含まれる
太字で示されたユーティリティは Phase 2 で拡張された項目である
一覧には arch, base64, cat, chmod, cp, date, dd, df, ls, rm, sort, tail, tr, wc, yes など GNU coreutils のコマンドが含まれる

コードを読む前に知っておくべき前提

coreutils の多くのユーティリティはほぼ30年に及ぶ歴史を持ち、長年にわたり多くの人が修正してきたコードである
大半は小さく単一目的に合わせて作られた小さなプログラムである
- たいていは単一ソースファイルのプログラムである
- 長く生き残ることや、本来の役割以上に拡張されることを前提に設計されたコードではない
- グローバル変数、マクロ、goto、入れ子の switch / ループを持つ長い関数といったパターンが見られる
コード理解には POSIX の知識が重要である
- Utility Syntax Guidelines から読み始めるのがよい
- POSIX は入出力の相互運用性を定義するが、実際の動作方式は実装に委ねる
- GNU coreutils は POSIX に厳密には従わないこともあるが、権限ビット、uid/gid、環境変数、終了状態といった概念が深く根付いている
移植性の問題のため、coreutils は gnulib に大きく依存している
- ほぼすべてのユーティリティが、複数システムで共通の問題を処理するために設計された gnulib 関数を含む
coreutils は bash, zsh, ksh のようなシェルの支援を前提として実行される
- シェルは fork/clone でユーティリティを起動し、引数を渡し、環境を設定し、パイプで入出力をリダイレクトし、終了値を保持する
GNU coreutils はもともとシェル、テキスト、ファイルユーティリティという 3 つのパッケージから始まり、同種のユーティリティは設計パターンを多く共有している

基本的な設計パターン

ほとんどの CLI ユーティリティは共通して 3 つの段階を持つ
- フラグ、オプション、ローカライズなどを準備する設定段階
- 入力を読み取り実行パラメータを決める引数解析段階
- 入力を整えて 1 つ以上のシステムコールへ渡す処理・実行段階
実行中は複数の箇所で制約条件を確認し、失敗することがある
- 異なる終了状態が問題の位置を示唆する場合がある
- EXIT_FAILURE は一般的な失敗状態としてよく使われる
失敗後にはユーザーへフィードバックを返す
ユーティリティの種類は 3 つのグループに分けられる
- Trivial utilities: 数行のマクロを定義した後、別のユーティリティのソースを include し、マクロで特定の制御フローを強制する。例として arch, dir, vdir
- Wrapper utilities: 設定とオプション解析の後、コマンドラインオプションをシステムコール引数へ直接渡す。システムコールの結果がそのままユーティリティの結果になり、独自処理は少ない。例として link, whoami, hostid, logname
- Full utilities: 設定、オプション・引数解析、入力データ処理、複数のシステムコール実行をすべて備えた形であり、ほとんどのユーティリティがこれに属する

共通の初期化とオプション解析

すべてのユーティリティは main() の冒頭で短い初期化手順を持つ
- initialize_main (&argc, &argv);
- set_program_name (argv[0]);
- setlocale (LC_ALL, "");
- bindtextdomain (PACKAGE, LOCALEDIR);
- textdomain (PACKAGE);
- atexit (close_stdout);
この前処理コードは国際化や終了時動作の登録といった管理作業を扱うもので、各ユーティリティの中核動作には影響しない
コマンドラインオプション解析では Getopt 系のツール群が中核的な役割を果たす
- 短いオプションは -、長いオプションは -- の接頭辞を使う
- 短いオプションは文字列で定義し、長いオプションは struct を使う
- 短いオプション文字列では、引数が不要なら文字だけを書き、必須引数には :, 任意引数には :: を付ける
- kill の短いオプション文字列 Lln:s:t は、L, l, t には引数がなく、n, s には引数が必要であることを意味する
- すべてのユーティリティで getopt_long() が次のオプションを返すために使われる
- optind は argv[] 配列内の次の引数位置を指す
- optarg はオプション引数の値を指す文字ポインタである

ファイルシステム走査とシステムコールヘルパー

Unix 系システムでは、ファイルシステム走査を扱いやすくするため fts ライブラリをサポートしていることが多い
- fts_open() または xfts_open() でパスから FTS 構造体を作る
- ツリー中のファイルやディレクトリノードは FTSENT 構造体で表現される
- fts_read() を呼ぶと FTSENT が生成され、この過程がツリー走査になる
- FTSENT->fts_info フィールドは項目説明によく使われ、項目の処理方法を決めるのに利用される
coreutils は libc が提供するもの以外にも多くのシステムコールラッパーやヘルパーを使う
書き込み処理では write() システムコールラッパーや fwrite() のような libc 関数に加え、full_write() のような非標準関数も登場する
- full_write() は致命的な失敗が起きない限り書き込みを再試行し続ける
- safe_write() は割り込みが発生しても write() システムコールを再試行する
- dd の iwrite(), split の cwrite() のように単一ユーティリティ内でのみ使われる書き込みヘルパーもある

共通関数とコードの慣用句

すべてのユーティリティは最低でも main(), usage(), _() の 3 つの関数を使う
usage() は入力パラメータ、意味、正しい構文を含むヘルプを表示する
_() は system.h で定義されたマクロで、単純な文字列を GNU gettext.h の Native Language Support 機能へ接続する
- ユーザーに表示される文字列であれば、たいていこのマクロで囲まれる
ほとんどの非自明なユーティリティでは共通コード行が繰り返し現れる
- #include "system.h" はシステム依存マクロ、変数、非標準ユーティリティ関数を定義する
- PROGRAM_NAME はユーティリティの正式名を定義し、バージョン確認に使われる
- AUTHORS はユーティリティ作者を定義し、バージョン確認に使われる
- emit_try_help() は失敗した出力の後にヘルプを試すよう促す文を出力する
- emit_ancillary_info (PROGRAM_NAME) はコマンド別出力の後に共通の追加ヘルプ情報を出力する
- initialize_main(&argc, &argv) は VMS の組み込みワイルドカード展開を処理し、ほとんどの他 OS では取り除かれる
- atexit(close_stdout) はプログラム終了時にバッファ付きストリームを flush して閉じる関数を登録する
初心者には見慣れない C の慣用句も登場する
- !! は二重単項 NOT 演算で、値をブール値へ強制変換するために使われる
- do { ... } while (0) は複数文マクロを包み、プリプロセッサ置換後のトークン化を安全にする非ループパターンである

メンテナンス方式と貢献前の確認

coreutils のような活発なプロジェクトは、概ね 3 種類のメンテナンスフローで進化する
プロジェクト全体の変更は、全ユーティリティの構造と依存関係にまたがる大きな変更である
- 1995 年に GNU gettext project を通じて Native Language Support が追加され、ほとんどのテキスト出力行に _() マクロが導入された
- 1996 年には国際化対応が拡張され、main() に複数の初期化コードが追加された
- 1995 年には usage 出力にユーティリティの目的を短く説明する文が追加された
- 2003 年には VMS ワイルドカード対応が追加され、これは initialize_main() 関数に見られる
- 2016 年には失敗経路でのコンパイラ警告を避けるため、die() マクロが大半の exit() と error() 関数を置き換えた
ユーティリティ別の変更は、バグ修正、新機能、最適化に分かれる
- join, sort, uniq は 2016 年のパッチ以前はオーバーフロー攻撃に脆弱だった
- df には 2013 年に --output オプションが追加された
- yes はより良いバッファリングにより性能が改善された
年次メンテナンスには、少なくとも全ユーティリティの著作権年の更新が含まれる
- FSF 住所更新のような管理上の変更もあり、実行には影響しない
貢献者はまず GNU project page, contribution guidelines, rejected features, mailing list archives を確認するとよい
コードを書く前に確認すべき問いは 3 つある
- 既存ツールで同じ機能を再現できるか
- 貢献が後方互換性を壊さないか
- 提案した動作が POSIX から大きく逸脱していないか
確信がなければ、メーリングリストでコミュニティに問い合わせる手順が推奨される

興味深い細部

最も短いユーティリティは false で 2 行、arch, dir, vdir と同率である
最も短い独立実行ユーティリティは true で 80 行であり、最初のバージョンはほぼ最小の C プログラムに近い
最も長いユーティリティは ls で 5308 行である
多くのユーティリティは 1970 年代の Research UNIX までさかのぼり、一部は Multics にまで至る
最古の精神的祖先は 1963 年ごろの CTSS LISTF コマンドで、後に ls と短縮された
- LISTF は 1962 design paper にある元々の 18 個のユーティリティの 1 つである
dd の独特な構文は 1960 年代初頭の OS/360 job control language を想起させる
sort はマルチスレッドを活用する唯一のユーティリティである
fmt は機能コストを使って行と段落の最適化を示す
yes はページ整列メモリバッファを使って高性能出力を実現する
df はデバイスメタデータを使い、du はすべてのファイルを確認するため、df のほうが速い
cksum には通常実行用と CRC-32 テーブル生成用の 2 つのエントリポイントがある
echo には失敗条件がない
test と expr の設計は一般的なユーティリティ構造と大きく異なる
su はもともと coreutils/shellutils で保守されていた

見ておきたい実装

shuf と shred は乱数に ISAAC cipher) を使う
shuf は Reservoir sampling を使う
sum はレガシーな System V と BSD のチェックサムを使う
expr は左結合の式評価を使う
shred は Secure overwrite を使う
cksum は CRC-32 checksum を計算する
sort は Merge sort を改変して使う
factor は数学的実装要素を見る価値のあるユーティリティである

支援案内

個人支援を受け取る設定はされていない
時間やお金を共有したいなら Free Software Foundation に貢献できる

1件のコメント

GN⁺ 2023-09-10

Hacker News の意見

「これらのユーティリティの多くはほぼ30年もの歴史があり、その間に多くの人が修正してきた」としながらも、「長寿命や役割以上に拡張されることを前提に設計されたものではない」と言うなら、著者が考える長寿命を念頭に置いたプログラムの例を見てみたい
30年間生き残ったプログラムでも、今後30年続きそうだと考えているプログラムでも気になる
- その役割が正確に何なのかが問題。こうしたツールでできることに限界があるのだろうかと思う
  自作の小さなプログラミング言語をテストするために bash と coreutils でテストフレームワークを作ったのだが、最初は「ちゃんとした」言語を使わなかったことが気持ち悪かったものの、実際には非常にうまく動作し、並列実行もできた
  唯一テストできなかったのはプログラムの argv[0] で、どう組み合わせても望む動作を正確に作れなかったため、coreutils に env の機能要望とパッチを送った: https://lists.gnu.org/archive/html/coreutils/2023-08/msg0006...
  取り込まれそうで、古いプログラムに新機能が入ることになる
- ここで言っているのは「長く活発に開発されるように作られている」という意味だと見るべきだろう
  著者が列挙した慣行は、大きなプログラムでは通常、規模が大きくなるほど保守性を損なうものとして批判されるものだ
- おそらく「長い開発寿命」を意味していたのだと思う。つまり、ほぼ一度書いて長く使うユーティリティという意味であり、「一つのことをうまくやる」というやり方の利点でもある
- 不思議なことに、「long life」を長時間実行され続けるプログラムとして解釈していた。明確な入力、短い実行、明確な出力を持つツールと対比される意味だと見ていた
- Emacs?
参考になりそうな資料:
GNU coreutils のテスト方法: https://www.pixelbeat.org/docs/coreutils-testing.html
coreutils の各コマンドの探究: https://ratfactor.com/slackware/pkgblog/coreutils
GNU Coreutils によるコマンドラインのテキスト処理: https://learnbyexample.github.io/cli_text_processing_coreuti... — テキスト処理ツールを20個以上扱った私の電子書籍
関連記事:
Decoded: GNU Coreutils (2018) - https://news.ycombinator.com/item?id=29871037 - 2022年1月、コメント7件
Decoded: GNU coreutils (2019) - https://news.ycombinator.com/item?id=26411908 - 2021年3月、コメント38件
Decoded: GNU Coreutils - https://news.ycombinator.com/item?id=20328650 - 2019年7月、コメント55件
面白い事実として、macOS で Homebrew を使って coreutils をインストールすると、macOS にはすでに od(1) があるため、coreutils の od は god(1) としてインストールされる
著者が見ているなら、少なくとも1つ誤りがある。shred ページの短い説明[0]が実際には csplit の説明[1]であり、「ファイルの内容を隠すために上書きし、任意で削除する」程度になるべきだ
[0]: https://maizure.org/projects/decoded-gnu-coreutils/shred.htm...
[1]: https://maizure.org/projects/decoded-gnu-coreutils/csplit.ht...
こういうものがあるとは知らなかったが、素晴らしい。yes のように単純なものでも、標準出力に書き込むユーティリティの基本コードがどう書かれているかを見るにはかなり興味深い
https://maizure.org/projects/decoded-gnu-coreutils/yes.html
- 私の要点は、単純なユーティリティであっても、きちんと書かれ最適化される価値があるということだ
  例えば、出力を非常に高速に書き出す方法を学べる最小限の例があるのは良い。プログラムが非常に短いので行数はあまり重要ではなく、作者が方法を知っているなら、できるだけ速くして邪魔にならないようにするほうがよいと思う
- 面白半分で作った Go 実装はこうだ:
```
package main

import "flag"

func main() {  
yes := flag.String("m", "y", "message")  
flag.Parse()  
for {  
println(*yes)  
}  
}  
```
基本ユーティリティの一覧としてかなり面白い。UNIXをかなり長く使っているのに、shred、shuf、factor みたいなものは聞いたことがなかった
一度
```
sudo find / -type f -exec shred {} \;  
```
を実行して、自滅するまでどれくらい持つのか見てみたくなる。もちろん 仮想マシン か、簡単に再フラッシュできる機器で
- 似たようなことを dd でやってみたが、最後まで完了してしまってかなり拍子抜けした
  クラッシュするか、少なくとも接続が切れることを期待していたのに、カーネルと sshd、bash はまだメモリ上にあって、何もまともにできないプロンプトに戻ってきた
- Linuxではおそらく最後まで行く可能性が高い。現在実行中の 実行ファイルとライブラリ には書き込めないため（ETXTBUSY）、shred が自分自身や find を壊せない
/bin/true が実際には失敗して false を返すことがあり得る、という点が気に入った。技術的には「Not /bin/false」呼び出しのほうがより堅牢になるわけだ: https://github.com/coreutils/coreutils/blob/master/src/true....
もちろん、ほとんど起こり得ないケースだとは分かっているが、単純に笑える
- true コマンドでもう一つ興味深いのは、必要以上にはるかに複雑になっていること
  まず練習:
```
touch mytrue  
chmod u+x mytrue  
./mytrue  
echo "error code for mytrue is $?"  
```
  true は文字どおりこうして始まった。かなり禅問答的だ
  最初の変化は法務が原因だった。すべてのコードに著作権表示が必要で、空ファイルにも必要だった。そこで何もないファイルが著作権表示だけのファイルになり、「何もないものに著作権をかけられるのか？」という疑問が浮かぶ。AT&Tはそれを試みた
  次に誰かが、プログラムは明確に定義されるべきで、Unixの偶然の挙動に依存すべきではないと言った。その時点ではかなり妥当だった。そこで true にはついにコードが入り、そのコードは exit 0 だった
  さらに誰かが、システムユーティリティはシェルではなくCで書いたほうが速いと言い、OpenBSDには今でもその形のよい例がある: http://cvsweb.openbsd.org/cgi-bin/cvsweb/~checkout~/src/usr....
  ある時点でGNUの官僚主義が入り込み、すべてのプログラムは -h フラグをサポートすべきだと言い、次にすべてのプログラムはロケールをサポートすべきだと言ったため、現在のGNU true は驚くことに80行になっている: https://github.com/coreutils/coreutils/blob/master/src/true....
  それでいいとも言えるが、定義上「何もせず成功する」プログラムにしてはコードが多い
  http://trillian.mit.edu/~jc/humor/ATT_Copyright_true.html
- オプションを付けて実行したときだけの話では？単に true を実行するだけなら、コメントが紛らわしいのでなければ影響はなさそう
データ構造とアルゴリズムをどう有用に適用するかの感覚を養いたい初心者プログラマーなら、ここで特に見るべきものはあるだろうか？
- coreutils の中の巧妙さの大半は、データ構造やアルゴリズムというより、カーネルと効果的にかみ合う方法にある
  例えば、データをユーザー空間へコピーしないように read()/write() の代わりに copy_file_range() を使う、といった具合。計算機科学というよりソフトウェア工学に近い
- 自分の理解が間違っているのかもしれないが、データ構造とアルゴリズム がコマンドラインツールとどう関係するのか分からない
このサイトの要点を見落としているのかもしれないが、それぞれについて manページ や infoページはすでにあるのでは？
- 使い方の情報ではなく、このサイトはプログラムが 内部でどのように動作するか を詳しく扱っている

GNU Coreutils デコード（2018年）

GNU coreutils 解説プロジェクトの範囲

ユーティリティ別の解説ページ

コードを読む前に知っておくべき前提

基本的な設計パターン

共通の初期化とオプション解析

ファイルシステム走査とシステムコールヘルパー

共通関数とコードの慣用句

メンテナンス方式と貢献前の確認

興味深い細部

見ておきたい実装

支援案内

関連記事

1件のコメント

Hacker News の意見