Pourquoi __sync_add_and_fetch fonctionne-t-il pour une variable 64 bits sur un système 32 bits?

Question

Examinez le code condensé suivant:

/* Compile: gcc -pthread -m32 -ansi x.c */ 
#include <stdio.h> 
#include <inttypes.h> 
#include <pthread.h> 

static volatile uint64_t v = 0; 

void *func (void *x) { 
    __sync_add_and_fetch (&v, 1); 
    return x; 
} 

int main (void) { 
    pthread_t t; 
    pthread_create (&t, NULL, func, NULL); 
    pthread_join (t, NULL); 
    printf ("v = %"PRIu64"\n", v); 
    return 0; 
} 

J'ai une variable uint64_t que je veux incrémenter atomiquement, car la variable est un compteur dans un programme multi-thread. Pour atteindre l'atomicité, j'utilise les codes atomic builtins de GCC.

Si je compile pour un système amd64 (-m64), le code assembleur produit est facile à comprendre. En utilisant un lock addq, le processeur garantit que l'incrément sera atomique.

400660:  f0 48 83 05 d7 09 20 lock addq $0x1,0x2009d7(%rip) 

Mais le même code C produit un code ASM très compliqué sur un système ia32 (-m32):

804855a:  a1 28 a0 04 08   mov 0x804a028,%eax 
804855f:  8b 15 2c a0 04 08  mov 0x804a02c,%edx 
8048565:  89 c1     mov %eax,%ecx 
8048567:  89 d3     mov %edx,%ebx 
8048569:  83 c1 01    add $0x1,%ecx 
804856c:  83 d3 00    adc $0x0,%ebx 
804856f:  89 ce     mov %ecx,%esi 
8048571:  89 d9     mov %ebx,%ecx 
8048573:  89 f3     mov %esi,%ebx 
8048575:  f0 0f c7 0d 28 a0 04 lock cmpxchg8b 0x804a028 
804857c:  08 
804857d:  75 e6     jne 8048565 <func+0x15> 

Voici ce que je ne comprends pas:

• lock cmpxchg8b garantit que la variable modifiée n'est écrite que si la valeur attendue réside toujours dans l'adresse cible. Le compare-and-swap est garanti pour arriver atomiquement.
• Mais ce qui garantit que la lecture de la variable dans 0x804855a et 0x804855f être atomique?

Probablement qu'il n'a pas d'importance s'il y avait une « lecture sale », mais quelqu'un pourrait s'il vous plaît décrire une courte preuve qu'il n'y a pas de problème? En outre: Pourquoi le code généré revient-il à 0x8048565 et non 0x804855a? Je suis certain que cela n'est correct que si d'autres auteurs, eux aussi, incrémentent la variable. Est-ce une exigence implicite pour la fonction __sync_add_and_fetch?

Answer 1

La lecture est garantie atomique parce qu'elle est correctement aligné (et il tient sur une ligne de cache) et parce que Intel a fait la spécification de cette façon, voir le manuel architecture Intel Vol 1, 4.4.1:

Un opérande de mot ou de double mot qui traverse une limite de 4 octets ou un opérande de quadribord qui dépasse une limite de 8 octets est considéré comme non aligné et nécessite deux cycles de bus mémoire séparés pour l'accès.

Vol 3A 8.1.1:

Les (processeurs et nouveaux depuis) ​​processeur Pentium garantit que les suivantes opérations de mémoire supplémentaires seront toujours effectués atomiquement:

• lire ou écrire un quadword aligné sur un 64 bits limite

• accès à 16 bits à des emplacements de mémoire non mises en cache qui correspondent à dans un bus de données 32-bit

Les processeurs de la famille P6 (et les nouveaux processeurs depuis) ​​garantissent que le fonctionnement de la mémoire supplémentaire suivante sera toujours effectuée atomiquement:

• Unaligned 16-, 32-, et 64 bits accès à la mémoire cache qui correspondent à une ligne de cache

Ainsi, en étant aligné, il peut être lu en 1 cycle, et il s'intègre dans une ligne de cache rendant l'atome de lecture.

Le code saute à 0x8048565 parce que les pointeurs ont déjà chargé, il n'y a pas besoin de les charger à nouveau, comme CMPXCHG8B sera mis EAX:EDX à la valeur de la destination si elle échoue:

CMPXCHG8B Description pour la Intel ISA manuel Vol. 2A:

Comparer EDX: EAX avec m64. Si ce paramètre est égal, définissez ZF et chargez ECX: EBX dans m64. Sinon, effacez ZF et chargez m64 dans EDX: EAX.

Ainsi, le code n'a besoin que d'incrémenter la nouvelle valeur retournée et de réessayer. Si nous faisons cela de celui-ci dans le code C, il devient plus facile:

value = dest; 
While(!CAS8B(&dest,value,value + 1)) 
{ 
    value = dest; 
} 

Answer 2

La lecture de la variable dans 0x804855a et 0x804855f n'a pas besoin d'être atomique. Utilisation de l'instruction de comparaison et-swap pour incrémenter se présente comme suit dans pseudocode:

oldValue = *dest; 
do { 
    newValue = oldValue+1; 
} while (!compare_and_swap(dest, &oldValue, newValue)); 

Depuis la comparaison et-swap vérifie que *dest == oldValue avant d'échanger, il agira à titre de garantie - de sorte que si la valeur oldValue est incorrect, la boucle sera essayée à nouveau, donc il n'y a pas de problème si la lecture non-atomique a abouti à une valeur incorrecte.

Votre deuxième question était pourquoi la ligne oldValue = *dest n'est pas à l'intérieur de la boucle. En effet, la fonction compare_and_swap remplace toujours la valeur oldValue par la valeur réelle *dest. Donc, il va essentiellement effectuer la ligne oldValue = *dest pour vous, et il ne sert à rien de le faire à nouveau. Dans le cas de l'instruction cmpxchg8b, il mettra le contenu de l'opérande de mémoire dans edx:eax lorsque la comparaison échoue.

Le pseudo-code pour compare_and_swap est:

bool compare_and_swap (int *dest, int *oldVal, int newVal) 
{ 
    do atomically { 
    if (*oldVal == *dest) { 
     *dest = newVal; 
     return true; 
    } else { 
     *oldVal = *dest; 
     return false; 
    } 
    } 
} 

Par ailleurs, dans votre code vous devez vous assurer que v est aligné à 64 bits - sinon il pourrait être divisé entre deux lignes de cache et l'instruction cmpxchg8b sera ne pas être effectué atomiquement. Vous pouvez utiliser les codes __attribute__((aligned(8))) de GCC pour cela.