[PATCH v3 0/4] blk-mq: Fix two causes of IO stalls found in reboot testing

[PATCH v3 0/4] blk-mq: Fix two causes of IO stalls found in reboot testing

[Douglas Anderson]

While doing reboot testing, I found that occasionally my device would
trigger the hung task detector.  Many tasks were stuck waiting for the
a blkdev mutex, but at least one task in the system was always sitting
waiting for IO to complete (and holding the blkdev mutex).  One
example of a task that was just waiting for its IO to complete on one
reboot:

 udevd           D    0  2177    306 0x00400209
 Call trace:
  __switch_to+0x15c/0x17c
  __schedule+0x6e0/0x928
  schedule+0x8c/0xbc
  schedule_timeout+0x9c/0xfc
  io_schedule_timeout+0x24/0x48
  do_wait_for_common+0xd0/0x160
  wait_for_completion_io_timeout+0x54/0x74
  blk_execute_rq+0x9c/0xd8
  __scsi_execute+0x104/0x198
  scsi_test_unit_ready+0xa0/0x154
  sd_check_events+0xb4/0x164
  disk_check_events+0x58/0x154
  disk_clear_events+0x74/0x110
  check_disk_change+0x28/0x6c
  sd_open+0x5c/0x130
  __blkdev_get+0x20c/0x3d4
  blkdev_get+0x74/0x170
  blkdev_open+0x94/0xa8
  do_dentry_open+0x268/0x3a0
  vfs_open+0x34/0x40
  path_openat+0x39c/0xdf4
  do_filp_open+0x90/0x10c
  do_sys_open+0x150/0x3c8
  ...

I've reproduced this on two systems: one boots from an internal UFS
disk and one from eMMC.  Each has a card reader attached via USB with
an SD card plugged in.  On the USB-attached SD card is a disk with 12
partitions (a Chrome OS test image), if it matters.  The system
doesn't do much with the USB disk other than probe it (it's plugged in
my system to help me recover).

From digging, I believe that there are two separate but related
issues.  Both issues relate to the SCSI code saying that there is no
budget.

I have done testing with only one or the other of the two patches in
this series and found that I could still encounter hung tasks if only
one of the two patches was applied.  This deserves a bit of
explanation.  To me, it's fairly obvious that the first fix wouldn't
fix the problems talked about in the second patch.  However, it's less
obvious why the second patch doesn't fix the problems in
blk_mq_dispatch_rq_list().  It turns out that it _almost_ does
(problems become much more rare), but I did manage to get a single
trace where the "kick" scheduled by the second patch happened really
quickly.  The scheduled kick then ran and found nothing to do.  This
happened in parallel to a task running in blk_mq_dispatch_rq_list()
which hadn't gotten around to splicing the list back into
hctx->dispatch.  This is why we need both fixes.

Most of my testing has been atop Chrome OS 5.4's kernel tree which
currently has v5.4.30 merged in.  The Chrome OS 5.4 tree also has a
patch by Salman Qazi, namely ("block: Limit number of items taken from
the I/O scheduler in one go").  Reverting that patch didn't make the
hung tasks go away, so I kept it in for most of my testing.

I have also done some testing on mainline Linux (most on what git
describe calls v5.6-rc7-227-gf3e69428b5e2) even without Salman's
patch.  I found that I could reproduce the problems there and that
traces looked about the same as I saw on the downstream branch.  These
patches were also confirmed to fix the problems on mainline.

Chrome OS is currently setup to use the BFQ scheduler and I found that
I couldn't reproduce the problems without BFQ.  As discussed in the
second patch this is believed to be because BFQ sometimes returns
"true" from has_work() but then NULL from dispatch_request().

I'll insert my usual caveat that I'm sending patches to code that I
know very little about.  If I'm making a total bozo patch here, please
help me figure out how I should fix the problems I found in a better
way.

If you want to see a total ridiculous amount of chatter where I
stumbled around a whole bunch trying to figure out what was wrong and
how to fix it, feel free to read <https://crbug.com/1061950>.  I
promise it will make your eyes glaze over right away if this cover
letter didn't already do that.  Specifically comment 79 in that bug
includes a link to my ugly prototype of making BFQ's has_work() more
exact (I only managed it by actually defining _both_ an exact and
inexact function to avoid circular locking problems when it was called
directly from blk_mq_hctx_has_pending()).  Comment 79 also has more
thoughts about alternatives considered.

I don't know if these fixes represent a regression of some sort or are
new.  As per above I could only reproduce with BFQ enabled which makes
it nearly impossible to go too far back with this.  I haven't listed
any "Fixes" tags here, but if someone felt it was appropriate to
backport this to some stable trees that seems like it'd be nice.
Presumably at least 5.4 stable would make sense.

Thanks to Salman Qazi, Paolo Valente, and Guenter Roeck who spent a
bunch of time helping me trawl through some of this code and reviewing
early versions of this patch.

Changes in v3:
- Note why blk_mq_dispatch_rq_list() change is needed.
- ("blk-mq: Add blk_mq_delay_run_hw_queues() API call") new for v3
- Always kick when putting the budget.
- Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
- Totally rewrote commit message.
- ("Revert "scsi: core: run queue...") new for v3.

Changes in v2:
- Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")

Douglas Anderson (4):
  blk-mq: In blk_mq_dispatch_rq_list() "no budget" is a reason to kick
  blk-mq: Add blk_mq_delay_run_hw_queues() API call
  blk-mq: Rerun dispatching in the case of budget contention
  Revert "scsi: core: run queue if SCSI device queue isn't ready and
    queue is idle"

 block/blk-mq.c          | 30 +++++++++++++++++++++++++++---
 block/blk-mq.h          | 14 +++++++++++++-
 drivers/scsi/scsi_lib.c |  7 +------
 include/linux/blk-mq.h  |  1 +
 4 files changed, 42 insertions(+), 10 deletions(-)

-- 
2.26.0.292.g33ef6b2f38-goog

[PATCH v3 1/4] blk-mq: In blk_mq_dispatch_rq_list() "no budget" is a reason to kick

[Douglas Anderson]

In blk_mq_dispatch_rq_list(), if blk_mq_sched_needs_restart() returns
true and the driver returns BLK_STS_RESOURCE then we'll kick the
queue.  However, there's another case where we might need to kick it.
If we were unable to get budget we can be in much the same state as
when the driver returns BLK_STS_RESOURCE, so we should treat it the
same.

It should be noted that even if we add a whole bunch of extra kicking
to the queue in other patches this patch is still important.
Specifically any kicking that happened before we re-spliced leftover
requests into 'hctx->dispatch' wouldn't have found any work, so we
really need to make sure we kick ourselves after we've done the
splicing.

Signed-off-by: Douglas Anderson <dianders@chromium.org>
Reviewed-by: Ming Lei <ming.lei@redhat.com>
---

Changes in v3:
- Note why blk_mq_dispatch_rq_list() change is needed.

Changes in v2: None

 block/blk-mq.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/block/blk-mq.c b/block/blk-mq.c
index f6291ceedee4..7d5f388b7da9 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -1206,6 +1206,7 @@ bool blk_mq_dispatch_rq_list(struct request_queue *q, struct list_head *list,
 	bool no_tag = false;
 	int errors, queued;
 	blk_status_t ret = BLK_STS_OK;
+	bool no_budget_avail = false;
 
 	if (list_empty(list))
 		return false;
@@ -1222,8 +1223,10 @@ bool blk_mq_dispatch_rq_list(struct request_queue *q, struct list_head *list,
 		rq = list_first_entry(list, struct request, queuelist);
 
 		hctx = rq->mq_hctx;
-		if (!got_budget && !blk_mq_get_dispatch_budget(hctx))
+		if (!got_budget && !blk_mq_get_dispatch_budget(hctx)) {
+			no_budget_avail = true;
 			break;
+		}
 
 		if (!blk_mq_get_driver_tag(rq)) {
 			/*
@@ -1318,13 +1321,15 @@ bool blk_mq_dispatch_rq_list(struct request_queue *q, struct list_head *list,
 		 *
 		 * If driver returns BLK_STS_RESOURCE and SCHED_RESTART
 		 * bit is set, run queue after a delay to avoid IO stalls
-		 * that could otherwise occur if the queue is idle.
+		 * that could otherwise occur if the queue is idle.  We'll do
+		 * similar if we couldn't get budget and SCHED_RESTART is set.
 		 */
 		needs_restart = blk_mq_sched_needs_restart(hctx);
 		if (!needs_restart ||
 		    (no_tag && list_empty_careful(&hctx->dispatch_wait.entry)))
 			blk_mq_run_hw_queue(hctx, true);
-		else if (needs_restart && (ret == BLK_STS_RESOURCE))
+		else if (needs_restart && (ret == BLK_STS_RESOURCE ||
+					   no_budget_avail))
 			blk_mq_delay_run_hw_queue(hctx, BLK_MQ_RESOURCE_DELAY);
 
 		blk_mq_update_dispatch_busy(hctx, true);
-- 
2.26.0.292.g33ef6b2f38-goog

[PATCH v3 2/4] blk-mq: Add blk_mq_delay_run_hw_queues() API call

[Douglas Anderson]

We have:
* blk_mq_run_hw_queue()
* blk_mq_delay_run_hw_queue()
* blk_mq_run_hw_queues()

...but not blk_mq_delay_run_hw_queues(), presumably because nobody
needed it before now.  Since we need it for a later patch in this
series, add it.

Signed-off-by: Douglas Anderson <dianders@chromium.org>
---

Changes in v3:
- ("blk-mq: Add blk_mq_delay_run_hw_queues() API call") new for v3

Changes in v2: None

 block/blk-mq.c         | 19 +++++++++++++++++++
 include/linux/blk-mq.h |  1 +
 2 files changed, 20 insertions(+)

diff --git a/block/blk-mq.c b/block/blk-mq.c
index 7d5f388b7da9..f0a89109fb6d 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -1544,6 +1544,25 @@ void blk_mq_run_hw_queues(struct request_queue *q, bool async)
 }
 EXPORT_SYMBOL(blk_mq_run_hw_queues);
 
+/**
+ * blk_mq_delay_run_hw_queues - Run all hardware queues asynchronously.
+ * @q: Pointer to the request queue to run.
+ * @msecs: Microseconds of delay to wait before running the queues.
+ */
+void blk_mq_delay_run_hw_queues(struct request_queue *q, unsigned long msecs)
+{
+	struct blk_mq_hw_ctx *hctx;
+	int i;
+
+	queue_for_each_hw_ctx(q, hctx, i) {
+		if (blk_mq_hctx_stopped(hctx))
+			continue;
+
+		blk_mq_delay_run_hw_queue(hctx, msecs);
+	}
+}
+EXPORT_SYMBOL(blk_mq_delay_run_hw_queues);
+
 /**
  * blk_mq_queue_stopped() - check whether one or more hctxs have been stopped
  * @q: request queue.
diff --git a/include/linux/blk-mq.h b/include/linux/blk-mq.h
index f389d7c724bd..3bbc730eca72 100644
--- a/include/linux/blk-mq.h
+++ b/include/linux/blk-mq.h
@@ -508,6 +508,7 @@ void blk_mq_unquiesce_queue(struct request_queue *q);
 void blk_mq_delay_run_hw_queue(struct blk_mq_hw_ctx *hctx, unsigned long msecs);
 void blk_mq_run_hw_queue(struct blk_mq_hw_ctx *hctx, bool async);
 void blk_mq_run_hw_queues(struct request_queue *q, bool async);
+void blk_mq_delay_run_hw_queues(struct request_queue *q, unsigned long msecs);
 void blk_mq_tagset_busy_iter(struct blk_mq_tag_set *tagset,
 		busy_tag_iter_fn *fn, void *priv);
 void blk_mq_tagset_wait_completed_request(struct blk_mq_tag_set *tagset);
-- 
2.26.0.292.g33ef6b2f38-goog

[PATCH v3 3/4] blk-mq: Rerun dispatching in the case of budget contention

[Douglas Anderson]

If ever a thread running blk-mq code tries to get budget and fails it
immediately stops doing work and assumes that whenever budget is freed
up that queues will be kicked and whatever work the thread was trying
to do will be tried again.

One path where budget is freed and queues are kicked in the normal
case can be seen in scsi_finish_command().  Specifically:
- scsi_finish_command()
  - scsi_device_unbusy()
    - # Decrement "device_busy", AKA release budget
  - scsi_io_completion()
    - scsi_end_request()
      - blk_mq_run_hw_queues()

The above is all well and good.  The problem comes up when a thread
claims the budget but then releases it without actually dispatching
any work.  Since we didn't schedule any work we'll never run the path
of finishing work / kicking the queues.

This isn't often actually a problem which is why this issue has
existed for a while and nobody noticed.  Specifically we only get into
this situation when we unexpectedly found that we weren't going to do
any work.  Code that later receives new work kicks the queues.  All
good, right?

The problem shows up, however, if timing is just wrong and we hit a
race.  To see this race let's think about the case where we only have
a budget of 1 (only one thread can hold budget).  Now imagine that a
thread got budget and then decided not to dispatch work.  It's about
to call put_budget() but then the thread gets context switched out for
a long, long time.  While in this state, any and all kicks of the
queue (like the when we received new work) will be no-ops because
nobody can get budget.  Finally the thread holding budget gets to run
again and returns.  All the normal kicks will have been no-ops and we
have an I/O stall.

As you can see from the above, you need just the right timing to see
the race.  To start with, the only case it happens if we thought we
had work, actually managed to get the budget, but then actually didn't
have work.  That's pretty rare to start with.  Even then, there's
usually a very small amount of time between realizing that there's no
work and putting the budget.  During this small amount of time new
work has to come in and the queue kick has to make it all the way to
trying to get the budget and fail.  It's pretty unlikely.

One case where this could have failed is illustrated by an example of
threads running blk_mq_do_dispatch_sched():

* Threads A and B both run has_work() at the same time with the same
  "hctx".  Imagine has_work() is exact.  There's no lock, so it's OK
  if Thread A and B both get back true.
* Thread B gets interrupted for a long time right after it decides
  that there is work.  Maybe its CPU gets an interrupt and the
  interrupt handler is slow.
* Thread A runs, get budget, dispatches work.
* Thread A's work finishes and budget is released.
* Thread B finally runs again and gets budget.
* Since Thread A already took care of the work and no new work has
  come in, Thread B will get NULL from dispatch_request().  I believe
  this is specifically why dispatch_request() is allowed to return
  NULL in the first place if has_work() must be exact.
* Thread B will now be holding the budget and is about to call
  put_budget(), but hasn't called it yet.
* Thread B gets interrupted for a long time (again).  Dang interrupts.
* Now Thread C (maybe with a different "hctx" but the same queue)
  comes along and runs blk_mq_do_dispatch_sched().
* Thread C won't do anything because it can't get budget.
* Finally Thread B will run again and put the budget without kicking
  any queues.

Even though the example above is with blk_mq_do_dispatch_sched() I
believe the race is possible any time someone is holding budget but
doesn't do work.

Unfortunately, the unlikely has become more likely if you happen to be
using the BFQ I/O scheduler.  BFQ, by design, sometimes returns "true"
for has_work() but then NULL for dispatch_request() and stays in this
state for a while (currently up to 9 ms).  Suddenly you only need one
race to hit, not two races in a row.  With my current setup this is
easy to reproduce in reboot tests and traces have actually shown that
we hit a race similar to the one describe above.

In theory we could choose to just fix blk_mq_do_dispatch_sched() to
kick the queues when it puts budget.  That would fix the BFQ case and
one could argue that all the other cases are just theoretical.  While
that is true, for all the other cases it should be very uncommon to
run into the case where we need put_budget().  Having an extra queue
kick for safety there shouldn't affect much and keeps the race at bay.

One last note is that (at least in the SCSI case) budget is shared by
all "hctx"s that have the same queue.  Thus we need to make sure to
kick the whole queue, not just re-run dispatching on a single "hctx".

Signed-off-by: Douglas Anderson <dianders@chromium.org>
---

Changes in v3:
- Always kick when putting the budget.
- Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
- Totally rewrote commit message.

Changes in v2:
- Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")

 block/blk-mq.h | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/block/blk-mq.h b/block/blk-mq.h
index 10bfdfb494fa..1270505367ab 100644
--- a/block/blk-mq.h
+++ b/block/blk-mq.h
@@ -180,12 +180,24 @@ unsigned int blk_mq_in_flight(struct request_queue *q, struct hd_struct *part);
 void blk_mq_in_flight_rw(struct request_queue *q, struct hd_struct *part,
 			 unsigned int inflight[2]);
 
+#define BLK_MQ_BUDGET_DELAY	3		/* ms units */
+
 static inline void blk_mq_put_dispatch_budget(struct blk_mq_hw_ctx *hctx)
 {
 	struct request_queue *q = hctx->queue;
 
-	if (q->mq_ops->put_budget)
+	if (q->mq_ops->put_budget) {
 		q->mq_ops->put_budget(hctx);
+
+		/*
+		 * The only time we call blk_mq_put_dispatch_budget() is if
+		 * we released the budget without dispatching.  Holding the
+		 * budget could have blocked any "hctx"s with the same queue
+		 * and if we didn't dispatch then there's no guarantee anyone
+		 * will kick the queue.  Kick it ourselves.
+		 */
+		blk_mq_delay_run_hw_queues(q, BLK_MQ_BUDGET_DELAY);
+	}
 }
 
 static inline bool blk_mq_get_dispatch_budget(struct blk_mq_hw_ctx *hctx)
-- 
2.26.0.292.g33ef6b2f38-goog

[PATCH v3 4/4] Revert "scsi: core: run queue if SCSI device queue isn't ready and queue is idle"

[Douglas Anderson]

This reverts commit 7e70aa789d4a0c89dbfbd2c8a974a4df717475ec.

Now that we have the patches ("blk-mq: In blk_mq_dispatch_rq_list()
"no budget" is a reason to kick") and ("blk-mq: Rerun dispatching in
the case of budget contention") we should no longer need the fix in
the SCSI code.  Revert it, resolving conflicts with other patches that
have touched this code.

With this revert (and the two new patches) I can run the script that
was in commit 7e70aa789d4a ("scsi: core: run queue if SCSI device
queue isn't ready and queue is idle") in a loop with no failure.  If I
do this revert without the two new patches I can easily get a failure.

Signed-off-by: Douglas Anderson <dianders@chromium.org>
---
I don't know for sure that we can revert this patch, but in the very
least the original test case now passes.  If there is any question
about this, we can just drop this patch.

Changes in v3:
- ("Revert "scsi: core: run queue...") new for v3.

Changes in v2: None

 drivers/scsi/scsi_lib.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)

diff --git a/drivers/scsi/scsi_lib.c b/drivers/scsi/scsi_lib.c
index 47835c4b4ee0..ea18f618dc66 100644
--- a/drivers/scsi/scsi_lib.c
+++ b/drivers/scsi/scsi_lib.c
@@ -1610,12 +1610,7 @@ static bool scsi_mq_get_budget(struct blk_mq_hw_ctx *hctx)
 	struct request_queue *q = hctx->queue;
 	struct scsi_device *sdev = q->queuedata;
 
-	if (scsi_dev_queue_ready(q, sdev))
-		return true;
-
-	if (atomic_read(&sdev->device_busy) == 0 && !scsi_device_blocked(sdev))
-		blk_mq_delay_run_hw_queue(hctx, SCSI_QUEUE_DELAY);
-	return false;
+	return scsi_dev_queue_ready(q, sdev);
 }
 
 static blk_status_t scsi_queue_rq(struct blk_mq_hw_ctx *hctx,
-- 
2.26.0.292.g33ef6b2f38-goog

Re: [PATCH v3 3/4] blk-mq: Rerun dispatching in the case of budget contention

[Ming Lei]

On Tue, Apr 07, 2020 at 03:00:04PM -0700, Douglas Anderson wrote:
> If ever a thread running blk-mq code tries to get budget and fails it
> immediately stops doing work and assumes that whenever budget is freed
> up that queues will be kicked and whatever work the thread was trying
> to do will be tried again.
> 
> One path where budget is freed and queues are kicked in the normal
> case can be seen in scsi_finish_command().  Specifically:
> - scsi_finish_command()
>   - scsi_device_unbusy()
>     - # Decrement "device_busy", AKA release budget
>   - scsi_io_completion()
>     - scsi_end_request()
>       - blk_mq_run_hw_queues()
> 
> The above is all well and good.  The problem comes up when a thread
> claims the budget but then releases it without actually dispatching
> any work.  Since we didn't schedule any work we'll never run the path
> of finishing work / kicking the queues.
> 
> This isn't often actually a problem which is why this issue has
> existed for a while and nobody noticed.  Specifically we only get into
> this situation when we unexpectedly found that we weren't going to do
> any work.  Code that later receives new work kicks the queues.  All
> good, right?
> 
> The problem shows up, however, if timing is just wrong and we hit a
> race.  To see this race let's think about the case where we only have
> a budget of 1 (only one thread can hold budget).  Now imagine that a
> thread got budget and then decided not to dispatch work.  It's about
> to call put_budget() but then the thread gets context switched out for
> a long, long time.  While in this state, any and all kicks of the
> queue (like the when we received new work) will be no-ops because
> nobody can get budget.  Finally the thread holding budget gets to run
> again and returns.  All the normal kicks will have been no-ops and we
> have an I/O stall.
> 
> As you can see from the above, you need just the right timing to see
> the race.  To start with, the only case it happens if we thought we
> had work, actually managed to get the budget, but then actually didn't
> have work.  That's pretty rare to start with.  Even then, there's
> usually a very small amount of time between realizing that there's no
> work and putting the budget.  During this small amount of time new
> work has to come in and the queue kick has to make it all the way to
> trying to get the budget and fail.  It's pretty unlikely.
> 
> One case where this could have failed is illustrated by an example of
> threads running blk_mq_do_dispatch_sched():
> 
> * Threads A and B both run has_work() at the same time with the same
>   "hctx".  Imagine has_work() is exact.  There's no lock, so it's OK
>   if Thread A and B both get back true.
> * Thread B gets interrupted for a long time right after it decides
>   that there is work.  Maybe its CPU gets an interrupt and the
>   interrupt handler is slow.
> * Thread A runs, get budget, dispatches work.
> * Thread A's work finishes and budget is released.
> * Thread B finally runs again and gets budget.
> * Since Thread A already took care of the work and no new work has
>   come in, Thread B will get NULL from dispatch_request().  I believe
>   this is specifically why dispatch_request() is allowed to return
>   NULL in the first place if has_work() must be exact.
> * Thread B will now be holding the budget and is about to call
>   put_budget(), but hasn't called it yet.
> * Thread B gets interrupted for a long time (again).  Dang interrupts.
> * Now Thread C (maybe with a different "hctx" but the same queue)
>   comes along and runs blk_mq_do_dispatch_sched().
> * Thread C won't do anything because it can't get budget.

Thread C will re-run queue in this case:

Just thought scsi_mq_get_budget() does handle the case via re-run queue:

        if (atomic_read(&sdev->device_busy) == 0 && !scsi_device_blocked(sdev))
                blk_mq_delay_run_hw_queue(hctx, SCSI_QUEUE_DELAY);

So looks no such race.

> * Finally Thread B will run again and put the budget without kicking
>   any queues.
> 
> Even though the example above is with blk_mq_do_dispatch_sched() I
> believe the race is possible any time someone is holding budget but
> doesn't do work.
> 
> Unfortunately, the unlikely has become more likely if you happen to be
> using the BFQ I/O scheduler.  BFQ, by design, sometimes returns "true"
> for has_work() but then NULL for dispatch_request() and stays in this
> state for a while (currently up to 9 ms).  Suddenly you only need one
> race to hit, not two races in a row.  With my current setup this is
> easy to reproduce in reboot tests and traces have actually shown that
> we hit a race similar to the one describe above.
> 
> In theory we could choose to just fix blk_mq_do_dispatch_sched() to
> kick the queues when it puts budget.  That would fix the BFQ case and
> one could argue that all the other cases are just theoretical.  While
> that is true, for all the other cases it should be very uncommon to
> run into the case where we need put_budget().  Having an extra queue
> kick for safety there shouldn't affect much and keeps the race at bay.
> 
> One last note is that (at least in the SCSI case) budget is shared by
> all "hctx"s that have the same queue.  Thus we need to make sure to
> kick the whole queue, not just re-run dispatching on a single "hctx".
> 
> Signed-off-by: Douglas Anderson <dianders@chromium.org>
> ---
> 
> Changes in v3:
> - Always kick when putting the budget.
> - Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
> - Totally rewrote commit message.
> 
> Changes in v2:
> - Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")
> 
>  block/blk-mq.h | 14 +++++++++++++-
>  1 file changed, 13 insertions(+), 1 deletion(-)
> 
> diff --git a/block/blk-mq.h b/block/blk-mq.h
> index 10bfdfb494fa..1270505367ab 100644
> --- a/block/blk-mq.h
> +++ b/block/blk-mq.h
> @@ -180,12 +180,24 @@ unsigned int blk_mq_in_flight(struct request_queue *q, struct hd_struct *part);
>  void blk_mq_in_flight_rw(struct request_queue *q, struct hd_struct *part,
>  			 unsigned int inflight[2]);
>  
> +#define BLK_MQ_BUDGET_DELAY	3		/* ms units */
> +
>  static inline void blk_mq_put_dispatch_budget(struct blk_mq_hw_ctx *hctx)
>  {
>  	struct request_queue *q = hctx->queue;
>  
> -	if (q->mq_ops->put_budget)
> +	if (q->mq_ops->put_budget) {
>  		q->mq_ops->put_budget(hctx);
> +
> +		/*
> +		 * The only time we call blk_mq_put_dispatch_budget() is if
> +		 * we released the budget without dispatching.  Holding the
> +		 * budget could have blocked any "hctx"s with the same queue
> +		 * and if we didn't dispatch then there's no guarantee anyone
> +		 * will kick the queue.  Kick it ourselves.
> +		 */
> +		blk_mq_delay_run_hw_queues(q, BLK_MQ_BUDGET_DELAY);

No, please don't do that un-conditionally we just need to re-run queue
when there has work to do.

Thanks,
Ming

Re: [PATCH v3 3/4] blk-mq: Rerun dispatching in the case of budget contention

[Doug Anderson]

Hi,

On Tue, Apr 7, 2020 at 7:09 PM Ming Lei <ming.lei@redhat.com> wrote:
>
> On Tue, Apr 07, 2020 at 03:00:04PM -0700, Douglas Anderson wrote:
> > If ever a thread running blk-mq code tries to get budget and fails it
> > immediately stops doing work and assumes that whenever budget is freed
> > up that queues will be kicked and whatever work the thread was trying
> > to do will be tried again.
> >
> > One path where budget is freed and queues are kicked in the normal
> > case can be seen in scsi_finish_command().  Specifically:
> > - scsi_finish_command()
> >   - scsi_device_unbusy()
> >     - # Decrement "device_busy", AKA release budget
> >   - scsi_io_completion()
> >     - scsi_end_request()
> >       - blk_mq_run_hw_queues()
> >
> > The above is all well and good.  The problem comes up when a thread
> > claims the budget but then releases it without actually dispatching
> > any work.  Since we didn't schedule any work we'll never run the path
> > of finishing work / kicking the queues.
> >
> > This isn't often actually a problem which is why this issue has
> > existed for a while and nobody noticed.  Specifically we only get into
> > this situation when we unexpectedly found that we weren't going to do
> > any work.  Code that later receives new work kicks the queues.  All
> > good, right?
> >
> > The problem shows up, however, if timing is just wrong and we hit a
> > race.  To see this race let's think about the case where we only have
> > a budget of 1 (only one thread can hold budget).  Now imagine that a
> > thread got budget and then decided not to dispatch work.  It's about
> > to call put_budget() but then the thread gets context switched out for
> > a long, long time.  While in this state, any and all kicks of the
> > queue (like the when we received new work) will be no-ops because
> > nobody can get budget.  Finally the thread holding budget gets to run
> > again and returns.  All the normal kicks will have been no-ops and we
> > have an I/O stall.
> >
> > As you can see from the above, you need just the right timing to see
> > the race.  To start with, the only case it happens if we thought we
> > had work, actually managed to get the budget, but then actually didn't
> > have work.  That's pretty rare to start with.  Even then, there's
> > usually a very small amount of time between realizing that there's no
> > work and putting the budget.  During this small amount of time new
> > work has to come in and the queue kick has to make it all the way to
> > trying to get the budget and fail.  It's pretty unlikely.
> >
> > One case where this could have failed is illustrated by an example of
> > threads running blk_mq_do_dispatch_sched():
> >
> > * Threads A and B both run has_work() at the same time with the same
> >   "hctx".  Imagine has_work() is exact.  There's no lock, so it's OK
> >   if Thread A and B both get back true.
> > * Thread B gets interrupted for a long time right after it decides
> >   that there is work.  Maybe its CPU gets an interrupt and the
> >   interrupt handler is slow.
> > * Thread A runs, get budget, dispatches work.
> > * Thread A's work finishes and budget is released.
> > * Thread B finally runs again and gets budget.
> > * Since Thread A already took care of the work and no new work has
> >   come in, Thread B will get NULL from dispatch_request().  I believe
> >   this is specifically why dispatch_request() is allowed to return
> >   NULL in the first place if has_work() must be exact.
> > * Thread B will now be holding the budget and is about to call
> >   put_budget(), but hasn't called it yet.
> > * Thread B gets interrupted for a long time (again).  Dang interrupts.
> > * Now Thread C (maybe with a different "hctx" but the same queue)
> >   comes along and runs blk_mq_do_dispatch_sched().
> > * Thread C won't do anything because it can't get budget.
>
> Thread C will re-run queue in this case:
>
> Just thought scsi_mq_get_budget() does handle the case via re-run queue:
>
>         if (atomic_read(&sdev->device_busy) == 0 && !scsi_device_blocked(sdev))
>                 blk_mq_delay_run_hw_queue(hctx, SCSI_QUEUE_DELAY);
>
> So looks no such race.

Thread B is holding budget and hasn't released it yet, right?  In the
context of scsi, that means "device_busy >= 1", right?  So how can the
code you point at help us?  When Thread C reads "device_busy" it will
be 1 and that code won't run.  What did I miss?


> > * Finally Thread B will run again and put the budget without kicking
> >   any queues.
> >
> > Even though the example above is with blk_mq_do_dispatch_sched() I
> > believe the race is possible any time someone is holding budget but
> > doesn't do work.
> >
> > Unfortunately, the unlikely has become more likely if you happen to be
> > using the BFQ I/O scheduler.  BFQ, by design, sometimes returns "true"
> > for has_work() but then NULL for dispatch_request() and stays in this
> > state for a while (currently up to 9 ms).  Suddenly you only need one
> > race to hit, not two races in a row.  With my current setup this is
> > easy to reproduce in reboot tests and traces have actually shown that
> > we hit a race similar to the one describe above.
> >
> > In theory we could choose to just fix blk_mq_do_dispatch_sched() to
> > kick the queues when it puts budget.  That would fix the BFQ case and
> > one could argue that all the other cases are just theoretical.  While
> > that is true, for all the other cases it should be very uncommon to
> > run into the case where we need put_budget().  Having an extra queue
> > kick for safety there shouldn't affect much and keeps the race at bay.
> >
> > One last note is that (at least in the SCSI case) budget is shared by
> > all "hctx"s that have the same queue.  Thus we need to make sure to
> > kick the whole queue, not just re-run dispatching on a single "hctx".
> >
> > Signed-off-by: Douglas Anderson <dianders@chromium.org>
> > ---
> >
> > Changes in v3:
> > - Always kick when putting the budget.
> > - Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
> > - Totally rewrote commit message.
> >
> > Changes in v2:
> > - Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")
> >
> >  block/blk-mq.h | 14 +++++++++++++-
> >  1 file changed, 13 insertions(+), 1 deletion(-)
> >
> > diff --git a/block/blk-mq.h b/block/blk-mq.h
> > index 10bfdfb494fa..1270505367ab 100644
> > --- a/block/blk-mq.h
> > +++ b/block/blk-mq.h
> > @@ -180,12 +180,24 @@ unsigned int blk_mq_in_flight(struct request_queue *q, struct hd_struct *part);
> >  void blk_mq_in_flight_rw(struct request_queue *q, struct hd_struct *part,
> >                        unsigned int inflight[2]);
> >
> > +#define BLK_MQ_BUDGET_DELAY  3               /* ms units */
> > +
> >  static inline void blk_mq_put_dispatch_budget(struct blk_mq_hw_ctx *hctx)
> >  {
> >       struct request_queue *q = hctx->queue;
> >
> > -     if (q->mq_ops->put_budget)
> > +     if (q->mq_ops->put_budget) {
> >               q->mq_ops->put_budget(hctx);
> > +
> > +             /*
> > +              * The only time we call blk_mq_put_dispatch_budget() is if
> > +              * we released the budget without dispatching.  Holding the
> > +              * budget could have blocked any "hctx"s with the same queue
> > +              * and if we didn't dispatch then there's no guarantee anyone
> > +              * will kick the queue.  Kick it ourselves.
> > +              */
> > +             blk_mq_delay_run_hw_queues(q, BLK_MQ_BUDGET_DELAY);
>
> No, please don't do that un-conditionally we just need to re-run queue
> when there has work to do.

...what function would you like me to call to check?  The code you
wrote in response to v2 only checked work for the given "hctx".  What
about other "hctx" that are part of the same "queue".  Are we
guaranteed that has_work() returns the same value for all "hctx"s on
the same "queue"?  If so, why doesn't has_work() take the "queue" as a
parameter?

-Doug

Re: [PATCH v3 3/4] blk-mq: Rerun dispatching in the case of budget contention

[Ming Lei]

On Tue, Apr 07, 2020 at 07:17:49PM -0700, Doug Anderson wrote:
> Hi,
> 
> On Tue, Apr 7, 2020 at 7:09 PM Ming Lei <ming.lei@redhat.com> wrote:
> >
> > On Tue, Apr 07, 2020 at 03:00:04PM -0700, Douglas Anderson wrote:
> > > If ever a thread running blk-mq code tries to get budget and fails it
> > > immediately stops doing work and assumes that whenever budget is freed
> > > up that queues will be kicked and whatever work the thread was trying
> > > to do will be tried again.
> > >
> > > One path where budget is freed and queues are kicked in the normal
> > > case can be seen in scsi_finish_command().  Specifically:
> > > - scsi_finish_command()
> > >   - scsi_device_unbusy()
> > >     - # Decrement "device_busy", AKA release budget
> > >   - scsi_io_completion()
> > >     - scsi_end_request()
> > >       - blk_mq_run_hw_queues()
> > >
> > > The above is all well and good.  The problem comes up when a thread
> > > claims the budget but then releases it without actually dispatching
> > > any work.  Since we didn't schedule any work we'll never run the path
> > > of finishing work / kicking the queues.
> > >
> > > This isn't often actually a problem which is why this issue has
> > > existed for a while and nobody noticed.  Specifically we only get into
> > > this situation when we unexpectedly found that we weren't going to do
> > > any work.  Code that later receives new work kicks the queues.  All
> > > good, right?
> > >
> > > The problem shows up, however, if timing is just wrong and we hit a
> > > race.  To see this race let's think about the case where we only have
> > > a budget of 1 (only one thread can hold budget).  Now imagine that a
> > > thread got budget and then decided not to dispatch work.  It's about
> > > to call put_budget() but then the thread gets context switched out for
> > > a long, long time.  While in this state, any and all kicks of the
> > > queue (like the when we received new work) will be no-ops because
> > > nobody can get budget.  Finally the thread holding budget gets to run
> > > again and returns.  All the normal kicks will have been no-ops and we
> > > have an I/O stall.
> > >
> > > As you can see from the above, you need just the right timing to see
> > > the race.  To start with, the only case it happens if we thought we
> > > had work, actually managed to get the budget, but then actually didn't
> > > have work.  That's pretty rare to start with.  Even then, there's
> > > usually a very small amount of time between realizing that there's no
> > > work and putting the budget.  During this small amount of time new
> > > work has to come in and the queue kick has to make it all the way to
> > > trying to get the budget and fail.  It's pretty unlikely.
> > >
> > > One case where this could have failed is illustrated by an example of
> > > threads running blk_mq_do_dispatch_sched():
> > >
> > > * Threads A and B both run has_work() at the same time with the same
> > >   "hctx".  Imagine has_work() is exact.  There's no lock, so it's OK
> > >   if Thread A and B both get back true.
> > > * Thread B gets interrupted for a long time right after it decides
> > >   that there is work.  Maybe its CPU gets an interrupt and the
> > >   interrupt handler is slow.
> > > * Thread A runs, get budget, dispatches work.
> > > * Thread A's work finishes and budget is released.
> > > * Thread B finally runs again and gets budget.
> > > * Since Thread A already took care of the work and no new work has
> > >   come in, Thread B will get NULL from dispatch_request().  I believe
> > >   this is specifically why dispatch_request() is allowed to return
> > >   NULL in the first place if has_work() must be exact.
> > > * Thread B will now be holding the budget and is about to call
> > >   put_budget(), but hasn't called it yet.
> > > * Thread B gets interrupted for a long time (again).  Dang interrupts.
> > > * Now Thread C (maybe with a different "hctx" but the same queue)
> > >   comes along and runs blk_mq_do_dispatch_sched().
> > > * Thread C won't do anything because it can't get budget.
> >
> > Thread C will re-run queue in this case:
> >
> > Just thought scsi_mq_get_budget() does handle the case via re-run queue:
> >
> >         if (atomic_read(&sdev->device_busy) == 0 && !scsi_device_blocked(sdev))
> >                 blk_mq_delay_run_hw_queue(hctx, SCSI_QUEUE_DELAY);
> >
> > So looks no such race.
> 
> Thread B is holding budget and hasn't released it yet, right?  In the
> context of scsi, that means "device_busy >= 1", right?  So how can the
> code you point at help us?  When Thread C reads "device_busy" it will
> be 1 and that code won't run.  What did I miss?

Oh, this is my fault, sorry for the noise.

> 
> 
> > > * Finally Thread B will run again and put the budget without kicking
> > >   any queues.
> > >
> > > Even though the example above is with blk_mq_do_dispatch_sched() I
> > > believe the race is possible any time someone is holding budget but
> > > doesn't do work.
> > >
> > > Unfortunately, the unlikely has become more likely if you happen to be
> > > using the BFQ I/O scheduler.  BFQ, by design, sometimes returns "true"
> > > for has_work() but then NULL for dispatch_request() and stays in this
> > > state for a while (currently up to 9 ms).  Suddenly you only need one
> > > race to hit, not two races in a row.  With my current setup this is
> > > easy to reproduce in reboot tests and traces have actually shown that
> > > we hit a race similar to the one describe above.
> > >
> > > In theory we could choose to just fix blk_mq_do_dispatch_sched() to
> > > kick the queues when it puts budget.  That would fix the BFQ case and
> > > one could argue that all the other cases are just theoretical.  While
> > > that is true, for all the other cases it should be very uncommon to
> > > run into the case where we need put_budget().  Having an extra queue
> > > kick for safety there shouldn't affect much and keeps the race at bay.
> > >
> > > One last note is that (at least in the SCSI case) budget is shared by
> > > all "hctx"s that have the same queue.  Thus we need to make sure to
> > > kick the whole queue, not just re-run dispatching on a single "hctx".
> > >
> > > Signed-off-by: Douglas Anderson <dianders@chromium.org>
> > > ---
> > >
> > > Changes in v3:
> > > - Always kick when putting the budget.
> > > - Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
> > > - Totally rewrote commit message.
> > >
> > > Changes in v2:
> > > - Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")
> > >
> > >  block/blk-mq.h | 14 +++++++++++++-
> > >  1 file changed, 13 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/block/blk-mq.h b/block/blk-mq.h
> > > index 10bfdfb494fa..1270505367ab 100644
> > > --- a/block/blk-mq.h
> > > +++ b/block/blk-mq.h
> > > @@ -180,12 +180,24 @@ unsigned int blk_mq_in_flight(struct request_queue *q, struct hd_struct *part);
> > >  void blk_mq_in_flight_rw(struct request_queue *q, struct hd_struct *part,
> > >                        unsigned int inflight[2]);
> > >
> > > +#define BLK_MQ_BUDGET_DELAY  3               /* ms units */
> > > +
> > >  static inline void blk_mq_put_dispatch_budget(struct blk_mq_hw_ctx *hctx)
> > >  {
> > >       struct request_queue *q = hctx->queue;
> > >
> > > -     if (q->mq_ops->put_budget)
> > > +     if (q->mq_ops->put_budget) {
> > >               q->mq_ops->put_budget(hctx);
> > > +
> > > +             /*
> > > +              * The only time we call blk_mq_put_dispatch_budget() is if
> > > +              * we released the budget without dispatching.  Holding the
> > > +              * budget could have blocked any "hctx"s with the same queue
> > > +              * and if we didn't dispatch then there's no guarantee anyone
> > > +              * will kick the queue.  Kick it ourselves.
> > > +              */
> > > +             blk_mq_delay_run_hw_queues(q, BLK_MQ_BUDGET_DELAY);
> >
> > No, please don't do that un-conditionally we just need to re-run queue
> > when there has work to do.
> 
> ...what function would you like me to call to check?  The code you

At least we only need to call it in blk_mq_do_dispatch_sched() and
blk_mq_do_dispatch_ctx(), in which no request is dequeued yet. Other
callers can handle the run queue cause request has been there.

> wrote in response to v2 only checked work for the given "hctx".  What
> about other "hctx" that are part of the same "queue".  Are we
> guaranteed that has_work() returns the same value for all "hctx"s on
> the same "queue"?

In theory has_work() should return ture when there is work associated with
this hctx. However, some schedulers put all requests in global scheduler
queue instead of per-hctx, then this scheduler's
has_work() returns true when there is any request in scheduler queue.

> If so, why doesn't has_work() take the "queue" as a
> parameter?

In theory has_work() needs to be checked before run queue, however this
code path should be called very unusually, so it is fine to just run all
hctxs.

Thanks,
Ming

Re: [PATCH v3 3/4] blk-mq: Rerun dispatching in the case of budget contention

[Doug Anderson]

Hi,

On Tue, Apr 7, 2020 at 8:06 PM Ming Lei <ming.lei@redhat.com> wrote:
>
> On Tue, Apr 07, 2020 at 07:17:49PM -0700, Doug Anderson wrote:
> > Hi,
> >
> > On Tue, Apr 7, 2020 at 7:09 PM Ming Lei <ming.lei@redhat.com> wrote:
> > >
> > > On Tue, Apr 07, 2020 at 03:00:04PM -0700, Douglas Anderson wrote:
> > > > If ever a thread running blk-mq code tries to get budget and fails it
> > > > immediately stops doing work and assumes that whenever budget is freed
> > > > up that queues will be kicked and whatever work the thread was trying
> > > > to do will be tried again.
> > > >
> > > > One path where budget is freed and queues are kicked in the normal
> > > > case can be seen in scsi_finish_command().  Specifically:
> > > > - scsi_finish_command()
> > > >   - scsi_device_unbusy()
> > > >     - # Decrement "device_busy", AKA release budget
> > > >   - scsi_io_completion()
> > > >     - scsi_end_request()
> > > >       - blk_mq_run_hw_queues()
> > > >
> > > > The above is all well and good.  The problem comes up when a thread
> > > > claims the budget but then releases it without actually dispatching
> > > > any work.  Since we didn't schedule any work we'll never run the path
> > > > of finishing work / kicking the queues.
> > > >
> > > > This isn't often actually a problem which is why this issue has
> > > > existed for a while and nobody noticed.  Specifically we only get into
> > > > this situation when we unexpectedly found that we weren't going to do
> > > > any work.  Code that later receives new work kicks the queues.  All
> > > > good, right?
> > > >
> > > > The problem shows up, however, if timing is just wrong and we hit a
> > > > race.  To see this race let's think about the case where we only have
> > > > a budget of 1 (only one thread can hold budget).  Now imagine that a
> > > > thread got budget and then decided not to dispatch work.  It's about
> > > > to call put_budget() but then the thread gets context switched out for
> > > > a long, long time.  While in this state, any and all kicks of the
> > > > queue (like the when we received new work) will be no-ops because
> > > > nobody can get budget.  Finally the thread holding budget gets to run
> > > > again and returns.  All the normal kicks will have been no-ops and we
> > > > have an I/O stall.
> > > >
> > > > As you can see from the above, you need just the right timing to see
> > > > the race.  To start with, the only case it happens if we thought we
> > > > had work, actually managed to get the budget, but then actually didn't
> > > > have work.  That's pretty rare to start with.  Even then, there's
> > > > usually a very small amount of time between realizing that there's no
> > > > work and putting the budget.  During this small amount of time new
> > > > work has to come in and the queue kick has to make it all the way to
> > > > trying to get the budget and fail.  It's pretty unlikely.
> > > >
> > > > One case where this could have failed is illustrated by an example of
> > > > threads running blk_mq_do_dispatch_sched():
> > > >
> > > > * Threads A and B both run has_work() at the same time with the same
> > > >   "hctx".  Imagine has_work() is exact.  There's no lock, so it's OK
> > > >   if Thread A and B both get back true.
> > > > * Thread B gets interrupted for a long time right after it decides
> > > >   that there is work.  Maybe its CPU gets an interrupt and the
> > > >   interrupt handler is slow.
> > > > * Thread A runs, get budget, dispatches work.
> > > > * Thread A's work finishes and budget is released.
> > > > * Thread B finally runs again and gets budget.
> > > > * Since Thread A already took care of the work and no new work has
> > > >   come in, Thread B will get NULL from dispatch_request().  I believe
> > > >   this is specifically why dispatch_request() is allowed to return
> > > >   NULL in the first place if has_work() must be exact.
> > > > * Thread B will now be holding the budget and is about to call
> > > >   put_budget(), but hasn't called it yet.
> > > > * Thread B gets interrupted for a long time (again).  Dang interrupts.
> > > > * Now Thread C (maybe with a different "hctx" but the same queue)
> > > >   comes along and runs blk_mq_do_dispatch_sched().
> > > > * Thread C won't do anything because it can't get budget.
> > >
> > > Thread C will re-run queue in this case:
> > >
> > > Just thought scsi_mq_get_budget() does handle the case via re-run queue:
> > >
> > >         if (atomic_read(&sdev->device_busy) == 0 && !scsi_device_blocked(sdev))
> > >                 blk_mq_delay_run_hw_queue(hctx, SCSI_QUEUE_DELAY);
> > >
> > > So looks no such race.
> >
> > Thread B is holding budget and hasn't released it yet, right?  In the
> > context of scsi, that means "device_busy >= 1", right?  So how can the
> > code you point at help us?  When Thread C reads "device_busy" it will
> > be 1 and that code won't run.  What did I miss?
>
> Oh, this is my fault, sorry for the noise.
>
> >
> >
> > > > * Finally Thread B will run again and put the budget without kicking
> > > >   any queues.
> > > >
> > > > Even though the example above is with blk_mq_do_dispatch_sched() I
> > > > believe the race is possible any time someone is holding budget but
> > > > doesn't do work.
> > > >
> > > > Unfortunately, the unlikely has become more likely if you happen to be
> > > > using the BFQ I/O scheduler.  BFQ, by design, sometimes returns "true"
> > > > for has_work() but then NULL for dispatch_request() and stays in this
> > > > state for a while (currently up to 9 ms).  Suddenly you only need one
> > > > race to hit, not two races in a row.  With my current setup this is
> > > > easy to reproduce in reboot tests and traces have actually shown that
> > > > we hit a race similar to the one describe above.
> > > >
> > > > In theory we could choose to just fix blk_mq_do_dispatch_sched() to
> > > > kick the queues when it puts budget.  That would fix the BFQ case and
> > > > one could argue that all the other cases are just theoretical.  While
> > > > that is true, for all the other cases it should be very uncommon to
> > > > run into the case where we need put_budget().  Having an extra queue
> > > > kick for safety there shouldn't affect much and keeps the race at bay.
> > > >
> > > > One last note is that (at least in the SCSI case) budget is shared by
> > > > all "hctx"s that have the same queue.  Thus we need to make sure to
> > > > kick the whole queue, not just re-run dispatching on a single "hctx".
> > > >
> > > > Signed-off-by: Douglas Anderson <dianders@chromium.org>
> > > > ---
> > > >
> > > > Changes in v3:
> > > > - Always kick when putting the budget.
> > > > - Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
> > > > - Totally rewrote commit message.
> > > >
> > > > Changes in v2:
> > > > - Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")
> > > >
> > > >  block/blk-mq.h | 14 +++++++++++++-
> > > >  1 file changed, 13 insertions(+), 1 deletion(-)
> > > >
> > > > diff --git a/block/blk-mq.h b/block/blk-mq.h
> > > > index 10bfdfb494fa..1270505367ab 100644
> > > > --- a/block/blk-mq.h
> > > > +++ b/block/blk-mq.h
> > > > @@ -180,12 +180,24 @@ unsigned int blk_mq_in_flight(struct request_queue *q, struct hd_struct *part);
> > > >  void blk_mq_in_flight_rw(struct request_queue *q, struct hd_struct *part,
> > > >                        unsigned int inflight[2]);
> > > >
> > > > +#define BLK_MQ_BUDGET_DELAY  3               /* ms units */
> > > > +
> > > >  static inline void blk_mq_put_dispatch_budget(struct blk_mq_hw_ctx *hctx)
> > > >  {
> > > >       struct request_queue *q = hctx->queue;
> > > >
> > > > -     if (q->mq_ops->put_budget)
> > > > +     if (q->mq_ops->put_budget) {
> > > >               q->mq_ops->put_budget(hctx);
> > > > +
> > > > +             /*
> > > > +              * The only time we call blk_mq_put_dispatch_budget() is if
> > > > +              * we released the budget without dispatching.  Holding the
> > > > +              * budget could have blocked any "hctx"s with the same queue
> > > > +              * and if we didn't dispatch then there's no guarantee anyone
> > > > +              * will kick the queue.  Kick it ourselves.
> > > > +              */
> > > > +             blk_mq_delay_run_hw_queues(q, BLK_MQ_BUDGET_DELAY);
> > >
> > > No, please don't do that un-conditionally we just need to re-run queue
> > > when there has work to do.
> >
> > ...what function would you like me to call to check?  The code you
>
> At least we only need to call it in blk_mq_do_dispatch_sched() and
> blk_mq_do_dispatch_ctx(), in which no request is dequeued yet. Other
> callers can handle the run queue cause request has been there.

Sure, I can move it so it's only in blk_mq_do_dispatch_sched() and
blk_mq_do_dispatch_ctx().  That would definitely make it so that I
can't reproduce problems anymore, at least.

The one thing that worries me is that I couldn't come up with a
convincing argument about why the race wasn't possible when we put the
budget in blk_mq_dispatch_rq_list() and __blk_mq_try_issue_directly().
Perhaps you can explain.  In blk_mq_dispatch_rq_list() I can see that
we will call blk_mq_run_hw_queue() or blk_mq_delay_run_hw_queue(), but
I guess I'm at least slightly worried that we'd also need to kick the
other "hctx"s on the same queue.  In theory holding budget could have
block those as well.  Do we care?  Maybe we should always assume that
the scheduler has a global queue across all "hctx"s?


> > wrote in response to v2 only checked work for the given "hctx".  What
> > about other "hctx" that are part of the same "queue".  Are we
> > guaranteed that has_work() returns the same value for all "hctx"s on
> > the same "queue"?
>
> In theory has_work() should return ture when there is work associated with
> this hctx. However, some schedulers put all requests in global scheduler
> queue instead of per-hctx, then this scheduler's
> has_work() returns true when there is any request in scheduler queue.

Assuming we care about supporting schedulers that don't have a global
scheduler queue, it seems important to kick all the queues.  However,
if you tell me that all the code is already assuming a global
scheduler code then I can change my code to assume that too.


> > If so, why doesn't has_work() take the "queue" as a
> > parameter?
>
> In theory has_work() needs to be checked before run queue, however this
> code path should be called very unusually, so it is fine to just run all
> hctxs.

OK, thanks for confirming.  If you tell me that we should assume that
all IO schedulers have a global scheduler queue then I'll add the
has_work() check back in.  Otherwise I'll leave it as-is.

-Doug

Re: [PATCH v3 3/4] blk-mq: Rerun dispatching in the case of budget contention

[Ming Lei]

On Tue, Apr 07, 2020 at 09:11:28PM -0700, Doug Anderson wrote:
> Hi,
> 
> On Tue, Apr 7, 2020 at 8:06 PM Ming Lei <ming.lei@redhat.com> wrote:
> >
> > On Tue, Apr 07, 2020 at 07:17:49PM -0700, Doug Anderson wrote:
> > > Hi,
> > >
> > > On Tue, Apr 7, 2020 at 7:09 PM Ming Lei <ming.lei@redhat.com> wrote:
> > > >
> > > > On Tue, Apr 07, 2020 at 03:00:04PM -0700, Douglas Anderson wrote:
> > > > > If ever a thread running blk-mq code tries to get budget and fails it
> > > > > immediately stops doing work and assumes that whenever budget is freed
> > > > > up that queues will be kicked and whatever work the thread was trying
> > > > > to do will be tried again.
> > > > >
> > > > > One path where budget is freed and queues are kicked in the normal
> > > > > case can be seen in scsi_finish_command().  Specifically:
> > > > > - scsi_finish_command()
> > > > >   - scsi_device_unbusy()
> > > > >     - # Decrement "device_busy", AKA release budget
> > > > >   - scsi_io_completion()
> > > > >     - scsi_end_request()
> > > > >       - blk_mq_run_hw_queues()
> > > > >
> > > > > The above is all well and good.  The problem comes up when a thread
> > > > > claims the budget but then releases it without actually dispatching
> > > > > any work.  Since we didn't schedule any work we'll never run the path
> > > > > of finishing work / kicking the queues.
> > > > >
> > > > > This isn't often actually a problem which is why this issue has
> > > > > existed for a while and nobody noticed.  Specifically we only get into
> > > > > this situation when we unexpectedly found that we weren't going to do
> > > > > any work.  Code that later receives new work kicks the queues.  All
> > > > > good, right?
> > > > >
> > > > > The problem shows up, however, if timing is just wrong and we hit a
> > > > > race.  To see this race let's think about the case where we only have
> > > > > a budget of 1 (only one thread can hold budget).  Now imagine that a
> > > > > thread got budget and then decided not to dispatch work.  It's about
> > > > > to call put_budget() but then the thread gets context switched out for
> > > > > a long, long time.  While in this state, any and all kicks of the
> > > > > queue (like the when we received new work) will be no-ops because
> > > > > nobody can get budget.  Finally the thread holding budget gets to run
> > > > > again and returns.  All the normal kicks will have been no-ops and we
> > > > > have an I/O stall.
> > > > >
> > > > > As you can see from the above, you need just the right timing to see
> > > > > the race.  To start with, the only case it happens if we thought we
> > > > > had work, actually managed to get the budget, but then actually didn't
> > > > > have work.  That's pretty rare to start with.  Even then, there's
> > > > > usually a very small amount of time between realizing that there's no
> > > > > work and putting the budget.  During this small amount of time new
> > > > > work has to come in and the queue kick has to make it all the way to
> > > > > trying to get the budget and fail.  It's pretty unlikely.
> > > > >
> > > > > One case where this could have failed is illustrated by an example of
> > > > > threads running blk_mq_do_dispatch_sched():
> > > > >
> > > > > * Threads A and B both run has_work() at the same time with the same
> > > > >   "hctx".  Imagine has_work() is exact.  There's no lock, so it's OK
> > > > >   if Thread A and B both get back true.
> > > > > * Thread B gets interrupted for a long time right after it decides
> > > > >   that there is work.  Maybe its CPU gets an interrupt and the
> > > > >   interrupt handler is slow.
> > > > > * Thread A runs, get budget, dispatches work.
> > > > > * Thread A's work finishes and budget is released.
> > > > > * Thread B finally runs again and gets budget.
> > > > > * Since Thread A already took care of the work and no new work has
> > > > >   come in, Thread B will get NULL from dispatch_request().  I believe
> > > > >   this is specifically why dispatch_request() is allowed to return
> > > > >   NULL in the first place if has_work() must be exact.
> > > > > * Thread B will now be holding the budget and is about to call
> > > > >   put_budget(), but hasn't called it yet.
> > > > > * Thread B gets interrupted for a long time (again).  Dang interrupts.
> > > > > * Now Thread C (maybe with a different "hctx" but the same queue)
> > > > >   comes along and runs blk_mq_do_dispatch_sched().
> > > > > * Thread C won't do anything because it can't get budget.
> > > >
> > > > Thread C will re-run queue in this case:
> > > >
> > > > Just thought scsi_mq_get_budget() does handle the case via re-run queue:
> > > >
> > > >         if (atomic_read(&sdev->device_busy) == 0 && !scsi_device_blocked(sdev))
> > > >                 blk_mq_delay_run_hw_queue(hctx, SCSI_QUEUE_DELAY);
> > > >
> > > > So looks no such race.
> > >
> > > Thread B is holding budget and hasn't released it yet, right?  In the
> > > context of scsi, that means "device_busy >= 1", right?  So how can the
> > > code you point at help us?  When Thread C reads "device_busy" it will
> > > be 1 and that code won't run.  What did I miss?
> >
> > Oh, this is my fault, sorry for the noise.
> >
> > >
> > >
> > > > > * Finally Thread B will run again and put the budget without kicking
> > > > >   any queues.
> > > > >
> > > > > Even though the example above is with blk_mq_do_dispatch_sched() I
> > > > > believe the race is possible any time someone is holding budget but
> > > > > doesn't do work.
> > > > >
> > > > > Unfortunately, the unlikely has become more likely if you happen to be
> > > > > using the BFQ I/O scheduler.  BFQ, by design, sometimes returns "true"
> > > > > for has_work() but then NULL for dispatch_request() and stays in this
> > > > > state for a while (currently up to 9 ms).  Suddenly you only need one
> > > > > race to hit, not two races in a row.  With my current setup this is
> > > > > easy to reproduce in reboot tests and traces have actually shown that
> > > > > we hit a race similar to the one describe above.
> > > > >
> > > > > In theory we could choose to just fix blk_mq_do_dispatch_sched() to
> > > > > kick the queues when it puts budget.  That would fix the BFQ case and
> > > > > one could argue that all the other cases are just theoretical.  While
> > > > > that is true, for all the other cases it should be very uncommon to
> > > > > run into the case where we need put_budget().  Having an extra queue
> > > > > kick for safety there shouldn't affect much and keeps the race at bay.
> > > > >
> > > > > One last note is that (at least in the SCSI case) budget is shared by
> > > > > all "hctx"s that have the same queue.  Thus we need to make sure to
> > > > > kick the whole queue, not just re-run dispatching on a single "hctx".
> > > > >
> > > > > Signed-off-by: Douglas Anderson <dianders@chromium.org>
> > > > > ---
> > > > >
> > > > > Changes in v3:
> > > > > - Always kick when putting the budget.
> > > > > - Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
> > > > > - Totally rewrote commit message.
> > > > >
> > > > > Changes in v2:
> > > > > - Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")
> > > > >
> > > > >  block/blk-mq.h | 14 +++++++++++++-
> > > > >  1 file changed, 13 insertions(+), 1 deletion(-)
> > > > >
> > > > > diff --git a/block/blk-mq.h b/block/blk-mq.h
> > > > > index 10bfdfb494fa..1270505367ab 100644
> > > > > --- a/block/blk-mq.h
> > > > > +++ b/block/blk-mq.h
> > > > > @@ -180,12 +180,24 @@ unsigned int blk_mq_in_flight(struct request_queue *q, struct hd_struct *part);
> > > > >  void blk_mq_in_flight_rw(struct request_queue *q, struct hd_struct *part,
> > > > >                        unsigned int inflight[2]);
> > > > >
> > > > > +#define BLK_MQ_BUDGET_DELAY  3               /* ms units */
> > > > > +
> > > > >  static inline void blk_mq_put_dispatch_budget(struct blk_mq_hw_ctx *hctx)
> > > > >  {
> > > > >       struct request_queue *q = hctx->queue;
> > > > >
> > > > > -     if (q->mq_ops->put_budget)
> > > > > +     if (q->mq_ops->put_budget) {
> > > > >               q->mq_ops->put_budget(hctx);
> > > > > +
> > > > > +             /*
> > > > > +              * The only time we call blk_mq_put_dispatch_budget() is if
> > > > > +              * we released the budget without dispatching.  Holding the
> > > > > +              * budget could have blocked any "hctx"s with the same queue
> > > > > +              * and if we didn't dispatch then there's no guarantee anyone
> > > > > +              * will kick the queue.  Kick it ourselves.
> > > > > +              */
> > > > > +             blk_mq_delay_run_hw_queues(q, BLK_MQ_BUDGET_DELAY);
> > > >
> > > > No, please don't do that un-conditionally we just need to re-run queue
> > > > when there has work to do.
> > >
> > > ...what function would you like me to call to check?  The code you
> >
> > At least we only need to call it in blk_mq_do_dispatch_sched() and
> > blk_mq_do_dispatch_ctx(), in which no request is dequeued yet. Other
> > callers can handle the run queue cause request has been there.
> 
> Sure, I can move it so it's only in blk_mq_do_dispatch_sched() and
> blk_mq_do_dispatch_ctx().  That would definitely make it so that I
> can't reproduce problems anymore, at least.
> 
> The one thing that worries me is that I couldn't come up with a
> convincing argument about why the race wasn't possible when we put the
> budget in blk_mq_dispatch_rq_list() and __blk_mq_try_issue_directly().
> Perhaps you can explain.  In blk_mq_dispatch_rq_list() I can see that
> we will call blk_mq_run_hw_queue() or blk_mq_delay_run_hw_queue(), but
> I guess I'm at least slightly worried that we'd also need to kick the
> other "hctx"s on the same queue.  In theory holding budget could have

No, if there is one request from any one hctx, when this request is
dispatched and completed, all hctxs will be run again from
scsi_end_request().



Thanks,
Ming

Re: [PATCH v3 3/4] blk-mq: Rerun dispatching in the case of budget contention

[Doug Anderson]

Hi,

On Wed, Apr 8, 2020 at 12:36 AM Ming Lei <ming.lei@redhat.com> wrote:
>
> On Tue, Apr 07, 2020 at 09:11:28PM -0700, Doug Anderson wrote:
> > Hi,
> >
> > On Tue, Apr 7, 2020 at 8:06 PM Ming Lei <ming.lei@redhat.com> wrote:
> > >
> > > On Tue, Apr 07, 2020 at 07:17:49PM -0700, Doug Anderson wrote:
> > > > Hi,
> > > >
> > > > On Tue, Apr 7, 2020 at 7:09 PM Ming Lei <ming.lei@redhat.com> wrote:
> > > > >
> > > > > On Tue, Apr 07, 2020 at 03:00:04PM -0700, Douglas Anderson wrote:
> > > > > > If ever a thread running blk-mq code tries to get budget and fails it
> > > > > > immediately stops doing work and assumes that whenever budget is freed
> > > > > > up that queues will be kicked and whatever work the thread was trying
> > > > > > to do will be tried again.
> > > > > >
> > > > > > One path where budget is freed and queues are kicked in the normal
> > > > > > case can be seen in scsi_finish_command().  Specifically:
> > > > > > - scsi_finish_command()
> > > > > >   - scsi_device_unbusy()
> > > > > >     - # Decrement "device_busy", AKA release budget
> > > > > >   - scsi_io_completion()
> > > > > >     - scsi_end_request()
> > > > > >       - blk_mq_run_hw_queues()
> > > > > >
> > > > > > The above is all well and good.  The problem comes up when a thread
> > > > > > claims the budget but then releases it without actually dispatching
> > > > > > any work.  Since we didn't schedule any work we'll never run the path
> > > > > > of finishing work / kicking the queues.
> > > > > >
> > > > > > This isn't often actually a problem which is why this issue has
> > > > > > existed for a while and nobody noticed.  Specifically we only get into
> > > > > > this situation when we unexpectedly found that we weren't going to do
> > > > > > any work.  Code that later receives new work kicks the queues.  All
> > > > > > good, right?
> > > > > >
> > > > > > The problem shows up, however, if timing is just wrong and we hit a
> > > > > > race.  To see this race let's think about the case where we only have
> > > > > > a budget of 1 (only one thread can hold budget).  Now imagine that a
> > > > > > thread got budget and then decided not to dispatch work.  It's about
> > > > > > to call put_budget() but then the thread gets context switched out for
> > > > > > a long, long time.  While in this state, any and all kicks of the
> > > > > > queue (like the when we received new work) will be no-ops because
> > > > > > nobody can get budget.  Finally the thread holding budget gets to run
> > > > > > again and returns.  All the normal kicks will have been no-ops and we
> > > > > > have an I/O stall.
> > > > > >
> > > > > > As you can see from the above, you need just the right timing to see
> > > > > > the race.  To start with, the only case it happens if we thought we
> > > > > > had work, actually managed to get the budget, but then actually didn't
> > > > > > have work.  That's pretty rare to start with.  Even then, there's
> > > > > > usually a very small amount of time between realizing that there's no
> > > > > > work and putting the budget.  During this small amount of time new
> > > > > > work has to come in and the queue kick has to make it all the way to
> > > > > > trying to get the budget and fail.  It's pretty unlikely.
> > > > > >
> > > > > > One case where this could have failed is illustrated by an example of
> > > > > > threads running blk_mq_do_dispatch_sched():
> > > > > >
> > > > > > * Threads A and B both run has_work() at the same time with the same
> > > > > >   "hctx".  Imagine has_work() is exact.  There's no lock, so it's OK
> > > > > >   if Thread A and B both get back true.
> > > > > > * Thread B gets interrupted for a long time right after it decides
> > > > > >   that there is work.  Maybe its CPU gets an interrupt and the
> > > > > >   interrupt handler is slow.
> > > > > > * Thread A runs, get budget, dispatches work.
> > > > > > * Thread A's work finishes and budget is released.
> > > > > > * Thread B finally runs again and gets budget.
> > > > > > * Since Thread A already took care of the work and no new work has
> > > > > >   come in, Thread B will get NULL from dispatch_request().  I believe
> > > > > >   this is specifically why dispatch_request() is allowed to return
> > > > > >   NULL in the first place if has_work() must be exact.
> > > > > > * Thread B will now be holding the budget and is about to call
> > > > > >   put_budget(), but hasn't called it yet.
> > > > > > * Thread B gets interrupted for a long time (again).  Dang interrupts.
> > > > > > * Now Thread C (maybe with a different "hctx" but the same queue)
> > > > > >   comes along and runs blk_mq_do_dispatch_sched().
> > > > > > * Thread C won't do anything because it can't get budget.
> > > > >
> > > > > Thread C will re-run queue in this case:
> > > > >
> > > > > Just thought scsi_mq_get_budget() does handle the case via re-run queue:
> > > > >
> > > > >         if (atomic_read(&sdev->device_busy) == 0 && !scsi_device_blocked(sdev))
> > > > >                 blk_mq_delay_run_hw_queue(hctx, SCSI_QUEUE_DELAY);
> > > > >
> > > > > So looks no such race.
> > > >
> > > > Thread B is holding budget and hasn't released it yet, right?  In the
> > > > context of scsi, that means "device_busy >= 1", right?  So how can the
> > > > code you point at help us?  When Thread C reads "device_busy" it will
> > > > be 1 and that code won't run.  What did I miss?
> > >
> > > Oh, this is my fault, sorry for the noise.
> > >
> > > >
> > > >
> > > > > > * Finally Thread B will run again and put the budget without kicking
> > > > > >   any queues.
> > > > > >
> > > > > > Even though the example above is with blk_mq_do_dispatch_sched() I
> > > > > > believe the race is possible any time someone is holding budget but
> > > > > > doesn't do work.
> > > > > >
> > > > > > Unfortunately, the unlikely has become more likely if you happen to be
> > > > > > using the BFQ I/O scheduler.  BFQ, by design, sometimes returns "true"
> > > > > > for has_work() but then NULL for dispatch_request() and stays in this
> > > > > > state for a while (currently up to 9 ms).  Suddenly you only need one
> > > > > > race to hit, not two races in a row.  With my current setup this is
> > > > > > easy to reproduce in reboot tests and traces have actually shown that
> > > > > > we hit a race similar to the one describe above.
> > > > > >
> > > > > > In theory we could choose to just fix blk_mq_do_dispatch_sched() to
> > > > > > kick the queues when it puts budget.  That would fix the BFQ case and
> > > > > > one could argue that all the other cases are just theoretical.  While
> > > > > > that is true, for all the other cases it should be very uncommon to
> > > > > > run into the case where we need put_budget().  Having an extra queue
> > > > > > kick for safety there shouldn't affect much and keeps the race at bay.
> > > > > >
> > > > > > One last note is that (at least in the SCSI case) budget is shared by
> > > > > > all "hctx"s that have the same queue.  Thus we need to make sure to
> > > > > > kick the whole queue, not just re-run dispatching on a single "hctx".
> > > > > >
> > > > > > Signed-off-by: Douglas Anderson <dianders@chromium.org>
> > > > > > ---
> > > > > >
> > > > > > Changes in v3:
> > > > > > - Always kick when putting the budget.
> > > > > > - Delay blk_mq_do_dispatch_sched() kick by 3 ms for inexact has_work().
> > > > > > - Totally rewrote commit message.
> > > > > >
> > > > > > Changes in v2:
> > > > > > - Replace ("scsi: core: Fix stall...") w/ ("blk-mq: Rerun dispatch...")
> > > > > >
> > > > > >  block/blk-mq.h | 14 +++++++++++++-
> > > > > >  1 file changed, 13 insertions(+), 1 deletion(-)
> > > > > >
> > > > > > diff --git a/block/blk-mq.h b/block/blk-mq.h
> > > > > > index 10bfdfb494fa..1270505367ab 100644
> > > > > > --- a/block/blk-mq.h
> > > > > > +++ b/block/blk-mq.h
> > > > > > @@ -180,12 +180,24 @@ unsigned int blk_mq_in_flight(struct request_queue *q, struct hd_struct *part);
> > > > > >  void blk_mq_in_flight_rw(struct request_queue *q, struct hd_struct *part,
> > > > > >                        unsigned int inflight[2]);
> > > > > >
> > > > > > +#define BLK_MQ_BUDGET_DELAY  3               /* ms units */
> > > > > > +
> > > > > >  static inline void blk_mq_put_dispatch_budget(struct blk_mq_hw_ctx *hctx)
> > > > > >  {
> > > > > >       struct request_queue *q = hctx->queue;
> > > > > >
> > > > > > -     if (q->mq_ops->put_budget)
> > > > > > +     if (q->mq_ops->put_budget) {
> > > > > >               q->mq_ops->put_budget(hctx);
> > > > > > +
> > > > > > +             /*
> > > > > > +              * The only time we call blk_mq_put_dispatch_budget() is if
> > > > > > +              * we released the budget without dispatching.  Holding the
> > > > > > +              * budget could have blocked any "hctx"s with the same queue
> > > > > > +              * and if we didn't dispatch then there's no guarantee anyone
> > > > > > +              * will kick the queue.  Kick it ourselves.
> > > > > > +              */
> > > > > > +             blk_mq_delay_run_hw_queues(q, BLK_MQ_BUDGET_DELAY);
> > > > >
> > > > > No, please don't do that un-conditionally we just need to re-run queue
> > > > > when there has work to do.
> > > >
> > > > ...what function would you like me to call to check?  The code you
> > >
> > > At least we only need to call it in blk_mq_do_dispatch_sched() and
> > > blk_mq_do_dispatch_ctx(), in which no request is dequeued yet. Other
> > > callers can handle the run queue cause request has been there.
> >
> > Sure, I can move it so it's only in blk_mq_do_dispatch_sched() and
> > blk_mq_do_dispatch_ctx().  That would definitely make it so that I
> > can't reproduce problems anymore, at least.
> >
> > The one thing that worries me is that I couldn't come up with a
> > convincing argument about why the race wasn't possible when we put the
> > budget in blk_mq_dispatch_rq_list() and __blk_mq_try_issue_directly().
> > Perhaps you can explain.  In blk_mq_dispatch_rq_list() I can see that
> > we will call blk_mq_run_hw_queue() or blk_mq_delay_run_hw_queue(), but
> > I guess I'm at least slightly worried that we'd also need to kick the
> > other "hctx"s on the same queue.  In theory holding budget could have
>
> No, if there is one request from any one hctx, when this request is
> dispatched and completed, all hctxs will be run again from
> scsi_end_request().

Ah, of course!  That makes sense to me.  Thanks for explaining.  So in
these contexts we know for sure that there is more work to do on our
"hctx" and we re-kick our own work.  If we happened to have blocked
some other "hctx" then at least it will get kicked again when we
finish our work just like in the normal case where we had budget and
blocked someone else.

I've updated the comments and I'm uploading a v4.  I hope it looks good now.

-Doug