Где замок для std :: atomic?

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

например:

#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 имеют одинаковый размер, я не думаю, что в атоме хранится блокировка.

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

Ответ 1

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

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

#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);
}

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

Ответ 2

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 3

Из 29.5.9 стандарта C++:

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

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