linux-kernel - [PATCH] sbitmap: Advance the queue index before waking up the queue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 14 Nov 2022 09:20:57 -0500
From:   Gabriel Krisman Bertazi <krisman@...e.de>
To:     Jan Kara <jack@...e.cz>
Cc:     axboe@...nel.dk, linux-kernel@...r.kernel.org,
        linux-block@...r.kernel.org, Hugh Dickins <hughd@...gle.com>,
        Keith Busch <kbusch@...nel.org>,
        Liu Song <liusong@...ux.alibaba.com>
Subject: [PATCH] sbitmap: Advance the queue index before waking up the queue

Jan Kara <jack@...e.cz> writes:

> Gabriel, when looking through this patch, I've noticed we can loose wakeups
> after your latest simplifications. See below for details:
>
> On Sat 05-11-22 19:10:55, Gabriel Krisman Bertazi wrote:
>> @@ -587,7 +571,7 @@ static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
>>  	for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
>>  		struct sbq_wait_state *ws = &sbq->ws[wake_index];
>>  
>> -		if (waitqueue_active(&ws->wait) && atomic_read(&ws->wait_cnt)) {
>> +		if (waitqueue_active(&ws->wait)) {
>>  			if (wake_index != atomic_read(&sbq->wake_index))
>>  				atomic_set(&sbq->wake_index, wake_index);
>>  			return ws;
>
> Neither sbq_wake_ptr() nor sbitmap_queue_wake_up() now increment the
> wake_index after performing the wakeup. Thus we would effectively keep
> waking tasks from a single waitqueue until it becomes empty and only then
> go for the next waitqueue. This creates unnecessary unfairness in task
> wakeups and even possible starvation issues. So I think we need to advance
> wake_index somewhere. Perhaps here before returning waitqueue.

right. This is indeed a problem.  what do you think of the patch below?

> Now this may be also problematic - when we were checking the number of woken
> waiters in the older version of the patch (for others: internal version of
> the patch) this was fine but now it may happen that the 'ws' we have
> selected has no waiters anymore. And in that case we need to find another
> waitqueue because otherwise we'd be loosing too many wakeups and we could
> deadlock. So I think this rather needs to be something like:
>
> 	do {
> 		if (atomic_read(&sbq->completion_cnt) - wakeups < wake_batch)
> 			return;
> 	} while (!atomic_try_cmpxchg(&sbq->wakeup_cnt,
> 				     &wakeups, wakeups + wake_batch));
>
> 	do {
> 		ws = sbq_wake_ptr(sbq);
> 		if (!ws)
> 			return;
> 	} while (!wake_up_nr(&ws->wait, wake_batch));
>
> with our original version of wake_up_nr() returning number of woken
> waiters. What do you think?

I agree, and it wouldn't happen with the wake_up_nr patch we had before.
I will revive it quickly and follow up.  But, in this case, I want to be
cautious with benchmarking, so I will follow up still today, but as soon
as the new round of tests complete.

thanks,

-- >8 --
Subject: [PATCH] sbitmap: Advance the queue index before waking up the queue

When a queue is awaken, the wake_index written by sbq_wake_ptr currently
keeps pointing to the same queue.  On the next wake up, it will thus
retry the same queue, which is unfair to other queues, and can lead to
starvation.  This patch, moves the index update to happen before the
queue is returned, such that it will now try a different queue first on
the next wake up, improving fairness.

Reported-by: Jan Kara <jack@...e.cz>
Signed-off-by: Gabriel Krisman Bertazi <krisman@...e.de>
---
 lib/sbitmap.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index eca462cba398..bea7984f7987 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -571,13 +571,19 @@ static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
 	for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
 		struct sbq_wait_state *ws = &sbq->ws[wake_index];
 
+		/*
+		 * Advance the index before checking the current queue.
+		 * It improves fairness, by ensuring the queue doesn't
+		 * need to be fully emptied before trying to wake up
+		 * from the next one.
+		 */
+		wake_index = sbq_index_inc(wake_index);
+
 		if (waitqueue_active(&ws->wait)) {
 			if (wake_index != atomic_read(&sbq->wake_index))
 				atomic_set(&sbq->wake_index, wake_index);
 			return ws;
 		}
-
-		wake_index = sbq_index_inc(wake_index);
 	}
 
 	return NULL;
-- 
2.35.3