Linuxカーネルのファイルアクセスの処理を追いかける (14) mq-deadline

関連記事

概要
はじめに
mq-deadlineの概要
- mq-deadlineのパラメータ
- deadline_data構造体
mq-deadlineの関数群
おわりに
変更履歴
参考

概要

QEMUの vexpress-a9 (arm) で Linux 5.15を起動させながら、ファイル書き込みのカーネル処理を確認していく。

本章では、mq-deadline I/Oスケジューラの概要紹介と初期処理(init_sched/init_hctx)・解放処理(exit_sched)を確認した。

はじめに

ユーザプロセスはファイルシステムという機構によって記憶装置上のデータをファイルという形式で書き込み・読み込みすることができる。
本調査では、ユーザプロセスがファイルに書き込み要求を実行したときにLinux カーネルではどのような処理が実行されるかを読み解いていく。

調査対象や環境などはPart 1: 環境セットアップを参照。

mq-deadlineの概要

mq-deadline I/Oスケジューラは、deadline I/Oスケジューラをマルチキュー向けに作り直されたI/Oスケジューラである。

deadline (mq-deadline) I/Oスケジューラでは、現在処理中のリクエストから近いI/Oリクエストから順に処理をしていくが、deadlineを過ぎているリクエストは優先して処理される。

mq-deadline I/Oスケジューラでは、セクタ位置をキーとする赤黒木とリクエスト挿入順を保持するFIFOのデータ構造を持ち、これらがReadとWriteの2種類が用意される。
さらに、mq-deadlineでは I/O優先度RT, BE, IDLEがサポートされており、優先度の高いリクエストがすべて終了した後に、低い優先度の要求がdispatchされることが保証されている。

www.spinics.net

mq-deadline I/Oスケジューラでは、同期リクエストのためにリクエストキューの25%を確保している。(後述するasync_depthで変更可能)

lwn.net

そして、ReadリクエストはWriteリクエストより優先されて処理される。

mq-deadlineのパラメータ

mq-deadline I/Oスケジューラでは、いくつかのパラメータをsysfs経由で設定・確認することができる。

    # ls /sys/block/mmcblk0/queue/iosched
    async_depth     front_merges    write_expire
    fifo_batch      read_expire     writes_starved

read_expire: Readリクエストのdeadline (ミリ秒)
write_expire: Writeリクエストのdeadline (ミリ秒)
fifo_batch: FIFOデータ構造のサイズ (リクエスト数)
writes_starved: Readリクエストのディスパッチ回数に対するWriteリクエストのディスパッチ回数の優先回数(ディスパッチ数)
front_merges: フロントマージの有効/無効化 (Bool値)
async_depth: 非同期要求が占有できるリクエストキュー (リクエスト数)

また、debugfsからはmq-deadline I/Oスケジューラのステータスを確認することができる。

    # ls /sys/kernel/debug/block/mmcblk0/sched/
    async_depth       owned_by_driver   read1_next_rq     write0_next_rq
    batching          queued            read2_fifo_list   write1_fifo_list
    dispatch0         read0_fifo_list   read2_next_rq     write1_next_rq
    dispatch1         read0_next_rq     starved           write2_fifo_list
    dispatch2         read1_fifo_list   write0_fifo_list  write2_next_rq

ここで、0はRT, 1はBE, 2はIDLEを表している。

deadline_data構造体

Linux の IO scheduler elevetor_queueのelevetor_dataに各IO scheduler固有のデータ構造を設定することができる。

mq-deadlineでは、deadline_dataが設定される。

// 79:
struct deadline_data {
    /*
    * run time data
    */

    struct dd_per_prio per_prio[DD_PRIO_COUNT];

    /* Data direction of latest dispatched request. */
    enum dd_data_dir last_dir;
    unsigned int batching;        /* number of sequential requests made */
    unsigned int starved;     /* times reads have starved writes */

    struct io_stats __percpu *stats;

    /*
    * settings that change how the i/o scheduler behaves
    */
    int fifo_expire[DD_DIR_COUNT];
    int fifo_batch;
    int writes_starved;
    int front_merges;
    u32 async_depth;

    spinlock_t lock;
    spinlock_t zone_lock;
};

mq-deadlineでは、リクエストをREADとWRITEに分類し、それぞれを別のキュー(赤黒木)で管理する。
ここでは、dir (direction)として扱われ、dd_data_dirで定義されている。

// 38:
enum dd_data_dir {
    DD_READ     = READ,
    DD_WRITE    = WRITE,
};

enum { DD_DIR_COUNT = 2 };

mq-deadlineではリクエストを、dd_per_prio構造体にあるキュー(赤黒木)で管理する。
この構造体は、各I/O優先度に用意される。

// 71:
struct dd_per_prio {
    struct list_head dispatch;
    struct rb_root sort_list[DD_DIR_COUNT];
    struct list_head fifo_list[DD_DIR_COUNT];
    /* Next request in FIFO order. Read, write or both are NULL. */
    struct request *next_rq[DD_DIR_COUNT];
};

mq-deadlineの関数群

ここでは、初期処理(init_sched/init_hctx)・解放処理(exit_sched)の関数のみ注目する。

dd_init_sched

dd_init_sched関数は、elevetor_typeにあるopsのinit_schedに設定され、blk_mq_init_sched関数から呼び出される関数となっている。

init_schedではrequest_queue (I/Oスケジューラ固有のelevator_dataを含む) の確保と request_queue->elevatorへの設定をする。

dd_init_sched関数の定義は次の通りとなっている。

// 552:
static int dd_init_sched(struct request_queue *q, struct elevator_type *e)
{
    struct deadline_data *dd;
    struct elevator_queue *eq;
    enum dd_prio prio;
    int ret = -ENOMEM;

    eq = elevator_alloc(q, e);
    if (!eq)
        return ret;

    dd = kzalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
    if (!dd)
        goto put_eq;

    eq->elevator_data = dd;

    dd->stats = alloc_percpu_gfp(typeof(*dd->stats),
                     GFP_KERNEL | __GFP_ZERO);
    if (!dd->stats)
        goto free_dd;

    for (prio = 0; prio <= DD_PRIO_MAX; prio++) {
        struct dd_per_prio *per_prio = &dd->per_prio[prio];

        INIT_LIST_HEAD(&per_prio->dispatch);
        INIT_LIST_HEAD(&per_prio->fifo_list[DD_READ]);
        INIT_LIST_HEAD(&per_prio->fifo_list[DD_WRITE]);
        per_prio->sort_list[DD_READ] = RB_ROOT;
        per_prio->sort_list[DD_WRITE] = RB_ROOT;
    }
    dd->fifo_expire[DD_READ] = read_expire;
    dd->fifo_expire[DD_WRITE] = write_expire;
    dd->writes_starved = writes_starved;
    dd->front_merges = 1;
    dd->last_dir = DD_WRITE;
    dd->fifo_batch = fifo_batch;
    spin_lock_init(&dd->lock);
    spin_lock_init(&dd->zone_lock);

    q->elevator = eq;
    return 0;

free_dd:
    kfree(dd);

put_eq:
    kobject_put(&eq->kobj);
    return ret;
}

dd_init_sched関数では、I/O優先度毎にリスト(赤黒木)と各パラメータを初期化する。

dd_init_hctx

dd_init_hctx関数は、elevetor_typeにあるopsのinit_hctxに設定され、blk_mq_init_sched関数から呼び出される関数となっている。

init_hctxではHardware dispatch queuesをI/Oスケジューラに向けて初期化する。

dd_init_hctx関数の定義は次の通りとなっている。

// 526:
static int dd_init_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx)
{
    dd_depth_updated(hctx);
    return 0;
}

dd_init_hctx関数は、後述するdd_depth_updated関数を呼び出す。

dd_depth_updated

dd_depth_updated関数は、elevetor_typeにあるopsのdepth_updatedに設定され、blk_mq_update_nr_requests関数から呼び出される関数となっている。

depth_updatedでは、リクエストキューの深さが変化したときにI/Oスケジューラの内部情報を更新することができる。

dd_depth_updated関数の定義は次の通りとなっている。

// 514:
static void dd_depth_updated(struct blk_mq_hw_ctx *hctx)
{
    struct request_queue *q = hctx->queue;
    struct deadline_data *dd = q->elevator->elevator_data;
    struct blk_mq_tags *tags = hctx->sched_tags;

    dd->async_depth = max(1UL, 3 * q->nr_requests / 4);

    sbitmap_queue_min_shallow_depth(tags->bitmap_tags, dd->async_depth);
}

mq-deadline I/Oスケジューラでは、非同期リクエストが占有できる割合をdd->async_depthに設定することができる。

ただし、最低でも25% ( ${\frac{1}{4}}$ ) は同期リクエストのために確保されているので、dd->async_depthに設定できる値は高々75% ( ${\frac{3}{4}}$ )となる。

dd_exit_sched

dd_exit_sched関数は、elevetor_typeにあるopsのexit_schedに設定され、blk_mq_exit_sched関数から呼び出される関数となっている。

exit_schedではI/Oスケジューラ周りのエラーハンドリングやI/Oスケジューラの変更により、データ構造を解放する。

dd_exit_sched関数の定義は次の通りとなっている。

// 532:
static void dd_exit_sched(struct elevator_queue *e)
{
    struct deadline_data *dd = e->elevator_data;
    enum dd_prio prio;

    for (prio = 0; prio <= DD_PRIO_MAX; prio++) {
        struct dd_per_prio *per_prio = &dd->per_prio[prio];

        WARN_ON_ONCE(!list_empty(&per_prio->fifo_list[DD_READ]));
        WARN_ON_ONCE(!list_empty(&per_prio->fifo_list[DD_WRITE]));
    }

    free_percpu(dd->stats);

    kfree(dd);
}