memory - ¿Cómo ocurre un "desbordamiento de pila" y cómo lo previene?

stack-overflow

Question

¿Cómo ocurre un desbordamiento de pila y cuáles son las mejores formas de garantizar que no ocurra, o formas de prevenirlo, particularmente en servidores web, pero también serían interesantes otros ejemplos?

Answer 1

Apilar

Una pila, en este contexto, es el último búfer que entra y sale, donde coloca los datos mientras se ejecuta su programa. El último en entrar, el primero en salir (LIFO) significa que lo último que ingresas es siempre lo primero que vuelves a salir: si presionas 2 elementos en la pila, ''A'' y luego ''B'', entonces lo primero que expliques fuera de la pila será ''B'', y el siguiente es ''A''.

Cuando llama a una función en su código, la siguiente instrucción después de la llamada a la función se almacena en la pila y cualquier espacio de almacenamiento que pueda sobrescribir la llamada a la función. La función a la que llama podría usar más pila para sus propias variables locales. Cuando está hecho, libera el espacio de la pila variable local que utilizó, luego vuelve a la función anterior.

Desbordamiento de pila

Un desbordamiento de pila ocurre cuando has agotado más memoria para la pila de lo que se suponía que tu programa debía usar. En los sistemas integrados, puede que solo tenga 256 bytes para la pila, y si cada función ocupa 32 bytes, entonces solo puede tener llamadas a funciones 8 profundas: función 1 llama a la función 2 que llama a la función 3 que llama a función 4 .... quién llama función 8 que llama a la función 9, pero la función 9 sobrescribe la memoria fuera de la pila. Esto podría sobrescribir memoria, código, etc.

Muchos programadores cometen este error llamando a la función A que luego llama a la función B, que luego llama a la función C, que luego llama a la función A. Puede funcionar la mayor parte del tiempo, pero solo una vez la entrada incorrecta hará que entre en ese círculo para siempre hasta que la computadora reconozca que la pila está exagerada.

Las funciones recursivas también son una causa de esto, pero si estás escribiendo recursivamente (es decir, tu función se llama a sí misma), entonces debes ser consciente de esto y usar variables estáticas / globales para evitar la recursión infinita.

En general, el sistema operativo y el lenguaje de programación que está utilizando administran la pila, y está fuera de sus manos. Debería mirar su gráfico de llamadas (una estructura de árbol que muestra desde su principal lo que cada función llama) para ver qué tan profundo van sus llamadas de función, y para detectar ciclos y recursiones que no son intencionales. Los ciclos intencionales y la recursividad deben verificarse artificialmente hasta el error si se llaman entre sí demasiadas veces.

Más allá de las buenas prácticas de programación, las pruebas estáticas y dinámicas, no hay mucho que pueda hacer en estos sistemas de alto nivel.

Sistemas embebidos

En el mundo integrado, especialmente en el código de alta confiabilidad (automotriz, avión, espacio), usted hace extensas revisiones y revisiones de código, pero también hace lo siguiente:

• No permitir la recursividad y los ciclos: impuestos por políticas y pruebas
• Mantenga el código y la pila separados (código en flash, pila en RAM, y nunca los dos se encontrarán)
• Coloque bandas de protección alrededor de la pila: área vacía de memoria que llena con un número mágico (generalmente una instrucción de interrupción de software, pero hay muchas opciones aquí), y cientos o miles de veces por segundo observa las bandas de guardia para asegurarse no han sido sobrescritos.
• Use protección de memoria (es decir, no ejecutar en la pila, no leer o escribir fuera de la pila)
• Las interrupciones no llaman a funciones secundarias: establecen indicadores, copian datos y permiten que la aplicación se encargue de procesarlos (de lo contrario, puede obtener 8 profundidades en el árbol de llamadas de función, tener una interrupción y luego salir de otras funciones dentro del interrumpir, causando el reventón). Tiene varios árboles de llamadas, uno para los procesos principales y uno para cada interrupción. Si tus interrupciones pueden interrumpirse ... bueno, habrá dragones ...

Lenguajes y sistemas de alto nivel

Pero en lenguajes de alto nivel se ejecutan en sistemas operativos:

• Reduzca el almacenamiento variable local (las variables locales se almacenan en la pila, aunque los compiladores son bastante inteligentes al respecto y algunas veces pondrán a los grandes locales en el montón si su árbol de llamadas es poco profundo)
• Evitar o limitar estrictamente la recursión
• No rompa demasiado sus programas en funciones cada vez más pequeñas: incluso sin contar las variables locales, cada llamada de función consume hasta 64 bytes en la pila (procesador de 32 bits, guarda la mitad de los registros de la CPU, banderas, etc.)
• Mantenga su árbol de llamadas poco profundo (similar a la declaración anterior)

Servidores web

Depende de la ''caja de arena'' que tengas si puedes controlar o incluso ver la pila. Hay muchas posibilidades de que pueda tratar los servidores web como lo haría con cualquier otro lenguaje de alto nivel y sistema operativo: está fuera de sus manos, pero consulte el idioma y la pila de servidores que está utilizando. Es posible volar la pila en su servidor SQL, por ejemplo.

-Adán

Answer 2

¿Qué? Nadie tiene amor por aquellos encerrados por un ciclo infinito.

do
{
JeffAtwood.WritesCode();
} while(.MakingMadBank.Equals(false));

Answer 3

Aparte de la forma de desbordamiento de pila que se obtiene de una recursión directa (por ejemplo, Fibonacci(1000000) ), una forma más sutil que he experimentado muchas veces es una recursión indirecta, donde una función llama a otra función, que llama a otra, y luego una de esas funciones llama al primero otra vez.

Esto puede ocurrir comúnmente en funciones que se llaman en respuesta a eventos pero que a su vez pueden generar nuevos eventos, por ejemplo:

void WindowSizeChanged(Size& newsize) {
// override window size to constrain width
newSize.width=200;
ResizeWindow(newSize);
}

En este caso, la llamada a ResizeWindow puede provocar que se ResizeWindow nuevo la devolución de llamada WindowSizeChanged() , que ResizeWindow llamar a ResizeWindow , hasta que se agote la pila. En situaciones como estas, a menudo necesita diferir la respuesta al evento hasta que el marco de pila haya regresado, por ejemplo, al publicar un mensaje.

Answer 4

La mayoría de las personas te dirá que se produce un desbordamiento de la pila con recursión sin una ruta de salida, mientras que la mayoría de las veces, si trabajas con estructuras de datos lo suficientemente grandes, incluso una ruta de salida de recursión correcta no te ayudará.

Algunas opciones en este caso:

• Búsqueda en primer lugar
• Recursividad de la cola , gran publicación de blog específica de .Net (lo siento, .Net de 32 bits)

Answer 5

La recursión infinita es una forma común de obtener un error de desbordamiento de la pila. Para evitarlo, siempre asegúrese de que haya una ruta de salida que será atacada. :-)

Otra forma de obtener un desbordamiento de pila (en C / C ++, al menos) es declarar una variable enorme en la pila.

char hugeArray[100000000];

Eso lo hará.

Answer 6

Por lo general, un desbordamiento de pila es el resultado de una llamada recursiva infinita (dada la cantidad habitual de memoria en las computadoras estándar hoy en día).

Cuando realiza una llamada a un método, función o procedimiento, el modo "estándar" o hacer la llamada consiste en:

1. Empujando la dirección de retorno para la llamada a la pila (esa es la siguiente oración después de la llamada)
2. Por lo general, el espacio para el valor de retorno se reserva en la pila
3. Al presionar cada parámetro en la pila (el orden diverge y depende de cada compilador, también algunos de ellos a veces se almacenan en los registros de la CPU para mejorar el rendimiento)
4. Realizando la llamada real.

Por lo tanto, por lo general, esto lleva unos pocos bytes dependiendo del número y tipo de parámetros, así como de la arquitectura de la máquina.

Verás que si comienzas a hacer llamadas recursivas, la pila comenzará a crecer. Ahora, la pila generalmente se reserva en la memoria de tal manera que crece en dirección opuesta al montón, por lo que, dada una gran cantidad de llamadas sin "volver", la pila comienza a llenarse.

Ahora, en tiempos más antiguos, el desbordamiento de la pila podría ocurrir simplemente porque agotó toda la memoria disponible, así como así. Con el modelo de memoria virtual (hasta 4 GB en un sistema X86) que estaba fuera del alcance por lo general, si obtiene un error de desbordamiento de pila, busque una llamada recursiva infinita.

Answer 7

Teniendo en cuenta que esto fue etiquetado con "piratería", sospecho que el "desbordamiento de la pila" al que se refiere es un desbordamiento de la pila de llamadas, en lugar de un desbordamiento de la pila de nivel superior como los que se mencionan en la mayoría de las otras respuestas aquí. En realidad, no se aplica a entornos administrados o interpretados como .NET, Java, Python, Perl, PHP, etc., en los que las aplicaciones web suelen estar escritas, por lo que su único riesgo es el propio servidor web, que probablemente esté escrito en C o C ++.

Mira este hilo:

Answer 8

Un desbordamiento de pila ocurre cuando Jeff y Joel quieren darle al mundo un lugar mejor para obtener respuestas a preguntas técnicas. Es demasiado tarde para evitar este desbordamiento de pila. Ese "otro sitio" podría haberlo evitado al no ser escéptico. ;)

Answer 9

Un desbordamiento de pila en código real ocurre muy raramente. La mayoría de las situaciones en las que ocurre son recurrencias donde la terminación ha sido olvidada. Sin embargo, puede ocurrir raramente en estructuras altamente anidadas, por ejemplo, documentos XML particularmente grandes. La única ayuda real aquí es refactorizar el código para usar un objeto de pila explícito en lugar de la pila de llamadas.