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

[Keith Busch <kbusch@meta.com>]

From: Keith Busch <kbusch@kernel.org>

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.

Link: https://lore.kernel.org/linux-block/20240529213921.3166462-1-bvanassche@acm.org/
Link: https://lore.kernel.org/linux-block/20260609121806.2121755-1-sumit.saxena@broadcom.com/
Signed-off-by: Keith Busch <kbusch@kernel.org>
---
 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(-)

diff --git a/block/blk-core.c b/block/blk-core.c
index 365641266c9e8..7e719b90d8a66 100644
--- a/block/blk-core.c
+++ b/block/blk-core.c
@@ -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);
diff --git a/block/blk-mq-debugfs.c b/block/blk-mq-debugfs.c
index 6754d8f9449c1..4b47a3322ff72 100644
--- a/block/blk-mq-debugfs.c
+++ b/block/blk-mq-debugfs.c
@@ -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;
 }
 
diff --git a/block/blk-mq-tag.c b/block/blk-mq-tag.c
index 35deee5bbc739..0dd497225c74a 100644
--- a/block/blk-mq-tag.c
+++ b/block/blk-mq-tag.c
@@ -33,6 +33,18 @@ static void blk_mq_update_wake_batch(struct blk_mq_tags *tags,
 			users);
 }
 
+/*
+ * Where this queue's fairness allocation-window slot is stored. HCTX_SHARED
+ * tag sets divide one global bitmap among request_queues (slot per queue);
+ * QUEUE_SHARED tag sets divide each per-hw-queue bitmap among the hctxs
+ * sharing it (slot per hctx).
+ */
+static int *blk_mq_tag_win_slot(struct blk_mq_hw_ctx *hctx)
+{
+	return blk_mq_is_shared_tags(hctx->flags) ?
+		&hctx->queue->tag_win_slot : &hctx->tag_win_slot;
+}
+
 /*
  * If a previously inactive queue goes active, bump the active user count.
  * We need to do this before try to allocate driver tag, then even if fail
@@ -65,6 +77,15 @@ void __blk_mq_tag_busy(struct blk_mq_hw_ctx *hctx)
 	users = tags->active_queues + 1;
 	WRITE_ONCE(tags->active_queues, users);
 	blk_mq_update_wake_batch(tags, users);
+	if (tags->active_slots) {
+		unsigned int nbits = tags->bitmap_tags.sb.depth;
+		unsigned int slot = find_first_zero_bit(tags->active_slots, nbits);
+
+		if (slot < nbits) {
+			set_bit(slot, tags->active_slots);
+			WRITE_ONCE(*blk_mq_tag_win_slot(hctx), slot);
+		}
+	}
 	spin_unlock_irqrestore(&tags->lock, flags);
 }
 
@@ -102,17 +123,82 @@ void __blk_mq_tag_idle(struct blk_mq_hw_ctx *hctx)
 	users = tags->active_queues - 1;
 	WRITE_ONCE(tags->active_queues, users);
 	blk_mq_update_wake_batch(tags, users);
+	if (tags->active_slots) {
+		int *slotp = blk_mq_tag_win_slot(hctx);
+		int slot = READ_ONCE(*slotp);
+
+		if (slot >= 0) {
+			clear_bit(slot, tags->active_slots);
+			WRITE_ONCE(*slotp, -1);
+		}
+	}
 	spin_unlock_irq(&tags->lock);
 
 	blk_mq_tag_wakeup_all(tags, false);
 }
 
+static inline bool blk_mq_tag_is_windowed(struct blk_mq_alloc_data *data)
+{
+	return !data->q->elevator &&
+	       !(data->flags & BLK_MQ_REQ_RESERVED) &&
+	       (data->hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED);
+}
+
+static bool blk_mq_tag_active_window(struct blk_mq_hw_ctx *hctx,
+				     unsigned int depth, unsigned int *min,
+				     unsigned int *max)
+{
+	unsigned int users = READ_ONCE(hctx->tags->active_queues);
+	int slot = READ_ONCE(*blk_mq_tag_win_slot(hctx));
+	unsigned int p, rem, pos;
+
+	if (users <= 1 || slot < 0 || depth <= 1)
+		return false;
+
+	p = depth / users;
+	if (!p)
+		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.
+	 */
+	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;
+
+	return true;
+}
+
+int blk_mq_get_tag_window(struct blk_mq_hw_ctx *hctx, struct sbitmap_queue *bt)
+{
+	unsigned int min, 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);
+
+}
+
+unsigned int blk_mq_hctx_active(struct blk_mq_hw_ctx *hctx)
+{
+	struct sbitmap *sb = &hctx->tags->bitmap_tags.sb;
+	unsigned int min, max;
+
+	if (!blk_mq_tag_active_window(hctx, sb->depth, &min, &max))
+		return sbitmap_weight(sb);
+	return sbitmap_weight_range(sb, min, max - min);
+}
+
 static int __blk_mq_get_tag(struct blk_mq_alloc_data *data,
 			    struct sbitmap_queue *bt)
 {
-	if (!data->q->elevator && !(data->flags & BLK_MQ_REQ_RESERVED) &&
-			!hctx_may_queue(data->hctx, bt))
-		return BLK_MQ_NO_TAG;
+	if (blk_mq_tag_is_windowed(data))
+		return blk_mq_get_tag_window(data->hctx, bt);
 
 	if (data->shallow_depth)
 		return sbitmap_queue_get_shallow(bt, data->shallow_depth);
@@ -142,6 +228,7 @@ unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
 	struct sbq_wait_state *ws;
 	DEFINE_SBQ_WAIT(wait);
 	unsigned int tag_offset;
+	bool slept = false;
 	int tag;
 
 	if (data->flags & BLK_MQ_REQ_RESERVED) {
@@ -193,8 +280,17 @@ unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
 		if (tag != BLK_MQ_NO_TAG)
 			break;
 
+		/*
+		 * We were previously woken but still cannot allocate within our
+		 * window: the freed bit belonged to another queue's window.
+		 * Relay the wakeup so a waiter that can use it gets to run.
+		 */
+		if (slept && blk_mq_tag_is_windowed(data))
+			sbitmap_queue_wake_up_relay(bt, ws);
+
 		bt_prev = bt;
 		io_schedule();
+		slept = true;
 
 		sbitmap_finish_wait(bt, ws, &wait);
 
@@ -574,8 +670,14 @@ struct blk_mq_tags *blk_mq_init_tags(unsigned int total_tags,
 	spin_lock_init(&tags->lock);
 	INIT_LIST_HEAD(&tags->page_list);
 
+	if (depth) {
+		tags->active_slots = bitmap_zalloc(depth, GFP_KERNEL);
+		if (!tags->active_slots)
+			goto out_free_tags;
+	}
+
 	if (bt_alloc(&tags->bitmap_tags, depth, round_robin, node))
-		goto out_free_tags;
+		goto out_free_slots;
 	if (bt_alloc(&tags->breserved_tags, reserved_tags, round_robin, node))
 		goto out_free_bitmap_tags;
 
@@ -583,6 +685,8 @@ struct blk_mq_tags *blk_mq_init_tags(unsigned int total_tags,
 
 out_free_bitmap_tags:
 	sbitmap_queue_free(&tags->bitmap_tags);
+out_free_slots:
+	bitmap_free(tags->active_slots);
 out_free_tags:
 	kfree(tags);
 	return NULL;
@@ -611,6 +715,7 @@ void blk_mq_free_tags(struct blk_mq_tag_set *set, struct blk_mq_tags *tags)
 {
 	sbitmap_queue_free(&tags->bitmap_tags);
 	sbitmap_queue_free(&tags->breserved_tags);
+	bitmap_free(tags->active_slots);
 
 	/* if tags pages is not allocated yet, free tags directly */
 	if (list_empty(&tags->page_list)) {
diff --git a/block/blk-mq.c b/block/blk-mq.c
index 2c850330a32bc..56ab6ac5ec696 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -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;
diff --git a/block/blk-mq.h b/block/blk-mq.h
index aa15d31aaae9b..920bef5e7ce6e 100644
--- a/block/blk-mq.h
+++ b/block/blk-mq.h
@@ -205,6 +205,8 @@ static inline struct sbq_wait_state *bt_wait_ptr(struct sbitmap_queue *bt,
 
 void __blk_mq_tag_busy(struct blk_mq_hw_ctx *);
 void __blk_mq_tag_idle(struct blk_mq_hw_ctx *);
+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);
 
 static inline void blk_mq_tag_busy(struct blk_mq_hw_ctx *hctx)
 {
@@ -291,70 +293,9 @@ static inline int blk_mq_get_rq_budget_token(struct request *rq)
 	return -1;
 }
 
-static inline void __blk_mq_add_active_requests(struct blk_mq_hw_ctx *hctx,
-						int val)
-{
-	if (blk_mq_is_shared_tags(hctx->flags))
-		atomic_add(val, &hctx->queue->nr_active_requests_shared_tags);
-	else
-		atomic_add(val, &hctx->nr_active);
-}
-
-static inline void __blk_mq_inc_active_requests(struct blk_mq_hw_ctx *hctx)
-{
-	__blk_mq_add_active_requests(hctx, 1);
-}
-
-static inline void __blk_mq_sub_active_requests(struct blk_mq_hw_ctx *hctx,
-		int val)
-{
-	if (blk_mq_is_shared_tags(hctx->flags))
-		atomic_sub(val, &hctx->queue->nr_active_requests_shared_tags);
-	else
-		atomic_sub(val, &hctx->nr_active);
-}
-
-static inline void __blk_mq_dec_active_requests(struct blk_mq_hw_ctx *hctx)
-{
-	__blk_mq_sub_active_requests(hctx, 1);
-}
-
-static inline void blk_mq_add_active_requests(struct blk_mq_hw_ctx *hctx,
-					      int val)
-{
-	if (hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED)
-		__blk_mq_add_active_requests(hctx, val);
-}
-
-static inline void blk_mq_inc_active_requests(struct blk_mq_hw_ctx *hctx)
-{
-	if (hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED)
-		__blk_mq_inc_active_requests(hctx);
-}
-
-static inline void blk_mq_sub_active_requests(struct blk_mq_hw_ctx *hctx,
-					      int val)
-{
-	if (hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED)
-		__blk_mq_sub_active_requests(hctx, val);
-}
-
-static inline void blk_mq_dec_active_requests(struct blk_mq_hw_ctx *hctx)
-{
-	if (hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED)
-		__blk_mq_dec_active_requests(hctx);
-}
-
-static inline int __blk_mq_active_requests(struct blk_mq_hw_ctx *hctx)
-{
-	if (blk_mq_is_shared_tags(hctx->flags))
-		return atomic_read(&hctx->queue->nr_active_requests_shared_tags);
-	return atomic_read(&hctx->nr_active);
-}
 static inline void __blk_mq_put_driver_tag(struct blk_mq_hw_ctx *hctx,
 					   struct request *rq)
 {
-	blk_mq_dec_active_requests(hctx);
 	blk_mq_put_tag(hctx->tags, rq->mq_ctx, rq->tag);
 	rq->tag = BLK_MQ_NO_TAG;
 }
@@ -396,45 +337,6 @@ static inline void blk_mq_free_requests(struct list_head *list)
 	}
 }
 
-/*
- * For shared tag users, we track the number of currently active users
- * and attempt to provide a fair share of the tag depth for each of them.
- */
-static inline bool hctx_may_queue(struct blk_mq_hw_ctx *hctx,
-				  struct sbitmap_queue *bt)
-{
-	unsigned int depth, users;
-
-	if (!hctx || !(hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED))
-		return true;
-
-	/*
-	 * Don't try dividing an ant
-	 */
-	if (bt->sb.depth == 1)
-		return true;
-
-	if (blk_mq_is_shared_tags(hctx->flags)) {
-		struct request_queue *q = hctx->queue;
-
-		if (!test_bit(QUEUE_FLAG_HCTX_ACTIVE, &q->queue_flags))
-			return true;
-	} else {
-		if (!test_bit(BLK_MQ_S_TAG_ACTIVE, &hctx->state))
-			return true;
-	}
-
-	users = READ_ONCE(hctx->tags->active_queues);
-	if (!users)
-		return true;
-
-	/*
-	 * Allow at least some tags
-	 */
-	depth = max((bt->sb.depth + users - 1) / users, 4U);
-	return __blk_mq_active_requests(hctx) < depth;
-}
-
 /* run the code block in @dispatch_ops with rcu/srcu read lock held */
 #define __blk_mq_run_dispatch_ops(q, check_sleep, dispatch_ops)	\
 do {								\
diff --git a/include/linux/blk-mq.h b/include/linux/blk-mq.h
index af878597afb8c..22cc09d5ef320 100644
--- a/include/linux/blk-mq.h
+++ b/include/linux/blk-mq.h
@@ -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;
 
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index 9213a5716f95a..86b16bd8b9c17 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -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;
 
-- 
2.52.0