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

Jonas Oberhauser
2023-01-19T13:40:17Z

On 1/19/2023 1:11 AM, Paul E. McKenney wrote:
> On Wed, Jan 18, 2023 at 10:24:50PM +0100, Jonas Oberhauser wrote:
>> What I was thinking of is more something like this:
>>
>> P0{
>>    idx1 = srcu_down(&ss);
>>    srcu_up(&ss,idx1);
>> }
>>
>> P1{
>>     idx2 = srcu_down(&ss);
>>     srcu_up(&ss,idx2)
>> }
> And srcu_read_lock() and srcu_read_unlock() already do this.

I think I left out too much from my example.
And filling in the details led me down a bit of a rabbit hole of
confusion for a while.
But here's what I ended up with:

P0{
idx1 = srcu_down(&ss);
store_rel(p1, true);

shared cs

R x == ?

while (! load_acq(p2));
R idx2 == idx1 // for some reason, we got lucky!
srcu_up(&ss,idx1);
}

P1{
idx2 = srcu_down(&ss);
store_rel(p2, true);

shared cs

R y == 0

while (! load_acq(p1));
srcu_up(&ss,idx2);
}

P2 {
W y = 1
srcu_sync(&ss);
W x = 1
}

Assuming that like indicated above both threads happen to read the same
index, are you guaranteed that the shared cs lasts until both P0 and P1
have performed their final up?
Is it allowed for P0 to read x==1?

If you define matching up&down as you do through the data link, then we
get something like

P1's down ->po;prop;po  grace period
thus
P1's up  ->rcu-order  grace period
P0's down ->po;hb;po  P1's up ->rcu-order grace period
P0's up ->srcu-rscsi;rcu-link;rcu-order  grace-period
Unfortunately, this is not enough to rcu-order  P0's up with the grace
period -- you'd need a second rcu-gp for that!

Looking at it from the other side, because x reads x=1, we have
grace period ->po;rfe;po P0's up
and thus
grace period ->rcu-order P0's down ->po;hb;po P1's up
but again this would order the grace period with P1's up because you'd
need a second grace period.

When sketching it out on paper, I couldn't find any forbidden cycles,
and so x==1 would be allowed. (But as I side, I managed to confuse
myself a few times with this, so if you find a forbidden cycle let me know).

But note that the synchronization in there and the fact that both have
the same index ensures that the two grace periods overlap, in a
hypothetical order it would be
down() -> down() -> up() -> up()
(with any premutation of P0 and P1 over these events so that they each
get 1 up() and 1 down()) and thus the grace period must actually end
after both, or start before both.

With the definition I offered, you would get
P0's up() ->srcu-rscsi  P1's down()
and
P1's up() ->srcu-rscsi P0's down()
and in particular

Rx1 ->po P0's up() ->srcu-rscsi  P1's down() ->po Ry0 ->prop Wy1 ->po
srcu-gp on the same loc ->po Wx1 ->rfe Rx1
which can be collapsed to
Rx1 ->po;rcu-order;po;hb Rx1 which isn't irreflexive

Thus x==1 would be forbidden.

This is more semaphore-like, where the same cookie shared between
threads implies that it's the same semaphore, and the overlapping
guarantee (through synchronizing on p1,p2 in the beginning) means that
the critical sections overlap.

In contrast, I wouldn't suggest the same for srcu_lock and srcu_unlock,
where even though you may get the same cookie by accident, those might
still be two completely independent critical sections.
For example, you could imagine a single percpu counter _cnt (per index
of course) that is incremented and decremented for lock() and unlock(),
and the condition to pass an srcu_sync() of a given index is that the
cpu[...]._cnt[idx] are all individually 0 and the sum of all ups[idx] is
equal to the sum of all downs[idx].

If you create an operational model of up() and down() in terms of such a
per-index semaphore, I think the x==1 case would similarly need to be
forbidden. Since the grace period must end after P1's grace period, and
P0's and P1's grace period overlap and use the same semaphore, the count
is never 0 at any point in time either P0 or P1 are in the grace period,
and so the grace period must also end after P0's grace period. But then
x=1 can't yet have propagated to P0 when it reads x inside its grace period.

In contrast, if the operational model of lock() and unlock() is a
per-index and per-cpu count, then the x==1 case would be allowed, e.g.,
as follows (time from left to right, all processes happen in parallel):
P0:                      < Rx1         >
P1: <    Ry0               >
P2:           y=1  < P0!     P1! > x=1

here < and > mark the start and end of cs and gp, and Pn! is the time
the gp realizes that Pn was not in a cs.

Best wishes,

jonas