En el software, se produce un desbordamiento de la pila si el puntero de la pila de llamadas excede el límite de la pila . La pila de llamadas puede consistir en una cantidad limitada de espacio de direcciones , a menudo determinada al inicio del programa. El tamaño de la pila de llamadas depende de muchos factores, incluido el lenguaje de programación, la arquitectura de la máquina, los subprocesos múltiples 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 del búfer ), se dice que la pila se desborda , lo que generalmente resulta en un caída del programa . [1]
La causa más común del desbordamiento de la pila es la 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 más de lo que cabe en la pila. [2]
Un ejemplo de recursividad infinita en C.
int foo () { return 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 genera un error de segmentación . [2] Sin embargo, algunos compiladores implementan optimización de llamada de cola , lo que permite que se produzca una recursividad 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 permitirán efectivamente la optimización de llamadas finales ; por ejemplo, compilar el programa simple anterior usando gcc con -O1resultará en un error 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 recursividad de cola como parte del estándar del lenguaje. [5]
Una función recursiva que termina en teoría pero que causa un desbordamiento del búfer de la pila de llamadas en la práctica se puede solucionar transformando la recursividad en un bucle y almacenando los argumentos de la función en una pila explícita (en lugar del uso implícito de 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 el del lado derecho.
Una función como el ejemplo anterior a la izquierda no sería un problema en un entorno que admita la optimización de llamadas de cola ; sin embargo, todavía es posible crear una función recursiva que pueda provocar un desbordamiento de la pila en estos lenguajes. Considere el siguiente ejemplo de dos funciones de exponenciación enteras simples.
Ambas pow(base, exp)funciones anteriores calculan un resultado equivalente; sin embargo, la de la izquierda es propensa a provocar un desbordamiento de la pila porque la optimización de la llamada final no es posible para esta función. Durante la ejecución, la pila de estas funciones tendrá este aspecto:
Observe que la función de la izquierda debe almacenar en su pila expel número de números enteros, que se multiplicarán cuando termine la recursividad y la función devuelva 1. Por el contrario, la función de la derecha solo debe almacenar 3 números enteros en cualquier momento y calcula un resultado intermediario 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 la posibilidad de un desbordamiento de la pila.
La otra causa importante de un desbordamiento de pila resulta de un 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 esta razón, algunos autores recomiendan que las matrices de más de 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 hay más memoria de la que está 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 la pila.
Los desbordamientos de pila empeoran con cualquier cosa que reduzca el tamaño efectivo de la 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 habilitan los subprocesos múltiples, el programa fallará. 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 de subprocesos múltiples, a las personas nuevas en el desarrollo de núcleos generalmente se les desaconseja el uso de algoritmos recursivos o grandes buffers de pila. [7]