¿Es seguro leer más allá del final de un búfer dentro de la misma página en x86 y x64?
Muchos métodos que se encuentran en algoritmos de alto rendimiento podrían (y se simplifican) simplificarse si se les permitiera leer una pequeña cantidad más allá del final de los buffers de entrada. Aquí, "pequeña cantidad" generalmente significa hasta W - 1bytes después del final, donde Wes el tamaño de la palabra en bytes del algoritmo (por ejemplo, hasta 7 bytes para un algoritmo que procesa la entrada en fragmentos de 64 bits).
Está claro que escribir más allá del final de un búfer de entrada nunca es seguro, en general, ya que puede alterar datos más allá del búfer 1 . También está claro que leer más allá del final de un búfer en otra página puede desencadenar una violación de acceso/fallo de segmentación, ya que es posible que la página siguiente no sea legible.
Sin embargo, en el caso especial de leer valores alineados, un error de página parece imposible, al menos en x86. En esa plataforma, las páginas (y por lo tanto los indicadores de protección de memoria) tienen una granularidad de 4K (son posibles páginas más grandes, por ejemplo, 2MiB o 1GiB, pero son múltiplos de 4K) y, por lo tanto, las lecturas alineadas solo accederán a bytes en la misma página que la página válida. parte del buffer.
Aquí hay un ejemplo canónico de algún bucle que alinea su entrada y lee hasta 7 bytes después del final del búfer:
int processBytes(uint8_t *input, size_t size) {
uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size);
int res;
if (size < 8) {
// special case for short inputs that we aren't concerned with here
return shortMethod();
}
// check the first 8 bytes
if ((res = match(*input)) >= 0) {
return input + res;
}
// align pointer to the next 8-byte boundary
input64 = (ptrdiff_t)(input64 + 1) & ~0x7;
for (; input64 < end64; input64++) {
if ((res = match(*input64)) > 0) {
return input + res < input + size ? input + res : -1;
}
}
return -1;
}
La función interna int match(uint64_t bytes)no se muestra, pero es algo que busca un byte que coincida con un determinado patrón y devuelve la posición más baja (0-7) si se encuentra o -1 en caso contrario.
En primer lugar, los casos con tamaño < 8 se asignan a otra función para simplificar la exposición. Luego se realiza una única verificación para los primeros 8 (bytes no alineados). Luego se realiza un bucle para los floor((size - 7) / 8)fragmentos restantes de 8 bytes 2 . Este bucle puede leer hasta 7 bytes después del final del búfer (el caso de 7 bytes ocurre cuando input & 0xF == 1). Sin embargo, la llamada de devolución tiene una verificación que excluye cualquier coincidencia falsa que ocurra más allá del final del búfer.
En términos prácticos, ¿esa función es segura en x86 y x86-64?
Estos tipos de sobrelecturas son comunes en código de alto rendimiento. También es común un código de cola especial para evitar tales sobrelecturas . A veces ves que el último tipo reemplaza al primero para silenciar herramientas como valgrind. A veces se ve una propuesta para realizar un reemplazo de este tipo, que se rechaza con el argumento de que el idioma es seguro y la herramienta es errónea (o simplemente demasiado conservadora) 3 .
Una nota para los abogados lingüísticos:
La lectura desde un puntero más allá de su tamaño asignado definitivamente no está permitida en el estándar. Aprecio las respuestas de los abogados del lenguaje, e incluso ocasionalmente las escribo yo mismo, e incluso estaré feliz cuando alguien busque el capítulo y el versículo que muestra que el código anterior es un comportamiento indefinido y, por lo tanto, no es seguro en el sentido más estricto (y lo copiaré los detalles aquí). Sin embargo, en última instancia, eso no es lo que busco. Como cuestión práctica, muchos modismos comunes que implican conversión de punteros, acceso a estructuras a través de dichos punteros y, por lo tanto, no están definidos técnicamente, pero están muy extendidos en código de alta calidad y alto rendimiento. A menudo no hay alternativa, o la alternativa va a la mitad de velocidad o menos.
Si lo desea, considere una versión modificada de esta pregunta, que es:
Después de que el código anterior se haya compilado en el ensamblado x86/x86-64 y el usuario haya verificado que está compilado de la forma esperada (es decir, el compilador no ha utilizado un acceso demostrable parcialmente fuera de límites para hacer algo realmente inteligente , ¿es seguro ejecutar el programa compilado?
En ese sentido, esta pregunta es tanto una pregunta C como una pregunta de ensamblaje x86. La mayor parte del código que he visto que utiliza este truco está escrito en C, y C sigue siendo el lenguaje dominante para las bibliotecas de alto rendimiento, eclipsando fácilmente cosas de nivel inferior como asm y cosas de nivel superior como <todo lo demás>. Al menos fuera del nicho numérico incondicional donde FORTRAN todavía juega a la pelota. Así que estoy interesado en la vista del compilador C y a continuación de la pregunta, razón por la cual no la formulé como una pregunta de ensamblaje x86 pura.
Dicho todo esto, si bien solo estoy moderadamente interesado en un enlace al estándar que muestre que esto es UD, estoy muy interesado en cualquier detalle de las implementaciones reales que puedan usar este UD en particular para producir código inesperado. Ahora bien, no creo que esto pueda suceder sin un análisis profundo de los procedimientos cruzados, pero el desbordamiento de gcc también sorprendió a mucha gente...
1 Incluso en casos aparentemente inofensivos, por ejemplo, cuando se vuelve a escribir el mismo valor, puede romper el código concurrente .
2 Tenga en cuenta que para que esta superposición funcione es necesario que esta función y match()esta función se comporten de una manera idempotente específica, en particular que el valor de retorno admita comprobaciones superpuestas. Por lo tanto, "buscar el patrón de coincidencia del primer byte" funciona ya que todas las match()llamadas todavía están en orden. Sin embargo, un método de "contar bytes que coincidan con el patrón" no funcionaría, ya que algunos bytes podrían contarse dos veces. Además: algunas funciones como la llamada "devolver el byte mínimo" funcionarían incluso sin la restricción de orden, pero es necesario examinar todos los bytes.
3 Vale la pena señalar aquí que para Memcheck de valgrind hay un indicador que --partial-loads-okcontrola si dichas lecturas se informan realmente como un error. El valor predeterminado es sí , lo que significa que, en general, dichas cargas no se tratan como errores inmediatos, pero se hace un esfuerzo para rastrear el uso posterior de los bytes cargados, algunos de los cuales son válidos y otros no, y se marca un error. si se utilizan bytes fuera de rango . En casos como el ejemplo anterior, en el que se accede a la palabra completa en match(), dicho análisis concluirá que se accede a los bytes, aunque los resultados finalmente se descarten. En general, Valgrind no puede determinar si realmente se utilizan bytes no válidos de una carga parcial (y la detección en general es probablemente muy difícil).
Sí, es seguro en ensamblaje x86, y las implementaciones de libc existentes strlen(3)aprovechan esto en ensamblaje escrito a mano. E incluso el C alternativo de glibc , pero se compila sin LTO, por lo que nunca puede incorporarse. Básicamente se trata de utilizar C como un ensamblador portátil para crear código de máquina para una función, no como parte de un programa C más grande con inserción. Pero eso se debe principalmente a que también tiene un posible UB de alias estricto; consulte mi respuesta en las preguntas y respuestas vinculadas. Probablemente también desee un __attribute__((may_alias))typedef de GNU C en lugar de uno simple como el que ya usa unsigned longsu tipo más amplio, como etc.__m128i
Es seguro porque una carga alineada nunca cruzará un límite de alineación más alto y la protección de la memoria ocurre con páginas alineadas, por lo que al menos límites de 4k 1.
Cualquier carga alineada naturalmente que toque al menos 1 byte válido no puede fallar. También es seguro comprobar si estás lo suficientemente lejos del límite de la página siguiente para realizar una carga de 16 bytes, como if (p & 4095 > (4096 - 16)) do_special_case_fallback. Consulte la sección siguiente sobre eso para obtener más detalles.
Por lo general, también es seguro en C compilado para x86, hasta donde yo sé. Leer fuera de un objeto es, por supuesto, un comportamiento indefinido en C, pero funciona en C-targeting-x86. No creo que los compiladores definan explícitamente o deliberadamente el comportamiento, pero en la práctica funciona de esa manera.
Creo que no es el tipo de UB que los compiladores agresivos asumirán que no puede suceder durante la optimización , pero la confirmación de un compilador-escritor sobre este punto sería buena, especialmente para los casos en los que se puede demostrar fácilmente en tiempo de compilación que se interrumpe el acceso. de más allá del final de un objeto. (Vea la discusión en los comentarios con @RossRidge: una versión anterior de esta respuesta afirmaba que era absolutamente seguro, pero esa publicación del blog de LLVM realmente no se lee de esa manera).
Esto es necesario en ASM para ir más rápido que 1 byte a la vez al procesar una cadena de longitud implícita. En teoría, en C, un compilador podría saber cómo optimizar dicho bucle, pero en la práctica no es así, por lo que hay que hacer trucos como este. Hasta que eso cambie, sospecho que los compiladores que le interesan a la gente generalmente evitarán descifrar el código que contiene este UB potencial.
No hay peligro cuando la lectura excesiva no es visible para el código que sabe cuánto mide un objeto. Un compilador tiene que crear un conjunto que funcione para el caso en el que hay elementos de matriz hasta donde realmente leemos. El peligro plausible que puedo ver con posibles compiladores futuros es: después de la inserción, un compilador podría ver la UB y decidir que nunca se debe tomar esta ruta de ejecución. O que la condición de terminación debe encontrarse antes del vector final no completo y omitirlo cuando se desenrolle por completo.
Los datos que obtiene son basura impredecible, pero no habrá otros posibles efectos secundarios. Mientras su programa no se vea afectado por los bytes basura, está bien. (por ejemplo, use bithacks para encontrar si uno de los bytes de a uint64_tes cero , luego un bucle de bytes para encontrar el primer byte cero, independientemente de qué basura haya más allá).
Situaciones inusuales en las que esto no sería seguro en x86 asm
Puntos de interrupción de datos de hardware (puntos de vigilancia) que se activan con una carga desde una dirección determinada. Si hay una variable que estás monitoreando justo después de una matriz, podrías obtener un resultado falso. Esto podría ser una molestia menor para alguien que esté depurando un programa normal. Si su función será parte de un programa que utiliza registros de depuración x86 D0-D3 y las excepciones resultantes para algo que podría afectar la corrección, entonces tenga cuidado con esto.
O de manera similar, un verificador de código como valgrind podría quejarse de leer fuera de un objeto.
En un sistema operativo hipotético de 16 o 32 bits, esto podría usar segmentación: un límite de segmento puede usar una granularidad de 4k o 1 byte , por lo que es posible crear un segmento donde el primer desplazamiento de falla sea impar. (Tener la base del segmento alineada con una línea o página de caché es irrelevante, excepto para el rendimiento). Todos los sistemas operativos x86 convencionales utilizan modelos de memoria plana y x86-64 elimina la compatibilidad con límites de segmento para el modo de 64 bits.
Los registros de E/S asignados en memoria justo después del búfer que deseaba recorrer con cargas amplias, especialmente la misma línea de caché de 64 B. Esto es extremadamente improbable incluso si llama a funciones como esta desde un controlador de dispositivo (o un programa de espacio de usuario como un servidor X que ha asignado algo de espacio MMIO).
Si está procesando un búfer de 60 bytes y necesita evitar la lectura de un registro MMIO de 4 bytes, lo sabrá y utilizará un archivo volatile T*. Este tipo de situación no ocurre con el código normal.
strlenes el ejemplo canónico de un bucle que procesa un búfer de longitud implícita y, por lo tanto, no puede vectorizar sin leer más allá del final de un búfer. Si necesita evitar leer más allá del 0byte de terminación, solo puede leer un byte a la vez.
Por ejemplo, la implementación de glibc utiliza un prólogo para manejar datos hasta el primer límite de alineación 64B. Luego, en el bucle principal (enlace de gitweb a la fuente de asm) , carga una línea de caché de 64B completa utilizando cuatro cargas alineadas con SSE2. Los fusiona en un vector con pminub(mínimo de bytes sin signo), por lo que el vector final tendrá un elemento cero solo si alguno de los cuatro vectores tuviera un cero. Después de encontrar que el final de la cadena estaba en algún lugar de esa línea de caché, vuelve a verificar cada uno de los cuatro vectores por separado para ver dónde. (Usando lo típico pcmpeqbcontra un vector de todo cero y pmovmskb/ bsfpara encontrar la posición dentro del vector). glibc solía tener un par de estrategias strlen diferentes para elegir , pero la actual es buena en todas las CPU x86-64.
Por lo general, bucles como este evitan tocar líneas de caché adicionales que no necesitan tocar, no solo páginas, por razones de rendimiento, como strlen de glibc.
Por supuesto, cargar 64B a la vez solo es seguro desde un puntero alineado con 64B, ya que los accesos alineados naturalmente no pueden cruzar los límites de la línea de caché o de la línea de página .
Si conoce la longitud de un búfer de antemano, puede evitar leer más allá del final manejando los bytes más allá del último vector completamente alineado usando una carga no alineada que finaliza en el último byte del búfer.
(Nuevamente, esto solo funciona con algoritmos idempotentes, como memcpy, a los que no les importa si se superponen en el destino. Los algoritmos de modificación in situ a menudo no pueden hacer esto, excepto con algo como convertir una cadena a formato superior). (caso con SSE2 , donde está bien reprocesar datos que ya se han actualizado. Aparte del puesto de reenvío de tienda si realiza una carga no alineada que se superpone con su última tienda alineada).
Entonces, si está vectorizando sobre un búfer de longitud conocida, de todos modos es mejor evitar la lectura excesiva.
La sobrelectura sin errores de un objeto es el tipo de UB que definitivamente no hace daño si el compilador no puede verlo en el momento de la compilación. El conjunto resultante funcionará como si los bytes adicionales fueran parte de algún objeto.
Pero incluso si es visible en tiempo de compilación, generalmente no hace daño a los compiladores actuales.
PD: una versión anterior de esta respuesta afirmaba que el deref no alineado int *también era seguro en C compilado para x86. Eso no es verdad . Fui demasiado arrogante hace 3 años al escribir esa parte. Necesita un typedef con GNU C __attribute__((aligned(1),may_alias))o memcpypara que sea seguro. La may_aliasparte no es necesaria si sólo accede a ella a través de firmado/sin firmar int*y/o `char*, es decir, de manera que no viole las reglas normales de alias estricto de C.
El conjunto de cosas que ISO C deja sin definir, pero que los intrínsecos de Intel requieren que los compiladores definan, incluye la creación de punteros no alineados (al menos con tipos como __m128i*), pero no desreferenciarlos directamente. ¿Es `reinterpret_cast`ing entre el puntero vectorial SIMD de hardware y el tipo correspondiente un comportamiento indefinido?
Comprobar si un puntero está lo suficientemente lejos del final de una página de 4k
Esto es útil para el primer vector de strlen; después de esto puedes p = (p+16) & -16ir al siguiente vector alineado. Esto se superpondrá parcialmente si pno está alineado con 16 bytes, pero realizar trabajo redundante es a veces la forma más compacta de configurar un bucle eficiente. Evitarlo podría significar realizar un bucle de 1 byte a la vez hasta un límite de alineación, y eso es ciertamente peor.
por ejemplo, verifique ((p + 15) ^ p) & 0xFFF...F000 == 0(LEA / XOR / TEST) que le indica que el último byte de una carga de 16 bytes tiene los mismos bits de dirección de página que el primer byte. O p+15 <= p|0xFFF(LEA / OR / CMP con mejor ILP) verifica que la dirección del último byte de la carga sea <= el último byte de la página que contiene el primer byte.
O más simplemente, p & 4095 > (4096 - 16)(MOV/AND/CMP), es decir, p & (pgsize-1) < (pgsize - vecwidth)comprueba que el desplazamiento dentro de la página esté lo suficientemente lejos del final de una página.
Puede usar un tamaño de operando de 32 bits para guardar el tamaño del código (prefijos REX) para esta o cualquiera de las otras comprobaciones porque los bits altos no importan. Algunos compiladores no notan esta optimización, por lo que puedes transmitir a unsigned inten lugar de uintptr_t, aunque para silenciar las advertencias sobre el código que no está limpio en 64 bits es posible que necesites transmitir (unsigned)(uintptr_t)p. Se puede ahorrar más tamaño de código con ((unsigned int)p << 20) > ((4096 - vectorlen) << 20)(MOV/SHL/CMP), porque shl reg, 20son 3 bytes, frente and eax, imm32a 5 o 6 para cualquier otro registro. (El uso de EAX también permitirá la forma abreviada sin modrm para cmp eax, 0xfff.)
Si hace esto en GNU C, probablemente quiera typedef unsigned long aliasing_unaligned_ulong __attribute__((aligned(1),may_alias));que sea seguro realizar accesos no alineados.
Si permite la consideración de dispositivos que no son CPU, entonces un ejemplo de operación potencialmente insegura es acceder a regiones fuera de los límites de páginas de memoria asignadas por PCI . No hay garantía de que el dispositivo de destino esté utilizando el mismo tamaño de página o alineación que el subsistema de memoria principal. Intentar acceder, por ejemplo, a la dirección [cpu page base]+0x800puede provocar un error de página del dispositivo si el dispositivo está en modo de página de 2 KB. Esto normalmente provocará una comprobación de errores del sistema.
