Blk Multi-queue understanding

• Quiesce and Freeze
• Mapping between ctx and hctx
• Tags sharing
• Polling

We split driver and scheduler tags, so we can run the scheduling independently of device queue depth.

blk_mq_init_sched()
>>>>
    /*
     * Default to double of smaller one between hw queue_depth and 128,
     * since we don't split into sync/async like the old code did.
     * Additionally, this is a per-hw queue depth.
     */
    q->nr_requests = 2 * min_t(unsigned int, q->tag_set->queue_depth,
                   BLKDEV_MAX_RQ); //BLKDEV_MAX_RQ 128

    queue_for_each_hw_ctx(q, hctx, i) {
        ret = blk_mq_sched_alloc_tags(q, hctx, i);
        if (ret)
            goto err;
    }
>>>>

blk_mq_alloc_tag_set()
    -> blk_mq_alloc_rq_maps() // the actual depth may be lower than the set->queue_depth
        -> __blk_mq_alloc_rq_maps()
            -> __blk_mq_alloc_rq_map() //per-hctx-idx set->queue_depth
OR
        blk_mq_init_sched()
            -> blk_mq_sched_alloc_tags() // per-hctx q->nr_requests
                
                -> blk_mq_alloc_rq_map() // alloc tags->rqs and tags->static_rqs arrary
                -> blk_mq_alloc_rqs() // alloc pages to carry the (request + driver payload)
                    -> blk_mq_ops->init_request()

blk_mq_get_request()
    -> blk_mq_rq_ctx_init()
        -> blk_mq_tags_from_data() // hctx->tags or sched_tags
        -> rq = tags->static_rqs[tag] // when w/o io scheduler

request_queue->queue_hw_ctx[] -> sched_tags -> static_rqs[] 
                   |                              /       
                   V                   ___ ___ __/____ ___
                  tags                |   |   |   |   |   |  w/ scheduler
                   |                  |___|___|___|___|___| <------------+
                   |                            /\                        \
                   |                           /  \                        \
                  /                  _________/    \___________             \
                 /                  | request + driver payload |             \
------------------------------------------------                              \  
               /                                                               |   
              |   maybe shared (Multiple LUs SCSI HBA, or Multiple ns NVMe)    |
              V                                                                |  
 tag_set->tags[] ---> rqs  [ ][ ][ ][ ][ ][ ] a reverse mapping from tag to request 
                 |                                                          /   
                 +--> static_rqs[]                                         /          
                                /                                         /
                     ___ ___ __/____ ___                                 /
                    |   |   |   |   |   |  w/o  scheduler               /
                    |___|___|___|___|___|  <---------------------------
                              /\
                             /  \
                   _________/    \___________
                  | request + driver payload |

• mq-deadline
• bfq (budget fair queuing) Improved over cfq, but essentially on slow device. traditional I/O scheduler, high per-operation overhead
• kyber lightweight, intended for fast multiqueue devices

BFQ is a complex scheduler that is designed to provide good interactive
response, especially on those slower devices. It has a relatively high 
per-operation overhead, which is justified when the I/O operations 
themselves are slow and expensive. This complexity may not make sense,
though, in situations where I/O operations are cheap and throughput is 
a primary concern. When running a server workload using solid-state 
devices, it may be better to run a much simpler scheduler that allows 
for request merging and perhaps some simple policies, but which mostly 
stays out of the way.

Except for the lightweight, the intention of kyber is to keep low level
latency of prioritized requests.
There are 3 domain there: READ, SYNC_WRITE, and OTHER (async writes, discard)
Note: some request will bypass the io scheduler, such as flush.

kyber_dispatch_request()
	-> kyber_dispatch_cur_domain()

>>>>
	rqs = &khd->rqs[khd->cur_domain];
	rq = list_first_entry_or_null(rqs, struct request, queuelist);

	/*
	 * If there wasn't already a pending request and we haven't flushed the
	 * software queues yet, flush the software queues and check again.
	 */
	if (!rq && !*flushed) {
		kyber_flush_busy_ctxs(khd, hctx);
		// flush the requests from the ctx software queue to kyber queue.
		*flushed = true;
		rq = list_first_entry_or_null(rqs, struct request, queuelist);
	}

	if (rq) {
		nr = kyber_get_domain_token(kqd, khd, hctx);
			-> __sbitmap_queue_get()
		if (nr >= 0) {
			khd->batching++;
			rq_set_domain_token(rq, nr);
			list_del_init(&rq->queuelist);
			return rq;
		}
	}
>>>>
Every domain has its own queue depth, look at the default ones:
static const unsigned int kyber_depth[] = {
	[KYBER_READ] = 256,
	[KYBER_SYNC_WRITE] = 128,
	[KYBER_OTHER] = 64,
};
It is similar with the blk-mq tags, but it is called token here.

The queue size of every domain will be resized based on the req latency.

kyber exploit the blk_stat mechanism to collect latency statistics and Adjust
the domain queue size in the blk_stat timer fn.

static int kyber_lat_status(struct blk_stat_callback *cb,
			    unsigned int sched_domain, u64 target)
{
	u64 latency;

	if (!cb->stat[sched_domain].nr_samples)
		return NONE;

	latency = cb->stat[sched_domain].mean;
	if (latency >= 2 * target)
		return AWFUL;
	else if (latency > target)
		return BAD;
	else if (latency <= target / 2)
		return GREAT;
	else /* (latency <= target) */
		return GOOD;
}

static void kyber_stat_timer_fn(struct blk_stat_callback *cb)
{
	struct kyber_queue_data *kqd = cb->data;
	int read_status, write_status;

	read_status = kyber_lat_status(cb, KYBER_READ, kqd->read_lat_nsec);
	write_status = kyber_lat_status(cb, KYBER_SYNC_WRITE, kqd->write_lat_nsec);

	kyber_adjust_rw_depth(kqd, KYBER_READ, read_status, write_status);
	kyber_adjust_rw_depth(kqd, KYBER_SYNC_WRITE, write_status, read_status);
	kyber_adjust_other_depth(kqd, read_status, write_status,
				 cb->stat[KYBER_OTHER].nr_samples != 0);

	/*
	 * Continue monitoring latencies if we aren't hitting the targets or
	 * we're still throttling other requests.
	 */
	if (!blk_stat_is_active(kqd->cb) &&
	    ((IS_BAD(read_status) || IS_BAD(write_status) ||
	      kqd->domain_tokens[KYBER_OTHER].sb.depth < kyber_depth[KYBER_OTHER])))
		blk_stat_activate_msecs(kqd->cb, 100);
}


There is no insert_requests callbacks in kyber, so the merge/sort will be done
by the ctx software queue.

blk_mq_freeze_queue() will increase the q->mq_freeze_depth and wait until the
q->q_usage_counter.

This two counter play very important role in blk-mq path.
q_usage_counter covers nearly all the path of blk-mq, more importantly, every
request will hold one reference of q_usage_counter until it is freed.

blk_mq_make_request()
    -> blk_mq_get_request()
        -> blk_queue_enter_live()
	// add 1 here

blk_mq_free_request()
    -> blk_queue_exit()
Other other hand, the mq_freeze_depth will gate blk-mq path.

generic_make_request()
    -> blk_queue_enter()
    >>>>
    ret = wait_event_interruptible(q->mq_freeze_wq,
                !atomic_read(&q->mq_freeze_depth) ||
                    blk_queue_dying(q));
    >>>>
Therfore, we know that when the blk_mq_free_queue() returns, all the requests
has been drained and no new request will enter the io path.

__blk_mq_insert_request()
    -> __blk_mq_insert_request()
    -> blk_mq_hctx_mark_pending()
        -> sbitmap_set_bit(&hctx->ctx_map, ctx->index_hw);

blk_mq_flush_busy_ctxs()
    -> sbitmap_for_each_set(&hctx->ctx_map, flush_busy_ctx, &data);

4b855ad (blk-mq: Create hctx for each present CPU)

302ad8c (nvme: Complete all stuck requests)

I am not doing a hot unplug and the replug, I use KVM and add a previously
not available CPU.

    WARN_ON(!cpumask_test_cpu(raw_smp_processor_id(), hctx->cpumask) &&
        cpu_online(hctx->next_cpu));

blk_mq_alloc_tag_set()
    -> blk_mq_update_queue_map()
        -> nvme_pci_map_queues()
            -> blk_mq_pci_map_queues()
>>>>
    for (queue = 0; queue < set->nr_hw_queues; queue++) {
        mask = pci_irq_get_affinity(pdev, queue);
        if (!mask)
            goto fallback;

        for_each_cpu(cpu, mask)
            set->mq_map[cpu] = queue;
    }

    return 0;
>>>>
Then in 
blk_mq_init_allocated_queue()
    -> blk_mq_map_swqueue()
>>>>
    for_each_present_cpu(i) {
        hctx_idx = q->mq_map[i];
        >>>>
        ctx = per_cpu_ptr(q->queue_ctx, i);
        hctx = blk_mq_map_queue(q, i);

        cpumask_set_cpu(i, hctx->cpumask);
        ctx->index_hw = hctx->nr_ctx;
        hctx->ctxs[hctx->nr_ctx++] = ctx;
    }
>>>>

nvme_alloc_ns()
    -> device_add_disk()
        -> blk_register_queue()
            -> __blk_mq_register_dev()
                -> echo hctx blk_mq_register_hctx()
>>>>
    ret = kobject_add(&hctx->kobj, &q->mq_kobj, "%u", hctx->queue_num);
    if (ret)
        return ret;

    hctx_for_each_ctx(hctx, ctx, i) {
        ret = kobject_add(&ctx->kobj, &hctx->kobj, "cpu%u", ctx->cpu);
        if (ret)
            break;
    }

>>>>

will@will-ThinkCentre-M910s:/sys/block/nvme0n1/mq$ tree
.
├── 0
│   ├── cpu0
│   ├── cpu_list
│   ├── nr_reserved_tags
│   └── nr_tags
├── 1
│   ├── cpu1
│   ├── cpu_list
│   ├── nr_reserved_tags
│   └── nr_tags
├── 2
│   ├── cpu2
│   ├── cpu_list
│   ├── nr_reserved_tags
│   └── nr_tags
├── 3
│   ├── cpu3
│   ├── cpu_list
│   ├── nr_reserved_tags
│   └── nr_tags
├── 4
│   ├── cpu4
│   ├── cpu_list
│   ├── nr_reserved_tags
│   └── nr_tags
├── 5
│   ├── cpu5
│   ├── cpu_list
│   ├── nr_reserved_tags
│   └── nr_tags
├── 6
│   ├── cpu6
│   ├── cpu_list
│   ├── nr_reserved_tags
│   └── nr_tags
└── 7
    ├── cpu7
    ├── cpu_list
    ├── nr_reserved_tags
    └── nr_tags

16 directories, 24 files

blk_mq_make_request()
>>>>
    rq = blk_mq_get_request(q, bio, bio->bi_opf, &data);
    // blk_mq_get_ctx() will invoke get_cpu() to disable the preempt
>>>>
    } else if (q->nr_hw_queues > 1 && is_sync) {
        blk_mq_put_ctx(data.ctx); // preempt enabled again.
        blk_mq_bio_to_request(rq, bio);
        // There seem to be a gap here with preempt enabled and the 
        // current task maybe migrated to other cpu.
        blk_mq_try_issue_directly(data.hctx, rq, &cookie);
    }
>>>> Let's look into the blk_mq_try_issue_directly()

>>>>
    if (!(hctx->flags & BLK_MQ_F_BLOCKING)) { 
        // nvme doesn't have this BLK_MQ_F_BLOCKING
        rcu_read_lock(); // preempt disable here
        __blk_mq_try_issue_directly(hctx, rq, cookie, false);
        rcu_read_unlock();
    }
>>>>

blk_mq_requeue_work()
    -> blk_mq_run_hw_queues()  // async = false
        -> echo hctx run blk_mq_run_hw_queue()

blk_freeze_queue_start()
    -> blk_mq_run_hw_queues() // async = false

blk_mq_init_allocated_queue()
    -> blk_mq_add_queue_tag_set()

static void blk_mq_add_queue_tag_set(struct blk_mq_tag_set *set,
                     struct request_queue *q)
{
    q->tag_set = set;

    mutex_lock(&set->tag_list_lock);

    /*
     * Check to see if we're transitioning to shared (from 1 to 2 queues).
     */
    if (!list_empty(&set->tag_list) &&
        !(set->flags & BLK_MQ_F_TAG_SHARED)) {
        set->flags |= BLK_MQ_F_TAG_SHARED;
        /* update existing queue */
        blk_mq_update_tag_set_depth(set, true);
        /*
         Actually, only the first request_queue on this tag_set will be set here.
         The blk-mq will be frozen and the hctxs associated with request_queue
         will be set BLK_MQ_F_TAG_SHARED.
         */
    }
    if (set->flags & BLK_MQ_F_TAG_SHARED)
        queue_set_hctx_shared(q, true); // Set the BLK_MQ_F_TAG_SHARED
    list_add_tail_rcu(&q->tag_set_list, &set->tag_list);

    mutex_unlock(&set->tag_list_lock);
}

blk_mq_init_allocated_queue()
    -> blk_mq_add_queue_tag_set()
    -> blk_mq_map_swqueue()
>>>>
    queue_for_each_hw_ctx(q, hctx, i) {
    >>>>
        hctx->tags = set->tags[i];
        WARN_ON(!hctx->tags);
    >>>>
    }
>>>>

blk_mq_get_request()
    -> blk_mq_rq_ctx_init()
Or 
blk_mq_get_driver_tag()
>>>>
        if (blk_mq_tag_busy(data.hctx)) {
            rq->rq_flags |= RQF_MQ_INFLIGHT;
            atomic_inc(&data.hctx->nr_active);
        }
>>>>
blk_mq_tag_busy() will only return true when BLK_MQ_F_TAG_SHARED is set.
In __blk_mq_tag_busy(), the BLK_MQ_S_TAG_ACTIVE will be set and
hctx->tags->active_queues will be increased.

In addition, the hctx->nr_active will also be increased.

The hctx->tags->nr_actives is the count of request_queues that use the driver tag.
The hctx->nr_active is the count of driver tags used by the hctx itself

Where will be these two values used ?

blk_mq_get_request()/blk_mq_get_driver_tag()
    -> blk_mq_get_tag()
        -> __blk_mq_get_tag() // if !BLK_MQ_REQ_INTERNAL
            -> hctx_may_queue()

static inline bool hctx_may_queue(struct blk_mq_hw_ctx *hctx,
                  struct sbitmap_queue *bt)
{
    unsigned int depth, users;

    if (!hctx || !(hctx->flags & BLK_MQ_F_TAG_SHARED))
        return true;
    if (!test_bit(BLK_MQ_S_TAG_ACTIVE, &hctx->state))
        return true;

    /*
     * Don't try dividing an ant
     */
    if (bt->sb.depth == 1)
        return true;

    users = atomic_read(&hctx->tags->active_queues);
    if (!users)
        return true;

    /*
     * Allow at least some tags
     */
    depth = max((bt->sb.depth + users - 1) / users, 4U);
    return atomic_read(&hctx->nr_active) < depth;
}
It is easy to understand the source code above. It just averages the tag depth to
among the active request_queues to ensure fairness. But it look like not fair
when a high workload on LU0 and a relatively low workload on LU1. Another sad
thing is the active_queues will only be decreased when the queue is timed out or
exits( Look at the blk_mq_tag_idle() ). This indicates that the tags will be shared 
between the LUs no matter whether there is workload on the LUs.

__blk_mq_put_driver_tag()/blk_mq_free_request()
>>>>
    if (rq->rq_flags & RQF_MQ_INFLIGHT) {
        rq->rq_flags &= ~RQF_MQ_INFLIGHT;
        atomic_dec(&hctx->nr_active);
    }
>>>>

hctx->nr_active will be decreased here.

a> driver tag is used up
At the moment, the req will be requeued to hctx->dispatch list. The hctx will be
re-run when the driver tag is freed.
b> the req inserted into ctx swqueue or IO scheduler cannot be dispatched when there
is residual reqs in the hctx->dispatch list. In blk_mq_sched_dispatch_requests(), we call 
blk_mq_sched_mark_restart() after we dispatch requests left over on our hardware queue 
dispatch list. This is so we'll go back and dispatch requests from the ctx
swqueue or IO scheduler queue.
c> merge into ctx swqueue or IO scheduler queue. This will occur when there are
residual reqs on the queues above. The reqs could be issued through the method
in a and b.

Regarding the a.
blk_mq_mark_tag_wait() will be invoked by blk_mq_dispatch_rq_list().
(A commit that optimize this path f906a6a blk-mq: improve tag waiting setup for non-shared tags)
For the non-shared-tags case, the BLK_MQ_S_SCHED_RESTART flag will be enough.
But for the shared-tags case, it uses the sbq_wake_up().

Regarding the b.

Look at the comment of blk_mq_sched_restart()
Called after a driver tag has been freed to check whether a hctx needs to
be restarted. Restarts @hctx if its tag set is not shared. Restarts hardware
queues in a round-robin fashion if the tag set of @hctx is shared with other
hardware queues.
Look at the round-robin part:
>>>>
        list_for_each_entry_rcu_rr(q, queue, &set->tag_list,
                       tag_set_list) {
            queue_for_each_hw_ctx(q, hctx2, i)
                if (hctx2->tags == tags &&
                    blk_mq_sched_restart_hctx(hctx2))
                    goto done;
        }
>>>>
blk_mq_sched_restart_hctx() will run the hctx in async fashion if has work
pending on it.

__blkdev_direct_IO_simple()
>>>>
qc = submit_bio(&bio);
    for (;;) {
        set_current_state(TASK_UNINTERRUPTIBLE);
        if (!READ_ONCE(bio.bi_private))
            break;
        if (!(iocb->ki_flags & IOCB_HIPRI) ||
            !blk_mq_poll(bdev_get_queue(bdev), qc))
            io_schedule();
    }
>>>>

try_to_wake_up()
    -> ttwu_queue()
        -> ttwu_do_activate()
            -> ttwu_do_wakeup()
                -> p->state = TASK_RUNNING

>>>>
    while (!need_resched()) {
        int ret;

        hctx->poll_invoked++;

        ret = q->mq_ops->poll(hctx, rq->tag);
        >>>>
        if (current->state == TASK_RUNNING)
            return true;
        if (ret < 0)
            break;
        cpu_relax();
    }
>>>>

w/o blk-mq polling
  read : io=131072KB, bw=79007KB/s, iops=19751, runt=  1659msec
    clat (usec): min=27, max=253, avg=49.46, stdev=33.61

w/ blk-mq polling
  read : io=131072KB, bw=97019KB/s, iops=24254, runt=  1351msec
    clat (usec): min=19, max=302, avg=40.90, stdev=34.31