[lttng-dev] RCU consistency guarantees
Paul E. McKenney
paulmck at kernel.org
Sun Dec 15 15:30:19 EST 2019
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 at 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 at 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 at 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 at gwmail.gwu.edu>
> > > > wrote:
> > > > > > >
> > > > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > > > > mailto:mathieu.desnoyers at efficios.com |
> > > > mathieu.desnoyers at efficios.com
> > > > > > ] >
> > > > > > > > wrote:
> > > > > > >
> > > > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > > > > ryx at gwmail.gwu.edu |
> > > > > > > >> ryx at 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 at lists.lttng.org |
> > lttng-dev at 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
> > > > > >
> > > >
> >
More information about the lttng-dev
mailing list