<div dir="ltr"><div dir="ltr">Hi Paul</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Dec 7, 2019 at 5:42 PM Paul E. McKenney <<a href="mailto:paulmck@kernel.org" target="_blank">paulmck@kernel.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Sat, Dec 07, 2019 at 03:04:42PM -0500, Yuxin Ren wrote:<br>
> Thanks a lot for your help. I have some questions below.<br>
> <br>
> On Sat, Dec 7, 2019 at 1:37 AM Paul E. McKenney <<a href="mailto:paulmck@kernel.org" target="_blank">paulmck@kernel.org</a>> wrote:<br>
> <br>
> > On Fri, Dec 06, 2019 at 07:00:13PM -0500, Yuxin Ren wrote:<br>
> > > Thanks so much for your great help.<br>
> > > I definitely will look at those resources and papers!<br>
> > ><br>
> > > One more thing that I am confused<br>
> > > As I mentioned earlier, someone said One key distinction is that both<br>
> > MVCC<br>
> > > and RLU provide much stronger consistency guarantees to readers than does<br>
> > > RCU ...) (<a href="https://lwn.net/Articles/777036/" rel="noreferrer" target="_blank">https://lwn.net/Articles/777036/</a>).<br>
> ><br>
> > That someone was in fact me. ;-)<br>
> ><br>
> > > I am not sure if the above statement is correct or not. But in general,<br>
> > > How can we compare RCU consistency guarantees to other techniques (such<br>
> > as<br>
> > > RLU)?<br>
> > > How to reason about which one has stronger or weaker guarantees?<br>
> ><br>
> > I suggest starting from the use case. For concreteness, let's assume<br>
> > that we are using a hash table. At one extreme, imagine a use case in<br>
> > which each event makes exactly one hash-table operation. No information<br>
> > is carried from one event to the next. (This might well be the case<br>
> > for simple web server.) Such a use case cannot tell the difference<br>
> > between RCU on the one hand and MVCC/RLU on the other.<br>
> ><br>
> > At the other extreme, suppose that each event either accesses or updates<br>
> > multiple entries in the hash table. In this case, MVCC/RLU will rule<br>
> > out outcomes that RCU would permit. For example, suppose we had four<br>
> > events accessing two different elements in different buckets of the<br>
> > hash table:<br>
> ><br>
> > E1: Adds 32 to the hash table.<br>
> > E2: Adds 1729 to the hash table.<br>
> > E3: Within a read-side critical section, looks up 32 then 1729.<br>
> > E4: Within a read-side critical section, looks up 1729 then 32.<br>
> ><br>
> > Given either MVCC or RLU, it will not be possible for E3 to find 32 but<br>
> > not 1729 and at the same time for E4 to find 1729 but not 32. Given RCU,<br>
> > this outcome is possible.<br>
> ><br>
> When you say "Within a read-side section", do you mean within a single same<br>
> read section? such as<br>
> <br>
> > read_lock()<br>
> > lookup(32)<br>
> > lookup(1729)<br>
> > read_unlock()<br>
> <br>
> <br>
> How about putting two lookups into two read-side sections? Do we still have<br>
> the problem, then?<br>
> <br>
> > read_lock()<br>
> > lookup(32)<br>
> > read_unlock()<br>
> > read_lock()<br>
> > lookup(1729)<br>
> > read_unlock()<br>
<br>
Without in any way agreeing with your characterization of this as a<br>
problem, because rcu_read_lock() and rcu_read_unlock() provide<br>
absolutely no ordering guarantees in the absence of a grace period,<br>
any non-grace-period-related reordering that can happen with a single<br>
RCU read-side critical section can also happen when that critical<br>
section is split in two as you have done above.<br>
<br>
> Could you kindly give me more clues why RCU can see such reorder, while RLU<br>
> can prevent it?<br>
<br>
Here are minimal C-language implementations for RCU that can (and are)<br>
actually used:<br></blockquote><div>Great. We use the same thing in our real-time work [1] <br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
#define rcu_read_lock()<br>
#define rcu_read_unlock()<br>
<br>
Please compare these to the read-side markers presented in the RLU paper,<br>
and then tell me your thoughts on the answer to your question. ;-)<br></blockquote><div>I submit my homework here, but I do not think I did it well.</div><div>1. I believe in the default URCU implementation, it has memory barrier inside the read_lock / read_unlock.</div><div>2. From the RLU paper, it shows the code for read-side operation.</div><div>RLU_READER_LOCK(ctx)</div><div> ctx.is-writer←false</div><div> ctx.run-cnt←ctx.run-cnt+1.</div><div> memory fence</div><div> ctx.local-clock←global-clock</div><div>RLU_READER_UNLOCK(ctx)</div><div> ctx.run-cnt←ctx.run-cnt+1</div><div> if (ctx.is-writer)</div><div> RLU_COMMIT_WRITE_LOG(ctx)</div><div><br></div><div>We can ignore the writer check, as in our case, the reader never do update.</div><div>My understanding is that read-side operations are only used to facilitate the quiescence detection.</div><div>the run cnt is used to decide if a thread is active (if it is currently inside a read-side section).</div><div>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.</div><div>However i see no difference between RLU and RCU read-side operation regarding consistency guarantee.</div><div>Could you kindly teach me more?</div><div><br></div><div>BTW, the RLU read-side ops are similar, but not efficient, comparing to our Parsec work [1, 2]</div><div>[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</div><div>[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</div><div><br></div><div>Thanks,</div><div>Best,</div><div>Yuxin<br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
> > This is because MVCC and RLU provide readers a consistent view of<br>
> > the updates, and RCU does not. Of course, it is often the case that a<br>
> > consistent view is not needed, in which case the MVCC and RLU guarantees<br>
> > are incurring read-side overhead for no reason. But if the use case<br>
> > requires consistent readers, RCU is not an option.<br>
> ><br>
> > The reason a consistent view is not always needed is that speed-of-light<br>
> > delays make it impossible to provide a consistent view of the outside<br>
> > world. In the common case where the use case interacts with the<br>
> > outside world, the algorithms absolutely must be designed to tolerate<br>
> > inconsistency, which opens the door to things like RCU.<br>
> <br>
> I am confused here. I think speed-of-light delays happen everywhere, not<br>
> only bound to RCU, but also any other synchronization approach (such RLU).<br>
> If so, how do others (RLU) provide consistent views?<br>
<br>
You just stated the answer. Now it is only necessary for you to invest<br>
the time, effort, and thought to fully understand it. To help with this,<br>
the following paragraph provides another hint:<br>
<br>
Yes, you are quite right, speed-of-light delays between the<br>
outside world and the computer affect RLU just as surely as they<br>
do RCU. This means that the additional consistency guarantees<br>
provided by RLU must necessarily be limited to the confines of the<br>
computer system in question. Taking this one step further, there<br>
are also speed-of-light delays within the computer. Therefore,<br>
in the general case, RLU can provide its consistency guarantees,<br>
even within the confines of the computer system, only at the<br>
expense of incurring delays. Because RCU does not provide RLU's<br>
consistency guarantees, it need not incur RLU's delays.<br>
<br>
This is not a new line of reasoning, see for example:<br>
<br>
@article{Herlihy:1996:LCN:1063369.1063372<br>
,author = {Herlihy, Maurice and Shavit, Nir and Waarts, Orli}<br>
,title = {Linearizable counting networks}<br>
,journal = {Distrib. Comput.}<br>
,volume = {9}<br>
,issue = {4}<br>
,month = {February}<br>
,year = {1996}<br>
,issn = {0178-2770}<br>
,pages = {193--203}<br>
,numpages = {11}<br>
,url = {<a href="http://portal.acm.org/citation.cfm?id=1063369.1063372" rel="noreferrer" target="_blank">http://portal.acm.org/citation.cfm?id=1063369.1063372</a>}<br>
,doi = {10.1007/s004460050019}<br>
,acmid = {1063372}<br>
,publisher = {Springer-Verlag}<br>
,address = {London, UK}<br>
,keywords = {concurrency, contention, counting networks, data structures, linearizability}<br>
}<br>
<br>
Thanx, Paul<br>
<br>
> Thanks for your education.<br>
> Yuxin<br>
> <br>
> ><br>
> > Thanx, Paul<br>
> ><br>
> > > Thanks<br>
> > > Yuxin<br>
> > ><br>
> > > On Fri, Dec 6, 2019 at 11:30 AM Paul E. McKenney <<a href="mailto:paulmck@kernel.org" target="_blank">paulmck@kernel.org</a>><br>
> > wrote:<br>
> > ><br>
> > > > On Fri, Dec 06, 2019 at 10:59:05AM -0500, Mathieu Desnoyers wrote:<br>
> > > > > ----- On Dec 6, 2019, at 3:51 PM, Yuxin Ren <<a href="mailto:ryx@gwmail.gwu.edu" target="_blank">ryx@gwmail.gwu.edu</a>><br>
> > wrote:<br>
> > > > ><br>
> > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [<br>
> > > > > > mailto:<a href="mailto:mathieu.desnoyers@efficios.com" target="_blank">mathieu.desnoyers@efficios.com</a> |<br>
> > <a href="mailto:mathieu.desnoyers@efficios.com" target="_blank">mathieu.desnoyers@efficios.com</a><br>
> > > > ] ><br>
> > > > > > wrote:<br>
> > > > ><br>
> > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:<br>
> > > > <a href="mailto:ryx@gwmail.gwu.edu" target="_blank">ryx@gwmail.gwu.edu</a> |<br>
> > > > > >> <a href="mailto:ryx@gwmail.gwu.edu" target="_blank">ryx@gwmail.gwu.edu</a> ] > wrote:<br>
> > > > ><br>
> > > > > >>> Hi,<br>
> > > > > >>> I am a student, and learning RCU now, but still know very little<br>
> > > > about it.<br>
> > > > > >>> Are there any documents/papers/materials which (in)formally<br>
> > define<br>
> > > > and explain<br>
> > > > > >>> RCU consistency guarantees?<br>
> > > > ><br>
> > > > > >> You may want to have a look at<br>
> > > > ><br>
> > > > > >> User-Level Implementations of Read-Copy Update<br>
> > > > > >> Article in IEEE Transactions on Parallel and Distributed Systems<br>
> > > > 23(2):375 - 382<br>
> > > > > >> · March 2012<br>
> > > > ><br>
> > > > > > Thanks for your info.<br>
> > > > > > However, I do not think URCU talks about any consistency model<br>
> > > > formally.<br>
> > > > ><br>
> > > > > > From previous communication with Paul, he said RCU is not designed<br>
> > for<br>
> > > > > > linearizability, and it is totally acceptable that RCU is not<br>
> > > > linearizable.<br>
> > > > > > However, I am curious how to accurately/formally Characterize RCU<br>
> > > > consistency<br>
> > > > > > model/guarantees<br>
> > > > ><br>
> > > > > Adding Paul E. McKenney in CC.<br>
> > > > ><br>
> > > > > I am referring to the section "Overview of RCU semantics" in the<br>
> > paper.<br>
> > > > Not sure it has the level of<br>
> > > > > formality you are looking for though. Paul, do you have pointers to<br>
> > > > additional material ?<br>
> > > ><br>
> > > > Indeed I do! The Linux kernel memory model (LKMM) includes RCU. It is<br>
> > > > in tools/memory-model in recent kernel source trees, which includes<br>
> > > > documentation. This is an executable model, which means that you<br>
> > > > can create litmus tests and have the model formally and automatically<br>
> > > > evaluate them.<br>
> > > ><br>
> > > > There are also a number of publications covering LKMM:<br>
> > > ><br>
> > > > o A formal kernel memory-ordering model<br>
> > > > <a href="https://lwn.net/Articles/718628/" rel="noreferrer" target="_blank">https://lwn.net/Articles/718628/</a><br>
> > > > <a href="https://lwn.net/Articles/720550/" rel="noreferrer" target="_blank">https://lwn.net/Articles/720550/</a><br>
> > > ><br>
> > > > These cover the release stores and dependency ordering that<br>
> > > > provide RCU's publish-subscribe guarantees.<br>
> > > ><br>
> > > > Backup material here:<br>
> > > ><br>
> > > ><br>
> > > ><br>
> > <a href="https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/" rel="noreferrer" target="_blank">https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/</a><br>
> > > ><br>
> > > > With these two likely being of particular interest:<br>
> > > ><br>
> > > ><br>
> > > ><br>
> > <a href="https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html" rel="noreferrer" target="_blank">https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/RCUguarantees.html</a><br>
> > > ><br>
> > > ><br>
> > <a href="https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html" rel="noreferrer" target="_blank">https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/srcu.html</a><br>
> > > ><br>
> > > > o Frightening Small Children and Disconcerting Grown-ups:<br>
> > > > Concurrency in the Linux Kernel<br>
> > > > <a href="https://dl.acm.org/citation.cfm?id=3177156" rel="noreferrer" target="_blank">https://dl.acm.org/citation.cfm?id=3177156</a><br>
> > > > <a href="http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf" rel="noreferrer" target="_blank">http://www0.cs.ucl.ac.uk/staff/j.alglave/papers/asplos18.pdf</a><br>
> > > ><br>
> > > > Backup material:<br>
> > > ><br>
> > > > <a href="http://diy.inria.fr/linux/" rel="noreferrer" target="_blank">http://diy.inria.fr/linux/</a><br>
> > > ><br>
> > > > o Who's afraid of a big bad optimizing compiler?<br>
> > > > <a href="https://lwn.net/Articles/793253/" rel="noreferrer" target="_blank">https://lwn.net/Articles/793253/</a><br>
> > > ><br>
> > > > o Calibrating your fear of big bad optimizing compilers<br>
> > > > <a href="https://lwn.net/Articles/799218/" rel="noreferrer" target="_blank">https://lwn.net/Articles/799218/</a><br>
> > > ><br>
> > > > These last two justify use of normal C-language assignment<br>
> > > > statements to initialize and access data referenced by<br>
> > > > RCU-protected pointers.<br>
> > > ><br>
> > > > There is a large body of litmus tests (thousands of them) here:<br>
> > > ><br>
> > > > <a href="https://github.com/paulmckrcu/litmus" rel="noreferrer" target="_blank">https://github.com/paulmckrcu/litmus</a><br>
> > > ><br>
> > > > Many of these litmus tests involve RCU, and these can be located by<br>
> > > > search for files containing rcu_read_lock(), rcu_read_unlock(),<br>
> > > > synchronize_rcu(), and so on.<br>
> > > ><br>
> > > > Or were you looking for something else?<br>
> > > ><br>
> > > > Thanx, Paul<br>
> > > ><br>
> > > > > Thanks,<br>
> > > > ><br>
> > > > > Mathieu<br>
> > > > ><br>
> > > > > >> as a starting point.<br>
> > > > ><br>
> > > > > >> Thanks,<br>
> > > > ><br>
> > > > > >> Mathieu<br>
> > > > ><br>
> > > > > >>> I know there are some consistency models in the database area<br>
> > (such<br>
> > > > as PRAM,<br>
> > > > > >>> Read Uncommitted, etc) from [ <a href="https://jepsen.io/consistency" rel="noreferrer" target="_blank">https://jepsen.io/consistency</a> |<br>
> > > > > >>> <a href="https://jepsen.io/consistency" rel="noreferrer" target="_blank">https://jepsen.io/consistency</a> ] and [1].<br>
> > > > > >>> How does RCU related to those consistency models?<br>
> > > > ><br>
> > > > > >>> I also found some comments online (One key distinction is that<br>
> > both<br>
> > > > MVCC and RLU<br>
> > > > > >>> provide much stronger consistency guarantees to readers than does<br>
> > > > RCU ...) ( [<br>
> > > > > >>> <a href="https://lwn.net/Articles/777036/" rel="noreferrer" target="_blank">https://lwn.net/Articles/777036/</a> |<br>
> > <a href="https://lwn.net/Articles/777036/" rel="noreferrer" target="_blank">https://lwn.net/Articles/777036/</a><br>
> > > > ] ).<br>
> > > > > >>> I do not understand how we reason/dresibe/compare the consistency<br>
> > > > guarantees. (<br>
> > > > > >>> I even do not know what consistency guarantees provided by RCU<br>
> > > > formally)<br>
> > > > > >>> Could someone explain this to me?<br>
> > > > ><br>
> > > > > >>> [1] Bailis, P., Davidson, A., Fekete, A., Ghodsi, A.,<br>
> > Hellerstein,<br>
> > > > J. M., &<br>
> > > > > >>> Stoica, I. (2013). Highly available transactions: Virtues and<br>
> > > > limitations.<br>
> > > > > >>> Proceedings of the VLDB Endowment, 7(3), 181-192.<br>
> > > > ><br>
> > > > > >>> Thanks<br>
> > > > > >>> Yuxin<br>
> > > > ><br>
> > > > > >>> _______________________________________________<br>
> > > > > >>> lttng-dev mailing list<br>
> > > > > >>> [ mailto:<a href="mailto:lttng-dev@lists.lttng.org" target="_blank">lttng-dev@lists.lttng.org</a> | <a href="mailto:lttng-dev@lists.lttng.org" target="_blank">lttng-dev@lists.lttng.org</a> ]<br>
> > > > > >>> [ <a href="https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev" rel="noreferrer" target="_blank">https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev</a> |<br>
> > > > > >>> <a href="https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev" rel="noreferrer" target="_blank">https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev</a> ]<br>
> > > > ><br>
> > > > > >> --<br>
> > > > > >> Mathieu Desnoyers<br>
> > > > > >> EfficiOS Inc.<br>
> > > > > >> [ <a href="http://www.efficios.com/" rel="noreferrer" target="_blank">http://www.efficios.com/</a> | <a href="http://www.efficios.com" rel="noreferrer" target="_blank">http://www.efficios.com</a> ]<br>
> > > > ><br>
> > > > > --<br>
> > > > > Mathieu Desnoyers<br>
> > > > > EfficiOS Inc.<br>
> > > > > <a href="http://www.efficios.com" rel="noreferrer" target="_blank">http://www.efficios.com</a><br>
> > > ><br>
> ><br>
</blockquote></div></div>