C11 Atomic Acquire / Release et x86_64 manque de cohérence chargement / stockage?

10

Je me bats avec la section 5.1.2.4 de la norme C11, en particulier la sémantique de Release / Acquire. Je note que https://preshing.com/20120913/acquire-and-release-semantics/ (entre autres) déclare que:

... La sémantique de libération empêche la réorganisation de la mémoire de la libération en écriture avec toute opération de lecture ou d'écriture qui la précède dans l'ordre du programme.

Donc, pour ce qui suit:

typedef struct test_struct
{
  _Atomic(bool) ready ;
  int  v1 ;
  int  v2 ;
} test_struct_t ;

extern void
test_init(test_struct_t* ts, int v1, int v2)
{
  ts->v1 = v1 ;
  ts->v2 = v2 ;
  atomic_store_explicit(&ts->ready, false, memory_order_release) ;
}

extern int
test_thread_1(test_struct_t* ts, int v2)
{
  int v1 ;
  while (atomic_load_explicit(&ts->ready, memory_order_acquire)) ;
  ts->v2 = v2 ;       // expect read to happen before store/release 
  v1     = ts->v1 ;   // expect write to happen before store/release 
  atomic_store_explicit(&ts->ready, true, memory_order_release) ;
  return v1 ;
}

extern int
test_thread_2(test_struct_t* ts, int v1)
{
  int v2 ;
  while (!atomic_load_explicit(&ts->ready, memory_order_acquire)) ;
  ts->v1 = v1 ;
  v2     = ts->v2 ;   // expect write to happen after store/release in thread "1"
  atomic_store_explicit(&ts->ready, false, memory_order_release) ;
  return v2 ;
}

où ceux-ci sont exécutés:

>   in the "main" thread:  test_struct_t ts ;
>                          test_init(&ts, 1, 2) ;
>                          start thread "2" which does: r2 = test_thread_2(&ts, 3) ;
>                          start thread "1" which does: r1 = test_thread_1(&ts, 4) ;

Je m'attends donc à ce que le thread "1" ait r1 == 1 et le thread "2" à r2 = 4.

Je m'attendrais à cela parce que (après les paragraphes 16 et 18 de la section 5.1.2.4):

  • toutes les lectures et écritures (non atomiques) sont "séquencées avant" et donc "se produisent avant" l'écriture / libération atomique dans le thread "1",
  • qui "inter-thread-se produit-avant" la lecture / acquisition atomique dans le thread "2" (quand il lit "vrai"),
  • qui à son tour est "séquencé avant" et donc "se produit avant" le (non atomique) lit et écrit (dans le thread "2").

Cependant, il est tout à fait possible que je n'ai pas compris la norme.

J'observe que le code généré pour x86_64 comprend:

test_thread_1:
  movzbl (%rdi),%eax      -- atomic_load_explicit(&ts->ready, memory_order_acquire)
  test   $0x1,%al
  jne    <test_thread_1>  -- while is true
  mov    %esi,0x8(%rdi)   -- (W1) ts->v2 = v2
  mov    0x4(%rdi),%eax   -- (R1) v1     = ts->v1
  movb   $0x1,(%rdi)      -- (X1) atomic_store_explicit(&ts->ready, true, memory_order_release)
  retq   

test_thread_2:
  movzbl (%rdi),%eax      -- atomic_load_explicit(&ts->ready, memory_order_acquire)
  test   $0x1,%al
  je     <test_thread_2>  -- while is false
  mov    %esi,0x4(%rdi)   -- (W2) ts->v1 = v1
  mov    0x8(%rdi),%eax   -- (R2) v2     = ts->v2   
  movb   $0x0,(%rdi)      -- (X2) atomic_store_explicit(&ts->ready, false, memory_order_release)
  retq   

Et à condition que R1 et X1 se produisent dans cet ordre, cela donne le résultat que j'attends.

Mais ma compréhension de x86_64 est que les lectures se produisent dans l'ordre avec d'autres lectures et écritures se produisent dans l'ordre avec d'autres écritures, mais les lectures et les écritures peuvent ne pas se produire dans l'ordre les unes avec les autres. Ce qui implique qu'il est possible que X1 se produise avant R1, et même que X1, X2, W2, R1 se produisent dans cet ordre - je crois. [Cela semble désespérément improbable, mais si R1 était bloqué par certains problèmes de cache?]

S'il vous plaît: qu'est-ce que je ne comprends pas?

Je note que si je change les charges / magasins de ts->readyen memory_order_seq_cst, le code généré pour les magasins est:

  xchg   %cl,(%rdi)

ce qui est cohérent avec ma compréhension de x86_64 et donnera le résultat que j'attends.

Chris Hall
la source
5
Sur x86, tous les magasins ordinaires (non non temporels) ont une sémantique de publication. Intel® 64 et IA-32 Architectures Logicielles (3B, 3C et 3A du 3D) 3 Manuel du développeur Volume: Guide du système de programmation , 8.2.3.3 Stores Are Not Reordered With Earlier Loads. Ainsi, votre compilateur traduit correctement votre code (c'est surprenant), de sorte que votre code est effectivement complètement séquentiel et que rien d'intéressant ne se produit simultanément.
EOF
Merci ! (J'allais tranquillement bonkers.) FWIW Je recommande le lien - en particulier la section 3, le "modèle du programmeur". Mais pour éviter l'erreur dans laquelle je suis tombé, notez que dans "3.1 The Abstract Machine" il y a des "threads matériels" dont chacun est "un seul flux d'exécution d'instructions dans l'ordre " (c'est moi qui souligne). Je peux maintenant revenir à essayer de comprendre la norme C11 ... avec moins de dissonance cognitive :-)
Chris Hall

Réponses:

1

Le modèle de mémoire de x86 est essentiellement à cohérence séquentielle plus un tampon de stockage (avec transfert de stockage). Chaque magasin est donc un magasin de versions 1 . C'est pourquoi seuls les magasins seq-cst ont besoin d'instructions spéciales. ( Mappages atomiques C / C ++ 11 à asm ). En outre, https://stackoverflow.com/tags/x86/info a des liens vers des documents x86, y compris une description formelle du modèle de mémoire x86-TSO (fondamentalement illisible pour la plupart des humains; nécessite de parcourir de nombreuses définitions).

Puisque vous lisez déjà l'excellente série d'articles de Jeff Preshing, je vais vous en indiquer un autre qui va plus en détail: https://preshing.com/20120930/weak-vs-strong-memory-models/

La seule réorganisation autorisée sur x86 est StoreLoad, pas LoadStore , si nous parlons en ces termes. (Le transfert de magasin peut faire des choses très amusantes si une charge chevauche seulement partiellement un magasin; instructions de chargement globalement invisible , bien que vous n'obtiendrez jamais cela dans le code généré par le compilateur pour stdatomic.)

@EOF a commenté avec la bonne citation du manuel d'Intel:

Manuel du développeur du logiciel des architectures Intel® 64 et IA-32 Volume 3 (3A, 3B, 3C et 3D): Guide de programmation système, 8.2.3.3 Les magasins ne sont pas réorganisés avec des charges antérieures.


Note de bas de page 1: ignorer les magasins NT faiblement ordonnés; c'est pourquoi vous normalement sfenceaprès avoir fait des magasins NT. Les implémentations C11 / C ++ 11 supposent que vous n'utilisez pas les magasins NT. Si vous l'êtes, utilisez _mm_sfenceavant une opération de libération pour vous assurer qu'elle respecte vos magasins NT. (En général, n'utilisez pas _mm_mfence/ _mm_sfencedans d'autres cas ; vous n'avez généralement besoin que de bloquer la réorganisation au moment de la compilation. Ou bien sûr, utilisez simplement stdatomic.)

Peter Cordes
la source
Je trouve que le x86-TSO: un modèle de programmeur rigoureux et utilisable pour les multiprocesseurs x86 est plus lisible que la description formelle (connexe) que vous avez référencée. Mais ma véritable ambition est de bien comprendre les sections 5.1.2.4 et 7.17.3 de la norme C11 / C18. En particulier, je pense que j'obtiens Release / Acquire / Acquire + Release, mais memory_order_seq_cst est défini séparément et j'ai du mal à voir comment ils s'emboîtent tous les deux :-(
Chris Hall
@ChrisHall: J'ai trouvé que cela aidait à réaliser exactement à quel point l'acq / rel peut être faible, et pour cela, vous devez regarder des machines comme POWER qui peuvent réorganiser IRIW. (ce que seq-cst interdit mais pas acq / rel). Deux écritures atomiques à des emplacements différents dans des threads différents seront-elles toujours vues dans le même ordre par d'autres threads? . Aussi Comment réaliser une barrière StoreLoad en C ++ 11? discute de la façon dont la norme garantit formellement peu de commandes en dehors des cas de synchronisation avec ou tout ce qui est-cst.
Peter Cordes
@ChrisHall: La principale chose que seq-cst fait est de bloquer la réorganisation de StoreLoad. (Sur x86, c'est la seule chose qu'il fait au-delà de acq / rel). preshing.com/20120515/memory-reordering-caught-in-the-act utilise asm, mais c'est équivalent à seq-cst contre acq / rel
Peter Cordes