Lock-free swap of two unique_ptr<T>

Question

Swapping two unique_ptrs is not guaranteed to be threadsafe.

std::unique_ptr<T> a, b;
std::swap(a, b); // not threadsafe

Since I need atomic pointer swaps and since I like the ownership handling of unique_ptr, is there a simple way to combine them both?

---

Edit: If this is not possible, I am open for alternatives. I at least want to do something like this:

threadshared_unique_ptr<T> global;

void f() {
   threadlocal_unique_ptr<T> local(new T(...));
   local.swap_content(global); // atomically for global
}

What is the idiomatic way of doing this in C++11?

Redness

First, how would you do this for T*? – Triadelphous

@JonathanWakely: Honestly, I don't know. This is why I'm asking this question. I've relaxed my question a bit, should be possible now for T*. – Redness

There's a proposal to add atomic<unique_ptr> (and atomic<shared_ptr> ) at isocpp.org/blog/2014/06/n4058 Doesn't help you right now, but the commentary might be useful. (And I think confirms that going through a raw T* pointer that does work with atomic<> is the best you can do at the moment). – Denominator

Answer 1

Lock-free swapping of two pointers

It seems there is no general lock-free solution for this problem. To do this, you need a possibility to atomically write new values into two non-continous memory locations. This is called DCAS, but it is not available in Intel processors.

Lock-free transfer of ownership

This one is possible, as it is only needed to atomically save new value into global and receive its old value. My first idea was to use CAS operation. Take a look at the following code to get an idea:

std::atomic<T*> global;

void f() {
   T* local = new T;
   T* temp = nullptr;
   do {
       temp = global;                                                   // 1
   } while(!std::atomic_compare_exchange_weak(&global, &temp, local));  // 2

   delete temp;
}

Steps

1. Remember current global pointer in temp
2. Save local to global if global is still equal to temp (it wasn't changed by other thread). Try again if this is not true.

Actually, CAS is overkill there, as we do not do anything special with old global value before it is changed. So, we just can use atomic exchange operation:

std::atomic<T*> global;

void f() {
   T* local = new T;
   T* temp = std::atomic_exchange(&global, local);
   delete temp;
}

See Jonathan's answer for even more short and elegant solution.

Anyway, you will have to write your own smart pointer. You can't use this trick with standard unique_ptr.

Ratchford

what type of memory synchronization ordering would you set for the std::atomic_exchange operation? Is the default memory_order_seq_cst ok, or maybe overkill? – Outbreed

Answer 2

The idiomatic way to modify two variables atomically is to use a lock.

You can't do it for std::unique_ptr without a lock. Even std::atomic<int> doesn't provide a way to swap two values atomically. You can update one atomically and get its previous value back, but a swap is conceptually three steps, in terms of the std::atomic API they are:

auto tmp = a.load();
tmp = b.exchange(tmp);
a.store(tmp);

This is an atomic read followed by an atomic read-modify-write followed by an atomic write. Each step can be done atomically, but you can't do all three atomically without a lock.

For a non-copyable value such as std::unique_ptr<T> you can't even use the load and store operations above, but must do:

auto tmp = a.exchange(nullptr);
tmp = b.exchange(tmp);
a.exchange(tmp);

This is three read-modify-write operations. (You can't really use std::atomic<std::unique_ptr<T>> to do that, because it requires a trivially-copyable argument type, and std::unique_ptr<T> isn't any kind of copyable.)

To do it with fewer operations would need a different API that isn't supported by std::atomic because it can't be implemented because as Stas's answer says, it isn't possible with most processors. The C++ standard is not in the habit of standardising functionality that is impossible on all contemporary architectures. (Not intentionally anyway!)

Edit: Your updated question asks about a very different problem, in the second example you don't need an atomic swap that affects two objects. Only global is shared between threads, so you don't care if updates to local are atomic, you just need to atomically update global and retrieve the old value. The canonical C++11 way to do that is with std:atomic<T*> and you don't even need a second variable:

atomic<T*> global;

void f() {
   delete global.exchange(new T(...));
}

This is a single read-modify-write operation.

Triadelphous

Yes, you're absolutely right! CAS is not needed there. Atomic exchange is more than enough. It seems I was too absorbed by the original problem and CAS already looked pretty simple) I will include this into my answer if you don't mind. – Ratchford

Answer 3

Is this a valid solution to the

You'll have to write your own smart pointer

template<typename T>
struct SmartAtomicPtr
{
    SmartAtomicPtr( T* newT )
    {
        update( newT );
    }
    ~SmartAtomicPtr()
    {
        update(nullptr);
    }
    void update( T* newT, std::memory_order ord = memory_order_seq_cst ) 
    {
        delete atomicTptr.exchange( newT, ord );
    }
    std::shared_ptr<T> get(std::memory_order ord = memory_order_seq_cst) 
    { 
        keepAlive.reset( atomicTptr.load(ord) );
        return keepAlive;
    }
private:
    std::atomic<T*> atomicTptr{nullptr};
    std::shared_ptr<T> keepAlive;
};

it's based on @Jonathan Wakely's snippet at the end.

the hope is that things like this would be safe:

/*audio thread*/ auto t = ptr->get() ); 
/*GUI thread*/ ptr->update( new T() );
/*audio thread*/ t->doSomething(); 

the issue is that you could do something like this:

/*audio thread*/ auto* t = ptr->get(); 
/*GUI thread*/ ptr->update( new T() );
/*audio thread*/ t->doSomething(); 

and there's nothing to keep t alive on the audio thread when the GUI thread calls ptr->update(...)

Derry

Your constructor is inefficient, and uses delete on uninitialized garbage. Use an initializer list to pass the arg to the atomic<T*> constructor, like SmartAtomicPtr( T* newT ) : atomicTptr(newT) {}. Your destructor also doesn't need to do an atomic RMW, just a get(), unless you want it to be safe for multiple threads to destroy the object... – Shela

Also, you probably want to take a std::memory_order ord = memory_order_seq_cst parameter so you can do a relaxed update or get if you want, but the default ordering is still seq-cst. – Shela

For my own understanding (I'm new to this atomic stuff), I dug into std::atomic here in Xcode, trying to find where the garbage value you're talking about comes from. 607: #define _Atomic(x) __gcc_atomic::__gcc_atomic_t<x> 891: struct __atomic_base // false { mutable _Atomic(_Tp) __a_; // <-- here? 1103: template <class _Tp> struct atomic<_Tp*> : public __atomic_base<_Tp*> { typedef __atomic_base<_Tp*> __base; 1111: _LIBCPP_CONSTEXPR atomic(_Tp* __d) _NOEXCEPT : __base(__d) {} – Derry

added recommended solutions @PeterCordes thanks for the suggestions!! – Derry

It's safe now that you added a {nullptr} default argument for the atomic<T*> constructor, so you're just uselessly deleting a nullptr when you construct this, and doing an unnecessary atomic RMW. Safe but slow. Previously you were letting it get default-constructed, which would only be safe if it was in static storage. In automatic or dynamic storage, atomicTptr would potentially be holding garbage before the update() in the constructor. – Shela

Anyway, the right place to ask for feedback like "Is this a valid solution?" is on codereview.stackexchange.com – Shela