pila de llamadas

En informática , una pila de llamadas es una estructura de datos que almacena información sobre las subrutinas activas y los bloques en línea de un programa . 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 ". Si bien el mantenimiento de la pila de llamadas es importante para el correcto funcionamiento de la mayoría del software , los detalles suelen estar ocultos y ser automáticos en los lenguajes de programación de alto nivel . Muchos conjuntos de instrucciones informáticas 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 llevar un registro del punto al que cada subrutina activa debe devolver el control cuando termina su ejecución. Una subrutina activa es aquella que ha sido llamada, pero aún no ha completado su ejecución, después de lo cual el control debe devolverse al punto de llamada. Dichas activaciones de subrutinas pueden estar anidadas a cualquier nivel (recursivas como caso especial), de ahí la estructura de pila. Por ejemplo, si una subrutina DrawSquarellama a otra subrutina DrawLinedesde cuatro lugares diferentes, DrawLinedebe saber dónde regresar cuando su ejecución finaliza. Para lograr esto, la dirección que sigue a la instrucción que salta a DrawLine, la dirección de retorno , se agrega a la parte superior de la pila de llamadas como parte de cada llamada.

Descripción

Dado que la pila de llamadas está organizada como una pila , quien llama a un procedimiento, o el prólogo de dicho procedimiento, coloca la dirección de retorno en la pila, y la subrutina llamada, al finalizar, extrae o elimina la dirección de retorno de la pila de llamadas y transfiere el control a esa dirección. De manera similar, el prólogo de un bloque en línea coloca un marco de pila y el epílogo lo extrae. Si una subrutina llamada llama a otra subrutina, colocará 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 proceso de inserción consume todo el espacio asignado a la pila de llamadas, se produce un error llamado desbordamiento de pila , que generalmente provoca que el programa falle . Agregar una entrada de un bloque o subrutina a la pila de llamadas se denomina a veces "enrollar", y eliminar entradas se denomina "desenrollar".

Normalmente, existe una única pila de llamadas asociada a un programa en ejecución (o, más precisamente, a cada tarea o hilo de un proceso ), aunque pueden crearse pilas adicionales para el manejo de señales o la multitarea cooperativa (como en el caso de `setcontext` ). Dado que solo existe 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 forma más explícita que a la pila de llamadas y se la suele denominar pila (véase más abajo).

En los lenguajes de programación de alto nivel , los detalles de la pila de llamadas suelen estar ocultos para el programador. Este solo tiene acceso a un conjunto de funciones, no a la memoria de la pila en sí. Este es un ejemplo de abstracción . La mayoría de los lenguajes ensamblador , en cambio, requieren que el programador manipule la pila. Los detalles de la pila en un lenguaje de programación dependen del compilador , el sistema operativo y el conjunto de instrucciones disponible .

Funciones de la pila de llamadas

Como se mencionó 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 realiza la llamada puede reanudarse posteriormente 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 inicio de la subrutina llamada o en alguna otra ubicación fija. Una de ellas es que cada tarea puede tener su propia pila, y por lo tanto la subrutina puede ser segura para subprocesos , es decir, puede estar activa simultáneamente para diferentes tareas que realizan diferentes cosas. Otro beneficio es que, al proporcionar reentrada , se admite automáticamente la recursión . Cuando una función se llama a sí misma recursivamente, se debe almacenar una dirección de retorno para cada activación de la función para que pueda usarse posteriormente 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, incluyendo, por ejemplo:

Almacenamiento local de datos: Una subrutina suele necesitar espacio de memoria para almacenar los valores de las variables locales , aquellas que solo se conocen dentro de la subrutina activa y no conservan su valor tras su finalización. A menudo, resulta conveniente asignar espacio para este fin simplemente desplazando la parte superior de la pila lo suficiente. Esto es mucho más rápido que la asignación dinámica de memoria , que utiliza el espacio del montón . Cabe destacar que cada activación independiente de una subrutina obtiene su propio espacio en la pila para las variables locales.; De forma similar, un bloque en línea puede asignar un marco de pila para variables locales. Al igual que con un marco de llamada, los valores se pierden cuando finaliza el bloque.
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 el espacio para estos parámetros se pueda establecer en la pila de llamadas. Generalmente, si hay solo unos pocos parámetros pequeños, se utilizarán 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 de 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 suelen almacenarse en registros y procesarse allí. Sin embargo, en algunos casos, los operandos pueden apilarse hasta una profundidad arbitraria, lo que implica el uso de recursos adicionales además de los 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 la subrutina envolvente: Algunos lenguajes de programación (por ejemplo, Pascal y Ada ) admiten la declaración de subrutinas anidadas , las cuales pueden acceder al contexto de sus rutinas contenedoras, es decir, a los parámetros y variables locales dentro del ámbito de las rutinas externas. Este anidamiento estático puede repetirse (una función declarada dentro de otra función, que a su vez se declara dentro de otra función...). La implementación debe proporcionar un mecanismo para que una función llamada en cualquier nivel de anidamiento estático pueda hacer referencia al marco de pila contenedor en cada nivel de anidamiento contenedor. Esta referencia se implementa comúnmente mediante un puntero al marco de pila de la instancia más reciente de la función contenedora, denominado "enlace de pila descendente" o "enlace estático", para distinguirlo del "enlace dinámico" que hace referencia a la función que realiza la llamada inmediata (que no necesariamente tiene que ser la función padre estática).; En lugar de un enlace estático, las referencias a los marcos estáticos que los contienen se pueden agrupar en una matriz de punteros conocida como display , la cual se indexa para localizar el marco deseado. La profundidad del anidamiento léxico de una rutina es una constante conocida, por lo que el tamaño del display de una rutina es fijo. Asimismo, se conoce el número de ámbitos que se deben recorrer, y el índice del display también es fijo. Normalmente, el display de una rutina se ubica en su propio marco de pila, pero el Burroughs B6500 implementó dicho display en un hardware que admitía hasta 32 niveles de anidamiento estático.; Las entradas de visualización que indican los ámbitos de contenido se obtienen del prefijo apropiado de la visualización del llamador. Una rutina interna recursiva 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, como ALGOL 60 o PL/I , un bloque dentro de un procedimiento puede tener sus propias variables locales, que se asignan al entrar en el bloque y se liberan al salir de él. Del mismo modo, el bloque puede tener sus propios manejadores de excepciones, que se desactivan 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 deban restaurarse cuando una subrutina finaliza. Esto podría incluir aspectos como el nivel de privilegios, la información de manejo de excepciones, los modos aritméticos, etc. Si es necesario, esta información puede almacenarse en la pila de llamadas, al igual que la dirección de retorno.

The typical call stack is used for the return address, locals, and parameters (known as a call frame). In some environments there may be more or fewer functions assigned to the call stack. In the Forth programming language, for example, ordinarily only the return address, counted loop parameters and indexes, and possibly local variables are stored on the call stack (which in that environment is named the return stack), although any data can be temporarily placed there using special return-stack handling code so long as the needs of calls and returns are respected; parameters are ordinarily stored on a separate data stack or parameter stack, typically called the stack in Forth terminology even though there is a call stack since it is usually accessed more explicitly. Some Forths also have a third stack for floating-point parameters.

Structure

A call stack is composed of stack frames (also called activation records or activation frames). These are machine dependent and ABI-dependent data structures containing subroutine state information. Each stack frame corresponds to an invocation of a subroutine that has not yet completed with a return.^[1] The stack frame at the top of the stack is for the currently executing routine. For example, if a subroutine named DrawLine is currently running, having been called by a subroutine DrawSquare, the top part of the call stack might be laid out like in the adjacent picture.

A diagram like this can be drawn in either direction as long as the placement of the top, and so direction of stack growth, is understood. Architectures differ as to whether call stacks grow towards higher addresses or towards lower addresses, so the logic of any diagram is not dependent on this addressing choice by convention.

While it is actively executing, with its frame at the stack top, a routine can access the information within its frame as needed.^[2] The stack frame typically includes at least the following items (in the order pushed):

the arguments (parameter values) passed to the routine on the call stack (if any);
the return address back to the routine's caller (e.g. in the DrawLine stack frame, an address into DrawSquare's code), if that is saved on the call stack rather than a register; and
space for the local variables of the routine (if any).

Stack and frame pointers

Cuando los tamaños de los marcos de pila pueden variar, como entre diferentes funciones o entre invocaciones de una función en particular, extraer un marco de la pila no constituye un decremento fijo del puntero de pila . Al regresar de la función, el puntero de pila se restaura al valor del puntero de marco , que es el valor del puntero de pila justo antes de que se llamara a la función. Cada marco de pila contiene un puntero de marco que apunta a la parte superior del marco inmediatamente inferior. El puntero de pila es un registro mutable compartido entre todas las invocaciones. El puntero de marco de una invocación dada de una función es una copia del puntero de pila tal como estaba antes de que se invocara la función. ^{[ 3 ]}

La ubicación de los demás campos del marco se puede 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 propio puntero de marco debe definirse inherentemente como un desplazamiento negativo del puntero de pila.

Almacenar la dirección en el marco del llamador

En la mayoría de los sistemas, un marco de pila contiene un campo para almacenar el valor anterior del registro del puntero de marco, es decir, el valor que tenía mientras se ejecutaba la función que lo llamó. Por ejemplo, el marco de pila DrawLinetendría una ubicación de memoria que almacena el valor del puntero de marco que DrawSquareutiliza (no se muestra en el diagrama anterior). Este valor se guarda al entrar en la subrutina. Disponer de dicho campo en una ubicación conocida del marco de pila permite que el código acceda sucesivamente a cada marco por debajo del marco de la rutina que se está ejecutando, y también permite que la rutina restaure fácilmente el puntero de marco al marco de la función que la llamó , justo antes de regresar.

Rutinas anidadas léxicamente

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 llamado, es decir, el ámbito inmediato del llamado. Esto se denomina enlace de acceso o enlace estático (ya que realiza un seguimiento del anidamiento estático 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 anidamiento. Algunas arquitecturas, compiladores o casos de optimización almacenan un enlace para cada nivel de contención (no solo el inmediatamente contencioso), de modo que las rutinas profundamente anidadas que acceden a datos superficiales no tengan que recorrer varios enlaces; esta estrategia se suele denominar "visualización". ^{[ 4 ]}

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 ocurre con las funciones puras que se comunican únicamente mediante argumentos y valores de retorno, por ejemplo. Algunos ordenadores históricos, como el 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 el omnipresente x86) simplemente reservan unas pocas palabras en la pila para los punteros, según sea necesario.

Superposición

Para ciertos fines, el marco de pila de una subrutina y el de su llamador pueden considerarse superpuestos, correspondiendo esta superposición al área donde se pasan los parámetros de la función que llama a la función llamada. En algunos entornos, la función que llama coloca cada argumento en la pila, extendiendo así su marco de pila, y luego invoca a la función llamada. En otros entornos, la función que llama dispone de un área preasignada en la parte superior de su marco de pila para almacenar los argumentos que proporciona a otras subrutinas que llama. Esta área se denomina a veces área de argumentos de salida o área de llamada . En este enfoque, el compilador calcula el tamaño de esta área para que sea el mayor necesario para cualquier subrutina llamada.

Usar

Procesamiento del sitio de llamadas

Por lo general, la manipulación de la pila de llamadas necesaria en el punto de llamada a una subrutina es mínima (lo cual es conveniente, ya que puede haber múltiples puntos de llamada para cada subrutina). Los valores de los argumentos se evalúan en el punto de llamada , dado que son específicos de esa llamada en particular, y se almacenan en la pila o en registros, según la convención de llamada utilizada . A continuación, se ejecuta la instrucción de llamada propiamente dicha, como "saltar y enlazar", para transferir el control al código de la subrutina de destino.

Procesamiento de entrada de subrutinas

En la subrutina llamada, el primer código que se ejecuta se suele denominar prólogo de la subrutina , ya que realiza las tareas de mantenimiento necesarias antes de que comience el código de las instrucciones de la rutina.

En arquitecturas de conjuntos de instrucciones donde la instrucción utilizada para llamar a una subrutina coloca la dirección de retorno en un registro, en lugar de apilarla, el prólogo suele guardar la dirección de retorno apilando el valor en la pila de llamadas. Sin embargo, si la subrutina llamada no llama a ninguna otra rutina, puede dejar el valor en el registro. De manera similar, los valores actuales del puntero de pila y/o del puntero de marco pueden apilarse.

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. A continuación, se puede asignar espacio en la pila para variables locales modificando incrementalmente el puntero de pila.

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

Procesamiento de devoluciones

Cuando una subrutina está lista para regresar, ejecuta un epílogo que deshace los pasos del prólogo. Esto generalmente restaura los valores de registro guardados (como el valor del puntero de pila) desde el marco de pila, elimina todo el marco de pila de la pila modificando el valor del puntero de pila y, finalmente, salta a la instrucción en la dirección de retorno. Según muchas convenciones de llamada, los elementos eliminados de la pila por el epílogo incluyen los valores de los argumentos originales, en cuyo caso normalmente no es necesario que quien llama realice más manipulaciones de la pila. Sin embargo, con algunas convenciones de llamada, es responsabilidad de quien llama eliminar los argumentos de la pila después del retorno.

Relajación

Al regresar de la función llamada, se extrae el marco superior de la pila, posiblemente dejando un valor de retorno. La acción más general de extraer 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 usan 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 una instrucción goto global para transferir el control de una función anidada a una función externa previamente invocada. Esta operación requiere que la pila se desenrolle, eliminando tantos marcos de pila como sea necesario para restaurar el contexto adecuado para transferir el control a la instrucción de destino dentro de la función externa contenedora. De manera similar, C tiene las funciones setjmpylongjmp que actúan como gotos no locales. Common Lisp permite controlar lo que sucede cuando la pila se desenrolla mediante el uso del unwind-protectoperador especial.

Al aplicar una continuación , la pila se desenrolla (lógicamente) y luego se vuelve a enrollar con la pila de la continuación. Esta no es la única forma de implementar continuaciones; por ejemplo, utilizando varias 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 thunks arbitrarios en puntos específicos al desenrollar o rebobinar la pila de control cuando se invoca una continuación.

Inspección

En ocasiones, se puede inspeccionar la pila de llamadas mientras el programa se está ejecutando. Dependiendo de cómo esté escrito y compilado el programa, la información de la pila puede utilizarse para determinar valores intermedios y trazas de llamadas a funciones. Esto se ha utilizado para generar pruebas automatizadas de grano fino ^{[ 5 ]} y, en casos como Ruby y Smalltalk , para implementar continuaciones de primera clase. Por ejemplo, el depurador GNU (GDB) implementa la inspección interactiva de la pila de llamadas de un programa C en ejecución, pero pausado ^{[ 6 ] .}

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

Seguridad

En un lenguaje con punteros libres o escrituras de matrices no verificadas (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 de programa simples (parámetros o valores de retorno) en una pila de llamadas es un riesgo de seguridad y puede ser explotable a través de desbordamientos de búfer de pila , que son el tipo más común de desbordamiento de búfer .

Un ataque de este tipo consiste en llenar un búfer con código ejecutable arbitrario y, a continuación, desbordar este u otro búfer para sobrescribir una dirección de retorno con un valor que apunta directamente al código ejecutable. Como resultado, cuando la función finaliza, el ordenador ejecuta dicho código. Este tipo de ataque puede bloquearse con W^X , pero ataques similares pueden tener éxito incluso con la protección W^X habilitada, incluyendo el ataque de retorno a libc o los ataques derivados de la programación orientada a retorno . Se han propuesto diversas medidas de mitigación, como almacenar los arrays en una ubicación completamente separada de la pila de retorno, como ocurre en el lenguaje de programación Forth. ^[⁷^]

Véase también

Referencias

↑ "Examinando la pila" . Universidad de Utah . Archivado del original el 12 de septiembre de 2019. Recuperado el 3 de abril de 2025 .
↑ Krzyzanowski, Paul (16 de febrero de 2018). "Marcos de pila" . Universidad de Rutgers . Archivado del original el 28 de agosto de 2021. Recuperado el 19 de diciembre de 2021 .
↑ "Understanding the Stack" . cs.umd.edu . 22 de junio de 2003. Archivado del original el 25 de febrero de 2013. Consultado el 21 de mayo de 2014 .
↑ Diseño alternativo de microprocesadores
↑ McMaster, S.; Memon, A. (2006). Cobertura de la pila de llamadas para la reducción de conjuntos de pruebas de interfaz gráfica de usuario (PDF) . 17.º Simposio Internacional sobre Ingeniería de Confiabilidad de Software ( ISSRE '06). págs. 33–44 . CiteSeerX 10.1.1.88.873 . doi : 10.1109/ISSRE.2006.19 . ISBN 0-7695-2684-5.
↑ "Depuración con GDB: Examinando la pila" . chemie.fu-berlin.de . 17 de octubre de 1997. Archivado del original el 14 de abril de 2021. Consultado el 16 de diciembre de 2014 .
↑ Doug Hoyte. "El lenguaje de programación Forth: por qué DEBERÍAS aprenderlo" .

Lecturas adicionales

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 revisión y análisis crítico". Memory Management . Lecture Notes in Computer Science. Vol. 986. pp. 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) del original el 1 de marzo de 2020. Consultado el 2 de marzo de 2020 . (Nota: El procesador Intel 4004 de 4 bits implementa una pila interna en lugar de una pila en memoria).

Enlaces externos

Llamada a funciones y operaciones con punteros de marco en el procesador 68000. Archivado el 24 de julio de 2010 en la Wayback Machine.
El proyecto libunwind : una API de desenrollado independiente de la plataforma

[1] "Examinando la pila" . Universidad de Utah . Archivado del original el 12 de septiembre de 2019. Recuperado el 3 de abril de 2025 .

[2] Krzyzanowski, Paul (16 de febrero de 2018). "Marcos de pila" . Universidad de Rutgers . Archivado del original el 28 de agosto de 2021. Recuperado el 19 de diciembre de 2021 .

[3] "Understanding the Stack" . cs.umd.edu . 22 de junio de 2003. Archivado del original el 25 de febrero de 2013. Consultado el 21 de mayo de 2014 .

[4] Diseño alternativo de microprocesadores

[5] McMaster, S.; Memon, A. (2006). Cobertura de la pila de llamadas para la reducción de conjuntos de pruebas de interfaz gráfica de usuario (PDF) . 17.º Simposio Internacional sobre Ingeniería de Confiabilidad de Software ( ISSRE '06). págs. 33–44 . CiteSeerX 10.1.1.88.873 . doi : 10.1109/ISSRE.2006.19 . ISBN 0-7695-2684-5.

[6] "Depuración con GDB: Examinando la pila" . chemie.fu-berlin.de . 17 de octubre de 1997. Archivado del original el 14 de abril de 2021. Consultado el 16 de diciembre de 2014 .

[7] Doug Hoyte. "El lenguaje de programación Forth: por qué DEBERÍAS aprenderlo" .

[1]

[2]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ] .

[