Где находится замок для std:: atomic?

Question

Где находится замок для 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):

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

мой вопрос:

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

580 3

c++c++11 x86 atomic

3 ответов:

Comments

Ничего не найдено.

Frank · Accepted Answer · 2018-05-16 19:49:47

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

компиляция следующего (я сделал вашу структуру больше, чтобы увернуться от хитрых махинаций компилятора):
#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);
}
и вот наше объяснение: адрес атома используется для генерации хэш-ключа для выбора предварительно размещенного замка.

Peter Cordes · Accepted Answer · 2018-05-11 23:20:57

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

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

хэш-коллизии означают, что два атомарных объекта могут иметь одну и ту же блокировку. Это не корректность проблема, но это может быть проблема производительности: вместо двух пар потоков, отдельно конкурирующих друг с другом за два разных объекта, вы можете иметь все 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-байтовые объекты как свободные от блокировки, даже если libatomic функции все равно будут использовать lock cmpxchg16b на машинах, где инструкция имеется. Смотрите is_lock_free () возвратил false после обновления до MacPorts gcc 7.3. Сообщение списка рассылки gcc, объясняющее это изменение здесь.

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

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

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

Hadi Brais · Accepted Answer · 2018-05-11 22:25:31

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

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

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