Atomic exchange of two std::atomic<T*> objects in a lock-free manner in C++11?

Question

The following code is a skeleton of an atomic pointer class taken from a simulated annealing application in the PARSEC benchmark suite for shared-memory multiprocessors.

In that application, the central data structure is a graph (more specifically, a netlist of an integrated circuit). Each node in the graph has an attribute indicating its physical location. The algorithm spawns many threads and each thread repeatedly and randomly selects two nodes and exchanges their physical locations if that results in better routing cost for the chip.

Because the graph is huge and any pair of nodes can be chosen by each thread, the only workable solution is a lock-free concurrent data structure (CDS). That's why the following AtomicPtr class is crucial (it is used to atomically exchange pointers to two physical location objects in a lock-free manner). The function atomic_load_acq_ptr() is a defined in assembly code and corresponds closely to std::atomic<T*>::load(memory_order_acquire).

I want to implement that CDS using C++11 atomics.

template <typename T>
class AtomicPtr {
  private:
    typedef long unsigned int ATOMIC_TYPE;
    T *p __attribute__ ((aligned (8)));
    static const T *ATOMIC_NULL;
    inline T *Get() const {
        T *val;
        do {
            val = (T *)atomic_load_acq_ptr((ATOMIC_TYPE *)&p);
        } while(val == ATOMIC_NULL);
        return val;
    }
    inline void Swap(AtomicPtr<T> &X) {
        // Define partial order in which to acquire elements to prevent deadlocks
        AtomicPtr<T> *first;
        AtomicPtr<T> *last;
        // Always process elements from lower to higher memory addresses
        if (this < &X) {
            first = this;
            last  = &X;
        } else {
            first = &X;
            last  = this;
        }
        // Acquire and update elements in correct order
        T *valFirst = first->Checkout(); // This sets p to ATOMIC_NULL so all Get() calls will spin.
        T *valLast  =  last->PrivateSet(valFirst);
        first->Checkin(valLast); // This restores p to valLast
    }
};

The std::atomic<T*>::exchange() method can only be used to exchange a bare T* pointer with a std::atomic<T*> object. How to do exchange of two std::atomic<T*> objects in a lock-free manner?

What I can think of is that the AtomicPtr class below can itself be based on std::atomic<T*> by declaring:

std::atomic<T*> p;

and replacing all atomic_load_acq_ptr() calls by std::atomic<T*>::load(memory_order_acquire) and replacing all atomic_store_rel_ptr() calls by std::atomic<T*>::store(memory_order_release). But my first thought was that std::atomic<T*> should replace AtomicPtr itself and there may be a clever way to exchange std::atomic<T*> objects directly. Any thoughts?

Answer 1

It seems to me that the simpler way to get what you wish is to replicate the logic that you have seen here.

The problem is that there is no possibility to get an atomic operations across two atomic objects, so you have to follow a procedure:

• order the atomics (to avoid dead-locks)
• "lock" all but the last one (increasing order)
• perform the operation atomically on the last one
• perform the operation and "unlock" the others one at a time (decreasing order)

This is, of course, quite imperfect:

• not atomic: whilst you are busy locking a variable, any of the not yet locked could change state
• not obstruction free: if for some reason a thread is blocked whilst having locked a variable, all other pending threads are also blocked; be careful to avoid deadlocks here (should you have other locks)
• brittle: a crash after locking a variable leaves you stranded, avoid operations that may throw and/or use RAII to "lock"

However it should work relatively well in practice in the case of only 2 objects (and thus one to lock).

Finally, I have two remarks:

• in order to lock you need to be able to define a sentinel value, 0x01 usually works well for pointers.
• the C++ Standard does not guarantee that std::atomic<T*> be lock-free, you can check this for your particular implementation and platform with std::atomic<T*>::is_lock_free().