Частичное сравнение и полная замена значений atomi c

Question

Проблема заключается в следующем.

Дан объект POD, который состоит из двух частей: индекс и данные . Я хочу выполнить операцию условного обмена atomi c над ним с условием, которое проверяет равенство только для индекса.

Примерно так:

struct Data { size_t m_index; char m_data; };
std::atomic<Data> dd; // some initialization
Data zz; // some initialization

// so I want something like this
dd.exchange_if_equals<&Data::m_index>(10,zz);

Так что это своего рода Операция « частичное -сравнение-и- полное -замена». Возможно, для этого потребуется соответствующее выравнивание для Data::m_index.

Очевидно, что std::atomic не поддерживает это, но можно ли реализовать это самостоятельно, или, может быть, есть другая библиотека, которая поддерживает это?

Answer 1

Так же, как C ++, аппаратный CAS (например, x86-64 или ARMv8.1) не поддерживает это в asm, вам придется свернуть свой собственный.

В C ++ это довольно просто: загрузить исходное значение и замените его часть. Это, конечно, может привести к ложному сбою, если другое ядро ​​изменило другую часть, с которой вы не хотели сравнивать.

Если возможно, используйте unsigned m_index вместо size_t, чтобы вся структура могла умещаются в 8 байтах на типичных 64-битных машинах вместо 16. 16-байтовые атомики медленнее (особенно часть чистой загрузки) на x86-64 или даже не блокируются вообще в некоторых реализациях и / или некоторые ISA. См. Как я могу реализовать счетчик ABA с c ++ 11 CAS? re: x86-64 lock cmpgxchg16b с текущим GCC / clang.

Если каждый доступ atomic<> отдельно требует блокировки , было бы намного лучше просто взять мьютекс вокруг всего пользовательского сравнения и установки.

---

Я написал простую реализацию одной попытки CAS (например, cas_weak) в качестве примера. Вы могли бы использовать его в специализации шаблона или производном классе std::atomic<Data>, чтобы предоставить новую функцию-член для atomic<Data> объектов.

#include <atomic>
struct Data {
    // without alignment, clang's atomic<Data> doesn't inline load + CAS?!?  even though return d.is_always_lock_free; is true
    alignas(long long)  char m_data;
    unsigned m_index;               // this last so compilers can replace it slightly more efficiently
};

inline bool partial_cas_weak(std::atomic<Data> &d, unsigned expected_idx, Data zz, std::memory_order order = std::memory_order_seq_cst)
{
    Data expected = d.load(std::memory_order_relaxed);
    expected.m_index = expected_idx;            // new index, same everything else
    return d.compare_exchange_weak(expected, zz, order);
    // updated value of "expected" discarded on CAS failure
    // If you make this a retry loop, use it instead of repeated d.load
}

На практике это хорошо компилируется с clang для x86-64 ( Godbolt ), встраивание в вызывающий объект, который передает константу времени компиляции order (иначе clang идет неистовым ветвлением по этому order arg для автономной не встроенной версии функции)

# clang10.0 -O3 for x86-64
test_pcw(std::atomic<Data>&, unsigned int, Data):
    mov     rax, qword ptr [rdi]                  # load the whole thing
    shl     rsi, 32
    mov     eax, eax                              # zero-extend the low 32 bits, clearing m_index
    or      rax, rsi                              # OR in a new high half = expected_idx
    lock            cmpxchg qword ptr [rdi], rdx      # the actual 8-byte CAS
    sete    al                                        # boolean FLAG result into register
    ret

К сожалению, компиляторы слишком глупы, чтобы загружать только ту часть структуры atomi c, которая им действительно нужна, вместо этого загружая все это целиком, а затем обнуляя часть, которую они не хотели . (См. Как я могу реализовать счетчик ABA с c ++ 11 CAS? для хаков объединения, чтобы обойти это на некоторых компиляторах.)

К сожалению, G CC создает беспорядочный asm, который хранит / перезагружает временные файлы в стек, что приводит к остановке пересылки магазина. G CC также обнуляет заполнение после char m_data (будь то первый или последний член), что может приводить к тому, что CAS всегда терпит неудачу, если у фактического объекта в памяти было ненулевое заполнение. Это может быть невозможно, если чистые хранилища и инициализация всегда сводятся к нулю.

---

LL / S C машина вроде ARM или PowerP C могла бы легко сделать это при сборке (сравнение / ветвление выполняется вручную, между привязкой к загрузке и условным хранилищем), но нет библиотек, которые переносят это. (Самое главное, потому что он не может компилироваться для таких машин, как x86, и потому, что то, что вы можете делать в транзакции LL / S C, сильно ограничено, и сброс / перезагрузка локальных переменных в режиме отладки может привести к коду, который всегда терпит неудачу. )

Answer 2

Я думаю, вам нужно выполнить загрузку, затем ваше пользовательское условие, затем сравнение и обмен, где сравнение заключается в том, что текущее значение полностью равно прочитанному значению. Если последний шаг завершился неудачно, l oop.

template<class T, class F>
bool swap_if(std::atomic<T>& atomic, T desired, F&& condition) {
    for (;;) {
        T data = atomic.load();
        if (!condition(data)) break;
        if (atomic.compare_exchange_weak(data, desired)) return true;
    }
    return false;
}

http://coliru.stacked-crooked.com/a/a394e336628246a9

Из-за сложности вам, вероятно, следует просто использовать мьютекс. Отдельно std::atomic<Data> может уже использовать мьютекс под крышками, поскольку Data такой большой.

Answer 3

Если можно использовать std::mutex вместо atomic, вы можете поместить мьютекс в свою собственную c -подобную оболочку atomi.

Вот начало того, как это может выглядеть:

#include <iostream>
#include <type_traits>
#include <mutex>

template<typename T>
class myatomic {
public:
    static_assert(
        // std::is_trivially_copyable_v<T> && // used in std::atomic, not needed here
        std::is_copy_constructible_v<T> &&
        std::is_move_constructible_v<T> &&
        std::is_copy_assignable_v<T> &&
        std::is_move_assignable_v<T>, "unsupported type");

    using value_type = T;

    myatomic() : data{} {}
    explicit myatomic(const T& v) : data{v} {}

    myatomic(const myatomic& rhs) : myatomic(rhs.load()) {}

    myatomic& operator=(const myatomic& rhs) {
        std::scoped_lock lock(mtx, rhs.mtx);
        data = rhs.data;
        return *this;
    }

    T load() const {
        const std::lock_guard<std::mutex> lock(mtx);
        return data;
    }

    operator T() const {
        return load();
    }

    void store(const T& v) {
        const std::lock_guard<std::mutex> lock(mtx);
        data = v;
    }

    myatomic& operator=(const T& v) {
        store(v);
        return *this;
    }

    // partial compare and full swap
    template<typename Mptr, typename V>
    bool exchange_if_equals(Mptr mvar, V mval, const T& oval) {
        const std::lock_guard<std::mutex> lock(mtx);
        if(data.*mvar == mval) {
            data = oval;
            return true;
        }
        return false;
    }

    template<typename Mptr>
    auto get(Mptr mvar) const {
        const std::lock_guard<std::mutex> lock(mtx);
        return data.*mvar;
    }

    template<typename Mptr, typename V>
    void set(Mptr mvar, const V& v) {
        const std::lock_guard<std::mutex> lock(mtx);
        data.*mvar = v;
    }

private:
    mutable std::mutex mtx;
    T data;
};

struct Data {
    size_t m_index;
    char m_data;
};

int main() {
    Data orig{10, 'a'};
    Data zz; // some initialization

    myatomic<Data> dd(orig);
    dd.exchange_if_equals(&Data::m_index, 10U, zz);
    std::cout << dd.get(&Data::m_index);
}