Pila de llamadas

En ciencias de la computación, una pila de llamadas (en inglés call stack) es una estructura dinámica de datos LIFO, (una pila), que almacena la información sobre las subrutinas activas de un programa de computadora. Esta clase de pila también es conocido como una pila de ejecución, pila de control, pila de función, o pila de tiempo de ejecución, y a menudo se describe en forma corta como "la pila".

Estructura de la pila de llamadas.
En la figura se ve una pila, creciendo de abajo hacia arriba.
La subrutina DrawSquare es llamada y se crea un stack frame para ella (en azul). Luego, DrawSquare llama a la subrutina DrawLine, la cual tiene su propio stack frame (en verde).
El stack frame de cada subrutina tiene, en este caso, tres partes: * una dirección de retorno que indica la siguiente dirección a ejecutar después de que termine la subrutina, * los parámetros con que fue llamada la subrutina (que se cargan antes de llamarla), * y un espacio reservado para las variables y las constantes locales de la subrutina.

Una pila de llamadas es de uso frecuente para varios propósitos relacionados, pero la principal razón de su uso, es seguir el curso del punto al cual cada subrutina activa debe retornar el control cuando termine de ejecutar. (Las subrutinas activas son las que se han llamado pero todavía no han completado su ejecución ni retornando al lugar siguiente desde donde han sido llamadas). Si, por ejemplo, una subrutina DibujaCuadrado llama a una subrutina DibujaLinea desde cuatro lugares diferentes, el código de DibujaLinea debe tener una manera de saber a dónde retornar. Esto es típicamente hecho por un código que, para cada llamada dentro de DibujaCuadrado, pone la dirección de la instrucción después de la sentencia de llamada particular (la "dirección de retorno") en la pila de llamadas.

Puesto que la pila de llamadas se organiza como una pila, el programa que llama (a la subrutina) empuja (push) la dirección de retorno en la pila (la dirección en la que el programa continuará después de volver de la subrutina), y la subrutina llamada, cuando finaliza, retira (pop) la dirección de retorno de la pila de llamadas y transfiere el control a esa dirección. Si una subrutina llamada, llama a otra subrutina, la primera empuja (push) su dirección de retorno en la pila de llamadas, y así sucesivamente, con la información de direcciones de retorno apilándose y desapilándose como el programa dicte. Si el empujar (push) consume todo el espacio asignado para la pila de llamadas, ocurre un error llamado desbordamiento de pila. Agregando una entrada de subrutina a la pila de llamadas es a veces llamado bobinando o enrollando (winding); inversamente, la eliminación de entradas es llamado desenbobinando o desenrollando (unwinding).

Usualmente hay exactamente una pila de llamadas asociado a un programa en ejecución (o más precisamente, con cada tarea o hilo de un proceso), aunque pilas adicionales pueden ser creados para el manejo de señales o la multitarea cooperativa (como con setcontext). Puesto que hay solamente una pila en este importante contexto, puede ser referido como la pila (implícito, "de la tarea").

En lenguajes de programación de alto nivel, las características específicas de la pila de llamadas usualmente son ocultadas al programador. Ellos solo tienen acceso a la lista de funciones, y no a la memoria de la pila en sí misma. La mayoría de los lenguajes ensambladores, por una parte, requieren que los programas sean invocados con manipulación explícita de la pila. En un lenguaje de programación, los detalles reales de la pila dependen del compilador, del sistema operativo, y del conjunto de instrucciones disponible.

Funciones de la pila de llamadas

Según lo observado arriba, el propósito primario de una pila de llamadas es:

  • Almacenamiento de la dirección de retorno - Cuando una subrutina es llamada, la localización de la instrucción para retornar necesita ser guardada en alguna parte. Usando una pila para guardar la dirección de retorno tiene importantes ventajas sobre las otras alternativas. Una de ellas es que cada tarea tiene su propia pila, y así, la subrutina puede ser reentrante, es decir, puede estar activa simultáneamente para diferentes tareas que hacen diferentes cosas. Otro beneficio es que la recursividad es automáticamente soportada. Cuando una función se llama a sí misma recursivamente, un dirección de retorno necesita ser almacenada para cada activación de la función de tal manera de poderla usar posteriormente para retornar de la activación de la función. Esta capacidad es automática con una pila.

Una pila de llamadas puede servir para funciones adicionales, dependiendo del lenguaje, del sistema operativo, y del ambiente de la máquina. Entre ellos puede estar:

  • Almacenamiento local de datos - Una subrutina frecuentemente necesita memoria para almacenar los valores de las variables locales, las variables que son conocidas solamente dentro de la subrutina activa y no conservan sus valores después de que la subrutina retorna. A menudo es conveniente asignar el espacio para las variables locales simplemente moviendo el tope de la pila lo suficiente para proporcionar el espacio necesario. Esto es muy rápido de hacer comparado con, por ejemplo, una asignación de memoria en el heap. Observe que cada activación separada de una subrutina toma su propio espacio separado en la pila para sus variables locales.
  • Paso de parámetros - A menudo las subrutinas requieren que los valores para sus parámetros les sean suministrados por el código que las llama, y no es infrecuente que el espacio para estos parámetros descanse en la pila de llamadas. Generalmente si solamente hay algunos pequeños parámetros, los registros del procesador serán usados para pasar los valores, pero si hay más parámetros de los que se pueda manejar de esta manera, será necesario espacio de memoria. La pila de llamadas trabaja bien como un lugar para estos parámetros, especialmente ya que a cada llamada a una subrutina, la cual tendrá diferentes valores para los parámetros, le será dado un espacio separado en la pila de llamadas para esos valores.
  • Pila de evaluación - Los operandos para las operaciones aritméticas o lógicas muy frecuentemente son puestas en un registro se hace la operación allí. Sin embargo, en algunas situaciones los operandos pueden ser apilados hasta una profundidad arbitraria, lo que significa que debe ser usado algo más que los registros. La pila de tales operandos, similar al de una calculadora RPN, se llama pila de evaluación, y puede ocupar espacio en la pila de llamadas.
  • Puntero a la instancia actual - Algunos lenguajes orientados objeto (ej., C++), almacenan el puntero this junto con los argumentos de la función en la pila de llamadas cuando se están invocando los métodos. El puntero this señala la instancia del objeto asociado al método que se invocará. El puntero this es una parte esencial del contexto de ejecución en lenguajes orientadas objetos, puesto que proporciona el acceso a los datos del miembro y la V-Table del objeto actual. El puntero this enlaza las capas (layers) usadas en el diseño orientado a objetos con las capas (tipos de stack frames) de la pila de llamadas del tiempo de ejecución.
  • Envolviendo el contexto de la subrutina - En algunos lenguajes de programación (ej. Pascal y Ada) soportan subrutinas anidadas, permitiendo a una rutina interna acceder al contexto de su rutina externa que la contiene, es decir, los parámetros y las variables locales dentro del alcance de la rutina externa. Tal anidamiento estático se puede repetir - una función, declarada dentro de una función, declarada dentro de una función,... La implementación debe proporcionar un medio por el cual una función llamada en cualquier nivel de anidado estático dado pueda referenciar al marco que envuelve a cada nivel de anidado envolvente. Comúnmente, esta referencia es implementada por un puntero al marco que lo envuelve (o abarca), llamado un "downstack link" o "static link", para distinguirlo del "dynamic link" que hace referencia al procedimiento llamador inmediato (que no necesita ser la función padre estática). Por ejemplo, los lenguajes a menudo permiten a las rutinas internas llamarse a sí mismas recursivamente, resultando en múltiples marcos de llamada para las invocaciones de la rutina interna, todos estos enlaces estáticos apuntan al mismo contexto externo de rutina. En vez de un enlace estático, las referencias a los marcos estáticos envolventes pueden ser recolectados en un arreglo de punteros conocido como display el cual es indexado para localizar un marco deseado. La Burroughs B6500 tenía dicho display en el hardware que soportaba hasta 32 niveles de anidado estático.
  • Otro estado de retorno - Además de la dirección de retorno, en algunos ambientes puede haber otra máquina o estados de software que necesitan ser restaurados cuando una subrutina retorna. Esto pudo incluir cosas como el nivel de privilegio, información de manejo de excepciones, modos aritméticos, y así sucesivamente. Si fuera necesario, esto puede ser almacenado en la pila de llamadas justo como lo es la dirección de retorno.

La pila de llamadas típica es usada para la dirección de retorno, variables locales, y los parámetros (conocido como el call frame). En algunos ambientes puede haber más o menos funciones asignadas a la pila de llamadas. En el lenguaje de programación Forth, por ejemplo, solamente la dirección de retorno y las variables locales son almacenadas en la pila de llamadas (que en ese ambiente es llamado la pila de retorno); los parámetros son almacenados en una pila de datos separado. La mayoría de los Forth también tiene una tercera pila para los parámetros de punto flotante.

Estructura

Una pila de llamadas está compuesto de stack frames (marcos de pila) (a veces llamados registros de activación). Estos son estructuras de datos dependientes de la máquina que contienen la información de estado de la subrutina. Cada stack frame corresponde a una llamada a una subrutina que activa, es decir, que todavía no ha terminado con un retorno a quien la llamó. Por ejemplo, si una subrutina llamada DrawLine está corriendo actualmente, acabando de ser llamada por una subrutina DrawSquare, la parte superior de la pila de llamadas puede presentarse como esto (donde la pila está creciendo de abajo hacia arriba):

El stack frame en el tope de la pila (en verde) es para la rutina actualmente en ejecución (DrawLine). En el más común acercamiento para el stack frame e incluye:

  • el espacio para las variables locales de la rutina,
  • la dirección de retorno del que llama a la rutina, y
  • los valores de los parámetros pasados a la rutina.

La pila es a menudo accedida vía un registro llamado el puntero de pila (ver registro de pila), que también sirve para indicar al tope actual de la pila. Alternativamente, la memoria dentro del frame (marco) puede ser accedida vía un registro separado, a menudo llamado el frame pointer (puntero del frame), que típicamente apunta a un cierto lugar fijo en la estructura del frame, tal como la localización de la dirección de retorno.

Los stack frames no son todos del mismo tamaño. Diferentes subrutinas tienen diferente número de parámetros, de modo que esa parte del stack frame será diferente para diversas subrutinas, aunque usualmente es fijo a través de todas las activaciones de una subrutina particular. Similarmente, la cantidad de espacio necesario para las variables locales será diferente para diversas subrutinas. De hecho, algunos lenguajes soportan asignaciones dinámicas de memoria para las variables locales en la pila, en este caso el tamaño del área para las variables locales varía de una a otra activación de una subrutina, y no es conocida cuando es compilada la subrutina. En el último caso, el acceso vía un puntero de frame, en vez de a través del puntero de pila, es usualmente necesario puesto que los desplazamientos relativos (offsets) desde el tope de la pila a valores tales como la dirección de retorno no serían conocidas en tiempo de compilación.

En muchos sistemas un stack frame tiene un campo para contener el valor anterior del registro del puntero del frame, es decir, el valor que tenía con el programa, que llamó a la subrutina, mientras estaba ejecutándose. Por ejemplo, en el diagrama de arriba, el stack frame de DrawLine (en verde) tendría una posición de memoria manteniendo el valor del puntero del frame que DrawSquare (en azul) está utilizando. El valor es guardado al entrar en la subrutina y es restaurado pare el retorno. Tener tal campo en una localización conocida del stack frame permite que el código tenga acceso a cada frame sucesivamente por debajo el frame de la rutina actualmente en ejecución.

Los lenguajes de programación que soportan subrutinas anidadas tienen un campo en el frame de llamada que apunta al frame de llamada de la rutina externa que invocó la rutina (anidada) interna. Esto a veces llamado un display.[1] Este apuntador proporciona a las rutinas internas (así como cualesquiera otras rutinas internas que pueda invocar) el acceso a los parámetros y las variables locales de la rutina externa (la que invoca). Algunos computadores, tales como los grandes sistemas de Burroughs, tienen "registros de display" especiales para soportar tales funciones anidadas.

Para algunos propósitos, el stack frame de una subrutina y el de la rutina que la llama pueden ser considerados como un solapado (overlap), el solapado consiste en el área donde los parámetros son pasados desde la rutina que llama a la rutina que es llamada. En algunos ambientes, la rutina que llama, empuja (push) cada argumento sobre la pila, extendiendo así su stack frame; después invoca a la subrutina (la cual usará esos parámetros). En otros ambientes, la rutina que llama tiene un área preasignada en el tope de su stack frame para mantener los argumentos que suministra a otras subrutinas que llama. Esta área a veces son llamadas el área de argumentos salientes o el callout area. Bajo este acercamiento, el tamaño del área es calculado por el compilador para ser la más grande necesaria para cualquier subrutina llamada.

Manejo de la pila

Procesamiento en el sitio de llamada

La manipulación de la pila de llamadas que se necesita en el lugar donde se realiza la llamada a una subrutina es mínima (lo que es bueno puesto que pueden haber muchos lugares de donde se llama cada subrutina). Los valores para los argumentos reales son evaluados en el sitio de la llamada, puesto que son específicos para una particular llamada, y pueden ser o empujados (push) sobre la pila o colocados en los registros, según lo determinado por la convención de llamada utilizada. La instrucción de llamada real, tal como "Branch and link" es entonces típicamente ejecutada para transferir el control al código de la subrutina de destino.

Procesamiento dentro de la rutina llamada

En la subrutina que ha sido llamada, el primer código ejecutado es usualmente llamado el prólogo de la subrutina, puesto que hace el trabajo necesario antes de que comience el código para las sentencias de la rutina.

El prólogo comúnmente guardará la dirección de retorno, dejado en un registro por la instrucción de llamada, empujando (push) dicho valor sobre la pila de llamadas. Similarmente, los valores actuales del puntero de pila o del puntero del frame pueden ser empujados (push) a la pila. Alternativamente, algunas arquitecturas de conjunto de instrucciones, proporcionan automáticamente la funcionalidad comparable, como parte de la acción de la instrucción de llamada en sí misma, y en tal ambiente, el prólogo no necesita hacer esto.

Si están siendo usados los punteros de frame, el prólogo típicamente fijará el nuevo valor del registro del puntero de frame desde el puntero de pila. El espacio en la pila para las variables locales entonces puede ser asignado incrementalmente cambiando así al puntero de pila.

El lenguaje de programación Forth, permite el bobinado explícito de la pila de llamadas (llamada en Forth el «pila de retorno»). El lenguaje de programación del Scheme, permite el bobinado de frames especiales en la pila, a través de un «viento dinámico».

Procesamiento de retorno

Cuando una subrutina está lista para retornar, ejecuta un epílogo que deshace los pasos del prólogo. Esto típicamente restaurará los valores de registros previamente guardados (tales como el valor del puntero del frame) tomándolos desde el frame de la pila, descargará (pop) todo el frame de la pila cambiando el valor del puntero de pila, y finalmente bifurcará a la instrucción indicada en la dirección de retorno. Bajo muchas convenciones de llamada, entre los elementos eliminados (pop) de la pila por el epílogo, incluyen los valores originales de los argumentos con que fue llamada la rutina, en este caso, usualmente no hay otras manipulaciones de la pila que necesiten ser hechas por la subrutina que llama. Sin embargo, con algunas convenciones de llamada, es la responsabilidad de la rutina que llama quitar los argumentos de la pila después del retorno.

Desenrollado

El Retorno de la función llamada hará una remoción (pop) del frame en el tope de la pila, quizás dejando un valor de retorno.

Algunos lenguajes (como Pascal) permiten una sentencia goto global para transferir el control fuera de una función anidada y llevarlo hacia dentro de función externa previamente invocada. Esta operación requiere que la pila sea desenrolado, quitando tantos frames de pila como sea necesario para restaurar el contexto apropiado para transferir el control a la declaración de destino dentro de la función externa que la envuelve. Tales transferencias de control son generalmente usadas solo para el tratamiento de errores.

Otras lenguajes (tales como Object Pascal) proporcionan el manejo de excepciones, que también requiere desenrollar la pila. El stack frame de una función contiene una o más entradas que especifican manejadores de excepción. Cuando una excepción es lanzada, se desenrolla la pila hasta que es encontrado un manejador de excepción que esté preparado para manejar (catch) dicha excepción. El Common Lisp permite el control de lo que sucede cuando la pila es desenrollada usando el operador especial unwind-protect.

Cuando se aplica una continuación, la pila es desenrollada y después rebobinado con la pila de la continuación. Esta no es la única manera de ejecutar continuaciones; por ejemplo, usando múltiples pilas explícitas, la aplicación de una continuación pueden simplemente activar su pila y enrollar un valor que será pasado.

Las pilas de llamadas y el software de pruebas

Una técnica recientemente divulgada[2] usa las pilas de llamadas en una manera diferente que otras discutidas en esta página. Se utiliza las pilas de llamadas para la reducción del juego de pruebas. Brevemente, la reducción del juego de pruebas busca reducir el número de casos de pruebas en un juego de pruebas mientras que retiene un alto porcentaje de la efectividad de la detección de falla del juego original. Dos casos de pruebas son considerados equivalentes si generan el mismo conjunto de pilas de llamadas durante la ejecución. Para más detalles, ver ([3]).

Análisis de desempeño

Tomando muestras en tiempos aleatorios de la pila de llamadas puede ser muy útil para optimizar el desempeño de los programas. La razón es que si una instrucción de llamada a subrutina aparece en la pila de llamadas en una cierta fracción del tiempo de ejecución, su posible remoción pudiera ahorrar esa cantidad de tiempo. Ver análisis de desempeño y muestreo profundo.

Seguridad

La mezcla de los datos del flujo de control que afectan la ejecución del código (direcciones de retorno, punteros de frame guardados) y datos simples del programa (parámetros, valores de retorno) en una pila de llamadas es un riesgo de seguridad, posiblemente explotable por medio del desbordamiento de búfer (en el artículo son explicados el riesgo y el exploit).

Referencias
  1. c2:AlternativeMicroprocessorDesign
  2. “Call Stack Coverage for GUI Test-Suite Reduction” by Scott McMaster and Atif M. Memon. In Proceedings of the 17th IEEE International Symposium on Software Reliability Engineering (ISSRE 2006), Nov. 2006.
  3. “Call-Stack Coverage for GUI Test-Suite Reduction” by Scott McMaster and Atif M. Memon. IEEE Trans. Softw. Eng., 2008, IEEE Press.

Véase también

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.