From mboxrd@z Thu Jan 1 00:00:00 1970 From: Yuxin Ren Subject: Re: RCU consistency guarantees Date: Sat, 7 Dec 2019 15:04:42 -0500 Message-ID: References: <194534011.751.1575629349181.JavaMail.zimbra@efficios.com> <512711764.1078.1575647945136.JavaMail.zimbra@efficios.com> <20191206163052.GG2889@paulmck-ThinkPad-P72> <20191207063730.GN2889@paulmck-ThinkPad-P72> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="===============4566789761914688777==" Return-path: Received: from mail-lj1-x241.google.com (mail-lj1-x241.google.com [IPv6:2a00:1450:4864:20::241]) by lists.lttng.org (Postfix) with ESMTPS id 47VgRG6dV4z131q for ; Sat, 7 Dec 2019 15:04:58 -0500 (EST) Received: by mail-lj1-x241.google.com with SMTP id 21so11328758ljr.0 for ; Sat, 07 Dec 2019 12:04:58 -0800 (PST) In-Reply-To: <20191207063730.GN2889@paulmck-ThinkPad-P72> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: lttng-dev-bounces@lists.lttng.org Sender: "lttng-dev" To: paulmck@kernel.org Cc: lttng-dev List-Id: lttng-dev@lists.lttng.org --===============4566789761914688777== Content-Type: multipart/alternative; boundary="000000000000301204059922ad8b" --000000000000301204059922ad8b Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Thanks a lot for your help. I have some questions below. On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney 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 do= es > > 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 > wrote: > > > > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote: > > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren > 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 littl= e > > > 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 > > > > >> =C2=B7 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 designe= d > 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/LWNLinuxM= M/ > > > > > > With these two likely being of particular interest: > > > > > > > > > > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxM= M/RCUguarantees.html > > > > > > > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxM= M/srcu.html > > > > > > o Frightening Small Children and Disconcerting Grown-ups: > > > Concurrency in the Linux Kernel > > > https://dl.acm.org/citation.cfm?id=3D3177156 > > > 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 do= es > > > RCU ...) ( [ > > > > >>> https://lwn.net/Articles/777036/ | > https://lwn.net/Articles/777036/ > > > ] ). > > > > >>> I do not understand how we reason/dresibe/compare the consisten= cy > > > 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 > > > > --000000000000301204059922ad8b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Thanks a lot for your help. I have some q= uestions below.

On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <paulmck@kernel.org> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">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 d= oes
> RCU ...) (https://lwn.net/Articles/777036/).

That someone was in fact me.=C2=A0 ;-)

> 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 (suc= h as
> RLU)?
> How to reason about which one has stronger or weaker guarantees?

I suggest starting from the use case.=C2=A0 For concreteness, let's ass= ume
that we are using a hash table.=C2=A0 At one extreme, imagine a use case in=
which each event makes exactly one hash-table operation.=C2=A0 No informati= on
is carried from one event to the next.=C2=A0 (This might well be the case for simple web server.)=C2=A0 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.=C2=A0 In this case, MVCC/RLU will rule<= br> out outcomes that RCU would permit.=C2=A0 For example, suppose we had four<= br> events accessing two different elements in different buckets of the
hash table:

=C2=A0 =C2=A0 =C2=A0 =C2=A0 E1: Adds 32 to the hash table.
=C2=A0 =C2=A0 =C2=A0 =C2=A0 E2: Adds 1729 to the hash table.
=C2=A0 =C2=A0 =C2=A0 =C2=A0 E3: Within a read-side critical section, looks = up 32 then 1729.
=C2=A0 =C2=A0 =C2=A0 =C2=A0 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.=C2=A0 Given R= CU,
this outcome is possible.
When you say "Within a = read-side section", do you mean within a single same read section? suc= h as
read_lock()
= lookup(32)
lookup(1729)
read_unlock()

How about putting two lookups into two read-side sections? Do we still hav= e the problem, then?=C2=A0
read_lock()
lookup(32)
read_unlock()
read_lock()
loo= kup(1729)
read_unlock()

Could you kindly= give me more clues why RCU can see such reorder, while RLU can prevent it?=
=C2=A0
This is because MVCC and RLU provide readers a consistent view of
the updates, and RCU does not.=C2=A0 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.=C2=A0 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.=C2=A0 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 e= verywhere, not only bound to RCU, but also=C2=A0 any other synchronization= =C2=A0approach (such RLU).
If so, how do others (RLU) provide=C2= =A0consistent views?

Thanks for your education.
Yuxin

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 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> wrot= e:
> > >
> > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [=
> > > > mailto:mathieu.desnoyers@efficios.com | mathieu.desnoyers@efficio= s.com
> > ] >
> > > > wrote:
> > >
> > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ = mailto:
> > ryx@gwmai= l.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 Distri= buted Systems
> > 23(2):375 - 382
> > > >> =C2=B7 March 2012
> > >
> > > > Thanks for your info.
> > > > However, I do not think URCU talks about any consistenc= y model
> > formally.
> > >
> > > > From previous communication with Paul, he said RCU is n= ot designed for
> > > > linearizability, and it is totally acceptable that RCU = is not
> > linearizable.
> > > > However, I am curious how to accurately/formally Charac= terize RCU
> > consistency
> > > > model/guarantees
> > >
> > > Adding Paul E. McKenney in CC.
> > >
> > > I am referring to the section "Overview of RCU semantic= s" in the paper.
> > Not sure it has the level of
> > > formality you are looking for though. Paul, do you have poin= ters to
> > additional material ?
> >
> > Indeed I do!=C2=A0 The Linux kernel memory model (LKMM) includes = RCU.=C2=A0 It is
> > in tools/memory-model in recent kernel source trees, which includ= es
> > documentation.=C2=A0 This is an executable model, which means tha= t you
> > can create litmus tests and have the model formally and automatic= ally
> > evaluate them.
> >
> > There are also a number of publications covering LKMM:
> >
> > o=C2=A0 =C2=A0 =C2=A0 =C2=A0A formal kernel memory-ordering model=
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0https://lwn.net/Articles/= 718628/
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0https://lwn.net/Articles/= 720550/
> >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0These cover the release stores a= nd dependency ordering that
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0provide RCU's publish-subscr= ibe guarantees.
> >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Backup material here:
> >
> >
> > https://mirrors= .edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/
> >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0With these two likely being of p= articular interest:
> >
> >
> > https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinux= MM/RCUguarantees.html
> >
> > https:= //mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.h= tml
> >
> > o=C2=A0 =C2=A0 =C2=A0 =C2=A0Frightening Small Children and Discon= certing Grown-ups:
> > Concurrency in the Linux Kernel
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0https://dl.ac= m.org/citation.cfm?id=3D3177156
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf
> >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Backup material:
> >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0http://diy.inria.fr/linux/<= br> > >
> > o=C2=A0 =C2=A0 =C2=A0 =C2=A0Who's afraid of a big bad optimiz= ing compiler?
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0https://lwn.net/Articles/= 793253/
> >
> > o=C2=A0 =C2=A0 =C2=A0 =C2=A0Calibrating your fear of big bad opti= mizing compilers
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0https://lwn.net/Articles/= 799218/
> >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0These last two justify use of no= rmal C-language assignment
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0statements to initialize and acc= ess data referenced by
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0RCU-protected pointers.
> >
> > There is a large body of litmus tests (thousands of them) here: > >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0https://github.com/pa= ulmckrcu/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?
> >
> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Thanx, 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://jepse= n.io/consistency |
> > > >>> https://jepsen.io/consistency ] and [= 1].
> > > >>> How does RCU related to those consistency model= s?
> > >
> > > >>> I also found some comments online (One key dist= inction is that both
> > MVCC and RLU
> > > >>> provide much stronger consistency guarantees to= readers than does
> > RCU ...) ( [
> > > >>> https://lwn.net/Articles/777036/ | <= a href=3D"https://lwn.net/Articles/777036/" rel=3D"noreferrer" target=3D"_b= lank">https://lwn.net/Articles/777036/
> > ] ).
> > > >>> I do not understand how we reason/dresibe/compa= re 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., Ghods= i, A., Hellerstein,
> > J. M., &
> > > >>> Stoica, I. (2013). Highly available transaction= s: Virtues and
> > limitations.
> > > >>> Proceedings of the VLDB Endowment, 7(3), 181-19= 2.
> > >
> > > >>> Thanks
> > > >>> Yuxin
> > >
> > > >>> _______________________________________________=
> > > >>> lttng-dev mailing list
> > > >>> [ mailto:lttng-dev@lists.lttng.org | lttng-dev@lists.lttng.org = ]
> > > >>> [ https://list= s.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.c= om ]
> > >
> > > --
> > > Mathieu Desnoyers
> > > EfficiOS Inc.
> > > http://www.efficios.com
> >
--000000000000301204059922ad8b-- --===============4566789761914688777== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev --===============4566789761914688777==--