[lttng-dev] RCU consistency guarantees
Paul E. McKenney
paulmck at kernel.org
Sun Dec 15 19:57:39 EST 2019
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 at 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 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?
> >
> 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 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