Skip to contentSkip to conversation

sbitmap enforced fairness for blk-mq

RFC PATCH In review Keith Busch 3 participants 9 messages Jul 6

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover 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
#1 lore raw

RFC PATCH 1/6 lib/sbitmap: add ranged allocation, bounded wakeup relay, and ranged weight

From: Keith Busch <[email protected]>

Add some helpers that let a caller carve a shared bitmap into per-user windows.

* sbitmap_queue_get_range() allocates a free bit only within requested range.
* sbitmap_queue_wake_up_relay() hands a wakeup to another waiter when the woken one cannot use the freed bit (it fell outside that waiter's window).
* sbitmap_weight_range() counts set (and not cleared) bits in a sub-range.

No callers yet. The intention is for blk-mq users for shared tag fairness without requiring per-io atomic accounting operations.

---
 include/linux/sbitmap.h |  53 +++++++++++
 lib/sbitmap.c           | 200 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 253 insertions(+)
include/linux/sbitmap.h +53 -0
index cc7ad189caa5c..9fceda5d9de51 100644
@@ -86,6 +86,7 @@ struct sbitmap {
 
 #define SBQ_WAIT_QUEUES 8
 #define SBQ_WAKE_BATCH 8
+#define SBQ_RELAY_BUDGET SBQ_WAKE_BATCH
 
 /**
  * struct sbq_wait_state - Wait queue in a &struct sbitmap_queue.
@@ -149,6 +150,14 @@ struct sbitmap_queue {
 	 * @wakeup_cnt: Number of thread wake ups issued.
 	 */
 	atomic_t wakeup_cnt;
+
+	/**
+	 * @relay_credits: Remaining range-relay wakeups allowed before the next
+	 * genuine completion. Refilled by sbitmap_queue_wake_up() and consumed
+	 * by sbitmap_queue_wake_up_relay(); bounds the relay chain so it cannot
+	 * cycle when no waiter can use a freed bit.
+	 */
+	atomic_t relay_credits;
 };
 
 /**
@@ -375,6 +384,18 @@ void sbitmap_show(struct sbitmap *sb, struct seq_file *m);
  */
 unsigned int sbitmap_weight(const struct sbitmap *sb);
 
+/**
+ * sbitmap_weight_range() - Return how many set and not cleared bits in a
+ * sub-range of a &struct sbitmap.
+ * @sb: Bitmap to check.
+ * @off: First bit of the range.
+ * @len: Number of bits in the range.
+ *
+ * Return: How many bits in [@off, @off + @len) are set and not cleared.
+ */
+unsigned int sbitmap_weight_range(const struct sbitmap *sb, unsigned int off,
+				  unsigned int len);
+
 /**
  * sbitmap_bitmap_show() - Write a hex dump of a &struct sbitmap to a &struct
  * seq_file.
@@ -472,6 +493,22 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
 int sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
 			      unsigned int shallow_depth);
 
+/**
+ * sbitmap_queue_get_range() - Try to allocate a free bit from a restricted
+ * range of a &struct sbitmap_queue, with preemption already disabled.
+ * @sbq: Bitmap queue to allocate from.
+ * @min: First bit (inclusive) the caller is allowed to allocate.
+ * @max: Last bit (exclusive) the caller is allowed to allocate.
+ *
+ * Allocation is confined to the [@min, @max) window. This lets several users
+ * share one bitmap while each is bounded to its own (possibly overlapping)
+ * window, providing fairness without a separate per-user accounting counter.
+ *
+ * Return: Non-negative allocated bit number if successful, -1 otherwise.
+ */
+int sbitmap_queue_get_range(struct sbitmap_queue *sbq, unsigned int min,
+			    unsigned int max);
+
 /**
  * sbitmap_queue_get() - Try to allocate a free bit from a &struct
  * sbitmap_queue.
@@ -575,6 +612,22 @@ void sbitmap_queue_wake_all(struct sbitmap_queue *sbq);
  */
 void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr);
 
+/**
+ * sbitmap_queue_wake_up_relay() - Relay a wakeup to the next waiter.
+ * @sbq: Bitmap queue to wake up.
+ * @cur: The relaying waiter's own wait queue, skipped so it does not wake
+ *       itself (it is about to sleep again); may be NULL.
+ *
+ * Wake a single waiter on the next active wait queue without touching the
+ * wake_batch accounting. Intended for range-limited allocation: a waiter that
+ * was woken but could not use the freed bit (it fell outside the waiter's
+ * allowed range) calls this to pass the wakeup along to another waiter that
+ * may be able to use it. The relay is bounded by a credit budget refilled
+ * only by genuine completions, so it cannot cycle indefinitely.
+ */
+void sbitmap_queue_wake_up_relay(struct sbitmap_queue *sbq,
+				 struct sbq_wait_state *cur);
+
 /**
  * sbitmap_queue_show() - Dump &struct sbitmap_queue information to a &struct
  * seq_file.
lib/sbitmap.c +200 -0

234 lines not on this page · raw message

Signature · 1 line
2.52.0
#2 lore raw

RFC PATCH 2/6 blk-mq: replace shared-tag fairness counter with allocation windows

In reply to Keith Busch

From: Keith Busch <[email protected]>

The per-request atomic active counter that hctx_may_queue() checks on every shared-tag allocation is costly under contention. Instead, confine each active queue to a slice of the shared bitmap and allocate from that, so one busy queue cannot starve the others. This removes per-IO atomic on the hot path. Fairness becomes structural to the sbitmap allocation range, so the counter and hctx_may_queue are removed.

---
 block/blk-core.c       |   2 +-
 block/blk-mq-debugfs.c |   2 +-
 block/blk-mq-tag.c     | 113 +++++++++++++++++++++++++++++++++++++++--
 block/blk-mq.c         |  21 ++------
 block/blk-mq.h         | 102 +------------------------------------
 include/linux/blk-mq.h |  15 ++++--
 include/linux/blkdev.h |   6 ++-
 7 files changed, 135 insertions(+), 126 deletions(-)
block/blk-core.c +1 -1
index 365641266c9e8..7e719b90d8a66 100644
@@ -464,7 +464,7 @@ struct request_queue *blk_alloc_queue(struct queue_limits *lim, int node_id)
 
 	q->node = node_id;
 
-	atomic_set(&q->nr_active_requests_shared_tags, 0);
+	q->tag_win_slot = -1;
 
 	timer_setup(&q->timeout, blk_rq_timed_out_timer, 0);
 	INIT_WORK(&q->timeout_work, blk_timeout_work);
block/blk-mq-debugfs.c +1 -1
index 6754d8f9449c1..4b47a3322ff72 100644
@@ -480,7 +480,7 @@ static int hctx_active_show(void *data, struct seq_file *m)
 {
 	struct blk_mq_hw_ctx *hctx = data;
 
-	seq_printf(m, "%d\n", __blk_mq_active_requests(hctx));
+	seq_printf(m, "%u\n", blk_mq_hctx_active(hctx));
 	return 0;
 }
 
block/blk-mq-tag.c +109 -4

172 lines not on this page · raw message

block/blk-mq.c +5 -16
index 2c850330a32bc..56ab6ac5ec696 100644
@@ -489,8 +489,6 @@ __blk_mq_alloc_requests_batch(struct blk_mq_alloc_data *data)
 		}
 	} while (data->nr_tags > nr);
 
-	if (!(data->rq_flags & RQF_SCHED_TAGS))
-		blk_mq_add_active_requests(data->hctx, nr);
 	/* caller already holds a reference, add for remainder */
 	percpu_ref_get_many(&data->q->q_usage_counter, nr - 1);
 	data->nr_tags -= nr;
@@ -587,8 +585,6 @@ static struct request *__blk_mq_alloc_requests(struct blk_mq_alloc_data *data)
 		goto retry;
 	}
 
-	if (!(data->rq_flags & RQF_SCHED_TAGS))
-		blk_mq_inc_active_requests(data->hctx);
 	rq = blk_mq_rq_ctx_init(data, blk_mq_tags_from_data(data), tag);
 	blk_mq_rq_time_init(rq, alloc_time_ns);
 	return rq;
@@ -763,8 +759,6 @@ struct request *blk_mq_alloc_request_hctx(struct request_queue *q,
 	tag = blk_mq_get_tag(&data);
 	if (tag == BLK_MQ_NO_TAG)
 		goto out_queue_exit;
-	if (!(data.rq_flags & RQF_SCHED_TAGS))
-		blk_mq_inc_active_requests(data.hctx);
 	rq = blk_mq_rq_ctx_init(&data, blk_mq_tags_from_data(&data), tag);
 	blk_mq_rq_time_init(rq, alloc_time_ns);
 	rq->__data_len = 0;
@@ -807,10 +801,8 @@ static void __blk_mq_free_request(struct request *rq)
 	blk_pm_mark_last_busy(rq);
 	rq->mq_hctx = NULL;
 
-	if (rq->tag != BLK_MQ_NO_TAG) {
-		blk_mq_dec_active_requests(hctx);
+	if (rq->tag != BLK_MQ_NO_TAG)
 		blk_mq_put_tag(hctx->tags, ctx, rq->tag);
-	}
 	if (sched_tag != BLK_MQ_NO_TAG)
 		blk_mq_put_tag(hctx->sched_tags, ctx, sched_tag);
 	blk_mq_sched_restart(hctx);
@@ -1157,8 +1149,6 @@ static inline void blk_mq_flush_tag_batch(struct blk_mq_hw_ctx *hctx,
 {
 	struct request_queue *q = hctx->queue;
 
-	blk_mq_sub_active_requests(hctx, nr_tags);
-
 	blk_mq_put_tags(hctx->tags, tag_array, nr_tags);
 	percpu_ref_put_many(&q->q_usage_counter, nr_tags);
 }
@@ -1844,17 +1834,16 @@ bool __blk_mq_alloc_driver_tag(struct request *rq)
 	if (blk_mq_tag_is_reserved(rq->mq_hctx->sched_tags, rq->internal_tag)) {
 		bt = &rq->mq_hctx->tags->breserved_tags;
 		tag_offset = 0;
+		tag = __sbitmap_queue_get(bt);
 	} else {
-		if (!hctx_may_queue(rq->mq_hctx, bt))
-			return false;
+		/* Fairness on the shared driver tags via the allocation window. */
+		tag = blk_mq_get_tag_window(rq->mq_hctx, bt);
 	}
 
-	tag = __sbitmap_queue_get(bt);
 	if (tag == BLK_MQ_NO_TAG)
 		return false;
 
 	rq->tag = tag + tag_offset;
-	blk_mq_inc_active_requests(rq->mq_hctx);
 	return true;
 }
 
@@ -4028,7 +4017,7 @@ blk_mq_alloc_hctx(struct request_queue *q, struct blk_mq_tag_set *set,
 	if (!zalloc_cpumask_var_node(&hctx->cpumask, gfp, node))
 		goto free_hctx;
 
-	atomic_set(&hctx->nr_active, 0);
+	hctx->tag_win_slot = -1;
 	if (node == NUMA_NO_NODE)
 		node = set->numa_node;
 	hctx->numa_node = node;
block/blk-mq.h +2 -100

123 lines not on this page · raw message

include/linux/blk-mq.h +12 -3
index af878597afb8c..22cc09d5ef320 100644
@@ -433,10 +433,12 @@ struct blk_mq_hw_ctx {
 	unsigned int		queue_num;
 
 	/**
-	 * @nr_active: Number of active requests. Only used when a tag set is
-	 * shared across request queues.
+	 * @tag_win_slot: Assigned fairness allocation-window slot within this
+	 * hctx's tags, or -1 if none. Used for non-HCTX_SHARED shared tag sets
+	 * (the per-hctx analogue of request_queue.tag_win_slot). Protected by
+	 * the tags->lock.
 	 */
-	atomic_t		nr_active;
+	int			tag_win_slot;
 
 	/** @cpuhp_online: List to store request if CPU is going to die */
 	struct hlist_node	cpuhp_online;
@@ -776,6 +778,13 @@ struct blk_mq_tags {
 	unsigned int nr_reserved_tags;
 	unsigned int active_queues;
 
+	/*
+	 * Bitmap of assigned per-queue fairness window slots, @nr_tags -
+	 * @nr_reserved_tags bits wide (windowing is moot once active users
+	 * exceed that). Protected by @lock.
+	 */
+	unsigned long *active_slots;
+
 	struct sbitmap_queue bitmap_tags;
 	struct sbitmap_queue breserved_tags;
 
include/linux/blkdev.h +5 -1
index 9213a5716f95a..86b16bd8b9c17 100644
@@ -573,7 +573,11 @@ struct request_queue {
 	struct timer_list	timeout;
 	struct work_struct	timeout_work;
 
-	atomic_t		nr_active_requests_shared_tags;
+	/*
+	 * Assigned allocation-window slot for shared (HCTX_SHARED) tag-set
+	 * fairness, or -1 if none. Protected by the shared tags->lock.
+	 */
+	int			tag_win_slot;
 
 	struct blk_mq_tags	*sched_shared_tags;
 
Signature · 1 line
2.52.0
#3 lore raw

RFC PATCH 3/6 blk-mq: factor out a per-hctx tag busy iterator

In reply to Keith Busch

From: Keith Busch <[email protected]>

Make a helper for walking the busy tags of specific hardware queue based on the per-hctx walk into __blk_mq_hctx_tag_busy_iter() so it can be reused to iterate a single hardware queue's tags. No functional change.

---
 block/blk-mq-tag.c | 40 ++++++++++++++++++++++++----------------
 1 file changed, 24 insertions(+), 16 deletions(-)
block/blk-mq-tag.c +19 -16
index 0dd497225c74a..58cf480df9c69 100644
@@ -582,6 +582,28 @@ void blk_mq_tagset_wait_completed_request(struct blk_mq_tag_set *tagset)
 }
 EXPORT_SYMBOL(blk_mq_tagset_wait_completed_request);
 
+static void __blk_mq_hctx_tag_busy_iter(struct blk_mq_hw_ctx *hctx,
+					busy_tag_iter_fn *fn, void *priv)
+{
+	struct blk_mq_tags *tags = hctx->tags;
+
+	/*
+	 * If no software queues are currently mapped to this hardware queue,
+	 * there's nothing to check
+	 */
+	if (!blk_mq_hw_queue_mapped(hctx))
+		return;
+
+	if (tags->nr_reserved_tags)
+		bt_for_each(hctx, hctx->queue, &tags->breserved_tags, fn, priv, true);
+	bt_for_each(hctx, hctx->queue, &tags->bitmap_tags, fn, priv, false);
+}
+
 /**
  * blk_mq_queue_tag_busy_iter - iterate over all requests with a driver tag
  * @q:		Request queue to examine.
@@ -621,22 +643,8 @@ void blk_mq_queue_tag_busy_iter(struct request_queue *q, busy_tag_iter_fn *fn,
 		struct blk_mq_hw_ctx *hctx;
 		unsigned long i;
 
-		queue_for_each_hw_ctx(q, hctx, i) {
-			struct blk_mq_tags *tags = hctx->tags;
-			struct sbitmap_queue *bresv = &tags->breserved_tags;
-			struct sbitmap_queue *btags = &tags->bitmap_tags;
-
-			/*
-			 * If no software queues are currently mapped to this
-			 * hardware queue, there's nothing to check
-			 */
-			if (!blk_mq_hw_queue_mapped(hctx))
-				continue;
-
-			if (tags->nr_reserved_tags)
-				bt_for_each(hctx, q, bresv, fn, priv, true);
-			bt_for_each(hctx, q, btags, fn, priv, false);
-		}
+		queue_for_each_hw_ctx(q, hctx, i)
+			__blk_mq_hctx_tag_busy_iter(hctx, fn, priv);
 	}
 	srcu_read_unlock(&q->tag_set->tags_srcu, srcu_idx);
 	blk_queue_exit(q);
Signature · 1 line
2.52.0
#4 lore raw

RFC PATCH 4/6 blk-mq: add a shared zone to tag fairness

In reply to Keith Busch

From: Keith Busch <[email protected]>

Private slices of the sbitmap can strand an under utilized queue's tags. Allow a driver to request some percentage of tags to be reserved into a common shared pool that anyone may allocate from. The default 0 means the entire tag set is divided up among its users; 100 means no one has an exclusive window and can therefore allocate from the entire tag space.

Shared tags being outside the private zone makes it so we can't do a sbitmap range weight to find its active commands, so the debugfs count may no longer accurate. Count the hctx's actual tags via __blk_mq_hctx_tag_busy_iter() to provide accuracy over performance for debugfs.

---
 block/blk-mq-tag.c     | 94 +++++++++++++++++++++++++++++++-----------
 block/blk-mq.c         |  3 ++
 include/linux/blk-mq.h |  5 +++
 3 files changed, 79 insertions(+), 23 deletions(-)
block/blk-mq-tag.c +71 -23
index 58cf480df9c69..aa7dbceb60dcd 100644
@@ -144,54 +144,79 @@ static inline bool blk_mq_tag_is_windowed(struct blk_mq_alloc_data *data)
 	       (data->hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED);
 }
 
+struct blk_mq_tag_win {
+	unsigned int priv_min;
+	unsigned int priv_max;
+	unsigned int shared_min;
+	unsigned int shared_max;
+};
+
 static bool blk_mq_tag_active_window(struct blk_mq_hw_ctx *hctx,
-				     unsigned int depth, unsigned int *min,
-				     unsigned int *max)
+				     unsigned int depth,
+				     struct blk_mq_tag_win *w)
 {
 	unsigned int users = READ_ONCE(hctx->tags->active_queues);
 	int slot = READ_ONCE(*blk_mq_tag_win_slot(hctx));
-	unsigned int p, rem, pos;
+	unsigned int fair, priv, pct, pos;
+
+	if (users <= 1 || depth <= 1)
+		return false;
 
-	if (users <= 1 || slot < 0 || depth <= 1)
+	fair = depth / users;
+	if (!fair)
 		return false;
 
-	p = depth / users;
-	if (!p)
+	pct = 100 - min(hctx->queue->tag_set->shared_pct, 100u);
+	priv = fair * pct / 100;
+	if (!priv)
 		return false;
 
 	/*
 	 * Slots are allocated from a bitmap and freed out of order, so a slot
 	 * index can exceed the active-user count once lower slots are freed.
 	 * Convert it to a position based on how many active slots precede it.
+	 * If a slot could not be assigned, the window is confined to the
+	 * shared range.
 	 */
-	pos = bitmap_weight(hctx->tags->active_slots, slot);
-	rem = depth - p * users;
-	*min = pos * p;
-	*max = pos * p + p + rem;
-	if (*max > depth)
-		*max = depth;
+	pos = slot >= 0 ? bitmap_weight(hctx->tags->active_slots, slot) : users;
+	if (pos < users) {
+		w->priv_min = pos * priv;
+		w->priv_max = w->priv_min + priv;
+	} else {
+		w->priv_min = w->priv_max = 0;
+	}
 
+	w->shared_min = min(users * priv, depth);
+	w->shared_max = depth;
+
+	if (w->priv_min == w->priv_max && w->shared_min == w->shared_max)
+		return false;
 	return true;
 }
 
-int blk_mq_get_tag_window(struct blk_mq_hw_ctx *hctx, struct sbitmap_queue *bt)
+static int __blk_mq_get_tag_window(struct sbitmap_queue *bt,
+				   struct blk_mq_tag_win *w)
 {
-	unsigned int min, max;
+	if (w->priv_max > w->priv_min) {
+		int tag = sbitmap_queue_get_range(bt, w->priv_min, w->priv_max);
 
-	if (blk_mq_tag_active_window(hctx, bt->sb.depth, &min, &max))
-		return sbitmap_queue_get_range(bt, min, max);
-	return __sbitmap_queue_get(bt);
+		if (tag >= 0)
+			return tag;
+	}
+
+	if (w->shared_max > w->shared_min)
+		return sbitmap_queue_get_range(bt, w->shared_min, w->shared_max);
 
+	return BLK_MQ_NO_TAG;
 }
 
-unsigned int blk_mq_hctx_active(struct blk_mq_hw_ctx *hctx)
+int blk_mq_get_tag_window(struct blk_mq_hw_ctx *hctx, struct sbitmap_queue *bt)
 {
-	struct sbitmap *sb = &hctx->tags->bitmap_tags.sb;
-	unsigned int min, max;
+	struct blk_mq_tag_win w;
 
-	if (!blk_mq_tag_active_window(hctx, sb->depth, &min, &max))
-		return sbitmap_weight(sb);
-	return sbitmap_weight_range(sb, min, max - min);
+	if (blk_mq_tag_active_window(hctx, bt->sb.depth, &w))
+		return __blk_mq_get_tag_window(bt, &w);
+	return __sbitmap_queue_get(bt);
 }
 
 static int __blk_mq_get_tag(struct blk_mq_alloc_data *data,
@@ -604,6 +629,29 @@ static void __blk_mq_hctx_tag_busy_iter(struct blk_mq_hw_ctx *hctx,
 	bt_for_each(hctx, hctx->queue, &tags->bitmap_tags, fn, priv, false);
 }
 
+static bool blk_mq_count_active(struct request *rq, void *priv)
+{
+	(*(unsigned int *)priv)++;
+	return true;
+}
+
+unsigned int blk_mq_hctx_active(struct blk_mq_hw_ctx *hctx)
+{
+	struct request_queue *q = hctx->queue;
+	unsigned int count = 0;
+	int srcu_idx;
+
+	if (!percpu_ref_tryget(&q->q_usage_counter))
+	        return 0;
+
+	srcu_idx = srcu_read_lock(&q->tag_set->tags_srcu);
+	__blk_mq_hctx_tag_busy_iter(hctx, blk_mq_count_active, &count);
+	srcu_read_unlock(&q->tag_set->tags_srcu, srcu_idx);
+
+	blk_queue_exit(q);
+	return count;
+}
+
 /**
  * blk_mq_queue_tag_busy_iter - iterate over all requests with a driver tag
  * @q:		Request queue to examine.
block/blk-mq.c +3 -0
index 56ab6ac5ec696..cc56baee74fe8 100644
@@ -4845,6 +4845,9 @@ int blk_mq_alloc_tag_set(struct blk_mq_tag_set *set)
 		set->queue_depth = BLK_MQ_MAX_DEPTH;
 	}
 
+	if (set->shared_pct > 100)
+		set->shared_pct = 100;
+
 	if (!set->nr_maps)
 		set->nr_maps = 1;
 	else if (set->nr_maps > HCTX_MAX_TYPES)
include/linux/blk-mq.h +5 -0
index 22cc09d5ef320..59847ac7d319c 100644
@@ -515,6 +515,10 @@ enum hctx_type {
  * @numa_node:	   NUMA node the storage adapter has been connected to.
  * @timeout:	   Request processing timeout in jiffies.
  * @flags:	   Zero or more BLK_MQ_F_* flags.
+ * @shared_pct:	   Percent of tags dedicated to non-exclusive use. 0 means
+ *		   the entire tagset is divided among the users for exclusive
+ *		   per-user access, and 100 means the entire tag space is
+ *		   available to all queue contexts that share it.
  * @driver_data:   Pointer to data owned by the block driver that created this
  *		   tag set.
  * @tags:	   Tag sets. One tag set per hardware queue. Has @nr_hw_queues
@@ -544,6 +548,7 @@ struct blk_mq_tag_set {
 	int			numa_node;
 	unsigned int		timeout;
 	unsigned int		flags;
+	unsigned int		shared_pct;
 	void			*driver_data;
 
 	struct blk_mq_tags	**tags;
Signature · 1 line
2.52.0
#5 lore raw

RFC PATCH 5/6 blk-mq: cache shared-tag fairness windows

In reply to Keith Busch

From: Keith Busch <[email protected]>

The windowed allocation path recomputed each queue's window on every tag allocation, which includes costly division and bitmap weight operations. Compute the window only when the active set changes and cache it per queue/hctx, packed into a single u64 so the allocation fast path reads it with one READ_ONCE and no arithmetic. A lock-free rebalance recomputes the windows at each busy/idle transition for all contexts using that tagset, assigning positions in tag_list order. This also drops the need for the per-queue/hctx slot bitmap.

---
 block/blk-core.c       |   2 +-
 block/blk-mq-tag.c     | 180 ++++++++++++++++++-----------------------
 block/blk-mq.c         |   2 +-
 include/linux/blk-mq.h |  16 +---
 include/linux/blkdev.h |  19 ++++-
 5 files changed, 102 insertions(+), 117 deletions(-)
block/blk-core.c +1 -1
index 7e719b90d8a66..85f7ad22f6461 100644
@@ -464,7 +464,7 @@ struct request_queue *blk_alloc_queue(struct queue_limits *lim, int node_id)
 
 	q->node = node_id;
 
-	q->tag_win_slot = -1;
+	q->tag_win = (struct blk_mq_tag_win){ .shared_max = U16_MAX };
 
 	timer_setup(&q->timeout, blk_rq_timed_out_timer, 0);
 	INIT_WORK(&q->timeout_work, blk_timeout_work);
block/blk-mq-tag.c +80 -100

244 lines not on this page · raw message

block/blk-mq.c +1 -1
index cc56baee74fe8..ef8699735aa95 100644
@@ -4017,7 +4017,7 @@ blk_mq_alloc_hctx(struct request_queue *q, struct blk_mq_tag_set *set,
 	if (!zalloc_cpumask_var_node(&hctx->cpumask, gfp, node))
 		goto free_hctx;
 
-	hctx->tag_win_slot = -1;
+	hctx->tag_win = (struct blk_mq_tag_win){ .shared_max = U16_MAX };
 	if (node == NUMA_NO_NODE)
 		node = set->numa_node;
 	hctx->numa_node = node;
include/linux/blk-mq.h +4 -12
index 59847ac7d319c..0b1e1697e1736 100644
@@ -433,12 +433,11 @@ struct blk_mq_hw_ctx {
 	unsigned int		queue_num;
 
 	/**
-	 * @tag_win_slot: Assigned fairness allocation-window slot within this
-	 * hctx's tags, or -1 if none. Used for non-HCTX_SHARED shared tag sets
-	 * (the per-hctx analogue of request_queue.tag_win_slot). Protected by
-	 * the tags->lock.
+	 * @tag_win: Cached fairness allocation window for non-HCTX_SHARED shared
+	 * tag sets (each per-hw-queue bitmap divided among its hctxs). Written by
+	 * the rebalance walk, read locklessly on the allocation path.
 	 */
-	int			tag_win_slot;
+	struct blk_mq_tag_win	tag_win;
 
 	/** @cpuhp_online: List to store request if CPU is going to die */
 	struct hlist_node	cpuhp_online;
@@ -783,13 +782,6 @@ struct blk_mq_tags {
 	unsigned int nr_reserved_tags;
 	unsigned int active_queues;
 
-	/*
-	 * Bitmap of assigned per-queue fairness window slots, @nr_tags -
-	 * @nr_reserved_tags bits wide (windowing is moot once active users
-	 * exceed that). Protected by @lock.
-	 */
-	unsigned long *active_slots;
-
 	struct sbitmap_queue bitmap_tags;
 	struct sbitmap_queue breserved_tags;
 
include/linux/blkdev.h +16 -3
index 86b16bd8b9c17..7b55ce6a3fd2b 100644
@@ -487,6 +487,18 @@ struct blk_independent_access_ranges {
 	struct blk_independent_access_range	ia_range[];
 };
 
+struct blk_mq_tag_win {
+	union {
+		struct {
+			u16	priv_min;
+			u16	priv_max;
+			u16	shared_min;
+			u16	shared_max;
+		};
+		u64	v;
+	};
+};
+
 struct request_queue {
 	/*
 	 * The queue owner gets to use this for whatever they like.
@@ -574,10 +586,11 @@ struct request_queue {
 	struct work_struct	timeout_work;
 
 	/*
-	 * Assigned allocation-window slot for shared (HCTX_SHARED) tag-set
-	 * fairness, or -1 if none. Protected by the shared tags->lock.
+	 * Cached fairness allocation window for HCTX_SHARED tag sets (the one
+	 * global bitmap divided among request_queues). Written by the rebalance
+	 * walk, read locklessly on the allocation path.
 	 */
-	int			tag_win_slot;
+	struct blk_mq_tag_win	tag_win;
 
 	struct blk_mq_tags	*sched_shared_tags;
 
Signature · 1 line
2.52.0
#6 lore raw

RFC PATCH 6/6 scsi: add shared-tag fairness to host_tagset drivers

In reply to Keith Busch

From: Keith Busch <[email protected]>

Introduce a per-host shared_pct into the scsi block tag set so host_tagset drivers can choose how much of the shared pool stays carved into per-LUN exclusivity versus shared by everyone. This may be useful for UFS where the sharing is harmful to performance.

---
 drivers/scsi/scsi_debug.c | 8 +++++++-
 drivers/scsi/scsi_lib.c   | 4 +++-
 include/scsi/scsi_host.h  | 8 ++++++++
 3 files changed, 18 insertions(+), 2 deletions(-)
drivers/scsi/scsi_debug.c +7 -1
index 9d1c9c41d0f99..cb2bec76ba3de 100644
@@ -905,6 +905,7 @@ static int sdebug_every_nth = DEF_EVERY_NTH;
 static int sdebug_fake_rw = DEF_FAKE_RW;
 static unsigned int sdebug_guard = DEF_GUARD;
 static int sdebug_host_max_queue;	/* per host */
+static int sdebug_shared_pct;		/* host_tagset shared tag pool % */
 static int sdebug_lowest_aligned = DEF_LOWEST_ALIGNED;
 static int sdebug_max_luns = DEF_MAX_LUNS;
 static int sdebug_max_queue = SDEBUG_CANQUEUE;	/* per submit queue */
@@ -7343,6 +7344,7 @@ module_param_named(fake_rw, sdebug_fake_rw, int, S_IRUGO | S_IWUSR);
 module_param_named(guard, sdebug_guard, uint, S_IRUGO);
 module_param_named(host_lock, sdebug_host_lock, bool, S_IRUGO | S_IWUSR);
 module_param_named(host_max_queue, sdebug_host_max_queue, int, S_IRUGO);
+module_param_named(shared_pct, sdebug_shared_pct, int, S_IRUGO);
 module_param_string(inq_product, sdebug_inq_product_id,
 		    sizeof(sdebug_inq_product_id), S_IRUGO | S_IWUSR);
 module_param_string(inq_rev, sdebug_inq_product_rev,
@@ -7427,6 +7429,8 @@ MODULE_PARM_DESC(guard, "protection checksum: 0=crc, 1=ip (def=0)");
 MODULE_PARM_DESC(host_lock, "host_lock is ignored (def=0)");
 MODULE_PARM_DESC(host_max_queue,
 		 "host max # of queued cmds (0 to max(def) [max_queue fixed equal for !0])");
+MODULE_PARM_DESC(shared_pct,
+		 "host_tagset: %% of the shared tag pool shared by all LUNs (0=exclusive, 100=no fairness, def=0)");
 MODULE_PARM_DESC(inq_product, "SCSI INQUIRY product string (def=\"scsi_debug\")");
 MODULE_PARM_DESC(inq_rev, "SCSI INQUIRY revision string (def=\""
 		 SDEBUG_VERSION "\")");
@@ -9569,8 +9573,10 @@ static int sdebug_driver_probe(struct device *dev)
 	 * following should give the same answer for each host.
 	 */
 	hpnt->nr_hw_queues = submit_queues;
-	if (sdebug_host_max_queue)
+	if (sdebug_host_max_queue) {
 		hpnt->host_tagset = 1;
+		hpnt->shared_pct = sdebug_shared_pct;
+	}
 
 	/* poll queues are possible for nr_hw_queues > 1 */
 	if (hpnt->nr_hw_queues == 1 || (poll_queues < 1)) {
drivers/scsi/scsi_lib.c +3 -1
index 22e2e3223440d..efcb49af899a2 100644
@@ -2152,8 +2152,10 @@ int scsi_mq_setup_tags(struct Scsi_Host *shost)
 	if (shost->queuecommand_may_block)
 		tag_set->flags |= BLK_MQ_F_BLOCKING;
 	tag_set->driver_data = shost;
-	if (shost->host_tagset)
+	if (shost->host_tagset) {
 		tag_set->flags |= BLK_MQ_F_TAG_HCTX_SHARED;
+		tag_set->shared_pct = shost->shared_pct;
+	}
 
 	return blk_mq_alloc_tag_set(tag_set);
 }
include/scsi/scsi_host.h +8 -0
index 7e2011830ba4b..68c99bc7ad865 100644
@@ -694,6 +694,14 @@ struct Scsi_Host {
 	/* The queuecommand callback may block. See also BLK_MQ_F_BLOCKING. */
 	unsigned queuecommand_may_block:1;
 
+	/*
+	 * For host_tagset hosts: percent of the shared tag pool made available
+	 * to all LUNs rather than reserved as per-LUN exclusive floors. See
+	 * blk_mq_tag_set.shared_pct. 0 (default) divides the pool exclusively;
+	 * 100 lets every LUN allocate from the whole pool with no fairness.
+	 */
+	unsigned int shared_pct;
+
 	/* Host responded with short (<36 bytes) INQUIRY result */
 	unsigned short_inquiry:1;
 
Signature · 1 line
2.52.0
#7 lore raw
In reply to Keith Busch
Quoted 5 lines · Keith Busch

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]/

There have been more proposals to remove the fairness code from other kernel contributors. I proposed to remove the tag fairness code because prior attempts to solve UFS performance issues were not good enough for the upstream kernel.

Quoted 4 lines

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.

Has this starving phenomenon ever been observed? I think that the measurement data that I published shows that the fairness properties of the current sbitmap implementation are good enough.

Quoted 11 lines

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.

What software layer is expected to set these percentages? My patch series intentionally removes the fairness mechanism because that's exactly what the legacy code path in the UFS driver needs. The UFS WLUN and data logical units share a single tag set. Any activity on the WLUN increases the number of active queues and hence reduces the number of tags available for any data logical units.

Additionally, what is the performance impact of this patch series? Removing the tag fairness code increases IOPS so this patch series probably has a performance impact.

Thanks,

Bart.

#8 lore raw
Quoted 12 lines · Bart Van Assche
Quoted 5 lines · Keith Busch

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]/

There have been more proposals to remove the fairness code from other kernel contributors. I proposed to remove the tag fairness code because prior attempts to solve UFS performance issues were not good enough for the upstream kernel.

Quoted 6 lines
Quoted 4 lines

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.

Has this starving phenomenon ever been observed?

If you're asking if a production workload sees the phenomenon, no because they run the code that has enforced fairness.

Quoted 3 lines

I think that the
measurement data that I published shows that the fairness properties of the current sbitmap implementation are good enough.

I can trivially wire up a test where one queue allocates 100% of the tags for long running commands, and all the other queues that want to start a short running command can't proceed.

Quoted 6 lines
Quoted 4 lines

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.

What software layer is expected to set these percentages?

It's a tagset parameter that the LLD can set to whatever it needs.

Quoted 8 lines

My patch
series intentionally removes the fairness mechanism because that's exactly what the legacy code path in the UFS driver needs. The UFS WLUN and data logical units share a single tag set. Any activity on the WLUN increases the number of active queues and hence reduces the number of tags available for any data logical units.

Additionally, what is the performance impact of this patch series?

It removes the per-io atomics, so impact is it goes faster if that was your bottle-neck.

Quoted 2 lines

Removing the tag fairness code increases IOPS so this patch series probably has a performance impact.

You can declare the entire tagset is shared if you want. That should get you what you were going for, but we still have an option to spatially constrain others that want fairness with this series.