<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Dec 15, 2019 at 3:30 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 14, 2019 at 01:31:31AM -0500, Yuxin Ren wrote:<br>
> Hi Paul<br>
> <br>
> 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>
> <br>
> > 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>><br>
> > 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<br>
> > 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<br>
> > general,<br>
> > > > > How can we compare RCU consistency guarantees to other techniques<br>
> > (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<br>
> > 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<br>
> > 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<br>
> > RCU,<br>
> > > > this outcome is possible.<br>
> > > ><br>
> > > When you say "Within a read-side section", do you mean within a single<br>
> > 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<br>
> > 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<br>
> > RLU<br>
> > > can prevent it?<br>
> ><br>
> > Here are minimal C-language implementations for RCU that can (and are)<br>
> > actually used:<br>
> ><br>
> Great. We use the same thing in our real-time work [1]<br>
<br>
It has been a popular choice for 40 years now. ;-)<br>
<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>
> ><br>
> I submit my homework here, but I do not think I did it well.<br>
> 1. I believe in the default URCU implementation, it has memory barrier<br>
> inside the read_lock / read_unlock.<br>
<br>
It certainly was at one time. But you would of course need to check<br>
to see what any given worker actually used.<br>
<br>
> 2. From the RLU paper, it shows the code for read-side operation.<br>
> RLU_READER_LOCK(ctx)<br>
> ctx.is-writer←false<br>
> ctx.run-cnt←ctx.run-cnt+1.<br>
> memory fence<br>
> ctx.local-clock←global-clock<br>
> RLU_READER_UNLOCK(ctx)<br>
> ctx.run-cnt←ctx.run-cnt+1<br>
> if (ctx.is-writer)<br>
> RLU_COMMIT_WRITE_LOG(ctx)<br>
> <br>
> We can ignore the writer check, as in our case, the reader never do update.<br>
> My understanding is that read-side operations are only used to facilitate<br>
> the quiescence detection.<br>
> the run cnt is used to decide if a thread is active (if it is currently<br>
> inside a read-side section).<br>
> the local clock is used to check if the active thread goes into the<br>
> read-side section very late, so it does not prevent reclaiming memory<br>
> unlinked before it enters the read section.<br>
> However i see no difference between RLU and RCU read-side operation<br>
> regarding consistency guarantee.<br>
> Could you kindly teach me more?<br>
<br>
In order to teach you more, I do need some help from you. I have posted<br>
a number of URLs earlier in this email thread. Could you please tell<br>
me what you learned from each of them?<br></blockquote><div>Sure, I will definitely learn those resources you provided, and come back to you if I have more questions.</div><div>Simply speaking, I failed to find a clear and formal consistency model/guarantee of RCU quickly.<br>The difficulty for me is, for most people, at their first glance, RCU only has relax/weak consistency guarantee. </div><div>So whenever I suggest to use RCU to others, they always ask like</div><div>Does RCU provide Serializability? .. maybe not.</div><div>Does RCU provide Linearizability? ... maybe not</div><div>...</div><div>OK, what does RCU provide? .. I am not sure. I even cannot find a single document which has an accurate answer.</div><div><br></div><div>Let me give more examples.</div><div>1. When I recommend using read-write lock, people are happy to use it.</div><div> 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.</div><div>2. In contrast, in the database area, it has relative clear definition of consistency levels (such as <a href="https://jepsen.io/consistency">https://jepsen.io/consistency</a>), and users are easy to assert if they can use certain database configuration based on its consistency model.</div><div><br></div><div>Again, I really appreciate your patience and communication, hope those does not bother you a lot.</div><div><br></div><div>Thanks</div><div>Best,</div><div>Yuxin</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Thanx, Paul<br>
<br>
> BTW, the RLU read-side ops are similar, but not efficient, comparing to our<br>
> Parsec work [1, 2]<br>
> [1] Yuxin Ren, G. Liu, G. Parmer, B. Brandenburg, Scalable Memory<br>
> Reclamation for Multi-Core, Real-Time Systems, in Proceedings of the 24th<br>
> IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS),<br>
> 2018<br>
> [2] Q. Wang, T. Stamler, and G. Parmer, Parallel Sections: Scaling<br>
> System-Level Data-Structures, in Proceedings of European Conference on<br>
> Computer Systems (EuroSys), 2016<br>
> <br>
> Thanks,<br>
> Best,<br>
> Yuxin<br>
> <br>
> <br>
> > > 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<br>
> > 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<br>
> > 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<br>
> > 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,<br>
> > 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>
> > ><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<br>
> > 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<br>
> > 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<br>
> > 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<br>
> > 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<br>
> > to<br>
> > > > > > additional material ?<br>
> > > > > ><br>
> > > > > > Indeed I do! The Linux kernel memory model (LKMM) includes RCU.<br>
> > 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<br>
> > 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>
> > > ><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>
> > > ><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>
> > > ><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>
> > > > > ><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>
> > |<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<br>
> > that<br>
> > > > both<br>
> > > > > > MVCC and RLU<br>
> > > > > > > >>> provide much stronger consistency guarantees to readers than<br>
> > 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<br>
> > consistency<br>
> > > > > > guarantees. (<br>
> > > > > > > >>> I even do not know what consistency guarantees provided by<br>
> > 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> |<br>
> > <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>
> > |<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>
> ><br>
</blockquote></div></div>