c - sistema - ¿Es seguro leer más allá del final de un búfer dentro de la misma página en x86 y x64?
sistemas operativos de 32 y 64 bits (2)
Sí, es seguro en x86 asm, y las strlen(3) libc strlen(3) se aprovechan de esto.
También es seguro en C compilado para x86, hasta donde yo sé. La lectura fuera de un objeto es, por supuesto, un comportamiento indefinido en C, pero está bien definido para C-targeting-x86. Creo que no es el tipo de UB que los compiladores agresivos supondrán que no puede suceder mientras se optimiza , pero la confirmación de un compilador y escritor en este punto sería buena, especialmente para casos en los que es fácilmente comprobable en tiempo de compilación que se cierra un acceso de más allá del final de un objeto. (Ver discusión en comentarios con @RossRidge: una versión anterior de esta respuesta afirmaba que era absolutamente seguro, pero esa publicación de blog de LLVM realmente no se lee de esa manera).
Los datos que obtienes son basura impredecible, pero no habrá ningún otro efecto secundario potencial. Mientras que su programa no se vea afectado por los bytes basura, está bien. (por ejemplo, use bithacks para encontrar si uno de los bytes de uint64_t es cero , luego un bucle de bytes para encontrar el primer byte cero, independientemente de qué basura esté más allá).
Del mismo modo, la creación de punteros desalineados con un molde es UB en el estándar C (incluso si no los desreferencia). Está bien definido en todos los compiladores de C conocidos cuando se dirige a x86. Los intrínsecos de SSE de Intel incluso lo requieren; por ejemplo, __m128i _mm_loadu_si128 (__m128i const* mem_addr) toma un puntero a un __m128i de 16 bytes __m128i .
(Para AVX512, finalmente cambiaron esa opción de diseño inconveniente por void* para nuevas intrínsecas como __m512i _mm512_loadu_si512 (void const* mem_addr) ).
Incluso desreferenciar un uint64_t* no uint64_t* o int* es seguro (y tiene un comportamiento bien definido) en C compilado para x86. Sin embargo, la __m128i* directa de un __m128i* directamente (en lugar de usar los intrínsecos de carga / almacenamiento) usará movdqa , que falla en los punteros desalineados.
Por lo general, los bucles como este evitan tocar cualquier línea de caché adicional que no necesiten tocar, no solo las páginas, por razones de rendimiento.
Es extremadamente improbable que haya registros de E / S mapeados en memoria en la misma página que un búfer en el que deseaba realizar bucles con cargas anchas, o especialmente la misma línea de caché 64B, incluso si está llamando a funciones como esta desde un controlador de dispositivo (o un programa de espacio de usuario como un servidor X que ha mapeado un poco de espacio MMIO).
Si está procesando un búfer de 60 bytes y necesita evitar leer desde un registro MMIO de 4 bytes, lo sabrá. Este tipo de situación no ocurre para el código normal.
strlen es 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 0 byte de terminación, solo puede leer un byte a la vez.
Por ejemplo, la implementación de glibc usa un prólogo para manejar datos hasta el primer límite de alineación de 64B. Luego, en el bucle principal (enlace gitweb a la fuente asm) , carga una línea de memoria caché completa de 64 B con cuatro cargas alineadas SSE2. Los combina con 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 tiene 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 el pcmpeqb típico contra un vector de todo-cero, y pmovmskb / bsf para encontrar la posición dentro del vector.) Glibc solía tener un par de estrategias de strings diferentes para elegir , pero el actual es bueno en todos los x86-64 CPUs
Cargar 64B a la vez es, por supuesto, solo seguro desde un puntero alineado con 64B, ya que los accesos naturalmente alineados no pueden cruzar los límites de la línea de caché o de la línea de la 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 alineado utilizando una carga desalineada que termina en el último byte del búfer. (De nuevo, esto solo funciona con algoritmos idempotentes, como memcpy, a los que no les importa si superponen tiendas en el destino. Los algoritmos de modificación en el lugar a menudo no pueden hacer esto, excepto con algo como convertir una cadena en superior caso con SSE2 , donde está bien reprocesar los datos que ya se han subido. Aparte del puesto de reenvío de tiendas si realiza una carga no alineada que se superpone con su última tienda alineada).
Muchos métodos encontrados en algoritmos de alto rendimiento podrían (y se) simplificar si se les permitiera leer una pequeña cantidad después del final de los buffers de entrada. Aquí, "pequeña cantidad" generalmente significa hasta W - 1 bytes más allá del final, donde W es el tamaño de 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 destruir 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 falla de segmentación / violación de acceso, ya que la página siguiente puede no ser legible.
En el caso especial de lectura de valores alineados, sin embargo, un error de página parece imposible, al menos en x86. En esa plataforma, las páginas (y por lo tanto las banderas de protección de memoria) tienen una granularidad 4K (páginas más grandes, por ejemplo 2MiB o 1GiB, pero son múltiplos de 4K) y las lecturas alineadas solo accederán a los bytes en la misma página que la válida parte del buffer
Aquí hay un ejemplo canónico de algún bucle que alinea su entrada y lee hasta 7 bytes más allá 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 comprobación para los primeros 8 (bytes no alineados). Luego se realiza un ciclo para el resto del floor((size - 7) / 8) fragmentos de 8 bytes 2 . Este ciclo puede leer hasta 7 bytes más allá del final del búfer (el caso de 7 bytes ocurre cuando input & 0xF == 1 ). Sin embargo, la devolución de llamada tiene una comprobación que excluye cualquier coincidencia espuria que se produzca más allá del final del búfer.
Hablando en términos prácticos, ¿es segura esa función en x86 y x86-64?
Estos tipos de sobrecargas son comunes en el código de alto rendimiento. Código de cola especial para evitar tales sobrecargas también es común. Algunas veces ves que el último tipo reemplaza al anterior para silenciar herramientas como valgrind. A veces ve una propuesta para hacer un reemplazo de este tipo, que se rechaza con el argumento de que la expresión idiomática es segura y la herramienta está equivocada (o simplemente es demasiado conservadora) 3 .
Una nota para abogados de idiomas:
La lectura desde un puntero más allá de su tamaño asignado definitivamente no está permitida en el estándar. Agradezco las respuestas de los abogados de idiomas, e incluso las escribo ocasionalmente, e incluso seré feliz cuando alguien desentierra 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 estricto (y copiaré los detalles aquí). A fin de cuentas, eso no es lo que busco. Como cuestión práctica, muchos lenguajes comunes que implican conversión de puntero, estructuran el acceso a través de tales punteros y, por lo tanto, están técnicamente indefinidos, pero están muy extendidos en código de alta calidad y alto rendimiento. A menudo no hay alternativa, o la alternativa funciona a media 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 para el ensamblaje x86 / x86-64, y el usuario haya verificado que se compila de la manera esperada (es decir, el compilador no ha utilizado un acceso comprobable parcialmente fuera de límites para hacer algo realmente inteligente , está ejecutando el programa compilado seguro?
En ese sentido, esta pregunta es tanto una pregunta C como una pregunta de ensamblaje x86. La mayor parte del código que usa este truco que he visto está escrito en C, y C sigue siendo el idioma dominante para las bibliotecas de alto rendimiento, eclipsa fácilmente las de nivel inferior como asm y las de nivel superior como <todo lo demás>. Al menos fuera del nicho numérico hardcore donde FORTRAN aún juega a la pelota. Así que estoy interesado en la vista de compilación de C-y-abajo de la pregunta, que es la razón por la que no lo formulé como una pregunta de ensamblaje de x86 puro.
Dicho todo esto, aunque estoy moderadamente interesado en un enlace al estándar que muestra que se trata de UD, estoy muy interesado en los detalles de las implementaciones reales que pueden usar este UD en particular para producir código inesperado. Ahora no creo que esto pueda suceder sin un profundo análisis profundo de procedimientos cruzados, pero el exceso de gcc sorprendió a mucha gente también ...
1 Incluso en casos aparentemente inofensivos, por ejemplo, cuando se escribe el mismo valor, puede romper el código concurrente .
2 La nota para que esta superposición funcione requiere que esta función y la función match() comporten de una manera idempotente específica, en particular, que el valor de retorno admite comprobaciones superpuestas. Por lo tanto, funciona un "patrón de buscar primer byte coincidente" ya que todas las llamadas de match() todavía están en orden. Sin embargo, un método de "conteo de bytes de coincidencia" no funcionaría, ya que algunos bytes podrían contarse doblemente. Como comentario adicional: algunas funciones, como la llamada "devolver el byte mínimo", funcionarían incluso sin la restricción en orden, pero es necesario examinar todos los bytes.
3 Vale la pena señalar aquí que para el Memcheck de Valgrind hay un indicador , --partial-loads-ok que controla si dichas lecturas se informan como un error. El valor predeterminado es sí , significa que, en general, tales cargas no se tratan como errores inmediatos, pero que se realiza un esfuerzo para rastrear el uso posterior de bytes cargados, algunos de los cuales son válidos y otros no, con un error marcado si se utilizan los 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 descartan. En general, Valgrind no puede determinar si los bytes inválidos de una carga parcial realmente se usan (y la detección en general es probablemente muy difícil).
Si permite la consideración de dispositivos que no son de la CPU, entonces un ejemplo de una operación potencialmente insegura es acceder a las regiones fuera de límites de las páginas de memoria mapeadas 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]+0x800 puede desencadenar un error de la página del dispositivo si el dispositivo está en un modo de página de 2 KB. Esto generalmente causará una comprobación de errores del sistema.