Messages in this thread | | | Date | Thu, 20 Jan 2011 16:57:06 +0800 | Subject | Re: [PATCH -v10 0/4] Lock-less list | From | huang ying <> |
| |
Hi, Mathieu,
On Thu, Jan 20, 2011 at 1:55 PM, Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote: > Hi Huang, > > I just found out about your lockless linked-list implementation, it looks > interesting. Paul McKenney and myself have created a similar implementation for > userspace within the Userspace RCU project, you might want to have a look (it's > LGPLv2.1). > > One point about semantic: a singly-linked list for which you can either delete > the first element or all the elements should probably be called a stack ? I'm > therefore going to refer to "push/pop" in this email rather than "add/delete". > > We've got two linked-list stack implementations in the userspace RCU tree: > > One has wait-free push, and blocking pop. Useful if you can afford to block when > you pop from the list. There is no restriction on the number of concurrent > push/pop to/from the list. The code is at: > > http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/wfstack-static.h > > The other has lock-free push and pop, no restriction on the number of concurrent > push/pop, but uses a clever trick that ensures that the cmpxchg loop will never > see a re-used pointer by using a RCU read-side to protect from memory reclaim. > It therefore requires that the memory used for the list must only be freed after > a RCU grace period. The code is at: > > http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/rculfstack-static.h > > We could probably extend this to allow popping all stack entries in one go, but > I haven't given it much thought. > > We also have queue implementations (enqueue at head, dequeue at tail). The first > has wait-free enqueue/blocking dequeue and the second has lock-free > enqueue/dequeue. We use the wait-free enqueue/blocking dequeue queue to push > RCU callbacks when call_rcu() is executed from real-time threads, and we then > dequeue the callbacks to execute with a blocking thread. The lock-free > enqueue/dequeue queue also needs a reference count on the "dummy" node it keeps > in addition to use RCU to delay memory reclamation (see comments in the code). > > wait-free enqueue/blocking dequeue: > > http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/wfqueue-static.h > > lock-free enqueue/dequeue (beware, the refcounting makes the API less elegant > than the other implementations): > > http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/rculfqueue-static.h > > Hoping this might be helpful to you,
Thanks! I will investigate your code!
Best Regards, Huang Ying
| |