[RFC PATCH 0/6] sbitmap enforced fairness for blk-mq

[Keith Busch <kbusch@meta.com>]

From: Keith Busch <kbusch@kernel.org>

There have been a few proposals to remove the blk-mq tag fairness
algorithm:

 https://lore.kernel.org/linux-block/20240529213921.3166462-1-bvanassche@acm.org/
 https://lore.kernel.org/linux-block/20260609121806.2121755-1-sumit.saxena@broadcom.com/

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(-)

-- 
2.52.0