¿Puede x86 reordenar una tienda estrecha con una carga más amplia que la contiene por completo?

El Manual del desarrollador de software Intel® 64 e IA-32 Architectures dice:

8.2.3.4 Las cargas pueden reordenarse con tiendas anteriores en diferentes ubicaciones
El modelo de ordenamiento de memoria Intel-64 permite reordenar una carga con una tienda anterior a una ubicación diferente. Sin embargo, las cargas no se reordenan con las tiendas en la misma ubicación.

¿Qué pasa con las cargas que se superponen parcial o totalmente a las tiendas anteriores, pero que no tienen la misma dirección de inicio? (Ver el final de esta publicación para un caso específico)


Supongamos el siguiente código tipo C:

// lock - pointer to an aligned int64 variable // threadNum - integer in the range 0..7 // volatiles here just to show direct r/w of the memory as it was suggested in the comments int TryLock(volatile INT64* lock, INT64 threadNum) { if (0 != *lock) return 0; // another thread already had the lock ((volatile INT8*)lock)[threadNum] = 1; // take the lock by setting our byte if (1LL << 8*threadNum != *lock) { // another thread set its byte between our 1st and 2nd check. unset ours ((volatile INT8*)lock)[threadNum] = 0; return 0; } return 1; } 

O su equivalente en x64 asm:

 ; rcx - address of an aligned int64 variable ; rdx - integer in the range 0..7 TryLock PROC cmp qword ptr [rcx], 0 jne @fail mov r8, rdx mov rax, 8 mul rdx mov byte ptr [rcx+r8], 1 bts rdx, rax cmp qword ptr [rcx], rdx jz @success mov byte ptr [rcx+r8], 0 @fail: mov rax, 0 ret @success: mov rax, 1 ret 

Entonces supongamos que TryLock se ejecuta simultáneamente en dos subprocesos:

 INT64 lock = 0; void Thread_1() { TryLock(&lock, 1); } void Thread_5() { TryLock(&lock, 5); } 

La pregunta:

El ((INT8*)lock)[1] = 1; y ((INT8*)lock)[5] = 1; las tiendas no están en la misma ubicación que la carga de lock de 64 bits. Sin embargo, cada uno de ellos está completamente contenido por esa carga, entonces ¿eso “cuenta” como la misma ubicación? Parece imposible que una CPU pueda hacer eso.

¿Qué pasa con ((INT8*)lock)[0] = 1 ? La dirección de la tienda es entonces la misma que la dirección de la siguiente carga. ¿Estas operaciones “están en el mismo lugar”, incluso si el caso anterior no fue?

Por favor, observe que la pregunta no es sobre el código C / Asm, sino sobre el comportamiento de las CPU x86.

¿Puede x86 reordenar una tienda estrecha con una carga más amplia que la contiene por completo?

Sí, x86 puede reordenar una tienda estrecha con una carga más amplia que la contiene por completo.

Es por eso que su algoritmo de locking está roto, shared_value no es igual a 800000:

  1. GCC 6.1.0 x86_64 – enlace al código del ensamblador: https://godbolt.org/g/ZK9Wql

  2. Clang 3.8.0 x86_64 – enlace al código del ensamblador: https://godbolt.org/g/qn7XuJ

Vea a continuación el ejemplo correcto.


La pregunta:

El locking ((INT8 *)) [1] = 1; y ((INT8 *) locking) [5] = 1; las tiendas no están en la misma ubicación que la carga de locking de 64 bits. Sin embargo, cada uno de ellos está completamente contenido por esa carga, entonces ¿eso “cuenta” como la misma ubicación?

No, eso no.

El Manual del desarrollador de software Intel® 64 e IA-32 Architectures dice:

8.2.3.4 Las cargas se pueden reordenar con tiendas anteriores a diferentes ubicaciones El modelo de solicitud de memoria Intel-64 permite reordenar una carga con una tienda anterior a una ubicación diferente. Sin embargo, las cargas no se reordenan con las tiendas en la misma ubicación.

Esta es una regla simplificada para el caso cuando la TIENDA y la CARGA tienen el mismo tamaño.

Pero una regla general es que la escritura en la memoria se retrasa por un tiempo, y ALMACENAR (dirección + valor) en cola en el Buffer de Tienda para esperar la línea de caché en estado exclusivo (E) – cuando esta línea de caché se invalidará ( I) en el caché de otros núcleos de CPU. Pero puede usar la operación de asm MFENCE (o cualquier operación con el prefijo [LOCK] ) para esperar forzosamente hasta que la escritura MFENCE , y las siguientes instrucciones se pueden realizar solo después de que se haya borrado el almacenamiento intermedio de la tienda, y STORE estará visible para todos CPU-Cores.

Acerca de reordenar dos líneas:

 ((volatile INT8*)lock)[threadNum] = 1; // STORE if (1LL < < 8*threadNum != *lock) // LOAD 
  • Si el tamaño de STORE y LOAD es el mismo, CARGUE CPU-Core (búsqueda de almacenamiento) en Store-Buffer y ve todos los datos necesarios; puede obtener todos los datos reales antes de que se haya realizado la TIENDA

  • Si los tamaños STORE y LOAD no son iguales, STORE (1 Byte) y LOAD (8 Byte), incluso si LOAD CPU-Core realiza una búsqueda en Store-Buffer, verá solo 1/8 de los datos requeridos; no puede obtener todos los datos reales en este momento antes de que se haya hecho la TIENDA. Aquí podría haber 2 variantes de acciones de CPU:

    1. caso-1: CPU-Core carga otros datos de la línea de caché que en estado compartido (S) y se superpone 1 byte desde el búfer de la tienda, pero la TIENDA aún permanece en el búfer de la tienda y espera la recepción de un estado exclusivo ( E) línea de caché para modificarlo, es decir, CPU-Core lee los datos antes de que se haya realizado ALMACENAMIENTO, en su ejemplo son razas de datos (error). STORE-LOAD se reordenó a LOAD-STORE en globalmente visible. - Esto es exactamente lo que sucede en x86_64

    2. caso-2: CPU-Core espera cuando Store-Buffer se vaciará, STORE ha esperado un estado exclusivo (E) de la línea de caché y se ha realizado ALMACENAMIENTO, luego CPU-Core carga todos los datos requeridos desde la línea de caché. STORE-LOAD no se reordena en globalmente visible. Pero esto es lo mismo que si MFENCE el MFENCE .

Conclusión, debe usar MFENCE después de ALMACENAR en cualquier caso:

  1. Resuelve completamente el problema en el caso-1.
  2. No tendrá ningún efecto sobre el comportamiento y el rendimiento en el caso-2. MFENCE explícito para Store-Buffer va a terminar inmediatamente.

El ejemplo correcto en C y x86_64 asm:

MFENCE la CPU-Core a actuar como en el caso-2 usando MFENCE , en consecuencia no hay una reordenación de StoreLoad

Nota: xchgb siempre tiene el prefijo LOCK , por lo que generalmente no está escrito en asm o se indica entre corchetes.

Todos los demás comstackdores se pueden seleccionar manualmente en los enlaces anteriores: PowerPC, ARM, ARM64, MIPS, MIPS64, AVR.

C-code - debería usar consistencia secuencial para la primera STORE y la próxima LOAD:

 #ifdef __cplusplus #include  using namespace std; #else #include  #endif // lock - pointer to an aligned int64 variable // threadNum - integer in the range 0..7 // volatiles here just to show direct r/w of the memory as it was suggested in the comments int TryLock(volatile uint64_t* lock, uint64_t threadNum) { //if (0 != *lock) if (0 != atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_acquire)) return 0; // another thread already had the lock //((volatile uint8_t*)lock)[threadNum] = 1; // take the lock by setting our byte uint8_t* current_lock = ((uint8_t*)lock) + threadNum; atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)1, memory_order_seq_cst); //if (1LL < < 8*threadNum != *lock) // You already know that this flag is set and should not have to check it. if ( 0 != ( (~(1LL << 8*threadNum)) & atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_seq_cst) )) { // another thread set its byte between our 1st and 2nd check. unset ours //((volatile uint8_t*)lock)[threadNum] = 0; atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)0, memory_order_release); return 0; } return 1; } 

GCC 6.1.0 - x86_64 asm-code - debería usar MFENCE para la primera TIENDA:

 TryLock(unsigned long volatile*, unsigned long): movq (%rdi), %rdx xorl %eax, %eax testq %rdx, %rdx je .L7 .L1: rep ret .L7: leaq (%rdi,%rsi), %r8 leaq 0(,%rsi,8), %rcx movq $-2, %rax movb $1, (%r8) rolq %cl, %rax mfence movq (%rdi), %rdi movq %rax, %rdx movl $1, %eax testq %rdi, %rdx je .L1 movb $0, (%r8) xorl %eax, %eax ret 

Ejemplo completo de cómo funciona: http://coliru.stacked-crooked.com/a/65e3002909d8beae

 shared_value = 800000 

Qué pasará si no usas MFENCE - Data-Races

Hay un reordenamiento de StoreLoad como en el caso-1 descrito anteriormente (es decir, si no se usa la consistencia secuencial para TIENDA) - asm: https://godbolt.org/g/p3j9fR

Cambié la barrera de memoria para STORE de memory_order_seq_cst a memory_order_release , elimina MFENCE - y ahora hay razas de datos - shared_value no es igual a 800000.

enter image description here

¿Puede mov byte [rcx+r8], 1 reordenar con cmp qword [rcx], rdx carga que lo sigue? Este es el lock[threadNum]=1 tienda y la siguiente carga para asegurarse de que nadie más escribió un byte.

La carga debe devolver datos que incluyan la tienda, porque la secuencia de ejecución siempre observa que sus propias acciones suceden en el orden del progtwig. (Esto es cierto incluso en ISA débilmente ordenadas).


Resulta que esta idea de locking exacto se ha propuesto antes (para el kernel de Linux), y Linus Torvalds explicó que x86 realmente permite este tipo de reordenamiento

A pesar del término “falla o pérdida de reenvío de tienda” , no significa que los datos tienen que comprometerse con la memoria caché antes de que la carga pueda leerla. En realidad, se puede leer desde el búfer de la tienda mientras la línea de la memoria caché todavía está en estado S ( MESI ). (Y en núcleos de Atom en orden, ni siquiera tienes un puesto de reenvío de tiendas).

El hardware real funciona de esta manera (como lo muestran las pruebas de Alex): la CPU fusionará los datos de L1D con los datos del búfer de la tienda, sin comprometer la tienda con L1D.

Esto por sí solo no se está reordenando aún 1 (la carga ve los datos de la tienda, y son adyacentes en el orden global), pero deja la puerta abierta para reordenar. La línea de caché puede ser invalidada por otro núcleo después de la carga, pero antes de que la tienda se comprometa. Una tienda de otro núcleo puede volverse visible a nivel mundial después de nuestra carga, pero antes de nuestra tienda.

Entonces, la carga incluye datos de nuestra propia tienda, pero no de otra tienda desde otra CPU. La otra CPU puede ver el mismo efecto para su carga y, por lo tanto, ambos hilos entran en la sección crítica.


1 (Este es el punto que estaba haciendo en los comentarios sobre la respuesta de Alex . Si x86 no permitía este reordenamiento, las CPU aún podían hacer el reenvío de tienda especulativamente antes de que la tienda se volviera globalmente visible, y dispararlo si otra CPU invalidaba el caché línea antes de que la tienda se comprometiera. Esa parte de la respuesta de Alex no probaba que x86 funcionara de la forma en que lo hace. Solo las pruebas experimentales y el razonamiento cuidadoso sobre el locking nos lo dieron).

Si x86 no permitía este reordenamiento, un par almacenar / parcialmente superponer-recargar funcionaría como un MFENCE: las cargas anteriores no pueden volverse visibles globalmente antes de la carga, y las tiendas anteriores no pueden volverse visibles globalmente antes de la tienda. La carga debe volverse globalmente visible antes de cualquier carga o almacenamiento posterior, y también impediría que la tienda se demore.

Dado este razonamiento, no es del todo obvio por qué las tiendas perfectamente superpuestas tampoco son equivalentes a MFENCE. ¡Quizás lo sean en realidad, y x86 solo logra hacer derrames / recargas o pasar arg en la stack rápidamente con la ejecución especulativa!


El esquema de locking:

Parece que TryLock puede fallar para ambos / todos los llamantes: todos lo ven inicialmente cero, todos escriben su byte, luego todos ven al menos dos bytes distintos de cero cada uno. Esto no es ideal para lockings muy disputados, en comparación con el uso de una instrucción de lock . Existe un mecanismo de arbitraje de hardware para manejar inss lock conflictivos. (TODO: busque la publicación del foro de Intel donde un ingeniero de Intel publicó esto en respuesta a otro tema de repetición de software vs. instrucción de lock , IIRC).

La escritura estrecha / lectura amplia siempre desencadenará un locking de almacenamiento en el hardware x86 moderno. Creo que esto solo significa que el resultado de la carga no está listo para varios ciclos, no que la ejecución de otras paradas de instrucciones (al menos no en un diseño de OOO).

En un candado levemente disputado que se usa con frecuencia, la sucursal predecirá correctamente que tomará la ruta sin conflicto. La ejecución especulativa por ese camino hasta que la carga finalmente se complete y la sucursal pueda retirarse no debe estancarse, ya que los puestos de reenvío de tiendas no son lo suficientemente largos como para llenar el ROB.

  • SnB: ~ 12 ciclos más que cuando funciona el reenvío de tienda (~ 5c)
  • HSW: ~ 10c más largo
  • SKL: ~ 11c más que cuando funciona el reenvío de tienda (4c para los operandos de 32 y 64 bits, que es 1c menos que las CPU anteriores)
  • AMD K8 / K10: Agner Fog no da un número.
  • AMD Bulldozer-family: 25-26c (Steamroller)

  • Átomo: “A diferencia de la mayoría de los otros procesadores, el Atom puede hacer el reenvío de tienda incluso si el operando de lectura es más grande que el operando de escritura precedente o está alineado de forma diferente”, y solo hay 1c de latencia. Solo falla al cruzar un límite de la línea de caché.

  • Silvermont: ~ 5c extra (base: 7c)
  • AMD Bobcat / Jaguar: 4-11c extra (base: 8c / 3c)

Entonces, si todo el esquema de locking funciona, podría funcionar bien para lockings levemente disputados.

Creo que podría convertirlo en un locking de varios lectores / solo escritor utilizando el bit 1 en cada byte para lectores y el bit 2 para escritores. TryLock_reader ignoraría los bits del lector en otros bytes. TryLock_writer funcionaría como el original, requiriendo un cero en todos los bits en otros bytes.


Por cierto, para el orden de la memoria en general, el blog de Jeff Preshing es excelente .