Comportamiento indefinido y verdad no definida

El término "comportamiento indefinido" en el lenguaje C y C ++ designa una situación en la que literalmente "lo que simplemente no sucede". Históricamente, los casos en que los compiladores anteriores para C (y las arquitecturas en él) se comportaron de manera incompatible se atribuyeron al comportamiento indefinido, y el comité para desarrollar el estándar, en su sabiduría ilimitada, decidió no decidir nada al respecto (es decir, no dar preferencia alguna de las implementaciones de la competencia). El comportamiento indefinido también se denominó situaciones posibles en las que el estándar, generalmente tan exhaustivo, no prescribía ningún comportamiento específico. Este término tiene un tercer significado, que en nuestro tiempo se está volviendo cada vez más relevante: comportamiento indefinido: esta es la oportunidad de optimización. Y los desarrolladores en C y C ++ adoran las optimizaciones; insistentemente requieren que los compiladores hagan todo lo posible para acelerar el código.

Este artículo se publicó por primera vez en el sitio web de Cryptography Services. La traducción se publica con el permiso del autor Thomas Pornin.

Aquí hay un ejemplo clásico:

void foo(double *src, int *dst) { int i; for (i = 0; i < 4; i ++) { dst[i] = (int)src[i]; } } 

Compilaremos este código GCC en una plataforma x86 de 64 bits para Linux (trabajo en la última versión de Ubuntu 18.04, versión GCC - 7.3.0). Activamos la optimización completa y luego miramos la lista de ensambladores, para la cual usamos las teclas "-W -Wall -O9 -S " (el argumento " -O9 " establece el nivel máximo de optimización de GCC, que en la práctica es equivalente a " -O3 ", aunque en algunas bifurcaciones) CCG definido y niveles superiores). Obtenemos el siguiente resultado:

  .file "zap.c" .text .p2align 4,,15 .globl foo .type foo, @function foo: .LFB0: .cfi_startproc movupd (%rdi), %xmm0 movupd 16(%rdi), %xmm1 cvttpd2dq %xmm0, %xmm0 cvttpd2dq %xmm1, %xmm1 punpcklqdq %xmm1, %xmm0 movups %xmm0, (%rsi) ret .cfi_endproc .LFE0: .size foo, .-foo .ident "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0" .section .note.GNU-stack,"",@progbits 

Cada una de las dos primeras instrucciones movupd mueve dos valores dobles al registro SSE2 de 128 bits (el doble tiene un tamaño de 64 bits, por lo que el registro SSE2 puede almacenar dos valores dobles ). En otras palabras, cuatro valores iniciales se leen primero, y solo luego se convierten a int (operación cvttpd2dq ). La operación punpcklqdq mueve los cuatro enteros de 32 bits recibidos en un registro SSE2 (% xmm0 ), cuyo contenido se escribe en RAM ( movups ). Y ahora lo principal: nuestro programa C requiere formalmente que el acceso a la memoria ocurra en el siguiente orden:

• Lea el primer valor doble de src [0] .
• Escriba el primer valor de tipo int en dst [0] .
• Lea el segundo valor doble de src [1] .
• Escriba el segundo valor de tipo int a dst [1] .
• Lea el tercer valor doble de src [2] .
• Escriba el tercer valor de tipo int a dst [2] .
• Lea el cuarto valor doble de src [3] .
• Escriba el cuarto valor de tipo int a dst [3] .

Sin embargo, todos estos requisitos tienen sentido solo en el contexto de una máquina abstracta, que define el estándar C; El procedimiento en una máquina real puede variar. El compilador es libre de reorganizar o modificar operaciones, siempre que su resultado no contradiga la semántica de la máquina abstracta (la llamada regla as-if es "como si"). En nuestro ejemplo, el orden de acción es simplemente diferente:

• Lea el primer valor doble de src [0] .
• Lea el segundo valor doble de src [1] .
• Lea el tercer valor doble de src [2] .
• Lea el cuarto valor doble de src [3] .
• Escriba el primer valor de tipo int en dst [0] .
• Escriba el segundo valor de tipo int a dst [1] .
• Escriba el tercer valor de tipo int a dst [2] .
• Escriba el cuarto valor de tipo int a dst [3] .

Este es el lenguaje C: todos los contenidos de la memoria son, en última instancia, bytes (es decir, ranuras con valores de tipo unsigned char , pero en la práctica, grupos de ocho bits), y se permiten cualquier operación de puntero arbitrario. En particular, los punteros src y dst se pueden usar para acceder a porciones de memoria superpuestas cuando se llama (esta situación se llama "aliasing"). Por lo tanto, el orden de lectura y escritura puede ser importante si los bytes se escriben y luego se leen nuevamente. Para que el comportamiento real del programa se corresponda con el resumen definido por el estándar C, el compilador tendría que alternar entre las operaciones de lectura y escritura, proporcionando un ciclo completo de accesos a la memoria en cada iteración. El código resultante sería más grande y funcionaría mucho más lento. Para los desarrolladores de C, esto sería una pena.

Aquí, afortunadamente, el comportamiento indefinido viene al rescate. El estándar C establece que no se puede acceder a los valores a través de punteros cuyo tipo no corresponde a los tipos actuales de estos valores. En pocas palabras, si el valor se escribe en dst [0] , donde dst es un puntero int , entonces los bytes correspondientes no se pueden leer a través de src [1] , donde src es un puntero doble , ya que en este caso intentaríamos acceder valor, que ahora es de tipo int , utilizando un puntero de un tipo incompatible. En este caso, se produciría un comportamiento indefinido. Esto se indica en el párrafo 7 de la sección 6.5 de la norma ISO 9899: 1999 (“C99”) (en la nueva edición 9899: 2018 o “C17”, la redacción no ha cambiado). Este requisito se llama la estricta regla de alias. Como resultado, el compilador de C puede actuar bajo el supuesto de que no se producen operaciones de acceso a la memoria que conducen a un comportamiento indefinido debido a la violación de la estricta regla de alias. Por lo tanto, el compilador puede reorganizar las operaciones de lectura y escritura en cualquier orden, ya que no deben acceder a porciones superpuestas de memoria. De esto se trata la optimización del código.

El significado del comportamiento indefinido, en resumen, es el siguiente: el compilador puede asumir que no habrá un comportamiento indefinido y generar código basado en esta suposición. En el caso de la estricta regla de alias, siempre que tenga lugar el alias, el comportamiento indefinido permite optimizaciones importantes que de otro modo serían difíciles de implementar. En términos generales, cada instrucción en los procedimientos de generación de código utilizada por el compilador tiene dependencias que restringen el algoritmo de planificación de la operación: una instrucción no se puede ejecutar antes de las instrucciones de las que depende, o después de las instrucciones que dependen de él. En nuestro ejemplo, el comportamiento indefinido elimina las dependencias entre las operaciones de escritura en dst [] y las operaciones de lectura "posteriores" de src [] : dicha dependencia solo puede existir en los casos en que se produce un comportamiento indefinido al acceder a la memoria. Del mismo modo, el concepto de comportamiento indefinido permite al compilador simplemente eliminar el código que no se puede ejecutar sin entrar en un estado de comportamiento indefinido.

Todo esto, por supuesto, es bueno, pero el compilador a veces percibe tal comportamiento como una traición traidora. A menudo puede escuchar la frase: "El compilador utiliza el concepto de comportamiento indefinido como una excusa para romper mi código". Supongamos que alguien escribe un programa que suma enteros y desborda temores; recuerde el caso de Bitcoin . Puede pensar así: para representar enteros, el procesador usa código adicional, lo que significa que si se produce un desbordamiento, sucederá porque el resultado se truncará al tamaño del tipo, es decir. 32 bit Esto significa que el resultado del desbordamiento se puede predecir y verificar con una prueba.

Nuestro desarrollador condicional escribirá esto:

 #include <stdio.h> #include <stdlib.h> int add(int x, int y, int *z) { int r = x + y; if (x > 0 && y > 0 && r < x) { return 0; } if (x < 0 && y < 0 && r > x) { return 0; } *z = r; return 1; } int main(int argc, char *argv[]) { int x, y, z; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); if (add(x, y, &z)) { printf("%d\n", z); } else { printf("overflow!\n"); } return 0; } 

Ahora intentemos compilar este código usando GCC:

 $ gcc -W -Wall -O9 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 overflow! 

Ok, parece funcionar. Ahora intente con otro compilador, por ejemplo, Clang (tengo la versión 6.0.0):

 $ clang -W -Wall -O3 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 -794967296 

Que?

Resulta que cuando una operación con tipos enteros con signo conduce a un resultado que no puede ser representado por el tipo de destino, ingresamos al territorio de comportamiento indefinido. Pero el compilador puede suponer que no sucede. En particular, al optimizar la expresión x> 0 && y> 0 && r <x , el compilador concluye que dado que los valores de x e y son estrictamente positivos, la tercera verificación no puede ser verdadera (la suma de dos valores no puede ser menor que ninguno de ellos), y puedes omitir toda esta operación. En otras palabras, dado que el desbordamiento es un comportamiento indefinido, "no puede suceder" desde el punto de vista del compilador, y todas las instrucciones que dependen de este estado se pueden eliminar. El mecanismo para detectar comportamientos indefinidos simplemente ha desaparecido.

El estándar nunca prescribió la suposición de que la "semántica con signo" (que en realidad se usa en las operaciones del procesador) se usa en los cálculos con tipos con signo; esto sucedió más bien por tradición, incluso en aquellos días en que los compiladores no eran lo suficientemente inteligentes como para optimizar el código, centrándose en una gama de valores. Puede forzar a Clang y GCC a aplicar semántica de ajuste a tipos firmados utilizando el indicador especial -fwrapv (en Microsoft Visual C, puede usar -d2UndefIntOverflow-, como se describe aquí ). Sin embargo, este enfoque no es confiable, la bandera puede desaparecer cuando el código se transfiere a otro proyecto o a otra arquitectura.

Pocas personas saben que los desbordamientos de tipo de personaje implican un comportamiento indefinido. Esto se afirma en el párrafo 5 de la sección 6.5 de las normas C99 y C17:

Si se produce una excepción al evaluar una expresión (es decir, si el resultado no está matemáticamente definido o está fuera del rango de valores válidos de un tipo dado), el comportamiento es indefinido.

Sin embargo, para los tipos sin signo, la semántica modular está garantizada. El párrafo 9 de la sección 6.2.5 dice lo siguiente:

El desbordamiento nunca ocurre en los cálculos con operandos sin signo, ya que un resultado que no puede ser representado por el tipo entero sin signo resultante es un módulo truncado, un número que es uno más que el valor máximo representado por el tipo resultante.

Otro ejemplo de comportamiento indefinido en operaciones con tipos con signo es la operación de división. Como todos saben, el resultado de la división por cero no está matemáticamente determinado, por lo tanto, de acuerdo con el estándar, esta operación implica un comportamiento indefinido. Si el divisor es cero en la operación idiv en el procesador x86, se genera una excepción de procesador. Al igual que las solicitudes de interrupción, el sistema operativo maneja las excepciones del procesador. En sistemas similares a Unix, como Linux, la excepción del procesador activada por la operación idiv se traduce en una señal SIGFPE , que se envía al proceso, y termina con el controlador predeterminado (no se sorprenda de que "FPE" significa "excepción de punto flotante" (excepción en operaciones de punto flotante), mientras que idiv trabaja con enteros). Pero hay otra situación que conduce a un comportamiento indefinido. Considere el siguiente código:

 #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", x / y); return 0; }  : $ gcc -W -Wall -O testdiv.c $ ./a.out 42 17 2 $ ./a.out -2147483648 -1 zsh: floating point exception (core dumped) ./a.out -2147483648 -1 

Y la verdad es: en esta máquina (la misma x86 para Linux), el tipo int representa un rango de valores desde -2,147,483,648 hasta +2,147,483,647. Si divide -2,147,483,648 por -1, debería obtener +2,147,483,648 Pero este número no está en el rango de valores int . Por lo tanto, el comportamiento no está definido. Cualquier cosa puede pasar. En este caso, el proceso se termina por la fuerza. En otro sistema, especialmente con un procesador pequeño que no tiene una operación de división, el resultado puede variar. En tales arquitecturas, la división se realiza mediante programación, con la ayuda del procedimiento generalmente proporcionado por el compilador, y ahora puede hacer lo que quiera con un comportamiento indefinido, porque eso es exactamente lo que es.

Observo que SIGFPE se puede obtener en las mismas condiciones y con la ayuda del operador de módulo ( % ). Y de hecho: debajo de ella se encuentra la misma operación idiv , que calcula tanto el cociente como el resto, por lo que se activa la misma excepción del procesador. Curiosamente, el estándar C99 dice que la expresión INT_MIN% -1 no puede conducir a un comportamiento indefinido, ya que el resultado está matemáticamente definido (cero) y claramente ingresa el rango de valores del tipo objetivo. En la versión C17, se modificó el texto del párrafo 6 de la sección 6.5.5, y ahora también se tiene en cuenta este caso, lo que acerca el estándar a la situación real en las plataformas de hardware comunes.

Hay muchas situaciones no obvias que también conducen a un comportamiento indefinido. Echa un vistazo a este código:

 #include <stdio.h> #include <stdlib.h> unsigned short mul(unsigned short x, unsigned short y) { return x * y; } int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", mul(x, y)); return 0; } 

¿Crees que un programa, siguiendo el estándar C, debería imprimirse si pasamos los factores 45,000 y 50,000 a la función?

• 18,048
• 2,250,000,000
• Dios salve a la reina!

La respuesta correcta ... sí, todo lo anterior! Es posible que haya argumentado así: dado que un corto sin signo es un tipo sin signo, debería admitir la semántica de envoltura módulo 65 536, porque en un procesador x86 el tamaño de este tipo, por regla general, es exactamente 16 bits (el estándar también permite un tamaño más grande, pero en la práctica, este sigue siendo un tipo de 16 bits). Como matemáticamente el producto es 2,250,000,000, se truncará el módulo 65,536, lo que da una respuesta de 18,048. Sin embargo, al pensar de esta manera, nos olvidamos de la extensión de los tipos enteros. De acuerdo con el estándar C (sección 6.3.1.1, párrafo 2), si los operandos son de un tipo cuyo tamaño es estrictamente más pequeño que el tamaño de int , y los valores de este tipo pueden ser representados por el tipo int sin pérdida de bits (y solo tenemos este caso: en mi x86 bajo Linux tiene un tamaño int de 32 bits, y puede almacenar explícitamente valores de 0 a 65.535), luego ambos operandos se convierten en int y la operación ya se realiza en los valores convertidos. A saber: el producto se calcula como un valor de tipo int, y es solo cuando regresa de la función que se devuelve a corto sin signo (es decir, es en este momento cuando se produce el módulo de truncamiento 65 536). El problema es que matemáticamente el resultado antes de la transformación inversa es 2.250 millones, y este valor excede el rango de int , que es un tipo con signo. Como resultado, obtenemos un comportamiento indefinido. Después de eso, puede pasar cualquier cosa, incluidos episodios repentinos de patriotismo inglés.

Sin embargo, en la práctica, con los compiladores ordinarios, el resultado es 18.048, ya que todavía no hay una optimización que pueda aprovechar el comportamiento indefinido en este programa en particular (uno podría imaginar escenarios más artificiales en los que realmente causaría problemas).

Finalmente, otro ejemplo, ahora en C ++:

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <array> int main(int argc, char *argv[]) { std::array<char, 16> tmp; int i; if (argc < 2) { return EXIT_FAILURE; } memset(tmp.data(), 0, 16); if (strlen(argv[1]) < 16) { strcpy(tmp.data(), argv[1]); } for (i = 0; i < 17; i ++) { printf(" %02x", tmp[i]); } printf("\n"); } 

¡Este no es el típico "malo, horrible, rayado () !" De hecho, aquí la función strcpy () se ejecuta solo si el tamaño de la cadena de origen, incluido el terminal cero, es lo suficientemente pequeño. Además, los elementos de la matriz se inicializan explícitamente a cero, por lo que todos los bytes de la matriz tienen un valor dado, independientemente de si se pasa una cadena grande o pequeña a la función. Al mismo tiempo, el bucle al final es incorrecto: lee un byte más de lo que debería.

Ejecuta el código:

 $ g++ -W -Wall -O9 testvec.c $ ./a.out foo 66 6f 6f 00 00 00 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ff ffffac ffffffc0 55 00 00 00 ffffff80 71 34 ffffff99 07 ffffffba ff ffffea ffffffd0 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ffffffac ffffffc0 55 00 00 ffffff97 7b 12 1b ffffffa1 7f 00 00 02 00 00 00 00 00 00 00 ffffffd8 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 ffffff80 00 00 02 00 00 00 60 56 (...) 62 64 3d 30 30 zsh: segmentation fault (core dumped) ./a.out foo ++? 

Puede objetar ingenuamente: bueno, lee un byte adicional más allá de los límites de la matriz; pero esto no da tanto miedo, porque en la pila este byte todavía está allí, se asigna a la memoria, por lo que el único problema aquí es el decimoséptimo elemento adicional con un valor desconocido. El ciclo seguirá imprimiendo exactamente 17 enteros (en formato hexadecimal) y finalizará sin ninguna queja.

Pero el compilador tiene su propia opinión sobre este asunto. Es muy consciente de que la decimoséptima lectura provoca un comportamiento indefinido. Según su lógica, cualquier instrucción posterior está en el limbo: no es necesario que después de un comportamiento indefinido algo deba existir (formalmente, incluso las instrucciones anteriores pueden estar bajo ataque, ya que el comportamiento indefinido también funciona en la dirección opuesta). En nuestro caso, el compilador simplemente ignorará la verificación de condición en el bucle, y girará para siempre, o más bien, hasta que comience a leer fuera de la memoria asignada para la pila, después de lo cual la señal SIGSEGV funcionará.

Es divertido, pero si GCC se inicia con configuraciones menos agresivas para optimizaciones, dará una advertencia:

 $ g++ -W -Wall -O1 testvec.c testvec.c: In function 'int main(int, char**)': testvec.c:20:15: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations] printf(" %02x", tmp[i]); ~~~~~~^~~~~~~~~~~~~~~~~ testvec.c:19:19: note: within this loop for (i = 0; i < 17; i ++) { ~~^~~~ 

En -O9, esta advertencia desaparece de alguna manera. Quizás el hecho es que a altos niveles de optimización, el compilador aplica de manera más agresiva el despliegue del bucle. Es posible (pero impreciso) que este sea un error de CCG (en el sentido de una pérdida de advertencia; por lo tanto, las acciones de CCG en cualquier caso no contradicen el estándar, ya que no requiere la emisión de "diagnósticos" en tal situación).

Conclusión: si está escribiendo código en C o C ++, tenga mucho cuidado y evite situaciones que conduzcan a un comportamiento indefinido, incluso cuando parezca "está bien".

Los tipos enteros sin signo son una buena ayuda en los cálculos aritméticos, ya que tienen semántica modular garantizada (pero aún puede obtener problemas relacionados con la extensión de los tipos enteros). Otra opción, por alguna razón impopular, es no escribir en C y C ++. Por varias razones, esta solución no siempre es adecuada. Pero si puede elegir en qué idioma escribir el programa, es decir, Cuando recién está comenzando un nuevo proyecto en una plataforma que admite Go, Rust, Java u otros lenguajes, puede ser más rentable negarse a usar C como el "lenguaje predeterminado". La elección de herramientas, incluido un lenguaje de programación, siempre es un compromiso. Las trampas de C, especialmente el comportamiento indefinido en operaciones con tipos firmados, conducen a costos adicionales para un mayor mantenimiento del código, que a menudo se subestiman.