[lttng-dev] RCU consistency guarantees
Yuxin Ren
ryx at gwmail.gwu.edu
Sun Dec 15 17:10:11 EST 2019
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
...
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 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
> > > > > > >
> > > > >
> > >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.lttng.org/pipermail/lttng-dev/attachments/20191215/f1b198ee/attachment-0001.html>
More information about the lttng-dev
mailing list