Message-ID: <2788294a-972e-acbc-84ce-25d2bb4d26d6@huaweicloud.com>
Date:   Tue, 24 Jan 2023 20:30:08 +0100
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
 Thunderbird/102.6.1
Subject: Re: Internal vs. external barriers (was: Re: Interesting LKMM litmus
 test)
To:     paulmck@kernel.org
Cc:     Andrea Parri <parri.andrea@gmail.com>,
        Alan Stern <stern@rowland.harvard.edu>,
        Jonas Oberhauser <jonas.oberhauser@huawei.com>,
        Peter Zijlstra <peterz@infradead.org>, will <will@kernel.org>,
        "boqun.feng" <boqun.feng@gmail.com>, npiggin <npiggin@gmail.com>,
        dhowells <dhowells@redhat.com>,
        "j.alglave" <j.alglave@ucl.ac.uk>,
        "luc.maranget" <luc.maranget@inria.fr>, akiyks <akiyks@gmail.com>,
        dlustig <dlustig@nvidia.com>, joel <joel@joelfernandes.org>,
        urezki <urezki@gmail.com>,
        quic_neeraju <quic_neeraju@quicinc.com>,
        frederic <frederic@kernel.org>,
        Kernel development list <linux-kernel@vger.kernel.org>
References: <20230120212037.GW2948950@paulmck-ThinkPad-P17-Gen-1>
 <Y82dWEW4RwclDTGM@rowland.harvard.edu>
 <20230123201659.GA3754540@paulmck-ThinkPad-P17-Gen-1>
 <Y88/5ib7zYl67mcE@rowland.harvard.edu>
 <20230124040611.GD2948950@paulmck-ThinkPad-P17-Gen-1>
 <Y8+8fH52iqQABYs2@andrea>
 <20230124145423.GI2948950@paulmck-ThinkPad-P17-Gen-1>
 <8cc799ab-ffa1-47f7-6e1d-97488a210f14@huaweicloud.com>
 <20230124162253.GL2948950@paulmck-ThinkPad-P17-Gen-1>
 <3e5020c2-0dd3-68a6-9b98-5a7f57ed7733@huaweicloud.com>
 <20230124172647.GN2948950@paulmck-ThinkPad-P17-Gen-1>
From:   Jonas Oberhauser <jonas.oberhauser@huaweicloud.com>
In-Reply-To: <20230124172647.GN2948950@paulmck-ThinkPad-P17-Gen-1>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: bulk


On 1/24/2023 6:26 PM, Paul E. McKenney wrote:
> On Tue, Jan 24, 2023 at 05:39:53PM +0100, Jonas Oberhauser wrote:
>>
>> On 1/24/2023 5:22 PM, Paul E. McKenney wrote:
>>> I clearly recall some
>>> store-based lack of ordering after a grace period from some years back,
>>> and am thus far failing to reproduce it.
>>>
>>> And here is another attempt that herd7 actually does allow.
>>>
>>> So what did I mess up this time?  ;-)
>>>
>>> 							Thanx, Paul
>>>
>>> ------------------------------------------------------------------------
>>>
>>> C C-srcu-observed-4
>>>
>>> (*
>>>    * Result: Sometimes
>>>    *
>>>    * The Linux-kernel implementation is suspected to forbid this.
>>>    *)
>>>
>>> {}
>>>
>>> P0(int *x, int *y, int *z, struct srcu_struct *s)
>>> {
>>> 	int r1;
>>>
>>> 	r1 = srcu_read_lock(s);
>>> 	WRITE_ONCE(*y, 2);
>>> 	WRITE_ONCE(*x, 1);
>>> 	srcu_read_unlock(s, r1);
>>> }
>>>
>>> P1(int *x, int *y, int *z, struct srcu_struct *s)
>>> {
>>> 	int r1;
>>>
>>> 	WRITE_ONCE(*y, 1);
>>> 	synchronize_srcu(s);
>>> 	WRITE_ONCE(*z, 2);
>>> }
>>>
>>> P2(int *x, int *y, int *z, struct srcu_struct *s)
>>> {
>>> 	WRITE_ONCE(*z, 1);
>>> 	smp_store_release(x, 2);
>>> }
>>>
>>> exists (x=1 /\ y=1 /\ z=1)
>> I think even if you implement the unlock as mb() followed by some store that
>> is read by the gp between mb()s, this would still be allowed.
> The implementation of synchronize_srcu() has quite a few smp_mb()
> invocations.
>
> But exactly how are you modeling this?  As in what additional accesses
> and memory barriers are you placing in which locations?

Along these lines:

P0(int *x, int *y, int *z, int *magic_location)
{
	int r1;


	WRITE_ONCE(*y, 2);
	WRITE_ONCE(*x, 1);

         smp_mb();
	WRITE_ONCE(*magic_location, 1);

}

P1(int *x, int *y, int *z, int *magic_location)
{
	int r1;

	WRITE_ONCE(*y, 1);

         smp_mb();
         while (! READ_ONCE(*magic_location))
		;
	smp_mb();
	WRITE_ONCE(*z, 2);
}


P2(int *x, int *y, int *z, struct srcu_struct *s)
{
	WRITE_ONCE(*z, 1);
	smp_store_release(x, 2);
}


Note that you can add as many additional smp_mb() and other accesses as 
you want around the original srcu call sites. I don't see how they could 
influence the absence of a cycle.

(Also, to make it work with herd it seems you need to replace the loop 
with a single read and state in the exists clause that it happens to 
read a 1.)

>> I have already forgotten the specifics, but I think the power model allows
>> certain stores never propagating somewhere?
> PowerPC would forbid the 3.2W case, where each process used an
> smp_store_release() as its sole ordering (no smp_mb() calls at all).
>
> [...]
>
> This propagation is modulated by the memory barriers, though.

Ah, looking at the model now. Indeed it's forbidden, because in order to 
say that something is in co, there must not be a (resulting) cycle of co 
and barriers. But you'd get that here.  In the axiomatic model, this 
corresponds to saying Power's "prop | co" is acyclic. The same isn't 
true in LKMM. So that's probably why.

Have fun, jonas