今回は、前回に紹介した kthreadd の初期化処理内部について紹介する。

　kthreadd は文字どおり、カーネルスレッド処理を行うために常駐するプロセス。
　内部、kthread_create_list を監視し、リストにエントリが追加されたら、リストから thread_struct オブジェクトを抽出し、create_kthread() を呼び出す。そして、create_kthread() から kernel_thread() を呼び出し、新しいプロセスが fork される。
　新たなカーネルスレッドを生成する場合には、kthread_create() によって行われるが。内部の処理が一風変わっている。以下が、v2.6.24 の kthread_create のコードである。

struct task_struct *kthread_create(int (*threadfn)(void *data),
　　　　   void *data,
　　　　   const char namefmt[],
　　　　   ...)
{
　struct kthread_create_info create;

　create.threadfn = threadfn;
　create.data = data;
　init_completion(&create.started);
　init_completion(&create.done);

　spin_lock(&kthread_create_lock);
　list_add_tail(&create.list, &kthread_create_list);
　wake_up_process(kthreadd_task);
　spin_unlock(&kthread_create_lock);

　wait_for_completion(&create.done);

　if (!IS_ERR(create.result)) {
　　va_list args;
　　va_start(args, namefmt);
　　vsnprintf(create.result->comm, sizeof(create.result->comm),
　　　  namefmt, args);
　　va_end(args);
　}
　return create.result;
}

　
　この内部では、ローカル変数として生成するカーネルスレッドの thread_create_info オブジェクトを生成し、kthread_create_list リストに追加する。直後に kthreadd を起こす。そして、対象のカーネルスレッドが生成されるまで待ち受ける。
　この関数内部では、いろいろ面白い事をやっている。まずはローカル変数の共有。
　kthread_create() 内部で宣言された kthread_create_info 型オブジェクトの create は、呼び出し元のカーネルのスタック領域に格納される。カーネルスタックは、kthrad_info オブジェクトの中に埋め込まれている。つまり変数 create は、カーネル空間に配置されている。カーネルから見たアドレス空間は単体なので、他のスレッドから直接参照可能となっている。
　そのため、kthread_create() で kthread_create_list のグローバルリストに追加した kthread_create_info 型ローカル変数 create を、kthreadd から参照している。
　このような共有アクセスをする際に問題になるのが排他制御である。ここでは、セマフォではなく complete という仕組みを使っている。これはずいぶん古い仕組みらしく、v2.4 系から既にあるものらしい。
　これについては、古いだけあってたくさんドキュメント [1] [2] [3] があるので、そっちを参照してもらいたい。簡単に言うと、wait_for_completion() で指定した事象が完了するまで、処理を待ち合わせるというもの。そして、その事象は init_completion() で宣言する。
　kthread_create() の処理では、kthreadd 側で呼び出した create_kthread() の処理が完了するまで待ち合わせている。
　ちなみに、kthreadd もカーネルスレッドであり、プロテクトモードに入った直後に呼び出される start_kernel() から生成される。この時点ではもちろん kthreadd は動作していないので、kthread_create() によるスレッド生成が不可能である。なので start_kernel() では、kthreadd を直接 kernel_thread() を呼び出して生成している。
　ならば、kthreadd なんか経由せずにみんな kernel_thread を直接呼び出せばよさそうだが。kthreadd では、新たなプロセスの子プロセスのリストやら、プロセスの属性情報の初期化を行っている。kthreadd が直接 kernel_thread のよって生成されているのは、これ自体は子プロセスの生成等の特殊な処理を行わない為である。

[1] http://www.makelinux.net/ldd3/chp-5-sect-4.shtml (英語だけど、とってもわかりやすい)
[2] http://www.ibm.com/developerworks/jp/linux/library/l-task-killable/
[3] http://sourceforge.jp/projects/linux-kernel-docs/wiki/1.7%E3%80%80%E4%BA%8B%E8%B1%A1%E3%81%AE%E5%BE%85%E3%81%A1%E5%90%88%E3%82%8F%E3%81%9B

　これまで低レベルファイルシステム (主に ext2) やらページキャッシュやらスワップ処理やらの学習を行ってきた。が。どれも汎用ブロックレイヤの上位の話である。実際の I/O 処理 (I/O スケジューラ) 周辺の話はしてこなかった (学習した記憶はあるのだが)。

  I/O スケジューラの話題を中心に、何回かに分けて GNU/Linux の実装を学習してゆく。初回は、汎用ブロックレイヤのデータ構造と I/O 発行の概要、そして GNU/Linux のソースのアウトラインを見てゆく。

　最初に、登場するデータ構造について見て行く。各データ構造の細かな役割について詳しく見ないで、どんなものなのかを簡単に知っておく。
　まずは request_queue [include/linux/blkdev.h] 構造体について。こいつは各ブロックデバイスについて一つ用意されているデータ構造であり、この中にリクエストキューが入っている。
　次が request [include/linux/blkdev.h] 構造体。こいつは汎用ブロックレイヤにおいて発行される I/O リクエストを表すデータ構造である。一個以上の bio 型オブジェクトから構成される。そして重要なポイントが、包含する bio オブジェクト群は I/O スケジューラによって動的に変更される事である。これが I/O スケジューラ本体の内部処理になる。これについては次回以降で詳しく見てゆく。
　汎用ブロックレイヤの内部でも細かなレイヤ構造が存在する。上位の汎用ブロックレイヤからは、受け取った bio リクエストを request_queue に格納して I/O を発行するように下のレイヤ (I/O スケジューラ) に委託する。上述したデータ構造は、上位の汎用ブロックレイヤで登場するデータ構造である。上位と下位のレイヤの隔たりについては後述する。
　次に、汎用ブロックレイヤの内部処理について詳しくみてゆく。なお、以下で述べる処理は上位部分の処理になる。I/O スケジューラ本体の処理については、次回以降で詳しくみてゆく。

　submit_bio() によって発行された bio リクエストは __generic_make_request() によって処理される。
　内部ではまず、渡されたリクエストがデバイスの容量を越えていないかというチェックを行い、bdev_get_queue() を呼び出して、リクエストを発行するブロックデバイスの request_queue オブジェクトを取得する。
　つぎに blk_partition_remap() を実行する。ここでは、I/O リクエストが対象としている物理アドレスに対して、パーティションによるオフセットの補正を行っている。
　ファイルシステムなどの上位レベルでは、ファイルを構成するブロックデータの物理アドレスは所属しているパーティションの先頭からオフセットで表される。しかし、このアドレスはブロックデバイスの絶対アドレスとは異なる。パーティションの物理アドレスのゼロ地点以前にはパーティションテーブルがあり、そして MBR が存在する。I/O を発行する場合にはその物理アドレスの補正をおこなってやる必要がある。blk_partition_remap() 内部では gendisk オブジェクトを取得して、当該 I/O が対象とする物理アドレスのゼロ地点の補正を行っている。
　そして __generic_make_request() では最後に、request_queue オブジェクトの make_request_fn メソッドを呼び出して、呼び出し元に帰る。
　先に述べた汎用ブロックレイヤの上位と下位の区切りがこの部分になる。

　__generic_make_request() では request_queue オブジェクトの make_request_fn メソッドを呼び出し、submit_bio() から受け取った bio オブジェクトを request オブジェクトに併合して、ブロックデバイスに対して I/O を発行するよう I/O スケジューラに依頼する。
　HDD を含めた多くの request_queue では make_request_fn メソッドの呼び出しによって __make_request() 関数を実行する。
　データ構造にコールバックメソッドを据えておいて、汎用関数を呼び出す理由は何か？ それは GNU/Linux がブロック I/O の発行形態の多様性を認めている為である。

　GNU/Linux の I/O スケジューラはブート時のカーネルパラメータ elevator によって設定する事ができる。設定が行われない場合、デフォルトの I/O スケジューラ (CFQ) が設定される。
　しかし、システムに搭載されている全てのデバイスに対して、共通の I/O スケジューラを用いる事が適切でない場合がある。例えば、HDD と他の特殊なブロックデバイスが同一システムに混成されている場合など。
　このようなケースでは、特定のブロックデバイスに対する I/O リクエストは独自の I/O スケジューラによって処理されるべき可能性がある。これに対応するために、デバイス固有の I/O スケジューラを持てるように make_request_fn メソッドによって、処理を切り離している。

　まとめとして、今回学習した事は次の 3 つ。

　(1) request_queue と request 構造体
　(2) I/O の処理の流れ (request_queue に bio が入れられるまで)
　(3) GNU/Linux のブロック I/O の多様化設計

　次回は、汎用ブロックレイヤの下位 (I/O スケジューラ本体とその周辺) の処理について詳しく見て行く。

　前回は I/O ブロックレイヤの上位レベルの話をした。I/O ブロックレイヤでのデータ構造について調べ、実際の処理についてソースを追っていった。そして bio オブジェクトを request_queue に併合する処理がブロックデバイス毎に行える設計についての話をした。
　今回は I/O ブロックレイヤと I/O スケジューラの関連を簡単に調べ、そもそも I/O スケジューラとは何ぞのもので、どんな処理をするものなのかという事を特に詳しく見てゆく。
　もちろん、これについても今回一回の話で I/O スケジューラの何たるかについて全てを理解できるわけではないので、複数回に分けて話をするつもりだ。

　まずは、前回の続き ( __make_generic_request() で、request_queue オブジェクトに bio オブジェクトを併合する処理 ( make_request_fn メソッド) の続き) について見てゆく。
　HDD を含む blk_init_queue() を呼び出す多くのを含むドライバでは request_queue オブジェクトの make_request_fn メソッドによって __make_request() が実行される。
　__make_request() では、何度も言っているように request_queue オブジェクトの最適な場所に bio オブジェクトの併合を行う。その「最適」の判断を行うのが I/O スケジューラになる。

　以下では、__make_request() の中身の処理について少し詳しく見てみる。
　まずは bio_sectors によって引数で渡された bio オブジェクトが対象としているブロックデバイスのセクタ番号を取得する。次に、blk_queue_bounce() を呼び出し、バウンスバッファが必要かどうかを判定する。
　教科書的な話になるが。一般的にアーキテクチャでは CPU に接続された各コンポーネント (メモリや (PCI 等の) デバイスコントローラなど) は共通のバスを介してデータ通信を行っている。
　つまり、メモリに乗っかっているデータを CPU に転送する場合も、デバイスに転送する場合も、同じラインにデータが乗っかる。しかし、デバイスないしデバイスコントローラによっては、高位のアドレス領域のアドレスラインが接続されていないケースがある。
　これに対応するために、必要に応じて bio のバッファ領域が高位アドレスにあるバッファは低位アドレス (仮想メモリ上のカーネル空間の上位 3/4 ) 領域のバッファを介して転送される。
　GNU/Linux では、この低位アドレス領域のバッファをバウンスバッファと読んでいる。
　そして __make_request() では次に elv_merge() を呼び出し、汎用 I/O スケジューラの処理に bio オブジェクトをマージする request オブジェクトの問い合わせを行う。
　このように。I/O ブロックレイヤの下位レベルに I/O スケジューラの処理が存在している事がわかる。そして、elv_merge() の処理は汎用の I/O スケジューラの処理で、この内部では各 I/O スケジューラのメソッドを呼び出す。GNU/Linux では、elv_merge() といった処理を含めたここまでの処理を I/O ブロックレイヤと呼んでいる。

　では I/O ブロックレイヤと I/O スケジューラの役割はそれぞれ何か。
　I/O ブロックレイヤでは、上位レイヤに対して request_queue オブジェクトで表されるキューというデータ構造を提供し、request で表される I/O 要求のソート、キューイング、そしてファイルシステムによらない I/O 要求処理を担当する。

　それでは狭義の I/O スケジューラとは何で、どんな処理を行うものなのか？
　多くを語らない GNU/Linux のマニュアル [1] によると、I/O スケジューラはファイルシステムによる I/O 要求処理とそれらの遅延を担当するらしい。
　ちなみにここで言っている "遅延" とは、キャッシュのことでは無い。カーネルの I/O 要求 (特に write 要求) の場合、特定の場所 (ブロックデバイスの物理アドレス) X に対する I/O 要求が到来してから近い将来、アドレス空間的に X に近い場所に対する I/O 要求がなされる可能性が高い事 (ファイルシステム I/O に空間的な局所性の特徴があること) が経験的にわかっている。
　そこで GNU/Linux の多くの I/O スケジューラは、非同期の write 要求処理が到来した場合に遅延し、積極的に要求の統合を行ってデバイスに対して発行する I/O の絶対数を減らす努力を行っている。
　また I/O スケジューラ自体は、I/O ブロックレイヤと異なりカーネルモジュールであり、動的に変更が可能である。

  カーネルモジュールである I/O スケジューラは GNU/Linux におけるひとつのクラスと考える事が出来る。次回は、I/O スケジューラの API について一通りみた後、CFQ I/O スケジューラにおける各 API の実装について詳しく見てゆく。

　最終的に、このテーマについて一連の投稿を終えた段階で、I/O スケジューラとは名んぞで、どんなモノか。そして、具体的にどんな処理を行うものなのかという事を一通り理解できている所まで持っていきたい。

　まとめとして、今回学習した事は次の 2 つ。

　(1) I/O の処理の流れ (make_request_fn メソッドが呼ばれてから elv_merge() 処理が呼ばれるまで)
　(2) I/O ブロックレイヤの役割と I/O スケジューラの役割

[1] Documentation/block/biodoc.txt

　前回は 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

　前回は I/O スケジューラの elevator_merge_fn メソッドの概要と、CFQ I/O スケジューラのコードを読むにあたって登場するデータ構造について話をした。
　今回は CFQ の elevator_merge_fn メソッドの実装について見て行く。CFQ I/O スケジューラは block/cfq_iosched.c に記載されている。

　CFQ における elevator_merge_fn メソッドの実体は cfq_merge() である。以下がそのコード
　尚、以下コードはひらメソッド [1] で見て行く。

　まずは elevator_queue オブジェクトの elevator_data メンバが参照している、各 I/O スケジューラ固有のデータ構造 (CFQ の場合は cfq_data 型) を取得し、これを引数として cfq_find_rq_fmerge() を呼び出す。
　次に cfq_find_rq_fmerge() では、カレントプロセスが持つ io_context オブジェクトを引数に cfq_cic_rb_lookup() を呼び出す。以下が cfq_cic_rb_lookup() のコードとなる。

static struct cfq_io_context *
cfq_cic_rb_lookup(struct cfq_data *cfqd, struct io_context *ioc)
{
  struct rb_node *n;
  struct cfq_io_context *cic;
  void *k, *key = cfqd;

  if (unlikely(!ioc))
    return NULL;

  /*
   * we maintain a last-hit cache, to avoid browsing over the tree
   */
  cic = ioc->ioc_data;
  if (cic && cic->key == cfqd)
    return cic;

restart:
  n = ioc->cic_root.rb_node;
  while (n) {
    cic = rb_entry(n, struct cfq_io_context, rb_node);
    /* ->key must be copied to avoid race with cfq_exit_queue() */
    k = cic->key;
    if (unlikely(!k)) {
      cfq_drop_dead_cic(ioc, cic);
      goto restart;
    }

    if (key < k)
      n = n->rb_left;
    else if (key > k)
      n = n->rb_right;
    else {
      ioc->ioc_data = cic;
      return cic;
    }
  }

  return NULL;
}

　ここではまず io_context オブジェクトの ioc_data メンバが参照する cfq_io_context オブジェクトを取り出す。
　取り出した cfq_io_context オブジェクトが存在し、且つ cfq_io_context オブジェクトの ioc_data メンバが elevator_queue オブジェクトの elevator_data メンバが参照する cfq_data オブジェクトだった場合には、対象の cfq_io_context オブジェクトを返す。
　そうでなければ restart ラベル以降の処理により io_context オブジェクトの cic_root メンバによって表される rb_tree から cfq_io_context オブジェクトを引っ張り出す。そして、取り出されたオブジェクトの ioc_data メンバに cfq_data を指定する。最後に、cfq_io_context オブジェクトを返す。
　ここで、cfq_cic_rb_lookup() の呼び出し元 (cfq_find_rq_fmerge() 関数) の処理について見る。以下が cfq_find_rq_fmerge() のコードである。

static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
{
  struct task_struct *tsk = current;
  struct cfq_io_context *cic;
  struct cfq_queue *cfqq;

  cic = cfq_cic_rb_lookup(cfqd, tsk->io_context);
  if (!cic)
    return NULL;

  cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
  if (cfqq) {
    sector_t sector = bio->bi_sector + bio_sectors(bio);

    return elv_rb_find(&cfqq->sort_list, sector);
  }

  return NULL;
}

　cfq_find_rq_fmerge() では cfq_cic_rb_lookup() によって、cfq_io_context オブジェクトを取得した後 cic_to_cfqq() を呼び出し cfq_queue オブジェクトを取得している。
　この内部では、cfq_io_context オブジェクトが保持する２個の cfq_queue オブジェクトのうち、bio 要求が READ ないし同期 I/O か否かによって選択される。
　前々回 に話したように、I/O ブロックレイヤにおいて WRITE 要求は積極的に遅延されるが、応答性能や可用性の観点から READ 要求や同期 I/O は、それらとは別に扱われる。CFQ I/O スケジューラ内部では、この種の I/O 要求の為のリクエストを他のリクエストと分けて溜めるキューを持っている。
　そして、cfq_io_context オブジェクトからいづれかの CFQ 内部リクエストキューを取得した後、bio オブジェクトが対象としている物理アドレスに bio オブジェクトのセクタサイズを加えた値を引数にして elv_rb_find() を呼び出す。
　elv_rb_find() 関数では単純に、引数に渡されたセクタ番号を I/O 要求の物理アドレスとする request オブジェクトを探し、これに合致するリクエストを返す処理を行う。
　つまり cfq_find_rq_fmerge() が何を行っているのかというと、elevator_merge_fn メソッドに渡された bio が行う I/O 要求の直後の物理アドレスを対象とする要求が CFQ の内部キューに存在するかどうかを調べている。そして、そのようなリクエストオブジェクトがキューに存在する場合には、呼び出し元 (cfq_merge() 関数) に elv_rb_find() によって取得したリクエストオブジェクトを返す。そのようなリクエストが無ければ NULL を返す。
　そして最後に I/O スケジューラの最上位の呼出元の処理について見てゆく。以下が cfq_merge() のコード。

static int cfq_merge(struct request_queue *q, struct request **req,
         struct bio *bio)
{
  struct cfq_data *cfqd = q->elevator->elevator_data;
  struct request *__rq;

  __rq = cfq_find_rq_fmerge(cfqd, bio);
  if (__rq && elv_rq_merge_ok(__rq, bio)) {
    *req = __rq;
    return ELEVATOR_FRONT_MERGE;
  }

  return ELEVATOR_NO_MERGE;
}

　cfq_find_rq_fmerge() によって、elevator_merge_fn に渡された bio の直後の物理アドレスを対象とする I/O 要求を含むリクエストオブジェクトを取得できた場合、bio はそのリクエストに併合されるべきである。
　なので cfq_merge() では、cfq_find_rq_fmerge() によって、リクエストオブジェクトが取得でき、且つ対象リクエストが併合可能である場合に、呼び出し元の I/O ブロックレイヤの関数に対して、併合すべきリクエストオブジェクトを渡す。そして、どの方向 (リクエストの前側 or 後側) から併合すべきなのかを戻り値によって教える。

　このように I/O スケジューラの elevator_merge_fn メソッドでは、引数で与えられた bio オブジェクトを既存のリクエストに対して併合する処理を行うわけではなく。あくまで、対象の bio オブジェクトが既存のリクエストに対して併合可能か否か。そして、併合可能なリクエストオブジェクトがある場合、どのリクエストオブジェクトに対して、どのように併合を行うべきなのかを教えてあげるという処理を行う。

　今回学習した事は次の２つ。
　(1) CFQ I/O スケジューラにおける elevator_merge_fn メソッドの実装
　(2) I/O スケジューラ一般における elevator_merge_fn メソッドの処理

[1] http://bestpc.s153.xrea.com/pukiwiki/pukiwiki.php?%A4%D2%A4%E9%A5%E1%A5%BD%A5%C3%A5%C9

　前回は CFQ I/O スケジューラにおける  elevator_merge_fn メソッドの実装を調べ、GNU/Linux の I/O スケジューラ一般における elevator_merge_fn メソッドの機能について調べた。
　今回も同様にして I/O スケジューラの elevator_merged_fn メソッドの機能について調べる。まずはドキュメントの内容を見てみる。
　カーネルドキュメントには elevator_merged_fn メソッドについて次のように記してある。

elevator_merged_fn　　called when a request in the scheduler has been
　　　　involved in a merge. It is used in the deadline
　　　　scheduler for example, to reposition the request
　　　　if its sorting order has changed.

　今回はそこそこな文量の説明が記載されている。どうやら、request をマージした後 I/O スケジューラ内部でソート順が変更された際に、キューの中のリクエストオブジェクトを再配置するらしい。
　何となく処理内容がわかったところで CFQ I/O スケジューラにおける実装について調べる。コードリーディングは前回同様にひらメソッド [1] で見てゆく。

　CFQ における elevator_merged_fn メソッドの実態は cfq_merged_request() 関数になる。ここではまず、RQ_CFQQ() マクロによって request オブジェクトの elevator_private2 メンバが参照する cfq_queue オブジェクトを取得して cfq_reposition_rq_rb() を呼び出す。

　そして cfq_reposition_rq_rb() では、cfq_add_rq_rb() を呼び出す。以下が cfq_add_rq_rb() のコードになる。

static void cfq_add_rq_rb(struct request *rq)
{
    struct cfq_queue *cfqq = RQ_CFQQ(rq);
    struct cfq_data *cfqd = cfqq->cfqd;
    struct request *__alias;

    cfqq->queued[rq_is_sync(rq)]++;

    /*
     * looks a little odd, but the first insert might return an alias.
     * if that happens, put the alias on the dispatch list
     */
    while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
        cfq_dispatch_insert(cfqd->queue, __alias);

    if (!cfq_cfqq_on_rr(cfqq))
        cfq_add_cfqq_rr(cfqd, cfqq);

    /*
     * check if this request is a better next-serve candidate
     */
    cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq);
    BUG_ON(!cfqq->next_rq);
}

　ここでは、引数で受け取った request オブジェクトのI/O タイプをオフセットとした cfq_queue の queued 配列の値をインクリメントしている。
　まずここで言っている I/O タイプは、前回に話をした、対象としているリクエストが READ 要求か同期 I/O の要求なのか否かを表すものであり、前者の I/O タイプは I/O ブロックレイヤにおいて内部的に 1 で表され、後者を 0 で表している。そして、cfq_queue オブジェクトの queued メンバは、

　int queued[2];

　と定義されており、現在 CFQ の内部リクエストキューに格納されている各 I/O タイプのリクエストの数をここで把握している。
　そしてここでは cfq_queue オブジェクト及び cfq_data オブジェクトを取得し、中央付近で何やら謎なループ処理を行っている。謎の答えがコメントに書かれてしまっているが、この内部処理について詳しく見てゆく。
　elv_rb_add() [block/elevator.c] 関数では、引数で与えられた rb_root オブジェクトをルートとする rb_tree 構造に引数で渡した request オブジェクトと同じ物理アドレスを対象とした request オブジェクトがツリー内部に存在する場合、ツリーの方のリクエストを返し、ツリー内にこれに該当するリクエストが存在しない場合に、引数で渡したリクエストをツリーに加えて NULL を返す。
　つまり行っている処理はというのは、単純に cfq_queue オブジェクトが持つ rb_tree に引数で与えられたリクエストを追加するというだけ。ただし、ツリー内部に既に同一の物理アドレスに対するリクエストが既に存在する場合に、バッティングするリクエストを受け取ってループの内側の cfq_dispatch_insert() を実行する。以下が cfq_dispatch_insert() のコードになる。

static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
{
    struct cfq_data *cfqd = q->elevator->elevator_data;
    struct cfq_queue *cfqq = RQ_CFQQ(rq);

    cfq_remove_request(rq);
    cfqq->dispatched++;
    elv_dispatch_sort(q, rq);

    if (cfq_cfqq_sync(cfqq))
        cfqd->sync_flight++;
}

　ここで言っているディスパッチキューとは I/O ブロックレイヤにおけるリクエストキューになる。
 cfq_dispatch_insert() 内部で呼び出されている cfq_remove_request() では、引数でわたしたリクエストが属する cfq_queue から、対象リクエストをパージする処理を行っている。
 その後に呼び出されている elv_dispatch_sort() 関数では、引数で渡されたキューの保留中リクエストのリストに 引数で渡したリクエストを追加する。

　この時点で CFQ の内部リクエストキューには、当該リクエストは存在しないので、呼び出し元の cfq_add_rq_rb() 内部のループにおける elv_rb_add() では、cfq_queue に対象のリクエストを追加して NULL を返す。
　そして cfq_add_rq_rb() では最後に cfq_choose_req() を呼び出し cfq_queue オブジェクトの next_rq メンバで表される request オブジェクトと、引数で渡された request オブジェクトとで、どちらの優先度がより高いかを計算し、cfq_queue オブジェクトの next_rq メンバを再設定している。
　そうやら、CFQ 内部リクエストキューの next_rq が参照するリクエストが CFQ 内部では特別な意味を持っているようである。

　ここで cfq_add_rq_rb() の呼び出し元の cfq_reposition_rq_rb() について調べる。コードは以下のとおり。

static inline void
cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
{
    elv_rb_del(&cfqq->sort_list, rq);
    cfqq->queued[rq_is_sync(rq)]--;
    cfq_add_rq_rb(rq);
}

 ここではまず elv_rb_del() を呼び出し、cfq_queue オブジェクトが持つ rb_tree から、引数で渡した request オブジェクトをパージしている。そして、cfq_queue オブジェクトの queued メンバで表される配列値を更新し、さっき調べた cfq_add_rq_rb() を呼び出している。
　ここで一体何をやっているかと言うと。CFQ の内部キューにおけるリクエストの付け替えを行っている。

　ここでようやくトップの cfq_merged_request() の処理について見てゆく。次に示すのがそのコード。

static void cfq_merged_request(struct request_queue *q, struct request *req,
                   int type)
{
    if (type == ELEVATOR_FRONT_MERGE) {
        struct cfq_queue *cfqq = RQ_CFQQ(req);

        cfq_reposition_rq_rb(cfqq, req);
    }
}

　といってもやっている処理は、引数で与えられた type が ELEVATOR_FRONT_MERGE の時に、さっき見た cfq_reposition_rq_rb() を実行するだけである。既に CFQ 内部に存在しているリクエストを cfq_position_rq_rb() を実行する事で cfq_queue オブジェクト中でのソート順序を更新する。
　ではなぜ、cfq_reposition_rq_rb() の呼び出しが ELEVATOR_FRONT_MERGE の時に限定されているのか？

　ここで I/O スケジューラの elevator_merged_fn メソッドが I/O ブロックレイヤに見せている機能について考える。
　ELEVATOR_FRONT_MERGE は、前方から request オブジェクトに bio オブジェクトが併合された事を表している。いったん request オブジェクトに bio オブジェクトが前方から併合されると、request オブジェクトの sector メンバの値が更新される。この場合、CFQ が管理するキュー内部のソート順が乱れる可能性がある。そのためブロックレイヤは I/O スケジューラの elevator_merged_fn メソッドを呼び出し、マージした request オブジェクトの位置を更新する事で、I/O スケジューラ内部のリクエストキューに存在する request オブジェクトのソート順を整理する。
　ただし。これを行う際に、I/O スケジューラの内部キューに溜っている request オブジェクトの I/O 要求位置が、更新する request オブジェクトのそれとバッティングする可能性がある。これについての責任は、各 I/O スケジューラが担っている。CFQ ではこのような場合に、前者の request オブジェクトをディスパッチキューに挿入し cfq_queue から取り除く処理を行っている。

　今回学習した内容は次の２つ。
　(1) CFQ I/O スケジューラにおける elevator_merged_fn メソッドの実装
　(2) I/O スケジューラ一般における elevator_merged_fn メソッドの処理