x86 equivalente para LWARX y STWCX

Question

Estoy buscando un equivalente de LWARX y STWCX (como se encuentra en los procesadores PowerPC) o una forma de implementar una funcionalidad similar en la plataforma x86. Además, ¿dónde sería el mejor lugar para averiguar sobre tales cosas (es decir, buenos artículos/sitios web/foros para la programación de bloqueo/espera).

---

Editar
Creo que podría necesitar dar más detalles a medida que se supone que sólo estoy en busca de un CAS (comparar y swap) operación. Lo que intento hacer es implementar un sistema de conteo de referencias sin candado con punteros inteligentes a los que se pueda acceder y cambiar por medio de varios hilos. Básicamente necesito una forma de implementar la siguiente función en un procesador x86.

int* IncrementAndRetrieve(int **ptr) 
{ 
    int val; 
    int *pval; 
    do 
    { 
    // fetch the pointer to the value 
    pval = *ptr; 

    // if its NULL, then just return NULL, the smart pointer 
    // will then become NULL as well 
    if(pval == NULL) 
     return NULL; 

    // Grab the reference count 
    val = lwarx(pval); 

    // make sure the pointer we grabbed the value from 
    // is still the same one referred to by 'ptr' 
    if(pval != *ptr) 
     continue; 

    // Increment the reference count via 'stwcx' if any other threads 
    // have done anything that could potentially break then it should 
    // fail and try again 
    } while(!stwcx(pval, val + 1)); 
    return pval; 
} 

Realmente necesito algo que imita LWARX y STWCX con bastante precisión para sacar esto adelante (no puedo encontrar una manera de hacer esto con el CompareExchange, intercambio o añadir funciones que he encontrado hasta ahora para el x86).

Gracias

Answer 1

Como mencionó Michael, lo que probablemente esté buscando es la instrucción cmpxchg.

Es importante señalar que el método de PPC para lograr esto se conoce como Load Link/Store Conditional (LL/SC), mientras que la arquitectura x86 usa Compare And Swap (CAS). LL/SC tiene una semántica más fuerte que CAS en el sentido de que cualquier cambio en el valor en la dirección condicionada hará que la tienda falle, incluso si el otro cambio reemplaza el valor con el mismo valor con el que la carga estuvo condicionada. CAS, por otro lado, tendría éxito en este caso. Esto se conoce como el problema ABA (ver el enlace CAS para más información).

Si necesita la semántica más fuertes en la arquitectura x86, se puede aproximar mediante el uso de la instrucción cmpxchg8b o cmpxchg16b bajo x86_64 de doble ancho x86s de comparación y de intercambio (DWCAS). Esto le permite intercambiar atómicamente dos palabras consecutivas de "tamaño natural" a la vez, en lugar de solo la habitual. La idea básica es que una de las dos palabras contiene el valor de interés, y la otra contiene un "recuento de mutaciones" siempre creciente. Aunque técnicamente esto no elimina el problema, la probabilidad de que el contador de mutaciones se ajuste entre intentos es tan baja que es un sustituto razonable para la mayoría de los propósitos.

Answer 2

x86 no admite directamente la "concurrencia optimista" al igual que lo hace el PPC - más bien, el apoyo de x86 para la concurrencia se basa en un "prefijo de bloqueo", véase here. (Algunas de las instrucciones llamadas "atómicas" como XCHG realmente obtienen su atomicidad al afirmar intrínsecamente el prefijo LOCK, ya sea que el programador de código ensamblador lo haya codificado o no). No es exactamente "a prueba de bombas", para decirlo diplomáticamente (de hecho, es bastante propenso a los accidentes, diría ;-).

Answer 3

Probablemente esté buscando la familia de instrucciones cmpxchg.

Deberá precederlos con una instrucción de bloqueo para obtener un comportamiento equivalente.

Eche un vistazo a here para tener una idea general de lo que está disponible.

es probable que termina con algo similar a esto:

mov ecx,dword ptr [esp+4] 
mov edx,dword ptr [esp+8] 
mov eax,dword ptr [esp+12] 
lock cmpxchg dword ptr [ecx],edx 
ret 12 

usted debe leer this paper ...

Editar

En respuesta a la pregunta actualizada, ¿está usted buscando hacer algo como el Boost shared_ptr? Si es así, eche un vistazo a ese código y a los archivos en ese directorio; definitivamente lo ayudarán a comenzar.

Answer 4

Lo que estás tratando de hacer no funcionará de la manera que esperas. Lo que implementó anteriormente se puede hacer con la función InterlockedIncrement (función Win32, ensamblaje: XADD).

El motivo por el cual su código no hace lo que cree que es que otro subproceso aún puede cambiar el valor entre la segunda lectura de * ptr y stwcx sin invalidar el stwcx.

Answer 5

si tiene 64 bits y se limita a decir 1 tb de pila, puede empaquetar el contador en los 24 bits superiores no utilizados. si tiene punteros alineados con palabras, los 5 bits inferiores también están disponibles.

int* IncrementAndRetrieve(int **ptr) 
{ 
    int val; 
    int *unpacked; 
    do 
    { 
    val = *ptr; 
    unpacked = unpack(val); 

    if(unpacked == NULL) 
     return NULL; 
    // pointer is on the bottom 
    } while(!cas(unpacked, val, val + 1)); 
    return unpacked; 
} 

Answer 6

No sé si LWARX y STWCX invalidan toda la línea de caché, CAS y DCAS do. Lo que significa que, a menos que esté dispuesto a tirar mucha memoria (64 bytes por cada puntero "bloqueable" independiente), no verá mucha mejoría si realmente está presionando el software para que esté estresado. Los mejores resultados que he visto hasta ahora fueron cuando las personas deliberadamente castigaron 64b, planificaron sus estructuras (empaquetando cosas que no estarían contenidas), mantuvieron todo alineado en los límites 64b y usaron barreras explícitas de lectura y escritura de datos. La invalidación de la línea de caché puede costar aproximadamente de 20 a 100 ciclos, por lo que es un problema de rendimiento real más grande que el bloqueo de evasión.

Además, tendría que planear una estrategia de asignación de memoria diferente para administrar fugas controladas (si puede dividir el código en "proceso de solicitud" lógico - una solicitud "pierde" y libera todo su volumen de memoria al final) o administración de asignación de datos para que una estructura bajo contención nunca reciba memoria generada por elementos de la misma estructura/colección (para evitar ABA). Algo de eso puede ser muy contrario a la intuición, pero es eso o pagar el precio de GC.