La pila de llamadas: marcos, direcciones de retorno y desbordamientos

Llamar a una función supone unas pocas escrituras en memoria; retornar consiste en leer de ella una dirección y saltar allí. Ejecuta paso a paso uno de los cuatro pequeños programas y observa la pila, con las direcciones más altas arriba. Cada escritura se ilumina en ámbar; cada lectura, en azul. Las posiciones que deja un marco al retirarse siguen visibles, atenuadas: nadie ha borrado su contenido.

Ejemplo resuelto — La pila de llamadas: marcos, direcciones de retorno y desbordamientos

Llamadas realizadas	5
Profundidad máxima en marcos	5
Pila usada a la profundidad máxima	60 de 128 bytes
Resultado	120

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — La pila de llamadas: marcos, direcciones de retorno y desbordamientos

La pila de llamadas es una región de memoria donde cada llamada a una función recibe un marco. Aquí contiene su argumento, la dirección de retorno (donde se reanuda la función que hizo la llamada), el puntero de marco guardado de esa función y las variables locales. El puntero de pila señala la dirección más baja en uso; una llamada lo hace bajar un marco y un retorno lo hace subir de nuevo. Una recursión de profundidad d, con marcos de f bytes, necesita d·f bytes de pila.

Qué significa cada símbolo

d: la profundidad: cuántos marcos hay a la vez en la pila
f: los bytes de cada marco: aquí, 12 más 4 por cada variable local

Supone: Se supone una máquina de 32 bits con la convención de llamada clásica de C: posiciones de 4 bytes, una pila que crece hacia direcciones más bajas, argumentos que se pasan por la pila y un puntero de marco en cada marco. Las convenciones de 64 bits pasan los primeros argumentos en registros; los compiladores pueden omitir el puntero de marco. En ARM, una función que no llama a ninguna otra puede conservar su dirección de retorno en un registro. Por eso, los marcos reales pueden tener un tamaño y una distribución distintos de los de estas tres posiciones.

La dirección de retorno es un número en memoria que un array puede sobrescribir 🖖

Pulsa Seis valores en cuatro. En buf caben cuatro valores de tipo int. Como buf[0] ocupa la dirección más baja, buf[4] y buf[5] son las dos posiciones que siguen hacia arriba: las que la llamada reservó para el puntero de marco guardado y la dirección de retorno, en ese orden. El bucle nunca comprueba el índice, así que el quinto valor sustituye al puntero de marco y el sexto, 0x46464646, sustituye a la dirección de retorno. Cuando copy retorna, el procesador lee esa posición y salta a la dirección que contiene. Con cuatro valores, retorna a 0x08048400, como corresponde; con cinco, también retorna allí, pero devuelve a main un puntero de marco dañado. Esto es un desbordamiento de búfer en la pila. En noviembre de 1988, el gusano Morris logró entrar en fingerd por esta vía: fingerd leía los datos de entrada en un búfer de 512 bytes sin limitar cuánto leía.

Una variable sin inicializar conserva lo que dejó allí la última llamada 🖖

Pulsa Valor residual. set guarda 42 en su variable local y retorna. Al retornar, el puntero de pila sube, pero no se borra nada. Después se llama a peek desde el mismo punto, por lo que su marco ocupa las mismas direcciones. Su variable local y queda en la dirección 1008, justo donde estaba x. peek nunca escribe en y, así que al leerla obtiene 42. En C, leer una variable sin inicializar es un comportamiento indefinido: el lenguaje no garantiza ningún resultado y un compilador que aplique optimizaciones puede incluso omitir la lectura de esa posición. Si la lectura llega a realizarse, encuentra lo que dejó la última escritura en esa dirección.

La pila conserva un solo camino entre las llamadas 🖖

Fija el valor de fib en 10. Realiza 177 llamadas, pero en el punto de mayor profundidad la pila contiene 10 marcos, que ocupan 120 bytes. El marco de una llamada se retira antes de añadir el de su llamada hermana: en la pila solo está la cadena que va desde fib(10) hasta la llamada que se está ejecutando. fact(11) realiza 11 llamadas, aproximadamente una dieciseisava parte, y desborda la pila porque su cadena tiene 11 marcos y necesita 132 bytes. En estas dos funciones, cada llamada realiza una cantidad fija de trabajo además de sus llamadas recursivas. Por eso, el número de llamadas mide el tiempo de ejecución; la profundidad de la cadena más larga mide el espacio de pila necesario.

Problema resuelto al detalle

¿Hasta qué profundidad puede llegar la recursión? 4 pasos
Pulsa fact(11) se desborda. La pila de esta página tiene 128 bytes. El enlazador de Microsoft reserva por defecto 1 MB de pila para un programa; toma ese tamaño como 1 MiB, es decir, 1.048.576 bytes, y usa los marcos de esta página. ¿Hasta qué profundidad puede llegar fact? ¿Y si cada llamada reserva además una variable local de 4 bytes? ¿Cuánta pila necesita fib(30) y cuántas llamadas realiza?

Abre este problema en la herramienta
1. Cada marco contiene un argumento, una dirección de retorno y un puntero de marco guardado: 3 × 4 = 12 bytes. Como 128 / 12 = 10,67, caben 10 marcos, y fact(11) necesita 11 × 12 = 132 bytes. La tabla de resultados muestra el desbordamiento.
  
  $f = 3 \times 4 = 12, ⌊ \frac{128}{12} ⌋ = 10, 11 \times 12 = 132 > 128$
2. 1.048.576 / 12 = 87.381,33, así que caben 87.381 marcos: fact podría alcanzar 87.381 niveles de recursión antes de agotar la pila. Mucho antes, su resultado ya habría superado lo que cabe en un int de 32 bits: ocurre con 13! = 6.227.020.800.
  
  $⌊ \frac{1 048 576}{12} ⌋ = 87381$
3. Con una variable local de 4 bytes, cada marco ocupa 16 bytes, y 1.048.576 / 16 = 65.536 exactamente.
  
  $f = 16 : \frac{1 048 576}{16} = 65536$
4. La cadena más larga de fib(30) tiene 30 marcos: 30 × 12 = 360 bytes. El número de llamadas es 2·F(31) − 1, donde F(31) = 1.346.269 es el término 31 de la sucesión de Fibonacci. En total, 2.692.537 llamadas.
  
  $d = 30 : 30 \times 12 = 360, 2 F_{31} - 1 = 2 \times 1346269 - 1 = 2692537$
Respuesta

87.381 niveles, o 65.536 con una variable local. fib(30) necesita 360 bytes de pila y realiza 2.692.537 llamadas. La profundidad determina el espacio de pila; en fib, el número de llamadas determina el tiempo.

$d_{m a x} = ⌊ \frac{S}{f} ⌋ = 87381 (f = 12), 65536 (f = 16)$

Ruta de aprendizaje

Cómo ejecuta un programa un ordenador

Referencias (2)

The worked problem's stack size: the linker's default reservation: Microsoft Learn, "/STACK (Stack allocations)," C/C++ build reference, updated 23 February 2022.
The first insight's 1988 example: fingerd's unbounded read into a 512-byte buffer on the stack: Bob Page, "A Report on the Internet Worm." University of Lowell, 7 November 1988 (copy hosted at Toronto Metropolitan University).

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.