lttng-dev.lists.lttng.org archive mirror
 help / color / mirror / Atom feed
From: Yuxin Ren <ryx@gwmail.gwu.edu>
To: paulmck@kernel.org
Cc: lttng-dev <lttng-dev@lists.lttng.org>
Subject: Re: RCU consistency guarantees
Date: Sat, 14 Dec 2019 01:31:31 -0500	[thread overview]
Message-ID: <CAAKbDrd5s06mnPYU_dwO1+dtySewm80ukaaEqJiJ0RtkFe-38w__31265.3649061517$1576305131$gmane$org@mail.gmail.com> (raw)
In-Reply-To: <20191207224232.GR2889@paulmck-ThinkPad-P72>


[-- Attachment #1.1: Type: text/plain, Size: 14972 bytes --]

Hi Paul

On Sat, Dec 7, 2019 at 5:42 PM Paul E. McKenney <paulmck@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@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 <paulmck@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@gwmail.gwu.edu>
> > > wrote:
> > > > > >
> > > > > > > On Fri, Dec 6, 2019 at 5:49 AM Mathieu Desnoyers < [
> > > > > > > mailto:mathieu.desnoyers@efficios.com |
> > > mathieu.desnoyers@efficios.com
> > > > > ] >
> > > > > > > wrote:
> > > > > >
> > > > > > >> ----- On Dec 5, 2019, at 8:17 PM, Yuxin Ren < [ mailto:
> > > > > ryx@gwmail.gwu.edu |
> > > > > > >> ryx@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
> > > > >
> > >
>

[-- Attachment #1.2: Type: text/html, Size: 22321 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

  parent reply	other threads:[~2019-12-14  6:31 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <CAAKbDrdMRrhnSzpPBZLf3nNUDW4YZLPkZkTD5gNJu+A9rATkWA@mail.gmail.com>
2019-12-06 10:49 ` RCU consistency guarantees Mathieu Desnoyers
     [not found] ` <194534011.751.1575629349181.JavaMail.zimbra@efficios.com>
2019-12-06 14:51   ` Yuxin Ren
     [not found]   ` <CAAKbDreZ8NerP-jsxezOmN3rktVSAk1a=RJw2YQY83UpQRrXfQ@mail.gmail.com>
2019-12-06 15:59     ` Mathieu Desnoyers
     [not found]     ` <512711764.1078.1575647945136.JavaMail.zimbra@efficios.com>
2019-12-06 16:30       ` Paul E. McKenney
     [not found]       ` <20191206163052.GG2889@paulmck-ThinkPad-P72>
2019-12-07  0:00         ` Yuxin Ren
     [not found]         ` <CAAKbDrfzbaPJcKQE7wsjPCgmxUMhcZshDptt=abtufbtCMp85g@mail.gmail.com>
2019-12-07  6:37           ` Paul E. McKenney
     [not found]           ` <20191207063730.GN2889@paulmck-ThinkPad-P72>
2019-12-07 20:04             ` Yuxin Ren
     [not found]             ` <CAAKbDre3N=RwTNeAqbr3MaA+zuioriLFasd85ZJsFr_pG_VApw@mail.gmail.com>
2019-12-07 22:42               ` Paul E. McKenney
     [not found]               ` <20191207224232.GR2889@paulmck-ThinkPad-P72>
2019-12-14  6:31                 ` Yuxin Ren [this message]
     [not found]                 ` <CAAKbDrd5s06mnPYU_dwO1+dtySewm80ukaaEqJiJ0RtkFe-38w@mail.gmail.com>
2019-12-15 20:30                   ` Paul E. McKenney
     [not found]                   ` <20191215203019.GN2889@paulmck-ThinkPad-P72>
2019-12-15 22:10                     ` Yuxin Ren
     [not found]                     ` <CAAKbDrfUGrL=Yz=mf4B1Wij3XkxgTwY-4HNB4+XJKdRGK1T2BQ@mail.gmail.com>
2019-12-16  0:57                       ` Paul E. McKenney
2019-12-06  1:17 Yuxin Ren
  -- strict thread matches above, loose matches on Subject: below --
2019-12-06  1:15 Yuxin Ren

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAAKbDrd5s06mnPYU_dwO1+dtySewm80ukaaEqJiJ0RtkFe-38w__31265.3649061517$1576305131$gmane$org@mail.gmail.com' \
    --to=ryx@gwmail.gwu.edu \
    --cc=lttng-dev@lists.lttng.org \
    --cc=paulmck@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).