Single word CAS tagged pointer for algorithms susceptible to the ABA problem I've been looking for a solution to the ABA problem for a lock-free stack. Searching the Web revealed patented and complicated hazard pointers and tagged pointers using double compare-and-swap (DCAS, CAS2). I would settle for the DCAS, but it's not available on some older AMD CPUs. So I came up with this helper class:

class TaggedPtrBase {
    typedef unsigned int tag_t;
    static const tag_t INVALIDATED = 1;
public:
    TaggedPtrBase() {
        tag.store(0, std::memory_order_relaxed);
        ptr = 0;
    }
    TaggedPtrBase &amp; operator=(const TaggedPtrBase &amp; other) {
        tag.store(other.tag.load(std::memory_order_acquire), std::memory_order_relaxed);
        ptr = other.ptr;
        return *this;
    }
    operator void *() const {
        return get();
    }
    void * get() const {
        return ptr;
    }
    bool compare_and_swap(const TaggedPtrBase &amp; oldval, void * newptr) {
        uintptr_t old_tag = oldval.tag.load(std::memory_order_relaxed);
        if (old_tag &amp; INVALIDATED) {
            return false;
        }
        if (tag.compare_exchange_strong(old_tag, old_tag | INVALIDATED, std::memory_order_acquire)) {
            ptr = newptr;
            tag.store(old_tag + 2, std::memory_order_release);
            return true;
        } else {
            return false;
        }
    }
private:
    std::atomic&lt;tag_t&gt; tag;
    void * ptr;
};
...
void push(Node * node) {
    void * newptr = reinterpret_cast&lt;void *&gt;(node);
    TaggedPtrBase old;
    do {
        old = ptr;
        node-&gt;next = static_cast&lt;Node *&gt;(old.get());
    } while (!ptr.compare_and_swap(old, newptr));
}


It appears to be working, but it's simplicity suggests that I'm missing something.
So I wonder if this is a proper solution, or is it just a glorified spin-lock? Any issues on non-x86 platforms?
It's just a spin lock. If the thread that invalidated of the tag got suspended right after, no other thread can make progress till the thread is resumed and releases the tag.

if (old_tag &amp; INVALIDATED) {
    return false; // no thread can go further if ...
}
if (tag.compare_exchange_strong(old_tag, old_tag | INVALIDATED, 
                                std::memory_order_acquire)) {
    ptr = newptr; // &lt;-- ... a thread is preempted here
    tag.store(old_tag + 2, std::memory_order_release);
    return true;
}


So the solution is not lock-free.