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

assembly locking (2)

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

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

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

GCC 6.1.0 x86_64 - enlace al código del ensamblador: https://godbolt.org/g/ZK9Wql
- shared_value = 662198 : http://coliru.stacked-crooked.com/a/157380085ccad40f
Clang 3.8.0 x86_64 - enlace al código del ensamblador: https://godbolt.org/g/qn7XuJ
- shared_value = 538246 : http://coliru.stacked-crooked.com/a/ecec7f021a2a9782

Vea a continuación el ejemplo correcto.

La pregunta:

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

No, eso no.

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

8.2.3.4 Las cargas se pueden reordenar con tiendas anteriores a diferentes ubicaciones El modelo de pedido 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 tiendas en la misma ubicación.

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

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

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 igual, entonces LOAD CPU-Core realiza la búsqueda (Store-forwarding) en Store-Buffer y ve todos los datos requeridos: puede obtener todos los datos reales ahora mismo antes de que se haya completado STORE
Si el tamaño de STORE y LOAD no es igual, STORE (1 Byte) y LOAD (8 Byte), incluso si LOAD CPU-Core busca en Store-Buffer, solo verá 1/8 de los datos requeridos; no puede Obtenga todos los datos reales en este momento antes de que se haya almacenado. Aquí podría haber 2 variantes de acciones de CPU:
1. case-1: CPU-Core carga otros datos de la línea de caché que está en estado compartido (S), y se superpone a 1 byte de Store Buffer, pero STORE aún permanece en Store Buffer y espera la recepción de un estado exclusivo ( E) línea de caché para modificarla, es decir, CPU-Core lee los datos antes de que se haya almacenado, en su ejemplo es carreras de datos (error). STORE-LOAD reordenado a LOAD-STORE en globalmente visible. - Esto es exactamente lo que sucede en x86_64
2. caso-2: CPU-Core espera cuando se vacía Store-Buffer, STORE ha esperado un estado exclusivo (E) de línea de caché y STORE se ha realizado, luego CPU-Core carga todos los datos necesarios de 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 STORE en cualquier caso:

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

El ejemplo correcto en C y x86_64 asm:

MFENCE al CPU-Core a actuar como en el caso 2 usando MFENCE , por lo tanto no hay reordenamiento de StoreLoad

GCC 6.1.0 (usa mfence para vaciar Store-Buffer): https://godbolt.org/g/dtNMZ7
Clang 4.0 (usa [LOCK] xchgb reg, [addr] para vaciar Store-Buffer): https://godbolt.org/g/BQY6Ju

Nota: xchgb siempre tiene el prefijo LOCK , por lo que generalmente no se escribe en asm ni se indica entre paréntesis.

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

Código C: debe usar la coherencia secuencial para la primera TIENDA y la próxima CARGA:

#ifdef __cplusplus #include <atomic> using namespace std; #else #include <stdatomic.h> #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 - código asm x86_64 - debe 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é sucederá si no usa MFENCE - Data-Races

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

GCC 6.1.0 x86_64 - shared_value = 610307 : http://coliru.stacked-crooked.com/a/469f087b1ce32977
Clang 3.8.0 x86_64 - shared_value = 678949 : http://coliru.stacked-crooked.com/a/25070868d3cfbbdd

Cambié la barrera de memoria para STORE de memory_order_seq_cst a memory_order_release , elimina MFENCE , y ahora hay carreras de datos, el valor compartido no es igual a 800000.

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

8.2.3.4 Las cargas se pueden reordenar con tiendas anteriores a diferentes ubicaciones
El modelo de pedido 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 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? (Vea 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 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

Luego, suponga que TryLock se ejecuta simultáneamente en dos hilos:

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 una está completamente contenida 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 la misma ubicación", incluso si el caso anterior no lo fuera?

PD: tenga en cuenta que la pregunta no se trata del código C / Asm, sino del comportamiento de las CPU x86.

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

La carga debe devolver datos que incluyen la tienda, porque el subproceso en ejecución siempre observa que sus propias acciones suceden en el orden del programa. (Esto es cierto incluso en las ISA de orden débil).

Resulta que esta idea de bloqueo exacta 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 la tienda" , no significa que los datos tengan que comprometerse con el caché antes de que la carga pueda leerlo. En realidad, se puede leer desde el búfer de la tienda mientras la línea de caché todavía está en estado S ( MESI ). (Y en los núcleos Atom en orden, ni siquiera obtienes un puesto de reenvío de la tienda).

El hardware real funciona de esta manera (como 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 a L1D.

Esto por sí solo no está reordenando todavía ¹ (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 hacerse globalmente visible después de nuestra carga, pero antes de nuestra tienda.

Entonces, la carga incluye datos de nuestra propia tienda, pero no de la otra tienda de 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.

¹ (Este es el punto que estaba señalando en los comentarios sobre la respuesta de Alex . Si x86 no permitiera este reordenamiento, las CPU aún podrían hacer el reenvío de la tienda especulativamente antes de que la tienda se vuelva globalmente visible, y derribarla si otra CPU invalida el caché antes de que la tienda se comprometiera. Esa parte de la respuesta de Alex no demostró que x86 funcionara como lo hace. Solo las pruebas experimentales y el razonamiento cuidadoso sobre el bloqueo nos dieron eso.)

Si x86 no permitiera esta reordenación, un par tienda / superposición parcial-recarga funcionaría como un MFENCE: las cargas anteriores no pueden hacerse visibles globalmente antes de la carga, y las tiendas anteriores no pueden hacerse visibles globalmente antes de la tienda. La carga tiene que hacerse visible globalmente antes de cualquier carga o tienda siguiente, y también evitaría que la tienda se retrase.

Dado este razonamiento, no es totalmente obvio por qué las tiendas que se superponen perfectamente no son equivalentes a un MFENCE también. ¡Tal vez lo sean, y x86 solo logra hacer derramar / recargar o pasar argumentos en la pila rápidamente con ejecución especulativa!

El esquema de bloqueo:

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 cerraduras muy contenidas, en comparación con el uso de una instrucción de lock . Existe un mecanismo de arbitraje de hardware para manejar entradas de conflicto lock . (TODO: encuentre la publicación del foro de Intel donde un ingeniero de Intel publicó esto en respuesta a otro bucle de reintento de software vs. tema de instrucción lock , IIRC).

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

En una cerradura ligeramente contenida que se usa con frecuencia, la rama se predecirá correctamente para tomar el camino sin conflicto. La ejecución especulativa por ese camino hasta que la carga finalmente se complete y la rama pueda retirarse no debería detenerse, porque los puestos de reenvío de la tienda 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 operandos de 32 y 64 bits, que es 1c menos que las CPU anteriores)
AMD K8 / K10: Agner Fog no da un número.
Familia de excavadoras AMD: 25-26c (apisonadora)
Atom: "A diferencia de la mayoría de los otros procesadores, Atom puede hacer reenvío de almacenamiento incluso si el operando de lectura es mayor que el operando de escritura anterior o está alineado de manera diferente", y solo hay una latencia de 1c. Solo falla al cruzar un límite de línea de caché.
Silvermont: ~ 5c extra (base: 7c)
AMD Bobcat / Jaguar: 4-11c extra (base: 8c / 3c)

Entonces, si todo el esquema de bloqueo funciona, podría funcionar bien para cerraduras con poca competencia.

Creo que podría convertirlo en un bloqueo de múltiples lectores / escritor único 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 los pedidos de memoria en general, el blog de Jeff Preshing es excelente .