Skip to contentSkip to conversation

Improve batched tag allocation

PATCH In review Jens Axboe 2 participants 5 messages Oct 12, 2021 – Oct 14, 2021

Subsystems (2)
lore
Share & tools
lore

Jens Axboe

author maintainer
#0 lore raw

cover Improve batched tag allocation

Hi,

We can do better than implementing batch tag allocs as just repeated calls into sbitmap. Add a sbitmap helper to grab a batch all at once, and use that instead.

Testing with instrumentation added, we get very close to the full batch count. For NVMe, if I run with 32 batch submits, the actual success batch size is ~31 on average. This is close to ideal, as one hw queue will have a 63 tag size and hence we get 31 of 32 tags once every 1/32 alloc. This could be improved, but wasting the extra cycles in sbitmap to skip to the next index for that case doesn't seem worth it.

Signature · 1 line
Jens Axboe
author maintainer
#1 lore raw

PATCH 1/2 sbitmap: add __sbitmap_queue_get_batch()

The block layer tag allocation batching still calls into sbitmap to get each tag, but we can improve on that. Add __sbitmap_queue_get_batch(), which returns a mask of tags all at once, along with an offset for those tags.

An example return would be 0xff, where bits 0..7 are set, with tag_offset == 128. The valid tags in this case would be 128..135.

A batch is specific to an individual sbitmap_map, hence it cannot be larger than that. The requested number of tags is automatically reduced to the max that can be satisfied with a single map.

On failure, 0 is returned. Caller should fall back to single tag allocation at that point/

---
 include/linux/sbitmap.h | 13 +++++++++++
 lib/sbitmap.c           | 51 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 64 insertions(+)
include/linux/sbitmap.h +13 -0
index 2713e689ad66..e30b56023ead 100644
@@ -426,6 +426,19 @@ void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth);
  */
 int __sbitmap_queue_get(struct sbitmap_queue *sbq);
 
+/**
+ * __sbitmap_queue_get_batch() - Try to allocate a batch of free bits
+ * @sbq: Bitmap queue to allocate from.
+ * @nr_tags: number of tags requested
+ * @offset: offset to add to returned bits
+ *
+ * Return: Mask of allocated tags, 0 if none are found. Each tag allocated is
+ * a bit in the mask returned, and the caller must add @offset to the value to
+ * get the absolute tag value.
+ */
+unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
+					unsigned int *offset);
+
 /**
  * __sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct
  * sbitmap_queue, limiting the depth used from each word, with preemption
lib/sbitmap.c +51 -0

57 lines not on this page · raw message

Signature · 1 line
2.33.0
author maintainer
#2 lore raw

PATCH 2/2 block: improve batched tag allocation

In reply to Jens Axboe

Add a blk_mq_get_tags() helper, which uses the new sbitmap API for allocating a batch of tags all at once. This both simplifies the block code for batched allocation, and it is also more efficient than just doing repeated calls into __sbitmap_queue_get().

This reduces the sbitmap overhead in peak runs from ~3% to ~1% and yields a performanc increase from 6.6M IOPS to 6.8M IOPS for a single CPU core.

---
 block/blk-mq-tag.c | 15 ++++++++++++
 block/blk-mq-tag.h |  2 ++
 block/blk-mq.c     | 57 ++++++++++++++++++++++++++++++----------------
 3 files changed, 54 insertions(+), 20 deletions(-)
block/blk-mq-tag.c +15 -0
index 72a2724a4eee..c43b97201161 100644
@@ -86,6 +86,21 @@ static int __blk_mq_get_tag(struct blk_mq_alloc_data *data,
 		return __sbitmap_queue_get(bt);
 }
 
+unsigned long blk_mq_get_tags(struct blk_mq_alloc_data *data, int nr_tags,
+			      unsigned int *offset)
+{
+	struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
+	struct sbitmap_queue *bt = &tags->bitmap_tags;
+	unsigned long ret;
+
+	if (data->shallow_depth ||data->flags & BLK_MQ_REQ_RESERVED ||
+	    data->hctx->flags & BLK_MQ_F_TAG_QUEUE_SHARED)
+		return 0;
+	ret = __sbitmap_queue_get_batch(bt, nr_tags, offset);
+	*offset += tags->nr_reserved_tags;
+	return ret;
+}
+
 unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
 {
 	struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
block/blk-mq-tag.h +2 -0
index d8ce89fa1686..71c2f7d8e9b7 100644
@@ -38,6 +38,8 @@ extern int blk_mq_init_bitmaps(struct sbitmap_queue *bitmap_tags,
 			       int node, int alloc_policy);
 
 extern unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data);
+unsigned long blk_mq_get_tags(struct blk_mq_alloc_data *data, int nr_tags,
+			      unsigned int *offset);
 extern void blk_mq_put_tag(struct blk_mq_tags *tags, struct blk_mq_ctx *ctx,
 			   unsigned int tag);
 extern int blk_mq_tag_update_depth(struct blk_mq_hw_ctx *hctx,
block/blk-mq.c +37 -20

75 lines not on this page · raw message

Signature · 1 line
2.33.0
#3 lore raw

Re: [PATCH 2/2] block: improve batched tag allocation

Review

Quoted 9 lines · Jens Axboe
(quoted diff) +8 -0
+unsigned long blk_mq_get_tags(struct blk_mq_alloc_data *data, int nr_tags,
+			      unsigned int *offset)
+{
+	struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
+	struct sbitmap_queue *bt = &tags->bitmap_tags;
+	unsigned long ret;
+
+	if (data->shallow_depth ||data->flags & BLK_MQ_REQ_RESERVED ||

Missing whitespace after the first ||.

Review

Quoted 9 lines
(quoted diff) +9 -0
+	if (data->nr_tags > 1) {
+		unsigned long tags;
+		unsigned int tag_offset;
+		int i, nr = 0;
+
+		tags = blk_mq_get_tags(data, data->nr_tags, &tag_offset);
+		if (unlikely(!tags)) {
+			data->nr_tags = 1;
+			goto retry;

Unless I'm missing something we don't want the retry case that maps the contexts against and calls blk_mq_tag_busy again.

Review

Quoted 11 lines
(quoted diff) +11 -0
+		}
+		for (i = 0; tags; i++) {
+			if (!(tags & (1UL << i)))
+				continue;
+			tag = tag_offset + i;
+			tags &= ~(1UL << i);
+			rq = blk_mq_rq_ctx_init(data, tag, alloc_time_ns);
+			rq->rq_next = *data->cached_rq;
+			*data->cached_rq = rq;
+		}
+		data->nr_tags -= nr;

And keeping all this batch logic in a helper (even if inlined) would simplify the code a lot. Something like this untested patch:

block/blk-mq.c +54 -46
index 5ac94149fb4be..608b270a7f6b8 100644
@@ -373,6 +373,38 @@ static struct request *blk_mq_rq_ctx_init(struct blk_mq_alloc_data *data,
 	return rq;
 }
 
+static inline struct request *
+__blk_mq_alloc_requests_batch(struct blk_mq_alloc_data *data,
+		u64 alloc_time_ns)
+{
+	unsigned int tag, tag_offset;
+	struct request *rq;
+	unsigned long tags;
+	int i, nr = 0;
+
+	tags = blk_mq_get_tags(data, data->nr_tags, &tag_offset);
+	if (unlikely(!tags))
+		return NULL;
+
+	for (i = 0; tags; i++) {
+		if (!(tags & (1UL << i)))
+			continue;
+		tag = tag_offset + i;
+		tags &= ~(1UL << i);
+		rq = blk_mq_rq_ctx_init(data, tag, alloc_time_ns);
+		rq->rq_next = *data->cached_rq;
+		*data->cached_rq = rq;
+	}
+	data->nr_tags -= nr;
+
+	if (!data->cached_rq)
+		return NULL;
+
+	rq = *data->cached_rq;
+	*data->cached_rq = rq->rq_next;
+	return rq;
+}
+
 static struct request *__blk_mq_alloc_requests(struct blk_mq_alloc_data *data)
 {
 	struct request_queue *q = data->q;
@@ -411,56 +443,32 @@ static struct request *__blk_mq_alloc_requests(struct blk_mq_alloc_data *data)
 	 * Try batched alloc if we want more than 1 tag.
 	 */
 	if (data->nr_tags > 1) {
-		unsigned long tags;
-		unsigned int tag_offset;
-		int i, nr = 0;
-
-		tags = blk_mq_get_tags(data, data->nr_tags, &tag_offset);
-		if (unlikely(!tags)) {
-			data->nr_tags = 1;
-			goto retry;
-		}
-		for (i = 0; tags; i++) {
-			if (!(tags & (1UL << i)))
-				continue;
-			tag = tag_offset + i;
-			tags &= ~(1UL << i);
-			rq = blk_mq_rq_ctx_init(data, tag, alloc_time_ns);
-			rq->rq_next = *data->cached_rq;
-			*data->cached_rq = rq;
-		}
-		data->nr_tags -= nr;
-	} else {
-		/*
-		 * Waiting allocations only fail because of an inactive hctx.
-		 * In that case just retry the hctx assignment and tag
-		 * allocation as CPU hotplug should have migrated us to an
-		 * online CPU by now.
-		 */
-		tag = blk_mq_get_tag(data);
-		if (tag == BLK_MQ_NO_TAG) {
-			if (data->flags & BLK_MQ_REQ_NOWAIT)
-				return NULL;
-			/*
-			 * Give up the CPU and sleep for a random short time to
-			 * ensure that thread using a realtime scheduling class
-			 * are migrated off the CPU, and thus off the hctx that
-			 * is going away.
-			 */
-			msleep(3);
-			goto retry;
-		}
-
-		return blk_mq_rq_ctx_init(data, tag, alloc_time_ns);
+		rq = __blk_mq_alloc_requests_batch(data, alloc_time_ns);
+		if (rq)
+			return rq;
+		data->nr_tags = 1;
 	}
 
-	if (data->cached_rq) {
-		rq = *data->cached_rq;
-		*data->cached_rq = rq->rq_next;
-		return rq;
+	/*
+	 * Waiting allocations only fail because of an inactive hctx.  In that
+	 * case just retry the hctx assignment and tag allocation as CPU hotplug
+	 * should have migrated us to an online CPU by now.
+	 */
+	tag = blk_mq_get_tag(data);
+	if (tag == BLK_MQ_NO_TAG) {
+		if (data->flags & BLK_MQ_REQ_NOWAIT)
+			return NULL;
+		/*
+		 * Give up the CPU and sleep for a random short time to
+		 * ensure that thread using a realtime scheduling class
+		 * are migrated off the CPU, and thus off the hctx that
+		 * is going away.
+		 */
+		msleep(3);
+		goto retry;
 	}
 
-	return NULL;
+	return blk_mq_rq_ctx_init(data, tag, alloc_time_ns);
 }
 
 struct request *blk_mq_alloc_request(struct request_queue *q, unsigned int op,
author maintainer
#4 lore raw

Re: [PATCH 2/2] block: improve batched tag allocation

Quoted 12 lines · Christoph Hellwig

Review

Quoted 9 lines · Jens Axboe
(quoted diff) +8 -0
+unsigned long blk_mq_get_tags(struct blk_mq_alloc_data *data, int nr_tags,
+			      unsigned int *offset)
+{
+	struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
+	struct sbitmap_queue *bt = &tags->bitmap_tags;
+	unsigned long ret;
+
+	if (data->shallow_depth ||data->flags & BLK_MQ_REQ_RESERVED ||

Missing whitespace after the first ||.

Fixed.

Quoted 4 lines
Quoted 4 lines
block/blk-mq.c +4 -0
+	if (data->nr_tags > 1) {
+		unsigned long tags;
+		unsigned int tag_offset;
+		int i, nr = 0;
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+
+		tags = blk_mq_get_tags(data, data->nr_tags, &tag_offset);
+		if (unlikely(!tags)) {
+			data->nr_tags = 1;
+			goto retry;

Unless I'm missing something we don't want the retry case that maps the contexts against and calls blk_mq_tag_busy again.

Yes and no, we could've been preempted and we're now on a different CPU. It's not a huge deal or likely outcome, and it'll only hurt efficiency a bit if that's the case. Can be skipped.

Quoted 6 lines
Quoted 6 lines
block/blk-mq.c +6 -0
+		}
+		for (i = 0; tags; i++) {
+			if (!(tags & (1UL << i)))
+				continue;
+			tag = tag_offset + i;
+			tags &= ~(1UL << i);
Quoted 8 lines

block/blk-mq.c static struct request *blk_mq_rq_ctx_init(struct blk_mq_alloc_data *data, · line 398

Quoted 5 lines
block/blk-mq.c +5 -0
+			rq = blk_mq_rq_ctx_init(data, tag, alloc_time_ns);
+			rq->rq_next = *data->cached_rq;
+			*data->cached_rq = rq;
+		}
+		data->nr_tags -= nr;

And keeping all this batch logic in a helper (even if inlined) would simplify the code a lot. Something like this untested patch:

Yeah, I did go back and forth on that, it's small enough that I didn't care too much about it, but an inline helper is fine too. I can fold this in.

Signature · 1 line
Jens Axboe