Avoiding the ABA problem in .NET code

Question

Please note that I already know of and understand the ABA problem. This question is about the behavior of the .NET memory model with regard to ABA.

In his discussion of the Lock-Free LIFO Stack (CLR Inside Out column from May 2007 MSDN Magazine), Joe Duffy says:

"We incur an object allocation for each Push, saving us from having to worry about so-called ABA problems."

He then goes on to very briefly describe the ABA problem and mentions that this can occur in native C/C++ because the memory allocator can reuse an address as soon as it's freed.

All well and good. But what makes .NET programs immune to the ABA problem? Is he implying that because nodes can't be reused immediately (i.e. there is some delay between when a node goes out of scope and when the GC collects it) there's no possibility of the ABA problem occurring? If so, is that a safe assertion to make?

I'll be the first to admit that I don't know all the intricacies of the .NET memory allocator or garbage collector, but my limited understanding leads me to believe that a reference can be reused. And if there's a possibility that a reference can be reused, then doesn't that make the ABA problem possible, if indeed highly unlikely?

Answer 1

If a thread 1 has an object reference at memory address X, then by definition, nothing that thread 2 does can cause another object to use that same address. The object is still alive and its address won't be reused until no references to it remain. This guarantees that -- when the interlocked exchange operation returns the value we expect -- the ABA problem hasn't happened.