assembly - tener - procesadores de 64 bits

¿Cómo puedo escribir el código de auto modificación que se ejecuta de manera eficiente en los procesadores x64 modernos?

Question

Estoy tratando de acelerar un esquema de compresión de enteros de ancho de bits variable y estoy interesado en generar y ejecutar código ensamblador sobre la marcha. Actualmente, se gasta mucho tiempo en ramas indirectas mal definidas, y generar código basado en la serie de anchos de bits que se encuentran parece ser la única manera de evitar esta penalización.

La técnica general se conoce como "subprocesamiento de subrutinas" (o "subprocesamiento de llamadas", aunque esto también tiene otras definiciones). El objetivo es aprovechar la predicción de call / ret eficiente de los procesadores para evitar puestos. El enfoque está bien descrito aquí: http://webdocs.cs.ualberta.ca/~amaral/cascon/CDP05/slides/CDP05-berndl.pdf

El código generado será simplemente una serie de llamadas seguidas de una devolución. Si hubiera 5 ''trozos'' de anchuras [4,8,8,4,16], se vería así:

call $decode_4
call $decode_8
call $decode_8
call $decode_4
call $decode_16
ret

En el uso real, será una serie más larga de llamadas, con una longitud suficiente para que cada serie sea única y solo se llame una vez. Generar y llamar al código está bien documentado, tanto aquí como en otros lugares. Pero no he encontrado mucha discusión sobre la eficiencia más allá de un simple "no lo hagas" o un bien considerado "hay dragones". Incluso la documentación de Intel habla principalmente en generalidades:

8.1.3 Tratamiento del código de auto modificación y modificación cruzada

El acto de un procesador que escribe datos en un segmento de código que se está ejecutando actualmente con la intención de ejecutar esos datos como código se llama código de auto modificación. Los procesadores IA-32 muestran un comportamiento específico del modelo al ejecutar el código auto modificado, dependiendo de qué tan avanzado el puntero de ejecución actual se haya modificado el código. ... El código de auto-modificación se ejecutará a un nivel de rendimiento inferior al que no se auto-modifica o código normal. El grado de deterioro del rendimiento dependerá de la frecuencia de la modificación y las características específicas del código.

11.6 CÓDIGO DE AUTO MODIFICACIÓN

Una escritura en una ubicación de memoria en un segmento de código que está actualmente almacenado en la memoria caché en el procesador causa la invalidación de la línea (o líneas) de la memoria caché asociada. Esta verificación se basa en la dirección física de la instrucción. Además, la familia P6 y los procesadores Pentium verifican si una escritura en un segmento de código puede modificar una instrucción que se ha captado previamente para su ejecución. Si la escritura afecta a una instrucción extraída previamente, la cola de captación previa se invalida. Esta última comprobación se basa en la dirección lineal de la instrucción. Para los procesadores Pentium 4 e Intel Xeon, una escritura o un rastreo de una instrucción en un segmento de código, donde la instrucción objetivo ya está decodificada y residente en el caché de seguimiento, invalida todo el caché de seguimiento. El último comportamiento significa que los programas que auto-modifican el código pueden causar una grave degradación del rendimiento cuando se ejecutan en los procesadores Pentium 4 e Intel Xeon.

Si bien hay un contador de rendimiento para determinar si están sucediendo cosas malas (C3 04 MACHINE_CLEARS.SMC: Número de autorreguladores de códigos de máquina detectados ) Me gustaría saber más detalles, especialmente para Haswell. Mi impresión es que siempre que pueda escribir el código generado con la suficiente anticipación como para que la captación previa de instrucciones no haya llegado aún, y siempre que no active el detector SMC modificando el código en la misma página (cuatrimestr. página?) como algo que se está ejecutando actualmente, entonces debería obtener un buen rendimiento. Pero todos los detalles parecen extremadamente vagos: ¿qué tan cerca está demasiado cerca? ¿Qué tan lejos es lo suficientemente lejos?

Tratando de convertir esto en preguntas específicas:

1. ¿Cuál es la distancia máxima por delante de la instrucción actual que el prefetcher Haswell alguna vez ejecuta?

2. ¿Cuál es la distancia máxima detrás de la instrucción actual que podría contener el "caché de rastreo" de Haswell?

3. ¿Cuál es la penalización real en ciclos para un evento MACHINE_CLEARS.SMC en Haswell?

4. ¿Cómo puedo ejecutar el ciclo de generación / ejecución en un ciclo predicho mientras evito que el recolector se coma su propia cola?

5. ¿Cómo puedo organizar el flujo para que cada parte del código generado siempre se vea "por primera vez" y no pisar las instrucciones ya almacenadas en la memoria caché?

Answer 1

Muy buena pregunta, pero la respuesta no es tan fácil ... Probablemente la última palabra sea para el experimento, caso común en el mundo moderno de diferentes arquitecturas.

De todos modos, lo que quieres hacer no es exactamente código de auto modificación. Los procedimientos "decode_x" existirán y no se modificarán. Por lo tanto, no debería haber problemas con la memoria caché.

Por otro lado, la memoria asignada para el código generado, probablemente será asignada dinámicamente desde el montón, por lo tanto, las direcciones estarán lo suficientemente lejos del código ejecutable del programa. Puede asignar un nuevo bloque cada vez que necesite generar una nueva secuencia de llamadas.

¿Qué tan lejos es suficiente? Creo que esto no es tan lejos. La distancia debería ser probablemente una multiplicación de la línea de caché del procesador y de esta manera, no tan grande. Tengo algo así como 64bytes (para L1). En el caso de memoria asignada dinámicamente tendrá muchas páginas de distancia.

El principal problema en este enfoque IMO es que el código de los procedimientos generados se ejecutará solo una vez. De esta manera, el programa perderá el avance principal del modelo de memoria en caché - ejecución eficiente del código de ciclismo.

Y al final, el experimento no parece tan difícil de realizar. Simplemente escriba algún programa de prueba en ambas variantes y mida el rendimiento. Y si publica estos resultados, los leeré detenidamente. :)

Answer 2

Esto está menos en el alcance de SMC y más en la optimización binaria dinámica, es decir, no manipulas realmente el código que estás ejecutando (como cuando escribes nuevas instrucciones), puedes generar un código diferente y redireccionar el código. llamada apropiada en su código para saltar allí en su lugar. La única modificación es en el punto de entrada, y solo se realiza una vez, por lo que no es necesario preocuparse demasiado por la sobrecarga (por lo general, significa enjuagar todas las tuberías para asegurarse de que la instrucción anterior no esté todavía viva en ningún lugar del máquina, supongo que la penalización es de unos cientos de ciclos de reloj, dependiendo de qué tan cargada esté la CPU. Solo relevante si ocurre repetidamente).

En el mismo sentido, no debe preocuparse demasiado por hacer esto con la suficiente antelación. Por cierto, con respecto a su pregunta, la CPU solo podría comenzar a ejecutar adelante en cuanto a su tamaño ROB, que en realidad es 192 uop (no instrucciones, pero lo suficientemente cerca), de acuerdo con esto - http: //www.realworldtech .com / haswell-cpu / 3 / , y sería capaz de ver un poco más adelante gracias a las unidades de predicción y recuperación, por lo que estamos hablando de un total de unos cientos).

Habiendo dicho eso, permítanme reiterar lo que se dijo aquí antes: experimentar, experimentar experimento :)

Answer 3

Esto no tiene que ser código de auto modificación, en su lugar puede ser código creado dinámicamente , es decir, "trampolines" generados en el tiempo de ejecución.

Lo que significa que mantiene un puntero de función (global) que redireccionará a una sección mapeada de escritura / ejecutable de la memoria, en la que luego inserta activamente las llamadas de función que desea realizar.

La principal dificultad con esto es que la call es relativa a IP (como la mayoría de jmp ), por lo que tendrás que calcular el desplazamiento entre la ubicación de la memoria de tu trampolín y los "funcs objetivo". Que como tal es bastante simple, pero combínelo con un código de 64 bits, y se encuentra con el desplazamiento relativo de que la call solo puede tratar con desplazamientos en el rango de + -2GB, se vuelve más compleja, necesita llamar a través de un enlace mesa.

Así que esencialmente crearías código como (/ me severamente UN * X sesgado, por lo tanto, ensamblado de AT & T, y algunas referencias a ELF-ismos):

.Lstart_of_modifyable_section:
callq 0f
callq 1f
callq 2f
callq 3f
callq 4f
....
ret
.align 32
0:        jmpq tgt0
.align 32
1:        jmpq tgt1
.align 32
2:        jmpq tgt2
.align 32
3:        jmpq tgt3
.align 32
4:        jmpq tgt4
.align 32
...

Esto se puede crear en tiempo de compilación (solo hacer una sección de texto modificable), o dinámicamente en tiempo de ejecución.

Luego, en tiempo de ejecución, parche los objetivos de salto . Es similar a cómo funciona la sección .plt ELF (PLT = tabla de vinculación de procedimientos), solo que allí, es el enlazador dinámico el que correlaciona las ranuras jmp, mientras que en su caso, usted mismo lo hace.

Si utiliza todo el tiempo de ejecución, la tabla como la anterior se puede crear fácilmente a través de C / C ++ incluso; Comience con una estructura de datos como:

typedef struct call_tbl_entry __attribute__(("packed")) {
    uint8_t call_opcode;
    int32_t call_displacement;
};
typedef union jmp_tbl_entry_t {
    uint8_t cacheline[32];
    struct {
        uint8_t jmp_opcode[2];    // 64bit absolute jump
        uint64_t jmp_tgtaddress;
    } tbl __attribute__(("packed"));
}

struct mytbl {
    struct call_tbl_entry calltbl[NUM_CALL_SLOTS];
    uint8_t ret_opcode;
    union jmp_tbl_entry jmptbl[NUM_CALL_SLOTS];
}

La única cosa crítica y algo dependiente del sistema aquí es la naturaleza "empaquetada" de esto que uno necesita contarle al compilador (es decir, no rellenar la matriz de call ), y que debe alinear la alineación de la tabla de salto.

Necesita hacer calltbl[i].call_displacement = (int32_t)(&jmptbl[i]-&calltbl[i+1]) , inicializar la tabla de salto vacía / no utilizada con memset(&jmptbl, 0xC3 /* RET */, sizeof(jmptbl)) y luego simplemente complete los campos con el código de operación de salto y la dirección de destino que necesite.

Answer 4

Encontré una mejor documentación de Intel y este parecía ser el mejor lugar para ponerlo en referencia futura:

Software should avoid writing to a code page in the same 1-KByte
subpage that is being executed or fetching code in the same 2-KByte
subpage of that is being written.

Manual de referencia de optimización de arquitecturas Intel® 64 e IA-32

Es solo una respuesta parcial a las preguntas (prueba, prueba, prueba) pero con números más firmes que las otras fuentes que había encontrado.

3.6.9 Código de mezcla y datos.

El código de auto-modificación funciona correctamente, de acuerdo con los requisitos del procesador de arquitectura Intel, pero incurre en una importante penalización de rendimiento. Evite el código de auto modificación si es posible. • Colocar datos escribibles en el segmento de código podría ser imposible de distinguir del código de modificación automática. Los datos que se pueden escribir en el segmento de código pueden sufrir la misma penalización de rendimiento que el código de auto modificación.

Regla de ensamblaje / compilación 57. (M impacto, generalidad L) Si los datos (con suerte de solo lectura) deben aparecer en la misma página que el código, evite colocarlos inmediatamente después de un salto indirecto. Por ejemplo, siga un salto indirecto con su objetivo más probable, y coloque los datos después de una rama incondicional. Sugerencia de ajuste 1. En casos poco frecuentes, un problema de rendimiento puede deberse a la ejecución de datos en una página de códigos como instrucciones. Es muy probable que esto suceda cuando la ejecución sigue a una rama indirecta que no reside en la memoria caché de seguimiento. Si esto está causando claramente un problema de rendimiento, intente mover los datos a otra parte, o inserte un código de operación ilegal o una instrucción PAUSE inmediatamente después de la rama indirecta. Tenga en cuenta que las dos últimas alternativas pueden degradar el rendimiento en algunas circunstancias.

Ensamblaje / Compilación Codificación Regla 58. (Impacto H, generalidad L) Coloque siempre el código y los datos en páginas separadas. Evite el código de auto modificación siempre que sea posible. Si se va a modificar el código, intente hacerlo todo de una vez y asegúrese de que el código que realiza las modificaciones y el código que se está modificando se encuentren en páginas separadas de 4 KByte o en subpáginas separadas de 1 KByte.

3.6.9.1 Código de modificación automática.

El código de auto-modificación (SMC) que se ejecutó correctamente en los procesadores Pentium III y las implementaciones anteriores se ejecutará correctamente en las implementaciones posteriores. SMC y el código de modificación cruzada (cuando múltiples procesadores en un sistema multiprocesador están escribiendo en una página de códigos) deben evitarse cuando se desea un alto rendimiento.

El software debe evitar escribir en una página de códigos en la misma subpágina de 1 KByte que se está ejecutando o buscar código en la misma subpágina de 2 KByte que se está escribiendo. Además, compartir una página que contiene código ejecutado directa o especulativamente con otro procesador como una página de datos puede desencadenar una condición SMC que causa que toda la interconexión de la máquina y la memoria caché de rastreo se borren. Esto se debe a la condición de código de auto modificación. El código dinámico no necesita causar la condición SMC si el código escrito llena una página de datos antes de acceder a esa página como código.

El código modificado dinámicamente (por ejemplo, de las reparaciones de destino) es probable que sufra la condición de SMC y se debe evitar siempre que sea posible. Evite la condición introduciendo ramas indirectas y usando tablas de datos en páginas de datos (no páginas de códigos) usando llamadas de registro indirecto.