linux-kernel - [PATCH 0/3] sbitmap: Fix two issues in the per-bitmap wakeup counter code

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-next>] [day] [month] [year] [list]

Date:   Tue, 15 Nov 2022 17:45:50 -0500
From:   Gabriel Krisman Bertazi <krisman@...e.de>
To:     axboe@...nel.dk
Cc:     mingo@...hat.com, peterz@...radead.org, jack@...e.cz,
        linux-kernel@...r.kernel.org, linux-block@...r.kernel.org,
        liusong@...ux.alibaba.com, chaitanyak@...dia.com,
        Gabriel Krisman Bertazi <krisman@...e.de>
Subject: [PATCH 0/3] sbitmap: Fix two issues in the per-bitmap wakeup counter code

Jan reported two issues in the original thread.

The first is that wake_index was not updated after returning from
sbq_wake_ptr which meant we'd have to empty the wq before moving to the
next one.  Patch 1/3 in this series reorders the code to avoid this
condition, increasing fairness of queue selection and preventing
starvation.  I sent this patch already on the other thread and Jan
reviewed it, but since it is a small one, and a dependency for the
other, I'm resending it a along this series.

The second issue is trickier.  When the selected queue is emptied after
the waitqueue_active check and before wake_up_nr, there is no waiters to
be awaken in that queue, even if other queues might have it.  This
causes us to loose one too many wakeups, and there might not be enough
requests in flight to wake up every queued request.

The proposed fix, is to walk through every queue after doing the atomic
update, such that we ensure any waiters already queued are candidates
for awakening, and that we awake at least 1 waiter in any of the queues.
The patch is a bit more complex than the suggestion since it avoids
partial updates to wake_index, which measurably hurt performance
unnecessarily.

It survived the same tests done on the original patch.

btw, I'm still missing the latency and utilisation reports.  I haven't
forgotten about it, but I didn't have a chance to collect them
yet. Sorry.  I will follow up with them for completeness, even if the
original patch is already queued.

Gabriel Krisman Bertazi (3):
  sbitmap: Advance the queue index before waking up a queue
  wait: Return number of exclusive waiters awaken
  sbitmap: Try each queue to wake up at least one waiter

 include/linux/wait.h |  2 +-
 kernel/sched/wait.c  | 18 +++++++++++-------
 lib/sbitmap.c        | 36 +++++++++++++++++++-----------------
 3 files changed, 31 insertions(+), 25 deletions(-)

-- 
2.35.3