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 conocida como una pila de ejecución, pila de programa, pila de control, pila de función, o pila de tiempo de ejecución, y a menudo se describe simplemente como "la pila". Aunque el mantenimiento de la pila de llamadas es importante para el correcto funcionamiento de la mayoría de programas, los detalles por lo general están ocultos y de forma automática en los lenguajes de alto nivel. Muchos conjuntos de instrucciones de computadora proveen instrucciones especiales para manipular pilas.

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 luego de la sentencia de llamada particular (la "dirección de retorno") en la pila de llamadas.

Descripción

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 asociada 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 referida como la pila (implícita, "de la tarea").

En lenguajes de programación de alto nivel, las características específicas de la pila de llamadas usualmente son ocultas al programador. Ellos sólo 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 directa 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 se llama una subrutina, la localización de la instrucción para retornar necesita guardarse 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 distintas tareas que hacen cosas diferentes. Otro beneficio es que la recursividad se soporta automáticamente. Cuando una función se llama a sí misma (recursivamente), una dirección de retorno necesita almacenarse para cada activación de tal función, de tal manera de poder usarla luego para retornar desde 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. Por lo general, si solamente hay algunos pequeños parámetros, los registros del procesador se usarán para pasar los valores, pero si hay más parámetros de los que se pueda manejar de esta manera, será necesario espacio en 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 aparte 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 puestos en un registro y operados allí. Sin embargo, en algunas situaciones los operandos pueden ser apilados hasta una profundidad arbitraria, lo que significa que se debe usar 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 se usa 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á compuesta de marcos de pila (stack frames - a veces llamados registros de activación). Estas 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 (DibujaLinea) se ejecuta actualmente, acabando de ser llamada por una subrutina DrawSquare (DibujaCuadrado), 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 incluye:

el espacio para las variables locales de la rutina,
la dirección de retorno del que llama a la rutina (p.e. en el marco de pila DrawLine, una dirección dentro del código de DrawSquare), y
los valores de los parámetros pasados a la rutina (si los hay).

La pila se accede a menudo mediante un registro llamado puntero de pila (Stack Pointer) (ver registro de pila), que también sirve para indicar al tope actual de la pila. Alternativamente, la memoria dentro del marco de pila (Stack Frame) se puede acceder mediante un registro separado, a menudo llamado puntero del marco (Frame Pointer); típicamente apunta a un cierto lugar fijo en la estructura del marco, tal como la localización de la dirección de retorno.

No todos los stack frames tienen el 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 se fija a través de todas las activaciones de una subrutina en particular. De igual forma, la cantidad de espacio necesaria 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 se estaba ejecutando. Por ejemplo, en el diagrama de arriba, el marco de pila de DrawLine (en verde) tendría una posición de memoria manteniendo el valor del puntero del marco 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 marco de pila 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 marco de pila; 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 marco de pila para mantener los argumentos que suministra a otras subrutinas que llama. Esta área a veces se entiende por el área de argumentos salientes o el callout area. Bajo este punto, el área se calcula mediante el compilador para ser tan grande como sea necesario para cualquier llamado a subrutina.

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.

Usos

Procesamiento dentro de la rutina llamada

En la subrutina que ha sido llamada, al primer código ejecutado se le llama 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 marco pueden empujarse (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 del marco, el prólogo típicamente fijará el nuevo valor del registro del puntero del marco desde el puntero de pila. Entonces, el espacio en la pila para las variables locales puede asignarse 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 la «pila de retorno»). El lenguaje de programación del Scheme, permite el bobinado de marcos especiales en la pila, a través de un «reembobinado».

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 marco) tomándolos desde el marco de pila, descargará (pop) todo el marco 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, se 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 marco 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 marcos de pila como se necesiten 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 se usan generalmente sólo para el tratamiento de errores.

Otras lenguajes (tales como Object Pascal/Delphi) proporcionan el manejo de excepciones, que también requiere desenrollar la pila. El marco de pila 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 se encuentra un manejador de excepción que esté preparado para atrapar (catch) tal 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 se desenrolla y después rebobina 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 de una manera diferente a otras discutidas en esta página. Se usa 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

↑ c2:AlternativeMicroprocessorDesign
↑ “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.
↑ “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

Stack Frame Allocation on MSDN
Function Calling and Frame Pointer Operations in 68000 Archivado el 24 de julio de 2010 en Wayback Machine.

Datos: Q759899

[1] 2: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.

[1]

[2]

[3]