テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

device-mapperの仕組み (6) dm_ioで同期I/O. デッドロックに気をつけて!

前回, dm_io関数について紹介しました. device-mapperの提供するI/O発行用便利ラッパーであり, 非同期I/Oを出してからスリープして待つ方式で同期I/Oもサポートしているということを述べました.

今回は, この同期I/Oを正直に行うとデッドロックするということを説明します. 私はまだ経験の浅かった頃, このバグに嵌りました. その当時このバグを「I/Oが迷子問題」と呼んでいました. 調査をすると, generic_make_requestまわりで何かおかしいということはやがて分かりましたが, generic_make_requestにprintkを入れると, カーネルが立ち上がらなくなりました. 私は, systemtapを使い, バグを突き止め, いつものように一瞬で修正しました.

後で分かったことですが, この問題はdevice-mapper界隈では良く知られているものでした. 紹介する以下のコードは, dm-snap-persistent.cというコードから抜き出したものです. do_metadataは同期I/Oを発行しており, chunk_ioでは, それをworkqueueにいれて(queue_work)別スレッドで動かし, スレッドの完了をflush_workで待つという処理を行なっています. なぜこのような冗長な処理が必要なのでしょうか?コメントに「generic_make_request recursionを避けるためだ」と書いてあります. この記事では, このコメントの裏にある仕組みを探求します.

static int chunk_io(struct pstore *ps, void *area, chunk_t chunk, int rw,
                    int metadata)
{
        // 略
        /*
         * Issue the synchronous I/O from a different thread
         * to avoid generic_make_request recursion.
         */
        INIT_WORK_ONSTACK(&req.work, do_metadata);
        queue_work(ps->metadata_wq, &req.work);
        flush_work(&req.work);
        // 略
}

static void do_metadata(struct work_struct *work)
{
        struct mdata_req *req = container_of(work, struct mdata_req, work);

        req->result = dm_io(req->io_req, 1, req->where, NULL);
}

以下は, generic_make_requestソースコードです. このコードにおいて, current->bio_listというのを使って, bioをキューするケースがあるというのがキモです. コメント(We only want...)を読むと, 「一つのタスクについてmake_request_fnがアクティブになるのはone at a timeであるべきだ. current->bio_listがnon-NULLであるということは, make_request_fnが今アクティブであるということだ. この場合, listのtailに格納して, あとで処理する」ということが書かれています.

void generic_make_request(struct bio *bio)
{
        struct bio_list bio_list_on_stack;

        if (!generic_make_request_checks(bio))
                return;

        /*
         * We only want one ->make_request_fn to be active at a time, else
         * stack usage with stacked devices could be a problem. So use
         * current->bio_list to keep a list of requests submited by a
         * make_request_fn function. current->bio_list is also used as a
         * flag to say if generic_make_request is currently active in this
         * task or not. If it is NULL, then no make_request is active. If
         * it is non-NULL, then a make_request is active, and new requests
         * should be added at the tail
         */
        if (current->bio_list) {
                bio_list_add(current->bio_list, bio); // (#1)
                return;
        }

        /* following loop may be a bit non-obvious, and so deserves some
         * explanation.
         * Before entering the loop, bio->bi_next is NULL (as all callers
         * ensure that) so we have a list with a single bio.
         * We pretend that we have just taken it off a longer list, so
         * we assign bio_list to a pointer to the bio_list_on_stack,
         * thus initialising the bio_list of new bios to be
         * added. ->make_request() may indeed add some more bios
         * through a recursive call to generic_make_request. If it
         * did, we find a non-NULL value in bio_list and re-enter the loop
         * from the top. In this case we really did just take the bio
         * of the top of the list (no pretending) and so remove it from
         * bio_list, and call into ->make_request() again.
         */
        BUG_ON(bio->bi_next);
        bio_list_init(&bio_list_on_stack);
        current->bio_list = &bio_list_on_stack;
        do {
                struct request_queue *q = bdev_get_queue(bio->bi_bdev);

                q->make_request_fn(q, bio); // (#2)

                bio = bio_list_pop(current->bio_list); // (#3)
        } while (bio);
        current->bio_list = NULL; /* deactivate */
}
EXPORT_SYMBOL(generic_make_request);

以下のようなストーリーでデッドロックを確認出来ます. 説明のため, コード中に番号#1-#3を振りました.

  1. 仮想デバイスに対してI/Oが入ってくる. dm_requestが呼ばれる(#2). current->bio_listはnon-NULLとなる.
  2. dm_requestの中でmapメソッドが呼ばれ, その中でdm_ioが同期I/Oモードで呼ばれる.
  3. 今度は, current->bio_listがnon-NULLなので, bioはbio_listに格納され(#1), dm_requestの処理が終わったあとにpopされ(#3), 処理されることを待つ.
  4. しかし, dm_ioを同期I/Oで使ったため, currentはsleepしてしまっており, I/Oの終わりを待っている.
  5. つまり, dm_io以下で発行したI/Oを処理するためには, dm_requestを抜けて#3まで進む必要があるが, そのI/O処理が終わらないと#2の位置から抜け出せず, めでたくデッドロックとなる. dm_ioで発行したI/Oが永遠に終了しないので, I/Oが「迷子になった」と呼んでいました.

この問題は, 同じタスクのbio_listを2つのI/Oで共有してしまってることが問題ですから, スレッドを分ければ解決します. そのために, 先のコード(chunk_io)では, workqueueにI/O発行を任せてしまうという工夫をしています. dm-lcでも, 以下のような関数を作ってこの問題に対処しています.

static int dm_safe_io_internal(
                struct dm_io_request *io_req,
                struct dm_io_region *region, unsigned num_regions,
                unsigned long *err_bits, bool thread, int lineno)
{
        int err;
        if(thread){
                struct safe_io io = {
                        .io_req = io_req,
                        .region = region,
                        .num_regions = num_regions,
                };

                INIT_WORK_ONSTACK(&io.work, safe_io_proc);

                queue_work(safe_io_wq, &io.work);
                flush_work(&io.work);

                err = io.err;
                *err_bits = io.err_bits;
        } else {
                err = dm_io(io_req, num_regions, region, err_bits);
        }

本質的な問題はどこにあるでしょうか?言い換えると, この問題をgeneric_make_request側で解決することは出来ないのでしょうか.
例えば, generic_make_requestの中でwhileループをするのではなく, generic_make_requestの中では常に, bio_listに追加するだけに止め, 実際にループしてmake_request_fnを呼び出すのは別のスレッドにするという手法が考えられます. 一般的に, このようにforegroundでloopingするというのはデッドロックや無限ループの可能性を含むため良い技法ではありません. そして, 多くの場合有効なのは, 一本のキューを用意し, それに格納する人(foreground)と, 処理する人(background)に分離することです. なぜこのような設計になっていないかは, foregroundとbackgroundの協調にタイミング差が生まれてしまい, それを制御することが難しいからだろうと思います. もし, この話について過去の議論を知っている方がいらっしゃったら教えてください.

ちなみにdm-lcでは, I/OデータをDRAMバッファに格納していき, 最終的に発行用データをqueueに格納するまでforegroundの処理として, その発行用データを素にして本当にI/Oをするのはbackgroundで行なっています. この工夫によって, 設計がシンプルになるだけでなく, backgroundにおいて同期I/Oを行なうことが出来てしまう(非同期で努力する性能上の意味があまりないので).
プログラミングの一般論として, 複雑に見えるものを基礎的ないくつかの処理に分解するというのが重要です. そして, 並列/並行/分散が課題となっている昨今, そのような基本的な技法を自然に採り入れることが出来る技術者がより重要になっていくことと思っています.