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: <Y8hclxuhpGm+krkz@rowland.harvard.edu>
Date:   Wed, 18 Jan 2023 15:54:47 -0500
From:   Alan Stern <stern@...land.harvard.edu>
To:     "Paul E. McKenney" <paulmck@...nel.org>
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 Wed, Jan 18, 2023 at 12:06:01PM -0800, Paul E. McKenney wrote:
> On Wed, Jan 18, 2023 at 11:50:24AM -0500, Alan Stern wrote:
> Boqun mentioned off-list this morning that this is still the case,
> and that each execution of srcu_read_lock() will return a unique value.
> Assuming that I understood him correctly, anyway.

That will no longer be true with the patch I posted yesterday.  Every 
execution of srcu_read_lock() will return 0 (or whatever the initial 
value of the lock variable is).

But with a small change to the .def file, each execution of 
srcu_read_unlock() can be made to increment the lock's value, and then 
the next srcu_read_lock() would naturally return the new value.

> > > given that I have no idea how one would go about modeling down_read()
> > > and up_read() in LKMM.
> > 
> > It might make sense to work on that first, before trying to do 
> > srcu_down_read() and srcu_up_read().
> 
> The thing is that it is easy to associate an srcu_down_read() with the
> corresponding srcu_up_read().  With down() and up(), although in the
> Linux kernel this might be represented by a data structure tracking
> (say) an I/O request, LKMM is going to be hard pressed to figure that out.

It would help (or at least, it would help _me_) if you gave a short 
explanation of how srcu_down_read() and srcu_up_read() are meant to 
work.  With regular r/w semaphores, the initial lock value is 0, each 
down() operation decrements the value, each up() operation increments 
the value -- or vice versa if you don't like negative values -- and a 
write_lock() will wait until the value is >= 0.  In that setting, it 
makes sense to say that a down() which changes the value from n to n-1 
matches the next up() which changes the value from n-1 to n.

I presume that srcu semaphores do not work this way.  Particularly since 
the down() operation returns a value which must be passed to the 
corresponding up() operation.  So how _do_ they work?

> > Hmmm.  What happens if you write:
> > 
> > 	r1 = srcu_down_read(x);
> > 	r2 = srcu_down_read(x);
> > 	srcu_up_read(x, r1);
> > 	srcu_up_read(x, r2);
> > 
> > ?  I can't even tell what that would be _intended_ to do.
> 
> Let's take it one line at a time:
> 
> 	r1 = srcu_down_read(x);
> 	// A
> 	r2 = srcu_down_read(x);
> 	// B
> 	srcu_up_read(x, r1);
> 	// C
> 	srcu_up_read(x, r2);
> 	// D
> 
> An SRCU grace period that starts at A is permitted to complete at
> C, difficult though it might be to actually make this happen in the
> Linux kernel.  It need wait only for pre-existing critical sections.

So the down() returning r1 matches the up() receiving r1?

> But an SRCU grace period that starts at either B or C must wait for both
> critical sections, that is until D.

Implying that the down() returning r2 matches up() receiving r2?

And in general, an up() matches a down() iff they have the same values?  
And we can imagine that every down() returns a different value?  

How does this differ from srcu_read_lock() and srcu_read_unlock()?  And 
how do the "up" and "down" parts figure into it? -- what is going up or 
down?

Alan