Как я могу реализовать счетчик ABA с C++ 11 CAS?

Question

Я реализую незаблокированную очередь на основе этого algorithm, который использует счетчик для решения проблемы ABA. Но я не знаю, как реализовать этот счетчик с C++ 11 CAS. Так, например, из алгоритма:

E9: if CAS(&tail.ptr->next, next, <node, next.count+1>) 

Это является атомарной операцией, то есть, если tail.ptr->next равно next, пусть tail.ptr->next пункт node и одновременно (атомарно) сделать next.count+1. Тем не менее, с помощью C++ 11 CAS, я могу только реализовать:

std::atomic_compare_exchange_weak(&tail.ptr->next, next, node); 

, которые не могут сделать next.count+1 одновременно произойдет.

Answer 1

Чтобы атомно изменить две вещи одновременно с помощью одной атомной операции, вам необходимо поместить их в соседнюю память, например. в структуре с двумя элементами. Затем вы можете использовать std::atomic<my_struct>, чтобы получить gcc для испускания lock cmpxchg16b на x86-64, например.

Для этого не требуется встроенный asm, и для его устранения стоит немного синтаксиса Си ++. https://gcc.gnu.org/wiki/DontUseInlineAsm.

К сожалению, с текущими компиляторами вы должны использовать union, чтобы получить эффективный код для чтения только одной из пары. «Очевидный» способ выполнения атомной нагрузки структуры, а затем только с использованием одного члена, все же приводит к lock cmpxchg16b, чтобы прочитать всю структуру, хотя нам нужен только один элемент. Я уверен, что нормальная 64-разрядная нагрузка указателя по-прежнему будет правильно реализовывать семантику получения порядка памяти на x86 (а также атомарность), но текущие компиляторы не делают эту оптимизацию даже для std::memory_order_relaxed, поэтому мы обманываем их в нее с союзом.

(., Представленный GCC bug 80835 об этом TODO:. То же самое для лязгом если это полезная идея)

---

Контрольный список:

• Убедитесь, что ваш компилятор генерирует эффективный код для загрузки только один член в случае только для чтения, а не lock cmpxchg16b пары. например используя союз.
• Убедитесь, что ваш компилятор гарантирует, что доступ к одному члену союза после написания другого члена профсоюза имеет четко определенное поведение в этой реализации. Union type-punning имеет право на C99 (так что это должно хорошо работать с C11 stdatomic), но это UB в ISO C++ 11. Однако это законно на диалекте GNU C++ (поддерживается, в частности, gcc, clang и ICC).
• Убедитесь, что ваш объект выровнен по 16B или 8B-выровненный для 32-разрядных указателей. В более общем плане, alignas(2*sizeof(void*)) должен работать. Misaligned lock ed инструкции могут быть очень медленно на x86, особенно если они пересекают границу линии кэша. clang3.8 даже компилирует его в вызов библиотеки, если объект не выровнен.

• Скомпилировать с -mcx16 для сборки x86-64. cmpxchg16b не был поддержан самыми ранними процессорами x86-64 (AMD K8), но должен быть на все после этого. Без вы получаете вызов функции библиотеки (который, вероятно, использует глобальную блокировку).32-разрядный эквивалент, cmpxchg8b, достаточно стар, что современные компиляторы принимают на себя поддержку. (И может использовать SSE, MMX или даже x87 для 64-битных атомных нагрузок/хранилищ, поэтому использование соединения несколько менее важно для хорошей производительности при чтении одного элемента).

• Убедитесь, что объект-указатель + uintptr_t не заблокирован. Это в значительной степени гарантируется для x32 и 32-разрядных ABI (объект 8B), но не для объектов 16B. например MSVC использует блокировку для x86-64.

  gcc7 и позже будет вызывать libatomic вместо встраивания lock cmpxchg16b и вернет ложь из atomic_is_lock_free (for reasons including that it's so slow it's not what users expect is_lock_free to mean), но, по крайней мере, на данный момент libatomic реализация все еще использует lock cmpxchg16b на цели, где эта команда доступна. (Это может даже сегментации только для чтения атомных объектов, так что это на самом деле не идеал.)

---

Вот пример кода с CAS Retry-цикл, который компилирует в ассемблере, который выглядит правильно, и я думаю, свободен от UB или других небезопасных C++ для реализаций, которые позволяют использовать тип объединения Punning. Он написан в стиле C (не-членские функции и т. Д.), Но это было бы одинаково, если бы вы написали функции-члены.

См. Код с выходом asm from gcc6.3 on the Godbolt compiler explorer. С -m32 он использует cmpxchg8b так же, как 64-разрядный код использует cmpxchg16b. С -mx32 (32-разрядные указатели в длинном режиме) он может просто использовать 64-разрядный cmpxchg и обычные 64-разрядные целые нагрузки для захвата обоих членов в одной атомной нагрузке.

Это переносимый C++ 11 (за исключением типа union-punning), который не имеет значения x86. Это только эффективный на цели, которые могут CAS объект размером с два указателя., например. он компилируется для вызова функции библиотеки __atomic_compare_exchange_16 для ARM/ARM64 и MIPS64, как вы можете видеть на Godbolt.

Он не компилируется на MSVC, где atomic<counted_ptr> больше, чем counted_ptr_separate, поэтому static_assert ловит его. Предположительно, MSVC включает в себя элемент блокировки в атомарном объекте.

#include <atomic> 
#include <stdint.h> 

using namespace std; 

struct node { 
    // This alignas is essential for clang to use cmpxchg16b instead of a function call 
    // Apparently just having it on the union member isn't enough. 
    struct alignas(2*sizeof(node*)) counted_ptr { 
    node * ptr; 
    uintptr_t count; // use pointer-sized integers to avoid padding 
    }; 

    // hack to allow reading just the pointer without lock-cmpxchg16b, 
    // but still without any C++ data race 
    struct counted_ptr_separate { 
    atomic<node *> ptr; 
    atomic<uintptr_t> count_separate; // var name emphasizes that accessing this way isn't atomic with ptr 
    }; 

    static_assert(sizeof(atomic<counted_ptr>) == sizeof(counted_ptr_separate), "atomic<counted_ptr> isn't the same size as the separate version; union type-punning will be bogus"); 
    //static_assert(std::atomic<counted_ptr>{}.is_lock_free()); 

    union { // anonymous union: the members are directly part of struct node 
    alignas(2*sizeof(node*)) atomic<counted_ptr> next_and_count; 
    counted_ptr_separate next; 
    }; 
    // TODO: write member functions to read next.ptr or read/write next_and_count 

    int data[4]; 
}; 


// make sure read-only access is efficient. 
node *follow(node *p) { // good asm, just a mov load 
    return p->next.ptr.load(memory_order_acquire); 
} 
node *follow_nounion(node *p) { // really bad asm, using cmpxchg16b to load the whole thing 
    return p->next_and_count.load(memory_order_acquire).ptr; 
} 


void update_next(node &target, node *desired) 
{ 
    // read the old value efficiently to avoid overhead for the no-contention case 
    // tearing (or stale data from a relaxed load) will just lead to a retry 
    node::counted_ptr expected = { 
     target.next.ptr.load(memory_order_relaxed), 
     target.next.count_separate.load(memory_order_relaxed) }; 

    bool success; 
    do { 
    node::counted_ptr newval = { desired, expected.count + 1 }; 
    // x86-64: compiles to cmpxchg16b 
    success = target.next_and_count.compare_exchange_weak(
          expected, newval, memory_order_acq_rel); 
    // updates exected on failure 
    } while(!success); 
} 

Выход ASM из лязга 4,0 -O3 -mcx16 является:

update_next(node&, node*): 
    push rbx    # cmpxchg16b uses rbx implicitly so it has to be saved/restored 
    mov  rbx, rsi 
    mov  rax, qword ptr [rdi]  # load the pointer 
    mov  rdx, qword ptr [rdi + 8] # load the counter 
.LBB2_1:      # =>This Inner Loop Header: Depth=1 
    lea  rcx, [rdx + 1] 
    lock 
    cmpxchg16b  xmmword ptr [rdi] 
    jne  .LBB2_1 
    pop  rbx 
    ret 

НКУ делают некоторые неуклюжий магазин/перезагружается, но в основном такой же логик.

follow(node*) компилируется в mov rax, [rdi]/ret, поэтому доступ к указателю только для чтения столь же дешев, как и должно быть, благодаря взлому профсоюза.

---

Это зависит от написания союза через одного члена и читать его через другой, чтобы сделать эффективными считывание только указатель без использования lock cmpxchg16b. Это гарантированно работает в GNU C++ (и ISO C99/C11), но не в ISO C++. Многие другие компиляторы C++ гарантируют, что объединение типа-punning работает, но даже без этого оно, вероятно, все еще будет работать: мы всегда используем нагрузки std::atomic, которые должны предполагать, что значение было изменено асинхронно. Таким образом, мы должны быть защищены от проблем с псевдонимом, где значения в регистрах по-прежнему считаются живыми после записи значения через другой указатель (или член профсоюза).Однако компиляционное переупорядочение вещей, которые, по мнению компилятора, независимы, может быть проблемой.

Атомно считывая только указатель после атомарного cmpxchg указателя + счетчик, вы все равно должны получать семантику получения/выпуска на x86, но я не думаю, что ISO C++ говорит об этом. Я бы предположил, что широкий релиз-магазин (как часть compare_exchange_weak будет синхронизироваться с более узкой нагрузкой с одного и того же адреса на большинстве архитектур (например, на x86), но AFAIK C++ std::atomic ничего не гарантирует о типе .

Не относится к указателю + ABA-счетчик, но может появиться в других приложениях с использованием объединения, чтобы разрешить доступ к подмножествам большего атомного объекта: Не используйте объединение, чтобы атомные хранилища могли указывать только указатель или просто счетчик. По крайней мере, если вам не нужна синхронизация с приобретаемой нагрузкой пары. Даже сильно упорядоченный x86 может reorder a narrow store with a wider load that fully contains it. Все по-прежнему является атомарным, но вы попадаете в странную территорию, насколько это касается порядка памяти.

На x86-64 для атомной нагрузки 16B требуется lock cmpxchg16b (что является полным барьером памяти, что препятствует тому, чтобы предыдущий узкий магазин стал глобально видимым после него). Но вы могли бы легко иметь проблему, если бы использовали это с 32-разрядными указателями (или 32-разрядными индексами массива), поскольку обе половины могли быть загружены с регулярным 64b-загрузкой. И я понятия не имею, какие проблемы вы можете увидеть на других архитектурах, если вам нужна синхронизация с другими потоками, а не просто атомарность.

---

Чтобы узнать больше о станд :: memory_order приобретать и освободить см Jeff Preshing's excellent articles.