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

[Alan Stern]

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