Re: RCU consistency guarantees

Re: RCU consistency guarantees

[Mathieu Desnoyers]

[-- Attachment #1.1: Type: text/plain, Size: 1662 bytes --]

----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren <ryx@gwmail.gwu.edu> wrote: 

> Hi,
> I am a student, and learning RCU now, but still know very little about it.
> Are there any documents/papers/materials which (in)formally define and explain
> RCU consistency guarantees?

You may want to have a look at 

User-Level Implementations of Read-Copy Update 
Article in IEEE Transactions on Parallel and Distributed Systems 23(2):375 - 382 · March 2012 

as a starting point. 

Thanks, 

Mathieu 

> I know there are some consistency models in the database area (such as PRAM,
> Read Uncommitted, etc) from [ https://jepsen.io/consistency |
> https://jepsen.io/consistency ] and [1].
> How does RCU related to those consistency models?

> I also found some comments online (One key distinction is that both MVCC and RLU
> provide much stronger consistency guarantees to readers than does RCU ...) ( [
> https://lwn.net/Articles/777036/ | https://lwn.net/Articles/777036/ ] ).
> I do not understand how we reason/dresibe/compare the consistency guarantees. (
> I even do not know what consistency guarantees provided by RCU formally)
> Could someone explain this to me?

> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M., &
> Stoica, I. (2013). Highly available transactions: Virtues and limitations.
> Proceedings of the VLDB Endowment, 7(3), 181-192.

> Thanks
> Yuxin

> _______________________________________________
> lttng-dev mailing list
> lttng-dev@lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

-- 
Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 

[-- Attachment #1.2: Type: text/html, Size: 3173 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Yuxin Ren]

[-- Attachment #1.1: Type: text/plain, Size: 2079 bytes --]

On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers <
mathieu.desnoyers@efficios.com> wrote:

>
> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren <ryx@gwmail.gwu.edu> wrote:
>
> Hi,
> I am a student, and learning RCU now, but still know very little about it.
> Are there any documents/papers/materials which (in)formally define and
> explain RCU consistency guarantees?
>
>
> You may want to have a look at
>
> User-Level Implementations of Read-Copy Update
> Article in IEEE Transactions on Parallel and Distributed Systems 23(2):375
> - 382 · March 2012
>

Thanks for your info.
However, I do not think URCU talks about any consistency model formally.

From previous communication with Paul, he said RCU is not
designed for linearizability, and it is totally acceptable that RCU is
not linearizable.
However, I am curious how to accurately/formally Characterize RCU
consistency model/guarantees

>
> as a starting point.
>
> Thanks,
>
> Mathieu
>
>
> I know there are some consistency models in the database area (such as
> PRAM, Read Uncommitted, etc) from https://jepsen.io/consistency and [1].
> How does RCU related to those consistency models?
>
> I also found some comments online (One key distinction is that both MVCC
> and RLU provide much stronger consistency guarantees to readers than does
> RCU ...) (https://lwn.net/Articles/777036/).
> I do not understand how we reason/dresibe/compare the
> consistency guarantees. ( I even do not know what consistency guarantees
> provided by RCU formally)
> Could someone explain this to me?
>
>
>
> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M.,
> & Stoica, I. (2013). Highly available transactions: Virtues and
> limitations. Proceedings of the VLDB Endowment, 7(3), 181-192.
>
> Thanks
> Yuxin
>
> _______________________________________________
> lttng-dev mailing list
> lttng-dev@lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
>

[-- Attachment #1.2: Type: text/html, Size: 4382 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Mathieu Desnoyers]

[-- Attachment #1.1: Type: text/plain, Size: 2818 bytes --]

----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu> wrote: 

> On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> mailto:mathieu.desnoyers@efficios.com | mathieu.desnoyers@efficios.com ] >
> wrote:

>> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:ryx@gwmail.gwu.edu |
>> ryx@gwmail.gwu.edu ] > wrote:

>>> Hi,
>>> I am a student, and learning RCU now, but still know very little about it.
>>> Are there any documents/papers/materials which (in)formally define and explain
>>> RCU consistency guarantees?

>> You may want to have a look at

>> User-Level Implementations of Read-Copy Update
>> Article in IEEE Transactions on Parallel and Distributed Systems 23(2):375 - 382
>> · March 2012

> Thanks for your info.
> However, I do not think URCU talks about any consistency model formally.

> From previous communication with Paul, he said RCU is not designed for
> linearizability, and it is totally acceptable that RCU is not linearizable.
> However, I am curious how to accurately/formally Characterize RCU consistency
> model/guarantees

Adding Paul E. McKenney in CC. 

I am referring to the section "Overview of RCU semantics" in the paper. Not sure it has the level of 
formality you are looking for though. Paul, do you have pointers to additional material ? 

Thanks, 

Mathieu 

>> as a starting point.

>> Thanks,

>> Mathieu

>>> I know there are some consistency models in the database area (such as PRAM,
>>> Read Uncommitted, etc) from [ https://jepsen.io/consistency |
>>> https://jepsen.io/consistency ] and [1].
>>> How does RCU related to those consistency models?

>>> I also found some comments online (One key distinction is that both MVCC and RLU
>>> provide much stronger consistency guarantees to readers than does RCU ...) ( [
>>> https://lwn.net/Articles/777036/ | https://lwn.net/Articles/777036/ ] ).
>>> I do not understand how we reason/dresibe/compare the consistency guarantees. (
>>> I even do not know what consistency guarantees provided by RCU formally)
>>> Could someone explain this to me?

>>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M., &
>>> Stoica, I. (2013). Highly available transactions: Virtues and limitations.
>>> Proceedings of the VLDB Endowment, 7(3), 181-192.

>>> Thanks
>>> Yuxin

>>> _______________________________________________
>>> lttng-dev mailing list
>>> [ mailto:lttng-dev@lists.lttng.org | lttng-dev@lists.lttng.org ]
>>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
>>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]

>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> [ http://www.efficios.com/ | http://www.efficios.com ]

-- 
Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 

[-- Attachment #1.2: Type: text/html, Size: 6240 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Paul E. McKenney]

On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:
> ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu> wrote: 
> 
> > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > mailto:mathieu.desnoyers@efficios.com | mathieu.desnoyers@efficios.com ] >
> > wrote:
> 
> >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:ryx@gwmail.gwu.edu |
> >> ryx@gwmail.gwu.edu ] > wrote:
> 
> >>> Hi,
> >>> I am a student, and learning RCU now, but still know very little about it.
> >>> Are there any documents/papers/materials which (in)formally define and explain
> >>> RCU consistency guarantees?
> 
> >> You may want to have a look at
> 
> >> User-Level Implementations of Read-Copy Update
> >> Article in IEEE Transactions on Parallel and Distributed Systems 23(2):375 - 382
> >> · March 2012
> 
> > Thanks for your info.
> > However, I do not think URCU talks about any consistency model formally.
> 
> > From previous communication with Paul, he said RCU is not designed for
> > linearizability, and it is totally acceptable that RCU is not linearizable.
> > However, I am curious how to accurately/formally Characterize RCU consistency
> > model/guarantees
> 
> Adding Paul E. McKenney in CC. 
> 
> I am referring to the section "Overview of RCU semantics" in the paper. Not sure it has the level of 
> formality you are looking for though. Paul, do you have pointers to additional material ? 

Indeed I do!  The Linux kernel memory model (LKMM) includes RCU.  It is
in tools/memory-model in recent kernel source trees, which includes
documentation.  This is an executable model, which means that you
can create litmus tests and have the model formally and automatically
evaluate them.

There are also a number of publications covering LKMM:

o	A formal kernel memory-ordering model
	https://lwn.net/Articles/718628/
	https://lwn.net/Articles/720550/

	These cover the release stores and dependency ordering that
	provide RCU's publish-subscribe guarantees.

	Backup material here:

	https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/

	With these two likely being of particular interest:

	https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
	https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html

o	Frightening Small Children and Disconcerting Grown-ups: Concurrency in the Linux Kernel
	https://dl.acm.org/citation.cfm?id=3177156
	http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf

	Backup material:

	http://diy.inria.fr/linux/

o	Who's afraid of a big bad optimizing compiler?
	https://lwn.net/Articles/793253/

o	Calibrating your fear of big bad optimizing compilers
	https://lwn.net/Articles/799218/

	These last two justify use of normal C-language assignment
	statements to initialize and access data referenced by
	RCU-protected pointers.

There is a large body of litmus tests (thousands of them) here:

	https://github.com/paulmckrcu/litmus

Many of these litmus tests involve RCU, and these can be located by
search for files containing rcu_read_lock(), rcu_read_unlock(),
synchronize_rcu(), and so on.

Or were you looking for something else?

							Thanx, Paul

> Thanks, 
> 
> Mathieu 
> 
> >> as a starting point.
> 
> >> Thanks,
> 
> >> Mathieu
> 
> >>> I know there are some consistency models in the database area (such as PRAM,
> >>> Read Uncommitted, etc) from [ https://jepsen.io/consistency |
> >>> https://jepsen.io/consistency ] and [1].
> >>> How does RCU related to those consistency models?
> 
> >>> I also found some comments online (One key distinction is that both MVCC and RLU
> >>> provide much stronger consistency guarantees to readers than does RCU ...) ( [
> >>> https://lwn.net/Articles/777036/ | https://lwn.net/Articles/777036/ ] ).
> >>> I do not understand how we reason/dresibe/compare the consistency guarantees. (
> >>> I even do not know what consistency guarantees provided by RCU formally)
> >>> Could someone explain this to me?
> 
> >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M., &
> >>> Stoica, I. (2013). Highly available transactions: Virtues and limitations.
> >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> 
> >>> Thanks
> >>> Yuxin
> 
> >>> _______________________________________________
> >>> lttng-dev mailing list
> >>> [ mailto:lttng-dev@lists.lttng.org | lttng-dev@lists.lttng.org ]
> >>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> 
> >> --
> >> Mathieu Desnoyers
> >> EfficiOS Inc.
> >> [ http://www.efficios.com/ | http://www.efficios.com ]
> 
> -- 
> Mathieu Desnoyers 
> EfficiOS Inc. 
> http://www.efficios.com 

Re: RCU consistency guarantees

[Yuxin Ren]

[-- Attachment #1.1: Type: text/plain, Size: 5997 bytes --]

Thanks so much for your great help.
I definitely will look at those resources and papers!

One more thing that I am confused
As I mentioned earlier, someone said One key distinction is that both MVCC
and RLU provide much stronger consistency guarantees to readers than does
RCU ...) (https://lwn.net/Articles/777036/).
I am not sure if the above statement is correct or not. But in general,
How can we compare RCU consistency guarantees to other techniques (such as
RLU)?
How to reason about which one has stronger or weaker guarantees?

Thanks
Yuxin

On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <paulmck@kernel.org> wrote:

> On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:
> > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu> wrote:
> >
> > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > mailto:mathieu.desnoyers@efficios.com | mathieu.desnoyers@efficios.com
> ] >
> > > wrote:
> >
> > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> ryx@gwmail.gwu.edu |
> > >> ryx@gwmail.gwu.edu ] > wrote:
> >
> > >>> Hi,
> > >>> I am a student, and learning RCU now, but still know very little
> about it.
> > >>> Are there any documents/papers/materials which (in)formally define
> and explain
> > >>> RCU consistency guarantees?
> >
> > >> You may want to have a look at
> >
> > >> User-Level Implementations of Read-Copy Update
> > >> Article in IEEE Transactions on Parallel and Distributed Systems
> 23(2):375 - 382
> > >> · March 2012
> >
> > > Thanks for your info.
> > > However, I do not think URCU talks about any consistency model
> formally.
> >
> > > From previous communication with Paul, he said RCU is not designed for
> > > linearizability, and it is totally acceptable that RCU is not
> linearizable.
> > > However, I am curious how to accurately/formally Characterize RCU
> consistency
> > > model/guarantees
> >
> > Adding Paul E. McKenney in CC.
> >
> > I am referring to the section "Overview of RCU semantics" in the paper.
> Not sure it has the level of
> > formality you are looking for though. Paul, do you have pointers to
> additional material ?
>
> Indeed I do!  The Linux kernel memory model (LKMM) includes RCU.  It is
> in tools/memory-model in recent kernel source trees, which includes
> documentation.  This is an executable model, which means that you
> can create litmus tests and have the model formally and automatically
> evaluate them.
>
> There are also a number of publications covering LKMM:
>
> o       A formal kernel memory-ordering model
>         https://lwn.net/Articles/718628/
>         https://lwn.net/Articles/720550/
>
>         These cover the release stores and dependency ordering that
>         provide RCU's publish-subscribe guarantees.
>
>         Backup material here:
>
>
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
>
>         With these two likely being of particular interest:
>
>
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
>
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
>
> o       Frightening Small Children and Disconcerting Grown-ups:
> Concurrency in the Linux Kernel
>         https://dl.acm.org/citation.cfm?id=3177156
>         http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
>
>         Backup material:
>
>         http://diy.inria.fr/linux/
>
> o       Who's afraid of a big bad optimizing compiler?
>         https://lwn.net/Articles/793253/
>
> o       Calibrating your fear of big bad optimizing compilers
>         https://lwn.net/Articles/799218/
>
>         These last two justify use of normal C-language assignment
>         statements to initialize and access data referenced by
>         RCU-protected pointers.
>
> There is a large body of litmus tests (thousands of them) here:
>
>         https://github.com/paulmckrcu/litmus
>
> Many of these litmus tests involve RCU, and these can be located by
> search for files containing rcu_read_lock(), rcu_read_unlock(),
> synchronize_rcu(), and so on.
>
> Or were you looking for something else?
>
>                                                         Thanx, Paul
>
> > Thanks,
> >
> > Mathieu
> >
> > >> as a starting point.
> >
> > >> Thanks,
> >
> > >> Mathieu
> >
> > >>> I know there are some consistency models in the database area (such
> as PRAM,
> > >>> Read Uncommitted, etc) from [ https://jepsen.io/consistency |
> > >>> https://jepsen.io/consistency ] and [1].
> > >>> How does RCU related to those consistency models?
> >
> > >>> I also found some comments online (One key distinction is that both
> MVCC and RLU
> > >>> provide much stronger consistency guarantees to readers than does
> RCU ...) ( [
> > >>> https://lwn.net/Articles/777036/ | https://lwn.net/Articles/777036/
> ] ).
> > >>> I do not understand how we reason/dresibe/compare the consistency
> guarantees. (
> > >>> I even do not know what consistency guarantees provided by RCU
> formally)
> > >>> Could someone explain this to me?
> >
> > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein,
> J. M., &
> > >>> Stoica, I. (2013). Highly available transactions: Virtues and
> limitations.
> > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> >
> > >>> Thanks
> > >>> Yuxin
> >
> > >>> _______________________________________________
> > >>> lttng-dev mailing list
> > >>> [ mailto:lttng-dev@lists.lttng.org | lttng-dev@lists.lttng.org ]
> > >>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
> > >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> >
> > >> --
> > >> Mathieu Desnoyers
> > >> EfficiOS Inc.
> > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> >
> > --
> > Mathieu Desnoyers
> > EfficiOS Inc.
> > http://www.efficios.com
>

[-- Attachment #1.2: Type: text/html, Size: 9646 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Paul E. McKenney]

On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:
> Thanks so much for your great help.
> I definitely will look at those resources and papers!
> 
> One more thing that I am confused
> As I mentioned earlier, someone said One key distinction is that both MVCC
> and RLU provide much stronger consistency guarantees to readers than does
> RCU ...) (https://lwn.net/Articles/777036/).

That someone was in fact me.  ;-)

> I am not sure if the above statement is correct or not. But in general,
> How can we compare RCU consistency guarantees to other techniques (such as
> RLU)?
> How to reason about which one has stronger or weaker guarantees?

I suggest starting from the use case.  For concreteness, let's assume
that we are using a hash table.  At one extreme, imagine a use case in
which each event makes exactly one hash-table operation.  No information
is carried from one event to the next.  (This might well be the case
for simple web server.)  Such a use case cannot tell the difference
between RCU on the one hand and MVCC/RLU on the other.

At the other extreme, suppose that each event either accesses or updates
multiple entries in the hash table.  In this case, MVCC/RLU will rule
out outcomes that RCU would permit.  For example, suppose we had four
events accessing two different elements in different buckets of the
hash table:

	E1: Adds 32 to the hash table.
	E2: Adds 1729 to the hash table.
	E3: Within a read-side critical section, looks up 32 then 1729.
	E4: Within a read-side critical section, looks up 1729 then 32.

Given either MVCC or RLU, it will not be possible for E3 to find 32 but
not 1729 and at the same time for E4 to find 1729 but not 32.  Given RCU,
this outcome is possible.

This is because MVCC and RLU provide readers a consistent view of
the updates, and RCU does not.  Of course, it is often the case that a
consistent view is not needed, in which case the MVCC and RLU guarantees
are incurring read-side overhead for no reason.  But if the use case
requires consistent readers, RCU is not an option.

The reason a consistent view is not always needed is that speed-of-light
delays make it impossible to provide a consistent view of the outside
world.  In the common case where the use case interacts with the
outside world, the algorithms absolutely must be designed to tolerate
inconsistency, which opens the door to things like RCU.

							Thanx, Paul

> Thanks
> Yuxin
> 
> On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> 
> > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:
> > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu> wrote:
> > >
> > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > mailto:mathieu.desnoyers@efficios.com | mathieu.desnoyers@efficios.com
> > ] >
> > > > wrote:
> > >
> > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > ryx@gwmail.gwu.edu |
> > > >> ryx@gwmail.gwu.edu ] > wrote:
> > >
> > > >>> Hi,
> > > >>> I am a student, and learning RCU now, but still know very little
> > about it.
> > > >>> Are there any documents/papers/materials which (in)formally define
> > and explain
> > > >>> RCU consistency guarantees?
> > >
> > > >> You may want to have a look at
> > >
> > > >> User-Level Implementations of Read-Copy Update
> > > >> Article in IEEE Transactions on Parallel and Distributed Systems
> > 23(2):375 - 382
> > > >> · March 2012
> > >
> > > > Thanks for your info.
> > > > However, I do not think URCU talks about any consistency model
> > formally.
> > >
> > > > From previous communication with Paul, he said RCU is not designed for
> > > > linearizability, and it is totally acceptable that RCU is not
> > linearizable.
> > > > However, I am curious how to accurately/formally Characterize RCU
> > consistency
> > > > model/guarantees
> > >
> > > Adding Paul E. McKenney in CC.
> > >
> > > I am referring to the section "Overview of RCU semantics" in the paper.
> > Not sure it has the level of
> > > formality you are looking for though. Paul, do you have pointers to
> > additional material ?
> >
> > Indeed I do!  The Linux kernel memory model (LKMM) includes RCU.  It is
> > in tools/memory-model in recent kernel source trees, which includes
> > documentation.  This is an executable model, which means that you
> > can create litmus tests and have the model formally and automatically
> > evaluate them.
> >
> > There are also a number of publications covering LKMM:
> >
> > o       A formal kernel memory-ordering model
> >         https://lwn.net/Articles/718628/
> >         https://lwn.net/Articles/720550/
> >
> >         These cover the release stores and dependency ordering that
> >         provide RCU's publish-subscribe guarantees.
> >
> >         Backup material here:
> >
> >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> >
> >         With these two likely being of particular interest:
> >
> >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
> >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
> >
> > o       Frightening Small Children and Disconcerting Grown-ups:
> > Concurrency in the Linux Kernel
> >         https://dl.acm.org/citation.cfm?id=3177156
> >         http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> >
> >         Backup material:
> >
> >         http://diy.inria.fr/linux/
> >
> > o       Who's afraid of a big bad optimizing compiler?
> >         https://lwn.net/Articles/793253/
> >
> > o       Calibrating your fear of big bad optimizing compilers
> >         https://lwn.net/Articles/799218/
> >
> >         These last two justify use of normal C-language assignment
> >         statements to initialize and access data referenced by
> >         RCU-protected pointers.
> >
> > There is a large body of litmus tests (thousands of them) here:
> >
> >         https://github.com/paulmckrcu/litmus
> >
> > Many of these litmus tests involve RCU, and these can be located by
> > search for files containing rcu_read_lock(), rcu_read_unlock(),
> > synchronize_rcu(), and so on.
> >
> > Or were you looking for something else?
> >
> >                                                         Thanx, Paul
> >
> > > Thanks,
> > >
> > > Mathieu
> > >
> > > >> as a starting point.
> > >
> > > >> Thanks,
> > >
> > > >> Mathieu
> > >
> > > >>> I know there are some consistency models in the database area (such
> > as PRAM,
> > > >>> Read Uncommitted, etc) from [ https://jepsen.io/consistency |
> > > >>> https://jepsen.io/consistency ] and [1].
> > > >>> How does RCU related to those consistency models?
> > >
> > > >>> I also found some comments online (One key distinction is that both
> > MVCC and RLU
> > > >>> provide much stronger consistency guarantees to readers than does
> > RCU ...) ( [
> > > >>> https://lwn.net/Articles/777036/ | https://lwn.net/Articles/777036/
> > ] ).
> > > >>> I do not understand how we reason/dresibe/compare the consistency
> > guarantees. (
> > > >>> I even do not know what consistency guarantees provided by RCU
> > formally)
> > > >>> Could someone explain this to me?
> > >
> > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein,
> > J. M., &
> > > >>> Stoica, I. (2013). Highly available transactions: Virtues and
> > limitations.
> > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> > >
> > > >>> Thanks
> > > >>> Yuxin
> > >
> > > >>> _______________________________________________
> > > >>> lttng-dev mailing list
> > > >>> [ mailto:lttng-dev@lists.lttng.org | lttng-dev@lists.lttng.org ]
> > > >>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
> > > >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> > >
> > > >> --
> > > >> Mathieu Desnoyers
> > > >> EfficiOS Inc.
> > > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> > >
> > > --
> > > Mathieu Desnoyers
> > > EfficiOS Inc.
> > > http://www.efficios.com
> >

Re: RCU consistency guarantees

[Yuxin Ren]

[-- Attachment #1.1: Type: text/plain, Size: 9618 bytes --]

Thanks a lot for your help. I have some questions below.

On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <paulmck@kernel.org> wrote:

> On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:
> > Thanks so much for your great help.
> > I definitely will look at those resources and papers!
> >
> > One more thing that I am confused
> > As I mentioned earlier, someone said One key distinction is that both
> MVCC
> > and RLU provide much stronger consistency guarantees to readers than does
> > RCU ...) (https://lwn.net/Articles/777036/).
>
> That someone was in fact me.  ;-)
>
> > I am not sure if the above statement is correct or not. But in general,
> > How can we compare RCU consistency guarantees to other techniques (such
> as
> > RLU)?
> > How to reason about which one has stronger or weaker guarantees?
>
> I suggest starting from the use case.  For concreteness, let's assume
> that we are using a hash table.  At one extreme, imagine a use case in
> which each event makes exactly one hash-table operation.  No information
> is carried from one event to the next.  (This might well be the case
> for simple web server.)  Such a use case cannot tell the difference
> between RCU on the one hand and MVCC/RLU on the other.
>
> At the other extreme, suppose that each event either accesses or updates
> multiple entries in the hash table.  In this case, MVCC/RLU will rule
> out outcomes that RCU would permit.  For example, suppose we had four
> events accessing two different elements in different buckets of the
> hash table:
>
>         E1: Adds 32 to the hash table.
>         E2: Adds 1729 to the hash table.
>         E3: Within a read-side critical section, looks up 32 then 1729.
>         E4: Within a read-side critical section, looks up 1729 then 32.
>
> Given either MVCC or RLU, it will not be possible for E3 to find 32 but
> not 1729 and at the same time for E4 to find 1729 but not 32.  Given RCU,
> this outcome is possible.
>
When you say "Within a read-side section", do you mean within a single same
read section? such as

> read_lock()
> lookup(32)
> lookup(1729)
> read_unlock()


How about putting two lookups into two read-side sections? Do we still have
the problem, then?

> read_lock()
> lookup(32)
> read_unlock()
> read_lock()
> lookup(1729)
> read_unlock()


Could you kindly give me more clues why RCU can see such reorder, while RLU
can prevent it?


> This is because MVCC and RLU provide readers a consistent view of
> the updates, and RCU does not.  Of course, it is often the case that a
> consistent view is not needed, in which case the MVCC and RLU guarantees
> are incurring read-side overhead for no reason.  But if the use case
> requires consistent readers, RCU is not an option.
>
> The reason a consistent view is not always needed is that speed-of-light
> delays make it impossible to provide a consistent view of the outside
> world.  In the common case where the use case interacts with the
> outside world, the algorithms absolutely must be designed to tolerate
> inconsistency, which opens the door to things like RCU.
>

I am confused here. I think speed-of-light delays happen everywhere, not
only bound to RCU, but also  any other synchronization approach (such RLU).
If so, how do others (RLU) provide consistent views?

Thanks for your education.
Yuxin

>
>                                                         Thanx, Paul
>
> > Thanks
> > Yuxin
> >
> > On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <paulmck@kernel.org>
> wrote:
> >
> > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:
> > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu>
> wrote:
> > > >
> > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > mailto:mathieu.desnoyers@efficios.com |
> mathieu.desnoyers@efficios.com
> > > ] >
> > > > > wrote:
> > > >
> > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > ryx@gwmail.gwu.edu |
> > > > >> ryx@gwmail.gwu.edu ] > wrote:
> > > >
> > > > >>> Hi,
> > > > >>> I am a student, and learning RCU now, but still know very little
> > > about it.
> > > > >>> Are there any documents/papers/materials which (in)formally
> define
> > > and explain
> > > > >>> RCU consistency guarantees?
> > > >
> > > > >> You may want to have a look at
> > > >
> > > > >> User-Level Implementations of Read-Copy Update
> > > > >> Article in IEEE Transactions on Parallel and Distributed Systems
> > > 23(2):375 - 382
> > > > >> · March 2012
> > > >
> > > > > Thanks for your info.
> > > > > However, I do not think URCU talks about any consistency model
> > > formally.
> > > >
> > > > > From previous communication with Paul, he said RCU is not designed
> for
> > > > > linearizability, and it is totally acceptable that RCU is not
> > > linearizable.
> > > > > However, I am curious how to accurately/formally Characterize RCU
> > > consistency
> > > > > model/guarantees
> > > >
> > > > Adding Paul E. McKenney in CC.
> > > >
> > > > I am referring to the section "Overview of RCU semantics" in the
> paper.
> > > Not sure it has the level of
> > > > formality you are looking for though. Paul, do you have pointers to
> > > additional material ?
> > >
> > > Indeed I do!  The Linux kernel memory model (LKMM) includes RCU.  It is
> > > in tools/memory-model in recent kernel source trees, which includes
> > > documentation.  This is an executable model, which means that you
> > > can create litmus tests and have the model formally and automatically
> > > evaluate them.
> > >
> > > There are also a number of publications covering LKMM:
> > >
> > > o       A formal kernel memory-ordering model
> > >         https://lwn.net/Articles/718628/
> > >         https://lwn.net/Articles/720550/
> > >
> > >         These cover the release stores and dependency ordering that
> > >         provide RCU's publish-subscribe guarantees.
> > >
> > >         Backup material here:
> > >
> > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> > >
> > >         With these two likely being of particular interest:
> > >
> > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
> > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
> > >
> > > o       Frightening Small Children and Disconcerting Grown-ups:
> > > Concurrency in the Linux Kernel
> > >         https://dl.acm.org/citation.cfm?id=3177156
> > >         http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> > >
> > >         Backup material:
> > >
> > >         http://diy.inria.fr/linux/
> > >
> > > o       Who's afraid of a big bad optimizing compiler?
> > >         https://lwn.net/Articles/793253/
> > >
> > > o       Calibrating your fear of big bad optimizing compilers
> > >         https://lwn.net/Articles/799218/
> > >
> > >         These last two justify use of normal C-language assignment
> > >         statements to initialize and access data referenced by
> > >         RCU-protected pointers.
> > >
> > > There is a large body of litmus tests (thousands of them) here:
> > >
> > >         https://github.com/paulmckrcu/litmus
> > >
> > > Many of these litmus tests involve RCU, and these can be located by
> > > search for files containing rcu_read_lock(), rcu_read_unlock(),
> > > synchronize_rcu(), and so on.
> > >
> > > Or were you looking for something else?
> > >
> > >                                                         Thanx, Paul
> > >
> > > > Thanks,
> > > >
> > > > Mathieu
> > > >
> > > > >> as a starting point.
> > > >
> > > > >> Thanks,
> > > >
> > > > >> Mathieu
> > > >
> > > > >>> I know there are some consistency models in the database area
> (such
> > > as PRAM,
> > > > >>> Read Uncommitted, etc) from [ https://jepsen.io/consistency |
> > > > >>> https://jepsen.io/consistency ] and [1].
> > > > >>> How does RCU related to those consistency models?
> > > >
> > > > >>> I also found some comments online (One key distinction is that
> both
> > > MVCC and RLU
> > > > >>> provide much stronger consistency guarantees to readers than does
> > > RCU ...) ( [
> > > > >>> https://lwn.net/Articles/777036/ |
> https://lwn.net/Articles/777036/
> > > ] ).
> > > > >>> I do not understand how we reason/dresibe/compare the consistency
> > > guarantees. (
> > > > >>> I even do not know what consistency guarantees provided by RCU
> > > formally)
> > > > >>> Could someone explain this to me?
> > > >
> > > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A.,
> Hellerstein,
> > > J. M., &
> > > > >>> Stoica, I. (2013). Highly available transactions: Virtues and
> > > limitations.
> > > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> > > >
> > > > >>> Thanks
> > > > >>> Yuxin
> > > >
> > > > >>> _______________________________________________
> > > > >>> lttng-dev mailing list
> > > > >>> [ mailto:lttng-dev@lists.lttng.org | lttng-dev@lists.lttng.org ]
> > > > >>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
> > > > >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> > > >
> > > > >> --
> > > > >> Mathieu Desnoyers
> > > > >> EfficiOS Inc.
> > > > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> > > >
> > > > --
> > > > Mathieu Desnoyers
> > > > EfficiOS Inc.
> > > > http://www.efficios.com
> > >
>

[-- Attachment #1.2: Type: text/html, Size: 15089 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Paul E. McKenney]

On Sat, Dec 07, 2019 at 03:04:42PM -0500, Yuxin Ren wrote:
> Thanks a lot for your help. I have some questions below.
> 
> On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> 
> > On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:
> > > Thanks so much for your great help.
> > > I definitely will look at those resources and papers!
> > >
> > > One more thing that I am confused
> > > As I mentioned earlier, someone said One key distinction is that both
> > MVCC
> > > and RLU provide much stronger consistency guarantees to readers than does
> > > RCU ...) (https://lwn.net/Articles/777036/).
> >
> > That someone was in fact me.  ;-)
> >
> > > I am not sure if the above statement is correct or not. But in general,
> > > How can we compare RCU consistency guarantees to other techniques (such
> > as
> > > RLU)?
> > > How to reason about which one has stronger or weaker guarantees?
> >
> > I suggest starting from the use case.  For concreteness, let's assume
> > that we are using a hash table.  At one extreme, imagine a use case in
> > which each event makes exactly one hash-table operation.  No information
> > is carried from one event to the next.  (This might well be the case
> > for simple web server.)  Such a use case cannot tell the difference
> > between RCU on the one hand and MVCC/RLU on the other.
> >
> > At the other extreme, suppose that each event either accesses or updates
> > multiple entries in the hash table.  In this case, MVCC/RLU will rule
> > out outcomes that RCU would permit.  For example, suppose we had four
> > events accessing two different elements in different buckets of the
> > hash table:
> >
> >         E1: Adds 32 to the hash table.
> >         E2: Adds 1729 to the hash table.
> >         E3: Within a read-side critical section, looks up 32 then 1729.
> >         E4: Within a read-side critical section, looks up 1729 then 32.
> >
> > Given either MVCC or RLU, it will not be possible for E3 to find 32 but
> > not 1729 and at the same time for E4 to find 1729 but not 32.  Given RCU,
> > this outcome is possible.
> >
> When you say "Within a read-side section", do you mean within a single same
> read section? such as
> 
> > read_lock()
> > lookup(32)
> > lookup(1729)
> > read_unlock()
> 
> 
> How about putting two lookups into two read-side sections? Do we still have
> the problem, then?
> 
> > read_lock()
> > lookup(32)
> > read_unlock()
> > read_lock()
> > lookup(1729)
> > read_unlock()

Without in any way agreeing with your characterization of this as a
problem, because rcu_read_lock() and rcu_read_unlock() provide
absolutely no ordering guarantees in the absence of a grace period,
any non-grace-period-related reordering that can happen with a single
RCU read-side critical section can also happen when that critical
section is split in two as you have done above.

> Could you kindly give me more clues why RCU can see such reorder, while RLU
> can prevent it?

Here are minimal C-language implementations for RCU that can (and are)
actually used:

#define rcu_read_lock()
#define rcu_read_unlock()

Please compare these to the read-side markers presented in the RLU paper,
and then tell me your thoughts on the answer to your question.  ;-)

> > This is because MVCC and RLU provide readers a consistent view of
> > the updates, and RCU does not.  Of course, it is often the case that a
> > consistent view is not needed, in which case the MVCC and RLU guarantees
> > are incurring read-side overhead for no reason.  But if the use case
> > requires consistent readers, RCU is not an option.
> >
> > The reason a consistent view is not always needed is that speed-of-light
> > delays make it impossible to provide a consistent view of the outside
> > world.  In the common case where the use case interacts with the
> > outside world, the algorithms absolutely must be designed to tolerate
> > inconsistency, which opens the door to things like RCU.
> 
> I am confused here. I think speed-of-light delays happen everywhere, not
> only bound to RCU, but also  any other synchronization approach (such RLU).
> If so, how do others (RLU) provide consistent views?

You just stated the answer.  Now it is only necessary for you to invest
the time, effort, and thought to fully understand it.  To help with this,
the following paragraph provides another hint:

	Yes, you are quite right, speed-of-light delays between the
	outside world and the computer affect RLU just as surely as they
	do RCU.  This means that the additional consistency guarantees
	provided by RLU must necessarily be limited to the confines of the
	computer system in question.  Taking this one step further, there
	are also speed-of-light delays within the computer.  Therefore,
	in the general case, RLU can provide its consistency guarantees,
	even within the confines of the computer system, only at the
	expense of incurring delays.  Because RCU does not provide RLU's
	consistency guarantees, it need not incur RLU's delays.

This is not a new line of reasoning, see for example:

@article{Herlihy:1996:LCN:1063369.1063372
,author = {Herlihy, Maurice and Shavit, Nir and Waarts, Orli}
,title = {Linearizable counting networks}
,journal = {Distrib. Comput.}
,volume = {9}
,issue = {4}
,month = {February}
,year = {1996}
,issn = {0178-2770}
,pages = {193--203}
,numpages = {11}
,url = {http://portal.acm.org/citation.cfm?id=1063369.1063372}
,doi = {10.1007/s004460050019}
,acmid = {1063372}
,publisher = {Springer-Verlag}
,address = {London, UK}
,keywords = {concurrency, contention, counting networks, data structures, linearizability}
}

							Thanx, Paul

> Thanks for your education.
> Yuxin
> 
> >
> >                                                         Thanx, Paul
> >
> > > Thanks
> > > Yuxin
> > >
> > > On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <paulmck@kernel.org>
> > wrote:
> > >
> > > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:
> > > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu>
> > wrote:
> > > > >
> > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > > mailto:mathieu.desnoyers@efficios.com |
> > mathieu.desnoyers@efficios.com
> > > > ] >
> > > > > > wrote:
> > > > >
> > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > > ryx@gwmail.gwu.edu |
> > > > > >> ryx@gwmail.gwu.edu ] > wrote:
> > > > >
> > > > > >>> Hi,
> > > > > >>> I am a student, and learning RCU now, but still know very little
> > > > about it.
> > > > > >>> Are there any documents/papers/materials which (in)formally
> > define
> > > > and explain
> > > > > >>> RCU consistency guarantees?
> > > > >
> > > > > >> You may want to have a look at
> > > > >
> > > > > >> User-Level Implementations of Read-Copy Update
> > > > > >> Article in IEEE Transactions on Parallel and Distributed Systems
> > > > 23(2):375 - 382
> > > > > >> · March 2012
> > > > >
> > > > > > Thanks for your info.
> > > > > > However, I do not think URCU talks about any consistency model
> > > > formally.
> > > > >
> > > > > > From previous communication with Paul, he said RCU is not designed
> > for
> > > > > > linearizability, and it is totally acceptable that RCU is not
> > > > linearizable.
> > > > > > However, I am curious how to accurately/formally Characterize RCU
> > > > consistency
> > > > > > model/guarantees
> > > > >
> > > > > Adding Paul E. McKenney in CC.
> > > > >
> > > > > I am referring to the section "Overview of RCU semantics" in the
> > paper.
> > > > Not sure it has the level of
> > > > > formality you are looking for though. Paul, do you have pointers to
> > > > additional material ?
> > > >
> > > > Indeed I do!  The Linux kernel memory model (LKMM) includes RCU.  It is
> > > > in tools/memory-model in recent kernel source trees, which includes
> > > > documentation.  This is an executable model, which means that you
> > > > can create litmus tests and have the model formally and automatically
> > > > evaluate them.
> > > >
> > > > There are also a number of publications covering LKMM:
> > > >
> > > > o       A formal kernel memory-ordering model
> > > >         https://lwn.net/Articles/718628/
> > > >         https://lwn.net/Articles/720550/
> > > >
> > > >         These cover the release stores and dependency ordering that
> > > >         provide RCU's publish-subscribe guarantees.
> > > >
> > > >         Backup material here:
> > > >
> > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> > > >
> > > >         With these two likely being of particular interest:
> > > >
> > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
> > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
> > > >
> > > > o       Frightening Small Children and Disconcerting Grown-ups:
> > > > Concurrency in the Linux Kernel
> > > >         https://dl.acm.org/citation.cfm?id=3177156
> > > >         http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> > > >
> > > >         Backup material:
> > > >
> > > >         http://diy.inria.fr/linux/
> > > >
> > > > o       Who's afraid of a big bad optimizing compiler?
> > > >         https://lwn.net/Articles/793253/
> > > >
> > > > o       Calibrating your fear of big bad optimizing compilers
> > > >         https://lwn.net/Articles/799218/
> > > >
> > > >         These last two justify use of normal C-language assignment
> > > >         statements to initialize and access data referenced by
> > > >         RCU-protected pointers.
> > > >
> > > > There is a large body of litmus tests (thousands of them) here:
> > > >
> > > >         https://github.com/paulmckrcu/litmus
> > > >
> > > > Many of these litmus tests involve RCU, and these can be located by
> > > > search for files containing rcu_read_lock(), rcu_read_unlock(),
> > > > synchronize_rcu(), and so on.
> > > >
> > > > Or were you looking for something else?
> > > >
> > > >                                                         Thanx, Paul
> > > >
> > > > > Thanks,
> > > > >
> > > > > Mathieu
> > > > >
> > > > > >> as a starting point.
> > > > >
> > > > > >> Thanks,
> > > > >
> > > > > >> Mathieu
> > > > >
> > > > > >>> I know there are some consistency models in the database area
> > (such
> > > > as PRAM,
> > > > > >>> Read Uncommitted, etc) from [ https://jepsen.io/consistency |
> > > > > >>> https://jepsen.io/consistency ] and [1].
> > > > > >>> How does RCU related to those consistency models?
> > > > >
> > > > > >>> I also found some comments online (One key distinction is that
> > both
> > > > MVCC and RLU
> > > > > >>> provide much stronger consistency guarantees to readers than does
> > > > RCU ...) ( [
> > > > > >>> https://lwn.net/Articles/777036/ |
> > https://lwn.net/Articles/777036/
> > > > ] ).
> > > > > >>> I do not understand how we reason/dresibe/compare the consistency
> > > > guarantees. (
> > > > > >>> I even do not know what consistency guarantees provided by RCU
> > > > formally)
> > > > > >>> Could someone explain this to me?
> > > > >
> > > > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A.,
> > Hellerstein,
> > > > J. M., &
> > > > > >>> Stoica, I. (2013). Highly available transactions: Virtues and
> > > > limitations.
> > > > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> > > > >
> > > > > >>> Thanks
> > > > > >>> Yuxin
> > > > >
> > > > > >>> _______________________________________________
> > > > > >>> lttng-dev mailing list
> > > > > >>> [ mailto:lttng-dev@lists.lttng.org | lttng-dev@lists.lttng.org ]
> > > > > >>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
> > > > > >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> > > > >
> > > > > >> --
> > > > > >> Mathieu Desnoyers
> > > > > >> EfficiOS Inc.
> > > > > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> > > > >
> > > > > --
> > > > > Mathieu Desnoyers
> > > > > EfficiOS Inc.
> > > > > http://www.efficios.com
> > > >
> >

Re: RCU consistency guarantees

[Yuxin Ren]

[-- Attachment #1.1: Type: text/plain, Size: 14972 bytes --]

Hi Paul

On Sat, Dec 7, 2019 at 5:42 PM Paul E. McKenney <paulmck@kernel.org> wrote:

> On Sat, Dec 07, 2019 at 03:04:42PM -0500, Yuxin Ren wrote:
> > Thanks a lot for your help. I have some questions below.
> >
> > On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <paulmck@kernel.org>
> wrote:
> >
> > > On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:
> > > > Thanks so much for your great help.
> > > > I definitely will look at those resources and papers!
> > > >
> > > > One more thing that I am confused
> > > > As I mentioned earlier, someone said One key distinction is that both
> > > MVCC
> > > > and RLU provide much stronger consistency guarantees to readers than
> does
> > > > RCU ...) (https://lwn.net/Articles/777036/).
> > >
> > > That someone was in fact me.  ;-)
> > >
> > > > I am not sure if the above statement is correct or not. But in
> general,
> > > > How can we compare RCU consistency guarantees to other techniques
> (such
> > > as
> > > > RLU)?
> > > > How to reason about which one has stronger or weaker guarantees?
> > >
> > > I suggest starting from the use case.  For concreteness, let's assume
> > > that we are using a hash table.  At one extreme, imagine a use case in
> > > which each event makes exactly one hash-table operation.  No
> information
> > > is carried from one event to the next.  (This might well be the case
> > > for simple web server.)  Such a use case cannot tell the difference
> > > between RCU on the one hand and MVCC/RLU on the other.
> > >
> > > At the other extreme, suppose that each event either accesses or
> updates
> > > multiple entries in the hash table.  In this case, MVCC/RLU will rule
> > > out outcomes that RCU would permit.  For example, suppose we had four
> > > events accessing two different elements in different buckets of the
> > > hash table:
> > >
> > >         E1: Adds 32 to the hash table.
> > >         E2: Adds 1729 to the hash table.
> > >         E3: Within a read-side critical section, looks up 32 then 1729.
> > >         E4: Within a read-side critical section, looks up 1729 then 32.
> > >
> > > Given either MVCC or RLU, it will not be possible for E3 to find 32 but
> > > not 1729 and at the same time for E4 to find 1729 but not 32.  Given
> RCU,
> > > this outcome is possible.
> > >
> > When you say "Within a read-side section", do you mean within a single
> same
> > read section? such as
> >
> > > read_lock()
> > > lookup(32)
> > > lookup(1729)
> > > read_unlock()
> >
> >
> > How about putting two lookups into two read-side sections? Do we still
> have
> > the problem, then?
> >
> > > read_lock()
> > > lookup(32)
> > > read_unlock()
> > > read_lock()
> > > lookup(1729)
> > > read_unlock()
>
> Without in any way agreeing with your characterization of this as a
> problem, because rcu_read_lock() and rcu_read_unlock() provide
> absolutely no ordering guarantees in the absence of a grace period,
> any non-grace-period-related reordering that can happen with a single
> RCU read-side critical section can also happen when that critical
> section is split in two as you have done above.
>
> > Could you kindly give me more clues why RCU can see such reorder, while
> RLU
> > can prevent it?
>
> Here are minimal C-language implementations for RCU that can (and are)
> actually used:
>
Great. We use the same thing in our real-time work [1]


> #define rcu_read_lock()
> #define rcu_read_unlock()
>
> Please compare these to the read-side markers presented in the RLU paper,
> and then tell me your thoughts on the answer to your question.  ;-)
>
I submit my homework here, but I do not think I did it well.
1. I believe in the default URCU implementation, it has memory barrier
inside the read_lock / read_unlock.
2. From the RLU paper, it shows the code for read-side operation.
RLU_READER_LOCK(ctx)
    ctx.is-writer←false
    ctx.run-cnt←ctx.run-cnt+1.
    memory fence
   ctx.local-clock←global-clock
RLU_READER_UNLOCK(ctx)
    ctx.run-cnt←ctx.run-cnt+1
    if (ctx.is-writer)
        RLU_COMMIT_WRITE_LOG(ctx)

We can ignore the writer check, as in our case, the reader never do update.
My understanding is that read-side operations are only used to facilitate
the quiescence detection.
the run cnt is used to decide if a thread is active (if it is currently
inside a read-side section).
the local clock is used to check if the active thread goes into the
read-side section very late, so it does not prevent reclaiming memory
unlinked before it enters the read section.
However i see no difference between RLU and RCU read-side operation
regarding consistency guarantee.
Could you kindly teach me more?

BTW, the RLU read-side ops are similar, but not efficient, comparing to our
Parsec work [1, 2]
[1] Yuxin Ren, G. Liu, G. Parmer, B. Brandenburg, Scalable Memory
Reclamation for Multi-Core, Real-Time Systems, in Proceedings of the 24th
IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS),
2018
[2] Q. Wang, T. Stamler, and G. Parmer, Parallel Sections: Scaling
System-Level Data-Structures, in Proceedings of European Conference on
Computer Systems (EuroSys), 2016

Thanks,
Best,
Yuxin


> > This is because MVCC and RLU provide readers a consistent view of
> > > the updates, and RCU does not.  Of course, it is often the case that a
> > > consistent view is not needed, in which case the MVCC and RLU
> guarantees
> > > are incurring read-side overhead for no reason.  But if the use case
> > > requires consistent readers, RCU is not an option.
> > >
> > > The reason a consistent view is not always needed is that
> speed-of-light
> > > delays make it impossible to provide a consistent view of the outside
> > > world.  In the common case where the use case interacts with the
> > > outside world, the algorithms absolutely must be designed to tolerate
> > > inconsistency, which opens the door to things like RCU.
> >
> > I am confused here. I think speed-of-light delays happen everywhere, not
> > only bound to RCU, but also  any other synchronization approach (such
> RLU).
> > If so, how do others (RLU) provide consistent views?
>
> You just stated the answer.  Now it is only necessary for you to invest
> the time, effort, and thought to fully understand it.  To help with this,
> the following paragraph provides another hint:
>
>         Yes, you are quite right, speed-of-light delays between the
>         outside world and the computer affect RLU just as surely as they
>         do RCU.  This means that the additional consistency guarantees
>         provided by RLU must necessarily be limited to the confines of the
>         computer system in question.  Taking this one step further, there
>         are also speed-of-light delays within the computer.  Therefore,
>         in the general case, RLU can provide its consistency guarantees,
>         even within the confines of the computer system, only at the
>         expense of incurring delays.  Because RCU does not provide RLU's
>         consistency guarantees, it need not incur RLU's delays.
>
> This is not a new line of reasoning, see for example:
>
> @article{Herlihy:1996:LCN:1063369.1063372
> ,author = {Herlihy, Maurice and Shavit, Nir and Waarts, Orli}
> ,title = {Linearizable counting networks}
> ,journal = {Distrib. Comput.}
> ,volume = {9}
> ,issue = {4}
> ,month = {February}
> ,year = {1996}
> ,issn = {0178-2770}
> ,pages = {193--203}
> ,numpages = {11}
> ,url = {http://portal.acm.org/citation.cfm?id=1063369.1063372}
> ,doi = {10.1007/s004460050019}
> ,acmid = {1063372}
> ,publisher = {Springer-Verlag}
> ,address = {London, UK}
> ,keywords = {concurrency, contention, counting networks, data structures,
> linearizability}
> }
>
>                                                         Thanx, Paul
>
> > Thanks for your education.
> > Yuxin
> >
> > >
> > >                                                         Thanx, Paul
> > >
> > > > Thanks
> > > > Yuxin
> > > >
> > > > On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <paulmck@kernel.org
> >
> > > wrote:
> > > >
> > > > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:
> > > > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu>
> > > wrote:
> > > > > >
> > > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > > > mailto:mathieu.desnoyers@efficios.com |
> > > mathieu.desnoyers@efficios.com
> > > > > ] >
> > > > > > > wrote:
> > > > > >
> > > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > > > ryx@gwmail.gwu.edu |
> > > > > > >> ryx@gwmail.gwu.edu ] > wrote:
> > > > > >
> > > > > > >>> Hi,
> > > > > > >>> I am a student, and learning RCU now, but still know very
> little
> > > > > about it.
> > > > > > >>> Are there any documents/papers/materials which (in)formally
> > > define
> > > > > and explain
> > > > > > >>> RCU consistency guarantees?
> > > > > >
> > > > > > >> You may want to have a look at
> > > > > >
> > > > > > >> User-Level Implementations of Read-Copy Update
> > > > > > >> Article in IEEE Transactions on Parallel and Distributed
> Systems
> > > > > 23(2):375 - 382
> > > > > > >> · March 2012
> > > > > >
> > > > > > > Thanks for your info.
> > > > > > > However, I do not think URCU talks about any consistency model
> > > > > formally.
> > > > > >
> > > > > > > From previous communication with Paul, he said RCU is not
> designed
> > > for
> > > > > > > linearizability, and it is totally acceptable that RCU is not
> > > > > linearizable.
> > > > > > > However, I am curious how to accurately/formally Characterize
> RCU
> > > > > consistency
> > > > > > > model/guarantees
> > > > > >
> > > > > > Adding Paul E. McKenney in CC.
> > > > > >
> > > > > > I am referring to the section "Overview of RCU semantics" in the
> > > paper.
> > > > > Not sure it has the level of
> > > > > > formality you are looking for though. Paul, do you have pointers
> to
> > > > > additional material ?
> > > > >
> > > > > Indeed I do!  The Linux kernel memory model (LKMM) includes RCU.
> It is
> > > > > in tools/memory-model in recent kernel source trees, which includes
> > > > > documentation.  This is an executable model, which means that you
> > > > > can create litmus tests and have the model formally and
> automatically
> > > > > evaluate them.
> > > > >
> > > > > There are also a number of publications covering LKMM:
> > > > >
> > > > > o       A formal kernel memory-ordering model
> > > > >         https://lwn.net/Articles/718628/
> > > > >         https://lwn.net/Articles/720550/
> > > > >
> > > > >         These cover the release stores and dependency ordering that
> > > > >         provide RCU's publish-subscribe guarantees.
> > > > >
> > > > >         Backup material here:
> > > > >
> > > > >
> > > > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> > > > >
> > > > >         With these two likely being of particular interest:
> > > > >
> > > > >
> > > > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
> > > > >
> > > > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
> > > > >
> > > > > o       Frightening Small Children and Disconcerting Grown-ups:
> > > > > Concurrency in the Linux Kernel
> > > > >         https://dl.acm.org/citation.cfm?id=3177156
> > > > >
> http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> > > > >
> > > > >         Backup material:
> > > > >
> > > > >         http://diy.inria.fr/linux/
> > > > >
> > > > > o       Who's afraid of a big bad optimizing compiler?
> > > > >         https://lwn.net/Articles/793253/
> > > > >
> > > > > o       Calibrating your fear of big bad optimizing compilers
> > > > >         https://lwn.net/Articles/799218/
> > > > >
> > > > >         These last two justify use of normal C-language assignment
> > > > >         statements to initialize and access data referenced by
> > > > >         RCU-protected pointers.
> > > > >
> > > > > There is a large body of litmus tests (thousands of them) here:
> > > > >
> > > > >         https://github.com/paulmckrcu/litmus
> > > > >
> > > > > Many of these litmus tests involve RCU, and these can be located by
> > > > > search for files containing rcu_read_lock(), rcu_read_unlock(),
> > > > > synchronize_rcu(), and so on.
> > > > >
> > > > > Or were you looking for something else?
> > > > >
> > > > >                                                         Thanx, Paul
> > > > >
> > > > > > Thanks,
> > > > > >
> > > > > > Mathieu
> > > > > >
> > > > > > >> as a starting point.
> > > > > >
> > > > > > >> Thanks,
> > > > > >
> > > > > > >> Mathieu
> > > > > >
> > > > > > >>> I know there are some consistency models in the database area
> > > (such
> > > > > as PRAM,
> > > > > > >>> Read Uncommitted, etc) from [ https://jepsen.io/consistency
> |
> > > > > > >>> https://jepsen.io/consistency ] and [1].
> > > > > > >>> How does RCU related to those consistency models?
> > > > > >
> > > > > > >>> I also found some comments online (One key distinction is
> that
> > > both
> > > > > MVCC and RLU
> > > > > > >>> provide much stronger consistency guarantees to readers than
> does
> > > > > RCU ...) ( [
> > > > > > >>> https://lwn.net/Articles/777036/ |
> > > https://lwn.net/Articles/777036/
> > > > > ] ).
> > > > > > >>> I do not understand how we reason/dresibe/compare the
> consistency
> > > > > guarantees. (
> > > > > > >>> I even do not know what consistency guarantees provided by
> RCU
> > > > > formally)
> > > > > > >>> Could someone explain this to me?
> > > > > >
> > > > > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A.,
> > > Hellerstein,
> > > > > J. M., &
> > > > > > >>> Stoica, I. (2013). Highly available transactions: Virtues and
> > > > > limitations.
> > > > > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> > > > > >
> > > > > > >>> Thanks
> > > > > > >>> Yuxin
> > > > > >
> > > > > > >>> _______________________________________________
> > > > > > >>> lttng-dev mailing list
> > > > > > >>> [ mailto:lttng-dev@lists.lttng.org |
> lttng-dev@lists.lttng.org ]
> > > > > > >>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> |
> > > > > > >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> > > > > >
> > > > > > >> --
> > > > > > >> Mathieu Desnoyers
> > > > > > >> EfficiOS Inc.
> > > > > > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> > > > > >
> > > > > > --
> > > > > > Mathieu Desnoyers
> > > > > > EfficiOS Inc.
> > > > > > http://www.efficios.com
> > > > >
> > >
>

[-- Attachment #1.2: Type: text/html, Size: 22321 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Paul E. McKenney]

On Sat, Dec 14, 2019 at 01:31:31AM -0500, Yuxin Ren wrote:
> Hi Paul
> 
> On Sat, Dec 7, 2019 at 5:42 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> 
> > On Sat, Dec 07, 2019 at 03:04:42PM -0500, Yuxin Ren wrote:
> > > Thanks a lot for your help. I have some questions below.
> > >
> > > On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <paulmck@kernel.org>
> > wrote:
> > >
> > > > On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:
> > > > > Thanks so much for your great help.
> > > > > I definitely will look at those resources and papers!
> > > > >
> > > > > One more thing that I am confused
> > > > > As I mentioned earlier, someone said One key distinction is that both
> > > > MVCC
> > > > > and RLU provide much stronger consistency guarantees to readers than
> > does
> > > > > RCU ...) (https://lwn.net/Articles/777036/).
> > > >
> > > > That someone was in fact me.  ;-)
> > > >
> > > > > I am not sure if the above statement is correct or not. But in
> > general,
> > > > > How can we compare RCU consistency guarantees to other techniques
> > (such
> > > > as
> > > > > RLU)?
> > > > > How to reason about which one has stronger or weaker guarantees?
> > > >
> > > > I suggest starting from the use case.  For concreteness, let's assume
> > > > that we are using a hash table.  At one extreme, imagine a use case in
> > > > which each event makes exactly one hash-table operation.  No
> > information
> > > > is carried from one event to the next.  (This might well be the case
> > > > for simple web server.)  Such a use case cannot tell the difference
> > > > between RCU on the one hand and MVCC/RLU on the other.
> > > >
> > > > At the other extreme, suppose that each event either accesses or
> > updates
> > > > multiple entries in the hash table.  In this case, MVCC/RLU will rule
> > > > out outcomes that RCU would permit.  For example, suppose we had four
> > > > events accessing two different elements in different buckets of the
> > > > hash table:
> > > >
> > > >         E1: Adds 32 to the hash table.
> > > >         E2: Adds 1729 to the hash table.
> > > >         E3: Within a read-side critical section, looks up 32 then 1729.
> > > >         E4: Within a read-side critical section, looks up 1729 then 32.
> > > >
> > > > Given either MVCC or RLU, it will not be possible for E3 to find 32 but
> > > > not 1729 and at the same time for E4 to find 1729 but not 32.  Given
> > RCU,
> > > > this outcome is possible.
> > > >
> > > When you say "Within a read-side section", do you mean within a single
> > same
> > > read section? such as
> > >
> > > > read_lock()
> > > > lookup(32)
> > > > lookup(1729)
> > > > read_unlock()
> > >
> > >
> > > How about putting two lookups into two read-side sections? Do we still
> > have
> > > the problem, then?
> > >
> > > > read_lock()
> > > > lookup(32)
> > > > read_unlock()
> > > > read_lock()
> > > > lookup(1729)
> > > > read_unlock()
> >
> > Without in any way agreeing with your characterization of this as a
> > problem, because rcu_read_lock() and rcu_read_unlock() provide
> > absolutely no ordering guarantees in the absence of a grace period,
> > any non-grace-period-related reordering that can happen with a single
> > RCU read-side critical section can also happen when that critical
> > section is split in two as you have done above.
> >
> > > Could you kindly give me more clues why RCU can see such reorder, while
> > RLU
> > > can prevent it?
> >
> > Here are minimal C-language implementations for RCU that can (and are)
> > actually used:
> >
> Great. We use the same thing in our real-time work [1]

It has been a popular choice for 40 years now.  ;-)

> > #define rcu_read_lock()
> > #define rcu_read_unlock()
> >
> > Please compare these to the read-side markers presented in the RLU paper,
> > and then tell me your thoughts on the answer to your question.  ;-)
> >
> I submit my homework here, but I do not think I did it well.
> 1. I believe in the default URCU implementation, it has memory barrier
> inside the read_lock / read_unlock.

It certainly was at one time.  But you would of course need to check
to see what any given worker actually used.

> 2. From the RLU paper, it shows the code for read-side operation.
> RLU_READER_LOCK(ctx)
>     ctx.is-writer←false
>     ctx.run-cnt←ctx.run-cnt+1.
>     memory fence
>    ctx.local-clock←global-clock
> RLU_READER_UNLOCK(ctx)
>     ctx.run-cnt←ctx.run-cnt+1
>     if (ctx.is-writer)
>         RLU_COMMIT_WRITE_LOG(ctx)
> 
> We can ignore the writer check, as in our case, the reader never do update.
> My understanding is that read-side operations are only used to facilitate
> the quiescence detection.
> the run cnt is used to decide if a thread is active (if it is currently
> inside a read-side section).
> the local clock is used to check if the active thread goes into the
> read-side section very late, so it does not prevent reclaiming memory
> unlinked before it enters the read section.
> However i see no difference between RLU and RCU read-side operation
> regarding consistency guarantee.
> Could you kindly teach me more?

In order to teach you more, I do need some help from you.  I have posted
a number of URLs earlier in this email thread.  Could you please tell
me what you learned from each of them?

								Thanx, Paul

> BTW, the RLU read-side ops are similar, but not efficient, comparing to our
> Parsec work [1, 2]
> [1] Yuxin Ren, G. Liu, G. Parmer, B. Brandenburg, Scalable Memory
> Reclamation for Multi-Core, Real-Time Systems, in Proceedings of the 24th
> IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS),
> 2018
> [2] Q. Wang, T. Stamler, and G. Parmer, Parallel Sections: Scaling
> System-Level Data-Structures, in Proceedings of European Conference on
> Computer Systems (EuroSys), 2016
> 
> Thanks,
> Best,
> Yuxin
> 
> 
> > > This is because MVCC and RLU provide readers a consistent view of
> > > > the updates, and RCU does not.  Of course, it is often the case that a
> > > > consistent view is not needed, in which case the MVCC and RLU
> > guarantees
> > > > are incurring read-side overhead for no reason.  But if the use case
> > > > requires consistent readers, RCU is not an option.
> > > >
> > > > The reason a consistent view is not always needed is that
> > speed-of-light
> > > > delays make it impossible to provide a consistent view of the outside
> > > > world.  In the common case where the use case interacts with the
> > > > outside world, the algorithms absolutely must be designed to tolerate
> > > > inconsistency, which opens the door to things like RCU.
> > >
> > > I am confused here. I think speed-of-light delays happen everywhere, not
> > > only bound to RCU, but also  any other synchronization approach (such
> > RLU).
> > > If so, how do others (RLU) provide consistent views?
> >
> > You just stated the answer.  Now it is only necessary for you to invest
> > the time, effort, and thought to fully understand it.  To help with this,
> > the following paragraph provides another hint:
> >
> >         Yes, you are quite right, speed-of-light delays between the
> >         outside world and the computer affect RLU just as surely as they
> >         do RCU.  This means that the additional consistency guarantees
> >         provided by RLU must necessarily be limited to the confines of the
> >         computer system in question.  Taking this one step further, there
> >         are also speed-of-light delays within the computer.  Therefore,
> >         in the general case, RLU can provide its consistency guarantees,
> >         even within the confines of the computer system, only at the
> >         expense of incurring delays.  Because RCU does not provide RLU's
> >         consistency guarantees, it need not incur RLU's delays.
> >
> > This is not a new line of reasoning, see for example:
> >
> > @article{Herlihy:1996:LCN:1063369.1063372
> > ,author = {Herlihy, Maurice and Shavit, Nir and Waarts, Orli}
> > ,title = {Linearizable counting networks}
> > ,journal = {Distrib. Comput.}
> > ,volume = {9}
> > ,issue = {4}
> > ,month = {February}
> > ,year = {1996}
> > ,issn = {0178-2770}
> > ,pages = {193--203}
> > ,numpages = {11}
> > ,url = {http://portal.acm.org/citation.cfm?id=1063369.1063372}
> > ,doi = {10.1007/s004460050019}
> > ,acmid = {1063372}
> > ,publisher = {Springer-Verlag}
> > ,address = {London, UK}
> > ,keywords = {concurrency, contention, counting networks, data structures,
> > linearizability}
> > }
> >
> >                                                         Thanx, Paul
> >
> > > Thanks for your education.
> > > Yuxin
> > >
> > > >
> > > >                                                         Thanx, Paul
> > > >
> > > > > Thanks
> > > > > Yuxin
> > > > >
> > > > > On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <paulmck@kernel.org
> > >
> > > > wrote:
> > > > >
> > > > > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:
> > > > > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <ryx@gwmail.gwu.edu>
> > > > wrote:
> > > > > > >
> > > > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > > > > mailto:mathieu.desnoyers@efficios.com |
> > > > mathieu.desnoyers@efficios.com
> > > > > > ] >
> > > > > > > > wrote:
> > > > > > >
> > > > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > > > > ryx@gwmail.gwu.edu |
> > > > > > > >> ryx@gwmail.gwu.edu ] > wrote:
> > > > > > >
> > > > > > > >>> Hi,
> > > > > > > >>> I am a student, and learning RCU now, but still know very
> > little
> > > > > > about it.
> > > > > > > >>> Are there any documents/papers/materials which (in)formally
> > > > define
> > > > > > and explain
> > > > > > > >>> RCU consistency guarantees?
> > > > > > >
> > > > > > > >> You may want to have a look at
> > > > > > >
> > > > > > > >> User-Level Implementations of Read-Copy Update
> > > > > > > >> Article in IEEE Transactions on Parallel and Distributed
> > Systems
> > > > > > 23(2):375 - 382
> > > > > > > >> · March 2012
> > > > > > >
> > > > > > > > Thanks for your info.
> > > > > > > > However, I do not think URCU talks about any consistency model
> > > > > > formally.
> > > > > > >
> > > > > > > > From previous communication with Paul, he said RCU is not
> > designed
> > > > for
> > > > > > > > linearizability, and it is totally acceptable that RCU is not
> > > > > > linearizable.
> > > > > > > > However, I am curious how to accurately/formally Characterize
> > RCU
> > > > > > consistency
> > > > > > > > model/guarantees
> > > > > > >
> > > > > > > Adding Paul E. McKenney in CC.
> > > > > > >
> > > > > > > I am referring to the section "Overview of RCU semantics" in the
> > > > paper.
> > > > > > Not sure it has the level of
> > > > > > > formality you are looking for though. Paul, do you have pointers
> > to
> > > > > > additional material ?
> > > > > >
> > > > > > Indeed I do!  The Linux kernel memory model (LKMM) includes RCU.
> > It is
> > > > > > in tools/memory-model in recent kernel source trees, which includes
> > > > > > documentation.  This is an executable model, which means that you
> > > > > > can create litmus tests and have the model formally and
> > automatically
> > > > > > evaluate them.
> > > > > >
> > > > > > There are also a number of publications covering LKMM:
> > > > > >
> > > > > > o       A formal kernel memory-ordering model
> > > > > >         https://lwn.net/Articles/718628/
> > > > > >         https://lwn.net/Articles/720550/
> > > > > >
> > > > > >         These cover the release stores and dependency ordering that
> > > > > >         provide RCU's publish-subscribe guarantees.
> > > > > >
> > > > > >         Backup material here:
> > > > > >
> > > > > >
> > > > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> > > > > >
> > > > > >         With these two likely being of particular interest:
> > > > > >
> > > > > >
> > > > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
> > > > > >
> > > > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
> > > > > >
> > > > > > o       Frightening Small Children and Disconcerting Grown-ups:
> > > > > > Concurrency in the Linux Kernel
> > > > > >         https://dl.acm.org/citation.cfm?id=3177156
> > > > > >
> > http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> > > > > >
> > > > > >         Backup material:
> > > > > >
> > > > > >         http://diy.inria.fr/linux/
> > > > > >
> > > > > > o       Who's afraid of a big bad optimizing compiler?
> > > > > >         https://lwn.net/Articles/793253/
> > > > > >
> > > > > > o       Calibrating your fear of big bad optimizing compilers
> > > > > >         https://lwn.net/Articles/799218/
> > > > > >
> > > > > >         These last two justify use of normal C-language assignment
> > > > > >         statements to initialize and access data referenced by
> > > > > >         RCU-protected pointers.
> > > > > >
> > > > > > There is a large body of litmus tests (thousands of them) here:
> > > > > >
> > > > > >         https://github.com/paulmckrcu/litmus
> > > > > >
> > > > > > Many of these litmus tests involve RCU, and these can be located by
> > > > > > search for files containing rcu_read_lock(), rcu_read_unlock(),
> > > > > > synchronize_rcu(), and so on.
> > > > > >
> > > > > > Or were you looking for something else?
> > > > > >
> > > > > >                                                         Thanx, Paul
> > > > > >
> > > > > > > Thanks,
> > > > > > >
> > > > > > > Mathieu
> > > > > > >
> > > > > > > >> as a starting point.
> > > > > > >
> > > > > > > >> Thanks,
> > > > > > >
> > > > > > > >> Mathieu
> > > > > > >
> > > > > > > >>> I know there are some consistency models in the database area
> > > > (such
> > > > > > as PRAM,
> > > > > > > >>> Read Uncommitted, etc) from [ https://jepsen.io/consistency
> > |
> > > > > > > >>> https://jepsen.io/consistency ] and [1].
> > > > > > > >>> How does RCU related to those consistency models?
> > > > > > >
> > > > > > > >>> I also found some comments online (One key distinction is
> > that
> > > > both
> > > > > > MVCC and RLU
> > > > > > > >>> provide much stronger consistency guarantees to readers than
> > does
> > > > > > RCU ...) ( [
> > > > > > > >>> https://lwn.net/Articles/777036/ |
> > > > https://lwn.net/Articles/777036/
> > > > > > ] ).
> > > > > > > >>> I do not understand how we reason/dresibe/compare the
> > consistency
> > > > > > guarantees. (
> > > > > > > >>> I even do not know what consistency guarantees provided by
> > RCU
> > > > > > formally)
> > > > > > > >>> Could someone explain this to me?
> > > > > > >
> > > > > > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A.,
> > > > Hellerstein,
> > > > > > J. M., &
> > > > > > > >>> Stoica, I. (2013). Highly available transactions: Virtues and
> > > > > > limitations.
> > > > > > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> > > > > > >
> > > > > > > >>> Thanks
> > > > > > > >>> Yuxin
> > > > > > >
> > > > > > > >>> _______________________________________________
> > > > > > > >>> lttng-dev mailing list
> > > > > > > >>> [ mailto:lttng-dev@lists.lttng.org |
> > lttng-dev@lists.lttng.org ]
> > > > > > > >>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> > |
> > > > > > > >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> > > > > > >
> > > > > > > >> --
> > > > > > > >> Mathieu Desnoyers
> > > > > > > >> EfficiOS Inc.
> > > > > > > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> > > > > > >
> > > > > > > --
> > > > > > > Mathieu Desnoyers
> > > > > > > EfficiOS Inc.
> > > > > > > http://www.efficios.com
> > > > > >
> > > >
> >
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Yuxin Ren]

[-- Attachment #1.1: Type: text/plain, Size: 18598 bytes --]

On Sun, Dec 15, 2019 at 3:30 PM Paul E. McKenney <paulmck@kernel.org> wrote:

> On Sat, Dec 14, 2019 at 01:31:31AM -0500, Yuxin Ren wrote:
> > Hi Paul
> >
> > On Sat, Dec 7, 2019 at 5:42 PM Paul E. McKenney <paulmck@kernel.org>
> wrote:
> >
> > > On Sat, Dec 07, 2019 at 03:04:42PM -0500, Yuxin Ren wrote:
> > > > Thanks a lot for your help. I have some questions below.
> > > >
> > > > On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <paulmck@kernel.org>
> > > wrote:
> > > >
> > > > > On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:
> > > > > > Thanks so much for your great help.
> > > > > > I definitely will look at those resources and papers!
> > > > > >
> > > > > > One more thing that I am confused
> > > > > > As I mentioned earlier, someone said One key distinction is that
> both
> > > > > MVCC
> > > > > > and RLU provide much stronger consistency guarantees to readers
> than
> > > does
> > > > > > RCU ...) (https://lwn.net/Articles/777036/).
> > > > >
> > > > > That someone was in fact me.  ;-)
> > > > >
> > > > > > I am not sure if the above statement is correct or not. But in
> > > general,
> > > > > > How can we compare RCU consistency guarantees to other techniques
> > > (such
> > > > > as
> > > > > > RLU)?
> > > > > > How to reason about which one has stronger or weaker guarantees?
> > > > >
> > > > > I suggest starting from the use case.  For concreteness, let's
> assume
> > > > > that we are using a hash table.  At one extreme, imagine a use
> case in
> > > > > which each event makes exactly one hash-table operation.  No
> > > information
> > > > > is carried from one event to the next.  (This might well be the
> case
> > > > > for simple web server.)  Such a use case cannot tell the difference
> > > > > between RCU on the one hand and MVCC/RLU on the other.
> > > > >
> > > > > At the other extreme, suppose that each event either accesses or
> > > updates
> > > > > multiple entries in the hash table.  In this case, MVCC/RLU will
> rule
> > > > > out outcomes that RCU would permit.  For example, suppose we had
> four
> > > > > events accessing two different elements in different buckets of the
> > > > > hash table:
> > > > >
> > > > >         E1: Adds 32 to the hash table.
> > > > >         E2: Adds 1729 to the hash table.
> > > > >         E3: Within a read-side critical section, looks up 32 then
> 1729.
> > > > >         E4: Within a read-side critical section, looks up 1729
> then 32.
> > > > >
> > > > > Given either MVCC or RLU, it will not be possible for E3 to find
> 32 but
> > > > > not 1729 and at the same time for E4 to find 1729 but not 32.
> Given
> > > RCU,
> > > > > this outcome is possible.
> > > > >
> > > > When you say "Within a read-side section", do you mean within a
> single
> > > same
> > > > read section? such as
> > > >
> > > > > read_lock()
> > > > > lookup(32)
> > > > > lookup(1729)
> > > > > read_unlock()
> > > >
> > > >
> > > > How about putting two lookups into two read-side sections? Do we
> still
> > > have
> > > > the problem, then?
> > > >
> > > > > read_lock()
> > > > > lookup(32)
> > > > > read_unlock()
> > > > > read_lock()
> > > > > lookup(1729)
> > > > > read_unlock()
> > >
> > > Without in any way agreeing with your characterization of this as a
> > > problem, because rcu_read_lock() and rcu_read_unlock() provide
> > > absolutely no ordering guarantees in the absence of a grace period,
> > > any non-grace-period-related reordering that can happen with a single
> > > RCU read-side critical section can also happen when that critical
> > > section is split in two as you have done above.
> > >
> > > > Could you kindly give me more clues why RCU can see such reorder,
> while
> > > RLU
> > > > can prevent it?
> > >
> > > Here are minimal C-language implementations for RCU that can (and are)
> > > actually used:
> > >
> > Great. We use the same thing in our real-time work [1]
>
> It has been a popular choice for 40 years now.  ;-)
>
> > > #define rcu_read_lock()
> > > #define rcu_read_unlock()
> > >
> > > Please compare these to the read-side markers presented in the RLU
> paper,
> > > and then tell me your thoughts on the answer to your question.  ;-)
> > >
> > I submit my homework here, but I do not think I did it well.
> > 1. I believe in the default URCU implementation, it has memory barrier
> > inside the read_lock / read_unlock.
>
> It certainly was at one time.  But you would of course need to check
> to see what any given worker actually used.
>
> > 2. From the RLU paper, it shows the code for read-side operation.
> > RLU_READER_LOCK(ctx)
> >     ctx.is-writer←false
> >     ctx.run-cnt←ctx.run-cnt+1.
> >     memory fence
> >    ctx.local-clock←global-clock
> > RLU_READER_UNLOCK(ctx)
> >     ctx.run-cnt←ctx.run-cnt+1
> >     if (ctx.is-writer)
> >         RLU_COMMIT_WRITE_LOG(ctx)
> >
> > We can ignore the writer check, as in our case, the reader never do
> update.
> > My understanding is that read-side operations are only used to facilitate
> > the quiescence detection.
> > the run cnt is used to decide if a thread is active (if it is currently
> > inside a read-side section).
> > the local clock is used to check if the active thread goes into the
> > read-side section very late, so it does not prevent reclaiming memory
> > unlinked before it enters the read section.
> > However i see no difference between RLU and RCU read-side operation
> > regarding consistency guarantee.
> > Could you kindly teach me more?
>
> In order to teach you more, I do need some help from you.  I have posted
> a number of URLs earlier in this email thread.  Could you please tell
> me what you learned from each of them?
>
Sure, I will definitely learn those resources you provided, and come back
to you if I have more questions.
Simply speaking, I failed to find a clear and formal consistency
model/guarantee of RCU quickly.
The difficulty for me is, for most people, at their first glance, RCU only
has relax/weak consistency guarantee.
So whenever I suggest to use RCU to others, they always ask like
Does RCU provide Serializability? .. maybe not.
Does RCU provide Linearizability? ... maybe not
...
OK, what does RCU provide?  .. I am not sure. I even cannot find a single
document which has an accurate answer.

Let me give more examples.
1. When I recommend using read-write lock, people are happy to use it.
    However, when I further suggest to replace rw lock with RCU, then they
hesitate to do so. Because they feel RCU is weaker than rw lock, and do not
know what precisely RCU guarantee.
2. In contrast, in the database area, it has relative clear definition of
consistency levels (such as https://jepsen.io/consistency), and users are
easy to assert if they can use certain database configuration based on its
consistency model.

Again, I really appreciate your patience and communication, hope those does
not bother you a lot.

Thanks
Best,
Yuxin

>
>                                                                 Thanx, Paul
>
> > BTW, the RLU read-side ops are similar, but not efficient, comparing to
> our
> > Parsec work [1, 2]
> > [1] Yuxin Ren, G. Liu, G. Parmer, B. Brandenburg, Scalable Memory
> > Reclamation for Multi-Core, Real-Time Systems, in Proceedings of the 24th
> > IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS),
> > 2018
> > [2] Q. Wang, T. Stamler, and G. Parmer, Parallel Sections: Scaling
> > System-Level Data-Structures, in Proceedings of European Conference on
> > Computer Systems (EuroSys), 2016
> >
> > Thanks,
> > Best,
> > Yuxin
> >
> >
> > > > This is because MVCC and RLU provide readers a consistent view of
> > > > > the updates, and RCU does not.  Of course, it is often the case
> that a
> > > > > consistent view is not needed, in which case the MVCC and RLU
> > > guarantees
> > > > > are incurring read-side overhead for no reason.  But if the use
> case
> > > > > requires consistent readers, RCU is not an option.
> > > > >
> > > > > The reason a consistent view is not always needed is that
> > > speed-of-light
> > > > > delays make it impossible to provide a consistent view of the
> outside
> > > > > world.  In the common case where the use case interacts with the
> > > > > outside world, the algorithms absolutely must be designed to
> tolerate
> > > > > inconsistency, which opens the door to things like RCU.
> > > >
> > > > I am confused here. I think speed-of-light delays happen everywhere,
> not
> > > > only bound to RCU, but also  any other synchronization approach (such
> > > RLU).
> > > > If so, how do others (RLU) provide consistent views?
> > >
> > > You just stated the answer.  Now it is only necessary for you to invest
> > > the time, effort, and thought to fully understand it.  To help with
> this,
> > > the following paragraph provides another hint:
> > >
> > >         Yes, you are quite right, speed-of-light delays between the
> > >         outside world and the computer affect RLU just as surely as
> they
> > >         do RCU.  This means that the additional consistency guarantees
> > >         provided by RLU must necessarily be limited to the confines of
> the
> > >         computer system in question.  Taking this one step further,
> there
> > >         are also speed-of-light delays within the computer.  Therefore,
> > >         in the general case, RLU can provide its consistency
> guarantees,
> > >         even within the confines of the computer system, only at the
> > >         expense of incurring delays.  Because RCU does not provide
> RLU's
> > >         consistency guarantees, it need not incur RLU's delays.
> > >
> > > This is not a new line of reasoning, see for example:
> > >
> > > @article{Herlihy:1996:LCN:1063369.1063372
> > > ,author = {Herlihy, Maurice and Shavit, Nir and Waarts, Orli}
> > > ,title = {Linearizable counting networks}
> > > ,journal = {Distrib. Comput.}
> > > ,volume = {9}
> > > ,issue = {4}
> > > ,month = {February}
> > > ,year = {1996}
> > > ,issn = {0178-2770}
> > > ,pages = {193--203}
> > > ,numpages = {11}
> > > ,url = {http://portal.acm.org/citation.cfm?id=1063369.1063372}
> > > ,doi = {10.1007/s004460050019}
> > > ,acmid = {1063372}
> > > ,publisher = {Springer-Verlag}
> > > ,address = {London, UK}
> > > ,keywords = {concurrency, contention, counting networks, data
> structures,
> > > linearizability}
> > > }
> > >
> > >                                                         Thanx, Paul
> > >
> > > > Thanks for your education.
> > > > Yuxin
> > > >
> > > > >
> > > > >                                                         Thanx, Paul
> > > > >
> > > > > > Thanks
> > > > > > Yuxin
> > > > > >
> > > > > > On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <
> paulmck@kernel.org
> > > >
> > > > > wrote:
> > > > > >
> > > > > > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers
> wrote:
> > > > > > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <
> ryx@gwmail.gwu.edu>
> > > > > wrote:
> > > > > > > >
> > > > > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > > > > > mailto:mathieu.desnoyers@efficios.com |
> > > > > mathieu.desnoyers@efficios.com
> > > > > > > ] >
> > > > > > > > > wrote:
> > > > > > > >
> > > > > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > > > > > ryx@gwmail.gwu.edu |
> > > > > > > > >> ryx@gwmail.gwu.edu ] > wrote:
> > > > > > > >
> > > > > > > > >>> Hi,
> > > > > > > > >>> I am a student, and learning RCU now, but still know very
> > > little
> > > > > > > about it.
> > > > > > > > >>> Are there any documents/papers/materials which
> (in)formally
> > > > > define
> > > > > > > and explain
> > > > > > > > >>> RCU consistency guarantees?
> > > > > > > >
> > > > > > > > >> You may want to have a look at
> > > > > > > >
> > > > > > > > >> User-Level Implementations of Read-Copy Update
> > > > > > > > >> Article in IEEE Transactions on Parallel and Distributed
> > > Systems
> > > > > > > 23(2):375 - 382
> > > > > > > > >> · March 2012
> > > > > > > >
> > > > > > > > > Thanks for your info.
> > > > > > > > > However, I do not think URCU talks about any consistency
> model
> > > > > > > formally.
> > > > > > > >
> > > > > > > > > From previous communication with Paul, he said RCU is not
> > > designed
> > > > > for
> > > > > > > > > linearizability, and it is totally acceptable that RCU is
> not
> > > > > > > linearizable.
> > > > > > > > > However, I am curious how to accurately/formally
> Characterize
> > > RCU
> > > > > > > consistency
> > > > > > > > > model/guarantees
> > > > > > > >
> > > > > > > > Adding Paul E. McKenney in CC.
> > > > > > > >
> > > > > > > > I am referring to the section "Overview of RCU semantics" in
> the
> > > > > paper.
> > > > > > > Not sure it has the level of
> > > > > > > > formality you are looking for though. Paul, do you have
> pointers
> > > to
> > > > > > > additional material ?
> > > > > > >
> > > > > > > Indeed I do!  The Linux kernel memory model (LKMM) includes
> RCU.
> > > It is
> > > > > > > in tools/memory-model in recent kernel source trees, which
> includes
> > > > > > > documentation.  This is an executable model, which means that
> you
> > > > > > > can create litmus tests and have the model formally and
> > > automatically
> > > > > > > evaluate them.
> > > > > > >
> > > > > > > There are also a number of publications covering LKMM:
> > > > > > >
> > > > > > > o       A formal kernel memory-ordering model
> > > > > > >         https://lwn.net/Articles/718628/
> > > > > > >         https://lwn.net/Articles/720550/
> > > > > > >
> > > > > > >         These cover the release stores and dependency ordering
> that
> > > > > > >         provide RCU's publish-subscribe guarantees.
> > > > > > >
> > > > > > >         Backup material here:
> > > > > > >
> > > > > > >
> > > > > > >
> > > > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> > > > > > >
> > > > > > >         With these two likely being of particular interest:
> > > > > > >
> > > > > > >
> > > > > > >
> > > > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
> > > > > > >
> > > > > > >
> > > > >
> > >
> https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
> > > > > > >
> > > > > > > o       Frightening Small Children and Disconcerting Grown-ups:
> > > > > > > Concurrency in the Linux Kernel
> > > > > > >         https://dl.acm.org/citation.cfm?id=3177156
> > > > > > >
> > > http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> > > > > > >
> > > > > > >         Backup material:
> > > > > > >
> > > > > > >         http://diy.inria.fr/linux/
> > > > > > >
> > > > > > > o       Who's afraid of a big bad optimizing compiler?
> > > > > > >         https://lwn.net/Articles/793253/
> > > > > > >
> > > > > > > o       Calibrating your fear of big bad optimizing compilers
> > > > > > >         https://lwn.net/Articles/799218/
> > > > > > >
> > > > > > >         These last two justify use of normal C-language
> assignment
> > > > > > >         statements to initialize and access data referenced by
> > > > > > >         RCU-protected pointers.
> > > > > > >
> > > > > > > There is a large body of litmus tests (thousands of them) here:
> > > > > > >
> > > > > > >         https://github.com/paulmckrcu/litmus
> > > > > > >
> > > > > > > Many of these litmus tests involve RCU, and these can be
> located by
> > > > > > > search for files containing rcu_read_lock(), rcu_read_unlock(),
> > > > > > > synchronize_rcu(), and so on.
> > > > > > >
> > > > > > > Or were you looking for something else?
> > > > > > >
> > > > > > >                                                         Thanx,
> Paul
> > > > > > >
> > > > > > > > Thanks,
> > > > > > > >
> > > > > > > > Mathieu
> > > > > > > >
> > > > > > > > >> as a starting point.
> > > > > > > >
> > > > > > > > >> Thanks,
> > > > > > > >
> > > > > > > > >> Mathieu
> > > > > > > >
> > > > > > > > >>> I know there are some consistency models in the database
> area
> > > > > (such
> > > > > > > as PRAM,
> > > > > > > > >>> Read Uncommitted, etc) from [
> https://jepsen.io/consistency
> > > |
> > > > > > > > >>> https://jepsen.io/consistency ] and [1].
> > > > > > > > >>> How does RCU related to those consistency models?
> > > > > > > >
> > > > > > > > >>> I also found some comments online (One key distinction is
> > > that
> > > > > both
> > > > > > > MVCC and RLU
> > > > > > > > >>> provide much stronger consistency guarantees to readers
> than
> > > does
> > > > > > > RCU ...) ( [
> > > > > > > > >>> https://lwn.net/Articles/777036/ |
> > > > > https://lwn.net/Articles/777036/
> > > > > > > ] ).
> > > > > > > > >>> I do not understand how we reason/dresibe/compare the
> > > consistency
> > > > > > > guarantees. (
> > > > > > > > >>> I even do not know what consistency guarantees provided
> by
> > > RCU
> > > > > > > formally)
> > > > > > > > >>> Could someone explain this to me?
> > > > > > > >
> > > > > > > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A.,
> > > > > Hellerstein,
> > > > > > > J. M., &
> > > > > > > > >>> Stoica, I. (2013). Highly available transactions:
> Virtues and
> > > > > > > limitations.
> > > > > > > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> > > > > > > >
> > > > > > > > >>> Thanks
> > > > > > > > >>> Yuxin
> > > > > > > >
> > > > > > > > >>> _______________________________________________
> > > > > > > > >>> lttng-dev mailing list
> > > > > > > > >>> [ mailto:lttng-dev@lists.lttng.org |
> > > lttng-dev@lists.lttng.org ]
> > > > > > > > >>> [
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> > > |
> > > > > > > > >>>
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> > > > > > > >
> > > > > > > > >> --
> > > > > > > > >> Mathieu Desnoyers
> > > > > > > > >> EfficiOS Inc.
> > > > > > > > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> > > > > > > >
> > > > > > > > --
> > > > > > > > Mathieu Desnoyers
> > > > > > > > EfficiOS Inc.
> > > > > > > > http://www.efficios.com
> > > > > > >
> > > > >
> > >
>

[-- Attachment #1.2: Type: text/html, Size: 28191 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: RCU consistency guarantees

[Paul E. McKenney]

On Sun, Dec 15, 2019 at 05:10:11PM -0500, Yuxin Ren wrote:
> On Sun, Dec 15, 2019 at 3:30 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> 
> > On Sat, Dec 14, 2019 at 01:31:31AM -0500, Yuxin Ren wrote:
> > > Hi Paul
> > >
> > > On Sat, Dec 7, 2019 at 5:42 PM Paul E. McKenney <paulmck@kernel.org>
> > wrote:
> > >
> > > > On Sat, Dec 07, 2019 at 03:04:42PM -0500, Yuxin Ren wrote:
> > > > > Thanks a lot for your help. I have some questions below.
> > > > >
> > > > > On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <paulmck@kernel.org>
> > > > wrote:
> > > > >
> > > > > > On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:
> > > > > > > Thanks so much for your great help.
> > > > > > > I definitely will look at those resources and papers!
> > > > > > >
> > > > > > > One more thing that I am confused
> > > > > > > As I mentioned earlier, someone said One key distinction is that
> > both
> > > > > > MVCC
> > > > > > > and RLU provide much stronger consistency guarantees to readers
> > than
> > > > does
> > > > > > > RCU ...) (https://lwn.net/Articles/777036/).
> > > > > >
> > > > > > That someone was in fact me.  ;-)
> > > > > >
> > > > > > > I am not sure if the above statement is correct or not. But in
> > > > general,
> > > > > > > How can we compare RCU consistency guarantees to other techniques
> > > > (such
> > > > > > as
> > > > > > > RLU)?
> > > > > > > How to reason about which one has stronger or weaker guarantees?
> > > > > >
> > > > > > I suggest starting from the use case.  For concreteness, let's
> > assume
> > > > > > that we are using a hash table.  At one extreme, imagine a use
> > case in
> > > > > > which each event makes exactly one hash-table operation.  No
> > > > information
> > > > > > is carried from one event to the next.  (This might well be the
> > case
> > > > > > for simple web server.)  Such a use case cannot tell the difference
> > > > > > between RCU on the one hand and MVCC/RLU on the other.
> > > > > >
> > > > > > At the other extreme, suppose that each event either accesses or
> > > > updates
> > > > > > multiple entries in the hash table.  In this case, MVCC/RLU will
> > rule
> > > > > > out outcomes that RCU would permit.  For example, suppose we had
> > four
> > > > > > events accessing two different elements in different buckets of the
> > > > > > hash table:
> > > > > >
> > > > > >         E1: Adds 32 to the hash table.
> > > > > >         E2: Adds 1729 to the hash table.
> > > > > >         E3: Within a read-side critical section, looks up 32 then
> > 1729.
> > > > > >         E4: Within a read-side critical section, looks up 1729
> > then 32.
> > > > > >
> > > > > > Given either MVCC or RLU, it will not be possible for E3 to find
> > 32 but
> > > > > > not 1729 and at the same time for E4 to find 1729 but not 32.
> > Given
> > > > RCU,
> > > > > > this outcome is possible.
> > > > > >
> > > > > When you say "Within a read-side section", do you mean within a
> > single
> > > > same
> > > > > read section? such as
> > > > >
> > > > > > read_lock()
> > > > > > lookup(32)
> > > > > > lookup(1729)
> > > > > > read_unlock()
> > > > >
> > > > >
> > > > > How about putting two lookups into two read-side sections? Do we
> > still
> > > > have
> > > > > the problem, then?
> > > > >
> > > > > > read_lock()
> > > > > > lookup(32)
> > > > > > read_unlock()
> > > > > > read_lock()
> > > > > > lookup(1729)
> > > > > > read_unlock()
> > > >
> > > > Without in any way agreeing with your characterization of this as a
> > > > problem, because rcu_read_lock() and rcu_read_unlock() provide
> > > > absolutely no ordering guarantees in the absence of a grace period,
> > > > any non-grace-period-related reordering that can happen with a single
> > > > RCU read-side critical section can also happen when that critical
> > > > section is split in two as you have done above.
> > > >
> > > > > Could you kindly give me more clues why RCU can see such reorder,
> > while
> > > > RLU
> > > > > can prevent it?
> > > >
> > > > Here are minimal C-language implementations for RCU that can (and are)
> > > > actually used:
> > > >
> > > Great. We use the same thing in our real-time work [1]
> >
> > It has been a popular choice for 40 years now.  ;-)
> >
> > > > #define rcu_read_lock()
> > > > #define rcu_read_unlock()
> > > >
> > > > Please compare these to the read-side markers presented in the RLU
> > paper,
> > > > and then tell me your thoughts on the answer to your question.  ;-)
> > > >
> > > I submit my homework here, but I do not think I did it well.
> > > 1. I believe in the default URCU implementation, it has memory barrier
> > > inside the read_lock / read_unlock.
> >
> > It certainly was at one time.  But you would of course need to check
> > to see what any given worker actually used.
> >
> > > 2. From the RLU paper, it shows the code for read-side operation.
> > > RLU_READER_LOCK(ctx)
> > >     ctx.is-writer←false
> > >     ctx.run-cnt←ctx.run-cnt+1.
> > >     memory fence
> > >    ctx.local-clock←global-clock
> > > RLU_READER_UNLOCK(ctx)
> > >     ctx.run-cnt←ctx.run-cnt+1
> > >     if (ctx.is-writer)
> > >         RLU_COMMIT_WRITE_LOG(ctx)
> > >
> > > We can ignore the writer check, as in our case, the reader never do
> > update.
> > > My understanding is that read-side operations are only used to facilitate
> > > the quiescence detection.
> > > the run cnt is used to decide if a thread is active (if it is currently
> > > inside a read-side section).
> > > the local clock is used to check if the active thread goes into the
> > > read-side section very late, so it does not prevent reclaiming memory
> > > unlinked before it enters the read section.
> > > However i see no difference between RLU and RCU read-side operation
> > > regarding consistency guarantee.
> > > Could you kindly teach me more?
> >
> > In order to teach you more, I do need some help from you.  I have posted
> > a number of URLs earlier in this email thread.  Could you please tell
> > me what you learned from each of them?
> >
> Sure, I will definitely learn those resources you provided, and come back
> to you if I have more questions.
> Simply speaking, I failed to find a clear and formal consistency
> model/guarantee of RCU quickly.
> The difficulty for me is, for most people, at their first glance, RCU only
> has relax/weak consistency guarantee.
> So whenever I suggest to use RCU to others, they always ask like
> Does RCU provide Serializability? .. maybe not.
> Does RCU provide Linearizability? ... maybe not
> ...

Are serializability and linearizability always useful?  Definitely not.
Are serializability and linearizability expensive?  You bet!!!

But if your use case absolutely requires either serializability or
linearizability, you probably should try something other than RCU.
But you should also strongly question serializability and lineariability
requirements, given that they are often imposed out of fear and force
of habit rather than real need.

Nevertheless, there are use cases where RCU is part of a concurrency
design that provides serializability and/or linearizability.  For but
one example:

@Conference{Arcangeli03,
 Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
Dipankar Sarma",
 Title="Using Read-Copy Update Techniques for {System V IPC} in the
{Linux} 2.5 Kernel",
 Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
(FREENIX Track)",
 Publisher="USENIX Association",
 location="San Antonio, Texas, USA",
 year="2003",
 month="June",
 pages="297-310",
 url="https://www.usenix.org/legacy/publications/library/proceedings/usenix03/tech/freenix03/full_papers/arcangeli/arcangeli.pdf",
 lastchecked="February 27, 2017",
}

> OK, what does RCU provide?  .. I am not sure. I even cannot find a single
> document which has an accurate answer.
> 
> Let me give more examples.
> 1. When I recommend using read-write lock, people are happy to use it.
>     However, when I further suggest to replace rw lock with RCU, then they
> hesitate to do so. Because they feel RCU is weaker than rw lock, and do not
> know what precisely RCU guarantee.
> 2. In contrast, in the database area, it has relative clear definition of
> consistency levels (such as https://jepsen.io/consistency), and users are
> easy to assert if they can use certain database configuration based on its
> consistency model.

The RCU guarantees are clearly stated in a number of places.  Most
recently and most formally, the 2018 ASPLOS "Frightening small children"
paper called out below (though the 2012 paper you referred to has a
good and sufficient statement of its guarantees).  This formalism is
executable, and has been available within the Linux-kernel source tree
in executable form for more than a year.  I strongly recommend that you
try playing with this executable model.

But successfully using RCU requires that you think about your problem
differently.  This should not be a surprise.  After all, locking
provides mutual exclusion and RCU does not.  So one set of promising
use cases for RCU are where some quantity is calculated read-holding a
reader-writer lock, but where that quantity is used after releasing that
reader-writer lock.  This is a common use case, and it is a case where the
user has purposefully set aside the serializability and linearizability
guarantees that reader-writer locking provides -- but has nevertheless
paid the full price for these guarantees.

> Again, I really appreciate your patience and communication, hope those does
> not bother you a lot.

At this point, I must confess to being much more amused than bothered.

For example, do I understand correctly that you haven't yet read -any-
of the references I sent you?  It sure seems that way.  ;-)

Also, are you getting adequate sleep, as in at least seven hours
per night?  After all, attempting to learn RCU while sleep-deprived
quite foolhardy.

							Thanx, Paul

> Thanks
> Best,
> Yuxin
> 
> >
> >                                                                 Thanx, Paul
> >
> > > BTW, the RLU read-side ops are similar, but not efficient, comparing to
> > our
> > > Parsec work [1, 2]
> > > [1] Yuxin Ren, G. Liu, G. Parmer, B. Brandenburg, Scalable Memory
> > > Reclamation for Multi-Core, Real-Time Systems, in Proceedings of the 24th
> > > IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS),
> > > 2018
> > > [2] Q. Wang, T. Stamler, and G. Parmer, Parallel Sections: Scaling
> > > System-Level Data-Structures, in Proceedings of European Conference on
> > > Computer Systems (EuroSys), 2016
> > >
> > > Thanks,
> > > Best,
> > > Yuxin
> > >
> > >
> > > > > This is because MVCC and RLU provide readers a consistent view of
> > > > > > the updates, and RCU does not.  Of course, it is often the case
> > that a
> > > > > > consistent view is not needed, in which case the MVCC and RLU
> > > > guarantees
> > > > > > are incurring read-side overhead for no reason.  But if the use
> > case
> > > > > > requires consistent readers, RCU is not an option.
> > > > > >
> > > > > > The reason a consistent view is not always needed is that
> > > > speed-of-light
> > > > > > delays make it impossible to provide a consistent view of the
> > outside
> > > > > > world.  In the common case where the use case interacts with the
> > > > > > outside world, the algorithms absolutely must be designed to
> > tolerate
> > > > > > inconsistency, which opens the door to things like RCU.
> > > > >
> > > > > I am confused here. I think speed-of-light delays happen everywhere,
> > not
> > > > > only bound to RCU, but also  any other synchronization approach (such
> > > > RLU).
> > > > > If so, how do others (RLU) provide consistent views?
> > > >
> > > > You just stated the answer.  Now it is only necessary for you to invest
> > > > the time, effort, and thought to fully understand it.  To help with
> > this,
> > > > the following paragraph provides another hint:
> > > >
> > > >         Yes, you are quite right, speed-of-light delays between the
> > > >         outside world and the computer affect RLU just as surely as
> > they
> > > >         do RCU.  This means that the additional consistency guarantees
> > > >         provided by RLU must necessarily be limited to the confines of
> > the
> > > >         computer system in question.  Taking this one step further,
> > there
> > > >         are also speed-of-light delays within the computer.  Therefore,
> > > >         in the general case, RLU can provide its consistency
> > guarantees,
> > > >         even within the confines of the computer system, only at the
> > > >         expense of incurring delays.  Because RCU does not provide
> > RLU's
> > > >         consistency guarantees, it need not incur RLU's delays.
> > > >
> > > > This is not a new line of reasoning, see for example:
> > > >
> > > > @article{Herlihy:1996:LCN:1063369.1063372
> > > > ,author = {Herlihy, Maurice and Shavit, Nir and Waarts, Orli}
> > > > ,title = {Linearizable counting networks}
> > > > ,journal = {Distrib. Comput.}
> > > > ,volume = {9}
> > > > ,issue = {4}
> > > > ,month = {February}
> > > > ,year = {1996}
> > > > ,issn = {0178-2770}
> > > > ,pages = {193--203}
> > > > ,numpages = {11}
> > > > ,url = {http://portal.acm.org/citation.cfm?id=1063369.1063372}
> > > > ,doi = {10.1007/s004460050019}
> > > > ,acmid = {1063372}
> > > > ,publisher = {Springer-Verlag}
> > > > ,address = {London, UK}
> > > > ,keywords = {concurrency, contention, counting networks, data
> > structures,
> > > > linearizability}
> > > > }
> > > >
> > > >                                                         Thanx, Paul
> > > >
> > > > > Thanks for your education.
> > > > > Yuxin
> > > > >
> > > > > >
> > > > > >                                                         Thanx, Paul
> > > > > >
> > > > > > > Thanks
> > > > > > > Yuxin
> > > > > > >
> > > > > > > On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <
> > paulmck@kernel.org
> > > > >
> > > > > > wrote:
> > > > > > >
> > > > > > > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers
> > wrote:
> > > > > > > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <
> > ryx@gwmail.gwu.edu>
> > > > > > wrote:
> > > > > > > > >
> > > > > > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > > > > > > mailto:mathieu.desnoyers@efficios.com |
> > > > > > mathieu.desnoyers@efficios.com
> > > > > > > > ] >
> > > > > > > > > > wrote:
> > > > > > > > >
> > > > > > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > > > > > > ryx@gwmail.gwu.edu |
> > > > > > > > > >> ryx@gwmail.gwu.edu ] > wrote:
> > > > > > > > >
> > > > > > > > > >>> Hi,
> > > > > > > > > >>> I am a student, and learning RCU now, but still know very
> > > > little
> > > > > > > > about it.
> > > > > > > > > >>> Are there any documents/papers/materials which
> > (in)formally
> > > > > > define
> > > > > > > > and explain
> > > > > > > > > >>> RCU consistency guarantees?
> > > > > > > > >
> > > > > > > > > >> You may want to have a look at
> > > > > > > > >
> > > > > > > > > >> User-Level Implementations of Read-Copy Update
> > > > > > > > > >> Article in IEEE Transactions on Parallel and Distributed
> > > > Systems
> > > > > > > > 23(2):375 - 382
> > > > > > > > > >> · March 2012
> > > > > > > > >
> > > > > > > > > > Thanks for your info.
> > > > > > > > > > However, I do not think URCU talks about any consistency
> > model
> > > > > > > > formally.
> > > > > > > > >
> > > > > > > > > > From previous communication with Paul, he said RCU is not
> > > > designed
> > > > > > for
> > > > > > > > > > linearizability, and it is totally acceptable that RCU is
> > not
> > > > > > > > linearizable.
> > > > > > > > > > However, I am curious how to accurately/formally
> > Characterize
> > > > RCU
> > > > > > > > consistency
> > > > > > > > > > model/guarantees
> > > > > > > > >
> > > > > > > > > Adding Paul E. McKenney in CC.
> > > > > > > > >
> > > > > > > > > I am referring to the section "Overview of RCU semantics" in
> > the
> > > > > > paper.
> > > > > > > > Not sure it has the level of
> > > > > > > > > formality you are looking for though. Paul, do you have
> > pointers
> > > > to
> > > > > > > > additional material ?
> > > > > > > >
> > > > > > > > Indeed I do!  The Linux kernel memory model (LKMM) includes
> > RCU.
> > > > It is
> > > > > > > > in tools/memory-model in recent kernel source trees, which
> > includes
> > > > > > > > documentation.  This is an executable model, which means that
> > you
> > > > > > > > can create litmus tests and have the model formally and
> > > > automatically
> > > > > > > > evaluate them.
> > > > > > > >
> > > > > > > > There are also a number of publications covering LKMM:
> > > > > > > >
> > > > > > > > o       A formal kernel memory-ordering model
> > > > > > > >         https://lwn.net/Articles/718628/
> > > > > > > >         https://lwn.net/Articles/720550/
> > > > > > > >
> > > > > > > >         These cover the release stores and dependency ordering
> > that
> > > > > > > >         provide RCU's publish-subscribe guarantees.
> > > > > > > >
> > > > > > > >         Backup material here:
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> > > > > > > >
> > > > > > > >         With these two likely being of particular interest:
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html
> > > > > > > >
> > > > > > > >
> > > > > >
> > > >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html
> > > > > > > >
> > > > > > > > o       Frightening Small Children and Disconcerting Grown-ups:
> > > > > > > > Concurrency in the Linux Kernel
> > > > > > > >         https://dl.acm.org/citation.cfm?id=3177156
> > > > > > > >
> > > > http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> > > > > > > >
> > > > > > > >         Backup material:
> > > > > > > >
> > > > > > > >         http://diy.inria.fr/linux/
> > > > > > > >
> > > > > > > > o       Who's afraid of a big bad optimizing compiler?
> > > > > > > >         https://lwn.net/Articles/793253/
> > > > > > > >
> > > > > > > > o       Calibrating your fear of big bad optimizing compilers
> > > > > > > >         https://lwn.net/Articles/799218/
> > > > > > > >
> > > > > > > >         These last two justify use of normal C-language
> > assignment
> > > > > > > >         statements to initialize and access data referenced by
> > > > > > > >         RCU-protected pointers.
> > > > > > > >
> > > > > > > > There is a large body of litmus tests (thousands of them) here:
> > > > > > > >
> > > > > > > >         https://github.com/paulmckrcu/litmus
> > > > > > > >
> > > > > > > > Many of these litmus tests involve RCU, and these can be
> > located by
> > > > > > > > search for files containing rcu_read_lock(), rcu_read_unlock(),
> > > > > > > > synchronize_rcu(), and so on.
> > > > > > > >
> > > > > > > > Or were you looking for something else?
> > > > > > > >
> > > > > > > >                                                         Thanx,
> > Paul
> > > > > > > >
> > > > > > > > > Thanks,
> > > > > > > > >
> > > > > > > > > Mathieu
> > > > > > > > >
> > > > > > > > > >> as a starting point.
> > > > > > > > >
> > > > > > > > > >> Thanks,
> > > > > > > > >
> > > > > > > > > >> Mathieu
> > > > > > > > >
> > > > > > > > > >>> I know there are some consistency models in the database
> > area
> > > > > > (such
> > > > > > > > as PRAM,
> > > > > > > > > >>> Read Uncommitted, etc) from [
> > https://jepsen.io/consistency
> > > > |
> > > > > > > > > >>> https://jepsen.io/consistency ] and [1].
> > > > > > > > > >>> How does RCU related to those consistency models?
> > > > > > > > >
> > > > > > > > > >>> I also found some comments online (One key distinction is
> > > > that
> > > > > > both
> > > > > > > > MVCC and RLU
> > > > > > > > > >>> provide much stronger consistency guarantees to readers
> > than
> > > > does
> > > > > > > > RCU ...) ( [
> > > > > > > > > >>> https://lwn.net/Articles/777036/ |
> > > > > > https://lwn.net/Articles/777036/
> > > > > > > > ] ).
> > > > > > > > > >>> I do not understand how we reason/dresibe/compare the
> > > > consistency
> > > > > > > > guarantees. (
> > > > > > > > > >>> I even do not know what consistency guarantees provided
> > by
> > > > RCU
> > > > > > > > formally)
> > > > > > > > > >>> Could someone explain this to me?
> > > > > > > > >
> > > > > > > > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A.,
> > > > > > Hellerstein,
> > > > > > > > J. M., &
> > > > > > > > > >>> Stoica, I. (2013). Highly available transactions:
> > Virtues and
> > > > > > > > limitations.
> > > > > > > > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.
> > > > > > > > >
> > > > > > > > > >>> Thanks
> > > > > > > > > >>> Yuxin
> > > > > > > > >
> > > > > > > > > >>> _______________________________________________
> > > > > > > > > >>> lttng-dev mailing list
> > > > > > > > > >>> [ mailto:lttng-dev@lists.lttng.org |
> > > > lttng-dev@lists.lttng.org ]
> > > > > > > > > >>> [
> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> > > > |
> > > > > > > > > >>>
> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]
> > > > > > > > >
> > > > > > > > > >> --
> > > > > > > > > >> Mathieu Desnoyers
> > > > > > > > > >> EfficiOS Inc.
> > > > > > > > > >> [ http://www.efficios.com/ | http://www.efficios.com ]
> > > > > > > > >
> > > > > > > > > --
> > > > > > > > > Mathieu Desnoyers
> > > > > > > > > EfficiOS Inc.
> > > > > > > > > http://www.efficios.com
> > > > > > > >
> > > > > >
> > > >
> >
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

RCU consistency guarantees

[Yuxin Ren]

[-- Attachment #1.1: Type: text/plain, Size: 978 bytes --]

Hi,

I am a student, and learning RCU now, but still know very little about it.
Are there any documents/papers/materials which (in)formally define and
explain RCU consistency guarantees?

I know there are some consistency models in the database area (such as
PRAM, Read Uncommitted, etc) from https://jepsen.io/consistency and [1].
How does RCU related to those consistency models?

I also found some comments online (One key distinction is that both MVCC
and RLU provide much stronger consistency guarantees to readers than does
RCU ...) (https://lwn.net/Articles/777036/).
I do not understand how we reason/dresibe/compare the
consistency guarantees. ( I even do not know what consistency guarantees
provided by RCU formally)
Could someone explain this to me?

[1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M., &
Stoica, I. (2013). Highly available transactions: Virtues and limitations.
Proceedings of the VLDB Endowment, 7(3), 181-192.

Thanks
Yuxin

[-- Attachment #1.2: Type: text/html, Size: 1333 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

RCU consistency guarantees

[Yuxin Ren]

[-- Attachment #1.1: Type: text/plain, Size: 978 bytes --]

Hi,

I am a student, and learning RCU now, but still know very little about it.
Are there any documents/papers/materials which (in)formally define and
explain RCU consistency guarantees?

I know there are some consistency models in the database area (such as
PRAM, Read Uncommitted, etc) from https://jepsen.io/consistency and [1].
How does RCU related to those consistency models?

I also found some comments online (One key distinction is that both MVCC
and RLU provide much stronger consistency guarantees to readers than does
RCU ...) (https://lwn.net/Articles/777036/).
I do not understand how we reason/dresibe/compare the
consistency guarantees. ( I even do not know what consistency guarantees
provided by RCU formally)
Could someone explain this to me?

[1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M., &
Stoica, I. (2013). Highly available transactions: Virtues and limitations.
Proceedings of the VLDB Endowment, 7(3), 181-192.

Thanks
Yuxin

[-- Attachment #1.2: Type: text/html, Size: 1271 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev