RFC sbitmap enforced fairness for blk-mq
Get series with b4
b4 am [email protected]Versions newest first
- v1 RFC Latest6 patches 2 repliesIn review
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/6 | lib/sbitmap: add ranged allocation, bounded wakeup relay, and ranged weightinclude/ lib/ | +253 | 0 replies | |
| 2/6 | blk-mq: replace shared-tag fairness counter with allocation windowsblock/ block/ block/ +4 more | +135 | 0 replies | |
| 3/6 | blk-mq: factor out a per-hctx tag busy iteratorblock/ | +19 | 0 replies | |
| 4/6 | blk-mq: add a shared zone to tag fairnessblock/ block/ include/ | +79 | 0 replies | |
| 5/6 | blk-mq: cache shared-tag fairness windowsblock/ block/ block/ +2 more | +102 | 0 replies | |
| 6/6 | scsi: add shared-tag fairness to host_tagset driversdrivers/ drivers/ include/ | +18 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [RFC PATCH 0/6] sbitmap enforced fairness for blk-mq
From: Keith Busch <[email protected]>
There have been a few proposals to remove the blk-mq tag fairness algorithm:
https://lore.kernel.org/linux-block/[email protected]/
https://lore.kernel.org/linux-block/[email protected]/
Both abandon blk-mq's attempt to enforce tag allocation limits on the per-queue/per-hctx users that share tag space. This can harm resource allocation for lesser devices sharing the space, potentially starving, them from fair progress by a highly utilized device.
This series proposes an entirely different fairness mechanism that doesn't require per-IO atomic accounting:
First, the sbitmap API is augmented with a ranged allocator. This allows a client to carve the depth into exclusive ranges for specific users.
Second, you can optionally declare a percentage of that pool to be fair game for anyone to allocate from. This provides a way to guarantee minimum tag space for each client while allowing a user to over-allocate its fair budget on demand into the shared zone.
For testing, I used scsi_debug for the TAG_HCTX_SHARED case and a nvme multi-namespace device for TAG_QUEUE_SHARED. Workloads emphasized greedy vs. passive jobs. No performance regressions were observed.
There's a couple difficult things to deal with here:
After a completion releases a tag, there isn't an easy way to wake up specific waiters for a range with that tag. This series handles that by introducing a bounded wakeup relay: a waiter that was woken but couldn't use the freed bit (it fell outside its allowed window) forwards the wakeup to another waiter. The relay is bounded by a credit budget refilled only by genuine completions, so it cannot cycle indefinitely. I think this overhead is acceptable as we're already in the slower path after exhausting the tag space.
The degenerate case when the number of users sharing the tag space exceeds the number of tags is not specially handled. If that happens, those users compete for the full tag space without fairness. The existing implementation lets each user get any 4 tags in this scenario, which is arbitrary. Duplicating that behavior would require re-introducing atomic counting, which this series aims to remove.
The 5th patch is a performance optimization to avoid recalculating the windows on every I/O (division + bitmap_weight). It computes the window only when the active set changes and caches it per queue/hctx, packed into a single u64 for a lockless fast-path read. It removes much of the infrastructure introduced in patches 1-3, but the series is presented as a 1:1 replacement first, then the optimization for easier review.
I am aware there are race windows with the purposefully lockless updates, but those are temporary and harmless. Windows are recomputed on every busy/idle transition and settle once the active set stabilizes. A torn u64 read on 32-bit is possible but results in a temporarily mis-sized window that self-corrects as tags get recycled.
The last patch enables scsi_debug to test the new fairness framework for various shared vs. private splits, and exposes shared_pct for host_tagset drivers where sharing may be harmful to performance. I understand based on the previous proposals there is use for such mechanisms for UFS.
Keith Busch (6):
lib/sbitmap: add ranged allocation, bounded wakeup relay, and ranged
weight
blk-mq: replace shared-tag fairness counter with allocation windows
blk-mq: factor out a per-hctx tag busy iterator
blk-mq: add a shared zone to tag fairness
blk-mq: cache shared-tag fairness windows
scsi: add shared-tag fairness to host_tagset drivers
block/blk-core.c | 2 +- block/blk-mq-debugfs.c | 2 +- block/blk-mq-tag.c | 179 ++++++++++++++++++++++++++++++---- block/blk-mq.c | 24 ++--- block/blk-mq.h | 102 +------------------ drivers/scsi/scsi_debug.c | 8 +- drivers/scsi/scsi_lib.c | 4 +- include/linux/blk-mq.h | 12 ++- include/linux/blkdev.h | 19 +++- include/linux/sbitmap.h | 53 ++++++++++ include/scsi/scsi_host.h | 8 ++ lib/sbitmap.c | 200 ++++++++++++++++++++++++++++++++++++++ 12 files changed, 470 insertions(+), 143 deletions(-)
Signature · 1 line
2.52.0