Messages in this thread | | | Date | Thu, 16 Jun 2011 10:40:16 +0800 | From | Lai Jiangshan <> | Subject | Re: [PATCH] rcu,doc: lock-free update site |
| |
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.
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" >
| |