linux-kernel - Re: [RFC 0/2] srcu: Remove pre-flip memory barrier

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]

Message-ID: <CAEXW_YR194jzDQM7YZr0H8pDjhxUdymFbaheOGsMXq8judgGEQ@mail.gmail.com>
Date:   Tue, 20 Dec 2022 18:05:46 +0000
From:   Joel Fernandes <joel@...lfernandes.org>
To:     Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc:     linux-kernel@...r.kernel.org,
        Josh Triplett <josh@...htriplett.org>,
        Lai Jiangshan <jiangshanlai@...il.com>,
        "Paul E. McKenney" <paulmck@...nel.org>, rcu@...r.kernel.org,
        Steven Rostedt <rostedt@...dmis.org>
Subject: Re: [RFC 0/2] srcu: Remove pre-flip memory barrier

Hi Mathieu,

On Tue, Dec 20, 2022 at 5:00 PM Mathieu Desnoyers
<mathieu.desnoyers@...icios.com> wrote:
>
> On 2022-12-19 20:04, Joel Fernandes wrote:
> > On Mon, Dec 19, 2022 at 7:55 PM Joel Fernandes <joel@...lfernandes.org> wrote:
[...]
> >>> On a 64-bit system, where 64-bit counters are used, AFAIU this need to
> >>> be exactly 2^64 read-side critical sections.
> >>
> >> Yes, but what about 32-bit systems?
>
> The overflow indeed happens after 2^32 increments, just like seqlock.
> The question we need to ask is therefore: if 2^32 is good enough for
> seqlock, why isn't it good enough for SRCU ?

I think Paul said wrap around does happen with SRCU on 32-bit but I'll
let him talk more about it. If 32-bit is good enough, let us also drop
the size of the counters for 64-bit then?

> >>> There are other synchronization algorithms such as seqlocks which are
> >>> quite happy with much less protection against overflow (using a 32-bit
> >>> counter even on 64-bit architectures).
> >>
> >> The seqlock is an interesting point.
> >>
> >>> For practical purposes, I suspect this issue is really just theoretical.
> >>
> >> I have to ask, what is the benefit of avoiding a flip and scanning
> >> active readers? Is the issue about grace period delay or performance?
> >> If so, it might be worth prototyping that approach and measuring using
> >> rcutorture/rcuscale. If there is significant benefit to current
> >> approach, then IMO it is worth exploring.
>
> The main benefit I expect is improved performance of the grace period
> implementation in common cases where there are few or no readers
> present, especially on machines with many cpus.
>
> It allows scanning both periods (0/1) for each cpu within the same pass,
> therefore loading both period's unlock counters sitting in the same
> cache line at once (improved locality), and then loading both period's
> lock counters, also sitting in the same cache line.
>
> It also allows skipping the period flip entirely if there are no readers
> present, which is an -arguably- tiny performance improvement as well.

The issue of counter wrap aside, what if a new reader always shows up
in the active index being scanned, then can you not delay the GP
indefinitely? It seems like writer-starvation is possible then (sure
it is possible also with preemption after reader-index-sampling, but
scanning active index deliberately will make that worse). Seqlock does
not have such writer starvation just because the writer does not care
about what the readers are doing.

That said, the approach of scanning both counters does seem attractive
for when there are no readers, for the reasons you mentioned. Maybe a
heuristic to count the number of readers might help? If we are not
reader-heavy, then scan both. Otherwise, just scan the inactive ones,
and also couple that heuristic with the number of CPUs. I am
interested in working on such a design with you! Let us do it and
prototype/measure. ;-)

Thanks.