Что такое эквивалент атомной библиотеки C++ 11 для AtomicMarkableReference Java? <T>

Question

Нужен этот вызов для реализации связанного с блокировкой списка. AtomicMarkableReference - это объект из пакета java.util.concurrent.atomic, который инкапсулирует как ссылку на объект типа T, так и логическую метку. Эти поля могут обновляться атомарно, либо вместе, либо индивидуально.

Thank you.

Answer 1

Предполагая alignement объекта более чем 1, вы можете использовать последний бит указателя как логические метки:

template<class T> 
class MarkableReference 
{ 
private: 
    uintptr_t val; 
    static const uintptr_t mask = 1; 
public: 
    MarkableReference(T* ref = NULL, bool mark = false) 
    { 
     val = ((uintptr_t)ref & ~mask) | (mark ? 1 : 0); 
    } 
    T* getRef(void) 
    { 
     return (T*)(val & ~mask); 
    } 
    bool getMark(void) 
    { 
     return (val & mask); 
    } 
}; 

Для выполнения атомарных операций, необходимо создать атомные переменный из этого класса. Например, если тип объекта, указываемого ссылкой, должны быть int, вы можете создать эту переменную:

atomic<MarkableReference<int>> mRef; 

Для переменной mRef вы можете применить любую операцию, которая применяется для нормальной атомарным. Например, сравнение-и-Set (CAS):

int a; 
int b; 
... 
// Atomically change pair (&a, true) to (&b, false). 
MarkableReference<int> old = mRef.load(); 
if(old == MarkableReference(&a, true)) 
{ 
    if(mRef.compare_exchange_strong(old, MarkableReference(&b, false))) 
    { 
     // Successful CAS 
    } 
} 
// 'old' contains other value. (Unsuccessfull CAS) 

Answer 2

идея Цыварева (в использовании бита внутри указателя) интересно, а для некоторых сценариев использования, вероятно, более эффективный, чем хранение булева отдельно. Для других случаев использования лучше хранить их отдельно и с помощью двойного сравнения и обмена для обмена одновременно. Это делает его более эффективным для атомарного изменения только логического или просто ref. Сохранение их вместе означает, что вам всегда нужно выполнять атомарное чтение-изменение-запись, чтобы изменить одно, а не другое (на x86 либо цикл lock or [mem], reg, либо lock cmpxchg, если вам также нужно старое значение), а не просто хранилище атомов, t влияет на другое. (Или атомный xchg, если вы хотите старое значение).

Для реализации с двумя отдельными элементами структуры см. my answer on another question об использовании compare_exchange_weak по адресу atomic<two_member_struct>. Я бы предложил сохранить логическое значение в целочисленном размере указателя, чтобы избежать какого-либо дополнения в объекте, который нужно игнорировать, или может привести к ошибке cmpxchg, когда заполнение не совпадает, но данные выполняются.

Если вы часто обновляете свои MarkableReference с новым указателем и булевым соединением, вложение данных в указатель, вероятно, полезно для производительности. В противном случае это, вероятно, плохо, если вы можете заставить компилятор сделать эффективный код для отдельного элемента.

Кроме того, если вам часто требуется как указатель, так и флаг атомарно, способ вложенных данных подходит для этого.

---

реализация Цыварев должен измениться для реализации атомарной модификации булева без установки нового указателя. class MarkableReference должен иметь атомную переменную-член, поэтому он может использовать fetch_or и тому подобное.

Это не проверено, но оно компилируется в код, который выглядит правильно (on the Godbolt compiler explorer).

На x86-64 вы можете позволить этому работать даже для невыровненных указателей, используя высокий бит указателя вместо младшего разряда. x86-64 requires that virtual addresses have their top 16 bits matching the 48th bit, то есть 64-разрядные адреса - это 48-разрядные адреса с расширенными знаками. Будущие процессоры x86-64 могли бы расширить это в будущем, однако, позволяя полное 64-битное виртуальное адресное пространство вместо текущего 48-битного.Затем вам придется запускать программы, используя этот код, в режиме совместимости, где ОС никогда не дает им адреса, которые были «неканоническими» в соответствии со старыми правилами.

#include <atomic> 
#include <assert.h> 

template<class T> 
class MarkableReference 
{ 
private: 
    std::atomic<uintptr_t> val; 
    static const uintptr_t mask = 1; 
    uintptr_t combine(T* ref, bool mark) { 
     return reinterpret_cast<uintptr_t>(ref) | mark; 
    } 

public: 
    MarkableReference(T* ref, bool mark) 
     : val(combine(ref, mark)) 
    { 
     // note that construction of an atomic is not *guaranteed* to be atomic, in case that matters. 
     // On most real CPUs, storing a single aligned pointer-sized integer is atomic 
     // This does mean that it's not a seq_cst operation, so it doesn't synchronize with anything 
     // (and there's no MFENCE required) 
     assert((reinterpret_cast<uintptr_t>(ref) & mask) == 0 && "only works with pointers that have the low bit cleared"); 
    } 

    MarkableReference(MarkableReference &other, std::memory_order order = std::memory_order_seq_cst) 
     : val(other.val.load(order)) 
    {} 
    // IDK if relaxed is the best choice for this, or if it should exist at all 
    MarkableReference &operator=(MarkableReference &other) 
    { 
     val.store(other.val.load(std::memory_order_relaxed), std::memory_order_relaxed); 
     return *this; 
    } 

/////// Getters 

    T* getRef(std::memory_order order = std::memory_order_seq_cst) 
    { 
     return reinterpret_cast<T*>(val.load(order) & ~mask); 
    } 
    bool getMark(std::memory_order order = std::memory_order_seq_cst) 
    { 
     return (val.load(order) & mask); 
    } 
    T* getBoth(bool& mark, std::memory_order order = std::memory_order_seq_cst) 
    { 
     uintptr_t current = val.load(order); 
     mark = expected & mask; 
     return reinterpret_cast<T*>(expected & ~mask); 
    } 

/////// Setters (and exchange) 

    // memory_order_acq_rel would be a good choice here 
    T* xchgRef(T* ref, std::memory_order order = std::memory_order_seq_cst) 
    { 
     uintptr_t old = val.load(std::memory_order_relaxed); 
     bool success; 
     do { 
      uintptr_t newval = reinterpret_cast<uintptr_t>(ref) | (old&mask); 
      success = val.compare_exchange_weak(old, newval, order); 
      // updates old on failure 
     } while(!success); 

     return reinterpret_cast<T*>(old & ~mask); 
    } 

    bool cmpxchgBoth_weak(T* &expectRef, bool& expectMark, T* desiredRef, bool desiredMark, std::memory_order order = std::memory_order_seq_cst) 
    { 
     uintptr_t desired = combine(desiredRef, desiredMark); 
     uintptr_t expected = combine(expectRef, expectMark); 
     bool status = compare_exchange_weak(expected, desired, order); 
     expectRef = reinterpret_cast<T*>(expected & ~mask); 
     expectMark = expected & mask; 
     return status; 
    } 

    void setRef(T* ref, std::memory_order order = std::memory_order_seq_cst) 
    { xchgReg(ref, order); } // I don't see a way to avoid cmpxchg without a non-atomic read-modify-write of the boolean. 
    void setRef_nonatomicBoolean(T* ref, std::memory_order order = std::memory_order_seq_cst) 
    { 
     uintptr_t old = val.load(std::memory_order_relaxed); // maybe provide a way to control this order? 
     // !!modifications to the boolean by other threads between here and the store will be stepped on! 
     uintptr_t newval = combine(ref, old&mask); 
     val.store(newval, order); 
    } 


    void setMark(bool mark, std::memory_order order = std::memory_order_seq_cst) 
    { 
     if(mark) 
      val.fetch_or(mask, order); 
     else 
      val.fetch_and(~mask, order); 
    } 

    bool toggleMark(std::memory_order order = std::memory_order_seq_cst) 
    { 
      return mask & val.fetch_xor(mask, order); 
    } 

    bool xchgMark(bool mark, std::memory_order order = std::memory_order_seq_cst) 
    { 
     // setMark might still compile to efficient code if it just called this and let the compile optimize away the fetch part 
     uintptr_t old; 
     if(mark) 
      old = val.fetch_or(mask, order); 
     else 
      old = val.fetch_and(~mask, order); 
     return (old & mask); 
     // It might be ideal to compile this to x86 BTS or BTR instructions (when the old value is needed) 
     // but clang uses a cmpxchg loop. 
    } 
}; 

---

Примеры использования, с выходом ассемблерном, показывающие, что это компилирует эффективно. (см. Ссылку на ботбол) выше

int a; 
int b; 
MarkableReference<int> mr_a(&a, true); 
MarkableReference<int> mr_b(&b, false); 


bool getbool(MarkableReference<int> &mr) { 
    return mr.getMark(); // using the default memory_order_seq_cst 
} 
    mov  rax, qword ptr [rdi] 
    and  eax, 1 
    ret 

void storeToRef(MarkableReference<int> &mr, int val) { 
    //(*mr.getRef(memory_order_relaxed)) = val; // less code on weakly-ordered CPUs like MIPS 
    (*mr.getRef()) = val; 
} 
    mov  rax, qword ptr [rdi] 
    and  rax, -2 
    mov  dword ptr [rax], esi 
    ret 

void foo() { 
    mr_a.setMark(true, memory_order_relaxed); 
} 
    lock 
    or  qword ptr [rip + mr_a], 1 
    ret 


void bar() { 
    mr_b = mr_a; 
} 
    // no MFENCE since I decided to make operator= use memory_order_relaxed. acquire/release would also not need MFENCE on x86 
    mov  rax, qword ptr [rip + mr_a] 
    mov  qword ptr [rip + mr_b], rax 
    ret 

// this one compiles to a cmpxchg loop and a branch :/ 
// but I think that's unavoidable 
void baz() { 
    bool tmp = mr_b.xchgMark(false); 
    mr_a.setMark(tmp); 
} 

    mov  rax, qword ptr [rip + mr_b] 

.LBB4_1:        # =>This Inner Loop Header: Depth=1 
    mov  rcx, rax 
    and  rcx, -2 
    lock cmpxchg qword ptr [rip + mr_b], rcx 
    jne  .LBB4_1 

    test al, 1 
    jne  .LBB4_3 

    lock and  qword ptr [rip + mr_a], -2 
    ret 

.LBB4_3: 
    lock or  qword ptr [rip + mr_a], 1 
    ret