RCU-safe reference counting

Posted Jul 17, 2004 0:54 UTC (Sat) by giraffedata (subscriber, #1954) [Link]

I believe it beats a spinlock because the processor can implement it without actually stopping all the other CPUs. It can go ahead and do the whole operation as if the other CPUs didn't exist, then check whether there had been any conflicting activity by another CPU, and in the unlikely event that there was, try again. The spinlock requires all the other CPUs (that want that lock) to stop doing work while the one holder runs.

But here, we aren't talking about using cmpxchg() per se instead of a spinlock. We're talking about using it as part of some RCU logic so that an entire sequence of (lookup, find, and add a reference) can happen at the same time as another thread is destroying the found object.

Traditionally, that whole sequence would be covered by a spinlock, and two CPUs at a time could not do it, even for different objects. Nor could any CPU destroy any object while another CPU was in this lookup sequence. CPUs would be waiting for another CPU to do something that isn't even an actual conflict.

Posted Jul 19, 2004 9:26 UTC (Mon) by khim (subscriber, #9252) [Link]

Never mind that cmpxchg() is a spinlock in different clothes.

Yes and no. It's reuse of existing "spinlock". Each and every access to every byte of RAM on SMP system is covered by "spinlock" anyway - think about cache cogerency! Yes, it's not really implemented as spinlock and there are different implementations of idea but the end result is the same: access to every byte in modern SMP systems is covered by "sort of spinlock" (and if two processors stomp each other feets too often system slows down to a crawl as you can guess). And cmpxchg() is using this feature - that's all. Since each and every access to any variable should be held with such "spinlock" held it's not slower then simple access without cmpxchg() function.