blk-mq: reimplement timeout handling

Currently, blk-mq timeout path synchronizes against the usual issue/completion path using a complex scheme involving atomic bitflags, REQ_ATOM_*, memory barriers and subtle memory coherence rules. Unfortunatley, it contains quite a few holes.

It's pretty easy to make blk_mq_check_expired() terminate a later instance of a request. If we induce 5 sec delay before time_after_eq() test in blk_mq_check_expired(), shorten the timeout to 2s, and issue back-to-back large IOs, blk-mq starts timing out requests spuriously pretty quickly. Nothing actually timed out. It just made the call on a recycle instance of a request and then terminated a later instance long after the original instance finished. The scenario isn't theoretical either.

This patchset replaces the broken synchronization mechanism with a RCU and generation number based one. Please read the patch description of the second path for more details.

Oleg, Peter, I'd really appreciate if you guys can go over the reported breakages and the new implementation.

(quoted diff) +18 -0

+static u64 blk_mq_rq_aborted_gstate(struct request *rq)
+{
+	unsigned int start;
+	u64 aborted_gstate;
+
+	do {
+		start = u64_stats_fetch_begin(&rq->aborted_gstate_sync);
+		aborted_gstate = rq->aborted_gstate;
+	} while (u64_stats_fetch_retry(&rq->aborted_gstate_sync, start));
+
+	return aborted_gstate;
+}
 
+	/* if in-flight && overdue, mark for abortion */
+	if ((gstate & MQ_RQ_STATE_MASK) == MQ_RQ_IN_FLIGHT &&
+	    time_after_eq(jiffies, deadline)) {
+		u64_stats_update_begin(&rq->aborted_gstate_sync);
+		rq->aborted_gstate = gstate;
+		u64_stats_update_end(&rq->aborted_gstate_sync);

After the recent updates to use generation number and state based synchronization, we can easily replace REQ_ATOM_STARTED usages by adding an extra state to distinguish completed but not yet freed state.

Add MQ_RQ_COMPLETE and replace REQ_ATOM_STARTED usages with blk_mq_rq_state() tests. REQ_ATOM_STARTED no longer has any users left and is removed.

Signed-off-by Tejun Heo <[email protected]>

---
 block/blk-mq-debugfs.c |  4 +---
 block/blk-mq.c         | 39 ++++++++-------------------------------
 block/blk-mq.h         |  1 +
 block/blk.h            |  1 -
 4 files changed, 10 insertions(+), 35 deletions(-)

block/blk-mq-debugfs.c +1 -3

index b56a4f3..8adc837 100644
@@ -271,7 +271,6 @@ static const char *const cmd_flag_name[] = {
 #define RQF_NAME(name) [ilog2((__force u32)RQF_##name)] = #name
 static const char *const rqf_name[] = {
 	RQF_NAME(SORTED),
-	RQF_NAME(STARTED),
 	RQF_NAME(QUEUED),
 	RQF_NAME(SOFTBARRIER),
 	RQF_NAME(FLUSH_SEQ),

@@ -295,7 +294,6 @@ static const char *const rqf_name[] = {
 #define RQAF_NAME(name) [REQ_ATOM_##name] = #name
 static const char *const rqaf_name[] = {
 	RQAF_NAME(COMPLETE),
-	RQAF_NAME(STARTED),
 	RQAF_NAME(POLL_SLEPT),
 };
 #undef RQAF_NAME

@@ -409,7 +407,7 @@ static void hctx_show_busy_rq(struct request *rq, void *data, bool reserved)
 	const struct show_busy_params *params = data;
 
 	if (blk_mq_map_queue(rq->q, rq->mq_ctx->cpu) == params->hctx &&
-	    test_bit(REQ_ATOM_STARTED, &rq->atomic_flags))
+	    blk_mq_rq_state(rq) != MQ_RQ_IDLE)
 		__blk_mq_debugfs_rq_show(params->m,
 					 list_entry_rq(&rq->queuelist));
 }

block/blk-mq.c +6 -13

index 4ebac33..663069d 100644
@@ -482,7 +482,7 @@ void blk_mq_free_request(struct request *rq)
 	if (blk_rq_rl(rq))
 		blk_put_rl(blk_rq_rl(rq));
 
-	clear_bit(REQ_ATOM_STARTED, &rq->atomic_flags);
+	blk_mq_rq_update_state(rq, MQ_RQ_IDLE);
 	clear_bit(REQ_ATOM_POLL_SLEPT, &rq->atomic_flags);
 	if (rq->tag != -1)
 		blk_mq_put_tag(hctx, hctx->tags, ctx, rq->tag);

@@ -530,7 +530,7 @@ static void __blk_mq_complete_request(struct request *rq)
 	int cpu;
 
 	WARN_ON_ONCE(blk_mq_rq_state(rq) != MQ_RQ_IN_FLIGHT);
-	blk_mq_rq_update_state(rq, MQ_RQ_IDLE);
+	blk_mq_rq_update_state(rq, MQ_RQ_COMPLETE);
 
 	if (rq->internal_tag != -1)
 		blk_mq_sched_completed_request(rq);

@@ -610,7 +610,7 @@ EXPORT_SYMBOL(blk_mq_complete_request);
 
 int blk_mq_request_started(struct request *rq)
 {
-	return test_bit(REQ_ATOM_STARTED, &rq->atomic_flags);
+	return blk_mq_rq_state(rq) != MQ_RQ_IDLE;
 }
 EXPORT_SYMBOL_GPL(blk_mq_request_started);
 

@@ -629,7 +629,6 @@ void blk_mq_start_request(struct request *rq)
 	}
 
 	WARN_ON_ONCE(blk_mq_rq_state(rq) != MQ_RQ_IDLE);
-	WARN_ON_ONCE(test_bit(REQ_ATOM_STARTED, &rq->atomic_flags));
 
 	/*
 	 * Mark @rq in-flight which also advances the generation number,

@@ -647,8 +646,6 @@ void blk_mq_start_request(struct request *rq)
 	blk_add_timer(rq);
 	write_seqcount_end(&rq->gstate_seqc);
 
-	set_bit(REQ_ATOM_STARTED, &rq->atomic_flags);
-
 	if (q->dma_drain_size && blk_rq_bytes(rq)) {
 		/*
 		 * Make sure space for the drain appears.  We know we can do

@@ -661,13 +658,9 @@ void blk_mq_start_request(struct request *rq)
 EXPORT_SYMBOL(blk_mq_start_request);
 
 /*
- * When we reach here because queue is busy, REQ_ATOM_COMPLETE
- * flag isn't set yet, so there may be race with timeout handler,
- * but given rq->deadline is just set in .queue_rq() under
- * this situation, the race won't be possible in reality because
- * rq->timeout should be set as big enough to cover the window
- * between blk_mq_start_request() called from .queue_rq() and
- * clearing REQ_ATOM_STARTED here.
+ * When we reach here because queue is busy, it's safe to change the state
+ * to IDLE without checking @rq->aborted_gstate because we should still be
+ * holding the RCU read lock and thus protected against timeout.
  */
 static void __blk_mq_requeue_request(struct request *rq)
 {

block/blk-mq.c +0 -4

 		if (q->dma_drain_size && blk_rq_bytes(rq))
 			rq->nr_phys_segments--;

@@ -786,18 +779,6 @@ static void blk_mq_rq_timed_out(struct request *req, bool reserved)
 	const struct blk_mq_ops *ops = req->q->mq_ops;
 	enum blk_eh_timer_return ret = BLK_EH_RESET_TIMER;
 
-	/*
-	 * We know that complete is set at this point. If STARTED isn't set
-	 * anymore, then the request isn't active and the "timeout" should
-	 * just be ignored. This can happen due to the bitflag ordering.

block/blk-mq.c +1 -5

@@ -824,9 +805,6 @@ static void blk_mq_check_expired(struct blk_mq_hw_ctx *hctx,
 	unsigned long gstate, deadline;
 	int start;
 
-	if (!test_bit(REQ_ATOM_STARTED, &rq->atomic_flags))
-		return;
-
 	/* read coherent snapshots of @rq->state_gen and @rq->deadline */
 	do {
 		start = read_seqcount_begin(&rq->gstate_seqc);

@@ -2944,8 +2922,7 @@ static bool blk_mq_poll_hybrid_sleep(struct request_queue *q,
 
 	hrtimer_init_sleeper(&hs, current);
 	do {
-		if (test_bit(REQ_ATOM_STARTED, &rq->atomic_flags) &&
-		    blk_mq_rq_state(rq) != MQ_RQ_IN_FLIGHT)
+		if (blk_mq_rq_state(rq) == MQ_RQ_COMPLETE)
 			break;
 		set_current_state(TASK_UNINTERRUPTIBLE);
 		hrtimer_start_expires(&hs.timer, mode);

block/blk-mq.h +1 -0

index 760e7ed..e1eaeb9 100644
@@ -34,6 +34,7 @@ struct blk_mq_ctx {
 enum mq_rq_state {
 	MQ_RQ_IDLE		= 0,
 	MQ_RQ_IN_FLIGHT		= 1,
+	MQ_RQ_COMPLETE		= 2,
 
 	MQ_RQ_STATE_BITS	= 2,
 	MQ_RQ_STATE_MASK	= (1 << MQ_RQ_STATE_BITS) - 1,

block/blk.h +0 -1

index 9cb2739..a68dbe3 100644
@@ -124,7 +124,6 @@ void blk_account_io_done(struct request *req);
  */
 enum rq_atomic_flags {
 	REQ_ATOM_COMPLETE = 0,
-	REQ_ATOM_STARTED,
 
 	REQ_ATOM_POLL_SLEPT,
 };

include/linux/blkdev.h +3 -0

index 8089ca1..e6cfe4b3 100644
@@ -228,6 +230,27 @@ struct request {
 
 	unsigned short write_hint;
 
+	/*
+	 * On blk-mq, the lower bits of ->gstate carry the MQ_RQ_* state
+	 * value and the upper bits the generation number which is

After the recent updates to use generation number and state based synchronization, we can easily replace REQ_ATOM_STARTED usages by adding an extra state to distinguish completed but not yet freed state.

Add MQ_RQ_COMPLETE and replace REQ_ATOM_STARTED usages with blk_mq_rq_state() tests. REQ_ATOM_STARTED no longer has any users left and is removed.

Signed-off-by Tejun Heo <[email protected]>

block/blk-mq.h +2 -0

+	WRITE_ONCE(rq->gstate, new_val);
+}

Oleg, Peter, I'd really appreciate if you guys can go over the reported breakages and the new implementation.

Please send this to linux-block so that it can be properly reviewed.

Quoted 17 lines

block/blk-mq.c +0 -12

@@ -786,18 +779,6 @@ static void blk_mq_rq_timed_out(struct request *req, bool reserved)
 	const struct blk_mq_ops *ops = req->q->mq_ops;
 	enum blk_eh_timer_return ret = BLK_EH_RESET_TIMER;
 
-	/*
-	 * We know that complete is set at this point. If STARTED isn't set
-	 * anymore, then the request isn't active and the "timeout" should
-	 * just be ignored. This can happen due to the bitflag ordering.
-	 * Timeout first checks if STARTED is set, and if it is, assumes
-	 * the request is active. But if we race with completion, then
-	 * both flags will get cleared. So check here again, and ignore
-	 * a timeout event with a request that isn't active.
-	 */
-	if (!test_bit(REQ_ATOM_STARTED, &req->atomic_flags))
-		return;
-
 	if (ops->timeout)

block/blk-mq.c static void blk_mq_rq_timed_out(struct request *req, bool reserved) · line 783

Quoted 1 line

block/blk-mq.c +0 -0

 		ret = ops->timeout(req, reserved);

The BLK_EH_RESET_TIMER case has not been covered here. In that case, the timer will be re-armed, but the gstate and aborted_gstate are not updated and still equal with echo other. Consequently, when the request is completed later, the __blk_mq_complete_request() will be missed, then the request will expire again. The aborted_gstate should be updated in the BLK_EH_RESET_TIMER case.

Quoted 6 lines

static void __blk_mq_requeue_request(struct request *rq) {

block/blk-mq.c +0 -0

@@ -679,7 +672,7 @@ static void __blk_mq_requeue_request(struct request *rq)
 	wbt_requeue(q->rq_wb, &rq->issue_stat);
 	blk_mq_sched_requeue_request(rq);
 

block/blk-mq.c static void __blk_mq_requeue_request(struct request *rq) · line 676

Quoted 3 lines

block/blk-mq.c +1 -1

-	if (test_and_clear_bit(REQ_ATOM_STARTED, &rq->atomic_flags)) {
+	if (blk_mq_rq_state(rq) != MQ_RQ_IDLE) {
 		blk_mq_rq_update_state(rq, MQ_RQ_IDLE);

The MQ_RQ_IDLE looks confused here. It is not freed , but idled. And when the requeued request is started again, the generation number will be increased. But it is not a recycle instance of the request. Maybe another state needed here ?

Quoted 8 lines · Tejun Heo

After the recent updates to use generation number and state based synchronization, we can easily replace REQ_ATOM_STARTED usages by adding an extra state to distinguish completed but not yet freed state.

Add MQ_RQ_COMPLETE and replace REQ_ATOM_STARTED usages with blk_mq_rq_state() tests. REQ_ATOM_STARTED no longer has any users left and is removed.

Where are the promised in patch 5/6 performance results?

include/linux/blkdev.h struct request { · line 252

Quoted 6 lines

include/linux/blkdev.h +6 -0

+	/*
+	 * ->aborted_gstate is used by the timeout to claim a specific
+	 * recycle instance of this request.  See blk_mq_timeout_work().
+	 */
+	struct u64_stats_sync aborted_gstate_sync;
+	u64 aborted_gstate;

So I dislike that u64_stats_sync thingy. Esp when used on a single variable like this.

There are two alternatives, but I don't understand the code well enough to judge the trade-offs.

1) use gstate_seq for this too; yes it will add some superfluous instructions on 64bit targets, but if timeouts are a slow path this might not matter.

2) use the pattern we use for cfs_rq::min_vruntime; namely:

u64 aborted_gstate

#ifdef CONFIG_64BIT
	u64 aborted_gstate_copy;

#endif

static inline void blk_mq_rq_set_abort(struct rq *rq, u64 gstate)

{
	rq->aborted_gstate = gstate;
#ifdef CONFIG_64BIT
	smp_wmb();
	rq->aborted_gstate_copy = gstate;

#endif
}

static inline u64 blk_mq_rq_get_abort(struct rq *rq) {

#ifdef CONFIG_64BIT
	u64 abort, copy;

	do {
		copy = rq->aborted_gstate_copy;
		smp_rmb();
		abort = rq->aborted_gstate;
	} while (abort != copy);

	return abort;
#else
	return rq->aborted_gstate;

#endif
}

which is actually _faster_ than the u64_stats_sync stuff (for a single variable).

But it might not matter; I just dislike that thing, could be me.

include/linux/blkdev.h struct request { · line 245

Quoted 2 lines

include/linux/blkdev.h +2 -0

+	seqcount_t gstate_seqc;
+	u64 gstate;

We typically name seqcount_t thingies _seq.

block/blk-mq.h extern void blk_mq_rq_timed_out(struct request *req, bool reserved); · line 129

Quoted 11 lines · Tejun Heo

block/blk-mq.h +11 -0

+static inline void blk_mq_rq_update_state(struct request *rq,
+					  enum mq_rq_state state)
+{
+	u64 new_val = (rq->gstate & ~MQ_RQ_STATE_MASK) | state;
+
+	if (state == MQ_RQ_IN_FLIGHT) {
+		WARN_ON_ONCE(blk_mq_rq_state(rq) != MQ_RQ_IDLE);
+		new_val += MQ_RQ_GEN_INC;
+	}
+
+	/* avoid exposing interim values */

My paranoia would like to see READ_ONCE() on the rq->gstate load above as well, that makes it a fully explicit load-store operation.

Hello, again.

Sorry, I missed part of your comment in the previous reply.

Quoted 6 lines · jianchao.wang

Quoted 6 lines

static void __blk_mq_requeue_request(struct request *rq) {

block/blk-mq.c +0 -0

@@ -679,7 +672,7 @@ static void __blk_mq_requeue_request(struct request *rq)
 	wbt_requeue(q->rq_wb, &rq->issue_stat);
 	blk_mq_sched_requeue_request(rq);
 

Quoted 8 lines

block/blk-mq.c static void __blk_mq_requeue_request(struct request *rq) · line 676

Quoted 3 lines

block/blk-mq.c +1 -1

-	if (test_and_clear_bit(REQ_ATOM_STARTED, &rq->atomic_flags)) {
+	if (blk_mq_rq_state(rq) != MQ_RQ_IDLE) {
 		blk_mq_rq_update_state(rq, MQ_RQ_IDLE);

The MQ_RQ_IDLE looks confused here. It is not freed , but idled. And when the requeued request is started again, the generation number will be increased. But it is not a recycle instance of the request. Maybe another state needed here ?

I don't quite follow it. At this point, the request can't be in-flight on the device side and is scheduled for re-submission. I'm not sure the distinction from IDLE is necessary. Am I missing something?

Thanks.

Currently, blk-mq protects only the issue path with RCU. This patch puts the completion path under the same RCU protection. This will be used to synchronize issue/completion against timeout by later patches, which will also add the comments.

Signed-off-by Tejun Heo <[email protected]>

---
 block/blk-mq.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)

block/blk-mq.c +4 -2

index 1109747..acf4fbb 100644
@@ -568,11 +568,23 @@ static void __blk_mq_complete_request(struct request *rq)
 void blk_mq_complete_request(struct request *rq)
 {
 	struct request_queue *q = rq->q;
+	struct blk_mq_hw_ctx *hctx = blk_mq_map_queue(q, rq->mq_ctx->cpu);
+	int srcu_idx;
 
 	if (unlikely(blk_should_fake_timeout(q)))
 		return;
-	if (!blk_mark_rq_complete(rq))
-		__blk_mq_complete_request(rq);
+
+	if (!(hctx->flags & BLK_MQ_F_BLOCKING)) {

block/blk-mq.c +0 -0

 }
 EXPORT_SYMBOL(blk_mq_complete_request);
 

Just don't quite understand the strict definition of "generation" you said. A allocation->free cycle is a generation ? or a idle->in-flight cycle is a generation? The idle->in-flight cycle could include the requeue case as above. Can you clarify this?

Hello,

Quoted 4 lines · jianchao.wang

Just don't quite understand the strict definition of "generation" you said. A allocation->free cycle is a generation ? or a idle->in-flight cycle is a generation? The idle->in-flight cycle could include the requeue case as above. Can you clarify this?

So, a request is

* IN_FLIGHT, if it can be completed by the lower level driver

* COMPLETE, if the lower level driver indicated completion but block layer is still processing.

* IDLE, if neither of the above two.

and generation is bumped up on IDLE -> IN_FLIGHT to distinguish different IN_FLIGHT instances.

Thanks.