c++ - 用32位原子实现64位原子计数器

Question

我想将原子uint32s的uint64原子计数器拼凑在一起。计数器只有一个作者和多个读者。 writer是信号处理程序，因此不能阻塞。

我的想法是将具有低位的世代计数用作读取锁定。读取器重试，直到在读取期间生成计数稳定为止，并且低位未设置。

以下代码在设计和使用内存顺序时是否正确？有没有更好的办法？

using namespace std;
class counter {
    atomic<uint32_t> lo_{};
    atomic<uint32_t> hi_{};
    atomic<uint32_t> gen_{};

    uint64_t read() const {
        auto acquire = memory_order_acquire;
        uint32_t lo, hi, gen1, gen2;
        do {
            gen1 = gen_.load(acquire);
            lo = lo_.load(acquire);
            hi = hi_.load(acquire);
            gen2 = gen_.load(acquire);
        } while (gen1 != gen2 || (gen1 & 1));
        return (uint64_t(hi) << 32) | lo;
    }

    void increment() {
        auto release = memory_order_release;
        gen_.fetch_add(1, release);
        uint32_t newlo = 1 + lo_.fetch_add(1, release);
        if (newlo == 0) {
            hi_.fetch_add(1, release);
        }
        gen_.fetch_add(1, release);
    }
};

编辑:哎呀，固定的 auto acquire = memory_order_release;

Answer 1

这是一个已知的模式，称为SeqLock。 https://en.wikipedia.org/wiki/Seqlock。 (为了简化起见，只有一个作者，因此不需要额外的支持来排除同时作者。)

您不需要或不希望计数器变量本身增加使用原子RMW操作。您可以只用原子32位加载来加载两个半块，对其进行递增并原子存储结果。 (使用便宜的relaxed或release存储顺序，并使用release存储进行第二次计数器更新)。

同样，计数器也不必是原子RMW。

编写器仅需要纯加载和纯存储(仅具有发布顺序)，这些发布和发行版比原子RMW便宜(很多)，或者仅具有seq_cst排序的存储:

以任意顺序加载计数器和值

存储新计数器(旧+1)

存储新值(如果您想在没有进位的情况下分支，则只需更新下半部分)

存储最终计数器。

唯一重要的是在这3个要点中对商店的排序。在第一个存储之后写入写保护区可能会很好，因为我们真的不希望在价格比宽松的CPU更高的CPU上将两个存储都设为 release的两个部分的成本。

不幸的是，为了满足C++规则， value必须是 atomic<T>，这使获取编译器生成可能同时加载这两个部分的最有效代码的不便。例如ARM ldp / stp负载对可能不是原子的，但这无关紧要。 (而且编译器通常不会将两个单独的原子32位负载优化为一个更大的负载。)

当序列计数器为奇数时，其他线程读取的值无关紧要，但我们希望避免未定义的行为。也许我们可以使用 volatile uint64_t和 atomic<uint64_t>的并集

我为 another question编写了这个C++ SeqLock<class T>模板，但我还没有完成答案(弄清楚哪些ARM版本具有64位原子加载和存储)。

这将尝试检查目标是否已经支持 atomic<T>上的无锁原子操作，以阻止您在毫无意义时使用它。 (通过定义 IGNORE_SIZECHECK禁用该功能以进行测试。)TODO:透明地回过头去做，可能是使用模板专门化，而不是使用 static_assert。

我为 inc()提供了 T函数，该函数支持 ++运算符。 TODO是一个 apply()，它接受一个lambda来对 T做某事，并在序列计数器更新之间存储结果。

// **UNTESTED**

#include <atomic>

#ifdef UNIPROCESSOR
// all readers and writers run on the same core
// ordering instructions at compile time is all that's necessary
#define ATOMIC_FENCE std::atomic_signal_fence
#else
// A reader can be running on another core while writing
// memory barriers or ARMv8 acquire / release loads / store are needed
#define ATOMIC_FENCE std::atomic_thread_fence
#endif
// using fences instead of .store(std::memory_order_release) will stop the compiler
// from taking advantage of a release-store instruction, like on AArch64 or x86


// SINGLE WRITER only.
// uses volatile + barriers for the data itself, like pre-C++11
template <class T>
class SeqLocked
{
#ifndef IGNORE_SIZECHECK
    // sizeof(T) > sizeof(unsigned)
    static_assert(!std::atomic<T>::is_always_lock_free, "A Seq Lock with a type small enough to be atomic on its own is totally pointless, and we don't have a specialization that replaces it with a straight wrapper for atomic<T>");
#endif

       // C++17 doesn't have a good way to express a load that doesn't care about tearing
       //  without explicitly writing it as multiple small parts and thus gimping the compiler if it can use larger loads
    volatile T data;          // volatile should be fine on any implementation where pre-C++11 lockless code was possible with volatile,
                              //  even though Data Race UB does apply to volatile variables in ISO C++11 and later.

    std::atomic<unsigned> seqcount{0};  // Even means valid, odd means modification in progress.
                                        //  unsigned wraps around at a power of 2 on overflow

public:
    T get() const {
        unsigned c0, c1;
        T tmp;

        do {
            c0 = seqcount.load(std::memory_order_relaxed);  // or this can be a std::memory_order_acquire for multicore so AArch64 can use LDAR
            ATOMIC_FENCE(std::memory_order_acquire);

            tmp = (T)data;       // load

            ATOMIC_FENCE(std::memory_order_acquire);  // LoadLoad barrier
            c1 = seqcount.load(std::memory_order_relaxed);
        } while(c0&1 || c0 != c1);     // retry if the counter changed or is odd

        return tmp;
    }

    // TODO: a version of this that takes a lambda for the operation on tmp
    T inc() {
        unsigned orig_count = seqcount.load(std::memory_order_relaxed);

        seqcount.store(orig_count+1, std::memory_order_relaxed);
        ATOMIC_FENCE(std::memory_order_release);
        // make sure the data stores appear after the first counter update.

        T tmp = data;  // load
        ++tmp;
        data = tmp;    // store

        ATOMIC_FENCE(std::memory_order_release);
        seqcount.store(orig_count+2, std::memory_order_relaxed);  // Or use mo_release here, better on AArch64

        return tmp;
    }

    void set(T newval) {
        unsigned orig_count = seqcount.load(std::memory_order_relaxed);

        seqcount.store(orig_count+1, std::memory_order_relaxed);
        ATOMIC_FENCE(std::memory_order_release);
        // make sure the data stores appear after the first counter update.

        data = newval;    // store

        ATOMIC_FENCE(std::memory_order_release);
        seqcount.store(orig_count+2, std::memory_order_relaxed);  // Or use mo_release here, better on AArch64
    }

};


/***** test callers *******/
#include <stdint.h>

struct sixteenbyte {
    //unsigned arr[4];
    unsigned long  a,b,c,d;
    sixteenbyte() = default;
    sixteenbyte(const volatile sixteenbyte &old)
         : a(old.a), b(old.b), c(old.c), d(old.d) {}
    //arr(old.arr) {}
};

void test_inc(SeqLocked<uint64_t> &obj) {  obj.inc(); }
sixteenbyte test_get(SeqLocked<sixteenbyte> &obj) { return obj.get(); }
//void test_set(SeqLocked<sixteenbyte> &obj, sixteenbyte val) { obj.set(val); }

uint64_t test_get(SeqLocked<uint64_t> &obj) {
    return obj.get();
}

// void atomic_inc_u64_seq_cst(std::atomic<uint64_t> &a) { ++a; }
uint64_t u64_inc_relaxed(std::atomic<uint64_t> &a) {
    // same but without dmb barriers
    return 1 + a.fetch_add(1, std::memory_order_relaxed);
}

uint64_t u64_load_relaxed(std::atomic<uint64_t> &a) {
    // gcc uses LDREXD, not just LDRD?
    return a.load(std::memory_order_relaxed);
}

void u64_store_relaxed(std::atomic<uint64_t> &a, uint64_t val) {
    // gcc uses a LL/SC retry loop even for a pure store?
    a.store(val, std::memory_order_relaxed);
}

它将编译为我们希望on the Godbolt compiler explorer用于ARM和其他ISA的asm。至少对于int64_t由于麻烦的volatile规则，较大的结构类型的复制效率可能较低。

它对共享数据使用非原子 volatile T data。从技术上讲，这是数据种族的未定义行为，但是我们在实践中使用的所有编译器都可以通过C++ 11之前的多线程访问 volatile对象。在C++ 11之前的版本中，人们甚至在某些尺寸上都依赖原子性。我们不这样做，我们检查计数器，仅在没有并发写入的情况下才使用读取的值。 (这就是SeqLock的重点。)
volatile T data的一个问题是，在ISO C++中，除非您从 T foo = data对象提供了一个复制构造函数，否则 volatile不会为结构对象编译。

sixteenbyte(const volatile sixteenbyte &old)
         : a(old.a), b(old.b), c(old.c), d(old.d) {}

这对我们来说真的很烦，因为我们不在乎如何读取内存的详细信息，只是不会将多次读取优化为一次。

volatile实际上是错误的工具此处，并且纯 T data具有足够的防护以确保读取实际上发生在原子计数器的读取之间会更好。例如我们可以使用 asm("":::"memory");编译器屏障在GNU C中做到这一点，以防止在访问之前/之后进行重新排序。这样一来，编译器就可以使用SIMD vector 或其他任何方式复制较大的对象，而使用单独的 volatile访问则不会这样做。

我认为 std::atomic_thread_fence(mo_acquire)也将是一个足够的障碍，但我不确定100％。

在ISO C中，您可以复制 volatile聚合(结构)，编译器将发出通常复制该字节的asm。但是在C++中，显然我们无法拥有美好的事物。