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

[Keith Busch <kbusch@meta.com>]

From: Keith Busch <kbusch@kernel.org>

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.

Signed-off-by: Keith Busch <kbusch@kernel.org>
---
 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(-)

diff --git a/block/blk-core.c b/block/blk-core.c
index 7e719b90d8a66..85f7ad22f6461 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;
 
-	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);
diff --git a/block/blk-mq-tag.c b/block/blk-mq-tag.c
index aa7dbceb60dcd..d92496378a834 100644
--- a/block/blk-mq-tag.c
+++ b/block/blk-mq-tag.c
@@ -34,15 +34,77 @@ static void blk_mq_update_wake_batch(struct blk_mq_tags *tags,
 }
 
 /*
- * 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).
+ * Where this queue's cached fairness window lives. HCTX_SHARED tag sets divide
+ * one global bitmap among request_queues (window per queue); QUEUE_SHARED tag
+ * sets divide each per-hw-queue bitmap among the hctxs sharing it (window per
+ * hctx). The window packs into a u64 only because every bound fits in a u16.
  */
-static int *blk_mq_tag_win_slot(struct blk_mq_hw_ctx *hctx)
+static_assert(BLK_MQ_MAX_DEPTH <= U16_MAX);
+
+static struct blk_mq_tag_win *blk_mq_tag_win_ptr(struct blk_mq_hw_ctx *hctx)
 {
 	return blk_mq_is_shared_tags(hctx->flags) ?
-		&hctx->queue->tag_win_slot : &hctx->tag_win_slot;
+		&hctx->queue->tag_win : &hctx->tag_win;
+}
+
+static void __blk_mq_rebalance(struct blk_mq_tag_set *set,
+			       struct blk_mq_tags *tags, bool shared,
+			       unsigned int idx)
+{
+	unsigned int depth = tags->bitmap_tags.sb.depth;
+	unsigned int users, priv, smin, pos;
+	struct request_queue *q;
+
+	users = READ_ONCE(tags->active_queues);
+	priv = smin = pos = 0;
+	if (users > 1 && depth > 1) {
+		unsigned int fair = depth / users;
+		unsigned int pct = 100 - min(set->shared_pct, 100u);
+
+		priv = fair * pct / 100;
+		smin = min(users * priv, depth);
+	}
+
+	rcu_read_lock();
+	list_for_each_entry_rcu(q, &set->tag_list, tag_set_list) {
+		struct blk_mq_tag_win *w, new_w;
+		bool active;
+
+		if (shared) {
+			w = &q->tag_win;
+			active = test_bit(QUEUE_FLAG_HCTX_ACTIVE, &q->queue_flags);
+		} else {
+			struct blk_mq_hw_ctx *hctx = queue_hctx(q, idx);
+
+			if (!hctx)
+				continue;
+			w = &hctx->tag_win;
+			active = test_bit(BLK_MQ_S_TAG_ACTIVE, &hctx->state);
+		}
+
+		if (!priv || !active) {
+			new_w = (struct blk_mq_tag_win) {
+				.shared_max = U16_MAX
+			};
+		} else {
+			new_w = (struct blk_mq_tag_win) {
+				.priv_min = min(pos * priv, depth),
+				.priv_max = min(pos * priv + priv, depth),
+				.shared_min = smin,
+				.shared_max = depth,
+			};
+			pos++;
+		}
+		WRITE_ONCE(w->v, new_w.v);
+	}
+	rcu_read_unlock();
+}
+
+/* Rebalance the pool @hctx draws from after its active set changed. */
+static void blk_mq_rebalance(struct blk_mq_hw_ctx *hctx)
+{
+	__blk_mq_rebalance(hctx->queue->tag_set, hctx->tags,
+			   blk_mq_is_shared_tags(hctx->flags), hctx->queue_num);
 }
 
 /*
@@ -77,16 +139,9 @@ 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);
+
+	blk_mq_rebalance(hctx);
 }
 
 /*
@@ -123,17 +178,9 @@ 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_rebalance(hctx);
 	blk_mq_tag_wakeup_all(tags, false);
 }
 
@@ -144,81 +191,22 @@ 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,
-				     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 fair, priv, pct, pos;
-
-	if (users <= 1 || depth <= 1)
-		return false;
-
-	fair = depth / users;
-	if (!fair)
-		return false;
-
-	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 = 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;
-}
-
-static int __blk_mq_get_tag_window(struct sbitmap_queue *bt,
-				   struct blk_mq_tag_win *w)
+int blk_mq_get_tag_window(struct blk_mq_hw_ctx *hctx, struct sbitmap_queue *bt)
 {
-	if (w->priv_max > w->priv_min) {
-		int tag = sbitmap_queue_get_range(bt, w->priv_min, w->priv_max);
+	struct blk_mq_tag_win w = { .v = READ_ONCE(blk_mq_tag_win_ptr(hctx)->v) };
+	int tag;
 
+	if (w.priv_max > w.priv_min) {
+		tag = sbitmap_queue_get_range(bt, w.priv_min, w.priv_max);
 		if (tag >= 0)
 			return tag;
 	}
 
-	if (w->shared_max > w->shared_min)
-		return sbitmap_queue_get_range(bt, w->shared_min, w->shared_max);
-
+	if (w.shared_max > w.shared_min)
+		return sbitmap_queue_get_range(bt, w.shared_min, w.shared_max);
 	return BLK_MQ_NO_TAG;
 }
 
-int blk_mq_get_tag_window(struct blk_mq_hw_ctx *hctx, struct sbitmap_queue *bt)
-{
-	struct blk_mq_tag_win w;
-
-	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,
 			    struct sbitmap_queue *bt)
 {
@@ -726,14 +714,8 @@ 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_slots;
+		goto out_free_tags;
 	if (bt_alloc(&tags->breserved_tags, reserved_tags, round_robin, node))
 		goto out_free_bitmap_tags;
 
@@ -741,8 +723,6 @@ 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;
@@ -771,7 +751,6 @@ 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)) {
@@ -786,6 +765,7 @@ void blk_mq_tag_resize_shared_tags(struct blk_mq_tag_set *set, unsigned int size
 {
 	struct blk_mq_tags *tags = set->shared_tags;
 
+	__blk_mq_rebalance(set, tags, true, 0);
 	sbitmap_queue_resize(&tags->bitmap_tags, size - set->reserved_tags);
 }
 
diff --git a/block/blk-mq.c b/block/blk-mq.c
index cc56baee74fe8..ef8699735aa95 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -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;
diff --git a/include/linux/blk-mq.h b/include/linux/blk-mq.h
index 59847ac7d319c..0b1e1697e1736 100644
--- a/include/linux/blk-mq.h
+++ b/include/linux/blk-mq.h
@@ -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;
 
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index 86b16bd8b9c17..7b55ce6a3fd2b 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -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;
 
-- 
2.52.0