Hi Paul On Sat, Dec 7, 2019 at 5:42 PM Paul E. McKenney <paul...@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 <paul...@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] > #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. 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? 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 <paul...@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 <r...@gwmail.gwu.edu> > > > wrote: > > > > > > > > > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [ > > > > > > > mailto:mathieu.desnoy...@efficios.com | > > > mathieu.desnoy...@efficios.com > > > > > ] > > > > > > > > wrote: > > > > > > > > > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto: > > > > > r...@gwmail.gwu.edu | > > > > > > >> r...@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@lists.lttng.org | > lttng-dev@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 > > > > > > > > >
_______________________________________________ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
