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

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

0 голосов
/ 11 мая 2018

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

например: 

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

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

Ответы [ 3 ]

0 голосов
/ 11 мая 2018

Обычная реализация - это хеш-таблица мьютексов (или просто простых спин-блокировок без возврата в режим сна / пробуждения с помощью ОС) с использованием адреса атомарного объекта в качестве ключа . Хеш-функция может быть такой же простой, как просто использование младших битов адреса в качестве индекса в массиве степени 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 байтами 1 .

AFAIK, MSVC никогда не использует lock cmpxchg16b для 16-байтовых объектов, и они в основном совпадают с 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 + счетчик на x86-64 с помощью gcc / clang: Как реализовать счетчик ABA с c ++ 11 CAS? . lock cmpxchg16b для обновлений указателя и счетчика, но простой mov загружает только указатель. Это работает только в том случае, если 16-байтовый объект фактически свободен от блокировки, используя lock cmpxchg16b.

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

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

0 голосов
/ 11 мая 2018

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

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

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

0 голосов
/ 11 мая 2018

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

Скомпилировать следующее (я увеличил вашу структуру, чтобы избежать хитрых компиляторов 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);
}

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

...