前回は I/O ブロックレイヤと I/O スケジューラの違いとそれぞれの役割について簡単に示した。今回は I/O ブロックレイヤの下位レベルに存在する I/O スケジューラについて本格的に見てゆく。
　具体的には、カーネルモジュールである I/O スケジューラが GNU/Linux に対して提供しているインターフェイスについて調べる。そして、そのインターフェイスの実装について CFQ I/O スケジューラの実装を調べ、I/O スケジューラの具体的な処理内容について調べる。

　では I/O スケジューラが提供するインターフェイスについて、まずは elevator_merge_fn メソッドについてドキュメントから調べる。
　前回、そして前々回。 request_queue で表されるキューに bio オブジェクトを挿入する為に、キューの make_request_fn メソッドが呼ばれるという話をした。キュー自体がブロックデバイス固有のオブジェクトである為、make_request_fn メソッド自体もブロックデバイス固有であるが、ide-hdd ブロックデバイスを含む多くのブロックデバイスドライバでは、request_queue の make_request_fn メソッドの実体に __make_request を設定しているという話をした。そして、I/O スケジューラの elevator_merge_fn メソッドは、__make_request() 等から呼び出される elv_merge() から実行される。
　I/O ブロックレイヤ処理の elv_merge() は、ざっくり説明すると対象の bio オブジェクトを併合する I/O ブロックレイヤの内部オブジェクトである request オブジェクトのうち、最適なものを選択して呼び出し元に request オブジェクトを返すというもの。そこから elevator_merge_fn メソッドが呼ばれている。
　では、肝心の elevator_merge_fn メソッドとは、何をするモノなのか。
　カーネルドキュメント [1] の内容は非常に素っ気ない。わずかに１行、次のように説明がされている。

　elevator_merge_fn        called to query requests for merge with a bio

　これをそのまま解釈すると。
　「I/O 要求を bio オブジェクトと併合する為の処理を I/O スケジューラに行わせるためにこいつが呼び出される」
　となる。このたった１行だけでは、中身で具体的にどんな処理を行っているのか見えてこないので、CFQ I/O スケジューラの実装を調べて、elevator_merge_fn メソッドの仕事について学習する。

　まずは、CFQ I/O スケジューラを読む上で登場するデータ構造について見て行く。
　elevator_queue 型 [include/linux/elevator.h] は、I/O ブロックレイヤから見た I/O スケジューラの中核を成すデータ構造となる。各リクエストキューの elevator メンバから参照される。
　elevator_type 型 [include/linux/elevator.h] は I/O スケジューラ自体のデータ構造。つまりシステムに存在している I/O スケジューラ固有の情報を表すデータ構造である。なので各 I/O スケジューラ毎にオブジェクトが存在する。
　cfq_data 型 [block/cfq_iosched.c] は CFQ の核となるデータ構造。ブロックデバイス毎にオブジェクトが存在する。
　cfq_queue 型 [block/cfq_iosched.c] は CFQ 内部でのリクエストキュー。I/O スケジューラにおけるリクエストの遅延とソートに用いられるものだろう。I/O スケジューラレベルにおける I/O の遅延については、前回記事を参照されたし。
　io_context 型 [include/linux/blkdev.h] は、プロセスの I/O に関するデータ構造。プロセス毎に io_context オブジェクトが存在し、task_struct 型オブジェクトの io_context メンバから参照される。
　cfq_io_context 型 [include/linux/blkdev.h] は、io_context の cic_root メンバをルートとする rb_tree から参照されるデータ構造。これを見ると、一つのプロセスに対して複数のオブジェクトが存在するようである。そして内部では、２個の cfq_queue オブジェクトを持っている。この２種類の CFQ の内部リクエストキューについては、CFQ の実装を調べる段階で話をする。

　区切りが良いので elevator_merge_fn メソッドの CFQ での実装については次回に話をする。

　今回学習した内容は次の２つ。
　(1) GNU/Linux I/O スケジューラの elevator_merge_fn メソッドの概要
　(2) CFQ I/O スケジューラにおけるデータ構造

[1] Documentation/block/biodoc.txt