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 de computadora . 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 " la 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 realizar un seguimiento del punto al que cada subrutina activa debe devolver el control cuando termina de ejecutarse. 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 anidarse en cualquier nivel (recursivo como 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 coloca en la parte superior de la pila de llamadas con cada llamada.
Dado que la pila de llamadas está organizada como una pila , la persona que llama inserta la dirección del remitente en la pila y la subrutina llamada, cuando termina, extrae o saca la dirección del remitente de la pila de llamadas y transfiere el control a esa dirección. Si una subrutina llamada llama a otra subrutina, enviará otra dirección de retorno a la pila de llamadas, y así sucesivamente, con la información apilándose y desapilándose según lo dicte el programa. Si la inserción consume todo el espacio asignado para la pila de llamadas, se produce un error llamado desbordamiento de pila , que generalmente provoca que el programa se bloquee . Agregar la entrada de un bloque o subrutina a la pila de llamadas a veces se denomina "desenrollar" y eliminar entradas "desenrollar".
Generalmente hay exactamente una pila de llamadas asociada con un programa en ejecución (o más exactamente, con cada tarea o subproceso de un proceso ), aunque se pueden crear pilas adicionales para el manejo de señales o la multitarea cooperativa (como con setcontext ). Dado que sólo hay uno en este importante contexto, se le 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 a la pila de parámetros de forma más explícita que a la pila de llamadas y comúnmente se la denomina pila (ver más abajo).
En los lenguajes de programación de alto nivel , los detalles de la pila de llamadas generalmente están ocultos para el programador. Sólo se les 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 posteriormente se puede reanudar la llamada a la rutina debe guardarse en algún lugar. El uso de una pila para guardar la dirección del remitente tiene ventajas importantes sobre algunas convenciones de llamada alternativas , como guardar la dirección del remitente 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 , la recursividad se admite automáticamente. Cuando una función se llama a sí misma de forma recursiva, se debe 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, que incluyen, por ejemplo:
thispuntero .La pila de llamadas típica se utiliza para la dirección de retorno, los locales y los parámetros (conocido 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 sólo la dirección de retorno, los índices y los parámetros del bucle contados 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 temporalmente. allí se utiliza un código especial de manejo de la pila de retorno siempre que se respeten las necesidades de llamadas y devoluciones; Los parámetros normalmente se almacenan en una pila de datos o pila de parámetros separada , generalmente llamada pila en la terminología Forth, aunque hay una pila de llamadas, ya que generalmente se accede a ella de manera más explícita. Algunos Forths también tienen una tercera pila para parámetros de punto flotante .
DrawSquaresubrutina (que se muestra en azul ) llamada DrawLine(que se muestra en verde ), que es la rutina que se está ejecutando actualmenteUna pila de llamadas se compone de marcos de pila (también llamados registros de activación o marcos de activación ). Estas son estructuras de datos dependientes de la máquina y de ABI que contienen información del estado de las subrutinas. Cada marco de pila corresponde a una llamada a una subrutina que aún no ha terminado con un retorno. Por ejemplo, si una subrutina denominada DrawLinese está ejecutando actualmente y ha 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 entienda la ubicación de la parte superior y, por tanto, la dirección del crecimiento de la pila. Las arquitecturas difieren en cuanto a si las pilas de llamadas crecen hacia direcciones más altas o hacia direcciones más bajas, por lo que la lógica de cualquier diagrama no depende de esta elección de dirección por convención.
El marco de la pila en la parte superior de la pila es para la rutina que se está ejecutando actualmente, que puede acceder a información dentro de su marco (como parámetros o variables locales) en cualquier orden. [1] El marco de la pila generalmente incluye al menos los siguientes elementos (en orden de inserción):
DrawLinemarco de la pila, una dirección en el DrawSquarecódigo de 's); yCuando los tamaños de los marcos de la pila pueden diferir, como entre diferentes funciones o entre invocaciones de una función particular, sacar un marco de la pila no constituye una disminución fija del puntero de la pila . En el retorno de la función, el puntero de la pila se restaura al puntero del marco , el valor del puntero de la pila justo antes de que se llamara la función. Cada marco de pila contiene un puntero de pila hacia la parte superior del marco inmediatamente debajo. El puntero de pila es un registro mutable compartido entre todas las invocaciones. Un puntero de marco de una invocación determinada de una función es una copia del puntero de pila tal como estaba antes de que se invocara la función. [2]
Las ubicaciones de todos los demás campos en el 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 del marco. La ubicación del puntero del marco debe definirse inherentemente como un desplazamiento negativo del puntero de la pila.
En la mayoría de los sistemas, un marco de pila tiene un campo que contiene el valor anterior del registro del puntero del marco, el valor que tenía mientras se ejecutaba la persona que llama. Por ejemplo, el marco de pila de DrawLinetendría una ubicación de memoria que contiene el valor del puntero del marco que DrawSquareutiliza (no se muestra en el diagrama anterior). El valor se guarda al ingresar a la subrutina. Tener dicho campo en una ubicación conocida en el marco de la 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 del marco al marco de la persona que llama , justo antes de que regrese.
Los lenguajes de programación que soportan 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, es decir, el alcance inmediato del destinatario. 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 de encapsulación en cada anidamiento. nivel. Algunas arquitecturas, compiladores o casos de optimización almacenan un enlace para cada nivel adjunto (no solo el inmediatamente adjunto), de modo que las rutinas profundamente anidadas que acceden a datos poco profundos no tengan que atravesar varios enlaces; Esta estrategia a menudo se denomina "pantalla". [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 soportar funciones anidadas, mientras que los compiladores de 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.
Para algunos propósitos, se puede considerar que el marco de pila de una subrutina y el de su llamador se superponen, y la superposición consiste en el área donde los parámetros se pasan del llamador al destinatario. En algunos entornos, la persona que llama inserta cada argumento en la pila, extendiendo así su marco de pila y luego invoca a la persona que llama. En otros entornos, la persona que llama tiene un área preasignada en la parte superior de su marco de pila para guardar los argumentos que proporciona a otras subrutinas que llama. Esta área a veces se denomina área de argumentos salientes o área de llamadas . Bajo este enfoque, el compilador calcula el tamaño del área para que sea el más grande que necesita 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 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 registros, según lo determine la convención de llamada utilizada . La instrucción de llamada real, como "bifurcación y enlace", generalmente se ejecuta para transferir el control al código de la subrutina de destino.
En la subrutina llamada, el primer código ejecutado generalmente se denomina prólogo de subrutina , ya que realiza las tareas domésticas necesarias antes de que comience el código para las declaraciones de la rutina.
Para 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 insertando el valor en la pila de llamadas, aunque si el objeto llamado la subrutina no llama a ninguna otra rutina, puede dejar el valor en el registro. De manera similar, se pueden insertar 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 desde el puntero de pila. Luego se puede asignar espacio en la pila para variables locales cambiando incrementalmente el puntero de la 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. Por lo general, esto restaurará los valores de registro guardados (como el valor del puntero del marco) del marco de la pila, sacará todo el marco de la pila de la pila cambiando el valor del puntero de la pila y finalmente pasará a la instrucción en la dirección de retorno. Según muchas convenciones de llamada, los elementos que salen de la pila mediante el epílogo incluyen los valores de los argumentos originales, en cuyo caso generalmente no hay más manipulaciones de la pila que deba realizar la persona que llama. Sin embargo, con algunas convenciones de llamada, es responsabilidad de quien llama 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, quizás dejando un valor de retorno. El acto más general de sacar uno o más fotogramas de la pila para reanudar la ejecución en otra parte del programa se denomina desenrollado de la pila y debe realizarse cuando se utilizan estructuras de control no locales, como las utilizadas para el manejo de excepciones . En este caso, el marco de pila de una función contiene una o más entradas que especifican controladores de excepciones. Cuando se lanza una excepción, la pila se desenrolla hasta que se encuentra un controlador que esté preparado para manejar (capturar) el tipo de excepción lanzada.
Algunos idiomas tienen otras estructuras de control que requieren una relajación general. Pascal permite que una instrucción goto global transfiera el control de una función anidada a una función externa previamente invocada. Esta operación requiere que se desenrolle la pila, eliminando tantos marcos de pila como sea necesario para restaurar el contexto adecuado para transferir el control a la declaración de destino dentro de la función externa adjunta. 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 uso del 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. Ésta no es la única forma de implementar continuaciones; por ejemplo, al utilizar pilas múltiples y explícitas, la aplicación de una continuación puede simplemente activar su pila y enrollar un valor para pasar. El lenguaje de programación Scheme permite ejecutar procesadores arbitrarios en puntos específicos al "desenrollar" o "rebobinar" la pila de control cuando se invoca una continuación.
A veces, la pila de llamadas se puede inspeccionar mientras se ejecuta el programa. Dependiendo de cómo se escribe y compila el programa, la información de la pila se puede utilizar para determinar valores intermedios y seguimientos de llamadas a funciones. Esto se ha utilizado para generar pruebas automatizadas detalladas [4] y, en casos como Ruby y Smalltalk, para implementar continuaciones de primera clase. Como ejemplo, el GNU Debugger (GDB) implementa una inspección interactiva de la pila de llamadas de un programa C en ejecución, pero en pausa. [5]
Tomar muestras periódicas de la pila de llamadas puede ser útil para perfilar el rendimiento de los programas, ya que si el puntero 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 matrices no verificadas (como en C), la combinación de datos de flujo de control que afecta 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 para la seguridad y posiblemente se pueda explotar mediante desbordamientos del búfer de la pila , que son el tipo más común de desbordamiento del búfer .
Uno de esos ataques implica 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 apunte directamente al código ejecutable. Como resultado, cuando la función regresa, 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 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]
