* [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues
@ 2022-03-18 8:25 Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 1/3] sbitmap: record the number of waiters for each waitqueue Yu Kuai
` (3 more replies)
0 siblings, 4 replies; 6+ messages in thread
From: Yu Kuai @ 2022-03-18 8:25 UTC (permalink / raw)
To: axboe, ming.lei, andriy.shevchenko, john.garry, yukuai3, bvanassche
Cc: linux-block, linux-kernel, yi.zhang
During some io test, I found that waitqueues can be extremly unbalanced,
especially when tags are little.
For example:
test cmd: nr_requests is set to 64, and queue_depth is set to 32
[global]
filename=/dev/sdh
ioengine=libaio
direct=1
allow_mounted_write=0
group_reporting
[test]
rw=randwrite
bs=4k
numjobs=512
iodepth=2
With patch 1 applied, I observe the following status:
ws_active=484
ws={
{.wait_cnt=8, .waiters_cnt=117},
{.wait_cnt=8, .waiters_cnt=59},
{.wait_cnt=8, .waiters_cnt=76},
{.wait_cnt=8, .waiters_cnt=0},
{.wait_cnt=5, .waiters_cnt=24},
{.wait_cnt=8, .waiters_cnt=12},
{.wait_cnt=8, .waiters_cnt=21},
{.wait_cnt=8, .waiters_cnt=175},
}
'waiters_cnt' means how many threads are waitng for tags in the 'ws',
and such extremely unbalanced status is very frequent. After reading the
sbitmap code, I found there are two situations that might cause the
problem:
1) blk_mq_get_tag() can call 'bt_wait_ptr()' while the threads might get
tag successfully before going to wait. - patch 2
2) After a 'ws' is woken up, following blk_mq_put_tag() might wake up
the same 'ws' again instead of the next one. - patch 3
I'm not sure if the unbalanced status is really a *problem* and need to
be fixed, this patchset is just to improve fairness and not a thorough
fix. Any comments and suggestions are welcome.
Yu Kuai (3):
sbitmap: record the number of waiters for each waitqueue
blk-mq: call 'bt_wait_ptr()' later in blk_mq_get_tag()
sbitmap: improve the fairness of waitqueues' wake up
block/blk-mq-tag.c | 6 ++---
include/linux/sbitmap.h | 5 ++++
lib/sbitmap.c | 57 ++++++++++++++++++++++-------------------
3 files changed, 39 insertions(+), 29 deletions(-)
--
2.31.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH RFC -next 1/3] sbitmap: record the number of waiters for each waitqueue
2022-03-18 8:25 [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues Yu Kuai
@ 2022-03-18 8:25 ` Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 2/3] blk-mq: call 'bt_wait_ptr()' later in blk_mq_get_tag() Yu Kuai
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: Yu Kuai @ 2022-03-18 8:25 UTC (permalink / raw)
To: axboe, ming.lei, andriy.shevchenko, john.garry, yukuai3, bvanassche
Cc: linux-block, linux-kernel, yi.zhang
This is just a helper to provide a api to see if waitqueues are
balanced.
Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
include/linux/sbitmap.h | 5 +++++
lib/sbitmap.c | 7 +++++--
2 files changed, 10 insertions(+), 2 deletions(-)
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index dffeb8281c2d..18c68e7f5362 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -91,6 +91,11 @@ struct sbq_wait_state {
*/
atomic_t wait_cnt;
+ /**
+ * @waiters_cnt: Number of active waiters
+ */
+ atomic_t waiters_cnt;
+
/**
* @wait: Wait queue.
*/
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 2eb3de18ded3..bde0783e4ace 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -444,6 +444,7 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
init_waitqueue_head(&sbq->ws[i].wait);
atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
+ atomic_set(&sbq->ws[i].waiters_cnt, 0);
}
return 0;
@@ -759,9 +760,9 @@ void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
struct sbq_wait_state *ws = &sbq->ws[i];
- seq_printf(m, "\t{.wait_cnt=%d, .wait=%s},\n",
+ seq_printf(m, "\t{.wait_cnt=%d, .waiters_cnt=%d},\n",
atomic_read(&ws->wait_cnt),
- waitqueue_active(&ws->wait) ? "active" : "inactive");
+ atomic_read(&ws->waiters_cnt));
}
seq_puts(m, "}\n");
@@ -798,6 +799,7 @@ void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq,
{
if (!sbq_wait->sbq) {
atomic_inc(&sbq->ws_active);
+ atomic_inc(&ws->waiters_cnt);
sbq_wait->sbq = sbq;
}
prepare_to_wait_exclusive(&ws->wait, &sbq_wait->wait, state);
@@ -810,6 +812,7 @@ void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws,
finish_wait(&ws->wait, &sbq_wait->wait);
if (sbq_wait->sbq) {
atomic_dec(&sbq->ws_active);
+ atomic_dec(&ws->waiters_cnt);
sbq_wait->sbq = NULL;
}
}
--
2.31.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH RFC -next 2/3] blk-mq: call 'bt_wait_ptr()' later in blk_mq_get_tag()
2022-03-18 8:25 [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 1/3] sbitmap: record the number of waiters for each waitqueue Yu Kuai
@ 2022-03-18 8:25 ` Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 3/3] sbitmap: improve the fairness of waitqueues' wake up Yu Kuai
2022-03-25 7:30 ` [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues yukuai (C)
3 siblings, 0 replies; 6+ messages in thread
From: Yu Kuai @ 2022-03-18 8:25 UTC (permalink / raw)
To: axboe, ming.lei, andriy.shevchenko, john.garry, yukuai3, bvanassche
Cc: linux-block, linux-kernel, yi.zhang
bt_wait_ptr() will increase 'wait_index', however, if blk_mq_get_tag()
get a tag successfully after bt_wait_ptr() is called and before
sbitmap_prepare_to_wait() is called, then the 'ws' is skipped. This
behavior might cause 8 waitqueues to be unbalanced.
Move bt_wait_ptr() later should reduce the problem when the disk is
under high io preesure.
Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
block/blk-mq-tag.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/block/blk-mq-tag.c b/block/blk-mq-tag.c
index 68ac23d0b640..a531351ab190 100644
--- a/block/blk-mq-tag.c
+++ b/block/blk-mq-tag.c
@@ -131,7 +131,7 @@ unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
{
struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
struct sbitmap_queue *bt;
- struct sbq_wait_state *ws;
+ struct sbq_wait_state *ws = NULL;
DEFINE_SBQ_WAIT(wait);
unsigned int tag_offset;
int tag;
@@ -155,7 +155,6 @@ unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
if (data->flags & BLK_MQ_REQ_NOWAIT)
return BLK_MQ_NO_TAG;
- ws = bt_wait_ptr(bt, data->hctx);
do {
struct sbitmap_queue *bt_prev;
@@ -173,7 +172,8 @@ unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
tag = __blk_mq_get_tag(data, bt);
if (tag != BLK_MQ_NO_TAG)
break;
-
+ if (!ws)
+ ws = bt_wait_ptr(bt, data->hctx);
sbitmap_prepare_to_wait(bt, ws, &wait, TASK_UNINTERRUPTIBLE);
tag = __blk_mq_get_tag(data, bt);
--
2.31.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH RFC -next 3/3] sbitmap: improve the fairness of waitqueues' wake up
2022-03-18 8:25 [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 1/3] sbitmap: record the number of waiters for each waitqueue Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 2/3] blk-mq: call 'bt_wait_ptr()' later in blk_mq_get_tag() Yu Kuai
@ 2022-03-18 8:25 ` Yu Kuai
2022-03-25 7:30 ` [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues yukuai (C)
3 siblings, 0 replies; 6+ messages in thread
From: Yu Kuai @ 2022-03-18 8:25 UTC (permalink / raw)
To: axboe, ming.lei, andriy.shevchenko, john.garry, yukuai3, bvanassche
Cc: linux-block, linux-kernel, yi.zhang
Currently, same waitqueue might be woken up continuously:
__sbq_wake_up __sbq_wake_up
sbq_wake_ptr -> assume 0 sbq_wake_ptr -> 0
atomic_dec_return
atomic_dec_return
atomic_cmpxchg -> succeed
atomic_cmpxchg -> failed
return true
__sbq_wake_up
sbq_wake_ptr
atomic_read(&sbq->wake_index) -> 0
sbq_index_atomic_inc -> inc to 1
if (waitqueue_active(&ws->wait))
if (wake_index != atomic_read(&sbq->wake_index))
atomic_set(&sbq->wake_index, wake_index); -> reset from 1 to 0
wake_up_nr -> wake up first waitqueue
// continue to wake up in first waitqueue
To fix the problem, add a detection in sbq_wake_ptr() to avoid choose
the same waitqueue; and refactor __sbq_wake_up() to increase
'wake_index' before updating 'wait_cnt'.
Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
lib/sbitmap.c | 50 ++++++++++++++++++++++++++------------------------
1 file changed, 26 insertions(+), 24 deletions(-)
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index bde0783e4ace..86b18eed83aa 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -583,6 +583,10 @@ static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
return NULL;
wake_index = atomic_read(&sbq->wake_index);
+
+ /* If this waitqueue is about to wake up, switch to the next */
+ if (atomic_read(&sbq->ws[wake_index].wait_cnt) <= 0)
+ wake_index = sbq_index_inc(wake_index);
for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
struct sbq_wait_state *ws = &sbq->ws[wake_index];
@@ -609,33 +613,31 @@ static bool __sbq_wake_up(struct sbitmap_queue *sbq)
return false;
wait_cnt = atomic_dec_return(&ws->wait_cnt);
- if (wait_cnt <= 0) {
- int ret;
-
- wake_batch = READ_ONCE(sbq->wake_batch);
-
- /*
- * Pairs with the memory barrier in sbitmap_queue_resize() to
- * ensure that we see the batch size update before the wait
- * count is reset.
- */
- smp_mb__before_atomic();
+ if (wait_cnt > 0)
+ return false;
+ /*
+ * Concurrent callers should call this function again
+ * to wakeup a new batch on a different 'ws'.
+ */
+ else if (wait_cnt < 0)
+ return true;
- /*
- * For concurrent callers of this, the one that failed the
- * atomic_cmpxhcg() race should call this function again
- * to wakeup a new batch on a different 'ws'.
- */
- ret = atomic_cmpxchg(&ws->wait_cnt, wait_cnt, wake_batch);
- if (ret == wait_cnt) {
- sbq_index_atomic_inc(&sbq->wake_index);
- wake_up_nr(&ws->wait, wake_batch);
- return false;
- }
+ /*
+ * Increase 'wake_index' before updating 'wake_batch', in case that
+ * concurrent callers wake up the same 'ws' again.
+ */
+ sbq_index_atomic_inc(&sbq->wake_index);
+ wake_batch = READ_ONCE(sbq->wake_batch);
- return true;
- }
+ /*
+ * Pairs with the memory barrier in sbitmap_queue_resize() to
+ * ensure that we see the batch size update before the wait
+ * count is reset.
+ */
+ smp_mb__before_atomic();
+ atomic_set(&ws->wait_cnt, wake_batch);
+ wake_up_nr(&ws->wait, wake_batch);
return false;
}
--
2.31.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues
2022-03-18 8:25 [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues Yu Kuai
` (2 preceding siblings ...)
2022-03-18 8:25 ` [PATCH RFC -next 3/3] sbitmap: improve the fairness of waitqueues' wake up Yu Kuai
@ 2022-03-25 7:30 ` yukuai (C)
2022-04-01 3:43 ` yukuai (C)
3 siblings, 1 reply; 6+ messages in thread
From: yukuai (C) @ 2022-03-25 7:30 UTC (permalink / raw)
To: axboe, ming.lei, andriy.shevchenko, john.garry, bvanassche
Cc: linux-block, linux-kernel, yi.zhang
friendly ping ...
在 2022/03/18 16:25, Yu Kuai 写道:
> During some io test, I found that waitqueues can be extremly unbalanced,
> especially when tags are little.
>
> For example:
> test cmd: nr_requests is set to 64, and queue_depth is set to 32
> [global]
> filename=/dev/sdh
> ioengine=libaio
> direct=1
> allow_mounted_write=0
> group_reporting
>
> [test]
> rw=randwrite
> bs=4k
> numjobs=512
> iodepth=2
>
> With patch 1 applied, I observe the following status:
> ws_active=484
> ws={
> {.wait_cnt=8, .waiters_cnt=117},
> {.wait_cnt=8, .waiters_cnt=59},
> {.wait_cnt=8, .waiters_cnt=76},
> {.wait_cnt=8, .waiters_cnt=0},
> {.wait_cnt=5, .waiters_cnt=24},
> {.wait_cnt=8, .waiters_cnt=12},
> {.wait_cnt=8, .waiters_cnt=21},
> {.wait_cnt=8, .waiters_cnt=175},
> }
>
> 'waiters_cnt' means how many threads are waitng for tags in the 'ws',
> and such extremely unbalanced status is very frequent. After reading the
> sbitmap code, I found there are two situations that might cause the
> problem:
>
> 1) blk_mq_get_tag() can call 'bt_wait_ptr()' while the threads might get
> tag successfully before going to wait. - patch 2
>
> 2) After a 'ws' is woken up, following blk_mq_put_tag() might wake up
> the same 'ws' again instead of the next one. - patch 3
>
> I'm not sure if the unbalanced status is really a *problem* and need to
> be fixed, this patchset is just to improve fairness and not a thorough
> fix. Any comments and suggestions are welcome.
>
> Yu Kuai (3):
> sbitmap: record the number of waiters for each waitqueue
> blk-mq: call 'bt_wait_ptr()' later in blk_mq_get_tag()
> sbitmap: improve the fairness of waitqueues' wake up
>
> block/blk-mq-tag.c | 6 ++---
> include/linux/sbitmap.h | 5 ++++
> lib/sbitmap.c | 57 ++++++++++++++++++++++-------------------
> 3 files changed, 39 insertions(+), 29 deletions(-)
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues
2022-03-25 7:30 ` [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues yukuai (C)
@ 2022-04-01 3:43 ` yukuai (C)
0 siblings, 0 replies; 6+ messages in thread
From: yukuai (C) @ 2022-04-01 3:43 UTC (permalink / raw)
To: axboe, ming.lei, andriy.shevchenko, john.garry, bvanassche
Cc: linux-block, linux-kernel, yi.zhang
friendly ping ...
在 2022/03/25 15:30, yukuai (C) 写道:
> friendly ping ...
>
> 在 2022/03/18 16:25, Yu Kuai 写道:
>> During some io test, I found that waitqueues can be extremly unbalanced,
>> especially when tags are little.
>>
>> For example:
>> test cmd: nr_requests is set to 64, and queue_depth is set to 32
>> [global]
>> filename=/dev/sdh
>> ioengine=libaio
>> direct=1
>> allow_mounted_write=0
>> group_reporting
>>
>> [test]
>> rw=randwrite
>> bs=4k
>> numjobs=512
>> iodepth=2
>>
>> With patch 1 applied, I observe the following status:
>> ws_active=484
>> ws={
>> {.wait_cnt=8, .waiters_cnt=117},
>> {.wait_cnt=8, .waiters_cnt=59},
>> {.wait_cnt=8, .waiters_cnt=76},
>> {.wait_cnt=8, .waiters_cnt=0},
>> {.wait_cnt=5, .waiters_cnt=24},
>> {.wait_cnt=8, .waiters_cnt=12},
>> {.wait_cnt=8, .waiters_cnt=21},
>> {.wait_cnt=8, .waiters_cnt=175},
>> }
>>
>> 'waiters_cnt' means how many threads are waitng for tags in the 'ws',
>> and such extremely unbalanced status is very frequent. After reading the
>> sbitmap code, I found there are two situations that might cause the
>> problem:
>>
>> 1) blk_mq_get_tag() can call 'bt_wait_ptr()' while the threads might get
>> tag successfully before going to wait. - patch 2
>>
>> 2) After a 'ws' is woken up, following blk_mq_put_tag() might wake up
>> the same 'ws' again instead of the next one. - patch 3
>>
>> I'm not sure if the unbalanced status is really a *problem* and need to
>> be fixed, this patchset is just to improve fairness and not a thorough
>> fix. Any comments and suggestions are welcome.
>>
>> Yu Kuai (3):
>> sbitmap: record the number of waiters for each waitqueue
>> blk-mq: call 'bt_wait_ptr()' later in blk_mq_get_tag()
>> sbitmap: improve the fairness of waitqueues' wake up
>>
>> block/blk-mq-tag.c | 6 ++---
>> include/linux/sbitmap.h | 5 ++++
>> lib/sbitmap.c | 57 ++++++++++++++++++++++-------------------
>> 3 files changed, 39 insertions(+), 29 deletions(-)
>>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2022-04-01 3:43 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-03-18 8:25 [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 1/3] sbitmap: record the number of waiters for each waitqueue Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 2/3] blk-mq: call 'bt_wait_ptr()' later in blk_mq_get_tag() Yu Kuai
2022-03-18 8:25 ` [PATCH RFC -next 3/3] sbitmap: improve the fairness of waitqueues' wake up Yu Kuai
2022-03-25 7:30 ` [PATCH RFC -next 0/3] improve fairness for sbitmap waitqueues yukuai (C)
2022-04-01 3:43 ` yukuai (C)
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).