11

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?

5
  • There is no way to atomically swap the contents of two std::atomics in C++11.
    – Casey
    Aug 21, 2013 at 6:04
  • actually, I don't think that this is even possible on x86 / x64 Aug 21, 2013 at 6:35
  • 2
    It is not possible directly. But the AtomicPtr class already does it by following a check-out\check-in discipline: 1- Any thread that wants to do a swap first checks out the pointer (by writing a sentinel value called ATOMIC_NULL above) and, when done, checks it in. 2- Any thread that wants to read (i.e., Get()) the pointer value has to keep spinning if the pointer has been checked out. Aug 21, 2013 at 6:37
  • @AhmedNassar: why not replicate this logic with std::atomic<T*> ? Aug 21, 2013 at 7:09
  • @Matthieu: This is what I am already suggesting as the only solution I could come up with. I was looking for better solutions :) Aug 21, 2013 at 7:23

3 Answers 3

6

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().
2
  • As I suggested in the question, porting the AtomicPtr class to use C++11 atomics instead of the custom-defined assembly-level functions was the only solution I had. The AtomicPtr class is in fact crafting its own spin lock by spinning whenever the pointer holds the sentinel value. But thanks a lot for elaborating on the imperfections of the suggested solution. I am using it as a benchmark, not in production code. BTW, the original code was already defining the sentinel value exactly as you suggested: template<typename T> const T *AtomicPtr<T>::ATOMIC_NULL((T *)((int)NULL + 1)); Aug 21, 2013 at 7:39
  • 2
    @AhmedNassar: for portability reasons, I would advise you to cast NULL to intptr_t instead of int; int is often only 32 bits in 64 bits code. Aug 21, 2013 at 7:42
4

The closest you can come without a spinlock is:

std::atomic<T> a;
std::atomic<T> b;
a = b.exchange(a);

Which is thread safe for b.

a may not be concurrently accessed.

2
  • This is not atomic because std::atomic<T>::exchange() accepts a bare T value not a std::atomic<T> object. Hence, it will first invoke a's conversion function to T and then pass it to b.exchange(). Aug 21, 2013 at 6:28
  • 6
    I never said it was atomic for a, it is only atomic for b. Which is the best you can achieve without a spin-lock.
    – ronag
    Aug 21, 2013 at 7:00
0

Have you checked out a CAS (compare and swap ) operation?

   std::atomic<T*> v;

      while(!v.compare_exchange_weak(old_value,new_value, std::memory_order_release, memory_order_relaxed))
1
  • 2
    But the new_value parameter in std::atomic<T*>::compare_exchange_weak() is a bare T* not a std::atomic<T*> object. If that bare T* value was previously read from a std::atomic<T*> object, the exchange is not gonna be atomic. Do I miss something here? Aug 21, 2013 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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