Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

[Rusty Russell <rusty@rustcorp.com.au>]

On Wed, 10 Oct 2001 02:36:13 -0700 (PDT)
Linus Torvalds <torvalds@transmeta.com> wrote:

> 
> On Wed, 10 Oct 2001, Rusty Russell wrote:
> >
> > If noone *holds* a reference, you can remove it "sometime later",
> > where "sometime later" is (for example) after every CPU has scheduled.
> 
> Ehh.. One of those readers can hold on to the thing while waiting for
> something else to happen.
> 
> Looking up a data structure and copying it to user space or similar is
> _the_ most common operation for any lookup.

Woah!  So now we're abandoning spinlocks for semaphores, given your
enlightened reasoning?  What are you going to call your new OS?

If you needed reference counts before, you need them still.  But you can
frequently get rid of the spinlock/rwlock protecting the list as a whole.

No, it's not possible everywhere.  But naive profiling doesn't show the
damage from grabbing a read lock, since the penalty is paid by other CPUs
(running unrelated code) as well as the one dirtying the cache, so the
penalty gets smeared across the profile.

As Dave says: the cost is not spinning for the lock, it's the cacheline,
and that's the same with a rwlock as a spinlock, and it's going to get
*worse* with new architectures.

Rusty.