今回は I/O スケジューラの API の  elevator_merge_req_fn メソッドについて。CFQ の実装を調べて、その役割を学習する。

　まずはカーネルドキュメント [1] から elevator_merge_req_fn メソッドの仕事について調べる。それによると

elevator_merge_req_fn　　called when two requests get merged. the one
　　　　which gets merged into the other one will be
　　　　never seen by I/O scheduler again. IOW, after
　　　　being merged, the request is gone.

　
　とある。つまり、elevator_merge_req_fn メソッドはリクエストオブジェクト同士を併合した時に呼び出されるらしい。そして、一方のリクエストオブジェクトは、I/O スケジューラでは二度と扱わないと言っている。これはどういう事を言っているのか。

　CFQ における elevator_merge_req_fn メソッドの実体は cfq_merged_requests() 関数 [block/cfq-iosched.c] で定義されている。以下がそのコードになる。

static void
cfq_merged_requests(struct request_queue *q, struct request *rq,
            struct request *next)
{
    /*
     * reposition in fifo if next is older than rq
     */
    if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
        time_before(next->start_time, rq->start_time))
        list_move(&rq->queuelist, &next->queuelist);

    cfq_remove_request(next);
}

　ここでは、変数 next で表されるリクエストオブジェクトが rq で表されるリクエストオブジェクトよりも若い (新しい) 場合に list_move() を実行して rq のリクエストオブジェクトを next のリスト上の後方に移動させている。
　そして cfq_remove_request() を呼び出している。こいつは、前回に、リクエストオブジェクトをディスパッチキューに挿入する処理 cfq_dispatch_insert() でも登場した処理で、引数で与えられたリクエストオブジェクトを CFQ 内部のリクエストキュー (cfq_queue オブジェクトで表されるキュー) からパージする。

　cfq_merged_requests() 関数の処理はたったこれだけ。やっている事は、単に第三引数で与えられたリクエストオブジェクトを cfq_remove_request() を呼び出して CFQ のキューからパージするだけ。リクエストの併合処理も、併合後の一方のリクエストの廃棄やら、環境情報や統計情報の更新といった諸処の処理を全く行わない。単に CFQ の内部リストから外すだけ。
    リストの更新処理を行っているのは、マージされたリクエストオブジェクトの処理順序がパージされたリクエストよりも前方に存在する場合に、前者のリクエストオブジェクトのキュー内部での位置を、後者が存在していた位置に移動させる為。パージされたリクエストオブジェクトの存在が過去形なのは、直後にリクエストキューから外される為。

　CFQ における elevator_merge_req_fn の処理内容は以上だが。これだけではつまらないので、この処理を行う I/O ブロックレイヤの elevator_merge_req_fn メソッドを呼び出す処理を調査する。

    elevator_merge_req_fn メソッドを実行するのは elv_merge_requests() 関数 [block/elevator.c] である。以下がそのコード

void elv_merge_requests(struct request_queue *q, struct request *rq,
                 struct request *next)
{
    elevator_t *e = q->elevator;

    if (e->ops->elevator_merge_req_fn)
        e->ops->elevator_merge_req_fn(q, rq, next);

    elv_rqhash_reposition(q, rq);
    elv_rqhash_del(q, next);

    q->nr_sorted--;
    q->last_merge = rq;
}

　elv_merge_requests() では elevator_merge_req_fn メソッドを呼び出した後。キュー内のハッシュリストの再配置し、マージしたリクエストオブジェクトを I/O ブロックレイヤのリクエストキューのリストから外し、リクエストキューの環境情報を更新する。
　この関数が呼び出された段階では、リクエストオブジェクトのマージが完了している。elv_merge_requests() を呼び出す関数は、attempt_merge() 関数 [block/ll_rw_blk.c] になる。以下がそのコード。

static int attempt_merge(struct request_queue *q, struct request *req,
              struct request *next)
{
    if (!rq_mergeable(req) || !rq_mergeable(next))
        return 0;

    /*
     * not contiguous
     */
    if (req->sector + req->nr_sectors != next->sector)
        return 0;

    if (rq_data_dir(req) != rq_data_dir(next)
        || req->rq_disk != next->rq_disk
        || next->special)
        return 0;

    /*
     * If we are allowed to merge, then append bio list
     * from next to rq and release next. merge_requests_fn
     * will have updated segment counts, update sector
     * counts here.
     */
    if (!ll_merge_requests_fn(q, req, next))
        return 0;

    /*
     * At this point we have either done a back merge
     * or front merge. We need the smaller start_time of
     * the merged requests to be the current request
     * for accounting purposes.
     */
    if (time_after(req->start_time, next->start_time))
        req->start_time = next->start_time;

    req->biotail->bi_next = next->bio;
    req->biotail = next->biotail;

    req->nr_sectors = req->hard_nr_sectors += next->hard_nr_sectors;

    elv_merge_requests(q, req, next);

    if (req->rq_disk) {
        disk_round_stats(req->rq_disk);
        req->rq_disk->in_flight--;
    }

    req->ioprio = ioprio_best(req->ioprio, next->ioprio);

    __blk_put_request(q, next);
    return 1;
}

　ここでは、引数で指定した２つのリクエストオブジェクトが、同一ブロックデバイスに対する要求対象の物理アドレス空間が隣接している場合に、一方のリクエストをもう一方にヘイグさせる。具体的には、一方のリクエストオブジェクトが持つ bio オブジェクトのリストをもう一方にマージする。
　マージしたリクエストオブジェクトは elevator_merge_req_fn メソッドによって I/O スケジューラの内部リクエストキューからパージされる。そして、I/O ブロックレイヤのリクエストキューからもパージされる。
　elv_merge_requests() の後で実行されている disk_round_stats() 関数の呼び出しと、gendisk オブジェクトの in_flight メンバの更新処理は、リクエストの対象となるディスクデバイスの統計情報の更新を行っている。これについてはカーネルドキュメント [2] が存在するので、そちらに詳しく書かれている。
　簡単に言うと。/proc/interrupts のように、ディスクアクセスやディスクアクセスに関する統計情報を取得できる。具体的には、read/write の回数や、セクタ数、リクエストに要した時間、I/O スケジューラによる待ち時間などを、/sys/block/<device name>/stat から参照できる。こいつを使う事で、I/O 関連のパフォーマンス測定なんかに役に立ちそうだ。
　attempt_merge() では最後に __blk_put_request() 関数を呼び出し、マージしたリクエストオブジェクトの廃棄処理を行っている。こいつの処理内容は、別の回の内容と被るので次回以降に話をする。

　今回学習した内容は次の４つ。
　(1) CFQ I/O スケジューラにおける elevator_merged_req_fn メソッドの実装
　(2) I/O スケジューラ一般における elevator_merged_req_fn メソッドの処理
　(3) I/O ブロックレイヤにおけるリクエストオブジェクト同士の併合処理の実装
　(4) ディスクに対する I/O の統計情報設定のカーネル処理

　[1] Documentation/block/biodoc.txt
　[2] Documentation/block/stat.txt

1. はじめに

　前回は CFQ における elevator_merged_fn メソッドの実体と I/O ブロックレイヤにおける周辺処理をしらべて、こいつがどんな役割を担っているのかという事を調べ、リクエストオブジェクト同士におけるマージの後に呼ばれる処理で、I/O スケジューラではマージしたリクエストを内部キューから外し、必要に応じて内部キューにおけるマージされたリクエストのリスト位置を更新していた。


2. 概要

　今回は I/O スケジューラの elevator_allow_merge_fn メソッドの役割と CFQ の実装、及び関連する I/O ブロックレイヤの処理についてみてゆく。

　例によってまずは、カーネルドキュメント [1] から処理の概要について調べる。

elevator_allow_merge_fn    called whenever the block layer determines
        that a bio can be merged into an existing
        request safely. The io scheduler may still
        want to stop a merge at this point if it
        results in some sort of conflict internally,
        this hook allows it to do that.

　ドキュメントには、bio オブジェクトをリクエストオブジェクトにマージする際に、マージ可能かどうかを判定するという事が書かれている。

 
3. 学習内容のまとめ
 
　elevator_allow_merge_fn メソッドを含む I/O ブロックレイヤにおける bio オブジェクトの request オブジェクトへのマージ関連処理の一連の動作は次のようになっている。
　I/O ブロックレイヤは bio オブジェクトを request オブジェクトにマージする前に elv_rq_merge_ok() 関数を実行し、bio オブジェクトを引数で渡した request オブジェクトにマージできるかどうかの確認を行う。
　そして I/O ブロックレイヤで bio オブジェクトを request オブジェクトに対してマージ可能だと判断した後、I/O スケジューラ的にマージ可能かどうかを確かめるために、I/O ブロックレイヤは elevator_allow_merge_fn メソッドを呼び出してこれを確認する。
　I/O スケジューラ側では、当該マージ要求に対して、マージされては困るケースについて elevator_allow_merge_fn メソッドの実体として記述する。
　尚、I/O スケジューラは、elevator_allow_merge_fn メソッドに対する応答としてマージ可能ならば 1 を返し、マージしてほしくない場合には 0 を返す。


4. 内容詳細
 
　それでは、実際に CFQ の elevator_allow_merge_fn メソッドの実態である cfq_allow_merge() について見て行く。以下がそのコード。

static int cfq_allow_merge(struct request_queue *q, struct request *rq,
               struct bio *bio)
{
    struct cfq_data *cfqd = q->elevator->elevator_data;
    struct cfq_io_context *cic;
    struct cfq_queue *cfqq;

    /*
     * Disallow merge of a sync bio into an async request.
     */
    if (cfq_bio_sync(bio) && !rq_is_sync(rq))
        return 0;

    /*
     * Lookup the cfqq that this bio will be queued with. Allow
     * merge only if rq is queued there.
     */
    cic = cfq_cic_rb_lookup(cfqd, current->io_context);
    if (!cic)
        return 0;

    cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
    if (cfqq == RQ_CFQQ(rq))
        return 1;

    return 0;
}

　引数で渡した bio オブジェクトとリクエストオブジェクトの I/O タイプが異なる場合、CFQ はマージ不可と判断する。I/O タイプについては前回の話を参照してもらいたい。
　又、cfq_cic_rb_lookup() によって cfq_io_context が取得できないケースも同様にマージ不可と判断する。cfq_cic_rb_lookup() 関数については前々回に話をしたので、それを参照してもらいたい。
　cfq_allow_merge() では、cfq_cic_rb_lookup() の呼び出しを行う際に、cfq_data オブジェクトとカレントプロセスの io_context オブジェクトをこれに渡している。
　cfq_data オブジェクトは I/O ブロックレイヤが持つ elevator_queue オブジェクトの elevator_data メンバが参照するオブジェクトであり io_context オブジェクトはカレントプロセスが参照している。
　つまり CFQ I/O スケジューラのデータ構造の設計では、プロセスのブロックデバイスの組合せによって cfq_io_context オブジェクトが一意に決定されるという事がわかる。また、cfq_cic_rb_lookup() から cfq_io_context オブジェクトと cfq_data オブジェクトが１対１に対応する事もわかる。
　そして cfq_allow_merge() では最後に、取得した cfq_io_context オブジェクトが持つ２本の cfq_queue オブジェクトのうち、マージする bio オブジェクトの cfq_queue オブジェクトを取得し、これがマージされるリクエストオブジェクトが参照する CFQ の内部リクエストキューである場合にのみ、マージ可能であると判断する。

　以上が CFQ における elevator_allow_merge_fn メソッドの実装である。
　ここで elevator_allow_merge_fn メソッドを実行している I/O ブロックレイヤの処理を見てみる。次に示すのは後述する I/O ブロックレイヤの elv_rq_merge_ok() コードである。

/*
 * can we safely merge with this request?
 */
inline int elv_rq_merge_ok(struct request *rq, struct bio *bio)
{
    if (!rq_mergeable(rq))
        return 0;

    /*
     * different data direction or already started, don't merge
     */
    if (bio_data_dir(bio) != rq_data_dir(rq))
        return 0;

    /*
     * must be same device and not a special request
     */
    if (rq->rq_disk != bio->bi_bdev->bd_disk || rq->special)
        return 0;

    if (!elv_iosched_allow_merge(rq, bio))
        return 0;

    return 1;
}

　
　I/O ブロックレイヤは elv_iosched_allow_merge() [block/elevator.c] から elevator_allow_merge_fn メソッドを呼び出しており、その呼び出し元は elv_rq_merge_ok() [block/elevator.c] である。
　そして、elv_iosched_allow_merge() が 0 を返すと、無条件で elv_rq_merge_ok() は 0 を返す。


5. まとめ

　今回学習した内容は次の３つ。

　(1) CFQ I/O スケジューラにおける elevator_allow_merge_fn メソッドの実装
　(2) I/O スケジューラ一般における elevator_allow_merge_fn メソッドの処理の役割
　(3) I/O ブロックレイヤにおける bio オブジェクト併合許可の確認処理の中身


　[1] Documentation/block/biodoc.txt

1. はじめに

  前回は I/O スケジューラの elevator_merged_fn メソッドの役割と CFQ における elevator_merged_fn メソッドの実装である cfq_allow_merge_fn メソッドの実装について見てきた。
  ここでは、I/O スケジューラにおける bio オブジェクトのリクエストオブジェクトに対するマージが行われてはならないケースについて記載していた。


2. 概要

  今回は elevator_dispatch_requests メソッドについて。前回同様に、その役割と CFQ における実装について見てゆく。
  まずは例によって、カーネルドキュメントからその処理の概要について把握する。以下がその内容になる。

elevator_dispatch_fn    fills the dispatch queue with ready requests.
        I/O schedulers are free to postpone requests by
        not filling the dispatch queue unless @force
        is non-zero.  Once dispatched, I/O schedulers
        are not allowed to manipulate the requests -
        they belong to generic dispatch queue.

  各 I/O スケジューラがこのメソッドで行う処理内容は、ディスパッチキューに入れる事らしい。この「ディスパッチキュー」について前回以前に説明なしでこれを紹介したが。I/O スケジューラから見た I/O ブロックレイヤのリクエストキュー (request_queue 型) オブジェクトの事をディスパッチキューとここでは言っている。
  そして、引数で渡される force 変数の値が 0 の時、I/O スケジューラはディスパッチキューに対するリクエストの挿入処理は自由に調節できると言っている。最後に、ディスパッチキューに送ったリクエストオブジェクトは I/O スケジューラの都合で変更してはいけないと言っている。
 

3. 学習内容のまとめ

  ドキュメントでも記載されているように、elevator_dispatch_fn メソッドでは、各 I/O スケジューラが持つリクエストオブジェクトをディスパッチキューに転送する処理を行う。
  処理内容は２通り存在し、このメソッドの第二引数の force 変数に 1 が設定された場合、I/O スケジューラが管理する全てのリクエストオブジェクトをディスパッチキューに転送する。force の値が 0 の場合、I/O スケジューラは独自の判断でディスパッチキューにリクエストオブジェクトを転送する (場合によっては何も転送しない) 処理を行う。


4. 内容詳細

  それでは CFQ における elevator_dispatch_requests メソッドの実装について、引数の force 変数に 1 が設定された場合の処理について見てゆく。以下がメソッドの実体の cfq_dispatch_requests() 関数のうち、force 変数に 1 が設定された時に関連するコード。

[ code 1 ]

1    static int cfq_dispatch_requests(struct request_queue *q, int force)
2    {
3      struct cfq_data *cfqd = q->elevator->elevator_data;
4      struct cfq_queue *cfqq;
5      int dispatched;
6   
7      if (!cfqd->busy_queues)
8        return 0;
9   
10     if (unlikely(force))
11       return cfq_forced_dispatch(cfqd);
12   
13     .. (略) ..
14   
15  }

  force 変数に 1 が設定された時 CFQ は、I/O スケジューラが管理する全てのリクエストオブジェクトをディスパッチキューに転送する処理を行う。

  コードの 7 行目で行っている cfq_data オブジェクトの busy_queues メンバのチェックは CFQ が持ついづれかのリクエストキューの中にリクエストオブジェクトが入っているかどうかを確認している。リクエストオブジェクトのキューへの挿入が完了した時、cfq_add_cfqq_rr() 関数 [2] が呼ばれ、cfq_data オブジェクトの busy_queues メンバの値をインクリメントする。逆に、cfq_del_rq_rb() [3] の処理が完了した時に busy_queues メンバの値はデクリメントされる。
  cfq_data オブジェクトの busy_queues メンバの値は、CFQ で管理するリクエストオブジェクトの数を表している。この値が 0 の時、CFQ 内部にはひとつもリクエストオブジェクトが存在しない事を意味する。

  そして 10 行目で force メンバの値を読み、判定が真の時に cfq_forced_dispatch() を実行する。この force 変数を囲んでいる unlikely マクロはコンパイラに対して、この判定がほとんどの場合偽である事を教えている。何故、こんなことをしているのか。
  かなり教科書的な話になるが。最近のアーキテクチャではマルチサイクルプロセッサが当り前である、シングルサイクルプロセッサでは１サイクル中に利用出来る CPU 内部の機能ユニットはひとつの命令によって占領されるが、マルチサイクルプロセッサでは、ひとつの CPU の同じクロック周期の間に、複数の命令によって複数の機能ユニットを使用できる。なので、複数の命令が同時に別々の処理 (命令フェッチやデコード処理など) が実行できる。
  これが世に言うパイプラインというやつなのだが。こいつは、逐次的な処理の場合には、同時に複数の命令を処理する事が出来てパフォーマンスが上がるが、if や while といったジャンプ命令がくると、パイプラインに溜った処理を実行する事が無いので、パイプライン処理が無駄になる (教科書的にはこいつの事を "ストール" とか言ったりする。パイプラインが細かければ細かい程、逐次処理のパフォーマンスは高いが、ストールによる損失は大きくなる)。
  ジャンプ命令が来てもパフォーマンスを落とさないために、昔の偉い人はジャンプ命令の予測を行うという事を考えた。この unlikely マクロの処理はその一環になる。つまり、発生するジャンプ処理のジャンプ先がほぼ確実にわかっていれば、そのジャンプ処理を含むパイプライン処理のパフォーマンスは逐次処理のそれと変わらなくなるから。

  ここで 11 行目で実行される cfq_forced_dispatch() 関数の処理を見てゆく。以下がそのコード。

[ code 2 ]

1    static int cfq_forced_dispatch(struct cfq_data *cfqd)
2    {
3      int dispatched = 0;
4      struct rb_node *n;
5   
6      while ((n = cfq_rb_first(&cfqd->service_tree)) != NULL) {
7        struct cfq_queue *cfqq = rb_entry(n, struct cfq_queue, rb_node);
8   
9        dispatched += __cfq_forced_dispatch_cfqq(cfqq);
10     }
11   
12     cfq_slice_expired(cfqd, 0);
13 
14     BUG_ON(cfqd->busy_queues);
15   
16     return dispatched;
17   }

  cfq_forced_dispatch() では 6 行目のループの判定処理で cfq_rb_first() を実行し、リクエストキューを表す rb (red-black) ツリーのノードを取得する。以下がそのコード

[ code 3 ]

1    static struct rb_node *cfq_rb_first(struct cfq_rb_root *root)
2    {
3      if (!root->left)
4        root->left = rb_first(&root->rb);
5    
6      return root->left;
7    }

  cfq_rb_root オブジェクトが持つ rb ツリーから、先頭ノードを表す rb_node オブジェクトを取得する。
  cfq_rb_root オブジェクトは、ルートノードの左側のノード情報をメンバに持っている。これは、CFQ のデータ構造に度々出てくる、探索処理を省略する為に用意されているものである。

  [ code 2 ] で示した cfq_forced_dispatch() では cfq_rb_first() で CFQ 内部のリクエストキューの rb ツリーノードを取得し、7 行目でリクエストキューオブジェクトを取得する。そして、__cfq_forced_dispatch_cfqq() 関数を呼び出す。以下がそのコード。

[ code 4 ]

1    static inline int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
2    {
3      int dispatched = 0;
4   
5      while (cfqq->next_rq) {
6        cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
7        dispatched++;
8      }
9   
10     BUG_ON(!list_empty(&cfqq->fifo));
11     return dispatched;
12   }

  __cfq_forced_dispatch_cfqq() では、CFQ のリクエストキューに属する全てのリクエストオブジェクトをディスパッチキューに転送させる。
  内部では 5 行目から 8 行目のループで表されるように、リクエストキューが参照する next_rq メンバ [struct request * 型] の参照が無くなるまで cfq_data オブジェクトが参照するディスパッチキューと cfq_queue->next_rq を引数に cfq_dispatch_insert() [4] を呼び出す。
  cfq_queue オブジェクトの next_rq メンバはキューが次に処理すべきリクエストオブジェクトを表し、なんらかの理由によってキューからこのリクエストが削除された場合には、cfq_find_next_rq() を呼び出して、対象の cfq_queue オブジェクトの next_rq メンバをその都度、更新しなければならない。この処理は cfq_dispatch_insert() から呼ばれる cfq_remove_request() [5] において行われる。
  ここでは CFQ において重要な特徴のひとつを教えてくれている。うまり、CFQ I/O スケジューラは、各キューに滞留しているリクエストオブジェクトの処理順序について次に処理するリクエストのみを把握しており、それ以外の滞留リクエストについては未定であって、次に処理されるリクエストが消えて初めて、cfq_queue 内部から次に処理されるリクエストオブジェクトを選出するという設計となっている。
  但しこれは cfq_queue オブジェクトの sort_list メンバで表される rb ツリーに登録されているリクエストオブジェクトの場合の話。cfq_queue オブジェクトでは、sort_list メンバ以外に fifo メンバによってリクエストオブジェクトを管理している。これが表すキューにリクエストオブジェクトの queuelist メンバのアドレスが登録されており、リクエスト "キュー" を実現している。

  [ code 2 ] で示した cfq_forced_dispatch() の 7 行目で実行される、上述の [ code 4 ] で示した __cfq_forced_dispatch_cfqq() によって、6 行目で取得した cfq_queue オブジェクトが持つリクエストオブジェクトは全てディスパッチキューに送られる。
  ここで改めて 6 行目から 10 行目のループがとても奇妙に見える。それは、ループの内部及び、ループの真偽の判定の度に呼び出される cfq_rb_first において、cfq_rb_root オブジェクトの left メンバの値は変えられていないので、一見すると毎回同じ値が選ばれて無限ループになるように思える。[ code 4 ] で見た 5 行目から 8 行目で表されるループのように。
  これが無限ループにならないのは、ループ中で呼び出される __cfq_forced_dispatch_cfqq() の内部処理に秘密がある。
  上述したように __cfq_forced_dispatch_cfqq() では、リクエストキューが溜めている全てのリクエストオブジェクトに対して cfq_dispatch_insert() を実行している。リクエストキューに属する最後のリクエストオブジェクトを対象とした cfq_dispatch_insert() 関数処理の内部では、cfq_cfqq_del_rr() 関数が実行される。
  cfq_cfqq_del_rr() では、対象のリクエストキューを cfq_data の service_tree メンバで表される rr ツリーから除き、service_tree オブジェクトの left メンバが表すノードが現在着目しているノードならば NULL を設定するという処理を行う。
  これにより、__cfq_forced_dispatch_cfqq() から返った後の判定処理において、cfq_rb_first() 関数は rb_first() を呼び出して別のリクエストキューを取得する事になる。
  cfq_data オブジェクトの service_tree メンバは、cfq_data オブジェクトが持つ cfq_queue オブジェクトを管理する rb ツリー構造のルートを表す。またこのツリーはラウンドロビンで選択される為、カーネル内部では rr ツリーと呼ばれている。cfq_service_tree_add() によってリストに cfq_queue オブジェクトが追加され、 cfq_del_cfqq_rr() 関数によって指定された cfq_queue オブジェクトが service_tree から除かれる。

  これが elevator_dispatch_requests メソッドにおいて、引数 force に 1 が指定された時の CFQ での実装である。force 変数に 0 が設定された時の処理については次回に示す。


[1] Documentation/block/biodoc.txt
[2] cfq_queue オブジェクトを、指定した cfq_data オブジェクトの管理下に追加する処理
[3] cfq_data オブジェクトの管理下にある cfq_queue オブジェクトを覗く処理
[4] http://dev.ariel-networks.com/Members/ohyama/25cbi-o-30b930b130e530fc30e9-305d306e5
[5] http://dev.ariel-networks.com/Members/ohyama/25cbi-o-30b930b130e530fc30e9-305d306e5