blk-mq: abstract tag allocation out into scale_bitmap library
Subsystems (2)
v2 cover blk-mq: abstract tag allocation out into scale_bitmap library
From: Omar Sandoval <[email protected]>
Here's v2 of the patch making blk-mq's scalable bitmaps a generic library, now blown up into 5 patches. v1 is here [1].
Changes since v1:
- Return -EINVAL instead of BUG_ON() if an invalid shift is passed to the initialization functions.
- Rename last_cache to alloc_hint.
- Split the wait queue allocation change into a separate patch. Patch 1 should now be a no-op.
- Add patches 3 and 4 to make the API cleaner by pushing some context from the blk-mq data structures into the common scale_bitmap code.
- Add patch 5 to randomize the allocation hint on initialization like was intended originally for blk-mq.
I ran some fio jobs on top of null-blk and verified that there was no performance impact from patches 1-4. Patch 5 is a slight win, although I couldn't come up with a benchmark where the tag allocation is enough of a bottleneck to see huge benefits. My synthetic test module [2], which does the scale_bitmap operations directly, shows much better results.
This survived a quick run of xfstests and a battery of benchmarks. Applies to 4.8-rc5.
Thanks!
1: http://marc.info/?l=linux-block&m=147251402805405&w=2
2: https://github.com/osandov/osandov-linux/blob/master/modules/scale_bitmap_benchmark/scale_bitmap_benchmark.c
Omar Sandoval (5):
blk-mq: abstract tag allocation out into scale_bitmap library
scale_bitmap: allocate wait queues on a specific node
scale_bitmap: push per-cpu last_tag into scale_bitmap_queue
scale_bitmap: push alloc policy into scale_bitmap_queue
scale_bitmap: randomize initial last_cache values
MAINTAINERS | 1 + block/Kconfig | 1 + block/blk-mq-tag.c | 504 ++++++++++--------------------------------- block/blk-mq-tag.h | 42 ++-- block/blk-mq.c | 115 +++------- block/blk-mq.h | 11 - include/linux/blk-mq.h | 9 +- include/linux/scale_bitmap.h | 390 +++++++++++++++++++++++++++++++++ lib/Kconfig | 3 + lib/Makefile | 2 + lib/scale_bitmap.c | 325 ++++++++++++++++++++++++++++ 11 files changed, 887 insertions(+), 516 deletions(-) create mode 100644 include/linux/scale_bitmap.h create mode 100644 lib/scale_bitmap.c
Signature · 1 line
2.9.3
PATCH v2 1/5 blk-mq: abstract tag allocation out into scale_bitmap library
From: Omar Sandoval <[email protected]>
This is a generally useful data structure, so make it available to anyone else who might want to use it. It's also a nice cleanup separating the allocation logic from the rest of the tag handling logic.
The code is behind a new Kconfig option, CONFIG_SCALE_BITMAP, which is only selected by CONFIG_BLOCK for now.
This should be a complete noop functionality-wise.
--- MAINTAINERS | 1 + block/Kconfig | 1 + block/blk-mq-tag.c | 469 ++++++++++--------------------------------- block/blk-mq-tag.h | 37 +--- block/blk-mq.c | 113 +++-------- block/blk-mq.h | 9 - include/linux/blk-mq.h | 9 +- include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++ lib/Kconfig | 3 + lib/Makefile | 2 + lib/scale_bitmap.c | 305 ++++++++++++++++++++++++++++ 11 files changed, 804 insertions(+), 485 deletions(-) create mode 100644 include/linux/scale_bitmap.h create mode 100644 lib/scale_bitmap.c
MAINTAINERS +1 -0
@@ -2452,6 +2452,7 @@ T: git git://git.kernel.org/pub/scm/linux/kernel/git/axboe/linux-block.git S: Maintained F: block/ F: kernel/trace/blktrace.c +F: lib/scale_bitmap.c BLOCK2MTD DRIVER M: Joern Engel <[email protected]>
block/Kconfig +1 -0
@@ -4,6 +4,7 @@ menuconfig BLOCK bool "Enable the block layer" if EXPERT default y + select SCALE_BITMAP help Provide block layer support for the kernel.
block/blk-mq-tag.c +107 -362
612 lines not on this page · raw message
block/blk-mq-tag.h +10 -27
@@ -3,31 +3,6 @@#include "blk-mq.h" -enum { -BT_WAIT_QUEUES =8 , -BT_WAIT_BATCH =8 , -}; - -struct bt_wait_state { -atomic_t wait_cnt; -wait_queue_head_t wait; -}____cacheline_aligned_in_smp ; - -#define TAG_TO_INDEX (bt, tag) ((tag) >> (bt)->bits_per_word) -#define TAG_TO_BIT (bt, tag) ((tag) & ((1 << (bt)->bits_per_word) - 1)) - -struct blk_mq_bitmap_tags { -unsigned int depth; -unsigned int wake_cnt; -unsigned int bits_per_word; - -unsigned int map_nr; -struct blk_align_bitmap *map; - -atomic_t wake_index; -struct bt_wait_state *bs; -}; -/* * Tag address space map. */
@@ -37,8 +12,8 @@ struct blk_mq_tags {atomic_t active_queues; -struct blk_mq_bitmap_tags bitmap_tags; -struct blk_mq_bitmap_tags breserved_tags; +struct scale_bitmap_queue bitmap_tags; +struct scale_bitmap_queue breserved_tags;struct request **rqs;struct list_head page_list;
@@ -61,6 +36,14 @@ extern void blk_mq_tag_wakeup_all(struct blk_mq_tags *tags, bool);void blk_mq_queue_tag_busy_iter (struct request_queue *q,busy_iter_fn *fn,void *priv); +static inline struct sbq_wait_state *bt_wait_ptr (struct scale_bitmap_queue *bt, +struct blk_mq_hw_ctx *hctx) +{ +if (!hctx) +return &bt->ws[0 ]; +return sbq_wait_ptr (bt, &hctx->wait_index); +} +enum {BLK_MQ_TAG_CACHE_MIN =1 ,BLK_MQ_TAG_CACHE_MAX =64 ,
block/blk-mq.c +33 -80
181 lines not on this page · raw message
block/blk-mq.h +0 -9
@@ -63,15 +63,6 @@ extern void blk_mq_rq_timed_out(struct request *req, bool reserved);void blk_mq_release (struct request_queue *q); -/* -* Basic implementation of sparser bitmap, allowing the user to spread -* the bits over more cachelines. -*/ -struct blk_align_bitmap { -unsigned long word; -unsigned long depth; -}____cacheline_aligned_in_smp ; -static inline struct blk_mq_ctx *__blk_mq_get_ctx (struct request_queue *q,unsigned int cpu) {
include/linux/blk-mq.h +2 -7
@@ -2,6 +2,7 @@#define BLK_MQ_H #include <linux/blkdev.h> +#include <linux/scale_bitmap.h> struct blk_mq_tags ;struct blk_flush_queue ;
@@ -12,12 +13,6 @@ struct blk_mq_cpu_notifier {int (*notify)(void *data,unsigned long action,unsigned int cpu); }; -struct blk_mq_ctxmap { -unsigned int size; -unsigned int bits_per_word; -struct blk_align_bitmap *map; -}; - struct blk_mq_hw_ctx { struct { spinlock_t lock;
@@ -38,7 +33,7 @@ struct blk_mq_hw_ctx {void *driver_data; -struct blk_mq_ctxmap ctx_map; +struct scale_bitmap ctx_map;unsigned int nr_ctx;struct blk_mq_ctx **ctxs;
include/linux/scale_bitmap.h new file +340 -0
340 lines not on this page · raw message
lib/Kconfig +3 -0
@@ -550,4 +550,7 @@ config STACKDEPOT bool select STACKTRACE +config SCALE_BITMAP + bool + endmenu
lib/Makefile +2 -0
@@ -227,3 +227,5 @@ obj-$(CONFIG_UCS2_STRING) += ucs2_string.o obj-$(CONFIG_UBSAN) += ubsan.o UBSAN_SANITIZE_ubsan.o := n + +obj-$(CONFIG_SCALE_BITMAP) += scale_bitmap.o
lib/scale_bitmap.c new file +305 -0
305 lines not on this page · raw message
Signature · 1 line
2.9.3
Quoted 24 lines · Omar Sandoval
From: Omar Sandoval <[email protected]>
This is a generally useful data structure, so make it available to anyone else who might want to use it. It's also a nice cleanup separating the allocation logic from the rest of the tag handling logic.
The code is behind a new
Kconfigoption,CONFIG_SCALE_BITMAP, which is only selected byCONFIG_BLOCKfor now.This should be a complete noop functionality-wise.
Signed-off-by Omar Sandoval <[email protected]>--- MAINTAINERS | 1 + block/Kconfig | 1 + block/blk-mq-tag.c | 469 ++++++++++--------------------------------- block/blk-mq-tag.h | 37 +--- block/blk-mq.c | 113 +++-------- block/blk-mq.h | 9 - include/linux/blk-mq.h | 9 +- include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++ lib/Kconfig | 3 + lib/Makefile | 2 + lib/scale_bitmap.c | 305 ++++++++++++++++++++++++++++
...
Quoted 8 lines
include/linux/scale_bitmap.h new file +2
-0@@ -0,0 +1,340 @@ +/* +* Fast and scalable bitmaps.
...
include/linux/scale_bitmap.h line 47
Quoted 11 lines
include/linux/scale_bitmap.h new file +11
-0+/** +* struct scale_bitmap_word - Word in a &struct scale_bitmap. +*/ +struct scale_bitmap_word { +/** + * struct scale_bitmap - Scalable bitmap. + * + * A &struct scale_bitmap is spread over multiple cachelines to avoid ping-pong. + * This trades off higher memory usage for better scalability. + */ +struct scale_bitmap {
scale_bitmap sounds odd, since 'scale' is also a verb. We also have lib/rhashtable.c:
* Resizable, Scalable, Concurrent Hash Table
everything is 'scalable' nowadays.
May be resizable bitmap would be a better name? 'struct rbitmap'... lib/rbitmap.c ?
Quoted 35 lines · Alexei Starovoitov
Quoted 24 lines · Omar Sandoval
From: Omar Sandoval <[email protected]>
This is a generally useful data structure, so make it available to anyone else who might want to use it. It's also a nice cleanup separating the allocation logic from the rest of the tag handling logic.
The code is behind a new
Kconfigoption,CONFIG_SCALE_BITMAP, which is only selected byCONFIG_BLOCKfor now.This should be a complete noop functionality-wise.
Signed-off-by Omar Sandoval <[email protected]>--- MAINTAINERS | 1 + block/Kconfig | 1 + block/blk-mq-tag.c | 469 ++++++++++--------------------------------- block/blk-mq-tag.h | 37 +--- block/blk-mq.c | 113 +++-------- block/blk-mq.h | 9 - include/linux/blk-mq.h | 9 +- include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++ lib/Kconfig | 3 + lib/Makefile | 2 + lib/scale_bitmap.c | 305 ++++++++++++++++++++++++++++...
Quoted 8 lines
include/linux/scale_bitmap.h new file +2
-0@@ -0,0 +1,340 @@ +/* +* Fast and scalable bitmaps. ...
Quoted 16 lines
include/linux/scale_bitmap.h line 47
Quoted 11 lines
include/linux/scale_bitmap.h new file +11
-0+/** +* struct scale_bitmap_word - Word in a &struct scale_bitmap. +*/ +struct scale_bitmap_word { +/** + * struct scale_bitmap - Scalable bitmap. + * + * A &struct scale_bitmap is spread over multiple cachelines to avoid ping-pong. + * This trades off higher memory usage for better scalability. + */ +struct scale_bitmap {
scale_bitmapsounds odd, since 'scale' is also a verb. We also havelib/rhashtable.c:
* Resizable, Scalable, Concurrent Hash Table
everything is 'scalable' nowadays.
Agreed, I'm not a huge fan of the name.
Quoted 3 lines
May be resizable bitmap would be a better name?
'struct rbitmap'...lib/rbitmap.c?
Hm, the resizing operation isn't very well thought-out right now, it's there because it's okay for the way blk-mq uses it, but it's definitely not the point of the data structure. It's more of a cache-friendly bitmap, or a sparse bitmap. struct sbitmap? struct cbitmap?
Signature · 1 line
Omar
Quoted 55 lines · Omar Sandoval
Quoted 35 lines · Alexei Starovoitov
Quoted 24 lines · Omar Sandoval
From: Omar Sandoval <[email protected]>
This is a generally useful data structure, so make it available to anyone else who might want to use it. It's also a nice cleanup separating the allocation logic from the rest of the tag handling logic.
The code is behind a new
Kconfigoption,CONFIG_SCALE_BITMAP, which is only selected byCONFIG_BLOCKfor now.This should be a complete noop functionality-wise.
Signed-off-by Omar Sandoval <[email protected]>--- MAINTAINERS | 1 + block/Kconfig | 1 + block/blk-mq-tag.c | 469 ++++++++++--------------------------------- block/blk-mq-tag.h | 37 +--- block/blk-mq.c | 113 +++-------- block/blk-mq.h | 9 - include/linux/blk-mq.h | 9 +- include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++ lib/Kconfig | 3 + lib/Makefile | 2 + lib/scale_bitmap.c | 305 ++++++++++++++++++++++++++++...
Quoted 8 lines
include/linux/scale_bitmap.h new file +2
-0@@ -0,0 +1,340 @@ +/* +* Fast and scalable bitmaps. ...
Quoted 16 lines
include/linux/scale_bitmap.h line 47
Quoted 11 lines
include/linux/scale_bitmap.h new file +11
-0+/** +* struct scale_bitmap_word - Word in a &struct scale_bitmap. +*/ +struct scale_bitmap_word { +/** + * struct scale_bitmap - Scalable bitmap. + * + * A &struct scale_bitmap is spread over multiple cachelines to avoid ping-pong. + * This trades off higher memory usage for better scalability. + */ +struct scale_bitmap {
scale_bitmapsounds odd, since 'scale' is also a verb. We also havelib/rhashtable.c:
* Resizable, Scalable, Concurrent Hash Table
everything is 'scalable' nowadays.Agreed, I'm not a huge fan of the name.
Quoted 8 lines
Quoted 3 lines
May be resizable bitmap would be a better name?
'struct rbitmap'...lib/rbitmap.c?Hm, the resizing operation isn't very well thought-out right now, it's there because it's okay for the way blk-mq uses it, but it's definitely not the point of the data structure. It's more of a cache-friendly bitmap, or a sparse bitmap.
struct sbitmap?struct cbitmap?
yeah. naming is hard.
I think the name ideally should indicate how this bitmap is different from array of bits that is already covered by primitives in bitmap.h
Is it because the user can wait on the bit or because it's smp aware? sort of percpu? I think that's the main trick how it achieves good concurrent set/get access, right? struct pcpu_bitmap ?
struct sbitmap is fine too.
Quoted 69 lines · Alexei Starovoitov
Quoted 59 lines · Omar Sandoval
Quoted 47 lines · Alexei Starovoitov
Quoted 26 lines · Omar Sandoval
From: Omar Sandoval <[email protected]>
This is a generally useful data structure, so make it available to anyone else who might want to use it. It's also a nice cleanup separating the allocation logic from the rest of the tag handling logic.
The code is behind a new
Kconfigoption,CONFIG_SCALE_BITMAP, which is only selected byCONFIG_BLOCKfor now.This should be a complete noop functionality-wise.
Signed-off-by Omar Sandoval <[email protected]>--- MAINTAINERS | 1 + block/Kconfig | 1 + block/blk-mq-tag.c | 469 ++++++++++--------------------------------- block/blk-mq-tag.h | 37 +--- block/blk-mq.c | 113 +++-------- block/blk-mq.h | 9 - include/linux/blk-mq.h | 9 +- include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++ lib/Kconfig | 3 + lib/Makefile | 2 + lib/scale_bitmap.c | 305 ++++++++++++++++++++++++++++...
Quoted 9 lines
include/linux/scale_bitmap.h new file +2
-0@@ -0,0 +1,340 @@ +/* +* Fast and scalable bitmaps. ...
Quoted 9 lines
include/linux/scale_bitmap.h new file +8
-0+/** +* struct scale_bitmap_word - Word in a &struct scale_bitmap. +*/ +struct scale_bitmap_word { +/** +* struct scale_bitmap - Scalable bitmap. +* +* A &struct scale_bitmap is spread over multiple cachelines to avoid ping-pong.
Quoted 8 lines
Quoted 3 lines
+ * This trades off higher memory usage for better scalability.
+ */
+structscale_bitmap{
scale_bitmapsounds odd, since 'scale' is also a verb. We also havelib/rhashtable.c:
* Resizable, Scalable, Concurrent Hash Table
everything is 'scalable' nowadays.Agreed, I'm not a huge fan of the name.
Quoted 8 lines
Quoted 3 lines
May be resizable bitmap would be a better name?
'struct rbitmap'...lib/rbitmap.c?Hm, the resizing operation isn't very well thought-out right now, it's there because it's okay for the way blk-mq uses it, but it's definitely not the point of the data structure. It's more of a cache-friendly bitmap, or a sparse bitmap.
struct sbitmap?struct cbitmap?
Quoted 9 lines
yeah. naming is hard.
I think the name ideally should indicate how this bitmap is different from array of bits that is already covered by primitives inbitmap.h
Is it because the user can wait on the bit or because it's smp aware? sort of percpu? I think that's the main trick how it achieves good concurrent set/get access, right? structpcpu_bitmap?
struct sbitmap is fine too.
It's not a true percpu bitmap. Rather it's a sparse bitmap, that provides some nice cache behavior through the nature of the sparseness. The percpu hinting helps with that. sbitmap might work, S for scale and/or sparse.
No name is going to convey what is special about it, but luckily Omar did a great job documenting it while pulling it out of blk-mq-tag. So I'm fine with just calling it sbitmap. I'll be pronouncing it like "spitmap".
Signature · 1 line
Jens Axboe
Quoted 85 lines · Jens Axboe
Quoted 69 lines · Alexei Starovoitov
Quoted 59 lines · Omar Sandoval
Quoted 47 lines · Alexei Starovoitov
Quoted 26 lines · Omar Sandoval
From: Omar Sandoval <[email protected]>
This is a generally useful data structure, so make it available to anyone else who might want to use it. It's also a nice cleanup separating the allocation logic from the rest of the tag handling logic.
The code is behind a new
Kconfigoption,CONFIG_SCALE_BITMAP, which is only selected byCONFIG_BLOCKfor now.This should be a complete noop functionality-wise.
Signed-off-by Omar Sandoval <[email protected]>--- MAINTAINERS | 1 + block/Kconfig | 1 + block/blk-mq-tag.c | 469 ++++++++++--------------------------------- block/blk-mq-tag.h | 37 +--- block/blk-mq.c | 113 +++-------- block/blk-mq.h | 9 - include/linux/blk-mq.h | 9 +- include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++ lib/Kconfig | 3 + lib/Makefile | 2 + lib/scale_bitmap.c | 305 ++++++++++++++++++++++++++++...
Quoted 9 lines
include/linux/scale_bitmap.h new file +2
-0@@ -0,0 +1,340 @@ +/* +* Fast and scalable bitmaps. ...
Quoted 9 lines
include/linux/scale_bitmap.h new file +8
-0+/** +* struct scale_bitmap_word - Word in a &struct scale_bitmap. +*/ +struct scale_bitmap_word { +/** +* struct scale_bitmap - Scalable bitmap. +* +* A &struct scale_bitmap is spread over multiple cachelines to avoid ping-pong.
Quoted 8 lines
Quoted 3 lines
+ * This trades off higher memory usage for better scalability.
+ */
+structscale_bitmap{
scale_bitmapsounds odd, since 'scale' is also a verb. We also havelib/rhashtable.c:
* Resizable, Scalable, Concurrent Hash Table
everything is 'scalable' nowadays.Agreed, I'm not a huge fan of the name.
Quoted 8 lines
Quoted 3 lines
May be resizable bitmap would be a better name?
'struct rbitmap'...lib/rbitmap.c?Hm, the resizing operation isn't very well thought-out right now, it's there because it's okay for the way blk-mq uses it, but it's definitely not the point of the data structure. It's more of a cache-friendly bitmap, or a sparse bitmap.
struct sbitmap?struct cbitmap?Quoted 9 lines
yeah. naming is hard.
I think the name ideally should indicate how this bitmap is different from array of bits that is already covered by primitives inbitmap.h
Is it because the user can wait on the bit or because it's smp aware? sort of percpu? I think that's the main trick how it achieves good concurrent set/get access, right? structpcpu_bitmap?
struct sbitmap is fine too.It's not a true percpu bitmap. Rather it's a sparse bitmap, that provides some nice cache behavior through the nature of the sparseness. The percpu hinting helps with that. sbitmap might work, S for scale and/or sparse.
Quoted 4 lines
No name is going to convey what is special about it, but luckily Omar did a great job documenting it while pulling it out of blk-mq-tag. So I'm fine with just calling it sbitmap. I'll be pronouncing it like "spitmap".
"spitmap" it is :) I'll also do scale_bitmap_queue -> sbitmap_queue unless anyone has a better idea.
Signature · 1 line
Omar
PATCH v2 2/5 scale_bitmap: allocate wait queues on a specific node
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
The original bt_alloc() we converted from was using kzalloc(), not kzalloc_node(), to allocate the wait queues. This was probably an oversight, so fix it for scale_bitmap_queue_init_node().
--- lib/scale_bitmap.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/scale_bitmap.c +1 -1
@@ -212,7 +212,7 @@ int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq,atomic_set (&sbq->wake_index,0 ); - sbq->ws =kzalloc (SBQ_WAIT_QUEUES *sizeof (*sbq->ws), flags); + sbq->ws =kzalloc_node (SBQ_WAIT_QUEUES *sizeof (*sbq->ws), flags, node);if (!sbq->ws) {scale_bitmap_free (&sbq->map);return -ENOMEM ;
Signature · 1 line
2.9.3
PATCH v2 3/5 scale_bitmap: push per-cpu last_tag into scale_bitmap_queue
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
Allocating your own per-cpu allocation hint separately makes for an awkward API. Instead, allocate the per-cpu hint as part of the struct scale_bitmap_queue. There's no point for a struct scale_bitmap_queue without the cache, but you can still use a bare struct scale_bitmap.
--- block/blk-mq-tag.c | 40 ++++++++++++++++------------------- block/blk-mq-tag.h | 3 ++- block/blk-mq.c | 2 +- block/blk-mq.h | 2 -- include/linux/scale_bitmap.h | 50 +++++++++++++++++++++++++++++++++++++++++++- lib/scale_bitmap.c | 16 ++++++++++++-- 6 files changed, 84 insertions(+), 29 deletions(-)
block/blk-mq-tag.c +18 -22
@@ -94,23 +94,21 @@ static inline bool hctx_may_queue(struct blk_mq_hw_ctx *hctx,#define BT_ALLOC_RR (tags) (tags->alloc_policy == BLK_TAG_ALLOC_RR)static int __bt_get (struct blk_mq_hw_ctx *hctx,struct scale_bitmap_queue *bt, -unsigned int *tag_cache,struct blk_mq_tags *tags) +struct blk_mq_tags *tags) {if (!hctx_may_queue (hctx, bt))return -1 ; -return scale_bitmap_get (&bt->map, tag_cache,BT_ALLOC_RR (tags)); +return __scale_bitmap_queue_get (bt,BT_ALLOC_RR (tags)); } -static int bt_get (struct blk_mq_alloc_data *data, -struct scale_bitmap_queue *bt, -struct blk_mq_hw_ctx *hctx, -unsigned int *last_tag,struct blk_mq_tags *tags) +static int bt_get (struct blk_mq_alloc_data *data,struct scale_bitmap_queue *bt, +struct blk_mq_hw_ctx *hctx,struct blk_mq_tags *tags) {struct sbq_wait_state *ws;DEFINE_WAIT (wait);int tag; - tag =__bt_get (hctx, bt, last_tag, tags); + tag =__bt_get (hctx, bt, tags);if (tag !=-1 )return tag;
@@ -121,7 +119,7 @@ static int bt_get(struct blk_mq_alloc_data *data, do { prepare_to_wait(&ws->wait, &wait, TASK_UNINTERRUPTIBLE); - tag = __bt_get(hctx, bt, last_tag, tags); + tag = __bt_get(hctx, bt, tags); if (tag != -1) break;
@@ -138,7 +136,7 @@ static int bt_get(struct blk_mq_alloc_data *data,* Retry tag allocation after running the hardware queue, * as running the queue may also have found completions. */ - tag =__bt_get (hctx, bt, last_tag, tags); + tag =__bt_get (hctx, bt, tags);if (tag !=-1 )break ;
@@ -152,7 +150,6 @@ static int bt_get(struct blk_mq_alloc_data *data,if (data->flags &BLK_MQ_REQ_RESERVED ) { bt = &data->hctx->tags->breserved_tags; }else { - last_tag = &data->ctx->last_tag; hctx = data->hctx; bt = &hctx->tags->bitmap_tags; }
@@ -169,7 +166,7 @@ static unsigned int __blk_mq_get_tag(struct blk_mq_alloc_data *data)int tag; tag =bt_get (data, &data->hctx->tags->bitmap_tags, data->hctx, - &data->ctx->last_tag, data->hctx->tags); + data->hctx->tags);if (tag >=0 )return tag + data->hctx->tags->nr_reserved_tags;
@@ -178,15 +175,15 @@ static unsigned int __blk_mq_get_tag(struct blk_mq_alloc_data *data)static unsigned int __blk_mq_get_reserved_tag (struct blk_mq_alloc_data *data) { -int tag, zero =0 ; +int tag;if (unlikely (!data->hctx->tags->nr_reserved_tags)) {WARN_ON_ONCE (1 );return BLK_MQ_TAG_FAIL ; } - tag =bt_get (data, &data->hctx->tags->breserved_tags,NULL , &zero, - data->hctx->tags); + tag =bt_get (data, &data->hctx->tags->breserved_tags,NULL , + data->hctx->tags);if (tag <0 )return BLK_MQ_TAG_FAIL ;
@@ -200,8 +197,8 @@ unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)return __blk_mq_get_tag (data); } -void blk_mq_put_tag (struct blk_mq_hw_ctx *hctx,unsigned int tag, -unsigned int *last_tag) +void blk_mq_put_tag (struct blk_mq_hw_ctx *hctx,struct blk_mq_ctx *ctx, +unsigned int tag) {struct blk_mq_tags *tags = hctx->tags;
@@ -209,12 +206,12 @@ void blk_mq_put_tag(struct blk_mq_hw_ctx *hctx, unsigned int tag,const int real_tag = tag - tags->nr_reserved_tags;BUG_ON (real_tag >= tags->nr_tags); -scale_bitmap_queue_clear (&tags->bitmap_tags, real_tag); -if (likely (tags->alloc_policy ==BLK_TAG_ALLOC_FIFO )) - *last_tag = real_tag; +scale_bitmap_queue_clear (&tags->bitmap_tags, real_tag, +BT_ALLOC_RR (tags), ctx->cpu); }else {BUG_ON (tag >= tags->nr_reserved_tags); -scale_bitmap_queue_clear (&tags->breserved_tags, tag); +scale_bitmap_queue_clear (&tags->breserved_tags, tag, +BT_ALLOC_RR (tags), ctx->cpu); } }
@@ -369,8 +366,7 @@ static unsigned int bt_unused_tags(const struct scale_bitmap_queue *bt)return bt->map.depth -scale_bitmap_weight (&bt->map); } -static int bt_alloc (struct scale_bitmap_queue *bt,unsigned int depth, -int node) +static int bt_alloc (struct scale_bitmap_queue *bt,unsigned int depth,int node) {return scale_bitmap_queue_init_node (bt, depth,-1 ,GFP_KERNEL , node); }
block/blk-mq-tag.h +2 -1
@@ -27,7 +27,8 @@ extern struct blk_mq_tags *blk_mq_init_tags(unsigned int nr_tags, unsigned int rextern void blk_mq_free_tags (struct blk_mq_tags *tags);extern unsigned int blk_mq_get_tag (struct blk_mq_alloc_data *data); -extern void blk_mq_put_tag (struct blk_mq_hw_ctx *hctx,unsigned int tag,unsigned int *last_tag); +extern void blk_mq_put_tag (struct blk_mq_hw_ctx *hctx,struct blk_mq_ctx *ctx, +unsigned int tag);extern bool blk_mq_has_free_tags (struct blk_mq_tags *tags);extern ssize_t blk_mq_tag_sysfs_show (struct blk_mq_tags *tags,char *page);extern void blk_mq_tag_init_last_tag (struct blk_mq_tags *tags,unsigned int *last_tag);
block/blk-mq.c +1 -1
@@ -302,7 +302,7 @@ static void __blk_mq_free_request(struct blk_mq_hw_ctx *hctx, rq->cmd_flags =0 ;clear_bit (REQ_ATOM_STARTED , &rq->atomic_flags); -blk_mq_put_tag (hctx, tag, &ctx->last_tag); +blk_mq_put_tag (hctx, ctx, tag);blk_queue_exit (q); }
block/blk-mq.h +0 -2
@@ -12,8 +12,6 @@ struct blk_mq_ctx {unsigned int cpu;unsigned int index_hw; -unsigned int last_tag____cacheline_aligned_in_smp ; -/* incremented at dispatch time */ unsigned long rq_dispatched[2 ];unsigned long rq_merged;
include/linux/scale_bitmap.h +49 -1
73 lines not on this page · raw message
lib/scale_bitmap.c +14 -2
@@ -206,6 +206,12 @@ int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq,if (ret)return ret; + sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags); +if (!sbq->alloc_hint) { +scale_bitmap_free (&sbq->map); +return -ENOMEM ; + } + sbq->wake_batch =SBQ_WAKE_BATCH ;if (sbq->wake_batch > depth /SBQ_WAIT_QUEUES ) sbq->wake_batch =max (1U , depth /SBQ_WAIT_QUEUES );
@@ -214,6 +220,7 @@ int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq, sbq->ws =kzalloc_node (SBQ_WAIT_QUEUES *sizeof (*sbq->ws), flags, node);if (!sbq->ws) { +free_percpu (sbq->alloc_hint);scale_bitmap_free (&sbq->map);return -ENOMEM ; }
@@ -259,7 +266,8 @@ static struct sbq_wait_state *sbq_wake_ptr(struct scale_bitmap_queue *sbq)return NULL ; } -void scale_bitmap_queue_clear (struct scale_bitmap_queue *sbq,unsigned int nr) +void scale_bitmap_queue_clear (struct scale_bitmap_queue *sbq,unsigned int nr, +bool round_robin,unsigned int cpu) {struct sbq_wait_state *ws;int wait_cnt;
@@ -271,7 +279,7 @@ void scale_bitmap_queue_clear(struct scale_bitmap_queue *sbq, unsigned int nr) ws =sbq_wake_ptr (sbq);if (!ws) -return ; + goto update_cache; wait_cnt =atomic_dec_return (&ws->wait_cnt);if (unlikely (wait_cnt <0 ))
@@ -281,6 +289,10 @@ void scale_bitmap_queue_clear(struct scale_bitmap_queue *sbq, unsigned int nr)sbq_index_atomic_inc (&sbq->wake_index);wake_up (&ws->wait); } + +update_cache: +if (likely (!round_robin)) + *per_cpu_ptr (sbq->alloc_hint, cpu) = nr; }EXPORT_SYMBOL_GPL (scale_bitmap_queue_clear);
Signature · 1 line
2.9.3
PATCH v2 4/5 scale_bitmap: push alloc policy into scale_bitmap_queue
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
Again, there's no point in passing this in every time. Make it part of struct scale_bitmap_queue and clean up the API.
--- block/blk-mq-tag.c | 33 +++++++++++++++------------------ block/blk-mq-tag.h | 1 - include/linux/scale_bitmap.h | 24 +++++++++++++----------- lib/scale_bitmap.c | 10 ++++++---- 4 files changed, 34 insertions(+), 34 deletions(-)
block/blk-mq-tag.c +15 -18
@@ -91,14 +91,11 @@ static inline bool hctx_may_queue(struct blk_mq_hw_ctx *hctx,return atomic_read (&hctx->nr_active) < depth; } -#define BT_ALLOC_RR (tags) (tags->alloc_policy == BLK_TAG_ALLOC_RR) - -static int __bt_get (struct blk_mq_hw_ctx *hctx,struct scale_bitmap_queue *bt, -struct blk_mq_tags *tags) +static int __bt_get (struct blk_mq_hw_ctx *hctx,struct scale_bitmap_queue *bt) {if (!hctx_may_queue (hctx, bt))return -1 ; -return __scale_bitmap_queue_get (bt,BT_ALLOC_RR (tags)); +return __scale_bitmap_queue_get (bt); } static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt,
@@ -108,7 +105,7 @@ static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt,DEFINE_WAIT (wait);int tag; - tag =__bt_get (hctx, bt, tags); + tag =__bt_get (hctx, bt);if (tag !=-1 )return tag;
@@ -119,7 +116,7 @@ static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt, do { prepare_to_wait(&ws->wait, &wait, TASK_UNINTERRUPTIBLE); - tag = __bt_get(hctx, bt, tags); + tag = __bt_get(hctx, bt); if (tag != -1) break;
@@ -136,7 +133,7 @@ static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt,* Retry tag allocation after running the hardware queue, * as running the queue may also have found completions. */ - tag =__bt_get (hctx, bt, tags); + tag =__bt_get (hctx, bt);if (tag !=-1 )break ;
@@ -206,12 +203,10 @@ void blk_mq_put_tag(struct blk_mq_hw_ctx *hctx, struct blk_mq_ctx *ctx,const int real_tag = tag - tags->nr_reserved_tags;BUG_ON (real_tag >= tags->nr_tags); -scale_bitmap_queue_clear (&tags->bitmap_tags, real_tag, -BT_ALLOC_RR (tags), ctx->cpu); +scale_bitmap_queue_clear (&tags->bitmap_tags, real_tag, ctx->cpu); }else {BUG_ON (tag >= tags->nr_reserved_tags); -scale_bitmap_queue_clear (&tags->breserved_tags, tag, -BT_ALLOC_RR (tags), ctx->cpu); +scale_bitmap_queue_clear (&tags->breserved_tags, tag, ctx->cpu); } }
@@ -366,21 +361,23 @@ static unsigned int bt_unused_tags(const struct scale_bitmap_queue *bt)return bt->map.depth -scale_bitmap_weight (&bt->map); } -static int bt_alloc (struct scale_bitmap_queue *bt,unsigned int depth,int node) +static int bt_alloc (struct scale_bitmap_queue *bt,unsigned int depth, +bool round_robin,int node) { -return scale_bitmap_queue_init_node (bt, depth,-1 ,GFP_KERNEL , node); +return scale_bitmap_queue_init_node (bt, depth,-1 , round_robin, +GFP_KERNEL , node); }static struct blk_mq_tags *blk_mq_init_bitmap_tags (struct blk_mq_tags *tags,int node,int alloc_policy) {unsigned int depth = tags->nr_tags - tags->nr_reserved_tags; +bool round_robin = alloc_policy ==BLK_TAG_ALLOC_RR ; - tags->alloc_policy = alloc_policy; - -if (bt_alloc (&tags->bitmap_tags, depth, node)) +if (bt_alloc (&tags->bitmap_tags, depth, round_robin, node)) goto free_tags; -if (bt_alloc (&tags->breserved_tags, tags->nr_reserved_tags, node)) +if (bt_alloc (&tags->breserved_tags, tags->nr_reserved_tags, round_robin, + node)) goto free_bitmap_tags;return tags;
block/blk-mq-tag.h +0 -1
@@ -18,7 +18,6 @@ struct blk_mq_tags {struct request **rqs;struct list_head page_list; -int alloc_policy;cpumask_var_t cpumask; };
include/linux/scale_bitmap.h +13 -11
@@ -122,6 +122,11 @@ struct scale_bitmap_queue {* @ws: Wait queues. */ struct sbq_wait_state *ws; + +/** +* @round_robin: Allocate bits in strict round-robin order. +*/ +bool round_robin; };/**
@@ -270,14 +275,15 @@ unsigned int scale_bitmap_weight(const struct scale_bitmap *bitmap);* @sbq: Bitmap queue to initialize. * @depth: See scale_bitmap_init_node(). * @shift: See scale_bitmap_init_node(). +* @round_robin: See scale_bitmap_get(). * @flags: Allocation flags. * @node: Memory node to allocate on. * * Return: Zero on success or negative errno on failure. */ int scale_bitmap_queue_init_node (struct scale_bitmap_queue *sbq, -unsigned int depth,int shift,gfp_t flags, -int node); +unsigned int depth,int shift, +bool round_robin,gfp_t flags,int node);/** * scale_bitmap_queue_free() - Free memory used by a &struct scale_bitmap_queue.
@@ -307,34 +313,31 @@ void scale_bitmap_queue_resize(struct scale_bitmap_queue *sbq,* __scale_bitmap_queue_get() - Try to allocate a free bit from a &struct * scale_bitmap_queue with preemption already disabled. * @sbq: Bitmap queue to allocate from. -* @round_robin: See scale_bitmap_get(). * * Return: Non-negative allocated bit number if successful, -1 otherwise. */ -static inline int __scale_bitmap_queue_get (struct scale_bitmap_queue *sbq, -bool round_robin) +static inline int __scale_bitmap_queue_get (struct scale_bitmap_queue *sbq) {return scale_bitmap_get (&sbq->map,this_cpu_ptr (sbq->alloc_hint), - round_robin); + sbq->round_robin); }/** * scale_bitmap_queue_get() - Try to allocate a free bit from a &struct * scale_bitmap_queue. * @sbq: Bitmap queue to allocate from. -* @round_robin: See scale_bitmap_get(). * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to * scale_bitmap_queue_clear()). * * Return: Non-negative allocated bit number if successful, -1 otherwise. */ static inline int scale_bitmap_queue_get (struct scale_bitmap_queue *sbq, -bool round_robin,unsigned int *cpu) +unsigned int *cpu) {int ret; *cpu =get_cpu (); - ret =__scale_bitmap_queue_get (sbq, round_robin); + ret =__scale_bitmap_queue_get (sbq);put_cpu ();return ret; }
@@ -344,11 +347,10 @@ static inline int scale_bitmap_queue_get(struct scale_bitmap_queue *sbq,* &struct scale_bitmap_queue. * @sbq: Bitmap to free from. * @nr: Bit number to free. -* @round_robin: See scale_bitmap_get(). * @cpu: CPU the bit was allocated on. */ void scale_bitmap_queue_clear (struct scale_bitmap_queue *sbq,unsigned int nr, -bool round_robin,unsigned int cpu); +unsigned int cpu);static inline int sbq_index_inc (int index) {
lib/scale_bitmap.c +6 -4
@@ -196,8 +196,8 @@ unsigned int scale_bitmap_weight(const struct scale_bitmap *bitmap)EXPORT_SYMBOL_GPL (scale_bitmap_weight);int scale_bitmap_queue_init_node (struct scale_bitmap_queue *sbq, -unsigned int depth,int shift,gfp_t flags, -int node) +unsigned int depth,int shift, +bool round_robin,gfp_t flags,int node) {int ret;int i;
@@ -229,6 +229,8 @@ int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq,init_waitqueue_head (&sbq->ws[i].wait);atomic_set (&sbq->ws[i].wait_cnt, sbq->wake_batch); } + + sbq->round_robin = round_robin;return 0 ; }EXPORT_SYMBOL_GPL (scale_bitmap_queue_init_node);
@@ -267,7 +269,7 @@ static struct sbq_wait_state *sbq_wake_ptr(struct scale_bitmap_queue *sbq) }void scale_bitmap_queue_clear (struct scale_bitmap_queue *sbq,unsigned int nr, -bool round_robin,unsigned int cpu) +unsigned int cpu) {struct sbq_wait_state *ws;int wait_cnt;
@@ -291,7 +293,7 @@ void scale_bitmap_queue_clear(struct scale_bitmap_queue *sbq, unsigned int nr, } update_cache: -if (likely (!round_robin)) +if (likely (!sbq->round_robin)) *per_cpu_ptr (sbq->alloc_hint, cpu) = nr; }EXPORT_SYMBOL_GPL (scale_bitmap_queue_clear);
Signature · 1 line
2.9.3
PATCH v2 5/5 scale_bitmap: randomize initial last_cache values
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
In order to get good cache behavior from a scale_bitmap, we want each CPU to stick to its own cacheline(s) as much as possible. This might happen naturally as the bitmap gets filled up and the last_cache values spread out, but we really want this behavior from the start. blk-mq apparently intended to do this, but the code to do this was never wired up. Get rid of the dead code and make it part of the scale_bitmap library.
--- block/blk-mq-tag.c | 8 -------- block/blk-mq-tag.h | 1 - lib/scale_bitmap.c | 6 ++++++ 3 files changed, 6 insertions(+), 9 deletions(-)
block/blk-mq-tag.c +0 -8
@@ -7,7 +7,6 @@*/ #include <linux/kernel.h> #include <linux/module.h> -#include <linux/random.h> #include <linux/blk-mq.h> #include "blk.h"
@@ -422,13 +421,6 @@ void blk_mq_free_tags(struct blk_mq_tags *tags)kfree (tags); } -void blk_mq_tag_init_last_tag (struct blk_mq_tags *tags,unsigned int *tag) -{ -unsigned int depth = tags->nr_tags - tags->nr_reserved_tags; - - *tag =prandom_u32 () % depth; -} -int blk_mq_tag_update_depth (struct blk_mq_tags *tags,unsigned int tdepth) { tdepth -= tags->nr_reserved_tags;
block/blk-mq-tag.h +0 -1
@@ -30,7 +30,6 @@ extern void blk_mq_put_tag(struct blk_mq_hw_ctx *hctx, struct blk_mq_ctx *ctx, unsigned int tag);extern bool blk_mq_has_free_tags (struct blk_mq_tags *tags);extern ssize_t blk_mq_tag_sysfs_show (struct blk_mq_tags *tags,char *page); -extern void blk_mq_tag_init_last_tag (struct blk_mq_tags *tags,unsigned int *last_tag);extern int blk_mq_tag_update_depth (struct blk_mq_tags *tags,unsigned int depth);extern void blk_mq_tag_wakeup_all (struct blk_mq_tags *tags,bool ); void blk_mq_queue_tag_busy_iter(struct request_queue *q, busy_iter_fn *fn,
lib/scale_bitmap.c +6 -0
@@ -15,6 +15,7 @@* along with this program. If not, see <https://www.gnu.org/licenses/>. */ +#include <linux/random.h> #include <linux/scale_bitmap.h> int scale_bitmap_init_node(struct scale_bitmap *bitmap, unsigned int depth,
@@ -212,6 +213,11 @@ int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq,return -ENOMEM ; } +if (depth && !round_robin) { +for_each_possible_cpu (i) + *per_cpu_ptr (sbq->alloc_hint, i) =prandom_u32 () % depth; + } + sbq->wake_batch =SBQ_WAKE_BATCH ;if (sbq->wake_batch > depth /SBQ_WAIT_QUEUES ) sbq->wake_batch =max (1U , depth /SBQ_WAIT_QUEUES );
Signature · 1 line
2.9.3