Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Thu, 12 Jan 2023 13:57:16 -0800
From:   "Paul E. McKenney" <paulmck@kernel.org>
To:     Jonas Oberhauser <jonas.oberhauser@huawei.com>
Cc:     Alan Stern <stern@rowland.harvard.edu>,
        Peter Zijlstra <peterz@infradead.org>,
        "parri.andrea" <parri.andrea@gmail.com>, 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>
Subject: Re: Internal vs. external barriers (was: Re: Interesting LKMM litmus
 test)
Message-ID: <20230112215716.GS4028633@paulmck-ThinkPad-P17-Gen-1>
Reply-To: paulmck@kernel.org
References: <20220921173109.GA1214281@paulmck-ThinkPad-P17-Gen-1>
 <YytfFiMT2Xsdwowf@rowland.harvard.edu>
 <YywXuzZ/922LHfjI@hirez.programming.kicks-ass.net>
 <114ECED5-FED1-4361-94F7-8D9BC02449B7>
 <Y77rgeg+UgozV/oF@rowland.harvard.edu>
 <07579baee4b84532a76ea8b0b33052bb@huawei.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <07579baee4b84532a76ea8b0b33052bb@huawei.com>
Precedence: bulk

On Wed, Jan 11, 2023 at 05:24:07PM +0000, Jonas Oberhauser wrote:
> 
> 
> -----Original Message-----
> From: Alan Stern [mailto:stern@rowland.harvard.edu] 
> > What is there to try?  As far as I know, the only construct in the cat language that can be used to get the effect of counting is a recursive definition.
> > Such a lemma would have to be based on the other constructs available in the language.  The only things I can think of which even come close are the * and + operators, and they are insufficient (because they are no stronger than regular expressions, which are well known to be too weak
> -- there isn't even a regular expression for strings in which the parentheses are balanced).
> 
> Well, like I said, I don't yet understand rcu-order well enough to have any opinions :D
> You could say that the time period between me asking if you've tried other stuff and thinking that there's probably some impossibility result making that a waste of time were the one minute I used to read the comment above rcu-order and look at the recursion a little :-P, that was barely enough to understand that you're counting stuff which like you say is probably not possible with the other operators.
> 
> Anyways I'll need to take some time to read the definition carefully.

Apologies for the delay, gmail spam-foldered your email again.  :-/

I will risk sharing the intuition behind the rcu-order counting rule.

In the code, an RCU read-side critical section begins with rcu_read_lock()
and ends with the matching rcu_read_unlock().  RCU read-side critical
section may be nested, in which case RCU cares only about the outermost
of the nested set.

An RCU grace period includes at least one moment in time during which
each and every process/CPU/task/whatever is not within an RCU read-side
critical section.  Any period of time spanning a grace period is itself
a grace period.  And synchronize_rcu() waits for a grace period.

Taking the above two paragraphs together, it is forbidden for any RCU
read-side critical section to start before the beginning of a given
grace period and end after the end of that same grace period.

There is no ordering within or between RCU read-side critical sections
other than their separate relationships to any concurrent grace periods
and due to any operations within or between them that may have ordering
effects.  For example, if you have a series of three non-overlapping RCU
read-side critical sections executed by a given process in the absence of
any grace periods (for example, in the absence of any synchronize_rcu()
invocations), and where all other operations executed by that process
are READ_ONCE() and WRITE_ONCE(), without dependencies of any sort,
those memory-reference operations can be executed in any order.

So if a given RCU read-side critical section's first operation follows a
given grace period on some other process, then all of its other operations
might have been executed just after the start of that same grace period.
The start of the grace period must be epsilon before the (reordered)
end of that RCU read-side critical section.

Suppose that one of that critical section's memory references started
just before a memory reference of some other critical section on some
other process.  Then other references in this second critical section
could be reordered to precede the beginning of the grace period.

If you work the other possible examples, you will find that as long as
there are at least as many grace periods as critical sections in a given
candidate cycle, there will be sufficient ordering to prohibit that cycle.

For diagrams, please see Figures 15.14-15.16 here:

https://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.2022.09.25a.pdf

On the off-chance that this helps...

							Thanx, Paul