En software, se produce un desbordamiento de pila si el puntero de la pila de llamadas excede el límite de la pila . La pila de llamadas puede constar de una cantidad limitada de espacio de direcciones , a menudo determinada al comienzo del programa. El tamaño de la pila de llamadas depende de muchos factores, incluidos el lenguaje de programación, la arquitectura de la máquina, el multihilo y la cantidad de memoria disponible. Cuando un programa intenta utilizar más espacio del que está disponible en la pila de llamadas (es decir, cuando intenta acceder a la memoria más allá de los límites de la pila de llamadas, lo que es esencialmente un desbordamiento de búfer ), se dice que la pila se desborda , lo que generalmente da como resultado un bloqueo del programa . [1]
La causa más común de desbordamiento de pila es una recursión excesivamente profunda o infinita, en la que una función se llama a sí misma tantas veces que el espacio necesario para almacenar las variables y la información asociada con cada llamada es mayor que el que cabe en la pila. [2]
Un ejemplo de recursión infinita en C.
int foo () { devolver foo (); } La función foo , cuando se invoca, continúa invocándose a sí misma, asignando espacio adicional en la pila cada vez, hasta que la pila se desborda, lo que da como resultado un error de segmentación . [2] Sin embargo, algunos compiladores implementan la optimización de llamadas de cola , lo que permite que se produzca una recursión infinita de un tipo específico ( recursión de cola ) sin desbordamiento de pila. Esto funciona porque las llamadas de recursión de cola no ocupan espacio de pila adicional. [3]
Algunas opciones del compilador de C habilitarán efectivamente la optimización de la recursión de cola ; por ejemplo, compilar el programa simple anterior usando gcc con -O1resultará en una falla de segmentación, pero no cuando se usa -O2o -O3, ya que estos niveles de optimización implican la -foptimize-sibling-callsopción del compilador. [4] Otros lenguajes, como Scheme , requieren que todas las implementaciones incluyan la recursión de cola como parte del estándar del lenguaje. [5]
Una función recursiva que termina en teoría pero que provoca un desbordamiento del búfer de la pila de llamadas en la práctica se puede solucionar transformando la recursión en un bucle y almacenando los argumentos de la función en una pila explícita (en lugar de utilizar implícitamente la pila de llamadas). Esto siempre es posible porque la clase de funciones recursivas primitivas es equivalente a la clase de funciones computables LOOP. Considere este ejemplo en pseudocódigo similar a C++ :
Una función recursiva primitiva como la del lado izquierdo siempre se puede transformar en un bucle como la del lado derecho.
Una función como la del ejemplo anterior a la izquierda no sería un problema en un entorno que admita la optimización de llamadas finales ; sin embargo, aún es posible crear una función recursiva que pueda generar un desbordamiento de pila en estos lenguajes. Considere el siguiente ejemplo de dos funciones de exponenciación de números enteros simples.
Ambas pow(base, exp)funciones anteriores calculan un resultado equivalente; sin embargo, la de la izquierda es propensa a provocar un desbordamiento de pila porque no es posible optimizar las llamadas finales para esta función. Durante la ejecución, la pila de estas funciones se verá así:
Tenga en cuenta que la función de la izquierda debe almacenar en su pila expuna cantidad de números enteros, que se multiplicarán cuando la recursión finalice y la función devuelva 1. En cambio, la función de la derecha solo debe almacenar 3 números enteros a la vez y calcula un resultado intermedio que se pasa a su siguiente invocación. Como no se debe almacenar ninguna otra información fuera de la invocación de la función actual, un optimizador de recursión de cola puede "eliminar" los marcos de pila anteriores, eliminando así la posibilidad de un desbordamiento de pila.
La otra causa principal de un desbordamiento de pila es el intento de asignar más memoria en la pila de la que cabe, por ejemplo, creando variables de matriz locales que son demasiado grandes. Por este motivo, algunos autores recomiendan que las matrices más grandes que unos pocos kilobytes se asignen dinámicamente en lugar de como una variable local. [6]
Un ejemplo de una variable de pila muy grande en C :
int foo () { doble x [ 1048576 ]; } En una implementación de C con flotantes de doble precisión de 8 bytes , la matriz declarada consume 8 megabytes de datos; si esta es más memoria que la disponible en la pila (según lo establecido por los parámetros de creación de subprocesos o los límites del sistema operativo), se producirá un desbordamiento de pila.
Los desbordamientos de pila se agravan con cualquier cosa que reduzca el tamaño efectivo de pila de un programa determinado. Por ejemplo, el mismo programa que se ejecuta sin múltiples subprocesos puede funcionar bien, pero tan pronto como se habilita la multiprocesación, el programa se bloquea. Esto se debe a que la mayoría de los programas con subprocesos tienen menos espacio de pila por subproceso que un programa sin soporte de subprocesos. Debido a que los núcleos son generalmente multiproceso, a las personas que se inician en el desarrollo de núcleos generalmente se les desaconseja utilizar algoritmos recursivos o grandes búferes de pila. [7]