Hmmm, a little question to people who are familiar with atomics and/or lockfree programming: does the ABA-proof property of LL/SC ever get used in practice?
Asking because most of the time I see LL/SC simply being used to conjure a CAS and at that point it is just as vulnerable to the ABA issue as readymade CAS instructions, no?
#AskFedi, I guess?
I was under the impression that ll/sc in hardware is terribly rare, so everyone makes do with CAS. They then use of the tricks to prevent ABA in CAS-based setups (either counters we trust to never wrap around, or pointers to objects that the actor who does the CAS keeps alive[1]). If we had ll/sc those tricks would be unnecessary.
So, I think that people don't use that property of ll/sc because they don't use ll/sc, because it's very rarely available.
[1]
roughly:
- read ptr from X
- increment refcount on *ptr
- read X again, verify it's still equal to ptr (if not: decrement refcount, start from scratch)
- ...
- CAS X from ptr to something else
- decrement refcount on *ptr (and potentially handle the case when it decrements to 0)
This guarantees ABA-freeness of the CAS if each potential target of the pointer in X can become it only once in its lifetime (which is pretty common in structures such as queues, stacks, approximate queues, ...).
This is a reasonably common pattern in lockfree data structures that need to do their own memory management (i.e. for environments without a garbage collector) and that don't want to use thread IDs (if they can, refcounts often get replaced with hazard pointers; that said, I've never seen hazard pointers used outside of theory).
By "not seeing hazard pointers used outside of theory" I meant that in places which would use them I'd see RCU used instead (with the thing that deallocates -- which might be a thing to the side of everything else -- waiting on the RCU "lock").
