Este sencillo programa en C rara vez termina con la misma profundidad de llamada:
#include <stdio.h> #include <stdlib.h> void recursive(unsigned int rec); int main(void) { recursive(1); return 0; } void recursive(unsigned int rec) { printf("%u\n", rec); recursive(rec + 1); }¿Cuáles podrían ser las razones detrás de este comportamiento caótico?
Estoy usando fedora (16GiB ram, tamaño de pila de 8192) y compilé usando cc sin ninguna opción.
EDITAR
La pregunta es más, dado que en Linux el tamaño de la pila de subprocesos es fijo y dado por ulimit -s , ¿qué influiría en el tamaño de la pila disponible para que el desbordamiento de la pila no siempre ocurra a la misma profundidad de llamada?
EDIT 2 @BlueMoon siempre ve el mismo resultado en su CentOS, mientras que en mi Fedora, con una pila de 8M, veo diferentes resultados (último entero impreso 261892 o 261845, o 261826, o...)
Cambie la llamada de printf a:
printf("%u %p\n", rec, &rec);Esto obliga a gcc a poner rec en la pila y te da su dirección, que es una buena indicación de lo que está pasando con el puntero de la pila.
Ejecute su programa varias veces y observe lo que sucede con la dirección que se imprime al final. Algunas ejecuciones en mi máquina muestran esto:
261958 0x7fff82d2878c 261778 0x7fffc85f379c 261816 0x7fff4139c78c 261926 0x7fff192bb79c Lo primero a tener en cuenta es que la dirección de la pila siempre termina en 78c o 79c . ¿Porqué es eso? Deberíamos bloquearnos al cruzar el límite de una página, las páginas tienen una longitud de 0x1000 bytes y cada función consume 0x20 bytes de la pila, por lo que la dirección debe terminar en 00X o 01X. Pero mirando esto más de cerca, nos estrellamos en libc. Entonces, el desbordamiento de la pila ocurre en algún lugar dentro de libc, de esto podemos concluir que llamar a printf y todo lo demás que llama necesita al menos 0x78c = 1932 (posiblemente más X * 4096) bytes de pila para funcionar.
La segunda pregunta es ¿por qué se necesita un número diferente de iteraciones para llegar al final de la pila? Una pista es el hecho de que las direcciones que obtenemos son diferentes en cada ejecución del programa.
1 0x7fff8c4c13ac 1 0x7fff0a88f33c 1 0x7fff8d02fc2c 1 0x7fffbc74fd9cLa posición de la pila en la memoria es aleatoria. Esto se hace para evitar toda una familia de explotaciones de desbordamiento de búfer. Pero dado que las asignaciones de memoria, especialmente en este nivel, solo se pueden realizar en varias páginas (4096 bytes), todos los punteros de pila iniciales se alinearían en 0x1000. Esto reduciría la cantidad de bits aleatorios en la dirección de la pila aleatoria, por lo que se agrega aleatoriedad adicional simplemente desperdiciando una cantidad aleatoria de bytes en la parte superior de la pila.
El sistema operativo solo puede contabilizar la cantidad de memoria que utiliza, incluido el límite de la pila, en páginas enteras. Entonces, aunque la pila comience en una dirección aleatoria, la última dirección accesible en la pila siempre será una dirección que termine en 0xfff.
La respuesta corta es: para aumentar la cantidad de aleatoriedad en el diseño de memoria aleatorio, se desperdician deliberadamente un montón de bytes en la parte superior de la pila, pero el final de la pila tiene que terminar en un límite de página.
No tendrá el mismo comportamiento entre ejecuciones porque depende de la memoria actual disponible. Cuanta más memoria tenga disponible, más lejos llegará en esta función recursiva.
Su programa se ejecuta infinitamente ya que no hay una condición base en su función recursiva. La pila crecerá continuamente con cada llamada de función y dará como resultado un desbordamiento de la pila.
Si fuera el caso de la optimización de recurrencia de cola (con la opción -O2 ), entonces se producirá un desbordamiento de pila con seguridad. Invoca un comportamiento indefinido.
¿Qué influiría en el tamaño de la pila disponible para que el desbordamiento de la pila no siempre se produzca a la misma profundidad de llamada?
Cuando se produce un desbordamiento de pila, invoca un comportamiento indefinido. No se puede decir nada sobre el resultado en este caso.