Comment réaliser une barrière StoreLoad en C ++ 11?

Je veux écrire du code portable (Intel, ARM, PowerPC ...) qui résout une variante d'un problème classique:

Initially: X=Y=0

Thread A:
  X=1
  if(!Y){ do something }
Thread B:
  Y=1
  if(!X){ do something }

dans lequel l'objectif est d'éviter une situation dans laquelle les deux threads fontsomething . (Ce n'est pas grave si rien ne fonctionne; ce n'est pas un mécanisme à exécution unique.) Veuillez me corriger si vous voyez des défauts dans mon raisonnement ci-dessous.

Je suis conscient que je peux atteindre le but avec memory_order_seq_cstles stores atomiques et les loads comme suit:

std::atomic<int> x{0},y{0};
void thread_a(){
  x.store(1);
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!x.load()) bar();
}

qui atteint l'objectif, car il doit y avoir un seul ordre total sur les
{x.store(1), y.store(1), y.load(), x.load()}événements, qui doit correspondre à l'ordre des programmes "bords":

• x.store(1) "dans TO c'est avant" y.load()
• y.store(1) "dans TO c'est avant" x.load()

et si a foo()été appelé, alors nous avons un avantage supplémentaire:

• y.load() "lit la valeur avant" y.store(1)

et si a bar()été appelé, alors nous avons un avantage supplémentaire:

• x.load() "lit la valeur avant" x.store(1)

et tous ces bords combinés ensemble formeraient un cycle:

x.store(1)"dans TO est avant" y.load()"lit la valeur avant" y.store(1)"dans TO est avant" x.load()"lit la valeur avant"x.store(true)

ce qui viole le fait que les commandes n'ont pas de cycles.

J'utilise intentionnellement des termes non standard "dans TO est avant" et "lit la valeur avant" par opposition aux termes standard comme happens-before, parce que je veux solliciter des commentaires sur l'exactitude de mon hypothèse selon laquelle ces bords impliquent effectivement une happens-beforerelation, peuvent être combinés ensemble en un seul graphique, et le cycle dans un tel graphique combiné est interdit. Je ne suis pas sûre à propos de ça. Ce que je sais, c'est que ce code produit des barrières correctes sur Intel gcc & clang et sur ARM gcc

Maintenant, mon vrai problème est un peu plus compliqué, car je n'ai aucun contrôle sur "X" - il est caché derrière certaines macros, modèles, etc. et pourrait être plus faible que seq_cst

Je ne sais même pas si "X" est une variable unique, ou un autre concept (par exemple un sémaphore léger ou un mutex). Tout ce que je sais, c'est que j'ai deux macros set()et check()que cela check()retourne true"après" qu'un autre thread ait appelé set(). (Il est également connu que setet checksont thread-safe et ne peuvent pas créer UB course de données.)

Donc, conceptuellement, set()c'est un peu comme "X = 1" et check()c'est comme "X", mais je n'ai aucun accès direct aux atomiques impliqués, le cas échéant.

void thread_a(){
  set();
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!check()) bar();
}

Je suis inquiet, cela set()pourrait être implémenté en interne comme x.store(1,std::memory_order_release)et / ou check()pourrait l'être x.load(std::memory_order_acquire). Ou hypothétiquement std::mutex, un thread se déverrouille et un autre est try_locking; dans la norme ISO std::mutexest uniquement garanti d'avoir acquis et validé l'ordre, pas seq_cst.

Si tel est le cas, alors check()si le corps peut être "réorganisé" avant y.store(true)( voir la réponse d'Alex où ils démontrent que cela se produit sur PowerPC ).
Ce serait vraiment mauvais, car maintenant cette séquence d'événements est possible:

• thread_b()charge d'abord l'ancienne valeur de x( 0)
• thread_a() exécute tout, y compris foo()
• thread_b() exécute tout, y compris bar()

Donc, les deux foo()et bar()j'ai été appelé, ce que j'ai dû éviter. Quelles sont mes options pour empêcher cela?

Option A

Essayez de forcer la barrière Store-Load. En pratique, cela peut être réalisé par std::atomic_thread_fence(std::memory_order_seq_cst);- comme l'explique Alex dans une réponse différente, tous les compilateurs testés ont émis une clôture complète:

• x86_64: MFENCE
• PowerPC: hwsync
• Itanuim: mf
• ARMv7 / ARMv8: dmb ish
• MIPS64: synchronisation

Le problème avec cette approche est que je ne pouvais trouver aucune garantie dans les règles C ++, qui std::atomic_thread_fence(std::memory_order_seq_cst)doivent se traduire par une barrière de mémoire pleine. En fait, le concept de atomic_thread_fences en C ++ semble être à un niveau d'abstraction différent du concept d'assemblage de barrières de mémoire et traite plus de choses comme "quelle opération atomique se synchronise avec quoi". Existe-t-il une preuve théorique que la mise en œuvre ci-dessous atteint l'objectif?

void thread_a(){
  set();
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!y.load()) foo();
}
void thread_b(){
  y.store(true);
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!check()) bar();
}

Option B

Utilisez le contrôle que nous avons sur Y pour réaliser la synchronisation, en utilisant les opérations lecture-modification-écriture memory_order_acq_rel sur Y:

void thread_a(){
  set();
  if(!y.fetch_add(0,std::memory_order_acq_rel)) foo();
}
void thread_b(){
  y.exchange(1,std::memory_order_acq_rel);
  if(!check()) bar();
}

L'idée ici est que l'accès à un seul atomic ( y) doit être formé d'un seul ordre sur lequel tous les observateurs s'accordent, donc fetch_addc'est avant exchangeou vice-versa.

Si fetch_addc'est avant, exchangealors la partie "libération" de se fetch_addsynchronise avec la partie "acquisition" de exchangeet donc tous les effets secondaires de set()doivent être visibles pour l'exécution du code check(), donc bar()ne seront pas appelés.

Sinon, exchangec'est avant fetch_add, alors le fetch_addverra 1et n'appellera pas foo(). Il est donc impossible d'appeler les deux foo()et bar(). Ce raisonnement est-il correct?

Option C

Utilisez atomique factice, pour introduire des «bords» qui empêchent le désastre. Envisagez l'approche suivante:

void thread_a(){
  std::atomic<int> dummy1{};
  set();
  dummy1.store(13);
  if(!y.load()) foo();
}
void thread_b(){
  std::atomic<int> dummy2{};
  y.store(1);
  dummy2.load();
  if(!check()) bar();
}

Si vous pensez que le problème est que les atomics sont locaux, alors imaginez les déplacer à l'échelle mondiale, dans le raisonnement suivant, cela ne semble pas avoir d'importance pour moi, et j'ai intentionnellement écrit le code de manière à exposer à quel point c'est drôle ce mannequin1 et dummy2 sont complètement séparés.

Pourquoi diable cela pourrait-il fonctionner? Eh bien, il doit y avoir un seul ordre total {dummy1.store(13), y.load(), y.store(1), dummy2.load()}qui doit être cohérent avec l'ordre des programmes "bords":

• dummy1.store(13) "dans TO c'est avant" y.load()
• y.store(1) "dans TO c'est avant" dummy2.load()

(Un magasin + chargement seq_cst forme, espérons-le, l'équivalent C ++ d'une barrière de mémoire complète, y compris StoreLoad, comme ils le font dans asm sur de véritables ISA, y compris même AArch64 où aucune instruction de barrière distincte n'est requise.)

Maintenant, nous avons deux cas à considérer: soit y.store(1)avant y.load()soit après dans l'ordre total.

Si y.store(1)c'est avant y.load()alors foo()ne sera pas appelé et nous sommes en sécurité.

Si y.load()est avant y.store(1), puis en le combinant avec les deux arêtes que nous avons déjà dans l'ordre du programme, nous déduisons que:

• dummy1.store(13) "dans TO c'est avant" dummy2.load()

Maintenant, dummy1.store(13)c'est une opération de libération, qui libère les effets de set(), et dummy2.load()est une opération d'acquisition, donc check()devrait voir les effets de set()et bar()ne sera donc pas appelée et nous sommes en sécurité.

Est-il correct de penser que check()cela verra les résultats de set()? Puis-je combiner les "bords" de différents types ("ordre du programme" aka Sequenced Before, "ordre total", "avant la sortie", "après l'acquisition") comme ça? J'ai de sérieux doutes à ce sujet: les règles C ++ semblent parler de relations "synchronise avec" entre le magasin et la charge au même endroit - ici, il n'y a pas une telle situation.

Notez que nous ne nous inquiétons que du cas où il dumm1.storeest connu (via un autre raisonnement) d'être avant dummy2.loaddans l'ordre total seq_cst. Donc, s'ils avaient accédé à la même variable, la charge aurait vu la valeur stockée et se serait synchronisée avec elle.

(Le raisonnement barrière / réorganisation de la mémoire pour les implémentations où les charges atomiques et les magasins se compilent vers au moins des barrières mémoire à 1 voie (et les opérations seq_cst ne peuvent pas réorganiser: par exemple, un magasin seq_cst ne peut pas passer une charge seq_cst) est que toutes les charges / les magasins après dummy2.loaddeviennent définitivement visibles pour les autres threads après y.store . Et de même pour l'autre thread, ... avant y.load.)

Vous pouvez jouer avec ma mise en œuvre des options A, B, C sur https://godbolt.org/z/u3dTa8

Les options A et B sont des solutions valides.

• Option A: peu importe ce que signifie une clôture seq-cst, la norme C ++ définit clairement les garanties qu'elle fournit. Je les ai présentées dans cet article: Quand une clôture memory_order_seq_cst est-elle utile?
• Option B: oui, votre raisonnement est correct. Toutes les modifications sur un objet ont un seul ordre total (l'ordre de modification), vous pouvez donc l'utiliser pour synchroniser les threads et assurer la visibilité de tous les effets secondaires.

Cependant, l'option C n'est pas valide! Une relation de synchronisation avec ne peut être établie que par des opérations d'acquisition / libération sur le même objet . Dans votre cas, vous avez deux objets complètement différents et indépendants dummy1et dummy2. Mais ceux-ci ne peuvent pas être utilisés pour établir une relation qui se produit avant. En fait, comme les variables atomiques sont purement locales (c'est-à-dire qu'elles ne sont jamais touchées que par un seul thread), le compilateur est libre de les supprimer en fonction de la règle de simulation .

Mise à jour

Option A:
je suppose set()et check()opère sur une valeur atomique. Ensuite, nous avons la situation suivante (-> indique séquencé avant ):

• set()-> fence1(seq_cst)->y.load()
• y.store(true)-> fence2(seq_cst)->check()

Nous pouvons donc appliquer la règle suivante:

Pour les opérations atomiques A et B sur un objet atomique M , où A modifie M et B prend sa valeur, s'il y a des memory_order_seq_cstclôtures X et Y telles que A est séquencé avant X , Y est séquencé avant B et X précède Y dans S , alors B observe soit les effets de A soit une modification ultérieure de M dans son ordre de modification.

C'est-à-dire, soit check()voit cette valeur stockée dans set, ou y.load()voit la valeur écrite être y.store()(les opérations sur ypeuvent même utiliser memory_order_relaxed).

Option C:
Le C ++ 17 standards Etats [32.4.3, P1347]:

Il doit y avoir un seul ordre total S sur toutes les memory_order_seq_cstopérations, conformément à l'ordre «avant» et aux ordres de modification pour tous les emplacements concernés [...]

Le mot important ici est "cohérent". Cela implique que si une opération A arrive, avant une opération B , puis A doit précéder B en S . Cependant, l' implication logique est un sens unique rue, donc nous ne pouvons en déduire l'inverse: juste parce que certaines opérations C précède une opération D en S ne signifie pas que C se produit avant D .

En particulier, deux opérations seq-cst sur deux objets séparés ne peuvent pas être utilisées pour établir une relation se produit avant, même si les opérations sont totalement ordonnées en S. Si vous voulez ordonner des opérations sur des objets séparés, vous devez vous référer à seq-cst -des clôtures (voir Option A).

Dans le premier exemple, la y.load()lecture de 0 n'implique pas que y.load()cela se produit avant y.store(1).

Cela implique cependant qu'il est plus tôt dans l'ordre total unique grâce à la règle qu'une charge seq_cst renvoie soit la valeur du dernier magasin seq_cst dans l'ordre total, soit la valeur d'un magasin non seq_cst qui ne se produit pas avant il (qui dans ce cas n'existe pas). Donc, si y.store(1)c'était plus tôt que y.load()dans la commande totale, y.load()serait retourné 1.

La preuve est toujours correcte car la commande totale unique n'a pas de cycle.

Et cette solution?

std::atomic<int> x2{0},y{0};

void thread_a(){
  set();
  x2.store(1);
  if(!y.load()) foo();
}

void thread_b(){
  y.store(1);
  if(!x2.load()) bar();
}

@mpoeter a expliqué pourquoi les options A et B sont sûres.

Dans la pratique sur les implémentations réelles, je pense que l'option A n'a besoin que std::atomic_thread_fence(std::memory_order_seq_cst)du fil A, pas de B.

Les magasins seq-cst incluent en pratique une barrière de mémoire complète, ou sur AArch64, au moins ne peuvent pas réorganiser avec des charges ultérieures d'acquisition ou seq_cst (la stlrlibération séquentielle doit s'écouler du tampon de stockage avant de ldarpouvoir lire dans le cache).

Les mappages C ++ -> asm ont le choix de mettre le coût de la vidange du tampon de stockage sur les magasins atomiques ou les charges atomiques. Le choix judicieux pour les implémentations réelles est de rendre les charges atomiques bon marché, donc les magasins seq_cst incluent une barrière complète (y compris StoreLoad). Alors que les charges seq_cst sont les mêmes que celles acquises sur la plupart.

(Mais pas POWER; il y a même des charges qui nécessitent une synchronisation lourde = une barrière complète pour arrêter le transfert en magasin à partir d'autres threads SMT sur le même noyau, ce qui pourrait entraîner une réorganisation IRIW, car seq_cst nécessite que tous les threads soient en mesure de s'accorder sur l'ordre de toutes les opérations seq_cst. Deux écritures atomiques à des emplacements différents dans des threads différents seront-elles toujours vues dans le même ordre par les autres threads? )

(Bien sûr, pour une garantie formelle de sécurité, nous avons besoin d'une clôture dans les deux pour promouvoir l'acquisition / la libération de l'ensemble () -> check () dans un seq_cst synchronise avec. Fonctionnerait également pour un ensemble détendu, je pense, mais un un contrôle détendu pourrait réorganiser avec une barre du POV d'autres threads.)

Je pense que le vrai problème avec l'option C est qu'elle dépend d'un observateur hypothétique qui pourrait se synchroniser avec yles opérations fictives. Et donc nous nous attendons à ce que le compilateur conserve cet ordre lors de la création d'ASM pour un ISA basé sur une barrière.

Cela va être vrai dans la pratique sur les vrais ISA; les deux threads incluent une barrière complète ou équivalente et les compilateurs n'optimisent pas (encore) l'atomique. Mais bien sûr, «la compilation vers une norme ISA basée sur les barrières» ne fait pas partie de la norme ISO C ++. Le cache partagé cohérent est l'observateur hypothétique qui existe pour le raisonnement asm mais pas pour le raisonnement ISO C ++.

Pour que l'option C fonctionne, nous avons besoin d'un ordre comme dummy1.store(13);/ y.load()/ set();(tel que vu par le thread B) pour violer certaines règles ISO C ++ .

Le thread exécutant ces instructions doit se comporter comme s'il était set() exécuté en premier (à cause de Sequenced Before). C'est bien, l'ordre de la mémoire au moment de l'exécution et / ou la réorganisation du temps de compilation des opérations pourraient toujours le faire.

Les deux opérations seq_cst d1=13et ysont cohérentes avec la séquence avant (ordre du programme). set()ne participe pas à l'ordre global requis pour les opérations seq_cst car ce n'est pas seq_cst.

Le thread B ne se synchronise pas avec dummy1.store donc aucunesetd1=13 occurrence ne se produit avant l'exigence relative à s'applique , même si cette affectation est une opération de libération.

Je ne vois aucune autre violation possible des règles; Je ne trouve rien ici qui soit nécessaire pour être cohérent avec le setséquencé avant d1=13.

Le raisonnement "dummy1.store releases set ()" est la faille. Cet ordre ne s'applique qu'à un véritable observateur qui se synchronise avec lui, ou en asm. Comme @mpoeter a répondu, l'existence de l'ordre total seq_cst ne crée pas ou n'implique pas de relations qui se produisent avant, et c'est la seule chose qui garantit formellement l'ordre en dehors de seq_cst.

Tout type de CPU "normal" avec un cache partagé cohérent où ce réarrangement pourrait vraiment se produire au moment de l'exécution ne semble pas plausible. (Mais si un compilateur pourrait retirer dummy1et dummy2il est clair que nous aurions un problème, et je pense que cela soit autorisé par la norme.)

Mais comme le modèle de mémoire C ++ n'est pas défini en termes de tampon de stockage, de cache cohérent partagé ou de tests décisifs de réorganisation autorisée, les choses requises par la raison ne sont pas formellement requises par les règles C ++. C'est peut-être intentionnel pour permettre d'optimiser même les variables seq_cst qui s'avèrent être des threads privés. (Les compilateurs actuels ne font pas cela, bien sûr, ni aucune autre optimisation des objets atomiques.)

Une implémentation où un thread pouvait vraiment voir le set()dernier tandis qu'un autre pouvait voir les set()premiers sons invraisemblables. Même POWER ne pouvait pas faire ça; la charge et le stockage seq_cst incluent des barrières complètes pour POWER. (J'avais suggéré dans les commentaires que la réorganisation IRIW pourrait être pertinente ici; les règles acq / rel de C ++ sont suffisamment faibles pour s'adapter à cela, mais le manque total de garanties en dehors des synchronisations avec ou dans d'autres situations avant que les situations ne soient beaucoup plus faibles que n'importe quel HW. )

C ++ ne garantit rien pour non seq_cst à moins qu'il en fait est un observateur, et seulement pour cet observateur. Sans un, nous sommes sur le territoire des chats de Schroedinger. Ou, si deux arbres tombent dans la forêt, l'un est-il tombé avant l'autre? (S'il s'agit d'une grande forêt, la relativité générale dit qu'elle dépend de l'observateur et qu'il n'y a pas de concept universel de simultanéité.)

@mpoeter a suggéré qu'un compilateur pourrait même supprimer les opérations de chargement et de stockage factices, même sur les objets seq_cst.

Je pense que cela peut être correct lorsqu'ils peuvent prouver que rien ne peut se synchroniser avec une opération. Par exemple, un compilateur qui peut voir que dummy2la fonction n'échappe pas peut probablement supprimer cette charge seq_cst.

Cela a au moins une conséquence réelle: si la compilation pour AArch64, cela permettrait à un magasin seq_cst antérieur de se réorganiser dans la pratique avec des opérations plus détendues plus tard, ce qui n'aurait pas été possible avec un magasin seq_cst + charge drainant le tampon de magasin avant tout des chargements ultérieurs pourraient s'exécuter.

Bien sûr, les compilateurs actuels n'optimisent pas du tout l'atomique, même si ISO C ++ ne l'interdit pas; c'est un problème non résolu pour le comité des normes.

Cela est autorisé, je pense, car le modèle de mémoire C ++ n'a pas d'observateur implicite ou d'exigence que tous les threads s'accordent sur la commande. Il fournit certaines garanties basées sur des caches cohérents, mais il ne nécessite pas de visibilité simultanée sur tous les threads.

dans la norme ISO, std :: mutex est uniquement garanti d'avoir un ordre d'acquisition et de libération, pas seq_cst.

Mais rien n'est garanti d'avoir un "ordre seq_cst", car ce seq_cstn'est la propriété d'aucune opération.

seq_cstest une garantie sur toutes les opérations d'une implémentation donnée std::atomicou d'une classe atomique alternative. En tant que tel, votre question n'est pas valable.