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

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

E9: if CAS(&tail.ptr->next, next, ) 

Это атомная операция, то есть если 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 одновременно.

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

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

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

(представленная ошибка GCC 80835 об этом. TODO: то же самое для clang, если это полезная идея.)


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

  • Убедитесь, что ваш компилятор создает эффективный код для загрузки только одного члена в режиме только для чтения, а не для 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), но после этого должен быть на все. Без -mcx16 вы получаете вызов функции библиотеки (который, вероятно, использует глобальную блокировку). 32-разрядный эквивалент, cmpxchg8b , достаточно стар, что современные компиляторы принимают на себя поддержку. (И может использовать SSE, MMX или даже x87 для 64-битных атомных нагрузок / хранилищ, поэтому использование соединения несколько менее важно для хорошей производительности при чтении одного элемента).

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

    gcc7 и позже вызовут libatomic вместо того, чтобы вставить lock cmpxchg16b , и вернет false из atomic_is_lock_free ( по причинам, в том числе, что это так медленно, это не то, что пользователи ожидают, что is_lock_free означает ), но по крайней мере на данный момент libatomic-реализация по-прежнему использует lock cmpxchg16b для целей где эта инструкция доступна. (Он может даже segfault для атомных объектов только для чтения, поэтому он действительно не идеален.)


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

См. Код с выходом asm из gcc6.3 в проводнике компилятора Godbolt . С -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_separate , поэтому static_assert его ловит. Предположительно, MSVC включает в себя элемент блокировки в атомарном объекте.

 #include  #include  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 ptr; atomic count_separate; // var name emphasizes that accessing this way isn't atomic with ptr }; static_assert(sizeof(atomic) == sizeof(counted_ptr_separate), "atomic isn't the same size as the separate version; union type-punning will be bogus"); //static_assert(std::atomic{}.is_lock_free()); union { // anonymous union: the members are directly part of struct node alignas(2*sizeof(node*)) atomic 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 из clang 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 

gcc делает некоторые неуклюжие хранилища / перезагрузки, но в основном та же логика.

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


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

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

Не относится к указателю + ABA-счетчик, но может появиться в других приложениях с использованием объединения, чтобы разрешить доступ к подмножествам большего атомного объекта. Не используйте объединение, чтобы атомные хранилища могли указывать только указатель или только счетчик . По крайней мере, если вам не нужна синхронизация с нагрузкой на пару. Даже сильно упорядоченная x86 может изменить порядок узкого хранилища с более широкой нагрузкой, которая полностью ее содержит . Все по-прежнему является атомарным, но вы попадаете в странную территорию по мере упорядочения памяти.

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


Чтобы узнать больше о приобретении и выпуске std :: memory_order , см . Превосходные статьи Джеффа Прешинга .

  • Что такое блокировка и концепция Re-entrant в целом?
  • Быстрый и грязный способ обеспечения одновременного запуска только одного экземпляра сценария оболочки
  • Блокировка ориентации экрана
  • Является ли Task.Factory.StartNew () гарантией использовать другой stream, чем вызывающий stream?
  • Как отключить домашние и другие системные кнопки в Android?
  • Портативная библиотека сравнения и свопинга (атомарные операции) C / C ++?
  • Давайте будем гением компьютера.