Где блокировка для std::atomic?

Question

Если структура данных содержит несколько элементов, атомарная версия не может (всегда) быть свободной от блокировок. Мне сказали, что это верно для больших типов, потому что процессор не может атомарно изменить данные без использования какой-либо блокировки.

например:

#include <iostream>
#include <atomic>

struct foo {
    double a;
    double b;
};

std::atomic<foo> var;

int main()
{
    std::cout << var.is_lock_free() << std::endl;
    std::cout << sizeof(foo) << std::endl;
    std::cout << sizeof(var) << std::endl;
}

вывод (Linux/gcc):

0
16
16

Так как атомная и foo одинакового размера, я не думаю, что замок хранится в атомарной.

Мой вопрос:
Если атомарная переменная использует блокировку, где она хранится и что это означает для нескольких экземпляров этой переменной?

Answer 1

Самый простой способ ответить на такие вопросы - это просто посмотреть на получившуюся сборку и взять ее оттуда.

Компилируем следующее (я увеличил вашу структуру, чтобы избежать хитроумных компиляторов):

#include <atomic>

struct foo {
    double a;
    double b;
    double c;
    double d;
    double e;
};

std::atomic<foo> var;

void bar()
{
    var.store(foo{1.0,2.0,1.0,2.0,1.0});
}

В clang 5.0.0 выдает следующее под -O3: смотри на godbolt

bar(): # @bar()
  sub rsp, 40
  movaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [1.000000e+00,2.000000e+00]
  movaps xmmword ptr [rsp], xmm0
  movaps xmmword ptr [rsp + 16], xmm0
  movabs rax, 4607182418800017408
  mov qword ptr [rsp + 32], rax
  mov rdx, rsp
  mov edi, 40
  mov esi, var
  mov ecx, 5
  call __atomic_store

Отлично, компилятор делегирует внутреннему (__atomic_store), это не говорит нам, что на самом деле здесь происходит. Однако, поскольку компилятор с открытым исходным кодом, мы можем легко найти реализацию встроенного (я нашел его в https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/atomic.c):

void __atomic_store_c(int size, void *dest, void *src, int model) {
#define LOCK_FREE_ACTION(type) \
    __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\
    return;
  LOCK_FREE_CASES();
#undef LOCK_FREE_ACTION
  Lock *l = lock_for_pointer(dest);
  lock(l);
  memcpy(dest, src, size);
  unlock(l);
}

Кажется, магия происходит в lock_for_pointer()Итак, давайте посмотрим на это:

static __inline Lock *lock_for_pointer(void *ptr) {
  intptr_t hash = (intptr_t)ptr;
  // Disregard the lowest 4 bits.  We want all values that may be part of the
  // same memory operation to hash to the same value and therefore use the same
  // lock.  
  hash >>= 4;
  // Use the next bits as the basis for the hash
  intptr_t low = hash & SPINLOCK_MASK;
  // Now use the high(er) set of bits to perturb the hash, so that we don't
  // get collisions from atomic fields in a single object
  hash >>= 16;
  hash ^= low;
  // Return a pointer to the word to use
  return locks + (hash & SPINLOCK_MASK);
}

И вот наше объяснение: адрес атомарного используется для генерации хеш-ключа для выбора предварительно выделенной блокировки.

Answer 2

Обычная реализация - это хеш-таблица мьютексов (или просто простых спин-блокировок без возврата в режим сна / пробуждения с помощью ОС) с использованием адреса атомарного объекта в качестве ключа. Хэш-функция может быть такой же простой, как просто использование младших битов адреса в качестве индекса в массиве степени 2, но ответ @Frank показывает, что реализация std:: atomic в LLVM выполняет XOR в некоторых старших битах, поэтому t автоматически получают псевдонимы, когда объекты разделены большой степенью 2 (что более распространено, чем любое другое случайное расположение).

Я думаю (но я не уверен), что g++ и clang++ совместимы с ABI; то есть они используют одну и ту же хеш-функцию и таблицу, поэтому они согласны с тем, какая блокировка сериализует доступ к какому объекту. Блокировка все сделано в libatomicТем не менее, так что если вы динамически связываете libatomic тогда весь код внутри той же программы, которая вызывает __atomic_store_16 будет использовать ту же реализацию; clang++ и g++ определенно договариваются о том, какие имена функций вызывать, и этого достаточно. (Но обратите внимание, что будут работать только атомарные объекты без блокировок в разделяемой памяти между различными процессами: каждый процесс имеет свою собственную хэш-таблицу блокировок. Предполагается, что объекты без блокировок должны (и фактически выполняют) просто работать в общей памяти на обычном процессоре архитектуры, даже если регион сопоставлен с разными адресами.)

Хеш-коллизии означают, что два атомных объекта могут иметь один и тот же замок.Это не проблема правильности, но это может быть проблема производительности: вместо двух пар потоков, отдельно конкурирующих друг с другом за два разных объекта, вы можете иметь все 4 потока, борющихся за доступ к любому объекту. Предположительно, это необычно, и обычно вы стремитесь к тому, чтобы ваши атомные объекты были свободны от блокировки на платформах, которые вас интересуют. Но в большинстве случаев вам не очень везет, и в целом это нормально.

Тупики не возможны, потому что нетstd::atomicфункции, которые пытаются заблокировать два объекта одновременно. Таким образом, код библиотеки, который берет блокировку, никогда не пытается взять другую блокировку, удерживая одну из этих блокировок. Дополнительный конфликт / сериализация - это не проблема правильности, а просто производительность.

---

x86-64 16-байтовые объекты с GCC и MSVC:

Как взломать, компиляторы могут использоватьlock cmpxchg16bреализовать 16-байтовую атомарную загрузку / сохранение, а также фактические операции чтения-изменения-записи.

Это лучше, чем блокировка, но имеет плохую производительность по сравнению с 8-байтовыми атомарными объектами (например, чистые нагрузки конкурируют с другими нагрузками). Это единственный документированный безопасный способ атомарного выполнения чего-либо с 16 байтами¹.

AFAIK, MSVC никогда не используетlock cmpxchg16bдля 16-байтовых объектов, и они в основном совпадают с 24- или 32-байтовыми объектами.

gcc6 и ранее встроенныйlock cmpxchg16b когда вы компилируете с -mcx16 (К сожалению, cmpxchg16b не является базовым для x86-64; в процессорах AMD K8 первого поколения он отсутствует.)

gcc7 решил всегда звонить libatomic и никогда не сообщать о 16-байтовых объектах как свободных от блокировки, даже если либатомические функции все еще будут использовать lock cmpxchg16b на машинах, где есть инструкция. См. Is_lock_free() вернул false после обновления до MacPorts gcc 7.3. Сообщение со списком рассылки gcc, объясняющее это изменение, находится здесь.

Вы можете использовать объединенный хак, чтобы получить достаточно дешевый указатель ABA + счетчик на x86-64 с помощью gcc/clang: Как я могу реализовать счетчик ABA с C++11 CAS?, lock cmpxchg16b для обновления указателя и счетчика, но просто mov загружает только указатель. Это работает только в том случае, если 16-байтовый объект фактически не блокируется с помощью lock cmpxchg16b, хоть.

---

Сноска 1: movdqa На некоторых (но не на всех) микроархитектурах x86 на практике 16-байтовая загрузка / сохранение является атомарным, и нет надежного или документированного способа определить, когда его можно использовать. См. Почему целочисленное присваивание естественно выровненной переменной атомарно в x86? и инструкции SSE: какие процессоры могут выполнять атомные операции памяти 16B? для примера, где K10 Opteron показывает разрыв на границах 8B только между сокетами с HyperTransport.

Так что авторы компилятора должны ошибаться на стороне осторожности и не могут использовать movdqa как они используют SSE2 movq для 8-байтовой атомарной загрузки / хранения в 32-битном коде. Было бы замечательно, если бы поставщики ЦП могли документировать некоторые гарантии для некоторых микроархитектур или добавить функциональные биты CPUID для атомарной 16 / 32- и 64-байтовой выровненной векторной загрузки / сохранения (с SSE, AVX и AVX512). Может быть, какие поставщики mobo могли бы отключить в прошивке на фанк-машинах с многими сокетами, которые используют специальные связующие чипы когерентности, которые не передают целые строки кэша атомарно.

Answer 3

С 29.5.9 стандарта C++:

Примечание: представление атомарной специализации не обязательно должно иметь тот же размер, что и соответствующий ему тип аргумента. Специализации должны иметь одинаковый размер, когда это возможно, поскольку это уменьшает усилия, необходимые для переноса существующего кода. - конец примечания

Желательно, чтобы размер атома соответствовал размеру его аргумента, хотя и не обязательно. Способ достижения этого - либо избегать замков, либо хранить замки в отдельной структуре. Как уже ясно объяснили другие ответы, для хранения всех блокировок используется хеш-таблица. Это наиболее эффективный способ памяти для хранения любого количества блокировок для всех используемых атомарных объектов.