¿Por qué __sync_add_and_fetch funciona para una variable de 64 bits en un sistema de 32 bits?

Question

Considere el siguiente código condensada:

/* 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; 
} 

que tienen una variable uint64_t que quiero para incrementar de forma atómica, ya que la variable es un contador en un programa multi-hilo. Para lograr la atomicidad uso GCC's atomic builtins.

Si compilo para un sistema amd64 (-m64) el código ensamblador producido es fácil de entender. Al usar un lock addq, el procesador garantiza que el incremento sea atómico.

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

Pero el mismo código C produce un código muy complicado ASM en un sistema 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> 

Esto es lo que no entiendo:

• lock cmpxchg8bgarantiza que la variable modificada solo se escribe si el valor esperado aún reside en la dirección de destino. El comparar y el intercambio está garantizado que ocurrirá atómicamente.
• Pero ¿qué garantiza que la lectura de la variable en 0x804855a y 0x804855f sea atómica?

Probablemente no importa si había una "lectura sucia", pero podría alguien por favor esbozar una breve prueba de que no hay problema?

Además: ¿Por qué el código generado vuelve a saltar a 0x8048565 y no a 0x804855a? Estoy seguro de que esto solo es correcto si otros escritores también incrementan la variable. ¿Es este un requisito implícito para la función __sync_add_and_fetch?

Answer 1

La lectura se garantiza que sea atómica debido a que está alineado correctamente (y que encaja en una línea de caché) y debido a que Intel hizo la especificación de esta manera, ver el manual de arquitectura Intel Vol 1, 4.4.1:

Un operando de palabra o palabra doble que cruza un límite de 4 bytes o un operando de cuatro palabras que cruza un límite de 8 bytes se considera desalineado y requiere dos ciclos de bus de memoria separados para el acceso.

Vol 3A 8.1.1:

El procesador Pentium (y procesadores más nuevos desde) garantiza que siempre se realizarán las siguientes operaciones de memoria adicionales a cabo atómicamente:

• Leer o escribir una palabra cuádruple alineados en un 64 bits límite

• 16 bits tiene acceso a posiciones de memoria sin almacenar en caché que se ajustan dentro de un bus de datos de 32 bits

Los procesadores de la familia P6 (y nuevos procesadores desde entonces) garantizan que la siguiente operación adicional de memoria siempre se llevará a cabo de forma atómica:

• Unaligned 16, 32, y 64 bits accesos a la memoria caché que encaja dentro de una línea de caché

Por lo tanto, al estar alineado, se puede leer en 1 ciclo, y cabe en una línea de caché que hace que la lectura sea atómica.

El código salta de nuevo a 0x8048565 porque los punteros ya se pueden cargar, no hay necesidad de cargarlos de nuevo, como CMPXCHG8B establecerá EAX:EDX al valor en el destino, si se produce un error:

CMPXCHG8B Descripción de la Intel ISA manual Vol. 2A:

Comparar EDX: EAX con m64. Si es igual, configure ZF y cargue ECX: EBX en m64. De lo contrario, borre ZF y cargue m64 en EDX: EAX.

Por lo tanto, el código solo necesita incrementar el valor recién devuelto e intentar nuevamente. Si esto de la misma en el código C se hace más fácil:

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

Answer 2

La lectura de la variable en 0x804855a y 0x804855f no tiene que ser atómicas. El uso de la instrucción y de intercambio en comparación a incrementar es la siguiente con pseudocódigo:

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

Dado que la comparación y de intercambio comprueba que *dest == oldValue antes de intercambiar, actuará como salvaguarda - por lo que si el valor de oldValue es incorrecto, el ciclo se intentará de nuevo, por lo que no hay problema si la lectura no atómica dio como resultado un valor incorrecto.

Su segunda pregunta fue por qué la línea oldValue = *dest no está dentro del lazo. Esto se debe a que la función compare_and_swap siempre reemplazará el valor de oldValue con el valor real de *dest. Por lo tanto, esencialmente realizará la línea oldValue = *dest para usted, y no tiene sentido volver a hacerlo. En el caso de la instrucción cmpxchg8b, pondrá el contenido del operando de memoria en edx:eax cuando la comparación falla.

El pseudocódigo para compare_and_swap es:

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

Por cierto, en su código que necesita para asegurarse de que v está alineado a 64 bits - de lo contrario podría dividirse entre dos líneas de caché y la instrucción cmpxchg8b se no se realizará atómicamente. Puede usar GCC's __attribute__((aligned(8))) para esto.