From owner-freebsd-arch@FreeBSD.ORG  Thu Feb 19 02:08:54 2004
Return-Path: <owner-freebsd-arch@FreeBSD.ORG>
Delivered-To: freebsd-arch@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id 37C7A16A4CE
	for <freebsd-arch@freebsd.org>; Thu, 19 Feb 2004 02:08:54 -0800 (PST)
Received: from smtp3.Stanford.EDU (smtp3.Stanford.EDU [171.67.16.117])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 2FCD743D1D
	for <freebsd-arch@freebsd.org>; Thu, 19 Feb 2004 02:08:54 -0800 (PST)
	(envelope-from tedu@stanford.edu)
Received: from elaine39.Stanford.EDU (elaine39.Stanford.EDU [171.64.15.114])
	by smtp3.Stanford.EDU (8.12.10/8.12.10) with ESMTP id i1JA8rdI031031;
	Thu, 19 Feb 2004 02:08:53 -0800
Date: Thu, 19 Feb 2004 02:08:53 -0800 (PST)
From: Ted Unangst <tedu@stanford.edu>
To: Doug Rabson <dfr@nlsystems.com>
In-Reply-To: <1077137806.28133.10.camel@herring.nlsystems.com>
Message-ID: <Pine.GSO.4.44.0402190200440.16174-100000@elaine39.Stanford.EDU>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
cc: freebsd-arch@freebsd.org
Subject: Re: Read Copy Update
X-BeenThere: freebsd-arch@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
List-Id: Discussion related to FreeBSD architecture
	<freebsd-arch.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-arch>,
	<mailto:freebsd-arch-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-arch>
List-Post: <mailto:freebsd-arch@freebsd.org>
List-Help: <mailto:freebsd-arch-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-arch>,
	<mailto:freebsd-arch-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 19 Feb 2004 10:08:54 -0000

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.


--