I/O スケジューラ (その2) + 他 [Linux]
○ I/O スケジューラ (その2)
[ありえるえりあ] I/O スケジューラ (その2)
○ JCSSAのセミナーで発表します
JCSSAのセミナーで発表させてもらう事になりました。
他の発表者が凄すぎて完全に浮いています。気張ってもしょうがないので、正直に手持ちの成果を披露してきます。
http://www.jcssa.or.jp/seminar/Content1.php?semiId=200911090001
○ 良き友人の話
研究室の友人からとある web アプリケーションの bot を作ってくれと頼まれた。
とてもおもしろそうな課題だったので、ふたつ返事で引き受ける。
対象は flash アプリなのだが、greasmonkey を使って GM_xmlhttpRequest から擬似リクエストを発行すればよいと手を動かしたが。flash が発行する POST/HTTP リクエストのデータの中身が JSON 形式ではなく、バイナリデータだったりする。Javascript でバイナリデータの送信を行うのはめんどくさい。
そもそも擬似リクエストを発行するのであれば、必ずしもブラウザを利用しなくてもよい (cookie の取得が面倒だが) 。なので、http のプロトコルメッセージを送るスクリプトを perl で書く(telnet で通信するような単純な処理)。
がしかし。flash アプリ内部でセッション毎に乱数を設定していて、それが認証のキーワードになるみたい。乱数生成は (flash を解析しない限り) こっちではできないで、擬似リクエストのアプローチを断念。
仕方ないので gui 操作を自動化する作戦に切り替える。ただし、処理が一辺倒ではないので web リクエストメッセージをトレースして、処理を切り替えるようにしなければならない。
そうして出来上がったプログラムを友人に見せると、友人は喜んでくれ、感謝してくれた。
自分としても、この課題に取り組んでいる最中にとても色々な勉強ができ、依頼してくれた友人にとても感謝している。
開発過程で学ぶ事があった事で喜びがあり、モノを作って友人に感謝される事でまた喜びがある。
[ありえるえりあ] I/O スケジューラ (その2)
○ JCSSAのセミナーで発表します
JCSSAのセミナーで発表させてもらう事になりました。
他の発表者が凄すぎて完全に浮いています。気張ってもしょうがないので、正直に手持ちの成果を披露してきます。
http://www.jcssa.or.jp/seminar/Content1.php?semiId=200911090001
○ 良き友人の話
研究室の友人からとある web アプリケーションの bot を作ってくれと頼まれた。
とてもおもしろそうな課題だったので、ふたつ返事で引き受ける。
対象は flash アプリなのだが、greasmonkey を使って GM_xmlhttpRequest から擬似リクエストを発行すればよいと手を動かしたが。flash が発行する POST/HTTP リクエストのデータの中身が JSON 形式ではなく、バイナリデータだったりする。Javascript でバイナリデータの送信を行うのはめんどくさい。
そもそも擬似リクエストを発行するのであれば、必ずしもブラウザを利用しなくてもよい (cookie の取得が面倒だが) 。なので、http のプロトコルメッセージを送るスクリプトを perl で書く(telnet で通信するような単純な処理)。
がしかし。flash アプリ内部でセッション毎に乱数を設定していて、それが認証のキーワードになるみたい。乱数生成は (flash を解析しない限り) こっちではできないで、擬似リクエストのアプローチを断念。
仕方ないので gui 操作を自動化する作戦に切り替える。ただし、処理が一辺倒ではないので web リクエストメッセージをトレースして、処理を切り替えるようにしなければならない。
そうして出来上がったプログラムを友人に見せると、友人は喜んでくれ、感謝してくれた。
自分としても、この課題に取り組んでいる最中にとても色々な勉強ができ、依頼してくれた友人にとても感謝している。
開発過程で学ぶ事があった事で喜びがあり、モノを作って友人に感謝される事でまた喜びがある。
lkml でお勉強 (その1-1) [Linux]
○ ページフレーム回収処理のパフォーマンスアップの話 (前編)
関連記事 : スワップ処理(その5) + 他
GNU/Linux (以下, linux) のカーネルコードを追い、onix を作り、linux コードをいじってきたが、lkml にパッチを送ったりコミュニティーに貢献できる実力はまだまだ不足している。
また本をいくら読んでも lkml で戦う力はつかないので、これからしばらく lkml の patch を使って学習する。
具体的には、(学習当時) 最近投稿された patch のうちで議論が活発なメールをピックアップし、それが一体どういういった内容なのかという事を、バックグラウンドを含めて解説してゆく。
ここでの目的は、patch の検証を行う事では無く patch を通して linux の理解を深める事である。
今回の教材は富士通の kosaki さんが今月の17日に投稿した patch (*1) を取り上げる。
文量が多いので、同 patch を理解する上で必要となるバックグラウンドについての解説を今回行い、patch の詳細な解説については次回に回す。
同 patch に書かれているコメントは、「cs オブジェクトの isolate_pages メソッドを呼び出し、0 が帰ってきたら shrink_page_list() を呼び出す必要がないので、これを迂回する処理を shrink_inactive_list() に書いた」という内容である。
これについて論じる前に、一連の処理のバックグラウンドをおさらいする。尚、参照するコードは lkml をテキストとする為、最新開発版を用いる。適宜 git を使って linus のリポジトリ等をチェックアウトされたし。
shrink_inactive_list() は mm/vmscan.c での内部関数であり、非アクティブなページフレーム郡を回収を行う処理である。またこれは vmscan.c の処理のインターフェイスである shrink_slab()、 try_to_free_pages() そして shrink_all_memory() などから呼び出される。以下では、try_to_free_pages() 処理について解説する。
try_to_free_pages() は、ゾーンリスト (struct zonelist 型) オブジェクトと、回収するページフレームの数を表す 2 の指数を引数に渡し、vmscan.c の内部処理用のデータ構造である scan_control オブジェクトを生>成・初期化し、各メモリゾーンにおいて shrink_zone() を呼び出す。
ゾーンリストオブジェクトは、各メモリゾーン (*2) オブジェクトを持っており、NUMA システムでない限りはシステムにおいて唯一のオブジェクトになる (はず)。
shrink_zone() では get_scan_ratio() を呼び出し、無名ページとページキャッシュどちらに属するページフレームをどれだけ回収するかの重み付けを計算する。
次に、対象ゾーンの各種類のページをどれだけ捜査するのかを決定する。通常各メモリゾーンに所属するページ郡は動的に include/linux/mmzone.h で宣言されている列挙型 lru_list の種類に分類される。そして、各 lru_list のページ郡に対して shrink_list() を実行する。
shrink_list() では引数として受け取った lru_list 列挙型オブジェクトの値に応じて、ページフレームの回収処理を行う。lru_list で非アクティブリストを指定されたり、対象のメモリゾーンにおいて非アクティブリストのページフレームが多数を占めている場合、shrink_inactive_list() が呼ばれる。
ここでようやく、今回の話題である shrink_inactive_list() 処理が実行される。kosaki さんの patch の中身を考察する前に、shrink_inactive_list() の処理について見てみる。
shrink_inactive_list() はまず、作業用データ構造である sca_control オブジェクトの isolate_pages メソッドを呼び出す。この実態は、try_to_free_pages() で isolate_pages_global() 関数に設定されており、間接的に isolate_lru_pages を呼び出す。isolate_lru_pages() の処理は、回収するページを既存の LRU リストから分離して、ページフレーム回収用のリストに結合する。この処理の細部については後で述べる。
この時点で shrink_inactive_list() では、isolate_pages() メソッドの呼出しによって、回収するページフレームが決定した。後は、ページフレームの属性情報の書き換えやら、各種類のページ数の更新を行い、shrink_page_list() 関数を呼び出す。
shrink_page_list() 関数では、引数で受け取ったページリストに属するページを、各ページの種類に応じた方法によって回収してゆく。
以上が、kosaki さんのパッチを解読する上でのバックグラウンドになる。同氏の patch の解説については次回に書くことにする。
(*1) http://lkml.org/lkml/2009/7/15/371
(*2) 各メモリゾーンの種類は include/linux/mmzone.h で宣言されている列挙型 zone_type の __MAX_NR_ZONES の数だけ存在する
関連記事 : スワップ処理(その5) + 他
GNU/Linux (以下, linux) のカーネルコードを追い、onix を作り、linux コードをいじってきたが、lkml にパッチを送ったりコミュニティーに貢献できる実力はまだまだ不足している。
また本をいくら読んでも lkml で戦う力はつかないので、これからしばらく lkml の patch を使って学習する。
具体的には、(学習当時) 最近投稿された patch のうちで議論が活発なメールをピックアップし、それが一体どういういった内容なのかという事を、バックグラウンドを含めて解説してゆく。
ここでの目的は、patch の検証を行う事では無く patch を通して linux の理解を深める事である。
今回の教材は富士通の kosaki さんが今月の17日に投稿した patch (*1) を取り上げる。
文量が多いので、同 patch を理解する上で必要となるバックグラウンドについての解説を今回行い、patch の詳細な解説については次回に回す。
同 patch に書かれているコメントは、「cs オブジェクトの isolate_pages メソッドを呼び出し、0 が帰ってきたら shrink_page_list() を呼び出す必要がないので、これを迂回する処理を shrink_inactive_list() に書いた」という内容である。
これについて論じる前に、一連の処理のバックグラウンドをおさらいする。尚、参照するコードは lkml をテキストとする為、最新開発版を用いる。適宜 git を使って linus のリポジトリ等をチェックアウトされたし。
shrink_inactive_list() は mm/vmscan.c での内部関数であり、非アクティブなページフレーム郡を回収を行う処理である。またこれは vmscan.c の処理のインターフェイスである shrink_slab()、 try_to_free_pages() そして shrink_all_memory() などから呼び出される。以下では、try_to_free_pages() 処理について解説する。
try_to_free_pages() は、ゾーンリスト (struct zonelist 型) オブジェクトと、回収するページフレームの数を表す 2 の指数を引数に渡し、vmscan.c の内部処理用のデータ構造である scan_control オブジェクトを生>成・初期化し、各メモリゾーンにおいて shrink_zone() を呼び出す。
ゾーンリストオブジェクトは、各メモリゾーン (*2) オブジェクトを持っており、NUMA システムでない限りはシステムにおいて唯一のオブジェクトになる (はず)。
shrink_zone() では get_scan_ratio() を呼び出し、無名ページとページキャッシュどちらに属するページフレームをどれだけ回収するかの重み付けを計算する。
次に、対象ゾーンの各種類のページをどれだけ捜査するのかを決定する。通常各メモリゾーンに所属するページ郡は動的に include/linux/mmzone.h で宣言されている列挙型 lru_list の種類に分類される。そして、各 lru_list のページ郡に対して shrink_list() を実行する。
shrink_list() では引数として受け取った lru_list 列挙型オブジェクトの値に応じて、ページフレームの回収処理を行う。lru_list で非アクティブリストを指定されたり、対象のメモリゾーンにおいて非アクティブリストのページフレームが多数を占めている場合、shrink_inactive_list() が呼ばれる。
ここでようやく、今回の話題である shrink_inactive_list() 処理が実行される。kosaki さんの patch の中身を考察する前に、shrink_inactive_list() の処理について見てみる。
shrink_inactive_list() はまず、作業用データ構造である sca_control オブジェクトの isolate_pages メソッドを呼び出す。この実態は、try_to_free_pages() で isolate_pages_global() 関数に設定されており、間接的に isolate_lru_pages を呼び出す。isolate_lru_pages() の処理は、回収するページを既存の LRU リストから分離して、ページフレーム回収用のリストに結合する。この処理の細部については後で述べる。
この時点で shrink_inactive_list() では、isolate_pages() メソッドの呼出しによって、回収するページフレームが決定した。後は、ページフレームの属性情報の書き換えやら、各種類のページ数の更新を行い、shrink_page_list() 関数を呼び出す。
shrink_page_list() 関数では、引数で受け取ったページリストに属するページを、各ページの種類に応じた方法によって回収してゆく。
以上が、kosaki さんのパッチを解読する上でのバックグラウンドになる。同氏の patch の解説については次回に書くことにする。
(*1) http://lkml.org/lkml/2009/7/15/371
(*2) 各メモリゾーンの種類は include/linux/mmzone.h で宣言されている列挙型 zone_type の __MAX_NR_ZONES の数だけ存在する
ヘボコード [Linux]
○ GNU/Linux 内部で 2^32 以上の数値をいたい話
諸処の事情を割愛して。
こういう計算をさせたい。
storage_blocks には、ストレージデバイスのブロック数が入る。
自分のヘボっぷりがまたも露呈する事になるが、最近これに重大な問題がある事に気づいた。
最近のストレージデバイスでも storage_block は x86 のアーキテクチャで扱う事が出来るサイズ (最高 2 TB (*1)) である。しかし、storage_blocks * PAGE_SIZE は、ほとんどの場合オーバーフローし、ret に期待通りの結果が入らない。
簡単な解決策として、
とすれば、うまくいきそうである。現代情報社会において、64 bit 変数はおよそ無限大のサイズを扱える。
しかし、arjan 曰く GNU/Linux において 64bit 変数を使うことはありえない (*2) ようなので、無い知恵を絞って考える。
でかい値をシフトしたりと、いろいろ面白い事ができそうだが。無難に、
とした。極端に小さいストレージでない限り、これで問題は起きないだろう。
「実につまらない」というツッコミは無しの方向でお願いします。
(*1) gendisk オブジェクトの capacity メンバはセクタ数で表される為。一般的なセクタサイズは 512 byte (だと思っている) なので、32 bit 変数で 2 TB のストレージサイズを表現できる。しかし、セクタサイズはカーネルではなく、ストレージデバイスによって決定される為、これが大きくなれば、扱えるアドレス空間も大きくなる (例えばセクタサイズが 4KB になれば、16TB のストレージアドレス空間を 32 bit 環境で扱える)。
(*2) http://search.luky.org/linux-kernel.2005/msg38380.html
諸処の事情を割愛して。
unsigned int ret;
ret = (storage_blocks * PAGE_SIZE) / (PAGE_SIZE + sizeof(struct foo));
こういう計算をさせたい。
storage_blocks には、ストレージデバイスのブロック数が入る。
自分のヘボっぷりがまたも露呈する事になるが、最近これに重大な問題がある事に気づいた。
最近のストレージデバイスでも storage_block は x86 のアーキテクチャで扱う事が出来るサイズ (最高 2 TB (*1)) である。しかし、storage_blocks * PAGE_SIZE は、ほとんどの場合オーバーフローし、ret に期待通りの結果が入らない。
簡単な解決策として、
unsigned int ret;
unsigned long long hoge = storage_blocks * PAGE_SIZE;
ret = (unsigned int)(hoge / (unsigned long long)(PAGE_SIZE + sizeof(struct foo)));
とすれば、うまくいきそうである。現代情報社会において、64 bit 変数はおよそ無限大のサイズを扱える。
しかし、arjan 曰く GNU/Linux において 64bit 変数を使うことはありえない (*2) ようなので、無い知恵を絞って考える。
でかい値をシフトしたりと、いろいろ面白い事ができそうだが。無難に、
unsigned int ret;
ret = (storage_blocks / (PAGE_SIZE + sizeof(struct foo))) * PAGE_SIZE;
とした。極端に小さいストレージでない限り、これで問題は起きないだろう。
「実につまらない」というツッコミは無しの方向でお願いします。
(*1) gendisk オブジェクトの capacity メンバはセクタ数で表される為。一般的なセクタサイズは 512 byte (だと思っている) なので、32 bit 変数で 2 TB のストレージサイズを表現できる。しかし、セクタサイズはカーネルではなく、ストレージデバイスによって決定される為、これが大きくなれば、扱えるアドレス空間も大きくなる (例えばセクタサイズが 4KB になれば、16TB のストレージアドレス空間を 32 bit 環境で扱える)。
(*2) http://search.luky.org/linux-kernel.2005/msg38380.html
GNU/Linux システムにおけるブロックデバイスに対する I/O 要求 + 他 [Linux]
○ 概要
ブロックデバイスに対する I/O リクエストは、通常ファイルシステムのインターフェイスを介して発行される。ここでは、GNU/Linux (以下、Linux) において低レベルファイルシステムが提供するインターフェイスを用いずに行う、ブロック I/O リクエストの仕組みを紹介する。
○ はじめに
ユーザプログラムから、ファイルシステムを用いずにデバイスファイルに対する I/O をプログラマブルに行う事は非常に簡単である。これは、Linux カーネルがデバイスファイルという形で、ファイルシステムが扱えるように構造を抽象化しているからである。逆を言うと、VFS のインターフェイスはユーザによって操作される事を前提としている為、カーネルの都合でデバイスを扱う為には、話が複雑になる。前回書いた記事にも共通する事が言える。
ここでの目的は、ファイルシステムの力を借りずに、カーネルに組み込んだ自前の処理関数によってブロック I/O を発行する事である。ファイルシステムの力を借りる事ができない理由は、上述したように処理の発信元がカーネル側にある事に起因する。
ブロックデバイスに対する I/O 処理は、一般的に Linux カーネルが提供するデバイスファイルを通して行われる。デバイスファイルに対するファイル操作処理は VFS インターフェイスを通し、bdev 特殊ファイルシステムによって処理される。
○ Linux カーネルによるブロック I/O
まずは、システム起動後からブロックデバイス初期化までの大まかな流れを追い、処理の範囲を絞りこむ。
システムを起動してから、デバイスをマウントし、ファイルシステムから参照されるまでの流れはおおよそ次のようになっている。
システム起動後、Linux カーネルは PCI デバイスを捜査し、k オブジェクトのツリーを生成する。同時にブロックデバイスに対して block_device オブジェクトを生成し、all_bdevs が参照するリストに登録される。そして、デバイスファイルという形でデバイス情報がファイルシステムに対して提供される。最後に、/etc/fstab が参照され、各デバイスが指定されたファイルシステムでマウント処理される。
ここでのミソは 2 つ。各デバイスは Linux によって、デバイスファイルという形で提供されるという事と、マウント処理されてはじめて VFS からデバイスに対してデータを読み書きする事ができるという事。
次に、このデバイスファイルに対するファイルオープンの処理の流れと内部的な処理について見てゆく。
デバイスファイルに対して open システムコールが発行されると、パス名検索を行った後、生成した nameidata オブジェクトを nameidata_to_filp() 関数に渡す。同関数では、パス名検索の結果取得した nameidata オブジェクトから対象ファイルのディレクトリエントリの情報を取り出し、ここから __dentry_open() を呼び出す。
ここまでの処理は、対象ファイルの inode 情報を取り出す常套手段で、各種ファイルシステム共通の処理になる。ここから、ファイルシステムのファイル操作の共通インターフェイスを定義したデータ構造 file_operations オブジェクトを取得し、open() メソッドを呼び出す。マウントされていないブロックデバイスは、bdev 特殊ファイルシステムによって定義されるスーパーブロックを持ち、デバイスファイルに対する読み書きによって叩かれるインターフェイスの実態は、この bdev ファイルシステムが定義する処理にある。これらの処理は fs/blocks.c で定義される。
重要なのは、どのように Linux がブロック I/O を発行するかという事である。
Linux はファイルシステムからの I/O 処理の要求を submit_bio() という関数で一手に引き受けている。ここに処理の対象となるブロックデバイスのデータ構造 block_device オブジェクトと bio オブジェクト 及び I/O の範囲を個別に指定した bio_vec オブジェクトのリンクを渡す事でブロック I/O が発行される。
まずは、処理の対象となるブロックデバイスの block_device オブジェクトの取得方法について。
bdev ファイルシステムのスーパーブロックが提供する inode オペレーションの .alloc_inode() メソッドの本体は bdev_alloc_inode() [fs/block_dev.c] で定義される。ここでは、bdev_inode オブジェクトを生成し、inode メンバを返している。bdev_inode のデータ構造は struct inode * の他に、struct block_device * を持つ。これは、bdev ファイルシステムで inode を作成した時に、block_device も同時に作成される。
なので、デバイスファイルの inode さえ取得できれば、オブジェクトのメンバのアドレスからオブジェクト本体のアドレスを逆算する container_of() などのマクロによって block_device オブジェクトを取得、またはその逆ができる。これらの操作を BDEV_I() や I_BDEV() マクロによって内部的に行っている。
Linux は上述したような処理を行う関数を外部に対して提供している。それが lookup_bdev() になる。
ブロックデバイスの操作が submit_bio() にて行われているわけだから、block_device オブジェクトを取得したら、bio オブジェクトを生成・初期化して submit_bio() を呼び出せば I/O 操作を行ってくれるように思うかもしれないが、そうは問屋が卸さない。Linux のブロックデバイスサブシステムに対して I/O 要求を発行する際にディスクを表すデータ構造の gendisk オブジェクトを参照し request_queue オブジェクトを生成して、デバイスドライバに処理を委託する。
通常、デバイスのマウント時に gendisk オブジェクトは生成されるが、特定のファイルシステムを持たないこの状況で submit_bio() を呼び出すと、generic_make_request() 関数で無効なアドレスを参照して例外ハンドラが呼び出されるか、予測不可能な処理が起こる。
この段階では、デバイスドライバの初期化が行われているだけで、ディスクオブジェクトなどの I/O ブロック層におけるオブジェクト郡は生成されていないようである。
この為、対象デバイスに対するブロックデバイスサブシステムに関連するデータ構造の生成・初期化も自前で行わなければならない。これを行う為に、デバイスファイルに対してカーネル側でファイルオープン処理を行う。デバイスファイルに対して、ファイルオープンを行うと、対象デバイスの bdev に関する I/O ブロック層の各種オブジェクトを生成してくれる。
そして、bio オブジェクトを生成し、書き込みを行う場所 (bi_sector) 等の設定を行う。又、block I/O を行う際に指定するバッファ領域としてページディスクリプタを指定する。なので、kmalloc() などによるスラブキャッシュからバッファ領域を取得するのではなく、直接ページアロケータにページの取得要求を出す。ページの取得等のページ操作については、ソースを見てもらえれば分かると思う。
○ サンプルプログラムソース
http://dev.ariel-networks.com/Members/ohyama/stuff/onix_blk.c/download
○ 注意
多分誰もいないと思うが。ユーザ権限でデバイスのファイルシステム壊すことが出来るので、これを使う際には、間違っても重要なデータが入っているデバイスに対して行うべきではない。どうでもいい USB メモリか何かで試して貰いたい。
【義憤にかられた瞬間：とある大学教授のお話】
新たな年度が始まり、今年度から学部 4 年となった。この時期は、やれ就活だ、研究だ、進学だと騒がしく。特に年度始めはそれが顕著である。
今月始め、同学年の学生を集めたガイダンスが開かれた。
しばらく事務的な話が続いた。窓に映る桜並木と春の暖かさが眠気を呼び寄せ、気がつくと教室は静まり、壇上には見慣れた偉い教授が立っていた。そして就活に関する話をはじめられた。
そこでは、昨年度の就職実績 (?) や、おもな就職先の企業の話をした後、大学院への進学の話に移った。話をはじめてから 5 分程度の時間が経過し、ようやくエンジンがかかってきたのか声に熱が入りはじめ、「就職するなら大企業かベンチャーか」という話になった。
教授は「まぁ、いろいろな考えを持った方がおられるでしょうが。」と前置きをした後、「絶対。大企業の方がいいです。」と言い切った。
相手は学者なので、ここから話の根拠が展開される。教授は始めにこう結論づけた。「なんといっても、生涯賃金が違います。」
ここまでは、よく耳にする話である。話を聞いている周りの学生達は退屈そうな目で教授を見ていたに違いない。
しかし教授の話はここで終わらない。教授は次にこう言い放った。「昨今、中央省庁の官僚の天下りが問題視されています。ですが、民間企業では当り前の事です。」そして、具体的な企業名と役職を挙げ、過去に子会社の社長やら重役やらに就任した話を繰り広げ、生涯設計を検討するなら大企業に入る事はひとつの大きな鍵になると結論づけた。
教授が仰りたかった事は、つまるところ『大企業の本体に入れば、生涯賃金は一般的に中小企業よりも高いし、定年過ぎても天下りやらを行え、人生安泰』という事であろう。
これには、驚いた。自分自身、この問に関する答えは持ち合わせていないし、その行為自体が正しいか間違っているかを述べるだけの根拠を持っていないし、個別のケースに対して意見できる程事情も知らない。しかし、自分はその教授の結論づけ方に憤りを覚えた。「これからスタートする人間に対し、リタイヤメントの話をここですべきなのか」と。
自分が今まで聞いた、「大企業とベンチャー」の話でもっとも酷い結論であり、もっとも言ってはいけない人間に対して言ったなと思った。
4,50 代の人間が、酒場で話すネタならまだしも。教室に集められたのは 20 歳前半の若者であり。そこで、曇りきった眼をしたオッサンが「人生の逃げ」について説いたわけである。
日本の癌細胞が細胞分裂を行う瞬間を目撃したような気分である。
自己の利益の為に組織を利用する、ある種の老害的な行為を是とする人間が、若者に対して影響を及ぼすポジションに立っている事が非常に悲しい。
っといった内容をその偉い教授に対して言いたい気持ちをグッと堪え。大人の階段を一歩登った気になる。
ブロックデバイスに対する I/O リクエストは、通常ファイルシステムのインターフェイスを介して発行される。ここでは、GNU/Linux (以下、Linux) において低レベルファイルシステムが提供するインターフェイスを用いずに行う、ブロック I/O リクエストの仕組みを紹介する。
○ はじめに
ユーザプログラムから、ファイルシステムを用いずにデバイスファイルに対する I/O をプログラマブルに行う事は非常に簡単である。これは、Linux カーネルがデバイスファイルという形で、ファイルシステムが扱えるように構造を抽象化しているからである。逆を言うと、VFS のインターフェイスはユーザによって操作される事を前提としている為、カーネルの都合でデバイスを扱う為には、話が複雑になる。前回書いた記事にも共通する事が言える。
ここでの目的は、ファイルシステムの力を借りずに、カーネルに組み込んだ自前の処理関数によってブロック I/O を発行する事である。ファイルシステムの力を借りる事ができない理由は、上述したように処理の発信元がカーネル側にある事に起因する。
ブロックデバイスに対する I/O 処理は、一般的に Linux カーネルが提供するデバイスファイルを通して行われる。デバイスファイルに対するファイル操作処理は VFS インターフェイスを通し、bdev 特殊ファイルシステムによって処理される。
○ Linux カーネルによるブロック I/O
まずは、システム起動後からブロックデバイス初期化までの大まかな流れを追い、処理の範囲を絞りこむ。
システムを起動してから、デバイスをマウントし、ファイルシステムから参照されるまでの流れはおおよそ次のようになっている。
システム起動後、Linux カーネルは PCI デバイスを捜査し、k オブジェクトのツリーを生成する。同時にブロックデバイスに対して block_device オブジェクトを生成し、all_bdevs が参照するリストに登録される。そして、デバイスファイルという形でデバイス情報がファイルシステムに対して提供される。最後に、/etc/fstab が参照され、各デバイスが指定されたファイルシステムでマウント処理される。
ここでのミソは 2 つ。各デバイスは Linux によって、デバイスファイルという形で提供されるという事と、マウント処理されてはじめて VFS からデバイスに対してデータを読み書きする事ができるという事。
次に、このデバイスファイルに対するファイルオープンの処理の流れと内部的な処理について見てゆく。
デバイスファイルに対して open システムコールが発行されると、パス名検索を行った後、生成した nameidata オブジェクトを nameidata_to_filp() 関数に渡す。同関数では、パス名検索の結果取得した nameidata オブジェクトから対象ファイルのディレクトリエントリの情報を取り出し、ここから __dentry_open() を呼び出す。
ここまでの処理は、対象ファイルの inode 情報を取り出す常套手段で、各種ファイルシステム共通の処理になる。ここから、ファイルシステムのファイル操作の共通インターフェイスを定義したデータ構造 file_operations オブジェクトを取得し、open() メソッドを呼び出す。マウントされていないブロックデバイスは、bdev 特殊ファイルシステムによって定義されるスーパーブロックを持ち、デバイスファイルに対する読み書きによって叩かれるインターフェイスの実態は、この bdev ファイルシステムが定義する処理にある。これらの処理は fs/blocks.c で定義される。
重要なのは、どのように Linux がブロック I/O を発行するかという事である。
Linux はファイルシステムからの I/O 処理の要求を submit_bio() という関数で一手に引き受けている。ここに処理の対象となるブロックデバイスのデータ構造 block_device オブジェクトと bio オブジェクト 及び I/O の範囲を個別に指定した bio_vec オブジェクトのリンクを渡す事でブロック I/O が発行される。
まずは、処理の対象となるブロックデバイスの block_device オブジェクトの取得方法について。
bdev ファイルシステムのスーパーブロックが提供する inode オペレーションの .alloc_inode() メソッドの本体は bdev_alloc_inode() [fs/block_dev.c] で定義される。ここでは、bdev_inode オブジェクトを生成し、inode メンバを返している。bdev_inode のデータ構造は struct inode * の他に、struct block_device * を持つ。これは、bdev ファイルシステムで inode を作成した時に、block_device も同時に作成される。
なので、デバイスファイルの inode さえ取得できれば、オブジェクトのメンバのアドレスからオブジェクト本体のアドレスを逆算する container_of() などのマクロによって block_device オブジェクトを取得、またはその逆ができる。これらの操作を BDEV_I() や I_BDEV() マクロによって内部的に行っている。
Linux は上述したような処理を行う関数を外部に対して提供している。それが lookup_bdev() になる。
ブロックデバイスの操作が submit_bio() にて行われているわけだから、block_device オブジェクトを取得したら、bio オブジェクトを生成・初期化して submit_bio() を呼び出せば I/O 操作を行ってくれるように思うかもしれないが、そうは問屋が卸さない。Linux のブロックデバイスサブシステムに対して I/O 要求を発行する際にディスクを表すデータ構造の gendisk オブジェクトを参照し request_queue オブジェクトを生成して、デバイスドライバに処理を委託する。
通常、デバイスのマウント時に gendisk オブジェクトは生成されるが、特定のファイルシステムを持たないこの状況で submit_bio() を呼び出すと、generic_make_request() 関数で無効なアドレスを参照して例外ハンドラが呼び出されるか、予測不可能な処理が起こる。
この段階では、デバイスドライバの初期化が行われているだけで、ディスクオブジェクトなどの I/O ブロック層におけるオブジェクト郡は生成されていないようである。
この為、対象デバイスに対するブロックデバイスサブシステムに関連するデータ構造の生成・初期化も自前で行わなければならない。これを行う為に、デバイスファイルに対してカーネル側でファイルオープン処理を行う。デバイスファイルに対して、ファイルオープンを行うと、対象デバイスの bdev に関する I/O ブロック層の各種オブジェクトを生成してくれる。
そして、bio オブジェクトを生成し、書き込みを行う場所 (bi_sector) 等の設定を行う。又、block I/O を行う際に指定するバッファ領域としてページディスクリプタを指定する。なので、kmalloc() などによるスラブキャッシュからバッファ領域を取得するのではなく、直接ページアロケータにページの取得要求を出す。ページの取得等のページ操作については、ソースを見てもらえれば分かると思う。
○ サンプルプログラムソース
http://dev.ariel-networks.com/Members/ohyama/stuff/onix_blk.c/download
○ 注意
多分誰もいないと思うが。ユーザ権限でデバイスのファイルシステム壊すことが出来るので、これを使う際には、間違っても重要なデータが入っているデバイスに対して行うべきではない。どうでもいい USB メモリか何かで試して貰いたい。
【義憤にかられた瞬間：とある大学教授のお話】
新たな年度が始まり、今年度から学部 4 年となった。この時期は、やれ就活だ、研究だ、進学だと騒がしく。特に年度始めはそれが顕著である。
今月始め、同学年の学生を集めたガイダンスが開かれた。
しばらく事務的な話が続いた。窓に映る桜並木と春の暖かさが眠気を呼び寄せ、気がつくと教室は静まり、壇上には見慣れた偉い教授が立っていた。そして就活に関する話をはじめられた。
そこでは、昨年度の就職実績 (?) や、おもな就職先の企業の話をした後、大学院への進学の話に移った。話をはじめてから 5 分程度の時間が経過し、ようやくエンジンがかかってきたのか声に熱が入りはじめ、「就職するなら大企業かベンチャーか」という話になった。
教授は「まぁ、いろいろな考えを持った方がおられるでしょうが。」と前置きをした後、「絶対。大企業の方がいいです。」と言い切った。
相手は学者なので、ここから話の根拠が展開される。教授は始めにこう結論づけた。「なんといっても、生涯賃金が違います。」
ここまでは、よく耳にする話である。話を聞いている周りの学生達は退屈そうな目で教授を見ていたに違いない。
しかし教授の話はここで終わらない。教授は次にこう言い放った。「昨今、中央省庁の官僚の天下りが問題視されています。ですが、民間企業では当り前の事です。」そして、具体的な企業名と役職を挙げ、過去に子会社の社長やら重役やらに就任した話を繰り広げ、生涯設計を検討するなら大企業に入る事はひとつの大きな鍵になると結論づけた。
教授が仰りたかった事は、つまるところ『大企業の本体に入れば、生涯賃金は一般的に中小企業よりも高いし、定年過ぎても天下りやらを行え、人生安泰』という事であろう。
これには、驚いた。自分自身、この問に関する答えは持ち合わせていないし、その行為自体が正しいか間違っているかを述べるだけの根拠を持っていないし、個別のケースに対して意見できる程事情も知らない。しかし、自分はその教授の結論づけ方に憤りを覚えた。「これからスタートする人間に対し、リタイヤメントの話をここですべきなのか」と。
自分が今まで聞いた、「大企業とベンチャー」の話でもっとも酷い結論であり、もっとも言ってはいけない人間に対して言ったなと思った。
4,50 代の人間が、酒場で話すネタならまだしも。教室に集められたのは 20 歳前半の若者であり。そこで、曇りきった眼をしたオッサンが「人生の逃げ」について説いたわけである。
日本の癌細胞が細胞分裂を行う瞬間を目撃したような気分である。
自己の利益の為に組織を利用する、ある種の老害的な行為を是とする人間が、若者に対して影響を及ぼすポジションに立っている事が非常に悲しい。
っといった内容をその偉い教授に対して言いたい気持ちをグッと堪え。大人の階段を一歩登った気になる。
非公式、未踏開発レポート (その1) [Linux]
未踏云々といっても、書く内容は格別普段と変わるわけではない。いつものように Linux をいじる話をする。
およそここ 2 ヶ月間、Linux ばかり相手にしてきた。ゼロからカーネルを作るのは格別に楽しいが。既に (ほぼ) 出来上がったカーネルをいじるのもまた楽しい。
今回は、Linux におけるページキャッシュ関連の話をする。かつてもページキャッシュの話を何回かに分けて話をしたが、あれはページキャッシュの概論に過ぎない。今回話す内容は、限定的なシチュエーションにおけるページキャッシュの振舞い等についての話が主である。
前回、カーネル空間からファイルオープンするという話をした。
未踏に関連した話なのだが。現在システムが発行している I/O 要求は、どの (時間) タイミングでどこ (場所) に対してどのような (方向) 処理を行っているのかを知りたかったので、あのような話をした。
ただし、取得したこれらの情報 (以下、I/O パターン) を保存する為に、Linux が通常利用しているインターフェイスを通してストーレジに保存すると、データにノイズが入り、また別のストレージインターフェイスを作るのも手間なので、klog が行っているように、一端カーネル空間のバッファにデータを保存し、ユーザプログラムによってこれを取得するコールゲートをカーネル側で提供してやり、それをネットワーク経由で別のマシン外に出す事で、純粋な I/O パターンを取得できる。
この仕組は既に完成しており、Linux 上で滞りなく動作している。作成したソースはこちら。
http://dev.ariel-networks.com/Members/ohyama/stuff/onix.c/download
http://dev.ariel-networks.com/Members/ohyama/stuff/onix.h/download
onix.c を fs 配下に、onix.h を適当に参照できる場所にそれぞれ置き、arch/xxx/kernel/syscall_table.S に onix.c で定義したサービスルーチン 3 つを登録し、onix_do_writelog() を submit_bh() から呼び出すようにすれば動くはず。もし、試してくれた玄人の中で、そでも動かなかった場合、メールを送ってもらえれば多分対応する。
作成したカーネルに対して、web サービスに対して不規則にリクエストを投げた時に発生する I/O パターンと、MTA に対してメールを送った時に発生する I/O パターンをそれぞれ取得し、考察してみる。
結果の一部を次のように示す。ちなみにフォーマットは、
[システム時間 (s)] ["システム時間" からの経過時間 (ns)] [I/O の方向] [LBA モードにおけるセクタ番号]
となっている。
機能を絞った限定的な環境で I/O パターンの取得を行ったが、それでも対象の I/O 要求が上位レイヤでどのような抽象構造 (ファイル) に対応した処理なのかがわかれば親切である。
幸い、大学は春休みであるので時間はたっぷりある。仮の配属をされたばかりの研究室の知人は就職活動に明け暮れているが。いまの御時世、自分が所属しているような三流大学では就職は難しいのではないかと、思ったり思わなかったり。
などというわけで、暇に任せて、I/O 処理がどのファイルに対する処理なのかを知られる処理を追加した。
ここでは、バッファヘッドから、バッファヘッドが存在するページを参照し、対象ページがページキャッシュに存在する時、キャッシュを構成しているファイルの名前を表示する。
ちなみに、有効なページであり、かつページキャッシュに存在していないページは、カーネルのスラブキャッシュに属している物か、プロセスの仮想メモリ空間にマッピングされたものである。後者のページを特に「無名ページ」と呼ぶ。カーネルのコメントにもこれを「anonymous page」と書いている。
次に、これを調べる為の具体的な実装の話をする。
まずは、バッファヘッドから、自身が存在しているページを取得する。そして、対象ページがページキャッシュのデータであるか無名ページなのかを調べる。ページディスクリプタの mapping メンバは、ページがページキャッシュに属している場合、アドレス空間オブジェクトを参照する。逆に、無名ページである場合には、プロセスのメモリリージョンの元締めでる anon_vma オブジェクトを参照する。
今回は、ページを確保しているファイルの名前を調べる仕組みの話なので、無名ページは扱っていないが。メモリリージョンからはプロセスのメモリディスクリプタが参照できる為、これを辿れば I/O を発行したプロセスを調べる事もできる (だろう)。
さて、ページの所属判定だが。mapping メンバの下位 1 ビットでこれを判定している。具体的には、onix_check_page_mapping() でこれを行っている。これによって、対象ページがページキャッシュに属している事がわかり、所属しているページキャッシュのアドレス空間オブジェクトを取得できる。
次に、ページキャッシュの所有者。つまりファイルの情報を取得する。ext2 や ext3 においてファイルはディスク上で inode というデータ構造で管理されている。VFS ではこれを inode というデータ構造で一般化している。ここでは、区別の為に前者をディスク inode と呼び、後者を単に inode と呼ぶ。
inode は、アドレス空間オブジェクトの host メンバから参照ができる。Linux では VFS 上でファイルのパス名情報を管理する為に dentry というデータ構造を用意している。
この inode と dentry の関係。つまり、ファイルの実体とパス名の関連付けは ext2 の場合、O_CREAT フラグ付でファイルオープンした際に実行される、ファイルオブジェクトの create メソッドの実体である ext2_create() 関数から参照される d_instantiate() 関数で行われる。
ここでは、inode オブジェクトの i_dentry リストにディレクトリエントリの d_alias を追加している。
さて。改めて作成したこのカーネルを実際に動かしてみると、アドレス空間オブジェクトが参照する inode が存在しない事がある。
無名ページでもスワップアウトされたページでもないページで、所有者の無いページ。通常、ページキャッシュの所有者はファイル、即ち inode であり、ここではそれが無いという事になる。
ファイルをマップしないページキャッシュとは一体何か。これの正体が全くわからず、バイト先企業であるアリエルにいる賢人に相談する。
賢人に対して「ページキャッシュ中のアドレス空間オブジェクトが inode を参照しないケースがあるが、これは一体どうゆう事なのか」と問うた。
すると恐るべき事に、賢人はこれだけを聞いて、瞬時に「mmap に ファイルを対象としないマッピング処理が存在する」とそっと答えた。
自分が無能すぎるのか、賢人が凄すぎるのか。とにかく、凄まじい洞察力である。
軽くヘコんだ後、オンラインマニュアルをよく読むと、MAP_ANONYMOUS フラグを指定する事でファイルディスクリプタが無視されるらしい。
実際に、mmap システムコールのサービスルーチンを見ると、ファイルオブジェクトの取得を行わずに do_mmap_pgoff() を呼び出し、メモリリージョンの予約を行っている。この処理の詳細については次回以降に話をする。
およそここ 2 ヶ月間、Linux ばかり相手にしてきた。ゼロからカーネルを作るのは格別に楽しいが。既に (ほぼ) 出来上がったカーネルをいじるのもまた楽しい。
今回は、Linux におけるページキャッシュ関連の話をする。かつてもページキャッシュの話を何回かに分けて話をしたが、あれはページキャッシュの概論に過ぎない。今回話す内容は、限定的なシチュエーションにおけるページキャッシュの振舞い等についての話が主である。
前回、カーネル空間からファイルオープンするという話をした。
未踏に関連した話なのだが。現在システムが発行している I/O 要求は、どの (時間) タイミングでどこ (場所) に対してどのような (方向) 処理を行っているのかを知りたかったので、あのような話をした。
ただし、取得したこれらの情報 (以下、I/O パターン) を保存する為に、Linux が通常利用しているインターフェイスを通してストーレジに保存すると、データにノイズが入り、また別のストレージインターフェイスを作るのも手間なので、klog が行っているように、一端カーネル空間のバッファにデータを保存し、ユーザプログラムによってこれを取得するコールゲートをカーネル側で提供してやり、それをネットワーク経由で別のマシン外に出す事で、純粋な I/O パターンを取得できる。
この仕組は既に完成しており、Linux 上で滞りなく動作している。作成したソースはこちら。
http://dev.ariel-networks.com/Members/ohyama/stuff/onix.c/download
http://dev.ariel-networks.com/Members/ohyama/stuff/onix.h/download
onix.c を fs 配下に、onix.h を適当に参照できる場所にそれぞれ置き、arch/xxx/kernel/syscall_table.S に onix.c で定義したサービスルーチン 3 つを登録し、onix_do_writelog() を submit_bh() から呼び出すようにすれば動くはず。もし、試してくれた玄人の中で、そでも動かなかった場合、メールを送ってもらえれば多分対応する。
作成したカーネルに対して、web サービスに対して不規則にリクエストを投げた時に発生する I/O パターンと、MTA に対してメールを送った時に発生する I/O パターンをそれぞれ取得し、考察してみる。
結果の一部を次のように示す。ちなみにフォーマットは、
[システム時間 (s)] ["システム時間" からの経過時間 (ns)] [I/O の方向] [LBA モードにおけるセクタ番号]
となっている。
49a04007|31066169|0|184a808
49a04007|31fa8952|0|185004f
49a04007|32749d43|0|1857000
49a04007|32eeb138|0|19a8061
49a04007|3368c52c|0|19b5bf1
49a04007|33a5cf26|0|19a8063
49a04007|33a5cf26|0|19b5da3
49a04007|33e2d920|0|19a8064
49a04007|33e2d920|0|19b5df0
49a04008|9ecf167|0|19b803e
49a04008|a670558|0|19c2358
49a04008|aa40f52|0|19b8061
49a04008|ae1194c|0|19c3808
49a04008|b1e2346|0|19c3809
機能を絞った限定的な環境で I/O パターンの取得を行ったが、それでも対象の I/O 要求が上位レイヤでどのような抽象構造 (ファイル) に対応した処理なのかがわかれば親切である。
幸い、大学は春休みであるので時間はたっぷりある。仮の配属をされたばかりの研究室の知人は就職活動に明け暮れているが。いまの御時世、自分が所属しているような三流大学では就職は難しいのではないかと、思ったり思わなかったり。
などというわけで、暇に任せて、I/O 処理がどのファイルに対する処理なのかを知られる処理を追加した。
ここでは、バッファヘッドから、バッファヘッドが存在するページを参照し、対象ページがページキャッシュに存在する時、キャッシュを構成しているファイルの名前を表示する。
ちなみに、有効なページであり、かつページキャッシュに存在していないページは、カーネルのスラブキャッシュに属している物か、プロセスの仮想メモリ空間にマッピングされたものである。後者のページを特に「無名ページ」と呼ぶ。カーネルのコメントにもこれを「anonymous page」と書いている。
次に、これを調べる為の具体的な実装の話をする。
まずは、バッファヘッドから、自身が存在しているページを取得する。そして、対象ページがページキャッシュのデータであるか無名ページなのかを調べる。ページディスクリプタの mapping メンバは、ページがページキャッシュに属している場合、アドレス空間オブジェクトを参照する。逆に、無名ページである場合には、プロセスのメモリリージョンの元締めでる anon_vma オブジェクトを参照する。
今回は、ページを確保しているファイルの名前を調べる仕組みの話なので、無名ページは扱っていないが。メモリリージョンからはプロセスのメモリディスクリプタが参照できる為、これを辿れば I/O を発行したプロセスを調べる事もできる (だろう)。
さて、ページの所属判定だが。mapping メンバの下位 1 ビットでこれを判定している。具体的には、onix_check_page_mapping() でこれを行っている。これによって、対象ページがページキャッシュに属している事がわかり、所属しているページキャッシュのアドレス空間オブジェクトを取得できる。
次に、ページキャッシュの所有者。つまりファイルの情報を取得する。ext2 や ext3 においてファイルはディスク上で inode というデータ構造で管理されている。VFS ではこれを inode というデータ構造で一般化している。ここでは、区別の為に前者をディスク inode と呼び、後者を単に inode と呼ぶ。
inode は、アドレス空間オブジェクトの host メンバから参照ができる。Linux では VFS 上でファイルのパス名情報を管理する為に dentry というデータ構造を用意している。
この inode と dentry の関係。つまり、ファイルの実体とパス名の関連付けは ext2 の場合、O_CREAT フラグ付でファイルオープンした際に実行される、ファイルオブジェクトの create メソッドの実体である ext2_create() 関数から参照される d_instantiate() 関数で行われる。
ここでは、inode オブジェクトの i_dentry リストにディレクトリエントリの d_alias を追加している。
さて。改めて作成したこのカーネルを実際に動かしてみると、アドレス空間オブジェクトが参照する inode が存在しない事がある。
無名ページでもスワップアウトされたページでもないページで、所有者の無いページ。通常、ページキャッシュの所有者はファイル、即ち inode であり、ここではそれが無いという事になる。
ファイルをマップしないページキャッシュとは一体何か。これの正体が全くわからず、バイト先企業であるアリエルにいる賢人に相談する。
賢人に対して「ページキャッシュ中のアドレス空間オブジェクトが inode を参照しないケースがあるが、これは一体どうゆう事なのか」と問うた。
すると恐るべき事に、賢人はこれだけを聞いて、瞬時に「mmap に ファイルを対象としないマッピング処理が存在する」とそっと答えた。
自分が無能すぎるのか、賢人が凄すぎるのか。とにかく、凄まじい洞察力である。
軽くヘコんだ後、オンラインマニュアルをよく読むと、MAP_ANONYMOUS フラグを指定する事でファイルディスクリプタが無視されるらしい。
実際に、mmap システムコールのサービスルーチンを見ると、ファイルオブジェクトの取得を行わずに do_mmap_pgoff() を呼び出し、メモリリージョンの予約を行っている。この処理の詳細については次回以降に話をする。
