前回は 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 メソッドの処理