Improve batched tag allocation
Subsystems (2)
Jens Axboe
maintainercover 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
Jens Axboe
maintainerPATCH 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
@@ -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
Jens Axboe
maintainerPATCH 2/2 block: improve batched tag allocation
In reply to Jens AxboeAdd 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
@@ -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
@@ -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
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
@@ -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,
Jens Axboe
maintainerRe: [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_busyagain.
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