Où se trouve le verrou pour un std::atomic ?

Question

Si une structure de données contient plusieurs éléments, sa version atomique ne peut pas (toujours) être sans verrou. On m'a dit que c'est vrai pour les grands types parce que le CPU ne peut pas changer les données de façon atomique sans utiliser une sorte de verrou.

par exemple :

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

la sortie (Linux/gcc) est :

0
16
16

Étant donné que l'atome et le foo sont de la même taille, je ne pense pas qu'un verrou soit stocké dans l'atomique.

Ma question est la suivante :
Si une variable atomique utilise un verrou, où est-il stocké et qu'est-ce que cela signifie pour les instances multiples de cette variable ?

Answer 1

L'implémentation habituelle est une table de hachage de mutex (ou même de simples spinlocks sans repli sur le sleep/wakeup assisté par le système d'exploitation), utilisant l'adresse de l'objet atomique comme clé. . La fonction de hachage pourrait être aussi simple que d'utiliser les bits de poids faible de l'adresse comme index dans un tableau de la taille d'une puissance de 2, mais la réponse de @Frank montre que l'implémentation std::atomic de LLVM effectue un XOR dans certains bits de poids fort afin de ne pas obtenir automatiquement un aliasing lorsque les objets sont séparés par une grande puissance de 2 (ce qui est plus courant que tout autre arrangement aléatoire).

Je pense (mais je n'en suis pas sûr) que g++ et clang++ sont compatibles ABI ; c'est-à-dire qu'ils utilisent la même fonction de hachage et la même table, et qu'ils se mettent d'accord sur quel verrou sérialise l'accès à quel objet. Le verrouillage est effectué dans libatomic Cependant, si vous liez dynamiquement libatomic alors tout le code à l'intérieur du même programme qui appelle __atomic_store_16 utiliseront la même implémentation ; clang++ et g++ sont d'accord sur les noms des fonctions à appeler, et c'est suffisant. (Mais notez que seuls les objets atomiques sans verrou dans la mémoire partagée entre différents processus fonctionnent : chaque processus a sa propre table de hachage des verrous. . Les objets sans verrou sont censés (et le font en fait) Just Work dans la mémoire partagée sur les architectures CPU normales, même si la région est mappée à des adresses différentes).

Les collisions de hachage signifient que deux objets atomiques peuvent partager le même verrou. Ce n'est pas un problème de correction, mais cela peut être un problème de performance. Au lieu que deux paires de threads se disputent séparément deux objets différents, les quatre threads pourraient se disputer l'accès à l'un ou l'autre des objets. On peut supposer que c'est inhabituel et qu'en général, vous cherchez à ce que vos objets atomiques soient libres de verrouillages sur les plateformes qui vous intéressent. Mais la plupart du temps, vous n'êtes pas vraiment malchanceux, et tout va bien.

Les blocages ne sont pas possibles parce qu'il n'y en a pas std::atomic les fonctions qui tentent de prendre le verrou sur deux objets à la fois. Ainsi, le code de la bibliothèque qui prend le verrou n'essaie jamais de prendre un autre verrou lorsqu'il détient l'un de ces verrous. La contention / sérialisation supplémentaire n'est pas un problème de correction, mais seulement de performance.

---

Objets x86-64 de 16 octets avec GCC vs. MSVC :

En guise d'astuce, les compilateurs peuvent utiliser lock cmpxchg16b pour mettre en œuvre un chargement/stockage atomique de 16 octets, ainsi que des opérations réelles de lecture-modification-écriture.

C'est mieux que le verrouillage, mais les performances sont mauvaises par rapport aux objets atomiques de 8 octets (par exemple, les charges pures entrent en conflit avec d'autres charges). C'est le seul moyen sûr documenté de faire quelque chose d'atomique avec 16 octets. 1 .

AFAIK, MSVC n'utilise jamais lock cmpxchg16b pour les objets de 16 octets, et ils sont fondamentalement les mêmes qu'un objet de 24 ou 32 octets.

gcc6 et antérieurs inlined lock cmpxchg16b lorsque vous compilez avec -mcx16 (cmpxchg16b n'est malheureusement pas une base de référence pour x86-64 ; les CPU AMD K8 de première génération en sont dépourvus).

gcc7 a décidé de toujours appeler libatomic et ne signalent jamais les objets de 16 octets comme étant libres de verrouillages, même si les fonctions libatomiques utilisent toujours lock cmpxchg16b sur les machines où l'instruction est disponible. Voir is_lock_free() retourne false après la mise à jour vers MacPorts gcc 7.3 . Le message de la liste de diffusion de gcc expliquant ce changement est ici .

Vous pouvez utiliser un hack d'union pour obtenir un pointeur+compteur ABA raisonnablement bon marché sur x86-64 avec gcc/clang : Comment puis-je implémenter un compteur ABA avec le CAS c++11 ? . lock cmpxchg16b pour les mises à jour du pointeur et du compteur, mais de simples mov au lieu du simple pointeur. Cela ne fonctionne que si l'objet de 16 octets est effectivement libre de tout verrouillage en utilisant lock cmpxchg16b mais

---

Note de bas de page 1 : movdqa Le chargement/stockage de 16 octets est atomique dans la pratique sur certaines (mais no toutes) les microarchitectures x86, et il n'existe aucun moyen fiable ou documenté de détecter quand il est utilisable. Voir Pourquoi l'affectation d'un nombre entier sur une variable alignée naturellement est atomique sur x86 ? et Instructions SSE : quels processeurs peuvent effectuer des opérations mémoire atomiques de 16B ? pour un exemple où l'Opteron K10 montre des déchirures aux frontières 8B seulement entre les sockets avec HyperTransport.

Les auteurs de compilateurs doivent donc pécher par excès de prudence et ne peuvent pas utiliser movdqa la façon dont ils utilisent SSE2 movq pour le chargement/stockage atomique de 8 octets en code 32 bits. Ce serait formidable si les fournisseurs de processeurs pouvaient documenter certaines garanties pour certaines microarchitectures, ou ajouter des bits de caractéristiques CPUID pour le chargement/stockage atomique de vecteurs alignés de 16, 32 et 64 octets (avec SSE, AVX et AVX512). Peut-être que les vendeurs de mobo pourraient désactiver dans le firmware les machines funky à plusieurs sockets qui utilisent des puces de cohérence spéciales qui ne transfèrent pas des lignes entières de cache de manière atomique.

Answer 2

La façon la plus simple de répondre à ce genre de questions est généralement de regarder l'assemblage qui en résulte et d'en déduire ce qu'il en est.

Compiler ce qui suit (j'ai agrandi votre struct pour éviter les manigances du compilateur) :

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

Dans clang 5.0.0, on obtient le résultat suivant sous -O3 : voir sur 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

Grande, le compilateur délègue à un intrinsèque ( __atomic_store ), cela ne nous dit pas ce qui se passe réellement ici. Cependant, puisque le compilateur est open source, nous pouvons facilement trouver l'implémentation de l'intrinsèque (je l'ai trouvé dans 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);
}

Il semble que la magie opère dans lock_for_pointer() Nous allons donc y jeter un coup d'œil :

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

Et voici notre explication : L'adresse de l'atomique est utilisée pour générer une clé de hachage afin de sélectionner un verrou pré-alocé.

Answer 3

Extrait de l'article 29.5.9 de la norme C++ :

Note : La représentation d'une spécialisation atomique ne doit pas nécessairement avoir la même taille que le type d'argument correspondant. Les spécialisations devraient avoir la même taille chaque fois que cela est possible, car cela réduit l'effort requis pour porter le code existant. - note de fin

Il est préférable de faire en sorte que la taille d'un atomique soit la même que celle de son type d'argument, bien que cela ne soit pas nécessaire. Le moyen d'y parvenir est soit d'éviter les verrous, soit de stocker les verrous dans une structure séparée. Comme les autres réponses l'ont déjà expliqué clairement, une table de hachage est utilisée pour contenir tous les verrous. C'est le moyen le plus efficace en termes de mémoire pour stocker un nombre quelconque de verrous pour tous les objets atomiques utilisés.