RFC: patch to allow lock-free traversal of lists with insertion
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 3 lines · Rusty Russell
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. You MUST NOT free it just because we scheduled away. Scheduling points have zero meaning in real life.
So you'll need a reference count to actually keep such a data structure alive _over_ a schedule. Or all the readers need to copy the data too before they actually start using it. At which point you've made your code a _lot_ slower than the locking version.
Yeah, I can see that your data structure can be made to work by limiting how you can use it ("you must never hold on to a entry over a schedule, reference-counting is a no-no, and you have to stand on your left foot when you look at it sideways").
Linus
Quoted 11 lines · On Wed, 10 Oct 2001 02:36:13 -0700 (PDT) Linus Torvalds…
Quoted 3 lines · Rusty Russell
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.