lkml.org 
[lkml]   [2011]   [Jun]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH] rcu,doc: lock-free update site
    On Thu, Jun 16, 2011 at 10:40:16AM +0800, Lai Jiangshan wrote:
    > On 06/14/2011 08:50 PM, Mathieu Desnoyers wrote:
    > > * Lai Jiangshan (laijs@cn.fujitsu.com) wrote:
    > >> Add a document which describes a pattern of using RCU to implement lock-free(lockless)
    > >> update site.
    > >>
    > > [...]
    > >> @@ -0,0 +1,143 @@
    > >> +Lock-free(lockless) update site
    > >> +
    > >> +This article describes a pattern of using RCU to implement lock-free(lockless)
    > >> +update site. RCU update site is considered call-rare and it is protected
    > >> +by a update-site lock generally. But blocking algorithms are undesirable
    > >> +in some cases for some reasons, thus, this pattern may help.
    > >
    > > Hi Lai,
    > >
    > > Yes, using this kind of rcu read-side lock to protect against the
    > > cmpxchg ABA problem is well-known (to me at least) ;) I used this
    > > technique in the userspace RCU library "lock-free queue" and "lock-free
    > > stack" in 2010*. Please feel free to dig through my RCU data containers code
    > > to bring in more data structure examples:
    > >
    > > http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/static/rculfqueue.h;h=b627e450cfdd581692b474d89437e3fd47f18463;hb=HEAD
    > >
    > > http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/static/rculfqueue.h;h=b627e450cfdd581692b474d89437e3fd47f18463;hb=HEAD
    > >
    > > Thanks!
    > >
    > > Mathieu
    >
    >
    > Hi, Mathieu
    >
    > I will try to make simple update site wait-free, so I wrote a simple guide/document
    > at first. I didn't notice your work. Your work is excellent,
    > I will add some references. I hope you rewrite/pretty this document also.
    >
    > The lock-free stack is a good example, but the lock-free queue is not good here I think.

    I look forward to seeing the update!

    Thanx, Paul

    > Thanks,
    > Lai
    >
    >
    > >
    > > * AFAIK I introduced this technique using RCU read-side C.S. to deal
    > > with cmpxchg ABA at that point, but someone might have thought about
    > > it before me without my knowledge. My litterature survey so far
    > > indicates that using a double-word CAS on a pointer/counter was one of
    > > the usual technique used to protect against cmpxchg ABA so far. Other
    > > techniques imply allocating elements in a limited-size array (so a
    > > simple cmpxchg can update the array index and counter atomically),
    > > Hasard Pointers, or having a full-blown GC which provides similar
    > > guarantees to the RCU grace period with a read-side lock held.
    > > Ref.:
    > >
    > > [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
    > > [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes"
    > > [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
    > >
    >
    > --
    > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    > the body of a message to majordomo@vger.kernel.org
    > More majordomo info at http://vger.kernel.org/majordomo-info.html
    > Please read the FAQ at http://www.tux.org/lkml/


    \
     
     \ /
      Last update: 2011-06-16 06:09    [W:0.030 / U:29.580 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site