valor tipos resumen qué modelos los datos cuadro cada atomicos atomico c++ c concurrency x86 atomic

c++ - tipos - ¿Por qué la asignación de enteros en una variable alineada naturalmente es atómica en x86?



tipos de datos atomicos en java (5)

He estado leyendo este article sobre operaciones atómicas, y menciona que la asignación de enteros de 32 bits es atómica en x86, siempre que la variable esté naturalmente alineada.

¿Por qué la alineación natural asegura la atomicidad?

Naturalmente alineado significa que la dirección del tipo es un múltiplo del tamaño del tipo.

Por ejemplo, un byte puede estar en cualquier dirección, un corto (suponiendo 16 bits) debe estar en un múltiplo de 2, un int (asumiendo 32 bits) debe estar en un múltiplo de 4, y un largo (asumiendo 64 bits) debe estar en un múltiplo de 8.

En el caso de que acceda a un dato que no esté alineado de forma natural, la CPU generará una falla o leerá / escribirá la memoria, pero no como una operación atómica. La acción que tome la CPU dependerá de la arquitectura.

Por ejemplo, en la imagen tenemos el diseño de memoria a continuación:

01234567 ...XXXX.

y

int *data = (int*)3;

Cuando intentamos leer *data los bytes que componen el valor se distribuyen en 2 bloques de tamaño int, 1 byte está en el bloque 0-3 y 3 bytes están en el bloque 4-7. Ahora, solo porque los bloques estén lógicamente uno al lado del otro no significa que estén físicamente. Por ejemplo, el bloque 0-3 podría estar al final de una línea de caché de la CPU, mientras que el bloque 3-7 está en un archivo de página. Cuando la CPU va al bloque de acceso 3-7 para obtener los 3 bytes que necesita, puede ver que el bloque no está en la memoria y señala que necesita la memoria paginada. Esto probablemente bloqueará el proceso de llamada mientras el sistema operativo páginas de la memoria de nuevo.

Después de que la memoria ha sido paginada, pero antes de que su proceso se vuelva a activar, puede aparecer otro y escribir una Y en la dirección 4. Luego, su proceso se reprograma y la CPU completa la lectura, pero ahora ha leído XYXX, en lugar de el XXXX que esperabas

Para responder a su primera pregunta, una variable se alinea naturalmente si existe en una dirección de memoria que es un múltiplo de su tamaño.

Si consideramos solo, como lo hace el artículo que vinculó, instrucciones de asignación , entonces la alineación garantiza la atomicidad porque MOV (la instrucción de asignación) es atómica por diseño en datos alineados.

Otros tipos de instrucciones, INC, por ejemplo, deben estar bloqueadas (un prefijo x86 que proporciona acceso exclusivo a la memoria compartida al procesador actual durante la operación prefijada) incluso si los datos están alineados porque realmente se ejecutan a través de múltiples pasos (= instrucciones, a saber, load, inc, store).

Si estuviera preguntando por qué está diseñado así, diría que es un buen producto secundario del diseño de la arquitectura de la CPU.

En el tiempo 486, no hay una CPU de múltiples núcleos o un enlace QPI, por lo que la atomicidad no es realmente un requisito estricto en ese momento (¿DMA puede requerirlo?).

En x86, el ancho de datos es de 32 bits (o 64 bits para x86_64), lo que significa que la CPU puede leer y escribir hasta el ancho de datos de una sola vez. Y el bus de datos de memoria es típicamente el mismo o más ancho que este número. Combinado con el hecho de que la lectura / escritura en una dirección alineada se realiza de una vez, naturalmente no hay nada que impida que la lectura / escritura no sea atómica. Ganas velocidad / atómica al mismo tiempo.

Si un objeto de 32 bits o más pequeño se alinea naturalmente dentro de una parte "normal" de la memoria, será posible que cualquier 80386 o procesador compatible que no sea el 80386sx lea o escriba los 32 bits del objeto en una sola operación. Si bien la capacidad de una plataforma para hacer algo de manera rápida y útil no necesariamente significa que la plataforma a veces no lo hará de alguna otra manera por alguna razón, y aunque creo que es posible en muchos, si no todos, los procesadores x86 tienen regiones de memoria a las que solo se puede acceder 8 o 16 bits a la vez, no creo que Intel haya definido alguna condición en la que solicitar un acceso alineado de 32 bits a un área "normal" de memoria haga que el sistema lea o escribir parte del valor sin leer o escribir todo, y no creo que Intel tenga la intención de definir algo así para áreas de memoria "normales".

La alineación "natural" significa alineado a su propio ancho de tipo . Por lo tanto, la carga / almacenamiento nunca se dividirá en ningún tipo de límite más ancho que sí mismo (por ejemplo, página, línea de caché o un tamaño de fragmento aún más estrecho utilizado para transferencias de datos entre diferentes cachés).

Las CPU a menudo hacen cosas como el acceso al caché o las transferencias de línea de caché entre núcleos, en fragmentos de tamaño de potencia de 2, por lo que los límites de alineación más pequeños que una línea de caché son importantes. (Ver los comentarios de @ BeeOnRope a continuación). Consulte también Atomicity en x86 para obtener más detalles sobre cómo las CPU implementan cargas atómicas o almacena internamente, y ¿Puede num ++ ser atómico para ''int num''? para obtener más información sobre cómo las operaciones atómicas de RMW como atomic<int>::fetch_add() / lock xadd se implementan internamente.

Primero, esto supone que el int se actualiza con una sola instrucción de almacenamiento, en lugar de escribir bytes diferentes por separado. Esto es parte de lo que garantiza std::atomic , pero ese simple C o C ++ no lo hace. Sin embargo, normalmente será el caso. El x86-64 System V ABI no prohíbe a los compiladores hacer que los accesos a las variables int no sean atómicos, a pesar de que requiere que int sea ​​4B con una alineación predeterminada de 4B. Por ejemplo, x = a<<16 | b x = a<<16 | b podría compilar en dos tiendas separadas de 16 bits si el compilador lo deseara.

Las carreras de datos son comportamientos indefinidos tanto en C como en C ++, por lo que los compiladores pueden asumir, y lo hacen, que la memoria no se modifica asincrónicamente. Para el código que se garantiza que no se rompa, use C11 stdatomic o C ++ 11 std::atomic . De lo contrario, el compilador solo mantendrá un valor en un registro en lugar de volver a cargarlo cada vez que lo lea , como volatile pero con garantías reales y soporte oficial del estándar de idioma.

Antes de C ++ 11, las operaciones atómicas generalmente se realizaban con volatile u otras cosas, y una buena dosis de "funciona en compiladores que nos interesan", por lo que C ++ 11 fue un gran paso adelante. Ahora ya no tiene que preocuparse por lo que hace un compilador para plain int ; solo use atomic<int> . Si encuentra guías antiguas que hablan sobre la atomicidad de int , probablemente sean anteriores a C ++ 11.

std::atomic<int> shared; // shared variable (compiler ensures alignment) int x; // local variable (compiler can keep it in a register) x = shared.load(std::memory_order_relaxed); shared.store(x, std::memory_order_relaxed); // shared = x; // don''t do that unless you actually need seq_cst, because MFENCE or XCHG is much slower than a simple store

Nota al .is_lock_free() : para atomic<T> más grande que la CPU puede hacer atómicamente (entonces .is_lock_free() es falso), vea ¿Dónde está el bloqueo para un std :: atomic? . int64_t uint64_t int e int64_t / uint64_t están libres de bloqueo en todos los principales compiladores x86.

Por lo tanto, solo necesitamos hablar sobre el comportamiento de un insn como mov [shared], eax .

TL; DR: el x86 ISA garantiza que las tiendas y las cargas alineadas naturalmente son atómicas, de hasta 64 bits de ancho. Por lo tanto, los compiladores pueden usar almacenes / cargas normales siempre que se aseguren de que std::atomic<T> tenga una alineación natural.

(Pero tenga en cuenta que i386 gcc -m32 no puede hacer eso para los _Atomic C11 _Atomic 64 bits, solo los alinea con 4B, por lo que atomic_llong no es realmente atómico. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65146#c4 ). g++ -m32 con std::atomic está bien, al menos en g ++ 5 porque https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65147 se corrigió en 2015 por un cambio en <atomic> encabezamiento. Sin embargo, eso no cambió el comportamiento del C11).

IIRC, había sistemas SMP 386, pero la semántica de memoria actual no se estableció hasta 486. Es por eso que el manual dice "486 y más reciente".

De los "Intel® 64 y IA-32 Architectures Software Developer Manuales, volumen 3", con mis notas en cursiva . (consulte también la wiki de etiquetas x86 para ver los enlaces: versiones actuales de todos los volúmenes, o enlace directo a la página 256 del vol3 pdf de diciembre de 2015 )

En terminología x86, una "palabra" son dos bytes de 8 bits. 32 bits son una palabra doble, o DWORD.

Sección 8.1.1 Operaciones atómicas garantizadas

El procesador Intel486 (y los procesadores más nuevos desde entonces) garantiza que las siguientes operaciones básicas de memoria siempre se realizarán atómicamente:

  • Leer o escribir un byte
  • Leer o escribir una palabra alineada en un límite de 16 bits
  • Leer o escribir una palabra doble alineada en un límite de 32 bits (esta es otra forma de decir "alineación natural")

El último punto que resalté es la respuesta a su pregunta: este comportamiento es parte de lo que se requiere para que un procesador sea una CPU x86 (es decir, una implementación de la ISA).

El resto de la sección ofrece más garantías para las CPU Intel más nuevas: Pentium amplía esta garantía a 64 bits .

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

  • Lectura o escritura de una palabra cuádruple alineada en un límite de 64 bits (por ejemplo, x87 carga / almacenamiento de un double , o cmpxchg8b (que era nuevo en Pentium P5))
  • Accesos de 16 bits a ubicaciones de memoria sin caché que caben dentro de un bus de datos de 32 bits.

La sección continúa para señalar que no se garantiza que los accesos divididos en líneas de caché (y límites de página) sean atómicos, y:

"Una instrucción x87 o una instrucción SSE que accede a datos mayores que una palabra cuádruple puede implementarse utilizando múltiples accesos de memoria".

El manual de AMD está de acuerdo con el de Intel sobre las cargas / tiendas alineadas de 64 bits y más estrechas que son atómicas

Por lo tanto, los números enteros, x87 y MMX / SSE cargan / almacenan hasta 64b, incluso en modo de 32 bits o 16 bits (por ejemplo, movsd , movhps , pinsrq , extractps , extractps , etc.) son atómicos si los datos están alineados. gcc -m32 usa movq xmm, [mem] para implementar cargas atómicas de 64 bits para cosas como std::atomic<int64_t> . Desafortunadamente, Clang4.0 -m32 usa el error de lock cmpxchg8b 33109 .

En algunas CPU con rutas de datos internas de 128b o 256b (entre unidades de ejecución y L1, y entre diferentes cachés), las cargas / almacenes de 128b e incluso 256b son atómicos, pero esto no está garantizado por ningún estándar o fácilmente consultable en tiempo de ejecución, desafortunadamente para los compiladores que implementan estructuras std::atomic<__int128> o 16B .

Si desea 128b atómico en todos los sistemas x86, debe usar lock cmpxchg16b (disponible solo en modo de 64 bits). (Y no estaba disponible en las CPU x86-64 de primera generación. -mcx16 usar -mcx16 con gcc / clang para que lo emitan ).

Incluso las CPU que realizan internamente cargas / almacenes atómicos de 128b pueden exhibir un comportamiento no atómico en sistemas de múltiples sockets con un protocolo de coherencia que opera en trozos más pequeños: por ejemplo, AMD Opteron 2435 (K10) con hilos que se ejecutan en zócalos separados, conectados con HyperTransport .

Los manuales de Intel y AMD divergen para el acceso no alineado a la memoria almacenable en caché . El subconjunto común para todas las CPU x86 es la regla AMD. Caché significa regiones de memoria de reescritura o reescritura, no combinables ni combinables, como se establece con las regiones PAT o MTRR. No significan que la línea de caché ya debe estar caliente en el caché L1.

  • Intel P6 y versiones posteriores garantizan la atomicidad para cargas / almacenes almacenables en caché de hasta 64 bits siempre que estén dentro de una sola línea de caché (64B o 32B en CPU muy antiguas como PentiumIII).

  • AMD garantiza la atomicidad para las cargas / tiendas almacenables en caché que se ajustan dentro de un solo fragmento alineado con 8B. Eso tiene sentido, porque sabemos por la prueba de 16B-store en Opteron multi-socket que HyperTransport solo se transfiere en fragmentos de 8B, y no se bloquea durante la transferencia para evitar el desgarro. (Véase más arriba). Supongo que el lock cmpxchg16b debe manejarse especialmente.

    Posiblemente relacionado: AMD usa MOESI para compartir líneas de caché sucias directamente entre cachés en diferentes núcleos, por lo que un núcleo puede leer desde su copia válida de una línea de caché mientras las actualizaciones provienen de otro caché.

    Intel utiliza MESIF , que requiere que los datos sucios se propaguen a la gran caché L3 inclusiva compartida que actúa como un respaldo para el tráfico de coherencia. L3 incluye etiquetas de cachés L2 / L1 por núcleo, incluso para líneas que tienen que estar en estado inválido en L3 debido a que son M o E en un caché L1 por núcleo. La ruta de datos entre L3 y cachés por núcleo es de solo 32 B de ancho en Haswell / Skylake, por lo que debe almacenarse en un búfer o algo para evitar que se escriba en L3 desde un núcleo entre lecturas de dos mitades de una línea de caché, lo que podría causar desgarros El límite 32B.

Las secciones relevantes de los manuales:

Los procesadores de la familia P6 (y los procesadores Intel más nuevos desde entonces) garantizan que la siguiente operación de memoria adicional siempre se realizará atómicamente:

  • Accesos no alineados de 16, 32 y 64 bits a la memoria caché que cabe dentro de una línea de caché.

Manual AMD64 7.3.2 Atomicidad de acceso
Las cargas individuales o almacenes en caché alineados de forma natural de hasta una palabra cuádruple son atómicos en cualquier modelo de procesador, al igual que las cargas o tiendas desalineadas de menos de una palabra cuádruple que se encuentran completamente dentro de una palabra cuádruple alineada naturalmente

Tenga en cuenta que AMD garantiza la atomicidad para cualquier carga más pequeña que una qword, pero Intel solo para tamaños de potencia de 2. El modo protegido de 32 bits y el modo largo de 64 bits pueden cargar un m16:32 48 bits como un operando de memoria en cs:eip con call jmp o jmp . (Y la llamada lejana empuja cosas en la pila). IDK si esto cuenta como un único acceso de 48 bits o separado de 16 y 32 bits.

Ha habido intentos de formalizar el modelo de memoria x86, el último es el documento x86-TSO (versión extendida) de 2009 (enlace de la sección de pedidos de memoria de la etiqueta wiki x86 ). No es útil skimable ya que definen algunos símbolos para expresar cosas en su propia notación, y no he intentado realmente leerlo. IDK si describe las reglas de atomicidad, o si solo se trata de ordenar la memoria.

Lectura-modificación-escritura atómica

Mencioné cmpxchg8b , pero solo estaba hablando de que la carga y la tienda por separado son atómicas (es decir, no hay "desgarro" donde la mitad de la carga es de una tienda, la otra mitad de la carga es de una tienda diferente).

Para evitar que el contenido de esa ubicación de memoria se modifique entre la carga y la tienda, necesita lock cmpxchg8b , al igual que necesita lock inc [mem] para que toda la lectura-modificación-escritura sea atómica. También tenga en cuenta que incluso si cmpxchg8b sin lock realiza una sola carga atómica (y opcionalmente una tienda), en general no es seguro usarlo como una carga de 64b con el valor esperado = deseado. Si el valor en la memoria coincide con el esperado, obtendrá una lectura-modificación-escritura no atómica de esa ubicación.

El prefijo de lock hace que incluso los accesos no alineados que cruzan la línea de caché o los límites de la página sean atómicos, pero no se puede usar con mov para crear una tienda no alineada o cargar atómica. Solo se puede usar con instrucciones de lectura-modificación-escritura de destino de memoria como add [mem], eax .

(el lock está implícito en xchg reg, [mem] , así que no use xchg con mem para guardar el tamaño del código o el recuento de instrucciones a menos que el rendimiento sea irrelevante. Úselo solo cuando desee la barrera de memoria y / o el intercambio atómico, o cuando el tamaño del código es lo único que importa, por ejemplo, en un sector de arranque).

Ver también: ¿Puede num ++ ser atómico para ''int num''?

Por qué lock mov [mem], reg no existe para tiendas atómicas no alineadas

Del manual de referencia de insn (Intel x86 manual vol2), cmpxchg :

Esta instrucción se puede usar con un prefijo LOCK para permitir que la instrucción se ejecute atómicamente. Para simplificar la interfaz con el bus del procesador, el operando de destino recibe un ciclo de escritura sin tener en cuenta el resultado de la comparación. El operando de destino se vuelve a escribir si la comparación falla; de lo contrario, el operando de origen se escribe en el destino. ( El procesador nunca produce una lectura bloqueada sin producir también una escritura bloqueada ).

Esta decisión de diseño redujo la complejidad del conjunto de chips antes de que el controlador de memoria se integrara en la CPU. Todavía puede hacerlo para instrucciones lock en regiones MMIO que llegan al bus PCI-express en lugar de DRAM. Sería confuso para un lock mov reg, [MMIO_PORT] producir una escritura y una lectura en el registro de E / S mapeado en memoria.

La otra explicación es que no es muy difícil asegurarse de que sus datos tengan una alineación natural, y lock store funcionaría horriblemente en comparación con solo asegurarse de que sus datos estén alineados. Sería una tontería gastar transistores en algo que sería tan lento que no valdría la pena usarlo. Si realmente lo necesita (y no le importa leer la memoria también), puede usar xchg [mem], reg (XCHG tiene un prefijo de BLOQUEO implícito), que es incluso más lento que un movimiento de lock mov hipotético.

El uso de un prefijo de lock también es una barrera de memoria completa, por lo que impone una sobrecarga de rendimiento más allá de solo el RMW atómico. es decir, x86 no puede hacer RMW atómica relajada (sin vaciar el búfer de la tienda). Otros ISA pueden, por lo que usar .fetch_add(1, memory_order_relaxed) puede ser más rápido en no x86.

Dato mfence : antes de que existiera mfence , un idioma común era lock add dword [esp], 0 , que no es una opción más que marcar banderas y hacer una operación bloqueada. [esp] casi siempre está activo en el caché L1 y no causará contención con ningún otro núcleo. Este idioma aún puede ser más eficiente que MFENCE como barrera de memoria independiente, especialmente en las CPU AMD.

xchg [mem], reg es probablemente la forma más eficiente de implementar un almacén de consistencia secuencial, en comparación con mov + mfence , tanto en Intel como en AMD. mfence en Skylake al menos bloquea la ejecución fuera de orden de instrucciones que no son de memoria, pero xchg y otras operaciones lock no lo hacen. Los compiladores que no sean gcc usan xchg para las tiendas, incluso cuando no les importa leer el valor anterior.

Motivación para esta decisión de diseño:

Sin él, el software tendría que usar bloqueos de 1 byte (o algún tipo de tipo atómico disponible) para proteger los accesos a enteros de 32 bits, lo cual es enormemente ineficiente en comparación con el acceso de lectura atómica compartida para algo como una variable de marca de tiempo global actualizada por una interrupción de temporizador . Probablemente es básicamente libre de silicio para garantizar accesos alineados de ancho de bus o menor.

Para que el bloqueo sea posible, se requiere algún tipo de acceso atómico. (En realidad, supongo que el hardware podría proporcionar algún tipo de mecanismo de bloqueo asistido por hardware totalmente diferente). Para una CPU que realiza transferencias de 32 bits en su bus de datos externo, tiene sentido que esa sea la unidad de atomicidad.

Dado que ofreció una recompensa, supongo que estaba buscando una respuesta larga que divagara en todos los temas secundarios interesantes. Avíseme si hay cosas que no cubrí que cree que harían más valiosas estas preguntas y respuestas para futuros lectores.

Dado que article , le recomiendo leer más publicaciones del blog de Jeff Preshing . Son excelentes y me ayudaron a reunir las piezas de lo que sabía para comprender el ordenamiento de la memoria en código fuente C / C ++ versus asm para diferentes arquitecturas de hardware, y cómo / cuándo decirle al compilador lo que quiere si no está t escribiendo asm directamente.