linux-kernel - Re: Internal vs. external barriers (was: Re: Interesting LKMM litmus test)

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: <20230120175804.GN2948950@paulmck-ThinkPad-P17-Gen-1>
Date:   Fri, 20 Jan 2023 09:58:04 -0800
From:   "Paul E. McKenney" <paulmck@...nel.org>
To:     Alan Stern <stern@...land.harvard.edu>
Cc:     Andrea Parri <parri.andrea@...il.com>,
        Jonas Oberhauser <jonas.oberhauser@...wei.com>,
        Peter Zijlstra <peterz@...radead.org>, will <will@...nel.org>,
        "boqun.feng" <boqun.feng@...il.com>, npiggin <npiggin@...il.com>,
        dhowells <dhowells@...hat.com>,
        "j.alglave" <j.alglave@....ac.uk>,
        "luc.maranget" <luc.maranget@...ia.fr>, akiyks <akiyks@...il.com>,
        dlustig <dlustig@...dia.com>, joel <joel@...lfernandes.org>,
        urezki <urezki@...il.com>,
        quic_neeraju <quic_neeraju@...cinc.com>,
        frederic <frederic@...nel.org>,
        Kernel development list <linux-kernel@...r.kernel.org>
Subject: Re: Internal vs. external barriers (was: Re: Interesting LKMM litmus
 test)

On Fri, Jan 20, 2023 at 11:01:03AM -0500, Alan Stern wrote:
> On Wed, Jan 18, 2023 at 04:02:14PM -0800, Paul E. McKenney wrote:
> > There are pairs of per-CPU counters.  One pair (->srcu_lock_count[])
> > counts the number of srcu_down_read() operations that took place on
> > that CPU and another pair (->srcu_unlock_count[]) counts the number
> > of srcu_down_read() operations that took place on that CPU.  There is
> > an ->srcu_idx that selects which of the ->srcu_lock_count[] elements
> > should be incremented by srcu_down_read().  Of course, srcu_down_read()
> > returns the value of ->srcu_idx that it used so that the matching
> > srcu_up_read() will use that same index when incrementing its CPU's
> > ->srcu_unlock_count[].
> > 
> > Grace periods go something like this:
> > 
> > 1.	Sum up the ->srcu_unlock_count[!ssp->srcu_idx] counters.
> > 
> > 2.	smp_mb().
> > 
> > 3.	Sum up the ->srcu_unlock_count[!ssp->srcu_idx] counters.
> 
> Presumably you meant to write "lock" here, not "unlock".

You are quite right, and apologies for my confusion.

> > 4.	If the sums are not equal, retry from #1.
> > 
> > 5.	smp_mb().
> > 
> > 6.	WRITE_ONCE(ssp->srcu_idx, !ssp->srcu_idx);
> > 
> > 7.	smp_mb().
> > 
> > 8.	Same loop as #1-4.
> > 
> > So similar to r/w semaphores, but with two separate distributed counts.
> > This means that the number of readers need not go to zero at any given
> > point in time, consistent with the need to wait only on old readers.
> 
> Reasoning from first principles, I deduce the following:
> 
> You didn't describe exactly how srcu_down_read() and srcu_up_read() 
> work.  Evidently the unlock increment in srcu_up_read() should have 
> release semantics, to prevent accesses from escaping out the end of the 
> critical section.  But the lock increment in srcu_down_read() has to be 
> stronger than an acquire; to prevent accesses in the critical section 
> escaping out the start, the increment has to be followed by smp_mb().

You got it!  There is some work going on to see if srcu_read_lock()'s
smp_mb() can be weakened to pure release, but we will see.

> The smp_mb() fences in steps 5 and 7 appear to be completely 
> unnecessary.

For correctness, agreed.  Their purpose is instead forward progress.
One can argue that step 5 is redundant due to control dependency, but
control dependencies are fragile, and as you say below, this code is
nowhere near a fastpath.

> Provided an smp_mb() is added at the very start and end of the grace 
> period, the memory barrier in step 2 and its copy in step 8 can be 
> demoted to smp_rmb().

This might need to be smp_mb() to allow srcu_read_unlock() to be
demoted to release ordering.  Work in progress.

> These changes would be small optimizations at best, and you may consider 
> them unimportant in view of the fact that grace periods often last quite 
> a long time.

Agreed, keeping it simple and obvious is important on this code, which
is nowhere near a fastpath.  The case of srcu_read_unlock() is another
thing altogether.

							Thanx, Paul