c++ multithreading x86-64 lock-free stdatomic

c++ - Adquirir/liberar semántica con almacenes no temporales en x64



multithreading x86-64 (1)

Podría estar equivocado acerca de algunas cosas en esta respuesta (¡lectura de prueba bienvenida de personas que saben esto!). Se basa en la lectura de los documentos y el blog de Jeff Preshing, no en experiencias o pruebas recientes reales.

Linus Torvalds recomienda enfáticamente no intentar inventar su propio bloqueo, porque es muy fácil equivocarse. Es más un problema al escribir código portátil para el kernel de Linux, en lugar de algo que es solo x86, por lo que me siento lo suficientemente valiente como para tratar de resolver las cosas para x86.

La forma normal de usar los almacenes NT es hacer un montón de ellos en una fila, como parte de un memset o memcpy, luego un SFENCE , luego un almacén de lanzamiento normal a una variable de bandera compartida: done_flag.store(1, std::memory_order_release) .

Usar una tienda movnti para la variable de sincronización perjudicará el rendimiento. Es posible que desee utilizar las tiendas NT en el Foo que apunta, pero desalojar el puntero del caché es perverso. ( movnt tiendas movnt desalojan la línea de caché si estaba en caché para empezar ; consulte el vol. cap. 10.4.6.2 Almacenamiento en caché de datos temporales versus no temporales ).

El objetivo de las tiendas NT es usarlo con datos no temporales, que no se usarán nuevamente (por ningún hilo) durante mucho tiempo, si es que lo hacen. Se espera que los bloqueos que controlan el acceso a los buffers compartidos, o las banderas que los productores / consumidores usan para marcar los datos como leídos, sean leídos por otros núcleos.

Los nombres de sus funciones tampoco reflejan realmente lo que está haciendo.

El hardware x86 está extremadamente optimizado para hacer almacenes de lanzamiento normales (no NT), porque cada tienda normal es un almacén de lanzamiento. El hardware tiene que ser bueno para que x86 se ejecute rápido.

El uso de almacenes / cargas normales solo requiere un viaje a la caché L3, no a la DRAM, para la comunicación entre subprocesos en las CPU Intel. La gran caché L3 inclusiva de Intel funciona como un respaldo para el tráfico de coherencia de caché. Al sondear las etiquetas L3 en una falla de un núcleo, se detectará el hecho de que otro núcleo tiene la línea de caché en el estado Modificado o Exclusivo . Las tiendas NT requerirían variables de sincronización para llegar a DRAM y regresar a otro núcleo para verlo.

Pedidos de memoria para tiendas de streaming NT

movnt tiendas movnt se pueden reordenar con otras tiendas, pero no con lecturas anteriores.

Intel x86 manual vol3, capítulo 8.2.2 (Pedido de memoria en P6 y familias de procesadores más recientes) :

  • Las lecturas no se reordenan con otras lecturas.
  • Las escrituras no se reordenan con lecturas anteriores . (tenga en cuenta la falta de excepciones).
  • Las escrituras en memoria no se reordenan con otras escrituras, con las siguientes excepciones:
  • ... cosas sobre clflushopt y las instrucciones de la cerca

actualización: también hay una nota (en 8.1.2.2 Bloqueo de bus controlado por software ) que dice:

No implemente semáforos utilizando el tipo de memoria WC. No realice almacenes no temporales en una línea de caché que contenga una ubicación utilizada para implementar un semáforo.

Esto puede ser solo una sugerencia de rendimiento; No explican si puede causar un problema de corrección. Sin embargo, tenga en cuenta que los almacenes de NT no son coherentes con la memoria caché (los datos pueden permanecer en el búfer de relleno de línea incluso si hay datos conflictivos para la misma línea en algún otro lugar del sistema o en la memoria). Tal vez podría usar de forma segura las tiendas NT como una tienda de lanzamiento que se sincroniza con cargas regulares, pero tendría problemas con operaciones atómicas de RMW como lock add dword [mem], 1 .

La semántica de liberación evita el reordenamiento de memoria de la liberación de escritura con cualquier operación de lectura o escritura que la precede en orden de programa.

Para bloquear el reordenamiento con tiendas anteriores, necesitamos una instrucción SFENCE , que es una barrera de StoreStore incluso para tiendas NT. (Y también es una barrera para algunos tipos de reordenamiento en tiempo de compilación, pero no estoy seguro de si bloquea que las cargas anteriores crucen la barrera). Las tiendas normales no necesitan ningún tipo de instrucción de barrera para ser tiendas de liberación, por lo que solo necesita SFENCE cuando usa las tiendas NT.

Para cargas: el modelo de memoria x86 para memoria WB ( reescritura , es decir, "normal") ya evita la reordenación de LoadStore incluso para tiendas ordenadas débilmente, por lo que no necesitamos un LFENCE para su efecto de barrera LoadStore , solo una barrera del compilador LoadStore antes de la tienda NT. Al menos en la implementación de gcc, std::atomic_signal_fence(std::memory_order_release) es una barrera compiladora incluso para cargas / tiendas no atómicas, pero atomic_thread_fence es solo una barrera para cargas / tiendas atomic<> (incluido mo_relaxed ). El uso de un atomic_thread_fence todavía le da al compilador más libertad para reordenar cargas / tiendas a variables no compartidas. Vea este Q&A para más .

// The function can''t be called release_store unless it actually is one (i.e. includes all necessary barriers) // Your original function should be called relaxed_store void NT_release_store(const Foo* f) { // _mm_lfence(); // make sure all reads from the locked region are already globally visible. Not needed: this is already guaranteed std::atomic_thread_fence(std::memory_order_release); // no insns emitted on x86 (since it assumes no NT stores), but still a compiler barrier for earlier atomic<> ops _mm_sfence(); // make sure all writes to the locked region are already globally visible, and don''t reorder with the NT store _mm_stream_si64((long long int*)&gFoo, (int64_t)f); }

Esto se almacena en la variable atómica (tenga en cuenta la falta de desreferenciación &gFoo ). Su función se almacena en el Foo que apunta, lo cual es súper extraño; IDK cuál era el punto de eso. También tenga en cuenta que se compila como código válido de C ++ 11 .

Cuando piense en lo que significa una tienda de lanzamiento, piense en ella como la tienda que libera el bloqueo en una estructura de datos compartida. En su caso, cuando el almacén de lanzamientos se vuelve globalmente visible, cualquier hilo que lo vea debería poder desreferenciarlo de manera segura.

Para hacer una adquisición-carga, solo dile al compilador que quieres una.

x86 no necesita ninguna instrucción de barrera, pero especificar mo_acquire lugar de mo_relaxed le proporciona la barrera de compilación necesaria. Como beneficio adicional, esta función es portátil: obtendrá todas las barreras necesarias en otras arquitecturas:

Foo* acquire_load() { return gFoo.load(std::memory_order_acquire); }

No dijo nada sobre el almacenamiento de gFoo en una gFoo WC (combinación de escritura no almacenable en gFoo débilmente ordenada. Probablemente sea muy difícil organizar el segmento de datos de su programa para que se gFoo a la memoria WC ... Sería mucho más fácil para gFoo señalar simplemente la memoria WC, después de asignar un poco de RAM de video WC o algo así. Pero si desea adquirir cargas de la memoria WC, probablemente necesite LFENCE . NO SÉ. Haga otra pregunta al respecto, porque esta respuesta supone en su mayoría que está utilizando la memoria WB.

Tenga en cuenta que el uso de un puntero en lugar de una bandera crea una dependencia de datos. Creo que debería poder usar gFoo.load(std::memory_order_consume) , que no requiere barreras ni siquiera en CPU con un orden débil (que no sea Alpha). Una vez que los compiladores están lo suficientemente avanzados como para asegurarse de que no rompen la dependencia de datos, en realidad pueden crear un mejor código (en lugar de promover mo_consume a mo_acquire . Lea sobre esto antes de usar mo_consume en el código de producción, y especialmente tenga en cuenta que probarlo correctamente es imposible porque se espera que los futuros compiladores ofrezcan garantías más débiles que los compiladores actuales en la práctica.

Inicialmente, pensaba que necesitábamos LFENCE para obtener una barrera LoadStore. ("Las escrituras no pueden pasar instrucciones anteriores de LFENCE, SFENCE y MFENCE". Esto a su vez evita que pasen (antes de ser globalmente visibles) las lecturas anteriores a LFENCE).

Tenga en cuenta que LFENCE + SFENCE sigue siendo más débil que un MFENCE completo, porque no es una barrera de StoreLoad. La propia documentación de SFENCE dice que se ordenó wrt. LFENCE, pero esa tabla del modelo de memoria x86 del manual Intel vol3 no menciona eso. Si SFENCE no puede ejecutarse hasta después de un LFENCE, entonces sfence / lfence podría ser un equivalente más lento que mfence , pero lfence / sfence / movnti daría semántica de liberación sin una barrera completa. Tenga en cuenta que la tienda NT podría volverse globalmente visible después de algunas cargas / tiendas siguientes, a diferencia de una tienda x86 normal fuertemente ordenada).

Relacionado: cargas NT

En x86, cada carga ha adquirido semántica, excepto las cargas de la memoria WC. SSE4.1 MOVNTDQA es la única instrucción de carga no temporal, y no está ordenada débilmente cuando se usa en la memoria normal (WriteBack). Por lo tanto, también es una carga de adquisición (cuando se usa en la memoria WB).

Tenga en cuenta que movntdq solo tiene un formulario de almacenamiento, mientras que movntdqa solo tiene un formulario de carga. Pero aparentemente Intel no podía simplemente llamarlos storentdqa y loadntdqa . Ambos tienen un requisito de alineación de 16B o 32B, por lo que dejar el a no tiene mucho sentido para mí. Supongo que SSE1 y SSE2 ya habían introducido algunas tiendas NT que ya usaban mov... mnemonic (como movntps ), pero no se movntps hasta años más tarde en SSE4.1. (2da generación Core2: 45nm Penryn).

Los documentos dicen que MOVNTDQA no cambia la semántica de pedidos para el tipo de memoria en la que se usa .

... Una implementación también puede hacer uso de la sugerencia no temporal asociada con esta instrucción si la fuente de memoria es el tipo de memoria WB (reescritura).

La implementación de una sugerencia no temporal por parte de un procesador no anula la semántica efectiva del tipo de memoria , pero la implementación de la sugerencia depende del procesador. Por ejemplo, una implementación de procesador puede optar por ignorar la sugerencia y procesar la instrucción como un MOVDQA normal para cualquier tipo de memoria.

En la práctica, las CPU Intel principales actuales (Haswell, Skylake) parecen ignorar la sugerencia para las cargas PREFETCHNTA y MOVNTDQA de la memoria WB . Consulte ¿Las arquitecturas x86 actuales admiten cargas no temporales (de la memoria "normal")? , y también las cargas no temporales y el prefetcher de hardware, ¿funcionan juntos? para más detalles.

Además, si lo está utilizando en la memoria WC (por ejemplo, copiando de la RAM de video, como en esta guía de Intel ):

Debido a que el protocolo WC usa un modelo de consistencia de memoria débilmente ordenado, se debe usar una instrucción MFENCE o bloqueada junto con las instrucciones MOVNTDQA si varios procesadores pueden hacer referencia a las mismas ubicaciones de memoria WC o para sincronizar las lecturas de un procesador con las escrituras de otros agentes en el sistema.

Sin embargo, eso no explica cómo debe usarse. Y no estoy seguro de por qué dicen MFENCE en lugar de LFENCE para leer. Tal vez están hablando de una situación de escritura en la memoria del dispositivo, lectura desde la memoria del dispositivo donde las tiendas deben ordenarse con respecto a las cargas (barrera StoreLoad), no solo entre sí (barrera StoreStore).

En Vol3 busqué movntdqa y no movntdqa ningún resultado (en todo el pdf). 3 éxitos para movntdq : toda la discusión sobre los pedidos débiles y los tipos de memoria solo habla de tiendas. Tenga en cuenta que LFENCE se introdujo mucho antes de SSE4.1. Presumiblemente es útil para algo, pero IDK qué. Para ordenar la carga, probablemente solo con memoria WC, pero no he leído cuándo sería útil.

LFENCE parece ser más que una simple barrera LoadLoad para cargas mal ordenadas: también ordena otras instrucciones. (Sin embargo, no es la visibilidad global de las tiendas, solo su ejecución local).

Del manual de referencia de Intel:

Específicamente, LFENCE no se ejecuta hasta que todas las instrucciones anteriores se hayan completado localmente, y ninguna instrucción posterior comienza a ejecutarse hasta que LFENCE se complete.
...
Las instrucciones que siguen a un LFENCE se pueden recuperar de la memoria antes del LFENCE, pero no se ejecutarán hasta que el LFENCE se complete.

La entrada para rdtsc sugiere usar LFENCE;RDTSC para evitar que se ejecute antes de las instrucciones anteriores, cuando RDTSCP no está disponible (y la garantía de pedido más débil está bien: rdtscp no deja de seguir las instrucciones antes de ejecutarlo). ( CPUID es una sugerencia común para serializar el flujo de instrucciones alrededor de rdtsc ).

Tengo algo como:

if (f = acquire_load() == ) { ... use Foo }

y:

auto f = new Foo(); release_store(f)

Podrías imaginar fácilmente una implementación de adquirir_carga y liberar_almacén que usa atómico con carga (memory_order_acquire) y store (memory_order_release). Pero ahora, ¿qué pasa si release_store se implementa con _mm_stream_si64, una escritura no temporal, que no está ordenada con respecto a otras tiendas en x64? ¿Cómo obtener la misma semántica?

Creo que lo siguiente es el mínimo requerido:

atomic<Foo*> gFoo; Foo* acquire_load() { return gFoo.load(memory_order_relaxed); } void release_store(Foo* f) { _mm_stream_si64(*(Foo**)&gFoo, f); }

Y úsalo así:

// thread 1 if (f = acquire_load() == ) { _mm_lfence(); ... use Foo }

y:

// thread 2 auto f = new Foo(); _mm_sfence(); // ensures Foo is constructed by the time f is published to gFoo release_store(f)

¿Es eso correcto? Estoy bastante seguro de que la defensa es absolutamente necesaria aquí. ¿Pero qué hay de la cerca? ¿Es necesario o una simple barrera de compilación sería suficiente para x64? por ejemplo, asm volátil (""::: "memoria"). Según el modelo de memoria x86, las cargas no se reordenan con otras cargas. Entonces, a mi entender, adquire_load () debe suceder antes de cualquier carga dentro de la instrucción if, siempre que haya una barrera de compilación.