Read Copy Update

[Doug Rabson]

On Thu, 2004-02-19 at 10:08, Ted Unangst wrote:
> On Wed, 18 Feb 2004, Doug Rabson wrote:
> 
> > I read one of the original papers at
> > http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf and its a
> > surprisingly simple idea. Basically for certain data structures which
> > are read-mostly, you can make the entire read path lock-free at the
> > expense of making updates quite a bit more expensive. They claim that
> > its much faster than reader-writer locks both for light contention and
> > for heavy contention.
> 
> consider the following for the linked list example given. A -> B -> C
> 
> thread 0 was changing B.   creates B', links A -> B' -> C.  waits for
> quiet time, free(B).
> 
> thread 1 is walking list.  when it's done, signals quiet time.
> 
> what if both threads want to change B?
> 
> thread 0 walks list to B.
> 		thread 1 walks list to B.
> thread 0 creates B'.
> 		thread 1 creates B''.
> thread 0 links list A -> B' -> C
> 		thread 1 links list A -> B'' -> C
> thread 0 creates callback.
> 		thread 1 creates callback.
> thread 0 callback runs, free(B).
> 		thread 1 callback runs, free(B).  *boom*
> 
> excuse me if i missed it, but i didn't see this addressed in the paper.

This is mentioned in the paper where they say that 'Thread 0 must use
some sort of update discipline to handle concurrent updates'.
Effectively, updates to the list must be serialised using e.g. a mutex
but simple list traversals don't need to take the mutex.