How to swap two pointers in multi-threaded c++ 17 program?

Question

I have two pointers: pA and pB. They points to two big hash map objects. when the hash map pointed by pB is updated completely, I want to swap pB and pA.

In C++ 17, how to swap them fast and thread safe? Atomic? I am new to c++ 17.

atomic is c++11, and all you want is [atomic exchange](https://en.cppreference.com/w/cpp/atomic/atomic_exchange) — Mgetz, Feb 06 '19 at 16:13
@Mgetz thanks, could you give me an example for exchanging two pointers. — Dean Chen, Feb 06 '19 at 16:28
Just some words of warning: An atomic update of a _single_ pointer can easily be achieved by using `std::atomic`. _Two_ pointers can be swapped atomically by using `std::atomic` (`std::pair` does not work). **However**, depending on your exact use-case **you may need an additional synchronization mechanism**: Other threads may continue to use the old hash map (now pointed-to by `pB`) even after the atomic update of `pA` from the "writer thread". This can yield a race condition if you plan to subsequently update the hash map `*pB`. — Julius, Feb 06 '19 at 18:17
I am reopening because this solution is wait-free, whereas [marked duplicate](https://stackoverflow.com/questions/29512112/want-an-efficient-way-to-swap-two-pointers-in-c) provides a lock-free solution. — Maxim Egorushkin, Feb 06 '19 at 23:25

Maxim Egorushkin · Accepted Answer · 2019-03-01T13:23:41.420

Atomic wait-free exchange of 2 pointers can be implemented in the following manner:

#include <atomic>
#include <cstdint>
#include <cassert>

template<class T>
class Pointers2 {
    uintptr_t const ab_;
    std::atomic<uintptr_t> a_;

public:
    Pointers2(T* a, T* b)
        : ab_(reinterpret_cast<uintptr_t>(a) ^ reinterpret_cast<uintptr_t>(b))
        , a_(reinterpret_cast<uintptr_t>(a))
    {}

    T* a() const { return reinterpret_cast<T*>(a_.load(std::memory_order_acquire)); }
    T* b() const { return reinterpret_cast<T*>(a_.load(std::memory_order_acquire) ^ ab_); }
    void exchange() { a_.fetch_xor(ab_, std::memory_order_release); }
};

int main() {
    int a = 1, b = 2;
    Pointers2<int> p2(&a, &b);
    assert(p2.a() == &a);
    assert(p2.b() == &b);
    p2.exchange();
    assert(p2.a() == &b);
    assert(p2.b() == &a);
    p2.exchange();
    assert(p2.a() == &a);
    assert(p2.b() == &b);
}

Acquire/release memory ordering is required to make sure that writes to shared data T do not get reordered past exchange.

A few comments on the code will be better for new people. Thanks. — Dean Chen, Feb 07 '19 at 02:53
@DeanChen It is based on the idea of exchanging 2 integers using xor: `void exchange(uintptr_t& a, uintptr_t& b) { a ^= b; b ^= a; a ^= b; }`. — Maxim Egorushkin, Feb 07 '19 at 15:34
question @MaximEgorushkin - this works fine but wouldn't the data that we are pointing to still need some locking? — Kobi, Feb 01 '21 at 19:23

Maxim Egorushkin · Answer 2 · 2019-02-06T16:51:47.653

1

On x86-64 you can atomically exchange 2 pointers only if they are adjacent in memory and aligned to 16 bytes with cmpxchg16b instruction directly or by using libatomic_ops:

AO_INLINE int
AO_compare_double_and_swap_double_full(volatile AO_double_t *addr,
                                       AO_t old_val1, AO_t old_val2,
                                       AO_t new_val1, AO_t new_val2)
{
  char result;
  __asm__ __volatile__("lock; cmpxchg16b %0; setz %1"
                      : "=m"(*addr), "=a"(result)
                      : "m"(*addr), "d" (old_val2), "a" (old_val1),
                        "c" (new_val2), "b" (new_val1)
                      : "memory");
  return (int) result;
}

If cmpxchg16b is unavailable you need to use a mutex to make exchanging 2 pointers atomic.

edited Feb 06 '19 at 16:51

answered Feb 06 '19 at 16:34

Maxim Egorushkin

131,725
17
180
271

The standard has [appropriate methods](https://en.cppreference.com/w/cpp/atomic/atomic_exchange) of doing pointer exchanges without resorting to third party libraries or non-portable assembly. – Mgetz Feb 06 '19 at 17:37
@Mgetz You do not understand how https://en.cppreference.com/w/cpp/atomic/atomic_exchange works, I am afraid. – Maxim Egorushkin Feb 06 '19 at 18:20

score 0 · Answer 3 · answered Feb 06 '19 at 20:17

0

Maybe it's not just swap that should be atomic, but transaction should include check that swap should be made (is_the_hash_map_pointed_by_pB_updated_completely()). Probably hash maps should be protected from concurrent usage with mutex.

answered Feb 06 '19 at 20:17

jnr

790
1
7
9

How to swap two pointers in multi-threaded c++ 17 program?

3 Answers3

Linked