[PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[Joel Fernandes (Google)]

This adds an example for the important RCU grace period guarantee, which
shows an RCU reader can never span a grace period.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
 .../litmus-tests/RCU+sync+free.litmus         | 40 +++++++++++++++++++
 1 file changed, 40 insertions(+)
 create mode 100644 tools/memory-model/litmus-tests/RCU+sync+free.litmus

diff --git a/tools/memory-model/litmus-tests/RCU+sync+free.litmus b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
new file mode 100644
index 0000000000000..c4682502dd296
--- /dev/null
+++ b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
@@ -0,0 +1,40 @@
+C RCU+sync+free
+
+(*
+ * Result: Never
+ *
+ * This litmus test demonstrates that an RCU reader can never see a write after
+ * the grace period, if it saw writes that happen before the grace period. This
+ * is a typical pattern of RCU usage, where the write before the grace period
+ * assigns a pointer, and the writes after destroy the object that the pointer
+ * points to.
+ *
+ * This guarantee also implies, an RCU reader can never span a grace period and
+ * is an important RCU grace period memory ordering guarantee.
+ *)
+
+{
+x = 1;
+y = x;
+z = 1;
+}
+
+P0(int *x, int *z, int **y)
+{
+	int r0;
+	int r1;
+
+	rcu_read_lock();
+	r0 = rcu_dereference(*y);
+	r1 = READ_ONCE(*r0);
+	rcu_read_unlock();
+}
+
+P1(int *x, int *z, int **y)
+{
+	rcu_assign_pointer(*y, z);
+	synchronize_rcu();
+	WRITE_ONCE(*x, 0);
+}
+
+exists (0:r0=x /\ 0:r1=0)
-- 
2.25.1.696.g5e7596f4ac-goog

[PATCH 2/3] LKMM: Add litmus test for RCU GP guarantee where reader stores

[Joel Fernandes (Google)]

This adds an example for the important RCU grace period guarantee, which
shows an RCU reader can never span a grace period.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
 .../litmus-tests/RCU+sync+read.litmus         | 37 +++++++++++++++++++
 1 file changed, 37 insertions(+)
 create mode 100644 tools/memory-model/litmus-tests/RCU+sync+read.litmus

diff --git a/tools/memory-model/litmus-tests/RCU+sync+read.litmus b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
new file mode 100644
index 0000000000000..73557772e2a32
--- /dev/null
+++ b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
@@ -0,0 +1,37 @@
+C RCU+sync+read
+
+(*
+ * Result: Never
+ *
+ * This litmus test demonstrates that after a grace period, an RCU updater always
+ * sees all stores done in prior RCU read-side critical sections. Such
+ * read-side critical sections would have ended before the grace period ended.
+ *
+ * This guarantee also implies, an RCU reader can never span a grace period and
+ * is an important RCU grace period memory ordering guarantee.
+ *)
+
+{
+x = 0;
+y = 0;
+}
+
+P0(int *x, int *y)
+{
+	rcu_read_lock();
+	WRITE_ONCE(*x, 1);
+	WRITE_ONCE(*y, 1);
+	rcu_read_unlock();
+}
+
+P1(int *x, int *y)
+{
+	int r0;
+	int r1;
+
+	r0 = READ_ONCE(*x);
+	synchronize_rcu();
+	r1 = READ_ONCE(*y);
+}
+
+exists (1:r0=1 /\ 1:r1=0)
-- 
2.25.1.696.g5e7596f4ac-goog

Re: [PATCH 2/3] LKMM: Add litmus test for RCU GP guarantee where reader stores

[Alan Stern]

On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:

> This adds an example for the important RCU grace period guarantee, which
> shows an RCU reader can never span a grace period.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  .../litmus-tests/RCU+sync+read.litmus         | 37 +++++++++++++++++++
>  1 file changed, 37 insertions(+)
>  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+read.litmus
> 
> diff --git a/tools/memory-model/litmus-tests/RCU+sync+read.litmus b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> new file mode 100644
> index 0000000000000..73557772e2a32
> --- /dev/null
> +++ b/tools/memory-model/litmus-tests/RCU+sync+read.litmus

Do these new tests really belong here?  I thought we were adding a new 
directory under Documentation/ for litmus tests that illustrate parts 
of the LKMM or memory-barriers.txt.

By contrast, the tests under tools/memory-model are merely to show 
people what litmus tests look like and how they should be written.

Alan

Re: [PATCH 2/3] LKMM: Add litmus test for RCU GP guarantee where reader stores

[Joel Fernandes]

On Fri, Mar 20, 2020 at 11:03:30AM -0400, Alan Stern wrote:
> On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:
> 
> > This adds an example for the important RCU grace period guarantee, which
> > shows an RCU reader can never span a grace period.
> > 
> > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > ---
> >  .../litmus-tests/RCU+sync+read.litmus         | 37 +++++++++++++++++++
> >  1 file changed, 37 insertions(+)
> >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > 
> > diff --git a/tools/memory-model/litmus-tests/RCU+sync+read.litmus b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > new file mode 100644
> > index 0000000000000..73557772e2a32
> > --- /dev/null
> > +++ b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> 
> Do these new tests really belong here?  I thought we were adding a new 
> directory under Documentation/ for litmus tests that illustrate parts 
> of the LKMM or memory-barriers.txt.
> 
> By contrast, the tests under tools/memory-model are merely to show 
> people what litmus tests look like and how they should be written.

I could add it to tools/memory-model/Documentation/ under a new
'examples' directory there. We could also create an 'rcu' directory in
tools/memory-model/litmus-tests/ and add these there. Thoughts?

thanks,

 - Joel

Re: [PATCH 2/3] LKMM: Add litmus test for RCU GP guarantee where reader stores

[Alan Stern]

On Fri, 20 Mar 2020, Joel Fernandes wrote:

> On Fri, Mar 20, 2020 at 11:03:30AM -0400, Alan Stern wrote:
> > On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:
> > 
> > > This adds an example for the important RCU grace period guarantee, which
> > > shows an RCU reader can never span a grace period.
> > > 
> > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > > ---
> > >  .../litmus-tests/RCU+sync+read.litmus         | 37 +++++++++++++++++++
> > >  1 file changed, 37 insertions(+)
> > >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > 
> > > diff --git a/tools/memory-model/litmus-tests/RCU+sync+read.litmus b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > new file mode 100644
> > > index 0000000000000..73557772e2a32
> > > --- /dev/null
> > > +++ b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > 
> > Do these new tests really belong here?  I thought we were adding a new 
> > directory under Documentation/ for litmus tests that illustrate parts 
> > of the LKMM or memory-barriers.txt.
> > 
> > By contrast, the tests under tools/memory-model are merely to show 
> > people what litmus tests look like and how they should be written.
> 
> I could add it to tools/memory-model/Documentation/ under a new
> 'examples' directory there. We could also create an 'rcu' directory in
> tools/memory-model/litmus-tests/ and add these there. Thoughts?

What happened was that about a month ago, Boqun Feng added
Documentation/atomic-tests for litmus tests related to handling of
atomic_t types (see
<https://marc.info/?l=linux-kernel&m=158276408609029&w=2>.)  Should we
interpose an extra directory level, making it
Documentation/litmus-tests/atomic?  Or
Documentation/LKMM-litmus-tests/atomic?

Then the new tests added here could go into
Documentation/litmus-tests/rcu, or whatever.

Alan

Re: [PATCH 2/3] LKMM: Add litmus test for RCU GP guarantee where reader stores

[Joel Fernandes]

On Fri, Mar 20, 2020 at 04:56:59PM -0400, Alan Stern wrote:
> On Fri, 20 Mar 2020, Joel Fernandes wrote:
> 
> > On Fri, Mar 20, 2020 at 11:03:30AM -0400, Alan Stern wrote:
> > > On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:
> > > 
> > > > This adds an example for the important RCU grace period guarantee, which
> > > > shows an RCU reader can never span a grace period.
> > > > 
> > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > > > ---
> > > >  .../litmus-tests/RCU+sync+read.litmus         | 37 +++++++++++++++++++
> > > >  1 file changed, 37 insertions(+)
> > > >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > 
> > > > diff --git a/tools/memory-model/litmus-tests/RCU+sync+read.litmus b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > new file mode 100644
> > > > index 0000000000000..73557772e2a32
> > > > --- /dev/null
> > > > +++ b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > 
> > > Do these new tests really belong here?  I thought we were adding a new 
> > > directory under Documentation/ for litmus tests that illustrate parts 
> > > of the LKMM or memory-barriers.txt.
> > > 
> > > By contrast, the tests under tools/memory-model are merely to show 
> > > people what litmus tests look like and how they should be written.
> > 
> > I could add it to tools/memory-model/Documentation/ under a new
> > 'examples' directory there. We could also create an 'rcu' directory in
> > tools/memory-model/litmus-tests/ and add these there. Thoughts?
> 
> What happened was that about a month ago, Boqun Feng added
> Documentation/atomic-tests for litmus tests related to handling of
> atomic_t types (see
> <https://marc.info/?l=linux-kernel&m=158276408609029&w=2>.)  Should we
> interpose an extra directory level, making it
> Documentation/litmus-tests/atomic?  Or
> Documentation/LKMM-litmus-tests/atomic?
> 
> Then the new tests added here could go into
> Documentation/litmus-tests/rcu, or whatever.

That's fine with me. Unless anyone objects, I will add to
Documentation/litmus-tests/rcu and resend.

thanks,

 - Joel

Re: [PATCH 2/3] LKMM: Add litmus test for RCU GP guarantee where reader stores

[Boqun Feng]

On Fri, Mar 20, 2020 at 05:44:32PM -0400, Joel Fernandes wrote:
> On Fri, Mar 20, 2020 at 04:56:59PM -0400, Alan Stern wrote:
> > On Fri, 20 Mar 2020, Joel Fernandes wrote:
> > 
> > > On Fri, Mar 20, 2020 at 11:03:30AM -0400, Alan Stern wrote:
> > > > On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:
> > > > 
> > > > > This adds an example for the important RCU grace period guarantee, which
> > > > > shows an RCU reader can never span a grace period.
> > > > > 
> > > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > > > > ---
> > > > >  .../litmus-tests/RCU+sync+read.litmus         | 37 +++++++++++++++++++
> > > > >  1 file changed, 37 insertions(+)
> > > > >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > > 
> > > > > diff --git a/tools/memory-model/litmus-tests/RCU+sync+read.litmus b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > > new file mode 100644
> > > > > index 0000000000000..73557772e2a32
> > > > > --- /dev/null
> > > > > +++ b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > 
> > > > Do these new tests really belong here?  I thought we were adding a new 
> > > > directory under Documentation/ for litmus tests that illustrate parts 
> > > > of the LKMM or memory-barriers.txt.
> > > > 
> > > > By contrast, the tests under tools/memory-model are merely to show 
> > > > people what litmus tests look like and how they should be written.
> > > 
> > > I could add it to tools/memory-model/Documentation/ under a new
> > > 'examples' directory there. We could also create an 'rcu' directory in
> > > tools/memory-model/litmus-tests/ and add these there. Thoughts?
> > 
> > What happened was that about a month ago, Boqun Feng added
> > Documentation/atomic-tests for litmus tests related to handling of
> > atomic_t types (see
> > <https://marc.info/?l=linux-kernel&m=158276408609029&w=2>.)  Should we
> > interpose an extra directory level, making it
> > Documentation/litmus-tests/atomic?  Or
> > Documentation/LKMM-litmus-tests/atomic?
> > 
> > Then the new tests added here could go into
> > Documentation/litmus-tests/rcu, or whatever.
> 
> That's fine with me. Unless anyone objects, I will add to
> Documentation/litmus-tests/rcu and resend.
> 

Seems good to me, I will resend my patchset with the new directory. And
I assume in your patchset you will include the MAINTAINERS part for
adding Documentation/litmus-tests/ as a diretory watched by LKMM group?
In that case, I won't need to add any change to MAINTAINERS file in mine
and we won't have any conflict. ;-)

Regards,
Boqun


> thanks,
> 
>  - Joel
> 

Re: [PATCH 2/3] LKMM: Add litmus test for RCU GP guarantee where reader stores

[Joel Fernandes]

On Sat, Mar 21, 2020 at 10:05:01AM +0800, Boqun Feng wrote:
> On Fri, Mar 20, 2020 at 05:44:32PM -0400, Joel Fernandes wrote:
> > On Fri, Mar 20, 2020 at 04:56:59PM -0400, Alan Stern wrote:
> > > On Fri, 20 Mar 2020, Joel Fernandes wrote:
> > > 
> > > > On Fri, Mar 20, 2020 at 11:03:30AM -0400, Alan Stern wrote:
> > > > > On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:
> > > > > 
> > > > > > This adds an example for the important RCU grace period guarantee, which
> > > > > > shows an RCU reader can never span a grace period.
> > > > > > 
> > > > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > > > > > ---
> > > > > >  .../litmus-tests/RCU+sync+read.litmus         | 37 +++++++++++++++++++
> > > > > >  1 file changed, 37 insertions(+)
> > > > > >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > > > 
> > > > > > diff --git a/tools/memory-model/litmus-tests/RCU+sync+read.litmus b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > > > new file mode 100644
> > > > > > index 0000000000000..73557772e2a32
> > > > > > --- /dev/null
> > > > > > +++ b/tools/memory-model/litmus-tests/RCU+sync+read.litmus
> > > > > 
> > > > > Do these new tests really belong here?  I thought we were adding a new 
> > > > > directory under Documentation/ for litmus tests that illustrate parts 
> > > > > of the LKMM or memory-barriers.txt.
> > > > > 
> > > > > By contrast, the tests under tools/memory-model are merely to show 
> > > > > people what litmus tests look like and how they should be written.
> > > > 
> > > > I could add it to tools/memory-model/Documentation/ under a new
> > > > 'examples' directory there. We could also create an 'rcu' directory in
> > > > tools/memory-model/litmus-tests/ and add these there. Thoughts?
> > > 
> > > What happened was that about a month ago, Boqun Feng added
> > > Documentation/atomic-tests for litmus tests related to handling of
> > > atomic_t types (see
> > > <https://marc.info/?l=linux-kernel&m=158276408609029&w=2>.)  Should we
> > > interpose an extra directory level, making it
> > > Documentation/litmus-tests/atomic?  Or
> > > Documentation/LKMM-litmus-tests/atomic?
> > > 
> > > Then the new tests added here could go into
> > > Documentation/litmus-tests/rcu, or whatever.
> > 
> > That's fine with me. Unless anyone objects, I will add to
> > Documentation/litmus-tests/rcu and resend.
> > 
> 
> Seems good to me, I will resend my patchset with the new directory. And
> I assume in your patchset you will include the MAINTAINERS part for
> adding Documentation/litmus-tests/ as a diretory watched by LKMM group?
> In that case, I won't need to add any change to MAINTAINERS file in mine
> and we won't have any conflict. ;-)

Yes, will add to MAINTAINERS so that you don't have to :) About to send my
queue now.

thanks,

 - Joel

[PATCH 3/3] LKMM: Rename MP+onceassign+derefonce for better clarity

[Joel Fernandes (Google)]

For better consistency with RCU examples, rename MP+onceassign+derefonce
to RCU+MP+onceassign+derefonce.

I plan to add more RCU related litmus tests, so we could use this
convention if that's Ok.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
 ...sign+derefonce.litmus => RCU+MP+onceassign+derefonce.litmus} | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
 rename tools/memory-model/litmus-tests/{MP+onceassign+derefonce.litmus => RCU+MP+onceassign+derefonce.litmus} (94%)

diff --git a/tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus b/tools/memory-model/litmus-tests/RCU+MP+onceassign+derefonce.litmus
similarity index 94%
rename from tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus
rename to tools/memory-model/litmus-tests/RCU+MP+onceassign+derefonce.litmus
index 97731b4bbdd8e..f9bfe0fd42e4d 100644
--- a/tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus
+++ b/tools/memory-model/litmus-tests/RCU+MP+onceassign+derefonce.litmus
@@ -1,4 +1,4 @@
-C MP+onceassign+derefonce
+C RCU+MP+onceassign+derefonce
 
 (*
  * Result: Never
-- 
2.25.1.696.g5e7596f4ac-goog

Re: [PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[Andrea Parri]

On Fri, Mar 20, 2020 at 02:55:50AM -0400, Joel Fernandes (Google) wrote:
> This adds an example for the important RCU grace period guarantee, which
> shows an RCU reader can never span a grace period.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  .../litmus-tests/RCU+sync+free.litmus         | 40 +++++++++++++++++++
>  1 file changed, 40 insertions(+)
>  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+free.litmus
> 
> diff --git a/tools/memory-model/litmus-tests/RCU+sync+free.litmus b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> new file mode 100644
> index 0000000000000..c4682502dd296
> --- /dev/null
> +++ b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> @@ -0,0 +1,40 @@
> +C RCU+sync+free
> +
> +(*
> + * Result: Never
> + *
> + * This litmus test demonstrates that an RCU reader can never see a write after
> + * the grace period, if it saw writes that happen before the grace period. This
> + * is a typical pattern of RCU usage, where the write before the grace period
> + * assigns a pointer, and the writes after destroy the object that the pointer
> + * points to.
> + *
> + * This guarantee also implies, an RCU reader can never span a grace period and
> + * is an important RCU grace period memory ordering guarantee.
> + *)
> +
> +{
> +x = 1;
> +y = x;
> +z = 1;

FYI, this could become a little more readable if we wrote it as follows:

int x = 1;
int *y = &x;
int z = 1;

The LKMM tools are happy either way, just a matter of style/preference;
and yes, MP+onceassign+derefonce isn't currently following mine...  ;-/


> +}
> +
> +P0(int *x, int *z, int **y)
> +{
> +	int r0;

This would need to be "int *r0;" in order to make klitmus7(+gcc) happy.


> +	int r1;
> +
> +	rcu_read_lock();
> +	r0 = rcu_dereference(*y);
> +	r1 = READ_ONCE(*r0);
> +	rcu_read_unlock();
> +}
> +
> +P1(int *x, int *z, int **y)
> +{
> +	rcu_assign_pointer(*y, z);

AFAICT, you don't need this "RELEASE"; e.g., compare this test with the
example in:

  https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Grace-Period%20Guarantee

What am I missing?

Thanks,
  Andrea


> +	synchronize_rcu();
> +	WRITE_ONCE(*x, 0);
> +}
> +
> +exists (0:r0=x /\ 0:r1=0)
> -- 
> 2.25.1.696.g5e7596f4ac-goog
> 

Re: [PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[Alan Stern]

On Fri, 20 Mar 2020, Andrea Parri wrote:

> On Fri, Mar 20, 2020 at 02:55:50AM -0400, Joel Fernandes (Google) wrote:
> > This adds an example for the important RCU grace period guarantee, which
> > shows an RCU reader can never span a grace period.
> > 
> > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > ---
> >  .../litmus-tests/RCU+sync+free.litmus         | 40 +++++++++++++++++++
> >  1 file changed, 40 insertions(+)
> >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > 
> > diff --git a/tools/memory-model/litmus-tests/RCU+sync+free.litmus b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > new file mode 100644
> > index 0000000000000..c4682502dd296
> > --- /dev/null
> > +++ b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > @@ -0,0 +1,40 @@
> > +C RCU+sync+free
> > +
> > +(*
> > + * Result: Never
> > + *
> > + * This litmus test demonstrates that an RCU reader can never see a write after
> > + * the grace period, if it saw writes that happen before the grace period. This
> > + * is a typical pattern of RCU usage, where the write before the grace period
> > + * assigns a pointer, and the writes after destroy the object that the pointer
> > + * points to.
> > + *
> > + * This guarantee also implies, an RCU reader can never span a grace period and
> > + * is an important RCU grace period memory ordering guarantee.
> > + *)
> > +
> > +{
> > +x = 1;
> > +y = x;
> > +z = 1;
> 
> FYI, this could become a little more readable if we wrote it as follows:
> 
> int x = 1;
> int *y = &x;
> int z = 1;

Also, the test won't work with klitmus7 unless you do this.

> The LKMM tools are happy either way, just a matter of style/preference;
> and yes, MP+onceassign+derefonce isn't currently following mine...  ;-/
> 
> 
> > +}
> > +
> > +P0(int *x, int *z, int **y)
> > +{
> > +	int r0;
> 
> This would need to be "int *r0;" in order to make klitmus7(+gcc) happy.
> 
> 
> > +	int r1;
> > +
> > +	rcu_read_lock();
> > +	r0 = rcu_dereference(*y);
> > +	r1 = READ_ONCE(*r0);
> > +	rcu_read_unlock();
> > +}
> > +
> > +P1(int *x, int *z, int **y)
> > +{
> > +	rcu_assign_pointer(*y, z);
> 
> AFAICT, you don't need this "RELEASE"; e.g., compare this test with the
> example in:
> 
>   https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Grace-Period%20Guarantee
> 
> What am I missing?

If z were not a simple variable but a more complicated structure, the
RELEASE would be necessary to ensure that all P1's prior changes to z
became visible before the write to y.

Besides, it's good form always to match rcu_dereference() with 
rcu_assign_pointer(), for code documentation if nothing else.

Alan

Re: [PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[Joel Fernandes]

On Fri, Mar 20, 2020 at 11:07:10AM -0400, Alan Stern wrote:
> On Fri, 20 Mar 2020, Andrea Parri wrote:
> 
> > On Fri, Mar 20, 2020 at 02:55:50AM -0400, Joel Fernandes (Google) wrote:
> > > This adds an example for the important RCU grace period guarantee, which
> > > shows an RCU reader can never span a grace period.
> > > 
> > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > > ---
> > >  .../litmus-tests/RCU+sync+free.litmus         | 40 +++++++++++++++++++
> > >  1 file changed, 40 insertions(+)
> > >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > > 
> > > diff --git a/tools/memory-model/litmus-tests/RCU+sync+free.litmus b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > > new file mode 100644
> > > index 0000000000000..c4682502dd296
> > > --- /dev/null
> > > +++ b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > > @@ -0,0 +1,40 @@
> > > +C RCU+sync+free
> > > +
> > > +(*
> > > + * Result: Never
> > > + *
> > > + * This litmus test demonstrates that an RCU reader can never see a write after
> > > + * the grace period, if it saw writes that happen before the grace period. This
> > > + * is a typical pattern of RCU usage, where the write before the grace period
> > > + * assigns a pointer, and the writes after destroy the object that the pointer
> > > + * points to.
> > > + *
> > > + * This guarantee also implies, an RCU reader can never span a grace period and
> > > + * is an important RCU grace period memory ordering guarantee.
> > > + *)
> > > +
> > > +{
> > > +x = 1;
> > > +y = x;
> > > +z = 1;
> > 
> > FYI, this could become a little more readable if we wrote it as follows:
> > 
> > int x = 1;
> > int *y = &x;
> > int z = 1;
> 
> Also, the test won't work with klitmus7 unless you do this.

Will do.

> > The LKMM tools are happy either way, just a matter of style/preference;
> > and yes, MP+onceassign+derefonce isn't currently following mine...  ;-/
> > 
> > 
> > > +}
> > > +
> > > +P0(int *x, int *z, int **y)
> > > +{
> > > +	int r0;
> > 
> > This would need to be "int *r0;" in order to make klitmus7(+gcc) happy.

Sorry fixed it now, my version of herd did not complain on this so I missed it.

> > > +	int r1;
> > > +
> > > +	rcu_read_lock();
> > > +	r0 = rcu_dereference(*y);
> > > +	r1 = READ_ONCE(*r0);
> > > +	rcu_read_unlock();
> > > +}
> > > +
> > > +P1(int *x, int *z, int **y)
> > > +{
> > > +	rcu_assign_pointer(*y, z);
> > 
> > AFAICT, you don't need this "RELEASE"; e.g., compare this test with the
> > example in:
> > 
> >   https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Grace-Period%20Guarantee
> > 
> > What am I missing?
> 
> If z were not a simple variable but a more complicated structure, the
> RELEASE would be necessary to ensure that all P1's prior changes to z
> became visible before the write to y.
> 
> Besides, it's good form always to match rcu_dereference() with 
> rcu_assign_pointer(), for code documentation if nothing else.

Yes, adding to what Alan said, you can see the effect of not using
rcu_assign_pointer() in: MP+onceassign+derefonce.litmus

Alan and Andrea, may I add your Reviewed-by or Acked-by tags on the v2?

thanks,

 - Joel

Re: [PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[Andrea Parri]

On Fri, Mar 20, 2020 at 02:55:50AM -0400, Joel Fernandes (Google) wrote:
> This adds an example for the important RCU grace period guarantee, which
> shows an RCU reader can never span a grace period.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  .../litmus-tests/RCU+sync+free.litmus         | 40 +++++++++++++++++++

I forgot to mention: this should probably come with an update of the
list of tests reported in tools/memory-model/litmus-tests/README and
similarly for patches #2 and #3; #2, #3 looked otherwise fine to me.

Thanks,
  Andrea


>  1 file changed, 40 insertions(+)
>  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+free.litmus
> 
> diff --git a/tools/memory-model/litmus-tests/RCU+sync+free.litmus b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> new file mode 100644
> index 0000000000000..c4682502dd296
> --- /dev/null
> +++ b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> @@ -0,0 +1,40 @@
> +C RCU+sync+free
> +
> +(*
> + * Result: Never
> + *
> + * This litmus test demonstrates that an RCU reader can never see a write after
> + * the grace period, if it saw writes that happen before the grace period. This
> + * is a typical pattern of RCU usage, where the write before the grace period
> + * assigns a pointer, and the writes after destroy the object that the pointer
> + * points to.
> + *
> + * This guarantee also implies, an RCU reader can never span a grace period and
> + * is an important RCU grace period memory ordering guarantee.
> + *)
> +
> +{
> +x = 1;
> +y = x;
> +z = 1;
> +}
> +
> +P0(int *x, int *z, int **y)
> +{
> +	int r0;
> +	int r1;
> +
> +	rcu_read_lock();
> +	r0 = rcu_dereference(*y);
> +	r1 = READ_ONCE(*r0);
> +	rcu_read_unlock();
> +}
> +
> +P1(int *x, int *z, int **y)
> +{
> +	rcu_assign_pointer(*y, z);
> +	synchronize_rcu();
> +	WRITE_ONCE(*x, 0);
> +}
> +
> +exists (0:r0=x /\ 0:r1=0)
> -- 
> 2.25.1.696.g5e7596f4ac-goog
> 

Re: [PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[Alan Stern]

On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:

> This adds an example for the important RCU grace period guarantee, which
> shows an RCU reader can never span a grace period.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  .../litmus-tests/RCU+sync+free.litmus         | 40 +++++++++++++++++++
>  1 file changed, 40 insertions(+)
>  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+free.litmus
> 
> diff --git a/tools/memory-model/litmus-tests/RCU+sync+free.litmus b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> new file mode 100644
> index 0000000000000..c4682502dd296
> --- /dev/null
> +++ b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> @@ -0,0 +1,40 @@
> +C RCU+sync+free
> +
> +(*
> + * Result: Never
> + *

The following comment needs some rewriting.  The grammar is somewhat
awkward and a very important "not" is missing.

> + * This litmus test demonstrates that an RCU reader can never see a write after
> + * the grace period, if it saw writes that happen before the grace period.

An RCU reader can never see a write that follows a grace period if it
did _not_ see writes that precede the grace period.

>  This
> + * is a typical pattern of RCU usage, where the write before the grace period
> + * assigns a pointer, and the writes after destroy the object that the pointer
> + * points to.

... that the pointer used to point to.

> + *
> + * This guarantee also implies, an RCU reader can never span a grace period and
> + * is an important RCU grace period memory ordering guarantee.

Unnecessary comma, and it is not clear what "This" refers to.  The 
whole sentence should be phrased differently:

	This is one implication of the RCU grace-period guarantee,
	which says (among other things) that an RCU reader cannot span 
	a grace period.

Alan

Re: [PATCH 1/3] LKMM: Add litmus test for RCU GP guarantee where updater frees object

[Joel Fernandes]

On Fri, Mar 20, 2020 at 10:59:55AM -0400, Alan Stern wrote:
> On Fri, 20 Mar 2020, Joel Fernandes (Google) wrote:
> 
> > This adds an example for the important RCU grace period guarantee, which
> > shows an RCU reader can never span a grace period.
> > 
> > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > ---
> >  .../litmus-tests/RCU+sync+free.litmus         | 40 +++++++++++++++++++
> >  1 file changed, 40 insertions(+)
> >  create mode 100644 tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > 
> > diff --git a/tools/memory-model/litmus-tests/RCU+sync+free.litmus b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > new file mode 100644
> > index 0000000000000..c4682502dd296
> > --- /dev/null
> > +++ b/tools/memory-model/litmus-tests/RCU+sync+free.litmus
> > @@ -0,0 +1,40 @@
> > +C RCU+sync+free
> > +
> > +(*
> > + * Result: Never
> > + *
> 
> The following comment needs some rewriting.  The grammar is somewhat
> awkward and a very important "not" is missing.
> 
> > + * This litmus test demonstrates that an RCU reader can never see a write after
> > + * the grace period, if it saw writes that happen before the grace period.
> 
> An RCU reader can never see a write that follows a grace period if it
> did _not_ see writes that precede the grace period.

Yes, you are right. I will change your wording to 'did not see *all* writes
that precede'.

> >  This
> > + * is a typical pattern of RCU usage, where the write before the grace period
> > + * assigns a pointer, and the writes after destroy the object that the pointer
> > + * points to.
> 
> ... that the pointer used to point to.

Will fix.

> > + *
> > + * This guarantee also implies, an RCU reader can never span a grace period and
> > + * is an important RCU grace period memory ordering guarantee.
> 
> Unnecessary comma, and it is not clear what "This" refers to.  The 
> whole sentence should be phrased differently:
> 
> 	This is one implication of the RCU grace-period guarantee,
> 	which says (among other things) that an RCU reader cannot span 
> 	a grace period.

Your wording is better, will use that.

thanks,

 - Joel