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

From: Rusty Russell (
Date: Thu Oct 11 2001 - 01:50:19 EST

On Wed, 10 Oct 2001 02:36:13 -0700 (PDT)
Linus Torvalds <> 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.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Oct 15 2001 - 21:00:39 EST