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

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

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

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

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

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

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

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

• Убедитесь, что указатель + атомный объект 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 на цели, где эта инструкция доступна. (Он может даже сегрегироваться для атомарных объектов, доступных только для чтения, поэтому он на самом деле не идеален.)

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

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

Это переносимый C ++ 11 (за исключением объединения типов), без специфической для 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 выход из 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так что доступ только для чтения к указателю так же дешев, как и должно быть, благодаря взлому union.

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

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

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

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

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