Read Copy Update

[Ted Unangst]

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.


--