¿Cómo funciona exactamente la pila de llamadas?

Estoy tratando de obtener una comprensión más profunda de cómo funcionan las operaciones de bajo nivel de los lenguajes de programación y especialmente cómo interactúan con el sistema operativo / CPU. Probablemente he leído todas las respuestas en cada hilo relacionado con pila / montón aquí en Stack Overflow, y todas son brillantes. Pero todavía hay una cosa que aún no entendí completamente.

Considere esta función en pseudocódigo que tiende a ser un código Rust válido ;-)

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(a, b);
    doAnotherThing(c, d);
}

Así es como supongo que la pila se verá en la línea X:

Stack

a +-------------+
  | 1           | 
b +-------------+     
  | 2           |  
c +-------------+
  | 3           | 
d +-------------+     
  | 4           | 
  +-------------+ 

Ahora, todo lo que he leído sobre cómo funciona la pila es que obedece estrictamente a las reglas LIFO (último en entrar, primero en salir). Al igual que un tipo de datos de pila en .NET, Java o cualquier otro lenguaje de programación.

Pero si ese es el caso, ¿qué sucede después de la línea X? Porque obviamente, lo siguiente que necesitamos es trabajar con ay b, pero eso significaría que el sistema operativo / CPU (?) Tiene que salir dy cprimero volver a ay b. Pero luego se dispararía en el pie, porque necesita cy den la siguiente línea.

Entonces, me pregunto qué sucede exactamente detrás de escena.

Otra pregunta relacionada. Considere que pasamos una referencia a una de las otras funciones como esta:

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(&a, &b);
    doAnotherThing(c, d);
}

Por cómo entiendo las cosas, esto significaría que los parámetros en doSomethingesencialmente apuntan a la misma dirección de memoria como ay ben foo. Pero, de nuevo, esto significa que no hay una ventana emergente en la pila hasta que lleguemos ayb ocurra.

Esos dos casos me hacen pensar que no he comprendido completamente cómo funciona exactamente la pila y cómo sigue estrictamente las reglas LIFO .

La pila de llamadas también podría denominarse pila de tramas.
Las cosas que se apilan después del principio LIFO no son las variables locales sino los marcos de pila completos ("llamadas") de las funciones que se llaman . Las variables locales se empujan y hacen estallar junto con esos fotogramas en la llamada función prólogo y epílogo , respectivamente.

Dentro del marco, el orden de las variables no está especificado en absoluto; Los compiladores "reordenan" las posiciones de las variables locales dentro de un marco de manera adecuada para optimizar su alineación, de modo que el procesador pueda recuperarlas lo más rápido posible. El hecho crucial es que el desplazamiento de las variables relativas a alguna dirección fija es constante durante toda la vida útil del marco , por lo que es suficiente tomar una dirección de anclaje, digamos, la dirección del propio marco, y trabajar con los desplazamientos de esa dirección para las variables. Dicha dirección de anclaje está realmente contenida en el llamado puntero base o marcoque se almacena en el registro EBP. Las compensaciones, por otro lado, se conocen claramente en el momento de la compilación y, por lo tanto, están codificadas en el código de máquina.

Este gráfico de Wikipedia muestra cómo se estructura la pila de llamadas típica como ¹ :

Agregamos el desplazamiento de una variable a la que queremos acceder a la dirección contenida en el puntero del marco y obtenemos la dirección de nuestra variable. Dicho brevemente, el código simplemente accede a ellos directamente a través de constantes desplazamientos en tiempo de compilación desde el puntero base; Es aritmética de puntero simple.

Ejemplo

#include <iostream>

int main()
{
    char c = std::cin.get();
    std::cout << c;
}

gcc.godbolt.org nos da

main:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp

    movl    std::cin, %edi
    call    std::basic_istream<char, std::char_traits<char> >::get()
    movb    %al, -1(%rbp)
    movsbl  -1(%rbp), %eax
    movl    %eax, %esi
    movl    std::cout, %edi
    call    [... the insertion operator for char, long thing... ]

    movl    $0, %eax
    leave
    ret

.. para main. Dividí el código en tres subsecciones. El prólogo de la función consta de las tres primeras operaciones:

• El puntero de la base se inserta en la pila.
• El puntero de pila se guarda en el puntero base
• El puntero de la pila se resta para dejar espacio para las variables locales.

Luego cinse mueve al registro EDI ² y getse llama; El valor de retorno está en EAX.

Hasta aquí todo bien. Ahora sucede lo interesante:

El byte de orden bajo de EAX, designado por el registro de 8 bits AL, se toma y se almacena en el byte inmediatamente después del puntero base : es decir -1(%rbp), el desplazamiento del puntero base es -1. Este byte es nuestra variablec . El desplazamiento es negativo porque la pila crece hacia abajo en x86. La siguiente operación se almacena cen EAX: EAX se mueve a ESI, coutse mueve a EDI y luego se llama al operador de inserción con couty csiendo los argumentos.

Finalmente,

• El valor de retorno de mainse almacena en EAX: 0. Eso se debe a la returndeclaración implícita . También puede ver en xorl rax raxlugar de movl.
• salir y volver al sitio de la llamada. leaveabrevia este epílogo e implícitamente
  • Reemplaza el puntero de la pila con el puntero base y
  • Saca el puntero de la base.

Después de esta operación y retse ha realizado, el marco se ha eliminado de manera efectiva, aunque el llamador aún tiene que limpiar los argumentos ya que estamos usando la convención de llamada cdecl. Otras convenciones, por ejemplo, stdcall, requieren que el destinatario de la llamada lo ordene, por ejemplo, pasando la cantidad de bytes a ret.

Omisión del puntero de cuadro

También es posible no utilizar compensaciones desde el puntero base / marco, sino desde el puntero de pila (ESB). Esto hace que el registro EBP, que de otro modo contendría el valor del puntero del marco, esté disponible para uso arbitrario, pero puede hacer que la depuración sea imposible en algunas máquinas y se desactivará implícitamente para algunas funciones . Es particularmente útil cuando se compila para procesadores con pocos registros, incluido x86.

Esta optimización se conoce como FPO (omisión de puntero de trama) y se establece -fomit-frame-pointeren GCC y -Oyen Clang; tenga en cuenta que se activa implícitamente por cada nivel de optimización> 0 si y solo si la depuración aún es posible, ya que no tiene ningún costo aparte de eso. Para obtener más información, consulte aquí y aquí .

¹ Como se señaló en los comentarios, el puntero del marco presumiblemente está destinado a apuntar a la dirección después de la dirección de retorno.

² Tenga en cuenta que los registros que comienzan con R son las contrapartes de 64 bits de los que comienzan con E. EAX designa los cuatro bytes de orden inferior de RAX. Usé los nombres de los registros de 32 bits para mayor claridad.

Porque obviamente, lo siguiente que necesitamos es trabajar con ayb, pero eso significaría que el sistema operativo / CPU (?) Tiene que aparecer primero en d y c para volver a ay b. Pero luego se dispararía en el pie porque necesita cyd en la siguiente línea.

En breve:

No es necesario hacer estallar los argumentos. Los argumentos pasados ​​por la persona fooque llama a la función doSomethingy las variables locales en se doSomething pueden hacer referencia como un desplazamiento del puntero base .
Entonces,

• Cuando se realiza una llamada a una función, los argumentos de la función se PUSHAN en la pila. Estos argumentos son referenciados además por el puntero base.
• Cuando la función regresa a su llamador, los argumentos de la función que regresa se hacen POP de la pila usando el método LIFO.

En detalle:

La regla es que cada llamada de función da como resultado la creación de un marco de pila (siendo el mínimo la dirección a la que volver). Entonces, si hay funcAllamadas funcBy funcBllamadas funcC, se configuran tres marcos de pila uno encima del otro. Cuando una función regresa, su marco deja de ser válido . Una función con buen comportamiento actúa solo en su propio marco de pila y no traspasa el de otra. En otras palabras, el POP se realiza en el marco de la pila en la parte superior (al regresar de la función).

La pila de su pregunta la configura la persona que llama foo. Cuando doSomethingy doAnotherThingpara los llamados, entonces configurar su propia pila. La figura puede ayudarlo a comprender esto:

Tenga en cuenta que, para acceder a los argumentos, el cuerpo de la función tendrá que recorrer hacia abajo (direcciones superiores) desde la ubicación donde se almacena la dirección de retorno, y para acceder a las variables locales, el cuerpo de la función deberá recorrer la pila (direcciones inferiores ) relativo a la ubicación donde se almacena la dirección de retorno. De hecho, el código típico generado por el compilador para la función hará exactamente esto. El compilador dedica un registro llamado EBP para esto (Base Pointer). Otro nombre para el mismo es puntero de marco. El compilador normalmente, como lo primero para el cuerpo de la función, empuja el valor actual de EBP a la pila y establece el EBP en el ESP actual. Esto significa que, una vez hecho esto, en cualquier parte del código de función, el argumento 1 es EBP + 8 de distancia (4 bytes para cada EBP de la persona que llama y la dirección de retorno), el argumento 2 es EBP + 12 (decimal) de distancia, variables locales están EBP-4n de distancia.

.
.
.
[ebp - 4]  (1st local variable)
[ebp]      (old ebp value)
[ebp + 4]  (return address)
[ebp + 8]  (1st argument)
[ebp + 12] (2nd argument)
[ebp + 16] (3rd function argument) 

Eche un vistazo al siguiente código C para la formación del marco de pila de la función:

void MyFunction(int x, int y, int z)
{
     int a, int b, int c;
     ...
}

Cuando la persona que llama lo llama

MyFunction(10, 5, 2);  

se generará el siguiente código

^
| call _MyFunction  ; Equivalent to: 
|                   ; push eip + 2
|                   ; jmp _MyFunction
| push 2            ; Push first argument  
| push 5            ; Push second argument  
| push 10           ; Push third argument  

y el código de ensamblaje para la función será (configurado por el destinatario antes de regresar)

^
| _MyFunction:
|  sub esp, 12 ; sizeof(a) + sizeof(b) + sizeof(c)
|  ;x = [ebp + 8], y = [ebp + 12], z = [ebp + 16]
|  ;a = [ebp - 4] = [esp + 8], b = [ebp - 8] = [esp + 4], c = [ebp - 12] =   [esp]
|  mov ebp, esp
|  push ebp
 

Referencias:

• Convenciones de llamadas de función y la pila .
• Puntero de cuadro y variables locales .
• Desmontaje x86 / Funciones y marcos de pila .

Como señalaron otros, no hay necesidad de hacer estallar parámetros hasta que se salgan del alcance.

Pegaré algún ejemplo de "Pointers and Memory" de Nick Parlante. Creo que la situación es un poco más simple de lo que imaginaba.

Aquí está el código:

void X() 
{
  int a = 1;
  int b = 2;

  // T1
  Y(a);

  // T3
  Y(b);

  // T5
}

void Y(int p) 
{
  int q;
  q = p + 2;
  // T2 (first time through), T4 (second time through)
}

Los puntos en el tiempo T1, T2, etc. están marcados en el código y el estado de la memoria en ese momento se muestra en el dibujo:

Los diferentes procesadores e idiomas utilizan algunos diseños de pila diferentes. Dos patrones tradicionales tanto en el 8x86 como en el 68000 se denominan convención de llamada de Pascal y convención de llamada de C; cada convención se maneja de la misma manera en ambos procesadores, excepto los nombres de los registros. Cada uno usa dos registros para administrar la pila y las variables asociadas, llamados puntero de pila (SP o A7) y puntero de marco (BP o A6).

Al llamar a una subrutina usando cualquiera de las convenciones, los parámetros se insertan en la pila antes de llamar a la rutina. El código de la rutina luego empuja el valor actual del puntero del marco a la pila, copia el valor actual del puntero de la pila al puntero del marco y resta del puntero de la pila el número de bytes usados ​​por las variables locales [si las hay]. Una vez hecho esto, incluso si se introducen datos adicionales en la pila, todas las variables locales se almacenarán en variables con un desplazamiento negativo constante desde el puntero de la pila, y se puede acceder a todos los parámetros que el llamador empujó en la pila en un desplazamiento positivo constante desde el puntero del marco.

La diferencia entre las dos convenciones radica en la forma en que manejan una salida de subrutina. En la convención de C, la función de retorno copia el puntero del marco al puntero de la pila [restaurándolo al valor que tenía justo después de que se empujó el puntero del marco anterior], saca el valor del puntero del marco anterior y realiza un retorno. Cualquier parámetro que la persona que llama haya introducido en la pila antes de la llamada permanecerá allí. En la convención de Pascal, después de sacar el puntero del marco antiguo, el procesador muestra la dirección de retorno de la función, agrega al puntero de la pila el número de bytes de parámetros empujados por la persona que llama y luego va a la dirección de retorno emergente. En el 68000 original era necesario utilizar una secuencia de 3 instrucciones para eliminar los parámetros de la persona que llama; los procesadores 8x86 y todos los 680x0 posteriores al original incluían una "ret N"

La convención de Pascal tiene la ventaja de guardar un poco de código en el lado de la persona que llama, ya que la persona que llama no tiene que actualizar el puntero de la pila después de una llamada a una función. Sin embargo, requiere que la función llamada sepa exactamente cuántos bytes de parámetros va a colocar la persona que llama en la pila. Es casi seguro que no enviar el número adecuado de parámetros a la pila antes de llamar a una función que usa la convención de Pascal provocará un bloqueo. Sin embargo, esto se compensa por el hecho de que un poco de código adicional dentro de cada método llamado guardará código en los lugares donde se llama al método. Por esa razón, la mayoría de las rutinas originales de la caja de herramientas de Macintosh usaban la convención de llamadas de Pascal.

La convención de llamadas de C tiene la ventaja de permitir que las rutinas acepten un número variable de parámetros y ser robustas incluso si una rutina no usa todos los parámetros que se pasan (la persona que llama sabrá cuántos bytes de los parámetros presionó, y así podrá limpiarlos). Además, no es necesario realizar una limpieza de la pila después de cada llamada a una función. Si una rutina llama a cuatro funciones en secuencia, cada una de las cuales usó cuatro bytes de parámetros, puede, en lugar de usar un ADD SP,4después de cada llamada, usar una ADD SP,16después de la última llamada para limpiar los parámetros de las cuatro llamadas.

Hoy en día, las convenciones de llamadas descritas se consideran algo anticuadas. Dado que los compiladores se han vuelto más eficientes en el uso de registros, es común que los métodos acepten algunos parámetros en los registros en lugar de requerir que todos los parámetros se inserten en la pila; si un método puede usar registros para contener todos los parámetros y variables locales, no es necesario usar un puntero de marco y, por lo tanto, no es necesario guardar y restaurar el anterior. Aún así, a veces es necesario usar las convenciones de llamadas más antiguas al llamar a las bibliotecas que estaban vinculadas para usarlas.

Ya hay algunas respuestas realmente buenas aquí. Sin embargo, si todavía le preocupa el comportamiento LIFO de la pila, considérelo una pila de marcos, en lugar de una pila de variables. Lo que quiero sugerir es que, aunque una función puede acceder a variables que no están en la parte superior de la pila, todavía está operando solo en el elemento en la parte superior de la pila: un solo marco de pila.

Por supuesto, hay excepciones a esto. Las variables locales de toda la cadena de llamadas todavía están asignadas y disponibles. Pero no se accederá directamente a ellos. En cambio, se pasan por referencia (o por puntero, que en realidad solo es diferente semánticamente). En este caso, se puede acceder a una variable local de un marco de pila mucho más abajo. Pero incluso en este caso, la función que se está ejecutando actualmente sigue operando solo con sus propios datos locales. Está accediendo a una referencia almacenada en su propio marco de pila, que puede ser una referencia a algo en el montón, en la memoria estática o más abajo en la pila.

Esta es la parte de la abstracción de la pila que hace que las funciones se puedan llamar en cualquier orden y permite la recursividad. El marco de la pila superior es el único objeto al que el código accede directamente. Se accede a cualquier otra cosa indirectamente (a través de un puntero que vive en el marco de la pila superior).

Puede resultar instructivo observar el ensamblaje de su pequeño programa, especialmente si lo compila sin optimización. Creo que verá que todo el acceso a la memoria en su función ocurre a través de un desplazamiento del puntero del marco de pila, que es la forma en que el compilador escribirá el código de la función. En el caso de un pase por referencia, verá instrucciones de acceso a memoria indirectas a través de un puntero que se almacena en algún desplazamiento del puntero del marco de pila.

La pila de llamadas no es en realidad una estructura de datos de pila. Detrás de escena, las computadoras que usamos son implementaciones de la arquitectura de la máquina de acceso aleatorio. Por lo tanto, se puede acceder directamente a ayb.

Detrás de escena, la máquina hace:

• obtener "a" es igual a leer el valor del cuarto elemento debajo de la parte superior de la pila.
• obtener "b" es igual a leer el valor del tercer elemento debajo de la parte superior de la pila.

http://en.wikipedia.org/wiki/Random-access_machine

Aquí hay un diagrama que creé para la pila de llamadas de C. Es más precisa y contemporánea que las versiones de imágenes de Google.

Y correspondiente a la estructura exacta del diagrama anterior, aquí hay una depuración de notepad.exe x64 en Windows 7.

Las direcciones bajas y las direcciones altas se intercambian, por lo que la pila asciende en este diagrama. El rojo indica el marco exactamente como en el primer diagrama (que usó rojo y negro, pero el negro ahora ha sido reutilizado); el negro es el espacio del hogar; el azul es la dirección de retorno, que es un desplazamiento de la función de llamada a la instrucción posterior a la llamada; naranja es la alineación y rosa es donde apunta el puntero de instrucción justo después de la llamada y antes de la primera instrucción. El valor de retorno de espacio de inicio + es el marco más pequeño permitido en Windows y, como se debe mantener la alineación rsp de 16 bytes justo al comienzo de la función llamada, esto siempre incluye una alineación de 8 bytes también.BaseThreadInitThunk y así.

Los marcos de función rojos describen lo que la función del destinatario lógicamente 'posee' + lee / modifica (puede modificar un parámetro pasado en la pila que era demasiado grande para pasar en un registro en -Ofast). Las líneas verdes delimitan el espacio que la función se asigna desde el principio hasta el final de la función.