4
\$\begingroup\$

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 & operator=(const TaggedPtrBase & 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 & oldval, void * newptr) {
        uintptr_t old_tag = oldval.tag.load(std::memory_order_relaxed);
        if (old_tag & 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<tag_t> tag;
    void * ptr;
};
...
void push(Node * node) {
    void * newptr = reinterpret_cast<void *>(node);
    TaggedPtrBase old;
    do {
        old = ptr;
        node->next = static_cast<Node *>(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?

\$\endgroup\$
1
  • \$\begingroup\$ How important is portability? On current x86-64 platforms, pointers only have 48-significant bits. You can play bit tricks to store a tag in the remaining (upper) 16 bits, and so use only a 64-bit (single word) compare-and-swap. 16 bits of tag don't give quite the safety against ABA that 64 bits of tag do, as it's possible to quickly overflow a 16 bit tag. But it's still not particularly likely. \$\endgroup\$
    – Managu
    Aug 22 '12 at 14:36
2
\$\begingroup\$

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 & 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; // <-- ... a thread is preempted here
    tag.store(old_tag + 2, std::memory_order_release);
    return true;
}

So the solution is not lock-free.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.