Pila de llamadas

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Pila de llamadas» – noticias  · periódicos  · libros  · académico  · JSTOR ( septiembre de 2012 ) ( Aprenda cómo y cuándo eliminar este mensaje )

En informática , una pila de llamadas es una estructura de datos de pila que almacena información sobre las subrutinas activas de un programa informático . Este tipo de pila también se conoce como pila de ejecución , pila de programa , pila de control , pila de tiempo de ejecución o pila de máquina , y a menudo se abrevia simplemente como " pila ". Aunque el mantenimiento de la pila de llamadas es importante para el correcto funcionamiento de la mayoría del software , los detalles normalmente están ocultos y son automáticos en los lenguajes de programación de alto nivel . Muchos conjuntos de instrucciones de computadora proporcionan instrucciones especiales para manipular pilas.

Una pila de llamadas se utiliza para varios propósitos relacionados, pero la razón principal para tener una es mantener un registro del punto al que cada subrutina activa debe devolver el control cuando termina de ejecutarse. Una subrutina activa es una que ha sido llamada, pero aún debe completar la ejecución, después de lo cual el control debe devolverse al punto de llamada. Tales activaciones de subrutinas pueden estar anidadas en cualquier nivel (recursivas como un caso especial), de ahí la estructura de pila. Por ejemplo, si una subrutina DrawSquarellama a una subrutina DrawLinedesde cuatro lugares diferentes, DrawLinedebe saber dónde regresar cuando se complete su ejecución. Para lograr esto, la dirección que sigue a la instrucción que salta a DrawLine, la dirección de retorno , se inserta en la parte superior de la pila de llamadas como parte de cada llamada.

Dado que la pila de llamadas está organizada como una pila , el llamador inserta la dirección de retorno en la pila y la subrutina llamada, cuando termina, extrae o saca 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, insertará otra dirección de retorno en la pila de llamadas, y así sucesivamente, con la información acumulándose y desapilándose según lo dicte el programa. Si el empuje consume todo el espacio asignado para la pila de llamadas, se produce un error llamado desbordamiento de pila , que generalmente hace que el programa se bloquee . Agregar la entrada de un bloque o subrutina a la pila de llamadas a veces se llama "enrollado" y eliminar entradas "desenrollado".

Normalmente hay exactamente una pila de llamadas asociada con un programa en ejecución (o más precisamente, con cada tarea o hilo de un proceso ), aunque se pueden crear pilas adicionales para el manejo de señales o la multitarea cooperativa (como con setcontext ). Dado que solo hay una en este contexto importante, se la puede denominar pila (implícitamente "de la tarea"); sin embargo, en el lenguaje de programación Forth, se accede a la pila de datos o pila de parámetros de manera más explícita que a la pila de llamadas y se la suele denominar pila (ver a continuación).

En los lenguajes de programación de alto nivel , los detalles específicos de la pila de llamadas suelen estar ocultos para el programador. Solo se le da acceso a un conjunto de funciones, y no a la memoria de la pila en sí. Este es un ejemplo de abstracción . La mayoría de los lenguajes ensambladores , por otro lado, requieren que los programadores participen en la manipulación de la pila. Los detalles reales de la pila en un lenguaje de programación dependen del compilador , el sistema operativo y el conjunto de instrucciones disponible .

Como se señaló anteriormente, el propósito principal de una pila de llamadas es almacenar las direcciones de retorno . Cuando se llama a una subrutina, la ubicación (dirección) de la instrucción en la que la rutina que llama puede reanudarse más tarde debe guardarse en algún lugar. El uso de una pila para guardar la dirección de retorno tiene ventajas importantes sobre algunas convenciones de llamada alternativas , como guardar la dirección de retorno antes del comienzo de la subrutina llamada o en alguna otra ubicación fija. Una es que cada tarea puede tener su propia pila y, por lo tanto, la subrutina puede ser segura para subprocesos , es decir, capaz de estar activa simultáneamente para diferentes tareas que hacen cosas diferentes. Otro beneficio es que al proporcionar reentrada , se admite automáticamente la recursión . Cuando una función se llama a sí misma de forma recursiva, es necesario almacenar una dirección de retorno para cada activación de la función para que luego pueda usarse para regresar de la activación de la función. Las estructuras de pila proporcionan esta capacidad automáticamente.

Dependiendo del idioma, el sistema operativo y el entorno de la máquina, una pila de llamadas puede tener propósitos adicionales, incluidos, por ejemplo:

Almacenamiento de datos local

Una subrutina necesita frecuentemente espacio de memoria para almacenar los valores de las variables locales , las variables que se conocen solo dentro de la subrutina activa y no retienen valores después de que retorna. A menudo es conveniente asignar espacio para este uso simplemente moviendo la parte superior de la pila lo suficiente para proporcionar el espacio. Esto es muy rápido en comparación con la asignación de memoria dinámica , que utiliza el espacio del montón . Tenga en cuenta que cada activación independiente de una subrutina obtiene su propio espacio separado en la pila para las variables locales.

Paso de parámetros

Las subrutinas a menudo requieren que el código que las llama les proporcione valores para los parámetros , y no es raro que se disponga de espacio para estos parámetros en la pila de llamadas. Generalmente, si solo hay unos pocos parámetros pequeños, se utilizarán los registros del procesador para pasar los valores, pero si hay más parámetros de los que se pueden manejar de esta manera, se necesitará espacio en la memoria. La pila de llamadas funciona bien como lugar para estos parámetros, especialmente porque a cada llamada a una subrutina, que tendrá diferentes valores para los parámetros, se le dará un espacio separado en la pila de llamadas para esos valores. En lenguajes orientados a objetos como C++ , la lista de parámetros también puede incluir el thispuntero .

Pila de evaluación

Los operandos para operaciones aritméticas o lógicas se colocan con mayor frecuencia en registros y se operan en ellos. Sin embargo, en algunas situaciones los operandos pueden apilarse hasta una profundidad arbitraria, lo que significa que se debe utilizar algo más que registros (este es el caso del desbordamiento de registros ). La pila de dichos operandos, similar a la de una calculadora RPN , se denomina pila de evaluación y puede ocupar espacio en la pila de llamadas.

Contexto de subrutina envolvente

Algunos lenguajes de programación (por ejemplo, Pascal y Ada ) admiten la declaración de subrutinas anidadas , a las que se les permite acceder al contexto de sus rutinas envolventes, es decir, los parámetros y las variables locales dentro del alcance de las rutinas externas. Tal anidamiento estático puede repetirse (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 anidamiento estático dado pueda hacer referencia al marco envolvente en cada nivel de anidamiento envolvente. Esta referencia se implementa comúnmente mediante un puntero al marco de la instancia activada más recientemente de la función envolvente, llamado "enlace descendente" o "enlace estático", para distinguirlo del "enlace dinámico" que hace referencia al llamador inmediato (que no necesita ser la función padre estática).

En lugar de un enlace estático, las referencias a los marcos estáticos que lo contienen se pueden recopilar en una matriz de punteros conocida como pantalla , que está indexada para ubicar un marco deseado. La profundidad del anidamiento léxico de una rutina es una constante conocida, por lo que el tamaño de la pantalla de una rutina es fijo. Además, se conoce el número de ámbitos de contención que se deben recorrer y el índice en la pantalla también es fijo. Por lo general, la pantalla de una rutina se encuentra en su propio marco de pila, pero Burroughs B6500 implementó una pantalla de este tipo en hardware que admitía hasta 32 niveles de anidamiento estático.

Las entradas de visualización que indican los ámbitos de contención se obtienen del prefijo apropiado de la visualización del invocador. Una rutina interna que recurre crea marcos de llamada separados para cada invocación. En este caso, todos los enlaces estáticos de la rutina interna apuntan al mismo contexto de rutina externa.

Contexto de bloque cerrado

En algunos lenguajes, por ejemplo, ALGOL 60 , PL/I , un bloque dentro de un procedimiento puede tener sus propias variables locales, asignadas al ingresar al bloque y liberadas al salir del mismo. De manera similar, el bloque puede tener sus propios controladores de excepciones, desactivados al salir del bloque.

Otro estado de retorno

Además de la dirección de retorno, en algunos entornos puede haber otros estados de la máquina o del software que se deben restaurar cuando regresa una subrutina. Esto puede incluir elementos como el nivel de privilegio, la información de manejo de excepciones, los modos aritméticos, etc. Si es necesario, esto se puede almacenar en la pila de llamadas al igual que la dirección de retorno.

La pila de llamadas típica se utiliza para la dirección de retorno, variables locales y parámetros (conocida como marco de llamada ). En algunos entornos puede haber más o menos funciones asignadas a la pila de llamadas. En el lenguaje de programación Forth , por ejemplo, normalmente solo la dirección de retorno, los parámetros de bucle contados e índices y posiblemente las variables locales se almacenan en la pila de llamadas (que en ese entorno se denomina pila de retorno ), aunque cualquier dato se puede colocar allí temporalmente utilizando un código especial de manejo de pila de retorno siempre que se respeten las necesidades de las llamadas y los retornos; los parámetros se almacenan normalmente en una pila de datos o pila de parámetros separada , normalmente llamada pila en la terminología de Forth, aunque hay una pila de llamadas, ya que generalmente se accede a ella de forma más explícita. Algunos Forth también tienen una tercera pila para parámetros de punto flotante .

Una pila de llamadas se compone de marcos de pila (también llamados registros de activación o marcos de activación ). Se trata de estructuras de datos dependientes de la máquina y de ABI que contienen información sobre el estado de las subrutinas. Cada marco de pila corresponde a una llamada a una subrutina que aún no ha finalizado con un retorno. Por ejemplo, si una subrutina nombrada DrawLinese está ejecutando actualmente, después de haber sido llamada por una subrutina DrawSquare, la parte superior de la pila de llamadas podría estar dispuesta como en la imagen adyacente.

Un diagrama como este se puede dibujar en cualquier dirección siempre que se comprenda la ubicación de la parte superior y, por lo tanto, la dirección del crecimiento de la pila. Las arquitecturas difieren en cuanto a si las pilas de llamadas crecen hacia direcciones superiores o inferiores, por lo que la lógica de cualquier diagrama no depende de esta elección de direccionamiento por convención.

El marco de pila en la parte superior de la pila es para la rutina que se está ejecutando actualmente, que puede acceder a la información dentro de su marco (como parámetros o variables locales) en cualquier orden. ^[1] El marco de pila generalmente incluye al menos los siguientes elementos (en orden de inserción):

• los argumentos (valores de los parámetros) pasados ​​a la rutina (si hay alguno);
• la dirección de retorno al llamador de la rutina (por ejemplo, en el DrawLinemarco de la pila, una dirección en DrawSquareel código de ); y
• espacio para las variables locales de la rutina (si las hay).

Cuando los tamaños de los marcos de pila pueden diferir, como entre diferentes funciones o entre invocaciones de una función en particular, sacar un marco de la pila no constituye una disminución fija del puntero de pila . En el retorno de la función, el puntero de pila se restaura en su lugar al puntero de marco , el valor del puntero de pila justo antes de que se llamara a la función. Cada marco de pila contiene un puntero de pila a la parte superior del marco inmediatamente inferior. El puntero de pila es un registro mutable compartido entre todas las invocaciones. Un puntero de marco de una invocación dada de una función es una copia del puntero de pila como era antes de que se invocara la función. ^[2]

Las ubicaciones de todos los demás campos del marco se pueden definir en relación con la parte superior del marco, como desplazamientos negativos del puntero de pila, o en relación con la parte superior del marco inferior, como desplazamientos positivos del puntero de marco. La ubicación del puntero de marco en sí debe definirse inherentemente como un desplazamiento negativo del puntero de pila.

En la mayoría de los sistemas, un marco de pila tiene un campo que contiene el valor anterior del registro de puntero de marco, el valor que tenía mientras se ejecutaba el llamador. Por ejemplo, el marco de pila de DrawLinetendría una ubicación de memoria que contiene el valor del puntero de marco que DrawSquareutiliza (no se muestra en el diagrama anterior). El valor se guarda al ingresar a la subrutina. Tener un campo de este tipo en una ubicación conocida en el marco de pila permite que el código acceda a cada marco sucesivamente debajo del marco de la rutina que se está ejecutando actualmente, y también permite que la rutina restaure fácilmente el puntero de marco al marco del llamador , justo antes de que regrese.

Los lenguajes de programación que admiten subrutinas anidadas también tienen un campo en el marco de llamada que apunta al marco de pila de la última activación del procedimiento que encapsula más estrechamente al destinatario de la llamada, es decir, el ámbito inmediato del destinatario de la llamada. Esto se denomina enlace de acceso o enlace estático (ya que realiza un seguimiento de la anidación estática durante las llamadas dinámicas y recursivas) y proporciona a la rutina (así como a cualquier otra rutina que pueda invocar) acceso a los datos locales de sus rutinas encapsulantes en cada nivel de anidación. Algunas arquitecturas, compiladores o casos de optimización almacenan un enlace para cada nivel de inclusión (no solo el inmediatamente inferior), de modo que las rutinas profundamente anidadas que acceden a datos superficiales no tengan que recorrer varios enlaces; esta estrategia a menudo se denomina "visualización". ^[3]

Los enlaces de acceso se pueden optimizar cuando una función interna no accede a ningún dato local (no constante) en la encapsulación, como es el caso de las funciones puras que se comunican solo a través de argumentos y valores de retorno, por ejemplo. Algunas computadoras históricas, como la Electrologica X8 y algo más tarde los grandes sistemas Burroughs , tenían "registros de visualización" especiales para admitir funciones anidadas, mientras que los compiladores para la mayoría de las máquinas modernas (como la omnipresente x86) simplemente reservan algunas palabras en la pila para los punteros, según sea necesario.

Para algunos propósitos, el marco de pila de una subrutina y el de su invocador pueden considerarse superpuestos, y el solapamiento consiste en el área donde los parámetros se pasan del invocador al llamado. En algunos entornos, el invocador inserta cada argumento en la pila, extendiendo así su marco de pila, y luego invoca al llamado. En otros entornos, el invocador tiene un área preasignada en la parte superior de su marco de pila para contener los argumentos que proporciona a otras subrutinas que invoca. Esta área a veces se denomina área de argumentos salientes o área de llamada . Con este enfoque, el compilador calcula el tamaño del área para que sea el mayor que necesite cualquier subrutina llamada.

Por lo general, la manipulación de la pila de llamadas necesaria en el sitio de una llamada a una subrutina es mínima (lo cual es bueno ya que puede haber muchos sitios de llamada para cada subrutina que se va a llamar). Los valores de los argumentos reales se evalúan en el sitio de la llamada, ya que son específicos de la llamada en particular, y se colocan en la pila o en los registros, según lo determine la convención de llamada utilizada . La instrucción de llamada real, como "bifurcar y vincular", se ejecuta generalmente para transferir el control al código de la subrutina de destino.

En la subrutina llamada, el primer código ejecutado normalmente se denomina prólogo de la subrutina , ya que realiza las tareas de mantenimiento necesarias antes de que se inicie el código para las declaraciones de la rutina.

En el caso de arquitecturas de conjuntos de instrucciones en las que la instrucción utilizada para llamar a una subrutina coloca la dirección de retorno en un registro, en lugar de colocarla en la pila, el prólogo normalmente guardará la dirección de retorno colocando el valor en la pila de llamadas, aunque si la subrutina llamada no llama a ninguna otra rutina, puede dejar el valor en el registro. De manera similar, se pueden colocar los valores actuales del puntero de pila y/o del puntero de marco.

Si se utilizan punteros de marco, el prólogo normalmente establecerá el nuevo valor del registro del puntero de marco a partir del puntero de pila. Luego, se puede asignar espacio en la pila para variables locales modificando de forma incremental el puntero de pila.

El lenguaje de programación Forth permite el bobinado explícito de la pila de llamadas (llamada allí "pila de retorno").

Cuando una subrutina está lista para regresar, ejecuta un epílogo que deshace los pasos del prólogo. Esto normalmente restaurará los valores de registro guardados (como el valor del puntero de marco) del marco de pila, sacará todo el marco de pila de la pila cambiando el valor del puntero de pila y, finalmente, se ramificará a la instrucción en la dirección de retorno. Según muchas convenciones de llamada, los elementos que el epílogo saca de la pila incluyen los valores de los argumentos originales, en cuyo caso, por lo general, el llamador no necesita realizar más manipulaciones en la pila. Sin embargo, con algunas convenciones de llamada, es responsabilidad del llamador eliminar los argumentos de la pila después del retorno.

Al regresar de la función llamada, se sacará el marco superior de la pila, dejando quizás un valor de retorno. El acto más general de sacar uno o más marcos de la pila para reanudar la ejecución en otra parte del programa se denomina desenrollado de pila y debe realizarse cuando se utilizan estructuras de control no locales, como las que se utilizan para el manejo de excepciones . En este caso, el marco de pila de una función contiene una o más entradas que especifican manejadores de excepciones. Cuando se lanza una excepción, la pila se desenrolla hasta que se encuentra un manejador que esté preparado para manejar (capturar) el tipo de excepción lanzada.

Algunos lenguajes tienen otras estructuras de control que requieren un desenrollado general. Pascal permite que una sentencia goto global transfiera el control desde una función anidada a una función externa invocada previamente. Esta operación requiere que se desenrolle la pila, eliminando tantos marcos de pila como sean necesarios para restaurar el contexto adecuado para transferir el control a la sentencia de destino dentro de la función externa que la encierra. De manera similar, C tiene las funciones setjmpylongjmp que actúan como gotos no locales. Common Lisp permite controlar lo que sucede cuando se desenrolla la pila mediante el unwind-protectoperador especial.

Al aplicar una continuación , la pila se desenrolla (lógicamente) y luego se rebobina con la pila de la continuación. Esta no es la única forma de implementar continuaciones; por ejemplo, al usar múltiples pilas explícitas, la aplicación de una continuación puede simplemente activar su pila y enrollar un valor que se pasará. El lenguaje de programación Scheme permite ejecutar fragmentos arbitrarios en puntos específicos al "desenrollar" o "rebobinar" la pila de control cuando se invoca una continuación.

En ocasiones, la pila de llamadas se puede inspeccionar mientras se ejecuta el programa. Según cómo se escriba y compile el programa, la información de la pila se puede utilizar para determinar valores intermedios y rastros de llamadas a funciones. Esto se ha utilizado para generar pruebas automatizadas de grano fino ^[4] y, en casos como Ruby y Smalltalk, para implementar continuaciones de primera clase. Como ejemplo, el depurador GNU (GDB) implementa la inspección interactiva de la pila de llamadas de un programa C en ejecución, pero en pausa ^{[5] .}

Tomar muestras regulares de la pila de llamadas puede ser útil para perfilar el rendimiento de los programas ya que, si la dirección de una subrutina aparece en los datos de muestreo de la pila de llamadas muchas veces, es probable que actúe como un cuello de botella en el código y se debe inspeccionar para detectar problemas de rendimiento.

En un lenguaje con punteros libres o escrituras de matriz no controladas (como en C), la mezcla de datos de flujo de control que afectan la ejecución del código (las direcciones de retorno o los punteros de marco guardados) y datos simples del programa (parámetros o valores de retorno) en una pila de llamadas es un riesgo de seguridad, y posiblemente se pueda explotar a través de desbordamientos de búfer de pila , que son el tipo más común de desbordamiento de búfer .

Uno de estos ataques consiste en llenar un búfer con código ejecutable arbitrario y luego desbordar este u otro búfer para sobrescribir alguna dirección de retorno con un valor que apunta directamente al código ejecutable. Como resultado, cuando la función retorna, la computadora ejecuta ese código. Este tipo de ataque se puede bloquear con W^X , ^{[ cita requerida ]} pero ataques similares pueden tener éxito incluso con la protección W^X habilitada, incluido el ataque de retorno a libc o los ataques provenientes de la programación orientada al retorno . Se han propuesto varias mitigaciones, como almacenar matrices en una ubicación completamente separada de la pila de retorno, como es el caso en el lenguaje de programación Forth. ^[6]

• Dijkstra, EW (1960). "Programación recursiva". Matemática numérica . 2 (1): 312–318. doi :10.1007/BF01386232.
• Wilson, PR; Johnstone, MS; Neely, M.; Boles, D. (1995). "Asignación dinámica de almacenamiento: una encuesta y una revisión crítica". Memory Management . Lecture Notes in Computer Science. Vol. 986. págs. 1–116. CiteSeerX  10.1.1.47.275 . doi :10.1007/3-540-60368-9_19. ISBN 978-3-540-60368-9.
• "2.4. La pila". Manual de programación en lenguaje ensamblador MCS-4 - Manual de programación del sistema de microcomputadoras INTELLEC 4 (PDF) (edición preliminar). Santa Clara, California, EE. UU.: Intel Corporation . Diciembre de 1973. págs. 2-7–2-8. MCS-030-1273-1. Archivado (PDF) desde el original el 2020-03-01 . Consultado el 2020-03-02 .(NB. El procesador 4004 de 4 bits de Intel implementa una pila interna en lugar de una pila en memoria).

• Llamadas de funciones y operaciones con puntero de marco en 68000 Archivado el 24 de julio de 2010 en Wayback Machine
• El proyecto libunwind: una API de desenrollado independiente de la plataforma