assembly - ¿Cómo funciona exactamente la pila de llamadas?

cpu callstack

Question

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 geniales. Pero aún hay una cosa que aún no entendí del todo.

Considere esta función en un pseudo código que tiende a ser un código de 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é ocurre después de la línea X? Porque, obviamente, lo siguiente que necesitamos es trabajar con b , pero eso significaría que el sistema operativo / CPU (?) Tiene que salir d y c primero para volver a a y b . Pero luego se dispararía en el pie, porque necesita d en la siguiente línea.

Entonces, me pregunto qué pasa exactamente detrás de las escenas?

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);
}

De cómo entiendo las cosas, esto significaría que los parámetros en doSomething están esencialmente apuntando a la misma dirección de memoria como a y b en foo . Pero, de nuevo, esto significa que no hay pop-up en la pila hasta que lleguemos a a y b sucediendo.

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

Answer 1

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

En breve:

No hay necesidad de mostrar los argumentos. Los argumentos transmitidos por el llamador foo para que funcione doSomething y las variables locales en doSomething se pueden referenciar como un desplazamiento desde el puntero base .
Asi que,

• Cuando se realiza una llamada de función, los argumentos de la función se PUSH en la pila. Estos argumentos son referenciados por el puntero base.
• Cuando la función regresa a su llamador, los argumentos de la función de retorno son POPed de la pila usando el método LIFO.

En detalle:

La regla es que cada llamada de función da como resultado una creación de un marco de pila (siendo la dirección mínima a la que volver). Por lo tanto, si funcA llama funcB y funcB llama a funcC , tres marcos de pila se configuran uno encima del otro. Cuando una función regresa, su cuadro se vuelve inválido . Una función de buen comportamiento actúa solo en su propio marco de pila y no traspasa la de otro. En otras palabras, el POPing se realiza en el marco de la pila en la parte superior (al regresar de la función).

La pila en tu pregunta es configurada por el visitante foo . Cuando se llaman doAnotherThing y doAnotherThing , configuran su propia pila. La figura puede ayudarte a entender esto:

Tenga en cuenta que, para acceder a los argumentos, el cuerpo de la función tendrá que recorrer hacia abajo (direcciones más altas) 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 tendrá que recorrer la pila (direcciones inferiores ) relativo a la ubicación donde se almacena la dirección de retorno . De hecho, el código generado por el compilador típico para la función hará exactamente esto. El compilador dedica un registro llamado EBP para esto (Puntero Base). Otro nombre para el mismo es el puntero de marco. El compilador típicamente, como primera cosa para el cuerpo de la función, empuja el valor de EBP actual a la pila y establece el EBP al 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), 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 llamado 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 llamada de función y la pila .
• Puntero de marco y variables locales .
• Desmontaje / Funciones x86 y Marcos de pila .

Answer 2

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

Pegaré un ejemplo de "Punteros y memoria" de Nick Parlante. Creo que la situación es un poco más simple de lo que imaginabas.

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:

Answer 3

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

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

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

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

Answer 4

La pila de llamadas también se podría llamar una pila de marcos.
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 a las que se llama . Las variables locales son empujadas y reventadas junto con esas tramas en los denominados prólogo de función y epilogue , respectivamente.

Dentro del marco, el orden de las variables no está especificado; Los compiladores "reordenan" las posiciones de las variables locales dentro de un marco de manera apropiada para optimizar su alineación, de modo que el procesador pueda buscarlas lo más rápido posible. El hecho crucial es que el desplazamiento de las variables con respecto a una dirección fija es constante durante toda la vida útil del cuadro , por lo que basta con tomar una dirección de anclaje, por ejemplo, la dirección del marco en sí, y trabajar con compensaciones de esa dirección para las variables. Dicha dirección de anclaje en realidad está contenida en el llamado puntero de base o marco que está almacenado en el registro EBP. Las compensaciones, por otro lado, son claramente conocidas en el momento de la compilación y, por lo tanto, están codificadas en el código de la máquina.

Este gráfico de Wikipedia muestra que la pila de llamadas típica está estructurada como ¹ :

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

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 función consiste en las tres primeras operaciones:

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

Luego cin se mueve al registro EDI ² y se llama get ; El valor de retorno está en EAX.

Hasta aquí todo bien. Ahora sucede lo interesante:

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

Finalmente,

• El valor de retorno de main se almacena en EAX: 0. Esto se debe a la declaración de return implícita. También puede ver xorl rax rax lugar de movl .
• salir y regresar al sitio de llamadas. leave abreviado este epílogo e implícitamente
  • Reemplaza el puntero de la pila con el puntero base y
  • Aparece el puntero base.

Después de realizar esta operación y ret , el recuadro se ha reventado efectivamente, aunque la persona que llama aún tiene que limpiar los argumentos mientras usamos la convención de llamadas cdecl. Otras convenciones, por ejemplo, stdcall, requieren que el destinatario arregle, por ejemplo, pasando la cantidad de bytes a ret .

Omisión del indicador de marco

También es posible no utilizar desplazamientos desde el puntero de 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 de marco esté disponible para uso arbitrario, pero puede imposibilitar la depuración en algunas máquinas y se desactivará implícitamente para algunas funciones . Es particularmente útil al compilar para procesadores con solo pocos registros, incluido x86.

Esta optimización se conoce como FPO (omisión de puntero de marco) y se establece por -fomit-frame-pointer en GCC y -Oy en Clang; tenga en cuenta que está implícitamente activado 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 más información, ver here y here .

¹ Como se señala en los comentarios, el puntero del marco se supone que apunta 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 las que comienzan con E. EAX designa los cuatro bytes de bajo orden de RAX. Usé los nombres de los registros de 32 bits para mayor claridad.

Answer 5

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

Al llamar a la subrutina utilizando cualquiera de las convenciones, cualquier parámetro se insertará en la pila antes de llamar a la rutina. El código de rutina luego empuja el valor actual del puntero de marco a la pila, copia el valor actual del puntero de pila en el puntero de marco y resta del puntero de pila el número de bytes utilizados por las variables locales [si hay alguno]. Una vez hecho esto, incluso si se envían datos adicionales a la pila, todas las variables locales se almacenarán en variables con un desplazamiento negativo constante desde el puntero de la pila, y se podrá acceder a todos los parámetros que la persona que llama aplicó a la pila. desplazamiento positivo constante desde el puntero del marco.

La diferencia entre las dos convenciones radica en la forma en que manejan una salida de la subrutina. En la convención C, la función de retorno copia el puntero de marco al puntero de pila [restaurándolo al valor que tenía justo después de que se presionó el puntero de marco anterior], muestra el valor del puntero de marco anterior y realiza una devolución. Cualquier parámetro que la persona que llamó haya insertado en la pila antes de la llamada permanecerá allí. En la convención de Pascal, después de hacer estallar el antiguo puntero de marco, el procesador muestra la dirección de retorno de la función, agrega al puntero de la pila el número de bytes de los parámetros empujados por la persona que llama, y ​​luego va a la dirección de devolución reventada. En el 68000 original, fue necesario utilizar una secuencia de 3 instrucciones para eliminar los parámetros de la persona que llama; los procesadores 8x86 y todos los de 680x0 posteriores al original incluyeron una instrucción "ret N" [o 680x0 equivalente] que añadiría N al puntero de la pila cuando se realiza una devolució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 de función. Sin embargo, requiere que la función llamada sepa exactamente cuántos bytes valen los parámetros que la persona que llama va a poner en la pila. Si no se puede presionar la cantidad adecuada de parámetros en la pila antes de llamar a una función que utiliza la convención de Pascal, casi se garantiza que causará un bloqueo. Esto se compensa, sin embargo, por el hecho de que un pequeño código adicional dentro de cada método llamado guardará el 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 C tiene la ventaja de permitir que las rutinas acepten una cantidad variable de parámetros, y de ser robustas incluso si una rutina no utiliza todos los parámetros que se pasan (la persona que llama sabrá cuántos bytes de parámetros vale y así podrá limpiarlos). Además, no es necesario realizar la limpieza de pila después de cada llamada de función. Si una rutina llama a cuatro funciones en secuencia, cada una de las cuales usa valores de cuatro bytes de parámetros, puede - en lugar de usar ADD SP,4 después de cada llamada, usar un ADD SP,16 despué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 anticuadas. Dado que los compiladores se han vuelto más eficientes en el uso del registro, 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 utilizar un puntero de marco, y por lo tanto no es necesario guardar y restaurar el anterior. Sin embargo, a veces es necesario utilizar las convenciones de llamadas anteriores al llamar a bibliotecas vinculadas para usarlas.

Answer 6

Ya hay algunas respuestas realmente buenas aquí. Sin embargo, si todavía le preocupa el comportamiento de LIFO de la pila, piense en ello como 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, solo está funcionando en el elemento en la parte superior de la pila: un único 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. En cambio, se pasan por referencia (o por puntero, que en realidad es solo semánticamente diferente). 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 solo funciona 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 recursión. El marco de la pila superior es el único objeto al que accede directamente el código. Cualquier otra cosa se accede indirectamente (a través de un puntero que vive en el marco de la pila superior).

Puede ser instructivo observar el conjunto de su pequeño programa, especialmente si 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 desde el puntero del marco de la pila, que es la forma en que el código de la función será escrito por el compilador. En el caso de un pase por referencia, verá instrucciones de acceso indirecto a la memoria a través de un puntero que está almacenado en algún desplazamiento desde el puntero del marco de pila.