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